公园导游管理系统.doc

计算机信息工程学院数 据 结 构课 程 设 计 报 告题 目： 公园导游系统 专 业： 计算机科学与技术（软件方向） 班 级： 学 号： 姓 名： 指导教师： 完成日期： 目 录一、概要设计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=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;二、详细设计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 Fprint-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标志,是否当前顶点属于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- 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，输入文件名filename20Fprint-Link(p，g，filename)SaveMap(g)L=P;结束图2- 5导入新文件结构示图三、测试分析3.1 可行性分析所谓可行性分析就是用最小的代价在尽可能短的时间内确定问题是否能够解决。这步工作的主要是要进行一次大大压缩简化了的系统分析和设计的过程，也就是在较高层次上以比较抽象的方式进行系统分析和设计的过程。可行性研究的最根本任务是对以后的行动方针提出建议，以避免时间、资源、人力和金钱的浪费，推荐一个较好的解决方案，并且为工程制定一个初步的计划。3.1.1技术可行性查找最短路径以及查询任意两景点之间的所有路径采用迪杰特斯拉算法或弗洛伊德算法实现。解决这个问题的一个方法是：每次以一个顶点为源点，重复执行迪杰斯特拉算法n次。这样，便可求得每一对顶点之间的最短路径。总的执行时间为O（n3）。虽然弗洛伊德算法时间复杂度也是O（n3），但形式简单些。从任意景点遍历全部的景点采用深度优先遍历或广度优先搜索遍历图实现。所谓可行性分析就是用最小的代价在尽可能短的时间内确定问题是否能够解决。这步工作的主要是要进行一次大大压缩简化了的系统分析和设计的过程，也就是在较高层次上以比较抽象的方式进行系统分析和设计的过程。可行性研究的最根本任务是对以后的行动方针提出建议，以避免时间、资源、人力和金钱的浪费，推荐一个较好的解决方案，并且为工程制定一个初步的计划。本系统采用人机操作进行管理，用visual C+ 6.0进行前台设计、系统随机产生数据，用户通过界面操作，系统自动给予合理分析，由于visual C+ 6.0功能强大、使用的灵活、良好的可扩展性、以及广泛实际应用，充分说明本系统在技术方面的可行性。3.1.2 工具可行性软件方面：信息时代对于软件的应用已不是人们的难题，人们在日常办公中用的计算机操作的系统等都属于软件部分。硬件方面：计算机普及到今天，人们对于它的拥有已不少见，它的硬件设备完全能够满足人们的需求，而价格也能被人们所接受。3.1.3 经济可行性线在大多数的公园景点及内容不断的增多和丰富，这也就使得整个公园系统不得不建立的更大。这也就为人们逛公园造成了很大的不便。人们往往不熟悉公园，找个东西，或某处带来了极大的不便。往往要花很多时间在这一方面。然而要是有一个公园导游系统这将给乘客带来极大的方便，使人们一下就能了解到这个公园的大致的情况。这是个超小型的性能分析系统，从投入的人力，财力与物力来讲是非常之小的，只要一台电脑，一台打印机，这个系统就可以搞起来，考虑到学校里有电脑，现只要购置一台打印机就可以了。从节省人力方面，可以让管理人员从繁与复杂的工作中解脱出来，做更多的工作，可以给读者提高到更深的一个层次。3.1.4 操作可行性本系统设计清晰，有良好的用户接口，操作简洁，完全可以给用户解决，并达到操作过程中的直观、方便、实用、安全等要求，因此操作方面具有可行性。3.2 需求分析3.2.1 功能需求对于游客，系统功能需求如下：能够浏览整个公园的信息、查询每一个景点的信息、从任意景点遍历全部的景点、能够查找最短路径。对于系统后台操作功能需求如下：删除地点、添加地点、添加路径、删除路径、保存修改、导入文件数据。3.2.2 输入输出的要求程序执行是需要有描述地图的文件，并放在相应的位置。文件中开始位置存放景点个数，图存在多少条边；接着是存放景点序号、名称、相关信息；对后是存放着各个景点之间的距离矩阵。执行程序先要先要进行选择。修改地图是要验证密码。查找任意两个景点的最短路径时，输入查找最短路径的两个点。运行各个小过程要求要输出的暂时的结果。四、使用说明与执行结果 4.1主界面 图4- 1主界面 4.2 游客界面 图4- 2 游客界面4.3 系统用户界面 图4- 3 系统用户登录界面图4- 4 系统用户界面4.5 浏览公园全景简图4- 5涉外公园简图 ， 4- 6详细信息表 4.6 寻找某一起点的最佳路径和指定起点、终点的最短路径图4- 7 查询最佳路径图4- 8 查询最短路径4.7 寻找指定起点、终点的所有路径图4- 9 输入两点之间的所有路径4.8 删除，添加结点，保存和导入新地图图4- 10 删除结点图4-10 导入新的地图17山西工商学院课程设计报告附 录（程序清单）#include#include#define INT_MAX 10000#define n 10int costnn;/* 边的值*/int shortestnn;/* 两点间的最短距离*/int pathnn;/* 经过的景点*/void welcome()printf(n 欢迎光临n);printf(n 凝香公园 nnnnn);printf(n 给您最纯净的享受n);printf(n Pure as the south polar snow nn);printf(n );system(pause); void Menu()/函数的主显示界面system(cls);system(color 70);printf( n);printf( 凝香公园导游系统 n);printf( n);printf( n);printf( n);printf( n);printf( 1：浏览公园全景 n);printf( n);printf( 2：最佳游览路线 n);printf( 主 n);printf( 3：查看单个景点 n);printf( 菜 n);printf( 4：游览线路查询 n);printf( 单 n);printf( 5：凝香公园简介 n);printf( n);printf( 6：退出导游系统 n);printf( n);printf( n);printf( n);printf( n);printf( n);printf(nn 请按键选择:);void Browser()printf(n 公园全景图 n);printf(n);printf( n);printf( 紫金大道 n);printf( 北 n);printf( n);printf( 1沁园 2公园大门 n);printf( n);printf( n);printf( 3梨园4春 园10夏园 n);printf( n);printf( n);printf( 5鼎湖 8秋园9冬园 n);printf( n);printf( n);printf( n);printf( 6聚缘阁7凝香园 n);printf( n);printf( n);printf( 2012年7月4日n);printf(n);void place() char z; printf(nnn【公园简介】n); printf(n n 凝香园也称“正春园”，位于菏泽城东岳程办事处岳楼行政村。nn); printf( 始建于元末明初，原为袁姓所有，称“袁家堂”花园。nn); printf( 凝香园是我国古代北方八大名园之一，俗称“何家花园”，距今有近1000余年的历史。nn); printf( 园中有百多年的刺柏、几百年的腊梅、紫丁香，千年翠兰松和一块假山石。nn); printf( “凝香园”附近的何应瑞墓地古柏成林，苍郁参天。nn); printf(n 注：本公园和真正的“凝香园”是同名，而非真实园林！n); printf(nnn); printf(nnn 请输入任意字符【返回主菜单】n); z=getchar();z=getchar();void go() printf(nnnnnn 感谢使用n); printf( n); printf( n); printf( n); printf( 请按任意键退出！ n); printf( n); printf( n); printf( 程序制作：陈明 n); printf( 学号：3100931036n); printf( nnnnnn); exit(0);void way() char z; printf(nn); printf( 本公园的最佳全景游览路线为：nn); printf( 2公园大门 1沁园 3梨园 5鼎湖 6聚缘阁 7凝香园 4春园 8秋园 9冬园 10夏园 2公园大门n); printf( 全程所需行程：276米!nn); printf( 如需其他路线请返回主菜单进入【浏览路线查询】n); printf(nnn); printf(nnn 请输入任意字符【返回主菜单】n); z=getchar(); z=getchar();void introduce()/*景点介绍*/ int a; char z; printf(请输入您想查询的景点编号:); scanf(%d,&a); getchar(); printf(nn【 查询结果：】nn); switch(a) case 1: printf( 1:沁园nn一首沁园春.雪让您对眼前的梅花感慨万千。n);break; case 2: printf( 2:公园大门nn仿古的气势宏伟建筑仿佛置身于100年前。n);break; case 3: printf( 3:梨园nn丛林间嬉戏的小鸟不禁让你回头倾听。n);break; case 4: printf( 4:春园nn广阔的草地伴着阵阵花香，躺在上面可以仰望南天。n);break; case 5: printf( 5:鼎湖nn 圆滑的湖面仿佛一面大鼎将湖水撑起来。n);break; case 6: printf( 6:聚缘阁nn来自大江南北的古玩古画齐聚一堂。n);break; case 7: printf( 7:凝香园nn神奇的南方小筑隐匿在桂花林中。聚香也。n);break; case 8: printf( 8:秋园nn当你独自一人行走在大片阔叶林里，才能感受自然的气息。n);break; case 9: printf( 9:冬园nn冬日恋歌在这里尽情唱响，High起来吧！n);break; case 10: printf( 10:夏园nn荷花池中一抹红，荷塘月色任你赏！n);break; default: printf( Error：景点编号输入错误！请输入110的数字编号！nn);break;printf(nn); void floyed()/*用floyed算法求两个景点的最短路径*/ int i,j,k; for(i=1;i=n;i+) for(j=1;j=n;j+) shortestij=costij; pathij=0; for(k=1;k=n;k+) for(j=1;j=n;j+) for(i=1;i(shortestik+shortestkj) /*用path记录从i到j的最短路径上点j的前驱景点的序号*/ shortestij=shortestik+shortestkj; pathij=k; pathji=k; void display(int i,int j)/* 打印两个景点的路径及最短距离 */ int a,b; a=i; b=j; printf(n【 查询结果：】nn); printf( 路径: ); if(shortestij!=INT_MAX) if(ij) printf( %d,b); while(pathij!=0) /* 把i到j的路径上所有经过的景点按逆序打印出来*/ printf( %d,pathij); if(ij) j=pathij; else i=pathji; printf( %d,a); printf(nn); printf( 距离：您需要步行 %dm才能到达目的地！,shortestab); else printf(%d,a); while(pathij!=0) /* 把i到j的路径上所有经过的景点按顺序打印出来*/ printf( %d,pathij); if(i请输入要查询的两个景点的编号(用空格键隔开):); scanf(%d %d,&i,&j); if(in|in|j0) printf(输入信息错误！nn); prin