数据结构实验报告-树

北京邮电大学电信工程学院第20页北京邮电大学电信工程学院第1页2008级数据结构实验报告实验名称：实验三树学生姓名：班级：班内序号：学号：日期：2009年11月23日实验要求a.实验目的通过选择两个题目之一进行实现，掌握如下内容：掌握二叉树基本操作的实现方法了解赫夫曼树的思想和相关概念学习使用二叉树解决实际问题的能力b.实验内容利用二叉树结构实现赫夫曼编/解码器。基本要求：初始化(Init)：能够对输入的任意长度的字符串s进行统计，统计每个字符的频度，并建立赫夫曼树建立编码表(CreateTable)：利用已经建好的赫夫曼树进行编码，并将每个字符的编码输出。编码(Encoding)：根据编码表对输入的字符串进行编码，并将编码后的字符串输出。译码(Decoding)：利用已经建好的赫夫曼树对编码后的字符串进行译码，并输出译码结果。打印(Print)：以直观的方式打印赫夫曼树（选作）计算输入的字符串编码前和编码后的长度，并进行分析，讨论赫夫曼编码的压缩效果。

2.程序分析2.1存储结构存储结构:二叉树示意图如下:2.2关键算法分析核心算法思想：哈夫曼编码(HuffmanCoding)是可变字长编码。编码时借助哈夫曼树，也即带权路径长度最小的二叉树，来建立编码。哈夫曼编码可以实现无损数据压缩。单个字符用一个特定长度的位序列替代：在字符串中出现频率高的符号，使用短的位序列，而那些很少出现的符号，则用较长的位序列。关键算法思想描述和实现：关键算法1：统计字符出现的频度，记录出现的字符及其权值，对未出现的字符不予统计编码。将统计的叶子节点编制成数组。为创建哈夫曼树作准备。C++实现：for(inti=0;str[i]!='\0';i++) //统计频度 frequency[(short)str[i]]++; 此处以一个一维的下标表示ascII编码，以元素之表示字符频度，解决统计字符的问题。for(intj=0;j<128;j++) //统计叶子节点个数 if(frequency[j]!=0)leaf++; 此处扫描一遍上面建立的数组得到叶子节点的个数，则由(leaf*2-1)得到总的节点个数。关键算法2：建立哈弗曼树——即最优二叉树。这里实现时：每建立一个父节点就需要扫描权值序列得到两个最小的权值。由于节点个数逐渐增多，因而扫描次数动态变化，程序里设置计数变量来控制扫描次数的变化。另外设置标记来标识节点是否已经被取出。由于前面得出了总的叶子节点个数，根据哈弗曼树建立的规律可以知道总的节点数和建立哈弗曼树过程中的父子节点间的对应关系，因而可以通过下标准确定位节点，动态建立哈弗曼树。具体C++实现参看源代码中的CreateTree()函数。关键算法3：建立字符编码表。这里采用从叶子节点到根节点的顺序逆序编码，然后字符串转置得到最终编码。C++实现：while(parent!=-1) { if(ptreetable[parent].lchild==child) strcat(pcodetable[j].code,"0"); //左孩子编码0 else strcat(pcodetable[j].code,"1"); //右孩子编码1 child=parent; //实现递归 parent=ptreetable[child].parent; } 此处从叶子节点向根节点编码，通过迭代法递归实现节点的查找。strrev(pcodetable[j].code); //字符串逆序这里调用String类中strrev()函数实现字符串的逆序。关键算法4：扫描原字符串，在字符编码表中查找相应字符的编码，串接写入编码串。C++实现：for(inti=0;str[i]!='\0';i++) { num=0; for(intj=0;str[i]!=pcodetable[j].ch[0];j++,num++){;} //查找编码表 strcat(pcode,pcodetable[num].code); //串接编码 }关键算法5：解码。这里从根节点出发，顺序查找，根据0和1的决定走左支还是右支。当查找到叶子节点时，将字符串接写入解码字符串，并将查找点置于根节点，开始后续解码，循环直到编码后的字符串遍历完毕。C++实现：for(inti=0;pcode[i-1]!='\0';i++) { if(ptreetable[parent].lchild==-1) //找到叶子节点 { strcat(pstr,pcodetable[parent].ch); //串接字符 parent=leaf*2-2; } if(pcode[i]=='0')parent=ptreetable[parent].lchild; //走左支 else parent=ptreetable[parent].rchild; //走右支关键算法6： 统计分析压缩效果。由于是模拟编码，重点在理解数据结构和算法，故没有进行位操作，输出的编码依旧以字符串存储，故计算压缩后长度需要折算。C++实现： intbefore=strlen(str); //原始编码大小 intlength=strlen(pcode); //模拟的编码串的大小 intafter=ceill((float)length/8); //如果进行bit存储时应该有的压缩效果 floatrate=after/(float)before; //压缩比率时间复杂度与空间复杂度：1.编码和解码需要大量扫描数据，因而时间复杂度很高。由于遍历的时候主要采用for循环结构，故主要的时间复杂度集中在此。设不同字符的个数为n，则整个程序的时间复杂度可以累加计算，最后估算结果是：O(3*n(n+3)/2)。2.由于使用数组存储字符串，有一定的空间浪费，空间复杂度由初始定义的字符串最大可用长度Max和不同字符个数n决定。计算总的空间复杂度约为O(Max*(n+4)/2+45n+20)。

