算法实验2-哈夫曼编码实验报告

1、精选优质文档-倾情为你奉上昆明理工大学信息工程与自动化学院学生实验报告（ 2011 2012 学年 第 1 学期 ）课程名称：算法设计与分析 开课实验室：信自楼机房444 2011年11月02日年级、专业、班学号姓名成绩实验项目名称哈夫曼编码指导教师教师评语该同学是否了解实验原理： A.了解B.基本了解C.不了解该同学的实验能力：A.强 B.中等 C.差 该同学的实验是否达到要求：A.达到B.基本达到C.未达到实验报告是否规范：A.规范B.基本规范C.不规范实验过程是否详细记录：A.详细B.一般 C.没有 教师签名： 年 月 日一、上机目的及内容上机目的（1）了解前缀编码的概念，理解数据压缩的

2、基本方法；（2）掌握最优子结构性质的证明方法；（3）掌握贪心法的设计思想并能熟练运用。上机内容设需要编码的字符集为d1, d2, , dn，它们出现的频率为w1, w2, , wn，应用哈夫曼树构造最短的不等长编码方案。 二、实验原理及基本技术路线图（方框原理图或程序流程图）实验原理（1）证明哈夫曼树满足最优子结构性质；（2）设计贪心算法求解哈夫曼编码方案；（3）设计测试数据，写出程序文档。流程图三、所用仪器、材料（设备名称、型号、规格等或使用软件）设备：1台PC及VISUAL C+6.0软件。 四、实验方法、步骤（或：程序代码或操作过程）源程序#include<stdio.h>#

3、define n 7 /一共有n棵左右孩子均为空的树#define m 2*n-1 /生成哈夫曼树后共有2*n-1个节点float small1,small2;int flag1,flag2,count;typedef struct HuffmanTreefloat weight;int lchild,rchild,parent;huffman;huffman huffmantreem;void CreatHuffmanTree()int i;void select();printf("请输入%d棵树的权值:",n); /初始化每棵树的权值for(i=0;i<n;i+

4、)scanf("%f",&huffmantreei.weight);printf("n");for(i=0;i<m;i+) /初始化huffmantreei.lchild=-1;huffmantreei.rchild=-1;huffmantreei.parent=-1;for(count=n;count<m;count+) /共合并n-1次 select(); huffmantreeflag1.parent=count; huffmantreeflag2.parent=count;huffmantreecount.weight=sma

5、ll1+small2; huffmantreecount.lchild=flag1; /值最小的作为左孩子 huffmantreecount.rchild=flag2;void select() /找出权值最小的两棵树,算法有问题int i,a,b;float stemp;int ftemp;a=0;b=0;for(i=0;i<count;i+)if(huffmantreei.parent=-1)if(a=0)small1=huffmantreei.weight; flag1=i;a=a+1;elseif(b=0) small2=huffmantreei.weight; flag2=i;

6、 b=b+1;if(a=1)&&(b=1)break;if(small1>small2)stemp=small1;small1=small2;small2=stemp;ftemp=flag1;flag1=flag2;flag2=ftemp;for(i=0;i<count;i+)if(huffmantreei.parent=-1) if(flag1!=i)&&(flag2!=i) if(huffmantreei.weight<small2) small2=huffmantreei.weight; flag2=i; if(small1>sma

7、ll2) stemp=small1; small1=small2; small2=stemp; ftemp=flag1; flag1=flag2; flag2=ftemp;void huffmancode()int an,j,k,i,c;for(i=0;i<n;i+)j=i;c=0;while(huffmantreej.parent!=-1)k=huffmantreej.parent;if(huffmantreek.lchild=j) ac=0;if(huffmantreek.rchild=j)ac=1;c=c+1; j=k;printf("节点%d的哈夫曼编码为："

8、,i);for(c=c-1;c>-1;c-) printf("%d",ac);printf("n");void main()CreatHuffmanTree();huffmancode();五、实验过程原始记录( 测试数据、图表、计算等) 六、实验结果、分析和结论（误差分析与数据处理、成果总结等。其中，绘制曲线图时必须用计算纸或程序运行结果、改进、收获）实验总结：每次将集合中两个权值最小的二叉树合并成一棵新的二叉树，n-1次合并后,，成为最终的一棵哈夫曼树。这既是贪心法的思想：从某一个最初状态出发，根据当前的局部最优策略，以满足约束方程为条件，以使目标函数最快(或最慢)为原则，在候选集合中进行一系列的选择，以便尽快构成问题的可行解。每次选择两个