[자료구조]

[Nineclown]

자료구조

리스트

What?

리스트란 배열의 단점(삽입과 삭제)을 보완할 수 있는 선형 데이터 구조입니다. 데이터를 저장하는 하나의 단위를 노드라고 했을 때, 각각의 노드는 다음 위치와 이전 위치를 기억하는 변수와 데이터를 저장할 변수를 갖고 있습니다.

Why?

삽입과 삭제가 배열에 비해 상대적으로 쉬운 이유는 메모리에 각각으로 할당될 수 있기 때문입니다. 연속되어 저장되어 있지 않기 때문입니다. 배열 int Array[10]을 선언하면 메모리에 공간이 할당되고 그 이상 데이터를 삽입할 수 없으며, 데이터를 삭제하더라도 메모리에 공간이 사라지지 않습니다. realloc, malloc을 통해 조정할 수 있지만, 복잡하고 어렵습니다.

리스트는 각각의 노드들은 자신의 메모리 공간을 할당 받고, 다음 위치와 이전 위치의 주소를 갖고 있기 때문에 쉽게 접근가능하며, 삭제와 삽입이 용이합니다.

How?

리스트는 Abstract Data Type(ADT) 중 하나입니다. ADT는 데이터 형과 이를 다루기 위한 API의 집합입니다. 따라서 리스트는 노드라는 데이터 형과 이를 다루기 위한 다양한 함수들이 존재합니다.

add(int index, void data)

void addNode(int id, int data) {
    //newNode
    list[id].prev = &head;
    list[id].next = head.next;

    //head.next
    head.next->prev = &list[id];

    //head
    head.next = &list[id];

    //data
    list[id].data = data;
}

void insNode(int targ_id, int id, int data) {
    Node *newNode_prev = list[targ_id].prev;
    Node *newNode_next = &list[targ_id];

    //newNode
    list[id].prev = newNode_prev;
    list[id].next = newNode_next;
    list[id].data = data;

    //target_prev
    newNode_prev->next = &list[id];

    //target
    newNode_next->prev = &list[id];
}

remove(int index)

void delNode(int id) {
    Node *targ_prev = list[id].prev;
    Node *targ_next = list[id].next;

    targ_prev->next = targ_next;
    targ_next->prev = targ_prev;
}

change(int index1, int index2)

• 고려할점 1 교환할 노드가 연속적인 경우와 그렇지 않은 경우로 나눌 수 있습니다. [Head] == [A] == [B] == [C] == [D] == [E] == [Tail]

• 고려할점 2 연속적인 경우, index의 순서가 결과에 영향을 미칠 수 있을 것 같습니다. 임시용 변수(A, B, C, 등등)는 Index의 순서에 맞춰 설정이 되기 때문입니다. 따라서 두가지 경우로 분기하여 처리할 수도 있고, 입력되는 Index의 순서를 다시 바꿔서 처리하는 방식도 생각해볼 수 있습니다.

  //노드가 연속되어 있는 경우, 역방향
  if (A == T2) {
      change(tg2, tg1);
      return;
  }
  
  //순방향
  else if (B == T2) {
      //T1
      T1->prev = B;
      T1->next = D;
  
      //T2
      T2->prev = A;
      T2->next = C;
  
      //A & D
      A->next = B;
      D->prev = C;
  
      //B & C
      //따로 설정할 게 없다. C가 T1이고 B가 T2이기 때문에 이미 위에서 설정이 끝났다.
  }

• 고려할점 3 비연속적인 경우, A, C를 교환할때와 A, D를 교환할 때도 나눌 수 있을 것 같습니다. A, C의 경우, B는 A의 다음 노드이자 C의 이전 노드입니다. A, D의 경우, B와 C는 이미 연결이 되어있기 때문에 각각의 앞, 뒤 노드는 수정할 필요가 없습니다.

else 
    //Before:   A == T1 == B == C == T2 == D
    //After:    A == T2 == B == C == T1 == D
    //T1
    T1->prev = C; T1->next = D;
    //T2
    T2->prev = A; T2->next = B;
    //A & D
    A->next = T2; D->prev = T1;

    //B & C
    if (B == C) {
        // (둘이 같은 곳의 주소를 갖고 있기 때문에 아무나 하나 골라서 설정해주면 댄다)
        B->prev = T2;
        C->next = T1;
    }
    else {
        B->prev = T2;
        C->next = T1; //결국 분기를 하지 않아도 된다.
    }
}

코드를 작성하고 보니, 고려할점 3은 굳이 생각하지 않아도 해결된다는 것을 알 수 있었습니다.

전체 소스 코드

#ifndef _CRT_SECURE_NO_WARNINGS
#define _CRT_SECURE_NO_WARNINGS
#endif

#include <stdio.h>

typedef struct _node {
    int data;
    _node *next;
    _node *prev;
} Node;

Node head, tail;
Node list[100];

void init() {
    head.prev = 0;
    head.next = &tail;
    head.next->prev = &head;
    head.next->next = 0;

    head.data = 999;
    tail.data = 999;
}

void addNode(int id, int data) {
    //newNode
    list[id].prev = &head;
    list[id].next = head.next;

    //head.next
    head.next->prev = &list[id];

    //head
    head.next = &list[id];

    //data
    list[id].data = data;

}

