課程設計-關(guān)鍵路徑

1、荊楚理工學院課程設計成果學院:班級:學生姓名：學號:設計地點（單位）設計題目:完成日期： 年 月 日指導教師評語：成績（五級記分制）:教師簽名:數(shù)據(jù)結(jié)構(gòu)課程設計報告摘要關(guān)鍵路徑是我們估算某些工程非常有用，是一種非常重要的估算一項工程所需的最短時間的依據(jù)。本文對如何求一個工程的關(guān)鍵路徑做了詳細的說明，包括需求分析、概要設計、詳細設計、測試與分析、總結(jié)、源程序清單。首先，做了需求分析，解釋了什么是關(guān)鍵路徑，并指出它在估算工程中的重要作用。然后給出求關(guān) 鍵路徑的概要設計，包括程序中用到的所有抽象數(shù)據(jù)類型的定義，主程序的流程以及各程序模塊之間的 層次（調(diào)用）關(guān)系。在概要設計的基礎上，又給出了詳細的算法

2、設計，實現(xiàn)概要設計中定義的所有函數(shù)，對每個函數(shù)寫出 核心算法，并畫出了流程圖。 然后對編碼進行了測試與分析 （并在最后附上 C語言編寫的程序代碼）。最 后對整個設計過程進行了總結(jié)。【關(guān)鍵詞】：關(guān)鍵路徑；抽象數(shù)據(jù)類型；程序模塊；核心算法；流程圖。 TOC o 1-5 h z HYPERLINK l bookmark5 o Current Document .需求分析11問題描述11 .2基本要求11.3目的1 HYPERLINK l bookmark7 o Current Document 2概要設計22.1算法分析2 HYPERLINK l bookmark9 o Current Docume

3、nt 2.2算法步驟3 HYPERLINK l bookmark13 o Current Document 2.3數(shù)據(jù)結(jié)構(gòu)32. 3. 1數(shù)據(jù)結(jié)構(gòu)32. 3. 2程序模塊32. 3. 3各模塊間的調(diào)用關(guān)系 4 HYPERLINK l bookmark21 o Current Document 3詳細設計43.1主要函數(shù)的核心代碼 4 HYPERLINK l bookmark25 o Current Document 4測試5開始界面5進入求關(guān)鍵路徑的系統(tǒng) 5 HYPERLINK l bookmark27 o Current Document 輸入節(jié)點數(shù)和活動個數(shù) 6 HYPERLINK l b

4、ookmark29 o Current Document 輸入某項目的信息（弧頭，弧尾，權(quán)值） 6打印出關(guān)鍵路徑 7課本上圖7.29的程序測試 7錯誤測試9回路測試9 HYPERLINK l bookmark37 o Current Document 5總結(jié)10 HYPERLINK l bookmark39 o Current Document 參考文獻12 HYPERLINK l bookmark41 o Current Document 附錄：源程序代碼 131.需求分析1. 1問題描述1）選取建圖的一種算法建立圖，有鄰接矩陣，鄰接表，十字鏈表，鄰接多重表等多種 方法，要選取一種適當?shù)姆椒?/p>

5、建立圖，才能提高算法效率，降低時間復雜度和空間復雜度。2）兩個相鄰頂點與它們之間的邊表示活動，邊上的數(shù)字表示活動延續(xù)的時間。對于給 出的事件AOE網(wǎng)絡，要求求出從起點到終點的所有路徑，經(jīng)分析、比較后找出長讀最大的 路徑，從而得出求關(guān)鍵路徑的算法，并給出計算機上機實現(xiàn)的源程序。完成不同路徑的活 動所需的時間雖然不同，但只有各條路徑上所有活動都完成了，這個工程才算完成。具體要解決的問題有如下四個：1）將項目中的各項活動視為有一個時間屬性的結(jié)點，從項目起點到終點進行排列；2）用有方向的線段標出各結(jié)點的緊前活動和緊后活動的關(guān)系，使之成為一個有方向的 網(wǎng)絡圖；3）用正推法和逆推法計算出各個活動的最早開始

