算法试验二哈夫曼编码

昆明理工大学信息工程与自动化学院学生实验报告（ 2012 2013 学年 第 1 学期 ）课程名称：算法分析与设计 开课实验室：信自楼应用、网络机房445 2012 年12月 6日年级、专业、班学号姓名成绩实验项目名称哈夫曼编码指导教师教师评语该同学是否了解实验原理：A.了解B.基本了解C.不了解该同学的实验能力：A.强 B.中等 C.差 该同学的实验是否达到要求：A.达到B.基本达到C.未达到实验报告是否规范：A.规范B.基本规范C.不规范实验过程是否详细记录：A.详细B.一般 C.没有 教师签名： 年 月 日一、上机目的及内容1.上机内容设需要编码的字符集为d1, d2, , dn，它们出现的频率为w1, w2, , wn，应用哈夫曼树构造最短的不等长编码方案。2.上机目的（1）了解前缀编码的概念，理解数据压缩的基本方法；（2）掌握最优子结构性质的证明方法；（3）掌握贪心法的设计思想并能熟练运用。二、实验原理及基本技术路线图（方框原理图或程序流程图）（1）证明哈夫曼树满足最优子结构性质；（2）设计贪心算法求解哈夫曼编码方案；（3）设计测试数据，写出程序文档。a 哈夫曼编码构造设计：找一个结点向上遍历直到跟结点，若再过程中当前结点为其双亲结点的左孩子则得到分支编码0，否则得到1,定义一个数组存放中间结果 循环n次得到n个结点的哈夫曼编码数组保存一个叶子结点的编码，不等长编码的起始位和相应的字符权值结束开始输出每个叶子结点的哈夫曼编码b 主函数算法：输入将要编码的数的权值构造哈夫曼树构造哈夫曼编码开始C 流程图建立huffman树初始化parent， lchild, rchild选择权值最小的两颗树对变量small1和small2赋值Huffmantrcei,weightsmall2 Y交换两值 为前n个元素编码I=n N 结束 Y三、所用仪器、材料（设备名称、型号、规格等或使用软件）1台PC及VISUAL C+6.0软件四、实验方法、步骤（或：程序代码或操作过程）a.创建file，书写代码并编译调试运行b 原代码如下：#include#define n 7 #define m 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;in;i+)scanf(%f,&huffmantreei.weight);printf(n);for(i=0;im;i+) huffmantreei.lchild=-1;huffmantreei.rchild=-1;huffmantreei.parent=-1;for(count=n;countm;count+) select(); huffmantreeflag1.parent=count; huffmantreeflag2.parent=count;huffmantreecount.weight=small1+small2; huffmantreecount.lchild=flag1; huffmantreecount.rchild=flag2;void select() int i,a,b;float stemp;int ftemp;a=0;b=0;for(i=0;ismall2)stemp=small1;small1=small2;small2=stemp;ftemp=flag1;flag1=flag2;flag2=ftemp;for(i=0;icount;i+)if(huffmantreei.parent=-1) if(flag1!=i)&(flag2!=i) if(huffmantreei.weightsmall2) stemp=small1; small1=small2; small2=stemp; ftemp=flag1; flag1=flag2; flag2=ftemp;void huffmancode()int an,j,k,i,c;for(i=0;i-1;c-) printf(%d,ac);printf(n);void main()CreatHuffmanTree();huffmancode();五、实验过程原始记录( 测试数据、图表、计算等)六、实验结果、分析和结论（误差分析与数据处理、成果总结等。其中，绘制曲线图时必须用计算纸或程序运行结果、改进、收获）通过本次试验，我了解了哈弗曼编码的全过程，对贪心发也有了更深的了解和认识；同时我对前缀编码的概念也有了初步的了解，对数据压缩的基本方法也有了一定的理解；同时也掌握最优子结构性质的证明方法；掌握贪心法的设计思想并能熟练运用。每次将集合中两个权值最小的二叉树合并成一棵新的二叉树，n-1次合并后,，成为最终的一棵哈夫曼树。这既是贪心法的思想：从某一个最初状态出发，根据当前的局部最优策略，以满足约束方程为条件，以使目标函数最快(或最慢)为原则，在候选集合中进行一系列的选择，以便尽快构成问题的可行解。每次选择两个权值最小的二叉树时，规定了较小的为左子树.。此次试验虽然花了较长时间才完成，但我收获很多，我对哈夫曼树、贪心法和数组与结构体的使用都有了一定的了解，在解解问题时也变得更有耐心。 在以后的学习中，要不断的实践和复习理论知识，只有两样结合起来才可以学得更好，才能真正理解所学的知识，也有利于对概念的升华理解。注：教师必须按照上述各项内容严格要求，认真批改和评定学生成绩。