二叉树的应用实验报告

《二叉树的应用实验报告》由会员上传分享，免费在线阅读，更多相关内容在行业资料-天天文库。

1、实验报告课程名称____数据结构上机实验__________实验项目______二叉树的应用____________实验仪器________PC机___________________系别____________________________专业_____________________________班级/学号____________________________学生姓名_____________________________实验日期_______________________成绩_______________________指导教师___________________

2、____精选范本,供参考！实验三.二叉树的应用1.实验目的：掌握二叉树的链式存储结构和常用算法。利用哈夫曼树设计最优压缩编码。2.实验内容：1)编写函数，实现建立哈夫曼树和显示哈夫曼树的功能。2)编写函数，实现生成哈夫曼编码的功能。3)编写主函数，从终端输入一段英文文本；统计各个字符出现的频率，然后构建哈夫曼树并求出对应的哈夫曼编码；显示哈夫曼树和哈夫曼编码。选做内容：修改程序，选择实现以下功能：4)编码：用哈夫曼编码对一段英文文本进行压缩编码，显示编码后的文本编码序列；5)统计：计算并显示文本的压缩比例；6)解码：将采用哈夫曼编码压缩的文本还原为英文文本。3.算法说明：1)二叉树

3、和哈夫曼树的相关算法见讲义。2)编码的方法是：从头开始逐个读取文本字符串中的每个字符，查编码表得到它的编码并输出。重复处理直至文本结束。3)解码的方法是：将指针指向哈夫曼树的树根，从头开始逐个读取编码序列中的每位，若该位为1则向右精选范本,供参考！子树走，为0则向左子树走。当走到叶子节点时，取出节点中的字符并输出。重新将指针放到树根，继续以上过程直至编码序列处理完毕。1)压缩比例的计算：编码后的文本长度为编码序列中的0和1,的个数，原文本长度为字符数*8。两者之比即为压缩比。1.实验步骤：实现哈夫曼树的编码序列操作：inti=0,j=0;huffnodep;p=tree[2*n-2

4、];//序号2*n-2节点就是树根节点while(hfmstr[i]!='')//从头开始扫描每个字符,直到结束{while(p.lchild!=-1&&p.rchild!=-1)if(hfmstr[i]=='0')//为0则向左子树走{p=tree[p.lchild];//取出叶子节点中的字符}elseif(hfmstr[i]=='1')//为1则向右子树走{p=tree[p.rchild];//取出叶子节点中的字符}i++;}精选范本,供参考！decodestr[j]=p.data;j++;//对字符进行译码,结果放在decodestr字符串中p=tree[2*n-2];/

5、/返回根节点}}程序修改后完整源代码如下：#include#include#include#include//专门用于检测整型数据数据类型的表达值范围#defineN96//ASCII字符集包含至多N个可见字符typedefstruct//Huffman树节点定义{chardata;//字符值intweight;//权重intlchild;//左子结点intrchild;//右子结点}huffnode;//huffman节点类型structcharcode{intcount;//字符出现的次数(频率)ch

6、arcode[N];//字符的Huffman编码}codeset[N];精选范本,供参考！//编码表,长为N,每项对应一个ascii码字符,下标i的项对应ascii编码为i+32的字符huffnode*CreateHufftree(chardata[],intweight[],intn)//建立Huffman树的算法{inti,k;intmin1,min2,min_i1,min_i2;huffnode*tree;tree=(huffnode*)malloc((2*n-1)*sizeof(huffnode));//为Huffman树分配2n-1个节点空间for(i=0;i<2*n-1

7、;i++)//初始化,将各字符和其频率填入Huffman树,作为叶子结点{tree[i].lchild=tree[i].rchild=-1;if(i