北邮数据结构哈夫曼树报告优质内容.doc
13页
数 据 结 构实验报告实验名称：哈夫曼树学生姓名：袁普班 级：2013211125班班内序号：14号学 号：2013210681日 期：2014年12月1. 实验目的和内容利用二叉树结构实现哈夫曼编/解码器基本要求：1、 初始化(Init)：能够对输入的任意长度的字符串 s进行统计，统计每个字符的频度，并建立哈夫曼树2、 建立编码表(CreateTable)：利用已经建好的哈夫曼树进行编码，并将每个字符的编码输出3、 编码(Encoding)：根据编码表对输入的字符串进行编码，并将编码后的字符串输出4、 译码(Decoding)：利用已经建好的哈夫曼树对编码后的字符串进行译码，并输出译码结果5、 打印(Print)：以直观的方式打印哈夫曼树（选作）6、 计算输入的字符串编码前和编码后的长度，并进行分析，讨论赫夫曼编码的压缩效果7、 可采用二进制编码方式（选作）测试数据：I love data Structure, I love ComputerI will try my best to study data Structure.提示：1、用户界面可以设计为“菜单”方式：能够进行交互。
2、根据输入的字符串中每个字符出现的次数统计频度，对没有出现的字符一律不用编码2. 程序分析2.1 存储结构用struct结构类型来实现存储树的结点类型struct HNode { int weight; //权值 int parent; //父节点 int lchild; //左孩子 int rchild; //右孩子};struct HCode //实现编码的结构类型{ char data; //被编码的字符 char code[100]; //字符对应的哈夫曼编码}; 2.2 程序流程 输入字符串 统计出现的字符种类和次数，构建权值数组，初始化树结点与编码表根据哈夫曼构建规则构建哈夫曼树，根据编码规则对出现字符进行编码，构建编码表将输入的字符挨个编码对编码后的字符进行解码分析存储大小2.3 关键算法分析 算法1：void Huffman::Count() [1] 算法功能：对出现字符的和出现字符的统计，构建权值结点，初始化编码表 [2] 算法基本思想：对输入字符一个一个的统计，并统计出现次数，构建权值数组， [3] 算法空间、时间复杂度分析：空间复杂度O（1），要遍历一遍字符串，时间复杂度O（n） [4] 代码逻辑： leaf=0; //初始化叶子节点个数 int i,j=0; int s[128]={0}; 用于存储出现的字符 for(i=0;str[i]!='\0';i++) 遍历输入的字符串 s[(int)str[i]]++; 统计每个字符出现次数 for(i=0;i<128;i++) if(s[i]!=0) { data[j]=(char)i; 给编码表的字符赋值 weight[j]=s[i]; 构建权值数组 j++; } leaf=j; //叶子节点个数即字符个数 for(i=0;i [3] 算法空间、时间复杂度分析：取决于叶子节点个数，时间复杂度O（n），空间复杂度O（1） [4] 代码逻辑HTree=new HNode[2*leaf-1]; n2=n0-1，一共需要2n-1个结点空间 for(int i=0;i
