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

1、 PAGE24 / NUMPAGES25 數(shù)據(jù)結(jié)構(gòu)課程設(shè)計(jì)目錄 TOC o 1-3 h z u HYPERLINK l _Toc376363708一. 設(shè)計(jì)目的 PAGEREF _Toc376363708 h 2HYPERLINK l _Toc376363709二. 設(shè)計(jì)內(nèi)容 PAGEREF _Toc376363709 h 2HYPERLINK l _Toc376363710三概要設(shè)計(jì) PAGEREF _Toc376363710 h 1HYPERLINK l _Toc3763637111、功能模塊圖 PAGEREF _Toc376363711 h 1HYPERLINK l _Toc376363

2、7122、各個(gè)模塊詳細(xì)的功能描述 PAGEREF _Toc376363712 h 1HYPERLINK l _Toc376363713四詳細(xì)設(shè)計(jì) PAGEREF _Toc376363713 h 2HYPERLINK l _Toc3763637141主函數(shù)和其他函數(shù)的偽碼算法 PAGEREF _Toc376363714 h 2HYPERLINK l _Toc3763637152、主要函數(shù)的程序流程圖 PAGEREF _Toc376363715 h 6HYPERLINK l _Toc3763637163、函數(shù)之間的調(diào)用關(guān)系圖 PAGEREF _Toc376363716 h 13HYPERLINK

3、l _Toc376363717五測(cè)試數(shù)據(jù)及運(yùn)行結(jié)果 PAGEREF _Toc376363717 h 14HYPERLINK l _Toc3763637181正常測(cè)試數(shù)據(jù)及運(yùn)行結(jié)果 PAGEREF _Toc376363718 h 14HYPERLINK l _Toc3763637192、非正常測(cè)試數(shù)據(jù)及運(yùn)行結(jié)果 PAGEREF _Toc376363719 h 15HYPERLINK l _Toc376363720六調(diào)試情況，設(shè)計(jì)技巧及體會(huì) PAGEREF _Toc376363720 h 17HYPERLINK l _Toc376363721七參考文獻(xiàn) PAGEREF _Toc376363721

4、h 17HYPERLINK l _Toc376363722八附錄：源代碼 PAGEREF _Toc376363722 h 17一. 設(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è)計(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)試方法，迅速找出

