当前位置： 代码迷 >> 综合 >> Tire
  详细解决方案

Tire

热度：30   发布时间：2024-01-11 02:00:20.0

字典树基础讲解 

标签： acm算法数据结构c语言
2014-10-23 10:36  315人阅读  评论(0)  收藏  举报
本文章已收录于： 
  算法与数据结构知识库
  分类：
 
   

/*

再次声明本文为转载

原作者地址

http://blog.csdn.net/u013548531/article/details/38896059

*/

题目链接：http://acm.hdu.edu.cn/showproblem.php?pid=1251


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

说到底，其实不难算是算法应当归为数据结构，一种特殊的树。

字典树有三个特点，非常重要，也是构建字典树的三个标准原则吧。

1.根节点为空

2.树的每一层的元素独一无二不可重复

3.从根节点到某一节点的路径就是该节点对应的字符串。

比如说这个样例

banana

band

bee

absolute

acm

这五个单词组成的字典树应该如下图所示：


（中间有些单词很长省略了..)这个图应该很直观了。

字典树的操作（看资料一般定义了四个操作。创建 添加 删除 查找。由于删除操作不常用于是在这就不说了）：

1.创建

创建应该分成两个部分。定义结点和建立树。

定义结点的代码如下：

[cpp]  view plain copy
print ?
  1. struct Trie  
  2. {  
  3.     int num;  
  4.     struct Trie  *next[maxn];  
  5. };  

1.num：到这个节点，前缀相同的数目，这个地方看起来可能并不理解，那么继续往下看会明白。（PS：这个num随题目变化而不同）

2.next是一个指针数组，其中maxn是每一层中最多的元素数。比如说这个题目当中，每一层最多只有26个小写字母，maxn = 26.

***建立字典树：

这个是最重要的部分。

建立字典树首先要创建一个Trie类型的指针root，并且将其初始化（next[i] = NULL）。

[cpp]  view plain copy
print ?
  1. struct Trie *root = (struct Trie*)malloc(sizeof(struct Trie));    
  2.     
  3. void initialize()    
  4. {    
  5.     /*别忘了给root分配内存*/     
  6.     root->num = 0;    
  7.     for(int i = 0 ; i < maxn ; ++i)    
  8.         root->next[i] = NULL;    
  9. }    

反应到图上就如下图所示。


（PS：用c语言的话千万别忘了用malloc函数）

建立了树根之后，开始完善这颗树，注意一定要遵守那三个原则。

先给出代码，然后以acm这个单词为例从图上体现一下。

[cpp]  view plain copy
print ?
  1. void insert(char *str)//插入字典树   
  2. {  
  3.     int len = strlen(str);  
  4.     struct Trie *p = root;//先由p指向字典树  
  5.     //把字符加入字典树  
  6.     for(int i = 0 ; i < len ; ++i)  
  7.     {  
  8.         int pos = str[i] - 'a';//转化为坐标  
  9.         if(p->next[pos] == NULL)//如果指向的结点为空，新建结点   
  10.         {  
  11.             //new一个新结点  
  12.             struct Trie *temp = (struct Trie*)malloc(sizeof(struct Trie));  
  13.             temp->num = 1;  
  14.             for(int j = 0 ; j < maxn ; ++j)  
  15.                 temp->next[j] = NULL;  
  16.             p->next[pos] = temp;   
  17.             p = p->next[pos];  
  18.         }   
  19.         else  
  20.         {  
  21.             p = p->next[pos];//移动到一下层   
  22.             p->num++;  
  23.         }  
  24.     }   
  25. }  

我们把执行过程画出来。

（假设str == acm）

在循环开始之前，我们得到的是这样的图


for(int i = 0 ; i < len ; ++i)

循环开始，第一个字符是a

pos = 0

显然p->next[pos] = NULL,则建立一个新的结点，然后p->next[pos]指向这个结点，如下图:


然后再把temp赋值给p使得temp称为新的p

（注意temp的num值赋值为1了，表示到现在为止有一个单词的开头字母是a，如果你在加入添加单词absolute，那么是指向else里边的代码，此时a这一点的num值为2，表示到现在为止有两个单词的开头字是a。这句话对于理解num的意义很有必要，后续的查找代码也更容易看懂）


