Rust数据结构实现：链表、树、哈希表与图

# Rust 数据结构实现：链表、树、哈希表与图 ## 1. 面向对象编程基础回顾 面向对象编程（OOP）是一种流行的编程范式，基于四大原则：继承、封装、抽象和多态。 - **继承**：对象可从其他对象继承数据和行为，无需重新定义。不过，Rust 不支持继承，而是推崇组合，因其更易用和实现。 - **封装**：限制对象实现细节对使用该对象代码的可见性。 - **抽象**：仅展示必要信息，隐藏其他细节。 - **多态**：代码能处理多种类型的数据，主要优势是代码复用。在 Rust 中，实现多态有静态分发和动态分发两种方式。 - **静态分发**：使用泛型和 trait 边界实现，性能高，但因单态化会使二进制文件变大。 - **动态分发**：使用 trait 对象在运行时实现多态，二进制文件小，但有性能开销。 ### 状态模式示例 状态模式是一种行为设计模式，当对象内部状态改变时，其行为也会改变。以下是一个简单的状态模式示例： ```rust trait State { fn process(&self); } struct Start; impl State for Start { fn process(&self) { println!("Started.."); } } struct Running; impl State for Running { fn process(&self) { println!("Running.."); } } struct Stop; impl State for Stop { fn process(&self) { println!("Stopped.."); } } struct StateContext { state: Box<dyn State> } impl StateContext { fn new() -> StateContext { StateContext { state: Box::new(Start {}), } } fn set_state(&mut self, s: Box<dyn State>) { self.state = s; } fn process(&self) { self.state.process(); } } fn main() { let mut ctxt = StateContext::new(); ctxt.process(); ctxt.set_state(Box::new(Running {})); ctxt.process(); ctxt.process(); ctxt.process(); ctxt.set_state(Box::new(Stop {})); ctxt.process(); } ``` 此示例中，`StateContext` 对象初始状态为 `Start`，调用 `process()` 方法时会体现该状态。后续状态多次改变，其行为也相应改变。 ## 2. 常见数据结构实现 ### 2.1 链表数据结构 链表是一种基础数据结构，分为单链表和双链表。本章实现单链表，虽实际应用中使用不多，但有助于学习。 - **节点结构**： ```rust struct Node<T> { data: T, next: Option<Box<Node<T>>>, } ``` - **链表结构**： ```rust pub struct LinkedList<T> { head: Option<Box<Node<T>>>, } ``` - **链表方法实现**： ```rust impl<T> LinkedList<T> { pub fn new() -> Self { LinkedList { head: None } } pub fn push(&mut self, data: T) { let node = Box::new(Node { data: data, next: self.head.take(), }); self.head = Some(node); } pub fn pop(&mut self) -> Option<T> { let val = self.head.take(); match val { Some(mut node) => { self.head = node.next.take(); Some(node.data) }, None => None } } pub fn length(&self) -> u8 { let mut len = 0; let mut n = &self.head; while let Some(ref node) = *n { n = &node.next; len += 1; } len } } ``` 以下是使用示例： ```rust fn main() { let mut list = LinkedList::new(); list.push(1); list.push(2); list.push(3); println!("Pop {}", list.pop().unwrap()); list.push(4); println!("Pop {}", list.pop().unwrap()); println!("length = {}", list.length()); } ``` ### 2.2 树、二叉树和二叉搜索树 树常用于表示层次数据，递归定义为节点集合。这里主要讨论二叉树，每个节点最多有两个子节点。 - **树节点结构**： ```rust pub struct TreeNode<T> { data: T, left: Option<Box<TreeNode<T>>>, right: Option<Box<TreeNode<T>>>, } ``` - **二叉树结构**： ```rust pub struct BinaryTree<T> { root: Option<Box<TreeNode<T>>>, } ``` - **二叉搜索树**：在二叉树基础上，左子树节点值小于等于当前节点，右子树节点值大于当前节点。 ```rust pub struct BinarySearchTree<T> { ```