数据结构-实验三-题目二：哈夫曼树

1、2021 级数据结构实验报告实验名称：实验三 树学生：班级：班序号：学号：日期：20013 年 11 月 26 日1实验要求实验目的通过选择下面两个题目之一进展实现，掌握如下容：掌握二叉树根本操作的实现方法了解赫夫曼树的思想和相关概念学习使用二叉树解决实际问题的能力实验容利用二叉树结构实现赫夫曼编 / 解码器。根本要求：1. 初始化 (Init) ：能够对输入的任意长度的字符串 s 进展统计， 统计每个字符的频度， 并 建立赫夫曼树2. 建立编码表 (CreateTable) ：利用已经建好的赫夫曼树进展编码，并将每个字符的编码 输出。3. 编码 (Encoding) ：根据编码表对输入的字符

2、串进展编码，并将编码后的字符串输出。4. 译码 (Decoding) ：利用已经建好的赫夫曼树对编码后的字符串进展译码， 并输出译码结 果。5. 打印 (Print) ：以直观的方式打印赫夫曼树选作6. 计算输入的字符串编码前和编码后的长度，并进展分析，讨论赫夫曼编码的压缩效果。2. 程序分析哈夫曼树结点的储存结构除了二叉树所有的双亲域 parents ，左子树域 lchild ，右子树域 rchild 。还需要有字符域 word，权重域weight，编码域code。其中由于编码是一串由0和1 组成的字符串，所以 code 是一个字符数组。进展哈夫曼编码首先要对用户输入的信息进展统计，将每个字

3、符作为哈夫曼树的叶子结点。 统计每个字符出现的次数 频度作为叶子的权重， 统计次数可以根据每个字符不同的 ASCII 码。并根据叶子结点的权重建立一个哈夫曼树。建立每个叶子的编码从根结点开始，规定通往左子树路径记为0，通往右子树路径记为 1.由于编码要求从根结点开始， 所以需要前序遍历哈夫曼树， 故编码过程是以前序遍历二叉树为根底的。同时注意递归函数中能否直接对结点的编码域进展操作。编码信息只要遍历字符串中每个字符，从哈夫曼树中找到相应的叶子结点，取得相应的编码。最后再将所有找到的编码连接起来即可。译码那么是将编码串从左到右诸位判别，直到确定一个字符。 这可以用生成哈夫曼树的逆过程实现。由于每

4、个字符的编码各不一样，且编码也是个字符串，所以只要遍历编码串，从哈 夫曼树中找到相应的叶子结点，取得相应的字符再将找到的字符连接起来即可。2.1存储结构哈夫曼树结点储存结构wordweightpare ntLChildRChild哈夫曼树顺序存储结构wordweightlchildpare ntsrchild0A35-13-11B25-13-12C15-14-1304004140753-1222关键算法分析1、统计字符的频度自然语言描述：1取出字符串中的一个字符2遍历所有初始化的哈夫曼树结点3如果结点中有记录代表的字符且字符等于取出的字符，说明该字符的叶子存在，那么将该结点的权加一。4如果所有

5、结点均没有记录字符与取出字符一致，说明该字符的叶子不存在，那么将结点的字符记为取出字符，并将权重设为1.5重复1 2 3 4步骤，如此遍历字符串中的所有字符。伪代码：1. forint i=O;i<字符长度；i+1.1for int j=O;j<字符长度;j+1.1.1 if WordStri=HuffTreej.word1.1.1.1 权重 +1.1.1.2 break;否那么取字符域为空的结点1.1.2.1 HuffTreej.word=WordStri;1.1.2.2 HuffTreej.weight=1;1.1.2.3 叶子数 +;1.1.2.4 break;完毕时间复杂度

6、0n2,空间复杂度S02、构造哈夫曼树自然语言描述：1) 将n个权值的叶子结点存放到数组huffTree的前n个分量中2) 通过统计字符频度的算法给 n个结点赋权值-1 ;权值为0；huffTree 的前3) 将数组huffTree中出叶子结点外的结点初始化：左右子树、双亲域为 字符编号域为0。4) 不断将两棵子树合并为一棵子树，并将新子树的根节点顺序存放到数组 n个分量的后面。伪代码描述：双亲域为-1 ；权值为0；1. 数组huffTree初始化，除叶子节点外，所有元素结点左右子树、 字符编号域为0。2. 进展n-1次合并2.1在二叉树集合中选取两个权值最小的根结点，其下标分别即为j1和j2

