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

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

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

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

4、G);初始条件：已经初始化了的图Go操作结果：通过输入函数输入图的顶点个数，各顶点信息，弧的条数，以及弧 的其他信息，构造图Go2、抽象数据类型栈的定义如下：ADT Stack 数据对象：D=ai | ai ElemSet, i=1,2,，n , nX)数据关系：Rl=vai-1 , ai> | ai-1 , ai D , i=2，n 约定an端为栈顶，ai端为栈底。基本操作：In itStack(&S)操作结果：构造一个空栈SoStackEmpty (S)初始条件：栈S已经存在。操作结果：若栈S为空栈，则返回TRUE,否则FALSEPush (&S, e)初始条件：栈S

5、已经存在。操作结果：插入元素e为新的栈顶元素。Pop (&S, &e)初始条件：栈S已存在且不为空。操作结果：删除S的栈顶元素,并用e返回其值。三、详细设计1、图的邻接表存储结构如下：#define MAX 20typedef struct ArcNode/ 表节点int adjvex;/该弧所指向的顶点的位置struct ArcNode * next; /指向下一条弧的指针char * in fol;/ 表示活动，如 al、a2、a3 等等int info2;/表示权值ArcNode;typedef struct VNode/ 头结点Vertextype data3;/ 顶点

6、信息，如 v1、v2、v3等等。ArcNode * first;/指向第一条依附该顶点的弧的指针VNode,AdjListMAX;typedef structAdjList vertices;int vex num;/图的顶点数int arcnum;/图的弧数ALGraph;2、栈的顺序存储结构如下：#define SIZEMAX 20#define ADD 10typedef int Elemtype;typedef structElemtype * base;Elemtype * top;int maxsize;Stack;3、图的构建函数设计如下：int IDMAX=0;/存放每个顶点的

7、入度的数组IDint veMAX=0;/用来存放每个顶点的最早发生时间的数组vechar str3MAX10;/存放活动的字符串数组void InitGraph(ALGraph &G) /初始化图时将图的顶点数、弧数都赋为MAX G.vex num=MAX;G.arc num=MAX;for(int i=0;i<G.vexnum;i+)/每一个头结点的first指针都指向空G.verticesi.first=NULL;void CreateGraphic(ALGraph &G)int i,j,s ,n;ArcNode *p,*pp;/定义两个指向ArcNode表结点的指针

