קווין שמידט: לעתים, בעת בנייה תכנית, ייתכן שתרצי לנצל מבנה הנתונים המכונה במילון. מפתחות מפות מילון, שהם בדרך כלל מחרוזות, לערכים, ints, תווים, מצביע לאובייקט כלשהו, מה שאנחנו רוצים. זה בדיוק כמו במילונים רגילים מילות המפה שדרך הגדרות. 

מילונים לספק לנו את יכולת לאחסן מידע קשור עם משהו ולבדוק את זה מאוחר יותר. אז איך אנחנו באמת ליישם מילון, למשל, קוד C שאנחנו יכולים להשתמש באחת מהתוכניות שלנו? ובכן, יש הרבה דרכים שבן אנחנו יכולים ליישם את מילון. 

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

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

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

אובייקט שסוגיו הוא struct יש צומת שני חלקים קרא נתונים וילדים. אנחנו כבר עזבנו את חלק הנתונים כתגובה כדי להיות מוחלף על ידי רכיב הכרזה כאשר צומת struct היא שולב בתכנית C. חלק הנתונים של צומת עלול להיות ערך בוליאני כדי לציין אם או לא את הצומת מייצגת את ההשלמה של מפתח מילון או שזה יכול להיות מחרוזת המייצגת את ההגדרה של מילה במילון. 

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

בואו לקבל מבט קרוב יותר של צומת השורש בדיאגרמה שלנו, שבו יש אין נתונים הקשורים אליו, כפי שצוין על ידי העדרו של פרצוף המחייך ב חלק הנתונים. החיצים המשתרעים מהחלקים ילדי המערך מייצגים הלא צומת מצביעים לצומת אחרים. לדוגמא, החץ המשתרעת האלמנט השני של ילדים מייצג את האות B במפתח במילון. ובתרשים הגדול יותר אנחנו מתייגים אותו עם B. 

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

נניח שאנחנו רוצים להסתכל למעלה מתאים ערך עבור האמבטיה המפתח. אנו נתחיל את המראה שלנו בצומת השורש. ואז ניקח את האות הראשונה שלנו מפתח, ב ', ולמצוא את מתאים לזהות במערך הילדים שלנו. שים לב שיש בדיוק 26 נקודות במערך, אחד עבור כל אות של האלפבית. ויהיה לנו את הנקודות מייצגות את אותיות האלף בית לפי סדר. 

אנחנו נסתכל על המדד השני לאחר מכן, מדד אחד, עבור ב 'באופן כללי, אם אנחנו יש לי כמה אנחנו C התו האלפביתי אפשר לקבוע את הנקודה המקבילה במערך הילדים באמצעות חישוב כזה. היינו יכולים להשתמש בילדים גדולים יותר מערך אם אנחנו רוצים להציע מבט מ מפתחות עם מגוון רחב יותר של תווים, כמו כל תווי ASCII מוגדרים. 

במקרה זה, את המצביע במערך הילדים שלנו ב מדד אחד הוא לא ריק. אז אנחנו נמשיך לחפש את האמבטיה המרכזית. אם אי פעם נתקלו במצביע null במקום הנכון בילדים מערך בזמן שאנחנו חציתי את צמתים, אז אנחנו נצטרך להגיד לנו ש לא הצליח למצוא שום דבר לאותו מקש. 

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

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

אם ניסינו לחפש את האמבטיה המרכזית, שני לאינדקס של המערך שעברה את הצומת, מקביל לאות H, הייתי קיימתי מצביע null. אז אמבטיה היא לא נמצאת במילון. וכך הגיבורים הוא ייחודיים בכך שהמפתחות אף פעם לא מאוחסנים באופן מפורש ב מבנה הנתונים. אז איך אנחנו מכניסים משהו לגיבורים? 

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

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

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

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

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

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

אם אנחנו לא עושים את ההנחה הזאת ש אורך המפתח הוא חסום על ידי קבוע קבוע, ולאחר מכן כניסה ולהסתכל למעלה, במקרה הגרוע ביותר, הם ליניאריים ב אורכו של המפתח. שים לב כי מספר הפריטים המאוחסן בגיבורים אינו משפיע על המראה או זמן כניסה. זה השפיע רק על ידי אורכו של המפתח. 

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

ניסיונות נוטים להשתמש הרבה מקום. זה בניגוד לשולחן חשיש, שבו אנו זקוקים לצומת חדשה אחד בלבד לאחסן כמה זוג ערך מפתח. עכשיו, שוב בתאוריה, חלל גדול הצריכה לא נראית כמו גדול להתמודד, במיוחד בהתחשב בכך שמודרני יש מחשבים ג'יגה ו ג'יגה בייט של זיכרון. אבל מסתבר שעדיין יש לנו לדאוג שימוש וזיכרון ארגון למען ביצועים, שכן מחשבים מודרניים יש מנגנונים במקום תחת מכסה המנוע כדי להאיץ את הגישה לזיכרון. 

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

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

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

זה גם קל להשיג רשימה זו בסדר אלפביתי מאז אלמנטים של מערך הילדים מסודרים בסדר אלפביתי. אז אני מקווה שאתה תשקלי נתינה מנסה לנסות. אני קווין שמידט, וזה CS50. 

אה, זה הוא תחילתו של הירידה. אני מצטער. סליחה. סליחה. סליחה. 

שביתת ארבעה. אני בחוץ. סליחה. סליחה. סליחה. מצטער לעשיית האדם צריך לערוך את זה להשתגע. 

סליחה. סליחה. סליחה. סליחה. 

SPEAKER 1: עבודה טובה. זה נעשה ממש טוב.