Phone Number(字典树)

【Description
Description】
We know that if a phone number A is another phone number B’s prefix, B is not able to
be called. For an example, A is 123 while B is 12345, after pressing 123, we call A, and not
able to call B.
Given N phone numbers, your task is to find whether there exits two numbers A and B
that A is B’s prefix.
Input
【Input
Input】
The input consists of several test cases.
The first line of input in each test case contains one integer N (0<N<1001), represent the
number of phone numbers.
The next line contains N integers, describing the phone numbers.
The last case is followed by a line containing one zero.
Output
【Output
Output】
For each test case, if there exits a phone number that cannot be called, print “NO”,
otherwise print “YES” instead.
Sample Input】
【Sample Input
2
012
012345
2
12
012345
0
Sample Output】
【Sample Output
NO
YES

 1 #include<stdio.h>
 2 #include<stdlib.h>
 3 struct node
 4 {
 5     int flag;
 6     struct node *next[10];
 7 }*root;
 8 int tag;
 9 struct node *creat()
10 {
11     struct node *p;
12     p=(struct node *)malloc(sizeof(struct node));
13     p->flag=0;
14     for(int i=0;i<10;i++)
15         p->next[i]=NULL;
16      return p;
17 }
18 void inser(char *s)
19 {
20     int i;
21     struct node *p;
22     p=root;
23     for(i=0;s[i]!='\0';i++)
24     {
25         if(!(p->next[s[i]-'0'])) p->next[s[i]-'0']=creat();
26         p=p->next[s[i]-'0'];
27         if(p->flag==1) tag=1;判断p节点是否是某字符串的结束。
28     }
29     p->flag=1;
30 }
31 int main ()
32 {
33     int t;
34     char s[1010];
35     while(~scanf("%d",&t))
36     {
37         if(!t) break;
38         root=creat();
39         tag=0;
40         while(t--)
41         {
42             scanf("%s",s);
43             inser(s);
44         }
45         if(tag==1)
46                 printf("NO\n");
47         else printf("YES\n");
48     }
49     return 0;
50 }