התייעצות למימוש TRIE בשפת C

[cha_had]

שלום,

אני מנסה לממש בשפת C (קומפיילר VS 2013) את העץ TRIE שבו כל צומת תיראה כפי במתואר בתמונה שצירפתי. הקושי העיקרי שלי הוא איך לממש אותו.

הכלל הוא כזה: כל צומת (NODE) בעץ תכיל מערך בגודל 27 בדיוק של אותיות שה-ABC באנגלית בלבד, כאשר התא הראשון יהיה דולר (מיוצג ע"י דולר) והוא למעשה מציין סוף מחרוזת (כמו באסמבלי).

שאר האיברים במערך יהיו בעלי מפתח char של אותיות ה-ABC.

בנוסף כל תא במערך שנמצא בצומת, יכיל מצביע לבן (האות הבאה של המחרוזת כמו next*) וכן מצביע להורה (האות הקודמת של המחרוזת כמו prev*) כאשר הכלל הוא שבהתחלה, כל המצביעים של האותיות להורה ולבן יהיו מאותחלים ל-NULL.

אם וכאשר רוצים שצומת מסוימת בעץ תייצג אות, אז המצביע ה-NEXT שלה (לבן) לה יהיה NULL.

 

התחלתי מימוש התחלתי כזה מתואר בתמונה נוספת, ורציתי לדעת האם הכיוון שלי למימוש העץ הוא נכון?

זאת ועוד, רציתי לשאול האם ניתן להגדיר את המבנה tnode כך שהמערך שלו יכיל את כל התווים הדרושים ואתחול המצביעים ל-NULL בלי שאצטרך להציב ב-MAIN?

תודה על העזרה.

חיים

[cha_had]

למי שלא הבין אני מנסה לחסוך את מה שרשום בתמונה -אתחול מבנה הנתונים כך שהיה מיידי ולא על ידי לולאה.

[ralman]

אתחול אותיות הוא מיותר, אתה יודע שקיימת אות אם הפוינטר אינו NULL.

כתובת האות ה-i הינה:

i'-'a'+1'

פרט לדולר אותו מחשבים בנפרד.

 

לאתחול מהיר יש שיטה שמשתמשטת ב-memset בשביל להציב 0 בכל התאים והיא די מהירה, בדר"כ לא תהיה בעיה עם זה כי NULL מוגדר כ-0.

 

למה כל אות צריכה להחזיק את האב?

 

בפועל כל מה שאתה צריך כאן הוא מערך אחד ב-tNode בגודל sigma בשביל להחזיק את כתובות ההבאים.