Algorithmen und Datenstrukturen in Rust: Ein Leitfaden für Anfänger

Online Python-Trainer für Anfänger

Lernen Sie Python einfach ohne theoretische Überlastung. Lösen Sie praktische Aufgaben mit automatischer Überprüfung und schreiben Sie Code direkt im Browser.

Kurs starten

Algorithmen und Datenstrukturen in Rust: Ein vollständiger Leitfaden für Anfänger

Rust ist eine Programmiersprache, die die hohe Leistung von C/C++ mit der Speichersicherheit kombiniert, die zur Kompilierzeit garantiert wird. Für angehende Entwickler ist das Erlernen von Algorithmen und Datenstrukturen in Rust nicht nur eine Möglichkeit, grundlegende Konzepte der Informatik zu meistern, sondern auch eine Gelegenheit, die einzigartigen Besonderheiten der Sprache zu verstehen: Ownership, Borrowing und Lifetimes.

In diesem Artikel behandeln wir die wichtigsten Datenstrukturen und Algorithmen, die jeder Entwickler kennen sollte. Alle Codebeispiele sind in Rust geschrieben und startbereit. Wir beginnen mit den grundlegenden Strukturen der Standardbibliothek und gehen dann zur Implementierung klassischer Algorithmen über.

1. Grundlegende Datenstrukturen in Rust

Die Rust-Standardbibliothek (std) bietet eine reichhaltige Sammlung vorgefertigter Datenstrukturen. Betrachten wir die drei wichtigsten davon.

Vektoren (Vec)

Vec ist ein dynamisches Array, das seine Größe ändern kann. Es ist das Äquivalent zu ArrayList in Java oder list in Python. Vektoren garantieren eine kontinuierliche Speicherplatzanordnung der Elemente, was den Zugriff über den Index sehr schnell macht (O(1)).

fn main() {    // Erstellen eines leeren Vektors    let mut numbers: Vec<i32> = Vec::new();        // Elemente hinzufügen    numbers.push(10);    numbers.push(20);    numbers.push(30);        // Zugriff über Index    let first = numbers[0]; // 10        // Iteration    for num in &numbers {        println!("{}", num);    }        // Makro vec!    let fruits = vec!["apple", "banana", "cherry"];    println!("Zweite Frucht: {}", fruits[1]); // banana}

Hashmaps (HashMap)

HashMap ist eine Datenstruktur, die Schlüssel-Wert-Paare speichert. Sie bietet eine durchschnittliche Zugriffszeit von O(1) für Einfügen, Suchen und Löschen. Ideal für Aufgaben, bei denen Daten schnell über einen Schlüssel gefunden werden müssen.

use std::collections::HashMap;

fn main() {    let mut scores = HashMap::new();        scores.insert(String::from("Alice"), 100);    scores.insert(String::from("Bob"), 85);        // Wert über Schlüssel abrufen    let alice_score = scores.get(&String::from("Alice"));    match alice_score {        Some(score) => println!("Alice hat erreicht: {}", score),        None => println!("Alice nicht gefunden"),    }        // Alle Paare durchlaufen    for (name, score) in &scores {        println!("{}: {}", name, score);    }}

Strings (String)

In Rust gibt es zwei Haupttypen von Strings: &str (String-Slice) und String (veränderbarer, besitzender String). Die Arbeit mit Strings in Rust erfordert aufgrund der UTF-8-Kodierung Aufmerksamkeit.

fn main() {    let mut hello = String::from("Hallo, ");    hello.push_str("Welt!"); // String anhängen    hello.push('!'); // Zeichen anhängen        println!("{}", hello); // Hallo, Welt!!        // String-Slices (Vorsicht mit Zeichengrenzen!)    let slice = &hello[0..7]; // "Hallo, "    println!("Slice: {}", slice);}

2. Implementierung von Stack und Queue

Stack und Queue sind grundlegende Datenstrukturen, die häufig in Algorithmen verwendet werden. In Rust lassen sie sich einfach mit Vec implementieren.

Stack (LIFO — Last In, First Out)

Ein Stack funktioniert nach dem Prinzip "zuletzt herein, zuerst heraus". Vec bietet bereits die Methoden push und pop, die das Verhalten eines Stacks implementieren.

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!("Entferne: {}", top);    }    // Ausgabe: 3, 2, 1}