SDUTOJ3345数据结构实验之二叉树六：哈夫曼编码

数据结构实验之二叉树六：哈夫曼编码

Time Limit:?1000 ms?Memory Limit:?65536 KiB

Submit?Statistic

Problem Description

字符的编码方式有多种，除了大家熟悉的ASCII编码，哈夫曼编码(Huffman?Coding)也是一种编码方式，它是可变字长编码。该方法完全依据字符出现概率来构造出平均长度最短的编码，称之为最优编码。哈夫曼编码常被用于数据文件压缩中，其压缩率通常在20%～90%之间。你的任务是对从键盘输入的一个字符串求出它的ASCII编码长度和哈夫曼编码长度的比值。

Input

?输入数据有多组，每组数据一行，表示要编码的字符串。

Output

?对应字符的ASCII编码长度la，huffman编码长度lh和la/lh的值(保留一位小数)，数据之间以空格间隔。

Sample Input

AAAAABCD

THE_CAT_IN_THE_HAT

Sample Output

64 13 4.9

144 51 2.8

Hint

Source

xam

#include

using namespace std;

int main()

{

char s[505];

int cnt[505];

int p[1000];

while (~scanf("%s",s))

{

memset(cnt,sizeof(cnt));

int len = strlen(s);

int sum1 = len * 8; // 计算ASCII编码的长度

int sum2 = 0;

for (int i = 0; i < len; i++)

cnt[s[i]]++; // 统计串中各元素个数

int top = 0,down = 0; // 栈顶和栈底

for (int i = 0; i < 505; i++)

{

if (cnt[i] != 0) // 字符存在 字符个数进栈

p[top++] = cnt[i];

}

sort(p,p + top); // 对栈内元素进行排序

while (top != down) // 当栈不为空的时候

{

int a = p[down++]; // 选择栈底的两个元素相加 后 入栈

if (top != down)

{

int b = p[down++];

sum2 += (a + b); // huffman编码长度加上栈底两元素和

p[top++] = a + b; // 栈底两元素相加 入栈

sort(p + down,p + top);

}

}

printf("%d %d %.1lfn",sum1,sum2,sum1 * 1.0 / sum2);

}

return 0;

}

（编辑：李大同）

【声明】本站内容均来自网络，其相关言论仅代表作者个人观点，不代表本站立场。若无意侵犯到您的权利，请及时与联系站长删除相关内容!