实现求关键路径的算法

《实现求关键路径的算法》由会员上传分享，免费在线阅读，更多相关内容在工程资料-天天文库。

1、WORD格式整理沈阳航空航天大学课程设计报告课程设计名称：数据结构课程设计课程设计题目：实现求关键路径的算法院（系）：计算机学院专业：计算机科学与技术班级：04010102学号：2008040101058姓名：刘小靖指导教师：许清完成日期：2014年1月9日学习参考资料分享WORD格式整理目录第一章需求分析11.1题目内容与要求11.2题目理解与功能分析1第二章概要设计22.1设计思路22.2系统模块图2第三章详细设计33.1图存储结构的建立33.2求关键路径的算法4第四章调试分析6参考文献8附录（程序清单）9学习参考资料分享WORD格式整理

2、第一章需求分析1.1题目内容与要求内容：自拟定合适的方式从键盘上输入一个AOE网，使用图的邻接表存储结构存储该AOE网，然后求出该AOE网的关键路径。输入AOE网的方式要尽量的简单方便，程序要能够形象方便地观察AOE网和它的关键路径基本要求：1．熟悉图的存储结构及操作方式；2．熟悉求关键路径的算法；3．熟练运用开发环境；4．完成软件的设计与编码；5.熟练掌握基本的调试方法；6.提交符合课程设计规范的报告；1.2题目理解与功能分析该题实质要求用数据结构中的图形知识编写一个求无循环有向帯权图中从起点到终点所有路径，经分析、比较求出长度最大路径，从

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

4、路径长度，即在这条路径上所有活动的持续时间之和。这条路径长度就叫做关键路径（criticalpath）。学习参考资料分享WORD格式整理程序所要达到的功能：输入并建立AOE网；输出关键活动并求出这个工程的关键路径；求出完成这个关键路径的最少时间并输出，该程序结束。学习参考资料分享WORD格式整理第二章概要设计2.1设计思路基本设计思路：(1)以某一个求无循环有向帯权图蓝本。(2)观察并记录这个图中每个弧的起始点及权值。(3)用记录的结果建立ＡＯE网，即边表示活动的网络，并用图的形式表示。(4)用领接表来存储图这些信息。(5)用Create()

5、函数建立AOE图。(6)用CriticPath()函数求出最大路径，并打印出关键路径。(7)编写代码并测试。2.2系统模块图图2-1系统模块图学习参考资料分享WORD格式整理第三章详细设计3.1图存储结构的建立1.先建立邻接表的存储单元，为建立邻接表做准备。为图中每个顶点建立一个单链表，第i个单链表中的结点表示依附于顶点vi的边（对于有向图是以vi为尾的弧）。每个结点由3个域组成，其中邻接域（adjvex）指示与顶点vi邻接的点在图中的位置，链域(nextedge)指示下一条边或弧的结点，权值域（W）存储边或弧的权值大小。在表头结点除了设有链

6、域（firstedge）指向链表中第一个结点之外，还设有存储顶点v或其他有关的数据域（data）和存储顶点入度的域（id）（代码如下）。typedefstructnode{intadjvex;intw;structnode*nextedge;}edgenode;typedefstruct{chardata;intid;edgenode*firstedge;}vexnode;2.然后构造有向图。第一，输入顶点信息存储在顶点表中，并初始化该顶点的便表。第二，首先输入边所依附的两个顶点的序号i和j然后生成新的邻接点序号为j的边表结点，最后将该结点插

7、入到第i个表头部。(代码如下)学习参考资料分享WORD格式整理for(intk=0;kadjvex=end-1;p->w=duttem;Graph[end-1].id++;p->nextedge=Graph[begin-1].firstedge;Graph[begin-1].firstedge=p;3.2求关键路径的算法利用AOE网进行工程管理时，需解决的

8、两个主要问题：其一，计算完成整个工程的最短工期；其二，确定关键路径，以找出哪些活动时影响工程进度的关键。计算其过程必须分别在拓扑有序和逆拓扑有序的前提下进行。也就说