數(shù)據(jù)結(jié)構(gòu)課程設(shè)計(jì)報(bào)告——關(guān)鍵路徑

1、數(shù)據(jù)結(jié)構(gòu)課程設(shè)計(jì)報(bào)告課程題目：關(guān)鍵路徑學(xué) 院：班 級(jí)：學(xué) 號(hào)：姓 名：指導(dǎo)教師：完成日期：目錄工需求分析二、概要設(shè)計(jì) 4三、詳細(xì)設(shè)計(jì) 5四、調(diào)試分析 12五、用戶使用說明 12六、測試結(jié)果 13七、附錄 13一、需求分析1、問題描述AOER(即邊表示活動(dòng)的網(wǎng)絡(luò))，在某些工程估算方面非常有用。它可以使人們了解：(1)研究某個(gè)工程至少需要多少時(shí)間？ ( 2)哪些活動(dòng)是影響工程進(jìn)度 的關(guān)鍵？在AOE網(wǎng)絡(luò)中，從源點(diǎn)到匯點(diǎn)的有向路徑可能不止一條，但只有各條路徑上所有活動(dòng)都完成了，這個(gè)工程才算完成。因此，完成整個(gè)工程所需的時(shí)間取 決于從源點(diǎn)到匯點(diǎn)的最長路徑長度，即在這條路徑上所有活動(dòng)的持續(xù)時(shí)間之和， 這條

2、路徑就叫做關(guān)鍵路徑(critical path )。2、設(shè)計(jì)步驟(1)、以某一工程為藍(lán)本，采用圖的結(jié)構(gòu)表示實(shí)際的工程計(jì)劃時(shí)間。(2)、調(diào)查并分析和預(yù)測這個(gè)工程計(jì)劃每個(gè)階段的時(shí)間。(3)、用調(diào)查的結(jié)果建立AOER,并用圖的形式表示。(4 )、用CreateGraphic ()函數(shù)建立圖的鄰接表存儲(chǔ)結(jié)構(gòu)，能夠輸入圖的 頂點(diǎn)和邊的信息，并存儲(chǔ)到相應(yīng)存儲(chǔ)結(jié)構(gòu)中。(5)、用SearchMaxPath()函數(shù)求出最大路徑，并打印出關(guān)鍵路徑。(6)、編寫代碼并調(diào)試、測試通過。3、測試數(shù)據(jù)、V46)6v1 v2 v3 v4 v5 v68v1 v2 a1 3v1 v3 a2 2v2 v4 a3 2v2 v5 a

3、4 3v3 v4 a5 4v3 v6 a6 3v4 v6 a7 2v5 v6 a8 1二、概要設(shè)計(jì)為了實(shí)現(xiàn)上述函數(shù)功能：1、抽象數(shù)據(jù)類型圖的定義如下：ADT Graph 數(shù)據(jù)對(duì)象V： V是具有相同特性的數(shù)據(jù)元素的集合，稱為頂點(diǎn)集。數(shù)據(jù)關(guān)系RR= VR ;VR= <v, w>|v , wC V,且P(v , w), < v, w>表示從 v至UW勺弧，謂詞 P(v , w)定義了弧< v, w>的意義和信息 基本操作：InitGraph(G);初始條件：圖G#在。操作結(jié)果：構(gòu)造一個(gè)圖的頂點(diǎn)數(shù)為MAX弧的個(gè)數(shù)也為MAX其他信息都相應(yīng)初始 化了的圖。CreatGr

