关键路径算法课程设计

《关键路径算法课程设计》由会员上传分享，免费在线阅读，更多相关内容在教育资源-天天文库。

1、沈阳航空工业学院课程设计报告课程设计名称：数据结构课程设计课程设计题目：实现求关键路径的算法院（系）：计算机学院专业：计算机科学与技术班级：7401102学号：20070401144姓名：李恰指导教师：郑智勇完成日期：2009年7月8日沈阳航空工业学院课程设计报告目录第一章需求分析11.1题目内容与要求11.2题目理解与功能分析1第二章概要设计22.1设计思路22.2系统模块图2第三章详细设计33.1图存储结构的建立33.2求取关键路径43.3主程序建立4第四章实验结果5参考文献6附录（程序清单）7-1-沈阳航空工业

2、学院课程设计报告第一章需求分析第一章需求分析1.1题目内容与要求内容：自拟定合适的方式，从键盘上输入一个AOE网，并用合适的存储结构存储该AOE网，然后求出该AOE网的关键路径。基本要求：1．输入AOE网的方式要尽量的简单方便；2．要能够较形象地观察AOE网和它的关键路径；3．课程设计报告必须符合课程设计报告规范；4．提交合格的课程设计报告，经指导教师测试课设完成（验收）程序，课设完成；1.2题目理解与功能分析该题实质要求用数据结构中的图形知识编写一个求无循环有向帯权图中从起点到终点所有路径，经分析、比较求出长度最大

3、路径，从而求出关键路径。通常我们用有向图表示一个工程。在这种有向图中，用顶点表示活动，用有向边表示活动Vi必须先于活动Vj进行。如果在这种图中用有向边表示一个工程中的各项活动（ACTIVITY），用有向边上的权值表示活动的持续时间（DURATION），用顶点表示事件（EVENT），则这种的有向图叫做用边表示活动的网络，简称AOE网络。在AOE网络中，从源点到各个顶点，可能不止一条。这些路径的长度也可能不同。不同路径所需的时间虽然不同，但只有各条路径上所有活动都完成了，这个工程才算完成。因此，完成整个工程

4、所需的时间取决于从源点到汇点的最长路径长度，即在这条路径上所有活动的持续时间之和。这条路径长度就叫做关键路径（criticalpath）。程序所要达到的功能：输入并建立AOE网；输出关键活动并求出这个工程的关键路径；求出完成这个关键路径的最少时间并输出，该程序结束。-1-沈阳航空工业学院课程设计报告第二章概要设计第二章概要设计2.1设计思路基本设计思路：(1)以某一个求无循环有向帯权图蓝本。(2)观察并记录这个图中每个弧的起始点及权值。(3)用记录的结果建立ＡＯE网，即边表示活动的网络，并用图的形式表示。(4)用领接

5、表来存储图这些信息。(5)用CreateGraph()函数建立AOE图。(6)用SearchMapPath()函数求出最大路径，并打印出关键路径。(7)编写代码并测试。2.2系统模块图图2-1系统模块图-13-沈阳航空工业学院课程设计报告第四章实验结果第三章详细设计3.1图存储结构的建立1.先建立邻接表的存储单元，为建立邻接表做准备。为图中每个顶点建立一个单链表，第i个单链表中的结点表示依附于顶点vi的边（对于有向图是以vi为尾的弧）。每个结点由3个域组成，其中邻接域（adjvex）指示与顶点vi邻接的点在图中的位置

6、，链域(nextedge)指示下一条边或弧的结点，权值域（W）存储边或弧的权值大小。在表头结点除了设有链域（firstedge）指向链表中第一个结点之外，还设有存储顶点v或其他有关的数据域（data）和存储顶点入度的域（id）（代码如下）。typedefstructnode{intadjvex;intw;structnode*nextedge;}edgenode;typedefstruct{chardata;intid;edgenode*firstedge;}vexnode;2.然后构造有向图。第一，输入顶点信息存储

7、在顶点表中，并初始化该顶点的便表。第二，首先输入边所依附的两个顶点的序号i和j然后生成新的邻接点序号为j的边表结点，最后将该结点插入到第i个表头部。(代码如下)for(intk=0;kadjvex=end-1;p->w=duttem;Graph[end-1].id++;p->nex

8、tedge=Graph[begin-1].firstedge;Graph[begin-1].firstedge=p;3.2求取关键路径利用AOE网进行工程管理时，需解决的两个主要问题：其一，计算完成整个工程的最短工期；其二，确定关键路径，以找出哪些活动时影响工程进度的关键。因此须计算以下几点：（1）事件的最早发生时间ve[k]；（2）事件最迟发