2024年哈夫曼树 实验报告.docx

计算机科學与技术學院数据构造试验汇报

班级级计算机1班學号4138021姓名张建华成绩

试验项目简朴哈夫曼编/译码的设计与实現试验曰期.1.5

一、试验目的

本试验的目的是深入理解哈夫曼树的逻辑构造和存储构造，深入提高使用理论知识指导处理实际問題的能力。

二、试验問題描述

运用哈夫曼编码進行通信可以大大提高信道运用率，缩短信息传播時间，減少传播成本。不過，這规定在发送端通過一种编码系统看待传数据预先编码，在接受端将传来的数据進行译码，此试验即设计這样的一种简朴编/码系统。系统应當具有如下的几种功能：

1、接受原始数据。

從终端讀入字符集大小n，以及n個字符和n個权值，建立哈夫曼树，并将它存于文献hfmtree.dat中。

2、编码。

运用已建好的哈夫曼树（如不在内存，则從文献hfmtree.dat中讀入），對文献中的正文進行编码，然後将成果存入文献codefile.dat中。

3、译码。

运用已建好的哈夫曼树将文献codefile.dat中的代码進行译码，成果存入文献textfile.dat中。

4、打印编码规则。

即字符与编码的一一對应关系。

5、打印哈夫曼树，

将已在内存中的哈夫曼树以直观的方式显示在终端上。

三、试验环节

1、试验問題分析

1、构造哈夫曼树時使用静态链表作為哈夫曼树的存储。

在构造哈夫曼树時，设计一种构造体数组HuffNode保留哈夫曼树中各結點的信息，根据二叉树的性质可知，具有n個叶子結點的哈夫曼树共有2n-1個結點，因此数组HuffNode的大小设置為2n-1，描述結點的数据类型為：

Typedefstrcut

{

Intweight；/*結點权值*/

Intparent；

Intlchild；

Intrchild；

}HNodeType；

2、求哈夫曼编码時使用一维构造数组HuffCode作為哈夫曼编码信息的存储。

求哈夫曼编码，实质上就是在已建立的哈夫曼树中，從叶子結點開始，沿結點的双亲链域回退到根結點，没回退一步，就走過了哈夫曼树的一种分支，從而得到一位哈夫曼码值，由于一种字符的哈夫曼编码是從根結點到對应叶子結點所通過的途径上各分支所构成的0、1序列，因此先得到的分支代码為所求编码的低位码，後得到的分支代码位所求编码的高位码，因此设计如下数据类型：

#defineMAXBIT10

Typedefstruct

{

Intbit[MAXBIT]；

Intstart；

}HCodeType；

3、文献hfmtree.dat、codefile.dat和textfile.dat。

2、功能（函数）设计

（1）、初始化功能模块。

此功能模块的功能為從键盘接受字符集大小n，以及n個字符和n個权值。

（2）、建立哈夫曼树的功能模块。

此模块功能為使用1中得到的数据按照教材中的构造哈夫曼树的算法构造哈夫曼树，即将HuffNode数组中的各個位置的各個域都添上有关的值，并将這個构造体数组存于文献hfmtree.dat中。

（3）、建立哈夫曼编码的功能模块。

此模块功能為從文献hfmtree.dat中讀入有关的字符信息進行哈夫曼编码，然後将成果存入codefile.dat中，同步将字符与0、1代码串的一一對应关系打印到屏幕上。

（4）、译码的功能模块。

此模块功能為接受需要译码的0、1代码串，按照3中建立的编码规则将其翻译成字符集中字符所构成的字符串形式，存入文献textfile.dat，同步将翻译的成果在屏幕上打印输出。

（5）、打印哈夫曼树的功能模块。

此模块功能為從HuffNode数组中讀入有关的結點信息，以图形的方式将各個結點以及叶子結點的权值和左分支上的0和右分支上的1画出来。

四、试验成果（程序）及分析

1、试验重要代码

typedefstruct/*結點构造体*/

{

stringhfmstr;/*結點内容*/

intweight;/*結點权值*/

intparent;

intlchild;

intrchild;

}HNodeType;

typedefstruct/*编码构造体*/

{

intbit[MAXBIT];

intstart;

}HCodeType;

voidCreate_HuffMTree(HNodeTypeHFMTree[],intn)/*