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

山东建筑大学信息与电气工程学院课程设计说明书 目录摘要正文1 一.设计目的和要求1 二.设计原理1 三.设计内容1 1.模块的设计及介绍2 2.主要模块程序流程图5 3.系统实现8 4.系统调试11总结与致谢.14参考文献.15附录 源程序16 1 摘要 在当今信息爆炸时代，如何采用有效的数据压缩技术来节省数据文件的存储空间和计算机网络的传送时间已越来越引起人们的重视。哈夫曼编码正是一种应用广泛且非常有效的数据压缩技术。哈夫曼编码的应用很广泛，利用哈夫曼树求得的用于通信的二进制编码称为哈夫曼编码。树中从根到每个叶子都有一条路径，对路径上的各分支约定：指向左子树的分支表示“0”码，指向右子树的分支表示“1”码，取每条路径上的“0”或“1”的序列作为和各个对应的字符的编码，这就是哈夫曼编码。通常我们把数据压缩的过程称为编码，解压缩的过程称为解码。电报通信是传递文字的二进制码形式的字符串。但在信息传递时，总希望总长度尽可能最短，即采用最短码。 关键词：哈夫曼树、编码、解码、设计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 接受命令； 处理命令；说明：在ht1.k中选择parent为0且权值最小的两个根结点的算法int jsq(参数) 初始化； for 接受命令； 处理命令； 说明：统计字符串中各种字母的个数以及字符的种类void ChuffmanTree() 初始化； for 接受命令； 处理命令； 输出字符统计情况；说明：构造哈夫曼树 1.3输出哈夫曼树的存储结构的初态和终态分别调用print1()和print2()来实现void print1(参数) 初始化； 输出初态；说明：输出哈夫曼树的初态void print2(参数) for 输出终态；说明：输出哈夫曼树的终态 1.4哈夫曼编码和译码void HuffmanEncoding(参数) 定义变量； 处理命令；说明：哈夫曼编码char*decode(参数) 定义变量；while接受命令；处理命令；说明：哈夫曼译码2.主要模块程序流程图下面介绍三个主要的程序模块流程图： 2.1主函数流程图：结束统计字符种类及频率字符总数num建立哈夫曼树哈夫曼编码哈夫曼译码打开文件？开始否是 图2.1流程图注释： 该图比较简单，主要是调用各个函数模块，首先代开已经存在的文件，然后统计总的字符数以及出现的各个字符和频率。然后才开始建立哈夫曼树，接着在哈夫曼树的基础上对其进行编码，编码之后才是译码。最后输出结束。 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)malloc(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;iParent;q=q-Parent)/判断q所指向的节点，左孩子置0，右孩子置1 if(q=q-Parent-LChild) HCi.code-HCi.start=0; elseHCi.code-HCi.start=1; p=p-next;/判断下一个叶子节点 3.4电文译码voidDeCoding(charcode,HFMTreeHT,charstr,chars) /对哈夫曼编码进行译码，放入字符串s中 inti,j,k=0; HFMTreeroot,p,q; for(root=HT;root-Parent;root=root-Parent); /用root指向哈夫曼树的根结点 for(i=0,p=root;codei;i+)/从根结点开始按编码顺序访问树 if(codei=0) p=p-LChild; elsep=p-RChild; if(p-LChild=NULL&p-RChild=NULL)/到根节点时将该节点对应的字符输出 for(j=0,q=HT;q!=p;q=q-next,j+); sk+=strj; p=root;/回溯到根结点 sk=0;/解码完毕，在字符串最后一个单元存入04.系统调试（1）运行程序后，我们可以见到一下的运行界面。 图4.1主界面运行截图（2）选择1，按回车键，在输入txt1.txt对字符串进行编码，得到如下界面： 图4.2编码运行截图（3）输入txt2.txt按回车键保存哈弗曼编码： 图4.3保存编码运行截图（4）输入txt2.txt按回车键进行译码得到如下界面： 图4.4译码运行截图 由此可见，此次测试很成功。我们能够将文本文档中的文段读出，并将其统计并输出字符种类和每种字符出现的频率。同时输出哈夫曼树存储结构的初态和终态。然后输出译码后的字符。 总结与致谢通过一周的课程设计使我对哈夫曼树以及哈夫曼编码有了更深的认识和理解，也使我更加明白哈夫曼编码译码在信息技术中的重要性和地位。在一开始的时候，代码中有许多的错误，在实现文章的读入时，由于对文件不是太熟悉，只好翻开C语言书本仿照其模式编写，但后来进入了死循环。还好有老师和同学的帮忙，在使得我明白了哈夫曼到底是怎么存储信息的。许多的错误让我明白了一个道理-细心是非常重要的。同时，对于编程者而言，思路清晰是相当重要的。在适当的时候和同学一起交流探讨是一个十分好的学习机会。请教老师也很重要，因为毕竟我们是新手，对于某些问题很难弄清楚。而且，某些错误对于我们来说有时候想半天都弄不来，但老师几下下就搞好了，这样就更加有效地节约了时间。这次课程设计不但让我学得了一些编程知识，还学会了系统的做一份课程设计报告学会了如何更好的画流程图，明白了做事情只有认真，才能真正做得更好。在本次课程设计过程中，指导老师杨红娟老师、张君捧老师都给予了我很大的帮助。在此，表示由衷的感谢。 参考文献1 严蔚敏.数据结构(C语言版).清华大学出版社，20072 苏仕华.数据结构课程设计.机械工业出版社，20073 谭浩强.C语言程序设计教程.高等教育出版社，20064 严蔚敏,陈文博.数据结构及应用算法教程.清华大学出版社，20115 (美）Robert L.Kruse,Alexander J.Ryba.数据结构与程序设计（影印版）.高等教育出版社，20016（美）Mark Allen Weiss.数据结构与算法分析.机械工业出版社，20047高一凡.数据结构算法实现及解析.西安电子科技大学，20088徐士良,葛兵.计算机软件技术基础（第二版）.清华大学出版社，20079沈被娜,刘祖照,姚晓冬.计算机软件技术基础（第三版）.清华大学出版社，200710赵应良.软件开发技术基础（第2版）.机械工业出版社，200411（美)H.M.Deitel, P.J.Deitel 著，薛万鹏等译，C 程序设计教程.北京机械工业出版社，200012谭浩强.C语言程序设计.清华大学出版社，201013 Brian W. Kernighan Dennis M. Ritchie, C PROGRAMMING LANGUAGE.清华大学影印版,2001 年 6 月第 10 次印刷 附录 源程序#include #include #include #include/*类型相关变量的定义*#define n 100 /叶子结点数#define m 2*n-1 /哈夫曼树中的结点树typedef structchar ch;char bits9; /存放编码位串int len; CodeNode;typedef CodeNode HuffmanCoden+1;typedef struct int weight; /权值int lchild,rchild,parent; /左右孩子几双亲指针 HTNode;typedef HTNode HuffmanTreem+1; /0号单元不用int num;/*建立HuffmanTree*void select(HuffmanTree T,int k,int &s1,int &s2) /在ht1.k中选择parent为0且权值最小的两个根结点的算法/其序号为s1和s2int i,j;int min1=101; for(i=1;i=k;i+)if(Ti.weightmin1 &Ti.parent=0) j=i;min1=Ti.weight;s1=j;min1=32767;for (i=1;i=k;i+)if(Ti.weightmin1 & Ti.parent=0 & i!=s1)j=i;min1=Ti.weight;s2=j;int jsq(char *s,int cnt,char str) /统计字符串中各种字母的个数以及字符的种类int i,j,k; char *p;int temp27; for(i=1;i=A&*p=Z)k=*p-64;tempk+;for(i=1,j=0;i=26;+i)if(tempi!=0 ) j+;strj=i+64; /送对应的字母到数组中cntj=tempi; /存入对应字母的权值return j; /j是输入字母总数void ChuffmanTree(HuffmanTree HT,HuffmanCode HC,int cnt,char str) /构造哈夫曼树HTint i,s1,s2;for(i=1;i=2*num-1;i+)/初始化HT，2*num-1是指哈夫曼树所有的结点数目HTi.lchild=0;HTi.rchild=0;HTi.parent=0;HTi.weight=0;for(i=1;i=num;i+) /输入num个叶结点的权值HTi.weight=cnti;for(i=num+1;i=2*num-1;i+) /在ht1.k中选择parent为0且权值最小的两个根结点/其序号为s1和s2/i为双亲select(HT,i-1,s1,s2);HTs1.parent=i;HTs2.parent=i;HTi.lchild=s1; HTi.rchild=s2;HTi.weight=HTs1.weight+HTs2.weight;for(i=0;i=num;i+) /输入字符集的中字符HCi.ch=stri; /字符的种类i=1;while(i=num)printf(字符%c次数:%dn,HCi.ch,cnti+);/*生成Huffman编码并写入文件*void HuffmanEncoding(HuffmanTree T,HuffmanCode H) /根据哈夫曼树T求哈夫曼编码Hint c,p,i; /c和p分别指示t中孩子和双亲char cdn; /临时存放编码串int start; /指示码在cd中的起始位置cdnum=0; /最后一位（第num个）放上串结束符for(i=1;i0) /直至上溯到tc是树根为止 /若tc是tp的左孩子,则生成0;否则生成底码cd-start=(Tp.lchild=c) ? 0 : 1;c=p;strcpy(Hi.bits,&cdstart);Hi.len=num-start;void coding(HuffmanCode HC ,char *str) /对str所代表的字符串进行编码 并写入文件int i,j;FILE *fp;fp=fopen(codefile.txt,w);while(*str)for(i=1;i=num;i+)if(HCi. ch=*str)for(j=0;j=HCi.len;j+)fputc(HCi.bitsj,fp);break;str+;fclose(fp);/*电文译码*char*decode(HuffmanCode HC) /代码文件codefile.txt的译码FILE *fp;char str254; /假设远文本文件不超过254个字符char *p;static char cdn+1;int i,j,k=0,cjs;fp=fopen(codefile.txt,r);/一只读的方式打开文本文档codefile.txtwhile(!feof(fp)/feof(fp)判断文件是否真正结束，feof(fp)=1时文件结束cjs=0;for(i=0;inum & cjs=0 & !feof(fp);i+)cdi= ;cdi+1=0;cdi=fgetc(fp);/数组接受从fp指针所指向文件中读入的一个字符 for(j=1;j=num;j+)if(strcmp(HCj.bits,cd)=0)/haffman编码和密码译码相比较strk=HCj.ch;k+;cjs=1;break; strk=0;p=str;return p;/*输出HuffmanTree存储结构*void print1(HuffmanTree HT)int x; for(x=1;x=2*num-1;x+) HTx.parent=0;HTx.lchild=0;HTx.rchild=0;printf(%11d %dt %dt %dn,HTx.weight,HTx.parent,HTx.lchild,HTx.rchild);printf(-n); void print2(HuffmanTree HT)int k;for(k=1;k=2*num-1;k+) printf( %dt %dt %dt %dn,HTk.weight,HTk.parent,HTk.lchild,HTk.rchild);