北京邮电大学信息与通信工程学院
数据结构实验报告
实验名称： 实验4——题目4——哈夫曼树 学生姓名： 班 级： 班内序号： 学 号：
日 期： 2017年1月6日
1． 实验要求
利用二叉树结构实现哈夫曼编/解码器。 基本要求：
1、 初始化(Init)：能够对输入的任意长度的字符串s进行统计，统计每个字符的频度，并建立赫夫曼树
2、 建立编码表(CreateTable)：利用已经建好的赫夫曼树进行编码，并将每个字符的编码输出。
3、 编码(Encoding)：根据编码表对输入的字符串进行编码，并将编码后的字符串输出。 4、 译码(Decoding)：利用已经建好的赫夫曼树对编码后的字符串进行译码，并输出译码结果。
5、 打印(Print)：以直观的方式打印赫夫曼树（选作）
6、 计算输入的字符串编码前和编码后的长度，并进行分析，讨论赫夫曼编码的压缩效果。
2. 程序分析
2.1 存储结构
本实验的存储结构为哈夫曼树与哈夫曼编码表
哈夫曼树： 存储结构：
struct HNode//哈夫曼树的结点结构
{
第1页
北京邮电大学信息与通信工程学院
};
int weight;//结点权值 int parent;//双亲指针 int LChild;//左孩子指针 int RChild;//右孩子指针
哈夫曼编码表：
struct HCode //编码表的结点结构
{ };
char data;//字符
char code[10];//编码 int k;//码长
存储结构：
2.2 关键算法分析
一、初始化：
第2页
北京邮电大学信息与通信工程学院
步骤：
1、 设立数组，记录每一个字符出现的次数与字符对应的ASCII码 2、 以字符不是回车或换行遍历输入的字符数组
3、 将存储出现次数大于0的字符存储进叶子节点数组 4、 相对应的，存储叶子结点的数据域字符出现的次数。
时间复杂度：O（n） 空间复杂度：O（n）
二、创建哈夫曼树 步骤：
1、 创建2n-1个数节点
2、 将权值数组依次赋值进0到n-1的权值节点中
3、 从0到i-1（最开始等于n-1）选择两个权值最小的节点x、y，将其连接为i节点的左
右孩子，改变x、y的双亲指针为i节点 4、 I++，循环步骤4直到2n-1
时间复杂度：O（n^2） 空间复杂度 O（n）
三、创建哈夫曼编码表 步骤：
1、 创建n个编码表节点
2、 依次将叶子节点的字符放入编码表节点数据域中
3、 对每个编码表对应的树结点，向根节点开始回溯（为父节点的左孩子编码值为0，右孩
子为1，不断上移，直到根节点） 4、 进行倒置
时间复杂度O（n） 空间复杂度 O（n） 四、编码 步骤：
1、 新建编码数组
2、 从源码第一个字符开始在编码表中寻找到相应字符后将编码复制进编码数组 3、 计算压缩比
时间复杂度O（n+e） n为源码 e为编码数组长度 空间复杂度O（n） 五、解码 步骤：
1、 从根节点开始，按照编码串寻找（0为左子树，1为右子树）
第3页
北京邮电大学信息与通信工程学院
2、 直到该节点无子树，将该节点（也就是叶子节点）字符放入解码串中 3、 重复步骤1、2直到编码串结束
时间复杂度O（n） n为编码串长度 空间复杂度O（e） e为原串长度 六、打印哈夫曼树 步骤：
1、 从根节点开始 第m层前方空m个格
2、 叶子结点先输出数据域再在下一行输出权值 3、 重复输出，递归调用，直到叶子。
时间复杂度O（n） 空间复杂度O（n）
2.3 其他
3. 程序运行结果
运行图解
第4页
北京邮电大学信息与通信工程学院
4. 总结
本次实验题目为哈夫曼树。
本次实验是在期末考试后进行了，经过了一学期的学习与期末复习，感觉对于数据结构的认识深刻了很多。
哈夫曼树是在学习第五章树的时候最后讲到的数据结构。相比于普通的树来说，海夫曼树的性质更为优良，首先它有权值，其次可以通过节点中编码域进行访问（例如0为左子树，1为右子树），最重要的是，哈夫曼树可以做到权值和最小。这一优良的性质使得其可以用于数据压缩，将权值看作字符出现的次数，而路径长度则是编码的路径。这样可以达到一种理想式的压缩效果。但是，如果压缩的字符串比较多的情况下，每个字符的哈夫曼编码会增加（因为树的层数在增加），这样压缩比会下降。虽然这个下降的趋势是逐渐减小的（因为每层具有的树节点的数量也在不断地增加）
本次编码的过程中一开始参考了教材上的代码，一些函数的实现是原创的。但是由于对于上界的理解不到位（n个叶子节点则一共有2n-1个节点）所以造成了原创代码的错误。后来在参考了教学辅导书后，发现了错误，更改了主函数与类函数的声明后，又加上了一些选作内容的代码，最后终于完成了本次实验。在完成之后还进行了一个有趣的测试：
在输入测试字符串后，发现随着字符串中字符种类的增加，压缩比在下降。最开始的只有两个字符的时候，压缩比（原串码长/编码串长）高达8。后来随着字符串种类的增加，压缩比下降明显，但是下降趋势是趋缓的。这就如我在前文中提到了一样，和哈夫曼树的结构有关。在之后的一次测试中，我输入了键盘上所有的字符，压缩比则跌到了1.2左右。这和相比最开始的压缩比已经很小了，此时压缩效果已经比较差了。这个测试说明，哈夫曼树编码的压缩效率很有限，无法适应于一般的编码情况。在压缩效率如此有限的情况下，却要额外付出时间和空间成本，并不是一种很好的压缩方法。
在浏览知乎的时候发现了一个很有意思的说法，要解决问题比如剔牙，只用基本的编程语言相当于用手抠，而数据结构则相当于用牙签，更加高效（各种数据结构留下了接口，使得操作变得多样化，比如二向链表可以极其方便的访问前驱后后继，普通的链表只能遍历），更加卫生（可以通过各种方式检测溢出，超限等等）。本学期的学习使我了解了很多的编程知识，比如一些基本的算法分析方法（时间复杂度，空间复杂度），很多的数据结构（线性表，栈串队列，树，图，多维数组），以及数据结构的使用方法（先定义存储结构，之后定义数据结构类）。本学期的学习也算是一次愉快的经历，虽然实验中的各种BUG不断，但是课程目标整体上还是脱离了普通的编程细节，而追求对算法和数据结构的宏观理解。在实验过程中，大量在网站上（CSDN，coDing）查找资料也让我们体验了一下程序员的生活。程序员并非是人形的编程语言字典，他对于算法和程序有一个整体的把握，同时直到各种数据结构的使用，通过合理应用各种已有的模板解决问题。
第5页
北邮数据结构 实验报告四——哈夫曼树
