首页 > 代码库 > 字典树

字典树

 

字典树 (解析加模版)

分类: ACM 204人阅读 评论(0) 收藏 举报

          字典树:又叫trie树,单词查找树。是一种树形结构,典型的用于统计。经常用于统计一片文章当中出现确定的单词的次数,它的优点就在于:省略了相同前缀的比较。以下图为例:用单词carbohy,carhure,english,englnee来构造的trie树。 


                                     


         当你用trie树来查找一个单词的时候,就像查字典是一样的,先查第一个单词,然后查第二个,在树中我们用深度遍历就可以实现。当然你不一定存储字母也可以存储数字什么的,根据具体情况来选择。

trie树结构定义:

[cpp] view plaincopy
  1. typedef struct node  
  2. {  
  3.        int cnt;               //用来经过此结点以上前缀的单词数  
  4.        node* next[26];        //这里只包含小写字母,故是26个  
  5. } Trie;  
next数组视情况而定,如果既有小写又有大写就是52,如果还有数字则更多。

接着就是构造trie树了,根据提供的单词构造trie树

过程如下:(跟树的构造类似)

[cpp] view plaincopy
  1. void Creat_Trie(char*str){  
  2.      int len,i,j;  
  3.      len=strlen(str);  
  4.      Trie *p=&root,*q;  
  5.      for( i=0; i<len; i++){  
  6.           int id=str[i]-‘a‘;            //在next数组中找到对应位  
  7.           if( p->next[id]==NULL){  
  8.               q=new Trie;            //如果该字符不存在,动态分配节点  
  9.               q->cnt=1;  
  10.               for( j=0; j<26; j++)  
  11.                    q->next[j]=NULL;  
  12.               p->next[id]=q;  
  13.               p=p->next[id];  
  14.           }  
  15.           else{  
  16.                p->next[id]->cnt++;  
  17.                p=p->next[id];  
  18.           }  
  19.      }  
  20. }  

构造trie树之后查找,这也是trie树重要的功能。

[cpp] view plaincopy
  1. int Find_Trie(char*str){   
  2.    int len,i,j,id;  
  3.    len=strlen(str);  
  4.    Trie*p=&root;  
  5.    for( i=0; i<len; i++){  
  6.         id=str[i]-‘a‘;  
  7.         p=p->next[id];  
  8.         if( p==NULL)  
  9.             return 0;  
  10.    }  
  11.    return p->cnt;  

题目:入门--统计难题hdu