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

Rust 算法与数据结构入门

Rust 编程语言凭借其高性能和严格的内存安全保证赢得了开发者的认可。然而，从 Python 或 JavaScript 等其他语言迁移到 Rust 可能颇具挑战，尤其是在实现经典算法和数据结构时。本文将探讨如何利用 Rust 的所有权（ownership）和借用（borrowing）系统特性，高效实现基本数据结构和算法。

本文面向已熟悉 Rust 基础的开发者。我们将重点放在可直接用于实际项目的实用代码示例上。所有示例均配有详细注释。

在 Rust 中实现链表

链表是基础数据结构之一。在 Rust 中，由于所有权规则的限制，其实现需要特别关注。下面我们使用 Box 进行内存管理，实现一个单向链表。

基础单向链表

首先定义节点和链表本身：

use std::fmt::Display;

#[derive(Debug)]struct Node<T> {    value: T,    next: Option<Box<Node<T>>>,}

#[derive(Debug)]struct LinkedList<T> {    head: Option<Box<Node<T>>>,    length: usize,}

impl<T> LinkedList<T> {    fn new() -> Self {        LinkedList {            head: None,            length: 0,        }    }

    fn push_front(&mut self, value: T) {        let new_node = Box::new(Node {            value,            next: self.head.take(),        });        self.head = Some(new_node);        self.length += 1;    }

    fn pop_front(&mut self) -> Option<T> {        self.head.take().map(|node| {            self.head = node.next;            self.length -= 1;            node.value        })    }

    fn is_empty(&self) -> bool {        self.head.is_none()    }

    fn len(&self) -> usize {        self.length    }}

请注意 Option<Box<Node<T>>> 的使用。这是在 Rust 中创建递归结构的标准方式，因为编译器需要预先知道类型大小。take() 方法可以安全地从 Option 中取出值，并将其替换为 None。

遍历链表

为链表实现迭代器：

impl<T: Clone> LinkedList<T> {    fn iter(&self) -> LinkedListIterator<T> {        LinkedListIterator {            current: self.head.as_deref(),        }    }}

struct LinkedListIterator<T> {    current: Option<&Node<T>>,}

impl<T> Iterator for LinkedListIterator<T> {    type Item = &T;

    fn next(&mut self) -> Option<Self::Item> {        self.current.take().map(|node| {            self.current = node.next.as_deref();            &node.value        })    }}

在 Rust 中实现二叉搜索树（BST）

树是另一种重要的数据结构。下面实现一个支持插入、搜索和遍历的二叉搜索树。

结构与基础插入操作

#[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 {            if value <