哈夫曼编码译码器课程设计详解.doc

目录 摘要 Ⅱ 正文 1 一.设计目的和要求 1 二.设计原理 1 三.设计内容 1 1.模块的设计及介绍 2 2.主要模块程序流程图 5 3.系统实现 8 4.系统调试 11 总结与致谢...............................................................................14 参考文献...................................................................................15 附录 源程序 16  摘要 在当今信息爆炸时代，如何采用有效的数据压缩技术来节省数据文件的存储空间和计算机网络的传送时间已越来越引起人们的重视。哈夫曼编码正是一种应用广泛且非常有效的数据压缩技术。 哈夫曼编码的应用很广泛，利用哈夫曼树求得的用于通信的二进制编码称为哈夫曼编码。树中从根到每个叶子都有一条路径，对路径上的各分支约定：指向左子树的分支表示“0”码，指向右子树的分支表示“1”码，取每条路径上的“0”或“1”的序列作为和各个对应的字符的编码，这就是哈夫曼编码。 通常我们把数据压缩的过程称为编码，解压缩的过程称为解码。电报通信是传递文字的二进制码形式的字符串。但在信息传递时，总希望总长度尽可能最短，即采用最短码。 关键词：哈夫曼树、编码、解码、设计  正 文 一.设计目的和要求 打开一篇英文文章，统计该文章中每个字符出现的次数，然后以它们作为权值，对每一个字符进行编码，编码完成后再对其编码进行译码。 实现的具体功能如下： 1．从硬盘的一个文件里读出一段英语文章； 2．统计这篇文章中的每个字符出现的次数； 3．以字符出现字数作为权值，构建哈夫曼树，并将哈夫曼树的存储 结构的初态和终态进行输出； 4．对每个字符进行编码并将所编码写入文件； 5．对所编码进行译码输出。 二.设计原理 本课题是用最优二叉树即哈夫曼树来实现哈夫曼编码译码器的功能。假设每种字符在电文中出现的次数为Wi，编码长度为Li，电文中有n种字符，则电文编码总长度为(W1*L1)+(W2*L2)+…+(Wi*Li)。若将此对应到二叉树上，Wi为叶结点，Li为根结点到叶结点的路径长度。那么，(W1*L1)+(W2*L2)+…+(Wi*Li)恰好为二叉树上带权路径长度。 因此，设计电文总长最短的二进制前缀编码，就是以n种字符出现的频率作权，构造一棵哈夫曼树，此构造过程称为哈夫曼编码。 该系统将实现以下几大功能：从硬盘读取字符串，建立哈夫曼树，输出哈夫曼树的存储结构的初态和终态，输出各种字符出现的次数以及哈夫曼编码的译码等。 三.设计内容 对系统进行分析，给出系统结构图 图1?系统结构图 （1）.编码：提示要编码的文件文件名→读取文件→以字母出现次数为权值建立哈弗曼树→对文本进行哈弗曼编码并输出编码→提示将编码保存的文件名→保存编码文件。? （2）.译码：提示输入要译码的文件名→利用建立好的哈弗曼树进行译码→将译码输出→提示保存译码文件的文件名→保存译码文件。 （3）.退出：退出系统，程序运行结束。? 1.模块的设计及介绍 1.1从硬盘读取字符串 fileopen(参数) { 实现命令； 打印输出； } 1.2建立HuffmanTree 通过三个函数来实现： void select(参数) { 初始化； for { 接受命令； 处理命令； } } 说明：在ht[1....k]中选择parent为0且权值最小的两个根结点的算法 int jsq(参数) { 初始化； for { 接受命令； 处理命令； } } 说明：统计字符串中各种字母的个数以及字符的种类 void ChuffmanTree() { 初始化； for { 接受命令； 处理命令； } 输出字符统计情况； } 说明：构造哈夫曼树 1.3输出哈夫曼树的存储结构的初态和终态 分别调用print1()和print2()来实现 void print1(参数) { 初始化； 输出初态； } 说明：输出哈夫曼树的初态 void print2(参数) { for { 输出终态； } } 说明：输出哈夫曼