數(shù)據(jù)結(jié)構(gòu)課程設(shè)計(jì)：拓?fù)渑判蚝完P(guān)鍵路徑.doc

數(shù)據(jù)結(jié)構(gòu)課程設(shè)計(jì)報(bào)告 1 ABSTRACT1.1圖和棧的結(jié)構(gòu)定義struct SqStack/棧部分SElemType *base;/棧底指針SElemType *top;/棧頂指針int stacksize;/棧的大小int element_count;/棧中元素個(gè)素;/AOE網(wǎng)的存儲(chǔ)結(jié)構(gòu)struct ArcNode /表結(jié)點(diǎn)int lastcompletetime;/活動(dòng)最晚開(kāi)始時(shí)間int adjvex; /點(diǎn)結(jié)點(diǎn)位置int info; /所對(duì)應(yīng)的弧的權(quán)值struct ArcNode *next;/指向下一個(gè)表結(jié)點(diǎn)指針;struct VNode /點(diǎn)結(jié)點(diǎn)VertexType data; /結(jié)點(diǎn)標(biāo)志int indegree; /該結(jié)點(diǎn)入度數(shù)int ve; /記錄結(jié)點(diǎn)的最早開(kāi)始時(shí)間 int vl; /記錄結(jié)點(diǎn)的最晚開(kāi)始時(shí)間struct ArcNode *first_out_arc; /存儲(chǔ)下一個(gè)出度的表結(jié)點(diǎn)struct ArcNode *first_in_arc;/存儲(chǔ)下一個(gè)入度的表結(jié)點(diǎn);struct ALGraphVNode *vertices; /結(jié)點(diǎn)數(shù)組int vexnum; /結(jié)點(diǎn)數(shù)int arcnum; /弧數(shù) int kind; /該圖的類型 ;2 系統(tǒng)總分析2.1關(guān)鍵路徑概念分析2.1.1什么是關(guān)鍵路徑關(guān)鍵路徑法(Critical Path Method, CPM)最早出現(xiàn)于20世紀(jì)50年代，它是通過(guò)分析項(xiàng)目過(guò)程中哪個(gè)活動(dòng)序列進(jìn)度安排的總時(shí)差最少來(lái)預(yù)測(cè)項(xiàng)目工期的網(wǎng)絡(luò)分析。這種方法產(chǎn)生的背景是，在當(dāng)時(shí)出現(xiàn)了許多龐大而復(fù)雜的科研和工程項(xiàng)目，這些項(xiàng)目常常需要運(yùn)用大量的人力、物力和財(cái)力，因此如何合理而有效地對(duì)這些項(xiàng)目進(jìn)行組織，在有限資源下以最短的時(shí)間和最低的成本費(fèi)用下完成整個(gè)項(xiàng)目就成為一個(gè)突出的問(wèn)題，這樣CPM就應(yīng)運(yùn)而生了。 對(duì)于一個(gè)項(xiàng)目而言，只有項(xiàng)目網(wǎng)絡(luò)中最長(zhǎng)的或耗時(shí)最多的活動(dòng)完成之后，項(xiàng)目才能結(jié)束，這條最長(zhǎng)的活動(dòng)路線就叫關(guān)鍵路徑（Critical Path），組成關(guān)鍵路徑的活動(dòng)稱為關(guān)鍵活動(dòng)。2.1.2關(guān)鍵路徑特點(diǎn) 關(guān)鍵路徑上的活動(dòng)持續(xù)時(shí)間決定了項(xiàng)目的工期，關(guān)鍵路徑上所有活動(dòng)的持續(xù)時(shí)間總和就是項(xiàng)目的工期。關(guān)鍵路徑上的任何一個(gè)活動(dòng)都是關(guān)鍵活動(dòng)，其中任何一個(gè)活動(dòng)的延遲都會(huì)導(dǎo)致整個(gè)項(xiàng)目完工時(shí)間的延遲。 關(guān)鍵路徑上的耗時(shí)是可以完工的最短時(shí)間量，若縮短關(guān)鍵路徑的總耗時(shí)，會(huì)縮短項(xiàng)目工期；反之，則會(huì)延長(zhǎng)整個(gè)項(xiàng)目的總工期。但是如果縮短非關(guān)鍵路徑上的各個(gè)活動(dòng)所需要的時(shí)間，也不至于影響工程的完工時(shí)間。 關(guān)鍵路徑上活動(dòng)是總時(shí)差最小的活動(dòng)，改變其中某個(gè)活動(dòng)的耗時(shí)，可能使關(guān)鍵路徑發(fā)生變化?？梢源嬖诙鄺l關(guān)鍵路徑，它們各自的時(shí)間總量肯定相等，即可完工的總工期。關(guān)鍵路徑是相對(duì)的，也可以是變化的。在采取一定的技術(shù)組織措施之后，關(guān)鍵路徑有可能變?yōu)榉顷P(guān)鍵路徑，而非關(guān)鍵路徑也有可能變?yōu)殛P(guān)鍵路徑。 2.2關(guān)鍵路徑實(shí)現(xiàn)過(guò)程2.2.1結(jié)構(gòu)選取首先要選取建圖的一種算法建立圖，有鄰接矩陣，鄰接表，十字鏈表，鄰接多重表等多種方法，要選取一種適當(dāng)?shù)姆椒ńD，才能提高算法效率，降低時(shí)間復(fù)雜度和空間復(fù)雜度。兩個(gè)相鄰頂點(diǎn)與它們之間的邊表示活動(dòng)，邊上的數(shù)字表示活動(dòng)延續(xù)的時(shí)間。對(duì)于給出的事件AOE網(wǎng)絡(luò)，要求求出從起點(diǎn)到終點(diǎn)的所有路徑，經(jīng)分析、比較后找出長(zhǎng)讀最大的路徑，從而得出求關(guān)鍵路徑的算法，并給出計(jì)算機(jī)上機(jī)實(shí)現(xiàn)的源程序。完成不同路徑的活動(dòng)所需的時(shí)間雖然不同，但只有各條路徑上所有活動(dòng)都完成了，這個(gè)工程才算完成。2.2.2具體要解決的問(wèn)題（1） 將項(xiàng)目中的各項(xiàng)活動(dòng)視為有一個(gè)時(shí)間屬性的結(jié)點(diǎn)，從項(xiàng)目起點(diǎn)到終點(diǎn)進(jìn)行排列； （2） 用有方向的線段標(biāo)出各結(jié)點(diǎn)的緊前活動(dòng)和緊后活動(dòng)的關(guān)系，使之成為一個(gè)有方向的網(wǎng)絡(luò)圖； （3） 用正推法和逆推法計(jì)算出各個(gè)活動(dòng)的最早開(kāi)始時(shí)間，最晚開(kāi)始時(shí)間，最早完工時(shí)間和最遲完工時(shí)間，并計(jì)算出各個(gè)活動(dòng)的時(shí)差； （4） 找出所有時(shí)差為零的活動(dòng)所組成的路線，即為關(guān)鍵路徑； （5） 識(shí)別出準(zhǔn)關(guān)鍵路徑，為網(wǎng)絡(luò)優(yōu)化提供約束條件；2.2.3算法分析（1）求關(guān)鍵路徑必須在拓?fù)渑判虻那疤嵯逻M(jìn)行，有環(huán)圖不能求關(guān)鍵路徑；（2）只有縮短關(guān)鍵活動(dòng)的工期才有可能縮短工期；（3）若一個(gè)關(guān)鍵活動(dòng)不在所有的關(guān)鍵路徑上，減少它并不能減少工期； （4）只有在不改變關(guān)鍵路徑的前提下，縮短關(guān)鍵活動(dòng)才能縮短整個(gè)工期。（5）關(guān)鍵路徑：從源點(diǎn)到匯點(diǎn)的路徑長(zhǎng)度最長(zhǎng)的路徑叫關(guān)鍵路徑。（6）活動(dòng)的最早開(kāi)始時(shí)間e(i)；（7）活動(dòng)的最晚開(kāi)始時(shí)間l(i)；（8）定義e(i)=l(i)的活動(dòng)叫關(guān)鍵活動(dòng)；（9）事件的最早開(kāi)始時(shí)間ve(i)；（10）事件的最晚開(kāi)始時(shí)間vl(i)。設(shè)活動(dòng)ai由弧(即從頂點(diǎn)j到k)表示，其持續(xù)時(shí)間記為dut(),則： e(i)=ve(j) l(i)=vl(k)-dut() 求ve(i)和vl(j)分兩步： 1.從ve(1)=0開(kāi)始向前遞推ve(j)=Max ve(i)+dut() T,2=j=n 其中，T是所有以j為弧頭的弧的集合。 2.從vl(n)=ve(n)開(kāi)始向后遞推 vl(i)=Min vl(j)-dut() S,1=i=n-1 其中，S是所有以i為弧尾的弧的集合。兩個(gè)公式是在拓?fù)溆行蚝湍嫱負(fù)溆行虻那疤嵯逻M(jìn)行。2.2.4 算法步驟（1）輸入e條弧，建立AOE網(wǎng)的存儲(chǔ)結(jié)構(gòu)。（2）從源點(diǎn)v1出發(fā)，令ve(1)=0,求個(gè)點(diǎn)的最早開(kāi)始時(shí)間ve(j)。（3）從匯點(diǎn)vn出發(fā)，令vl(n)=最大值，求個(gè)點(diǎn)的最晚開(kāi)始時(shí)間vl(j)。（4）由于各結(jié)點(diǎn)的最早開(kāi)始時(shí)間已求出來(lái)，所以各活動(dòng)的最早開(kāi)始時(shí)間即（每條弧s（活動(dòng)）的最早開(kāi)始時(shí)間）就等于該結(jié)點(diǎn)的最早開(kāi)始時(shí)間，并由上可同時(shí)求出該活動(dòng)的最晚開(kāi)始時(shí)間l(j)。（5）具體表達(dá)式為： e(i)=ve(j) l(i)=vl(k)-dut() （6）當(dāng)結(jié)點(diǎn)的最早開(kāi)始時(shí)間ve(j)=最晚開(kāi)始時(shí)間時(shí)vl(j)，則該結(jié)點(diǎn)為關(guān)鍵結(jié)點(diǎn)。（7）當(dāng)活動(dòng)的最早開(kāi)始時(shí)間e(j)=最晚開(kāi)始時(shí)間時(shí)l(j)，則該結(jié)點(diǎn)為關(guān)鍵活動(dòng)。3 主要功能模塊設(shè)計(jì)3.1程序模塊棧部分模塊Status InitStack(SqStack &S) /初始化棧Status DestroyStack(SqStack &S)/銷(xiāo)毀棧Status ClearStack(SqStack &S)/清空棧Status StackEmpty(SqStack S)/判斷是否為空Status StackEmpty(SqStack S)/判斷是否為空Status Pop(SqStack &S,SElemType &e) /彈出元素Status GetElement(SqStack &S,int position,SElemType &e) /取元素，非彈出,i為要去元素位置無(wú)向圖（AOE網(wǎng)）部分模塊void CreateALGraph(ALGraph &graph)/初始化AOE網(wǎng)Status TopologicalSort(ALGraph &graph,SqStack &ToPoReverseSort) /求拓?fù)渑判騍tatus PutInfoToPoSort(SqStack temp,ALGraph graph) /輸出拓?fù)漤樞蚺判?當(dāng)拓?fù)湫蛄写嬖跁r(shí)）Status GetVeAndVl(ALGraph &graph,SqStack OrderSort,SqStack RevSort) /求出結(jié)點(diǎn)和活動(dòng)的最晚開(kāi)始時(shí)間和最早開(kāi)始時(shí)間Status CriticalPath(ALGraph &graph,SqStack RevSort) /求出關(guān)鍵活動(dòng)和關(guān)鍵事件并輸出4 系統(tǒng)詳細(xì)設(shè)計(jì)4.1主函數(shù)模塊 main函數(shù)首先調(diào)用SqStack ToPoSort;SqStack ToPoReverseSort;函數(shù)來(lái)定義棧，調(diào)用InitStack(ToPoSort);來(lái)初始化存拓?fù)渑判虻臈：虸nitStack(ToPoReverseSort);來(lái)初始化逆拓?fù)渑判虻臈?。其次調(diào)用CreateALGraph(ALGraph &graph)函數(shù)定義和初始化AOE網(wǎng)，調(diào)用TopologicalSor t(ALGraph &graph,SqStack &ToPoReverseSort) 函數(shù)求拓?fù)湫蛄泻驼{(diào)用PutInfoToPoSort(ToPoSort,graph);函數(shù)來(lái)輸出輸出拓?fù)漤樞蚺判?。然后調(diào)用GetVeAndVl(graph,ToPoSort,ToPoReverseSort) 函數(shù)求結(jié)點(diǎn)和活動(dòng)的最晚開(kāi)始時(shí)間、最早開(kāi)始時(shí)間并輸出。最后調(diào)用Status CriticalPath(ALGraph &graph,SqStack RevSort)函數(shù)來(lái)求關(guān)鍵活動(dòng)、關(guān)鍵事件并輸出。4.2初始化模塊初始化模塊用來(lái)初始化圖，要求用戶自己輸入數(shù)據(jù)，并程序構(gòu)造AOE網(wǎng)。本程序是用自己改進(jìn)的鄰接表來(lái)構(gòu)造AOE網(wǎng)。見(jiàn)圖2-4-2 4.3求拓?fù)湫蛄心K 利用棧來(lái)存儲(chǔ)入度為零的結(jié)點(diǎn)，然后逐個(gè)彈出，來(lái)進(jìn)行與該結(jié)點(diǎn)的出度結(jié)點(diǎn)來(lái)比較，是否符合拓?fù)渑判虻囊?guī)則，最后用ToPoReverseSort存放拓?fù)淠嫘蛐蛄衼?lái)完成整個(gè)拓?fù)渑判?。?jiàn)圖2-4-34.4求最晚開(kāi)始時(shí)間和最早開(kāi)始時(shí)間模塊 （包括結(jié)點(diǎn)和活動(dòng)的最早和最晚開(kāi)始時(shí)間）見(jiàn)圖2-4-44.5關(guān)鍵活動(dòng)和關(guān)鍵事件 見(jiàn)圖2-4-54.6輸出模塊輸出相應(yīng)結(jié)點(diǎn)的信息，拓?fù)湫蛄?，以及事件的最早開(kāi)始時(shí)間和最晚開(kāi)始時(shí)間，輸出相應(yīng)的活動(dòng)的最早開(kāi)始時(shí)間和最晚開(kāi)始時(shí)間，關(guān)鍵活動(dòng)以及關(guān)鍵事件。5 測(cè)試分析5.1測(cè)試內(nèi)容求的關(guān)鍵路徑為：程序輸入部分：求拓?fù)湫蛄胁糠智蠼Y(jié)點(diǎn)和活動(dòng)的最早開(kāi)始時(shí)間和最晚開(kāi)始時(shí)間輸出圖中的關(guān)鍵事件和關(guān)鍵活動(dòng)（關(guān)鍵路徑）測(cè)試關(guān)鍵路徑結(jié)果：5.2回路測(cè)試結(jié)果分析：結(jié)果完全符合所求，但是輸出的方面不夠完美，并且自我感覺(jué)程序所使用的空間比較大，算法復(fù)雜度較高，所以效率比較低下，當(dāng)程序輸入存在有環(huán)的時(shí)候，程序沒(méi)有發(fā)生任何錯(cuò)誤，直接輸出“圖存在有環(huán)”然后退出程序。由此可見(jiàn)本程序計(jì)劃實(shí)施到完工比較順利的完成了，并且在程序測(cè)試中能夠得到預(yù)期的結(jié)果出來(lái)，不過(guò)唯一不滿意的是程序過(guò)于復(fù)雜化，使用的太多的空間，致使程序成為一個(gè)缺陷。參考文獻(xiàn)1 嚴(yán)蔚敏，吳偉民.數(shù)據(jù)結(jié)構(gòu). 北京：清華大學(xué)出版社，2006.2 譚浩強(qiáng). C程序設(shè)計(jì)（第二版）作者：清華大學(xué)出版社，2006心得體會(huì)經(jīng)歷幾天的編程之后，課程設(shè)計(jì)終于結(jié)束了。一開(kāi)始整個(gè)程序不知道怎么開(kāi)始，而且算法是怎么樣的都不知道，不過(guò)經(jīng)過(guò)一番的查書(shū)、翻閱資料、上網(wǎng)查找之后終于了解到整個(gè)算法流程以及實(shí)現(xiàn)，首先，關(guān)鍵路徑的實(shí)現(xiàn)是用鄰接表來(lái)存儲(chǔ)的，對(duì)于這個(gè)來(lái)說(shuō)，本人覺(jué)得單純按照書(shū)本的鄰接表來(lái)做不太合適，于是就自己改進(jìn)了一個(gè)鄰接表，加上在結(jié)點(diǎn)里加上存儲(chǔ)入度的變量，和加上指向所以入度的表的指針。并且在表結(jié)構(gòu)上加上入度表結(jié)構(gòu)。由于搜集了很多關(guān)于關(guān)鍵路徑的資料，包括幾種不同思路的程序代碼，以及程序流程。然后看懂并整理這些代碼，然后再其基礎(chǔ)上增加自己需要的功能，按照自己的意愿來(lái)修改與完善。在程序輸入部分采用結(jié)點(diǎn)，結(jié)點(diǎn)，?。唇Y(jié)點(diǎn)和結(jié)點(diǎn)之間的權(quán)值），由于輸入貫穿整個(gè)程序部分，所以輸入部分十分重要。之后創(chuàng)建整個(gè)程序的結(jié)構(gòu)，其中包括入度和出度的表結(jié)點(diǎn)，這兩個(gè)都依附在結(jié)點(diǎn)結(jié)構(gòu)之上。在程序求關(guān)鍵路徑的時(shí)候，首先必須要求出整個(gè)圖的拓?fù)渑判?，并用棧?lái)保存起來(lái)，然后并在主函數(shù)里定義了兩個(gè)棧，分別來(lái)存儲(chǔ)順序拓?fù)渑判蚝湍嫘蛲負(fù)渑判?，其中在求拓?fù)渑判虻臅r(shí)候就遇到了一個(gè)問(wèn)題就是結(jié)點(diǎn)存儲(chǔ)的度數(shù)發(fā)生變化了，這個(gè)問(wèn)題在后來(lái)的時(shí)候才發(fā)現(xiàn)的，因?yàn)橹筮€需要用到入度數(shù)，由此，在求拓?fù)湫蛄械臅r(shí)候必須把入度數(shù)先用一個(gè)數(shù)組來(lái)存起來(lái)，然后求完拓?fù)湫蛄兄蟊仨毎颜麄€(gè)結(jié)點(diǎn)的入度數(shù)還原。/保留入度度數(shù)/int *indegree_copy=(int *)malloc(sizeof(int)*graph.vexnum);for(i=0;iindegree ;/還原入度度數(shù)/for(i=0;iindegree=*(indegree_copy+i) ;/最后按照拓?fù)涞捻樞蛐蛄星蟪鼋Y(jié)點(diǎn)的最早開(kāi)始時(shí)間，但是源結(jié)點(diǎn)的最早開(kāi)始時(shí)間必須賦予一定的值，所以按照順序的拓?fù)湫蛄胁⑶疫€可以求出活動(dòng)的最早開(kāi)始時(shí)間。再次，按照逆序拓?fù)湫蛄衼?lái)求出結(jié)點(diǎn)和活動(dòng)的最晚開(kāi)始時(shí)間。然后根據(jù)算法就可以輕易的求出關(guān)鍵路徑和關(guān)鍵事件。其中在編譯過(guò)程中出現(xiàn)了一個(gè)編譯的異常，上網(wǎng)找了一下，說(shuō)是指針越界了，于是，再設(shè)斷點(diǎn)等手段經(jīng)過(guò)長(zhǎng)時(shí)間的摸索之后就發(fā)現(xiàn)了原來(lái)是程序中的棧的部分出問(wèn)題了，由于之前都沒(méi)有過(guò)棧出問(wèn)題的情況，于是就改變了一下這個(gè)問(wèn)題就沒(méi)出現(xiàn)過(guò)了。教師評(píng)語(yǔ)附 錄程序源代碼：/ 關(guān)鍵路徑.cpp : 定義控制臺(tái)應(yīng)用程序的入口點(diǎn)。#include stdafx.h#include#include#define VertexType int/棧部分#define STACK_ADDITION sizeof(SElemType)#define SElemType int#define OK true#define ERROR false#define Status boolstruct SqStackSElemType *base;SElemType *top;int stacksize;int element_count;/元素個(gè)素;Status InitStack(SqStack &S) /初始化棧S.base =(SElemType *)malloc(STACK_ADDITION);S.stacksize =STACK_ADDITION;S.element_count =0;if(S.base =NULL)printf(malloc errorn);exit(0);elseS.top=S.base ;return OK;Status DestroyStack(SqStack &S)/銷(xiāo)毀棧if(S.base=NULL)printf(Stack is not existentn);elsedelete(S.base);return OK;Status ClearStack(SqStack &S)/清空棧if(S.base=NULL)printf(Stack is not existentn);else if(S.base =S.top )printf(Sack is NULLn);elseS.top=S.base ;S.element_count =0;return OK;Status StackEmpty(SqStack S)/判斷是否為空if(S.base=NULL)printf(Stack is not existentn);return false;if(S.top =S.base )return true;elsereturn false;Status Push(SqStack &S,SElemType e) /增加元素SElemType *temp1=S.base;SElemType *temp2=S.top;if(S.stacksize-(S.element_count *STACK_ADDITION)=STACK_ADDITION)S.base = (SElemType *)realloc(S.base ,(S.stacksize+STACK_ADDITION);S.stacksize+=STACK_ADDITION;S.top =S.base + (temp2-temp1);*S.top =e;S.top =S.top +1;S.element_count+;else*S.top =e;S.top =S.top+1;S.element_count+;return OK;Status Pop(SqStack &S,SElemType &e) /彈出元素if(S.top=S.base )printf(Stack is null! Pop error!n);return false;elsee=*-S.top ;S.element_count -;return OK;int StackLength(SqStack S)return S.element_count ;Status GetElement(SqStack &S,int position,SElemType &e) /取元素，非彈出,i為要去元素位置SElemType *temp;temp=S.top;if(S.top=S.base )printf(Stack is null! GetElement error!n);return false;else if(position=S.element_count)e=*(temp-position);return OK;elseprintf(error!由于輸入位置比棧元素?cái)?shù)目大);return false;/=struct ArcNode /表結(jié)點(diǎn)int lastcompletetime;/活動(dòng)最晚完成時(shí)間int adjvex; /點(diǎn)結(jié)點(diǎn)位置int info; /所對(duì)應(yīng)的弧的權(quán)值struct ArcNode *next;/下一個(gè)表結(jié)點(diǎn);struct VNode /點(diǎn)結(jié)點(diǎn)VertexType data; /標(biāo)志int indegree; /該結(jié)點(diǎn)入度數(shù)int ve; /記錄最早開(kāi)始時(shí)間 int vl; /記錄最晚開(kāi)始時(shí)間struct ArcNode *first_out_arc; /存儲(chǔ)下一個(gè)出度的表結(jié)點(diǎn)struct ArcNode *first_in_arc;/存儲(chǔ)下一個(gè)入度的表結(jié)點(diǎn);struct ALGraphVNode *vertices; /結(jié)點(diǎn)數(shù)組int vexnum; /結(jié)點(diǎn)數(shù)int arcnum; /弧數(shù) int kind; /該圖的類型;void CreateALGraph(ALGraph &graph)int temp1=1;int temp2=0;int temp3=0;/權(quán)int i=0;struct ArcNode *arc1=NULL;struct ArcNode *arc2=NULL;printf(請(qǐng)輸入結(jié)點(diǎn)數(shù)(結(jié)點(diǎn)由1開(kāi)始）和圖的類型：n);scanf(%d %d,&graph.vexnum,&graph.kind );graph.vertices =(VNode *)malloc(graph.vexnum+1)*sizeof(VNode);for(i=0;idata=i;(graph.vertices+i)-first_in_arc =NULL;(graph.vertices+i)-first_out_arc=NULL;(graph.vertices+i)-ve =0;(graph.vertices+i)-vl=0;(graph.vertices+i)-indegree =0;printf(請(qǐng)輸入(格式：點(diǎn)，點(diǎn)，兩點(diǎn)之間的權(quán)值n);graph.arcnum =-1;while(!(temp1=0&temp2=0&temp3=0)graph.arcnum+; /圖的弧數(shù)scanf(%d %d %d,&temp1,&temp2,&temp3);(graph.vertices +temp2)-indegree) +;if(graph.vertices+temp2)-first_in_arc=NULL)(graph.vertices+temp2)-first_in_arc =(ArcNode *)malloc(sizeof(ArcNode);(graph.vertices+temp2)-first_in_arc-adjvex =temp1;(graph.vertices+temp2)-first_in_arc-info =temp3;(graph.vertices+temp2)-first_in_arc-lastcompletetime =0;/活動(dòng)最晚完成時(shí)間初始化(graph.vertices+temp2)-first_in_arc-next =NULL;elsearc2=(graph.vertices+temp2)-first_in_arc;while(arc2-next!=NULL) /如果下一個(gè)不為空的話就存儲(chǔ)下一個(gè)地址arc2=arc2-next ;arc2-next =(ArcNode *)malloc(sizeof(ArcNode);arc2-next-adjvex =temp1;arc2-lastcompletetime =0;/活動(dòng)最晚完成時(shí)間初始化arc2-next-info =temp3;arc2-next-next =NULL;/=if(graph.vertices+temp1)-first_out_arc=NULL)(graph.vertices+temp1)-first_out_arc =(ArcNode *)malloc(sizeof(ArcNode);(graph.vertices+temp1)-first_out_arc-adjvex =temp2;(graph.vertices+temp1)-first_out_arc-info =temp3;(graph.vertices+temp1)-first_out_arc-lastcompletetime =0;/活動(dòng)最晚完成時(shí)間初始化(graph.vertices+temp1)-first_out_arc-next =NULL;elsearc1=(graph.vertices+temp1)-first_out_arc;while(arc1-next!=NULL) /如果下一個(gè)不為空的話就存儲(chǔ)下一個(gè)地址arc1=arc1-next ;arc1-next =(ArcNode *)malloc(sizeof(ArcNode);arc1-next-adjvex =temp2;arc1-next-info =temp3;arc1-next-lastcompletetime =0;/活動(dòng)最晚完成時(shí)間初始化arc1-next-next =NULL;/求拓?fù)渑判騍tatus TopologicalSort(ALGraph &graph,SqStack &ToPoReverseSort)SqStack S;struct ArcNode *p=NULL;int k=0;int i=0;int counter;/計(jì)算拓?fù)湫蛄械膫€(gè)數(shù)/保留入度度數(shù)/int *indegree_copy=(int *)malloc(sizeof(int)*graph.vexnum);for(i=0;iindegree ;/if(!InitStack(S)printf(初始化棧失敗);for(i=1;iindegree )Push(S,i);counter=0;i=0;while(!StackEmpty(S)Pop(S,i);Push(ToPoReverseSort,i);/用棧ToPoReverseSort存放拓?fù)淠嫘蛐蛄衏ounter+;for(p=(graph.vertices +i)-first_out_arc);p;p=p-next )k=p-adjvex ;if(!(-(graph.vertices +k)-indegree )Push(S,k);DestroyStack(S);/還原入度度數(shù)/for(i=0;iindegree=*(indegree_copy+i) ;/if(countergraph.vexnum )return ERROR;elsereturn OK;/輸出拓?fù)漤樞蚺判?當(dāng)拓?fù)湫蛄写嬖跁r(shí)）Status PutInfoToPoSort(SqStack temp,ALGraph graph)SElemType e=0;int j=temp.element_count;for(int i=1;idata ,e);return OK;/求出結(jié)點(diǎn)和活動(dòng)的最晚開(kāi)始時(shí)間和最早開(kāi)始時(shí)間Status GetVeAndVl(ALGraph &graph,SqStack OrderSort,SqStack RevSort)int i=0,j=0;int kk=0;struct ArcNode *p=NULL;SElemType e1;SElemType e2;/求出所有結(jié)點(diǎn)的最早開(kāi)始時(shí)間/Pop(OrderSort,e1);(graph.vertices+e1)-ve =1;kk=OrderSort.element_count;for(i=1;ifirst_in_arc);jindegree ;j+,p=p-next )if( (graph.vertices +e2)-ve adjvex )-ve + p-info )(graph.vertices +e2)-ve =(graph.vertices+ p-adjvex )-ve + p-info ;/求出所有結(jié)點(diǎn)的最晚開(kāi)始時(shí)間/Pop(RevSort,e1); /彈出拓?fù)湫蛄凶詈笠粋€(gè)元素for(i=1;ivl =2147483647;(graph.vertices+e1)-vl = (graph.vertices+e1)-ve ;/最晚開(kāi)始時(shí)間=最早開(kāi)始時(shí)間kk=RevSort.element_count;for(i=1;ifirst_out_arc);p;p=p-next )p-lastcompletetime =(graph.vertices+ p-adjvex )-vl) - (p-info) ;if( (graph.vertices +e2)-vl (graph.vertices+ p-adjvex )-vl) - (p-info) )(graph.vertices +e2)-vl =(graph.vertices+ p-adjvex )-vl) - (p-info) ;/printf(nn結(jié)點(diǎn)信息n);printf(結(jié)點(diǎn)t最早開(kāi)始時(shí)間t最晚開(kāi)始時(shí)間t入度數(shù)n);for(i=1;idata,(graph.vertices+i)-ve,(graph.vertices+i)-vl,(graph.vertices+i)-indegree);printf(n活動(dòng)信息n);printf(活動(dòng) 最早開(kāi)始時(shí)間 最