最小生成樹問題課程設(shè)計報告1

1、數(shù)據(jù)結(jié)構(gòu)課程設(shè)計報告專 業(yè)： 軟件工程題 目： 最小生成樹問題 目錄一. 設(shè)計目的2二. 設(shè)計內(nèi)容2三概要設(shè)計11、功能模塊圖12、各個模塊詳細的功能描述1四詳細設(shè)計21主函數(shù)和其他函數(shù)的偽碼算法22、主要函數(shù)的程序流程圖63、函數(shù)之間的調(diào)用關(guān)系圖13五測試數(shù)據(jù)及運行結(jié)果141正常測試數(shù)據(jù)及運行結(jié)果142、非正常測試數(shù)據(jù)及運行結(jié)果15六調(diào)試情況，設(shè)計技巧及體會17七參考文獻17八附錄：源代碼1724一. 設(shè)計目的課程設(shè)計是軟件設(shè)計的綜合訓練，包括問題分析、總體結(jié)構(gòu)設(shè)計、用戶界面設(shè)計、程序設(shè)計基本技能和技巧。能夠在設(shè)計中逐步提高程序設(shè)計能力，培養(yǎng)科學的軟件工作方法。而且通過數(shù)據(jù)結(jié)構(gòu)課程設(shè)計能夠在

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

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

4、e); char u; cout圖創(chuàng)建成功。; cout請根據(jù)如下菜單選擇操作。n; cout *endl; cout *1、用鄰接矩陣存儲：*endl; cout *2、用鄰接表存儲：*endl; cout *3、普里姆算法求最經(jīng)濟的連接方案*endl; cout *4、克魯斯卡爾算法求最經(jīng)濟的連接方案*endl; cout *endlendl; int s; char y=y; while(y=y) cout請選擇菜單：s; switch(s) case 1: cout用鄰接矩陣存儲為：endl; adjacency_matrix(g); break; case 2: cout用鄰接表存儲

5、為：endl; adjacency_list(g,dgevalue); break; case 3: cout普里姆算法最經(jīng)濟的連接方案為:endl; coutu; minispantree_prim(g,u); break; case 4: cout克魯斯卡爾算法最經(jīng)濟的連接方案為:endl; minispantree_krsl(g,dgevalue); break; default: cout您的輸入有誤!; break; coutendly; if(y=n) break; 鄰接矩陣和臨接表的創(chuàng)建：int createudg(mgraph & g,dgevalue & dgevalue)

