關(guān)鍵路徑問題報告.doc

滁州學(xué)院課程設(shè)計報告課程名稱： 數(shù)據(jù)結(jié)構(gòu) 設(shè)計題目： 關(guān)鍵路徑問題 院 部： 計算機與信息工程 專 業(yè)： 網(wǎng)絡(luò)工程 組 別： 第六組 起止日期: 2012年4月9日 2012年6月24日 指導(dǎo)教師: 趙玉艷 計算機與信息工程學(xué)院二一二年制課程設(shè)計題目關(guān)鍵路徑問題組長柯焱芳學(xué)號2011211384班級網(wǎng)工113班院部計算機工程系專業(yè)網(wǎng)絡(luò)工程組員靳夢婷 李鵬飛 陸勇 劉宜雨指導(dǎo)教師趙玉艷課程設(shè)計目的1鞏固和加深學(xué)生對數(shù)據(jù)結(jié)構(gòu)課程基本知識的理解，綜合該課程中所學(xué)的理論知識，獨立或聯(lián)合完成一個數(shù)據(jù)結(jié)構(gòu)應(yīng)用課題的設(shè)計；2根據(jù)選題需要，通過查閱手冊和文獻資料，培養(yǎng)分析和解決實際問題的能力；3熟練掌握圖的各種基本數(shù)據(jù)結(jié)構(gòu)的定義、存儲結(jié)構(gòu)和相應(yīng)的算法，并可熟練利用c語言進行實現(xiàn)；4具有一定的算法設(shè)計和分析能力，掌握選用合適的數(shù)據(jù)結(jié)構(gòu)解決實際問題的方法；5學(xué)會撰寫課程設(shè)計報告，能做出簡單答辯；6培養(yǎng)嚴肅認真的工作作風(fēng)和嚴謹求實的科學(xué)態(tài)度。課程設(shè)計所需環(huán)境 實驗設(shè)備：PC機 操作系統(tǒng)：Windows XP 開發(fā)環(huán)境：Visio C+6.0課程設(shè)計任務(wù)要求要求學(xué)生理解圖的特征和性質(zhì)，掌握各類圖的存儲結(jié)構(gòu)、相關(guān)操作的程序?qū)崿F(xiàn)以及圖的應(yīng)用，能夠利用圖的遍歷、圖的最小生成樹、最短路徑、關(guān)鍵路徑、拓撲排序等原理解決實際問題。課程設(shè)計工作進度計劃序號起止日期工 作 內(nèi) 容分工情況14.09-4.16選題與分析課題內(nèi)容，查找資料柯焱芳：選題與分析課題內(nèi)容陸勇 靳夢婷 李鵬飛 劉宜雨：查找資料24.17-4.25編寫創(chuàng)建圖，求最大路徑的函數(shù)劉宜雨 靳夢婷：創(chuàng)建圖李鵬飛 陸勇：求最大路徑34.26-5.16編寫總代碼和主函數(shù)（求關(guān)鍵路徑）柯焱芳：編寫總代碼和主函數(shù)（求關(guān)鍵路徑）45.17-5.25對程序輸入改寫柯焱芳 靳夢婷：對程序輸入改寫55.26-6.10對程序進行測試柯焱芳 靳夢婷 劉宜雨 陸勇 李鵬飛66.11-6.24整理文檔與總結(jié) 柯焱芳 陸勇指導(dǎo)教師簽字： 年 月 日院（系）審核意見院長（主任）簽字： 年 月 日數(shù)據(jù)結(jié)構(gòu)課程設(shè)計報告目 錄1 引言12 需求分析12.1問題描述12.2基本要求12.3目的23 概要設(shè)計23.1數(shù)據(jù)類型23.2 程序流程圖24 詳細設(shè)計34.1文件輸入34.2創(chuàng)建圖的函數(shù)34.3求關(guān)鍵路徑45 關(guān)鍵路徑測試76 課程設(shè)計總結(jié)與體會10參考文獻11附錄12致謝17數(shù)據(jù)結(jié)構(gòu)課程設(shè)計報告1 引言 當(dāng)一項工程劃分為若干個子任務(wù)或活動后，人們不僅需要確定這些活動的先后次序，而且需要進一步計算完成整個工程的時間，確定哪些活動是影響工程進度的關(guān)鍵活動，以便合理地組織人力、物力、財力，加快這些活動的進度，為按時或提前完成整個工程提供保證，這就是關(guān)鍵路徑問題。關(guān)鍵路徑問題相應(yīng)的網(wǎng)稱為AOE網(wǎng)，其中：頂點表示事件，邊表示活動，邊上的權(quán)表示活動持續(xù)的時間。AOE-網(wǎng)可以用來估算工程的完成時間。 它可以使人了解研究某個工程至少需要多少時間?哪些活動是影響工程進度的關(guān)鍵？由于AOE-網(wǎng)中的有些活動可以并行進行，從開始點到各個頂點，以致從開始點到完成點的有向路徑可能不止一條，這些路徑的長度也可能不同。完成不同路徑的活動所需的時間雖然不同，但只有各條路徑上所有活動都完成了，這個工程才算完成。因此，完成工程所需的最短時間是從開始點到完成點的最長路徑的長度，即在這條路徑上的所有活動的持續(xù)時間之和.這條路徑長度就叫做關(guān)鍵路徑。2 需求分析2.1問題描述 （1）選取建圖的一種算法建立圖，有鄰接矩陣，鄰接表，十字鏈表，鄰接多重表等多種方法，要選取一種適當(dāng)?shù)姆椒ńD，才能提高算法效率，降低時間復(fù)雜度和空間復(fù)雜度。（2）兩個相鄰頂點與它們之間的邊表示活動，邊上的數(shù)字表示活動延續(xù)的時間。對于給出的事件AOE網(wǎng)絡(luò)，要求求出從起點到終點的所有路徑，經(jīng)分析、比較后找出長讀最大的路徑，從而得出求關(guān)鍵路徑的算法，并給出計算機上機實現(xiàn)的源程序。完成不同路徑的活動所需的時間雖然不同，但只有各條路徑上所有活動都完成了，這個工程才算完成。具體要解決的問題有如下四個：（1）將項目中的各項活動視為有一個時間屬性的結(jié)點，從項目起點到終點進行排列； （2）用有方向的線段標出各結(jié)點的緊前活動和緊后活動的關(guān)系，使之成為一個有方向的網(wǎng)絡(luò)圖； （3）用正推法和逆推法計算出各個活動的最早開始時間，最晚開始時間，最早完工時間和最遲完工時間，并計算出各個活動的時差； （4） 找出所有時差為零的活動所組成的路線，即為關(guān)鍵路徑； 2.2基本要求 （1）選取建圖的一種算法建立圖： 選取鄰接表的算法來建立圖，是一種順序+ 鏈式存儲結(jié)構(gòu)。用順序表存放頂點，為每個頂點建立一個單鏈表，單鏈表中的結(jié)點表示依附于該頂點的邊或以該頂點為尾的弧。（2）兩個相鄰頂點與它們之間的邊表示活動，邊上的數(shù)字表示活動延續(xù)的時間參照該工程所化的AOE-網(wǎng)，求出從起點到終點的所有路徑，然后通過拓撲排序和逆拓撲排序求出最早與最晚發(fā)生時間，找出長度最大的路徑，從而求得關(guān)鍵路徑。 2.3目的在該部分，即需求分析中，根據(jù)設(shè)計題目的要求，充分地分析和理解問題，敘述系統(tǒng)的功能要求，明確問題要求做什么，以及限制條件是什么。 程序所能達到的功能：通過輸入所要構(gòu)建的圖的頂點數(shù)，弧數(shù)，創(chuàng)建圖，并打印出來，對圖進行拓撲排序，求得此圖的最早發(fā)生時間和最遲發(fā)生時間，并求得關(guān)鍵活動和關(guān)鍵路徑，打印出來。3 概要設(shè)計求關(guān)鍵路徑必須在拓撲排序的前提下進行，有環(huán)圖不能求關(guān)鍵路徑；只有縮短關(guān)鍵活動的工期才有可能縮短工期；若一個關(guān)鍵活動不在所有的關(guān)鍵路徑上，減少它并不能減少工期； 只有在不改變關(guān)鍵路徑的前提下，縮短關(guān)鍵活動才能縮短整個工期。關(guān)鍵路徑：從源點到匯點的路徑長度最長的路徑叫關(guān)鍵路徑?；顒娱_始的最早時間e(i)；活動開始的最晚時間l(i)；定義e(i)=l(i)的活動叫關(guān)鍵活動；事件開始的最早時間ve(i)；事件開始的最晚時間vl(i)。在程序中進行根據(jù)課程要求，需要對數(shù)據(jù)進行文件輸入，所以建文件夾，在文件夾里建input文本文檔，在文本文檔里寫入要輸入的數(shù)，通過對文檔的調(diào)用，對程序進行數(shù)據(jù)輸入，在文件夾建output文本文檔， 程序輸出到屏幕和文件 。3.1數(shù)據(jù)類型typedef struct node/邊表結(jié)點 int adjvex; /鄰接點編號int dut; /弧的信息 struct node *next; /下一條弧指針edgenode; typedef struct /頂點表結(jié)點 int projectname;/頂點域 int id;/頂點的入度信息 edgenode *link; /邊表頭指針 vexnode; 3.2 程序流程圖開始文件輸入求最大路徑，打印關(guān)鍵路徑主函數(shù)：求關(guān)鍵路徑結(jié)束 圖3-1程序流程圖4 詳細設(shè)計 4.1文件輸入 根據(jù)課程設(shè)計要求需要對程序進行文件輸入，對文件輸入的才做如下FILE *fp1,*fp2;if(fp2= fopen(ouput.txt,w)=NULL)fprintf(fp2, 打開文件失敗);return 0;if(fp1 = fopen(qq2.txt,r)=NULL)fprintf(fp2, 打開文件失敗);return 0;4.2創(chuàng)建圖的函數(shù) 在創(chuàng)建圖的過程中begin,end,duttem分別代表弧的前節(jié)點，尾節(jié)點，活動時間，在用文件對其進行數(shù)據(jù)輸入，并存儲到鄰接表內(nèi).輸入e條弧，建立AOE網(wǎng)的存儲結(jié)構(gòu)。void CreateGraphic(vexnode* Graphicmap,int projectnumber,int activenumber,FILE *fp1,FILE *fp2) int begin,end,duttem; edgenode *p; for(int i=0;iprojectnumber;i+) Gjectname=i; Graphicmapi.id =0; Graphicmapi.link =NULL; printf(n); printf(請輸入某項目的信息，并請用整形數(shù)字表示（格式：弧頭，弧尾，權(quán)值）：n); fprintf(fp2,n); fprintf(fp2,請輸入某項目的信息，并請用整形數(shù)字表示（格式：弧頭，弧尾，權(quán)值）：n); for(int k=0;kadjvex =end-1; p-dut =duttem; Graphicmapend-1.id +; p-next =Graphicmapbegin-1.link ; Graphicmapbegin-1.link =p; 4.3求關(guān)鍵路徑在求關(guān)鍵路徑時，用逆拓撲排序來求活動Ai最遲完成開始時間，即從最后一個節(jié)點減去最短的時間，求出整個活動的最短完成時間和活動Ai最早完成時間，當(dāng)最早完成時間和最遲完成時間相減為零時，即可求出關(guān)鍵路徑。根據(jù)各頂點的ve和vl值，求每條弧s（活動）的最早開始時間e(s)和最晚開始時間l(s)，其中e(s)=l(s)的為關(guān)鍵活動。int SearchMapPath(vexnode* Graphicmap,int projectnumber,int activenumber,int &totaltime,FILE *fp2) int i,j,k,m=0; int front=-1,rear=-1; int* topologystack=(int*)malloc(projectnumber*sizeof(int); int* vl=(int*)malloc(projectnumber*sizeof(int); int* ve=(int*)malloc(projectnumber*sizeof(int); int* l=(int*)malloc(activenumber*sizeof(int); int* e=(int*)malloc(activenumber*sizeof(int); edgenode *p; totaltime=0; for(i=0;iprojectnumber;i+) vei=0; for(i=0;iadjvex ; Graphicmapk.id -; if(vej+p-dut vek) vek=vej+p-dut ; if(Graphicmapk.id =0) topologystack+rear=k; p=p-next ; if(mprojectnumber) fprintf(fp2,n本程序所建立的圖有回路不可計算出關(guān)鍵路徑!n); fprintf(fp2,將退出本程序！n); return 0; totaltime=veprojectnumber-1; for(i=0;i=0;i-) j=topologystacki; p=Graphicmapj.link ; while(p) k=p-adjvex ; if(vlk-p-dut )dut ; p=p-next ; i=0; printf(n); printf(| 起點 | 終點 | 最早開始時間 | 最遲完成時間 | 差值 | 備注 n); fprintf(fp2,n); fprintf(fp2,| 起點 | 終點 | 最早開始時間 | 最遲完成時間 | 差值 | 備注 n); for(j=0;jadjvex ; e+i=vej; li=vlk-p-dut; printf(| %4d | %4d | %11d | %11d | %3d |,Gjectname +1,Gjectname +1,ei,li,li-ei); fprintf(fp2,| %4d | %4d | %11d | %11d | %3d |,Gjectname +1,Gjectname +1,ei,li,li-ei); if(li=ei) fprintf(fp2, 關(guān)鍵活動 ,權(quán)值%4d,Gjectname +1,Gjectname +1,p-dut); printf( 關(guān)鍵活動 ,權(quán)值%2d,Gjectname +1,Gjectname +1,p-dut); fprintf(fp2,n); printf(n); p=p-next ; return 1;5 關(guān)鍵路徑測試程序完成后，在輸入文件里輸入不同的數(shù)據(jù)，對程序進行調(diào)試，不同的輸入數(shù)據(jù)出現(xiàn)不同的結(jié)果：當(dāng)程序通過input文本文檔進行輸入數(shù)據(jù)如圖5-1，通過程序運行，結(jié)果輸出在屏幕（圖5-2）。圖5-1input文件內(nèi)容圖5-2input文件輸出的結(jié)果當(dāng)輸入的圖會出現(xiàn)回路時，即qq1文檔顯示的數(shù)據(jù)如圖5-3.由于出現(xiàn)回路，無法運行，出現(xiàn)結(jié)果如圖5-4.圖5-3 qq1文件內(nèi)容圖5-4 qq1文件的輸出結(jié)果.對下圖進行程序測試圖5-5 活動圖將上述圖表示的數(shù)據(jù)輸入到文本文檔qq2中如圖5-6所示，在通過程序?qū)崿F(xiàn)可得出關(guān)鍵路徑輸出如圖5-7所示。圖5-6 qq2文件內(nèi)容圖5-7 qq2文件輸出結(jié)果6 課程設(shè)計總結(jié)與體會課程設(shè)計的題目是關(guān)鍵路徑問題：當(dāng)一項工程劃分為若干個子任務(wù)或活動后，人們不僅需要確定這些活動的先后次序，而且需要進一步計算完成整個工程的時間，確定哪些活動是影響工程進度的關(guān)鍵活動，以便合理地組織人力、物力、財力，加快這些活動的進度，為按時或提前完成整個工程提供保證。設(shè)計的程序，當(dāng)你輸入一個AOE網(wǎng)，就可以求出這個AOE網(wǎng)的關(guān)鍵活動。程序還是有很多不足，程序輸入時只能輸入整形數(shù)據(jù)，而非整形的輸入則會導(dǎo)致程序異常停止 ，但是因為整形的輸入方式已貫穿整個程序，若要修改只能另外重做整個程序，所以暫不考慮修改，而打算做一個判錯系統(tǒng)，判斷若非整形的輸入則報錯。歷時兩個月數(shù)據(jù)結(jié)構(gòu)課程設(shè)計終于可以落幕了。在整個課程設(shè)計過程中，我們學(xué)到了好多知識，例如文件輸入是去年學(xué)的，由于一直沒有使用過，所以無從下手，又一次鉆到課本與資料里。自己查資料弄出來的程序總是死機，最后找學(xué)長幫忙，程序就是那一點點的小錯誤造成的死機。但最后我們還是學(xué)會了，以后再編寫程序需要用文件輸入是就會小菜一碟。其次，關(guān)于課程設(shè)計報告方面的編寫，老師對我們的要求非常嚴格，對課程設(shè)計報告的要求與畢業(yè)設(shè)計的格式相當(dāng)，在學(xué)校網(wǎng)站下載了一個模版，因為寫過數(shù)字邏輯報告，知道報告單復(fù)雜度不比編程序簡單，有大堆的要求、規(guī)定、格式等，完成起來卻真的很麻煩也很辛苦。在抱著電腦，奮斗了好今天的幸苦下，終于把報告完成了，通過對報告的編寫，對于個是我們學(xué)會了很多，以后遇到要編寫報告，就不會像初次這樣費時費力。我認為這樣的課程設(shè)計比較有意義，獨立完成資料的搜集以及課設(shè)的內(nèi)容，然后獨立的做出報告，讓這個過程很完整，無論是知識方面、還是報告的書寫方面，都學(xué)到了更多的東西。還有團隊合作，團隊的分工合作也很重要。參考文獻1 嚴蔚敏 吳偉民.數(shù)據(jù)結(jié)構(gòu)（c語言版本）.北京:清華大學(xué)出版社,1997.42 何欽銘 顏暉.C語言程序設(shè)計.北京：高等教育出版社，2008.13 胡學(xué)鋼.數(shù)據(jù)結(jié)構(gòu)（c語言版本）北京：高等教育出版社，2008.10附錄#include#includetypedef struct node int adjvex; int dut; struct node *next; edgenode;typedef struct int projectname; int id; edgenode *link; vexnode;void CreateGraphic(vexnode* Graphicmap,int projectnumber,int activenumber,FILE *fp1,FILE *fp2) int begin,end,duttem; edgenode *p; for(int i=0;iprojectnumber;i+) Gjectname=i; Graphicmapi.id =0; Graphicmapi.link =NULL; printf(n); printf(請輸入某項目的信息，并請用整形數(shù)字表示（格式：弧頭，弧尾，權(quán)值）：n); fprintf(fp2,n); fprintf(fp2,請輸入某項目的信息，并請用整形數(shù)字表示（格式：弧頭，弧尾，權(quán)值）：n); for(int k=0;kadjvex =end-1; p-dut =duttem; Graphicmapend-1.id +; p-next =Graphicmapbegin-1.link ; Graphicmapbegin-1.link =p; int SearchMapPath(vexnode* Graphicmap,int projectnumber,int activenumber,int &totaltime,FILE *fp2) int i,j,k,m=0; int front=-1,rear=-1; int* topologystack=(int*)malloc(projectnumber*sizeof(int); int* vl=(int*)malloc(projectnumber*sizeof(int); int* ve=(int*)malloc(projectnumber*sizeof(int); int* l=(int*)malloc(activenumber*sizeof(int); int* e=(int*)malloc(activenumber*sizeof(int); edgenode *p; totaltime=0; for(i=0;iprojectnumber;i+) vei=0; for(i=0;iadjvex ; Graphicmapk.id -; if(vej+p-dut vek) vek=vej+p-dut ; if(Graphicmapk.id =0) topologystack+rear=k; p=p-next ; if(mprojectnumber) fprintf(fp2,n本程序所建立的圖有回路不可計算出關(guān)鍵路徑!n); fprintf(fp2,將退出本程序！n); return 0; totaltime=veprojectnumber-1; for(i=0;i=0;i-) j=topologystacki; p=Graphicmapj.link ; while(p) k=p-adjvex ; if(vlk-p-dut )dut ; p=p-next ; i=0; printf(n); printf(| 起點 | 終點 | 最早開始時間 | 最遲完成時間 | 差值 | 備注 n); fprintf(fp2,n); fprintf(fp2,| 起點 | 終點 | 最早開始時間 | 最遲完成時間 | 差值 | 備注 n); for(j=0;jadjvex ; e+i=vej; li=vlk-p-dut; printf(| %4d | %4d | %11d | %11d | %3d |,Gjectname +1,Gjectname +1,ei,li,li-ei); fprintf(fp2,| %4d | %4d | %11d | %11d | %3d |,Gjectname +1,Gjectname +1,ei,li,li-ei); if(li=ei) fprintf(fp2, 關(guān)鍵活動 ,權(quán)值%4d,Gjectname +1,Gjectname +1,p-dut); printf( 關(guān)鍵活動 ,權(quán)值%2d,Gjectname +1,Gjectname +1,p-dut); fprintf(fp2,n); printf(n); p=p-next ; return 1;int main() FILE *fp1,*fp2;if(fp2= fopen(ouput.txt,w)=NULL)fprintf(fp2, 打開文件失敗);return 0;if(fp1 = fopen(qq2.txt,r)=NULL)fprintf(fp2, 打開文件失敗);ret