首页 > 代码库 > poj 2418 Hardwood Species (trie树)
poj 2418 Hardwood Species (trie树)
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 }
声明:以上内容来自用户投稿及互联网公开渠道收集整理发布,本网站不拥有所有权,未作人工编辑处理,也不承担相关法律责任,若内容有误或涉及侵权可进行投诉: 投诉/举报 工作人员会在5个工作日内联系你,一经查实,本站将立刻删除涉嫌侵权内容。