字典树皇星客栈

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

字典树与字典很相似,当你要查一个单词是不是在字典树中,首先看单词的第一个字母是不是在字典的第一层,如果不在,说明字典树里没有该单词,如果在就在该字母的孩子节点里找是不是有单词的第二个字母,没有说明没有该单词,有的话用同样的方法继续查找.字典树不仅可以用来储存字母,也可以储存数字等其它数据。

http://www.cnblogs.com/tanky_woo/archive/2010/09/24/1833717.html 这里讲的很清楚

然后我做了几道杭电的题目：

http://acm.hdu.edu.cn/showproblem.php?pid=1251

统计难题

View Code

 1 #include<iostream>
 2 using namespace std;
 3 
 4 typedef struct Trie{
 5         int v;
 6         Trie *next[26];
 7 }Trie;
 8 
 9 Trie root;
10 
11 void createTrie(char *str)
12 {
13      int len = strlen(str);
14      Trie *p = &root,*q;
15      for( int i=0; i<len; ++i )
16      {
17           int id = str[i] - 'a';
18           if( p->next[id] == NULL )
19           {
20               q = (Trie *)malloc(sizeof(root));
21               q->v=1;
22               for( int j=0; j<26; j++ )
23                    q->next[j] = NULL;
24               p->next[id] = q;
25               p = p->next[id];
26           }
27           else
28           {
29               p->next[id]->v++;
30               p = p->next[id];
31           }
32     }
33 }
34 
35 int findTrie(char *str)
36 {
37     int len = strlen(str);
38     Trie *p = &root;
39     for( int i=0; i<len; i++ )
40     {
41         int id = str[i]-'a';
42         p = p->next[id];
43         if( p == NULL )
44             return 0;
45     }
46     return p->v;
47 }
48 
49 int main( )
50 {
51     char str[15];
52     int i;
53     for( i=0; i<26; i++ )
54         root.next[i] = NULL;
55     while( gets(str)&&str[0]!='\0' )
56         createTrie(str);
57     memset(str,0,sizeof(str));
58     while( scanf("%s",str) != EOF )
59     {
60         int ans = findTrie(str);
61         printf("%d\n",ans);
62     }
63     return 0;
64 }
65     
66

http://acm.hdu.edu.cn/showproblem.php?pid=1671

Phone List

View Code

 1 #include<iostream>
 2 using namespace std;
 3 
 4 typedef struct Trie{
 5         int v;
 6         Trie *next[10];
 7 }Trie;
 8 
 9 Trie *root;
10 
11 void createTrie(char *str)
12 {
13      int len = strlen(str);
14      Trie *p = root,*q;
15      for( int i=0; i<len; ++i )
16      {
17           int id = str[i] - '0';
18           if( p->next[id] == NULL )
19           {
20               q = (Trie *)malloc(sizeof(Trie));
21               q->v=1;
22               for( int j=0; j<10; j++ )
23                    q->next[j] = NULL;
24               p->next[id] = q;
25               p = p->next[id];
26           }
27           else
28           {
29               p->next[id]->v++;
30               p = p->next[id];
31           }
32     }
33     p->v = -1;
34 }
35 
36 int findTrie( char *str )
37 {
38     Trie *p = root;
39     int len = strlen(str);
40     for( int i=0; i<len; i++ )
41     {
42          int id = str[i] - '0';
43          p = p->next[id];
44          if( p == NULL )
45              return 0;
46          if( p->v == -1 )
47              return -1;
48     }
49     return -1;
50 }
51 
52 int deal( Trie *T )
53 {
54     int i;
55     if( T == NULL )
56         return 0;
57     for( i=0; i<10; i++ )
58     {
59         if( T->next[i]!=NULL )
60             deal(T->next[i]);
61     }
62     free(T);
63     return 0;
64 }    
65 
66 int main( )
67 {
68     char str[11];
69     int i;
70     int n;
71     int j;
72     int m;
73     int flag;
74     while( scanf("%d",&n) == 1 )
75     {
76         for( j=0; j<n; j++ )
77         { 
78             flag = 0;
79             root = (Trie *)malloc(sizeof(Trie));
80             for( i=0; i<10; i++ )
81                 root->next[i] = NULL;
82             scanf("%d",&m);
83             for( i=0; i<m; i++ )
84             {
85                 scanf("%s",str);
86                 if(  findTrie(str) == -1 )
87                     flag = 1;
88                 if( flag == 1 )
89                     continue;
90                 createTrie(str);
91             }
92             printf("%s\n",flag?"NO":"YES");
93             deal(root);
94         }
95     }
96     return 0;
97 }
98     
99

字典树 皇星客栈

统计难题

Phone List

字典树皇星客栈