Menu
Coddy logo textTech

הוספה

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

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

כשתגיעו לסוף המילה, סמנו את הצומת שהגעתם אליו באמצעות isEndOfWord = true. הדגל הזה הוא שמבדיל בהמשך בין מילה אמיתית שנשמרה לבין מסלול שקיים רק משום שהוא קידומת של משהו אחר.

הוספת "cat" ולאחר מכן "car" חולקת את המסלול c -> a ומתפצלת רק בתו השלישי. השיתוף הזה הוא שהופך טריות לחסכוניות כל כך במקום עבור מילונים.

challenge icon

אתגר

קל

הוסף מתודה insert למחלקה Trie.

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

  • התחל ב־root. עבור כל תו c ב־word, אם לצומת הנוכחי אין ילד עבור c, הוסף שם TrieNode חדש.
  • עבור אל אותו ילד והמשך.
  • אחרי התו האחרון, סמן את 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); }
    }
    return 0;
}

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

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