數(shù)據(jù)結構課程設計報告關鍵路徑

1、數(shù) 據(jù) 結 構課 程 設 計 報 告理論成績實踐成績總成績院系： 信息管理學院 專業(yè)： 軟件工程 班級： 軟件Q1141 學號： 11150038 姓名： 李艷平 教師： 鄧沌華 時間： 2013.4.2 目錄一、 問題的描述二、 系統(tǒng)需求及分析1、 簡要介紹2、 需求分析3、 概要設計4、 詳細設計(1) 數(shù)據(jù)結構(2) 創(chuàng)建有向圖的鄰接表(3) 計算各事件及活動的相關信息(4) 輸出有向圖的相關信息(5) 判斷圖中是否有回路(6) 計算并輸出關鍵活動(7) 計算并輸出關鍵路徑(8) 操作入口三、 系統(tǒng)實現(xiàn)四、 設計總結五、 附件（完整源代碼）一、問題的描述：關鍵路徑問題（起評分：85）1、

2、功能：設計一個程序求出完成整項工程至少需要多少時間以及整項工程中的關鍵活動。2、數(shù)據(jù)：自行設計每個活動的前導活動和后續(xù)活動以及活動的進行時間，然后依據(jù)這些活動的前后次序，畫出其網(wǎng)絡圖，選擇存儲結構。3、操作：（1）求工程最短工期；（2）輸出關鍵路徑；（3）輸出關鍵活動。 4、要求：界面友好，提示信息完整。二、系統(tǒng)需求及分析：1、簡要介紹：我們通常把計劃、施工過程、生產流程、程序流程等都當成一個工程。工程通常分為若干個稱為“活動”的子工程。完成了這些“活動”，這個工程就可以完成了。 我們通常用AOE-網(wǎng)來表示工程。AOE-網(wǎng)是一個帶權的有向無環(huán)圖，其中，頂點表示事件（EVENT），弧表示活動，權

3、表示活動持續(xù)的時間。AOE-網(wǎng)可以用來估算工程的完成時間。他可以使人們了解： (1). 研究某個工程至少需要多少時間? (2). 哪些活動是影響工程進度的關鍵？ 由于AOE-網(wǎng)中的有些活動可以并行進行，從開始點到各個頂點，以致從開始點到完成點的有向路徑可能不止一條，這些路徑的長度也可能不同。完成不同路徑的活動所需的時間雖然不同，但只有各條路徑上所有活動都完成了，這個工程才算完成。因此，完成工程所需的最短時間是從開始點到完成點的最長路徑的長度，即在這條路徑上的所有活動的持續(xù)時間之和.這條路徑長度就叫做關鍵路徑(Critical Path)。 關鍵路徑可以很方便的讓我們估算出某個工程最短的時間開銷

4、，以及這個工程中哪些活動，即哪些項目是主要的，是影響工程進度的關鍵，從而讓我們對工程的實施做出更好的時間安排，并且可以分清主次，抓住核心工程，做到有的放矢?？偟膩碚f，正因為關鍵路徑可以幫助我們對工程進行非常有必要的估算，讓我們得以看清全局，作出更為優(yōu)化的安排，所以可見關鍵路徑的求出對一項工程而言是非常必要的。2、需求分析：建立工程網(wǎng)絡圖：采用鄰接表的算法來建立圖，即順序+鏈式存儲結構。計算出各事件及活動的的相關信息：如每個事件的最早和最遲開始時間，每項活動的最早最遲開始時間以及完成此活動所需的時間輸出工程圖的相關信息：用戶可根據(jù)自己需要查看相關信息拓撲排序：以此來判斷圖中是否有回路，因為圖中如

5、果有回路，工程就無法進行找出關鍵活動并輸出找出關鍵路徑并輸出3、概要設計： 相關說明：設某一活動的起點為i, 中點為j，完成該活動所需時間為time; 源點和匯點分別表示整個工程的開始事件和結束事件ve：任一事件的最早可發(fā)生時間, 其值為源點到該點所有路徑長度的最大值；vl：在不影響整個工程進度的情況下各事件的最晚可發(fā)生時間，其值為該點到匯點的最長路徑之差；e：各項活動的最早開始時間，若以表示該活動，則e(i,j) = ve(i)；l：各項活動的最晚開始時間，若以表示該活動，則v(i,j) = vl(j)-time；d：在不增加整個工程所需總時間的情況下，某項活動可以拖延的時，其值為e-l；

