数据结构课程设计实验

admin 管理员组

文章数量: 1087652

数据结构课程设计实验

大家好呀，平平无奇大学生一枚，到期末了，各种报告接踵而至😭，应课程要求，来水 认真写一篇实验开发博客，记录我的开发过程，望各位大佬给出指导意见

文章目录

• 一、引言
• • 1.1 背景和目标
  • 1.2 需求
  • 1.3 设计要求
• 二、系统设计和准备工作
• • 2.1 模块设计思路和实现方式
• 三、实现过程
• • 3.1 参赛队伍信息管理模块
  • 3.2 二叉排序树模块
  • 3.3 查询功能模块：
  • 3.4 决赛叫号系统模块：
  • 3.5 校园导游程序模块：
• 四结果演示：

一、引言

1.1 背景和目标

1. 背景
   中国大学生计算机设计大赛是我国高校面向本科生的计算机应用设计大赛，大赛旨在激发学生学习计算机知识和技能的兴趣与潜能，提高学生运用信息技术解决实际问题的综合能力。通过大赛这种计算机教学实践形式，可展示师生的教与学成果，最终以赛促学，以赛促教，以赛促创。该赛事在历届学生中影响力较大，参与者众多，请结合2021届省赛参赛的数据，**借助数据结构课程所学的相关知识，通过对数据的处理和分析，熟悉数据结构设计及数据处理在信息管理系统中应用的重要性。**赛事相关数据存储在文本文件和excel文件中，相应的文件信息说明如表1所示。其中，各个文件中不同的数据项之间均使用#分隔，下图中给出了文件team.txt中参赛信息的对应数据示例。
   
2. 目标
   1. 熟练掌握线性表、栈、队列、串、数组、树和图等基本数据结构的逻辑特性和存储表示方法；熟练掌握各种基本数据结构的基本算法和其应用；熟练掌握问题分析、数据结构设计、程序设计的基本技能和技术。
   2. 能够综合运用数据结构与算法和相关的数学等理论知识对复杂工程中的算法问题进行抽象、分析和建模；能够依据工程实际问题的需求合理组织数据、并在计算机中有效地存储数据；能够针对复杂工程中的算法问题，设计出比较合理的解决方案，利用具体的编程语言实现解决方案，并具有一定的创新思维能力。
   3. 具有良好的工程素养和职业素养，诚信守法，能够坚持职业操守和道德规范；具有精益求精的工匠精神、创新精神和探索未知终身学习的意识；具有科技报国的社会责任感、使命感和爱国主义情操。

1.2 需求

本次课程设计要求协助中国大学生计算机设计大赛江苏省组委会，设计一款赛事管理系统，实现赛务相关的数据管理及信息服务，该系统能够为省级赛事管理

1. 能够管理各参赛队的基本信息（包含参赛队编号，参赛作品名称，参赛学校，赛事类别，参赛者，指导老师），赛事类别共11项（参见大赛官网jsjds.blcu.edu）；包括增加、删除、修改参赛队伍的信息。
2. 从team.txt中读取参赛队伍的基本信息，实现基于二叉排序树的查找。根据提示输入参赛队编号，若查找成功，输出该赛事类别对应的基本信息（参赛作品名称、参赛学校、赛事类别、参赛者和指导老师信息），同时，输出查找成功时的平均查找长度ASL；否则，输出“查找失败！”。
3. 能够提供按参赛学校查询参赛团队（或根据赛事类别查询参赛团队），即，根据提示输入参赛学校名称（赛事类别），若查找成功，输出该学校参赛的（该赛事类别的）所有团队的基本信息，输出的参赛团队按赛事类别有序输出。（排序算法可从选择排序、插入排序、希尔排序、归并排序、堆排序中任意选择，并为选择算法的原因做出说明。）
4. 为省赛现场设计一个决赛叫号系统。所有参赛队按赛事组织文件中的赛事类别分到9个决赛室，决赛室按顺序叫号，被叫号参赛队进场，比赛结束后，下一参赛队才能进赛场。请模拟决赛叫号系统，演示省赛现场各决赛室的参赛队进场情况。（模拟时，要能直观展示叫号顺序与进场秩序一致）
5. 赛事系统为参赛者提供赛地的校园导游程序,为参赛者提供各种路径导航的查询服务。以我校长山校区提供比赛场地为例，（请为参赛者提供不少于10个目标地的导航。可为参赛者提供校园地图中任意目标地（建筑物）相关信息的查询；提供任意两个目标地（建筑物）的导航查询，即查询任意两个目的地（建筑物）之间的一条最短路径。

