[자료구조] 3. 배열, 구조체, 포인터

3.1 배열

• A[i] - i: 시작번지로부터 (sizeof(double)) 크기 만큼의 offset --> O(1) random lookup time
• 처리해야 할 각 데이터의 ID를 배열의 index로 사용할 수 있는 경우, 간단하고 읽기 쉬운 알고리즘 작성이 가능하다.

1차원 배열, 2차원 배

 

배열의 응용: 다항식

#1 모든 차수의 계수값을 배열에 저장한다.

• degree: 다항식의 차수 저장
• coef: 모든 차수에 대한 계수값 저장

#1 모든 차수의 계수값을 배열에 저장한다.

 

#2 다항식에서 0이 아닌 항만을 하나의 전역 배열에 저장한다.

: (계수, 차수) 형식으로 배열에 저장한다.

• expon: 차수를 저장하는 변수

#2 다항식에서 0이 아닌 항만을 하나의 전역 배열에 저장한다.

▷ 다항식 덧셈

: A와 B의 차수를 비교하여(expon), 차수가 같으면 계수를 더해서 C로 옮기고, 차수가 다르면 A와 B 중에서 차수가 큰 항을 C로 옮긴다.

 다항식 덧셈

 

배열의 응용: 희소 행렬

#1 2차원 배열: a[i][j];

--> 행렬 전치: a[j][i];

2차원 배열: a[i][j];

▷ int A[ROWS][COLS], int B[ROWS][COLS];

: int에서 4B, ROWS/COLS에서 6B이므로, 4*6*6 B이다.

 

#2 배열을 이용하되, 0이 아닌 요소들만을 나타내는 방법

#1 방법과 #2 방법 중 무엇이 더 이득인가?

▷ SparseMatrix
: element에서 12B, int rows, cols, terms에서 12B이므로, (12B * terms + 12)B가 된다.

--> 그렇다면, 4*6*6 > 12*terms + 12 일 때, #2 방법이 더 유리하다.

• term: 0이 아닌 것의 개수; 즉, 0이 아닌 것의 개수가 ?개 이하여야, #2 방법 유리하다.

col(열)부터 하는 이

 

3.2 구조체

: 타입이 다른 데이터를 하나로 묶는 방법

 

▶ struct vs. union

struct vs. union

struct, typedef

 

 

3.5 포인터

포인터 연산

▶ 널 포인터

• p = NULL

 

▶ 함수를 매개변수로 포인터 사용하기

: 포인터를 이용하여 함수 안에서 외부 변수의 값을 변경할 수 있다.

 

▶ 배열과 포인터

• 배열의 이름 = 배열의 시작 위치를 가리키는 포인터

 

 

3.6 동적 메모리 할당 (Dynamic Memory Allocation)

: 필요한 만큼 메모리를 운영체제로부터 할당받아 사용하고, 사용이 끝나면 메모리 반납

• 히프(heap): 동적 메모리가 할당되는 공간

동적 메모리 할당 (Dynamic Memory Allocation)

• variable = malloc();
  : 동적 메모리 할당 후, 할당된 메모리 블록의 시작 주소를 return
• free(variable);
  : 할당된 메모리 블록을 운영체제에게 반환
  - 반드시 malloc() 함수가 return한 포인터 값을 기억해야 한다.