数据结构课程设计实验报告哈夫曼树的应用(2)

三、详细设计

功能函数模块划分 void main() void printhead()

void printree(HuffmanTree HT,int w) //打印赫夫曼树

void coprint(HuffmanTree start,HuffmanTree HT)//打印代码文件 void printcode() //打印代码 void decode() //完成译码功能 void encode() //完成编码功能 void inputcode()

void init()

void HuffmanCoding(HuffmanTree &HT,HuffmanCode &HC,int *w,int n) void select(HuffmanTree t,int i,int &s1,int &s2) int min(HuffmanTree t,int i)//找两个最小的权值

（1）哈夫曼编码：首先定义函数，找出全部权值中最小的两个，然后定义一个变量，使他始终成为最小的那个。再将两个函数最为叶子结点，并得到一个父亲节点，此父亲节点的权值为其叶子节点的权值之和。并将此父亲节点的权值与其余权值进行比较，重新选出两个最小的权值，再进行上述步骤，直到所有权值形成了一颗二叉树，而此二叉树就是我们所说的最优二叉树，即哈夫曼树。

以上为哈夫曼树的建立过程，下面为哈夫曼编码的过程，从叶子节点出发，若此叶子节点为其父亲节点的左孩子，则将其编码为0，若为右孩子，则将其编码为1，然后为其父亲节点编码，若为祖先的左孩子，则变为0，为右孩子则为1，依次向上一层进行遍历，直到遍历到根节点，停止编码。

（2）译码：对于已经建好的哈夫曼树，要对其进行译码，首先从根出发如果编码为0，则往左孩子遍历，如果编码为1，则往右孩子遍历，直到遍历到叶子节点，便求得该子串相应的字符。

（3）初始化哈夫曼链表:首先输入结点个数，再将字符及权值输入，调用编码函数，得到每个字符编码并将其输出。最后将哈夫曼编码写入文件。

（4）完成编码功能：打开目录下文件tobetran.txt，读取里面的字符，对其进行编码后，将编码写入目录下的codefile.txt中。

（5）完成译码功能：打开根目录下codefile.txt文件，读取里面的编码，对其中的编码进行译码，并将得到的内容写入根目录下的文件txtfile.txt中。 （6）打印编码 （7）打印哈夫曼树

6

四、调试分析和测试结果

（一）初始化哈夫曼链表

7

（二）编码字符

（三）编码

8

（四）译码

（五）打印编码

（六）打印哈夫曼函数

9

五、心得体会与总结

对于本次课程设计，主要是需要掌握哈夫曼树建立、哈夫曼编码以及哈夫曼译码的算法。并能将其熟练应用于编译码器的完成。经过这次的课程设计，使我们更加了解了数据结构，也更深入地了解了哈夫曼编码与译码算法，课程设计的题目比我们平常的实验内容要难，完成它不仅需要有厚实的语言基础，而且还要熟练掌握哈夫曼编码与译码的算法，另外对于文件的基本操作也需要熟悉。

通过数据结构课程设计，我的C++语言水平有了比较大的提高其中。C++语言关于类的操作理解的比以前深刻不少。另外是数据结构方面的提高对哈夫曼树的构造及哈夫曼码方面也有不少的提高。 在项目中也出现了很多的问题,最大的问题就是对程序设计框架结构的不了解,在实现代码与功能的连接时经常会出现各种不同的错误,

以致拖了整个设计的后腿。课程设计中，既回顾了很多以前的东西，也发现了很多的问题以前都没遇见过的，收获很大。 通过本次数据结构的课程设计，我学习了很多在上课没懂的知识，并对求哈夫曼树及哈夫曼编码/译码的算法有了更加深刻的了解，更巩固了课堂中学习有关于哈夫曼编码的知识。 此次哈夫曼树的应用系统的设计让自己对数据结构的了解更深入。

六、参考文献

《C++面向对象程序设计教程》（第三版） 陈维兴 林小茶编著 清华大学出版社 《数据结构》（C语言版）严蔚民 吴伟民编著 清华大学出版社

10