[השמעת מוסיקה] DAVID מלאן: זה CS50. וזה הוא גם ההתחלה ו end-- כמו literally-- כמעט הסוף שבוע שישה. 

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

קהל: [לא ברור] DAVID מלאן: אכן. ועוד בצורה משעשעת, חס וחלילה, אנו מחזיקים הרצאה אחת ביום שישי בתחילת הסמסטר, זה מה שאנו רואים במקרה. אז היום, אנחנו אוכלים בקצת נוסף על מבני נתונים. ולתת לך יותר ממוצק מודל המנטלי לבעיות בחמש, שנמצא עכשיו החוצה. שגיאות כתיב, שבו, אנחנו למסור לך קובץ טקסט כ -100,000 בתוספת מילות באנגלית, ו אתה הולך לי כדי להבין איך לטעון אותם בחוכמה לזיכרון, לזכרון RAM, באמצעות כמה נתונים מבנה על פי בחירתך. 

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

קהל: הכנסה. 

DAVID מלאן: הכנסה. מה אתה מתכוון? 

קהל: בכל מקום לאורך הרשימה [לא ברור]. 

DAVID מלאן: טוב. אז אתה יכול להכניס אלמנט בכל מקום אתה רוצה באמצע הרשימה מבלי לערבב כל דבר, שהגענו למסקנה, במיון שלנו דיונים, לא בהכרח דבר טוב, כי זה לוקח זמן לעבור למעשה כל בני האדם אלה שמאלה או ימינה. וכך, עם רשימה מקושרת, אתה יכול רק להקצות עם malloc, צומת חדשה, ולאחר מכן לעדכן כמה pointers-- שני, שלושה ניתוחים max-- ואנחנו מסוגלים חריץ מישהו בכל מקום לרשימה. 

מה עוד היה יתרון על רשימה מקושרת? כן? 

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

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

קהל: לא גישה אקראית. 

DAVID מלאן: אין גישה אקראית. אבל למי אכפת? הגישה אקראית לא נשמעה משכנעת. 

קהל: [לא ברור] DAVID מלאן: בדיוק. אם אתה רוצה יש לי algorithm-- מסוים ותן לי למעשה מציע חיפוש בינארי בפרט, ש הוא אחד מאלה שהשתמשנו די bit-- אם אין לך גישה אקראית, אתה לא יכול לעשות את זה חשבון פשוט למצוא כמו אלמנט האמצע ולקפוץ ישר לעניין. אתה במקום להתחיל בשעה הראשונה אלמנט ואופן ליניארי חיפוש משמאל לימין אם אתה רוצה למצוא באמצע או כל גורם אחר. 

קהל: זה כנראה לוקח יותר זיכרון. 

DAVID מלאן: לוקח יותר זיכרון. איפה שנוסף העלות מגיעה בזיכרון? 

קהל: [לא ברור] DAVID מלאן: בדיוק. במקרה זה כאן, היה לנו רשימה מקושרת למספרים שלמים, ובכל זאת, אנחנו מכפילים כמות הזיכרון אנחנו צריכים גם על ידי אחסון מצביעים אלה. עכשיו פחות מזה עניין גדול כ structs שלך לקבל גדול ואתה אחסון לא מספר אך אולי סטודנט או חפץ אחר. אבל הנקודה בהחלט נשארה. וכך מספר הפעולות ברשימות מקושרות נקראו היו O הגדול של יניארי n--. דברים כמו הכנסה או חיפוש או מחיקה במקרה אלמנט היה במקרה בסופו של הרשימה אם זה מיון או לא. 

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

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

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

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

קהל: א 'מינוס 

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

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

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

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

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

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

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

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

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

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

קהל: n. DAVID מלאן: שמעתי O הגדול של n. לא נכון. אבל אנחנו להפריד מדוע ברגע. מה עוד יכול להיות? 

קהל: [לא ברור] DAVID מלאן: ותן לי לעשות את זה מבחינה ויזואלית. אז נניח שזה האות S 

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

