1、數據結構課程設計報告設計題目：構造可以使設計題目：構造可以使 n n 個城市連接的最小生成個城市連接的最小生成樹樹姓名：姓名： 學號：學號：專業：物聯網工程（嵌入式培養）專業：物聯網工程（嵌入式培養）院系：計算機技術與科學學院院系：計算機技術與科學學院班級：班級：14051405指導教師：指導教師： 20162016 年年 0101 月月 0909 日日 摘要本次課程設計的要求是給定一個地區的本次課程設計的要求是給定一個地區的 n n 個城市間的距離個城市間的距離網，用網，用 PrimPrim 算法建立最小生成樹，并計算得到的最小生成算法建立最小生成樹，并計算得到的最小生成樹的代價。將該地區的

2、城市用頂點表示，城市間的公路用樹的代價。將該地區的城市用頂點表示，城市間的公路用邊表示，公路的長度作為邊的權值，最終這個問題可以歸邊表示，公路的長度作為邊的權值，最終這個問題可以歸結為網圖中，求頂點結為網圖中，求頂點 A A 到頂點到頂點 B B 的所有路徑中，邊的權值的所有路徑中，邊的權值之和最少的那條路徑。之和最少的那條路徑。關鍵詞：關鍵詞：最小生成樹最小生成樹 PrimPrim 算法算法 C+C+語言源程序語言源程序AbstractTheThe curriculumcurriculum designdesign requirementsrequirements isis givengiv

3、en a a regionregion n n city,city, thethe distancedistance betweenbetween thethe netnet withwith thethe PrimPrim algorithmalgorithm toto establishestablish minimumminimum spanningspanning tree,tree, andand calculatedcalculated thethe priceprice ofof minimumminimum spanningspanning tree.tree. CitiesC

4、ities inin thethe regionregion withwith vertexvertex said,said, betweenbetween highwayhighway inin thethe citycity edge,edge, saidsaid thethe lengthlength ofof thethe roadroad asas thethe edgeedge ofof thethe rightright values,values, finallyfinally thethe problemproblem cancan bebe summedsummed upu

5、p inin networknetwork diagram,diagram, andand allall thethe pathspaths ofof vertexvertex A A toto B,B, thethe edgeedge ofof thethe weightsweights ofof thethe sumsum ofof thethe minimumminimum path.path.Keywords:Keywords: minimumminimum spanningspanning treetreePrimPrim algorithmalgorithm C+C+ langua

6、gelanguage sourcesource programprogram目 錄一、問題描述一、問題描述.4 41.11.1 題目內容題目內容 .4 41.21.2 基本要求基本要求 .4 4二、需求分析二、需求分析.4 4三、概要設計三、概要設計.4 43.13.1 鄰接矩陣的建立鄰接矩陣的建立 .5 53.23.2 圖的建立圖的建立 .5 53.33.3 求最小生成樹求最小生成樹 .6 6四、數據結構設計四、數據結構設計.7 7五、算法設計五、算法設計.8 85.15.1 算法分析算法分析 .8 85.25.2 算法實現算法實現 .8 8六、程序測試與實現六、程序測試與實現.9 96.1

7、6.1 主程序主程序 .9 96.26.2 測試結果測試結果 .1010七、調試分析七、調試分析.1010八、遇到的問題及解決辦法八、遇到的問題及解決辦法.1010九、心得體會九、心得體會.1010十、附錄十、附錄.1111一、一、 問題描述問題描述1 題目內容：給定一個地區的 n 個城市間的距離網，用 Prim 算法建立最小生成樹，并計算得到的最小生成樹的代價。2 基本要求：a) 城市間的距離網采用鄰接矩陣表示，若兩個城市之間不存在道路，則將相應邊的權值設為自己定義的無窮大值。 （要求至少 10 個城市，15 條邊）b) 最小生成樹中包括的邊及其權值，并顯示得到的最小生成樹的代價。二、二、

