[CS50-2019] C언어 총정리-(10) 자료구조

[1] 배열

(1) 배열 : 같은 자료형의 데이터들을 하나의 변수로 정의, 각 인덱스위 값이 메모리상에서 연이어 저장됨

array =

int

int

int

int

* 파이썬은 서로 다른 자료형의 데이터들도 하나의 변수로 정의할 수 있다.(= list)

 

(2) 배열의 크기 조정 : realloc

일정한 크기의 배열이 주어졌을때, 그 크기를 확장하기 위해서는 새로운 공간에 큰 크기의 메모리를 다시 할당하고 값을 복사해야 한다

malloc (메모리 할당)	realloc (배열 크기 조정)
#include <stdio.h> // printf를 쓰기 위해 헤더파일 추가 #include <stdlib.h> // malloc을 사용하기위해 헤더파일 추가 int main(void) {     int *list = malloc (3*sizeof(int));     if(list == NULL)     // 만약 메모리가 다 차서 할당하지 못하게 되면     {      // 프로그램을 끝내라          return 1;      }     list[0] = 1;     list[1] = 2;     list[2] = 3;
// 배열의 크기를 3 → 4로 변경하고 싶음     // 바로 list에 malloc을 사용하면 이전에 쓰던 메모리들은     포인터를 잃고 떠돌아 다니게 됨(메모리 낭비)     int * temp = malloc(4* sizeof(int));     if(temp == NULL)      // 포인터가 잘 선언되었는지 확인     {        return 1;      }     // old 배열에서 new 배열로 정수 값 복사     for (int i = 0; i<3; i++)     {         tmp[i] = list[i];      }      tem[3] = 4;      free(list); // list의 메모리 할당 해제      list = tmp; // 원래 포인터 이름을 그대로 쓰기 위해      for (int i=0; i<4; i++)      {          printf("%i\n", list[i]);         }       free(list); }	// tem포인터에 메모리를 할당하고 list값 복사     int * temp = realloc(list, 4* sizeof(int));     if(temp == NULL)      {        return 1;      }      // list가 tmp와 같은 곳을 가리키도록 지정      list = temp;         // 새로운 list의 네번째 값 저장      list[3] = 4;       //list의 값 확인       for (int i=0; i<4; i++)      {          printf("%i\n", list[i]);         }       // list의 메모리 초기화       free(list); }
출력결과 1 2 3 4

 

 

[2] 연결리스트

(1) 연결리스트 : 각 인덱스의 메모리 주소에서 자신의 값과 함께 바로 다음 값의 주소(포인터)를 저장하므로써 연결

크기가 3인 연결리스트는 자신의 값과 함께 바로 다음 값의 주소(포인터)를 저장			typedef struct node(x같은거로 바꿀수 O, 구조체의 정식 명칭) {     int number;     struct node(x같은거로 바꿀수O) *next; } node(구조체의 별명, 프로그램의 다른부분에서 사용하기 쉽게);
1 주소: 0x123
0x456 →	2 주소: 0x456
↑이 두칸을 하나의 node라고 함	0x789 →	3 주소: 0x789
	↑이 두칸을 하나의 node라고 함	NULL (포인터) (16진법으로 0, \0인 NUL과는 다름)
		↑ 이 두칸을 하나의 node라고 함

 

* 연결리스트 구현해보기

