數(shù)據(jù)結(jié)構(gòu)課程設(shè)計(jì)-關(guān)鍵路徑Word版

整理為word格式整理為word格式整理為word格式《數(shù)據(jù)結(jié)構(gòu)》課程設(shè)計(jì)報(bào)告課程題目：關(guān)鍵路徑學(xué)院：班級(jí)：學(xué)號(hào)：姓名：指導(dǎo)教師：完成日期：目錄TOC\o"1-1"\h\z\u一、需求分析 3整理為word格式整理為word格式整理為word格式二、概要設(shè)計(jì) 4三、詳細(xì)設(shè)計(jì) 5四、 調(diào)試分析 11五、 用戶使用說明 12六、 測試結(jié)果 12七、 附錄 13一、需求分析1、問題描述整理為word格式整理為word格式整理為word格式AOE網(wǎng)(即邊表示活動(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í)間之和，這條路徑就叫做關(guān)鍵路徑（criticalpath）。2、設(shè)計(jì)步驟（1）、以某一工程為藍(lán)本，采用圖的結(jié)構(gòu)表示實(shí)際的工程計(jì)劃時(shí)間。（2）、調(diào)查并分析和預(yù)測這個(gè)工程計(jì)劃每個(gè)階段的時(shí)間。（3）、用調(diào)查的結(jié)果建立AOE網(wǎng)，并用圖的形式表示。（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ù)eq\o\ac(○,v2)eq\o\ac(○,v5)eq\o\ac(○,v1)eq\o\ac(○,v4)eq\o\ac(○,v6)eq\o\ac(○,v3)6v1v2v3v4v5v68v1v2a13v1v3a22v2v4a32v2v5a43v3v4a54v3v6a63v4v6a72v5v6a81整理為word格式整理為word格式整理為word格式二、 概要設(shè)計(jì)為了實(shí)現(xiàn)上述函數(shù)功能： 1、抽象數(shù)據(jù)類型圖的定義如下：ADTGraph{數(shù)據(jù)對(duì)象V：V是具有相同特性的數(shù)據(jù)元素的集合，稱為頂點(diǎn)集。數(shù)據(jù)關(guān)系R：R={VR}；VR={＜v，w＞|v，w∈V，且P(v，w)，＜v，w＞表示從v到w的弧，謂詞P(v，w)定義了?。紇，w＞的意義和信息}基本操作：InitGraph(G);初始條件：圖G存在。操作結(jié)果：構(gòu)造一個(gè)圖的頂點(diǎn)數(shù)為MAX，弧的個(gè)數(shù)也為MAX，其他信息都相應(yīng)初始化了的圖。CreatGraph(&G);初始條件：已經(jīng)初始化了的圖G。操作結(jié)果：通過輸入函數(shù)輸入圖的頂點(diǎn)個(gè)數(shù)，各頂點(diǎn)信息，弧的條數(shù)，以及弧的其他信息，構(gòu)造圖G。}2、抽象數(shù)據(jù)類型棧的定義如下：ADTStack{數(shù)據(jù)對(duì)象：D={ai|ai∈ElemSet，i=1,2,…，n，n≥0}數(shù)據(jù)關(guān)系：Rl={＜ai-1，ai＞|ai-1，ai∈D，i=2，…，n}約定an端為棧頂，ai端為棧底?；静僮鳎篒nitStack(&S)操作結(jié)果：構(gòu)造一個(gè)空棧S。StackEmpty（S）初始條件：棧S已經(jīng)存在。操作結(jié)果：若棧S為空棧，則返回TRUE，否則FALSE。整理為word格式整理為word格式整理為word格式Push（&S，e）初始條件：棧S已經(jīng)存在。操作結(jié)果：插入元素e為新的棧頂元素。Pop（&S，&e）初始條件：棧S已存在且不為空。操作結(jié)果：刪除S的棧頂元素，并用e返回其值。}三、詳細(xì)設(shè)計(jì)1、圖的鄰接表存儲(chǔ)結(jié)構(gòu)如下：#defineMAX20typedefstructArcNode//表節(jié)點(diǎn){ intadjvex;//該弧所指向的頂點(diǎn)的位置 structArcNode*next;//指向下一條弧的指針 char*info1;//表示活動(dòng)，如a1、a2、a3等等 intinfo2;//表示權(quán)值}ArcNode;typedefstructVNode//頭結(jié)點(diǎn){ Vertextypedata[3];//頂點(diǎn)信息，如v1、v2、v3等等。 ArcNode*first;//指向第一條依附該頂點(diǎn)的弧的指針。}VNode,AdjList[MAX];typedefstruct{ AdjListvertices; intvexnum;//圖的頂點(diǎn)數(shù) intarcnum;//圖的弧數(shù)}ALGraph;整理為word格式整理為word格式整理為word格式2、棧的順序存儲(chǔ)結(jié)構(gòu)如下：#defineSIZEMAX20#defineADD10typedefintElemtype;typedefstruct{ Elemtype*base; Elemtype*top; intmaxsize;}Stack;3、圖的構(gòu)建函數(shù)設(shè)計(jì)如下：intID[MAX]={0};//存放每個(gè)頂點(diǎn)的入度的數(shù)組IDintve[MAX]={0};//用來存放每個(gè)頂點(diǎn)的最早發(fā)生時(shí)間的數(shù)組vecharstr3[MAX][10];//存放活動(dòng)的字符串?dāng)?shù)組voidInitGraph(ALGraph&G)//初始化圖時(shí)將圖的頂點(diǎn)數(shù)、弧數(shù)都賦為MAX{ G.vexnum=MAX; G.arcnum=MAX; for(inti=0;i<G.vexnum;i++)//每一個(gè)頭結(jié)點(diǎn)的first指針都指向空 G.vertices[i].first=NULL;}voidCreateGraphic(ALGraph&G){ inti,j,s,n;ArcNode*p,*pp;//定義兩個(gè)指向ArcNode表結(jié)點(diǎn)的指針p,pp charstr1[10],str2[10];//定義兩個(gè)字符串str1,str2,最大長度為10 scanf("%d\n",&G.vexnum);//輸入圖的頂點(diǎn)數(shù)vexnum for(i=0;i<G.vexnum;i++) { scanf("%s",G.vertices[i].data);//輸入各頂點(diǎn)的信息,頂點(diǎn)名稱整理為word格式整理為word格式整理為word格式 G.vertices[i].first=NULL;//第i個(gè)頭結(jié)點(diǎn)的first域指向空 } scanf("%d\n",&G.arcnum);//輸入圖的弧數(shù)arcnumfor(i=0;i<G.arcnum;i++) { scanf("%s%s%s%d",str1,str2,str3[i],&n);//輸入每條弧的其它相關(guān)信息,str1是弧的弧尾，str2是弧的弧頭，str3指的是活動(dòng)，n指的是權(quán)值 for(j=0;j<G.vexnum;j++)//根據(jù)str1，找對(duì)應(yīng)的弧尾，若找到， if(strcmp(str1,G.vertices[j].data)==0)則停止查找，并保存弧尾 break;所示的頂點(diǎn)在頭結(jié)點(diǎn)中的序號(hào)j for(s=0;s<G.arcnum;s++)//根據(jù)str1，找對(duì)應(yīng)的弧頭，若找到 if(strcmp(str2,G.vertices[s].data)==0)則停止查找，并保存弧頭 break;所示的頂點(diǎn)在頭結(jié)點(diǎn)中的序號(hào)s pp=(ArcNode*)malloc(sizeof(ArcNode));//給pp申請一個(gè)內(nèi)存空間 pp->adjvex=s;//將弧頭所指向的頂點(diǎn)的位置下標(biāo)存放在pp的adjvex域中 pp->info1=str3[i];//將該弧的活動(dòng)信息存放在pp的info1域中 pp->info2=n;//將該弧的權(quán)值大小存放在pp的info2域中 pp->next=NULL;//pp的next指向空 ID[s]++;//s的入度加1 if(G.vertices[j].first!=NULL)//如果序號(hào)為j的頭結(jié)點(diǎn)的first所指向的不為 {空，則表示該頂點(diǎn)已經(jīng)連好了一條弧，需要找下一個(gè)可存放的位置整理為word格式整理為word格式整理為word格式 p=G.vertices[j].first;//用一個(gè)臨時(shí)指針保存該頭結(jié)點(diǎn)的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;//直到p的next指向?yàn)榭眨侔裵的next指向pp } elseG.vertices[j].first=pp;//如果序號(hào)為j的頭結(jié)點(diǎn)的first所指向的為空，直接把它的first指向pp }}4、堆棧的功能函數(shù)設(shè)計(jì)如下：StatusInitStack(Stack&S)//棧的初始化操作{ S.base=(Elemtype*)malloc(SIZEMAX*sizeof(Elemtype));//給棧分配內(nèi)存空間 if(!S.base)exit(OVERFLOW);//若分配不成功，則返回OVERFLOW； S.top=S.base;//讓棧的棧頂指針和棧底指針相等 S.maxsize=SIZEMAX;//棧的當(dāng)前容量為SIZEMAX returnOK;}StatusPop(Stack&S,int&e){整理為word格式整理為word格式整理為word格式 if(S.top==S.base)//如果棧的棧頂指針等于棧底指針，則表示當(dāng)前棧為空 returnERROR;//棧頂元素不存在，所以返回ERROR e=*(--S.top);//如果棧不為空，就取出S的棧頂指針?biāo)赶虻臄?shù)據(jù)， returnOK;//并把top指針往下移一個(gè)位置}StatusPush(Stack&S,inte){ if(S.top-S.base>=S.maxsize)//如果當(dāng)前棧內(nèi)存的元素超過了它的最大存放量 {//則必須追加空間 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;//top指針往上移一位后，讓top指針指向元素e returnOK;}StatusEmpty(StackS){ if(S.top==S.base)returnOK; //如果棧的棧頂指針等于棧底指針，則表示當(dāng)前棧為空,返回OKelsereturnERROR;//否則返回ERROR}5、求關(guān)鍵路徑的函數(shù)設(shè)計(jì)如下：StatusTopo(ALGraphG,Stack&T)//拓?fù)渑判蚝瘮?shù){inti,j,k; ArcNode*p;//定義一個(gè)指向ArcNode表結(jié)點(diǎn)的指針p整理為word格式整理為word格式整理為word格式 StackS;//定義一個(gè)存放入度為0的頂點(diǎn)所在的下標(biāo)值的棧InitStack(S);//初始化棧S for(j=0;j<G.vexnum;j++)//查看各個(gè)頂點(diǎn)的入度是否為0， if(ID[j]==0)//若為0，就讓該頂點(diǎn)所在位置的下標(biāo)值入棧 Push(S,j); intcount=0;//記錄進(jìn)入拓?fù)渑判驐的元素個(gè)數(shù) while(!Empty(S)) { Pop(S,j);//從零入度頂點(diǎn)棧S中取出棧頂元素，存放在j中 Push(T,j);//元素j入棧T，表示序號(hào)為j的頂點(diǎn)入棧 count++; for(p=G.vertices[j].first;p;p=p->next) {//找以第j個(gè)頂點(diǎn)為弧尾的弧的弧頭 k=p->adjvex;//保存弧頭所示的頂點(diǎn)的位置下標(biāo) ID[k]--;//刪除該弧后，弧頭所示的頂點(diǎn)入度減1 if(ID[k]==0)Push(S,k);//如果該頂點(diǎn)入度為0，就入棧S if((ve[j]+(p->info2))>ve[k])ve[k]=ve[j]+(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.vexnum)returnERROR;//如果拓?fù)湫蛄袟Ｖ械捻旤c(diǎn)數(shù)小于圖的頂點(diǎn)數(shù)，則表示圖中有環(huán)，沒有關(guān)鍵路徑 elsereturnOK;}StatusCritial(ALGraphG)//求關(guān)鍵路徑函數(shù){ inti,j,k,ee,el; intvl[MAX];//存放各頂點(diǎn)最遲發(fā)生時(shí)間的數(shù)組vlStackT;//定義一個(gè)存放拓?fù)湫蛄性氐臈整理為word格式整理為word格式整理為word格式InitStack(T);//初始化該棧ArcNode*p; if(!Topo(G,T))returnERROR;//如果拓?fù)渑判虿怀晒?，也無法找到關(guān)鍵路徑，就返回ERROR for(i=0;i<G.vexnum;i++)//頂點(diǎn)最遲發(fā)時(shí)間始化，都等于最后一個(gè)頂點(diǎn)的ve vl[i]=ve[G.vexnum-1]; while(!Empty(T))//在入度頂點(diǎn)棧不為空的條件下循環(huán) { for(Pop(T,j),p=G.vertices[j].first;p;p=p->next) {//取出棧頂元素，并查找以j號(hào)頂點(diǎn)為弧尾的弧的弧頭 k=p->adjvex;//把弧頭所示的頂點(diǎn)位置下標(biāo)值存放在k中 if(vl[k]-(p->info2)<vl[j])vl[j]=vl[k]-(p->info2);//如果k號(hào)頂點(diǎn)的最遲發(fā)生時(shí)間與該弧的權(quán)值之差小于j號(hào)定點(diǎn)的最遲發(fā)生時(shí)間，就改變vl[j] } } printf("關(guān)鍵頂點(diǎn)為a："); for(j=0;j<G.vexnum;j++) {if(ve[j]==vl[j])//如果定點(diǎn)的最早發(fā)生時(shí)間與最遲發(fā)生時(shí)間相等，則表示該 printf("%s",G.vertices[j].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.vertices[j].first;p;p=p->next)整理為word格式整理為word格式整理為word格式 {k=p->adjvex; ee=ve[j]; el=vl[k]-(p->info2); if(el==ee)printf("%s",p->info1); } } printf("\n"); returnOK;}四、 調(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()時(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)。整理為word格式整理為word格式整理為word格式五、 用戶使用說明第一行輸入頂點(diǎn)個(gè)數(shù)vexnum。第二行輸入各個(gè)頂點(diǎn)的名稱。第三行輸入弧的邊數(shù)arcnum。接下來的arcnum行輸入每一條弧的弧尾頂點(diǎn)、弧頭頂點(diǎn)、活動(dòng)以及權(quán)值大小。六、 測試結(jié)果

