哈夫曼编译码器

哈夫曼编译码器 摘 要 随着计算机的普遍应用与日益发展,其应用早已不局限于简单的数值运算,而涉及到问题的分析,数据结构框架的 设计 领导形象设计圆作业设计ao工艺污水处理厂设计附属工程施工组织设计清扫机器人结构设计 以及设计最短路线等复杂的非数值处理和操作。算法与数据结构的学习就是为以后利用计算机资源高效地开发非数值处理的计算机程序打下坚实的理论,方法和技术基础。 利用哈夫曼编码进行通信可以大大提高信道利用率，缩短信息传输时间，降低传输成本。但是，这要求在发送端通过一个编码系统对待传数据预先编码，在接收端将传来的数据进行译码(复原)。对于双工通信(即可以双向传输信息的信道)，每端都需要一个完整的编/译码系统，试设计一个哈夫曼编码系统。 关键词:Huffman编码树;编码;译码 Abstract With 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 algorithm 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, reduce 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 needs a complete encoding / decoding system, try to design a Huffman coding system. Keywords: Huffman coding tree; coding;decoding 目 录 1概述 ................................................................ 1 1.1设计背景 ....................................................... 1 1.2问题分析 ....................................................... 1 1.3设计任务 ....................................................... 2 1.4总体结构 ....................................................... 2 2总体设计 ............................................................ 3 2.1总体设计思想、设计 方案 气瓶 现场处置方案 .pdf气瓶 现场处置方案 .doc见习基地管理方案.doc关于群访事件的化解方案建筑工地扬尘治理专项方案下载 的选择 ................................... 3 2.1.1 最优二叉树(Huffman树) ................................. 3 2.1.2构造哈夫曼树的步骤 ....................................... 3 2.1.3数据结构的选择 ........................................... 4 2.2结构设计 ....................................................... 4 2.2.1结构体存储 表 关于同志近三年现实表现材料材料类招标技术评分表图表与交易pdf视力表打印pdf用图表说话 pdf 示 ........................................... 4 2.2.2主函数模块 ............................................... 4 2.2.3系统结构图 ............................................... 5 3详细设计 ........................................... 错误～未定义书签。 3.1构造哈夫曼树 .................................. 错误～未定义书签。 3.2哈夫曼编码 ................................... 错误～未定义书签。 4系统实现与测试 ...................................................... 9 4.1错误分析 ....................................................... 9 4.2运行结果 ...................................................... 9 5 总结 ............................................................... 12 参考文献 ............................................................. 13 致 谢 ............................................................... 14 附 录 ............................................................... 15 1概述 1.1设计背景 1951年，哈夫曼和他在MIT信息论的同学需要选择是完成学期报告还是期末考试。导师Robert M. Fano给他们的学期报告的题目是，寻找最有效的二进制编码。由于无法证明哪个已有编码是最有效的，哈夫曼放弃对已有编码的研究，转向新的探索，最终发现了基于有序频率二叉树编码的想法，并很快证明了这个方法是最有效的。 由于这个算法，学生终于青出于蓝，超过了他那曾经和信息论创立者香农共同研究过类似编码的导师。哈夫曼使用自底向上的方法构建二叉树，避免了次优算法Shannon-Fano编码的最大弊端??自顶向下构建树。哈夫曼压缩是个无损的压缩算法，一般用来压缩文本和程序文件。哈夫曼压缩属于可变代码长度算法一族。意思是个体符号(例如，文本文件中的字符)用一个特定长度的位序列替代。因此，在文件中出现频率高的符号，使用短的位序列，而那些很少出现的符号，则用较长的位序列。 利用赫夫曼编码进行通信可以大大提高信道利用率，缩短信息传输时间，降低传输成本。这要求在发送端通过一个编码系统对待传输数据预先编码，在接收端将传来的数据进行译码(复原)。对于双工信道(即可以双向传输信息的信道)，每端都需要一个 码系统。 完整的编/译 1.2问题分析 哈夫曼在上世纪五十年代初就提出这种编码时，根据字符出现的概率来构造平均长度最短的编码。它是一种变长的编码。哈夫曼编码应用广泛，如JPEG中就应用了哈夫曼编码。在编码中，若各码字长度严格按照码字所对应符号出现概率的大小的逆序排列，则编码的平均长度是最小的。构造好哈夫曼树后，就可根据哈夫曼树进行编码。然而怎样构造一棵哈夫曼树呢,最具有一般规律的构造方法就是哈夫曼算法。字符根据其出现的概率作为权值构造一棵哈夫曼树后，经哈夫曼编码得到的对应的码值。只要使用同一棵哈夫曼树，就可把编码还原成原来那组字符。显然哈夫曼编码是前缀编码，即任一个字符的编码都不是另一个字符的编码的前缀，否则，编码就不能进行翻译。 分析此次设计，是关于实现利用哈夫曼算法编码和译码功能的问题，要求能重复地显示并处理以下项目，即构造哈夫曼树，编码及译码几项功能，直到选择退出为止。本次设计就是为这样的一个哈夫曼的编/译码器。 1.3设计任务 主要内容:设计一个利用哈夫曼算法的编码和译码系统，可以接收从键盘输入的字符集大小、字符和权值信息，创建哈夫曼树生成哈夫曼编码并能对其进行解码。 使用二叉链表存储结构，主要功能有:建立哈夫曼树、利用已建好的功能指标:1. 哈夫曼树(如不在内存，则从文件hfmTree中读入)，对文件中的正文进行编码、对文件中的代码进行译码、显示输出等功能; 2.用下表给出的字符集和频度的实际统计数据建立哈夫曼树，并实现以下报文的编码和译码:“THIS PROGRAM IS MY FAVORITE”. 表1.1 字符集和频度 字符 A B C D E F G H I J K L M 频度 186 64 13 22 32 103 21 15 47 57 1 5 32 20 字符 N O P Q R S T U V W X Y Z 频度 57 63 15 1 48 51 80 23 8 18 1 16 1 算法对于合法的输入数据都能产生满足规格 说明 关于失联党员情况说明岗位说明总经理岗位说明书会计岗位说明书行政主管岗位说明书 要求的结果; 3.算法对于精心选择的典型、苛刻而带有刁难性的几组输入数据能够得出满足规格说明要求的结果;对算法实现过程中的异常情况能给出有效信息。 1.4总体结构 本程序主要分为3个模块:主模块，编码模块，译码模块。 主模块:程序的主体部分，分别调用各个模块，实现各项功能。 编码模块:对每个出现的字符进行编码。 译码模块:将已有编码译成字符，使之可以直接被读出。 2总体设计 2.1总体设计思想、设计方案的选择 哈夫曼编码所以能产生较短的码文，是因为哈夫曼树具有最小加权路径长度的二叉树。如果叶结点的权值恰好是某个需编码的文本中各字符出现的次数，则编码后文本的长度就是该哈夫曼树的加权路径长度。译码过程为自做向右逐一扫描码文，并从哈夫曼树的根开始，将扫到的二进制位串中的相邻位与哈夫曼树上标的0，1相匹配，以确定一条从根到叶子结点的路径，一旦到达叶子，则译出了一个字符。再回到树根，从二进位串的下一位开始继续译码。 2.1.1 最优二叉树(Huffman树) 首先给出路径和路径长度的概念。从树中一个结点到另一个结点之间的分支构成这两个结点之间的路径，路径上的分支数目称作路径长度。树的路径长度是从树根到每一结点的路径长度之和。结点的带权路径长度为从该结点到树根之间的路径长度与节点上权的乘积。树的带权路径长度为书中所有叶子结点的带权路径长度之和，通常记做n WPL,{w,w,,,,w}。那么假设有个权值，试构造一棵有个叶子结点的二nn,wl12nkk,1k WPL叉树，每个叶子结点带权为，则其中带权路径长度 最小的二叉树称作最优二叉wi 树或Huffman 树。 2.1.2构造哈夫曼树的步骤 步骤如下: 1、对给定的n个权值{W1,W2,W3,...,Wi,...,Wn}构成n棵二叉树的初始集合F={T1,T2,T3,...,Ti,...,Tn}，其中每棵二叉树Ti中只有一个权值为Wi的根结点，它的左右子树均为空。(为方便在计算机上实现算法，一般还要求以Ti的权值Wi的升序排列。); 2、选取左右子树:在F中选取两棵根结点权值最小的树作为新构造的二叉树的左右子树，新二叉树的根结点的权值为其左右子树的根结点的权值之和。 3、删除左右子树:从F中删除这两棵树，并把这棵新的二叉树同样以升序排列加入到集合F中。 4、重复2、3两步:重复2和3，直到集合F中只有一棵二叉树为止。 2.1.3数据结构的选择 为了建立哈夫曼树以及实现哈夫曼编码以及译码，因此我们选择了结点结构体，利 用这一结构体，我们定义了一个结构体数组和一个树根指针，数组用来纪录输入数据的 多少，树根指针用来连接哈夫曼树。从程序中可以看到使用哈夫曼算法构造哈夫曼树过 程，是从n棵知识一个根结点的树组成的森林开始的。在算法执行中，哈夫曼树是由若 干棵树组成的森林，通过不断地合并树，最后得到一棵哈夫曼树。 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()函数对函数的各模块调用，使得函数 的运行效率大大提高，主函数实现功能用如下算法表示。 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; } 2.2.3系统结构图 程序开始定义一个结构体用来动态分配数组存储哈夫曼树和哈夫曼编码，然后定义 各个函数下的变量，初始化程序设计任务中所给字符的权值，通过选择函数void Select( ) 选择所给字符中权值最小的两个字符作为叶子节点，运用循环函数依次比较把权值最小的节点赋给定义的变量，同时运用void HuffmanCoding( )函数对字母编码，void Customize( )函数用来用户自定义权值和字符，void TexttoCode( )函数进行编码，void CodetoText( )函数进行译码，最后使用主函数对给函数块进行调用，实现程序的各个功能。如下是哈夫曼编/译码器结构框图。 主函数 默 认 译 自定 编 退 初 码 义初 码 出 始 始化 化 图2.1 哈夫曼编/译码器结构框图 3详细设计 3.1构造哈夫曼树 如下 流程 快递问题件怎么处理流程河南自建厂房流程下载关于规范招聘需求审批流程制作流程表下载邮件下载流程设计 图(图3.1)为构造哈夫曼树的过程，输入字符的次数为权值对每个结点 赋值，构造哈夫曼树。 开始 读入字符次数并令i=2n-1 Y i为0 N 找出最小和次小树s1,s2 两树合并成新树n+i i减1 结束 图3.1 构造哈夫曼树 3.2哈夫曼编码 如下流程图(图3.2)是对字符进行哈夫曼编码的过程，将字符转化为哈夫曼编码。 开始 第一个字符，i=1 N =i<=n Y N 节点?=根节点 Y N 左节点?=该节点 N 将得到的编码存储 Y 记编码0 记编码1 i=i+1 结束 图3.2 编码模块流程图 4系统实现与测试 4.1错误分析 在此程序调试过程中主要遇到以下几类问题: 1、本程序运用了对文件进行操作，一定要注意操作文件的位置，我在做此程序时就是因为操作的文件位置错了导致程序无法正常运行。 2、在函数内部有时需要多次定义参数，注意参数的作用域，而且注意引用调用和传值调用的区别，如果不能正确的修改实参的值，就会导致程序运行错误。 3、本程序用到的外部函数较多，在调用时一定要注意传入的参数是否符合函数的定义，而且位置也不能错，这是引用函数要注意的一点。 4、刚开始时清屏函数运用出错，导致操作界面消失，使用户无法操作，因此，在使用一些函数是一定要注意。 4.2运行结果 运行程序首先出现界面图，如图4.1所示 图4.1 界面图 选择操作1后，默认初始化，生成哈夫曼树。系统会显示每个字符的哈夫曼编码，但由于截图不方便，因此选择操作2用户自定义初始化，输入相应的字符个数大小，字符和权值，生成哈夫曼树。系统会显示每个字符的哈夫曼编码，如图4.2所示。 图4.2 程序运行截图 图4.2 程序运行截图 选择操作3后，系统会显示用哈夫曼编码翻译成的字符，显示以下界面(图4.3) 供用户选择 图4.3 程序运行截图 选择操作4后，系统会显示用哈夫曼编码翻译成的字符，显示以下界面(图4.4)供用户选择 图4.4 程序运行截图 选择操作5后，退出系统，显示以下界面(图4.5) 图4.5 程序运行截图 5 总结 通过此次课程设计，使我们更加扎实的掌握了有关数据结构方面的知识，在设计过程中虽然遇到了一些问题，但经过一次又一次的思考，一遍又一遍的检查终于找出了原因所在，也暴露出了前期我在这方面的知识欠缺和经验不足。实践出真知，通过亲自动手制作，使我们掌握的知识不再是纸上谈兵。在课程设计过程中，我们不断发现错误，不断改正，不断领悟，不断获取。在设计中遇到了很多问题，最后在谢老师的指导下，终于迎刃而解。在今后社会的发展和学习实践过程中，一定要不懈努力，不能遇到问题就想到要退缩，一定要不厌其烦的发现问题所在，然后一一进行解决，只有这样，才能成功的做成想做的事，才能在今后的道路上劈荆斩棘，而不是知难而退. 课程设计诚然是一门专业课，给我很多专业知识以及专业技能上的提升，同时又是一门辩思课，给了我很多思，给了我莫大的空间。同时，设计让我感触很深。使我对抽象的理论有了具体的认识。我认为，在这学期的课设中，不仅培养了我独立思考、动手操作的能力，在各种其它能力上也都有了提高。更重要的是，在实验课上，我们学会了很多学习的方法。而这是日后最实用的，真的是受益匪浅。 在这两周里，可以说得是苦多于甜，但是可以学到很多很多的东西，同时不仅可以巩固了以前所学过的知识，而且学到了很多在书本上所没有学到过的知识。通过这次课程设计使我懂得了理论与实际相结合是很重要的，只有理论知识是远远不够的，只有把所学的理论知识与实践相结合起来，从理论中得出结论，从而提高自己的实际动手能力和独立思考的能力。在设计的过程中遇到问题，可以说得是困难重重，但可喜的是最终都得到了解决。 课设过程中，也对团队精神的进行了考察，让我们在合作起来更加默契，在成功后一起体会喜悦的心情。果然是团结就是力量，只有互相之间默契融洽的配合才能换来最终完美的结果。此次设计也让我明白了思路即出路，有什么不懂不明白的地方要及时请教或上网查询，只要认真钻研，动脑思考，动手实践，就没有弄不懂的知识。 参考文献 [1] 谭浩强.C程序设计教程[M].清华大学出版社，2007.06 [2] 赵永哲，李雄飞.C语言程序设计[M].科学出版社，2006.04 [3] 夏宽理，赵子正.C语言程序设计[M].中国铁道出版社，2006.05 [4] 谭浩强编著.C程序设计[M].清华大学出版社，1991.07 [5] 藤国文编著.数据结构课程设计[M].清华大学出版社，2010.02 [6] 严蔚敏，吴伟民编著.数据结构(C语言版)[M].清华大学出版社，2006.03 [7] 苏德富.计算机算法设计与分析[M].清华大学出版社，1991.04 [8] 曹新谱.算法设计与分析[M].湖南科学技术出版社，1984.07 [9] 胡学刚.算法与数据结构设计指导[M].清华大学出版社，1999.06 [10] 张乃孝.数据结构C++与面向对象的途径[M].高等教育出版社，2001.07 致 谢 在这次课程设计的撰写过程中，我们之所以能够顺利的完成我们的数据结构课程设计，要感谢我们的指导老师谢老师，我们的成功离不开她的谆谆教导，在这短暂而又忙碌的两周里，我们学习收获了很多。首先我们要感谢谢老师在课程设计上给予我们的指导、提供给我们的支持和帮助，这是我们能顺利完成这次报告的主要原因，更重要的是老师帮我们解决了许多技术上的难题，让我能把系统做得更加完善。在此期间，我不仅学到了许多新的知识，而且也开阔了视野，提高了自己的设计能力。 其次，我要感谢帮助过我的同学，他们也为我解决了不少我不太明白的设计上的难题。同时也感谢学院为我提供良好的做毕业设计的环境。 最后再一次感谢所有在设计中曾经帮助过我的良师益友和同学。我们会在以后的求学路上再接再厉，不断完善自我，提高自我，为以后顺利的步入社会打下结实的基础。 由衷的感谢老师和同学们的帮助。 附 录 源代码程序: #include #include #include #include typedef struct { char ch; unsigned int weight; unsigned int parent, lchild, rchild; }HTNode,*HuffmanTree; typedef char **HuffmanCode; int wei[27]={186,64,13,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 flag[54]; static int n,m; HuffmanTree HT; HuffmanCode HC; void Select(HuffmanTree HT, int j,int &s1,int &s2) { //在1到j 中 选择双亲为0，并且weight最小的两个子叶节点 ,其序号分别为 s1,s2 int i,mark=0; for(i=1;i<=j;i++) //for循环找到权值最小的节点 { if(flag[i]==0&&mark==0) //第一次 把第一个flag未改变的节点编号 给s1 { s1=i;mark=1; } else if(HT[i].weight1:"); scanf("%d",&n); for(int i=0;i