北邮哈夫曼树实验报告.doc

《北邮哈夫曼树实验报告.doc》由会员分享，可在线阅读，更多相关《北邮哈夫曼树实验报告.doc（8页珍藏版）》请在淘文阁 - 分享文档赚钱的网站上搜索。

1、数据结构实验报告实验名称： 实验三树学生姓名：班 级： 2011211114班内序号： 14学 号： 2011210400日 期： 2012 年11 月29 日1实验要求（1） 实验目的 掌握二叉树基本操作的实现方法 了解赫夫曼树的思想和相关概念 学习使用二叉树解决实际问题的能力（2） 实验内容利用二叉树结构实现赫夫曼编/解码器。基本要求：1、 初始化(Init)：能够对输入的任意长度的字符串 s 进行统计，统计每个字符的频度，并建立赫夫曼树2、 建立编码表(CreateTable)：利用已经建好的赫夫曼树进行编码，并将每个字符的编码输出。3、 编码(Encoding)：根据编码表对输入的字符

2、串进行编码，并将编码后的字符串输出。4、 译码(Decoding)：利用已经建好的赫夫曼树对编码后的字符串进行译码，并输出译码结果。5、 打印(Print)：以直观的方式打印赫夫曼树（选作）6、 计算输入的字符串编码前和编码后的长度，并进行分析，讨论赫夫曼编码的压缩效果。测试数据：I love data Structure, I love Computer。I will try my best to study dataStructure.2. 程序分析2.1 存储结构该程序使用哈夫曼树结构存储数据，并利用哈夫曼树进行编码得到每个字符的编码从而第1页减少数据的存储空间，哈夫曼树是二叉树，以各频

3、度作为叶子结点组成哈夫曼树，而每个结点存储的有其频度，其双亲结点，其左孩子和右孩子，并且哈夫曼树有一个相应的编码表存储各叶子结点的编码。哈夫曼树的存储结构如图： D EBA C2.2 关键算法分析1关键算法哈夫曼树解码和译码问题的实质就是把已知的一段字符串，统计每个字符的频度，并按照频度建立哈夫曼树，每个叶子结点都为一个频度，然后利用建好的哈夫曼树建立编码表，从而得到每个字符的编码，这样每输入一段字符都可以去编码表找对应的字符从而编码成一段二进制码，这样的编码存储更节省存储空间，从而达到压缩效果。关键算法如下：1：把输入的一段字符串转化为每个字符的频度，并对应一个字符数组存储字符： 利用 AS

4、CII 码有 128 个并对应着的整形，用一个整形数组存储每个字符出现的次数，数组的下标为每个字符的 ASCII 码对应整数。 用赋好值的整形数组每个元素除以总的元素并对应存入一个 double 类型的数组（元素为 0 的不存），并建立一个字符数组存储每个字符对应 double 数组的每一个元素（频度）。2：利用建好的 double 数组建立哈夫曼树：建立一个含 2*k-1 个结点的树，并把 k 个频度对应存入 0-k-1 个结点的 weight 域，并令这些结点的左孩子，右孩子，和双亲都为-1。找出 0k-1 个结点频度最小的两个结点，并令第 k 个结点的频度等于两节点频度之和，一个结点为其

5、左孩子，一个结点为其右孩子。循环步骤 2，使建好的树每个结点的域都填充好（每次比较除去已经提取出来的结点，并加入新建好的结点）。3：利用建好的哈夫曼树建立编码表:编码表 data 域存字符，code 域存每个字符的编码。找到叶子结点的双亲，判断如果该结点是双亲的左孩子则存编码0，右孩子存编码 1，然后再找其双亲的双亲，判断双亲是祖父结点的左孩子还是右孩子，重复上述步骤直到根结点。第2页把每个字符的编码倒置并输出每个字符的编码。4：译码函数: 如果是第一个字符是 0 则找根结点的左孩子，如果是 1 则找右孩子。 继续令找到的结点作为双亲并找下一个字符重复步骤（1）（2）直到叶子结点。 重复(1)

