C# · 12月 20, 2021

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;

}