Arama
Coddy'nin Trie - Veri Yapıları Serisi #8 kursunda ders 6 / 14.
Bir kelimeyi aramak, eklemenin (insert) doğal zıttıdır: eşleşen çocukları takip ederek kökten aşağıya doğru her seferinde bir karakter ilerleyin. Herhangi bir noktada mevcut düğümün bir sonraki karakter için çocuğu yoksa, kelime trie içinde değildir ve hemen false döndürebiliriz.
Her karakteri geçmeyi başarırsak, bir düğüme ulaşırız. Cevap, o düğümün isEndOfWord bayrağının ne dediğidir. Kritik ayrım şudur: "car" eklendikten sonra, "ca" yolu trie içinde mevcuttur, ancak search("ca") yine de false döndürmelidir çünkü kimse o düğümü bir kelimenin sonu olarak işaretlememiştir.
Görev
KolayTrie sınıfına bir search metodu ekleyin.
Bu metot bir word dizesi alır ve şunları döndürür:
- Eğer
worddaha önce trie yapısına eklenmişsetrue. - Aksi takdirde
false(yalnızcaword'ün bir öneki mevcutsa veyawordile başlayan daha uzun bir kelime saklanıyorsa dahil).
Kendin dene
#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;
}