Data Structures and Algorithms Coursework2

Basic rules#

• You must create at least one executable project after completing all tasks.
  完成所有任务后，你必须创建至少一个可执行项目。
• Do not use built-in collection libraries
  (e.g., java.util.ArrayDeque, java.util.Deque, java.util.TreeMap, java.util.ArrayList/LinkedList) for the core implementations. Use basic arrays and your own classes.
  核心实现不得使用内置集合库
  （例如 java.util.ArrayDeque、java.util.Deque、java.util.TreeMap、java.util.ArrayList/LinkedList）。应使用基本数组和你自己的类。
• All code must adhere to good programming practices (comments, meaningful naming).
  所有代码都必须遵循良好的编程实践，包括适当注释和有意义的命名。

Task 1: Binary Search Tree Implementation#

任务 1：二叉搜索树实现

Design and implement a binary search tree data structure.
设计并实现一个二叉搜索树数据结构。

• The binary search tree should be a generic data structure that can store elements of integer data type.
  二叉搜索树应作为一种通用数据结构，能够存储整数类型的数据元素。
• Implement a TreeNode class that represents each node in the binary search tree. Each node should contain the data, a reference to the left child node, and a reference to the right child node.
  实现一个 TreeNode 类，用于表示二叉搜索树中的每个节点。每个节点应包含数据、指向左子节点的引用以及指向右子节点的引用。
  1. The node class should have appropriate constructors and accessor methods.
     节点类应具有合适的构造方法和访问器方法。
  2. It should maintain the integrity of the binary search tree structure and the ordering property.
     它应维护二叉搜索树结构的完整性以及排序性质。
• Implement a BinarySearchTree class that represents the binary search tree itself. It should include methods for inserting nodes, deleting nodes, performing pre-order traversal, in-order traversal, post-order traversal, searching for a specific value, and returning the height of the tree.
  实现一个 BinarySearchTree 类，用于表示二叉搜索树本身。该类应包含插入节点、删除节点、执行前序遍历、中序遍历、后序遍历、搜索特定值以及返回树高度的方法。
  1. For the pre-order traversal method, it should visit the root node first, then recursively traverse the left subtree, and finally the right subtree. The method should return a list of the visited nodes in the preorder sequence.
     对于前序遍历方法，应先访问根节点，然后递归遍历左子树，最后遍历右子树。该方法应返回按前序顺序访问到的节点列表。
  2. For the in-order traversal method, it should recursively traverse the left subtree first, then visit the root node, and finally the right subtree. The method should return a list of the visited nodes in the in-order sequence.
     对于中序遍历方法，应先递归遍历左子树，然后访问根节点，最后遍历右子树。该方法应返回按中序顺序访问到的节点列表。
  3. For the post-order traversal method, it should recursively traverse the left subtree first, then the right subtree, and finally visit the root node. The method should return a list of the visited nodes in the post-order sequence.
     对于后序遍历方法，应先递归遍历左子树，再遍历右子树，最后访问根节点。该方法应返回按后序顺序访问到的节点列表。
  4. The insertion operation should maintain the binary search tree property (i.e., for each node, all values in the left subtree are less than the node’s value, and all values in the right subtree are greater than the node’s value). In case of duplicate values, handle them according to a predefined rule (e.g., allow duplicates and insert them either to the left or right subtree based on a specific criterion).
     插入操作应保持二叉搜索树性质（即对于每个节点，左子树中的所有值都小于该节点的值，右子树中的所有值都大于该节点的值）。如果出现重复值，应根据预先定义的规则进行处理（例如允许重复值，并根据特定标准将其插入左子树或右子树）。
  5. The deletion operation should handle different cases (leaf node, node with one child, node with two children) properly while maintaining the binary search tree property.
     删除操作应在保持二叉搜索树性质的同时，正确处理不同情况（叶子节点、只有一个子节点的节点、具有两个子节点的节点）。
  6. The search operation should return the node if the value is found or null otherwise.
     搜索操作在找到目标值时应返回对应节点，否则返回 null。
  7. The height calculation method should return the correct height of the tree.
     高度计算方法应返回树的正确高度。
• The implementation should include error handling to handle errors such as deleting a non-existent node and searching for a value in an empty tree.
  实现中应包含错误处理，用于处理删除不存在的节点、在空树中搜索值等错误情况。
  1. Provide meaningful error messages to help users understand the problem.
     提供有意义的错误信息，帮助用户理解问题。
