C++ Datenstrukturen

C++ bietet eine Vielzahl von Datenstrukturen, von grundlegenden wie Arrays, Strukturen und Klassen bis hin zu fortgeschrittenen STL-Containern wievector、mapundunordered_mapusw.

Im Folgenden werden die häufig verwendeten Datenstrukturen in C++ zusammen mit ihren Eigenschaften und ihrer Verwendung detailliert beschrieben.

1. Array

Arrays sind die grundlegendsten Datenstrukturen und werden verwendet, um eine Menge gleichartiger Daten zu speichern.

Funktionen：

  • Feste Größe; nach der Deklaration kann die Größe nicht geändert werden.
  • Direkter Elementzugriff mit einer Zeitkomplexität von O(1).
  • Geeignet für die Verarbeitung von Sammlungen bekannter Größe mit identischen Elementtypen.

Beispiel

int arr[5] = {1, 2, 3, 4, 5};
cout << arr[0]; // Erstes Element ausgeben

Vorteile und Nachteile：

  • Vorteil: Schnelle Zugriffsgeschwindigkeit, kompakter Speicherverbrauch.
  • Nachteile: feste Größe, kann nicht dynamisch erweitert werden, nicht geeignet für Datensätze ungewisser Größe.

2. Struktur

Strukturen ermöglichen die Kombination verschiedener Datentypen zu einem benutzerdefinierten Datentyp.

Funktionen：

  • Kann Membervariablen unterschiedlicher Typen enthalten.
  • Bietet eine grundlegende Kapselung von Daten, jedoch mit begrenzter Funktionalität.

Beispiel：

Beispiel

struct Person {
    string name;
    int age;
};
Person p = {"Alice", 25};
cout << p.name << endl; // Ausgabe Alice

3. Klasse

Klassen sind die Kernstruktur für objektorientierte Programmierung in C++ und ermöglichen die Definition von Membervariablen und Memberfunktionen. Verglichen mitstructÄhnlich, aber leistungsfähiger, mit Unterstützung von Funktionen wie Vererbung, Kapselung und Polymorphie.

Funktionen：

  • Kann Membervariablen, Memberfunktionen, Konstruktoren und Destruktoren enthalten.
  • Unterstützt objektorientierte Merkmale wie Kapselung, Vererbung und Polymorphie.

Beispiel

class Person {
private:
    string name;
    int age;
public:
    Person(string n, int a) : name(n), age(a) {}
    void printInfo() {
        cout << "Name: " << name << ", Alter: " << age << endl;
    }
};
Person p("Bob", 30);
p.printInfo(); // Ausgabe: Name: Bob, Alter: 30

4. Verkettete Liste

Eine verkettete Liste ist eine dynamische Datenstruktur, die aus einer Reihe von Knoten besteht, wobei jeder Daten und einen Zeiger auf den nächsten Knoten enthält.

Funktionen：

  • Passt seine Größe dynamisch an, Kapazität muss nicht vorab festgelegt werden.
  • Einfüge- und Löschoperationen sind effizient, mit einer Zeitkomplexität von O(1) (beim Arbeiten am Kopf oder Ende der Liste).
  • Lineare Suche mit einer Zeitkomplexität von O(n).

Beispiel (einfach verkettete Liste)

struct Node {
    int data;
    Node* next;
};
Node* head = nullptr;
Node* newNode = new Node{10, nullptr};
head = newNode; // Neuen Knoten einfügen

Vorteile und Nachteile：

  • Vorteile: dynamische Größe, geeignet für Szenarien mit häufigen Einfügungen und Löschungen.
  • Nachteile: ineffizienter wahlfreier Zugriff, nicht so schnell wie direkter Array-Zugriff.

5. Stapel

Ein Stack ist eine Last-In-First-Out-(LIFO)-Datenstruktur, die häufig in Szenarien wie Rekursion und Tiefensuche verwendet wird.

Funktionen：

  • Erlaubt nur Einfüge- und Löschoperationen am oberen Ende des Stapels.
  • Die Zeitkomplexität ist O(1).

Beispiel

stack<int> s;
s.push(1);
s.push(2);
cout << s.top(); // Ausgabe 2
s.pop();

Vorteile und Nachteile：

  • Vorteil: Einfache Operationen, hohe Effizienz.
  • Nachteile: Operationen können nur am oberen Ende ausgeführt werden; der Zugriff auf andere Elemente erfordert das Entfernen des obersten Elements.

6. Warteschlange

Eine Warteschlange ist eine First-In-First-Out-Datenstruktur (FIFO), die häufig in Szenarien wie der Breitensuche und der Aufgabenplanung verwendet wird.

Funktionen：

  • Einfügeoperationen erfolgen am Ende der Warteschlange, und Löschoperationen erfolgen am Kopf.
  • Die Zeitkomplexität ist O(1).

