数据结构课程设计报告_关键路径.doc

数 据 结 构 课 程 设 计 报 告 理论成绩 实践成绩 总成绩 院系： 信息管理学院 专业： 软件工程 班级： 软件Q1141 学号： 姓名： 李艳平 教师： 邓沌华 时间： 2013.4.2 目录 问题的描述 系统需求及分析 简要介绍 需求分析 概要设计 详细设计 数据结构 创建有向图的邻接表 计算各事件及活动的相关信息 输出有向图的相关信息 判断图中是否有回路 计算并输出关键活动 计算并输出关键路径 操作入口 系统实现 设计总结 附件（完整源代码） 一、问题的描述： 关键路径问题（起评分：85） 1、功能：设计一个程序求出完成整项工程至少需要多少时间以及整项工程中的关键活动。 2、数据：自行设计每个活动的前导活动和后续活动以及活动的进行时间，然后依据这些活动的前后次序，画出其网络图，选择存储结构。 3、操作：（1）求工程最短工期；（2）输出关键路径；（3）输出关键活动。 4、要求：界面友好，提示信息完整。 二、系统需求及分析： 1、简要介绍： 我们通常把计划、施工过程、生产流程、程序流程等都当成一个工程。工程通常分为若干个称为“活动”的子工程。完成了这些“活动”，这个工程就可以完成了。 我们通常用AOE-网来表示工程。AOE-网是一个带权的有向无环图，其中，顶点表示事件（EVENT），弧表示活动，权表示活动持续的时间。 AOE-网可以用来估算工程的完成时间。他可以使人们了解： (1). 研究某个工程至少需要多少时间? (2). 哪些活动是影响工程进度的关键？ 由于AOE-网中的有些活动可以并行进行，从开始点到各个顶点，以致从开始点到完成点的有向路径可能不止一条，这些路径的长度也可能不同。完成不同路径的活动所需的时间虽然不同，但只有各条路径上所有活动都完成了，这个工程才算完成。因此，完成工程所需的最短时间是从开始点到完成点的最长路径的长度，即在这条路径上的所有活动的持续时间之和.这条路径长度就叫做关键路径(Critical Path)。 关键路径可以很方便的让我们估算出某个工程最短的时间开销，以及这个工程中哪些活动，即哪些项目是主要的，是影响工程进度的关键，从而让我们对工程的实施做出更好的时间安排，并且可以分清主次，抓住核心工程，做到有的放矢。 总的来说，正因为关键路径可以帮助我们对工程进行非常有必要的估算，让我们得以看清全局，作出更为优化的安排，所以可见关键路径的求出对一项工程而言是非常必要的。 2、需求分析： ◆建立工程网络图：采用邻接表的算法来建立图，即顺序+链式存储结构。 ◆计算出各事件及活动的的相关信息：如每个事件的最早和最迟开始时间，每项活动的最早最迟开始时间以及完成此活动所需的时间 ◆输出工程图的相关信息：用户可根据自己需要查看相关信息 ◆拓扑排序：以此来判断图中是否有回路，因为图中如果有回路，工程就无法进行 ◆找出关键活动并输出 ◆找出关键路径并输出 3、概要设计： 相关说明：设某一活动的起点为i, 中点为j，完成该活动所需时间为time; 源点和汇点分别表示整个工程的开始事件和结束事件 ve：任一事件的最早可发生时间, 其值为源点到该点所有路径长度的最大值； vl：在不影响整个工程进度的情况下各事件的最晚可发生时间，其值为该点到汇点的最长路径之差； e：各项活动的最早开始时间，若以i, j表示该活动，则e(i,j) = ve(i)； l：各项活动的最晚开始时间，若以i, j表示该活动，则v(i,j) = vl(j)-time； d：在不增加整个工程所需总时间的情况下，某项活动可以拖延的时，其值为e-l； 采用邻接表的方式建立工程图 对AOE网进行排序, 若发现回路，则提醒用户数据错误，让其重新输入 对于源点，对于源点，置其ve = 0，依次计算出各事件的ve；对于汇点，置其vl = ve, 然后依次计算出各事件的vl；再计算出各活动的e, l, d; 找出关键活动和关键路径 4、详细设计： 1、数据结构： typedef struct//顶点类型 { char num; //顶点编号 int out