字典树(讲解+模板)
又称单词查找树,Trie树,是一种树形结构，是一种哈希树的变种。典型应用是用于统计，排序和保存大量的字符串（但不仅限于字符串），所以经常被搜索引擎系统用于文本词频统计。它的优点是：利用字符串的公共前缀来节约存储空间，最大限度地减少无谓的字符串比较，，查询效率比哈希表高。
字典树跟字典很相似,当我们要查询一个单词是不是在字典中时,我们首先查询单词的第一个字母,之后确定了一个字母后,查找下一个字母,反复这种操作,直到找到单词,但是这种效率很低,在庞大的单词系统面前,则显得心塞了.所以就有了字典树这种快速查找单词的数据结构的诞生.字典树不仅可以用来储存字母,也可以储存数字等其它数据。
Trie数据结构的定义:
struct Trie {int index; <span style="color:#008000;">//</span><span style="color:#008000;">根据需要变化</span>Trie *next[MAX]; //<span class="com">表示每一节点包含有多少种类的数,根据需求而定.</span><span class="pln"></span>Trie() { 初始化index = 1;memset(next,0,sizeof(next));}};Trie数据结构的插入操作:
void Trie_insert(Trie *tr,int len) { //根据需求变化if(s[len]) {int u = s[len] – 'a';if(tr->next[u] == 0) tr->next[u] = new Trie;else tr->next[u]->index++;Trie_insert(tr->next[u],len + 1);}}Trie数据结构的查找操作(dfs)
int dfs(Trie *tr,int len) {int u = s[len] – 'a';if(tr->next[u]){if(!s[len + 1]) return tr->next[u]->index;return dfs(tr->next[u],len + 1);}return 0;}
HDOJ 1671 Phone List
?pid=1671
HDOJ 1251 统计难题：
?pid=1251
我爱你….为了你的幸福，我愿意放弃一切—包括你。
