综合训练 利用哈夫曼树进行编码与解码.docVIP

《数据结构》 综 合 训 练 报 告 题 目 利用哈夫曼树进行编码与解码 班 级 理科13—1 姓 名 李全鹏 时 间 2014 年 12 月 7 日 利用哈夫曼树进行编码与解码 一、目的和要求：使学生理解哈夫曼树的概念、掌握哈夫曼树的建立以及利用利用哈夫曼树进行哈夫曼编码的算法思想。要求： 1、使用文件流方式。 2、要求提供编码和解码两种方式 3、能够打开input.txt文件，统计其中字符出现的频率，并以此进行哈夫曼编码，并将编码后的结果输出到output.txt文件中。 4、能够根据3中得到的字符编码，将output.txt文件中的码文进行解码，并将解码后的结果输出到input.txt文件中。 二、概要设计：。 该程序共有五个模块组成：1. 统计字母种类和个数模块2. 哈弗曼树的建立模块3. 建立哈夫曼编码的功能模块4. 密文的输出模块。5.将密文转化为原文模块。各模块之间无直接调用关系，但模块三和模块五调用了模块二的结果，模块二、三、四都调用了模块一的结果。 （1）统计字母种类和个数模块 此模块的功能是统计出字符串S中出现的字符info[i].ch，以及该字符的个数info[i].num。该模块先把S的第一个字符存放在info[0].ch中，并将info[0].num置为1。然后进行v次循环，每第k次循环将字符S[k]分别于info结构体中的info[i].ch元素进行对比，若相等，则info[i].num+1,否则的话在info中新增加一个元素，将num元素置为1。 （2）哈弗曼树的建立模块 1、该模块首先建立n棵二叉树的森林并赋值。2、然后在森林中选出两棵根节点的权值最小的树作为一棵新树的左右子树，最小的作为左子树，次小的作为右子树，且置新树的根节点的权值为其左右子树上根节点的权值之和。3、然后从森林中删除构成新树的那两棵树，同时把新树加入森林中。重复二、三步骤知道最后剩下一棵树为止。 (3) 建立哈夫曼编码的功能模块 该模块运用了递归的思想，将该二叉树中每个分枝结点的左、右分支分别用0和1编码，从树根结点到每个叶子节点的路径上所经分支的0、1编码序列等于该叶子节点的二进制编码 (4)密文的输出模块。 对S中的每个字符，在info结构体数组中寻找与之对应的字符info[j].ch,然后输出info[j]中保存的二进制编码info[j].a (5) 将密文转化为原文模块 该模块将树根节点的指针赋给BTreeNode类型的指针p,对二进制编码数组code依次检索，若为0，则将指针p赋值为p-left,否则赋值为p-right,然后判断是否到达了叶子节点，若到达叶子节点，则输出叶子节点里存储的字符，重新将指针p赋值为树根节点，接着进行下去；若没有到达，则继续往下进行，知道全部遍历了code中的元素。 四、算法描述：给出各模块流程图，不要附源代码，可以对重点函数及结构进行说明。 （1）统计字母种类和个数模块 N Y Y Y N （2）哈弗曼树的建立模块(k1初始指向森林中第一棵树，k2初始指向森林中第二棵树) Y N Y Y N Y Y N ……. (3) 建立哈夫曼编码的功能模块 Y N Y …… (4) 密文的输出模块。 N Y Y N Y （5）将密文转化为原文模块（num为code数组中元素的个数） N Y N Y N Y 五、测试结果及分析： 测试数据： 在input.txt文本中输入数据 运行程序得： 密文为： 再次将密文解密得 时间复杂度：模块一的时间复杂度为n(字符总个数)*v（字符的种类）；模块二的时间复杂度为n*n；模块三的时间复杂度为2（n-1）*n； 模块四的时间复杂度为v* n*；模块五的时间复杂度为num(0、1代码的长度) 调试时遇到的问题： 1.当S字符长度较短时运行没问题，然而较长时运行错误，不能将密文再次转化为原文。问题解决：code[]数组定义的长度为1000，本以为已经足够长了，其实不然，当字符种类较多时候，每个字符的编码长度会很长，因此超出了code[]数组的范围而出错，在将code[]数组长度改为2000时，问题便得到了解决。 2.在模块四将0、1代码转化为原文时，不能判断到达的叶子节点处的字符，因而不能输出。问题解决：在定义BTreeNode是增加了一个int zifu;变量，用于保存字符，从而便可输出叶子节点处的字