实现求关键路径算法

沈阳航空航天大学

课 程 设 计 报 告

课程设计名称：数据结构课程设计 课程设计题目：实现求关键路径的算法

院（系）：计算机学院 专 业：计算机科学与技术 班 级：04010102 学 号：2008040101058 姓 名：刘小靖 指导教师：许清 完成日期：2014年1月9日

目 录

第一章 需求分析 ............................................................................................................ 1 1.1 题目内容与要求 .................................................................................................. 1 1.2 题目理解与功能分析 .......................................................................................... 1 第二章 概要设计 ............................................................................................................ 3 2.1 设计思路 .............................................................................................................. 3 2.2 系统模块图 .......................................................................................................... 3 第三章 详细设计 ............................................................................................................ 4 3.1 图存储结构的建立 .............................................................................................. 4 3.2 求关键路径的算法 .............................................................................................. 5 第四章 调试分析 ............................................................................................................ 7 参考文献 ........................................................................................................................ 10

附 录（程序清单） ................................................................................................... 11

第一章 需求分析

1.1 题目内容与要求

内容：

自拟定合适的方式从键盘上输入一个AOE网，使用图的邻接表存储结构存储该AOE网，然后求出该AOE网的关键路径。输入AOE网的方式要尽量的简单方便，程序要能够形象方便地观察AOE网和它的关键路径 基本要求：

1．熟悉图的存储结构及操作方式； 2．熟悉求关键路径的算法； 3．熟练运用开发环境； 4．完成软件的设计与编码； 5. 熟练掌握基本的调试方法； 6. 提交符合课程设计规范的报告；

1.2 题目理解与功能分析

该题实质要求用数据结构中的图形知识编写一个求无循环有向帯权图中从起点到终点所有路径，经分析、比较求出长度最大路径，从而求出关键路径。

通常我们用有向图表示一个工程。在这种有向图中，用顶点表示活动，用有向边表示活动Vi必须先于活动Vj进行。如果在这种图中用有向边表示一个工程中的各项活动（ACTIVITY），用有向边上的权值表示活动的持续时间（DURATION），用顶点表示事件（EVENT），则这种的有向图叫做用边表示活动的网络，简称AOE网络。在AOE网络中，从源点到各个顶点，可能不止一条。这些路径的长度也可能不同。不同路径所需的时间虽然不同，但只有各条路径上所有活动都完成了，这个工程才算完成。因此，完成整个工程所需的时间取决于从源点到汇点的最长路径长度，即在这条路径上所有活动的持续时间之和。这条路径长度就叫做关键路径（critical path）。 程序所要达到的功能：输入并建立AOE