字典树：
又称单词查找树，Trie树，是一种树形结构，是一种哈希树的变种。典型应用是用于统计，，排序和保存大量的字符串（但不仅限于字符串），它的优点是：利用字符串的公共前缀来节约存储空间，最大限度地减少无谓的字符串比较，查询效率比哈希表高。
#define MAX 26struct Trie {Trie *next[MAX];int v; //根据需要变化}root;next是表示每层有多少种类的数，如果只是小写字母，则26即可，若改为大小写字母，则是52，若再加上数字，则是62了，这里根据题意来确定。v可以表示一个字典树到此有多少相同前缀的数目，这里根据需要应当学会自由变化。
生成字典树：
void createTrie(char *str){int len = strlen(str);Trie *p = new Trie;p=&root;for(int i=0; i<len; ++i){int id = str[i]-'0';if(p->next[id] == NULL){Trie *q=new Trie;q->v = 1; //初始v==1for(int j=0; j<MAX; ++j)q->next[j] = NULL;p->next[id] = q;p = p->next[id];}else{p->next[id]->v++;p = p->next[id];}}// p->v = -1; //若为结尾，则将v改成-1表示(视情况而定)}查找的过程:
int findTrie(char *str){int len = strlen(str);Trie *p = new Trie;p=&root;for(int i=0; i<len; ++i){int id = str[i]-'0'; //根据需要选择是减去'0'还是'a'，或者是'A'p = p->next[id];if(p == NULL) //若为空集，表示不存以此为前缀的串return 0;if(p->v == -1) //字符集中已有串是此串的前缀return -1;}return -1; //此串是字符集中某串的前缀}对于上述动态字典树，有时会超内存，比如HDOJ 1671 Phone List
int dealTrie(Trie* T){int i;if(T==NULL)return 0;for(i=0;i<MAX;i++){if(T->next[i]!=NULL)deal(T->next[i]);}free(T);return 0;}
版权声明：本文为博主原创文章，未经博主允许不得转载。
有事者，事竟成;破釜沉舟，百二秦关终归楚;苦心人，