3.程序运行结果

测试条件：以随机输入的一串字符串。（测试对字符的兼容能力）实验题目中给出的字符串。（测试小规模数据的编解码能力）网上摘录的大段文字。（测试大规模数据编解码能力）测试结论：本程序对所有ASCII编码均支持，对大规模和小规模编码均能实现正确编解码和压缩。

4.总结1、哈夫曼编码的基本思想是对出现频率高的输入单元赋予较短的比特片，而对出现频率低的输入单元赋予较长的比特片，从而使编码后的字符串平均长度降低,达到无损数据压缩的目的。这种压缩的思想需要去理解和掌握。而通过哈弗曼树的方式来编码的这种巧妙的构思应好好体会。2、这算是写过的最长的代码了，中间遇到了不少阻碍。上课老师讲了实现的思想方法，但自己在将这种思想付诸实践形成代码的过程中却并非容易。有时看老师写代码就像是说话或者说写作文一样简单，但是自己真正动手操作的时候却发现并非易事。自己对编程语言的掌握和理解还不够透，写程序不够熟练，在算法到代码还有很长的鸿沟。须是在今后的编程实践中勤加练习，多问多思，终有一天达到老师的水准。3、学习哈弗曼编码是一个点，从这个点出发，可以思考很多，比如ASCII码的编码会了，GB编码呢？UTP-8编码呢？能否仿照实现呢？比如其他的压缩算法呢？能否扩展开去，了解和掌握更多形式的编码和压缩技术呢？编码和压缩在后续课程中体现较多，应用也很广，应当扩展开去学习。4、思考改进：A．由于主要考虑模拟算法、理解数据结构，所以只是模拟实现压缩，最后只是用字符串存储的压缩后的编码，严格说实际压缩还没有实现，后续应考虑能否对bit位进行操作，实现能够实际存储的代码。B．本程序只能处理ASCII编码，对汉字编码和其他编码格式尚不支持，后续应考虑研究不同的编码格式，进行编码转换，实现对多种编码格式的压缩支持。C．用数组处理字符串造成了一定的空间的浪费，后续应考虑采取其他方式处理字符串。D．程序中对数据进行了大量的扫描和遍历，当数据量很大的时候，时间复杂度将很高，应该考虑改进哈弗曼编码。网上应该有类似的优化的哈弗曼算法，应学习和借鉴。

