字典树(模版+源码)

字典树：

又称单词查找树，Trie树，是一种树形结构，是一种哈希树的变种。典型应用是用于统计，排序和保存大量的字符串（但不仅限于字符串），所以经常被搜索引擎系统用于文本词频统计。它的优点是：利用字符串的公共前缀来减少查询时间，最大限度地减少无谓的字符串比较，查询效率比哈希表高。

字典树与字典很相似,当你要查一个单词是不是在字典树中,首先看单词的第一个字母是不是在字典的第一层,如果不在,说明字典树里没有该单词,如果在就在该字母的孩子节点里找是不是有单词的第二个字母,没有说明没有该单词,有的话用同样的方法继续查找.字典树不仅可以用来储存字母,也可以储存数字等其它数据。

Trie的查找（最主要的操作）：< http://www.2cto.com/kf/ware/vc/" target="_blank" class="keylink">vc3Ryb25nPjxicj4KKDEpIMO/tM6007j5veG147+qyrzSu7TOy9HL96O7PGJyPgooMikgyKG1w9KqsunV0rnYvPy0yrXEtdrSu7j219bEuKOssqK4+b7duMPX1sS40aHU8bbU06a1xNfTyveyoteqtb24w9fTyve8zND4vfjQ0Lzsy/ejuyChoaGhKDMpINTaz+DTprXE19PK98nPo6zIobXD0qqy6dXSudi8/LTKtcS12rb+uPbX1sS4LLKivfjSu7K90aHU8bbU06a1xNfTyve9+NDQvOzL96GjIKGhoaE8YnI+Cig0KSC1/LT6uf2zzKGtoa0goaGhoTxicj4KKDUpINTaxLO49r3hteO0pqOsudi8/LTKtcTL+dPQ19bEuNLRsbvIobP2o6zU8rbByKG4vdTauMO94bXjyc+1xNDFz6KjrLy0zeqzybLp1dKhozwvcD4KPHA+PHByZSBjbGFzcz0="brush:java;">//字典树 #include #include using namespace std; struct Trie{ Trie *next[26]; int v; }; Trie root; void Create(char *t) { int len=strlen(t),i,id,j; Trie *p=&root,*q; for(i=0;i next[id]==NULL) { for(j=0;j<26;j++) q->next[j]=NULL; p->next[id]=q; p=p->next[id]; p->v=1; } else { p->next[id]->v++; p=p->next[id]; } } } int Find(char *str) { Trie *p=&root; int len=strlen(str),i; for(i=0;i next[str[i]-'a']; if(p==NULL) return 0; } return p->v; } int main() { int i; char str[50]; for(i=0;i<26;i++) { root.next[i]=NULL; } while(gets(str)&&str[0]!='\0') Create(str); cout<<"Input End"<