算法试验二哈夫曼编码.doc

《算法试验二哈夫曼编码.doc》由会员上传分享，免费在线阅读，更多相关内容在工程资料-天天文库。

1、昆明理工大学信息工程与自动化学院学生实验报告（2012—2013学年第1学期）课程名称：算法分析与设计开课实验室：信自楼应用、网络机房4452012年12月6日年级、专业、班学号姓名成绩实验项目名称哈夫曼编码指导教师教师评语该同学是否了解实验原理：A.了解□B.基本了解□C.不了解□该同学的实验能力：A.强□B.中等□C.差□该同学的实验是否达到要求：A.达到□B.基本达到□C.未达到□实验报告是否规范：A.规范□B.基本规范□C.不规范□实验过程是否详细记录：A.详细□B.一般□C.没有□教师签名：年月日一、上机目的及内容1.

2、上机内容设需要编码的字符集为{d1,d2,…,dn}，它们出现的频率为{w1,w2,…,wn}，应用哈夫曼树构造最短的不等长编码方案。2.上机目的（1）了解前缀编码的概念，理解数据压缩的基本方法；（2）掌握最优子结构性质的证明方法；（3）掌握贪心法的设计思想并能熟练运用。二、实验原理及基本技术路线图（方框原理图或程序流程图）（1）证明哈夫曼树满足最优子结构性质；（2）设计贪心算法求解哈夫曼编码方案；（3）设计测试数据，写出程序文档。a哈夫曼编码构造设计：找一个结点向上遍历直到跟结点，若再过程中当前结点为其双亲结点的左孩子则得到分

3、支编码0，否则得到1,定义一个数组存放中间结果循环n次得到n个结点的哈夫曼编码数组保存一个叶子结点的编码，不等长编码的起始位和相应的字符权值结束开始输出每个叶子结点的哈夫曼编码b主函数算法：输入将要编码的数的权值构造哈夫曼树构造哈夫曼编码开始C流程图建立huffman树初始化parent，lchild,rchild选择权值最小的两颗树对变量small1和small2赋值Huffmantrce[i],weightsmall2Y交换两值为前n个元素编码I=nN结束Y三、所用仪器、材料（设备名称

4、、型号、规格等或使用软件）1台PC及VISUALC++6.0软件四、实验方法、步骤（或：程序代码或操作过程）a.创建file，书写代码并编译调试运行b原代码如下：#include#definen7#definem2*n-1floatsmall1,small2;intflag1,flag2,count;typedefstructHuffmanTree{floatweight;intlchild,rchild,parent;}huffman;huffmanhuffmantree[m];voidCreatHuffma

5、nTree(){inti;voidselect();printf("请输入%d棵树的权值:",n);for(i=0;i

6、ent=count;huffmantree[flag2].parent=count;huffmantree[count].weight=small1+small2;huffmantree[count].lchild=flag1;huffmantree[count].rchild=flag2;}}voidselect(){inti,a,b;floatstemp;intftemp;a=0;b=0;for(i=0;i

7、ffmantree[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(small1>small2){stemp=small1;small1=small2;small2=stemp;ftemp=flag1;flag1=flag2;flag2=ftemp;}for(i=0;i

8、lag1!=i)&&(flag2!=i))if(huffmantree[i].weightsmall2){stemp=small1;small1=sm