[Powered by Google Translate] [שבוע 6, המשך] [הדוד י מלאן] [אוניברסיטת הרווארד] [זה CS50.] [CS50.TV] זה CS50 וזה סוף השבוע 6. אז CS50x, אחד הקורסים הראשונים של הרווארד המעורבים ביוזמת edx אכן זו לראשונה שלשום. אם אתם רוצים לקבל צצה לאחרים מה באינטרנט כעת עוקבים יחד עם, אתם יכולים לגשת לx.cs50.net. שיפנה אותך למקום המתאים בedx.org, שהיה שם זה וקורסים נוספים מ-MIT וברקלי חי כיום. תצטרך להירשם לחשבון, תמצאו שהחומר הוא במידה רבה באותה כפי שהיה לך בסמסטר הזה, אם כי כמה שבועות עוכבו, כפי שאנו מקבלים הכל מוכן. אבל מה תלמידים בCS50x כעת לראות הוא ממשק ממש כמו זה. זו, למשל, היא Zamyla מוביל את ההדרכה לקבוצת הבעיה 0. עם כניסתך לedx.org, סטודנט CS50x רואה את מיני דברים שהיית מצפה לראות בקורס: ההרצאה ליום שני, הרצאה ליום רביעי, מכנסים שונים, סט הבעיה, ליין, קבצי PDF. בנוסף לכך, כפי שאתה רואה כאן, תרגומי מכונית מתעתיקים האנגלים לסיני, יפני, ספרדית, איטלקי, וכל חבורה של שפות אחרות שבהחלט תהיה מושלם כפי שאנו לגלגל אותם החוצה תכנותיים באמצעות משהו שנקרא API, או ממשק תכנות יישומים, מ-Google שמאפשר לנו להמיר אנגלית לשפות אחרות אלה. אך הודות לרוח הנפלאה של חלק ממתנדבים 100 ויותר, אנשים אקראיים באינטרנט שמוצעים בחביבות להסתבך בפרויקט זה, אנחנו בהדרגה להיות שיפור האיכות של התרגומים האלה על ידי כך בני אדם לתקן את הטעויות שהמחשבים שלנו עשו. 

אז מתברר שיש לנו עוד כמה סטודנטים יגיעו ביום שני ממה שציפינו בתחילה. למעשה, עכשיו CS50x יש 100.000 אנשים הבאים יחד בבית. אז מבין שהם החלק ממעמד ההשבעה הזה של עשיית קורס זה במדע המחשב חינוך באופן כללי יותר, באופן רחב יותר, נגיש. והמציאות היא עכשיו, עם חלק מהקורסים מקוונים המסיביים אלה, כולם מתחילים עם מספרים אלה גבוהים מאוד, כפי שנראה שנעשה כאן. אבל המטרה, בסופו, לCS50x היא באמת להגיע כמה שיותר אנשים אל קו הסיום כמה שאפשר. על פי תכנון, CS50x הולך להיות מוצע מיום שני האחרון לאורך כל הדרך 15 אפריל 2013, כך שאנשים שיש להם מחויבויות לבית הספר במקום אחר, עבודה, משפחה, סכסוכים אחרים וכדומה, יש קצת יותר גמישות עם שלצלול לקורס זה, ש, די אם נאמר, נעשה די שאפתן ולו רק במשך שלושה חודשים בלבד במהלך סמסטר רגיל. אבל תלמידים אלה יהיו התמודדות עם סטיה הבעיה, צפייה באותו התוכן, יש גישה לאותם מכנסיים קצרים וכדומה. אז הבין שכולנו בעצם בזה ביחד. ואחת מהמטרות הסופיות של CS50x הוא לא רק כדי לקבל כמה שיותר אנשים אל קו הסיום ולתת להם הבנה חדשה זו של מדעי מחשב ותכנות, אבל גם שיש להם הניסיון המשותף הזה. אחד המאפיינים המגדירים של 50 בקמפוס, ואנו מקווים, היה זה סוג של חוויה קהילתית, לטוב או לרע, לפעמים, אבל יש את האנשים האלה לפנות לשמאל ולימין, ושעתי העבודה וhackathon והוגן. זה קצת קשה לעשות את זה באופן אישי עם אנשים באינטרנט, אבל CS50x יסתיים באפריל עם אי CS50 אקספו הראשון, שתהיה הסתגלות מקוונת של הרעיון ההוגן איפה אלו אלף תלמידים וכולם מוזמנים להגיש 1 - לוידאו 2-דקה, גם screencast של הפרויקט שלהם הסופי או וידאו שלהם מנופף לשלום ומדבר על הפרויקט שלהם וdemoing, בדומה לקודמים שעשו כאן בקמפוס ביריד, כך שבסופו של הסמסטר, התקווה היא שתהיה לי תערוכה עולמית של פרויקטי הגמר של סטודנטי CS50x, ממש כמו זה שמחכה לך בדצמבר הקרוב כאן בקמפוס. נוסף על כך, כי בחודשים הבאים. 

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

קורסים למדעי מחשב באוניברסיטת הרווארד יש קצת מסורת, CS50 ביניהם, שיש כמה בגדים, קצת בגדים, שאתה יכול ללבוש בגאווה בסוף הסמסטר, ואמר די בגאווה שסיימת CS50 ולקחתי CS50 וכיוצא בזה, ואנחנו תמיד מנסים לערב את התלמידים בתהליך זה עד כמה שניתן, לפיה אנחנו מזמינים, בערך בתקופה זו של הסמסטר, סטודנטים להגיש עיצובים באמצעות פוטושופ, או מה שכלי של בחירה שברצונך להשתמש אם אתה מעצב, להגיש עיצובים לחולצות וסווטשירטים ומטריות ובנדנות הקטנה לכלבים יש לנו עכשיו וכדומה. והכל אז - את הזוכים בכל שנה לאחר מכן, הציגו באתר האינטרנט של הקורס בstore.cs50.net. הכל נמכר במחיר שם, אבל האתר פשוט מתנהל מעצמו ומאפשר לאנשים לבחור את הצבעים והעיצובים שהם אוהבים. אז חשבנו שאנחנו רק רוצים לחלוק כמה מהעיצובים של השנה שעברה שהיו באתר מלבד זה שלפנינו, שהנה מסורת שנתית. "כל היום אני SEG Faultn" היה אחת מההגשות בשנה שעברה, שהוא עדיין זמין יש לבוגרים. אנחנו ראינו את זה, "CS50, נוסד 1989." אחד Bowdens, רוב, היה פופולרי מאוד בשנה שעברה. "צוות אודן" נולד, עיצוב זו הוגש, בין מוכרי הדף. כפי שהיה זה כאן. אנשים רבים הייתה "קדחת אודן" על פי יומני מכירות. מבין שזה עכשיו יכול להיות העיצוב שלך שם, עד באינטרנט. פרטים נוספים על זה בבעיה הבאה קובעים לבוא. 

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

