數(shù)據(jù)結(jié)構(gòu)課程設(shè)計(jì)報(bào)告-關(guān)鍵路徑

1、<p>　　《數(shù)據(jù)結(jié)構(gòu)》課程設(shè)計(jì)報(bào)告</p><p>　　學(xué) 院 計(jì)算機(jī)與通信工程 專 業(yè) 網(wǎng)絡(luò)工程 </p><p>　　班 級 學(xué) 號 </p><p>　　學(xué)生姓名 指導(dǎo)教師 </p><p>　　課程成績

2、 完成日期 2011年2月27日</p><p><b>　　課程設(shè)計(jì)任務(wù)書</b></p><p>　　計(jì)算機(jī)與通信工程學(xué)院 網(wǎng)絡(luò)工程專業(yè) </p><p>　　數(shù)據(jù)結(jié)構(gòu)課程設(shè)計(jì)報(bào)告</p><p><b>　　摘 要</b&g

3、t;</p><p>　　關(guān)鍵路徑是我們估算某些工程非常有用，是一種非常重要的估算一項(xiàng)工程所需的最短時間的依據(jù)。本文對如何求一個工程的關(guān)鍵路徑做了詳細(xì)的說明，包括需求分析、概要設(shè)計(jì)、詳細(xì)設(shè)計(jì)、測試與分析、總結(jié)、源程序清單。 </p><p>　　首先，做了需求分析，解釋了什么是關(guān)鍵路徑，并指出它在估算工程中的重要作用。然后給出求關(guān)鍵路徑的概要設(shè)計(jì)，包括程序中用到的所有抽象數(shù)據(jù)類型

4、的定義，主程序的流程以及各程序模塊之間的層次(調(diào)用)關(guān)系。</p><p>　　在概要設(shè)計(jì)的基礎(chǔ)上，又給出了詳細(xì)的算法設(shè)計(jì)，實(shí)現(xiàn)概要設(shè)計(jì)中定義的所有函數(shù),對每個函數(shù)寫出核心算法，并畫出了流程圖。然后對編碼進(jìn)行了測試與分析（并在最后附上C語言編寫的程序代碼）。最后對整個設(shè)計(jì)過程進(jìn)行了總結(jié)</p><p>　　關(guān)鍵詞：關(guān)鍵路徑；抽象數(shù)據(jù)類型；程序模塊；核心算法；流程圖</p>&

5、lt;p><b>　　目錄</b></p><p><b>　　1緒論- 1 -</b></p><p>　　1．1前言- 1 -</p><p>　　1．2研究意義- 1 -</p><p>　　2 需求分析- 2 -</p><p>　　2．1問題描述-

6、2 -</p><p>　　2．2基本要求- 2 -</p><p>　　2．3目的- 2 -</p><p>　　3 概要設(shè)計(jì)- 3 -</p><p>　　3．1算法分析- 3 -</p><p>　　3．2算法步驟- 3 -</p><p>　　3．3數(shù)據(jù)結(jié)構(gòu)- 4 -<

7、/p><p>　　4 詳細(xì)設(shè)計(jì)- 5 -</p><p>　　4．1主要函數(shù)的核心代碼- 5 -</p><p>　　4．2程序流程圖- 5 -</p><p>　　5 測試- 6 -</p><p>　　5．1開始界面- 6 -</p><p>　　5．2進(jìn)入求關(guān)鍵路徑的系統(tǒng)- 6 -

8、</p><p>　　5．3輸入節(jié)點(diǎn)數(shù)和活動個數(shù)- 7 -</p><p>　　5．4輸入某項(xiàng)目的信息（弧頭，弧尾，權(quán)值）- 7 -</p><p>　　5．5打印出關(guān)鍵路徑- 8 -</p><p>　　5．6錯誤測試- 9 -</p><p>　　5．7回路測試- 10 -</p><

9、p>　　6 總結(jié)- 11 -</p><p>　　參考文獻(xiàn)- 12 -</p><p>　　附錄：源程序清單- 13 -</p><p><b>　　1緒論</b></p><p><b>　　1．1前言 </b></p><p>　　我們通常把計(jì)劃、施工過程、生

10、產(chǎn)流程、程序流程等都當(dāng)成一個工程。工程通常分為若干個稱為“活動”的子工程。完成了這些“活動”，這個工程就可以完成了。

11、

