最小生成樹問題課程設(shè)計(jì)報(bào)告

1、數(shù)據(jù)結(jié)構(gòu)課程設(shè)計(jì)目錄一. 設(shè)計(jì)目的 錯(cuò)誤 !未定義書簽。二. 設(shè)計(jì)內(nèi)容 1三 概要設(shè)計(jì) 11、功能模塊圖 12、各個(gè)模塊詳細(xì)的功能描述 2四詳細(xì)設(shè)計(jì) 31主函數(shù)和其他函數(shù)的偽碼算法 32、主要函數(shù)的程序流程圖 73、函數(shù)之間的調(diào)用關(guān)系圖 15五測試數(shù)據(jù)及運(yùn)行結(jié)果 151正常測試數(shù)據(jù)及運(yùn)行結(jié)果 162、非正常測試數(shù)據(jù)及運(yùn)行結(jié)果 17六調(diào)試情況，設(shè)計(jì)技巧及體會(huì) 18七參考文獻(xiàn) 19八附錄：源代碼 19. 設(shè)計(jì)目的課程設(shè)計(jì)是軟件設(shè)計(jì)的綜合訓(xùn)練， 包括問題分析、 總體結(jié)構(gòu)設(shè)計(jì)、用戶界面設(shè)計(jì)、 程序設(shè)計(jì)基本技能和技巧。 能夠在設(shè)計(jì)中逐步提高程序設(shè)計(jì)能力， 培養(yǎng)科學(xué)的軟 件工作方法。而且通過數(shù)據(jù)結(jié)構(gòu)課程設(shè)

2、計(jì)能夠在下述各方面得到鍛煉：1、能根據(jù)實(shí)際問題的具體情況，結(jié)合數(shù)據(jù)結(jié)構(gòu)課程中的基本理論和基本算 法，正確分析出數(shù)據(jù)的邏輯結(jié)構(gòu)， 合理地選擇相應(yīng)的存儲(chǔ)結(jié)構(gòu)， 并能設(shè)計(jì)出解決 問題的有效算法。2、提高程序設(shè)計(jì)和調(diào)試能力。通過上機(jī)實(shí)習(xí)，驗(yàn)證自己設(shè)計(jì)的算法的正確 性。學(xué)會(huì)有效利用基本調(diào)試方法，迅速找出程序代碼中的錯(cuò)誤并且修改。3、培養(yǎng)算法分析能力。分析所設(shè)計(jì)算法的時(shí)間復(fù)雜度和空間復(fù)雜度，進(jìn)一 步提高程序設(shè)計(jì)水平。二 . 設(shè)計(jì)內(nèi)容最小生成樹問題 :設(shè)計(jì)要求：在 n個(gè)城市之間建設(shè)網(wǎng)絡(luò)， 只需保證連通即可， 求最經(jīng)濟(jì)的架設(shè)方法。 存儲(chǔ)結(jié)構(gòu)采用多種。求解算法多種。三 概要設(shè)計(jì)1、功能模塊圖2、各個(gè)模塊詳細(xì)的功

3、能描述創(chuàng)建一個(gè)圖 ：通過給用戶信息提示，讓用戶將城市信息及城市之間的聯(lián)系 關(guān)系和連接權(quán)值寫入程序，并根據(jù)寫入的數(shù)據(jù)創(chuàng)建成一個(gè)圖。功能選擇 ：給用戶提示信息，讓用戶選擇相應(yīng)功能。 建立鄰接矩陣 ：將用戶輸入的數(shù)據(jù)整理成鄰接矩陣并顯現(xiàn)在屏幕上。建立鄰接表 ： 將用戶輸入的數(shù)據(jù)整理成臨接表并顯現(xiàn)在屏幕上。PRIM 算法 ：利用 PRIM 算法求出圖的最小生成樹，即：城市之間最經(jīng)濟(jì)的 連接方案。四詳細(xì)設(shè)計(jì)1主函數(shù)和其他函數(shù)的偽碼算法主函數(shù)：void main()MGraph G;Dgevalue dgevalue;CreateUDG(G,dgevalue);char u;cout 圖創(chuàng)建成功。 ; c

