POJ-2418-Hardwood Species-字典树

本文主要是介绍POJ-2418-Hardwood Species-字典树，希望对大家解决编程问题提供一定的参考价值，需要的开发者们随着小编来一起学习吧！

统计各个单词占得比例

#include<stdio.h>
#include<string.h>
#include<stdlib.h>
#include<algorithm>
#include<iostream>
using namespace std;
int top, t=0;
struct node
{int next[130];int n;
}pos[3500];struct nod
{char s[35];int num;
}ls[12000];bool cmp(nod a,nod b)
{return strcmp(a.s,b.s)<0;
}
void add(char st[])
{int j = 0, len = strlen(st);int i;for( i = 0; i < len; i++){int x = st[i];if(pos[j].next[x]==-1)pos[j].next[x]=++top;j = pos[j].next[x];}if(pos[j].n == -1){pos[j].n = t++;strcpy(ls[t-1].s,st);}ls[pos[j].n].num++;
}
int main()
{top = 0;t = 0;memset(pos,-1,sizeof(pos));for(int i = 0; i < 12000; i++){ls[i].num = 0;}char str[35];int sum = 0;while(gets(str)!=NULL){add(str);sum++;}sort(ls,ls+t,cmp);for(int i = 0; i < t; i++)printf("%s %.4f\n",ls[i].s,ls[i].num*1.0/sum*100);return 0;
}

这篇关于POJ-2418-Hardwood Species-字典树的文章就介绍到这儿，希望我们推荐的文章对编程师们有所帮助！

---