Rust中的算法与数据结构：初学者指南

面向初学者的在线Python训练器

轻松学习Python，无需理论负担。在浏览器中直接解决带自动检查的实践任务，无需安装任何东西。

开始课程

Rust中的算法与数据结构：初学者完整指南

Rust是一种编程语言，它将C/C++的高性能与编译时保证的内存安全性相结合。对于初学者开发者来说，学习Rust中的算法与数据结构不仅是掌握计算机科学基础概念的方法，也是理解该语言独特特性（所有权、借用和生命周期）的机会。

在本文中，我们将介绍每位开发者都应掌握的关键数据结构与算法。所有代码示例均用Rust编写，可直接运行。我们将从标准库提供的基本结构开始，然后转向经典算法的实现。

1. Rust中的基本数据结构

Rust标准库（std）提供了丰富的现成数据结构。我们来介绍其中最重要的三种。

向量（Vec<T>）

Vec<T>是一种动态数组，可以改变其大小。它类似于Java中的ArrayList或Python中的list。向量保证元素在内存中连续存储，这使得通过索引访问非常快（O(1)）。

fn main() {    // 创建一个空向量    let mut numbers: Vec<i32> = Vec::new();        // 添加元素    numbers.push(10);    numbers.push(20);    numbers.push(30);        // 通过索引访问    let first = numbers[0]; // 10        // 迭代    for num in &numbers {        println!("{}", num);    }        // 使用vec!宏    let fruits = vec!["apple", "banana", "cherry"];    println!("第二个水果: {}", fruits[1]); // banana}

哈希映射（HashMap<K, V>）

HashMap是一种存储键值对的数据结构。它提供平均O(1)的插入、查找和删除时间。非常适合需要根据键快速查找数据的任务。

use std::collections::HashMap;

fn main() {    let mut scores = HashMap::new();        scores.insert(String::from("Alice"), 100);    scores.insert(String::from("Bob"), 85);        // 根据键获取值    let alice_score = scores.get(&String::from("Alice"));    match alice_score {        Some(score) => println!("Alice得分: {}", score),        None => println!("未找到Alice"),    }        // 遍历所有键值对    for (name, score) in &scores {        println!("{}: {}", name, score);    }}

字符串（String）

Rust中有两种主要的字符串类型：&str（字符串切片）和String（可变的、拥有所有权的字符串）。由于UTF-8编码，在Rust中处理字符串需要特别注意。

fn main() {    let mut hello = String::from("你好， ");    hello.push_str("世界！"); // 追加字符串    hello.push('！'); // 追加字符        println!("{}", hello); // 你好， 世界！！        // 字符串切片（注意字符边界！）    let slice = &hello[0..9]; // "你好， "    println!("切片: {}", slice);}

2. 栈和队列的实现

栈和队列是基础的数据结构，常用于算法中。在Rust中，可以轻松地使用Vec来实现它们。

栈（LIFO — 后进先出）

栈遵循"后进先出"的原则。Vec已经提供了push和pop方法，这些方法实现了栈的行为。

fn main() {    let mut stack: Vec<i32> = Vec::new();        stack.push(1);    stack.push(2);    stack.push(3);        while let Some(top) = stack.pop() {        println!("弹出: {}", top);    }    // 输出: 3, 2, 1}