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

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

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

קהל: בודק זה לדליפות זיכרון? 

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

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

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

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

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

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

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

קהל: לכו לצומת ו להעריך את ערך n עבורו. 

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

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

ג'ייסון הירשהורן: אז זה לא ליצור צומת חדשה. זה יוצר את מה? 

קהל: מצביע. 

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

קהל: צומת חדשה? 

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

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

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

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

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

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

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

קהל: התקשר למצביע לצומת הבאה. 

ג'ייסון הירשהורן: ולמה לעשות אנחנו הולכים לצד אחד? 

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

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

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

קהל: שש גדול מחמישה. 

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

קהל: שני. 

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

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

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

קהל: זה מקל על תחילת או הסוף. 

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

קהל: בגלל ההתחלה הוא כבר מלא. 

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

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

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

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

קהל: בתמורת שווא? 

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

קהל: כן. כן. 

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

קהל: אה, סליחה. אנחנו צריכים malloc מרחב לצומת. 

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

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

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

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

קהל: לשחרר אותו. 

ג'ייסון הירשהורן: כן. כנראה לשחרר אותו. על אישור. מה עושה אחרי ש ליצור צומת חדשה? אנני? 

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

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

קהל: אנחנו נעבור על הרשימה. 

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

קהל: בדוק אם ערך n של הצומת שהיא גדולה מערך n של הצומת שלנו. 

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

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

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

קהל: ואז אתה פשוט להמשיך אלא אם כן זה האחרון. 

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

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

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

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

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

קהל: - תנאי ערך? 

ג'ייסון הירשהורן: איזה אחד במיוחד? 

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

ג'ייסון הירשהורן: אז אם הערך שלנו הוא גדול מהערך של הצומת הזה. 

קהל: כן, אז היית רוצה ללכת בהמשך הקו, נכון? 

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

קהל: חכה, שהוא זה צומת ובה היא ערך? 

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

קהל: אם הערך גדול מצומת זה. 

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

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

על אישור. בואו נתחיל. אסם, איך אנו יוצרים צומת חדש? 

קהל: אתה struct *. 

ג'ייסון הירשהורן: אז אנחנו יש שעד כאן. אה, סליחה. אתה אומר struct *. 

קהל: ואז [? סוג?] צומת או צומת ג. 

ג'ייסון הירשהורן: אישור. אני הולך לקרוא לזה new_node כדי שנוכל להישאר עקבי. 

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

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

קהל: הגודל של struct. 

ג'ייסון הירשהורן: גודל של struct. ומה שנקרא struct? 

קהל: צומת? 

ג'ייסון הירשהורן: צומת. אז malloc (sizeof (צומת)); נותן לנו מרחב. והאם הקו הזה - דבר אחד אינו נכון בקו הזה. האם new_node מצביע למבנה? זה שם גנרי. מה זה - צומת, בדיוק. זה צומת *. ומה עושים מייד אחרי אנו malloc משהו, אסאן? מה הדבר הראשון שאנחנו עושים? מה אם זה לא עובד? 

קהל: אה, לבדוק אם זה מצביע לצומת? 

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

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

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

קהל: הערך שלהם ברשימה שלנו. 

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

קהל: האם זה לא עבר לפונקציה? 

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

קהל: רשימה. 

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

קהל: רשימה מינוס אחד? 

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

קהל: Null. 

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

קהל: עד שיגיעו ריק. 

ג'ייסון הירשהורן: אישור. אז אם, ואילו, ללולאה. מה אנחנו עושים? 

קהל: אולי ללולאה? 

ג'ייסון הירשהורן: בואו לעשות ללולאה. על אישור. 

קהל: ואנחנו אומרים ל-- עד שהמצביע הנוכחי אינו שווה לריק. 

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

קהל: בעוד. 

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

קהל: אם הנוכחי>-n n פחות מהערך. או להפוך את זה. לעבור סוגר זה. 

ג'ייסון הירשהורן: מצטער. 

קהל: שנה את הסוגר. 

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

קהל: האם זה עדיין? 

ג'ייסון הירשהורן: כן. 

קהל: אתה - new_node-> הבא. 

ג'ייסון הירשהורן: אז מה שהולך להיות שווה? 

קהל: זה הולך הנוכחי שווה. 

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

קהל: בדוק אם בעבר שווה אפס. 

ג'ייסון הירשהורן: אם קודם - כך שאם קודם שווה אפס. 

