欢迎来到天天文库
浏览记录
ID:25834607
大小:369.78 KB
页数:18页
时间:2018-11-23
《校园导航系统---算法与分析课程设计》由会员上传分享,免费在线阅读,更多相关内容在学术论文-天天文库。
1、算法设计与分析课程设计题目:校园导航问题文档:物联网工程学院物联网工程专业学号学生姓名班级物联网1101二〇一三年十二月设计要求:设计你的学校的平面图,至少包括10个以上的场所,每两个场所间可以有不同的路,且路长也可能不同,找出从任意场所到达另一场所的最佳路(最短路径)。本系统为用户提供以下功能:(一)、查询了解学校概况,为导游参观者提供关于学校的相关信息。(二)、查询校园各个场所和景点信息;(三)、为导游者或外来人员参观人员提供校园交通信息,方便用户走访学校。完成需要操作时,退出系统校园导航查询系统的开发方法总结如下:(1)需求分析,了解学校各个场所与场所或者是各个景点与景点之间的信息,
2、路径和距离,考虑该如何设计才能满足用户需求。(2)概要设计,对调查得到的数据进行分析,根据其要求实现的功能分析系统结构和界面将实现的基本功能。(3)详细设计,设计系统界面并编辑实现其各个功能的代码。(4)调试分析,在设计完成后,调试系统运行的状况,修改完善系统,然后进行测试。一、需求分析1学校以及各景点介绍模块采用一维数组将学校景点依次排放好编号G.vex[i].number=i在选择校园介绍的时候,弹出G.vex[0]校园简介。在选择各景点信息的时候,可按编号查询2查询最短路径(主要)查出出发地到想要到达的景点的最短路径,初步构想采用最经典的迪杰斯特拉算法最短路径函数3查询各点距离将所有
3、景点的距离显示出来。4主菜单页面显示提供使用者选择功能界面,按照提示进行操作。5退出完成需要操作时,退出系统校园导航系统最短路径查询查询各景点距离查询校园所有景点路径校园介绍,各景点介绍输入起点与终点输出最短路径校园导航系统模式图二、概要设计2.1算法设计说明校园导航模型是由各个景点和景点以及场所和场所之间的路径组成的,所以这完全可以用数据结构中的图来模拟。用图的结点代表景点或场所,用图的边代表景点或场所之间的路径。所以首先应创建图的存储结构。结点值代表景点信息,边的权值代表景点间的距离。结点值及边的权值采用图存储。本系统需要查询景点信息和求一个景点到另一个景点的最短路径长度及路线,为方便
4、操作,所以给每个景点一个代码,用结构体类型实现。计算路径长度,最短路线和最佳路径时可分别用迪杰斯特拉(Dijkastra)算法和哈密而顿回路算法实现。最后switch选择语句选择执行浏览景点信息或查询最短路径和距离。2.1.1学校以及各景点介绍模块采用了图的邻接矩阵存储结构,首先初始化每一个景点名称(一维数组)for(i=1;i5、假设s为已求得最短路径的终点的集合,则下一条最短路径或者是弧(v,x)或者是中间经过s中是顶点而最后到达顶点x的路径。(1)arcs表示弧上的权值。若不存在,则置arcs为∞。S为已找到从v出发的最短路径的终点的集合,初始状态为空集。那么,从v出发到图上其余各顶点vi可能达到的最短路径长度的初值为D=arcs[LocateVex(G,v),i]vi∈V(2)选择vj,使得D[j]=Min{D6、vi∈V-S}(3修改从v出发到集合V-S上任一顶点vk可达的最短路径长度路径查询流程图2.1.3查询各点距离由于图的结构比较复杂,任意两个点之间都可能存在联系。因此无法以数据元素在存储区中的物理位置7、来表示元素之间的关系,但是却可以借助数组的数据类型表示元素之间的关系。2.1.4主函数循环体用开关语句,该语句的条件值ck是当用户选择菜单通过调用主菜单函数得到,返回值整数作开关语句的条件。根据该值调用相应的各功能函数,同时设置一个退出程序点,执行完用户的某项功能后继续显示菜单,当返回值为e时函数结束程序,以免造成死循环。2.2数据结构与函数考虑2.2.1数据结构定义结构体类型,将多个相关的变量包装成为一个整体使用。#defineMax32767#defineNUM20自定义顶点的类型typedefstructVertexType{intnumber;//景点编号char*sight;//8、景点名称}VertexType;自定义图的类型typedefstruct{VertexTypevex[NUM];//图中的顶点,即为景点intarcs[NUM][NUM];//图中的边,即为景点间的距离intvexnum;//顶点数}MGraph;把图定义为全局变量MGraphG;intP[NUM][NUM];辅助变量存储最短路径长度longintD[NUM];2.2.2使用的系统头文件#include"stdio.h"
5、假设s为已求得最短路径的终点的集合,则下一条最短路径或者是弧(v,x)或者是中间经过s中是顶点而最后到达顶点x的路径。(1)arcs表示弧上的权值。若不存在,则置arcs为∞。S为已找到从v出发的最短路径的终点的集合,初始状态为空集。那么,从v出发到图上其余各顶点vi可能达到的最短路径长度的初值为D=arcs[LocateVex(G,v),i]vi∈V(2)选择vj,使得D[j]=Min{D
6、vi∈V-S}(3修改从v出发到集合V-S上任一顶点vk可达的最短路径长度路径查询流程图2.1.3查询各点距离由于图的结构比较复杂,任意两个点之间都可能存在联系。因此无法以数据元素在存储区中的物理位置
7、来表示元素之间的关系,但是却可以借助数组的数据类型表示元素之间的关系。2.1.4主函数循环体用开关语句,该语句的条件值ck是当用户选择菜单通过调用主菜单函数得到,返回值整数作开关语句的条件。根据该值调用相应的各功能函数,同时设置一个退出程序点,执行完用户的某项功能后继续显示菜单,当返回值为e时函数结束程序,以免造成死循环。2.2数据结构与函数考虑2.2.1数据结构定义结构体类型,将多个相关的变量包装成为一个整体使用。#defineMax32767#defineNUM20自定义顶点的类型typedefstructVertexType{intnumber;//景点编号char*sight;//
8、景点名称}VertexType;自定义图的类型typedefstruct{VertexTypevex[NUM];//图中的顶点,即为景点intarcs[NUM][NUM];//图中的边,即为景点间的距离intvexnum;//顶点数}MGraph;把图定义为全局变量MGraphG;intP[NUM][NUM];辅助变量存储最短路径长度longintD[NUM];2.2.2使用的系统头文件#include"stdio.h"
此文档下载收益归作者所有