实现求关键路径的算法【参考】.docVIP

沈阳航空航天大学 课 程 设 计 报 告 课程设计名称：数据结构课程设计 课程设计题目：实现求关键路径的算法 院（系）：计算机学院 专 业：计算机科学与技术 班 级学 号：2008040101058 姓 名：刘小靖 指导教师：许清 完成日期：2014年1月9日目 录 第一章 需求分析 1 1.1 题目内容与要求 1 1.2 题目理解与功能分析 1 第二章 概要设计 2 2.1 设计思路 2 2.2 系统模块图 2 第三章 详细设计 3 3.1 图存储结构的建立 3 3.2 求关键路径的算法 4 第四章 调试分析 6 参考文献 8 附 录（程序清单） 9 第一章 需求分析 1.1 题目内容与要求 内容： 自拟定合适的方式从键盘上输入一个AOE网，使用图的邻接表存储结构存储该AOE网，然后求出该AOE网的关键路径。输入AOE网的方式要尽量的简单方便，程序要能够形象方便地观察AOE网和它的关键路径 基本要求： 1．熟悉图的存储结构及操作方式； 2．熟悉求关键路径的算法； 3．熟练运用开发环境； 4．完成软件的设计与编码； 5. 熟练掌握基本的调试方法； 6. 提交符合课程设计规范的报告； 1.2 题目理解与功能分析 该题实质要求用数据结构中的图形知识编写一个求无循环有向帯权图中从起点到终点所有路径，经分析、比较求出长度最大路径，从而求出关键路径。 通常我们用有向图表示一个工程。在这种有向图中，用顶点表示活动，用有向边<Vi,Vj>表示活动Vi必须先于活动Vj进行。如果在这种图中用有向边表示一个工程中的各项活动（ACTIVITY），用有向边上的权值表示活动的持续时间（DURATION），用顶点表示事件（EVENT），则这种的有向图叫做用边表示活动的网络，简称AOE网络。在AOE网络中，从源点到各个顶点，可能不止一条。这些路径的长度也可能不同。不同路径所需的时间虽然不同，但只有各条路径上所有活动都完成了，这个工程才算完成。因此，完成整个工程所需的时间取决于从源点到汇点的最长路径长度，即在这条路径上所有活动的持续时间之和。这条路径长度就叫做关键路径（critical path）。 程序所要达到的功能：输入并建立AOE网；输出关键活动并求出这个工程的关键路径；求出完成这个关键路径的最少时间并输出，该程序结束。 第二章 概要设计 2.1 设计思路 基本设计思路： (1) 以某一个求无循环有向帯权图蓝本。 (2) 观察并记录这个图中每个弧的起始点及权值。 (3) 用记录的结果建立ＡＯE网，即边表示活动的网络，并用图的形式表示。 (4) 用领接表来存储图这些信息。 (5) 用Create( )函数建立AOE图。 (6) 用CriticPath ( )函数求出最大路径，并打印出关键路径。 (7) 编写代码并测试。 2.2 系统模块图 图2-1系统模块图 第三章 详细设计 3.1 图存储结构的建立 1. 先建立邻接表的存储单元，为建立邻接表做准备。为图中每个顶点建立一个单链表，第i个单链表中的结点表示依附于顶点vi的边（对于有向图是以vi为尾的弧）。每个结点由3个域组成，其中邻接域（adjvex）指示与顶点vi邻接的点在图中的位置，链域(nextedge)指示下一条边或弧的结点，权值域（W）存储边或弧的权值大小。在表头结点除了设有链域（firstedge）指向链表中第一个结点之外，还设有存储顶点v或其他有关的数据域（data）和存储顶点入度的域（id）（代码如下）。 typedef struct node { int adjvex; int w; struct node *nextedge; }edgenode; typedef struct { char data; int id; edgenode *firstedge; }vexnode; 2. 然后构造有向图。第一，输入顶点信息存储在顶点表中，并初始化该顶点的便表。第二，首先输入边所依附的两个顶点的序号i和j然后生成新的邻接点序号为j的边表结点，最后将该结点插入到第i个表头部。(代码如下) for(int k=0;k<arcnumber;k++) { scanf("%d,%d,%d",&begin,&end,&duttem); p=(edgenode*)malloc(si