哈夫曼编译码器.doc

《哈夫曼编译码器.doc》由会员分享，可在线阅读，更多相关《哈夫曼编译码器.doc（26页珍藏版）》请在三一办公上搜索。

1、摘 要随着计算机的普遍应用与日益发展,其应用早已不局限于简单的数值运算,而涉及到问题的分析,数据结构框架的设计以及设计最短路线等复杂的非数值处理和操作。算法与数据结构的学习就是为以后利用计算机资源高效地开发非数值处理的计算机程序打下坚实的理论,方法和技术基础。利用哈夫曼编码进行通信可以大大提高信道利用率，缩短信息传输时间，降低传输成本。但是，这要求在发送端通过一个编码系统对待传数据预先编码，在接收端将传来的数据进行译码（复原）。对于双工通信（即可以双向传输信息的信道），每端都需要一个完整的编/译码系统，试设计一个哈夫曼编码系统。关键词：Huffman编码树；编码；译码AbstractWith

2、the widespread application and the development of computer, its application is not limited to a simple numerical computation, and relates to theproblem analysis, data structure design of the framework for the design and the shortest route of complicated non numerical processing and operation. The al

3、gorithm and data structure of learning for the future is the use of computer resources efficiently to develop computer programs non numerical treatment to lay a solid theoretical foundation, methods and techniques.The use of Huffman coding can greatly improve the communication channel utilization, r

4、educe the information transmission time, lower transmission costs.However, this requires the sending end through a coding system for pre encoded data, at the receiving end of data from the decoding (Fu Yuan). Forduplex communication (which can be a two-way channel to transmit information),each side

5、needs a complete encoding / decoding system, try to design a Huffman coding system.Keywords: Huffman coding tree; coding;decoding目 录1概述11.1设计背景11.2问题分析11.3设计任务21.4总体结构22总体设计32.1总体设计思想、设计方案的选择32.1.1 最优二叉树（Huffman树）32.1.2构造哈夫曼树的步骤32.1.3数据结构的选择42.2结构设计42.2.1结构体存储表示42.2.2主函数模块42.2.3系统结构图53详细设计73.1构造哈夫曼树

6、73.2哈夫曼编码84系统实现与测试94.1错误分析94.2运行结果95 总结12参考文献13致 谢14附 录151概述1.1设计背景1951年，哈夫曼和他在MIT信息论的同学需要选择是完成学期报告还是期末考试。导师Robert M. Fano给他们的学期报告的题目是，寻找最有效的二进制编码。由于无法证明哪个已有编码是最有效的，哈夫曼放弃对已有编码的研究，转向新的探索，最终发现了基于有序频率二叉树编码的想法，并很快证明了这个方法是最有效的。 由于这个算法，学生终于青出于蓝，超过了他那曾经和信息论创立者香农共同研究过类似编码的导师。哈夫曼使用自底向上的方法构建二叉树，避免了次优算法Shannon

7、-Fano编码的最大弊端自顶向下构建树。哈夫曼压缩是个无损的压缩算法，一般用来压缩文本和程序文件。哈夫曼压缩属于可变代码长度算法一族。意思是个体符号（例如，文本文件中的字符）用一个特定长度的位序列替代。因此，在文件中出现频率高的符号，使用短的位序列，而那些很少出现的符号，则用较长的位序列。利用赫夫曼编码进行通信可以大大提高信道利用率，缩短信息传输时间，降低传输成本。这要求在发送端通过一个编码系统对待传输数据预先编码，在接收端将传来的数据进行译码（复原）。对于双工信道（即可以双向传输信息的信道），每端都需要一个完整的编/译码系统。1.2问题分析哈夫曼在上世纪五十年代初就提出这种编码时，根据字符出

8、现的概率来构造平均长度最短的编码。它是一种变长的编码。哈夫曼编码应用广泛，如JPEG中就应用了哈夫曼编码。在编码中，若各码字长度严格按照码字所对应符号出现概率的大小的逆序排列，则编码的平均长度是最小的。构造好哈夫曼树后，就可根据哈夫曼树进行编码。然而怎样构造一棵哈夫曼树呢？最具有一般规律的构造方法就是哈夫曼算法。字符根据其出现的概率作为权值构造一棵哈夫曼树后，经哈夫曼编码得到的对应的码值。只要使用同一棵哈夫曼树，就可把编码还原成原来那组字符。显然哈夫曼编码是前缀编码，即任一个字符的编码都不是另一个字符的编码的前缀，否则，编码就不能进行翻译。分析此次设计，是关于实现利用哈夫曼算法编码和译码功能的

