哈夫曼树实验报告 Company number：【0089WT-8898YT-W8CCB-BUUT-202108】
计算机科学与技术学院数据结构实验报告
班级 2014级计算机1班学号姓名张建华成绩
实验项目简单哈夫曼编/译码的设计与实现实验日期一、实验目的
本实验的目的是进一步理解哈夫曼树的逻辑结构和存储结构，进一步提高使用理论知识指导解决实际问题的能力。
二、实验问题描述
利用哈夫曼编码进行通信可以大大提高信道利用率，缩短信息传输时间，降低传输成本。但是，这要求在发送端通过一个编码系统对待传数据预先编码，在接收端将传来的数据进行译码，此实验即设计这样的一个简单编/码系统。系统应该具有如下的几个功能：
1、接收原始数据。
从终端读入字符集大小n，以及n个字符和n个权值，建立哈夫曼树，并将它存于文件中。
2、编码。
利用已建好的哈夫曼树（如不在内存，则从文件中读入），对文件中的正文进行编码，然后将结果存入文件中。
3、译码。
利用已建好的哈夫曼树将文件中的代码进行译码，结果存入文件中。
4、打印编码规则。
即字符与编码的一一对应关系。
5、打印哈夫曼树，
将已在内存中的哈夫曼树以直观的方式显示在终端上。
三、实验步骤
1、实验问题分析
1、构造哈夫曼树时使用静态链表作为哈夫曼树的存储。
在构造哈夫曼树时，设计一个结构体数组HuffNode保存哈夫曼树中各结点的信息，根据二叉树的性质可知，具有n个叶子结点的哈夫曼树共有2n-1个结点，所以数组HuffNode的大小设置为2n-1，描述结点的数据类型为：
Typedef strcut
{
Int weight；/*结点权值*/
Int parent；
Int lchild；
Int rchild；
}HNodeType；
2、求哈夫曼编码时使用一维结构数组HuffCode作为哈夫曼编码信息的存储。
求哈夫曼编码，实质上就是在已建立的哈夫曼树中，从叶子结点开始，沿结点的双亲链域回退到根结点，没回退一步，就走过了哈夫曼树的一个分支，从而得到一位哈夫曼码值，由于一个字符的哈夫曼编码是从根结点到相应叶子结点所经过的路
径上各分支所组成的0、1序列，因此先得到的分支代码为所求编码的低位码，后得到的分支代码位所求编码的高位码，所以设计如下数据类型：
#define MAXBIT 10
Typedef struct
{
Int bit[MAXBIT]；
Int start；
}HCodeType；
3、文件、和。
2、功能（函数）设计
（1）、初始化功能模块。
此功能模块的功能为从键盘接收字符集大小n，以及n个字符和n个权值。（2）、建立哈夫曼树的功能模块。
此模块功能为使用1中得到的数据按照教材中的构造哈夫曼树的算法构造哈夫曼树，即将HuffNode数组中的各个位置的各个域都添上相关的值，并将这个结构体数组存于文件中。
（3）、建立哈夫曼编码的功能模块。
此模块功能为从文件中读入相关的字符信息进行哈夫曼编码，然后将结果存入中，同时将字符与0、1代码串的一一对应关系打印到屏幕上。
（4）、译码的功能模块。
此模块功能为接收需要译码的0、1代码串，按照3中建立的编码规则将其翻译成字符集中字符所组成的字符串形式，存入文件，同时将翻译的结果在屏幕上打印输出。（5）、打印哈夫曼树的功能模块。
此模块功能为从HuffNode数组中读入相关的结点信息，以图形的方式将各个结点以及叶子结点的权值和左分支上的0和右分支上的1画出来。
四、实验结果（程序）及分析
1、实验主要代码
typedef struct /*结点结构体*/
{
string hfmstr; /*结点内容*/
int weight; /*结点权值*/
int parent;
int lchild;
int rchild;
}HNodeType;
typedef struct /* 编码结构体 */
{
int bit[MAXBIT];
int start;
}HCodeType;
void Create_HuffMTree(HNodeType HFMTree[],int n) /*创建哈夫曼树*/ {
int m1,x1,m2,x2;
int i,j;
for(i=0;i<2*n-1;i++)
{
HFMTree[i].hfmstr="";
HFMTree[i].weight=0;
HFMTree[i].parent=-1;
HFMTree[i].lchild=-1;
HFMTree[i].rchild=-1;
}
for(i=0;i{
cout<<"请输入第"<cin>>HFMTree[i].weight;
cout<<"请输入对应字符"<cin>>HFMTree[i].hfmstr;
}
for(i=0;i{
x1=x2=MAXVALUE;
m1=m2=0;
for(j=0;j{
if(HFMTree[j].parent==-1&&HFMTree[j].weight{
x2=x1;
m2=m1;
x1=HFMTree[j].weight;
m1=j;
}
else if(HFMTree[j].parent==-1&&HFMTree[j].weight
