《基于无向图的校园导游系统数据结构课程设计报告-毕设论文》由会员分享，可在线阅读，更多相关《基于无向图的校园导游系统数据结构课程设计报告-毕设论文（26页珍藏版）》请在金锄头文库上搜索。
1、重庆科技学院本科生课程设计 摘要重庆科技学院课程设计报告 院（系）:_电气与信息工程学院 专业班级: 计科普0902 设计地点（单位）_计算机基础自主学习中心I306_设计题目:_校园导游咨询_重庆科技学院课程设计任务书设计题目：校园导游咨询学生姓名课程名称数据结构课程设计专业班级计科2009-02地 点计算机基础自主学习中心起止时间设计内容及要求基本要求:（1）设计你的学校的校园平面图，所含景点不少于10个。以图中顶点表示学校各景点，存放景点名称、代号、简介等信息；以边表示路径，存放路径长度等相关信息。（2）为来访客人提供图中任意景点的问路查询，即查询任意两个景点之间的一条最短的简单路径。
2、（3）为来访客人提供图中任意景点相关信息的查询。测试数据：由读者根据实际情况指定。实现提示：一般情况下，校园的道路是双向通行的，可设校园平面图是一个无向网。顶点和边均含有相关信息。扩展要求：（1）提供图中任意景点问路查询，即求任意两个景点之间的所有路径。（2）扩充道路信息，如道路类别（车道、人行道等）、沿途景色等级，以至可按客人所需分别查询人行路径或车行路径或观景路径等设计参数1、 自己编写程序，校园初始数据以文本文件保存，文件格式根据需要自行定义。对应的地图初始化从文件中读出数据进行初始化。2、 查询的结果应提供屏幕和文件两种方式。3、 有基础的同学尽量实现界面的可视化操作和动态显示。进度要
3、求2011.1.4 星期二（上午教师指导，下午学生独立完成）、完成任务的讲解、并接受课程设计任务，选定课程设计的题目2011.1.5 星期三（上午教师指导，下午学生独立完成）、了解任务的算法、并画出算法的程序流程图2011.1.6 星期四（上午教师指导，下午学生独立完成）、对任务的关键技术进行验证、并确定解决办法2011.1.7 星期五（上午教师指导，下午学生独立完成）、编制任务的程序2011.1.10 星期一（上午教师指导，下午学生独立完成）、编制任务的程序2011.1.11 星期二（上午教师指导，下午学生独立完成）、对程序的调试，并试运行。2011.1.12 星期三（上午教师指导，下午学生
4、独立完成）、整理课程设计过程中的各个参数、并进行总结，提出改进意见2011.1.13 星期四（上午教师指导，下午学生独立完成）、编写课程设计报告、准备答辨2011.1.14 星期五（上午答辨）、进行答辨验收工作。参考资料1严蔚敏 吴伟民 著， 数据结构（C语言版），清华大学出版社，2007.42. Richard F.Gilberg Behrouz A.Forouzan, Data Structures A Pseudocode Approach with C，second edition, Thomson, 2005.13. 李春葆 著，数据结构教程，清华大学出版社，2005.1其它说明.本
5、表应在每次实施前一周由负责教师填写二份，院系审批后交院系办备案，一份由负责教师留用。.若填写内容较多可另纸附后。3.一题多名学生共用的，在设计内容、参数、要求等方面应有所区别。教研室主任： 指导教师：向毅、陈刘奎、熊茜 2010年 12 月 20日重庆科技学院本科生课程设计 摘要重庆科技学院本科生课程设计 摘要重庆科技学院本科生课程设计 摘要摘要现代快节奏的生活使得都市人越来越渴望亲近自然，因此外出旅游现在被越来越多的都市人所看中，所以如何快速方便的找到我们想要的旅游景点的信息和最短路径就成了一个很重要的问题。本设计基于图的结构，创建一个无向图，针对游客的实际需求，将重庆科技学院的景点编号、名
6、称、介绍等信息放入到图的顶点当中并保存在景点文本文件当中，将两个景点的编号和它们之间的距离当作权值也保存到权值文本文件当中，利用迪杰斯特拉算法来求从一个景点到另一个景点的最短距离，利用strcmp();函数来查找景点，并显示出它的信息，从而解决了要查找景点信息和景点之间的最短路径的问题，最后按照显示屏上的提示进行相关的操作。关键词：无向图、查找信息、最短距离、校园导游咨询重庆科技学院本科生课程设计 目录目录摘要I1 设计内容和要求11.1设计内容11.1设计要求12 概要设计22.1 程序的模块图22.2 主函数的概要设计32.3 查找介绍函数的概要设计32.4 查找最短路径函数的概要设计32
7、.5 退出函数的概要设计33 详细设计43.1 程序的流程图43.2 主函数的详细设计53.3 查找介绍函数的详细设计53.4 查找最短路径函数的详细设计63.5 退出函数的详细设计83.6 数据结构的详细设计84 软件测试104.1 菜单的测试104.2 查找景点简介的测试104.3 查找两个景点之间的最短距离的测试114.4 退出的测试115 软件使用说明126 致谢137 参考文献148 附录15重庆科技学院本科生课程设计 设计内容和要求1 设计内容和要求1.1设计内容依据课程设计的要求，利用一个无向图的结构，将景点当作图的顶点，将景点之间的距离当作权值来储存，然后根据游客自己的需求，按
8、照显示屏上的提示来进行查找景点介绍，查找两个景点之间的最短距离，退出程序等基本操作。1.1设计要求本软件为校园导游咨询系统，根据游客的实际需求而设计，首先创建一个无向图，然后从文件当中读取所有景点的编号、名称、介绍和两点之间的权值，并将它们写入到无向图当中。功能主要包括查找已知景点的信息，查找从一个景点到另一个景点的最短路径，退出等基本操作。软件的界面要求使用VC+6.0的运行环境。软件的数据库包括校园景点的编号、名称、介绍和两个景点之间的距离（权值），首先要定义顶点的数据类型结构体，里面包括景点的编号、名称、介绍，然后定义一个邻接矩阵结构体来储存边的信息，最后定义一个无向图类型的结构体来储存
9、顶点的信息，边的信息，顶点的个数，边的个数。最后游客按照显示屏上的提示来进行相关的操作。1重庆科技学院本科生课程设计 概要设计2 概要设计2.1 程序的模块图本软件的算法依据无向图的操作通过查找函数查找景点的信息，通过迪杰斯特拉函数来查找最短距离，开始时首先从文件当中读取景点的编号、名称、介绍和两个景点之间的距离即权值，然后将其加入到图当中，再调用查找函数查找景点的信息，调用迪杰斯特拉函数来查找最短距离，调用退出函数实现退出功能，其模块图如图2.5所示：开始文件读取加入图退出最短距离查找信息屏幕显示屏幕显示图2.5模块图2.2 主函数的概要设计基于程序的操作要求，对于主函数的设计首先是显示一个
10、可视化的操作界面提醒游客进行相关的操作和提示游客其可供选择的景点的名称，便于其在后面的操作过程当中能够快速方便的找到其需要查找的景点的名称。而后就是一个switch（）；的选择函数，提供查找景点信息，查找两个景点之间的最短距离和退出的相关的选择操作而后进入到每一个操作界面当中，从而实现所需要的功能。2.3 查找介绍函数的概要设计当游客选择了要查找景点的信息的介绍这一项功能的时候，就会进入到查找的界面，对于查找景点信息就是利用strcmp（）；函数，当游客输入景点的名称的时候看其是否与文件当中的数据相匹配，如果有则输出它的介绍，如果没有则输出错误的提示提醒游客进行相关的操作来进入到正确的操作过程
11、当中。2.4 查找最短路径函数的概要设计对于查找最短路径的这一项功能，则是利用迪杰斯特拉函数(1)假设用带权的邻接矩阵arcs来表示带权的有向图，arcsij表示弧（vi,vj）上的权值。若(vi,vj)不存在，则置arcsij为无穷大。S为已找到从v出发的最短路径的终点集合，它的初始状态为空集。那么，从v出发到图上其余各个定点vi可能到达的最短路径长度的初始值为：Di = arcsvi;(2)选择vj,使得Dj = MinDi | vi V Svj就是当前求得的一条从v出发的最短路径的终点。令S = S j;(3)修改从v出发到集合V S 上任意顶点vk可到达的最短路径的长度。如果Dj +
12、arcsjk Dk则修改Dk为Dk = Dj+arcsjk;(4)重复操作(2)、(3)共n 1 次，由此求得从v到图上其余各个顶点的最短路径是依路径长度递增的序列。从而求得了从一个景点到另一个景点的最短路径的问题。2.5 退出函数的概要设计关于退出函数，则是当游客执行完了他想要进行的操作过后选择退出的功能的时候就调用退出函数exit(0);跳入到退出界面实现退出的功能。3重庆科技学院本科生课程设计 详细设计3 详细设计3.1 程序的流程图当我们想要更加实际的了解一个程序的算法过程的时候，我们就要依据程序的流程图来给我们一个比较实际的过程，从流程图当中能够更加清楚整个程序实现的过程是怎样的。其流程图如图3.1所示：start读取文件信息创建无向图写入无向图中Case ICase PCase Q查找信息end最短路径TTFF图3.1流程图3.2 主函数的详细设计主函数是一个程序的主体，当我们要进行我们所需要的操作的时候我们就要根据主函数中的显示信息和它给我们的相关的提示信息来进行所需要的操作，因此在这次的程序实现的过程当中，首先调用CreateUDN(G);函数创建一个无向图，然后利用一个for();循
