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

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

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

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

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

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

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

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

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

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

קהל: איפה שעתי עבודה? 

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

אני יודע גם הלילה או מחר הוא צהבהב, ואני חושב שיש לנו נחלת ללילה. אני לא בטוח. שאלה טובה. בדוק בCS50. 

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

אוקיי, אז ערימות. מי אהב את השאלה על ג'ק ובגדיו בחידון? אף אחד? אוקי זה בסדר. 

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

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

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

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

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

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

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

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

אתה רוצה לגשת בתוך של הערימה שלך, כך s.strings, ואתה הולך לשים את זה מספר חדש שאתה רוצה להכניס לתוך שם. בואו נגיד שאנחנו רוצים הכנס n int על הערימה, אנחנו יכולים לעשות s.strings, סוגריים, s.size שווה n. בגלל הגודל שבו אנחנו כיום נמצאים בערימה אם אנחנו הולכים לדחוף זה ב, אנחנו פשוט לגשת בכל מקום שהגודל הוא, מלאות הנוכחיות של הערימה, ואנחנו דוחפים n int על זה. ואז אנחנו רוצים לוודא ש אנחנו גם הגדלה גודל של n, כדי שנוכל לעקוב אחר שיש לנו הוסיף דבר נוסף כדי הערימה. עכשיו יש לנו גודל גדול יותר. האם זה הגיוני כאן כולם, איך זה עובד באופן הגיוני? זה היה סוג של מהיר. קהל: האם אתה יכול לעבור על s.stringss.strings [s.size] שוב? ANDI פנג: בטח, אז מה עושה s.size כרגע לתת לנו? קהל: זה הגודל הנוכחי. ANDI פנג: בדיוק, כך מדד הנוכחי שהגודל שלנו הוא ב, ולכן אנחנו רוצים לשים את המספר השלם החדש שאנחנו רוצים להכניס לתוך s.size. האם זה הגיוני? בגלל s.strings, כל ש הוא הוא שמו של המערך. כל זה הוא בגישה ל מערך בתוך struct שלנו, ולכן אם אנחנו רוצים מקום n למדד ש, אנחנו רק יכולים לגשת אליו סוגריים באמצעות s.size. לְהִתְקַרֵר. 

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

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

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

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

אז מה שאנחנו אוהבים לקרוא את זה הוא dequeueing וenqueueing. אם אנחנו רוצים להוסיף משהו לתורנו, אנחנו Enqueue. אם אנחנו רוצים dequeue, או לקחת משהו משם, אנחנו dequeue. 

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

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

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

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

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

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

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

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

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

עכשיו אנחנו רוצים להוסיף משהו ל התור הזה, אבל כמו שאתם יכולים לראות, זה לא כל כך פשוט כמו שרק להוסיף מה שאחרי הגודל כי אז נגמרו גבולות של המערך האמיתי שלנו. איפה אנחנו רוצים באמת להוסיף כאן. זה היופי של תור הוא שלנו, מבחינה ויזואלית זה נראה כמו הקו הולך ככה, אבל כאשר הם מאוחסנים במבנה נתונים, הם נותנים לו כמו כמו מחזור. זה סוג של עוטף לחזית באותה הדרך כי קו יכול גם לעטוף סביב בהתאם לכל מקום שאתה רוצה תחילת השורה להיות. וכך אנו אם לקחת להסתכל למטה כאן, בואו אומר שאנחנו רוצים ליצור פונקציה שנקראת Enqueue. רצינו להוסיף n int לq ש. אם q.size q-- אנחנו נתקשר כי הנתונים שלנו structure-- אם queue.size לא שווה לקיבולת או אם זה פחות מיכולת, q.strings הוא המערך בתוך q שלנו. אנחנו הולכים להגדיר ששווה לq.heads, שנמצא ממש כאן, בתוספת q.size מודולוס על ידי היכולת, ש לעטוף בחזרה כאן. 

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

