【POJ】2418 Hardwood Species

简单字典树。
 1 #include <cstdio>
 2 #include <cstring>
 3 #include <cstdlib>
 4 
 5 #define MAXN 128
 6 
 7 typedef struct Trie {
 8     int count;
 9     Trie *next[MAXN];
10     Trie() {
11         count = 0;
12         for (int i=0; i<MAXN; ++i)
13             next[i] = NULL;
14     }
15 } Trie;
16 
17 Trie root;
18 char buf[35];
19 double n = 0;
20 
21 void create(char str[]) {
22     int i = 0, id;
23     Trie *p = &root, *q;
24 
25     while (str[i]) {
26         id = str[i];
27         ++i;
28         if (p->next[id] == NULL) {
29             q = new Trie();
30             p->next[id] = q;
31         }
32         p = p->next[id];
33     }
34     p->count++;
35 }
36 
37 void dfs(Trie *t, int d) {
38     int i;
39 
40     if (t->count) {
41         buf[d] = '';
42         printf("%s %.4lf
", buf, t->count*100.0/n);
43     }
44     for (i=0; i<MAXN; ++i) {
45         if (t->next[i]) {
46             buf[d] = i;
47             dfs(t->next[i], d+1);
48         }
49     }
50 }
51 
52 int main() {
53     while (gets(buf) != NULL) {
54         create(buf);
55         n += 1.0;
56     }
57     dfs(&root, 0);
58     return 0;
59 }