[Powered by Google Translate] [שבוע 6] [הדוד י מלאן] [אוניברסיטת הרווארד] [זה CS50.] [CS50.TV] 

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

אבל עכשיו, אם אנחנו הולכים לספרייה זו כאן ושים לב שיש לי conditions2.c- ואני מפעיל את הפקודה הזו החדשה, style50, על conditions2.c קובץ זה, זן, שם לב שהוא הודיע ​​לי שזה כבר מסוגנן. Gedit לב שהקובץ השתנה בדיסק, ואם אני לוחץ על לטעון מחדש, כל הבעיות שלך נמצאות כעת באופן אוטומטי. [מחיאות כפות] זה אחד מהדברים שעשינו בסוף השבוע הזה. להבין שזה לא מושלם, מפני שיש קוד כי זה פשוט לא יהיה מסוגל לסגנן בצורה מושלמת, אבל מבין שזה כרגע כלי שאתה יכול לנצל את היתרון של אם רק לחלק מלסדר את הפלטה מונח יותר errantly המסולסלת וכדומה. 

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

הבדיקות שברצונך להפעיל מזוהות באופן ייחודי על ידי מחרוזת זו, 2012/pset4/resize. במילים אחרות, זה פשוט מחרוזת שרירותית, אך ייחודית שאנו משתמשים כדי לזהות בדיקות תקינות של 4 pset. ואז אתה מציין רשימה מופרדת שטח של קבצים שאתה רוצה להעלות לCS50 הגעה לניתוח. לדוגמה, אם אני הולך לפתרון שלי כאן לresize.c- תן לי לפתוח את חלון מסוף גדול יותר, ואני ממשיך ולהפעיל אניח check50-ג 2012/pset4/resize, ואז אני הולך קדימה ולציין את שמות הקבצים, resize.c, ולאחר מכן על Enter, הוא דוחס, הוא מאפשר להעלות, הוא בודק, ואני פשוט לא הצלחתי חבורה שלמה של בדיקות. אחד באדום בפינה שמאלית עליונה אומר שresize.c וbmp קיים. זה היה המבחן. זו השאלה ששאלה. וזה עצוב, משום שהתשובה הייתה כוזבת. הטקסט הלבן מתחתיו אומר bmp.h צפוי להתקיים, וזה פשוט אשמתי. שכחתי להעלות אותה, ולכן אני צריך להעלות את שני קבצים, resize.c וbmp.h. אבל עכשיו שם לב כל בדיקות האחרות הנם בצבע צהוב בגלל שהם לא לרוץ, ואז פרצוף המחייך הוא אנכי כי הוא שמח ולא עצוב, אבל יש לנו לתקן בעיה שבאדום לפני בדיקות אחרות אלה תפעלנה. 

תן לי לתקן את זה. בואו להגדיל אותי וזה שידור חוזר, הפעם עם bmp.h גם בשורת הפקודה, זן, ועכשיו אם הכל ילך כשורה, זה הולך לבדוק ולאחר מכן להחזיר תוצאה, יחזיק אותך הנשימה כל ירוק, מה שאומר שאני עושה ממש טוב על pset 4 עד כה. אתה יכול לראות ולהסיק מטקסט התיאורים כאן בדיוק מה שזה בדקנו. בדקנו תחילה את הקבצים קיימים? אז בדקנו עושה לקמפל resize.c? אז בדקנו זה לא ישנה את גודל 1x1 BMP פיקסל כאשר n, גורם שינוי הגודל, הוא 1. עכשיו, אם אין לך מושג מה n הוא, אתה ברגע שאתה לצלול לתוך pset 4, אבל זה פשוט הוא שפיות לבדוק כדי לוודא שאתה לא שינוי גודל תמונה בכלל אם גורם שינוי הגודל הוא 1. אם, לעומת זאת, זה משנה את גודל 1x1 פיקסל לפיקסל BMP 1x1 ל2x2 כראוי כאשר n הוא 2, אז באופן דומה, שלי יוצר בהתאם. 

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

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

בלי שהיות, הבה נעבור למקום שבו הפסיק. CS50 ספרייה לקחנו כמובן מאליו במשך כמה שבועות, אבל אז בשבוע שעבר, התחילו לקלף אחת מהשכבות שלו. התחלנו לשים בצד מחרוזת לטובת מה במקום? [סטודנטים] צ'אר. * Char, אשר כבר דמות * כל הזמן הזה, אבל עכשיו אין לנו להעמיד פן שזה סוג מחרוזת נתונים בפועל. במקום זאת, הוא הייתה מילה נרדפת של מיני לדמות *, ומחרוזת היא רצף של תווים, אז מדוע זה הגיוני לייצג מחרוזות כchar * s? מה * char כן מייצג בהקשר של תפיסה זו של מחרוזת? כן. >> [סטודנטים] התו הראשון. טוב, התו הראשון, אבל לא ממש את התו הראשון. זהו אופן ש[ סטודנטים] כתובת. טוב, את הכתובת של התו הראשון. כל מה שהכרחי כדי לייצג מחרוזת בזיכרון של מחשב רק הכתובת הייחודית של הבתים הראשונים שלה. אתה אפילו לא צריך לדעת כמה זמן זה הוא כי איך אפשר להבין את זה באופן דינמי? [סטודנטים] אורך מחרוזת. אתה יכול לקרוא לאורך מחרוזת, מצוין, אבל איך זה עובד אורך מחרוזת? מה זה עושה? כן. [סטודנטים] תמשיך ללכת עד שתקבל את תו null. כן, בדיוק, זה פשוט סובב עם ללולאה, ואילו לולאה, מה * עד הסוף, והסוף מיוצג על ידי \ 0, דמות שנקראת NUL, NUL, לא להתבלבל עם אפס, אשר הוא מצביע, שעלה בשיחה שוב היום. 

