數(shù)據結構求關鍵路徑實習報告.doc

河 南 工 程 學 院實 習 報 告系（部） 專 業(yè) 班 級 姓 名 學 號 2011 年 7月 1日實 習 （訓） 報 告 評 語等 級： 評閱人： 職稱： 年月日河南工程學院實習（訓）報告實習內容： 關鍵路徑問題 實習時間：自 6 月 27 日 至 7 月 1 日 共5 天實習地點： 實習單位： 指導教師： 系主任： 目 錄一、設計目標1二、課題分析與設計21課題需求分析22存儲結構設計23算法設計34程序流程圖4三、程序清單5四、測試91測試數(shù)據92測試結果及分析9五、總結111收獲112不足113算法改進分析11 11一、設計目標用帶權有向圖構造的AOE網表示一項工程計劃，圖的結點表示事件，弧表示活動，權值表示活動持續(xù)時間。完成工程的最短時間是從開始點到完成點的最長路徑的長度。路徑長度最長的路徑叫關鍵路徑。關鍵路徑上的所有活動都是關鍵活動。求關鍵路徑必須在拓撲排序的前提下進行，有環(huán)圖不能求關鍵路徑；只有縮短關鍵活動的工期才有可能縮短工期；若一個關鍵活動不在所有的關鍵路徑上，減少它并不能減少工期；只有在不改變關鍵路徑的前提下，縮短關鍵活動才能縮短整個工期。本次實訓設計程序，任意給出表示工程計劃的頂點及帶權弧的有向圖信息，即可判斷整項工程計劃是否合理，求出工程計劃中的關鍵路徑及關鍵活動。完成整項工程至少需要的時間。二、課題分析與設計1課題需求分析1.1問題描述：（1）選取建圖的一種算法建立圖，有鄰接矩陣，鄰接表，十字鏈表，鄰接多重表等多種方法，要選取一種適當?shù)姆椒ńD，才能提高算法效率，降低時間復雜度和空間復雜度。（2）兩個相鄰頂點與它們之間的邊表示活動，邊上的數(shù)字表示活動延續(xù)的時間。對于給出的事件AOE網絡，要求求出從起點到終點的所有路徑，經分析、比較后找出長讀最大的路徑，從而得出求關鍵路徑的算法，并給出計算機上機實現(xiàn)的源程序。完成不同路徑的活動所需的時間雖然不同，但只有各條路徑上所有活動都完成了，這個工程才算完成。具體要解決的問題有如下四個：1） 將項目中的各項活動視為有一個時間屬性的結點，從項目起點到終點進行排列； 2） 用有方向的線段標出各結點的緊前活動和緊后活動的關系，使之成為一個有方向的網絡圖； 3） 用正推法和逆推法計算出各個活動的最早開始時間，最晚開始時間，最早完工時間和最遲完工時間，并計算出各個活動的時差； 4） 找出所有時差為零的活動所組成的路線，即為關鍵路徑； 1.2 基本要求（1）選取建圖的一種算法建立圖；選取鄰接表的算法來建立圖，是一種順序+ 鏈式存儲結構。用順序表存放頂點，為每個頂點建立一個單鏈表，單鏈表中的結點表示依附于該頂點的邊或以該頂點為尾的弧。（2）兩個相鄰頂點與它們之間的邊表示活動，邊上的數(shù)字表示活動延續(xù)的時間。參照該工程所化的AOE-網，求出從起點到終點的所有路徑，然后通過拓撲排序和逆拓撲排序求出最早與最晚發(fā)生時間，找出長度最大的路徑，從而求得關鍵路徑。2存儲結構設計對于帶權有向圖構造的AOE網，采用鏈式存儲結構，定義的結構體如下：typedef struct node /定義表結點 int adjvex; /該弧所指向的頂點的位置 int dut; /弧的權值 struct node *next; /指向下一條弧的指針 edgenode; typedef struct /定義頭結點 int projectname; /頂點信息 int id; /結點入度 edgenode *link; /指向第一條依附該頂點的弧的指針vexnode; 3算法設計3.1 算法準備為求關鍵路徑，設開始點是V1，從V1到Vi的最長路徑長度叫做事件Vi的最早發(fā)生時間。這個時間決定了所有以Vi為尾的弧所表示的活動的最遲開始時間。用e(i)表示活動ai的最早開始時間。用l(i)表示活動的最遲開始時間，即在不推遲整個工程完成的前提下，活動ai最遲必須開始的時間。兩者之差l(i)-e(i)意味著完成活動ai的時間余量。其中l(wèi)(i)=e(i)的活動叫做關鍵活動。用ve(i) 表示事件開始的最早時間，vl(i)表示事件開始的最晚時間。設活動ai由弧(即從頂點j到k)表示，其持續(xù)時間記為dut(),則：e(i)=ve(j)l(i)=vl(k)-dut()求ve(i)和vl(j)分兩步：（1）.從ve(1)=0開始向前遞推ve(j)=Max ve(i)+dut() T,2=j=n其中，T是所有以j為弧頭的弧的集合。（2）.從vl(n)=ve(n)開始向后遞推vl(i)=Min vl(j)-dut() S,1=i=n-1其中，S是所有以i為弧尾的弧的集合。兩個遞推公式是在拓撲有序和逆拓撲有序的前提下進行。3.2 算法步驟(1)輸入e條弧，建立AOE網的存儲結構。(2)從源點v1出發(fā)，令ve(1)=0,按拓撲有序求其余各頂點的最早發(fā)生時間ve(i)（2=i=n）。如果得到的拓撲有序序列中頂點個數(shù)小于網中頂點數(shù)n，則說明網中存在環(huán)，不能求關鍵路徑，算法終止；否則執(zhí)行步驟3。 (3)從匯點vn出發(fā)，令vl(n)=ve(n),求 按逆拓撲有序求其余各頂點的最遲發(fā)生時間vl(i)（1=i=n-1）。(4)根據各頂點的ve和vl值，求每條弧s（活動）的最早開始時間e(s)和最晚開始時間l(s)，若某條弧滿足條件e(s)=l(s)，則為關鍵活動。4程序流程圖 三、程序清單#include #include #include #include typedef struct node /定義表結點 int adjvex; /該弧所指向的頂點的位置 int dut; /弧的權值 struct node *next; /指向下一條弧的指針 edgenode; typedef struct /定義頭結點 int projectname; /頂點信息 int id; /結點入度 edgenode *link; /指向第一條依附該頂點的弧的指針vexnode; void CreateGraphic(vexnode* G,int prnum,int actnum) /創(chuàng)建圖 int begin,end,duttem; edgenode *p; for(int i=0;iprnum;i+) Gjectname=i; Gi.id=0; Gi.link=NULL; printf(某項目的開始到結束在圖中的結點輸入n); printf(如：3,4,9 回車表示第三節(jié)點到第四結點之間的活動用了9個單位時間n); for(int k=0;kadjvex=end-1; p-dut=duttem; Gend-1.id+; p-next=Gbegin-1.link ; Gbegin-1.link=p; int SearchMapPath(vexnode* G,int prnum,int actnum,int& totaltime) /尋找關鍵活動 int i,j,k,m=0; int front=-1,rear=-1; int*topologystack=(int*)malloc(prnum*sizeof(int);/用來保存拓撲排列 int*vl=(int*)malloc(prnum*sizeof(int);/用來表示在不推遲整個工程的前提下，VJ允許最遲發(fā)生的時間 int*ve=(int*)malloc(prnum*sizeof(int);/用來表示Vj最早發(fā)生時間 int*l=(int*)malloc(actnum*sizeof(int);/用來表示活動Ai最晚發(fā)生時間 int*e=(int*)malloc(actnum*sizeof(int);/表示活動最早發(fā)生時間edgenode *p; totaltime=0; for(i=0;iprnum;i+) vei=0; for(i=0;iadjvex ; Gk.id-; if(vej+p-dutvek) vek=vej+p-dut ; if(Gk.id=0) topologystack+rear=k; p=p-next ; if(mprnum) printf(n本程序所建立的圖有回路不可計算出關鍵路徑n); printf(將退出本程序n); return 0; totaltime=veprnum-1; for(i=0;i=0;i-) j=topologystacki; p=Gj.link ; while(p) k=p-adjvex ; if(vlk-p-dut)dut ; p=p-next ; i=0; printf(| 起點 | 終點 | 最早發(fā)生時間 | 最晚發(fā)生時間 | 差值 | 備注 |n); for(j=0;jadjvex ; e+i=vej; li=vlk-p-dut; printf(| %4d | %4d | %4d | %4d | %4d |,Gjectname +1,Gjectname +1,ei,li,li-ei); if(li=ei) printf( 關鍵活動 |); printf(n); p=p-next ; return 0; void mintime () /計算整個工程所用的最短時間 int pn,an,totaltime=0; system(cls); printf(請輸入這個工程的化成圖形的結點數(shù):); scanf(%d,&pn); printf(請輸入這個工程的活動數(shù):); scanf(%d,&an); vexnode* Graphicmap=(vexnode*)malloc(pn*sizeof(vexnode); CreateGraphic(Graphicmap,pn,an); SearchMapPath(Graphicmap,pn,an,totaltime); printf(整個工程所用的最短時間為：%d個單位時間n,totaltime); system(pause); int main() char ch; for(;) do system(cls); printf(| 歡迎進入求關鍵路徑算法程序 |); for(int i=0;i25;i+)printf( ); printf(%s,(S)tart開始輸入工程的結點數(shù)據并求出關鍵路徑n); printf(%s,(E)xit退出n); printf(%s,請輸入選擇:); scanf(%c,&ch); ch=toupper(ch); while(ch!=S&ch!=E); switch(ch) caseS: mintime (); break; caseE: return 0; 四、測試1測試數(shù)據表示工程計劃的帶權有向圖測試數(shù)據如下：頂點集為V=v1，v2，v3，v4，v5，v6；弧集為S=, ；八條弧依次對應的權值為3，2，2，3，4，3，2，1。2測試結果及分析結果表示此項工程的關鍵路徑為：V1V3v4V6242關鍵活動有,。五、總結1收獲通過這次實訓，使我學到了很多。由于對標準C語言缺乏深入的學習，致使我在編程中遇到了很多困難，但在攻克困難的過程中提高了自己的自學能力，分析問題及解決問題的能力、熟練運用理論知識的能力。同時，讓我更深入的掌握了有關AOE網表示工程計劃及關鍵路徑問題等方面的知識，鞏固了所學內容。然而，盡管這次的實習是獨立的個人工作，但在完成課程設計遇到困難時，也得到了很多老師的指導和同學的幫助。這次實訓，促進了我與同學們之間的友誼，也讓我明白了合作的重要性，提高了自己的合作能力。 在實訓過程中收獲了很多的豐富的經驗知識，更加深了我對一些算法和新知識的理解與應用，讓我受益匪淺。2不足這次實訓也讓我認識到了自己在很多方面