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

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

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

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

5、t輸入邊的權(quán)值：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;/定義邊的權(quán)值w/輸出圖的邊coutnn圖中頂點可以建立的關(guān)系網(wǎng)：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()/構(gòu)造算法t=0;/初始化邊的個數(shù)為0tl=l;Tll=l;/資源節(jié)點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;/刪除圖的邊f(xié)or(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挑選出的邊及其對應(yīng)的權(quán)值：n；for(inti=l;i二t;i+)couttree_edgei1，tree_edgei2:tree_edgei3endl;intmain()primsobj;obj.input();obj.

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

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