[השמעת מוסיקה] דוד י מלאן: בסדר. זה CS50. זהו שבוע חמישה המשיכו, ואנו יש לי כמה חדשות טובות וחדשות רעות. אז חדשות טובות היא שCS50 משיק ביום שישי הקרוב. אם ברצונכם להצטרף אלינו, הראש לכתובת הרגילה כאן. חדשות טובות עוד יותר, לא הרצאה ביום שני הקרוב 13th. מעט פחות חדשות טובות יותר, חידון אפס הוא ביום רביעי הבא. פרטים נוספים יכולים להיות מצא בכתובת אתר זו כאן. ובמשך כמה הימים הבאים יהיה לנו למלא את החסר בכל הקשור לחדרים שנהיה לנו שמורות. חדשות טובות יותר היא שתהיינה עוד להיות סקירה כמובן רחבות פגישה זו באה יום שני בערב. השארו לקורס של אתר למיקום ופרטים. סעיפים, למרות שזה חג, גם לפגוש גם כן. החדשות הטובות ביותר, להרצות ביום שישי הבא. אז זה שאנחנו מסורת יש לי, לפי תכנית הלימודים. פשוט- זה הולך להיות מדהים. אתה תראה דברים כמו מבני נתונים בזמן קבוע ושולחנות חשיש ועצים ומנסה. ונדבר על בעיות יום הולדת. חבורה של דברים שלמות מחכה ביום שישי הבא. אישור. בכל אופן. אז תזכור, כי אנחנו כבר התמקדות בתמונה הזאת של מה בתוך הזיכרון של המחשב שלנו. אז זיכרון או זיכרון RAM הוא שבו תוכניות קיים בזמן שאתה מפעיל אותם. אם תלחץ פעמים סמל לרוץ כמה תכנית לחץ לחיצה כפולה או סמל כדי לפתוח קובץ כלשהו, זה נטען מקשיח לנהוג או כונן מצב מוצק לזכרון RAM, זיכרון גישה אקראי, שבו הוא חי עד את הכח יוצא, מכסה המחשב הנייד נסגר, או שאתה יוצא מהתכנית. עכשיו זיכרון ש, של שכנראה שיש לך 1 ג'יגה בימים אלה, 2 ג 'יגה, או אפילו הרבה יותר, הוא הניח את כלל עבור תכנית נתונה בסוג כזה של מלבני מודל רעיוני לפי שיש לנו הערימה בתחתית וכל מינים דברים אחרים בראש. הדבר בחלקו העליון שראינו בתמונה הזאת בעבר, אבל מעולם לא דיבר על הוא מגזר הטקסט שנקרא. קטע טקסט הוא רק דרך מפוארת לומר אפסים ואחדים ש להלחין תכנית הידור שלך בפועל. אז בלחיצה כפולה כאשר אתה Microsoft Word על Mac או PC שלך, או כאשר אתה מפעיל נקודה לקצץ מריו על מחשב לינוקס בחלון המסוף שלך, האפסים ואחדים שמרכיבים מילה או מריו מאוחסן באופן זמני בזכרון RAM של המחשב שלך שבנקרא קטע טקסט עבור תכנית מסוימת. מתחת לזה הולך אותחל ונתונים שלא אותחלו. זה חומר כמו משתנים הגלובליים, שאנחנו כבר לא בשימוש רב של, אבל במקרה יש לנו היה לי משתנים הגלובליים או שהוגדר באופן סטטי מחרוזות ש הוא מקודד קשה במילות כמו "שלום" שאינם נלקחים מהמשתמש הבקידוד קשיח בתכנית שלך. עכשיו, למטה בתחתית אנחנו יש לי הערימה מה שנקרא. והערימה, עד כה, אנחנו כבר משתמש עבור אילו סוגים של מטרות? מה הערימה שימשה במשך? כן? קהל: פונקציות. דוד י מלאן: לפונקציות? באיזה מובן לפונקציות? קהל: כשאתה מתקשר לפונקציה, טיעונים מועתקים על גבי הערימה. דוד י מלאן: בדיוק. כשאתה מתקשר לפונקציה, שלה טיעונים מועתקים על גבי הערימה. אז כל X או Y של של או של או B של שאתה עובר לפונקציה לשים על באופן זמני הערימה מה שנקרא, בדיוק כמו אחד מאננברג מגשי אוכל, וגם דברים כמו משתנים מקומיים. אם פונקצית foo או ההחלפה שלך שלך יש לי פונקציה משתנים מקומיים, כמו טמפ ', שני אלה בסופו של בערימה. עכשיו, אנחנו לא מדברים יותר מדי על שלהם, אבל משתני הסביבה האלה בתחתית שראינו לפני זמן מה כאשר אני היה לשפץ במקלדת יום אחד ואני התחלתי בגישת דברים כמו argv 100 או argv 1,000, רק elements-- אני שוכח אחר המספרים אבל ש לא היו אמור להיות גישה על ידי לי. התחלנו לראות כמה סימנים פאנקי על המסך. אלה היו מה שנקרא משתני סביבה כמו הגדרות גלובליות עבורי תכנית או למחשב שלי, לא שאינו קשור לאחרון באג שדנו, Shellshock, שהיה הפוקד לא מעט מחשבים. עכשיו סוף סוף, בהתמקדותה של היום אנו סופו של דבר נהיה על הערימה. זה עוד נתח של זיכרון. ויסודו את כל זה זיכרון הוא אותו החומר. זה באותה החומרה. אנחנו רק סוג של טיפול באשכולות שונים בתים למטרות שונות. הערימה היא גם הולכת להיות בו משתנים וזיכרון שאתה מבקש ממערכת ההפעלה מאוחסן באופן זמני. אבל יש סוג של בעיה כאן, כמו בתמונה מרמזת. סוג שיש לנו משני ספינות עומדים להתנגש. כי כפי שאתה משתמש יותר ויותר הערימה, וכפי שאנו רואים היום ואילך, כפי שאתה משתמש יותר ויותר של ערימה, בוודאי דברים רעים עלולים לקרות. ואכן, אנחנו יכולים לגרום לזה במכוון או שלא בכוונה. אז הסחרור המסוכן שעבר הזמן היה בתכנית זו, שלא משרת שום פונקציונלי מטרה אחרת מאשר להפגין איך אתה כאיש רע באמת יכול לקחת יתרון של באגים בתכניתו של מישהו ולהשתלט על תכנית או אפילו מערכת כל מחשב או שרת. אז רק כדי מבט בקצרה, אתה שם לב עיקרי שבתחתית לוקח בשורת הפקודה טענות, לפי argv. ויש לה קריאה לפונקצית f, בעצם פונקציה אלמונית בשם f, וזה עובר בargv [1]. אז מה מילת המשתמש מקליד ב הפקודה אחרי השם של תכנית זו, ולאחר מכן פונקציה עד שרירותית זו עליון, f, לוקחת במחרוזת, char * AKA, כפי שאנו כבר החלו לדון, וזה פשוט קורא לזה "בר". אבל אנחנו יכולים לקרוא לזה שום דבר. ואז זה מצהיר, בתוך של f, מערך של תווים נקרא c-- 12 תווים כאלה. עכשיו, על ידי הסיפור שסיפרתי לי לפני רגע, שבו בזיכרון הוא ג, או 12 אלה תווים הולכים בסופו? רק שיהיה ברור. כן? קהל: בערימה. דוד י מלאן: בערימה. אז ג הוא משתנה מקומי. אנחנו מבקשים 12 תווים או 12 בתים. מי הולך בסופו של על הערימה שנקרא. עכשיו סוף סוף היא פונקציה אחרת זה זה בעצם די שימושי, אבל אנחנו כבר לא ממש בשימוש זה בעצמנו, strncopy. זה אומר העתקת מחרוזת, אבל n רק אותיות, n תווים. אז דמויות n תהיה הועתק מבר לג. וכמה? אורכו של בר. אז במילים אחרות, ש שורה אחת, strncopy, הולך להעתיק יעילות בר לג. עכשיו, רק כדי לצפות סוג של מוסר ההשכל של הסיפור הזה, מה שעלול להיות בעייתי כאן? למרות שאנחנו בודקים את האורך של בר והעברתו לstrncopy, מה תחושת הבטן שלך אומרת לך היא עדיין שבור על תכנית זו? כן? קהל: לא כולל חדר לאופי null. דוד י מלאן: לא כולל חדר לאופי null. פוטנציאל, שלא כמו ב בפועל העבר שאנחנו עושים אפילו לא יש כל כך הרבה כמו בתוספת 1 ל להכיל כי אופי null. אבל זה אפילו יותר גרוע מזה. מה עוד אנחנו לא מצליחין לעשות? כן? קהל: [לא ברור] דוד י מלאן: מושלם. אנחנו כבר בקידוד קשיח 12 די שרירותיים. זה לא כל כך הרבה בעיה, אבל העובדה שאנחנו אפילו לא בודקים אם אורכו של בר הוא פחות מ12, ובמקרה זה הולך להיות בטוח לשים אותו לזיכרון ג נקרא שאנחנו כבר הוקצו. ואכן, אם בר הוא כמו 20 תווים, פונקציה זו נראית שהעתקה 20 תווים מבר לג, ובכך לוקח לפחות 8 בתים כי זה לא צריך להיות. זה המשמעות כאן. אז בתכנית קצרה, שבורה. לא כזה ביג דיל. אולי אתה מקבל אשמת פילוח. היו לנו את כל הבאגים בתוכניות. אולי לכולנו יש באגים בתוכניות כרגע. אבל מה המשמעות? ובכן, הנה גרסה מוגדלת-בשל תמונה של זיכרון המחשב שלי. זה החלק התחתון של הערימה שלי. ואכן, בתחתית מאוד הוא מה ערימה נקראת הורה שגרתית, דרך מפוארת לומר שזה עיקרי. כך שכל מי שקרא לפונקציה f על זה אנחנו מדברים. אז זהו תחתית הערימה. כתובת שולח הוא משהו חדש. זה תמיד היה שם, תמיד היה בתמונה ש. אנחנו פשוט אף פעם לא הפנינו את תשומת לב אליו. כי מתברר הדרך ג עובד היא כי כאשר פונקציה אחת קוראת אחרת, לא רק לעשות את הטיעונים של פונקציה מקבלת דחף על הערימה, לא רק לעשות מקומית של הפונקציה משתנים לקבל דחף על הערימה, משהו שנקרא כתובה שולח גם מקבל לשים על הערימה. באופן ספציפי, אם שיחות עיקריות פ.ו., של עיקרי כתובת שלו בזיכרון, שור משהו, ביעילות מקבל לשים על הערימה כך שכאשר f נעשה הרצתו יודע לאן לקפוץ חזרה בטקסט קטע על מנת להמשיך וביצוע. אז אם אנחנו כאן מבחינה קונספטואלית, בעיקרי, אז f נקראת. איך f יודעת ש לשליטה ביד אחורית? ובכן, זה קצת פירורי לחם באדום כאן, נקרא את כתובת השולח, זה פשוט בדיקות, מה היא שכתובת שולח? הו, תן לי לקפוץ לראש העיקרי כאן. וזה קצת של פשטנות, בגלל האפסים ואחדים לעיקרי הם מבחינה טכנית עד כאן במגזר טק. אבל זה הרעיון. f רק צריך לדעת מה למקום שבי שליטת סופו של דבר חוזרת. אבל מחשבי הדרך הניחו את דברים ארוכים כמו משתנים מקומיים ו טיעונים הוא כזה. אז בחלק העליון של התמונה הזאת ב הכחול היא מסגרת המחסנית לf, אז כל מה ש של הזיכרון שf במיוחד הוא שימוש. אז בהתאם, שם לב ש בר הוא בתמונה הזאת. בר היה הטיעון שלו. ואנחנו טוענים שטיעונים ל פונקציות לקבל דחף על הערימה. וג, כמובן, הוא גם בתמונה זו. ורק למטרות סימנים,, שם לב בפינה השמאלית העליונה זה מה שיהיה ג סוגר 0 ו אז קצת למטה בצד הימין הוא סוגר ג 11. אז במילים אחרות, אתה יכול לדמיין שיש רשת של בתים שם, הראשון שבם הוא שמאלי עליון, תחתון שלה הוא האחרון של 12 בתים אלה. אבל עכשיו מנסה להריץ קדימה. מה עומד לקרות אם אנחנו עוברים בבר מחרוזת זה זמן רב יותר מג? ואנחנו לא בודקים אם זה אכן זמן רב יותר מאשר 12. איזה חלק של תמונה זה הולך לקבל מוחלף על ידי בתים 0, 1, 2, 3, נקודת נקודת נקודה, 11, ולאחר מכן רע, 12, 13 דרך 19? מה שהולך לקרות כאן, אם אפשר להסיק מההזמנה שסוגר ג 0 הוא בחלק העליון וסוגר ג 11 הוא סוג של מטה מימין? כן? קהל: ובכן, זה הולך כדי להחליף את בר * char. דוד י מלאן: כן, זה נראה כמו אתה הולך לדרוס בר char *. וגרוע מזה, אם אתה שולח בבאמת ארוך מחרוזת, אתה עשוי אפילו להחליף מה? כתובת השולח. אשר שוב, הוא בדיוק כמו סימני דרך לספר את התכנית שבה לחזור לכאשר f נעשה להיקרא. אז מה הרעים בדרך כלל לעשות הוא אם הם נתקל תכנית שהם סקרנים אם הוא ניצול, מרכבה בצורה כזאת שהוא או היא יכולה לקחת יתרון של באג ש, בדרך כלל הם לא מקבלים זכות זו בפעם הראשונה. הם פשוט להתחיל לשלוח, למשל, מחרוזות אקראיות בתכנית שלך, אם במקלדת, או בכנות שהם כנראה לכתוב תוכנה קטנה רק ליצור באופן אוטומטי מחרוזות, ולהתחיל לדפוק על התכנית שלך על ידי שליחה בהרבה תשומות שונות באורכים שונים. ברגע שקריסות התכנית שלך, זה דבר מדהים. כי זה אומר שהוא או שהיא גילתה מה הוא כנראה אכן באג. ואז הם יכולים לקבל חכמים יותר ולהתחיל להתמקד יותר באופן צר על איך לנצל באג ש. בפרט, את מה שהוא או היא עלולה לעשות הוא לשלוח, במקרה הטוב, שלום. זה לא עניין גדול. זה מחרוזת זה קצר מספיק. אבל מה אם הוא או היא שולחת, ואנו להכליל אותו כ, התקפת code-- כך אפסים ואלה שעושים דברים כמו rm-rf, כי להסיר את כל מה מהכונן הקשיח או לשלוח דואר זבל או איכשהו לתקוף את המכונה? אז אם כל אחד מאלה מכתבים רק מייצג, מבחינה קונספטואלית, התקפה, התקפה, התקפת התקפה, קצת קוד, רע שמישהו כתב אחר, אבל אם האדם שהוא חכם מספיק לא רק כולל את כל מאותם rm-RFS, אלא גם יש לי כמה הבתים האחרונים שלו או שלה להיות מספר המתאים לכתובת שלו או קוד התקפה משלה שהוא או היא עברה רק על ידי מתן אותו בשורת הפקודה, אתה יכול למעשה להערים על המחשב לשם לב שf נעשה ביצוע, הו, זה זמן עבורי לקפוץ בחזרה לכתובת השולח האדומה. אבל בגלל שהוא או היא צריכה איכשהו חפיפת שכתובת שולח עם המספר שלהם, והם חכמים מספיק להגדיר ש מספר מתייחס, כפי שאתה לראות בחלק העליון הסופר פינה השמאלית יש, הכתובת האמיתית במחשב זיכרון של חלק מקוד ההתקפה שלהם, בחור רע יכול להערים על המחשב להפעלת הקוד שלו או שלה. וקוד ש, שוב, יכול להיות כל דבר. זה בדרך כלל נקרא קוד פגז, וזה רק דרך לומר שזה לא בדרך כלל משהו פשוט כמו rm-rf. זה בעצם משהו כמו Bash, או תכנית בפועל זה נותנת לו או שליטתה התכנותית לבצע כל דבר אחר שהם רוצים. אז בקיצור, זה כל נובע מהעובדה הפשוטה כי הבאג הזה המעורב לא בודק הגבולות של המערך שלך. ומשום שהדרך עבודת מחשבים היא שהם להשתמש במחסנית מ ביעילות, מבחינה קונספטואלית, תחתון בעד, אבל אז אלמנטים אתה דוחף אל הערימה לגדול במורד עליון, זה הוא בעייתי מאוד. עכשיו, יש דרכים לעקוף את זה. ולמען אמת, יש שפות שבה לעבודה בסביבה זו. ג'אווה היא חיסון, למשל, לנושא המסוים הזה. בגלל שהם לא נותנים לך עצות. הם לא נותנים לך כתובות זיכרון ישירות. אז עם הכח הזה שיש לנו לגעת בשום דבר בזיכרון אנחנו רוצים מגיעים, יש להודות, סיכון גדול. אז לפקוח עין. אם, בכנות, בחודשים או בשנים הבאות, בכל עת אתה קורא על כמה ניצול של תכנית או שרת, אם אי פעם תראה את רמז של משהו כמו התקפת גלישת מאגר, או הצפת מחסנית היא סוג אחר של התקפה, דומה ברוחו, כמה שמעורר באתר שם, אם אתה יודע את זה, זה כולם מדבר על רק עולה על גדותיו בגודל של איזו דמות מערך או מערך באופן כללי יותר. שאלות, אז, על זה? אל תנסה את זה בבית. בסדר. אז malloc עד כה היה חדש שלנו חבר שבאנחנו יכולים להקצות זיכרון שאנחנו לא בהכרח יודעים ב מראש שאנחנו רוצים ולכן אין לנו לקוד קשה לנו מספרים כמו 12 תכנית. ברגע שהמשתמש אומר לנו כמה הנתונים שהוא או היא רוצה קלט, אנחנו יכולים malloc כך הרבה זיכרון. אז malloc מתברר, ל במידה שכבר משתמשים בה, במפורש בפעם האחרונה, ולאחר מכן אתם כבר משתמשים בה לgetstring ביודעין ל מספר שבועות, כל הזיכרון של malloc מגיע מהערימה שנקרא. ובגלל זה getstring, למשל, יכול להקצות זיכרון דינמי בלי לדעת מה אתה הולך להקליד מראש, למסור לך בחזרה מצביע לזיכרון ש, וזיכרון שעדיין שלך כדי לשמור על, גם לאחר getstring תשואות. משום זוכר אחרי כל זה הערימה היא כל הזמן עולה ויורד, למעלה ולמטה. וברגע שזה הולך למטה, שפירושו כל זיכרון פונקציה זו משמשת צריכה לא בשימוש על ידי כל אדם אחר. זה ערכי זבל עכשיו. אבל הערימה היא עד כאן. ומה שיפה הוא שmalloc כאשר malloc מקצה זיכרון עד כאן, זה לא השפיע, ל לרוב, על ידי הערימה. ולכן כל פונקציה יכולה לגשת זיכרון שכבר malloc'd, אפילו על ידי פונקציה כמו getstring, גם לאחר שהוא חזר. עכשיו, היפוכה של malloc ללא תשלום. ואכן, השלטון ש צריך להתחיל לאמץ היא כל, כל, כל פעם שאתה משתמש malloc את עצמך אתה חייב להשתמש חינם, סופו של דבר, באותו מצביע. כל הזמן הזה אנחנו כבר כותבים מרכבה, קוד מרכבה, מסיבות רבות. אבל אחד מהם היה באמצעות ספריית CS50, ש עצמו הוא במכוון מרכבה, זה דליפת זיכרון. בכל פעם שיש לך בשם getstring בשבועות האחרונים אנחנו מבקשים ההפעלה מערכת, לינוקס, לזיכרון. ואף פעם לא נתן לו פעם אחת בחזרה. ואת זה הוא לא, ב להתאמן, דבר טוב. וValgrind, אחד כלים שהוצגו ב4 Pset, הוא על כל לעזור לך עכשיו למצוא באגים כמו ש. אבל לשמחתם של Pset 4 אתה לא צריך להשתמש בספריית CS50 או getstring. אז כל הבאגים הקשורים לזיכרון סופו של דבר הולך להיות שלך. אז malloc הוא יותר מאשר רק נוח למטרה זו. אנחנו למעשה יכולים כעת לפתור בעיות שונות במהותו, ויסודו לפתור את הבעיות יותר ביעילות בהתאם להבטחתו של שבוע אפס. עד כה זה הכי סקסי מבנה הנתונים שהיו לנו. ועל ידי מבנה נתונים אני רק אומר דרך של זיכרון המשגה באופן שהוא מעבר לרק אומר, זו היא int, זה char. אנחנו יכולים להתחיל לדברים אשכול יחד. אז מערך נראה כך. ומה היה מפתח בכ מערך הוא שזה נותן לך גב אל גב נתחים זיכרון, כל אחד מהם הולך להיות מאותו הסוג, int, int, int, int, או char, char, char, char. אבל יש כמה חסרונות. זה למשל, הוא מערך של גודל שש. נניח שאתה ממלא את המערך הזה עם שש מספרים ולאחר מכן, מכל סיבה ש, המשתמש שלך רוצה לתת לי אתה מספר שביעי. איפה שמת את זה? מה הפתרון אם יש לך נוצר מערך במחסנית, למשל, רק עם בשבוע שני סימון שהצגנו, סוגריים מרובעים עם מספר בפנים? ובכן, יש לך שש מספרים בתיבות אלה. מה היית האינסטינקטים שלך להיות? איפה היית רוצה לשים את זה? קהל: [לא ברור] דוד י מלאן: מצטער? קהל: שים את זה בצד. דוד י מלאן: שים את זה בצד. אז קצת יותר בצד הימין, מחוץ לתיבה זו. שיהיה נחמד, אבל זה מתברר שאתה לא יכול לעשות את זה. כי אם אתה כבר לא שאל עבור נתח זה של זיכרון, זה יכול להיות במקרה שזה נמצא בשימוש על ידי כמה משתנה אחרים לגמרי. תחשוב שוב כשבוע כאשר הנחנו את השמות של Zamyla ודווין וגייב בזיכרון. הם היו, פשוטו כמשמעו, גב אל גב אל גב. אז אנחנו לא יכולים בהכרח לסמוך על כך שכל מה ששל כאן הוא זמין עבורי לשימוש. אז מה עוד אתה יכול לעשות? ובכן, הבין אותך פעם אחת צריך מערך של גודל שבע, רק אתה יכול ליצור מערך של גודל שבע ולאחר מכן להשתמש ללולאה או לולאה בזמן, להעתיק אותו למערך החדש, ואז איכשהו רק להיפטר מערך זה או פשוט להפסיק להשתמש בו. אבל זה לא יעיל במיוחד. בקיצור, מערכים לא נותנים לי אתה באופן דינמי לשנות את הגודל. אז מצד האחד אתה מקבל גישה אקראית, וזה מדהים. כי זה מאפשר לנו לעשות דברים כמו הפרד ומשול, חיפוש בינארי, שכולן יש לנו דיבר על על המסך כאן. אבל אתה מצייר את עצמך לפינה. ברגע שאתה מכה סוף המערך שלך, אתה צריך לעשות מאוד פעולה יקרה או לכתוב חבורה של קוד כולו עכשיו להתמודד עם בעיה ש. אז מה אם במקום שהיו לנו משהו שנקרא רשימה, או קשור רשימה בפרט? מה אם במקום שיש מלבנים לגבות לגבות לגבות, יש לנו מלבנים שישאירו קצת קצת מרחב תמרון ביניהם? ולמרות שאני כבר נמשך זה תמונה או מותאם תמונה זו מאחד הטקסטים כאן כדי לחזור ל גב אל גב מאוד מסודר, במציאות, אחד מהמלבנים אלה יכול להיות כאן בזיכרון. אחד מהם היה יכול להיות כאן. אחד מהם היה יכול להיות כאן, כאן, וכן הלאה. אבל מה אם אנחנו ציירנו, במקרה זה, חיצים המקשרים איכשהו אלה מלבנים יחד? ואכן, ראינו טכני גלגולו של חץ. מה יש לנו בשימוש באחרון ימים ש, מתחת למכסת המנוע, הוא נציג של חץ? מצביע, נכון? אז מה אם, במקום רק אחסון המספרים, כמו 9, 17, 22, 26, 34, מה אם אנחנו מאוחסנים לא רק מספר אבל מצביע ליד כל מספר כזה? כך שהרבה כמו שהיית חוט מחט דרך חבורה של בד כולו, דברים איכשהו קשירה יחד, יכול באופן דומה אנחנו עם מצביעים, כ התגלגל על ​​ידי חצים כאן, סוג של לארוג יחד מלבנים בודדים אלה על ידי יעילות באמצעות מצביע ליד כל מספר ש מצביע על כמה מספר הבא, ש מצביע, בתורו, כמה מספר הבא? אז במילים אחרות, מה ש אם אנחנו באמת רוצים כדי ליישם משהו כזה? ובכן, למרבה הצער, מלבנים אלה, לפחות אחד עם 9, 17, 22, וכן הלאה, אלה הם כבר לא ריבועים נחמדים עם מספרים בודדים. התחתון, המלבן מתחת ל -9, למשל, מייצג את מה שצריך להיות מצביע, 32 סיביות. עכשיו, אני עדיין לא מודע לכל סוג נתונים בC שנותן לך לא רק int אבל מצביע לגמרי. אז מה הפתרון אם אנחנו רוצים להמציא התשובה שלנו לזה? כן? קהל: [לא ברור] דוד י מלאן: מה זה? קהל: מבנה חדש. דוד י מלאן: כן, אז למה לא אנחנו יוצרים מבנה חדש, או בC, struct? ראינו structs לפני, אם לזמן קצר, שבו עסקנו במבנה סטודנט כמו זה, שהיה לו שם ובית. בPset 3 פריצה שבה השתמשה כל חבורה של GRect וGOvals structs-- כי סטנפורד נוצר כדי מידע אשכול יחד. אז מה אם אנחנו לוקחים את אותו הרעיון הזה של מילות מפתח "typedef" ו "struct," ולאחר מכן כמה דברים תלמיד ספציפי, ולהתפתח זה לבא: typedef struct node-- והצומת היא רק מדעי מחשב מאוד גנריות טווח משהו במבנה הנתונים, מיכל במבנה הנתונים. צומת אני טוען הוא הולכת להיות n int, לגמרי פשוט, ואז עוד קצת במסתוריות, קו שני זה, צומת struct * הבא. אבל במונחים טכניים פחות, מה זה קו שני של קוד בתוך הסוגריים המסולסלים? כן? קהל: [לא ברור] דוד י מלאן: מצביע לצומת אחרת. אז אמנם, תחביר קצת מסתורי. אבל אם אתה קורא את זה פשוטו כמשמעו, הבא הוא שמו של משתנה. מהו סוג הנתונים שלה? זה קצת מפורט הפעם, אבל זה של צומת struct סוג *. בכל פעם שראינו כוכב משהו, ש אומר שזה מצביע לאותו סוג נתונים. אז הבא הוא ככל הנראה מצביע לצומת struct. עכשיו, מה היא צומת struct? ובכן, שמתי לב שאתה רואה אותם אותן מילות בצד ימין למעלה. ואכן, אתה גם רואה את המילה "צומת" כאן למטה בפינה השמאלית התחתונה. וזה בעצם רק נוחות. שים לב כי בהגדרת תלמידנו יש את המילה "סטודנט" רק פעם אחת. וזה בגלל שתלמיד האובייקט לא היה התייחסות עצמית. אין שום דבר פנימי של תלמיד שצריך להצביע על תלמיד אחר, פרסיי. זה יהיה סוג של מוזר בעולם האמיתי. אבל עם צומת בצמודה רשימה, שאנחנו עושים ברצון צומת להיות רפרנציאלית לאובייקט דומה. וכך להבחין בשינוי כאן הוא לא רק מה שבפנים בסוגריים המסולסלים. אבל אנחנו מוסיפים את המילה "צומת" בחלק העליון, כמו גם הוספתו לתחתית במקום "סטודנט". וזה רק פרט טכני כך ש, שוב, מבנה הנתונים שלך יכול להיות התייחסות עצמית, כך ש צומת יכולה להצביע על עוד צומת כזה. אז מה זה סופו של דבר הולך אומר לנו? ובכן, בתוך אחד, הדברים האלה הוא את התוכן של הצומת שלנו. הדבר הזה כאן, ימני עליון, הוא פשוט כל כך כי, שוב, אנו יכולים להתייחס לעצמנו. ולאחר מכן את החומר החיצוני ביותר, למרות שהצומת היא מונח חדש, אולי, זה עדיין אותו דבר כמו תלמיד ומה היה מתחת למכסת המנוע בSPL. אז אם אנחנו עכשיו רוצים להתחיל יישום רשימה מקושר זה, איך ייתכן שאנו מתרגמים משהו כזה קוד? ובכן, בואו רק לראות דוגמא לתכנית ש בעצם משתמש רשימה מקושרת. בין קוד ההפצה של היום הוא תכנית בשם רשימת אפס. ואם אני מפעיל את זה אני יצרתי סופר GUI פשוט, ממשק משתמש גרפי, אבל זה באמת רק printf. ועכשיו אני מרשה לעצמי כמה תפריט options-- מחיקה, הוספה, חיפוש, וTraverse. וצא. אלה הם פעולות רק משותפות על מבנה נתונים הידוע ברשימת קישור. עכשיו, מחק את הולך למחוק מספר מהרשימה. הכנס הולך להוסיף מספר לרשימה. חיפוש הולך להיראות למספר ברשימה. וחוצה הוא רק דרך מפוארת לומר, ללכת ברשימה, להדפיס את זה, אבל זה הכל. אין לשנותו בכל דרך. אז בואו ננסה את זה. בואו נלך קדימה וסוג 2. ואז אני הולך הכנס את המספר, אומר 9. הזן. ועכשיו התכנית שלי היא פשוט מתוכנת לומר, רשימה היא עכשיו 9. עכשיו, אם אני הולך קדימה ו אל הכניסו שוב, תן לי לי ללכת קדימה ולהקטין את התצוגה ולהקליד ב17. עכשיו הרשימה שלי היא 9, אז 17. אם אני עושה להכניס שוב, בואו נדלג על אחד. במקום 22, כמו לכל התמונה שיש לנו כבר מסתכל כאן, תן לי לקפוץ קדימה והכנס 26 הבא. אז אני הולך להקליד 26. הרשימה היא כפי שאני מצפה. אבל עכשיו, רק כדי לראות אם הקוד הזה הולך להיות גמיש, תן לי עכשיו סוג 22, אשר לפחות מבחינה רעיונית, אם אנחנו שמירה על זה מסודרים, שהוא אכן הולך להיות עוד שער עכשיו, צריך ללכת בין 17 ו26. אז על Enter. ואכן, זה עובד. ואז עכשיו תן לי להכניס את אחרון, לתמונה, 34. בסדר. אז לעת עתה תן לי לקבוע כי למחוק וTraverse וחיפוש לעשות, למעשה, לעבוד. למעשה, אם אני מפעיל חיפוש, בואו לחפש את המספר 22, הזן. זה מצא 22. אז זה מה שזה תכנית רשימת אפס עושה. אבל מה הוא בעצם הולך על שמיישם את זה? ובכן, פעם ראשונה שאולי יש לי, ואכן יש לי, קובץ שנקרא list0.h. ואי שם שביש זה קו, typedef, צומת struct, אז יש לי הסוגריים המסולסלים שלי, int n, ו אז struct-- מה הייתה ההגדרה? צומת struct הבאה. אז אנחנו צריכים את הכוכב. עכשיו מבחינה טכנית אנחנו נכנסים ההרגל של ציור אותו כאן. ייתכן שתראה ספרי לימוד ו אזכור באינטרנט לעשות את זה שם. זה תפקודיות שווה ערך. למעשה, זה אופייני קצת יותר. אבל אני אהיה בקנה אחד עם מה ש שעשינו בפעם שעברה, ולעשות את זה. ואז לבסוף, אני הולך לעשות את זה. אז בקובץ כותרת אי שם, בlist0.h היום הוא הגדרת struct זה, ואולי עוד כמה דברים אחרים. בינתיים בlist0c יש הולך להיות כמה דברים. אבל אנחנו הולכים רק להתחיל ולא לסיים את זה. List0.h הוא קובץ שאני רוצה לכלול בקובץ C שלי. ואז בשלב מסוים אני הולך להיות int, עיקרי, לביטול. ואז אני הולך יש לי כמה מטלות כאן. אני גם הולך ליש לי אב טיפוס, כמו חלל, חיפוש, int, n, שמטרתו בחיים היא כדי לחפש אלמנט. ולאחר מכן כאן למטה אני טוען ב הקוד של היום, חלל, חיפוש, int, n, לא פסיק אבל סוגריים מסולסלים פתוחים. ועכשיו אני רוצה לחפש איכשהו לאלמנט ברשימה זו. אבל אין לנו מספיק מידע על המסך עדיין. יש לי לא ממש ייצג את הרשימה עצמה. אז דרך אחת שנוכל ליישם רשימה מקושרת בתכנית הוא אני סוג של רוצה לעשות משהו כמו מצהיר קשור רשימה כאן. לשם פשטות, אני הולך לעשות זה עולמי, למרות שבאופן כללי לא צריך לעשות את זה יותר מדי. אבל זה יהיה לפשט דוגמא זו. אז אני רוצה להכריז רשימה עד מקושר כאן. עכשיו, איך ייתכן שאני עושה את זה? הנה התמונה של רשימה מקושרת. ואני ממש לא יודע ברגע איך אני הולך ללכת על ייצוג כל כך הרבה דברים עם אחד בלבד משתנה בזיכרון. אבל תחשוב לרגע. כל הזמן הזה שהיינו לנו מחרוזות, שאותם אנו מתגלה להיות מערכים של דמויות, שאותם אנו חשף רק כדי להיות מצביע לתו הראשון במערך של תווים שהסתיים null. אז לפי ההיגיון הזה, ועם זה סוג תמונה של זריעת המחשבות שלך, מה צריכים אנחנו בעצם לכתוב בנו קוד לייצג רשימה מקושרת? כמה מהמידע הזה אנחנו צריכים כדי ללכוד בקוד C, היית אומר? כן? קהל: אנחנו צריכים מצביע לצומת. דוד י מלאן: מצביע לצומת. בפרט, שהצומת היית שלך אינסטינקטים להיות לשמור מצביע ל? קהל: הצומת הראשונה. דוד י מלאן: כן, כנראה רק הראשון. ושים לב, הראשון צומת היא צורה שונה. זה רק חצי מהגודל של struct, כי זה אכן רק מצביע. אז מה שאתה אכן יכול לעשות הוא להכריז רשימה מקושרת להיות של צומת סוג *. ובואו פשוט נקראים לזה ראשון ולאתחל אותו לאפס. אז null, שוב, הוא הקרוב לתמונה כאן. לא רק משמש כnull כמו מיוחד ערך החזרה על דברים כמו getstring וmalloc, null הוא גם אפס מצביע, חוסר מצביע, אם תרצה. זה רק אומר ששום דבר עדיין כאן. עכשיו ראשון, אני יכול כבר בשם כל דבר הזה. אני יכול לקרוא לה "רשימה" או כל מספר של דברים אחרים. אבל אני קורא לזה "ראשון", כך ש קווים אותו בתמונה הזאת. אז בדיוק כמו מחרוזת יכול להיות מיוצג עם הכתובת של הבית הראשון שלה, כך יכולה רשימה מקושרת. ואנו רואים נתונים אחרים להיות מיוצגים על מבנים רק עם מצביע אחד, חץ 32 סיביות, מצביע בצומת הראשונה במבנה. אבל עכשיו בואו לצפות בעיה. אם אני זוכר רק בתכנית שלי את הכתובת של הצומת הראשונה, הראשון מלבן במבנה נתונים זה, מה יותר טוב היה להיות במקרה על יישום של שאר הרשימה שלי? מה פרט מפתח שקורה כדי להבטיח את זה באמת עובד? ועל ידי "באמת עובד" אני כלומר, בדומה למחרוזת, מאפשר לנו לעבור מהתו הראשון בשמו של דווין לשני, לשלישי, ל רביעי, עד הסוף, איך אנחנו יודעים כשאנחנו בסופו של הדבר של רשימה מקושרת שנראית כך? כאשר זה null. ואני כבר מיוצג מסוג זה כמו כמו כוח מהנדס חשמל, עם ההארקה הקטנה סמל, של מיני. אבל זה רק אומר שnull במקרה זה. אתה יכול לצייר את זה כל מספר דרכים, אבל מחבר זה קרה להשתמש בסמל זה כאן. כל עוד אנחנו בחוטים כל צמתים הללו יחד, זוכר רק שבו הראשון הוא, כל כך הרבה זמן כפי שאנו לשים סמל מיוחד ב הצומת האחרון ברשימה, ואנו נשתמש null, כי זה מה יש לנו לרשותנו, רשימה זו אינה שלמה. וגם אם אני רק אתן לך מצביע האלמנט הראשון, אתה, המתכנת, בהחלט יכול לגשת לכל השאר. אבל בואו אתן את הדעה שלך לשוטט קצת, אם הם לא כבר די wandered-- מה הולך להיות זמן הריצה של מציאת כל דבר ברשימה זו? לעזאזל, זה O הגדול של n, וזה לא רע, בהגינות. אבל זה הוא ליניארי. אנחנו ויתרנו על מה תכונה של מערכים על ידי ההעברה יותר כיוון תמונה זו של אופן דינמי שזורה יחד או צמוד צמתים? אנחנו כבר ויתרנו על גישה אקראית. מערך הוא נחמד, כי הכל מבחינה מתמטית הוא גב אל גב אל גב אל גב. למרות שהתמונה הזאת נראה די, ואפילו למרות שזה נראה כמו בלוטות אלה הם יפה במרווחים, במציאות הם יכולים להיות בכל מקום. OX1, Ox50, Ox123, Ox99, אלה צמתים יכולים להיות בכל מקום. בגלל malloc עושה להקצות זיכרון מהערימה, אך בכל מקום בערמה. אתה לא בהכרח יודע שזה הולך להיות גב אל גב אל גב. וכך התמונה הזאת במציאות של לא הולך להיות די זה די. אז זה הולך לקחת קצת לפעול ליישום פונקציה זו. אז בואו ליישם חיפוש עכשיו. ואנו רואים סוג של דרך חכמה לעשות את זה. אז אם אני פונקציית חיפוש ו אני מקבל n משתנה, מספר שלם לחפש, אני צריך לדעת תחביר חדש להתבוננות פנימה של מבנה זה הצביע, למצוא n. אז בואו נעשיתי את זה. אז קודם כל אני הולך ללכת קדימה ולהכריז צומת *. ואני הולך לקרוא לזה מצביע, רק על ידי ועידה. ואני הולך לאתחל אותו לראשון. ועכשיו אני יכול לעשות את זה במספר הדרכים. אבל אני הולך לנקוט בגישה נפוצה. בעוד המצביע אינו שווה ל null, וזה תחביר תקף. וזה רק אומר לבצע את הפעולות הבאות, כך כל עוד אתה לא מצביע על שום דבר. מה אני רוצה לעשות? אם n נקודת מצביע, תנו לי לחזור לזה, equals-- שווה מה? איזה ערך אני מחפש? N בפועל שהתקבל ב. אז הנה עוד תכונה של C ושפות רבות. למרות שצומת המבנה המכונה יש n ערך, לגיטימי לחלוטין יש גם ויכוח מקומי או משתנים בשם n. כי גם אנחנו, עם עיניים אנושיות, יכולות להבחין שn זה הוא ככל הנראה שונה מn זה. בגלל התחביר שונה. יש לך נקודה ומצביע, ואילו זה אחד יש אין דבר כזה. אז זה בסדר. זה בסדר לקרוא להם את אותם הדברים. אם אני אתה מוצא את זה, אני הולך רוצה לעשות משהו כמו להכריז שמצאנו n. ואנחנו נשאיר את זה כ להגיב או קוד pseudocode. אחר, והנה חלק מעניין, מה ש אני רוצה לעשות אם הצומת הנוכחית לא מכיל n שאכפת לי? איך אני משיג את הדברים הבאים? אם האצבע שלי ב רגע הוא PTR, וזה מצביע על מה ש הראשון הוא מצביע ב, איך אני מזיז את האצבע שלי לצומת הבאה בקוד? ובכן, מה סימני הדרך שאנחנו הולך לעקוב במקרה זה? קהל: [לא ברור]. דוד י מלאן: כן, כל כך הקרוב. אז אם אני חוזר לשלי קוד כאן, אכן, אני הולך קדימה ואומרים מצביע, ש רק variable-- זמני זה שם מוזר, PTR, אבל זה בדיוק כמו temp-- אני הולך להגדיר מצביע שווה לכל מה שis-- המצביע ושוב, זה הולך להיות מרכבה קטנה לנקודת moment-- הבאה. במילים אחרות, אני הולך לקחת אותי אצבע שמצביעה בצומת זה כאן ואני הולך לומר, אתה יודע מה, תסתכל על השדה הבא ולהזיז את האצבע ל מה שזה מצביע על. וזה הולך לחזור, לחזור, לחזור. אבל כאשר עושה את האצבע שלי להפסיק לעשות משהו בכלל? ברגע שמה שורה של בעיטות קוד ב? קהל: [לא ברור] דוד י מלאן: אם בזמן שנקודה המצביע אינו שווה ל null. בשלב האצבע שלי כמה הולך להיות מצביע על null ואני הולך להגשים לי זה הסוף של רשימה זו. עכשיו, זה קצת שקר לבן לפשטות. מתברר שלמרות שאנחנו רק למדתי בסימון נקודה זו למבנים, מצביע הוא לא struct. ptr הוא מה? רק כדי להיות קטנוני יותר. זה מצביע לצומת. זה לא צומת עצמו. אם לא היה לי כוכב כאן, מצביע absolutely-- זה צומת. זה כמו בשבוע אחד הכרזה על משתנה, אף שהמילה "צומת" היא חדשה. אבל ברגע שאנחנו מציגים כוכב, שזה עתה מצביע לצומת. ולמרבה הצער, אתה לא יכול להשתמש סימון הנקודה למצביע. אתה צריך להשתמש בחץ סימון, אשר, בצורה בולטת, הפעם הראשונה שכל פיסה תחביר נראה אינטואיטיבי. זה נראה ממש כמו חץ. וכדי שזה דבר טוב. וכאן למטה, פשוטו כמשמעו, נראה כמו חץ. אז אני חושב שזה la-- אני לא חושב שאני מבצע מעל here-- אני חושב שזה הקטע החדש שעבר תחביר שאנחנו הולכים לראות. ותודה לאל, זה אכן קצת יותר אינטואיטיבי. עכשיו, לאלה מכם ש ייתכן שיעדיף את הדרך הישנה, אתה עדיין יכול להשתמש בסימון הנקודה. אבל כמו לכל היום השני של שיחה, אנחנו ראשון צריך ללכת לשם, ללכת של לטפל, ולאחר מכן לגשת לשדה. אז זה גם נכון. ולמען אמת, זה הוא קצת קפדן יותר. אתה אומר, פשוטו כמשמעו, dereference המצביע וללכת לשם. ואז לתפוס .n, השדה שנקרא n. אבל בכנות, אף אחד לא רוצה להקליד או לקרוא את זה. וכך העולם המציא סימון החץ, ש שווה, זהה, זה רק סוכר תחבירי. אז דרך מפוארת של אומר את זה נראה טוב יותר, או נראה פשוטים יותר. אז עכשיו אני הולך לעשות דבר אחד אחר. אני הולך לומר "הפסקה" ברגע שיש לי מצאתי את זה ולכן אני לא אמשיך לחפש אותו. אבל זה התמצית של פונקציית חיפוש. אבל זה הרבה יותר קל, ב הסוף, לא ללכת דרך הקוד. זה אכן היישום הרשמי חיפוש בקוד ההפצה של היום. אני מעז לומר להוסיף שאינו במיוחד כיף ללכת דרך מבחינה ויזואלית, וגם לא למחוק, אפילו אם כי בסופו של היום הם מסתכמים למדי היוריסטיקה פשוטה. אז בואו נעשיתי את זה. אם תוכל הומור אותי לכאן, אני עשיתי להביא חבורה של מתח כדורים. הבאתי חבורה של מספרים. ואנחנו יכולים לקבל רק כמה מתנדבים לייצג 9, 17, 20, 22, 29, ו34? אז בעצם כולם מי נמצא כאן היום. זה היה אחד, שתיים, שלוש, ארבעה, חמש, שישה אנשים. ואני כבר ביקשתי go-- לראות, לא אחד בחלק האחורי מרים את ידיהם. אישור, אחד, שתיים, שלוש, ארבעה, five-- תן לי לטעון balance-- שש. בסדר, אתה שישה לבוא בעד. אנחנו נצטרך אנשים אחרים. אנחנו הבאנו את מתח כדורים נוספים. ואם אתה יכול, ל רק רגע, שורה את עצמכם עד עתה כמו התמונה הזאת כאן. בסדר. בואו נראה, מה השם שלך? קהל: אנדרו. דוד י מלאן: אנדרו, אתה מספר 9. נחמד לפגוש אותך. הנה לך. קהל: ג'ן. דוד י מלאן: ג'ן. דוד. מספר 17. כן? קהל: אני ג'וליה. דוד י מלאן: ג'וליה, דוד. מספר 20. קהל: נוצרי. דוד י מלאן: נוצרי, דוד. מספר 22. ו? קהל: JP. דוד י מלאן: JP. מספר 29. אז קדימה ולקבל in-- אה אה. אה אה. המתנה. 20. למישהו יש סמן? קהל: יש לי טוש. דוד י מלאן: יש לך טוש? אישור. והאם מישהו יש פיסת נייר? שמור את ההרצאה. יאללה. קהל: יש לנו את זה. דוד י מלאן: יש לנו את זה? בסדר, תודה לך. הנה אנחנו מתחילים. היה זה ממך? אתה פשוט הצלת את היום. אז 29. בסדר. אני באיות שגוי 29, אבל בסדר. קדימה. בסדר, אני אתן לך העט שלך בחזרה לרגע. אז יש לנו האנשים האלה כאן. בואו אחד אחר. גייב, אתה רוצה לשחק האלמנט הראשון כאן? אנחנו זקוקים לך להצביע באנשים הטובים האלה. אז 9, 17, 20, 22, סוג של 29, ולאחר מכן 34. האם אנחנו מאבדים מישהו? יש לי 34. איפה did-- אישור, מי שרוצה להיות 34? אישור, בואו תיכנס, 34. בסדר, זה יהיה בהחלט שווה את השיא. מה שמך? קהל: פיטר. דוד י מלאן: פיטר, בחייך עד. בסדר, אז הנה כל חבורה של צמתים. כל אחד מכם חבר 'ה מייצגת אחד מהמלבנים האלה. וגייב, מוזר במקצת אדם החוצה, מייצג ראשון. אז המצביע שלו הוא קצת יותר קטן על המסך מכל אחד אחר. ובמקרה הזה, כל אחד משמאלך ידיים הולכת או להצביע כלפי מטה, ובכך מייצג את null, כך רק העדר מצביע, או שזה הולך להיות הצבעה בצומת לידך. אז עכשיו אם אתה מעטרים את עצמכם כמו בתמונה כאן, קדימה, נקודה אחד על השני, עם גייב בהצבעה מסוימת ב מספר 9 לייצג את הרשימה. אישור, ומספר 34, יד השמאל שלך צריך רק להיות הצביע על הרצפה. אוקיי, אז זה הוא הרשימה המקושרת. אז זהו התרחיש בשאלה. ואכן, זו היא נציג של כיתה של בעיות שאולי אתה מנסה לפתור עם קוד. אתה רוצה להכניס סופו של דבר אלמנט חדש לרשימה. במקרה זה, אנחנו הולכים תנסה להכניס את המספר 55. אבל יש הולך להיות מקרים שונים לשקול. ואכן, זה הולך להיות אחד של התמונה הגדולה מזנונים כאן, הוא, מה הם המקרים השונים. מה הם שונה אם תנאים או סניפים שאולי יש לך בתכנית? ובכן, המספר שאתה מנסה הכנס, שבו אנו יודעים עכשיו להיות 55, אבל אם אתה לא יודע מראש, אני מעז לומר נופל לתוך לפחות שלוש מצבים אפשריים. איפה עשוי אלמנט חדש יהיה? קהל: וסוף או באמצע. דוד י מלאן: בסוף, ב האמצע, או בתחילת. אז אני טוען שיש לפחות שלוש בעיות שאנחנו צריכים לפתור. בואו לבחור מה אולי ניתן לטעון הפשוט ביותר אחד, שבו האלמנט החדש שייך בתחילת. אז אני הולך ליש קוד די כמו חיפוש, שבו אני פשוט כתבתי. ואני הולך לי PTR, ש אני מייצג כאן עם האצבע שלי, כרגיל. וזכור, מה ערך עשיתי לנו לאתחל ptr ל? אז אנחנו אותחלו זה ל null בתחילה. אבל אז מה שאנחנו עושים ברגע שאנו היו בתוך פונקציית החיפוש שלנו? אנחנו מגדירים את זה שווה לראשון, מה שלא אומר לעשות את זה. אם אני ראשון להגדיר ptr שווה, מה ש צריכה את היד שלי באמת להיות מצביעה על? ימין. אז אם גייב ואני הולכים להיות ערכים שווים כאן, אנחנו צריכים שני הנקודות בבית המספר 9. אז זה היה תחילתו של הסיפור שלנו. ועכשיו זה רק פשוט, למרות שהתחביר הוא חדש. מבחינה מושגית זה רק חיפוש ליניארי. האם 55 שווים 9? או לייתר דיוק, נניח פחות מ 9. מכיוון שאני מנסה להבין איפה לשים את 55. פחות מ 9, פחות מ 17, פחות מ -20, פחות מ22, פחות מ29, פחות מ 34, לא. אז עכשיו אנחנו במקרה אחד מלפחות שלוש. אם אני רוצה להכניס 55 כאן, מה ש קווים של צורך קוד למוצאים להורג? איך עושה את התמונה הזאת של בני אדם צריך לשנות? מה עליי לעשות עם יד השמאל שלי? זה צריך להיות null בתחילה, בגלל שאני בסוף הרשימה. ומה צריך לקרות כאן עם פיטר, זה היה? ברור שהוא הולך להצביע לי. אז אני טוען שיש לפחות שני קווים של קוד בקוד לדוגמא מהיום זה הולך ליישם את זה תרחיש של הוספת 55 בזנב. ואני יכול לקבל הופ מישהו ורק מייצג 55? בסדר, אתה 55 החדשים. אז עכשיו מה אם הבא תרחיש מגיע, ואנחנו רוצים להכניס ב מתחיל או ראש הרשימה זו? ומה השם שלך, המספר 55? קהל: ג'ק. דוד י מלאן: ג'ק? אישור, נחמד לפגוש אותך. ברוכים הבאים על סיפון. אז עכשיו אנחנו הולכים הכנס, למשל, המספר 5. הנה המקרה השני של שלוש באנו עם לפני. אז אם 5 שייכים בתחילת, בואו לראות איך אנחנו מגלים ש. אני לאתחל PTR שלי מצביע למספר 9 שוב. ואני הבנתי, אה, 5 היא פחות מ 9. אז לתקן את התמונה הזאת בשבילנו. של מי ידיים, גייב של או דוד של or-- מה השם של מספר 9? קהל: ג'ן. דוד י מלאן: hands-- של ג'ן איזו מהידיים שלנו צריך לשנות? אוקיי, אז גייב מצביע על מה עכשיו? עליי. אני הצומת החדשה. אז אני רק סוג של מהלך כאן כדי לראות את זה מבחינה ויזואלית. ובינתיים מה אני מצביע ש? ובכל זאת שבו אני אני מצביע. אז זהו זה. אז רק באמת שורה אחת של תיקוני קוד נושא ספציפי זה, זה היה נראה. בסדר, אז זה טוב. ומישהו יכול להיות מציין מיקום עבור 5? בואו למעלה. אנחנו נוציא אותך בפעם הבאה. בסדר, אז now-- ו במאמר מוסגר, שמות אני לא עושה אזכור מפורש של זכות עכשיו, מצביע pred, מצביע קודמו ומצביע חדש, זה השמות ניתנו רק בקוד לדוגמא למצביעים או הידיים שלי שהוא סוג של ההצבעה סביב. מה שמך? קהל: כריסטין. דוד י מלאן: כריסטין. ברוכים הבאים על סיפון. בסדר, אז בואו נשקול עכשיו תרחיש מעט יותר מעצבן, לפי שאני רוצה להכניס משהו כמו 26 לתוך זה. 20? מה? אלה are-- דבר טוב שיש לנו העט הזה. בסדר, 20. אם מישהו יכול לקבל פיסה אחרת נייר מוכן, רק בcase-- בסדר. אה, מעניין. ובכן, זה הוא דוגמא של באג הרצאה. אישור אז מה השם שלך שוב? קהל: ג'וליה. דוד י מלאן: ג'וליה, אתה יכול לצוץ החוצה ולהעמיד פן שאתה אף פעם לא היה שם? אוקיי, זה מעולם לא קרה. תודה לך. אז נניח שאנחנו רוצים להכניס ג'וליה לרשימה מקושרת זה. היא היא המספר 20. וכמובן שהיא הולך להיות שייכים ב begin-- אינו מצביע בשום דבר עדיין. אז היד שלך סוג של יכולה להיות את null או ערך כלשהו אשפה. בואו לספר את הסיפור מהיר. אני מצביע על מספר 5 זה זמן. לאחר מכן אני בודק את 9. אז אני בודק 17. אז אני בודק 22. ואני מבין, אוו, ג'וליה צריך ללכת לפני 22. אז מה צריך לקרות? שידיו צריכים לשנות? ג'וליה, שלי, or-- מה השם שלך שוב? קהל: נוצרי. דוד י מלאן: נוצרי או? קהל: אנדי. דוד י מלאן: אנדי. נוצרי או אנדי? אנדי צריך להצביע על? ג'וליה. בסדר. אז אנדי, אתה רוצה להצביע על יוליה? אבל חכה רגע. בסיפור עד כה, אני הסוג של אחת בתשלום, במובן זה ש מצביע הוא הדבר זה נע ברשימה. אולי יש לנו שם לאנדי, אבל אין משתנה בשם אנדי. משתנה רק אחרים שיש לנו הוא ראשון, שהוא מיוצג על ידי גייב. אז זה בעצם למה כך כה יש לנו לא צריכים את זה. אבל עכשיו על המסך יש להזכיר שוב של מצביע pred. אז תן לי להיות ברור יותר. אם זה מצביע, היה לי טוב יותר לקבל קצת יותר אינטליגנטי על איטרציה שלי. אם לא אכפת לך שלי עובר כאן שוב, מצביע כאן, מצביע כאן. אבל תן לי מצביע pred, מצביע קודמו, שזה סוג של הצבעה על אלמנט הייתי רק ב. אז כשאני הולך כאן, עכשיו עדכוני יד השמאל שלי. כשאני הולך כאן עדכוני היד השמאלי שלי. ועכשיו יש לי לא רק מצביע ל האלמנט שהולך אחרי ג'וליה, עדיין יש לי מצביע אנדי, האלמנט לפני. אז יש לך גישה, במהות, פירורי לחם, אם תרצה, לכל המצביעים הנדרשים. אז אם אני מצביע על אנדי ואני גם מצביעים בנוצרי, שידיו עכשיו צריך להיות הצביע במקום אחר? אז אנדי יכול כעת להצביע על ג'וליה. ג'וליה יכולה כעת להצביע על נוצרי. משום שהיא יכולה להעתיק שלי המצביע של יד ימין. וזה מכניס אותך בצורה יעילה בחזרה למקום הזה כאן. אז בקיצור, למרות שזה הוא לוקח אותנו סוג של לנצח לעדכן למעשה מקושר רשימה, מבין כי הפעולות הם פשוטים יחסית. זה של אחד, שתיים, שלוש שורות קוד סופו של דבר. אבל עוטף אותם שורות קוד מן הסתם זה קצת היגיון שיעילות שואל את השאלה, איפה אנחנו? האם אנחנו בתחילתו, האמצע, או הסוף? עכשיו, בהחלט יש כמה אחרים פעולות שאנו עשויים ליישם. ואת התמונות האלה לכאן רק לתאר מה בדיוק עשינו עם בני אדם. מה לגבי ההסרה? אם אני רוצה, למשל, להסיר את המספר 34 או 55, אולי יש לי את אותו סוג של קוד, אבל אני הולך לצריך שלבים אחד או שניים. משום מה חדש? אם אני מסיר מישהו בסוף, כמו מספר 55 ולאחר מכן 34, מה גם שיש לשנות כמו שאני עושה את זה? יש לי לא evict-- מה השם שלך שוב? קהל: ג'ק. דוד י מלאן: ג'ק. צריך לא רק evict-- ג'ק חינם אני, כך, פשוטו כמשמעו, קורא ג'ק החופשי, או לפחות מדי המצביע יש, אבל עכשיו מה צריך להשתנות עם פיטר? ידו טובה יותר להתחיל כלפי מטה. כי ברגע שאני קורא חינם על ג'ק, אם של פיטר עדיין מצביע על ג'ק ולכן אני שומר חוצים הרשימה והגישה מצביע זה, זה רגע שבי פילוח ידידנו הוותיק פגם באמת עשוי לבעוט ב. בגלל שנתנו בחזרה זיכרון לג'ק. אתה יכול להישאר שם במבוכה לרגע. כי יש לנו רק כמה פעולות סופיות לשקול. הסרת ראש הרשימה, או beginning-- וזה אחד של קצת מעצבן. מכיוון שאנו צריכים לדעת שגייב הוא סוג של מיוחד בתכנית זו. כי אכן, יש לו המצביע שלו. הוא לא רק שהצביע על, כפי שכמעט כל אחד אחר כאן. לכן, כאשר ראש הרשימה הוא הוסר, שידיו צריכים לשנות עכשיו? מה שמך שוב? קהל: כריסטין. דוד י מלאן: אני נורא בשמות, כנראה. אז כריסטין וגייב, ידיים שצריכים לשנות כאשר אנו מנסים להסיר את כריסטין, מספר 5, מהתמונה? אוקיי, אז בואו נעשה את גייב. גייב הולך להצביע, ככל הנראה, בבית המספר 9. אבל מה הלאה צריך לקרות? קהל: כריסטין צריך להיות null [לא ברור]. דוד י מלאן: בסדר, אנחנו כנראה צריכים make-- שמעתי "null" אי שם. קהל: Null וחופשי שלה. דוד י מלאן: null מה? קהל: Null וחופשי שלה. דוד י מלאן: ריק וחופשי שלה. אז זה קל מאוד. וזה מושלם כי אתה עכשיו סוג לעמוד שם, לא שייך. מכיוון שאתה כבר מנותק מהרשימה. היית יעיל התייתם מהרשימה. וכך היינו לנו טוב יותר להתקשר חינם עכשיו על כריסטין לתת הזיכרון הזה חזרה. אחרת כל פעם שאנחנו למחוק צומת מהרשימה אנחנו יכולים להיות מה שהופך את הרשימה קצר יותר, אבל לא ממש יורד הגודל בזיכרון. ולכן אם אנחנו שומרים על הוספה ו הוספה, הוספת דברים לרשימה, המחשב שלי יכול לקבל איטי יותר ולאט לאט, כי אני פועל מתוך זיכרון, גם אם אני לא ממש באמצעות הבתים של קריסטין זיכרון יותר. אז בסופו של הדבר יש אחרים תרחישים, של הסרת course-- ב, הסרת האמצע בסוף, כפי שראינו. אבל מעניין יותר אתגר כרגע הוא הולך להיות לשקול בדיוק מה הוא זמן הריצה. אז לא רק אתה יכול לשמור עליך פיסות נייר, אם, גייב, לא היית אכפת לו לתת כולם לחץ כדור. תודה רבה לך לרשימה המקושרת שלנו מתנדבים כאן, אם אתה יכול. [מחיאות כפות] דוד י מלאן: בסדר. אז כמה אנליטיים שאלות לאחר מכן, אם הייתי יכול. ראינו סימון זה לפני, O גדול ואומגה, גבול עליון וחסמים התחתונים על זמן ריצה של כמה אלגוריתם. אז בואו נשקול רק כמה שאלות. אחד, ואנחנו אמרו את זה לפני, מה הריצה זמן של חיפוש אחר רשימה במונחים של O הגדול? מה גבול עליון על הריצה זמן של חיפוש רשימה מקושרת כפי שהיא מתבצעת על ידי המתנדבים שלנו כאן? זה O הגדול של n, ליניארי. משום שבמקרה הגרוע ביותר, האלמנט, כמו 55, אנחנו יכולים להיות מחפשים עשויים להיות בי ג'ק היה, כל הדרך בסוף. ולמרבה הצער, בניגוד למערך אנו לא יכולים לקבל מפוארים זה זמן. למרות שכל בני האדם שלנו היו מסודרים מאלמנטים קטנים, 5, כל הדרך עד לאלמנט הגדול יותר, 55, זה בדרך כלל דבר טוב. אבל מה עושה הנחה ש כבר לא מאפשר לנו לעשות? קהל: [לא ברור] דוד י מלאן: תגיד את זה שוב? קהל: גישה אקראית. דוד י מלאן: גישה אקראית. וזה בתור זה אומר שאנחנו יכולים לא עוד להשתמש אפסים, אינטואיציה חלשה, ומובן מאליו של שימוש בינארי לחפש ופרד ומשול. כי למרות שאנחנו בני אדם כמובן יכולים רואה שאנדי או נוצרי היו בערך באמצע הרשימה, רק אנחנו יודעים שכ מחשב על ידי רפרוף ברשימה מההתחלה. אז אנחנו כבר ויתרנו כי גישה אקראית. O כל כך הגדול של n כרגע הוא עליון מחויב בזמן החיפוש שלנו. מה לגבי אומגה של החיפוש שלנו? מה גבול תחתון על חיפוש עבור חלק מספר ברשימה זו? קהל: [לא ברור] דוד י מלאן: תגיד את זה שוב? קהל: אחת. דוד י מלאן: אחת. אז בפעם קבועה. במקרה הטוב ביותר, כריסטין הוא אכן בתחילת הרשימה. ואנחנו מחפשים מספר 5, אז מצאנו אותה. אז לא ביג דיל. אבל היא חייבת להיות ב תחילתה של הרשימה במקרה זה. מה לגבי משהו כמו מחיקה? מה אם אתה רוצה למחוק את רכיב? מה הגבול העליון וגבול תחתון על מחיקת משהו ממקושר רשימה? קהל: [לא ברור] דוד י מלאן: תגיד את זה שוב? קהל: n. דוד י מלאן: n הוא אכן גבול העליון. משום שבמקרה הגרוע ביותר שאנו מנסים למחוק ג'ק, כמו שאנחנו פשוט עשינו. הוא כל הדרך בסוף. לוקח אותנו לנצח, או n צעדים כדי למצוא אותו. אז זה גבול עליון. זה ליניארי, בטוח. והמקרה הטוב ביותר זמן ריצה, או החסמים התחתונים במקרה הטוב יהיה זמן קבוע. כי אולי אנחנו מנסים למחוק כריסטין, ואנחנו רק מזל היא בתחילת. עכשיו חכה רגע. גייב היה גם בתחילת, והיה לנו גם לעדכן את גייב. כך שלא היה רק ​​צעד אחד. אז האם זה אכן קבוע זמן, במקרה הטוב, כדי להסיר את האלמנט הקטן ביותר? זה, למרות שזה יכול להיות שתי, שלוש, או אפילו 100 שורות קוד, אם זה אותו המספר של קווים, לא בחלק הלולאה, ובלתי תלוי בגודל של הרשימה, באופן מוחלט. מחיקת האלמנט ב תחילתה של הרשימה, גם אם אנחנו צריכים להתמודד עם גייב, עדיין זמן קבוע. אז זה נראה כמו צעד מאסיבי אחורה. ואיזה בזבוז של זמן אם, בשבוע אחד ובשבוע ש אפס שהיו לנו לא רק קוד pseudocode אבל קוד בפועל כדי ליישם משהו שהוא יומן n בסיס, או להתחבר, ולא, של n, בסיס 2, במונחים של זמן הריצה שלה. אז למה לעזאזל היינו רוצים להתחיל באמצעות משהו כמו רשימה מקושרת? כן. קהל: אז אתה יכול להוסיף אלמנטים למערך. דוד י מלאן: אז אתה יכול להוסיף אלמנטים למערך. וגם את זה הוא נושאיות. ואנחנו נמשיך לראות זה, זה trade-off, הרבה כמו שראינו trade-off עם סוג המיזוג. אנחנו באמת יכולים להאיץ את חיפוש או מיון, ולא, אם אנחנו מבלים מרחב קצת יותר ו יש לי נתח נוסף של זיכרון או מערך לסוג מיזוג. אבל אנחנו מבלים יותר חלל, אבל אנחנו לחסוך זמן. במקרה זה, אנחנו ויתור על זמן אבל אנחנו צובר גמישות, הדינמיות אם תרצה, שהוא ללא ספק תכונה חיובית. כמו כן, אנו מבלים בחלל. באיזה מובן הוא קשור רשימה יקרה יותר במונחים של שטח מאשר מערך? איפה השטח הנוסף מגיע? כן? קהל: [לא ברור] מצביע. דוד י מלאן: כן, אנחנו יש גם את המצביע. אז זה minorly מעצבן שבכבר לא אני אחסון רק int לייצג int. אני אחסון int ו מצביע, שהוא גם 32 סיביות. אז, פשוטו כמשמעו, אני מכפיל כמות השטח מעורבת. אז זה trade-off, אבל שהוא במקרה של int. נניח שאתה לא אחסון int, אבל מניח שכל אחד מהמלבנים האלה או כל אחד מבני האדם אלה מייצג מילה, מילה אנגלית ש יכול להיות חמישה תווים, 10 דמויות, אולי אפילו יותר. ואז מוסיף רק 32 יותר ביטים יכול להיות פחות מזה עניין גדול. מה אם כל אחד מהתלמידים בהפגנה היו, פשוטו כמשמעו, structs סטודנט ש יש שמות ובתים, ואולי מספרי טלפון וטוויטר מטפל וכדומה. אז כל השדות התחלנו מדבר על היום האחר, הרבה פחות מזה עניין גדול כ צמתים שלנו לקבל יותר מעניינים וגדול לבלות, אה, נוסף מצביע רק כדי לקשר אותם יחד. אבל אכן, זה trade-off. ואכן, הקוד הוא יותר מורכב, כפי שאתה לראות תוך מעבר דוגמא מסוימת ש. אבל מה יש אם היו כמה גביע קדוש כאן. מה אם אנחנו לא לוקחים צעד אחורה אבל צעד ענק קדימה וליישם נתונים מבנה שדרכו אנחנו ניתן למצוא אלמנטים כמו ג'ק או כריסטין או כל אלמנטים אחרים במערך זה בזמן קבוע אמיתי? חיפוש הוא קבוע. מחיקה היא קבועה. הכנס הוא קבוע. כל הפעולות הללו הם קבועים. זה יהיה הגביע הקדוש שלנו. וזה מקום שבו אנו יאסוף את הפעם הבאה. אז נתראה.