數據結構課程設計-旅游景點咨詢系統(tǒng)的設計與實現

1、旅游景點咨詢系統(tǒng)的設計與實現一、需求分析1、問題描述創(chuàng)建一個至少有15個點的無向網表示的某個旅游景點的導游圖。頂點代表景點，類型為字符串（例如，泰山導游圖：“天地廣場門”，“十八盤”，“馮玉祥墓”，“桃花峪門”，“中天門”，“南天門”，“玉皇頂”等），弧表示兩個景點之間可以直達，弧上的權值表示兩個景點之間的路程（公里數），弧上還有到達方法的信息（有步行和索道兩種）。建立一個游客咨詢系統(tǒng)。2、基本要求a創(chuàng)建圖的存儲結構。b.輸入兩個景點名，就可以得到從一個景點到達另一個景點的所有簡單路徑、相應路徑的路程公里數、行走的方法（每一段是步行，還是坐索道）。c輸入兩個景點名，就可以得到其最短路徑，即：路

2、程最短的行進方法；如果兩者無路徑可通，就得出“兩景點不可達的信息”。二、概要設計1 .數據結構本程序需要用到兩個結構體，分別為ArcCell和MGraph。2 .程序模塊本程序包含兩個模塊，一個是實現功能的函數的模塊，另一個是主函數模塊。系統(tǒng)子程序及功能設計本系統(tǒng)共有七個子程序，分別是：intLocateVex(MGraphG,VertexTypeu)得到頂點u的序號voidCreateDN(MGraph*G)建立景點間的無向網VertexType*GetVex(MGraphG,intv)/根據頂點序號返回頂點值intFirstAdjVex(MGraphG,VertexTypev)/l回v的第

