trie字典树实现 一时失言乱红尘 2022-09-27 15:22 144阅读 0赞 实现了一个简单的字典树. 假设所有的字符只有26个小写字母,并且除了节点出现的次数之外还增加了类似map功能的索引。 假如不只有26个字母,需要相应的做一些修改。 #include <stdio.h> #include <string.h> #include <stdlib.h> #define ALPHABET_SIZE 26 int num = 0; typedef struct trie_node { int count; // 记录该节点代表的单词的个数 int index; //该节点的索引 trie_node *children[ALPHABET_SIZE]; // 各个子节点 }*trie; trie_node* create_trie_node() { trie_node* pNode = (trie_node*) malloc(sizeof(trie_node)); //trie_node* pNode = new trie_node(); pNode->count = 0; for (int i = 0; i < ALPHABET_SIZE; ++i) { pNode->children[i] = NULL; } return pNode; } void trie_insert(trie root, char* key) { trie_node* node = root; char* p = key; while (*p) { if (node->children[*p-'a'] == NULL) { node->children[*p-'a'] = create_trie_node(); } node = node->children[*p-'a']; ++p; } node->count += 1; node->index = num++; } /** * 查询:不存在返回-1,存在返回索引index */ int trie_search(trie root, char* key) { trie_node* node = root; char* p = key; while (*p && node!=NULL) { node = node->children[*p-'a']; ++p; } if(node == NULL) { return -1; } else { return node->index; } } int main() { trie root = create_trie_node(); return 0; }
还没有评论,来说两句吧...