《数据结构与算法》课程设计成果报告-哈夫曼编码的实现.doc

河南工程学院数据结构与算法课程设计成果报告哈夫曼编码的实现学生学号： 学生姓名： 学 院： 计算机学院 专业班级： 1341软件工程 专业课程： 数据结构与算法 指导教师： 2014 年 12 月 29 日题 目哈夫曼编码的实现考核项目考核内容得分平时考核（30分）出勤情况、态度、效率；知识掌握情况、基本操作技能、知识应用能力、获取知识能力系统设计（20分）分析系统的功能模块编程调试（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 课程设计目标根据课堂讲授的内容，做相应的自主练习，消化课堂所讲解的内容，通过调试典型例题或习题积累调试c程序的经验，通过完成辅助教材中的编程题，逐渐培养学生的编程能力，用计算机解决实际问题的能力。数据结构课程设计的目标是，通过设计掌握数据结构课程中学到的基本理论和算法并综合运用于解决实际问题中，它是理论与实践相结合的重要过程。设计要求学会如何对实际问题定义相关数据结构，并采用恰当的设计方法和算法解决问题，同时训练进行复杂程序设计的技能和培养良好的程序设计习惯。1.2 课程设计任务1、深刻理解信源编码的基本思想与目的；2、理解哈夫曼编码方法的基本过程与特点；3、提高综合运用所学理论知识独立分析和解决问题的能力；4、使用MATLAB或其他语言进行编程。5、编写的函数要有通用性；6、信源可以自由选择，符号信源于图像信源均可。1.3 设计内容假设已知一个信源的各符号概率，编写适当函数，对其进行哈夫曼编码，得出码子，平均码长和编码效率，总结该编码方法的特点和运用。1、从终端读入字符集大小n，以及n个字符和n个权值，建立哈夫曼树并将它存于文件haffTree中，将已在内存中的哈夫曼树以直观的方式（比如树）显示在终端上；2、利用已经建好的哈夫曼树（如不在内存，则从文件haffmTree中读入），对文件TexT、txt中的正文进行编码，然后将结果存入文件Code.txt中。3、利用已建好的哈夫曼树将文件Code.txt中的代码进行译码，结果存入文件TexT、txt中，并输出结果。2 分析与设计2.1 题目需求分析该程序大体上有两个功能：1、输入任何一个字符串后，该程序能统计不同字符串的个数，并以不同字符串的个数作为权值。2、已知不同字母的权值，以该权值作为叶节点，构造一颗带权路径最小的数，对该数从叶节点到根节点路径分支遍历，经历一个分支就得到一位哈夫曼编码值。（规定哈夫曼树种的左分支为0，右分支为1，则从根节点到每个叶节点所经过的分支对应的0和1组成的序列便为该结点对应字符的编码）2.2 存储结构设计存储结构：typedef structint weight,flag,parent,leftChild,rightChild;HaffNode;Typedef structint bitMaxN,start,weight;/*数组编码的起始下标字符的权值*/Code;/*哈夫曼编码结构*/Int weight16;Char s30;2.3 算法描述1、统计模块任意输入一个字符串，不论字母是否相联，字符串是否含空格都能统计出不同字母的个数。2、建立哈夫曼树模块以统计的字符串个数作为权值，利用仿真存储结构，建立带权路径最小的树。其中对结点的存储需要六个域，分别是weight域，flag域，parent域，leftChlid域，rightChild域。Weight域是对权值的存放，flag域是一个标志域，flag=0时表示该结点尚未加入到哈夫曼树中，flag=1时表示该结点已加入到哈夫曼树中。3、哈夫曼编码模块从哈夫曼树的叶节点到根节点路径分支逐步遍历，每经过一个分支就得到一位赫夫曼编码。赫夫曼编码也利用仿真存储结构。4、主函数模板从屏幕上输入字符串，调用函数，输出每个字母的权值与编码。开始定义初始化变量nMHaffmanHaffmancodein结束输入j=myHaffCodei.starjn输出j+i+打印n越界2.4 程序流程图1、主函数nyi=0y输出nny 图2-1主函数流程图主函数中利用gets输入一个字符串，统计不同字母的个数，在调用Haffman函数建立哈夫曼树，然后调用HaffmanCode函数进行编码，如果成功，输出权值与编码，否则退出。2、统计函数开始I=0，k=0，nin&si!=0Temp=1Jnj=si&i!=jTemp+PnP+结束Weightk+=tempI+ NSp=sp+1J+ 图2-2 统计函数流程图统计函数在统计不同字符个数时先利用一个for循环遍历所有的字母每遍历一个不同字母前令temp=1，然后用一个for循环将其后的字母与之比较，若相等则temp+，且将该字母从字符串中删除，否则从下一个字母遍历。如此循环直到字符串结束。in初始化结束Parent！=0haffTreeparen.leftChild=child开始cd.bitcd.start=1 3、HffmanCode函数ncd.bitcd.start=0InhaffCodei.bitj=cd.bitjhaffCodei.start=cd.start;haffCodei.weight=cd.weight;I+cd.start-;child=parent;parent=haffTreechild.parent;图2-3haffman函数流程图可以利用二叉树来设计二进制的前缀编码，假设有一颗二叉树，其四个叶子结点分别为A,B,C,D这4个字符，且约定左分支表示字符0，右分支表示字符1，则可以从跟结点到叶节点的路径上分支字符组成的字符串作为该叶子节点字符的编码。2.5 测试程序说明主要有字符串统计源程序，哈夫曼树建立源程序，哈夫曼树编码函数这三个组成，各自完成不同的任务，其中字符串统计程序主要是遍历字符，哈夫曼程序主要是建立叶节点和根节点，哈夫曼编码主要是确立分支编码，然后形成编码。1、 首先是哈夫曼树的定义：假设有n个权值，试构造一颗有n个叶子结点的二叉树，每个叶子带权值为wi，其中树带权路径最小的二叉树成为哈夫曼树或者最优二叉树；2、 哈夫曼树的构造：weight为输入的频率数组，把其中的值赋给依次建立的HTNode对象中的data属性，即每一个HTNode对于一个输入的频度。然后根据data属性按从小到大顺序排序，每次从data取出两个最小和次小的HTNode，将他们的data相加，构造出新的HTNode作为他们的父结点，指针parent，leftchlid，rightchild赋相应的值。在把这个新的结点插入最小堆。按此步骤可以构造出一颗哈夫曼树。通过已经构造出来的哈夫曼树，自底向上，有频率结点开始向上寻找parent，直到parent为树的顶点为止。这样，根据每次向上搜索后，原结点为父结点的左孩子还是右孩子，来记录1或0，这样，每个频率都会有一个01编码与之唯一对应，并且任何编码没有前部分是同其它完整编码一样的。3 程序清单1、 字符串统计源程序：int count(char*s,int*weight,int n)int I,j,temp,k=0,p;for(i=0;in&si!=0;i+)temp=1;for(j=0;jn;j+) /*遍历相同的字母*/ if(sj=si&i!=j) temp+; for(p=j;pn;p+)/*删除相同的字母*/ sp=sp+1; n-;j-;Weightk+=temp;/*temp作为权值赋给weight数组*/Return I;/* 返回权值个数*/2、 哈夫曼树建立源程序void Haffman(int weight,int n,HaffNode haffTree)/*建立叶节点个数为n，权值数组为weight的哈夫曼树HaffTree*/int I,j,m1,m2,x1,x2; For(i=0;i2*n-1;i+) if(in)haffTreei.flag=0;weighti;else haffTreei.weight=0;haffTreei.parent=0;haffTreei.flag=0;haffTreei.leftChild=-1;haffTreei.rightChild=-1;/* 构造哈夫曼树haffTree的n-1个非叶节点*/For(i=0;In-1;i+)m1=m2=MaxValue;X1=x2=0;For(j=0;jn+I;j+)if(haffTreej.weightm1&haffTreej,flag=0)m2=m1;X2=x1;M1=haffTreej.weightr;X1=j;Else if(haffTreej.weightm2&haffTreej,flag=0)m2=haffTreej.weightr;X2=j;/*将找出的两颗权值最小的子树合并为一颗子树/*haffTreex1.parent=n+i;haffTreex2.parent=n+i;haffTreex1.flag=1;haffTreex2.flag=1haffTreen+i.weight=haffTreex1.weight+ haffTreex2.weight;haffTreen+i.leftChild=x1;haffTreen+i.rightChild=x2;3、哈夫曼树编码函数Void HaffmanCode(HaffNode haffTree,int n,Code haffCode)/*有n个结点的哈夫曼haffTree构造哈夫曼编码haffCode*/Code*cd=(Code*)malloc(sizeof(Code);Int I,j,child,parent;/*求n个结点的哈夫曼编码*/For(i=0;in;i+)cd.start=n-1;cd.weight= haffTreei.weight;child=i;parent= haffTreechild.parent/*由叶节点 直到根节点*/while(parent!=0)if(haffTreeparent.leftChild=child)Cd.bitcd.start=0; /*左孩子分支编码0/*Else Cd.bitcd.start=1; /*左孩子分支编码1/*cd.start-;child=parent;parent=haffTreechild.parent;For（j= cd.start+1;jMaxN)printf(“给出的n越界，修改MaxN！n”);Exit(1);Haffman(weight,n,myHaffTree);HaffmanCode(myHaffTree,n,myHaffCode);For(i=0;in;i+)printf(“ ”,myHaffCodei.weight);For(j=myHaffCodei.start+1;jMaxN)printf(“给出的n越界，修改MaxN！n”);Exit(1);Haffman(weight,n,myHaffTree);HaffmanCode(myHaffTree,n,myHaffCode);For(i=0;in;i+)printf(“ ”,myHaffCodei.weight);For(j=myHaffCodei.start+1;jn;j+)Printf(”%d”,myHaffCodei.bitj);Printf(“n”);int count(char*s,int*weight,int n)int I,j,temp,k=0,p;for(i=0;in&si!=0;i+)temp=1;for(j=0;jn;j+) /*遍历相同的字母*/ if(sj=si&i!=j) temp+; for(p=j;pn;p+)/*删除相同的字母*/ sp=sp+1; n-;j-;Weightk+=temp;/*temp作为权值赋给weight数组*/Return I;/* 返回权值个数*/void Haffman(int weight,int n,HaffNode haffTree)/*建立叶节点个数为n，权值数组为weight的哈夫曼树HaffTree*/int I,j,m1,m2,x1,x2; For(i=0;i2*n-1;i+) if(in)haffTreei.flag=0;weighti;else haffTreei.weight=0;haffTreei.parent=0;haffTreei.flag=0;haffTreei.leftChild=-1;haffTreei.rightChild=-1;/* 构造哈夫曼树haffTree的n-1个非叶节点*/For(i=0;In-1;i+)m1=m2=MaxValue;X1=x2=0;For(j=0;jn+I;j+)if(haffTreej.weightm1&haffTreej,flag=0)m2=m1;X2=x1;M1=haffTreej.weightr;X1=j;Else if(haffTreej.weightm2&haffTreej,flag=0)m2=haffTreej.weightr;X2=j;/*将找出的两颗权值最小的子树合并为一颗子树/*haffTreex1.parent=n+i;haffTreex2.parent=n+i;haffTreex1.flag=1;haffTreex2.flag=1haffTreen+i.weight=haffTreex1.weight+ ha