דוד Malan: בסדר. ברוך שובי לCS50. זוהי תחילת השבוע 8. וזוכרים שקבוצת הבעיה 5 הסתיימה עם קצת אתגר. אז בהנחה שאתה התאושש את כולך עמיתי הוראה והתצלומים של CA בקובץ card.raw, אתה זכאי עכשיו כדי למצוא את כל האנשים האלה, ו זוכה מאושר אחד ילך הביתה עם אחד מהדברים האלה, את תנועת הקפיצה מכשיר שאתה יכול להשתמש עבור סופי פרויקטים, למשל. 

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

לאחר מכן, "אני היה מחוץ לעיר בסוף השבוע הזה, וכשחזרתי, לא היה אחד ב שלי חדר שינה. "[שחוק] דוד Malan: הציטוט הבא מצוות חבר, "תלמיד הגיע לבית שלי ב סומרוויל ב -4 בבוקר בבוקר ". הבא צוות, "יש לי למלון שלי בסן פרנסיסקו ותלמיד חיכו לי לי בלובי עם שלוש DSLRs ". סוג של מצלמה. "אני אפילו לא בסגל בסמסטר הזה, אבל תלמיד פרץ לבית שלי זה בוקר והקליט את כל העניין עם Google זכוכית. "ואז לבסוף, "לפחות 12 בני אדם בשקיקה ממתין לי כשיצא משלי לימוזינה, ואז התעורר. "בסדר. אז בין התמונות, כפי שאתה יכול כזכור, הוא הבחור הזה כאן, מי אתה אולי יודע כמיל בננה, המתגורר עם לורן קרבאליו, הראש שלנו עמית הוראה. מילו, מילו, בוא הנה בחור. מילוא. מילוא. אכפת לך, שהוא לובש גוגל זכוכית, ולכן אנחנו אראה לך את כל זה לאחר. אז זה מיל אם אתה רוצה לצלם איתו לאחר מכן. אם ברצונך להסתכל החוצה בקהל שם. אישור. זה סרט טוב. ובכן, מילו בננה. אה, לא עושה את זה. 

[שחוק] 

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

אז אם אתה עשוי להיות מעוניין באחד או יותר מהסמינרים של שנה זו, להירשם בcs50.net/seminar. ישנם סמינרים מבוגרים בcs50.net/seminars. ובסגל עד כה לשנה זו הם יישומי אינטרנט מדהימים עם Ruby on מסילות, אשר מהווה חלופה שפת PHP. בלשנות חישובית. מבוא לiOS, שהוא פלטפורמה המשמשת עבור iPhone ו פיתוח האייפד. JavaScript עבור יישומי אינטרנט, שנכסנו את זה, אבל בסמינר זה, אתה תלך לקבלת פרטים נוספים. 

קפיצת Motion, אז למעשה לא תהיה לנו קצת מחברינו מתנועת קפיצה, החברה עצמה, להצטרף אלינו. מחר, למעשה, על מנת לספק ידות על סמינר, אם לעניין אותך. Meteor.js, טכניקה חלופית עבור באמצעות JavaScript לא בדפדפן, אבל בשרת. Node.js, אשר היא במידה רבה כמו גם ברוח זו. עיצוב מלוטש אנדרואיד. אנדרואיד להיות חלופה פופולרית מאוד לiOS ו-Windows טלפון ופלטפורמות ניידים אחרות. הגנה אקטיבית ואבטחת האינטרנט. 

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

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

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

קהל: גודל דינמי. 

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

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

קהל: דורש יותר זיכרון. 

דוד Malan: זה דורש יותר זיכרון, איך בדיוק? 

קהל: [לא ברור]. 

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

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

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

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

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

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

קהל: [לא ברור]. 

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

קהל: [לא ברור]. 

דוד Malan: אישור. שמעתי מתחיל. למה בהתחלה? 

קהל: [לא ברור]. 

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

קהל: [לא ברור]. 

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

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

אז לאחר מכן הסתכל על הדבר הזה, שבי היא באמת ההזדמנות הגדולה האחרת עבור p-סט 6. ומבין, אם יש לך כבר, צלילות Zamyla לשני אלה, חשיש שולחנות ומנסה, ביתר פירוט. וההדרכה בוידאו היא מוטבע במפרט P-סט. זה היה trie - T-R-I-E. ומה שהיה מעניין זה היה שהזמן פועל בחיפוש אחר שם, כמו מקסוול בפעם האחרונה, הייתה גדול O של מה? מה זה? 

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

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

