数据结构求关键路径实习报告.doc

河 南 工 程 学 院实 习 报 告系（部） 专 业 班 级 姓 名 学 号 2011 年 7月 1日实 习 （训） 报 告 评 语等 级： 评阅人： 职称： 年月日河南工程学院实习（训）报告实习内容： 关键路径问题 实习时间：自 6 月 27 日 至 7 月 1 日 共5 天实习地点： 实习单位： 指导教师： 系主任： 目 录一、设计目标1二、课题分析与设计21课题需求分析22存储结构设计23算法设计34程序流程图4三、程序清单5四、测试91测试数据92测试结果及分析9五、总结111收获112不足113算法改进分析11一、设计目标用带权有向图构造的AOE网表示一项工程计划，图的结点表示事件，弧表示活动，权值表示活动持续时间。完成工程的最短时间是从开始点到完成点的最长路径的长度。路径长度最长的路径叫关键路径。关键路径上的所有活动都是关键活动。求关键路径必须在拓扑排序的前提下进行，有环图不能求关键路径；只有缩短关键活动的工期才有可能缩短工期；若一个关键活动不在所有的关键路径上，减少它并不能减少工期；只有在不改变关键路径的前提下，缩短关键活动才能缩短整个工期。本次实训设计程序，任意给出表示工程计划的顶点及带权弧的有向图信息，即可判断整项工程计划是否合理，求出工程计划中的关键路径及关键活动。完成整项工程至少需要的时间。二、课题分析与设计1课题需求分析1.1问题描述：（1）选取建图的一种算法建立图，有邻接矩阵，邻接表，十字链表，邻接多重表等多种方法，要选取一种适当的方法建立图，才能提高算法效率，降低时间复杂度和空间复杂度。（2）两个相邻顶点与它们之间的边表示活动，边上的数字表示活动延续的时间。对于给出的事件AOE网络，要求求出从起点到终点的所有路径，经分析、比较后找出长读最大的路径，从而得出求关键路径的算法，并给出计算机上机实现的源程序。完成不同路径的活动所需的时间虽然不同，但只有各条路径上所有活动都完成了，这个工程才算完成。具体要解决的问题有如下四个：1） 将项目中的各项活动视为有一个时间属性的结点，从项目起点到终点进行排列； 2） 用有方向的线段标出各结点的紧前活动和紧后活动的关系，使之成为一个有方向的网络图； 3） 用正推法和逆推法计算出各个活动的最早开始时间，最晚开始时间，最早完工时间和最迟完工时间，并计算出各个活动的时差； 4） 找出所有时差为零的活动所组成的路线，即为关键路径； 1.2 基本要求（1）选取建图的一种算法建立图；选取邻接表的算法来建立图，是一种顺序+ 链式存储结构。用顺序表存放顶点，为每个顶点建立一个单链表，单链表中的结点表示依附于该顶点的边或以该顶点为尾的弧。（2）两个相邻顶点与它们之间的边表示活动，边上的数字表示活动延续的时间。参照该工程所化的AOE-网，求出从起点到终点的所有路径，然后通过拓扑排序和逆拓扑排序求出最早与最晚发生时间，找出长度最大的路径，从而求得关键路径。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的最长路径长度叫做事件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)=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),求 按逆拓扑有序求其余各顶点的最迟发生时间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; /顶点信息 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+) Gjectname=i; Gi.id=0; Gi.link=NULL; printf(某项目的开始到结束在图中的结点输入n); printf(如：3,4,9 回车表示第三节点到第四结点之间的活动用了9个单位时间n); for(int 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);/用来表示在不推迟整个工程的前提下，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; for(i=0;i=0;i-) j=topologystacki; p=Gj.link ; while(p) k=p-adjvex ; if(vlk-p-dut)dut ; p=p-next ; i=0; printf(| 起点 | 终点 | 最早发生时间 | 最晚发生时间 | 差值 | 备注 |n); for(j=0;jadjvex ; e+i=vej; li=vlk-p-dut; printf(| %4d | %4d | %4d | %4d | %4d |,Gjectname +1,Gjectname +1,ei,li,li-ei); if(li=ei) printf( 关键活动 |); printf(n); p=p-next ; return 0; void mintime () /计算整个工程所用的最短时间 int pn,an,totaltime=0; system(cls); printf(请输入这个工程的化成图形的结点数:); scanf(%d,&pn); printf(请输入这个工程的活动数:); scanf(%d,&an); vexnode* Graphicmap=(vexnode*)malloc(pn*sizeof(vexnode); CreateGraphic(Graphicmap,pn,an); SearchMapPath(Graphicmap,pn,an,totaltime); printf(整个工程所用的最短时间为：%d个单位时间n,totaltime); system(pause); int main() char ch; for(;) do system(cls); printf(| 欢迎进入求关键路径算法程序 |); for(int i=0;i25;i+)printf( ); printf(%s,(S)tart开始输入工程的结点数据并求出关键路径n); printf(%s,(E)xit退出n); printf(%s,请输入选择:); scanf(%c,&ch); ch=toupper(ch); while(ch!=S&ch!=E); switch(ch) caseS: mintime (); break; caseE: return 0; 四、测试1测试数据表示工程计划的带权有向图测试数据如下：顶点集为V=v1，v2，v3，v4，v5，v6；弧集为S=, ；八条弧依次对应的权值为3，2，2，3，4，3，2，1。2测试结果及分析结果表示此项工程的关键路径为：V1V3v4V6242关键活动有,。五、总结1收获通过这次实训，使我学到了很多。由于对标准C语言缺乏深入的学习，致使我在编程中遇到了很多困难，但在攻克困难的过程中提高了自己的自学能力，分析问题及解决问题的能力、熟练运用理论知识的能力。同时，让我更深入的掌握了有关AOE网表示工程计划及关键路径问题等方面的知识，巩固了所学内容。然而，尽管这次的实习是独立的个人工作，但在完成课程设计遇到困难时，也得到了很多老师的指导和同学的帮助。这次实训，促进了我与同学们之间的友谊，也让我明白了合作的重要性，提高了自己的合作能力。 在实训过程中收获了很多的丰富的经验知识，更加深了我对一些算法和新知识的理解与应用，让我受益匪浅。2不足这次实训也让我认识到了自己在很多方面的