课程设计：哈夫曼编码译码器

《课程设计：哈夫曼编码译码器》由会员上传分享，免费在线阅读，更多相关内容在工程资料-天天文库。

1、目录1.课程设计的题目32.组员的分工23.概要设计（函数划分、总体设计）34.详细设计（算法、流程图、程序）45.调试结果56.心得体会6课程设计的题目：哈夫曼树一即最优：义树，带权路径长度最小的二义树，经常应用于数据压缩。在计算机信息处理中，哈弗曼编码在信息论中应用举例“哈夫曼编码’’是一种一致性编码法（又称“嫡编码法”），用于数据的无损耗压缩。这一术语是指使用一张特殊的编码表将源字符（例如某文件中的一个符号）进行编码。这张编码表的特殊之处在于，它是根据每一个源字符出现的估算概率而建立起来的（出现概率高的字符使用较短的编码，反之出现

2、概率低的则使用较长的编码，这便使编码之后的字符串的平均期望长度降低，从而达到无损压缩数据的目的）。这种方法是由David.A.Huffman发展起来的。例如，在英文中，e的出现概率很高，而z的出现概率则最低。当利用哈夫曼编码对一篇英文进行压缩时，e极有可能用一个位例对以F信源进行哈夫受锔码估教符兮&概糸卿W字'WKk；0201020.191120.180003□.170013045010040011040.0101114哈弗曼编码在信息论中应用举例[2]（bit）来表示，而z则可能花去25个位（不是26）。用普通的表示方法时，每个英文

3、字母均占用一个字节（byte）,即8个位。二者相比，e使用了一般编码的1/8的长度，z则使用了3倍多。若能实现对于英文屮各个字母出现概率的较准确的估算，就可以大幅度提高无损压缩的比例组员的分工:工作进度表时间完成工作完成人周四上午完成需求分析，且从两种思路寻找圾好的一种陈亦信，陈永培周四上午设置流程图陈亦信，陈永培周四下午开始编代码陈亦信，陈永培周五上午不断调试，在调试中继续调整思路陈亦信，陈永培周五下午不断改进.完善陈亦信，陈永培201235020307陈亦信（组长）201235020308陈永培设计并编写核心部分代码；1、和队友共同

4、讨论并优化算法；设计哈夫噠树的算法2、编写课程设计报告和心得体会；编写课程设计报告和心得3、画算法的程序流程阁；体会；4、测试算法分析与设计5、改进编写课程设计报告和心得6、整理代码并且截阁体会软件开发环境：C语言编程，MicrosoftVisualC++6.0，MicrosoftVisualStudio2008编程工具实现0概要设计：要完成哈夫曼的编码和解码需要首先建立哈夫曼树，之后对所有字符根据权重进行编码，最后再对文件内容进行编码和解码。建立哈夫曼树的思想。首先定义适合哈夫曼树的节点类型，需要定义的有当前节点的字符，当前节点的左子

5、、右子和父亲指针。在建立哈夫曼树之前还需要对山现的字符和权重进行统计和记录，并且定义一个可以筛选出最小权重的函数。初始化树节点之后开始建立哈夫曼树。先在所有可能出现的字符中筛选出当前权重最小的两个字符，将这两个字符分别作为新节点的左子和右子建立一个小的二叉树，并将两个字符的权重之和赋值给新节点，将新二叉树放入筛选字符屮，再将筛选过的两个字符从筛选列表中淘汰掉。依次对列表屮剩下的字符进行权重最小的筛选，直到根节点（如果编码表共有N个字符，则2*N-1就为最终根节点）为止，也就是当筛选列表为空的吋候，哈夫曼树即建立完成。对于哈夫曼编码树來说

6、，由于哈夫曼编码是前缀码，所以所宥要编码的字符最终都将是这颗树的叶子节点，而其它节点并没有真正的字符意义。即当哈夫曼编码树建立之后，对树的所有叶子节点进行打印可知道是否有字符遗漏或多余。建立哈夫曼编码表。建立编码表时要根据每个出现的字符的权重对建立的哈夫曼树的每个叶子节点进行编码。编码时要从叶子节点出发向根节点进行逆向编码。判断如果当前节点为左子则对其编码‘0’，如果当前节点为右子则对其编码‘1’。以此类推进行编码直到根节点为止。此时的编码是逆向的，所以需要将码值逆向存储。依次对每一个叶子节点进行编码操作，即可得到当前哈夫曼树的编码表。

7、对于码值的逆向存储可以使川栈结构，先将一个码的每一步编码存入栈，再在一个码结束后出栈至空。当然也可以定义一个字符型数组，将值从后向前存入数组，再将数组有值部分粘贴到新的数组屮进行存储。本次采用了后者，因为个人认为为此一步操作建立栈结构不划算，而且前一个设计也已经熟练掌握了栈的方法，此处进行新的尝试会更好。对文件进行编码。首先需要建立一个原始文件，在文件屮输入需要编码的内容。之后将文件打开，将其屮的内容存储到字符串中以便程序编码调用。开始对需要编码的字符进行编码，将字符逐一读取与刚刚建立的编码表屮的毎个叶子节点代表的字符进行比较，找出相同

8、的对象，并将当前节点的编码打印到屏幕，并将编码存入到新建的密码文件当中。对文件进行解码。先打开密码文件，将之前编码后得到的密文内容存储到字符串中以便解码调用。开始对密文的字符串进行解码，树索引从根节点开始走