1、 算法设计与分析课程设计算法设计与分析课程设计 题目：题目： 校园导航问题 文档：文档： 物联网工程 学 院 物联网工程 专 业 学 号 学生姓名 班 级 物联网 1101 二一三年十二月 设计要求：设计你的学校的平面图，至少包括设计要求：设计你的学校的平面图，至少包括 10个以上的场所，每两个场个以上的场所，每两个场 所间可以有不同的路，且路所间可以有不同的路，且路长也可能不同，找出从任意场所到达另一场所的最长也可能不同，找出从任意场所到达另一场所的最 佳路（最短路径） 。佳路（最短路径） 。 本系统为用户提供以下功能: (一)、查询了解学校概况，为导游参观者提供关于学校的相关信息。 (二)
2、、查询校园各个场所和景点信息; (三)、 为导游者或外来人员参观人员提供校园交通信息， 方便用户走访学校。 完成需要操作时，退出系统 校园导航查询系统的开发方法总结如下： (1) 需求分析，了解学校各个场所与场所或者是各个景点与景点之间的信 息，路径和距离，考虑该如何设计才能满足用户需求。 (2) 概要设计，对调查得到的数据进行分析，根据其要求实现的功能分析系 统结构和界面将实现的基本功能。 (3) 详细设计，设计系统界面并编辑实现其各个功能的代码。 (4) 调试分析，在设计完成后，调试系统运行的状况，修改完善系统,然后进 行测试。 一、一、需求分析需求分析 1 学校以及各景点介绍模块学校以及
3、各景点介绍模块 采用一维数组将学校景点依次排放好编号 G.vexi.number=i 在选择校园介 绍的时候，弹出 G.vex0校园简介。在选择各景点信息的时候，可按编号查询 2 查询最短路径（主要）查询最短路径（主要） 查出出发地到想要到达的景点的最短路径， 初步构想采用最经典的迪杰斯特 拉算法最短路径函数 3 查询查询各点距离各点距离 将所有景点的距离显示出来。 4 主菜单页面显示主菜单页面显示 提供使用者选择功能界面，按照提示进行操作。 5 退出退出 完成需要操作时，退出系统 校园导航系统模式图 二、概要设计概要设计 2.1 算法设计说明算法设计说明 校园导航模型是由各个景点和景点以及场
4、所和场所之间的路径组成的，所 以这完全可以用数据结构中的图来模拟。用图的结点代表景点或场所，用图的边 代表景点或场所之间的路径。所以首先应创建图的存储结构。结点值代表景点信 息，边的权值代表景点间的距离。结点值及边的权值采用图存储。本系统需要查 询景点信息和求一个景点到另一个景点的最短路径长度及路线，为方便操作，所 以给每个景点一个代码，用结构体类型实现。计算路径长度，最短路线和最佳路 径时可分别用迪杰斯特拉 （Dijkastra） 算法和哈密而顿回路算法实现。 最后 switch 选择语句选择执行浏览景点信息或查询最短路径和距离。 2.1.1 学校以及各景点介绍模块 采用了图的邻接矩阵存储结
5、构，首先初始化每一个景点名称（一维数组） for(i=1;iG.vexnum;+i) G.vexi.number=i 校园导航系统 校园介绍，各景 点介绍 查询校园所有景 点路径 最短路径查询 查询各景点距 离 输入起点与终点 输出最短路径 景点介绍功能流程图 2.1.2 查询最短路径（主要） 算法的主要思想是按路径长度递增的次序产生最短路径的算法。中心思想 是假设 s 为已求得最短路径的终点的集合，则下一条最短路径或者是弧（v,x）或 者是中间经过 s 中是顶点而最后到达顶点 x的路径。 （1）arcs 表示弧上的权值。若不存在，则置 arcs 为。S 为已找到从 v出发 的最短路径的终点的
6、集合，初始状态为空集。那么，从 v出发到图上其余各顶点 vi可能达到的最短路径长度的初值为 D=arcsLocate Vex(G,v),i viV （2）选择 vj，使得 Dj=MinD | viV-S SearchMenu 子菜单 输入景点 编号 编号值=i Inum 输出景点介 绍 输出“错 误” 结束 (3 修改从 v出发到集合 V-S 上任一顶点 vk 可达的最短路径长度 路径查询流程图 2.1.3 查询各点距离 由于图的结构比较复杂，任意两个点之间都可能存在联系。因此无法以数据 元素在存储区中的物理位置来表示元素之间的关系， 但是却可以借助数组的数据 类型表示元素之间的关系。 2.1.4 主函数 循环体用开关语句，该语句的条件值 ck 是当用户选择菜单通过调用主菜单 函数得到，返回值整数作开关语句的条件。根据该值调用相应的各功能函数，同 时设置一个退出程序点，执行完用户的某项功能后继续显示菜单，当返回值为 e
