《算法分析与设计 实验二 哈夫曼编码》由会员分享，可在线阅读，更多相关《算法分析与设计 实验二 哈夫曼编码（8页珍藏版）》请在金锄头文库上搜索。
1、昆明理工大学信息工程与自动化学院学生实验报告（201 201 学年第一学期）课程名称：算法设计与分析开课实验室：年 月 日年级、专业、班学号姓名成绩实验项目名称哈夫曼编码指导教师教 师 评 语该同学是否了解实验原理：A.了解口B.基本了解口C.不了解口该同学的实验能力：A.强 口B.中等 口。差 口该同学的实验是否达到要求：A.达到口B.基本达到口 C.未达到口实验报告是否规范：A.规范口B.基本规范口C.不规范口实验过程是否详细记录：A.详细口B.一般 口C.没有口教师签名：年月日一、上机目的及内容1. 上机内容设需要编码的字符集为dl, d2,，dn,它们出现的频率为wl, w2,，wn,
2、应用哈夫曼 树构造最短的不等长编码方案。2. 上机目的（1）了解前缀编码的概念，理解数据压缩的基本方法；（2）掌握最优子结构性质的证明方法；（3）掌握贪心法的设计思想并能熟练运用。二、实验原理及基本技术路线图（方框原理图或程序流程图）（1）证明哈夫曼树满足最优子结构性质；（2）设计贪心算法求解哈夫曼编码方案；（3）设计测试数据，写出程序文档。数据结构与算法：typedef char *HufIinanCode; 动态分配数组，存储哈夫曼编码typedef stnictunsigned int weight; 用来存放各个结点的权值unsigned int parent,LCluld,RClnl
3、d; 指向双亲、孩子结点的指针 HTNode, *HuffinanTree; 动态分配数组，存储哈夫曼树程序流程图:Y结束三、所用仪器、材料（设备名称、型号、规格等或使用软件）1 台 PC 及 VISUAL C+6.0 软件四、实验方法、步骤（或：程序代码或操作过程）#include #include #include typedef stmctunsigned hit weight;unsigned hit parent.LChild .RChild;) HTNode, *HuffmanTree; 动态分配数组，存储哈夫曼树typedef chai *HuffmanCode; 动态分配数组，
4、存储哈夫曼编码void Select(HuffinanTree *ht,int n,int *sl,int *s2)int i.min;fbr(i=l; i=n; i+)if(*ht)i .parent=0)min=i;break;fbr(i=l; i=n; i+)if(*ht)i.parent=O)if(*ht)i.weight(*ht) min, weight)min=i;*sl=min;fbr(i=l; i=n; i+)if(*ht)i.parent=O & i!=(*sl)min=i;break;fbr(i=l; i=n; i+)if(*ht)i.parent=O &if(*ht)i.
5、weight(*ht) min, weight)niin=i;*s2=min;构造哈夫曼树ht,w存放已知的n个权值void CitHnffinanTree(HuffiiianTree *ht,int *w,int n)iiit m,i,sl,s2;m=2 *n-l;总的结点数*ht=(HufftnanTree)malloc(m+l)*sizeof(HTNode);for(i= 1; i=n; i+) /1 -n号存放叶子结点，初始化(*ht)i.weight=wi;(*ht)i.LChild=O;(*ht)i.parent=O;(*ht)i.RChild=O;for(i=n十1; i=m;
6、i+)/非叶子结点的初始化(*ht)i.weight=O;(*ht)i.LChild=O;(*ht)i.parent=O;(*ht)i.RChild=O;pnntf(”n所构造的哈夫曼树为:n”)；for(i=n十1; i=m; i+)/创建非叶子结点，建哈夫曼树Select(ht,i-1 ,&s 1 ,&s2);(*ht)sl.parent=i;(*ht)s2 .parent=i;(*ht)i.LChild=sl;(*ht)i.RChild=s2;(*ht)i. weight=(*ht)s 1 .weight+(*ht)s2 .weight;printf(%d (%d, %d)n,(*ht)
7、i.weight,(*ht)s 1 .weight/*ht)s2.weight); 从叶子结点到根，逆向求每个叶子结点对应的哈夫曼编码void CitHuffinanCode(HuffinanTree *ht, HuffinanCode *hc, int n)char *cd;/定义的存放编码的空间int a100;int i,start,p,w=O;unsigned int c;hc=(HufftnanCode *)malloc(n+l)*sizeof(char *);cd=(char *)nialloc(n*sizeof(char);cdn.l=0for(i=l; i=n; i+) /求n
8、个结点对应的哈夫曼编码ai=0；start=n-l; 起始指针位置在最右边for(c=i,p=(*ht)i.parent; p!=0; c=p,p=(*ht)p.parent) 从叶子到根结点求编码if( (*ht)p.LChild=c)cd.start=T;a】+;elsecd-stait=,0,;a】+;hci=(char *)malloc(n-start)*sizeof(char); 为第 i 个编码分配空间strcpy(hc i ,&cd start);fiee(cd);fbr(i=l; i=n; i+)printf(”权值为1 的哈夫曼编码为:%sn,(*ht)i.weight,hc
9、i);fbr(i=l; i=n; i+)w+=(*ht) i .weight *a i;printf(Hn 带权路径长度 WPL 为：dWn”,w);voidHufftnanTree HT;HuffinanCode HC; int 率w,i,n,wei;printf(,rtttt 哈夫曼编码n” );pnntf(”请输入结点个数：”)；scanf(”cT,&ii);w=(int *)nialloc(n+l)*sizeof(int);printf(n请分别输入这1个结点的权值:n,n);for(i=l; i=n; i+)pnntf(”结点& ”,i);fflush(stdm);scanf(”d”
10、,&wei);wi=wei;CrtHuffinanTree(&HT,w,n);CrtHu ffinanC ode(&HT, &HC ,n);五、实验过程原始记录（测试数据、图表、计算等）哈夫舅编码 G:VCDebughafuman.exe请输入结点个数；2 2 0 俞 2 5 18 9 7 2 别1 :2:3:4:5:6:7: 分占告罟罟罟罟罟罟罟罟罟S 主星 口士口士曰王 drtn.王 .土口士 口士 口士 口王口1 6 1 1 9 -0 18 9 11麓惠哈夫曼树为，13 15 18 9, 923 11. 1228 36 43 G:VCDebughafuman.exe回所构造的哈夫爰树为=
11、7 C2. 5)13 15 18 9, 923 11. 1228 13. 1536 43 64 10? 43, 64nrpnrpnrp-r中 5 马马彳 i i & 5 5彳扁.扁5用扁 .扁扁g吊吊麻之弓扁 一tfsaisfia- 甘后-Tt哈-4-i/ 哈跛哈哈哈伊加哈隔 .DM .DM 2 .OH.rtn.rtn01 ,-cn-cn 8 25189721961 -E*EF*又以又又又又又兑又又又01011 01010 100 0100 0001 0110;11 ;101 0000 Bill:001市权路径长度WPL为：354Press any key to co nt in Lie六、实验结果、分析和结论（误差分析与数据处理、成果总结等。其中，绘制曲线图时必 须用计算纸或程序运行结果、改进、收获）这次实验的内容是哈夫曼编码，哈夫曼树也就是最优二叉树，构造哈夫曼树的过程就是 先在所有结点中找到权值最小的两个结点合并，依次这样找到较小的结点合并，最终生成哈 夫曼树。树中所有叶子结点的带权路径长度之和最小，带权路径长度就是该结点到树根之间 的路径长度与结点上权的乘积，且权值越大的叶子离跟越近。
