实验三哈夫曼树实验报告.doc

数据结构实验报告实验名称：实验三 树学生姓名：班级：班内序号：学号：日期：2012年12月7号1、 实验要求利用二叉树结构实现赫夫曼编/解码器。基本要求：1、 初始化(Init)：能够对输入的任意长度的字符串s进行统计，统计每个字符的频度，并建立赫夫曼树2、 建立编码表(CreateTable)：利用已经建好的赫夫曼树进行编码，并将每个字符的编码输出。3、 编码(Encoding)：根据编码表对输入的字符串进行编码，并将编码后的字符串输出。4、 译码(Decoding)：利用已经建好的赫夫曼树对编码后的字符串进行译码，并输出译码结果。5、 打印(Print)：以直观的方式打印赫夫曼树（选作）6、 计算输入的字符串编码前和编码后的长度，并进行分析，讨论赫夫曼编码的压缩效果。测试数据： I love data Structure, I love Computer。I will try my best to study data Structure. 提示： 1、用户界面可以设计为“菜单”方式：能够进行交互。 2、根据输入的字符串中每个字符出现的次数统计频度，对没有出现的字符一律不用编码。2、 程序分析2.1存储结构（1）二叉树template class BiTreepublic: BiTree(); /构造函数，其前序序列由键盘输入 BiTree(void); /析构函数 BiNode* Getroot(); /获得指向根结点的指针protected: BiNode *root;/指向根结点的头指针;/声明类BiTree及定义结构BiNodeData： 二叉树是由一个根结点和两棵互不相交的左右子树构成。 二叉树中的结点具有相同数据类型及层次关系。示意图： root lchild parent rchild （2）静态三叉链表struct HNode /哈夫曼树的静态三叉链表 unsigned int weight; /结点权值 unsigned int parent; /双亲指针 unsigned int Lchild; /左孩子指针 unsigned int Rchild; /右孩子指针;示意图： parent Rchild Lchild data(3) 编码表的节点结构struct HCode /字符及其编码结构 char data; char code100;示意图：char code100char data2.2关键算法分析一：关键算法 (一)初始化函数 void Huffman:Init(int a,int n)（1）算法自然语言1. 创建一个长度为2*n -1的三叉链表2. 将存储字符及其权值的链表中的字符逐个写入三叉链表的前n个结点的data域，并将对应结点的孩子域和双亲域赋为空3. 从三叉链表的第n个结点开始，i=n3.1 从存储字符及其权值的链表中取出两个权值最小的结点x,y，记录其下标x,y。3.2 将下标为x和y的哈夫曼树的结点的双亲设置为第i个结点3.3 将下标为x的结点设置为i结点的左孩子，将下标为y的结点设置为i结点的右孩子，i结点的权值为x结点的权值加上y结点的权值，i结点的双亲设置为空4. 根据哈夫曼树创建编码表（2）源代码void Huffman:Init(int a,int n) /创建哈夫曼树 /二叉树只有度为和度为的结点时，总结点数为（n-1）个 HTree=new HNode2*n-1; /根据权重数组a1n初始化哈夫曼树 int i,x,y; for(i=0;in;i+) /n个叶子结点 HTreei.weight=ai; HTreei.Lchild=-1; HTreei.Rchild=-1; HTreei.parent=-1; for(int i=n;i2*n-1;i+) /开始建哈夫曼树，从底层向顶层搭建 SelectMin(HTree,i,x,y); /从-(i-1)中选出两个权值最小的结点 HTreex.parent=i; HTreey.parent=i; /左右孩子权值相加为父结点的权值 HTreei.weight=HTreex.weight+HTreey.weight; HTreei.Lchild=x; HTreei.Rchild=y; HTreei.parent=-1; (3)时间复杂度在选取两个权值最小的结点的函数中要遍历链表，时间复杂度为O(n),故该函数的时间复杂度为O（n2）（二）统计字符出现频度的代码（1）算法自然语言用cin.getline（）函数获取一段字符串。同时设置一个权值数组weight，以及暂时统计和存放权值的数组s。用 strlen（）函数获取未编码时的字符串长度。从字符串的起始位置进行权值统计，即获得stri每个字符的AS编码，并在s(int)stri数组中进行+1统计，为字符出现一次。 i进行自加，统计下面字符出现的频度，在相应的数组元素中进行+1统计。继续循环，直到字符串结束。（2）源代码（在main（）函数中实现）int i,j=0,v; int s200=0; int weightM; /权值数组 cout请输入一段字符串，按回车键结束：endl; cin.getline(str,1000,n); /由用户输入一段字符串 coutendl; Len1=strlen(str); /得到未编码时的字符串长度 for(i=0;stri!=0;i+) /统计每个字符的权值 s(int)stri+; /(int)stri为每个字符的AS编码 for(i=0;i200;i+) if(si!=0) /如果权值不为 cj=i; /AS编码为i的字符写入字符数组c weightj=si; /权值s数组赋给权值weight数组 j+; n=j; /叶子结点个数 for(v=0;vn;v+) /循环输出字符权值 coutcv的权值为：weightvendl;(3) 时间复杂度： 若输入的字符串长度为n，则时间复杂度为O(n)（三）选择两个最小权值的函数（1）算法自然语言先暂时将前两个叶子结点作为权值最小的两个结点i1，i2从第三个叶子结点开始，每一个结点的权值与i1，i2进行比较，如果此结点权值比i1权值要小，则将i1结点赋给i2，此结点赋给i1。如果此结点权值比i2要小，此结点赋给i2。每进行一次循环，总结点个数1.（两个结点进行权值合并）继续执行循环，直到循环到根结点，循环结束。（2）源代码void Huffman:SelectMin(HNode*hTree,int n,int &i1,int &i2) int i,j; /找一个比较的起始值 for(i=0;in;i+) /找i1 if(hTreei.parent=-1) i1=i; break; i+; for(;ihTreei2.weight) /i1指向最小的 j=i2; i2=i1; i1=j; i+; for(;in;i+) /开始找最小的两个 if(hTreei.parent=-1&hTreei.weighthTreei1.weight) /如果之后的叶子结点权值小于前两个，那么进行交换 i2=i1; /把i1赋给i2 i1=i; else if(hTreei.parent=-1&hTreei.weighthTreei2.weight) i2=i; /始终保证i2权值大于i1 （3）时间复杂度若输入的字符串长度为n，则时间复杂度为O(n)（四）创建编码表（1）算法自然语言1.生成一个编码表2.从终端结点开始，如果此结点是其父结点的左孩子，则标“0”；如果是其父结点的右孩子，则标“1”。3.将父结点赋给孩子结点，并将新的孩子结点的父结点作为当前父结点，重复2操作。4.继续循环，直到根结点，即不满足循环条件时，将编码表的最后一位置0.5.将编码字符逆置。将编码串的最后一位置换成新编码串的第一位，倒数第二位置换成新编码串的第二位，直到置换完毕。6.将新的编码串重新赋给编码表。7.输出字符的哈夫曼编码。8.循环将字符编码后的长度赋给Len3数组。（2）源代码void Huffman:CreateTable(char data,int n) HCodeTable=new HCoden; /生成编码表 for(int i=0;in;i+) HCodeTablei.data=datai; int child=i; int parent=HTreei.parent; int k=0; /从终端结点开始编码，代表每个编码串的长度 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 codeM; int u; for(u=0;uk;u+) codeu=HCodeTablei.codek-u-1;/上述编码串的最后一位变成新的编码表中编码串的第一位 for(u=0;uk;u+) HCodeTablei.codeu=codeu; /将新的编码串重新赋给编码表 coutci的哈夫曼编码为：; coutHCodeTablei.codeendl; Len3i=k; /每个字符编码后的长度 （3）时间复杂度若输入的字符串长度为n，则时间复杂度为O(n)。（五）编码算法（1）算法自然语言1.从字符串的起始位置开始，将每个字符与编码表中的字符进行比对。2.当两字符相等时，输出编码表中字符对应的编码。3.将此字符编码的长度加到Len2中，循环结束后，Len2的数值为字符串编码后的总长度。（2）源代码void Huffman:Encoding(int n) /编码 coutendl输入的字符串转化为哈夫曼编码为:endl; for (int i=0;stri!=0;i+) /只要字符串不结束就执行循环 for(int j=0;jn;j+) if(stri=HCodeTablej.data) /如果字符串中的字符与编码表中的字符相等 coutHCodeTablej.code; /输出编码表中字符对应的编码 Len2+=Len3j; /求编码后的字符总的编码长度，为了求压缩比 coutendl;（3）时间复杂度 设待编码字符串长度为n，编码表中字符个数为m，则复杂度为O（n*m）。（六）解码算法（1）算法自然语言1.从根节点开始，如果编码串为0，则下溯到此结点的左孩子结点；如果编码串为1，则下溯到此结点的右孩子结点。2.执行循环，直到不满足while循环条件，即追溯到叶子结点。输出叶子结点的字符。（2）源代码void Huffman:Decoding(char* p) /p为编码串 cout解码后的字符串为: endl; char* q=0; while(*p!=0) int parent=2*n-1-1; /根结点在哈夫曼树中的下标 while(HTreeparent.Lchild!=-1) /如果不是叶子结点就执行循环 if(*p=0) parent=HTreeparent.Lchild; else if(*p=1) parent=HTreeparent.Rchild; p+; coutHCodeTableparent.data; /输出叶子结点的字符 coutendlendl;（3）时间复杂度若输入的字符串长度为n，则时间复杂度为O(n)。（七）计算压缩比函数（1）算法自然语言1. 获得编码前字符串的长度，即其占用的字节数（float类型）。2. 获得编码后的字符串的长度，将其除以8，得到其占用的字节数（float类型）。3. 压缩比将两个相除。（2）源代码void Huffman:Calculate(int x, int y) /编码前后的压缩比 cout编码前字符串长度为：x Byteendl; /编码前以字节存储 cout编码后字符串的大小为:y bitendl; /编码后以位存储 cout压缩比为：(float)(y/8)/(float)x)*100%endl; /计算压缩比 （3）时间复杂度时间复杂度为O(1)。2.3其他 1.由于题目要求能输入任意长的字符串，所以本程序采用了string变量来记录输入的字符串，并采用string类的类成员函数来完成各项任务 2.统计权值代码和将编码串逆置的代码都没有单独定义函数。其中统计权值代码放到了主程序中，将编码串逆置代码放到了CreateTable（）函数中。 3.未能将哈夫曼树直观打印出来。3、程序运行结果（1）程序流程图开始 调用主函数等待用户输入字符串利用用户输入的字符串创建哈夫曼树和编码表打印权值表和编码表计算编码前后的压缩比重新输入二进制编码调用解码函数进行解码结束（2）测试条件由用户任意输入一段字符，进行编码解码等操作。（3）运行结果：（4）说明：各函数运行正常，没有出现bug。四、总结1、调试时出现的问题及解决方法在给每个字符编码时，由于编码是从根结点开始，所以选用与前序遍历相似的递归遍历形式。其中需要一个字符型数组来记录路径和编码，由于递归一次才有一位编码，所以这个数组也要随着递归的进行而不断修改。开始时我没有用引用作为参数而是直接将数组作为参数，结果发现每次调用递归时数组都是空。原来我用的是值传递，数组就算修改了也无法返回。这提醒了我之后运用递归时如果需要某个变量随函数递归而修改时应该使用地址传递而非值传递。2、心得体会这是第三次实验编程，相比前两次实验的相对生疏来说，这次对于基本语句的运用差不多能熟练掌握。但是还是出现了不少的问题，比如在基本代码以及主程序敲定完成以后，编译并没有出现错误，但是一运行，编码就输出为无限循环，反复调试也找不出关键所在，一直坐在电脑前呆呆地看了代码两个小时，还是一无所获；后来隔一段时间之后自己又转回来重新看代码，才恍然大悟，原来是循环条件写错，编码逆置和逆置后的代码重新赋给数组没有做到两层分别循环，导致整个语句块未能正常调用。修改之后一切运行正常。我也明白了，如果一直盯着代码看，多数情况是什么也看不出来的，因为你脑袋里充斥的都是那短短几句代码，越想反而越糊涂；如果过一阵自己头脑清醒了再去想问题说不定会有新发现。这次实验，总结说来，让我更好地掌握了哈夫曼树的创建过程，了解了一种不等长编码的方法，用设断点调试的方法更加熟练，同时熟悉了STL中string类型的用法，对C+更加熟悉。3.下一步改进可以直观输出哈夫曼树，但是打印树需要考虑到结点所在的层次和需要打印空格的个数，难度有点大。主函数中用户交互界面做得还不是很好，之后的改进可以是用case条件语句，由用户决定输出权值、编码、解码等函数执行结果的次序。