【正文】 ptime = t。 pend = j+65。 p = new ArcNode。 k++) { cout第k項：。 for( k = 1。 gadjlist[i]. = gadjlist[i]. = 0。 gadjlist[i].firstarc = NULL。 i n。 ge = e。 } } while (!sign)。 if ((n == 0) || (e n1)) { cout數(shù)據(jù)有誤，請檢查后重新輸入!endl。 do { sign = 1。 int i, j, k, n, e, t, sign。 //鄰接鏈表}ALGraph。typedef struct{ int n, e。 //該頂點的相關(guān)信息 ArcNode *firstarc。 //指向下一條弧的指針 }ArcNode。 //該弧所代表的活動的最遲開始時間 int d。 //完成該弧所表示的活動所需的時間 int e。 //該弧的終點，表示此弧所代表的活動的結(jié)束事件 int vp。typedef struct arode//弧的結(jié)點結(jié)構(gòu)類型{ char start。 //頂點所表示的事件的最早發(fā)生時間 int vl。 //頂點出度 int in_d?！?找出關(guān)鍵活動和關(guān)鍵路徑 詳細設(shè)計： 數(shù)據(jù)結(jié)構(gòu)： typedef struct//頂點類型{ char num?！粲嬎愠龈魇录盎顒拥牡南嚓P(guān)信息：如每個事件的最早和最遲開始時間，每項活動的最早最遲開始時間以及完成此活動所需的時間◆輸出工程圖的相關(guān)信息：用戶可根據(jù)自己需要查看相關(guān)信息◆拓撲排序：以此來判斷圖中是否有回路，因為圖中如果有回路，工程就無法進行◆找出關(guān)鍵活動并輸出◆找出關(guān)鍵路徑并輸出概要設(shè)計： 相關(guān)說明：設(shè)某一活動的起點為i, 中點為j，完成該活動所需時間為time。總的來說，正因為關(guān)鍵路徑可以幫助我們對工程進行非常有必要的估算，讓我們得以看清全局，作出更為優(yōu)化的安排，所以可見關(guān)鍵路徑的求出對一項工程而言是非常必要的。因此，完成工程所需的最短時間是從開始點到完成點的最長路徑的長度，(Critical Path)。他可以使人們了解： (1). 研究某個工程至少需要多少時間? (2). 哪些活動是影響工程進度的關(guān)鍵？ 由于AOE網(wǎng)中的有些活動可以并行進行，從開始點到各個頂點，以致從開始點到完成點的有向路徑可能不止一條，這些路徑的長度也可能不同。AOE網(wǎng)是一個帶權(quán)的有向無環(huán)圖，其中，頂點表示事件（EVENT），弧表示活動，權(quán)表示活動持續(xù)的時間。完成了這些“活動”，這個工程就可以完成了。二、系統(tǒng)需求及分析：簡要介紹：我們通常把計劃、施工過程、生產(chǎn)流程、程序流程等都當(dāng)成一個工程。操作：（1）求工程最短工期；（2）輸出關(guān)鍵路徑；（3）輸出關(guān)鍵活動。數(shù) 據(jù) 結(jié) 構(gòu)課 程 設(shè) 計 報 告理論成績實踐成績總成績院系： 信息管理學(xué)院 專業(yè)： 軟件工程 班級： 軟件Q1141 學(xué)號： 11150038 姓名： 李艷平 教師： 鄧沌華 時間： 目錄一、 問題的描述二、 系統(tǒng)需求及分析 簡要介紹 需求分析 概要設(shè)計 詳細設(shè)計(1) 數(shù)據(jù)結(jié)構(gòu)(2) 創(chuàng)建有向圖的鄰接表(3) 計算各事件及活動的相關(guān)信息(4) 輸出有向圖的相關(guān)信息(5) 判斷圖中是否有回路(6) 計算并輸出關(guān)鍵活動(7) 計算并輸出關(guān)鍵路徑(8) 操作入口三、 系統(tǒng)實現(xiàn)四、 設(shè)計總結(jié)五、 附件（完整源代碼）一、問題的描述：關(guān)鍵路徑問題（起評分：85）功能：設(shè)計一個程序求出完成整項工程至少需要多少時間以及整項工程中的關(guān)鍵活動。數(shù)據(jù)：自行設(shè)計每個活動的前導(dǎo)活動和后續(xù)活動以及活動的進行時間，然后依據(jù)這些活動的前后次序，畫出其網(wǎng)絡(luò)圖，選擇存儲結(jié)構(gòu)。 要求：界面友好，提示信息完整。工程通常分為若干個稱為“活動”的子工程。 我們通常用AOE網(wǎng)來表示工程。AOE網(wǎng)可以用來估算工程的完成時間。完成不同路徑的活動所需的時間雖然不同，但只有各條路徑上所有活動都完成了，這個工程才算完成。 關(guān)鍵路徑可以很方便的讓我們估算出某個工程最短的時間開銷，以及這個工程中哪些活動，即哪些項目是主要的，是影響工程進度的關(guān)鍵，從而讓我們對工程的實施做出更好的時間安排，并且可以分清主次，抓住核心工程，做到有的放矢。需求分析：◆建立工程網(wǎng)絡(luò)圖：采用鄰接表的算法來建立圖，即順序+鏈?zhǔn)酱鎯Y(jié)構(gòu)。 源點和匯點分別表示整個工程的開始事件和結(jié)束事件ve：任一事件的最早可發(fā)生時間, 其值為源點到該點所有路徑長度的最大值；vl：在不影響整個工程進度的情況下各事件的最晚可發(fā)生時間，其值為該點到匯點的最長路徑之差；e：各項活動的最早開始時間，若以i, j表示該活動，則e(i,j) = ve(i)；l：各項活動的最晚開始時間，若以i, j表示該活動，則v(i,j) = vl(j)time；d：在不增加整個工程所需總時間的情況下，某項活動可以拖延的時，其值為el；◆ 采用鄰接表的方式建立工程圖◆ 對AOE網(wǎng)進行排序, 若發(fā)現(xiàn)回路，則提醒用戶數(shù)據(jù)錯誤，讓其重新輸入◆ 對于源點，對于源點，置其ve = 0，依次計算出各事件的ve；對于匯點，置其vl = ve, 然后依次計算出各事件的vl；再計算出各活動的e, l, d。 //頂點編號 int out_d。 //頂點入度 int ve。 //頂點所表示的事件的最遲發(fā)生時間}Vertex。 //該弧的起點, 表示此弧所代表的活動開始事件 char end。 //該弧的終點在鄰接表中的位置 int time。 //該弧所代表的活動的最早開始時間 int l。 //該弧所代表的活動可以拖延的時間, 當(dāng)d = 0時表示此活動為關(guān)鍵活動 struct arode *nextarc。typedef struct//鄰接表頭結(jié)點的類型{ Vertex data。 //指向第一條弧 }VNode。//圖中頂點數(shù)和邊數(shù) VNode adjlist[MAXV]。創(chuàng)建有向圖的鄰接鏈表：void CreateGraph(ALGraph *g) //創(chuàng)建有向圖的鄰接鏈表{ ArcNode *p。 cout\n請輸入事件總數(shù)和活動總數(shù)：endl。 cinne。 sign = 0。 gn = n。 for( i = 0。 i++) //初始化頂點信息 { gadjlist[i]. = i+65。 gadjlist[i]. = gadjlist[i]. = 0。 } cout\n請輸入各項活動的開始事件和結(jié)束事件的編號及所需時間