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

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

תלמיד: [לא ברור]. 

רמקול 1: מה זה? 

תלמיד: [לא ברור]. 

רמקול 1: גודל קבוע. בסדר, אז למה הוא גודל קבוע אם כי טוב? 

תלמיד: [לא ברור]. 

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

מה צד אחר של את מערך? כן? 

תלמיד: [לא ברור]. 

1 רמקול: כל - הסליחה? 

תלמיד: [לא ברור]. 

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

תלמיד: [לא ברור]. 

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

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

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

תלמיד: [לא ברור]. 

רמקול 1: מה זה? 

תלמיד: [לא ברור]. 

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

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

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

תלמיד: [לא ברור]. 

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

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

תלמיד: [לא ברור]. 

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

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

אז החסרון, ואז, רשימה מקושרת היא מה? מה מחיר שאנחנו כנראה משלם? 

תלמיד: [לא ברור]. 

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

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

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

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

תלמיד: [לא ברור]. 

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

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

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

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

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

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

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

תלמיד: [לא ברור]. 

1 רמקול: כן אז זה קובץ מקומי. אז אם זה קובץ מקומי שלך כאן בקו 15, למשל, אתה משתמש את המרכאות הכפולות במקום מסוגר הזווית. 

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

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

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

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

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

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

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

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

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

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

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

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

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

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

תלמיד: [לא ברור]. 

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

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

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

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

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

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

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

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

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

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

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

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

תלמיד: [לא ברור]. 

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

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

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

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

תלמיד: בן. 

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

תלמיד: ג'ייסון. 

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

תלמיד: ג'יל. 

רמקול 1: ג'יל, אתה הולך להיות 17, שאם הייתי עושה את זה יותר בתבונה, הייתי לי התחיל בקצה השני. אתה הולך בדרך. 22. ואתה? 

תלמיד: מרי. 

רמקול 1: מרי, תהיה 22. והשם שלך הוא? 

תלמיד: כריס. 

1 רמקול: כריס, תהיה 26. ואז לבסוף. 

תלמיד: דיאנה. 

1 רמקול: דיאנה, תהיה 34. אז אתה בא לכאן ב. 

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

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

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

תלמיד: בריאן. 

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

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

תלמיד: ג'ייסון. 

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

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

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

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

מי מקבל הצביע על מי? 

תלמיד: [לא ברור]. 

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

תלמיד: [לא ברור]. 

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

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

תלמיד: [לא ברור]. 

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

תלמיד: דיאנה. 

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

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

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

תלמיד: [לא ברור]. 

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

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

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

תלמיד: [לא ברור]. 

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

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

תלמיד: [לא ברור]. 

1 דובר: סליחה? 

תלמיד: [לא ברור]. 

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

אז אנחנו יכולים לעשות 17 מצביעים על 20. אז זה בסדר. לאן אנחנו רוצים להצביע המצביע שלך עכשיו? בגיל 22. ואנחנו יודעים איפה הוא 22, שוב תודה למצביע הזמני שלי. אז אנחנו בסדר שם. אז בגלל זה אחסון זמני אני כל הזמן אחר שבו כולם. ועכשיו לך מבחינה ויזואלית יכול להיכנס לשם אתה שייך, ועכשיו אנחנו צריכים 1, 2, 3, 4, 5, 6, 7, 8, 9 כדורי לחץ, ומחיאות כפות ל החבר 'ה האלה, אם אנחנו יכולים. יפה עשה. 

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

תלמיד: [לא ברור]. 

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

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

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

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

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

אז בחדר של n CS50 תלמידים, מה ההסתברות שלפחות שני סטודנטים בחדר יש לו יום ההולדת? אז מה יש. כמה הונט - 200, 300 אנשים פה וכמה מאה אנשים בבית היום. אז אם אתם רוצים לשאול את עצמנו מה ההסתברות של שני אנשים בחדר הזה שיש באותו יום הולדת, אנחנו יכולים להבין את זה. ואני טוען שלמעשה יש שתיים אנשים עם אותו יום ההולדת. 

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

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

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

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

והאוכל המוכן מעקומה זו הוא כי ברגע שאתה מקבל לחן 40 סטודנטים, אתה למעלה בהסתברות 90% combinatorically של שתיים אנשים או יותר שיש באותו יום ההולדת. וברגע שאתה מקבל 58 אנשים אוהבים את זה כמעט 100% מסיכוי שתיים אנשים בחדר הולכים להיות אותו יום הולדת, למרות שיש 365 או 366 דליים אפשריים, ו רק 58 אנשים בחדר. פשוט סטטיסטי אתה צפוי לקבל התנגשויות, אשר בקיצור מניע את הדיון הזה. כי גם אם אנחנו מקבלים כאן מפוארים, ו הפעלה שיש רשתות אלה, אנחנו עדיין הולך להיות התנגשויות. 

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

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

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

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

תלמיד: [לא ברור]. 

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

תלמיד: [לא ברור]. 

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

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

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

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

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

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

תלמיד: [לא ברור]. 

רמקול 1: בצד השמאל. אז מה מעניין עם נתונים אלה מבנה הוא לא חנות מחרוזת M-X--W-E-L-L קו נטוי אפס, כל סמיכות, מה שאתה עושה במקום עוקב אחרי. אם זה trie כמו מבנה נתונים, כל אחד מצומת שלהם הוא שוב מערך, ואתה רוצה לאחסן את מקסוול, אתה ראשון מדד וכן הצומת של השורש, ולכן לדבר, הצומת העליונה ביותר, במיקום M, נכון, ולכן בערך באמצע. ואז משם, אתה מבין מצביע לבלוטות ילד, כביכול. אז במובן עץ המשפחה, אתה מבין את זה כלפי מטה. וזה יוביל אותך לצומת אחרת בצד השמאל יש, שהוא רק עוד מערך. 

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

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

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

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

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

תלמיד: [לא ברור]. 

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

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

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

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

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

[השמעת וידאו] 

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

[השמעת וידאו הסוף] 

1 רמקול: ככה האינטרנט יפעל החל מהשבוע הבא.