实验四、哈夫曼编码.doc

《实验四、哈夫曼编码.doc》由会员上传分享，免费在线阅读，更多相关内容在教育资源-天天文库。

1、实验四、哈夫曼编码问题描述与实验目的：给定n个字母（或字）在文档中出现的频率序列X=，求出这n个字母的Huffman编码。为方便起见，以下将频率用字母出现的次数（或称权值）w1,w2,…,wn代替。输入输入文件中的开始行上有一个整数T，（0

2、直到文件结束。输出对输入中的每组有n个权值的数据，应输出n+1行：先在一行上输出“Case#”，其中“#”是测试数据的组号（从1开始）；接下来输出n行，其第1行到第n行上依次输出第i个字母出现的次数和相应的Huffman编码，格式如下：wiHuffman编码。每组测试数据对应的输出最后结束时加一个空行，以便区分。为保证Huffman编码的唯一性，在构造Huffman树的过程中，我们约定：1．左儿子标记为0，右儿子标记为1；2．左儿子的权值>=右儿子的权值；3．相同权值w的两个字母x、y，先输入权值的字母x的H

3、uffman编码长度不超过后输入权值的字母y的Huffman编码长度。4．合并两个节点后新的权值应从右到左搜索、插入到相应的位置。例如：输入权值序列893412，其Huffman编码求解过程如下，参考图A-J：注意，如图C中权值1、2对应的节点合并后得权值为3的新节点，它插入到权值为3的原有节点的右边。实验结果：输入样例2698341286020553331输出样例Case190080131004111101121010Case26002010511015111031100031100131111011111

4、1实验报告要求:1．先分析要点，说明原理。2．能正确运行的程序。输入若干个字母的权值序列后，能输出对应的Huffman编码序列,可添加提示性语句。要有一般性，即可同时处理若干组数据，每组2行。3．设计、调试中的问题及实验体会。