6、時間，最晚開始時間，最早完工時間 和最遲完工時間，并計算出各個活動的時差；4）找出所有時差為零的活動所組成的路線，即為關(guān)鍵路徑；. 2基本要求1）選取建圖的一種算法建立圖；選取鄰接表的算法來建立圖，是一種順序 +鏈式存儲結(jié)構(gòu)。用順序表存放頂點，為每 個頂點建立一個單鏈表，單鏈表中的結(jié)點表示依附于該頂點的邊或以該頂點為尾的弧。2）兩個相鄰頂點與它們之間的邊表示活動，邊上的數(shù)字表示活動延續(xù)的時間參照該工程所化的AOE-網(wǎng)，求出從起點到終點的所有路徑，然后通過拓撲排序和逆拓 撲排序求出最早與最晚發(fā)生時間，找出長度最大的路徑，從而求得關(guān)鍵路徑。. 3目的在該部分，即需求分析中，根據(jù)設計題目的要求，充分

7、地分析和理解問題，敘述系統(tǒng) 的功能要求，明確問題要求做什么，以及限制條件是什么。程序所能達到的功能：通過輸入所要構(gòu)建的圖的頂點數(shù)，弧數(shù)，創(chuàng)建圖，并打印出來, 對圖進行拓撲排序，求得此圖的最早發(fā)生時間和最遲發(fā)生時間，并求得關(guān)鍵活動和關(guān)鍵路 徑，打印出來。2概要設計. 1算法分析求關(guān)鍵路徑必須在拓撲排序的前提下進行，有環(huán)圖不能求關(guān)鍵路徑；只有縮短關(guān)鍵活動的工期才有可能縮短工期；若一個關(guān)鍵活動不在所有的關(guān)鍵路徑上，減少它并不能減少工期；只有在不改變關(guān)鍵路徑的前提下，縮短關(guān)鍵活動才能縮短整個工期。關(guān)鍵路徑：從源點到匯點的路徑長度最長的路徑叫關(guān)鍵路徑?；顒娱_始的最早時間e(i);活動開始的最晚時間l(i

8、);定義e(i)=l(i)的活動叫關(guān)鍵活動；事件開始的最早時間ve(i);(10)事件開始的最晚時間vl(i)。設活動ai由弧(即從頂點j到k)表示，其持續(xù)時間記為dut(),則：e(i)=ve(j)l(i)=vl(k)-dut()求ve(i)和vl(j) 分兩步：.從ve(1)=0開始向前遞推ve(j)=Max ve(i)+dut() T, 2=j=n其中，T是所有以j為弧頭的弧的集合。.從vl(n)=ve(n)開始向后遞推vl(i)=Min vl(j)-dut() S, 1=i=n-1其中，S是所有以i為弧尾的弧的集合。兩個遞推公式是在拓撲有序和逆拓撲有序的前提下進行。2算法步驟輸入e條弧

9、 ,建立AOE的存儲結(jié)構(gòu)。從源點 v1 出發(fā)，令 ve(1)=0,求 ve(j) , 2=j=n。從匯點 vn 出發(fā)，令 vl(n)=ve(n), 求 vl(i) 1=i=n-1。根據(jù)各頂點的ve和vl值，求每條弧s (活動)的最早開始時間e(s)最晚開始時間l(s),其中e(s)=l(s)的為關(guān)鍵活動。2. 3數(shù)據(jù)結(jié)構(gòu)2. 3. 1數(shù)據(jù)結(jié)構(gòu)typedef struct node/ 邊表結(jié)點int adjvex; / 鄰接點編號int dut; /弧的信息struct node *next; /下一條弧指針edgenode;typedef struct / 頂點表結(jié)點int projectna

