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

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

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

קהל: אז אני זוכר שראיתי את זה ב דוגמא קודמת של הסתכלות char * s ולראות את הסריקה של ים ו רואה כי זה מצביע, איך עשית את זה ישפיע על מה שסרקת ב? האם זה זה או את הכתובת של ים? 

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

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

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

קהל: אם אתה משתמש בקלט שב מחרוזת זה זמן רב יותר מאשר 49 תווים. 

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

אבל בדיוק את זה, אם אתה קורא את מחרוזת זה זמן רב יותר מאשר 49 תווים, 49 כי אתה צריך מקום לקו הנטוי 0, אתה הולך לעלות על גדותיו מאגר זה. ואתה עלול לקבל מזל להיות מסוגלים לכתוב אופי 51st, 52nd, 53rd. אבל בשלב מסוים, מערכת ההפעלה הוא הולך להגיד, לא. זה בהחלט לא זיכרון מותר לך לגעת. והתכנית הולכת segfault. 

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

קהל: אז כדי לפתור את זה, אתה יכול יש לו הצהרת בדיקה בפועל הוא גדול יותר באורך יותר או קטן יותר? 

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

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

אז שאלה של 2 שואל, נניח שגרסה כי 3 נערך והוצאו להורג. מדוע ייתכן שתכנית segfault? אז זה בעצם אותו הדבר תענה, למרות שזה נראה קצת להשתכלל. אנחנו משתמשים malloc, שמרגיש כמו אנחנו נותנים את עצמנו יותר אפשרויות. ואז אנחנו משחררים כי זיכרון בסוף. זה עדיין רק 50 בתים של זיכרון. אז אנחנו אולי עדיין מנסים לקרוא ב51, 52, 1,000 בתים. זה הולך לsegfault בדיוק מאותה הסיבה. 

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

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

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

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

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

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

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

קהל: האם זה היה 64 סיביות אדריכלות, היית כי תכפיל את כולם? 

ROB אודן: זה לא היית תכפיל את כולם. אז ארכיטקטורת 64 קצת, זה, שוב, שינויים שדבר בסיסי ש המצביע הוא החברה 64 סיביות. כן. אז מצביע הוא 8 בתים. אז אלה שהיו 4 בתים הולכים להיות 8 בתים. תלמיד, שהיה שני מצביעים, טוב, עכשיו זה הולך יהיה 8 בתים, 8 בתים. זה הולך להפוך את 16 בתים. 

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

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

קהל: השרת חיפש עבור מה שביקשת. אבל זה לא הצליח למצוא אותו. אז יש שגיאה. 

ROB אודן: אז השרת היה מחפש את מה שאתה רוצה. אז פשוט מחפש כאן, 302 מצאו, זה היה יכול למצוא אותו. 

קהל: אני מצטער. נמצא אומר שהם לא מוצאים אותו. סליחה. 

ROB אודן: אז 302 נמצא. השרת הוא מסוגל למצוא מה שרצית. 

קהל: אבל זה לא להציג אותה? 

ROB אודן: ההבדל בין זה 302 ו200 הוא שזה יודע מה אתה רוצה. אבל זה לא בדיוק שבו שרצית לשאול. אז 302 היא הפניה טיפוסית. אז שביקשת דף. היא יודעת, הו, אני רוצה כדי להחזיר לך את זה. אבל זה בכתובת שונה. אז היי, אתה באמת רוצה את זה. 

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

ROB אודן: אישור. אז מה לגבי 403 אסורים? 

קהל: אני חושב שזה שהשרת הוא בעצם אומר שהלקוח לא יכול לגשת לדף הבית. 

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

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

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

ROB אודן: אז 404 לא נמצא. כן. אז בניגוד ל302 שבו לא היה זה בדיוק שבו אתה שואל, אבל היא יודעת מה אתה רוצה, זה, זה פשוט אין לי מושג מה אתה רוצה. ואתה לא מבקש משהו בתוקף. 418 אני קומקום ולאחר מכן 500 שרת פנימי. אז למה אתה יכול לקבל את זה? 

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

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

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