9、问题，要求能重复地显示并处理以下项目，即构造哈夫曼树，编码及译码几项功能，直到选择退出为止。本次设计就是为这样的一个哈夫曼的编/译码器。1.3设计任务主要内容：设计一个利用哈夫曼算法的编码和译码系统，可以接收从键盘输入的字符集大小、字符和权值信息，创建哈夫曼树生成哈夫曼编码并能对其进行解码。功能指标：1.使用二叉链表存储结构，主要功能有：建立哈夫曼树、利用已建好的哈夫曼树（如不在内存，则从文件hfmTree中读入），对文件中的正文进行编码、对文件中的代码进行译码、显示输出等功能；2. 用下表给出的字符集和频度的实际统计数据建立哈夫曼树，并实现以下报文的编码和译码：“THIS PROGRAM I

10、S MY FAVORITE”.表1.1 字符集和频度字符ABCDEFGHIJKLM频度1866413223210321154757153220字符NOPQRSTUVWXYZ频度5763151485180238181161算法对于合法的输入数据都能产生满足规格说明要求的结果；3. 算法对于精心选择的典型、苛刻而带有刁难性的几组输入数据能够得出满足规格说明要求的结果；对算法实现过程中的异常情况能给出有效信息。1.4总体结构本程序主要分为3个模块：主模块，编码模块，译码模块。主模块：程序的主体部分，分别调用各个模块，实现各项功能。编码模块：对每个出现的字符进行编码。译码模块：将已有编码译成字符，使之

11、可以直接被读出。2总体设计2.1总体设计思想、设计方案的选择哈夫曼编码所以能产生较短的码文，是因为哈夫曼树具有最小加权路径长度的二叉树。如果叶结点的权值恰好是某个需编码的文本中各字符出现的次数，则编码后文本的长度就是该哈夫曼树的加权路径长度。译码过程为自做向右逐一扫描码文，并从哈夫曼树的根开始，将扫到的二进制位串中的相邻位与哈夫曼树上标的0，1相匹配，以确定一条从根到叶子结点的路径，一旦到达叶子，则译出了一个字符。再回到树根，从二进位串的下一位开始继续译码。2.1.1 最优二叉树（Huffman树） 首先给出路径和路径长度的概念。从树中一个结点到另一个结点之间的分支构成这两个结点之间的路径，路

12、径上的分支数目称作路径长度。树的路径长度是从树根到每一结点的路径长度之和。结点的带权路径长度为从该结点到树根之间的路径长度与节点上权的乘积。树的带权路径长度为书中所有叶子结点的带权路径长度之和，通常记做。那么假设有个权值，试构造一棵有个叶子结点的二叉树，每个叶子结点带权为，则其中带权路径长度 最小的二叉树称作最优二叉树或Huffman 树。2.1.2构造哈夫曼树的步骤步骤如下：1、 对给定的n个权值W1,W2,W3,.,Wi,.,Wn构成n棵二叉树的初始集合F=T1,T2,T3,.,Ti,.,Tn，其中每棵二叉树Ti中只有一个权值为Wi的根结点，它的左右子树均为空。（为方便在计算机上实现算法，

13、一般还要求以Ti的权值Wi的升序排列。）； 2、 选取左右子树：在F中选取两棵根结点权值最小的树作为新构造的二叉树的左右子树，新二叉树的根结点的权值为其左右子树的根结点的权值之和。3、 删除左右子树：从F中删除这两棵树，并把这棵新的二叉树同样以升序排列加入到集合F中。 4、重复2、3两步：重复2和3，直到集合F中只有一棵二叉树为止。2.1.3数据结构的选择为了建立哈夫曼树以及实现哈夫曼编码以及译码，因此我们选择了结点结构体，利用这一结构体，我们定义了一个结构体数组和一个树根指针，数组用来纪录输入数据的多少，树根指针用来连接哈夫曼树。从程序中可以看到使用哈夫曼算法构造哈夫曼树过程，是从n棵知识一

