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

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

軟件設(shè)計師案例分析每日一練試題（2025/4/26）在線測試：m.xiexiliangjiufa.com/exam/ExamDayAL.aspx?t1=4&day=2025/4/26

點擊查看：更多軟件設(shè)計師習(xí)題與指導(dǎo)

軟件設(shè)計師案例分析每日一練試題內(nèi)容（2025/4/26）

13、閱讀下列函數(shù)說明和c代碼，將應(yīng)填入  (n)  處的字句寫在答題紙的對應(yīng)欄內(nèi)。
【說明】
函數(shù)int Toplogical(Linded WDipaph  G.的功能是對圖G中的頂點進行拓?fù)渑判?，并返回關(guān)鍵路徑的長度。其中圖G表示一個具有n個頂點的AOE-網(wǎng)，圖中頂點從1～n依次編號，圖G的存儲結(jié)構(gòu)采用鄰接表表示，其數(shù)據(jù)類型定義如下：
typedefstruct Gnode{               /* 鄰接表的表結(jié)點類型*/
iht adjvex;                  /* 鄰接頂點編號*/
iht weight;                 /* 弧上的權(quán)值*/
street Gnode *nextarc;          /* 指示下一個弧的結(jié)點*/
}Gnode;
typedef struct Adjlist{           /* 鄰接表的頭結(jié)點類型*/
char vdata;                  /*頂點的數(shù)據(jù)信息*/
struct Gnode *Firstadj;        /* 指向鄰接表的第一個表結(jié)點*/
}Adjlist;
typedef street LinkedWDigraph{      /* 圖的類型*/
int n, e;                  /* 圖中頂點個數(shù)和邊數(shù)*/
struct Adjlist *head;         /*指向圖中第一個頂點的鄰接表的頭結(jié)點 */
} LinkedWDigraph;
例如，某AOE-網(wǎng)如圖5-1所示，其鄰接表存儲結(jié)構(gòu)如圖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));   /* 存儲網(wǎng)中各頂點的入度*/
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++) { /* 求網(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("%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*/

信管網(wǎng)cnit**************：
1.indegree[j]++ 2.top 3.p-＞adjvex++ 4.!stack[p-＞adjvex] 5.stack