连云港景点导游咨询

淮海工学院计算机工程学院课程设计报告设计名称：数据结构课程设计选题名称：连云港市景点导游咨询姓名：顾浩然学号：110912109专业班级：网络工程网络091系（院）：计算机工程学院设计时间：2010.12.20~2010.12.31设计地点：软件工程实验室、教室指导教师评语：签名：年月日成绩：数据结构课程设计报告第1页，共页1．课程设计目的1、训练学生灵活应用所学数据结构知识，独立完成问题分析，结合数据结构理论知识，编写程序求解指定问题。2.初步掌握软件开发过程的问题分析、系统设计、程序编码、测试等基本方法和技能；3.提高综合运用所学的理论知识和方法独立分析和解决问题的能力；4.训练用系统的观点和软件开发一般规范进行软件开发，巩固、深化学生的理论知识，提高编程水平，并在此过程中培养他们严谨的科学态度和良好的工作作风。2．课程设计任务与要求：任务：用无向网表示连云港市旅游景点平面图，图中顶点表示主要景点，存放景点编号、名称、简介等信息，图中边表示景点间的道路，存放路径长度信息。要求：（1）查询各景点的相关信息；（2）查询图中任意两个景点间的最短路径（3）查询图中任意两个景点间的所有路径（4）可动态添加景点，加后可查询该景点到其它景点的最短路径数据结构课程设计报告第2页，共页3．课程设计说明书一需求分析：连云港作为一个著名的旅游城市，每年都有大量的国内外游客来港城旅游，大多数外地游客对连云港的旅游景点的相关信息不是非常了解，所以我们可以为他们设计一个方便在连云港外出旅游的咨询程序，即连云港市景点导游咨询程序。连云港市导游咨询程序需要把连云港市的主要景点（争取十个左右，虽然我只认识几个而已）都包括在一个平面图内。(1)以图中各顶点存放连云港的各景点名称，代号，简介等相关信息（2）程序中，以各个旅游景点名称为图的顶点，各个顶点的信息是景点的简要描述，权值就是任意两个景点间的路径长度(3)以边存放路径及路径长度等相关信息，游客可根据图所提供的景点来查询各个景点的相关信息及各景点的路径查询(4)提供两个景点间的所有路径并提示最短路径，为游客的旅游带来方便，游客可根据实际情况选择最佳的游览路线。二概要设计1、基本操作：CreateGraph(G):创建图G。LocateVertex(G,v):确定顶点v在图g中的位置，若图g中没有顶点v，则函数值为“空”。GetVertex(G,i):取出图g中的第i个顶点的值，若i大于图g中顶点数，则函数值为“空”。FirstAdjVertex（G，v）：求图G顶点v的第一个邻接点，若v无邻接点或图G中无顶点v，则函数值为“空”。NextAdjVertex（G，v，w）：已知w是图G中顶点v的某个邻接点，求顶点v的下一个邻接点（紧跟在w后面），若w是v的最后一个邻接点，则函数值为“空”。InsertVertex（G，u）：在图G中增加一个顶点u。InsertArc（G，v，w）：在图G中增加一条从顶点v到顶点w的弧。TraverseGraph（G）：按照某种次序，对图G的每个结点访问一次且仅访问一次。2、系统中子程序及功能要求：①path(MGraphg,inti,intj,intk)：确定路径上第k+1个顶点的序号,k初始值为0②apath(MGraphg,inti,intj)：初始化访问标志与路径条数，并调用path（）函数③cpath(MGraphg,intpath1[],inti,intv0)：输出最短路径④bpath(MGraphg,intdist[],intpath1[],ints[],intn,intv0,inti)：由path1计算从v0到i的最短路径⑤Dijkstra(MGraphg,intv0,intp)：采用迪杰斯特拉算法求从顶点v0到顶点p的最短路径⑥chaname(MGraphg)：查询景点的信息⑦chapath1(MGraphg)：查询两个景点间的所有路径⑧chapath2(MGraphg)：查询两个景点间的最短路径数据结构课程设计报告第3页，共页3、各程序模块之间的调用关系：函数的调用关系图mainchaname⑥chapath1⑦chapath2⑧apath④Dijkstra⑤path①bpath④path①cpath③cpath③主函数可调用子程序⑥⑦⑧子程序⑦可调用子程序④子程序⑧可调用子程序⑤子程序④可调用子程序①子程序①可调用子程序①子程序④可调用子程序③子程序③可调用子程序③子程序②可调用子程序①子程序⑤可调用子程序④三详细设计⑴顶点、边和图的类型：typedefstruct{intnum;/*顶点编号*/charname[MAXSIZE];/*顶点名称*/chardiscription[MAXLEN];/*顶点信息描述*/}VertexType;typedefstruct{intedges[MAXV][MAXV];intvexnum,arcnum;VertexTypevexs[MAXV];}MGraph;intvisited[MAXV];intp[MAXV];⑵创建连云港市景点地图：数据结构课程设计报告第4页，共页inti,j;intb[11]={1,2,3,4,5,6,7,8,9,10,11};char*c[11]={/*各个景点名称*/};char*d[11]={/*字符串指针数组,用来给每个顶点的简介信息进行赋值*/};MGraphg;/*创建一个无向网*/intA[11][11]={/*景点的相关简介进行赋值*/};g.vexnum=顶点个数;g.arcnum=顶点边数;/*建立无向网的邻接矩阵*/for(i=0;i图的顶点个数;i++){/*给每个顶点一个编号*//*通过字符串复制函数给每个顶点一个名称*//*通过字符串复制函数给每个顶点加上信息，即作为景点的简介信息*/}⑶查询景点的信息：inti;chars;while(1)/*可提供循环查询,当输入为'N'或'n'时,结束循环*/{printf(\t\t\t请输入你要查询的景点：);scanf(%d,&i);for(intj=0;j图的顶点个数;j++){/*输出信息*/}printf(继续查询?(y或n):);scanf(%s,&s);if(s=='N'||s=='n')break;}⑷查询景点间的游览路径：voidchapath1(MGraphg)inti,j;chars;while(1)/*可提供循环查询,当输入为'N'或'n'时,结束循环*/{/*输入起点与终点*/;disppath(g,i,j);/*调用disppath函数,用来输出两个景点间的所有路径*/printf(继续查询?(y或n):);scanf(%s,&s);数据结构课程设计报告第5页，共页if(s=='N'||s=='n')break;}}⑸查询两个景点间的最短路径：inti,j;chars;while(1)/*可提供循环查询,当输入为'N'或'n'时,结束循环*/{/*输入起点与终点*/Dijkstra(g,i,j);/*调用Dijkstra函数,用来输出两个景点间的最短路径*/printf(继续查询?(y或n):);scanf(%s,&s);if(s=='N'||s=='n')break;}}⑹主函数：intselect;/*定义一个整型变量,用来输入不同的选择*/do/*可提供循环输入选择,当输入的选择为4时,退出循环*/{switch(select)/*判断select的值，根据其值跳转到相应的子模块继续执行*/{case1:/*查询景点的信息*/break;case2:;/*查询景点间的游览路径*/break;case3:/*查询景点间的最短游览路径*/break;case4:/*退出程序*/break;}}while(select!=4);/*当select的值不为4时，继续循环*/}四设计与调试分析1、在执行查询景点间的游览路径时，我之前考虑到深度优先遍历，我可以以指定的为起点开始遍历，在到达指定的终点时，让他停止并输出路径，不过这之间要定义一个s，来存放访问过的并且可走通的顶点编号，以便可以方便输出，可是，如一个顶点有多个邻接点，它是选取其中一条的，有可能在这个顶点可以经过数据结构课程设计报告第6页，共页这些邻接点照样可以走到我们指定的终点，在这里就出现了问题，怎样让它在访问一个邻接点之后还可以在访问它的另外一个邻接点。之后想到了递归调用,以及邻接矩阵并通过visited[]来解决这个问题；2、在执行导游程序时，需要根据用户的临时输入求最短路径。虽然迪杰斯特拉算法的时间复杂度比弗洛伊德算法低，但每次在求一条最短路径时都必须重新搜索一遍，如果用户频繁查询会导致查询效率降低，所以，在选用算法时不能单纯的只考虑算法的渐近时间复杂度，有时还必须综合考虑各种因素。五用户手册尊敬的用户您好，本程序提供完全人性化操作界面，您完全可以根据程序的详细操作提示得到您所要的相关信息及帮助服务，以下为本程序的主界面，感谢您的支持与使用。六测试成果数据结构课程设计报告第7页，共页数据结构课程设计报告第8页，共页数据结构课程设计报告第9页，共页数据结构课程设计报告第10页，共页七附录（源程序清单）#includestdio.h#includestring.h#includestdlib.h#defineMAXV11#defineMAXSIZE30#defineMAXLEN3000#defineINF32767inta=0;typedefstruct{intnum;charname[MAXSIZE];charxinxi[MAXLEN];}VertexType;typedefstruct{数据结构课程设计报告第11页，共页intedges[MAXV][MAXV];intvexnum,arcnum;VertexTypevexs[MAXV];}MGraph;intvisited[MAXV];intp[MAXV];voidpath(MGraphg,inti,intj,intk)/*确定路径上第k+1个顶点的序号,k初始值为0*/{ints;if(p[k]==j){a++;printf(第%d条:,a);for(s=0;s=k-1;s++)printf(%s-,g.vexs[p[s]].name);printf(%s\n,g.vexs[p[s]].name);}s=0;while(sg.vexnum){if(s!=i){if(g.edges[p[k]][s]!=INF&&visited[s]==0){visited[s]=1;p[k+1]=s;path(g,i,j,k+1);visited[s]=0;}}数据结构课程设计报告第12页，共页s++;}}voidapath(MGraphg,inti,intj)/*初始化访问标志与路径条数，并调用path（）函数*/{intk;p[0]=i;for(k=0;kg.vexnum;k++)visited[i]=0;a=0;path(g,i,j,0);}voidcpath(MGraphg,intpath1[],inti,intv0)/*输出最短路径*/{intk;k=path1[i];if(k==v0)return;cpath(g,path1,k,v0);printf(%s-,g.vexs[k].name);}voidbpath(MGraphg,intdist[],intpath1[],ints[],intn,intv0,inti)/*由path1计算从v0到i的最短路径*/{if(s[i]==1&&i!=v0){printf(从%s到%s的最短游览路径是:\n,g.vexs[v0].name,g.vexs[i].name);数据结构课程设计报告第13页，共页printf(%s-,g.vexs[v0].name);cpath(g,path1,i,v0);printf(%s,g.vexs[i].name);printf(路径长度：%d公里\n,dist[i]);}}