12、 </p><p>　　我們通常用AOE-網(wǎng)來表示工程。AOE-網(wǎng)是一個帶權(quán)的有向無環(huán)圖，其中，頂點(diǎn)表示事件（EVENT），弧表示活動，權(quán)表示活動持續(xù)的時間。</p><p>　　AOE-網(wǎng)可以用來估算工程的完成時間。他可以使人們了解：</p><p>　　研究某個工程至少需要

13、多少時間?</p><p>　　哪些活動是影響工程進(jìn)度的關(guān)鍵？</p><p>　　由于AOE-網(wǎng)中的有些活動可以并行進(jìn)行，從開始點(diǎn)到各個頂點(diǎn)，以致從開始點(diǎn)到完成點(diǎn)的有向路徑可能不止一條，這些路徑的長度也可能不同。完成不同路徑的活動所需的時間雖然不同，但只有各條路徑上所有活動都完成了，這個工程才算完成。因此，完成工程所需的最短時間是從開始點(diǎn)到完成點(diǎn)的最長路徑的長度，即在這條路徑上的所有活動

14、的持續(xù)時間之和.這條路徑長度就叫做關(guān)鍵路徑(Critical Path)。</p><p><b>　　1．2研究意義 </b></p><p>　　關(guān)鍵路徑可以很方便的讓我們估算出某個工程最短的時間開銷，以及這個工程中哪些活動，即哪些項(xiàng)目是主要的，是影響工程進(jìn)度的關(guān)鍵，從而讓我們對工程的實(shí)施作出更好的時間安排，并且可以分清主次，抓住核心工程，做到有的放矢。</

15、p><p>　　總的來說，正因?yàn)殛P(guān)鍵路徑可以幫助我們對工程進(jìn)行非常有必要的估算，讓我們得以看清全局，作出更為優(yōu)化的安排，所以可見關(guān)鍵路徑的求出對一項(xiàng)工程而言是非常必要的。這亦是本次對關(guān)鍵路徑求法的研究意義所在。</p><p><b>　　-1-</b></p><p><b>　　2 需求分析</b></p>

16、<p><b>　　2．1問題描述 </b></p><p>　?。?）選取建圖的一種算法建立圖，有鄰接矩陣，鄰接表，十字鏈表，鄰接多重表等多種方法，要選取一種適當(dāng)?shù)姆椒ńD，才能提高算法效率，降低時間復(fù)雜度和空間復(fù)雜度。</p><p>　?。?）兩個相鄰頂點(diǎn)與它們之間的邊表示活動，邊上的數(shù)字表示活動延續(xù)的時間。對于給出的事件AOE網(wǎng)絡(luò)，要求求出從起點(diǎn)到

17、終點(diǎn)的所有路徑，經(jīng)分析、比較后找出長讀最大的路徑，從而得出求關(guān)鍵路徑的算法，并給出計(jì)算機(jī)上機(jī)實(shí)現(xiàn)的源程序。完成不同路徑的活動所需的時間雖然不同，但只有各條路徑上所有活動都完成了，這個工程才算完成。</p><p>　　具體要解決的問題有如下四個：</p><p>　　1） 將項(xiàng)目中的各項(xiàng)活動視為有一個時間屬性的結(jié)點(diǎn)，從項(xiàng)目起點(diǎn)到終點(diǎn)進(jìn)行排列； </p><p>　　

18、2） 用有方向的線段標(biāo)出各結(jié)點(diǎn)的緊前活動和緊后活動的關(guān)系，使之成為一個有方向的網(wǎng)絡(luò)圖； </p><p>　　3） 用正推法和逆推法計(jì)算出各個活動的最早開始時間，最晚開始時間，最早完工時間和最遲完工時間，并計(jì)算出各個活動的時差； </p><p>　　4） 找出所有時差為零的活動所組成的路線，即為關(guān)鍵路徑； </p><p><b>　　2．2基本要求 &

19、lt;/b></p><p>　?。?）選取建圖的一種算法建立圖；</p><p>　　選取鄰接表的算法來建立圖，是一種順序+ 鏈?zhǔn)酱鎯Y(jié)構(gòu)。用順序表存放頂點(diǎn)，為每個頂點(diǎn)建立一個單鏈表，單鏈表中的結(jié)點(diǎn)表示依附于該頂點(diǎn)的邊或以該頂點(diǎn)為尾的弧。</p><p>　　（2）兩個相鄰頂點(diǎn)與它們之間的邊表示活動，邊上的數(shù)字表示活動延續(xù)的時間</p><

