南郵數(shù)據(jù)結(jié)構(gòu)上機實驗三圖的基本運算及飛機換乘次數(shù)最少問題

1、和3瑯唸/毀實驗報告（2015/2016學(xué)年第二學(xué)期）課程名稱數(shù)據(jù)結(jié)構(gòu)A實驗名稱圖的基本運算及飛機換乘次數(shù)最少問題實驗時間2016年5月19日指導(dǎo)單位科學(xué)與技術(shù)系指導(dǎo)教師駱健學(xué)生姓名班級學(xué)號學(xué)生姓名班級學(xué)號學(xué)院（系）管理學(xué)院專業(yè)信息管理與信息系統(tǒng)(b)(b)模版類Graph,MGraph和LGraph實習(xí)題名：圖的基本運算班級姓名學(xué)號日期2016.05.19一、問題描述驗證教材中關(guān)于在鄰接矩陣和鄰接表兩種不同的儲存結(jié)構(gòu)上實現(xiàn)圖的基本運算的算法（見程序9.1程序9.8），在鄰接矩陣存儲結(jié)構(gòu)上實現(xiàn)圖的深度和廣度優(yōu)先遍歷算法，設(shè)計主函數(shù)，測試上述運算。二、概要設(shè)計文件graph.cpp中在該文件中定

2、義圖數(shù)據(jù)結(jié)構(gòu)的抽象模板類Graph。鄰接矩陣類MGraph是從抽象類Graph派生得來，鄰接表類LGraph也是從抽象類Graph派生得來。主函數(shù)的代碼如圖所示。drfBff羽s-drfBff羽s-PA君%qT-riMKFl.h/-liT-2Lffl闕;.?-g：出制*3；：EE/帖|JjlUD諏E幻*EV：廣-巴7.34/：弓口卄：萼科曲氏血矗E：:三、詳細(xì)設(shè)計類和類的層次設(shè)計程序定義了Graph類，以及鄰接矩陣類MGraph和鄰接表類LGraph以及循環(huán)列表類SeqQueue。鄰接矩陣類MGraph繼承了Graph的數(shù)據(jù)成員n和e，重載了Graph的純虛函數(shù)。保護數(shù)據(jù)成員T*a指向動態(tài)生成

3、的二維數(shù)組，用以存儲鄰接矩陣。鄰接表類LGraph也繼承了Graph的數(shù)據(jù)成員n和e及重載了Graph的純虛函數(shù)，邊結(jié)點由類ENode定義，每個結(jié)點有三個域adjVex、w和nextArc。鄰接表的表頭組成為一維數(shù)組，a是指向該數(shù)組的指針。TSeqQueue-intfront,rear;-intmaxSize;-BTNode*q;+SeqQueue(intmSize);+SeqQueue()deleteq;+boolIsEmpty()constreturnfront=rear;+boolIsFull()constreturn(rear+1)%maxSize=front;+boolFront(B

4、TNode*&x)const;+boolEnQueue(BTNode*x);+boolDeQueue();+voidClear()front=rear=0;(a)循環(huán)隊列類TGraph#intn,e;+virtualResultCodeInsert(intu,intv,T&w)=0;+virtualResultCodeRemove(intu,intv)=0;+virtualboolExist(intu,intv)const=0;TTMGraphLGraph#T*a;#TnoEdge;#voidDFS(intv,bool*visited);#voidBFS(intv,bool*visited);

5、#ENode*a;+LGraph(intmSize);+LGraph();+ResultCodeInsert(intu,intv,T&w);+ResultCodeRemove(intu,intv);+boolExist(intu,intv)const;+MGraph(intmSize,constT&noedg);+MGraph();+ResultCodeInsert(intu,intv,T&w);+ResultCodeRemove(intu,intv);+boolExist(intu,intv)const;+voidDFS();+voidBFS();核心算法深度優(yōu)先搜索用棧來實現(xiàn)：1）把根節(jié)點

