数据结构实验报告
实验名称：实验三树
学生姓名：
班级：
班内序号：
学号：
日期：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 BiTree
{
public:
BiTree(); //构造函数，其前序序列由键盘输入 ~BiTree(void); //析构函数
BiNode* Getroot(); //获得指向根结点的指针
protected:
BiNode *root; //指向根结点的头指针
};
//声明类BiTree 及定义结构BiNode
Data ：
二叉树是由一个根结点和两棵互不相交的左右子树构成。
二叉树中的结点具有相同数据类型及层次关系。
（2
）静态三叉链表
struct HNode //哈夫曼树的静态三叉链表 {
unsigned int weight; //结点权值
unsigned int parent; //双亲指针
unsigned int Lchild; //左孩子指针
unsigned int Rchild; //右孩子指针
};
示意图：
(3) 编码表的节点结构 struct HCode //字符及其编码结构 {
char data;
char code[100];
};
示意图：
2.2关键算法分析
一：关键算法
(一)初始化函数void Huffman::Init(int a[],int n)
（1）算法自然语言
1.创建一个长度为2*n -1的三叉链表
2.将存储字符及其权值的链表中的字符逐个写入三叉链表的前n个结点的data域，并将对
应结点的孩子域和双亲域赋为空
3.从三叉链表的第n个结点开始，i=n
3.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 HNode[2*n-1]; //根据权重数组a[1—>n]初始化哈夫曼树
int i,x,y;
for(i=0;i{
HTree[i].weight=a[i];
HTree[i].Lchild=-1;
HTree[i].Rchild=-1;
HTree[i].parent=-1;
}
for(int i=n;i<2*n-1;i++) //开始建哈夫曼树，从底层向顶层搭建
{
SelectMin(HTree,i,x,y); //从--(i-1)中选出两个权值最小的结点
HTree[x].parent=i;
HTree[y].parent=i; //左右孩子权值相加为父结点的权值
HTree[i].weight=HTree[x].weight+HTree[y].weight;
HTree[i].Lchild=x;
HTree[i].Rchild=y;
HTree[i].parent=-1;
}
}
(3)时间复杂度
在选取两个权值最小的结点的函数中要遍历链表，时间复杂度为O(n),故该函数的时间复杂度为O（n^2）
（二）统计字符出现频度的代码
（1）算法自然语言
①用cin.getline（）函数获取一段字符串。同时设置一个权值数组weight，以及暂时统计和存放权值的数组s。
②用strlen（）函数获取未编码时的字符串长度。
③从字符串的起始位置进行权值统计，即获得str[i]每个字符的ASⅡ编码，并在s[(int)str[i]]数组中进行+1统计，为字符出现一次。
④ i进行自加，统计下面字符出现的频度，在相应的数组元素中进行+1统计。
⑤继续循环，直到字符串结束。
（2）源代码（在main（）函数中实现）
int i,j=0,v;
int s[200]={0};
int weight[M]; //权值数组
cout<<"请输入一段字符串，按回车键结束："<cin.getline(str,1000,'\n'); //由用户输入一段字符串
cout<Len1=strlen(str); //得到未编码时的字符串长度
for(i=0;str[i]!='\0';i++) //统计每个字符的权值
s[(int)str[i]]++; //(int)str[i]为每个字符的ASⅡ编码
for(i=0;i<200;i++)
if(s[i]!=0) //如果权值不为
{
c[j]=i; //ASⅡ编码为i的字符写入字符数组c
weight[j]=s[i]; //权值s数组赋给权值weight数组 j++;
}
n=j; //叶子结点个数
for(v=0;vcout<(3)时间复杂度：
若输入的字符串长度为n，则时间复杂度为O(n)
