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

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

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

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

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

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

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

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

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

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

1 SPEAKER: נכון. אז עם arrays-- 

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

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

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

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

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

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

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

בסדר, ללכת לשלב הבא. בצע את זה. האם הוא מכיל המספר 9? מס ' בצע את הבא. 

אז אנחנו צריכים לחזר למעשה באמצעות הרשימה המקושרת שלנו. אנחנו לא יכולים פשוט ללכת ישירות למקום שבי 9 הוא. ואם אתם באמת רוצים לראות כמה פסאודו-קוד שם למעלה. יש לנו כמה פונקציית חיפוש כאן שלוקח in-- מה זה לוקח ב? מה אתה חושב? כל כך קל אחד. מה זה? קהל: [לא ברור]. 1 SPEAKER: המספר שאנחנו מחפשים. נכון? ומה זה מתאים ל? זה מצביע ל? 

קהל: צומת. 

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

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

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

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

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

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

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

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

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

אבל reassigning שלך מצביעים בסדר הנכונה הולך להיות מאוד, מאוד חשוב לpset זה. אחרת, אתה הולך יש לי חשיש שולחן או לנסות זה פשוט הולך להיות רק חלק מהמילים שאתה רוצה ולאחר מכן "ממממ you're--? קהל: מה היה זמני דבר אחסון אתה מדבר? 1 SPEAKER: האחסון הזמני. אז בעצם עוד דרך בה אתה יכול לעשות את זה הוא לאחסן את הראש של משהו, כמו לאחסן אותו במשתנה הזמנית. להקצות אותו 1 ו לאחר מכן לעדכן 1 להצביע לכל הראש משמש להצבעה. בדרך זו היא ללא ספק אלגנטי יותר, כי אתה לא צריך ערך זמני, אבל רק מציע עוד דרך לעשות את זה. ואנחנו עושים למעשה יש קוד לזה. אז לרשימה מקושרת, אנחנו באמת יש להם קצת קוד. אז להכניס כאן, זה prepending. אז זה נכנס אליו בראש. 

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

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

קהל: האם יש לנו ל לאתחל הבא חדש ל NULL הראשון, או שאנחנו פשוט יכולים לאתחל אותו לעמוד בראש? 

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

אז יש לך כמה חשיש זה רק אות הראשונה של מינוס המחרוזת שלך, שייתן לך כמה מספר בין 0 ל -25. ומה שאתה רוצה לעשות הוא לוודא שזה מייצג בגודל של החשיש table-- כמה דליים יש. עם רבים מהם פונקציות חשיש, הם הולך להיות חוזר ערכים שאולי יהיה הרבה מעל למספר הסלים כי בעצם יש לך בטבלת החשיש שלך, כך שאתה צריך לעשות בטוח ומשרד ביטחון על ידי אלה. אחרת, זה הולך לומר, הו, זה צריך להיות בדלי 5,000 אבל יש לך רק 30 דליים בטבלת החשיש שלך. וכמובן, כולנו יודעים שזה הולך לגרום כמה טעויות מטורפות. כדי לוודא mod על ידי גודל טבלת החשיש שלך. מגניב. אז התנגשויות. האם כולם טוב עד כה? "ממממ? 

קהל: למה שיהיה את זה להחזיר ערך כזה גדול? 

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

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

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

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

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

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

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

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

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

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

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

אז כולם בסדר שם? בְּסֵדֶר. אה. מה בדיוק קרה? ממש עכשיו. מניח שמישהו הורג אותי. 

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

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

קהל: זה לעץ אחזור. 

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

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

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

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

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

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

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

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

1 SPEAKER: אתה עדיין צריך אותם. 

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

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

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

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

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

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

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

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

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

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

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

קהל: האם זה סטנדרטי יש ש כמדד 0 ולאחר מכן יש סוג ב 1 או שיש בסופו של הדבר? 

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

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

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

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

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

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

קהל: אז עושה את זה אומר כי "תואר ראשון" היא גם מילה? 

SPEAKER 1: מס ' אז במקרה הזה, היינו מקבל "תואר ראשון" כאן, היינו אומר שזה מילה, וזה עדיין יהיה לא. בסדר? "ממממ? 

קהל: אז ברגע שאתה הוא זה מילה ואתה אומר כן, אז זה יכיל ללכת למ '? 

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

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

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

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

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

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

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

קהל: חכה, אז יש לך 26 אותיות בכל אחד ואחד? 

1 SPEAKER: "ממממ. כן, יש לך 26. יש לך קצת הוא מילת סמן ולאחר מכן יש לך 26 מצביעים בכל אחד. והם point-- 

קהל: ובכל 26, יש להם כל 26? 

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

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

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

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

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

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

קהל: מקס שני עלים. 

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

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

רשימות מקושרות: קהל 

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

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

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

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

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

קהל: האחרון נכנס, ראשון יוצא. 

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

קהל: הראשון. 

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

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

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

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

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

קהל: האם זה אומר שאנחנו היה מכריז על מערך ש היה ארוך חמישה אלמנטים ו אז אנחנו מוסיפים על זה? 

SPEAKER 1: מס ' אז במקרה הזה, מדובר בערימה. זה יוכרז כמערך של גודל 6. ובמקרה הזה, אנחנו רק השאיר חלל אחד. 

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

קהל: לדוגמא ש, כך הזנב החדש הוא ב 0 על זה? 1 SPEAKER: כן. קהל: אישור. אז עובר, שיהיה לך or-- 1 ועוד 4 

1 SPEAKER: אז אתה אומר, כאשר אנחנו רוצים ללכת לעשות את זה שוב? קהל: כן. לכן, אם היו להבין out-- איפה אתה חישוב הזנב בזה? 

1 SPEAKER: אז הזנב היה in-- אני שיניתי את השם. ולכן בדוגמא כאן, זה היה המערך אנחנו מסתכלים, בסדר? אז יש לנו דברים ב1, 2, 3, ו -4. אז יש לנו הראש שלנו הוא שווה ל 1 ב נקודה זו, והגודל שלנו שווה ל -4 בשלב זה, נכון? 

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

קהל: מה כובע? 

1 SPEAKER: היכולת. מצטער. כך שהוא בגודל של המערך שלך. כן? 

קהל: [לא ברור] לפני אנו חוזרים האלמנט? 

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

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

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

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

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

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

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

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

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

קהל: אמרת קודם ש אנו יכולים להשתמש בפונקציות חשיש אחרות, כי אנחנו לא צריכים ליצור פונקצית חשיש? 

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

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

קהל: האם לנסות להיות או יעיל אך פשוט יותר קשה ל, like-- 

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

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

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

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

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

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