Menu
Coddy logo textTech

מספר מילים

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

כמה מילים שונות יש כרגע בטרייה הזו? אין מונה שמתעדכן, ולכן עלינו לעבור על העץ ולספור את הצמתים שבהם isEndOfWord הוא true.

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

שימו לב שהדבר מטפל באופן טבעי גם בכפילויות: הכנסת "cat" שלוש פעמים עדיין מסמנת צומת אחד כסוף של מילה, ולכן הספירה היא 1. גם קידומות שמעולם לא הוכנסו בפני עצמן אינן נספרות — הצמתים שלהן קיימים, אבל isEndOfWord הוא false עבורן.

challenge icon

אתגר

קל

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

היא אינה מקבלת קלט ומחזירה את מספר המילים הייחודיות המאוחסנות כרגע בטרייה. עבור בטרייה החל מהשורש וספור כל צומת שהערך של 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); }
        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"); }
        if (strcmp(cmd, "delete") == 0) { char* arg = strtok(NULL, " \t"); if (arg) Trie_delete(&t, arg); }
        if (strcmp(cmd, "wordCount") == 0) { printf("%d\n", Trie_wordCount(&t)); }
    }
    return 0;
}

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

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