אבל כמובן, ברגע שאני מגיע ל אדם שני ששם הוא A או B או C סופו של דבר, אם אני כבר בשימוש ליניארי חיטוט כפתרון שלי, זמן הריצה של הכנסה במקרה הגרוע ביותר הוא בעצם הולך לרדת ברמה למה? ואני לא שמעתי את זה כאן בצורה נכונה בשלב מוקדם. קהל: [לא ברור] DAVID מלאן: אז זה n אכן פעם אחת יש לך סט נתונים גדול מספיק. אז, מצד האחד, אם המערך שלך הוא גדול מספיק הנתונים שלך, והוא דליל מספיק, לך מקבל זמן קבוע זה יפה. אבל ברגע שאתה מתחיל מקבל יותר ויותר אלמנטים, ורק מבחינה סטטיסטית אתה מקבל יותר אנשים עם המכתב שמם כאו המכתב B, הוא עלול לרדת ברמה למשהו יותר ליניארי. אז לא ממש מושלם. אז אנחנו יכולים לעשות טובים יותר? 

ובכן, מה היה שלנו פתרון לפני כשאנחנו רוצה יותר דינמי מאשר משהו כמו מערך מותר? קהל: [לא ברור] DAVID מלאן: מה עשיתי להציג? כן. אז רשימה מקושרת. ובכן, בואו נראה מה קשור רשימה עשויה לעשות עבורנו במקום. ובכן, הרשה לי להציע לנו ש לצייר את התמונה באופן הבא. עכשיו זה שונה תמונה מדוגמה מטקסט שונה, למעשה, ש הוא למעשה משתמש במערך של גודל 31. ומחבר זה פשוט החליט חשיש מחרוזות אינו מבוסס על השמות של האדם, אבל על סמך תאריכי הלידה שלהם. ללא קשר לחודש, שהם חשבו אם אתה נולד ביום הראשון של חודש או ה -31 של חודש, המחבר יהיה חשיש המבוסס על הערך ש, כדי להפיץ את השמות מתוך קצת יותר מסתם 26 נקודות עשויות לאפשר. ואולי זה קצת יותר מדי מאשר ללכת עם אותיות אלף-בית, כי כמובן יש כנראה יותר אנשים בעולם עם שמות התחלה כי עם יותר מבהחלט כמה מכתבים אחרים של האלפבית. אז אולי זה קצת אחיד יותר, בהנחה התפלגות אחידה של תינוקות על פני חודש. 

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

קהל: רשימה מקושרת. 

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

עכשיו, בהתאם, מה זמן הריצה עכשיו? אם אני רוצה להכניס מישהו יום ההולדת שלו הוא יום 31 באוקטובר, שבו הוא או היא הולכת? בְּסֵדֶר. בתחתית מאוד שבו כתוב 31. וזה מושלם. זה היה זמן קבוע. אבל מה אם אנחנו מוצאים מישהו אחר יום ההולדת שלו הוא, בואו נראה, אוקטובר, נובמבר, דצמבר 31? איפה הוא או היא הולכת? אותו דבר. שני שלבים אף. זה קבוע אם כי לא? בְּסֵדֶר. ברגע זה. אבל במקרה הכללי, יותר אנשים נוסיף, הסתברותי, אנחנו הולכים כדי לקבל יותר ויותר התנגשויות. 

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

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

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

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

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

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

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

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

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

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

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

ואתם יודעים מה? אם זה רק צומת בזיכרון ש אני יצרתי עם malloc, באמצעות struct כפי שאנו תראו בקרוב, אני הולך לעשות זה-- אני הולך לצייר חץ מ הדבר שייצג D למטה לצומת חדשה זה. ועכשיו, ראשון הבא מכתב בשמו של דייבן, V-- D-A-V-- אני הולך קדימה ולצייר צומת אחר כך, לפי, אלמנטי V כאן, ש אנחנו עושים הגרלה אופס instance--. אנחנו לא נמשוך לשם. זה הולך כאן. 

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

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

אז מה אנחנו יכולים לעשות במקום הוא טיפול בכל אחד מהאלמנטים האלה כאולי יש שני אלמנטים בתוכם. אחד הוא מצביע, אכן, כמו שאני כבר עושה. אז כל אחד מהתיבות הללו לא רק תא אחד. אבל מה אם החלק העליון one-- התחתון של אחד הולך להיות null, כי אין דבנפורט עדיין. מה אם ראש אחד איזה ערך מיוחד? וזה הולך להיות קצת קשה לצייר אותו בגודל זה. אבל נניח שזה רק סימן ביקורת. בדוק. D-A-V-E-N הוא מחרוזת במבנה נתונים זה. 