然后不断的这样构造即可。

2.查找

同样，先贴代码然后解释。

[cpp]  view plain copy
print ?
  1. int find(char *str)  
  2. {  
  3.     struct Trie *p = root;  
  4.     int len = strlen(str);  
  5.     for(int i = 0 ; i < len ; ++i)  
  6.     {  
  7.         int pos = str[i] - 'a';  
  8.         p = p->next[pos];  
  9.         if(p == NULL)  
  10.             return 0;  
  11.     }  
  12.     return p->num;  
  13. }  

在看懂了上边的图和理解了num的意思之后，这段代码理解起来应该就很容易了。

假设字典树已经建立完毕，对于ac这组数据，我们寻找到底有几个单词的前缀是ac。

str == ac

循环:

i = 0时 pos = a - 'a' = 0;

p - > next[0]不是空，继续到下一层。

i = 1时 pos = c - 'a' = 2;

p - > next[2]不是空，继续下一层。

i = 2 循环结束。

返回当前结点的num(也就是到该结点的字符串刚好为ac的单词的个数）

（如果想更加详细的了解的话..多画图，多找几个例子，顺着代码走一遍，就明白了了）

附AC代码，98MS

[cpp]  view plain copy
print ?
  1. </pre><pre name="code" class="cpp"><span style="font-family:Microsoft YaHei;font-size:14px;">#include <stdio.h>  
  2. #include <string.h>  
  3. #include <malloc.h>  
  4. #define maxn 26  
  5. struct Trie  
  6. {  
  7.     int num;//到某一层字符数目   
  8.     struct Trie  *next[maxn];//每层最多多少种字符   
  9. };  
  10.   
  11. struct Trie *root = (struct Trie*)malloc(sizeof(struct Trie));  
  12.   
  13. void initialize()  
  14. {  
  15.     /*别忘了给root分配内存*/   
  16.     root->num = 0;  
  17.     for(int i = 0 ; i < maxn ; ++i)  
  18.         root->next[i] = NULL;  
  19. }  
  20. void insert(char *str)//插入字典树   
  21. {  
  22.     int len = strlen(str);  
  23.     struct Trie *p = root;//先由p指向字典树的根，从而找到这棵字典树   
  24.     //把字符加入字典树  
  25.     for(int i = 0 ; i < len ; ++i)  
  26.     {  
  27.         int pos = str[i] - 'a';//转化为坐标  
  28.         if(p->next[pos] == NULL)//如果指向的结点为空，新建结点   
  29.         {  
  30.             //new一个新结点  
  31.             struct Trie *temp = (struct Trie*)malloc(sizeof(struct Trie));  
  32.             temp->num = 1;//这个地方是1说明添加了一个字符   
  33.             for(int j = 0 ; j < maxn ; ++j)  
  34.                 temp->next[j] = NULL;  
  35.             p->next[pos] = temp;   
  36.             p = p->next[pos];  
  37.         }   
  38.         else  
  39.         {  
  40.             p = p->next[pos];//移动到一下层   
  41.             p->num++;  
  42.         }  
  43.     }   
  44. }  
  45. int find(char *str)  
  46. {  
  47.     struct Trie *p = root;  
  48.     int len = strlen(str);  
  49.     for(int i = 0 ; i < len ; ++i)  
  50.     {  
  51.         int pos = str[i] - 'a';  
  52.         p = p->next[pos];  
  53.         if(p == NULL)  
  54.             return 0;  
  55.     }  
  56.     return p->num;  
  57. }  
  58.   
  59. int main()  
  60. {  
  61.     char s[15];  
  62.   
  63.     initialize();//初始化字典树，让根节点为空   
  64.     while(gets(s) && strlen(s))  
  65.         insert(s);//每读取一条记录就加入字典树   
  66.     while(gets(s))  
  67.     {  
  68.         int ans = find(s);  
  69.         printf("%d\n",ans);  
  70.     }  
  71.     return 0;  
  72. }  
  73. </span>  
  相关解决方案

代码迷 - 您身边的软件异常，代码异常，编程异常助手（发现，解决，分享）
Copyright © 2009-2013 DAIMAMI.COM. All rights reserved.