[השמעת מוסיקה] 

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

-הוא משקר. 

-לגבי מה? 

-אני לא יודע. 

-אז מה אנחנו יודעים? 

חייהם." בשעת 9:15, ריי Santoya היה בכספומט. 'כן. אז השאלה היא, מה הוא עשה בשעת 9:16? 

-Shooting המילימטר 9 במשהו. אולי הוא ראה את הצלף. 

-או עבד איתו. 

לחכות. חזור אחד. 

-מה אתה רואה? 

-Bring את פניו במסך מלא. 

משקפיו התיזו. 

"מצאתי השתקפות. 

"זאת קבוצת בייסבול Nuevitas. זה הלוגו שלהם. 

-ואז הוא מדבר ל מי שלובש מעיל ש. 

[סוף ההשמעה] 

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

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

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

קהל: כמה? DAVID מלאן: כמה? כמה בבתים, וכך, זה, שוב, דוגמא מאולצת, היא רק אומרת, תן לי את הגודל של int. עכשיו, בגודל של int הוא ארבעה בתים או 32 סיביות. אז זה רק דרך אומר, היי, מערכת הפעלה, תן לי ארבעה בתים של זיכרון שאני יכול להשתמש שברשותי, ובאופן ספציפי, מה עושה תמורת malloc בכבוד לנתח של ארבעה בתים? קהל: כתובת? DAVID מלאן: כתובת. הכתובת של נתח זה של ארבעה בתים. בדיוק. ואז זה מה שהוא מאוחסן סופו של דבר בx ולכן אנחנו לא באמת אכפת לי מה מספר ש כתובת היא, בין אם זה ox1 או OX2 או כמה כתובת הקסדצימלי נסתרות. רק אכפת לנו ציורי שx משתנה הוא עכשיו מצביע על נתח זה של זיכרון. אז החץ מייצג מצביע, או באופן יותר ספציפי, כתובת זיכרון. אבל שוב, לא אכפת לנו בדרך כלל מה הן כתובות בפועל אלה. עכשיו, קו זה אומר מה במונחים של ההדיוט? x כוכבים מקבל 42 פסיק. מה זה אומר? אתה רוצה ללכת? לא לגרד את הצוואר שלך. 

קהל: הכתובת של x היא ב42. 

DAVID מלאן: הכתובת של x היא על 42. לא בדיוק. כל כך קרוב, אבל לא ממש, כי אין הכוכב זה קידומת X זה. אז אנחנו צריכים לצבוט קצת. כן? 

קהל: הערך ש x המצביע מצביע להם 42. DAVID מלאן: אישור. הערך שx המצביע הוא מצביע על, נניח, יהיה 42, או במילים אחרת, את הכוכב x אומר, ללכת לכל כתובת הוא בx, בין אם זה 1 אוקספורד רחוב אוקספורד סטריט או 33 או ox1 או ox33, מה ש שכתובת מספרית היא, x הכוכב הוא ביטול ההפניה של x. אז ללכת לכתובת זו ו ואז לשים את המספר 42 שם. כך שיהיה דרך שווה ערך לומר ש. אז זה בסדר גמור ולאחר מכן היינו מייצג את התמונה כדלקמן בי הוספנו 42 לנתח של ארבעה ביטים בצד ימין, אבל הקו הזה היה בו דברים השתבשו וראשו של הינקי צץ את בשלב זה, כי דברים רעים קורים כש אתה dereference ערכי זבל או שאתה dereference לא חוקי מצביעים, ואני אומר לא חוקי כי בשלב זה ב סיפור, מה יש בתוכו של y? מה הערך של y מבוסס בכמה הצעדים האחרונים? כן? מה זה? 

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

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

וכך ציורי, יש לנו ייצגתי את זה עם שני חיצים מx ומהצבעת y לאותו המקום. אז מבחינה סמנטית, x הוא שווה לy כי שני אלה מאחסנים אותו כתובת, ergo מצביע על 42, ועכשיו, כשאתה אומר כוכב y, ללכת לכתובת בy, זה יש תופעת לוואי מעניין. אז הכתובת בy היא אותו דבר כמו הכתובת בx. אז אם אתה אומר ללכת לכתובת בy ולשנות את הערך ל -13, מי עוד נפגע? X הוא, נקודת D, כביכול, צריך להיות מושפע גם כן. 

