ZOJ 1117 Entropy(哈夫曼编码)

按照普通的哈夫曼编码来做就可以,只有一个字符的时候要特殊处理下

#include <iostream>
#include <queue>
#include <cstdio>
#include <cstring>
#include <vector>
#include <functional>
using namespace std;
const int maxn=1010;
char text[maxn];
int cnt[maxn],father[maxn];
struct node{
int p,f,v;
bool operator>(const node &rhs)const{
return v>rhs.v;
}
}ns[maxn];
priority_queue<node,vector<node>,greater<node> >q;
int main(){
while(scanf("%s",text)&&strcmp(text,"END")){
while(q.size())q.pop();
memset(cnt,0,sizeof(cnt));
memset(father,0,sizeof(father));
memset(ns,0,sizeof(ns));
int len=strlen(text),ans=0;
for(int i=0;i<len;++i){
cnt[text[i]]++;
}
for(int i=0;i<96;++i){
if(cnt[i]){
ns[i].f=0;
ns[i].p=i;
ns[i].v=cnt[i];
q.push(ns[i]);
}
}
int flag=0;
if(q.size()==1){
flag=1;
}else{
flag=0;
}
int i=100;
while(q.size()>1){
node n1=q.top();
q.pop();
node n2=q.top();
q.pop();
ns[n1.p].f=i;
ns[n2.p].f=i;
ns[i].p=i;
ns[i].v=n1.v+n2.v;
q.push(ns[i]);
++i;
}
for(int i=0;i<96;++i){
if(cnt[i]){
int cn=flag,t=i;
while(ns[t].f){
cn++;
t=ns[t].f;
}
ans+=cn*cnt[i];
}
}
printf("%d %d %.1lfn",8*len,ans,(8.0*len)/ans);
}
return 0;
}

最后

以上就是微笑酒窝为你收集整理的ZOJ 1117 Entropy(哈夫曼编码)的全部内容，希望文章能够帮你解决ZOJ 1117 Entropy(哈夫曼编码)所遇到的程序开发问题。

如果觉得靠谱客网站的内容还不错，欢迎将靠谱客网站推荐给程序员好友。