1、-. z理工大學數據構造課程設計報告題目： 關鍵路徑的實現院系：計算機工程學院學生:班級：*:起迄日期: 2021.7.19指導教師: 艷 一、需求分析1.問題描述 找出實際工程中的關鍵路徑，合理安排關鍵活動的施工順序。要求：(1)表示工程的圖可以用鄰接表或鄰接矩陣存儲；(2)應能以圖形的方式輸出圖；(3)輸出關鍵路徑和關鍵活動。2.根本功能 (1)用鄰接表存儲有向圖并建立AOE網 CreateGraph； (2)用圖形的形式輸出有向圖Display(); (3)輸出關鍵路徑和關鍵活動 SearchMapPath；3.輸入輸出輸入: (1)有向圖的頂點數和弧數，都是int型，中間用空格隔開；

2、(2)圖中的各個頂點的值，char型; (3)圖中弧的權值、起點、終點,都是int型，中間用空格隔開； 輸出： 起點char、終點(char) 、最早開場時間(int)、最遲開場時間(int)、差值(int)、是否為關鍵活動、關鍵路徑。二、概要設計1.設計思路：(1) 輸入圖的頂點數和弧數。(2) 輸入這個圖中每段弧的起始點及權值。 (3) 用輸入的數據建立AOE網。(4)用鄰接表來存儲圖的這些信息。 (5) 用CreateGraph( )函數建立AOE圖。(6)用Display()函數輸出AOE圖。(7) 用SearchMapPath ( )函數求出最長路徑，并輸出關鍵路徑。(8) 編寫程序

3、。2.數據構造設計：1邏輯構造采用圖狀的構造。圖是一種較線性表和樹更為復雜的數據構造。在線性表中，數據元素之間僅有線性關系，每個數據元素只有一個直接前驅和一個直接后繼；在樹形構造中，數據元素之間有著明顯的層次關系，并且每一層上的數據元素可能和下一層中多個元素即其孩子結點相關，但只能和上一層中一個元素即其雙親結點相關；而在圖形構造中，結點之間的關系可以是任意的，圖中任意兩個數據元素之間都可能相關。而由于本程序的操作對象是有向圖，所以必須采用圖狀的構造。2存儲構造采用鏈式的構造。由于圖的構造比擬復雜，任意兩個頂點之間都可能存在聯系，因此無法以數據元素在存儲區中的物理位置來表示元素之間的關系，即圖沒

4、有順序映象的存儲構造，因此采用鏈式的存儲構造。3抽象數據類型圖的定義如下：ADT Graph 數據對象V：V是具有一樣特性的數據元素的集合，稱為頂點集。數據關系R： R=VR VR=|v,wV且Pv,w,表示從v到w的弧，謂詞Pv,w定義了弧的意義或信息根本操作P：CreateGraph(&G,V,VR );初始條件：V是圖的頂點集，VR是圖中弧的集合。操作結果：按V和VR的定義構造圖G。 SearchMapPath (&G,V,VR )；初始條件：V是圖的頂點集，VR是圖中弧的集合。操作結果：求出最長路徑，并輸出關鍵路徑。Display(&G,V,VR)；初始條件：V是圖的頂點集，VR是圖中

