Menu
Coddy logo textTech

חיפוש

שיעור 6 מתוך 14 בקורס טריות (עצי קידומות) – סדרת מבני נתונים מס׳ 8 של Coddy.

חיפוש מילה הוא ההפך הטבעי מהכנסה: מתקדמים מהשורש, תו אחד בכל פעם, ועוקבים אחר הילדים התואמים. אם בשלב כלשהו אין לצומת הנוכחי ילד עבור התו הבא, המילה אינה נמצאת בטרייה, ואפשר להחזיר מיד false.

אם נצליח להתקדם דרך כל התווים, נגיע לצומת. התשובה היא מה שמציין הדגל isEndOfWord של אותו צומת. זו ההבחנה החשובה: אחרי הכנסת "car", הנתיב עבור "ca" קיים בטרייה, אבל search("ca") עדיין חייבת להחזיר false, כי אף אחד לא סימן את הצומת הזה כסוף של מילה.

challenge icon

אתגר

קל

הוסיפו מתודה search למחלקה Trie.

היא מקבלת מחרוזת word ומחזירה:

  • true אם word הוכנסה לטריי קודם לכן.
  • 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;
}

כל השיעורים ביחידה טריות (עצי קידומות) – סדרת מבני נתונים מס׳ 8

תרגלו בעצמכם: קומפיילר C אונליין