연결 리스트 ( Linked List ) 활용

▶연결 리스트 ( Linked List) 활용

 노드를 이용하여 문자열에 대응하는 값을 얻을 수 있다.

c++에서는 map<string, int>에서 map["문자열"]=값과 같은 형태를 예로 들 수 있다.

단, 중복된 문자열에 대한 값은 생각하지 않는다.

 

▶소스코드

#include <stdlib.h>

typedef struct _node {
    int idx;
    struct _node *alpha[26];
} node;

node *create_node() {//노드 생성
    node *np = (node *)malloc(sizeof(node));
    for (int i = 0; i < 26; i++) np->alpha[i] = NULL;
    return np;
}

void delete_node(node *np) {//노드 삭제
    for (int i = 0; i < 26; i++) {
        if (np->alpha[i]) delete_node(np->alpha[i]);
    }
    free(np);
}

void add_node(node *root, char *str, int idx) {//노드 추가
    node *np = root;
    while (*str) {
        int i = *str++ - 'a';
        if (!np->alpha[i]) np->alpha[i] = create_node();
        np = np->alpha[i];
    }
    np->idx = idx;
}

int find_idx(node *root, char *str) {//문자열을 이용한 검색
    node *np = root;
    while (*str) {
        int i = *str++ - 'a';
        np = np->alpha[i];
    }
    return np->idx;
}

 

▶해석

문자열 "acd"에 대응하는 idx=10을 node에 추가한다고 가정하면,

add_node 함수에서

int i = *str++ - 'a'; 를 통해 i값을 얻어 np->alpha[i] = create_node(); 로 노드를 생성한다.

첫 번째 값으로는 i='a' - 'a'; 가 되어 i=0 이 된다.

노드 생성 후 np = np->alpha[i]; 로 인해 다음 노드를 가리키고,

i='c'-'a'; 가 되어 i=2가 되고 노드 생성 후 다음 노드를 가리키고,

i='d'-'a'; 가 되어 i=3으로 노드 생성 후 *str='\0'가 되어 반복문이 종료된다.

마지막으로 가리키는 np->idx에 저장하고자 하는 값을 대입한다.

 

find_idx 함수로 문자열 str="acd"를 검색한다면

add_node 함수와 마찬가지로 str 문자 하나씩 'a'를 빼서 i값을 구한 후

연결된 노드를 따라가면 마지막 노드에 idx 값이 저장되어 있어 반환하여 idx를 찾을 수 있다.