ואכן, איך ניק משך תמונה זו באולפן היה בדיוק את זה. למרות שאנחנו בצענו את המצביע y, בסופו שלנו באותו המקום, ולכן אם היינו להדפיס את x או y pointee של, אז היינו רואה את הערך של 13. עכשיו, אני אומר pointee להיות עולה בקנה אחד עם הווידאו. מתכנתים, לשלי ידע, אף פעם לא באמת לומר את המילה pointee, שבו הוא מחודד ב, אבל לעקביות עם הווידאו, מבין זה כל מה שהיה התכוון במצב זה. אז שאלות על אולפן או מצביעים או malloc עדיין? לא? בסדר. 

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

אז זה תכנית בשם scanf 0. זה סופר קצר. זה פשוט יש שורות אלה, אבל זה מציג scanf פונקציה שנקראת שאנחנו בעצם הולכים לראות ב רגע הפנימי של ספריית CS50, אם כי בצורה מעט שונה. אז בתכנית זו בקו 16 מכריז x משתנה. אז תן לי ארבעה בתים לint. זה כבר אומר למשתמש, מספר בבקשה, ולאחר מכן זה קו מעניין ש קושר יחד למעשה בשבוע שעבר וזה. Scanf, ולאחר מכן שמו לב שלוקח מחרוזת פורמט, בדיוק כמו printf, אני אומר% int, ואז זה לוקח טיעון שני שנראה קצת פאנקי. זה x אמפרסנד, ולהיזכר, רק שראינו פעם בשבוע האחרון. מה x האמפרסנד אין מייצג? מה אמפרסנד עושה בC? כן? 

קהל: כתובת. DAVID מלאן: כתובת. אז זה ההפך של מפעיל הכוכב, ואילו מפעיל הכוכב אומר, ללכת ל כתובת זו, מפעיל האמפרסנד אומר, להבין את כתובת של משתנה זה, ואז זה מפתח, משום ש המטרה של scanf בחיים הוא לסרוק את המשתמש של קלט מהמקלדת, בהתאם לכל מה שהוא או היא סוגים, ולאחר מכן לקרוא קלט של המשתמש ש למשתנה, אבל אנחנו ראה בשבועות האחרונים שפונקצית ההחלפה ש ניסיתי ללא מאמץ ליישם רק נשבר. נזכיר כי עם פונקצית swap, אם אנחנו רק הכריזו A ו- B כints, אנו לא בהצלחה להחליף שני משתנים פנימיים של החלפה בדיוק כמו עם חלב וג'יי, אבל ברגע שההחלפה חזרו, מה הייתה התוצאה עם כבוד לx ו- y, הערכים המקוריים? לא כלום. כן. שום דבר לא קרה שזמן, משום ש חילופים לשנות רק עותקים המקומיים שלה, כלומר, כל הפעם, בכל פעם שיש לנו כבר עובר בטיעונים לפונקציות, אנחנו רק עובר עותקים של טענות אלה. אתה יכול לעשות עם זה מה שאתה רוצה איתם, אבל הם הולכים אין לי השפעה על הערכים המקוריים. אז זה בעייתי אם אתה רוצה להיות פונקציה כמו scanf בחיים, שמטרתה לסרוק הקלט של המשתמש מהמקלדת ולאחר מכן למלא את החסר, ולכן ל לדבר, כלומר, לתת משתנה כמו x ערך, משום שאם היינו רק כדי לעבור x לscanf, אם אתה מחשיב את ההיגיון של אחרון שבוע, scanf יכול לעשות מה שהיא רוצה עם עותק של x, אבל זה לא יכול לשנות לצמיתות x אלא אם כן אנחנו נותנים scanf מפת אוצר, כביכול, כאשר x מסמן את המקום, שבו אנחנו עוברים בכתובת של x, כך ש scanf יכול ללכת לשם ולמעשה שינוי הערך של x. וכך אכן, כל כי תכנית זו עושה אם אני עושה scanf 0, במקור שלי ספריית 5M, לעשות scanf 0, מספר הנקודה לקצץ scanf, בבקשה 50, תודה על 50. 

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

