数据结构哈夫曼树C++实现.doc

实 验 报 告
一、 实验目的
1. 掌握哈夫曼树的基本概念及所用的存储结构。
2. 掌握哈夫曼树的建立算法。
3. 掌握哈夫曼树的应用（哈夫曼树的编码和译码）。
二、 实验内容
给定权值5、29、7、8、14、23、3、11，建立哈夫曼树，输出哈夫曼编码。对上述给定的哈夫曼树及得到的哈夫曼编码，试输入一串二进制编码，输出它的哈夫曼译码。
三、 实验与算法分析
建立哈夫曼树，将哈夫曼树的机构定义为一个结构型的一维数组每个元素含有四项：权值、双亲、左孩子、右孩子。给定的权值可以从键盘输入，要输出所建立的哈夫曼树，只要输出表示哈夫曼树的一维数组中的全部元素即可。
要实现哈夫曼编码，只要在所建立的哈夫曼树上进行二进制编码：往左走，编码为0，往右走编码为1，然后将从根结点到树叶中的所有0,1排列起来，则得到该树叶的哈夫曼编码。哈夫曼编码可以用一个结构型的一维数组保存，每个元素包含：编码，编码的开始位置，编码所对应的字符三项。
哈夫曼译码，就是将输入的译码还原成对应的字符。
抽象的算法描述：将建立哈夫曼树、实现哈夫曼编码、哈夫曼译码都定义成子函数的的形式，然后在主函数中调用它们。哈夫曼树的构造：假设有n个权值，则构造出的有n个叶子结点。n个权值分别设为w1,w2,……,wn，则哈夫曼树的构造规则为：（1）将w1,w2,……,wn看成是有n棵树的森林（每棵树仅有一个结点）；（2）在森林中选出两个根结点的权值最小的树合并，作为一棵新树的左右子树，且新树的根结点权值为其左右子树的根结点的权值之；（3）从森林中删除选取的两棵树，并将新树加入森林。（4）重复（2）、（3）步，直到森林中只剩一棵树为止，该树即为我们所求得的哈夫曼树。
四、 可执行程序及注释
实验代码
#include<iostream.h>
#include<iomanip.h>
const int n=8; //maxn表示叶子数目
const int m=2*n-1; //m为森林中树的棵数
struct tree //哈夫曼树中的一个结点
{
float weight; //权值
int parent; //双亲
int lch,rch; //左孩子、右孩子
};
struct codetype //哈弗曼编码
{
int bits[n+1]; //哈弗曼编码
int start; //编码的存放位置
char ch; //所对应的字符
};
tree hftree[m+1];
codetype code[n+1];
void creathuffmantree() //建立哈夫曼树
{
int i,j,p1,p2;
float s1,s2;
for(i=1;i<=m;i++)
{
hftree[i].parent=0;
hftree[i].lch=0;
hftree[i].rch=0;
hftree[i].weight=0;
}
cout<<"请输入"<<n<<"个权值"<<endl;
for(i=1;i<=n;i++)
cin>>hftree[i].weight; //输入权值
for(i=n+1;i<=m;i++) //进行次合并
{
p1=p2=0; //p1,p2分别指向两个权值最小的值的位置
s1=s2=32767; //s1,s2代表两个最小权值
for(j=1;j<=i-1;j++) //选两个最小值
if(hftree[j].parent==0) //该权值还没有选中
if(hftree[j].weight<s1)
{
s2=s1;
s1=hftree[j].weight;
p2=p1;
p1=j;
}
else if(hftree[j].weight<s2)
{s2=hftree[j].weight;p2=j;}
//以下为合并
hftree[p1].parent=i;
hftree[p2].parent=i;
hftree[i].lch=p1;
hftree[i].rch=p2;
hftree[i].weight=hftree[p1].weight+hftree[p2].weight;
}
}
void huffcode() //哈弗曼编码
{
codetype cd;
int c,p;
for(int i=1;i<=n;i++)
{
cd.start=n+1;
cd.ch=96+i; //第一个树叶对应字母a，其余依此类推
c=i;
p=hftree[i].parent;
while(p!=0)
{
cd.start--;
if(hftree[p].lch==c)
cd.bits[cd.start]=0;
else
cd.bits[cd.start]=1;
c=p;
p=hftree[p].parent;
}
code[i]=cd;
}
for(i=1;i<=n;i++)
{
cout<<"字符"<<code[i].ch<<"的权值为："<<hftree[i].weight<<setw(5)<<"编码为：";
for(int j=code[i].start;j<=n;j++)
cout<<code[i].bits[j]<<" ";
cout<<endl;
}
}
void trancode() //哈弗曼译码
{
int i=m;
char b;
cout<<"请输入一串二进制编码（0、1以外的数结束）"<<endl;
cin>>b;
while((b=='0')||(b=='1'))
{
if(b=='0')
i=hftree[i].lch;
else
i=hftree[i].rch;
if(hftree[i].lch==0)
{
cout<<code[i].ch;
i=m;
}
cin>>b;
}
}
void main()
{
creathuffmantree(); //建立哈夫曼树
huffcode(); //实现哈弗曼编码
trancode(); //进行哈弗曼译码
cout<<endl;
}

五、 实验小结