Data_Structure Ch.2

Chapter 2. Arrays and Structures

Arrays

배열이란 연속적인 메모리로 구현된 집합을 의미한다. 이를 ADT로 표현하면 <index, value>로 할 수 있다. 새로운 배열을 만들 때, 대부분의 프로그래밍 언어들은 (1) 값을 저장, (2) 값을 검색하는 기능을 기본으로 넣어놓았다.
C에서의 배열 선언은 다음과 같다.

int arr[5]; 
// C는 arr[i]를 int포인터로 해석한다. 그래서 *(arr + 1) == arr[1]이다.

Dynamicaly Allocated Array

기존 배열은 길이 변경이 불가능했다. 이를 해결하기 위해 동적 할당 배열을 사용한다. C에서는 다음과 같이 표현한다.

int len; scanf("%d", &len);
int* arr = (int*)malloc(sizeof(int) * len);
int* arr2 = (int*)calloc(len, sizeof(int));
realloc(arr, sizeof(int) * (len + 5));

Structures

구조체는 많은 데이터의 집합을 의미한다. 다음 구조체를 보자.

typedef struct node{
    int val;
    node* nxt;
};

노드에 대한 구조체이며, 각 노드는 데이터와 다음 위치의 주소를 가지고 있다.

구조체가 자기 자신을 포인터로 가지고 있는 경우, 이를 Self-Referential Structures라고 한다. 주로 동적할당을 이용한다.

typedef를 사용하는 이유는 c에선 typedef 없이 struct를 선언하면 매 node 선언시마다 앞에 struct를 사용해야 하기 때문이다. C++과의 차이점이니 알아두자.
컴파일러가 구조체를 메모리에 어떻게 저장하는지는 그다지 신경쓸 필요가 없다. 그냥 구조체 정의 순서대로 저장한다 생각하자.

Unions

동일한 메모리 공간을 소요하며, 구조체처럼 여러 변수가 들어있으나 그 중 활성화된 한개만을 사용한다.