北邮数据结构哈夫曼树报告

1、数据结构实验报告实验名称：哈夫曼树学生姓名：袁普班级：25 班班内序号： 14 号学号：81日期：2014 年12 月1. 实验目的和内容利用二叉树结构实现哈夫曼编 / 解码器。基本要求：1、初始化(Init):能够对输入的任意长度的字符用s进行统计，统计每个字符的频度，并建立哈夫曼树2、建立编码表(CreateTable)利用已经建好的哈夫曼树进行编码，并将每个 字符的编码输出。3、编码(Encoding):根据编码表对输入的字符串进行编码，并将编码后的字 符串输出。4、译码(Decoding):利用已经建好的哈夫曼树对编码后的字符串进行译码， 并输出译码结果。5、打印(Print):以直观

2、的方式打印哈夫曼树(选作)6 、 计算输入的字符串编码前和编码后的长度，并进行分析，讨论赫夫曼编码的压缩效果。7 、 可采用二进制编码方式(选作)测试数据：I love data Structure, I love Computer。 I will try my best to study data Structure.提示：1 、用户界面可以设计为“菜单”方式：能够进行交互。2 、 根据输入的字符串中每个字符出现的次数统计频度， 对没有出现的字符一律不用编码2. 程序分析存储结构用 struct 结构类型来实现存储树的结点类型struct HNodeint weight;eigh=W

3、4;ghti;HT闸给每个结点附权值初始化左右孩子和父节点，都为 -1HTre®阳独树结点与编码表int x,y;arent=i;父节点设置为新建立HTreei.parent=-1;的结点HTreey.parent=i;父节点权值为两个相HTreei.weight=HTreex.weight+HTreey.weight;HTreei.lchild=x;使父节点指向这两个孩子结点HTreei.rchild=y;HTreei.parent=-1;父节点的父节点设为 -1算法 3: void Selectmin(HNode*hTree,int n,int&i1,int &i

4、2);1算法功能：从现有的结点中选择出两个最小的结点，返回其位置2算法基本思想：先选出两个没有构建的结点，然后向后依次比较，筛选出最小的两个结点3算法空间、时间复杂度分析：空间复杂度 O(1),要遍历所有结点，时间复 杂度 O(N)4代码逻辑int i;for(i=0;i<n;i+)arent=-1) arent=-1)i2=i;记录第二个没选择过的结点编号break;if(hTreei1.weight>hTreei2.weight) 进行比较，使I1 为最小的， I2 为第二小的int j=0;j=i2;i2=i1;i1=j; i+;for(;i<n;i+)将 I1 I2

5、与后面的结点进行比较if(hTreei.parent=-1&&hTreei.weight<hTreei1.weight) 如果结点小于I1 i2=i1;使 I2=I1I1=新结点i1=i; else if(hTreei.parent=-1&&hTreei.weight<hTreei2.weight)I1新结点I2,使I2为新节点i2=i; 算法 4： void CreateTable();1 算法功能：对出现的字符进行编码2 算法基本思想： 根据字符在哈夫曼树中的位置， 从下到上编码， 是左孩子编0，右孩子编 13算法空间、时间复杂度分析：空间复杂度

6、0(1),要遍历data数组，时间复杂度 0(N)新建编码结点，个数为叶子节点个数4 代码逻辑HCodeTable=new HCodeleaf;for(int i=0;i<leaf;i+)HCodeTablei.data=datai;int child=i;初始化要编码的结点的位置int parent=HTreei.parent;初始化父结点int k=0;child)HCodeTablei.codek='0' odek='1'节点也上移arent;父HCodeTablei.codek='0'for(int u=0;u<k;u+)HC

7、odeTablei.codeu=codeu;cout<<datai<<" 的哈夫曼编码为： "cout<<HCodeTablei.code<<endl;length3i=k;的编码 s1=s1+HCodeTablej.code;cout<<HCodeTablej.code;odek-u-1;ata)找到字符对应将所有编码按顺序加起来输出编码cout<<endl;算法 6： void Decoding();1 算法功能：对编码串进行解码2 算法基本思想：找到每段编码对应的字符，输出字符3算法空间、时间复杂

8、度分析：时间复杂度0(N),空间复杂度0 (1)4 代码逻辑(可用伪代码描述)cout<<" 解码后的字符串为 : "<<endl;char *s = const_cast<char*>();将编码字符串转化为charwhile(*s!='0')int parent=2*leaf-2;父节点为最后一个节点while(HTreeparent.lchild!=-1)child;elseparent=HTreeparent.rchild; 编码为 1，为右孩子 s+; cout<<HCodeTableparent.d

9、ata; 输出字符cout<<endl;注意分析程序的时间复杂度、内存申请和释放，以及算法思想的体现。其他在此次试验中使用了类和STL中的string,使用string可以方便的将单个字符的编码加起来成为总的编码后的数值，再利用 STL 中的转化函数可以直接将string 转化为char,方便进行解码工作。总而言之，使用STL使得编码大大的简洁了。3. 程序运行结果分析调试过程中遇到的问题主要是执行时有内存错误， 检查后发现是数组有越界现象，这提醒我在编写时一定要仔细，特别是在 for 循环条件上一定要注意范围C :Wi n d owssyste m 32cmd .exe清湎人一段

10、字将串，柠回三遍结束;沙狗物者输入法学;C:Windowssystem32cmd.exe011UB10001VUlVTLVi 011110H1011011011011 Q1Q001010111Gil SOSsiiioe 001B mom 0Q11S31工& 213 ?巾一4F ri 马 马 nprrprrTTiTTiTTrprrmTTiprrprrp-zrT年.也一le三口 一口 T 一0 一q 一口一巾一电编编编编编编拐编编编编编编编编编编T 为为为为昙昊u K曼e昙曼曼OWUL戛曼0WHL悬曼 isw夫夫夫大夫夫夫夫夫夫夫夫夫夫夫夫 哈哈哈皓哈哈哈哈，雷目后富哈哈哈陌 n” Jl

11、1¥/1" l"!h“l3-卜3e 研/-|" 5 - - - ptL- .L .E tL -E t .E- tL-.E .匚,E -211-tk, -£tl-J二r1 J二七二出二 a -qrwCWindoi/vAsysterTi 32crnd.exe人为字符串转化为哈夫曼编码为:用码后的字符串为，lave data £t jmjlc t uiro, I Lou a Computefl uill t i»w my Jbest to stud u data £ti?uc tm'e需49绯?it t bB 133 38 : .，为 1Z 曼曼曼曼曼昙具 天夫夫夫夫夫夫 哈哈哈哈哈哈哈IM TR 口 6 1 6 石工 11011总结实验的难点和关键点首先在输入字符串时我发现直接用cin无法输入空格，在上网查询后找到了getline函数解决了这个问题。然后还有就是如何存储编码后总的那个字符串，因为每一个字符编码的长度不定，无法用 char数组来存储，于是用了string的相加函数来将所有