10、me;/ 頂點域int id;/ 頂點的入度信息edgenode *link; /邊表頭指針vexnode;2. 3. 2程序模塊int main()界面程序的主函數(shù)void seekkeyroot()求關(guān)鍵路徑的主函數(shù)void CreateGraphic(vexnode* Graphicmap,int projectnumber,int activenumber)函數(shù)建立AO0SInt SearchMapPath(vexnode* Graphicmap,int projectnumber,int activenumber,int& totaltime)求出最大路徑，并打印出關(guān)鍵路徑3. 3各

11、模塊間的調(diào)用關(guān)系主函數(shù) void main()要調(diào)用：求關(guān)鍵路徑的函數(shù) seekkeyroot()；求關(guān)鍵路徑的函數(shù)seekkeyroot()要調(diào)用：倉1J建圖的函數(shù) CreateGraphic(Graphicmap,projectnumber,activenumber)求最大路徑并打印出關(guān)鍵路徑的函數(shù)int SearchMapPath(vexnode* Graphicmap,intprojectnumber,int activenumber,int& totaltime)3詳細設計1主要函數(shù)的核心代碼要求：1)建立一個AOES,并輸出結(jié)果確保創(chuàng)建成功；2)判斷AOES是一個拓撲有序序列，如果

12、不是拓撲有序則報錯；3)編寫函數(shù)求AOES的關(guān)鍵路徑；4)打印輸出關(guān)鍵路徑；5)每一個函數(shù)要有必要的注釋，在課程設計論文中有流程圖。具體代碼請見附錄：源程序清單。3. 2程序流程圖4測試4.1開始界面4.2進入求關(guān)鍵路徑的系統(tǒng)輸入節(jié)點數(shù)和活動個數(shù)輸入某項目的信息（弧頭，弧尾,權(quán)值）C:UsersSDesktopUn title di .exe耕十壬二路S握開始輸入工程的節(jié)點數(shù)據(jù)并求出關(guān)鍵路徑退出請輸入選擇冷輸入符合標準，進入求關(guān)鍵路徑？臧斕;羽蠹繇菰31青輸入某項目的信息，并請用整形教字表示（格式，瓠頭，弧尾，權(quán)值顏124），（24工卡3 * S4.2.3打印出關(guān)鍵路徑其他00動 動差值1,弧

13、頭，弧尾，權(quán)值例，：俞人符合標準，進入求關(guān)鍵路徑，并請用整形數(shù)字表示（格式:起點!終點1最早開始時間：最遲完成時間J2最短時間為:1日個單位時間王.00404個工 椅仟開始輸入工程的節(jié)點數(shù)據(jù)并求出關(guān)鍵路徑 mt）退出由 0E-網(wǎng)的活動不數(shù):C:UsersgDesktopUntitledLexe4.2.4課本上圖7.24的程序測試Hn4n 鬻 矢天求上述AOE網(wǎng)的操作為:權(quán)值例*0E-網(wǎng)的節(jié)點 邯肥-網(wǎng)的活動最短時間為：18個單位時間輸入符合標準，進入求關(guān)鍵路徑睛輸入某項目的信息,并請用整形數(shù)字表示（格式孤頭,最早開始時間:最遲完成時間C:U sers 明哲D eskto pUntitled1.

14、exe求的關(guān)鍵路徑為:4.2.5錯誤測試應輸入的數(shù)為整形，若輸入非整形的數(shù)據(jù)，則程序遇到問題關(guān)閉。4.2.6回路測試建立的圖有回路不能計算出關(guān)鍵路徑，序！并請用整形數(shù)字表示（格式：弧頭，瓠尾，權(quán)值例：上,2,4）：0”亮人的E-網(wǎng)的節(jié)點激：3備入ftOE-網(wǎng)的活動秘二3，進入求關(guān)鍵路徑:退出gtart）開始輸入工程的節(jié)點數(shù)據(jù)并求出關(guān)犍路徑關(guān)鍵路徑C :U &ersBDesktopUntit led 1,exe& 程出取短時間為：口個單位時間5總結(jié)歷時兩周的課程設計終于結(jié)束了，現(xiàn)在來做一下總結(jié)。首先，關(guān)于程序方面，我發(fā)現(xiàn)即使對設計思路有了眉目，知道了所要用到的數(shù)據(jù)結(jié)構(gòu)、 用鄰接表來存儲AOE網(wǎng)、

