数据结构程序设计实验～AOE图的关键路径

数据结构课程设计报告专业网络工程班级姓名学号指导老师评分计算AOE网的关键路径AOE网即边表示活动的网络。通常，可用AOE网来估算工程计划的完成时间。如下所示的AOE网包括11项活动，9个事件，每个事件都有所需的完成时间。我们现在要解决的是：（1）完成整项工程至少需要多少时间（最短时间）；（2）哪些活动是影响工程进度的关键（关键活动）。用e(i)表示活动最早开始时间，l(i)表示活动的最迟开始时间，则l(i)-e(i)为完成该活动的时间余量。对于本例列表如下：活动a1a2a3a4a5a6a7a8a9a10a11e(i)0006457771614l(i)02366877101614l(i)-e(i)02302300300下图就是上述AOE网的关键路径：请编程完成下列工作：1、输入：（1）顶点的信息和入度；（2）AOE网的边（始点、终点和权值）。2、输出：（1）AOE网的邻接表（按“顶点入度：—顶点权值”的格式输出）如a0：--45--34--26（2）输出关键活动每行所显示的分别为开始事件、结束事件、最早开始时间、最迟开始时间和完成活动的时间余量：当l(i)-e(i)=0时，在该行注明为关键活动。如：ab000关键活动源程序#includestdio.h#includestdlib.h#includeiomanip.h#includeprocess.h//#definePROJECTNUMBER9//10//#definePLANNUMBER11//13typedefstructnode{intadjvex;intdut;structnode*next;}edgenode;typedefstruct{intprojectname;intid;edgenode*link;}vexnode;//vexnodeGraphicmap[PROJECTNUMBER];voidCreateGraphic(vexnode*Graphicmap,intprojectnumber,intactivenumber){intbegin,end,duttem;edgenode*p;for(inti=0;iprojectnumber;i++){Graphicmap[i].projectname=i;Graphicmap[i].id=0;Graphicmap[i].link=NULL;}printf(某项目的开始到结束在图中的节点输入vi,vj,dut\n);printf(如：3,4,9回车表示第三节点到第四节点之间的活动用了9个单位时间\n);for(intk=0;kactivenumber;k++){scanf(%d,%d,%d,&begin,&end,&duttem);p=(edgenode*)malloc(sizeof(edgenode));p-adjvex=end-1;p-dut=duttem;Graphicmap[end-1].id++;p-next=Graphicmap[begin-1].link;Graphicmap[begin-1].link=p;}}intSearchMapPath(vexnode*Graphicmap,intprojectnumber,intactivenumber,int&totaltime){inti,j,k,m=0;intfront=-1,rear=-1;int*topologystack=(int*)malloc(projectnumber*sizeof(int));//用来保存拓扑排列int*vl=(int*)malloc(projectnumber*sizeof(int));//用来表示在不推迟整个工程的前提下，VJ允许最迟发生的时间int*ve=(int*)malloc(projectnumber*sizeof(int));//用来表示Vj最早发生时间int*l=(int*)malloc(activenumber*sizeof(int));//用来表示活动Ai最迟完成开始时间int*e=(int*)malloc(activenumber*sizeof(int));//表示活动最早开始时间edgenode*p;totaltime=0;for(i=0;iprojectnumber;i++)ve[i]=0;for(i=0;iprojectnumber;i++){if(Graphicmap[i].id==0){topologystack[++rear]=i;m++;}}while(front!=rear){front++;j=topologystack[front];m++;p=Graphicmap[j].link;while(p){k=p-adjvex;Graphicmap[k].id--;if(ve[j]+p-dutve[k])ve[k]=ve[j]+p-dut;if(Graphicmap[k].id==0)topologystack[++rear]=k;p=p-next;}}if(mprojectnumber){printf(\n本程序所建立的图有回路不可计算出关键路径\n);printf(将退出本程序\n);return0;}totaltime=ve[projectnumber-1];for(i=0;iprojectnumber;i++)vl[i]=totaltime;for(i=projectnumber-2;i=0;i--){j=topologystack[i];p=Graphicmap[j].link;while(p){k=p-adjvex;if((vl[k]-p-dut)vl[j])vl[j]=vl[k]-p-dut;p=p-next;}}i=0;printf(|起点|终点|最早开始时间|最迟完成时间|差值|备注|\n);for(j=0;jprojectnumber;j++){p=Graphicmap[j].link;while(p){k=p-adjvex;e[++i]=ve[j];l[i]=vl[k]-p-dut;printf(|%4d|%4d|%4d|%4d|%4d|,Graphicmap[j].projectname+1,Graphicmap[k].projectname+1,e[i],l[i],l[i]-e[i]);if(l[i]==e[i])printf(关键活动|);printf(\n);p=p-next;}}return1;}voidseekkeyroot(){intprojectnumber,activenumber,totaltime=0;system(cls);printf(请输入这个工程的化成图形的节点数:);scanf(%d,&projectnumber);printf(请输入这个工程的活动个数:);scanf(%d,&activenumber);vexnode*Graphicmap=(vexnode*)malloc(projectnumber*sizeof(vexnode));CreateGraphic(Graphicmap,projectnumber,activenumber);SearchMapPath(Graphicmap,projectnumber,activenumber,totaltime);printf(整个工程所用的最短时间为：%d个单位时间\n,totaltime);system(pause);}intmain(){charch;for(;;){do{system(cls);printf(|欢迎进入求关键路径算法程序|);for(inti=0;i80;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){case'S':seekkeyroot();break;case'E':return1;}}}