בינתיים, אם יש לי יותר מקום כאן, אני יכול לעשות את P-O-R-T, ואני יכול לשים את הסימון בצומת שיש לו את האות T בסוף מאוד. אז זה בצורה מסיבית מבנה נתונים למראה מורכב. וכתב היד שלי בהחלט לא עוזר. אבל אם אני רוצה להכניס משהו אחר, לשקול מה היינו עושה. אם אנחנו רוצים לשים דוד ב, היינו לעקוב אחר אותו ההיגיון, D--V, אבל עכשיו הייתי נקודה בעולם הבא אלמנט לא מE, אבל מאני לד אז יש הולך להיות יותר צמתים בעץ הזה. אנחנו הולכים להיות שיחת malloc יותר. אבל אני לא רוצה לעשות בלגן שלם של תמונה זו. אז בואו במקום להסתכל אחד זה כבר נסח מראש כמו זה עם לא נקודה, נקודה, נקודות, אבל מערכים רק מקוצרים. אבל כל אחד מצומת בעץ את זה כאן מייצג את אותו thing-- מערך ריי בגודל 26. 

או אם אנחנו רוצים להיות באמת נכון עכשיו, מה אם שמו של מישהו כ גרש, בוא תניח כי כל צומת בעצם יש כמו 27 אינדקסים בזה, לא רק 26. אז זה עכשיו הולך להיות נתונים מבנה נקרא T-R-אני-E trie--. לבלבים, שהוא כביכול מבחינה היסטורית שם חכם לעץ זה מותאם במיוחד ל אחזור, שכמובן, מאוית עם I-E כך שזה לבלבים. אבל זה ההיסטוריה של הלבלבים. 

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

כי למרות ש, באותו הרגע, אני רק באמצעות המצביע של D'ו וV וEs וNS, אני מבזבז את לעזאזל של הרבה זיכרון. אבל איפה אני מבלה משאב אחד, אני נוטה לעשות לקבל בחזרה אחר. אז אם אני מבלה יותר מרחב, מה כנראה התקווה? שאני מבלה פחות מה? קהל: פחות זמן. DAVID מלאן: זמן. עכשיו למה שעשוי להיות? ובכן, מה היא ההכנסה זמן, במונחים של O הגדול עכשיו, של שם כמו בדייבן או דבנפורט או דוד? ובכן, דייבן היה חמישה שלבים. דבנפורט יהיה תשעה שלבים, כך שזה יהיה עוד כמה צעדים. דוד יהיה חמישה שלבים, כמו גם. אז אלה הם בטון מספרים, אבל אין ספק שיש גבול עליון ל אורכו של שמו של מישהו. ואכן, בבעיה סטים של חמישה מפרט, אנחנו הולכים להציע שזה משהו זה תווים 40-ומשהו. 

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

להיות המחרוזת הוכנס, שהופך אותה זה אסימפטוטית קבועה O הגדול time-- של אחד. ולמען אמת, רק ב העולם האמיתי, זה משמעות הדבר היא הכנסה שם של דייבן לוקח כמו חמישה שלבים, או דבנפורט תשע צעדים, או דוד חמישה צעדים. זה לא רע בכלל פעמים ריצה קטנות. ואכן, זה מאוד דבר טוב, במיוחד כאשר זה לא תלוי בסך מספר האלמנטים שביש. אז איך אנחנו יכולים ליישם את זה סוג של מבנה בקוד? זה קצת יותר מורכב, אבל עדיין זה רק יישום של אבני בניין בסיסי. אני הולך להגדיר מחדש צומתנו כדלקמן: bool נקרא word-- וזה אפשר לקרוא לכל דבר. אבל בול מייצג מה ציירתי כסימן ביקורת. כן. זה קצה חוט במבנה נתונים זה. 

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

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

עכשיו Meanwhile-- אה, שאלה. 

קהל: מה מילה בול? 

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

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

שאלות אחרות על ניסיונות? כן. 

