《数据结构求关键路径实习报告》由会员分享,可在线阅读,更多相关《数据结构求关键路径实习报告(15页珍藏版)》请在金锄头文库上搜索。
1、河 南 工 程 学 院实 习 报 告系(部) 专 业 班 级 姓 名 学 号 2011 年 7月 1日实 习 (训) 报 告 评 语等 级: 评阅人: 职称: 年月日河南工程学院实习(训)报告实习内容: 关键路径问题 实习时间:自 6 月 27 日 至 7 月 1 日 共5 天实习地点: 实习单位: 指导教师: 系主任: 目 录一、设计目标1二、课题分析与设计21课题需求分析22存储结构设计23算法设计34程序流程图4三、程序清单5四、测试91测试数据92测试结果及分析9五、总结111收获112不足113算法改进分析11一、设计目标用带权有向图构造的AOE网表示一项工程计划,图的结点表示事件,
2、弧表示活动,权值表示活动持续时间。完成工程的最短时间是从开始点到完成点的最长路径的长度。路径长度最长的路径叫关键路径。关键路径上的所有活动都是关键活动。求关键路径必须在拓扑排序的前提下进行,有环图不能求关键路径;只有缩短关键活动的工期才有可能缩短工期;若一个关键活动不在所有的关键路径上,减少它并不能减少工期;只有在不改变关键路径的前提下,缩短关键活动才能缩短整个工期。本次实训设计程序,任意给出表示工程计划的顶点及带权弧的有向图信息,即可判断整项工程计划是否合理,求出工程计划中的关键路径及关键活动。完成整项工程至少需要的时间。二、课题分析与设计1课题需求分析1.1问题描述:(1)选取建图的一种算
3、法建立图,有邻接矩阵,邻接表,十字链表,邻接多重表等多种方法,要选取一种适当的方法建立图,才能提高算法效率,降低时间复杂度和空间复杂度。(2)两个相邻顶点与它们之间的边表示活动,边上的数字表示活动延续的时间。对于给出的事件AOE网络,要求求出从起点到终点的所有路径,经分析、比较后找出长读最大的路径,从而得出求关键路径的算法,并给出计算机上机实现的源程序。完成不同路径的活动所需的时间虽然不同,但只有各条路径上所有活动都完成了,这个工程才算完成。具体要解决的问题有如下四个:1) 将项目中的各项活动视为有一个时间属性的结点,从项目起点到终点进行排列; 2) 用有方向的线段标出各结点的紧前活动和紧后活
4、动的关系,使之成为一个有方向的网络图; 3) 用正推法和逆推法计算出各个活动的最早开始时间,最晚开始时间,最早完工时间和最迟完工时间,并计算出各个活动的时差; 4) 找出所有时差为零的活动所组成的路线,即为关键路径; 1.2 基本要求(1)选取建图的一种算法建立图;选取邻接表的算法来建立图,是一种顺序+ 链式存储结构。用顺序表存放顶点,为每个顶点建立一个单链表,单链表中的结点表示依附于该顶点的边或以该顶点为尾的弧。(2)两个相邻顶点与它们之间的边表示活动,边上的数字表示活动延续的时间。参照该工程所化的AOE-网,求出从起点到终点的所有路径,然后通过拓扑排序和逆拓扑排序求出最早与最晚发生时间,找
5、出长度最大的路径,从而求得关键路径。2存储结构设计对于带权有向图构造的AOE网,采用链式存储结构,定义的结构体如下:typedef struct node /定义表结点 int adjvex; /该弧所指向的顶点的位置 int dut; /弧的权值 struct node *next; /指向下一条弧的指针 edgenode; typedef struct /定义头结点 int projectname; /顶点信息 int id; /结点入度 edgenode *link; /指向第一条依附该顶点的弧的指针vexnode; 3算法设计3.1 算法准备为求关键路径,设开始点是V1,从V1到Vi的
6、最长路径长度叫做事件Vi的最早发生时间。这个时间决定了所有以Vi为尾的弧所表示的活动的最迟开始时间。用e(i)表示活动ai的最早开始时间。用l(i)表示活动的最迟开始时间,即在不推迟整个工程完成的前提下,活动ai最迟必须开始的时间。两者之差l(i)-e(i)意味着完成活动ai的时间余量。其中l(i)=e(i)的活动叫做关键活动。用ve(i) 表示事件开始的最早时间,vl(i)表示事件开始的最晚时间。设活动ai由弧(即从顶点j到k)表示,其持续时间记为dut(),则:e(i)=ve(j)l(i)=vl(k)-dut()求ve(i)和vl(j)分两步:(1).从ve(1)=0开始向前递推ve(j)
7、=Max ve(i)+dut() T,2=j=n其中,T是所有以j为弧头的弧的集合。(2).从vl(n)=ve(n)开始向后递推vl(i)=Min vl(j)-dut() S,1=i=n-1其中,S是所有以i为弧尾的弧的集合。两个递推公式是在拓扑有序和逆拓扑有序的前提下进行。3.2 算法步骤(1)输入e条弧,建立AOE网的存储结构。(2)从源点v1出发,令ve(1)=0,按拓扑有序求其余各顶点的最早发生时间ve(i)(2=i=n)。如果得到的拓扑有序序列中顶点个数小于网中顶点数n,则说明网中存在环,不能求关键路径,算法终止;否则执行步骤3。 (3)从汇点vn出发,令vl(n)=ve(n),求
8、按逆拓扑有序求其余各顶点的最迟发生时间vl(i)(1=i=n-1)。(4)根据各顶点的ve和vl值,求每条弧s(活动)的最早开始时间e(s)和最晚开始时间l(s),若某条弧满足条件e(s)=l(s),则为关键活动。4程序流程图 三、程序清单#include #include #include #include typedef struct node /定义表结点 int adjvex; /该弧所指向的顶点的位置 int dut; /弧的权值 struct node *next; /指向下一条弧的指针 edgenode; typedef struct /定义头结点 int projectname
9、; /顶点信息 int id; /结点入度 edgenode *link; /指向第一条依附该顶点的弧的指针vexnode; void CreateGraphic(vexnode* G,int prnum,int actnum) /创建图 int begin,end,duttem; edgenode *p; for(int i=0;iprnum;i+) Gi.projectname=i; Gi.id=0; Gi.link=NULL; printf(某项目的开始到结束在图中的结点输入n); printf(如:3,4,9 回车表示第三节点到第四结点之间的活动用了9个单位时间n); for(int
10、k=0;kadjvex=end-1; p-dut=duttem; Gend-1.id+; p-next=Gbegin-1.link ; Gbegin-1.link=p; int SearchMapPath(vexnode* G,int prnum,int actnum,int& totaltime) /寻找关键活动 int i,j,k,m=0; int front=-1,rear=-1; int*topologystack=(int*)malloc(prnum*sizeof(int);/用来保存拓扑排列 int*vl=(int*)malloc(prnum*sizeof(int);/用来表示在不
11、推迟整个工程的前提下,VJ允许最迟发生的时间 int*ve=(int*)malloc(prnum*sizeof(int);/用来表示Vj最早发生时间 int*l=(int*)malloc(actnum*sizeof(int);/用来表示活动Ai最晚发生时间 int*e=(int*)malloc(actnum*sizeof(int);/表示活动最早发生时间edgenode *p; totaltime=0; for(i=0;iprnum;i+) vei=0; for(i=0;iadjvex ; Gk.id-; if(vej+p-dutvek) vek=vej+p-dut ; if(Gk.id=0) topologystack+rear=k; p=p-next ; if(mprnum) printf(n本程序所建立的图有回路不可计算出关键路径n); printf(将退出本程序n); return 0; totaltime=veprnum-1; fo