數(shù)據(jù)結(jié)構(gòu)課程設(shè)計實驗報告《校園導(dǎo)游咨詢系統(tǒng)》內(nèi)含程序源代碼 運行截圖[方案]

1、上海電力學(xué)院數(shù)據(jù)結(jié)構(gòu)C+課程設(shè)計題目: 校園導(dǎo)游咨詢 學(xué)生姓名： 學(xué) 號： 院系： 專業(yè)年級： 2011年7月1日一、設(shè)計題目校園導(dǎo)游咨詢；1、 實驗?zāi)康?熟練掌握圖的創(chuàng)立及遍歷根本操作算法。2 熟練掌握最短路徑算法。3利用圖的遍歷和最短路徑求解技術(shù)，設(shè)計一個校園導(dǎo)游程序，為來訪的客人提供各種信息查詢效勞。2、 實驗內(nèi)容【問題描述】設(shè)計一個校園導(dǎo)游程序，為來訪的客人提供各種信息查詢效勞。【根本要求】 (1)設(shè)計你所在學(xué)校的校園平面圖，所含景點不少于10個。以圖中頂點表示校內(nèi)各景點，存放景點名稱、代號、簡介等信息；以邊表示路徑，存放路徑長度等相關(guān)信息。 (2)為來訪客人提供圖中任意景點相關(guān)信息的

2、查詢。 (3)為來訪客人提供圖中任意景點的問路查詢，即查詢?nèi)我鈨蓚€景點之間的一個最短的簡單路徑。【測試數(shù)據(jù)】由讀者根據(jù)實際情況指定?！緦崿F(xiàn)提示】一般情況下，校園的道路是雙向通行的，可設(shè)校園平面圖是一個無向網(wǎng)。頂點和邊均含有相關(guān)信息?！具x作內(nèi)容】 (6)擴充每個景點的鄰接景點的方向等信息，使得路徑查詢結(jié)果能提供詳盡的導(dǎo)向信息。二、小組成員分工說明略三、需求分析1運行環(huán)境軟、硬件環(huán)境硬件環(huán)境：windows2000、windows XP、windows7 皆可；軟件環(huán)境：Microsoft (R) Developer Studio (2)2輸入的形式和輸入值的范圍輸入形式：整形數(shù)據(jù)景點代號、路徑長

3、度、地圖上的方位信息，字符串景點名稱及簡介；輸入值范圍：景點代號為：整形017共18個景點路徑長度為：整形110兩景點間距離，以近似1：:100m比例換算，最遠(yuǎn)1km景點名稱字符串長度：整形115景點名稱字符串長度為：字符數(shù)組150對景點進行簡要介紹景點在地圖方位圖上的位置：整形0103輸出的形式描述景點代號、景點名稱、信息的關(guān)聯(lián)以cout形式輸出，告知來訪客人，以便查詢；景點信息查詢結(jié)果的輸出形式為cout字符串；兩景點間最短路徑輸出形式為cout字符串 符號、以及嵌套的printroad函數(shù)以顯示路徑信息及方位信息，方便客人獲取最正確路線；4功能描述 (1)設(shè)計學(xué)校的校園平面圖，所含景點1

4、8個。以圖中頂點表示校內(nèi)各景點，存放景點名稱、代號、簡介等信息；以邊表示路徑，存放路徑長度等相關(guān)信息。(2)為來訪客人提供圖中任意景點相關(guān)信息的查詢。(3)為來訪客人提供圖中任意景點的問路查詢，即查詢?nèi)我鈨蓚€景點之間的一個最短的簡單路徑，并提示出各景點之間的方位關(guān)系，行走方向。5測試數(shù)據(jù)輸入功能選擇號碼，進入各項功能界面；根據(jù)功能界面的提示輸入所要查詢的內(nèi)容：如，在查詢景點功能界面需要根據(jù)提示輸入所需查詢的景點代號；在問路查詢功能界面需要根據(jù)提示輸入起點終點的景點代號。四、概要設(shè)計1抽象數(shù)據(jù)類型定義描述對各類的成員及成員函數(shù)進行抽象描述，參見書或ppt及實驗#include<iostre

