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

1、數(shù)據(jù)結(jié)構(gòu)課程設(shè)計報告專 業(yè)： 軟件工程題 目： 最小生成樹問題 目錄一. 設(shè)計目的2二. 設(shè)計內(nèi)容2三概要設(shè)計11、功能模塊圖12、各個模塊詳細(xì)的功能描述1四詳細(xì)設(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七參考文獻(xiàn)17八附錄：源代碼1724 / 27文檔可自由編輯打印一. 設(shè)計目的課程設(shè)計是軟件設(shè)計的綜合訓(xùn)練，包括問題分析、總體結(jié)構(gòu)設(shè)計、用戶界面設(shè)計、程序設(shè)計基本技能和技巧。能夠在設(shè)計中逐步提高程序設(shè)計能力，培養(yǎng)科學(xué)的軟件工作方法。而

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

3、1.建立鄰接矩陣2.建立鄰接表3. PRIM算法4.kruscal算法結(jié)束2、各個模塊詳細(xì)的功能描述創(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)濟(jì)的連接方案。四詳細(xì)設(shè)計1主函數(shù)和其他函數(shù)的偽碼算法 主函數(shù)：void main() MGraph G; Dgevalue dgevalue; Creat

4、eUDG(G,dgevalue); char u; cout<<"圖創(chuàng)建成功。" cout<<"請根據(jù)如下菜單選擇操作。n" cout<<" *"<<endl; cout<<" *1、用鄰接矩陣存儲：*"<<endl; cout<<" *2、用鄰接表存儲：*"<<endl; cout<<" *3、普里姆算法求最經(jīng)濟(jì)的連接方案*"<<endl; cout<

5、;<" *4、克魯斯卡爾算法求最經(jīng)濟(jì)的連接方案*"<<endl; cout<<" *"<<endl<<endl; int s; char y='y' while(y='y') cout<<"請選擇菜單："<<endl; cin>>s; switch(s) case 1: cout<<"用鄰接矩陣存儲為："<<endl; Adjacency_Matrix(G); break

6、; case 2: cout<<"用鄰接表存儲為："<<endl; Adjacency_List(G,dgevalue); break; case 3: cout<<"普里姆算法最經(jīng)濟(jì)的連接方案為:"<<endl; cout<<"請輸入起始城市名稱：" cin>>u; MiniSpanTree_PRIM(G,u); break; case 4: cout<<"克魯斯卡爾算法最經(jīng)濟(jì)的連接方案為:"<<endl; MiniS

7、panTree_KRSL(G,dgevalue); break; default: cout<<"您的輸入有誤!" break; cout<<endl<<"是否繼續(xù)？y/n:" cin>>y; if(y='n') break; 鄰接矩陣和臨接表的創(chuàng)建：int CreateUDG(MGraph & G,Dgevalue & dgevalue) /構(gòu)造無向加權(quán)圖的鄰接矩陣 int i,j,k; cout<<"請輸入城市個數(shù)及其之間的可連接線路數(shù)目："

8、; cin>>G.vexnum>>G.arcnum; cout<<"請輸入各個城市名稱(分別用一個字符代替)：" for(i=0;i<G.vexnum;+i) cin>>G.vexsi; for(i=0;i<G.vexnum;+i)/初始化數(shù)組 for(j=0;j<G.vexnum;+j) G.arcsij.adj=MAX; cout<<"請輸入兩個城市名稱及其連接費用(嚴(yán)禁連接重復(fù)輸入!)："<<endl; for(k=0;k<G.arcnum;+k) ci

9、n >> 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) /用鄰接矩陣存儲數(shù)據(jù)int i,j;for(i=0; i<G.vexnum; i+) for

10、(j=0; j<G.vexnum; j+) if(G.arcsij.adj=MAX)cout<<0<<" " elsecout<<G.arcsij.adj<<" " cout<<endl; 鄰接表的輸出： void Adjacency_List(MGraph G,Dgevalue dgevalue) /用鄰接表儲存數(shù)據(jù)int i,j;for(i=0;i<G.vexnum;i+)cout<<G.vexsi<<"->"for(j=0;j&

11、lt;G.arcnum;j+)if(dgevaluej.ch1=G.vexsi&&dgevaluej.ch2!=G.vexsi)cout<<dgevaluej.ch2<<"->"else if(dgevaluej.ch1!=G.vexsi&&dgevaluej.ch2=G.vexsi)cout<<dgevaluej.ch1<<"->"cout<<"bb "<<endl;最小生成樹PRIM算法： void MiniSpan

12、Tree_PRIM(MGraph G,char u)/普里姆算法求最小生成樹 int i,j,k; Closedge closedge; k = LocateVex(G,u); for(j=0; j<G.vexnum; j+) /輔助數(shù)組初始化 if(j != k) closedgej.adjvex = u; closedgej.lowcost = G.arcskj.adj; closedgek.lowcost = 0; for(i=1; i<G.vexnum; i+) k = Minimum(G,closedge); cout<<" 城市"<

13、<closedgek.adjvex<<"與城市"<<G.vexsk<<"連接。"<<endl; closedgek.lowcost = 0; for(j=0; j<G.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)值

