湖南科技学院 数据结构 课程设计报告 课 题: 霍夫曼编码 专业班级: 信计 1202 学 号: ************ * 名: *** ****: *** 1 1 课程设计的目的和意义 在当今信息爆炸时代,如何采用有效的数据压缩技术来节省数据文件的存储空间和计算机网络的传送时间已越来越引起人们的重视。哈夫曼编码正是一种应用广泛且非常有效的数据压缩技术。 哈夫曼编码的应用很广泛,利用哈夫曼树求得的用于通信的二进制编码称为哈夫曼编码。树中从根到每个叶子都有一条路径,对路径上的各分支约定:指向左子树的分支表示“0”码,指向右子树的分支表示“1”码,取每条路径上的“0”或“1”的序列作为和各个对应的字符的编码,这就是哈夫曼编码。 通常我们把数据压缩的过程称为编码,解压缩的过程称为解码。电报通信是传递文字的二进制码形式的字符串。但在信息传递时,总希望总长度尽可能最短,即采用最短码。 2 2.需求分析 课 题:哈夫曼编码译码器系统 问题描述:打开一篇英文文章,统计该文章中每个字符出现的次数,然后以它们作为权值,对每一个字符进行编码,编码完成后再对其编码进行译码。 问题补充:1. 从硬盘的一个文件里读出一段英语文章; 2. 统计这篇文章中的每个字符出现的次数; 3. 以字符出现字数作为权值,构建哈夫曼树 4. 对每个字符进行编码并将所编码写入文件然后对所编码进行破译。 具体介绍:在本课题中,我们在硬盘 D 盘中预先建立一个xuzhimo.txt 文档,在里面编辑一篇文章(大写)。然后运行程序,调用 fileopen()函数读出该文章,显示在界面;再调用 tongji()函数对该文章的字符种类进行统计,并对每个字符的出现次数进行统计,并且在界面上显示;然后以每个字符出现次数作为权值,调用 Create_huffmanTree()函数构建哈夫曼树。然后调用 Huffman_bianma()函数对哈夫曼树进行编码,调用coding()函数将编码写入文件。 3 3 系统(项目)设计 (1)设计思路及方案 本课题是用最优二叉树即哈夫曼树来实现哈夫曼编码译码器的功能。假设每种字符在电文中出现的次数为Wi,编码长度为Li,电文中有n 种字符,则电文编码总长度为(W1*L1)+(W2*L2)+…+(Wi*Li)。若将此对应到二叉树上,Wi 为叶结点,Li 为根结点到叶结点的路径长度。那么,(W1*L1)+(W2*L2)+…+(Wi*Li)恰好为二叉树上带权路径长度。 因此,设计电文总长最短的二进制前缀编码,就是以 n 种字符出现的频率作权,构造一棵哈夫曼树,此构造过...