1.3 设计要求

1）赛事数据要求存入文件（txt或excel）并能读入查询；
2）赛地目的地查询,需提供目的地（建筑物）名称、代号、简介、两地之间路径长度等信息；
3）输入数据形式和范围：赛事相关数据可从键盘输入，或自文件导入。
4）界面要求：交互设计要合理，每个功能可以设计菜单，用户根据提示，完成相关功能的要求。

二、系统设计和准备工作

2.1 模块设计思路和实现方式

参赛队伍信息管理模块：

• 增加参赛队伍信息：收集参赛队伍的基本信息，并将其添加到系统中。
• 删除参赛队伍信息：根据参赛队编号删除相应的参赛队伍信息。
• 修改参赛队伍信息：根据参赛队编号选择要修改的参赛队伍，并允许更新相关信息。

二叉排序树模块：

• 从文件(team.txt)中读取参赛队伍的基本信息，并构建二叉排序树数据结构。
• 实现基于二叉排序树的查找功能：根据参赛队编号在二叉排序树中进行查找，并返回对应赛事类别的基本信息。
• 计算平均查找长度（ASL）：统计查找过程中访问节点的总数，计算平均查找长度。

查询功能模块：

• 按参赛学校查询参赛团队：根据输入的参赛学校名称，输出该学校参赛的所有团队的基本信息。
• 按赛事类别查询参赛团队：根据输入的赛事类别，输出该类别的所有团队的基本信息。
• 排序功能：根据赛事类别对参赛团队进行排序，可选择选择排序、插入排序、希尔排序、归并排序或堆排序，需说明选择算法的原因。

决赛叫号系统模块：

• 设计决赛叫号系统：根据赛事组织文件中的赛事类别将参赛队伍分配到9个决赛室。
• 模拟叫号和进场过程：按顺序叫号，展示叫号顺序与参赛队伍进场秩序的一致性。

校园导游程序模块：

• 提供目标地导航信息查询：根据输入的目标地名称，查询并输出相关信息，包括名称、代号、简介等。
• 最短路径查询：根据输入的两个目标地名称，计算并输出它们之间的最短路径长度。

三、实现过程

3.1 参赛队伍信息管理模块

1. 题目要求：能够管理各参赛队的基本信息（包含参赛队编号，参赛作品名称，参赛学校，赛事类别，参赛者，指导老师），赛事类别共11项（参见大赛官网jsjds.blcu.edu）；包括增加、删除、修改参赛队伍的信息。
2. 需求分析：

• 从team.txt文件中读取参赛队伍的基本信息。
• 实现增加参赛队伍信息功能。
• 实现删除参赛队伍信息功能。
• 实现修改参赛队伍信息功能。

3. 实现过程分析：

• 创建Team类：定义了队伍的属性（队伍编号、参赛作品名称、参赛学校、赛事类别、参赛者、指导教师），以及相应的getter和setter方法。

import java.util.List;/*** 队伍类* 存储队伍的基本信息*/
public class Team {//参赛队伍编号private String teamNumber;// 参赛作品名称private String projectName;// 参赛学校private String school;// 赛事类别private String category;// 参赛者private String participants;// 指导老师private  String instructor;public Team(String teamNumber, String projectName, String school, String category, String participants, String instructor) {this.teamNumber = teamNumber;this.projectName = projectName;this.school = school;this.category = category;this.participants = participants;this.instructor = instructor;}public String getTeamNumber() {return teamNumber;}public void setTeamNumber(String teamNumber) {this.teamNumber = teamNumber;}public String getProjectName() {return projectName;}public void setProjectName(String projectName) {this.projectName = projectName;}public String getSchool() {return school;}public void setSchool(String school) {this.school = school;}public String getCategory() {return category;}public void setCategory(String category) {this.category = category;}public String getParticipants() {return participants;}public void setParticipants(String participants) {this.participants = participants;}public String getInstructor() {return instructor;}public void setInstructor(String instructor) {this.instructor = instructor;}@Overridepublic String toString() {return "Team{" +"teamNumber='" + teamNumber + '\'' +", projectName='" + projectName + '\'' +", school='" + school + '\'' +", category='" + category + '\'' +", participants='" + participants + '\'' +", instructor='" + instructor + '\'' +'}';}
}

