Recherche
Leçon 6 sur 14 du cours Tries - Série Structures de données n°8 de Coddy.
Rechercher un mot est l'opposé naturel de l'insertion : descendez à partir de la racine un caractère à la fois, en suivant les enfants correspondants. Si à n'importe quel moment le nœud actuel n'a pas d'enfant pour le caractère suivant, le mot n'est pas dans le trie et nous pouvons retourner false immédiatement.
Si nous parvenons à parcourir chaque caractère, nous arrivons sur un nœud. La réponse est la valeur de l'indicateur isEndOfWord de ce nœud. C'est la distinction cruciale : après avoir inséré "car", le chemin pour "ca" existe dans le trie, mais search("ca") doit toujours retourner false car personne n'a marqué ce nœud comme étant la fin d'un mot.
Défi
FacileAjoutez une méthode search à la classe Trie.
Elle reçoit une chaîne word et renvoie :
truesiworda été inséré dans le trie auparavant.falsesinon (y compris lorsqu'un seul préfixe dewordexiste, ou lorsqu'un mot plus long commençant parwordest stocké).
Essayez vous-même
#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;
}