بحث
الدرس 6 من 14 في دورة Tries - سلسلة هياكل البيانات #8 على Coddy.
البحث عن كلمة هو النقيض الطبيعي لعملية الإدراج: انتقل للأسفل من الجذر حرفاً واحداً في كل مرة، متبعاً الأبناء المطابقين. إذا لم يكن لدى العقدة الحالية في أي نقطة ابن للحرف التالي، فإن الكلمة ليست موجودة في الـ trie ويمكننا إرجاع false على الفور.
إذا تمكنا من المرور عبر كل حرف، فسنصل إلى عقدة. الإجابة هي أياً كانت القيمة التي يشير إليها علم isEndOfWord لتلك العقدة. هذا هو التمييز الجوهري: بعد إدراج "car"، يكون المسار لـ "ca" موجوداً في الـ trie، ولكن يجب أن تظل search("ca") ترجع false لأن لا أحد قام بتمييز تلك العقدة كنهاية لكلمة.
التحدي
سهلأضف طريقة search إلى فئة Trie.
تستقبل هذه الطريقة سلسلة نصية word وتعيد:
trueإذا تم إدخالwordفي الـ trie من قبل.falseخلاف ذلك (بما في ذلك الحالات التي يوجد فيها بادئة فقط منword، أو عندما يتم تخزين كلمة أطول تبدأ بـwordفقط).
جرّب بنفسك
#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;
}