公园导游管理系统

1、计算机信息工程学院数据结构课程设计报告题 目：公园游系统专 业：计算机科学与技术（软件方向）班 级：学 号：姓 名：指导教师：完成日期：目 录一、概要设计 41 .题目的内容与要求41.1 程序模块 41.2 系统涉及的数据结构 错误！未定义书签。1.2.1 程序数据结构 51.2.2 具体数据类型定义 6二、详细设计 82.1 创建图（FPRINT-L INK） 82.2 寻找最佳路径（DFS'RaversE 92.3 最短路径（ShorPatH 92.4 遍历出某一起点到终点的所有路径（SearcAllPath） 112.5 导入新文件（LoadnewiMap 12三、测试分析12

2、3.1 可行性分析 123.1.1 技术可行性 133.1.2 工具可行性 133.1.3 经济可行性 133.1.4 操作可行性 143.2 需求分析 143.2.1 功能需求 143.2.2 输入输出的要求 14四、使用说明与执行结果 144.1 主界面 144.2 游客界面 154.3 系统用户界面 15附 录（程序清单）1一、概要设计1 .题目的内容与要求1.1 课题的研究背景、要求和意义现代公园范围的广阔，内容不断的增加，使得公园整个系统变得复杂。使 用电脑对游客进行导游成为发展的趋势，以达到更好的为游客服务的目的。对于公园的游客来说，他们要求：能够浏览整个公园的信息、查询每一个 景

