采用静态链表作存储结构,设置一个大小为2n-1的数组,令数组每个元素由四个域组成:wt是结点的权值;lchild、rchild分别为结点的左、右孩子在数组中的下标;parent是结点的双亲在数组中的下标。其数组元素类型定义如下:
typedef struct
{
float wt; /*权值*/
int parent, lchild rchild; /*指针域*/
} node;
typedef node hftree[2*n-1];
在这种存储结构上所建的哈夫曼树算法如下,请在括号内填充适当的语句,使其完整。
void Huffman(int k,float W[k],hftree T) /*求给定权值W的哈夫曼树T*/
{
int i,j, x, y;
float m,n;
for(i=0; i<2*k-1;i++)
{
T[i].parent=-1; T[i].lchild=-1; T[i]rchild=-1;
if (i<k)
T[i].wt=W[i];
else
T[i].wt=0;
}
for (i=0; i<k-1; i++)
{
x=0; y=0;m=maxint;n=maxint;
for(j=0; j<=k+i; j++)
if ((T[j].wt<m)&&(T[j].parent==-1))
{n=m;y=( ① );m=( ② ) ;x=j;}
else if ((T[j].wt<n)&&(T[j].parint==-1))
{n=T[j].wt; y=j; }
T[x].parent=( ③ ) ;T[y].parent=( ④ ) ;
T[k+i].wt=( ⑤ ) ;
T[k+i].lchild=( ⑥ ) ;T[k+i].rchild=y;
}
}
