数据结构哈夫曼编码实验报告.doc

: .
数据结构实验报告
―― 实验五 简单哈夫曼编 /译码的设计与实现
本实验的目的是通过对简单哈夫曼编 /译码系统的设计与实现来熟练掌握树型结
构在实际问题中的应用。此实验可以作为综合实验，阶段性实验时可以选择其中的几 个功能来设计和实现。
一、【问题描述】
利用哈夫曼编码进行通信可以大大提高信道利用率， 缩短信息传输时间， 降低传输成本。 但是，这要求在发送端通过一个编码系统对待传数据预先编码， 在接收端将传来的数据进行 译码，此实验即设计这样的一个简单编 /码系统。系统应该具有如下的几个功能：
1、接收原始数据。
从终端读入字符集大小 n,以及n个字符和n个权值，建立哈夫曼树，并将它存于文件
中。
2、编码。
利用已建好的哈夫曼树（如不在内存,则从文件 中读入）,对文件中的正 文进行编码,然后将结果存入文件 中。
3、 译码。利用已建好的哈夫曼树将文件 中的代码进行译码,结果存入文件 中。
4、 打印编码规则。
即字符与编码的一一对应关系。
二、【数据结构设计】
1、 构造哈夫曼树时使用静态链表作为哈夫曼树的存储。 在构造哈夫曼树时,设计一个结构体数组 HuffNode 保存哈夫曼树中各结点的信息,根
据二叉树的性质可知,具有 n 个叶子结点的哈夫曼树共有 2n-1 个结点,所以数组 HuffNode 的大小设置为 2n-1 ,描述结点的数据类型为： typedef struct
{
int weight;// 结点权值
int parent;
int lchild;
int rchild;
char inf;
}HNodeType;
2、 求哈夫曼编码时使用一维结构数组 HuffCode 作为哈夫曼编码信息的存储。
求哈夫曼编码, 实质上就是在已建立的哈夫曼树中, 从叶子结点开始, 沿结点的双亲链 域回退到根结点,没回退一步,就走过了哈夫曼树的一个分支,从而得到一位哈夫曼码值, 由于一个字符的哈夫曼编码是从根结点到相应叶子结点所经过的路径上各分支所组成的 0、
1 序列,因此先得到的分支代码为所求编码的低位码,后得到的分支代码位所求编码的高位 码,所以设计如下数据类型：
#define MAXBIT 10
typedef struct
{
int bit[MAXBIT] ；
int start ；
}HcodeType ;
3、文件 、 和 。
三、【功能(函数)设计】
1、 初始化功能模块。
此功能模块的功能为从键盘接收字符集大小 n,以及n个字符和n个权值。
2、 建立哈夫曼树的功能模块。
此模块功能为使用1中得到的数据按照教材中的构造哈夫曼树的算法构造哈夫曼树， 即
将HuffNode数组中的各个位置的各个域都添上相关的值，并将这个结构体数组存于文件 中。
3、 建立哈夫曼编码的功能模块。
此模块功能为从文件 nodedat