אז הציג style50 היום השני, שהוא כלי שורת פקודה קצר שמנסה לסגנן את הקוד שלך קצת יותר נקי ממה שאתה, אנושי, עשוי לעשות. אבל גם את זה, הוא באמת רק עניין אסתטי. אבל מתברר שיש בכלי זה אחר בשם Valgrind שהוא קצת יותר מסתורי לשימוש. הפלט שלו הוא אכזרי סתום במבט הראשון. אבל זה שימושי להפליא, במיוחד עכשיו שאנחנו בחלק מהטווח איפה אתה מתחיל להשתמש malloc והקצאת זיכרון דינמית. דברים יכולים ללכת ממש ממש לא בסדר במהירות. כי אם אתה שוכח לשחרר את הזיכרון שלך, או שאתה חלק dereference מצביע NULL, או שאתה חלק dereference מצביע אשפה, מה שהוא בדרך כלל הסימפטום שתוצאות? SEG אשמה. ואתה מקבל קובץ הגרעין הזה של מספר מסוים של ק"ג או מגה המייצג את המצב של הזיכרון של התכנית שלך כאשר הוא התרסק, אבל התכנית שלך בסופו צינוק פגמים, תקלות פילוח, מה שאומר שמשהו רע קרה כמעט תמיד קשור לטעות בזיכרון שעשית במקום. אז Valgrind עוזר לך למצוא דברים כאלה. זה כלי שאתה מפעיל, כמו GDB, לאחר שצרפת את התכנית שלך, אבל במקום להריץ את התכנית שלך באופן ישיר, אתה מפעיל Valgrind ואתה עובר אליו התכנית שלך, בדיוק כמו שאתה עושה עם GDB. כעת, השימוש, כדי לקבל הסוג של פלט הטוב ביותר, הוא קצת ארוך, אז ממש שם על גבי המסך תראה Valgrind-V. "-V" כמעט אוניברסלי פירוש מפורט כאשר אתה משתמש בתוכניות במחשב לינוקס. אז זה אומר לירוק יותר נתונים ממה שהיית כברירת מחדל. "- דליפה לבדוק = מלא". זה רק אומר סימון עבור כל דליפות הזיכרון האפשריות, טעויות שאולי עשיתי. גם זה, הוא פרדיגמה משותפת עם תוכניות לינוקס. באופן כללי, אם יש לך טיעון שורת פקודה זה "בורר", זה אמור לשנות את ההתנהגות של התכנית, וזה אות אחת, זה-V, אבל אם זה יעבור, רק על ידי עיצוב של המתכנת, הוא מילה או סדרה מלאה של מילים, ויכוח שורת הפקודה מתחיל עם -. אלה הם רק מוסכמות אדם, אבל אתה רואה אותם יותר ויותר. ואז, סוף סוף, "a.out" הוא שם השרירותי לתכנית בדוגמה זו בפרט. והנה כמה פלט נציג. 

לפני שאנחנו מסתכלים על מה שאולי אומרים, בואו נעבור עליי לקטע של קוד כאן. ולתת לי לזוז מזה של הדרך, בקרוב, ובואו נסתכל memory.c, שהוא דוגמה קצרה זה כאן. אז בתכנית זו, תן לי להתקרב בפונקציות ובשאלות. יש לנו פונקציה עיקרית שקוראה לפונקציה, f, ואז מה f אין להמשיך לעשות, באנגלית הטכנית במקצת? מה f אין להמשיך לעשות? מה דעתך על אני אתחיל עם קו 20, ואת מיקומו של הכוכב לא משנה, אבל אני פשוט אהיה עקבי כאן עם ההרצאה אחרונה. מה אין קו 20 בשבילנו? בצד השמאל. אנחנו נשבור אותו עוד יותר למטה. Int * x: מה זה עושה? אוקיי. זה הכרזת מצביע, ועכשיו בואו אהיה גם יותר טכני. מה זה אומר, מאוד קונקרטי, להכריז על מצביע? מישהו אחר? כן? [תשובת סטודנט, לא מובן] יותר מדי רחוק. אז אתה קורא לצד הימני של סימן השוויון. בואו נתמקד רק בצד השמאל, רק על int x *. זה "להצהיר" מצביע, אבל עכשיו בואו לצלול עמוק יותר להגדרה הזאת. מה זה קונקרטי, מבחינה טכנית אומר? כן? [תשובת סטודנט, לא מובן] אוקיי. זה הכנה לשמירת כתובת בזיכרון. טוב. ובואו ניקח את זה צעד אחד קדימה; הוא מכריז על משתנה, x, זה 32 סיביים. ואני יודע שזה 32 סיבי בגלל -? זה לא בגלל שזה int, כי זה מצביע במקרה זה. צירוף מקרים שזה אחד ואותו הדבר עם int, אבל העובדה שיש שם פירושו כוכב זה הוא מצביע ובמכשיר, כמו במחשבים רבים, אך לא כולם, מצביעים הם 32 סיביים. על חומרה מודרנית יותר כמו מקינטוש האחרון, את המחשבים החדישים ביותר, שאולי יש לי מצביעים 64-bit, אבל במכשיר, הדברים האלה הם 32 סיביים. כך יהיו לנו סטנדרטיזציה על זה. באופן קונקרטי יותר, הסיפור הולך כך: אנחנו "להכריז" מצביע, מה זה אומר? אנחנו מכינים לאחסון כתובת זיכרון. מה זה אומר? אנו יוצרים משתנים בשם x שתופס 32 סיביים כי בקרוב יהיה לאחסן את הכתובת של מספר שלם. וזהו ככל הנראה על מדויקים כמו שאנחנו יכולים לקבל. זה בסדר נע קדימה על מנת לפשט את העולם, ורק אומרים להכריז מצביע נקרא x. להכריז מצביע, אך מבין ולהבין מה באמת קורה אפילו במרחק של רק כמה תווים אלה. 

עכשיו, זה כמעט קצת יותר קל, למרות שזה ביטוי ארוך יותר. אז מה זה עושה, שמודגש עכשיו: "malloc (10 * sizeof (int));" כן? [תשובת סטודנט, לא מובן] טוב. ואני אקח אותה לשם. זה הקצאת נתח הזיכרון עבור 10 מספרים שלמים. ועכשיו בואו לצלול קצת יותר עמוק; זה הקצאת נתח הזיכרון עבור 10 מספרים שלמים. מה malloc אז חוזר? הכתובת של נתח, או, באופן קונקרטי יותר, את הכתובת של הבית הראשון של שהנתח. אז איך אני, המתכנת, לדעת היכן שמסתיים נתח של הזיכרון? אני יודע שזה רציף. Malloc, מעצם הגדרתו, ייתן לך נתח רציף של זיכרון. אין פערים בזה. יש לך גישה לכל בתים שבגוש, גב אל גב אל גב, אבל איך אני יודע איפה סוף הנתח זה של זיכרון הוא? כאשר אתה משתמש malloc? [תשובת סטודנט, לא מובן] טוב. אתה לא יודע. צריכים לזכור. אני צריך לזכור שהייתי הערך 10, ואני אפילו לא נראה לי שעשיתי כאן. אבל את האחריות היא כולה עליי. Strlen, שנהיינו קצת סומך על למייתרים, עובד רק בגלל מוסכמות זה שיש \ 0 או התו המיוחד הזה NUL, NUL, בסוף המחרוזת. שאינו מחזיק בנתחים שרירותיים רק של זיכרון. זה תלוי בך. אז קו 20, ולאחר מכן, מקצה נתח של זיכרון שיכול לאחסן 10 מספרים שלמים, והוא מאחסן את הכתובת של הבית הראשון שהנתח של הזיכרון בx משתנה בשם. מכאן, שהוא מצביע. אז 21 קו, למרבה הצער, הייתה טעות. אבל קודם, מה הוא עושה? זה אומר חנות במיקום 10, 0 אינדקס, מגוש הזיכרון נקרא x הערך 0. 

