《北邮数据结构哈夫曼树报告优质内容》由会员分享，可在线阅读，更多相关《北邮数据结构哈夫曼树报告优质内容（12页珍藏版）》请在金锄头文库上搜索。
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=codeu; coutdatai的哈夫曼编码为：; coutHCo
