trie树

scott_lan

题目地址：http://www.soj.me/1426
以前直接排序加上做一些判断就AC了，现在想练练trie，可是一直没AC。代码如下：（大家顺便教我怎么结贴，一直没找到）

1. 
   
2. #include <stdio.h>
   
3. #include<stdlib.h>
   
4. #include <string.h>
   
5. #define MAX 11
   
6. typedef struct node
   
7. {
   
8.     char data;
   
9.     struct node *next[MAX];
   
10.     int mrk;
    
11. }node;
    
12. 
    
13. void del(node *root);
    
14. 
    
15. int main()
    
16. {
    
17.     int t, n;
    
18.     scanf("%d", &t);
    
19.     for(; t>0; t--)
    
20.     {
    
21.         int prefix = 0, cnt;
    
22.         node *root = malloc(sizeof(node));
    
23.         root->data = '#';//根节点就随便放个数据吧
    
24.         memset(root->next, 0, sizeof(root->next));
    
25.         root->mrk = 0;
    
26.         scanf("%d", &n);
    
27.         char nums[10000][11];
    
28.         memset(nums, 0, sizeof(nums));
    
29.         for(cnt=0; cnt<n; cnt++)
    
30.             scanf("%s", nums[cnt]);
    
31. 
    
32.         for(cnt=0; cnt<n; cnt++)//下面是进行插入不进行判断
    
33.         {
    
34.             node *s = root;
    
35.             int i, len = strlen(nums[cnt]);
    
36.             char *tmp = nums[cnt];
    
37.             for(i=0; i<len; i++)//插入第i个字符串，并做判断
    
38.             {
    
39.                 if(s->mrk == 1)//发现有前缀，让prefix为1
    
40.                 {
    
41.                     printf("%s\n", nums[cnt]);
    
42.                     printf("============\n");
    
43.                     prefix = 1;
    
44.                     break;
    
45.                 }
    
46. 
    
47.                 if(s->next[tmp[i]-'0'] == NULL)//插入
    
48.                 {
    
49.                     printf("ifififif\n");
    
50.                     s->next[tmp[i]-'0'] = (node*)malloc(sizeof(node));
    
51.                     s->next[tmp[i]-'0']->data = tmp[i];
    
52.                     memset(s->next[tmp[i]-'0']->next, 0, sizeof(s->next[tmp[i]-'0']->next));
    
53.                     s->next[tmp[i]-'0']->mrk = 0;
    
54.                 }
    
55.                 else
    
56.                     s = s->next[tmp[i]-'0'];
    
57.             }
    
58.             if(prefix == 1)
    
59.                 break;
    
60.             s->mrk = 1;
    
61.         }
    
62.         printf("%s\n", prefix==1?"NO":"YES");
    
63.         del(root);
    
64.     }
    
65.     return 0;
    
66. }
    
67. 
    
68. void del(node *root)
    
69. {
    
70.     if(root == NULL)
    
71.         return;
    
72.     int i;
    
73.     for(i=0; i<MAX; i++)
    
74.         del(root->next[i]);
    
75.     free(root);
    
76. }

复制代码

starwing83

回复 1# scott_lan


    你难道没发现，你只记录了结束的状态，但是没有记录”经过“的状态么？

比如说，假设现在有个号码911112，你在2处设置了”结束“，但是又来了个号码911，你在最后的1处是找不到mrk的，但是它的确是之前号码的前缀。

修改一下设置prefix的条件。如果发现当前的串结束了，并且当前的节点不是现在分配的，那么也算prefix=1。

fender0107401

我觉得还是递归实现比较爽。

scott_lan

回复 3# fender0107401
递归实现？可不可以给个例子出来呢？

fender0107401

回复 4# scott_lan

你destroy整个树的时候不就是用的递归吗，插入新的entry的时候也可以用递归实现，

我感觉递归看着比较清楚。

scott_lan