אז שם לב כמה דברים קורים. למרות x הוא מצביע, זוכר מלפני שבועות שאתה עדיין יכול להשתמש בסימון סוגר מרובע מערך בסגנון. כי זה בעצם סימון קצר יד לפעולות אריתמטיות על המצביעים מסתוריים למראה יותר. שבו אנחנו היו עושים משהו כזה: קח x הכתובת, העבר את 10 מקומות מעל, אז הולך לשם כדי שינה את הכתובה מאוחסנת באותו מקום. אבל בכנות, זה פשוט זוועה לקרוא ולהרגיש בנוח עם. אז העולם בדרך כלל משתמש בסוגריים המרובעים רק בגלל שזה כל כך הרבה יותר ידידותי לאדם לקריאה. אבל זה מה שבאמת קורה מתחת למכסת המנוע; x הוא כתובת, לא מערך, כשלעצמה. אז זה אחסון 0 במיקום 10 בx. למה זה רע? כן? [תשובת סטודנט, לא מובן] בדיוק. אנו הוקצינו רק 10 ints, אבל אנחנו סופרים מ0 כאשר תכנות ב-C, אז יש לך גישה ל0 1 2 3 4 5 6 7 8 9, אבל לא 10. אז או שהתכנית הולכת אשמת צינוק או שזה לא. אבל אנחנו לא ממש יודעים, זה סוג של התנהגות לא דטרמיניסטית. זה באמת תלוי בשאלות אם נהיה לנו מזל. אם אתברר שמערכת ההפעלה לא אכפת לי אם אני משתמש שבבתים נוספים, למרות שזה לא נתן לי את זה, התכנית שלי לא יכולה לקרוס. זה גולמי, זה עגלה, אבל ייתכן שלא תראו שסימפטום, או שאתה יכול לראות את זה רק פעם אחת בכמה זמן. אבל המציאות היא שהבאג הוא, למעשה, יש. וזה באמת בעייתי אם אתה כתבת תכנית שאתה רוצה להיות נכון, שמכרת את התכנית שהאנשים משתמשים שבכל פעם מתרסקת כי, כמובן, זה לא טוב. למעשה, אם יש לך טלפון אנדרואיד או iPhone ואתה מוריד אפליקציות בימים אלה, אם אי פעם היה לי אפליקציה פשוט להפסיק, פתאום הוא נעלם, זה כמעט תמיד נבע מהסיבה הקשורה לנושא זיכרון, לפי המתכנת דפוק וdereferenced מצביע שהוא או היא לא הייתה צריכה, והתוצאה של iOS או אנדרואיד הוא רק כדי להרוג את התכנית לגמרי ולא התנהגות בלתי מוגדרת סיכון או איזה סוג של פשרת אבטחה. 

יש באג אחד אחר בתכנית זו מלבד זה. מה עוד יש לי דפוק בתכנית זו? אני כבר לא התאמנתי מה שהטפתי לו. כן? [תשובת סטודנט, לא מובן] טוב. אני עדיין לא שחררתי את הזיכרון. אז כלל האצבע עכשיו צריך להיות בכל העת שאתה קורא malloc, עליך להתקשר חינם כאשר אתה עשית שימוש בזיכרון זה. עכשיו, כשאני הייתי רוצה לשחרר את הזיכרון הזה? כנראה, בהנחת הקו הראשון זה היה נכון, לא הייתי רוצה לעשות את זה כאן. כי אני לא יכול, למשל, לעשות את זה כאן. למה? רק מחוץ לתחום. אז למרות שאנחנו מדברים על מצביעים, זה שבוע 2 או 3 בעיה, כאשר x הוא רק בהיקפה הפנימי של הסוגריים המסולסלים שבו הוכרז. אז אתה בהחלט לא יכול לשחרר אותו שם. הסיכוי היחיד שלי כדי לשחרר אותו הוא בערך אחרי 21 שורות. זוהי תכנית פשוטה למדי, זה היה די קל ברגע שאתה סוג של עטף את דעתך סביב מה התכנית עושה, שבו היו טעויות. וגם אם אתה לא רואה את זה בהתחלה, אני מקווה שזה קצת ברור עכשיו שהטעויות האלה נפתרות די בקלות ועשויה בקלות. אך כאשר תכנית היא ארוך יותר מ 12 קווים, זה עוד 50 קווים, 100 קווים ארוך, הליכה בקו הקוד שלך על ידי קו מחשבה המעמיקה על כל זה בהיגיון, אפשרי אבל לא במיוחד כיף לעשות, כל זמן מחפש באגים, וזה גם קשה לעשות, וזו הסיבה שכלי כמו Valgrind קיים. תן לי ללכת קדימה ולעשות את זה: תן לי לפתוח את חלון המסוף שלי, והרשו לי לא פשוט להפעיל זיכרון, כי זיכרון נראה בסדר. אני מקבל מזל. הולכים לבתים נוספים בסוף המערך לא נראה לי בעייתי מדי. אבל תרשה לי, בכל זאת, לעשות בדיקת שפיות, שרק אומר שכדי לבדוק אם זה הוא למעשה נכון. 

אז בואו נעשיתי valgrind-v - דליפה לבדוק = מלא, ולאחר מכן את שמה של התכנית במקרה זה הוא זיכרון, לא a.out. אז תן לי ללכת קדימה ולעשות את זה. על Enter. אלוהים יקר. זה הפלט שלה, וזה מה שנאמרתי קודם לכן. אבל, אם אתה לומד לקרוא בדרך את כל השטויות כאן, ביותר לכך הוא פשוט פלט אבחון זה לא כל כך מעניין. מה העיניים שלך באמת רוצות להיות מחפשות הוא כל אזכור של טעות או לא חוקי. מילים המרמזות על בעיות. ואכן, בואו לראות מה השתבש כאן למטה. יש לי סיכום כלשהו, ​​"בשימוש ביציאה:. 40 בתים ב1 רחובות" אני לא ממש בטוח מה הוא בלוק, אבל 40 בתים ממש מרגיש כאילו אני יכול להבין מהאיפה זה מגיע. 40 בתים. למה הם 40 בתים בשימוש ביציאה? ולייתר דיוק, אם אנחנו לגלול למטה כאן, לכן אני בהחלט אבדתי 40 בתים? כן? [תשובת סטודנט, לא מובן] מושלם. כן, בדיוק. היו עשרה מספרים שלמים, וכל אחד מאלה הם גודל של 4, או 32 סיביים, כך אבדתי בדיוק 40 בתים, כי, כפי שההצעה, לא נקרא חופשי. זה באג אחד, ועכשיו בואו נסתכל למטה עוד קצת ולראות לצד זה, "לא חוקי לכתוב בגודל 4". מה קורה פה? כתובת זו בטאה את מה שתיווי בסיס, כנראה? זה הקסדצימלי, וכל פעם שאתה רואה את מספר התחלה עם 0x, זה אומר ההקסדצימלי, כפי שאכן עשה בדרך חזרה, אני חושב, קטע של 0 pset של שאלות, שהיה רק ​​כדי לעשות את תרגיל חימום, המרה עשרונית לקסדצימלי לינארי וכך הלאה. הקסדצימלי, פשוט על ידי כינוס אנושי, משמש בדרך כלל כדי לייצג את המצביעים או, באופן כללי יותר, מתייחס. זה פשוט כנס, כי זה קצת יותר קל לקריאה, זה קצת יותר קומפקטי מאשר משהו כמו עשרוני, ובינארי הוא חסר תועלת עבור רוב בני האדם לשימוש. אז עכשיו מה זה אומר? ובכן, זה נראה כאילו יש כתיבה לא חוקית בגודל 4 על 21 קו memory.c. אז בואו נחזור לקו 21, ואכן, כאן היא שכתיבה לא חוקית. אז Valgrind לא הולך להחזיק לחלוטין ידי ואומר לי מה הוא התיקון, אבל זה הוא גילוי שאני עושה לכתוב חוקי. אני נוגע בי 4 בתים שאני לא צריך להיות, וכנראה שזה בגלל, כפי שציינת, אני עושה [10] במקום [9] מקסימאלי או [0] או משהו באמצע. עם Valgrind, מבין כל זמן עכשיו אתה כותב תכנית המשתמש במצביעים ומשתמש בזיכרון, וmalloc לייתר דיוק, בהחלט להיכנס להרגל של ריצה ארוכה זה אך יועתק בקלות ולהדביק פיקוד Valgrind כדי לראות אם יש כמה טעויות שהיו שם. וזה יהיה מכריע בכל פעם שאתה רואה את הפלט, אלא רק לנתח דרך ויזואלית את כל התפוקה ולראות אם אתה רואה אזכורים של טעויות או אזהרות או לא חוקי או שאבד. כל אחת ממילים שנשמעים כמו פשלת איפשהו. אז מבין שזה כלי חדש בארגז הכלים שלך. 

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

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

