首页 > 代码库 > poj 2418 Hardwood Species (trie树)

poj 2418 Hardwood Species (trie树)

2024-07-15 09:58:13   225人阅读

poj   2418   Hardwood Species 

http://poj.org/problem?id=2418

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 0x0f0f0f0f15 #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 tree20 {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         else44         {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

 


联系
我们