201440410234杜飞杨哈夫曼树的应用.doc

课程设计（论文） 编 号： B04900083学 号： 201440410234 课 程 设 计教 学 院计算机学院课程名称数据结构与算法课程设计题 目哈夫曼树的应用专 业计算机科学与技术班 级计算机科学与技术（2）班姓 名杜飞杨同组人员罗义飞 范永康 唐傲指导教师成俊2015年12月27日 课程设计任务书 20152016 学年 第 1学期学生姓名： 杜飞杨 专业班级： 计算机科学与技术（2）班 指导教师： 成俊 工作部门：计算机学院 一、课程设计题目：哈夫曼树的应用二、课程设计内容1) 从终端读入字符集大小n，以及n个字符和n个权值，建立哈夫曼树并将它存于文件hfmTree中.将已在内存中的哈夫曼树以直观的方式（比如树）显示在终端上；2) 利用已经建好的哈夫曼树（如不在内存，则从文件htmTree中读入），对文件Text.txt中的正文进行编码，然后将结果存入文件Code.txt中。3) 利用已建好的哈夫曼树将文件Code.txt中的代码进行译码，结果存入文件Text.txt中，并输出结果。三、进度安排1分析问题，给出数学模型，选择数据结构。2设计算法，给出算法描述，给出源程序清单。3编辑、编译、调试源程序，撰写课程设计报告。四、基本要求1.界面友好，函数功能要划分好2.总体设计应画一流程图3.程序要加必要的注释4.要提供程序测试方案5.程序一定要经得起测试，宁可功能少一些，也要能运行起来，不能运行的程序是没有价值的。目录一、概述3（一）课程设计目的3（二）课程设计实验要求3二、总体设计4（一） 设计思想4（二）数据结构与算法设计4(三) 个人任务6三、详细设计7(一)功能函数模块划分7（二）个人任务7四、调试分析和测试结果10五、心得体会与总结13六、参考文献14一、概述1.1课程设计目的1理解和掌握该课程中的有关基本概念，程序设计思想和方法。2培养综合运用所学知识独立完成课题的能力。3培养勇于探索、严谨推理、实事求是、有错必改，用实践来检验理论，全方位考虑问题等科学技术人员应具有的素质。4掌握从资料文献、科学实验中获得知识的能力，提高学生从别人经验中找到解决问题的新途径的悟性，初步培养工程意识和创新能力。1.2课程设计实验要求从终端读入字符集大小n，以及n个字符和n个权值，建立哈夫曼树并将它存于文件hfmTree中.将已在内存中的哈夫曼树以直观的方式（比如树）显示在终端上；利用已经建好的哈夫曼树（如不在内存，则从文件htmTree中读入），对文件text.txt中的正文进行编码，然后将结果存入文件Code中，并输出结果，将文件Code以紧凑格式先是在终端上，每行50个代码。同时将此字符形式的编码文件写入文件CodePrint中。利用已建好的哈夫曼树将文件Code中的代码进行译码，结果存入文件Text中，并输出结果。 二、总体设计2.1 设计思想哈夫曼树用邻接矩阵作为存储结构，借助静态链表来实现遍历。2.2数据结构与算法设计哈夫曼编译码器的主要功能是先建立哈夫曼树，然后利用建好的哈夫曼树生成哈夫曼编码后进行译码 。在数据通信中，经常需要将传送的文字转换成由二进制字符0、1组成的二进制串，称之为编码。构造一棵哈夫曼树，规定哈夫曼树中的左分之代表0，右分支代表1，则从根节点到每个叶子节点所经过的路径分支组成的0和1的序列便为该节点对应字符的编码，称之为哈夫曼编码。最简单的二进制编码方式是等长编码。若采用不等长编码，让出现频率高的字符具有较短的编码，让出现频率低的字符具有较长的编码，这样可能缩短传送 其主要流程图如下图所示。开始结点数是否大于1将data和权值赋给ht输出根结点和权值调用SELECT函数计算根结点函数父结点为两子结点之和输出两子结点和已构造的结点是否为根结点？左子是否为空？此时编码为0I2*N?I+编码为1结束否否否右子是否为空是是否否是是是哈夫曼树编译码器流程图2.3 个人任务我在组内负责哈弗曼树的数据结构设计与哈弗曼树的译码和哈夫曼树的数据结构：假设有n个权值，则构造出的哈夫曼树有n个叶子结点。n个权值分别设为w1、w2、wn，则哈夫曼树的构造规则为：(1)将w1、w2、，wn看成是有n棵树的森林(每棵树仅有一个结点)；(2)在森林中选出两个根结点的权值最小的树合并，作为一棵新树的左、右子树，且新树的根结点权值为其左、右子树根结点权值之和；(3)从森林中删除选取的两棵树，并将新树加入森林；(4)重复(2)、(3)步，直到森林中只剩一棵树为止，该树即为所求得的哈夫曼树。构造过程如下：（a）有权值为1,2,3,4四棵树；（b）由于树1,2的权值处于最小和次最小，所以选中，并合成为一棵树，小的权值位于左边；（c）从3,4，（1,2=3）三棵树里面选择权值最小的和次小的，我们选中3和（1,2）合成新树（3，（1,2）=6）；（d）最后选出新树（4，（3，（1，2）哈夫曼树的译码：假设有n个权值，则构造出的哈夫曼树有n个叶子结点。 n个权值分别设为 w1、w2、wn，则哈夫曼树的构造规则为： (1) 将w1、w2、，wn看成是有n 棵树的森林(每棵树仅有一个结点)； (2) 在森林中选出两个根结点的权值最小的树合并，作为一棵新树的左、右子树，且新树的根结点权值为其左、右子树根结点权值之和； (3)从森林中删除选取的两棵树，并将新树加入森林； (4)重复(2)、(3)步，直到森林中只剩一棵树为止，该树即为所求得的哈夫曼树三、详细设计3.1功能函数模块划分（1）哈夫曼编码：首先定义函数，找出全部权值中最小的两个，然后定义一个变量，使他始终成为最小的那个。再将两个函数最为叶子结点，并得到一个父亲节点，此父亲节点的权值为其叶子节点的权值之和。并将此父亲节点的权值与其余权值进行比较，重新选出两个最小的权值，再进行上述步骤，直到所有权值形成了一颗二叉树，而此二叉树就是我们所说的最优二叉树，即哈夫曼树。以上为哈夫曼树的建立过程，下面为哈夫曼编码的过程，从叶子节点出发，若此叶子节点为其父亲节点的左孩子，则将其编码为0，若为右孩子，则将其编码为1，然后为其父亲节点编码，若为祖先的左孩子，则变为0，为右孩子则为1，依次向上一层进行遍历，直到遍历到根节点，停止编码。（2）译码：对于已经建好的哈夫曼树，要对其进行译码，首先从根出发如果编码为0，则往左孩子遍历，如果编码为1，则往右孩子遍历，直到遍历到叶子节点，便求得该子串相应的字符。（3）初始化哈夫曼链表:首先输入结点个数，再将字符及权值输入，调用编码函数，得到每个字符编码并将其输出。最后将哈夫曼编码写入文件。（4）完成编码功能：打开目录下文件text.txt，读取里面的字符，对其进行编码后，将编码写入目录下的code.txt中。（5）完成译码功能：打开根目录下code.txt文件，读取里面的编码，对其中的编码进行译码，并将得到的内容写入根目录下的文件text.txt中。（6）打印编码（7）打印哈夫曼树3.2个人任务 我在组内组要负责哈弗曼树的数据结构设计与哈弗曼树的译码 。1） 数据结构设计：typedef struct /哈夫曼树的存储表示 int weight; /权值int parent,lchild,rchild; /父节点，左孩子结点，右孩子结点HTNode,* HuffmanTree; /动态分配数组存储哈夫曼树typedef char *HuffmanCode;/动态分配数组存储哈夫曼编码表/-全局变量-HuffmanTree HT; /代表哈夫曼树HuffmanCode HC; /代表哈夫曼编码int *w,i,j,n; char *z;int flag=0; int numb=0;2） 译码：void decode() /完成译码功能cout下面对根目录下文件code.txt中的字符进行译码endl;FILE *codef,*text;if(text=fopen(Text.txt,w)=NULL)cout不能打开文件endl;if (codef=fopen(code.txt,r)=NULL)cout不能打开文件endl;char *tbdc,*outext,i2;int io=0,i,m;unsigned long length=10000;tbdc=(char*)malloc(length*sizeof(char); /分配空间fgets(tbdc,length,codef);outext=(char*)malloc(length*sizeof(char); /分配空间m=2*n-1;for(i=0;*(tbdc+i)!=0;i+) /进入循环i2=*(tbdc+i);if(HTm.lchild=0) *(outext+io)=*(z+m-1);io+;m=2*n-1;i-;else if(i2=0) m=HTm.lchild;else if(i2=1) m=HTm.rchild;*(outext+io)=0;fputs(outext,text);cout译码完成endl内容写入根目录下的文件text.txt中endlendl;free(tbdc);free(outext);fclose(text);fclose(codef);四、调试分析和测试结果（一） 初始化哈夫曼链表:首先输入要执行的操作i,然后输入8个字符按回车结束，以及每个字符的权值初始化结束。（二）编码字符：根据设计好的程序，输入w执行编码字符的操作，然后输入想要编码的字符注意必须是初始化时输入过的字符。（三）编码：根据提示，输入e执行对text.txt文件的哈夫曼树的编码，编码写入code.txt文件下。（四）译码：对写入到code.txt代码译码，并输入d进行译码，内容写入text.txt文件下。（五）打印编码：根据提示，输入p对编码和译码后的字符进行打印编码。（六）打印哈夫曼函数：最后输入t打印哈夫曼树，显示打印结果和打印结束。五、心得体会与总结对于本次课程设计，主要是需要掌握哈夫曼树建立、哈夫曼编码以及哈夫曼译码的算法。并能将其熟练应用于编译码器的完成。经过这次的课程设计，使我们更加了解了数据结构，也更深入地了解了哈夫曼编码与译码算法，课程设计的题目比我们平常的实验内容要难，完成它不仅需要有厚实的语言基础，而且还要熟练掌握哈夫曼编码与译码的算法，另外对于文件的基本操作也需要熟悉。通过数据结构课程设计，我的C+语言水平有了比较大的提高其中。C+语言关于类的操作理解的比以前深刻不少。另外是数据结构方面的提高对哈夫曼树的构造及哈夫曼码方面也有不少的提高。 在项目中也出现了很多的问题,最大的问题就是对程序设计框架结构的不了解,在实现代码与功能的连接时经常会出现各种不同的错误,在实现一些功能时系统常常会报错。许多错误不知从哪修改以致拖了整个设计的后腿。课程设计中，既回顾了很多以前的东西，也发现了很多的问题以前都没遇见过的，收获很大。 通过本次数据结构的课程设计，我学习了很多在上课没懂的知识，并对求哈夫曼树及哈夫曼编码/译码的算法有了更加深刻的了解，更巩固了课堂中学习有关于哈夫曼编码的知识。 此次哈夫曼树的应用系统的设计让自己对数据结构的了解更深入。六、参考文献1 严蔚敏,吴伟民.数据结构（C语言版）M. (第一版)北京：清华大学出版社.1997 2 Sartaj Sahni. Data Structure, Algorithms, and Application in C+. The McGraw-Hill Company Inc.1998M (第一版) (数据结构、算法与应用C+语言描述.北京:机械工业出版社.19993 Willan Ford,Willian Topp. Data Structures with C+. New Jersey:Prentice Hall Inc, Adivision Simon & Schuster Company,1996M (第一版) (数据结构C+语言描述.北京:清华大学出版社，19974 徐孝凯.数据结构实用教程（C/C+描述）M. (第一版)北京:清华大学出版社.19995 陈慧南.数据结构（使用C+语言描述）M. (第一版)南京:东南大学出版社.20016 殷人昆,陶永雷,谢若阳等.数据结构（用面向对象方法与C+描述）M. (第一版)北京:清华大学出版社.1999 数据结构与算法 课程设