2010年軟件水平考試軟件設(shè)計(jì)師考前練習(xí)題(5)

　　試題4(15分)

　　閱讀下列函數(shù)說(shuō)明和C代碼，將應(yīng)填入(n)處的字句寫(xiě)在答題紙的對(duì)應(yīng)欄內(nèi)。

　　【說(shuō)明】函數(shù)int Toplogical (LinkedWDigraph G)的功能是對(duì)圖G中的頂點(diǎn)進(jìn)行拓?fù)渑判颍�并返回關(guān)鍵路徑的長(zhǎng)度。其中圖G表示一個(gè)具有n個(gè)頂點(diǎn)的AOE-網(wǎng)，圖中頂點(diǎn)從1～n依次編號(hào)，圖G的存儲(chǔ)結(jié)構(gòu)采用鄰接表表示，其數(shù)據(jù)類(lèi)型定義如下：

　　typedef struct Gnode{ /*鄰接表的表結(jié)點(diǎn)類(lèi)型*/

　　int adjvex; /*鄰接頂點(diǎn)編號(hào)*/

　　int weight; /*弧上的權(quán)值*/

　　struct Gonde*nextare;　 /*指示下一個(gè)弧的結(jié)點(diǎn)*/

　　} Gnode;

　　typedef struct Adjlist{ 　 /*鄰接表的頭結(jié)點(diǎn)類(lèi)型*/

　　char vdata;　 /*頂點(diǎn)的數(shù)據(jù)信息*/

　　struct Gnode*Firstadj;　 /*指向鄰接表的第1個(gè)表結(jié)點(diǎn)*/

　　} Adjlist;

　　typedef struct LinkedWDigraph{ /*圖的類(lèi)型*/

　　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)的編號(hào)*/

　　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)并保存其編號(hào)*/

　　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*/