C++ Dictionary mit Bag und Threaded Binary Tree: Ein umfassendes Tutorial für CSIS 215

Einführung: Warum Datenstrukturen in C++ wichtig sind

In der heutigen digitalen Welt, in der Apps wie TikTok und Instagram Milliarden von Datenpunkten in Echtzeit verarbeiten, sind effiziente Datenstrukturen das Rückgrat jeder Software. Als Student in CSIS 215 wirst du gefordert, grundlegende ADTs (Abstract Data Types) wie Bag und Dictionary zu implementieren und später einen Threaded Binary Tree zu bauen. Dieses Tutorial führt dich durch die Konzepte, ohne deine Hausaufgaben zu lösen – es gibt dir das nötige Verständnis, um die Aufgaben selbst zu meistern.

Projekt 1: Array-basierte Bag-Implementierung

Was ist ein Bag ADT?

Ein Bag (auch Multiset genannt) ist eine Sammlung, die Elemente ohne bestimmte Reihenfolge speichert und Duplikate erlaubt. Stell dir vor, du sammelst Pokémon-Karten – du kannst mehrere Pikachu haben, und die Reihenfolge spielt keine Rolle. In C++ wird ein Bag typischerweise mit Operationen wie add, remove, contains und size definiert.

Array-basierte Implementierung

Eine einfache Möglichkeit, einen Bag zu implementieren, ist die Verwendung eines Arrays fester Größe. Du definierst ein Array und einen Zähler für die aktuelle Anzahl der Elemente. Die add-Methode fügt ein Element am Ende des Arrays hinzu (sofern Platz vorhanden ist). Die remove-Methode sucht nach dem Element und verschiebt die restlichen Elemente nach links, um das Loch zu füllen.

template <typename T>
class ABag : public Bag<T> {
private:
    static const int DEFAULT_CAPACITY = 100;
    T items[DEFAULT_CAPACITY];
    int itemCount;
public:
    ABag() : itemCount(0) {}
    bool add(const T& item) override {
        if (itemCount >= DEFAULT_CAPACITY) return false;
        items[itemCount++] = item;
        return true;
    }
    // ... weitere Methoden
};

Beachte: Deine ABag-Klasse muss von der abstrakten Bag-Klasse erben. Die bereitgestellte Vorlage ABag.h erledigt das bereits. Du darfst keine öffentlichen Methoden hinzufügen, aber private Helfer sind erlaubt.

Projekt 2: Dictionary mit Bag implementieren

Dictionary ADT verstehen

Ein Dictionary (auch Map oder assoziatives Array genannt) speichert Schlüssel-Wert-Paare. Jeder Schlüssel ist eindeutig. In der Praxis wird dies z. B. in Datenbanken oder bei der Konfiguration von Apps verwendet. Deine Aufgabe ist es, das Dictionary mithilfe deines Bags zu implementieren. Das bedeutet, dass du intern einen Bag von KVpair-Objekten verwendest.

Implementierung mit Bag

Die Dictionary-Klasse enthält einen Bag von KVpair. Die Methode insert erstellt ein neues Paar und fügt es dem Bag hinzu. find durchsucht den Bag nach einem Paar mit dem angegebenen Schlüssel. Da der Bag keine Duplikate verhindert, musst du selbst sicherstellen, dass Schlüssel eindeutig bleiben – z. B. durch Entfernen eines vorhandenen Eintrags vor dem Einfügen.

template <typename K, typename V>
class BDictionary : public Dictionary<K, V> {
private:
    ABag<KVpair<K, V>> bag;
public:
    void insert(const K& key, const V& value) override {
        KVpair<K, V> pair(key, value);
        bag.add(pair);
    }
    // ... weitere Methoden
};

Wichtig: Der KVpair verwendet den ==-Operator, um Schlüssel zu vergleichen. Stelle sicher, dass deine Schlüsseltypen diesen Operator unterstützen. Der Datentyp Int (aus der C++-Bibliothek) funktioniert nicht – verwende stattdessen int oder andere Typen.

