哈夫曼树编码实验报告

1 数学学院数学类数学1班田娟

数据结构课程设计

报告

题 目: 哈夫曼编码/译码

学 院 数学与信息科学学院 学科门类 理科 专 业 数学类 学 号 2013433033 姓 名 田娟 2014年 12 月30日

1

2 数学学院数学类数学1班田娟

目 录

一、需求分析

1.程序的功能··················································3 2.输入输出的要求··············································3 3.测试数据····················································3 二、概要设计

1.本程序所用的抽象数据类型的定义·······························3 2.主程序模块···················································3 3.主模块的流程及各子模块的主要功能·····························4 4.模块之间的层次关系···········································4

三、详细设计

1.采用c语言定义相关的数据类型·································4 2. 伪码算法·····················································5

四、调试分析

1.调试中遇到的问题及对问题的解决方法···························15

五、使用说明及测试结果

1.建立哈夫曼树,输入叶子结点个数,权值,字符集··················15 2.编码··························································15 3.译码··························································16 4.显示码文······················································16 5.显示哈夫曼树··················································16

六、源程序

2

3 数学学院数学类数学1班田娟

一、需求分析

1.程序的功能;

哈夫曼编码是一种应用广泛而有效的数据压缩技术。利用哈夫曼编码进行通信可以大大提高信道利用率,加快信息传输速度,降低传输成本。数据压缩的过程称为编码,解压缩的过程称为译码。进行信息传递时,发送端通过一个编码系统对待传数据(明文)预先编码,而接收端将传来的数据(密文)进行译码。

2.输入输出的要求;:

2.1.构造哈夫曼树及哈夫曼编码:从终端读入字符集大小n、n个字符以及n个对应的权值,建立哈夫曼树;利用已经建好的哈夫曼树求每个叶结点的哈夫曼编码,并保存。

2.2编码:利用已构造的哈夫曼编码对“明文”文件中的正文进行编码,然后将结果存入“密文”文件中。

2.3.译码:将“密文”文件中的0、1代码序列进行译码。

2.4.打印“密文”文件:将文件以紧凑格式显示在终端上,每行30个代码;同时,将此字符形式的编码文件保存。

2.5.打印哈夫曼树及哈夫曼编码:将已在内存中的哈夫曼树以凹入表形式显示在终端上,同时将每个字符的哈夫曼编码显示出来;并保存到文件。

3.测试数据。

3.1.令叶子结点个数N为4,权值集合为{1,3,5,7},字符集合为{A,B,C,D},且字符集与权值集合一一对应。

3.2.请自行选定一段英文文本,统计给出的字符集,实际统计字符的频度,建立哈夫曼树,构造哈夫曼编码,并实现其编码和译码。

二、概要设计

1.本程序所用的抽象数据类型的定义; class HuffmanTree //哈夫曼树 {

private:

HuffmanNode *Node; //Node[]存放哈夫曼树

int LeafNum; //哈夫曼树的叶子个数,也是源码个数 2.主程序模块 main()

2.2 建立哈夫曼树函数

// 函数功能:建立哈夫曼树

void HuffmanTree::CreateHuffmanTree() 2.3 函数功能:为哈夫曼树编码

3

联系客服:779662525#qq.com(#替换为@) 苏ICP备20003344号-4