3、一個鄰接頂點的序號intNextAdjVex(MGraphG,VertexTypev,VertexTypew返回v的(相對于w的)下一個鄰接頂點的序號voidSimpleway(MGraph&m,char*str,char*buf)/求任意兩個景點之間的所有簡單路徑intMinway(MGraph&m,char*str,char*buf)/求兩頂點間的最短路徑3 .各模塊之間的調用關系以及算法設計函數CreateDN調用函數LocateVex函數Simpleway調用函數LocateVex函數Minway調用函數LocateVexGetVex,FirstAdjVex,NextA

4、djVex主函數調用函數CreateDN,Simpleway,Minway。三、詳細設計1 .數據類型定義typedefstructVRTypeadj;intinfo;ArcCell,AdjMatrixMAX_VERTEX_NUMMAX_VERTEX_NUM;typedefstructVertexTypevexsMAX_VERTEX_NUM;AdjMatrixarcs;intvexnum,arcnum;MGraph;2 .系統(tǒng)主要子程序詳細設計a.voidCreateDN(MGraph*G)/*采用數組(鄰接矩陣)表示法，構造有向網G*/inti,j,k,w,c;charsMAX_INFO,*

5、info;VertexTypeva,vb;printf("請輸入景點個數以及景點間所有路徑的個數(以空格隔開)");scanf("%d%d",&(*G).vexnum,&(*G).arcnum);printf("請輸入%d個景點:n",(*G).vexnum);for(i=0;i<(*G).vexnum;+i)/*構造頂點向量*/scanf("%s",(*G).vexsi);for(i=0;i<(*G).vexnum;+i)/*初始化鄰接矩陣*/for(j=0;j<(*G).vex

6、num;+j)(*G).arcsij.adj=INFINITY;/*網*/(*G).=NULL;printf("請輸入%d條景點間的路徑，路徑間的路程權值以及路徑間到達方式(以0或1來表示到達方式，步行:0,索道:1,如:光明頂迎客松301):n",(*G).arcnum);for(k=0;k<(*G).arcnum;+k)scanf("%s%s%d%d*c",va,vb,&w,&c);/*%*c乞掉回車符*/i=LocateVex(*G,va);j=LocateVex(*G,vb);(*G).arcsij.a

7、dj=(*G).arcsji.adj=w;/*有向網*/(*G).=(*G).=c;/*有向*/b.voidSimpleway(MGraph&m,char*str,char*buf)/*求任意兩個景點之間的所有簡單路徑*/for(inti=0;i<m.vexnum;i+)(visitedi=false;)intx=LocateVex(m,str);inty=LocateVex(m,buf);/*從x出發(fā)到y(tǒng)*/stack<int>s;s.push(x);visitedx=true;inti=0;intz=0;/表示沒有找到這

8、兩個點之間有路徑while(!s.empty()(intflag=0;/取棧頂元素intt=s.top();for(;i<m.vexnum;i+)(if(m.arcsti.adj!=INFINITY&&visitedi=false)(s.push(i);flag=1;visitedi=true;/*找到簡單路徑*/if(s.top()=y)/到達終點(z=1;/找到這樣的路徑cout<<"一條簡單路徑為:"<<endl;(stack<int>s2;/建立一個臨時的棧/創(chuàng)建一個數組存放路徑下標int*way=newin

9、ts.size();intcount=0;while(!s.empty()(s2.push(s.top();s.pop();)還原s同時輸出路徑while(!s2.empty()(cout<<m.vexss2.top()<<""waycount+=s2.top();s.push(s2.top();s2.pop();計算路徑長度，給出到達的方式intnum=0;cout<<"到達方式：”；for(intk=0;k<s.size()-1;k+)intx1=LocateVex(m,m.vexswayk);inty1=Locate

10、Vex(m,m.vexswayk+1);num+=m.arcsx1y1.adj;if(=0)cout<<"步行"<<""elsecout<<"索道"<<""cout<<"路程:"<<num<<endl;cout<<endl;/出棧intp=s.top();visitedp=false;s.pop();從p開始接著訪問后面的鄰接點i=p+1;break;跳出本次循環(huán)i=0;

11、break;if(flag=0)/出棧intp=s.top();visitedp=false;s.pop();從p開始接著訪問后面的鄰接點i=p+1;)if(z=0)(cout<<"兩景點不可達"<<endl;)Minway(MGraph&m,char*str,char*buf)求兩頂點間的最短路徑(intx=LocateVex(m,str);inty=LocateVex(m,buf);/分配路徑相關信息的存儲空間int*road=newint*m.vexnum;for(inti=0;i<m.vexnum;i+)(roadi=

12、newintm.vexnum;)/初始化for(inti=0;i<m.vexnum;i+)(for(intj=0;j<m.vexnum;j+)(if(j=0)(roadij=x;)else(roadij=-1;)for(inti=0;i<m.vexnum;i+)(/while(find_sx=true)find_si=false;lengthi=m.arcsxi.adj;if(m.arcsxi.adj!=INFINITY)(roadi1=i;find_sx=true;lengthx=0;rigth_lengthx=0;for(intj=1;j<m.vexnum;j+)(

13、intpose=find_min_length(m,length);(一一intz=0;記錄找到它的路徑while(roadposez!=-1&&z<=m.vexnum)(z+;cout<<"min_length="<<lengthpose<<endl;rigth_lengthpose=lengthpose;/M路徑最短的關聯的另一個頂點加入已找到路徑的數組中find_spose=true;/更新最短路徑for(inti=0;i<m.vexnum;i+)(/i點還沒有找到最短路徑if(find_si=false

14、&&m.arcsposei.adj+lengthpose<lengthi).lengthi=m.arcsposei.adj+lengthpose;記錄中間節(jié)點intz=0;記錄找到它的路徑while(roadposez!=-1)z+;/*移位再插入，用pose更新*/(1)復制for(intk=0;k<z;k+)roadik=roadposek;)roadiz=i;)cout<<endl;if(roady1=-1)(cout<<"兩景點不可達"<<endl;return-1;)else(cout<<

15、"最短路徑為："；intcount=0;while(roadycount!=-1&&count<m.vexnum)(cout<<m.vexsroadycount<<""count+;)cout<<"到達方式：”；for(inti=0;i<count-1;i+)(intx1=LocateVex(m,m.vexsroadyi);inty1=LocateVex(m,m.vexsroadyi+1);if(=0)cout<<"步行"

16、;<<""elsecout<<"索道"<<"")cout<<endl;returnrigth_lengthy;).)四、測試與分析1.建立旅游景點咨詢系統(tǒng)，根據提示依次輸入景點，路徑，以及到達方式。-旅鏘景點咨詢奈統(tǒng)1 .律方號點導滿圖2,兩個景點間的所有簡單三兩個景點間的最短¥斜至4 .退出請輸入功能編號：1陞立景點導游圖請輸入景點個數以及景點間所有路徑的個數（以空相隔開）1516請輸入15個景點:光明頂西遞天都峰神仙洞迎客松桃花溪齊云山西海大峽谷白際石門峽云谷寺石潭玉扉樓慈

17、光閣盧村請輸入1陳景點間的路徑,路徑間的路程權值以及蹲徑間到達方式（以?；?未表示到達方式,步行：0,索道：L如:光明頂迎客松301）:光明頂西遞50西遞天都峰50天都峰神仙閣151神仙閣迎客松51迎客松電訛溪e。光明頂齊云山101齊云山西海大峽谷5U酉海大始桃花溪51迎客松白際30坡狗拼音輸入法羋：西海大峽谷桃花溪51迎客松白際30白際石門峽20石門峽云谷寺W1迎客松云谷寺71桃花榛石潭101石潭玉屏樓E0石潭慈光閣30慈光閣盧村212.求兩個景點間的所有簡單路徑在主菜單下選2,并輸入任意兩個景點名稱，可以得到這兩個景點間的所有簡單路徑。L建立景點導游圖2,兩個景點間的所有苣單路徑&

18、兩個景點間的最短路徑文退出請輸入功能編號：2個景點間的所有簡單路徑請輸入兩個景點、空珞隔開）光明頂云谷寺條簡單路徑為：光明頂齊云山西海大峽谷桃花溪迎客松白際石門峽云谷寺到達方式二道步行索道步行步行步行索道路程：£一條簡單路徑為：光明頂齊云山西海大峽谷桃花浮迎客松云谷寺到達方式:索道步行索道一行索道路程和3.求兩個頂點間的最短路徑在主菜單下選3,并輸任意的兩個景點，可以得到這兩個景點間的最短路徑，輸出最短路徑并以此輸出到達方式。麗游景點密詢系統(tǒng)L建立景點導游圖2,兩個景點間的所有荷單路徑&兩人景點間的最短路徑4"良出請輸入功能編號二3兩個景點間的最短路徑請輸入兩八景點

19、（以空格隔開）光明頂云谷寺路徑為;光明頂齊云山西海大峽谷桃花溪迎客松云谷寺到達方式:秦道步行索道步行索道4 .退出系統(tǒng)退出程序。I旅看重點百詢系疣1 .建立景點導游圖2 .兩個景點間的所有筒單至M,兩人景點間的最短路徑4,退出b輸入功能編號;4卜青按任意鍵繼續(xù).五、附錄1 .旅游景點咨詢系統(tǒng).h#include<iostream>#include<string>#include<stack>usingnamespacestd;# defineMAX_NAME50/*頂點字符串的最大長度+1*/# defineMAX_INFO50/*相關信息字符串的最大長度+

20、1*/typedefintVRType;typedefcharVertexTypeMAX_NAME;# defineINFINITY10000# defineMAX_VERTEX_NUM20typedefstructVRTypeadj;intinfo;ArcCell,AdjMatrixMAX_VERTEX_NUMMAX_VERTEX_NUM;typedefstructVertexTypevexsMAX_VERTEX_NUM;AdjMatrixarcs;intvexnum,arcnum;MGraph;intLocateVex(MGraphG,VertexTypeu)/*初始條件：圖G存在,u和G

21、中頂點有相同特征*/*操作結果:若G中存在頂點u,則返回該頂點在圖中位置；否則返回-1*/inti;for(i=0;i<G.vexnum;+i)if(strcmp(u,G.vexsi)=0)returni;return-1;voidCreateDN(MGraph*G)/*采用數組(鄰接矩陣)表示法，構造有向網G*/inti,j,k,w,c;charsMAX_INFO,*info;VertexTypeva,vb;printf("請輸入景點個數以及景點間所有路徑的個數(以空格隔開)");scanf("%d%d",&(*G).vexnum,&am

22、p;(*G).arcnum);printf("請輸入%d個景點:n",(*G).vexnum);for(i=0;i<(*G).vexnum;+i)/*構造頂點向量*/scanf("%s",(*G).vexsi);for(i=0;i<(*G).vexnum;+i)/*初始化鄰接矩陣*/for(j=0;j<(*G).vexnum;+j)(*G).arcsij.adj=INFINITY;/*網*/(*G).=NULL;printf("請輸入%d條景點間的路徑，路徑間的路程權值以及路徑間到達方式(以0或1來表示到

23、達方式，步行:0,索道:1,如:光明頂迎客松301):n",(*G).arcnum);for(k=0;k<(*G).arcnum;+k)scanf("%s%s%d%d*c”,va,vb,&w,&c);/*%*c乞掉回車符*/i=LocateVex(*G,va);j=LocateVex(*G,vb);(*G).arcsij.adj=(*G).arcsji.adj=w;/*有向網*/(*G).=(*G).=c;/*有向*/VertexType*GetVex(MGraphG,intv)/*初始條件：圖G存在，v是G

24、中某個頂點的序號。操作結果：返回v的值*/if(v>=G.vexnum|v<0)exit(0);return&G.vexsv;intFirstAdjVex(MGraphG,VertexTypev)/*初始條件：圖G存在,v是G中某個頂點*/*操作結果：返回v的第一個鄰接頂點的序號。若頂點在G中沒有鄰接頂點，則返回-1*/inti,j=0,k;k=LocateVex(G,v);/*k為頂點v在圖G中的序號*/j=INFINITY;for(i=0;i<G.vexnum;i+)if(G.arcski.adj!=j)returni;return-1;intNextAdjVex

25、(MGraphG,VertexTypev,VertexTypew)/*初始條件：圖G存在,v是G中某個頂點，w是v的鄰接頂點*/*操作結果：返回v的(相對于w的)下一個鄰接頂點的序號/*若w是v的最后一個鄰接頂點，則返回-1*/inti,j=0,k1,k2;k1=LocateVex(G,v);/*k1為頂點v在圖G中的序號*/k2=LocateVex(G,w);/*k2為頂點w在圖G中的序號*/j=INFINITY;for(i=k2+1;i<G.vexnum;i+)if(G.arcsk1i.adj!=j)returni;return-1;)boolvisitedMAX_NAME;void

26、Simpleway(MGraph&m,char*str,char*buf)/*求任意兩個景點之間的所有簡單路徑*/for(inti=0;i<m.vexnum;i+)visitedi=false;)intx=LocateVex(m,str);inty=LocateVex(m,buf);/*從x出發(fā)到y(tǒng)*/stack<int>s;s.push(x);visitedx=true;inti=0;intz=0;/表示沒有找到這兩個點之間有路徑while(!s.empty()intflag=0;/取棧頂元素intt=s.top();for(;i<m.vexnum;i+)if(m.arcsti.adj!=INFINITY&