数据结构课设

项目

发布时间 : 2023-05-22 23:15

字数:6.1k 阅读 :

数据结构课程设计

基于JavaSwing的赛事管理系统

【引入】

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

信息管理

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

信息查询

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

详细查询

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

赛事模拟

为省赛现场设计一个决赛叫号系统。所有参赛队按赛事组织文件中的赛事类别分到9个决赛室，决赛室按顺序叫号，被叫号参赛队进场，比赛结束后，下一参赛队才能进赛场。请模拟决赛叫号系统，演示省赛现场各决赛室的参赛队进场情况。（模拟时，要能直观展示叫号顺序与进场秩序一致）

地图模拟

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

【设计要求】

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

【实现步骤提示】

分析任务，进行模块划分。
定义数据结构，建议按照抽象数据类型的定义、表示和实现来描述，用类C语言（伪代码）来描述数据的存储表示和相应操作的具体实现过程。
设计合适的算法来实现其功能，并绘制函数调用关系图。

【测试数据】

要求使用全部合法数据，整体非法数据，局部非法数据。进行程序测试，以保证程序的健壮性。

开发过程

UI界面设计

基于JavaSwing的赛事管理系统，在需求分析后我们先考虑UI界面的布局。

按照需求分析，我们可以得出本次赛事系统大概需要5个界面进行展示不同业务。

信息管理
- 信息模块主要展示赛事全部队伍的表单，每个表单项记录了一行的队伍详细信息，且提供对应的删除和修改的操作按钮。
查询模块
- 查询模块主要负责精确查询和按校查询两个业务。
  - 按队号查询需要一行文本框和查询按钮（页面顶部）
  - 按学校名称查询需要一行文本框和查询按钮（页面顶部）
  - 需要一个展示查询结果的表单（占页面2/3，页面中间）
  - 需要一个显示精确查询ASL失败和成功次数的文本显示区域(页面底部)
参赛登记
- 需要提供5行文本框和对应提示符，用于收集登记信息
- 需要一个登记按钮，用于提交登记的信息
赛事模拟
- 需要一个模拟按钮，用于启动本次赛事模拟
- 需要一个文本输出域来显示赛事模拟文字结果
地图模拟
- 需要一个模拟按钮，用于启动本次赛事地图模拟
- 需要一个文本输出域来显示地图模拟文字结果

UI实现

使用自定义的选项卡式页面切换UI

左侧为菜单栏，右侧为具体显示页面

package com.os467.management;

import JFrameBuilder.WindowBuilder;

public class init {

    public static void main(String[] args) {

        new WindowBuilder().
                register(new JFrameMakerImpl())
                .getFrame();
    }

}

采用自己封装的窗体构建者类创建窗口

窗体内容构建者

package com.os467.management;

import JFrameBuilder.JFrameContentMaker;
import JFrameBuilder.component.menu.LeftSelectMenu;
import JFrameBuilder.component.menu.Menu;
import com.os467.management.servicePage.AddInfoPageBuilder;
import com.os467.management.servicePage.FileService;
import com.os467.management.servicePage.InfoPageBuilder;
import com.os467.management.servicePage.SearchPageBuilder;
import com.os467.management.servicePage.impl.AddInfoPageBuilderImpl;
import com.os467.management.servicePage.impl.InfoPageBuilderImpl;
import com.os467.management.servicePage.impl.SearchPageBuilderImpl;

import javax.swing.*;


public class JFrameMakerImpl implements JFrameContentMaker {

    private FileService fileService = new FileService();

    private InfoPageBuilder infoPageBuilder = new InfoPageBuilderImpl();

    private SearchPageBuilder searchPageBuilder = new SearchPageBuilderImpl();

    private AddInfoPageBuilder addInfoPageBuilder = new AddInfoPageBuilderImpl();

    @Override
    public void make(JFrame jFrame) {
        jFrame.setTitle("赛事管理系统");
        Menu leftSelectMenu = new LeftSelectMenu(jFrame, 5);

        leftSelectMenu.name(0,"信息管理");
        leftSelectMenu.name(1,"查询模块");
        leftSelectMenu.name(2,"参赛登记");
        leftSelectMenu.name(3,"赛事模拟");
        leftSelectMenu.name(4,"地图模拟");

        //注入依赖
        infoPageBuilder.setFileService(fileService);
        searchPageBuilder.setFileService(fileService);
        addInfoPageBuilder.setFileService(fileService);
        addInfoPageBuilder.setInfoPageBuilder(infoPageBuilder);

        //构建页面
        infoPageBuilder.buildPage(leftSelectMenu.getPage(0));
        searchPageBuilder.buildPage(leftSelectMenu.getPage(1));
        addInfoPageBuilder.buildPage(leftSelectMenu.getPage(2));

        //设置默认页
        leftSelectMenu.setDefaultPage(leftSelectMenu.getPage(0));
    }




}

