Kelime Sayısı
Coddy'nin Trie - Veri Yapıları Serisi #8 kursunda ders 9 / 14.
Şu anda bu trie yapısında kaç tane farklı kelime bulunuyor? Çalışan bir sayaç yok, bu yüzden ağacı dolaşmalı ve isEndOfWord değerinin true olduğu düğümleri saymalıyız.
Kökten başlayan bir derinlik öncelikli arama (depth-first search), işi tek bir geçişte halleder. Her düğüm için, eğer kelime sonuysa 1 ekleyin, ardından her bir alt düğüme özyinelemeli olarak gidin ve sonuçları toplayın. Toplam, saklanan kelimelerin sayısıdır.
Bunun kopyaları doğal olarak işlediğine dikkat edin: "cat" kelimesini üç kez eklemek yine de tek bir düğümü kelime sonu olarak işaretler, bu nedenle sayı 1'dir. Kendi başlarına hiç eklenmemiş olan önekler de sayılmaz - düğümleri mevcuttur ancak bu düğümlerde isEndOfWord değeri false'tur.
Görev
KolayTrie sınıfına bir wordCount metodu ekleyin.
Bu metot girdi almaz ve şu anda trie içinde saklanan benzersiz kelimelerin sayısını döndürür. Trie'yi kökten (root) başlayarak dolaşın ve isEndOfWord değeri true olan her düğümü sayın.
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"); }
if (strcmp(cmd, "startsWith") == 0) { char* arg = strtok(NULL, " \t"); if (arg) printf("%s\n", Trie_startsWith(&t, arg) ? "true" : "false"); }
if (strcmp(cmd, "delete") == 0) { char* arg = strtok(NULL, " \t"); if (arg) Trie_delete(&t, arg); }
if (strcmp(cmd, "wordCount") == 0) { printf("%d\n", Trie_wordCount(&t)); }
}
return 0;
}