6、/構(gòu)造無向加權(quán)圖的鄰接矩陣 int i,j,k; coutg.vexnumg.arcnum; cout請輸入各個城市名稱(分別用一個字符代替)：; for(i=0;ig.vexsi; for(i=0;ig.vexnum;+i)/初始化數(shù)組 for(j=0;jg.vexnum;+j) g.arcsij.adj=max; cout請輸入兩個城市名稱及其連接費用(嚴禁連接重復輸入!)：endl; for(k=0;k dgevaluek.ch1 dgevaluek.ch2 dgevaluek.value; i = locatevex(g,dgevaluek.ch1); j = locatevex(g,

7、dgevaluek.ch2); g.arcsij.adj = dgevaluek.value; g.arcsji.adj = g.arcsij.adj; return ok; 臨接矩陣的輸出： void adjacency_matrix(mgraph g) /用鄰接矩陣存儲數(shù)據(jù)int i,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,dgevalu

8、e dgevalue) /用鄰接表儲存數(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

9、 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(shù).vexsk連接。endl; closedgek.lowcost = 0; for(j=0; jg.vexn

10、um; +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)值最小的邊，并返回其頂點在vexs中的位置 int i,j; double k = 1000; for(i=0; ig.vexnum; i+) if(closedgei.lowcost != 0 & closedgei.lowcost k) k = closedgei.lowcost;

11、j = i; return j; 最小生成樹kruscal算法：void minispantree_krsl(mgraph g,dgevalue & dgevalue)/克魯斯卡爾算法求最小生成樹 int p1,p2,i,j; int bjmax_vertex_num; /標記數(shù)組 for(i=0; ig.vexnum; i+) /標記數(shù)組初始化 bji=i; sortdge(dgevalue,g);/將所有權(quán)值按從小到大排序 for(i=0; ig.arcnum; i+) p1 = bjlocatevex(g,dgevaluei.ch1); p2 = bjlocatevex(g,dgeval

12、uei.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)/對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; dgeval

13、uei.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; 2、主要函數(shù)的程序流程圖 main（）主函數(shù)creatudg()建圖函數(shù)adjacency_matrix()鄰接矩陣輸出函數(shù) adjacency_list()鄰接表輸出函數(shù)minispantree_pr

14、im()普里姆算法：基本思想： 假設(shè)wn=(v,e)是一個含有n個頂點的連通網(wǎng)，tv是wn上最小生成樹中頂點的集合，te是最小生成樹中邊的集合。顯然，在算法執(zhí)行結(jié)束時，tv=v，而te是e的一個子集。在算法開始執(zhí)行時，te為空集，tv中只有一個頂點，因此，按普利姆算法構(gòu)造最小生成樹的過程為：在所有“其一個頂點已經(jīng)落在生成樹上，而另一個頂點尚未落在生成樹上”的邊中取一條權(quán)值為最小的邊，逐條加在生成樹上，直至生成樹中含有n-1條邊為止。在此系統(tǒng)中，n是你所需要輸入的城市個數(shù)。而每條邊的權(quán)值就是你所輸入的每兩個城市之間的建設(shè)成本。開始標志頂點1加入u集合尋找滿足邊的一個頂點在u,另一個頂點在v的最小

15、邊形成n-1條邊的生成樹頂點k加入u修改由頂點k到其他頂點邊的權(quán)值結(jié)束得到最小生成樹minispantree_krsl()克魯斯卡爾算法： 基本思想： 假設(shè)wn=（v, e）是一個含有n個頂點的連通網(wǎng)。則按照克魯斯卡爾算法構(gòu)造最小生成樹的過程為：先構(gòu)造一個只含n個頂點，而邊集為空的子圖，若將該子圖中各個頂點看成是各棵樹上的根結(jié)點，則它是一個含有n棵樹的一個森林。之后，從網(wǎng)的邊集e中選取一條權(quán)值最小的邊，若該條邊的兩個頂點分屬不同的樹，則將其加入子圖，也就是說，將這兩個頂點分別所在的兩棵樹合成一棵樹；反之，若該條邊的兩個頂點已落在同一棵樹上，則不可取，而應(yīng)該取下一條權(quán)值最小的邊再試之。依次類推，

16、直到森林中只有一棵樹，也即子圖中含有n-1條邊為止。在此系統(tǒng)中，n是你所需要輸入的城市個數(shù)。而每條邊的權(quán)值就是你所輸入的每兩個城市之間的建設(shè)成本。locatevex（）節(jié)點位置函數(shù)： minimum()權(quán)值比較函數(shù)： sortdge()權(quán)值排序函數(shù)：3、函數(shù)之間的調(diào)用關(guān)系圖五測試數(shù)據(jù)及運行結(jié)果 1正常測試數(shù)據(jù)及運行結(jié)果2、非正常測試數(shù)據(jù)及運行結(jié)果六調(diào)試情況，設(shè)計技巧及體會通過此次課程設(shè)計，我更深刻地理解了最小生成樹問題，知道如何在n個城市之間建設(shè)網(wǎng)絡(luò)，只需保證連通即可，求最經(jīng)濟的架設(shè)方法。并且用了多種求解方式。數(shù)據(jù)結(jié)構(gòu)是學習計算機的一門重要的基礎(chǔ)課，在學習數(shù)據(jù)結(jié)構(gòu)之前我們學習了c語言在我們看來

17、數(shù)據(jù)結(jié)構(gòu)就是學習c語言的延續(xù)。這幾天的課程設(shè)計讓 我充分地體會到了上機實踐對于計算機編程的重要性。其實在于計算機語言這類課程看重的就是上機的實際操作，不滿足于基本理論的學習。上機操作才能讓我們更加好的掌握我們所要學習的計算機語言知識。只顧學習理論是遠遠不夠的。實踐中可以發(fā)現(xiàn)許許多多的問題，然后通過同學老師的幫助，得以解決，讓自己的編程能力得到極大的提升。此外，也讓我更加明白編程是要解決現(xiàn)實問題的。只有擁有把現(xiàn)實問題理論化的能力，才是編程真正需要達到的境界。七參考文獻新編c語言課程設(shè)計教程 周二強 編著 清華大學出版社數(shù)據(jù)結(jié)構(gòu)（c語言版） 嚴蔚敏 吳偉民 編著 清華大學出版社八附錄：源代碼#in

18、clude #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_vertex_num; typedef struct char vexsmax_vertex_num; /節(jié)點數(shù)組 adjmatrix arcs; /鄰接矩陣 int vexnum,arcnum; /圖的當前節(jié)點數(shù)和弧數(shù) mgraph; typedef struct pn

19、ode /用于普利姆算法 char adjvex; /節(jié)點 double lowcost; /權(quán)值 pnode,closedgemax_vertex_num; /記錄頂點集u到v-u的代價最小的邊的輔助數(shù)組定義 typedef struct knode /用于克魯斯卡爾算法中存儲一條邊及其對應(yīng)的2個節(jié)點 char ch1; /節(jié)點1 char ch2; /節(jié)點2 double value;/權(quán)值 knode,dgevaluemax_vertex_num; /- int createudg(mgraph & g,dgevalue & dgevalue); int locatevex(mgraph

20、 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);/- int createudg(mgraph & g,dgevalue & dgevalue) /構(gòu)造無向加權(quán)圖的鄰接矩陣 int i,j,k; coutg.v

21、exnumg.arcnum; cout請輸入各個城市名稱(分別用一個字符代替)：; for(i=0;ig.vexsi; for(i=0;ig.vexnum;+i)/初始化數(shù)組 for(j=0;jg.vexnum;+j) g.arcsij.adj=max; cout請輸入兩個城市名稱及其連接費用(嚴禁連接重復輸入!)：endl; for(k=0;k dgevaluek.ch1 dgevaluek.ch2 dgevaluek.value; i = locatevex(g,dgevaluek.ch1); j = locatevex(g,dgevaluek.ch2); g.arcsij.adj = d

22、gevaluek.value; g.arcsji.adj = g.arcsij.adj; return ok; int locatevex(mgraph g,char ch) /確定節(jié)點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)/普里姆算法求最小生成樹 int i,j,k; closedge closedge; k = locatevex(g,u); for(j=0; jg.vexnum; j+

23、) /輔助數(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(shù).vexsk連接。endl; closedgek.lowcost = 0; for(j=0; jg.vexnum; +j) if(g.arcskj.adj closedgej.lowcost) closedgej.adjvex = g.vexsk

24、; closedgej.lowcost= g.arcskj.adj; int minimum(mgraph g,closedge closedge) /求closedge中權(quá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; void minispantree_krsl(mgraph g,dgevalue & dgevalue)

25、/克魯斯卡爾算法求最小生成樹 int p1,p2,i,j; int bjmax_vertex_num; /標記數(shù)組 for(i=0; ig.vexnum; i+) /標記數(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 != p2) cout 城市dgevaluei.ch1與城市dgevaluei.ch2連接。endl; for(j=0; jg.vexn

26、um; j+) if(bjj = p2) bjj = p1; void sortdge(dgevalue & dgevalue,mgraph g)/對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) /用鄰接矩陣存儲數(shù)據(jù)int i,j;for(i=0; ig.vexnum; i+) for(j=0; jg.vexnum; j+) if(g.arcsij.adj=max)cout0 ; elsecoutg