快速构建页面模块，将具体的页面实现交给对应的页面构建类即可

信息管理页面逻辑

文件读写

根据相对路径获取到文件位置

使用包装输入输出流读取文件信息

具体信息交由对应的页面处理即可

package com.os467.management.servicePage;

import javax.swing.*;
import java.io.*;

public class FileService {

    private String title;

    private String context;

    private JTable jTable;

    public String readFile() {
        //读取文件
        String property = System.getProperty("user.dir") + "\\src\\main\\resources\\team.txt";

        StringBuilder stringBuilder = null;
        BufferedReader bufferedReader = null;
        try {
            FileReader fileReader = new FileReader(property);
            bufferedReader = new BufferedReader(fileReader);
            stringBuilder = new StringBuilder();
            int read;
            while ((read = bufferedReader.read()) != -1){
                if (read == -1){
                    break;
                }
                stringBuilder.append((char)read);
            }
        } catch (FileNotFoundException e) {
            e.printStackTrace();
        } catch (IOException e) {
            e.printStackTrace();
        }finally {
            try {
                bufferedReader.close();
            } catch (IOException e) {
                e.printStackTrace();
            }
        }

        String context = stringBuilder.toString();
        this.context = context;
        return context;
    }

    public void writeFileWithJTable() {
        int rowCount = jTable.getRowCount();
        int columnCount = jTable.getColumnCount() - 2;
        StringBuilder stringBuilder = new StringBuilder();
        stringBuilder.append(title);
        for (int i = 0; i < rowCount; i++) {
            for (int j = 0; j < columnCount - 1; j++) {
                Object s = jTable.getValueAt(i, j);
                stringBuilder.append(s);
                stringBuilder.append("\t#\t");
            }
            Object s = jTable.getValueAt(i, columnCount - 1);
            stringBuilder.append(s);
            stringBuilder.append("\n");
        }
        String context = stringBuilder.toString();

        writeFileWithContext(context);
    }

    public void writeFileWithContext(String context){
        //文件位置
        String property = System.getProperty("user.dir") + "\\src\\main\\resources\\team.txt";

        BufferedWriter bufferedWriter = null;
        try {
            bufferedWriter = new BufferedWriter(new FileWriter(property));
            bufferedWriter.write(context);
        } catch (IOException e) {
            e.printStackTrace();
        }finally {
            try {
                this.context = context;
                bufferedWriter.flush();
                bufferedWriter.close();
            } catch (IOException e) {
                e.printStackTrace();
            }
        }
    }

    public String getTitle() {
        return title;
    }

    public void setTitle(String title) {
        this.title = title;
    }

    public String getContext() {
        return context;
    }

    public void setContext(String context) {
        this.context = context;
    }

    public JTable getjTable() {
        return jTable;
    }

    public void setjTable(JTable jTable) {
        this.jTable = jTable;
    }
}

增加信息

绑定一个登记按钮监听器，获取到具体的文本框信息，整合为新记录插入赛事表

测试数据添加成功

队伍编号生成问题，需要获取到当前列表最大编号，新增编号为当前最大编号+1

//获取到当前最大序列号
String[] split = context.split("\n");
int max = 0;

for (int i = 1; i < split.length; i++) {
    int num = Integer.parseInt(split[i].split("\t#\t")[0]);
    if (num > max){
        max = num;
    }
}

用StringBuilder构建新加入的信息，重新写回文件

//序列号增加
++max;
StringBuilder stringBuilder = new StringBuilder();
stringBuilder.append(context);
stringBuilder.append(max);
stringBuilder.append("\t#\t");
stringBuilder.append(subjectField.getText());
subjectField.setText("");
stringBuilder.append("\t#\t");
stringBuilder.append(schoolField.getText());
schoolField.setText("");
stringBuilder.append("\t#\t");
stringBuilder.append(eventField.getText());
eventField.setText("");
stringBuilder.append("\t#\t");
stringBuilder.append(contestantField.getText());
contestantField.setText("");
stringBuilder.append("\t#\t");
stringBuilder.append(teacherField.getText());
teacherField.setText("");
stringBuilder.append("\t#\t");
stringBuilder.append("\n");

