数据结构_关键路径实验报告

一、实验目的1、巩固和加深对数据结构课程基本知识的理解，综合数据结构课程里学的理论知识，完成对关键路径程序的设计。2、理解和掌握图的各种基本数据结构的定义、存储结构和相应的算法，并能够用c语言实现。3、理解AOE网和拓扑排序、求关键路径的算法。二、实验内容对于给定的一个工程施工图，该图以边为单位从键盘输入，编写能够找出该图的关键路径的程序。三、实验环境1、硬件配置：Pentium（R）Dual-Core9CUPE6500@2.93GHz，1.96的内存2、软件环境：MicrosoftWindowsXPProfessionalServicePack3，MicrosoftVisualC++6.0四、需求分析1、输入的形式和输入值的范围：根据题目要求与提示输入所建图的顶点个数和边的个数，用空格间隔，并且所输入的顶点和边的数目不超过定义好的VEX_NUM和ARC_NUM，然后输入顶点的信息和入度以空格为间隔，最后输入每2个顶点以及边的权值。2、输出的形式：输出AOE网的关键路径。3、程序所能达到的功能：对于给定的一个工程施工图，该图以边为单位从键盘输入，该程序能够输出该AOE网的关键路径。4、测试数据：工程施工图如下：输入顶点的个数和边的个数:911输出的关键路径为：1-2-5-7-9和1-2-5-8-9五、概要设计为了实现上述操作，抽象数据图的定义如下：structarcnode//声明边表中结点结构{intadjvex;intdut;//边上的权值structarcnode*nextarc;};structnode//声明头结点结构{intdata;intid;//定点入度structarcnode*firstarc;};1、基本操作：（1）voidcreate_ALgraph(ALgraphg,inte,intn)建立AOE网的邻接表，e为弧的数目，n为顶点数（2）voidoupe_ALgraph(ALgraphg,intn)输出AOE网的邻接表（3）intCriticalpath(ALgraphg,intn)求AOE网的各个关键活动2、本程序包含两个模块：（1）主程序模块；（2）建立AOE网的邻接表、输出AOE网的邻接表、求AOE网的各个关键活动；（3）模块调用图：主程序模块建立AOE网的邻接表输出AOE网的邻接表求AOE网的各个关键活动3、流程图开始定义变量Algraphg;inte,n,tag请输入顶点的个数和边的个数，用空格间隔:scanf(%d%d,&n,&e)调用create_ALgraph(g,e,n)函数提示输出邻接表信息:调用oupe_ALgraph(g,n)函数提示输出AOE网的关键路径:提示printf(弧:权值\n);调用Criticalpath(g,n)函数并赋值给tag！tagprintf(AOE网有回路\n);结束YN六、详细设计1、存储类型，元素类型，结点类型：structarcnode//声明边表中结点结构{intadjvex;intdut;//边上的权值structarcnode*nextarc;};structnode//声明头结点结构{intdata;intid;//定点入度structarcnode*firstarc;};元素类型为整形和指针型。2、每个模块的分析：（1）主程序模块：main(){ALgraphg;inte,n;inttag;printf(\n请输入顶点的个数和边的个数，用空格间隔:);scanf(%d%d,&n,&e);create_ALgraph(g,e,n);//建立邻接表printf(\n输出邻接表信息:\n);oupe_ALgraph(g,n);//建立输出邻接表printf(\n输出AOE网的关键路径:\n);printf(弧:权值\n);tag=Criticalpath(g,n);//找关键活动if(!tag)printf(AOE网有回路\n);}（2）建立AOE网的邻接表函数模块voidcreate_ALgraph(ALgraphg,inte,intn){//建立AOE网的邻接表，e为弧的数目，n为顶点数structarcnode*p;inti,j,k,w;printf(请输入顶点的信息和入度，用空格间隔:);for(i=1;i=n;i++)//结点下标从1开始{scanf(%d%d,&g[i].data,&g[i].id);//输入顶点信息和入度g[i].firstarc=NULL;}for(k=1;k=e;k++)//建立边表{printf(请输入边的两个顶点以及边上的权值，用空格间隔:);scanf(%d%d%d,&i,&j,&w);//输入有向边的两个顶点p=(structarcnode*)malloc(sizeof(structarcnode));p-adjvex=j;p-dut=w;p-nextarc=g[i].firstarc;//插入下标为i的边表的第一个结点的位置g[i].firstarc=p;}}输出AOE网的邻接表函数模块voidoupe_ALgraph(ALgraphg,intn)//输出AOE网的邻接表{inti;structarcnode*p;for(i=1;in;i++){p=g[i].firstarc;printf(%d,%d-,g[i].data,g[i].id);while(p!=NULL){printf(%3d%3d,p-adjvex,p-dut);p=p-nextarc;//找下一个邻接点}printf(\n);}}求AOE网的各个关键活动函数模块intCriticalpath(ALgraphg,intn)//求AOE网的各个关键活动{inti,j,k,count;inttpord[VEX_NUM+1];//顺序队列intve[VEX_NUM+1],le[VEX_NUM+1];inte[ARC_NUM+1],l[ARC_NUM+1];intfront=0,rear=0;//顺序队列的首尾指针初值为0structarcnode*p;for(i=1;i=n;i++)//各事件最早发生事件初值为0ve[i]=0;for(i=1;i=n;i++)if(g[i].id==0)//入度为0入队列tpord[++rear]=i;count=0;while(front!=rear){front++;j=tpord[front];count++;p=g[j].firstarc;while(p!=NULL){k=p-adjvex;g[k].id--;if(ve[j]+p-dutve[k])ve[k]=ve[j]+p-dut;if(g[k].id==0)tpord[++rear]=k;p=p-nextarc;}}if(countn)//该AOE网有回路return0;for(i=1;i=n;i++)//各事件的最迟发生事件赋初值le[i]=ve[n];for(i=n-1;i=1;i--)//按拓扑序列的逆序取顶点{j=tpord[i];p=g[j].firstarc;while(p!=NULL){k=p-adjvex;if(le[k]-p-dutle[j])le[j]=le[k]-p-dut;p=p-nextarc;}}i=0;for(j=1;j=n;j++){p=g[j].firstarc;while(p!=NULL)//计算各边Vj-1,Vk所代表的a(i+1)的e[i]和l[i]{k=p-adjvex;e[i]=ve[j];l[i]=le[k]-p-dut;if(l[i]==e[i])//输出关键活动printf(v%d,v%d:%d\n,g[j].data,g[k].data,p-dut);p=p-nextarc;i++;}}return1;}3）函数调用关系图main()create_ALgraph(ALgraphg,inte,intn)oupe_ALgraph(ALgraphg,intn)Criticalpath(ALgraphg,intn)3、完整的程序：#includestdio.h#includestdlib.h#defineVEX_NUM10//定义最大顶点数#defineARC_NUM20//定义最多边数typedefintvertype;structarcnode//声明边表中结点结构{intadjvex;intdut;//边上的权值structarcnode*nextarc;};structnode//声明头结点结构{intdata;intid;//定点入度structarcnode*firstarc;};typedefstructnodeALgraph[VEX_NUM+1];voidcreate_ALgraph(ALgraphg,inte,intn){//建立AOE网的邻接表，e为弧的数目，n为顶点数structarcnode*p;inti,j,k,w;printf(请输入顶点的信息和入度，用空格间隔:);for(i=1;i=n;i++)//结点下标从1开始{scanf(%d%d,&g[i].data,&g[i].id);//输入顶点信息和入度g[i].firstarc=NULL;}for(k=1;k=e;k++)//建立边表{printf(请输入边的两个顶点以及边上的权值，用空格间隔:);scanf(%d%d%d,&i,&j,&w);//输入有向边的两个顶点p=(structarcnode*)malloc(sizeof(structarcnode));p-adjvex=j;p-dut=w;p-nextarc=g[i].firstarc;//插入下标为i的边表的第一个结点的位置g[i].firstarc=p;}}voidoupe_ALgraph(ALgraphg,intn)//输出AOE网的邻接表{inti;structarcnode*p;for(i=1;in;i++){p=g[i].firstarc;printf(%d,%d-,g[i].data,g[i].id);while(p!=NULL){printf(%3d%3d,p-adjvex,p-dut);p=p-nextarc;//找下一个邻接点}printf(\n);}}intCriticalpath(ALgraphg,intn)//求AOE网的各个关键活动{inti,j,k,count;inttpord[VEX_NUM+1];//顺序队列intve[VEX_NUM+1],le[VEX_NUM+1];inte[ARC_NUM+1],l[ARC_NUM+1];intfront=0,rear=0;//顺序队列的首尾指针初值为0structarcnode*p;for(i=1;i=n;i++)//各事件最早发生事件初值为0ve[i]=0;for(i=1;i=n;i++)if(g[i].id==0)//入度为0入队列tpord[++rear]=i;count=0;while(front!=rear){front++;j=tpord[front];count++;p=g[j].firstarc;while(p!=NULL){k=p-adjvex;g[k].id--;if(ve[j]+p-dutve[k])ve[k]=ve[j]+p-dut;if(g[k].id==0)tpord[++rear]=k;p=p-nextarc;}}if(countn)//该AOE网有回路return0;for(i=1;i=n;i++)//各事件的最迟发生事件赋初值le[i]=ve[n];for(i=n-1;i=1;i--)//按拓扑序列的逆序取顶点{j=tpord[i];p=g[j].firstarc;while(p!=NULL){k=p-adjvex;if(le[k]-p-dutle[j])le[j]=le[k]-p-dut;p=p-nextarc;}}i