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

數(shù)據(jù)結(jié)構(gòu)課程設(shè)計(jì)目錄一.設(shè)計(jì)目的 2二.設(shè)計(jì)內(nèi)容 2三． 概要設(shè)計(jì) 11、功能模塊圖 12、各個模塊詳細(xì)的功能描述 1四．詳細(xì)設(shè)計(jì) 21．主函數(shù)和其他函數(shù)的偽碼算法 22、主要函數(shù)的程序流程圖 63、函數(shù)之間的調(diào)用關(guān)系圖 13五．測試數(shù)據(jù)及運(yùn)行結(jié)果 141．正常測試數(shù)據(jù)及運(yùn)行結(jié)果 142、非正常測試數(shù)據(jù)及運(yùn)行結(jié)果 15六．調(diào)試情況，設(shè)計(jì)技巧及體會 17七．參考文獻(xiàn) 17八．附錄：源代碼 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)的存儲結(jié)構(gòu)，并能設(shè)計(jì)出解決問題的有效算法。2、提高程序設(shè)計(jì)和調(diào)試能力。通過上機(jī)實(shí)習(xí)，驗(yàn)證自己設(shè)計(jì)的算法的正確性。學(xué)會有效利用基本調(diào)試方法，迅速找出程序代碼中的錯誤并且修改。3、培養(yǎng)算法分析能力。分析所設(shè)計(jì)算法的時(shí)間復(fù)雜度和空間復(fù)雜度，進(jìn)一步提高程序設(shè)計(jì)水平。二.設(shè)計(jì)內(nèi)容最小生成樹問題:設(shè)計(jì)要求：在n個城市之間建設(shè)網(wǎng)絡(luò)，只需保證連通即可，求最經(jīng)濟(jì)的架設(shè)方法。存儲結(jié)構(gòu)采用多種。求解算法多種。概要設(shè)計(jì)1、功能模塊圖開始開始創(chuàng)建一個圖功能選擇1.建立鄰接矩陣2.建立鄰接表3.PRIM算法4.kruscal算法結(jié)束2、各個模塊詳細(xì)的功能描述※創(chuàng)建一個圖：通過給用戶信息提示，讓用戶將城市信息及城市之間的聯(lián)系關(guān)系和連接權(quán)值寫入程序，并根據(jù)寫入的數(shù)據(jù)創(chuàng)建成一個圖?！δ苓x擇：給用戶提示信息，讓用戶選擇相應(yīng)功能?！⑧徑泳仃嚕簩⒂脩糨斎氲臄?shù)據(jù)整理成鄰接矩陣并顯現(xiàn)在屏幕上?！⑧徑颖恚簩⒂脩糨斎氲臄?shù)據(jù)整理成臨接表并顯現(xiàn)在屏幕上?！鵓RIM算法：利用PRIM算法求出圖的最小生成樹，即：城市之間最經(jīng)濟(jì)的連接方案。四．詳細(xì)設(shè)計(jì)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)濟(jì)的連接方案********"<<endl;cout<<"**4、克魯斯卡爾算法求最經(jīng)濟(jì)的連接方案****"<<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)濟(jì)的連接方案為:"<<endl;cout<<"請輸入起始城市名稱：";cin>>u;MiniSpanTree_PRIM(G,u);break;case4:cout<<"克魯斯卡爾算法最經(jīng)濟(jì)的連接方案為:"<<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<<"請輸入兩個城市名稱及其連接費(fèi)用(嚴(yán)禁連接重復(fù)輸入!)："<<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)值最小的邊，并返回其頂點(diǎ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];//標(biāo)記數(shù)組for(i=0;i<G.vexnum;i++)//標(biāo)記數(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()普里姆算法：基本思想：假設(shè)WN=(V,{E})是一個含有n個頂點(diǎn)的連通網(wǎng)，TV是WN上最小生成樹中頂點(diǎn)的集合，TE是最小生成樹中邊的集合。顯然，在算法執(zhí)行結(jié)束時(shí)，TV=V，而TE是E的一個子集。在算法開始執(zhí)行時(shí)，TE為空集，TV中只有一個頂點(diǎn)，因此，按普利姆算法構(gòu)造最小生成樹的過程為：在所有“其一個頂點(diǎn)已經(jīng)落在生成樹上，而另一個頂點(diǎn)尚未落在生成樹上”的邊中取一條權(quán)值為最小的邊，逐條加在生成樹上，直至生成樹中含有n-1條邊為止。在此系統(tǒng)中，N是你所需要輸入的城市個數(shù)。而每條邊的權(quán)值就是你所輸入的每兩個城市之間的建設(shè)成本。開始開始標(biāo)志頂點(diǎn)1加入U(xiǎn)集合尋找滿足邊的一個頂點(diǎn)在U,另一個頂點(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}）是一個含有N個頂點(diǎn)的連通網(wǎng)。則按照克魯斯卡爾算法構(gòu)造最小生成樹的過程為：先構(gòu)造一個只含n個頂點(diǎn)，而邊集為空的子圖，若將該子圖中各個頂點(diǎn)看成是各棵樹上的根結(jié)點(diǎn)，則它是一個含有n棵樹的一個森林。之后，從網(wǎng)的邊集E中選取一條權(quán)值最小的邊，若該條邊的兩個頂點(diǎn)分屬不同的樹，則將其加入子圖，也就是說，將這兩個頂點(diǎn)分別所在的兩棵樹合成一棵樹；反之，若該條邊的兩個頂點(diǎn)已落在同一棵樹上，則不可取，而應(yīng)該取下一條權(quán)值最小的邊再試之。依次類推，直到森林中只有一棵樹，也即子圖中含有n-1條邊為止。在此系統(tǒng)中，N是你所需要輸入的城市個數(shù)。而每條邊的權(quán)值就是你所輸入的每兩個城市之間的建設(shè)成本?！鵏ocateVex（）節(jié)點(diǎn)位置函數(shù)：※Minimum()權(quán)值比較函數(shù)：※Sortdge()權(quán)值排序函數(shù)：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ì)技巧及體會通過此次課程設(shè)計(jì)，我更深刻地理解了最小生成樹問題，知道如何在n個城市之間建設(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ì)讓我充分地體會到了上機(jī)實(shí)踐對于計(jì)算機(jī)編程的重要性。其實(shí)在于計(jì)算機(jī)語言這類課程看重的就是上機(jī)的實(shí)際操作，不滿足于基本理論的學(xué)習(xí)。上機(jī)操作才能讓我們更加好的掌握我們所要學(xué)習(xí)的計(jì)算機(jī)語言知識。只顧學(xué)習(xí)理論是遠(yuǎn)遠(yuǎn)不夠的。實(shí)踐中可以發(fā)現(xiàn)許許多多的問題，然后通過同學(xué)老師的幫助，得以解決，讓自己的編程能力得到極大的提升。此外，也讓我更加明白編程是要解決現(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<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é)點(diǎn)數(shù)組AdjMatrixarcs;//鄰接矩陣intvexnum,arcnum;//圖的當(dāng)前節(jié)點(diǎn)數(shù)和弧數(shù)}MGraph;typedefstructPnode//用于普利姆算法{charadjvex;//節(jié)點(diǎn)doublelowcost;//權(quán)值}Pnode,Closedge[MAX_VERTEX_NUM];//記錄頂點(diǎn)集U到V-U的代價(jià)最小的邊的輔助數(shù)組定義typedefstructKnode//用于克魯斯卡爾算法中存儲一條邊及其對應(yīng)的2個節(jié)點(diǎn){charch1;//節(jié)點(diǎn)1charch2;//節(jié)點(diǎn)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<<"請輸入兩個城市名稱及其連接費(fèi)用(嚴(yán)禁連接重復(fù)輸入!)："<<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é)點(diǎn)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)值最小的邊，并返回其頂點(diǎ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];//標(biāo)記數(shù)組for(i=0;i<G.vexnum;i++)//標(biāo)記數(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]<<