数据结构课程设计报告---关键路径

《数据结构课程设计报告---关键路径》由会员上传分享，免费在线阅读，更多相关内容在学术论文-天天文库。

1、数据结构课程设计报告理论成绩实践成绩总成绩院系：信息管理学院专业：软件工程班级：软件Q1141学号：11150038姓名：李艳平教师：邓沌华时间：2013.4.2目录一、问题的描述二、系统需求及分析1、简要介绍2、需求分析3、概要设计4、详细设计(1)数据结构(2)创建有向图的邻接表(3)计算各事件及活动的相关信息(4)输出有向图的相关信息(5)判断图中是否有回路(6)计算并输出关键活动(7)计算并输出关键路径(8)操作入口三、系统实现四、设计总结五、附件（完整源代码）一、问题的描述：关键路径问题（起评分：85）1、功能：设计一个程序求出完成整项工程至少需要多少时间以及整项

2、工程中的关键活动。2、数据：自行设计每个活动的前导活动和后续活动以及活动的进行时间，然后依据这些活动的前后次序，画出其网络图，选择存储结构。3、操作：（1）求工程最短工期；（2）输出关键路径；（3）输出关键活动。4、要求：界面友好，提示信息完整。二、系统需求及分析：1、简要介绍：我们通常把计划、施工过程、生产流程、程序流程等都当成一个工程。工程通常分为若干个称为“活动”的子工程。完成了这些“活动”，这个工程就可以完成了。我们通常用AOE-网来表示工程。AOE-网是一个带权的有向无环图，其中，顶点表示事件（EVENT），弧表示活动，权表示活动持续的时间。AOE-网可以用来估算

3、工程的完成时间。他可以使人们了解：(1).研究某个工程至少需要多少时间?(2).哪些活动是影响工程进度的关键？由于AOE-网中的有些活动可以并行进行，从开始点到各个顶点，以致从开始点到完成点的有向路径可能不止一条，这些路径的长度也可能不同。完成不同路径的活动所需的时间虽然不同，但只有各条路径上所有活动都完成了，这个工程才算完成。因此，完成工程所需的最短时间是从开始点到完成点的最长路径的长度，即在这条路径上的所有活动的持续时间之和.这条路径长度就叫做关键路径(CriticalPath)。关键路径可以很方便的让我们估算出某个工程最短的时间开销，以及这个工程中哪些活动，即哪些项目

4、是主要的，是影响工程进度的关键，从而让我们对工程的实施做出更好的时间安排，并且可以分清主次，抓住核心工程，做到有的放矢。总的来说，正因为关键路径可以帮助我们对工程进行非常有必要的估算，让我们得以看清全局，作出更为优化的安排，所以可见关键路径的求出对一项工程而言是非常必要的。2、需求分析：◆建立工程网络图：采用邻接表的算法来建立图，即顺序+链式存储结构。◆计算出各事件及活动的的相关信息：如每个事件的最早和最迟开始时间，每项活动的最早最迟开始时间以及完成此活动所需的时间◆输出工程图的相关信息：用户可根据自己需要查看相关信息◆拓扑排序：以此来判断图中是否有回路，因为图中如果有回路

5、，工程就无法进行◆找出关键活动并输出◆找出关键路径并输出3、概要设计：相关说明：设某一活动的起点为i,中点为j，完成该活动所需时间为time;源点和汇点分别表示整个工程的开始事件和结束事件ve：任一事件的最早可发生时间,其值为源点到该点所有路径长度的最大值；vl：在不影响整个工程进度的情况下各事件的最晚可发生时间，其值为该点到汇点的最长路径之差；e：各项活动的最早开始时间，若以表示该活动，则e(i,j)=ve(i)；l：各项活动的最晚开始时间，若以表示该活动，则v(i,j)=vl(j)-time；d：在不增加整个工程所需总时间的情况下，某项活动可以拖延的

6、时，其值为e-l；◆采用邻接表的方式建立工程图◆对AOE网进行排序,若发现回路，则提醒用户数据错误，让其重新输入◆对于源点，对于源点，置其ve=0，依次计算出各事件的ve；对于汇点，置其vl=ve,然后依次计算出各事件的vl；再计算出各活动的e,l,d;◆找出关键活动和关键路径4、详细设计：1、数据结构：typedefstruct//顶点类型{charnum;//顶点编号intout_d;//顶点出度intin_d;//顶点入度intve;//顶点所表示的事件的最早发生时间intvl;//顶点所表示的事件的最迟发生时间}Vertex;typedefstructarcnode

7、//弧的结点结构类型{charstart;//该弧的起点,表示此弧所代表的活动开始事件charend;//该弧的终点，表示此弧所代表的活动的结束事件intvp;//该弧的终点在邻接表中的位置inttime;//完成该弧所表示的活动所需的时间inte;//该弧所代表的活动的最早开始时间intl;//该弧所代表的活动的最迟开始时间intd;//该弧所代表的活动可以拖延的时间,当d=0时表示此活动为关键活动structarcnode*nextarc;//指向下一条弧的指针}ArcNode;typedefstruct//邻