数据结构实验报告――树.doc

《数据结构实验报告――树.doc》由会员上传分享，免费在线阅读，更多相关内容在工程资料-天天文库。

1、2008级数据结构实验报告实验名称：实验三树学生姓名：班级：班内序号：学号：日期：2009年11月23日1．实验要求a.实验目的通过选择两个题目之一进行实现，掌握如下内容：Ø掌握二叉树基本操作的实现方法Ø了解赫夫曼树的思想和相关概念Ø学习使用二叉树解决实际问题的能力b.实验内容利用二叉树结构实现赫夫曼编/解码器。基本要求：1、初始化(Init)：能够对输入的任意长度的字符串s进行统计，统计每个字符的频度，并建立赫夫曼树2、建立编码表(CreateTable)：利用已经建好的赫夫曼树进行编码，并将每个字

2、符的编码输出。3、编码(Encoding)：根据编码表对输入的字符串进行编码，并将编码后的字符串输出。4、译码(Decoding)：利用已经建好的赫夫曼树对编码后的字符串进行译码，并输出译码结果。5、打印(Print)：以直观的方式打印赫夫曼树（选作）6、计算输入的字符串编码前和编码后的长度，并进行分析，讨论赫夫曼编码的压缩效果。2.程序分析2.1存储结构存储结构:二叉树示意图如下:2.2关键算法分析核心算法思想：1.哈夫曼编码(HuffmanCoding)是可变字长编码。编码时借助哈夫曼树，也即带权

3、路径长度最小的二叉树，来建立编码。2.哈夫曼编码可以实现无损数据压缩。单个字符用一个特定长度的位序列替代：在字符串中出现频率高的符号，使用短的位序列，而那些很少出现的符号，则用较长的位序列。关键算法思想描述和实现：关键算法1：统计字符出现的频度，记录出现的字符及其权值，对未出现的字符不予统计编码。将统计的叶子节点编制成数组。为创建哈夫曼树作准备。C++实现：for(inti=0;str[i]!='';i++)//统计频度frequency[(short)str[i]]++;此处以一个一维的下标表示

4、ascII编码，以元素之表示字符频度，解决统计字符的问题。for(intj=0;j<128;j++)//统计叶子节点个数if(frequency[j]!=0)leaf++;此处扫描一遍上面建立的数组得到叶子节点的个数，则由(leaf*2-1)得到总的节点个数。关键算法2：建立哈弗曼树——即最优二叉树。这里实现时：每建立一个父节点就需要扫描权值序列得到两个最小的权值。由于节点个数逐渐增多，因而扫描次数动态变化，程序里设置计数变量来控制扫描次数的变化。另外设置标记来标识节点是否已经被取出。由于前面得出了总

5、的叶子节点个数，根据哈弗曼树建立的规律可以知道总的节点数和建立哈弗曼树过程中的父子节点间的对应关系，因而可以通过下标准确定位节点，动态建立哈弗曼树。具体C++实现参看源代码中的CreateTree()函数。关键算法3：建立字符编码表。这里采用从叶子节点到根节点的顺序逆序编码，然后字符串转置得到最终编码。C++实现：while(parent!=-1){if(ptreetable[parent].lchild==child)strcat(pcodetable[j].code,"0");//左孩子编码0el

6、sestrcat(pcodetable[j].code,"1");//右孩子编码1child=parent;//实现递归parent=ptreetable[child].parent;}此处从叶子节点向根节点编码，通过迭代法递归实现节点的查找。strrev(pcodetable[j].code);//字符串逆序这里调用String类中strrev()函数实现字符串的逆序。关键算法4：扫描原字符串，在字符编码表中查找相应字符的编码，串接写入编码串。C++实现：for(inti=0;str[i]!='

7、';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]!='';i++){if(p

8、treetable[parent].lchild==-1)//找到叶子节点{strcat(pstr,pcodetable[parent].ch);//串接字符parent=leaf*2-2;}if(pcode[i]=='0')parent=ptreetable[parent].lchild;//走左支elseparent=ptreetable[parent].rchild;//走右支关键算法6：统计分析压缩效果。由于是模拟编码，重点在理解数据结构和算法，