最小生成樹問題課程設計報告

數(shù)據(jù)結(jié)構(gòu)課程設計目錄一.設計目的 2二.設計內(nèi)容 2三． 概要設計 11、功能模塊圖 12、各個模塊詳細的功能描述 1四．詳細設計 21．主函數(shù)和其他函數(shù)的偽碼算法 22、主要函數(shù)的程序流程圖 63、函數(shù)之間的調(diào)用關系圖 13五．測試數(shù)據(jù)及運行結(jié)果 141．正常測試數(shù)據(jù)及運行結(jié)果 142、非正常測試數(shù)據(jù)及運行結(jié)果 15六．調(diào)試情況，設計技巧及體會 17七．參考文獻 17八．附錄：源代碼 17一.設計目的課程設計是軟件設計的綜合訓練，包括問題分析、總體結(jié)構(gòu)設計、用戶界面設計、程序設計基本技能和技巧。能夠在設計中逐步提高程序設計能力，培養(yǎng)科學的軟件工作方法。而且通過數(shù)據(jù)結(jié)構(gòu)課程設計能夠在下述各方面得到鍛煉：1、能根據(jù)實際問題的具體情況，結(jié)合數(shù)據(jù)結(jié)構(gòu)課程中的基本理論和基本算法，正確分析出數(shù)據(jù)的邏輯結(jié)構(gòu)，合理地選擇相應的存儲結(jié)構(gòu)，并能設計出解決問題的有效算法。2、提高程序設計和調(diào)試能力。通過上機實習，驗證自己設計的算法的正確性。學會有效利用基本調(diào)試方法，迅速找出程序代碼中的錯誤并且修改。3、培養(yǎng)算法分析能力。分析所設計算法的時間復雜度和空間復雜度，進一步提高程序設計水平。二.設計內(nèi)容最小生成樹問題:設計要求：在n個城市之間建設網(wǎng)絡，只需保證連通即可，求最經(jīng)濟的架設方法。存儲結(jié)構(gòu)采用多種。求解算法多種。概要設計1、功能模塊圖開始開始創(chuàng)建一個圖功能選擇1.建立鄰接矩陣2.建立鄰接表3.PRIM算法4.kruscal算法結(jié)束2、各個模塊詳細的功能描述※創(chuàng)建一個圖：通過給用戶信息提示，讓用戶將城市信息及城市之間的聯(lián)系關系和連接權(quán)值寫入程序，并根據(jù)寫入的數(shù)據(jù)創(chuàng)建成一個圖?！δ苓x擇：給用戶提示信息，讓用戶選擇相應功能。※建立鄰接矩陣：將用戶輸入的數(shù)據(jù)整理成鄰接矩陣并顯現(xiàn)在屏幕上?！⑧徑颖恚簩⒂脩糨斎氲臄?shù)據(jù)整理成臨接表并顯現(xiàn)在屏幕上?！鵓RIM算法：利用PRIM算法求出圖的最小生成樹，即：城市之間最經(jīng)濟的連接方案。四．詳細設計1．主函數(shù)和其他函數(shù)的偽碼算法※主函數(shù)：voidmain(){MGraphG;Dgevaluedgevalue;CreateUDG(G,dgevalue); charu;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<<"*****************************************"<<endl<<endl;ints;chary='y';while(y='y'){cout<<"請選擇菜單："<<endl;cin>>s;switch(s){case1:cout<<"用鄰接矩陣存儲為："<<endl;Adjacency_Matrix(G);break;case2:cout<<"用鄰接表存儲為："<<endl;Adjacency_List(G,dgevalue);break;case3:cout<<"普里姆算法最經(jīng)濟的連接方案為:"<<endl;cout<<"請輸入起始城市名稱：";cin>>u;MiniSpanTree_PRIM(G,u);break;case4:cout<<"克魯斯卡爾算法最經(jīng)濟的連接方案為:"<<endl;MiniSpanTree_KRSL(G,dgevalue);break;default: cout<<"您的輸入有誤!";break;}cout<<endl<<"是否繼續(xù)？y/n:";cin>>y;if(y=='n')break;}}※鄰接矩陣和臨接表的創(chuàng)建：intCreateUDG(MGraph&G,Dgevalue&dgevalue)//構(gòu)造無向加權(quán)圖的鄰接矩陣{inti,j,k;cout<<"請輸入城市個數(shù)及其之間的可連接線路數(shù)目：";cin>>G.vexnum>>G.arcnum;cout<<"請輸入各個城市名稱(分別用一個字符代替)：";for(i=0;i<G.vexnum;++i)cin>>G.vexs[i];for(i=0;i<G.vexnum;++i)//初始化數(shù)組for(j=0;j<G.vexnum;++j){G.arcs[i][j].adj=MAX;}cout<<"請輸入兩個城市名稱及其連接費用(嚴禁連接重復輸入!)："<<endl;for(k=0;k<G.arcnum;++k){cin>>dgevalue[k].ch1>>dgevalue[k].ch2>>dgevalue[k].value;i=LocateVex(G,dgevalue[k].ch1);j=LocateVex(G,dgevalue[k].ch2);G.arcs[i][j].adj=dgevalue[k].value;G.arcs[j][i].adj=G.arcs[i][j].adj;}returnOK;}※臨接矩陣的輸出：voidAdjacency_Matrix(MGraphG)//用鄰接矩陣存儲數(shù)據(jù){ inti,j; for(i=0;i<G.vexnum;i++){for(j=0;j<G.vexnum;j++)if(G.arcs[i][j].adj==MAX) cout<<0<<""; else cout<<G.arcs[i][j].adj<<"";cout<<endl;}}※鄰接表的輸出：voidAdjacency_List(MGraphG,Dgevaluedgevalue)//用鄰接表儲存數(shù)據(jù){ inti,j; for(i=0;i<G.vexnum;i++) { cout<<G.vexs[i]<<"->"; for(j=0;j<G.arcnum;j++) if(dgevalue[j].ch1==G.vexs[i]&&dgevalue[j].ch2!=G.vexs[i]) cout<<dgevalue[j].ch2<<"->"; elseif(dgevalue[j].ch1!=G.vexs[i]&&dgevalue[j].ch2==G.vexs[i]) cout<<dgevalue[j].ch1<<"->"; cout<<"\b\b"<<endl; }}※最小生成樹PRIM算法：voidMiniSpanTree_PRIM(MGraphG,charu)//普里姆算法求最小生成樹{inti,j,k;Closedgeclosedge;k=LocateVex(G,u);for(j=0;j<G.vexnum;j++)//輔助數(shù)組初始化 {if(j!=k){closedge[j].adjvex=u;closedge[j].lowcost=G.arcs[k][j].adj;} }closedge[k].lowcost=0;for(i=1;i<G.vexnum;i++){k=Minimum(G,closedge);cout<<"城市"<<closedge[k].adjvex<<"與城市"<<G.vexs[k]<<"連接。"<<endl;closedge[k].lowcost=0;for(j=0;j<G.vexnum;++j){if(G.arcs[k][j].adj<closedge[j].lowcost){closedge[j].adjvex=G.vexs[k];closedge[j].lowcost=G.arcs[k][j].adj;}}}}intMinimum(MGraphG,Closedgeclosedge)//求closedge中權(quán)值最小的邊，并返回其頂點在vexs中的位置{inti,j;doublek=1000;for(i=0;i<G.vexnum;i++){if(closedge[i].lowcost!=0&&closedge[i].lowcost<k){k=closedge[i].lowcost;j=i;}}returnj;}※最小生成樹kruscal算法：voidMiniSpanTree_KRSL(MGraphG,Dgevalue&dgevalue)//克魯斯卡爾算法求最小生成樹{intp1,p2,i,j;intbj[MAX_VERTEX_NUM];//標記數(shù)組for(i=0;i<G.vexnum;i++)//標記數(shù)組初始化bj[i]=i;Sortdge(dgevalue,G);//將所有權(quán)值按從小到大排序for(i=0;i<G.arcnum;i++){p1=bj[LocateVex(G,dgevalue[i].ch1)];p2=bj[LocateVex(G,dgevalue[i].ch2)];if(p1!=p2){cout<<"城市"<<dgevalue[i].ch1<<"與城市"<<dgevalue[i].ch2<<"連接。"<<endl;for(j=0;j<G.vexnum;j++){if(bj[j]==p2)bj[j]=p1;}}}}voidSortdge(Dgevalue&dgevalue,MGraphG)//對dgevalue中各元素按權(quán)值按從小到大排序{inti,j;doubletemp;charch1,ch2;for(i=0;i<G.arcnum;i++){for(j=i;j<G.arcnum;j++){if(dgevalue[i].value>dgevalue[j].value){temp=dgevalue[i].value;dgevalue[i].value=dgevalue[j].value;dgevalue[j].value=temp;ch1=dgevalue[i].ch1;dgevalue[i].ch1=dgevalue[j].ch1;dgevalue[j].ch1=ch1;ch2=dgevalue[i].ch2;dgevalue[i].ch2=dgevalue[j].ch2;dgevalue[j].ch2=ch2;}}}}2、主要函數(shù)的程序流程圖※main（）主函數(shù)※CreatUDG()建圖函數(shù)※Adjacency_Matrix()鄰接矩陣輸出函數(shù)※Adjacency_List()鄰接表輸出函數(shù)※MiniSpanTree_PRIM()普里姆算法：基本思想：假設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)值就是你所輸入的每兩個城市之間的建設成本。開始開始標志頂點1加入U集合尋找滿足邊的一個頂點在U,另一個頂點在V的最小邊形成n-1條邊的生成樹頂點k加入U修改由頂點k到其他頂點邊的權(quán)值結(jié)束得到最小生成樹※MiniSpanTree_KRSL()克魯斯卡爾算法：基本思想：假設WN=（V,{E}）是一個含有N個頂點的連通網(wǎng)。則按照克魯斯卡爾算法構(gòu)造最小生成樹的過程為：先構(gòu)造一個只含n個頂點，而邊集為空的子圖，若將該子圖中各個頂點看成是各棵樹上的根結(jié)點，則它是一個含有n棵樹的一個森林。之后，從網(wǎng)的邊集E中選取一條權(quán)值最小的邊，若該條邊的兩個頂點分屬不同的樹，則將其加入子圖，也就是說，將這兩個頂點分別所在的兩棵樹合成一棵樹；反之，若該條邊的兩個頂點已落在同一棵樹上，則不可取，而應該取下一條權(quán)值最小的邊再試之。依次類推，直到森林中只有一棵樹，也即子圖中含有n-1條邊為止。在此系統(tǒng)中，N是你所需要輸入的城市個數(shù)。而每條邊的權(quán)值就是你所輸入的每兩個城市之間的建設成本。※LocateVex（）節(jié)點位置函數(shù)：※Minimum()權(quán)值比較函數(shù)：※Sortdge()權(quán)值排序函數(shù)：3、函數(shù)之間的調(diào)用關系圖五．測試數(shù)據(jù)及運行結(jié)果1．正常測試數(shù)據(jù)及運行結(jié)果2、非正常測試數(shù)據(jù)及運行結(jié)果六．調(diào)試情況，設計技巧及體會通過此次課程設計，我更深刻地理解了最小生成樹問題，知道如何在n個城市之間建設網(wǎng)絡，只需保證連通即可，求最經(jīng)濟的架設方法。并且用了多種求解方式。數(shù)據(jù)結(jié)構(gòu)是學習計算機的一門重要的基礎課，在學習數(shù)據(jù)結(jié)構(gòu)之前我們學習了C語言在我們看來數(shù)據(jù)結(jié)構(gòu)就是學習C語言的延續(xù)。這幾天的課程設計讓我充分地體會到了上機實踐對于計算機編程的重要性。其實在于計算機語言這類課程看重的就是上機的實際操作，不滿足于基本理論的學習。上機操作才能讓我們更加好的掌握我們所要學習的計算機語言知識。只顧學習理論是遠遠不夠的。實踐中可以發(fā)現(xiàn)許許多多的問題，然后通過同學老師的幫助，得以解決，讓自己的編程能力得到極大的提升。此外，也讓我更加明白編程是要解決現(xiàn)實問題的。只有擁有把現(xiàn)實問題理論化的能力，才是編程真正需要達到的境界。七．參考文獻《《新編C語言課程設計教程》》周二強編著清華大學出版社《《數(shù)據(jù)結(jié)構(gòu)（C語言版）》》嚴蔚敏吳偉民編著清華大學出版社八．附錄：源代碼#include<stdio.h>#include<stdlib.h>#include<iostream.h>#defineMAX_VERTEX_NUM20#defineOK1#defineERROR0#defineMAX1000typedefstructArcell{doubleadj;}Arcell,AdjMatrix[MAX_VERTEX_NUM][MAX_VERTEX_NUM];typedefstruct{charvexs[MAX_VERTEX_NUM];//節(jié)點數(shù)組AdjMatrixarcs;//鄰接矩陣intvexnum,arcnum;//圖的當前節(jié)點數(shù)和弧數(shù)}MGraph;typedefstructPnode//用于普利姆算法{charadjvex;//節(jié)點doublelowcost;//權(quán)值}Pnode,Closedge[MAX_VERTEX_NUM];//記錄頂點集U到V-U的代價最小的邊的輔助數(shù)組定義typedefstructKnode//用于克魯斯卡爾算法中存儲一條邊及其對應的2個節(jié)點{charch1;//節(jié)點1charch2;//節(jié)點2doublevalue;//權(quán)值}Knode,Dgevalue[MAX_VERTEX_NUM];//intCreateUDG(MGraph&G,Dgevalue&dgevalue);intLocateVex(MGraphG,charch);intMinimum(MGraphG,Closedgeclosedge);voidMiniSpanTree_PRIM(MGraphG,charu);voidSortdge(Dgevalue&dgevalue,MGraphG);voidAdjacency_Matrix(MGraphG);voidAdjacency_List(MGraphG,Dgevaluedgevalue);//intCreateUDG(MGraph&G,Dgevalue&dgevalue)//構(gòu)造無向加權(quán)圖的鄰接矩陣{inti,j,k;cout<<"請輸入城市個數(shù)及其之間的可連接線路數(shù)目：";cin>>G.vexnum>>G.arcnum;cout<<"請輸入各個城市名稱(分別用一個字符代替)：";for(i=0;i<G.vexnum;++i)cin>>G.vexs[i];for(i=0;i<G.vexnum;++i)//初始化數(shù)組for(j=0;j<G.vexnum;++j){G.arcs[i][j].adj=MAX;}cout<<"請輸入兩個城市名稱及其連接費用(嚴禁連接重復輸入!)："<<endl;for(k=0;k<G.arcnum;++k){cin>>dgevalue[k].ch1>>dgevalue[k].ch2>>dgevalue[k].value;i=LocateVex(G,dgevalue[k].ch1);j=LocateVex(G,dgevalue[k].ch2);G.arcs[i][j].adj=dgevalue[k].value;G.arcs[j][i].adj=G.arcs[i][j].adj;}returnOK;}intLocateVex(MGraphG,charch)//確定節(jié)點ch在圖G.vexs中的位置{inta;for(inti=0;i<G.vexnum;i++)if(G.vexs[i]==ch)a=i;returna;}voidMiniSpanTree_PRIM(MGraphG,charu)//普里姆算法求最小生成樹{inti,j,k;Closedgeclosedge;k=LocateVex(G,u);for(j=0;j<G.vexnum;j++)//輔助數(shù)組初始化 {if(j!=k){closedge[j].adjvex=u;closedge[j].lowcost=G.arcs[k][j].adj;} }closedge[k].lowcost=0;for(i=1;i<G.vexnum;i++){k=Minimum(G,closedge);cout<<"城市"<<closedge[k].adjvex<<"與城市"<<G.vexs[k]<<"連接。"<<endl;closedge[k].lowcost=0;for(j=0;j<G.vexnum;++j){if(G.arcs[k][j].adj<closedge[j].lowcost){closedge[j].adjvex=G.vexs[k];closedge[j].lowcost=G.arcs[k][j].adj;}}}}intMinimum(MGraphG,Closedgeclosedge)//求closedge中權(quán)值最小的邊，并返回其頂點在vexs中的位置{inti,j;doublek=1000;for(i=0;i<G.vexnum;i++){if(closedge[i].lowcost!=0&&closedge[i].lowcost<k){k=closedge[i].lowcost;j=i;}}returnj;}voidMiniSpanTree_KRSL(MGraphG,Dgevalue&dgevalue)//克魯斯卡爾算法求最小生成樹{intp1,p2,i,j;intbj[MAX_VERTEX_NUM];//標記數(shù)組for(i=0;i<G.vexnum;i++)//標記數(shù)組初始化bj[i]=i;Sortdge(dgevalue,G);//將所有權(quán)值按從小到大排序for(i=0;i<G.arcnum;i++){p1=bj[LocateVex(G,dgevalue[i].ch1)];p2=bj[LocateVex(G,dgevalue[i].ch2)];if(p1!=p2){cout<<"城市"<<dgevalue[i].ch1<<"與城市"<<dgevalue[i].ch2<<"連接。"<<endl;for(j=0;j<G.vexnum;j++){if(bj[j]==p2)bj[j]=p1;}}}}voidSortdge(Dgevalue&dgevalue,MGraphG)//對dgevalue中各元素按權(quán)值按從小到大排序{inti,j;doubletemp;charch1,ch2;for(i=0;i<G.arcnum;i++){for(j=i;j<G.arcnum;j++){if(dgevalue[i].value>dgevalue[j].value){temp=dgevalue[i].value;dgevalue[i].value=dgevalue[j].value;dgevalue[j].value=temp;ch1=dgevalue[i].ch1;dgevalue[i].ch1=dgevalue[j].ch1;dgevalue[j].ch1=ch1;ch2=dgevalue[i].ch2;dgevalue[i].ch2=dgevalue[j].ch2;dgevalue[j].ch2=ch2;}}}}voidAdjacency_Matrix(MGraphG)//用鄰接矩陣存儲數(shù)據(jù){ inti,j; for(i=0;i<G.vexnum;i++){for(j=0;j<G.vexnum;j++)if(G.arcs[i][j].adj==MAX) cout<<0<<""; else cout<<G.arcs[i][j].adj<<"";cout<<endl;}}voidAdjacency_List(MGraphG,Dgevaluedgevalue)//用鄰接表儲存數(shù)據(jù){ inti,j; for(i=0;i<G.vexnum;i++) { cout<<G.vexs[i]<<