20、;p>　　參照該工程所化的AOE-網(wǎng)，求出從起點(diǎn)到終點(diǎn)的所有路徑，然后通過拓?fù)渑判蚝湍嫱負(fù)渑判蚯蟪鲎钤缗c最晚發(fā)生時間，找出長度最大的路徑，從而求得關(guān)鍵路徑。 </p><p><b>　　2．3目的</b></p><p>　　在該部分，即需求分析中，根據(jù)設(shè)計(jì)題目的要求，充分地分析和理解問題，敘述系統(tǒng)的功能要求，明確問題要求做什么，以及限制條件是什么。 程序

21、所能達(dá)到的功能：通過輸入所要構(gòu)建的圖的頂點(diǎn)數(shù)，弧數(shù)，創(chuàng)建圖，并打印出來，對圖進(jìn)行拓?fù)渑判?，求得此圖的最早發(fā)生時間和最遲發(fā)生時間，并求得關(guān)鍵活動和關(guān)鍵路徑，打印出來。</p><p><b>　　-2-</b></p><p><b>　　3 概要設(shè)計(jì)</b></p><p><b>　　3．1算法分析</b

22、></p><p>　?。?）求關(guān)鍵路徑必須在拓?fù)渑判虻那疤嵯逻M(jìn)行，有環(huán)圖不能求關(guān)鍵路徑；</p><p>　?。?）只有縮短關(guān)鍵活動的工期才有可能縮短工期；</p><p>　?。?）若一個關(guān)鍵活動不在所有的關(guān)鍵路徑上，減少它并不能減少工期； </p><p>　　（4）只有在不改變關(guān)鍵路徑的前提下，縮短關(guān)鍵活動才能縮短整個工期。&l

23、t;/p><p>　?。?）關(guān)鍵路徑 ：從源點(diǎn)到匯點(diǎn)的路徑長度最長的路徑叫關(guān)鍵路徑。</p><p>　?。?）活動開始的最早時間e(i)；</p><p>　?。?）活動開始的最晚時間l(i)；</p><p>　?。?）定義e(i)=l(i)的活動叫關(guān)鍵活動；</p><p>　　（9）事件開始的最早時間ve

24、(i)；</p><p>　?。?0）事件開始的最晚時間vl(i)。</p><p>　　設(shè)活動ai由弧<j,k>(即從頂點(diǎn)j到k)表示，其持續(xù)時間記為dut(<j,k>),則： e(i)=ve(j) l(i)=vl(k)-dut(<j,k>)   </p><p>　　求ve(i)和vl(j)

25、分兩步： 1.從ve(1)=0開始向前遞推</p><p>　　ve(j)=Max{ ve(i)+dut(<i,j>) }      <i,j>T,  2<=j<=n 其中，T是所有以j為弧頭的弧的集合。 2.從vl(n)=ve(n)開始向后遞推 vl(

26、i)=Min{ vl(j)-dut(<i,j>) }     <i,j>S,  1<=i<=n-1 其中，S是所有以i為弧尾的弧的集合。兩個遞推公式是在拓?fù)溆行蚝湍嫱負(fù)溆行虻那疤嵯逻M(jìn)行。</p><p><b>　　3．2算法步驟</b></p><p&

27、gt;　　(1)輸入e條弧<j,k>，建立AOE網(wǎng)的存儲結(jié)構(gòu)。(2)從源點(diǎn)v1出發(fā)，令ve(1)=0,求 ve(j)，2<=j<=n。(3)從匯點(diǎn)vn出發(fā)，令vl(n)=ve(n),求 vl(i)    1<=i<=n-1。(4)根據(jù)各頂點(diǎn)的ve和vl值，求每條弧s（活動）的最早開始時間e(s)和最晚開始時間l(s)，其中e(s)=l(s)的為關(guān)鍵活動。</p>

28、<p><b>　　-3-</b></p><p><b>　　3．3數(shù)據(jù)結(jié)構(gòu)</b></p><p>　　typedef struct node//邊表結(jié)點(diǎn) </p><p><b>　　{ </b></p><p>　　int adjvex; //鄰接點(diǎn)編