写回文件，更新列表页面

fileService.writeFileWithContext(stringBuilder.toString());
infoPageBuilder.reBuildPage();

删除，修改按钮监听器绑定

TableCellButton tableCellButton = new TableCellButton(strings.length,tableModel.getRowCount(), fileService.getjTable());
tableCellButton.registerOperation("修改",new ActionListener() {
    @Override
    public void actionPerformed(ActionEvent e) {
        fileService.writeFileWithJTable();
    }
},new Color(236, 195, 114));

//绑定表单项
tableCellButton = new TableCellButton(strings.length+1,tableModel.getRowCount(), fileService.getjTable());
tableCellButton.registerOperation("删除",new ActionListener() {
    @Override
    public void actionPerformed(ActionEvent e) {
        String actionCommand = e.getActionCommand();
        DefaultTableModel tableModel = (DefaultTableModel)fileService.getjTable().getModel();
        tableModel.removeRow(Integer.parseInt(actionCommand));
        fileService.writeFileWithJTable();
    }
},new Color(255, 88, 88));

封装了一个tableCellButton组件，用于自动添加表列操作按钮，内部进行自动封装，省略了开发步骤

查询模块

基于二叉排序树的队号查找

本类提供了基本的create方法，会根据提供的键-值数组自动构建二叉排序树

提供get方法，进行比较查找，若查找为空则返回null

提供了ASL失败和成功的算法，通过栈实现非递归的ASL计算

ASL计算方法设计

中序遍历访问，当遇到叶子结点时累计一次访问失败比较次数（查父结点层数即可知道比较次数），访问到一次子树根结点则累记一次访问成功次数，累计成功比较次数（查结点层数）。

n为根结点数
$$
ASL_{success} = {1\over n} * (\sum_i^n Level(Node_i))
$$
n 为叶子结点数
$$
ASL_{failed} = {1\over n} * (\sum_i^n (Level(Leaf_i) -1))
$$

package com.os467.management.dataStruct;

import java.util.List;
import java.util.Stack;

public class MyTreeMap<K, V> {

    private TreeNode root;

    private Integer nodeNum = 0;

    private Integer leafNum = 0;

    private Double aslSuccess;

    private Double aslFailed;

    public void create(List<K> keys, List<V> values) {
        if (values.get(0) != null){
            root = new TreeNode(keys.get(0),values.get(0),1);
            incNodeNum();
        }
        for (int i = 1; i < values.size(); i++) {
            put(keys.get(i),values.get(i));
        }
    }

    /**
     * 构建二叉排序树
     * @param k
     * @param v
     */
    private void put(K k, V v) {
        Integer key = (Integer) k;
        String value = (String) v;
        TreeNode p = root;
        Integer level = 1;
        while (true){
            ++level;
            if (key > (Integer) (p.key)){
                if (p.rChild == null){
                    p.rChild = new TreeNode(key,value,level);
                    incNodeNum();
                    break;
                }else {
                    p = p.rChild;
                }
            }else{
                if (p.lChild == null){
                    p.lChild = new TreeNode(key,value,level);
                    incNodeNum();
                    break;
                }else {
                    p = p.lChild;
                }
            }
        }
    }

    private void incNodeNum(){
        nodeNum++;
        incLeafNum();
    }

    private void incLeafNum() {
        leafNum = nodeNum + 1;
    }

    /**
     * 二叉查找
     * @param key
     * @return
     */
    public V get(K key) {
        TreeNode p = root;
        Integer key0 = (Integer) key;
        while (true){
            if (p != null){
                if (!key0.equals(p.key)){
                    if (key0 > (Integer) (p.key)){
                        p = p.rChild;
                    }else{
                        p = p.lChild;
                    }
                }else {
                    return (V) p.value;
                }
            }else {
                return null;
            }
        }
    }

    class TreeNode<K,V>{
        K key;
        V value;
        Integer level;
        TreeNode lChild;
        TreeNode rChild;

        public TreeNode(K v, V v1,Integer level) {
            key = v;
            value = v1;
            this.level = level;
        }
    }

    /**
     * 获取成功ASL
     * @return
     */
    public double getAslSuccess() {
        if (aslSuccess == null){
            calculate();
        }
        return aslSuccess;
    }

