PAGE..課程設計管道鋪設施工的最佳方案課程設計題目N〔N>10個居民區(qū)之間需要鋪設煤氣管道。假設任意兩個居民區(qū)之間都可以鋪設煤氣管道,但代價不同。事先將任意兩個居民區(qū)之間鋪設煤氣管道的代價存入磁盤文件中。設計一個最佳方案使得這N個居民區(qū)之間鋪設煤氣管道所需代價最少,并希望以圖形方式在屏幕上輸出結果。課程設計目的及要求：目的：1.能根據(jù)實際問題的具體情況,結合數(shù)據(jù)結構課程中的基本理論和基本算法,正確分析出數(shù)據(jù)的邏輯結構,合理地選擇相應的存儲結構,并能設計出解決問題的有效算法2.提高程序設計和調試能力.學生通過上機實習,驗證自己設計的算法的正確性,學會有效利用基本調試方法,迅速找出程序代碼中的錯誤并且修改.3.培養(yǎng)算法分析能力.分析所設計算法的時間復雜度和空間復雜度,進一步提高程序設計水平.要求：求解的算法為：在可能架設的m條管道中選取n-1條,即能連通n-1個居民區(qū),又使總投資達到"最小"。網(wǎng)采用鄰接矩陣為存儲結構,以頂點對〔i,j的形式輸出最小生成樹的邊。二、數(shù)據(jù)結構設計①圖文件的結構？

②圖在內存中的存儲結構

鄰接矩陣、鄰接表、三元組

③最小生成樹的存儲結構

④圖形的顯示結構三、功能設計①準備代價文件

自動隨機生成、用戶可以自定義

②讀圖文件,得到圖的存儲結構

③計算最小生成樹

何種算法效率更好？Prim、Kruskal

④顯示最小生成樹

文本方式：各邊、總權值

圖形函數(shù)：屏幕初始化、端點位置的初始化、繪邊函數(shù)、代價顯示函數(shù)、繪無邊圖函數(shù)課程設計詳細內容：//main.ccp#include<iostream>#include<conio.h>#include<process.h>#include"Pipe.h"usingnamespacestd;intmain<>{ intn; for<inti=1;i<=10;i++> cout<<endl; cout<<"**************************"<<endl; cout<<"**歡迎進入**"<<endl; cout<<"**管道鋪設系統(tǒng)**"<<endl; cout<<"**************************"<<endl; cout<<"按任意鍵繼續(xù)..."<<endl; if<!getch<>> return0; system<"cls.exe">; Pipelinem; system<"cls.exe">; while<1> { m.menu<>; cin>>n; switch<n> { case1: m.create<>; break; case2: m.prim<>; break; case3: m.print<>; break; case4: m.print2<>; case5: break; case6: return0; } }}//#include<iostream>#include<fstream>#include<iomanip>#include"Pipe.h"usingnamespacestd;Pipeline::Pipeline<>{ cout<<"************************************"<<endl; cout<<endl; cout<<"請輸入需鋪設管道的居民數(shù)量："<<endl; cout<<endl; cout<<"************************************"<<endl; cin>>N;}voidPipeline::prim<>{ intmin,t,m,w; intr; intk=2; intj=k-1; inti=1; cout<<"請輸入從哪個居民開始鋪設管道："<<endl; cin>>r; for<i;i<=N;i++> { bian[i].from=r; bian[i].end=i; bian[i].weights=Graph[r][i]; } for<k;k<=N+1;k++> { min=999; m=k-1; for<j;j<=N;j++> { if<bian[j].weights<min> { min=bian[j].weights; m=j; } } edgetemp=bian[k-1]; bian[k-1]=bian[m]; bian[m]=temp; j=bian[k-1].end; for<i=k;i<=N;i++> { t=bian[i].end; w=Graph[j][t]; if<w<bian[i].weights> { bian[i].weights=w; bian[i].from=j; } } }}voidPipeline::menu<>{ cout<<"***********************************"<<endl; cout<<"**1、輸入需鋪設管道的居民信息**"<<endl; cout<<"**2、用prim算法求出最短路徑**"<<endl; cout<<"**3、輸出prim算法的結果**"<<endl; cout<<"**4、輸出輸入各權值的結果**"<<endl; cout<<"**5、畫出管道鋪設的結果圖**"<<endl; cout<<"**6、退出**"<<endl; cout<<"***********************************"<<endl;}voidPipeline::create<>{ intm; ofstreamf<"weight.txt">;//打開文件用于寫,若文件不存在就創(chuàng)建它 if<!f>//打開文件失敗則結束運行 { throw"文件打開失敗！"; return; } else { for<inti=1;i<=N;i++> { for<intj=i;j<=N;j++> { if<i==j> { Graph[i][j]=999; continue; } cout<<"請輸入<"<<i<<","<<j<<">邊的權值："<<endl; cin>>m; f<<setw<10><<m;//將權值保存到文件中 Graph[i][j]=m; Graph[j][i]=m; } cout<<endl; } f.close<>;//關閉文件 }}voidPipeline::print<>{ cout<<"起點"<<""<<"終點"<<""<<"權值"<<endl; for<inti=1;i<=N;i++> cout<<bian[i].from<<""<<bian[i].end<<""<<bian[i].weights<<endl;}voidPipeline::print2<>{ for<inti=1;i<=N;i++> { for<intj=1;j<=N;j++> { cout<<Graph[i][j]<<""; } cout<<endl; }}//Pipe.h#ifndef_PIPE_H_#define_PIPE_H_#include<iostream>structedge//定義一條生成樹的邊{ intfrom;//起點 intend;//終點 intweights;//權值};classPipeline//定義一個管道的類{public: Pipeline<>;//無參構造函數(shù) voidprim<>;//普里母算法實現(xiàn) voidmenu<>;//菜單 voidcreate<>;//建立各個居民之間的權限 voidprint<>;//輸出prim算法的結果 voidprint2<>;//輸出輸入權值的結果private: intN; //居民數(shù) edgebian[50]; //最小生成樹的邊集 intGraph[50][50]; //各個居民點的權值的集合}; #endif注：可另附頁課程設計總結及體會：通過數(shù)據(jù)結構的課程設計使我們對所學知識有了更好的理解,也增強了動手能力,同時也發(fā)現(xiàn)了自己的很多不足之處,對所學知識的應用能力不足,編程水平與課程要求有很大差距。由于對課本知識了解不夠,在實驗過程中遇到了一些問題,經(jīng)過查閱資料思考和探究,最終將問題得到了解決。通過這次課程設計使我懂得了理論與實際相結合是很