8、需求分析需求分析本程序的功能包括圖的建立（采用鄰接矩陣存儲）和求最小生成樹。1圖的建立涉及到頂點數組 datan和鄰接矩陣 Edgenn，頂點數組運用順序表完成，操作有：頂點的插入即順序表的插入；鄰接矩陣的建立，操作有：插入弧和對應的權值,輸出鄰接矩陣2最小生成樹是通過 Prim 算法完成的。Prim 里涉及到候選最短邊集，用數組 shortEdgen表示候選最短邊集，數組元素包括候選最短邊的的鄰接點（adjvex）和權值（lowcost）兩個域三、三、 概要設計概要設計1. 鄰接矩陣的建立鄰接矩陣的建立1鄰接矩陣的初始化，頂點自己對自己的權值為 0，其余的權值均為 MaxWeight（自定義

9、的無窮大,999）AdjMatGraph:AdjMatGraph(const int sz)/sz 是頂點數，有參構造函數for(int i=0;isz;i+)for(int j=0;jsz;j+)if(i=j)Edgeij=0;elseEdgeij=MaxWeight;/無窮大numOfEdges=0;2鄰接矩陣中點與點之間有弧的，則將兩個頂點之間的權值設為 weight 取代 MaxWeight（無窮大,999）void AdjMatGraph:InsertEdge(const int v1,const int v2,int weight)/插入弧，權為 weightif(v1Vertic

10、es.ListSize()|v2Vertices.ListSize()cout參數 v1,v2 有誤 2endl;exit(0);Edgev1v2=weight;Edgev2v1=weight;numOfEdges+;2. 圖的建立圖的建立struct RowColWeight/邊信息三元組int row;int col;int weight;void AdjMatCreateGraph(AdjMatGraph &G,DataType V,int n,RowColWeight E,int e)/用一個存儲邊權信息的三元組來生成圖int i;for( i=0;in;i+)G.Insert

11、Vertex(Vi);/填充頂點信息for(i=0;ie;i+)G.InsertEdge(Ei.row,Ei.col,Ei.weight);3. 求最小生成樹求最小生成樹struct shortEdgeint lowcost;int adjvex;void AdjMatGraph:Prim()int k,w,cost=0;for(int i=1;inumOfVertices();i+)shortEdgei.lowcost=Edge0i;shortEdgei.adjvex=0;shortEdge0.lowcost=0;for(int i=1;inumOfVertices();i+)w=MaxWe

12、ight ;for(int j=1;jnumOfVertices();j+)if(shortEdgej.lowcost!=0 & shortEdgej.lowcostw)w=shortEdgej.lowcost;k=j;shortEdgek.lowcost=0;for(int j=1;jnumOfVertices();j+)if(Edgekj shortEdgej.lowcost)shortEdgej.lowcost=Edgekj;shortEdgej.adjvex=k;cout最小生成樹為：endl;for(int i=1;inumOfVertices();i+)coutishort

13、Edgei.adjvex-EdgeishortEdgei.adjvexendl;cost=cost+EdgeishortEdgei.adjvex;cout最小生成樹代價為：costendl;四、 數據結構設計數據結構設計元素類型，結點類型class SeqListprivate:DataType dataMaxListSize;int size;public:SeqList();int ListSize()const;/返回元素的個數 sizevoid Insert(const DataType & item,int pos);/在位置 pos 插入元素 item;struct Row

14、ColWeight/邊信息三元組int row;int col;int weight;struct RowColWeight/邊信息三元組int row;int col;int weight;class AdjMatGraphprivate:SeqList Vertices;/用順序表存儲結點信息int EdgeMaxVerticesMaxVertices;/用數組存儲帶權或不帶權的邊int numOfEdges;/邊數shortEdge shortEdgeMaxSize;public:AdjMatGraph(const int sz=MaxVertices);/有參構造函數,sz 為頂點數i

15、nt numOfVertices()/返回結點數目return Vertices.ListSize();int numOfEdge()/返回邊數return numOfEdges;void InsertVertex(const VerT &vertex);/插入結點 vertexvoid InsertEdge(const int v1,const int v2,int weight);/插入弧，權為weightvoid printMGraph();void Prim();五、五、 算法設計算法設計1. 算法分析算法分析根據用 Prim 算法求最小生成樹，設 G=(V,E)是具有 n 個

16、頂點的連通網，T=(U,TE)是 G 的最小生成樹，T 的初始狀態為 U=u0( u0V）),TE= ,重復執行下述操作：在所有 uU,vV-U 的邊中找一條代價最小的邊（u，v）并入集合 TE,同時 v 并入 U,直至 U=V0,最后計算得到的最小生成樹的代價2. 算法實現算法實現voidvoid AdjMatGraph:Prim()AdjMatGraph:Prim() intint k,w,cost=0;k,w,cost=0;for(intfor(int i=1;inumOfVertices();i+)i=1;inumOfVertices();i+) shortEdgei.lowcost=

17、Edge0i;shortEdgei.lowcost=Edge0i;shortEdgei.adjvex=0;shortEdgei.adjvex=0; shortEdge0.lowcost=0;shortEdge0.lowcost=0;for(intfor(int i=1;inumOfVertices();i+)i=1;inumOfVertices();i+) w=MaxWeightw=MaxWeight ; ;for(intfor(int j=1;jnumOfVertices();j+)j=1;jnumOfVertices();j+) if(shortEdgej.lowcost!=0if(sho

18、rtEdgej.lowcost!=0 & shortEdgej.lowcostw)shortEdgej.lowcostw) w=shortEdgej.lowcost;w=shortEdgej.lowcost;k=j;k=j; shortEdgek.lowcost=0;shortEdgek.lowcost=0;for(intfor(int j=1;jnumOfVertices();j+)j=1;jnumOfVertices();j+) if(Edgekjif(Edgekj shortEdgej.lowcost)shortEdgej.lowcost) shortEdgej.lowcost=

19、Edgekj;shortEdgej.lowcost=Edgekj;shortEdgej.adjvex=k;shortEdgej.adjvex=k; coutcout最小生成樹為：最小生成樹為：endl;endl;for(intfor(int i=1;inumOfVertices();i+)i=1;inumOfVertices();i+) coutishortEdgei.adjvex-coutishortEdgei.adjvex-EdgeishortEdgei.adjvexendl;EdgeishortEdgei.adjvexendl;cost=cost+EdgeishortEdgei.adjv

20、ex;cost=cost+EdgeishortEdgei.adjvex; coutcout最小生成樹代價為：最小生成樹代價為：costendl;costendl; 六、六、 程序測試與實現程序測試與實現1.主程序主程序voidvoid main()main() AdjMatGraphAdjMatGraph g;g;charchar a=A,B,C,D,E,F,G,H,I,J;a=A,B,C,D,E,F,G,H,I,J;RowColWeightRowColWeight rcw=0,4,1,0,1,2,4,5,3,0,5,4,1,5,5,5,6,6,1,2,7,2,6,8,rcw=0,4,1,0,

21、1,2,4,5,3,0,5,4,1,5,5,5,6,6,1,2,7,2,6,8,2,7,9,2,3,10,3,7,11,3,9,12,8,9,13,7,8,14,6,7,15;2,7,9,2,3,10,3,7,11,3,9,12,8,9,13,7,8,14,6,7,15;intint n=10,e=15;/10n=10,e=15;/10 個頂點，個頂點，1515 條邊條邊AdjMatCreateGraph(g,a,n,rcw,e);AdjMatCreateGraph(g,a,n,rcw,e);coutcout 當前的頂點個數為：當前的頂點個數為： g.numOfVertices()g.numO

22、fVertices() endl;endl; coutcout 當前的邊的條數為：當前的邊的條數為： g.numOfEdge()g.numOfEdge() endl;endl;g.printMGraph();g.printMGraph();g.Prim();g.Prim(); 2.測試結果（測試結果（999999 是我自己設置的無窮大）是我自己設置的無窮大）七、 調試分析調試分析1圖的鄰接矩陣是一個 n*n 的矩陣，所以其空間代價是 O(n2)2在求解最小生成樹的過程中，會不斷的讀取任意兩個頂點之間邊的權值，所以采用鄰接矩陣八、 遇到的問題及解決辦法遇到的問題及解決辦法在求解利用 Prim 求

23、解最小生成樹的過程中，算法能夠看懂，但是利用 C+程序去實現，還是有問題的。最后反復看代碼，構造了一個最短候選邊集，即數組 shortEdgen。九、九、 心得體會心得體會本次課程設計用到了順序表的建立與插入，圖的鄰接矩陣存儲，最本次課程設計用到了順序表的建立與插入，圖的鄰接矩陣存儲，最終實現了求終實現了求 n n 個個城市城市之間的相同公路之間的最短距離，我主要學到之間的相同公路之間的最短距離，我主要學到了將實際問題轉換為自己所學到的知識，做到了學以致用。了將實際問題轉換為自己所學到的知識，做到了學以致用。十、十、 附錄（源代碼）附錄（源代碼）SeqList.hSeqList.h#inclu

24、de#includeusingusing namespacenamespace std;std;classclass SeqListSeqList private:private:DataTypeDataType dataMaxListSize;dataMaxListSize;intint size;size;public:public:SeqList();SeqList();intint ListSize()const;/ListSize()const;/返回元素的個數返回元素的個數 sizesizevoidvoid Insert(constInsert(const DataTypeData

25、Type & & item,intitem,int pos);/pos);/在位置在位置 pospos 插入元素插入元素 itemitem;SeqList:SeqList()SeqList:SeqList() size=0;size=0; intint SeqList:ListSize()constSeqList:ListSize()const returnreturn size;size; voidvoid SeqList:Insert(constSeqList:Insert(const DataTypeDataType & & item,intitem,in

26、t pos)/pos)/在位置在位置 pospos 插入元素插入元素 itemitem intint i;i;if(size=MaxListSize)if(size=MaxListSize) coutcout順序表已滿無法插入！順序表已滿無法插入！endl;endl;exit(1);exit(1); if(possize)/if(possize)/當當 pospos 等于等于 sizesize 時表示插入在最后時表示插入在最后 coutcout參數參數 pospos 越界出錯越界出錯!endl;!pos;i-)for(i=size;ipos;i-)datai=datai-1;datai=dat