29、號</p><p>　　int dut; //弧的信息 </p><p>　　struct node *next; //下一條弧指針</p><p>　　}edgenode; </p><p>　　typedef struct //頂點(diǎn)表結(jié)點(diǎn)</p><p><b>　　{ </b><

30、/p><p>　　int projectname;//頂點(diǎn)域 </p><p>　　int id;//頂點(diǎn)的入度信息 </p><p>　　edgenode *link; //邊表頭指針 </p><p>　　}vexnode; </p><p>　　int main() </p><p>

31、<b>　　界面程序的主函數(shù)</b></p><p>　　void seekkeyroot()</p><p>　　求關(guān)鍵路徑的主函數(shù) </p><p>　　void CreateGraphic(vexnode* Graphicmap,int projectnumber,int activenumber)</p><p&g

32、t;　　函數(shù)建立AOE圖 </p><p>　　int SearchMapPath(vexnode* Graphicmap,int projectnumber,int activenumber,int& totaltime) </p><p>　　求出最大路徑，并打印出關(guān)鍵路徑 </p><p>　　主函數(shù)void main()</p>&

33、lt;p>　　要調(diào)用：求關(guān)鍵路徑的函數(shù)seekkeyroot()；</p><p>　　求關(guān)鍵路徑的函數(shù)seekkeyroot()</p><p>　　要調(diào)用：創(chuàng)建圖的函數(shù)CreateGraphic(Graphicmap,projectnumber,activenumber)</p><p>　　求最大路徑并打印出關(guān)鍵路徑的函數(shù)int SearchMapPat

34、h(vexnode* Graphicmap,int projectnumber,int activenumber,int& totaltime) </p><p><b>　　-4-</b></p><p><b>　　4 詳細(xì)設(shè)計(jì)</b></p><p>　　4．1主要函數(shù)的核心代碼</p><

35、;p>　　首先寫出一個構(gòu)建一個有向圖的函數(shù)，包括節(jié)點(diǎn)，活動個數(shù)以及個節(jié)點(diǎn)之間的權(quán)值輸入,為求關(guān)鍵路徑作準(zhǔn)備。即函數(shù)CreateGraphic（）。</p><p>　　寫求出關(guān)鍵路徑的主函數(shù)，以及實(shí)現(xiàn)顯示求關(guān)鍵路徑過程的函數(shù)，里面用到線性表鏈表的算法數(shù)據(jù)結(jié)構(gòu)。即函數(shù)seekkeyroot()</p><p>　　編寫主函數(shù)mian（）對函數(shù)CreateGraphic（）和函數(shù)seek

36、keyroot()進(jìn)行調(diào)用，實(shí)現(xiàn)程序求關(guān)鍵路徑的功能。</p><p>　　具體代碼請見附錄：源程序清單。</p><p><b>　　4．2程序流程圖</b></p><p>　　圖4.1 程序流程圖</p><p><b>　　-5-</b></p><p><b&

37、gt;　　5 測試</b></p><p><b>　　5．1開始界面</b></p><p>　　開始界面如圖5.1所示</p><p>　　圖5.1 開始界面圖</p><p>　　5．2進(jìn)入求關(guān)鍵路徑的系統(tǒng)</p><p>　　輸入s之后則出現(xiàn)如圖5.2，開始進(jìn)入程序</p

38、><p>　　圖5.2 進(jìn)入程序界面圖</p><p><b>　　-6-</b></p><p>　　5．3輸入節(jié)點(diǎn)數(shù)和活動個數(shù)</p><p>　　輸入節(jié)點(diǎn)數(shù)和活動點(diǎn)數(shù)為3，如圖5.3所示</p><p>　　圖5.3 建立節(jié)點(diǎn)圖</p><p>　　5．4輸入某項(xiàng)目的信息

39、</p><p>　　輸入各節(jié)點(diǎn)之間的聯(lián)系，弧頭，弧尾以及之間的權(quán)值如圖5.4所示</p><p>　　圖5.4 輸入節(jié)點(diǎn)信息圖</p><p><b>　　-7-</b></p><p>　　5．5打印出關(guān)鍵路徑</p><p>　　按回車之后，程序則會自動計(jì)算關(guān)鍵路徑，過程如圖5.5所示<

40、;/p><p>　　圖5.5 打印關(guān)鍵路徑圖</p><p><b>　　-8-</b></p><p><b>　　5．6錯誤測試</b></p><p>　　應(yīng)輸入的數(shù)為整形，若輸入非整形的數(shù)據(jù)，則程序遇到問題如圖5.6關(guān)閉。</p><p><b>　　圖5.1&