    private boolean inOrder(TreeNode r){
        if (r == null){
            return false;
        }
        //访问左子树
        boolean b1 = inOrder(r.lChild);
        if (!b1){
            failedLevelSum += r.level;
        }
        //访问根结点
        levelSum += r.level;
        //访问右子树
        boolean b = inOrder(r.rChild);
        if (!b){
            failedLevelSum += r.level;
        }
        return true;
    }

    private Integer failedLevelSum = 0;
    private Integer levelSum = 0;

    /**
     * 计算ASL
     */
    private void calculate() {
        failedLevelSum = 0;
        levelSum = 0;
        inOrder(root);
        aslFailed = (double)failedLevelSum/(double)(nodeNum+1);
        aslSuccess = (double)levelSum / (double)nodeNum;
    }

    /**
     * 获取失败ASL
     * @return
     */
    public double getAslFailed() {
        if (aslFailed == null){
            calculate();
        }
        return aslFailed;
    }
}

按学校名称的聚类查找，实现按赛事类别排序

基于递归的并归排序算法实现，sort方法调用的并归排序，对ArrayList的内部对象进行重新排序

由于赛事类别是字符串类型无法直接比较大小，因此需要实现比较器接口实现字典序比较

package com.os467.management.dataStruct;

import java.util.ArrayList;
import java.util.Comparator;

public class MyArrayList<E> {

    private ArrayList<E> arrayList;

    private Comparator comparator;

    public MyArrayList() {
        this.arrayList = new ArrayList<>();
    }

    public void add(E e){
        arrayList.add(e);
    }

    public E get(Integer i){
        return arrayList.get(i);
    }

    /**
     * 使用二路归并排序，最差与最好时间复杂度相对较好且相同 O(n*log_2(n))，比较稳定
     * @param comparator
     */
    public void sort(Comparator<E> comparator) {
        this.comparator = comparator;
        Object[] r = new Object[arrayList.size()];
        for (int i = 0; i < arrayList.size(); i++) {
            r[i] = arrayList.get(i);
        }
        Object[] r1 = new Object[arrayList.size()];

        //排序算法
        mergeSort(r,r1,0,r.length-1);


        for (int i = 0; i < r.length; i++) {
            arrayList.set(i, (E) r[i]);
        }
    }


    /**
     * 递归二路归并
     * @param r
     * @param r1
     * @param left
     * @param right
     */
    private void mergeSort(Object[] r, Object[] r1, int left, int right) {
        if (left < right){
            int mid = (left + right) /2;
            mergeSort(r,r1,left,mid);
            mergeSort(r,r1,mid+1,right);
            merge(r,r1,left,mid,right);
            for (int j = left; j < right; j++) {
                r[j] = r1[j];
            }
        }
    }

    /**
     * 将相邻两段归并
     * @param r
     * @param r1
     * @param s
     * @param m
     * @param t
     */
    private void merge(Object[] r, Object[] r1, int s, int m, int t) {
        //r[s~m]
        int i = s, j = m + 1, k = s;
        while (i <= m && j <= t){
            //r[i] <= r[j]
            if (comparator.compare(r[i],r[j]) != 1){
                r1[k++] = r[i++];
            }else {
                r1[k++] = r[j++];
            }
        }
        while (i <= m){
            r1[k++] = r[i++];
        }
        while (j <= t){
            r1[k++] = r[j++];
        }
    }

    public int size() {
        return arrayList.size();
    }
}

提供一个字典序比较接口

先比较两个数组长度

按照较短的数组长度开始遍历比较

依次将char类型数据转换为int类型进行比较，如果相等则继续比较下一个

若可比较则直接返回比较结果

否则比较串长度，若长度相等则判断为相等字符串，否则较长串更大。

teams.sort(new Comparator<Team>() {
    @Override
    public int compare(Team o1, Team o2) {
        char[] e1 = new char[0];
        char[] e2 = new char[0];
        e1 = o1.getEventCategory().toCharArray();
        e2 = o2.getEventCategory().toCharArray();
        int len = e1.length;
        int ret = -1;
        if (e1.length > e2.length){
            len = e2.length;
            ret = 1;
        }
        for (int i = 0; i < len; i++) {
            int i1 = e1[i];
            int i2 = e2[i];
            if (i1 == i2){
                continue;
            }else if (i1 > i2){
                return 1;
            }else {
                return -1;
            }
        }
        if (e1.length == e2.length){
            return 0;
        }
        return ret;
    }
});

