Алгоритмы и структуры данных на Rust: руководство для начинающих

Алгоритмы и структуры данных на Rust: полный гид для начинающих

Rust — язык программирования, который сочетает высокую производительность C/C++ с безопасностью памяти, гарантируемой на этапе компиляции. Для начинающих разработчиков изучение алгоритмов и структур данных на Rust — это не только способ освоить фундаментальные концепции Computer Science, но и возможность понять уникальные особенности языка: владение (ownership), заимствование (borrowing) и время жизни (lifetimes).

В этой статье мы разберём ключевые структуры данных и алгоритмы, которые должен знать каждый разработчик. Все примеры кода написаны на Rust и готовы к запуску. Мы начнём с базовых структур, предоставляемых стандартной библиотекой, а затем перейдём к реализации классических алгоритмов.

1. Основные структуры данных в Rust

Стандартная библиотека Rust (std) предоставляет богатый набор готовых структур данных. Рассмотрим три самые важные из них.

Векторы (Vec)

Vec — это динамический массив, который может изменять свой размер. Это аналог ArrayList в Java или list в Python. Векторы гарантируют непрерывное расположение элементов в памяти, что делает доступ по индексу очень быстрым (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)

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 (изменяемая, владеющая строка). Работа со строками в Rust требует внимания из-за UTF-8 кодировки.

fn main() {
    let mut hello = String::from("Привет, ");
    hello.push_str("мир!"); // Добавление строки
    hello.push('!'); // Добавление символа
    
    println!("{}", hello); // Привет, мир!!
    
    // Срезы строк (осторожно с границами символов!)
    let slice = &hello[0..7]; // "Привет"
    println!("Срез: {}", slice);
}

2. Реализация стека и очереди

Стек и очередь — это фундаментальные структуры данных, которые часто используются в алгоритмах. В Rust их можно легко реализовать с помощью Vec.

Стек (LIFO — Last In, First Out)

Стек работает по принципу "последним пришёл — первым вышел". 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
}

Очередь (FIFO — First In, First Out)

Для реализации очереди можно использовать VecDeque из стандартной библиотеки. Она поддерживает эффективные операции добавления и удаления с обоих концов.

use std::collections::VecDeque;

fn main() {
    let mut queue: VecDeque<i32> = VecDeque::new();
    
    queue.push_back(1);
    queue.push_back(2);
    queue.push_back(3);
    
    while let Some(front) = queue.pop_front() {
        println!("Обрабатываем: {}", front);
    }
    // Вывод: 1, 2, 3
}

3. Алгоритмы сортировки: пузырьковая и быстрая

Сортировка — одна из самых часто встречающихся задач. Хотя в Rust есть встроенная сортировка через метод .sort(), понимание алгоритмов поможет вам в решении более сложных задач.

Пузырьковая сортировка (Bubble Sort)

Простой, но неэффективный алгоритм (O(n²)). Полезна для обучения и работы с маленькими массивами.

fn bubble_sort(arr: &mut [i32]) {
    let n = arr.len();
    for i in 0..n {
        for j in 0..n - 1 - i {
            if arr[j] > arr[j + 1] {
                arr.swap(j, j + 1);
            }
        }
    }
}

fn main() {
    let mut numbers = [64, 34, 25, 12, 22, 11, 90];
    bubble_sort(&mut numbers);
    println!("Отсортировано: {:?}", numbers);
}

Быстрая сортировка (Quick Sort)

Один из самых эффективных алгоритмов сортировки (в среднем O(n log n)). Работает по принципу "разделяй и властвуй".

fn quick_sort(arr: &mut [i32]) {
    if arr.len() <= 1 {
        return;
    }
    
    let pivot_index = partition(arr);
    let (left, right) = arr.split_at_mut(pivot_index);
    
    quick_sort(left);
    quick_sort(&mut right[1..]); // Исключаем опорный элемент
}

fn partition(arr: &mut [i32]) -> usize {
    let pivot = arr[arr.len() - 1];
    let mut i = 0;
    
    for j in 0..arr.len() - 1 {
        if arr[j] <= pivot {
            arr.swap(i, j);
            i += 1;
        }
    }
    arr.swap(i, arr.len() - 1);
    i
}

fn main() {
    let mut numbers = [10, 7, 8, 9, 1, 5];
    quick_sort(&