行业知识
手写数据结构(JAVA基础)
一.手写栈结构
在Java��，你可以手写一个栈（Stack）结构。栈是一种后进先出（LIFO, Last In First Out）的数据结构，它只允许在栈顶进行元素的添加和删除操作。
（）下面是一个简单的栈的实现示例：
public class MyStack { private List elements; public MyStack() { elements = new ArrayList(); } // 入栈操作 public void push(T element) { elements.add(element); } // 出栈操作 public T pop() { if (!isEmpty()) { return elements.remove(elements.size() - 1); } else { throw new EmptyStackException(); } } // 查看栈顶元素，不移除 public T peek() { if (!isEmpty()) { return elements.get(elements.size() - 1); } else { throw new EmptyStackException(); } } // 检查栈是否为空 public boolean isEmpty() { return elements.isEmpty(); } // 获取栈的大小 public int size() { return elements.size(); } // 清空栈 public void clear() { elements.clear(); } // 栈溢出异常 public static class EmptyStackException extends RuntimeException { private static final long serialVersionUID = 1L; public EmptyStackException() { super("Stack is empty"); } } // 测试 public static void main(String[] args) { MyStack stack = new MyStack(); stack.push(1); stack.push(2); stack.push(3); System.out.println(stack.peek()); // 输出 3 System.out.println(stack.pop()); // 输出 3 System.out.println(stack.pop()); // 输出 2 System.out.println(stack.pop()); // 输出 1 // 再次尝试出栈将抛出异常 try { stack.pop(); } catch (MyStack.EmptyStackException e) { System.out.println(e.getMessage()); } }} 在这个示例中，MyStack 类使用了一个 ArrayList 作为内部存储机制。push 方法用于向栈中添加元素，pop 方法用于移除并返回栈顶元素，peek 方法用于查看栈顶元素但不移除，isEmpty 方法用于检查栈是否为空，size 方法用于获取栈的大小，clear 方法用于清空栈。此外，还定义了一个内部异常类 EmptyStackException，用于在栈为空时抛出异常。
（）在 main 方法中，我们创建了一个 MyStack 实例，并演示了如何使用它进行基本的栈操作。
二.手写单向链表结构
在Java中，你可以手写一个单向链表（Singly Linked List）结构。单向链表由一系列节点组成，每个节点包含两部分：数据部分（用于存储数据）和链接部分（用于指向下一个节点）。
下面是一个简单的单向链表的实现示例：
public class Node { private T data; private Node next; public Node(T data) { this.data = data; } public T getData() { return data; } public void setData(T data) { this.data = data; } public Node getNext() { return next; } public void setNext(Node next) { this.next = next; }}public class SinglyLinkedList { private Node head; public SinglyLinkedList() { head = null; } // 添加元素到链表尾部 public void append(T data) { Node newNode = new Node(data); if (head == null) { head = newNode; } else { Node current = head; while (current.getNext() != null) { current = current.getNext(); } current.setNext(newNode); } } // 遍历链表并打印元素 public void printList() { Node current = head; while (current != null) { System.out.print(current.getData() + " "); current = current.getNext(); } System.out.println(); } // 测试 public static void main(String[] args) { SinglyLinkedList list = new SinglyLinkedList(); list.append(1); list.append(2); list.append(3); list.append(4); list.printList(); // 输出 1 2 3 4 }} 在这个示例中，Node 类表示单向链表中的一个节点，包含数据（data）和指向下一个节点的指针（next）。SinglyLinkedList 类是单向链表的实现，它有一个头节点（head）用于开始遍历链表。append 方法用于在链表尾部添加一个新元素，而 printList 方法则用于遍历链表并打印出所有元素。
在 main 方法中，我们创建了一个 SinglyLinkedList 实例，并添加了几个整数元素，然后调用 printList 方法打印链表的内容。
请注意，这个示例只包含了单向链表的基本操作，实际上一个完整的单向链表实现可能还会包括其他方法，如插入元素、删除元素、查找元素等。
三.手写双向链表结构
在Java中，你可以手写一个双向链表（Doubly Linked List）结构。双向链表与单向链表的主要区别在于，每个节点不仅有一个指向下一个节点的链接，还有一个指向前一个节点的链接。这使得双向链表可以从头到尾或从尾到头进行遍历。
下面是一个简单的双向链表的实现示例：
public class Node { private T data; private Node next; private Node prev; public Node(T data) { this.data = data; } public T getData() { return data; } public void setData(T data) { this.data = data; } public Node getNext() { return next; } public void setNext(Node next) { this.next = next; if (next != null) { next.setPrev(this); } } public Node getPrev() { return prev; } public void setPrev(Node prev) { this.prev = prev; }}public class DoublyLinkedList { private Node head; private Node tail; private int size; public DoublyLinkedList() { head = null; tail = null; size = 0; } // 添加元素到链表尾部 public void append(T data) { Node newNode = new Node(data); if (head == null) { head = newNode; tail = newNode; } else { tail.setNext(newNode); newNode.setPrev(tail); tail = newNode; } size++; } // 添加元素到链表头部 public void prepend(T data) { Node newNode = new Node(data); if (head == null) { head = newNode; tail = newNode; } else { newNode.setNext(head); head.setPrev(newNode); head = newNode; } size++; } // 遍历链表并打印元素 public void printList() { Node current = head; while (current != null) { System.out.print(current.getData() + " "); current = current.getNext(); } System.out.println(); } // 测试 public static void main(String[] args) { DoublyLinkedList list = new DoublyLinkedList(); list.append(1); list.append(2); list.append(3); list.prepend(0); list.printList(); // 输出 0 1 2 3 }} 在这个示例中，Node 类表示双向链表中的一个节点，它包含了数据（data）、指向下一个节点的指针（next）和指向前一个节点的指针（prev）。DoublyLinkedList 类是双向链表的实现，它维护了头节点（head）、尾节点（tail）和链表的大小（size）。append 方法用于在链表尾部添加一个新元素，而 prepend 方法用于在链表头部添加一个新元素。printList 方法则用于遍历链表并打印出所有元素。
在 main 方法中，我们创建了一个 DoublyLinkedList 实例，并添加了几个整数元素，然后调用 printList 方法打印链表的内容。注意，在添加新节点时，我们需要更新相邻节点的指针以保持链表的双向连接。
四.手写二叉树排序
在Java中，手写一个二叉树排序通常是指实现一个二叉搜索树（Binary Search Tree, BST）的插入和遍历方法，以保证树中的节点按照某种顺序排列。下面是一个简单的二叉搜索树的实现，包括插入和中序遍历（结果是有序的）的方法。
首先，我们定义一个二叉树节点的类：
public class TreeNode { int value; TreeNode left; TreeNode right; TreeNode(int value) { this.value = value; this.left = null; this.right = null; }} 然后，我们定义二叉搜索树类：
public class BinarySearchTree { TreeNode root; // 插入新节点 public void insert(int value) { root = insertRecursive(root, value); } private TreeNode insertRecursive(TreeNode node, int value) { if (node == null) { return new TreeNode(value); } if (value node.value) { node.right = insertRecursive(node.right, value); } return node; } // 中序遍历（左-根-右），结果是有序的 public void inorderTraversal(TreeNode node) { if (node != null) { inorderTraversal(node.left); System.out.println(node.value); inorderTraversal(node.right); } }} 最后，我们可以创建一个二叉搜索树实例并插入一些值，然后使用中序遍历来查看排序结果：
public class Main { public static void main(String[] args) { BinarySearchTree bst = new BinarySearchTree(); bst.insert(50); bst.insert(30); bst.insert(20); bst.insert(40); bst.insert(70); bst.insert(60); bst.insert(80); bst.inorderTraversal(bst.root); }} 运行上面的代码，你会看到输出结果是按升序排列的：20, 30, 40, 50, 60, 70, 80。这就是如何在Java中手写一个二叉树排序的例子。
五.手写树形数据结构
在Java中手写一个树形数据结构通常意味着实现一个基本的树结构，其中可以包括节点（Node）和树（Tree）类。节点类代表树中的单个元素，而树类代表整个树结构。以下是一个简单的树形数据结构的实现，包括节点类和树类。
首先，我们定义一个树节点类（TreeNode），它包含节点的值以及指向其子节点的引用：
public class TreeNode { T value; TreeNode left; TreeNode right; public TreeNode(T value) { this.value = value; this.left = null; this.right = null; }} 然后，我们可以定义一个树类（Tree），它包含一个根节点以及可能的一些树操作（如插入、遍历等）：
public class Tree { TreeNode root; public Tree(T value) { root = new TreeNode(value); } public Tree(TreeNode root) { this.root = root; } // 插入新节点（假设这是一个二叉搜索树） public void insert(T value) { root = insertRecursive(root, value); } private TreeNode insertRecursive(TreeNode node, T value) { if (node == null) { return new TreeNode(value); } if (value.compareTo(node.value) 0) { node.right = insertRecursive(node.right, value); } else { // 值已存在，不插入 } return node; } // 中序遍历（左-根-右） public void inorderTraversal(TreeNode node) { if (node != null) { inorderTraversal(node.left); System.out.println(node.value); inorderTraversal(node.right); } } // 前序遍历（根-左-右） public void preorderTraversal(TreeNode node) { if (node != null) { System.out.println(node.value); preorderTraversal(node.left); preorderTraversal(node.right); } } // 后序遍历（左-右-根） public void postorderTraversal(TreeNode node) { if (node != null) { postorderTraversal(node.left); postorderTraversal(node.right); System.out.println(node.value); } }} 在这个例子中，我们假设树是一个二叉搜索树（BST），这意味着对于树中的每个节点，其左子树中的所有元素值都小于该节点的值，而右子树中的所有元素值都大于该节点的值。
现在，我们可以创建一个Tree实例并插入一些值：
public class Main { public static void main(String[] args) { Tree tree = new Tree(50); tree.insert(30); tree.insert(20); tree.insert(40); tree.insert(70); tree.insert(60); tree.insert(80); // 遍历树 System.out.println("Inorder Traversal:"); tree.inorderTraversal(tree.root); System.out.println("\nPreorder Traversal:"); tree.preorderTraversal(tree.root); System.out.println("\nPostorder Traversal:"); tree.postorderTraversal(tree.root); }} 当你运行这个程序时，你将看到按照不同遍历顺序打印出来的节点值。中序遍历将给出排序后的结果。这个例子演示了如何在Java中手写一个简单的树形数据结构。当然，根据你的具体需求，你可以扩展这个基本框架来包括其他功能，如删除节点、查找节点、平衡树等。
下一篇：时间服务器异常怎么办?
