1、數據結構課程設計報告設計題目：構造可以使 n n 個城市連接的最小生成樹 姓名：學號：專業：物聯網工程（嵌入式培養）院系：計算機技術與科學學院班級：14051405指導教師：20162016 年 0101 月 0909 日第1頁共 17 頁摘要本次課程設計的要求是給定一個地區的n n 個城市間的距離網， 用 PrimPrim 算法建立最小生成樹， 并計算得到的最小生成 樹的代價。將該地區的城市用頂點表示，城市間的公路用邊 表示，公路的長度作為邊的權值，最終這個問題可以歸結為 網圖中，求頂點 A A 到頂點 B B的所有路徑中，邊的權值之和最 少的那條路徑。關鍵詞：最小生成樹PrimPrim 算

2、法C+C+語言源程序第2頁共 17 頁AbstractThe curr iculum design requirements is given a region ncity, thedista neebetwee nthe net with thealgorithm to establish minimumspa nningtree,calculated the price of minimum spanning tree. Cities in the region with vertexsaid, between highway in the city edge, said the len

3、gth of the road as the edge ofthe right values, fin ally the problem can be summed up in n etwork diagram, andall the paths of vertex A to B, the edge of the weights of the sum of the minimumpath.Keywords:minimum spa nning treePrim algorithmC+ Ian guage source programPrimand第3頁共 17 頁一、問題描述.41.1 題目內容

4、 .41.2 基本要求.4二、需求分析.4三、概要設計.43.1 鄰接矩陣的建立 .53.2 圖的建立 .53.3 求最小生成樹 .6四、數據結構設計 . 7五、算法設計.85.1 算法分析.85.2 算法實現 .8六、 程序測試與實現.96.1 主程序. 96.2 測試結果.10七、調試分析.10八、 遇到的問題及解決辦法 .10九、心得體會.10十、附錄.11問題描述第4頁共 17 頁1.題目內容：給定一個地區的 n 個城市間的距離網，用 Prim 算 法建立最小生成樹，并計算得到的最小生成樹的代價。2.基本要求：a）城市間的距離網米用鄰接矩陣表示，若兩個城市之間不存在道路，則將相應邊的權

5、值設為自己定義的無窮大值。（要求至少 10 個城市，15 條邊）b）最小生成樹中包括的邊及其權值，并顯示得到的最小生成樹的代價。二、需求分析本程序的功能包括圖的建立（采用鄰接矩陣存儲）和求最小生成樹。圖的建立涉及到頂點數組 datan和鄰接矩陣 Edgenn，頂點 數組運用順序表完成，操作有：頂點的插入即順序表的插入；鄰接矩 陣的建立，操作有：插入弧和對應的權值，輸出鄰接矩陣最小生成樹是通過 Prim 算法完成的。Prim 里涉及到候選最 短邊集，用數組 shortEdge n表示候選最短邊集，數組元素包括候選 最短邊的的鄰接點（adjvex）和權值（lowcost）兩個域三、概要設計1.鄰接