ROB אודן: כן. 

קהל: האם שגיאה עדיין לבוא? 

ROB אודן: אז אתה לא הייתי מקבל טעות זו, כי הכל מנקודת המבט של שרת האינטרנט היה בסדר לחלוטין. אבל אתה ביקשת index.html. שביקשת shuttle.js וservice.js. וזה היה מסוגל לחזור בהצלחה לכל הדברים האלה שאתה - 200. על אישור. זה רק כאשר הדפדפן שלך ניסה לפרש את קוד JavaScript כי זה כמו, הרגע, זה לא שגיאת JavaScript בתוקף. יש עוד שאלות? בסדר. 

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

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

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

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

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

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

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

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

קהל: בחץ המצביע [לא ברור] שווה null, עושה את זה להתמודד עם הרשימה כי הרשימה היא ריקה? 

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

אז אם המצביע שווה לרשימה עצמו, כך שאם אני בתחילת הרשימה ומצאתי n, אני צריך לעשות כמה דברים. אחד, אני צריך לשנות את הרשימה כדי מצביע לשדה הבא, 50. אז נניח שאני מנסה כדי להסיר 34. אז הבחור הזה חייב ללכת משם ברגע. 

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

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

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

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

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

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

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

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

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

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

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

קהל: אז היא רשימה דומה ראש בדוגמאות קודמות. 

דוד י מלאן: בדיוק, בדיוק. רק שם שונה עבור משתנה גלובלי. העולם רחב מה? 

ROB אודן: אישור. אז זה אחד שבו אתה הייתי צריך לכתוב פסקה. יש אנשים שכתבו מאמרים לשאלה זו. אבל אתה רק צריך להשתמש ששת תנאים אלה כדי לתאר את מה שקורה כאשר אתה מנסה ליצור קשר facebook.com. אז רק אני אדבר בתהליך משתמש בכל המונחים האלה. אז בדפדפן שלנו, אנחנו סוג facebook.com ולחץ על Enter. אז הדפדפן שלנו הולך לבנות HTTP לבקש שזה הולך לשלוח דרך איזה תהליך לפייסבוק עבור פייסבוק להגיב אלינו עם ה-HTML של הדף שלה. 

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

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

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

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

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

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

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

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

ROB אודן: אז HTTPS, שכן זה האזנה במיוחד עבור מוצפן, זה ביציאה 4430. 

קהל: ומיילים הם 25, נכון? 

דוד י מלאן: יוצא מיילים, 25, כן. 

ROB אודן: אני אפילו לא מכיר את רוב - כל אלה נמוכים יותר נוטים להיות שמורות לדברים. אני חושב שכל מה שמתחת 1024 הוא שמורות. 

קהל: למה אמרת 3 היו המספר השגוי? 

ROB אודן: כי בכתובת ה-IP, יש ארבע קבוצות של ספרות. והם 0-255. אז 192.168.2.1 הוא נפוץ כתובת ה-IP ברשת מקומית. שים לב כל אלה הם פחות מ 255. אז כשהתחלתי עם 300, כי לא יכול להיות היה אחד מהמספרים. 

דוד י מלאן: אבל זה קליפ מטופש מ-- היה זה CSI, שם היה להם מספר זה היה גדול מדי לכתובת ה-IP. 

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

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

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

דוד י מלאן: כן בסדר כאן היית היה להשתמש בבית ספר ישן ל לולאה עם i $ = 0 0 ובאמצעות ספירה ל להבין את אורכו של ריי. גם לגמרי בסדר, רק wordier קטן. 

קהל: אז אם אתה הולך [לא ברור], היית עושה - אני לא זוכר מה [לא ברור] היא הלולאה. הייתי לך $ quad סוגר אני? 

דוד י מלאן: בדיוק. כן, בדיוק. 

ROB אודן: כל דבר אחר? 

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

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

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

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

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

קהל: אז אם אנחנו רק אמר פחות בטוח - 

דוד י מלאן: [צוחק] איכס. אלה הם תמיד קשים יותר אלה לפסוק. 

