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網的系列概念及用法，也基本完成代碼的調試與運行，具體實驗步驟