数据结构课程设计报告——关键路径

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

2、路径就叫做关键路径(critical path )。2、设计步骤(1)、以某一工程为蓝本，采用图的结构表示实际的工程计划时间。(2)、调查并分析和预测这个工程计划每个阶段的时间。(3)、用调查的结果建立AOER,并用图的形式表示。(4 )、用CreateGraphic ()函数建立图的邻接表存储结构，能够输入图的 顶点和边的信息，并存储到相应存储结构中。(5)、用SearchMaxPath()函数求出最大路径，并打印出关键路径。(6)、编写代码并调试、测试通过。3、测试数据、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二、概要设计为了实现上述函数功能：1、抽象数据类型图的定义如下：ADT Graph 数据对象V： V是具有相同特性的数据元素的集合，称为顶点集。数据关系RR= VR ;VR= <v, w>|v , wC V,且P(v , w), < v, w>表示从 v至UW勺弧，谓词 P(v , w)定义了弧< v, w>的意义和信息 基本操作：InitGraph(G);初始条件：图G#在。操作结果：构造一个图的顶点数为MAX弧的个数也为MAX其他信息都相应初始 化了的图。CreatGr

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

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

6、pe data3; / 顶点信息，如 v1、v2、v3等等。ArcNode * first;/指向第一条依附该顶点的弧的指针VNode,AdjListMAX;typedef structAdjList vertices;int vexnum;/图的顶点数int arcnum;/图的弧数ALGraph;教育资料2、栈的顺序存储结构如下:#defineSIZEMAX 20#defineADD 10typedefint Elemtype;typedefstructElemtype * base;Elemtype * top;int maxsize;3、Stack;图的构建函数设计如下:int IDM

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

8、 str110,str210; /定义两个指向ArcNodeS结点的指针p,pp定义两个字符串str1,str2,最大长度为scanf( "%dn" ,&G.vexnum);/ 输入图的顶点数vexnumfor (i=0;i<G.vexnum;i+)输入各顶点的信息，顶点名scanf( "%s",G.verticesi.data); /G.verticesi.first=NULL; /第i个头结点的first域指向空scanf( "%dn" ,&G.arcnum); 输入图的弧数 arcnum for (i=0;

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

10、data)=0)则停止查找，并保存弧头break;所示的顶点在头结点中的序号spp=(ArcNode *)malloc( sizeof (ArcNode); /给pp中请一个内存空pp->adjvex=s; /域中pp->info1=str3i; /中pp->info2=n; /pp->next=NULL; /ppID回+;/sif (G.verticesj.first!=NULL) /向的不为pp 的 adjvex将该弧的活动信息存放在pp的info1域将该弧的权值大小存放在pp的info2域中 的next指向空的入度加1如果序号为j的头结点的first所指将弧头所指

11、向的顶点的位置下标存放在用一个临时指针保存该头结点的空，则表示该顶点已经连好了一条弧，需要找下一个可存放的位置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; /直至1J p的next指向为空，再把 p的next指向ppelse

12、 G.verticesj.first=pp; /如果序号为 j 的头结点的first所指向的为空，直接把它的first指向pp4、堆栈的功能函数设计如下：Status InitStack(Stack &S) /栈的初始化操作S.base=(Elemtype *)malloc(SIZEMAX* sizeof (Elemtype); 给栈分配内存空间if (!S.base) exit (OVERFLOW); /若分配不成功，则返回 OVERFLOWS.top=S.base; /让栈的栈顶指针和栈底指针相等S.maxsize=SIZEMAX; / 栈的当前容量为 SIZEMAX return

13、 OK;Status Pop(Stack &S, int &e)if (S.top=S.base) /如果栈的栈顶指针等于栈底指针，则表示当前栈为空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

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;/如果栈的栈顶指针等于栈底指针，则表示当前栈为空，返回OKelse return ERROR; / 否则返回 ERROR5、求关键路径的函数设计如下：Status Topo(AL

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

16、入栈T,表示序号为j的顶点入栈 count+;for (p=G.verticesj.first;p;p=p->next)/ 找以第j个顶点为弧尾的弧的弧头k=p->adjvex; /保存弧头所示的顶点的位置下标IDk-;/删除该弧后，弧头所示的顶点入度减1if (IDk=0) Push(S,k); /如果该顶点入度为0,就入栈Sif ( ( vej + (p->info2) ) > vek) vek=vej+(p->info2);/如果j号顶点的最早发生时间与该弧的权值之和大于k号定点的/最早发生时间，就改变k号顶点的最早发生时间if (count<G.ve

17、xnum) return ERROR; /如果拓扑序列栈中的顶点数小于图的顶点数，则表示图中有环，没有关键路径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;i<G.vexnum;i+) /顶点最迟发时间始化

18、，都等于最后一个顶点 的vevli=veG.vexnum-1;while (丘mpty(T) /在入度顶点栈不为空的条件下循环for (Pop(T,j),p=G.verticesj.first;p;p=p->next) /取出栈顶元素，并查找以j号顶点为弧尾的弧的弧头k=p->adjvex; /把弧头所示的顶点位置下标值存放在k中if (vlk-(p->info2)<vlj) vlj=vlk-(p->info2); /如果k号顶点的最迟发生时间与该弧的权值之差小于j号定点的最迟发生时间，就改变 vljprintf("关键顶点为a：");for

19、(j=0;j<G.vexnum;j+)if (vej=vlj) /如果定点的最早发生时间与最迟发生时间相等，则表示该printf( "%s " ,G.verticesj.data);/ 顶点是关键顶点，就输出该关键 顶点的名称printf( "n");printf("关键路径为：");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;四、调试分析1、本次课程设计题目思路特别清晰，算法特别简单，但是在编程过程中遇到了 一系列的问题都值得思考与分析。2、首先是在图的创建过程中，用邻接表创建图的时候，指针使用没有正确到 位而引发了一系列问题，后来通过与老师同学一起分析才找到了问题的症结所 在。之前用临时指针p保存头结点的first指针，然后让p指向已经存好信息的 表结点pp,这样操作并没有真正把它连起来，下次循环时，又覆盖了原来的信 息。3、在成功创建了图后，把主函数中生成的图作为参数传给 Critial

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

22、行输入顶点个数vexnumi第二行输入各个顶点的名称。第三行输入弧的边数arcnum。接下来的arcnum行输入每一条弧的弧尾顶点、弧头顶点、活动以及权值大小。六、测试结果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 关键顶点为:M v3 v4 v6 美耀路径为；m2 aS a? Press any key to continue七、附录以下是该程序设计的完整代码:#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