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

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

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

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

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

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

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

26 בקובץ שנקרא memory.c, שהיה הדוגמא שאנחנו משחקים עם באותו הזמן. אז זה כנראה לא בmalloc. זה היה כנראה בקוד שלי במקום. אז אנחנו תראו את זה שוב ושוב לפני זמן רב. 

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

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

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

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

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

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

אז בקיצור, 18 קו זה פשוט אומר, תנסה לקרוא int מהמשתמש של מקלדת ולאחסן אותו בתוך X, בשעה מה כתובת x קורה לחיות ב. ואז לבסוף, קו 19 רק אומר, תודה על int, במקרה זה. 

אז הרשה לי להמשיך ולעשות את זה. אז להפוך את scanf 0. תנו לי להמשיך ולהתמקד פנימה אני אלך ולרוץ עם זה נקודות לקצץ scanf 0. מספר, בבקשה? 50. תודה על 50. אז זה די פשוט. 

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

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

אבל דברים יותר מעניינים בדוגמה זו הבאה. אם אני הולך לscanf-1.c, מה הוא אחד דבר שהשתנה באופן מהותי ב הדוגמא הבאה זה? אני משתמש * char, כמובן, במקום int. 

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

קו 17 - אני שוב אומר, תן לי בבקשה משהו, במקרה זה, מחרוזת. ולאחר מכן בשורה הבאה, אני קורא scanf, שוב, זה נותן קוד תבנית, אבל אחוזים של הזמן הזה. ולאחר מכן הפעם, אני זה נותן חיץ. 

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

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

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

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

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

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

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

אז תן לי להמשיך ולעבד את זה. אני הולך לעשות את זה דרך בית הספר הישן. אז מקף צלצול 0, scanf-1, scanf-1.c, Enter. אופס, בית ספר ישן מדי. בואו נראה. לאן אני הולך? אה, חיץ * char. הו, תודה לך - שמור, בסדר - בית הספר ישן מאוד. בסדר, זה כבר זמן מה. 

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

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

אז אנחנו לא יכולים לגרום ממש בקלות segfault עם זה, אבל ברור שזה לא ההתנהגות שאני רוצה. אז מה הפתרון פשוט? ובכן, בscanf-2, הרשה לי להציע כי במקום באמת רק הקצאה * Char, הרשו לי להיות קצת יותר חכם על זה, ותן לי להקצות זיכרון כרצף של 16 תווים. 

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

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

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

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

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

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

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

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

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

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

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

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

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

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

למשל, אם אני חוזר לgedit כאן רק לרגע, ואני הולך קדימה ולעשות משהו כזה, תן לי לחסוך זה כמו, נניח, structs.c באופן זמני, אני רק הולך ללכת קדימה וכולל standardio.h, החלל עיקרי int. ולאחר מכן בכאן, נניח שאני רוצה כדי לכתוב תכנית שמאחסנת תלמידים רבים ממספר רב של בתים, למשל. אז זה כמו registrarial מסד הנתונים. כלשהו 

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

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

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

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

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

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

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

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

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

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

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

ועכשיו, מה שעושה את השאר של תכנית זו עושה? אני צריך משהו קצת שרירותי. אז מ -24 ואילך באינטרנט, אני לחזר 0 עד 3. אז אני שואל את המשתמש עבור שמו של התלמיד. ואז אני משתמש GetString כמו קודם. ואז אני שואל לביתו של התלמיד, ואני משתמש בGetString כמו קודם. 

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

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

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

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

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

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

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

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

אני להתקרב קצת. ועכשיו תן לי לרוץ נקודה לקצץ structs-1. שמו של התלמיד - דוד מאת'ר, בואו אעשה את רוב קירקלנד, בואו נעשה את לורן וורט. מה שמעניין עכשיו הוא הודעה - ואני רק יודע את זה כי אני כתבתי את התכנית - יש קובץ עכשיו על הנוכחי שלי ספרייה בשם students.csv. חלק מכם אולי ראה אלה בעולם האמיתי. 

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

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

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

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

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

fopen אומר קובץ פתוח. מה קובץ שאתה רוצה לפתוח? אני רוצה לפתוח קובץ שאני יהיה באופן שרירותי לקרוא students.csv. אני יכול להתקשר לכל דבר שאני רוצה. 

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

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

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

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

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