node	node	node	node
list	2	4	5
→ 2를 가리킴	→ 4 를 가리킴	→ 5를 가리킴
// 비어있는 연결 리스트 구현 // NULL이기 때문에 화살표가 아직 안들어가있음 node *list = NULL; node *n = malloc(sizeof(node)); // malloc이 주소를 반환 // n이 node를 저장할 수 있는 크기의 메모리 덩어리를 가리키도록 만듬 즉, n은 node를 가리키는 포인터(n은 node*로 나타낼 수 있는 node 포인터, n은 node의 주소라는 뜻) // 그래서 n은 포인터이므로 n.number라고 못쓰고 n->number를 쓰는거임 if( n! = NULL)  {   n -> number = 2;    // (*n).number = 2; 와 같은 의미    // 이제 2 값에 다음 node의 주소를 적어줘야함    // 근데 다음 node가 없음    n->next = NULL; }    // node n을 list에 연결 list = n; node *n = malloc(sizeof(node)); if( n! = NULL)  {   n -> number = 4;    n->next = NULL; } node *tmp = list; while (tmp -> next != NULL)  // 가리키는 곳이 널이 아니면 다음 코드를 실행해라 } {   tmp = tem-> next; }
* list에 1 값을 앞에 넣고 싶은 경우, 3값을 중간에 넣고 싶은 경우
node	node	node	node
list	2	4	5
→ 2를 가리킴 ② ↓ 1을 가리키게 함	→ 4 를 가리킴 ② ↓ 3을 가리키게 함	→ 5 를 가리킴
node	node
1	3
① ↗ 2를 가리키게 함	① ↗  4 를 가리키게함
n -> next = list; list = n; 최종적으로 list → 1 → 2 → 3 → 4 → 5  이 과정에서 반복문과 대소비교, 포인터를 업데이트 하는 과정이 필요하다. 따라서 맨앞에 추가하는 것이 가장 쉽고, 맨뒤에추가하는것 그리고 중간에 추가하는거 순으로 점점 어려워진다.

 

(2) 트리

- 연결리스트를 기반으로 한 새로운 데이터 구조

- 연결리스트에서의 각 노드들의 연결이 1차원적으로 구성되어 있다면, 트리에서의 노드들의 연결은 2차원적으로 구성되어 있다고 볼 수 있다

이진 검색 트리

 

[3] 해시테이블

- 연결 리스트의 배열

- 여러 값들을 몇 개의 바구니에 나눠 담는 상황에서 각 값들은 '해시 함수'라는 맞춤형 함수를 통해 어떤 바구니에 담지는 지가 결정된다. 각 바구니에 담기는 값들은 그 바구니에서 새롭게 정의되는 연결 리스트로 이어진다.

- 이상적인 경우 각 바구니에는 단 하나의 값들만 담기게 될 것이므로 검색시간은 O(1), 최악의 경우 단 하나의 모든 값들이 담겨서 O(n)이 될 수도 있지만 일반적으로는 최대한 많은 바구니를 만드는 해시 함수를 사용하기 때문에 거의 O(1)에 가깝다.

해시테이블

 

[4] 트라이

- '트리' 형태의 자료 구조

- 각 노드가 배열로 이루어져 있다. 맨 위는 루트 노드. 루트 노드를 시작으로 각 화살표가 가리키는 알파벳을 따라가면서 노드를 이어준다.

- 트라이에서 값을 검색하는데 걸리는 시간은 문자열의 길이에 의해 한정되므로 일반적인 영어 이름의 길이를 n이라고 했을때, 검색시간은 O(n)이 되지만, 대부분의 이름은 그리 크지 않기 때문에 O(1)이나 마찬가지라고 볼 수 있다. 

트라이

[5] 큐

- 값이 아래로 쌓이는 구조

- 선입 선출(FIFO) : 가장 먼저 들어온 값이 가장 먼저 나가는 것 ex. 은행에서 번호표 순대로 일처리

→ 배열이나 연결리스트를 통해 구현이 가능

 

[6] 스택

- 값이 위로 쌓이는 구조

- 후입 선출(LIFO) : 가장 나중에 들어온 값이 가장 먼저 나가는 것 ex. 뷔페에서 가장 나중에 쌓인거부터 사용

→ 배열이나 연결리스트를 통해 구현이 가능

 

[7] 딕셔너리

- '키'와 '값'이라는 요소로 이루어짐 ex. '학번'에 따라 '학생'이 결정

- 일반적인 의미에서 '해시테이블'과 동일한 개념

- '키'를 어떻게 정의할 것인지가 중요함

 

※ 출처 :  CS50 - 2019 [네이버부스트코스] https://www.boostcourse.org/cs112/lecture/119038/?isDesc=false