实 验 报 告
课程名称 ____数据结构上机实验__________ 实验项目 ______二叉树的应用 ____________ 实验仪器 ________PC机___________________
系 别____________________________ 专 业_____________________________ 班级/学号____________________________
学生姓名 _____________________________ 实验日期 _______________________ 成 绩 _______________________
指导教师 _______________________
实验三.二叉树的应用
1. 实验目的：掌握二叉树的链式存储结构和常用算法。利
用哈夫曼树设计最优压缩编码。
2. 实验内容：
1) 编写函数，实现建立哈夫曼树和显示哈夫曼树的功能。 2) 编写函数，实现生成哈夫曼编码的功能。
3) 编写主函数，从终端输入一段英文文本；统计各个字符出现的频率，然后构建哈夫曼树并求出对应的哈夫曼编码；显示哈夫曼树和哈夫曼编码。
选做内容：修改程序，选择实现以下功能：
4) 编码：用哈夫曼编码对一段英文文本进行压缩编码，显示编码后的文本编码序列；
5) 统计：计算并显示文本的压缩比例；
6) 解码：将采用哈夫曼编码压缩的文本还原为英文文本。
3. 算法说明：
1) 二叉树和哈夫曼树的相关算法见讲义。
2) 编码的方法是：从头开始逐个读取文本字符串中的每个字符，查编码表得到它的编码并输出。重复处理直至文本结束。
3) 解码的方法是：将指针指向哈夫曼树的树根，从头开始逐个读取编码序列中的每位，若该位为1则向右子树走，为
0则向左子树走。当走到叶子节点时，取出节点中的字符并输出。重新将指针放到树根，继续以上过程直至编码序列处理完毕。
4) 压缩比例的计算：编码后的文本长度为编码序列中的0和1,的个数，原文本长度为字符数*8。两者之比即为压缩比。
4. 实验步骤：
实现哈夫曼树的编码序列操作：
int i=0,j=0; huffnode p;
p=tree[2*n-2];//序号2*n-2节点就是树根节点
while(hfmstr[i]!='\\0')//从头开始扫描每个字符,直到结束 {while(p.lchild!=-1&&p.rchild!=-1) if(hfmstr[i]=='0')//为0则向左子树走 {
p=tree[p.lchild];//取出叶子节点中的字符 }
else if(hfmstr[i]=='1')//为1则向右子树走 {
p=tree[p.rchild];//取出叶子节点中的字符 } i++; }
decodestr[j]=p.data;j++;//对字符进行译码,结果放在decodestr字符串中
p=tree[2*n-2];//返回根节点 } }
程序修改后完整源代码如下：
#include
#include
#define N 96 //ASCII字符集包含至多N个可见字符 typedef struct //Huffman树节点定义 { char data; //字符值 int weight; //权重 int lchild; //左子结点 int rchild; //右子结点
} huffnode; //huffman节点类型 struct charcode
{ int count; //字符出现的次数(频率) char code[N]; //字符的Huffman编码
} codeset[N]; //编码表,长为N,每项对应一个ascii码字符,下标
i的项对应ascii编码为i+32的字符
huffnode * CreateHufftree(char data[], int weight[], int n) //建立Huffman树的算法 { int i,k;
int min1,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;i++) //初始化,将各字符和其频率填入Huffman树,作为叶子结点 {
tree[i].lchild=tree[i].rchild=-1; if (i tree[i].data=data[i]; tree[i].weight=weight[i]; } else tree[i].data=' '; } for (i=n;i<2*n-1;i++) ////合并两棵树,作n-1遍 { min1=min2=INT_MAX; //INT_MAX为最大值
二叉树的应用实验报告