ROB אודן: זה יהיה כבר קיבל. 

דוד י מלאן: מה? 

ROB אודן: אני יצרתי את הבעיה הזו. שהיה מתקבל. 

דוד י מלאן: כן. 

קהל: מגניב. 

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

קהל: מה עם לא לטעון מחדש את הדף? 

ROB אודן: כן. זה היה תשובה מקובלת. 

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

קהל: זה ליניארי. חיפוש ברשימה מקושרת הוא ליניארי במקום מה שאתה נכנסת פנימה 

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

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

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

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

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

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

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

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

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

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

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

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

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

דוד י מלאן: דום דה dom dom. אני כנראה היחיד שמבין ככה זה אמור להיות מבוטא, נכון? 

ROB אודן: היה לי מושג באמת. 

דוד י מלאן: זה גרם תחושה בראש שלי. 

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

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

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

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

ROB אודן: שאלות על זה? אני צריך לעשות הבא? 

דוד י מלאן: בטח. 

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

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

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

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

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

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

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

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

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

דוד י מלאן: לא די הרוח השאלה אך מקובלת ל spec בכל זאת. 

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

דוד י מלאן: האם אתה רוצה לומר בתואר הזה? 

ROB אודן: מס 

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

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

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

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

כדי שתוכל להסיר. Php לגמרי זוכר מהרצאה. ואתה באמת יכול לעשות. / Foo אם שchmodded בכך שהוא הפעלה. אז + x foo chmod היה עושה את זה. ואם אתה גם להוסיף את העסק כאן. אבל באמת, הבעיה הייתה מקבלת ב הדפסה החוצה משהו כזה. לא HTML, לא C-קוד בהחלט, רק חלק PHP. אז מילו ולאחר מכן חזר בבעיה 25. וב25, אתה קיבל את הדברים הבאים קוד שלד, שהיה דף אינטרנט פשוט למדי. והחלק העסיסי HTML החכם היה למטה כאן, איפה שיש לנו בתוך הגוף טופס הכולל זיהוי ייחודי של תשומות בתוכה הייתה שתי כניסות, אחת עם רעיון של שמו, אחד עם רעיון של כפתור. 

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

אז דרך אחת אתה יכול לעשות זאת היא עם jQuery, שנראה קצת מבחינה תחבירית מביך בהתחלה. אתה יכול לעשות את זה עם קוד DOM טהור - document.getelement לפי תעודת זהות. אבל בואו נסתכל על גרסה זו. יש לי כמה חשוב השורות הראשונות. אז אחד, יש לנו את הקו הזה, שהוא זהה למה שאולי ראה ב, אני מאמין, form2.html מכיתה בשבוע 9. וזה רק אומר, לבצע הקוד הבא בעת המסמך מוכן. זה להיות חשוב רק בגלל דפי HTML נקראים מלמעלה למטה, משמאל לימין. 

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

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

קהל: הוא מקבל את הערך ש משתמש לא עשה בקוד HTML שלהלן. זה נהיה מזהה ושלאחר מכן מוצא את הערך של זה. 

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

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

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

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

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

קהל: כי זה קורה רק פעם אחת. 

דוד י מלאן: קורה רק פעם אחת. לא ממש. כן? 

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

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

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

קהל: אז לשמור אותו בצד לקוח. 

דוד י מלאן: שמירה זה בצד לקוח. בדיוק נכון. עד הבא היה שלי הו MySQL. 

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

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

דוד י מלאן: מזומן. 

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

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

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

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

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

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

ROB אודן: זכור כי MySQL הוא שפה נפרדת מ-PHP. אנחנו במקרה כותבים MySQL ב-PHP. ו-PHP אז הוא שולח אותו מעל לשרת MySQL. אבל אתה לא צריך PHP כדי לתקשר עם שרת MySQL. 

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

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

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

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

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

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

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

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

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

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

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

קהל: Q הוא אחסון ערכים חיוביים. מכיוון שאתה לאחסן רק ערכים חיוביים בq, שלילי הוא שגיאה. 

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

