首页 > 其他 > 详细

字典树（转）

时间：2015-10-25 20:38:36      阅读：269      评论：0      收藏：0      [点我收藏+]

字典树：很强大的数据结构，实现多个字符串的查找、对其个数的纪录以及对其子串的查询。

 连接：http://blog.csdn.net/chenzhenyu123456/article/details/46490539

这里讲下建树过程：

 

 准备：MAX 记录总节点数目

 

[cpp] view plaincopy
  1. char str[1010][50];//输入的字符串集   
  2. int ch[MAX][30];//字典树的实现   
  3. int word[MAX];//记录当前节点下有多少个单词   
  4. int val[MAX];//标记单词节点   
  5. int sz;//节点数   

 

初始化：

[cpp] view plaincopy
  1. void init()  
  2. {  
  3.     sz = 1;  
  4.     memset(ch[0], 0, sizeof(ch[0]));  
  5.     memset(word, 0, sizeof(word));  
  6. }   


返回字符的ascll码值：

[cpp] view plaincopy
  1. int idx(char x)  
  2. {  
  3.     return x - ‘a‘;  
  4. }  


插入字符串：


[cpp] view plaincopy
  1. void insert(char *s)  
  2. {  
  3.     int i, j, len = strlen(s);  
  4.     int u = 0;//根节点开始   
  5.     for(i = 0; i < len; i++)  
  6.     {  
  7.         int c = idx(s[i]);  
  8.         if(!ch[u][c])//当前节点不存在   
  9.         {  
  10.             memset(ch[sz], 0, sizeof(ch[sz]));//初始化新节点   
  11.             val[sz] = 0;  
  12.             ch[u][c] = sz++; //节点数增一   
  13.         }  
  14.         u = ch[u][c];  
  15.         word[u]++;//单词数加一   
  16.     }  
  17.     val[u] = 1;//标记单词节点   
  18. }  

 

查找以字符串s为前缀的字符串 在字符串集中有多少个

[cpp] view plaincopy
  1. int findnum(char *s)//查询以该s为前缀的字符串有多少个    
  2. {    
  3.     int i, j, l = strlen(s);    
  4.     int u = 0;    
  5.     for(i = 0; i < l; i++)    
  6.     {    
  7.         int c = idx(s[i]);    
  8.         if(!ch[u][c]) return 0;//不存在     
  9.         u = ch[u][c];    
  10.     }    
  11.     return word[u];    
  12. }    



查找并输出字符串在串集里面唯一确定的最短前缀 ：

[cpp] view plaincopy
  1. void findprefix(char *s)  
  2. {  
  3.     int i, j, len = strlen(s);  
  4.     int u = 0;  
  5.     for(i = 0; i < len; i++)  
  6.     {  
  7.         int c = idx(s[i]);  
  8.         u = ch[u][c];//继续查找   
  9.         printf("%c", s[i]);  
  10.         if(word[u] == 1)//节点下只有一个单词   
  11.         return ;  
  12.     }   
  13. }   



判断该字符串是不是串集里某个字符串前缀 ：

[cpp] view plaincopy
  1. bool judgeprefix(char *s)  
  2. {  
  3.     int i, j, len = strlen(s);  
  4.     int u = 0;  
  5.     for(i = 0; i < len; i++)  
  6.     {  
  7.         int c = idx(s[i]);  
  8.         u = ch[u][c];//继续查找   
  9.         if(word[u] == 1)//不是任何字符串的前缀   
  10.         return true;  
  11.     }   
  12.     return false;//是前缀   
  13. }   


判断字符串是否由串集里的两个字符串构成： 假设该字符串分s1,s2两部分，这里只实现s1的查找

[cpp] view plaincopy
  1. bool finds(char *s)  
  2. {  
  3.     int i, j, len = strlen(s);  
  4.     int u = 0;  
  5.     for(i = 0; i < len; i++)  
  6.     {  
  7.         int c = idx(s[i]);  
  8.         if(!ch[u][c])//不存在节点    
  9.         return false;  
  10.         u = ch[u][c];  
  11.     }  
  12.     return val[u];//最后一个是不是单词节点   
  13. }  


大模板：