4、aph(& G);初始條件：已經(jīng)初始化了的圖 G操作結(jié)果：通過輸入函數(shù)輸入圖的頂點(diǎn)個(gè)數(shù)，各頂點(diǎn)信息，弧的條數(shù)，以及弧的 其他信息，構(gòu)造圖G2、抽象數(shù)據(jù)類型棧的定義如下：ADT Stack 數(shù)據(jù)對(duì)象：D=ai | ai C ElemSet, i=1,2,，n, n>0數(shù)據(jù)關(guān)系：Rl= <ai-1 , ai > | ai-1 , ai D, i=2,，n 約定an端為棧頂，ai端為棧底。基本操作：InitStack(&S)操作結(jié)果：構(gòu)造一個(gè)空棧SoStackEmpty (S)初始條件：棧S已經(jīng)存在。操作結(jié)果：若棧 她空棧，則返回TRUE否則FALSEPush (&

5、amp;S, e)初始條件：棧S已經(jīng)存在。操作結(jié)果：插入元素e為新的棧頂元素。Pop (&S, &e)初始條件：棧S已存在且不為空。操作結(jié)果：刪除S的棧頂元素，并用e返回其值。三、詳細(xì)設(shè)計(jì)1、圖的鄰接表存儲(chǔ)結(jié)構(gòu)如下：#define MAX 20typedef struct ArcNode/表節(jié)點(diǎn)int adjvex;/該弧所指向的頂點(diǎn)的位置struct ArcNode * next;指向下一條弧的指針char * infol;/ 表示活動(dòng)，如 al、a2、a3等等int info2;/表示權(quán)值A(chǔ)rcNode;typedef struct VNode / 頭結(jié)點(diǎn) Vertexty

6、pe data3; / 頂點(diǎn)信息，如 v1、v2、v3等等。ArcNode * first;/指向第一條依附該頂點(diǎn)的弧的指針VNode,AdjListMAX;typedef structAdjList vertices;int vexnum;/圖的頂點(diǎn)數(shù)int arcnum;/圖的弧數(shù)ALGraph;教育資料2、棧的順序存儲(chǔ)結(jié)構(gòu)如下:#defineSIZEMAX 20#defineADD 10typedefint Elemtype;typedefstructElemtype * base;Elemtype * top;int maxsize;3、Stack;圖的構(gòu)建函數(shù)設(shè)計(jì)如下:int IDM

7、AX=0;/存放每個(gè)頂點(diǎn)的入度的數(shù)組IDint veMAX=0;/用來存放每個(gè)頂點(diǎn)的最早發(fā)生時(shí)間的數(shù)組 vechar str3MAX10;/存放活動(dòng)的字符串?dāng)?shù)組10void InitGraph(ALGraph &G)G.vexnum=MAX;G.arcnum=MAX;/初始化圖時(shí)將圖的頂點(diǎn)數(shù)、弧數(shù)都賦為 MAXfor (int i=0;i<G.vexnum;i+) /每一個(gè)頭結(jié)點(diǎn)的first 指針都指向空G.verticesi.first=NULL;void CreateGraphic(ALGraph &G)int i,j,s,n;ArcNode *p,*pp;/char

8、 str110,str210; /定義兩個(gè)指向ArcNodeS結(jié)點(diǎn)的指針p,pp定義兩個(gè)字符串str1,str2,最大長度為scanf( "%dn" ,&G.vexnum);/ 輸入圖的頂點(diǎn)數(shù)vexnumfor (i=0;i<G.vexnum;i+)輸入各頂點(diǎn)的信息，頂點(diǎn)名scanf( "%s",G.verticesi.data); /G.verticesi.first=NULL; /第i個(gè)頭結(jié)點(diǎn)的first域指向空scanf( "%dn" ,&G.arcnum); 輸入圖的弧數(shù) arcnum for (i=0;

9、i<G.arcnum;i+)scanf( "%s%s%s%停tr1,str2,str3i,&n); 輸入每條弧的其它相關(guān)信息,strl是弧的弧尾，str2是弧的弧頭，str3指的是活動(dòng)，n指的是 權(quán)值for (j=0;j<G.vexnum;j+) /根據(jù)str1，找對(duì)應(yīng)的弧尾，若找到，if (strcmp(str1,G.verticesj.data)=0)則停止查找，并保存弧尾 break;所示的頂點(diǎn)在頭結(jié)點(diǎn)中的序號(hào)jfor (s=0;s<G.arcnum;s+) /根據(jù)str1 ,找對(duì)應(yīng)的弧頭，若找到if (strcmp(str2,G.verticess.

10、data)=0)則停止查找，并保存弧頭break;所示的頂點(diǎn)在頭結(jié)點(diǎn)中的序號(hào)spp=(ArcNode *)malloc( sizeof (ArcNode); /給pp中請(qǐng)一個(gè)內(nèi)存空pp->adjvex=s; /域中pp->info1=str3i; /中pp->info2=n; /pp->next=NULL; /ppID回+;/sif (G.verticesj.first!=NULL) /向的不為pp 的 adjvex將該弧的活動(dòng)信息存放在pp的info1域?qū)⒃摶〉臋?quán)值大小存放在pp的info2域中 的next指向空的入度加1如果序號(hào)為j的頭結(jié)點(diǎn)的first所指將弧頭所指

