Menu
Coddy logo textTech
flag Ar iconالعربيةdown icon

بحث

الدرس 6 من 14 في دورة Tries - سلسلة هياكل البيانات #8 على Coddy.

البحث عن كلمة هو النقيض الطبيعي لعملية الإدراج: انتقل للأسفل من الجذر حرفاً واحداً في كل مرة، متبعاً الأبناء المطابقين. إذا لم يكن لدى العقدة الحالية في أي نقطة ابن للحرف التالي، فإن الكلمة ليست موجودة في الـ trie ويمكننا إرجاع false على الفور.

إذا تمكنا من المرور عبر كل حرف، فسنصل إلى عقدة. الإجابة هي أياً كانت القيمة التي يشير إليها علم isEndOfWord لتلك العقدة. هذا هو التمييز الجوهري: بعد إدراج "car"، يكون المسار لـ "ca" موجوداً في الـ trie، ولكن يجب أن تظل search("ca") ترجع false لأن لا أحد قام بتمييز تلك العقدة كنهاية لكلمة.

challenge icon

التحدي

سهل

أضف طريقة 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;
}

جميع دروس Tries - سلسلة هياكل البيانات #8