JZTXT

课设预习报告

发布时间 2023-05-23 11:11:23作者: 奇蛮

数据结构课程设计预习报告

1.问题描述

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

1.能够管理各参赛队的基本信息

包含参赛队编号，参赛作品名称，参赛学校，赛事类别，参赛者，指导老师），赛事类别共11项，包括增加、删除、修改参赛队伍的信息。

 1 public class Team {
 2     private int teamId; // 参赛队编号
 3     private String teamName; // 参赛作品名称
 4     private String school; // 参赛学校
 5     private String eventType; // 赛事类别
 6     private String participant; // 参赛者
 7     private String teacher; // 指导老师
 8 
 9     public Team(int teamId, String teamName, String school, String eventType, String participant, String teacher) {
10         this.teamId = teamId;
11         this.teamName = teamName;
12         this.school = school;
13         this.eventType = eventType;
14         this.participant = participant;
15         this.teacher = teacher;
16     }
17 
18     public int getTeamId() {
19         return teamId;
20     }
21 
22     public String getTeamName() {
23         return teamName;
24     }
25 
26     public String getSchool() {
27         return school;
28     }
29 
30     public String getEventType() {
31         return eventType;
32     }
33 
34     public String getParticipant() {
35         return participant;
36     }
37 
38     public String getTeacher() {
39         return teacher;
40     }
41 
42     @Override
43     public String toString() {
44         return "参赛队伍信息：" +
45                 "参赛队编号：" + teamId +
46                 ", 参赛作品名称：" + teamName +
47                 ", 参赛学校：" + school +
48                 ", 赛事类别：" + eventType +
49                 ", 参赛者：" + participant +
50                 ", 指导老师：" + teacher;
51     }
52 }

 

2.从team.txt中读取参赛队伍的基本信息，实现基于二叉排序树的查找。

根据提示输入参赛队编号，若查找成功，输出该赛事类别对应的基本信息（参赛作品名称、参赛学校、赛事类别、参赛者和指导老师信息），同时，输出查找成功时的平均查找长度ASL；否则，输出“查找失败！”。

// 从team.txt中读取参赛队伍信息

 1  public void readTeamFile(String filename) {
 2         File file = new File(filename);
 3         try {
 4             BufferedReader reader = new BufferedReader(new FileReader(file));
 5             String line = null;
 6             while ((line = reader.readLine()) != null) { // 读取文件内容
 7                 String[] data = line.split("#"); // 按符号“#”切分数据
 8                 int teamId = Integer.parseInt(data[0]);
 9                 String teamName = data[1];
10                 String school = data[2];
11                 String eventType = data[3];
12                 String participant = data[4];
13                 String teacher = data[5];
14                 Team team = new Team(teamId, teamName, school, eventType, participant, teacher);
15                 addTeam(team);
16             }
17         } catch (IOException e) {
18             e.printStackTrace();
19         }
20     }

 

 

// 基于二叉排序树的查找

 1 public void search() {
 2         Scanner scanner = new Scanner(System.in);
 3         System.out.println("请输入要查找的参赛队编号：");
 4         int teamId = scanner.nextInt();
 5         BinarySortTree.BSTNode temp = binarySortTree.search(teamId);
 6         if (temp != null) { // 查找成功
 7             Team team = (Team) temp.getData();
 8             System.out.println(team);
 9             System.out.println("平均查找长度ASL：" + binarySortTree.getASL());
10         } else { // 查找失败
11             System.out.println("查找失败！");
12         }
13     }

 

//二叉树类

 

public class BinarySortTree {
    private BSTNode root;
    private int size;
    private int sum; //二叉排序树中所有结点的深度之和

    public BinarySortTree() {
        root = null;
        size = 0;
        sum = 0;
    }

    public BSTNode getRoot() {
        return root;
    }

    public int getSize() {
        return size;
    }

    public int getASL() {
        return sum / size;
    }

    // 插入操作
    public void insert(int key, Object data) {
        insert(root, key, data);
    }

    private void insert(BSTNode node, int key, Object data) {
        if (root == null) {
            root = new BSTNode(key, data);
            size++;
            return;
        }
        if (node == null) {
            node = new BSTNode(key, data);
            size++;
            return;
        }
        if (key < node.key) {
            if (node.leftChild == null) {
                node.leftChild = new BSTNode(key, data);
                size++;
                return;
            }
            insert(node.leftChild, key, data);
        } else if (key > node.key) {
            if (node.rightChild == null) {
                node.rightChild = new BSTNode(key, data);
                size++;
                return;
            }
            insert(node.rightChild, key, data);
        } else {
            node.data = data;
        }
    }

