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

旅游景点咨询系统的设计与实现一、需求分析1、问题描述创建一个至少有15个点的无向网表示的某个旅游景点的导游图。顶点代表景点,类型为字符串（例如，泰山导游图：“天地广场门”，“十八盘”，“冯玉祥墓”，“桃花峪门”，“中天门”，“南天门”，“玉皇顶”等），弧表示两个景点之间可以直达，弧上的权值表示两个景点之间的路程（公里数），弧上还有到达方法的信息（有步行和索道两种）。建立一个游客咨询系统。2、基本要求a. 创建图的存储结构。b. 输入两个景点名，就可以得到从一个景点到达另一个景点的所有简单路径、相应路径的路程公里数、行走的方法（每一段是步行，还是坐索道）。c. 输入两个景点名，就可以得到其最短路径，即：路程最短的行进方法；如果两者无路径可通，就得出“两景点不可达的信息”。二、概要设计1.数据结构本程序需要用到两个结构体，分别为ArcCell和MGraph。2.程序模块本程序包含两个模块，一个是实现功能的函数的模块，另一个是主函数模块。系统子程序及功能设计本系统共有七个子程序，分别是：int LocateVex(MGraph G,VertexType u)/得到顶点u的序号void CreateDN(MGraph *G)/建立景点间的无向网VertexType* GetVex(MGraph G,int v)/根据顶点序号返回顶点值int FirstAdjVex(MGraph G,VertexType v)/ 返回v的第一个邻接顶点的序号int NextAdjVex(MGraph G,VertexType v,VertexType w)/ 返回v的(相对于w的)下一个邻接顶点的序号void Simpleway(MGraph& m,char *str,char *buf)/求任意两个景点之间的所有简单路径int Minway(MGraph& m,char *str,char *buf)/求两顶点间的最短路径3. 各模块之间的调用关系以及算法设计函数CreateDN调用函数LocateVex函数Simpleway调用函数LocateVex函数Minway调用函数LocateVex， GetVex，FirstAdjVex，NextAdjVex主函数调用函数CreateDN，Simpleway，Minway。三、详细设计1.数据类型定义typedef struct VRType adj; int info; ArcCell,AdjMatrixMAX_VERTEX_NUMMAX_VERTEX_NUM;typedef struct VertexType vexsMAX_VERTEX_NUM; AdjMatrix arcs; int vexnum,arcnum; MGraph;2.系统主要子程序详细设计a.void CreateDN(MGraph *G) /* 采用数组(邻接矩阵)表示法,构造有向网G */ int i,j,k,w,c; char sMAX_INFO,*info; VertexType va,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).vexnum;+j) (*G).arcsij.adj=INFINITY; /* 网 */ (*G).=NULL; printf(请输入%d条景点间的路径,路径间的路程权值以及路径间到达方式(以0或1来表示到达方式,步行:0,索道:1,如:光明顶 迎客松 30 1): 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; /* 有向 */ b.void Simpleway(MGraph& m,char *str,char *buf)/*求任意两个景点之间的所有简单路径*/for(int i=0;im.vexnum;i+)visitedi=false;int x=LocateVex(m,str);int y=LocateVex(m,buf);/*从x出发到y*/stacks;s.push(x);visitedx=true;int i=0;int z=0;/表示没有找到这两个点之间有路径while(!s.empty()int flag=0;/取栈顶元素 int t=s.top();for(;im.vexnum;i+)if(m.arcsti.adj != INFINITY & visitedi=false)s.push(i);flag=1; visitedi=true;/*找到简单路径*/ if(s.top()=y)/到达终点 z=1;/找到这样的路径 cout一条简单路径为:endl;stacks2;/建立一个临时的栈/创建一个数组存放路径下标int *way=new ints.size();int count=0;while(!s.empty()s2.push(s.top();s.pop();/还原s同时输出路径while(!s2.empty()coutm.vexss2.top() ;waycount+=s2.top();s.push(s2.top();s2.pop();/计算路径长度，给出到达的方式int num=0;cout 到达方式:;for(int k=0;ks.size()-1;k+)int x1=LocateVex(m,m.vexswayk);int y1=LocateVex(m,m.vexswayk+1);num+=m.arcsx1y1.adj;if(=0)cout步行 ;elsecout索道 ;cout路程:numendl;coutendl; /出栈 int p=s.top(); visitedp=false; s.pop(); /从p开始接着访问后面的邻接点 i=p+1;break; /跳出本次循环i=0;break;if(flag=0)/出栈int p=s.top();visitedp=false;s.pop();/从p开始接着访问后面的邻接点i=p+1;if(z=0)cout两景点不可达endl; Minway(MGraph& m,char *str,char *buf)/求两顶点间的最短路径int x=LocateVex(m,str);int y=LocateVex(m,buf);/分配路径相关信息的存储空间int *road=new int*m.vexnum;for(int i=0;im.vexnum;i+)roadi=new intm.vexnum;/初始化for(int i=0;im.vexnum;i+)for(int j=0;jm.vexnum;j+)if(j=0)roadij=x;elseroadij=-1;for(int i=0;im.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(int j=1;jm.vexnum;j+)int pose=find_min_length(m,length);int z=0;/记录找到它的路径while(roadposez!=-1&z=m.vexnum)z+;/coutmin_length=lengthposeendl;rigth_lengthpose=lengthpose; /将路径最短的关联的另一个顶点加入已找到路径的数组中 find_spose=true; /更新最短路径 for(int i=0;im.vexnum;i+) /i点还没有找到最短路径 if(find_si=false & m.arcsposei.adj + lengthpose lengthi) lengthi=m.arcsposei.adj + lengthpose; /记录中间节点 int z=0; /记录找到它的路径 while(roadposez!=-1) z+; /*移位再插入,用pose更新*/ /(1)复制 for(int k=0;kz;k+) roadik=roadposek; roadiz=i; coutendl;if(roady1=-1)cout两景点不可达endl;return -1;elsecout最短路径为:;int count=0;while(roadycount!=-1 & countm.vexnum)coutm.vexsroadycount ;count+;cout 到达方式:;for(int i=0;icount-1;i+)int x1=LocateVex(m,m.vexsroadyi);int y1=LocateVex(m,m.vexsroadyi+1);if(=0)cout步行 ;elsecout索道 ;coutendl;return rigth_lengthy;四、测试与分析1.建立旅游景点咨询系统，根据提示依次输入景点，路径，以及到达方式。 2.求两个景点间的所有简单路径在主菜单下选2，并输入任意两个景点名称，可以得到这两个景点间的所有简单路径。 3.求两个顶点间的最短路径 在主菜单下选3，并输任意的两个景点，可以得到这两个景点间的最短路径，输出最短路径并以此输出到达方式。4.退出系统退出程序。五、附录1.旅游景点咨询系统.h#include#include#includeusing namespace std;#define MAX_NAME 50 /* 顶点字符串的最大长度+1 */#define MAX_INFO 50 /* 相关信息字符串的最大长度+1 */typedef int VRType;typedef char VertexTypeMAX_NAME;#define INFINITY 10000 #define MAX_VERTEX_NUM 20 typedef struct VRType adj; int info; ArcCell,AdjMatrixMAX_VERTEX_NUMMAX_VERTEX_NUM;typedef struct VertexType vexsMAX_VERTEX_NUM; AdjMatrix arcs; int vexnum,arcnum; MGraph;int LocateVex(MGraph G,VertexType u) /* 初始条件:图G存在,u和G中顶点有相同特征 */ /* 操作结果:若G中存在顶点u,则返回该顶点在图中位置;否则返回-1 */ int i; for(i=0;iG.vexnum;+i) if(strcmp(u,G.vexsi)=0) return i; return -1;void CreateDN(MGraph *G) /* 采用数组(邻接矩阵)表示法,构造有向网G */ int i,j,k,w,c; char sMAX_INFO,*info; VertexType va,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).vexnum;+j) (*G).arcsij.adj=INFINITY; /* 网 */ (*G).=NULL; printf(请输入%d条景点间的路径,路径间的路程权值以及路径间到达方式(以0或1来表示到达方式,步行:0,索道:1,如:光明顶 迎客松 30 1): n,(*G).arcnum); for(k=0;k=G.vexnum|v0) exit(0); return &G.vexsv; int FirstAdjVex(MGraph G,VertexType v) /* 初始条件: 图G存在,v是G中某个顶点 */ /* 操作结果: 返回v的第一个邻接顶点的序号。若顶点在G中没有邻接顶点,则返回-1 */ int i,j=0,k; k=LocateVex(G,v); /* k为顶点v在图G中的序号 */ j=INFINITY; for(i=0;iG.vexnum;i+) if(G.arcski.adj!=j) return i; return -1; int NextAdjVex(MGraph G,VertexType v,VertexType w) /* 初始条件: 图G存在,v是G中某个顶点,w是v的邻接顶点 */ /* 操作结果: 返回v的(相对于w的)下一个邻接顶点的序号, */ /* 若w是v的最后一个邻接顶点,则返回-1 */ int i,j=0,k1,k2; k1=LocateVex(G,v); /* k1为顶点v在图G中的序号 */ k2=LocateVex(G,w); /* k2为顶点w在图G中的序号 */ j=INFINITY; for(i=k2+1;iG.vexnum;i+) if(G.arcsk1i.adj!=j) return i; return -1;bool visitedMAX_NAME;void Simpleway(MGraph& m,char *str,char *buf)/*求任意两个景点之间的所有简单路径*/for(int i=0;im.vexnum;i+)visitedi=false;int x=LocateVex(m,str);int y=LocateVex(m,buf);/*从x出发到y*/stacks;s.push(x);visitedx=true;int i=0;int z=0;/表示没有找到这两个点之间有路径while(!s.empty()int flag=0;/取栈顶元素 int t=s.top();for(;im.vexnum;i+)if(m.arcsti.adj != INFINITY & visitedi=false)s.push(i);flag=1; visitedi=true;/*找到简单路径*/ if(s.top()=y)/到达终点 z=1;/找到这样的路径 cout一条简单路径为:endl;stacks2;/建立一个临时的栈/创建一个数组存放路径下标int *way=new ints.size();int count=0;while(!s.empty()s2.push(s.top();s.pop();/还原s同时输出路径while(!s2.empty()coutm.vexss2.top() ;waycount+=s2.top();s.push(s2.top();s2.pop();/计算路径长度，给出到达的方式int num=0;cout 到达方式:;for(int k=0;ks.size()-1;k+)int x1=LocateVex(m,m.vexswayk);int y1=LocateVex(m,m.vexswayk+1);num+=m.arcsx1y1.adj;if(=0)cout步行 ;elsecout索道 ;cout路程:numendl;coutendl; /出栈 int p=s.top(); visitedp=false; s.pop(); /从p开始接着访问后面的邻接点 i=p+1;break; /跳出本次循环i=0;break;if(flag=0)/出栈int p=s.top();visitedp=false;s.pop();/从p开始接着访问后面的邻接点i=p+1;if(z=0)cout两景点不可达endl;bool find_sMAX_NAME;/标记是否找到最短路径int lengthMAX_NAME;/记录最短路径int rigth_lengthMAX_NAME;int find_min_length(MGraph &m,int *a)int x=0;while(find_sx=true)x+;for(int i=1;iai & find_si=false)x=i;return x;int Minway(MGraph& m,char *str,char *buf)/求两顶点间的最短路径int x=LocateVex(m,str);int y=LocateVex(m,buf);/分配路径相关信息的存储空间int *road=new int*m.vexnum;for(int i=0;im.vexnum;i+)roadi=new intm.vexnum;/初始化for(int i=0;im.vexnum;i+)for(int j=0;jm.vexnum;j+)if(j=0)roadij=x;elseroadij=-1;for(int i=0;im.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(int j=1;jm.vexnum;j+)int pose=find_min_length(m,length);int z=0;/记录找到它的路径while(roadposez!=-1&z=m.vexnum)z+;/coutmin_length=lengthposeendl;rigth_lengthpose=lengthpose; /将路径最短的关联的另一个顶点加入已找到路径的数组中 find_spose=true; /更新最短路径 for(int i=0;im.vexnum;i+) /i点还没有找到最短路径 if(find_si=false & m.arcsposei.adj + lengthpose lengthi) lengthi=m.arcsposei.adj + lengthpose; /记录中间节点 int z=0; /记录找到它的路径 while(roadposez!=-1) z+; /*移位再插入,用pose更新*/ /(1)复制 fo