数据结构课程设计——校园导游图.doc

景德镇陶瓷学院
信息工程学院
班 级：12计科（2）班
学 号：6
姓 名：乐升平
指导老师：林卫中
时 间：2014年6月18号
题 目：校园导游图
校园导游图
、需求分析：
需求：
（1）将导游图看作一张带权无向图，顶点表示公园的各个景点，边表示各景点之间的道路，边上的权值表示距离。为此图选择适当的数据结构。
（2）把各种路径都显示给游客，由游客自己选择游览路线。
（3）画出景点分布图于屏幕上。
分析：
完成对整个导游图系统的功能实现，需要对的每一项功能都有清楚的设想和认识，了解并明确每一项功能的实现需要解决的问题，选择正确并且高效的算法把问题逐个解决，最终实现程序的正确调试运行。有以下设计思路：
（1）.结合本校的实际情况，选出10个景点；
（2）.人为手工为选出的10个景点赋上相关信息（名称、代号、简介信息、以及路权等等）；
（3）.根据选出来的10个景点用邻接矩阵存储校园图。
（4）.依照景点的相关信息创建校园图。
（5）.把纸质上的内容，利用C++编程语言编写查找景点相关信息的程序。
（6).根据人为赋值的路权，迪杰斯特拉算法计算任意两点之间的最短路径。
（7）.综上所诉，用一个主函数把这些板块合成，生产一个菜单界面呈现在用户面前。
、设计与实现：
选出本校10个景点
结合景德镇陶瓷学院实际情况，我选出以下10个景点，从1到10编号：
编号
名称
编号
名称
编号
名称
编号
名称
1
研究生楼
2
二食堂
3
10#宿舍
4
主教学楼
5
毕业礼堂
6
主阶
7
一食堂
8
A系列楼
9
B系列楼
10
图书馆
11
科艺楼
12
科阶
13 篮球场 14 田径场 15 游泳池 16 体育馆
17 翠湖 18 校门口
图的初始化
由于邻接矩阵特殊的存储方式，它非常便于快速的查找两个顶点之间的边上的权值。所以，图采用带权的邻接矩阵存储。
决定了图的存储方式后，以华南农业大学18个景点的游览地图作为蓝本，把校园地图抽象化成顶点与边构成的图形式，如图所示
10#宿舍
二食堂
研究生楼
研究生楼 二食堂 10
毕业礼堂
主教学楼
主教学楼 毕业礼堂
一食堂
主阶
主阶 一食堂
B系列楼
科阶
科艺楼
图书馆
A 系列楼楼
A系列楼 B系列楼 图书馆 科艺楼 科阶
篮球场

篮球场

田径场
田径场

游泳池
游泳池
体育馆

翠湖
体育馆
翠湖
校门口

校门口
、模块的划分
含有四个模块：（1）陶院地图信息
（2）陶院景点信息
（3）查找两点间最短路径
（4）退出
模板功能
（1）将陶院的地图