Algorithmen und Datenstrukturen in C++: Vollständiger Leitfaden für Anfänger

Algorithmen und Datenstrukturen in C++: Von den Grundlagen bis zu fortgeschrittenen Techniken

Algorithmen und Datenstrukturen sind das Fundament jedes effizienten Programms. In C++ haben Sie die volle Kontrolle über Speicher und Leistung, was diese Sprache ideal für das Erlernen algorithmischen Denkens macht. In diesem Artikel behandeln wir die wichtigsten Konzepte, geben Codebeispiele und zeigen, wie man sie in der Praxis anwendet. Das Material eignet sich sowohl für Anfänger als auch für Entwickler, die ihr Wissen systematisieren möchten.

Wir betrachten drei Hauptgruppen: lineare Datenstrukturen (Arrays, Listen, Stapel, Warteschlangen), hierarchische Strukturen (Bäume) und Verarbeitungsalgorithmen (Sortierung und Suche). Jeder Abschnitt enthält fertigen C++-Code und Erklärungen.

1. Lineare Datenstrukturen: Arrays, verkettete Listen, Stack und Queue

Lineare Strukturen sind die Grundlage, mit der die Arbeit mit Daten beginnt. In C++ werden sie sowohl durch eingebaute Mittel als auch durch benutzerdefinierte Klassen implementiert.

Arrays und dynamische Arrays (std::vector)

Ein Array ist die einfachste Struktur mit fester Größe. Für Flexibilität verwenden Sie std::vector:

#include <iostream>#include <vector>

int main() {    std::vector<int> numbers = {5, 2, 8, 1, 9};        // Element hinzufügen    numbers.push_back(3);        // Zugriff über Index    std::cout << "Drittes Element: " << numbers[2] << std::endl;        // Durchlaufen    for (int num : numbers) {        std::cout << num << " ";    }    return 0;}

Vorteile: schneller Zugriff O(1), Cache-Lokalität. Nachteile: Einfügen/Löschen in der Mitte — O(n).

Verkettete Liste (einfach verkettet)

Eine Liste besteht aus Knoten, die jeweils Daten und einen Zeiger auf das nächste Element speichern. Implementierung in C++:

struct Node {    int data;    Node* next;        Node(int val) : data(val), next(nullptr) {}};

class LinkedList {private:    Node* head;public:    LinkedList() : head(nullptr) {}        void pushFront(int val) {        Node* newNode = new Node(val);        newNode->next = head;        head = newNode;    }        void print() {        Node* current = head;        while (current) {            std::cout << current->data << " -> ";            current = current->next;        }        std::cout << "nullptr" << std::endl;    }        ~LinkedList() {        Node* current = head;        while (current) {            Node* next = current->next;            delete current;            current = next;        }    }};

Wann verwenden: häufige Einfügungen/Löschungen am Anfang der Liste. Suche — O(n).

Stack und Queue

Stack (LIFO) und Queue (FIFO) sind spezialisierte Strukturen. In C++ gibt es fertige Adapter:

#include <stack>#include <queue>

int main() {    // Stack    std::stack<int> st;    st.push(10);    st.push(20);    std::cout << "Oberstes Element des Stacks: " << st.top() << std::endl; // 20    st.pop();        // Queue    std::queue<int> q;    q.push(1);    q.push(2);    std::cout << "Erstes Element der Queue: " << q.front() << std::endl; // 1    q.pop();        return 0;}

2. Hierarchische Strukturen: binäre Suchbäume

Bäume ermöglichen die effiziente Speicherung hierarchischer Daten. Der binäre Suchbaum (BST) ist ein Klassiker der Algorithmen in C++.

Implementierung eines BST

struct TreeNode {    int key;    TreeNode* left;    TreeNode* right;        TreeNode(int k) : key(k), left(nullptr), right(nullptr) {}};

TreeNode* insert(TreeNode* root, int key) {    if (!root) return new TreeNode(key);        if (key < root->key)        root->left =