《校园导航系统---算法与分析报告课程设计》由会员分享，可在线阅读，更多相关《校园导航系统---算法与分析报告课程设计（23页珍藏版）》请在金锄头文库上搜索。
1、侈k A f算法设计与分析课程设计题目：校园导航问题文档:物联网工程学院物联网工程 专业学 号学生姓名班 级物联网1101二一三年十二月设计要求：设计你的学校的平面图，至少包括10个以上的场所，每两个场所间可以有不同的路，且路长也可能不同，找出从任意场所到达另一场所的最 佳路（最短路径）。本系统为用户提供以下功能：（一）、查询了解学校概况，为导游参观者提供关于学校的相关信息。（二）、查询校园各个场所和景点信息；（三） 、为导游者或外来人员参观人员提供校园交通信息，方便用户走访学校。 完成需要操作时，退出系统校园导航查询系统的开发方法总结如下：（1）需求分析，了解学校各个场所与场所或者是各个景点
2、与景点之间的信 息，路径和距离，考虑该如何设计才能满足用户需求。（2）概要设计，对调查得到的数据进行分析，根据其要求实现的功能分析系 统结构和界面将实现的基本功能。（3）详细设计，设计系统界面并编辑实现其各个功能的代码。（4）调试分析，在设计完成后，调试系统运行的状况，修改完善系统，然后进行测试。一、需求分析1学校以及各景点介绍模块采用一维数组将学校景点依次排放好编号 G.vexi. number=i在选择校园介绍的时候，弹出G.vex0校园简介。在选择各景点信息的时候，可按编号查 询2查询最短路径（主要）查出出发地到想要到达的景点的最短路径， 初步构想采用最经典的迪杰斯特 拉算法最短路径函数
3、3查询各点距离将所有景点的距离显示出来。4主菜单页面显示提供使用者选择功能界面，按照提示进行操作。5退出完成需要操作时，退出系统校园导航系统校园介绍，各景查询校园所有景最短路径查询查询各景点距点介绍点路径卜J输入起点与终点输出最短路径校园导航系统模式图二、概要设计2.1算法设计说明校园导航模型是由各个景点和景点以及场所和场所之间的路径组成的，所 以这完全可以用数据结构中的图来模拟。 用图的结点代表景点或场所，用图的边 代表景点或场所之间的路径。所以首先应创建图的存储结构。结点值代表景点信 息，边的权值代表景点间的距离。结点值及边的权值采用图存储。 本系统需要查 询景点信息和求一个景点到另一个景
4、点的最短路径长度及路线，为方便操作，所以给每个景点一个代码，用结构体类型实现。计算路径长度，最短路线和最佳路 径时可分别用迪杰斯特拉(Dijkastra )算法和哈密而顿回路算法实现。最后 switch选择语句选择执行浏览景点信息或查询最短路径和距离。学校以及各景点介绍模块采用了图的邻接矩阵存储结构，首先初始化每一个景点名称（一维数组）for（i=1;iG.vexnum;+i） G.vexi.number=iSearchMenu 子菜单输入景点编号编号值=ilnum输出“错误”输出景点介绍结束景点介绍功能流程图查询最短路径（主要）算法的主要思想是按路径长度递增的次序产生最短路径的算法。中心思想
5、 是假设s为已求得最短路径的终点的集合，则下一条最短路径或者是弧(v,x)或者是中间经过s中是顶点而最后到达顶点x的路径。(1) arcs表示弧上的权值。若不存在，则置 arcs为S为已找到从v 出发的最短路径的终点的集合，初始状态为空集。那么，从v出发到图上其余各 顶点vi可能达到的最短路径长度的初值为D=arcsLocate Vex(G,v),i vi V(2) 选择 vj，使得 Dj=MinD | vi V-S(3修改从v出发到集合V-S上任一顶点vk可达的最短路径长度厂Dnum=O点为tium权恆为。1=1冥余其僉 G佬jtnumJ个琨 占r ! !Nh mtrpMax;当前軒知an点
6、numS近匡爲D佃为班已苕走路径查询流程图查询各点距离由于图的结构比较复杂，任意两个点之间都可能存在联系。因此无法以数据 元素在存储区中的物理位置来表示元素之间的关系，但是却可以借助数组的数据 类型表示元素之间的关系。主函数循环体用开关语句，该语句的条件值 ck是当用户选择菜单通过调用主菜单 函数得到，返回值整数作开关语句的条件。 根据该值调用相应的各功能函数，同 时设置一个退出程序点，执行完用户的某项功能后继续显示菜单，当返回值为e时函数结束程序，以免造成死循环。2.2数据结构与函数考虑数据结构定义结构体类型，将多个相关的变量包装成为一个整体使用#defi ne Max 32767#defi
7、 ne NUM 20自定义顶点的类型typedef struct VertexTypeint nu mber; /景点编号char *sight;景点名称VertexType;自定义图的类型typedef structVertexType vexNUM; /图中的顶点，即为景点int arcsNUMNUM; /图中的边，即为景点间的距离int vex num; /顶点数MGraph;把图定义为全局变量MGraph G;int PNUMNUM;辅助变量存储最短路径长度long int DNUM;222使用的系统头文件#i nclude stdio.h /*1/0函数 */#include std
8、lib.h/* 使用 system （）exit（）atoi （） malloc （） free（）函 */#include string.h/* 字符串函数，strcpy （）strlen （） strcmp （）*/三、主程序#in clude #in clude #i nclude #defi ne Max 32767#defi ne NUM 20typedef struct VertexTypeint nu mber;char *sight;VertexType;typedef structVertexType vexNUM;int arcsNUMNUM;int vex num;MGr
9、aph;MGraph G;int PNUMNUM;long int DNUM;void CreateMGraph（i nt v）创建图的函数,v是函数入口int i,j;G.vex num=v;for(i=1;iG.vex nu m;+i)G.vexi. nu mber=i;G.vexO.sight=各个地点名字;G.vex1.sight=江南大学校北门”G.vex2.sight=第一食堂;G.vex3.sight=江南大学东偏门”G.vex4.sight=设计学院;G.vex5.sight=体育中心；G.vex 6.sight=物联网工程学院”G.vex7.sight=图书馆;G.vex8.
10、sight=江南大学东门;G.vex9.sight=国家重点实验室”G.vex10.sight=第二教学楼;G.vex11.sight=第四食堂;G.vex13.sight=臻善楼;G.vex12.sight=江南大学南门;for(i=1;iG.vex nu m;+i)for(j=1;jG.vex nu m;+j)G.arcsij=Max;G.arcs12=G.arcs21=200;G.arcs13=G.arcs31=210;G.arcs15=G.arcs51=521;G.arcs24=G.arcs42=299;G.arcs25=G.arcs52=450;G.arcs23=G.arcs32=8
11、69;G.arcs35=G.arcs53=620;G.arcs38=G.arcs83=756;G.arcs45=G.arcs 54=355;G.arcs46=G.arcs 64=221;G.arcs57=G.arcs75=225;G.arcs58=G.arcs85=900;G.arcs67=G.arcs7 6=280;G.arcs69=G.arcs9 6=241;G.arcs78=G.arcs87=440;G.arcs710=G.arcs107=350;G.arcs810=G.arcs108=570;G.arcs910=G.arcs109=1300;G.arcs911=G.arcs119=99
12、8;G.arcs912=G.arcs129=1200;G.arcs1011=G.arcs1110=639;G.arcs1012=G.arcs1210=805;G.arcs1112=G.arcs1211=283;G.arcs1213=G.arcs1312=296;void Map()地图展示函数江南大学大学地图导航系统次次次次次次次次次次次次次次次次次次次次次次次次*n);prin tf( 1江南大学北大门n);printf(”|In);printf(|In);10II5体育中心III7图书馆III第二教学楼Iprin tf(” 2第一食堂江南大学东偏门n);prin tf(|In);prin tf(|In);prin tf( 4 设计学院，In ”)；prin tf(|In);prin tf(|In);prin tf(IIn);printf( 6 物联网工程学院，江南大学东门n);prin tf(IIn);prin tf(IIn);prin tf(IIn);printf( 9 国家重点实验室In ”)；prin tf(IIn);prin tf(IIn);printf(In);III 11第四食堂I
