22.03.18資料構造

データ構造は、コンピュータのメモリをより効率的に管理するために再定義された構造です。

malloc & pointer

int main(void)
{
    int *x;
    int *y;

    x = malloc(sizeof(int));

    *x = 42;
    *y = 13;
}

realloc

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

int main(void)
{
    int *list = malloc(3 * sizeof(int));
    if (list == NULL)
    {
        return 1;
    }

    list[0] = 1;
    list[1] = 2;
    list[2] = 3;

    // tmp 포인터에 메모리를 할당하고 list의 값 복사
    int *tmp = realloc(list, 4 * sizeof(int));
    if (tmp == NULL)
    {
        return 1;
    }

    // list가 tmp와 같은 곳을 가리키도록 지정
    list = tmp;

    // 새로운 list의 네 번째 값 저장
    list[3] = 4;

    // list의 값 확인
    for (int i = 0; i < 4; i++)
    {
        printf("%i\n", list[i]);
    }

    //list 의 메모리 초기화
    free(list);
}

接続リスト

typedef struct node  // 2. 구조체 정의 시 node라는 단어를 설정해주었다.
{
    int number;
    struct node *next;  // 1. node를 내부에서도 사용하기 위해,
}
node;

(*n).number = 2; // n의 메모리의 값의 number 속성에 2를 저장함.
n->number = 2; 로 바꿔서 사용 가능

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

// Represents a node
typedef struct node
{
    int number;
    struct node *next;
}
node;

int main(void)
{
    // List of size 0
    node *list = NULL;

    // Add number to list
    node *n = malloc(sizeof(node));
    if (n == NULL)
    {
        return 1;
    }
    n->number = 1;
    n->next = NULL;
    list = n;  // Pointing at new node (첫 번째 node의 주소)

    // Add number to list
    n = malloc(sizeof(node));
    if (n == NULL)
    {
        return 1;
    }
    n->number = 2;
    n->next = NULL;
    list->next = n;  // list가 첫번째 node를 가리키고 있었으므로, 그 것의 next는 두 번째 node를 가리킨다.

    // Add number to list
    n = malloc(sizeof(node));
    if (n == NULL)
    {
        return 1;
    }
    n->number = 3;
    n->next = NULL;
    list->next->next = n;  // list->next가 두번째 node를 가리키고 있었으므로, 그 것의 next는 세 번째 node를 가리킨다.

    // Print list
    for (node *tmp = list; tmp != NULL; tmp = tmp->next)
    {
        printf("%i\n", tmp->number);  // tmp가 가리키는 number 필드의 숫자를 출력
    }

    // Free list
    while (list != NULL)
    {
        node *tmp = list->next;
        free(list);
        list = tmp;
    }
}

//이진 검색 트리의 노드 구조체
typedef struct node
{
    int number;
    struct node *left;
    struct node *right;
} node;

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

ハッシュ表

trie(略語の取得)

O(1)定数時間、大量メモリが必要
出典:全員向けコンピュータ科学(CS 502019)

Queue

Stack

Dictionary