附录源码：（包含两个.cpp文件一个.h文件）//Main.cpp#include<iostream>#include"Huffman.h"usingnamespacestd;intmain(){ cout<<"************欢迎测试Huffman编码***************"<<endl; cout<<"请输入要编码的字符串：（暂不支持中文编码）"<<endl; Huffmanobj; obj.Init(); obj.CreateTree(); obj.CreateTable(); obj.Encoding(); obj.Decoding(); cout<<"请选择操作：\n"<<"1.打印原始字符串的统计数据\n"<<"2.以表格方式打印Huffman树\n" <<"3.打印编码表\n"<<"4.打印编码后的字符串\n" <<"5.输出解码后的字符串\n"<<"6.分析压缩效果\n"; unsignedintoption; while(true) { cin>>option; switch(option) { case1: cout<<'\n'<<"总共的字符个数："<<strlen(obj.str)/sizeof(char)<<endl; cout<<"不同的字符总数："<<obj.leaf<<endl; cout<<"字符\t"<<"频率\t"<<endl; for(intj=0;j<obj.leaf;j++) cout<<obj.pcodetable[j].ch<<'\t'<<obj.pcodetable[j].freq<<endl; break; case2: cout<<"Huffman树表如下：\n"; cout<<"序号\t"<<"权值\t"<<"父节点\t"<<"左孩子\t"<<"右孩子\n"; for(intt=0;t<2*obj.leaf-1;t++) { cout<<t<<":"<<'\t'<<obj.ptreetable[t].weight<<"\t"<<obj.ptreetable[t].parent<<"\t"<<obj.ptreetable[t].lchild<<"\t" <<obj.ptreetable[t].rchild<<endl; } break; case3: cout<<"字符\t"<<"编码\t"<<endl; for(intj=0;j<obj.leaf;j++) cout<<obj.pcodetable[j].ch<<'\t'<<obj.pcodetable[j].code<<endl; break; case4: cout<<"\n编码后的字符串如下：\n"<<obj.pcode<<endl; break; case5: cout<<"\n解码后的字符串如下：\n"<<obj.pstr<<endl; break; case6: obj.Analyse(); break; default: cout<<"\n缺省输出：\n"; cout<<"\n编码后的字符串如下：\n"<<obj.pcode<<endl; obj.Analyse(); return0; } } return0;}//Huffman.h#include<string>constintMax=1000;structtreetable //树表的元素 { intweight; //权值 intparent; //父节点 intlchild; //左孩子 intrchild; //右孩子 intmark; //标记是否已经编码 };structcodetable //编码表的元素 { charch[2]; //字符 intfreq; //频度 charcode[Max/2]; //字符编码 };classHuffman //Huffman类定义{public: Huffman(){;} ~Huffman(); intInit(); //初始化类,统计必要的原始字符串数据 intCreateTree(); //建立哈弗曼树表 intCreateTable(); //建立编码表 intEncoding(); //对给定的字符串进行编码 intDecoding(); //对编码后的字符串进行解码 intAnalyse(); //分析编码压缩的相关数据 friendintmain();private: charstr[Max]; //保存用户输入字符串 treetable*ptreetable; //保存哈弗曼树表 codetable*pcodetable; //保存编码表 intleaf; //叶子节点个数 char*pcode; //保存压缩后的字符串 char*pstr; //保存解压缩之后的字符串};//HuffmanFunc.cpp#include"Huffman.h"#include<iostream>#include<string>#include<cmath>usingnamespacestd;/*****************************************************************************************************************************************/intHuffman::Init(){ cin.getline(str,Max); cout<<"正在初始化编码……"<<endl; shortfrequency[128]={0}; leaf=0; for(inti=0;str[i]!='\0';i++) //统计频度 frequency[(short)str[i]]++; for(intj=0;j<128;j++) //统计叶子节点个数 if(frequency[j]!=0)leaf++; ptreetable=newtreetable[leaf*2-1]; pcodetable=newcodetable[leaf]; for(intk=0,m=0;k<128;k++) //建立叶子节点表 { if(frequency[k]!=0) { pcodetable[m].freq=ptreetable[m].weight=frequency[k]; pcodetable[m].ch[0]=(char)k; pcodetable[m].ch[1]='\0'; pcodetable[m].code[0]='\0'; ptreetable[m].mark=0; m++; } } for(intk=0;k<leaf;k++) //标记叶子节点：无左右孩子 ptreetable[k].lchild=ptreetable[k].rchild=-1; return0;}/*****************************************************************************************************************************************/intHuffman::CreateTree(){intmin=Max; intnum(0),times(leaf),front(leaf),count1(0),count2(0),lcvalue(0),rcvalue(0); for(ints=0;s<(2*leaf-2);s++) { for(inti=0;i<times;i++) { if(ptreetable[i].mark!=1&&min>=ptreetable[i].weight) {min=ptreetable[i].weight;num=i;} } count1++; if(count1==2){times++;count1=0;} ptreetable[num].mark=1; //标记已读 count2++; if(count2==1) //左孩子 { lcvalue=min; ptreetable[num].parent=front; ptreetable[front].lchild=num; } if(count2==2) //右孩子 { rcvalue=min; ptreetable[num].parent=front; ptreetable[front].rchild=num; ptreetable[front].weight=lcvalue+rcvalue; front++; count2=0; } min=Max; } ptreetable[2*leaf-2].parent=-1; ptreetable[2*leaf-2].mark=-1; return0;}/*****************************************************************************************************************************************/intHuffman::CreateTable(){ for(intj=0,parent=0,child=0;j<leaf;j++) { parent=ptreetable[j].parent; child=j; while(parent!=-1) { if(ptreetable[parent].lchild==child) strcat(pcodetable[j].code,"0"); else strcat(pcodetable[j].code,"1"); child=parent; parent=ptreetable[child].parent; } strrev(pcodetable[j].code); } return0;}/*****************************************************************************************************************************************/intHuffman::Encoding(){ intnum; pcode=newchar[Max]; pcode[0]='\0'; for(inti=0;str[i]!='\0';i++) { num=0; for(intj=0;str[i]!=pcodetable[j].ch[0];j++,num++){;} strcat(pcode,pcodetable[num].code); } return0;}/*****************************************************************************************************************************************/intHuffman::Decoding(){ intparent=leaf*2-2; pstr=newchar[Max]; pstr[0]='\0'; for(inti=0;pcode[i-1]!='\0';i++) { if(ptreetable[parent].lchild==-1) {