אז אם אנחנו רוצים אז כדי לקבוע אם מקסוול הוא כאן, אני יכול ללכת למערך הראשון, בחלקו העליון של העץ, השורש כביכול, החלק העליון של trie, ולאחר מכן בצעתי את המצביע מ ', לאחר מכן מצביע, אז X, W, E, L, l. ואז כשאני רואה כמה סמל מיוחד, מסומן כאן כמשולש. בקוד תראה שאנו מציעים לך מיושם כבול, רק אומר כן או לא, מילה עוצרת כאן. 

ובכן, ברגע שעברנו לM-X--W-E-L-L, מרגיש כמו שבע, אולי שמונה אם תלכו אחד בעברו, שמונה צעדים כדי למצוא מקסוול. או בואו נקראים לזה ק 'אבל זוכר שעבר זמן, אני טענתי שאם יש מציאותי אורך מרבי על מילה, כמו דמויות של 40 ומשהו, אורך מרבי מרמז ערך קבוע. אז באמת, כן, זה גדול מבחינה טכנית O של 8 או 7, או O הגדול באמת של ק 'אבל אם יש כובע סופי על מה K יכול להיות, זה קבוע. ואז זה גדול O של 1 ב סופו של היום. 

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

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

וזה לא. זה לא בהכרח את הנתונים מבנה שאתה צריך להימשך ל, כי כמו שולחנות חשיש, איזון. מה המחיר שאתה משלם כאן? זיכרון. אני מתכוון, זה זוועתי כמות הזיכרון. ואתה לא ממש יכול לראות את זה כאן, כי המחבר של תמונה זו ברור שקטום כל המערכים, ואנחנו לא רואים הרבה ושל B ו-C של של וQ של Y ושל וZ של במערכים אלה. אבל הם שם. 

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

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

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

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

קהל: שיחות לפונקציות. 

דוד Malan: אני מצטער. 

קהל: שיחות לפונקציות. 

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

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

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

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

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

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

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

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

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

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

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

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

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

סטיבן: לא הרבה. 

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

סטיבן: קוד אקראי פשוט, נכון? פשוט - 

מלאן דוד: כן, אני הולך קוראים לזה קוד, אבל אקראי - 

סטיבן: דברים. 

דוד Malan: דברים כמו אקראי 

סטיבן: חתיכות. 

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

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

סטיבן: מגש הוא תת 3. 

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

סטיבן: אפס. 

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

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

סטיבן: בתוך - הגודל? 

דוד Malan: אישור. גודל צריך להיות מה? 

סטיבן: גודל יהיה אחד. 

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

סטיבן: אנחנו הולכים מ תחתון עד 9. 

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

סטיבן: אז גודל הוא הולך לשניים. 

דוד Malan: אישור. אתה מחק - אופס. אתה מחק. 

סטיבן: מחק. 

דוד Malan: אתה מברשת. 

סטיבן: מברשת. 

דוד Malan: אישור. ומה עוד? 

סטיבן: ואז אנחנו - 

דוד Malan: אנחנו דחפו 17. 

סטיבן: אנחנו מקל על גבי 17, ולכן - 

דוד Malan: בסדר, טוב. 

סטיבן: - שחררת אותו. 

דוד Malan: בסדר. זה מתחיל להיות קל. אני לא הולך לעזור לך הפעם. Push 22. 

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

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

סטיבן: או. אוי. אתה באמת תפסת אותי לא מוכן. 

דוד Malan: אתה לא רואה את זה בא? 

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

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

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

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

[מחיאות כפות] 

סטיבן: תודה לך. 

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

קהל: אנחנו יכולים לעבור - 

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

למעשה, בואו לראות את זה. לפני שנכניס 22, בואו קדימה, dequeue 9. מה שמך שוב? 

קהל: ג'ייק. 

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

קהל: דוד. 

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

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

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

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

ובכן, מה קורה בהמשך? Enqueue בואו - מה השם שלך? 

קהל: Callen. 

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

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

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

קהל: אתה מחוץ לתחום. 

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

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

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

כל שאלות בערימות, או התור הזה? 

קהל: האם הסיבה לכך אתה צריך גודל כך שאתה יודע היכן יש לאדם? 

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

בסדר? מחיאות כפות לחבר 'ה הללו ואנו לתת להם לצאת משם. 

[מחיאות כפות] 

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

[מוסיקה מחול אוגר] 

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

[מוסיקה מחול אוגר] דוד Malan: בCS50 הבא -