基于无向图的校园导游系统数据结构课程设计报告.docx

重庆科技学院课程设计报告 院（系）:_电气与信息工程学院 专业班级: 计科普0902 设计地点（单位）_计算机基础自主学习中心I306_设计题目:_校园导游咨询_重庆科技学院课程设计任务书设计题目：校园导游咨询学生姓名课程名称数据结构课程设计专业班级计科2009-02地 点计算机基础自主学习中心起止时间设计内容及要求基本要求:（1）设计你的学校的校园平面图，所含景点不少于10个。以图中顶点表示学校各景点，存放景点名称、代号、简介等信息；以边表示路径，存放路径长度等相关信息。（2）为来访客人提供图中任意景点的问路查询，即查询任意两个景点之间的一条最短的简单路径。 （3）为来访客人提供图中任意景点相关信息的查询。测试数据：由读者根据实际情况指定。实现提示：一般情况下，校园的道路是双向通行的，可设校园平面图是一个无向网。顶点和边均含有相关信息。扩展要求：（1）提供图中任意景点问路查询，即求任意两个景点之间的所有路径。（2）扩充道路信息，如道路类别（车道、人行道等）、沿途景色等级，以至可按客人所需分别查询人行路径或车行路径或观景路径等设计参数1、 自己编写程序，校园初始数据以文本文件保存，文件格式根据需要自行定义。对应的地图初始化从文件中读出数据进行初始化。2、 查询的结果应提供屏幕和文件两种方式。3、 有基础的同学尽量实现界面的可视化操作和动态显示。进度要求2011.1.4 星期二（上午教师指导，下午学生独立完成）、完成任务的讲解、并接受课程设计任务，选定课程设计的题目2011.1.5 星期三（上午教师指导，下午学生独立完成）、了解任务的算法、并画出算法的程序流程图2011.1.6 星期四（上午教师指导，下午学生独立完成）、对任务的关键技术进行验证、并确定解决办法2011.1.7 星期五（上午教师指导，下午学生独立完成）、编制任务的程序2011.1.10 星期一（上午教师指导，下午学生独立完成）、编制任务的程序2011.1.11 星期二（上午教师指导，下午学生独立完成）、对程序的调试，并试运行。2011.1.12 星期三（上午教师指导，下午学生独立完成）、整理课程设计过程中的各个参数、并进行总结，提出改进意见2011.1.13 星期四（上午教师指导，下午学生独立完成）、编写课程设计报告、准备答辨2011.1.14 星期五（上午答辨）、进行答辨验收工作。参考资料3. 李春葆 著，数据结构教程，清华大学出版社，2005.1其它说明.本表应在每次实施前一周由负责教师填写二份，院系审批后交院系办备案，一份由负责教师留用。.若填写内容较多可另纸附后。3.一题多名学生共用的，在设计内容、参数、要求等方面应有所区别。教研室主任： 指导教师：向毅、陈刘奎、熊茜 2010年 12 月 20日摘要现代快节奏的生活使得都市人越来越渴望亲近自然，因此外出旅游现在被越来越多的都市人所看中，所以如何快速方便的找到我们想要的旅游景点的信息和最短路径就成了一个很重要的问题。本设计基于图的结构，创建一个无向图，针对游客的实际需求，将重庆科技学院的景点编号、名称、介绍等信息放入到图的顶点当中并保存在景点文本文件当中，将两个景点的编号和它们之间的距离当作权值也保存到权值文本文件当中，利用迪杰斯特拉算法来求从一个景点到另一个景点的最短距离，利用strcmp();函数来查找景点，并显示出它的信息，从而解决了要查找景点信息和景点之间的最短路径的问题，最后按照显示屏上的提示进行相关的操作。关键词：无向图、查找信息、最短距离、校园导游咨询目录摘要I1 设计内容和要求11.1设计内容11.1设计要求12 概要设计22.1 程序的模块图22.2 主函数的概要设计32.3 查找介绍函数的概要设计32.4 查找最短路径函数的概要设计32.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 附录151 设计内容和要求1.1设计内容依据课程设计的要求，利用一个无向图的结构，将景点当作图的顶点，将景点之间的距离当作权值来储存，然后根据游客自己的需求，按照显示屏上的提示来进行查找景点介绍，查找两个景点之间的最短距离，退出程序等基本操作。1.1设计要求本软件为校园导游咨询系统，根据游客的实际需求而设计，首先创建一个无向图，然后从文件当中读取所有景点的编号、名称、介绍和两点之间的权值，并将它们写入到无向图当中。功能主要包括查找已知景点的信息，查找从一个景点到另一个景点的最短路径，退出等基本操作。软件的界面要求使用VC+6.0的运行环境。软件的数据库包括校园景点的编号、名称、介绍和两个景点之间的距离（权值），首先要定义顶点的数据类型结构体，里面包括景点的编号、名称、介绍，然后定义一个邻接矩阵结构体来储存边的信息，最后定义一个无向图类型的结构体来储存顶点的信息，边的信息，顶点的个数，边的个数。最后游客按照显示屏上的提示来进行相关的操作。2 概要设计2.1 程序的模块图本软件的算法依据无向图的操作通过查找函数查找景点的信息，通过迪杰斯特拉函数来查找最短距离，开始时首先从文件当中读取景点的编号、名称、介绍和两个景点之间的距离即权值，然后将其加入到图当中，再调用查找函数查找景点的信息，调用迪杰斯特拉函数来查找最短距离，调用退出函数实现退出功能，其模块图如图2.5所示：开始文件读取加入图退出最短距离查找信息屏幕显示屏幕显示图2.5模块图2.2 主函数的概要设计基于程序的操作要求，对于主函数的设计首先是显示一个可视化的操作界面提醒游客进行相关的操作和提示游客其可供选择的景点的名称，便于其在后面的操作过程当中能够快速方便的找到其需要查找的景点的名称。而后就是一个switch（）；的选择函数，提供查找景点信息，查找两个景点之间的最短距离和退出的相关的选择操作而后进入到每一个操作界面当中，从而实现所需要的功能。2.3 查找介绍函数的概要设计当游客选择了要查找景点的信息的介绍这一项功能的时候，就会进入到查找的界面，对于查找景点信息就是利用strcmp（）；函数，当游客输入景点的名称的时候看其是否与文件当中的数据相匹配，如果有则输出它的介绍，如果没有则输出错误的提示提醒游客进行相关的操作来进入到正确的操作过程当中。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 + arcsjk Dk则修改Dk为Dk = Dj+arcsjk;(4)重复操作(2)、(3)共n 1 次，由此求得从v到图上其余各个顶点的最短路径是依路径长度递增的序列。从而求得了从一个景点到另一个景点的最短路径的问题。2.5 退出函数的概要设计关于退出函数，则是当游客执行完了他想要进行的操作过后选择退出的功能的时候就调用退出函数exit(0);跳入到退出界面实现退出的功能。3 详细设计3.1 程序的流程图当我们想要更加实际的了解一个程序的算法过程的时候，我们就要依据程序的流程图来给我们一个比较实际的过程，从流程图当中能够更加清楚整个程序实现的过程是怎样的。其流程图如图3.1所示：start读取文件信息创建无向图写入无向图中Case ICase PCase Q查找信息end最短路径TTFF图3.1流程图3.2 主函数的详细设计主函数是一个程序的主体，当我们要进行我们所需要的操作的时候我们就要根据主函数中的显示信息和它给我们的相关的提示信息来进行所需要的操作，因此在这次的程序实现的过程当中，首先调用CreateUDN(G);函数创建一个无向图，然后利用一个for();循环语句for(int k = 0; k G.vexnum; k+)if(k - 5 = 0)coutendl;couttG.vexsk.name;elsecouttG.vexsk.name;将景点的名称打印在显示屏上，最后是一个switch();的选择语句，提示游客根据选择来进入到相关的操作界面实现程序的基本功能。3.3 查找介绍函数的详细设计当游客选择了要查找景点的信息的介绍这一项功能的时候，程序就会调用DisIntroduction(G);函数进入到查找景点的介绍的界面，当游客输入了需要查找的景点的名称的时候，程序利用for();循环语句来查找是否有这个景点for(int i=0;iG.vexnum;i+)int m = strcmp(G.vexsi.name,n1);if(m=0)v1=i;count1=count1+1;，找到将它的编号返回，并输出它的介绍，没有找到这输出错误提示，提醒游客进行相关的操作进入正确的操作过程当中。3.4 查找最短路径函数的详细设计当游客选择了要查找两个景点之间的最短距离这一项功能的时候，程序就会调用DisPath(G)；函数进入到查找两个景点之间的最短距离的操作界面当中，当游客输入了两个景点的名称过后，程序会调用strcmp();函数查看是否有这两个景点，如果有则返回他们各自的编号，并调用ShortPath_DIJ(G,v1,v2);函数进入到查找最短路径问题的程序当中。for(v=0;vG.vexnum;v+)/各对节点之间初始已知路径及距离finalv=FALSE;/从V出发的最短路径的空集合Dv=G.arcsv0v;/从V出发到图上其余各个定点v0可能到达的最短路径的初始值for(w=0;wG.vexnum;w+)Pvw=FALSE;/设空路径if(DvMAXNUM)Pvv0=TRUE;Pvv=TRUE;Dv0=0;finalv0=TRUE;int a20;for(i=0;iG.vexnum;i+)/对Pathij进行初始化，使其值全部为1000，便于后期的判断for(j=0;jG.vexnum;j+)Pathij=1000;for(i=0;iG.vexnum;i+)/对数组进行初始化，以便对Pathij进行描述ai=1;for(v=0;vG.vexnum;v+)/各条路线的初始节点为v0Pathv0=v0;/开始主循环，每次求解得到v0到某个v顶点的最短路径，并加入到S集合中for(i=1;iG.vexnum;i+)/其余G.vexnum - 1个顶点m=MAXNUM;/当前所知的离v0最近的距离for(w=0;wG.vexnum;w+)if(!finalw)/w顶点在V-S中if(Dwm)/w顶点离v0顶点更近v=w;m=Dw;Pathvav=v;/离v0顶点最近的v加入s集合finalv=TRUE;for(w=0;wG.vexnum;w+)/更新当前最短路径及距离if(!finalw)&(m+G.arcsvwDw)Dw=m+G.arcsvw;/修改当前的最短路径的值int k0=1;aw=1;while(Pathvk0!=1000)/如果上述条件成立，Pathw路径需要改变，因为从v0到w的路径显然经过了v0和v之间的所有的点（包括v）Pathwk0=Pathvk0;k0+;aw+;cout两个景点之间的最短路径为:t;int k=0;while(Pathv2k!=1000)int m=Pathv2k;coutG.vexsm.namet;k+;coutendl;cout两个景点之间的最短距离为: Dv2Mendl;cout请选择要进行的操作(I:查询景点信息，P:查询两个景点之间的最短路径，Q:退出)endl;(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 + arcsjk Dk则修改Dk为Dk = Dj+arcsjk;(4)重复操作(2)、(3)共n 1 次，由此求得从v到图上其余各个顶点的最短路径是依路径长度递增的序列。从而求得了从一个景点到另一个景点的最短路径的问题。3.5 退出函数的详细设计对于退出函数，当游客选择了退出这一个操作的时候，程序就会调用Exit();函数从而进入到退出函数的界面void Exit() /退出cout欢迎下次继续使用!endl;exit(0);程序会提示游客感谢使用，欢迎下次继续使用的提示语，然后调用exit(0);函数实现退出主函数的功能。3.6 数据结构的详细设计本软件的数据结构包括3个部分：1. 邻接矩阵typedef int AdjMatrixMAX_VERTEX_NUMMAX_VERTEX_NUM;定义一个邻接矩阵，用邻接矩阵来定义和储存边的相关信息。2. 顶点的结构体typedef struct Vertex/定义图中顶点的数据类型int num;/景点编号char name14;/景点名称char introduction100;/景点介绍Vertex;定义一个顶点的结构体，用来储存景点的编号、景点得名称和景点的介绍等关于景点的信息。3.无向图的结构体typedef struct /定义图的数据类型Vertex vexsMAX_VERTEX_NUM;/顶点的结构体AdjMatrix arcs;/边的邻接矩阵int vexnum,arcnum;/顶点的个数，边的个数MGraph;定义一个图的结构体，用来储存顶点的信息、边的信息、顶点的个数和边的个数等相关的信息便于我们以后在用的时候能够方便快捷的调用。定义好这些结构体后，当我们以后需要调用的时候，我们就能够方便快捷的调用这些结构体，从而使得我们在运行程序的时候能够更加的快速能够提高我们的程序的运行效率，大大的节省了我们的时间还使得程序变得更加的简单。4 软件测试4.1 菜单的测试对于菜单函数的测试，首先菜单是一个可示化的界面，它能够提示游客依据显示屏上出现的提示来进行相关的操作，查看所有的景点从而方便游客进行相关的操作，因而我们在运行程序的时候首先就会进入到菜单函数当中，经过测试其能够实现我们所要实现得基本功能，其效果图如图4.1所示：图4.1菜单4.2 查找景点简介的测试对于查找景点的介绍的测试，首先依据显示屏上的提示首先输入要进行的操作输入i进入查找景点信息的操作界面，然后输入需要查找的景点的名称即可显示出景点的介绍信息，经过测试可以得出其没有什么错误，程序能够按照我的要求实现它的功能，其效果图如图4.2所示：图4.2查找景点信息4.3 查找两个景点之间的最短距离的测试同查找景点的信息一样，对于查找景点之间的最短距离的测试，我们就要依据提示输入p进入到查询最短路径的界面，依次输入所需要查找的两个景点就会显示出怎样到达这两个景点并显示出它们之间的最短路径，经过测试可见程序能够按照我的要求来实现其所需要的功能，其效果图如图4.3所示：图4.3查找两个景点之间的最短距离4.4 退出的测试原理同上，对于退出函数的测试，我需要依据显示屏上的提示，首先需要输入q进入到退出的界面，系统就会直接调用退出的函数，显示出“欢迎下次继续使用！”的话让后按任意键就退出了系统，其效果图如图4.4所示：图4.4退出界面5 软件使用说明对于软件的使用，对于第一次使用软件的游客来说，要让他们在第一次用的时候就能够快速轻松的掌握软件的用法，因此在程序一开始运行的时候，我们要进行如下的操作：（1）首先我会给游客提供一个可视化的菜单操作界面，在显示屏上提示用户其可以进行的操作和他能够查询的景点的名称。（2）用户输入了“i”后，进入到查询景点简介的界面，当用户输入了想要查找的景点的名称过后就会显示出这个景点的介绍来。（3）当用户输入了“p”后，进入到查询最短路径的界面，然后依据提示用户依次输入两个景点的名称，程序就会将这两个景点的最短路径给我们表示出来并显示出最短路径是多少。（4）当用户输入了“q”后，进入到退出界面，这是系统就会提示用户程序将要运行结束，欢迎下次继续使用的提示语，最后按下任意键程序结束。6 致谢在本次的实验过程当中，虽然有各种各样的问题在困扰着我，但是好在我的身边总会有人在这个时候出现为我解决这些问题，而他们就是我的老师和同学们，一个人做事的时候总是会遇到问题的，有问题并不可怕只要我们相信我们不是一个人在战斗而是有很多的同学和老师与我们站在一起的这样我们就能够战胜各种困难，感谢我的老师和我的同学们。是他们在我遇到问题的时候给我指明了解决的方法，从而克服了一个又一个的问题最终解决了所有的问题实现了程序所需要的功能，感谢我的同学们，不论是上课还是下课，只要是遇到了困难找到他们的时候只要是能够解决的他们会义不容辞的献出自己的力量。感谢老师们的谆谆教诲，他们不辞辛劳为了我们能够顺利的解决问题无时无刻不在我们的身边，当我们一遇到问题的时候他就会出现，从没有半点怨言。最后还要感谢学校感谢给我们提供了良好的实验环境，使我们能够安心轻松的在好的额环境当中完成我们的实验。 签名 周 杨 日期 2011年1月13日7 参考文献【1】 数据结构(C语言版) 严蔚敏 吴伟民 编著 清华大学出版社 2002【2】 C程序设计经典教程，美Deitel,H.M.，美Deitel,P.J.著，清华大学出版社 2006【3】 Windows程序设计，美 Charles Petzold 著，北京大学出版社 2004【4】 Data Structures：A Pseudecode（Approach with C）美Richard F.Gilberg，美Behrouz A.Forouzan著8 附录main.cpp#include#include#include#include GraphADT.husing namespace std;void main()MGraph G;CreateUDN(G);int i = 0;char choice10;coutt*欢迎使用重庆科技学院校园导游程序*endl;coutt_endl;coutt*景点名称*endl;for(int k = 0; k G.vexnum; k+)if(k - 5 = 0)coutendl;couttG.vexsk.name;elsecouttG.vexsk.name;coutnt_nendl;cout请选择要进行的操作(I:查询景点信息，P:查询两个景点之间的最短路径，Q:退出)choicei;switch(choicei)case I:case i:DisIntroduction(G);break;case P:case p:DisPath(G);break;case Q:case q:Exit();break;CreatUDN.h#include#include#include#define MAXNUM 10000#define Vertex 10#define Edges 13using namespace std;void CreateUDN(MGraph &G)/创建一个图ifstream in_file(view.txt,ios:in);/从view.txt中读入景点的相关信息if(!in_file)exit(-1);int i,j,k,w;G.vexnum = Vertex;G.arcnum = Edges;for(i=0;iG.vexsi.numG.vexsi.nameG.vexsi.introduction;for(i=0;iG.vexnum;i+)/初始化矩阵for(j=0;jG.vexnum;j+)G.arcsij=MAXNUM;ifstream weight_file(weight.txt,ios:in);/从weight.txt中读入权重的值if(!weight_file)exit(-1);for(k=0;kijw;G.arcsij=w;G.arcsji=G.arcsij;DisIntroduction.hvoid DisIntroduction(MGraph G)/提供景点的信息char n120;int v1;cout请输入所要查询的景点的名称:n1;int count1=0;for(int i=0;iG.vexnum;i+)int m = strcmp(G.vexsi.name,n1);if(m=0)v1=i;count1=count1+1;if(count1!=1)cout您输入的名称有误!endl;cout请选择要进行的操作(I:查询景点信息，P:查询两个景点之间的最短路径，Q:退出)endl;else cout该景点的简介为:tG.vexsv1.introductionendl;cout请选择要进行的操作(I:查询景点信息，P:查询两个景点之间的最短路径，Q:退出)endl;DisPath.hvoid DisPath(MGraph G)/查询任意两个景点之间的一条最短的简单路径int v1,v2;char n120,n220;cout请输入要查询的最短路径的两个顶点名称:n1n2;int count=0;for(int i=0;iG.vexnum;i+)int m1= strcmp(G.vexsi.name,n1);int m2= strcmp(G.vexsi.name,n2);if(m1=0)v1=i;count+;else if(m2=0)v2=i;count+;if(count!=2)cout您输入的名称有误!endl;cout请选择要进行的操作(I:查询景点信息，P:查询两个景点之间的最短路径，Q:退出)endl;ShortPath_DIJ(G,v1,v2);Exit.hvoid Exit() /退出cout欢迎下次继续使用!endl;exit(0);GraphADT.h#include GraphTypeDef.h#include CreateUDN.h#include ShortPath.h#include DisIntroduction.h#include DisPath.h#include Exit.hGraphTypeDef.h#define MAX_VERTEX_NUM 10typedef int AdjMatrixMAX_VERTEX_NUMMAX_VERTEX_NUM;typedef struct Vertex/定义图中顶点的数据类型int num;char name14;char introduction100;Vertex;typedef struct /定义图的数据类型Vertex vexsMAX_VERTEX_NUM;AdjMatrix arcs;int vexnum,arcnum;MGraph;void CreateUDN(MGraph &G);void ShortPath_DIJ(MGraph G,int v0,int v2);void DisIntroduction(MGraph G);void DisPath(MGraph G);void Exit();ShortPath.h#include#include#include#define MAXNUM 10000#define TRUE 1#define FALSE 0using namespace std;void ShortPath_DIJ(MGraph G,int v0,int v2)/Dijkstra算法求最短路径/Pathw表示从v0到w的最短路径；Dw表示从v0到w的最短距离int v,w,i,j,m;int PathMAX_VERTEX_NUMMAX_VERTEX_NUM;int PMAX_VERTEX_NUMMAX_VERTEX_NUM;int DMAX_VERTEX_NUM;int finalMAX_VERTEX_NUM;for(v=0;vG.vexnum;v+)/各对节点之间初始已知路径及距离finalv=FALSE;Dv=G.arcsv0v;for(w=0;wG.vexnum;w+)Pvw=FALSE;if(DvMAXNUM)Pvv0=TRUE;Pvv=TRUE;Dv0=0;finalv0=TRUE;int a20;for(i=0;iG.vexnum;i+)/对Pathij进行初始化，使其值全部为1000，便于后期的判断for(j=0;jG.vexnum;j+)Pathij=1000;for(i=0;iG.vexnum;i+)/对数组进行初始化，以便对Pathij进行描述ai=1;for(v=0;vG.vexnum;v+)/各条路线的初始节点为v0Pathv0=v0;/开始主循环，每次求解得到v0到某个v顶点的最短路径，并加入到S集合中for(i=1;iG.vexnum;i+)m=MAXNUM;/当前所知的离v0最近的距离for(w=0;wG.vexnum;w+)if(!finalw)/w顶点在V-S中if(Dwm)v=w;m=Dw;Pathvav=v;finalv=TRUE;for(w=0;wG.vexnum;w+)if(!finalw)&(m+G.arcsvwDw)Dw=m+G.arcsvw;/修改当前的最短路径的值int k0=1;aw=1;while(Pathvk0!=1000)/如果上述条件成立，Pathw路径需要改变，因为从v0到w的路径显然经过了v0和v之间的所有的点（包括v）Pathwk0=Pathvk0;k0+;aw+;cout两个景点之间的最短路径为:t;int k=0;while(Pathv2k!=1000)int m=Pathv2k;coutG.vexsm.namet;k+;coutendl;cout两个景点之间的最短距离为: Dv2Mendl;cout请选择要进行的操作(I:查询景点信息，P:查询两个景点之间的最短路径，Q:退出)endl;内部资料仅供参考内部资料仅供参考