15、建立棧來求拓撲序列、輸出的拓撲序列的個數(shù)少于節(jié)點數(shù)則有回 路等等，要把這些方法寫成函數(shù)代碼，其實還是一件非常不容易的事情。再加上要完善設 計思路，構(gòu)造整個程序框架在內(nèi)，都是一件工作量非常大的工作。幸好，有很多資料可以在網(wǎng)路上搜到。所以課程設計的第一天，我們搜集了很多關(guān)于 關(guān)鍵路徑的資料，包括幾種不同思路的程序代碼，以及程序流程。然后我們的工作就變成： 盡量看懂并整理這些代碼，然后再其基礎上篩選需要的功能，按照自己的意愿來修改與完 善。在處理程序代碼的時候，有兩個問題始終解決不了。一是程序輸入時只能輸入整形數(shù) 據(jù)，而非整形的輸入則會導致程序異常停止，但是因為整形的輸入方式已貫穿整個程序,若要修改

16、只能另外重做整個程序，所以暫不考慮修改，而打算做一個判錯系統(tǒng)，判斷若非 整形的輸入則報錯；二是第一種錯誤的解決方案未能成功實行，于網(wǎng)絡上搜索到了幾種判 斷是否為整形數(shù)據(jù)的程序代碼，但將其修改融合到求關(guān)鍵路徑的程序中，雖然沒有錯誤可 以運行，但是卻不能正確的報錯并且這樣做感覺有點超綱，不是本學期學到的運用到設計 程序上。于是，在嘗試多種方案卻仍不成功的前提下，我只好選擇加上提示語，即： printf( 請輸入某項目的信息，并請用整形數(shù)字表示(格式：弧頭，弧尾，權(quán)值) ：n); o不過在操作界面的人性化上，我倒盡可能的做得很完善，無論從美觀角度還是方便清 楚操作，都實行了非常人性化的方式。因為通常

17、清楚程序的人，知道怎么操作以及該輸入 什么，而不清楚的人卻有很大可能在細節(jié)方面輸入錯誤導致程序運行失敗，或是根本不知 道應該怎么輸入。所以，盡可能的人性化的設計是非常有必要的，讓不懂程序的人也可以 正確的操作運行。其次，關(guān)于課程設計報告方面，大一時任正云我們的要求非常嚴格，對課程設計報告 的要求與畢業(yè)設計的格式相當，但一大堆的要求、規(guī)定、格式等，完成起來卻真的很麻煩 也很辛苦。然而，經(jīng)過了幾天的“努力報告”的狀態(tài)，常常一弄就弄很長時間，時常做到很晚還 在做報告內(nèi)容、目錄、頁眉頁腳、程序截圖,再加上關(guān)鍵路徑的課程內(nèi)容，是在幾天辛10苦又充實。我認為這樣的課程設計比較有意義，獨立完成資料的搜集以及

18、課設的內(nèi)容，然 后團隊的做出報告，讓這個過程很完整，無論是知識方面、還是報告的書寫方面，都學到 了更多的東西，為畢業(yè)設計打下了良好的基礎。最后，做再次一下總結(jié)。程序方面仍有為解決的問題，希望即便課設之后也可以努力 將問題解決掉。然后關(guān)鍵路徑的算法中，有些知道怎么做卻很難清楚回答出來的問題，希 望可以再好好的查找一下相關(guān)資料，將知識系統(tǒng)化、理論化、規(guī)范化。11參考文獻1嚴蔚敏，吳偉民.數(shù)據(jù)Z勾.北京：清華大學出版社，2006.2譚浩強.C程序設計（第二版）作者：清華大學出版社，200612附錄：源程序代碼#include #include #include typedef struct node