6、壓入棧中2）每次從棧中彈出一個元素，搜索所有在它下一級的元素，把這些元素壓入棧中。并把這個元素記為它下一級元素的前驅(qū)3）找到所要找的元素時結(jié)束程序4）如果遍歷整個樹還沒有找到，結(jié)束程序廣度優(yōu)先搜索使用隊列來實現(xiàn)：1）把根節(jié)點放到隊列的末尾2）每次從隊列的頭部取出一個元素，查看這個元素所有的下一級元素，把它們放到隊列的末尾。并把這個元素記為它下一級元素的前驅(qū)3）找到所要找的元素時結(jié)束程序4）如果遍歷整個樹還沒有找到，結(jié)束程序DFS()四、程序代碼templatevclassTvoidMGraphvT:DFS()深度遍歷bool*visited=newbooln;for(inti=0;ivn;i+

7、)visitedi=false;for(i=0;in;i+)if(!visitedi)DFS(i,visited);deletevisited;templatevoidMGraph:DFS(intv,bool*visited)visitedv=true;coutvvv;for(inti=0;ivoidMGraphvT:BFS()廣度遍歷bool*visited=newbooln;for(inti=0;ivn;i+)visitedi=false;for(i=0;in;i+)if(!visitedi)BFS(i,visited);deletevisited;templatevoidMGraph:B

8、FS(intv,bool*visited)SeqQueuevintq(n);visitedv=true;coutvvv;q.EnQueue(v);while(!q.IsEmpty()q.Front(v);q.DeQueue();for(inti=0;in;i+)if(avi!=noEdge&avi!=0&!visitedi)visitedi=true;coutvvebugl.ee!輸入邊以及權(quán)值2)214-5輸入邊以及權(quán)值2)214-5&1?243-r5Ri13-cLk-rLTKftttfi“：J:“-.;廠.-.1.1.1.1-l-l-111!-llimlxlxlI-lrhjbIIc1:1宀

9、I.n+Jrrw-s3）得到圖的深度遍歷以及廣度遍歷4）輸入要搜索的邊，得到搜索結(jié)果5）輸入要刪除的邊，得到新的遍歷2.結(jié)果分析1）程序能夠正確的實現(xiàn)關(guān)于在鄰接矩陣和鄰接表兩種不同的儲存結(jié)構(gòu)上實現(xiàn)圖的基本運算的算法，在鄰接矩陣存儲結(jié)構(gòu)上實現(xiàn)圖的深度和廣度優(yōu)先遍歷算法2）由測試結(jié)果來看，若在輸出數(shù)據(jù)時以圖的形式輸出，更簡單直觀，程序還有待改進。實習(xí)題名：飛機最少換乘問題班級姓名學(xué)號日期2016.05.19一、問題描述設(shè)有n個城市，編號為0n1,m條航線的起點和終點由用戶輸入提供。尋找一條換乘次數(shù)最少的線路方案。（提示：可以使用有向圖表示城市間的航線。只要兩城市間有航班，則圖中這兩點間存在一條權(quán)為

10、1的邊?？梢允褂肈ijkstra算法實現(xiàn)）二、概要設(shè)計文件min.cpp中定義了兩個類，分別是圖數(shù)據(jù)結(jié)構(gòu)的抽象模板類Graph以及從抽象類Graph派生得來鄰接矩陣類MGraph。主函數(shù)mian的代碼如圖所示：三、詳細(xì)設(shè)計類和類的層次結(jié)構(gòu)程序定義了Graph類，以及鄰接矩陣類MGraph。同上鄰接矩陣類MGraph也繼承了Graph的數(shù)據(jù)成員n和e,重載了Graph的純虛函數(shù)。保護數(shù)據(jù)成員T*a指向動態(tài)生成的二維數(shù)組，用以存儲鄰接矩陣。TGraph#intn,e;+virtualResultCodeInsert(intu,intv,T&w)=0;+virtualResultCodeRemove

11、(intu,intv)=0;+virtualboolExist(intu,intv)const=0;TMGraph#T*a;#TnoEdge;#voidDFS(intv,bool*visited);#voidBFS(intv,bool*visited);_+MGraph(intmSize,constT&noedg);+MGraph();+ResultCodeInsert(intu,intv,T&w);+ResultCodeRemove(intu,intv);+boolExist(intu,intv)const;+voidDFS();+voidBFS();模版類Graph和MGraph2.核心算

12、法定義了類之后，求換乘次數(shù)最少主要是通過迪杰斯特拉算法實現(xiàn)。迪杰斯特拉算法主要通過動態(tài)創(chuàng)建數(shù)據(jù)結(jié)構(gòu)，初始化操作，將源點v加入集合S,使用for循環(huán)，按照長度的非遞減次序，依次產(chǎn)生n-1條最短路徑等步驟實現(xiàn)。核心算法程圖如下：Dijkstra()四、程序代碼迪杰斯特拉算法templatevclassT迪杰斯特拉算法voidMGraphvT:Dijkstra(intv,T*d,int*path)inti,k,w;if(vvOllvn-l)throwOutOfBounds;bool*s=newbooln;for(i=0;ivn;i+)si=false;di=avi;if(i!=v&divINF)pa