41、lt;/b></p><p>　　圖5.6 錯誤側(cè)測試圖</p><p><b>　　-9-</b></p><p><b>　　5．7回路測試</b></p><p>　　如果輸入的節(jié)點(diǎn)構(gòu)成的圖有回路則會出現(xiàn)如圖5.7的提示無法計(jì)算出關(guān)鍵路徑</p><p>　　圖5

42、.7 回路測試錯誤圖</p><p><b>　　-10-</b></p><p><b>　　6 總結(jié)</b></p><p>　　歷時兩周的課程設(shè)計(jì)終于結(jié)束了，現(xiàn)在來做一下總結(jié)。</p><p>　　首先，關(guān)于程序方面，我發(fā)現(xiàn)即使對設(shè)計(jì)思路有了眉目，知道了所要用到的數(shù)據(jù)結(jié)構(gòu)、用鄰接表來存儲AOE

43、-網(wǎng)、建立棧來求拓?fù)湫蛄?、輸出的拓?fù)湫蛄械膫€數(shù)少于節(jié)點(diǎn)數(shù)則有回路等等，要把這些方法寫成函數(shù)代碼，其實(shí)還是一件非常不容易的事情。再加上要完善設(shè)計(jì)思路，構(gòu)造整個程序框架在內(nèi)，都是一件工作量非常大的工作。</p><p>　　幸好，有很多資料可以在網(wǎng)路上搜到。所以課程設(shè)計(jì)的第一天，我們搜集了很多關(guān)于關(guān)鍵路徑的資料，包括幾種不同思路的程序代碼，以及程序流程。然后我們的工作就變成：看懂并整理這些代碼，然后再其基礎(chǔ)上增加自己

44、需要的功能，按照自己的意愿來修改與完善。</p><p>　　不過在操作界面的人性化上，我倒盡可能的做得很完善，無論從美觀角度還是方便清楚操作，都實(shí)行了非常人性化的方式。因?yàn)橥ǔＧ宄绦虻娜?，知道怎么操作以及該輸入什么，而不清楚的人卻有很大可能在細(xì)節(jié)方面輸入錯誤導(dǎo)致程序運(yùn)行失敗，或是根本不知道應(yīng)該怎么輸入。所以，盡可能的人性化的設(shè)計(jì)是非常有必要的，讓不懂程序的人也可以正確的操作運(yùn)行。</p><

45、;p>　　其次，關(guān)于課程設(shè)計(jì)報(bào)告方面，老師對我們的要求非常嚴(yán)格，對課程設(shè)計(jì)報(bào)告的要求與畢業(yè)設(shè)計(jì)的格式相當(dāng)，以便為大四時做畢業(yè)設(shè)計(jì)打下良好的基礎(chǔ)。</p><p>　　初期，因?yàn)橹盀榱怂鸭Y料模板，有參考一下已經(jīng)做完數(shù)據(jù)結(jié)構(gòu)課設(shè)的對日班即十二班的報(bào)告，發(fā)現(xiàn)她們的報(bào)告相當(dāng)簡單，所以確實(shí)覺得老師對我們要求太嚴(yán)了，雖然看似簡單，但一大堆的要求、規(guī)定、格式等，完成起來卻真的很麻煩也很辛苦。</p>&

46、lt;p>　　然而，經(jīng)過了幾天的“努力報(bào)告ing~~~”的狀態(tài)，常常一弄就弄很長時間，時常做到</p><p>　　很晚還在做報(bào)告內(nèi)容、目錄、頁眉頁腳、程序截圖……再加上關(guān)鍵路徑的課程內(nèi)容，是在十幾辛苦又充實(shí)。雖然辛苦程度相差很遠(yuǎn)，但也有些明白大四的學(xué)生為什么幾乎沒課卻也整天在那里做畢業(yè)設(shè)計(jì)了。</p><p>　　我認(rèn)為這樣的課程設(shè)計(jì)比較有意義，獨(dú)立完成資料的搜集以及課設(shè)的內(nèi)容，然

