数据结构课程设计：拓扑排序和关键路径

《数据结构课程设计：拓扑排序和关键路径》由会员上传分享，免费在线阅读，更多相关内容在教育资源-天天文库。

1、数据结构课程设计报告1ABSTRACT1.1图和栈的结构定义structSqStack////栈部分{SElemType*base;//栈底指针SElemType*top;//栈顶指针intstacksize;//栈的大小intelement_count;//栈中元素个素};/////////AOE网的存储结构structArcNode//表结点{intlastcompletetime;//活动最晚开始时间intadjvex;//点结点位置intinfo;//所对应的弧的权值structArcNode*next;//指向下一个表结点指针};structVNode//点结点{

2、VertexTypedata;//结点标志intindegree;//该结点入度数intve;//记录结点的最早开始时间intvl;//记录结点的最晚开始时间structArcNode*first_out_arc;//存储下一个出度的表结点structArcNode*first_in_arc;//存储下一个入度的表结点};structALGraph{VNode*vertices;//结点数组intvexnum;//结点数intarcnum;//弧数intkind;//该图的类型};27数据结构课程设计报告2系统总分析2.1关键路径概念分析2.1.1什么是关键路径关键路径法(

3、CriticalPathMethod,CPM)最早出现于20世纪50年代，它是通过分析项目过程中哪个活动序列进度安排的总时差最少来预测项目工期的网络分析。这种方法产生的背景是，在当时出现了许多庞大而复杂的科研和工程项目，这些项目常常需要运用大量的人力、物力和财力，因此如何合理而有效地对这些项目进行组织，在有限资源下以最短的时间和最低的成本费用下完成整个项目就成为一个突出的问题，这样CPM就应运而生了。对于一个项目而言，只有项目网络中最长的或耗时最多的活动完成之后，项目才能结束，这条最长的活动路线就叫关键路径（CriticalPath），组成关键路径的活动称为关键活动。2.1

4、.2关键路径特点关键路径上的活动持续时间决定了项目的工期，关键路径上所有活动的持续时间总和就是项目的工期。关键路径上的任何一个活动都是关键活动，其中任何一个活动的延迟都会导致整个项目完工时间的延迟。关键路径上的耗时是可以完工的最短时间量，若缩短关键路径的总耗时，会缩短项目工期；反之，则会延长整个项目的总工期。但是如果缩短非关键路径上的各个活动所需要的时间，也不至于影响工程的完工时间。关键路径上活动是总时差最小的活动，改变其中某个活动的耗时，可能使关键路径发生变化。可以存在多条关键路径，它们各自的时间总量肯定相等，即可完工的总工期。关键路径是相对的，也可以是变化的。在采取一定

5、的技术组织措施之后，关键路径有可能变为非关键路径，而非关键路径也有可能变为关键路径。2.2关键路径实现过程2.2.1结构选取首先要27数据结构课程设计报告选取建图的一种算法建立图，有邻接矩阵，邻接表，十字链表，邻接多重表等多种方法，要选取一种适当的方法建立图，才能提高算法效率，降低时间复杂度和空间复杂度。两个相邻顶点与它们之间的边表示活动，边上的数字表示活动延续的时间。对于给出的事件AOE网络，要求求出从起点到终点的所有路径，经分析、比较后找出长读最大的路径，从而得出求关键路径的算法，并给出计算机上机实现的源程序。完成不同路径的活动所需的时间虽然不同，但只有各条路径上所有活

6、动都完成了，这个工程才算完成。2.2.2具体要解决的问题（1）将项目中的各项活动视为有一个时间属性的结点，从项目起点到终点进行排列；（2）用有方向的线段标出各结点的紧前活动和紧后活动的关系，使之成为一个有方向的网络图；（3）用正推法和逆推法计算出各个活动的最早开始时间，最晚开始时间，最早完工时间和最迟完工时间，并计算出各个活动的时差；（4）找出所有时差为零的活动所组成的路线，即为关键路径；（5）识别出准关键路径，为网络优化提供约束条件；2.2.3算法分析（1）求关键路径必须在拓扑排序的前提下进行，有环图不能求关键路径；（2）只有缩短关键活动的工期才有可能缩短工期；（3）若一

7、个关键活动不在所有的关键路径上，减少它并不能减少工期；（4）只有在不改变关键路径的前提下，缩短关键活动才能缩短整个工期。（5）关键路径 ：从源点到汇点的路径长度最长的路径叫关键路径。（6）活动的最早开始时间e(i)；（7）活动的最晚开始时间l(i)；（8）定义e(i)=l(i)的活动叫关键活动；（9）事件的最早开始时间ve(i)；（10）事件的最晚开始时间vl(i)。设活动ai由弧(即从顶点j到k)表示，其持续时间记为dut(),则：e(i)=ve(j)l(i)=vl(k)-dut()