一组数据结构七章实验.pptx

例3：设字符集为26个英文字母，其出现频度如下表所示。;提示1：霍夫曼树中各结点的结构可以定义为如下5个分量：;用ht[]数组存放哈夫曼树，对于具有n个叶子结点的哈夫曼树，总共有2n-1个结点。树中每个结点结构如下：

typedefstruct

{ char data; //结点值

float weight; //权重

int parent; //双亲结点

int lchild; //左孩子结点

int rchild; //右孩子结点

}HTNode;;算法思路：

1).n个叶子结点只有data和weight域值，先将所有2n-1个结点的parent、lchild和rchild域置为初值-1。

2).处理每个非叶子结点ht[i]（存放在ht[n]～ht[2n-2]中）：从ht[0]～ht[i-2]中找出根结点（即其parent域为-1）最小的两个结点ht[lnode]和ht[rnode]，将它们作为ht[i]的左右子树，ht[lnode]和ht[rnode]的双亲结点置为ht[i]，并且ht[i].weight=ht[lnode].weight+ht[rnode].weight。

3).如此这样直到所有2n-1个非叶子结点处理完毕。;voidCreateHT(HTNodeht[],intn)

{inti,j,k,lnode,rnode; floatmin1,min2;

for(i=0;i2*n-1;i++)//所有结点的相关域置初值-1

ht[i].parent=ht[i].lchild=ht[i].rchild=-1;

for(i=n;i2*n-1;i++){ //构造哈夫曼树

min1=min2=32767;lnode=rnode=-1;

for(k=0;k=i-1;k++)

if(ht[k].parent==-1){//未构造二叉树的结点中查找

if(ht[k].weightmin1)

{min2=min1;rnode=lnode;

min1=ht[k].weight;lnode=k;}

elseif(ht[k].weightmin2)

{min2=ht[k].weight;rnode=k;}

}//if

ht[lnode].parent=i;ht[rnode].parent=i;

ht[i].weight=ht[lnode].weight+ht[rnode].weight;

ht[i].lchild=lnode;ht[i].rchild=rnode;

}

};No;哈夫曼编码

具体构造方法如下：设需要编码的字符集合为{d1,d2,…,dn}，各个字符在电文中出现的次数集合为{w1,w2,…,wn}，以d1，d2，…，dn作为叶结点，以w1，w2，…，wn作为各根结点到每个叶结点的权值构造一棵二叉树，规定哈夫曼树中的左分支为0，右分支为1，则从根结点到每个叶结点所经过的分支对应的0和1组成的序列便为该结点对应字符的编码。这样的编码称为哈夫曼编码。;29;存放每个结点哈夫曼编码用到以下类型：

typedefstruct

{

charcd[N];//存放当前结点的哈夫曼码

intstart;

}HCode;

;voidCreateHCode(HTNodeht[],HCodehcd[],intn)

{

inti,f,c;HCodehc;

for(i=0;in;i++) //根据哈夫曼树求哈夫曼编码

{hc.start=n;c=i;f=ht[i].parent;

while(f!=-1)//循环直到无双亲结点即到达树根结点

{if(ht[f].lchild==c) //当前结点是左孩子结点

hc.cd[hc.start--]=0;

else //当前结点是双亲结点的右孩子结点

hc.cd[hc.start--]=1;

c=f;f=ht[f].parent;//对双亲结点进行同样的操作

}

hc.start++;//start指向哈夫曼编码最开始字符

hcd[i]=hc;

}

};No