哈弗曼编码,C实现二叉树的图形化输出,已经界面.pdfVIP

软件工程学院

程序设计实践（下）实验

报告

题目：哈夫曼编码/译码器

姓名：张祺

学号

班级：软件工程3班

一、问题解析（对问题的分析、解题思路与解题方法）

问题主要分为三部分，分别是文件的操作、界面的设计、文件

的压缩，其中界面的设计和文件的压缩又是基于哈弗曼编码的，因此，

构造哈弗曼树和获取哈弗曼编码是程序的关键。

1、文件的操作：

程序中文件的操作主要是文件的读和写，关于这点，基本上没

有遇到什么问题。

2、界面设计

前面已经提到，界面设计是基于哈弗曼树和哈弗曼树的小时，

我分到了这一块，下面做介绍。

由于哈弗曼树是正则二叉树，即对于每个结点，要么其左右孩子都存

在，要么都不存在。但对于树形结构来说，其变化多端，每一行的结

点数不确定，虽然第二层（第一层只有根结点）和最后一层结点数没

有任何确定的关系，但他们之间却有相互制约关系，即底层结点的个

数关系着上层（尤其是第二、三层）结点之间的距离，这也是最难把

握的地方。

最初，我用矩阵保存同一层结点之间的关系，但后来发现，兄弟结点

的关系容易获得，但如果两结点不是兄弟结点而是堂兄结点时，这种

关系就比较难找了，再不理想一点，如果两结点在的根结点父节点来

自不同的结点，这种关系就更难确定了。

然后，我又想想到了从根结点出发仿照先序遍历的原理逐个打印

结点的信息。很快，我发现，这种方法也是不行的，原因在于在先序

遍历时可也借助栈或者递归栈来储存后面要访问的元素。但是想要找

到这个元素的具体位置比较难，所以这种方法也很快被否认。

一直找不到可行的办法，想过用打表，也想过放弃。但是实在不想，

一个原因是这是我的任务，如果我放弃或者做的不够完美，这将会影

响我们组所有同学的成绩。另一个原因就是我一直认为，只要是能想

的到的，就能用代码实现，这也是编程的精髓。无奈之下，我开始查

找资料，突然，一张满二叉树的图片（其实是一张家谱图）给了我灵

感。我为什么要根据结点选位置呢？完全可也根据位置确定这点的结

点啊……所以我的最初构想是先打印出一个树形结构，然后根据每个

结点的信息，将其输出到指定的位置，最后我就是用这种方法做到的。

3、构造哈弗曼树、获取哈弗曼编码

构造哈弗曼树的关键在于每次将权值最小的两个结点合并成一个

新结点，如此循环，直到只剩一个结点。在获取编码时，从每一个叶

子结点出发，访问哈弗曼树的根结点，所走过的路径刚好和编码相反。

二、任务分工及进度计划

我们组的成员还有王倩、求春磊、章力挺。最初分工时，王倩负

责文件的读写操作；求春磊负责文件的编码压缩这一块；章力挺负责

构造哈弗曼树、获取哈弗曼编码这一块；我负责疏导图形化输出、界

面这一块。

总体来说，小组的进度比较慢，原因在于第一个程序还没写好。

而且我的任务在中间，只有有了哈弗曼编码才能进行树形结构的输

出，所以在开始时，前面的问题我也解决了。下面谈谈我的见解。

文件的读写基本上没有什么大的问题，在统计字符频率时，我统

计了128个常见字符，用了点小算法，效率比较高。在构造哈弗曼树

时出现了瓶颈。究其原因，主要是以前没有接触过哈弗曼树，只有老

师在上课时提到过，所以，面对一个新问题，首先需要时间去熟悉。

等到哈弗曼树构造完成，获取编码也就相应比较简单了

三、数据结构选择、算法设计

前面已经提到，这个程序我基本上全都做了，现在就出现的问题

分析。

1、统计字符频率

常见的字符有128个，如果检索一个一个判断，那样的代价

会很大的。由于128个字符分别对应1~~128的ASCII码值，所

以可以定义一个128单元的数组，用字符代替下标。这样一来，

对于每一个字符，其计算频率其出现一次，下标为该字符的元素

递增1。这样可以高效的简单的统计每一个字符出现的频率。

2、构造哈弗曼树、获取哈弗曼编码

在问题分析中叶提到，构造哈弗曼树的关键是每次将两个

权值最小的结点合并成一个新的结点。教材上采用0号元素不用，

通过判断结点的父结点是否为0确定该结点是否要被计算。在我

的计算中，我用0号结点，而且另外开辟了一个存放结点权值的

副本数组，这