數(shù)據(jù)結(jié)構(gòu)課程設計拓撲排序和關鍵路徑

1、1 ABSTRACT1.1圖和棧的結(jié)構(gòu)定義struct SqStack/棧部分SElemType *base;/棧底指針SElemType *top;/棧頂指針int stacksize;/棧的大小int element_count;/棧中元素個素;/AOE網(wǎng)的存儲結(jié)構(gòu)struct ArcNode /表結(jié)點int lastcompletetime;/活動最晚開始時間int adjvex; /點結(jié)點位置int info; /所對應的弧的權(quán)值struct ArcNode *next;/指向下一個表結(jié)點指針;struct VNode /點結(jié)點VertexType data; /結(jié)點標志int ind

2、egree; /該結(jié)點入度數(shù)int ve; /記錄結(jié)點的最早開始時間 int vl; /記錄結(jié)點的最晚開始時間struct ArcNode *first_out_arc; /存儲下一個出度的表結(jié)點struct ArcNode *first_in_arc;/存儲下一個入度的表結(jié)點;struct ALGraphVNode *vertices; /結(jié)點數(shù)組int vexnum; /結(jié)點數(shù)int arcnum; /弧數(shù) int kind; /該圖的類型 ;2 系統(tǒng)總分析2.1關鍵路徑概念分析2.1.1什么是關鍵路徑關鍵路徑法(Critical Path Method, CPM)最早出現(xiàn)于20世紀50年

3、代，它是通過分析項目過程中哪個活動序列進度安排的總時差最少來預測項目工期的網(wǎng)絡分析。這種方法產(chǎn)生的背景是，在當時出現(xiàn)了許多龐大而復雜的科研和工程項目，這些項目常常需要運用大量的人力、物力和財力，因此如何合理而有效地對這些項目進行組織，在有限資源下以最短的時間和最低的成本費用下完成整個項目就成為一個突出的問題，這樣CPM就應運而生了。 對于一個項目而言，只有項目網(wǎng)絡中最長的或耗時最多的活動完成之后，項目才能結(jié)束，這條最長的活動路線就叫關鍵路徑（Critical Path），組成關鍵路徑的活動稱為關鍵活動。關鍵路徑特點 關鍵路徑上的活動持續(xù)時間決定了項目的工期，關鍵路徑上所有活動的持續(xù)時間總和就是

4、項目的工期。關鍵路徑上的任何一個活動都是關鍵活動，其中任何一個活動的延遲都會導致整個項目完工時間的延遲。 關鍵路徑上的耗時是可以完工的最短時間量，若縮短關鍵路徑的總耗時，會縮短項目工期；反之，則會延長整個項目的總工期。但是如果縮短非關鍵路徑上的各個活動所需要的時間，也不至于影響工程的完工時間。 關鍵路徑上活動是總時差最小的活動，改變其中某個活動的耗時，可能使關鍵路徑發(fā)生變化?？梢源嬖诙鄺l關鍵路徑，它們各自的時間總量肯定相等，即可完工的總工期。關鍵路徑是相對的，也可以是變化的。在采取一定的技術(shù)組織措施之后，關鍵路徑有可能變?yōu)榉顷P鍵路徑，而非關鍵路徑也有可能變?yōu)殛P鍵路徑。 2.2關鍵路徑實現(xiàn)過程結(jié)

5、構(gòu)選取首先要選取建圖的一種算法建立圖，有鄰接矩陣，鄰接表，十字鏈表，鄰接多重表等多種方法，要選取一種適當?shù)姆椒ńD，才能提高算法效率，降低時間復雜度和空間復雜度。兩個相鄰頂點與它們之間的邊表示活動，邊上的數(shù)字表示活動延續(xù)的時間。對于給出的事件AOE網(wǎng)絡，要求求出從起點到終點的所有路徑，經(jīng)分析、比較后找出長讀最大的路徑，從而得出求關鍵路徑的算法，并給出計算機上機實現(xiàn)的源程序。完成不同路徑的活動所需的時間雖然不同，但只有各條路徑上所有活動都完成了，這個工程才算完成。具體要解決的問題（1） 將項目中的各項活動視為有一個時間屬性的結(jié)點，從項目起點到終點進行排列； （2） 用有方向的線段標出各結(jié)點的緊

