湘潭大学数据结构实验8实验报告源代码赫夫曼编码

《湘潭大学数据结构实验8实验报告源代码赫夫曼编码》由会员上传分享，免费在线阅读，更多相关内容在工程资料-天天文库。

1、“数据结构和算法Ir课程实验报告实验名称=赫夫曼编码及其应用班级姓名学号实验日期：实验机时：2学时实验成绩：实验目的：掌握赫夫曼树的概念、存储结构掌握建立赫夫曼树和赫夫曼编码的方法及带权路径长度的计算熟练掌握二叉树的应用二.实验内容：(1)基本实验内容：实现赫夫曼树的生成，完成赫夫曼编码的输出；(2)扩展实验内容：完成一组码字的赫夫曼编码及解码(以一个文本文件的内容为例).三•程序及注释：tiincludctiincludetJinclude^defineMAXLEN100t

2、ypedcfstruct{intweight;intIchild;intrchiId;intparent:charkey;Jhtnode;typedefhtnodehfmt[MAXLEN];intn;voidinithfmt(hfmtl)//对结构体进彳亍初始化{inti:printf("");printfrT);printf(^******************************输入区*****************************、『)；printfC请输入n=");scanf&n);getchar(

3、);for(i=0;i<2*n1;i++)//对结构体进行初始化{t[i]・wcight=O;t[i]・lchild=-l;t[i].rchild=-l;t[i]・parent=-l;}printf("");}voidinputweight(hTmtt)//输入函数{intw;//w为权值inti;chark;//k表示获取的字符for(i=0:i

4、C%d^,&w);gelchar()；t[i]・weight•二w;printf("");))voidselectmin(hfmtt,inti,int*pl,int*p2)//选中两个权值最小的函数{longmin1=999999;longmin2二999999;intj;for(j=0;j<“；j++)//选择最小权值字符的下标返回if(t[j]・parent==-l)if(minl>t[j].weight){minl=t[j]・weight;*pl=j；}for(j=0;j<=i;j++)//选择次小权值字符的下标返回if(

5、t[j]・parent==-1)if(min2>t[j].weight&&j!=(*pl))//注意j!=(*pl)){min2=t[j]・weight;*p2=j;}}voidcreathfmt(hfmtt)//创建哈夫曼树的函数{inti,pl,p2;inithfmt(t);inputweight(t);for(i=n;i<2*n-l;i++){selectmin(t,i-1,&pl,&p2);t[pl]・parent=i;t[p2]・parent二i;t[i]・lchild二pl;t[i]・rchild=p2;t[i].wei

6、ght=t[pl].weight+t[p2].weight;}}voidprinthfmt(hfmtt)//打印哈夫曼树{inti；printfC"");戸1仆1「("**********************哈夫曼编数结构*****************************「)；printf("tt权逼t父母t左孩子t右孩子t字符t");for(i=0;i<2*n-l;i++){prinlf("");printfC，tt%dt%dt%dt%dt%c?z,t[iJ.weight,t[i].

7、parent,tLiJ.lchild,t[i].rchiId,t[i].key);}printf(/z");printfr*):}voidhfmtpath(hfmtt,inti,intj)〃编码的重要哈夫曼树路径递归算法{inta,b;a=i;b=j=t[i]・parent：if(t[jj.parent!=-l){i=j；hfmtpath(t,i,j):)iflchild==a)printf('"O"):elseprintf(T);voidphfmnodc(hfmtt)//对字符进彳了初始编码{inti,j,a;pr

8、intfC"");printf(，z**************************哈夫曼編码*****************************")；for(i=0;i