哈夫曼树实验报告

哈夫曼树实验报告 2012-11-25 [数据结构-实验（四）]数据结构（四）实验报告书班级：__________________学号：__________________姓名：__________________2012年11月25日一、实验目的·在二叉树基本操作的基础上，掌握对二叉树的一些其它操作的具体实现方法。·掌握构造哈夫曼树以及哈夫曼编码的方法。·熟练掌握哈夫曼树（最优二叉树）特征及其应用二、实验课题哈夫曼树和哈夫曼编码：·从终端输入若干个字符，统计（或指定）字符出...

2012-11-25 [数据结构-实验（四）]数据结构（四）实验报告书班级：__________________学号：__________________姓名：__________________2012年11月25日一、实验目的·在二叉树基本操作的基础上，掌握对二叉树的一些其它操作的具体实现方法。·掌握构造哈夫曼树以及哈夫曼编码的方法。·熟练掌握哈夫曼树（最优二叉树）特征及其应用二、实验课题哈夫曼树和哈夫曼编码：·从终端输入若干个字符，统计（或指定）字符出现的频率；·将字符出现的频率作为结点的权值；·建立哈夫曼树，然后对各字符进行哈夫曼编码；·最后打印哈夫曼树和对应的哈夫曼编码。三、实验步骤㈠、数据结构与核心算法的设计描述1)数据类型定义：typedefstruct{ charCdata; intWeight; intParent,Lchild,Rchild;}HTNode,*PTNode;typedefchar**HCode;2)统计字符出现的频率：voidFreqChar(char*text,intnc,PTNode&HT,intn){ inti,k,m; m=2*n-1; for(i=1;i<=nc;i++) { for(k=1;k<=n;k++) { if(text[i]==HT[k].Cdata) HT[k].Weight++; } } printf("\n改变权值之后的结点信息\n"); printf("n=%dm=%d\n",n,m); printf("KCLRPW\n"); for(k=1;k<=m;k++) printf("%d%c%d%d%d%d\n",k,HT[k].Cdata,HT[k].Lchild,HT[k].Rchild,HT[k].Parent,HT[k].Weight);}3)建立哈夫曼树：intCreateHTree(PTNode&HT,intn,intm){ intj,k; for(k=n+1;k<=m;k++) { intw1=32767,w2=w1;/*w1,w2分别保存权值最小的两个权值*/ intp1=0,p2=0;/*p1,p2保存两个最小权值的下标*/ for(j=1;j<=k-1;j++) { if(HT[j].Parent==0)/*尚未合并*/ { if(HT[j].Weight<w1) { w2=w1; p2=p1; w1=HT[j].Weight; p1=j; } elseif(HT[j].Weight<w2) { w2=HT[j].Weight; p2=j; } }/*找到权值最小的两个值及其下标*/ } HT[k].Lchild=p1; HT[k].Rchild=p2; HT[k].Weight=w1+w2; HT[p1].Parent=k; HT[p2].Parent=k; } printf("\n哈夫曼树打印\n"); printf("KCLRPW\n"); for(k=1;k<=m;k++) printf("%d%c%d%d%d%d\n",k,HT[k].Cdata,HT[k].Lchild,HT[k].Rchild,HT[k].Parent,HT[k].Weight); return0;}4)哈夫曼编码：voidHTCoding(PTNode&HT,intn){ intk,sp,fp,p; char*cd; HCodeHC; HC=(HCode)malloc((n+1)*sizeof(char*));/*1~n个结点、下标为1~n*/ cd=(char*)malloc(n*sizeof(char));/*动态分配求编码的工作空间*/ cd[n-1]='\0';/*编码的结束标志*/ printf("\n打印哈弗曼编码\n"); printf("CWHC\n"); for(k=1;k<=n;k++)/*逐个求字符的编码*/ { sp=n-1; p=k; fp=HT[k].Parent; for(;fp!=0;p=fp,fp=HT[fp].Parent)//从叶子结点到根逆向求编码 if(HT[fp].Lchild==p) cd[--sp]='0'; elseif(HT[fp].Rchild==p) cd[--sp]='1'; HC[k]=(char*)malloc((n-sp)*sizeof(char));/*为第k个字符分配保存编码的空间*/ strcpy(HC[k],&cd[sp]);/*HC[]为二维数组，一维下标存放结点的下标，二维下标存放其哈弗曼编码*/ printf("%c%d%s\n",HT[k].Cdata,HT[k].Weight,HC[k]); } free(cd);}㈡、函数调用及主函数设计结束输入字符程序入口（main）组成数组text数组arr[]输出arr[]形成树输出结果㈢程序调试及运行结果分析1.输入若干字符：2.输出叶子结点：3.打印哈夫曼树：4.哈夫曼编码：四、实验总结这次实验真的很难，花了一周才把所有的功能函数编写完，而且中间也遇到了不少麻烦。但是功夫不负有心人，通过寻求同学的帮助以及自己查资料，还是很快就解决了。同时，这次实验也学到了很多课本上没有的编程技巧，也加深了对课本上知识点的理解。认识到哈夫曼树在其他领域的广泛应用。熟悉掌握哈夫曼编码对我们的算法设计有很大的帮助，在以后的学习过程中，应该能够不断地运用哈夫曼的思想来解决一些实际的问题。谢谢！2012年11月25日-3-

                    本文档为【哈夫曼树实验报告】，请使用软件OFFICE或WPS软件打开。作品中的文字与图均可以修改和编辑，
                    图片更改请在作品中右键图片并更换，文字修改请直接点击文字进行修改，也可以新增和删除文档中的内容。 
 该文档来自用户分享，如有侵权行为请发邮件ishare@vip.sina.com联系网站客服，我们会及时删除。

                    [版权声明] 本站所有资料为用户分享产生，若发现您的权利被侵害，请联系客服邮件isharekefu@iask.cn，我们尽快处理。

                    本作品所展示的图片、画像、字体、音乐的版权可能需版权方额外授权，请谨慎使用。

                    网站提供的党政主题相关内容(国旗、国徽、党徽..)目的在于配合国家政策宣传，仅限个人学习分享使用，禁止用于任何广告和商用目的。
                

下载需要：免费已有0 人下载

立即下载

哈夫曼树实验报告

你可能还喜欢