北邮数据结构实验报告三题目2哈夫曼树.docx
《北邮数据结构实验报告三题目2哈夫曼树.docx》由会员分享，可在线阅读，更多相关《北邮数据结构实验报告三题目2哈夫曼树.docx（16页珍藏版）》请在冰点文库上搜索。
北邮数据结构实验报告三题目2哈夫曼树
1．实验要求
利用二叉树结构实现哈夫曼编/解码器
（1）.初始化：
能够对输入的任意长度的字符串s进行统计，统计每个字符的频度，并建立哈夫曼树。
（2）.建立编码表：
利用已经建好的哈夫曼树进行编码，并将每个字符的编码输出。
（3）.编码：
根据编码表对输入的字符串进行编码，并将编码后的字符串输出。
（4）.译码：
利用已经建好的哈夫曼树对编码后的字符串进行译码，并输出译码结果。
（5）.打印：
以直观的方式打印哈夫曼树。
（6）.计算输入的字符串编码前和编码后的长度，并进行分析，讨论哈夫曼编码的压缩效果。
（7）.用户界面可以设计成“菜单”方式，能进行交互，根据输入的字符串中每个字符出现的次数统计频度，对没有出现的字符一律不用编码。
2.程序分析
2.1存储结构
二叉树：
示意图：
root
Parent
lchildrchild
2.2程序流程
2.3关键算法分析
1.定义哈夫曼树的模板类
#include
#include
usingnamespacestd;
structLNode//链表的节点,用来统计字符频率，并编码
{
charch;//字符
intweight;//权值
charcode[20];//字符编码
LNode*next;//指向下一个节点
};
structTNode//哈弗曼树结点的结构体
{
intweight;//结点权值
intLchild;//左孩子指针
intRchild;//右孩子指针
intParent;//双亲指针
};
classHuffman
{
public:
Huffman（）;//构造函数，输入、统计字符，创建哈弗曼树、码表
~Huffman（）;//释放链表空间、哈弗曼树的节点
voidCreateTable（）;//建立编码表，并将信息存入链表
voidPrintTable（）;//输出码表
voidEncoding（）;//哈弗曼编码
voidDecoding（）;//译码
voidComrate（）;//计算编码的压缩率
voidSelectMin（int&x,int&y,intbegin,intend）;
//选取权值最小的两个数，创建哈弗曼树
voidreverse（charch[]）;//将码值倒置，用来编码
voidcontrol（）;//对菜单交互等提示操作
private:
TNode*troot;
LNode*lroot;//在统计字符频率是构建链表的根节点
voidList（chara[]）;//统计字符的权值建立的单链表
voidHTree（）;//哈弗曼树建立
intLetter;//共有不同字符总数
charastr[1000];//用户输入的一串字符
charbstr[1000];//将字符串的码值保存
};
Huffman:
:
Huffman（）
{
lroot=newLNode;
bstr[0]='\0';
lroot->next=NULL;
Letter=0;//初始化字符总数为1
cout<<"请输入一串字符，以回车键结束"<cin.getline（astr,1000,'\n'）;
if（strlen（astr）==0）throw1;
else
{
List（astr）;//用链表存储每个字符
HTree（）;
CreateTable（）;
Encoding（）;
}
};
Huffman:
:
~Huffman（）
{
deletetroot;
LNode*p=lroot;
while（p=lroot->next）
{
lroot=p->next;
deletep;
p=lroot;
}
deletep;
};
2.建立哈夫曼树
voidHuffman:
:
HTree（）
{
LNode*p=lroot;
inta=0;
troot=newTNode[2*Letter-1];//2n-1个结点
while（p=p->next）//建立叶子节点
{
troot[a].weight=p->weight;
troot[a].Parent=-1;
troot[a].Lchild=-1;
troot[a].Rchild=-1;
a++;
};
for（inti=Letter;i<2*Letter-1;i++）
troot[i].Parent=-1;
intx,y,begin=0;//是两个最小值的角标
for（intj=Letter;j<2*Letter-1;j++）
{
while（troot[begin].Parent!
=-1）
begin++;
SelectMin（x,y,begin,j）;
troot[j].weight=troot[x].weight+troot[y].weight;
troot[j].Lchild=x;
troot[j].Rchild=y;
troot[j].Parent=-1;
troot[x].Parent=j;
troot[y].Parent=j;
}
};
3.统计字符的频率
voidHuffman:
:
List（chara[]）
{
LNode*p=lroot;
inti=0;
while（a[i]!
='\0'）
{
while（p&&p->ch!
=a[i]）//查找链表中没有该字符或者找到该字符
p=p->next;
if（!
p）//如果没有该字符，创建节点。
{
p=newLNode;
p->ch=a[i];
p->weight=1;
p->next=lroot->next;
lroot->next=p;
Letter++;
}
else
p->weight++;
i++;
p=lroot->next;
};
};
4.选最小值
voidHuffman:
:
SelectMin（int&x,int&y,intbegin,intend）
{
intt1,b,t2;//分别表示临时最小值、对应角标、从b开始比较
t1=troot[begin].weight,b=t2=begin;
for（;b{
if（troot[b].weight{
t1=troot[b].weight;
t2=b;
}
}
x=t2;
troot[x].Parent=100;//临时为该最小的双亲赋值，防止再次被找出
if（t2!
=begin）//判断最小是否是第一个
b=begin;
else
{
b=begin;
while（troot[++b].Parent!
=-1）;
}
t1=troot[b].weight;t2=b;
for（;b{
if（troot[b].weight{
t1=troot[b].weight;
t2=b;
}
}
y=t2;
};
5.倒置字符串
voidHuffman:
:
reverse（charch[]）
{
for（inti=0;i{
chartemp=ch[i];
ch[i]=ch[strlen（ch）-i-1];
ch[strlen（ch）-i-1]=temp;
}
}
6.建立码表，并将信息存在链表
voidHuffman:
:
CreateTable（）
{
LNode*p=lroot;
inti=0,j,k;//将letter个字符都编码，与p相对应
while（p=p->next）
{
j=i,k=0;
while（troot[j].Parent!
=-1）
{
if（troot[troot[j].Parent].Lchild==j）
p->code[k++]='0';
else
p->code[k++]='1';
j=troot[j].Parent;
}
p->code[k]='\0';
reverse（p->code）;
i++;
}
}
7.打印码表和编码结果
voidHuffman:
:
PrintTable（）
{
LNode*p=lroot;
cout<<"字符:
频率:
编码:
\n";
while（p=p->next）
{
cout<ch<<"\t"<weight<<"\t"<code<};
cout<<"原字符编码结果为：
"<}
8.编码
voidHuffman:
:
Encoding（）
{
intk=0;//输入字符串的脚标
LNode*p;
while（astr[k]!
='\0'）//所有字符编码完为止
{
p=lroot;
while（（p=p->next）->ch!
=astr[k]）;//找到字符的码值为止
strcat（bstr,p->code）;
k++;
}
}
9.解码
voidHuffman:
:
Decoding（）
{
cout<<"对码值"<cout<<"编码结果为：
\t";
intk=0,parent=2*Letter-2;
while（bstr[k]!
='\0'）//码值读取结束
{
if（bstr[k]=='0'）
parent=troot[parent].Lchild;
else
parent=troot[parent].Rchild;
if（troot[parent].Lchild==-1）
{
LNode*p=lroot;
for（inti=0;ip=p->next;
cout<ch;
parent=2*Letter-2;
}
k++;
}
cout<}
10.计算压缩结果
voidHuffman:
:
Comrate（）
{
cout<<"编码前大小:
"<cout<<"编码后大小:
"<cout<<"压缩率为:
"<<100*float（strlen（bstr））/strlen（astr）/8<<"%"<}
11.控制
voidHuffman:
:
control（）
{
intm;
while
（1）
{
cout<<"请选择执行功能:
\n";
cout<<"1.打印编码表\n2.原始数据解码\n3.数据大小及压缩率\n4.结束\n\n";
cin>>m;
switch（m）
{
case1:
{
cout<<"打印编码表\n";
PrintTable（）;
break;
}
case2:
{
cout<<"原始数据解码\n";
Decoding（）;
break;
}
case3:
{
cout<<"数据大小及压缩率\n";
Comrate（）;
break;
}
case4:
cout<<"欢迎使用\n";
}
}
};
3.
程序运行结果分析
1.哈夫曼树初始化成功
2．键入测试字符
3．菜单选择所需功能
4.选择1，打印编码表
5.选择2，解码
6.选择3，计算压缩结果
7.选择4，退出
4.总结
4.1实验的难点和关键点
调试出现的问题：
键入的字符为空
解决办法：
用throw和catch语句来排除异常
4.2心得体会
经过这次实验，我了解了哈夫曼树的创建过程，了解了一种不等长编码的方法，用设断点调试的方法更加熟练，同时熟悉了STL中string类型的用法，对C++更加熟悉
升级会员 