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

-1-昆明理工大学信息工程与自动化学院学生实验报告（2011—2012学年第1学期）课程名称：算法设计与分析开课实验室：信自楼机房4442011年11月02日年级、专业、班学号姓名成绩实验项目名称哈夫曼编码指导教师教师评语该同学是否了解实验原理：A.了解□B.基本了解□C.不了解□该同学的实验能力：A.强□B.中等□C.差□该同学的实验是否达到要求：A.达到□B.基本达到□C.未达到□实验报告是否规范：A.规范□B.基本规范□C.不规范□实验过程是否详细记录：A.详细□B.一般□C.没有□教师签名：年月日一、上机目的及内容上机目的（1）了解前缀编码的概念，理解数据压缩的基本方法；（2）掌握最优子结构性质的证明方法；（3）掌握贪心法的设计思想并能熟练运用。上机内容设需要编码的字符集为{d1,d2,…,dn}，它们出现的频率为{w1,w2,…,wn}，应用哈夫曼树构造最短的不等长编码方案。二、实验原理及基本技术路线图（方框原理图或程序流程图）实验原理（1）证明哈夫曼树满足最优子结构性质；（2）设计贪心算法求解哈夫曼编码方案；（3）设计测试数据，写出程序文档。-2-流程图开始建立huffman树初始化parent，lchild，rchild为-1从所有树中选择权值最小的两棵对变量small1和small2赋值（森林中得任意两棵树的权值）Huffmantree[i].weightsmall1交换Huffmantree[i].weight和small1的值是否i=i+1Small1small2否交换small1和small2将两棵树合并，生成新节点为前n个元素编码双亲节点是否为空否该节点为左孩子是A[i]=0;i=i+1A[i]=1;i=i+1否i=n是结束是否-3-三、所用仪器、材料（设备名称、型号、规格等或使用软件）设备：1台PC及VISUALC++6.0软件。四、实验方法、步骤（或：程序代码或操作过程）源程序#includestdio.h#definen7//一共有n棵左右孩子均为空的树#definem2*n-1//生成哈夫曼树后共有2*n-1个节点floatsmall1,small2;intflag1,flag2,count;typedefstructHuffmanTree{floatweight;intlchild,rchild,parent;}huffman;huffmanhuffmantree[m];voidCreatHuffmanTree(){inti;voidselect();printf(请输入%d棵树的权值:,n);//初始化每棵树的权值for(i=0;in;i++)scanf(%f,&huffmantree[i].weight);printf(\n);for(i=0;im;i++)//初始化{huffmantree[i].lchild=-1;huffmantree[i].rchild=-1;huffmantree[i].parent=-1;}for(count=n;countm;count++)//共合并n-1次{select();huffmantree[flag1].parent=count;huffmantree[flag2].parent=count;huffmantree[count].weight=small1+small2;huffmantree[count].lchild=flag1;//值最小的作为左孩子huffmantree[count].rchild=flag2;}}voidselect()//找出权值最小的两棵树,算法有问题{-4-inti,a,b;floatstemp;intftemp;a=0;b=0;for(i=0;icount;i++){if(huffmantree[i].parent==-1){if(a==0){small1=huffmantree[i].weight;flag1=i;a=a+1;}elseif(b==0){small2=huffmantree[i].weight;flag2=i;b=b+1;}}if((a==1)&&(b==1))break;}if(small1small2){stemp=small1;small1=small2;small2=stemp;ftemp=flag1;flag1=flag2;flag2=ftemp;}for(i=0;icount;i++)if(huffmantree[i].parent==-1)if((flag1!=i)&&(flag2!=i))if(huffmantree[i].weightsmall2){small2=huffmantree[i].weight;flag2=i;if(small1small2){stemp=small1;small1=small2;-5-small2=stemp;ftemp=flag1;flag1=flag2;flag2=ftemp;}}}voidhuffmancode(){inta[n],j,k,i,c;for(i=0;in;i++){j=i;c=0;while(huffmantree[j].parent!=-1){k=huffmantree[j].parent;if(huffmantree[k].lchild==j)a[c]=0;if(huffmantree[k].rchild==j)a[c]=1;c=c+1;j=k;}printf(节点%d的哈夫曼编码为：,i);for(c=c-1;c-1;c--)printf(%d,a[c]);printf(\n);}}voidmain(){CreatHuffmanTree();huffmancode();}-6-五、实验过程原始记录(测试数据、图表、计算等)六、实验结果、分析和结论（误差分析与数据处理、成果总结等。其中，绘制曲线图时必须用计算纸或程序运行结果、改进、收获）实验总结：每次将集合中两个权值最小的二叉树合并成一棵新的二叉树，n-1次合并后,，成为最终的一棵哈夫曼树。这既是贪心法的思想：从某一个最初状态出发，根据当前的局部最优策略，以满足约束方程为条件，以使目标函数最快(或最慢)为原则，在候选集合中进行一系列的选择，以便尽快构成问题的可行解。每次选择两个权值最小的二叉树时，规定了较小的为左子树.。此次试验虽然花了较长时间才完成，但我收获很多，我对哈夫曼树、贪心法和数组与结构体的使用都有了一定的了解，在解解问题时也变得更有耐心。注：教师必须按照上述各项内容严格要求，认真批改和评定学生成绩。