14、最小的邊，并返回其頂點在vexs中的位置 int i,j; double k = 1000; for(i=0; i<G.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;

15、 /標(biāo)記數(shù)組 for(i=0; i<G.vexnum; i+) /標(biāo)記數(shù)組初始化 bji=i; Sortdge(dgevalue,G);/將所有權(quán)值按從小到大排序 for(i=0; i<G.arcnum; i+) p1 = bjLocateVex(G,dgevaluei.ch1); p2 = bjLocateVex(G,dgevaluei.ch2); if(p1 != p2) cout<<" 城市"<<dgevaluei.ch1<<"與城市"<<dgevaluei.ch2<<&quo

16、t;連接。"<<endl; for(j=0; j<G.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; i<G.arcnum; i+) for(j=i; j<G.arcnum; j+) if(dgevaluei.value > dgevaluej.value) temp = dgevaluei.val

17、ue; 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; 2、主要函數(shù)的程序流程圖 main（）主函數(shù)CreatUDG()建圖函數(shù)Adjacency_Matrix()鄰接矩陣輸出函數(shù) Adjacency_List()鄰接表輸出函數(shù)MiniS

18、panTree_PRIM()普里姆算法：基本思想： 假設(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è)成本。開始標(biāo)志頂點1加入U集合尋找滿足邊的一個頂點在U,

19、另一個頂點在V的最小邊形成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)值最小的

20、邊再試之。依次類推，直到森林中只有一棵樹，也即子圖中含有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)濟(jì)的架設(shè)方法。并且用了多種求解方式。數(shù)據(jù)結(jié)構(gòu)是學(xué)習(xí)計算機(jī)的一門重要的基礎(chǔ)課，在學(xué)習(xí)數(shù)據(jù)結(jié)構(gòu)之前我們學(xué)

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

22、八附錄：源代碼#include<stdio.h> #include<stdlib.h> #include<iostream.h> #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; /鄰接

23、矩陣 int vexnum,arcnum; /圖的當(dāng)前節(jié)點數(shù)和弧數(shù) MGraph; typedef struct Pnode /用于普利姆算法 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 Crea

24、teUDG(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);/- int Cre

25、ateUDG(MGraph & G,Dgevalue & dgevalue) /構(gòu)造無向加權(quán)圖的鄰接矩陣 int i,j,k; cout<<"請輸入城市個數(shù)及其之間的可連接線路數(shù)目：" cin>>G.vexnum>>G.arcnum; cout<<"請輸入各個城市名稱(分別用一個字符代替)：" for(i=0;i<G.vexnum;+i) cin>>G.vexsi; for(i=0;i<G.vexnum;+i)/初始化數(shù)組 for(j=0;j<G.vexnum;

26、+j) G.arcsij.adj=MAX; cout<<"請輸入兩個城市名稱及其連接費用(嚴(yán)禁連接重復(fù)輸入!)："<<endl; for(k=0;k<G.arcnum;+k) cin >> dgevaluek.ch1 >> dgevaluek.ch2 >> dgevaluek.value; i = LocateVex(G,dgevaluek.ch1); j = LocateVex(G,dgevaluek.ch2); G.arcsij.adj = dgevaluek.value; G.arcsji.adj =

27、G.arcsij.adj; return OK; int LocateVex(MGraph G,char ch) /確定節(jié)點ch在圖G.vexs中的位置 int a ; for(int i=0; i<G.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; j<G.vexnum; j+) /輔助數(shù)組初始化 if(j != k) c

28、losedgej.adjvex = u; closedgej.lowcost = G.arcskj.adj; closedgek.lowcost = 0; for(i=1; i<G.vexnum; i+) k = Minimum(G,closedge); cout<<" 城市"<<closedgek.adjvex<<"與城市"<<G.vexsk<<"連接。"<<endl; closedgek.lowcost = 0; for(j=0; j<G.vexn

29、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; i<G.vexnum; i+) if(closedgei.lowcost != 0 && closedgei.lowcost < k)

30、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; i<G.vexnum; i+) /標(biāo)記數(shù)組初始化 bji=i; Sortdge(dgevalue,G);/將所有權(quán)值按從小到大排序 for(i=0; i<G.arcnum; i+) p1 = bjLocateVex(G,dgevaluei.ch1); p2 =

31、bjLocateVex(G,dgevaluei.ch2); if(p1 != p2) cout<<" 城市"<<dgevaluei.ch1<<"與城市"<<dgevaluei.ch2<<"連接。"<<endl; for(j=0; j<G.vexnum; j+) if(bjj = p2) bjj = p1; void Sortdge(Dgevalue & dgevalue,MGraph G)/對dgevalue中各元素按權(quán)值按從小到大排序 int i,

32、j; double temp; char ch1,ch2; for(i=0; i<G.arcnum; i+) for(j=i; j<G.arcnum; j+) if(dgevaluei.value > dgevaluej.value) temp = dgevaluei.value; dgevaluei.value = dgevaluej.value; dgevaluej.value = temp; ch1 = dgevaluei.ch1; dgevaluei.ch1 = dgevaluej.ch1; dgevaluej.ch1 = ch1; ch2 = dgevaluei.c

33、h2; dgevaluei.ch2 = dgevaluej.ch2; dgevaluej.ch2 = ch2; void Adjacency_Matrix(MGraph G) /用鄰接矩陣存儲數(shù)據(jù)int i,j;for(i=0; i<G.vexnum; i+) for(j=0; j<G.vexnum; j+) if(G.arcsij.adj=MAX)cout<<0<<" " elsecout<<G.arcsij.adj<<" " cout<<endl; void Adjacency_

34、List(MGraph G,Dgevalue dgevalue) /用鄰接表儲存數(shù)據(jù)int i,j;for(i=0;i<G.vexnum;i+)cout<<G.vexsi<<"->"for(j=0;j<G.arcnum;j+)if(dgevaluej.ch1=G.vexsi&&dgevaluej.ch2!=G.vexsi)cout<<dgevaluej.ch2<<"->"else if(dgevaluej.ch1!=G.vexsi&&dgevaluej.ch2=G.vexsi)cout<<dgevaluej.ch1<<"->"cout<<