构造带哈夫曼树并能算出带权路径程度.doc

西安文理学院软件学院课程设计报告设计名称： 数据结构课程设计 设计题目： 构造哈夫曼树的哈夫曼算法 学生学号： 专业班级： 学生姓名： 学生成绩： 指导教师（职称）： （教授） 课题工作时间： 2014.6.16 至 2014.6.27 软件学院课程设计任务书学生姓名学号专业班级 设计题目构造哈夫曼树的哈夫曼算法内容概要： 设计或开发环境：Microsoft Visual Studio 2010 关键技术：C语言 主要功能：能求解出所构造的哈夫曼树的带权路径长度。文献资料：1严蔚敏 吴伟民编.数据结构（c语言版）. 清华大学出版社,2010.92 韩利凯,李军.数据结构 浙江大学出版社 M 2013.83谭浩强编.C程序设计.清华大学出版社 2010.6设计要求：（1）可以使用实验工具的有关功能。（2）要能演示构造过程。（3）求解出所构造的哈夫曼树的带权路径长度。工作期限：设计工作自2014年6月16日至2014年6月27日止。指导教师： 院长： 日 期：2014年6月16日软件学院课程设计进度安排表学生姓名： 学号： 专业： 软件工程 班级： 1班 起止日期内 容备注6月16日 6月 17日下任务书；收集、阅读、整理相关参考文献，并进行归纳和概括总结，完成项目/任务背景介绍部分文字内容。6月18日11月20日系统功能设计和模块设计、系统体系结构构建。6月21日6月24日各功能模块编码实现，系统各功能模块调试与维护。6月25日6月26日系统功能集成、系统调试与测试，按照模板要求撰写课程设计/项目设计报告。6月27日课程设计/项目设计分组答辩，提交课程设计/项目设计报告以及相关文档，进行成绩评定。指导教师签名： 2014年6月16日成绩评定表学生姓名： 学号： 专业： 软件工程 班级： 1班 类别合计分值各项分值评分标准实际得分合计得分平时表现1010按时参加设计指导，无违反纪律情况。完成情况3020按设计任务书的要求完成了全部任务，能完整演示其设计内容，符合要求。10能对其设计内容进行详细、完整的介绍，并能就指导教师提出的问题进行正确的回答。报告质量3510报告文字通顺，内容翔实，论述充分、完整，立论正确，结构严谨合理；报告字数符合相关要求，工整规范，整齐划一。5课题背景介绍清楚，综述分析充分。5设计方案合理、可行，论证严谨，逻辑性强，具有说服力。5符号统一；图表完备、符合规范要求。5能对整个设计过程进行全面的总结，得出有价值的结论或结果。5参考文献数量在2篇以上，格式符合要求，在正文中正确引用。答辩情况2510在规定时间内能就所设计的内容进行阐述，言简意明，重点突出，论点正确，条理清晰。15在规定时间内能准确、完整、流利地回答教师所提出的问题。总评成绩： 分 指导教师： （签字） 日期：2014 年6月 27 日摘 要 摘要： 设计程序以实现构造哈夫曼树的哈夫曼算法,该程序的目的是求解出所构造的哈夫曼树的带权路径长度。利用哈夫曼树的结构，求出指令的哈夫曼代码，同时求出叶子节点的带权路径长度。依次输入五个值分别算出其权值，最后输出所构造的哈夫曼树的带权路径长度。 关键词：数组；带权路径长度；结点.西安文理学院软件学院 课程设计报告目 录摘 要v目 录I第一章 课题背景21.1 课题背景21.11课题背景知识21.2课题目的与意义21.2.1课题的目的21.2.2课题意义2第二章 设计简介及设计方案论述32.1 系统分析32.1.1 功能需求32.1.2 数据需求32.1.3 系统需求32.2 主要难点3第三章 详细设计43.1 程序结构分析43.1.1 图示43.1.2程序模块设计4第四章 设计结果及分析74.1 程序运行结果74.1.1 截图74.2运行结果分析74.2.1测试7总结8参考文献9附录10- 12 -第一章 课题背景1.1 课题背景1.11课题背景知识 在实际生活和生产应用中，我们往往会遇到综合比较一系列的离散量的问题；比如说车站根据包裹的重量以及旅途的长短来确定携带行李的价格，或者我们根据一定的重量范围来给一箱铁球进行分类。我们说在现实的分类中，每一类数据出现的概率不尽相同；这些数据出现的概率可以被看做哈夫曼树中叶子的权值。为了获取最短的路径，也就是带权路径长度最短的二叉树，我们希望那些权值低的数据拥有相对较长的对根结点的路径长度。1.2课题目的与意义1.2.1课题的目的 本课题的目的是让同学们理解哈夫曼算法，并能利用自己已经学习的知识，去解决一些现实生活中出现的问题。比如各个城市之间需要联网问题，利用哈夫曼树的相关知识就能对这一问题作出很好的解决。1.2.2课题意义 一个好的算法可以更快的解决问题，所以平时在学习编程的时候应该着重理解一些基础的算法。 第二章 设计简介及设计方案论述2.1 系统分析2.1.1 功能需求（1）可以使用实验工具的有关功能。（2）要能演示构造过程。（3）求解出所构造的哈夫曼树的带权路径长度。2.1.2 数据需求在输入过程中，首先要给定输入的数据，数据只能是数字，不能是字母或其他，不能连续输入数据，必须要求以换行分开要输入的数据。2.1.3 系统需求 系统必须安全可靠，不会出现无故死机状态，本程序较小，系统可以正常运行即可。2.2 主要难点(1)构造哈夫曼树：根据给定的权值构成二叉树集合，其中每棵二叉树中只有一个带权的根节点，其左右子树均为空；在二叉树集合中选取两棵根节点权值最小的树作为左右子树构造一棵新的二叉树，且新的二叉树的根节点的权值为其左、右子树上根节点的权值之和；在二叉树集合中删除这两棵树，并将得到的二叉树加入集合中；重复上述步骤，直至二叉树集合中只含一棵树为止。(2)求带权路径长度：先求每个叶子结点到树根之间的路径长度与该叶子结点所带权值之积，在将所得之积求和。 第三章 详细设计3.1 程序结构分析开始3.1.1 图示设定结点最大值输入n个结点的权值For循环找出权值最小的两结点输入初始状态图调用haffTree()函数构造哈夫曼树引用sum（）函数求带权路径长度输出带权路径长度结束 3-1函数流程图3.1.2程序模块设计1）建立叶结点个数为n权值为weight的哈夫曼树haffTreevoid Haffman(int weight, int n, HaffNode haffTree) int j, m1, m2, x1, x2;/哈夫曼树haffTree初始化。n个叶结点的哈夫曼树共有2n-1个结点 for(int i=0;i2*n-1;i+)if(in) haffTreei.weight=weighti;else haffTreei.weight=0;haffTreei.parent=0;haffTreei.flag=0;haffTreei.leftChild=-1;haffTreei.rightChild=-1; /构造哈夫曼树haffTree的n-1个非叶结点2) 将找出的两棵权值最小的子树合并为一棵子树 for(int k=0;kn-1;k+)m1=m2=MaxValue;x1=x2=0;for(j=0;jn+k;j+)if (haffTreej.weight m1 & haffTreej.flag = 0) m2=m1; x2=x1; m1=haffTreej.weight; x1=j; else if(haffTreej.weight m2 & haffTreej.flag = 0) m2 = haffTreej.weight;x2 = j;3)由n个结点的哈夫曼树haffTree构造哈夫曼编码haffCode void HaffmanCode(HaffNode haffTree, int n, Code haffCode) Code *cd = new Code; int child, parent;/求n个叶结点的哈夫曼编码 for(int i=0;istart=n-1;/不等长编码的最后一位为n-1 cd-weight=haffTreei.weight; /取得编码对应权值的字符 child=i;parent=haffTreechild.parent; /由叶结点向上直到根结点 while(parent!=0) if(haffTreeparent.leftChild = child)cd-bitcd-start = 0;/左孩子结点编码0 elsecd-bitcd-start = 1;/右孩子结点编码1 cd-start-; child=parent;parent=haffTreechild.parent; /保存叶结点的编码和不等长编码的起始位for(int j=cd-start+1;jbitj; haffCodei.start=cd-start; haffCodei.weight=cd-weight; /保存编码对应的权值第四章 设计结果及分析4.1 程序运行结果4.1.1 截图4.2运行结果分析 该运行结果为输入了五个结点的权值之后所得到的哈夫曼编码和所得到的带权路径长度，通过本次试验我更好地了解了哈夫曼树的结构，知道了最优二树的优点与实际应用，学会了怎么求哈夫曼树的带权路径长度。 4.2.1测试软件测试是软件生存期中的一个重要阶段，是软件质量保证的关键步骤从用户的角度来看，普遍希望通过软件测试暴露软件中隐藏的错误和缺陷，所以软件测试应该是“为了发现错误而执行程序的过程”。或者说，软件测试应该根据软件开发各阶段的规格说明和程序的内部结构而精心设计一批测试用例（即输入数据及其预期的输出结果），并利用这些测试用例去运行程序，以发现程序错误或缺陷。过度测试则会浪费许多宝贵的资源。到测试后期，即使找到了错误，然而付出了过高的代价。 总结 在我自己课程设计中，就在编写好源代码后的调试中出现了不少的错误，遇到了很多麻烦及困难，我的调试及其中的错误和我最终找出错误，修改为正确的能够执行的程序中，通过分析，我学到了：在定义头文件时可多不可少，即我们可多写些头文件，肯定不会出错，但是若没有定义所引用的相关头文件，必定调试不通过；在这次课程设计中我学习了很多在上课没懂的知识，并对求哈夫曼树的算法有了更加深刻的了解，更巩固了课堂中学习有关于哈夫曼编树的知识，真正学会了一种算法。当求解一个算法时,不是拿到问题就不加思索地做，而是首先要先对它有个大概的了解，接着再详细地分析每一步怎么做，无论自己以前是否有处理过相似的问题，只要按照以上的步骤，必定会顺利地做出来。通过本次数据结构的课程设计，虽然程序运行结果基本正确，能实现实验要求的功能，但也存在不足的地方，如运行界面不美观，程序语句不精练，有些地方可以更加简单等等。这些都需要我在以后的实验中着重注意并加以学习，另外，这次实验编程我花的时间较短，因为学期末复习工作比较忙，所以本程序还有一些不足之处。 参考文献1严蔚敏 吴伟民编.数据结构（c语言版）. 清华大学出版社,2010.92 韩利凯,李军.数据结构 浙江大学出版社 M 2013.83谭浩强编.C程序设计.清华大学出版社 2010.64 唐国民,王国均. 数据结构(C语言版)M. 北京:清华大学出版社.5 王路明. C语言程序设计教程M. 北京:北京邮电大学出版社,2005年5月.6 谭浩强. C+程序设计M. 北京:清华大学出版社.2004.7范策. 算法与数据结构（C语言版)M. 北京:机械工业出版社，2004.8 詹春华,杨沙. C语言程序设计教程M. 科学出版社,2011.8.附录#include #include #includeconst int MaxValue = 1000;/初始设定的权值最大值const int MaxBit = 4;/初始设定的最大编码位数const int MaxN = 10;/初始设定的最大结点个数struct HaffNode/哈夫曼树的结点结构int weight;/权值int flag;/标记int parent;/双亲结点下标int leftChild;/左孩子下标int rightChild;/右孩子下标;struct Code/存放哈夫曼编码的数据元素结构int bitMaxN;/数组int start;/编码的起始下标int weight;/字符的权值;void Haffman(int weight, int n, HaffNode haffTree) /建立叶结点个数为n权值为weight的哈夫曼树haffTreeint j, m1, m2, x1, x2;/哈夫曼树haffTree初始化。n个叶结点的哈夫曼树共有2n-1个结点 for(int i=0;i2*n-1;i+)if(in) haffTreei.weight=weighti;else haffTreei.weight=0;haffTreei.parent=0;haffTreei.flag=0;haffTreei.leftChild=-1;haffTreei.rightChild=-1; /构造哈夫曼树haffTree的n-1个非叶结点for(int k=0;kn-1;k+)m1=m2=MaxValue;x1=x2=0;for(j=0;jn+k;j+)if (haffTreej.weight m1 & haffTreej.flag = 0) m2=m1; x2=x1; m1=haffTreej.weight; x1=j; else if(haffTreej.weight m2 & haffTreej.flag = 0) m2 = haffTreej.weight;x2 = j;/将找出的两棵权值最小的子树合并为一棵子树haffTreex1.parent = n+k;haffTreex2.parent = n+k;haffTreex1.flag = 1; haffTreex2.flag = 1;haffTreen+k.weight = haffTreex1.weight+haffTreex2.weight; haffTreen+k.leftChild = x1;haffTreen+k.rightChild = x2;void HaffmanCode(HaffNode haffTree, int n, Code haffCode) /由n个结点的哈夫曼树haffTree构造哈夫曼编码haffCode Code *cd = new Code; int child, parent;/求n个叶结点的哈夫曼编码 for(int i=0;istart=n-1;/不等长编码的最后一位为n-1 cd-weight=haffTreei.weight; /取得编码对应权值的字符 child=i;parent=haffTreechild.parent; /由叶结点向上直到根结点 while(parent!=0) if(haffTreeparent.leftChild = child)cd-bitcd-start = 1;/左孩子结点编码0 elsecd-bitcd-start = 0;/右孩子结点编码1 cd-start-; child=parent;parent=haffTreechild.parent; /保存叶结点的编码和不等长编码的起始位for(int j=cd-start+1