构造带哈夫曼树并能算出带权路径程度
西安文理学院软件学院
课程设计报告
设计名称：设计题目： 构造哈夫曼树的哈夫曼算法 学生学号： 专业班级：
学生姓名： 学生成绩： 指导教师（职称）： 课题工作时间： 2014.6.16 至 2014.6.27
软件学院课程设计任务书
指导教师： 院长：
日 期：2014年6月16日
软件学院课程设计进度安排表
学生姓名： 学号： 专业： 软件工程 班级： 1班
指导教师签名：
2014年6月16日
成绩评定表
学生姓名： 学号： 专业： 软件工程 班级： 1班
摘 要
摘要： 设计程序以实现构造哈夫曼树的哈夫曼算法,该程序的目的是求解出所构造的哈夫曼树的带权路径长度。利用哈夫曼树的结构，求出指令的哈夫曼代码，同时求出叶子节点的带权路径长度。依次输入五个值分别算出其权值，最后输出所构造的哈夫曼树的带权路径长度。
关键词：数组；带权路径长度；结点.
西安文理学院计算机科学系 课程设计报告
目 录
摘 要 ............................................................................................................................................................. v 目 录 ................................................................................................................................................................ I 第一章 课题背景 ......................................................................................................................................... 2
1.1 课题背景 ......................................................................................................................................... 2
1.11课题背景知识 ........................................................................................................................ 2 1.2课题目的与意义 ...................................................................................................................... 2 1.2.1课题的目的 .......................................................................................................................... 2 1.2.2课题意义 .............................................................................................................................. 2
第二章 设计简介及设计方案论述 ............................................................................................................. 3
2.1 系统分析 ......................................................................................................................................... 3
2.1.1 功能需求 ............................................................................................................................. 3 2.1.2 数据需求 ............................................................................................................................. 3 2.1.3 系统需求 ............................................................................................................................. 3 2.2 主要难点 ........................................................................................................................................ 3 第三章 详细设计 ......................................................................................................................................... 4
3.1 程序结构分析 ................................................................................................................................. 4
3.1.1 图示 ..................................................................................................................................... 4 3.1.2程序模块设计 ...................................................................................................................... 4
第四章 设计结果及分析 ............................................................................................................................. 7
4.1 程序运行结果 ................................................................................................................................. 7
4.1.1 截图 ..................................................................................................................................... 7 4.2运行结果分析 .......................................................................................................................... 7 4.2.1测试 ...................................................................................................................................... 7
总结 ................................................................................................................................................................. 8 参考文献 ......................................................................................................................................................... 9 附录 ............................................................................................................................................................... 10
第一章 课题背景
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 图示
3-1函数流程图
3.1.2程序模块设计
1）建立叶结点个数为n权值为weight的哈夫曼树haffTree void Haffman(int weight[], int n, HaffNode haffTree[]) { int j, m1, m2, x1, x2; //哈夫曼树haffTree初始化。n个叶结点的哈夫曼树共有2n-1个结点
for(int i=0;i
2) 将找出的两棵权值最小的子树合并为一棵子树 for(int k=0;k
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=haffTree[i].weight; //取得编码对应权值的字符 child=i; parent=haffTree[child].parent; //由叶结点向上直到根结点 while(parent!=0) { if(haffTree[parent].leftChild == child)
西安文理学院软件学院 课程设计报告}cd->bit[cd->start] = 0; //左孩子结点编码0 else cd->bit[cd->start] = 1; //右孩子结点编码1 cd->start--; child=parent; parent=haffTree[child].parent; //保存叶结点的编码和不等长编码的起始位 for(int j=cd->start+1;jbit[j]; haffCode[i].start=cd->start; haffCode[i].weight=cd->weight; //保存编码对应的权值} }-6-
西安文理学院软件学院 课程设计报告第四章4.1 程序运行结果4.1.1 截图设计结果及分析4.2 运行结果分析该运行结果为输入了五个结点的权值之后所得到的哈夫曼编码和所得到的 带权路径长度， 通过本次试验我更好地了解了哈夫曼树的结构，知道了最优二树 的优点与实际应用，学会了怎么求哈夫曼树的带权路径长度。4.2.1 测试软件测试是软件生存期中的一个重要阶段， 是软件质量保证的关键步骤从用 户的角度来看， 普遍希望通过软件测试暴露软件中隐藏的错误和缺陷，所以软件 测试应该是“为了发现错误而执行程序的过程”。或者说，软件测试应该根据软 件开发各阶段的规格说明和程序的内部结构而精心设计一批测试用例 （即输入数 据及其预期的输出结果） ，并利用这些测试用例去运行程序，以发现程序错误或 缺陷。过度测试则会浪费许多宝贵的资源。到测试后期，即使找到了错误，然而 付出了过高的代价。-7-
西安文理学院软件学院 课程设计报告总结在我自己课程设计中， 就在编写好源代码后的调试中出现了不少的错误， 遇到了很多麻 烦及困难，我的调试及其中的错误和我最终找出错误，修改为正确的能够执行的程序中，通 过分析，我学到了：在定义头文件时可多不可少，即我们可多写些头文件，肯定不会出错， 但是若没有定义所引用的相关头文件， 必定调试不通过； 在这次课程设计中我学习了很多在 上课没懂的知识， 并对求哈夫曼树的算法有了更加深刻的了解， 更巩固了课堂中学习有关于 哈夫曼编树的知识，真正学会了一种算法。当求解一个算法时,不是拿到问题就不加思索地 做，而是首先要先对它有个大概的了解，接着再详细地分析每一步怎么做，无论自己以前是 否有处理过相似的问题，只要按照以上的步骤，必定会顺利地做出来。通过本次数据结构的 课程设计，虽然程序运行结果基本正确，能实现实验要求的功能，但也存在不足的地方，如 运行界面不美观，程序语句不精练，有些地方可以更加简单等等。这些都需要我在以后的实 验中着重注意并加以学习，另外，这次实验编程我花的时间较短，因为学期末复习工作比较 忙，所以本程序还有一些不足之处。-8-
西安文理学院软件学院 课程设计报告参考文献[1]严蔚敏 吴伟民编.《数据结构（c 语言版） 》. 清华大学出版社,2010.9 [2] 韩利凯,李军.数据结构 浙江大学出版社 [M] 2013.8[3]谭浩强编.《C 程序设计》.清华大学出版社 2010.6 [4] 唐国民,王国均. 数据结构(C 语言版)[M]. 北京:清华大学出版社. [5] 王路明. C 语言程序设计教程[M]. 北京:北京邮电大学出版社,2005 年 5 月. [6] 谭浩强. C++程序设计[M]. 北京:清华大学出版社.2004. [7]范策. 算法与数据结构（C 语言版)[M]. 北京:机械工业出版社，2004. [8] 詹春华,杨沙. C 语言程序设计教程[M]. 科学出版社,2011.8.-9-
西安文理学院软件学院 课程设计报告附录#include #include #include const 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 bit[MaxN]; int start; int weight; }; //初始设定的权值最大值 //初始设定的最大编码位数 //初始设定的最大结点个数 //哈夫曼树的结点结构 //权值 //标记 //双亲结点下标 //左孩子下标 //右孩子下标 //存放哈夫曼编码的数据元素结构 //数组 //编码的起始下标 //字符的权值void Haffman(int weight[], int n, HaffNode haffTree[]) //建立叶结点个数为n 权值为weight的哈夫曼树haffTree { int j, m1, m2, x1, x2; //哈夫曼树haffTree初始化。n个叶 结点的哈夫曼树共有2n-1个结点 for(int i=0;i
西安文理学院软件学院 课程设计报告} } //将找出的两棵权值最小的子树合 并为一棵子树 haffTree[x1].parent = n+k; haffTree[x2].parent = n+k; haffTree[x1].flag = 1; haffTree[x2].flag = 1; haffTree[n+k].weight = haffTree[x1].weight+haffTree[x2].weight; haffTree[n+k].leftChild = x1; haffTree[n+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=haffTree[i].weight; //取得编码对应权值的字符 child=i; parent=haffTree[child].parent; //由叶结点向上直到根结点 while(parent!=0) { if(haffTree[parent].leftChild == child) cd->bit[cd->start] = 1; //左孩子结点编码0 else cd->bit[cd->start] = 0; //右孩子结点编码1 cd->start--; child=parent; parent=haffTree[child].parent; } //保存叶结点的编码和不等长编 码的起始位 for(int j=cd->start+1;jbit[j]; haffCode[i].start=cd->start; haffCode[i].weight=cd->weight; //保存编码对应的权值 } } int main() { cout
西安文理学院软件学院 课程设计报告Haffman(weight, n, myHaffTree); HaffmanCode(myHaffTree, n, myHaffCode); //输出每个叶结点的哈夫曼 编码 for(i=0;i
西安文理学院软件学院 课程设计报告- 13 -