此算法实现了字典序字符串比较

赛事模拟

分类

点击赛事模拟按钮开始进行赛事模拟

根据赛事类别提前分类为7个组别，当一组超过28个队伍会自动分成两组

在查询时需要根据组别进行分类，同时要根据字典序对类别进行排序保证相同赛事类别的队伍尽量在一组的同一段时间内入场

并且从12点左右到2点10分为午休时间，停止队伍入场

String context = fileService.getContext();
String[] rows = context.split("\n");

//用于分组
HashMap<Integer, List<Team>> hashMap = new HashMap<>();

//获取到队伍列表
C: for (int i = 1; i < rows.length; i++) {
    Team team = new Team(rows[i].split("\t#\t"));
    int categoryIndex = Constant.getCategoryIndex(team.getEventCategory());
    List<Team> teams = hashMap.get(categoryIndex);
    if (teams == null){
        teams = new ArrayList<>();
    }else if (teams.size() >= 28){
        while (true){
            categoryIndex++;
            List<Team> teams1 = hashMap.get(categoryIndex);
            if (teams1 == null){
                teams1 = new ArrayList<>();
            }else if (teams1.size() >= 28){
                continue;
            }
            teams1.add(team);
            hashMap.put(categoryIndex,teams1);
            continue C;
        }
    }
    teams.add(team);
    hashMap.put(categoryIndex,teams);
}

StringBuilder stringBuilder = new StringBuilder();
int totalSpace = 35;
MyComparator myComparator = new MyComparator();
Set<Integer> keySet = hashMap.keySet();
for (int i = 0; i < keySet.size(); i++) {
    List<Team> teams = hashMap.get(i);
    teams.sort(myComparator);
    stringBuilder.append("-------第");
    stringBuilder.append((i+1));
    stringBuilder.append("组入场次序-------\n");
    time = Constant.EIGHT_AM + Constant.HOUR;
    handle(stringBuilder, totalSpace, teams);
}
textArea.setText(stringBuilder.toString());
}

private void handle(StringBuilder stringBuilder, int totalSpace, List<Team> teams) {
    for (int j = 0; j < teams.size(); j++) {
        stringBuilder.append(teams.get(j).getTid());
        stringBuilder.append("\t");
        String eventCategory = teams.get(j).getEventCategory();
        eventCategory.replace(" ","");
        int eL = eventCategory.length();
        stringBuilder.append(eventCategory);
        for (int k = 0; k < totalSpace - eL*2; k++) {
            stringBuilder.append(" ");
        }
        String student = teams.get(j).getStudent();
        student.replace(" ","");
        eL = student.length();
        stringBuilder.append(student);
        for (int k = 0; k < totalSpace - eL*2; k++) {
            stringBuilder.append(" ");
        }
        stringBuilder.append("准备入场\t");
        String format = new SimpleDateFormat().format(new Date(time));
        time += Constant.MIN * (12 + random.nextInt(4)) ;
        if (time >= Constant.EIGHT_AM + 4*Constant.HOUR && time <= Constant.EIGHT_AM + 5 *Constant.HOUR){
            time = Constant.EIGHT_AM + 6 * Constant.HOUR - 2 * Constant.MIN;
        }
        stringBuilder.append(format.replace("70-1-1",""));
        stringBuilder.append("\n");
    }
}

使用哈希表存储不同分组的队伍列队，便于下次取出使用

地图模拟

按照下图构建地图矩阵

需要提供一个景点类

用于存储复杂数据，如景点的具体id，景点名称，景点介绍等。

package com.os467.management.entity;

public class View {
    //景点的编号
    private int id;

    //景点的名称
    private String name;

    //景点的介绍
    private String introduction;

    //构造方法
    public View(int id, String name, String introduction) {
        this.id = id;
        this.name = name;
        this.introduction = introduction;
    }

    public String getName() {
        return name;
    }

    public String getIntroduction() {
        return introduction;
    }

    public int getId() {
        return id;
    }
}

迪杰斯特拉算法

为什么要选用迪杰斯特拉算法？迪杰斯特拉算法是单源点到其它源点生成最短路径的算法。由于在每次搜索时并不需要把所有源点的都搜索出来，并且我需要记录生成过程中的具体路径，因此使用了单源点的迪杰斯特拉算法。

