实验四-赫夫曼.doc

《实验四-赫夫曼.doc》由会员上传分享，免费在线阅读，更多相关内容在教育资源-天天文库。

1、目录1.概述11.1问题描述12.现状分析13.系统分析14.1系统功能模块图25.1赫夫曼树的存储结构定义35.2赫夫曼算法及其实现35.3统计字符串中字符的种类以及各类字符的个数35.4赫夫曼编译码系统功能模块36.主要代码结构46.1定义赫夫曼编码类型如下46.2赫夫曼编码算法46.3建立正文的编码文件57.主要代码段分析67.1赫夫曼编码的结构定义67.2赫夫曼编码算法68.运行与测试78.1测试数据及结果79.总结和心得8参考文献810.附：源代码91.概述1.1问题描述利用赫夫曼编码进行通信可以大大提高信道利用率，缩短信息传输时间，降低传输成本。这要求在发送端通过一

2、个编码系统对待传输数据预先编码，对于双工信道（即可以双向传输信息的信道），每端都需要一个完整的编码系统。2.现状分析在当今信息爆炸时代，如何采用有效的数据压缩技术节省数据文件的存储空间和计算机网络的传送时间已越来越引起人们的重视，赫夫曼编码正是一种应用广泛且非常有效的数据压缩技术。赫夫曼编码是一种编码方式，以赫夫曼树—即最优二叉树，带权路径长度最小的二叉树，经常应用于数据压缩。赫夫曼编码使用一张特殊的编码表将源字符（例如某文件中的一个符号）进行编码。赫夫曼编码的应用很广泛，利用赫夫曼树求得的用于通信的二进制编码称为赫夫曼编码。树中从根到每个叶子都有一条路径，对路径上的各分支约定

3、：指向左子树的分支表示“0”码，指向右子树的分支表示“1”码，取每条路径上的“0”或“1”的序列作为和各个叶子对应的字符的编码，这就是赫夫曼编码。赫夫曼译码输入字符串可以把它编译成二进制代码，输入二进制代码时可以编译成字符串.赫夫曼编码是已被证明的一种有效的熵编码方式,在诸如文本、图像、视频压缩及通信、密码等信息压缩编码标准中被广泛使用。目前广泛应用的许多其他高效数据压缩算法。3.系统分析利用二叉树结构实现赫夫曼编/解码器。基本要求：1、初始化：能够对输入的任意长度的字符串进行统计，统计每个字符的频度，并建立赫夫曼树。2、建立编码表(CreateTable)：利用已经建好的赫夫

4、曼树进行编码，并将每个字符的编码输出。3、编码(Encoding)：根据编码表对输入的字符串进行编码，并将编码后的字符串输出。4、译码(Decoding)：利用已经建好的赫夫曼树对编码后的字符串进行译码，并输出译码结果。4.概要设计4.1系统功能模块图赫夫曼编译码器的主要功能是先建立赫夫曼树，然后利用建好的赫夫曼树生成赫夫曼编码后进行译码。在数据通信中，经常需要将传送的文字转换成由二进制字符0、1组成的二进制串，称之为编码。构造一棵赫夫曼树，规定赫夫曼树中的左分之代表0，右分支代表1，则从根节点到每个叶子节点所经过的路径分支组成的0和1的序列便为该节点对应字符的编码，称之为赫

5、夫曼编码。最简单的二进制编码方式是等长编码。若采用不等长编码，让出现频率高的字符具有较短的编码，让出现频率低的字符具有较长的编码，这样可能缩短传送电文的总长度。赫夫曼树课用于构造使电文的编码总长最短的编码方案。赫夫曼编码/译码器类型及相关变量的定义建立赫夫曼树生成赫夫曼文件赫夫曼译码4.1系统功能模块图5.详细设计5.1赫夫曼树的存储结构定义#definen100//叶子结点数#definem2*n-1//赫夫曼树中结点总数typedefstruct{intweight;//权值intlchild,rchild,parent;//左右孩子及双亲指针}HTNode;//树中结点类

6、型typedefHTNodeHuffmanTree[m+1];//零号单元不用5.2赫夫曼算法及其实现①根据给定的n个权值{w1,w2,···wn},构成n棵二叉树的集F={T1,T2,···Tn},其中每棵二叉树Ti中只有一个带权为wi的根结点,其左右子树均空。②在F中选取两棵根结点的权值最小的树作为左右子树构造一棵新的二叉树,且置新的二叉树的根结点的权值为其左、右子树上根结点的权值之和。③在F中删除这两棵树,同时将新得到的二叉树加入F中。④重复②和③,直到F只含一棵树为止,这棵树便是赫夫曼树。5.3统计字符串中字符的种类以及各类字符的个数该算法的主要实现思想是：先定义一个含

7、有26个元素的临时整型数组，用来存储各种字母出现的次数。因为大写字母与小写字母相差64位，所以在算法中我们可以使用字母减去64作为统计数组的下标对号入座。在统计和保存过程中，我们用一个循环来判断先前统计的各类字符是否为零，若不为零，则将其存入一个数组对应得元素中，同时将其对应的字符也存入另一个数组元素中。5.4赫夫曼编译码系统功能模块(1)赫夫曼建树模块:根据输入的字符和频率,完成赫夫曼树的构造,并根据赫夫曼树求赫夫曼编码。(2)编码模块:读取文本文件进行编码,编码结果存入到新文件。(3)译