void insNode(int targ_id, int id, int data) {
    Node *newNode_prev = list[targ_id].prev;
    Node *newNode_next = &list[targ_id];

    //newNode
    list[id].prev = newNode_prev;
    list[id].next = newNode_next;
    list[id].data = data;

    //target_prev
    newNode_prev->next = &list[id];

    //target
    newNode_next->prev = &list[id];
}

void delNode(int id) {
    Node *targ_prev = list[id].prev;
    Node *targ_next = list[id].next;

    targ_prev->next = targ_next;
    targ_next->prev = targ_prev;
}

void change(int tg1, int tg2) {
    Node *T1 = &list[tg1];  Node *T2 = &list[tg2];
    Node *A = T1->prev;     Node *B = T1->next;
    Node *C = T2->prev;     Node *D = T2->next;

    //노드가 연속되어 있는 경우, 역방향
    if (A == T2) {
        change(tg2, tg1);
        return;
    }

    //순방향
    else if (B == T2) {
        //T1
        T1->prev = B;
        T1->next = D;

        //T2
        T2->prev = A;
        T2->next = C;

        //A & D
        A->next = B;
        D->prev = C;

        //B & C
        //따로 설정할 게 없다. C가 T1이고 B가 T2이기 때문에 이미 위에서 설정이 끝났다.
    }
    else {
        //Before:   A == T1 == B == C == T2 == D
        //After:    A == T2 == B == C == T1 == D

        //T1
        T1->prev = C; T1->next = D;

        //T2
        T2->prev = A; T2->next = B;

        //A & D
        A->next = T2; D->prev = T1;

        //B & C
        B->prev = T2; C->next = T1;
    }

}

void printList() {
    Node temp = head;

    //for(temp = head; temp.next != 0; temp = *temp.next)
    while (temp.next != 0) {
        printf("[ %d ]===", temp.data);
        temp = *temp.next;
    }

    printf("[ %d ]\n", temp.data);

}

int main() {
    init();

    addNode(0, 0);
    insNode(0, 1, 10);
    addNode(2, 20);
    addNode(3, 30);
    printf("%10s", "리스트 출력");
    printList();

    printf("%10s", "delNode(3)");
    delNode(3);
    printList();

    addNode(4, 40);
    addNode(5, 50);
    printf("%10s", "리스트 출력");
    printList();

    printf("%10s", "change(2, 5)");
    change(2, 5);
    printList();

    printf("%10s", "change(2, 4)");
    change(2, 4);
    printList();

    printf("%10s", "change(4, 2)");
    change(4, 2);
    printList();

    printf("%10s", "change(4, 2)");
    change(4, 2);
    printList();

    printf("%10s", "change(4, 2)");
    change(4, 2);
    printList();

    return 0;
}

[Nineclown]

Hash

데이터의 효율적 관리를 목적으로 임의의 길이의 데이터(Key)를 고정된 길이의 데이터(Hash value)로 매핑하는 함수. 매핑하는 과정 자체를 해싱(Hashing)이라고 합니다.

적은 리소스로 많은 데이터를 효율적으로 관리하기 위해 사용합니다.

색인(Index)에 해시값을 사용하여 모든 데이터를 탐색하지 않고 검색 / 삽입 / 삭제를 빠르게 사용할 수 있습니다.

해시충돌

해시테이블

해시함수를 사용해 키를 해시값으로 매핑하고, 해시값을 색인(Index) 혹은 주소 삼아 데이터의 값(value)을 키와 함께 저장하는 자료구조. 이때 데이터가 저장되는 곳을 버킷(Bucket) 또는 슬롯(Slot)이라 합니다.

Chaining

해시충돌 문제를 해

[Nineclown]

https://ratsgo.github.io/data%20structure&algorithm/2017/10/25/hash/

[Nineclown]

Trie

: 문자열을 저장하기 위해 만든? 트리 구조의 자료 구조.

자료형(structure)

typedef struct _node {
    _node *child[26];
    int word;
} Node;

기능(function)

void insert(char *data);
void showAll(Node *now, char *str, int depth);
void find(Node *root, char *str);

insert

: 데이터(data)가 들어오면 Trie에 삽입하는 기능. 루트부터 시작해서 데이터의 길이만큼, 반복해서 트리를 들어간다. 현재 위치를 기억하는 cursor를 둔다. ex) apple. 1 - a). 먼저 커서를 루트로 옮겨서 자식 노드가 a인 노드를 찾는다. 없다면 a를 루트의 자식으로 추가하고, 커서를 a로 옮긴다. 1 - b). 만약 자식이 있다면, 커서를 a로 옮긴다.

2. 1번을 입력받은 데이터의 길이만큼 반복한다.

   3. 추가가 끝나면 마지막 문자의 word 값을 true로 바꾼다. (= 추가된 문자를 표시하기 위해서)

      
      void insert(char *data) {
      int len = mstrlen(data);
      Node *now = &Trie[0];

   for (int i = 0; i < len; i++) { if (now->child[data[i] - 'a'] == 0) now->child[data[i] - 'a'] = &Trie[cnt++]; now = now->child[data[i] - 'a']; } now->word = 1; }

   
   ### showAll
   루트부터 탐색하면서 문자 표시를 해둔 트리까지를 이어서 출력하는 기능.

void showAll(Node *now, char *str, int depth) {
    if (now->word)
        printf("%s\n", str);

    for (int i = 0; i < 26; i++) {
        //자식이 존재할 경우,
        if (now->child[i]) {
            str[depth] = i + 'a';
            str[depth + 1] = '\0';
            showAll(now->child[i], str, depth + 1);
        }
    }
}

find