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