19、/邊表結(jié)點(int adjvex; /鄰接點編號int dut; / 弧的信息struct node *next; / 下一條弧指針 edgenode;typedef struct / 頂點表結(jié)點(int projectname;/頂點域int id;/頂點的入度信息edgenode *link; /邊表頭指針vexnode;void CreateGraphic(vexnode* Graphicmap,int projectnumber,int activenumber)/創(chuàng)建圖(int i,k;int begin,end,duttem;/分別代表弧的前節(jié)點，尾節(jié)點，活動時間edgenode

20、*p;/邊表頭指針for(i=0;iprojectnumber;i+)( Gjectname=i;/頂點的命名按 0, 1, 2, 3Graphicmapi.id =0;/頂點的信息的度數(shù)均賦為零Graphicmapi.link =NULL;printf(n);printf(請輸入某項目的信息，并請用整形數(shù)字表示(格式：弧頭，弧尾，權(quán)值例：1,2,4 )： n);printf(n);為活動的數(shù)目，即弧的條數(shù)請輸入第d條的起點、終點和權(quán)值臨時分配存儲空間所以要減 1,就是讓終點插入到鄰接表內(nèi)for(k=0;kadjvex =end-1;/ 因為是從0開始記的,p-du

21、t =duttem; /該弧的活動時間為 duttemGraphicmapend-1.id +; /入度加一p-next =Graphicmapbegin-1.link ;Graphicmapbegin-1.link =p;/讓下一個節(jié)點作為下一插入節(jié)點的前驅(qū)節(jié)點int SearchMapPath(vexnode* Graphicmap,int projectnumber,int activenumber,int totaltime)/求出最大路徑，并打印出關(guān)鍵路徑13(int i,j,k,m=0;int front=-1,rear=-1;int* topologystack=(int*)ma

22、lloc(projectnumber*sizeof(int);int*vl=(int*)malloc(projectnumber*sizeof(int);許最遲發(fā)生的時間int* ve=(int*)malloc(projectnumber*sizeof(int);int* l=(int*)malloc(activenumber*sizeof(int);/int* e=(int*)malloc(activenumber*sizeof(int);/edgenode *p; /邊表頭的指針totaltime=0; /存放整個工程的最短時間用來保存拓撲排列用來表示在不推遲整個工程的前提下,用來表示Vj

23、最早發(fā)生時間用來表示活動 Ai最遲完成開始時間 表示活動最早開始時間VJ允for(i=0;iprojectnumber;i+) vei=0;/for(i=0;iadjvex ; / Graphicmapk.id -;/ if(vej+p-dut vek)/ vek=vej+p-dut ;if(Graphicmapk.id =0)/指向頂點指向的下一個頂點鄰接點編號讓入度減一，相當于刪除一個入度為零的前驅(qū)節(jié)點，和相關(guān)的弧 將最長的路徑賦給 VEK如果入度為零，則入隊列topologystack+rear=k;p=p-next ; /指向下一個節(jié)點)if(mprojectnumber)/如果有環(huán)，

24、則不能遍歷每個節(jié)點(printf(n本程序所建立的圖有回路不能計算出關(guān)鍵路徑！n);printf(退出本程序！n);return 0;)totaltime=veprojectnumber-1;/最短完成時間即為最后一個節(jié)點所累加的時間之和14for(i=0;i=0;i-)/用逆拓撲排序來求活動Ai最遲完成開始時間，即從最后一個節(jié)點減去最短的時間j=topologystacki;p=Graphicmapj.link ;while(p)k=p-adjvex ;if(vlk-p-dut )dut ;p=p-next ;i=0;printf(n);printf(| 起點|終點|最早開始時間|最遲完成時間|差值|其他n);for(j=0;jadjvex ;e+i=vej;li=vlk-p-dut;printf(|%4d |%4d |%12d|%12d|%4d|,Gjectname+1,Gjectname +1,ei,li,li-ei);if(li=ei) /當差值為零時，則為關(guān)鍵路徑printf(關(guān)鍵活動 ,Gjectn