5、程序代碼中的錯(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、功能模塊圖開始創(chuàng)建一個(gè)圖功能選擇1.建立鄰接矩陣2.建立鄰接表3. PRIM算法4.kruscal算法結(jié)束2、各個(gè)模塊詳細(xì)的功能描述創(chuàng)建一個(gè)圖：通過給用戶信息提示，讓用戶將城市信息及城市之間的聯(lián)系關(guān)系和連接權(quán)值寫入程序，并根據(jù)寫入的數(shù)據(jù)創(chuàng)建成一個(gè)圖。功能選擇：給用戶提示信息，讓用戶選擇相應(yīng)功能。建立鄰接矩陣：將用戶輸入的數(shù)據(jù)整理成鄰接矩陣并

6、顯現(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)建成功。; cout請(qǐng)根據(jù)如下菜單選擇操作。n; cout *endl; cout *1、用鄰接矩陣存儲(chǔ)：*endl; cout *2、用鄰接表存儲(chǔ)：*endl; cout *3、普里姆算法求最經(jīng)濟(jì)的連接方案*endl; cout *4、克魯斯卡爾

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

8、:endl; 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,k; coutG.vexnumG.arum; cout請(qǐng)輸入各個(gè)城市名稱(分別用一個(gè)字符代替)：; for(i=0;iG.vexsi; for(i=0;iG.vexnum;+i)/初始化數(shù)組 for(j=0;jG.vexnum;+j) G.

9、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.arcsij.adj = dgevaluek.value; G.arcsji.adj = G.arcsij.adj; return OK; 臨接矩陣的輸出：void Adjacency_Matrix(MGraph G) /用鄰接矩陣存儲(chǔ)數(shù)據(jù)int i,

10、j;for(i=0; iG.vexnum; i+) for(j=0; jG.vexnum; j+) if(G.arcsij.adj=MAX)cout0 ; elsecoutG.arcsij.adj ; coutendl; 鄰接表的輸出： void Adjacency_List(MGraph G,Dgevalue dgevalue) /用鄰接表儲(chǔ)存數(shù)據(jù)int i,j;for(i=0;iG.vexnum;i+)coutG.vexsi;for(j=0;jG.arum;j+)if(dgevaluej.ch1=G.vexsi&dgevaluej.ch2!=G.vexsi)coutdgevaluej.ch

11、2;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; Closedge closedge; k = LocateVex(G,u); for(j=0; jG.vexnum; j+) /輔助數(shù)組初始化 if(j != k) closedgej.adjvex = u; closedgej.lowcost = G.arcskj.adj;

12、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.arcskj.adj closedgej.lowcost) closedgej.adjvex = G.vexsk; closedgej.lowcost= G.arcskj.adj; int Minimum(MGraph G,Closedge closedge) /求c

13、losedge中權(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; 最小生成樹kruscal算法：void MiniSpanTree_KRSL(MGraph G,Dgevalue & dgevalue)/克魯斯卡爾算法求最小生成樹 int p1,p2,i,j; int bjMAX_VERTEX_NUM; /標(biāo)記數(shù)組 for(i

14、=0; iG.vexnum; i+) /標(biāo)記數(shù)組初始化 bji=i; Sortdge(dgevalue,G);/將所有權(quán)值按從小到大排序 for(i=0; iG.arum; i+) p1 = bjLocateVex(G,dgevaluei.ch1); p2 = bjLocateVex(G,dgevaluei.ch2); if(p1 != p2) cout 城市dgevaluei.ch1與城市dgevaluei.ch2連接。endl; for(j=0; jG.vexnum; j+) if(bjj = p2) bjj = p1; void Sortdge(Dgevalue & dgevalue,M

15、Graph G)/對(duì)dgevalue中各元素按權(quán)值按從小到大排序 int i,j; double temp; char ch1,ch2; for(i=0; iG.arum; 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; dgev

16、aluei.ch2 = dgevaluej.ch2; dgevaluej.ch2 = ch2; 2、主要函數(shù)的程序流程圖main（）主函數(shù)CreatUDG()建圖函數(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è)頂

17、點(diǎn)已經(jīng)落在生成樹上，而另一個(gè)頂點(diǎn)尚未落在生成樹上”的邊中取一條權(quán)值為最小的邊，逐條加在生成樹上，直至生成樹中含有n-1條邊為止。在此系統(tǒng)中，N是你所需要輸入的城市個(gè)數(shù)。而每條邊的權(quán)值就是你所輸入的每?jī)蓚€(gè)城市之間的建設(shè)成本。開始標(biāo)志頂點(diǎn)1加入U(xiǎn)集合尋找滿足邊的一個(gè)頂點(diǎn)在U,另一個(gè)頂點(diǎn)在V的最小邊形成n-1條邊的生成樹頂點(diǎn)k加入U(xiǎn)修改由頂點(diǎn)k到其他頂點(diǎn)邊的權(quán)值結(jié)束得到最小生成樹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)看成

18、是各棵樹上的根結(jié)點(diǎn)，則它是一個(gè)含有n棵樹的一個(gè)森林。之后，從網(wǎng)的邊集E中選取一條權(quán)值最小的邊，若該條邊的兩個(gè)頂點(diǎn)分屬不同的樹，則將其加入子圖，也就是說，將這兩個(gè)頂點(diǎn)分別所在的兩棵樹合成一棵樹；反之，若該條邊的兩個(gè)頂點(diǎn)已落在同一棵樹上，則不可取，而應(yīng)該取下一條權(quán)值最小的邊再試之。依次類推，直到森林中只有一棵樹，也即子圖中含有n-1條邊為止。在此系統(tǒng)中，N是你所需要輸入的城市個(gè)數(shù)。而每條邊的權(quán)值就是你所輸入的每?jī)蓚€(gè)城市之間的建設(shè)成本。LocateVex（）節(jié)點(diǎn)位置函數(shù)：Minimum()權(quán)值比較函數(shù)：Sortdge()權(quán)值排序函數(shù)：3、函數(shù)之間的調(diào)用關(guān)系圖五測(cè)試數(shù)據(jù)及運(yùn)行結(jié)果1正常測(cè)試數(shù)據(jù)及運(yùn)行結(jié)

19、果2、非正常測(cè)試數(shù)據(jù)及運(yùn)行結(jié)果六調(diào)試情況，設(shè)計(jì)技巧及體會(huì)通過此次課程設(shè)計(jì)，我更深刻地理解了最小生成樹問題，知道如何在n個(gè)城市之間建設(shè)網(wǎng)絡(luò)，只需保證連通即可，求最經(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é)老師的幫助，得以解

20、決，讓自己的編程能力得到極大的提升。此外，也讓我更加明白編程是要解決現(xiàn)實(shí)問題的。只有擁有把現(xiàn)實(shí)問題理論化的能力，才是編程真正需要達(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 1000 typedef struct Arcell double adj; Arcell,AdjMatrixMAX_VERTEX_NUMMAX_VE

21、RTEX_NUM; typedef struct char vexsMAX_VERTEX_NUM; /節(jié)點(diǎn)數(shù)組 AdjMatrix arcs; /鄰接矩陣 int vexnum,arum; /圖的當(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)1

22、char ch2; /節(jié)點(diǎn)2 double value;/權(quán)值 Knode,DgevalueMAX_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

23、G);void Adjacency_List(MGraph G,Dgevalue dgevalue);/- int CreateUDG(MGraph & G,Dgevalue & dgevalue) /構(gòu)造無向加權(quán)圖的鄰接矩陣 int i,j,k; coutG.vexnumG.arum; 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

24、=0;k dgevaluek.ch1 dgevaluek.ch2 dgevaluek.value; 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; retu

25、rn a; void MiniSpanTree_PRIM(MGraph G,char u)/普里姆算法求最小生成樹 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.adj

26、vex與城市G.vexsk連接。endl; closedgek.lowcost = 0; for(j=0; jG.vexnum; +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(closedge

27、i.lowcost != 0 & closedgei.lowcost k) k = closedgei.lowcost; 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.arum; i+) p1 = bjLocateVex

28、(G,dgevaluei.ch1); p2 = bjLocateVex(G,dgevaluei.ch2); if(p1 != 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.arum; i+) for(j=i; j dgeva

29、luej.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; i