5、am>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;/景點信息direction dir;/存放景點方位信息的direction類的di

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

7、顯示景點i到j(luò)的方向信息，如“向東100m，向南200mVertexNode<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 kkk;/在floyed算法中，做Line數(shù)組的標(biāo)記private: T vertex

8、MaxSize; /存放圖中頂點的數(shù)組 int arcMaxSizeMaxSize;/存放圖中邊的數(shù)組;2功能模塊設(shè)計如主程序模塊設(shè)計int funcchoice()/系統(tǒng)功能選擇頁面int choice;cout<<"="<<endl;cout<<" 歡送進入校園導(dǎo)游咨詢平臺"<<endl;cout<<" 1-顯示校園所有景點信息"<<endl;cout<<" 2-查詢校園景點信息"<<endl;cout<<

9、;" 3-問路查詢系統(tǒng)"<<endl;cout<<" 4-退出導(dǎo)游資訊平臺"<<endl;cout<<"="<<endl;cout<<"請輸入要選擇的功能號："cin>>choice;return choice;3模塊層次調(diào)用關(guān)系圖主程序菜單模式問路模塊printroad(int i,int j)查詢信息模塊printvexname()顯示所有景點信息模塊printvexinf(int i)方位信息模塊printdir(int p,

10、int q)最短路徑模塊Floyed遞歸算法Root(int p,int q)返回某景點信息模塊printvexinf(int i)五、詳細(xì)設(shè)計實現(xiàn)概要設(shè)計中定義的所有的類的定義及類中成員函數(shù)，并對主要的模塊寫出偽碼算法。=以下為guide.cpp文件中對所有成員函數(shù)的定義等=#include<iostream>#include<iomanip>#include"guide.h"using namespace std;template <class T>MGraph<T>:MGraph()/a為景點代號，b為景點名稱，c為景點

11、信息，d為景點方位信息的橫坐標(biāo)，e為景點方位信息的縱坐標(biāo)，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,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,

12、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,7,8,9,10,11,12,13,14,15,16,17;char* b="南門","實驗樓","南圖","大活","睿思樓","大禮堂","南4教","知行樓",&

13、quot;國交樓","南3教","南2教","南1教","北圖","北3教","北4教","北2教","北1教","北門"char* c="南校區(qū)正門","物理實驗樓","南校區(qū)圖書館","大學(xué)生活動中心","教師辦公樓、醫(yī)務(wù)室及留學(xué)生公寓","大禮堂，用于舉辦各種文藝演出","

14、南校區(qū)第4教學(xué)樓","實習(xí)基地，計算機房等","國際交流中心，教職工餐廳","南校區(qū)第3教學(xué)樓","南校區(qū)第2教學(xué)樓","南校區(qū)第1教學(xué)樓","北校區(qū)圖書館","北校區(qū)第3教學(xué)樓","北校區(qū)第4教學(xué)樓","北校區(qū)第2教學(xué)樓","北校區(qū)第1教學(xué)樓","北校區(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,

15、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.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ù)

16、組arctemplate<class T>void MGraph<T>:printvexname()int i;for(i=0;i<vertexNum;i+)cout<<adjlisti.vex<<" "<<adjlisti.vexname<<endl;template<class T>void MGraph<T>:printvexinf(int i)cout<<i<<" "<<adjlisti.vexname<

17、<":"<<adjlisti.vexinf<<endl;template<class T>void MGraph<T>:printdir(int i,int j)int dx,nb;/臨時存放i與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，

18、"elsecout<<"向西"<<dx*(0-100)<<"m，"if(nb>0)/即j在i的南邊cout<<"向南"<<nb*100<<"m"elsecout<<"向北"<<nb*(0-100)<<"m"template<class T>void MGraph<T>:Root(int p,int q) if (Pathpq>

19、;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,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&

20、lt;vertexNum;q+) if (Distkq>0) if (Distpq>Distpk+Distkq)|(Distpq=0)&&(p!=q) Distpq=Distpk+Distkq; Pathpq=k; cout<<"n=n"cout<<"從"<<adjlisti.vexname<<"到"<<adjlistj.vexname<<"的最短路徑為："<<endl;cout<<adjli

