《数据结构课程设计报告——关键路径》由会员分享，可在线阅读，更多相关《数据结构课程设计报告——关键路径（22页珍藏版）》请在金锄头文库上搜索。
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、测试数据 6 v1 v2 v3 v4 v5 v68v1 v2 a1 3v1 v3 a2 2v2 v4 a3 2v2
3、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。操作结果：通过输
4、入函数输入图的顶点个数，各顶点信息，弧的条数，以及弧的其他信息，构造图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已存在且不为空。操作结果：
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,AdjListM
6、AX;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
7、; /存放活动的字符串数组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,
8、&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+)
9、/根据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所指向的不为 空，
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指向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.
