《数据结构》 课程设计报告
课程题目：关键路径
学 院： 班 级： 学 号： 姓 名： 指导教师： 完成日期：
目录
一、需求分析 ............................................................. 2
1
二、概要设计 ............................................................. 4 三、详细设计 ............................................................. 5 四、 调试分析 .......................................................... 11 五、 用户使用说明 .................................................. 12 六、 测试结果 .......................................................... 12 七、 附录 ................................................................. 12
一、需求分析
1、问题描述
2
AOE网(即边表示活动的网络)，在某些工程估算方面非常有用。它可以使人们了解：（1）研究某个工程至少需要多少时间？（2）哪些活动是影响工程进度的关键? 在AOE网络中，从源点到汇点的有向路径可能不止一条，但只有各条路径上所有活动都完成了，这个工程才算完成。因此，完成整个工程所需的时间取决于从源点到汇点的最长路径长度，即在这条路径上所有活动的持续时间之和，这条路径就叫做关键路径（critical path）。
2、设计步骤
（1）、 以某一工程为蓝本，采用图的结构表示实际的工程计划时间。 （2）、 调查并分析和预测这个工程计划每个阶段的时间。 （3）、 用调查的结果建立AOE网，并用图的形式表示。
（4 ）、用CreateGraphic ()函数建立图的邻接表存储结构，能够输入图的顶点和边的信息，并存储到相应存储结构中。
（5）、 用SearchMaxPath()函数求出最大路径，并打印出关键路径。 （6）、 编写代码并调试、测试通过。 3、测试数据
v2 ○v5 ○v1 ○v4 ○v6 ○v3 ○6
v1 v2 v3 v4 v5 v6 8
v1 v2 a1 3 v1 v3 a2 2 v2 v4 a3 2
v2 v5 a4 3 v3 v4 a5 4 v3 v6 a6 3 v4 v6 a7 2 v5 v6 a8 1
3
二、 概要设计
为了实现上述函数功能： 1、抽象数据类型图的定义如下： ADT Graph {
数据对象V：V是具有相同特性的数据元素的集合，称为顶点集。 数据关系R： R={ VR }；
VR={＜v，w＞|v，w∈V，且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，n≥0} 数据关系：Rl={＜ai-1，ai＞ | ai-1，ai∈D，i=2，…，n } 约定an端为栈顶，ai端为栈底。 基本操作： InitStack(&S)
操作结果：构造一个空栈S。 StackEmpty（S）
初始条件：栈S已经存在。
操作结果：若栈S为空栈，则返回TRUE，否则FALSE。
4
Push（&S，e）
初始条件：栈S已经存在。
操作结果：插入元素e为新的栈顶元素。 Pop（&S，&e）
初始条件：栈S已存在且不为空。
操作结果：删除S的栈顶元素，并用e返回其值。 }
三、详细设计
1、图的邻接表存储结构如下：
#define MAX 20
typedef struct ArcNode //表节点 {
int adjvex; //该弧所指向的顶点的位置 struct ArcNode * next; //指向下一条弧的指针 char * info1; //表示活动，如a1、a2、a3等等 int info2; //表示权值 }ArcNode;
typedef struct VNode //头结点 {
Vertextype data[3]; //顶点信息，如v1、v2、v3等等。 ArcNode * first; //指向第一条依附该顶点的弧的指针。}VNode,AdjList[MAX];
typedef struct {
AdjList vertices;
int vexnum; //图的顶点数 int arcnum; //图的弧数
}ALGraph;
5
数据结构课程设计 - 关键路径
