校园导游系统

1、西安郵電大学数据结构课程设计报告题 目： 校园导游系统院系名称： 专业名称： 班 级： 学生姓名： 学号（8位）： 指导教师： 设计起止时间：2013年12月16日2013年12月27日一. 设计目的（1） 了解二叉树特性、存储及其操作实现，在计算机领域运用二叉树编译代码实现一件简单实际的操作，熟练掌握二叉树的三种遍历递归与非递归的实现；（2） 掌握图的两种遍历深度优先遍历和广度优先遍历，了解两者的区别和优缺点。学习在计算机中表示和处理图形结构以及绘制简单的地图并输出，熟练掌握图的逻辑结构和存储结构，学习用算法来解决实际问题；（3） 掌握邻接链表和邻接矩阵的存储结构，以及这两者的区别，会用邻接

2、链表和邻接数组两种方法来实现数据的存储与读取；（4） 巩固文件的存储与读取部分，以便能够加深对文件读写的理解和更好的更熟练的实际应用；（5） 学会用计算机解决实际问题，将生活中的问题数据化，然后输入到计算机中以便更快的解决，提高自己的实践能力以及自身的学习能力，加深对课本知识的理解和掌握。二. 设计内容<1> 设计题目：设计一个校园导游程序，并按各要求进行编程：要求： （1）设计并显示学校的校园平面图， 地点（地点名称、地点介绍）， 路线（公里数）均不少于10个。 （2）提供图中任意地点相关信息的查询。 （3）提供图中任意地点的问路查询： 1>任意两个地点之间的一条最短的简单

3、路径； （最短路径长度中转次数最少） 2>任意两个地点之间的一条最佳访问路线； （带权（公里数）最短路径长度） 3>任意两个地点之间的所有简单路径。 （4）提供图中所有地点的最佳布网方案； （5）增加新地点和路线、撤销旧地点和路线。三概要设计1 功能模块图：校园导游系统main()创建新地图Create() 1. 查看西邮地图功能菜单 3. 查询路线基本状况 2. 显示基本信息 4. 添加新路线 6. 增加新景点 5. 撤销旧路线 7. 撤销旧景点 8. 最短路径查询 9. 最短连通路径查询 12. 查看所有简单路径 0. 退出系统 13.查看中转次数最少路径 11. 查看所有景点

4、名称 10. 查看所有景点详情2各个模块详细的功能描述。该导游系统能为来访者提供包括景点介绍、景点查询、仿真地图、最短路径之类的快捷指导。最短路径查询和景点概况主要运用了Dijstra算法来实现，其他功能都是通过一些简单的算法来编写的。所谓系统，也不尽然，只是一个小小的信息提示。其中主要运用到的程序、算法也较简单。除了可以创建一个新的地图外，其主要功能还有以下几点：1. 查看西邮地图，自制的西安邮电大学方针地图，地图上标有景点名称以及编号和各景点之间的距离，方便更直观的了解本校的景点分布；2. 显示基本信息，显示每一个景点可直达的景点路径和距离；3. 查询路线基本状况，查询从任意一个景点出发到

5、其余各景点之间距离最短的路径，提供给旅客最简单的路线介绍；4. 添加新路线，在原有路线的基础之上，新增一条路线并保存到文件里面（该功能中新增路线的两端只能是目前地图上已有景点）；5. 撤销旧路线，在原有路线的基础之上，删除一条废弃不用的路线并将删除后的信息保存到文件里面；6. 增加新景点，在原有景点的基础之上，添加一个新的景点并保存到文件里面，添加景点包括景点名称和景点详细介绍；7. 撤销旧景点，就是在原有景点的基础之上，删除一个废弃或拆迁的景点并将删除后的信息保存到文件里面；8. 最短路径查询，只需要从键盘输入起点和终点的景点编号，就可以找出这两点之间的最短路径；9. 最短连通路径查询，从键

6、盘输入起始景点的编号，就可以找出一条最短连通路，方便旅客找出一条参观所有景点的最佳路径；10. 查看所有景点详情，可以输出所有景点的编号、名称以及该景点的详细介绍，供旅客选择自己喜欢的地方；11. 查看所有景点名称，输出所有景点名称，让旅客知道本校的所有景点；12. 查看两个景点的所有简单路径，输出两个景点之间的所有简单路径供给旅客选择；13. 查看中转次数最少路径，输出两个景点之间途径地方最少的一条路径。四详细设计1功能函数的调用关系图；Main( ) read()Map( )Serach(&G)Infor(&G)Display(& G)Search_All(&

7、;G,1)Search_All(&G,0)Information(&G)exit(0)Mintree(& G)Del(&G)Shortcut(&G)Delvex(&G)Save(&G)Addvex(&G)Add(&G)Infor(&G)2各功能函数的数据流程图；1.创建新地图输入G->vexnum，G->arcnumi=1i<=G->vexnum输入第i个景点的名称和详情输入G->arcnum条路线将景点信息和路线存入文件i+2.输出所有景点详情i=1开始输出G->vexi.na

8、mei+i<=G->vexnum输出G->结束3.显示图信息i=1开始输出iß àj的直达路径i+i<=G->vexnum结束j+j=1j<=G->vexnumG->arcij=327684.添加新景点No=Locate(G，place)开始输入景点名称placei=1i<=G->vexnumreturnG->arciNo=INFINITYG->arcNoi=INFINITY(G->vexnum)+；G->vexNo.num=No;No<=G->vexnumNo

