[자료구조] Array (배열)

배열

정의 : 인덱스와 값 <index, value> 의 쌍으로 구성된 집합.

배열의 추상 데이터 타입(ADT)

Object : 집합 (아무 자료형)에 속한 값이 존재하는 <, >쌍의 집합. Fuctions :  모든 , , , 에 대하여     = return 차원의 배열.         = if ()     return 배열 의 인덱스 값에 포함되어 있는 항목.     else return 에러.    = if ()     return 새로운 쌍 <, >가 삽입된 배열 .     else return 에러.

C 언어에서의 배열

1. 1차원 배열

C언어에서 1차원 배열을 선언하는 방법은 두가지가 있다.

int array[5];
int *parray[5];

첫 번째 배열은 5개의 정수를 선언한것이고,

두 번째 배열은 정수에 대한 5개의 포인터를 정의하였다.

C에서는 모든 배열의 인덱스는 0에서 시작하므로 첫번째 배열의 각각의 원소는 array[0], array[1], array[2], array[3], array[4]로서, 각각 하나의 정수 값을 포함한다.

마찬가지로 parray의 배열 원소는 parray[0], parray[1], parray[2], parray[3], parray[4]로서, 각각 하나의 정수에 대한 포인터를 포함한다.

배열의 첫 번째 원소인 array[0]의 주소는 기본 주소(base address)라 한다. 각 배열이름름을 가리키는 포인터이다.

사용하는 컴퓨터의 정수의 크기를 라고 하면 array[]의 주소는 가 된다(는 기본 주소). 그러므로 배열의 타입과 관계없이 (array + )와 &array[i]는 항상 같다. 그러므로 *(parray + )와 parray[]도 항상 같다.

2. 다차원 배열

C언어는 다차원 배열을 표현하기 위하여 배열의 배열을 사용하고 있다. 다음과 같이 2차원 배열을 선언하면,

int 2dArray[2][4];

크기가 2인 1차원배열 2dArray가 생성되고 이 2dArray의 각 원소는 크기가 4인 1차원 배열이다.

3. 동적 배열

프로그램에서 배열의 크기가 미리 정해놓은 것을 넘어갈 수도 있고, 너무 커서 사용되지 않는 부분이 있어 낭비될 수도 있기 때문에 C에서는 프로그램의 실행시간(runtime) 때 할당해주는 크기를 정할 수 있는 동적 배열 라이브러리를 제공한다.

stdlib.h 헤더파일에 정의되어 있다.

자주 사용하는 함수는 

void* malloc(size_t size) 인데 size만큼의 메모리를 할당한다.

1차원 배열은 다음과 같이 동적 할당 할 수 있다.

int *list;
list = (int*)malloc(sizeof(int) * 5);

정수형 포인터 list에 5개 만큼의 정수의 크기를 가지는 배열을 동적 할당한 것이다. 

다차원 배열은 1차원 배열의 1차원 배열이므로, 한 차원씩 동적 할당을 해주면 된다.

int **list;
int i;
 
list = (int**)malloc(sizeof(int*) * 5);
 
for (i = 0; i < 5; i++)
    list[i] = (int*)malloc(sizeof(int)*3));

동적 할당으로 배열을 만든 후 더 이상 쓰지 않을 때도 그 부분의 메모리는 계속 할당이 되어 있기 때문에 더 이상 쓰지 않을 때는 free 함수를 써서 할당된 공간을 해제시키는 것이 좋다.

int *list;
 
list = (int*)malloc(sizeof(int) * 5);
 
...
 
//사용완료
 
free(list);

다차원 배열은 가장 마지막에 동적 할당한 부분부터 free 함수를 써주면 된다. 동적 할당을 해준 역순으로 할당 해제를 해준다고 생각하면 쉽다.

int **list;
int i;
 
list = (int**)malloc(sizeof(int*) * 5);
 
for (i = 0; i < 5; i++)
    list[i] = (int*)malloc(sizeof(int)*3));
 
...
 
//사용완료
 
for (i = 0; i < 5; i++)
    free(list[i]);
 
free(list);