21、sti.vexname;kkk=2;Root(i,j);item2=Line2;cout<<"->"printdir(i,item2);cout<<"->"<<adjlistitem2.vexname;for(m=3;m<=kkk-1;m+)item1=Linem;cout<<"->"printdir(item1-1,item1);cout<<"->"<<adjlistitem1.vexname;cout<&

22、lt;endl;cout<<"n=n"=以下為main.cpp文件中主函數(shù)的實現(xiàn)=#include<iostream>#include"guide.cpp"using namespace std;int funcchoice()/系統(tǒng)功能選擇頁面int choice;cout<<"="<<endl;cout<<" 歡送進入校園導(dǎo)游咨詢平臺"<<endl;cout<<" 1-顯示校園所有景點信息"<<e

23、ndl;cout<<" 2-查詢校園景點信息"<<endl;cout<<" 3-問路查詢系統(tǒng)"<<endl;cout<<" 4-退出導(dǎo)游資訊平臺"<<endl;cout<<"="<<endl;cout<<"請輸入要選擇的功能號："cin>>choice;return choice;void main()MGraph<char*> mg;int funcchoice(

24、);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.printvexname();cout<<endl<<"請輸入所要查詢景點代號："cin>>i;mg.printvexinf(i);else if(fc=3)int i,j;mg.printvexname();cout<<"請輸入兩景點代號我們將把最短路線反應(yīng)予您："cin>

25、;>i>>j;mg.printroad(i,j);else if(fc=4)break;elsecout<<"輸入有誤，請重新輸入！"<<endl;六、調(diào)試分析遇到的問題及解決的方法：在調(diào)試過程中，最常見到的問題有以下幾種：1、忘記調(diào)用函數(shù)類模塊template<class T>，有些類中或者函數(shù)中涉及函數(shù)類模塊的調(diào)用，但忘記標(biāo)注會導(dǎo)致編譯錯誤。我的解決方法是在寫程序中，一旦寫到“T，就立刻到前面找類模塊的定義，如果發(fā)現(xiàn)沒寫就趕緊補上；2、容易混淆指針和對象，假設(shè)將p定義為指針，那么調(diào)用p所指向的類的函數(shù)時應(yīng)該用“-&g

26、t;，假設(shè)p為對象那么可直接用“.調(diào)用類中的共有接口函數(shù)。針對該問題，我的解決方法是在紙上寫明各個類及類中的成員函數(shù)，標(biāo)清類型等，這樣一目了然，寫程序的時候查對起來也方便；3、容易將類或函數(shù)名中的大寫字母錯寫成小寫字母，有時甚至導(dǎo)致編譯正確，連接錯誤，error不能指出錯誤的情況發(fā)生，使程序查對過程較長，我的解決方法是，以后在編程中應(yīng)盡量使用統(tǒng)一的書寫形式，如全部大寫或全部小寫；4、“=的應(yīng)用，很多時候是不能直接用“=賦值的，要注意等號兩邊的類型是否一致，是否可以用=賦值等；5、雖然已經(jīng)養(yǎng)成了在寫多句函數(shù)的時候，先把花括號一起打上，但改程序的過程中還是會有粗心導(dǎo)致花括號不成對等情況出現(xiàn)，編譯中

27、自己很難根據(jù)error提示找到問題所在，是同學(xué)幫我檢查到的，這提醒我在日后檢查error時也要注意花括號是否完整，而且我的一個習(xí)慣有益于這個錯誤的查找，那就是格式對齊，格式對齊可以讓程序一目了然，檢查花括號也變得簡單輕松很多；6、運行程序后對程序進行改動，改動后運行程序時應(yīng)將之前的運行界面關(guān)閉才可以繼續(xù)；Floyed算法的時間空間復(fù)雜性分析： 本程序中的Floyed算法對鄰接矩陣每一個元素都進行了NN即為景點個數(shù)遍比擬，所以時間復(fù)雜度是O(N3)；存放兩點間最短路徑前驅(qū)結(jié)點的path矩陣占用了N*N的空間，所以時間復(fù)雜度是O(N2)。經(jīng)驗體會：在涉及矩陣等算法的時候，一定要注意下標(biāo)是否是0開始