14、个根结点的树组成的森林开始的。在算法执行中，哈夫曼树是由若干棵树组成的森林，通过不断地合并树，最后得到一棵哈夫曼树。2.2结构设计2.2.1结构体存储表示typedef struct char ch; unsigned int weight;unsigned int parent, lchild, rchild;HTNode,*HuffmanTree; /动态分配数组存储哈夫曼树typedef char *HuffmanCode; /动态分配数组存储哈弗曼编2.2.2主函数模块在主函数实现过程，使用开关语句switch（）函数对函数的各模块调用，使得函数的运行效率大大提高，主函数实现功能用如下

15、算法表示。main()int num; char *str= abcdefghijklmnopqrstuvwxyz; while(1)printf(n);printf( *赫夫曼编码/译码器 *n); printf( *1 使用默认初始化 *n); printf( *2 使用自定义初始化 *n); printf( *3 编码 *n); printf( *4 译码 *n);printf( *5 退出 *n)printf(n); printf(请输入您要操作的步骤：);scanf(%d,&num);getchar( );switch(num)case 1 :HuffmanCoding(HT,wei

16、,27,str);break;case 2:Customize();break;case 3 :TexttoCode();break;case 4 :CodetoText();break;case 5 :exit(0);break;return 0;2.2.3系统结构图程序开始定义一个结构体用来动态分配数组存储哈夫曼树和哈夫曼编码，然后定义各个函数下的变量，初始化程序设计任务中所给字符的权值，通过选择函数void Select( )选择所给字符中权值最小的两个字符作为叶子节点，运用循环函数依次比较把权值最小的节点赋给定义的变量，同时运用void HuffmanCoding( )函数对字母编码，

17、void Customize( )函数用来用户自定义权值和字符，void TexttoCode( )函数进行编码，void CodetoText( )函数进行译码，最后使用主函数对给函数块进行调用，实现程序的各个功能。如下是哈夫曼编/译码器结构框图。默认初始化自定义初始化编码译码退出主函数 图2.1 哈夫曼编/译码器结构框图3详细设计3.1构造哈夫曼树如下流程图（图3.1）为构造哈夫曼树的过程，输入字符的次数为权值对每个结点赋值，构造哈夫曼树。NY读入字符次数并令i=2n-1找出最小和次小树s1,s2两树合并成新树n+ii减1i为0开始结束图3.1 构造哈夫曼树3.2哈夫曼编码如下流程图（图3

18、.2）是对字符进行哈夫曼编码的过程，将字符转化为哈夫曼编码。记编码0将得到的编码存储左节点?=该节点第一个字符，i=1=i=n记编码1i=i+1开始NN节点?=根节点结束YYNY N图3.2 编码模块流程图4系统实现与测试4.1错误分析在此程序调试过程中主要遇到以下几类问题：1、本程序运用了对文件进行操作，一定要注意操作文件的位置，我在做此程序时就是因为操作的文件位置错了导致程序无法正常运行。2、在函数内部有时需要多次定义参数，注意参数的作用域，而且注意引用调用和传值调用的区别，如果不能正确的修改实参的值，就会导致程序运行错误。3、本程序用到的外部函数较多，在调用时一定要注意传入的参数是否符合

19、函数的定义，而且位置也不能错，这是引用函数要注意的一点。4、刚开始时清屏函数运用出错，导致操作界面消失，使用户无法操作，因此，在使用一些函数是一定要注意。4.2运行结果运行程序首先出现界面图，如图4.1所示图4.1 界面图选择操作1后，默认初始化，生成哈夫曼树。系统会显示每个字符的哈夫曼编码，但由于截图不方便，因此选择操作2用户自定义初始化，输入相应的字符个数大小，字符和权值，生成哈夫曼树。系统会显示每个字符的哈夫曼编码，如图4.2所示。图4.2 程序运行截图图4.2 程序运行截图选择操作3后，系统会显示用哈夫曼编码翻译成的字符，显示以下界面（图4.3）供用户选择图4.3 程序运行截图选择操作

20、4后，系统会显示用哈夫曼编码翻译成的字符，显示以下界面（图4.4）供用户选择图4.4 程序运行截图选择操作5后，退出系统，显示以下界面（图4.5）图4.5 程序运行截图5 总结通过此次课程设计，使我们更加扎实的掌握了有关数据结构方面的知识，在设计过程中虽然遇到了一些问题，但经过一次又一次的思考，一遍又一遍的检查终于找出了原因所在，也暴露出了前期我在这方面的知识欠缺和经验不足。实践出真知，通过亲自动手制作，使我们掌握的知识不再是纸上谈兵。在课程设计过程中，我们不断发现错误，不断改正，不断领悟，不断获取。在设计中遇到了很多问题，最后在谢老师的指导下，终于迎刃而解。在今后社会的发展和学习实践过程中，

