数据结构课程设计：拓扑排序和关键路径(16页).doc
-数据结构课程设计：拓扑排序和关键路径-第 16 页1 ABSTRACTstruct SqStack/栈部分SElemType *base;/栈底指针SElemType *top;/栈顶指针int stacksize;/栈的大小int element_count;/栈中元素个素/AOE网的存储结构struct ArcNode /表结点int lastcompletetime;/活动最晚开始时间int adjvex; /点结点位置int info; /所对应的弧的权值struct ArcNode *next;/指向下一个表结点指针struct VNode /点结点VertexType data; /结点标志int indegree; /该结点入度数int ve; /记录结点的最早开始时间 int vl; /记录结点的最晚开始时间struct ArcNode *first_out_arc; /存储下一个出度的表结点struct ArcNode *first_in_arc;/存储下一个入度的表结点struct ALGraphVNode *vertices; /结点数组int vexnum; /结点数int arcnum; /弧数 int kind; /该图的类型 ;2 系统总分析概念分析2.1.1什么是关键路径关键路径法(Critical Path Method, CPM)最早出现于20世纪50年代，它是通过分析项目过程中哪个活动序列进度安排的总时差最少来预测项目工期的网络分析。这种方法产生的背景是，在当时出现了许多庞大而复杂的科研和工程项目，这些项目常常需要运用大量的人力、物力和财力，因此如何合理而有效地对这些项目进行组织，在有限资源下以最短的时间和最低的成本费用下完成整个项目就成为一个突出的问题，这样CPM就应运而生了。 对于一个项目而言，只有项目网络中最长的或耗时最多的活动完成之后，项目才能结束，这条最长的活动路线就叫关键路径（Critical Path），组成关键路径的活动称为关键活动。关键路径特点 关键路径上的活动持续时间决定了项目的工期，关键路径上所有活动的持续时间总和就是项目的工期。关键路径上的任何一个活动都是关键活动，其中任何一个活动的延迟都会导致整个项目完工时间的延迟。 关键路径上的耗时是可以完工的最短时间量，若缩短关键路径的总耗时，会缩短项目工期；反之，则会延长整个项目的总工期。但是如果缩短非关键路径上的各个活动所需要的时间，也不至于影响工程的完工时间。 关键路径上活动是总时差最小的活动，改变其中某个活动的耗时，可能使关键路径发生变化。可以存在多条关键路径，它们各自的时间总量肯定相等，即可完工的总工期。关键路径是相对的，也可以是变化的。在采取一定的技术组织措施之后，关键路径有可能变为非关键路径，而非关键路径也有可能变为关键路径。 2.2关键路径实现过程结构选取首先要选取建图的一种算法建立图，有邻接矩阵，邻接表，十字链表，邻接多重表等多种方法，要选取一种适当的方法建立图，才能提高算法效率，降低时间复杂度和空间复杂度。两个相邻顶点与它们之间的边表示活动，边上的数字表示活动延续的时间。对于给出的事件AOE网络，要求求出从起点到终点的所有路径，经分析、比较后找出长读最大的路径，从而得出求关键路径的算法，并给出计算机上机实现的源程序。完成不同路径的活动所需的时间虽然不同，但只有各条路径上所有活动都完成了，这个工程才算完成。具体要解决的问题（1） 将项目中的各项活动视为有一个时间属性的结点，从项目起点到终点进行排列； （2） 用有方向的线段标出各结点的紧前活动和紧后活动的关系，使之成为一个有方向的网络图； （3） 用正推法和逆推法计算出各个活动的最早开始时间，最晚开始时间，最早完工时间和最迟完工时间，并计算出各个活动的时差； （4） 找出所有时差为零的活动所组成的路线，即为关键路径； （5） 识别出准关键路径，为网络优化提供约束条件；2.2.3算法分析（1）求关键路径必须在拓扑排序的前提下进行，有环图不能求关键路径；（2）只有缩短关键活动的工期才有可能缩短工期；（3）若一个关键活动不在所有的关键路径上，减少它并不能减少工期； （4）只有在不改变关键路径的前提下，缩短关键活动才能缩短整个工期。（5）关键路径 ：从源点到汇点的路径长度最长的路径叫关键路径。（6）活动的最早开始时间e(i)；（7）活动的最晚开始时间l(i)；（8）定义e(i)=l(i)的活动叫关键活动；（9）事件的最早开始时间ve(i)；（10）事件的最晚开始时间vl(i)。设活动ai由弧<j,k>(即从顶点j到k)表示，其持续时间记为dut(<j,k>),则： e(i)=ve(j) l(i)=vl(k)-dut(<j,k>) 求ve(i)和vl(j)分两步： 1.从ve(1)=0开始向前递推ve(j)=Max ve(i)+dut(<i,j>) <i,j>T, 2<=j<=n 其中，T是所有以j为弧头的弧的集合。 2.从vl(n)=ve(n)开始向后递推 vl(i)=Min vl(j)-dut(<i,j>) <i,j>S, 1<=i<=n-1 其中，S是所有以i为弧尾的弧的集合。两个公式是在拓扑有序和逆拓扑有序的前提下进行。2. 算法步骤（1）输入e条弧<j,k>，建立AOE网的存储结构。（2）从源点v1出发，令ve(1)=0,求个点的最早开始时间ve(j)。（3）从汇点vn出发，令vl(n)=最大值，求个点的最晚开始时间vl(j)。（4）由于各结点的最早开始时间已求出来，所以各活动的最早开始时间即（每条弧s（活动）的最早开始时间）就等于该结点的最早开始时间，并由上可同时求出该活动的最晚开始时间l(j)。（5）具体表达式为： e(i)=ve(j) l(i)=vl(k)-dut(<j,k>) （6）当结点的最早开始时间ve(j)=最晚开始时间时vl(j)，则该结点为关键结点。（7）当活动的最早开始时间e(j)=最晚开始时间时l(j)，则该结点为关键活动。3 主要功能模块设计3.1程序模块栈部分模块Status InitStack(SqStack &S) /初始化栈Status DestroyStack(SqStack &S)/销毁栈Status ClearStack(SqStack &S)/清空栈Status StackEmpty(SqStack S)/判断是否为空Status StackEmpty(SqStack S)/判断是否为空Status Pop(SqStack &S,SElemType &e) /弹出元素Status GetElement(SqStack &S,int position,SElemType &e) /取元素，非弹出,i为要去元素位置无向图（AOE网）部分模块void CreateALGraph(ALGraph &graph)/初始化AOE网Status TopologicalSort(ALGraph &graph,SqStack &ToPoReverseSort) /求拓扑排序Status PutInfoToPoSort(SqStack temp,ALGraph graph) /输出拓扑顺序排序(当拓扑序列存在时）Status GetVeAndVl(ALGraph &graph,SqStack OrderSort,SqStack RevSort) /求出结点和活动的最晚开始时间和最早开始时间Status CriticalPath(ALGraph &graph,SqStack RevSort) /求出关键活动和关键事件并输出4 系统详细设计4.1主函数模块 main函数首先调用SqStack ToPoSort;SqStack ToPoReverseSort;函数来定义栈，调用InitStack(ToPoSort);来初始化存拓扑排序的栈和InitStack(ToPoReverseSort);来初始化逆拓扑排序的栈。其次调用CreateALGraph(ALGraph &graph)函数定义和初始化AOE网，调用TopologicalSor t(ALGraph &graph,SqStack &ToPoReverseSort) 函数求拓扑序列和调用PutInfoToPoSort(ToPoSort,graph);函数来输出输出拓扑顺序排序。然后调用GetVeAndVl(graph,ToPoSort,ToPoReverseSort) 函数求结点和活动的最晚开始时间、最早开始时间并输出。最后调用Status CriticalPath(ALGraph &graph,SqStack RevSort)函数来求关键活动、关键事件并输出。4.2初始化模块初始化模块用来初始化图，要求用户自己输入数据，并程序构造AOE网。本程序是用自己改进的邻接表来构造AOE网。见图2-4-24.3求拓扑序列模块 利用栈来存储入度为零的结点，然后逐个弹出，来进行与该结点的出度结点来比较，是否符合拓扑排序的规则，最后用ToPoReverseSort存放拓扑逆序序列来完成整个拓扑排序。见图2-4-34.4求最晚开始时间和最早开始时间模块 （包括结点和活动的最早和最晚开始时间）见图2-4-44.5关键活动和关键事件 见图2-4-54.6输出模块输出相应结点的信息，拓扑序列，以及事件的最早开始时间和最晚开始时间，输出相应的活动的最早开始时间和最晚开始时间，关键活动以及关键事件。5 测试分析5.1测试内容求的关键路径为：程序输入部分：求拓扑序列部分求结点和活动的最早开始时间和最晚开始时间输出图中的关键事件和关键活动（关键路径）测试关键路径结果：5.2回路测试结果分析：结果完全符合所求，但是输出的方面不够完美，并且自我感觉程序所使用的空间比较大，算法复杂度较高，所以效率比较低下，当程序输入存在有环的时候，程序没有发生任何错误，直接输出“图存在有环”然后退出程序。由此可见本程序计划实施到完工比较顺利的完成了，并且在程序测试中能够得到预期的结果出来，不过唯一不满意的是程序过于复杂化，使用的太多的空间，致使程序成为一个缺陷。参考文献1 严蔚敏，吴伟民.数据结构. 北京：清华大学出版社，2006.2 谭浩强. C程序设计（第二版）作者：清华大学出版社，2006心得体会经历几天的编程之后，课程设计终于结束了。一开始整个程序不知道怎么开始，而且算法是怎么样的都不知道，不过经过一番的查书、翻阅资料、上网查找之后终于了解到整个算法流程以及实现，首先，关键路径的实现是用邻接表来存储的，对于这个来说，本人觉得单纯按照书本的邻接表来做不太合适，于是就自己改进了一个邻接表，加上在结点里加上存储入度的变量，和加上指向所以入度的表的指针。并且在表结构上加上入度表结构。由于搜集了很多关于关键路径的资料，包括几种不同思路的程序代码，以及程序流程。然后看懂并整理这些代码，然后再其基础上增加自己需要的功能，按照自己的意愿来修改与完善。在程序输入部分采用结点，结点，弧（即结点和结点之间的权值），由于输入贯穿整个程序部分，所以输入部分十分重要。之后创建整个程序的结构，其中包括入度和出度的表结点，这两个都依附在结点结构之上。在程序求关键路径的时候，首先必须要求出整个图的拓扑排序，并用栈来保存起来，然后并在主函数里定义了两个栈，分别来存储顺序拓扑排序和逆序拓扑排序，其中在求拓扑排序的时候就遇到了一个问题就是结点存储的度数发生变化了，这个问题在后来的时候才发现的，因为之后还需要用到入度数，由此，在求拓扑序列的时候必须把入度数先用一个数组来存起来，然后求完拓扑序列之后必须把整个结点的入度数还原。/保留入度度数/int *indegree_copy=(int *)malloc(sizeof(int)*graph.vexnum);for(i=0;i<graph.vexnum;i+)*(indegree_copy+i)=(graph.vertices +i+1)->indegree ;/还原入度度数/for(i=0;i<graph.vexnum;i+)(graph.vertices +i+1)->indegree=*(indegree_copy+i) ;最后按照拓扑的顺序序列求出结点的最早开始时间，但是源结点的最早开始时间必须赋予一定的值，所以按照顺序的拓扑序列并且还可以求出活动的最早开始时间。再次，按照逆序拓扑序列来求出结点和活动的最晚开始时间。然后根据算法就可以轻易的求出关键路径和关键事件。其中在编译过程中出现了一个编译的异常，上网找了一下，说是指针越界了，于是，再设断点等手段经过长时间的摸索之后就发现了原来是程序中的栈的部分出问题了，由于之前都没有过栈出问题的情况，于是就改变了一下这个问题就没出现过了。教师评语附 录程序源代码：/ 关键路径.cpp : 定义控制台应用程序的入口点。#include "stdafx.h"#include<stdio.h>#include<stdlib.h>#define VertexType int/栈部分#define STACK_ADDITION sizeof(SElemType)#define SElemType int#define OK true#define ERROR false#define Status boolstruct SqStackSElemType *base;SElemType *top;int stacksize;int element_count;/元素个素Status InitStack(SqStack &S) /初始化栈S.base =(SElemType *)malloc(STACK_ADDITION);S.stacksize =STACK_ADDITION;S.element_count =0;if(S.base =NULL)printf("malloc errorn");exit(0);elseS.top=S.base ;return OK;Status DestroyStack(SqStack &S)/销毁栈if(S.base=NULL)printf("Stack is not existentn");elsedelete(S.base);return OK;Status ClearStack(SqStack &S)/清空栈if(S.base=NULL)printf("Stack is not existentn");se =S.top )printf("Sack is NULLn");elseS.top=S.base ;S.element_count =0;return OK;Status StackEmpty(SqStack S)/判断是否为空if(S.base=NULL)printf("Stack is not existentn");return false;if(S.top =S.base )return true;elsereturn false;Status Push(SqStack &S,SElemType e) /增加元素SElemType *temp1=S.base;SElemType *temp2=S.top;if(S.stacksize-(S.element_count *STACK_ADDITION)=STACK_ADDITION)cksize+STACK_ADDITION);S.stacksize+=STACK_ADDITION;S.top =S.base + (temp2-temp1);*S.top =e;S.top =S.top +1;S.element_count+;else*S.top =e;S.top =S.top+1;S.element_count+;return OK;Status Pop(SqStack &S,SElemType &e) /弹出元素if(S.top=S.base )printf("Stack is null! Pop error!n");return false;elsee=*-S.top ;S.element_count -;return OK;int StackLength(SqStack S)return S.element_count ;Status GetElement(SqStack &S,int position,SElemType &e) /取元素，非弹出,i为要去元素位置SElemType *temp;temp=S.top;if(S.top=S.base )printf("Stack is null! GetElement error!n");return false;else if(position<=S.element_count)e=*(temp-position);return OK;elseprintf("error!由于输入位置比栈元素数目大");return false;/=struct ArcNode /表结点int lastcompletetime;/活动最晚完成时间int adjvex; /点结点位置int info; /所对应的弧的权值struct ArcNode *next;/下一个表结点struct VNode /点结点VertexType data; /标志int indegree; /该结点入度数int ve; /记录最早开始时间 int vl; /记录最晚开始时间struct ArcNode *first_out_arc; /存储下一个出度的表结点struct ArcNode *first_in_arc;/存储下一个入度的表结点struct ALGraphVNode *vertices; /结点数组int vexnum; /结点数int arcnum; /弧数 int kind; /该图的类型void CreateALGraph(ALGraph &graph)int temp1=1;int temp2=0;int temp3=0;/权int i=0;struct ArcNode *arc1=NULL;struct ArcNode *arc2=NULL;printf("请输入结点数(结点由1开始）和图的类型：n");scanf("%d %d",&graph.vexnum,&graph.kind );graph.vertices =(VNode *)malloc(graph.vexnum+1)*sizeof(VNode);for(i=0;i<=graph.vexnum;i+)(graph.vertices+i)->data=i;(graph.vertices+i)->first_in_arc =NULL;(graph.vertices+i)->first_out_arc=NULL;(graph.vertices+i)->ve =0;(graph.vertices+i)->vl=0;(graph.vertices+i)->indegree =0;printf("请输入(格式：点，点，两点之间的权值n");graph.arcnum =-1;while(!(temp1=0&&temp2=0&&temp3=0)graph.arcnum+; /图的弧数scanf("%d %d %d",&temp1,&temp2,&temp3);(graph.vertices +temp2)->indegree) +;if(graph.vertices+temp2)->first_in_arc=NULL)(graph.vertices+temp2)->first_in_arc =(ArcNode *)malloc(sizeof(ArcNode);(graph.vertices+temp2)->first_in_arc->adjvex =temp1;(graph.vertices+temp2)->first_in_arc->info =temp3;(graph.vertices+temp2)->first_in_arc->lastcompletetime =0;/活动最晚完成时间初始化(graph.vertices+temp2)->first_in_arc->next =NULL;elsearc2=(graph.vertices+temp2)->first_in_arc;while(arc2->next!=NULL) /如果下一个不为空的话就存储下一个地址arc2=arc2->next ;arc2->next =(ArcNode *)malloc(sizeof(ArcNode);arc2->next->adjvex =temp1;arc2->lastcompletetime =0;/活动最晚完成时间初始化arc2->next->info =temp3;arc2->next->next =NULL;if(graph.vertices+temp1)->first_out_arc=NULL)(graph.vertices+temp1)->first_out_arc =(ArcNode *)malloc(sizeof(ArcNode);(graph.vertices+temp1)->first_out_arc->adjvex =temp2;(graph.vertices+temp1)->first_out_arc->info =temp3;(graph.vertices+temp1)->first_out_arc->lastcompletetime =0;/活动最晚完成时间初始化(graph.vertices+temp1)->first_out_arc->next =NULL;elsearc1=(graph.vertices+temp1)->first_out_arc;while(arc1->next!=NULL) /如果下一个不为空的话就存储下一个地址arc1=arc1->next ;arc1->next =(ArcNode *)malloc(sizeof(ArcNode);arc1->next->adjvex =temp2;arc1->next->info =temp3;arc1->next->lastcompletetime =0;/活动最晚完成时间初始化arc1->next->next =NULL;/求拓扑排序Status TopologicalSort(ALGraph &graph,SqStack &ToPoReverseSort)SqStack S;struct ArcNode *p=NULL;int k=0;int i=0;int counter;/计算拓扑序列的个数/保留入度度数/int *indegree_copy=(int *)malloc(sizeof(int)*graph.vexnum);for(i=0;i<graph.vexnum;i+)*(indegree_copy+i)=(graph.vertices +i+1)->indegree ;if(!InitStack(S)printf("初始化栈失败");for(i=1;i<=graph.vexnum;i+)if(!(graph.vertices +i)->indegree )Push(S,i);counter=0;i=0;while(!StackEmpty(S)Pop(S,i);Push(ToPoReverseSort,i);/用栈ToPoReverseSort存放拓扑逆序序列counter+;for(p=(graph.vertices +i)->first_out_arc);p;p=p->next )k=p->adjvex ;if(!(-(graph.vertices +k)->indegree )Push(S,k);DestroyStack(S);/还原入度度数/for(i=0;i<graph.vexnum;i+)(graph.vertices +i+1)->indegree=*(indegree_copy+i) ;if(counter<graph.vexnum )return ERROR;elsereturn OK;/输出拓扑顺序排序(当拓扑序列存在时）Status PutInfoToPoSort(SqStack temp,ALGraph graph)SElemType e=0;int j=temp.element_count;for(int i=1;i<=j ;i+)Pop(temp,e);printf("该结点为V%d： 数组下标为：%dn",(graph.vertices +e)->data ,e);return OK;/求出结点和活动的最晚开始时间和最早开始时间Status GetVeAndVl(ALGraph &graph,SqStack OrderSort,SqStack RevSort)int i=0,j=0;int kk=0;struct ArcNode *p=NULL;SElemType e1;SElemType e2;/求出所有结点的最早开始时间/Pop(OrderSort,e1);(graph.vertices+e1)->ve =1;kk=OrderSort.element_count;for(i=1;i<=kk ;i+)Pop(OrderSort,e2);for(j=1,p=(graph.vertices +e2)->first_in_arc);j<=(graph.vertices+e2)->indegree ;j+,p=p->next )if( (graph.vertices +e2)->ve <(graph.vertices+ p->adjvex )->ve + p->info )(graph.vertices +e2)->ve =(graph.vertices+ p->adjvex )->ve + p->info ;/求出所有结点的最晚开始时间/Pop(RevSort,e1); /弹出拓扑序列最后一个元素for(i=1;i<=graph.vexnum ;i+)(graph.vertices+i)->vl =2147483647;(graph.vertices+e1)->vl = (graph.vertices+e1)->ve ;/最晚开始时间=最早开始时间kk=RevSort.element_count;for(i=1;i<=kk ;i+)Pop(RevSort,e2);for(p=(graph.vertices +e2)->first_out_arc);p;p=p->next )p->lastcompletetime =(graph.vertices+ p->adjvex )->vl) - (p->info) ;if( (graph.vertices +e2)->vl >(graph.vertices+ p->adjvex )->vl) - (p->info) )(graph.vertices +e2)->vl =(graph.vertices+ p->adjvex )->vl) - (p->info) ;printf("nn结点信息n");printf("结点t最早开始时间t最晚开始时间t入度数n");for(i=1;i<=graph.vexnum;i+)printf("V%dt%2dtt%2dtt%2dn",(graph.vertices+i)->data,(graph.vertices+i)->ve,(graph.vertices+i)->vl,(graph.vertices+i)->indegree);printf("n活动信息n");printf("活动 最早开始时间 最晚开始时间为n");for(i=1;i<=graph.vexnum ;i+)for(p=(graph.vertices +i)->first_out_arc);p;p=p->next )printf("<V%d,V%d>tt%dtt%dn",i,p->adjvex ,(graph.vertices +i)->ve ,p->lastcompletetime );printf("nn");return OK;/求出关键活动和关键事件并输出Status CriticalPath(ALGraph &graph,SqStack RevSort)struct ArcNode *p=NULL;int i,j;int m=0;SqStack S;InitStack(S);SElemType e1;SElemType e2;for(i=1;i<=graph.vexnum ;i+)Pop(RevSort,e1);if(graph.vertices +e1)->ve = (graph.vertices +e1)->vl)Push(S,e1);/存储关键事件m=S.element_count ;for(i=1;i<=m;i+)GetElement(S,i,e1);for(j=1;j<=m;j+)GetElement(S,j,e2);for(p=(graph.vertices +e1)->first_out_arc);p;p=p->next )if( (p ->adjvex = e2) && (e1!=e2) && ( (graph.vertices +e1)->ve = p ->lastcompletetime )printf("<V%d,V%d>存在关键活动n",e1,e2);printf("关键事件为：");while(!StackEmpty(S)Pop(S,e1);printf("V%d ",e1);DestroyStack(S);return OK;void main()int i=0;int j=0;int temp;/定义栈，来存储拓扑序列和逆拓扑序列SqStack ToPoSort;SqStack ToPoReverseSort;InitStack(ToPoSort);/存拓扑排序的栈InitStack(ToPoReverseSort);/存逆拓扑排序的栈ALGraph graph;CreateALGraph(graph);if(!TopologicalSort(graph,ToPoReverseSort)printf("该图存在有环");elseprintf("拓扑序列存在（即该图不存在环），分别为：n");/图不存在环j=ToPoReverseSort.element_count ;for(i=1;i<=j;i+)GetElement(ToPoReverseSort,i,temp);Push(ToPoSort,temp);/拓扑顺序排序存储在栈ToPoSort中PutInfoToPoSort(ToPoSort,graph);/输出拓扑顺序排序printf("=n");GetVeAndVl(graph,ToPoSort,ToPoReverseSort);printf("=n");CriticalPath(graph,ToPoRevers