מה אם אנחנו רוצים לטפל בזה? אנחנו עשינו את רוב החזותיים הזה, ועם בני אדם, אבל מה אם אנחנו רוצים לעשות כניסה? אז ברשימה המקורית הייתה 9, 17, 20, 22, 29, 34. מה אם אז רציתי חלל malloc למספר 55, צומת עבורו, ואז אנחנו רוצים להכניס 55 לרשימה בדיוק כפי שעשינו ביום שני? איך עושים את זה? ובכן, אניטה עלתה והיא בעצם נכנסה לרשימה. היא החלה במרכיב הראשון, אז הבאה, הבא, הבא, הבא, הבא. לבסוף פגע בכל הדרך השמאלית למטה והבנתי אה, זה הוא ריק. אז מניפולצית מצביע מה שהיה צריכה לעשות? האדם שהיה בסופו של דבר, המספר 34, צריך ידו השמאלית מורמת כדי להצביע על 55, 55 נזקקו הזרוע השמאלית שלהם כלפי מטה כדי להיות NULL השליחות הקטלנית החדשה. עשה. די קל להכניס 55 לרשימה ממוינת. ואיך ייתכן שזה נראה? 

תן לי ללכת קדימה, לפתוח את חלק קוד דוגמה כאן. אני אפתח את gedit, ותן לי לפתוח את שני קבצים ראשונים. אחת הוא list1.h, ותן לי רק להזכיר שזה היה הנתח של קוד שאנו משמשים כדי לייצג צומת. צומת יש גם int בשם n ומצביע בשם הבא שרק נקודות לדבר הבא ברשימה. זה עכשיו ב. קובץ h. למה? יש אמנה זו, ואנחנו לא נצלנו את זה כמות עצם ענקיות, אבל מי שכתב את פונקציות printf ואחרות נתן במתנה לעולם כל הפונקציות הללו על ידי כתיבת קובץ בשם stdio.h. ואז יש string.h, ואז יש map.h, ויש את כל הקבצים האלה h שאולי ראה או השתמשתי במונח נכתב על ידי אנשים אחרים. בדרך כלל באלה. קבצי h דברים בלבד כמו typedefs או הצהרות של סוגים או הצהרות של קבועים מותאמים אישית. אתה לא שמת את ההטמעות 'פונקציות בקבצי כותרת. אתה שם, במקום, רק אב הטיפוס שלהם. אתה שם את הדברים שאתה רוצה לחלוק עם העולם את מה שהם צריכים כדי לקמפל את הקוד שלהם. אז רק כדי להיכנס להרגל הזה, החלטנו לעשות את אותו דבר. אין הרבה בlist1.h, אבל אנחנו שמנו משהו שעשוי לעניין את האנשים בעולם שרוצה להשתמש ביישום הרשימה המקושר שלנו. עכשיו, בlist1.c, אני לא עובר את כל העניין הזה כי זה קצת ארוך, זה תכנית, אבל בואו להפעיל אותו במהירות אמיתית בשורת הפקודה. בואו לאסוף אותי List1, תן לי לאחר מכן להפעיל List1, ומה שתראה הוא יש לנו מדומה תכנית קטנה ופשוט כאן זה הולך כדי לאפשר לי להוסיף ולהסיר מספרים לרשימה. אז תן לי ללכת קדימה וסוג 3 ל3 אפשרות התפריט. אני רוצה להכניס את המספר - בואו נעשה את המספר הראשון, שהיה 9, ועכשיו אומר לי שהרשימה היא עכשיו 9. תן לי ללכת קדימה ולעשות הכנסה נוספת, ולכן אני מכה אפשרות תפריט 3. מה מספר אני רוצה להוסיף? 17. Enter. ואני אעשה רק עוד אחד. בואו יכניסו לי את המספר 22. אז יש לנו את ראשיתה של הרשימה המקושרת שהיו לנו בצורת שקופית לפני רגע. איך הכנסה זו אכן קורית? ואכן, 22 הם עכשיו בסוף הרשימה. אז הסיפור שספרנו על במה ביום שני ורק עכשיו recapped חייב להיות ממש קורה בקוד. בואו נעיף מבט. בואו לגלול למטה בקובץ זה. אנחנו לחפות על חלק מהפונקציות, אבל אנחנו ניסע, נניח, להוספת הפונקציה. 

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

אחרת, אני אומר לי המשתמש נתן לי מספר להוסיף, אני קורא GetInt הידיד הוותיק שלנו, ואז זה היה התחביר החדש שהצגנו ביום שני. 'Newptr-> n' הפירוש תיקח את הכתובת שניתנה לך על ידי malloc המייצג את הבית הראשון של אובייקט צומת חדש, ואז ללכת לשדה בשם n. שאלת טריוויה קטנה: זה שווה את מה שהשורה סתומה עוד יותר של קוד? אחרת איך יכולתי לכתוב את זה? רוצה לקחת דקירה? [תשובת סטודנט, לא מובן] טוב. שימוש. N, אבל זה לא ממש פשוט כמו זה. מה אני קודם צריך לעשות? [תשובת סטודנט, לא מובן] טוב. אני צריך לעשות * newptr.n. אז זה אומר מצביע חדש ברור כתובת. למה? כי זה הוחזר על ידי malloc. Newptr * אומר "ללכת לשם" ואז ברגע שאתה שם, אז אתה יכול להשתמש בהרבה יותר מוכר. n, אבל זה רק נראה קטן ומכוער, במיוחד אם אנו בני האדם הולכים לצייר עם חצי מצביעים כל הזמן; העולם יש טופל על סימון החץ הזה, שעושה בדיוק את אותו הדבר. אז אתה משתמש רק -> סימון כאשר הדבר בצד השמאל הוא מצביע. אחרת, אם זה struct בפועל, השתמש. N. ואז זה: מדוע אני לאתחל newptr-> ליד NULL? אנחנו לא רוצים שיד שמאל שלו משתלשלת מסיום השלב. אנחנו רוצים שהוא מצביע ישר למטה, מה שאומר בסוף הרשימה זו עלול להיות בצומת הזו, כך שעדיף שלוודא שהוא NULL. וגם, באופן כללי, אתחול המשתנים שלך או החברים שלך ונתוני structs למשהו הוא פשוט תרגול טוב. פשוט לתת לאשפה קיימת ותמשיך להתקיים, בדרך כלל מקבלת אותך בצרות אם שכחת לעשות משהו בהמשך. 