27、ai-1;datapos=item;/datapos=item;/在在 pospos 位置插入位置插入 itemitemsize+;/size+;/數據元素個數數據元素個數 sizesize 加加 1 1 AdjMatGraphLib.hAdjMatGraphLib.hstructstruct RowColWeight/RowColWeight/邊信息三元組邊信息三元組 intint row;row;intint col;col;intint weight;weight;voidvoid AdjMatCreateGraph(AdjMatGraphAdjMatCreateGraph(AdjMat

28、Graph &G,DataType&G,DataType V,intV,int n,RowColWeightn,RowColWeight E,intE,int e)/e)/用一個存儲邊權信息的三元組來生成圖用一個存儲邊權信息的三元組來生成圖 intint i;i;for(for( i=0;in;i+)i=0;in;i+)G.InsertVertex(Vi);/G.InsertVertex(Vi);/填充頂點信息填充頂點信息for(i=0;ie;i+)for(i=0;ie;i+)G.InsertEdge(Ei.row,Ei.col,Ei.weight);G.InsertEdge(

29、Ei.row,Ei.col,Ei.weight); AdjMatGraph.hAdjMatGraph.h#include#includeconstconst intint MaxSize=100;MaxSize=100;structstruct shortEdgeshortEdge intint lowcost;lowcost;intint adjvex;adjvex;classclass AdjMatGraphAdjMatGraph private:private:SeqListSeqList Vertices;/Vertices;/用順序表存儲結點信息用順序表存儲結點信息intint Ed

