《公园导游管理系统.doc》由会员分享，可在线阅读，更多相关《公园导游管理系统.doc（28页珍藏版）》请在金锄头文库上搜索。
1、。计算机信息工程学院数 据 结 构课 程 设 计 报 告题 目： 公园导游系统 专 业： 计算机科学与技术（软件方向） 班 级： 学 号： 姓 名： 指导教师： 完成日期： -可编辑修改-目 录一、概要设计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三
2、、测试分析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课题的研究背景、要求和意义现代公园范围的广阔，内容不断的增加，使得公园整个系统变得复杂。使用电脑对游客进行导游成为发展的趋势，以达到更好的为游客服务的目的。对于公园的游客来说，他们要求：能够浏览整个公园的信息、查询每一个景点的信息、从任意景点遍历全部的景点、能
3、够查找最短路径。对于系统用户来说，他们要求：删除地点、添加地点、添加路径、删除路径、保存修改、导入文件数据。采用图这么一种数据结构，采用邻接表的存储方式，用一个二维数组来记录所有的边，为了实现地图的随时更新，采用了静态链表实现对图的接点的添加，删除。应用文件的读写来进行文件操作。查找最短路径采用迪杰特斯拉算法实现，从任意景点遍历全部的景点采用深度优先遍历实现。对于界面设计，游客不能进行地图的修改，更换，所以首先要验证身份，再出现对应的界面。2.总体设计程序模块从文件中对出数据(Fprint-Link()：通过调用Update(L,g)，先将链表L的信息赋值给邻接数组g中，进行更新。 建立无向图
4、，把公园的景点及景点的信息，连接起来建立邻接表采用链式加顺式存储。浏览学校的全景（Browser）：列出学校的所有的景点。寻找最佳路径（DFSTraverse：）：输入一个景点，会吧所有都浏览一边，并找出最佳的路径。最短路径（ShortPath）:求出起点和终点的最佳路径，并求出最佳路径的长度。遍历出某一起点到终点的所有路径（SearchAllPath）：找出所有路径，利用深度优先遍历。删除地点、添加地点、添加路径、删除路径、保存修改、导入文件数据。对应代码函数如下：DeleteAdv(L,g)、InsertAdv(L,g)、InsertEdge()、DeleteEdge()、SaveMap(
5、g)、Loadnewmap(p,g)。总体结构设计如图1-1所示。删除地点主模块系统用户游客模块添加地点添加路径删除路径保存存修改入文件数据任意景点遍历查询景点信息和浏览公园简图查询任意两个景点最短的路径遍历输出任意一个景点的所有路径图1- 1 系统框架图3.系统数据结构3.1 程序数据结构程序主要用了图和静态链表两种数据结构，采用矩阵来保存图形结构的地图，用数组来保存遍历经过的结点用以遍历回溯，以及存储最最终路径。图的抽象数据类型：ADT Graph数据对象V：V是具有相同特性的数据元素的集合，称为顶点集。数据关系：R=VRVR=|v,wv且P(v,w)表示从v到w的弧，谓词P（v,w）定义
6、了弧的意义或信息基本操作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;cha
7、r 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
8、 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(s
9、izeof(ArcNode); q-data=b; q-nextarc=ga.firstarc; ga.firstarc=q;二、详细设计2.1 创建图（Fprint-Link）从文件中读出数据，函数流程图2-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赋值图2- 1 F
10、print-Link函数流程图2.2 寻找最佳路径（DFSTraverse）利用深度优先的思想，遍历图找出一条最佳最佳的的路径，让它遍历所有景点。利用递归的思想，往下遍历，访问标志位，若访问过在下次就不用访问。若找完一个分支在下次重新遍历，函数流程如图2-2所示。开始初始化visitv=0/初始化标志位If（visitv=0）DFS(g,v,visited); v+Count+Count=n结束YN图2- 2 寻找最佳路径流程图2.3 最短路径（ShortPath）利用迪杰特斯拉算法，求v0到其余顶点的最短路径path,distance 是用来存放各路径的权值，借助辅助数组s标志,是否当前顶点
11、属于S(1,属于) 函数流程图2-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图2
12、- 3 寻找最短路径流程图2.4 遍历出某一起点到终点的所有路径（SearchAllPath） 利用图的深度优先遍历，利用访问标志位。path记录路径，visited设访问标志，v起点，des终点，length，代表的是访问景点的长度。若碰见死路或者不同的路，则从上一个景点，从新扫描，searchAllPath()流程如图2-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图2- 4 searchAllPath()流程图2.5 导入新文件（Loadnewmap）将指定文件导入到邻接表中，再保存到zheke1.txt 中 ,具体实现如图2-5所示。开始初始化Link p，输入文