הנה כמה מקרים. זה, שוב, הוא הוספת הפונקציה, והדבר הראשון שאני בודק הוא אם למשתנה בשם הראשון, שמשתנים הגלובלי הוא NULL, זה אומר שאין רשימה מקושרת. אנחנו לא הכנסנו את כל מספרים, כך שזה טריוויאלי להכניס מספר הנוכחי לרשימה, מכיוון שזה שייך בתחילת הרשימה. אז זה היה כאשר אניטה פשוט עמדה לכאן לבד, מעמיד פן אף אחד אחר לא היה כאן על במה עד שהוקצינו צומת, אז היא יכולה להרים את ידה בפעם הראשונה, אם כל אחד אחר היה לעלות על הבמה אחריה ביום שני. עכשיו הוא כאן, זו בדיקה קטנה שבו אני חייב לומר שאם הערך של צומת החדש של n הוא <הערך של n בצומת הראשונה הנוכחית, זה אומר שיש רשימה מקושרת שהחלה. יש צומת אחת לפחות ברשימה, אבל הבחור החדש שייך לפניו, כך שאנחנו צריכים להעביר דברים. במילים אחרות, אם ברשימה החלה רק עם, יניח, רק מספר 17, זה - למעשה, אנחנו יכולים לעשות את זה בצורה ברורה יותר. אם תתחילו את הסיפור שלנו עם מצביע כאן התקשר בפעם הראשונה ותחילה זה NULL, ואנו מוסיפים את המספר 9, המספר 9 שייך בבירור בתחילת הרשימה. אז בואו נעמיד פן שאנחנו רק malloced כתובת או המספר 9 והכנסנו אותו לכאן. אם הראשון הוא 9 כברירת מחדל, התרחיש הראשון דנו רק אומר ששלב זה בחור בואו לכאן, תשאיר את זה כNULL; עכשיו יש לנו את המספר 9. המספר הבא אנחנו רוצים להכניס הוא 17. 17 שייכים לכאן, ולכן אנחנו הולכים לעשות קצת קפיצה לוגית בזה. אז בואו במקום, לפני שאנחנו עושים את זה, בואו נעמיד פן שאנחנו רוצים להכניס את המספר 8. 

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

אז נתת לי לצייר עוד דבר אחד, ואני צריך להשאיר קצת יותר מקום לזה. אז תסלח הציור הקטנטן. הבחור הזה נקרא newptr. זה משתנה הכרזנו כמה שורות קודם לכן, בקו - מעל 25. וזה מצביע על 8. לכן, כאשר אני אומר newptr-> הבא, זה אומר ללכת לstruct שמכוונים אליי על ידי newptr, אז הנה אנחנו, נלך לשם. ואז הוא אומר לי חץ השדה הבא, ולאחר מכן = אומר לשים איזה ערך יש? הערך שהיה במקום הראשון, מה ערך היה בראשון? קודם הצביע בצומת הזו, אז זה אומר שזה צריך עכשיו להצביע בצומת זה. במילים אחרות, מה שנראה אמנם בלגן מגוחך עם כתב היד שלי, מה זה רעיון פשוט של הזזת החיצים האלה מסביב מתרגם ל קוד רק עם התוחם הזה. לאחסן את מה שהוא בראשון בשדה הבא ולאחר מכן לעדכן מה קודם למעשה. בואו נלך קדימה ולהריץ קדימה דרך החלק הזה, ולהסתכל רק על הכנסת זנב זה לעת עתה. אניח שאני מגיע לנקודה שבה אני מוצא שהשדה הבא של צומת מסוימת הוא NULL. ובנקודה הזאת בסיפור, פרט שאני פסחתי על הוא שאני כבר הצגתי מצביע אחר כאן בקו 142, מצביע קודם. בעיקרו של דבר, בשלב זה בסיפור, ברגע שמקבלת הרשימה ארוכה, אני סוג של צריך ללכת אותו עם שתי אצבעות, כי אם אני הולך רחוק מדי, זוכר ברשימה אחת באורך, אתה לא יכול ללכת אחורה. אז הרעיון הזה של predptr הוא האצבע השמאלית שלי, וnewptr - לא newptr. מצביע נוסף שיש כאן זה את האצבע שלי אחרת, ואני פשוט סוג של הליכה ברשימה. זו הסיבה שקיימת. אבל הבה נבחן אחד מהמקרים הפשוטים יותר כאן בלבד. אם השדה הבא ששל המצביע הוא NULL, מה המשמעות ההגיונית? אם אתה חוצה את הרשימה הזאת ואתה מכה מצביע NULL? אתה בסוף הרשימה, וכן את הקוד לאז לצרף מרכיב נוסף זה הוא סוג של אינטואיטיבית ייקח צומת שלידו מצביע הוא NULL, אז זה כרגע ריק, ולשנות אותו, אם כי, כדי להיות הכתובת של הצומת החדשה. אז אנחנו רק ציור בקוד על החץ שציירנו על במה על ידי הרמת יד השמאל של מישהו. 

ומקרה שאני אניף את הידות שלי בעכשיו, רק בגלל שאני חושב שזה קל ללכת לאיבוד כאשר אנחנו עושים את זה בסוג כזה של הסביבה, בודק לכניסה באמצע של הרשימה. אבל רק באופן אינטואיטיבי, מה צריך לקרות אם אתה רוצה להבין שבו חלק מספר שייך באמצע הוא שאתה צריך ללכת ברגלו עם יותר מאצבע אחת, מצביע יותר מפעם אחת, להבין לאן הוא שייך על ידי בדיקה הוא המרכיב <1 הנוכחי, > הנוכחי אחד, וברגע שאתה מוצא את המקום, אז אתה צריך לעשות את זה סוג של משחק פגז שבו אתה מזיז את המצביעים סביב מאוד בזהירות. ותשובה, אם תרצו למצוא היגיון בתוך זה בבית בעצמך, מסתכם רק בשתי השורות האלה של קוד, אבל כדי של הקווים האלה הוא סופר חשוב. כי אם אתה טיפה היד של מישהו ולהעלות מישהו אחר שלא בסדר הנכון, שוב, אתה יכול בסוף יתום הרשימה. לסיכום יותר מושגית, הכניסה בזנב היא פשוטה יחסית. הכניסה בראש היא גם פשוטה יחסית, אבל אתה צריך לעדכן את מצביע נוסף הפעם לסחוט מספר 5 ברשימה כאן, ולאחר מכן כניסה באמצע כרוך אפילו יותר מאמץ, כדי להוסיף את המספר 20 מאוד בזהירות במיקום הנכון שלו, שבין 17 ו 22. אז אתה צריך לעשות משהו כמו 20 יש נקודת הצומת החדשה עד 22, ולאחר מכן, המצביע של הצומת שבו צריך להיות מעודכן אחרון? זה 17, כדי באמת להכניס אותו. אז שוב, אני לדחות את הקוד בפועל שליישום מסוים. 

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