• Test the implementation.
  测试该实现。
  1. Create a set of 500 random integer data in an unordered sequence.
     创建一组包含 500 个随机整数的无序数据。
  2. Create an object of the BinarySearchTree.
     创建一个 BinarySearchTree 对象。
  3. Using the integer set to test the functionality and correctness of the object.
     使用该整数集合测试对象的功能和正确性。

Task 2: Stack and Priority Queue Implementation#

任务 2：栈和优先队列实现

Design and implement a stack and a priority queue data structure.
设计并实现栈和优先队列数据结构。

• The stack should be a Last-In-First-Out (LIFO) data structure that can store elements of the string data type.
  栈应是一个后进先出（LIFO）的数据结构，能够存储字符串类型的数据元素。
  1. Implement a StackNode class and a Stack class. The Stack class should include methods for pushing elements onto the stack, popping elements from the stack, checking if the stack is empty, and getting the size of the stack.
     实现一个 StackNode 类和一个 Stack 类。Stack 类应包含将元素压入栈、从栈中弹出元素、检查栈是否为空以及获取栈大小的方法。
  2. The implementation should handle stack overflow and underflow conditions gracefully.
     实现应妥善处理栈溢出和栈下溢情况。
• The priority queue should be a data structure that can store elements of the string data type and prioritize them based on a priority function.
  优先队列应是一种能够存储字符串类型元素的数据结构，并根据优先级函数对元素进行优先级排序。
  1. Implement a PriorityQueueNode class and a PriorityQueue class. The PriorityQueue class should include methods for enqueuing elements into the queue, dequeuing elements from the queue, checking if the queue is empty, and retrieving the size of the queue.
     实现一个 PriorityQueueNode 类和一个 PriorityQueue 类。PriorityQueue 类应包含入队、出队、检查队列是否为空以及获取队列大小的方法。
  2. Implement a priority function that changes the priority of an element based on an integer value.
     实现一个优先级函数，根据整数值改变元素的优先级。
  3. The implementation should ensure that elements are dequeued in the correct priority order.
     实现应确保元素按照正确的优先级顺序出队。
• Test the implementation.
  测试该实现。
  1. Create an object of the Stack class and an object of the PriotityQueue class.
     创建一个 Stack 类对象和一个 PriotityQueue 类对象。
  2. Design test cases to test the functionality and correctness of the object.
     设计测试用例来测试对象的功能和正确性。

Task 3: Graph Implementation#

任务 3：图实现

Design and implement a graph data structure.
设计并实现一个图数据结构。

• The graph should be represented using an adjacency list.
  图应使用邻接表表示。
  1. The adjacency list should be implemented by using the doubly linked list structure.
     邻接表应使用双向链表结构实现。
  2. It should handle the storage of vertex and edge information appropriately.
     它应能够适当地存储顶点和边的信息。
• Design and implement a Graph class that represents the graph. It should include methods for adding vertices, adding edges between vertices, removing vertices, removing edges, checking if two vertices are adjacent, performing depth-first traversal (DFT) and breadth-first traversal (BFT), and using the stack and priority queue implemented in Task 2 for specific graph operations (e.g., using the stack for topological sorting or the priority queue for Dijkstra’s algorithm implementation).
  设计并实现一个表示图的 Graph 类。该类应包含添加顶点、在顶点之间添加边、删除顶点、删除边、检查两个顶点是否相邻、执行深度优先遍历（DFT）和广度优先遍历（BFT）的方法，并在特定图操作中使用任务 2 中实现的栈和优先队列（例如使用栈进行拓扑排序，或使用优先队列实现 Dijkstra 算法）。
  1. The adding vertices method should update the graph structure correctly.
     添加顶点的方法应正确更新图结构。
  2. The adding edges method should handle weighted and unweighted edges properly.
     添加边的方法应正确处理带权边和无权边。
  3. The removing vertices method should remove all associated edges as well.
     删除顶点的方法也应删除所有相关边。
  4. The removing edges method should update the graph structure accordingly.
     删除边的方法应相应地更新图结构。
  5. The adjacent check method should return true or false accurately.
     相邻检查方法应准确返回 true 或 false。
  6. For the DFT method, it should start from a given vertex and explore as deep as possible along each branch before backtracking. The method should return a list of vertices visited in the order of traversal.
     对于 DFT 方法，应从给定顶点开始，在回溯之前沿每个分支尽可能深入地探索。该方法应返回按遍历顺序访问到的顶点列表。
  7. For the BFT method, it should start from a given vertex and visit all the vertices at the current level before moving to the next level. The method should return a list of vertices visited in the order of traversal.
     对于 BFT 方法，应从给定顶点开始，先访问当前层级的所有顶点，再移动到下一层级。该方法应返回按遍历顺序访问到的顶点列表。
