poj2418Hardwood Species

trie树，有非空格、字母的字符
View Code
 1 #include <iostream>
 2 #include<cstdio>
 3 #include<cstring>
 4 #include<stdlib.h>
 5 #include<algorithm>
 6 using namespace std;
 7 typedef struct node
 8 {
 9     int num;
10     struct node *next[130];
11     node()
12     {
13         memset(next,NULL,sizeof(next));
14         num = 0;
15     }
16 }trie;
17 int y,k;
18 char ss[10010][40],w[40];
19 void ctrie(trie *t,char *x)
20 {
21     int i,j,d,k = strlen(x);
22     char yy[40];
23     strcpy(yy,x);
24     trie *p = t;
25     for(i = 0 ; i < k ; i++)
26     {
27         d = x[i];
28         if(p->next[d]==NULL)
29         {
30             p->next[d] = new node;
31         }
32         p = p->next[d];
33     }
34     if(p->num==0)
35     {
36         strcpy(ss[y],yy);
37         y++;
38     }
39     p->num++;
40 }
41 void dfs(trie *t,int x)
42 {
43     trie *p = t;
44     int i;
45     if(p->num>0)
46     {
47         w[x] = '\0';
48         printf("%s %.4lf\n",w,p->num*100.0/k);
49     }
50     for(i = 1; i <= 129 ; i++)
51     {
52         if(p->next[i]!=NULL)
53         {
54             w[x] = i;
55             dfs(p->next[i],x+1);
56         }
57     }
58 }
59 int main()
60 {
61     int i,j;
62     char s[40];
63     trie *t = new node;
64     while(gets(s)!=NULL)
65     {
66         k++;
67         ctrie(t,s);
68     }
69     dfs(t,0);
70     return 0;
71 }