数据结构课程设计-关键路径

《数据结构课程设计-关键路径》由会员分享，可在线阅读，更多相关《数据结构课程设计-关键路径（18页珍藏版）》请在装配图网上搜索。

1、数据结构课程设计报告课程题目：关键路径学 院：班 级：学 号：姓 名：指导教师：完成日期：目录一、需求分析3二、概要设计4三、详细设计5四、调试分析11五、用户使用说明12六、测试结果12七、附录13一、需求分析1、问题描述AOE网（即边表示活动的网络），在某些工程估算方面非常有用。它可以使人 们了解：（1）研究某个工程至少需要多少时间？ （2）哪些活动是影响工程进度 的关键？在AOE网络中，从源点到汇点的有向路径可能不止一条，但只有各条路 径上所有活动都完成了，这个工程才算完成。因此，完成整个工程所需的时间取 决于从源点到汇点的最长路径长度，即在这条路径上所有活动的持续时间之和， 这条路径就

2、叫做关键路径（critical path）。2、设计步骤（1）、以某一工程为蓝本，采用图的结构表示实际的工程计划时间。（2）、调查并分析和预测这个工程计划每个阶段的时间。（3）、用调查的结果建立AOE网，并用图的形式表示。（4）、用CreateGraphic （）函数建立图的邻接表存储结构，能够输入图的 顶点和边的信息，并存储到相应存储结构中。（5）、用SearchMaxPath（）函数求出最大路径，并打印出关键路径。（6）、编写代码并调试、测试通过。3、测试数据-QQ6v1 v2 v3 v4 v5 v68v1 v2 a1 3v1 v3 a2 2v2 v4 a3 2v2 v5 a4 3v3 v

