公园导游图数据结构课程设计

课程名称：数据结构 湖南涉外经济学院本科学生课程设计（论文）题 目 公园导游图 姓 名 唐 哲 学 号 学 部 计算机科学与技术 专业、年级 指 导 教 师 2011 年 12 月 8 日摘 要随着中国经济不断的发展，城市发展的越来越好，越来越多的人融入了城市生活。公园成为人们散心，娱乐的场所，公园也随即也在不断的扩张，变得越来越全面，但是这不利于逛公园的人寻找自己想要去的地方，尤其是对公园陌生的游客，更是不知道如何走，才能更好的游玩公园，达到的最好经济效益。所以针对这种现象，为了方便游客，开发这么一款公园导游系统软件。系统是用C语言实现，基于visual c+6.0 开发的，采用图这么一种数据结构，采用邻接矩阵的存储方式，用一个二维数组来记录所有的边，为了实现地图的随时更新，采用了静态链表实现对图的接点的添加，删除。本系统设计基于图的结构，创建一个无向图，针对游客的需求，将涉外公园的景点编号、名称、介绍等信息放入到图的顶点当中并保存景点文本文件中，将两个景点的编号和它们之间的距离当权值也保存在相同的文本文件中，利用迪杰特斯拉算法来求从一个景点到另一个景点的最短距离，利用Serach（）；查找景点，本显示他的信息，从而解决了要查找景点信息和两个景点之间的最短路径的问题，最后按照显示屏上的提示进行相关的操作。关键词： 公园导游；图；邻接矩阵；二维数组；静态链目 录第一章 前 言11.1课题的研究背景、要求和意义11.2课题的目标、研究范围11.3理论技术方案的选取21.4研究方法21.5结构与安排2第二章 系统功能分析42.1 可行性分析42.1.1技术可行性42.1.2 工具可行性42.1.3 经济可行性42.1.4 操作可行性52.2 需求分析52.2.1 功能需求52.2.2 输入输出的要求5第三章 总体设计63.1 程序模块63.2 系统涉及的数据结构63.2.1 程序数据结构73.2.2 具体数据类型定义7第四章 详细设计94.1 创建图（Fprint-Link）94.2 寻找最佳路径（DFSTraverse）94.3 最短路径（ShortPath）104.4 遍历出某一起点到终点的所有路径（SearchAllPath）124.5 导入新文件（Loadnewmap）13第五章 系统实现145.1 程序执行之前的准备145.2 主界面145.3 游客界面155.4 系统用户界面155.5 浏览公园全景简图165.6 寻找某一起点的最佳路径和指定起点、终点的最短路径165.7 寻找指定起点、终点的所有路径175.8 删除，添加结点，保存和导入新地图17第六章 解决的关键问题186.1 如何实现寻找最短路径功能186.2 如何实现深度优先搜索186.3 如何修改地图186.4如何导入其他文件信息18第七章 结 论19结 束 语20参考文献21第一章 前 言1.1课题的研究背景、要求和意义现代公园范围的广阔，内容不断的增加，使得公园整个系统变得复杂。使用电脑对游客进行导游成为发展的趋势，以达到更好的为游客服务的目的。对于公园的游客来说，他们要求：能够浏览整个公园的信息、查询每一个景点的信息、从任意景点遍历全部的景点、能够查找最短路径。对于系统用户来说，他们要求：删除地点、添加地点、添加路径、删除路径、保存修改、导入文件数据。采用图这么一种数据结构，采用邻接表的存储方式，用一个二维数组来记录所有的边，为了实现地图的随时更新，采用了静态链表实现对图的接点的添加，删除。应用文件的读写来进行文件操作。查找最短路径采用迪杰特斯拉算法实现，从任意景点遍历全部的景点采用深度优先遍历实现。对于界面设计，游客不能进行地图的修改，更换，所以首先要验证身份，再出现对应的界面。1.2课题的目标、研究范围实现的目标：实现对某一个公园导游及地图的修改与更新的系统。通过系统分析、系统设计、编程调试，写实验报告等环节，进一步掌握应用系统设计的方法和步骤，灵活运用并深刻理解典型数据结构在软件开发中的应用 。综合运用数据结构课程中学到的几种典型数据结构，如链表，栈，队列，以及程序设计语言（C语言），自行实现一个较为完整的应用系统的设计与开发，对自己学过的知识进一步的加深理解，对数据结构的算法思想要有更深的理解。图（Graph）是一种较线性表和树更为复杂的数据结构。在线性表中，数据元素之间仅有线性关系，每个数据元素只有一个直接前驱和一个直接后继；在树形结构中，数据元素之间有着明显的层次关系，并且每一层上的数据元素可能和下一层中多个元素（即其该子结点）相关，但只能和上一层中一个元素（即其双亲结点）相关，而在图形结构中，结点之间的关系可以是任意的，图中任意两个数据元素之间都可能相关。由此，图的应用极为广泛，特别是近年来的迅速发展，已渗入到诸如语言学、逻辑学、物理、化学、电讯工程、计算机科学以及数学的其他分支中。1.3理论技术方案的选取邻接矩阵存储结构对图的构造操作的实现框架，他根据图G的种类调用具体构造算法。如果G是无向图，则构造一个具有n个顶点和e条边的无向网G的时间复杂度是O（n2+e*n），其中对邻接矩阵G.arcs的初始化耗费了O（n2）的时间。这个存储结构上易于实现课题所需的基本操作，在建立邻接表或逆邻接表，时间复杂度为（n+e），需要通过查找才能得到顶点图中位置，时间复杂度为O（n*e）。在邻接表上容易找到任一顶点的的第一个邻接点和下一邻接点，但要判定任意两个顶点（vi和vj）之间是否有边或弧相连，则需要搜索第i个或第j个链表，因此，不及邻接矩阵方便。1.4研究方法基于Visual C+ 6.0平台编程是当今程序者的青睐，它有着强大的性能、完全丰富的工具及高速的处理速度和完备的兼容性。不仅可以简化编程的设计并且算法应用灵活，使应用程序的开发更为简便。C+是为开发大型程序而研制的，它比C语言困难得多，它功能丰富、表达能力强、使用灵活方便、应用面广、目标程序效率高、可移植性好，既具有高级语言的优点，又具有低级语言的许多特点，完全适合于编写系统软件；本人就利用上述C+开发软件编写了公园导游系统，采用人机互动的操作模式，系统经过显示主界面功能，然后用户的需要操作。1.5结构与安排首先“前言”对研究背景和研究目的作了简单的介绍；其次“系统功能分析”对本系的说明和讲解；再次“总体设计”对本系统做了一个简要引导，并且通过“总体设计”对该系统的运行懂得差不多了；“详细设计”就是对系统有了详细的设计过程，更进一步知道设计原理；“排序算法的改进” 介绍传统算法的不足，经过设想对原算法加以改进“系统实现”不但让我们知道了系统的界面和一些操作的实施，让你知道整个算法的设计并且加以理解。第二章 系统功能分析2.1 可行性分析所谓可行性分析就是用最小的代价在尽可能短的时间内确定问题是否能够解决。这步工作的主要是要进行一次大大压缩简化了的系统分析和设计的过程，也就是在较高层次上以比较抽象的方式进行系统分析和设计的过程。可行性研究的最根本任务是对以后的行动方针提出建议，以避免时间、资源、人力和金钱的浪费，推荐一个较好的解决方案，并且为工程制定一个初步的计划。技术可行性查找最短路径以及查询任意两景点之间的所有路径采用迪杰特斯拉算法或弗洛伊德算法实现。解决这个问题的一个方法是：每次以一个顶点为源点，重复执行迪杰斯特拉算法n次。这样，便可求得每一对顶点之间的最短路径。总的执行时间为O（n3）。虽然弗洛伊德算法时间复杂度也是O（n3），但形式简单些。从任意景点遍历全部的景点采用深度优先遍历或广度优先搜索遍历图实现。所谓可行性分析就是用最小的代价在尽可能短的时间内确定问题是否能够解决。这步工作的主要是要进行一次大大压缩简化了的系统分析和设计的过程，也就是在较高层次上以比较抽象的方式进行系统分析和设计的过程。可行性研究的最根本任务是对以后的行动方针提出建议，以避免时间、资源、人力和金钱的浪费，推荐一个较好的解决方案，并且为工程制定一个初步的计划。本系统采用人机操作进行管理，用visual C+ 6.0进行前台设计、系统随机产生数据，用户通过界面操作，系统自动给予合理分析，由于visual C+ 6.0功能强大、使用的灵活、良好的可扩展性、以及广泛实际应用，充分说明本系统在技术方面的可行性。 工具可行性软件方面：信息时代对于软件的应用已不是人们的难题，人们在日常办公中用的计算机操作的系统等都属于软件部分。硬件方面：计算机普及到今天，人们对于它的拥有已不少见，它的硬件设备完全能够满足人们的需求，而价格也能被人们所接受。 经济可行性线在大多数的公园景点及内容不断的增多和丰富，这也就使得整个公园系统不得不建立的更大。这也就为人们逛公园造成了很大的不便。人们往往不熟悉公园，找个东西，或某处带来了极大的不便。往往要花很多时间在这一方面。然而要是有一个公园导游系统这将给乘客带来极大的方便，使人们一下就能了解到这个公园的大致的情况。这是个超小型的性能分析系统，从投入的人力，财力与物力来讲是非常之小的，只要一台电脑，一台打印机，这个系统就可以搞起来，考虑到学校里有电脑，现只要购置一台打印机就可以了。从节省人力方面，可以让管理人员从繁与复杂的工作中解脱出来，做更多的工作，可以给读者提高到更深的一个层次。 操作可行性本系统设计清晰，有良好的用户接口，操作简洁，完全可以给用户解决，并达到操作过程中的直观、方便、实用、安全等要求，因此操作方面具有可行性。2.2 需求分析2.2.1 功能需求对于游客，系统功能需求如下：能够浏览整个公园的信息、查询每一个景点的信息、从任意景点遍历全部的景点、能够查找最短路径。对于系统后台操作功能需求如下：删除地点、添加地点、添加路径、删除路径、保存修改、导入文件数据。2.2.2 输入输出的要求程序执行是需要有描述地图的文件，并放在相应的位置。文件中开始位置存放景点个数，图存在多少条边；接着是存放景点序号、名称、相关信息；对后是存放着各个景点之间的距离矩阵。执行程序先要先要进行选择。修改地图是要验证密码。查找任意两个景点的最短路径时，输入查找最短路径的两个点。运行各个小过程要求要输出的暂时的结果。第三章 总体设计3.1 程序模块从文件中对出数据(Fprint-Link()：通过调用Update(L,g)，先将链表L的信息赋值给邻接数组g中，进行更新。 建立无向图，把公园的景点及景点的信息，连接起来建立邻接表采用链式加顺式存储。浏览学校的全景（Browser）：列出学校的所有的景点。寻找最佳路径（DFSTraverse：）：输入一个景点，会吧所有都浏览一边，并找出最佳的路径。最短路径（ShortPath）:求出起点和终点的最佳路径，并求出最佳路径的长度。遍历出某一起点到终点的所有路径（SearchAllPath）：找出所有路径，利用深度优先遍历。删除地点、添加地点、添加路径、删除路径、保存修改、导入文件数据。对应代码函数如下：DeleteAdv(L,g)、InsertAdv(L,g)、InsertEdge()、DeleteEdge()、SaveMap(g)、Loadnewmap(p,g)。总体结构设计如图3-1所示。删除地点主模块系统用户游客模块添加地点添加路径删除路径保存存修改入文件数据任意景点遍历查询景点信息和浏览公园简图查询任意两个景点最短的路径遍历输出任意一个景点的所有路径图3- 1 系统框架图3.2 系统涉及的数据结构3.2.1 程序数据结构程序主要用了图和静态链表两种数据结构，采用矩阵来保存图形结构的地图，用数组来保存遍历经过的结点用以遍历回溯，以及存储最最终路径。图的抽象数据类型：ADT Graph数据对象V：V是具有相同特性的数据元素的集合，称为顶点集。数据关系：R=VRVR=|v,wv且P(v,w)表示从v到w的弧，谓词P（v,w）定义了弧的意义或信息基本操作P：PrintMap(g) Serach(g)DFSTraverse(g)ShortPath(g)。ADT Graph线性链表的抽象数据类型：ADT List数据对象：D=ai|aiElemSet，i=1，2，,n,n0数据关系：R1=|ai-1,aiD,i=2, ,n基本操作: DeleteAdv(L,g) InsertAdv(L,g)InsertEdge() DeleteEdge()SaveMap(g) Loadnewmap(p,g)ADT List。 3.2.2 具体数据类型定义typedef struct LNodechar name30;int num;char introduction100;struct LNode *next;LNode,*Link;typedef struct ArcNodeint data; /该弧所得指向的顶点的位置ArcNode *nextarc; /指向下一条弧的指针ArcNode,*ArcLink;typedef struct VNode /顶点信息char name30;int num; char introduction100;ArcLink firstarc; /指向第一条依附该顶点的弧的指针VNode,AdjListMAX+1;typedef struct ALGraphAdjList vdata; int vexnum,arcnum; /图的顶点数和弧数ALGraph;int EdgeMAXMAX; /用来存放路径的权值int n,e;/存放结点数和边数读取文件信息代码如下：for(i=1;i=n;i+)fscanf(fp,%d,&num);fscanf(fp,%s,name);fscanf(fp,%s,information);ListInsert(L, num, name, information);Update(L,g); for ( j=1;jdata=a; p-nextarc=gb.firstarc; gb.firstarc=p; /把p插进来 q=(ArcLink)malloc(sizeof(ArcNode); q-data=b; q-nextarc=ga.firstarc; ga.firstarc=q;第四章 详细设计4.1 创建图（Fprint-Link）从文件中读出数据，函数流程图4-1所示。结束j+开始读入n,eArcLink p,q;初始化链表，邻接表，Eage i=1,j=1，p=q=(ArcLink)malloc(sizeof(ArcNode);inextarc=gb.firstarc; gb.firstarc=p; /把p插进来q-nextarc=ga.firstarc; ga.firstarc=q;j=eYNUpdate(L,g);/给g赋值图4- 1 Fprint-Link函数流程图4.2 寻找最佳路径（DFSTraverse）利用深度优先的思想，遍历图找出一条最佳最佳的的路径，让它遍历所有景点。利用递归的思想，往下遍历，访问标志位，若访问过在下次就不用访问。若找完一个分支在下次重新遍历，函数流程如图4-2所示。开始初始化visitv=0/初始化标志位If（visitv=0）DFS(g,v,visited); v+Count+Count=n结束YN图4- 2 寻找最佳路径流程图4.3 最短路径（ShortPath）利用迪杰特斯拉算法，求v0到其余顶点的最短路径path,distance 是用来存放各路径的权值，借助辅助数组s标志,是否当前顶点属于S(1,属于) 函数流程图4-3所示。 开始初始化distence，s,path开始主循环 ，每次求得v0到某顶点v的最短距离，并将v并入中minDis=MAXEDGE;/当前所知v0的最短距离并设初值为MAXEAGE，int i=1,j=1,u=v0;!sj&distancejminDisu=j;/在s下一直往下找minDis=distancej ;j=nj=0;更新当前最短路径及距离；newDist=distanceu+GetWeightudistancej=newDist;pathj=u;/记录寻找的最短的路径i=n结束If(newDistdistancej)j=nYNYNYYN图4- 3 寻找最短路径流程图4.4 遍历出某一起点到终点的所有路径（SearchAllPath） 利用图的深度优先遍历，利用访问标志位。path记录路径，visited设访问标志，v起点，des终点，length，代表的是访问景点的长度。若碰见死路或者不同的路，则从上一个景点，从新扫描，searchAllPath()流程如图4-4所示。If（visitedV）returen;/若所有景点都访问过，则终止v=desPrintfPath(G,path,length);visitedv=1;GetWeight(v,i)!=MAXEDG&!visitediSearchAllPath(G,path,visited,i,des,length+1)i+i=n结束开始NYvisitedv=0;NY图4- 4 searchAllPath()流程图4.5 导入新文件（Loadnewmap）将指定文件导入到邻接表中，再保存到zheke1.txt 中 ,具体实现如图4-5所示。开始初始化Link p，输入文件名filename20Fprint-Link(p，g，filename)SaveMap(g)L=P;结束图4- 5导入新文件结构示图第五章 系统实现5.1 程序执行之前的准备首先在zheke1.txt中保存内容图5-1所示北门理工天堂汽车展览中心微澜湖东门餐厅哲科技术中心静心湖体育中心爱情博物馆涉外花园华天大酒店巾帼纪念堂56715710456553555765南门图5- 1 涉外公园简图在zheke2.txt中保存内容图5-2所示3长沙市邵阳市衡阳市隆回县710126825株洲市图5- 2 城市连通图5.2 主界面表5- 1主界面5.3 游客界面表5- 2 游客界面5.4 系统用户界面表5- 3 系统用户登录界面表5- 4 系统用户界面5.5 浏览公园全景简图 表5- 5涉外公园简图 表5- 6详细信息表5.6 寻找某一起点的最佳路径和指定起点、终点的最短路径表5- 7 查询最佳路径表5- 8 查询最短路径5.7 寻找指定起点、终点的所有路径表5- 9 输入两点之间的所有路径5.8 删除，添加结点，保存和导入新地图表5- 10 删除结点 表5- 10 导入新的地图第六章 解决的关键问题6.1 如何实现寻找最短路径功能我在网上查了很多资料，在考虑好用邻接表做系统后，我一直在寻找一种合适的算法来实现查找最短路径的功能。最终我决定采用迪杰特斯拉算法。解决了这一难题。6.2 如何实现深度优先搜索系统采用一个数组来做访问过的标记，如果正在访问结点的下一个结点没有访问，就采用函数的递归来实现深度优先搜索。6.3 如何修改地图通过对链表中结点的修改，就能对邻接表中结点的修改，在删除结点时，通过将后面结点的边信息将次结点的信息覆盖，即Edgeij=Edgei+1j; Edgeij=Edgei+1j;至于边的添加与删除，直接修改Eage的值即可6.4如何导入其他文件信息导入其他文件时，老是出错，困扰了我很久，后来我通过一个一个程序测试，终于找到了问题所在，当再导入文件信息时，我用到的还是原来那个链表指针，于是我又新建了一个链表，将文件信息导入到这个新的链表中，然后将原来链表的头指针指向它，问题得以解决。第七章 结 论通过努力，公园导游系统最后完成，这个系统能够提高公园的服务质量，能够快速的查询景点信息，大大的方便了游客，还能便于公园信息的更新。但是此系统只能查询一个大的地点，不能查找的详细的位置，边的不能更好的描述等等。系统还可以添加跟多使用的功能，比如说：“查询票的信息功能、验票、由大地点查询更具体的位置”等等，这些都是值得去研究的。系统存在问题: 当导入新文件导入时，原来的链表内存没有释放结 束 语这次课程设计让我学到了很多，课程设计开始之前，我看了别做的系统，认真的分析了别人的代码，当我弄懂了迪杰特斯拉算法和弗洛伊德算法时，我就开始编写自己的系统。我想再添加一些新的功能，但是这两周下来我当然也感到累，也有心情烦躁的时候，体会到调试成功使的那种喜悦。 课程设计之前老师让我们自己先将设计思路写好，都做了哪些模块，第一天要检查。我当时是在电脑上写了，那天下午编了一下午，没什么成就弄得我很心烦第二天老师检查时我什麽都没有看到同学的程序我开始着急了，但那会我只有一个念头我得从新开始，由于对图不是很了解，我就从读写模块开始，就使用简单的C语知识，那天早上将那两个模块给拿下了。下机后我在寝室开始编程，开始进入真正的图部分，边思考怎样可以将它们联系起来，边进行调试。对编程兴趣很浓，直到晚上十点我已经将老师的要求完成差不多。这些日子是很辛苦，但我学到了很多东西，和同学一起分享调试成功的那种喜悦，我完成的早，同学有问题会让我帮助，在帮他们的过程中我也学会了很多种不同的思想，让我对图有了更深刻的理解。 参考文献1 耿国华.数据结构-c语言描述M.北京：高等教育出版社，1998.5682.2 吴伟民，严蔚敏.数据结构（c语言版）M.北京：清华大学出版社，1997.4142.