בואו נסתכל על גרסה זו כעת זה הניסיון שלי reimplement GetString. אם scanf יש את כל זה פונקציונלי מובנה, מדוע יש לנו הייתי מתעסק עם אלה גלגלים כמו GetString אימון? ובכן, כאן הוא אולי שלי גרסה פשוטה של ​​GetString לפי לפני שבוע, אולי הייתי אומר, תן לי מחרוזת וקורא לזה חיץ. היום, אני הולך להתחיל רק אומר כוכב char, אשר, כזכור, זה רק מילים נרדפים. זה נראה מפחיד אבל זה את אותו הדבר בדיוק. אז תן לי חיץ משתנה בשם זה הולך לאחסן מחרוזת, לספר מחרוזת המשתמשים בבקשה, ואז, בדיוק כמו לפני, בואו ננסה לשאול את הלקח הזה scanf % S הפעם ולאחר מכן לעבור במאגר. עכשיו, לבדוק את שפיות מהירה. למה אני לא אומר אמפרסנד חיץ הפעם? להסיק מהדוגמא הקודמת. קהל: כוכב תו הוא מצביע. DAVID מלאן: בדיוק, כי הזמן, char זה כוכב הוא כבר מצביע, כתובת, על ידי הגדרה של להיות שם כוכב ש. ואם scanf מצפה כתובת, די פשוט לעבור במאגר. אני לא צריך לומר חיץ אמפרסנד. לסקרן, אתה יכול לעשות משהו כזה. תהיה לו משמעות שונה. זה ייתן לך מצביע למצביע, שהוא למעשה דבר תקף ב- C, אבל ל עכשיו, בואו נשמור את זה פשוט ולשמור את הסיפור בקנה אחד. אני רק הולך לעבור ב חיץ וזה נכון. הבעיה למרות שזה. תן לי ללכת קדימה ולהפעיל את זה תכנית לאחר עריכתו. הפוך scanf 1. לעזאזל, מהדר שלי של המושך את השגיאה שלי. תן לי שנייה אחת. צלצול. נניח scanf-1.c. אוקיי. יש לנו ללכת. אני צריך את זה. יש מספר CS50 שונים הגדרות תצורה שלהגן עליך מפני עצמך. אני צריך להשבית אלה על ידי פועל צלצול ידני הפעם. אז מחרוזת בבקשה. אני הולך קדימה והקלד בעולם שלום האהוב עליי. אישור, null. זה לא מה שהקלדתי. אז זה מעיד על משהו לא בסדר להיות. תן לי ללכת קדימה והקלידו במחרוזת ארוכה באמת. תודה על null ואני לא יודע אם אני הולך להיות מסוגל לקרוס זה. בואו ננסה עותק קטן להדביק ולראות אם זה עוזר. רק להדביק את זה הרבה. זה בהחלט גדול יותר מחרוזת מהרגיל. בואו פשוט באמת לכתוב אותו. מס ' לעזאזל. פקודה לא נמצא. אז זה לא קשור. זה בגלל שאני הודבק כמה דמויות רעות, אבל זה מתברר לא הולך לעבוד. 

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

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

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

קהל: הקצאת זיכרון? 

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

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

הממ, מה קרה? מחרוזת בבקשה. מה עשה לא בסדר? שלום עולם, חיץ. שלום עולם. אה, אני יודע מה זה עושה. אוקיי. אז זה קורא עד עד החלל הראשון. אז בואו לרמות רק לרגע ו אומר רק רציתי להקליד משהו באמת ארוך כמו זה משפט ארוך זה אחד, שתיים, שלוש, ארבעה, חמש, שש, שבע, שמונה, תשע, 10, 11, 12, 13, 14, 15, 16. אוקיי. זה אכן משפט ארוך. אז המשפט הזה הוא יותר מ- 16 תווים ולכן, כאשר אני על Enter, מה הולך לקרות? ובכן, במקרה זה של חיץ סיפור, שהכרזתי בעצם להיות מערך עם 16 תווים מוכנים ללכת. אז אחת, שתיים, שלוש, ארבעה, חמש, שש, שבע, שמונה, תשע, 10, 11, 12, 13, 14, 15, 16. אז 16 תווים, ועכשיו, כשאני לקרוא במשהו כזה הוא ארוך משפט, מה שהולך לקרות הוא שאני הולך לקרוא בזה הוא ארוך S-E-N-T-E-N-C-E, משפט. 

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

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

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

