关键路径算法课程设计

《数据结构》课程设计说明书题目：求网中的关键路径班级计科1203组别：指导老师：彭代文完成时间：2014.6.6组长：王勋峰学号：19组员1：蒋磊学号：18组员2：刘源学号：17组员3：陈乙生学号：16成绩：湖南工学院课程设计报告-I-目录一需求分析..................................................................................................................11.1题目内容与要求.....................................................................................................11.2题目理解与功能分析..........................................................................................1二概要设计..................................................................................................................22.1设计思路..............................................................................................................22.2系统模块图.............................................................................................................32.2系统模块图…………………………………………………………………….3三详细设计……………………………………………………………………….…43.1图存储结构的建立………………………..……………………………………43.2求取关键路径…………………………………………………………………..83.3主程序建立……………………………………………………………………10四实验结果……………………………………………………………………….11五课程设计心得…………………………………………………………………...12六参考文献………………………………………………………………………...13七附录（程序清单）………………………………………………………………14湖南工学院课程设计报告第一章需求分析-1-一需求分析1.1题目内容与要求内容：自拟定合适的方式，从键盘上输入一个AOE网，并用合适的存储结构存储该AOE网，然后求出该AOE网的关键路径。基本要求：1．输入AOE网的方式要尽量的简单方便；2．要能够较形象地观察AOE网和它的关键路径；3．课程设计报告必须符合课程设计报告规范；4．提交合格的课程设计报告，经指导教师测试课设完成（验收）程序，课设完成；1.2题目理解与功能分析该题实质要求用数据结构中的图形知识编写一个求无循环有向帯权图中从起点到终点所有路径，经分析、比较求出长度最大路径，从而求出关键路径。通常我们用有向图表示一个工程。在这种有向图中，用顶点表示活动，用有向边Vi,Vj表示活动Vi必须先于活动Vj进行。如果在这种图中用有向边表示一个工程中的各项活动（ACTIVITY），用有向边上的权值表示活动的持续时间（DURATION），用顶点表示事件（EVENT），则这种的有向图叫做用边表示活动的网络，简称AOE网络。在AOE网络中，从源点到各个顶点，可能不止一条。这些路径的长度也可能不同。不同路径所需的时间虽然不同，但只有各条路径上所有活动都完成了，这个工程才算完成。因此，完成整个工程所需的时间取决于从源点到汇点的最长路径长度，即在这条路径上所有活动的持续时间之和。这条路径长度就叫做关键路径（criticalpath）。程序所要达到的功能：输入并建立AOE网；输出关键活动并求出这个工程的关键路径；求出完成这个关键路径的最少时间并输出，该程序结束。湖南工学院课程设计报告第二章概要设计-2-二概要设计2.1设计思路基本设计思路：(1)以某一个求无循环有向帯权图蓝本。(2)观察并记录这个图中每个弧的起始点及权值。(3)用记录的结果建立AOE网，即边表示活动的网络，并用图的形式表示。(4)用领接表来存储图这些信息。(5)用CreateGraph()函数建立AOE图。(6)用CriticalPath()函数求出最大路径，并打印出关键路径。(7)编写代码并测试。湖南工学院课程设计报告第二章概要设计-3-2.2系统模块图图2-1系统模块图湖南工学院课程设计报告三详细设计-4-三详细设计3.1图存储结构的建立全局变量及用途：#defineMAX_VERTEX_NUM50//最大顶点数intindegree[MAX_VERTEX_NUM];//存放节点入度数组intve[MAX_VERTEX_NUM],vl[MAX_VERTEX_NUM];//顶点事件最早发生时间和最迟发生时间数组，全局变量初始为0intee[MAX_VERTEX_NUM],el[MAX_VERTEX_NUM];//弧活动最早发生时间和最迟发生时间数组stackintS;//存放入度为0的结点stackintT;//存放顶点的拓扑序列1先建立邻接表的存储单元，为建立邻接表做准备。为图中每个顶点建立一个单链表，第i个单链表中的结点表示依附于顶点vi的边（对于有向图是以vi为尾的弧）。每个结点由3个域组成，其中邻接域（adjvex）指示与顶点vi邻接的点在图中的位置，链域(nextedge)指示下一条边或弧的结点，权值域（W）存储边或弧的权值大小。在表头结点除了设有链域（firstedge）指向链表中第一个结点之外，还设有存储顶点v或其他有关的数据域（data）和存储顶点入度的域（id）（代码如下）。湖南工学院课程设计报告三详细设计-5-数据存储结构：typedefstructArcNode//结点结构{intadjvex;//该边所指的顶点的位置structArcNode*nextarc;//指向下一条边的指针InforTypeinfo;//弧的长度(关键路径中的活动)}ArcNode;//表的结点typedefstructVNode//顶点{VertexTypedata;//顶点信息【如数据等】ArcNode*firstarc;//指向第一条依附该顶点的边的弧指针}VNode;typedefstructALGraph{VNodevertices[MAX_VERTEX_NUM];//顶点线性表【数组】intvexnum,arcnum;//图的当前顶点数和弧数}ALGraph;湖南工学院课程设计报告三详细设计-6-2构造有向图。构图函数由增加结点和增加边构成。第一，增加结点：输入顶点数级定点信息，并初始化该顶点的边表。第二，首先输入边所依附的两个顶点及权重，最后将该结点接到第i个表尾部。(代码如下)定位函数：//==========返回顶点v在顶点向量中的位置===========intLocateVex(ALGraph*G,charv){for(inti=1;v!=G-vertices[i].data&&i=G-vexnum;i++)if(iG-vexnum)return0;returni;}//===========构造邻接链表图==================voidCreateGraph(ALGraph*G){add_vex(G);//增加节点add_arc(G);//增加边}//==============增加边=====================湖南工学院课程设计报告三详细设计-7-voidadd_arc(ALGraph*G){ArcNode*s;ArcNode*p;cout\n输入有向图边数:;cinG-arcnum;charv1,v2;intlength;cout\n\n输入边信息(始点终点权值):endl;for(intk=1;k=G-arcnum;k++){cinv1v2length;inti=LocateVex(G,v1);intj=LocateVex(G,v2);//确定v1,v2在G中的位置indegree[j]++;//点j的入度增加1s=(ArcNode*)malloc(sizeof(ArcNode));s-adjvex=j;//该边所指向的顶点的位置为js-info=length;s-nextarc=NULL;if(G-vertices[i].firstarc==NULL){G-vertices[i].firstarc=s;湖南工学院课程设计报告三详细设计-8-}else{for(p=G-vertices[i].firstarc;p-nextarc!=NULL;p=p-nextarc)//尾插法构建顶点链表;p-nextarc=s;}}}3.2求取关键路径利用AOE网进行工程管理时，需解决的两个主要问题：其一，计算完成整个工程的最短工期；其二，确定关键路径，以找出哪些活动时影响工程进度的关键。因此须计算以下几点：（1）事件的最早发生时间ve[k]；（2）事件最迟发生时间vl[k]；（3）活动最早开始时间ee[i]；（4）活动的最迟开始时间el[i]；计算其过程必须分别在拓扑有序和逆拓扑有序的前提下进行。也就说，ve[k]必须在事件vk所有前驱的最早发生的时间求得之后才能确定。因此，可以在拓扑排序的基础上计算ve[k]和vl[k]。由此得到求解关键路径的方法：首先输入arcnum条有向边i,j，建立AOE网的邻接表存储结构；然后从始湖南工学院课程设计报告三详细设计-9-点出发，令事件的最早发生时间为0，按拓扑有序求其余各顶点时间的最早发生时间ve[k]；(代码如下)If(ve[t]+p-infove[k])ve[k]=ve[t]+p-info;//ve[k]k(终点)顶点事件最早能发生的时间ve[]初始为0接着从终点出发，令事件最迟发生时间等于其最早发生时间，按你你逆拓扑排序求其余各顶点事件最迟发生时间vl[k]；最后根据各顶点事件的ve和vl值，求所有活动最早开始时间ee和最迟开始时间el。如果某活动满足条件ee＝el，则为关键活动。(代码如下)if(vl[k]-dutvl[t]){vl[t]=vl[k]-dut;}//vl[t]t(始点)顶点事件最迟发生时间for(intj=1;j=G-vexnum;j++){p=G-vertices[j].firstarc;while(p){i++;intk=p-adjvex;ee[i]=ve[j];el[i]=vl[k]-p-info;printf(|%3c|%3c|%6d|%6d|%3d|,G-vertices[j].data,G-vertices[k].data,ee[i],el[i],el[i]-ee[i]);if(el[i]==ee[i]){printf(此弧为关键活动);}p=p-nextarc;}}湖南工学院课程设计报告三详细设计-10-同时，为计算各顶点事件的ve值是在拓扑排序的过程中进行的，因此需一个栈来记录拓扑排序，如果顶点的入度为0，则该顶点入栈。intt=S.top()；S.pop();T.push(t);count++;//度为0的结点出栈S入栈T栈T保存拓扑序列cout关键路径所需时间为：ve[G-vexnum];3.3主程序建立该部分主要是对所建立的函数的调用。包括：建立图的函数CreateGraph()；计算关键路径的函数CriticalPath()；最后程序结束。这样