1、數(shù)據(jù)結(jié)構(gòu)課程設(shè)計(jì)報(bào)告設(shè)計(jì)題目：構(gòu)造可以使設(shè)計(jì)題目：構(gòu)造可以使 n n 個(gè)城市連接的最小生成個(gè)城市連接的最小生成樹樹姓名：姓名： 學(xué)號(hào)：學(xué)號(hào)：專業(yè)：物聯(lián)網(wǎng)工程（嵌入式培養(yǎng)）專業(yè)：物聯(lián)網(wǎng)工程（嵌入式培養(yǎng)）院系：計(jì)算機(jī)技術(shù)與科學(xué)學(xué)院院系：計(jì)算機(jī)技術(shù)與科學(xué)學(xué)院班級(jí)：班級(jí)：14051405指導(dǎo)教師：指導(dǎo)教師： 20162016 年年 0101 月月 0909 日日 摘要本次課程設(shè)計(jì)的要求是給定一個(gè)地區(qū)的本次課程設(shè)計(jì)的要求是給定一個(gè)地區(qū)的 n n 個(gè)城市間的距離個(gè)城市間的距離網(wǎng)，用網(wǎng)，用 PrimPrim 算法建立最小生成樹，并計(jì)算得到的最小生成算法建立最小生成樹，并計(jì)算得到的最小生成樹的代價(jià)。將該地區(qū)的

2、城市用頂點(diǎn)表示，城市間的公路用樹的代價(jià)。將該地區(qū)的城市用頂點(diǎn)表示，城市間的公路用邊表示，公路的長(zhǎng)度作為邊的權(quán)值，最終這個(gè)問題可以歸邊表示，公路的長(zhǎng)度作為邊的權(quán)值，最終這個(gè)問題可以歸結(jié)為網(wǎng)圖中，求頂點(diǎn)結(jié)為網(wǎng)圖中，求頂點(diǎn) A A 到頂點(diǎn)到頂點(diǎn) B B 的所有路徑中，邊的權(quán)值的所有路徑中，邊的權(quán)值之和最少的那條路徑。之和最少的那條路徑。關(guān)鍵詞：關(guān)鍵詞：最小生成樹最小生成樹 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 題目?jī)?nèi)容題目?jī)?nèi)容 .4 41.21.2 基本要求基本要求 .4 4二、需求分析二、需求分析.4 4三、概要設(shè)計(jì)三、概要設(shè)計(jì).4 43.13.1 鄰接矩陣的建立鄰接矩陣的建立 .5 53.23.2 圖的建立圖的建立 .5 53.33.3 求最小生成樹求最小生成樹 .6 6四、數(shù)據(jù)結(jié)構(gòu)設(shè)計(jì)四、數(shù)據(jù)結(jié)構(gòu)設(shè)計(jì).7 7五、算法設(shè)計(jì)五、算法設(shè)計(jì).8 85.15.1 算法分析算法分析 .8 85.25.2 算法實(shí)現(xiàn)算法實(shí)現(xiàn) .8 8六、程序測(cè)試與實(shí)現(xiàn)六、程序測(cè)試與實(shí)現(xiàn).9 96.1

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

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

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

10、es.ListSize()|v2Vertices.ListSize()cout參數(shù) 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)/用一個(gè)存儲(chǔ)邊權(quán)信息的三元組來生成圖int i;for( i=0;in;i+)G.Insert

11、Vertex(Vi);/填充頂點(diǎn)信息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最小生成樹代價(jià)為：costendl;四、 數(shù)據(jù)結(jié)構(gòu)設(shè)計(jì)數(shù)據(jù)結(jié)構(gòu)設(shè)計(jì)元素類型，結(jié)點(diǎn)類型class SeqListprivate:DataType dataMaxListSize;int size;public:SeqList();int ListSize()const;/返回元素的個(gè)數(shù) 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;/用順序表存儲(chǔ)結(jié)點(diǎn)信息int EdgeMaxVerticesMaxVertices;/用數(shù)組存儲(chǔ)帶權(quán)或不帶權(quán)的邊int numOfEdges;/邊數(shù)shortEdge shortEdgeMaxSize;public:AdjMatGraph(const int sz=MaxVertices);/有參構(gòu)造函數(shù),sz 為頂點(diǎn)數(shù)i

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

