HDU 1671 phone list

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

字典树的题目，在POJ上的时候字典树的话会因为不断开辟新的节点而消耗过多的时间，所以会开一个固定的空间.....

但是我不知道该开多大的空间....o(╯□╰)o

看别人的代码是开到 100000...话说我不知道为什么只要那么点就可以了....

Code

 1 #include <stdio.h>
 2 #include <stdlib.h>
 3 #include <string.h>
 4 #include <iostream>
 5 using namespace std;
 6 struct node
 7 {
 8     int num,f;
 9     node *next[10];
10 };
11 typedef node* link;
12 link head;
13 int f = 0;
14 
15 void btree(char s[],link r)
16 {
17     int i, j, l,len;
18     link p;
19     if(f)  return ;
20     len = strlen(s);
21     for(i = 0; i < len; i++)
22     {
23         j = s[i] - '0';
24         if(!r->next[j])
25         {
26             p = (link)malloc(sizeof(node));
27             p->num = 1;
28             p->f = 0;
29             for(l = 0; l < 10; l++)
30             p->next[l] = NULL;
31             r->next[j] = p;
32             r = p;
33         }
34         else
35         {
36             r = r->next[j];
37             r->num++;
38         }
39         if(i == len -1) r->f = 1;
40         if(r->num == 2 && r->f == 1 ) f = 1;
41     }
42 }
43 
44 void realse(link r)
45 {
46     int i;
47     if(!r) return ;
48     else
49     {
50         for(i = 0; i < 10; i++)
51         realse(r->next[i]);
52         free(r);
53     }
54     return ;
55 } 
56 
57 int main()
58 {
59     char s[12];
60     int n, m, i;
61     scanf("%d",&n);
62     while(n--)
63     {
64         head = (link)malloc(sizeof(node));
65         for(i = 0; i < 10; i++)
66         head->next[i] = NULL;
67         scanf("%d",&m);
68         f=0;
69         for(i = 0; i < m; i++)
70         {
71             scanf("%s",s);
72             btree(s, head);
73         }
74         if(f) printf("NO\n");
75         else printf("YES\n");
76         realse(head);
77     }
78     return 0;
79 }