11、向的頂點(diǎn)的位置下標(biāo)存放在用一個(gè)臨時(shí)指針保存該頭結(jié)點(diǎn)的空，則表示該頂點(diǎn)已經(jīng)連好了一條弧，需要找下一個(gè)可存放的位置p=G.verticesj.first; /first 指針if (p->next!=NULL) / 如果first 所指向的表結(jié)點(diǎn)的next指向不為空,/則需要找下一個(gè)可存放位置while (p->next->next!=NULL) /如果p所指向的表結(jié)點(diǎn)的next所指向另一表結(jié)點(diǎn)的next不為空，就把p指針往后移一位p=p->next;p=p->next;p->next=pp; /直至1J p的next指向?yàn)榭眨侔?p的next指向ppelse

12、 G.verticesj.first=pp; /如果序號(hào)為 j 的頭結(jié)點(diǎn)的first所指向的為空，直接把它的first指向pp4、堆棧的功能函數(shù)設(shè)計(jì)如下：Status InitStack(Stack &S) /棧的初始化操作S.base=(Elemtype *)malloc(SIZEMAX* sizeof (Elemtype); 給棧分配內(nèi)存空間if (!S.base) exit (OVERFLOW); /若分配不成功，則返回 OVERFLOWS.top=S.base; /讓棧的棧頂指針和棧底指針相等S.maxsize=SIZEMAX; / 棧的當(dāng)前容量為 SIZEMAX return

13、 OK;Status Pop(Stack &S, int &e)if (S.top=S.base) /如果棧的棧頂指針等于棧底指針，則表示當(dāng)前棧為空return ERROR; /棧頂元素不存在，所以返回ERRORe=*(-S.top); 如果棧不為空，就取出S的棧頂指針?biāo)赶虻臄?shù)據(jù), return OK; / 并把top指針往下移一個(gè)位置Status Push(Stack &S, int e)if (S.top-S.base>=S.maxsize) /如果當(dāng)前棧內(nèi)存的元素超過了它的最大存 放量/ 則必須追加空間S.base=(Elemtype*)realloc(S

14、.base,(S.maxsize+ADD)* sizeof (Elemtype);if (!S.base)exit (OVERFLOW);S.top=S.base+S.maxsize;S.maxsize=S.maxsize+ADD;*(S.top+尸e;/top指針往上移一位后，讓top指針指向元素ereturn OK;Status Empty(Stack S) if (S.top=S.base) return OK;/如果棧的棧頂指針等于棧底指針，則表示當(dāng)前棧為空，返回OKelse return ERROR; / 否則返回 ERROR5、求關(guān)鍵路徑的函數(shù)設(shè)計(jì)如下：Status Topo(AL

15、Graph G,Stack &T) / 拓?fù)渑判蚝瘮?shù)int i,j,k;ArcNode *p; /定義一個(gè)指向ArcNodeS結(jié)點(diǎn)的指針pStack S;/定義一個(gè)存放入度為0的頂點(diǎn)所在的下標(biāo)值的棧InitStack(S); / 初始化棧 Sfor (j=0;j<G.vexnum;j+) /查看各個(gè)頂點(diǎn)的入度是否為0,if (IDj=0)/ 若為0,就讓該頂點(diǎn)所在位置的下標(biāo)值入棧Push(S,j)；int count=0; /記錄進(jìn)入拓?fù)渑判驐的元素個(gè)數(shù)while (!Empty(S)Pop(S,j); /從零入度頂點(diǎn)棧S中取出棧頂元素，存放在j中Push(T,j); /元素j

16、入棧T,表示序號(hào)為j的頂點(diǎn)入棧 count+;for (p=G.verticesj.first;p;p=p->next)/ 找以第j個(gè)頂點(diǎn)為弧尾的弧的弧頭k=p->adjvex; /保存弧頭所示的頂點(diǎn)的位置下標(biāo)IDk-;/刪除該弧后，弧頭所示的頂點(diǎn)入度減1if (IDk=0) Push(S,k); /如果該頂點(diǎn)入度為0,就入棧Sif ( ( vej + (p->info2) ) > vek) vek=vej+(p->info2);/如果j號(hào)頂點(diǎn)的最早發(fā)生時(shí)間與該弧的權(quán)值之和大于k號(hào)定點(diǎn)的/最早發(fā)生時(shí)間，就改變k號(hào)頂點(diǎn)的最早發(fā)生時(shí)間if (count<G.ve

17、xnum) return ERROR; /如果拓?fù)湫蛄袟Ｖ械捻旤c(diǎn)數(shù)小于圖的頂點(diǎn)數(shù)，則表示圖中有環(huán)，沒有關(guān)鍵路徑else return OK;Status Critial(ALGraph G) /求關(guān)鍵路徑函數(shù)int i,j,k,ee,el;int vlMAX; /存放各頂點(diǎn)最遲發(fā)生時(shí)間的數(shù)組vlStack T;/定義一個(gè)存放拓?fù)湫蛄性氐臈InitStack(T); / 初始化該棧ArcNode * p;if (!Topo(G,T) return ERROR;/如果拓?fù)渑判虿怀晒?，也無法找到關(guān)鍵路徑，就返回 ERRORfor (i=0;i<G.vexnum;i+) /頂點(diǎn)最遲發(fā)時(shí)間始化

