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

.数据结构课程设计报告课程题目：关键路径学 院： 班 级： 学 号： 姓 名： 指导教师： 完成日期： 目录一、需求分析3二、概要设计4三、详细设计5四、调试分析11五、用户使用说明12六、测试结果12七、附录13 一、需求分析1、问题描述AOE网(即边表示活动的网络)，在某些工程估算方面非常有用。它可以使人们了解：（1）研究某个工程至少需要多少时间？（2）哪些活动是影响工程进度的关键? 在AOE网络中，从源点到汇点的有向路径可能不止一条，但只有各条路径上所有活动都完成了，这个工程才算完成。因此，完成整个工程所需的时间取决于从源点到汇点的最长路径长度，即在这条路径上所有活动的持续时间之和，这条路径就叫做关键路径（critical path）。2、设计步骤（1）、 以某一工程为蓝本，采用图的结构表示实际的工程计划时间。（2）、 调查并分析和预测这个工程计划每个阶段的时间。 （3）、 用调查的结果建立AOE网，并用图的形式表示。 （4 ）、用CreateGraphic ()函数建立图的邻接表存储结构，能够输入图的顶点和边的信息，并存储到相应存储结构中。（5）、 用SearchMaxPath()函数求出最大路径，并打印出关键路径。 （6）、 编写代码并调试、测试通过。3、测试数据 6 v1 v2 v3 v4 v5 v68v1 v2 a1 3v1 v3 a2 2v2 v4 a3 2v2 v5 a4 3 v3 v4 a5 4v3 v6 a6 3v4 v6 a7 2 v5 v6 a8 1二、概要设计 为了实现上述函数功能：1、抽象数据类型图的定义如下：ADT Graph 数据对象V：V是具有相同特性的数据元素的集合，称为顶点集。数据关系R： R= VR ； VR=v，w|v，wV，且P(v，w)，v，w表示从v到w的弧，谓词P(v，w)定义了弧v，w的意义和信息 基本操作：InitGraph(G);初始条件：图G存在。操作结果：构造一个图的顶点数为MAX，弧的个数也为MAX，其他信息都相应初始化了的图。CreatGraph(& G);初始条件：已经初始化了的图G。操作结果：通过输入函数输入图的顶点个数，各顶点信息，弧的条数，以及弧的其他信息，构造图G。2、抽象数据类型栈的定义如下：ADT Stack 数据对象：D=ai | ai ElemSet，i=1,2, ，n，n0数据关系：Rl=ai-1，ai | ai-1，aiD，i=2，n 约定an端为栈顶，ai端为栈底。基本操作：InitStack(&S)操作结果：构造一个空栈S。StackEmpty（S）初始条件：栈S已经存在。操作结果：若栈S为空栈，则返回TRUE，否则FALSE。Push（&S，e）初始条件：栈S已经存在。操作结果：插入元素e为新的栈顶元素。Pop（&S，&e）初始条件：栈S已存在且不为空。操作结果：删除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;typedef structAdjList 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; /存放活动的字符串数组void InitGraph(ALGraph &G) /初始化图时将图的顶点数、弧数都赋为MAX G.vexnum=MAX; G.arcnum=MAX; for(int i=0;iG.vexnum;i+) /每一个头结点的first指针都指向空G.verticesi.first=NULL; void CreateGraphic(ALGraph &G) int i,j,s,n; ArcNode *p,*pp; /定义两个指向ArcNode表结点的指针p,pp char str110,str210; /定义两个字符串str1,str2,最大长度为10 scanf(%dn,&G.vexnum); /输入图的顶点数vexnum for(i=0;iG.vexnum;i+) scanf(%s,G.verticesi.data); /输入各顶点的信息,顶点名称 G.verticesi.first=NULL; /第i个头结点的first域指向空 scanf(%dn,&G.arcnum); /输入图的弧数arcnum for(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，找对应的弧尾，若找到，if(strcmp(str1,G.verticesj.data)=0) 则停止查找，并保存弧尾break; 所示的顶点在头结点中的序号jfor(s=0;sadjvex=s; /将弧头所指向的顶点的位置下标存放在pp的adjvex域中pp-info1=str3i; /将该弧的活动信息存放在pp的info1域中pp-info2=n; /将该弧的权值大小存放在pp的info2域中pp-next=NULL; /pp的next指向空 IDs+; /s的入度加1if(G.verticesj.first!=NULL) /如果序号为j的头结点的first所指向的不为 空，则表示该顶点已经连好了一条弧，需要找下一个可存放的位置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所指向的为空，直接把它的first指向pp 4、堆栈的功能函数设计如下：Status InitStack(Stack &S) /栈的初始化操作S.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) /如果栈的栈顶指针等于栈底指针，则表示当前栈为空 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.maxsize;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; /定义一个指向ArcNode表结点的指针p Stack S; /定义一个存放入度为0的顶点所在的下标值的栈 InitStack(S); /初始化栈S for(j=0;jnext) /找以第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(countG.vexnum) return ERROR; /如果拓扑序列栈中的顶点数小于图的顶点数，则表示图中有环，没有关键路径else return OK;Status Critial(ALGraph G) /求关键路径函数int i,j,k,ee,el;int vlMAX; /存放各顶点最迟发生时间的数组vl Stack T; /定义一个存放拓扑序列元素的栈T InitStack(T); /初始化该栈 ArcNode * p;if(!Topo(G,T) return ERROR; /如果拓扑排序不成功，也无法找到关键路径，就返回ERRORfor(i=0;inext) /取出栈顶元素，并查找以j号顶点为弧尾的弧的弧头k=p-adjvex; /把弧头所示的顶点位置下标值存放在k中if(vlk-(p-info2)info2); /如果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 OK;四、调试分析 1、本次课程设计题目思路特别清晰，算法特别简单，但是在编程过程中遇到了一系列的问题都值得思考与分析。 2、首先是在图的创建过程中，用邻接表创建图的时候，指针使用没有正确到位而引发了一系列问题，后来通过与老师同学一起分析才找到了问题的症结所在。之前用临时指针p保存头结点的first指针，然后让p指向已经存好信息的表结点pp，这样操作并没有真正把它连起来，下次循环时，又覆盖了原来的信息。3、在成功创建了图后，把主函数中生成的图作为参数传给Critial()时，又发现原来图中的活动这一信息又改变了，全变成乱码了，原来是由于存放活动的字符串str3，由于不断的输入，导致最后字符串什么也没有了，而图中每个弧的活动指针都指向它，所以就全乱了，后来就把它改为字符串数组，并且把它设为全局变量。4、在调试Critial()这一函数中，也遇到了一些问题，在观察零入度栈S的栈顶元素和拓扑序列栈T的时候，在watch窗口中输入*(S.top-)，发现一直乱变，根本不知道它的栈内元素，甚至怀疑栈的初始化函数有没有写对，后来通过查找以前堆栈类型问题以及与同学题目作对比才发现就是由于窗口输入内容写错了，应该改为*(S.top-1)。五、用户使用说明第一行输入顶点个数vexnum。第二行输入各个顶点的名称。第三行输入弧的边数arcnum。接下来的arcnum行输入每一条弧的弧尾顶点、弧头顶点、活动以及权值大小。六、测试结果七、附录以下是该程序设计的完整代码：#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 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 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(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!=NULL) p=G.verticesj.first; if(p-next!=NULL) while(p-next-next!=NULL) p=p-next;p=p-next; p-next=pp; else G.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.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+