試題4(15分)
閱讀下列函數(shù)說明和C代碼，將應(yīng)填入(n)處的字句寫在答題紙的對應(yīng)欄內(nèi)。
【說明】函數(shù)int Toplogical (LinkedWDigraph G)的功能是對圖G中的頂點(diǎn)進(jìn)行拓?fù)渑判?，并返回關(guān)鍵路徑的長度。其中圖G表示一個(gè)具有n個(gè)頂點(diǎn)的AOE-網(wǎng)，圖中頂點(diǎn)從1～n依次編號，圖G的存儲(chǔ)結(jié)構(gòu)采用鄰接表表示，其數(shù)據(jù)類型定義如下：
typedef struct Gnode{ /*鄰接表的表結(jié)點(diǎn)類型*/
int adjvex; /*鄰接頂點(diǎn)編號*/
int weight; /*弧上的權(quán)值*/
struct Gonde*nextare; /*指示下一個(gè)弧的結(jié)點(diǎn)*/
} Gnode;
typedef struct Adjlist{ /*鄰接表的頭結(jié)點(diǎn)類型*/
char vdata; /*頂點(diǎn)的數(shù)據(jù)信息*/
struct Gnode*Firstadj; /*指向鄰接表的第1個(gè)表結(jié)點(diǎn)*/
} Adjlist;
typedef struct LinkedWDigraph{ /*圖的類型*/
int n ,e; /*圖中頂點(diǎn)個(gè)數(shù)和邊數(shù)*/
struct Adjlist head; /*指向圖中第1個(gè)頂點(diǎn)的鄰接表的頭結(jié)點(diǎn)*/
} LinkedWDigraph;
【函數(shù)】
int Toplogical(LinkedWDigraph G)
{ Gnode *p;
int j,w,top=0;
int *Stack,*ve,*indegree;
ve=(int *)mallloc(G.n+1)*sizeof(int)};
indegree=(int *)malloc((G.n+1)*sizeof(int)); /*存儲(chǔ)網(wǎng)中個(gè)頂點(diǎn)的入度*/
Stack=(int *)malloc((G.n+1)*sizeof(int)); /*存儲(chǔ)入度為0的頂點(diǎn)的編號*/
if (!ve || !indegree || !Stack)
exit(0);
for (j=1;j<=G.n;j++){
ve[j]=0; indegree[j]=0;
}/*for*/
for (j=1;j<=G.n;j++) { /*求網(wǎng)中各頂點(diǎn)的入度*/
p=G.head[j].Firstadj;
while (p) {
(1) ; p=p->nextarc;
} /*while*/
} /*for*/
for (j=1;j<=G.n;j++) /求網(wǎng)中入度為0的頂點(diǎn)并保存其編號*/
if (!indegree[j]) Stack[++top]=j;
while (top>0){
w= (2) ;
printf(“%c”,G.head[w].vdata);
p=G.head[w].Firstadj;
while (p) {
(3) ;
if (!indegree[p->adjvex])
Stack[++top]=p->adjvex;
if( (4) )
ve[p->adjvex]=ve[w]+p->weight;
p=p->nextarc;
}/*while*/
return (5) ;
} /*Toplogical*/