// 数据结构 – 上机考试：学生信息管理 // // 任务：用你自己实现的数据结构完成标有 TODO 的方法。 // 解答中不得使用 java.util 中的集合类（ArrayList、LinkedList、HashMap、TreeMap 等）。 // // 运行：java StudentRegistry.java // 最后程序按级别输出哪些检查通过（OK），哪些失败（FAIL）。 public class StudentRegistry { // ------------------------------------------------------------------ // 学生（不要修改！） // ------------------------------------------------------------------ static class Student { final int id; final String name; final int score; Student(int id, String name, int score) { this.id = id; this.name = name; this.score = score; } public String toString() { return id + " " + name + " " + score; } } // ------------------------------------------------------------------ // 第 1–3 级：单链表 // ------------------------------------------------------------------ static class StudentList { static class Node { Student data; Node next; Node(Student data, Node next) { this.data = data; this.next = next; } } Node head; // 第一个结点；空链表中为 null // 如有需要，可以增加其他字段（例如 tail、size）。 // 第 1 级：新学生加到链表的末尾 void add(Student s) { // >>> SOLUTION Node n = new Node(s, null); if (head == null) { head = n; return; } Node p = head; while (p.next != null) p = p.next; p.next = n; // <<< SOLUTION } // 第 1 级：学生人数 int size() { // >>> SOLUTION int c = 0; for (Node p = head; p != null; p = p.next) c++; return c; // <<< SOLUTION } // 第 1 级：按学号查找；没有这个学生时为 null Student find(int id) { // >>> SOLUTION for (Node p = head; p != null; p = p.next) if (p.data.id == id) return p.data; return null; // <<< SOLUTION } // 第 1 级：链表的文本形式，例如 "[1003 Li Wei 87, 1001 Wang Fang 92]"；空链表："[]" public String toString() { // >>> SOLUTION StringBuilder sb = new StringBuilder("["); for (Node p = head; p != null; p = p.next) { sb.append(p.data); if (p.next != null) sb.append(", "); } return sb.append("]").toString(); // <<< SOLUTION } // 第 2 级：删除给定学号的学生；如果有这个学生则返回 true boolean remove(int id) { // >>> SOLUTION Node prev = null, p = head; while (p != null && p.data.id != id) { prev = p; p = p.next; } if (p == null) return false; if (prev == null) head = p.next; else prev.next = p.next; return true; // <<< SOLUTION } // 第 2 级：分数的平均值；空链表为 0 double averageScore() { // >>> SOLUTION int n = 0, sum = 0; for (Node p = head; p != null; p = p.next) { n++; sum += p.data.score; } return n == 0 ? 0 : (double) sum / n; // <<< SOLUTION } // 第 2 级：分数最高的学生（并列时取链表中靠前的）；空链表为 null Student best() { // >>> SOLUTION Student b = null; for (Node p = head; p != null; p = p.next) if (b == null || p.data.score > b.score) b = p.data; return b; // <<< SOLUTION } // 第 3 级：插入后链表仍按分数降序排列； // 分数相同时，新学生排在已有学生的后面（稳定） void addSortedByScore(Student s) { // >>> SOLUTION if (head == null || s.score > head.data.score) { head = new Node(s, head); return; } Node p = head; while (p.next != null && p.next.data.score >= s.score) p = p.next; p.next = new Node(s, p.next); // <<< SOLUTION } // 第 3 级：原地逆置链表（不创建新结点） void reverse() { // >>> SOLUTION Node prev = null, p = head; while (p != null) { Node next = p.next; p.next = prev; prev = p; p = next; } head = prev; // <<< SOLUTION } } // ------------------------------------------------------------------ // 第 4 级：按学号组织的二叉搜索树 // ------------------------------------------------------------------ static class StudentBST { static class Node { Student data; Node left, right; Node(Student data) { this.data = data; } } Node root; // 第 4 级：插入（键：id）；如果学号已经存在，就不再插入 void insert(Student s) { // >>> SOLUTION root = insert(root, s); // <<< SOLUTION } // >>> SOLUTION private Node insert(Node p, Student s) { if (p == null) return new Node(s); if (s.id < p.data.id) p.left = insert(p.left, s); else if (s.id > p.data.id) p.right = insert(p.right, s); return p; } private int height(Node p) { return p == null ? -1 : 1 + Math.max(height(p.left), height(p.right)); } private void inorder(Node p, StringBuilder sb) { if (p == null) return; inorder(p.left, sb); if (sb.length() > 1) sb.append(", "); sb.append(p.data.id); inorder(p.right, sb); } // <<< SOLUTION // 第 4 级：按学号查找；找不到时为 null Student find(int id) { // >>> SOLUTION Node p = root; while (p != null && p.data.id != id) p = (id < p.data.id) ? p.left : p.right; return p == null ? null : p.data; // <<< SOLUTION } // 第 4 级：树的高度（空树：-1，只有一个结点：0） int height() { // >>> SOLUTION return height(root); // <<< SOLUTION } // 第 4 级：按中序排列的学号，例如 "[1001, 1002, 1003]" String inorderIds() { // >>> SOLUTION StringBuilder sb = new StringBuilder("["); inorder(root, sb); return sb.append("]").toString(); // <<< SOLUTION } } // ================================================================== // 检查程序 – 不要修改！ // ================================================================== static int ok, fail; static void check(String what, boolean cond) { if (cond) ok++; else fail++; System.out.println(" " + (cond ? "OK " : "FAIL ") + what); } static Student[] sample() { return new Student[] { new Student(1003, "Li Wei", 87), new Student(1001, "Wang Fang", 92), new Student(1005, "Chen Jie", 78), new Student(1002, "Zhang Min", 92), new Student(1004, "Anna Kovács", 65) }; } interface Level { void run(); } static boolean level(String title, Level body) { System.out.println(title); int failBefore = fail; try { body.run(); } catch (UnsupportedOperationException e) { System.out.println(" --- not solved yet"); return false; } catch (RuntimeException e) { fail++; System.out.println(" FAIL exception: " + e); return false; } return fail == failBefore; } public static void main(String[] args) { boolean l1 = level("Level 1 (pass): add, size, find, toString", () -> { StudentList l = new StudentList(); check("empty list: size() == 0 and \"[]\"", l.size() == 0 && l.toString().equals("[]")); for (Student s : sample()) l.add(s); check("after 5 students size() == 5", l.size() == 5); check("the order is the insertion order", l.toString().equals( "[1003 Li Wei 87, 1001 Wang Fang 92, 1005 Chen Jie 78, 1002 Zhang Min 92, 1004 Anna Kovács 65]")); check("find(1005) -> Chen Jie", l.find(1005) != null && l.find(1005).name.equals("Chen Jie")); check("find(9999) -> null", l.find(9999) == null); }); boolean l2 = l1 && level("Level 2 (satisfactory): remove, averageScore, best", () -> { StudentList l = new StudentList(); check("empty list: averageScore() == 0 and best() == null", l.averageScore() == 0 && l.best() == null); for (Student s : sample()) l.add(s); check("remove(1005) true", l.remove(1005)); check("remove(9999) false", !l.remove(9999)); check("after deletion size() == 4 and find(1005) == null", l.size() == 4 && l.find(1005) == null); check("deleting the first element: remove(1003)", l.remove(1003) && l.toString().startsWith("[1001")); check("averageScore() == 83.0", Math.abs(l.averageScore() - 83.0) < 1e-9); check("best() -> Wang Fang (on a tie the earlier one)", l.best() != null && l.best().name.equals("Wang Fang")); }); boolean l3 = l2 && level("Level 3 (good): addSortedByScore, reverse", () -> { StudentList l = new StudentList(); for (Student s : sample()) l.addSortedByScore(s); check("descending score, stable order", l.toString().equals( "[1001 Wang Fang 92, 1002 Zhang Min 92, 1003 Li Wei 87, 1005 Chen Jie 78, 1004 Anna Kovács 65]")); l.addSortedByScore(new Student(1006, "Liu Yang", 100)); l.addSortedByScore(new Student(1007, "Zhou Lan", 50)); check("insertion at the beginning and at the end of the list", l.toString().startsWith("[1006") && l.toString().endsWith("Zhou Lan 50]")); l.reverse(); check("reverse()", l.toString().startsWith("[1007 Zhou Lan 50, 1004") && l.toString().endsWith("1006 Liu Yang 100]")); StudentList e = new StudentList(); e.reverse(); check("reversing an empty list", e.toString().equals("[]")); }); boolean l4 = l3 && level("Level 4 (excellent): StudentBST – insert, find, height, inorderIds", () -> { StudentBST t = new StudentBST(); check("empty tree: height() == -1", t.height() == -1); for (Student s : sample()) t.insert(s); t.insert(new Student(1003, "Duplicate", 0)); check("inorderIds() sorted", t.inorderIds().equals("[1001, 1002, 1003, 1004, 1005]")); check("height() == 2", t.height() == 2); check("find(1004) -> Anna Kovács, find(1) -> null", t.find(1004) != null && t.find(1004).name.equals("Anna Kovács") && t.find(1) == null); check("a duplicate id is not inserted", t.find(1003).name.equals("Li Wei")); // 测量：20 000 个学生，在链表和二叉搜索树中各查找 20 000 次 java.util.Random rnd = new java.util.Random(2026); StudentList list = new StudentList(); StudentBST tree = new StudentBST(); int n = 20_000; int[] ids = new int[n]; for (int i = 0; i < n; i++) { ids[i] = 100_000 + rnd.nextInt(900_000); Student s = new Student(ids[i], "S" + i, rnd.nextInt(101)); list.head = new StudentList.Node(s, list.head); // 在表头快速填充 tree.insert(s); } long t0 = System.nanoTime(); int found1 = 0; for (int id : ids) if (list.find(id) != null) found1++; long t1 = System.nanoTime(); int found2 = 0; for (int id : ids) if (tree.find(id) != null) found2++; long t2 = System.nanoTime(); System.out.printf(" measurement: %d searches – list: %.1f ms, search tree: %.1f ms, tree height: %d%n", n, (t1 - t0) / 1e6, (t2 - t1) / 1e6, tree.height()); check("both structures find every element", found1 == n && found2 == n); check("the height of the search tree is small (< 60)", tree.height() < 60); }); String grade = l4 ? "excellent (5)" : l3 ? "good (4)" : l2 ? "satisfactory (3)" : l1 ? "pass (2)" : "fail (1)"; System.out.println("\nPassed checks: " + ok + ", failed: " + fail); System.out.println("Level reached according to the automatic check: " + grade + " (the final grade is set by the instructor based on the code and the oral explanation)"); } }