实验五哈夫曼树的建立、编码、解码.pdfVIP

成绩

实验五

实验题目：哈夫曼树的应用

一、实验目的

•加深理解哈夫曼树的定义和特性；

•掌握哈夫曼树的存储结构与实现；

•掌握哈夫曼树的应用

二、实验内容

•根据输入的权值信息建立哈夫曼树

•输出各个叶子结点所表示字符的哈夫曼编码

•对给定的密码串进行解码

三、设计与编码

1、基本思想

2、编码

#includeiostream.h

#includestring.h

constintMAX20;

structhuffnode

{

intweight;

intlchild,rchild,parent;

};

structhuffinit//输入的权值信息的结构

{

chardata;

intweight;

};

structhuffcode//哈夫曼树编码的结构

{

chardata;

charcode[MAX+1];

};

classHuffTree//哈夫曼树类的声明

{public:

HuffTree(huffinitw[],intn);

~HuffTree(){}

voidSelect(intmin1,intmin2,intm);

voidOutput();//tree

输出哈夫曼树最终状态（数组）

voidEncode();//编码

voidDecode(charcode[]);//解码

private:

huffnodetree[2*MAX-1];//存储哈夫曼树

huffcodecd[MAX];//存储各个哈夫曼编码

intsize;//哈夫曼树的叶子结点数

};

HuffTree::HuffTree(huffinitw[],intn)

{

sizen;

for(inti0;i2*n-1;i++)

{

tree[i].parent-1;

tree[i].lchild-1;

tree[i].rchild-1;

}

for(i0;in;i++)

{tree[i].weightw[i].weight;

cd[i].dataw[i].data;}

intmin1-1;

intmin2-1;

intmsize;

for(intkn;k2*n-1;k++)

{

Select(min1,min2,m);

tree[min1].parentk;

tree[min2].parentk;

tree[k].weighttree[min1].weight+tree[min2].weight;

tree[k].lchildmin1;

tree[k].rchildmin2;

m++;

}

}

voidHuffTree::Select(intmin1,intmin2,intm)//选择两个权值最小的结点

{

inta100;

intb100;

for(inti0;im;i++)

{

if(tree[i].weightatree[i].parent-1)

{

atree[i].weight;