课程设计校园导航查询系统.doc

课 程 设 计课程名称 ： 数据结构应用题目名称 ： 校园导航查询系统学生学院 ： 计算机科学与教育技术学院专业班级 ：计算机科学与技术-2班学 号 ：200624101067学生姓名 ： 王导指导教师 ： 张学平2008 年 5 月 8 日摘 要本文论述的校园导航查询系统是为校园参观者或导游者提供的一种便捷的交通查询系统，该系统主要解决了校园参观者或导游者在进行采访或参观时所遇到的校园路径方向问题，为此，设计该系统能够给带来他们一种比较方便快捷的导航帮助。本文论述了校园导航查询系统开发的目标和实现的功能，并重点介绍了系统分析、系统设计、系统测试和系统实施的全过程。在描述系统分析和系统设计过程中，为了使该系统的开发过程具有规范化，为此，本文确定了开发系统的指导思想：一、运用了规范化的设计思想。二、从实际应用出发，为求实用。三、运用数据结构里所涉及到的算法思想进行设计开发，开发一个适宜查询学校的相关信以及校园场所和景点之间的最短路径的方向导航系统。本文分为四章编写：第一章： 是系统分析，系统分析是对系统的现状进行分析。根据系统的目标、需求分析和功能分析，制定和选择一个较好的系统方案，从而达到一个合理的优化系统。第二章： 是程序设计和结构创建，程序设计的全过程，可以相应地分成三个阶段：第一个阶段：为程序需求分析阶段第二个阶段：为建立概念性数据模型第三个阶段：为逻辑设计阶段第三章： 是系统设计，系统设计的目的是最大限度地运用系统分析的结果，设计出能最大限度地满足要求的系统。第四章是系统测试和系统运行，系统测试的目的是为了找出错误，修正错误，使系统真正达到要求。目 录 概述.4一.系统分析.51.1 问题描述.51.2 导航流程分析.61.3 信息需求分析.61.4 系统功能分析.7二.系统设计.72.1 设计思路.8 2.2输入输出分析.82.3 概要设计.92.4 模块概要设计.,.10 2.5详细设计.122.6 各个算法功能设计.142.7算法调用关系模型.162.8算法详细分析.16三.调试分析.253.3调试问题.253.1成员讨论.283.4所作修改.33四用户使用说明.34五. 测试结果.35六结论.39 七参考文献.37 八致谢.38概 述数据结构是计算机程序设计的重要理论技术基础，它不仅是计算机科学的核心课程，而且已成为其他理工专业的热门选修课。从课程性质上讲，数据结构是一门专业技术基础课。它的教学要求是：学会分析研究计算机加工的数据结构的特性，以便为应用涉及的数据选择适当的逻辑结构，存储结构及其相应的算法，并初步掌握算法的时间分析和空间分析的技术。另一方面，本课程的学习过程也是复杂程序设计的训练过程，要求编写的程序结构清楚和正确意读，符合软件工程的规范。高级语言程序设计的训练过程，结构化程序设计的训练，程序语言的综合运用。数据结构主要培养我们的数据抽象能力。本次设计其实就是数据结构中图类的问题。将校园景点作为图的结点，将景点间的路径作为图的边，路径距离作为边的权值。这样一来，求两景点间最短路径的问题就抽象成了求图中一结点到另一结点的问题。这也是计算机代替人工的一个实例，也是软件工程必不可少的基础。以下是针对本次校园导航系统所做的一些陈述：校园导航查询系统是典型的校园导游查询系统,其设计主要根据学校的各个景点和场所所设计的导航系统。本系统是一个涉及海南师范大学相关景点和场所查询系统,是为了方便人们能够更快更准地获得学校各个景点和场所的详细信息。本系统为用户提供以下功能:(一)、查询了解学校概况，为导游参观者提供关于学校的相关 信息。(二)、查询校园各个场所和景点信息;(三)、为导游者或外来人员参观人员提供校园交通信息，方便用户走访学校。校园导航查询系统的开发方法总结如下：(1) 调查，了解学校各个场所与 场所或者是各个景点与景点之间的信息，路径和距离，从外来人员或者参观者和走访者的角度出发，该如何设计才能满足用户需求。(2) 分析，对调查得到的数据进行分析，根据其要求实现的功能分析系统结构和界面将实现的基本功能。(3) 设计与开发，设计系统界面并编辑实现其各个功能的代码。(4) 调试，在设计完成后，调试系统运行的状况，修改完善系统,然后进行测试。一. 系统分析1.1 问题描述：设计一个校园导游程序，为来访的客人提供各种信息查询服务。 (1)设计学校的校园平面图，所含景点不少于10个。以图中顶点表示校内各景点，存 放景点名称、代号、间介等信息；以边表示路径，存放路径长度等相关信息。 (2)为来访客人提供图中任意景点相关信息的查询。 (3)提供途中任意景点问路查询，即求任意两个景点间的一条最短的简单路径。1.2 导航流程分析：根据海南师范大学的各个场所和景点设计导航系统，该 系统的 建立方便用户了解海南师范大学里的各个场所的和景点以及学校的一些相关信息，通过该系统，用户不但可以有选择性地对学校的景点和场所进行走访和参观，还可以查询了解学校各种不同的具体路线，更重要的是通过该系统可以让用户迷路情况下找到校园出口。1.3 信息需求分析：列出学校里的各个场所和各个景点以及各个场所和景点所 对应的相关信息列举如下：学校简介输入学校的一些相关信息海师大门输入相关信息实验楼输入相关信息田家丙输入相关信息椰林广场输入相关信息榕树下输入相关信息图书馆输入相关信息体育馆输入相关信息二食堂输入相关信息十三栋输入相关信息海师后门输入相关信息1.4 系统功能分析：(1). 查询学校概况简介(2). 学校各个景点和场所信息查询(3). 学校路径查询(4). 导游最短路径查询(5). 学校各个景点和场所之间的距离查询 其功能如下图所示：二.系统设计：2.1 设计思路：校园旅游模型是由各个景点和景点以及场所和场所之间的路径组成的，所以这完全可以用数据结构中的图来模拟。用图的结点代表景点或场所，用图的边代表景点或场所之间的路径。所以首先应创建图的存储结构。结点值代表景点信息，边的权值代表景点间的距离。结点值及边的权值采用图存储。本系统需要查询景点信息和求一个景点到另一个景点的最短路径长度及路线，为方便操作，所以给每个景点一个代码，用结构体类型实现。计算路径长度，最短路线和最佳路径时可分别用狄克斯特拉（Dijkastra）算法和哈密而顿回路算法实现。最后用switch选择语句选择执行浏览景点信息或查询最短路径和距离。2.2输入输出分析：输入系统里指定的相关操作（1）输出学校概况简介；（2） 输出景点和场所信息：将校园内各位置输出。（3）输出边的信息：将校园内每两个位置（若两个位置之间有直接路径）的距离输出。（4）输出走访学校的各景点和场所的最佳路径。（5） 求最短路径：输出给定两点之间的最短路径的长度及途经的地点或输出任意一点与其他各点的最短路径。2.3 概要设计1 程序设计三步曲：第一步：搭建程序框架图其图如下所示：第二步:设计功能的实现接下来根据以上搭建的程序框架完成各个模块的算法1 首先是抽象数据类型的定义：图的抽象数据类型的 定义：ADT Mgragh数据对象V: V是具有相同特征的数据元素的 集合，称为定点集数据关系R=VRVR= | V, WV, 表示从V到W的边 2. 基本操作：CreateUDN(&G,V,VR); / 创建图初始条件：V是图的顶点集，VR是图中边的 集合。操作结果：按V和VR的定义构造图 G。第三步：主要算法设计及相关算法补充先创建图存储学校各个景点或场所，以图的顶点表示景点或场所，以边表示路径，再利用迪杰斯特拉（DijkStra）算法求出校园各个地方的最短路径，然后根据需要进行补充相关算法。2.4 模块概要设计本程序包含三大模块：第一模块是主程序模块，即Main()函数主程序模块：void main() / 主函数 CreateUDN(NUM,11); /调用造图函数 do ck=Menu(); switch(ck) case1: introduce();break; /介绍景点信息case 2: ShortestPath(v0); / 计算两个景点之间的最短路径 output(v0,v1); / 输出结果 break;case 3:search(); break; case 4: HaMiTonian(1); break;case5: PrintMGraph(); while(ck!=e);第二模块主菜单和子菜单模块：1.主菜单模块：char Menu() / 主菜单 / char c; int flag; do if(c=1|c=2|c=3|c=4|c=5|c=e) flag=0; while(flag);2.子菜单模块：char SearchMenu() / 查询子菜单 char c; int flag; do flag=1;scanf(%c,&c); if(c=1|c=2|c=e) flag=0; while(flag); return c;第三模块：函数调用1. 主菜单模块里所包含的函数调用：void CreateUDN(int v,int a); / 创建图的函数void search()void pingmu(); /屏幕输出函数void introduce();介绍景点的函数void output(int sight1,int sight2); /输出最短路径的函数void PrintMGraph();打印各个地方，查看地方之间的距离2. 子菜单所包含函数调用模块：void introduce();介绍景点的函数void ShortestPath(int num); /最短距离函数void HaMiTonian(int); / 哈密尔顿图的遍历 ，输出最佳参观路线void NextValue(int); void display(); / 显示校园路径结果其主要模块关系图如下图所示：2.菜单模块Menu()（选择所设数字，输出相应结果）char SearchMenu();（2）子菜单char Menu();（1）主菜单1.主程序模块Main()函数void CreateUDN(int v,int a); / 创建图的函数void search()void pingmu(); /屏幕输出函数void introduce();介绍景点的函数void PrintMGraph();打印各个地方，查看地方之间的距离void introduce();介绍景点的函数void ShortestPath(int num); /最短距离函数void output(int sight1,int sight2); /输出最短路径的函数void HaMiTonian(int); / 哈密尔顿图的遍历 ，输出最佳参观路线void NextValue(int); void display(); / 显示校园路径结果3.主菜单所调用的函数算法模块3.子菜单所调用的函数算法模块2.5 详细设计1. 建立关于学校景点和场所的图的存储结构首先定义图的数据类型：typedef struct ArcCell int adj; / 相邻接的景点之间的路程 char *info;ArcCell; / 定义边的类型 typedef struct VertexType int number; / 景点编号 char *sight; / 景点名称 char *description; / 景点描述 VertexType; / 定义顶点的类型 typedef struct VertexType vexNUM; / 图中的顶点，即为景点 ArcCell arcsNUMNUM; / 图中的边，即为景点间的距离 int vexnum,arcnum; / 顶点数，边数 MGraph; / 定义图的类型 MGraph G; / 把图定义为全局变量2.各个算法的实现：（1） void CreateUDN(int v,int a); / 创建图的函数 （2） void pingmu(); /屏幕输出函数（3） void introduce();/景点和场所介绍函数（4） void ShortestPath(int num); /最短路径函数（5） void output(int sight1,int sight2); /输出详细路线函数（6） void PrintMGraph();打印邻接矩阵（7） void search(); ;/ 查询景点信息（8） void HaMiTonian(int); / 哈密尔顿图的遍历 （9） void NextValue(int); （10） void display(); / 显示遍历结果 2.6各个算法功能设计2.7算法调用关系模型2.8主要算法详细分析1. 用无向网表示学校的校园景点平面图，图中顶点表示主要景点，存放景点的编号、名称、简介等信息，图中的边表示景点间的道路，存放路径长度等信息。即 V:-景点 A-边数，0，1，2，3，4，5，6，7，8，9，10表示各个景点的编号通过输入该编号即可查找到所代表的景点。void CreateUDN(int v,int a) / 创建图的函数 int i,j; G.vexnum=v; / 初始化结构中的景点数和边数 G.arcnum=a; for(i=1;iG.vexnum;+i) G.vexi.number=i; / 初始化每一个景点的编号 / 初始化没一个景点名及其景点描述 G.vex0.sight=学校简介; G.vex1.sight=校大门; G.vex2.sight=实验楼; G.vex3.sight=田家丙; G.vex4.sight=椰林场; G.vex5.sight=榕树下; G.vex6.sight=图书馆; G.vex7.sight=体育馆; G.vex8.sight=二食堂;G.vex9.sight=十三栋;G.vex10.sight=大后门; / 这里把所有的边假定为20000，含义是这两个景点之间是不可到达 for(i=1;iG.vexnum;+i) for(j=1;jG.vexnum;+j) G.arcsij.adj=Max;G.=NULL; /下边是可直接到达的景点间的距离，由于两个景点间距离是互相的， / 所以要对图中对称的边同时赋值。 G.arcs14.adj=G.arcs41.adj=200; G.arcs13.adj=G.arcs31.adj=500; G.arcs35.adj=G.arcs53.adj=100; G.arcs310.adj=G.arcs103.adj=400; G.arcs46.adj=G.arcs64.adj=200; G.arcs25.adj=G.arcs52.adj=200; G.arcs24.adj=G.arcs42.adj=300; G.arcs57.adj=G.arcs75.adj=500; G.arcs46.adj=G.arcs64.adj=400; G.arcs47.adj=G.arcs74.adj=600; G.arcs68.adj=G.arcs86.adj=500; G.arcs78.adj=G.arcs87.adj=300; G.arcs69.adj=G.arcs96.adj=500;2. 迪杰斯特拉算法其算法思想如下：迪杰斯特拉（DijkStra）算法求最短路径的实现思想是：设图G=（V，A）其中，V=0，1，2，3n,COST是表示G的邻接矩阵, G.arcsij.adj的权为无穷大(这里取值为32767).设S是一个集合,其中的每个元素表示一个顶点,从源点到这些顶点的最短路径已经求出.设顶点V1为源点,集合S的初态只包含顶点V1.数组Dv记录从源点到其他各个场所顶点当前的最短距离,其初值为Dv=G.arcsnumv.adj,i=2,3,n.从S之外的顶点集合V-S中选出一个顶点w,使Dv的值最小.于是从原点到达w只通过S中的顶点,把w加入集合S中,调整dist中记录的从单原点到V-S中每个顶点v的距离:从原来的Dv和min+ G.arcsvw.adj中选择较小的值作为新的Dv.重复上述过程,直到S中包含V中其余顶点的最短路径.最终结果是:S记录了从原点到该顶点存在最短路径的顶点集合,数组Dv记录了从原点到V中其余各顶点之间的最短路径顶点,path最短路径的路径数组,其中pathi表示从原点到顶点i之间的最短路径的前驱顶点.因此, 迪杰斯特拉（DijkStra）算法可用简单语言描述如下:初始化S和D,置空最短路径终点集,置初始的最短路径值;SV1=TRUE; finalv=0; /S集合初始时候只有原点,原点到原点的距离为0;While(S集中顶点数 n) 开始循环,每次求得V1到某个V顶点的最短路径,并加V到S集合中;SV=TRUE;更新当前最短路径及距离;相应代码如下：void ShortestPath(int num) / 迪杰斯特拉算法最短路径函数 num为入口点的编号 int v,w,i,t; / i、w和v为计数变量 int finalNUM; int min; for(v=1;vNUM;v+) finalv=0; / 假设从顶点num到顶点v没有最短路径 Dv=G.arcsnumv.adj;/ 将与之相关的权值放入D中存放 for(w=1;wNUM;w+) / 设置为空路径 Pvw=0; if(Dv32767) / 存在路径 Pvnum=1; / 存在标志置为一 Pvv=1; / 自身到自身 Dnum=0; finalnum=1; / 初始化num顶点属于S集合 / 开始主循环，每一次求得num到某个顶点的最短路径，并将其加入到S集合 for(i=1;iNUM;+i) / 其余G.vexnum-1个顶点 min=Max; / 当前所知离顶点num的最近距离 for(w=1;wNUM;+w) if(!finalw) / w顶点在v-s中 if(Dwmin) / w顶点离num顶点更近 v=w; min=Dw; finalv=1; / 离num顶点更近的v加入到s集合 for(w=1;wNUM;+w) / 更新当前最短路径极其距离 if(!finalw&(min+G.arcsvw.adj)Dw)/ 不在s集合，并且比以前所找到的路径都短就更新当前路径 / Dw=min+G.arcsvw.adj; for(t=0;t8) return; L: NextValue(m); if(xm=0) return; if(m=7&G.arcs1x8-1.adj!=32767) display(); else HaMiTonian(m+1); goto L; void NextValue(int k) int j; l:xk=(xk+1)%10; if(xk=0) return; if(G.arcsxk-1-1xk-1.adj!=32767) for(j=0;jk;j+) if(xj=xk) goto l; return; else goto l; void display() int i=1; printf(nnt); for(i=1;i,G.vexxi-1.sight); printf(出口); printf(n); 4.打印邻接矩阵，该算法可方便用户查看校园景点与 景点之间的距离，这里说明一下为什么其他地方都 用printf语句输出而这里怯用cout语句输出；由于用printf输出的时候屏幕上显示的景点与景点之间的距离很乱，不对称，调来调去都 调不 好，所以本人只好用cout进行输出，因为cout对调整屏幕上的输出比较适用。void PrintMGraph()int i,j;coutn =nn ;for(i=1;iG.vexnum;+i)coutG.vexi.sight ;coutendl;for(i=1;iG.vexnum;+i)coutnnG.vexi.sight ;for(j=1;jG.vexnum;+j)if(G.arcsij.adj=Max)cout no ;elsecout G.arcsij.adj;coutnnnn=nnn;5. void output(int sight1,int sight2) / 输出函数 int a,b,c,d,q=0; a=sight2; / 将景点二赋值给a if(a!=sight1) / 如果景点二不和景点一输入重合，则进行. printf(nt从%s到%s的最短路径是,G.vexsight1.sight,G.vexsight2.sight);/ 输出提示信息 printf(t(最短距离为 %dm.)nnt,Da); / 输出sight1到sight2的最短路径长度，存放在D数组中 printf(t%s,G.vexsight1.sight); / 输出景点一的名称 d=sight1; / 将景点一的编号赋值给d for(c=0;cNUM;+c) gate:; / 标号，可以作为goto语句跳转的位置 Pasight1=0; for(b=0;bNUM;b+) if(G.arcsdb.adj%s,G.vexb.sight); / 输出此节点的名称 q=q+1; / 计数变量加一，满8控制输出时的换行 Pab=0; d=b; / 将b作为出发点进行下一次循环输出，如此反复 if(q%8=0) printf(n); goto gate; 5.介绍函数void introduce() / 介绍函数 int i; for(i=1;i=NUM;i+) G.vex0.description=海南师范大学座落在美丽的热带海滨城市nntt国家历史文化名城海口，校园椰风流韵、芳林叠翠、风景秀丽。nntt经过半个多世纪的发展,学校现已形成以教师教育为主要办学特色nntt教、文、管、理、经等多学科协调发展的格局,是海南省培养基础教育nntt师资和其他高级应用型人才的重要基地.目前，学校确立了立足海南nntt逐渐面向全国辐射东南亚的服务面向定位，充分发挥毗邻港澳nntt面向东南亚的人缘地缘优势，积极扩大对外交流与合作，学术交流日趋nntt频繁，国际影响不断增强nntt下面几点是海南师范大学的办学特色：nntt办学历史较为悠久nntt学科专业较为齐全nntt师资队伍素质优良nntt教学成果较为丰硕nntt科研水平不断提高nntt校园文化丰富活跃nntt人才培养成效显著nntt合作交流日趋频繁nntt; G.vex1.description=学校大门，对面是金鹏女生公寓，你要找美女ntt首先你得注意别被车撞飞了; G.vex2.description=计教系办公大楼，计算机科学技术的科研中心; G.vex3.description=教学大楼，不同的系都在这楼上课; G.vex4.description=在这破地方什么鸟人都 有，拿书呐喊的，失恋的，打KISS的，暗送秋波的，ntt可千万别来这鸳鸯之地，你来了，一个电灯泡亮那儿ntt你说人家两口子咋亲热啊，还是闪为上策; G.vex5.description=学生作品会展中心，学习活动之地; G.vex6.description=海南师范大学信息中心，各种书籍应有尽有; G.vex7.description=排球篮球比赛，晚会，各种报告，开学典礼举行都在这破地方举行; G.vex8.description=老师和同学们吃饭的地方，这里的饭比一食堂好吃，菜不错ntt看你肚皮有没有猪八戒大,你要是吃不饱可以考虑来这吃，准让你撑死; G.vex9.description=男生鸟窝，这楼不错住着舒服，不过你 要想住ntt首先你得学会尖叫的本领，半夜明月高照的时候，可以尖叫尖叫; G.vex10.description=学校后门就是海南中学，后门有许多小吃哦，还有很多可爱东东买哦; 6.这个函数可用于在主界面输出void pingmu() / 屏幕输出函数 int i; printf(nntt%c%c%c%c%c%c%c%c%c%c%c欢迎来到海南师范大学%c%c%c%c%c%c%c%c%c%cnn,6,6,6,6,6,6,6,6,6,6,6,6,6,6,6,6,6,6,6,6,6); printf(tt%c %c %c %c %c %c %c %c %c %c %c %c %c %c %c %c %c %c %c %c %cn,3,3,3,3,3,3,3,3,3,3,3,3,3,3,3,3,3,3,3,3,3); printf(tt%ctt学校简介tt%cn,1,1); printf(tt%c %c %c %c %c %c %c %c %c %c %c %c %c %c %c %c %c %c %c %c %cn,3,3,3,3,3,3,3,3,3,3,3,3,3,3,3,3,3,3,3,3,3); printf(tt%ctt学校概况tt%cn,6,6); printf(tt%c %c %c %c %c %c %c %c %c %c %c %c %c %c %c %c %c %c %c %c %cn,3,3,3,3,3,3,3,3,3,3,3,3,3,3,3,3,3,3,3,3,3); for(i=1;i G.vexsight2的时候，或者是在主函数里调用G.vexi.sight的时候没有写 .sight ，就会调用不到sight里所存储的信息，屏幕就不会输出我们想要查找的相关信息。8. output输出函数算法与前面图的算法联系不上。也就是没有通过输出函数输出图里所存放的顶点信息。9.哈密尔顿的遍历出错，调试虽然出来了但结果不合理。输出最佳路径的时候，学校简介也输出来了，其主要原因是数据的初始化不对。10.程序调试出来了，但没有达到预先想要的结果，看上去感觉不