1、 0 数据结构课程设计报告 2015 数据结构数据结构 课程设计课程设计 题目题目-哈夫曼编码哈夫曼编码/译码的设计与实现译码的设计与实现 1 数据结构课程设计报告 2015 目目 录录 目录目录1 一、一、 需求分析需求分析2 2 二、二、 设计要求设计要求2 2 三、概要设计三、概要设计2 2 1、流程图2 2、设计包含的几个部分4 四、详细设计四、详细设计2 2 五、显示结果五、显示结果9.9. 六、心得体会六、心得体会1010 七、参考文献七、参考文献1111 2 数据结构课程设计报告 2015 哈夫曼编码译码哈夫曼编码译码 一、一、 需求分析需求分析 在当今信息爆炸时代， 如何采用有
2、效的数据压缩技术节省数据文件的存储空 间和计算机网络的传送时间已越来越引起人们的重视， 赫夫曼编码正是一种应用 广泛且非常有效的数据压缩技术。哈夫曼编码是一种编码方式，以哈夫曼树即 最优二叉树，带权路径长度最小的二叉树，经常应用于数据压缩。哈弗曼编码使 用一张特殊的编码表将源字符（例如某文件中的一个符号）进行编码。这张编码 表的特殊之处在于，它是根据每一个源字符出现的估算概率而建立起来的（出现 概率高的字符使用较短的编码，反之出现概率低的则使用较长的编码，这便使编 码之后的字符串的平均期望长度降低，从而达到无损压缩数据的目的） 。赫夫曼 编码的应用很广泛，利用赫夫曼树求得的用于通信的二进制编码
3、称为赫夫曼编 码。树中从根到每个叶子都有一条路径，对路径上的各分支约定：指向左子树的 分支表示“0”码，指向右子树的分支表示“1”码，取每条路径上的“0”或“1” 的序列作为和各个叶子对应的字符的编码，这就是赫夫曼编码。哈弗曼译码输入 字符串可以把它编译成二进制代码，输入二进制代码时可以编译成字符串。 二、设计要求设计要求 对输入的一串电文字符实现赫夫曼编码， 再对赫夫曼编码生成的代码串进行 译码，输出电文字符串。通常我们把数据压缩的过程称为编码，解压缩的过程称 为解码。电报通信是传递文字的二进制码形式的字符串。但在信息传递时，总希 望总长度能尽可能短，即采用最短码。假设每种字符在电文中出现的
4、次数为 Wi， 编码长度为 Li，电文中有 n 种字符，则电文编码总长度为WiLi。若将此对应 到二叉树上， Wi 为叶结点的权， Li 为根结点到叶结点的路径长度。 那么， WiLi 恰好为二叉树上带权路径长度。因此 ，设计电文总长最短的二进制前缀编码， 就是以 n 种字符出现的频率作权，构造一棵赫夫曼树，此构造过程称为赫夫曼编 码。 设计实现的功能： (1) 赫夫曼树的建立； (2) 赫夫曼编码的生成； (3) 编 码文件的译码。 三、三、 概要设计概要设计 哈夫曼编译码器的主要功能是先建立哈夫曼树，然后利用建好的哈夫曼树 生成哈夫曼编码后进行译码 。 在数据通信中，经常需要将传送的文字转
5、换成由二进制字符 0、1 组成的二 进制串，称之为编码。构造一棵哈夫曼树，规定哈夫曼树中的左分之代表 0，右 分支代表 1，则从根节点到每个叶子节点所经过的路径分支组成的 0 和 1 的序列 便为该节点对应字符的编码，称之为哈夫曼编码。 最简单的二进制编码方式是等长编码。若采用不等长编码，让出现频率高的 字符具有较短的编码，让出现频率低的字符具有较长的编码，这样可能缩短传送 电文的总长度。哈夫曼树课用于构造使电文的编码总长最短的编码方案。 （1）其主要流程图如图 1-1 所示。 3 数据结构课程设计报告 2015 开始 结点数是否大于 1 将 data 和权值赋给 ht 输出根结点和权值 调用 SELECT 函数 计算根结点函数 父结点为两子结点之和 输出两子结点和已构造的结点 是否为根结点？ 左子是否为空？ 此时编码为 0 I2*N? I+ 编码为 1 结束 否 否 否 右子是否为空 是 是 否 否 是 是 是 4 数据结构课程设计报告 2015 （2）设计包含的几个方面： 赫夫曼树的建立 赫夫曼树的建立由赫夫曼算法的定义可知， 初始
