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

昆明理工大学信息工程与自动化学院学生实验报告（ 2011 2012 学年 第 1 学期 ）课程名称：算法设计与分析 开课实验室：信自楼机房445 2011 年11月 2日年级、专业、班计科092学号200910405201姓名刘召成绩实验项目名称哈夫曼编码指导教师 张晶教师评语该同学是否了解实验原理：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）证明哈夫曼树满足最优子结构性质；证明：设c为一给定的字母表，其中每个字母cc都定义有频度fc。设x和y是c中具有最低频度的两个字母。并设d为字母表移去x和y，再加上新字符z后的字母表，d=c-x，yz；如c一样为d定义f，其中fz=fx+fy。设t为表示字母表d上最优前缀编码的任意一棵树。那么，将t中的叶子节点z替换成具有x和y孩子的内部节点所得到的树t，表示字母表c上的一个最优前缀编码。（2） 设计贪心算法求解哈夫曼编码方案；解：哈弗曼编码是以贪心法为基础的，可以从最优子结构中求得问题的解。所以，需要从一个问题中选出一个当前最优的解，再把这些解加起来就是最终问题的解。可以构造一个优先队列priority_queue，每次求解子问题的解时，从优先级队列priority_queue中选取频率最小的两个字母（x、y）进行合并得到一个新的结点z，把x与y从优先级队列priority_queue中弹出，把压入到优先级队列priority_queue中。如此反复进行，直到优先级队列priority_queue中只有一个元素（根节点）为止。（3） 设计测试数据，写出程序文档。共设计了两组测试数据，他们的哈弗曼树如下图所示：图（1）测试数据的哈弗曼树图表一：第一组测试数据字符出现的频率a1b3c6d14e58表二：第二组测试数据字符出现的频率d4b3f5g6h14m16由图（1）可知各个字符的哈弗曼编码如下表：表三：表一中各元素的哈弗曼编码字符出现的频率a0000b0001c001d01e1表四：表二中各元素的哈弗曼编码字符出现的频率d001b000f010g011h10m11三、所用仪器、材料（设备名称、型号、规格等或使用软件）1台pc及visual c+6.0软件亿图程序流程图绘制软件四、实验方法、步骤（或：程序代码或操作过程） 下面源代码可以在visual c+6.0平台上运行！/author刘召 at 2011-11-18/this program is edited and compiled on visual studio 10 platform/huffman编码/#include stdafx.h/在visual studio中运行，应取消该句的注释！#include #include #include #include #include #includeusing namespace std;struct codeinformationdouble priority;char codename;int lchild,rchild,parent;bool test;bool operator (const codeinformation& x) const return !(priorityx.priority);bool check(vector qa,const char c)for (int i=0 ;i(int)(qa.size();i+)if(qai.codename=c) return true; return false;void aline(char c,int n)for (int i=0;in;i+)coutc;int inputelement(vector* harffcode,priority_queue* pq)int i=1,j=1;codeinformation wk;while(i)aline(-,80);cout请输入第j个元素的字符名称（ascll码）：wk.codename;while(check(* harffcode,wk.codename)coutwk.codename;cout请输入第j个元素的概率（权值）：wk.priority;wk.lchild=wk.rchild=wk.parent=-1;wk.test=false;harffcode-push_back(wk);pq-push(wk);j+;cout1继续输入下一个元素信息！endl;cout2已完成输入，并开始构造哈弗曼树！i;if (i=2) i=0;int count=1;j=harffcode-size();int selectelement(vector*,priority_queue*);for (int k=j;k2*j-1;k+)aline(*,80);cout第count次合并：push(wk);count+;cout所合成的节点名称：#（虚节点）t概率（权值）：(*harffcode)k.priorityendl;aline(*,80);return j;void showchar(const char c)if(isspace(c)cout#;coutc;int selectelement(vector*harffcode,priority_queue*qurgh)for (int i=0;i(int)(*harffcode).size();i+)if (*harffcode)i.priority=(*qurgh).top().priority)&(*harffcode)i.test=false)cout所选择的节点的信息：频率（权值）：setw(5)(*qurgh).top().priorityt名为：;showchar(*qurgh).top().codename);coutendl;(*qurgh).pop();(*harffcode)i.test=true;return i;void huffmancode(vector harffcode,int n)for (int i1=0;i1(int)harffcode.size();i1+)coutarrayi1的概率（权值）：harffcodei1.priorityt名为:;showchar(harffcodei1.codename);coutt父节点的数组下标索引值：harffcodei1.parentendl;aline(&,80);for (int i=0;i=0)if (harffcodeharffcodej.parent.lchild=j)s=s+0;else s=s+1;j=harffcodej.parent;coutn概率（权值）为:setw(8)harffcodei.priority 名为:;showchar(harffcodei.codename);cout0;i-)coutsi-1;void choise()coutendl;aline(+,80);coutn1继续使用该程序endl;cout2退出系统endl;void welcome()coutnsetw(56)欢迎使用赫夫曼编码简易系统nendl;couttttt学 校：昆明理工大学endl;couttttt学 院：信息工程与自动化学院endl;couttttt专 业：计算机科学与技术endl;couttttt指导老师：张晶endl;couttttt制 作 人：刘召endl;couttttt学 号：200910405201endl;coutttttqq 邮箱：329245767endl;int main()welcome();system(color d1); int i=1,n;vectorhufftree; priority_queueqptree; while(i!=2) n=inputelement(&hufftree,&qptree); huffmancode(hufftree, n);choise();cini;hufftree.clear(); while(qptree.empty() qptree.pop(); return 0;程序说明：在机器（内存）条件较好的情况下，原则上本程序可以对任意多个字符进行编码，本程序是动态扩展的，虽然不能很清晰地表述哈弗曼树种每一个节点的位置，不过可以根据合并过程输出的结果画出相应的哈弗曼树。本程序对哈弗曼树种的虚节点的名称统一用#表示。五、实验过程原始记录( 测试数据、图表、计算等)程序测试结果及分析：图（2）输入第一组测试数据开始输入第一组测试数据，该组数据信息如表一所示。其实，由于字母表中的各个字符是相互唯一的，在该程序中，若输入了一个与当前字母表中已存在的字符，则会提示重新输入该字符。图（3）对第一组数据进行合并，并计算各个字符的哈弗曼编码对第一组测试数据进行哈弗曼编码，并输出了各个结点合并的过程，及产生的新结点的信息，以便可以较为容易地手工画出该字母表的哈弗曼树。通过与表三对照可知，对各个字符的编码与最初的分析相符合。图（4）输入第二组测试数据在完成对第一组数据测试后，可以输入1 继续对下一组要编码的字母表进行哈弗曼编码。第二组要测试的数据信息如表2所示。图（5）对第二组数据进行哈弗曼编码的运行结果图把第二组数据进行哈弗曼编码的运行结果与表4对比可知，程序的运行结果与原来设计的结果相同。6、 实验结果、分析和结论（误差分析与数据处理、成果总结等。其中，绘制曲线图时必须用计算纸或程序运行结果、改进、收获）在实验过程中，当选择概率最小的结点时，要返回原数组下标的索引值，我一开始设想把结点分为两组进行存储，一组存储在向量里，另一组存储在优先级队列中，通过优先级队列可以较为容易地实现应该选择哪个结点，通过对向量操作，可以较为容易地实现对数组的操作，并且还具有动态的扩展性。通过优先级队列中顶层结点元素的频率与向量中结点