למעשה, יניח שעשינו רשימה מקושרת בצד לשים לרגע ואנחנו במקום הצגנו את הרעיון של שולחן. ובואו נחשוב על שולחן לרגע, כמו מערך. מערך זה והמקרה הזה כאן יש כמה אלמנטים 26, 0 עד 25, ותניח שאתה זקוק לקצת נתח של אחסון לשמות: אליס ובוב וצ'רלי וכדומה. ואתה צריך קצת מבנה נתונים כדי לאחסן את השמות האלה. ובכן, אתה יכול להשתמש במשהו כמו רשימה מקושרת ואתה יכול ללכת ברשימת ההכנסה אליס לפני בוב וצ'רלי לאחר שבוב וכן הלאה. ואכן, אם אתה רוצה לראות את קוד כמו שכהערת אגב, יודע שבlist2.h, אנו עושים בדיוק את זה. אנחנו לא נעבור על הקוד הזה, אבל זה הנו נגזר של הדוגמא הראשונה שמציג struct אחד אחר שראינו לפני הסטודנט שנקרא, ואז מה זה בעצם מאחסן ברשימה המקושרת הוא מצביע למבנה סטודנט במקום מספר שלם קטן ופשוט, n. אז מבין שיש קוד שיש כרוך מחרוזות בפועל, אם המטרה בהישג יד ממש כרגע היא לטפל בבעיה, אבל היעילות, האם זה לא יהיה נחמד אם אנו מקבלים אובייקט בשם אליס, אנחנו רוצים להביא אותה למיקום הנכון במבנה נתונים, זה מרגיש כאילו זה הייתי ממש נחמד, רק כדי לשים את אליס, מי ששם מתחיל ב, במיקום הראשון. ובוב, ששמה מתחיל ב-B, במיקום השני. עם מערך, או בואו נתחיל קוראים לזה שולחן, שולחן חשיש בזה, אנחנו יכולים לעשות בדיוק את זה. אם אנו מקבלים שם כמו אליס, מחרוזת כמו אליס, שבו אתה מכניס-l-i-c-דואר? אנחנו צריכים hueristic. אנחנו צריכים פונקציה לקחת קצת קלט כמו אליס ולהחזיר תשובה, "שים את אליס במיקום זה." ופונקציה זו, הקופסה השחורה הזו, הוא הולך להיות שם פונקציית hash. 

פונקציית hash היא משהו שלוקח קלט, כמו "אליס", וחוזר אליך, בדרך כלל, את המיקום המספרי בחלק מבנה נתונים בי אליס שייכת. במקרה זה, פונקציית hash שלנו צריכה להיות פשוט יחסית. פונקציית hash שלנו צריכה לומר, אם אתה מקבל את "אליס", שדמות צריכה שאכפת לי? ראשון. אז אני מסתכל על [0], ואז אני אומר אם [0] דמות היא, להחזיר את המספר 0. אם זה ב ', לחזור 1. אם C זה, לחזור 2, וכן הלאה. הכל 0 המדד, ושיאפשר לי להכניס את אליס, ואז בוב וצ'רלי וכן הלאה למבנה נתונים זה. אבל יש בעיה. מה אם אניטה מגיעה שוב? איפה שם את אניטה? את שמה, גם מתחיל באות, וזה מרגיש כמו שעשינו בלגן גדול עוד יותר לבעיה זו. עכשיו יש לנו החדרה מיידית, החדרת זמן קבועה, למבנה נתונים ולא במקרה הגרוע יותר ליניארי, אבל מה אנחנו יכולים לעשות עם אניטה במקרה זה? מה הן שתי אפשרויות, באמת? כן? [תשובת סטודנט, לא מובן] אוקיי, אז נהיה לנו ממד אחר. זה טוב. אז אנחנו יכולים לבנות דברים ב3D כמו שדברנו עליה מילולי ביום שני. אנחנו יכולים להוסיף גישה אחרת כאן, אבל נניח שלא, מה שאני מנסה לומר את זה פשוט. כל המטרה כאן היא כדי לקבל גישה מיידית בזמן קבוע, כך שזה חיבור יותר מדי מורכב. מה הן אפשרויות אחרות, כשמנסה להכניס את אניטה למבנה נתונים זה? כן? [תשובת סטודנט, לא מובן] טוב. כדי שנוכל לעבור את כולם למטה, כמו צ'רלי דחיפות את בוב ואליס, ואז אנחנו שמים את אניטה שבו היא לא באמת רוצה להיות. 

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

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

אולי אנחנו פשוט נהיה לך מזל ואנחנו לא הולכים להיות לך שתיים או שניים של B של בהסתברות מאוד גבוהה, אבל כמו שמישהו ציין, אם להכליל את הבעיה הזו ולא לעשות 0-25 אבל, אומר, 0 עד 364, או 65, לעתים קרובות מספר ימים בשנה טיפוסית, ושאל את השאלה, "מה ההסתברות ששנינו בחדר הזה יש לו יום הולדת?" שים את זה בדרך אחרת, מה ההסתברות ששנינו יש שם החל? הסוג של שאלה הוא אותו הדבר, אבל מרחב הכתובות הזה, מרחב חיפוש זה, הוא יותר גדול במקרה של ימי הולדת, כי יש לנו כל כך הרבה יותר ימים בשנה מאותיות באלפבית. מה ההסתברות להתנגשות? ובכן, אנחנו יכולים לחשוב על זה על ידי חישוב המתמטי בכיוון ההפוך. מה ההסתברות להתנגשויות לא? ובכן, הביטוי הזה כאן אומר שמה ההסתברות אם יש רק אדם אחד בחדר הזה, שיש להם יום הולדת ייחודית? זה 100%. כי אם יש רק אדם אחד בחדר, או יום ההולדת שלה יכול להיות כל אחד מתוך 365 ימים מתוך השנה. אז אפשרויות 365/365 נותנות לי ערך של 1. אז ההסתברות בשאלה כרגע היא רק 1. אבל אם יש אדם נוסף בחדר, מה ההסתברות שיום ההולדת שלהם הוא שונה? יש 364 ימים בלבד אפשריים, שנים מעוברות, תוך התעלמות ליום ההולדת שלהם לא אתנגש עם האנשים האחרים. אז 364/365. אם אדם שלישי מגיע, זה 363/365, וכן הלאה. אז אנחנו ממשיכים יחד הכפלת השברים האלה, שמקבלים יותר ויותר קטנים, כדי להבין מה היא ההסתברות שכולנו יש ימי הולדת ייחודיים? אבל אז אנחנו יכולים, כמובן, פשוט לקחת את התשובה הזאת ולהעיף סביבו ולעשות 1 מינוס כל זה, ביטוי שסופו של דבר יקבל אם אתה זוכר את החלק האחורי של ספרי המתמטיקה שלך, זה נראה משהו קטן כזה, אשר מתפרש הרבה יותר בקלות בצורה גרפית. וגרפיקה זה כאן יש מספר ימי ההולדת על ציר x, או מספר אנשים עם ימי הולדת, ועל ציר y הוא ההסתברות להתאמה. ומה שזה אומר הוא שאם יש לך, יניח, אפילו, בואו לבחור משהו כמו 22, 23. אם יש 22 או 23 אנשים בחדר, ההסתברות כי שניים מאותם מעט מאוד אנשים הולכים להיות באותו יום ההולדה הוא למעשה גבוה נפלא, combinatorially. 50% סיכויים כי בכיתה של רק 22 אנשים, סמינר, כמעט, 2 האנשים האלה הולכים להיות אותו יום ההולדת. בגלל שיש כל כך הרבה דרכים שבם אתה יכול לקבל אותו יום ההולדת. גרוע מכך, אם אתה מסתכל על הצד הימני של התרשים, בזמן שיש לך בכיתה עם 58 תלמידים בזה, ההסתברות של 2 אנשים שיש להם יום הולדת היא גבוהה נפלא, סופר, כמעט 100%. עכשיו, זה סוג של עובדה משעשעת על חיים אמיתיים. 