קהל: מהו החפיפה? מה אם יש לך דייב ולהתפלל? DAVID מלאן: מושלם. מה אם יש לך דייב ולהתפלל? אז אם אנחנו מכניסים, אומרים כינוי, לDavid-- Dave-- D-A-V-E? זהו למעשה סופר פשוט. אז אנחנו הולכים רק לקחת ארבעה שלבים. D-A-V-E. ומה אני צריך לעשות כדי לעשות ברגע שאני מכה שהצומת הרביעית? רק הולך לבדוק. אנחנו כבר טובים ללכת. עשה. ארבעה שלבים. זמן קבוע אסימפטוטית. ועכשיו אנחנו כבר הצביעו על כך שגם דייב ואתפלל הן מחרוזות במבנה. אז לא בעיה. ושים לב כמה הנוכחות של דייבן את לא עושה את זה לקחת כל זמן פחות או יותר זמן לדייב ולהיפך. 

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

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

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

עכשיו תור שמו נקרא מאוד במכוון. זה קו כי יש כמה הגינות לזה. נכון? זה היה נשאב סוג של אם יש לך הגעתי לשם ראשון בחנות אפל אבל אתה ביעילות התחתונה מגש, שכן עובדי אפל פופ האדם האחרון ש למעשה יש בשורה. אז ערימות ותורים, למרות ש פונקציונלי הוא סוג של same-- זה פשוט אוסף זה משאבים זה הולך לגדול וshrink-- יש היבט הגינות זה לזה, לפחות בעולם האמיתי, שבו פעולותיך לממש שונים באופן מהותי. Stack-- תור rather-- הוא אמר לי שתי פעולות: תור n ותור ד. או שאתה יכול לקרוא להם כל מספר של דברים. אבל אתה רק רוצה ללכוד הרעיון שהאדם הוא הוספה ואחד סופו של דבר הפחתה. 

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

קהל: תור. DAVID מלאן: טוב, תור. בטח. מה עוד? 

קהל: רשימה מקושרת. 

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

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

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

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

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

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

קהל: קטן יותר בצד השמאל. 

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

עכשיו איך אתה יכול למצוא את המספר 44? אתה היה מתחיל בשורש ואומר, HM. 55 הוא לא 44 אז אני רוצה ללכת תקין או שאני רוצה ללכת שמאלה? ובכן, ברור שאתה רוצה ללכת שמאלה. ואז זה בדיוק כמו הטלפון דוגמא ספר בחיפוש בינארי באופן כללי יותר. אבל אנחנו מיישמים את זה עכשיו קצת יותר דינמי מ מערך עשוי לאפשר. ולמעשה, אם אתה רוצה להיראות בקוד, שבמבט הראשון בטוח. זה נראה כמו חבורה של קווים שלמה. אבל זה פשוט יפה. אם אתה רוצה ליישם פונקציה חיפוש בשם מטרתו בחיים הוא לחפש ערך כמו n, מספר שלם, ואתה עבר בpointer-- אחד מצביע לצומת של השורשים, ולא, של עץ שממנו אתה יכול לגשת לכל דבר אחר, שים לב איך בצורה ישירה אתה יכול ליישם את ההיגיון. אם העץ הוא null, כמובן שזה לא שם. בואו פשוט נחזיר שקר. נכון? אם תמסור לי שום דבר, אין שם כלום. 

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

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

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

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

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

[וידאו השמעה] 

-הוא בא עם מסר, עם פרוטוקול כולו. הוא הגיע לעולם של אכזריות חומות אש, נתבים אדישים, וסכנות הרבה יותר גרועה ממוות. הוא מהיר. הוא חזק. הוא TCP / IP, ויש לו את הכתובת שלך. "לוחמים נטו." [END הפעלת וידאו] DAVID מלאן: בשבוע הבא יגיע. נראים אותך אז. [וידאו השמעה] -ואז עכשיו, "מחשבות עמוקות" על ידי לדייבן פארנהאם. -David תמיד מתחיל הרצאות עם, "בסדר." למה לא, "הנה הפתרון לקבוצת הבעיה "של השבוע או "אנחנו נותנים את כולכם?" [צוחק] [END הפעלת וידאו]