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

1、数据结构课程设计报告专业 网络工程班级 姓名 学号 指导老师 评分计算AOE网的关键路径AOE网即边表示活动的网络。通常，可用AOE网来估算工程计划的完成时间。如下所示的AOE网包括11项活动，9个事件，每个事件都有所需的完成时间。我们现在要解决的是：（1）完成整项工程至少需要多少时间（最短时间）；（2）哪些活动是影响工程进度的关键（关键活动）。用e(i)表示活动最早开始时间，l(i)表示活动的最迟开始时间，则l(i)-e(i)为完成该活动的时间余量。对于本例列表如下：活动a1a2a3a4a5a6a7a8a9a10a11e(i)0006457771614l(i)02366877101614l(

2、i)-e(i)02302300300下图就是上述AOE网的关键路径：请编程完成下列工作：1、 输入：（1） 顶点的信息和入度；（2） AOE网的边（始点、终点和权值）。2、 输出：（1） AOE网的邻接表（按“顶点 入度：顶点 权值”的格式输出）如a 0：-4 5-3 4-2 6（2）输出关键活动每行所显示的分别为开始事件、结束事件、最早开始时间、最迟开始时间和完成活动的时间余量：当l(i)-e(i)=0时，在该行注明为关键活动。如：a b 0 0 0 关键活动源程序#include#include#include#include /#define PROJECTNUMBER 9/10/#de

3、fine PLANNUMBER 11/13typedef struct node int adjvex; int dut; struct node *next;edgenode;typedef struct int projectname; int id; edgenode *link;vexnode;/vexnode GraphicmapPROJECTNUMBER;void CreateGraphic(vexnode* Graphicmap,int projectnumber,int activenumber) int begin,end,duttem; edgenode *p; for(i

4、nt i=0;iprojectnumber;i+) Gjectname=i; Graphicmapi.id =0; Graphicmapi.link =NULL; printf(某项目的开始到结束在图中的节点输入n); printf(如：3,4,9 回车表示第三节点到第四节点之间的活动用了9个单位时间n); for(int k=0;kadjvex =end-1; p-dut =duttem; Graphicmapend-1.id +; p-next =Graphicmapbegin-1.link ; Graphicmapbegin-1.link =p; int Se

5、archMapPath(vexnode* Graphicmap,int projectnumber,int activenumber,int& totaltime) int i,j,k,m=0; int front=-1,rear=-1; int* topologystack=(int*)malloc(projectnumber*sizeof(int);/用来保存拓扑排列 int* vl=(int*)malloc(projectnumber*sizeof(int);/用来表示在不推迟整个工程的前提下，VJ允许最迟发生的时间 int* ve=(int*)malloc(projectnumber*

6、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+) vei=0; for(i=0;iadjvex ; Graphicmapk.id -; if(vej+p-dut vek) vek=vej+p-dut ; if(Graphicmapk.id =0) to

7、pologystack+rear=k; p=p-next ; if(mprojectnumber) printf(n本程序所建立的图有回路不可计算出关键路径n); printf(将退出本程序n); return 0; totaltime=veprojectnumber-1; for(i=0;i=0;i-) j=topologystacki; p=Graphicmapj.link ; while(p) k=p-adjvex ; if(vlk-p-dut )dut ; p=p-next ; i=0; printf(| 起点 | 终点 | 最早开始时间 | 最迟完成时间 | 差值 | 备注 |n);

8、 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 1;void seekkeyroot() int projectnumber,activenumber,totaltime=0; system(cls); printf(请输入这个工程的化成

9、图形的节点数:); 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);int main() char ch; for(;) do system(cls); printf(| 欢迎进入求关键路径算法程序 |); for(int i=0;i80;i+)printf(*); printf(%s,(S)tart开始输入工程的节点数据并求出关键路径n);