最小生成樹問題報(bào)告_本科論文.doc

《最小生成樹問題報(bào)告_本科論文.doc》由會員上傳分享，免費(fèi)在線閱讀，更多相關(guān)內(nèi)容在學(xué)術(shù)論文-天天文庫。

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

2、且通過數(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)試方法，迅速找出程序代碼中的錯(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è)方法。存儲結(jié)構(gòu)采用多種。求解算法多種。24三．概要設(shè)計(jì)1、功能模塊圖開始創(chuàng)建一個(gè)圖

3、功能選擇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ù)整理成鄰接矩陣并顯現(xiàn)在屏幕上。※建立鄰接表：將用戶輸入的數(shù)據(jù)整理成臨接表并顯現(xiàn)在屏幕上?！鵓RIM算法：利用PRIM算法求出圖的最小生成樹，即：城市之間最經(jīng)濟(jì)的連接方案。24四．詳細(xì)設(shè)計(jì)1．主函數(shù)和其他函數(shù)的偽碼算法※主函數(shù)：voidmain(){MGraphG;Dgevaluedge

4、value;CreateUDG(G,dgevalue);charu;cout<<"圖創(chuàng)建成功。";cout<<"請根據(jù)如下菜單選擇操作。";cout<<"*****************************************"<

5、<>s;switch(s){case1:cout<<"用鄰接矩陣存儲為："<

6、請輸入起始城市名稱：";cin>>u;MiniSpanTree_PRIM(G,u);break;case4:cout<<"克魯斯卡爾算法最經(jīng)濟(jì)的連接方案為:"<>y;if(y=='n')break;}}※鄰接矩陣和臨接表的創(chuàng)建：intCreateUDG(MGraph&G,Dgevalue&dgevalue)//構(gòu)造無向加權(quán)圖的鄰接矩陣{inti,j,k;cout<<"請輸入城市個(gè)數(shù)及

7、其之間的可連接線路數(shù)目：";cin>>G.vexnum>>G.arcnum;cout<<"請輸入各個(gè)城市名稱(分別用一個(gè)字符代替)：";for(i=0;i>G.vexs[i];for(i=0;i