Beispiel

queue<int> q;
q.push(1);
q.push(2);
cout << q.front(); // Ausgabe 1
q.pop();

Vorteile und Nachteile：

  • Vorteile: Geeignet für Szenarien, die Daten in der Reihenfolge verarbeiten, wie z. B. Aufgabenplanung.
  • Nachteil: Kein wahlfreier Zugriff auf Elemente möglich.

7. Doppelendige Warteschlange (Deque)

Eine Deque ermöglicht Einfüge- und Löschoperationen an beiden Enden und kombiniert die Eigenschaften eines Stapels und einer Warteschlange.

Funktionen：

  • Ermöglicht Einfügen und Löschen an beiden Enden.
  • Die Zeitkomplexität ist O(1).

Beispiel

deque<int> dq;
dq.push_back(1);
dq.push_front(2);
cout << dq.front(); // Ausgabe 2
dq.pop_front();

Vorteile und Nachteile：

  • Vorteil: Flexible bidirektionale Operationen.
  • Nachteile: größerer Speicherbedarf, geeignet für Szenarien, die häufige Operationen an beiden Enden erfordern.

8. Hash-Tabelle

Eine Hash-Tabelle ist eine Datenstruktur, die Daten über Schlüssel-Wert-Paare speichert und schnelle Such-, Einfüge- und Löschoperationen unterstützt. In C++,unordered_mapEine Implementierung einer Hash-Tabelle.

Funktionen：

  • Verwendet eine Hash-Funktion, um Elemente schnell zu lokalisieren, mit einer Zeitkomplexität von O(1).
  • Garantiert nicht die Reihenfolge der Elemente.

Beispiel

unordered_map<string, int> hashTable;
hashTable["apple"] = 10;
cout << hashTable["apple"]; // Ausgabe 10

Vorteile und Nachteile：

  • Vorteile: hohe Effizienz bei Such-, Einfüge- und Löschvorgängen.
  • Nachteile: Die Reihenfolge der Elemente kann nicht garantiert werden, und die Leistung verschlechtert sich, wenn Hash-Kollisionen auftreten.

9. Map

mapEs ist ein geordneter Container für Schlüssel-Wert-Paare, implementiert unter Verwendung eines Rot-Schwarz-Baums. Im Vergleich zuunordered_mapanderen, garantiert es die Reihenfolge der Schlüssel, mit Zeitkomplexitäten von O(log n) für Suchen, Einfügen und Löschen.

Funktionen：

  • Garantiert, dass die Elemente in der Reihenfolge ihrer Schlüssel angeordnet sind.
  • Implementiert unter Verwendung eines binären Suchbaums.

Beispiel

map<string, int> myMap;
myMap["apple"] = 10;
cout << myMap["apple"]; // Ausgabe 10

Vorteile und Nachteile：

  • Vorteile: Elemente sind geordnet, geeignet für Szenarien, in denen Daten in der Reihenfolge verarbeitet werden müssen.
  • Nachteil: Geringere operationelle Effizienz alsunordered_mapEtwas niedriger.

10. Set

setEs ist ein geordnetes Set zum Speichern eindeutiger Elemente, das ebenfalls mit einem Rot-Schwarz-Baum implementiert ist. Es stellt sicher, dass Elemente nicht dupliziert und geordnet sind.

Funktionen：

  • Garantiert die Eindeutigkeit von Elementen.
  • Elemente werden automatisch in aufsteigender Reihenfolge angeordnet.
  • Die Zeitkomplexität ist O(log n).

Beispiel

set<int> s;
s.insert(1);
s.insert(2);
cout << *s.begin(); // Ausgabe 1

Vorteile und Nachteile：

  • Vorteil: Automatische Sortierung und Garantie der Eindeutigkeit.
  • Nachteile: Einfüge- und Lösch-Effizienz ist geringer als bei ungeordneten Mengen.

11. Dynamisches Array (Vektor)

vectorEs handelt sich um eine von der C++-Standardbibliothek bereitgestellte Implementierung eines dynamischen Arrays, die ihre Kapazität dynamisch erweitern kann und wahlfreien Zugriff unterstützt.

Funktionen：

  • Dynamische Größenanpassung.
  • Unterstützt wahlfreien Zugriff mit einer Zeitkomplexität von O(1).
  • Wenn die Kapazität nicht ausreicht, wird sie dynamisch erweitert, mit einer amortisierten Zeitkomplexität von O(1).

Beispiel

vector<int> v;
v.push_back(1);
v.push_back(2);
cout << v[0]; // Ausgabe 1

Vorteile und Nachteile：

  • Vorteile: Unterstützt wahlfreien Zugriff und dynamische Erweiterung.
  • Nachteile: geringe Effizienz beim Einfügen oder Löschen von Elementen in der Mitte.
Weitere Erweiterungen