1、數(shù)據(jù)結(jié)構(gòu)實(shí)驗(yàn)報(bào)告-6 -、目的與要求1）掌握AOE網(wǎng)的鄰接表存儲(chǔ)結(jié)構(gòu)表示及創(chuàng)建算法的c語言實(shí)現(xiàn)；2）理解AOE網(wǎng)的拓?fù)渑判蛩惴ǎㄋ惴?.12）的實(shí)現(xiàn)原理及應(yīng)用；3）掌握AOE網(wǎng)關(guān)鍵路徑的計(jì)算算法（算法 7.13 , 7.14）及C語言實(shí)現(xiàn)與應(yīng)用；4）按照實(shí)驗(yàn)題目要求獨(dú)立正確地完成實(shí)驗(yàn)內(nèi)容（提交程序清單及相關(guān)實(shí)驗(yàn)數(shù)據(jù)與運(yùn)行結(jié)果）；5）認(rèn)真書寫實(shí)驗(yàn)報(bào)告，并按時(shí)提交。二、實(shí)驗(yàn)內(nèi)容題目： 圖的應(yīng)用實(shí)驗(yàn)一一計(jì)算 AOER的關(guān)鍵路徑1所示內(nèi)容：按照?qǐng)D的“鄰接表”存儲(chǔ)結(jié)構(gòu)表示AOER,實(shí)現(xiàn)求其關(guān)鍵路徑的算法，并驗(yàn)證如下圖AOE網(wǎng)的關(guān)鍵路徑。三、實(shí)驗(yàn)步驟與源程序# 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)/依次輸入頂點(diǎn)偶對(duì)，建立無向圖鄰接表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;/初始化每個(gè)鏈表為空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);/生成一個(gè)節(jié)點(diǎn)p->adjvex=j;/ 為節(jié)點(diǎn)j的序號(hào)附值為jp->next=pni.firstarc;/將該p節(jié)點(diǎn)作為第i個(gè)鏈表的第一個(gè)節(jié)點(diǎn)插入pni之后 pni.firstarc=p;/ 將接點(diǎn)j作為第一個(gè)接點(diǎn)插入連表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 個(gè)元素不用degi=0;/對(duì)數(shù)組進(jìn)行初始化，全部置0pedgenode pk;for(i=1;i<=n;i+)/對(duì)鄰接表進(jìn)行遍歷pk=pni.

6、firstarc;for(;pk;pk=pk->next) degpk->adjvex+;/ 數(shù)組相應(yīng)元素自增存放各點(diǎn)發(fā)生的最早時(shí)刻（全局變量）存放拓?fù)湫蛄懈黜旤c(diǎn)的棧（全局變量）int vemax_vertex_num;/ int stmax_vertex_num;/ int top2;/( 全局變量)void topologicalorder(pvnode pn,int n,int *tt)int indegreemax_vertex_num;/該數(shù)組存放各頂點(diǎn)的入度int ssmax_vertex_num;/ 設(shè)計(jì)棧ss,用以存放入度為0的頂點(diǎn)的信息 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)/ 若頂點(diǎn)i入度為0,則進(jìn)棧ss+top1=i;int count=0;/對(duì)輸出頂點(diǎn)計(jì)數(shù)cout<<"The topological order of the graph is:n"while(top1)/ 若ss非空，

8、進(jìn)入循環(huán)j=sstop1-;/i 出棧cout<<j<<" "/ 輸出i頂點(diǎn)序號(hào)tt+top2=j;/將 i 進(jìn)入 tt 棧count+;/ 計(jì)數(shù)for(pedgenode p=pnj.firstarc ;p;p=p->next )int k=p->adjvex ;indegreek-;/對(duì)每一個(gè)以i為弧尾的頂點(diǎn)，將他們的入度減1if(!indegreek)ss+top1=k;/如果減為0,則入棧。因?yàn)槿羧攵葹閤,必然要自減x次才能如 棧，所以可以避免重復(fù)進(jìn)棧if(vej+p->weight)>vek)vek=vej+p-&g

9、t;weight;/顯然此時(shí)j是k的前驅(qū)，且vej是j發(fā)生的最早時(shí)間，若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;/存放各點(diǎn)發(fā)生的最遲時(shí)刻for(int i=1;i<=n;i+)vli=ven;/ 用頂點(diǎn)n的最早時(shí)間初始化各頂點(diǎn)的最遲時(shí)間*/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,說明是關(guān)鍵活動(dòng)cout

12、<<"The"<<f+<<"Key activities are:"<<j<<"-"<<k<<endl;/打印關(guān)鍵活動(dòng)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;四、測試數(shù)據(jù)與實(shí)驗(yàn)結(jié)果C VJirido q l 邑產(chǎn) 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五、結(jié)果分析與實(shí)驗(yàn)體會(huì)本次實(shí)驗(yàn)基本掌握了 AOE網(wǎng)的系列概念及用法，也基本完成代碼的調(diào)試與運(yùn)行，具體實(shí)驗(yàn)步驟