4、out 請(qǐng)根據(jù)如下菜單選擇操作。 n;cout cout cout cout cout cout int s; char y=y; while(y=y) *endl;*1 、用鄰接矩陣存儲(chǔ)： *endl;*2 、用鄰接表存儲(chǔ)： *endl;*3 、普里姆算法求最經(jīng)濟(jì)的連接方案 *endl;*4 、克魯斯卡爾算法求最經(jīng)濟(jì)的連接方案 *endl; *endlendl;cout 請(qǐng)選擇菜單：s; switch(s) case 1:cout 用鄰接矩陣存儲(chǔ)為： endl;Adjacency_Matrix(G);break;case 2:cout 用鄰接表存儲(chǔ)為： endl;Adjacency_List

5、(G ,dgevalue); break;case 3:cout 普里姆算法最經(jīng)濟(jì)的連接方案為 :endl; coutu;MiniSpanTree_PRIM(G ,u); break;case 4:endl;cout 克魯斯卡爾算法最經(jīng)濟(jì)的連接方案為 MiniSpanTree_KRSL(G ,dgevalue);break;default:cout 您的輸入有誤 !; break;coutendly; if(y=n) break; 鄰接矩陣和臨接表的創(chuàng)建： int CreateUDG(MGraph & G ,Dgevalue & dgevalue) / 構(gòu)造無向加權(quán)圖的鄰接矩陣 int i,j

