《数据结构课程设计-旅游景点咨询系统的设计与实现》由会员分享，可在线阅读，更多相关《数据结构课程设计-旅游景点咨询系统的设计与实现（21页珍藏版）》请在金锄头文库上搜索。
1、精选优质文档-倾情为你奉上旅游景点咨询系统的设计与实现一、需求分析1、问题描述创建一个至少有15个点的无向网表示的某个旅游景点的导游图。顶点代表景点,类型为字符串（例如，泰山导游图：“天地广场门”，“十八盘”，“冯玉祥墓”，“桃花峪门”，“中天门”，“南天门”，“玉皇顶”等），弧表示两个景点之间可以直达，弧上的权值表示两个景点之间的路程（公里数），弧上还有到达方法的信息（有步行和索道两种）。建立一个游客咨询系统。2、基本要求a. 创建图的存储结构。b. 输入两个景点名，就可以得到从一个景点到达另一个景点的所有简单路径、相应路径的路程公里数、行走的方法（每一段是步行，还是坐索道）。c. 输入两个
2、景点名，就可以得到其最短路径，即：路程最短的行进方法；如果两者无路径可通，就得出“两景点不可达的信息”。二、概要设计1.数据结构本程序需要用到两个结构体，分别为ArcCell和MGraph。2.程序模块本程序包含两个模块，一个是实现功能的函数的模块，另一个是主函数模块。系统子程序及功能设计本系统共有七个子程序，分别是：int LocateVex(MGraph G,VertexType u)/得到顶点u的序号void CreateDN(MGraph *G)/建立景点间的无向网VertexType* GetVex(MGraph G,int v)/根据顶点序号返回顶点值int FirstAdjVex
3、(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
4、调用函数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
5、) /* 采用数组(邻接矩阵)表示法,构造有向网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(
6、*G).vexnum;+j) (*G).arcsij.adj=INFINITY; /* 网 */ (*G).arcsij.info=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).arcs
7、ji.adj=w; /* 有向网 */ (*G).arcsij.info=(*G).arcsji.info=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
8、.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(
9、);/还原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(m.arcsx1y1.info=0)cout步行 ;elsecout索道 ;cout路程:numendl;cout
10、endl; /出栈 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;c.int Minway(MGraph& m,char *str,char *buf)/求两顶点间的最短路径int x=LocateVex(m,str);int y=LocateVex(m,buf);/分配路径相关信息的存
11、储空间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; /将路径最短的关联的另一个顶点加入已找到