קהל: זה אומר שזה הולך כדי להפוך את הראש. 

ג'ייסון הירשהורן: אמצעי זה זה נהיה הראש. אז מה אנחנו עושים? 

קהל: אנו עושים בראש שווה new_node. 

ג'ייסון הירשהורן: ראש שווה new_node. ולמה בראש כאן, לא יפרט? 

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

ג'ייסון הירשהורן: מתוק. על אישור. ו-- 

קהל: ואז אתה אחר prev-> הבא שווה new_node. ואז אתה חוזר נכון. 

ג'ייסון הירשהורן: לאן אנו קובעים סוף new_node? 

קהל: הייתי - אני מגדיר את זה בהתחלה. 

ג'ייסון הירשהורן: אז מה קו? 

קהל: אחרי אם הצהרה בודק אם זה ידוע. 

ג'ייסון הירשהורן: ממש כאן? 

קהל: הייתי עושה new_node-> n שווה ערך. 

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

קהל: אם הערך גדול מ curr-> n - 

ג'ייסון הירשהורן: איך לעשות אנחנו הולכים לקשר הבא? 

קהל: Curr-> n הוא שווה new_node. 

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

קהל: אה, הבא. 

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

קהל: המצביעים. 

ג'ייסון הירשהורן: אז אנו מעודכנים הנוכחיים. 

קהל: קודם-> הבא. 

ג'ייסון הירשהורן: כן. OK, נשהה. מי יכול לעזור לנו כאן? מנו, מה עלינו לעשות? 

קהל: אתה חייב להגדיר זה שווה לcurr-> הבא. אבל לעשות את זה לפני הקו הקודם. 

ג'ייסון הירשהורן: אישור. כל דבר אחר? Akshar. 

קהל: אני לא חושב שאתה נועד לשנות curr-> הבא. אני חושב שאתה אמור לעשות שווים curr curr-> הבא ללכת לצומת הבאה. 

ג'ייסון הירשהורן: אז מצטער, שבו? על מה קו? קו זה? 

קהל: כן. הפוך curr שווה curr-> הבא. 

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

קהל: קודם-> הבא שווה curr. 

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

קהל: זה יהיה רק ​​את קודם. 

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

קהל: אם הערך הוא שווה curr-> n. 

ג'ייסון הירשהורן: מצטער. אלוהים אדירים. מה? ערך == curr-> n. מה אנחנו עושים? 

קהל: היית לשחרר new_node שלנו, ואז היית בתמורת שווא. 

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

קהל: האם אתה אמור לשים את התמורה אמיתי מחוץ ללולאה בזמן? 

ג'ייסון הירשהורן: אני לא יודע. האם אתה רוצה שאני? 

קהל: לא משנה. לא. 

ג'ייסון הירשהורן: Akshar? 

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

ג'ייסון הירשהורן: אז איפה אתה רוצה שזה ילך? 

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

ג'ייסון הירשהורן: אישור. אז מה אנחנו עושים כאן? 

קהל: אתה בתמורת שווא גם שם. 

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

קהל: כן. 

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

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

קהל: לא הזכיר - אתה לא אומר את זה בראש, זה היה אותחל לאפס בהתחלה. אבל חשבתי שאמרת שזה היה בסדר. 

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

קהל: אה, הוא מת. 

ג'ייסון הירשהורן: אני רק משך אותו החוצה. על אישור. 

קהל: אולי זה קצה שני של החוט. 

ג'ייסון הירשהורן: וואו. אז השורה התחתונה - מה אמר? 

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

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

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

קהל: מה? 

ג'ייסון הירשהורן: פקודת GDB מה אני משתמש כדי להיכנס פנימה בפונקציה זו? 

קהל: שלב? 

ג'ייסון הירשהורן: שלב באמצעות ס 'זה לוקח אותי פנימה. על אישור. New_node mallocing קצת מרחב. כי הכל נראה כמו שלה הולך. הבה נבחן new_node. זה יש לי כמה כתובת זיכרון. בואו לבדוק - זה כל מה נכון. אז הכל כאן נראה לעבוד בצורה נכונה. 

קהל: מה ההבדל בין P ותצוגה? 

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

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

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

קהל: לא. 

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

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

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

ג'ייסון הירשהורן: אישור. האם זה יפתור את הבעיה שלנו, אם כי? 

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

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

