綜合實(shí)驗(yàn)十二校園導(dǎo)游咨詢(xún)

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

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

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

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

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

6、k;/Line數(shù)組的標(biāo)記private:T vertexMaxSize; /存放圖中頂點(diǎn)的數(shù)組int arcMaxSizeMaxSize;/存放圖中邊的數(shù)組;*【以下為類(lèi)的實(shí)現(xiàn) 即類(lèi)函數(shù)的定義】*template <class T>MGraph<T>:MGraph()/a為景點(diǎn)代號(hào)，b為景點(diǎn)名稱(chēng)，c為景點(diǎn)信息，d為景點(diǎn)方位信息的橫坐標(biāo)，e為景點(diǎn)方位信息的縱坐標(biāo)/s為存放景點(diǎn)鄰接矩陣信息的一維數(shù)組，根據(jù)其對(duì)稱(chēng)性可以用公式賦值給二維數(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="南門(mén)","實(shí)驗(yàn)樓","南圖","大活","睿思樓","大禮堂","南4教","知行樓","國(guó)交樓","南3教","南2教","南1教","北圖","北3教","北4教","北2教","北1教

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

10、圖書(shū)館","北校區(qū)第3教學(xué)樓","北校區(qū)第4教學(xué)樓","北校區(qū)第2教學(xué)樓","北校區(qū)第1教學(xué)樓","北校區(qū)正門(mén)"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的對(duì)稱(chēng)性，將一維數(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;/臨時(shí)存放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)功能選擇頁(yè)面int choice;cout<<"="<<endl;cout<<&qu

18、ot; 歡迎進(jìn)入校園導(dǎo)游咨詢(xún)平臺(tái)"<<endl;cout<<" 1-顯示校園所有景點(diǎn)信息"<<endl;cout<<" 2-查詢(xún)校園景點(diǎn)信息"<<endl;cout<<" 3-問(wèn)路查詢(xún)系統(tǒng)"<<endl;cout<<" 4-退出導(dǎo)游資訊平臺(tái)"<<endl;cout<<"="<<endl;cout<<"請(qǐng)輸入要選擇的功能號(hào)："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