קהל: המחרוזת היא אורך 1,001. DAVID מלאן: בדיוק. אם המחרוזת שלך היא אורך 1,001, יש לך בדיוק את אותה בעיה, ועל ידי הטיעון שלי, הייתי רק אז לעשות את זה 2000, אבל אתה לא יודע ב לקדם כמה גדול הוא צריך להיות, ובכל זאת, אני צריך לקמפל את התכנית שלי לפני לתת לאנשים להשתמש והורדה את זה. אז זה בדיוק מהסוג דברים שמנסה ספריית CS50 כדי לעזור לנו עם ואנחנו רק מבט חטוף בחלק מיישום הבסיסי כאן, אבל זה CS50 נקודת C. זה הוא הקובץ שהיה בCS50 IDE כל השבועות האלה אתה שכבר משתמש. זה הידור מראש ושיש לך הייתי משתמש בו באופן אוטומטי על ידי טבע שיש מקף דגל CS50 L עם צלצול, אבל אם אני לגלול למטה דרך כל פונקציות אלה, הנה GetString, ורק כדי לתת לך הטעם של מה שקורה, בואו ניקח מבט מהיר על המורכבות היחסית. זה לא סופר ארוך פונקציה, אבל אנחנו לא צריך לחשוב כל קשה על איך ללכת על מקבל מחרוזות. 

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

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

קהל: זה מתאר סכום זיכרון שיכול להיות [לא ברור]. 

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

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

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

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

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

קהל: למה אתה להכפיל הקיבולת של החיץ ולא רק הגדלת זה על ידי את הסכום המדויק? 

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

אז בואו נסתכל על כמה תופעות לוואי אחרות של זיכרון, דברים שיכולים להשתבש וכלים שאתה יכול להשתמש בו כדי לתפוס מיני הטעויות האלה. למרות שמסתבר שכולכם, check50 לא סיפר לך כמה שיותר, כבר כתב עגלה קוד מאז שבוע אחד, גם אם כל בדיקות check50 הן עבר, וגם אם אתה וTF שלך הם סופר בטוחים ש הקוד שלך עובד כמתוכנן. או את הקוד שלך כבר מרכבה פגום בכל מה שמכם, בשימוש בספריית CS50, כבר דולף זיכרון. אתה כבר שואל את מערכת ההפעלה לזיכרון ברוב התוכניות שכתבת, אבל יש לך אף פעם לא באמת נתן אותו בחזרה. שנקרא GetString וGetInt וGetFloat, אבל עם GetString, יש לך מעולם לא קרא unGetString או תנו מחרוזת חזרה או משהו דומה, אבל שראינו שGetString עושה להקצות זיכרון בדרך של malloc או זה להקצות מחדש פונקציה, שהוא רק דומה מאוד ברוח, ובכל זאת, אנחנו כבר שואל את מערכת ההפעלה ל זיכרון וזיכרון שוב ושוב אבל אף פעם לא נותן אותו בחזרה. 

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

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

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

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

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

קהל: [לא ברור] פעמים את הגודל של int אשר 10 פעמים ש[ לא ברור] DAVID מלאן: טוב ותן לי לסכם. אז להקצות מספיק מקום למספרים שלמים 10 או 10, מה הגודל של int, זה ארבעה בתים, כך 10 פעמים 4 הוא 40, כך שהצד ימני שיש לי המודגש הוא לתת לי 40 בתים ו לאחסן את הכתובת של הבית הראשון לx. ועכשיו סוף סוף, והנה שבי תכנית זו היא מרכבה, מה לא בסדר עם קו 21 המבוסס על היגיון זה? מה רע בקו 21? כן? קהל: אתה לא יכול מדד לx [לא ברור]. DAVID מלאן: כן. אני לא צריך למדד x כמו ש. אז מבחינה תחבירית, זה בסדר. מה שיפה הוא, הרבה כמוך יכול לטפל בשם של מערך כאילו זה מצביע, באופן דומה אתה יכול לטפל מצביע כאילו זה מערך, ואז אני יכול מבחינה תחבירית אומר תושבת x משהו, x הסוגר אני, אבל 10 הוא בעייתיים. למה? 

קהל: כי זה לא בפנים. 

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

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

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

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

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

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

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

קהל: מצביע. 

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

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

קהל: אמפרסנד [לא ברור]. 

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

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

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

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

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

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

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

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

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

קהל: ידו של טיילור צריך להצביע שמאל. 

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

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

ג'ייק: ג'ייק. 

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

קהל: התחל עם השמאלי ביותר. 

DAVID מלאן: התחל עם השמאלי ביותר. מי השמאלי ביותר כאן אז? קהל: ראשית. 

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

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

קהל: טיפאני צריך להצביע על 9? DAVID מלאן: אני לא יכול להתקרב לך את זה. מי צריך להצביע על 9? 

קהל: טיפאני. 

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

אריק: אריק. 

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

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

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

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

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

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

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

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

[השמעת מוסיקה]