28、的，對稱的鄰接矩陣賦值給arcij的同時不要忘記賦值給arcji。七、 用戶使用說明詳細(xì)列出每一步的操作說明。一翻開Microsoft (R) Developer Studio二新建一個工程三選擇“an empty project并單擊“完成四在工程內(nèi)新建一個header file用于存放類的定義五新建一個source file用于存放類的實現(xiàn)，函數(shù)定義六新建一個source file用于編寫主函數(shù)八、 測試結(jié)果構(gòu)造函數(shù)中已經(jīng)將校園景點的代號、名稱、簡介等信息全部設(shè)好，只需根據(jù)主頁面提示輸入功能號，即可查詢景點信息；在查詢校園景點信息時，頁面會顯示各個景點的名稱及代號，方便來訪者查詢景點使用問

29、路查詢系統(tǒng)時，頁面顯示各景點代號及名稱，方便來訪者輸入查詢信息。在該模塊中，還設(shè)計了各景點在地圖上的分布矩陣，根據(jù)景點的方位信息，輸出兩景點間的距離方向信息可以讓來訪者更容易找到這些景點及線路使用完程序后 輸入4號功能鍵即可退出附錄：代碼(ps:該校園導(dǎo)游咨詢系統(tǒng)沒有輸入值，所有信息是都在class MGraph的構(gòu)造函數(shù)中傳輸?shù)?，且校園景點信息皆為【上海電力學(xué)院】景點信息。請大家注意，直接從文章copy到visual stutio中會出現(xiàn)中文字符，注意刪除，推薦大家在一行語句的分號后面，點出光標(biāo)，按一下delete鍵，然后按一下enter鍵，完成visual stutio的自動對齊，這樣程序

30、看起來一目了然，更易于操作和更改)【問題描述】設(shè)計一個校園導(dǎo)游程序，為來訪的客人提供各種信息查詢效勞?！靖疽蟆?1)設(shè)計你所在學(xué)校的校園平面圖，所含景點不少于10個。以圖中頂點表示校內(nèi)各景點，存放景點名稱、代號、簡介等信息；以邊表示路徑，存放路徑長度等相關(guān)信息。(2)為來訪客人提供圖中任意景點相關(guān)信息的查詢。(3)為來訪客人提供圖中任意景點的問路查詢，即查詢?nèi)我鈨蓚€景點之間的一個最短的簡單路徑?！具x作內(nèi)容】(6)擴充每個景點的鄰接景點的方向等信息，使得路徑查詢結(jié)果能提供詳盡的導(dǎo)向信息。*【以下為類的定義】*#include<iostream>#include<iomani

31、p>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;/頂點信息direction dir;/存放頂點方位信息的direction類的dir。;class

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

33、向信息，如“向東100m，向南200mVertexNode<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 kkk;/Line數(shù)組的標(biāo)記private:T vertexMaxSize; /存放圖中頂點的數(shù)組int

34、arcMaxSizeMaxSize;/存放圖中邊的數(shù)組;*【以下為類的實現(xiàn) 即類函數(shù)的定義】*template <class T>MGraph<T>:MGraph()/a為景點代號，b為景點名稱，c為景點信息，d為景點方位信息的橫坐標(biāo)，e為景點方位信息的縱坐標(biāo)/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,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,

35、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,7,8,9,10,11,12,13,14,15,16,17;char* b="南門&quo

36、t;,"實驗樓","南圖","大活","睿思樓","大禮堂","南4教","知行樓","國交樓","南3教","南2教","南1教","北圖","北3教","北4教","北2教","北1教","北門"char* c="南校區(qū)正門",&quo

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

38、,"北校區(qū)第2教學(xué)樓","北校區(qū)第1教學(xué)樓","北校區(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.vexinf=ci;adjlisti.dir.ln=di;adjlisti.dir.col=ei;fo

39、r (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<<" "<<adjlisti.vexname<<endl;template&

40、lt;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與j之間的南北東西關(guān)系 j在i的哪邊？dx=adjlistj.dir.col-adjlisti.dir

41、.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*100<<"m"elsecout<<"向北"

42、;<<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,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=