يبدأ بـ
الدرس 7 من 14 في دورة Tries - سلسلة هياكل البيانات #8 على Coddy.
السبب الكامل لوجود هياكل الـ tries هو الإجابة على أسئلة البادئات (prefix) بسرعة. تتحقق startsWith مما إذا كانت أي كلمة مخزنة تبدأ ببادئة معينة - ولا يهم ما إذا كانت تلك البادئة نفسها كلمة كاملة تم إدخالها أم لا.
عملية الانتقال (the walk) مطابقة تقريبًا لـ search: من الجذر (root)، اتبع الأبناء حرفًا واحدًا في كل مرة. إذا كان هناك حرف مفقود في الطريق، فهذا يعني أنه لا توجد كلمة مخزنة تبدأ بتلك البادئة، لذا قم بإرجاع false. إذا مررت عبر كل حرف دون توقف، فستكون الإجابة true - حيث تحتوي الشجرة الفرعية (subtree) الموجودة أسفل تلك العقدة على كلمة مخزنة واحدة على الأقل.
الاختلاف الوحيد عن search هو: عدم وجود فحص isEndOfWord في النهاية. الوصول إلى نهاية البادئة كافٍ.
التحدي
سهلأضف طريقة startsWith إلى فئة Trie.
تستقبل سلسلة نصية prefix وتعيد:
trueإذا كانت هناك كلمة تم إدخالها تبدأ بـprefix(يمكن أن تطابق البادئة كلمة كاملة، أو تكون الجزء الأول من كلمة أطول).falseخلاف ذلك.
جرّب بنفسك
#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"); }
}
return 0;
}