1、數(shù)據(jù)結(jié)構(gòu)課程設(shè)計(jì)報(bào)告設(shè)計(jì)題目:構(gòu)造可以使n個(gè)城市連接的最小生成樹姓名：學(xué)號(hào)：專業(yè)：物聯(lián)網(wǎng)工程（嵌入式培養(yǎng)）院系：計(jì)算機(jī)技術(shù)與科學(xué)學(xué)院班級(jí):1405指導(dǎo)教師：2016年04月09日第 頁(yè)共17頁(yè)摘要本次課程設(shè)計(jì)的要求是給定一個(gè)地區(qū)的n個(gè)城市間的距離網(wǎng)用Prim算法建立最小生成樹.并計(jì)算得到的最小生成樹的代價(jià)。將該地區(qū)的城市用頂點(diǎn)表示,城市間的公路用邊表示.公路的長(zhǎng)度作為邊的權(quán)值.最終這個(gè)問題可以歸結(jié)為網(wǎng)圖中求頂點(diǎn)A到頂點(diǎn)B的所有路徑中，邊的權(quán)值之和最少的那條路槿。關(guān)鍵詞：最小生成樹Prim算法C+語(yǔ)言源程序AbstractThecurriculumdesignrequirementsisgive

2、naregionncity,thedistancebetweenthenetwiththePrimalgorithmtoestablishminimumspanningtree,andcalculatedthepriceofminimumspanningtreeCitiesintheregionwithvertexsaid,betweenhighwayinthecityedge,saidthelengthoftheroadastheedgeoftherightvalues,finallytheproblemcanbesummedupinnetworkdiagram,andallthepaths

3、ofvertexAtoB,theedgeoftheweightsofthesumoftheminimumpathKeywords：minimumspanningtreePrimalgorithmC+languagesourceprogramTOC o 1-5 h z HYPERLINK l bookmark8 o Current Document 一、問題描述4題目?jī)?nèi)容41.2基本要求4 HYPERLINK l bookmark10 o Current Document 二、需求分析4 HYPERLINK l bookmark12 o Current Document 三、概要設(shè)計(jì)43.1鄰接

4、矩陣的建立3.2圖的建立 HYPERLINK l bookmark24 o Current Document 33求最小生成樹6 HYPERLINK l bookmark26 o Current Document 四、數(shù)據(jù)結(jié)構(gòu)設(shè)計(jì)7 HYPERLINK l bookmark28 o Current Document 五、算法設(shè)計(jì)85.1算法分析85.2算法實(shí)現(xiàn)8 HYPERLINK l bookmark38 o Current Document 六、程序測(cè)試與實(shí)現(xiàn)96.1主酚96.2測(cè)試結(jié)果10 HYPERLINK l bookmark40 o Current Document 七、調(diào)試分析1

5、0 HYPERLINK l bookmark48 o Current Document 八、遇到的問題及解決辦法10 HYPERLINK l bookmark52 o Current Document 九、心得體會(huì)10十、附錄11一、問題描述題目?jī)?nèi)容：給定一個(gè)地區(qū)的n個(gè)城市間的距離網(wǎng)，用Pnm算法建立最小生成樹，并計(jì)算得到的最小生成樹的代價(jià)?；疽螅篴）城市間的距離網(wǎng)采用鄰接矩陣表示，若兩個(gè)城市之間不存在道路，則將相應(yīng)邊的權(quán)值設(shè)為自己定義的無(wú)窮大值。（要求至少10個(gè)城市，15條邊）b）最小生成樹中包括的邊及其權(quán)值，并顯示得到的最小生成樹的代價(jià)。二、需求分析本程序的功能包括圖的建立（采用鄰接矩

