Алгоритмы и структуры данных на 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 Some(node) = current {
            match value.cmp(&node.value) {
                Ordering::Less => current = &node.left,
                Ordering::Greater => current = &node.right,
                Ordering::Equal => return true,
            }
        }
        false
    }
}

fn main() {
    let mut bst = BinarySearchTree::new();
    bst.insert(5);
    bst.insert(3);
    bst.insert(7);
    bst.insert(2);
    bst.insert(4);
    
    println!("Содержит 4? {}", bst.contains(&4)); // true
    println!("Содержит 6? {}", bst.contains(&6)); // false
}

Ключевые моменты:

• Трейт Ord — требует, чтобы тип T можно было сравнивать
• Итерация через while let — безопасный обход по ссылкам
• Рекурсивная структура — каждый узел содержит потомков того же типа

3. Сортировка слиянием (Merge Sort)

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

Реализация Merge Sort

fn merge_sort<T: Ord + Clone>(arr: &mut [T]) {
    if arr.len() <= 1 {
        return;
    }

    let mid = arr.len() / 2;
    let mut left = arr[..mid].to_vec();
    let mut right = arr[mid..].to_vec();

    merge_sort(&mut left);
    merge_sort(&mut right);

    // Слияние двух отсортированных половин
    let mut i = 0;
    let mut j = 0;
    let mut k = 0;

    while i < left.len() && j < right.len() {
        if left[i] <= right[j] {
            arr[k] = left[i].clone();
            i += 1;
        } else {
            arr[k] = right[j].clone();
            j += 1;
        }
        k += 1;
    }

    // Дописываем остатки
    while i < left.len() {
        arr[k] = left[i].clone();
        i += 1;
        k += 1;
    }

    while j < right.len() {
        arr[k] = right[j].clone();
        j += 1;
        k += 1;
    }
}

fn main() {
    let mut numbers = vec![38, 27, 43, 3, 9, 82, 10];
    println!("До сорти