《数据结构》项目2：校园导游咨询 预习实验报告

目录

一、问题描述

二、基本要求

三、重难点分析

1.最短路径算法：

2.设计思路

四、数据类型定义声明

1.景点（scene）类：声明景点相关变量。

2.路径（route）类：声明各景点路径相关变量。

3.主（main）类：声明菜单函数，调试系统程序。

五、编程语言

六、开发工具/平台

---

一、问题描述

设计一个校园导游程序,为来访的客人提供各种信息查询服务。

二、基本要求

（1）设计你所在学校的校园平面图，所含景点不少于10个。以图中顶点表示校内各景点，存放景点名称、代号、简介 等信息；以边表示路径，存放路径长度等相关信息。

（2）为来访客人提供图中任意景点相关信息的查询。

（3）为来访客人提供图中任意景点的问路查询，即查询任意两个景点之间的一条最短的简单路径。

三、重难点分析 1.最短路径算法：

1-1.floyd算法

floyd算法只有五行代码，代码简单，三个for循环就可以解决问题，所以它的时间复杂度为O(n^3)，可以求多源最短路问题。

1-2.dijkstra

迪杰斯特拉(Dijkstra)算法是典型最短路径算法，用于计算一个节点到其他节点的最短路径。
它的主要特点是以起始点为中心向外层层扩展(广度优先遍历思想)，直到扩展到终点为止。

2.设计思路

先创建邻接数组类型无向图，再呈现用户界面，通过switch语句让用户选择功能，然后调用相应函数来实现功能。

四、数据类型定义声明 1.景点（scene）类：声明景点相关变量。

成员变量：

景点名称（String）、景点编号（int）。

2.路径（route）类：声明各景点路径相关变量。

成员变量：

路径长度（int）、景点数量（int）、路径数量（int）。

3.主（main）类：声明菜单函数，调试系统程序。

成员函数：

菜单函数menu（）、景点列表函数sceneList（）。

五、编程语言

JAVA

六、开发工具/平台

IDEA