6、陣存儲(chǔ)）和求最小生成樹。圖的建立涉及到頂點(diǎn)數(shù)組datan和鄰接矩陣Edgenn,頂點(diǎn)數(shù)組運(yùn)用順序表完成，操作有：頂點(diǎn)的插入即順序表的插入；鄰接矩陣的建立，操作有：插入弧和對(duì)應(yīng)的權(quán)值，輸出鄰接矩陣最小生成樹是通過Prim算法完成的。Prim里涉及到候選最短邊集，用數(shù)組shortEdgen表示候選最短邊集，數(shù)組元素包括候選最短邊的的鄰接點(diǎn)（adjvex）和權(quán)值（lowcost）兩個(gè)域三、概要設(shè)計(jì)鄰接矩陣的建立鄰接矩陣的初始化，頂點(diǎn)自己對(duì)自己的權(quán)值為0,其余的權(quán)值均為MnxWeight(自定義的無(wú)窮大,999)AdjMatGraph:AdjMatGraph(constmtsz)/sz是頂點(diǎn)數(shù)，有參構(gòu)

7、造函數(shù)fbr(inti=0;isz;i+)fbr(iiitj=0jszJ+)If(l=J)Edgeij=0;elseEdgeij1=MaxWeighty/無(wú)窮knumOfEdges=0;鄰接矩陣中點(diǎn)與點(diǎn)之間有弧的，則將兩個(gè)頂點(diǎn)之間的權(quán)值設(shè)為weight取代MaxWeight(無(wú)窮大,999)voidAdjMatGraph:InsenEdge(constintvl,constmtv2.iiitweight)插入弧vl,v2A,權(quán)為weightif(vlVertices.ListSize()|v2Veitices.ListSize()coutH參數(shù)vl,v2有誤2Hendl;exit(O);Edg

8、evlv2=weight;Edgev2vl=weight;numOfEdges+;圖的建立stmctRowColWeight/邊信息三元組iiitrow;iiitcol;iiitweight;voidAdjMatCreateGraph(AdjMatGraph&G；DataTvpeV.iiitn.RowColWeightE,iiite)用一個(gè)存儲(chǔ)邊權(quán)信息的三元組來(lái)生成圖mti;fbr(i=O:in;i+)G.InsertVertex(Vi);/填充頂點(diǎn)信息fbr(i=O;ie;i-H-)G.IiiseitEdge(Ei.iow,Ei.cotEi.weight);求最小生成樹stmctshonEd

9、gemtlowcost;iiitadjvex;voidAdjMatGraph:Priin()iiitk,w.cost=0;fbr(inti=l;inumOfVenicesQ;i-H-)shortEdgei.lowcost=Edge0i;shortEdgeiadjvex=0;shonEdge0.lowcost=0;fbr(inti=l;inumOfVeiticesQ;i-H-)w=MaxWeight;fbr(mtj=ljnumOfVeiticesQ;j+)if(shoitEdgej.lowcost!=0&shortEdgej.Iowcostw)w=shortEdgejlowcost;k=J；sh

10、ortEdgek.lowcost=0;fbr(mtj=ljnumOfVeiticesQ;j+)if(EdgekjshonEdgeJj.lowcost)shortEdgej.lowcost=Edgekj;shortEdgej.adjvex=k;coutH最小生成樹為：yeiidl;fbr(inti=l;inumOfVenicesQ;i-H-)coutiH-HshonEdgei.adjvexHEdgeishortEdgei.adjvexendl;cost=cost+EdgeishoitEdgei.adjvex;coutM最小生成樹代價(jià)為:Hcostendl;四、數(shù)據(jù)結(jié)構(gòu)設(shè)計(jì)元素類型，結(jié)點(diǎn)類型cla

11、ssSeqListprivate:DataTvpedataMaxListSize;mtsize;public:SeqListQ;intListSizeQconst;/返回元素的個(gè)數(shù)sizevoidIiisert(constDataTe&itemiiitpos);在位置pos插入元素item;stiuctRowColWeight/邊信息三元組imtrow;mtcol;mtweight;stmctRowColWeight/邊信息三元組imtrow;mtcol;mtweight;classAdjMatGraphiprivate:SeqListVenices;/用順序表存儲(chǔ)結(jié)點(diǎn)信息mtEdgeMaxV

12、erticesMaxVertices;/用數(shù)組存儲(chǔ)帶權(quán)或不帶權(quán)的邊mtnumOfEdges;/邊數(shù)shonEdgeshortEdgeMaxSize;public:AdjMatGraph(constintsz=MaxVertices);有參構(gòu)造函數(shù),sz為頂點(diǎn)數(shù)iiitnumOfVertices()/返回結(jié)點(diǎn)數(shù)目returnVeitices.ListSize();mtnumOfEdge()返回邊數(shù)returnnumOfEdges;voidIiisenVenex(constVeiT&vert亡x);插入結(jié)點(diǎn)vertexvoidIiisertEdge(constintvl,constintv2,in

13、tweight);/插入弧權(quán)為weightvoidpimtMGraph();voidPrim();五、算法設(shè)計(jì)算法分析根據(jù)用Pnm算法求最小生成樹，設(shè)G=(V,E)是具有n個(gè)頂點(diǎn)的連通網(wǎng)，T=(U,TE)是G的最小生成樹,T的初始狀態(tài)為U=uo(uoFV),TE=,重復(fù)執(zhí)行下述操作:在所有uU,vFV-U的邊中找一條代價(jià)最小的邊(11,v)并入集合TE,同時(shí)v并入U(xiǎn),直至U=V0,最后計(jì)算得到的最小生成樹的代價(jià)算法實(shí)現(xiàn)voidAdjMatGraph:Prim()intk,w,cost=0;for(inti=1;inumOfVertices();i+)shortEdgeilowcost=Edge

14、0l;shortEdgei.adjvex=0;shortE(lge0.Iowcost=0;for(inti=l;inumOfyrertices();i+)w=MaxWeight;for(intj=lnumOfVertices()+)if(shortEdgeJowcost!=0&shortEdgejJowcostw)w=shortEdgej.Iowcost;k=j；shortEdgek.Iowcost=0;for(intj=lijnumOfVertices()+)if(EdgekjshortEdgejJowcost)shortEdgejJowcost=Edgekj;shortEdgej.adjv

15、ex=k;coutn最小生成樹為：vvendl;for(inti=1;inumOfVerticesO；i+)coutvvivv”vvshortEdgei.adjvexvv”EdgeishortEdgei.adjvexend1；cost=cost+EdgeishortEdgei.adjvex;coutu最小生成樹代價(jià)為:*costendl;六、程序測(cè)試與實(shí)現(xiàn)1.主程序voidmain()AdjMatGraphg;chara=,A,BVC,DyE,F,G,HVI,J,;RowColWeightrcw=0,4,l,0,U,4,53,0,5,4,l,5,5,6,6,U,7,2,6,8,2,7,9,2,

16、3,10,3,7,11,3,9,12,8,9,13,7,8,14,6,7,15;intn=10,e=15/10個(gè)頂點(diǎn)，15條邊AdjMatCreateGraph(g,a,n,rcw,e);cout當(dāng)前的頂點(diǎn)個(gè)數(shù)為：Hg.numOfVertices()endl;cout”當(dāng)前的邊的條數(shù)為：”vvg.numOfEdgeOendl;g.printMGraph();g.PrimO;2.測(cè)試結(jié)果（999是我自己設(shè)置的無(wú)窮大）S3C:windowssystem32cmd.exe一口L當(dāng)前的頂點(diǎn)亍歛対當(dāng)前的邊的條數(shù)為鄰接拒陣是，0:10=15299999914999999999999207999999599

17、99999999999990109999998999999999999910099999999911999121699999999039999999999994599999930699999999999999989999996015999999999999911999999150149999995999999999999999991401399999999912999999999999130最小生成02TOC o 1-5 h z172100143562g913312杲小生駆代價(jià)為，63請(qǐng)按任意継繼級(jí)中文簡(jiǎn)休)-手心輸人注七、調(diào)試分析圖的鄰接矩陣是一個(gè)n*n的矩陣，所以其空間代價(jià)是O(i?)在求

18、解最小生成樹的過程中，會(huì)不斷的讀取任意兩個(gè)頂點(diǎn)之間邊的權(quán)值，所以采用鄰接矩陣八、遇到的問題及解決辦法在求解利用Pmn求解最小生成樹的過程中，算法能夠看懂，但是利用C+程序去實(shí)現(xiàn)，還是有問題的。最后反復(fù)看代碼，構(gòu)造了一個(gè)最短候選邊集，即數(shù)組shoitEdgen九、心得體會(huì)本次課程設(shè)計(jì)用到了順序表的建立與插入，圖的鄰接矩陣存儲(chǔ)，最終實(shí)現(xiàn)了求n個(gè)城市之間的相同公路之間的最短距離，我主要學(xué)到了將實(shí)際問題轉(zhuǎn)換為自己所學(xué)到的知識(shí)，做到了學(xué)以致用。十、附錄（源代碼）SeqList.h#includeusingnamespacestd;classSeqListprivate:DataTypedataMaxLi

19、stSize;intsize;public:SeqList();intListSize()const;/j&回元素的個(gè)數(shù)sizevoidInsert(constDataType&itemjntpos);在位置pos插入元素item;SeqList:SeqList()size=O;intSeqList:ListSize()constreturnsize;voidSeqList:Insert(constDataType&itemjntpos)/在位置pos插入元素iteminti;if(size=MaxListSize)coutu順序表已滿無(wú)法插入！vvendl;exit(l);_if(possi

20、ze)/當(dāng)pos等于size時(shí)表示插入在最后coutft參數(shù)pos越界出錯(cuò)!,fendl;exit(l);從后向前把前一個(gè)元素遷移到后一個(gè)元素位置直到存儲(chǔ)位置pos為止for(i=size;ipos;i)datai=datai-l;datnpos=item;在pos位置插入itemsize*”/數(shù)據(jù)元素個(gè)數(shù)size加1AdjMatGraphLib.hstructRowColWeight/邊信息三元組introw；intcol；intweight；;voidAdjMatCreateGraph(AdjMatGrapli&GQmtiiTypeV,intn,RowColWeightE,int可/用_個(gè)

21、存儲(chǔ)邊權(quán)信息的三元組來(lái)生成圖inti;for(i=O;in;i+)G.InsertVertex(Vi)；/填充頂點(diǎn)信息for(i=0；i,權(quán)為weightvoidprintMGraph();voidPrimO；;AdjMatGraph:AdjMatGraph(constintsz)/sz是頂點(diǎn)數(shù)p有參構(gòu)造函數(shù)for(inti=O;i.權(quán)為weightif(vlVertices.ListSize()|v2Vertices.ListSize()coutf,參數(shù)vl,y2有誤2nendl;exit(O);Edgevlv2=weight;Edgev2vl=weight;numOfEdges+;void

22、AdjMatGraph:printMGraph()coutn鄰接矩陣是:r,endl；for(inti=0；inumOfVertices()；i+)for(intj=0;jnumOfVerticesO；j+)coutsetw(10)Edgeij;coutendl;coutendl;voidAdjMatGraph:Prim0intk,w,cost=0;for(inti=l；inumOfVerticesO；i+)shortEdgei.lowcost=Edge0i;shortEdgei.adjvex=0；shortEdge0.lowcost=0;for(inti=l；inumOfVerticesO；i+)w=MaxWeight;for(intj=l；jnumOfVerticesO；j+)if(shortEdgej.lowcost!=0&shortEdgej.lowcostw)w=shortEdgej.lowcost;k=j；shortEdgek.lowcost=0;for(intj=l；jnumOfVerticesO；j+)if(EdgekjshortEdgej.lowcost)shortEdgej.l