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

北京邮电大学电信工程学院 第 1 页 2008 级数据结构实验报告 实验名称 实验三 树 学生姓名 班 级 班内序号 学 号 日 期 20013 年 11 月 26 日 1 实验要求 实验目的实验目的 通过选择下面两个题目之一进行实现 掌握如下内容 掌握二叉树基本操作的实现方法 了解赫夫曼树的思想和相关概念 学习使用二叉树解决实际问题的能力 实验内容实验内容 利用二叉树结构实现赫夫曼编 解码器 基本要求 1 初始化 Init 能够对输入的任意长度的字符串 s 进行统计 统计每个字符的频度 并 建立赫夫曼树 2 建立编码表 CreateTable 利用已经建好的赫夫曼树进行编码 并将每个字符的编码输 出 3 编码 Encoding 根据编码表对输入的字符串进行编码 并将编码后的字符串输出 4 译码 Decoding 利用已经建好的赫夫曼树对编码后的字符串进行译码 并输出译码结 果 5 打印 Print 以直观的方式打印赫夫曼树 选作 6 计算输入的字符串编码前和编码后的长度 并进行分析 讨论赫夫曼编码的压缩效果 2 程序分析 哈夫曼树结点的储存结构除了二叉树所有的双亲域 parents 左子树域 lchild 右子树域 rchild 还需要有字符域 word 权重域 weight 编码域 code 其中由于编码是一串由 0 和 1 组成的字符串 所以 code 是一个字符数组 进行哈夫曼编码首先要对用户输入的信息进行统计 将每个字符作为哈夫曼树的叶子结点 统计每个字符出现的次数 频度 作为叶子的权重 统计次数可以根据每个字符不同的 ASCII 码 并根据叶子结点的权重建立一个哈夫曼树 建立每个叶子的编码从根结点开始 规定通往左子树路径记为 0 通往右子树路径记为 1 北京邮电大学电信工程学院 第 2 页 由于编码要求从根结点开始 所以需要前序遍历哈夫曼树 故编码过程是以前序遍历二叉 树为基础的 同时注意递归函数中能否直接对结点的编码域进行操作 编码信息只要遍历字符串中每个字符 从哈夫曼树中找到相应的叶子结点 取得相应的编 码 最后再将所有找到的编码连接起来即可 译码则是将编码串从左到右诸位判别 直到确定一个字符 这可以用生成哈夫曼树的逆过 程实现 由于每个字符的编码各不相同 且编码也是个字符串 所以只要遍历编码串 从 哈夫曼树中找到相应的叶子结点 取得相应的字符再将找到的字符连接起来即可 2 1 存储结构 哈夫曼树结点储存结构 wordweightparentLChildRChild 哈夫曼树顺序存储结构 wordweightlchildparentsrchild 0A35 13 1 1B25 13 1 2C15 14 1 3 040041 4 0753 12 2 2 关键算法分析 1 统计字符的频度 统计字符的频度 自然语言描述 1 取出字符串中的一个字符 2 遍历所有初始化的哈夫曼树结点 3 如果结点中有记录代表的字符且字符等于取出的字符 说明该字符的叶子存在 则将 该结点的权加一 4 如果所有结点均没有记录字符与取出字符一致 说明该字符的叶子不存在 则将结点 的字符记为取出字符 并将权重设为 1 5 重复 1 2 3 4 步骤 如此遍历字符串中的所有字符 伪代码 1 for int i 0 i 字符长度 i 1 1for int j 0 j 字符长度 j 1 1 1 if WordStr i HuffTree j word 1 1 1 1 权重 1 1 1 2 break 1 1 2 否则取字符域为空的结点 1 1 2 1 HuffTree j word WordStr i 1 1 2 2 HuffTree j weight 1 1 1 2 3 叶子数 1 1 2 4 break 结束 时间复杂度 O n2 空间复杂度 S 0 北京邮电大学电信工程学院 第 3 页 2 构造哈夫曼树 构造哈夫曼树 自然语言描述 1 将 n 个权值的叶子结点存放到数组 huffTree 的前 n 个分量中 2 通过统计字符频度的算法给 n 个结点赋权值 3 将数组 huffTree 中出叶子结点外的结点初始化 左右子树 双亲域为 1 权值为 0 字 符编号域为 0 4 不断将两棵子树合并为一棵子树 并将新子树的根节点顺序存放到数组 huffTree 的前 n 个分量的后面 伪代码描述 1 数组 huffTree 初始化 除叶子节点外 所有元素结点左右子树 双亲域为 1 权值为 0 字符编号域为 0 2 进行 n 1 次合并 2 1 在二叉树集合中选取两个权值最小的根结点 其下标分别即为 j1 和 j2 2 2 将二叉树 j1 和 j2 合并为一棵新的二叉树结点 k 时间复杂度 O n 空间复杂度 S 2 3 为每个叶子结点编码 为每个叶子结点编码 自然语言描述 1 初始化一个字符数组 Code 暂存每个叶子结点的编码 2 从叶子结点开始 如果是哈夫曼树的左孩子 则将编码表中的 code 值赋为 0 否则为 1 3 将指针层层上移 重复 2 直到根结点 4 将所得编码逆置 并将编码最后一位赋为 0 5 进行下一叶子结点的编码 算法时间复杂度 O n2 空间复杂度 S 60 4 为信息编码 为信息编码 自然语言描述 1 定义字符串 str1 储存编码 2 遍历信息字符串中的每一个字符 3 对每一个字符 将其与 huffTree 前 n 个叶子结点的 word 域逐个比较 发现相同的则将 该结点的编码串 code 连接到 str1 串的末尾 4 遍历信息字符串结束 输出 str1 算法时间复杂度 O n2 空间复杂度 S 2 5 译码 译码 自然语言描述 1 从编码串 str1 第一个字符开始和数组 huffTree 第一个结点的编码域第一个字符进行比 较 2 若相等 则继续比较两者的后续字符 3 否则 从 str1 第一个字符与 huffTree 第二个节点的编码域第一个字符进行比较 4 重复上述过程 当 huffTree 结点中的字符全部比较完毕则说明本趟匹配成功 输出 huffTree 结点的 word 域值 5 重复上述过程 当 str1 中的字符全部比较完毕 译码结束 本趟匹配开始位置 i 北京邮电大学电信工程学院 第 4 页 主串 CodeStr 回溯 huffTree k 1 huffTree k j 回溯 算法时间复杂度 O n2 1 程序运行结果 测试主函数流程 测试条件 问题规模 n 的数量级为 1 测试内容 I love data Structure I love Computer I will try my best to study data Structure 开始 测试的字符串为 I love data structure I love computer I will try my best to study data structure 建立哈夫曼树 建立编码表 编码 解码 输出长度 比较压缩效果 结束 北京邮电大学电信工程学院 第 5 页 测试结论 测试的功能有 建立哈夫曼树 对每个字符进行编码 对信息字符串进行编码 对编码串进行译码 各项功能均能正常运行 界面的跳转也能实现 编码前信息总长度为 400bits 编码后的长度为 320bits 由于哈夫曼编码采用不 等长编码 有效缩短了编码长度 节省了空间 2 总结 调试时出现的问题及解决的方法调试时出现的问题及解决的方法 1 字符串在函数中的存储 在给字符进行编码时 由于对于字符串储存的理解不清楚 以致于在生成解决方案是出现 了 屯屯屯 的字样 经过查阅相关资料得知 是因为字符串末尾没有加 0 所致 2 字符串编码的位数 由于对于字符串存储位数的不够清晰 走入了以往的经验错误 在储存编码时总是少一位 经检查发现是在逆置时数组的个数没有搞清楚 3 字符串的输入输出问题 最初字符串是用 cin 输入 后来发现此种方式只适用于单个次 遇到 0 即停止 后来调用 了 cin getline 才有效的解决了这个问题 心得体会心得体会 哈夫曼树又称做最优二叉树 它是 n 个带权叶子结点构成的所有二叉树中 带权路径 长度 WPL 最小的二叉树 在 n 个带权叶子结点所构成的二叉树中 满二叉树或完全二叉 树不一定是最优二叉树 权值越大的结点离树根越近的二叉树才是最优二叉树 哈夫曼树 是根据字符出现的概率来构造平均长度最短的编码 它是一种变长的编码 在编码中 若 各码字长度严格按照码字所对应符号出现概率的大小的逆序排列 则编码的平均长度是最 小的 再做本实验的过程中 也出现了很多问题 主要是要编写程序 因为程序比较长 再 编写的过程中 经常会出现一些错误 比如 把一些字母编写错误 没区分大小写 漏句 符号写错或漏写等等 我想这些都是一些比较低级的错误 主要是自己对程序还不是很熟 悉 再做实验的时候还不够细心所导致的吧 这些都是要求我们再做实验的过程中不断总 结经验教训 加深对程序的了解和喜爱 不要粗心大意 通过本实验我也总结了一些经验 那就是再修改程序的时候 不要死转牛角尖 要从大处着手 逐步深入 逐个修改 还要 用联系的观点来看程序 有时候一个地方错了 会引起很多个错误 而显示错误的句子本 身可能会没有错误 只是与之相关联的一些语句发生了错误而引起的错误 这时我们就不 要死盯着原来的地方不放 而应该找出与之相关联的语句 哈夫曼树的应用非常广泛 在通信中 采用 0 1 的不同排列来表示不同的字符 而哈 夫曼树在数据编码中的应用 若每个字符出现的频率相同 则可以采用等长的二进制编码 若频率不同 则可以采用不等长的二进编码 频率较大的采用位数较少的编码 频率较小 的字符采用位数较多的编码 这样可以使字符的整体编码长度最小 哈夫曼编码就是一种 不等长的二进制编码 且哈夫曼树是一种最优二叉树 它的编码也是一种最优编码 在哈 夫曼树中 规定往左编码为 0 往右编码为 1 则得到叶子结点编码为