首页 > 代码库 > 字典树模板
字典树模板
定义一颗字典树:
struct Trie { int n; // n可以存储相关有用信息,视情况而定 Trie *next[maxn]; //maxn视字典树中有多少种元素而定 }
Trie *root; void init() { root = (Trie *)malloc(sizeof(Trie)); root -> n = 0; for(int i = 0;i < maxn; i++) root -> next[i] = NULL; }
建立字典树:
void insert(char *word) { Trie *temp = root; for(int i = 0; i < strlen(word); i++) { int pos = word[i] - 'a'; if(temp -> next[pos] == NULL) { Trie *cur = (Trie *)malloc(sizeof(Trie)); for(int j = 0;i < maxn; i++) { cur -> next[i] = NULL; cur -> n = 0; } temp -> next[pos] = cur; } temp = temp ->next[pos]; } temp -> n = 1; // 单词结尾处标记1 }
查找:
bool search(char *word) { Trie *temp = root; for(int i = 0; i < strlen(word); i++) { temp = temp -> next[word[i] - 'a']; if(temp == NULL) return false; //没有以次为前缀的单词 if(temp -> n = 1) return true; //该单词是别的单词的前缀 } return true; //别的单词是该单词的前缀 }释放内存
void del(Trie *cur) //采用递归来释放 { for(int i = 0;i < maxn; i++) { if(cur -> next[i] != NULL) del(cur -> next[i]); } free(cur); }
声明:以上内容来自用户投稿及互联网公开渠道收集整理发布,本网站不拥有所有权,未作人工编辑处理,也不承担相关法律责任,若内容有误或涉及侵权可进行投诉: 投诉/举报 工作人员会在5个工作日内联系你,一经查实,本站将立刻删除涉嫌侵权内容。