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

《数据结构c语言哈夫曼编码译码》由会员上传分享，免费在线阅读，更多相关内容在应用文档-天天文库。

1、哈夫曼的编码与解码实训报告题目：哈夫曼树编码译码院系：信息工程系专业：计算机科学与技术（网络方向）姓名：梁展荣学号：1151220115指导教师：赵莹莹刘欣日期：2013年7月3日桂林电子科技大学信息科技学院-16-哈夫曼的编码与解码目录一、设计思想11.1建立哈夫曼树的思想11.2建立哈夫曼编码表21.3对文件进行编码21.4对文件进行解码2二、算法流程图3三、运行结果8四、遇到的问题及解决10五、心得体会13-16-哈夫曼的编码与解码一、设计思想要完成哈夫曼的编码和解码需要首先建立哈夫曼树，之

2、后对所有字符根据权重进行编码，最后再对文件内容进行编码和解码。1.1建立哈夫曼树的思想。首先定义适合哈夫曼树的节点类型，需要定义的有当前节点的字符，当前节点的左子、右子和父亲指针。在建立哈夫曼树之前还需要对出现的字符和权重进行统计和记录，并且定义一个可以筛选出最小权重的函数。初始化树节点之后开始建立哈夫曼树。先在所有可能出现的字符中筛选出当前权重最小的两个字符，将这两个字符分别作为新节点的左子和右子建立一个小的二叉树，并将两个字符的权重之和赋值给新节点，将新二叉树放入筛选字符中，再将筛选过的两个字

3、符从筛选列表中淘汰掉。依次对列表中剩下的字符进行权重最小的筛选，直到根节点（如果编码表共有N个字符，则2*N-1就为最终根节点）为止，也就是当筛选列表为空的时候，哈夫曼树即建立完成。对于哈夫曼编码树来说，由于哈夫曼编码是前缀码，所以所有要编码的字符最终都将是这颗树的叶子节点，而其它节点并没有真正的字符意义。即当哈夫曼编码树建立之后，对树的所有叶子节点进行打印可知道是否有字符遗漏或多余。-16-哈夫曼的编码与解码1.2建立哈夫曼编码表。建立编码表时要根据每个出现的字符的权重对建立的哈夫曼树的每个叶子

4、节点进行编码。编码时要从叶子节点出发向根节点进行逆向编码。判断如果当前节点为左子则对其编码‘0’，如果当前节点为右子则对其编码‘1’。以此类推进行编码直到根节点为止。此时的编码是逆向的，所以需要将码值逆向存储。依次对每一个叶子节点进行编码操作，即可得到当前哈夫曼树的编码表。对于码值的逆向存储可以使用栈结构，先将一个码的每一步编码存入栈，再在一个码结束后出栈至空。当然也可以定义一个字符型数组，将值从后向前存入数组，再将数组有值部分粘贴到新的数组中进行存储。本次采用了后者，因为个人认为为此一步操作建立

5、栈结构不划算，而且前一个设计也已经熟练掌握了栈的方法，此处进行新的尝试会更好。1.3对文件进行编码。首先需要建立一个原始文件，在文件中输入需要编码的内容。之后将文件打开，将其中的内容存储到字符串中以便程序编码调用。开始对需要编码的字符进行编码，将字符逐一读取与刚刚建立的编码表中的每个叶子节点代表的字符进行比较，找出相同的对象，并将当前节点的编码打印到屏幕，并将编码存入到新建的密码文件当中。1.4对文件进行解码。-16-哈夫曼的编码与解码先打开密码文件，将之前编码后得到的密文内容存储到字符串中以便解

6、码调用。开始对密文的字符串进行解码，树索引从根节点开始走，当密文中的当前字符是‘0’的时候，则索引走向左子节点；当是‘1’的时候，则走向右子节点。以此类推，一直走到叶子节点为止，则当前叶子节点所代表的字符即为前一段密文的解码结果，。再对下一个字符依次从根节点开始解码，如此循环对每一段密文进行解码直到解码结束。将解码打印到屏幕，并将解码结果存入到新的解码文件当中。在解码之前，还应该先确认之前是否建立了哈夫曼树并且是否构建了编码表。不过由于本次将‘a’到‘z’都进行了编码，所以此步省略了，因为编码表是

7、唯一的。需要的时候可以在Encoder函数中先进行判定。将编码和解码写在了一起，可以在运行时进行选择调用。二、算法流程图第一步：建立哈夫曼树。-16-哈夫曼的编码与解码图1建立哈夫曼树的算法流程图第二步：构建哈夫曼编码表。-16-哈夫曼的编码与解码图2构建哈夫曼编码表的算法流程图第三步：编码。-16-哈夫曼的编码与解码图3编码算法流程图第四步：解码。-16-哈夫曼的编码与解码图4解码算法流程图-16-哈夫曼的编码与解码四、运行结果原文文件：图5中缀转后缀运行结果图编码图：图6编码图密文文件：-16

8、-哈夫曼的编码与解码图7密文文件图解码图：图8解码图译文文件：-16-哈夫曼的编码与解码图9译文文件图整体运行图：图10编码解码整体运行图五、遇到的问题及解决这部分我主要遇到了如下两个问题，其内容与解决方法如下所列：l第一个问题是权重的筛选部分出现了错误解决办法：一开始对于筛选最小权重的代码编写如下：voidSelectMin(HFMTT,inti,int*p1,int*p2){intj,min=999;for(j=0;j