綜合實驗十二校園導游咨詢VIP

1、綜合實驗十二 校園導游咨詢一、 實驗?zāi)康模?）熟練掌握圖的創(chuàng)建及遍歷基本操作算法。（2） 熟練掌握最短路徑算法。（3）利用圖的遍歷和最短路徑求解技術(shù)，設(shè)計一個校園導游程序，為來訪的客人提供各種信息查詢服務(wù)。二、 實驗內(nèi)容【問題描述】設(shè)計一個校園導游程序，為來訪的客人提供各種信息查詢服務(wù)?！净疽蟆?(1)設(shè)計你所在學校的校園平面圖，所含景點不少于10個。以圖中頂點表示校內(nèi)各景點，存放景點名稱、代號、簡介等信息；以邊表示路徑，存放路徑長度等相關(guān)信息。 (2)為來訪客人提供圖中任意景點相關(guān)信息的查詢。 (3)為來訪客人提供圖中任意景點的問路查詢，即查詢?nèi)我鈨蓚€景點之間的一個最短的簡單路徑?！緶y試

2、數(shù)據(jù)】由讀者根據(jù)實際情況指定?！緦崿F(xiàn)提示】一般情況下，校園的道路是雙向通行的，可設(shè)校園平面圖是一個無向網(wǎng)。頂點和邊均含有相關(guān)信息?！具x作內(nèi)容】 (1)求校園圖的關(guān)節(jié)點。 (2)提供圖中任意景點問路查詢，即求任意兩個景點之間的所有路徑。 (3)提供校園圖中多個景點的最佳訪問路線查詢，即求途經(jīng)這多個景點的最佳(短)路徑。 (4)校園導游圖的景點和道路的修改擴充功能。 (5)擴充道路信息，如道路類別(車道、人行道等)、沿途景色等級，以至可按客人所需分別查詢?nèi)诵新窂交蜍囆新窂交蛴^景路徑等。 (6)擴充每個景點的鄰接景點的方向等信息，使得路徑查詢結(jié)果能提供詳盡的導向信息。(7)實現(xiàn)校園導游圖的仿真界面。

3、程序代碼及結(jié)果：#include<iostream>#include<iomanip>using namespace std;const int MaxSize=18;const int INFINITY=65535;/最大值無窮class direction;template <class T> class MGraph;template <class T>class VertexNode/定義頭結(jié)點friend class MGraph<T> public:int vex;/頂點名稱T vexname;/頂點名稱T vexinf;

4、/頂點信息direction dir;/存放頂點方位信息的direction類的dir。;class directionpublic:int ln;/存放在方向圖中的橫坐標，表示東西int col;/存放在方向圖中的縱坐標，表示南北;template <class T>class MGraph/定義無向圖的鄰接矩陣public:MGraph(); /構(gòu)造函數(shù)，初始化具有n個頂點的圖void printvexname();/顯示所有景點及景點代號void printvexinf(int i);/顯示代號為i景點的名稱及信息void printroad(int i,int j);/顯示

5、景點ij的最短路徑方案信息void printdir(int i,int j);/顯示景點i到j(luò)的方向信息，如“向東100m，向南200m”VertexNode<T> adjlistMaxSize; /存放景點全部信息的 景點類數(shù)組int vertexNum,arcNum; /圖的頂點數(shù)和邊數(shù)void Root(int p,int q);/遞歸尋找pq間的最短路徑int PathMaxSizeMaxSize,DistMaxSizeMaxSize;/創(chuàng)建Path和Dist分別存放兩點間最短路徑的前驅(qū)節(jié)點，兩點間最短路徑長度int LineMaxSize;/Line存放路徑int kk

6、k;/Line數(shù)組的標記private:T vertexMaxSize; /存放圖中頂點的數(shù)組int arcMaxSizeMaxSize;/存放圖中邊的數(shù)組;*【以下為類的實現(xiàn) 即類函數(shù)的定義】*template <class T>MGraph<T>:MGraph()/a為景點代號，b為景點名稱，c為景點信息，d為景點方位信息的橫坐標，e為景點方位信息的縱坐標/s為存放景點鄰接矩陣信息的一維數(shù)組，根據(jù)其對稱性可以用公式賦值給二維數(shù)組arcint s=0,1,0,0,2,0,0,0,2,0,0,0,2,3,0,0,0,0,4,2,0,0,0,0,0,2,3,0,0,0,0

7、,0,2,3,1,0,0,0,2,0,2,0,0,2,0,4,0,2,0,0,0,0,0,1,0,0,0,0,0,0,0,0,0,0,2,0,1,0,0,0,0,0,0,0,0,0,2,0,0,0,0,0,0,0,0,0,0,3,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,2,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,1,1,0,0,0,0,0,0,0,0,0,0,0,0,0,3,0,0,2,0,0,0,0,0,0,0,0,0,0,0,0,0,4,4,0,0,2,0;int a=0,1,2,3,4,5,6