30、geMaxVerticesMaxVertices;/EdgeMaxVerticesMaxVertices;/用數組存儲帶權或不帶權的邊用數組存儲帶權或不帶權的邊intint numOfEdges;/numOfEdges;/邊數邊數shortEdgeshortEdge shortEdgeMaxSize;shortEdgeMaxSize;public:public:AdjMatGraph(constAdjMatGraph(const intint sz=MaxVertices);sz=MaxVertices);/有參構造函數有參構造函數,sz,sz 為頂點數為頂點數intint numOfVert

31、ices()/numOfVertices()/返回結點數目返回結點數目 returnreturn Vertices.ListSize();Vertices.ListSize(); intint numOfEdge()/numOfEdge()/返回邊數返回邊數 returnreturn numOfEdges;numOfEdges; voidvoid InsertVertex(constInsertVertex(const VerTVerT &vertex);/&vertex);/插入結點插入結點 vertexvertexvoidvoid InsertEdge(constInser

32、tEdge(const intint v1,constv1,const intint v2,intv2,int weight);/weight);/插入弧插入弧，權為，權為weightweightvoidvoid printMGraph();printMGraph();voidvoid Prim();Prim();AdjMatGraph:AdjMatGraph(constAdjMatGraph:AdjMatGraph(const intint sz)/szsz)/sz 是頂點數，有參構造函數是頂點數，有參構造函數 for(intfor(int i=0;isz;i+)i=0;isz;i+)for

