算法题4 哈夫曼编码

发布时间: 2017年6月19日 00:23   时间限制: 1000ms   内存限制: 128M

给定n个字母(或字)在文档中出现的频率序列X=<x1,x2,,xn>,求出这n个字母的Huffman编码。为方便起见,以下将频率用字母出现的次数(或称权值)w1,w2,,wn代替。

输入文件中的开始行上有一个整数T,(0<T<=20),表示有T组测试数据。

接下来是T行测试数据的描述,每组测试数据有2行。测试数据的第1行上是一个正整数n,(n<50),表示序列的长度。第2行是n个字母出现的权值序列w1,w2,,wn,它们均为正整数,相邻的两个整数之间用空格隔开。

输入直到文件结束。

对输入中的每组有n个权值的数据,应输出n+1行:先在一行上输出“Case #”,其中“#”是测试数据的组号(从1开始);接下来输出n行,其第1行到第n行上依次输出第i个字母出现的次数和相应的Huffman编码,格式如下:

wi Huffman编码。

每组测试数据对应的输出最后结束时加一个空行,以便区分。

为保证Huffman编码的唯一性,在构造Huffman树的过程中,我们约定:

1.左儿子标记为0,右儿子标记为1;

2.左儿子的权值>=右儿子的权值;

3.相同权值w的两个字母x、y,先输入权值的字母x的Huffman编码长度不超过后输入权值的字母y的Huffman编码长度。

4.合并两个节点后新的权值应从右到左搜索、插入到相应的位置。

例如:输入权值序列8 9 3 4 1 2,其Huffman编码求解过程如下,参考图A-J:

[图片]

注意,如图C中权值1、2对应的节点合并后得权值为3的新节点,它插入到权值为3的原有节点的右边。

复制
2
6
9 8 3 4 1 2
8
60 20 5 5 3 3 3 1
Case 1
9 00
8 01
3 100
4 11
1 1011
2 1010

Case 2
60 0
20 10
5 1101
5 1110
3 11000
3 11001
3 11110
1 11111
1614

old_judge

old_judge_None