[DS] Ch2. Arrays and Structures

Data Structure

• Data Structure = data type + storage structure
  1) Data type : 데이터를 어떻게 범주화하는가?
  Object + operator
  ex) int, float, double, char, struct, pointer
  2) Storage structure : 데이터가 메모리에 저장될 때 어떤 구조를 갖는가?

• 어떤 data structure를 사용하느냐에 따라 프로그램의 성능이 달라질 수 있음

• Abstract Data Type (ADT) : Data type에 대한 정의와 기능들
  

Abstract Data Type (ADT) of Array

• <index, value> 쌍의 집합
  ex) list[0] = 10, list[1] = 20, list[2] = 30, list[3] = 40
  => <index, value>의 집합으로 표현
  => <0, 10> <1, 20> <2, 30> <3, 40>

• Operations:
  retrieves a value(value 반환) => v=list[1] (v에 list[1]의 값 가져옴)
  stores a value(value 저장) => list[1]=50 (list[1]에 50이라는 값 저장)

1D Array Representation In C

• 참고:

int *p; (선언)  // int 형을 가리키는 포인터
*p (명령문 내)  // p가 가리키고 있는 곳의 내용

int a[50];
sizeof(int);  // 4byte
// 필요한 메모리 공간 : 4*50 = 200byte

• char x[4] = {a, b, c, d} / char x[] = {a, b, c, d}
  (x는 포인터로 사용 가능. char size만큼 증가)

• 메모리 내 연속적인 공간에 저장됨.-

• location(x[i]) = start + i = x + i

1D Array Addressing

• int one[] = {0,1,2,3,4};
  print1(one, 5); // one 자체가 포인터이므로 시작 주소로 one을 넘겨줘도 됨.
  print1(&one[0], 5);

void print1(int *ptr, int row)
{
	int i;
    printf("Address Contents\n");
    for (i = 0; i < rows; i++)
    	printf("%8u%5d\n", ptr+i, *(ptr+i));
    printf("\n");
}
// 포인터는 어떤 주소를 가리키고 있고, 
// 그 주소 안에 있는 내용을 가져오려면 * 붙이면 됨.

• Pointer and Arrays

int *list1, list2[5];
list1 = list2;  // list2가 가리키고 있는 것을 list1이 가리키게 하라.

list2 == &list2[0]
list2 + i == &list1[i]
*(list1+i) == list2[i]

1D Array Program : examples

• &(ampersand) : reference operator ("address of")
• *(asterisk) : dereference operator ("value pointed by")

#define MAX_SIZE 100
float sum(float [], int);
float input[MAX_SIZE], answer;
int i;
float sum(float list[], int n)
{
	int i;
    float tempsum = 0;
    for (i = 0; i < n; i++)
    	tempsum += list[i];  // "list[i]에 있는 값" (dereferencing)
    return tempsum;
}
void main(void)
{
	for (i = 0; i < MAX_SIZE; i++)
    	input[i] = i;  // "input[i]라는 위치"에 i라는 값을 넣어라. (referencing)
        // input[i] == &input[i]
    answer = sum(input, MAX_SIZE);
    printf("The sum is: %f\n", answer);
}

• list[i]가 '='의 우측 : (list+i)가 가리키는 값 반환
  list[i]가 '='의 좌측 : 값을 (list+i) 위치에 저장

2D Arrays

• 행(row) 렬(column)

a[0][0] a[0][1] a[0][2] a[0][3]
a[1][0] a[1][1] a[1][2] a[1][3]
a[2][0] a[2][1] a[2][2] a[2][3]
..........................................................
10 20 30 40
50 60 70 80
90 100 110 120

• row-major => {10, 20, 30, 40, 50, 60, ..., 120}
  column-major => {10,50, 90, 20, 60, 100, ..., 80, 120}

Representation of arrays (1)

• Row major order example
  A[2][3][2][2] : 2x3x2x2 = 24개 원소
  A[0][0][0][0], A[0][0][0][1], ... , A[1][2][1][0], A[1][2][1][1]
  => 오른쪽 끝부터 바뀌어 감.
  (Column major order인 경우, 왼쪽 끝부터 바뀌어 감)

• 4차원 Array
  A[u1][u2][u3][u4]일 때, 시작주소 a라면,
  A[i][j][k][m] -> a + i * u2u3u4 + j * u3u4+ k * u4 + m

Representation of arrays (2)

• 2차원 Array
  A[u1][u2]일 때, 시작주소 a라면,
  A[i][j] -> a + i * u2 + j

• 3차원 Array
  A[u1][u2][u3]일 때, 시작주소 a라면,
  A[i][j][k] -> a + i * u2u3 + j * u3 + k

Representation of arrays (3)

• n차원 Array
  A[u0][u1][u2]...[un-1]일 때, 시작주소 a라면,
  A[i0][i1]...[in-1] ->
  a + i0 * u1u2...un-1 + i1 * u2u3...un-1 + ... + in-2 * un-1 + in-1

Dynamic memory allocation

// 2차원 array를 dynamic memory allocation으로 만들기

int **myArray;
myArray = make2dArray(5,10);
myArray[2][4] = 6;

int** make2dArray(int rows, int cols)
{
	int **x, i;  // **x는 포인터 array x[ ]를 가리키는 포인터임. (더블 포인터)
    
    MALLOC(x, rows*sizeof(*x));  // *x는 포인터
    
    for (i = 0; i < rows; i++)
		MALLOC(x[i], cols*sizeof(**x));  // **x는 포인터가 가리키는 값(원소의 크기)
    
    return x;
}

• 2차원 array를 만들기 위해서는 2차원 array의 각 행에 해당하는 부분을 각각 1차원 array로 만들면 됨.
  ex) int x[2][3] = {1,2,3,4,5,6}
  x[ ]는 포인터 array
  x[0] -> 1차원 array {1,2,3}
  x[1] -> 1차원 array {4,5,6}