[课设论文]校园导航问题.doc

课程设计（论文）
课程名称： 数据结构
题 目： 校园导航系统
院 （系）： 信息与控制工程学院
专业班级： 计算机科学与技术0902
姓 名： 宫向阳
学 号： 090620219
指导教师： 祁飞
年 月 日
摘 要
数据结构是实践性很强的课程，任何程序都要借助于合适的数据结构才能完成，所以掌握数据结构的应用对学生而言是至关重要的。本程序设计的是本校的校园导航系统，具有四个基本功能：校园平面简图查询、各景点查询、路径查询、最短路径查询，借助C++中所学的EZWIN实现图形用户界面，利用数据结构中图的知识构成程序的框架，最短路径查询中采用了“贪婪算法”，为用户提供任意两景点之间的最短路径，通过灵活运用所学的数据结构—queue来实现两点之间最短路径的存储。
关键字：数据结构，图，EZWIN，贪婪算法，queue
西安建筑科技大学课程设计（论文）任务书
专业班级： 计算机0902 学生姓名： 宫向阳 指导教师（签名）：
一、课程设计（论文）题目
校园导航问题
说明：设计学校的平面图，至少包括10个以上的场所，每两个场所间可以有不同的路，且路长也可能不同。找出从任意场所到达另一场所的最佳路径。
二、本次课程设计（论文）应达到的目的
数据结构是实践性很强的课程。课程设计是加强学生实践能力的一个强有力手段。课程设计要求学生在完成程序设计的同时能够写出比较规范的设计报告。严格实施课程设计这一环节，对于学生基本程序设计素养的培养和软件工作者工作作风的训练，将起到显著的促进作用。
本题目要达到目的：熟练掌握图论中的最短路径的实现。
三、本次课程设计（论文）任务的主要内容和要求（包括原始数据、技术参数、设计要求等）
输入数据：10个以上场所的编号；每两个场所间的路径和路长；
1. 自己设定每两个场所间的路径和路长（可能不同）；
2. 图示化输出任意两个场所间的最佳路径（最短路径）。
3. 优化界面设计。
四、应收集的资料及主要参考文献：

由于本课程没有安排“课内上机”学时，因此，在课程设计之前必须自己已经上机练习了“图”的基本操作。
参考文献：
1. Robert L. Kruse，Data Structures And Program Design in C++，高等教育出版社，.
2. 严蔚敏等编著，数据结构（C语言版），清华大学出版社，；
3. 赵文静等编著，数据结构与算法，科学出版社，；
4．孙鑫等编著，VC++深入详解，电子工业出版社，；
五、审核批准意见
教研室主任（签字）
目 录
西安建筑科技大学课程设计（论文）任务书 3
1、需求分析 5
2、概要设计 5
3、详细设计 8
4、调试分析 13
5、使用说明 17
6、课设总结 17
7、结束语 18
8、致谢 18
9、参考文献 19
10、附页（主要源代码） 19
1、需求分析
软件是简单的西安建筑科技大学校园导航系统，需具备两个基本功能：一、景点之间的路径查询，为用户提供任意两个景点之间的所有路径；二、景点之间的最短路径查询，为用户提供任意两个景点之间的最短路径。具体要求包括：①、输入数据包括10个以上场所的编号；每两个场所间的路径和路长；②、 自己设定每两个场所间的路径和路长（可能不同）；③、 图示化输出任意两个场所间的最佳路径（最短路径）；④优化界面设计。
2、概要设计
软件中的功能四（最短路径）中应用了数据结构中所学的图的相关知识，1、利用邻接矩阵来存储所选的12个景点之间的相关信息（两点之间的距离，将那些没有相关联的点的值置为无穷大，程序中设为1000）。2、最短路径的核心是贪婪算法，初始化 ，用一个变量表示一个点的状态（有没有被访问过，如果访问过，则将其置为true，如果没有被访问过，则将其置为false），然后确定图的源点，选择剩余所有点中距此点距离最小的点，将其包进去，然后