青岛理工大学
数据结构课程设计报告
题目一： 关键路径 题目二： 全国交通运输网最佳经由问题
院（系）： 计算机工程学院 学生姓名: 刘善永 班级： 计算094 学号: 200907124 起迄日期: 2011年6月20日—2011年6月30日 指导教师: 张 艳
指导教师评语： 成绩： 签名： 年 月 日 2010—2011年度 第 2 学期
题目一：关键路径 一、需求分析 1.问题描述：
给定一个AOE-网（即带权的有向无环图），求出此图的关键路径。AOE-网中，顶点表示事件，弧表示活动，权表示活动持续的时间。用AOE-网来估算某些工程完成的时间是非常有用。
2.基本功能
对于任意给定的AOE-网，显示出该图的关键路径。 3.输入输出
程序的输出格式为：
首先输出一句话判断是否是拓扑排序； 接着输出关键路径（格式如下）：
起点 终点 dut ee el tag
输入数据：根据提示输入相应的数据。一般若依次输入多个数据时，中间要用空格隔
开。需要注意的是顶点的类型是字符串）。 测试数据如下：
. V2a4=3V5a3=2a1=3V1V4a2=2V34a5=a6=3a7=2V6
二、概要设计
1.设计思路
首先对于图的存储结构采用了邻接表的存储结构。其次对于给定的有向无环图，先对其进行拓扑排序，在对其求关键路径。 拓扑排序的算法为：
a. 在有向图中选一个没有前驱的顶点且输出之； b. 从图中删除该顶点和所有以它为尾的弧。
a8=1 重复上述两步，直至全部顶点均以输出或者当前图中不存在无前驱的顶点为止。
关键路径的算法:(其中活动的最早发生时间e(i)和最迟发生时间l(i),事件的最早发
生时间ve(i)和最迟发生时间vl(i))
a. 从源点v0出发，令ve(0)=0,对拓扑有序求出其余各顶点的ve（i）。 b. 从汇点vn出发，令vl(n-1)=ve(n-1)，按拓扑逆序求出各顶点的vl(i);
c. 根据各顶点的ve和vl的值，求每条弧s的最早发生时间e(s)和最迟发生时间
l(s).若某条弧满足e(s)=l(s),则为关键活动。
2.数据结构设计
抽象数据类型图的定义如下：
ADT Graph{
数据对象V：V是具有相同特性的数据元素的集合，称为顶点集。 数据关系R：
R={VR}
VR={（v,w）| v,w∈V,(v,w)表示v和w之间存在路径}
基本操作P:
LocateVex(G,v) 初始条件：图G存在，v和G中顶点有相同特征。
操作结果：若G中存在顶点v，则返回该顶点在图中位置；否则返回0 ，零号空
间不用。
CreateGraph(&G)
初始条件：输入顶点和边。
操作结果：根据输入的顶点和边，定义构造图。 FindInDegree(ALGraph G,int indegree[]) 初始条件：有向图G存在。
操作结果：对个顶点求入度indegree[0...vernum-1]。 TopologicOrder(ALGraph G,SqStack &T)
初始条件：有向图G存在，拓扑序列顶点栈T存在。 操作结果：若G无回路，则返回OK，否则返回ERROR。 CriticalPath(ALGraph G) 初始条件：有向图G存在。
操作结果：输出G的各项关键活动。 } ADT Graph
ADT Stack{
数据对象：D={ai|ai∈ElemSet,i=1,2,?,n,n>=0}
数据关系：R1={
基本操作：
InitStack(&S)
操作结果：构造一个空栈S。
DestroyStack(&S)
初始条件：栈S已存在。 操作结果：销毁栈S。 StackEmpty（S）
初始条件：栈S已存在。
操作结果：若S为空栈，则返回TRUE，否则返回FALSE。 Push（&S,e）
初始条件：栈S已存在。
操作结果：在栈S的栈顶插入新的栈顶元素。 Pop（&S，&e）
初始条件：栈S已存在。
操作结果：删除S的栈顶元素，并以e返回其值。 } ADT Stack
3.软件结构设计
程序中包含的模块及模块间的关系说明。 (1)主程序模块:
void main()
{
初始化G，T；
CreateGraph(G); CriticalPath(G);
}
（2）图模块——实现图的抽象数据类型
int LocateVex(ALGraph G,VertexType u)； void CreateGraph(ALGraph &G)；
void FindInDegree(ALGraph G,int indegree[])； int TopologicOrder(ALGraph G,SqStack &T)； int CriticalPath(ALGraph G)；
（3）栈模块——实现栈的抽象数据类型 void InitStack(SqStack &S)； void DestroyStack(SqStack &S)； int StackEmpty(SqStack S)； void Push(SqStack &S,char e)； int Pop(SqStack &S,int &e) 各模块之间的调用关系如下：
主程序模块 图模块 栈模块
三、详细设计
1. 定义程序中所有用到的数据及其数据结构，及其基本操作的实现；
（1）弧结点、顶点以及图的类型 #define MAX_VERTEX_NUM 21 #define NULL 0
typedef char VertexType[5]; typedef int InfoType; typedef struct ArcNode
{
int adjvex; /* 该弧所指向的顶点的位置 */ struct ArcNode *nextarc; /* 指向下一条弧的指针 */ InfoType info;//存放权值 }ArcNode; /* 弧结点 */
typedef struct {
VertexType data; /* 顶点信息 */
ArcNode *firstarc; /* 第一个表结点的地址,指向第一条依附该顶点的弧的指针 */ }VNode,AdjList[MAX_VERTEX_NUM]; /* 顶点结点的数组 */ typedef struct
{
AdjList vertices; /* 邻接表 */
int vexnum,arcnum; /* 图的顶点数和弧数 */ }ALGraph; 图的基本操作：
int LocateVex(ALGraph G,VertexType u)
{ /* 初始条件：图G存在，u和G中顶点有相同特征 */
/* 操作结果：若G中存在顶点u，则返回该顶点在图中位置；否则返回0 ，零号空间不用*/
for(i=1;i<=G.vexnum;++i)
if(strcmp(u,G.vertices[i].data)==0) return i;
return 0;}
void CreateGraph(ALGraph &G) { /* 采用邻接表存储结构*/
printf(\请输入%d个顶点的值:\\n\ for(i=0;i { scanf(\ G.vertices[i].firstarc=NULL; /* 初始化与该顶点有关的出弧链表 */ } for(k=0;k i=LocateVex(G,va); /* 弧尾 */
数据结构，课程设计，全国铁路最佳经由问题，关键路径
