Einfügen
Lektion 5 von 14 im Kurs Tries - Datenstrukturen-Serie #8 von Coddy.
Um ein Wort in den Trie einzufügen, gehen Sie von der Wurzel aus Zeichen für Zeichen nach unten. Für jedes Zeichen des Wortes: Wenn der aktuelle Knoten kein Kind für dieses Zeichen hat, erstellen Sie einen neuen TrieNode und fügen Sie ihn hinzu. In jedem Fall gehen Sie zu diesem Kindknoten über und fahren mit dem nächsten Zeichen fort.
Wenn Sie das Ende des Wortes erreichen, markieren Sie den Knoten, auf dem Sie gelandet sind, mit isEndOfWord = true. Dieses Flag unterscheidet später ein tatsächlich gespeichertes Wort von einem Pfad, der nur existiert, weil er ein Präfix von etwas anderem ist.
Das Einfügen von "cat" und dann "car" teilt sich den c -> a Pfad und verzweigt sich erst beim dritten Zeichen. Dieses Teilen ist es, was Tries so platzeffizient für Wörterbücher macht.
Aufgabe
EinfachFügen Sie der Klasse Trie eine Methode insert hinzu.
Sie erhält einen String word und speichert diesen im Trie:
- Beginnen Sie bei der
root. Für jedes Zeichencinword: Wenn der aktuelle Knoten kein Kind fürchat, fügen Sie dort einen neuenTrieNodehinzu. - Wechseln Sie in dieses Kind und fahren Sie fort.
- Markieren Sie nach dem letzten Zeichen das Feld
isEndOfWorddes letzten Knotens alstrue.
Probier es selbst
#include <stdio.h>
#include <stdlib.h>
#include <string.h>
#include "trie.h"
int main() {
Trie t;
Trie_init(&t);
char line[1024];
while (fgets(line, sizeof(line), stdin)) {
line[strcspn(line, "\r\n")] = '\0';
char* cmd = strtok(line, " \t");
if (!cmd) continue;
if (strcmp(cmd, "rootIsEmpty") == 0) { printf("%s\n", TrieNode_childrenCount(t.root) == 0 ? "true" : "false"); }
if (strcmp(cmd, "hasChild") == 0) { char* arg = strtok(NULL, " \t"); if (arg) printf("%s\n", t.root->children[(unsigned char)arg[0]] != NULL ? "true" : "false"); }
if (strcmp(cmd, "insert") == 0) { char* arg = strtok(NULL, " \t"); if (arg) Trie_insert(&t, arg); }
}
return 0;
}