[CS50 2019] 5. Data Structures

in Study #CS #C

모두를 위한 컴퓨터 과학

💡 메모리 동적 할당 관련 함수

malloc 함수 (메모리 할당)

int *arr = (int *)malloc(5 * sizeof(int)); // int 형 배열을 위한 20바이트 할당
  • 함수 원형: void *malloc(size_t size);
  • 동적으로 메모리를 할당하는 함수
  • size 매개변수는 할당하고자 하는 메모리의 크기를 의미
  • 할당된 메모리는 초기화되지 않음
  • 할당된 메모리의 시작 주소를 반환, 실패 시에는 NULL을 반환

calloc 함수 (메모리 할당 및 초기화)

int *arr = (int *)calloc(5, sizeof(int)); // int 형 배열을 위한 20바이트 할당 및 초기화
  • 함수 원형: void *calloc(size_t num_elements, size_t element_size);
  • 동적으로 메모리를 할당하며, 할당된 메모리를 모두 0으로 초기화
  • num_elements는 할당할 요소의 개수, element_size는 각 요소의 크기
  • 총 메모리 크기는 num_elements * element_size
  • 할당된 메모리의 시작 주소를 반환, 실패 시에는 NULL을 반환

realloc 함수 (메모리 재할당)

arr = (int *)realloc(arr, 10 * sizeof(int)); // 배열 크기를 10으로 재할당
  • 함수 원형: void *realloc(void *ptr, size_t size);
  • 이미 할당된 메모리의 크기를 변경할 때 사용
  • ptr은 이전에 할당된 메모리 포인터, size는 새롭게 할당하거나 조정하려는 메모리의 크기
  • 새로운 메모리 블록을 할당하고 이전 데이터를 새 메모리로 복사한 후, 이전 메모리를 해제
  • 새 메모리 블록의 시작 주소를 반환, 실패 시에는 NULL을 반환

1. 연결 리스트 (Linked List)

[data1] -> [data2] -> [data3] -> ... -> [dataN] -> NULL
  • 데이터 요소들이 순서대로 연결되어 있는 자료 구조
  • 각 데이터 요소는 자신의 데이터와 다음 요소를 가리키는 링크(포인터)로 이루어짐
  • 마지막 노드의 포인터는 보통 NULL을 가리킴
  • 배열과 비교해서 연결 리스트는 새로운 값을 추가할 때 다시 메모리를 할당하지 않아도 된다는 장점이 있음
  • but, 특정 인덱스에 직접 접근하는 데에는 O(n)의 시간이 걸림
⭐️ 구현 예시
typedef struct node
{
    int number;
    struct node *next;
}
node;
  • number는 각 node가 가지는 값, *next는 다음 node를 가리키는 포인터
  • 여기서 typedef struct 대신에 typedef struct node 라고 node를 함께 명시해주는 것은, 구조체 안에서 node를 사용하기 위함

예제 코드

연결 리스트를 생성하고 데이터를 출력하는 함수 구현

#include <stdio.h>
#include <stdlib.h>

// 연결 리스트의 기본 단위가 되는 node 구조체 정의
typedef struct node
{
    // node 안에서 정수형 값이 저장되는 변수를 name으로 지정
    int number;

    // 다음 node의 주소를 가리키는 포인터를  *next로 지정
    struct node *next;
}
node;

int main(void)
{
    // 첫번째 노드 생성
    node *node1 = malloc(sizeof(node));
    if (node1 == NULL)
    {
        return 1;
    }

    // 첫번째 노드에 데이터 삽입
    node1->number = 1;
    node1->next = NULL;
    
    // -------------------------------
    // 두번째 노드 생성
    node *node2 = malloc(sizeof(node));
    if (node2 == NULL)
    {
        return 1;
    }

    // 두번째 노드에 데이터 삽입
    node2->number = 2;
    node2->next = NULL;
    
    // 첫번째 노드와 두번째 노드 연결
    node1->next = node2;

    // -------------------------------
    // 세번째 노드 생성
    node *node3 = malloc(sizeof(node));
    if (node3 == NULL)
    {
        return 1;
    }

    // 세번째 노드에 데이터 삽입
    node3->number = 3;
    node3->next = NULL;

    // 두번째 노드와 세번째 노드 연결
    node2->next = node3;

    // -------------------------------
    // 각 노드들을 방문하며 number 데이터 출력
    for (node *tmp = node1; tmp != NULL; tmp = tmp->next)
    {
        printf("%i\n", tmp->number);
    }

    // 메모리 해제
    while (node1 != NULL)
    {
        node *tmp = node1->next;
        free(node1);
        node1 = tmp;
    }
}
🧐 연결 리스트의 중간에 node를 추가하려면?
// 새로운 노드 생성
node *node4 = malloc(sizeof(node));
if (node4 == NULL)
{
    return 1;
}
node4->number = 4;
node4->next = NULL;

// node2와 node3 사이에 node4 삽입
node2->next = node4;
node4->next = node3;

2. 트리 (Tree)

    A
   / \
  B   C
 / \
