北邮 数据结构 哈夫曼树报告[优质内容]

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

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

3、ight; /权值int parent; /父节点int lchild; /左孩子int rchild; /右孩子;struct HCode /实现编码的结构类型 char data; /被编码的字符char code100; /字符对应的哈夫曼编码; 2.2 程序流程 输入字符串 统计出现的字符种类和次数，构建权值数组，初始化树结点与编码表根据哈夫曼构建规则构建哈夫曼树，根据编码规则对出现字符进行编码，构建编码表将输入的字符挨个编码对编码后的字符进行解码分析存储大小2.3 关键算法分析 算法1：void Huffman:Count() 1 算法功能：对出现字符的和出现字符的统计，构建权值结点

4、，初始化编码表 2 算法基本思想：对输入字符一个一个的统计，并统计出现次数，构建权值数组， 3 算法空间、时间复杂度分析：空间复杂度O（1），要遍历一遍字符串，时间复杂度O（n） 4 代码逻辑： leaf=0; /初始化叶子节点个数 int i,j=0; int s128=0; 用于存储出现的字符 for(i=0;stri!=0;i+) 遍历输入的字符串 s(int)stri+; 统计每个字符出现次数 for(i=0;i128;i+) if(si!=0) dataj=(char)i; 给编码表的字符赋值 weightj=si; 构建权值数组 j+; leaf=j; /叶子节点个数即字符个数 f

5、or(i=0;ileaf;i+) coutdatai的权值为：weightiendl; 算法2：void Init(); 1 算法功能：构建哈弗曼树 2 算法基本思想：根据哈夫曼树构建要求，选取权值最小的两个结点结合，新结点加入数组，再继续选取最小的两个结点继续构建。 3 算法空间、时间复杂度分析：取决于叶子节点个数，时间复杂度O（n），空间复杂度O（1） 4 代码逻辑HTree=new HNode2*leaf-1; n2=n0-1，一共需要2n-1个结点空间 for(int i=0;ileaf;i+) HTreei.weight=weighti; 给每个结点附权值 HTreei.lchild

6、=-1; 初始化左右孩子和父节点，都为-1 HTreei.rchild=-1; HTreei.parent=-1; int x,y; /用于记录两个最小权值 for(int i=leaf;i2*leaf-1;i+) Selectmin(HTree,i,x,y); 选出两个最小权值的结点 HTreex.parent=i; 父节点设置为新建立的结点 HTreey.parent=i; HTreei.weight=HTreex.weight+HTreey.weight; 父节点权值为两个相加 HTreei.lchild=x; 使父节点指向这两个孩子结点 HTreei.rchild=y; HTreei.

7、parent=-1; 父节点的父节点设为-1 算法3：void Selectmin(HNode*hTree,int n,int&i1,int &i2); 1 算法功能：从现有的结点中选择出两个最小的结点，返回其位置 2 算法基本思想：先选出两个没有构建的结点，然后向后依次比较，筛选出最小的两个结点 3 算法空间、时间复杂度分析：空间复杂度O(1)，要遍历所有结点，时间复 杂度O(N) 4 代码逻辑int i;for(i=0;in;i+) /n为现在有的结点个数，是个变化值,会有相加后的新权值加入 if(hTreei.parent=-1) /父节点不是-1意味着这个结点还没有被选择过i1=i;

8、记录结点位置break; i+; /执行一遍for循环就加1，意为下次查找从当前位置开始查找for(;ihTreei2.weight) 进行比较，使I1为最小的，I2为第二小的int j=0;j=i2;i2=i1;i1=j; i+;for(;in;i+) 将I1 I2 与后面的结点进行比较if(hTreei.parent=-1&hTreei.weighthTreei1.weight) 如果结点小于I1i2=i1; 使I2=I1 I1=新结点i1=i; else if(hTreei.parent=-1&hTreei.weighthTreei2.weight) I1新结点I2，使I2为新节点i2=

9、i; 算法4：void CreateTable(); 1 算法功能：对出现的字符进行编码 2 算法基本思想：根据字符在哈夫曼树中的位置，从下到上编码，是左孩子编0，右孩子编1 3 算法空间、时间复杂度分析：空间复杂度O(1)，要遍历data数组，时间复杂度0(N) 4 代码逻辑HCodeTable=new HCodeleaf; 新建编码结点，个数为叶子节点个数 for(int i=0;ileaf;i+) HCodeTablei.data=datai; int child=i; 初始化要编码的结点的位置 int parent=HTreei.parent; 初始化父结点 int k=0; /统计编

10、码个数 while(parent!=-1) if(child=HTreeparent.lchild) HCodeTablei.codek=0; /左孩子标0 else HCodeTablei.codek=1; /右孩子标1 k+; child=parent; 孩子结点上移 parent=HTreechild.parent; 父节点也上移 HCodeTablei.codek=0; /将编码反向 char code100; for(int u=0;uk;u+) codeu=HCodeTablei.codek-u-1; for(int u=0;uk;u+) HCodeTablei.codeu=cod

11、eu; coutdatai的哈夫曼编码为：; coutHCodeTablei.codeendl; length3i=k; /每一个字符编码的长度，为求编码总长度做准备 算法5：void Encoding(); 1 算法功能：对输入的字符串进行编码 2 算法基本思想：找到每个字符对应的编码，将编码按顺序输出 3 算法空间、时间复杂度分析：空间复杂度O(1),时间复杂度0（n） 4 代码逻辑 coutendl输入的字符串转化为哈夫曼编码为:endl; for (int i=0;stri!=0;i+) 遍历输入的每一个字符 for(int j=0;jleaf;j+) if(stri=HCodeTab

12、lej.data) 找到字符对应的编码 s1=s1+HCodeTablej.code; 将所有编码按顺序加起来 coutHCodeTablej.code; 输出编码 coutendl;算法6：void Decoding(); 1 算法功能：对编码串进行解码 2 算法基本思想：找到每段编码对应的字符，输出字符 3 算法空间、时间复杂度分析：时间复杂度0(N)，空间复杂度0（1） 4 代码逻辑（可用伪代码描述） cout解码后的字符串为: endl; char *s = const_cast(s1.c_str(); 将编码字符串转化为char while(*s!=0) int parent=2*l

13、eaf-2; 父节点为最后一个节点 while(HTreeparent.lchild!=-1) /还有左子树，不可能是叶子节点 if(*s=0) 编码为0，为左孩子 parent=HTreeparent.lchild; else parent=HTreeparent.rchild; 编码为1，为右孩子 s+; coutHCodeTableparent.data; 输出字符 coutendl; 注意分析程序的时间复杂度、内存申请和释放，以及算法思想的体现。2.4 其他在此次试验中使用了类和STL中的string，使用string可以方便的将单个字符的编码加起来成为总的编码后的数值，再利用STL中的转化函数可以直接将string转化为char，方便进行解码工作。总而言之，使用STL使得编码大大的简洁了。3. 程序运行结果分析调试过程中遇到的问题主要是执行时有内存错误，检查后发现是数组有越界现象，这提醒我在编写时一定要仔细，特别是在for循环条件上一定要注意范围 总结4.1实验的难点和关键点 首先在输入字符串时我发现直接用cin无法输入空格，在上网查询后找到了getline函数解决了这个问题。然后还有就是如何存储编码后总的那个字符串，因为每一个字符编码的长度不定，无