数据结构实验之二叉树六：哈夫曼编码
Time Limit: 1000ms Memory limit: 65536K
题目描述
字符的编码方式有多种，除了大家熟悉的
ASCII
编码，哈夫曼编码
(Huffman Coding)
也是一种编码方式，它是可变字长编码。该方法完全依据字符出现概率来构造出平均长度最短的编码，称之为最优编码。哈夫曼编码常被用于数据文件压缩中，其压缩率通常在
20%
～
90%
之间。你的任务是对从键盘输入的一个字符串求出它的
ASCII
编码长度和哈夫曼编码长度的比值。
输入
输入数据有多组，每组数据一行，表示要编码的字符串。
输出
对应字符的
ASCII
编码长度
la
，
huffman
编码长度
lh
和
la/lh
的值
(
保留一位小数
)
，数据之间以空格间隔。
示例输入
AAAAABCD THE_CAT_IN_THE_HAT
示例输出
64 13 4.9 144 51 2.8
///每次都把长度累加 最后就是哈夫曼编码的长度 哈弗曼编码详情百度
/** 重载()运算符
struct cmp
{
bool operator ()(int x,int y)
{
return (x > y);
}
};
*/
#include <bits/stdc++.h>
using namespace std;
const int maxn=10010;
priority_queue < int,vector<int>,greater<int> >q;
/// 最大值先输出的优先队列 容器为 vector , 可以重载()运算符 见上cmp
int main()
{
int n;
int huf,sum,i,num;
while (cin>>n)
{
huf=0;
sum=0;
for (i=1; i<=n; i++)
{
cin>>num;
q.push(num);
}
while(!q.empty())
{
huf+=sum; ///最后一次不计入长度 所以放在这里了...
sum=q.top();
q.pop();
if (!q.empty())
{
sum+=q.top();
q.pop();
q.push(sum);
}
}
cout<<huf<<endl;
}
return 0;
}
版权声明：本文为Gentle_Guan原创文章，遵循 CC 4.0 BY-SA 版权协议，转载请附上原文出处链接和本声明。