3、点的信息、从任意景点遍历全部的景点、能够查找最短路径。对于系统用户 来说，他们要求：删除地点、添加地点、添加路径、删除路径、保存修改、导 入文件数据。采用图这么一种数据结构，采用邻接表的存储方式，用一个二维数组来记 录所有的边，为了实现地图的随时更新，采用了静态链表实现对图的接点的添 加，删除。应用文件的读写来进行文件操作。查找最短路径采用迪杰特斯拉算法实现，从任意景点遍历全部的景点采用 深度优先遍历实现。对于界面设计，游客不能进行地图的修改，更换，所以首先要验证身份， 再出现对应的界面。2 .总体设计程序模块从文件中对出数据(Fprint-Link()：通过调用Update(L,g),先将链

4、表L的信 息赋值给邻接数组g中，进行更新。建立无向图，把公园的景点及景点的信息， 连接起来建立邻接表采用链式加顺式存储。浏览学校的全景(Browser):列出学校的所有的景点。寻找最佳路径(DFSTraverse):输入一个景点，会吧所有都浏览一边，并 找出最佳的路径。最短路径(ShortPath :求出起点和终点的最佳路径，并求出最佳路径的长 度。遍历出某一起点到终点的所有路径(SearchAllPath):找出所有路径，利用 深度优先遍历删除地点、添加地点、添加路径、删除路径、保存修改、导入文件数据。对应代码函数如下：DeleteAdv(L,g)、InsertAdv(L,g)、Insert

5、Edge。DeleteEdge。SaveMap(gb Loadnewmap(p,g)总体结构设计如图1-1所示图1- 1系统框架图3 .系统数据结构3.1 程序数据结构程序主要用了图和静态链表两种数据结构，采用矩阵来保存图形结构的地 图，用数组来保存遍历经过的结点用以遍历回溯，以及存储最最终路径。图的抽象数据类型：ADT Graph数据对象V： V是具有相同特性的数据元素的集合，称为顶点集。数据关系：R=VRVR= <v,w>|v,w v 且 P(v,w)表示从 v 到 w 的弧，谓词 P (v,w)定义了弧<v,w>的意义或信息基本操作 P： PrintMap(g)S

6、erach(g)DFSTraverse(g)ShortPath(g) ADT Graph线性链表的抽象数据类型：ADT List 数据对象：D= ai|aiC 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 Listo3.2.2具体数据类型定义typedef struct LNodechar name30;int num;char in

7、troduction100;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

8、,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;j<=e;j+)从文件中读入边的信息fscanf(fp,"%

9、d",&a);fscanf(fp,"%d",&b);fscanf(fp,"%d",&weight);Edgeab=weight;Edgeba=weight;p=(ArcLink)malloc(sizeof(ArcNode); 为顶点申请空间 p->data=a;p->nextarc=gb.firstarc;gb.firstarc=p;/把 p 插进来q=(ArcLink)malloc(sizeof(ArcNode);q->data=b;q->nextarc=ga.firstarc;ga.first

10、arc=q;、详细设计2.1 创建图(Fprint-Link)从文件中读出数据，函数流程图2-1所示图 2- 1 Fprint-Link函数流程图2.2 寻找最佳路径（DFSTraverse利用深度优先的思想，遍历图找出一条最佳最佳的的路径，让它遍历所有 景点。利用递归的思想，往下遍历，访问标志位，若访问过在下次就不用访问。若找完一个分支在下次重新遍历，函数流程如图 2-2所示。2.3 最短路径（ShortPath）利用迪杰特斯拉算法，求v0到其余顶点的最短路径path口,distance 借用来存放各路径的权值，借助辅助数组s口标志，是否当前顶点属于S（1属于）函数流程图2-3所示。开始di

11、stancej=newDist;pathj=u;/ 记录寻找的最短J<=n结束图2- 3寻找最短路径流程图2.4 遍历出某一起点到终点的所有路径(SearchAllPath)利用图的深度优先遍历，利用访问标志位。path记录路径，visited口 设访问标志，v起点，des终点，length,代表的是访问景点的长度。若碰见死 路或者不同的路，则从上一个景点，从新扫描，searchAllPath(流程如图2-4所 示。图 2- 4 searchAllPath() 流程图2.5 导入新文件(Loadnewmap将指定文件导入到邻接表中，再保存到 zheke1.txt中 具体实现如图2-5所示

12、。图2- 5导入新文件结构示图三、测试分析3.1 可行性分析所谓可行性分析就是用最小的代价在尽可能短的时间内确定问题是否能够 解决。这步工作的主要是要进行一次大大压缩简化了的系统分析和设计的过程, 也就是在较高层次上以比较抽象的方式进行系统分析和设计的过程。可行性研 究的最根本任务是对以后的行动方针提出建议，以避免时间、资源、人力和金 钱的浪费，推荐一个较好的解决方案，并且为工程制定一个初步的计划。3.1.1 技术可行性查找最短路径以及查询任意两景点之间的所有路径采用迪杰特斯拉算法或 弗洛伊德算法实现。解决这个问题的一个方法是：每次以一个顶点为源点，重 复执行迪杰斯特拉算法n次。这样，便可求得

13、每一对顶点之间的最短路径。总 的执行时间为O (n3)。虽然弗洛伊德算法时间复杂度也是 O (n3),但形式简 单些。从任意景点遍历全部的景点采用深度优先遍历或广度优先搜索遍历图实现。所谓可行性分析就是用最小的代价在尽可能短的时间内确定问题是否能够 解决。这步工作的主要是要进行一次大大压缩简化了的系统分析和设计的过程， 也就是在较高层次上以比较抽象的方式进行系统分析和设计的过程。可行性研 究的最根本任务是对以后的行动方针提出建议，以避免时间、资源、人力和金 钱的浪费，推荐一个较好的解决方案，并且为工程制定一个初步的计划。本系统采用人机操作进行管理，用visual C+ 6.0进行前台设计、系统

14、随机 产生数据，用户通过界面操作，系统自动给予合理分析，由于 visual C+ 6.0 功能强大、使用的灵活、良好的可扩展性、以及广泛实际应用，充分说明本系 统在技术方面的可行性。3.1.2 工具可行性软件方面：信息时代对于软件的应用已不是人们的难题，人们在日常办公中用的计算 机操作的系统等都属于软件部分。硬件方面：计算机普及到今天，人们对于它的拥有已不少见，它的硬件设备完全能够 满足人们的需求，而价格也能被人们所接受。3.1.3 经济可行性线在大多数的公园景点及内容不断的增多和丰富，这也就使得整个公园系 统不得不建立的更大。这也就为人们逛公园造成了很大的不便。人们往往不熟 悉公园，找个东西

15、，或某处带来了极大的不便。往往要花很多时间在这一方面。 然而要是有一个公园导游系统这将给乘客带来极大的方便，使人们一下就能了 解到这个公园的大致的情况。这是个超小型的性能分析系统，从投入的人力，财力与物力来讲是非常之 小的，只要一台电脑，一台打印机，这个系统就可以搞起来，考虑到学校里有 电脑，现只要购置一台打印机就可以了。从节省人力方面，可以让管理人员从 繁与复杂的工作中解脱出来，做更多的工作，可以给读者提高到更深的一个层 次。3.1.4 操作可行性本系统设计清晰，有良好的用户接口，操作简洁，完全可以给用户解决， 并达到操作过程中的直观、方便、实用、安全等要求，因此操作方面具有可行 性。3.2

16、 需求分析3.2.1 功能需求对于游客，系统功能需求如下：能够浏览整个公园的信息、查询每一个景 点的信息、从任意景点遍历全部的景点、能够查找最短路径。对于系统后台操作功能需求如下：删除地点、添加地点、添加路径、删除 路径、保存修改、导入文件数据。3.2.2 输入输出的要求程序执行是需要有描述地图的文件，并放在相应的位置。文件中开始位置 存放景点个数，图存在多少条边；接着是存放景点序号、名称、相关信息；对 后是存放着各个景点之间的距离矩阵。执行程序先要先要进行选择。修改地图是要验证密码。查找任意两个景点的最短路径时，输入查找最短路径的两个点。运行各个 小过程要求要输出的暂时的结果。四、使用说明与

17、执行结果4.1主界面1.用户,2 .游客八4.2游客界面。门我的文档'桌面'patk cuiderXDebucXpark puidEr. exs*公园导游系统跖有 佳地所 费雷的 44目有 园点利息相 公起点? 外一蓍一统循系 喜出 >!图4- 2游客界面4.3系统用户界面图4- 3系统用户登录界面图4- 4 系统用户界面4- 5涉外公园简图4- 6详细信息表4.5 浏览公园全景简图4.6 寻找某一起点的最佳路径和指定起点、终点的最短路径理工天堂一一北门一一汽车展览中心itII.应门炉心-IhfItr j二电基螂总二索斗应七中心一一汽车旅比中心弃展悦中心 尔过M呆甲心一

18、下 东| J len一A五夺展优于心丁>>wrr大I I I n*伴百卬心-塞门-?+& 弟拈懈忱怜*悻育中，心- 爱情感物忸 华天六旭庙 涉夕卜W 园 年赤女酒店一下涉外花国 午X大酒店 涉打廿网附外花园1-南门 A1T科愤本 巾帼纭念空- 哲科校本中心 ）袋惜 博物rt官- 体得 中心一冻黄情博恸馆- 巾 帼纪念 堂一 ，件飞 可平I"于玩术中?本景点描述弼浦慧彝研环曦里寓翡客i ，.岳,的暑篇普覆挝，ii雳，我小二百浦 W1B,体浦.量的口泡 1叫慎霜师新衣，籁也生提.你方曲T-需玉&瞿.第五源美.薰传.建发品展灯一,华天/湖上林外牝园-wgri-哲

19、74技术中，小一m帼 中心一 T存门-华天大酒店一涉外布园一方嬖ts四料t*-f rti帼纪J±dt一*科图4- 7查询最佳路径图4- 8查询最短路径,tic南门1An髀已依皆留?叱至希庙巧作 下力帼肥,二曳办“” 、Tl. .、件必衣国-餐厅汽车展览中心-5东门-唾工天崟-惜漏隔-静心涵-谪接任慈傩继族一一一4.7 寻找指定起点、终点的所有路径图4- 9输入两点之间的所有路径4.8 删除，添加结点，保存和导入新地图图4- 10删除结点图4-10 导入新的地图名 文 . 的 一 X : 巳F 卷 根由一=> 八fA狂附 录(程序清单)#include<stdio.h>

20、;#include<process.h>#define INT_MAX 10000#define n 10int costnn;/* 边的值 */int shortestnn;/* 两点间的最短距离 */ int pathnn;/* 经过的景点 */ void welcome。printf("n欢迎光临 n");printf("n凝香公园 nnnnn");printf("n给您最纯净的享受n");printf("nPure as the south polar snow nn");printf(&quo

21、t;n");system("pause");void Menu()函数的主显示界面system("cls");system("color 70");printf("i1n");printf("1凝香公园导游系统1 n");printf("11n");printf("n");printf(iin);printf("11 n");printf("11:浏览公园全景I n");printf("11 n&

22、quot;);printf("12：最佳游览路线| n");printf("主 11 n");printf("13:查看单个景点1 n");printf("菜 11 n");printf("14：游览线路查询| n");printf("单 11 n");printf("5:凝香公园简介n");printf("11 n");printf("I6:退出导游系统1 n");printf("11 n");

23、11print-n );printf("n");printf("n");printf("n");printf("nn >>>请按键选择:"）;)void Browser。(printf("n公园全景图n");nrin+ff"printT(n),printf("n");printf("1-紫金大道n");printf("1T 北 n");printf("1n");printf("1

24、沁园2公园大门1n");printf("111n");printf("111n");printf("3梨园4春园10夏园n");printf("11 11n");printf("11 11n");printf("5鼎湖| 8秋园9冬园n");printf("11 1n");printf("11 1n");printf("11 1n");printf("6聚缘阁7凝香园n");printf

25、("n");printf("n");printf("2012 年 7 月 4 日 n");printf("n");）void place（）（charz;printf（"nnn 【公园简介】 n"）;printf（"n n凝香园也称"正春园"，位于荷泽城东岳程办事处岳楼行政村。nn"）;printf（"始建于元末明初，原为袁姓所有，称"袁家堂"花园。 nn"）;printf（"凝香园是我国古代北方八大名园之

26、一，俗称“何家花园” ，距今有近1000余年的历史。nn"）;printf（"园中有百多年的刺柏、几百年的腊梅、紫丁香，千年翠兰松和一块假山石。nn"）;printf("“凝香园"附近的何应瑞墓地古柏成林，苍郁参天。nn");printf("n 注：本公园和真正的“凝香园”是同名，而非真实园林！n");printf("nn n");printf("nnn >>>>请输入任意字符【返回主菜单 n");z=getchar();z=getchar();)vo

27、id go()(printf("nnnnnn感谢使用1n");printf("|I n");printf("|I n");printf("|I n");printf("|请按任意键退出！I n"); printf("|I n");printf("|I n");printf("|程序制作：陈明 I n"); printf("|学号：3100931036 | n");printf("11 nnnnnn"

28、;);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");n")；printf（"如需其他路线请返回主菜单进入【浏览路线查询】printf（"nn n"）；printf("nnn >&g

29、t;>>请输入任意字符【返回主菜单n");z=getchar();z=getchar();void introduce。/*景点介绍*/ int a;char z;printf（">>>请输入您想查询的景点编号："）;scanf("%d",&a);getchar();printf("nn查询结果：n'n");switch(a)case 1:printf（" 1:沁园nn 一首沁园春.雪让您对眼前的梅花感慨万千。n"）;break;case 2:printf（&

30、quot; 2:公园大门nn仿古的气势宏伟建筑仿佛置身于100年前。n"）;break;case 3:printf(" 3:梨园 nncase 4:printf(" 4:春园 nncase 5:printf(" 5:鼎湖 nncase 6:丛林间嬉戏的小鸟不禁让你回头倾听。n"）;break;广阔的草地伴着阵阵花香，躺在上面可以仰望南天。n"）;break;圆滑的湖面仿佛一面大鼎将湖水撑起来。n"）;break;printf（" 6:聚缘阁nn来自大江南北的古玩古画齐聚一堂。n"）;break;case

31、7:printf（" 7:凝香园nn神奇的南方小筑隐匿在桂花林中。聚香也。n"）;break;printf(" 8:秋园 nn n");break;case 9:printf(" 9:冬园 nncase 10:printf(" 10:夏园 nncase 8:当你独自一人行走在大片阔叶林里，才能感受自然的气息。冬日恋歌在这里尽情唱响，High起来吧！ n"）;break;荷花池中一抹红，荷塘月色任你赏！n"）;break;default:printf（" Error：景点编号输入错误！请输入 110的数字编

32、号！nn"）;break;printf(" 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<=n;i+)if(shortestij>(shortestik+shortestkj)/*用path川记录从i到j的最短路径上点j的前驱景点的序号*/shortestij=shortestik+shor

33、testkj;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(i<j)printf(" %d",b);while(pathij!=0)/*把i至ij j的路径上所有经过的景点按逆序打印出来*/printf(" 一 %d",pathij);if(i<j) j=pathij;e

34、lse i=pathji;)printf(" 一 %d",a); printf("nn");printf("距离：您需要步行 %dm才能到达目的地！ ",shortestab);) else printf("%d",a);while(pathij!=0)/*把i至ij j的路径上所有经过的景点按顺序打印出来*/printf(" 一 %d",pathij);if(i<j) j=pathij;else i=pathji;)printf(" 一 %d",b); printf(

35、"nn");printf("距离：您需要步行%dm才能到达目的地！ nn",shortestab);printf("n'n");)elseprintf("输入错误！不存在此路！nn"); printf("n");printf("n'n");)int shortestdistance()/*要查找的两景点的最短距离*/int i,j;charz;printf(">>>请输入要查询的两个景点的编号(用空格键隔开):");sca

36、nf("%d %d",&i,&j);if(i>n|i<=0|j>n|j<0)printf("输入信息错误！nn");printf(">>>请输入要查询的两个景点的编号(用空格键隔开):");scanf("%d %d",&i,&j);)elsefloyed(); display(i,j);)printf(" >>>>请输入任意字符【返回主菜单n");z=getchar();z=getchar();re

37、turn 1;void main()/*主函数*/system("color 8巧;界面背景颜色system("mode con: cols=100 lines=15");/ 界面长度及宽度welcome。；system("mode con: cols=100 lines=40");int i,j; char k,z;for(i=0;i<=n;i+)for(j=0;j<=n;j+)costij=INT_MAX;cost12=cost21=12;cost13=cost31=38;cost34=cost43=32;cost24=cost42=21;cost210=cost102=36;cost35=cost53=28;cost56=cost65=29;cost67=cost76=40;cost109=cost910=18;cost410=cost104=30;cost47=cost74=22;cost78=cost87=12;co