Projekt 3: Double-Threaded Binary Tree

Was ist ein Threaded Binary Tree?

Ein Threaded Binary Tree ist ein binärer Suchbaum, bei dem die Nullzeiger durch Verweise auf den Vorgänger (predecessor) und Nachfolger (successor) in der Inorder-Reihenfolge ersetzt werden. Das ermöglicht eine effiziente Inorder- und Reverse-Inorder-Traversierung ohne Rekursion oder Stack. Stell dir vor, du hast eine Playlist in Spotify – die Threads zeigen dir den nächsten und vorherigen Song an, ohne dass du die gesamte Liste durchsuchen musst.

Implementierung der Threads

Du beginnst mit der vorhandenen BST-Implementierung aus dem Lehrbuch. Füge in BSTNode.h zwei boolesche Variablen hinzu: leftThread und rightThread. Wenn leftThread true ist, zeigt left auf den Inorder-Vorgänger (statt auf das linke Kind). Analog für rightThread und den Nachfolger. Schreibe Getter und Setter für diese Variablen.

template <typename T>
class ThreadedNode : public BSTNode<T> {
private:
    bool leftThread, rightThread;
public:
    ThreadedNode(const T& data)
        : BSTNode<T>(data), leftThread(false), rightThread(false) {}
    bool isLeftThread() const { return leftThread; }
    void setLeftThread(bool val) { leftThread = val; }
    // ... analog für rightThread
};

Modifikation von inserthelp

Der schwierigste Teil ist die Anpassung der inserthelp-Methode. Beim Einfügen eines neuen Knotens musst du die Threads der umliegenden Knoten aktualisieren. Wenn du z. B. einen Knoten als linkes Kind einfügst, wird dessen left-Thread auf den Vorgänger (den Elternknoten oder dessen Vorgänger) gesetzt, und sein right-Thread auf den Elternknoten. Zeichne den Baum auf Papier, um die Zustände zu visualisieren – das hilft ungemein.

Projekt 4: LRU Buffer Pool für den Plattenzugriff

Motivation

Moderne Datenbanken und Dateisysteme verwenden Puffer, um häufig benötigte Datenblöcke im Speicher zu halten. Der LRU (Least Recently Used)-Algorithmus verwirft den Block, der am längsten nicht verwendet wurde. Dieses Konzept ist zentral für die Leistung von Systemen wie Googles Bigtable oder der Festplattenverwaltung deines Betriebssystems.

Implementierungsidee

Du implementierst eine Klasse BufferPool, die eine feste Anzahl von Blöcken im Speicher hält. Jeder Block hat eine Blocknummer. Bei einem Zugriff (z. B. getBlock) wird geprüft, ob der Block bereits im Pool ist. Wenn ja, wird er als zuletzt verwendet markiert. Wenn nein, wird der LRU-Block verdrängt und der neue Block von der Platte geladen. Verwende eine doppelt verkettete Liste oder eine std::list in Kombination mit einer Hash-Map, um die Reihenfolge der Nutzung zu verfolgen.

Allgemeine Tipps zum Debuggen

Ein großer Teil dieser Aufgaben besteht darin, Fehler zu finden. Nutze den Debugger deiner Entwicklungsumgebung (z. B. Visual Studio 2017), um den Zustand von Zeigern und Variablen zu überprüfen. Teste jede Funktion einzeln, bevor du zur nächsten übergehst. Schreibe deine Herangehensweise in einem Word-Dokument auf – das hilft dir, Klarheit zu gewinnen.

Abschlussgedanke

Diese Projekte sind anspruchsvoll, aber sie vermitteln dir grundlegende Fähigkeiten, die du in der Praxis benötigst. Egal, ob du später an einer KI-App wie ChatGPT arbeitest oder an einer Finanzsoftware – das Verständnis von Datenstrukturen ist unverzichtbar. Fang früh an, zeichne Bäume, und zögere nicht, Hilfe zu suchen. Viel Erfolg!