6、前活動和緊后活動的關系，使之成為一個有方向的網(wǎng)絡圖； （3） 用正推法和逆推法計算出各個活動的最早開始時間，最晚開始時間，最早完工時間和最遲完工時間，并計算出各個活動的時差； （4） 找出所有時差為零的活動所組成的路線，即為關鍵路徑； （5） 識別出準關鍵路徑，為網(wǎng)絡優(yōu)化提供約束條件；2.2.3算法分析（1）求關鍵路徑必須在拓撲排序的前提下進行，有環(huán)圖不能求關鍵路徑；（2）只有縮短關鍵活動的工期才有可能縮短工期；（3）若一個關鍵活動不在所有的關鍵路徑上，減少它并不能減少工期； （4）只有在不改變關鍵路徑的前提下，縮短關鍵活動才能縮短整個工期。（5）關鍵路徑 ：從源點到匯點的路徑長度最

7、長的路徑叫關鍵路徑。（6）活動的最早開始時間e(i)；（7）活動的最晚開始時間l(i)；（8）定義e(i)=l(i)的活動叫關鍵活動；（9）事件的最早開始時間ve(i)；（10）事件的最晚開始時間vl(i)。設活動ai由弧<j,k>(即從頂點j到k)表示，其持續(xù)時間記為dut(<j,k>),則： e(i)=ve(j) l(i)=vl(k)-dut(<j,k>)                      

8、60; 求ve(i)和vl(j)分兩步： 1.從ve(1)=0開始向前遞推ve(j)=Max ve(i)+dut(<i,j>)       <i,j>T,  2<=j<=n 其中，T是所有以j為弧頭的弧的集合。 2.從vl(n)=ve(n)開始向后遞推 vl(i)=Min vl(j)-dut(<i,j>)      <i,j>S,  1<=i<=n-1 其中，S是所有以i為弧尾的弧的集合。兩個公式是在拓撲有序和逆拓

9、撲有序的前提下進行。2.2.4 算法步驟（1）輸入e條弧<j,k>，建立AOE網(wǎng)的存儲結(jié)構(gòu)。（2）從源點v1出發(fā)，令ve(1)=0,求個點的最早開始時間ve(j)。（3）從匯點vn出發(fā)，令vl(n)=最大值，求個點的最晚開始時間vl(j)。（4）由于各結(jié)點的最早開始時間已求出來，所以各活動的最早開始時間即（每條弧s（活動）的最早開始時間）就等于該結(jié)點的最早開始時間，并由上可同時求出該活動的最晚開始時間l(j)。（5）具體表達式為： e(i)=ve(j) l(i)=vl(k)-dut(<j,k>) （6）當結(jié)點的最早開始時間ve(j)=最晚開始時間時vl(j)，則該結(jié)點為

10、關鍵結(jié)點。（7）當活動的最早開始時間e(j)=最晚開始時間時l(j)，則該結(jié)點為關鍵活動。3 主要功能模塊設計3.1程序模塊棧部分模塊Status InitStack(SqStack &S) /初始化棧Status DestroyStack(SqStack &S)/銷毀棧Status ClearStack(SqStack &S)/清空棧Status StackEmpty(SqStack S)/判斷是否為空Status StackEmpty(SqStack S)/判斷是否為空Status Pop(SqStack &S,SElemType &e) /彈出元素

