Wortanzahl
Lektion 9 von 14 im Kurs Tries - Datenstrukturen-Serie #8 von Coddy.
Wie viele verschiedene Wörter befinden sich derzeit in diesem Trie? Es gibt keinen laufenden Zähler, also müssen wir den Baum durchlaufen und die Knoten zählen, bei denen isEndOfWord auf true gesetzt ist.
Eine Tiefensuche, die an der Wurzel beginnt, erledigt dies in einem Durchgang. Addieren Sie für jeden Knoten 1, wenn es sich um ein Wortende handelt, führen Sie dann eine Rekursion für jedes Kind aus und summieren Sie die Ergebnisse. Die Gesamtsumme entspricht der Anzahl der gespeicherten Wörter.
Beachten Sie, dass dies Duplikate automatisch berücksichtigt: Wenn Sie "cat" dreimal einfügen, wird dennoch nur ein Knoten als Wortende markiert, sodass die Anzahl 1 bleibt. Präfixe, die nie eigenständig eingefügt wurden, werden ebenfalls nicht mitgezählt – ihre Knoten existieren zwar, aber isEndOfWord ist bei ihnen false.
Aufgabe
EinfachFügen Sie der Klasse Trie eine Methode wordCount hinzu.
Sie nimmt keine Eingabe entgegen und gibt die Anzahl der eindeutigen Wörter zurück, die derzeit im Trie gespeichert sind. Durchlaufen Sie den Trie von der Wurzel aus und zählen Sie jeden Knoten, dessen isEndOfWord den Wert true hat.
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"); }
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;
}