33、(intfor(int j=0;jsz;j+)j=0;jsz;j+) if(i=j)if(i=j)Edgeij=0;Edgeij=0;elseelseEdgeij=MaxWeight;/Edgeij=MaxWeight;/無窮大無窮大 numOfEdges=0;numOfEdges=0; voidvoid AdjMatGraph:InsertVertex(constAdjMatGraph:InsertVertex(const VerTVerT &vertex)/&vertex)/插入結點插入結點 vertexvertex Vertices.Insert(vertex,Verti

34、ces.ListSize();Vertices.Insert(vertex,Vertices.ListSize(); voidvoid AdjMatGraph:InsertEdge(constAdjMatGraph:InsertEdge(const intint v1,constv1,const intint v2,intv2,int weight)/weight)/插入弧插入弧，權為，權為 weightweight if(v1Vertices.ListSize()|v2Vertices.ListSize()if(v1Vertices.ListSize()|v2Vertices.ListSiz

35、e() coutcout參數參數 v1,v2v1,v2 有誤有誤 2endl;2endl;exit(0);exit(0); Edgev1v2=weight;Edgev1v2=weight;Edgev2v1=weight;Edgev2v1=weight;numOfEdges+;numOfEdges+; voidvoid AdjMatGraph:printMGraph()AdjMatGraph:printMGraph() coutcout鄰接矩陣是：鄰接矩陣是：endl;endl;for(intfor(int i=0;inumOfVertices();i+)i=0;inumOfVertices()

36、;i+) for(intfor(int j=0;jnumOfVertices();j+)j=0;jnumOfVertices();j+) coutsetw(10)Edgeij;coutsetw(10)Edgeij; coutendl;coutendl;coutendl;coutendl; voidvoid AdjMatGraph:Prim()AdjMatGraph:Prim() intint k,w,cost=0;k,w,cost=0;for(intfor(int i=1;inumOfVertices();i+)i=1;inumOfVertices();i+) shortEdgei.lowco

37、st=Edge0i;shortEdgei.lowcost=Edge0i;shortEdgei.adjvex=0;shortEdgei.adjvex=0; shortEdge0.lowcost=0;shortEdge0.lowcost=0;for(intfor(int i=1;inumOfVertices();i+)i=1;inumOfVertices();i+) w=MaxWeightw=MaxWeight ; ;for(intfor(int j=1;jnumOfVertices();j+)j=1;jnumOfVertices();j+) if(shortEdgej.lowcost!=0if(

38、shortEdgej.lowcost!=0 & shortEdgej.lowcostw)shortEdgej.lowcostw) w=shortEdgej.lowcost;w=shortEdgej.lowcost;k=j;k=j; shortEdgek.lowcost=0;shortEdgek.lowcost=0;for(intfor(int j=1;jnumOfVertices();j+)j=1;jnumOfVertices();j+) if(Edgekjif(Edgekj shortEdgej.lowcost)shortEdgej.lowcost) shortEdgej.lowcost=Edgekj;shortEdgej.lowcost=Edgekj;shortEdgej.adjvex=k;shortEdgej.adjvex=k; coutcout最小生成樹為：最小生成樹為：endl;endl;for(intfor(int i=1;inumOfVertices();i+)i=1;inumOfVertices();i+) coutishortEdgei.adjvex-coutishortEdgei.adjv