算法设计与分析实验报告-哈夫曼编码（含源程序）

《算法设计与分析实验报告-哈夫曼编码（含源程序）》由会员上传分享，免费在线阅读，更多相关内容在行业资料-天天文库。

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

2、1,d2,…,dn}，它们出现的频率为{w1,w2,…,wn}，应用哈夫曼树构造最短的不等长编码方案。2.上机目的（1）了解前缀编码的概念，理解数据压缩的基本方法；（2）掌握最优子结构性质的证明方法；（3）掌握贪心法的设计思想并能熟练运用。二、实验原理及基本技术路线图（方框原理图或程序流程图）（1）证明哈夫曼树满足最优子结构性质；证明：设C为一给定的字母表，其中每个字母c∈C都定义有频度f[c]。设x和y是C中具有最低频度的两个字母。并设D为字母表移去x和y，再加上新字符z后的字母表，D=C-{x，y}∪{z}；如C一样为D定义f，其中f[z]=f[x]+f[y]。设T为表示字母表D上最优前

3、缀编码的任意一棵树。那么，将T中的叶子节点z替换成具有x和y孩子的内部节点所得到的树T，表示字母表C上的一个最优前缀编码。（2）设计贪心算法求解哈夫曼编码方案；解：哈弗曼编码是以贪心法为基础的，可以从最优子结构中求得问题的解。所以，需要从一个问题中选出一个当前最优的解，再把这些解加起来就是最终问题的解。可以构造一个优先队列priority_queue，每次求解子问题的解时，从优先级队列priority_queue中选取频率最小的两个字母（x、y）进行合并得到一个新的结点z，把x与y从优先级队列priority_queue中弹出，把压入到优先级队列priority_queue中。如此反复进行，

4、直到优先级队列priority_queue中只有一个元素（根节点）为止。（3）设计测试数据，写出程序文档。共设计了两组测试数据，他们的哈弗曼树如下图所示：-11-图（1）测试数据的哈弗曼树图-11-表一：第一组测试数据字符出现的频率a1b3c6d14e58表二：第二组测试数据字符出现的频率d4b3f5g6h14m16由图（1）可知各个字符的哈弗曼编码如下表：表三：表一中各元素的哈弗曼编码字符出现的频率a0000b0001c001d01e1表四：表二中各元素的哈弗曼编码字符出现的频率d001b000f010g011h10m11三、所用仪器、材料（设备名称、型号、规格等或使用软件）1台PC及VI

5、SUALC++6.0软件亿图程序流程图绘制软件四、实验方法、步骤（或：程序代码或操作过程）下面源代码可以在VisualC++6.0平台上运行！//author@刘召at2011-11-18//ThisprogramiseditedandcompiledonVisualStudio10platform-11-//Huffman编码//#include"stdafx.h"//在Visualstudio中运行，应取消该句的注释！#include#include#include#include#include#inc

6、ludeusingnamespacestd;structcodeInformation{doublepriority;charcodeName;intlchild,rchild,parent;booltest;booloperator<(constcodeInformation&x)const{return!(priorityqa,constcharc){for(inti=0;i<(int)(qa.size());i++){if(qa[i].codeName==c)returnt

7、rue;}returnfalse;}voidaline(charc,intn){for(inti=0;i*Harffcode,priority_queue*pq){inti=1,j=1;codeInformationwk;while(i){aline('-',80);