5、弧的集合。操作結果：以圖形的形式輸出圖。ADT Graph軟件構造設計：三、詳細設計定義程序中所有用到的數據及其數據構造: 鄰接表的存儲單元: typedef struct node int adjve*; int w; struct node *ne*tedge; edgenode; 表頭結點: typedef struct char data; int id;int *,y; /頂點的橫坐標、縱坐標 edgenode *firstedge; ve*node; 主函數和其他函數的偽碼算法:主函數：void main() int ve*number,arumber; printf(請輸入這個圖

6、中的節點數和弧數:); scanf(%d %d,&ve*number,&arumber); ve*node* Graph=(ve*node*)malloc(ve*number*sizeof(ve*node); CreateGraph(Graph,ve*number,arumber); SearchMapPath(Graph,ve*number,arumber); 建立AOE網函數：void CreateGraph(ve*node* Graph,int ve*number,int arumber) int begin,end,duttem; char ch; edgenode *p; /輸入頂點

7、信息存儲在頂點表中，并初始化該頂點的便表。 for(int i=0;ive*number;i+) Graphi.id =0; Graphi.firstedge =NULL; /輸入邊所依附的兩個頂點的序號i和j然后生成新的鄰接點序號為j的/邊表結點,將該結點插入到第i個表頭部。printf(請輸入這個圖中的各個頂點的值:n); for(i=0;ive*number;i+) scanf(%s,&ch); Graphi.data=ch; printf(請輸入圖中弧的權值、起點、終點:中間用空格隔開n); for(int k=0;kadjve* =end-1; p-w =duttem; Graphe

8、nd-1.id +; p-ne*tedge =Graphbegin-1.firstedge ; Graphbegin-1.firstedge =p; 顯示有向圖函數：void Display(ve*node* Graph,int ve*number,int arumber)int i;int arw6;edgenode *p;initgraph(400, 600);for(i=0;ive*number;i+)if(i%3=0|i=0) outte*t*y(100,50*(i+1), Graphi.data);Graphi.*=100;Graphi.y=50*(i+1);if(i%3=1|i=1

9、) outte*t*y(10,50*(i+1), Graphi.data);Graphi.*=10;Graphi.y=50*(i+1);if(i%3=2|i=2)outte*t*y(200,50*i, Graphi.data);Graphi.*=200;Graphi.y=50*i;for(i=0;iadjve*.*,Graphp-adjve*.y);outte*t*y(Graphi.*+Graphp-adjve*.*)/2,(Graphi.y+Graphp-adjve*.y)/2,p-w+48);arw0=Graphp-adjve*.*+5;arw1=Graphp-adjve*.y-10;ar

10、w2=Graphp-adjve*.*;arw3=Graphp-adjve*.y;arw4=Graphp-adjve*.*+5;arw5=Graphp-adjve*.y+10;drawpoly(3,arw);p=p-ne*tedge;getch();closegraph(); 求解關鍵路徑函數：int SearchMapPath(ve*node* Graph,int ve*number,int arumber) int totaltime=0;int m=0; int i,j,k,t; char sv100; int front,rear; int *topology_queue,*vl,*ve

11、,*el,*ee; front=rear=-1; t=0; topology_queue=(int*)malloc(ve*number*sizeof(int); vl=(int*)malloc(ve*number*sizeof(int); ve=(int*)malloc(ve*number*sizeof(int); el=(int*)malloc(arumber*sizeof(int); ee=(int*)malloc(arumber*sizeof(int); edgenode *p; for(i=0;ive*number;i+) vei=0; for(i=0;iadjve*; Graphk.

12、id -; if(vej+p-w vek) vek=vej+p-w ; if(Graphk.id =0) topology_queue+rear=k; p=p-ne*tedge ; if(mve*number) printf(n該圖中存在回路，不可計算出關鍵路徑！n); return 0; totaltime=veve*number-1; for(i=0;i=0;i-) j=topology_queuei; p=Graphj.firstedge; while(p) k=p-adjve* ; if(vlk-p-w )w; p=p-ne*tedge; printf(| 起點 | 終點 | 最早開場

13、時間 | 最遲開場時間 | 差值 | n); i=0; for(j=0;jadjve* ; ee+i=vej; eli=vlk-p-w; printf(| %4c | %4c | %12d | %12d | %4d |,Graphj.data ,Graphk.data ,eei,eli,eli-eei); if(eli=eei) printf( 是關鍵活動 ); svt=Graphj.data;t+; printf(n); p=p-ne*tedge; printf(關鍵路徑為：); svt=Graphve*number-1.data; for(i=0;i=t;i+) printf(%c,svi

14、);if(svi!=Graphve*number-1.data)printf(); printf(n); return 1; 主要函數的程序流程圖： 4. 畫出函數之間的調用關系圖:調試分析1.實際完成的情況說明: 本程序完成的功能是：顯示用戶從鍵盤輸入的有向圖，并計算出其關鍵路徑。支持用戶輸入char型的頂點值，int型的弧數和頂點數，int型的權值；2.程序的性能分析：本程序的時間復雜度為O(n),空間復雜度為O1。3.上機過程中出現的問題及其解決方案：1有向圖的存儲。存儲時，由于對鄰接表的具體代碼實現不了解，導致在寫這局部程序的過程中遇到不少麻煩，比方如何在結點里添加指向下一鄰接結點的指

15、針等，后來查閱了教材，解決了這一局部的問題。2有向圖的顯示。如何在屏幕上以圖形的形式輸出圖，困惑了我好久。通過在網上查找資料及尋找幫助，明白了需在頭文件里添加graphics.h文件，并使用該庫里的line()函數和outte*t*y()函數。接著是如何顯示帶箭頭的直線，由于graphics.h庫里不含有畫帶箭頭的直線的函數，于是，我使用了畫多邊形的函數drawpoly()來實現箭頭，但是這個函數的第二個形參類型是數組型的，需用數組來存儲三個點的坐標信息。3關鍵路徑的求解。由于對關鍵路徑的根本算法不了解，所以特地查閱了這一方面的書籍，了解了關鍵路徑的根本算法。4.程序中可以改良的地方說明：有向

16、圖的顯示里，箭頭無法隨直線的斜率的變化而變化，頂點值與箭頭重合，看不清箭頭的方向。5.程序中可以擴大的功能及設計實現假想：應能顯示多個有向圖，能求解多個有向圖的關鍵路徑，關鍵活動。界面可以做成可視化，人性化的界面。測試結果1輸入一組可以構成AOE網的頂點與弧的數據輸入一組不可構成AOE網的頂點與弧的數據即存在回路用戶手冊輸入圖中的節點數與弧數 2輸入圖中各個頂點的值3輸入圖中弧的權值、起點、終點4按回車鍵按回車鍵6按任意鍵七、體會與自我評價通過本次課程設，掌握了鄰接表的存儲構造，圖形顯示的一些函數的使用以及關鍵路徑的求法。在實驗過程中出現了不少的問題，通過查閱資料，向教師、同學尋求幫助，解決了

17、出現的問題。從這次的課程設計任務中我深刻地體會到：任何事情并不像我們想的那樣困難。剛開場拿到這個課設任務時，對于關鍵路徑很是發怵，因為之前對這一局部的知識運用的少，再加上任務書上還要求以圖形的形式顯示有向圖，在這次課設之前，我從來沒有接觸過圖形處理的函數。然而，俗話說世上無難事，只怕有心人，通過積極地查閱書籍，上網查找資料，這些困難都一個個的迎刃而解。并且在解決這些困難的同時，自己也復習并掌握了這些知識。本次課設遇到了很多理論課上所沒有遇到過的問題，也讓理論課上所學的理論得到驗證和使用，通過實際操作，扎實了理論知識，開拓了自己的算法思想。通過本次課設，更讓我意識到團隊合作的力量，通過小組成員的討論和互相解惑，學到很多自己沒有遇到過的問題的解決方法，學會了如何在團隊合作中互