7、2.2将二叉树j1和j2合并为一棵新的二叉树结点 k 时间复杂度0(n)，空间复杂度S(2)3、为每个叶子结点编码自然语言描述：1) 初始化一个字符数组 Code暂存每个叶子结点的编码。2) 从叶子结点开始，如果是哈夫曼树的左孩子，那么将编码表中的code值赋为0,否那么为13) 将指针层层上移，重复2直到根结点4) 将所得编码逆置，并将编码最后一位赋为0'5) 进展下一叶子结点的编码算法时间复杂度 O(n2)，空间复杂度S(60)4、为信息编码自然语言描述：1) 定义字符串str1储存编码2) 遍历信息字符串中的每一个字符3) 对每一个字符，将其与huffTree前n个叶子结点的wo

8、rd域逐个比较，发现一样的那么将该结点的编码串code连接到str1串的末尾。4) 遍历信息字符串完毕，输出 str1算法时间复杂度 O(n2)，空间复杂度S(2)5、译码自然语言描述：1) 从编码串str1第一个字符开始和数组 huffTree第一个结点的编码域第一个字符进展比 拟。2) 假设相等，那么继续比较两者的后续字符3) 否那么，从str1第一个字符与huffTree第二个节点的编码域第一个字符进展比较。4) 重复上述过程，当 huffTree结点中的字符全部比较完毕那么说明本趟匹配成功，输出 huffTree结点的word域值。5) 重复上述过程，当str1中的字符全部比较完毕，译

9、码完毕。本趟匹配开始位置i主串 CodeStr2 一回溯算法时间复杂度0(n2)1.程序运行结果测试主函数流程：测试条件：问题规模n的数量级为1。测试容：I love data Structure, I love Computer, I will try my best to study data Structure.测试结论：测试的功能有：建立哈夫曼树、对每个字符进展编码、对信息字符串进展编码、 对编码串进展译码。各项功能均能正常运行。界面的跳转也能实现。 编码前信息总长度为 400bits ，编码后的长度为 320bits 。由于哈夫曼编码采用 不等长编码，有效缩短了编码长度，节省了空间。

10、2. 总结调试时出现的问题与解决的方法 1 字符串在函数中的存储 在给字符进展编码时， 由于对于字符串储存的理解不清楚， 以致于在生成解决方案是出现了 “屯屯屯的字样，经过查阅相关资料得知，是因为字符串末尾没有加'0'所致。 2 字符串编码的位数 由于对于字符串存储位数的不够清晰，走入了以往的经验错误，在储存编码时总是少一位， 经检查发现是在逆置时数组的个数没有搞清楚 3 字符串的输入输出问题 最初字符串是用 cin 输入， 后来发现此种方式只适用于单个次， 遇到' 0'即停止， 后来调 用了 cin.getline 才有效的解决了这个问题 心得体会哈夫曼树又称

11、做最优二叉树， 它是 n 个带权叶子结点构成的所有二叉树中， 带权路径长 度WPL最小的二叉树。在n个带权叶子结点所构成的二叉树中，满二叉树或完全二叉树不一定是最优二叉树。 权值越大的结点离树根越近的二叉树才是最优二叉树。哈夫曼树是根据字符出现的概率来构造平均长度最短的编码。 它是一种变长的编码。 在编码中， 假设各码字长 度严格按照码字所对应符号出现概率的大小的逆序排列，那么编码的平均长度是最小的。再做本实验的过程中，也出现了很多问题，主要是要编写程序，因为程序比较长，再编 写的过程中，经常会出现一些错误，比方：把一些字母编写错误，没区分大小写，漏句，符 号写错或漏写等等。我想这些都是一些比

12、较低级的错误，主要是自己对程序还不是很熟悉， 再做实验的时候还不够细心所导致的吧。 这些都是要求我们再做实验的过程中不断总结经验 教训，加深对程序的了解和喜爱，不要粗心大意。通过本实验我也总结了一些经验，那就是 再修改程序的时候，不要死转牛角尖，要从大处着手，逐步深入，逐个修改，还要用联系的 观点来看程序， 有时候一个地方错了， 会引起很多个错误， 而显示错误的句子本身可能会没 有错误， 只是与之相关联的一些语句发生了错误而引起的错误。 这时我们就不要死盯着原来 的地方不放，而应该找出与之相关联的语句。哈夫曼树的应用非常广泛， 在通信中， 采用 0,1 的不同排列来表示不同的字符， 而哈夫 曼树在数据编码中的应用， 假设每个字符出现的频率一样， 那么可以采用等长的二进制编码， 假设频率不同， 那么可以采用不等长的二进编码， 频率较大的采用位数较少的编码，频率较小的字符采用位数较多的编码， 这样可以使字符的整体编码长度最小， 哈夫曼编码就是一种 不等长的二进制编码， 且哈夫曼树是一种最优二叉树， 它的编码也是一种最优编码，在哈夫曼树中，规定往左编码为 0，往右编码为 1，那么得到叶子结点编