• The implementation should handle the case of weighted and unweighted edges.
  实现应能够处理带权边和无权边的情况。
  1. Store and access the weight information correctly if applicable.
     如适用，应正确存储和访问权重信息。
  2. Differentiate between weighted and unweighted operations when necessary.
     必要时应区分带权和无权操作。
• The implementation should include error handling to handle errors such as adding an edge between non-existent vertices and removing a non-existent vertex.
  实现中应包含错误处理，用于处理在不存在的顶点之间添加边、删除不存在的顶点等错误情况。
  1. Provide appropriate error handling and feedback.
     提供适当的错误处理和反馈。
  2. Ensure the graph remains in a consistent state after error handling.
     确保图在错误处理后仍保持一致状态。
• Test the implementation.
  测试该实现。
  1. Design a graph that contains at least 10 vertices and more than 30 edges. Generate an object of the Graph class according to the graph you designed.
     设计一个至少包含 10 个顶点且超过 30 条边的图，并根据设计创建一个 Graph 类对象。
  2. Design and use test cases to test the functionality and correctness of the object.
     设计并使用测试用例来测试对象的功能和正确性。

Task 4: Path Finding Algorithm Implementation#

任务 4：路径查找算法实现

Implement Dijkstra’s algorithm to find the shortest path between two vertices in the graph implemented in Task 3.
实现 Dijkstra 算法，用于在任务 3 实现的图中查找两个顶点之间的最短路径。

• Implement a method within the Graph class to implement these algorithms.
  在 Graph 类中实现一个方法来完成这些算法。
  1. The start and the end vertex for path-finding could be set manually.
     路径查找的起点和终点可以手动设置。
• The implementation should use the data structures created in Task 2 if needed.
  如有需要，实现应使用任务 2 中创建的数据结构。
• The implementation should return the shortest path and its length.
  实现应返回最短路径及其长度。 2. The path should be represented in a suitable format (e.g., a list of vertices).
  路径应以合适的格式表示（例如顶点列表）。 3. The length should be calculated accurately.
  路径长度应准确计算。
• The implementation should handle the case as no path between the two vertices.
  实现应处理两个顶点之间不存在路径的情况。
  1. Return an appropriate indication (e.g., null or a special value) when no path exists.
     当不存在路径时，应返回适当的标识（例如 null 或特殊值）。
• The implementation should include error handling to handle errors such as invalid vertex inputs.
  实现中应包含错误处理，用于处理无效顶点输入等错误情况。
  1. Validate the vertex inputs and provide error messages if they are incorrect.
     验证顶点输入；如果输入不正确，应提供错误信息。
• Test the implementation.
  测试该实现。
  1. Design and use test cases to test the functionality and correctness of the methods.
     设计并使用测试用例来测试这些方法的功能和正确性。

Task 5 Complexity Comparison and Analysis (Annotation)#

任务 5：复杂度比较与分析（注释）

Analyse and compare the time and space complexities of all the implementations in Tasks 1 through 4. Write the analysis and conclusion as a block annotation in each task implementation.
分析并比较任务 1 到任务 4 中所有实现的时间复杂度和空间复杂度。将分析和结论以块注释的形式写入每个任务的实现中。

• For the binary search tree, analyze the complexity of insertion, deletion, traversal (pre-order, in-order, post-order), and search operations in different scenarios (e.g., best case, average case, worst case).
  对于二叉搜索树，需要分析插入、删除、遍历（前序、中序、后序）和搜索操作在不同场景下的复杂度（例如最好情况、平均情况、最坏情况）。
• For the graph, compare the complexity of adding vertices, adding edges, removing vertices, removing edges, DFT, BFT, and the path-finding algorithms when applied to different graph types (e.g., sparse graphs, dense graphs).
  对于图，需要比较添加顶点、添加边、删除顶点、删除边、DFT、BFT 以及路径查找算法在不同图类型（例如稀疏图、稠密图）中的复杂度。
• Explain the factors that influence the complexity in each case and discuss any trade-offs between different data structures and algorithms.
  解释每种情况下影响复杂度的因素，并讨论不同数据结构与算法之间的权衡。