하단 광고


Trie 구현 참고 by 설악이






source code - C

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
106
107
108
109
110
111
112
113
114
115
116
// C implementation of search and insert operations 
// on Trie 
#include <stdio.h> 
#include <stdlib.h> 
#include <string.h> 
#include <stdbool.h> 
 
#define ARRAY_SIZE(a) sizeof(a)/sizeof(a[0]) 
 
// Alphabet size (# of symbols) 
#define ALPHABET_SIZE (26
 
// Converts key current character into index 
// use only 'a' through 'z' and lower case 
#define CHAR_TO_INDEX(c) ((int)c - (int)'a'
 
// trie node 
struct TrieNode 
    struct TrieNode *children[ALPHABET_SIZE]; 
 
    // isEndOfWord is true if the node represents 
    // end of a word 
    bool isEndOfWord; 
}; 
 
// Returns new trie node (initialized to NULLs) 
struct TrieNode *getNode(void
    struct TrieNode *pNode = NULL
 
    pNode = (struct TrieNode *)malloc(sizeof(struct TrieNode)); 
 
    if (pNode) 
    { 
        int i; 
 
        pNode->isEndOfWord = false
 
        for (i = 0; i < ALPHABET_SIZE; i++
            pNode->children[i] = NULL
    } 
 
    return pNode; 
 
// If not present, inserts key into trie 
// If the key is prefix of trie node, just marks leaf node 
void insert(struct TrieNode *root, const char *key) 
    int level; 
    int length = strlen(key); 
    int index; 
 
    struct TrieNode *pCrawl = root; 
 
    for (level = 0; level < length; level++
    { 
        index = CHAR_TO_INDEX(key[level]); 
        if (!pCrawl->children[index]) 
            pCrawl->children[index] = getNode(); 
 
        pCrawl = pCrawl->children[index]; 
    } 
 
    // mark last node as leaf 
    pCrawl->isEndOfWord = true
 
// Returns true if key presents in trie, else false 
bool search(struct TrieNode *root, const char *key) 
    int level; 
    int length = strlen(key); 
    int index; 
    struct TrieNode *pCrawl = root; 
 
    for (level = 0; level < length; level++
    { 
        index = CHAR_TO_INDEX(key[level]); 
 
        if (!pCrawl->children[index]) 
            return false
 
        pCrawl = pCrawl->children[index]; 
    } 
 
    return (pCrawl != NULL && pCrawl->isEndOfWord); 
 
// Driver 
int main() 
    // Input keys (use only 'a' through 'z' and lower case) 
    char keys[][8= {"the""a""there""answer""any"
                    "by""bye""their"}; 
 
    char output[][32= {"Not present in trie""Present in trie"}; 
 
 
    struct TrieNode *root = getNode(); 
 
    // Construct trie 
    int i; 
    for (i = 0; i < ARRAY_SIZE(keys); i++
        insert(root, keys[i]); 
 
    // Search for different keys 
    printf("%s --- %s\n""the", output[search(root, "the")] ); 
    printf("%s --- %s\n""these", output[search(root, "these")] ); 
    printf("%s --- %s\n""their", output[search(root, "their")] ); 
    printf("%s --- %s\n""thaw", output[search(root, "thaw")] ); 
 
    return 0
 
cs



그리고 정리가 잘되어 있는 분이 있어서 참고 용으로 적어 둡니다. ^^;





덧글

댓글 입력 영역