18、，都等于最后一個(gè)頂點(diǎn) 的vevli=veG.vexnum-1;while (丘mpty(T) /在入度頂點(diǎn)棧不為空的條件下循環(huán)for (Pop(T,j),p=G.verticesj.first;p;p=p->next) /取出棧頂元素，并查找以j號(hào)頂點(diǎn)為弧尾的弧的弧頭k=p->adjvex; /把弧頭所示的頂點(diǎn)位置下標(biāo)值存放在k中if (vlk-(p->info2)<vlj) vlj=vlk-(p->info2); /如果k號(hào)頂點(diǎn)的最遲發(fā)生時(shí)間與該弧的權(quán)值之差小于j號(hào)定點(diǎn)的最遲發(fā)生時(shí)間，就改變 vljprintf("關(guān)鍵頂點(diǎn)為a：");for

19、(j=0;j<G.vexnum;j+)if (vej=vlj) /如果定點(diǎn)的最早發(fā)生時(shí)間與最遲發(fā)生時(shí)間相等，則表示該printf( "%s " ,G.verticesj.data);/ 頂點(diǎn)是關(guān)鍵頂點(diǎn)，就輸出該關(guān)鍵 頂點(diǎn)的名稱printf( "n");printf("關(guān)鍵路徑為：");for (j=0;j<G.vexnum;j+)for (p=G.verticesj.first;p;p=p->next) k=p->adjvex;ee=vej;el=vlk-(p->info2);if (el=ee) pri

20、ntf( "%s ” ,p->info1);printf( "n");return OK;四、調(diào)試分析1、本次課程設(shè)計(jì)題目思路特別清晰，算法特別簡單，但是在編程過程中遇到了 一系列的問題都值得思考與分析。2、首先是在圖的創(chuàng)建過程中，用鄰接表創(chuàng)建圖的時(shí)候，指針使用沒有正確到 位而引發(fā)了一系列問題，后來通過與老師同學(xué)一起分析才找到了問題的癥結(jié)所 在。之前用臨時(shí)指針p保存頭結(jié)點(diǎn)的first指針，然后讓p指向已經(jīng)存好信息的 表結(jié)點(diǎn)pp,這樣操作并沒有真正把它連起來，下次循環(huán)時(shí)，又覆蓋了原來的信 息。3、在成功創(chuàng)建了圖后，把主函數(shù)中生成的圖作為參數(shù)傳給 Critial

21、() 時(shí)，又 發(fā)現(xiàn)原來圖中的活動(dòng)這一信息又改變了，全變成亂碼了，原來是由于存放活動(dòng)的字符串str3 ,由于不斷的輸入，導(dǎo)致最后字符串什么也沒有了，而圖中每個(gè)弧的活動(dòng)指針都指向它，所以就全亂了，后來就把它改為字符串?dāng)?shù)組，并且把它設(shè)為 全局變量。4、在調(diào)試Critial()這一函數(shù)中，也遇到了一些問題，在觀察零入度棧 S的棧頂元素和拓?fù)湫蛄袟的時(shí)候，在watch窗口中輸入*(S.top-)，發(fā)現(xiàn)一直亂變， 根本不知道它的棧內(nèi)元素，甚至懷疑棧的初始化函數(shù)有沒有寫對(duì)，后來通過查找以前堆棧類型問題以及與同學(xué)題目作對(duì)比才發(fā)現(xiàn)就是由于窗口輸入內(nèi)容寫錯(cuò)了， 應(yīng)該改為*(S.top-1)。五、用戶使用說明第一

