《数据结构求关键路径实习报告》由会员分享，可在线阅读，更多相关《数据结构求关键路径实习报告（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