קהל: אתה כבר נכשל כדי להחזיר מספר שלם. 

דוד י מלאן: בדיוק. וזה מקום שבי C מקבל די מגביל. אם אתה אומר שאתה הולך להחזיר int, יש לך להחזיר int. אתה לא יכול לקבל מפואר ולהתחיל לחזור bool או לצוף או מחרוזת או משהו כזה. עכשיו, בינתיים, JavaScript ו-PHP ו כמה שפות אחרות יכול, למעשה, יש לך חוזר שונה סוגים של ערכים. וזה באמת יכול להיות שימושי, שבו אתה יכול לחזור ints, אפסים חיוביים, ints השלילי, או שקר או null אפילו כדי לסמן שגיאה. אבל אין לנו את זה רבגוניות בג 

אז עם dequeue, מה שאנחנו מציע לעשות הוא - 

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

דוד י מלאן: זה למה אני לא אומר את זה. 

ROB אודן: אבל זה לא היה נכון כי אתה לא יכול לחזור שווא. 

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

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

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

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

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

אז אם אני שם את 34 כאן בחלקו העליון, ולאחר מכן שמתי 20 כאן, אז זה חוקי כל כך כה, כי כאן 34 למעלה. 20 הוא הולך לצד השמאל. אז זה פחות. אבל אני לא יכול ואז לשים 59 כאן, כי למרות 59 הוא בצד הימין של 20, זה עדיין בצד השמאל של 34. אז עם אילוץ זה בחשבון, הדרך הקלה ביותר של ככל הנראה פתרון זה בעיה היא רק מעין המספרים האלה - כך 20, 34, 36, 52, 59, 106. ולאחר מכן להוסיף אותם משמאל לימין. 

אז 20 הולך כאן. 34 הולך כאן. 36 הולך כאן. 52, 59, 106. ואתה גם יכול להבין עם כמה חיבור והגשמה, אה, רגע, אין לי מספיק מספרים כדי למלא את זה בפה. אז אני צריך reshift מה פתק מסלול הולך להיות. אבל שמו לב שבשלושה הסופיים, אם אתה קורא משמאל לימין, הוא ב סדר הולך וגובר. 

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

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

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

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

קהל: יש לי שאלה על [לא ברור]. 

ROB אודן: אז דרך אחת מתקרב כל בעיה רקורסיבית היא לחשוב רק על זה כמו שאתה צריך לחשוב על כל המקרים שפינה. לכן קחו בחשבון שאנחנו רוצים להדפיס כל העץ הזה. אז כל מה שאנחנו הולכים להתמקד על היא צומת המסוימת הזה - 36. שיחות רקורסיבית, אנו מעמידים פנים אלה רק לעבוד. אז הנה, קריאה רקורסיבית זה כדי Traverse, אנחנו אפילו בלי לחשוב על זה, פשוט חוצה את השמאל שלוש, מתאר לעצמי שכבר מדפיס 20 ו34 עבורנו. ולאחר מכן כאשר אנו סופו של דבר באופן רקורסיבי קורא Traverse על בסדר, שיהיה בצורה נכונה להדפיס 52, 59, ו106 עבורנו. 

אז בהתחשב בכך שזה יכול להדפיס 20, 34, ו האחרים יכול להדפיס 52, 59, 108, כל מה שאנחנו צריכים להיות מסוגלים לעשות הוא להדפיס את עצמנו באמצע זה. אז להדפיס את כל מה שלפנינו. להדפיס את עצמנו, ולכן הדפסת הצומת הנוכחית 36, printf הרגיל, ולאחר מכן להדפיס כל דבר אחרינו. 

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

ROB אודן: בשאלות? 

דוד י מלאן: ולמטה מעט המספרים, האם מישהו יודעים איפה מספרים אלה באים? 

ROB אודן: יש לי ממש מושג. 

דוד י מלאן: הם מופיעים לאורך כל החידון. 

קהל: האם הם אותם המספרים? 

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

ROB אודן: כל שאלות שעברה על כל דבר בחידון?