השלמה אוטומטית
שיעור 12 מתוך 14 בקורס טריות (עצי קידומות) – סדרת מבני נתונים מס׳ 8 של Coddy.
זהו מקרה השימוש הקלאסי של trie: בהינתן מה שהמשתמש הקליד עד כה, הציגו את כל המילים המאוחסנות שמתחילות בקידומת הזאת. עברו אל צומת הקידומת; אם אינכם יכולים, החזירו רשימה ריקה. לאחר מכן סיירו בתת-העץ שמתחתיו ואספו כל מילה שתמצאו.
כשאתם יורדים במהלך חיפוש ה-DFS, בנו את המילה בהדרגה על ידי הוספת התו של הקשת שזה עתה עברתם בה. בכל פעם שאתם מגיעים לצומת שבו isEndOfWord הוא true, הנתיב הנוכחי הוא אחת מההתאמות.
אתגר
בינוניכתבו פונקציה autocomplete שמקבלת מערך מחרוזות words ומחרוזת prefix, ומחזירה את רשימת המילים מהמערך שמתחילות ב־prefix.
הרשימה המוחזרת חייבת להיות בסדר עולה (אלפביתי). אם אין מילים מתאימות, החזירו רשימה ריקה.
חובה להשתמש במחלקה Trie (שסופקה בקובץ trie יחד עם trienode) — אין להשתמש במבנים מובנים בשפה כמו קבוצות, מילונים או מפות לצורך ספירה או מעקב.
נסו בעצמכם
#include <stdio.h>
#include <stdlib.h>
#include <string.h>
#include "solution.h"
int main() {
char l1[4096], prefix[1024];
if (!fgets(l1, sizeof(l1), stdin)) l1[0] = 0;
if (!fgets(prefix, sizeof(prefix), stdin)) prefix[0] = 0;
l1[strcspn(l1, "\r\n")] = '\0';
prefix[strcspn(prefix, "\r\n")] = '\0';
char* words[1024]; int n = 0;
char* tok = strtok(l1, " \t");
while (tok && n < 1024) { words[n++] = tok; tok = strtok(NULL, " \t"); }
int out_n = 0;
char** res = autocomplete(words, n, prefix, &out_n);
for (int i = 0; i < out_n; i++) { printf("%s", res[i]); if (i + 1 < out_n) printf(" "); }
printf("\n");
if (res) free(res);
return 0;
}
כל השיעורים ביחידה טריות (עצי קידומות) – סדרת מבני נתונים מס׳ 8
3אתגרי תרגול
הקידומת המשותפת הארוכה ביותרספירת מילים עם קידומתהשלמה אוטומטיתהמילה הארוכה ביותר במילוןחלוקת מילהתרגלו בעצמכם: קומפיילר C אונליין