Ricerca
Lezione 6 di 14 del corso Trie - Serie sulle strutture dati n. 8 di Coddy.
Cercare una parola è l’opposto naturale di insert: scendi dalla radice un carattere alla volta, seguendo i figli corrispondenti. Se in qualsiasi momento il nodo corrente non ha un figlio per il carattere successivo, la parola non è nel trie e possiamo restituire subito false.
Se riusciamo a percorrere tutti i caratteri, arriviamo a un nodo. La risposta è ciò che indica il flag isEndOfWord di quel nodo. Questa è la distinzione fondamentale: dopo aver inserito "car", nel trie esiste il percorso per "ca", ma search("ca") deve comunque restituire false, perché nessuno ha contrassegnato quel nodo come fine di una parola.
Sfida
FacileAggiungi un metodo search alla classe Trie.
Riceve una stringa word e restituisce:
truesewordè stata inserita nel trie in precedenza.falsealtrimenti (anche quando esiste solo un prefisso diwordo quando è memorizzata solo una parola più lunga che inizia conword).
Provalo tu
#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;
}
Tutte le lezioni di Trie - Serie sulle strutture dati n. 8
Esercitati da solo: Compilatore C online