哈夫曼树和哈夫曼编码

课程设计（数据结构）

哈夫曼树和哈夫曼编码二。。九年六月二十六日课程设计任务书及成绩评定课题名称表达式求值哈夫曼树和哈夫曼编码I、题目的目的和要求：巩固和加深对数据结构的理解，通过上机实验、调试程序，加深对课本知识的理解，最终使学生能够熟练应用数据结构的知识写程序。（1） 通过本课程的学习，能熟练掌握几种基本数据结构的基本操作。（2） 能针对给定题目，选择相应的数据结构，分析并设计算法，进而给出问题的正确求解过程并编写代码实现。II、设计进度及完成情况日期内 容6.8-6.10选取参考书，查阅有关文献资料，完成资料搜集和系统分析工作。6.15和6.19创建相关数据结构，录入源程序。6.22〜6.25调试程序并记录调试中的问题，初步完成课程设计报告。6.26上交课程设计报告并进行课程设计答辩，要求每个同学针对自己的设计回答指导教师3-4个问题。考核结束后将课程设计报告和源程序的电子版交班长统一刻光盘上交。III、主要参考文献及资料[1]严蔚敏数据结构（C语言版）清华大学出版社1999严蔚敏数据结构题集（C语言版）清华大学出版社1999谭浩强C语言程序设计清华大学出版社与所用编程环境相配套的C语言或C++相关的资料IV、成绩评定：设计成绩： （教师填写）指导老师： （签字）二oo九年六月二十六日TOC\o"1-5"\h\z第一章概述 1第二章系统分析 2第三章概要设计 3第四章详细设计及实现代码 8第五章调试过程中的问题及系统测试情况 1213第六章结束语 13参考文献13第_章概述课程设计是实践性教学中的一个重要环节，它以某一课程为基础，可以涉及和课程相关的各个方面，是一门独立于课程之外的特殊课程。课程设计是让同学们对所学的课程更全面的学习和应用，理解和掌握课程的相关知识。《数据结构》是一门重要的专业基础课，是计算机理论和应用的核心基础课程。数据结构课程设计，要求学生在数据结构的逻辑特性和物理表示、数据结构的选择和应用、算法的设计及其实现等方面，加深对课程基本内容的理解。同时，在程序设计方法以及上机操作等基本技能和科学作风方面受到比较系统和严格的训练。在这次的课程设计中我选择的题目是表达式求值和哈夫曼树及哈夫曼编码。这里我们介绍一种简单直观、广为使用的算法，通常称为“算符优先法”。哈夫曼树又称最优树，是一类带权路径长度最短的树，有着广泛的应用。功能：表达式求值以栈为存储结构，实现输入的表达式的求值；哈夫曼树和哈夫曼编码是实现最优二叉树的构造，并能通过最优二叉树进行编码，应用到电文中，并以此来译码。利用键盘，输入相应的数值，通过程序实现表达式的求值；再利用键盘，输入各个顶点，通过程序构造最优二叉树以及为此编码。第二章系统分析一、表达式求值根据一元多项式相加的运算规则：对于两个一元多项式中所有指数相同的项，对应系数相加，若其和不为零，则构成“和多项式”中的一项；对于两个一元多项式所有指数不相同的项，则分别复抄到“和多项式”中去。在此，安装上述抽象数据类型Polynomial中基本操作的定义，“和多项式”链表中的结点无需另生成，而应该从两个多项式的链表中摘取。其运算规则如下：假设指着qa和qb分别指向多项式A和多项式B中当前进行比较的某个结点，则比较两个结点中的指数项，有下列3种情况：①指针qa所指结点的指数值＜指针qb所指结点的指数值，则应摘取qa指针所指结点插入到“和多项式”链表中去；②指针qa所指结点的指数值〉指针qb所指结点的指数值，则应摘取指针qb所指结点插入到“和多项式”链表中去；③指针qa所指结点的指数值=指针qb所指结点的指数值，则将两个结点中的系数相加，若和数不为零，则修改qa所指结点的系数值，同时释放qb所指结点；反之，从多项式A的链表中删除相应结点，并释放指针qa和qb所指结点。二、哈夫曼树和哈夫曼编码建立哈夫曼树的算法思想是：1） 根据给定的几个权值｛w1，w2， ，wn｝构成n颗二叉树的集合F=｛T1，T2， ，Tn｝，其中每颗二叉树Ti中只有一个带权为wj的根结点，其左右子树均空。2） 在F中选取两棵根结点的权值最小作为左右子树构造一棵新的二叉树，且置新的二叉树的根结点的权值为其左、右子树上根结点的权值之和。3） 在F中删除这两棵树，同时将新得到的二叉树加入F中。4） 重复（2）和（3），直到F只含一棵树为止。这棵树便是哈夫曼树。第三章概要设计以下算法描述了这个求值过程：intcmp(terma,termb);〃依a的指数值＜(或二)(或＞)b的指数值，分别返回-1、0、+1voidCreatPolyn(polynomail&p,intm){〃输入m项的系数和指数，建立表示一元多项式的有序链表pInitList(p);h=GetHead(p);e.coef=0.0;e.expn=-1;SetCurElem(h,e);〃设置头结点的数据元素for(i=1;i＜=m;++i){〃依次输入m个非零项scanf(e.coef,e.expn);if(!LocateElem(P,e,q(*cmp)())){〃当前链表中不存在该指数项if(MakeNode(s,e))InsFirst(q,s);〃生成结点并插入链表}}}//CreatPolynvoidAddPolyn(polynomai&Pa,polynomai&Pb){〃多项式加法：Pa=Pa+Pb，利用两个多项式的结点构成“和多项式”。ha=GetHead(Pa);hb=GetHead(Pb);//ha和hb分别指向Pa和Pb中当前结点while(qa&&qb){//qa和qb均非空a=GetCurElem(qa);b=GetCurElem(qb);//a和b为两表中当前比较元素switch(*cmp(a,b)){case-1://多项式PA中当前结点的指数值小ha=qa;qa=NextPos(pa,qa);break;case0:〃两者的指数值相等sum=a.coef+b.coef;if(sum!=0.0){//修改多项式PA中当前结点的系数值SetCurElem(qa,sum);ha=qa;}else{//删除多项式PA中当前结点DelFirst(ha,qa);FreeNode(qa);}DelFirst(hb,qb);FreeNode(qb);qb=NextPos(Pb,hb);qa=NextPos(Pa,ha);break;case1:〃多项式PB中当前结点的指数值小DelFirst(hb,qb);InsFirst(ha,qb);qb=Nextpos(Pb,hb);ha=NextPos(Pa,ha);break;}//switch}//whileif(!ListEmpty(Pb))Append(Pa,qb);〃链接pb中剩余结点FreeNode(Pb):〃释放Pb的头结点}//AddPolyn哈夫曼树及哈夫曼编码ADTBinaryTree(数据对象:D是具有相同特性的数据元素的集合。数据关系：R：若D=①，则R=①，称BinaryTree为空二叉树；若D尹①，则R={H},H是如下二元关系：在D中存在惟一的称为根的数据元素root，它在关系H下无前驱；若D-{root}尹①，则存在D-{root}={D1,Dr}，且DIEDr=①；若D1尹①，则D1中存在惟一的元素XI，<root,X1>EH,且存在D1上的关系H1EH;若Dr尹①，则Dr中存在惟一的元素Xr,<root,Xr>EH，且存在Dr上的关系Hr£H;H={<root,X1>,<root,Xr>,H1,Hr};(D1,{H1})是一颗符合本定义的二叉树，称为根的左子树,(Dr,{Hr})是一颗符合本定义的二叉树，称为根的右子树。基本操作P：Initqueue(&q)；操作结果：构造空二叉树T。Destroyqueue(&q)；初始条件：二叉树T已存在。操作结果：销毁二叉树T。CreateBiTree(&T,definition)；初始条件：definition给出二叉树T的定义。操作结果：按definition构造二叉树T。ClearBiTree(&T)；初始条件：二叉树T已存在。操作结果:将二叉树T清为空树。BiTreeEmpty(T)；初始条件：二叉树T已存在。操作结果：若T为空二叉树，则返回TRUE，否则FALSE。BiTreeDepth(T)；初始条件：二叉树T已存在。操作结果：返回T的深度。Root(T)初始条件：二叉树T已存在。操作结果：返回T的根。Value(T，e)；初始条件：二叉树T存在，e是T中某个结点。操作结果：返回e的值。Assign（T,&e，value）；初始条件：二叉树T存在，e是T中某个结点。操作结果：结点e赋值为value。Parent（T，e）；初始条件：二叉树T存在，e是T中某个结点。操作结果:若e是丁的非根结点，则返回它的双亲，否则返回“空”。LeftChild（T，e）；初始条件：二叉树T存在，e是T中某个结点。操作结果:返回e的左孩子。若e无左孩子，则返回“空”。RightChild（T，e）；初始条件：二叉树T存在，e是T中某个结点。操作结果:返回e的右孩子。若e无右孩子，则返回“空”；LeftSibling（T，e）；初始条件：二叉树T存在，e是T中某个结点。操作结果:返回e的左兄弟。若e是T的左孩子或无左兄弟，则返回“空”。RightSibling（T，e）；初始条件：二叉树T存在，e是T中某个结点。操作结果:返回e的右兄弟。若e是T的右孩子或无右兄弟，则返回“空”。InsertChild（T，p，LR，c）；初始条件：二叉树T存在，p指向T中某个结点，LR为0或1，非空二叉树c与T不相交且右子树为空。操作结果:根据LR为0或为1，插入c为T中p所指结点的左或右子树。P所指结点的原有左或右子树则成为c的右子树。DeleteChild（T，p，LR）；初始条件：二叉树T存在，p指向T中某个结点，LR为0或1。操作结果：根据LR为0或为1，删除T中p所指结点的左或右子树。PreOrderTraverse（T,Visit（））；初始条件：二叉树T存在，Visit是对结点操作的应用函数。操作结果:先序遍历T,对每个结点调用函数Visit一次且仅一次。一旦visit()失败，则操作失败。InOrderTraverse(T,Visit())；初始条件：二叉树T存在，Visit是对结点操作的应用函数。操作结果：中序遍历T，对每个结点调用函数Visit一次且仅一次。一旦visit()失败，则操作失败。PostOrderTraverse(T，Visit())；初始条件：二叉树T存在，Visit是对结点操作的应用函数。操作结果:后序遍历T，对每个结点调用函数Visit一次且仅一次。一旦visit()失败，则操作失败。LevelOrderTraverse(T,Visit())；初始条件：二叉树T存在，Visit是对结点操作的应用函数。操作结果:层序遍历T，对每个结点调用函数Visit一次且仅一次。一旦visit()失败，则操作失败。}ADTBinaryTree求哈夫曼编码的算法如下：VoidHuffmanCoding(HuffmanTree&HT,HuffmanCode&HC,int*w,intn){//w存放n个字符的权值(均>0)，构造哈夫曼树HT，并求n个字符的哈夫曼编码HC。if(n<=1)return;m=2*n-1;HT=(HuffmanTree)malloc((m+1)*sizeof(HTNode));//0号单元未用。for(p=HT+1,i=1;i<=n,++i,++p,++w)*p={*w,0,0,0};for(;i<=m,++i,++p,)*p={0,0,0,0};for(i=n+1;i<=m,++i,){//建哈夫曼树//在HT[1..i-1]选择parent为0且weight最小的两个结点，其序号分别为s1和s2。Select(HT,i-1,s1,s2);HT[s1].parent=I;HT[s2].parent=i;HT[i].lchild=s1;HT[i].rchild=s2;HT[i].weight=HT[s1].weight+HT[s2].weight;}〃从叶子到根逆向求每个字符的哈夫曼编码。HC=(HaffmanCode)malloc((n+1)*sizeof(char*));//分配n个字符编码的头指针向量cd=(char*)malloc(n*sizeof(char*));//分配求编码的工作空间cd[n-1]=”\0”； 〃编码结束符。for(i=1;i<=n;++i){ 〃逐个字符求哈夫曼编码start=n-1; 〃编码结束符位置for(c=i,f=HT[i].parent;f!=0;c=f,f=HT[f].parent)//从叶子到根逆向求编码if(HT[f].lchild==c)cd[--start]=”0”；elescd[--start]='T';HC[i]=(char*)malloc((n-start)*sizeof(char));//为第i个字符编码分配空间strcpy(HC[i],&cd[start]); 〃从cd复制编码(串)到HC}free(cd); 〃释放工作空间}//HuffmanCoding第四章详细设计及实现代码表达式求值的源代码：#include"stdio.h”#include"stdlib.h"typedefstructpolynode{intcofe;intexp;structpolynode*next;}PNode;PNode*Creat_Linkst(intn){PNode*head,*p,*s;inti;head=(PNode*)malloc(sizeof(PNode));head->next=NULL;p=head;printf("entercofe,exp:\n");for(i=1;i<=n;++i){s=(PNode*)malloc(sizeof(PNode));scanf("%d,%d”,&s->cofe,&s->exp);s->next=NULL;p->next=s;p=s;}return(head);}voidpolyADD(PNode*pa,PNode*pb){PNode*pre,*qa,*qb,*q;intsum;pre=pa;qa=pa->next;qb=pb->next;while(qa&&qb){if(qa->exp==qb->exp){sum=qa->cofe+qb->cofe;if(sum){qa->cofe=sum;pre=qa;}else{pre->next=qa->next;free(qa);}qa=pre->next;q=qb;qb=qb->next;free(q);}else{if(qa->exp>qb->exp){pre=qa;qa=qa->next;}else{pre->next=qb;pre=qb;qb=qb->next;pre->next=qa;}}}if(qb)pre->next=qb;free(pb);}voidprint_Linkst(PNode*H){PNode*p;p=H->next;while(p){printf("%dxA%d+H,p->cofe,p->exp);p=p->next;}if(p->exp)printf("%dxA%d\n",p->cofe,p->exp);elseprintf("%d\n”,p->cofe);}main(){PNode*HA,*HB;intla,lb;printf("enterla,lb:");scanf("%d,%d",&la,&lb);printf("\ncreatHA\n");HA=Creat_Linkst(la);printf("A(x)=");print_Linkst(HA);printf("\ncreatHB\n");HB=Creat_Linkst(lb);printf("B(x)=");print_Linkst(HB);polyADD(HA,HB);printf("\nA(x)=");}哈夫曼树和哈夫曼编码的程序：#definemaxvalue10000#definemaxnodenumber100#definemaxbit10typedefstruct{intweight;intparent,lchild,rchild;}htnode;typedefstruct{intbit[maxbit];intstart;}hcodetype;typedefhtnode*huffmantree;htnodeht[maxnodenumber];hcodetypecd[maxnodenumber];voidcrthuffmantree(intn){inti,j,m1,m2,k1,k2;for(i=0;i<2*n-1;i++){ht[i].weight=0;ht[i].parent=1;ht[i].lchild=1;ht[i].rchild=1;}printf("shuruyizuweight:\n");for(i=0;i<n;i++)scanf("%d”,&ht[i].weight);printf("iweightparentlchildrchild\n");for(i=0;i<n-1;i++){m1=maxvalue;m2=maxvalue;k1=0;k2=0;for(j=0;j<n+i;j++)if(ht[j].parent==-1&&ht[j].weight<m1){m2=m1;k2=k1;m1=ht[j].weight;k1=j;}if(ht[j].parent==-1&&ht[j].weight<m2){m2=ht[j].weight;k2=j;}ht[k1].parent=n+i;ht[k2].parent=n+i;ht[n+i].weight=ht[k1].weight+ht[k2].weight;ht[n+i].lchild=k1;ht[n+i].rchild=k2;}for(i=0;i<2*n-1;i++)%5d%5d%5d\n”,i,ht[i].weight,ht[i].parent,ht[i].{printf("%d%5d%5d%5d%5d\n”,i,ht[i].weight,ht[i].parent,ht[i].lchild,ht[i].rchild);printf("\n");}}/*crthuffmantree*/voidgethuffmancode(htnodeht[],intn){inti,j,c,p;printf("code:%d\n",n);for(i=0;i<n;i++){c=i;j=maxbit;do{j--；p=ht[c].parent;if(ht[p].lchild==c)cd[i].bit[j]=0;elsecd[i].bit[j]=1;c=p;}while(p!=1);cd[i].start=j+1;/*根也置1,所以编码从下一位置始*/}for(i=0;i<n;i++){printf("%d