11、Status GetElement(SqStack &S,int position,SElemType &e) /取元素，非彈出,i為要去元素位置無向圖（AOE網(wǎng)）部分模塊void CreateALGraph(ALGraph &graph)/初始化AOE網(wǎng)Status TopologicalSort(ALGraph &graph,SqStack &ToPoReverseSort) /求拓撲排序Status PutInfoToPoSort(SqStack temp,ALGraph graph) /輸出拓撲順序排序(當拓撲序列存在時）Status GetVe

12、AndVl(ALGraph &graph,SqStack OrderSort,SqStack RevSort) /求出結(jié)點和活動的最晚開始時間和最早開始時間Status CriticalPath(ALGraph &graph,SqStack RevSort) /求出關鍵活動和關鍵事件并輸出4 系統(tǒng)詳細設計4.1主函數(shù)模塊 main函數(shù)首先調(diào)用SqStack ToPoSort;SqStack ToPoReverseSort;函數(shù)來定義棧，調(diào)用InitStack(ToPoSort);來初始化存拓撲排序的棧和InitStack(ToPoReverseSort);來初始化逆拓撲排序的棧

13、。其次調(diào)用CreateALGraph(ALGraph &graph)函數(shù)定義和初始化AOE網(wǎng)，調(diào)用TopologicalSor t(ALGraph &graph,SqStack &ToPoReverseSort) 函數(shù)求拓撲序列和調(diào)用PutInfoToPoSort(ToPoSort,graph);函數(shù)來輸出輸出拓撲順序排序。然后調(diào)用GetVeAndVl(graph,ToPoSort,ToPoReverseSort) 函數(shù)求結(jié)點和活動的最晚開始時間、最早開始時間并輸出。最后調(diào)用Status CriticalPath(ALGraph &graph,SqStack R

14、evSort)函數(shù)來求關鍵活動、關鍵事件并輸出。4.2初始化模塊初始化模塊用來初始化圖，要求用戶自己輸入數(shù)據(jù)，并程序構(gòu)造AOE網(wǎng)。本程序是用自己改進的鄰接表來構(gòu)造AOE網(wǎng)。見圖2-4-2 4.3求拓撲序列模塊 利用棧來存儲入度為零的結(jié)點，然后逐個彈出，來進行與該結(jié)點的出度結(jié)點來比較，是否符合拓撲排序的規(guī)則，最后用ToPoReverseSort存放拓撲逆序序列來完成整個拓撲排序。見圖2-4-34.4求最晚開始時間和最早開始時間模塊 （包括結(jié)點和活動的最早和最晚開始時間）見圖2-4-44.5關鍵活動和關鍵事件 見圖2-4-54.6輸出模塊輸出相應結(jié)點的信息，拓撲序列，以及事件的最早開始時間和最晚開

15、始時間，輸出相應的活動的最早開始時間和最晚開始時間，關鍵活動以及關鍵事件。5 測試分析5.1測試內(nèi)容求的關鍵路徑為：程序輸入部分：求拓撲序列部分求結(jié)點和活動的最早開始時間和最晚開始時間輸出圖中的關鍵事件和關鍵活動（關鍵路徑）測試關鍵路徑結(jié)果：5.2回路測試結(jié)果分析：結(jié)果完全符合所求，但是輸出的方面不夠完美，并且自我感覺程序所使用的空間比較大，算法復雜度較高，所以效率比較低下，當程序輸入存在有環(huán)的時候，程序沒有發(fā)生任何錯誤，直接輸出“圖存在有環(huán)”然后退出程序。由此可見本程序計劃實施到完工比較順利的完成了，并且在程序測試中能夠得到預期的結(jié)果出來，不過唯一不滿意的是程序過于復雜化，使用的太多的空間，

16、致使程序成為一個缺陷。參考文獻1 嚴蔚敏，吳偉民.數(shù)據(jù)結(jié)構(gòu). 北京：清華大學出版社，2006.2 譚浩強. C程序設計（第二版）作者：清華大學出版社，2006心得體會經(jīng)歷幾天的編程之后，課程設計終于結(jié)束了。一開始整個程序不知道怎么開始，而且算法是怎么樣的都不知道，不過經(jīng)過一番的查書、翻閱資料、上網(wǎng)查找之后終于了解到整個算法流程以及實現(xiàn)，首先，關鍵路徑的實現(xiàn)是用鄰接表來存儲的，對于這個來說，本人覺得單純按照書本的鄰接表來做不太合適，于是就自己改進了一個鄰接表，加上在結(jié)點里加上存儲入度的變量，和加上指向所以入度的表的指針。并且在表結(jié)構(gòu)上加上入度表結(jié)構(gòu)。由于搜集了很多關于關鍵路徑的資料，包括幾種不同

17、思路的程序代碼，以及程序流程。然后看懂并整理這些代碼，然后再其基礎上增加自己需要的功能，按照自己的意愿來修改與完善。在程序輸入部分采用結(jié)點，結(jié)點，?。唇Y(jié)點和結(jié)點之間的權(quán)值），由于輸入貫穿整個程序部分，所以輸入部分十分重要。之后創(chuàng)建整個程序的結(jié)構(gòu)，其中包括入度和出度的表結(jié)點，這兩個都依附在結(jié)點結(jié)構(gòu)之上。在程序求關鍵路徑的時候，首先必須要求出整個圖的拓撲排序，并用棧來保存起來，然后并在主函數(shù)里定義了兩個棧，分別來存儲順序拓撲排序和逆序拓撲排序，其中在求拓撲排序的時候就遇到了一個問題就是結(jié)點存儲的度數(shù)發(fā)生變化了，這個問題在后來的時候才發(fā)現(xiàn)的，因為之后還需要用到入度數(shù)，由此，在求拓撲序列的時候必須把

18、入度數(shù)先用一個數(shù)組來存起來，然后求完拓撲序列之后必須把整個結(jié)點的入度數(shù)還原。/保留入度度數(shù)/int *indegree_copy=(int *)malloc(sizeof(int)*graph.vexnum);for(i=0;i<graph.vexnum;i+)*(indegree_copy+i)=(graph.vertices +i+1)->indegree ;/還原入度度數(shù)/for(i=0;i<graph.vexnum;i+)(graph.vertices +i+1)->indegree=*(indegree_copy+i) ;/最后按照拓撲的順序序列求出結(jié)點的最早

19、開始時間，但是源結(jié)點的最早開始時間必須賦予一定的值，所以按照順序的拓撲序列并且還可以求出活動的最早開始時間。再次，按照逆序拓撲序列來求出結(jié)點和活動的最晚開始時間。然后根據(jù)算法就可以輕易的求出關鍵路徑和關鍵事件。其中在編譯過程中出現(xiàn)了一個編譯的異常，上網(wǎng)找了一下，說是指針越界了，于是，再設斷點等手段經(jīng)過長時間的摸索之后就發(fā)現(xiàn)了原來是程序中的棧的部分出問題了，由于之前都沒有過棧出問題的情況，于是就改變了一下這個問題就沒出現(xiàn)過了。教師評語附 錄程序源代碼：/ 關鍵路徑.cpp : 定義控制臺應用程序的入口點。#include "stdafx.h"#include<stdio

20、.h>#include<stdlib.h>#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;/元素個素;Status InitStack(SqStack &S) /初始化棧S.base =(

21、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)/銷毀棧if(S.base=NULL)printf("Stack is not existentn");elsedelete(S.base);return OK;Status