• 创建TeamManager类：包含了队伍管理和控制的功能。

import java.io.*;
import java.util.ArrayList;
import java.util.List;/*** 队伍管理类* 能够管理参赛队伍的基本信息，包括对进行信息的增删改*/
public class TeamManager {// 用于存储每个队伍的信息private List<Team> teams;public TeamManager() {this.teams = new ArrayList<>();}// 从txt文件中读取队伍信息并存储到列表中public void loadTeamsFromFile(String filePath,String charset  ) {CommonUtils.initTeamsList(teams,filePath,charset);}public void printTeams() {for (Team team : teams) {System.out.println(team);}}}

• loadTeamsFromFile方法：从txt文档中读取队伍信息，并将其存储在teamList列表中。

  public void loadTeamsFromFile(String filePath,String charset  ) {CommonUtils.initTeamsList(teams,filePath,charset);}

说明：因为后续要用到读取和写入txt的方法，所以进行了封装实现了复用😊

import java.io.BufferedReader;
import java.io.FileInputStream;
import java.io.IOException;
import java.io.InputStreamReader;
import java.util.List;public class CommonUtils {public static void initTeamsList(List<Team> teams , String filePath, String charset  ) {try (BufferedReader br = new BufferedReader(new InputStreamReader(new FileInputStream(filePath), charset))) {String line;// 跳过第一行信息br.readLine();while ((line = br.readLine()) != null) {String[] data = line.split("#");if (data.length == 6) {String teamNum = data[0].trim();String projectName = data[1].trim();String school = data[2].trim();String category = data[3].trim();String participants = data[4].trim();String instructor = data[5].trim();Team team = new Team(teamNum, projectName, school, category, participants, instructor);teams.add(team);}}System.out.println("队伍信息读取完毕");} catch (IOException e) {System.out.println("队伍信息有误: " + e.getMessage());}}
}
public static void saveTeamsToFile(List<Team> teams ,String filePath) {try {FileOutputStream fos = new FileOutputStream(filePath);OutputStreamWriter osw = new OutputStreamWriter(fos, "Utf-8");BufferedWriter writer = new BufferedWriter(osw);writer.write("参赛队编号\t#\t参赛作品名称\t#\t参赛学校\t#\t赛事类别\t#\t参赛者\t#\t指导教师"+ "\n");for (Team team : teams) {writer.write(team.getTeamNumber() + " \t# \t" +team.getProjectName() + " \t# \t" +team.getSchool() + " \t#\t " +team.getCategory() + "\t #\t " +team.getParticipants() + "\t # \t" +team.getInstructor() + "\n");}writer.close();} catch (IOException e) {e.printStackTrace();}}

• addTeam方法：添加队伍到teamList列表中。

 public void addTeam(Team team,String filePath) {teams.add(team);CommonUtils.saveTeamsToFile(teams,filePath);}

• deleteTeam方法：根据队伍编号删除相应的队伍信息。

  public void deleteTeam(String teamNum,String filePath) {// 方法说明 判断是否满足后面的添加如果满足就进行删除 参数传入的是Lambda表达式teams.removeIf(team -> team.getTeamNumber().equals(teamNum));CommonUtils.saveTeamsToFile(teams,filePath);}

• updateTeam方法：根据队伍编号选择要修改的队伍，并允许更新相关信息（赛事类别、参赛者、指导教师）。

 public void updateTeam(String teamNum, String newCategory, String newParticipants, String instructor,String filePath) {for (Team team : teams) {if (team.getTeamNumber().equals(teamNum)) {team.setCategory(newCategory);team.setParticipants(newParticipants);team.setInstructor(instructor);CommonUtils.saveTeamsToFile(teams,filePath);break;}}}

• printTeams方法：打印所有队伍的基本信息。

 public void printTeams() {for (Team team : teams) {System.out.println(team);}}

4. main方法：测试以上功能，加载队伍数据并进行相关操作。

 public static void main(String[] args) {String filePath = "team.txt";String charset = "Utf-8"; // 文件编码格式TeamManager teamManager = new TeamManager();teamManager.loadTeamsFromFile(filePath,charset);teamManager.printTeams();// 添加队伍信息Team newTeam = new Team("2023001234", "New Project", "New School", "New Event", "New Leader", "New Advisor");teamManager.addTeam(newTeam,filePath);//删除某个队伍信息teamManager.deleteTeam("2021009290",filePath);// 修改队伍信息Team updatedTeam = new Team("2021001018", "大数据", "江科大", "666", "小王", "大王");teamManager.updateTeam(updatedTeam,filePath);}

3.2 二叉排序树模块

1. 题目要求：根据参赛队伍的基本信息，实现基于二叉排序树的查找。根据提示输入参赛队编号，若查找成功，输出该赛事类别对应的基本信息（参赛作品名称、参赛学校、赛事类别、参赛者和指导老师信息），同时，输出查找成功时的平均查找长度ASL；否则，输出“查找失败！”。
2. 需求分析

• 输入：参赛队编号。
• 输出：如果查找成功，则输出该队伍的基本信息（参赛作品名称、参赛学校、赛事类别、参赛者和指导老师信息），同时输出查找成功时的平均查找长度（ASL）。如果查找失败，则输出"查找失败！"。

3. 过程分析：

• 根据参赛队伍的基本信息，构建一个二叉排序树。

  // 用于记录查找操作过程中遍历节点的数量private static int searchCount = 0;// 节点内部类static class Node {//编号int key;Team team;Node left, right;Node(int key, Team team) {this.key = key;this.team = team;left = right = null;}}//根节点Node root;// 将新队伍插入二叉搜索树void insert(int key, Team team) {root = insertRec(root, key, team);}// 递归辅助函数，将队伍插入二叉搜索树Node insertRec(Node root, int key, Team team) {if (root == null) {root = new Node(key, team);return root;}if (key < root.key)root.left = insertRec(root.left, key, team);else if (key > root.key)root.right = insertRec(root.right, key, team);return root;}

关于构建二叉树方法实现的说明：

• 首先判断二叉搜索树是否为空，如果为空，则创建一个新的节点，该节点的参赛队编号为 key，队伍信息为 team，然后将该节点作为根节点返回。
• 如果二叉搜索树不为空，通过递归的方式将队伍插入到正确的位置：
  • 若 key 小于当前节点的参赛队编号，则递归调用 insertRec 函数，将队伍插入到当前节点的左子树中，并更新左子节点的链接。
  • 若 key 大于当前节点的参赛队编号，则递归调用 insertRec 函数，将队伍插入到当前节点的右子树中，并更新右子节点的链接。
• 最后，返回根节点。

• 在二叉排序树中查找指定参赛队编号的队伍，如果查找成功，输出该队伍的基本信息和平均查找长度（ASL）如果查找失败，输出"查找失败！"。

 // 根据参赛队编号搜索队伍并返回相应的队伍信息Team search(int key) {Node result = searchRec(root, key);if (result != null) {System.out.println("查找成功！");return result.team;} else {System.out.println("查找失败！");return null;}}// 递归辅助函数，根据参赛队编号搜索队伍Node searchRec(Node root, int key) {if (root == null || root.key == key)return root;if (key < root.key)return searchRec(root.left, key);return searchRec(root.right, key);}/****  // 计算并返回平均查找长度（ASL）*/public double getASL() {if (root == null) return 0;// 存储每一层的元素数量, root!=null, 则首层必然有1个元素int levelSize = 1;int lever = 1; // 树的层数int count = 0; // 存储结点的数量int denominator = lever*levelSize;Queue<Node> queue = new LinkedList<>();queue.offer(root);while (!queue.isEmpty()) {Node node = queue.poll();count++;levelSize--;if (node.left != null) {queue.offer(node.left);}if (node.right != null) {queue.offer(node.right);}if (levelSize == 0) { // 即将要访问下一层lever++;levelSize = queue.size(); // 下一层的元素数量denominator+=lever*levelSize;}}return (double) denominator/count;}

4. 测试功能

// 二叉排序树BinarySearchTree bst = new BinarySearchTree();List<Team> teams = teamManager.getTeams();for (Team team : teams) {bst.insert(Double.parseDouble(team.getTeamNumber()), team);}// 提示用户输入参赛队编号进行查找(!! 从键盘输入）double searchTeamId = 2021001018; // 示例参赛队编号Team result = bst.search(searchTeamId);if (result != null) {System.out.println(result);double asl = bst.getASL(BinarySearchTree.searchCount, 1);System.out.println("平均查找长度（ASL）：" + asl);}

5. 小结：

• 选用二叉排序树作为数据结构来实现队伍的查找操作。二叉排序树具有以下特点：
  • 每个节点的左子树的所有节点值都小于该节点的值，而右子树的所有节点值都大于该节点的值，符合队伍编号的大小关系。
  • 可以通过比较节点值来进行快速查找，减少查找时间复杂度。
  • 二叉排序树的平均查找长度（ASL）较小，适合用于查找操作。
• 通过使用二叉排序树，我们可以高效地实现参赛队伍的查找操作。二叉排序树的特性使得查找过程具有较低的时间复杂度，并且可以根据查找的结果输出相应的信息。平均查找长度（ASL）是衡量查找效率的指标之一，通过计算ASL可以评估二叉排序树的性能。

3.3 查询功能模块：

1. 题目要求：能够提供按参赛学校查询参赛团队（或根据赛事类别查询参赛团队），即，根据提示输入参赛学校名称（赛事类别），若查找成功，输出该学校参赛的（该赛事类别的）所有团队的基本信息，输出的参赛团队按赛事类别有序输出。（排序算法可从选择排序、插入排序、希尔排序、归并排序、堆排序中任意选择，并为选择算法的原因做出说明。）
2. 需求分析：

• 用户需要根据参赛学校名称或赛事类别查询参赛团队的基本信息，并按照赛事类别对查询结果进行排序。
• 查询成功时，需要输出该学校参赛的指定赛事类别的所有团队的基本信息，并按照赛事类别有序输出。
• 可以使用插入排序算法进行排序，选择插入排序的原因可以是其简单易实现且适用于小规模数据的排序。

3. 实现过程分析：
   提示用户输入参赛学校名称或赛事类别。（键盘输入）
   遍历参赛团队列表，找到符合条件的团队，将其添加到一个新的列表中。
   使用插入排序算法对新的列表按赛事类别进行排序。
   输出排序后的结果，包括每个团队的基本信息。

// 查询并输出参赛团队信息的方法public void queryTeamsByCategory(String eventCategory) {List<Team> queriedTeams = new ArrayList<>();// 遍历所有参赛队伍，找到符合赛事类别的参赛团队for (Team team : teams) {if (team.getCategory().equals(eventCategory)) {queriedTeams.add(team);}}// 使用插入排序对查询结果按赛事类别进行排序// 使用插入排序对查询结果按赛事类别进行排序for (int i = 1; i < queriedTeams.size(); i++) {Team current = queriedTeams.get(i);int j = i - 1;while (j >= 0 && queriedTeams.get(j).getTeamNumber()pareTo(current.getTeamNumber()) > 0) {queriedTeams.set(j + 1, queriedTeams.get(j));j--;}queriedTeams.set(j + 1, current);}// 输出查询结果if (queriedTeams.isEmpty()) {System.out.println("未找到该赛事类别的参赛团队！");} else {for (Team team : queriedTeams) {System.out.println("参赛编号："+ team.getTeamNumber());System.out.println("参赛作品名称：" + team.getProjectName());System.out.println("参赛学校：" + team.getSchool());System.out.println("赛事类别：" + team.getCategory());System.out.println("参赛者：" + team.getCategory());System.out.println("指导教师：" + team.getInstructor());System.out.println("---------------------------");}}}

4. 选用插入排序的原因分析：

• 简单实现：插入排序算法的实现较为简单(这才是主要原因啊 😀)，易于理解和编写，适用于小规模数据集的排序需求。
• 部分有序性：如果参赛团队数据具有一定的有序性，插入排序的性能较好。对于赛事类别较为连续的数据集，插入排序算法可以快速完成排序。
• 原地排序：插入排序是一种原地排序算法，不需要额外的空间。

5. 功能测试

// 根据赛事类别查询参赛团队(键盘输入！！！）String eventCategory = "大数据实践";teamManager.queryTeamsByCategory(eventCategory);}

3.4 决赛叫号系统模块：

1. 题目要求：
2. 需求分析：

• 首先定义了一个决赛室类，包括属性（赛事类别、当前类别下的队伍、叫号队伍的队列）和方法（给每个队伍分配入场的号码，和叫号的方法）

import java.util.*;/*** 决赛室*/
public class Room implements Runnable {// 决赛室的赛事类别private String currentCategory;// 存储当前类别下的队伍private List<Team> competitionTeams;// 叫号队伍的队列private Queue<Team> teamQueue;public Room() {}public Room(String currentCategory) {this.currentCategory = currentCategory;}public Room(String currentCategory, List<Team> competitionTeams) {this.currentCategory = currentCategory;thispetitionTeams = competitionTeams;}public Room(String currentCategory, List<Team> competitionTeams, Queue<Team> teamQueue) {this.currentCategory = currentCategory;thispetitionTeams = competitionTeams;this.teamQueue = teamQueue;}public List<Team> getCompetitionTeams() {return competitionTeams;}public void setCompetitionTeams(List<Team> competitionTeams) {thispetitionTeams = competitionTeams;}// 给每个队伍进行分配顺序编号public void allocateOrder(){int numTeams = competitionTeams.size();List<Integer> numbers = new ArrayList<>();for (int i = 1; i <= numTeams; i++) {numbers.add(i);}//洗牌算法Collections.shuffle(numbers);//给每个队伍进行分配号码for (int i = 0; i < numTeams; i++) {int teamNumber = numbers.get(i);competitionTeams.get(i).setOrder(teamNumber);}}// 队伍按照各自顺序依次入队等待叫号public void enQueue(){teamQueue = new LinkedList<>();//按照进程顺序进行排序competitionTeams.sort(new Comparator<Team>() {@Overridepublic int compare(Team o1, Team o2) {if (o1.getOrder() < o2.getOrder()) {return -1; // o1 小于 o2，返回负整数} else if (o1.getOrder() > o2.getOrder()) {return 1; // o1 大于 o2，返回正整数 进行交换位置} else {return 0; // o1 等于 o2，返回 0}}});// 入队for (int i =0;i<competitionTeams.size();i++){teamQueue.add(competitionTeams.get(i));}}int count =1;//模拟叫号public void startCall(){while (!teamQueue.isEmpty()){System.out.println(currentCategory+"决赛室的"+count +"号请进场");Team currentTeam = teamQueue.poll();System.out.println(currentCategory+"决赛室的"+currentTeam.getOrder()+"已经入场，参与答辩，，其它队伍耐心等待");count++;}System.out.println(currentCategory+"决赛室的"+"所有队伍已经全部入场，比赛结束");}@Overridepublic void run() {//分配号码allocateOrder();//入队enQueue();// 模拟叫号startCall();}
}

• 其次定义了一个叫号模拟执行类

import java.util.ArrayList;
import java.util.List;/*** 决赛叫号系统* 实现思路：* 1. 首先初始化每个决赛室，包括决赛室的类别并* 2. 然后给其分配对应的队伍* 3. 最后开始进行并发执行，因为各个决赛室室同时执行的*/
public class FinalsCallSystem {private List<Room> rooms;private final List<String> eventCategories; // 赛事类别public FinalsCallSystem(List<String> eventCategories) {this.eventCategories = eventCategories;this.rooms = new ArrayList<>();}// 初始化各个决赛室的队伍队列public void initializeRooms(TeamManager teamManager) {for (int i =0;i<eventCategories.size();i++){String currentCategory = eventCategories.get(i);Room room = new Room(currentCategory);List<Team> teams = teamManager.queryTeamsByCategoryNoPrint(currentCategory);room.setCompetitionTeams(teams);rooms.add(room);}}public void startCompetition(){List<Thread> threads = new ArrayList<>();for (int i = 0; i <9; i++) {Room room = rooms.get(i);Thread thread = new Thread(room);threads.add(thread);}// 启动所有决赛室的线程for (Thread thread : threads) {thread.start();}// 等待所有线程执行结束for (Thread thread : threads) {try {thread.join();} catch (InterruptedException e) {throw new RuntimeException(e);}}}}

3. 数据结构选取分析
   使用队列（Queue）来表示每个决赛室的参赛队伍队列，保证先进先出的顺序。
4. 测试分析

 // 模拟叫号过程实现ArrayList<String> categories = new ArrayList<>();categories.add("大数据实践");categories.add("信息图形设计");categories.add("动态信息影像（MG动画）");categories.add("数据可视化");categories.add("人工智能实践赛");categories.add("Web应用与开发");categories.add("管理信息系统");categories.add("算法设计与应用");categories.add("移动应用开发");FinalsCallSystem finalsCallSystem = new FinalsCallSystem(categories);finalsCallSystem.initializeRooms(teamManager);finalsCallSystem.startCompetition();

3.5 校园导游程序模块：

1. 题目要求：
   赛事系统为参赛者提供赛地的校园导游程序,为参赛者提供各种路径导航的查询服务。以我校长山校区提供比赛场地为例，（请为参赛者提供不少于10个目标地的导航。可为参赛者提供校园地图中任意目标地（建筑物）相关信息的查询；提供任意两个目标地（建筑物）的导航查询，即查询任意两个目的地（建筑物）之间的一条最短路径。
2. 需求分析：

• 提供校园地图中不少于10个目标地（建筑物）的导航查询服务。
• 提供任意两个目标地（建筑物）之间的一条最短路径查询。

3. 过程分析：

• 构建校园地图数据，包括建筑物的位置、连接关系等信息。

package navagator;// 建筑物类
public class Building {private String name;private String description;public Building(String name, String description) {this.name = name;this.description = description;}public String getName() {return name;}public String getDescription() {return description;}
}package navagator;// 路径边类
class Path {private String from;private String to;private int distance;public Path(String from, String to, int distance) {this.from = from;this.to = to;this.distance = distance;}public String getFrom() {return from;}public String getTo() {return to;}public int getDistance() {return distance;}
}

• 提供目标地查询服务，让参赛者可以查询指定建筑物的相关信息，如位置、功能等。

   // 获取建筑物信息public Building getBuilding(String name) {return buildings.get(name);}

• 提供最短路径查询服务，参赛者可以输入起点和终点建筑物，系统返回两个建筑物之间的一条最短路径。

 // 导航查询：获取从起点到终点的最短路径和总距离public List<String> findShortestPath(String start, String end) {// 使用Dijkstra算法来查找最短路径PriorityQueue<Path> queue = new PriorityQueue<>(ComparatorparingInt(Path::getDistance));Map<String, Integer> distanceMap = new HashMap<>();Map<String, String> previous = new HashMap<>();// 初始化距离for (String building : buildings.keySet()) {if (building.equals(start)) {distanceMap.put(building, 0);} else {distanceMap.put(building, Integer.MAX_VALUE);}}queue.add(new Path(null, start, 0));while (!queue.isEmpty()) {Path currentPath = queue.poll();String current = currentPath.getTo();if (current.equals(end)) {/**这部分代码是从终点（end）开始向起点（start）回溯遍历路径。初始时，将终点赋值给变量node，然后进入循环。在每次循环中，将当前节点node添加到路径列表path的开头，然后更新node为前一个节点（通过previous映射获取）。这样就实现了从终点到起点的路径遍历，最终得到的路径列表将是从起点到终点的顺序。*/// 已找到最短路径，回溯构建路径列表和总距离List<String> path = new ArrayList<>();String node = end;int totalDistance = currentPath.getDistance();while (node != null) {path.add(0, node);node = previous.get(node);}path.add(Integer.toString(totalDistance)); // 添加总距离return path;}if (currentPath.getDistance() > distanceMap.get(current)) {continue; // 已经存在更短路径，忽略当前路径}for (Path neighborPath : adjacencyList.get(current)) {String neighbor = neighborPath.getFrom().equals(current) ? neighborPath.getTo() : neighborPath.getFrom();int newDistance = distanceMap.get(current) + neighborPath.getDistance();if (newDistance < distanceMap.get(neighbor)) {distanceMap.put(neighbor, newDistance);previous.put(neighbor, current);queue.add(new Path(current, neighbor, newDistance));}}}return null; // 无法找到路径}

寻找最短路径方法分析：

• 首先，创建一个优先队列queue，用于按路径距离从小到大排序。创建两个辅助映射，distanceMap用于记录从起点到每个建筑物的当前最短距离，previous用于记录路径中每个节点的前一个节点。
• 初始化距离：遍历所有建筑物，将起点的距离设置为0，其他建筑物的距离设置为无穷大。
• 将起点添加到队列中。
• 进入循环，直到队列为空：
  • 弹出队列中距离最小的路径。
  • 如果当前节点为终点，说明已找到最短路径，通过回溯构建路径列表和总距离。
  • 遍历当前节点相邻的路径：
    • 获取相邻节点的名称。
    • 计算新的距离：当前节点的距离加上相邻路径的距离。
    • 如果新的距离比之前记录的距离小，更新距离和前一个节点，并将路径加入队列。
• 如果循环结束仍未找到路径，返回null表示无法找到路径。

4. 数据结构选取及其原因
   图数据结构：校园地图可以看作一个图，建筑物作为图的顶点，路径作为图的边。使用图数据结构可以方便表示建筑物之间的连接关系。
5. 测试分析：

System.out.println("=============================欢迎来到地图导航系统=============================");while (true){System.out.println("提示：1.查询建筑物信息 2. 导航查询：获取从起点到终点的最短路径和总距离 3.退出 ");scanner = new Scanner(System.in);int num = scanner.nextInt();switch (num){case 1:// 查询建筑物信息scanner = new Scanner(System.in);System.out.println("请输入要查询的目的地名称");System.out.println("目前可供选择的：西苑食堂\",\n" +"明德楼\", \n" +"文理大楼\",\n" +"体育馆\", \n" +"图书馆\", \n" +"东苑操场\",\n" +"计算机学院楼\n" +"文体中心\",\n" +"扬帆广场\",");String buildingName = scanner.next();Building buildingA = campusMap.getBuilding(buildingName);System.out.println(buildingA.getName() + ": " + buildingA.getDescription());break;case 2:// 导航查询：获取从起点到终点的最短路径和总距离scanner = new Scanner(System.in);System.out.println("请输入起始地点的名称：");String from = scanner.next();System.out.println("请输入目的地的名称：");String to = scanner.next();List<String> shortestPath = campusMap.findShortestPath(from, to);if (shortestPath != null) {System.out.println("最短路径：");for (int i = 0; i < shortestPath.size() - 1; i++) {System.out.print(shortestPath.get(i));if (i!=shortestPath.size()-2){System.out.print("--->");}}System.out.println();int totalDistance = Integer.parseInt(shortestPath.get(shortestPath.size() - 1));System.out.println("最短距离为：" + totalDistance);} else {System.out.println("无法找到路径！");}case 3:return;default:System.out.println("输入错误！！！");}}

四结果演示：

后期又进行了一些优化，放一些图片吧：

实现了前四个模块的功能：

第五个地图模块的功能：

源码地址,真的太肝了 😭😭😭：课程实验源码仓库地址

本文标签： 数据结构课程设计实验