[cpp] view plaincopy
  1. #include <cstdio>  
  2. #include <cstring>  
  3. #define MAX 50000+10  
  4. using namespace std;  
  5. char str[1010][50];//输入的字符串集   
  6. int ch[MAX][30];//字典树的实现   
  7. int word[MAX];//记录当前节点下有多少个单词   
  8. int val[MAX];//标记单词节点   
  9. int sz;//节点数   
  10. int idx(char x)  
  11. {  
  12.     return x - ‘a‘;  
  13. }  
  14. void init()  
  15. {  
  16.     sz = 1;  
  17.     memset(ch[0], 0, sizeof(ch[0]));  
  18.     memset(word, 0, sizeof(word));  
  19. }   
  20. void insert(char *s)  
  21. {  
  22.     int i, j, len = strlen(s);  
  23.     int u = 0;//根节点开始   
  24.     for(i = 0; i < len; i++)  
  25.     {  
  26.         int c = idx(s[i]);  
  27.         if(!ch[u][c])//当前节点不存在   
  28.         {  
  29.             memset(ch[sz], 0, sizeof(ch[sz]));//初始化新节点   
  30.             val[sz] = 0;  
  31.             ch[u][c] = sz++; //节点数增一   
  32.         }  
  33.         u = ch[u][c];  
  34.         word[u]++;//单词数加一   
  35.     }  
  36.     val[u] = 1;//标记单词节点   
  37. }  
  38. //查找以字符串s为前缀的字符串 在字符串集中有多少个  
  39. int findnum(char *s)//查询以该s为前缀的字符串有多少个    
  40. {    
  41.     int i, j, l = strlen(s);    
  42.     int u = 0;    
  43.     for(i = 0; i < l; i++)    
  44.     {    
  45.         int c = idx(s[i]);    
  46.         if(!ch[u][c]) return 0;//不存在     
  47.         u = ch[u][c];    
  48.     }    
  49.     return word[u];    
  50. }    
  51. //查找并输出字符串在串集里面唯一确定的最短前缀   
  52. void findprefix(char *s)  
  53. {  
  54.     int i, j, len = strlen(s);  
  55.     int u = 0;  
  56.     for(i = 0; i < len; i++)  
  57.     {  
  58.         int c = idx(s[i]);  
  59.         u = ch[u][c];//继续查找   
  60.         printf("%c", s[i]);  
  61.         if(word[u] == 1)//节点下只有一个单词   
  62.         return ;  
  63.     }   
  64. }   
  65. //判断该字符串是不是串集里某个字符串前缀    
  66. bool judgeprefix(char *s)  
  67. {  
  68.     int i, j, len = strlen(s);  
  69.     int u = 0;  
  70.     for(i = 0; i < len; i++)  
  71.     {  
  72.         int c = idx(s[i]);  
  73.         u = ch[u][c];//继续查找   
  74.         if(word[u] == 1)//不是任何字符串的前缀   
  75.         return true;  
  76.     }   
  77.     return false;//是前缀   
  78. }   
  79. //判断字符串是否由串集里的两个字符串构成:假设该字符串分两部分,这里只实现一部分的查找  
  80. bool finds(char *s)  
  81. {  
  82.     int i, j, len = strlen(s);  
  83.     int u = 0;  
  84.     for(i = 0; i < len; i++)  
  85.     {  
  86.         int c = idx(s[i]);  
  87.         if(!ch[u][c])//不存在节点    
  88.         return false;  
  89.         u = ch[u][c];  
  90.     }  
  91.     return val[u];//最后一个是不是单词节点   
  92. }  


字典树（转）

原文：http://www.cnblogs.com/handsomecui/p/4909330.html
踩
(0)
赞
(0)
   
举报
评论 一句话评论（0）
分享档案
更多>
2021年09月23日 (328)
2021年09月24日 (313)
2021年09月17日 (191)
2021年09月15日 (369)
2021年09月16日 (411)
2021年09月13日 (439)
2021年09月11日 (398)
2021年09月12日 (393)
2021年09月10日 (160)
2021年09月08日 (222)
最新文章
更多>
教程昨日排行
更多>
友情链接
汇智网   PHP教程   插件网  
关于我们 - 联系我们 - 留言反馈 - 联系我们:wmxa8@hotmail.com
© 2014 bubuko.com 版权所有
打开技术之扣，分享程序人生！