22、 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;i

23、f(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.t

24、op =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 S

25、tackLength(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

26、OK;elseprintf("error!由于輸入位置比棧元素數(shù)目大");return false;/=struct ArcNode /表結(jié)點int lastcompletetime;/活動最晚完成時間int adjvex; /點結(jié)點位置int info; /所對應的弧的權(quán)值struct ArcNode *next;/下一個表結(jié)點;struct VNode /點結(jié)點VertexType data; /標志int indegree; /該結(jié)點入度數(shù)int ve; /記錄最早開始時間 int vl; /記錄最晚開始時間struct ArcNode *first_out_arc;

27、 /存儲下一個出度的表結(jié)點struct ArcNode *first_in_arc;/存儲下一個入度的表結(jié)點;struct ALGraphVNode *vertices; /結(jié)點數(shù)組int vexnum; /結(jié)點數(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("請輸入結(jié)點數(shù)(結(jié)點由1

28、開始）和圖的類型：n");scanf("%d %d",&graph.vexnum,&graph.kind );graph.vertices =(VNode *)malloc(graph.vexnum+1)*sizeof(VNode);for(i=0;i<=graph.vexnum;i+)(graph.vertices+i)->data=i;(graph.vertices+i)->first_in_arc =NULL;(graph.vertices+i)->first_out_arc=NULL;(graph.vertices+

29、i)->ve =0;(graph.vertices+i)->vl=0;(graph.vertices+i)->indegree =0;printf("請輸入(格式：點，點，兩點之間的權(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

30、) +;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

31、 =0;/活動最晚完成時間初始化(graph.vertices+temp2)->first_in_arc->next =NULL;elsearc2=(graph.vertices+temp2)->first_in_arc;while(arc2->next!=NULL) /如果下一個不為空的話就存儲下一個地址arc2=arc2->next ;arc2->next =(ArcNode *)malloc(sizeof(ArcNode);arc2->next->adjvex =temp1;arc2->lastcompletetime =0;/活動最

32、晚完成時間初始化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->inf

33、o =temp3;(graph.vertices+temp1)->first_out_arc->lastcompletetime =0;/活動最晚完成時間初始化(graph.vertices+temp1)->first_out_arc->next =NULL;elsearc1=(graph.vertices+temp1)->first_out_arc;while(arc1->next!=NULL) /如果下一個不為空的話就存儲下一個地址arc1=arc1->next ;arc1->next =(ArcNode *)malloc(sizeof(Ar

34、cNode);arc1->next->adjvex =temp2;arc1->next->info =temp3;arc1->next->lastcompletetime =0;/活動最晚完成時間初始化arc1->next->next =NULL;/求拓撲排序Status TopologicalSort(ALGraph &graph,SqStack &ToPoReverseSort)SqStack S;struct ArcNode *p=NULL;int k=0;int i=0;int counter;/計算拓撲序列的個數(shù)/保留入

35、度度數(shù)/int *indegree_copy=(int *)malloc(sizeof(int)*graph.vexnum);for(i=0;i<graph.vexnum;i+)*(indegree_copy+i)=(graph.vertices +i+1)->indegree ;/if(!InitStack(S)printf("初始化棧失敗");for(i=1;i<=graph.vexnum;i+)if(!(graph.vertices +i)->indegree )Push(S,i);counter=0;i=0;while(!StackEmpty

36、(S)Pop(S,i);Push(ToPoReverseSort,i);/用棧ToPoReverseSort存放拓撲逆序序列counter+;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;i<graph.vexnum;i+)(graph.vertices +i+1)->indegree=*(indegree_cop

37、y+i) ;/if(counter<graph.vexnum )return ERROR;elsereturn OK;/輸出拓撲順序排序(當拓撲序列存在時）Status PutInfoToPoSort(SqStack temp,ALGraph graph)SElemType e=0;int j=temp.element_count;for(int i=1;i<=j ;i+)Pop(temp,e);printf("該結(jié)點為V%d： 數(shù)組下標為：%dn",(graph.vertices +e)->data ,e);return OK;/求出結(jié)點和活動的最晚開始

38、時間和最早開始時間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é)點的最早開始時間/Pop(OrderSort,e1);(graph.vertices+e1)->ve =1;kk=OrderSort.element_count;for(i=1;i<=kk ;i+)Pop(OrderSort,e2);for(j=1,p=(graph.vert

39、ices +e2)->first_in_arc);j<=(graph.vertices+e2)->indegree ;j+,p=p->next )if( (graph.vertices +e2)->ve <(graph.vertices+ p->adjvex )->ve + p->info )(graph.vertices +e2)->ve =(graph.vertices+ p->adjvex )->ve + p->info ;/求出所有結(jié)點的最晚開始時間/Pop(RevSort,e1); /彈出拓撲序列最后一個元

40、素for(i=1;i<=graph.vexnum ;i+)(graph.vertices+i)->vl =2147483647;(graph.vertices+e1)->vl = (graph.vertices+e1)->ve ;/最晚開始時間=最早開始時間kk=RevSort.element_count;for(i=1;i<=kk ;i+)Pop(RevSort,e2);for(p=(graph.vertices +e2)->first_out_arc);p;p=p->next )p->lastcompletetime =(graph.vert

41、ices+ 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é)點信息n");printf("結(jié)點t最早開始時間t最晚開始時間t入度數(shù)n");for(i=1

42、;i<=graph.vexnum;i+)printf("V%dt%2dtt%2dtt%2dn",(graph.vertices+i)->data,(graph.vertices+i)->ve,(graph.vertices+i)->vl,(graph.vertices+i)->indegree);printf("n活動信息n");printf("活動 最早開始時間 最晚開始時間為n");for(i=1;i<=graph.vexnum ;i+)for(p=(graph.vertices +i)->first_out_arc);p;p=p->next )printf("<V%d,V%d>tt%dtt%dn",i,p->adjvex ,(graph.ve