================================== Grobe Festlegung der Datenstruktur ================================== In einem ersten Entwurf legen wir fest, welche Klassen, Methoden und Attribute benötigt werden. Im Lösungsvorschlag sind diese zum Beispiel die Klassen: - Eine Klasse `Key` Diese enthält zwei statische Methoden: - `size` gibt die Anzahl der unterschiedlichen Schlüssel zurück - `map` berechnet für ein character den Schlüssel Beide Methoden sind zudem als `constexpr` deklariert, so dass der Rückgabewert bereits zur Compile-Zeit bekannt ist (bzw. bekannt sein muss). Damit ist es möglich die Dimension eines C-Arrays über die statische `size`-Methode festzulegen. - Eine Klasse `Trie` - Diese enthält die üblichen Konstruktoren, den Destruktor und einen Zuweisungsoperator. - Eine `size`-Methode soll die Anzahl der Blatt-Knoten zurückgeben, d.h. die Anzahl der gespeicherten Objekte. - Die Methode `insert` erlaubt das Einfügen eines Schlüssel-Objekt Paares. - Die Methode `visit` erlaubt das besuchen aller Objekte, deren Schlüssel mit einem angegebenen Präfix beginnt. - Eine interne Klasse `Node` wird benutzt, um einen Konten zu repräsentieren: - Da ein Konten ein Objekt enthalten kann oder auch nicht, werden wird zunächst einen Zeigen auf ein Objekt verwenden. Ein Null-Zeiger bedeutet, dass kein Objekt gespeichert ist. - Zudem enthält ein Knoten ein Array mit Zeigern auf Unter-Knoten. Enthält ein Array-Eintrag einen Null-Zeiger, dann bedeutet diese, dass kein Unter-Knoten existiert. Mit `Key::map(c)` wird aus einem Character `c` ein Array-Index `i` berechnet werden. Hier das so entstandene Grundgerüst: :import: cpp-lecture/trie/step00/trie.hpp :navigate: next -> doc:cpp-lecture/trie/step01