47、后獨(dú)立的做出報(bào)告，讓這個過程很完整，無論是知識方面、還是報(bào)告的書寫方面，都學(xué)到了更多的東西，為畢業(yè)設(shè)計(jì)打下了良好的基礎(chǔ)。</p><p>　　最后，做再次一下總結(jié)。程序方面仍有為解決的問題，希望即便課設(shè)之后也可以努力將問題解決掉。然后關(guān)鍵路徑的算法中，有些知道怎么做卻很難清楚回答出來的問題，希望可以再好好的查找一下相關(guān)資料，將知識系統(tǒng)化、理論化、規(guī)范化。</p><p><b>

48、　　-11-</b></p><p><b>　　參考文獻(xiàn)</b></p><p>　　楊路明.C語言程序設(shè)計(jì)教程.北京：北京郵電大學(xué)出版社，2000.1</p><p>　　嚴(yán)蔚敏，吳偉民.數(shù)據(jù)結(jié)構(gòu). 北京：清華大學(xué)出版社，2006</p><p>　　譚浩強(qiáng).C程序設(shè)計(jì).北京：北京清華大學(xué)出版社，1999

49、.1</p><p>　　北京金洪恩電腦有限公司.C/C++程序設(shè)計(jì)入門.天津：天津電子出版社，2003.4</p><p><b>　　-12-</b></p><p><b>　　附錄：源程序清單</b></p><p>　　#include<stdio.h></p>

50、<p>　　#include<stdlib.h></p><p>　　#include<iomanip.h></p><p>　　#include <process.h></p><p>　　typedef struct node//邊表結(jié)點(diǎn)</p><p><b>　　{</b&

51、gt;</p><p>　　int adjvex; //鄰接點(diǎn)編號</p><p>　　int dut; //弧的信息</p><p>　　struct node *next; //下一條弧指針</p><p>　　}edgenode;</p><p>　　typedef struct //頂點(diǎn)表結(jié)點(diǎn)</p&

52、gt;<p><b>　　{</b></p><p>　　int projectname;//頂點(diǎn)域</p><p>　　int id;//頂點(diǎn)的入度信息</p><p>　　edgenode *link; //邊表頭指針</p><p><b>　　}vexnode;</b><

53、/p><p>　　void CreateGraphic(vexnode* Graphicmap,int projectnumber,int activenumber)//創(chuàng)建圖</p><p><b>　　{</b></p><p>　　int begin,end,duttem; //分別代表弧的前節(jié)點(diǎn)，尾節(jié)點(diǎn)，活動時間</p>&l

54、t;p>　　edgenode *p;// 邊表頭指針</p><p>　　for(int i=0;i<projectnumber;i++)</p><p><b>　　{</b></p><p>　　Graphicmap[i].projectname=i;//頂點(diǎn)的命名按0，1，2，3......</p><p

55、>　　Graphicmap[i].id =0;//頂點(diǎn)的信息的度數(shù)均賦為零</p><p>　　Graphicmap[i].link =NULL;</p><p><b>　　}</b></p><p>　　printf("\n");</p><p>　　printf("請輸入某項(xiàng)目的

56、信息，并請用整形數(shù)字表示（格式：弧頭，弧尾，權(quán)值）：\n");</p><p>　　printf("例如:輸入1,2,4 即代表結(jié)點(diǎn)1與4之間的活動需要4個時間單位。\n");</p><p>　　printf("\n");</p><p>　　for(int k=0;k<activenumber;k++)

57、 //activenumber為活動的數(shù)目，即弧的條數(shù)</p><p><b>　　{</b></p><p>　　scanf("%d,%d,%d",&begin,&end,&duttem); //請輸入第%d條的起點(diǎn)、終點(diǎn)和權(quán)值</p><p>　　p=(edgenode*)malloc(sizeo

58、f(edgenode));//臨時分配存儲空間</p><p>　　p->adjvex =end-1;//因?yàn)槭菑牧汩_始記的，姑要減一，就是讓終點(diǎn)插入到鄰接表內(nèi)</p><p>　　p->dut =duttem; //該弧的活動時間為duttem</p><p>　　Graphicmap[end-1].id ++; //入度加一</p>

59、<p>　　p->next =Graphicmap[begin-1].link ;</p><p>　　Graphicmap[begin-1].link =p;//讓下一個節(jié)點(diǎn)作為下一插入節(jié)點(diǎn)的前驅(qū)節(jié)點(diǎn)</p><p><b>　　}</b></p><p><b>　　-13-</b></p>

