2-1강 - ADT array, 동적 할당

cf> ADT

1) 구체적인 기능의 완성 과정은 서술하지 않고 오로지 순수하게 기능이 무엇인지만 나열하는 것

2) 속성

1> Objects (Characters) : ADT의 내부 속성 (OOP에서 classd의 내부 필드와 유사) ex> 자동차의 바퀴, 문, 핸들 등

2> Functions (Operations) : ADT의 연산 ex> 자동차 : 운전을 하다

 

 

---

1. Arrays

1) The Abstract Data Type

0> array를 단순히 '일련의 연속적인 메모리 위치'로만 보지 말자

- object : <index, value>의 쌍으로 구성된 집합 (index와 value간에 mapping이 존재)

- Functions (주목) : retrieving a value, storing a value (value를 불러오거나 저장하거나)

 

1> Objects

<index, value>쌍의 집합  

(전제 1: value가 item 집합 내부에 있으며, value와 index가 대응 관계) 

(전제 2: index는 1차원 또는 다차원의 유한 순서)

 

2> Functions

- Array Create(j, list) : j 차원의 array 생성 (list: i번째 원소가 i번째 차원의 크기인 j개 짜리 tuple)

- Item Retrieve(A, i) : (index에 포함된 i라면) index i에 해당하는 item value 출력 (포함 X => error)

- Array Store(A, i, x) : (index에 포함된 i라면) 새로운 쌍 <i, x>가 삽입된 배열 A를 출력 (포함 X => error)

2) Arrays in C

1> 구분할 것

int list[5]	5개의 원소를 포함하는 array 선언	각 원소는 정수값을 포함한다.
int *plist[5]		각 원소는 정수에 대한 포인터를 포함한다.

2> 1차원 배열의 메모리

- list[0]의 메모리 주소: 기본 주소(base address) = a

- list[i]의 메모리 주소: a + i*sizeof(int)  (정확히는 a+i로 표현하는 게 맞다.)

 

3> pointer와 array name

	(int *list1) list1	(int list2[5]) list2
정의	pointer	array name
공통점	둘 다 정수를 가리키는 포인터
주소 값의 변경		불가능 (++ 불가능) (5개 정수를 위한 메모리 위치가 예약되어 있다.)
기타	(int *list1 = list2) 포인터 변수가 배열을 참조하면 포인터 변수를 배열처럼 사용할 수 있다.

4> pointer 관계

		*(list2 + i)	=>	(list2 + i)	=>	&(list2 + i)
*list2[i]	=>	list2[i]	=>	&list2[i]	=>

 

 

---

 

2. Dynamically allocated arrays

사용할 배열이 크기를 결정하기에 아주 곤란한 경우가 있습니다.

이에 대한 좋은 해답은, 이 결정을 실행 시간까지 미루었다가 필요한 배열 크기가 결정될 때 배열을 할당하는 것입니다.

0) 기초

1> malloc : 할당한 메모리의 시작주소를 void pointer로 return

void* malloc (size_t size);

- 해당 메모리 영역을 할당하는데 실패 => NULL pointer return

- void pointer이므로 다른 type의 변수를 참조할 수 있다. (casting pointer)

 

2> free : 동적으로 할당 받은 메모리 영역(ptr)을 반환하는 함수

void free (void* ptr);

- 해제하려는 pointer가 NULL이면 아무 일도 하지 않는다.

 

3> 예시

int* p;
 
p = (int *)malloc(8*sizeof(int));

free(p);

 

4> calloc : 한 번에 여러 메모리를 만들며(마치 array같이) 할당한 메모리의 시작주소를 void pointer로 return한다.

<Contiguous Memoryallocation (contiguous: 인접한)>

void* calloc (size_t element-count, size_t element_size);

- element-count: 몇 개의 메모리를 만들 것인지

- element-size: 해당 자료의 size를 넣어야 한다. =>'sizeof(int)*n'을 보통 사용

 

5> realloc : 변수의 메모리(ptr)를 특정 크기(newSize)로 동적으로 변경

void* realloc(void *ptr, size_t newSize);

 

1) 1차원 배열

int n
int *list;

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

 

2) 2차원 배열

0> 쉽게 연상할 것

- '행' array의 원소들은 각각의 '열'에 대한 pointer이다. (그런데 열도 하나의 array이니 pointer이다.)

    => 그러므로 행은 이중 포인터

    => 행(열의 포인터 = 이중 포인터; ), 열(포인터)

- N-dimensional array 접근 시 앞의 index부터 접근 (원소 x[i][j]를 찾을 때 제일 먼저 x[i]에 있는 포인터에 접근한다.)

 

1> 이중 포인터 이용

- x : 행렬(2-dimension)을 담을 이중 포인터 선언

- x 동적 할당 : 행의 개수(rows)만큼 & int pointer 크기(sizeof(int*))만큼 할당

- x[i] : 각 행마다 열을 담을 포인터 할당해야 한다.

- x[i] 동적 할당 : 열의 개수(cols)만큼 & int 크기(sizeof(int))만큼 할당

int** make2dArray(int rows, int cols)
{
	int **x; // x는 2차원 배열 = x는 2중 포인터
	// 그래서 x에 이중 포인터를 동적 할당
	// 행 array 각 원소는 열 pointer이다.
	x = (int**)malloc(rows * sizeof(int*)); // 이중 포인터를 행의 크기 만큼 메모리 할당
	for (int i = 0; i < rows; i++)
	{
		x[i] = (int*)malloc(cols * sizeof(int)); // 각 열마다 열의 크기만큼 메모리 할당
	}
	return x;
}

 

2> 각 열마다 크기 다르게 하는 방법