Trie 기본 예제
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 117 118 119 120 121 122 123 | #include <stdio.h> const int ALPABATS = 26; int bn; struct Node { int val; Node* prev; Node* next; Node* alloc(int _val, Node* _prev, Node* _next) { val = _val; prev = _prev; next = _next; if (prev) prev->next = this; if (next) next->prev = this; return this; } void del() { if (prev) prev->next = next; if (next) next->prev = prev; prev = next = 0; } }buf[10000], *hash[1000], *hash_tail[1000]; class Trie { private: Trie* child[ALPABATS]; Node* p; int cnt; public: Trie() { for (int i = 0; i < ALPABATS; ++i) { child[i] = NULL; cnt = 0; } } ~Trie() { for (int i = 0; i < ALPABATS; i++) { if (child[i] != NULL) { cnt = 0; delete child[i]; } } } void insert(const char *words) { // index를 구하고 int idx = *words - 'a'; // 현재 index의 포인터가 없으면 new if (child[idx] == NULL) { child[idx] = new Trie(); } // 마지막이면 cnt++ if (*(words + 1) == '\0') { cnt += 1; return; } // 다음 char 처리 child[idx]->insert(words + 1); } int find(const char *words) { int idx = *words - 'a'; if (child[idx] == NULL) { return 0; } if (*(words + 1) == '\0') { return cnt; } return child[idx]->find(words + 1); } void remove(const char *words) { int idx = *words - 'a'; if (child[idx] == NULL) { return; } if (*(words + 1) == '\0') { cnt -= 1; return; } child[idx]->remove(words + 1); } }; int main() { Trie tri; tri.insert("like"); tri.insert("like"); tri.insert("likes"); tri.insert("lik"); int ret = 0; ret = tri.find("like"); printf("find cnt:%d\n", ret); tri.remove("like"); tri.remove("like"); ret = tri.find("like"); printf("find cnt:%d\n", ret); return 0; } | cs |