-
。
《数据结构》
课程设计报告
课程题目：关键路径
学
院：
班
级：
学
号：
姓
名：
指导教师：
完成日期：
目录
一、需求分析
................................
2
精选资料，欢迎下载
。
二、概要设计
................................
4
三、详细设计
................................
5
四、
调试分析
..............................
12
五、
用户使用说明
..........................
12
六、
测试结果
..............................
七、
附录
..................................
一、需求分析
1
、问题描述
精选资料，欢迎下载
13
13
。
AOE
网
(
即边表示活动的网络
)
，在某些工程估算方面非常有用。它可以使人
们了解：
（
1
）研究某个工程至少需要多少时间？（
< br>2
）哪些活动是影响工程进度
的关键
?
在
AOE
网络中，
从源点到汇点的有向路径可能不止一条，
但只有各条路
径上所有活动都完成了，
这个工程才算完成。
因此，
完成整个工程所需的时间取
决于从源点到汇点的最长路径长度，即在这
条路径上所有活动的持续时间之和，
这条路径就叫做关键路径（
critical path
）。
2
、设计步骤
（
1
）、
以某一工程为蓝本，采用图的结构表示实际的工程计划时间。
（
2
）、
调查并分析和预测这个工程计划每个阶段的时间。
（
3
）、
<
/p>
用调查的结果建立
AOE
网，并用图的形
式表示。
（
4
）、用
CreateGraphic
()
函数建立图的邻接表存储结构，能够输入图的
顶点和边的信
息，并存储到相应存储结构中。
（
5
）、
<
/p>
用
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
精选资料，欢迎下载
。
二、
概要设计
为了实现上述函数功能：
1
、抽象数据类型图的定义如下：
ADT Graph {
数据对象
V
：
V
是具有相同特性的数据元素的集合
，称为顶点集。
数据关系
R
：
R={ VR }
；
VR={
＜
v
，
w
＞
|v
，
w
∈
V
，
且
P(v
，
w)
，
＜
v
< br>，
w
＞表示从
v
到
w
的弧，
谓词
P(v
，
w)
定义了弧＜<
/p>
v
，
w
＞的意义
和信息
}
基本操作：
InitGraph(G);
初始条件：图
< br>G
存在。
操作结果：
构造一个图的顶点数为
MAX
，
弧的个数也为
MAX
，
其他信
息都相应初始
化了的图。
CreatGraph(& G);
初始条件：已经初始化了
的图
G
。
操
作结果：通过输入函数输入图的顶点个数，各顶点信息，弧的条数，以及弧的
其他信息，
构造图
G
。
}
2
、抽象数据类型栈的定义如下：
ADT Stack {
数据对象：
D={ai | ai
∈
ElemSet
，
i=1,2,
…，
n
，
n
≥
0}
数据关系：
Rl={
＜
ai-1
< br>，
ai
＞
| ai-1
，
ai
∈
D
，
i=2
，…，
n }
约定
a
n
端为栈顶，
a
i
端为栈底。
基本操作：
InitStack(&S)
操作结果：构造一个空栈
S
。
StackE
mpty
（
S
）
初始条件：栈
S
已经存在。
操作结果：若栈
S
为空栈，则返回
TRUE
，否则
FAL
SE
。
精选资料，欢迎下载
。
Push
（
&S
，
e
）
初始条件：栈
S
已经存在。
操作结果：插入元素
e
为新的栈顶元素。
Pop
（
&S
，
&e
）
初始条件：栈
S<
/p>
已存在且不为空。
操作结果：删除
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;
精选资料，欢迎下载
。
2
、栈的顺序存储结构如下：
#define SIZEMAX 20
#define
ADD 10
typedef int Elemtype;
typedef struct
{
Elemtype * base;
Elemtype * top;
int maxsize;
}Stack;
3
、图的构建函数设计如下：
int ID[MAX]={0};
//
存放每个顶点的入度的数组
ID
int ve[MAX]={0};
//
用来存放每个顶点的最早发生时间的数组
ve
char str3[MAX][10];
//
存放活动的字符串数组
void
InitGraph(ALGraph &G)
//
初始化图时将图的顶点数、弧数都赋为
MAX
{
=MAX;
=MAX;
for(int i=0;i<;i++) //
每一个
头结点的
first
指针都指向空
}
void CreateGraphic(ALGraph &G)
{
int
i,j,s,n;
ArcNode *p,*pp; //
定义两个指向
ArcNode
表结点的指针
p,pp
char
str1[10],str2[10]; //
定义两个字符串
str1,str2,
最大长度为
10
scanf(
输入图的顶点数
vexnum
for(i=0;i<;i++)
es[i].first=NULL;
{
scanf(
输入各顶点的信息
,
顶点名
精选资料，欢迎下载
。
称
es[i].first=NULL; //
第
i
个头结点的
first
域指向空
}
scanf(
输入图的弧数
arcnum
for(i=0;i<;i++)
{
scanf(
输入每条弧的其它相
关信息
,str1
是弧的弧尾，
str2
是弧的弧头，
str3
指的是活动，
n
指的
是
权值
弧尾
弧头
间
域中
中
pp->info2=n;
//
将该弧的权值大小存放在
pp
的<
/p>
info2
域中
pp->next=NULL; //pp
的
next
指向空
ID[s]++;
//s
的入度加
1
if(es[j].first!=NULL) //
如果序号
为
j
的头结点的
first
所指
pp->info1=str3[i]; //
将该弧的活动信息存放在
pp
的
info1
域
pp->adjvex=s; /
/
将弧头所指向的顶点的位置下标存放在
pp
< br>的
adjvex
break;
所示的顶点在头结点中的序号
s
break;
所示的顶点在头结点中的序号
j
for(j=0;j<;j++) //
根据<
/p>
str1
，
找对应的弧尾，
若找到，
if(strcmp(str1,es[j].data)==0)
则停止查找，
并保存
for(s=0;s<;s++
) //
根据
str1
，
找对应的弧头，
若找到
if(strcmp(str2,es[s].data)==0)
则停止查找，
并保存
pp=(ArcNode
*)malloc(sizeof(ArcNode)); //
给
pp
申请一个内存空
向的不为
{
空，
则表示该顶点已经连好
了一条弧，
需要找下一个可存放的位置
p=es[j].first; //
用一个临时指针保存该头结点的
first
指针
精选资料，欢迎下载
。
为空，
next
if(p->next!=NULL) //
如果
first
所指向的表结点的
next
指向不
{
//
则需要找下一个可存放位置
while(p->next->next!=NULL) //
< br>如果
p
所指向的表结点的
{
所指向另一表结点的
next
不为空，就把
p
< br>指针往后移一位
}
p=p->next;
p=p->next;
}
}
p->next=pp; /
/
直到
p
的
n
ext
指向为空，再把
p
的
next
指向
pp
else es[j].first=pp; //
如果序号为
j
的头结点
的
first
所指向的为空，直接把它的
firs
t
指向
pp
}
}
4
、堆栈的功能函数设计如下：
Status InitStack(Stack &S)
//
栈的初始化操作
{
=(Elemtype
*)malloc(SIZEMAX*sizeof(Elemtype));
//
给栈分配内
存空间
if(!) exit (OVERFLOW);
//
若分配不成功，则返回
OVERFLOW
< br>；
=;
//
让栈的栈顶指针和栈底指针相等
e=SIZEMAX;
//
栈的当前容量为
SIZEMAX
return OK;
}
Status Pop(Stack &S,int &e)
{
if(==) //<
/p>
如果栈的栈顶指针等于栈底指针，
则表示当前栈
< br>为空
return ERROR;
//
栈顶元素不存在，所以返回
ERROR
精选资料，欢迎下载
。
e=*(--); //
如果栈不为
空，就取出
S
的栈顶指针所指向的数据，
return OK; //
并把
top
指针往下移一个位置
}
Status Push(Stack
&S,int e)
{
if(>=e)
//
如果当前栈内存
的元素超过了它的最大存
放量
{ //
则必须追加空间
=(Elemtype
*)realloc(,(e+ADD)*sizeof(Elemtype));
}
*(++)=e; //top
指针往上移一位后，让
top
指针指向元素
e
return OK;
}
Status Empty(Stack S)
{
if(==) return OK;
//
如果栈的栈顶指针等于栈底指针，则表示当前栈为空
,
返回
OK
else return ERROR;
//
否则返回
ERROR
}
5
、求关键路径的函数设计如下：
Status Topo(ALGraph G,Stack &T)
//
拓扑排序函数
{
int i,j,k;
ArcNode *p; //
定义一个指向
ArcNo
de
表结点的指针
p
Stack S; //
定义一个存放入
度为
0
的顶点所在的下标值的栈
InitStack(S);
//
初始化栈
S
for(j=0;j<;j++) //
查看各个顶
点的入度是否为
0
，
if(!)
exit
(OVERFLOW);
=+e;
e=e+ADD;
精选资料，欢迎下载
-
-
-
-
-
-
-
-
-
上一篇：小孩子学英语三个不要
下一篇：3DS MAX标准文本导出格式ASE的文件结构