Реализация связанного списка на Rust

Введение

В этом лабораторном задании мы реализуем связанный список с использованием enum в Rust. Enum List имеет два варианта: Cons, представляющий узел с элементом и указателем на следующий узел, и Nil, означающий конец связанного списка. Enum имеет методы, такие как new для создания пустого списка, prepend для добавления элемента в начало списка, len для возврата длины списка и stringify для возврата строкового представления списка. Предоставленная главная функция демонстрирует использование этих методов для создания и манипулирования связанным списком.

Примечание: Если лабораторная работа не уточняет имя файла, вы можете использовать любое имя файла, которое хотите. Например, вы можете использовать main.rs, скомпилировать и запустить его с помощью rustc main.rs &&./main.

Тестовый случай: связанный список

Одним из распространенных способов реализации связанного списка является использование enum:

use crate::List::*;

enum List {
    // Cons: Тьюпловая структура, которая оборачивает элемент и указатель на следующий узел
    Cons(u32, Box<List>),
    // Nil: Узел, означающий конец связанного списка
    Nil,
}

// Методы могут быть прикреплены к enum
impl List {
    // Создайте пустой список
    fn new() -> List {
        // `Nil` имеет тип `List`
        Nil
    }

    // Создайте новый список, вставив элемент в начало списка
    fn prepend(self, elem: u32) -> List {
        // `Cons` также имеет тип List
        Cons(elem, Box::new(self))
    }

    // Возвращает длину списка
    fn len(&self) -> u32 {
        // `self` должен быть сопоставлен, так как поведение этого метода
        // зависит от варианта `self`
        // `self` имеет тип `&List`, а `*self` имеет тип `List`, поэтому сопоставление с
        // конкретным типом `T` предпочтительнее сопоставления с ссылкой `&T`
        // После Rust 2018 вы также можете использовать self здесь и tail (без ref) ниже,
        // Rust будет выводить &s и ref tail.
        // См. https://doc.rust-lang.org/edition-guide/rust-2018/ownership-and-lifetimes/default-match-bindings.html
        match *self {
            // Не получайте владение хвостом, так как `self` является заимствованной ссылкой;
            // вместо этого получите ссылку на хвост
            Cons(_, ref tail) => 1 + tail.len(),
            // Базовый случай: пустой список имеет длину 0
            Nil => 0
        }
    }

    // Возвращает представление списка в виде (кучи выделенной) строки
    fn stringify(&self) -> String {
        match *self {
            Cons(head, ref tail) => {
                // `format!` похож на `print!`, но возвращает кучу
                // выделенную строку вместо вывода на консоль
                format!("{}, {}", head, tail.stringify())
            },
            Nil => {
                format!("Nil")
            },
        }
    }
}

fn main() {
    // Создайте пустой связанный список
    let mut list = List::new();

    // Добавьте несколько элементов в начало списка
    list = list.prepend(1);
    list = list.prepend(2);
    list = list.prepend(3);

    // Показать конечное состояние списка
    println!("длина связанного списка: {}", list.len());
    println!("{}", list.stringify());
}

Резюме

Поздравляем! Вы завершили тестовый случай: лабораторную работу по связанным спискам. Вы можете практиковаться в более многих лабораторных работах в LabEx, чтобы улучшить свои навыки.