אבל השלכות, עכשיו, למבני נתונים ואחסון מידע משמעות הדבר הוא כי רק בהנחה שיש לך הפצה נחמדה, נקיה ואחידה של נתונים ויש לך מספיק גדול כדי להתאים מערך חבורה של דברים זה לא אומר שאתה הולך לגרום לאנשים במיקומים ייחודיים. אתה הולך להיות התנגשויות. אז הרעיון הזה של hashing, כפי שהוא נקרא, לוקח קלט כמו "אליס" ומעסה אותו בדרך כלשהי ולאחר מכן מקבל בחזרה תשובה כמו 0 או 1 או 2. מקבל בחזרה חלק מהתפוקה שהוא הוטרד על ידי פונקצית ההסתברות של התנגשות. אז איך אנחנו יכולים להתמודד עם ההתנגשויות האלה? ובכן, במקרה אחד, אנחנו יכולים לקחת את הרעיון שהוצע. אנחנו רק יכולים להעביר את כולם, או אולי, קצת יותר פשוט, ולא כל מהלך אחר, בואו פשוט לעבור אניטה לתחתית במקום הזמין. אז אם אליס היא ב0, בוב הוא ב1, צ'רלי הוא ב2, אנחנו פשוט נשים את אניטה בשעת 3 מיקום. וזו טכניקה במבני נתונים הנקראת ליניארי חיטוט. בשכבות בגלל שאתה סתם הליכת הקו הזה, ואתה סוג של חיטוט למקומות פנויים במבנה הנתונים. כמובן, זה יתפורר אל O (n). אם מבנה הנתונים ממש מלא, יש 25 אנשים בזה כבר, ואז מגיעה יחד אניטה, היא מסתיימת במה יהיה המיקום Z, וזה בסדר גמור. היא עדיין מתאימה, ואנחנו יכולים למצוא אותה מאוחר יותר. 

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

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

אבל אם תניחו לרגע שהתפלגות אחידה, ויש לנו n אנשי סך הכל, ושרשרות כלל מ ' עומד לרשותנו, ולאחר מכן את האורך של כל אחת מרשתות אלה די פשוט הולך להיות כולל, n מתחלק במספר הרשתות. אז n / m. אבל כאן בדיוק אנחנו יכולים להיות כל מתמטיים מתוחכמים. מ 'הוא תמידי, כי יש מספר קבוע של אלה. אתה הולך להכריז על המערך שלך בהתחלה, ואנחנו לא שינוי גודל הציר האנכי. על פי הגדרה, שנשאר קבוע. זה רק הציר האופקי, כביכול, שהוא משתנה. אז מבחינה טכנית, זה קבוע. אז עכשיו, בפעם ההכנסה הוא פחות או יותר O (n). כך שלא מרגיש כל כך הרבה יותר טוב. אבל מה האמת כאן? ובכן, כל הזמן הזה, במשך שבועות, אנחנו אומרים O (n ²). O (n), 2 x n ², - n, מחולק על ידי 2. . . איכס. זה פשוט ² n. אבל עכשיו, בחלק זה של הסמסטר, אנחנו יכולים להתחיל לדבר על לחזור לעולם האמיתי. וn / מ 'הוא בהחלט מהיר יותר מאשר רק n לבד. אם יש לך אלף שמות, ואתה שובר אותם לסלים מרובים כך יש לך רק עשרה שמות בכל אחת מרשתות אלה, בהחלט מחפש עשרה דברים הולך להיות מהיר יותר מאלף דברים. וכך באחת קבוצות הבעיה הקרובות הוא הולך לאתגר אותך לחשוב בדיוק על זה למרות, כן, asymptotically ומתמטי, זה עדיין רק ליניארית, שמבאס באופן כללי, כאשר מנסים למצוא דברים. במציאות, זה הולך להיות מהיר יותר מזה בגלל המחלק הזה. ואז יש שוב הולך להיות תחלופה זו וזה קונפליקט בין התאוריה למציאות, ואת אחד הכפתורים יהיה להתחיל להסתובב בנקודה זו בסמסטר הוא יותר של מציאות אחת כמו שאנחנו סוג של להתכונן לסוף semster, כפי שאנו מציגים את העולם של תכנות אינטרנט, שם באמת, ביצועים הולכים לספור כי המשתמשים שלך הולכים מתחיל להרגיש ולהעריך את החלטות עיצוב עניות. 

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

מהו צומת בפועל? מה היא צומת ברשימה המקושרת החדשה הזה? הדבר הראשון, שנקרא מילה, הוא לשמו של האדם. האורך, ככל הנראה, מתייחס לאורך המרבי של שמו של אדם, מה שזה, 20, 30, 40 תווים במקרים פינתיים מטורפים, ו+1 הוא בשביל מה? זה פשוט אופי NULL הנוסף, \ 0. אז צומת זו עטיפה "משהו" בתוך עצמו, אבל זה גם מצהיר מצביע נקרא הבא כך שאנחנו יכולים שרשרת אליס לבוב לצ'ארלי וכן הלאה. יכול להיות אפס, אך לא בהכרח צריך להיות. כל שאלה על שולחנות החשיש האלה? כן? [סטודנט ששאל את השאלה, לא מובן] מערך - שאלה טובה. מדוע מילת char זה במערך ולא רק * char? בדוגמא השרירותית הזה, אני לא רוצה שיהיה לי להיזקק לmalloc עבור כל אחד מהשמות המקוריים. אני רוצה להכריז על סכום מקסימאלי של זיכרון עבור המחרוזת כדי שאוכל להעתיק את מבנה אליס \ 0 ולא אצטרך להתמודד עם malloc וחופשי וכדומה. אבל אני יכול לעשות את זה אם אני רוצה להיות מודע יותר לשימוש בחלל. שאלה טובה. אז בואו ננסה לעשות הכללות מזה ולמקד את השארית היום במבני נתונים באופן כללי יותר ובעיות אחרות שאנחנו יכולים לפתור תוך שימוש באותם יסודות למרות שמבני הנתונים עצמם עשויים להיות שונים בפרטים שלהם. 

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

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

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

אז יש מבנה נתונים אחר שאנחנו יכולים להציג. 1 זה נועד במבט הראשון נראה מסתורי, אבל זה אחד מדהים. אז זה הוא מבנה נתונים בשם איירי, איירי, שהתקבל בירושה ממילת האחזור, שלא מבוטא מחדש לנסות-val, אבל זה מה שהעולם קורא את הדברים האלה. מנסה. T-r-i-דואר. זהו מבנה עץ מסוג כלשהו, ​​אבל כל אחד מצומת באיירי נראה כי מה? וזה קצת מטעה, כי זה סוג של מקוצר. אבל זה נראה כמו כל צומת באיירי זה היא למעשה מערך. ולמרות שמחבר תרשים זה לא הראה את זה, במקרה זה, איירי זה היא מבנה נתונים שמטרתו בחיים הוא לאחסן מילים כמו-l-i-c-דואר או B-O-B. ואופן שבו נתוני החנויות אליס ובוב וצ'ארלי ואניטה וכן הלאה הוא משתמש במערך לפי לאחסן אליס בארץ איירי, אנחנו מתחילים בצומת השורש שנראה כמו מערך, וזה כתוב בסימון מקוצר. המחבר השמיט אבגדהוז כי לא היו שמות עם זה. הם הראו M ו-P ו-T בלבד, אבל במקרה הזה, בואו נתרחק מאליס ובוב וצ'רלי לכמה שמות שנמצאים כאן. מקסוול הוא למעשה בשרטוט זה. אז איך עשה את חנות מחבר M--x-w-e-l-l? הוא או היא התחיל בצומת השורש, והלך ל[ ז], כך שבערך 13, מיקום ה -13 במערך. אז משם, יש מצביע. מצביע שמוביל למערך אחר. משם המחבר צמוד שלמערך במיקום, כפי שמוצג שם בפינה שמאלית עליונה, ואז הוא או היא אחרי שהמצביע למערך אחר, והלך למצביע במיקום X. ואז במערך המיקום W הבא, E, L, L, וכן הלאה, ולבסוף, בואו באמת מנסה לשים תמונה לזה. איך נראה צומת כמו בקוד? בצומת איירי מכילה מערך של מצביעים לצומת נוספים. אבל יש גם חייב להיות איזשהו הערך בוליאני, לפחות ביישום זה. אני במקרה קורא לזה is_word. למה? כי כשאתה מכניס מקסוול, אתה לא מכניס משהו לתוך מבנה נתונים זה. אתה לא כותב מ 'אתה לא כותב X. כל מה שאתה עושה הוא בעקבות מצביעים. המצביע המייצג M, אז המצביע המייצג, אז המצביע המייצג X, אז W, E, L, L, אבל מה שאתה צריך לעשות בסוף הוא סוג של ללכת, בדוק, שהגעתי מיקום זה. הייתה מילה שמסתיימת כאן במבנה הנתונים. 