קהל: אם אתה כבר קיבלת את הצומת malloced, אתה יכול פשוט להגיד new_node-> הבא שווה null משום זה חייב להיות בסוף. או new_node-> הבא שווה אפס. 

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

קהל: ראש. 

ג'ייסון הירשהורן: סליחה? 

קהל: הראש מצביע לסוף הרשימה. 

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

קהל: אני חושב שאתה לעשות הנוכחי> הבא. 

ג'ייסון הירשהורן: אישור. curr-> הבא. אז שוב, הסיבה היחידה שאנחנו למטה כאן הוא, מה עושה נוכחית שווה? 

קהל: שווה אפס. 

ג'ייסון הירשהורן: אז מה קורה אם אנחנו עושים null-> הבא? מה אנחנו הולכים לקבל? אנחנו נוציא את אשמת פילוח. 

קהל: curr האם שווה אפס. 

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

קהל: הקודם-> הבא? 

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

קהל: זה הולך לחזור שקר במקרה זה? 

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

קהל: האם קודם עדיין שווה null בחלק העליון של הרשימה? 

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

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

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

קהל: אז אם את הראש שווה שווה אפס. 

ג'ייסון הירשהורן: אם ראש שווה שווה null - שיגיד לנו אם זה רשימה ריקה. 

קהל: ואז אתה לעשות ראש שווה חדש. 

ג'ייסון הירשהורן: ראש שווה new_node? ומה עוד אנחנו צריכים לעשות? 

קהל: ואז אתה חוזר נכון. 

ג'ייסון הירשהורן: לא ממש. חסרים לנו עוד צעד אחד. 

קהל: New_node הבא יש להצביע על NULL. 

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

קהל: כן. 

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

קהל: לא. 

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

על אישור. תן לנו להפעיל את התכנית שוב. לא מוצלח. 

קהל: אתה לא עושה את זה. 

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

קהל: זה חייב להיות לריק. 

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

קהל: שבע. 

ג'ייסון הירשהורן: שבע? 

קהל: כן. 

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

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

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

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

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

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

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

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

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

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

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

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

קהל: זה יכול למצוא את מדד בזמן קבוע? 

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

קהל: זה יכול להיות ממופה רק מפתח למקום אחד בטבלת הגיבוב. 

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

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

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

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

קהל: אפס. 

ג'ייסון הירשהורן: למה אפס? 

קהל: בגלל שלוש מודולו שלוש הוא אפס? 

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

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

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

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

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

קהל: סוכריות. 

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

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

ג'ייסון הירשהורן: אז אנחנו הולכים לצייר את הרעיון הטוב כאן. על אישור. 

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

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

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

קהל: מצביעים ל-- 

ג'ייסון הירשהורן: מכיוון שאתה אמרה רשימה מקושרת, ולכן - 

קהל: מצביעי צומת? 

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

קהל: Null. 

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

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

ג'ייסון הירשהורן: כן. ובכן, יש לנו דלעת. בואו לקבל את הראשון שלנו. יש לנו את הדלעת. 

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

ג'ייסון הירשהורן: איך אנחנו לשים אותו ברשימה המקושרת? 

קהל: אה, את התחביר בפועל? 

ג'ייסון הירשהורן: פשוט ללכת - לומר יותר. מה אנחנו עושים? 

קהל: אתה פשוט להכניס אותה כצומת הראשונה. 

ג'ייסון הירשהורן: אישור. אז יש לנו הצומת, הדלעת שלנו. ועכשיו איך אני מכניס את זה? 

קהל: אתה להקצות אותו למצביע. 

ג'ייסון הירשהורן: איזה מצביע? 

קהל: המצביע על אפס. 

ג'ייסון הירשהורן: אז איפה עושה את הנקודה הזו? 

קהל: כדי null עכשיו. 

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

קהל: לדלעת. 

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

קהל: Null. 

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

קהל: זה תלוי אם לא שאנחנו מנסים למיין את זה. 

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

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

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

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

ג'ייסון הירשהורן: כמו זה? ואומר שיש לנו עוד דבר למפה לאפס? 

קהל: ובכן, אתה פשוט לעשות את אותו הדבר? 

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

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

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

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

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

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

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

ג'ייסון הירשהורן: ליניארי תכנות, אין רשימות מקושרות. המקום הבא בטבלת הגיבוב. 

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

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

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

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

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

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

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