數(shù)據(jù)結(jié)構(gòu)求關(guān)鍵路徑實(shí)習(xí)報(bào)告.doc

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