哈夫曼树及哈夫曼编码译码

实验2哈夫曼树及哈夫曼编码译码的实现一、实验目的和要求通过本实验使学生深刻理解二叉树的性质和存储结构。认识哈夫曼树、哈夫曼编码的作用和意义。能够建立一个哈夫曼树，并输出哈夫曼编码，正确调程序。二、实验内容和原理哈夫曼编码(HuffmanCoding)是一种编码方式，以哈夫曼树─即最优二叉树，带权路径长度最小的二叉树，经常应用于数据压缩。哈夫曼树又称做最优二叉树，它是n个带权叶子结点构成的所有二叉树中，带权路径长度WPL最小的二叉数。是一种带权路径长度最短的二叉树。所谓树的带权路径长度，就是树中所有的叶结点的权值乘上其到根结点的路径长度（若根结点为0层，叶结点到根结点的路径长度为叶结点的层数）。树的带权路径长度记为WPL=(W1*L1+W2*L2+W3*L3+...+Wn*Ln)，N个权值Wi(i=1,2,...n)构成一棵有N个叶结点的二叉树，相应的叶结点的路径长度为Li(i=1,2,...n)。树中每个节点的左分支标记0，而右分支标记1.则每个结点代表的字符的编码为从根结点到叶子结点的路径上分支所标记的数组的串。三、实验环境惠普计算机，WindowsXP操作系统，TurboC++四、算法描述及实验步骤#includestdio.h/*头文件*/#definemaxbit10/*定义哈夫曼编码最大长度*/#definemaxvalue10000/*定义最大权值常量*/#definemaxnodenumber100/*定义结点最大数目常量*/typedefstruct/*定义结点结构*/{intweight;/*权重域值为整型*/charcharacter;intparent,lchild,rchild;/*3个指针域为整型值，即静态指针*/}htnode;/*定义结点类型标识符*/typedefstruct/*定义保存一个叶子结点哈曼编码的结构*/{intbit[maxbit];/*哈曼编码域为一维数组*/intstart;/*开始位置域为整型*/}hcodetype;/*定义哈曼编码类型*/voidmain()/*主函数*/{voidgethuffmancode(htnodeht[],intn);/*函数声明*/htnodeht[maxnodenumber];/*定义链表存储结构区数组*/inti,j,m1,m2,k1,k2,n,a;printf(Pleaseinputn:);/*提示输出叶子结点个数*/scanf(%d,&n);printf(Pleaseinputcharacterandweight:\n);/*提示输出各叶子结点的权值*/for(i=0;i2*n-1;i++)/*数组ht初始化*/{ht[i].weight=0;/*权重初始化为0*/ht[i].character='\0';ht[i].parent=-1;/*3个指针域初始化为-1，即NULL*/ht[i].lchild=-1;ht[i].rchild=-1;}for(i=0;in;i++)/*读入n个叶子结点的权重值*/{fflush(stdin);scanf(%c%d,&ht[i].character,&ht[i].weight);}for(i=0;in-1;i++)/*控制n-1趟生成新结点构造哈夫曼树*/{m1=maxvalue;/*预置最小权值变量为最大权值*/m2=maxvalue;/*预置次小权值变量为最大权值*/k1=0;k2=0;/*预置最小和次小权值结点位置为下标0处*/for(j=0;jn+i;j++)/*控制一趟中找出两个最小权值的结点*/if(ht[j].parent==-1&&ht[j].weightm1){m2=m1;k2=k1;/*若第j个结点权小于当前最小的m1改为次小的*/m1=ht[j].weight;k1=j;/*并记下新的当前最小权值及位置*/}elseif(ht[j].parent==-1&&ht[j].weightm2){m2=ht[j].weight;k2=j;/*否则若小于当前次小的m2则更新m2及其位置*/}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;/*新生成结点的左孩子指针指向k1*/ht[n+i].rchild=k2;/*新生成结点的右孩子指针指向k2*/}printf(Thecharacterandthecodeisasfollows:\n);gethuffmancode(ht,n);/*调用函数*/}voidgethuffmancode(htnodeht[],intn)/*对具有n个叶子结点的哈夫曼树ht，求所有叶子结点的哈夫曼编码并输出*/{inti,j,c,p,m,k;/*定义局部变量*/charch[100];hcodetypecd[100];/*定义存放哈曼编码的数组cd*/for(i=0;in;i++)/*对n个结点逐一求哈夫曼编码*/{c=i;j=maxbit;/*为求一个结点的哈夫曼编码初始化c和j*/do{j--;/*j指向bit中存放编码位的正确位置*/p=ht[c].parent;/*p指向c的双亲结点*/if(ht[p].lchild==c)/*如果c是p的左孩子*/cd[i].bit[j]=0;/*编码位上赋0*/elsecd[i].bit[j]=1;/*否则c是p的右孩子，编码位上赋1*/c=p;/*更新c为p，为求下一个编码位做准备*/}while(p!=-1);/*当未到达根结点继续做do循环*/cd[i].start=++j;/*求完一个叶子结点的哈夫曼编码时，记下编码开始位置*/}for(i=0;in;i++)/*输出n个叶子结点的哈夫曼编码*/{printf(Character:%cCode:,ht[i].character);/*显示排版需要*/for(j=cd[i].start;jmaxbit;j++)/*逐位输出一个编码*/printf(%d,cd[i].bit[j]);printf(\n);/*输出完一个哈夫曼编码后换行*/}printf(Pleaseinputch:);scanf(%s,ch);/*输入被译码的字符*/printf(Thedecodeis:);for(i=0;ch[i]!='\0';i++)/*三个循环实现译码*/{for(j=0;jn;j++)if(ht[j].character==ch[i])for(k=cd[j].start;kmaxbit;k++)/*第三个循环输出译码*/printf(%d,cd[j].bit[k]);}}五、调试过程1、有部分输入错误了，改正后就能正常运行了。六、实验结果经调试程序正确后，输入n=8个权重值如下：h6；e4；l13；o24；k17；i3；t9；y29.再输入被译码的字符串：hellokity七、总结通过这次实验，我加深了对最优二叉树的理解和哈夫曼算法的静态实现。从哈夫曼的编码实现，我了解了最优算法的广泛。从而对今后的学习有了很好的了解。同时自己的编程水平也有所提高。八、附录：参考书本，《算法与数据结构》（宁正元、王秀丽和林大辉编著，清华大学出版社）；《C程序设计》（谭浩强编著，清华大学出版社）。