在生成完单源点的最短路径列表后，只需要将**(源点索引-路径列表)**存入哈希表即可
当下次访问时只需要从哈希表中取出计算过的值即可
如果选择了其它源点则重新生成新的最短路径列表，也存入哈希表即可下次直接取出使用

算法实现思路

创建一个哈希集合s用于存储已生成到源的最短路径的顶点

创建一个哈希集合vs用于存储未生成到源的最短路径的顶点

vs集合中存储的顶点的最短路径是动态更新不断被优化的，只有存入了s集合的才是已确定了最短路径的顶点

开始将源点放入s集合，开始源点记录初始路径
将其它顶点全部添加到vs集合，其它源点路径状态为空
进入循环
- 通过s集合中的最短路径顶点更新vs集合
  - 具体是将s集合中的所有顶点进行遍历，依次和vs集合中所有与当前遍历到的s集合顶点连通的顶点进行比较，并决定是否更新vs中的顶点
  - 比较更新的过程如下：
    - 如果遍历到的s集合中顶点记录的最短源点长度 + 当前vs集合遍历到顶点到此s集合顶点的路径长度 < 当前vs集合顶点记录的最短路径长度 → 则更新vs集合顶点最短路径长度记录为新的更短长度记录
    - 否则不做更新，继续遍历直到s集合遍历完毕
- 获取到vs集合中目前记录的最短路径点加入v集合，并从vs集合中移出
- 判断vs集合是否为空，为空代表遍历结束，否则继续下一轮循环

具体代码

由于用MAX_INT代替了不连通，因此没有创建邻接矩阵，只需要用边矩阵即可判断是否连通。

package com.os467.management.dataStruct;

import com.os467.management.Constant;
import com.os467.management.entity.View;

import java.util.*;

public class MGraph {

    //地图点对点集合
    private static Map<String,String> wayMap = new HashMap<>();

    //顶点数组
    private static View[] vertex = Constant.views;

    //图的路径数组
    private static int[][] pre = Constant.pre;

    //图的顶点数和边数
    private static int vertexNum = Constant.MAX_SIZE, edgeNum = Constant.EDGE_NUM;


    public String getTargetInfo(String tP) {
        for (View view : vertex) {
            if (view.getName().equals(tP)){
                return view.getIntroduction();
            }
        }
        return "";
    }

    /**
     * 获取两点之间的最短路径
     * @param sP
     * @param tP
     * @return
     */
    public String getWay(String sP, String tP) {
        Integer s = getVertexIndex(sP);
        Integer t = getVertexIndex(tP);
        String wayInfo = wayMap.get(s + "," + t);
        if (wayInfo != null){
            return wayInfo;
        }else {
            dijkstra(s);
            wayInfo = wayMap.get(s + "," + t);
        }
        return wayInfo;
    }

    /**
     * 迪杰斯特拉算法生成单源点到其它源点路径及路径长度，保存到哈希表中便于下次直接取出使用
     * @param source
     */
    private void dijkstra(Integer source) {
        HashMap<Integer,Path> s = new HashMap<>();
        //记录每次更新的最近距离
        HashMap<Integer,Path> vs = new HashMap<>();

        //s开始只包含源，s有集合和记录作用
        s.put(source,new Path(0,(source+1)+"->"));
        for (int i = 0; i < vertexNum; i++) {
            if(i == source){
                continue;
            }
            //添加其它点到vs集合，初始化一开始最近距离
            vs.put(i,new Path(Constant.MAX_INT,""));
        }

        while (true){
            //通过s集合中最短路径点更新vs集合
            updateVs(s,vs);
            //获取到vs集合中目前最短路径点加入v集合
            Integer index = selectDisInVs(vs);
            Path dist = vs.get(index);
            //从vs集合中移出
            vs.remove(index);
            //加入s集合
            s.put(index,dist);
            if (vs.isEmpty()){
                break;
            }
        }

        //保存此源点到其它点集合
        Set<Integer> keySet = s.keySet();
        for (Integer k : keySet) {
            if (k.equals(source)){
                continue;
            }else {
                Path path = s.get(k);
                String pathPrint = path.getPrint();
                wayMap.put(source+","+k,pathPrint);
            }
        }
    }