60、<p><b>　　}</b></p><p>　　int SearchMapPath(vexnode* Graphicmap,int projectnumber,int activenumber</p><p>　　,int& totaltime) //求出最大路徑，并打印出關(guān)鍵路徑</p><p><b>　

61、　{</b></p><p>　　int i,j,k,m=0;</p><p>　　int front=-1,rear=-1;</p><p>　　int* topologystack=(int*)malloc(projectnumber*sizeof(int));//用來保存拓?fù)渑帕?lt;/p><p>　　int* vl=(int

62、*)malloc(projectnumber*sizeof(int));//用來表示在不推遲整個工程的前提下，VJ允許最遲發(fā)生的時間</p><p>　　int* ve=(int*)malloc(projectnumber*sizeof(int));//用來表示Vj最早發(fā)生時間</p><p>　　int* l=(int*)malloc(activenumber*sizeof(int));

63、//用來表示活動Ai最遲完成開始時間</p><p>　　int* e=(int*)malloc(activenumber*sizeof(int));//表示活動最早開始時間</p><p>　　edgenode *p; //邊表頭的指針</p><p>　　totaltime=0; //存放整個工程的最短時間</p><p>　　for(

64、i=0;i<projectnumber;i++) ve[i]=0;//先把每個工程的最早發(fā)生時間初始化為零</p><p>　　for(i=0;i<projectnumber;i++)</p><p><b>　　{</b></p><p>　　if(Graphicmap[i].id==0)</p><p>

65、<b>　　{</b></p><p>　　topologystack[++rear]=i;//讓所有的頭節(jié)點(diǎn)入隊(duì)列</p><p>　　m++; //記錄入隊(duì)列的頂點(diǎn)個數(shù)</p><p><b>　　}</b></p><p><b>　　}</b></p>

66、<p>　　while(front!=rear)</p><p><b>　　{</b></p><p>　　front++; //出隊(duì)列</p><p>　　j=topologystack[front]; //拓?fù)渑判虻墓?jié)點(diǎn)依次出隊(duì)列</p><p>　　m++; //記錄入隊(duì)列的節(jié)點(diǎn)個數(shù)</p>

67、;<p>　　p=Graphicmap[j].link ; //指向頂點(diǎn)指向的下一個頂點(diǎn)</p><p><b>　　while(p)</b></p><p><b>　　{</b></p><p>　　k=p->adjvex ; // 鄰接點(diǎn)編號</p><p>　　Grap

68、hicmap[k].id --;//讓入度減一，相當(dāng)于刪除一個入度為零的前驅(qū)節(jié)點(diǎn)，和相關(guān)的弧</p><p>　　if(ve[j]+p->dut >ve[k])//將最長的路徑賦給VE[K]</p><p>　　ve[k]=ve[j]+p->dut ;</p><p>　　if(Graphicmap[k].id ==0)//如果入度為零，則入隊(duì)列&

69、lt;/p><p>　　topologystack[++rear]=k;</p><p>　　p=p->next ; //指向下一個節(jié)點(diǎn)</p><p><b>　　}</b></p><p><b>　　-14-</b></p><p><b>　　}</

70、b></p><p>　　if(m<projectnumber)//如果有環(huán)，則不能遍歷每個節(jié)點(diǎn)</p><p><b>　　{</b></p><p>　　printf("\n本程序所建立的圖有回路不可計(jì)算出關(guān)鍵路徑!\n");</p><p>　　printf("將退出本程序

71、！\n");</p><p><b>　　return 0;</b></p><p><b>　　}</b></p><p>　　totaltime=ve[projectnumber-1];//最短完成時間即為最后一個節(jié)點(diǎn)所累加的時間之和</p><p>　　for(i=0;i<pr

72、ojectnumber;i++)</p><p>　　vl[i]=totaltime;</p><p>　　for(i=projectnumber-2;i>=0;i--)// 用逆拓?fù)渑判騺砬蠡顒覣i最遲完成開始時間，即從最后一個節(jié)點(diǎn)減去最短的時間</p><p><b>　　{</b></p><p>　　j=t

73、opologystack[i];</p><p>　　p=Graphicmap[j].link ;</p><p><b>　　while(p)</b></p><p><b>　　{</b></p><p>　　k=p->adjvex ;</p><p>　　if((

74、vl[k]-p->dut )<vl[j])</p><p>　　vl[j]=vl[k]-p->dut ;</p><p>　　p=p->next ;</p><p><b>　　}</b></p><p><b>　　}</b></p><p><

