数据结构实验四(哈弗曼编码).doc

数据结构实验四实验报告实验名称：哈弗曼编码姓名：黄州龙 班级：08级软件工程A班 学号：082512102一、 需求分析1、 本实验涉及的算法思想是最优二叉树的构建，而该算法思想的实际应用广泛，哈弗曼编码就是这一算法的应用，通过本实验的练习，可以加深学生对二叉树的理解，学习如何将算法学以致用，并为以后应用中有所突破奠定基础；2、 实验程序是通过用户输入的哈弗曼编码频度表文件（.txt）路径，从硬盘中读取数据，并进一步使用哈弗曼编码算法进行哈弗曼树的构建，最后输出编码结果给用户，也可以选择将哈弗曼树存入文件保存起来；3、 实验程序可以实现对已知频度的码值进行编码的功能，具有一定的使用价值，编写的函数算法是完全可以被用在其他的软件程序中的，具有很好的代码复用性；4、 存储编码频度表的文件的结构：首行是一个正整数N，表示有N个码第二行是N个以空格隔开的字符，即N个码的码值，第三行是N个用空格隔开的非负整数，对应N个码值的频度；5、 测试数据;1、 huffman1.txt文件内容：8A B C D E F G H12 50 52 60 34 80 21 42、 huffman2.txt文件内容：6V P K L Y M20 10 30 40 60 403、 huffman3.txt文件内容：26A B C D E F G H I J K L M N O P Q R S T U V W X Y Z1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 264、 huffman4.txt 文件内容：9I A M Z E P H Y R9 8 7 6 5 4 3 2 1二、 概要设计 1、二叉链结点的定义 struct TreeNodechar data;/数据域，具体应用时可能是别的类型 int visit;/当前的访问状态TreeNode * l;/左树域TreeNode * r;/右树域;/end of definition to TreeNode 2、创建森林和创建哈弗曼树模块 Status createForest(vector &forest,string filename)初始条件：filename所指示的文件路径有效且文件内容符合格 式要求参数：第一个参数传入用来存放每个码结点的地址的向量，第二个参数传入编码频度表文件的路径字符串操作结果:从文件中读取数据并构建出码值二叉森林，为哈弗曼编码算法做准备Status createHuffman(vector &forest)初始条件：传入的码值森林已经初始化参数：第一个参数传入码值森林所初始化的向量操作结果：码值森林只剩一个结点，该结点是哈弗曼树的根结点3、输出哈弗曼编码和输出哈弗曼树模块void printHuffmanCode(TreeNode * root)初始条件：传入的树根结点是有效的树根结点参数：第一个参数传入哈弗曼树的根结点操作结果：输出每个码值对应的哈弗曼编码printTree(TreeNode * tn,int depth)初始条件：传入的二叉树的根是有效的，传入的二叉树深度与二叉树相对应参数：第一个参数传入要进行树形输出的二叉树的根结点 第二个根结点传入二叉树的深度操作结果;将二叉树以树状进行输出，比较直观三、 详细设计1、创建森林和创建哈弗曼树模块 Status createForest(vector &forest,string filename)ifstream is(filename.c_str();/从路径字符串初始化文/件流 coutcodenum;/读取码数 cout有codenum个编码.n; for(int i=0;icode-data; while(code-datadataZ) iscode-data; code-l=NULL; code-r=NULL; forest.push_back(code);/将单结点树加入森林 code=NULL; for(int j=0;jforestj-visit; cout读取完毕.n现在输出内容：n;/提示读取完/毕 is.close();/关闭文件流 for(int k=0;kcodenum;k+) cout编码：data 频度：visitendl; /输出数据以便进行确认 return OK;3、输出哈弗曼编码和输出哈弗曼树模块void printHuffmanCode(TreeNode * root)/该算法以递归方法实现对哈弗曼树的哈弗曼编码进行输出static vector codes;/作为栈来进行使用，回溯地/输出哈弗曼编码if(!root-l&!root-r)/若是叶子结点，将沿根结点至该结点的码值输出即为哈弗/曼编码值int size=codes.size();printf(%c的哈夫曼编码为：,root-data);for(int i=0;il)/若左子非空，则将0压入路径向量codes.push_back(0);printHuffmanCode(root-l);if(root-r)/若右子非空，则将1压入路径向量codes.push_back(1);printHuffmanCode(root-r);if(!codes.empty()codes.pop_back();/弹出当前层的路径void printTree(TreeNode * tn,int depth)/树状输出/.获取层序遍历序列printf(_n);TreeNode * fulltree=NULL;copyTree(tn,fulltree);/将哈弗曼树拷贝至局部树fillTree(fulltree,depth,1);/将局部树填充为满二叉树TreeNode * iter=NULL;int num=1;int *indents=new intdepth+1;/计算满二叉树每层的节/点间间隔数indentsdepth=0;for(int i=depth-1;i0;i-)indentsi=indentsi+1*2+1;queue nds;nds.push(fulltree);for(int i=1;i=depth;i+)/层序遍历满二叉树 for(int j=1;jl) nds.push(iter-l); if(iter-r) nds.push(iter-r); /根据缩进间隔来输出结点数据 for(int k=0;kdata); for(int k=0;k=indentsi;k+) printf( ); num*=2;printf(n); printf(_n);destroyTree(fulltree);/将局部树进行空间释放，防止内/存泄露四、 调试分析1、 哈弗曼编码算法的初始状态应该是每个码都处于独立的状态，因此首先想到的是用数组来存储各个结点的地址，但是在算法进行越到后期的时候会由于大量的结点被合成而导致大量的数组空间空闲，造成内存的浪费，因此改为采用c+标准库文件这个模板类来存放结点，这样在算法执行过程中该模板自己内部可以及时地进行空间回收，解决了空间浪费的问题 ；2、 对文件流的操作完毕后，没有将文件流进行关闭，这在单个的程序中不会暴露出问题，但是当程序有可能多次访问同一个文件的时候会出现严重的访问占用，因此在每个文件流不再访问后，补充代码立即关闭文件流；3、 当构建的哈弗曼树过于广大时，控制台输出的哈弗曼树将会出现显示问题，为了解决这一问题，增加了在输出哈弗曼树之后询问用户是否要将哈弗曼树存入本地文件，以便用户返现显示问题是可以选择将哈弗曼树存入文件中，这样就可以通过在文件中查看哈弗曼树来解决控制台显示上的不足；4、 程序实现的前期只把注意力集中在主要算法和功能的实现，没有对可能产生的异常情况进行具体的考虑，后期则重新审阅代码，捕捉可能出现运行时错误的代码进行异常的捕捉，保证了程序的鲁棒性。这次的后期完善花去了较多的时间，主要问题在于没有在设计出就把异常状况考虑进去，导致问题出现后再来修补花费更多得多的代价，这是一次很宝贵的教训。五、 测试数据1、 huffman1.txt文件内容：8A B C D E F G H12 50 52 60 34 80 21 4测试结果： 2、huffman2.txt文件内容：6V P K L Y M20 10 30 40 60 40测试结果：3、 huffman3.txt文