数据结构实验预习报告——校园导游系统

Rozbrid

已于 2022-05-26 15:23:16 修改

阅读量984

点赞数

文章标签：图论 java 贪心算法

于 2022-05-26 15:02:05 首次发布

本文链接： https://blog.csdn.net/qq_53841114/article/details/124984315

版权

一、问题描述和基本要求

【问题描述】

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

【基本要求】

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

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

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

【测试数据】

以江苏科技大学长山校区为例。

【实现提示】

一般情况下，校园的道路是双向通行的，可设校园平面图是一个无向网，顶点和边均含有相关信息.

二、问题分析和任务定义

每个地点为一个node，对每一个node赋予顺序，并且用无向图的方式标记，且给两个node之间赋权进行计算最短路径。主要核心算法为Dijkstra算法。

Dijkstra算法详解：https://blog.csdn.net/lbperfect123/article/details/84281300?ops_request_misc=%257B%2522request%255Fid%2522%253A%2522165353775516782395350651%2522%252C%2522scm%2522%253A%252220140713.130102334..%2522%257D&request_id=165353775516782395350651&biz_id=0&utm_medium=distribute.pc_search_result.none-task-blog-2~all~top_positive~default-2-84281300-null-null.142^v10^pc_search_result_control_group,157^v12^control&utm_term=dijkstra%E7%AE%97%E6%B3%95&spm=1018.2226.3001.4187https://blog.csdn.net/lbperfect123/article/details/84281300?ops_request_misc=%257B%2522request%255Fid%2522%253A%2522165353775516782395350651%2522%252C%2522scm%2522%253A%252220140713.130102334..%2522%257D&request_id=165353775516782395350651&biz_id=0&utm_medium=distribute.pc_search_result.none-task-blog-2~all~top_positive~default-2-84281300-null-null.142%5Ev10%5Epc_search_result_control_group,157%5Ev12%5Econtrol&utm_term=dijkstra%E7%AE%97%E6%B3%95&spm=1018.2226.3001.4187

三、逻辑设计

此为长山校区平面图

设置10个地点

序号	地点名称
0	文体中心
1	三号组团
2	西食堂
3	笃学楼
4	西操场
5	文理大楼
6	北门
7	云书山
8	图书馆
9	东食堂

有权无向图

四、物理设计

Site[] sites = new Site[11];//以地点代号循序存放地点
ArrayList<String> arrSites = new ArrayList<>();
double[][] matrix = new double[11][11];//用来存放地点间的路径长度(对角线为0，不存在为INFINITY)
static {//设计校园平面图}
query(String siteName) {//根据地点名称查询地点信息}
findShortestPath(String path) {//找到两地点间的最短路径}
dijkstra(int start, int end) {//使用Dijkstra算法找到两地间的最短路径}
printDijkstra(int[] parent, double[] distant, int start, int end) {//打印出最短路径}
main(String[] args) {//调用各种函数以及设计交互界面}
class Site {//地点类}