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

Algorithmen und Datenstrukturen in C++: Von den Grundlagen zur Praxis

Die Beherrschung von Algorithmen und Datenstrukturen ist ein entscheidender Schritt in der Entwicklung eines jeden Programmierers. In diesem Artikel behandeln wir die grundlegenden Konzepte am Beispiel der Sprache C++. Sie erfahren, wie Sie Daten effizient organisieren und schnelle Algorithmen schreiben, die die Grundlage Ihrer Projekte bilden. Das Material richtet sich an Anfänger und Intermediate-Entwickler.

Was sind Algorithmen und Datenstrukturen?

Algorithmus — eine klare Abfolge von Schritten zur Lösung einer Aufgabe. Datenstruktur — eine Methode zur Organisation und Speicherung von Daten, die effizienten Zugriff und Änderung ermöglicht. In C++ sind beide Konzepte eng verbunden: Die Wahl der richtigen Datenstruktur kann einen Algorithmus um ein Vielfaches beschleunigen.

Wichtige Datenstrukturen in C++:

• Arrays — fester Satz von Elementen desselben Typs
• Verkettete Listen — dynamische Sequenzen
• Stacks und Queues — Strukturen mit eingeschränktem Zugriff
• Bäume — hierarchische Strukturen
• Hash-Tabellen — schnelle Suche nach Schlüsseln

Arrays und die Arbeit mit ihnen

Ein Array ist die einfachste Datenstruktur, bei der Elemente in einem zusammenhängenden Speicherbereich abgelegt werden. In C++ gibt es statische und dynamische Arrays.

#include <iostream>using namespace std;

int main() {    // Statisches Array    int arr[5] = {10, 20, 30, 40, 50};        // Dynamisches Array (über new)    int* dynArr = new int[3];    dynArr[0] = 1;    dynArr[1] = 2;    dynArr[2] = 3;        // Ausgabe der Elemente    for (int i = 0; i < 5; i++) {        cout << arr[i] << " ";    }        delete[] dynArr; // Speicher freigeben    return 0;}

Algorithmus der linearen Suche in einem Array:

int linearSearch(int arr[], int n, int x) {    for (int i = 0; i < n; i++) {        if (arr[i] == x)            return i; // Index zurückgeben    }    return -1; // Nicht gefunden}

Komplexität: O(n). Zur Beschleunigung verwenden Sie std::vector aus der STL — dieser verwaltet den Speicher automatisch.

Verkettete Listen: einfach und doppelt verkettet

Eine verkettete Liste besteht aus Knoten, die jeweils Daten und einen Zeiger auf das nächste (oder vorherige) Element enthalten. In C++ werden häufig std::forward_list (einfach verkettet) und std::list (doppelt verkettet) verwendet.

Implementierung einer einfachen einfach verketteten Liste:

struct Node {    int data;    Node* next;};

class LinkedList {private:    Node* head;public:    LinkedList() : head(nullptr) {}        void insert(int val) {        Node* newNode = new Node{val, nullptr};        if (!head) {            head = newNode;            return;        }        Node* temp = head;        while (temp->next) temp = temp->next;        temp->next = newNode;    }        void display() {        Node* temp = head;        while (temp) {            cout << temp->data << " -> ";            temp = temp->next;        }        cout << "nullptr" << endl;    }};

Vorteile von Listen:

• Dynamische Größe
• Schnelles Einfügen und Löschen in der Mitte (O(1) wenn ein Zeiger vorhanden ist)

Nachteile:

• Langsamer Zugriff über Index (O(n))
• Zusätzlicher Speicher für Zeiger

Stack und Queue: Prinzipien LIFO und FIFO

Stack arbeitet nach dem Prinzip "last in, first out" (LIFO). Queue — "first in, first out" (FIFO). In C++ sind sie in der STL implementiert.

Beispiel für die Verwendung eines Stacks:

#include <stack>#include