關(guān)鍵路徑問(wèn)題設(shè)計(jì)與實(shí)現(xiàn)

1、數(shù)據(jù)結(jié)構(gòu)的課程設(shè)計(jì) 報(bào)告題目：關(guān)鍵路徑問(wèn)題設(shè)計(jì)與實(shí)現(xiàn)班級(jí)：1612401學(xué)號(hào)：161240113姓名：張修鳴指導(dǎo)老師：孫涵完成日期：2014.1.3目 錄一需求分析二.程序主要功能.三程序運(yùn)行平臺(tái).程序類說(shuō)明模*分析.存在的不足對(duì)策.七體驗(yàn)感悟八.程序代碼.需求分析設(shè)計(jì)并實(shí)現(xiàn)關(guān)鍵路徑的一種應(yīng)用。序主要功能實(shí)現(xiàn)拓?fù)渑判蚝完P(guān)鍵路徑的發(fā)現(xiàn)。給出一個(gè)具體的應(yīng)用環(huán)境。序運(yùn)行平臺(tái)該程序是用VC+6.0制做的，使用Microsoft Visual C+ 6.0運(yùn)行該程序，具體操作是: 打開(kāi)Microsoft Visual C+ 6.0,菜單欄里點(diǎn)文件f打開(kāi)工作區(qū)f找到“圖書(shū)管理系統(tǒng)dsw” 這個(gè)文件f打開(kāi)，

2、或者在資源管理器中雙擊該文件，此時(shí)，VC+6.0會(huì)自動(dòng)打開(kāi)，并載入該 系統(tǒng)相關(guān)資源，點(diǎn)擊Run命令菜單或者或用快捷鍵Ctrl+F5運(yùn)行該程序。程序類說(shuō)明typedef struct node(int adjvex; /鄰接點(diǎn)域int time;/活動(dòng)持續(xù)時(shí)間 struct node *next;Node;Node *p;typedef struct VertexNode(int vertex; 頂點(diǎn)域int indegree; /入度域Node *firstedge; 邊表頭指針 AdjList20;typedef struct(AdjList adjlist;/鄰接表 int Dian;/頂

3、點(diǎn)數(shù)int Bian; /邊數(shù)ALGraph函數(shù)分析：void CreateALGraph(ALGraph *&G)建立有向圖int TopoSort(ALGraph *Gint s20,int ve20)/拓?fù)渑判虿⑶蟾黜旤c(diǎn)事件的最早發(fā)生時(shí)間及拓?fù)淠嫘蛄衖nt CriticalPath(ALGraph *G)/求 關(guān)鍵路徑和關(guān)鍵活動(dòng)塊分析文件的信息|又4理罪輯電宿式4 50 1 22 33 40 2 11 3 2關(guān)鍵活動(dòng)與關(guān)鍵路徑u Du Du生生生ny 發(fā)發(fā)發(fā)a 詛詛詛ss 曰w取repO t 0 2 5ey關(guān)鍵活動(dòng)：|U0,U1 ul,u2u2,u3匡鍵路徑是0-1 1-2 2-3存在的

4、不足與對(duì)策由于自身能力有限，所以沒(méi)有設(shè)計(jì)好交互界面。在設(shè)計(jì)過(guò)程中由于設(shè)計(jì)者的編程功底欠缺，因此學(xué)習(xí)過(guò)程較為艱辛，需要解決的問(wèn)題也比較 多。在以后的學(xué)習(xí)中，應(yīng)該循序漸進(jìn)，不可急于求成，先打好基礎(chǔ)，這樣才能更好地發(fā)展。體驗(yàn)感悟在編寫(xiě)程序的過(guò)程中，深切的體會(huì)到自身能力還有待提高，通過(guò)大規(guī)模的查詢網(wǎng)上資料 與相關(guān)書(shū)籍我學(xué)習(xí)到了很多以前不知道的編程方法與各種奇妙的函數(shù)語(yǔ)句時(shí)，提高了自 己對(duì)程序設(shè)計(jì)本身的興趣，更加樂(lè)意去學(xué)習(xí)這方面的新的東西，并在不斷地自我挑戰(zhàn)中 收獲著，或知識(shí)技能，或信心勇氣。希望自己在今后的學(xué)習(xí)中可以更好的完善自我。程序源代碼#includeusing namespace std;#i

5、nclude typedef struct node(int adjvex; 鄰接點(diǎn)域int time;/活動(dòng)持續(xù)時(shí)間struct node *next;Node;Node *p;typedef struct VertexNode(int vertex; 頂點(diǎn)域int indegree; / 入度域Node *firstedge; 邊表頭指針AdjList20;typedef struct(AdjList adjlist;/鄰接表 int Dian;/頂點(diǎn)數(shù)int Bian; 邊數(shù)ALGraph;void CreateALGraph(ALGraph *&G)建立有向圖(fstream fp;i

6、nt i,j,k,cost;Node *s;G=(ALGraph *)malloc(sizeof(ALGraph);fp.open(a.txt,ios:in);if(fp.fail()(cout G-Dian;fpG-Bian;/cout請(qǐng)輸各個(gè)入頂點(diǎn)號(hào)：adjlisti.vertex=i;G-adjlisti.firstedge=NULL;G-adjlisti.indegree=0;/cout請(qǐng)輸入各個(gè)邊的弧頭頂點(diǎn)弧尾頂點(diǎn)活動(dòng)持續(xù)時(shí)間(弧的長(zhǎng) 度):endl;for(k=0;kBian;k+)(fpi;fpj;fpcost;s=(Node*)malloc(sizeof(Node);s-adj

7、vex=j;s-time=cost;s-next=G-adjlisti.firstedge;G-adjlisti.firstedge=s;G-adjlistj.indegree+; int TopoSort(ALGraph *G,int s20,int ve20)拓?fù)渑判虿⑶蟾黜旤c(diǎn)事件的最早發(fā)生時(shí)間及拓?fù)淠嫘蛄衖nt i,j,k,num=0,n=0,stack20;Node *p;for(i=0;iDian;i+)計(jì)算各個(gè)頂點(diǎn)的入度(if(G-adjlisti.indegree=0)(stacknum=i;num+;for(i=0;iDian;i+)vei=0;while(num!=0)(j=

8、stacknum-1;sn=j;n+;num-;p=G-adjlistj.firstedge;while(p)(k=p-adjvex;G-adjlistk.indegree-;if(G-adjlistk.indegree=0)(stacknum=k;num+;if(vej+p-timevek)(vek=vej+p-time;p=p-next;if(nDian)return 0;else return 1;int CriticalPath(ALGraph *G)/求 關(guān)鍵路徑和關(guān)鍵活動(dòng)(int i,j,k,h=0;int ee,el,dut;int v120,ve20,T20,g40;int t

9、ag;if(!TopoSort(G,T,ve)(cout錯(cuò)誤!網(wǎng)中存在環(huán)Dian-1;for(i=G-Dian-1;i=0;i-)(j=Ti；p=G-adjlistj.firstedge;while(p!=NULL)(k=p-adjvex;dut=p-time;if(v1k-dutnext;cout關(guān)鍵活動(dòng)：endl;for(j=0;jDian;+j)for(p=G-adjlistj.firstedge;p;p=p-next)(k=p-adjvex;dut=p-time;ee=vej;el=v1k-dut;if(ee=el) (若兩者相等，說(shuō)明這這個(gè)活動(dòng)為關(guān)鍵活動(dòng)cout(j,k);cout vj,vk