6、(2)直到遍历字符数组。5：编码函数： 把字符数组的第一个字符与叶子结点的字符比较，找到相同的字符，把其编码并入一个字符数组存储起来。 字符下标加 1，重复步骤（1）直到遍历整个字符数组。2. 代码详细分析:（1）把输入的一段字符串转化为每个字符的频度，并对应一个字符数组存储字符：利用 ASCII 码有 128 个并对应着的整形，用一个整形数组存储每个字符出现的次数，数组的下标为每个字符的 ASCII 码对应整数;while(pi)api+;i+;用赋好值的整形数组每个元素除以总的元素并对应存入一个 double 类型的数组（元素为 0 的不存），并建立一个字符数组存储每个字符对应 doubl

7、e 数组的每一个元素（频度）：for(int j=0;j128;j+)if(aj)bk=(double)aj/i;ck=(char)j;k+;(2) 利用建好的 double 数组建立哈夫曼树建立一个含2*k-1个结点的树，并把k个频度对应存入0-k-1个结点的weight域，并令这些结点的左孩子，右孩子，和双亲都为-1：for(int j=0;jk;j+)HTreej.weight=bj;HTreej.LChild=-1;HTreej.RChild=-1;HTreej.parent=-1;找出0k-1个结点频度最小的两个结点，并令第k个结点的频度等于两节点频度之和，第3页一个结点为其左孩子，

8、一个结点为其右孩子：for(int j=k;j2*k-1;j+)double min1=1000,min2=1000;int x=-1,y=-1;for(int p=0;p=j-1;p+)if(HTreep.parent=-1)if(HTreep.weightmin1) min2=min1;y=x;min1=HTreep.weight;x=p;else if(HTreep.weightmin2) ymin2=HTreep.weight;y=p;（3）译码函数:如果是第一个字符是0则找根结点的左孩子，如果是1则找右孩子：while(HTreeparent.LChild!=-1)if(si=0)p

9、arent=HTreeparent.LChild;elseparent=HTreeparent.RChild;i+;(4) 编码函数：输把字符数组的第一个字符与叶子结点的字符比较，找到相同的字符，把其编码并入一个字符数组存储起来;while(si)for(int j=0;jn;j+)if(si=HCodeTablej.data) strcat(h,HCodeTablej.code);i+;3时间复杂度的计算1 O(n)第4页1.1 O(n)2.1 O(n)2.2 O(n)2.3 O(n)3.1 O(1)3.2 O(n)3.3 O(n)4.1 O(n)4.2 O(n)5.1 O(n) 2.3 其

10、他在此需要说明的是，这里编码函数和译码函数都是在输入字符串建立的编码表基础上调用的，不能另外输入字符串调用其函数。3. 程序运行结果1流程流程图如下：开始用 cin.getline()函数接受一段可含空格的字符串。调用菜单函数，实参为输入的字符串。对字符串进行处理，用 double类型数组 b存频度，用字符数组 c存对应字符。调用哈夫曼树建立函数，实参为数组 b和数组中总频度数 k。调用编码表初始化函数，实参为 c和 k。第5页用 户 输 入 整 形n，判断 n 大小n=3n=1 n=2调用编码函数，实参为数 调用译码函数， 调用计算数组大小函数，组 c和 k，输出编码。 输出译码。 然后输入

11、压缩效果结束2. 测试结论：第6页4. 总结（1）调试时出现的问题及解决方法第7页在调试时发现用字符指针不能用 cin 输入字符串，后来把字符指针改为字符数组后问题得到解决。在执行时发现输出编码时后面总有一段乱码，在给字符数组赋值的地方设置断点调试后发现字符数组没初始化时为乱码，后来把字符数组初始化后问题得到解决。（2）心得体会在本次实验中，熟悉了哈夫曼树的各种基本操作，特别是初始化哈夫曼树操作、建立编码表操作和编码队头和译码操作有了较深的理解。对于数组和指针的用法也更熟练，在程序的调试和异常处理方面有了一定的经验。相信在本次实验中积累的经验、提高的能力将在今后的实验中展现出来。尤其在函数嵌套调用方面有了很大的提高，熟悉了嵌套使用条件，使自己的逻辑思维有了很大的提高。（3）下一步的改进程序有的代码不够简洁，而且有的地方时间复杂度太大，例如在对字符串进行处理的地方，利用了两个循环才把频度和字符存储好。希望能找到更简洁的方法可以使时间复杂度减少，从而使程序改进。第8页