9、>=15.添加新路线开始输入start 和 endx=1returnG->arcstartend=length G->arcstartend=INFINITY输入length输入x(G->arcnum)+G->arcendstart=length6.两点之间的所有简单路径和中转次数最少路径开始输入start 和 endtop=0Min(G，start，end)Depsearch(G，start，end)cont=INFINITYx=17.删除路线开始输入待删除路线G->arcstartend=INFINITYG->arc endstart=INFINI

10、TY(G->arcnum)-8.删除景点开始输入待删除景点No删除邻接矩阵中第No行第No列的有路的路径，G->arcnum减去相应值从邻接矩阵第No行第No列开始，将数据前移(G->vexnum)-3重点设计及编码。1> Dijkatra算法的修改路径部分的代码for(j=1;j<=G->vexnum;j+)if(!pathj0&&G->arckj<INFINITY&&distk+G->arckj<distj) distj=distk+G->arckj; /当前最小权值t=1;while(pat

11、hkt!=0) /pathkt未结束pathjt=pathkt;t+;pathjt=k; /第k个结点pathjt+1=0; Dijkstra算法是典型最短路算法，用于计算一个节点到其他所有节点的最短路径。主要特点是以起始点为中心向外层层扩展，直到扩展到终点为止。Dijkstra算法能得出最短路径的最优解，但由于它遍历计算的节点很多，所以效率低。Dijkstra算法思想为：设G=(V,E)是一个带权有向图，把图中顶点集合V分成两组，第一组为已求出最短路径的顶点集合（用S表示，初始时S中只有一个源点，以后每求得一条最短路径 , 就将 加入到集合S中，直到全部顶点都加入到S中，算法就结束了），第二

12、组为其余未确定最短路径的顶点集合（用U表示），按最短路径长度的递增次序依次把第二组的顶点加入S中。在加入的过程中，总保持从源点v到S中各顶点的最短路径长度不大于从源点v到U中任何顶点的最短路径长度。此外，每个顶点对应一个距离，S中的顶点的距离就是从v到此顶点的最短路径长度，U中的顶点的距离，是从v到此顶点只包括S中的顶点为中间顶点的当前最短路径长度。2> 文件存储功能的部分代码fprintf(fp,"%d %dn",G->vexnum,G->arcnum);for(i=1;i<=G->vexnum;i+)fprintf(fp,PV);for(i

13、=1;i<=G->vexnum;i+)for(j=1;j<=G->vexnum;j+)fprintf(fp,"%d ",G->arcij);fprintf(fp,"n");文件存储是先存入景点数和路线条数，然后再存入所有的景点名称和景点详细介绍以及所有的路线，路线是以邻接矩阵的形式存入文件的，邻接矩阵里面的每一个数据都对应两个景点，有路的存路径长度，没有路的默认为一个极大值，这样一来方便路线的读取。将信息存入文件，以便下一次运行程序的时候就不用再次输入一连串繁琐的信息了，可以直接打开所需的文件直接读取便可，如此一来便省去了不

14、少事。五 测试数据及运行结果1.正常测试数据（3组）及运行结果； 最短路径查询（权值最小） 两点之间所有简单路径查询 两点之间中转次数最小路径查询2非正常测试数据（2组）及运行结果。 两点之间最短路径查询（所查景点不存在） 增加新路线（该路线已存在）六调试情况，设计技巧及体会1对自己的设计进行评价，指出合理和不足之处，提出改进方案；（1）本程序参考课本上的导游系统编写而成。期间或自我摸索，或查找资料，或请教同学，最终实现了该系统的成功运行。编程过程不断出现各种各样的，均能设法将其化解，算是在实践中学得编译运行调试指法。以下是编写过程中出现过的几个较大漏洞，直接导致程序运行的错误，在此记录下来作

15、为之后自省。a. scanf中缺少“取地址符”，输入不起作用；b. 源程序所给的“求最短路径”算法错误，参照课Dijkstra算法之后写出本程序所用的算法，值得肯定；c. 调用display函数时错误，经过同学指点，删掉五句多余代码，程序成功运行。（2）书上介绍的弗洛伊德算法只需计算一次，即可求得每一对顶点之间的最短效率，但时间复杂度为O（n3）。迪杰斯特拉算法虽然每求一次最短路径都必须重新搜索一遍，频繁查找时会导致效率降低，但是时间复杂度要比弗洛伊德算法低，因此我还是选择了Dijkstra算法其中编程过程中显露出来的问题也必须引起高度重视，在今后的学习中必当万分注意绝不再犯。比如细心问题，有次的一个小小的“取地址符”没有添加，导致整个程序无法运行，检查了好久才发现。所以说，编程是个细活，只有严谨的态度，细心的思路以及良好的学习习惯，最终才能收获成功的喜悦。2对设计及调试过程的心得体会。 这次课程设计显然要比去年上手的多，毕竟已经是第二次课程设计了，所以心里也没那么紧张了，但是在编写过程中还是遇到了种种困难和极难解决的问题。就比如说最少中转次数那里，刚开始编写的代码第一次查询的时候还能够正确输出，但是第二次第三次就会出