北邮数据结构实验报告三题目2哈夫曼树Word格式文档下载.docx
《北邮数据结构实验报告三题目2哈夫曼树Word格式文档下载.docx》由会员分享，可在线阅读，更多相关《北邮数据结构实验报告三题目2哈夫曼树Word格式文档下载.docx（16页珍藏版）》请在冰点文库上搜索。
//字符
intweight;
//权值
charcode[20];
//字符编码
LNode*next;
//指向下一个节点
};
structTNode//哈弗曼树结点的结构体
//结点权值
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<
<
"
请输入一串字符，以回车键结束"
endl;
cin.getline（astr,1000,'
\n'
）;
if（strlen（astr）==0）throw1;
else
{
List（astr）;
//用链表存储每个字符
HTree（）;
CreateTable（）;
Encoding（）;
}
~Huffman（）
deletetroot;
LNode*p=lroot;
while（p=lroot->
next）
lroot=p->
next;
deletep;
p=lroot;
deletep;
2.建立哈夫曼树
voidHuffman:
HTree（）
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<
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.统计字符的频率
List（chara[]）
LNode*p=lroot;
inti=0;
while（a[i]!
='
）
while（p&
&
p->
ch!
=a[i]）//查找链表中没有该字符或者找到该字符
p=p->
if（!
p）//如果没有该字符，创建节点。
{
p=newLNode;
p->
ch=a[i];
weight=1;
next=lroot->
lroot->
next=p;
Letter++;
}
else
weight++;
i++;
p=lroot->
4.选最小值
SelectMin（int&
y,intbegin,intend）
{
intt1,b,t2;
//分别表示临时最小值、对应角标、从b开始比较
t1=troot[begin].weight,b=t2=begin;
for（;
b<
end;
b++）
if（troot[b].weight<
t1&
troot[b].Parent==-1）
t1=troot[b].weight;
t2=b;
x=t2;
troot[x].Parent=100;
//临时为该最小的双亲赋值，防止再次被找出
if（t2!
=begin）//判断最小是否是第一个
b=begin;
while（troot[++b].Parent!
=-1）;
t1=troot[b].weight;
t2=b;
y=t2;
5.倒置字符串
reverse（charch[]）
for（inti=0;
strlen（ch）/2;
chartemp=ch[i];
ch[i]=ch[strlen（ch）-i-1];
ch[strlen（ch）-i-1]=temp;
}
6.建立码表，并将信息存在链表
CreateTable（）
inti=0,j,k;
//将letter个字符都编码，与p相对应
j=i,k=0;
while（troot[j].Parent!
if（troot[troot[j].Parent].Lchild==j）
p->
code[k++]='
0'
else
1'
j=troot[j].Parent;
p->
code[k]='
reverse（p->
code）;
7.打印码表和编码结果
PrintTable（）
字符:
频率:
编码:
\n"
cout<
ch<
\t"
weight<
code<
原字符编码结果为：
bstr<
8.编码
Encoding（）
intk=0;
//输入字符串的脚标
LNode*p;
while（astr[k]!
）//所有字符编码完为止
while（（p=p->
next）->
=astr[k]）;
//找到字符的码值为止
strcat（bstr,p->
k++;
9.解码
Decoding（）
对码值"
进行解码……"
编码结果为：
intk=0,parent=2*Letter-2;
while（bstr[k]!
）//码值读取结束
if（bstr[k]=='
）
parent=troot[parent].Lchild;
else
parent=troot[parent].Rchild;
if（troot[parent].Lchild==-1）
LNode*p=lroot;
for（inti=0;
parent+1;
p=p->
cout<
ch;
parent=2*Letter-2;
10.计算压缩结果
Comrate（）
编码前大小:
"
strlen（astr）*8<
bit\n"
编码后大小:
strlen（bstr）<
压缩率为:
100*float（strlen（bstr））/strlen（astr）/8<
%"
11.控制
control（）
intm;
while
（1）
请选择执行功能:
1.打印编码表\n2.原始数据解码\n3.数据大小及压缩率\n4.结束\n\n"
cin>
>
m;
switch（m）
case1:
{
cout<
打印编码表\n"
PrintTable（）;
break;
}
case2:
原始数据解码\n"
Decoding（）;
case3:
数据大小及压缩率\n"
Comrate（）;
case4:
欢迎使用\n"
3.
程序运行结果分析
1.哈夫曼树初始化成功
2．键入测试字符
3．菜单选择所需功能
4.选择1，打印编码表
5.选择2，解码
6.选择3，计算压缩结果
7.选择4，退出
4.总结
4.1实验的难点和关键点
调试出现的问题：
键入的字符为空
解决办法：
用throw和catch语句来排除异常
4.2心得体会
经过这次实验，我了解了哈夫曼树的创建过程，了解了一种不等长编码的方法，用设断点调试的方法更加熟练，同时熟悉了STL中string类型的用法，对C++更加熟悉
升级会员 