軟件設計師案例分析當天每日一練試題地址：m.xiexiliangjiufa.com/exam/ExamDayAL.aspx?t1=4

往期軟件設計師每日一練試題匯總：m.xiexiliangjiufa.com/class/27/e4_1.html

軟件設計師案例分析每日一練試題（2022/10/12）在線測試：m.xiexiliangjiufa.com/exam/ExamDayAL.aspx?t1=4&day=2022/10/12

點擊查看：更多軟件設計師習題與指導

軟件設計師案例分析每日一練試題內容（2022/10/12）

13、閱讀下列函數(shù)說明和c代碼，將應填入  (n)  處的字句寫在答題紙的對應欄內。
【說明】
函數(shù)int Toplogical(Linded WDipaph  G.的功能是對圖G中的頂點進行拓撲排序，并返回關鍵路徑的長度。其中圖G表示一個具有n個頂點的AOE-網，圖中頂點從1～n依次編號，圖G的存儲結構采用鄰接表表示，其數(shù)據類型定義如下：
typedefstruct Gnode{               /* 鄰接表的表結點類型*/
iht adjvex;                  /* 鄰接頂點編號*/
iht weight;                 /* 弧上的權值*/
street Gnode *nextarc;          /* 指示下一個弧的結點*/
}Gnode;
typedef struct Adjlist{           /* 鄰接表的頭結點類型*/
char vdata;                  /*頂點的數(shù)據信息*/
struct Gnode *Firstadj;        /* 指向鄰接表的第一個表結點*/
}Adjlist;
typedef street LinkedWDigraph{      /* 圖的類型*/
int n, e;                  /* 圖中頂點個數(shù)和邊數(shù)*/
struct Adjlist *head;         /*指向圖中第一個頂點的鄰接表的頭結點 */
} LinkedWDigraph;
例如，某AOE-網如圖5-1所示，其鄰接表存儲結構如圖5-2所示。

【函數(shù)】
iht Toplogical(LinkedWDigraph G.
{ Gnode *p;
intj, w, top = 0;
iht *Stack, *ye, *indegree;
ye = (int *)malloe((G.n+1) * sizeof(int));
indegree = (int *)malloc((G.n+1)*sizeof(int));   /* 存儲網中各頂點的入度*/
Stack = (int *)malloe((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++) { /* 求網中各頂點的入度*/
p = G.head[j].Firstadj;
while (p) {
(1)  ;  p = p→nextarc;
}/*while*/
}/*for*/
for (j = 1; j ＜= G.n; j++)                  /*求網中入度為0的頂點并保存其編號*/
if (!indegree[j])     Stack[++top] =j;
while (top ＞ 0) {
w=   (2)  ;
printf("%e  ", G.head[w].vdata);
p = G.head[w].Firstadj;
while (p) {
(3)   ;
if ( !indegree [p→adjvex])
Staek[++top] = p→adjvex;
if(   (4)  )
ve[p→adjvex] = ve[w] + p→weight;
p = p→nextarc;
}/* while */
}/* while */ return   (5)   ; }/*Toplogieal*/