题目地址：http://www.soj.me/1426
删除不用递归还真不知道怎么搞，重新写了一下，AC了，谢谢2楼~还是没人说怎么结贴啊，杯具
顺便贴下自己的代码，也希望各位帮看看还可以怎么改进

1. #include <stdio.h>
   
2. #include <stdlib.h>
   
3. #include<string.h>
   
4. /*
   
5.     只是对一些号码进行处理，0-9的一些组合，,刚好串最长可以是10，定义MAX=10
   
6. */
   
7. #define MAX 10
   
8. 
   
9. typedef struct trie_node
   
10. {
    
11.     struct trie_node *nxt[MAX];//每个节点有MAX个孩子，trie的空间开支巨大
    
12.     int mrk;//初始化为0，一个号码插入完整后置1，表示整个号码都插入trie了
    
13. } trie_node;
    
14. 
    
15. int insert(trie_node *root, char *number)
    
16. {
    
17.     if(root==NULL)
    
18.         return 0;
    
19.     trie_node *cur = root;
    
20.     int prefix = 0, i, len=strlen(number);
    
21.     for(i=0; i<len; i++)
    
22.     {
    
23.         /*
    
24.             因为是判断是否有前缀，先要判断mrk是不是等于1了
    
25.             当前节点的number[i]-'0'分支为NULL
    
26.         */
    
27.         if(cur->mrk != 1 && cur->nxt[number[i]-'0']==NULL)
    
28.         {
    
29.             //分配一个新结点并初始化，插入
    
30.             cur->nxt[number[i]-'0'] = malloc(sizeof(trie_node));
    
31.             cur->nxt[number[i]-'0']->mrk = 0;
    
32.             memset(cur->nxt[number[i]-'0']->nxt, 0, sizeof(cur->nxt[number[i]-'0']->nxt));
    
33.         }
    
34.         /*
    
35.             如果已经到号码尾部：比如先插入111，再插入11111
    
36.             或要插入串已经到结尾：比如先插入11111，再插入111
    
37.             表明有前缀存在
    
38.         */
    
39.         else if(cur->mrk==1 || i==len-1)
    
40.         {
    
41.             prefix = 1;
    
42.             break;
    
43.         }
    
44.         cur = cur->nxt[number[i]-'0'];
    
45.     }
    
46.     if(prefix==1)
    
47.         return 1;
    
48.     cur->mrk = 1;
    
49.     return 0;
    
50. }
    
51. 
    
52. void clr(trie_node *root)
    
53. {
    
54.     if(root==NULL)
    
55.         return;
    
56.     int i;
    
57.     for(i=0; i<MAX; i++)
    
58.         clr(root->nxt[i]);
    
59.     free(root);
    
60. }
    
61. 
    
62. int main()
    
63. {
    
64.     int t;
    
65.     scanf("%d", &t);
    
66.     for(; t>0; t--)
    
67.     {
    
68.         trie_node *root = malloc(sizeof(trie_node));
    
69.         root->mrk = 0;
    
70.         memset(root->nxt, 0, sizeof(root->nxt));
    
71.         int n,i, prefix = 0;
    
72.         char numbers[10000][MAX];
    
73.         scanf("%d", &n);
    
74.         for(i=0; i<n; i++)
    
75.             scanf("%s", numbers[i]);
    
76.         for(i=0; i<n; i++)
    
77.         {
    
78.             prefix=insert(root, numbers[i]);
    
79.             if(prefix)
    
80.                 break;
    
81.        }
    
82.        printf("%s\n", prefix==1?"NO":"YES");
    
83.        clr(root);
    
84.     }
    
85.     return 0;
    
86. }
    

复制代码

redor

我这有一个trie实现
http://libibase.googlecode.com/s ... /src/utils/mmtrie.c
http://libibase.googlecode.com/s ... /src/utils/mmtrie.h
直接mmap隐射到文件的.

scott_lan

回复 7# redor
考完试好好研究~