6、矩陣的建立第5頁共 17 頁鄰接矩陣的初始化，頂點自己對自己的權值為0,其余的權值均為 MaxWeight (自定義的無窮大，999)AdjMatGraph:AdjMatGraph(co nst int sz)/sz是頂點數，有參構造函數for(i nt i=0;isz;i+)for(i nt j=0;jsz;j+)if(i=j)Edgeij=0;elseEdgeij=MaxWeight;無窮大num OfEdges=0;鄰接矩陣中點與點之間有弧的，則將兩個頂點之間的權值設為 weight 取代 MaxWeight (無窮大,999)void AdjMatGraph:InsertEdge(co

7、nst int v1,const int v2,int weight)/ 插入弧 ，權 為 weightif(v1Vertices.ListSize()|v2Vertices.ListSize()cout參數 v1,v2 有誤 2endl;exit(0);Edgev1v2=weight;Edgev2v1=weight;num OfEdges+;2.圖的建立struct RowColWeight/ 邊信息三元組int row;int col;int weight;void AdjMatCreateGraph(AdjMatGraph &G ,DataType V,i nt n ,RowCo

8、lWeight E,i nt e)/ 用 一個存儲邊權信息的三元組來生成圖int i; for( i=O;in;i+)G.lnsertVertex(Vi); 填充頂點信息第6頁共 17 頁for(i=0;ie;i+)G.ln sertEdge(Ei.row,Ei.col,Ei.weight);3.求最小生成樹struct shortEdgeint lowcost;int adjvex;void AdjMatGraph:Prim()int k,w,cost=0;for(i nt i=1;inum OfVertices();i+)shortEdgei.lowcost=Edge0i; shortEd

9、gei.adjvex=0;shortEdge0.lowcost=0;for(i nti=1;inum OfVertices();i+)w=MaxWeight ;for(i nt j=1;jnum OfVertices();j+)if(shortEdgej.lowcost!=0 & shortEdgej.lowcostw) w=shortEdgej.lowcost;k=j;shortEdgek.lowcost=0;for(i nt j=1;jnum OfVertices();j+)if(Edgekj shortEdgej.lowcost)shortEdgej.lowcost=Edgekj

10、; shortEdgej.adjvex=k;cout最小生成樹為：endl;for(i nt i=1;inum OfVertices();i+)coutishortEdgei.adjvex-_-EdgeishortEdgei.adjvexe ndl;cost=cost+EdgeishortEdgei.adjvex;cout最小生成樹代價為：costendl;第7頁共 17 頁四、數據結構設計元素類型，結點類型class SeqListprivate:DataType dataMaxListSize;int size;public:SeqList();int ListSize()const; 返

11、回元素的個數 sizevoid Insert(const DataType & item,int pos); 在位置 pos 插入元素 item;struct RowColWeight/ 邊信息三元組int row;int col;int weight;struct RowColWeight/ 邊信息三元組int row;int col;int weight;class AdjMatGraphprivate:SeqList Vertices;/用順序表存儲結點信息int EdgeMaxVerticesMaxVertices;用數組存儲帶權或不帶權的邊int numOfEdges;/ 邊

12、數shortEdge shortEdgeMaxSize;public:AdjMatGraph(const int sz=MaxVertices);/有參構造函數，sz 為頂點數int numOfVertices()/ 返回結點數目return Vertices.ListSize();int numOfEdge()返回邊數retur n num OfEdges;第8頁共 17 頁void InsertVertex(const VerT &vertex);插入結點 vertexvoid InsertEdge(const int v1,const int v2,int weight);/ 插

13、入弧 ，權為 weightvoidprin tMGraph();void Prim();五、算法設計1. 算法分析根據用 Prim 算法求最小生成樹，設 G=(V,E)是具有 n 個頂點的連通網，T=(U,TE)是 G 的最小生成樹，T 的初始狀態為 U=u0( uo V),TE= ,重復執行下述操作：在所有 u U,v V-U 的邊中找一條代價最小的邊(u, v)并入集合 TE，同時 v 并入 U,直至 U=Vo,最后計算得到的最小 生成樹的代價2. 算法實現void AdjMatGraph:Prim()int k,w,cost=0;for(i nt i=1;inum OfVertices(

14、);i+)shortEdgei.lowcost=Edge0i;shortEdgei.adjvex=0;shortEdge0.lowcost=0;for(i nti=1;inum OfVertices();i+)w=MaxWeight ;for(i nt j=1;jnum OfVertices();j+)if(shortEdgej.lowcost!=0 & shortEdgej.lowcostw)w=shortEdgej.lowcost;k=j;第9頁共 17 頁shortEdgek.lowcost=0;for(i nt j=1;jnum OfVertices();j+)if(Edgek

15、j shortEdgej.lowcost)shortEdgej.lowcost=Edgekj;shortEdgej.adjvex=k;cout最小生成樹為：endl;for(i nt i=1;inum OfVertices();i+)coutishortEdgei.adjvex-_-EdgeishortEdgei.adjvexe nd l;cost=cost+EdgeishortEdgei.adjvex;cout最小生成樹代價為：costendl;六、程序測試與實現1.主程序void mai n()AdjMatGraph g;char a=A,B,C,D,E,F,G,H,T,J;RowColW

16、eight 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,2,7,9,2,3,10,3,7,11,3,9,12,8,9,13,7,8,14,6,7,15;int n=10,e=15;/10 個頂點，15 條邊AdjMatCreateGraph(g,a, n, rcw,e);cout 當前的頂點個數為： g.numOfVertices() endl;cout 當前的邊的條數為： g.numOfEdge() 2104 一-15- 4 36-5- 6-Q? 1Q 一4弓9-3 12赳住塾攤價知 S3請按柱意 1 鮭耀|十4 心嶄人芒半bC:w

17、ind owsXsyste m 32cm d.exe二X第11頁共 17 頁利用 C+程序去實現，還是有問題的。最后反復看代碼，構造了一個最短候選邊集，即數組 shortEdge n。九、心得體會第12頁共 17 頁本次課程設計用到了順序表的建立與插入， 圖的鄰接矩陣存儲，最終實現了求 n 個城市之間的相同公路之間的最短距離，我主要學到了將實際問題轉換為自己所學到的知識，做到了學以致用。十、附錄(源代碼)SeqList.hSeqList.h#in cludeusing n amespace std;class SeqListprivate:DataType dataMaxListSize;in

18、t size;public:SeqList();int ListSize()const; 返回元素的個數 sizevoid Insert(const DataType & item,int pos);在位置 pos 插入元素 item;SeqList:SeqList()size=0;int SeqList:ListSize()c onstreturn size;void SeqList:Insert(const DataType & item,int pos)/ 在位置 pos 插入元素 item int i;if(size=MaxListSize)cout順序表已滿無法插入！

19、endl;exit(1);if(possize)當 pos 等于 size 時表示插入在最后cout參數 pos 越界出錯!pos;i_)datai=datai-1;datapos=item; 在 pos 位置插入 itemsize+;數據元素個數 size 加 1AdjMatGraphLib.hAdjMatGraphLib.hstruct RowColWeight/ 邊信息三元組int row;int col;int weight;void AdjMatCreateGraph(AdjMatGraph & G,DataType V,i nt n ,RowColWeight e)/用一個