6、,k; coutG.vexnumG.arcnum;cout 請(qǐng)輸入各個(gè)城市名稱 (分別用一個(gè)字符代替 )：; for(i=0;iG.vexsi;for(i=0;iG .vexnum;+i)/ 初始化數(shù)組 for(j=0;jG .vexnum;+j) G.arcsij.adj=MAX; cout請(qǐng)輸入兩個(gè)城市名稱及其連接費(fèi)用 (嚴(yán)禁連接重復(fù)輸入 !)： endl; for(k=0;k dgevaluek.ch1 dgevaluek.ch2 dgevaluek.value;i = LocateVex(G,dgevaluek.ch1);j = LocateVex(G,dgevaluek.ch2);G

7、.arcsij.adj = dgevaluek.value;G.arcsji.adj = G .arcsij.adj; return OK; 臨接矩陣的輸出： void Adjacency_Matrix(MGraph G) / 用鄰接矩陣存儲(chǔ)數(shù)據(jù)int i,j;for(i=0; iG .vexnum; i+)for(j=0; jG .vexnum; j+) if(G.arcsij.adj=MAX) cout0 ;else coutG.arcsij.adj ;coutendl;鄰接表的輸出：void Adjacency_List(MGraph G,Dgevalue dgevalue) /用鄰接表

8、儲(chǔ)存數(shù)據(jù)int i,j;for(i=0;iG .vexnum;i+)coutG.vexsi;for(j=0;jG .arcnum;j+) if(dgevaluej.ch1=G.vexsi&dgevaluej.ch2!=G .vexsi) coutdgevaluej.ch2;else if(dgevaluej.ch1!=G.vexsi&dgevaluej.ch2=G .vexsi)coutdgevaluej.ch1;coutbb endl;最小生成樹 PRIM 算法 ：void MiniSpanTree_PRIM(MGraph G,char u)/ 普里姆算法求最小生成樹int i,j,k;Cl

9、osedge closedge;k = LocateVex(G,u);for(j=0; jG.vexnum; j+) / 輔助數(shù)組初始化if(j != k)closedgej.adjvex = u;closedgej.lowcost = G.arcskj.adj;closedgek.lowcost = 0;for(i=1; iG.vexnum; i+)k = Minimum(G,closedge);cout 城市 closedgek.adjvex 與城市 G.vexsk 連 接。 endl;closedgek.lowcost = 0;for(j=0; jG.vexnum; +j)if(G.ar

10、cskj.adj closedgej.lowcost)closedgej.adjvex = G.vexsk;closedgej.lowcost= G.arcskj.adj;int Minimum(MGraph G,Closedge closedge) /求 closedge 中權(quán)值最小的邊，并返回其頂點(diǎn)在 vexs 中的位置int i,j;double k = 1000;for(i=0; iG.vexnum; i+)if(closedgei.lowcost != 0 & closedgei.lowcost k)k = closedgei.lowcost;j = i;return j;最小生成樹

11、 kruscal 算法 ：void MiniSpanTree_KRSL(MGraph G ,Dgevalue & dgevalue)/ 克魯斯卡爾算法求最 小生成樹int p1,p2,i,j;int bjMAX_VERTEX_NUM; / 標(biāo)記數(shù)組 for(i=0; iG .vexnum; i+) / 標(biāo)記數(shù)組初始化 bji=i;Sortdge(dgevalue,G);/將所有權(quán)值按從小到大排序 for(i=0; iG .arcnum; i+)p1 = bjLocateVex(G,dgevaluei.ch1);p2 = bjLocateVex(G,dgevaluei.ch2);if(p1 !=

12、 p2) cout 城市 dgevaluei.ch1 與城市 dgevaluei.ch2 連接。 endl;for(j=0; jG .vexnum; j+)if(bjj = p2)bjj = p1;void Sortdge(Dgevalue & dgevalue,MGraph G)/對(duì) dgevalue中各元素按權(quán)值按從小 到大排序int i,j;double temp;char ch1,ch2;for(i=0; iG .arcnum; i+)for(j=i; j dgevaluej.value) temp = dgevaluei.value; dgevaluei.value = dgeval

13、uej.value; dgevaluej.value = temp;ch1 = dgevaluei.ch1; dgevaluei.ch1 = dgevaluej.ch1; dgevaluej.ch1 = ch1;ch2 = dgevaluei.ch2; dgevaluei.ch2 = dgevaluej.ch2; dgevaluej.ch2 = ch2;2、主要函數(shù)的程序流程圖main（）主函數(shù)CreateUDG()switch()Adjacency_Matrix()Adjacency_List()MiniSpanTree_PRIM()MiniSpanTree_KRSL() CreatUDG(

14、) 建圖函數(shù) Adjacency_Matrix() 鄰接矩陣輸出函數(shù) Adjacency_List() 鄰接表輸出函數(shù) MiniSpanTree_PRIM() 普里姆算法：基本思想： 假設(shè) WN=(V,E) 是一個(gè)含有 n 個(gè)頂點(diǎn)的連通網(wǎng)， TV 是 WN 上最小 生成樹中頂點(diǎn)的集合， TE 是最小生成樹中邊的集合。顯然，在算法 執(zhí)行結(jié)束時(shí)， TV=V ，而 TE 是 E 的一個(gè)子集。在算法開始執(zhí)行時(shí)， TE為空集， TV 中只有一個(gè)頂點(diǎn)，因此，按普利姆算法構(gòu)造最小生成 樹的過程為：在所有“其一個(gè)頂點(diǎn)已經(jīng)落在生成樹上，而另一個(gè)頂點(diǎn) 尚未落在生成樹上”的邊中取一條權(quán)值為最小的邊，逐條加在生成樹

15、上，直至生成樹中含有 n-1條邊為止。在此系統(tǒng)中， N 是你所需要輸 入的城市個(gè)數(shù)。 而每條邊的權(quán)值就是你所輸入的每兩個(gè)城市之間的建 設(shè)成本。 MiniSpanTree_KRSL()克魯斯卡爾算法：基本思想： 假設(shè) WN=（V, E ）是一個(gè)含有 N 個(gè)頂點(diǎn)的連通網(wǎng)。 則按照克魯斯 卡爾算法構(gòu)造最小生成樹的過程為：先構(gòu)造一個(gè)只含 n 個(gè)頂點(diǎn)，而邊 集為空的子圖，若將該子圖中各個(gè)頂點(diǎn)看成是各棵樹上的根結(jié)點(diǎn)，則 它是一個(gè)含有 n 棵樹的一個(gè)森林。 之后，從網(wǎng)的邊集 E 中選取一條權(quán) 值最小的邊，若該條邊的兩個(gè)頂點(diǎn)分屬不同的樹，則將其加入子圖， 也就是說，將這兩個(gè)頂點(diǎn)分別所在的兩棵樹合成一棵樹；反之

16、，若該 條邊的兩個(gè)頂點(diǎn)已落在同一棵樹上，則不可取，而應(yīng)該取下一條權(quán)值 最小的邊再試之。依次類推，直到森林中只有一棵樹，也即子圖中含 有 n-1 條邊為止。在此系統(tǒng)中， N 是你所需要輸入的城市個(gè)數(shù)。而每 條邊的權(quán)值就是你所輸入的每兩個(gè)城市之間的建設(shè)成本。 LocateVex （）節(jié)點(diǎn)位置函數(shù)： Minimum() 權(quán)值比較函數(shù)：開始 Sortdge() 權(quán)值排序函數(shù)：i+開始3、函數(shù)之間的調(diào)用關(guān)系圖五測試數(shù)據(jù)及運(yùn)行結(jié)果1正常測試數(shù)據(jù)及運(yùn)行結(jié)果2、非正常測試數(shù)據(jù)及運(yùn)行結(jié)果六調(diào)試情況，設(shè)計(jì)技巧及體會(huì)通過此次課程設(shè)計(jì)，我更深刻地理解了最小生成樹問題，知道如何在 n 個(gè) 城市之間建設(shè)網(wǎng)絡(luò)， 只需保證連

17、通即可， 求最經(jīng)濟(jì)的架設(shè)方法。 并且用了多種求 解方式。數(shù)據(jù)結(jié)構(gòu)是學(xué)習(xí)計(jì)算機(jī)的一門重要的基礎(chǔ)課， 在學(xué)習(xí)數(shù)據(jù)結(jié)構(gòu)之前我們學(xué)習(xí) 了 C 語言在我們看來數(shù)據(jù)結(jié)構(gòu)就是學(xué)習(xí) C 語言的延續(xù)。這幾天的課程設(shè)計(jì)讓 我 充分地體會(huì)到了上機(jī)實(shí)踐對(duì)于計(jì)算機(jī)編程的重要性。 其實(shí)在于計(jì)算機(jī)語言這類課 程看重的就是上機(jī)的實(shí)際操作， 不滿足于基本理論的學(xué)習(xí)。 上機(jī)操作才能讓我們 更加好的掌握我們所要學(xué)習(xí)的計(jì)算機(jī)語言知識(shí)。只顧學(xué)習(xí)理論是遠(yuǎn)遠(yuǎn)不夠的。實(shí)踐中可以發(fā)現(xiàn)許許多多的問題，然后通過 同學(xué)老師的幫助，得以解決，讓自己的編程能力得到極大的提升。此外，也讓我 更加明白編程是要解決現(xiàn)實(shí)問題的。 只有擁有把現(xiàn)實(shí)問題理論化的能力

18、， 才是編 程真正需要達(dá)到的境界。七參考文獻(xiàn)新編 C 語言課程設(shè)計(jì)教程 周二強(qiáng) 編著清華大學(xué)出版社數(shù)據(jù)結(jié)構(gòu)( C 語言版)嚴(yán)蔚敏 吳偉民 編著 清華大學(xué)出版社八附錄：源代碼#include #include #include#define MAX_VERTEX_NUM 20#define OK 1#define ERROR 0#define MAX 1000typedef struct Arcelldouble adj; Arcell,AdjMatrixMAX_VERTEX_NUMMAX_VERTEX_NUM; typedef structchar vexsMAX_VERTEX_NUM; /

19、節(jié)點(diǎn)數(shù)組AdjMatrix arcs; / 鄰接矩陣int vexnum,arcnum; /圖的當(dāng)前節(jié)點(diǎn)數(shù)和弧數(shù)MGraph;typedef struct Pnode /用/ 于普利姆算法char adjvex; /節(jié)點(diǎn)double lowcost; /權(quán)值Pnode,ClosedgeMAX_VERTEX_NUM; / 記錄頂點(diǎn)集 U 到 V-U 的代價(jià)最小的邊 的輔助數(shù)組定義typedef struct Knode /用于克魯斯卡爾算法中存儲(chǔ)一條邊及其對(duì)應(yīng)的 2 個(gè)節(jié)點(diǎn) char ch1; /節(jié)點(diǎn) 1char ch2; /節(jié)點(diǎn) 2double value;/權(quán)值 Knode,Dgevalue

20、MAX_VERTEX_NUM; /int CreateUDG(MGraph & G,Dgevalue & dgevalue); int LocateVex(MGraph G,char ch);int Minimum(MGraph G ,Closedge closedge);void MiniSpanTree_PRIM(MGraph G,char u);void Sortdge(Dgevalue & dgevalue,MGraph G);void Adjacency_Matrix(MGraph G);void Adjacency_List(MGraph G,Dgevalue dgevalue);

21、/int CreateUDG(MGraph & G,Dgevalue & dgevalue) /構(gòu)造無向加權(quán)圖的鄰接矩陣 int i,j,k; coutG.vexnumG.arcnum;cout請(qǐng)輸入各個(gè)城市名稱 (分別用一個(gè)字符代替 )：; for(i=0;iG.vexsi;for(i=0;iG .vexnum;+i)/ 初始化數(shù)組for(j=0;jG.vexnum;+j)G.arcsij.adj=MAX;cout請(qǐng)輸入兩個(gè)城市名稱及其連接費(fèi)用 (嚴(yán)禁連接重復(fù)輸入 !) ：endl; for(k=0;k dgevaluek.ch1 dgevaluek.ch2 dgevaluek.value;

22、i = LocateVex(G,dgevaluek.ch1);j = LocateVex(G,dgevaluek.ch2);G.arcsij.adj = dgevaluek.value;G.arcsji.adj = G .arcsij.adj;return OK;int LocateVex(MGraph G,char ch) /確定節(jié)點(diǎn) ch 在圖 G.vexs 中的位置int a ;for(int i=0; iG .vexnum; i+)if(G.vexsi = ch)a=i;return a;void MiniSpanTree_PRIM(MGraph G,char u)/普里姆算法求最小生

23、成樹int i,j,k;Closedge closedge;k = LocateVex(G,u); for(j=0; jG.vexnum; j+) /輔助數(shù)組初始化if(j != k) closedgej.adjvex = u; closedgej.lowcost = G.arcskj.adj; closedgek.lowcost = 0; for(i=1; iG .vexnum; i+)k = Minimum(G,closedge);cout 城市closedgek.adjvex與城市G.vexsk 連接。 endl;closedgek.lowcost = 0; for(j=0; jG .v

24、exnum; +j) if(G.arcskj.adj closedgej.lowcost) closedgej.adjvex = G.vexsk; closedgej.lowcost= G.arcskj.adj;int Minimum(MGraph G ,Closedge closedge) /求/ closedge中權(quán)值最小的邊， 并返回 其頂點(diǎn)在 vexs 中的位置int i,j;double k = 1000;for(i=0; iG .vexnum; i+)if(closedgei.lowcost != 0 & closedgei.lowcost k)k = closedgei.lowc

25、ost;j = i; return j;void MiniSpanTree_KRSL(MGraph G,Dgevalue & dgevalue)/克魯斯卡爾算法求最 小生成樹int p1,p2,i,j;int bjMAX_VERTEX_NUM; / 標(biāo)記數(shù)組for(i=0; iG .vexnum; i+) / 標(biāo)記數(shù)組初始化 bji=i;Sortdge(dgevalue,G);/將所有權(quán)值按從小到大排序for(i=0; iG .arcnum; i+)p1 = bjLocateVex(G,dgevaluei.ch1);p2 = bjLocateVex(G,dgevaluei.ch2); if(p

26、1 != p2)cout 城市dgevaluei.ch1 與城市 dgevaluei.ch2 連接。 endl;for(j=0; jG .vexnum; j+)if(bjj = p2)bjj = p1;void Sortdge(Dgevalue & dgevalue,MGraph G)/對(duì) dgevalue中各元素按權(quán)值按從小 到大排序int i,j;double temp;char ch1,ch2;for(i=0; iG .arcnum; i+)for(j=i; j dgevaluej.value)temp = dgevaluei.value; dgevaluei.value = dgevaluej.value; dgevaluej.value = temp;ch1 = dgevaluei.ch1; dgevaluei.ch1 = dgevaluej.ch1; dgevaluej.ch1 = ch1;ch2 = dgevaluei.ch2; dgevaluei.ch2 = dgevaluej.ch2; dgevaluej.ch2 = ch2;void Adjacency_Matrix(MGraph G) /用鄰接矩陣存儲(chǔ)數(shù)據(jù)int i,j;for(i=0; iG .vexnum; i+)for(j=0; jG .vexnum; j+) if(G.arcsij.adj=MAX)