明净日夜
课程论文（设计）
2011-2012 学年第2学期
课程名称：数据结构课程设计课程性质：实践课专业班级：考核方式：考查学生姓名：学 号：学 时：教师姓名： 1周
自评分：95分 评语及评分
目 录
1. 作业内容·····················································1 2. 基本思路·····················································1 2.1 本校10个景点···············································1 2.2 图的初始化··················································2 2.3 图的遍历····················································2 2.4 求最短路径··················································3 3.系统流程······················································4 3.1 系统的简单说明··············································4 3.2 系统流程图··················································5 4. 系统运行效果图···············································5 4.1 校园导游界面················································5 4.2 华农校园地图················································6 4.3 景点的相关信息查询··········································6 4.4 任意两个景点间的最短路径····································7 4.5 退出校园导游系统············································8 5.总结··························································9 6.参考文献······················································10
1. 作业内容
设计一个校园导游程序，为来访客人提供各种信息查询任务。基本要求： （1）设计你所在学校的校园平面图，所含景点不少于10个。以图中顶点表示校内各景点，存放景点名称、代号、简介信息，以边表示路权，存放路径长度等相关信息。
（2）为来访客人提供图中任意景点相关信息的查询
（3）为来访客人提供图中任意景点的问路查询，即查询任意两个景点之间的一条最短的简单路径。
2. 基本思路
要完成对整个导游图系统的功能实现，需要对的每一项功能都有清楚的设想和认识，了解并明确每一项功能的实现需要解决的问题，选择正确并且高效的算法把问题逐个解决，最终实现程序的正确调试运行。有以下设计思路：
（1）.结合本校的实际情况，选出10个景点；
（2）.人为手工为选出的10个景点赋上相关信息（名称、代号、简介信息、以及路权等等）；
（3）.根据选出来的10个景点用邻接矩阵存储校园图。 （4）.依照景点的相关信息创建校园图。
（5）.把纸质上的内容，利用C++编程语言编写查找景点相关信息的程序。 （6).根据人为赋值的路权，迪杰斯特拉算法计算任意两点之间的最短路径。 （7）.综上所诉，用一个主函数把这些板块合成，生产一个菜单界面呈现在用户面前。
为此，可把系统分为以下几个核心：图的初始化、图的遍历、求最佳路线。 2.1 选出本校10个景点
结合华南农业大学实际情况，我选出以下10个景点，从1到10编号： 编号 1 5 9
名称 校史馆 东区运动场 老校门 编号 2 6 10 名称 红满堂 树木园 黑山运动场 编号 3 7 名称 行政楼 竹园 编号 4 8 名称 西园 新校门 1
2.2 图的初始化
由于邻接矩阵特殊的存储方式，它非常便于快速的查找两个顶点之间的边上的权值。所以，图采用带权的邻接矩阵存储。
决定了图的存储方式后，以华南农业大学10个景点的游览地图作为蓝本，把校园地图抽象化成顶点与边构成的图形式，如图2.2所示，途中数字代表线的权值。
2.3 图的遍历
图的遍历是图中最基本的操作。图的遍历是指从图中某一顶点出发，对图中所有顶点访问一次且仅访问一次。导游图需要把每条路径的信息都向游客展示，就需要读取每两个顶点间的路径信息。由于采用了带权的邻接矩阵存储结构进行存储，所以需要针对这一存储结构对路线进行遍历操作。其遍历算法如图2.3所示。
2