22、行輸入頂點(diǎn)個(gè)數(shù)vexnumi第二行輸入各個(gè)頂點(diǎn)的名稱。第三行輸入弧的邊數(shù)arcnum。接下來的arcnum行輸入每一條弧的弧尾頂點(diǎn)、弧頭頂點(diǎn)、活動(dòng)以及權(quán)值大小。六、測試結(jié)果Evl v3 v4 u5 B ul v2 al 3 vl v3 2 u4 a3 2 u2 v5 a4 3 。3 v4 dS 4 u3 u6 aS 3 u4 vG a7 2 05 v6 a8 1 關(guān)鍵頂點(diǎn)為:M v3 v4 v6 美耀路徑為；m2 aS a? Press any key to continue七、附錄以下是該程序設(shè)計(jì)的完整代碼:#include <stdio.h>#include <strin

23、g.h>#include <stdlib.h># define TRUE 1# define FALSE 0# define OK 1# define ERROR 0# define OVERFLOW -2# define MAX 20# define SIZEMAX 20# define ADD 10 typedef int Status;typedef int Infotype;typedef char Vertextype;typedef int Elemtype;int IDMAX=0;int veMAX=0;char str3MAX10;typedef struct

24、 ArcNodeint adjvex;struct ArcNode * next;char * infol;int info2;ArcNode;typedef struct VNodeVertextype data3;ArcNode * first;VNode,AdjListMAX;typedef structAdjList vertices;int vexnum;int arcnum;ALGraph;typedef structElemtype * base;Elemtype * top; int maxsize;Stack;void Init(ALGraph &G)G.vexnum

25、=MAX;G.arcnum=MAX;for (int i=0;i<G.vexnum;i+) G.verticesi.first=NULL;void CreateGraphic(ALGraph &G)int i,j,s,n;ArcNode *p,*pp;char str110,str210; scanf( "%dn" ,&G.vexnum);for (i=0;i<G.vexnum;i+)scanf( "%s",G.verticesi.data);G.verticesi.first=NULL;scanf( "%dn&qu

26、ot; ,&G.arcnum);for (i=0;i<G.arcnum;i+)scanf( "%s%s%s%停tr1,str2,str3i,&n);for (j=0;j<G.vexnum;j+)if (strcmp(str1,G.verticesj.data)=0) break;for (s=0;s<G.arcnum;s+)if (strcmp(str2,G.verticess.data)=0) break;pp=(ArcNode *)malloc( sizeof (ArcNode);pp->adjvex=s;pp->info1=str3

27、i;pp->info2=n;pp->next=NULL;IDs+;if (G.verticesj.first!=NULL)p=G.verticesj.first;if (p->next!=NULL)while (p->next->next!=NULL)p=p->next;p=p->next;p->next=pp;elseG.verticesj.first=pp;Status InitStack(Stack &S)S.base=(Elemtype *)malloc(SIZEMAX* sizeof (Elemtype); if (!S.bas

28、e) exit (OVERFLOW);S.top=S.base;S.maxsize=SIZEMAX;return OK;Status Pop(Stack &S, int &e)if (S.top=S.base) return ERROR;e=*(-S.top);return OK;Status Push(Stack &S, int e)if (S.top-S.base>=S.maxsize)S.base=(Elemtype*)realloc(S.base,(S.maxsize+add)* sizeof (Elemtype); if (!S.base) exit (OVERFLOW);S.top=S.base+S.maxsize;S.maxsize=S.maxsize+add;*(S.top+)=e;/*(S.top)=e,S.top+;return OK;Status Empty(Stack S)if (S.top=S.base) return OK;else return ERROR;Status Topo(ALGraph G,Stack &T)int i,j,k;ArcNode *p;Stack S;InitStack(S);for (j=0;j<G.vexnum;j+)if (IDj=0) Pus