D   E
  • 연결 리스트를 기반으로 한 계층적인 자료 구조
  • 연결 리스트에서의 각 노드들의 연결이 1차원 적으로 구성되어 있다면, 트리에서의 노드들의 연결은 2차원적으로 구성
  • 각 노드는 일정한 층에 속하고, 다음 층의 노드들을 가리키는 포인터를 가짐
  • 이진 검색 트리와 같은 특수한 형태의 트리는 데이터의 검색 및 삽입이 매우 효율적임
  • but, 데이터를 삭제하는 과정이 복잡하고 메모리 사용량이 증가한다는 단점이 있음

✔ 트리의 주요 구성 요소

  • 루트 노드 (Root Node): 트리의 가장 상위에 위치한 노드
  • 부모 노드 (Parent Node): 특정 노드의 바로 위에 있는 노드
  • 자식 노드 (Child Node): 어떤 노드에 의해 생성된 하위 노드
⭐️ 구현 예시
typedef struct node       // 이진 검색 트리
{
    int number;
    struct node *left;    // 왼쪽 자식 노드
    struct node *right;   // 오른쪽 자식 노드
} node;

예제 코드

이진 검색 트리에서 “50”을 재귀적으로 검색하는 이진 검색 함수

// 이진 검색 함수 (*tree는 이진 검색 트리를 가리키는 포인터)
bool search(node *tree)
{
    // 트리가 비어있는 경우 ‘false’를 반환하고 함수 종료
    if (tree == NULL)
    {
        return false;
    }
    // 현재 노드의 값이 50보다 크면 왼쪽 노드 검색
    else if (50 < tree->number)
    {
        return search(tree->left);
    }
    // 현재 노드의 값이 50보다 작으면 오른쪽 노드 검색
    else if (50 > tree->number)
    {
        return search(tree->right);
    }
    // 위 모든 조건이 만족하지 않으면 노드의 값이 50이므로 ‘true’ 반환
    else {
        return true;
    }
}

위와 같은 이진 검색 함수를 구현했을 때, 이진 탐색 트리의 search와 insert 속도의 상한은 O(log n)

3. 해시 테이블 (Hash Table)

Index 0: [ ] 
Index 1: [ ]
Index 2: [ ] -> [Key1: Value1] -> [Key2: Value2]
Index 3: [ ] -> [Key3: Value3]
  • 연결 리스트의 배열
  • Key와 Value의 쌍을 저장하는 자료구조 중 하나로 빠르게 데이터 검색 가능
  • 각각의 Key값에 해시 함수를 적용해 해시값을 얻고, 이 해시값을 인덱스로 사용하여 배열에 값을 저장하거나 검색하는 방식
  • 해시테이블의 평균 시간복잡도는 O(1)이지만, 데이터의 충돌이 발생한 경우 O(n)까지 증가
  • 좋은 해시 함수는 Key들이 균일하게 해시되어야 하며, 충돌이 적게 발생해야 함
⭐️ 구현 예시
typedef struct Node {
    int key;
    int value;
    struct Node* next;
} Node;

typedef struct HashTable {
    Node* table[TABLE_SIZE];
} HashTable;

// 해시 함수 예시 (나눗셈을 통한 해시)
int hashFunction(int key) {
    return key % TABLE_SIZE;
}

4. 트라이 (Trie)

      (root)
     /  |  \
   a    b    c
  /|    |    |
 t d    i    a
  • 트리 자료 구조의 한 형태로 여러 문자열을 저장하고 검색하는 데에 유용
  • 특이한 점은 각 노드가 배열로 이루어져 있음
  • 루트에서 각 노드로 이어지는 경로가 문자열을 나타냄 (루트 노드는 주로 빈 문자열)
  • 문자열의 길이가 n일 때, 문자열의 삽입, 검색, 삭제의 시간복잡도는 O(n)
  • but, 많은 메모리를 요구하고 구현이 복잡하다는 단점이 있음
⭐️ 구현 예시
typedef struct TrieNode {
    struct TrieNode* children[ALPHABET_SIZE];
    int isEndOfWord;    // 단어의 끝 체크
} TrieNode;

5. 스택, 큐, 딕셔너리

스택 (Stack)

|   |
| 3 |
| 2 |
| 1 |
|___|
  • LIFO(Last In First Out) - 가장 나중에 들어온 값이 가장 먼저 나감
  • 배열이나 연결 리스트를 통해 구현 가능
⭐ 구현 예시
typedef struct {
    int arr[MAX_SIZE];
    int top;
} Stack;

큐 (Queue)

(front)   1   2   3   4   5   (rear)
   ↓                            ↑
 Dequeue                     Enqueue
  • FIFO(First In First Out) - 가장 먼저 들어온 값이 가장 먼저 나감
  • 배열이나 연결 리스트를 통해 구현 가능
⭐️ 구현 예시
typedef struct {
    int arr[MAX_SIZE];
    int front, rear;
} Queue;

딕셔너리 (Dictionary)

{ "key1": "value1", "key2": "value2", ... }
  • 키(Key)와 값(Value)의 쌍으로 이루어짐
  • 키에 해당하는 값을 저장하고 읽어오는 것
  • 주로 해시 테이블을 기반으로 구현
⭐️ 구현 예시
typedef struct {
    char key[MAX_SIZE];
    int value;
} KeyValuePair;

typedef struct {
    KeyValuePair pairs[MAX_SIZE];
    int size;
} Dictionary;