21、一定要不懈努力，不能遇到问题就想到要退缩，一定要不厌其烦的发现问题所在，然后一一进行解决，只有这样，才能成功的做成想做的事，才能在今后的道路上劈荆斩棘，而不是知难而退.课程设计诚然是一门专业课，给我很多专业知识以及专业技能上的提升，同时又是一门辩思课，给了我很多思，给了我莫大的空间。同时，设计让我感触很深。使我对抽象的理论有了具体的认识。我认为，在这学期的课设中，不仅培养了我独立思考、动手操作的能力，在各种其它能力上也都有了提高。更重要的是，在实验课上，我们学会了很多学习的方法。而这是日后最实用的，真的是受益匪浅。在这两周里，可以说得是苦多于甜，但是可以学到很多很多的东西，同时不仅可以巩固了以

22、前所学过的知识，而且学到了很多在书本上所没有学到过的知识。通过这次课程设计使我懂得了理论与实际相结合是很重要的，只有理论知识是远远不够的，只有把所学的理论知识与实践相结合起来，从理论中得出结论，从而提高自己的实际动手能力和独立思考的能力。在设计的过程中遇到问题，可以说得是困难重重，但可喜的是最终都得到了解决。 课设过程中，也对团队精神的进行了考察，让我们在合作起来更加默契，在成功后一起体会喜悦的心情。果然是团结就是力量，只有互相之间默契融洽的配合才能换来最终完美的结果。此次设计也让我明白了思路即出路，有什么不懂不明白的地方要及时请教或上网查询，只要认真钻研，动脑思考，动手实践，就没有弄不懂的知

23、识。参考文献1 谭浩强.C程序设计教程M.清华大学出版社，2007.062 赵永哲，李雄飞.C语言程序设计M.科学出版社，2006.043 夏宽理，赵子正.C语言程序设计M.中国铁道出版社，2006.054 谭浩强编著.C程序设计M.清华大学出版社，1991.075 藤国文编著.数据结构课程设计M.清华大学出版社，2010.026 严蔚敏，吴伟民编著.数据结构（C语言版）M.清华大学出版社，2006.037 苏德富.计算机算法设计与分析M.清华大学出版社，1991.048 曹新谱.算法设计与分析M.湖南科学技术出版社，1984.079 胡学刚.算法与数据结构设计指导M.清华大学出版社，1999

24、.0610 张乃孝.数据结构C+与面向对象的途径M.高等教育出版社，2001.07致 谢在这次课程设计的撰写过程中，我们之所以能够顺利的完成我们的数据结构课程设计，要感谢我们的指导老师谢老师，我们的成功离不开她的谆谆教导，在这短暂而又忙碌的两周里，我们学习收获了很多。首先我们要感谢谢老师在课程设计上给予我们的指导、提供给我们的支持和帮助，这是我们能顺利完成这次报告的主要原因，更重要的是老师帮我们解决了许多技术上的难题，让我能把系统做得更加完善。在此期间，我不仅学到了许多新的知识，而且也开阔了视野，提高了自己的设计能力。 其次，我要感谢帮助过我的同学，他们也为我解决了不少我不太明白的设计上的难题

25、。同时也感谢学院为我提供良好的做毕业设计的环境。 最后再一次感谢所有在设计中曾经帮助过我的良师益友和同学。我们会在以后的求学路上再接再厉，不断完善自我，提高自我，为以后顺利的步入社会打下结实的基础。由衷的感谢老师和同学们的帮助。附 录源代码程序：#include#include#include#includetypedef struct char ch; unsigned int weight;unsigned int parent, lchild, rchild;HTNode,*HuffmanTree;typedef char *HuffmanCode;int wei27=186,64,13

26、,22,32,103,21,15,47,57,1,5,32,20,57,63,15,1,48,51,80,23,8,18,1,16,1; /186为空格的权值int flag54;static int n,m;HuffmanTree HT;HuffmanCode HC;void Select(HuffmanTree HT, int j,int &s1,int &s2) /在1到j 中 选择双亲为0，并且weight最小的两个子叶节点 ,其序号分别为s1,s2int i,mark=0;for(i=1;i=j;i+) /for循环找到权值最小的节点 if(flagi=0&mark=0) /第一次

