课程设计报告
课程名称： 数据结构与算法 题目名称： 校园导游系统 学生学院： 数学与计算机科学系 专业班级： 2016级计算机科学与技术本科班 小组组长： 王明 小组成员: 王明 郑双凤 吕运发 指导老师： 熊小颖 老师
2017年10月15日
一、设计目的 3
二、问题描述 3
三、基本要求 3
四、概要设计 3
五、主程序 4
六、测试数据 13
6.1调试程序所用数据
目录
13
6.2程序的调试结果
七、总结
一、设计目的 随着现代社会生活节奏的加快，人们外出旅行以寻求放松的时间越来越多。考虑到游客不可能对所有景点都有所了解，因此可能无法找到游玩景点最省时，最高效的路径，而人工导游成本又过高，故使用C语言，基于《数据结构》中图的相关算法开发了“南昌师范学院导游系统”。 开发本系统目的在于为来访我校的游客提供一条最短游览路径，本系统从实际出发，通过对校园平面图的分析，将其转化为数据并保存在系统中，因此系统提供的路径具有较大的可信性。 二、问题描述
设计校园导游程序，为来访的客人提供服务，为来访我校的游客提供一条在游客当前位置到目的地的最短游览路径，找到游玩景点最省时，最高效的路径。 三、 基本要求
1. 假设有一所校园的平面图，所含景点不小于10个，请选择适当
的坐标来表示出该图上的各个景点。
2. 为来访的客人提供从当前位置到其他景点的最短路径的咨询； 3. 必须具有校园平面图的修改和扩充功能（即某些景点坐标的修改
和景点个数的增加）。 四、 概要设计 算法思路
本设计的重难点在于问题二的解决。利用了弗洛伊德算法函数设计Floyd() 本算法在设计时参考了《数据结构C语言版》一书中有关Floyd算法的介绍，同时借鉴了如今网上流行的设计方式。之所以选择本算法来实现计算最短路径，原因在于本算法容易理解，可以算出任意两个节点之间的最短距离，代码编写简单。但是，本算法缺点在于时间复杂度过高，不适合用于计算大量数据。Floyd算法首先将两景点间路径长度数据存储于数组D[v][w]中，而后使用一个三维数组用于存放最短路径所经过的顶点，接下来使用三重循环判断两景点之间直接路径是否大于间接路径，若大于，则将三维数组中存放的顶点信息更改为简介路径所经过的顶点信息。以上部分完成后，当用于标记输入数据是否合法的flag=1时，输出错误信息，提示用户重新输入，当输入数据合法时，输出以上程序得到结果。
五、 主程序
#include
#define MAX_VERTEX_NUM 100 //最大顶点数 #define MAX_INT 10000 //无穷大 typedef int AdjType; typedef struct{
int pi[MAX_VERTEX_NUM];//存放v到vi的一条最短路径
int end; }PathType;
typedef char VType; //设顶点为字符类型 typedef struct{
VType V[MAX_VERTEX_NUM]; //顶点存储空间 AdjType A[MAX_VERTEX_NUM][MAX_VERTEX_NUM]; //邻接矩阵
}MGraph;//邻接矩阵表示的图
校园导游系统
