数据结构C语言哈夫曼编码译码

哈夫曼的编码与解码 1 题题 目 目 哈夫曼树编码译码哈夫曼树编码译码 院院 系 系 信息工程系信息工程系 专专 业 业 计算机科学与技术 网络方向 计算机科学与技术 网络方向 姓姓 名 名 梁展荣梁展荣 学学 号 号 11512201151151220115 指导教师 指导教师 赵莹莹赵莹莹 刘欣刘欣 日日 期 期 20132013 年年 7 7 月月 3 3 日日 桂林电子科技大学信息科技学院桂林电子科技大学信息科技学院 实实训训报报告告 哈夫曼的编码与解码 2 目目 录录 一 设计思想 1 1 1 建立哈夫曼树的思想 1 1 2 建立哈夫曼编码表 2 1 3 对文件进行编码 2 1 4 对文件进行解码 2 二 算法流程图 3 三 运行结果 8 四 遇到的问题及解决 10 五 心得体会 13 哈夫曼的编码与解码 3 一 设计思想一 设计思想 要完成哈夫曼的编码和解码需要首先建立哈夫曼树 之后对所 有字符根据权重进行编码 最后再对文件内容进行编码和解码 1 1 建立哈夫曼树的思想 首先定义适合哈夫曼树的节点类型 需要定义的有当前节点的 字符 当前节点的左子 右子和父亲指针 在建立哈夫曼树之前还 需要对出现的字符和权重进行统计和记录 并且定义一个可以筛选 出最小权重的函数 初始化树节点之后开始建立哈夫曼树 先在所有可能出现的字 符中筛选出当前权重最小的两个字符 将这两个字符分别作为新节 点的左子和右子建立一个小的二叉树 并将两个字符的权重之和赋 值给新节点 将新二叉树放入筛选字符中 再将筛选过的两个字符 从筛选列表中淘汰掉 依次对列表中剩下的字符进行权重最小的筛 选 直到根节点 如果编码表共有 N 个字符 则 2 N 1 就为最终根 节点 为止 也就是当筛选列表为空的时候 哈夫曼树即建立完成 对于哈夫曼编码树来说 由于哈夫曼编码是前缀码 所以所有 要编码的字符最终都将是这颗树的叶子节点 而其它节点并没有真 正的字符意义 即当哈夫曼编码树建立之后 对树的所有叶子节点 进行打印可知道是否有字符遗漏或多余 哈夫曼的编码与解码 4 1 2 建立哈夫曼编码表 建立编码表时要根据每个出现的字符的权重对建立的哈夫曼树 的每个叶子节点进行编码 编码时要从叶子节点出发向根节点进行 逆向编码 判断如果当前节点为左子则对其编码 0 如果当前节 点为右子则对其编码 1 以此类推进行编码直到根节点为止 此 时的编码是逆向的 所以需要将码值逆向存储 依次对每一个叶子 节点进行编码操作 即可得到当前哈夫曼树的编码表 对于码值的逆向存储可以使用栈结构 先将一个码的每一步编 码存入栈 再在一个码结束后出栈至空 当然也可以定义一个字符 型数组 将值从后向前存入数组 再将数组有值部分粘贴到新的数 组中进行存储 本次采用了后者 因为个人认为为此一步操作建立 栈结构不划算 而且前一个设计也已经熟练掌握了栈的方法 此处 进行新的尝试会更好 1 3 对文件进行编码 首先需要建立一个原始文件 在文件中输入需要编码的内容 之后将文件打开 将其中的内容存储到字符串中以便程序编码调用 开始对需要编码的字符进行编码 将字符逐一读取与刚刚建立的编 码表中的每个叶子节点代表的字符进行比较 找出相同的对象 并 将当前节点的编码打印到屏幕 并将编码存入到新建的密码文件当 中 哈夫曼的编码与解码 5 1 4 对文件进行解码 先打开密码文件 将之前编码后得到的密文内容存储到字符串 中以便解码调用 开始对密文的字符串进行解码 树索引从根节点 开始走 当密文中的当前字符是 0 的时候 则索引走向左子节点 当是 1 的时候 则走向右子节点 以此类推 一直走到叶子节点 为止 则当前叶子节点所代表的字符即为前一段密文的解码结果 再对下一个字符依次从根节点开始解码 如此循环对每一段密文进 行解码直到解码结束 将解码打印到屏幕 并将解码结果存入到新 的解码文件当中 在解码之前 还应该先确认之前是否建立了哈夫曼树并且是否 构建了编码表 不过由于本次将 a 到 z 都进行了编码 所以 此步省略了 因为编码表是唯一的 需要的时候可以在 Encoder 函 数中先进行判定 将编码和解码写在了一起 可以在运行时进行选择调用 二 算法流程图二 算法流程图 第一步 建立哈夫曼树 哈夫曼的编码与解码 6 图 1 建立哈夫曼树的算法流程图 第二步 构建哈夫曼编码表 哈夫曼的编码与解码 7 图 2 构建哈夫曼编码表的算法流程图 第三步 编码 哈夫曼的编码与解码 8 图 3 编码算法流程图 第四步 解码 哈夫曼的编码与解码 9 图 4 解码算法流程图 哈夫曼的编码与解码 10 四 运行结果四 运行结果 原文文件 图 5 中缀转后缀运行结果图 编码图 图 6 编码图 密文文件 哈夫曼的编码与解码 11 图 7 密文文件图 解码图 图 8 解码图 译文文件 哈夫曼的编码与解码 12 图 9 译文文件图 整体运行图 图 10 编码解码整体运行图 五 遇到的问题及解决五 遇到的问题及解决 这部分我主要遇到了如下两个问题 其内容与解决方法如下所 列 第一个问题是权重的筛选部分出现了错误 解决办法 一开始对于筛选最小权重的代码编写如下 void SelectMin HFMT T int i int p1 int p2 int j min 999 for j 0 jT j weight 哈夫曼的编码与解码 13 min T j weight p1 j min 999 for j 0 jT j weight p2 j 因为权重中最大的就是字符 e 的权重 103 所以为初始值 min 赋值时觉得 999 就已经是无限大了 但是后来发现编码不知确 就 开始思考是什么问题 发现每次筛选都将会把最小的两个权重进行 相加 所以很快就会超过 999 编码自然就出现了问题 所以后来 将 min 定义成了 long 型 并赋值 999999 问题就解决了 第二个问题是生成编码表的时候如何将逆向编码正向存储 哈夫曼的编码与解码 14 解决办法 对于求编码的时候 由于是从叶子节点向根顺次而求 所以编 码结果将是逆向的 一开始想到的办法是利用栈的结构 将编码依 次存入栈中 再在一个字符编码结束时将栈倒空 这样就可以将编 码正向存储了 但是又在考虑如果不用栈时候也可以做到 后来想到了 strcpy 函数对字符数组进行链接 所以就可以定义 一个数组 从后向前存储编码 再在一个字符编码结束时将这个数 组有值的重新存入新数组中 即可以成为正向编码了 最终实现编 码如下 HFCode hfEn HFMT T int i f c start HFCode hc char cd hc char malloc N 1 sizeof char cd char malloc N sizeof char cd N 1 0 for i 0 i N i start N 1 for c i f T i parent f 1 c f f T f parent 哈夫曼的编码与解码 15 if T f left c cd start 0 else cd start 1 hc i char malloc N start sizeof char strcpy hc i return hc 六 心得体会六 心得体会 通过对本次的编写 使我掌握了哈夫曼编码的特点 存储方法和 基本原理 培养了我运用 C 语言正确编写程序以及调试程序的能力 哈夫曼编码的结构取决于可能出现的字符的个数和其所对应的权值 权值大的编码短 权值小的编码长 这样的结构会利用比较小的空 间存储数据 而且 利用树的结构对其编码和对其解码 也是比较 规格话 比较方便的 本次编程还运用了结构体 便捷的对树节点 哈夫曼的编码与解码 16 和树以及编码表进行定义和调用 并且了解到当求解一个算法时 不是