poj 2418 Hardwood Species（字典树）

 1 #include<stdio.h>
 2 #include<string.h>
 3 #include<stdlib.h>
 4 
 5 const int MAXN=256;
 6 
 7 struct Trie
 8 {
 9     Trie *next[MAXN];
10     int v;
11 };
12 Trie *root;
13 int sum;
14 
15 void creatTrie(char *str)
16 {
17     int len=strlen(str);
18     Trie *p=root,*q;
19     for(int i=0;i<len;i++)
20     {
21         int id=str[i];
22         if(p->next[id]==NULL)
23         {
24             q=(Trie *)malloc(sizeof(Trie));
25             q->v=0;//这里初始化
26             for(int j=0;j<MAXN;j++) q->next[j]=NULL;
27             p->next[id]=q;
28             p=p->next[id];
29         }
30         else
31         {
32             p=p->next[id];
33         }
34     }
35     p->v++;
36 }
37 
38 int findTrie(char *str)
39 {
40 
41     int len=strlen(str);
42     Trie *p=root;
43     for(int i=0;i<len;i++)
44     {
45         int id=str[i];
46         p=p->next[id];
47         if(p==NULL) return 0;
48         if(p->v==-1) return -1;
49     }
50     return -1;
51 }
52 
53 void DFS(Trie *root,int pos,char str[31])
54 {
55     int i;
56     if(root->v)
57     {
58         str[pos]='\0';
59         if(str[0])
60         {
61             printf("%s %.4lf\n",str,100.0*root->v/sum);
62         }
63     }
64     for(i=0;i<256;i++)
65     {
66         if(root->next[i]!=NULL)
67         {
68             str[pos]=i;
69             DFS(root->next[i],pos+1,str);
70         }
71     }
72 }
73 
74 int main()
75 {
76     char str[31],str1[60];
77     sum=0;
78     int i;
79     memset(str,0,sizeof(str));
80     root=(Trie *)malloc(sizeof(Trie));
81     for(i=0;i<MAXN;i++) root->next[i]=NULL;
82     while(gets(str)!=NULL)
83     {
84         sum++;
85         creatTrie(str);
86     }
87     DFS(root,0,str);
88     return 0;
89 }

 1 #include<stdio.h>
 2 #include<string.h>
 3 #include<stdlib.h>
 4 #include<map>
 5 #include<string>
 6 #include<algorithm>
 7 #include<iostream>
 8 using namespace std;
 9 const int MAXN=3000;
10 struct Node
11 {
12     string nam;
13     double cnt;
14 }node[MAXN];
15 map<string,int>_map;
16 
17 bool cmp(Node a,Node b)
18 {
19     return a.nam<b.nam;
20 }
21 
22 int main()
23 {
24     string str;
25     int sum=0;
26     int i;
27     _map.clear();
28     while(getline(cin,str))
29     {
30         sum++;
31         _map[str]++;
32     }
33     int cas=0;
34     map<string,int>::iterator iter;
35     for(iter=_map.begin();iter!=_map.end();iter++)
36     {
37         cout<<iter->first;
38         printf(" %.4lf\n",100.0*iter->second/sum);
39     }
40        return 0;
41 }