קהל: 0. 

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

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

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

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

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

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

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

קהל: כי הם כולם מחוברים, אבל אתה לא ממש יודע איפה [לא ברור]. 

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

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

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

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

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

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

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

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

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

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

בואו שלטבול לקצת. זה יהיה די חשוב לpset. ההיגיון שלו הוא פשוט מאוד, אולי מבחינה תחבירית פשוט ליישם אותה. אתם רוצים לעשות בטוח שאתה מבין. לְהִתְקַרֵר. 

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

קהל: זה דינמי, לכן קל יותר צריכה-- 

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

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

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

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

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

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

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

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

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

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

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

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

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

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

אוקיי, אז קוד יהיה כאן. אתם תסתכל אחרי הסעיף. זה יהיה שם. 

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

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

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

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

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

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

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

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

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

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

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

בסדר, אז עכשיו אני באמת לבלות כנראה כמו 15 עד 20 דקות או בתפזורת של שאר הזמן בסעיף מדבר על שולחנות חשיש. כמה מכם קראו מפרט pset5? בסדר, טוב. זה גבוה יותר מאשר 50% מכלל. זה בסדר. 

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

אם אני רוצה insert-- מה פירות שמתחיל ב, אני לא יודע, B, אחר מאשר ברי, בננה. 

קהל: Blackberry. 

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

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

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

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

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

ANDI פנג: אז החשיש שלך function-- שולחן החשיש שלך יכול להיות גדול כמו שאתה רוצה אותו. אז במובן הזה, חשבתי זה היה קל מאוד, מאוד פשוט בשבילי מבוססים רק סוג באותיות של המילה הראשונה. וכך יש רק 26 אפשרויות. אני יכול רק לקבל 26 אופציות מ 0 עד 25, כי הם יכולים רק תתחיל מ- A עד Z. אבל אם אתה רוצה להוסיף, אולי, מורכבות יותר או יותר מהר לרוץ זמן שלך שולחן חשיש, אתה בהחלט יכול לעשות כל מיני דברים. אתה יכול להפוך את עצמו משוואה שנותנת לך יותר הפצה בך מילות, אז כשאתה מחפש, זה הולך להיות מהיר יותר. 

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

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

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

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

לְהִתְקַרֵר. בסדר, עכשיו יש לנו סוג אחר של מבנה נתונים שנקרא עץ. בואו נלך על ולדבר על ניסיונות שהם שונים במובהק, אבל באותה הקטגוריה. בעיקרו של דבר, כל עץ הוא במקום של ארגון הנתונים באופן ליניארי כי שולחן חשיש does-- יודעים, זה שיש לי עליון ותחתון ואז אתה סוג של לקשר את של it-- יש עץ עליון שבו אתה קורא את השורש, ואז יש לו עלים סביבו. 

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

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

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

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

אז הנה, אם אני הולך לחפש הערך של 66, אני יכול להתחיל ב 55. זה 66 יותר מ 55? כן, זה הוא, אז אני יודע שאני mus חיפוש אני n המצביע הימני של העץ הזה. אני הולך ל -77. אישור, הוא 66 פחות או יותר מ -77? זה פחות מ, כך שאתה יודע, הו, שצריך להיות הצומת עזבה. 

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

אז אתה צריך להגיד את זה בדיוק באיזה שלב היא זו מילה? באיזה שלב זה לא מילה? ובאיזו נקודה אני צריך לחפש דברים, ובאיזו נקודה אני צריך ללכת הלאה? כולם ברורים של זה? לְהִתְקַרֵר. 

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

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

אנחנו הולכים להקצות H, קודם כל, זה null, אנחנו הולכים להיפטר. אנחנו הולכים לי מטה נקודת H. אם אנו רואים H, אנחנו רוצים את זה ללכת למקום אחר. 

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

קהל: האם אנחנו יכולים לצטט רק על ידי שימוש ב[ לא ברור]? 

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

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

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

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

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

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