1、數據結構課程設計題目二：最小生成樹的構建學院：xxxxxxxxxxx班級：XXXXXXXXXXX學號：xxxxxxxxxxx姓名：xxxxxxxxxxx設計時間：xxxxxxxxxxx目錄：TOC o 1-5 h z1.需求分析12.課題設計內容1 HYPERLINK l bookmark8課程設計基本流程1詳細設計說明1界面操作流程圖：2主要程序3運行結果截圖53.得意之處6 HYPERLINK l bookmark124.設計實踐過程中的收獲與體會6 HYPERLINK l bookmark145.設計目前存在的問題76.主要參考文獻7、需求分析本課程主要是完成一個最小生成樹的構建，要求用

2、克魯斯卡爾算法或者普利姆算法求網的最小生成樹(此程序我用的是普利姆算法)，并輸出各條邊及他們的權值。要求用戶在使用時可以準確輸入頂點及每個頂點的關系，運算出可以建立的關系網，最后利用普利姆算法準確輸出最短路徑。、課程設計內容1、課程設計基本流程：關于此課程的設計，是從設計要求入手的。根據對知識的掌握程度，我選擇了用普利姆算法進行設計。根據實驗要求，我定義了一個prims類，在類中定義一個私有成員函數和一個公有成員函數。定義相關變量和相關函數，并完善程序。2、詳細設計說明：首先在私有成員private中定義節點個數n、圖中邊的個數g，樹的邊的個數t，源節點s。定義二維數組graph_edge99

3、4和tree_edge994，分別為圖的邊和樹的邊。因為普利姆算法是把圖分為兩部分進行運算，所以我定義了Tl50,tl為第一部分，T250,t2為第二部分。在公有成員public中定義輸入函數input()、算法函數algorithm()、輸出函數output()。3322在input中進行界面的設計，定義圖中邊的個數g的初始值為0,利用for循環實現邊的權值的輸入，嵌套if語句定義圖的頂點i,j；邊的權值w。用for循環完成圖中可以建立關系網的輸出。在algorithm中構造算法，將圖的兩部分進行運算，利用while循環找出最短路徑，其中嵌套for循環和if語句。在output中打印挑選出的

4、邊及其對應的權值。最后,設計主函數并完善界面。3、界面操作流程圖：4、主要程序：#includeclassprimsprivate:intn;/節點的個數intgraph_edge994;/圖的邊intg;/圖中邊的個數inttree_edge994;/樹的邊intt;/樹的邊的個數ints;/源節點/把圖分成兩個部分intT150,t1;/第一部分intT250,t2;/第二部分public:voidinput();intfindset(int);voidalgorithm();voidoutput();voidprims:input()cout*nn;g=0;/圖中邊的個數初始值為0cou

5、t輸入邊的權值：n;for(inti=1;i=n;i+)for(intj=i+1;j=n;j+)couti,j：;intw;5544cinw;if(w!=0)g+;graph_edgegl=i;/定義圖的頂點igraph_edgeg2=j;/定義圖的頂點jgraph_edgeg3=w;/定義邊的權值w/輸出圖的邊coutnn圖中頂點可以建立的關系網：n;for(i=l;iendl;intprims：findset(intx)for(inti=l;i=tl;i+)if(x=Tli)returnl;for(i=l;it2;i+)if(x=T2i)return2;return-l;voidprims

6、:algorithm()/構造算法t=0;/初始化邊的個數為0tl=l;Tll=l;/資源節點t2=n-l;inti;for(i=l;i=n-l;i+)T2i=i+1;coutnn*運算開始*nnn;while(g!=0&t!=n-1)/找出最短路徑intmin=99;intp;intu,v,w;for(i=1;i=g;i+)if(findset(graph_edgei1)!=findset(graph_edgei2)/如果u和v在不同的部分if(mingraph_edgei3)min=graph_edgei3;u=graph_edgei1;v=graph_edgei2;w=graph_edg

7、ei3;p=i;/刪除圖的邊for(intl=p;lg;l+)graph_edgel1=graph_edgel+11;graph_edgel2=graph_edgel+12;graph_edgel3=graph_edgel+13;/增加樹的邊t+;tree_edget1=u;tree_edget2=v;tree_edget3=w; voidprims:output()cout挑選出的邊及其對應的權值：n；for(inti=l;i二t;i+)couttree_edgei1，tree_edgei2:tree_edgei3endl;intmain()primsobj;obj.input();obj.

8、algorithm();obj.output。；return0;5、運彳丁結果截圖：，-E:僅件;字刁舊己詼懾小主壓列的枸逞Dcbug儲小主咸訶旳構崔啟曲卄比運算開始卄“：=1：2卄比運算開始卄“：=1：2ressanvkeytocontinueJtWMKMMKMMMMMKMKMM傅用MMMMMXMMMKMMMKMKMMMXMX*占甲丈目尋j學|H各比址址at址ttx*光開址at直社112數個值的權戸的頂邊三、得意之處這次課程設計的課題雖然比較簡單，但是每個函數的編寫都花了很大的心思。之前有去過之前有去過圖書館查資料、也上網看到了一些，但有很多地方還是不太明白，有些語句通過自己能理解的方式進行

9、了改進，比如for循環語句和if語句的編寫等。在編寫過程中，比較得意的地方還是用普利姆算法將圖分為兩個部分的代碼的編寫，還有可以準確的顯示可以建立的關系網，當運行出現bug后，自己又認真修改，解決問題，心情非常喜悅。另外，我最滿意的地方就是在運算完成后，可以準確的輸出最短路徑及其對應的權值，整個界面設計的簡單但不失美觀同時方便用戶的使用，增加了友好性。四、設計實踐過程中的收獲與體會這一星期的課程設計中確實讓我增長了不少，也發現自己對于數據結構的知識掌握不夠，學得不夠好。自己上網看了一些程序，但都不太懂，而且都是用C語言編寫的，所以，我去圖書館查了些資料，還是很有幫助的。對于if語句、for循環語句和while語句我還是查了查C+的書一點一點修改的。其中有一些句子是照著參考資料寫的，自己也不太懂。但是經過努力和同學的幫助還是總算沒有bug了。五、設計目前存在的問題目前這個程序還有很