AOE网数据结构

1、数据结构实验报告-6 -、目的与要求1）掌握AOE网的邻接表存储结构表示及创建算法的c语言实现；2）理解AOE网的拓扑排序算法（算法7.12）的实现原理及应用；3）掌握AOE网关键路径的计算算法（算法 7.13 , 7.14）及C语言实现与应用；4）按照实验题目要求独立正确地完成实验内容（提交程序清单及相关实验数据与运行结果）；5）认真书写实验报告，并按时提交。二、实验内容题目： 图的应用实验一一计算 AOER的关键路径1所示内容：按照图的“邻接表”存储结构表示AOER,实现求其关键路径的算法，并验证如下图AOE网的关键路径。三、实验步骤与源程序# include <iostream.h

2、> # include <stdlib.h># define max_vertex_num 50# define maxvalue 32760# define NULL 0 typedef struct edgenodeint adjvex;struct edgenode *next;int weight; edgenode,* pedgenode;typedef struct vnodeint data;struct edgenode *firstarc;vnode,adjlistmax_vertex_num,* pvnode;void creatgraphadlist(p

3、vnode &pn,int n)/依次输入顶点偶对，建立无向图邻接表edgenode *p;int i,j,k,wei;i=j=1;pn=(pvnode)malloc(n+1)*sizeof(vnode);for(k=1;k<=n;k+)pnk.firstarc=NULL;/初始化每个链表为空for(int f=1;!(i=0&&j=0);) cout<<"Please input number of-"<<f<<"-vertices of an arc,End with (0,0):"

4、;cin>>i>>j;if(i>0&&i<=n&&j>0&&j<=n)p=(edgenode *)malloc(sizeof(edgenode);/生成一个节点p->adjvex=j;/ 为节点j的序号附值为jp->next=pni.firstarc;/将该p节点作为第i个链表的第一个节点插入pni之后 pni.firstarc=p;/ 将接点j作为第一个接点插入连表i的后面 cout<<"Please enter the weight of the edge:&q

5、uot; cin>>wei;p->weight =wei; f+; else if(i=0&&j=0) ;/什么也不做 else cout<<"Please re-enter .n" /for cout<<"n"void findindegree(pvnode pn,int n,int *deg)for(int i=1;i<=n;i+) 第 0 个元素不用degi=0;/对数组进行初始化，全部置0pedgenode pk;for(i=1;i<=n;i+)/对邻接表进行遍历pk=pni.

6、firstarc;for(;pk;pk=pk->next) degpk->adjvex+;/ 数组相应元素自增存放各点发生的最早时刻（全局变量）存放拓扑序列各顶点的栈（全局变量）int vemax_vertex_num;/ int stmax_vertex_num;/ int top2;/( 全局变量)void topologicalorder(pvnode pn,int n,int *tt)int indegreemax_vertex_num;/该数组存放各顶点的入度int ssmax_vertex_num;/ 设计栈ss,用以存放入度为0的顶点的信息 int *deg;int

7、j;deg=indegree;findindegree(pn,n,deg);for(int i=1;i<=n;i+)/ve0 不用vei=0;/ 初始化int top1;top1=top2=0;/top1 和top2为栈顶指针，分别指向栈ss和tt ,初始值均为0(即栈为空)for(i=1;i<=n;i+)if(!indegreei)/ 若顶点i入度为0,则进栈ss+top1=i;int count=0;/对输出顶点计数cout<<"The topological order of the graph is:n"while(top1)/ 若ss非空，

8、进入循环j=sstop1-;/i 出栈cout<<j<<" "/ 输出i顶点序号tt+top2=j;/将 i 进入 tt 栈count+;/ 计数for(pedgenode p=pnj.firstarc ;p;p=p->next )int k=p->adjvex ;indegreek-;/对每一个以i为弧尾的顶点，将他们的入度减1if(!indegreek)ss+top1=k;/如果减为0,则入栈。因为若入度为x,必然要自减x次才能如 栈，所以可以避免重复进栈if(vej+p->weight)>vek)vek=vej+p-&g

9、t;weight;/显然此时j是k的前驱，且vej是j发生的最早时间，若if(count<n)cout<<"nThere are rings in the graph -error!n"return;cout<<"n"<<endl;cout<<"The earliest time of each vertex :"<<endl;for(i=1;i<=n;i+)cout<<"vertex("<<i<<"

