阅读下列C程序和程序说明,将应填入(n)处的字句写在答题纸的对应栏内。【说明】用克鲁斯卡尔算法求解

Question

阅读下列C程序和程序说明，将应填入(n)处的字句写在答题纸的对应栏内。

【说明】用克鲁斯卡尔算法求解给定图的最小生成树。

include ＜stdio. h＞

include ＜stdlib. h＞

define MAXN 30

typedef struct

{ int v1,v2; /*一条边依附的两个顶点*/

int weight; /*边上的权值*/

}EDGE;

typedef struct

{ int Vnum; /*图中的顶点数目*/

EDGE e[MAXN*(MAXN-1)/2]; /*图中的边*/

}Graph;

typedef struct node{ /*用链表存储同一个连通分量的顶点*/

int v;

struct node *next;

}Alist;

void heapadjust(EDGE data[], int s, int m)

{ /*将元素序列data[s..m]调整为小顶堆, 堆顶元素(最小元素)为data[s]*/

int j;

EDGE t;

t=data[s]; /*备份元素data[s], 为其找到适当位置后再插入*/

for(j=2*s+1; j＜=m; j=j*2+1){/*沿值较小的子结点向下筛选*/

if(j＜m &&(1)) ++j;

if(!(t. weight＞data[j]. weight)) break;

data[s]=data[j];s=j; /*用s记录待插入元素的位置(下标)*/

}/*for*/

data[s]=t; /*将备份元素插入由s所指出的插入位置*/

}/*heapadjust*/

int creat_graph(Graph *p) /*输入图中的顶点及边, 返回图中边的数目*/

{ int k=0; /*记录图中边的数目*/

int n;

int v1,v2;

int w;

printf("vertex number of the graph:");

scanf("%d", &n); /*输入图中的顶点数目*/

if(n＜1) return 0;

p-＞Vnum=n;

do{ printf("edge(vertex1,vertex2,weight):");

scanf("%d %d %d", &V1, &v2, &w);

if(v1＞=0 && v1＜n && v2＞=0 && v2＜n){

p-＞e[k]. v1=v1; p-＞e[k]. v2=v2; p-＞e[k]. weight=w;

k++;

}/*if*/

}while(!( (2) ));

return k; /*返回图中边的数目*/

}/*creat_graph*/

int kruskal(Graph G, int enumber, int tree[][3])

{ /*用kruskal算法求无向连通图G的最小生成树, 图中边所得数目为enumber, */

/*数组tree[][3]中存放生成树中边的顶点和边上的权值, 函数返回生成树的代价*/

int i, k, m, c=0;

int v1, v2;

Alist *p, *q, *a[MAXN];

for(i=0; i＜G．Vnum; ++i){ /*将每个连通分量中的顶点存放在一个单链表中*/

a[i]=(Alist*)malloc(sizeof(Alist));

if(!a[i]) {

printf("\n mernory allocation error!");

exit(0);

}/*if*/

a[i]-＞v=i; a[i]-＞next=NULL;

}/*for*/

for(i=enumber-1; i＞=0; --i)/*按照边上的权值建立小顶堆*/

heapadjust( (3) );

k=G. Vnum; /*k用于计算图中的连通分量数目*/

m=enumber-1;

i=0;

do{

v1=G. e[0]. v1; v2=G. e[0]. v2;

p=a[v1];

while(p && p-＞v!=v2){ /*判断当前选择的边的顶点是否在一个连通分量中*/

q=p; p=p-＞next;

}

if(!p){ /*当前边的顶点不在一个连通分量中*/

p=q;

p-＞next=a[G. e[0]. v2];

&nb

Answer 1

正确答案：(1) data[j].weight＞data[j+1].weight (2) v1==-1 && v2==-1 (3) G.eienumber-1 (4) a[G.e[0].v1] (5) G.e0m
(1) data[j].weight＞data[j+1].weight (2) v1==-1 && v2==-1 (3) G.e，i，enumber-1 (4) a[G.e[0].v1] (5) G.e,0,m 解析：(1) data[j].weight＞data[j+1].weight
沿值较小的子结点向下筛选，建堆，堆顶元素最小；
(2) v1==-1 && v2==-1
当v1!=-1||v2!=-1时，循环读入，直到v1==-1 && v2==-1为真。
(3) G.e，i，enumber-1
按照边上的权值建立小顶堆。
(4) a[G.e[0].v1]
加入边(v1,v2)，将两个连通分量合并为一个。
(5) G.e,0,m
找出下一条权值最小的边。