عدد الكلمات
الدرس 9 من 14 في دورة Tries - سلسلة هياكل البيانات #8 على Coddy.
كم عدد الكلمات المميزة الموجودة في شجرة trie هذه الآن؟ لا يوجد عداد مستمر، لذا يتعين علينا المرور عبر الشجرة وعدّ العقد التي تكون فيها قيمة isEndOfWord هي true.
يقوم البحث بالعمق أولاً (depth-first search) بدءاً من الجذر بالمهمة في تمريرة واحدة. لكل عقدة، أضف 1 إذا كانت نهاية كلمة، ثم قم بالاستدعاء الذاتي (recurse) لكل عقدة تابعة واجمع النتائج. الإجمالي هو عدد الكلمات المخزنة.
لاحظ أن هذا يتعامل بشكل طبيعي مع التكرارات: إدراج "cat" ثلاث مرات لا يزال يحدد عقدة واحدة فقط كنهاية كلمة، لذا يكون العدد 1. البوادئ التي لم يتم إدراجها ككلمات مستقلة لا تُحتسب أيضاً - عُقدها موجودة، لكن isEndOfWord تكون false فيها.
التحدي
سهلأضف طريقة wordCount إلى فئة Trie.
لا تأخذ هذه الطريقة أي مدخلات وتعيد عدد الكلمات المتميزة المخزنة حالياً في الـ trie. قم بالمرور على الـ trie بدءاً من الجذر (root) وقم بعدّ كل عقدة تكون قيمة isEndOfWord فيها هي true.
جرّب بنفسك
#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;
}