10、;)earliest time is:"<<vei<<endl;cout<<"n"<<endl;void criticalpath(pvnode pn,int n,int *tt)int j,k,dut,ee,el,tag,f=1;pedgenode p;int vlmax_vertex_num;/存放各点发生的最迟时刻for(int i=1;i<=n;i+)vli=ven;/ 用顶点n的最早时间初始化各顶点的最迟时间*/while(top2)j=tttop2-;/ 出栈for(p=pnj.firstarc ;

11、p;p=p->next )k=p->adjvex ;dut=p->weight;if(vlk-dut)<vlj)vlj=vlk-dut;cout<<"After calculation, the key path of the figure is as follows n"for(j=1;j<=n;j+)for(p=pnj.firstarc ;p;p=p->next )k=p->adjvex ;dut=p->weight ;ee=vej;el=vlk-dut;if(ee=el) /ee=el,说明是关键活动cout

12、<<"The"<<f+<<"Key activities are:"<<j<<"-"<<k<<endl;/打印关键活动int main()int n,*tt;pvnode pn;tt=st;cout<<"Please enter the number of vertices of the graph :" cin>>n;cout<<""<<endl;creatgra

13、phadlist(pn,n);topologicalorder(pn,n,tt);criticalpath(pn,n,tt);return 0;四、测试数据与实验结果C VJirido q l 邑产 1lense enter thr number of vertices of the graphease enseedse easeertse erise rsiqp户 nascEC立足 PilRP niisc 巳日 ease 户 flQPUdEU edeinputnumber of 1 vertices of narcXnddth(0.0)；12enierthe ”ioht of the edg

14、e: 6inputruin her nt'?-vrrt i c&s of anarc hFndwith（配 tn：25Enterthe weigh! of the adge;linputnumber of 3-vertices ofeirc, EndML th(0W)：13pnlerthp wp i ght of thp pdgft 4.inpiiltMJmbr of-4-ver 1 ic&s of dnfire pFndtj i 1 li(CM):35enterthe weiqht of the edcie： 1inputnunber of-5 vertices of

15、 wncirc PEndjith(0f0)：51enierthe weight of the d()c:9inpulnumber ol-6-verlices of anarc.Endfuilli(0.OL73enterthe weight of the edge;2i npidrniiihpr of -7-vertics nf nnnrc PFnd5 th(0 0):5Renterthe weight of the adqc:7inputnumber ot-8-vcrlices of anarc.EndtjiUi(0.0);8yenterthe weight of the edge：4i np

16、iitr>imbpr of -9-vert iof anfircpFndwii th(0,0):1&enterthe tveight of the edge；binputnunber ol-10-uert ices of ari arc.tnc1 with(0,0);h6enierthe weight of the edge：2i npiitminber of -11 -yerti res of nr arc,Fnd wi th(nforfi genterthe neioht of the edge;4inpu Inumber ol-12-vertices of drarc.En

17、d withwu)：E1日Pl电3金 i nput nuiKbr of 12 vert i ces； of an orc .End 叫ith (C, 0 h 8 6The 1orological order of the grnph ist 12 3 3 7 4 6 8 9The eflrI iest t i ne tex(1 Jear I iestyertext?)earliest vertex(9earliest verteKUierirl jest uertex(5)earliest uertex(6)earliest wertex(7)earliest ver tex(8)tjrlit

18、s t uertex(9)earliestn>f f?曰二h vertex : tIne is:0 tiite i零:6 tine is;fttine is：5 iiMe is:7 tike is:7ti.Me is: 16 t iae is:14 tine is:18fitter calcjlatian, ThelKeyi activities The2KBy activities TheSKey activities TheKey aciivities The5Key activities Ihn6K叫 nr t i u11 iesthn k(?y path cf th何 fiyiiro is as foilowsare :1 2<*ra;25arQ: 5-ftore: 5 7are: 79enter thd riiiKiher 口f,0rtirRE nf the 口r即卜rirn田9五、结果分析与实验体会本次实验基本掌握了 AOE网的系列概念及用法，也基本完成代码的调试与运行，具体实验步骤