poj 2418 Hardwood Species (trie树)

poj 2418 Hardwood Species

trie树+dfs

题意：给你多个单词，问每个单词出现的频率。

方法：通过字典树，将所有单词放入树中，通过dfs遍历（题目要求按ASSIC码顺序输出单词及其频率），dfs可满足

注意：单词中不一定只出现26个英文字母，ASSIC码表共有256个字符

 1 #include <stdio.h>
 2 #include <string.h>
 3 #include <iostream>
 4 #include <algorithm>
 5 #include <cstdio>
 6 #include <cstring>
 7 #include <cmath>
 8 #include <stack>
 9 #include <queue>
10 #include <functional>
11 #include <vector>
12 #include <map>
13 using namespace std;
14 #define M 0x0f0f0f0f
15 #define min(a,b) (a>b?b:a)
16 #define max(a,b) (a>b?a:b)
17 int ji;
18 char st[40];
19 struct tree
20 {
21     int count_;
22     struct tree *next[256];
23 };
24 
25 void insert_(struct tree *root,char *s)
26 {
27     int i;
28     if(root==NULL||*s=='\0')
29         return ;
30     struct tree *p=root;
31     while(*s!='\0')
32     {
33 
34         if(p->next[*s]==NULL)
35         {
36             struct tree *t=(struct tree *)malloc(sizeof(struct tree));
37             for(i=0; i<256; i++)
38                 t->next[i]=NULL;
39             t->count_=0;
40             p->next[*s]=t;
41             p=t;
42         }
43         else
44         {
45             p=p->next[*s];
46         }
47         s++;
48     }
49     p->count_++;
50 }
51 int j=0;
52 void dfs(struct tree *p,int j)
53 {
54     int i;
55     if(p->count_)
56     {
57         st[j]='\0';
58         double m=(p->count_)*1.0/((ji)*1.0)*100;
59         printf("%s %.4lf\n",st,m);
60     }
61     for(i=0; i<256; i++)
62     {
63         if(p->next[i]!=NULL)
64         {
65             st[j]=i;
66             dfs(p->next[i],j+1);
67         }
68     }
69 }
70 
71 int main()
72 {
73     char a[10005],a1[10005];
74     int i;
75     struct tree *root=(struct tree *)malloc(sizeof(struct tree));
76     for(i=0; i<256; i++)
77     {
78         root->next[i]=NULL;
79     }
80     root->count_=0;
81     ji=0;
82     while(gets(a)!=NULL)
83     {
84         ji++;
85         insert_(root,a);
86     }
87     dfs(root,0);
88     return 0;
89 }

View Code