北邮数据结构上机实验哈夫曼树.doc
《北邮数据结构上机实验哈夫曼树.doc》由会员分享，可在线阅读，更多相关《北邮数据结构上机实验哈夫曼树.doc（16页珍藏版）》请在冰点文库上搜索。
北邮数据结构上机实验-哈夫曼树
/*2.2题目2——应用实验
利用二叉树结构实现哈夫曼编/解码器。
基本要求：
1、初始化（Init）：
能够对输入的任意长度的字符串s进行统计，统计每个字符的频度，并建立哈夫曼树
2、建立编码表（CreateTable）：
利用已经建好的哈夫曼树进行编码，并将每个字符的编码输出。
3、编码（Encoding）：
根据编码表对输入的字符串进行编码，并将编码后的字符串输出。
4、译码（Decoding）：
利用已经建好的哈夫曼树对编码后的字符串进行译码，并输出译码结果。
5、打印（Print）：
以直观的方式打印哈夫曼树（选作）
6、计算输入的字符串编码前和编码后的长度，并进行分析，讨论赫夫曼编码的压缩效果。
7、可采用二进制编码方式（选作）
测试数据：
IlovedataStructure,IloveComputer。
IwilltrymybesttostudydataStructure.
提示：
1、用户界面可以设计为“菜单”方式：
能够进行交互。
2、根据输入的字符串中每个字符出现的次数统计频度，对没有出现的
字符一律不用编码。
3代码要求
1、必须要有异常处理，比如删除空链表时需要抛出异常；
2、保持良好的编程的风格：
?
代码段与段之间要有空行和缩近
?
标识符名称应该与其代表的意义一致
?
函数名之前应该添加注释说明该函数的功能
?
关键代码应说明其功能
3、递归程序注意调用的过程，防止栈溢?
*/
#include
#include
#include
usingnamespacestd;
//静态三叉链表，用于存储哈夫曼树
structhnode
{
charss;//结点代表的字符
intweight;//结点的权重
intparent;//双亲指针
intlchild;//左孩子指针
intrchild;//右孩子指针
};
//哈夫曼编码表
structhcode
{
chardata;//存储字符
charcode[100];//存储字符编码
};
//huffman类
classhuffman
{
private:
hnode*htree;//哈夫曼树动态数组的指针，huffman树
hcode*hcodetable;//哈夫曼树的编码数组指针,huffman编码表
inthn;//存储哈夫曼数组的大小
public:
voidInit（char*s）;//初始化哈夫曼树
voidcreatehuffman（）;//创建哈夫曼树
voidselectmin（int&x,int&y,inti）;//寻找权重最小的两个数
voidcreatecodetable（）;//创建哈夫曼编码表
voidreverse（charm[]）;//逆置编码字符，颠倒
voidencode（char*s,string*d）;//编码
voiddecode（char*s,char*d）;//解码
voidprinttable（）;//打印哈夫曼树
~huffman（）{
delete[]htree;
delete[]hcodetable;
}//析构函数
};
//初始化
voidhuffman:
:
Init（char*s）
{
intn=0;
while（*（s+n）!
='\0'）//统计字符串字符数
{
n++;
}
char*m=newchar[n];//动态字符数组存储字符串
for（inti=0;i{
m[i]=*（s+i）;
}
chartemp;
for（inti=0;i{
for（intj=0;j{
if（m[j]>m[j+1]）
{
temp=m[j];
m[j]=m[j+1];
m[j+1]=temp;
}
}
}
intk=1;
for（inti=1;i{
if（m[i]!
=m[i-1]）
{
k++;
}
}
htree=newhnode[2*k-1];
hn=2*k-1;
intl=0;//统计不同字符出现的频度
k=0;//哈夫曼数组下标
temp=m[0];//标记？
for（inti=0;i{
if（m[i]==temp）
{
l++;//统计出现次数
if（i==n-1）
htree[k].weight=l;
}
else
{
htree[k].weight=l;
htree[k].ss=temp;
temp=m[i];
k++;
l=1;
htree[k].ss=temp;
htree[k].weight=l;
}
}
delete[]m;//释放动态内存空间
createhuffman（）;//创建哈夫曼树
createcodetable（）;//创建哈夫曼编码表
}
//创建哈夫曼树
voidhuffman:
:
createhuffman（）
{
intn=（hn+1）/2;//n表示不同字符的个数
for（inti=0;i{
htree[i].lchild=-1;
htree[i].rchild=-1;
htree[i].parent=-1;
}
intx,y;
for（inti=n;i<2*n-1;i++）
{
selectmin（x,y,i）;//找出权重最小的两个字符
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;
}
}
//寻找权重最小的两个字符
voidhuffman:
:
selectmin（int&x,int&y,inti）
{
x=0;
while（htree[x].parent!
=-1）
{
x++;
}
for（intj=1;j{
if（htree[j].parent!
=-1）
{
continue;//如果是之前找过的最小值，跳出本次循环
}
x=（htree[x].weight<=htree[j].weight）?
x:
j;
}
htree[x].parent=-2;//防止重复
y=0;
while（htree[y].parent!
=-1）
{
y++;
}
for（intj=1;j{
if（htree[j].parent!
=-1）
{
continue;
}
y=（htree[y].weight<=htree[j].weight）?
y:
j;
}
}
//创建哈夫曼表
voidhuffman:
:
createcodetable（）
{
intn=（hn+1）/2;
hcodetable=newhcode[n];//存储不同字符代表的编码
for（inti=0;i{
hcodetable[i].data=htree[i].ss;//存储字符
intchild=i;
intparent=htree[i].parent;
intk=0;
while（parent!
=-1）//自下而上到达根节点之后结束循环
{
if（child==htree[parent].lchild）//左孩子编码'0'
hcodetable[i].code[k]='0';
else//右孩子编码'1'
hcodetable[i].code[k]='1';
k++;
child=parent;
parent=htree[child].parent;
}
hcodetable[i].code[k]='\0';//字符编码串最后添加结束符
reverse（hcodetable[i].code）;//颠倒字符串
}
}
//颠倒字符串
voidhuffman:
:
reverse（charm[]）
{
intn=0;
chartemp;
while（m[n+1]!
='\0'）
n++;
for（inti=0;i<=n/2;i++）
{
temp=m[i];
m[i]=m[n-i];
m[n-i]=temp;
}
}
//编码
voidhuffman:
:
encode（char*s,string*d）
{
floatsum=0;//统计字节数
intn=0;
while（*s!
='\0'）
{
for（inti=0;i<（hn+1）/2;i++）
{
if（*s==htree[i].ss）
{
for（intj=0;hcodetable[i].code[j]!
='\0';j++）
{
*d+=hcodetable[i].code[j];
sum+=1;
}
s++;
n++;
break;
}
}
}
cout<<"编码前长度：
"<<8*n<cout<<"编码后的长度：
"<cout<<"压缩比为：
"<<8*n/sum<}
//解码函数
voidhuffman:
:
decode（char*s,char*d）
{
while（*s!
='\0'）
{
intparent=hn-1;//根节点
while（htree[parent].lchild!
=-1）//从根节点开始到终端节点结束循环
{
if（*s=='0'）
parent=htree[parent].lchild;
else
parent=htree[parent].rchild;
if（*s=='\0'）//不解码码串最尾部，无编码部分
{
cout<"<return;
}
s++;
}
*d=hcodetable[parent].data;
d++;
}
}
//打印哈夫曼树
voidhuffman:
:
printtable（）
{
cout<:
left）<setw（12）<<"rchild"<for（inti=0;i{
if（i<（hn+1）/2）
{
cout<:
left）<setw（12）<}
else
{
cout<:
left）<setw（12）<}
}
}
//主函数
intmain（）
{
charm;
char*ce="IlovedataStructure.IloveComputer.IwilltrymybesttostudydataStructure.";//测试数据
cout<<"************菜单************"<cout<<"请选择：
a.测试；"<cout<<"b.进入交互界面。
"<cin>>m;
while（m!
='\n'）
{
if（m=='a'）//测试
{
cout<<"测试数据为：
IlovedataStructure,IloveComputer.IwilltrymybesttostudydataStructure."<huffmanh1;
h1.Init（ce）;
cout<<"打印哈夫曼表：
"<h1.printtable（）;
strings1="";
h1.encode（ce,&s1）;
cout<<"编码后的字符串：
"<cout<ints1count=s1.length（）;
charstr1[10000]={'\0'};
char*sce=&str1[0];
s1.copy（str1,s1count,0）;
charhce[10000]={'\0'};
char*dce=&hce[0];
h1.decode（sce,dce）;
cout<<"解码后的字符串：
"<cout<cout<<"请选择：
a.测试；"<cout<<"b.进入交互界面。
"<cin>>m;
}
else
{
if（m=='b'）//交互，由用户输入数据
{
cout<<"*******************************"<cout<<"进入交互界面！
"<cout<<"请输入字符串：
"<charq;
cin.get（q）;
charstr[1000]={'\0'};
char*s=&str[0];
charc;//输入的单个字符
inti=0;
boolflag=0;//判断不同字符的个数是否大于等于2
while（cin.get（c））
{
if（c=='\n'）
{
升级会员 