27、把第一个flag未改变的节点编号 给s1s1=i;mark=1;else if(HTi.weightHTs1.weight&flagi=0) s1=i; /通过循环把最小权值节点给S1mark=0; /mark 归零flags1=1; /把s1节点的标记改为1for(i=1;i=j;i+)if(flagi=0&mark=0)s2=i;mark=1;else if(HTi.weightHTs2.weight&flagi=0)s2=i;flags2=1;void HuffmanCoding(HuffmanTree &HT, int w, int s,char *ch) /*1*哈夫曼初始化进行对字

28、母编码n=s;int i, j, s1, s2, start;char *cd;unsigned int c, f;for(i=0;is*2;i+)flagi=0; /每个对应节点标记为0 选择最小节点时 被选中标记为1if (n=1) return;m=2*n-1; /n个子叶 2*n-1个节点HT=(HuffmanTree)malloc(m+1) * sizeof(HTNode);/0号单元未用for (i=1; i=n; i+)/哈夫曼树初始化HTi.weight=wi-1; /w对应的权值依次赋给HT每一个叶子节点HTi.ch=chi-1; /ch对应的字母依次赋给 没一个叶子节点HT

29、i.parent=0;HTi.lchild=0;HTi.rchild=0;for (; i=m; i+)HTi.weight=0;HTi.parent=0;HTi.lchild=0;HTi.rchild=0;HTi.ch= ;printf(n哈夫曼树的构造过程如下所示：n);for (i=n+1; i=m; 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;printf(n 结点 cha

30、r weight parent lchild rchild); for (j=1; j=i-1; j+)printf(n%4d%6c%8d%8d%8d%8d,j,HTj.ch,HTj.weight,HTj.parent,HTj.lchild, HTj.rchild);/- 从叶子到根逆向求每个字符的哈夫曼编码 -HC=(HuffmanCode)malloc(n+1)*sizeof(char *);cd = (char *)malloc(n*sizeof(char);cdn-1 =0;for (i=1; i=n; +i)start = n-1;for (c=i, f=HTi.parent; f!

31、=0; c=f, f=HTf.parent)if (HTf.lchild=c) cd-start=0;else cd-start = 1;HCi=(char *)malloc(n-start)*sizeof(char);strcpy(HCi, &cdstart);printf(n每个字母对应的哈夫曼编码:n);for(int a=1; a1:);scanf(%d,&n);for(int i=0;in;i+)printf(请输入第%d个字母及对应的权值:,i+1);scanf(%s %d,&chi,&weighti);HuffmanCoding(HT,weight,n,ch);void Text

32、toCode() /*3编码*char str50;int j;if(HT = NULL)printf(请先进行初始化!n);return;printf(请输入要编码的文本(小写英文字母):n);gets(str);printf(编码结果如下:n);int p =strlen(str);for(int i=1; i=p ; i+)for(j=1; j=n; j+)if(stri-1 =HTj.ch)printf(%s,HCj);break;printf(n);void CodetoText() /*4译码* int i=1,j,key;char str100;if(HT = NULL)prin

33、tf(请先进行初始化!n);return;printf(n每个字母对应的哈夫曼编码:n);for(int a=1; a=n; a+)printf(%c:,HTa.ch);printf(%s ,HCa);if(a%5=0)printf(n);printf(n请输入哈夫曼编码:n);scanf(%s,str);j=strlen(str);key=m;printf(哈夫曼编码译码如下:n);while( i= j)while(HTkey.lchild != 0)if(stri-1 =0)key=HTkey.lchild;i+; continue;if(stri-1 =1)key=HTkey.rchi

34、ld;i+; continue;printf(%c,HTkey.ch);key=m;printf(n);main()int num; char *str= abcdefghijklmnopqrstuvwxyz; / while(1)printf(n);printf( *赫夫曼编码/译码器 *n); printf( *1 使用默认初始化 *n); printf( *2 使用自定义初始化 *n); printf( *3 编码 *n); printf( *4 译码 *n);printf( *5 退出 *n);printf(n); printf(请输入您要操作的步骤：);scanf(%d,&num);getchar();switch(num)case 1 :HuffmanCoding(HT,wei,27,str);break;case 2:Customize();break;case 3 :TexttoCode();break;case 4 :CodetoText();break;case 5 :exit(0);break;return 0;