Suchen
Lektion 6 von 14 im Kurs Tries - Datenstrukturen-Serie #8 von Coddy.
Die Suche nach einem Wort ist das natürliche Gegenteil des Einfügens: Gehen Sie von der Wurzel aus Zeichen für Zeichen nach unten und folgen Sie den passenden Kindknoten. Wenn der aktuelle Knoten zu irgendeinem Zeitpunkt kein Kind für das nächste Zeichen hat, befindet sich das Wort nicht im Trie, und wir können sofort false zurückgeben.
Wenn wir es schaffen, jedes Zeichen zu durchlaufen, landen wir bei einem Knoten. Die Antwort ist das, was das isEndOfWord-Flag dieses Knotens besagt. Dies ist der entscheidende Unterschied: Nach dem Einfügen von "car" existiert der Pfad für "ca" im Trie, aber search("ca") muss dennoch false zurückgeben, da niemand diesen Knoten als Ende eines Wortes markiert hat.
Aufgabe
EinfachFügen Sie der Klasse Trie eine Methode search hinzu.
Sie erhält einen String word und gibt Folgendes zurück:
true, wennwordzuvor in den Trie eingefügt wurde.falseandernfalls (einschließlich der Fälle, in denen nur ein Präfix vonwordexistiert oder wenn nur ein längeres Wort gespeichert ist, das mitwordbeginnt).
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); }
if (strcmp(cmd, "search") == 0) { char* arg = strtok(NULL, " \t"); if (arg) printf("%s\n", Trie_search(&t, arg) ? "true" : "false"); }
}
return 0;
}