8、,7,8,9,10,11,12,13,14,15,16,17;char* b="南門","實驗樓","南圖","大活","睿思樓","大禮堂","南4教","知行樓","國交樓","南3教","南2教","南1教","北圖","北3教","北4教","北2教","北1教

9、","北門"char* c="南校區(qū)正門","物理實驗樓","南校區(qū)圖書館","大學生活動中心","教師辦公樓、醫(yī)務(wù)室及留學生公寓","大禮堂，用于舉辦各種文藝演出","南校區(qū)第4教學樓","實習基地，計算機房等","國際交流中心，教職工餐廳","南校區(qū)第3教學樓","南校區(qū)第2教學樓","南校區(qū)第1教學樓","北校區(qū)

10、圖書館","北校區(qū)第3教學樓","北校區(qū)第4教學樓","北校區(qū)第2教學樓","北校區(qū)第1教學樓","北校區(qū)正門"int d=8,6,4,4,1,0,0,1,3,4,6,8,4,3,2,3,5,8;int e=8,8,8,10,8,10,7,6,6,6,6,6,3,1,0,0,0,2;int i,j;vertexNum=18;arcNum=30; for(i=0;i<vertexNum;i+)adjlisti.vex=ai;adjlisti.vexname=bi;adjlisti.

11、vexinf=ci;adjlisti.dir.ln=di;adjlisti.dir.col=ei;for (i=0; i<vertexNum; i+)/初始化鄰接矩陣for (j=0; j<vertexNum; j+)arcij=arcji=s(i*(i+1)/2+j; /根據(jù)s的對稱性，將一維數(shù)組中的數(shù)據(jù)賦給二維數(shù)組arc template<class T>void MGraph<T>:printvexname()int i;for(i=0;i<vertexNum;i+)cout<<adjlisti.vex<<" &

12、quot;<<adjlisti.vexname<<endl;template<class T>void MGraph<T>:printvexinf(int i)cout<<i<<" "<<adjlisti.vexname<<":"<<adjlisti.vexinf<<endl;template<class T>void MGraph<T>:printdir(int i,int j)int dx,nb;/臨時存放i

13、與j之間的南北東西關(guān)系 j在i的哪邊？dx=adjlistj.dir.col-adjlisti.dir.col;nb=adjlistj.dir.ln-adjlisti.dir.ln;if(dx>0)/即j在i的東邊cout<<"向東"<<dx*100<<"m，"elsecout<<"向西"<<dx*(0-100)<<"m，"if(nb>0)/即j在i的南邊cout<<"向南"<<nb*10

14、0<<"m"elsecout<<"向北"<<nb*(0-100)<<"m"template<class T>void MGraph<T>:Root(int p,int q) if (Pathpq>0) Root(p,Pathpq); Root(Pathpq,q); else Linekkk=q; kkk+; template<class T>void MGraph<T>:printroad(int i,int j)int p,q,m,

15、k,item1,item2;for(p=0;p<vertexNum;p+)for(q=0;q<vertexNum;q+)Distpq=arcpq;/鄰接矩陣賦值for(k=0;k<vertexNum;k+) for(p=0;p<vertexNum;p+)if (Distpk>0) for(q=0;q<vertexNum;q+) if (Distkq>0) if (Distpq>Distpk+Distkq)|(Distpq=0)&&(p!=q) Distpq=Distpk+Distkq; Pathpq=k; cout<<

16、"n=n"cout<<"從"<<adjlisti.vexname<<"到"<<adjlistj.vexname<<"的最短路徑為："<<endl;cout<<adjlisti.vexname;kkk=2;Root(i,j);item2=Line2;cout<<"->"printdir(i,item2);cout<<"->"<<adjlistite

17、m2.vexname;for(m=3;m<=kkk-1;m+)item1=Linem;cout<<"->"printdir(item1-1,item1);cout<<"->"<<adjlistitem1.vexname;cout<<endl;cout<<"n=n"*【以下為主函數(shù)】*int funcchoice()/系統(tǒng)功能選擇頁面int choice;cout<<"="<<endl;cout<<&qu

18、ot; 歡迎進入校園導游咨詢平臺"<<endl;cout<<" 1-顯示校園所有景點信息"<<endl;cout<<" 2-查詢校園景點信息"<<endl;cout<<" 3-問路查詢系統(tǒng)"<<endl;cout<<" 4-退出導游資訊平臺"<<endl;cout<<"="<<endl;cout<<"請輸入要選擇的功能號："cin>>choice;return choice;void main()MGraph<char*> mg;int funcchoice();int fc;while(1)fc=funcchoice();if(fc=1)int i;for(i=0;i<mg.vertexNum;i+)mg.printvexinf(i);else if(fc=2)int i;mg.pr