6、采用鄰接表的方式建立工程圖 對AOE網(wǎng)進行排序, 若發(fā)現(xiàn)回路，則提醒用戶數(shù)據(jù)錯誤，讓其重新輸入 對于源點，對于源點，置其ve = 0，依次計算出各事件的ve；對于匯點，置其vl = ve, 然后依次計算出各事件的vl；再計算出各活動的e, l, d; 找出關鍵活動和關鍵路徑 4、詳細設計： 1、數(shù)據(jù)結構： typedef struct/頂點類型 char num; /頂點編號 int out_d; /頂點出度 int in_d; /頂點入度 int ve; /頂點所表示的事件的最早發(fā)生時間 int vl; /頂點所表示的事件的最遲發(fā)生時間Vertex;typedef struct arcnod

7、e/弧的結點結構類型 char start; /該弧的起點, 表示此弧所代表的活動開始事件 char end; /該弧的終點，表示此弧所代表的活動的結束事件 int vp; /該弧的終點在鄰接表中的位置 int time; /完成該弧所表示的活動所需的時間 int e; /該弧所代表的活動的最早開始時間 int l; /該弧所代表的活動的最遲開始時間 int d; /該弧所代表的活動可以拖延的時間, 當d = 0時表示此活動為關鍵活動 struct arcnode *nextarc; /指向下一條弧的指針ArcNode;typedef struct/鄰接表頭結點的類型 Vertex data;

8、 /該頂點的相關信息 ArcNode *firstarc; /指向第一條弧 VNode;typedef struct int n, e;/圖中頂點數(shù)和邊數(shù) VNode adjlistMAXV; /鄰接鏈表ALGraph;2、創(chuàng)建有向圖的鄰接鏈表：void CreateGraph(ALGraph *g) /創(chuàng)建有向圖的鄰接鏈表ArcNode *p; int i, j, k, n, e, t, sign;coutn請輸入事件總數(shù)和活動總數(shù)：ne;if (n = 0) | (e n-1)cout數(shù)據(jù)有誤，請檢查后重新輸入!n = n;g-e = e; for( i = 0; i adjlisti.d

9、ata.num = i+65; g-adjlisti.firstarc = NULL;g-adjlisti.data.in_d = g-adjlisti.data.out_d = 0;g-adjlisti.data.ve = g-adjlisti.data.vl = 0;coutn請輸入各項活動的開始事件和結束事件的編號及所需時間：n;for( k = 1; k = e; k+)cout第kijt;p = new ArcNode;p-start = i+65; p-end = j+65;p-vp = j;p-time = t;g-adjlisti.data.out_d+;g-adjlistj.

10、data.in_d+; p-nextarc = g-adjlisti.firstarc;g-adjlisti.firstarc = p;3、計算出各事件及活動的的相關信息：void EventInfo(ALGraph *g) /計算各事件及活動的相關信息 ArcNode *p = new ArcNode; int i, k; g-adjlist0.data.ve = 0; /對于源點，置其ve = 0 for (i = 0; i n; i +) /計算各頂點所表示事件的最早發(fā)生時間ve p = g-adjlisti.firstarc; while (p != NULL) k = p-vp; i

11、f (g-adjlistk.data.ve != 0) /如果該事件的ve已經有值，則取源點到該事件的所有路徑長度的最大值 g-adjlistk.data.ve = Max(g-adjlistk.data.ve, g-adjlisti.data.ve + p-time); else /否則就取當前計算出來的值 g-adjlistk.data.ve = g-adjlisti.data.ve + p-time; p = p-nextarc; g-adjlistg-n-1.data.vl = g-adjlistg-n-1.data.ve; /對于匯點，置其vl = ve for (i = g-n -

12、 1; i = 0; i -) /計算各頂點所表示事件的最遲發(fā)生時間vl p = g-adjlisti.firstarc; while (p != NULL) k = p-vp; if (g-adjlisti.data.vl != 0) /如果該事件的vl已經有值，則取該事件到匯點的最長路徑之差 g-adjlisti.data.vl = Min(g-adjlisti.data.vl, g-adjlistk.data.vl - p-time); else /否則就取當前計算出來的值 g-adjlisti.data.vl = g-adjlistk.data.vl - p-time; p = p-n

13、extarc; for (i = 0; i n; i +) /計算各弧所代表的活動最早開始e、最遲開始l以及可以拖延的時間d p = g-adjlisti.firstarc; while (p != NULL) k = p-vp; p-e = g-adjlisti.data.ve; /某活動的最早開始時間是該活動的起點所表示的事件的最早發(fā)生時間：e = ve p-l = g-adjlistk.data.vl - p-time; /某活動的最遲開始時間l是該活動的終點所表示的事件的最遲開始時間與該活動的所需時間之差：l = vl-time p-d = p-l - p-e; /某活動可以推遲的時間

14、是其最遲開始時間與最早開始時間之差 p = p-nextarc; 4、輸出工程圖的相關信息：void OutputGraph(ALGraph *g) /輸出工程圖的相關信息couteventt ve:t vlendl;for (int i = 0; i n; i +)coutadjlisti.data.numt adjlisti.data.vet adjlisti.data.vlendl; coutendl;for (i = 0; i n; i+)ArcNode *p = g-adjlisti.firstarc;while (p != NULL)cout(start,end);couttt e

15、t lt d t timeendl;couttt e t l t d t timenextarc;coutendl;5、判斷圖中是否有回路：int TopSort(ALGraph *g) /用來判斷圖中是否有回路int i, j, sum = 0; /sum用來記錄輸出的頂點數(shù)，以判斷途中是否有回路int stMAXV, top = -1; /棧st的指針為topArcNode *p;for (i = 0; i n; i +)if (g-adjlisti.data.in_d = 0) /入度為0的頂點入棧top +;sttop = i;while (top -1) /棧不為空時就循環(huán)i = s

16、ttop; top-; /出棧/coutchar(i+65)adjlisti.firstarc; /找第一個相鄰頂點while (p != NULL)j = p-vp;g-adjlistj.data.in_d -;if (g-adjlistj.data.in_d = 0) /入度為0的相鄰頂點入棧top +;sttop = j;p = p-nextarc; /找下一個相鄰頂點coutn);6、計算并輸出關鍵活動：void KeyActs(ALGraph *g) /計算并輸出關鍵活動ArcNode *p;coutn關鍵活動有：endl;for (int i = 0; i n; i+)p = g-