3、4 a5 4v3 v6 a6 3v4 v6 a7 2v5 v6 a8 1二、概要设计为了实现上述函数功能：1、抽象数据类型图的定义如下：ADT Graph (数据对象V： V是具有相同特性的数据元素的集合，称为顶点集。数据关系R：R=( VR ；VR=Vv，w|v，wV，且P(v，w), Vv，w表示从v到可的孤，谓词P(v， w)定义了孤Vv，w的意义和信息 基本操作： InitGraph(G);初始条件：图G存在。操作结果：构造一个图的顶点数为MAX，孤的个数也为MAX，其他信息都相应初始 化了的图。CreatGraph(& G);初始条件：已经初始化了的图G。操作结果：通过输入函数输入图

4、的顶点个数，各顶点信息，孤的条数，以及孤的 其他信息，构造图G。2、抽象数据类型栈的定义如下：ADT Stack 数据对象：D=ai | ai EElemSet，i=1,2,，n， nN0数据关系：Rl=Vai-1，ai | ai-1，aiED， i=2，n 约定an端为栈顶，ai端为栈底。基本操作：InitStack(&S)操作结果：构造一个空栈S。StackEmpty (S)初始条件：栈S已经存在。操作结果：若栈S为空栈，则返回TRUE，否则FALSE。Push （&S， e）初始条件：栈S已经存在。操作结果：插入元素e为新的栈顶元素。Pop （&S， &e）初始条件：栈S已存在且不为空。

5、操作结果：删除S的栈顶元素，并用e返回其值。三、详细设计1、图的邻接表存储结构如下：#define MAX 20typedef struct ArcNode/表节点（int adjvex;/该孤所指向的顶点的位置struct ArcNode * next; /指向下一条孤的指针char * info1;/表示活动，如a1、a2、a3等等int info2;/表示权值ArcNode;typedef struct VNode头结点（Vertextype data3;/顶点信息，如v1、v2、v3等等。ArcNode * first;指向第一条依附该顶点的孤的指针。VNode,AdjListMAX;

6、typedef struct（AdjList vertices;int vexnum;/图的顶点数int arcnum;图的孤数ALGraph;2、栈的顺序存储结构如下：#define SIZEMAX 20#define ADD 10typedef int Elemtype;typedef struct(Elemtype * base;Elemtype * top;int maxsize;Stack;3、图的构建函数设计如下：int IDMAX = 0;存放每个顶点的入度的数组IDint veMAX = 0;/用来存放每个顶点的最早发生时间的数组vechar str3MAX10;存放活动的字符

7、串数组void InitGraph(ALGraph &G) 初始化图时将图的顶点数、弓瓜数都赋为MAX (G.vexnum=MAX;G.arcnum=MAX;for (int i=0;iG.vexnum;i+) /每一个头结点的firs t指针都指向空 G.verticesi.first二NULL;void CreateGraphic(ALGraph &G)(int i,j,s,n;ArcNode *p,*pp;/定义两个指向ArcNod e表结点的指针p,ppchar str110,str210;/定义两个字符串str1,str2,最大长度为10scanf(dn，&G.vexnum);/输入

8、图的顶点数 vexnumfor (i=0;iG.vexnum;i+)scanf(s，G.verticesi.data);/输入各顶点的信息，顶点名称G.verticesi.first二NULL;/第 i 个头结点的 firs t 域指向空scanf(dn，&G.arcnum); /输入图的孤数 arcnumfor (i=0;iG.arcnum;i+)(scanf(s%s%s%d，str1,str2,str3i,&n); /输入每条孤的其它相 关信息，str1是孤的孤尾，str2是孤的孤头，str3指的是活动，n指的是 权值for(j=0;jG.vexnum;j+)根据str1，找对应的弓瓜尾，

9、若找到，if(strcmp(str1,G.verticesj.data)=0) 则停止查找，并保存 孤尾break;所示的顶点在头结点中的序号jfor(s=0;sadjvex=s; /将弓瓜头所指向的顶点的位置下标存放在pp的adjvex 域中pp-info1=str3i;/将该弓瓜的活动信息存放在pp的info 1域中pp-info2=n;/将该弓瓜的权值大小存放在pp的info2域中pp-next=NULL;/pp 的 nex t指向空IDs+;/s的入度加1if(G.verticesj.first!=NULL) /如果序号为j的头结点的first所指 向的不为( 空，则表示该顶点已经连好

10、了一条孤，需要找下一个可存放的位置p=G.verticesj.first; /用一个临时指针保存该头结点的 first指针if (p-next!二NULL)如果first所指向的表结点的next指向不为空，(/则需要找下一个可存放位置while (p-next-next!二NULL)/如果p所指向的表结点的next( 所指向另一表结点的next不为空，就把p指针往后移一位 p=p-next;p=p-next;p-next=pp; 直到p的next指向为空，再把p的next指向ppelse G.verticesj.first=pp; /如果序号为 j 的头结点的first所指向的为空，直接把它的

11、first指向pp4、堆栈的功能函数设计如下：Status InitStack(Stack &S)栈的初始化操作(5. base=(Elemtype *)malloc(SIZEMAX*sizeof(Elemtype); 给栈分配内 存空间if(!S.base) exit (OVERFLOW); /若分配不成功，则返回 OVERFLOW；S.top=S.base;让栈的栈顶指针和栈底指针相等S.maxsize=SIZEMAX;/栈的当前容量为 SIZEMAXreturn OK; Status Pop(Stack &S, int &e)(if(S.top=S.base) 如果栈的栈顶指针等于栈底指

12、针，则表示当前栈为空return ERROR; 栈顶元素不存在，所以返回ERRORe=*(-S.top); /如果栈不为空，就取出S的栈顶指针所指向的数据，return OK;/并把top指针往下移一个位置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.max

13、size;S.maxsize二S.maxsize+ADD;*(S.top+)=e; /top指针往上移一位后，让top指针指向元素e return OK;Status Empty(Stack S)( if(S.top=S.base) return OK;如果栈的栈顶指针等于栈底指针，则表示当前栈为空，返回OKelse return ERROR;否则返回ERROR5、求关键路径的函数设计如下：Status Topo(ALGraph G,Stack &T)/拓扑排序函数(int i,j,k;ArcNode *p;/定义一个指向ArcNod e表结点的指针pStack S;定义一个存放入度为0的顶点

14、所在的下标值的栈InitStack(S);初始化栈 Sfor(j=0;jnext) (/找以第j个顶点为孤尾的孤的孤头k=p-adjvex;保存孤头所示的顶点的位置下标IDk-;删除该孤后，孤头所示的顶点入度减1if(IDk=0) Push(S,k);如果该顶点入度为0，就入栈、 if ( ( vej + (p-info2) ) vek) vek=vej + (p-info2); 如果j号顶点的最早发生时间与该孤的权值之和大于k号定点的 )/最早发生时间，就改变k号顶点的最早发生时间 if(countG.vexnum) return ERROR;如果拓扑序列栈中的顶点数小于图的顶点数，则表示图

15、中有环，没有关键路径 else return OK; Status Critial(ALGraph G)求关键路径函数( int i,j,k,ee,el; int vlMAX;存放各顶点最迟发生时间的数组vlStack T;/定义一个存放拓扑序列元素的栈TInitStack(T);初始化该栈ArcNode * p;if(!Topo(G,T) return ERROR;/如果拓扑排序不成功，也无法找到关键路径，就返回ERRORfor (i=0;inext)(/取出栈顶元素，并查找以j号顶点为孤尾的孤的孤头k=p-adjvex;把孤头所示的顶点位置下标值存放在k中if(vlk-(p-info2)i

16、nfo2);/如果k号顶点的最迟发生时间与该孤的权值之差小于j号定点的最迟发生时间，就改变 vljprintf(关键顶点为a：);for (j=0;jG.vexnum;j+)(if(vej=vlj) 如果定点的最早发生时间与最迟发生时间相等，则 表示该printf(%s ”,G.verticesj.data);/顶点是关键顶点，就输出该关键 顶点的名称printf(n)；printf(关键路径为：)；for (j=0;jnext)( k=p-adjvex;ee=vej;el=vlk-(p-info2);if (el=ee) printf(s ,p-info1);printf(n)；return

17、 OK;四、调试分析1、本次课程设计题目思路特别清晰，算法特别简单，但是在编程过程中遇到 了一系列的问题都值得思考与分析。2、首先是在图的创建过程中，用邻接表创建图的时候，指针使用没有正确到 位而引发了一系列问题，后来通过与老师同学一起分析才找到了问题的症结所 在。之前用临时指针p保存头结点的first指针，然后让p指向已经存好信息的 表结点pp，这样操作并没有真正把它连起来，下次循环时，又覆盖了原来的信 息。3、在成功创建了图后，把主函数中生成的图作为参数传给Critial()时，又 发现原来图中的活动这一信息又改变了，全变成乱码了，原来是由于存放活动的 字符串str3,由于不断的输入，导致

18、最后字符串什么也没有了，而图中每个孤的 活动指针都指向它，所以就全乱了，后来就把它改为字符串数组，并且把它设为 全局变量。4、在调试Critial()这一函数中，也遇到了一些问题，在观察零入度栈S的 栈顶元素和拓扑序列栈T的时候，在watch窗口中输入*(S.top-)，发现一直乱变， 根本不知道它的栈内元素，甚至怀疑栈的初始化函数有没有写对，后来通过查找 以前堆栈类型问题以及与同学题目作对比才发现就是由于窗口输入内容写错了， 应该改为*(S.top-1)。五、用户使用说明第一行输入顶点个数vexnum。第二行输入各个顶点的名称。第三行输入孤的边数arcnum。接下来的arcnum行输入每一条

19、孤的孤尾顶点、弓瓜头顶点、活动以及权值大小。六、测试结果u4v2 3 vl v3 2 v4 2 v5 a4 3 糖 4 b33丁4a? 2b5aS 1关键顶点为：叫心g u6 关锤踌径为：a2 a5 a? Press： smy key to continue七、附录以下是该程序设计的完整代码:#include#include#include#define TRUE 1#define FALSE 0#define OK 1#define ERROR 0#define OVERFLOW -2#define MAX 20#define SIZEMAX 20#define ADD 10typedef

20、int Status;typedef int Infotype;typedef char Vertextype;typedef int Elemtype;int IDMAX = 0;int veMAX = 0;char str3MAX10;typedef struct ArcNode(int adjvex;struct ArcNode * next;char * info1;int info2;ArcNode;typedef struct VNode(Vertextype data3;ArcNode * first;VNode,AdjListMAX;typedef struct(AdjList

21、 vertices;int vexnum;int arcnum;ALGraph;typedef struct(Elemtype * base;Elemtype * top;int maxsize;Stack;void Init(ALGraph &G)(G.vexnum=MAX;G.arcnum=MAX;for (int i=0;iG.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

22、 (i=0;iG.vexnum;i+)(scanf(s，G.verticesi.data);G.verticesi.first二NULL;scanf(dn，&G.arcnum);for (i=0;iG.arcnum;i+)(scanf(s%s%s%d，str1,str2,str3i,&n);for (j=0;jG.vexnum;j+)if (strcmp(str1,G.verticesj.data)=0) break;for (s=0;sadjvex=s;pp-info1=str3i;pp-info2=n;pp-next=NULL;IDs+;if (G.verticesj.first!=NUL

23、L)(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.base) exit (OVERFLOW);S.top=S.base;S.maxsize=SIZEMAX;return OK;Status Pop(Stack &S, int &e)(if(S.t

24、op=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(St

25、ack 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;jnext)(k=p-adjvex;IDk-;if(IDk=0) Push(S,k);if ( ( vej + (p-info2) ) vek) vek=vej + (p-info2);if(countG.vexnum) return ERROR;else return OK;Status Critial(ALGraph G)(

26、int i,j,k,ee,el;int vlMAX;Stack T;InitStack(T);ArcNode * p;if(!Topo(G,T) return ERROR;for (i=0;inext)(k=p-adjvex;if(vlk-(p-info2)info2);printf(关键顶点为a：);for (j=0;jG.vexnum;j+)(if (vej=vlj) printf(%s ,G.verticesj.data);printf(n)；printf(关键路径为a： )；for (j=0;jnext)(k=p-adjvex;ee=vej;el=vlk-(p-info2);if (el=ee) printf(%s ，p-info1);printf(n)； return OK;int main()(ALGraph G;Init(G);CreateGraphic(G);Critial(G);return 0;