校园导航系统

目录摘 要 2正文 31 设计目的及要求32 设计原理32.1 C/C+语言简介32.2 开发环境32.3 系统模块分析43 设计内容43.1 方案设计与论证43.2 数据结构描述与定义53.3 主要函数的说明63.4 设计结果验证11总结与致谢14参考文献15附录 16摘要与传统的地图相比较，地理信息系统有着不可比拟的优势，信息量大，切换方便，可扩 展性强。校园导航问题是基于校园中的不同的景点，从陌生人的角度，为来往的客人提供校 园景点相关信息的查询以及为来往的客人提供校园中任意景点的问路查询，以便客人能用最 短的时间从某一地点到达想要去的地方。大大节约了旅客参观校园的时间。本文是采用C+作为开发语言，又最大程度上用了 C语言的有关的语法。以visual C+6.0 为开发工具。旨在实现校园导航系统中，学校的简介，景点的介绍，路线查询等基本的问题。 为来往客人参观校园提供方便。关键字：visual C+6.0 ；校园导航系统；正文1设计目的及要求1. 了解并掌握数据结构与算法的设计方法，具备初步的独立分析和设计能力；2. 初步掌握软件开发过程的问题分析、系统设计、程序编码、测试等基本方法和技能；3. 独立完成，提高综合运用所学的理论知识和方法独立分析和解决问题的能力；4. 训练用系统的观点和软件开发一般规范进行软件开发，培养软件工作者所应具备的 科学的工作方法和作风。5. 设计学校平面图，至少包括10 个以上场所，校园导航系统能自动找出校园平面图中 任意起始点与终点的最佳路径（最短路径）。求并输出路径及路径长度。2 设计原理2.1 C/C+语言简介C 语言是一种计算机程序设计语言。它既具有高级语言的特点，又具有汇编语言的特点。它由美国贝尔研究所的D.M.Ritchie于1972年推出。1978后，C语言已先后被移植到大、 中、小及微型机上。它可以作为工作系统设计语言，编写系统应用程序，也可以作为应用程 序设计语言，编写不依赖计算机硬件的应用程序。它的应用范围广泛，具备很强的数据处理 能力，不仅仅是在软件开发上，而且各类科研都需要用到 C 语言，适于编写系统软件，三 维，二维图形和动画。具体应用比如单片机以及嵌入式系统开发。C+是一种静态数据类型检查的、支持多重编程范式的通用程序设计语言。它支持过程 化程序设计、数据抽象、面向对象程序设计、制作图标等等泛型程序设计等多种程序设计风 格。2.2 开发环境 随着科学技术的不断发展，计算机科学日渐成熟，其强大的功能已为人们所深刻认识，它己进入人类社会的各个领域并发挥着越来越重要的作用。采用计算机进行校园导航已成为 衡量校园数字化的重要标志。校园导航效率的好坏对于来校参观的客人和学校管理者来说都 至关重要，在很大程度上影响着校园的数字化建设和学校的影响力。因此，本文所研究的校 园导航系统具有一定的使用价值和现实意义。2.3 系统模块分析采用工程思想，将系统共分一下几个模块:数据结构定义模块、导航图建立模块、求最 短路径模块、主菜单；下面是具体各功能简单的实际应用：数据结构定义模块：模块定义了导航图中各个节点的基本结构类型，主要采用邻 接矩阵的存储结构来真实反映各节点到其他所有节点的路径长度（权值大小）。导航图建立模块：采用上述结构体类型对导航图中每个节点进行赋值。包括：各 定点的名称（地点名），各个节点到其他所有节点的真实路径长度（赋权值）。求最短路径模块：本模块的基本思想是采用迪杰斯特拉算法求最短路径。次模块 是本校园导航系统的核心模块，求两点间的最短路径与求一点到其他所有点最短 路径两个子功能均是在最短路径算法模块的基础上进行调用，进而实现导航功 能。主菜单：主菜单中主要是显示导航图中的所有导航节点，能够快速方便的对各个地 点进行导航。以上程序的几个模块，构成了校园导航系统的基本组成部分，程序运行良好，达到了课 程设计的基本要求。3设计内容3.1 方案设计与论证校园旅游模型是由各个景点和景点以及场所和场所之间的路径组成的，所以这完全可以 用数据结构中的图来模拟。用图的结点代表景点或场所，用图的边代表景点或场所之间的路 径。所以首先应创建图的存储结构。结点值代表景点信息，边的权值代表景点间的距离。结 点值及边的权值采用图存储。本系统需要查询景点信息和求一个景点到另一个景点的最短路 径长度及路线，为方便操作，所以给每个景点一个代码，用结构体类型实现。计算路径长度， 最短路线和最佳路径时可分别用迪杰斯特拉（Dijkastra）算法和哈密而顿回路算法实现。最 后用 switch 选择语句选择执行浏览景点信息或查询最短路径和距离。图 1 ：山东建筑大学重要平面图3.2 数据结构描述与定义1、结构体的定义：typedef struct VertexTypeint number;char *sight;VertexType;typedef structVertexType vexNUM;int arcsNUMNUM;int vexnum;2、常量的定义：#define Max 32767#define NUM 13、各个函数的定义： void CreateMGraph(int v) /创建图的函数，其中 v 表示图中的顶点数 void Map() /地图展示函数,用于输出山东建筑大学的平面简略图 char Menu() /主菜单显示于操作界面 void Info() /资料介绍函数，用于当用户选择查询地点资料时输出地点的资料信息void Dijkstra(int num) 迪杰斯特拉函数void Display(int sightl,int sight2) /地图展示函数void main() /主函数的定义3.3主要函数的说明Mam()Info()图：主函数对各个函数的调用#define Max 32767/用Max来表示权值为此时的两点间直接不可达#defineNUM15/选取了学校的十七个地点用数组存储，其中数组第一个元素不存储地点以方便操作typedef struct VertexTypeint number;char *sight;VertexType;/定义顶点的结构体类型，number表示顶点编号，字符数组表示顶点的名称typedef structVertexType vexNUM;int arcsNUMNUM;int vexnum;MGraph;/定义图的结构体类型，vexNUM数组存储顶点，arcspNUMNUM矩阵存储边的权值，vexnum表示顶点的个数MGraph G;生成G表示结构体变量MGraphint PNUMNUM;定义全局变量PNUMNUM 存储点之间的最短路径long int DNUM;定义全局变量DNUM存储点之间最短路径的权值void Dijkstra(int num)/通过迪杰斯特拉算法求num点到其余点的最短路径，并将最短路径保存在数组PNUMNUM中，将最短路径的权值保存在数组DNUM中int v,w,i,t;int finalNUM;int min;for(v=1;vNUM;v+)finalv=0; /置空最短路径终点集Dv=G.arcsnumv; /置初始的最短路径长度for(w=1;wNUM;w+)Pvw=0; /置空最短路径if(Dv32767)Pvnum=1;Pvv=1;Dnum=0;finalnum=l;/初始化num顶点属于S集for(i=l;iNUM;+i)/开始循环，每次求得num到某个顶点的最短路径，并添加到S集min二Max;/min为当前所知的num到顶点的最短距离for(w=1;wNUM;+w)if(!finalw) /w 顶点在 V-S 集中if(Dwmin)min=Dw;finalv=l;/与num相距最近的顶点并入S集for(w=1;wNUM;+w) /更新最短路径辻(！finalw&(min+G.arcsvw)Dw)/修改 Dw和Pw, w在V-S集中Dw=min+G.arcsvw;for(t=0;tNUM;t+)Pwt=Pvt;Pww=1;char Menu() /主菜单显示于操作界面从而让用户选择查询路径功能或者查询地点信息 功能char c;int flag; /定义标志flag确定循环条件doflag=1;Map();printf(tt 1.查询地点路径 n);prin tf(tt 2.地点信息简介n);pri ntf (tt e.退出 n);pri ntf (t*山东建筑大学 *n);printf (ttt请输入您的选择：)；scanf(%c,&c);if(c=1|c=2|c=e)flag=0;while(flag);return c;void Display(in t sigh tl,in t sigh t2)/输出函数用于通过数组 PNUMNU M提取出从点sightl到点sight2的最短路径，从DNUM中输出点sightl到点sight2的最短路径 的权值int a,b,c,d,q=0;a=sight2;if(a!=sightl)printf (nt从%$到$的最短路径是 ,G.vexsightl.sight,G.vexsight2.sight);printf(t (最短距离为 %dm.)nnt,Da);/从 DNUM中提取出 sight1到sight2的最短距离的权值输出printf(t%s,G.vexsightl.sight);d=sightl;for(c=0;cNUM;+c)Pasightl=0; for(b=0;bNUM;b+)if(G.arcsdb32767&Pab)printf(s,G.vexb.sight);/通过 PNUMNUM确定sightl到sight2的最短路径q=q+l;Pab=0;d=b;if(q%8=0) printf(n);void main() /主函数int v0,v1;char e;char ck;CreateMGraph(NUM);Do/用do while循环确保循环至少进行一次system(cls);/用 system(cls)清屏使屏幕简洁ck=Menu();switch(ck)/用switch语句确定用户选择功能1 case 1:gate:/门函数使程序退回到gate位置system(cls);Map();doprintf (nnttt请选择出发地序号(114)：); scanf(%d,&v0);if(v017)printf(nntttt 输入错误!n); while(v017);doprintf(ttt请选择目的地序号(114)：);scanf(%d,&v1);if(v114|v1=v0)printf(nntttt 输入错误!n);while(v114|v1=v0);Dijkstra(v0);Display(v0,v1);printf(nntttt请按任意键继续，按e退回首页n); getchar();scanf(%c，&e);if(e=e)当标识符e等于e时跳出语句break;goto gate;case2:system(cls);Info();printf(nntttt 请按回车键退回首页.n);getchar();getchar();break;while(ck!=e);/当标识符ck不等于e时继续循环3.4 设计结果验证图2山东建筑大学导航系统首页.=Hk- 趙 灵的何作fwoiF;活耆爭爭.n矗渤 二._甞_一百山 亠L八律八宅罟臣一应抹.龟心x=_0 12 3 4 5图3选择2后的山建景点介绍丛办楼到逸天楼的最更珞径是最短距离対13S5n亦施-汐卜丈揆-博丈搂-逸夫校按回耳锭继续投匕退目首瓦外东门3建艺馆办舌搂T刘文楼T博文桜7逸夫楼k只唁息楼,10十木楼一exeC: VDociiBeiit and图4选择1后查询4到7的最短路径结果吕口万 也也 出冃 韋 诜诜一 请请总结与致谢随着计算机软硬件的不断发展，导航系统在客户需求中的应用已成必然。 本系统在开 发中也是严格按照学校的实际情况进行开发的，在开发中，查阅了很多相关的算法资料，巩 固了数据结构、C语言和C+方面的知识，同时也学习了新的算法知识。最重要的是在开发 过程中，通过不断地学习，不断提高自己编程能力和实际应用能力，还有助于改善自己的逻 辑思维能力，这对自己以后对软件的开发提供很大的帮助。另外通过此次课程的设计使我认 识到对知识的掌握不全面，即在学习专业知识的同时还需要再加强其他方面知识的学习，因 为软件的开发有时候涉及到其他方面的知识，只有了解了其他方面的知识才能收集资料，然 后用于软件开发。短暂的课程设计就要结束了，在此，感谢所有在学习和生活中给予我关心和帮助的人 们。首先我要感谢杨红娟、张君捧两位位老师，本次课程设计设计的选题、课题调研与撰写 工作实在和老师的指导下完成的。和老师渊博的知识、严谨的治学态度、一丝不苟的工作作 风、和不厌其烦的精神对我影响至深，使我受益终生，在此我向和老师表示崇高的敬意和衷 心的感谢。其次，在我的课程设计期间，同课题的同学都给予了我热情的帮助和无私的指导，在此 向这些同学们表示衷心的感谢。 最后，向所有曾给予我关心和帮助的老师和同学们再次致以最衷心的感谢，向参加报告评审、 答辩的老师表示衷心的感谢和崇高的敬意参考文献1 数据结构及应用算法教程，严蔚敏、陈文博，清华大学出版社，20112 数据结构与程序设计（影印版），（美）Robert L.Kruse,Alexander J.Ryba,高等教育出版社， 20013 数据结构与算法分析，（美）Mark Allen Weiss机械工业出版社，20044 数据结构算法实现及解析，高一凡，西安电子科技大学， 20085 计算机软件技术基础（第二版），徐士良、葛兵，清华大学出版社， 20076 计算机软件技术基础（第三版），沈被娜、刘祖照、姚晓冬，清华大学出版社， 20077 软件开发技术基础（第2版），赵应良，机械工业出版社， 20048 （美） H.M.Deitel, P.J.Deitel 著，薛万鹏等译， C 程序设计教程，北京：机械工业出版社， 20009 C语言程序设计，谭浩强主编，清华大学出版社，201010 Brian W. Kernighan Dennis M. Ritchie, C PROGRAMMING LANGUAGE, 清华大学影印版 ,2001 年 6 月第 10 次印刷附录#include #include #include #define Max 32767#define NUM 16typedef struct VertexTypeint number;char *sight;VertexType;typedef structVertexType vexNUM;int arcsNUMNUM;int vexnum;MGraph;MGraph G;int PNUMNUM;long int DNUM;/void CreateMGraph(int v)创建图的函数int i,j;G.vexnum=v;for(i=1;iG.vexnum;+i)G.vexi.number=i;G.vexO.sight=各个景点名字；G.vexl.sight=东门；G.vex2.sight=小东门；G.vex3.sight=建艺馆；G.vex4.sight=办公楼；G.vex5.sight=外文楼；G.vex .sight=博文楼；G.vex7.sight=逸夫楼；G.vex8.sight=信息喽；G.vex9.sight=图书馆；G.vex10.sight= 土木楼；G.vexll.sight=映雪湖；G.vex12.sight=操场；G.vex13.sight=食堂；G.vex14.sight=宿舍；G.vex15.sight=雪山；for（i=1；iG.vexnum；+i）for（j=1；jG.vexnum；+j）G.arcsij=Max；G.arcs12=G.arcs21=212；G.arcs14=G.arcs41=501；G.arcs115=G.arcs151=140；G.arcs24=G.arcs42=299；G.arcs25=G.arcs52=307；G.arcs34=G.arcs43=601；G.arcs35=G.arcs53=1023；G.arcs39=G.arcs93=1312；G.arcs312=G.arcs123=806；G.arcs45=G.arcs54=355；G.arcs49=G.arcs94=1300；G.arcs411=G.arcs114=1800；G.arcs56=G.arcs65=750；G.arcs67=G.arcs76=180;G.arcs68=G.arcs86=241;G.arcs610=G.arcs106=250;G.arcs611=G.arcs116=720;G.arcs78=G.arcs87=140;G.arcs810=G.arcs108=350;G.arcs912=G.arcs129=650;G.arcs913=G.arcs139=1225;G.arcs911=G.arcs119=700;G.arcs1011=G.arcs1110=520;G.arcs1112=G.arcs1211=639;G.arcs1113=G.arcs1311=405;G.arcs1213=G.arcs1312=1083;G.arcs1214=G.arcs1412=1096; void Map()地图展示函数n);13printf(t * 山 东 建 筑 大 学 大 学 地 图 导 航 系 统Tx Tx Tx Tx Tx Tx Tx Tx Tx Tx Tx Tx Tx Tx Tx Tx Tx Tx Txprintf(n);printf(n);printf(食堂一14宿舍n);printf(IIn)；printf(printf(n);printf(I12操场n);printf(!n);printf(!15 雪山n);printf(!n);printf(!8 信息楼图书馆n);printf(!n);printf(!11映雪湖一III10 土木楼IIn);printf(3建艺馆4办公楼一5外文楼一6博文楼7逸夫楼printf(Iprintf(Iprintf(东门II2小n);n);n);1 东门n);void Info（）资料介绍函数printf（1 东门 ： 山建的正门n）;printf（2小东门：山建侧门n）;printf（3建艺馆：艺术生学习的地方n）;printf（4办公楼：学校办公的地方n）;printf（5外文楼：外语学习地n）;printf（6博文楼：主要自习楼n）;printf（7逸夫楼：自习楼n）;printf（8信息楼：领导办公地n）;printf（9图书馆：图书馆n）;printf（10土木楼：土木学院学习n）;printf（11映雪湖：山建最大的湖n）;printf（12操场： 操场n）;printf（13食堂： 吃饭n）;printf（14宿舍： 睡觉n）;printf（15雪山： 山建的灵魂n）;void Dijkstra（int num）迪杰斯特拉算法最短路径int v,w,i,t;int finalNUM;int min;for（v=1;vNUM;v+）finalv=0;Dv=G.arcsnumv; for（w=1;wNUM;w+）Pvw=0;if（DvMax）Pvnum=1;Pvv=1;Dnum=0;finalnum=1;for(i=1;iNUM;+i)min=Max;for(w=1;wNUM;+w)if(!finalw)if(Dwmin)v=w;min=Dw;finalv=1;for(w=1;wNUM;+w) if(!finalw&(min+G.arcsvw)Dw) Dw=min+G.arcsvw;for(t=0;tNUM;t+)Pwt=Pvt;Pww=1;char Menu() 主菜单char c;int flag;dosystem(cls);flag=1;Map();printf(tt欢迎使用山东建筑大学导航图系统n);printf(tt 1.查询地点之间最短路径 n);printf(tt 2.山东建筑大学景点介绍n);printf(tt e.退出 n);printf(ttt请输入您的选择：”)；scanf(%c,&c);if(c=1|c=2|c=e)flag=0;while(flag);return c;void Display(int sightl,int sight2)/输出函数int a,b,c,d,q=0;a=sight2;if(a!=sightl)printf(nt 从$ 到$ 的最短路径是,G.vexsight1.sight,G.vexsight2.sight);printf(t(最短距离为 dm.)nnt,Da);printf(t%s,G.vexsight1.sight);d=sight1;for(c=0;cNUM;+c)Pasight1=0;for(b=0;bNUM;b+)if(G.arcsdb%s,G.vexb.sight); q=q+1;Pab=0;d=b;if(q%8=0) printf(n);void main()主函数int v0,v1;char e;char ck;CreateMGraph(NUM);dosystem(cls);ck=Menu();switch(ck)case 1:gate:system(cls);Map();doprintf(nnttt请选择出发地序号(114)：);scanf(%d,&v0);if(v015)printf(nntttt 输入错误!n);while(v015);doprintf(ttt请选择目的地序号(114)：);scanf(%d,&v1);if(v115|v1=v0)printf(nntttt 输入错误!n);while(v115|v1=v0);Dijkstra(v0);Display(v0,v1);printf(nntttt按回车键继续，按e退回首页n);getchar();scanf(%c，&e);if(e=e)break;goto gate;case2:system(cls);Info();printf(nntttt 按回车键返回首页.n);getchar();getchar();break;while(ck!=e);