    // 删除操作
    public boolean delete(int key) {
        BSTNode parent = root; // 记录要删除结点的父结点
        BSTNode current = root; // 记录要删除结点
        boolean isLeftChild = true;
        while (current.key != key) {
            parent = current;
            if (key < current.key) {
                isLeftChild = true;
                current = current.leftChild;
            } else {
                isLeftChild = false;
                current = current.rightChild;
            }
            if (current == null) {
                return false;
            }
        }
        // 情况1：要删除的结点没有子结点
        if (current.leftChild == null && current.rightChild == null) {
            if (current == root) {
                root = null;
            } else if (isLeftChild) {
                parent.leftChild = null;
            } else {
                parent.rightChild = null;
            }
        }
        // 情况2：要删除的结点只有一个子结点
        else if (current.rightChild == null) {
            if (current == root) {
                root = current.leftChild;
            } else if (isLeftChild) {
                parent.leftChild = current.leftChild;
            } else {
                parent.rightChild = current.leftChild;
            }
        } else if (current.leftChild == null) {
            if (current == root) {
                root = current.rightChild;
            } else if (isLeftChild) {
                parent.leftChild = current.rightChild;
            } else {
                parent.rightChild = current.rightChild;
            }
        }
        // 情况3：要删除的结点有两个子结点
        else {
            BSTNode successor = getSuccessor(current);
            if (current == root) {
                root = successor;
            } else if (isLeftChild) {
                parent.leftChild = successor;
            } else {
                parent.rightChild = successor;
            }
            successor.leftChild = current.leftChild;
        }
        size--;
        return true;
    }

    // 获取后继结点
    private BSTNode getSuccessor(BSTNode delNode) {
        BSTNode successorParent = delNode;
        BSTNode successor = delNode;
        BSTNode current = delNode.rightChild;
        while (current != null) {
            successorParent = successor;
            successor = current;
            current = current.leftChild;
        }
        if (successor != delNode.rightChild) {
            successorParent.leftChild = successor.rightChild;
            successor.rightChild = delNode.rightChild;
        }
        return successor;
    }

    // 修改操作
    public void update(int key, Object newData) {
        BSTNode node = search(key);
        if (node != null) {
            node.data = newData;
        }
    }

    // 查找操作
    public BSTNode search(int key) {
        BSTNode current = root;
        while (current != null && current.key != key) {
            if (key < current.key) {
                current = current.leftChild;
            } else {
                current = current.rightChild;
            }
        }
        return current;
    }

    // 中序遍历操作
    public void inorderTraversal(BSTNode node, Queue queue, int eventType) {
        if (node != null) {
            inorderTraversal(node.leftChild, queue, eventType);
            Team team = (Team) node.data;
            if (team.getEventType().equals(String.valueOf(eventType))) { // 赛事类别匹配
                queue.enqueue(team);
            }
            sum += getNodeDepth(node);
            inorderTraversal(node.rightChild, queue, eventType);
        }
    }

    // 计算结点深度
    private int getNodeDepth(BSTNode node) {
        if (node == null || node == root) {
            return 0;
        }
        int depth = 1;
        BSTNode parent = node.parent;
        while (parent != null) {
            depth++;
            parent = parent.parent;
        }
        return depth;
    }

    // 二叉排序树结点类
    public class BSTNode {
        private int key;
        private Object data;
        private BSTNode parent;
        private BSTNode leftChild;
        private BSTNode rightChild;

        public BSTNode(int key, Object data) {
            this.key = key;
            this.data = data;
            parent = leftChild = rightChild = null;
        }

        public int getKey() {
            return key;
        }

        public Object getData() {
            return data;
        }

        public BSTNode getParent() {
            return parent;
        }

        public BSTNode getLeftChild() {
            return leftChild;
        }

        public BSTNode getRightChild() {
            return rightChild;
        }
    }
}

 

（3）能够提供按参赛学校查询参赛团队（或根据赛事类别查询参赛团队）

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

[待更新]...

（4）为省赛现场设计一个决赛叫号系统。

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

[待更新]...

（5）赛事系统为参赛者提供赛地的校园导游程序,为参赛者提供各种路径导航的查询服务。

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

[待更新]...

2.设计要求

1）赛事数据要求存入文件（txt或excel）并能读入查询；

2）赛地目的地查询,需提供目的地（建筑物）名称、代号、简介、两地之间路径长度等信息；

3）输入数据形式和范围：赛事相关数据可从键盘输入，或自文件导入。

4）界面要求：交互设计要合理，每个功能可以设计菜单，用户根据提示，完成相关功能的要求。