數(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班級：XXXXXXXXXXX學(xué)號：XXXXXXXXXXX姓名：XXXXXXXXXXX設(shè)計(jì)時(shí)間： XXXXXXXXXXX目錄：1. 需求分析- 12. 課題設(shè)計(jì)內(nèi)容- 1(1)課程設(shè)計(jì)基本流程- 1 (2)詳細(xì)設(shè)計(jì)說明- 1 (3)界面操作流程圖：- 2 (4)主要程序- 3(5)運(yùn)行結(jié)果截圖- 53.得意之處- 64.設(shè)計(jì)實(shí)踐過程中的收獲與體會- 65.設(shè)計(jì)目前存在的問題- 76.主要參考文獻(xiàn)- 7 一、 需求分析 本課程主要是完成一個(gè)最小生成樹的構(gòu)建，要求用克魯斯卡爾算法或者普利姆算法求網(wǎng)的最小生成樹（此程序我用的是普利姆

2、算法），并輸出各條邊及他們的權(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ù)對知識的掌握程度，我選擇了用普利姆算法進(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_edge994和tree_edge994，分別為圖的邊和樹的邊。因?yàn)槠?/p>

3、利姆算法是把圖分為兩部分進(jìn)行運(yùn)算，所以我定義了T150,t1為第一部分， T250,t2為第二部分。在公有成員public中定義輸入函數(shù)input ()、算法函數(shù)algorithm()、輸出函數(shù)output()。 1在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中打印挑選出的邊及其對應(yīng)的權(quán)值。最后，設(shè)計(jì)主函數(shù)并完善界面。3、 界面操

4、作流程圖：菜單輸入頂點(diǎn)個(gè)數(shù)n輸入邊的權(quán)值w輸出挑出的邊及其對應(yīng)的權(quán)值顯示關(guān)系網(wǎng) 24、 主要程序：#includeclass primsprivate:int n; /節(jié)點(diǎn)的個(gè)數(shù)int graph_edge994; /圖的邊int g; /圖中邊的個(gè)數(shù)int tree_edge994; /樹的邊int t; /樹的邊的個(gè)數(shù)int s; /源節(jié)點(diǎn)/把圖分成兩個(gè)部分int T150,t1; / 第一部分int T250,t2; /第二部分public:void input();int findset(int);void algorithm();void output();void prims:in

5、put()cout*nendl;cout*歡迎使用*endl;cout*普里姆算法運(yùn)算*n;cout*n;coutn;g=0;/圖中邊的個(gè)數(shù)初始值為0cout輸入邊的權(quán)值 :n;for(int i=1;i=n;i+)for(int j=i+1;j=n;j+)cout i , j :;int w; 3cinw;if(w!=0)g+;graph_edgeg1=i;/定義圖的頂點(diǎn)igraph_edgeg2=j;/定義圖的頂點(diǎn)jgraph_edgeg3=w;/定義邊的權(quán)值w/輸出圖的邊coutnn圖中頂點(diǎn)可以建立的關(guān)系網(wǎng):n;for(i=1;i=g;i+)cout graph_edgei1 , gra

6、ph_edgei2 endl;int prims:findset(int x)for(int i=1;i=t1;i+)if(x=T1i)return 1;for(i=1;it2;i+)if(x=T2i)return 2;return -1;void prims:algorithm()/構(gòu)造算法t=0;/初始化邊的個(gè)數(shù)為0t1=1;T11=1; /資源節(jié)點(diǎn)t2=n-1;int i;for(i=1;i=n-1;i+) 4T2i=i+1; coutnn*運(yùn)算開始*nnn;while(g!=0 & t!=n-1)/ 找出最短路徑int min=99;int p;int u,v,w;for(i=1;ig

7、raph_edgei3)min=graph_edgei3;u=graph_edgei1;v=graph_edgei2;w=graph_edgei3;p=i;/刪除圖的邊f(xié)or(int l=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; 5void prims:output()cout挑選出的邊及其對應(yīng)的權(quán)值:n;for(int i=1;i=t;i+)cout

8、tree_edgei1,tree_edgei2 :tree_edgei3endl;int main()prims obj;obj.input();obj.algorithm();obj.output();return 0;5、 運(yùn)行結(jié)果截圖： 5三、 得意之處這次課程設(shè)計(jì)的課題雖然比較簡單，但是每個(gè)函數(shù)的編寫都花了很大的心思。之前有去過之前有去過圖書館查資料、也上網(wǎng)看到了一些，但有很多地方還是不太明白，有些語句通過自己能理解的方式進(jìn)行了改進(jìn)，比如for循環(huán)語句和if語句的編寫等。在編寫過程中，比較得意的地方還是用普利姆算法將圖分為兩個(gè)部分的代碼的編寫，還有可以準(zhǔn)確的顯示可以建立的關(guān)系網(wǎng)，當(dāng)運(yùn)行

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