75、;b>　　i=0;</b></p><p>　　printf("\n");</p><p>　　printf("| 起點(diǎn) | 終點(diǎn) | 最早開始時間 | 最遲完成時間 | 差值 | 備注 \n");</p><p>　　for(j=0;j<projectnumber;j++)</p>&l

76、t;p><b>　　{</b></p><p>　　p=Graphicmap[j].link;</p><p><b>　　while(p)</b></p><p><b>　　{</b></p><p>　　k=p->adjvex ;</p><

77、;p>　　e[++i]=ve[j];</p><p>　　l[i]=vl[k]-p->dut;</p><p>　　printf("| %4d | %4d | %11d | %11d | %3d |",Graphicmap[j].projectname +1,Graphicmap[k].projectname +1,e[i],l[i],l[i]-e[i

78、]);</p><p>　　if(l[i]==e[i]) //當(dāng)差值為零時，則為關(guān)鍵路徑</p><p>　　printf(" 關(guān)鍵活動 <%2d,%4d>",</p><p>　　Graphicmap[j].projectname +1,Graphicmap[k].projectname +1);</p><p

79、>　　printf("\n");</p><p>　　p=p->next ;</p><p><b>　　}</b></p><p><b>　　-15-</b></p><p><b>　　}</b></p><p>　

80、　return 1;}</p><p>　　void seekkeyroot()//求關(guān)鍵路徑的主函數(shù)</p><p><b>　　{</b></p><p>　　int projectnumber,activenumber,totaltime=0;</p><p>　　printf("\n");&l

81、t;/p><p>　　printf("輸入符合標(biāo)準(zhǔn)，歡迎進(jìn)入求關(guān)鍵路徑的系統(tǒng)!\n");</p><p>　　printf("\n");</p><p>　　printf("請輸入這個項(xiàng)目的AOE-網(wǎng)的節(jié)點(diǎn)數(shù): ");</p><p>　　scanf("%d"

82、,&projectnumber);</p><p>　　printf("請輸入這個項(xiàng)目的AOE-網(wǎng)的活動個數(shù): ");</p><p>　　scanf("%d",&activenumber);</p><p>　　vexnode* Graphicmap=(vexnode*)malloc(projectnum

83、ber*sizeof(vexnode));</p><p>　　CreateGraphic(Graphicmap,projectnumber,activenumber);//創(chuàng)建鄰接圖</p><p>　　SearchMapPath(Graphicmap,projectnumber,activenumber,totaltime);//求出最大路徑，并打印出關(guān)鍵路徑</p>&

84、lt;p>　　printf("\n");</p><p>　　printf("整個工程所用的最短時間為：%d個單位時間\n",totaltime);</p><p>　　system("pause");</p><p><b>　　}</b></p><p&g

85、t;　　int main()</p><p><b>　　{</b></p><p><b>　　char ch;</b></p><p><b>　　for(;;)</b></p><p><b>　　{</b></p><p>

86、<b>　　do</b></p><p><b>　　{</b></p><p>　　system("cls");</p><p>　　printf("☆★☆★☆★☆★☆★☆★☆★☆★☆★☆★☆★☆★☆★☆★☆★☆★☆★☆★☆★ \n");&l

87、t;/p><p>　　printf(" 歡迎進(jìn)入求關(guān)鍵路徑算法程序 \n");</p><p>　　printf("☆★☆★☆★☆★☆★☆★☆★☆★☆★☆★☆★☆★☆★☆★☆★☆★☆★☆★☆★

88、 \n");</p><p>　　printf("%s","\ns(start)開始輸入工程的節(jié)點(diǎn)數(shù)據(jù)并求出關(guān)鍵路徑\n");</p><p>　　printf("\n");</p><p>　　printf("%s","e(exit)退出\n");&l

89、t;/p><p>　　printf("\n");</p><p>　　printf("%s","請輸入選擇:");</p><p>　　scanf("%c",&ch);</p><p>　　ch=toupper(ch);</p><p>

90、;<b>　　-16-</b></p><p>　　}while(ch!='S'&&ch!='E');</p><p>　　switch(ch)</p><p><b>　　{</b></p><p><b>　　case'S'

91、;:</b></p><p>　　seekkeyroot();</p><p><b>　　break;</b></p><p><b>　　case'E':</b></p><p><b>　　return 1;</b></p>&l