אנחנו קלפנו שכבת GetInt, ואז לקחנו להסתכל GetString, וזוכר ששתי פונקציות אלה, או באמת, GetString, היה משתמש בפונקציה מסוימת למעשה לנתח, כלומר, לקרוא או לנתח, הקלט של המשתמש. וכי מה היה תפקידו החדש? Scanf או sscanf. זה באמת מגיע בכמה טעמים שונים. יש scanf, יש sscanf, יש fscanf. לעת עתה, אם כי, בואו נתמקד באחד מודגם בקלות הרבה ביותר, ותנו לי ללכת קדימה ולפתוח במכשיר קובץ כזה, scanf1.c. זוהי תכנית סופר פשוטה, אבל שעושה משהו שאנחנו אף פעם לא עשינו ללא עזרה של CS50 הספרייה. זה מקבל int ממשתמש. איך זה עובד? ובכן, ב 16 יש קו, שם לב שאנו מצהירים x נקרא int, ובשלב זה בסיפור, מהו הערך של x? [תגובת תלמיד לא נשמעה] [דוד מ '] נכון, מי יודע, איזה ערך זבל פוטנציאלי, ולכן ב17, אנחנו פשוט לספר את המשתמש תן לי מספר, בבקשה, וצעד 18 הוא מקום שבו מתחיל להיות מעניין. Scanf נראה ללוות רעיון מprintf בכך שהוא משתמש בפורמט הקודים האלה במרכאות. ד% הוא כמובן מספר עשרוני. אבל למה אני עובר ב& x במקום רק X? הראשון הוא נכון. כן. [תגובת תלמיד לא נשמעה] בדיוק, אם המטרה של התכנית הזו, כמו GetInt הפונקציה עצם, הוא להגיע int מהמשתמש אני יכול להעביר פונקציות כל המשתנים שאני רוצה, אבל אם אני לא אעבור אותם על ידי התייחסות או על ידי כתובת או על ידי מצביע, כל המילה נרדפת למטרות של היום, אז פונקציה שאין לו יכולת לשנות את התוכן של אותו משתנה. זה היה עובר בעותק בדיוק כמו את גרסת המרכבה של החלפה שאנחנו מדברים עליו כבר כמה פעמים. 

אבל במקום זה, על ידי עושה & x, אני ממש עובר במה? [סטודנטים] הכתובת. >> הכתובת של x. זה כמו ציור מפה לפונקציה שנקראת scanf ואומר כאן, אלה הם כיוונים לנתח של זיכרון במחשב כי אתה יכול ללכת לאחסן חלק שלם פנימה על מנת sscanf לעכשיו לעשות את זה מה מפעיל, מה קטע של תחביר זה הולך צריך להשתמש למרות שאנחנו לא יכולים לראות את זה בגלל שמישהו אחר כתב בפונקציה זו? במילים אחרות - מה זה? [סטודנטים] X לקרוא. יש הולך להיות קצת קריאה, אבל רק בנוגע לx כאן. אם scanf המועברת כתובת של x, מבחינה תחבירית, מה שמפעיל חייב להתקיים במקום כלשהו בתוך היישום של scanf כך שscanf בעצם יכול לכתוב את המספר 2 לאותה כתובת? כן, אז *. תזכיר כי * הוא מפעיל dereference שלנו, שבעצם אומר ללכת לשם. 

לאחר שנמסרת כתובת, כמו במקרה כאן, scanf הוא כנראה, אם אנחנו באמת הסתכלנו סביב מקורו הקוד עושה * x או שווה הערך בעצם ללכת לכתובת ולשים קצת ערך שם. עכשיו, כמו לכמה scanf מקבל קלט מהמקלדת, אנחנו מניפים את ידינו להווה. רק להניח כי מערכת ההפעלה מאפשרת sscanf לדבר למקלדת של המשתמש, אך בשלב זה עכשיו בקו 19, כאשר אנו פשוט להדפיס את x, נראה שזה המקרה שscanf יש לשים int ב x. זה בדיוק איך scanf עובד, ולהיזכר בשבוע שעבר זה בדיוק מה שGetString וGetInt ומשפחתה האחרת של פונקציות סופו של דבר עובד, אם כי עם שונות קלות כמו sscanf, מה שאומר לסרוק מחרוזת במקום מקלדת. אבל בואו נסתכל על שונות קטנות של זה. בscanf2, אני ממש דפוק. מה לא בסדר ואני להסתיר את ההערה שמסבירה עד כמה- מה לא בסדר עם תכנית זו, גרסה 2? להיות טכני ככל האפשר שלב זה. זה נראה די טוב. זה מסוכסך יפה, אבל- בסדר, מה איתי בואו לגזום אותו לשאלות קצרות יותר? קו 16. מה הקו 16 עושה באנגלית מדויקת אך טכנית? מקבל קצת מביך. כן, מיכאל. [סטודנטים] זה מצביע על המכתב הראשון בשרשרת. 

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

קו 18 הוא סוג של מכיר כעת בכך שרק עכשיו ראו את שונות של זה אבל עם קוד פורמט שונה, ולכן בקו 18, אנחנו מספרים scanf כאן היא הכתובת של נתח של זיכרון. אני רוצה שתצלצל במחרוזת, כפי שנרמז על ידי% s, אבל הבעיה היא שאנחנו לא עשינו כמה דברים כאן. מה אחת הבעיות? [סטודנטים] הוא מנסה dereference מצביע null. טובים, מצביעי null או סתם שאינו ידועים. אתה מוסר scanf כתובת, אבל אתה פשוט אמרת לפני רגע כתובת זו שהיא חלק ערך זבל בגלל שאנחנו לא ממש להקצות אותו לשום דבר, ואז אתה אומר לי scanf ביעילות הולך לשים מחרוזת כאן, אבל אנחנו לא יודעים איפה הוא עדיין כאן, אז אנחנו לא באמת נוקצה זיכרון לחיץ. יתר על כן, מה שאתה גם אפילו לא אומר לי scanf? תניח שזה היה נתח של זיכרון, וזה לא היה ערך זבל, אבל אתה עדיין לא אומר לי scanf משהו חשוב. [סטודנטים] איפה שזה באמת הוא, האמפרסנד. אמפרסנד, כך שבמקרה זה, זה בסדר. בגלל חיץ כבר הוכרז כמצביע עם החתיכה * בתחביר, אנחנו לא צריכים להשתמש אמפרסנד כי זה כבר כתובת, אבל אני חושב ששמעתי את זה כאן. [סטודנטים] איזה גודל הוא? טוב, אנחנו לא אומרים לscanf כמה גדול חיץ זה, מה שאומר שגם אם המאגר היה מצביע, אנחנו אומרים scanf, לשים מחרוזת כאן, אבל כאן יכול להיות 2 בתים, זה יכול להיות 10 בתים, זה יכול להיות מגה. Scanf אין לו מושג, ובגלל זה הוא נתח של זיכרון ככל הנראה, זה לא מחרוזת עדיין. זה רק מחרוזת ברגע שאתה כותב תווים ו\ 0 עד שהנתח של זיכרון. עכשיו זה רק חלק הנתח של זיכרון. Scanf לא יודע מתי להפסיק לכתוב לכתובת זו. 

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

הנה, אני אומר לי scanf הנה נתח של זיכרון. הפעם, זה בעצם נתח של זיכרון, אבל למה היא תכנית זו עדיין ניצול? מה לא בסדר עדיין? אני כבר אמרתי לי 16 בתים אבל- [סטודנטים] מה אם הם מקלידים יותר מ 16? בדיוק, מה אם המשתמש מקליד ב 17 תווים או תווים 1700? למעשה, בואו נראה אם ​​אנחנו לא יכולים למעוד על הטעות הזאת עכשיו. זה יותר טוב, אבל לא מושלם. תן לי ללכת קדימה ולרוץ לעשות scanf3 לקמפל תכנית זו. תן לי לרוץ scanf3, מחרוזת בבקשה: הלו, ונראים שאנחנו לא בסדר. תן לי לנסות קצת יותר ארוך אחד, שלום לך. אוקיי, בואו נעשה שלום יש מה שלומך היום, Enter. מקבל סוג של מזל, בואו נגיד שלום לשם השלום. לעזאזל. אוקיי, אז היינו לנו מזל. בואו נראה אם ​​אנחנו לא יכולים לתקן את זה. לא, זה לא הולך לתת לי להעתיק. בואו ננסה את זה שוב. בסדר, בכוננות. נצטרך לראות כמה זמן אני יכול להעמיד פן כדי להתמקד ועדיין עושה את זה. לעזאזל. זה לא מתאים, למעשה. הנה. נקודה שהועלה. 

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

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

[סטודנטים] איך זה שאתה לא צריך לשים את אמפרסנד ליד החלקי שאלה טובה. איך זה שאני לא צריך לשים אמפרסנד הבא למערך התווים כפי שעשיתי בעבר ברוב הדוגמות שלנו? התשובה הקצרה היא מערכים הם קצת מיוחדים. אתה כמעט יכול לחשוב חיץ כמו להיות ממש כתובת, וזה פשוט כל כך קורה להיות המקרה שתיווי סוגר המרובע היא נוחות, כך שנוכל להיכנס למסגרת 0, 1 משען סוגר 2, מבלי להשתמש בסימון *. זה קצת שקר לבן כי מערכים ומצביעים הם, למעשה, קצת שונים, אבל הם יכולים לעתים קרובות אך לא תמיד ניתן להשתמש לסירוגין. בקיצור, כאשר פונקציה מצפה מצביעה לנתח של זיכרון, אתה יכול להעביר אותו כתובת שהוחזרה ע"י malloc, ואנו רואים malloc שוב לפני זמן, או שאתה יכול להעביר אותו את שמו של מערך. אתה לא צריך לעשות אמפרסנד עם מערכים כי הם כבר בעצם רוצים כתובות. זה יוצא מן הכלל. הסוגריים המרובעים הופכים אותם מיוחדים. 

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

GetString היא דוגמה מושלמת. GetString, שנכתב על ידי בנו, אין לו מושג כמה תווים לצפות, לכן העובדה שאנחנו יכולים להקצות נתחי זיכרון רציף היא טובה. מערכים גם לפתור בעיה שראינו לפני כמה שבועות שם הקוד שלך מתחיל לרדת ברמה למשהו תוכנן בצורה גרועה מאוד. זוכר שיצרתי מבנה סטודנט בשם דוד, ולאחר מכן שלמרות שהיה למעשה אלטרנטיבה,, שיש שם משתנה בשם ומשתנים נוספים שנקרא, אני חושב, הבית, ועוד משתנים הנקרא תעודת זהות, כי בסיפור הזה אז אני רוצה להציג משהו אחר רוצה רוב לתכנית, אז אני החלטתי לחכות רגע, אני צריך לשנות את השם משתנה אלה. בואו נקראים name1, ID1, house1. בואו לקרוא רוב של name2, house2, ID2. אבל אז רגע, מה עם טומי? ואז היו לנו עוד שלושה משתנים. אנחנו הצגנו מישהו אחר, ארבעה סטים של משתנים. העולם התחיל להיות מלוכלך מהר מאוד, כך הצגנו structs, ומה משכנע על struct? מה struct C לא ייתן לך לעשות? זה ממש מוזר היום. מה? >> [תגובת תלמיד לא נשמעה] כן, באופן ספציפי, typedef מאפשר לך ליצור סוג נתונים חדש, וstruct, מילת מפתח struct, מאפשר לך לתמצת יצירות הקשורות מושגית של נתונים יחד ולאחר מכן קורא להם משהו כמו סטודנט. 

זה היה טוב, כי עכשיו אנחנו יכולים מודל מין הרבה יותר מבחינה רעיונית העקבי הרעיון של תלמיד במשתנה ולא באופן שרירותי שיש אחד למחרוזת, אחד לזיהוי, וכן הלאה. מערכים הם נחמדים, כי הם מאפשרים לנו להתחיל לנקות את הקוד שלנו. אבל מה הוא חסרון כרגע של מערך? מה אתה לא יכול לעשות? כן. [סטודנטים] אתה צריך לדעת כמה הוא גדול. אתה צריך לדעת כמה הוא גדול, כך שזה סוג של כאב. עם ניסיון בתכנות מוקדם אלה מכם שיודעים בהרבה שפות, כמו Java, אתה יכול לשאול את נתח של זיכרון, ובמיוחד מערך, כמה אתה גדול, עם אורך, רכוש, אם אפשר לומר כך, וזה ממש נוח. ב-C, אתה אפילו לא יכול לקרוא strlen על מערך גנרי בגלל strlen, כמשמעות המילה היא רק עבור מחרוזות, ואתה יכול להבין את האורך של מחרוזת בגלל המוסכמות האנושיות הזה שיש \ 0, אך מערך, יותר הגנרי, הוא פשוט גוש של זיכרון. אם זה מערך של ints, שם לא הולך להיות דמות מיוחדת בסוף מחכה לך. צריך לזכור את האורך של מערך. חסרון נוסף של מערך הרים את ראשה בGetString עצמו. מה חסרון נוסף של מערך? אדונים, רק אתה ואני היום. [תגובת תלמיד לא נשמעה] >> זה מה? זה הכריז במחסנית. אוקיי, הכריז על הערימה. למה אתה לא אוהב את זה? [סטודנטים] כי היא מקבלת בשימוש חוזר. זה נעשה שימוש חוזר. אוקיי, אם אתה משתמש במערך כדי להקצות זיכרון, אתה לא יכול, למשל, להחזיר אותו כי זה בערימה. אוקיי, זה חסרון. ומה דעתך על אחד אחר עם מערך? ברגע שאתה מקצה לו, את הסוג של נדפק אם אתה צריך יותר מקום מהמערך שיש. 

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

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

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

בדיוק כמו עם מחרוזת, אתה צריך לדעת את הכתובת של הדמות הראשונה. עסקה זהה לרשימות מקושרות. אתה צריך לדעת את הכתובת של הגוש הראשון של זיכרון כי משם, אתה יכול להגיע לכל אחד אחר. חסרון. מה מחיר שאנחנו משלמים על זה שיש צדדי באופן דינמי מבנה נתונים גדול למדי, שאם אי פעם נצטרך יותר זיכרון, בסדר, רק להקצות יותר חתיכה אחת ולהסיק ממצביע הישן לזנב החדש של הרשימה? כן. [סטודנטים] זה לוקח בערך כפליים חלל. זה לוקח פי שניים משטח, כך שזה בהחלט חסרון, ואנחנו ראינו את זה איזון בין לפני הזמן ובמרחב וגמישות שם עד עכשיו, אנחנו לא צריכים 32 סיביים לכל אחד מהמספרים האלה. אנחנו באמת צריכים 64, 32 למספר 32 ולמצביע. אבל היי, יש לי 2 ג'יגה בייט של זכרון RAM. הוספת 32 ביטים עוד כאן וכאן לא נראית כל כך גדולה של עסקה. אבל עבור ערכות נתונים גדולות, זה בהחלט מוסיף עד ממש כפליים. מה חסרון נוסף עכשיו, או מה תכונה שאנחנו מוותרים, אם אנחנו מייצגים רשימות של דברים עם רשימה מקושרת ולא במערך? [סטודנטים] אתה לא יכול לעבור אותו לאחור. אתה לא יכול לעבור אותו לאחור, כך שאת די דפוקה אם אתה הולך משמאל לימין באמצעות לולאה או ללולאה בזמן ואז אתה מבין, "הו, אני רוצה לחזור לתחילת הרשימה." אתה לא יכול כי המצביעים האלה ללכת רק משמאל לימין כחצים מצביעים. 

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

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

שוב, אנחנו לא פתרון כל הבעיות שלנו. אנחנו מציגים חדשים, אבל זה באמת תלוי במה שאתה מנסה לתכנן ל. במונחים של יישום זה, אנחנו יכולים ללוות מרעיון שמבנה התלמיד. התחביר מאוד דומה, אלא שעכשיו, הרעיון הוא קצת יותר מופשט מבית ושם ותעודת זהות. אבל אני מציע שיהיה לנו מבנה נתונים ב-C שנקרא צומת, כמילה האחרונה בשקופית מרמזת, בתוך צומת, וצומת היא רק מכל הגנרית במדעי מחשב. בדרך כלל זה נמשך כעיגול או ריבוע או מלבן כפי שעשינו. ובמבנה נתונים זה, יש לנו int, n, אז זה המספר שאני רוצה לאחסן. אבל מה הוא הקו הזה השני, struct * צומת הבאה? למה זה נכון, או מה תפקיד הדבר הזה, למרות שזה לא ברור מספיק במבט הראשון? כן. [תגובת תלמיד לא נשמעה] בדיוק, ולכן הסוג * של שלל שזה מצביע מסוג כלשהו. שמו של מצביע זה הוא שרירותי הבא, אבל אנחנו יכולים לקרוא לה שום דבר שאנחנו רוצים, אבל מה זה נקודת מצביע זה? [סטודנטים] צומת נוספת. >> בדיוק, הוא מצביע על צומת כזו אחרת. 

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

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

C היא הרבה יותר כיף כשזה ימומש. מי ממש רוצה להיות ראשון? אוקיי, בואו ניכנס. אתה ראשון. מי רוצה להיות 9? אוקיי, 9. מה דעתך על 9? 17? קליקה קטנה כאן. 22 ו 26 שבשורה ראשונה. ואז מה עם מישהו שם שמכוון אליי. אתה 34. אוקיי, בן 34, יעלה למעלה. הראשון היא שם. אוקיי, כל ארבעה החבר 'ה. ומי שלא אומרים ל9? מי הם 9? מי שבאמת רוצה להיות 9? בסדר, בואו, יהיו 9. הנה אנחנו מתחילים. 34, שנפגוש אותך שם. החלק הראשון הוא להפוך את עצמכם להיראות ככה. 26, 22, 17, טובים. אם אתה יכול לעמוד בצד, כי אנחנו הולכים malloc ברגע. 

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

עכשיו התמונה האנושית שלנו היא מאוד עקבית. זהו למעשה כמה מצביעי עבודה. ואם אתה יכול לכווץ קצת בדרך זו ולכן אני לא בדרך שלך. אניטה כאן, תמצא לי את המספר 22, אבל תניח אילוץ של בני אדם לא מחזיקים את פיסות נייר, אבל זו רשימה, ויש לך רק לוקאס מלכתחילה משום שהוא, פשוטו כמשמעו, את המצביע הראשון. תניח שאתה בעצמך הוא מצביע, ואז יש לך את היכולת להצביע על משהו יותר מדי. למה שלא תתחיל בהצבעה על לוקאס בדיוק מה הוא מצביע? טוב, ולתת לחוקקי את זה כאן. רק לצורך הדיון, בואו תמשכו אותי דף ריק כאן. איך מאיית את השם שלך? >> אניטה. אוקיי, אניטה. נניח צומת * אניטה = לוקאס. ובכן, אנחנו לא צריכים לקרוא לך לוקאס. אנחנו צריכים לקרוא לך ראשונים. למה זה בעצם עולה בקנה אחד עם מציאות כאן? אחד, ראשון שכבר קיים. הראשון הוקצה כנראה איפשהו כאן למעלה. * הצומת ראשונה, וזה הוקצה רשימה איכשהו. אני לא יודע איך זה קרה. זה קרה לפני השיעור התחיל. רשימה מקושרת זה של בני אדם נוצרה. ועכשיו, בשלב זה בסיפור, כל זה הולך בפייסבוק ככל הנראה מאוחר יותר בנקודה זו בסיפור, אניטה אותחלה להיות שווה לראשון, מה שלא אומר שנקודתי אניטה בלוקאס. במקום זאת, היא מצביעה על מה שהוא מצביע על בגלל אותה כתובת שיש בפנים של 32 הסיביים של לוקאס - 1, 2, 3 - עכשיו גם חלק פנימי של 32 הסיביים של אניטה - 1, 2, 3. 

עכשיו למצוא 22. איך היית הולך על עושה את זה? מה זה נקודה? >> לכל דבר. להצביע על מה, אז קדימה, ולפעול את זה כמיטב היכולת לכאן. טוב, טוב, ועכשיו אתה מצביע, מה שמך עם 22? רמון. >> רמון, אז רמון הוא מחזיק עד 22. עכשיו יש לך לעשות בדיקה. האם רמון == 22, ואם כן, למשל, אנחנו יכולים לחזור אמיתיים. תן לי, בעוד החבר 'ה האלה עומדים כאן מעט מגושם- תן לי לעשות משהו במהירות כמו bool למצוא. אני הולך קדימה, ואומר (צומת * רשימה, int n). אני כבר חוזר איתכם. אני רק צריך לכתוב קצת קוד. ועכשיו אני הולך ללכת ולעשות, צומת * אניטה = רשימה זו. ואני הולך קדימה, ואומר אילו (אניטה! = NULL). 

המטאפורה כאן היא מקבלת קצת מתוחה, אבל בזמן (אניטה! = NULL), מה שאני רוצה לעשות? אני זקוק לדרך ההתייחסות השלם שאניטה היא מצביעה. בעבר, כאשר היו לנו מבנים, שצומת היא, השתמשנו בסימון הנקודה, ואנחנו היו אומרים משהו כמו anita.n, אבל הבעיה כאן היא שאניטה היא לא struct כשלעצמה. מה הוא? היא מצביעה, אז באמת, אם אנחנו רוצים להשתמש בנקודה זו סימון- וזה הולך להיראות בכוונה לא ברור מספיק, אנחנו צריכים לעשות משהו כמו ללכת יד השמאל של אניטה מה הוא מצביע ולאחר מכן לקבל את השדה שנקרא n. אניטה היא מצביע, אבל מה היא * אניטה? מה אתה מוצא כשאתה הולך למה שאניטה היא מצביעה? Struct, צומת וצומת, כזכור, יש שדה שנקרא n משום שהוא, כזכור, 2 תחומים אלה, הבאים וn, שראינו לפני רגע ממש כאן. 

למעשה לחקות זה בקוד, אנחנו יכולים לעשות את זה ואומרים שאם ((* anita). n == n), n שאני מחפש. שים לב כי הפונקציה עברה במספר שאכפת לי. אז אני יכול ללכת ולעשות משהו כמו תשואה אמיתית. אחר, אם זה לא מקרה, מה שאני רוצה לעשות? כיצד ניתן לתרגם לקוד מה אניטה עשתה זאת באופן אינטואיטיבי על ידי הליכה ברשימה? מה אני צריך לעשות כאן כדי לדמות אניטה צעד שלשמאל, צעד שלשמאל? [תגובת תלמיד לא נשמע] >> מה זה? [תגובת תלמיד לא נשמעה] טוב, רעיון לא רע, אבל בעבר, כשעשינו את זה, עשה אניטה + + משום שהייתי מוסיף מספר 1 לאניטה, אשר בדרך כלל מצביע על האדם הבא, כמו רמון, או האדם שיושב לידו, או לידו אדם לאורך הקו. אבל זה לא ממש טוב כאן משום מה הדבר הזה נראה כמו בזיכרון? לא זה. אנחנו צריכים לבטל את זה. זה נראה כאילו זה בזיכרון, ולמרות שאני נמשך 1 ו 2 ו 3 קרוב אחד לשני, אם אנחנו באמת לדמות הזאת-אתם יכולים, ועדיין מצביעים על אותם האנשים, כמה מכם יכול לקחת צעד אחורה אקראי, כמה מכם צעד קדימה אקראי? 

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

מאחורי הקלעים, הייתי לפתור את הבעיה בדרך זו. אניטה, לקחת צעד לשמאל, ראשון, אנחנו הולכים לכתובת שאניטה היא מצביעה ושם היא תמצא את n, שאנו פשוט בדקנו לשם השוואה, לא רק אבל אתה גם מוצא בא - במקרה זה, יד השמאל של רמון מצביעה לצומת הבאה ברשימה. אבל זה בלגן הנורא והאיום שאליו התייחסתי קודם לכן, אבל מסתבר C מאפשרת לנו לפשט את זה. במקום כתיבה (* anita), אנחנו יכולים פשוט במקום לכתוב אניטה-> n, וזה בדיוק אותו דבר פונקציונלי, אבל זה הרבה יותר אינטואיטיבי, וזה הרבה יותר בקנה אחד עם התמונה שאנו מציירים כל הזמן הזה באמצעות חיצים. 

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

עכשיו בואו ננסה עוד אחד. אניטה, אתה רוצה לחזור לכאן? למה שלא להמשיך ולהקצות אדם אחר אחד מהקהל? Malloc-מה השם שלך? >> רבקה. רבקה. רבקה כבר malloced מהקהל, והיא כעת אחסון המספר 55. והמטרה בהישג יד כרגע היא לאניטה להכניס רבקה לרשימה המקושרת כאן במקום הראוי לו. בואו הנה לרגע. אני עשיתי משהו כזה. עשיתי * צומת. ואיך קורא לך שוב? רבקה. >> רבקה, בסדר. רבקה מקבלת malloc (sizeof (צומת)). בדיוק כמו שאנו הקצינו דברים כמו סטודנטים ומה לא בעבר, אנחנו צריכים את הגודל של הצומת, כך שעכשיו רבקה הוא מצביע על מה? רבקה יש שני תחומים בתוכה, אחד מהם הם 55. בואו נעשה מה, רבקה-> = 55. אבל אז רבקה-> הבא צריך להיות-כמו עכשיו, ידה היא סוג של מי יודע? זה מצביע על איזה ערך זבל, אז למה לא למען הסדר טוב אנחנו לפחות עושים זאת כדי שיד שמאל היא עכשיו בצד שלה. עכשיו אניטה, קח אותו מכאן. יש לך רבקה שהוקצתה. קדימה ולמצוא בו אנחנו צריכים לשים את רבקה. טוב, טוב מאוד. אוקיי, טוב, ועכשיו אנחנו צריכים אותך כדי לספק קצת כיוון, כך שהגעת לארי. בידו השמאלי הוא אפס, אבל רבקה שייכת בבירור לימין, אז איך אנחנו צריכים לשנות את הרשימה מקושרת זה כדי להכניס את רבקה למקום המתאים? אם אתה ממש יכולת להזיז את הידות השמאליות של אנשים מסביב לפי צורך, אנחנו נסדר את הבעיה בדרך זו. אוקיי, טוב, ובינתיים, יד השמאל של רבקה היא עכשיו על הצד שלה. 

זה היה קל מדי. בואו ננסה הקצאה-אנחנו כבר כמעט סיימנו, 20. אוקיי, בואו ניכנס. 20 הוקצו, אז תן לי ללכת קדימה ואומרים שוב כאן פשוט עשינו סעד * צומת. יש לנו malloc (sizeof (צומת)). אז אנחנו עושים אותו התחביר המדויק כפי שעשינו קודם ל20, ואני אעשה = NULL הבא, ועכשיו זה תלוי בי אניטה כדי להכניס אותך לרשימה המקושרת, אם אתה יכול לשחק באותו תפקיד בדיוק. ביצוע. בסדר, טוב. עכשיו תחשוב היטב לפני שתתחיל להזיז את הידות שמאליות בסביבה. אתה ללא ספק קבלת את התפקיד המביך ביותר כיום. ידו של מי צריך להיות הראשון שזז? אוקיי, הרגע, אני שומע כמה לא של. אם כמה אנשים בנימוס ברצון לעזור לפתור מצב מביך כאן. יד שמאל שצריך להיות מעודכנת, אולי לראשונה? כן. [סטודנטים] סעד של. אוקיי, סעד של, למה, בעצם? [תגובת תלמיד לא נשמעה] טוב, כי אם תעברו, מה שמך? >> מרשל. מרשל, שאם תזיז את ידו הראשונה למטה לnull, עכשיו יש לנו ארבעה אנשים, פשוטו כמשמעו, התייתמו ברשימה זו כי הוא היה הדבר היחיד שמצביע על רמון וכולם לשמאל, כך מעדכן כי המצביע ראשון היה רע. הבה תתיר את זה. טוב, ועכשיו קדימה ולהזיז את יד השמאל המתאימה מצביעה על רמון. זה מרגיש קצת מיותר. עכשיו יש שני אנשים מצביעים על רמון, אבל זה בסדר כי עכשיו איך עוד אנחנו לעדכן את הרשימה? מה מצד שני יש לעבור? מצוין, עכשיו יש לנו אבדתי כל זיכרון? לא, כל כך טוב, בואו נראה אם ​​אנחנו לא יכולים לעבור את זה פעם נוספת. 

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

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

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

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

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

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

אבל יניח שעכשיו אני הולך קדימה ולהכניס משהו לתוך המחסנית. אני רוצה להכניס את המספר 5, אז שמתי מספר 5 כאן, ואז מה ישים כאן למטה? עכשיו אני ממש לא הנחתי 1 עבור הגודל, ועכשיו היא בגודל הערימה 1. מה אם אני הולך קדימה ולהכניס את המספר, יניח, ליד 7? אז זה מתעדכן ל 2, ואז אנחנו נעשה 9, ואז זה מתעדכן ל 3. אבל התכונה המעניינת עכשיו ערימה של זה היא כי אני אמור להסיר את האלמנט שאם אני רוצה לקפוץ משהו מהערימה, כביכול? 9 יהיו הדבר הראשון ללכת. איך התמונה צריכה להשתנות אם אני רוצה לפוצץ את אלמנט המחסנית, הרבה אוהב את מגש למאת'ר? כן. >> [סטודנטים] גודל מוגדר 2. בדיוק, כל מה שאני עושה הוא להגדיר גודל 2, ומה עליי לעשות עם המערך? אני לא צריך לעשות שום דבר. אני יכול, רק כדי להיות אנאלי, לשים 0 שם או -1 או משהו שיעיד כי זה לא ערך חוקי, אבל זה לא משנה כי אני יכול להקליט מחוץ למערך עצמו כמה זמן הוא כך שאני יודע שמסתכל רק על שני המרכיבים הראשונים במערך הזה. עכשיו, אם אני הולך ולהוסיף את המספר 8 למערך זה, איך לשנות את התמונה הבאה? זה הופך להיות 8, וזה הופך להיות 3. אני חותך כמה פינות כאן. עכשיו יש לנו 5, 7, 8, ואנחנו שוב לגודל של 3. זה די פשוט לביצוע, אבל כאשר אנחנו הולכים להתחרט על החלטת העיצוב הזה? כאשר הדברים מתחילים ללכת מאוד מאוד לא בסדר? כן. [תגובת תלמיד לא נשמעה] כשאתה רוצה לחזור ולקבל את האלמנט הראשון שהכנסת פנימה 

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

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

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

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

ואכן, במבט קדימה, אחד מpsets בכיתה זו היא כמעט תמיד ביצוע בדיקת איות, לפיו אנחנו נותנים לך שוב כמה מילים באנגלית 150.000 והמטרה היא אלה לטעון לזיכרון ומהירות להיות מסוגל לענות על שאלות בטופס היא מילה זו מאויתת בצורה נכונה? וזה באמת היה שואב אם היית צריך לחזר דרך כל 150.000 המילים לענות על זה. אבל, למעשה, נראה שאנחנו יכולים לעשות את זה בזמן מאוד, מאוד מהיר. וזה הולך לערב משהו יישום נקרא שולחן חשיש, ואף על פי שבמבט הראשון הדבר הזה שנקרא שולחן חשיש הולך תנו לנו להשיג זמני התגובה המהירים אלה סופר, מתברר שיש למעשה בעיה. כשזה מגיע זמן ליישם הדבר הזה שנקרא, שוב, אני עושה את זה שוב. אני היחיד כאן. כשזה מגיע זמן ליישום הדבר הזה שנקרא שולחן חשיש, אנחנו הולכים לעשות כדי להפוך את החלטה. כמה גדול צריך להיות הדבר הזה בעצם? כאשר אנו מתחילים מספרי החדרה לתוך שולחן חשיש וזה, איך אנחנו הולכים לאחסן אותם באופן כזה שאנחנו יכולים לקבל אותם בחזרה החוצה מהר ככל שיש לנו אותם? אבל אנחנו רואים לפני זמן רב ששאלה זו של מתי יום ההולדת של כולם היא בכיתה יהיה די רלוונטי. מתברר כי בחדר הזה, יש לנו כמה מאה אנשים, כך הסיכויים ששנינו יש לו יום ההולדת היא כנראה די גבוהה. מה אם היו רק 40 מאיתנו בחדר הזה? מה הסיכויים של שני אנשים שיש אותו יום הולדת? [סטודנטים] מעל 50%. כן, מעל 50%. למעשה, אני אפילו הבאתי תרשים. מתברר, וזה באמת רק תצוגה מקדימה להתגנב- אם יש רק 58 מאיתנו בחדר הזה, את ההסתברות של 2 מתוכנו נתקל באותה יום ההולדת הוא עצום גבוה, כמעט 100%, וזה הולך לגרום לכל חבורה של כאב בשבילנו ביום רביעי. 

עם זאת אמרה, בואו לדחות כאן. ניראה אותך ביום רביעי. [מחיאות כפות] [CS50.TV]