北邮数据结构实验三哈夫曼树.docx
《北邮数据结构实验三哈夫曼树.docx》由会员分享，可在线阅读，更多相关《北邮数据结构实验三哈夫曼树.docx（17页珍藏版）》请在冰点文库上搜索。
北邮数据结构实验三哈夫曼树
数据结构实验报告
实验名称：
实验三——树
学生姓名：
班级：
班内序号：
学号：
日期：
1实验目的
通过选择下面两个题目之一进行实现，掌握如下内容：
Ø掌握二叉树基本操作的实现方法
Ø了解哈夫曼树的思想和相关概念
Ø学习使用二叉树解决实际问题的能力
实验内容：
利用二叉树结构实现哈夫曼编/解码器。
基本要求：
1、初始化（Init）：
能够对输入的任意长度的字符串s进行统计，统计每个字符的频度，并建立哈夫曼树
2、建立编码表（CreateTable）：
利用已经建好的哈夫曼树进行编码，并将每个字符的编码输出。
3、编码（Encoding）：
根据编码表对输入的字符串进行编码，并将编码后的字符串输出。
4、译码（Decoding）：
利用已经建好的哈夫曼树对编码后的字符串进行译码，并输出译码结果。
5、打印（Print）：
以直观的方式打印哈夫曼树（选作）
6、计算输入的字符串编码前和编码后的长度，并进行分析，讨论赫夫曼编码的压缩效果。
（选作）
7、可采用二进制编码方式（选作）
测试数据：
IlovedataStructure,IloveComputer。
IwilltrymybesttostudydataStructure.
2程序分析
2.1存储结构：
三叉树：
classHuffman
{
private:
HNode*HTree;//哈夫曼树结点
HCode*HCodeTable;//哈夫曼编码表
charb[1000];//记录所有输入内容被编码后的结果
charc[127];
charletter[1000];//输入内容的保存
voidSelectMin（int&x,int&y,intk）;//求最小权重的字符
node*count;//计算各个字符出现次数
intn;//输入字符的种类（个数）
intl;
public:
Huffman（）;
voidCreateHTree（）;//创建哈夫曼树
voidCreateCodeTable（）;//创建哈夫曼编码表
voidEncode（）;//编码
voidDecode（）;//解码
};
结点结构为如下所示：
三叉树的节点结构：
structHNode//哈夫曼树结点的结构体
{intweight;//结点权值
intparent;//双亲指针
intlchild;//左孩子指针
intrchild;//右孩子指针
chardata;//字符
};
示意图为：
intweight
intparent
intlchild
intrchild
chardata
编码表节点结构：
structHCode//编码表结构体
{
chardata;//字符
charcode[100];//编码内容
};
示意图为：
chardata
charcode[100]
基本结构体记录字符和出现次数:
structnode
{
intnum;
chardata;
};
示意图为:
intnum
chardata
2.关键算法分析
（1）.初始化:
伪代码：
1.输入需要编译的文本内容
2.将输入的内容保存到动态建立的node型数组count中
3.统计出现的字符种类的数目,并且保存到private型变量n
Huffman:
:
Huffman（）//将输入数据保存到Huffman类中
{
l=0;
n=0;
count=newnode[127];
cout<<"请输入需要编译压缩的内容"<cin.getline（letter,200,'\n'）;
for（intj=0;j<127;j++）//一个号码代表一种字符
{
count[j].num=0;
}
while（letter[l]!
='\0'）//在结束之前，每输入一个字符，则对应字符的数目则自增1
{
++count[letter[l]].num;
count[letter[l]].data=letter[l];
++l;
}
for（intk=0;k<127;k++）{
if（count[k].num>0）
{n++;}//在某个字符出现此书num不为0时，n自增1，最终n为出现的字符种类数目
}
其时间复杂度为O（n）
（2）.创建哈夫曼树（voidHuffmanTree:
:
CreateCodeTable（Node*p））
算法伪代码：
1.创建一个长度为2*n-1的三叉链表
2.将存储字符及其权值的链表中的字符逐个写入三叉链表的前n个结点的data域，并将对应结点的孩子域和双亲域赋为空
3.从三叉链表的第n个结点开始，
3.1从存储字符及其权值的链表中取出两个权值最小的结点x,y，记录其下标x,y。
3.2将下标为x和y的哈夫曼树的结点的双亲设置为第i个结点
3.3将下标为x的结点设置为i结点的左孩子，将下标为y的结点设置为i结点的右孩子，i结点的权值为x结点的权值加上y结点的权值，i结点的双亲设置为空
4.根据哈夫曼树创建编码表
源代码为：
voidHuffman:
:
CreateHTree（）
{
l=0;
HTree=newHNode[2*n-1];//建立含有n种字符的哈夫曼树只需要2*n-1个结点即可
for（inti=0;i{
while（count[l].num==0）//如果count内的权重为0，即该字符没有出现，则跳过，i自增继续寻找出现过的字符
{l++;}
HTree[i].weight=count[l].num;//将count里统计的次数传入哈夫曼树的节点中，作为字符权重
HTree[i].lchild=-1;
HTree[i].rchild=-1;
HTree[i].parent=-1;//将左右孩子结点和父节点都置空
HTree[i].data=count[l].data;//将count内的有效字符传入哈夫曼树的结点
l++;
}
intx=-1,y=-1;
for（inti=n;i<2*n-1;i++）//开始建立哈夫曼树
{
SelectMin（x,y,i）;//挑选三者中的权重较小的两个
HTree[x].parent=HTree[y].parent=i;//令较小的x、y为孩子节点，该两个结点的父节点是i
HTree[i].weight=HTree[x].weight+HTree[y].weight;//i结点字符的权重赋为是左右孩子字符权重之和
HTree[i].lchild=x;//左孩子为x
HTree[i].rchild=y;//右孩子为y
HTree[i].parent=-1;//父节点置空
x=-1;
y=-1;//将x、y重新赋值为零，进行下一次比较建树
｝
其时间复杂度为：
O（n）
（3）．创建编码表
算法伪代码：
1.初始化编码表
2.初始化一个指针，从链表的头结点开始，遍历整个链表
2.1将链表中指针当前所指的结点包含的字符写入编码表中
2.2得到该结点对应的哈夫曼树的叶子结点及其双亲
2.3如果哈夫曼树只有一个叶子结点，将其字符对应编码设置为0
2.4如果不止一个叶子结点，从当前叶子结点开始判断
2.4.1如果当前叶子结点是其双亲的左孩子，则其对应的编码为0，否则为1
2.4.2child指针指向叶子结点的双亲，parent指针指向child指针的双亲，重复2.4.1的操作
2.5将已完成的编码倒序
2.6取得链表中的下一个字符
3．输出编码表
源代码为：
voidHuffman:
:
CreateCodeTable（）//建立哈夫曼编码表
{
HCodeTable=newHCode[n];//建立动态编码表
for（inti=0;i{
HCodeTable[i].data=HTree[i].data;
intchild=i;
intparent=HTree[i].parent;
intk=0;
while（parent!
=-1）
{
if（child==HTree[parent].lchild）//判断该节点是父节点的左孩子或右孩子，左孩子则编码为0，右孩子则编码为1
HCodeTable[i].code[k]='0';
else
HCodeTable[i].code[k]='1';
k++;
child=parent;//将该节点的父节点作为新的孩子节点，继续进行编码输出
parent=HTree[child].parent;
}
HCodeTable[i].code[k]='\0';//code数组以\0结尾
Reverse（HCodeTable[i].code）;//由于是从下到上输出，顺序是相反的，所以还需要逆置才能输出字符的编码值
}
cout<"<for（inti=0;i{
cout<"<}
}
}
其时间复杂度为：
O（n）
（4）选择两个最小权值的函数voidHuffman:
:
SelectMin（int&x,int&y,intk）
算法伪代码：
1.从下标为i=0的开始遍历。
前两次将x，y赋值为序号最小的两个结点的地址序号。
2.开始进行比较：
进行如下分类
对于任何不存在父节点的结点：
若x权值<=y权值
（1）且i权值>=y权值，则无疑i权值最大，为输出x、y为权值较小的两个故而x，y值不便；
（2）其余情况皆为x、i的权值是较小的两个，令y赋值为i，则保证x、y权值是最小的两个。
若y权值<=x权值
（1）且i权值>=x权值，则i权值是最大，x、y不变。
（2）其余情况皆为i、y权值最小，令x赋值为i，保证x、y序号结点的权值最小
3.完成如上循环，直至i=k则推出循环，第k个结点在树的位置已经确定
源代码为：
voidHuffman:
:
SelectMin（int&x,int&y,intk）//选出权值较小的两个字符结点
{
inti=0;
while（i{
while（i{
if（x==-1）
x=i;
elseif（y==-1）
y=i;
else
if（HTree[x].weight<=HTree[y].weight）
{
if（HTree[y].weight<=HTree[i].weight）
{y=y;x=x;}
else
y=i;
}
else
if（HTree[x].weight>HTree[y].weight）
{
if（HTree[i].weight>=HTree[x].weight）
{x=x;y=y;}
else
x=i;
}
i++;
}
i++;
}
}
其时间复杂度为O（n）
（5）.将字符串倒序的函数（voidHuffmanTree:
:
Reverse（char*pch））
算法伪代码：
1．得到字符串的长度
2．初始化两个记录下标的变量，一个为字符串开头字符所在的下标i，另一个为字符串结尾字符所在的下标j
3．将下标为i和j的字符交换
4．i++,j--
源代码：
voidReverse（chara[]）
{
charb[100];
inti=0,j=0;
while（a[i]!
='\0'）
{
b[i]=a[i];
i++;
}
b[i]='\0';
i--;
while（i>=0）
{
a[j]=b[i];
i--;
j++;
}
a[j]='\0';
}
其时间复杂度为O（n）
（6）.编码函数（voidHuffman:
:
Encode（a[]））
算法伪代码：
1.从开头的字符开始，逐一对a中的字符进行编码
2.在编码表中查找与当前字符对应的字符
3．如果找到了与当前字符对应的编码表中的字符，将其编码追加到解码串的末尾。
4.重复以上步骤，直到所有待编码串中的字符都编码完毕
5.输出编码后的字符串
voidHuffman:
:
Encode（）//编译输入内容为代码内容用0和1表示
{
cout<<"编码结果为：
";
intk=0;
for（inti=0;letter[i]!
='\0';i++）
{
intj=0;
while（HCodeTable[j].data!
=letter[i]）//编码表的字符等于输入内容的字符时进行下一个while循环
{j++;}
intm=0;
while（HCodeTable[j].code[m]!
='\0'）//输出该字符的编码
{
b[k]=HCodeTable[j].code[m];//用数组b记录所有的编码数据，以备后续解码使用
k++;
m++;
}
}
b[k]='\0';
cout<cout<}
其时间复杂度为：
O（n）
（7）.解码函数（voidHuffman:
:
Decode（））
算法伪代码：
1.得到指向哈夫曼树的根结点的指针和指向待解码串中的第1个字符的指针
2.逐个读取待解码串中的字符，若为0，则指向哈夫曼树当前结点的指针指向当前结点的左孩子，若为1，则指向当前结点的右孩子
3.指向待解码串的指针指向解码串中的下一个字符，直到指向哈夫曼树结点的指针的孩子结点为空
4.如果哈夫曼树只有一个叶子结点，直接将待解码串中的编码转换为对应的字符
5.如果指向哈夫曼树结点的指针的孩子结点已经为空，则将叶子结点下标对应的字符追加到解码串中。
6.输出解码串
源代码：
voidHuffman:
:
Decode（）
{
cout<<"解码结果为：
";
inti=0,j=0;
while（b[i]!
='\0'）
{
intchild=2*n-1-1;//找到保存根节点的数组数
据
while（HTree[child].lchild!
=-1）//若是这个节
点父节点的孩子存在则继续向下寻找
{
if（b[i]=='0'）
child=HTree
[child].lchild;//是0则找左孩子
else
child=HTree
[child].rchild;//是1则找右孩子
i++;
}
c[j]=HCodeTable[child].data;//若不存在孩子节点，则令数组的元素为该节点的字符变量
cout<j++;//逐个输出字符内容
}
}
时间复杂度：
O（n）
3.程序运行结果
1.主函数流程图
运行结果：
4.总结
通过本次数据结构实验，我学会了利用哈夫曼树解决编译代码的问题，并且初步了解掌握了二叉树、树的用法。
实验重点是建立哈夫曼三叉树，建立编码表，解码函数，以及选择权重最小两个结点的函数的调用。
同时还要注意学会逆置输出代码等容易被忽视的细节问题。
本次实验提高了对于哈夫曼思想的加深理解，有利于以后编程的继续学习和实践能力的增强。
升级会员 