数据结构课程设计最终版.docVIP

PAGE 成绩评定 学 号 姓 名 任务分工 成绩 20131614310048 钟海梅 整理思路，程序和算法的设计，调试和修改程序 20131614310003 陈雪梅 整理思路，程序和算法的设计，调试和修改程序 20131614310027 舒小霞 搜集资料，总结 数据结构与算法 课程设计报告 设计题目: 校园平面图 院 系： 信息科学技术学院 专业班级： 13级信息与计算科学 学生姓名： 钟海梅 20131614310048 陈雪梅 20131614310003 舒小霞 20131614310027 2016年12月20日 目 录 TOC \o 1-3 \h \z \u HYPERLINK \l _Toc204154444 1.设计内容 PAGEREF _Toc204154444 \h 1 HYPERLINK \l _Toc204154445 1.1问题描述 PAGEREF _Toc204154445 \h 1 HYPERLINK \l _Toc204154446 1.2设计要求 PAGEREF _Toc204154446 \h 1 HYPERLINK \l _Toc204154447 1.3开发环境 PAGEREF _Toc204154447 \h 1 HYPERLINK \l _Toc204154448 1.4设计思路 PAGEREF _Toc204154448 \h 1 HYPERLINK \l _Toc204154449 2.设计流程 4 HYPERLINK \l _Toc204154450 2.1需求分析 4 HYPERLINK \l _Toc204154451 2.2校园平面图 4 HYPERLINK \l _Toc204154452 2.3程序功能 6 HYPERLINK \l _Toc204154453 2.4程序设计 6 HYPERLINK \l _Toc204154454 2.5程序运行 9 HYPERLINK \l _Toc204154455 3.总结与心得 12 HYPERLINK \l _Toc204154458 4.参考文献 12 HYPERLINK \l _Toc204154459 附 录 12 1、设计内容 1.1问题描述 在地图上从一个地点到另一个地点，给出一条最短路径，各个地点之间不能重复，最终给出一条路径的方案和长度。 1.2 设计要求 （1）将地图作为带权无向图，顶点表示学校的各个地点，边表示各地点之间的路，边上的权值表示距离。 （2）将地图信息存入一文件中，程序运行时可自动读入文件建立相关数据结构。 （3）按操作要求显示对应的最短路径和长度。 1.3开发环境 本程序开发环境为 Visual Studio 2010 1.4设计思路? 校园平面图模型是由场所和场所之间的路径组成的，所以这完全可以用数据结构中的图来模拟。用图的结点代表场所，用图的边代表场所之间的路径，结点值代表场所信息，边的权值代表场所间的距离。结点值及边的权值用顺序表存储，所以需要设计一个顺序表类。本系统需要查询场所信息和求一个场所到另一个场所的最短路径长度及路线为方便操作，所以给每个场所一个代码用结构体类型实现。计算路径长度和最短路线时可用狄克斯特拉Dijkastra算法实现。最后用switch选择语句选择执行浏览推荐路线或查询最短路径并且主页面会简单描述场所的信息。 程序的主要算法是狄克斯特拉Dijkastra算法，其基本描述如下（可参考课本）： 首先求出长度最短的一条最短路径，然后参照它求出长度次短的一条最短路径，以此类推，直到从定点v到其他各顶点的最短路径全部求出为止。 1000 100 0 1000 1000 3041 30 4 110 500 600 32 3 2 20 20 作为一个例子，考虑如图所示的有向带权图。边上的数字即为该边的长度，并设原点为顶点0。按照Dijkastra算法，首先引用其邻接矩阵的第0行，求出从顶点0到其他各定点最短路径的初步结果；以后逐步求最短路径的过程如下图所示。 源点 终点 最短路径 路经长度 V0 V1 (v0,v1) 10 V2 - (v0,v1,v2) (v0,v3,v2) - 60 50 V3 (v0,v3)