הוספה
שיעור 5 מתוך 14 בקורס טריות (עצי קידומות) – סדרת מבני נתונים מס׳ 8 של Coddy.
כדי להוסיף מילה לטרייה, רדו מהשורש, תו אחד בכל פעם. עבור כל תו במילה: אם לצומת הנוכחי אין צומת בן עבור התו הזה, צרו TrieNode חדש וחברו אותו. כך או כך, עברו לצומת הבן הזה והמשיכו לתו הבא.
כשתגיעו לסוף המילה, סמנו את הצומת שהגעתם אליו באמצעות isEndOfWord = true. הדגל הזה הוא שמבדיל בהמשך בין מילה אמיתית שנשמרה לבין מסלול שקיים רק משום שהוא קידומת של משהו אחר.
הוספת "cat" ולאחר מכן "car" חולקת את המסלול c -> a ומתפצלת רק בתו השלישי. השיתוף הזה הוא שהופך טריות לחסכוניות כל כך במקום עבור מילונים.
אתגר
קלהוסף מתודה 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 אונליין