《数据结构_关键路径实验报告.》由会员分享,可在线阅读,更多相关《数据结构_关键路径实验报告.(17页珍藏版)》请在金锄头文库上搜索。
1、一正文红色部分表示示例内容,供参考、实验目的1、巩固和加深对数据结构课程基本知识的理解,综合数据结构课程里学的理论知识,完成对关键路径程序的设计。2、理解和掌握图的各种基本数据结构的定义、存储结构和相应的算法,并能够用c语言实现。3、理解AOE网和拓扑排序、求关键路径的算法。二、实验内容对于给定的一个工程施工图,该图以边为单位从键盘输入,编写能够找出该图的关键路径的程序。三、实验环境1、硬件配置:Pentium(R) Dual-Core9 CUP E6500 2.93GHz,1.96的内存2、软件环境:Microsoft Windows XP Professional Service Pack
2、 3,Microsoft Visual C+ 6.0四、需求分析1、输入的形式和输入值的范围:根据题目要求与提示输入所建图的顶点个数和边的个数,用空格间隔,并且所输入的顶点和边的数目不超过定义好的VEX_NUM和ARC_NUM,然后输入顶点的信息和入度以空格为间隔,最后输入每2个顶点以及边的权值。2、输出的形式:输出AOE网的关键路径。3、程序所能达到的功能:对于给定的一个工程施工图,该图以边为单位从键盘输入,该程序能够输出该AOE网的关键路径。 4、测试数据:工程施工图如下:输入顶点的个数和边的个数:9 11输出的关键路径为:1-2-5-7-9和1-2-5-8-9五、概要设计为了实现上述操作
3、,抽象数据图的定义如下:struct arcnode/声明边表中结点结构 int adjvex; int dut; /边上的权值 struct arcnode *nextarc;struct node /声明头结点结构int data;int id; /定点入度 struct arcnode *firstarc; 1、基本操作:(1)void create_ALgraph(ALgraph g,int e,int n)建立AOE网的邻接表,e为弧的数目,n为顶点数(2)void oupe_ALgraph(ALgraph g,int n) 输出AOE网的邻接表(3)int Criticalpath
4、(ALgraph g,int n) 求AOE网的各个关键活动2、本程序包含两个模块:(1)主程序模块;(2)建立AOE网的邻接表、输出AOE网的邻接表、求AOE网的各个关键活动;(3)模块调用图:主程序模块建立AOE网的邻接表输出AOE网的邻接表求AOE网的各个关键活动3、流程图重点内容六、详细设计1、存储类型,元素类型,结点类型:struct arcnode/声明边表中结点结构 int adjvex; int dut; /边上的权值 struct arcnode *nextarc;struct node /声明头结点结构int data;int id; /定点入度 struct arcnod
5、e *firstarc; 元素类型为整形和指针型。2、每个模块的分析:(1)主程序模块:main() ALgraph g; int e,n; int tag; 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网有回路
6、n);(2)建立AOE网的邻接表函数模块void create_ALgraph(ALgraph g,int e,int n) /建立AOE网的邻接表,e为弧的数目,n为顶点数 struct arcnode *p; int i,j,k,w; printf(请输入顶点的信息和入度,用空格间隔:); for(i=1;i=n;i+) /结点下标从1开始 scanf(%d%d,&gi.data,&gi.id); /输入顶点信息和入度 gi.firstarc=NULL; for(k=1;kadjvex=j; p-dut=w; p-nextarc=gi.firstarc; /插入下标为i的边表的第一个结点的
7、位置 gi.firstarc=p; 输出AOE网的邻接表函数模块void oupe_ALgraph(ALgraph g,int n) /输出AOE网的邻接表int i;struct arcnode *p;for(i=1;i,gi.data,gi.id);while(p!=NULL)printf(%3d%3d,p-adjvex,p-dut);p=p-nextarc; /找下一个邻接点printf(n);求AOE网的各个关键活动函数模块int Criticalpath(ALgraph g,int n)/求AOE网的各个关键活动 int i,j,k,count; int tpordVEX_NUM+1
8、; /顺序队列 int veVEX_NUM+1,leVEX_NUM+1; int eARC_NUM+1,lARC_NUM+1; int front=0,rear=0;/顺序队列的首尾指针初值为0 struct arcnode *p; for(i=1;i=n;i+) /各事件最早发生事件初值为0 vei=0; for(i=1;iadjvex; gk.id-; if(vej+p-dutvek) vek=vej+p-dut; if(gk.id=0) tpord+rear=k; p=p-nextarc; if(countn) /该AOE网有回路 return 0; for(i=1;i=1;i-) /按
9、拓扑序列的逆序取顶点 j=tpordi; p=gj.firstarc; while(p!=NULL) k=p-adjvex; if(lek-p-dutdut; p=p-nextarc; i=0; for(j=1;j=n;j+) p=gj.firstarc; while(p!=NULL) /计算各边所代表的a(i+1)的ei和li k=p-adjvex; ei=vej; li=lek-p-dut; if(li=ei) /输出关键活动 printf(:%dn,gj.data,gk.data,p-dut); p=p-nextarc; i+; return 1; 3)函数调用关系图main()crea
10、te_ALgraph(ALgraph g,int e,int n)oupe_ALgraph(ALgraph g,int n)Criticalpath(ALgraph g,int n)3、完整的程序:#includestdio.h#includestdlib.h#define VEX_NUM 10/定义最大顶点数#define ARC_NUM 20/定义最多边数typedef int vertype;struct arcnode/声明边表中结点结构 int adjvex; int dut; /边上的权值 struct arcnode *nextarc;struct node /声明头结点结构in
11、t data;int id; /定点入度 struct arcnode *firstarc;typedef struct node ALgraphVEX_NUM+1;void create_ALgraph(ALgraph g,int e,int n) /建立AOE网的邻接表,e为弧的数目,n为顶点数 struct arcnode *p; int i,j,k,w; printf(请输入顶点的信息和入度,用空格间隔:); for(i=1;i=n;i+) /结点下标从1开始 scanf(%d%d,&gi.data,&gi.id); /输入顶点信息和入度 gi.firstarc=NULL; for(k=1;kadjvex=j;