《哈夫曼编码译码器课程设计》由会员分享，可在线阅读，更多相关《哈夫曼编码译码器课程设计（27页珍藏版）》请在金锄头文库上搜索。
1、山东建筑大学信息与电气工程学院课程设计说明书 目录摘要正文1 一.设计目的和要求1 二.设计原理1 三.设计内容1 1.模块的设计及介绍2 2.主要模块程序流程图5 3.系统实现8 4.系统调试11总结与致谢.14参考文献.15附录 源程序16 1 摘要 在当今信息爆炸时代，如何采用有效的数据压缩技术来节省数据文件的存储空间和计算机网络的传送时间已越来越引起人们的重视。哈夫曼编码正是一种应用广泛且非常有效的数据压缩技术。哈夫曼编码的应用很广泛，利用哈夫曼树求得的用于通信的二进制编码称为哈夫曼编码。树中从根到每个叶子都有一条路径，对路径上的各分支约定：指向左子树的分支表示“0”码，指向右子树的分
2、支表示“1”码，取每条路径上的“0”或“1”的序列作为和各个对应的字符的编码，这就是哈夫曼编码。通常我们把数据压缩的过程称为编码，解压缩的过程称为解码。电报通信是传递文字的二进制码形式的字符串。但在信息传递时，总希望总长度尽可能最短，即采用最短码。 关键词：哈夫曼树、编码、解码、设计1 正 文一.设计目的和要求 打开一篇英文文章，统计该文章中每个字符出现的次数，然后以它们作为权值，对每一个字符进行编码，编码完成后再对其编码进行译码。 实现的具体功能如下： 1从硬盘的一个文件里读出一段英语文章； 2统计这篇文章中的每个字符出现的次数； 3以字符出现字数作为权值，构建哈夫曼树，并将哈夫曼树的存储
3、结构的初态和终态进行输出； 4对每个字符进行编码并将所编码写入文件； 5对所编码进行译码输出。二.设计原理 本课题是用最优二叉树即哈夫曼树来实现哈夫曼编码译码器的功能。假设每种字符在电文中出现的次数为Wi，编码长度为Li，电文中有n种字符，则电文编码总长度为(W1*L1)+(W2*L2)+(Wi*Li)。若将此对应到二叉树上，Wi为叶结点，Li为根结点到叶结点的路径长度。那么，(W1*L1)+(W2*L2)+(Wi*Li)恰好为二叉树上带权路径长度。 因此，设计电文总长最短的二进制前缀编码，就是以n种字符出现的频率作权，构造一棵哈夫曼树，此构造过程称为哈夫曼编码。 该系统将实现以下几大功能：从
4、硬盘读取字符串，建立哈夫曼树，输出哈夫曼树的存储结构的初态和终态，输出各种字符出现的次数以及哈夫曼编码的译码等。 三.设计内容对系统进行分析，给出系统结构图: 哈夫曼树编码译码器 退出 译码 编码 图1系统结构图（1）.编码：提示要编码的文件文件名读取文件以字母出现次数为权值建立哈弗曼树对文本进行哈弗曼编码并输出编码提示将编码保存的文件名保存编码文件。（2）.译码：提示输入要译码的文件名利用建立好的哈弗曼树进行译码将译码输出提示保存译码文件的文件名保存译码文件。（3）.退出：退出系统，程序运行结束。1.模块的设计及介绍 1.1从硬盘读取字符串fileopen(参数) 实现命令； 打印输出； 1
5、.2建立HuffmanTree通过三个函数来实现：void select(参数) 初始化； for 接受命令； 处理命令；说明：在ht1.k中选择parent为0且权值最小的两个根结点的算法int jsq(参数) 初始化； for 接受命令； 处理命令； 说明：统计字符串中各种字母的个数以及字符的种类void ChuffmanTree() 初始化； for 接受命令； 处理命令； 输出字符统计情况；说明：构造哈夫曼树 1.3输出哈夫曼树的存储结构的初态和终态分别调用print1()和print2()来实现void print1(参数) 初始化； 输出初态；说明：输出哈夫曼树的初态void pr
6、int2(参数) for 输出终态；说明：输出哈夫曼树的终态 1.4哈夫曼编码和译码void HuffmanEncoding(参数) 定义变量； 处理命令；说明：哈夫曼编码char*decode(参数) 定义变量；while接受命令；处理命令；说明：哈夫曼译码2.主要模块程序流程图下面介绍三个主要的程序模块流程图： 2.1主函数流程图：结束统计字符种类及频率字符总数num建立哈夫曼树哈夫曼编码哈夫曼译码打开文件？开始否是 图2.1流程图注释： 该图比较简单，主要是调用各个函数模块，首先代开已经存在的文件，然后统计总的字符数以及出现的各个字符和频率。然后才开始建立哈夫曼树，接着在哈夫曼树的基础上
7、对其进行编码，编码之后才是译码。最后输出结束。 2.2构造哈夫曼树：开始结束第i个结点权值i=num?创建哈夫曼树输出字符统计情况第i个根结点i=2*num-1?i=num?否是否是否是 图2.2流程图注释： 该图是表示构造哈夫曼树的过程。首先输入num个叶结点的权值，当i=num是循环结束。然后进行哈夫曼树的构建，当i=2*num-1是循环结束。最后输出所得到的字符统计情况。 2.3哈夫曼编码：结束开始Tp.lchlid=c?inext=p-LChild=p-RChild=p-Parent=NULL;/初始化哈夫曼链表且有2n-1个节点for(i=1;inext=(HFMTree)mallo
8、c(sizeof(HFMNode); p=p-next;p-next=p-LChild=p-RChild=p-Parent=NULL; for(i=0,p=*HT;iweight=counti; p=p-next; for(i=n;iParent=HT2-Parent=p; p-LChild=HT1; p-RChild=HT2; p-weight=HT1-weight+HT2-weight;/将两个节点的权值相加存入最后一个节点中 p=p-next;/p指向下一个没有存储权值的节点 3.3生成Huffman编码并写入文件 voidHFMCode(HFMTreeHT,CodeNodeHC,charstr)/从每个叶子节点开始，利用哈夫曼树对每个字符进行编码，最终建立一个哈夫曼表 inti; HFMTreeq,p=HT; for(i=0;in;i+)/将字符存入哈夫曼编码结构体数组的字符单元中 HCi.ch=stri; HCi.coden-1=0;/初始化编码的最后一位 for(i=0;in;i+)
