数据结构课程设计-旅游景点咨询系统的设计与实现

1、旅游景点咨询系统的设计与实现一、需求分析1、问题描述创建一个至少有15个点的无向网表示的某个旅游景点的导游图。顶点代表景点，类型为字符串（例如，泰山导游图：“天地广场门”，“十八盘”，“冯玉祥墓”，“桃花峪门”，“中天门”，“南天门”，“玉皇顶”等），弧表示两个景点之间可以直达，弧上的权值表示两个景点之间的路程（公里数），弧上还有到达方法的信息（有步行和索道两种）。建立一个游客咨询系统。2、基本要求a创建图的存储结构。b.输入两个景点名，就可以得到从一个景点到达另一个景点的所有简单路径、相应路径的路程公里数、行走的方法（每一段是步行，还是坐索道）。c输入两个景点名，就可以得到其最短路径，即：路

2、程最短的行进方法；如果两者无路径可通，就得出“两景点不可达的信息”。二、概要设计1 .数据结构本程序需要用到两个结构体，分别为ArcCell和MGraph。2 .程序模块本程序包含两个模块，一个是实现功能的函数的模块，另一个是主函数模块。系统子程序及功能设计本系统共有七个子程序，分别是：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 .系统主要子程序详细设计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出发到y*/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;/建立一个临时的栈/创建一个数组存放路径下标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;跳出本次循环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;记录中间节点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.建立旅游景点咨询系统，根据提示依次输入景点，路径，以及到达方式。-旅锵景点咨询奈统1 .律方号点导满图2,两个景点间的所有简单三两个景点间的最短¥斜至4 .退出请输入功能编号：1陞立景点导游图请输入景点个数以及景点间所有路径的个数（以空相隔开）1516请输入15个景点:光明顶西递天都峰神仙洞迎客松桃花溪齐云山西海大峡谷白际石门峡云谷寺石潭玉扉楼慈

17、光阁卢村请输入1陈景点间的路径,路径间的路程权值以及蹲径间到达方式（以。或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,并输任意的两个景点，可以得到这两个景点间的最短路径，输出最短路径并以此输出到达方式。丽游景点密询系统L建立景点导游图2,两个景点间的所有荷单路径&两人景点间的最短路径4"良出请输入功能编号二3两个景点间的最短路径请输入两八景点

19、（以空格隔开）光明顶云谷寺路径为;光明顶齐云山西海大峡谷桃花溪迎客松云谷寺到达方式:秦道步行索道步行索道4 .退出系统退出程序。I旅看重点百询系疣1 .建立景点导游图2 .两个景点间的所有筒单至M,两人景点间的最短路径4,退出b输入功能编号;4卜青按任意键继续.五、附录1 .旅游景点咨询系统.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出发到y*/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&