首页 > 代码库 > 字典树的实现
字典树的实现
字典树常用于前缀匹配
[syswj@host 0813]$ cat dic_tree.cpp #include <iostream> #include <stdio.h> #define MAX 26 usingnamespace std; typedefstruct TrieNode { intncount; structTrieNode *next[MAX]; }TrieNode; voidinit(TrieNode **pRoot)//初始化 { *pRoot = NULL; } TrieNode* create()//创建新节点 { TrieNode *a =new TrieNode; a->ncount = 0; for(inti = 0; i < MAX; ++i) a->next[i] = NULL; returna; } voidinsert(TrieNode **pRoot, char*s)//插入 { inti, k; TrieNode *p; if(!(p = *pRoot)) { p = *pRoot = create(); } i = 0; while(s[i]) { k = s[i++] -'a'; if(!p->next[k]) { p->next[k] = create(); } p = p->next[k]; } p->ncount++; } int search(TrieNode *pRoot, char *s)//查找 { TrieNode *p; inti, k; if(!(p = pRoot)) { return0; } i = 0; while(s[i]) { k = s[i++] -'a'; if(p->next[k] == NULL) return0; p = p->next[k]; } returnp->ncount; } int main(int argc,const char *argv[]) { TrieNode *p; init(&p); chara[20] = {"abc"} ; insert(&p, a); insert(&p, a); insert(&p,"bcd"); insert(&p,a); cout << search(p,a) << endl; cout << search(p,"bcd") << endl; return0; }
字典树的实现
声明:以上内容来自用户投稿及互联网公开渠道收集整理发布,本网站不拥有所有权,未作人工编辑处理,也不承担相关法律责任,若内容有误或涉及侵权可进行投诉: 投诉/举报 工作人员会在5个工作日内联系你,一经查实,本站将立刻删除涉嫌侵权内容。