数据结构实验报告-哈夫曼树（含文件压缩）.doc

北京邮电大学信息与通信工程学院 第 PAGE 1页 北京邮电大学电信工程学院 第 PAGE 1页 2008级数据结构实验报告 实验名称： 实验三——实现哈夫曼树 学生姓名： *** 班 级： ********** 班内序号： ** 学 号： ******** 日 期： 200 1．实验要求 利用二叉树结构实现赫夫曼编/解码器。 基本要求： 初始化(Init)：能够对输入的任意长度的字符串s进行统计，统计每个字符的频度，并建立赫夫曼树 建立编码表(CreateTable)：利用已经建好的赫夫曼树进行编码，并将每个字符的编码输出。 编码(Encoding)：根据编码表对输入的字符串进行编码，并将编码后的字符串输出。 译码(Decoding)：利用已经建好的赫夫曼树对编码后的字符串进行译码，并输出译码结果。 打印(Print)：以直观的方式打印赫夫曼树（选作） 计算输入的字符串编码前和编码后的长度，并进行分析，讨论赫夫曼编码的压缩效果。 测试数据： I love data Structure, I love Computer。I will try my best to study data Structure. 提示： 1、用户界面可以设计为“菜单”方式：能够进行交互。 2、根据输入的字符串中每个字符出现的次数统计频度，对没有出现的 字符一律不用编码。 2. 程序分析 2.1 存储结构 在哈夫曼树编码这个程序中，所有数据用的存储结构都是顺序存储结构，其中包括顺序表和树（三叉树）。 树的存储结构如下：（输入的字符串为 assddddffffffffgggggggggggggggg） 0 1 2 3 4 5 6 7 8 ASCⅡ 97 115 100 102 103 weight 1 2 4 8 16 3 7 15 31 lchild -1 -1 -1 -1 －1 0 2 3 4 rchild －1 －1 －1 －1 －1 1 5 6 7 parent -5 5 -6 -7 -8 6 7 8 0 上结构图中，填充为黄色的部分为写入内存中的部分。每一行的部分为数组的下标，左边部分为所定义的结构的成员。其中有的结点的父节点的下标是一个负数，用来说明该节点是该节点的父节点的左孩子，正数说明的是该节点的父节点的右孩子。父节点这零的节点说明该节点是该哈夫曼树的根节点。画出树的结构如下画所示：（结点中第一个数表示这个字符的ASCⅡ编码，第二个数字表示权值） ^ ^ 3 ^ 7 ^ 15 ^ 31 ^ 16 102 8 97 1 100 4 115 2 8 7 6 5 4 3 2 1 0 0 0 0 0 10 1 1 1 红色箭头表示父指针，黑色箭头表示孩子指针 由上面的图可知，原字符串编码后的二进制编码为 11101111111111011011011010101010101010100000000000000000 字符串中出现的所有的字符的编码如下： a 1110 ； s 1111 ； d 110 ； f 10 ； g 0 2.2 关键算法分析 算法1：哈夫曼树的构造 这个算法分两个部分，每一个部分是对一个字符串中每个字符出现次数的统计，并为每一个出现的字符建立一个叶子节点；第二个部分是以上面的统计的数据为依据建立起一棵哈夫曼树。 问题的规模由两部分组成，一是字符串中总的字符的个数m，二是这个字符串中出现的所有的不同的字符的个数n。 算法的第一部分须要对输入的字符串进行一次遍历，故其时间复杂度为O(m)，为了对每一个字符出现的次数进行计数，程序在开始的时候初始化了一个整形数组 Asc[256] 用256个元素的存储空间来分别计算可能出现的256个字符在字符串中出现的频数，因此这个算法的空间复杂度是一个常数，即O(1)。 算法的第二部分是构造一棵哈夫曼树，这算法首先在之前每个出现过的字符的频数的统计的依据下，为每一个字符建立一个节点。并按每一个叶子节点的权值进行一次从大到小的排序（这里的排序所用的算法是冒泡算法），排序后的结果进行哈夫曼树的构造（实际上就是为数组 hft 填入相关的数据）。现在对审一部分的每一个小的部分进行时间和空间复杂度的分析。对于建立节点这一部分，程序中并没有用到额外的存储空间，只用到之前所申请的511个节点空间的数组，故其空间复杂度为O(1)，遍历了数组Asc，差为出现过的n个字符各自建立起了一个叶子节点，故其时间复杂度为O(n)。 对于冒泡排序这个算法，无论输入的问题规模有多大，其调用的额外的存储空间都是一个常数，易知其空间复杂度为O(1)；对于冒泡算法，其时间复杂度为O(n2)。 最后的一部分就是树的构造，对于一棵有n个叶子节点树，须要进行n-1次的