首页 > 试题广场 >

程序填空

[问答题]

采用静态链表作存储结构,设置一个大小为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;
    }
}

这道题你会答吗?花几分钟告诉大家答案吧!