Rust算法与数据结构：实用指南

引言：为什么用Rust学习算法？

Rust是一种现代系统编程语言，结合了C/C++的高性能与内存安全性。对于学习算法与数据结构，Rust尤为出色，因为：

• 所有权控制（ownership）迫使你明确思考内存管理
• 安全性——编译器能避免许多运行时错误
• 速度——Rust编译为机器码，对高性能算法至关重要

在本文中，我们将通过实际代码示例，讲解在Rust中实现四种基础结构与算法。

1. 链表（Linked List）

经典数据结构之一。在Rust中，其实现需要使用Box在堆上分配内存，并用Option表示节点的存在与否。

单向链表的实现

// 定义链表节点#[derive(Debug)]struct Node<T> {    value: T,    next: Option<Box<Node<T>>>,}

// 链表本身#[derive(Debug)]struct LinkedList<T> {    head: Option<Box<Node<T>>>,}

impl<T> LinkedList<T> {    // 创建空链表    fn new() -> Self {        LinkedList { head: None }    }

    // 在头部添加元素    fn push_front(&mut self, value: T) {        let new_node = Box::new(Node {            value,            next: self.head.take(),        });        self.head = Some(new_node);    }

    // 从头部删除元素    fn pop_front(&mut self) -> Option<T> {        self.head.take().map(|node| {            self.head = node.next;            node.value        })    }}

fn main() {    let mut list = LinkedList::new();    list.push_front(10);    list.push_front(20);    list.push_front(30);    println!("{:?}", list); // LinkedList { head: Some(Node { value: 30, next: ... }) }        let popped = list.pop_front();    println!("删除了: {:?}", popped); // 删除了: Some(30)    println!("现在链表: {:?}", list);}

这里发生了什么：

• Box<Node>——指向堆中节点的指针
• Option——要么有节点（Some），要么没有（None）
• take()——从Option中取出值，留下None

2. 二叉搜索树（Binary Search Tree）

树是一种层次结构。在二叉搜索树中，每个节点有左子节点和右子节点，且左子节点小于根节点，右子节点大于根节点。

BST的实现

use std::cmp::Ordering;

#[derive(Debug)]struct TreeNode<T> {    value: T,    left: Option<Box<TreeNode<T>>>,    right: Option<Box<TreeNode<T>>>,}

#[derive(Debug)]struct BinarySearchTree<T> {    root: Option<Box<TreeNode<T>>>,}

impl<T: Ord> BinarySearchTree<T> {    fn new() -> Self {        BinarySearchTree { root: None }    }

    // 插入元素    fn insert(&mut self, value: T) {        let mut current = &mut self.root;        while let Some(node) = current {            match value.cmp(&node.value) {                Ordering::Less => current = &mut node.left,                Ordering::Greater => current = &mut node.right,                Ordering::Equal => return, // 忽略重复值            }        }        *current = Some(Box::new(TreeNode {            value,            left: None,            right: None,        }));    }

    // 查找元素    fn contains(&self, value: &T) -> bool {        let mut current = &self.root;        while let