數(shù)據(jù)結(jié)構(gòu)課程設(shè)計(jì)最小生成樹的構(gòu)建實(shí)驗(yàn)報(bào)告

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

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

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

4、邊及其對(duì)應(yīng)的權(quán)值。最后,設(shè)計(jì)主函數(shù)并完善界面。3、界面操作流程圖：4、主要程序：#includeclassprimsprivate:intn;/節(jié)點(diǎn)的個(gè)數(shù)intgraph_edge994;/圖的邊intg;/圖中邊的個(gè)數(shù)inttree_edge994;/樹的邊intt;/樹的邊的個(gè)數(shù)ints;/源節(jié)點(diǎn)/把圖分成兩個(gè)部分intT150,t1;/第一部分intT250,t2;/第二部分public:voidinput();intfindset(int);voidalgorithm();voidoutput();voidprims:input()cout*nn;g=0;/圖中邊的個(gè)數(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;/定義圖的頂點(diǎn)igraph_edgeg2=j;/定義圖的頂點(diǎn)jgraph_edgeg3=w;/定義邊的權(quán)值w/輸出圖的邊coutnn圖中頂點(diǎn)可以建立的關(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;/初始化邊的個(gè)數(shù)為0tl=l;Tll=l;/資源節(jié)點(diǎn)t2=n-l;inti;for(i=l;i=n-l;i+)T2i=i+1;coutnn*運(yùn)算開始*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挑選出的邊及其對(duì)應(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、運(yùn)彳丁結(jié)果截圖：，-E:僅件;字刁舊己詼懾小主壓列的枸逞Dcbug儲(chǔ)小主咸訶旳構(gòu)崔啟曲卄比運(yùn)算開始卄“：=1：2卄比運(yùn)算開始卄“：=1：2ressanvkeytocontinueJtWMKMMKMMMMMKMKMM傅用MMMMMXMMMKMMMKMKMMMXMX*占甲丈目尋j學(xué)|H各比址址at址ttx*光開址at直社112數(shù)個(gè)值的權(quán)戸的頂邊三、得意之處這次課程設(shè)計(jì)的課題雖然比較簡(jiǎn)單，但是每個(gè)函數(shù)的編寫都花了很大的心思。之前有去過之前有去過圖書館查資料、也上網(wǎng)看到了一些，但有很多地方還是不太明白，有些語句通過自己能理解的方式進(jìn)行

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