《数据结构实验四(哈弗曼编码)》由会员分享，可在线阅读，更多相关《数据结构实验四(哈弗曼编码)（16页珍藏版）》请在金锄头文库上搜索。
1、 数据结构实验四实验报告实验名称：哈弗曼编码姓名：黄州龙 班级：08 级软件工程 A 班 学号：082512102一、需求分析1、 本实验涉及的算法思想是最优二叉树的构建，而该算法思想的实际应用广泛，哈弗曼编码就是这一算法的应用，通过本实验的练习，可以加深学生对二叉树的理解，学习如何将算法学以致用，并为以后应用中有所突破奠定基础；2、 实验程序是通过用户输入的哈弗曼编码频度表文件（.txt）路径，从硬盘中读取数据，并进一步使用哈弗曼编码算法进行哈弗曼树的构建，最后输出编码结果给用户，也可以选择将哈弗曼树存入文件保存起来；3、 实验程序可以实现对已知频度的码值进行编码的功能，具有一定的使用价值，
2、编写的函数算法是完全可以被用在其他的软件程序中的，具有很好的代码复用性；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
3、 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 1、二叉链结点的定义、二叉链结点的定义struct TreeNodechar data;/数据域，具体应用时可能是别的类型int visit;/当前的访问状态TreeNode * l;/左树域TreeNode * r;/右树域;/end of definition to TreeNode2、创建森林和
4、创建哈弗曼树模块Status createForest(vector 将二叉树以树状进行输出，比较直观三、详细设计1、创建森林和创建哈弗曼树模块Status createForest(vector /从路径字符串初始化文/件流coutcodenum;/读取码数coutcode-data;while(code-datadataZ)iscode-data;code-l=NULL;code-r=NULL;forest.push_back(code);/将单结点树加入森林code=NULL;for(int j=0;jforestj-visit;coutdatavisit codes;/作为栈来进行使用
5、，回溯地/输出哈弗曼编码if(!root-lprintf(“%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)/树状输出/.获取层序遍历序列print
6、f(“_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;il)nds.push(it
7、er-l);if(iter-r)nds.push(iter-r);/根据缩进间隔来输出结点数据for(int k=0;kdata);for(int k=0;k这个模板类来存放结点，这样在算法执行过程中该模板自己内部可以及时地进行空间回收，解决了空间浪费的问题 ；2、对文件流的操作完毕后，没有将文件流进行关闭，这在单个的程序中不会暴露出问题，但是当程序有可能多次访问同一个文件的时候会出现严重的访问占用，因此在每个文件流不再访问后，补充代码立即关闭文件流；3、当构建的哈弗曼树过于广大时，控制台输出的哈弗曼树将会出现显示问题，为了解决这一问题，增加了在输出哈弗曼树之后询问用户是否要将哈弗曼树存入本地
8、文件，以便用户返现显示问题是可以选择将哈弗曼树存入文件中，这样就可以通过在文件中查看哈弗曼树来解决控制台显示上的不足；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文件内容：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 26测试结果：5、huffman4.txt文件内容：9I A M Z E P H Y R9 8 7 6 5 4 3 2 1
