哈夫曼编码的实现.docx

《哈夫曼编码的实现.docx》由会员分享，可在线阅读，更多相关《哈夫曼编码的实现.docx（15页珍藏版）》请在taowenge.com淘文阁网|工程机械CAD图纸|机械工程制图|CAD装配图下载|SolidWorks_CaTia_CAD_UG_PROE_设计图分享下载上搜索。

1、河南工程学院数据结构与算法课程设计成果报告哈夫曼编码的实现2014年12月29日3程序清单1、字符串统计源程序：int count (charts, int*weight, int n)int I, j, temp, k=0, p;for(i=0;in&si!=0 ;i+)temp=l;for (j=0; jn; j+)/*遍历相同的字母*/ if (sj=si&i!=j)temp+;for (p=j ; pn; p+) /*删除相同的字母*/sp=sp+l;n; j;)Weight k+ =temp; /*temp 作为权值赋给 weight 数组*/)Return I;/*返回权值个数*/

2、)2、哈夫曼树建立源程序void Haffman (int weight , int n, HaffNode haffTree 口)/*建立叶节点个数为 n,权值数组为weight的哈夫曼树Haff Tree*/int I, j, ml, m2, xl, x2;For (i=0;i2*n-l;i+)if(in)haffTreei. flag=O;weighti;else haffTreei. weight=0;haffTreei. parent=0;haffTreei. flag=0;haffTreei. leftChild=-l;haffTreei. rightChild=-l;)/*构造哈

3、夫曼树haffTree的n-1个非叶节点*/For(i=0;In-l;i+)m 1 =m2=Max V alue;Xl=x2=0;For(j=0;jn+I;j+)if(haffTreej.weightml&haffTreej,flag=O)m2=ml;X2=xl;M l=haffT ree j .weightr;xi=j； )Else if(haffTreej.weightm2&haffTreej,flag-0)m2=haffTreej.weightr;X2=j;)/*将找出的两颗权值最小的子树合并为一颗子树/*haffTreexl. parent=n+i;haffTreex2. parent

4、=n+i;haffTreexl. flag=l;haffTreex2. flag=lhaffTreen+i. weight=haffTreex1. weight+ haffTreex2. weight;haffTreen+i. leftChild=xl;haffTreen+i. rightChild=x2;)3、哈夫曼树编码函数Void HaffmanCode(HaffNode haflTree,int n,Code haffCodef)/*有n个结点的哈夫曼haffTree构造哈夫曼编码haffCode*/ Codecd=(Code*)malloc(sizeof(Code);Int Ij,c

5、hild,parent;/*求n个结点的哈夫曼编码*/For(i=0;in;i+)cd.start=n-l;cd.weight= haffTreei. weight;child=i;parent= haffTreechild. parent/*由叶节点 直到根节点*/ while (parent!=0)if(haffTreeparent. leftChild=child)Cd. bit cd. start =0; /*左孩子分支编码 0/*Else Cd. bit cd. start =1; /*左孩子分支编码 1/*cd. start-;child=parent;parent=haffTre

6、echild. parent;)For (j= cd. start+1;jMaxN)printf (给出的n越界，修改MaxN! n);Exit ;Haffman(weight, n, myHaffTree);HaffmanCode(myHaffTree, n, myHaffCode);For (i=0;in;i+)printf ( , myHaffCodei. weight);For(j=myHaffCodei. start+1;jn;j+)Printf( %dv , myHaffCodei. bitj);Printf ( “n);4测试4.1测试数据测试数据三组：AAAABBBCCD (判

7、断连续的字符串是否可行)AABBAABCDC (判断间段的字符串是否可行)AAAABBBCCD (判断含空格的字符串是否可行)4. 2测试结果分析1、count函数：最坏情况下时间复杂度为0 (n*n*n),调试时必须给定 字符串的长度，否那么会输出乱码，这很不方便。只要在条件语句中加上“si!=“0”, 就能解决。同时对于含空格的字符串不能正确统计，因为输入字符串是以scanf 的形式输入，scanf遇到空格自动结束，将scanf改为gets即可，出现个gets (s)；2、HaffmanCode函数在最坏情况下计算的次数为n* (3*n-l)，时间复杂为0 (n*n) HaffmanCod

8、e函数在书写时要注意定义变量的位置。输入字符串W-410111110W=3W-2Pi*ess any key toW=1 cont inue_图4-1判断连续字符串是否可行程序的运行结果如下图105总结通过这次课程设计，现在我有很多的想法，从理论的设计到实践，在这几天 内，我学到了很多，不仅巩固了以前所学过的知识，而且还学到了很多课本上所 没有的内容。通过这次课程设计使我懂得了理论与实际相结合是很重要的，只有 理论知识与实践相结合起来，从理论中得出结论，才是真正的知识，才能提高自 己的实际动手能力和独立思考能力。在设计的过程中遇到各种各样的问题，同时 在设计的过程中发现自己的缺乏之处，对以前所

9、学过的知识理解的不够深刻，掌 握的不够牢固，通过这才课程设计，把以前所学过的知识重新温故，巩固了所学 的知识。11参考文献1严蔚敏等.数据结构（C语言版）清华大学出版社2朱战立.数据结构-使用C语言（第四版）.电子工业出版社3吴跃.数据结构和算法.机械工业出版社4周海英等.数据结构与算法设计（第二版）.国际工业出版社5谭浩强著，C语言设计题解与上机指导，清华大学出版社6谭浩强著，C面向对象程序设计谭浩强，清华大学出版社12题目哈夫曼编码的实现考核工程考核内容得分平时考核（30分）出勤情况、态度、效率；知识掌握情况、基本操作技能、知识应用能力、获取知识能力系统设计（20分）分析系统的功能模块编程

10、调试（20分）实现系统的各个功能模块，并完成调试回答下列问题（15分）回答老师针对课程设计提出的问题课程设计报告撰写（10分）严格按照规范要求完成课程设计报告源代码（5分）按照规范要求完成课程设计源代码的排版总评成绩指导教师评语:日期:目录31课程设计目标与任务11.1 课程设计目标11.2 课程设计任务11.3 设计内容12分析与设计22.1 题目需求分析22.2 存储结构设计22.3 算法描述22.4 程序流程图32.5 测试程序说明63程序清单74测试104.1 测试数据104.2 测试结果分析105总结11参考文献121课程设计目标与任务1.1课程设计目标根据课堂讲授的内容，做相应的自

11、主练习，消化课堂所讲解的内容，通过 调试典型例题或习题积累调试C程序的经验，通过完成辅助教材中的编程题， 逐渐培养学生的编程能力，用计算机解决实际问题的能力。数据结构课程设计 的目标是，通过设计掌握数据结构课程中学到的基本理论和算法并综合运用于 解决实际问题中，它是理论与实践相结合的重要过程。设计要求学会如何对实 际问题定义相关数据结构，并采用恰当的设计方法和算法解决问题，同时训练 进行复杂程序设计的技能和培养良好的程序设计习惯。1. 2课程设计任务1、深刻理解信源编码的基本思想与目的；2、理解哈夫曼编码方法的基本过程与特点；3、提高综合运用所学理论知识独立分析和解决问题的能力；4、使用MAT

12、LAB或其他语言进行编程。5、编写的函数要有通用性；6、信源可以自由选择，符号信源于图像信源均可。1.3设计内容假设一个信源的各符号概率，编写适当函数，对其进行哈夫曼编码，得 出码子，平均码长和编码效率，总结该编码方法的特点和运用。1、从终端读入字符集大小n,以及n个字符和n个权值，建立哈夫曼树并 将它存于文件haffTree中，将已在内存中的哈夫曼树以直观的方式（比方树）显 示在终端上；2、利用已经建好的哈夫曼树（如不在内存，那么从文件haffmTree中读入）， 对文件TexT、txt中的正文进行编码，然后将结果存入文件Code, txt中。3、利用已建好的哈夫曼树将文件Code, txt

13、中的代码进行译码，结果存入文件TexT、txt中，并输出结果。2分析与设计2.1题目需求分析该程序大体上有两个功能：1、输入任何一个字符串后，该程序能统计不同字符串的个数，并以不同字 符串的个数作为权值。2、不同字母的权值，以该权值作为叶节点，构造一颗带权路径最小的 数，对该数从叶节点到根节点路径分支遍历，经历一个分支就得到一位哈夫曼编 码值。（规定哈夫曼树种的左分支为0,右分支为1,那么从根节点到每个叶节点 所经过的分支对应的0和1组成的序列便为该结点对应字符的编码）2. 2存储结构设计存储结构：typedef structint weight, flag, parent, leftChil

14、d, rightChild;HaffNode;Typedef structint bit MaxN, start, weight ;/*数组编码的起始下标字符的权值*/ Code; / *哈夫曼编码结构*/Int weight16;Char s 30;2. 3算法描述1、统计模块任意输入一个字符串，不管字母是否相联，字符串是否含空格都能统计出不 同字母的个数。2、建立哈夫曼树模块以统计的字符串个数作为权值,利用仿真存储结构,建立带权路径最小的树。 其中对结点的存储需要六个域，分别是weight域，flag域，parent域，leftChlid域，rightChild域。Weight域是对权值的

15、存放，flag域是一个标志域，flag=O时 表示该结点尚未加入到哈夫曼树中，flag=l时表示该结点已加入到哈夫曼树中。3、哈夫曼编码模块从哈夫曼树的叶节点到根节点路径分支逐步遍历，每经过一个分支就得到一位赫夫曼编码。赫夫曼编码也利用仿真存储结构。4、主函数模板从屏幕上输入字符串，调用函数，输出每个字母的权值与编码。2. 4程序流程图图27主函数流程图主函数中利用gets输入一个字符串，统计不同字母的个数，在调用Haffman 函数建立哈夫曼树，然后调用HaffmanCode函数进行编码，如果成功，输出权值与编码，否那么退出。结束结束4统计函数在统计不同字符个数时先利用一个for循环遍历所有

16、的字母每遍历 一个不同字母前令temp=l,然后用一个for循环将其后的字母与之比拟，假设相等 那么temp+,且将该字母从字符串中删除，否那么从下一个字母遍历。如此循环直 到字符串结束。图2-3haffman函数流程图可以利用二叉树来设计二进制的前缀编码，假设有一颗二叉树，其四个叶子 结点分别为A,B,C,D这4个字符，且约定左分支表示字符0,右分支表示字 符1,那么可以从跟结点到叶节点的路径上分支字符组成的字符串作为该叶子 节点字符的编码。2. 5测试程序说明主要有字符串统计源程序，哈夫曼树建立源程序，哈夫曼树编码函数这三个 组成，各自完成不同的任务，其中字符串统计程序主要是遍历字符，哈夫

17、曼程序 主要是建立叶节点和根节点，哈夫曼编码主要是确立分支编码，然后形成编码。1、首先是哈夫曼树的定义：假设有n个权值，试构造一颗有n个叶子结点 的二叉树，每个叶子带权值为wi,其中树带权路径最小的二叉树成为哈夫曼树 或者最优二叉树；2、哈夫曼树的构造：weight为输入的频率数组，把其中的值赋给依次建立 的HTNode对象中的data属性，即每一个HTNode对于一个输入的频度。然后 根据data属性按从小到大顺序排序,每次从data取出两个最小和次小的HTNode, 将他们的data相加，构造出新的HTNode作为他们的父结点，指针parent, leftchlid, rightchild赋相应的值。在把这个新的结点插入最小堆。按此步骤可以 构造出一颗哈夫曼树。通过已经构造出来的哈夫曼树，自底向上，有频率结点开始向上寻找parent, 直到parent为树的顶点为止。这样，根据每次向上搜索后，原结点为父结点的左 孩子还是右孩子，来记录1或0,这样，每个频率都会有一个01编码与之唯一 对应，并且任何编码没有前局部是同其它完整编码一样的。