POJ 1521 哈夫曼编码 贪心法

题意：给定字符串，求哈夫曼编码长和它与等长编码的比值，比较基础

思路：这题考查哈弗曼编码，但其实没必要建树得出编码，只需要统计哈弗曼编码后的总码长即可

参考了网友的题解，用到了优先权队列维持一个从小到大的序列

第38行其实就是把越小的频数反复多加几次，越大的频率少加几次，体现了前缀码的设计思想

Source Code

//这题考查哈弗曼编码，但其实没必要建树得出编码，只需要统计哈弗曼编码后的总码长即可
#include <iostream>
#include <queue>
using namespace std;
class mycomparison
{
public:
bool operator() (const int& lhs, const int&rhs) const
{
return (lhs > rhs);//使得从小到大排序，队列头为最小元素，优选权队列默认队列头最大
}
};
int main(){
char s[500];
int count[200] = {0};//count[i]记录ASCII码为i的字符的个数
int i, sum, len;
priority_queue<int, vector<int>, mycomparison> pq;
while(cin>>s){
if(!strcmp(s,"END")){
break;
}
len = strlen(s);
for(i = 0; i < len; i++){
count[s[i]]++;
}
sum = 0;
for(i = 0;i < 200; i++){
if(count[i]){
pq.push(count[i]);
count[i] = 0;
}
}
while(pq.size() > 1){
int a = pq.top(); pq.pop();
int b = pq.top(); pq.pop();
sum += a + b;//其实就是把越小的频率反复多加几次，越大的频率少加几次
pq.push(a + b);
}
if(!sum){
sum = len;//此时pq中只有一个元素
}
while(!pq.empty()){
pq.pop();
}
printf("%d %d %.1fn",8*len,sum,double(double(8*len)/sum));//注意精度设置
}
return 0;
}

最后

以上就是精明秋天为你收集整理的POJ 1521 哈夫曼编码 贪心法的全部内容，希望文章能够帮你解决POJ 1521 哈夫曼编码 贪心法所遇到的程序开发问题。

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