校园导航问题课程设计论文

《校园导航问题课程设计论文》由会员上传分享，免费在线阅读，更多相关内容在行业资料-天天文库。

1、摘要校园导航要求每两个场所间可以有不同的路，且路长也可能不同，找出从任意场所到达另一场所的最佳路径(最短路径)。要用“邻接矩阵”来存储各点间的距离，然后用Dijkstra算法求出最短路径。所以采用工程思想，将系统共分以下五个模块：节点数据结构类型、创建导航图函数、最短路径导航函数、查询函数声明、主菜单。关键字校园导航查询Dijkstra算法19目录摘要1校园导航问题61问题分析与任务定义：62数据结构描述与定义73Dijkstra算法流程图84程序运行调试95结论11参考文献12附录：1219校园导航问题1问题分析与任务定义：本课程设计的内容为设

2、计学校的平面图,至少包括10个以上的场所,每两个场所间可以有不同的路,且路长也可能不同,找出从任意场所到达另一场所的最佳路径(最短路径)。如图1,图中已标出主要路线，各路线的长度如表1中所示。显然要解决这一问题要用“邻接矩阵”来存储各点间的距离，然后用Dijkstra求出最短路径。7图书馆1会堂8主楼　0分析测试中心3二教学楼6足球场410号楼2一教学楼9学生食堂5篮球场19图1：校园平面图0←→1:2000←→3:200←→7:1000←→8:1001←→7:501←→8:502←→4:3502←→5:2002←→6:1002←→9:1503←

3、→4:2903←→6:2003←→9:3004←→5:2004←→9:505←→9:1006←→7:2007←→8:100表1：各景点距离单位：米（m）2数据结构描述与定义1.节点数据结构类型#defineMax20000#defineNUM10typedefstructArcCell{intadj;/*相邻接的景点之间的路程*/}ArcCell;/*定义边的类型*/typedefstructVertexType{intnumber;/*景点编号*/char*sight;/*景点名称*/char*info;/*景点描述*/}VertexType;

4、/*定义顶点的类型*/typedefstruct{VertexTypevex[NUM];/*图中的顶点，即为景点*/ArcCellarcs[NUM][NUM];/*图中的边，即为景点间的距离*/intvexnum,arcnum;/*顶点数，边数*/}MGraph;/*定义图的类型*/2.创建导航图函数voidCreateUDN(intv,inta)函数描述：主要将每个节点进行命名、每个顶点到其他所有定点的路径值用邻接矩阵进行存储。例：G.vex[0].sight=“分析测试中心”；作用：使0号定点命名为“分析测试中心”；19G.vex[0].in

5、fo=“老师办公和学生做实验”；作用：0号描述为“老师办公和学生做实验”；G.arcs[0][1].adj=G.arcs[1][0].adj=200；作用：使0号节点到1号节点的路径赋值为200，应为是无向图，所以1号节点到0号节点的路径长度也应赋值为200。3.最短路径导航函数voidShortestPath(intnum)函数描述：用Dijkstra算法求无向网G的V0定点到其余定点V的最短路径P[v]及其带权长度D[v]。若P[v][w]为True，则w是从V0到V当前求得最短路径上的顶点。Final[v]为True当且仅当V∈S，即已经求

6、得从V0到V的最短路径。4.查询函数声明charSearchMenu()voidHaMiTonian(int)函数描述：哈密尔顿图的遍历。5.主菜单charMenu()描述;显示导航图中的所有导航节点，能够快速方便的对各个地点进行导航。3Dijkstra算法流程图194程序运行调试本程序用microsoftvisualc++6.0运行结果如下：主界面：19景点路径查询景点信息查询19推荐参观路线6结论本系统实现了在大量的校园景点中任意指定两个景点就能给出最短路径。并且设计save()保存函数，和load()下载函数，分别用来保存创建的导航数据，和

7、下载其它导航数据，这样这个系统才能更加实用，voidcreateadj()原来的函数原型为arcnode*createdj()函数中用链表结构把adjmatrix[][]的数据都保存其中，这样就能实现数据的保存，但随之要把Ｄijkstra中的adjmatrix[][]转换成用arcnode指针的形式进行表示，因为只有这样，下载后的数据才能使用。19参考文献［1］《数据结构》（C语言版），严蔚敏，清华大学出版社，2005．［2］《算法设计与分析》，王晓东主编，清华大学出版社，2005［3］汪诗林等译，《数据结构、算法与应用》，（美）SartajSa

8、hni著，机械工业出版社，1999［4］《数据结构与算法分析》，CLIFFORDA.SHAFFER著，张铭、刘晓丹译，电子工业出版社，1