אז מה היא באמת איירי מלאה והמחבר בחר לייצג terminuses אלה עם משולשים קטנים. זה רק אומר שעובדת המשולש הזה כאן, ערך בוליאני זה של אמיתי משמעות היא שאם אתה הולך אחורה בעץ, זה אומר מילה בשם מקסוול הוא בזה. אבל המילה foo, למשל, לא בעץ, משום שאם אני מתחיל לעבוד בצומת השורש לכאן בראש, אין מצביע f, אין מצביע o, אין מצביע o. Foo אינו שם במילון זה. אבל לעומת זאת, טיורינג, t-u-r-i-n-g. שוב, אני לא לאחסן t או u או r או אני או n או g. אבל עשיתי את החנות במבנה נתונים זה ערך של דרך האמיתית כאן בצומת הזה - בעץ על ידי הגדרת הערך בוליאני זה של is_word לנכון. אז איירי היא סוג של המבנה מטה מאוד המעניין הזה, איפה שאתה לא באמת אחסון הדברים עצמם לסוג זה של מילון. כדי להיות ברור, אתה רק אחסון כן או לא, יש מילה שמסתיימת כאן. 

עכשיו, מה המשמעות? אם יש לך 150.000 מילים במילון שאתה מנסה לאחסן בזיכרון באמצעות משהו כמו רשימה מקושרת, אתה הולך לי 150.000 צומת ברשימה המקושרת שלך. ולמצוא אחת את המילים האלה בסדר אלפביתי יכול לקחת זמן O (n). הזמן ליניארי. אבל במקרה כאן של איירי, מה זמן הריצה של מציאת מילה? מתברר היופי כאן הוא שגם אם יש לך 149,999 מילים כבר במילון זה, כפי שיושם במבנה נתונים זה, כמה זמן לוקח למצוא או להכניס אדם נוסף לזה, כמו אליס, אליס? טוב, זה רק 5, אולי 6 שלבים לתו הנגרר. בגלל הנוכחות בשמות אחרים במבנה לא מקבל בדרך של החדרת אליס. יתר על כן, מציאת אליס פעם יש 150.000 מילים במילון זה לא מקבל בדרך של מציאת אליס כלל, כי אליס היא. . . . . כאן, בגלל שמצאתי ערך בוליאני. ואם אין בוליאני הנכונה, אז אליס היא לא במבנה הנתונים הזה של מילים. במילים אחרות, הזמן פועל למציאת דברים והחדרת דברים לזה חדש מבנה נתונים של איירי הוא הו - זה לא N. בגלל הנוכחות בשל 150.000 אנשים אין כל השפעה על אליס, שזה נראה. אז בואו נקראים לזה k, כאשר k הוא האורך המקסימאלי של מילה באנגלית שהוא בדרך כלל לא יותר מתווים 20-משהו. אז k הוא קבוע. אז את הגביע הקדוש נראים שאנו נמצאים כעת הוא זו של זמן איירי, קבוע למוסיף, לחיפושים, למחיקות. בגלל מספר הדברים שכבר קיים במבנה, שהם אפילו לא שם פיסיים. שוב, הם פשוט למיין של מסומן, כן או לא, אין השפעה על זמן הריצה שלו בעתיד. 

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

תאמינו או לא, כיף כמו C כבר כמה זמן, אנחנו מגיעים לנקודה בסמסטר שבו הגיע זמן למעבר לדברים יותר מודרניים. דברים ברמה גבוהה יותר. ואף על פי לשבועות הקרובים אנחנו עדיין נמשיך לטבול את עצם בעולם של מצביעים וניהול זיכרון כדי לקבל נחמה זו שאיתה אז יכולה לבנות עליו, סוף המשחק הוא בסופו להציג, באופן אירוני, לא זו שפה. נבלנו, כמו 10 דקות בדיבורים על ה-HTML. כל HTML הוא הוא שפת סימון, ומה היא שפת סימון אלה הוא סדרה של סוגריים פתוחים וסגורים סוגריים שאומרים 'תעשה את זה מודגש' "לעשות את זה" הנטוי "לעשות מרכז זה '. זה לא כל כך מעניין מבחינה אינטלקטואלית, אבל זה סופר שימושי. וזה בהחלט נוכח בכל מקום בימים אלה. אבל מה רב עצמה על העולם של ה-HTML, ותכנות אינטרנט באופן כללי יותר, בונה דברים דינמיים; כתיבת קוד בשפות כמו PHP או Python או Ruby או Java או C #. באמת, כל השפה של בחירה שלך, ויצירת HTML באופן דינמי. יצירת משהו שנקרא CSS באופן דינמי. גיליונות סגנון מדורג, שהיא גם באסתטיקה. וכך למרות שהיום, אם אני הולך לאתר מסוים כמו Google.com המוכר, ואני הולכת להצגה, ליזם, הצגת מקור, שאולי כבר עשה קודם, אבל הולך להציג מקור, החומר הזה כנראה נראה די תמוה. אבל זה הקוד הבסיסי שמיישם Google.com. על הקצה הקדמי. ובעצם כל זה הוא דברי אסתטיקה אווריריות. זה CSS עד כאן. אם אני שומר את הגלילה למטה נקבל כמה דברים בצבעים. זה HTML. הקוד של גוגל נראה כמו בלגן, אבל אם אני באמת לפתוח את חלון אחר, אנו יכולים לראות כמה מבנה לזה. אם אני פותח את זה, שים לב כאן, זה קצת יותר קריא. אנחנו הולכים לראות תג זה לפני זמן רב, [מילה] הוא תג, HTML, ראש, גוף, div, תסריט, אזור טקסט, תוחלת, ממוקד, div. וזה גם למיין נסתר למראה במבט הראשון, אבל כל הבלגן הזה כדלקמן דפוסים מסוימים, ודפוסי דיר, כך שברגע שיקבל את היסודות למטה, תוכל לכתוב קוד כזה ולאחר מכן לתפעל קוד כזה עדיין משתמש בשפה אחרת, בשם-JavaScript. וJavaScript היא שפה שפועלת בתוך דפדפן היום שאנו משתמשים בקורסי הרווארד, לכלי הקניות כמובן שגוגל מפות משתמשות כדי לתת לך חבורה שלמה של דינמי, פייסבוק נותן לך להציג עדכוני סטטוס מיידיים, טוויטר משתמש בו כדי להראות לך טוויטים באופן מיידי. כל זה יתחיל לשקוע פנימה את עצמנו אבל כדי להגיע לשם, אנחנו צריכים להבין משהו קטן על האינטרנט. הקליפ הזה כאן הוא רק דקה ארוכה, ובואו נניח לזה עכשיו, למעשה, איך האינטרנט עובד כמו טיזר למה שעומד לבוא. אני נותן לך "לוחמים של הרשת." 

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