数据结构-关键路径实验报告.doc

精选优质文档-倾情为你奉上一正文红色部分表示示例内容，供参考、实验目的1、巩固和加深对数据结构课程基本知识的理解，综合数据结构课程里学的理论知识，完成对关键路径程序的设计。2、理解和掌握图的各种基本数据结构的定义、存储结构和相应的算法，并能够用c语言实现。3、理解AOE网和拓扑排序、求关键路径的算法。二、实验内容对于给定的一个工程施工图，该图以边为单位从键盘输入，编写能够找出该图的关键路径的程序。三、实验环境1、硬件配置：Pentium（R） Dual-Core9 CUP E6500 2.93GHz，1.96的内存2、软件环境：Microsoft Windows XP Professional Service Pack 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五、概要设计为了实现上述操作，抽象数据图的定义如下：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(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 arcnode *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网有回路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;k<=e;k+) /建立边表 printf("请输入边的两个顶点以及边上的权值，用空格间隔:"); scanf("%d%d%d",&i,&j,&w); /输入有向边的两个顶点 p=(struct arcnode *)malloc(sizeof(struct arcnode); p->adjvex=j; p->dut=w; p->nextarc=gi.firstarc; /插入下标为i的边表的第一个结点的位置 gi.firstarc=p; 输出AOE网的邻接表函数模块void oupe_ALgraph(ALgraph g,int n) /输出AOE网的邻接表int i;struct arcnode *p;for(i=1;i<n;i+)p=gi.firstarc;printf("%d,%d->",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; /顺序队列 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;i<=n;i+) if(gi.id=0) /入度为0入队列 tpord+rear=i; count=0; while(front!=rear) front+; j=tpordfront; count+; p=gj.firstarc; while(p!=NULL) k=p->adjvex; gk.id-; if(vej+p->dut>vek) vek=vej+p->dut; if(gk.id=0) tpord+rear=k; p=p->nextarc; if(count<n) /该AOE网有回路 return 0; for(i=1;i<=n;i+) /各事件的最迟发生事件赋初值 lei=ven; for(i=n-1;i>=1;i-) /按拓扑序列的逆序取顶点 j=tpordi; p=gj.firstarc; while(p!=NULL) k=p->adjvex; if(lek-p->dut<lej) lej=lek-p->dut; p=p->nextarc; i=0; for(j=1;j<=n;j+) p=gj.firstarc; while(p!=NULL) /计算各边<Vj-1,Vk>所代表的a(i+1)的ei和li k=p->adjvex; ei=vej; li=lek-p->dut; if(li=ei) /输出关键活动 printf("<v%d,v%d>:%dn",gj.data,gk.data,p->dut); p=p->nextarc; i+; return 1; 3）函数调用关系图main()create_ALgraph(ALgraph g,int e,int n)oupe_ALgraph(ALgraph g,int n)Criticalpath(ALgraph g,int n)3、完整的程序：#include"stdio.h"#include"stdlib.h"#define VEX_NUM 10/定义最大顶点数#define ARC_NUM 20/定义最多边数typedef int vertype;struct arcnode/声明边表中结点结构 int adjvex; int dut; /边上的权值 struct arcnode *nextarc;struct node /声明头结点结构int 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;k<=e;k+) /建立边表 printf("请输入边的两个顶点以及边上的权值，用空格间隔:"); scanf("%d%d%d",&i,&j,&w); /输入有向边的两个顶点 p=(struct arcnode *)malloc(sizeof(struct arcnode); p->adjvex=j; p->dut=w; p->nextarc=gi.firstarc; /插入下标为i的边表的第一个结点的位置 gi.firstarc=p; void oupe_ALgraph(ALgraph g,int n) /输出AOE网的邻接表int i;struct arcnode *p;for(i=1;i<n;i+)p=gi.firstarc;printf("%d,%d->",gi.data,gi.id);while(p!=NULL)printf("%3d%3d",p->adjvex,p->dut);p=p->nextarc; /找下一个邻接点printf("n");int Criticalpath(ALgraph g,int n)/求AOE网的各个关键活动 int i,j,k,count; int tpordVEX_NUM+1; /顺序队列 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;i<=n;i+) if(gi.id=0) /入度为0入队列 tpord+rear=i; count=0; while(front!=rear) front+; j=tpordfront; count+; p=gj.firstarc; while(p!=NULL) k=p->adjvex; gk.id-; if(vej+p->dut>vek) vek=vej+p->dut; if(gk.id=0) tpord+rear=k; p=p->nextarc; if(count<n) /该AOE网有回路 return 0; for(i=1;i<=n;i+) /各事件的最迟发生事件赋初值 lei=ven; for(i=n-1;i>=1;i-) /按拓扑序列的逆序取顶点 j=tpordi; p=gj.firstarc; while(p!=NULL) k=p->adjvex; if(lek-p->dut<lej) lej=lek-p->dut; p=p->nextarc; i=0; for(j=1;j<=n;j+) p=gj.firstarc; while(p!=NULL) /计算各边<Vj-1,Vk>所代表的a(i+1)的ei和li k=p->adjvex; ei=vej; li=lek-p->dut; if(li=ei) /输出关键活动 printf("<v%d,v%d>:%dn",gj.data,gk.data,p->dut); p=p->nextarc; i+; return 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网有回路n");七、程序使用说明及测试结果1、程序使用说明（1）本程序的运行环境为VC6.0。（2）进入演示程序后即显示提示信息： 请输入顶点的个数和边的个数，用空格间隔：（输入后）回车；请输入顶点的信息和入度，用空格间隔（输入后）回车；请输入边的两个顶点以及边上的权值，用空格间隔：（输入后）回车；即得结果；2、测试结果：例如：输入：请输入顶点的个数和边的个数，用空格间隔：9 11输出的关键路径为：1-2-5-7-9和1-2-5-8-93、调试中的错误及解决办法。调试过程中，遇到了许多的问题，如关于图的存储结构使用邻接矩阵还是邻接表，然后是关于拓扑排序的算法的问题，通过查阅相关数据结构算法的书本解决了编程过程中遇到的问题。运行界面先输入9 11后，回车：再输入1 0 2 1 3 1 4 1 5 2 6 1 7 1 8 2 9 2后回车：输入边的两个顶点以及边上的权值，用空格间隔： 回车即得结果：八、实验小结重点内容： 首先通过数据结构老师在课堂上的讲解，对关键路径有了认识和了解，求关键路径的算法也了解和理解了，然后参考相关数据结构算法的书本，将求关键路径的算法运行后，遇到了一些小问题，通过查阅相关资料和向其他同学请教，解决遇到的问题，关于图的路径问题还有最短路径也是求图的路径的一种算法，感觉图的用途挺多的，能够解决实际生活中遇到的很多问题。签 名：日 期：实验成绩：批阅日期：专心-专注-专业