首页 > 代码库 > POJ 1521 Entropy
POJ 1521 Entropy
优先队列实现完整哈夫曼树,一大段英文都是介绍哈夫曼树的。
外面用了一个pre来找parent,其实可以把这个项放入结构体中。
特别注意当有一个结点的情况不能用优先队列,另外判断下
#include<iostream> #include<cstring> #include<string> #include<algorithm> #include<cstdio> #include<queue> using namespace std; #define maxn 256 struct node { int ch; int num; int depth; }nodes[512],a,b,c; int pre[512]; class cmp { public: bool operator()(struct node a,struct node b)const { return a.num>b.num; } }; int N; char str[10000]; int main() { int i,j,k,LEN,maxnum; priority_queue<struct node,vector<struct node>,cmp> q; while(scanf("%s",str)!=EOF) { if(strcmp(str,"END")==0) break; LEN=strlen(str); memset(nodes,0,sizeof(nodes)); memset(pre,0,sizeof(pre)); for(i=0;i<LEN;i++) { if(nodes[str[i]].ch==0) nodes[str[i]].ch=str[i]; nodes[str[i]].num++; } maxnum=0; for(i=0;i<256;i++) if(nodes[i].num) q.push(nodes[i]),maxnum++,j=nodes[i].num; int pos=256; if(maxnum==1) { printf("%d %d 8.0\n",j*8,j); q.pop(); continue; } while(q.size()>1) { a=q.top(); q.pop(); b=q.top(); q.pop(); pre[a.ch]=pos; pre[b.ch]=pos; c.num=a.num+b.num; c.ch=pos; pos++; q.push(c); } int ans=0; for(i=0;i<256;i++) if(nodes[i].num) { maxnum=0; k=i; while(pre[k]) k=pre[k],maxnum++; ans+=nodes[i].num*maxnum; } printf("%d %d %.1f\n",LEN*8,ans,(LEN*8+0.0)/ans); while(!q.empty()) //清空队列 q.pop(); } return 0; }
声明:以上内容来自用户投稿及互联网公开渠道收集整理发布,本网站不拥有所有权,未作人工编辑处理,也不承担相关法律责任,若内容有误或涉及侵权可进行投诉: 投诉/举报 工作人员会在5个工作日内联系你,一经查实,本站将立刻删除涉嫌侵权内容。