Keyboard shortcuts

Press ← or → to navigate between chapters

Press S or / to search in the book

Press ? to show this help

Press Esc to hide this help

基本数据结构

目录

线性数据结构

Rust 中的线性数据结构如下：

  • 数组（Array）：[T; N]
  • 向量（Vec）：Vec<T>
  • 队列（Queue）：std::collections::VecDeque<T>
  • 双端队列（VecDeque）：VecDeque<T>
  • 链表：LinkedList<T>
  • 栈（Stack）：Vec<T> 或 VecDeque<T>

1、数组

  • 定义：Array 是 Rust 中的一种基本数据结构，表示固定长度的同构元素集合，类型为 [T; N]，其中 T 是元素类型，N 是长度，在编译时确定。
  • 内存分配：存储在栈上，内存是连续的，分配大小在编译时已知。
  • 所有权：Array 是值类型。如果其元素实现了 Copy trait（如 i32），则数组也实现 Copy，复制时不转移所有权；否则（如 String），会转移所有权。
  • 可变性：长度不可变，但元素可以通过可变绑定（mut）修改。
  • 使用场景：适合需要固定大小且数量已知的数据集合，例如坐标点、固定长度的缓冲区等。
  • 性能：由于栈分配，访问和操作效率高，没有额外的内存管理开销。

用法示例

2、向量

  • 定义：Vec 是 Rust 标准库（std::vec）提供的一种动态数组，类型为 Vec<T>，可以存储任意数量的同构元素。
  • 内存分配：存储在堆上，通过 Rust 的内存分配器管理，内存是连续的，支持动态调整大小。
  • 所有权：Vec 是拥有者类型，拥有其元素的所有权。移动时（如赋值给新变量），原 Vec 不可用，除非元素是 Copy 类型。
  • 可变性：长度和元素都可变，支持动态扩展（push）和缩减（pop）等操作。
  • 使用场景：适合需要运行时动态调整大小的数据集合，例如列表、队列或需要追加元素的场景。
  • 性能：因堆分配，操作（如 push）平均时间复杂度为 O(1)，但当容量不足时需要重新分配内存，可能为 O(n)。

Vec 内部维护三个主要字段：

  • 指针：指向堆上分配的内存，存储实际元素。
  • 长度：当前存储的元素数量（len）。
  • 容量：分配的内存能容纳的元素数量（capacity）。 当 len 接近或超过 capacity 时，Vec 会重新分配更大的内存（通常以 2 倍增长），并将现有元素复制到新内存。

用法示例+[实现]

3、队列

Rust 的标准库提供了 std::collections::VecDeque，这是一个高效的双端队列（double-ended queue），既支持队列的 FIFO 操作，也支持栈的 LIFO 操作，非常适合实现队列。

  • 先进先出（FIFO）：先入队的元素先出队。
  • 线性结构：元素按顺序排列，尾部入队，头部出队。
  • 高效首尾操作：入队（push_back）和出队（pop_front）通常为 O(1)。
  • 单向访问：通常只访问头部（front）或尾部添加，不支持随机访问。
  • 动态大小：可动态增长或缩小。
  • 有限容量（可选）：可设置最大容量，超限需特殊处理。
  • 线程安全性（视实现）：VecDeque 非线程安全，需 Mutex 或用 std::sync::mpsc。
  • 变体：支持双端队列（VecDeque）、优先级队列（BinaryHeap）等。

用法示例+实现

4、双端队列

  • 双端操作：支持在队列头部和尾部进行添加（push）和移除（pop）。
  • 先进先出/后进先出：可实现 FIFO（队列）或 LIFO（栈）行为。
  • 高效首尾操作：头部和尾部操作（如 push_front、pop_front、push_back、pop_back）均摊复杂度为 O(1)。
  • 动态大小：可动态增长或缩小，元素数量不固定。
  • 随机访问：支持通过索引访问任意元素（O(1)）。
  • 内存连续：元素通常存储在连续内存中，缓存友好。
  • 非线程安全：标准实现（如 VecDeque）需配合锁用于多线程。
  • 灵活变体：可作为队列、栈或双端队列使用。

用法示例+实现

5、链表

  • 动态结构：链表通过指针连接节点，允许动态分配和释放内存，适合大小不固定的数据。
  • 非连续存储：节点在内存中不连续，插入和删除操作效率高（O(1)），但随机访问效率低（O(n)）。
  • 灵活性：支持单向、双向、循环等多种形式，适应不同场景。
  • 空间开销：每个节点需额外存储指针，占用更多内存。
  • 顺序访问：遍历需从头或尾开始，无法直接跳跃到任意节点。

用法示例+实现

6、栈

Rust 没有专门的栈类型或 API，但 Vec<T> 的 push、pop、last等方法提供了高效、封装好的栈操作，足以满足 LIFO 需求。

  • LIFO 顺序：最后压入（push）的元素最先弹出（pop），类似堆叠的盘子。
  • 高效操作：压入（push）和弹出（pop）操作通常为 O(1) 时间复杂度。
  • 受限访问：只能操作栈顶元素，无法直接访问中间元素。
  • 内存管理：栈通常在连续内存中实现（如数组）或通过链表实现，Rust 中常用 Vec 作为栈的底层结构。
  • 用途：
    • 函数调用管理（调用栈）。
    • 表达式求值（如中缀转后缀）。
    • 回溯算法（如深度优先搜索）。
    • 撤销/重做功能。

vec实现+队列实现

进制转换实现

括号匹配实现

栈的实现

特殊类型结构

切片

  • 定义：切片是 Rust 中用于访问连续数据子集的引用类型，分为字符串切片（&str）和数组切片（&[T]）
    • 字符串切片（&str）：专门用于 UTF-8 编码的字符串数据，引用 String 或字符串字面量的一部分。
    • 数组切片（&[T]）：引用数组、Vec<T> 或其他连续序列的一部分，T 是任意类型。
  • 特点：轻量、内存安全、不拥有数据，支持只读或可变访问。
  • 使用场景：函数参数、字符串处理、数组操作、避免数据拷贝。
  • 优势：结合 Rust 的借用规则，切片提供高效、灵活的数据访问方式。

用法示例

字符串

  • 定义：String 是 Rust 标准库中用于动态、可变字符串的拥有类型，基于堆分配，支持 UTF-8 编码。
  • 特点：拥有所有权、可变、动态增长，与 &str 配合灵活。
  • 使用场景：动态字符串构建、 字符串修改、 与切片配合、 多语言支持、 临时缓冲。

用法示例