2010年軟件水平考試軟件設計師考前練習題(5)

　　試題4(15分)

　　閱讀下列函數(shù)說明和C代碼，將應填入(n)處的字句寫在答題紙的對應欄內。

　　【說明】函數(shù)int Toplogical (LinkedWDigraph G)的功能是對圖G中的頂點進行拓撲排序，并返回關鍵路徑的長度。其中圖G表示一個具有n個頂點的AOE-網(wǎng)，圖中頂點從1～n依次編號，圖G的存儲結構采用鄰接表表示，其數(shù)據(jù)類型定義如下：

　　typedef struct Gnode{ /*鄰接表的表結點類型*/

　　int adjvex; /*鄰接頂點編號*/

　　int weight; /*弧上的權值*/

　　struct Gonde*nextare;　 /*指示下一個弧的結點*/

　　} Gnode;

　　typedef struct Adjlist{ 　 /*鄰接表的頭結點類型*/

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

　　struct Gnode*Firstadj;　 /*指向鄰接表的第1個表結點*/

　　} Adjlist;

　　typedef struct LinkedWDigraph{ /*圖的類型*/

　　int n ,e;　 /*圖中頂點個數(shù)和邊數(shù)*/

　　struct Adjlist head; /*指向圖中第1個頂點的鄰接表的頭結點*/

　　} 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)); /*存儲網(wǎng)中個頂點的入度*/

　　Stack=(int *)malloc((G.n+1)*sizeof(int)); /*存儲入度為0的頂點的編號*/

　　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)中各頂點的入度*/

　　p=G.head[j].Firstadj;

　　while (p) {

　　(1) ; p=p->nextarc;

　　} /*while*/

　　} /*for*/

　　for (j=1;j<=G.n;j++) /求網(wǎng)中入度為0的頂點并保存其編號*/

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