1 00:00:00,000 --> 00:00:00,500 2 00:00:00,500 --> 00:00:11,137 [השמעת מוסיקה] 3 00:00:11,137 --> 00:00:12,220 דוד י מלאן: בסדר. 4 00:00:12,220 --> 00:00:13,950 זה CS50. 5 00:00:13,950 --> 00:00:18,560 זהו שבוע חמישה המשיכו, ואנו יש לי כמה חדשות טובות וחדשות רעות. 6 00:00:18,560 --> 00:00:21,140 אז חדשות טובות היא שCS50 משיק ביום שישי הקרוב. 7 00:00:21,140 --> 00:00:24,430 אם ברצונכם להצטרף אלינו, הראש לכתובת הרגילה כאן. 8 00:00:24,430 --> 00:00:28,670 חדשות טובות עוד יותר, לא הרצאה ביום שני הקרוב 13th. 9 00:00:28,670 --> 00:00:31,970 מעט פחות חדשות טובות יותר, חידון אפס הוא ביום רביעי הבא. 10 00:00:31,970 --> 00:00:33,840 פרטים נוספים יכולים להיות מצא בכתובת אתר זו כאן. 11 00:00:33,840 --> 00:00:36,340 ובמשך כמה הימים הבאים יהיה לנו למלא את החסר 12 00:00:36,340 --> 00:00:39,234 בכל הקשור לחדרים שנהיה לנו שמורות. 13 00:00:39,234 --> 00:00:41,400 חדשות טובות יותר היא שתהיינה עוד להיות סקירה כמובן רחבות 14 00:00:41,400 --> 00:00:43,570 פגישה זו באה יום שני בערב. 15 00:00:43,570 --> 00:00:46,270 השארו לקורס של אתר למיקום ופרטים. 16 00:00:46,270 --> 00:00:49,290 סעיפים, למרות שזה חג, גם לפגוש גם כן. 17 00:00:49,290 --> 00:00:50,490 18 00:00:50,490 --> 00:00:52,940 החדשות הטובות ביותר, להרצות ביום שישי הבא. 19 00:00:52,940 --> 00:00:56,220 אז זה שאנחנו מסורת יש לי, לפי תכנית הלימודים. 20 00:00:56,220 --> 00:00:58,100 פשוט- זה הולך להיות מדהים. 21 00:00:58,100 --> 00:01:02,510 אתה תראה דברים כמו מבני נתונים בזמן קבוע 22 00:01:02,510 --> 00:01:04,730 ושולחנות חשיש ועצים ומנסה. 23 00:01:04,730 --> 00:01:07,150 ונדבר על בעיות יום הולדת. 24 00:01:07,150 --> 00:01:09,440 חבורה של דברים שלמות מחכה ביום שישי הבא. 25 00:01:09,440 --> 00:01:11,212 26 00:01:11,212 --> 00:01:12,200 אישור. 27 00:01:12,200 --> 00:01:13,190 בכל אופן. 28 00:01:13,190 --> 00:01:17,080 >> אז תזכור, כי אנחנו כבר התמקדות בתמונה הזאת של מה 29 00:01:17,080 --> 00:01:18,980 בתוך הזיכרון של המחשב שלנו. 30 00:01:18,980 --> 00:01:22,875 אז זיכרון או זיכרון RAM הוא שבו תוכניות קיים בזמן שאתה מפעיל אותם. 31 00:01:22,875 --> 00:01:25,215 אם תלחץ פעמים סמל לרוץ כמה תכנית 32 00:01:25,215 --> 00:01:27,520 לחץ לחיצה כפולה או סמל כדי לפתוח קובץ כלשהו, 33 00:01:27,520 --> 00:01:30,430 זה נטען מקשיח לנהוג או כונן מצב מוצק 34 00:01:30,430 --> 00:01:34,190 לזכרון RAM, זיכרון גישה אקראי, שבו הוא חי עד את הכח יוצא, 35 00:01:34,190 --> 00:01:36,700 מכסה המחשב הנייד נסגר, או שאתה יוצא מהתכנית. 36 00:01:36,700 --> 00:01:38,960 >> עכשיו זיכרון ש, של שכנראה שיש לך 37 00:01:38,960 --> 00:01:41,950 1 ג'יגה בימים אלה, 2 ג 'יגה, או אפילו הרבה יותר, 38 00:01:41,950 --> 00:01:44,420 הוא הניח את כלל עבור תכנית נתונה 39 00:01:44,420 --> 00:01:47,170 בסוג כזה של מלבני מודל רעיוני 40 00:01:47,170 --> 00:01:50,860 לפי שיש לנו הערימה בתחתית וכל מינים דברים אחרים בראש. 41 00:01:50,860 --> 00:01:53,140 הדבר בחלקו העליון שראינו בתמונה הזאת 42 00:01:53,140 --> 00:01:55,670 בעבר, אבל מעולם לא דיבר על הוא מגזר הטקסט שנקרא. 43 00:01:55,670 --> 00:01:58,419 קטע טקסט הוא רק דרך מפוארת לומר אפסים ואחדים ש 44 00:01:58,419 --> 00:02:01,150 להלחין תכנית הידור שלך בפועל. 45 00:02:01,150 --> 00:02:03,910 >> אז בלחיצה כפולה כאשר אתה Microsoft Word על Mac או PC שלך, 46 00:02:03,910 --> 00:02:08,030 או כאשר אתה מפעיל נקודה לקצץ מריו על מחשב לינוקס בחלון המסוף שלך, 47 00:02:08,030 --> 00:02:12,460 האפסים ואחדים שמרכיבים מילה או מריו מאוחסן באופן זמני 48 00:02:12,460 --> 00:02:16,610 בזכרון RAM של המחשב שלך שבנקרא קטע טקסט עבור תכנית מסוימת. 49 00:02:16,610 --> 00:02:19,080 מתחת לזה הולך אותחל ונתונים שלא אותחלו. 50 00:02:19,080 --> 00:02:22,655 זה חומר כמו משתנים הגלובליים, שאנחנו כבר לא בשימוש רב של, 51 00:02:22,655 --> 00:02:24,910 אבל במקרה יש לנו היה לי משתנים הגלובליים 52 00:02:24,910 --> 00:02:28,819 או שהוגדר באופן סטטי מחרוזות ש הוא מקודד קשה במילות כמו "שלום" 53 00:02:28,819 --> 00:02:31,860 שאינם נלקחים מהמשתמש הבקידוד קשיח בתכנית שלך. 54 00:02:31,860 --> 00:02:34,230 >> עכשיו, למטה בתחתית אנחנו יש לי הערימה מה שנקרא. 55 00:02:34,230 --> 00:02:37,665 והערימה, עד כה, אנחנו כבר משתמש עבור אילו סוגים של מטרות? 56 00:02:37,665 --> 00:02:39,706 57 00:02:39,706 --> 00:02:40,997 מה הערימה שימשה במשך? 58 00:02:40,997 --> 00:02:41,160 כן? 59 00:02:41,160 --> 00:02:42,070 >> קהל: פונקציות. 60 00:02:42,070 --> 00:02:43,320 >> דוד י מלאן: לפונקציות? 61 00:02:43,320 --> 00:02:44,980 באיזה מובן לפונקציות? 62 00:02:44,980 --> 00:02:48,660 >> קהל: כשאתה מתקשר לפונקציה, טיעונים מועתקים על גבי הערימה. 63 00:02:48,660 --> 00:02:49,660 >> דוד י מלאן: בדיוק. 64 00:02:49,660 --> 00:02:52,650 כשאתה מתקשר לפונקציה, שלה טיעונים מועתקים על גבי הערימה. 65 00:02:52,650 --> 00:02:56,330 אז כל X או Y של של או של או B של שאתה עובר לפונקציה 66 00:02:56,330 --> 00:02:58,680 לשים על באופן זמני הערימה מה שנקרא, 67 00:02:58,680 --> 00:03:02,000 בדיוק כמו אחד מאננברג מגשי אוכל, וגם דברים 68 00:03:02,000 --> 00:03:03,190 כמו משתנים מקומיים. 69 00:03:03,190 --> 00:03:06,290 אם פונקצית foo או ההחלפה שלך שלך יש לי פונקציה משתנים מקומיים, 70 00:03:06,290 --> 00:03:08,602 כמו טמפ ', שני אלה בסופו של בערימה. 71 00:03:08,602 --> 00:03:11,560 עכשיו, אנחנו לא מדברים יותר מדי על שלהם, אבל משתני הסביבה האלה 72 00:03:11,560 --> 00:03:15,690 בתחתית שראינו לפני זמן מה כאשר אני היה לשפץ במקלדת יום אחד 73 00:03:15,690 --> 00:03:20,050 ואני התחלתי בגישת דברים כמו argv 100 או argv 1,000, 74 00:03:20,050 --> 00:03:22,320 רק elements-- אני שוכח אחר המספרים אבל ש 75 00:03:22,320 --> 00:03:24,330 לא היו אמור להיות גישה על ידי לי. 76 00:03:24,330 --> 00:03:26,581 התחלנו לראות כמה סימנים פאנקי על המסך. 77 00:03:26,581 --> 00:03:28,330 אלה היו מה שנקרא משתני סביבה 78 00:03:28,330 --> 00:03:32,390 כמו הגדרות גלובליות עבורי תכנית או למחשב שלי, לא 79 00:03:32,390 --> 00:03:37,090 שאינו קשור לאחרון באג שדנו, 80 00:03:37,090 --> 00:03:39,670 Shellshock, שהיה הפוקד לא מעט מחשבים. 81 00:03:39,670 --> 00:03:42,960 >> עכשיו סוף סוף, בהתמקדותה של היום אנו סופו של דבר נהיה על הערימה. 82 00:03:42,960 --> 00:03:44,864 זה עוד נתח של זיכרון. 83 00:03:44,864 --> 00:03:47,030 ויסודו את כל זה זיכרון הוא אותו החומר. 84 00:03:47,030 --> 00:03:48,040 זה באותה החומרה. 85 00:03:48,040 --> 00:03:49,956 אנחנו רק סוג של טיפול באשכולות שונים 86 00:03:49,956 --> 00:03:51,460 בתים למטרות שונות. 87 00:03:51,460 --> 00:03:56,540 הערימה היא גם הולכת להיות בו משתנים וזיכרון שאתה מבקש 88 00:03:56,540 --> 00:03:58,810 ממערכת ההפעלה מאוחסן באופן זמני. 89 00:03:58,810 --> 00:04:01,890 >> אבל יש סוג של בעיה כאן, כמו בתמונה מרמזת. 90 00:04:01,890 --> 00:04:05,261 סוג שיש לנו משני ספינות עומדים להתנגש. 91 00:04:05,261 --> 00:04:08,010 כי כפי שאתה משתמש יותר ויותר הערימה, וכפי שאנו רואים היום 92 00:04:08,010 --> 00:04:11,800 ואילך, כפי שאתה משתמש יותר ויותר של ערימה, בוודאי דברים רעים עלולים לקרות. 93 00:04:11,800 --> 00:04:15,054 ואכן, אנחנו יכולים לגרום לזה במכוון או שלא בכוונה. 94 00:04:15,054 --> 00:04:16,970 אז הסחרור המסוכן שעבר הזמן היה בתכנית זו, 95 00:04:16,970 --> 00:04:20,570 שלא משרת שום פונקציונלי מטרה אחרת מאשר להפגין 96 00:04:20,570 --> 00:04:24,750 איך אתה כאיש רע באמת יכול לקחת יתרון של באגים בתכניתו של מישהו 97 00:04:24,750 --> 00:04:28,460 ולהשתלט על תכנית או אפילו מערכת כל מחשב או שרת. 98 00:04:28,460 --> 00:04:31,660 אז רק כדי מבט בקצרה, אתה שם לב עיקרי שבתחתית 99 00:04:31,660 --> 00:04:34,510 לוקח בשורת הפקודה טענות, לפי argv. 100 00:04:34,510 --> 00:04:38,480 ויש לה קריאה לפונקצית f, בעצם פונקציה אלמונית בשם 101 00:04:38,480 --> 00:04:40,250 f, וזה עובר בargv [1]. 102 00:04:40,250 --> 00:04:43,960 >> אז מה מילת המשתמש מקליד ב הפקודה אחרי השם של תכנית זו, 103 00:04:43,960 --> 00:04:49,310 ולאחר מכן פונקציה עד שרירותית זו עליון, f, לוקחת במחרוזת, char * AKA, 104 00:04:49,310 --> 00:04:51,720 כפי שאנו כבר החלו לדון, וזה פשוט קורא לזה "בר". 105 00:04:51,720 --> 00:04:53,310 אבל אנחנו יכולים לקרוא לזה שום דבר. 106 00:04:53,310 --> 00:04:57,470 ואז זה מצהיר, בתוך של f, מערך של תווים 107 00:04:57,470 --> 00:04:59,930 נקרא c-- 12 תווים כאלה. 108 00:04:59,930 --> 00:05:03,580 >> עכשיו, על ידי הסיפור שסיפרתי לי לפני רגע, שבו בזיכרון 109 00:05:03,580 --> 00:05:06,720 הוא ג, או 12 אלה תווים הולכים בסופו? 110 00:05:06,720 --> 00:05:07,570 רק שיהיה ברור. 111 00:05:07,570 --> 00:05:08,070 כן? 112 00:05:08,070 --> 00:05:08,590 >> קהל: בערימה. 113 00:05:08,590 --> 00:05:09,420 >> דוד י מלאן: בערימה. 114 00:05:09,420 --> 00:05:10,720 אז ג הוא משתנה מקומי. 115 00:05:10,720 --> 00:05:14,079 אנחנו מבקשים 12 תווים או 12 בתים. 116 00:05:14,079 --> 00:05:16,120 מי הולך בסופו של על הערימה שנקרא. 117 00:05:16,120 --> 00:05:18,530 עכשיו סוף סוף היא פונקציה אחרת זה זה בעצם די שימושי, 118 00:05:18,530 --> 00:05:20,571 אבל אנחנו כבר לא ממש בשימוש זה בעצמנו, strncopy. 119 00:05:20,571 --> 00:05:21,550 120 00:05:21,550 --> 00:05:25,200 זה אומר העתקת מחרוזת, אבל n רק אותיות, n תווים. 121 00:05:25,200 --> 00:05:31,990 אז דמויות n תהיה הועתק מבר לג. 122 00:05:31,990 --> 00:05:32,980 וכמה? 123 00:05:32,980 --> 00:05:34,110 אורכו של בר. 124 00:05:34,110 --> 00:05:36,330 אז במילים אחרות, ש שורה אחת, strncopy, 125 00:05:36,330 --> 00:05:39,500 הולך להעתיק יעילות בר לג. 126 00:05:39,500 --> 00:05:42,340 >> עכשיו, רק כדי לצפות סוג של מוסר ההשכל של הסיפור הזה, 127 00:05:42,340 --> 00:05:44,750 מה שעלול להיות בעייתי כאן? 128 00:05:44,750 --> 00:05:49,710 למרות שאנחנו בודקים את האורך של בר והעברתו לstrncopy, 129 00:05:49,710 --> 00:05:53,145 מה תחושת הבטן שלך אומרת לך היא עדיין שבור על תכנית זו? 130 00:05:53,145 --> 00:05:54,410 131 00:05:54,410 --> 00:05:55,220 כן? 132 00:05:55,220 --> 00:05:57,491 >> קהל: לא כולל חדר לאופי null. 133 00:05:57,491 --> 00:05:59,990 דוד י מלאן: לא כולל חדר לאופי null. 134 00:05:59,990 --> 00:06:02,073 פוטנציאל, שלא כמו ב בפועל העבר שאנחנו עושים אפילו לא 135 00:06:02,073 --> 00:06:04,810 יש כל כך הרבה כמו בתוספת 1 ל להכיל כי אופי null. 136 00:06:04,810 --> 00:06:06,649 אבל זה אפילו יותר גרוע מזה. 137 00:06:06,649 --> 00:06:07,940 מה עוד אנחנו לא מצליחין לעשות? 138 00:06:07,940 --> 00:06:08,432 כן? 139 00:06:08,432 --> 00:06:09,307 >> קהל: [לא ברור] 140 00:06:09,307 --> 00:06:15,440 141 00:06:15,440 --> 00:06:16,440 דוד י מלאן: מושלם. 142 00:06:16,440 --> 00:06:18,490 אנחנו כבר בקידוד קשיח 12 די שרירותיים. 143 00:06:18,490 --> 00:06:19,497 144 00:06:19,497 --> 00:06:21,330 זה לא כל כך הרבה בעיה, אבל העובדה 145 00:06:21,330 --> 00:06:25,630 שאנחנו אפילו לא בודקים אם אורכו של בר הוא פחות מ12, 146 00:06:25,630 --> 00:06:28,530 ובמקרה זה הולך להיות בטוח לשים אותו לזיכרון 147 00:06:28,530 --> 00:06:30,260 ג נקרא שאנחנו כבר הוקצו. 148 00:06:30,260 --> 00:06:32,960 ואכן, אם בר הוא כמו 20 תווים, 149 00:06:32,960 --> 00:06:39,010 פונקציה זו נראית שהעתקה 20 תווים מבר לג, ובכך 150 00:06:39,010 --> 00:06:41,310 לוקח לפחות 8 בתים כי זה לא צריך להיות. 151 00:06:41,310 --> 00:06:42,690 זה המשמעות כאן. 152 00:06:42,690 --> 00:06:44,347 >> אז בתכנית קצרה, שבורה. 153 00:06:44,347 --> 00:06:45,180 לא כזה ביג דיל. 154 00:06:45,180 --> 00:06:46,360 אולי אתה מקבל אשמת פילוח. 155 00:06:46,360 --> 00:06:47,651 היו לנו את כל הבאגים בתוכניות. 156 00:06:47,651 --> 00:06:50,196 אולי לכולנו יש באגים בתוכניות כרגע. 157 00:06:50,196 --> 00:06:51,320 אבל מה המשמעות? 158 00:06:51,320 --> 00:06:54,390 ובכן, הנה גרסה מוגדלת-בשל תמונה של זיכרון המחשב שלי. 159 00:06:54,390 --> 00:06:56,230 זה החלק התחתון של הערימה שלי. 160 00:06:56,230 --> 00:06:59,644 ואכן, בתחתית מאוד הוא מה ערימה נקראת הורה שגרתית, דרך מפוארת 161 00:06:59,644 --> 00:07:00,560 לומר שזה עיקרי. 162 00:07:00,560 --> 00:07:03,772 כך שכל מי שקרא לפונקציה f על זה אנחנו מדברים. 163 00:07:03,772 --> 00:07:05,230 אז זהו תחתית הערימה. 164 00:07:05,230 --> 00:07:06,640 כתובת שולח הוא משהו חדש. 165 00:07:06,640 --> 00:07:08,810 זה תמיד היה שם, תמיד היה בתמונה ש. 166 00:07:08,810 --> 00:07:10,440 אנחנו פשוט אף פעם לא הפנינו את תשומת לב אליו. 167 00:07:10,440 --> 00:07:15,290 כי מתברר הדרך ג עובד היא כי כאשר פונקציה אחת קוראת אחרת, 168 00:07:15,290 --> 00:07:18,780 לא רק לעשות את הטיעונים של פונקציה מקבלת דחף על הערימה, 169 00:07:18,780 --> 00:07:22,470 לא רק לעשות מקומית של הפונקציה משתנים לקבל דחף על הערימה, 170 00:07:22,470 --> 00:07:26,820 משהו שנקרא כתובה שולח גם מקבל לשים על הערימה. 171 00:07:26,820 --> 00:07:33,330 באופן ספציפי, אם שיחות עיקריות פ.ו., של עיקרי כתובת שלו בזיכרון, שור משהו, 172 00:07:33,330 --> 00:07:38,240 ביעילות מקבל לשים על הערימה כך שכאשר f נעשה הרצתו 173 00:07:38,240 --> 00:07:43,630 יודע לאן לקפוץ חזרה בטקסט קטע על מנת להמשיך וביצוע. 174 00:07:43,630 --> 00:07:47,760 >> אז אם אנחנו כאן מבחינה קונספטואלית, בעיקרי, אז f נקראת. 175 00:07:47,760 --> 00:07:50,200 איך f יודעת ש לשליטה ביד אחורית? 176 00:07:50,200 --> 00:07:52,020 ובכן, זה קצת פירורי לחם באדום כאן, 177 00:07:52,020 --> 00:07:54,978 נקרא את כתובת השולח, זה פשוט בדיקות, מה היא שכתובת שולח? 178 00:07:54,978 --> 00:07:57,039 הו, תן לי לקפוץ לראש העיקרי כאן. 179 00:07:57,039 --> 00:07:59,080 וזה קצת של פשטנות, 180 00:07:59,080 --> 00:08:00,750 בגלל האפסים ואחדים לעיקרי הם מבחינה טכנית 181 00:08:00,750 --> 00:08:01,967 עד כאן במגזר טק. 182 00:08:01,967 --> 00:08:03,800 אבל זה הרעיון. f רק צריך לדעת מה 183 00:08:03,800 --> 00:08:06,680 למקום שבי שליטת סופו של דבר חוזרת. 184 00:08:06,680 --> 00:08:09,790 >> אבל מחשבי הדרך הניחו את דברים ארוכים 185 00:08:09,790 --> 00:08:12,320 כמו משתנים מקומיים ו טיעונים הוא כזה. 186 00:08:12,320 --> 00:08:17,180 אז בחלק העליון של התמונה הזאת ב הכחול היא מסגרת המחסנית לf, אז כל מה ש 187 00:08:17,180 --> 00:08:19,630 של הזיכרון שf במיוחד הוא שימוש. 188 00:08:19,630 --> 00:08:22,990 אז בהתאם, שם לב ש בר הוא בתמונה הזאת. 189 00:08:22,990 --> 00:08:23,980 בר היה הטיעון שלו. 190 00:08:23,980 --> 00:08:27,240 ואנחנו טוענים שטיעונים ל פונקציות לקבל דחף על הערימה. 191 00:08:27,240 --> 00:08:29,910 וג, כמובן, הוא גם בתמונה זו. 192 00:08:29,910 --> 00:08:33,520 >> ורק למטרות סימנים,, שם לב בפינה השמאלית העליונה 193 00:08:33,520 --> 00:08:37,020 זה מה שיהיה ג סוגר 0 ו אז קצת למטה בצד הימין 194 00:08:37,020 --> 00:08:38,220 הוא סוגר ג 11. 195 00:08:38,220 --> 00:08:41,240 אז במילים אחרות, אתה יכול לדמיין שיש רשת של בתים 196 00:08:41,240 --> 00:08:44,380 שם, הראשון שבם הוא שמאלי עליון, תחתון שלה 197 00:08:44,380 --> 00:08:48,360 הוא האחרון של 12 בתים אלה. 198 00:08:48,360 --> 00:08:49,930 >> אבל עכשיו מנסה להריץ קדימה. 199 00:08:49,930 --> 00:08:55,580 מה עומד לקרות אם אנחנו עוברים בבר מחרוזת זה זמן רב יותר מג? 200 00:08:55,580 --> 00:08:59,130 ואנחנו לא בודקים אם זה אכן זמן רב יותר מאשר 12. 201 00:08:59,130 --> 00:09:03,146 איזה חלק של תמונה זה הולך לקבל מוחלף על ידי בתים 0, 1, 2, 3, 202 00:09:03,146 --> 00:09:07,890 נקודת נקודת נקודה, 11, ולאחר מכן רע, 12, 13 דרך 19? 203 00:09:07,890 --> 00:09:11,820 מה שהולך לקרות כאן, אם אפשר להסיק מההזמנה 204 00:09:11,820 --> 00:09:14,790 שסוגר ג 0 הוא בחלק העליון וסוגר ג 11 הוא סוג של מטה 205 00:09:14,790 --> 00:09:15,812 מימין? 206 00:09:15,812 --> 00:09:16,796 כן? 207 00:09:16,796 --> 00:09:19,260 >> קהל: ובכן, זה הולך כדי להחליף את בר * char. 208 00:09:19,260 --> 00:09:22,260 >> דוד י מלאן: כן, זה נראה כמו אתה הולך לדרוס בר char *. 209 00:09:22,260 --> 00:09:26,245 וגרוע מזה, אם אתה שולח בבאמת ארוך מחרוזת, אתה עשוי אפילו להחליף מה? 210 00:09:26,245 --> 00:09:27,460 211 00:09:27,460 --> 00:09:28,570 כתובת השולח. 212 00:09:28,570 --> 00:09:31,380 אשר שוב, הוא בדיוק כמו סימני דרך לספר את התכנית שבה 213 00:09:31,380 --> 00:09:34,060 לחזור לכאשר f נעשה להיקרא. 214 00:09:34,060 --> 00:09:37,140 >> אז מה הרעים בדרך כלל לעשות הוא אם הם נתקל תכנית 215 00:09:37,140 --> 00:09:41,290 שהם סקרנים אם הוא ניצול, מרכבה בצורה כזאת 216 00:09:41,290 --> 00:09:43,550 שהוא או היא יכולה לקחת יתרון של באג ש, 217 00:09:43,550 --> 00:09:45,720 בדרך כלל הם לא מקבלים זכות זו בפעם הראשונה. 218 00:09:45,720 --> 00:09:48,590 הם פשוט להתחיל לשלוח, למשל, מחרוזות אקראיות בתכנית שלך, 219 00:09:48,590 --> 00:09:50,260 אם במקלדת, או בכנות שהם כנראה 220 00:09:50,260 --> 00:09:52,740 לכתוב תוכנה קטנה רק ליצור באופן אוטומטי מחרוזות, 221 00:09:52,740 --> 00:09:55,430 ולהתחיל לדפוק על התכנית שלך על ידי שליחה בהרבה תשומות שונות 222 00:09:55,430 --> 00:09:56,340 באורכים שונים. 223 00:09:56,340 --> 00:09:58,990 >> ברגע שקריסות התכנית שלך, זה דבר מדהים. 224 00:09:58,990 --> 00:10:01,020 כי זה אומר שהוא או שהיא גילתה 225 00:10:01,020 --> 00:10:02,660 מה הוא כנראה אכן באג. 226 00:10:02,660 --> 00:10:05,830 ואז הם יכולים לקבל חכמים יותר ולהתחיל להתמקד יותר באופן צר 227 00:10:05,830 --> 00:10:07,420 על איך לנצל באג ש. 228 00:10:07,420 --> 00:10:11,480 בפרט, את מה שהוא או היא עלולה לעשות הוא לשלוח, במקרה הטוב, שלום. 229 00:10:11,480 --> 00:10:12,210 זה לא עניין גדול. 230 00:10:12,210 --> 00:10:14,750 זה מחרוזת זה קצר מספיק. 231 00:10:14,750 --> 00:10:18,100 אבל מה אם הוא או היא שולחת, ואנו להכליל אותו כ, 232 00:10:18,100 --> 00:10:20,890 התקפת code-- כך אפסים ואלה שעושים דברים 233 00:10:20,890 --> 00:10:25,150 כמו rm-rf, כי להסיר את כל מה מהכונן הקשיח או לשלוח דואר זבל 234 00:10:25,150 --> 00:10:27,000 או איכשהו לתקוף את המכונה? 235 00:10:27,000 --> 00:10:29,570 >> אז אם כל אחד מאלה מכתבים רק מייצג, 236 00:10:29,570 --> 00:10:32,380 מבחינה קונספטואלית, התקפה, התקפה, התקפת התקפה, קצת קוד, רע 237 00:10:32,380 --> 00:10:36,410 שמישהו כתב אחר, אבל אם האדם שהוא חכם מספיק 238 00:10:36,410 --> 00:10:40,790 לא רק כולל את כל מאותם rm-RFS, אלא גם 239 00:10:40,790 --> 00:10:46,100 יש לי כמה הבתים האחרונים שלו או שלה להיות מספר המתאים 240 00:10:46,100 --> 00:10:50,540 לכתובת שלו או קוד התקפה משלה 241 00:10:50,540 --> 00:10:53,820 שהוא או היא עברה רק על ידי מתן אותו בשורת הפקודה, 242 00:10:53,820 --> 00:10:58,760 אתה יכול למעשה להערים על המחשב לשם לב שf נעשה ביצוע, 243 00:10:58,760 --> 00:11:02,400 הו, זה זמן עבורי לקפוץ בחזרה לכתובת השולח האדומה. 244 00:11:02,400 --> 00:11:06,070 אבל בגלל שהוא או היא צריכה איכשהו חפיפת שכתובת שולח 245 00:11:06,070 --> 00:11:09,602 עם המספר שלהם, והם חכמים מספיק 246 00:11:09,602 --> 00:11:11,560 להגדיר ש מספר מתייחס, כפי שאתה 247 00:11:11,560 --> 00:11:13,740 לראות בחלק העליון הסופר פינה השמאלית יש, 248 00:11:13,740 --> 00:11:18,020 הכתובת האמיתית במחשב זיכרון של חלק מקוד ההתקפה שלהם, 249 00:11:18,020 --> 00:11:21,740 בחור רע יכול להערים על המחשב להפעלת הקוד שלו או שלה. 250 00:11:21,740 --> 00:11:23,700 >> וקוד ש, שוב, יכול להיות כל דבר. 251 00:11:23,700 --> 00:11:26,120 זה בדרך כלל נקרא קוד פגז, וזה רק 252 00:11:26,120 --> 00:11:29,030 דרך לומר שזה לא בדרך כלל משהו פשוט כמו rm-rf. 253 00:11:29,030 --> 00:11:32,340 זה בעצם משהו כמו Bash, או תכנית בפועל זה נותנת לו 254 00:11:32,340 --> 00:11:37,230 או שליטתה התכנותית לבצע כל דבר אחר שהם רוצים. 255 00:11:37,230 --> 00:11:40,210 אז בקיצור, זה כל נובע מהעובדה הפשוטה 256 00:11:40,210 --> 00:11:44,490 כי הבאג הזה המעורב לא בודק הגבולות של המערך שלך. 257 00:11:44,490 --> 00:11:47,250 ומשום שהדרך עבודת מחשבים היא שהם 258 00:11:47,250 --> 00:11:49,430 להשתמש במחסנית מ ביעילות, מבחינה קונספטואלית, 259 00:11:49,430 --> 00:11:54,830 תחתון בעד, אבל אז אלמנטים אתה דוחף אל הערימה לגדול במורד עליון, 260 00:11:54,830 --> 00:11:56,624 זה הוא בעייתי מאוד. 261 00:11:56,624 --> 00:11:58,290 עכשיו, יש דרכים לעקוף את זה. 262 00:11:58,290 --> 00:12:00,800 ולמען אמת, יש שפות שבה לעבודה בסביבה זו. 263 00:12:00,800 --> 00:12:03,100 ג'אווה היא חיסון, למשל, לנושא המסוים הזה. 264 00:12:03,100 --> 00:12:04,110 בגלל שהם לא נותנים לך עצות. 265 00:12:04,110 --> 00:12:05,943 הם לא נותנים לך כתובות זיכרון ישירות. 266 00:12:05,943 --> 00:12:08,560 אז עם הכח הזה שיש לנו לגעת בשום דבר בזיכרון 267 00:12:08,560 --> 00:12:11,580 אנחנו רוצים מגיעים, יש להודות, סיכון גדול. 268 00:12:11,580 --> 00:12:12,430 >> אז לפקוח עין. 269 00:12:12,430 --> 00:12:14,596 אם, בכנות, בחודשים או בשנים הבאות, בכל עת 270 00:12:14,596 --> 00:12:17,740 אתה קורא על כמה ניצול של תכנית או שרת, 271 00:12:17,740 --> 00:12:22,370 אם אי פעם תראה את רמז של משהו כמו התקפת גלישת מאגר, 272 00:12:22,370 --> 00:12:25,390 או הצפת מחסנית היא סוג אחר של התקפה, דומה ברוחו, 273 00:12:25,390 --> 00:12:28,770 כמה שמעורר באתר שם, אם אתה יודע את זה, 274 00:12:28,770 --> 00:12:33,170 זה כולם מדבר על רק עולה על גדותיו בגודל של איזו דמות 275 00:12:33,170 --> 00:12:36,200 מערך או מערך באופן כללי יותר. 276 00:12:36,200 --> 00:12:38,822 שאלות, אז, על זה? 277 00:12:38,822 --> 00:12:39,780 אל תנסה את זה בבית. 278 00:12:39,780 --> 00:12:41,620 279 00:12:41,620 --> 00:12:42,300 >> בסדר. 280 00:12:42,300 --> 00:12:47,270 אז malloc עד כה היה חדש שלנו חבר שבאנחנו יכולים להקצות זיכרון 281 00:12:47,270 --> 00:12:50,540 שאנחנו לא בהכרח יודעים ב מראש שאנחנו רוצים ולכן אין לנו 282 00:12:50,540 --> 00:12:52,920 לקוד קשה לנו מספרים כמו 12 תכנית. 283 00:12:52,920 --> 00:12:55,550 ברגע שהמשתמש אומר לנו כמה הנתונים שהוא או היא רוצה קלט, 284 00:12:55,550 --> 00:12:58,000 אנחנו יכולים malloc כך הרבה זיכרון. 285 00:12:58,000 --> 00:13:01,484 >> אז malloc מתברר, ל במידה שכבר משתמשים בה, 286 00:13:01,484 --> 00:13:03,900 במפורש בפעם האחרונה, ולאחר מכן אתם כבר משתמשים בה 287 00:13:03,900 --> 00:13:08,160 לgetstring ביודעין ל מספר שבועות, כל הזיכרון של malloc 288 00:13:08,160 --> 00:13:09,820 מגיע מהערימה שנקרא. 289 00:13:09,820 --> 00:13:13,852 ובגלל זה getstring, למשל, יכול להקצות זיכרון דינמי 290 00:13:13,852 --> 00:13:16,060 בלי לדעת מה אתה הולך להקליד מראש, 291 00:13:16,060 --> 00:13:21,520 למסור לך בחזרה מצביע לזיכרון ש, וזיכרון שעדיין שלך כדי לשמור על, 292 00:13:21,520 --> 00:13:24,080 גם לאחר getstring תשואות. 293 00:13:24,080 --> 00:13:27,450 משום זוכר אחרי כל זה הערימה היא כל הזמן עולה ויורד, 294 00:13:27,450 --> 00:13:27,950 למעלה ולמטה. 295 00:13:27,950 --> 00:13:30,230 וברגע שזה הולך למטה, שפירושו כל זיכרון 296 00:13:30,230 --> 00:13:33,030 פונקציה זו משמשת צריכה לא בשימוש על ידי כל אדם אחר. 297 00:13:33,030 --> 00:13:34,570 זה ערכי זבל עכשיו. 298 00:13:34,570 --> 00:13:36,120 >> אבל הערימה היא עד כאן. 299 00:13:36,120 --> 00:13:39,360 ומה שיפה הוא שmalloc כאשר malloc מקצה זיכרון עד כאן, 300 00:13:39,360 --> 00:13:42,070 זה לא השפיע, ל לרוב, על ידי הערימה. 301 00:13:42,070 --> 00:13:46,000 ולכן כל פונקציה יכולה לגשת זיכרון שכבר malloc'd, 302 00:13:46,000 --> 00:13:49,120 אפילו על ידי פונקציה כמו getstring, גם לאחר שהוא חזר. 303 00:13:49,120 --> 00:13:51,700 >> עכשיו, היפוכה של malloc ללא תשלום. 304 00:13:51,700 --> 00:13:53,900 ואכן, השלטון ש צריך להתחיל לאמץ 305 00:13:53,900 --> 00:13:58,950 היא כל, כל, כל פעם שאתה משתמש malloc את עצמך אתה חייב להשתמש חינם, סופו של דבר, 306 00:13:58,950 --> 00:14:00,280 באותו מצביע. 307 00:14:00,280 --> 00:14:03,289 כל הזמן הזה אנחנו כבר כותבים מרכבה, קוד מרכבה, מסיבות רבות. 308 00:14:03,289 --> 00:14:05,580 אבל אחד מהם היה באמצעות ספריית CS50, ש 309 00:14:05,580 --> 00:14:09,010 עצמו הוא במכוון מרכבה, זה דליפת זיכרון. 310 00:14:09,010 --> 00:14:11,410 בכל פעם שיש לך בשם getstring בשבועות האחרונים 311 00:14:11,410 --> 00:14:13,870 אנחנו מבקשים ההפעלה מערכת, לינוקס, לזיכרון. 312 00:14:13,870 --> 00:14:15,780 ואף פעם לא נתן לו פעם אחת בחזרה. 313 00:14:15,780 --> 00:14:17,730 ואת זה הוא לא, ב להתאמן, דבר טוב. 314 00:14:17,730 --> 00:14:20,330 >> וValgrind, אחד כלים שהוצגו ב4 Pset, 315 00:14:20,330 --> 00:14:22,900 הוא על כל לעזור לך עכשיו למצוא באגים כמו ש. 316 00:14:22,900 --> 00:14:27,060 אבל לשמחתם של Pset 4 אתה לא צריך להשתמש בספריית CS50 או getstring. 317 00:14:27,060 --> 00:14:31,220 אז כל הבאגים הקשורים לזיכרון סופו של דבר הולך להיות שלך. 318 00:14:31,220 --> 00:14:34,060 >> אז malloc הוא יותר מאשר רק נוח למטרה זו. 319 00:14:34,060 --> 00:14:37,420 אנחנו למעשה יכולים כעת לפתור בעיות שונות במהותו, 320 00:14:37,420 --> 00:14:41,640 ויסודו לפתור את הבעיות יותר ביעילות בהתאם להבטחתו של שבוע אפס. 321 00:14:41,640 --> 00:14:44,720 עד כה זה הכי סקסי מבנה הנתונים שהיו לנו. 322 00:14:44,720 --> 00:14:47,804 ועל ידי מבנה נתונים אני רק אומר דרך של זיכרון המשגה 323 00:14:47,804 --> 00:14:50,720 באופן שהוא מעבר לרק אומר, זו היא int, זה char. 324 00:14:50,720 --> 00:14:52,930 אנחנו יכולים להתחיל לדברים אשכול יחד. 325 00:14:52,930 --> 00:14:54,460 >> אז מערך נראה כך. 326 00:14:54,460 --> 00:14:57,270 ומה היה מפתח בכ מערך הוא שזה נותן לך 327 00:14:57,270 --> 00:14:59,724 גב אל גב נתחים זיכרון, כל אחד מהם 328 00:14:59,724 --> 00:15:02,765 הולך להיות מאותו הסוג, int, int, int, int, או char, char, char, 329 00:15:02,765 --> 00:15:03,330 char. 330 00:15:03,330 --> 00:15:04,496 אבל יש כמה חסרונות. 331 00:15:04,496 --> 00:15:06,570 זה למשל, הוא מערך של גודל שש. 332 00:15:06,570 --> 00:15:10,650 נניח שאתה ממלא את המערך הזה עם שש מספרים ולאחר מכן, מכל סיבה ש, 333 00:15:10,650 --> 00:15:13,187 המשתמש שלך רוצה לתת לי אתה מספר שביעי. 334 00:15:13,187 --> 00:15:14,020 איפה שמת את זה? 335 00:15:14,020 --> 00:15:15,490 336 00:15:15,490 --> 00:15:18,990 >> מה הפתרון אם יש לך נוצר מערך במחסנית, 337 00:15:18,990 --> 00:15:22,030 למשל, רק עם בשבוע שני סימון שהצגנו, 338 00:15:22,030 --> 00:15:23,730 סוגריים מרובעים עם מספר בפנים? 339 00:15:23,730 --> 00:15:25,160 340 00:15:25,160 --> 00:15:27,260 ובכן, יש לך שש מספרים בתיבות אלה. 341 00:15:27,260 --> 00:15:28,530 מה היית האינסטינקטים שלך להיות? 342 00:15:28,530 --> 00:15:29,973 איפה היית רוצה לשים את זה? 343 00:15:29,973 --> 00:15:30,860 >> קהל: [לא ברור] 344 00:15:30,860 --> 00:15:31,315 >> דוד י מלאן: מצטער? 345 00:15:31,315 --> 00:15:32,380 >> קהל: שים את זה בצד. 346 00:15:32,380 --> 00:15:33,796 >> דוד י מלאן: שים את זה בצד. 347 00:15:33,796 --> 00:15:35,880 אז קצת יותר בצד הימין, מחוץ לתיבה זו. 348 00:15:35,880 --> 00:15:38,710 שיהיה נחמד, אבל זה מתברר שאתה לא יכול לעשות את זה. 349 00:15:38,710 --> 00:15:41,350 כי אם אתה כבר לא שאל עבור נתח זה של זיכרון, 350 00:15:41,350 --> 00:15:44,490 זה יכול להיות במקרה שזה נמצא בשימוש על ידי כמה משתנה אחרים 351 00:15:44,490 --> 00:15:45,030 לגמרי. 352 00:15:45,030 --> 00:15:49,210 תחשוב שוב כשבוע כאשר הנחנו את השמות של Zamyla ודווין וגייב 353 00:15:49,210 --> 00:15:49,930 בזיכרון. 354 00:15:49,930 --> 00:15:51,638 הם היו, פשוטו כמשמעו, גב אל גב אל גב. 355 00:15:51,638 --> 00:15:53,550 אז אנחנו לא יכולים בהכרח לסמוך על כך שכל מה ששל 356 00:15:53,550 --> 00:15:55,800 כאן הוא זמין עבורי לשימוש. 357 00:15:55,800 --> 00:15:56,990 >> אז מה עוד אתה יכול לעשות? 358 00:15:56,990 --> 00:16:00,282 ובכן, הבין אותך פעם אחת צריך מערך של גודל שבע, 359 00:16:00,282 --> 00:16:02,490 רק אתה יכול ליצור מערך של גודל שבע ולאחר מכן להשתמש 360 00:16:02,490 --> 00:16:05,950 ללולאה או לולאה בזמן, להעתיק אותו למערך החדש, 361 00:16:05,950 --> 00:16:09,680 ואז איכשהו רק להיפטר מערך זה או פשוט להפסיק להשתמש בו. 362 00:16:09,680 --> 00:16:12,130 אבל זה לא יעיל במיוחד. 363 00:16:12,130 --> 00:16:15,340 בקיצור, מערכים לא נותנים לי אתה באופן דינמי לשנות את הגודל. 364 00:16:15,340 --> 00:16:17,900 >> אז מצד האחד אתה מקבל גישה אקראית, וזה מדהים. 365 00:16:17,900 --> 00:16:20,108 כי זה מאפשר לנו לעשות דברים כמו הפרד ומשול, 366 00:16:20,108 --> 00:16:23,100 חיפוש בינארי, שכולן יש לנו דיבר על על המסך כאן. 367 00:16:23,100 --> 00:16:24,950 אבל אתה מצייר את עצמך לפינה. 368 00:16:24,950 --> 00:16:27,810 ברגע שאתה מכה סוף המערך שלך, 369 00:16:27,810 --> 00:16:29,980 אתה צריך לעשות מאוד פעולה יקרה 370 00:16:29,980 --> 00:16:33,910 או לכתוב חבורה של קוד כולו עכשיו להתמודד עם בעיה ש. 371 00:16:33,910 --> 00:16:36,680 >> אז מה אם במקום שהיו לנו משהו שנקרא רשימה, 372 00:16:36,680 --> 00:16:38,820 או קשור רשימה בפרט? 373 00:16:38,820 --> 00:16:41,930 מה אם במקום שיש מלבנים לגבות לגבות לגבות, 374 00:16:41,930 --> 00:16:45,730 יש לנו מלבנים שישאירו קצת קצת מרחב תמרון ביניהם? 375 00:16:45,730 --> 00:16:49,670 ולמרות שאני כבר נמשך זה תמונה או מותאם תמונה זו 376 00:16:49,670 --> 00:16:54,696 מאחד הטקסטים כאן כדי לחזור ל גב אל גב מאוד מסודר, במציאות, 377 00:16:54,696 --> 00:16:56,820 אחד מהמלבנים אלה יכול להיות כאן בזיכרון. 378 00:16:56,820 --> 00:16:58,028 אחד מהם היה יכול להיות כאן. 379 00:16:58,028 --> 00:17:00,420 אחד מהם היה יכול להיות כאן, כאן, וכן הלאה. 380 00:17:00,420 --> 00:17:02,910 >> אבל מה אם אנחנו ציירנו, במקרה זה, חיצים 381 00:17:02,910 --> 00:17:05,650 המקשרים איכשהו אלה מלבנים יחד? 382 00:17:05,650 --> 00:17:08,170 ואכן, ראינו טכני גלגולו של חץ. 383 00:17:08,170 --> 00:17:09,839 384 00:17:09,839 --> 00:17:13,710 מה יש לנו בשימוש באחרון ימים ש, מתחת למכסת המנוע, 385 00:17:13,710 --> 00:17:15,210 הוא נציג של חץ? 386 00:17:15,210 --> 00:17:16,290 387 00:17:16,290 --> 00:17:17,349 מצביע, נכון? 388 00:17:17,349 --> 00:17:19,780 >> אז מה אם, במקום רק אחסון המספרים, 389 00:17:19,780 --> 00:17:23,130 כמו 9, 17, 22, 26, 34, מה אם אנחנו מאוחסנים לא 390 00:17:23,130 --> 00:17:27,079 רק מספר אבל מצביע ליד כל מספר כזה? 391 00:17:27,079 --> 00:17:30,690 כך שהרבה כמו שהיית חוט מחט דרך חבורה של בד כולו, 392 00:17:30,690 --> 00:17:32,950 דברים איכשהו קשירה יחד, יכול באופן דומה 393 00:17:32,950 --> 00:17:35,550 אנחנו עם מצביעים, כ התגלגל על ​​ידי חצים כאן, 394 00:17:35,550 --> 00:17:38,550 סוג של לארוג יחד מלבנים בודדים אלה 395 00:17:38,550 --> 00:17:41,780 על ידי יעילות באמצעות מצביע ליד כל מספר ש 396 00:17:41,780 --> 00:17:46,065 מצביע על כמה מספר הבא, ש מצביע, בתורו, כמה מספר הבא? 397 00:17:46,065 --> 00:17:47,940 אז במילים אחרות, מה ש אם אנחנו באמת רוצים 398 00:17:47,940 --> 00:17:49,820 כדי ליישם משהו כזה? 399 00:17:49,820 --> 00:17:53,610 ובכן, למרבה הצער, מלבנים אלה, לפחות אחד עם 9, 17, 22, 400 00:17:53,610 --> 00:17:57,040 וכן הלאה, אלה הם כבר לא ריבועים נחמדים עם מספרים בודדים. 401 00:17:57,040 --> 00:17:59,960 התחתון, המלבן מתחת ל -9, למשל, 402 00:17:59,960 --> 00:18:04,330 מייצג את מה שצריך להיות מצביע, 32 סיביות. 403 00:18:04,330 --> 00:18:09,460 עכשיו, אני עדיין לא מודע לכל סוג נתונים בC שנותן לך לא רק int 404 00:18:09,460 --> 00:18:11,630 אבל מצביע לגמרי. 405 00:18:11,630 --> 00:18:15,020 >> אז מה הפתרון אם אנחנו רוצים להמציא התשובה שלנו לזה? 406 00:18:15,020 --> 00:18:15,760 כן? 407 00:18:15,760 --> 00:18:16,640 >> קהל: [לא ברור] 408 00:18:16,640 --> 00:18:17,360 >> דוד י מלאן: מה זה? 409 00:18:17,360 --> 00:18:17,880 >> קהל: מבנה חדש. 410 00:18:17,880 --> 00:18:19,590 >> דוד י מלאן: כן, אז למה לא אנחנו יוצרים מבנה חדש, 411 00:18:19,590 --> 00:18:20,920 או בC, struct? 412 00:18:20,920 --> 00:18:25,990 ראינו structs לפני, אם לזמן קצר, שבו עסקנו במבנה סטודנט 413 00:18:25,990 --> 00:18:27,780 כמו זה, שהיה לו שם ובית. 414 00:18:27,780 --> 00:18:31,980 בPset 3 פריצה שבה השתמשה כל חבורה של GRect וGOvals structs-- 415 00:18:31,980 --> 00:18:34,810 כי סטנפורד נוצר כדי מידע אשכול יחד. 416 00:18:34,810 --> 00:18:38,580 אז מה אם אנחנו לוקחים את אותו הרעיון הזה של מילות מפתח "typedef" ו "struct," 417 00:18:38,580 --> 00:18:42,890 ולאחר מכן כמה דברים תלמיד ספציפי, ולהתפתח זה לבא: 418 00:18:42,890 --> 00:18:46,210 typedef struct node-- והצומת היא רק מדעי מחשב מאוד גנריות 419 00:18:46,210 --> 00:18:49,980 טווח משהו במבנה הנתונים, מיכל במבנה הנתונים. 420 00:18:49,980 --> 00:18:53,900 צומת אני טוען הוא הולכת להיות n int, לגמרי פשוט, 421 00:18:53,900 --> 00:18:58,810 ואז עוד קצת במסתוריות, קו שני זה, צומת struct * הבא. 422 00:18:58,810 --> 00:19:01,300 אבל במונחים טכניים פחות, מה זה קו שני 423 00:19:01,300 --> 00:19:02,980 של קוד בתוך הסוגריים המסולסלים? 424 00:19:02,980 --> 00:19:03,737 כן? 425 00:19:03,737 --> 00:19:04,851 >> קהל: [לא ברור] 426 00:19:04,851 --> 00:19:06,600 דוד י מלאן: מצביע לצומת אחרת. 427 00:19:06,600 --> 00:19:09,910 אז אמנם, תחביר קצת מסתורי. 428 00:19:09,910 --> 00:19:13,250 אבל אם אתה קורא את זה פשוטו כמשמעו, הבא הוא שמו של משתנה. 429 00:19:13,250 --> 00:19:14,410 מהו סוג הנתונים שלה? 430 00:19:14,410 --> 00:19:18,206 זה קצת מפורט הפעם, אבל זה של צומת struct סוג *. 431 00:19:18,206 --> 00:19:22,960 בכל פעם שראינו כוכב משהו, ש אומר שזה מצביע לאותו סוג נתונים. 432 00:19:22,960 --> 00:19:26,810 אז הבא הוא ככל הנראה מצביע לצומת struct. 433 00:19:26,810 --> 00:19:28,310 >> עכשיו, מה היא צומת struct? 434 00:19:28,310 --> 00:19:31,044 ובכן, שמתי לב שאתה רואה אותם אותן מילות בצד ימין למעלה. 435 00:19:31,044 --> 00:19:33,960 ואכן, אתה גם רואה את המילה "צומת" כאן למטה בפינה השמאלית התחתונה. 436 00:19:33,960 --> 00:19:35,640 וזה בעצם רק נוחות. 437 00:19:35,640 --> 00:19:39,930 שים לב כי בהגדרת תלמידנו יש את המילה "סטודנט" רק פעם אחת. 438 00:19:39,930 --> 00:19:42,510 וזה בגלל שתלמיד האובייקט לא היה התייחסות עצמית. 439 00:19:42,510 --> 00:19:45,340 אין שום דבר פנימי של תלמיד שצריך להצביע על תלמיד אחר, 440 00:19:45,340 --> 00:19:45,610 פרסיי. 441 00:19:45,610 --> 00:19:47,630 זה יהיה סוג של מוזר בעולם האמיתי. 442 00:19:47,630 --> 00:19:50,880 >> אבל עם צומת בצמודה רשימה, שאנחנו עושים ברצון צומת 443 00:19:50,880 --> 00:19:53,970 להיות רפרנציאלית לאובייקט דומה. 444 00:19:53,970 --> 00:19:57,900 וכך להבחין בשינוי כאן הוא לא רק מה שבפנים בסוגריים המסולסלים. 445 00:19:57,900 --> 00:20:00,800 אבל אנחנו מוסיפים את המילה "צומת" בחלק העליון, כמו גם 446 00:20:00,800 --> 00:20:02,930 הוספתו לתחתית במקום "סטודנט". 447 00:20:02,930 --> 00:20:06,000 וזה רק פרט טכני כך ש, שוב, מבנה הנתונים שלך 448 00:20:06,000 --> 00:20:11,380 יכול להיות התייחסות עצמית, כך ש צומת יכולה להצביע על עוד צומת כזה. 449 00:20:11,380 --> 00:20:13,840 >> אז מה זה סופו של דבר הולך אומר לנו? 450 00:20:13,840 --> 00:20:17,560 ובכן, בתוך אחד, הדברים האלה הוא את התוכן של הצומת שלנו. 451 00:20:17,560 --> 00:20:19,360 הדבר הזה כאן, ימני עליון, הוא פשוט כל כך 452 00:20:19,360 --> 00:20:20,860 כי, שוב, אנו יכולים להתייחס לעצמנו. 453 00:20:20,860 --> 00:20:23,401 ולאחר מכן את החומר החיצוני ביותר, למרות שהצומת היא מונח חדש, 454 00:20:23,401 --> 00:20:25,500 אולי, זה עדיין אותו דבר כמו תלמיד ומה 455 00:20:25,500 --> 00:20:27,520 היה מתחת למכסת המנוע בSPL. 456 00:20:27,520 --> 00:20:31,095 >> אז אם אנחנו עכשיו רוצים להתחיל יישום רשימה מקושר זה, 457 00:20:31,095 --> 00:20:33,220 איך ייתכן שאנו מתרגמים משהו כזה קוד? 458 00:20:33,220 --> 00:20:35,350 ובכן, בואו רק לראות דוגמא לתכנית ש 459 00:20:35,350 --> 00:20:36,840 בעצם משתמש רשימה מקושרת. 460 00:20:36,840 --> 00:20:40,870 בין קוד ההפצה של היום הוא תכנית בשם רשימת אפס. 461 00:20:40,870 --> 00:20:44,980 ואם אני מפעיל את זה אני יצרתי סופר GUI פשוט, ממשק משתמש גרפי, 462 00:20:44,980 --> 00:20:46,460 אבל זה באמת רק printf. 463 00:20:46,460 --> 00:20:50,930 ועכשיו אני מרשה לעצמי כמה תפריט options-- מחיקה, הוספה, חיפוש, 464 00:20:50,930 --> 00:20:51,750 וTraverse. 465 00:20:51,750 --> 00:20:52,630 וצא. 466 00:20:52,630 --> 00:20:55,970 אלה הם פעולות רק משותפות על מבנה נתונים הידוע ברשימת קישור. 467 00:20:55,970 --> 00:20:58,409 >> עכשיו, מחק את הולך למחוק מספר מהרשימה. 468 00:20:58,409 --> 00:21:00,200 הכנס הולך להוסיף מספר לרשימה. 469 00:21:00,200 --> 00:21:02,181 חיפוש הולך להיראות למספר ברשימה. 470 00:21:02,181 --> 00:21:04,930 וחוצה הוא רק דרך מפוארת לומר, ללכת ברשימה, 471 00:21:04,930 --> 00:21:06,245 להדפיס את זה, אבל זה הכל. 472 00:21:06,245 --> 00:21:07,720 אין לשנותו בכל דרך. 473 00:21:07,720 --> 00:21:08,570 >> אז בואו ננסה את זה. 474 00:21:08,570 --> 00:21:10,160 בואו נלך קדימה וסוג 2. 475 00:21:10,160 --> 00:21:12,710 ואז אני הולך הכנס את המספר, אומר 9. 476 00:21:12,710 --> 00:21:13,620 הזן. 477 00:21:13,620 --> 00:21:17,480 ועכשיו התכנית שלי היא פשוט מתוכנת לומר, רשימה היא עכשיו 9. 478 00:21:17,480 --> 00:21:20,190 עכשיו, אם אני הולך קדימה ו אל הכניסו שוב, תן לי 479 00:21:20,190 --> 00:21:23,680 לי ללכת קדימה ולהקטין את התצוגה ולהקליד ב17. 480 00:21:23,680 --> 00:21:25,770 עכשיו הרשימה שלי היא 9, אז 17. 481 00:21:25,770 --> 00:21:27,750 אם אני עושה להכניס שוב, בואו נדלג על אחד. 482 00:21:27,750 --> 00:21:32,400 במקום 22, כמו לכל התמונה שיש לנו כבר מסתכל כאן, תן לי לקפוץ קדימה 483 00:21:32,400 --> 00:21:34,630 והכנס 26 הבא. 484 00:21:34,630 --> 00:21:36,230 אז אני הולך להקליד 26. 485 00:21:36,230 --> 00:21:37,755 הרשימה היא כפי שאני מצפה. 486 00:21:37,755 --> 00:21:40,630 אבל עכשיו, רק כדי לראות אם הקוד הזה הולך להיות גמיש, תן לי עכשיו 487 00:21:40,630 --> 00:21:43,520 סוג 22, אשר לפחות מבחינה רעיונית, אם אנחנו 488 00:21:43,520 --> 00:21:46,520 שמירה על זה מסודרים, שהוא אכן הולך להיות עוד שער עכשיו, 489 00:21:46,520 --> 00:21:48,690 צריך ללכת בין 17 ו26. 490 00:21:48,690 --> 00:21:50,270 אז על Enter. 491 00:21:50,270 --> 00:21:51,380 ואכן, זה עובד. 492 00:21:51,380 --> 00:21:54,950 ואז עכשיו תן לי להכניס את אחרון, לתמונה, 34. 493 00:21:54,950 --> 00:21:55,450 >> בסדר. 494 00:21:55,450 --> 00:21:58,980 אז לעת עתה תן לי לקבוע כי למחוק וTraverse וחיפוש לעשות, 495 00:21:58,980 --> 00:21:59,760 למעשה, לעבוד. 496 00:21:59,760 --> 00:22:04,180 למעשה, אם אני מפעיל חיפוש, בואו לחפש את המספר 22, הזן. 497 00:22:04,180 --> 00:22:05,010 זה מצא 22. 498 00:22:05,010 --> 00:22:07,580 אז זה מה שזה תכנית רשימת אפס עושה. 499 00:22:07,580 --> 00:22:10,230 >> אבל מה הוא בעצם הולך על שמיישם את זה? 500 00:22:10,230 --> 00:22:14,530 ובכן, פעם ראשונה שאולי יש לי, ואכן יש לי, קובץ שנקרא list0.h. 501 00:22:14,530 --> 00:22:16,540 502 00:22:16,540 --> 00:22:20,690 ואי שם שביש זה קו, typedef, צומת struct, 503 00:22:20,690 --> 00:22:24,850 אז יש לי הסוגריים המסולסלים שלי, int n, ו אז struct-- מה הייתה ההגדרה? 504 00:22:24,850 --> 00:22:26,530 505 00:22:26,530 --> 00:22:28,545 צומת struct הבאה. 506 00:22:28,545 --> 00:22:29,920 507 00:22:29,920 --> 00:22:31,045 אז אנחנו צריכים את הכוכב. 508 00:22:31,045 --> 00:22:33,420 עכשיו מבחינה טכנית אנחנו נכנסים ההרגל של ציור אותו כאן. 509 00:22:33,420 --> 00:22:35,670 ייתכן שתראה ספרי לימוד ו אזכור באינטרנט לעשות את זה שם. 510 00:22:35,670 --> 00:22:36,660 זה תפקודיות שווה ערך. 511 00:22:36,660 --> 00:22:37,980 למעשה, זה אופייני קצת יותר. 512 00:22:37,980 --> 00:22:40,563 אבל אני אהיה בקנה אחד עם מה ש שעשינו בפעם שעברה, ולעשות את זה. 513 00:22:40,563 --> 00:22:42,350 ואז לבסוף, אני הולך לעשות את זה. 514 00:22:42,350 --> 00:22:45,550 >> אז בקובץ כותרת אי שם, בlist0.h 515 00:22:45,550 --> 00:22:49,200 היום הוא הגדרת struct זה, ואולי עוד כמה דברים אחרים. 516 00:22:49,200 --> 00:22:52,580 בינתיים בlist0c יש הולך להיות כמה דברים. 517 00:22:52,580 --> 00:22:54,740 אבל אנחנו הולכים רק להתחיל ולא לסיים את זה. 518 00:22:54,740 --> 00:22:59,690 List0.h הוא קובץ שאני רוצה לכלול בקובץ C שלי. 519 00:22:59,690 --> 00:23:03,910 ואז בשלב מסוים אני הולך להיות int, עיקרי, לביטול. 520 00:23:03,910 --> 00:23:06,530 ואז אני הולך יש לי כמה מטלות כאן. 521 00:23:06,530 --> 00:23:10,620 אני גם הולך ליש לי אב טיפוס, כמו חלל, חיפוש, int, 522 00:23:10,620 --> 00:23:13,610 n, שמטרתו בחיים היא כדי לחפש אלמנט. 523 00:23:13,610 --> 00:23:18,310 ולאחר מכן כאן למטה אני טוען ב הקוד של היום, חלל, חיפוש, int, n, 524 00:23:18,310 --> 00:23:21,020 לא פסיק אבל סוגריים מסולסלים פתוחים. 525 00:23:21,020 --> 00:23:25,049 ועכשיו אני רוצה לחפש איכשהו לאלמנט ברשימה זו. 526 00:23:25,049 --> 00:23:27,340 אבל אין לנו מספיק מידע על המסך עדיין. 527 00:23:27,340 --> 00:23:29,800 יש לי לא ממש ייצג את הרשימה עצמה. 528 00:23:29,800 --> 00:23:33,070 אז דרך אחת שנוכל ליישם רשימה מקושרת בתכנית 529 00:23:33,070 --> 00:23:37,520 הוא אני סוג של רוצה לעשות משהו כמו מצהיר קשור רשימה כאן. 530 00:23:37,520 --> 00:23:40,520 לשם פשטות, אני הולך לעשות זה עולמי, למרות שבאופן כללי 531 00:23:40,520 --> 00:23:41,645 לא צריך לעשות את זה יותר מדי. 532 00:23:41,645 --> 00:23:43,260 אבל זה יהיה לפשט דוגמא זו. 533 00:23:43,260 --> 00:23:45,890 אז אני רוצה להכריז רשימה עד מקושר כאן. 534 00:23:45,890 --> 00:23:47,010 עכשיו, איך ייתכן שאני עושה את זה? 535 00:23:47,010 --> 00:23:48,810 536 00:23:48,810 --> 00:23:50,750 >> הנה התמונה של רשימה מקושרת. 537 00:23:50,750 --> 00:23:53,030 ואני ממש לא יודע ברגע איך 538 00:23:53,030 --> 00:23:56,710 אני הולך ללכת על ייצוג כל כך הרבה דברים עם אחד בלבד 539 00:23:56,710 --> 00:23:58,040 משתנה בזיכרון. 540 00:23:58,040 --> 00:23:59,160 אבל תחשוב לרגע. 541 00:23:59,160 --> 00:24:00,830 כל הזמן הזה שהיינו לנו מחרוזות, שאותם אנו 542 00:24:00,830 --> 00:24:02,913 מתגלה להיות מערכים של דמויות, שאותם אנו 543 00:24:02,913 --> 00:24:05,740 חשף רק כדי להיות מצביע לתו הראשון 544 00:24:05,740 --> 00:24:08,890 במערך של תווים שהסתיים null. 545 00:24:08,890 --> 00:24:13,530 אז לפי ההיגיון הזה, ועם זה סוג תמונה של זריעת המחשבות שלך, 546 00:24:13,530 --> 00:24:17,964 מה צריכים אנחנו בעצם לכתוב בנו קוד לייצג רשימה מקושרת? 547 00:24:17,964 --> 00:24:21,130 כמה מהמידע הזה אנחנו צריכים כדי ללכוד בקוד C, היית אומר? 548 00:24:21,130 --> 00:24:22,654 549 00:24:22,654 --> 00:24:23,154 כן? 550 00:24:23,154 --> 00:24:24,738 >> קהל: אנחנו צריכים מצביע לצומת. 551 00:24:24,738 --> 00:24:26,237 דוד י מלאן: מצביע לצומת. 552 00:24:26,237 --> 00:24:29,320 בפרט, שהצומת היית שלך אינסטינקטים להיות לשמור מצביע ל? 553 00:24:29,320 --> 00:24:30,026 >> קהל: הצומת הראשונה. 554 00:24:30,026 --> 00:24:31,942 >> דוד י מלאן: כן, כנראה רק הראשון. 555 00:24:31,942 --> 00:24:34,030 ושים לב, הראשון צומת היא צורה שונה. 556 00:24:34,030 --> 00:24:37,690 זה רק חצי מהגודל של struct, כי זה אכן רק מצביע. 557 00:24:37,690 --> 00:24:44,650 אז מה שאתה אכן יכול לעשות הוא להכריז רשימה מקושרת להיות של צומת סוג *. 558 00:24:44,650 --> 00:24:47,780 ובואו פשוט נקראים לזה ראשון ולאתחל אותו לאפס. 559 00:24:47,780 --> 00:24:49,910 אז null, שוב, הוא הקרוב לתמונה כאן. 560 00:24:49,910 --> 00:24:53,620 לא רק משמש כnull כמו מיוחד ערך החזרה על דברים כמו getstring 561 00:24:53,620 --> 00:24:57,770 וmalloc, null הוא גם אפס מצביע, חוסר מצביע, 562 00:24:57,770 --> 00:24:58,430 אם תרצה. 563 00:24:58,430 --> 00:25:00,309 זה רק אומר ששום דבר עדיין כאן. 564 00:25:00,309 --> 00:25:02,100 עכשיו ראשון, אני יכול כבר בשם כל דבר הזה. 565 00:25:02,100 --> 00:25:04,200 אני יכול לקרוא לה "רשימה" או כל מספר של דברים אחרים. 566 00:25:04,200 --> 00:25:06,960 אבל אני קורא לזה "ראשון", כך ש קווים אותו בתמונה הזאת. 567 00:25:06,960 --> 00:25:10,280 אז בדיוק כמו מחרוזת יכול להיות מיוצג עם הכתובת של הבית הראשון שלה, 568 00:25:10,280 --> 00:25:11,280 כך יכולה רשימה מקושרת. 569 00:25:11,280 --> 00:25:13,480 ואנו רואים נתונים אחרים להיות מיוצגים על מבנים 570 00:25:13,480 --> 00:25:16,700 רק עם מצביע אחד, חץ 32 סיביות, מצביע 571 00:25:16,700 --> 00:25:18,740 בצומת הראשונה במבנה. 572 00:25:18,740 --> 00:25:20,340 >> אבל עכשיו בואו לצפות בעיה. 573 00:25:20,340 --> 00:25:23,230 אם אני זוכר רק בתכנית שלי את הכתובת 574 00:25:23,230 --> 00:25:27,220 של הצומת הראשונה, הראשון מלבן במבנה נתונים זה, 575 00:25:27,220 --> 00:25:31,760 מה יותר טוב היה להיות במקרה על יישום של שאר הרשימה שלי? 576 00:25:31,760 --> 00:25:35,820 מה פרט מפתח שקורה כדי להבטיח את זה באמת עובד? 577 00:25:35,820 --> 00:25:39,250 ועל ידי "באמת עובד" אני כלומר, בדומה למחרוזת, 578 00:25:39,250 --> 00:25:42,180 מאפשר לנו לעבור מהתו הראשון בשמו של דווין לשני, 579 00:25:42,180 --> 00:25:44,755 לשלישי, ל רביעי, עד הסוף, 580 00:25:44,755 --> 00:25:47,880 איך אנחנו יודעים כשאנחנו בסופו של הדבר של רשימה מקושרת שנראית כך? 581 00:25:47,880 --> 00:25:50,035 582 00:25:50,035 --> 00:25:50,660 כאשר זה null. 583 00:25:50,660 --> 00:25:53,640 ואני כבר מיוצג מסוג זה כמו כמו כוח מהנדס חשמל, 584 00:25:53,640 --> 00:25:56,420 עם ההארקה הקטנה סמל, של מיני. 585 00:25:56,420 --> 00:25:58,246 אבל זה רק אומר שnull במקרה זה. 586 00:25:58,246 --> 00:26:00,370 אתה יכול לצייר את זה כל מספר דרכים, אבל מחבר זה 587 00:26:00,370 --> 00:26:02,800 קרה להשתמש בסמל זה כאן. 588 00:26:02,800 --> 00:26:06,260 >> כל עוד אנחנו בחוטים כל צמתים הללו יחד, 589 00:26:06,260 --> 00:26:08,600 זוכר רק שבו הראשון הוא, כל כך הרבה זמן 590 00:26:08,600 --> 00:26:11,760 כפי שאנו לשים סמל מיוחד ב הצומת האחרון ברשימה, 591 00:26:11,760 --> 00:26:15,130 ואנו נשתמש null, כי זה מה יש לנו לרשותנו, 592 00:26:15,130 --> 00:26:16,480 רשימה זו אינה שלמה. 593 00:26:16,480 --> 00:26:20,190 וגם אם אני רק אתן לך מצביע האלמנט הראשון, אתה, המתכנת, 594 00:26:20,190 --> 00:26:22,486 בהחלט יכול לגשת לכל השאר. 595 00:26:22,486 --> 00:26:24,360 אבל בואו אתן את הדעה שלך לשוטט קצת, 596 00:26:24,360 --> 00:26:26,140 אם הם לא כבר די wandered-- מה 597 00:26:26,140 --> 00:26:28,723 הולך להיות זמן הריצה של מציאת כל דבר ברשימה זו? 598 00:26:28,723 --> 00:26:30,450 599 00:26:30,450 --> 00:26:33,470 לעזאזל, זה O הגדול של n, וזה לא רע, בהגינות. 600 00:26:33,470 --> 00:26:34,800 אבל זה הוא ליניארי. 601 00:26:34,800 --> 00:26:37,980 אנחנו ויתרנו על מה תכונה של מערכים על ידי ההעברה יותר 602 00:26:37,980 --> 00:26:43,130 כיוון תמונה זו של אופן דינמי שזורה יחד או צמוד צמתים? 603 00:26:43,130 --> 00:26:44,970 604 00:26:44,970 --> 00:26:46,687 אנחנו כבר ויתרנו על גישה אקראית. 605 00:26:46,687 --> 00:26:48,770 מערך הוא נחמד, כי הכל מבחינה מתמטית 606 00:26:48,770 --> 00:26:50,340 הוא גב אל גב אל גב אל גב. 607 00:26:50,340 --> 00:26:52,370 למרות שהתמונה הזאת נראה די, ואפילו 608 00:26:52,370 --> 00:26:55,830 למרות שזה נראה כמו בלוטות אלה הם יפה במרווחים, במציאות 609 00:26:55,830 --> 00:26:56,830 הם יכולים להיות בכל מקום. 610 00:26:56,830 --> 00:27:01,590 OX1, Ox50, Ox123, Ox99, אלה צמתים יכולים להיות בכל מקום. 611 00:27:01,590 --> 00:27:05,960 בגלל malloc עושה להקצות זיכרון מהערימה, אך בכל מקום בערמה. 612 00:27:05,960 --> 00:27:09,080 אתה לא בהכרח יודע שזה הולך להיות גב אל גב אל גב. 613 00:27:09,080 --> 00:27:12,460 וכך התמונה הזאת במציאות של לא הולך להיות די זה די. 614 00:27:12,460 --> 00:27:16,140 >> אז זה הולך לקחת קצת לפעול ליישום פונקציה זו. 615 00:27:16,140 --> 00:27:17,880 אז בואו ליישם חיפוש עכשיו. 616 00:27:17,880 --> 00:27:20,250 ואנו רואים סוג של דרך חכמה לעשות את זה. 617 00:27:20,250 --> 00:27:24,660 אז אם אני פונקציית חיפוש ו אני מקבל n משתנה, מספר שלם 618 00:27:24,660 --> 00:27:28,490 לחפש, אני צריך לדעת תחביר חדש להתבוננות פנימה 619 00:27:28,490 --> 00:27:32,400 של מבנה זה הצביע, למצוא n. 620 00:27:32,400 --> 00:27:33,210 אז בואו נעשיתי את זה. 621 00:27:33,210 --> 00:27:36,030 >> אז קודם כל אני הולך ללכת קדימה ולהכריז צומת *. 622 00:27:36,030 --> 00:27:39,400 ואני הולך לקרוא לזה מצביע, רק על ידי ועידה. 623 00:27:39,400 --> 00:27:41,710 ואני הולך לאתחל אותו לראשון. 624 00:27:41,710 --> 00:27:43,770 ועכשיו אני יכול לעשות את זה במספר הדרכים. 625 00:27:43,770 --> 00:27:45,436 אבל אני הולך לנקוט בגישה נפוצה. 626 00:27:45,436 --> 00:27:50,180 בעוד המצביע אינו שווה ל null, וזה תחביר תקף. 627 00:27:50,180 --> 00:27:54,550 וזה רק אומר לבצע את הפעולות הבאות, כך כל עוד אתה לא מצביע על שום דבר. 628 00:27:54,550 --> 00:27:55,800 מה אני רוצה לעשות? 629 00:27:55,800 --> 00:28:01,939 >> אם n נקודת מצביע, תנו לי לחזור לזה, equals-- שווה מה? 630 00:28:01,939 --> 00:28:03,105 איזה ערך אני מחפש? 631 00:28:03,105 --> 00:28:04,920 632 00:28:04,920 --> 00:28:06,590 N בפועל שהתקבל ב. 633 00:28:06,590 --> 00:28:09,020 אז הנה עוד תכונה של C ושפות רבות. 634 00:28:09,020 --> 00:28:13,705 למרות שצומת המבנה המכונה יש n ערך, לגיטימי לחלוטין 635 00:28:13,705 --> 00:28:17,530 יש גם ויכוח מקומי או משתנים בשם n. 636 00:28:17,530 --> 00:28:20,085 כי גם אנחנו, עם עיניים אנושיות, יכולות להבחין 637 00:28:20,085 --> 00:28:22,087 שn זה הוא ככל הנראה שונה מn זה. 638 00:28:22,087 --> 00:28:23,420 בגלל התחביר שונה. 639 00:28:23,420 --> 00:28:26,211 יש לך נקודה ומצביע, ואילו זה אחד יש אין דבר כזה. 640 00:28:26,211 --> 00:28:27,290 אז זה בסדר. 641 00:28:27,290 --> 00:28:29,120 זה בסדר לקרוא להם את אותם הדברים. 642 00:28:29,120 --> 00:28:32,380 >> אם אני אתה מוצא את זה, אני הולך רוצה לעשות משהו 643 00:28:32,380 --> 00:28:35,000 כמו להכריז שמצאנו n. 644 00:28:35,000 --> 00:28:37,930 ואנחנו נשאיר את זה כ להגיב או קוד pseudocode. 645 00:28:37,930 --> 00:28:40,190 אחר, והנה חלק מעניין, מה ש 646 00:28:40,190 --> 00:28:47,320 אני רוצה לעשות אם הצומת הנוכחית לא מכיל n שאכפת לי? 647 00:28:47,320 --> 00:28:50,700 איך אני משיג את הדברים הבאים? 648 00:28:50,700 --> 00:28:53,710 אם האצבע שלי ב רגע הוא PTR, וזה 649 00:28:53,710 --> 00:28:55,920 מצביע על מה ש הראשון הוא מצביע ב, 650 00:28:55,920 --> 00:28:59,290 איך אני מזיז את האצבע שלי לצומת הבאה בקוד? 651 00:28:59,290 --> 00:29:01,915 ובכן, מה סימני הדרך שאנחנו הולך לעקוב במקרה זה? 652 00:29:01,915 --> 00:29:03,464 653 00:29:03,464 --> 00:29:04,380 קהל: [לא ברור]. 654 00:29:04,380 --> 00:29:05,630 דוד י מלאן: כן, כל כך הקרוב. 655 00:29:05,630 --> 00:29:06,640 656 00:29:06,640 --> 00:29:09,824 אז אם אני חוזר לשלי קוד כאן, אכן, אני 657 00:29:09,824 --> 00:29:12,990 הולך קדימה ואומרים מצביע, ש רק variable-- זמני זה 658 00:29:12,990 --> 00:29:15,320 שם מוזר, PTR, אבל זה בדיוק כמו temp-- 659 00:29:15,320 --> 00:29:19,234 אני הולך להגדיר מצביע שווה לכל מה שis-- המצביע 660 00:29:19,234 --> 00:29:22,150 ושוב, זה הולך להיות מרכבה קטנה לנקודת moment-- הבאה. 661 00:29:22,150 --> 00:29:23,551 662 00:29:23,551 --> 00:29:26,550 במילים אחרות, אני הולך לקחת אותי אצבע שמצביעה בצומת זה 663 00:29:26,550 --> 00:29:31,247 כאן ואני הולך לומר, אתה יודע מה, תסתכל על השדה הבא 664 00:29:31,247 --> 00:29:33,330 ולהזיז את האצבע ל מה שזה מצביע על. 665 00:29:33,330 --> 00:29:35,163 וזה הולך לחזור, לחזור, לחזור. 666 00:29:35,163 --> 00:29:37,630 אבל כאשר עושה את האצבע שלי להפסיק לעשות משהו בכלל? 667 00:29:37,630 --> 00:29:40,095 ברגע שמה שורה של בעיטות קוד ב? 668 00:29:40,095 --> 00:29:40,970 קהל: [לא ברור] 669 00:29:40,970 --> 00:29:43,060 דוד י מלאן: אם בזמן שנקודה המצביע אינו שווה ל null. 670 00:29:43,060 --> 00:29:44,900 בשלב האצבע שלי כמה הולך להיות מצביע על null 671 00:29:44,900 --> 00:29:47,070 ואני הולך להגשים לי זה הסוף של רשימה זו. 672 00:29:47,070 --> 00:29:48,910 עכשיו, זה קצת שקר לבן לפשטות. 673 00:29:48,910 --> 00:29:51,580 מתברר שלמרות שאנחנו רק למדתי בסימון נקודה זו 674 00:29:51,580 --> 00:29:55,220 למבנים, מצביע הוא לא struct. 675 00:29:55,220 --> 00:29:56,580 ptr הוא מה? 676 00:29:56,580 --> 00:29:58,350 רק כדי להיות קטנוני יותר. 677 00:29:58,350 --> 00:29:59,720 678 00:29:59,720 --> 00:30:01,360 זה מצביע לצומת. 679 00:30:01,360 --> 00:30:03,120 זה לא צומת עצמו. 680 00:30:03,120 --> 00:30:06,650 אם לא היה לי כוכב כאן, מצביע absolutely-- זה צומת. 681 00:30:06,650 --> 00:30:08,650 זה כמו בשבוע אחד הכרזה על משתנה, 682 00:30:08,650 --> 00:30:10,120 אף שהמילה "צומת" היא חדשה. 683 00:30:10,120 --> 00:30:13,860 >> אבל ברגע שאנחנו מציגים כוכב, שזה עתה מצביע לצומת. 684 00:30:13,860 --> 00:30:17,960 ולמרבה הצער, אתה לא יכול להשתמש סימון הנקודה למצביע. 685 00:30:17,960 --> 00:30:21,070 אתה צריך להשתמש בחץ סימון, אשר, בצורה בולטת, 686 00:30:21,070 --> 00:30:23,470 הפעם הראשונה שכל פיסה תחביר נראה אינטואיטיבי. 687 00:30:23,470 --> 00:30:25,245 זה נראה ממש כמו חץ. 688 00:30:25,245 --> 00:30:26,370 וכדי שזה דבר טוב. 689 00:30:26,370 --> 00:30:28,995 וכאן למטה, פשוטו כמשמעו, נראה כמו חץ. 690 00:30:28,995 --> 00:30:31,870 אז אני חושב שזה la-- אני לא חושב שאני מבצע מעל here-- אני 691 00:30:31,870 --> 00:30:34,120 חושב שזה הקטע החדש שעבר תחביר שאנחנו הולכים לראות. 692 00:30:34,120 --> 00:30:36,500 ותודה לאל, זה אכן קצת יותר אינטואיטיבי. 693 00:30:36,500 --> 00:30:40,090 >> עכשיו, לאלה מכם ש ייתכן שיעדיף את הדרך הישנה, 694 00:30:40,090 --> 00:30:42,550 אתה עדיין יכול להשתמש בסימון הנקודה. 695 00:30:42,550 --> 00:30:45,380 אבל כמו לכל היום השני של שיחה, אנחנו ראשון 696 00:30:45,380 --> 00:30:50,530 צריך ללכת לשם, ללכת של לטפל, ולאחר מכן לגשת לשדה. 697 00:30:50,530 --> 00:30:51,897 אז זה גם נכון. 698 00:30:51,897 --> 00:30:53,730 ולמען אמת, זה הוא קצת קפדן יותר. 699 00:30:53,730 --> 00:30:56,530 אתה אומר, פשוטו כמשמעו, dereference המצביע וללכת לשם. 700 00:30:56,530 --> 00:30:59,320 ואז לתפוס .n, השדה שנקרא n. 701 00:30:59,320 --> 00:31:01,370 אבל בכנות, אף אחד לא רוצה להקליד או לקרוא את זה. 702 00:31:01,370 --> 00:31:03,620 וכך העולם המציא סימון החץ, ש 703 00:31:03,620 --> 00:31:06,980 שווה, זהה, זה רק סוכר תחבירי. 704 00:31:06,980 --> 00:31:10,570 אז דרך מפוארת של אומר את זה נראה טוב יותר, או נראה פשוטים יותר. 705 00:31:10,570 --> 00:31:12,296 >> אז עכשיו אני הולך לעשות דבר אחד אחר. 706 00:31:12,296 --> 00:31:15,420 אני הולך לומר "הפסקה" ברגע שיש לי מצאתי את זה ולכן אני לא אמשיך לחפש אותו. 707 00:31:15,420 --> 00:31:17,620 אבל זה התמצית של פונקציית חיפוש. 708 00:31:17,620 --> 00:31:21,710 אבל זה הרבה יותר קל, ב הסוף, לא ללכת דרך הקוד. 709 00:31:21,710 --> 00:31:25,570 זה אכן היישום הרשמי חיפוש בקוד ההפצה של היום. 710 00:31:25,570 --> 00:31:30,530 אני מעז לומר להוסיף שאינו במיוחד כיף ללכת דרך 711 00:31:30,530 --> 00:31:33,180 מבחינה ויזואלית, וגם לא למחוק, אפילו אם כי בסופו של היום 712 00:31:33,180 --> 00:31:35,460 הם מסתכמים למדי היוריסטיקה פשוטה. 713 00:31:35,460 --> 00:31:36,330 >> אז בואו נעשיתי את זה. 714 00:31:36,330 --> 00:31:39,250 אם תוכל הומור אותי לכאן, אני עשיתי להביא חבורה של מתח כדורים. 715 00:31:39,250 --> 00:31:40,620 הבאתי חבורה של מספרים. 716 00:31:40,620 --> 00:31:46,562 ואנחנו יכולים לקבל רק כמה מתנדבים לייצג 9, 17, 20, 22, 29, ו34? 717 00:31:46,562 --> 00:31:48,270 אז בעצם כולם מי נמצא כאן היום. 718 00:31:48,270 --> 00:31:50,170 719 00:31:50,170 --> 00:31:52,760 זה היה אחד, שתיים, שלוש, ארבעה, חמש, שישה אנשים. 720 00:31:52,760 --> 00:31:55,740 ואני כבר ביקשתי go-- לראות, לא אחד בחלק האחורי מרים את ידיהם. 721 00:31:55,740 --> 00:32:01,910 אישור, אחד, שתיים, שלוש, ארבעה, five-- תן לי לטעון balance-- שש. 722 00:32:01,910 --> 00:32:03,051 בסדר, אתה שישה לבוא בעד. 723 00:32:03,051 --> 00:32:04,050 אנחנו נצטרך אנשים אחרים. 724 00:32:04,050 --> 00:32:05,460 אנחנו הבאנו את מתח כדורים נוספים. 725 00:32:05,460 --> 00:32:08,200 ואם אתה יכול, ל רק רגע, שורה 726 00:32:08,200 --> 00:32:10,490 את עצמכם עד עתה כמו התמונה הזאת כאן. 727 00:32:10,490 --> 00:32:15,200 728 00:32:15,200 --> 00:32:15,959 >> בסדר. 729 00:32:15,959 --> 00:32:17,125 בואו נראה, מה השם שלך? 730 00:32:17,125 --> 00:32:17,550 >> קהל: אנדרו. 731 00:32:17,550 --> 00:32:18,800 >> דוד י מלאן: אנדרו, אתה מספר 9. 732 00:32:18,800 --> 00:32:19,540 נחמד לפגוש אותך. 733 00:32:19,540 --> 00:32:20,400 הנה לך. 734 00:32:20,400 --> 00:32:21,593 735 00:32:21,593 --> 00:32:22,176 קהל: ג'ן. 736 00:32:22,176 --> 00:32:22,662 דוד י מלאן: ג'ן. 737 00:32:22,662 --> 00:32:23,162 דוד. 738 00:32:23,162 --> 00:32:23,765 מספר 17. 739 00:32:23,765 --> 00:32:24,950 740 00:32:24,950 --> 00:32:25,450 כן? 741 00:32:25,450 --> 00:32:26,400 >> קהל: אני ג'וליה. 742 00:32:26,400 --> 00:32:26,980 >> דוד י מלאן: ג'וליה, דוד. 743 00:32:26,980 --> 00:32:27,545 מספר 20. 744 00:32:27,545 --> 00:32:28,507 745 00:32:28,507 --> 00:32:29,340 קהל: נוצרי. 746 00:32:29,340 --> 00:32:30,715 דוד י מלאן: נוצרי, דוד. 747 00:32:30,715 --> 00:32:31,541 מספר 22. 748 00:32:31,541 --> 00:32:32,040 ו? 749 00:32:32,040 --> 00:32:32,649 >> קהל: JP. 750 00:32:32,649 --> 00:32:33,440 דוד י מלאן: JP. 751 00:32:33,440 --> 00:32:34,880 מספר 29. 752 00:32:34,880 --> 00:32:37,080 אז קדימה ולקבל in-- אה אה. 753 00:32:37,080 --> 00:32:38,486 754 00:32:38,486 --> 00:32:38,985 אה אה. 755 00:32:38,985 --> 00:32:39,650 756 00:32:39,650 --> 00:32:40,150 המתנה. 757 00:32:40,150 --> 00:32:41,360 758 00:32:41,360 --> 00:32:42,390 20. 759 00:32:42,390 --> 00:32:43,682 למישהו יש סמן? 760 00:32:43,682 --> 00:32:44,890 קהל: יש לי טוש. 761 00:32:44,890 --> 00:32:45,660 דוד י מלאן: יש לך טוש? 762 00:32:45,660 --> 00:32:46,159 אישור. 763 00:32:46,159 --> 00:32:47,577 764 00:32:47,577 --> 00:32:49,160 והאם מישהו יש פיסת נייר? 765 00:32:49,160 --> 00:32:51,562 766 00:32:51,562 --> 00:32:52,270 שמור את ההרצאה. 767 00:32:52,270 --> 00:32:53,810 768 00:32:53,810 --> 00:32:55,362 יאללה. 769 00:32:55,362 --> 00:32:56,320 קהל: יש לנו את זה. 770 00:32:56,320 --> 00:32:57,600 דוד י מלאן: יש לנו את זה? 771 00:32:57,600 --> 00:32:58,577 בסדר, תודה לך. 772 00:32:58,577 --> 00:33:01,380 773 00:33:01,380 --> 00:33:02,520 הנה אנחנו מתחילים. 774 00:33:02,520 --> 00:33:03,582 היה זה ממך? 775 00:33:03,582 --> 00:33:04,540 אתה פשוט הצלת את היום. 776 00:33:04,540 --> 00:33:05,670 777 00:33:05,670 --> 00:33:07,220 אז 29. 778 00:33:07,220 --> 00:33:10,510 779 00:33:10,510 --> 00:33:11,110 בסדר. 780 00:33:11,110 --> 00:33:13,360 781 00:33:13,360 --> 00:33:14,890 אני באיות שגוי 29, אבל בסדר. 782 00:33:14,890 --> 00:33:15,720 קדימה. 783 00:33:15,720 --> 00:33:18,114 בסדר, אני אתן לך העט שלך בחזרה לרגע. 784 00:33:18,114 --> 00:33:19,280 אז יש לנו האנשים האלה כאן. 785 00:33:19,280 --> 00:33:20,330 בואו אחד אחר. 786 00:33:20,330 --> 00:33:23,750 גייב, אתה רוצה לשחק האלמנט הראשון כאן? 787 00:33:23,750 --> 00:33:25,705 אנחנו זקוקים לך להצביע באנשים הטובים האלה. 788 00:33:25,705 --> 00:33:26,930 789 00:33:26,930 --> 00:33:31,030 אז 9, 17, 20, 22, סוג של 29, ולאחר מכן 34. 790 00:33:31,030 --> 00:33:32,160 791 00:33:32,160 --> 00:33:33,325 האם אנחנו מאבדים מישהו? 792 00:33:33,325 --> 00:33:33,950 יש לי 34. 793 00:33:33,950 --> 00:33:36,730 איפה did-- אישור, מי שרוצה להיות 34? 794 00:33:36,730 --> 00:33:37,605 אישור, בואו תיכנס, 34. 795 00:33:37,605 --> 00:33:39,280 796 00:33:39,280 --> 00:33:41,220 בסדר, זה יהיה בהחלט שווה את השיא. 797 00:33:41,220 --> 00:33:41,550 מה שמך? 798 00:33:41,550 --> 00:33:42,040 >> קהל: פיטר. 799 00:33:42,040 --> 00:33:43,456 >> דוד י מלאן: פיטר, בחייך עד. 800 00:33:43,456 --> 00:33:46,810 בסדר, אז הנה כל חבורה של צמתים. 801 00:33:46,810 --> 00:33:49,060 כל אחד מכם חבר 'ה מייצגת אחד מהמלבנים האלה. 802 00:33:49,060 --> 00:33:51,930 וגייב, מוזר במקצת אדם החוצה, מייצג ראשון. 803 00:33:51,930 --> 00:33:54,850 אז המצביע שלו הוא קצת יותר קטן על המסך מכל אחד אחר. 804 00:33:54,850 --> 00:33:58,120 ובמקרה הזה, כל אחד משמאלך ידיים הולכת או להצביע כלפי מטה, 805 00:33:58,120 --> 00:34:01,085 ובכך מייצג את null, כך רק העדר מצביע, 806 00:34:01,085 --> 00:34:03,210 או שזה הולך להיות הצבעה בצומת לידך. 807 00:34:03,210 --> 00:34:05,440 >> אז עכשיו אם אתה מעטרים את עצמכם כמו בתמונה 808 00:34:05,440 --> 00:34:07,585 כאן, קדימה, נקודה אחד על השני, עם גייב 809 00:34:07,585 --> 00:34:11,030 בהצבעה מסוימת ב מספר 9 לייצג את הרשימה. 810 00:34:11,030 --> 00:34:14,050 אישור, ומספר 34, יד השמאל שלך צריך רק להיות הצביע על הרצפה. 811 00:34:14,050 --> 00:34:15,750 >> אוקיי, אז זה הוא הרשימה המקושרת. 812 00:34:15,750 --> 00:34:17,580 אז זהו התרחיש בשאלה. 813 00:34:17,580 --> 00:34:20,210 ואכן, זו היא נציג של כיתה של בעיות 814 00:34:20,210 --> 00:34:21,929 שאולי אתה מנסה לפתור עם קוד. 815 00:34:21,929 --> 00:34:25,020 אתה רוצה להכניס סופו של דבר אלמנט חדש לרשימה. 816 00:34:25,020 --> 00:34:27,494 במקרה זה, אנחנו הולכים תנסה להכניס את המספר 55. 817 00:34:27,494 --> 00:34:28,500 818 00:34:28,500 --> 00:34:30,860 אבל יש הולך להיות מקרים שונים לשקול. 819 00:34:30,860 --> 00:34:34,409 ואכן, זה הולך להיות אחד של התמונה הגדולה מזנונים כאן, הוא, 820 00:34:34,409 --> 00:34:35,659 מה הם המקרים השונים. 821 00:34:35,659 --> 00:34:39,120 מה הם שונה אם תנאים או סניפים שאולי יש לך בתכנית? 822 00:34:39,120 --> 00:34:42,024 >> ובכן, המספר שאתה מנסה הכנס, שבו אנו יודעים עכשיו להיות 55, 823 00:34:42,024 --> 00:34:44,650 אבל אם אתה לא יודע מראש, אני מעז לומר 824 00:34:44,650 --> 00:34:47,840 נופל לתוך לפחות שלוש מצבים אפשריים. 825 00:34:47,840 --> 00:34:49,717 איפה עשוי אלמנט חדש יהיה? 826 00:34:49,717 --> 00:34:51,050 קהל: וסוף או באמצע. 827 00:34:51,050 --> 00:34:54,150 דוד י מלאן: בסוף, ב האמצע, או בתחילת. 828 00:34:54,150 --> 00:34:56,650 אז אני טוען שיש לפחות שלוש בעיות שאנחנו צריכים לפתור. 829 00:34:56,650 --> 00:34:58,691 בואו לבחור מה אולי ניתן לטעון הפשוט ביותר 830 00:34:58,691 --> 00:35:01,090 אחד, שבו האלמנט החדש שייך בתחילת. 831 00:35:01,090 --> 00:35:04,040 אז אני הולך ליש קוד די כמו חיפוש, שבו אני פשוט כתבתי. 832 00:35:04,040 --> 00:35:07,670 ואני הולך לי PTR, ש אני מייצג כאן עם האצבע שלי, 833 00:35:07,670 --> 00:35:08,370 כרגיל. 834 00:35:08,370 --> 00:35:12,430 >> וזכור, מה ערך עשיתי לנו לאתחל ptr ל? 835 00:35:12,430 --> 00:35:15,300 אז אנחנו אותחלו זה ל null בתחילה. 836 00:35:15,300 --> 00:35:16,410 837 00:35:16,410 --> 00:35:19,770 אבל אז מה שאנחנו עושים ברגע שאנו היו בתוך פונקציית החיפוש שלנו? 838 00:35:19,770 --> 00:35:20,940 839 00:35:20,940 --> 00:35:24,870 אנחנו מגדירים את זה שווה לראשון, מה שלא אומר לעשות את זה. 840 00:35:24,870 --> 00:35:25,890 841 00:35:25,890 --> 00:35:30,570 אם אני ראשון להגדיר ptr שווה, מה ש צריכה את היד שלי באמת להיות מצביעה על? 842 00:35:30,570 --> 00:35:31,070 ימין. 843 00:35:31,070 --> 00:35:33,290 אז אם גייב ואני הולכים להיות ערכים שווים כאן, 844 00:35:33,290 --> 00:35:34,760 אנחנו צריכים שני הנקודות בבית המספר 9. 845 00:35:34,760 --> 00:35:36,420 >> אז זה היה תחילתו של הסיפור שלנו. 846 00:35:36,420 --> 00:35:38,700 ועכשיו זה רק פשוט, למרות שהתחביר הוא חדש. 847 00:35:38,700 --> 00:35:40,580 מבחינה מושגית זה רק חיפוש ליניארי. 848 00:35:40,580 --> 00:35:42,750 האם 55 שווים 9? 849 00:35:42,750 --> 00:35:45,559 או לייתר דיוק, נניח פחות מ 9. 850 00:35:45,559 --> 00:35:47,600 מכיוון שאני מנסה להבין איפה לשים את 55. 851 00:35:47,600 --> 00:35:51,270 פחות מ 9, פחות מ 17, פחות מ -20, פחות מ22, פחות מ29, 852 00:35:51,270 --> 00:35:52,510 פחות מ 34, לא. 853 00:35:52,510 --> 00:35:55,080 אז עכשיו אנחנו במקרה אחד מלפחות שלוש. 854 00:35:55,080 --> 00:35:59,910 >> אם אני רוצה להכניס 55 כאן, מה ש קווים של צורך קוד למוצאים להורג? 855 00:35:59,910 --> 00:36:01,890 איך עושה את התמונה הזאת של בני אדם צריך לשנות? 856 00:36:01,890 --> 00:36:03,181 מה עליי לעשות עם יד השמאל שלי? 857 00:36:03,181 --> 00:36:04,530 858 00:36:04,530 --> 00:36:07,360 זה צריך להיות null בתחילה, בגלל שאני בסוף הרשימה. 859 00:36:07,360 --> 00:36:09,318 ומה צריך לקרות כאן עם פיטר, זה היה? 860 00:36:09,318 --> 00:36:10,520 861 00:36:10,520 --> 00:36:12,430 ברור שהוא הולך להצביע לי. 862 00:36:12,430 --> 00:36:15,580 אז אני טוען שיש לפחות שני קווים של קוד בקוד לדוגמא מהיום 863 00:36:15,580 --> 00:36:18,570 זה הולך ליישם את זה תרחיש של הוספת 55 בזנב. 864 00:36:18,570 --> 00:36:20,950 ואני יכול לקבל הופ מישהו ורק מייצג 55? 865 00:36:20,950 --> 00:36:22,200 בסדר, אתה 55 החדשים. 866 00:36:22,200 --> 00:36:23,580 867 00:36:23,580 --> 00:36:27,054 >> אז עכשיו מה אם הבא תרחיש מגיע, 868 00:36:27,054 --> 00:36:29,720 ואנחנו רוצים להכניס ב מתחיל או ראש הרשימה זו? 869 00:36:29,720 --> 00:36:31,100 ומה השם שלך, המספר 55? 870 00:36:31,100 --> 00:36:31,420 >> קהל: ג'ק. 871 00:36:31,420 --> 00:36:32,295 >> דוד י מלאן: ג'ק? 872 00:36:32,295 --> 00:36:33,585 אישור, נחמד לפגוש אותך. 873 00:36:33,585 --> 00:36:34,210 ברוכים הבאים על סיפון. 874 00:36:34,210 --> 00:36:36,640 אז עכשיו אנחנו הולכים הכנס, למשל, המספר 5. 875 00:36:36,640 --> 00:36:39,840 הנה המקרה השני של שלוש באנו עם לפני. 876 00:36:39,840 --> 00:36:43,050 אז אם 5 שייכים בתחילת, בואו לראות איך אנחנו מגלים ש. 877 00:36:43,050 --> 00:36:46,310 אני לאתחל PTR שלי מצביע למספר 9 שוב. 878 00:36:46,310 --> 00:36:49,140 ואני הבנתי, אה, 5 היא פחות מ 9. 879 00:36:49,140 --> 00:36:50,880 אז לתקן את התמונה הזאת בשבילנו. 880 00:36:50,880 --> 00:36:54,820 של מי ידיים, גייב של או דוד של or-- מה השם של מספר 9? 881 00:36:54,820 --> 00:36:55,740 >> קהל: ג'ן. 882 00:36:55,740 --> 00:36:58,406 >> דוד י מלאן: hands-- של ג'ן איזו מהידיים שלנו צריך לשנות? 883 00:36:58,406 --> 00:36:58,905 884 00:36:58,905 --> 00:37:00,970 אוקיי, אז גייב מצביע על מה עכשיו? 885 00:37:00,970 --> 00:37:01,640 עליי. 886 00:37:01,640 --> 00:37:02,750 אני הצומת החדשה. 887 00:37:02,750 --> 00:37:04,870 אז אני רק סוג של מהלך כאן כדי לראות את זה מבחינה ויזואלית. 888 00:37:04,870 --> 00:37:06,435 ובינתיים מה אני מצביע ש? 889 00:37:06,435 --> 00:37:07,910 890 00:37:07,910 --> 00:37:09,020 ובכל זאת שבו אני אני מצביע. 891 00:37:09,020 --> 00:37:10,000 אז זהו זה. 892 00:37:10,000 --> 00:37:13,717 אז רק באמת שורה אחת של תיקוני קוד נושא ספציפי זה, זה היה נראה. 893 00:37:13,717 --> 00:37:14,800 בסדר, אז זה טוב. 894 00:37:14,800 --> 00:37:17,580 ומישהו יכול להיות מציין מיקום עבור 5? 895 00:37:17,580 --> 00:37:18,080 בואו למעלה. 896 00:37:18,080 --> 00:37:20,270 897 00:37:20,270 --> 00:37:21,320 אנחנו נוציא אותך בפעם הבאה. 898 00:37:21,320 --> 00:37:24,280 >> בסדר, אז now-- ו במאמר מוסגר, שמות 899 00:37:24,280 --> 00:37:28,510 אני לא עושה אזכור מפורש של זכות עכשיו, מצביע pred, מצביע קודמו 900 00:37:28,510 --> 00:37:31,260 ומצביע חדש, זה השמות ניתנו רק 901 00:37:31,260 --> 00:37:35,280 בקוד לדוגמא למצביעים או הידיים שלי שהוא סוג של ההצבעה סביב. 902 00:37:35,280 --> 00:37:36,060 מה שמך? 903 00:37:36,060 --> 00:37:36,700 >> קהל: כריסטין. 904 00:37:36,700 --> 00:37:37,100 >> דוד י מלאן: כריסטין. 905 00:37:37,100 --> 00:37:38,090 ברוכים הבאים על סיפון. 906 00:37:38,090 --> 00:37:42,180 בסדר, אז בואו נשקול עכשיו תרחיש מעט יותר מעצבן, 907 00:37:42,180 --> 00:37:46,350 לפי שאני רוצה להכניס משהו כמו 26 לתוך זה. 908 00:37:46,350 --> 00:37:47,090 20? 909 00:37:47,090 --> 00:37:47,590 מה? 910 00:37:47,590 --> 00:37:50,510 אלה are-- דבר טוב שיש לנו העט הזה. 911 00:37:50,510 --> 00:37:51,955 בסדר, 20. 912 00:37:51,955 --> 00:37:53,640 913 00:37:53,640 --> 00:37:57,570 אם מישהו יכול לקבל פיסה אחרת נייר מוכן, רק בcase-- בסדר. 914 00:37:57,570 --> 00:37:58,370 אה, מעניין. 915 00:37:58,370 --> 00:37:59,760 916 00:37:59,760 --> 00:38:02,390 ובכן, זה הוא דוגמא של באג הרצאה. 917 00:38:02,390 --> 00:38:03,894 אישור אז מה השם שלך שוב? 918 00:38:03,894 --> 00:38:04,560 קהל: ג'וליה. 919 00:38:04,560 --> 00:38:07,559 דוד י מלאן: ג'וליה, אתה יכול לצוץ החוצה ולהעמיד פן שאתה אף פעם לא היה שם? 920 00:38:07,559 --> 00:38:09,040 אוקיי, זה מעולם לא קרה. 921 00:38:09,040 --> 00:38:09,680 תודה לך. 922 00:38:09,680 --> 00:38:12,180 אז נניח שאנחנו רוצים להכניס ג'וליה לרשימה מקושרת זה. 923 00:38:12,180 --> 00:38:13,780 היא היא המספר 20. 924 00:38:13,780 --> 00:38:15,530 וכמובן שהיא הולך להיות שייכים ב 925 00:38:15,530 --> 00:38:17,521 begin-- אינו מצביע בשום דבר עדיין. 926 00:38:17,521 --> 00:38:20,020 אז היד שלך סוג של יכולה להיות את null או ערך כלשהו אשפה. 927 00:38:20,020 --> 00:38:21,210 בואו לספר את הסיפור מהיר. 928 00:38:21,210 --> 00:38:22,980 אני מצביע על מספר 5 זה זמן. 929 00:38:22,980 --> 00:38:23,880 לאחר מכן אני בודק את 9. 930 00:38:23,880 --> 00:38:25,130 אז אני בודק 17. 931 00:38:25,130 --> 00:38:26,247 אז אני בודק 22. 932 00:38:26,247 --> 00:38:27,650 933 00:38:27,650 --> 00:38:32,485 ואני מבין, אוו, ג'וליה צריך ללכת לפני 22. 934 00:38:32,485 --> 00:38:33,580 935 00:38:33,580 --> 00:38:34,660 אז מה צריך לקרות? 936 00:38:34,660 --> 00:38:35,786 937 00:38:35,786 --> 00:38:36,910 שידיו צריכים לשנות? 938 00:38:36,910 --> 00:38:38,360 ג'וליה, שלי, or-- מה השם שלך שוב? 939 00:38:38,360 --> 00:38:39,230 >> קהל: נוצרי. 940 00:38:39,230 --> 00:38:40,060 >> דוד י מלאן: נוצרי או? 941 00:38:40,060 --> 00:38:40,560 >> קהל: אנדי. 942 00:38:40,560 --> 00:38:40,905 >> דוד י מלאן: אנדי. 943 00:38:40,905 --> 00:38:41,654 נוצרי או אנדי? 944 00:38:41,654 --> 00:38:44,280 945 00:38:44,280 --> 00:38:45,690 אנדי צריך להצביע על? 946 00:38:45,690 --> 00:38:46,780 947 00:38:46,780 --> 00:38:47,341 ג'וליה. 948 00:38:47,341 --> 00:38:47,840 בסדר. 949 00:38:47,840 --> 00:38:48,960 אז אנדי, אתה רוצה להצביע על יוליה? 950 00:38:48,960 --> 00:38:50,120 אבל חכה רגע. 951 00:38:50,120 --> 00:38:53,260 בסיפור עד כה, אני הסוג של אחת 952 00:38:53,260 --> 00:38:56,800 בתשלום, במובן זה ש מצביע הוא הדבר זה 953 00:38:56,800 --> 00:38:57,850 נע ברשימה. 954 00:38:57,850 --> 00:39:00,800 אולי יש לנו שם לאנדי, אבל אין משתנה בשם אנדי. 955 00:39:00,800 --> 00:39:04,320 משתנה רק אחרים שיש לנו הוא ראשון, שהוא מיוצג על ידי גייב. 956 00:39:04,320 --> 00:39:07,690 >> אז זה בעצם למה כך כה יש לנו לא צריכים את זה. 957 00:39:07,690 --> 00:39:10,846 אבל עכשיו על המסך יש להזכיר שוב של מצביע pred. 958 00:39:10,846 --> 00:39:11,970 אז תן לי להיות ברור יותר. 959 00:39:11,970 --> 00:39:14,820 אם זה מצביע, היה לי טוב יותר לקבל קצת יותר אינטליגנטי 960 00:39:14,820 --> 00:39:15,950 על איטרציה שלי. 961 00:39:15,950 --> 00:39:19,580 אם לא אכפת לך שלי עובר כאן שוב, מצביע כאן, מצביע כאן. 962 00:39:19,580 --> 00:39:22,500 אבל תן לי מצביע pred, מצביע קודמו, שזה 963 00:39:22,500 --> 00:39:24,740 סוג של הצבעה על אלמנט הייתי רק ב. 964 00:39:24,740 --> 00:39:27,330 אז כשאני הולך כאן, עכשיו עדכוני יד השמאל שלי. 965 00:39:27,330 --> 00:39:29,370 כשאני הולך כאן עדכוני היד השמאלי שלי. 966 00:39:29,370 --> 00:39:33,090 ועכשיו יש לי לא רק מצביע ל האלמנט שהולך אחרי ג'וליה, 967 00:39:33,090 --> 00:39:36,300 עדיין יש לי מצביע אנדי, האלמנט לפני. 968 00:39:36,300 --> 00:39:39,430 אז יש לך גישה, במהות, פירורי לחם, אם תרצה, 969 00:39:39,430 --> 00:39:41,500 לכל המצביעים הנדרשים. 970 00:39:41,500 --> 00:39:43,710 >> אז אם אני מצביע על אנדי ואני גם מצביעים 971 00:39:43,710 --> 00:39:47,105 בנוצרי, שידיו עכשיו צריך להיות הצביע במקום אחר? 972 00:39:47,105 --> 00:39:48,770 973 00:39:48,770 --> 00:39:51,960 אז אנדי יכול כעת להצביע על ג'וליה. 974 00:39:51,960 --> 00:39:54,460 ג'וליה יכולה כעת להצביע על נוצרי. 975 00:39:54,460 --> 00:39:56,950 משום שהיא יכולה להעתיק שלי המצביע של יד ימין. 976 00:39:56,950 --> 00:40:00,044 וזה מכניס אותך בצורה יעילה בחזרה למקום הזה כאן. 977 00:40:00,044 --> 00:40:02,460 אז בקיצור, למרות שזה הוא לוקח אותנו סוג של לנצח 978 00:40:02,460 --> 00:40:04,510 לעדכן למעשה מקושר רשימה, מבין 979 00:40:04,510 --> 00:40:06,580 כי הפעולות הם פשוטים יחסית. 980 00:40:06,580 --> 00:40:10,030 זה של אחד, שתיים, שלוש שורות קוד סופו של דבר. 981 00:40:10,030 --> 00:40:12,780 אבל עוטף אותם שורות קוד מן הסתם 982 00:40:12,780 --> 00:40:16,350 זה קצת היגיון שיעילות שואל את השאלה, איפה אנחנו? 983 00:40:16,350 --> 00:40:18,970 האם אנחנו בתחילתו, האמצע, או הסוף? 984 00:40:18,970 --> 00:40:21,890 >> עכשיו, בהחלט יש כמה אחרים פעולות שאנו עשויים ליישם. 985 00:40:21,890 --> 00:40:24,880 ואת התמונות האלה לכאן רק לתאר מה בדיוק עשינו עם בני אדם. 986 00:40:24,880 --> 00:40:26,080 מה לגבי ההסרה? 987 00:40:26,080 --> 00:40:30,650 אם אני רוצה, למשל, להסיר את המספר 34 או 55, 988 00:40:30,650 --> 00:40:34,680 אולי יש לי את אותו סוג של קוד, אבל אני הולך לצריך שלבים אחד או שניים. 989 00:40:34,680 --> 00:40:36,110 משום מה חדש? 990 00:40:36,110 --> 00:40:40,460 אם אני מסיר מישהו בסוף, כמו מספר 55 ולאחר מכן 34, 991 00:40:40,460 --> 00:40:42,995 מה גם שיש לשנות כמו שאני עושה את זה? 992 00:40:42,995 --> 00:40:44,870 יש לי לא evict-- מה השם שלך שוב? 993 00:40:44,870 --> 00:40:45,380 >> קהל: ג'ק. 994 00:40:45,380 --> 00:40:46,255 >> דוד י מלאן: ג'ק. 995 00:40:46,255 --> 00:40:49,770 צריך לא רק evict-- ג'ק חינם אני, כך, פשוטו כמשמעו, קורא ג'ק החופשי, או לפחות 996 00:40:49,770 --> 00:40:53,530 מדי המצביע יש, אבל עכשיו מה צריך להשתנות עם פיטר? 997 00:40:53,530 --> 00:40:55,510 ידו טובה יותר להתחיל כלפי מטה. 998 00:40:55,510 --> 00:40:59,300 כי ברגע שאני קורא חינם על ג'ק, אם של פיטר עדיין מצביע על ג'ק 999 00:40:59,300 --> 00:41:02,530 ולכן אני שומר חוצים הרשימה והגישה מצביע זה, 1000 00:41:02,530 --> 00:41:05,650 זה רגע שבי פילוח ידידנו הוותיק פגם באמת עשוי לבעוט ב. 1001 00:41:05,650 --> 00:41:07,860 בגלל שנתנו בחזרה זיכרון לג'ק. 1002 00:41:07,860 --> 00:41:10,760 >> אתה יכול להישאר שם במבוכה לרגע. 1003 00:41:10,760 --> 00:41:13,410 כי יש לנו רק כמה פעולות סופיות לשקול. 1004 00:41:13,410 --> 00:41:15,600 הסרת ראש הרשימה, או beginning-- וזה אחד של 1005 00:41:15,600 --> 00:41:16,349 קצת מעצבן. 1006 00:41:16,349 --> 00:41:19,640 מכיוון שאנו צריכים לדעת שגייב הוא סוג של מיוחד בתכנית זו. 1007 00:41:19,640 --> 00:41:21,440 כי אכן, יש לו המצביע שלו. 1008 00:41:21,440 --> 00:41:24,860 הוא לא רק שהצביע על, כפי שכמעט כל אחד אחר כאן. 1009 00:41:24,860 --> 00:41:28,112 >> לכן, כאשר ראש הרשימה הוא הוסר, שידיו צריכים לשנות עכשיו? 1010 00:41:28,112 --> 00:41:29,070 מה שמך שוב? 1011 00:41:29,070 --> 00:41:29,450 >> קהל: כריסטין. 1012 00:41:29,450 --> 00:41:31,408 >> דוד י מלאן: אני נורא בשמות, כנראה. 1013 00:41:31,408 --> 00:41:34,011 אז כריסטין וגייב, ידיים שצריכים לשנות 1014 00:41:34,011 --> 00:41:36,510 כאשר אנו מנסים להסיר את כריסטין, מספר 5, מהתמונה? 1015 00:41:36,510 --> 00:41:37,550 1016 00:41:37,550 --> 00:41:38,820 אוקיי, אז בואו נעשה את גייב. 1017 00:41:38,820 --> 00:41:40,950 גייב הולך להצביע, ככל הנראה, בבית המספר 9. 1018 00:41:40,950 --> 00:41:42,230 1019 00:41:42,230 --> 00:41:44,642 אבל מה הלאה צריך לקרות? 1020 00:41:44,642 --> 00:41:46,600 קהל: כריסטין צריך להיות null [לא ברור]. 1021 00:41:46,600 --> 00:41:50,244 דוד י מלאן: בסדר, אנחנו כנראה צריכים make-- שמעתי "null" אי שם. 1022 00:41:50,244 --> 00:41:51,410 קהל: Null וחופשי שלה. 1023 00:41:51,410 --> 00:41:51,855 דוד י מלאן: null מה? 1024 00:41:51,855 --> 00:41:53,074 קהל: Null וחופשי שלה. 1025 00:41:53,074 --> 00:41:54,490 דוד י מלאן: ריק וחופשי שלה. 1026 00:41:54,490 --> 00:41:55,422 אז זה קל מאוד. 1027 00:41:55,422 --> 00:41:58,380 וזה מושלם כי אתה עכשיו סוג לעמוד שם, לא שייך. 1028 00:41:58,380 --> 00:42:00,430 מכיוון שאתה כבר מנותק מהרשימה. 1029 00:42:00,430 --> 00:42:02,820 היית יעיל התייתם מהרשימה. 1030 00:42:02,820 --> 00:42:07,770 וכך היינו לנו טוב יותר להתקשר חינם עכשיו על כריסטין לתת הזיכרון הזה חזרה. 1031 00:42:07,770 --> 00:42:10,240 אחרת כל פעם שאנחנו למחוק צומת מהרשימה 1032 00:42:10,240 --> 00:42:14,230 אנחנו יכולים להיות מה שהופך את הרשימה קצר יותר, אבל לא ממש יורד 1033 00:42:14,230 --> 00:42:15,096 הגודל בזיכרון. 1034 00:42:15,096 --> 00:42:17,720 ולכן אם אנחנו שומרים על הוספה ו הוספה, הוספת דברים לרשימה, 1035 00:42:17,720 --> 00:42:19,280 המחשב שלי יכול לקבל איטי יותר ולאט לאט, 1036 00:42:19,280 --> 00:42:21,740 כי אני פועל מתוך זיכרון, גם אם אני לא ממש 1037 00:42:21,740 --> 00:42:25,580 באמצעות הבתים של קריסטין זיכרון יותר. 1038 00:42:25,580 --> 00:42:28,500 >> אז בסופו של הדבר יש אחרים תרחישים, של הסרת course-- 1039 00:42:28,500 --> 00:42:30,640 ב, הסרת האמצע בסוף, כפי שראינו. 1040 00:42:30,640 --> 00:42:32,348 אבל מעניין יותר אתגר כרגע הוא 1041 00:42:32,348 --> 00:42:34,770 הולך להיות לשקול בדיוק מה הוא זמן הריצה. 1042 00:42:34,770 --> 00:42:36,640 אז לא רק אתה יכול לשמור עליך פיסות נייר, אם, גייב, 1043 00:42:36,640 --> 00:42:38,640 לא היית אכפת לו לתת כולם לחץ כדור. 1044 00:42:38,640 --> 00:42:42,100 תודה רבה לך לרשימה המקושרת שלנו מתנדבים כאן, אם אתה יכול. 1045 00:42:42,100 --> 00:42:45,320 >> [מחיאות כפות] 1046 00:42:45,320 --> 00:42:46,700 >> דוד י מלאן: בסדר. 1047 00:42:46,700 --> 00:42:51,110 אז כמה אנליטיים שאלות לאחר מכן, אם הייתי יכול. 1048 00:42:51,110 --> 00:42:59,670 ראינו סימון זה לפני, O גדול ואומגה, גבול עליון 1049 00:42:59,670 --> 00:43:02,520 וחסמים התחתונים על זמן ריצה של כמה אלגוריתם. 1050 00:43:02,520 --> 00:43:04,950 אז בואו נשקול רק כמה שאלות. 1051 00:43:04,950 --> 00:43:07,090 >> אחד, ואנחנו אמרו את זה לפני, מה הריצה 1052 00:43:07,090 --> 00:43:10,647 זמן של חיפוש אחר רשימה במונחים של O הגדול? 1053 00:43:10,647 --> 00:43:13,480 מה גבול עליון על הריצה זמן של חיפוש רשימה מקושרת 1054 00:43:13,480 --> 00:43:16,340 כפי שהיא מתבצעת על ידי המתנדבים שלנו כאן? 1055 00:43:16,340 --> 00:43:17,820 זה O הגדול של n, ליניארי. 1056 00:43:17,820 --> 00:43:20,630 משום שבמקרה הגרוע ביותר, האלמנט, כמו 55, 1057 00:43:20,630 --> 00:43:23,830 אנחנו יכולים להיות מחפשים עשויים להיות בי ג'ק היה, כל הדרך בסוף. 1058 00:43:23,830 --> 00:43:28,250 ולמרבה הצער, בניגוד למערך אנו לא יכולים לקבל מפוארים זה זמן. 1059 00:43:28,250 --> 00:43:31,820 למרות שכל בני האדם שלנו היו מסודרים מאלמנטים קטנים, 5, 1060 00:43:31,820 --> 00:43:35,900 כל הדרך עד לאלמנט הגדול יותר, 55, זה בדרך כלל דבר טוב. 1061 00:43:35,900 --> 00:43:38,815 אבל מה עושה הנחה ש כבר לא מאפשר לנו לעשות? 1062 00:43:38,815 --> 00:43:39,775 1063 00:43:39,775 --> 00:43:40,650 קהל: [לא ברור] 1064 00:43:40,650 --> 00:43:40,920 דוד י מלאן: תגיד את זה שוב? 1065 00:43:40,920 --> 00:43:41,800 קהל: גישה אקראית. 1066 00:43:41,800 --> 00:43:43,049 דוד י מלאן: גישה אקראית. 1067 00:43:43,049 --> 00:43:46,330 וזה בתור זה אומר שאנחנו יכולים לא עוד להשתמש אפסים, אינטואיציה חלשה, 1068 00:43:46,330 --> 00:43:49,365 ומובן מאליו של שימוש בינארי לחפש ופרד ומשול. 1069 00:43:49,365 --> 00:43:51,240 כי למרות שאנחנו בני אדם כמובן יכולים 1070 00:43:51,240 --> 00:43:54,610 רואה שאנדי או נוצרי היו בערך באמצע הרשימה, 1071 00:43:54,610 --> 00:43:57,670 רק אנחנו יודעים שכ מחשב על ידי רפרוף ברשימה 1072 00:43:57,670 --> 00:43:59,029 מההתחלה. 1073 00:43:59,029 --> 00:44:00,570 אז אנחנו כבר ויתרנו כי גישה אקראית. 1074 00:44:00,570 --> 00:44:04,380 >> O כל כך הגדול של n כרגע הוא עליון מחויב בזמן החיפוש שלנו. 1075 00:44:04,380 --> 00:44:07,920 מה לגבי אומגה של החיפוש שלנו? 1076 00:44:07,920 --> 00:44:11,535 מה גבול תחתון על חיפוש עבור חלק מספר ברשימה זו? 1077 00:44:11,535 --> 00:44:12,410 קהל: [לא ברור] 1078 00:44:12,410 --> 00:44:13,040 דוד י מלאן: תגיד את זה שוב? 1079 00:44:13,040 --> 00:44:13,420 קהל: אחת. 1080 00:44:13,420 --> 00:44:13,800 דוד י מלאן: אחת. 1081 00:44:13,800 --> 00:44:14,760 אז בפעם קבועה. 1082 00:44:14,760 --> 00:44:17,020 במקרה הטוב ביותר, כריסטין הוא אכן בתחילת הרשימה. 1083 00:44:17,020 --> 00:44:19,020 ואנחנו מחפשים מספר 5, אז מצאנו אותה. 1084 00:44:19,020 --> 00:44:19,787 אז לא ביג דיל. 1085 00:44:19,787 --> 00:44:22,370 אבל היא חייבת להיות ב תחילתה של הרשימה במקרה זה. 1086 00:44:22,370 --> 00:44:23,745 מה לגבי משהו כמו מחיקה? 1087 00:44:23,745 --> 00:44:24,717 1088 00:44:24,717 --> 00:44:26,300 מה אם אתה רוצה למחוק את רכיב? 1089 00:44:26,300 --> 00:44:29,200 מה הגבול העליון וגבול תחתון על מחיקת משהו ממקושר 1090 00:44:29,200 --> 00:44:29,699 רשימה? 1091 00:44:29,699 --> 00:44:35,195 1092 00:44:35,195 --> 00:44:36,070 קהל: [לא ברור] 1093 00:44:36,070 --> 00:44:36,420 דוד י מלאן: תגיד את זה שוב? 1094 00:44:36,420 --> 00:44:37,067 קהל: n. 1095 00:44:37,067 --> 00:44:38,900 דוד י מלאן: n הוא אכן גבול העליון. 1096 00:44:38,900 --> 00:44:41,700 משום שבמקרה הגרוע ביותר שאנו מנסים למחוק ג'ק, כמו שאנחנו פשוט עשינו. 1097 00:44:41,700 --> 00:44:43,050 הוא כל הדרך בסוף. 1098 00:44:43,050 --> 00:44:45,419 לוקח אותנו לנצח, או n צעדים כדי למצוא אותו. 1099 00:44:45,419 --> 00:44:46,460 אז זה גבול עליון. 1100 00:44:46,460 --> 00:44:47,430 זה ליניארי, בטוח. 1101 00:44:47,430 --> 00:44:50,970 והמקרה הטוב ביותר זמן ריצה, או החסמים התחתונים במקרה הטוב 1102 00:44:50,970 --> 00:44:51,975 יהיה זמן קבוע. 1103 00:44:51,975 --> 00:44:54,600 כי אולי אנחנו מנסים למחוק כריסטין, ואנחנו רק מזל 1104 00:44:54,600 --> 00:44:55,558 היא בתחילת. 1105 00:44:55,558 --> 00:44:56,350 עכשיו חכה רגע. 1106 00:44:56,350 --> 00:44:59,370 גייב היה גם בתחילת, והיה לנו גם לעדכן את גייב. 1107 00:44:59,370 --> 00:45:01,150 כך שלא היה רק ​​צעד אחד. 1108 00:45:01,150 --> 00:45:04,210 אז האם זה אכן קבוע זמן, במקרה הטוב, 1109 00:45:04,210 --> 00:45:06,345 כדי להסיר את האלמנט הקטן ביותר? 1110 00:45:06,345 --> 00:45:07,360 1111 00:45:07,360 --> 00:45:10,960 זה, למרות שזה יכול להיות שתי, שלוש, או אפילו 100 שורות קוד, 1112 00:45:10,960 --> 00:45:14,000 אם זה אותו המספר של קווים, לא בחלק הלולאה, 1113 00:45:14,000 --> 00:45:16,577 ובלתי תלוי בגודל של הרשימה, באופן מוחלט. 1114 00:45:16,577 --> 00:45:18,660 מחיקת האלמנט ב תחילתה של הרשימה, 1115 00:45:18,660 --> 00:45:21,940 גם אם אנחנו צריכים להתמודד עם גייב, עדיין זמן קבוע. 1116 00:45:21,940 --> 00:45:24,220 >> אז זה נראה כמו צעד מאסיבי אחורה. 1117 00:45:24,220 --> 00:45:27,000 ואיזה בזבוז של זמן אם, בשבוע אחד ובשבוע ש 1118 00:45:27,000 --> 00:45:30,250 אפס שהיו לנו לא רק קוד pseudocode אבל קוד בפועל 1119 00:45:30,250 --> 00:45:35,780 כדי ליישם משהו שהוא יומן n בסיס, או להתחבר, ולא, של n, בסיס 2, 1120 00:45:35,780 --> 00:45:37,150 במונחים של זמן הריצה שלה. 1121 00:45:37,150 --> 00:45:40,710 אז למה לעזאזל היינו רוצים להתחיל באמצעות משהו כמו רשימה מקושרת? 1122 00:45:40,710 --> 00:45:41,517 כן. 1123 00:45:41,517 --> 00:45:44,022 >> קהל: אז אתה יכול להוסיף אלמנטים למערך. 1124 00:45:44,022 --> 00:45:46,230 דוד י מלאן: אז אתה יכול להוסיף אלמנטים למערך. 1125 00:45:46,230 --> 00:45:47,550 וגם את זה הוא נושאיות. 1126 00:45:47,550 --> 00:45:49,740 ואנחנו נמשיך לראות זה, זה trade-off, הרבה 1127 00:45:49,740 --> 00:45:51,573 כמו שראינו trade-off עם סוג המיזוג. 1128 00:45:51,573 --> 00:45:54,606 אנחנו באמת יכולים להאיץ את חיפוש או מיון, ולא, 1129 00:45:54,606 --> 00:45:57,480 אם אנחנו מבלים מרחב קצת יותר ו יש לי נתח נוסף של זיכרון 1130 00:45:57,480 --> 00:45:58,760 או מערך לסוג מיזוג. 1131 00:45:58,760 --> 00:46:01,270 אבל אנחנו מבלים יותר חלל, אבל אנחנו לחסוך זמן. 1132 00:46:01,270 --> 00:46:04,820 במקרה זה, אנחנו ויתור על זמן אבל אנחנו 1133 00:46:04,820 --> 00:46:08,170 צובר גמישות, הדינמיות אם תרצה, 1134 00:46:08,170 --> 00:46:10,280 שהוא ללא ספק תכונה חיובית. 1135 00:46:10,280 --> 00:46:11,520 >> כמו כן, אנו מבלים בחלל. 1136 00:46:11,520 --> 00:46:13,710 באיזה מובן הוא קשור רשימה יקרה יותר 1137 00:46:13,710 --> 00:46:15,700 במונחים של שטח מאשר מערך? 1138 00:46:15,700 --> 00:46:18,379 1139 00:46:18,379 --> 00:46:19,920 איפה השטח הנוסף מגיע? 1140 00:46:19,920 --> 00:46:20,460 כן? 1141 00:46:20,460 --> 00:46:21,800 >> קהל: [לא ברור] מצביע. 1142 00:46:21,800 --> 00:46:23,310 >> דוד י מלאן: כן, אנחנו יש גם את המצביע. 1143 00:46:23,310 --> 00:46:25,560 אז זה minorly מעצבן שבכבר לא 1144 00:46:25,560 --> 00:46:27,780 אני אחסון רק int לייצג int. 1145 00:46:27,780 --> 00:46:30,990 אני אחסון int ו מצביע, שהוא גם 32 סיביות. 1146 00:46:30,990 --> 00:46:33,470 אז, פשוטו כמשמעו, אני מכפיל כמות השטח מעורבת. 1147 00:46:33,470 --> 00:46:36,040 אז זה trade-off, אבל שהוא במקרה של int. 1148 00:46:36,040 --> 00:46:39,580 נניח שאתה לא אחסון int, אבל מניח שכל אחד מהמלבנים האלה 1149 00:46:39,580 --> 00:46:43,290 או כל אחד מבני האדם אלה מייצג מילה, מילה אנגלית ש 1150 00:46:43,290 --> 00:46:46,430 יכול להיות חמישה תווים, 10 דמויות, אולי אפילו יותר. 1151 00:46:46,430 --> 00:46:49,940 ואז מוסיף רק 32 יותר ביטים יכול להיות פחות מזה עניין גדול. 1152 00:46:49,940 --> 00:46:52,160 >> מה אם כל אחד מהתלמידים בהפגנה 1153 00:46:52,160 --> 00:46:55,107 היו, פשוטו כמשמעו, structs סטודנט ש יש שמות ובתים, ואולי 1154 00:46:55,107 --> 00:46:57,065 מספרי טלפון וטוויטר מטפל וכדומה. 1155 00:46:57,065 --> 00:46:59,564 אז כל השדות התחלנו מדבר על היום האחר, 1156 00:46:59,564 --> 00:47:02,410 הרבה פחות מזה עניין גדול כ צמתים שלנו לקבל יותר מעניינים 1157 00:47:02,410 --> 00:47:05,972 וגדול לבלות, אה, נוסף מצביע רק כדי לקשר אותם יחד. 1158 00:47:05,972 --> 00:47:07,180 אבל אכן, זה trade-off. 1159 00:47:07,180 --> 00:47:09,560 ואכן, הקוד הוא יותר מורכב, כפי שאתה 1160 00:47:09,560 --> 00:47:11,770 לראות תוך מעבר דוגמא מסוימת ש. 1161 00:47:11,770 --> 00:47:14,302 אבל מה יש אם היו כמה גביע קדוש כאן. 1162 00:47:14,302 --> 00:47:17,010 מה אם אנחנו לא לוקחים צעד אחורה אבל צעד ענק קדימה 1163 00:47:17,010 --> 00:47:19,180 וליישם נתונים מבנה שדרכו אנחנו 1164 00:47:19,180 --> 00:47:22,870 ניתן למצוא אלמנטים כמו ג'ק או כריסטין או כל אלמנטים אחרים 1165 00:47:22,870 --> 00:47:25,870 במערך זה בזמן קבוע אמיתי? 1166 00:47:25,870 --> 00:47:26,920 חיפוש הוא קבוע. 1167 00:47:26,920 --> 00:47:28,320 מחיקה היא קבועה. 1168 00:47:28,320 --> 00:47:29,570 הכנס הוא קבוע. 1169 00:47:29,570 --> 00:47:32,260 כל הפעולות הללו הם קבועים. 1170 00:47:32,260 --> 00:47:33,750 זה יהיה הגביע הקדוש שלנו. 1171 00:47:33,750 --> 00:47:36,690 וזה מקום שבו אנו יאסוף את הפעם הבאה. 1172 00:47:36,690 --> 00:47:38,600 אז נתראה. 1173 00:47:38,600 --> 00:47:39,371