אז סיור הסופה, אבל אתה תקבל מוכר מדי עם קובץ I/O-- קלט ופלט - עם pset חמש. ושאלות על יסודות ראשוניים כאן? כן? 

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

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

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

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

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

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

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

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

ואני הולך לומר, נניח זה קורות החיים שלי. resume.doc שלי מאוחסן ב מיקום, נניח 123. אני תמיד הולך למספר הזה. אבל די אם נאמרתי שרק רוצים בזכרון RAM, אתה יכול לקחת את כונן קשיח זה לגיגה או 200 ג'יגה או טרה, ושאתה יכול מספר כל הבתים. באפשרותך למספר את כל הגושים של 8 סיביות. 

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

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

שום דבר, באמת. זה בדיוק כמו תיקייה. זה תיקייה מיוחדת, כדי להיות בטוח. אבל האם זה באמת למחוק את הקובץ? 

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

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

כן, אז הוא נמחק יותר מכך. אבל כל מה שקורה הוא זה. המחשב שבו שוכח resume.doc היה. 

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

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

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

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

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

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

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

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

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

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

[השמעת וידאו הסוף] 

דוד Malan: קרב קטן עכשיו עמוק יותר על מה למעשה על מגשים אלה. 

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

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

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

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

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

[השמעת וידאו הסוף] 

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

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

צפיפות סטנדרטית הייתה 800 קילו. ולפני זה, היו דיסקים של 400 קילובייט. ולפני זה, היו 5 ו 1/4 דיסקי אינץ, שהיו באמת, תקליטונים רחב יותר וגבוה יותר וקטנים מהדברים האלה כאן. אבל אתה יכול ממש לראות את מה שנקרא היבט דיסקט מהדיסקים האלה. 

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

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

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

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

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

ושוב, כדי לשים את זה בפרספקטיבה נכונה, כמה גדול הוא שרוב כוננים קשיח בימים אלה? 500 ג'יגה בייט, טרה, אולי ב מחשב שולחני, 2 טרה, 3 טרה, 4 טרה, נכון? זהו מגה אחד, פחות או יותר, שאפילו לא יכול להתאים MP3 טיפוסי כבר בימים אלה, או חלק קובץ מוסיקה דומה. 

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

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

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

כמה שבועות אחרי זה הוא המעמד דו"ח, שהוא באופן דומה דוא"ל מזדמן לTF לומר עד כמה הרחק מאחור אתה בסופי שלך יישומו של הפרויקט, ואחריו Hackathon CS50 כדי שכולם הוא הוזמן, שיהיה אירוע מ 20:00 בערב אחד עד 07:00 בבוקר למחרת. פיצה, כפי שאולי ציינו בשבוע אפס, wil להיות מוגש בשעה 9:00 בערב, אוכל סיני בשעה 1:00 PM. ואם אתה עדיין ער בשעה 5:00 בבוקר, אנחנו ניקח אותך לבית הפנקייק הבינלאומי לארוחת בוקר. 

אז Hackathon הוא אחד יותר חוויות בלתי נשכחות בכיתה. אז היישום הוא עקב, ו אז יריד CS50 השיא. פרטים נוספים על כל אלה בשבועות הבאים. 

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

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

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

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

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

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

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

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

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

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

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

אז אם יש לי את המספרים האלה במערך - 9, 17, 22, 26, 24 - לא בהכרח בקנה מידה. בסדר, אז הנה הוא המערך שלי - אוי, אלוהים. בסדר, אז הנה הוא המערך שלי. אוי אלוהים. 

[שחוק] 

דוד Malan: להעמיד פן. זה יותר מדי מאמץ כדי לחזור ולתקן את זה, ולכן יש - 26. אז יש לנו מערך זה של 9, 17, 22, 26, ו -34. לאלו מכם יכולים לראות את טעות מביכה אני רק עשיתי, זה מה שיש. 

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

נתראה ביום רביעי. 

דובר: בCS50 הבא, דוד שוכח מקרה הבסיס שלו. 

דוד Malan: וזה איך שאתה שולח הודעות טקסט עם ג מה - 

[הודעה טקסט שונות הודעת SOUNDS]