1 福建农林大学 计算机与信息学院 数据结构课程设计 设计：哈夫曼编译码器 姓名：*** 专业：2013 级计算机科学与技术 学号：******** 班级：13052316 完成日期：2013.12.28 2 哈夫曼编译码器 一、需求分析 在当今信息爆炸时代，如何采用有效的数据压缩技术节省数据文件的存储空间和计算机网络的传送时间已越来越引起人们的重视，哈夫曼编码正是一种应用广泛且非常有效的数据压缩技术。哈夫曼编码是一种编码方式，以哈夫曼树—即最优二叉树，带权路径长度最小的二叉树，经常应用于数据压缩。哈夫曼编码使用一张特殊的编码表将源字符（例如某文件中的一个符号）进行编码。这张编码表的特殊之处在于，它是根据每一个源字符出现的估算概率而建立起来的（出现概率高的字符使用较短的编码，反之出现概率低的则使用较长的编码，这便使编码之后的字符串的平均期望长度降低，从而达到无损压缩数据的目的）。哈夫曼编码的应用很广泛，利用哈夫曼树求得的用于通信的二进制编码称为哈夫曼编码。树中从根到每个叶子都有一条路径，对路径上的各分支约定：指 向 左 子树的分支表示 “ 0” 码，指向 右 子树的分支表示 “ 1” 码，取 每条路径上的“ 0” 或 “ 1” 的序 列作 为和各个叶子对应的字符的编码，这就 是哈夫曼编码。哈夫曼译码输 入 字符串可 以把 它编译成 二进制代码，输 入 二进制代码时可 以编译成 字符串。 二、设 计要 求 对输 入 的一串电 文字符实 现哈夫曼编码，再 对哈夫曼编码生 成 的 3 代码串进行译码，输出电文字符串。通常我们把数据压缩的过程称为编码，解压缩的过程称为解码。电报通信是传递文字的二进制码形式的字符串。但在信息传递时，总希望总长度能尽可能短，即采用最短码。假设每种字符在电文中出现的次数为Wi，编码长度为Li，电文中有n 种字符，则电文编码总长度为∑WiLi。若将此对应到二叉树上，Wi 为叶结点的权，Li 为根结点到叶结点的路径长度。那么，∑WiLi恰好为二叉树上带权路径长度。因此 ，设计电文总长最短的二进制前缀编码，就是以 n 种字符出现的频率作权，构造一棵哈夫曼树，此构造过程称为哈夫曼编码。设计实现的功能： (1) 哈夫曼树的建立； (2) 哈夫曼编码的生成； (3) 编码文件的译码。 三、概要设计 哈夫曼编\译码器的主要功能是先建立哈夫曼树，然后利用建好的哈夫曼树生成哈夫曼编码后进行译码 。 在数据通信中，经常需要将传送...
