公园导游管理方案系统

A计算机信息工程学院数据结构课程设计报告题 目公园导游系统_专 业：计算机科学与技术（软件方向）_班 级：_学 号：_姓 名：_指导教师：_完成日期：_A1.1程序模块.1.2系统涉及的数据结构1.2.1程序数据结构1.2.2具体数据类型定义2.1创建图(FPRINTLINK). 82.2寻找最佳路径(DFSMAVERS). 82.3最短路径(SHORPATH. 92.4遍历出某一起点到终点的所有路径(SEARCALLPATH). 112.5导入新文件(LOADNEWMAP. 12三、 测试分析.123.1可行性分析 .123.1.1技术可行性.133.1.2工具可行性.133.1.3经济可行性.133.1.4操作可行性.143.2需求分析.143.2.1功能需求.143.2.2输入输出的要求.14四、使用说明与执行结果 .1.44.1主界面.144.2游客界面.154.3系统用户界面 .15、概要设计1题目的内容与要求.4.、详细设计.8.4错误!未定义书签。56A附录(程序清单).1.AA、概要设计1.题目的内容与要求1.1 课题的研究背景、要求和意义现代公园范围的广阔，内容不断的增加，使得公园整个系统变得复杂。使 用电脑对游客进行导游成为发展的趋势，以达到更好的为游客服务的目的。对于公园的游客来说，他们要求：能够浏览整个公园的信息、查询每一个 景点的信息、从任意景点遍历全部的景点、能够查找最短路径。对于系统用户 来说，他们要求：删除地点、添加地点、添加路径、删除路径、保存修改、导 入文件数据。采用图这么一种数据结构，采用邻接表的存储方式，用一个二维数组来记 录所有的边，为了实现地图的随时更新，采用了静态链表实现对图的接点的添 加，删除。应用文件的读写来进行文件操作。查找最短路径采用迪杰特斯拉算法实现，从任意景点遍历全部的景点采用 深度优先遍历实现。对于界面设计，游客不能进行地图的修改，更换，所以首先要验证身份， 再出现对应的界面。2总体设计程序模块从文件中对出数据(Fprint-Link():通过调用Update(L,g),先将链表L的信 息赋值给邻接数组g中，进行更新。建立无向图，把公园的景点及景点的信息， 连接起来建立邻接表采用链式加顺式存储。浏览学校的全景(Browser)：列出学校的所有的景点。寻找最佳路径(DFSTraverse):输入一个景点，会吧所有都浏览一边，并 找出最佳的路径。最短路径(ShortPath :求出起点和终点的最佳路径，并求出最佳路径的长 度。遍历出某一起点到终点的所有路径(SearchAIIPath):找出所有路径，利用 深度优先遍历删除地点、添加地点、添加路径、删除路径、保存修改、导入文件数据。对应代码函数如下：DeleteAdv(L,g)、InsertAdv(L,g)、InsertEdge() DeleteEdge()SaveMap(g) Loadnewmap(p,g)bA总体结构设计如图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线性链表的抽象数据类型：AADT List数据对象：D=ai|aiElemSe,i=1,2,，n,n0 数据关系：R1=|ai-1,aiD,i=2,n 基本操作：DeleteAdv(L,g)InsertAdv(L,g)In sertEdge()DeleteEdge()SaveMap(g)Load newmap(p,g) ADT List o3.2.2具体数据类型定义typedef struct LNodechar n ame30;int num;char in troductio n100;struct LNode *n ext;LNode,*Li nk;typedef struct ArcNodei nt data;该弧所得指向的顶点的位置ArcNode *n extarc;指向下一条弧的指针ArcNode,*ArcLi nk;typedef struct VNode顶点信息 char n ame30;int num;char in troductio n100;ArcLi nk firstarc; /指向第一条依附该顶点的弧的指针VNode,AdjListMAX+1;typedef struct ALGraphAdjList vdata;int vexnum,arcnum;图的顶点数和弧数ALGraph;int EdgeMAXMAX;/用来存放路径的权值int n, e;存放结点数和边数读取文件信息代码如下：for(i=1;i=n ;i+)fsca nf(fp,%d,&nu m);fsca nf(fp,%s ,n ame);fsca nf(fp,%s,i nformatio n);AList In sert(L, num, n ame, in formati on);Update(L,g);for ( j=1;jdata=a;p-n extarc=gb.firstarc;gb.firstarc=p;/把p插进来q=(ArcL in k)malloc(sizeof(ArcNode); q-data=b;q-n extarc=ga.firstarc;ga.firstarc=q;A、详细设计2.1 创建图(Fprint-Link)从文件中读出数据，函数流程图2-1所示图 2- 1 Fprint-Link函数流程图2.2 寻找最佳路径(DFSTraverse利用深度优先的思想，遍历图找出一条最佳最佳的的路径，让它遍历所有A景点。利用递归的思想，往下遍历，访问标志位，若访问过在下次就不用访问 若找完一个分支在下次重新遍历，函数流程如图2-2所示。图 2- 2 寻找最佳路径流程图2.3 最短路径（ShortPath利用迪杰特斯拉算法，求v0到其余顶点的最短路径path,distanee 是用来 存放各路径的权值，借助辅助数组s标志，是否当前顶点属于S（1属于）函数流 程图2-3所示。A开始初始化distence, s,path开始主循环，每次求得vO到某顶点v的最短距离，并将v并入中minDis=MAXEDGE;当前所知vO的最短距离并设初值为MAXEAGE，j=0;更新当前最短路径及距离；n ewDist=distanfceu+GetWeightu图 2- 3 寻找最短路径流程图!sj&distancejv=nNu=j；在s下一直往下找A2.4 遍历出某一起点到终点的所有路径(SearchAIIPath)利用图的深度优先遍历，利用访问标志位。path记录路径，visited设访问标志，v起点，des终点，length，代表的是访问景点的长度。若碰见死 路或者不同的路，则从上一个景点，从新扫描，SearchAIIPath(流程如图2-4所 示。图2- 4 searchAIIPath()流程图A2.5 导入新文件(Loadnewma)将指定文件导入到邻接表中，再保存到zheke1.txt中 具体实现如图2-5所示。初始化Link p ， 输入文件名filename20-Fpri nt-L ink(p，g，file name)SaveMap(g)L=P;图 2- 5 导入新文件结构示图三、测试分析3.1 可行性分析所谓可行性分析就是用最小的代价在尽可能短的时间内确定问题是否能够 解决。 这步工作的主要是要进行一次大大压缩简化了的系统分析和设计的过程, 也就是在较高层次上以比较抽象的方式进行系统分析和设计的过程。可行性研 究的最根本任务是对以后的行动方针提出建议，以避免时间、资源、人力和金 钱的浪费，推荐一个较好的解决方案，并且为工程制定一个初步的计划。3.1.1技术可行性查找最短路径以及查询任意两景点之间的所有路径采用迪杰特斯拉算法或 弗洛伊A德算法实现。解决这个问题的一个方法是：每次以一个顶点为源点，重 复执行迪杰斯特拉算法n次。这样，便可求得每一对顶点之间的最短路径。总 的执行时间为0(n3)。虽然弗洛伊德算法时间复杂度也是O(n3)，但形式简 单些。从任意景点遍历全部的景点采用深度优先遍历或广度优先搜索遍历图实现。所谓可行性分析就是用最小的代价在尽可能短的时间内确定问题是否能够 解决。这步工作的主要是要进行一次大大压缩简化了的系统分析和设计的过程， 也就是在较高层次上以比较抽象的方式进行系统分析和设计的过程。可行性研 究的最根本任务是对以后的行动方针提出建议，以避免时间、资源、人力和金 钱的浪费，推荐一个较好的解决方案，并且为工程制定一个初步的计划。本系统采用人机操作进行管理，用visual C+ 6.0进行前台设计、系统随机 产生数据，用户通过界面操作，系统自动给予合理分析，由于visual C+ 6.0功能强大、使用的灵活、良好的可扩展性、以及广泛实际应用，充分说明本系 统在技术方面的可行性。3.1.2工具可行性软件方面：信息时代对于软件的应用已不是人们的难题，人们在日常办公中用的计算 机操作的系统等都属于软件部分。硬件方面：计算机普及到今天，人们对于它的拥有已不少见，它的硬件设备完全能够 满足人们的需求，而价格也能被人们所接受。3.1.3经济可行性线在大多数的公园景点及内容不断的增多和丰富，这也就使得整个公园系 统不得不建立的更大。这也就为人们逛公园造成了很大的不便。人们往往不熟 悉公园，找个东西，或某处带来了极大的不便。往往要花很多时间在这一方面。 然而要是有一个公园导游系统这将给乘客带来极大的方便，使人们一下就能了 解到这个公园的大致的情况。这是个超小型的性能分析系统，从投入的人力，财力与物力来讲是非常之 小的，只要一台电脑，一台打印机，这个系统就可以搞起来，考虑到学校里有 电脑，现只要购置一台打印机就可以了。从节省人力方面，可以让管理人员从 繁与复杂的工作中解脱出来，做更多的工作，可以给读者提高到更深的一个层 次。3.1.4操作可行性本系统设计清晰，有良好的用户接口，操作简洁，完全可以给用户解决， 并达到操作过程中的直观、方便、实用、安全等要求，因此操作方面具有可行 性。A3.2 需求分析3.2.1功能需求对于游客，系统功能需求如下：能够浏览整个公园的信息、查询每一个景 点的信息、从任意景点遍历全部的景点、能够查找最短路径。对于系统后台操作功能需求如下：删除地点、添加地点、添加路径、删除 路径、保存修改、导入文件数据。3.2.2输入输出的要求程序执行是需要有描述地图的文件，并放在相应的位置。文件中开始位置 存放景点个数，图存在多少条边；接着是存放景点序号、名称、相关信息；对 后是存放着各个景点之间的距离矩阵。执行程序先要先要进行选择。修改地图是要验证密码。查找任意两个景点的最短路径时，输入查找最短路径的两个点。运行各个 小过程要求要输出的暂时的结果。四、使用说明与执行结果4.1 主界面曲户詐游客） :帕血In图4- 1主界面A4.2 游客界面- d：、我的文档桌面patk cuiderXDebucXpark puidEr. exs*公园导游系统*图4- 4系统用户界面4.5 浏览公园全景简图4- 5涉外公园简图囲有1所旦專的曲全凶目点园点和息記公起点集外一香一统喬岀- =H图4- 2游客界面4.3 系统用户界面图4- 3系统用户登录界面Z 己=%我的龙也点帀研p包直k ：11derXDBbug：park障u五dexr xe険改地圉模壊*XX仇-MHM1H XXK IM 币|=作輛舟鬥那反.总更工7锂工若堂nWfr阴二舞勰総芒Lit # 3. |门A|IU J-汽辛JM忧中心 為I 1-AItl 1-A 汽辛展饶申心. 41 j珂弋辛展吃帀心A 樽门ill L厂亠亠-槽斤筱 II啓白 中吃nuw+&克怙协斷惊育中心一爱寓 輝物馆 华天K?tt JEA沖夕卜花 圉作丟*酒店一-涉夕卜花国普天涉詞in岡刑夕I花01- 南11 - A1T利帙卡， 巾*即己念 堂 哉悄同幽t自、帯悄苗椚节自1门-哲科A 哲科检术中心-訂本商中.呑-7E屮習圮总:堂一1- -J Jr-p J- 3螯黄宮育F-蚩壬去Ly- f,J1J1.1J - d- 垂二中三nBUHrn -n/ ” I n - - - -华禾人河丿上桝卜花西 中心-卜耳门申门哲科上克术中心r|JP节.jrujx时.町陀匕r.i* injr.Mv门mu：-二二空.LJ-t-l4t卜Anw JF巾f A-二-丄替誉辆.5 1.le-l- i- I图4- 7查询最佳路径 图4- 8查询最短路径- -函门-A涉 外花网 7 华天 大酒JS4.7 寻找指定起点、终点的所有路径n*-n *三牡掠杭羽恭縫逐舉严逢舟 Ji 疗毀烈即幅從芾耶AF崔r r皆MJHr!I J ./,工AAA?卫卫鼻nnrH电罟w“.H盲峠i J X.SIH E-三三二I7sQ8RriAA图4- 9输入两点之间的所有路径4.8 删除，添加结点，保存和导入新地图图4- 10删除结点导入新的地图图4-10已 F践球申工二 3zfA在弩#罗A附 录(程序清单)#in clude#in clude#defi ne INT_MAX 10000#defi ne n 10int costnn;/* 边的值 */int shortestnn;/*两点间的最短距离 */int pathnn;/*经过的景点 */void welcome。prin tf(n system(pause);void Menu()函数的主显示界面system(cls);system(color 70);printf(”11n);printf(”1凝香公园导游系统1n);printf(”1n);printf(”n);printT(1in );printf(”1printf(”11:浏览公园全景1printf(”11printf(”12:最佳游览路线1printf(”主11printf(”13:查看单个景点1printf(”菜11prin tf(n prin tf(n prin tf(n欢迎光临n);凝香公园nnnnn);给您最纯净的享受n);printf(nPure as the south polar snow nn););Aprintf(”14:游览线路查询1printf(”单11printf(”5:凝香公园简介1printf(”11Aprintf(”printf(”printf(”printf(”printf(”printf(”printf(nn 请按键选择：”); void place（）char 乙printf（nnn - 【公园简介】 -n ”）；6:退出导游系统In);In);-1n);n);n);n);void Browser。prin tf(n printf( printf(”printf(” printf(”printf(” printf(”printf(” printf(”printf(” printf(”printf(” printf(”printf(” printf(”printf(” printf(”printf(” printf(”printf(”prin tf( 1 沁园一II3 梨园一II5 鼎湖III6 聚缘阁公园全景图 n);n);III2 公园大门II-4 春IIIIII园II8 秋园,III-7 凝香园紫金大道II10 夏园II9 冬园n);n);n ”)；n ”)；f北n ”);n);n ”)；n);n);n);n);n);n);n);n);n);n);2012 年 7 月 4 日 n”);- n);Aprin tf（n n 凝香园也称正春园”，位于荷泽城东岳程办事处岳楼行政村。nn）;printf（始建于元末明初，原为袁姓所有，称“袁家堂”花园。nn）;printf（ 凝香园是我国古代北方八大名园之一，俗称“何家花园”，距今有近 1000 余年的历史。nn）;printf（园中有百多年的刺柏、几百年的腊梅、紫丁香，千年翠兰松和一块假山石。nn”）;printf(”凝香园附近的何应瑞墓地古柏成林，仓郁参天。nn);prin tf(n 注：本公园和真正的“凝香园”是同名，而非真实园林！n);printf(nn -n);printf(nnn 请输入任意字符【返回主菜单】 n); z=getchar();z=getchar();void go()prin tf(nnnnnni- 感谢使用-in );printf(|1n);printf(|1n);printf(|1n);prin tf(|请按任意键退出！1n);printf(|1n);printf(|1n);prin tf(|程序制作：陈明 | n);prin tf(|学号：3100931036|n);printf(1-Jnnnnnn);exit(0);void way()char z;printf(n-n);Aprintf(”本公园的最佳全景游览路线为：nn);printf(2 公园大门宀 1 沁园宀 3 梨园宀 5 鼎湖宀 6 聚缘阁宀 7 凝香园宀 4 春园宀 8秋园T9 冬园T10 夏园T2 公园大门n);printf(全程所需行程：276 米!nn”)；Aprin tf(”如需其他路线请返回主菜单进入【浏览路线查询】n);printf(nn -n )；printf(nnn 请输入任意字符【返回主菜单】n);z=getchar();z=getchar(); void in troduce()/*景点介绍*/ int a;char z;printf(请输入您想查询的景点编号：”);sca nf(%d,&a);nn);switch(a)case 1:printf( 1:沁园nn 首沁园春.雪让您对眼前的梅花感慨万千。n);break;case 2:printf(” 2:公园大门nn 仿古的气势宏伟建筑仿佛置身于100 年前。n”);break;case 3:丛林间嬉戏的小鸟不禁让你回头倾听。n);break;广阔的草地伴着阵阵花香，躺在上面可以仰望南天。n);break;圆滑的湖面仿佛一面大鼎将湖水撑起来。n ”);break;来自大江南北的古玩古画齐聚一堂。n);break;神奇的南方小筑隐匿在桂花林中。聚香也。n ”);break;当你独自一人行走在大片阔叶林里，才能感受自然的气息。冬日恋歌在这里尽情唱响，High 起来吧！ n);break;荷花池中一抹红，荷塘月色任你赏！n );break;default:printf( Error:景点编号输入错误！请输入 110 的数字编号！nn);break;getchar();printf(nn查询结果：】-printf(” 3:梨园 nncase 4:printf(” 4:春园 nncase 5:printf(” 5:鼎湖 nncase 6:printf(” 6:聚缘阁 nncase 7:printf(” 7:凝香园 nncase 8:printf(8:秋园 nnn);break;case 9:printf( 9:冬园 nncase 10:printf( 10:夏园 nnAprintf(”void floyed()/*用 floyed 算法求两个景点的最短路径*/int i,j,k;for(i=1;i=n ;i+)for(j=1;j=n ;j+) shortestij=costij;pathij=O;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(i nt i,i nt j)/*打印两个景点的路径及最短距离*/int a,b;a=i; b=j;printf(n -【查询结果：】 -printf(路径:);if(shortestij!=INT_MAX)if(ij)printf( %d,b);while(pathij!=0)/*把 i 至打的路径上所有经过的景点按逆序打印出来*/prin tf( %d,pathij);if(ij) j=pathij;else i=pathji;prin tf( %d,a);prin tf(nn);Aprintf(距离：您需要步行%dm 才能到达目的地！ ,shortestab);nn);nn);A elseprin tf(%d,a);while(pathij!=O)/*把 i 到 j 的路径上所有经过的景点按顺序打印出来*/printf(”T%d,pathij);if(i请输入要查询的两个景点的编号sca nf(%d %d,&i,&j);if(i n|i n| |j请输入要查询的两个景点的编号sca nf(%d %d,&i,&j);elsefloyed(); display(i,j);printf( 请输入任意字符【返回主菜单】（用空格键隔开）:）;（用空格键隔开）:）;n);Avoid mai n()/*主函数*/system(color 8f); 界面背景颜色system(mode con: cols=100 lines=15);/ 界面长度及宽度 welcome();system(mode con: cols=100 lin es=40);int i,j; char k,z;for(i=0;i=n ;i+)for(j=0;j请输入任意字符【返回主菜单】n);z=getchar();z=getchar();Me nu();break;case 2:system(cls);system(color f2);Browser();printf(n【最佳游览路线way();break;case 3:system(cls);system(color f2); Browser();printf(n【查看单个景点】nn);】nn);Ain troduce();printf(nnn 请输入任意字符【返回主菜单】n);z=getchar(); break;case 4:system(cls);system(color f2); Browser。;printf(n【游览线路查询】nn);shortestdista nce(); break;case 5:system(cls);system(color f2);place();Me nu();break;case 6:system(cls);system(color f2);go();default: printf(”-nn);printf(Error :输入错误，请您核对后重新输入！n);printf(n -nn);system(pause);break;课程设计总结：这次课程设计让我学到了很多，课程设计开始之前，我看了别做的系统，认 真的分析了别人的代码，当我弄懂了迪杰特斯拉算法和弗洛伊德算法时，我就开 始编写自己的系统。我想再添加一些新的功能，但是这两周下来我当然也感到累，也有心情烦躁的时候，体会到调试成功使的那种喜悦。A指导教师评语：指导教师（签字）:年 月日课程设计成绩A