17、adjlisti.firstarc;while (p != NULL)if (p-d = 0) /如果p指向的活動是關鍵活動，就將此活動輸出cout (startendnextarc;coutendl;7、計算并輸出關鍵路徑：void KeyPath(ALGraph *g) /計算并輸出關鍵路徑ArcNode tMAXV, *p; /tMAVX數(shù)組用來存放代表關鍵活動的邊的信息int j = 0; /j指示t數(shù)組下標int count = 0; /記錄關鍵路徑的條數(shù)coutn關鍵路徑有：endl;for (int i = 0; i n; i +) p = g-adjlisti.firstarc

18、;while (p != NULL)if (p-d = 0) tj.start = p-start;tj.end = p-end; j+;if (p-end = g-adjlistg-n-1.data.num) /當某活動的結束事件就是整個工程的結束事件時就出現(xiàn)一條關鍵路徑count +; p = p-nextarc;int sign; /sign用來標記關鍵路徑在哪個位置有分叉int flag; /一條關鍵路徑計算完的標志int k = 0; /用于一條關鍵路徑計算完以后從新計算下一條關鍵路徑的入口char num; /當發(fā)生分叉時用于交換的中間變量while(count 0)flag =

19、0;k = 0;while (flag != 1)if (k = 0 | tk.start = tsign.end) /如果活動源點或是上一活動的結束事件此次活動的開始事件則輸出couttk.start ;sign = k;if (tk.end = g-adjlistg-n-1.data.num)couttk.endendl;flag = 1;count -;k+;if (tk.start = tsign.start) /如果有分叉即兩活動的開始事件相同、結束事件不同時就將兩項活動 /的結束事件交換，以便計算下一條路徑時不發(fā)生重復num = tk-1.end;tk-1.end = tk.end

20、;tk.end = num; 8、所有操作的入口：void Interface() /所有操作的入口，主函數(shù)通過調用此函數(shù)來完成相關操作char choose1, choose2, ch;int flag1, flag2;docout|-歡迎使用!-|endl;cout| |endl;cout S - 退出 - Q -|endl;cout| |endl;cout|-|endl;coutchoose1;if (choose1 = S | choose1 = s)ALGraph *G = new ALGraph;do flag1 = 1;CreateGraph(G);if (!TopSort(G)

21、cout圖中有回路!請檢查后重新輸入!endl;flag1 = 0; while (!flag1); EventInfo(G);cout Y - No any key - ch; if (ch = Y | ch = y )OutputGraph(G);coutn工程的最短工期為：adjlistG-n-1.data.vl天endl;KeyActs(G);KeyPath(G);cout Y - 退出系統(tǒng) any key -choose2;if (choose2 = Y | choose2 = y)flag2 = 1;else coutn- 謝謝使用!歡迎再次使用! -endl;flag2 = 0;

22、coutendlendl;else if (choose1 = Q | choose1 = q)coutn- 謝謝使用!歡迎再次使用! -endl;exit(1);else coutn操作有誤! 請重新選擇：nendl; while (flag2);三、系統(tǒng)實現(xiàn)： 1、源代碼見報告尾部； 2、調試分析，測試數(shù)據(jù)及界面如下：四、設計總結：由于上學期時間緊張，關鍵路徑這塊基本上沒有理解，通過這次課程設計，我選了這個課題，一是為了讓自己能很好的掌握這個知識點，二是為了在得分的壓力下把輸出多條關鍵路徑的這個算法寫出來。但是在做的過程中才真正發(fā)現(xiàn)這個算法并不是那么簡單，我花了幾乎一天半的時間就為了把它寫

23、出來，但是一直無果，然后又在圖書館查閱大量書籍，雖然還是沒有找到相關算法，但是在查閱的過程中我學習到了很多算法思想，這應該是我這次課程設計最大的收獲吧。這個算法的實現(xiàn)其實來的很突然，我在草稿紙上不停地畫圖分析以及上機實驗，就在不知不覺中這個算法就實現(xiàn)了，這我從中明白：任何事不能只想不做，要善于分析和勤于動手，才有可能達到我們期望的效果。我從這次課程設計中所得的另外一個很大的收獲是：不能因為問題難就逃避它，只有勇于嘗試才可能解決根本問題。數(shù)據(jù)結構這門課程對我們學習好這個專業(yè)很重要，在以后，我會盡量利用我的空閑時間把以前不熟的和掌握不牢固的知識點再學習一遍，讓它成為一門為我所用的課程。五、附件（完

24、整源代碼）：#include #include #define MAXV 50typedef struct/頂點類型char num; /頂點編號int out_d; /頂點出度int in_d; /頂點入度int ve; /頂點所表示的事件的最早發(fā)生時間int vl; /頂點所表示的事件的最遲發(fā)生時間Vertex;typedef struct arcnode/弧的結點結構類型char start; /該弧的起點, 表示此弧所代表的活動開始事件char end; /該弧的終點，表示此弧所代表的活動的結束事件int vp; /該弧的終點在鄰接表中的位置int time; /完成該弧所表示的活動所

25、需的時間int e; /該弧所代表的活動的最早開始時間int l; /該弧所代表的活動的最遲開始時間int d; /該弧所代表的活動可以拖延的時間, 當d = 0時表示此活動為關鍵活動struct arcnode *nextarc; /指向下一條弧的指針ArcNode;typedef struct/鄰接表頭結點的類型 Vertex data; /該頂點的相關信息ArcNode *firstarc; /指向第一條弧 VNode;typedef struct int n, e;/圖中頂點數(shù)和邊數(shù)VNode adjlistMAXV; /鄰接鏈表ALGraph;int Max(int x, int y

26、)return (x y ? x : y);int Min(int x, int y)return (x y ? x : y);void CreateGraph(ALGraph *g) /創(chuàng)建有向圖的鄰接鏈表ArcNode *p; int i, j, k, n, e, t, sign;coutn請輸入事件總數(shù)和活動總數(shù)：ne;if (n = 0) | (e n-1)cout數(shù)據(jù)有誤，請檢查后重新輸入!n = n;g-e = e; for( i = 0; i adjlisti.data.num = i+65; g-adjlisti.firstarc = NULL;g-adjlisti.data.

27、in_d = g-adjlisti.data.out_d = 0;g-adjlisti.data.ve = g-adjlisti.data.vl = 0;coutn請輸入各項活動的開始事件和結束事件的編號及所需時間：n;for( k = 1; k = e; k+)cout第kijt;p = new ArcNode;p-start = i+65; p-end = j+65;p-vp = j;p-time = t;g-adjlisti.data.out_d+;g-adjlistj.data.in_d+; p-nextarc = g-adjlisti.firstarc;g-adjlisti.firs

28、tarc = p;void EventInfo(ALGraph *g) /計算各事件及活動的相關信息ArcNode *p = new ArcNode; int i, k;g-adjlist0.data.ve = 0; /對于源點，置其ve = 0for (i = 0; i n; i +) /計算各頂點所表示事件的最早發(fā)生時間vep = g-adjlisti.firstarc;while (p != NULL) k = p-vp;if (g-adjlistk.data.ve != 0) /如果該事件的ve已經有值，則取源點到該事件的所有路徑長度的最大值g-adjlistk.data.ve = M

29、ax(g-adjlistk.data.ve, g-adjlisti.data.ve + p-time);else /否則就取當前計算出來的值g-adjlistk.data.ve = g-adjlisti.data.ve + p-time;p = p-nextarc;g-adjlistg-n-1.data.vl = g-adjlistg-n-1.data.ve; /對于匯點，置其vl = vefor (i = g-n - 1; i = 0; i -) /計算各頂點所表示事件的最遲發(fā)生時間vlp = g-adjlisti.firstarc;while (p != NULL) k = p-vp;if

30、 (g-adjlisti.data.vl != 0) /如果該事件的vl已經有值，則取該事件到匯點的最長路徑之差g-adjlisti.data.vl = Min(g-adjlisti.data.vl, g-adjlistk.data.vl - p-time);else /否則就取當前計算出來的值g-adjlisti.data.vl = g-adjlistk.data.vl - p-time;p = p-nextarc;for (i = 0; i n; i +) /計算各弧所代表的活動最早開始e、最遲開始l以及可以拖延的時間dp = g-adjlisti.firstarc;while (p !=

31、 NULL)k = p-vp;p-e = g-adjlisti.data.ve; /某活動的最早開始時間是該活動的起點所表示的事件的最早發(fā)生時間：e = vep-l = g-adjlistk.data.vl - p-time; /某活動的最遲開始時間l是該活動的終點所表示的事件的最遲開始時間與該活動的所需時間之差：l = vl-timep-d = p-l - p-e; /某活動可以推遲的時間是其最遲開始時間與最早開始時間之差p = p-nextarc;void OutputGraph(ALGraph *g) /輸出工程圖的相關信息couteventt ve:t vlendl;for (int

32、i = 0; i n; i +)coutadjlisti.data.numt adjlisti.data.vet adjlisti.data.vlendl; coutendl;for (i = 0; i n; i+)ArcNode *p = g-adjlisti.firstarc;while (p != NULL)cout(start,end);couttt et lt d t timeendl;couttt e t l t d t timenextarc;coutendl;coutnumt ve:t vlendl;for (i = 0; i n; i +)coutadjlisti.data.

33、numt adjlisti.data.vet adjlisti.data.vlendl; int TopSort(ALGraph *g) /用來判斷圖中是否有回路int i, j, sum = 0; /sum用來記錄輸出的頂點數(shù)，以判斷途中是否有回路int stMAXV, top = -1; /棧st的指針為topArcNode *p;for (i = 0; i n; i +)if (g-adjlisti.data.in_d = 0) /入度為0的頂點入棧top +;sttop = i;while (top -1) /棧不為空時就循環(huán)i = sttop; top-; /出棧/coutchar(

34、i+65)adjlisti.firstarc; /找第一個相鄰頂點while (p != NULL)j = p-vp;g-adjlistj.data.in_d -;if (g-adjlistj.data.in_d = 0) /入度為0的相鄰頂點入棧top +;sttop = j;p = p-nextarc; /找下一個相鄰頂點coutn);void KeyActs(ALGraph *g) /計算并輸出關鍵活動ArcNode *p;coutn關鍵活動有：endl;for (int i = 0; i n; i+)p = g-adjlisti.firstarc;while (p != NULL)if

35、 (p-d = 0) /如果p指向的活動是關鍵活動，就將此活動輸出cout (startendnextarc;coutendl;void KeyPath(ALGraph *g) /計算并輸出關鍵路徑ArcNode tMAXV, *p; /tMAVX數(shù)組用來存放代表關鍵活動的邊的信息int j = 0; /j指示t數(shù)組下標int count = 0; /記錄關鍵路徑的條數(shù)coutn關鍵路徑有：endl;for (int i = 0; i n; i +) p = g-adjlisti.firstarc;while (p != NULL)if (p-d = 0) tj.start = p-start;tj.end = p-end; j+;if (p-end = g-adjlistg-n-1.data.num) /當某活動的結束事件就是整個工程的結束事件時就出現(xiàn)一條關鍵路徑count +; p = p-nextarc;int sign; /sign用來標記關鍵路