七、 附錄

以下是該程序設(shè)計(jì)的完整代碼：#include<stdio.h>#include<string.h>#include<stdlib.h>#defineTRUE1#defineFALSE0整理為word格式整理為word格式整理為word格式#defineOK1#defineERROR0#defineOVERFLOW-2#defineMAX20#defineSIZEMAX20#defineADD10typedefintStatus;typedefintInfotype;typedefcharVertextype;typedefintElemtype;intID[MAX]={0};intve[MAX]={0};charstr3[MAX][10];typedefstructArcNode{ intadjvex; structArcNode*next; char*info1; intinfo2;}ArcNode;typedefstructVNode{ Vertextypedata[3];ArcNode*first;}VNode,AdjList[MAX];typedefstruct{ AdjListvertices; intvexnum; intarcnum;}ALGraph;typedefstruct{ Elemtype*base; Elemtype*top; intmaxsize;}Stack;voidInit(ALGraph&G){ G.vexnum=MAX;G.arcnum=MAX; for(inti=0;i<G.vexnum;i++) G.vertices[i].first=NULL;}整理為word格式整理為word格式整理為word格式voidCreateGraphic(ALGraph&G){ inti,j,s,n;ArcNode*p,*pp; charstr1[10],str2[10]; scanf("%d\n",&G.vexnum); for(i=0;i<G.vexnum;i++) { scanf("%s",G.vertices[i].data); G.vertices[i].first=NULL; } scanf("%d\n",&G.arcnum); for(i=0;i<G.arcnum;i++) { scanf("%s%s%s%d",str1,str2,str3[i],&n); for(j=0;j<G.vexnum;j++) if(strcmp(str1,G.vertices[j].data)==0) break; for(s=0;s<G.arcnum;s++) if(strcmp(str2,G.vertices[s].data)==0) break; pp=(ArcNode*)malloc(sizeof(ArcNode)); pp->adjvex=s; pp->info1=str3[i]; pp->info2=n; pp->next=NULL; ID[s]++; if(G.vertices[j].first!=NULL) { p=G.vertices[j].first; if(p->next!=NULL) { while(p->next->next!=NULL) { p=p->next; } p=p->next; } p->next=pp; } else G.vertices[j].first=pp; }}整理為word格式整理為word格式整理為word格式StatusInitStack(Stack&S){ S.base=(Elemtype*)malloc(SIZEMAX*sizeof(Elemtype)); if(!S.base)exit(OVERFLOW); S.top=S.base; S.maxsize=SIZEMAX; returnOK;}StatusPop(Stack&S,int&e){ if(S.top==S.base)returnERROR; e=*(--S.top); returnOK;}StatusPush(Stack&S,inte){ 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++; returnOK;}StatusEmpty(StackS){ if(S.top==S.base)returnOK; elsereturnERROR;}StatusTopo(ALGraphG,Stack&T){inti,j,k; ArcNode*p; StackS;InitStack(S); for(j=0;j<G.vexnum;j++) if(ID[j]==0) Push(S,j); intcount=0; while(!Empty(S))整理為word