13、thi=v;elsepathi=-1;sv=true;dv=0;for(i=1;in;i+)k=Choose(d,s);sk=true;for(w=0;wconstintINFTY=2147483640;enumResultCodeUnderflow,Duplicate,Failure,Success,NotPresent;templateclassGraph抽象類public:virtualResultCodeInsert(intu,intv,T&w)=0;virtualResultCodeRemove(intu,intv)=0;virtualboolExist(intu,intv)cons

14、t=0;protected:intn,e;templatevclassT循環(huán)隊列類classSeqQueuepublic:SeqQueue(intmSize);SeqQueue()deleteq;boolIsEmpty()constreturnfront=rear;boolIsFull()constreturn(rear+1)%maxSize=front;boolFront(T&x)const;boolEnQueue(Tx);boolDeQueue();voidClear()front=rear=0;private:intfront,rear;intmaxSize;T*q;templatevc

15、lassTSeqQueue:SeqQueue(intmSize)構(gòu)造函數(shù)maxSize=mSize;q=newTmaxSize;front=rear=0;templatevclassTboolSeqQueuevT:Front(T&x)const取隊頭元素if(IsEmpty()returnfalse;x=q(front+l)%maxSize;returntrue;templatevclassTboolSeqQueuevT:EnQueue(Tx)在隊尾插入xif(IsFull()coutvvFullvvendl;returnfalse;qrear=(rear+1)%maxSize=x;retur

16、ntrue;templatevclassTboolSeqQueuevT:DeQueue()刪除隊頭元素if(IsEmpty()coutvvUnderflowvvendl;returnfalse;front=(front+1)%maxSize;returntrue;templatevclassTclassMGraph:publicGraphvT鄰接矩陣類public:MGraph(intmSize,constT&noedg);MGraph();ResultCodeInsert(intu,intv,T&w);ResultCodeRemove(intu,intv);boolExist(intu,in

17、tv)const;voidDFS();voidBFS();protected:T*a;TnoEdge;voidDFS(intv,bool*visited);voidBFS(intv,bool*visited);templatevclassTMGraphvT:MGraph(intmSize,constT&noedg)n=mSize;e=0;noEdge=noedg;a=newT*n;for(inti=0;ivn;i+)ai=newTn;for(intj=0;jvn;j+)aij=noEdge;aii=0;templateMGraph:MGraph()析構(gòu)函數(shù)for(inti=0;in;i+)de

18、leteai;deletea;templateResultCodeMGraph:Insert(intu,intv,T&w)if(uvOllvvOllun-lllvn-lllu=v)returnFailure;if(auv!=noEdge)returnDuplicate;auv=w;e+;returnSuccess;templateResultCodeMGraph:Remove(intu,intv)if(uv0llvv0llun-1llvn-1llu=v)returnFailure;if(auv=noEdge)returnNotPresent;auv=noEdge;e-;returnSucces

19、s;構(gòu)造函數(shù)插入函數(shù)刪除函數(shù)templatevclassTboolMGraphvT:Exist(intu,intv)const判斷邊是否存在if(uvOllvvOllun-lllvn-lllu=vllauv=noEdge)returnfalse;returntrue;templatevoidMGraphvT:DFS()深度遍歷bool*visited=newbooln;for(inti=0;ivn;i+)visitedi=false;for(i=0;in;i+)if(!visitedi)DFS(i,visited);deletevisited;templatevoidMGraph:DFS(in

20、tv,bool*visited)visitedv=true;coutvvv;for(inti=0;in;i+)if(avi!=noEdge&avi!=0&!visitedi)DFS(i,visited);templatevoidMGraph:BFS()廣度遍歷bool*visited=newbooln;for(inti=0;in;i+)visitedi=false;for(i=0;in;i+)if(!visitedi)BFS(i,visited);deletevisited;templatevoidMGraph:BFS(intv,bool*visited)SeqQueuevintq(n);vi

21、sitedv=true;coutvvvvv;q.EnQueue(v);while(!q.IsEmpty()q.Front(v);q.DeQueue();for(inti=0;ivn;i+)if(avi!=noEdge&avi!=0&!visitedi)visitedi=true;coutvv/結(jié)點類classENodepublic:ENode()nextArc=NULL;ENode(intvertex,Tweight,ENode*next)adjVex=vertex;w=weight;nextArc=next;intadjVex;Tw;ENode*nextArc;templatevclassT

22、classLGraph:publicGraphvT鄰接表類public:LGraph(intmSize);LGraph();ResultCodeInsert(intu,intv,T&w);ResultCodeRemove(intu,intv);boolExist(intu,intv)const;protected:ENodevT*a;templatevclassTLGraphvT:LGraph(intmSize)構(gòu)造函數(shù)n=mSize;e=0;a=newENodevT*n;for(inti=O;ivn;i+)ai=NULL;templatevclassTLGraphvT:LGraph()析構(gòu)E

23、NodevT*p,*q;for(inti=0;inextArc;deleteq;q=p;deletea;templateboolLGraph:Exist(intu,intv)const判斷邊是否存在if(uvOllvvOllun-lllvn-lllu=v)returnfalse;ENode*p=au;while(p&p-adjVex!=v)p=p-nextArc;if(!p)returnfalse;elsereturntrue;templateResultCodeLGraph:Insert(intu,intv,T&w)插入if(uv0llvv0llun-1llvn-1llu=v)returnF

24、ailure;if(Exist(u,v)returnDuplicate;ENode*p=newENode(v,w,au);au=p;e+;returnSuccess;刪除templatevclassT刪除ResultCodeLGraphvT:Remove(intu,intv)if(uvOllvvOllun-lllvn-lllu=v)returnFailure;ENodevT*p=au,*q;q=NULL;while(p&p-adjVex!=v)q=p;p=p-nextArc;if(!p)returnNotPresent;if(q)q-nextArc=p-nextArc;elseau=p-nex

25、tArc;deletep;e-;returnSuccess;intmain()主函數(shù)intn,g;coutvv請輸入元素的個數(shù):;cinn;MGraphvintA(n,INFTY);LGraphB(n);coutvv請輸入邊的條數(shù):;cing;int*a=newintg;int*b=newintg;int*w=newintg;for(inti=0;ivg;i+)coutvv請輸入邊及權(quán)值:;cinaibiwi;Insert(ai,bi,wi);Insert(ai,bi,wi);coutvv該圖的深度優(yōu)先遍歷為:vvendl;A.DFS();coutvvendl;coutvv該圖的廣度優(yōu)先遍歷為

26、:vvendl;A.BFS();coutvvendl;coutvv請輸入要搜索的邊:;intc,d;cincd;if(A.Exist(c,d)coutvv鄰接矩陣中該邊存在!vvendl;elsecoutvv鄰接矩陣中該邊不存在!vvendl;if(B.Exist(c,d)coutvv鄰接表中該邊存在!vvendl;elsecoutvv鄰接表中該邊不存在!vvendl;coutvv請輸入要刪除的邊:;inte,f;cinef;if(A.Remove(e,f)=Success)coutvv鄰接矩陣中刪除該邊成功!vvendl;elseif(A.Remove(e,f)=NotPresent)cou

27、tvv鄰接矩陣中該邊不存在!vvendl;elsecoutvv輸入錯誤!vvendl;if(B.Remove(e,f)=Success)coutvv鄰接表中刪除該邊成功!vvendl;elseif(B.Remove(e,f)=NotPresent)coutvv鄰接表中該邊不存在!vvendl;elsecoutvv鄰接表中輸入錯誤!vvendl;coutvv刪除該邊后該圖的深度優(yōu)先遍歷為:vvendl;A.DFS();coutvvendl;coutvv刪除該邊后該圖的廣度優(yōu)先遍歷為:vvendl;A.BFS();coutvvendl;return0;2.飛機換乘次數(shù)最少問題#includevio

28、stream.h#includevstring.hconstintINF=2147483647;enumResultCodeUnderflow,Duplicate,Failure,Success,NotPresent,OutOfBounds;templateclassGraph抽象類public:virtualResultCodeInsert(intu,intv,Tw)=0;virtualResultCodeRemove(intu,intv)=0;virtualboolExist(intu,intv)const=0;protected:intn,e;templateclassMGraph:pu

29、blicGraphvT鄰接矩陣類public:MGraph(intmSize,constTnoedg);MGraph();ResultCodeInsert(intu,intv,Tw);ResultCodeRemove(intu,intv);boolExist(intu,intv)const;intChoose(int*d,bool*s);voidDijkstra(intv,T*d,int*path);protected:T*a;TnoEdge;templateMGraph:MGraph(intmSize,constTnoedg)n=mSize;e=0;noEdge=noedg;a=newT*n

30、;for(inti=0;ivn;i+)ai=newTn;for(intj=0;jn;j+)aij=noEdge;aii=0;templateMGraph:MGraph()for(inti=O;ivn;i+)deleteai;deletea;templatevclassTResultCodeMGraphvT:Insert(intu,intv,Tw)if(uvOllvvOllun-lllvn-lllu=v)returnFailure;if(auv!=noEdge)returnDuplicate;auv=w;e+;returnSuccess;templateResultCodeMGraph:Remove(intu,intv)if(uv0llvv0llun-1llvn-1llu=v)returnFailure;if(auv=noEdge)returnNotPresent;auv=noEdge;e-;returnSuccess;templatevclassTboolMGraphvT:Exist(intu,intv)constif(uv0llvv0llun-1llvn-1llu=vllauv=