![算法设计与分析实验报告-哈夫曼编码(含源程序).doc_第1页](http://file.renrendoc.com/FileRoot1/2019-7/20/7249caee-1d1b-4644-b259-eab0eb2f0b9e/7249caee-1d1b-4644-b259-eab0eb2f0b9e1.gif)
![算法设计与分析实验报告-哈夫曼编码(含源程序).doc_第2页](http://file.renrendoc.com/FileRoot1/2019-7/20/7249caee-1d1b-4644-b259-eab0eb2f0b9e/7249caee-1d1b-4644-b259-eab0eb2f0b9e2.gif)
![算法设计与分析实验报告-哈夫曼编码(含源程序).doc_第3页](http://file.renrendoc.com/FileRoot1/2019-7/20/7249caee-1d1b-4644-b259-eab0eb2f0b9e/7249caee-1d1b-4644-b259-eab0eb2f0b9e3.gif)
![算法设计与分析实验报告-哈夫曼编码(含源程序).doc_第4页](http://file.renrendoc.com/FileRoot1/2019-7/20/7249caee-1d1b-4644-b259-eab0eb2f0b9e/7249caee-1d1b-4644-b259-eab0eb2f0b9e4.gif)
![算法设计与分析实验报告-哈夫曼编码(含源程序).doc_第5页](http://file.renrendoc.com/FileRoot1/2019-7/20/7249caee-1d1b-4644-b259-eab0eb2f0b9e/7249caee-1d1b-4644-b259-eab0eb2f0b9e5.gif)
已阅读5页,还剩6页未读, 继续免费阅读
版权说明:本文档由用户提供并上传,收益归属内容提供方,若内容存在侵权,请进行举报或认领
文档简介
昆明理工大学信息工程与自动化学院学生实验报告( 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、 实验结果、分析和结论(误差分析与数据处理、成果总结等。其中,绘制曲线图时必须用计算纸或程序运行结果、改进、收获)在实验过程中,当选择概率最小的结点时,要返回原数组下标的索引值,我一开始设想把结点分为两组进行存储,一组存储在向量里,另一组存储在优先级队列中,通过优先级队列可以较为容易地实现应该选择哪个结点,通过对向量操作,可以较为容易地实现对数组的操作,并且还具有动态的扩展性。通过优先级队列中顶层结点元素的频率与向量中结点
温馨提示
- 1. 本站所有资源如无特殊说明,都需要本地电脑安装OFFICE2007和PDF阅读器。图纸软件为CAD,CAXA,PROE,UG,SolidWorks等.压缩文件请下载最新的WinRAR软件解压。
- 2. 本站的文档不包含任何第三方提供的附件图纸等,如果需要附件,请联系上传者。文件的所有权益归上传用户所有。
- 3. 本站RAR压缩包中若带图纸,网页内容里面会有图纸预览,若没有图纸预览就没有图纸。
- 4. 未经权益所有人同意不得将文件中的内容挪作商业或盈利用途。
- 5. 人人文库网仅提供信息存储空间,仅对用户上传内容的表现方式做保护处理,对用户上传分享的文档内容本身不做任何修改或编辑,并不能对任何下载内容负责。
- 6. 下载文件中如有侵权或不适当内容,请与我们联系,我们立即纠正。
- 7. 本站不保证下载资源的准确性、安全性和完整性, 同时也不承担用户因使用这些下载资源对自己和他人造成任何形式的伤害或损失。
最新文档
- 交通银行福建分行社会招聘笔试真题2023
- 北海市政府采购中心招聘笔试真题2023
- 结构力学优化算法:灵敏度分析:有限元方法在结构优化中的应用
- 开学第一课-一年级开学第一课
- 气动工具作业安全技术操作规程
- 黄金卷08(解析版)-【赢在高考·黄金8卷】备战2024年高考地理模拟卷(湖北专用)
- 黄金卷02(考试版)-【赢在高考·黄金8卷】备战2024年高考地理模拟卷(全国卷老教材)
- 适用于新高考新教材备战2025届高考历史一轮总复习第1单元从中华文明起源到秦汉统一多民族封建国家的建立与巩固课时练第2讲诸侯纷争与变法运动课件
- 数字电子技术(第3版)-课件 第五章2
- 卒中个案护理
- GB/T 23547-2009浓酱兼香型白酒
- GB/T 20284-2006建筑材料或制品的单体燃烧试验
- GB/T 12957-2005用于水泥混合材的工业废渣活性试验方法
- GB/T 12467.2-2009金属材料熔焊质量要求第2部分:完整质量要求
- 生活垃圾填埋场污染控制标准
- 肠内营养理论知识试题含答案
- 智慧厂房智能化系统建设方案
- 能源与动力工程专业英语词汇
- 《再喂养综合症》课件
- JTG A02-2013公路工程行业标准管理导则
- 患者搬运法操作流程课件
评论
0/150
提交评论