    private void updateVs(HashMap<Integer, Path> s, HashMap<Integer, Path> vs) {
        Set<Integer> sk = s.keySet();
        //通过s集合点集更新vs
        for (Integer key : sk) {
            //更新新结点
            Path disPath = s.get(key);
            Integer sDis = disPath.getDist();
            for (int i = 0; i < vertexNum; i++) {
                if (i == key){
                    continue;
                }
                //更新vs点集中与当前s集点连通点
                if (pre[key][i] != Constant.MAX_INT && vs.containsKey(i)){
                    //更新vs集合中的i索引结点的最新源路径
                    Path old = vs.get(i);
                    Integer dist = old.getDist();
                    //如果s集合中的点能够更新vs集合中点的源路径长度则更新
                    int preUpdate = sDis + pre[key][i];
                    if (dist > preUpdate){
                        //说明vs中dist的长度可以被更新，通过s集合中的点有更好的路径选择
                        old.setDist(preUpdate);
                        //更新为s点集中记录的路径
                        old.setDistPath(disPath.getDistPath() + (i + 1) + "->");
                    }else {
                        //否则不做更新
                        continue;
                    }
                }
            }
        }
    }

    private Integer selectDisInVs(HashMap<Integer, Path> vs) {
        Integer index = null;
        Integer dist = null;
        Set<Integer> keySet = vs.keySet();
        for (Integer key : keySet) {
            Integer dis = vs.get(key).getDist();
            if (index == null){
                index = key;
                dist = dis;
            }else if (dis < dist){
                index = key;
                dist = dis;
            }
        }
        return index;
    }

    private Integer getVertexIndex(String name) {
        for (int i = 0; i < vertexNum; i++) {
            if (vertex[i].getName().equals(name)){
                return i;
            }
        }
        return null;
    }
}

使用绘图工具绘制路线

实现一个绘图面板

调用paint方法进行绘图

class MapPanel extends JPanel{

    private List<Integer> markIds;

    public MapPanel() {
    }

    public void markMap(String[] ways){
        List<Integer> ids = new ArrayList<>();
        for (String way : ways) {
            int id = Constant.getViewByName(way).getId();
            ids.add(id);
        }
        this.markIds = ids;
        repaint();
    }

    @Override
    public void paint(Graphics g) {
        super.paint(g);
        //处理所有x，y点，绘制圆圈，读取View中的xy数据
        drawAllView(g);
    }

    //1315 937
    private void drawAllView(Graphics g) {
        int width = getWidth();
        int height = getHeight();
        double wB = width * (5D/6D)/ (double)1315;
        double hB = height *(5D/6D)/ (double)937;
        View[] views = Constant.views;
        for (int i = 0; i < views.length; i++) {
            int x = (int) (views[i].getX() * wB);
            int y = (int)(views[i].getY() * hB);
            if (inMarkIds(views[i])){
                if (isFirstMark(views[i])){
                    g.setColor(new Color(46, 168, 18));
                }else {
                    g.setColor(new Color(236, 68, 68));
                }
                g.fillOval(x-15,y-15,30,30);
                g.drawString(views[i].getName(),x,y-20);
                g.setColor(new Color(0,0,0));
            }else {
                g.drawOval(x-15,y-15,30,30);
                g.drawString(views[i].getName(),x,y-20);
            }
        }
        int[][] pre = Constant.pre;
        for (int i = 0; i < pre.length; i++) {
            for (int j = 0; j <= i; j++) {
                if (pre[i][j] != Constant.MAX_INT){
                    if (inMarkIds(views[i]) && inMarkIds(views[j])){
                        g.setColor(new Color(229, 15, 15));
                        g.drawLine((int) (views[i].getX() * wB),(int)(views[i].getY() * hB),
                                (int) (views[j].getX() * wB),(int)(views[j].getY() * hB));
                        g.setColor(new Color(0,0,0));
                    }else {
                        g.drawLine((int) (views[i].getX() * wB),(int)(views[i].getY() * hB),
                                (int) (views[j].getX() * wB),(int)(views[j].getY() * hB));
                    }
                }
            }
        }
    }

    private boolean isFirstMark(View view) {
        if (markIds != null){
            if (markIds.get(0).equals(view.getId())){
                return true;
            }
        }
        return false;
    }

    private boolean inMarkIds(View view) {
        if (markIds != null){
            for (Integer markId : markIds) {
                if (view.getId() == markId){
                    return true;
                }
            }
        }
        return false;
    }

}

转载请注明来源，欢迎对文章中的引用来源进行考证，欢迎指出任何有错误或不够清晰的表达。可以邮件至 1300452403@qq.com