8、p,ppchar str110,str210;/定义两个字符串str1,str2,最大长度为10sca nf("%dn" ，&G.vex num);/ 输入图的顶点数 vex numfor (i=0;i<G.vex nu m;i+)scanf("%s",G.verticesi.data);/输入各顶点的信息，顶点名称G.verticesi.first=NULL;/ 第i个头结点的 first 域指向空scanf("%dn" ，&G.arcnum); / 输入图的弧数 arcnumfor(i=0;i<G.ar

9、c nu m;i+)scanf("%s%s%s%d" ,str1,str2,str3i,&n); / 输入每条弧的其它相关信 息,str1是弧的弧尾，str2是弧的弧头，str3指的是活动，n指的是权值 for(j=0;j<G.vexnum;j+)/ 根据 str1，找对应的弧尾，若找到,则停止查找，并保存弧尾if(strcmp(str1,G.verticesj.data)=0)所示的顶点在头结点中的序号j /根据str1，找对应的弧头，若找到 则停止查找，并保存弧头break;for(s=0;s<G.arc nu m;s+)if(strcmp(str2

10、,G.verticess.data)=0)break;所示的顶点在头结点中的序号spp=(ArcNode *)malloc( sizeof(ArcNode); / 给pp 申请一个内存空pp->adjvex=s;/将弧头所指向的顶点的位置下标存放在 pp的adjvex域中pp->i nfo仁str3i;pp->i nfo2=n;pp-> next=NULL;IDs+;/将该弧的活动信息存放在pp的info1域中/将该弧的权值大小存放在pp的info2域中/pp的next指向空s的入度加1空,nextp=G.verticesj.first;/用一个临时指针保存该头结点的f

11、irst指针if(p-> next!=NULL)/如果first所指向的表结点的next指向不为while (p-> next-> next!=NULL)/则需要找下一个可存放位置/如果p所指向的表结点的if(G.verticesj.first!=NULL) /如果序号为j的头结点的first所指向的不为空，则表示该顶点已经连好了一条弧，需要找下一个可存放的位 所指向另一表结点的next不为空，就把p指针往后移一位p=p->n ext;p=p->n ext;p->next=pp;/直至U p的next指向为空，再把p的next指向ppelse G.verti

12、cesj.first=pp;/如果序号为j的头结点的first所4、堆栈的功能函数设计如下：Status In itStack(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,

13、int &e)if(S.top=S.base) /如果栈的栈顶指针等于栈底指针，则表示当前栈 为空return ERROR; /栈顶元素不存在，所以返回ERROR e=*(-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 (E

14、lemtype);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;/如果栈的栈顶指针等于栈底指针，则表示当前栈为空，返回0K else return ERROR; / 否则返回 ERROR5、求关键路径的函数设计如下：Status Topo(ALGraph G,Stack &T)/ 拓扑排序函数i

15、nt i,j,k;ArcNode *p;/定义一个指向ArcNode表结点的指针pStack S;/定义一个存放入度为0的顶点所在的下标值的栈InitStack(S);/ 初始化栈 Sfor(j=0;j<G.vexnum;j+)/查看各个顶点的入度是否为0,if(IDj=0)/若为0，就让该顶点所在位置的下标值入栈Push(Sj);int count=0;/记录进入拓扑排序栈T的元素个数while (!Empty(S)Pop(S,j); /从零入度顶点栈S中取出栈顶元素，存放在j中Push(T,j); /元素j入栈T，表示序号为j的顶点入栈coun t+;for (p=G.vertice

16、sj.first;p;p=p->n ext)/找以第j个顶点为弧尾的弧的弧头k=p->adjvex;/保存弧头所示的顶点的位置下标IDk-;/删除该弧后，弧头所示的顶点入度减1if(IDk=0) Push(S,k); /如果该顶点入度为0,就入if( ( vej + (p->i nfo2) ) > vek )vek=vej+(p->i nfo2);/如果j号顶点的最早发生时间与该弧的权值之和大于k号定点的/最早发生时间，就改变k号顶点的最早发生时间if(countvG.vexnum)return ERROR;/ 如果拓扑序列栈中的顶点数小于图的顶点数，则表示图中有

17、环，没有关键路径else return OK;Status Critial(ALGraph G)/ 求关键路径函数int i,j,k,ee,el;int vlMAX;/存放各顶点最迟发生时间的数组vlStack T;/定义一个存放拓扑序列元素的栈TIn itStack(T);/初始化该栈ArcNode * p;if(!Topo(G,T) return ERROR;/如果拓扑排序不成功，也无法找到关键路径，就返回ERRORfor(i=0;i<G.vexnum;i+)/顶点最迟发时间始化，都等于最后一个顶点的vevli=veG.vex num-1;while (!Empty(T)/在入度顶点

18、栈不为空的条件下循环for(Pop(T,j),p=G.verticesj.first;p;p=p->n ext)/取出栈顶元素，并查找以j号顶点为弧尾的弧的弧头k=p->adjvex; /把弧头所示的顶点位置下标值存放在k中 if(vlk-(p->i nfo2)<vlj) vlj=vlk-(p->i nfo2); / 如果 k 号顶点 的最迟发生时间与该弧的权值之差小于j号定点的最迟发生时间，就改变vljprintf("关键顶点为a：");for (j=0;j<G.vex nu m;j+)if(vej=vlj)/如果定点的最早发生时间与最

19、迟发生时间相等,贝憔示该printf( "%s " ,G.verticesj.data);/顶点是关键顶点，就输出该关键顶点的 名称printf( "n");printf("关键路径为：")；for (j=0;j<G.vex nu m;j+)for(p=G.verticesj.first;p;p=p->n ext) k=p->adjvex;ee=vej;el=vlk-(p->i nfo2); if(el=ee) printf( "%s " ,p->info1);printf( &quo

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

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

22、数arcnum。接下来的arcnum行输入每一条弧的弧尾顶点、弧头顶点、活动以及权值大 小。vlm3v4 v5 u6Bulu2al3vlv3a22v2u4a32u2a43v3v4a54v3v6a63u4a72v5vGa81关犍顶点为i vl u3 u4 关犍路径为；£ aS a?Press an9 kej/ to cont inue七、附录以下是该程序设计的完整代码：#include <stdio.h>#include <string.h>#include <stdlib.h>#define TRUE 1#define FALSE 0#define

23、 OK 1#define ERROR 0#define OVERFLOW -2#define MAX 20#define SIZEMAX 20#define ADD 10typedef int Status; typedef int Infotype;typedef char Vertextype; typedef int Elemtype;int IDMAX=0;int veMAX=0;char str3MAX10;typedef struct ArcNodeint adjvex;struct ArcNode * n ext; char * in fol;int in fo2;ArcNode

24、;typedef struct VNodeVertextype data3;ArcNode * first;VNode,AdjListMAX;typedef structAdjList vertices;int vex num;int arcnum;ALGraph;typedef structElemtype * base;Elemtype * top;int maxsize;Stack;void In it(ALGraph &G)G.vex num=MAX;G.arcnum=MAX;for (i nt i=0;i<G.vex nu m;i+)G.verticesi.first=

25、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.vex nu m;i+)scan f("%s" ,G.verticesi.data);G.verticesi.first=NULL;scanf("%dn" ，&G.arcnum);for(i=0;i<G.arc nu m;i+)scan f("%s%s%s%

26、d" ,str1,str2,str3i,&n);for(j=0;j<G.vex nu m;j+) if(strcmp(str1,G.verticesj.data)=0) break;for(s=0;s<G.arc nu m;s+) if(strcmp(str2,G.verticess.data)=0) break;pp=(ArcNode *)malloc( sizeof (ArcNode);pp->adjvex=s;pp->i nfo1=str3i;pp->i nfo2=n;pp-> next=NULL;IDs+;if(G.vertices

27、j.first!=NULL)p=G.verticesj.first;if(p-> next!=NULL)while (p-> next- >n ext!=NULL)p=p->n ext;p=p->n ext;p->n ext=pp;elseG.verticesj.first=pp;Status In itStack(Stack &S)sizeof(Elemtype);S.base=(Elemtype *)malloc(SIZEMAX* if(!S.base) exit (OVERFLOW);S.top=S.base;S.maxsize=SIZEMAX

28、;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;Ini tStack(S);for (j=0;j<G.vex nu m;j+)if(IDj=O)Push(S,j);