16、頂點(diǎn)的連通網(wǎng)，T=(U,TE)是 G 的最小生成樹，T 的初始狀態(tài)為 U=u0( u0V）),TE= ,重復(fù)執(zhí)行下述操作：在所有 uU,vV-U 的邊中找一條代價(jià)最小的邊（u，v）并入集合 TE,同時(shí) v 并入 U,直至 U=V0,最后計(jì)算得到的最小生成樹的代價(jià)2. 算法實(shí)現(xiàn)算法實(shí)現(xiàn)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最小生成樹代價(jià)為：最小生成樹代價(jià)為：costendl;costendl; 六、六、 程序測(cè)試與實(shí)現(xiàn)程序測(cè)試與實(shí)現(xiàn)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 個(gè)頂點(diǎn)，個(gè)頂點(diǎn)，1515 條邊條邊AdjMatCreateGraph(g,a,n,rcw,e);AdjMatCreateGraph(g,a,n,rcw,e);coutcout 當(dāng)前的頂點(diǎn)個(gè)數(shù)為：當(dāng)前的頂點(diǎn)個(gè)數(shù)為： g.numOfVertices()g.numO

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

23、解最小生成樹的過程中，算法能夠看懂，但是利用 C+程序去實(shí)現(xiàn)，還是有問題的。最后反復(fù)看代碼，構(gòu)造了一個(gè)最短候選邊集，即數(shù)組 shortEdgen。九、九、 心得體會(huì)心得體會(huì)本次課程設(shè)計(jì)用到了順序表的建立與插入，圖的鄰接矩陣存儲(chǔ)，最本次課程設(shè)計(jì)用到了順序表的建立與插入，圖的鄰接矩陣存儲(chǔ)，最終實(shí)現(xiàn)了求終實(shí)現(xiàn)了求 n n 個(gè)個(gè)城市城市之間的相同公路之間的最短距離，我主要學(xué)到之間的相同公路之間的最短距離，我主要學(xué)到了將實(shí)際問題轉(zhuǎn)換為自己所學(xué)到的知識(shí)，做到了學(xué)以致用。了將實(shí)際問題轉(zhuǎn)換為自己所學(xué)到的知識(shí)，做到了學(xué)以致用。十、十、 附錄（源代碼）附錄（源代碼）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;/返回元素的個(gè)數(shù)返回元素的個(gè)數(shù) 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)/當(dāng)當(dāng) pospos 等于等于 sizesize 時(shí)表示插入在最后時(shí)表示插入在最后 coutcout參數(shù)參數(shù) pospos 越界出錯(cuò)越界出錯(cuò)!endl;!pos;i-)for(i=size;ipos;i-)datai=datai-1;datai=dat

27、ai-1;datapos=item;/datapos=item;/在在 pospos 位置插入位置插入 itemitemsize+;/size+;/數(shù)據(jù)元素個(gè)數(shù)數(shù)據(jù)元素個(gè)數(shù) 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)/用一個(gè)存儲(chǔ)邊權(quán)信息的三元組來生成圖用一個(gè)存儲(chǔ)邊權(quán)信息的三元組來生成圖 intint i;i;for(for( i=0;in;i+)i=0;in;i+)G.InsertVertex(Vi);/G.InsertVertex(Vi);/填充頂點(diǎn)信息填充頂點(diǎn)信息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;/用順序表存儲(chǔ)結(jié)點(diǎn)信息用順序表存儲(chǔ)結(jié)點(diǎn)信息intint Ed

30、geMaxVerticesMaxVertices;/EdgeMaxVerticesMaxVertices;/用數(shù)組存儲(chǔ)帶權(quán)或不帶權(quán)的邊用數(shù)組存儲(chǔ)帶權(quán)或不帶權(quán)的邊intint numOfEdges;/numOfEdges;/邊數(shù)邊數(shù)shortEdgeshortEdge shortEdgeMaxSize;shortEdgeMaxSize;public:public:AdjMatGraph(constAdjMatGraph(const intint sz=MaxVertices);sz=MaxVertices);/有參構(gòu)造函數(shù)有參構(gòu)造函數(shù),sz,sz 為頂點(diǎn)數(shù)為頂點(diǎn)數(shù)intint numOfVert

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

32、tEdge(const intint v1,constv1,const intint v2,intv2,int weight);/weight);/插入弧插入弧，權(quán)為，權(quán)為weightweightvoidvoid printMGraph();printMGraph();voidvoid Prim();Prim();AdjMatGraph:AdjMatGraph(constAdjMatGraph:AdjMatGraph(const intint sz)/szsz)/sz 是頂點(diǎn)數(shù)，有參構(gòu)造函數(shù)是頂點(diǎn)數(shù)，有參構(gòu)造函數(shù) 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)/插入結(jié)點(diǎn)插入結(jié)點(diǎn) 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)/插入弧插入弧，權(quán)為，權(quán)為 weightweight if(v1Vertices.ListSize()|v2Vertices.ListSize()if(v1Vertices.ListSize()|v2Vertices.ListSiz

35、e() coutcout參數(shù)參數(shù) 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