公园导游管理系统..docx

计算机信息工程学院《数 据 结 构》课 程 设 计 报 告题 目： 公园导游系统 专 业： 计算机科学与技术（软件方向） 班 级： 学 号： 姓 名： 指导教师： 完成日期： 目 录一、概要设计11.题目的内容与要求1 1.1 程序模块61.2 系统涉及的数据结构61.2.1 程序数据结构71.2.2 具体数据类型定义7二、详细设计22.1 创建图（Fprint-Link）92.2 寻找最佳路径（DFSTraverse）92.3 最短路径（ShortPath）102.4 遍历出某一起点到终点的所有路径（SearchAllPath）122.5 导入新文件（Loadnewmap）13三、测试分析53.1 可行性分析43.1.1技术可行性43.1.2 工具可行性43.1.3 经济可行性43.1.4 操作可行性53.2 需求分析53.2.1 功能需求53.2.2 输入输出的要求5四、使用说明与执行结果64.1 主界面144.2 游客界面154.3 系统用户界面15附 录（程序清单）8一、概要设计1.题目的内容与要求1.1课题的研究背景、要求和意义现代公园范围的广阔，内容不断的增加，使得公园整个系统变得复杂。使用电脑对游客进行导游成为发展的趋势，以达到更好的为游客服务的目的。对于公园的游客来说，他们要求：能够浏览整个公园的信息、查询每一个景点的信息、从任意景点遍历全部的景点、能够查找最短路径。对于系统用户来说，他们要求：删除地点、添加地点、添加路径、删除路径、保存修改、导入文件数据。采用图这么一种数据结构，采用邻接表的存储方式，用一个二维数组来记录所有的边，为了实现地图的随时更新，采用了静态链表实现对图的接点的添加，删除。应用文件的读写来进行文件操作。查找最短路径采用迪杰特斯拉算法实现，从任意景点遍历全部的景点采用深度优先遍历实现。对于界面设计，游客不能进行地图的修改，更换，所以首先要验证身份，再出现对应的界面。2.总体设计程序模块从文件中对出数据(Fprint-Link())：通过调用Update(L,g)，先将链表L的信息赋值给邻接数组g中，进行更新。 建立无向图，把公园的景点及景点的信息，连接起来建立邻接表采用链式加顺式存储。浏览学校的全景（Browser）：列出学校的所有的景点。寻找最佳路径（DFSTraverse：）：输入一个景点，会吧所有都浏览一边，并找出最佳的路径。最短路径（ShortPath）:求出起点和终点的最佳路径，并求出最佳路径的长度。遍历出某一起点到终点的所有路径（SearchAllPath）：找出所有路径，利用深度优先遍历。删除地点、添加地点、添加路径、删除路径、保存修改、导入文件数据。对应代码函数如下：DeleteAdv(L,g)、InsertAdv(L,g)、InsertEdge()、DeleteEdge()、SaveMap(g)、Loadnewmap(p,g)。总体结构设计如图1-1所示。图1- 1 系统框架图3.系统数据结构3.1 程序数据结构程序主要用了图和静态链表两种数据结构，采用矩阵来保存图形结构的地图，用数组来保存遍历经过的结点用以遍历回溯，以及存储最最终路径。图的抽象数据类型：ADT Graph{数据对象V：V是具有相同特性的数据元素的集合，称为顶点集。数据关系：R={VR}VR=｛v,w|v,w∈v且P(v,w)表示从v到w的弧，谓词P（v,w）定义了弧v,w的意义或信息｝基本操作P：PrintMap(g) Serach(g)DFSTraverse(g)ShortPath(g)。｝ADT Graph线性链表的抽象数据类型：ADT List｛数据对象：D=｛ai|ai∈ElemSet，i=1，2，…,n,n≥0｝数据关系：R1=｛ai-1,ai|ai-1,ai∈D,i=2, …,n｝基本操作: DeleteAdv(L,g) InsertAdv(L,g)InsertEdge() DeleteEdge()SaveMap(g) Loadnewmap(p,g)｝ADT List。 3.2.2 具体数据类型定义typedef struct LNode{char name[30];int num;char introduction[100];struct LNode *next;}LNode,*Link;typedef struct ArcNode{int data; //该弧所得指向的顶点的位置ArcNode *nextarc; //指向下一条弧的指针}ArcNode,*ArcLink;typedef struct VNode //顶点信息{char name[30];int num; char introduction[100];ArcLink firstarc; //指向