20、存儲邊權信息的三元組來生成圖int i;for( i=0;i n;i+)G.I nsertVertex(Vi);填充頂點信息for(i=0;ie;i+)G.ln sertEdge(Ei.row,Ei.col,Ei.weight);AdjMatGraph.hAdjMatGraph.h#in cludeconst int MaxSize=100;struct shortEdgeint lowcost;int adjvex;class AdjMatGraphprivate:SeqList Vertices;/用順序表存儲結點信息int EdgeMaxVerticesMaxVertices;用數組存儲

21、帶權或不帶權的邊int numOfEdges;/ 邊數 shortEdge shortEdgeMaxSize;public:AdjMatGraph(const int sz=MaxVertices);/ 有參構造函數，sz 為頂點數int numOfVertices()/返回結點數目E,int第14頁共 17 頁return Vertices.ListSize();第15頁共 17 頁int numOfEdge()返回邊數retur n num OfEdges;void InsertVertex(const VerT &vertex);插入結點 vertexvoid InsertEdg

22、e(const int v1,const int v2,int weight);/插入弧 ,權為 weightvoidprin tMGraph();void Prim();AdjMatGraph:AdjMatGraph(co nst int sz)/sz是頂點數，有參構造函數for(i nt i=0;isz;i+)for(i nt j=0;jsz;j+)if(i=j)Edgeij=0;elseEdgeij=MaxWeight;/ 無窮大num OfEdges=0;void AdjMatGraph:InsertVertex(const VerT &vertex)/插入結點 vertexV

23、ertices.I nsert(vertex,Vertices.ListSize();void AdjMatGraph:InsertEdge(const int v1,const int v2,int weight)/插入弧 ，權為 weightif(v1Vertices.ListSize()|v2Vertices.ListSize()cout參數 v1,v2 有誤 2endl;exit(0);Edgev1v2=weight;Edgev2v1=weight;num OfEdges+;void AdjMatGraph:pri ntMGraph()cout鄰接矩陣是：endl;for(i nt i

24、=O;inum OfVertices();i+)第16頁共 17 頁for(i nt j=O;jnum OfVertices();j+)coutsetw(10)Edgeij;coute ndl;coute ndl;void AdjMatGraph:Prim()int k,w,cost=0;for(i nt i=1;inumO fVertices();i+)shortEdgei.lowcost=Edge0i;shortEdgei.adjvex=0;shortEdge0.lowcost=0;for(i nti=1;inum OfVertices();i+)w=MaxWeight ;for(i nt j=1;jnum OfVertices();j+)if(shortEdgej.lowcost!=0 & shortEdgej.lowcostw)w=shortEdgej.lowcost;k=j;shortEdgek.lowcost=0;for(i nt j=1;jnum OfVertices();j+)if(Edgekj sho