1
00:00:00,000 --> 00:00:10,900

2
00:00:10,900 --> 00:00:15,860
>> 1 SPEAKER: בסדר, אז זה
CS50 זה סוף השבוע חמש.

3
00:00:15,860 --> 00:00:19,220
וזוכר שהפעם האחרונה ש
התחיל להסתכל על הנתונים להשתכלל

4
00:00:19,220 --> 00:00:22,310
מבנים שהתחילו לפתור
בעיות, שהחלו להציג

5
00:00:22,310 --> 00:00:25,640
בעיות חדשות, אבל המפתח לזה
היה הסוג של השחלה ש

6
00:00:25,640 --> 00:00:27,940
התחיל לעשות מצומת לצומת.

7
00:00:27,940 --> 00:00:30,085
אז זה כמובן הוא
רשימה מקושרת ביחידים.

8
00:00:30,085 --> 00:00:31,960
ועל ידי קשור ביחידות,
אני אומר שיש רק אחד

9
00:00:31,960 --> 00:00:33,380
חוט בין כל אחד מצומת אלה.

10
00:00:33,380 --> 00:00:35,890
מתברר שאתה יכול לעשות להשתכלל
דברים כמו רשימות מקושרות כפליים

11
00:00:35,890 --> 00:00:38,470
לפי שיש לך חץ
הולך בשני הכיוונים, ש

12
00:00:38,470 --> 00:00:40,320
יכול לעזור עם יעילות מסוימת.

13
00:00:40,320 --> 00:00:42,000
אבל זה פתר את הבעיה?

14
00:00:42,000 --> 00:00:43,500
מה בעיה שזה יפתור?

15
00:00:43,500 --> 00:00:46,620
מדוע אכפת לנו ביום שני?

16
00:00:46,620 --> 00:00:49,820
למה, בתאוריה, לא אכפת לנו ביום שני?

17
00:00:49,820 --> 00:00:50,630
מה זה עושה?

18
00:00:50,630 --> 00:00:51,950
>> קהל: אנחנו יכולים באופן דינמי לשנות את גודלו.

19
00:00:51,950 --> 00:00:53,740
>> 1 מרצה: אוקיי, אז אנחנו יכולים
באופן דינמי לשנות את גודלו.

20
00:00:53,740 --> 00:00:54,710
כל הכבוד לשניכם.

21
00:00:54,710 --> 00:00:57,560
אז אתה יכול לשנות את גודל דינמי זה
מבנה נתונים, ואילו מערך,

22
00:00:57,560 --> 00:01:00,760
כזכור, אתה צריך לדעת
מראש כמה מקום שאתה רוצה

23
00:01:00,760 --> 00:01:03,870
ואם אתה צריך קצת יותר
מרחב, אתה סוג של מזל.

24
00:01:03,870 --> 00:01:05,560
אתה צריך ליצור מערך חדש לגמרי.

25
00:01:05,560 --> 00:01:07,893
אתה צריך להעביר את כולך
נתונים מאחד לשני,

26
00:01:07,893 --> 00:01:10,600
סופו של דבר לשחרר את המערך הישן
אם אתה יכול, ולאחר מכן להמשיך.

27
00:01:10,600 --> 00:01:13,891
שפשוט מרגיש מאוד יקר ומאוד
לא יעיל, ואכן זה יכול להיות.

28
00:01:13,891 --> 00:01:14,890
אבל זה לא כל כך טוב.

29
00:01:14,890 --> 00:01:18,180
אנו משלמים מחיר, מה שהיה אחד
של המחירים יותר ברורים לנו

30
00:01:18,180 --> 00:01:20,550
לשלם באמצעות רשימה מקושרת?

31
00:01:20,550 --> 00:01:22,825
>> קהל: אנחנו צריכים להשתמש
רווח כפול עבור כל אחד.

32
00:01:22,825 --> 00:01:25,200
1 SPEAKER: כן, ולכן אנחנו צריכים
לפחות כפליים שטח.

33
00:01:25,200 --> 00:01:27,700
למעשה, הבנתי של תמונה זו
אפילו קצת מטעה,

34
00:01:27,700 --> 00:01:32,200
כי על IDE CS50 בהרבה מודרני
מחשבים, מצביע או כתובת

35
00:01:32,200 --> 00:01:33,700
אינו למעשה ארבעה בתים.

36
00:01:33,700 --> 00:01:36,090
זה לעתים קרובות מאוד אלה
ימים שמונה בתים, ש

37
00:01:36,090 --> 00:01:38,530
פירוש התחתון ביותר
מלבנים יש במציאות

38
00:01:38,530 --> 00:01:40,900
הם סוג של פי שניים
גדול כמו מה שנמשך,

39
00:01:40,900 --> 00:01:44,409
מה שאומר שאתה משתמש בשלוש פעמים כ
הרבה מקום כמו שיש לנו בדרך אחרת.

40
00:01:44,409 --> 00:01:46,700
עכשיו באותו הזמן, אנחנו
עדיין מדברים בתים, נכון?

41
00:01:46,700 --> 00:01:49,140
אנחנו לא בהכרח מדברים
מגה בייט או ג 'יגה,

42
00:01:49,140 --> 00:01:51,000
אלא אם כן נתונים אלה מבנים לקבל גדולים.

43
00:01:51,000 --> 00:01:54,510
>> וכך היום אנחנו מתחילים לשקול
איך אנחנו יכולים לחקור נתונים

44
00:01:54,510 --> 00:01:57,310
בצורה יעילה יותר אם ב
נתונים למעשה נעשה גדולים יותר.

45
00:01:57,310 --> 00:02:00,360
אבל בואו ננסה canonicalize
הפעולות ראשונה

46
00:02:00,360 --> 00:02:02,460
שאתה יכול לעשות באלה
סוגים של מבני נתונים.

47
00:02:02,460 --> 00:02:04,790
אז משהו כמו מקושר
רשימה בדרך כלל תומכת ב

48
00:02:04,790 --> 00:02:07,514
פעולות רוצים למחוק,
הכנס, ולחפש.

49
00:02:07,514 --> 00:02:08,639
ומה אני מתכוון?

50
00:02:08,639 --> 00:02:11,222
זה רק אומר שבדרך כלל,
אם אנשים משתמשים רשימה מקושרת,

51
00:02:11,222 --> 00:02:14,287
הם או מישהו אחר יישם
פונקציות כמו למחוק, להוסיף,

52
00:02:14,287 --> 00:02:16,120
וחיפוש, כך שאתה יכול
למעשה לעשות משהו

53
00:02:16,120 --> 00:02:18,030
שימושי עם מבנה נתונים.

54
00:02:18,030 --> 00:02:20,760
אז בואו ניקח מבט מהיר
באופן בו אנו יכולים ליישם

55
00:02:20,760 --> 00:02:24,530
קוד לרשימה מקושרת כדלקמן.

56
00:02:24,530 --> 00:02:27,885
>> אז זה רק חלק קוד C,
אפילו לא תכנית מלאה

57
00:02:27,885 --> 00:02:29,260
כי אני באמת מוקצף במהירות.

58
00:02:29,260 --> 00:02:32,300
זה לא מקוון בהפצה
קוד, כי זה לא ממש לרוץ.

59
00:02:32,300 --> 00:02:33,790
אבל שמתי לב יש לי רק
עם תגובה אמרה,

60
00:02:33,790 --> 00:02:36,130
נקודת נקודת נקודה, יש משהו
שם, נקודת נקודת נקודה, משהו שם.

61
00:02:36,130 --> 00:02:38,410
ובואו פשוט להסתכל
מה הם החלקים העסיסיים.

62
00:02:38,410 --> 00:02:40,790
אז על קו שלושה,
זוכר שזה עכשיו

63
00:02:40,790 --> 00:02:45,960
הצענו להכריז על צומת האחרונה
זמן, אחד של אובייקטים מלבניים אלה.

64
00:02:45,960 --> 00:02:48,790
יש לו int שנתקשר אל N,
אבל אנחנו יכולים לקרוא לזה שום דבר,

65
00:02:48,790 --> 00:02:51,920
ולאחר מכן כוכב צומת struct בשם הבא.

66
00:02:51,920 --> 00:02:55,520
ורק שיהיה ברור, שני ש
קו, על קו שש, מה זה?

67
00:02:55,520 --> 00:02:57,930
מה הוא עושה לנו?

68
00:02:57,930 --> 00:03:01,044
כי זה בהחלט נראה יותר
נסתר מהמשתנים הרגילים שלנו.

69
00:03:01,044 --> 00:03:02,740
>> קהל: זה עושה את זה לעבור אחד.

70
00:03:02,740 --> 00:03:04,650
>> 1 דובר: זה עושה את זה לעבור אחד.

71
00:03:04,650 --> 00:03:08,580
ולייתר דיוק,
זה יהיה לאחסן את הכתובת

72
00:03:08,580 --> 00:03:11,582
של הצומת שאמורה להיות
סמנטי לידו, נכון?

73
00:03:11,582 --> 00:03:13,540
אז זה לא הולך ל
בהכרח להזיז כלום.

74
00:03:13,540 --> 00:03:15,290
זה רק הולך
לאחסן ערך, שהוא

75
00:03:15,290 --> 00:03:17,170
הולך להיות הכתובת
חלק הצומת אחרת,

76
00:03:17,170 --> 00:03:20,810
וזה למה שאמרנו struct
כוכב צומת, הכוכב המציין

77
00:03:20,810 --> 00:03:22,370
מצביע או כתובת.

78
00:03:22,370 --> 00:03:26,390
אוקיי, אז עכשיו אם אתה מניח שיש לנו
N זה עומד לרשותנו, ובואו

79
00:03:26,390 --> 00:03:29,490
תניח שמישהו אחר יש
הוכנס חבורה של מספרים שלמים שלמה

80
00:03:29,490 --> 00:03:30,400
לרשימה מקושרת.

81
00:03:30,400 --> 00:03:35,640
ושהרשימה המקושרת היא
הצביע על נקודה מסוימת על ידי

82
00:03:35,640 --> 00:03:39,040
רשימה נקראת משתנה זה
עבר לכאן כפרמטר,

83
00:03:39,040 --> 00:03:43,120
איך אני הולך על קו
14 יישום חיפוש?

84
00:03:43,120 --> 00:03:45,990
במילים אחרות, אם אני מיישם
פונקציה שמטרתה בחיים

85
00:03:45,990 --> 00:03:48,889
הוא לקחת int ולאחר מכן
תחילת רשימה מקושרת,

86
00:03:48,889 --> 00:03:50,430
שהוא מצביע לרשימה המקושרת.

87
00:03:50,430 --> 00:03:52,992
כמו ראשון, שאני חושב שדוד
היה מתנדב שלנו ביום שני,

88
00:03:52,992 --> 00:03:54,700
הוא מצביע על
כל מקושר הרשימה,

89
00:03:54,700 --> 00:03:57,820
זה כאילו שאנחנו עוברים
דוד כבטיעון שלנו כאן.

90
00:03:57,820 --> 00:03:59,990
איך אנחנו הולכים על החוצים רשימה זו?

91
00:03:59,990 --> 00:04:04,640
ובכן, מתברר שלמרות ש
מצביעים הם חדשים יחסית עכשיו אלינו,

92
00:04:04,640 --> 00:04:07,010
אנחנו יכולים לעשות את זה יחסית
בצורה ישירה.

93
00:04:07,010 --> 00:04:09,500
>> אני הולך קדימה ו
להצהיר על משתנה זמני ש

94
00:04:09,500 --> 00:04:12,364
באמנה היא רק הולך
להיקרא מצביע, או PTR,

95
00:04:12,364 --> 00:04:14,030
אבל אתה יכול לקרוא לזה מה שאתה רוצה.

96
00:04:14,030 --> 00:04:16,470
ואני הולך לאתחל
זה לתחילת הרשימה.

97
00:04:16,470 --> 00:04:20,050
אז אתה סוג של יכול לחשוב על זה
כ מורה היום האחר,

98
00:04:20,050 --> 00:04:23,580
סוג של מצביע על מישהו
בקרב בני האדם כמתנדבים.

99
00:04:23,580 --> 00:04:26,470
אז אני משתנה זמני זה
רק מצביע על אותו הדבר

100
00:04:26,470 --> 00:04:31,390
ש בשם במקרה
מתנדב דוד גם היה מצביע.

101
00:04:31,390 --> 00:04:35,440
עכשיו בזמן שמצביע הוא
לא ריק, כי כזכור

102
00:04:35,440 --> 00:04:40,350
null שהוא ערך כלשהו זקיף מיוחד
תוחם את סוף הרשימה,

103
00:04:40,350 --> 00:04:44,280
אז בזמן שאני לא מצביע ב
קרקע כמו מתנדב האחרון שלנו

104
00:04:44,280 --> 00:04:47,190
היה, בואו נלך קדימה
ולבצע את הפעולות הבאות.

105
00:04:47,190 --> 00:04:51,820
אם pointer-- ועכשיו אני סוג של הרצון
לעשות את מה שעשינו עם התלמיד

106
00:04:51,820 --> 00:04:57,410
structure-- אם נקודת המצביע הבאה
equals-- ולא, אם נקודת מצביע N שווה

107
00:04:57,410 --> 00:05:02,290
שווה N משתנה,
טיעון שכבר עבר ב,

108
00:05:02,290 --> 00:05:05,370
אז אני רוצה ללכת קדימה
ואומרים לחזור אמיתי.

109
00:05:05,370 --> 00:05:11,020
מצאתי N המספר פנימי של
אחד הצמתים של הרשימה המקושרת שלי.

110
00:05:11,020 --> 00:05:13,500
אבל הנקודה כבר לא
עובד בהקשר זה,

111
00:05:13,500 --> 00:05:17,260
כי מצביע, PTR, הוא
אכן מצביע, כתובת,

112
00:05:17,260 --> 00:05:20,632
אנחנו באמת יכולים להפליא
להשתמש סוף סוף פיסת התחביר

113
00:05:20,632 --> 00:05:22,590
זה סוג של גורם
תחושה אינטואיטיבית ולמעשה

114
00:05:22,590 --> 00:05:27,870
להשתמש חץ כאן, מה שאומר שהולכים מ
שכתובת למספר השלם יש ב.

115
00:05:27,870 --> 00:05:30,160
אז זה דומה מאוד ב
רוח למפעיל הנקודה,

116
00:05:30,160 --> 00:05:33,860
אלא משום שהמצביע אינו מצביע
ולא struct בפועל עצמו,

117
00:05:33,860 --> 00:05:35,380
אנחנו פשוט להשתמש בחץ.

118
00:05:35,380 --> 00:05:40,620
>> אז אם הצומת הנוכחית שאני,
משתנים זמני, אני מצביע על

119
00:05:40,620 --> 00:05:43,060
לא N, מה שאני רוצה לעשות?

120
00:05:43,060 --> 00:05:45,910
ובכן, עם המתנדבים האנושיים שלי
שיש לנו כאן ביום האחר,

121
00:05:45,910 --> 00:05:49,710
אם האדם הראשון שלי הוא לא שאני אחד
רוצה, ואולי האדם השני הוא לא

122
00:05:49,710 --> 00:05:52,660
אחד שאני רוצה, והשלישי, אני
צריך לשמור פיזי נע.

123
00:05:52,660 --> 00:05:54,690
כמו איך אני לשלב ברשימה?

124
00:05:54,690 --> 00:05:57,470
כאשר היו לנו מערך, אתה
רק עשה כמוני ועוד ועוד.

125
00:05:57,470 --> 00:06:03,660
אבל במקרה הזה, זה מספיק כדי
לעשות מצביע, מקבל, מצביע, הבא.

126
00:06:03,660 --> 00:06:07,580
במילים אחרות, השדה הבא
כמו כל הידיים שמאלי

127
00:06:07,580 --> 00:06:10,880
שהמתנדבים האנושיים שלנו ביום שני
היו משתמש כדי להצביע על כמה צומת אחרת.

128
00:06:10,880 --> 00:06:12,890
אלה היו השכנים הבאים שלהם.

129
00:06:12,890 --> 00:06:17,060
>> אז אם אני רוצה לשלב ברשימה זו,
אני לא יכול פשוט לעשות אני בתוספת בתוספת יותר,

130
00:06:17,060 --> 00:06:20,120
אני חייב לומר במקום
אני, מצביע, הוא הולך

131
00:06:20,120 --> 00:06:24,650
שווה כל תחום הבא הוא,
השדה הבא, השדה הבא הוא,

132
00:06:24,650 --> 00:06:28,350
הבא כל ידיים עזבו אלה
שהיו לנו בהצבעה שלב

133
00:06:28,350 --> 00:06:30,000
לכמה ערכים שלאחר מכן.

134
00:06:30,000 --> 00:06:32,590
ואם אני מקבל דרך
שאיטרציה כל,

135
00:06:32,590 --> 00:06:39,330
ולבסוף, אני מכה null שלא
מצא N עדיין, אני פשוט לחזור שווא.

136
00:06:39,330 --> 00:06:44,100
אז שוב, כל מה שאנחנו עושים כאן,
כמו לכל התמונה לפני רגע,

137
00:06:44,100 --> 00:06:47,840
מתחיל על ידי הצבעה ב
תחילתה של הרשימה יש להניח.

138
00:06:47,840 --> 00:06:50,970
ואז אני בודק, הוא הערך
אני מחפש שווה לתשע?

139
00:06:50,970 --> 00:06:52,650
אם כן, אני חוזר אמיתי ושאני גומר.

140
00:06:52,650 --> 00:06:56,450
אם לא, אני מעדכן את היד שלי,
מצביע AKA, להצביע

141
00:06:56,450 --> 00:06:59,540
במיקום של החץ שליד, ו
אז המיקום של החץ שליד,

142
00:06:59,540 --> 00:07:00,480
והבא.

143
00:07:00,480 --> 00:07:03,770
אני פשוט הולך במערך זה.

144
00:07:03,770 --> 00:07:06,010
>> אז שוב, למי אכפת?

145
00:07:06,010 --> 00:07:07,861
כמו מה זה מרכיב ל?

146
00:07:07,861 --> 00:07:10,360
ובכן, זוכר שהצגנו
הרעיון של מחסנית, ש

147
00:07:10,360 --> 00:07:15,400
הוא נתונים מופשטים הקלד ככל זה
לא דבר C, זה לא דבר CS50,

148
00:07:15,400 --> 00:07:19,430
זה רעיון מופשט, הרעיון הזה של
לערום דברים על גבי זו

149
00:07:19,430 --> 00:07:21,820
כי יכול להיות מיושם ב
צרורות של דרכים שונות.

150
00:07:21,820 --> 00:07:25,600
ואחת דרכים שהצענו היו עם
מערך, או עם רשימה מקושרת.

151
00:07:25,600 --> 00:07:29,570
ומתברר שcanonically,
ערימה תומכת לפחות שתי פעולות.

152
00:07:29,570 --> 00:07:32,320
והמילים באז הן דחיפה, ל
לדחוף משהו על הערימה,

153
00:07:32,320 --> 00:07:34,770
כמו מגש חדש ב
חדר אוכל, או פופ,

154
00:07:34,770 --> 00:07:39,000
מה שאומר שכדי להסיר העליון
מגש מהערימה בפינת האוכל

155
00:07:39,000 --> 00:07:41,500
אולם, ואז אולי כמה
פעולות אחרות גם כן.

156
00:07:41,500 --> 00:07:45,770
אז איך אנחנו יכולים להגדיר את המבנה
כי אנחנו עכשיו קוראים ערימה?

157
00:07:45,770 --> 00:07:50,020
>> ובכן, יש לנו את כל הנדרש
תחביר העומדים לרשותנו בג אני אומר,

158
00:07:50,020 --> 00:07:53,830
תן לי הגדרת סוג של
struct בתוך ערימה,

159
00:07:53,830 --> 00:07:58,030
אני הולך לומר הוא מערך, של
כל חבורה של מספרים ולאחר מכן גודל.

160
00:07:58,030 --> 00:08:00,930
אז במילים אחרות, אם אני רוצה
ליישם את זה בקוד,

161
00:08:00,930 --> 00:08:03,830
תן לי ללכת ופשוט סוג של
לצייר מה שזה אומר.

162
00:08:03,830 --> 00:08:06,317
אז זה אומר, תן לי
מבנה שיש לי מערך,

163
00:08:06,317 --> 00:08:09,400
ואני לא יודע מה היא קיבולת,
זה כנראה חלק קבוע שיש לי

164
00:08:09,400 --> 00:08:10,858
מוגדר במקום אחר, וזה בסדר.

165
00:08:10,858 --> 00:08:15,260
אבל נניח שזה רק אחד,
שתיים, שלוש, ארבעה, חמש.

166
00:08:15,260 --> 00:08:16,700
אז יכולת היא 5.

167
00:08:16,700 --> 00:08:21,730
אלמנט זה בתוכי
מבנה ייקרא מספרים.

168
00:08:21,730 --> 00:08:24,020
ואז אני צריך אחד
משתנה אחרים, ככל הנראה,

169
00:08:24,020 --> 00:08:27,814
גודל נקרא שתחילה אני הולך
לקבוע מאותחל לאפס.

170
00:08:27,814 --> 00:08:29,730
אם אין שום דבר ב
הערימה, הגודל הוא אפס,

171
00:08:29,730 --> 00:08:31,420
וזה ערכי אשפה במספרים.

172
00:08:31,420 --> 00:08:33,450
אין לי מושג מה יש שם עדיין.

173
00:08:33,450 --> 00:08:36,059
>> אז אם אני רוצה לדחוף
משהו על הערימה,

174
00:08:36,059 --> 00:08:40,780
מניח שאני מכנה את דחיפת הפונקציה, ו
אני אומר לדחוף 50, כמו המספר 50,

175
00:08:40,780 --> 00:08:44,090
איפה אתה מציע
אני מצייר אותו במערך הזה?

176
00:08:44,090 --> 00:08:47,124
יש חמש תשובות אפשריות שונות.

177
00:08:47,124 --> 00:08:48,790
איפה אתה רוצה לדחוף את המספר 50?

178
00:08:48,790 --> 00:08:51,899
אם המטרה כאן, שוב, קוראים
דחיפת פונקציה, לעבור בטענה

179
00:08:51,899 --> 00:08:52,940
של 50, שבו אין אני שם את זה?

180
00:08:52,940 --> 00:08:55,680

181
00:08:55,680 --> 00:08:59,052
חמישה סיכוי של 20% possible--
ניחוש נכון.

182
00:08:59,052 --> 00:08:59,896
כן?

183
00:08:59,896 --> 00:09:00,740
>> קהל: ימין קיצוני.

184
00:09:00,740 --> 00:09:01,990
>> 1 מרצה: ימין קיצוני.

185
00:09:01,990 --> 00:09:08,359
יש עכשיו סיכוי של 25%
ניחוש נכון.

186
00:09:08,359 --> 00:09:09,650
אז שלמעשה יהיה בסדר.

187
00:09:09,650 --> 00:09:12,770
לפי אמנה, אני אומר עם מערך,
היינו בדרך כלל מתחיל בצד השמאל,

188
00:09:12,770 --> 00:09:14,519
אבל אנחנו בהחלט יכולים
תתחיל בצד הימין.

189
00:09:14,519 --> 00:09:17,478
אז ספוילר כאן יהיה אני
כנראה הולך לצייר אותו בצד השמאל,

190
00:09:17,478 --> 00:09:20,060
בדיוק כמו במערך רגיל שבי
אני מתחיל ללכת משמאל לימין.

191
00:09:20,060 --> 00:09:21,780
אבל אם אתה יכול להעיף
החשבון, בסדר.

192
00:09:21,780 --> 00:09:23,060
זה פשוט לא מקובל.

193
00:09:23,060 --> 00:09:24,880
בסדר, אני צריך לעשות אחד
יותר שינוי אף.

194
00:09:24,880 --> 00:09:27,710
עכשיו אני כבר דחפתי משהו
על הערימה, מה הלאה?

195
00:09:27,710 --> 00:09:29,400
>> בסדר, אני צריך להגדיל את הגודל.

196
00:09:29,400 --> 00:09:32,600
אז תן לי ללכת קדימה ורק
עדכון זה, שהיה אפס.

197
00:09:32,600 --> 00:09:35,950
ובמקום עכשיו, אני הולך
לשים בערך אחד.

198
00:09:35,950 --> 00:09:39,460
ועכשיו נניח שאני דוחף עוד
מספר על הערימה, כמו 51.

199
00:09:39,460 --> 00:09:42,680
ובכן, יש לי לעשות אחד יותר
שינוי, שהוא עד לגודל שני.

200
00:09:42,680 --> 00:09:46,100
ואז מניח שדוחף אחד יותר
מספר על הערימה כמו 61,

201
00:09:46,100 --> 00:09:52,530
עכשיו אני צריך לעדכן את הגודל אחד יותר
הזמן, ולקבל את הערך 3 כגודל.

202
00:09:52,530 --> 00:09:54,690
ועכשיו נניח שאני קורא פופ.

203
00:09:54,690 --> 00:09:57,250
עכשיו פופ, על ידי אמנה,
לא לוקח טיעון.

204
00:09:57,250 --> 00:10:00,430
עם ערימה, כל
נקודת מטפורה המגש

205
00:10:00,430 --> 00:10:03,450
הוא שאין לך שיקול דעת
ללכת לקבל מגש ש, כל מה שאתה יכול לעשות

206
00:10:03,450 --> 00:10:06,330
הוא פופ העליון אחד מ
הערימה, רק בגלל ש.

207
00:10:06,330 --> 00:10:08,010
זה מה שמבנה נתונים זה עושה.

208
00:10:08,010 --> 00:10:12,250
>> אז לפי היגיון שאם
אומר פופ, מה יורד?

209
00:10:12,250 --> 00:10:13,080
אז 61.

210
00:10:13,080 --> 00:10:15,402
אז מה באמת המחשב
הולך לעשות בזיכרון?

211
00:10:15,402 --> 00:10:16,610
מה הקוד שלי צריך לעשות?

212
00:10:16,610 --> 00:10:20,330
מה היית מציע
אנחנו משנים על המסך?

213
00:10:20,330 --> 00:10:23,410
מה צריך לשנות?

214
00:10:23,410 --> 00:10:24,960
מצטער?

215
00:10:24,960 --> 00:10:26,334
אז אנחנו להיפטר 61.

216
00:10:26,334 --> 00:10:27,500
אז בהחלט אני יכול לעשות את זה.

217
00:10:27,500 --> 00:10:28,640
ואני מקבל יכול להיפטר של 61.

218
00:10:28,640 --> 00:10:30,980
ואז מה אחר
שינוי צריך לקרות?

219
00:10:30,980 --> 00:10:33,160
גודל כנראה יש לחזור לשתיים.

220
00:10:33,160 --> 00:10:34,210
ואז זה בסדר.

221
00:10:34,210 --> 00:10:36,690
אבל חכה רגע, גודל
רגע לפני היה שלוש.

222
00:10:36,690 --> 00:10:38,240
בואו פשוט לעשות בדיקת שפיות מהירה.

223
00:10:38,240 --> 00:10:41,810
איך אנחנו יודעים שאנחנו
רציתי להיפטר של 61?

224
00:10:41,810 --> 00:10:42,760
כי אנחנו קופצים.

225
00:10:42,760 --> 00:10:46,450
ואז יש לי גודל נכס שני זה.

226
00:10:46,450 --> 00:10:48,470
>> חכה רגע, אני
חשבתי לחזור לשבוע שני

227
00:10:48,470 --> 00:10:51,660
כאשר התחלנו לדבר על
מערכים, שבו זה היה מיקום אפס,

228
00:10:51,660 --> 00:10:55,920
זה היה מקום אחד, זה היה מיקום
שני, זה מיקום שלושה, ארבעה,

229
00:10:55,920 --> 00:10:58,460
זה נראה כמו
קשר בין הגודל

230
00:10:58,460 --> 00:11:02,780
והאלמנט שאני רוצה להסיר
מהמערך מופיע רק כדי להיות מה?

231
00:11:02,780 --> 00:11:05,120
גודל מינוס אחד.

232
00:11:05,120 --> 00:11:07,786
ואז זה איך שבני אדם
אנחנו יודעים 61 מגיעים ראשון.

233
00:11:07,786 --> 00:11:09,160
איך המחשב הולך לדעת?

234
00:11:09,160 --> 00:11:11,701
כאשר הקוד שלך, שבו אתה כנראה
רוצה לעשות מינוס גודל אחד,

235
00:11:11,701 --> 00:11:14,950
כך שלוש מינוס אחד הוא שתיים, וש
אומר שאנחנו רוצים להיפטר של 61.

236
00:11:14,950 --> 00:11:18,000
ואז אנחנו יכולים אכן לעדכן
גודל כל כך גודל שעכשיו

237
00:11:18,000 --> 00:11:20,300
עובר משלושה לשתיים בלבד.

238
00:11:20,300 --> 00:11:24,520
ורק כדי להיות קפדן, אני הולך
להציע שאני עושה, נכון?

239
00:11:24,520 --> 00:11:27,660
אתה הציע באופן אינטואיטיבי
נכון שאני צריך להיפטר של 61.

240
00:11:27,660 --> 00:11:30,700
אבל יש לי לא סוג של
סוג של להיפטר של 61?

241
00:11:30,700 --> 00:11:33,790
שכחתי יעילות
שזה בעצם שם.

242
00:11:33,790 --> 00:11:37,680
וחושב לחזור לPSET4, אם יצאת לך לקרוא
המאמר על זיהוי פלילי, PDF

243
00:11:37,680 --> 00:11:40,780
שהיו לנו אתם קוראים, או שאתה
יקרא את זה בשבוע שלPSET4.

244
00:11:40,780 --> 00:11:44,300
נזכיר כי זו היא למעשה רלוונטית ל
כל הרעיון של זיהוי פלילי מחשב.

245
00:11:44,300 --> 00:11:47,820
מה מחשב בדרך כלל עושה הוא
זה פשוט שוכח איפה הוא משהו,

246
00:11:47,820 --> 00:11:51,300
אבל זה לא הולך ובכמו
מנסה לגרד החוצה או לעקוף אותו

247
00:11:51,300 --> 00:11:54,560
אלה פיסות עם אפסים ואחדים
או איזה דפוס אקראי אחר

248
00:11:54,560 --> 00:11:56,690
אלא אם כן אתה בעצמך עושה זאת במכוון.

249
00:11:56,690 --> 00:11:58,930
אז האינטואיציה שלך הייתה
בסדר, בואו להיפטר של 61.

250
00:11:58,930 --> 00:12:00,650
אבל במציאות, אנחנו לא צריכים לטרוח.

251
00:12:00,650 --> 00:12:04,040
אנחנו פשוט צריכים לשכוח ש
זה שם על ידי שינוי הגודל שלנו.

252
00:12:04,040 --> 00:12:05,662
>> עכשיו יש בעיה עם זה ערימה.

253
00:12:05,662 --> 00:12:07,620
אם אני שומר דוחף דברים
על הערימה, מה

254
00:12:07,620 --> 00:12:11,167
ברור שהולך לקרות
רק כמה רגעים זמן?

255
00:12:11,167 --> 00:12:12,500
אנחנו הולכים נגמרים של שטח.

256
00:12:12,500 --> 00:12:13,580
ומה אנחנו עושים?

257
00:12:13,580 --> 00:12:14,680
אנחנו דפוקים סוג של.

258
00:12:14,680 --> 00:12:19,000
יישום זה לא נותן
שלנו לשנות את גודל המערך, כי שימוש ב

259
00:12:19,000 --> 00:12:21,240
תחביר זה, אם אתה
חושב לחזור לשבוע שני,

260
00:12:21,240 --> 00:12:23,520
לאחר שהכרזת
הגודל של מערך,

261
00:12:23,520 --> 00:12:26,780
שלא ראיתי עדיין מנגנון שבו
אתה יכול לשנות את הגודל של המערך.

262
00:12:26,780 --> 00:12:29,020
ואכן C אין תכונה ש.

263
00:12:29,020 --> 00:12:32,524
אם אתה אומר לי חמישה
Nths, קורא להם מספרים,

264
00:12:32,524 --> 00:12:33,940
זה כל מה שאתה הולך לקבל את זה.

265
00:12:33,940 --> 00:12:38,790
אז אנחנו עושים עכשיו ליום שני, יש לי
היכולת לבטא פתרון

266
00:12:38,790 --> 00:12:42,480
אם כי, אנחנו פשוט צריכים לצבוט
ההגדרה של המחסנית שלנו

267
00:12:42,480 --> 00:12:46,840
לא להיות חלק ממערך בקידוד קשיח,
אבל רק כדי לאחסן את כתובת.

268
00:12:46,840 --> 00:12:47,890
>> עכשיו למה זה?

269
00:12:47,890 --> 00:12:51,690
עכשיו אנחנו רק צריכים להיות נוחים עם
העובדה שכאשר התכנית שלי פועלת,

270
00:12:51,690 --> 00:12:53,730
אני כנראה הולך
צריך לשאול את האדם,

271
00:12:53,730 --> 00:12:55,110
כמה מספרים שאתה רוצה לאחסן?

272
00:12:55,110 --> 00:12:56,776
אז הקלט צריך לבוא ממקום כלשהו.

273
00:12:56,776 --> 00:12:59,140
אבל ברגע שאני יודע ש
מספר, אז אני רק יכול

274
00:12:59,140 --> 00:13:02,470
להשתמש במה לתפקד לתת
שלי נתח של זיכרון?

275
00:13:02,470 --> 00:13:03,580
אני יכול להשתמש בmalloc.

276
00:13:03,580 --> 00:13:06,710
ואני יכול לומר כל מספר של
בתים שאני רוצה לחזור לNths אלה.

277
00:13:06,710 --> 00:13:10,910
וכל מה שאני צריך לאחסן במספרים
משתנה כאן בתוך struct זה

278
00:13:10,910 --> 00:13:13,480
צריך להיות מה?

279
00:13:13,480 --> 00:13:18,440
מה בעצם הולך ל
מספרים בתרחיש זה?

280
00:13:18,440 --> 00:13:21,300
כן, מצביע לראשון
בתים של נתח זה של זיכרון,

281
00:13:21,300 --> 00:13:24,940
או לייתר דיוק, את הכתובת
הראשונים של בתים אלה.

282
00:13:24,940 --> 00:13:27,300
לא משנה אם זה אחד
בתים או מיליארדים בייטים,

283
00:13:27,300 --> 00:13:28,890
אני רק צריך לדאוג הראשון.

284
00:13:28,890 --> 00:13:31,530
כי מה ערבויות malloc ו
ערבויות מערכת הפעלה שלי,

285
00:13:31,530 --> 00:13:34,170
הוא שהנתח שלי זיכרון
לקבל, זה הולך להיות רציף.

286
00:13:34,170 --> 00:13:35,378
יש לא הולך להיות פערים.

287
00:13:35,378 --> 00:13:38,576
אז אם אני כבר ביקשתי 50
בתים או 1,000 בתים,

288
00:13:38,576 --> 00:13:40,450
הם כולם הולכים להיות
גב אל גב אל גב.

289
00:13:40,450 --> 00:13:44,500
וכל עוד אני זוכר איך גדול, איך
הרבה בקשתי, כל מה שאני צריך לדעת

290
00:13:44,500 --> 00:13:46,230
היא הכתובת הראשונה מהסוג.

291
00:13:46,230 --> 00:13:48,660
>> אז עכשיו יש לנו את היכולת בקוד.

292
00:13:48,660 --> 00:13:51,280
אם כי, זה הולך לקחת אותנו
יותר זמן לכתוב את זה,

293
00:13:51,280 --> 00:13:55,900
אנחנו יכולים עכשיו להקצות מחדש זיכרון שעל ידי
רק אחסון כתובת אחרת יש

294
00:13:55,900 --> 00:13:59,060
אם אנחנו רוצים יותר גדולים או אפילו
נתח קטן יותר של זיכרון.

295
00:13:59,060 --> 00:14:00,170
אז הנה ממסחר.

296
00:14:00,170 --> 00:14:01,360
עכשיו אנחנו מקבלים דינמיות.

297
00:14:01,360 --> 00:14:03,350
עדיין יש לנו
contiguousness אני טוען.

298
00:14:03,350 --> 00:14:05,881
בגלל malloc ייתן לנו
נתח רציף של זיכרון.

299
00:14:05,881 --> 00:14:08,630
אבל זה הולך להיות כאב ב
צווארנו, מתכנת,

300
00:14:08,630 --> 00:14:09,770
למעשה קוד למעלה.

301
00:14:09,770 --> 00:14:10,730
זה פשוט יותר עבודה.

302
00:14:10,730 --> 00:14:13,930
אנחנו צריכים קוד דומה למה שהייתי
דופק את רק לפני רגע.

303
00:14:13,930 --> 00:14:16,120
מאוד אפשרי, אבל זה מוסיף מורכבות.

304
00:14:16,120 --> 00:14:19,520
וכך זמן מפתח, מתכנת
זמן הוא משאב אחר עדיין

305
00:14:19,520 --> 00:14:22,520
שאולי אנחנו צריכים להשקיע
קצת זמן כדי לקבל תכונות חדשות.

306
00:14:22,520 --> 00:14:24,020
ואז כמובן יש תור.

307
00:14:24,020 --> 00:14:26,227
אנחנו לא נכנסנו לזה
אחד בפירוט רב.

308
00:14:26,227 --> 00:14:27,560
אבל זה דומה מאוד ברוחו.

309
00:14:27,560 --> 00:14:31,220
אני יכול ליישם תור, ו
הפעילות המקבילה שלה,

310
00:14:31,220 --> 00:14:35,660
Enqueue או dequeue, כמו להוסיף או להסיר,
זה רק דרך מהודרת לומר את זה,

311
00:14:35,660 --> 00:14:38,100
Enqueue או dequeue, כדלקמן.

312
00:14:38,100 --> 00:14:41,170
אני יכול רק לתת לעצמי struct
יש מערך של מספר ששוב,

313
00:14:41,170 --> 00:14:44,000
יש ששוב גודל,
אבל למה לעשות עכשיו אני צריך

314
00:14:44,000 --> 00:14:46,940
כדי לעקוב אחר מול תור?

315
00:14:46,940 --> 00:14:50,630
אני לא צריך לדעת
מול הערימה שלי.

316
00:14:50,630 --> 00:14:53,570
ובכן, אם אני שוב ל
queue-- בואו פשוט קשה

317
00:14:53,570 --> 00:14:57,870
קוד זה כבעל כמו חמש
מספרים שלמים בכאן פוטנציאל.

318
00:14:57,870 --> 00:15:00,940
אז זה הוא אפס, אחת, שתיים, שלוש, ארבעה.

319
00:15:00,940 --> 00:15:03,430
זה הולך להיות
מספרים התקשרו שוב.

320
00:15:03,430 --> 00:15:06,940
וזה ייקרא גודל.

321
00:15:06,940 --> 00:15:10,056
>> למה זה לא מספיק
יש רק גודל?

322
00:15:10,056 --> 00:15:11,680
ובכן, בואו לדחוף אותם מספרים ב.

323
00:15:11,680 --> 00:15:14,220
אז אני pushed-- אני בעלות מוצבת בתור, או דחפתי.

324
00:15:14,220 --> 00:15:20,150
עכשיו אני Enqueue 50, ולאחר מכן
51, ולאחר מכן 61, ושלוש נקודות.

325
00:15:20,150 --> 00:15:21,070
אז זה Enqueue.

326
00:15:21,070 --> 00:15:23,176
אני בעלות מוצבות בתור 50, אז 51, אז 61.

327
00:15:23,176 --> 00:15:25,050
וזה נראה זהה
לערימה עד כה,

328
00:15:25,050 --> 00:15:27,190
מלבד אני צריך לעשות שינוי אחד.

329
00:15:27,190 --> 00:15:33,680
אני צריך לעדכן את הגודל הזה, אז אני הולך
מאפס לאחד, ל02:58 עכשיו.

330
00:15:33,680 --> 00:15:35,760
איך אני dequeue?

331
00:15:35,760 --> 00:15:36,890
מה קורה עם dequeue?

332
00:15:36,890 --> 00:15:41,950
מי צריך לבוא מרשימה זו ראשונה
אם זה בתור בחנות אפל?

333
00:15:41,950 --> 00:15:42,780
אז 50.

334
00:15:42,780 --> 00:15:44,700
אז זה סוג של יותר מסובך הפעם.

335
00:15:44,700 --> 00:15:47,880
ואילו בפעם האחרונה זה היה סופר
קל רק כדי לעשות מינוס גודל אחד,

336
00:15:47,880 --> 00:15:51,440
אני מגיע לסוף המערך שלי ביעילות
שבו המספרים, הוא מסיר 61.

337
00:15:51,440 --> 00:15:52,920
אבל אני לא רוצה להסיר 61.

338
00:15:52,920 --> 00:15:55,030
אני רוצה לקחת את 50, ש
היה שם שעה 5:00 בבוקר

339
00:15:55,030 --> 00:15:56,790
בשורה ל
iPhone או מה שלא חדשים.

340
00:15:56,790 --> 00:16:01,200
וכך להיפטר של 50, אני
לא יכול פשוט לעשות את זה, נכון?

341
00:16:01,200 --> 00:16:02,547
אני יכול לעבור את 50.

342
00:16:02,547 --> 00:16:04,380
אבל אנחנו פשוט אמרתי שאנחנו
לא צריך להיות כל כך אנאלי

343
00:16:04,380 --> 00:16:06,330
כלגרד החוצה או להסתיר את הנתונים.

344
00:16:06,330 --> 00:16:08,090
אנחנו יכולים פשוט לשכוח איפה זה.

345
00:16:08,090 --> 00:16:12,330
>> אבל אם אני משנה את הגודל שלי עכשיו ל
שני, הוא מספיק מידע זה

346
00:16:12,330 --> 00:16:15,711
לדעת מה קורה בתור שלי?

347
00:16:15,711 --> 00:16:16,680
לא באמת.

348
00:16:16,680 --> 00:16:19,830
כמו הגודל שלי הוא שתיים, אבל
שבו התור אינו מתחיל,

349
00:16:19,830 --> 00:16:22,980
במיוחד אם עדיין יש לי
אותם מספרים בזיכרון.

350
00:16:22,980 --> 00:16:24,260
50, 51, 61.

351
00:16:24,260 --> 00:16:27,090
אז אני צריך לזכור
עכשיו איפה החזית.

352
00:16:27,090 --> 00:16:29,630
וכך כפי שהצעתי עד
שם, אנחנו פשוט נקראים

353
00:16:29,630 --> 00:16:33,729
מול המי יודע כמה, שראשוני
ערך צריך להיות מה?

354
00:16:33,729 --> 00:16:35,270
אפס, רק ההתחלה של הרשימה.

355
00:16:35,270 --> 00:16:40,876
אבל עכשיו, בנוסף לdecrementing
הגודל, אנחנו פשוט להגדיל את החזית.

356
00:16:40,876 --> 00:16:42,000
עכשיו הנה בעיה נוספת.

357
00:16:42,000 --> 00:16:43,030
אז ברגע שאני כל הזמן הולך.

358
00:16:43,030 --> 00:16:47,520
מניח שזה הוא מספר
כמו 121, 124, ולאחר מכן, לכל הרוחות,

359
00:16:47,520 --> 00:16:48,610
אני מתוך שטח.

360
00:16:48,610 --> 00:16:50,390
אבל חכה רגע, אני לא.

361
00:16:50,390 --> 00:16:55,630
כך שבנקודה זו של הסיפור,
נניח שהגודל הוא אחד, שתי,

362
00:16:55,630 --> 00:17:00,370
שלוש, ארבעה, כך מניח ש
גודל הוא ארבעה, החזית היא אחד,

363
00:17:00,370 --> 00:17:01,621
כך 51 הוא בחזית.

364
00:17:01,621 --> 00:17:04,329
אני רוצה לשים את מספר אחר כאן,
אבל, לעזאזל, אני לא בשטח.

365
00:17:04,329 --> 00:17:06,710
אבל אני לא ממש, נכון?

366
00:17:06,710 --> 00:17:11,192
איפה אני יכול לשים כמה
ערך נוסף, כמו 171?

367
00:17:11,192 --> 00:17:13,400
רק כן, אני יכול סוג של
לחזור לשם, נכון?

368
00:17:13,400 --> 00:17:18,161
ואז לחצות את 50, או
רק להחליף אותו עם 171.

369
00:17:18,161 --> 00:17:20,410
ואם אתם תוהים למה
המספרים שלנו יש כל כך אקראיים,

370
00:17:20,410 --> 00:17:24,150
אלה נלקחים מחשב נפוץ
קורסי מדע באוניברסיטת הרווארד לאחר CS50.

371
00:17:24,150 --> 00:17:27,510
אבל זה היה אופטימיזציה טובה,
כי עכשיו אני לא מבזבז שטח.

372
00:17:27,510 --> 00:17:30,750
אני עדיין צריך לזכור
כמה גדול הדבר הזה הוא מוחלט.

373
00:17:30,750 --> 00:17:31,500
זה חמש כולל.

374
00:17:31,500 --> 00:17:33,375
כי אני לא רוצה
תתחיל להחליף 51.

375
00:17:33,375 --> 00:17:36,260
אז עכשיו אני עדיין מחוץ למרחב,
כך את אותה הבעיה כמו קודם.

376
00:17:36,260 --> 00:17:39,140
אבל אתה יכול לראות איך עכשיו
בקוד שלך, אתה כנראה

377
00:17:39,140 --> 00:17:41,910
צריך לכתוב קצת יותר
מורכבות כדי שזה יקרה.

378
00:17:41,910 --> 00:17:44,510
ולמעשה, מה שמפעיל
בC כנראה מאפשר לי

379
00:17:44,510 --> 00:17:48,110
אתה קסם לעשות את זה מעגלי?

380
00:17:48,110 --> 00:17:50,160
כן מפעיל מודולו,
אחוזים הסימן.

381
00:17:50,160 --> 00:17:53,160
אז מה סוג של מגניב על תור,
למרות שאנחנו ממשיכים מערכי ציור

382
00:17:53,160 --> 00:17:56,520
כקווים ישרים כמו אלה, אם אתה
סוג של לחשוב על זה כמתעקל

383
00:17:56,520 --> 00:18:00,341
סביב כעיגול, ואז פשוט
באופן אינטואיטיבי אותו סוג של עובד נפשי

384
00:18:00,341 --> 00:18:01,590
אני חושב שקצת יותר נקי.

385
00:18:01,590 --> 00:18:05,190
אתה עדיין תצטרך ליישם
שמודל המנטלי בקוד.

386
00:18:05,190 --> 00:18:07,550
אז לא כל כך קשה,
סופו של דבר, ליישום,

387
00:18:07,550 --> 00:18:12,430
אבל אנחנו עדיין מאבדים size-- ולא,
היכולת לשנות את הגודל, אלא אם כן אנחנו עושים את זה.

388
00:18:12,430 --> 00:18:15,310
>> יש לנו להיפטר מהמערך, אנחנו
להחליף אותו עם מצביע יחיד,

389
00:18:15,310 --> 00:18:20,010
ואז אי שם בקוד שלי שיש לי
לקרוא למה לתפקד ליצור למעשה

390
00:18:20,010 --> 00:18:23,720
המערך מספרים הנקראים?

391
00:18:23,720 --> 00:18:26,190
Malloc, או כמה דומה
פונקציה, בדיוק.

392
00:18:26,190 --> 00:18:30,481
כל שאלות על ערימות או תורים.

393
00:18:30,481 --> 00:18:30,980
כן?

394
00:18:30,980 --> 00:18:33,657

395
00:18:33,657 --> 00:18:34,240
שאלה טובה.

396
00:18:34,240 --> 00:18:35,830
מה מודולו היית להשתמש כאן.

397
00:18:35,830 --> 00:18:38,520
אז בדרך כלל, בעת שימוש ב
mod, היית עושה את זה

398
00:18:38,520 --> 00:18:40,620
עם הגודל של
מבנה נתונים שלם.

399
00:18:40,620 --> 00:18:44,120
אז משהו כמו חמש או יכולת, אם
זה קבוע, כנראה מעורב.

400
00:18:44,120 --> 00:18:47,100
אבל רק עושה מודולו חמש
כנראה לא מספיק,

401
00:18:47,100 --> 00:18:51,380
כי אנחנו צריכים לדעת לעשות
לעטוף כאן או לכאן או לכאן.

402
00:18:51,380 --> 00:18:54,160
אז אתה כנראה גם
הולך רוצה לערב

403
00:18:54,160 --> 00:18:57,220
גודלו של הדבר, או
משתנה מול כן.

404
00:18:57,220 --> 00:19:00,140
אז זה רק זה יחסית
ביטוי חשבון פשוט,

405
00:19:00,140 --> 00:19:02,000
אבל מודולו יהיה המרכיב העיקרי.

406
00:19:02,000 --> 00:19:03,330
>> סרט כל כך קצר, אם תרצה.

407
00:19:03,330 --> 00:19:05,780
אנימציה שחלק
אנשים באוניברסיטה אחרת

408
00:19:05,780 --> 00:19:08,060
להרכיב שיש לנו
מותאם לדיון הזה.

409
00:19:08,060 --> 00:19:12,630
זה כרוך ג'ק לומד
עובדות על תורים ונתונים סטטיסטיים.

410
00:19:12,630 --> 00:19:19,010

411
00:19:19,010 --> 00:19:21,890
>> סרט: פעם,
היה בחור בשם ג'ק.

412
00:19:21,890 --> 00:19:25,330
כשזה הגיע לקבלת חברים,
ג'ק לא היה לו כשרון.

413
00:19:25,330 --> 00:19:28,220
אז ג'ק הלך לדבר
רוב הבחור הפופולרי שהוא יודע.

414
00:19:28,220 --> 00:19:30,920
הוא הלך ללו ושאלו, מה עליי לעשות?

415
00:19:30,920 --> 00:19:33,400
לו ראה שחברו
היה ממש במצוקה.

416
00:19:33,400 --> 00:19:36,050
ובכן, הוא התחיל, רק
תראה איך אתה לבוש.

417
00:19:36,050 --> 00:19:38,680
אין לך בגדים
במבט שונה?

418
00:19:38,680 --> 00:19:39,660
כן, אמר ג'ק.

419
00:19:39,660 --> 00:19:40,840
אני בטוח שאעשה.

420
00:19:40,840 --> 00:19:43,320
בואו לבית שלי ו
אני אראה לך אותם.

421
00:19:43,320 --> 00:19:44,550
אז הם הלכו לג'ק.

422
00:19:44,550 --> 00:19:47,520
וג'ק הראה לו את התיבה
שבו החזיק את כל החולצות שלו,

423
00:19:47,520 --> 00:19:49,260
ומכנסיו, וגרביו.

424
00:19:49,260 --> 00:19:52,290
לו אמר, אני רואה שיש לך
כל הבגדים שלך בערימה.

425
00:19:52,290 --> 00:19:54,870
למה אתה לא לובש כמה
אחרים פעם בכמה זמן?

426
00:19:54,870 --> 00:19:58,020
>> ג'ק אמר, טוב, כש
להסיר את הבגדים וגרביים,

427
00:19:58,020 --> 00:20:00,780
אני רוחץ אותם ולשים את
אותם משם בתיבה.

428
00:20:00,780 --> 00:20:03,210
ואז מגיע הבא
בוקר, ועד שאני לקפוץ.

429
00:20:03,210 --> 00:20:06,380
אני הולך לתיבה ולקבל
הבגדים שלי את החלק העליון.

430
00:20:06,380 --> 00:20:09,070
לו מהר מאוד הבין
הבעיה עם ג'ק.

431
00:20:09,070 --> 00:20:12,080
הוא המשיך בגדים, דיסקים,
וספרים בערימה.

432
00:20:12,080 --> 00:20:14,420
כשהגיע ל
משהו לקרוא או ללבוש,

433
00:20:14,420 --> 00:20:17,100
הוא הייתי בוחר ספר או תחתונים העליונים.

434
00:20:17,100 --> 00:20:19,500
לאחר מכן, כאשר הוא נעשה, הוא
היה לשים אותו בחזרה.

435
00:20:19,500 --> 00:20:21,970
חזור זה ילך, בראש הערימה.

436
00:20:21,970 --> 00:20:24,460
אני יודע את הפתרון,
אמר נצחון בקול רם.

437
00:20:24,460 --> 00:20:27,090
אתה צריך ללמוד
להתחיל להשתמש בתור.

438
00:20:27,090 --> 00:20:29,870
לו לקח את בגדיו של ג'ק ו
תלה אותם בארון.

439
00:20:29,870 --> 00:20:32,710
וכשהוא התרוקן
התיבה, הוא פשוט זרק אותו.

440
00:20:32,710 --> 00:20:36,500
>> ואז הוא אמר, עכשיו ג'ק, בסוף
היום, לשים את הבגדים שלך בצד השמאל

441
00:20:36,500 --> 00:20:37,990
כאשר אתה שם אותם משם.

442
00:20:37,990 --> 00:20:41,300
אז מחר בבוקר כשאתה
לראות את אור השמש, את הבגדים שלך

443
00:20:41,300 --> 00:20:43,440
מימין, מסוף השורה.

444
00:20:43,440 --> 00:20:44,880
אתה לא רואה? אמר לו.

445
00:20:44,880 --> 00:20:46,370
זה יהיה כל כך נחמד.

446
00:20:46,370 --> 00:20:49,770
אתה לובש כל מה שפעם
לפני שאתה לובש משהו פעמיים.

447
00:20:49,770 --> 00:20:52,670
ועם כל דבר בתורים
בארון והמדף שלו,

448
00:20:52,670 --> 00:20:55,160
ג'ק התחיל להרגיש
די בטוח בעצמו.

449
00:20:55,160 --> 00:20:59,720
הכל בזכות לו ו
תורו הנפלא.

450
00:20:59,720 --> 00:21:01,220
1 SPEAKER: בסדר, זה מקסים.

451
00:21:01,220 --> 00:21:05,920

452
00:21:05,920 --> 00:21:10,080
אז מה באמת כבר הולך
במתחת למכסת המנוע עכשיו?

453
00:21:10,080 --> 00:21:12,370
שיש לנו עצות,
שיש לנו malloc,

454
00:21:12,370 --> 00:21:15,680
שיש לנו את היכולת ליצור
נתחי זיכרון לעצמנו

455
00:21:15,680 --> 00:21:16,344
באופן דינמי.

456
00:21:16,344 --> 00:21:18,510
אז זה אנחנו תמונה
ראיתי רק לפני כמה הימים.

457
00:21:18,510 --> 00:21:21,180
אנחנו לא באמת להתעכב
על זה, אבל התמונה הזאת

458
00:21:21,180 --> 00:21:24,180
כבר קורה מתחת
מכסה המנוע לשבועות.

459
00:21:24,180 --> 00:21:27,050
וכך זה מייצג, רק
מלבן שאנחנו כבר נמשכים,

460
00:21:27,050 --> 00:21:28,180
הזיכרון של המחשב שלך.

461
00:21:28,180 --> 00:21:31,850
ואולי המחשב שלך, או CS50
זיהוי, יש ג'יגה זיכרון או זיכרון RAM

462
00:21:31,850 --> 00:21:33,050
או שתי ג'יגה-בייט או ארבעה.

463
00:21:33,050 --> 00:21:34,450
זה לא משנה באמת.

464
00:21:34,450 --> 00:21:37,240
מערכת ההפעלה שלך
Windows או Mac OS או לינוקס,

465
00:21:37,240 --> 00:21:41,120
בעצם מאפשר התכנית שלך
לחשוב שיש לו גישה

466
00:21:41,120 --> 00:21:42,982
למכלול
הזיכרון של המחשב שלך,

467
00:21:42,982 --> 00:21:45,440
למרות שאתה יכול להיות ריצה
תוכניות מרובות בבת אחת.

468
00:21:45,440 --> 00:21:46,990
אז במציאות, שלא ממש עובד.

469
00:21:46,990 --> 00:21:49,448
אבל זה סוג של אשליה
נתתי לכל התוכניות שלך.

470
00:21:49,448 --> 00:21:53,110
אז אם היה לך שתי הופעות של זיכרון RAM, זה
איך ייתכן שהמחשב חושב על זה.

471
00:21:53,110 --> 00:21:57,110
>> עכשיו במקרה, אחד מאלה
דברים, אחד מהמגזרים של זיכרון אלה,

472
00:21:57,110 --> 00:21:58,350
נקרא ערימה.

473
00:21:58,350 --> 00:22:01,680
ואכן כל זמן
עד כה בכתיבת קוד

474
00:22:01,680 --> 00:22:05,900
שיש לך בשם
פונקציה, לדוגמה העיקרית.

475
00:22:05,900 --> 00:22:08,410
נזכיר כי כל זמן יש לי
הזיכרון של המחשב נמשך,

476
00:22:08,410 --> 00:22:10,640
אני תמיד לצייר סוג של
מחצית מלבן כאן

477
00:22:10,640 --> 00:22:12,520
ולא טורח לדבר
על מה שמעל.

478
00:22:12,520 --> 00:22:15,980
כי כאשר עיקרי נקרא, אני טוען
כי אתה מקבל רסיס זה של זיכרון

479
00:22:15,980 --> 00:22:16,970
שיורד כאן.

480
00:22:16,970 --> 00:22:20,650
ואם עיקריים נקרא פונקציה
כמו החלפה, גם החלפה הולכת כאן.

481
00:22:20,650 --> 00:22:23,720
ומתברר, כי זה
איפה זה מסתיים.

482
00:22:23,720 --> 00:22:26,277
על משהו שנקרא ערימה
בתוך הזיכרון של המחשב שלך.

483
00:22:26,277 --> 00:22:28,360
עכשיו בסופו של היום,
זה רק מטפל.

484
00:22:28,360 --> 00:22:30,680
זה כמו בייט אפס,
בית אחד, בייט 2 מליארד דולרים.

485
00:22:30,680 --> 00:22:33,130
אבל אם אתה חושב על זה
כאובייקט מלבני זה,

486
00:22:33,130 --> 00:22:35,130
כל מה שאנחנו עושים בכל
זמן שאנו מכנים פונקציה היא

487
00:22:35,130 --> 00:22:37,180
שכבות הפרוסה חדשה של זיכרון.

488
00:22:37,180 --> 00:22:41,700
אנחנו נותנים פונקציה שפרוסה
הזיכרון שלו לעבוד איתו.

489
00:22:41,700 --> 00:22:44,490
>> וזוכר עכשיו שזה חשוב.

490
00:22:44,490 --> 00:22:46,400
כי אם יש לנו
משהו כמו החלפה

491
00:22:46,400 --> 00:22:51,610
ושני משתנים מקומיים כמו A ו- B ו
אנחנו משנים את הערכים האלה מאחד ושתי

492
00:22:51,610 --> 00:22:55,130
לשתיים ואחד, כזכור
כי כאשר החלפה חוזרת,

493
00:22:55,130 --> 00:22:58,330
זה כאילו פרוסה זה
זיכרון הוא פשוט נעלם.

494
00:22:58,330 --> 00:23:00,080
במציאות, זה עדיין
בחינה משפטית יש.

495
00:23:00,080 --> 00:23:01,940
ומשהו עדיין ממש שם.

496
00:23:01,940 --> 00:23:05,410
אבל מבחינה רעיונית, זה כ
למרות שהוא נעלם לחלוטין.

497
00:23:05,410 --> 00:23:10,910
וכך עיקרי אינו יודע את כל העבודה
שנעשה שבפונקצית swap,

498
00:23:10,910 --> 00:23:14,890
אלא אם כן זה ממש עבר באלה
טיעונים על ידי מצביע או על ידי התייחסות.

499
00:23:14,890 --> 00:23:17,790
עכשיו, הפתרון היסודי
לבעיה שעם החלפה

500
00:23:17,790 --> 00:23:19,970
עובר דברים בכתובת.

501
00:23:19,970 --> 00:23:23,250
אבל מתברר, גם, מה
נמשך מעל כי חלק

502
00:23:23,250 --> 00:23:26,330
של המלבן כל הזמן הזה הוא
עדיין יש יותר זיכרון עד לשם.

503
00:23:26,330 --> 00:23:28,790
וכאשר אתה באופן דינמי
להקצות זיכרון,

504
00:23:28,790 --> 00:23:32,020
בין אם זה בתוך GetString, ש
אנחנו כבר עושים בשבילך בCS50

505
00:23:32,020 --> 00:23:34,710
ספרייה, או אם אתם
קורא malloc ולשאול

506
00:23:34,710 --> 00:23:37,950
מערכת ההפעלה לנתח של
זיכרון, זה לא בא מהערימה.

507
00:23:37,950 --> 00:23:40,960
זה בא ממקום אחר
בזיכרון של המחשב שלך

508
00:23:40,960 --> 00:23:42,220
זה נקרא הגל.

509
00:23:42,220 --> 00:23:43,430
וזה לא שונה.

510
00:23:43,430 --> 00:23:44,285
זה אותו זיכרון RAM.

511
00:23:44,285 --> 00:23:45,160
זה אותו הזיכרון.

512
00:23:45,160 --> 00:23:49,080
זה רק זיכרון RAM זה עד
שם במקום כאן למטה.

513
00:23:49,080 --> 00:23:50,750
>> ואז מה זה אומר?

514
00:23:50,750 --> 00:23:53,650
ובכן, אם המחשב שלך יש
כמות סופית של זיכרון

515
00:23:53,650 --> 00:23:57,450
והערימה גדלה, כך
לדבר, והערימה, לפי

516
00:23:57,450 --> 00:23:59,349
הלחץ הזה, הוא גדל במורד.

517
00:23:59,349 --> 00:24:01,140
במילים אחרות, כל
זמן שאתה קורא malloc,

518
00:24:01,140 --> 00:24:03,430
אתה נותן להם בפרוסת
זיכרון מלמעלה,

519
00:24:03,430 --> 00:24:06,630
אז אולי קצת נמוך יותר, ואז קטן
נמוך, בכל פעם שאתה קורא malloc,

520
00:24:06,630 --> 00:24:10,100
הערימה, זה שימוש,
הוא סוג של גידול,

521
00:24:10,100 --> 00:24:11,950
גדל יותר ויותר למה?

522
00:24:11,950 --> 00:24:13,382
המחסנית.

523
00:24:13,382 --> 00:24:14,840
אז האם זה נראה כמו רעיון טוב?

524
00:24:14,840 --> 00:24:18,420

525
00:24:18,420 --> 00:24:22,140
אני מתכוון, שבו זה לא ממש ברור
מה עוד אתה יכול לעשות אם אתה רק

526
00:24:22,140 --> 00:24:23,910
יש כמות סופית של זיכרון.

527
00:24:23,910 --> 00:24:25,200
אבל זה בוודאי רע.

528
00:24:25,200 --> 00:24:27,920
אלה שני חצים הם על
קורס מזורז לאחד אחרת.

529
00:24:27,920 --> 00:24:31,930
>> ומתברר שהבחור רע, אנשים ש
טובים במיוחד עם תכנות,

530
00:24:31,930 --> 00:24:36,140
ומנסה לפרוץ למחשבים,
יכול לנצל את המציאות הזאת.

531
00:24:36,140 --> 00:24:38,290
למעשה, הבה נבחן
קטע קטן.

532
00:24:38,290 --> 00:24:41,350
אז זו דוגמא שאתה יכול לקרוא
על בפירוט רב יותר בויקיפדיה.

533
00:24:41,350 --> 00:24:43,100
אנחנו נצביע עליך
מאמר אם סקרן.

534
00:24:43,100 --> 00:24:45,650
אבל יש התקפה בדרך
ידוע כהצפת מאגר ש

535
00:24:45,650 --> 00:24:49,570
קיים כל עוד בני אדם
יש לי היכולת לתפעל

536
00:24:49,570 --> 00:24:53,120
הזיכרון של המחשב, במיוחד בג
אז זה הוא תכנית מאוד שרירותית,

537
00:24:53,120 --> 00:24:55,130
אבל בואו לקרוא אותו מלמטה למעלה.

538
00:24:55,130 --> 00:24:57,650
ראשי לכוכב char argc argv.

539
00:24:57,650 --> 00:24:59,830
אז מדוברים בתכנית שלוקחת
שורת פקודת טיעונים.

540
00:24:59,830 --> 00:25:03,620
וכל זה, ככל הנראה, היא עיקרי שיחה
פונקציה, קוראת לזה F לפשטות.

541
00:25:03,620 --> 00:25:04,610
והוא עובר במה?

542
00:25:04,610 --> 00:25:05,490
Argv של אחד.

543
00:25:05,490 --> 00:25:09,320
אז הוא עובר לF מה
המילה היא שהמשתמש הקליד

544
00:25:09,320 --> 00:25:11,500
בשורת אחרי
שמו של תכנית בכל.

545
00:25:11,500 --> 00:25:15,730
כל כך הרבה כמו קיסר או Vigenere, ש
אולי אתה זוכר עושה עם argv.

546
00:25:15,730 --> 00:25:16,680
>> אז מה הוא F?

547
00:25:16,680 --> 00:25:19,760
F לוקח במחרוזת
כטענתה הבלעדית,

548
00:25:19,760 --> 00:25:22,100
AKA כוכב char, אותו
דבר, כמחרוזת.

549
00:25:22,100 --> 00:25:24,920
וזה נקרא באופן שרירותי
בר בדוגמא זו.

550
00:25:24,920 --> 00:25:27,710
ולאחר מכן char ג 12,
רק במונחים של ההדיוט,

551
00:25:27,710 --> 00:25:31,750
מה היא תושבת ג char 12 עושה לנו?

552
00:25:31,750 --> 00:25:33,440
מה זה עושה?

553
00:25:33,440 --> 00:25:36,490
הקצאת זיכרון, במיוחד
12 בתים עבור 12 תווים.

554
00:25:36,490 --> 00:25:36,990
בדיוק.

555
00:25:36,990 --> 00:25:40,000
ולאחר מכן את השורה האחרונה, מערבבים ו
עותק, שכנראה לא ראה.

556
00:25:40,000 --> 00:25:43,360
זהו עותק מחרוזת
פונקציה שמטרתה בחיים

557
00:25:43,360 --> 00:25:48,160
הוא להעתיק הטיעון השני שלה
לטענה הראשונה שלה,

558
00:25:48,160 --> 00:25:51,190
אבל רק עד ל
מספר מסוים של בתים.

559
00:25:51,190 --> 00:25:53,860
אז הטיעון השלישי אומר,
כמה בתים יש לך להעתיק?

560
00:25:53,860 --> 00:25:56,720
אורכו של בר,
כל מה שהמשתמש הקליד ב.

561
00:25:56,720 --> 00:25:59,320
ואת התוכן של
בר, מחרוזת ש, הם

562
00:25:59,320 --> 00:26:02,330
הועתק לזיכרון הצביע על בג

563
00:26:02,330 --> 00:26:04,060
>> אז זה נראה לי קצת טיפשי, וזה.

564
00:26:04,060 --> 00:26:06,300
זוהי דוגמא מבוים,
אבל זה נציג

565
00:26:06,300 --> 00:26:10,100
של כיתה של התקפה,
דרך של תקיפת תכנית.

566
00:26:10,100 --> 00:26:15,050
הכל טוב ויפה אם המשתמש
סוגים במילה זה 11 תווים

567
00:26:15,050 --> 00:26:18,040
או פחות, בתוספת הקו הנטוי אפס.

568
00:26:18,040 --> 00:26:22,830
מה אם המשתמש מקליד יותר מ
11 או 12 או 20 או 50 תווים?

569
00:26:22,830 --> 00:26:25,090
מה בתכנית זו הולכת לעשות?

570
00:26:25,090 --> 00:26:29,360
אשמה פוטנציאלית SEG. זה הולך
באופן עיוור להעתיק הכל בבר עד

571
00:26:29,360 --> 00:26:31,750
לאורכו, שהוא
פשוטו כמשמעו, כל דבר בבר,

572
00:26:31,750 --> 00:26:36,307
לכתובה הצביע על C. אבל C
מנע נתן רק 12 בתים.

573
00:26:36,307 --> 00:26:37,640
אבל אין בדיקה נוספת.

574
00:26:37,640 --> 00:26:38,700
אין אם תנאים.

575
00:26:38,700 --> 00:26:40,580
אין בדיקת שגיאות כאן.

576
00:26:40,580 --> 00:26:43,270
>> ואז מה היא תכנית זו
הולך לעשות הוא פשוט עיוור

577
00:26:43,270 --> 00:26:45,750
להעתיק דבר אחד למשנהו.

578
00:26:45,750 --> 00:26:47,880
ולכן אם אנו מפנים את זה
כתמונה, הנה

579
00:26:47,880 --> 00:26:49,860
רק רסיס של מרחב הזיכרון.

580
00:26:49,860 --> 00:26:53,470
אז שמנו לב בתחתית, אנחנו
יש בר משתנה המקומי.

581
00:26:53,470 --> 00:26:57,330
כך שהמצביע שהולך store--
ולא שהטיעון מקומי זה

582
00:26:57,330 --> 00:26:58,672
הולך לחנות בר המחרוזת.

583
00:26:58,672 --> 00:27:00,380
ואז שם לב רק
מעליה בערימה,

584
00:27:00,380 --> 00:27:02,505
כי בכל פעם שאתה שואל
לזיכרון במחסנית,

585
00:27:02,505 --> 00:27:04,310
זה הולך קצת
מעליו ציורי,

586
00:27:04,310 --> 00:27:06,270
הודעה שיש לנו 12 בתים שם.

587
00:27:06,270 --> 00:27:10,690
שמאל אחד העליון היא תושבת C אפס ו
את האדם הנכון התחתון הוא תושבת C 11.

588
00:27:10,690 --> 00:27:12,870
זה בדיוק איך המחשבים
הולך להוציא אותו.

589
00:27:12,870 --> 00:27:18,300
אז רק באופן אינטואיטיבי, אם בר יש יותר
מ -12 תווים בסך הכל, כוללים

590
00:27:18,300 --> 00:27:25,790
הקו הנטוי אפס, שבו הוא
12 או את תושבת C 12 הולכים?

591
00:27:25,790 --> 00:27:28,440
או לייתר דיוק שבו הוא ה -12
אופי או הדמות -13,

592
00:27:28,440 --> 00:27:30,900
האופי מאית הולך
בסופו של בתמונה?

593
00:27:30,900 --> 00:27:33,400
מעל או מתחת?

594
00:27:33,400 --> 00:27:36,300
>> נכון, כי למרות ש
הערימה עצמו גדלה כלפי מעלה,

595
00:27:36,300 --> 00:27:39,590
לאחר שהנחת את הדברים ב
זה, זה מסיבות עיצוב,

596
00:27:39,590 --> 00:27:41,294
מעביר את הזיכרון מלמעלה עד למטה.

597
00:27:41,294 --> 00:27:44,460
אז אם יש לך יותר מ 12 בתים,
אתה הולך להתחיל להחליף בר.

598
00:27:44,460 --> 00:27:47,280
עכשיו זה באג, אבל זה
לא ממש עניין גדול.

599
00:27:47,280 --> 00:27:51,130
אבל זה עניין גדול, כי יש
יותר דברים שקורים בזיכרון.

600
00:27:51,130 --> 00:27:53,074
אז הנה כיצד אוכל
לשים שלום, שיהיה ברור.

601
00:27:53,074 --> 00:27:54,490
אם הקלדתי בשלום בשורת.

602
00:27:54,490 --> 00:27:59,330
H-E-L-L-O קו נטוי אפס, בסופו של ב
12 בתים אלה, ואנחנו סופר בטוחים.

603
00:27:59,330 --> 00:28:00,330
הכל בסדר.

604
00:28:00,330 --> 00:28:03,020
אבל אם אני מקליד משהו
ארוך יותר, פוטנציאל זה

605
00:28:03,020 --> 00:28:05,860
הולך לזחול לתוך חלל הבר.

606
00:28:05,860 --> 00:28:08,405
אבל גרוע מכך, מתברר
את כל הזמן הזה,

607
00:28:08,405 --> 00:28:11,530
למרות שאנחנו אף פעם לא דיברנו על
זה, הערימה משמשת לדברים אחרים.

608
00:28:11,530 --> 00:28:13,560
זה לא רק משתנים מקומיים.

609
00:28:13,560 --> 00:28:15,100
>> C הוא שפה ברמה נמוכה מאוד.

610
00:28:15,100 --> 00:28:17,810
וזה סוג של בסתר
משתמש גם הערימה

611
00:28:17,810 --> 00:28:21,260
יש לזכור בעת
פונקציה נקראת, מה ש

612
00:28:21,260 --> 00:28:26,040
הכתובת היא של הפונקציה הקודמת,
כך שהוא יכול לקפוץ לראש הפונקציה ש.

613
00:28:26,040 --> 00:28:29,980
לכן, כאשר שיחות עיקריות להחליף בין,
הדברים דחפו על הערימה

614
00:28:29,980 --> 00:28:34,380
הם לא רק מחליף משתנים מקומיים,
או טענותיה, גם דחפו סתר

615
00:28:34,380 --> 00:28:37,510
על הערימה כפי שהוא מיוצג
על ידי פרוסה האדומה כאן,

616
00:28:37,510 --> 00:28:40,520
היא הכתובת של עיקרי פיזית
בזיכרון של המחשב שלך,

617
00:28:40,520 --> 00:28:44,180
כך שכאשר ההחלפה נעשה, המחשב
יודע שאני צריך לחזור לעיקרי

618
00:28:44,180 --> 00:28:46,760
ולסיים ביצוע הפונקציה העיקרית.

619
00:28:46,760 --> 00:28:51,960
אז זה מסוכן עכשיו, כי אם
המשתמש מקליד גם יותר מ שלום,

620
00:28:51,960 --> 00:28:57,030
כך שהקלט של המשתמש clobbers
או מחליף כי סעיף אדום,

621
00:28:57,030 --> 00:28:59,820
מבחינה לוגית, אם של המחשב
רק הולך להניח באופן עיוור

622
00:28:59,820 --> 00:29:03,830
כי הבתים שבפרוסה אדומה
הכתובת שאליה הוא אמור לחזור,

623
00:29:03,830 --> 00:29:09,020
מה אם היריב הוא או חכם מספיק
מזל מספיק כדי לשים רצף של בתים

624
00:29:09,020 --> 00:29:13,450
יש שנראה כמו כתובת,
אבל זה את הכתובת של קוד

625
00:29:13,450 --> 00:29:18,730
שהוא או היא רוצה מחשב
לבצע במקום מרכזי?

626
00:29:18,730 --> 00:29:21,670
>> במילים אחרות, אם מה ש
המשתמש להקליד בשורת הפקודה,

627
00:29:21,670 --> 00:29:23,850
הוא לא רק משהו
כמו מזיק שלום,

628
00:29:23,850 --> 00:29:28,210
אבל זה בעצם קוד זה שווה ערך
כדי למחוק את כל הקבצים של משתמש זה?

629
00:29:28,210 --> 00:29:30,060
או בדוא"ל את הסיסמה שלהם אליי?

630
00:29:30,060 --> 00:29:31,940
או להתחיל בכניסתם
הקשות, נכון?

631
00:29:31,940 --> 00:29:34,920
יש דרך, בואו נקבעו היום,
כי הם יכולים להקליד ולא רק שלום

632
00:29:34,920 --> 00:29:36,711
עולם או את שמם,
הם בעצם יכולים

633
00:29:36,711 --> 00:29:39,570
לעבור בקוד, אפסים ו
אלה, שהמחשב

634
00:29:39,570 --> 00:29:43,450
טעויות לשני קוד וכתובת.

635
00:29:43,450 --> 00:29:48,950
אז גם אם קצת מופשט, אם
משתמש מקליד קוד יריב מספיק

636
00:29:48,950 --> 00:29:52,330
שאנחנו להכליל כאן כ
א הוא התקפה או יריבים.

637
00:29:52,330 --> 00:29:53,140
דברים כל כך פשוט רעים.

638
00:29:53,140 --> 00:29:55,306
לא אכפת לנו
מספרים או האפסים או אלה

639
00:29:55,306 --> 00:29:59,470
היום, כאמור, כי אתה בסופו של
דריסת שהסעיף אדום,

640
00:29:59,470 --> 00:30:01,580
שם לב שהרצף של בתים.

641
00:30:01,580 --> 00:30:05,020
O 835 C אפס שמונה אפס.

642
00:30:05,020 --> 00:30:08,960
ועכשיו כמאמר של ויקיפדיה כאן
הציע, אם אתה עכשיו בעצם מתחיל

643
00:30:08,960 --> 00:30:12,460
תיוג הבתים במחשב שלך
זיכרון, מה הוא המאמר בויקיפדיה

644
00:30:12,460 --> 00:30:19,060
מציע הוא ש, מה אם כתובת
של שהבתים שמאלי העליונים הוא 80 C 0 3508.

645
00:30:19,060 --> 00:30:22,200
>> במילים אחרות, אם הבחור הרע הוא
חכם מספיק עם הקוד שלו או שלה

646
00:30:22,200 --> 00:30:26,650
למעשה לשים מספר כאן ש
תואם את הכתובת של הקוד

647
00:30:26,650 --> 00:30:29,180
הוא או היא הזריק
למחשב, אתה

648
00:30:29,180 --> 00:30:31,050
יכול להערים על המחשב
לעושה שום דבר.

649
00:30:31,050 --> 00:30:34,140
הסרת קבצים, דואר אלקטרוני
דברים, מרחרח את התנועה שלך,

650
00:30:34,140 --> 00:30:36,710
פשוטו כמשמעו, כל דבר יכול להיות
שהוחדר לתוך המחשב.

651
00:30:36,710 --> 00:30:39,220
וכך הצפת מאגר
פיגוע בליבה שלה

652
00:30:39,220 --> 00:30:43,530
רק טיפש, טיפש
העל של מערך ש

653
00:30:43,530 --> 00:30:45,840
לא היה לו גבולות מסומנים.

654
00:30:45,840 --> 00:30:48,850
וזה מה שהוא סופר מסוכן
ובו זמנית סופר חזק

655
00:30:48,850 --> 00:30:52,560
ב- C היא שאכן יש לנו
גישה לכל מקום בזיכרון.

656
00:30:52,560 --> 00:30:55,320
זה תלוי בנו, המתכנתים,
שכותב את הקוד המקורי

657
00:30:55,320 --> 00:30:59,330
כדי לבדוק את האורך לעזאזל של כל
מערכים שאנחנו מניפולציה.

658
00:30:59,330 --> 00:31:00,750
אז כדי להיות ברור, מה לתקן?

659
00:31:00,750 --> 00:31:03,190
אם לחזור לזה
קוד, שאני לא צריך רק

660
00:31:03,190 --> 00:31:08,000
לשנות את אורכו של בר, מה ש
עוד אני צריך לבדוק?

661
00:31:08,000 --> 00:31:10,620
מה עוד אני צריך לעשות כדי
למנוע התקפה זו לחלוטין?

662
00:31:10,620 --> 00:31:14,110
אני לא רוצה רק עיוור אומר
כי אתה צריך להעתיק בתים רבים

663
00:31:14,110 --> 00:31:16,140
כהוא אורך בר.

664
00:31:16,140 --> 00:31:18,910
אני רוצה לומר, להעתיק כ
בתים רבים כמו גם בבר

665
00:31:18,910 --> 00:31:24,090
עד שהוקצה
זיכרון, או 12 מקסימאלי.

666
00:31:24,090 --> 00:31:27,450
אז אני צריך קצת סוג של אם מצב
שעושה לבדוק את האורך של בר,

667
00:31:27,450 --> 00:31:32,800
אבל אם זה עולה על 12, קוד פשוט קשה לנו
12 כמרחק המרבי אפשרי.

668
00:31:32,800 --> 00:31:35,910
אחרת החיץ שנקרא
התקפת הצפה יכולה לקרות.

669
00:31:35,910 --> 00:31:38,451
בחלק התחתון של שקופיות אלה,
אם אתה סקרן לקרוא עוד

670
00:31:38,451 --> 00:31:41,200
הוא המאמר המקורי בפועל
אם אתה רוצה להעיף מבט.

671
00:31:41,200 --> 00:31:44,550
>> אבל עכשיו, בין המחירים
שילם כאן היה חוסר יעילות.

672
00:31:44,550 --> 00:31:46,680
אז זה היה מהיר
מבט ברמה נמוך במה

673
00:31:46,680 --> 00:31:49,709
בעיות יכולות להתעורר עכשיו אנחנו ש
יש להם גישה לזיכרון של המחשב.

674
00:31:49,709 --> 00:31:51,750
אבל בעיה נוספת ש
כבר נתקל ביום שני

675
00:31:51,750 --> 00:31:53,800
היה רק ​​חוסר היעילות
של רשימה מקושרת.

676
00:31:53,800 --> 00:31:56,019
אנחנו חוזרים לזמן ליניארי.

677
00:31:56,019 --> 00:31:57,560
כבר אין לנו מערך רציף.

678
00:31:57,560 --> 00:31:58,980
אין לנו גישה אקראית.

679
00:31:58,980 --> 00:32:00,710
אנחנו לא יכולים להשתמש בסימון הסוגר מרובע.

680
00:32:00,710 --> 00:32:04,590
פשוטו כמשמעו, יש לנו להשתמש בלולאה בזמן
כמו אחד שכתבתי לפני רגע.

681
00:32:04,590 --> 00:32:09,740
אבל ביום שני, אנחנו טענו שאנחנו יכולים
לזחול בחזרה לתחום של יעילות

682
00:32:09,740 --> 00:32:13,040
השגת משהו ש
לוגריתמים אולי, או הטוב ביותר עדיין,

683
00:32:13,040 --> 00:32:16,120
אולי אפילו משהו ש
מה שנקרא זמן קבוע.

684
00:32:16,120 --> 00:32:19,840
אז איך אנחנו יכולים לעשות את זה על ידי שימוש חדש
כלים, כתובות אלה, המצביעים הללו,

685
00:32:19,840 --> 00:32:22,210
ושחלת דברים משלנו?

686
00:32:22,210 --> 00:32:23,960
ובכן, נניח ש
כאן, אלה הם חבורה

687
00:32:23,960 --> 00:32:27,170
מספרים שאנו רוצים לאחסן ב
מבנה נתונים וחיפוש ביעילות.

688
00:32:27,170 --> 00:32:30,960
אנחנו יכולים להריץ אחורה בהחלט שבוע
שני, לזרוק אלה למערך,

689
00:32:30,960 --> 00:32:33,150
ולחפש אותם באמצעות חיפוש בינארי.

690
00:32:33,150 --> 00:32:34,040
הפרד ומשול.

691
00:32:34,040 --> 00:32:37,720
ולמעשה אתה כתב
חיפוש בינארי בPSET3,

692
00:32:37,720 --> 00:32:40,100
שבו אתה מיישם את התכנית למצוא.

693
00:32:40,100 --> 00:32:40,890
אבל אתה יודע מה.

694
00:32:40,890 --> 00:32:45,060
יש סוג של יותר
דרך חכמה לעשות את זה.

695
00:32:45,060 --> 00:32:47,390
זה קצת יותר
אולי מתוחכם ו

696
00:32:47,390 --> 00:32:50,830
מאפשר לנו לראות מדוע בינארי
חיפוש הוא כל כך הרבה יותר מהר.

697
00:32:50,830 --> 00:32:52,980
ראשית, בואו להציג
הרעיון של עץ.

698
00:32:52,980 --> 00:32:54,730
שלמרות ב
עצי מציאות מסוג

699
00:32:54,730 --> 00:32:57,730
לגדול כמו זה, בעולם של מחשב
מדע הם סוג של לגדול כלפי מטה

700
00:32:57,730 --> 00:33:00,830
כמו עץ ​​משפחה, שבו יש לך
הסבא והסבתא שלך או סבא וסבתא גדול

701
00:33:00,830 --> 00:33:04,580
או מה שלא בראש, הפטריארך ו
האם הגדול של המשפחה, רק אחד

702
00:33:04,580 --> 00:33:07,930
מה שנקרא שורש, צומת, להלן
שהם הילדים שלה,

703
00:33:07,930 --> 00:33:11,442
שמתחתיו הם ילדיה, או
הצאצאים שלה באופן כללי יותר.

704
00:33:11,442 --> 00:33:13,400
וכל מי שתלוי מ
החלק התחתון של המשפחה

705
00:33:13,400 --> 00:33:16,070
עץ, מלבד היותו
צעיר במשפחה,

706
00:33:16,070 --> 00:33:19,520
יכול גם להיות רק הגנרי
נקרא את העלים של העץ.

707
00:33:19,520 --> 00:33:21,800
>> אז זה סתם חבורה
של מילות והגדרות

708
00:33:21,800 --> 00:33:25,790
למשהו שנקרא עץ במחשב
מדע, כמו עץ ​​משפחה.

709
00:33:25,790 --> 00:33:28,770
אבל יש גלגולים להשתכלל
עצים, שאחד מהם

710
00:33:28,770 --> 00:33:30,780
נקרא עץ חיפוש בינארי.

711
00:33:30,780 --> 00:33:34,380
ואתה יכול סוג של להקניט
מלבד מה שעושה את הדבר הזה.

712
00:33:34,380 --> 00:33:37,180
ובכן, זה בינארי באיזה מובן?

713
00:33:37,180 --> 00:33:41,455
איפה ינארי מגיע מכאן?

714
00:33:41,455 --> 00:33:41,955
מצטער?

715
00:33:41,955 --> 00:33:45,961

716
00:33:45,961 --> 00:33:47,210
זה לא כל כך הרבה או או.

717
00:33:47,210 --> 00:33:52,000
זה יותר שכל אחד מהצמתים אין
יותר משני ילדים, כפי שאנו רואים כאן.

718
00:33:52,000 --> 00:33:54,990
באופן כללי, וtree--
ההורים והסבים שלך

719
00:33:54,990 --> 00:33:57,640
יכול להיות כמה שיותר ילדים או
נכדים כפי שהם באמת רוצים,

720
00:33:57,640 --> 00:34:00,820
וכך למשל יש לנו שלוש
ילדים שמיד ימין הצומת,

721
00:34:00,820 --> 00:34:05,480
אבל בעץ בינארי, יש צומת
אפס, אחד, או שני ילדים מקסימאלי.

722
00:34:05,480 --> 00:34:08,496
וזה נכס נחמד,
כי אם זה כתרים על ידי שתי,

723
00:34:08,496 --> 00:34:10,620
אנחנו הולכים להיות מסוגלים
לקבל בסיס יומן קטן שני

724
00:34:10,620 --> 00:34:11,975
פעולה קורה כאן סופו של דבר.

725
00:34:11,975 --> 00:34:13,350
אז יש לנו משהו לוגריתמית.

726
00:34:13,350 --> 00:34:14,558
אבל עוד על כך ברגע.

727
00:34:14,558 --> 00:34:19,810
עץ חיפוש משמעות הדבר היא כי המספרים
מסודר כך שהילד השמאלי של

728
00:34:19,810 --> 00:34:22,429
הערך גדול מהשורש.

729
00:34:22,429 --> 00:34:26,010
והילד שלה הנכון הוא
גדול יותר מהשורש.

730
00:34:26,010 --> 00:34:29,290
במילים אחרות, אם אתה לוקח את כל
צמתים, חוגים בתמונה הזאת,

731
00:34:29,290 --> 00:34:31,840
ומסתכל על השמאל שלה
ילד והילד שלה תקין,

732
00:34:31,840 --> 00:34:34,739
הראשון צריך להיות פחות מ,
השני צריכים להיות גדול מ.

733
00:34:34,739 --> 00:34:36,159
אז שפיות לבדוק 55.

734
00:34:36,159 --> 00:34:37,780
זה שנשאר ילד הוא 33.

735
00:34:37,780 --> 00:34:38,620
זה פחות מ.

736
00:34:38,620 --> 00:34:40,929
55, הילד שלה תקין הוא 77.

737
00:34:40,929 --> 00:34:41,783
זה גדול יותר מ.

738
00:34:41,783 --> 00:34:43,199
וזה הגדרה רקורסיבית.

739
00:34:43,199 --> 00:34:46,480
אנחנו יכולים לבדוק כל אחד מאותם
בלוטות ואת אותו הדפוס יחזיק.

740
00:34:46,480 --> 00:34:49,389
>> אז מה נחמד ב
עץ החיפוש בינארי, הוא

741
00:34:49,389 --> 00:34:52,204
כי אחד, אנחנו יכולים ליישם את זה
עם struct, בדיוק כמו זה.

742
00:34:52,204 --> 00:34:54,620
ואף על פי שאנחנו זורקים
הרבה מבנים בך,

743
00:34:54,620 --> 00:34:56,560
הם במידה מסוימת
אינטואיטיבי עכשיו בתקווה.

744
00:34:56,560 --> 00:35:00,570
התחביר הוא עדיין מסתורי בודאות,
אבל התוכן של צומת בזה

745
00:35:00,570 --> 00:35:02,786
context-- ואנחנו שומרים
שימוש במילה צומת,

746
00:35:02,786 --> 00:35:04,910
בין אם זה מלבן
על המסך או מעגל,

747
00:35:04,910 --> 00:35:08,970
זה רק חלק מיכל גנריות,
במקרה זה של עץ, כמו אחד

748
00:35:08,970 --> 00:35:11,780
ראינו, אנחנו צריכים שלמים
בכל אחד מהצמתים

749
00:35:11,780 --> 00:35:15,460
ואז אני צריך הצבעה שני מצביעים
לילד השמאלי והילד תקין,

750
00:35:15,460 --> 00:35:16,590
בהתאמה.

751
00:35:16,590 --> 00:35:20,730
אז זה כיצד תוכל
ליישם את זה בstruct.

752
00:35:20,730 --> 00:35:22,315
ואיך אני יכול ליישם את זה בקוד?

753
00:35:22,315 --> 00:35:26,730
ובכן, בואו ניקח מהיר
תתבונן בדוגמה קטנה זו.

754
00:35:26,730 --> 00:35:29,820
זה לא פונקציונלי, אבל יש לי
להעתיק ולהדביק מבנה ש.

755
00:35:29,820 --> 00:35:33,510
ואם הפונקציה שלי לינארי
עץ חיפוש נקרא חיפוש,

756
00:35:33,510 --> 00:35:36,980
וזה לוקח שני טיעונים,
N מספר שלם ומצביע

757
00:35:36,980 --> 00:35:41,400
לצומת, ולכן מצביע לעץ
או מצביע לשורש של עץ,

758
00:35:41,400 --> 00:35:43,482
איך אני הולך על חיפוש עבור N?

759
00:35:43,482 --> 00:35:45,440
ובכן, ראשית, כי אני
התמודדות עם מצביעים,

760
00:35:45,440 --> 00:35:46,750
אני הולך לעשות בדיקת שפיות.

761
00:35:46,750 --> 00:35:54,279
אם שווים עץ שווים null, הוא N
בעץ הזה או לא בעץ הזה?

762
00:35:54,279 --> 00:35:55,070
זה לא יכול להיות, נכון?

763
00:35:55,070 --> 00:35:56,870
אם אני האחרון null,
אין שם כלום.

764
00:35:56,870 --> 00:35:59,230
אני יכול גם פשוט
עיוור אומרים לחזור שווא.

765
00:35:59,230 --> 00:36:04,050
אם אתה נותן לי שום דבר, אני לא יכול ללא ספק
למצוא כל מספר נ 'אז מה עוד יכול אני

766
00:36:04,050 --> 00:36:04,750
בדוק עכשיו?

767
00:36:04,750 --> 00:36:12,830
אני הולך לומר גם אחר, אם N הוא
פחות מכל מה שהוא בצומת העץ

768
00:36:12,830 --> 00:36:16,300
כי אני כבר מסרתי ערך N.

769
00:36:16,300 --> 00:36:20,270
במילים אחרות, אם אני המספר
מחפש, N, הוא פחות מהצומת

770
00:36:20,270 --> 00:36:21,340
שאני מסתכל.

771
00:36:21,340 --> 00:36:23,190
והצומת אני מחפש
בנקרא עץ,

772
00:36:23,190 --> 00:36:26,370
וזוכר מהדוגמא הקודמת
כדי להגיע לערך במצביע,

773
00:36:26,370 --> 00:36:28,310
אני משתמש בסימון החץ.

774
00:36:28,310 --> 00:36:35,960
אז אם N הוא פחות מחץ עץ
N, אני רוצה ללכת שמאל מושגית.

775
00:36:35,960 --> 00:36:38,590
איך אני מביע גששתי ימינה?

776
00:36:38,590 --> 00:36:41,560
כדי להיות ברור, אם זה
התמונה בשאלה,

777
00:36:41,560 --> 00:36:44,612
וכבר עבר לי כי עליון
חץ שמצביע למטה.

778
00:36:44,612 --> 00:36:45,570
זה מצביע העץ שלי.

779
00:36:45,570 --> 00:36:48,060
אני מצביע על השורש של העץ.

780
00:36:48,060 --> 00:36:52,100
ואני מחפש למשל, ל
המספר 44, באופן שרירותי.

781
00:36:52,100 --> 00:36:55,300
האם 44 פחות או
יותר מ -55 ברור?

782
00:36:55,300 --> 00:36:56,360
אז זה פחות מ.

783
00:36:56,360 --> 00:36:58,760
וכך זה אם המצב חל.

784
00:36:58,760 --> 00:37:03,981
אז מבחינה רעיונית, מה אני רוצה
חיפוש הבא אם אני מחפש 44?

785
00:37:03,981 --> 00:37:04,480
כן?

786
00:37:04,480 --> 00:37:08,310

787
00:37:08,310 --> 00:37:11,100
>> בדיוק, אני רוצה
לחפש את הילד השמאלי,

788
00:37:11,100 --> 00:37:12,789
או תת-העץ השמאלי של תמונה זו.

789
00:37:12,789 --> 00:37:14,830
ולמעשה, תן לי דרך
התמונה כאן למטה

790
00:37:14,830 --> 00:37:17,770
רק לרגע, שכן
אני לא יכול לגרד את זה.

791
00:37:17,770 --> 00:37:21,150
אם אני אתחיל כאן בגיל 55, ו
אני יודע שהערך 44

792
00:37:21,150 --> 00:37:23,180
אני מחפש ל
השמאל, שזה סוג

793
00:37:23,180 --> 00:37:26,010
כמו קורע את ספר טלפונים ב
מחצית או קורע את העץ במחצית.

794
00:37:26,010 --> 00:37:29,660
אני כבר לא צריך לדאוג
מחצית שלמה זה של העץ.

795
00:37:29,660 --> 00:37:33,270
ובכל זאת, בסקרנות במונחים של
מבנה, הדבר הזה כאן ש

796
00:37:33,270 --> 00:37:36,682
מתחיל עם 33, שעצמו
הוא עץ חיפוש בינארי.

797
00:37:36,682 --> 00:37:39,890
אמרתי את המילה רקורסיבית לפני כי
אכן זה הוא מבנה נתונים ש

798
00:37:39,890 --> 00:37:41,707
על פי הגדרה הוא רקורסיבית.

799
00:37:41,707 --> 00:37:44,540
אולי יש לך עץ זה זה
גדול, אבל כל אחד מילדיה

800
00:37:44,540 --> 00:37:46,870
מייצג עץ רק קצת יותר קטן.

801
00:37:46,870 --> 00:37:50,910
במקום שזה יהיה סבא
או סבתא, עכשיו זה רק אמא

802
00:37:50,910 --> 00:37:54,300
or-- אני לא יכול say-- לא אמא
או אבא, זה יהיה מוזר.

803
00:37:54,300 --> 00:37:59,000
במקום שני הילדים יש
היה כמו אחות ואח להיות.

804
00:37:59,000 --> 00:38:01,120
דור חדש של עץ המשפחה.

805
00:38:01,120 --> 00:38:02,900
אבל מבחינה מבנית, זה אותו הרעיון.

806
00:38:02,900 --> 00:38:06,790
ומתברר שיש לי פונקציה
עם שאני יכול לחפש בחיפוש בינארי

807
00:38:06,790 --> 00:38:07,290
עץ.

808
00:38:07,290 --> 00:38:08,680
זה נקרא חיפוש.

809
00:38:08,680 --> 00:38:17,870
אני מחפש את N בשמאל חץ עץ
אחר אם N הוא גדול מהערך

810
00:38:17,870 --> 00:38:18,870
כי אני כרגע ב.

811
00:38:18,870 --> 00:38:20,800
55 בסיפור לפני רגע.

812
00:38:20,800 --> 00:38:23,780
יש לי פונקציה שנקראת
חיפוש שאני רק יכול

813
00:38:23,780 --> 00:38:29,660
לעבור N זה ואופן רקורסיבי חיפוש
תת-העץ ורק תמורה

814
00:38:29,660 --> 00:38:30,620
מה תשובה ש.

815
00:38:30,620 --> 00:38:33,530
אחר יש לי כמה מקרה בסיס סופי כאן.

816
00:38:33,530 --> 00:38:35,310
>> מהו המקרה האחרון?

817
00:38:35,310 --> 00:38:36,570
העץ הוא גם null.

818
00:38:36,570 --> 00:38:39,980
הערך אני גם אני מחפש
פחות מזה או גדול יותר מזה

819
00:38:39,980 --> 00:38:42,610
או שווה לה.

820
00:38:42,610 --> 00:38:44,750
ואני יכול להגיד שווה
שווה, אבל מבחינה לוגית זה

821
00:38:44,750 --> 00:38:46,500
שווה רק אומר אחר כאן.

822
00:38:46,500 --> 00:38:49,150
כל כך נכון הוא איך אני מוצא משהו.

823
00:38:49,150 --> 00:38:51,710
אז אני מקווה שזה הוא
אפילו דוגמא משכנעת יותר

824
00:38:51,710 --> 00:38:54,900
מפונקצית סיגמא הטיפש
עשינו כמה הרצאות בחזרה,

825
00:38:54,900 --> 00:38:58,360
איפה זה היה פשוט קל לשימוש לולאה
לספור את כל מספרים מאחד

826
00:38:58,360 --> 00:39:02,390
נ 'כאן עם מבנה נתונים
שעצמו הוא באופן רקורסיבי

827
00:39:02,390 --> 00:39:07,050
מוגדרים ונמשכים באופן רקורסיבי, עכשיו אנחנו
יש את היכולת לבטא את עצמנו

828
00:39:07,050 --> 00:39:09,780
בקוד שעצמו הוא רקורסיבית.

829
00:39:09,780 --> 00:39:12,580
אז זה בדיוק אותו הקוד כאן.

830
00:39:12,580 --> 00:39:14,400
>> אז מה בעיות אחרות שאנחנו יכולים לפתור?

831
00:39:14,400 --> 00:39:18,160
אז צעד מהיר מ
עצים לרגע.

832
00:39:18,160 --> 00:39:20,130
הנה, אומר, את הדגל הגרמני.

833
00:39:20,130 --> 00:39:22,020
ויש באופן ברור
דפוס לדגל הזה.

834
00:39:22,020 --> 00:39:23,811
ויש המון
דגלים בעולם ש

835
00:39:23,811 --> 00:39:27,560
הם פשוט כמו זה במונחים
הצבעים ודפוסים שלהם.

836
00:39:27,560 --> 00:39:31,930
אבל נניח שזה מאוחסן כ
.GIF, או JPEG, או מפת סיביות, או פינג,

837
00:39:31,930 --> 00:39:34,240
כל קובץ בפורמט גרפי
עם שאתה מכיר,

838
00:39:34,240 --> 00:39:36,460
שחלקם אנחנו
לשחק עם בPSET4.

839
00:39:36,460 --> 00:39:41,550
זה לא נראה כדאי לאחסן
פיקסל השחור, פיקסלים שחורים, פיקסלים שחורים,

840
00:39:41,550 --> 00:39:44,790
נקודה, נקודה, נקודה, חבורה של כל
פיקסלים שחורים לScanline הראשון,

841
00:39:44,790 --> 00:39:47,430
או שורה, אז חבורה של כל
אותו אז כל חבורה,

842
00:39:47,430 --> 00:39:49,530
מאותו, ולאחר מכן
כל חבורה של פיקסלים אדומים,

843
00:39:49,530 --> 00:39:53,020
פיקסלים אדומים, פיקסלים אדומים, אז כל
חבורה של פיקסלים צהובים, צהובה, נכון?

844
00:39:53,020 --> 00:39:55,050
>> יש חוסר יעילות כזו כאן.

845
00:39:55,050 --> 00:39:59,040
איך היית באופן אינטואיטיבי
לדחוס את הדגל הגרמני

846
00:39:59,040 --> 00:40:01,320
אם יישומו כקובץ?

847
00:40:01,320 --> 00:40:04,940
כמו איזה מידע יכול שלא
מפריע אחסון בדיסק כדי

848
00:40:04,940 --> 00:40:08,040
כדי להקטין את גודל הקובץ שלנו כמ
מגה לקילובייט, משהו

849
00:40:08,040 --> 00:40:09,430
קטן יותר?

850
00:40:09,430 --> 00:40:13,130
היכן טמונה היתירות
כאן צריך להיות ברור?

851
00:40:13,130 --> 00:40:13,880
מה אתה יכול לעשות?

852
00:40:13,880 --> 00:40:14,380
כן?

853
00:40:14,380 --> 00:40:21,380

854
00:40:21,380 --> 00:40:21,970
בדיוק.

855
00:40:21,970 --> 00:40:24,550
למה לא ולא זוכר
הצבע של כל פיקסל לעזאזל

856
00:40:24,550 --> 00:40:28,200
בדיוק כמו שאתה עושה בPSET4
עם פורמט קובץ מפת הסיביות,

857
00:40:28,200 --> 00:40:32,060
למה אתה לא רק מייצג את
העמודה השמאלית ביותר של פיקסלים, למשל

858
00:40:32,060 --> 00:40:35,370
חבורה של פיקסלים שחורים, חבורה
של אדום, וחבורה של צהוב,

859
00:40:35,370 --> 00:40:39,210
ואז פשוט איכשהו לקודד
רעיון של חזרה 100 פעמים

860
00:40:39,210 --> 00:40:41,020
או לחזור על 1,000 פעמים זה?

861
00:40:41,020 --> 00:40:43,430
איפה 100 או 1,000 הוא
רק מספר שלם, כך ש

862
00:40:43,430 --> 00:40:47,290
יכול לברוח עם רק מספר בודד
במקום מאות או אלפים

863
00:40:47,290 --> 00:40:48,270
פיקסלים של נוספים.

864
00:40:48,270 --> 00:40:50,990
ואכן, זה איך אנחנו
יכול לדחוס את הדגל הגרמני.

865
00:40:50,990 --> 00:40:51,490
ו

866
00:40:51,490 --> 00:40:53,470
עכשיו מה לגבי הדגל הצרפתי?

867
00:40:53,470 --> 00:40:58,930
וקצת סוג של
תרגיל מחשבי, שדגל

868
00:40:58,930 --> 00:41:01,040
יכול להיות דחוס יותר בדיסק?

869
00:41:01,040 --> 00:41:05,720
הדגל הגרמני או צרפתית
דגל, אם תיקח גישה ש?

870
00:41:05,720 --> 00:41:08,490
הדגל הגרמני, משום שיש
יתירות אופקית יותר.

871
00:41:08,490 --> 00:41:12,190
ועל ידי עיצוב, קובץ גרפי רב
פורמטים אכן עובדים קווי סריקה כ

872
00:41:12,190 --> 00:41:12,830
אופקי.

873
00:41:12,830 --> 00:41:14,674
הם יכולים לעבוד
אנכי, אנושות רק

874
00:41:14,674 --> 00:41:17,090
לפני שנים החליטו שנוסיף ל
בדרך כלל חושב על שורת דברים

875
00:41:17,090 --> 00:41:18,880
על ידי שורה במקום טור על ידי טור.

876
00:41:18,880 --> 00:41:20,820
אז אכן אם היית
להסתכל על הקובץ

877
00:41:20,820 --> 00:41:24,670
גודל של דגל גרמני וצרפתית
דגל, כל עוד ההחלטה היא

878
00:41:24,670 --> 00:41:27,530
אותו הדבר, באותו הרוחב
וגובה, זה אחד

879
00:41:27,530 --> 00:41:31,580
כאן הולך להיות גדול יותר, כי אתה
צריך לחזור על עצמך שלוש פעמים.

880
00:41:31,580 --> 00:41:35,570
אתה צריך לציין כחול, חזור
את עצמך, לבן, לחזור על עצמך, אדום,

881
00:41:35,570 --> 00:41:36,740
לחזור על עצמך.

882
00:41:36,740 --> 00:41:39,000
אתה לא יכול פשוט ללכת כל
בדרך לימין.

883
00:41:39,000 --> 00:41:41,200
וכמו בצד, לעשות
לנקות את הדחיסה

884
00:41:41,200 --> 00:41:43,910
נמצא בכל מקום, אם אלה הם
ארבע מסגרות מvideo--

885
00:41:43,910 --> 00:41:45,890
אולי זוכר שסרט
או וידאו הוא בדרך כלל

886
00:41:45,890 --> 00:41:47,286
כמו 29 או 30 פריימים לשניה.

887
00:41:47,286 --> 00:41:50,410
זה כמו ספר להעיף קטן שבו אתה
רק לראות את התמונה, תמונה, תמונה, תמונה,

888
00:41:50,410 --> 00:41:54,410
תמונה רק סופר מהיר כל כך שזה נראה כמו
השחקנים על המסך נעים.

889
00:41:54,410 --> 00:41:57,130
הנה דבורה ב
העליון של זר פרחים.

890
00:41:57,130 --> 00:41:59,790
ואף על פי שזה יכול להיות סוג של
קשה לראות במבט ראשון,

891
00:41:59,790 --> 00:42:04,020
הדבר היחיד שנע ב
הסרט הזה הוא הדבורה.

892
00:42:04,020 --> 00:42:06,880
>> מה הוא מטומטם על אחסון
וידאו לא דחוס?

893
00:42:06,880 --> 00:42:11,420
זה סוג של בזבוז לאחסון וידאו
כארבע תמונות כמעט זהות ש

894
00:42:11,420 --> 00:42:13,670
שונה רק במידה שבי הדבורה היא.

895
00:42:13,670 --> 00:42:16,280
אתה יכול לזרוק ביותר
מידע ש

896
00:42:16,280 --> 00:42:20,190
וזוכר רק, למשל,
הפריים הראשון והפריים האחרון,

897
00:42:20,190 --> 00:42:22,180
מסגרות מפתח אם יש לך
אי פעם שמע את המילה,

898
00:42:22,180 --> 00:42:24,337
ורק לאחסן ב
אמצע שבו הדבורה היא.

899
00:42:24,337 --> 00:42:26,170
ואין לך ל
לאחסן את כל הוורוד,

900
00:42:26,170 --> 00:42:28,330
והכחול, ו
ערכים ירוקים גם כן.

901
00:42:28,330 --> 00:42:31,200
אז זה אומר רק ש
דחיסה היא בכל מקום.

902
00:42:31,200 --> 00:42:34,900
זוהי טכניקה לעתים קרובות אנו משתמשים
או לוקח כמובן מאליו בימים אלה.

903
00:42:34,900 --> 00:42:38,750
>> אבל איך אתה לדחוס טקסט?

904
00:42:38,750 --> 00:42:40,450
איך אתה הולך על דחיסת טקסט?

905
00:42:40,450 --> 00:42:45,410
ובכן, כל אחת מהדמויות ב
ASCII הוא בית אחד, או שמונה סיביות.

906
00:42:45,410 --> 00:42:47,360
וזה סוג של מטומטם, נכון?

907
00:42:47,360 --> 00:42:51,160
מכיוון שאתה כנראה להקליד
ו- E ואני וO וU הרבה

908
00:42:51,160 --> 00:42:55,270
לעתים קרובות יותר מאשר כמו W או Q או Z,
בהתאם לשפה שבי

909
00:42:55,270 --> 00:42:56,610
אתה כותב בהחלט.

910
00:42:56,610 --> 00:42:59,600
ואז למה אנחנו משתמשים ב
שמונה סיביות לכל אות,

911
00:42:59,600 --> 00:43:02,040
כולל לפחות
אותיות פופולריות, נכון?

912
00:43:02,040 --> 00:43:05,300
למה לא להשתמש פחות סיביות ל
מכתבי סופר הפופולריים,

913
00:43:05,300 --> 00:43:07,760
כמו E, הדברים שאתה מניח
ראשון בגלגל המזל,

914
00:43:07,760 --> 00:43:10,450
ולהשתמש יותר ביטים ל
האותיות פחות פופולריות?

915
00:43:10,450 --> 00:43:10,950
למה?

916
00:43:10,950 --> 00:43:13,130
כי אנחנו פשוט הולכים
להשתמש בם בתדירות נמוכה יותר.

917
00:43:13,130 --> 00:43:15,838
>> ובכן, מתברר שיש לי
היה ניסיונות לעשות את זה.

918
00:43:15,838 --> 00:43:18,630
ואם אתה זוכר מכיתה
בית ספר או תיכון, קוד מורס.

919
00:43:18,630 --> 00:43:20,400
יש קוד מורס נקודות
ומקפים שיכולים להיות

920
00:43:20,400 --> 00:43:24,270
מועבר לאורך חוט כ
נשמע או אותות מסוג כלשהו.

921
00:43:24,270 --> 00:43:25,930
אבל קוד המורס הוא סופר נקי.

922
00:43:25,930 --> 00:43:29,010
זה סוג של מערכת בינארית ב
כי יש לך נקודות או מקפים.

923
00:43:29,010 --> 00:43:30,977
אבל אם אתה רואה, למשל, שתי נקודות.

924
00:43:30,977 --> 00:43:33,810
או אם אתה חושב בחזרה למפעיל
מי הולך כמו צפצוף, צפצוף, צפצוף,

925
00:43:33,810 --> 00:43:36,760
צפצוף, להכות קצת הדק
שמשדר אות,

926
00:43:36,760 --> 00:43:40,360
אם אתה, הנמען, מקבל שני
נקודות, מה מסר שקבלתן?

927
00:43:40,360 --> 00:43:43,490
שרירותי לחלוטין.

928
00:43:43,490 --> 00:43:44,450
>> אני?

929
00:43:44,450 --> 00:43:45,060
אני?

930
00:43:45,060 --> 00:43:47,500
או מה על-- או אני?

931
00:43:47,500 --> 00:43:49,570
אולי זה היה רק ​​שתי תקין של E?

932
00:43:49,570 --> 00:43:52,480
אז יש את הבעיה הזאת
של decodability עם מורס

933
00:43:52,480 --> 00:43:54,890
קוד, לפיו, אלא אם כן
אדם שולח לך הודעה

934
00:43:54,890 --> 00:43:59,510
עוצר למעשה, כך שאתה יכול למיין של
לראות או לשמוע את הפערים בין אותיות,

935
00:43:59,510 --> 00:44:02,990
זה לא מספיק רק ל
לשלוח זרם של אפסים ואחדים,

936
00:44:02,990 --> 00:44:05,610
או נקודות ומקפים,
כי יש עמימות.

937
00:44:05,610 --> 00:44:08,640
E היא נקודה אחת, כך שאם אתה
רואה שתי נקודות או לשמוע שתי נקודות,

938
00:44:08,640 --> 00:44:11,254
אולי זה שתי E של או אולי זה I. אחד

939
00:44:11,254 --> 00:44:13,670
אז אנחנו צריכים מערכת זה
קצת יותר חכם מזה.

940
00:44:13,670 --> 00:44:16,851
שנות האפמן אז אדם בשם
לפני באתי עם זה בדיוק.

941
00:44:16,851 --> 00:44:18,600
אז אנחנו פשוט הולכים
לקחת מבט מהיר

942
00:44:18,600 --> 00:44:20,114
בכמה עצים רלוונטיים לזה.

943
00:44:20,114 --> 00:44:22,530
נניח שזה חלק
הודעה טיפשית שאתה רוצה לשלוח,

944
00:44:22,530 --> 00:44:26,342
מורכב מרק A, B, של ד 'של C ו- E של,
אבל יש הרבה יתירות כאן.

945
00:44:26,342 --> 00:44:27,550
זה לא אמור להיות באנגלית.

946
00:44:27,550 --> 00:44:28,341
זה לא מוצפן.

947
00:44:28,341 --> 00:44:30,540
זה פשוט טיפשי הודעה
עם הרבה חזרות.

948
00:44:30,540 --> 00:44:34,010
אז אם אתה באמת לספור את כל
של, B של, C של, D's, ו- E של, הנה

949
00:44:34,010 --> 00:44:34,890
התדירות.

950
00:44:34,890 --> 00:44:37,800
20% מהאותיות
של, 45% מהאותיות

951
00:44:37,800 --> 00:44:39,660
הם E של, ושלושה תדרים אחרים.

952
00:44:39,660 --> 00:44:41,960
ספרנו שם למעלה באופן ידני
ורק עשיתי את החשבון.

953
00:44:41,960 --> 00:44:44,579
>> אז מתברר ש
האפמן, לפני כמה זמן,

954
00:44:44,579 --> 00:44:46,620
הבין את זה, אתה יודע
מה, אם אני מתחיל בניין

955
00:44:46,620 --> 00:44:51,172
עץ, או יער של עצים, אם תרצה,
כדלקמן, אני יכול לעשות את הדברים הבאים.

956
00:44:51,172 --> 00:44:53,880
אני הולך לתת לי צומת לכל
של המכתבים שאכפת לי

957
00:44:53,880 --> 00:44:55,530
ואני הולך לחנות
בתוך הצומת ש

958
00:44:55,530 --> 00:44:58,610
התדרים כנקודה צפה
ערך, או שאתה יכול להשתמש בו N, מדי,

959
00:44:58,610 --> 00:45:00,210
אבל אנחנו פשוט להשתמש לצוף כאן.

960
00:45:00,210 --> 00:45:03,100
והאלגוריתם ש
הוא הציע הוא שאתה

961
00:45:03,100 --> 00:45:07,210
לקחת יער זה של צומת אחת
עצים, עצים כל כך סופר קצרים,

962
00:45:07,210 --> 00:45:11,920
ואתה מתחיל לחבר אותם עם
קבוצות חדשות, הורים חדשים, אם תרצה.

963
00:45:11,920 --> 00:45:16,150
ואתה עושה את זה על ידי הבחירה
שני תדרים קטנים בכל פעם.

964
00:45:16,150 --> 00:45:18,110
אז לקחתי 10% ו -10%.

965
00:45:18,110 --> 00:45:19,090
אני יוצר צומת חדש.

966
00:45:19,090 --> 00:45:20,910
ואני קורא לצומת החדשה 20%.

967
00:45:20,910 --> 00:45:22,750
>> ששני צמתים אני משלב הבא?

968
00:45:22,750 --> 00:45:23,810
זה קצת מעורפל.

969
00:45:23,810 --> 00:45:26,643
אז יש כמה מקרי פינה ל
לשקול, אלא כדי לשמור על דברים יפים,

970
00:45:26,643 --> 00:45:29,300
אני הולך לבחור 20% -
עכשיו אני מתעלם הילדים.

971
00:45:29,300 --> 00:45:33,640
אני הולך לבחור 20% ו
15% ולצייר שני קצוות חדשים.

972
00:45:33,640 --> 00:45:35,624
ועכשיו ששני צמתים
אני לוגי לשלב?

973
00:45:35,624 --> 00:45:38,540
להתעלם מכל הילדים, כל
נכדים, רק להסתכל על השורשים

974
00:45:38,540 --> 00:45:39,070
עכשיו.

975
00:45:39,070 --> 00:45:42,220
ששני צמתים אני קושר יחד?

976
00:45:42,220 --> 00:45:44,530
נקודה שתיים ו0.35.

977
00:45:44,530 --> 00:45:45,890
אז תן לי לצייר שני קצוות חדשים.

978
00:45:45,890 --> 00:45:47,570
ואז יש לי רק אחד שמאלה.

979
00:45:47,570 --> 00:45:48,650
אז הנה עץ.

980
00:45:48,650 --> 00:45:51,160
וזה נמשך במכוון
לחפש סוג של די,

981
00:45:51,160 --> 00:45:55,870
אבל שמתי לב שיש לי הקצוות
גם כותרתו אפס ואחד.

982
00:45:55,870 --> 00:45:59,510
אז כל הקצוות השמאלי הוא אפס
באופן שרירותי, אלא באופן עקבי.

983
00:45:59,510 --> 00:46:01,170
כל הקצוות ימני הם אלה.

984
00:46:01,170 --> 00:46:05,070
>> ואז מה הופמן המוצע,
אם אתה רוצה לייצג B,

985
00:46:05,070 --> 00:46:10,080
ולא מייצג את המספר 66 כ
Ascii שהוא שמונה סיביות כל,

986
00:46:10,080 --> 00:46:13,360
אתה יודע מה חנות, רק
הדפוס אפס, אפס, אפס,

987
00:46:13,360 --> 00:46:17,030
אפס, כי זה הדרך
מהעץ שלי, העץ של מר האפמן,

988
00:46:17,030 --> 00:46:18,600
לעלה מהשורש.

989
00:46:18,600 --> 00:46:20,970
אם אתה רוצה לאחסן
E, לעומת זאת, לא

990
00:46:20,970 --> 00:46:26,290
לשלוח שמונה סיביות שמייצגים א
במקום זאת, לשלוח מה דפוס של ביטים?

991
00:46:26,290 --> 00:46:26,890
אחד.

992
00:46:26,890 --> 00:46:30,410
ומה שיפה זה
E שהיא האות הפופולרית ביותר,

993
00:46:30,410 --> 00:46:32,340
ואתה משתמש ב
הקוד הקצר ביותר לזה.

994
00:46:32,340 --> 00:46:34,090
הבא הפופולרי ביותר
מכתב נראה כמו זה

995
00:46:34,090 --> 00:46:37,380
היה א וכך כמה ביטים
האם הוא מציע באמצעות בשביל זה?

996
00:46:37,380 --> 00:46:38,270
אפס, אחד.

997
00:46:38,270 --> 00:46:41,060
>> וכי זה מיושם
כעץ הזה, לעת עתה

998
00:46:41,060 --> 00:46:43,350
תן לי לקבוע שיש
אין עמימות כבמורס

999
00:46:43,350 --> 00:46:46,090
קוד, כי כל
מכתבים שאכפת לך

1000
00:46:46,090 --> 00:46:48,780
הם בסופו של הקצוות הללו.

1001
00:46:48,780 --> 00:46:50,580
אז זה רק אחד
יישומו של עץ.

1002
00:46:50,580 --> 00:46:52,538
זה הוא-- ואני אנופף
היד שלי בשלב זה איך אתה

1003
00:46:52,538 --> 00:46:55,570
אולי ליישם את זה כמבנה C.

1004
00:46:55,570 --> 00:46:58,260
אנחנו פשוט צריכים לשלב
סמל, כמו char,

1005
00:46:58,260 --> 00:46:59,910
והתדירות בימין ועל שמאל.

1006
00:46:59,910 --> 00:47:02,510
אבל בואו נסתכל על שתי
דוגמאות סופיות כי אתה

1007
00:47:02,510 --> 00:47:06,070
לקבל מכיר היטב לאחר
חידון אפס בבעיה להגדיר חמש.

1008
00:47:06,070 --> 00:47:09,210
>> אז יש את מבנה הנתונים
ידוע כשולחן חשיש.

1009
00:47:09,210 --> 00:47:12,247
ושולחן חשיש הוא סוג של
לקרר שביש לו דליים.

1010
00:47:12,247 --> 00:47:14,830
ונניח שיש ארבעה דליים
כאן, רק ארבעה חללים ריקים.

1011
00:47:14,830 --> 00:47:20,830
הנה חפיסת קלפים, וכאן היא
מועדון, את חפירה, מועדון, יהלומים, מועדון,

1012
00:47:20,830 --> 00:47:25,960
יהלומים, מועדון, יהלומים,
clubs-- אז זה אקראי.

1013
00:47:25,960 --> 00:47:30,330
לבבות, hearts-- אז אני
bucketizing כל התשומות כאן.

1014
00:47:30,330 --> 00:47:32,430
וצרכימי שולחן חשיש
להסתכל על הקלט שלך,

1015
00:47:32,430 --> 00:47:34,850
ואז לשים אותו במסוים
מקום המבוסס על מה שאתה רואה.

1016
00:47:34,850 --> 00:47:35,600
זה אלגוריתם.

1017
00:47:35,600 --> 00:47:37,980
ואני משתמש בסופר
אלגוריתם חזותי פשוט.

1018
00:47:37,980 --> 00:47:40,030
החלק הקשה ביותר שהיה
לזכור מה היו התמונות.

1019
00:47:40,030 --> 00:47:41,590
ואז יש ארבעה דברים מוחלט.

1020
00:47:41,590 --> 00:47:45,440
>> עכשיו הערימות גדלו, ש
זה דבר עיצוב מכוון כאן.

1021
00:47:45,440 --> 00:47:46,540
אבל מה עוד אני יכול לעשות?

1022
00:47:46,540 --> 00:47:49,080
אז בעצם יש לנו כאן
חבורה של ספרי בחינה בבית הספר ישנים.

1023
00:47:49,080 --> 00:47:51,240
נניח שחבורה של
שמות תלמידים על כאן.

1024
00:47:51,240 --> 00:47:52,570
הנה טבלת חשיש גדולה יותר.

1025
00:47:52,570 --> 00:47:54,867
במקום ארבעה דליים,
יש לי, נניח 26.

1026
00:47:54,867 --> 00:47:57,950
ואנחנו לא רוצים ללכת ללוות 26
דברים מ[ בחוץ? אננברג?], ולכן

1027
00:47:57,950 --> 00:48:00,289
הנה חמש שמייצגים
דרך ז 'ואם אני

1028
00:48:00,289 --> 00:48:03,580
לראות תלמיד ששמו מתחיל ב,
אני הולך לשים אותו או חידונה שם.

1029
00:48:03,580 --> 00:48:08,850
אם מישהו מתחיל עם C, שם,
זה-- למעשה, לא רוצה לעשות את זה.

1030
00:48:08,850 --> 00:48:10,060
B הולך כאן.

1031
00:48:10,060 --> 00:48:13,390
אז יש לי A ו- B ו- C. ו
עכשיו הנה תלמיד אחר.

1032
00:48:13,390 --> 00:48:16,212
אבל אם שולחן חשיש זה
מיושם עם מערך,

1033
00:48:16,212 --> 00:48:17,920
אני סוג של דפוק
בשלב זה, נכון?

1034
00:48:17,920 --> 00:48:19,510
אני סוג של צריך לשים איפשהו זה.

1035
00:48:19,510 --> 00:48:24,380
>> אז דרך יחידה שאני יכול לפתור את זה, כולו
נכון, הוא עסוק, B הוא עסוק, C הוא עסוק.

1036
00:48:24,380 --> 00:48:28,880
אני הולך לשים אותו בד אז ב
הראשון, יש לי גישה מיידית אקראית

1037
00:48:28,880 --> 00:48:31,064
לכל אחד מהדליים לתלמידים.

1038
00:48:31,064 --> 00:48:33,230
אבל עכשיו זה סוג של devolved
ליניארי משהו,

1039
00:48:33,230 --> 00:48:36,750
כי אם אני רוצה לחפש מישהו
השם שלהם מתחיל עם, אני בודק כאן.

1040
00:48:36,750 --> 00:48:38,854
אבל אם זה לא
סטודנט אני מחפש,

1041
00:48:38,854 --> 00:48:41,520
אני סוג של יש להתחיל לבדוק
הדליים, כי מה שעשיתי

1042
00:48:41,520 --> 00:48:44,530
היה סוג של ליניארי
לחקור את מבנה הנתונים.

1043
00:48:44,530 --> 00:48:47,710
דרך מטופשת לומר רק להסתכל
לפתיחה זמינה הראשונה,

1044
00:48:47,710 --> 00:48:51,850
ולשים כתכנית ב ', כביכול,
או D תכנית במקרה זה, הערך

1045
00:48:51,850 --> 00:48:53,340
במיקום שבמקום.

1046
00:48:53,340 --> 00:48:56,470
זה פשוט כל כך שאם יש לך
קיבלתי 26 מקומות ולא תלמידים

1047
00:48:56,470 --> 00:49:00,600
עם שם Q או Z, או משהו כזה
כי, לפחות אתה משתמש בחלל.

1048
00:49:00,600 --> 00:49:03,140
>> אבל כבר ראינו יותר
פתרונות חכמים כאן, נכון?

1049
00:49:03,140 --> 00:49:04,870
מה היית עושה במקום
אם יש לך התנגשות?

1050
00:49:04,870 --> 00:49:06,670
אם יש לי שני אנשים
שם, מה היית עושה

1051
00:49:06,670 --> 00:49:09,160
היה יותר חכם או יותר
פתרון אינטואיטיבי יותר מאשר רק

1052
00:49:09,160 --> 00:49:12,840
לשים בי D אמור להיות?

1053
00:49:12,840 --> 00:49:14,810
למה אני לא פשוט ללכת
[בחוץ? אננברג?],

1054
00:49:14,810 --> 00:49:19,960
כמו malloc, צומת אחר, לשים אותו
כאן, ולאחר מכן לשים את זה סטודנט כאן.

1055
00:49:19,960 --> 00:49:22,120
כך שאני בעצם יש לי
איזה מערך,

1056
00:49:22,120 --> 00:49:25,590
או אולי יותר באלגנטיות כמו שאנחנו
מתחיל לראות רשימה מקושרת.

1057
00:49:25,590 --> 00:49:29,520
>> וכך שולחן חשיש הוא מבנה
שיכול להיראות בדיוק כמו זה,

1058
00:49:29,520 --> 00:49:33,900
אבל יותר בחוכמה, אתה משהו שנקרא
שרשור נפרד, לפי טבלת חשיש

1059
00:49:33,900 --> 00:49:38,340
בפשטות הוא מערך, כל אחד מ
שאלמנטים הוא לא מספר,

1060
00:49:38,340 --> 00:49:40,470
היא עצמו רשימה מקושרת.

1061
00:49:40,470 --> 00:49:45,080
כך שאתה מקבל גישת סופר מהירה
מחליט היכן חשיש הערך שלך ל.

1062
00:49:45,080 --> 00:49:48,059
בדומה לדוגמא הכרטיסים,
אני עשיתי את החלטות סופר מהירות.

1063
00:49:48,059 --> 00:49:49,600
לבבות הולכים כאן, יהלומים הולכים כאן.

1064
00:49:49,600 --> 00:49:52,180
אותו דבר כאן, הולך כאן,
D הולך כאן, B הולך כאן.

1065
00:49:52,180 --> 00:49:55,740
מבט קופצים אז סופר מהיר, ואם
אתה במקרה נתקל במקרה

1066
00:49:55,740 --> 00:49:59,429
התנגשויות שבו אתה חייב, שתי
אנשים עם אותו שם, גם אז

1067
00:49:59,429 --> 00:50:00,970
אתה פשוט להתחיל מקשר אותם יחד.

1068
00:50:00,970 --> 00:50:03,900
ואולי לך לשמור אותם מסודרים
בסדר אלפביתי, אולי אתה לא.

1069
00:50:03,900 --> 00:50:05,900
אבל לפחות עכשיו יש לנו את הדינמיות.

1070
00:50:05,900 --> 00:50:10,250
אז מצד האחד יש לנו סופר מהיר
זמן קבוע, וסוג של זמן ליניארי

1071
00:50:10,250 --> 00:50:14,110
מעורב אם הרשימות הללו מקושרים
מתחיל לקבל קצת ארוך.

1072
00:50:14,110 --> 00:50:16,880
>> אז של מטופש מסוג זה,
שנות בדיחה חנונית לפני.

1073
00:50:16,880 --> 00:50:19,590
בגרזן-א-תון CS50,
כאשר תלמידים לבדוק ב,

1074
00:50:19,590 --> 00:50:22,040
כמה TF או CA בכל שנה
חושב שזה מצחיק לשים את

1075
00:50:22,040 --> 00:50:27,772
סימן כזה, שבו רק
המשמעות היא שאם השם שלך מתחיל ב,

1076
00:50:27,772 --> 00:50:28,870
ללכת בדרך זו.

1077
00:50:28,870 --> 00:50:31,110
אם השם שלך מתחיל
עם B, ללכת זה-- אישור,

1078
00:50:31,110 --> 00:50:33,290
זה מצחיק אולי מאוחר יותר בסמסטר.

1079
00:50:33,290 --> 00:50:36,420
אבל יש עוד
דרך לעשות זאת, מדי.

1080
00:50:36,420 --> 00:50:37,410
בואו נחזור לזה.

1081
00:50:37,410 --> 00:50:38,600
>> אז יש את המבנה הזה.

1082
00:50:38,600 --> 00:50:40,420
וזה אחרון שלנו
מבנה להיום,

1083
00:50:40,420 --> 00:50:42,400
וזה משהו שנקרא איירי.

1084
00:50:42,400 --> 00:50:47,140
T-R-אני-E, שמשום מה היא קצר
לאחזור, אבל זה נקרא איירי.

1085
00:50:47,140 --> 00:50:51,389
אז איירי היא עוד מעניינת
תערובת של הרבה מהרעיונות האלה.

1086
00:50:51,389 --> 00:50:52,930
זה עץ, שראינו בעבר.

1087
00:50:52,930 --> 00:50:54,180
זה לא עץ חיפוש בינארי.

1088
00:50:54,180 --> 00:50:58,410
זה עץ עם כל מספר של ילדים,
אבל כל אחד מהילדים באיירי

1089
00:50:58,410 --> 00:51:00,090
הוא מערך.

1090
00:51:00,090 --> 00:51:04,790
מערך של גודל, אומר, 26 או אולי 27
אם אתה רוצה לתמוך בשמות מקף

1091
00:51:04,790 --> 00:51:06,790
או גרשיים בשמות של אנשים.

1092
00:51:06,790 --> 00:51:08,280
>> ואז זה מבנה נתונים.

1093
00:51:08,280 --> 00:51:10,290
ואם אתה מסתכל מלמעלה
למטה, כמו אם

1094
00:51:10,290 --> 00:51:13,710
מסתכל על הצומת העליונה שם, M, הוא
מצביע על הדבר השמאלי ביותר שם,

1095
00:51:13,710 --> 00:51:17,665
שלאחר מכן, X, W, E, L, ל 'זה הוא
רק מבנה נתונים שבאופן שרירותי

1096
00:51:17,665 --> 00:51:19,120
הוא אחסון השמות של אנשים.

1097
00:51:19,120 --> 00:51:25,720
ומקסוול מאוחסן רק על ידי הבא
דרכו של מערך למערך למערך.

1098
00:51:25,720 --> 00:51:30,050
אבל מה מדהים על איירי היא
ש, ואילו רשימה מקושרת ואפילו

1099
00:51:30,050 --> 00:51:34,520
מערך, את הטוב ביותר שאי פעם קיבלו הוא
זמן ליניארי או לוגריתמי זמן מחפש

1100
00:51:34,520 --> 00:51:35,600
מישהו שם למעלה.

1101
00:51:35,600 --> 00:51:40,530
במבנה זה נתונים של איירי, אם
יש מבנה הנתונים שלי שם אחד בזה

1102
00:51:40,530 --> 00:51:43,720
ואני מחפש מקסוול, אני
הולך למצוא אותו די מהר.

1103
00:51:43,720 --> 00:51:47,910
אני רק מחפש M-X-W-E-L-L. אם
מבנה נתונים זה, לעומת זאת,

1104
00:51:47,910 --> 00:51:51,830
אם N הוא מיליון, אם יש
מיליון שמות במבנה נתונים זה,

1105
00:51:51,830 --> 00:51:57,100
מקסוול עדיין הולך להיות
לגילוי רק לאחר M-X-W-E-L-L

1106
00:51:57,100 --> 00:51:58,090
צעדים.

1107
00:51:58,090 --> 00:52:01,276
וצעדי David-- D-A-V-אני-D.

1108
00:52:01,276 --> 00:52:03,400
במילים אחרות, על ידי בנייה
מבנה נתונים זה

1109
00:52:03,400 --> 00:52:07,240
קיבלתי את כל מערכים אלה, אשר כולם
עצמם לתמוך בגישה אקראית,

1110
00:52:07,240 --> 00:52:11,090
אני יכול להתחיל לחפש את האנשים של
שם באמצעות כמות הזמן זה

1111
00:52:11,090 --> 00:52:14,340
לא פרופורציונאלי למספר
דברים במבנה נתונים,

1112
00:52:14,340 --> 00:52:16,330
כמו מיליון שמות קיימים.

1113
00:52:16,330 --> 00:52:20,135
משך זמן שלוקח לי למצוא
M-X-W-E-L-L במבנה נתונים זה

1114
00:52:20,135 --> 00:52:22,260
מידתי שלא
גודלו של מבנה הנתונים,

1115
00:52:22,260 --> 00:52:25,930
אבל לאורכו של השם.

1116
00:52:25,930 --> 00:52:28,440
ומציאותי
שמות שאנחנו מחפשים את

1117
00:52:28,440 --> 00:52:29,970
אף פעם לא הולכים להיות מטורף עוד.

1118
00:52:29,970 --> 00:52:32,600
אולי למישהו יש 10 דמות
שם, 20 שם דמות.

1119
00:52:32,600 --> 00:52:33,900
זה בהחלט סופי, נכון?

1120
00:52:33,900 --> 00:52:37,110
יש אדם על פני כדור הארץ ש
יש שם הארוך ביותר האפשריים,

1121
00:52:37,110 --> 00:52:39,920
אבל השם שהוא קבוע
אורך ערך, נכון?

1122
00:52:39,920 --> 00:52:41,980
זה לא ישתנה בכל מובן.

1123
00:52:41,980 --> 00:52:45,090
אז בדרך זו, יש לנו
השיג מבנה נתונים

1124
00:52:45,090 --> 00:52:47,800
שהוא להסתכל למעלה בזמן קבוע.

1125
00:52:47,800 --> 00:52:50,670
זה לוקח מספר הצעדים
בהתאם לאורכו של הקלט,

1126
00:52:50,670 --> 00:52:54,250
אבל לא את מספר שם
במבנה נתונים.

1127
00:52:54,250 --> 00:52:58,700
אז אם אנחנו להכפיל את מספר השמות
בשנה הבאה ממליארד לשני מיליארדים,

1128
00:52:58,700 --> 00:53:03,720
ממצא מקסוול הולך לקחת
בדיוק את אותו המספר של שבעה צעדים

1129
00:53:03,720 --> 00:53:04,650
כדי למצוא אותו.

1130
00:53:04,650 --> 00:53:08,810
וכך אנו נראים שהשגנו
הגביע הקדוש שלנו של זמן ריצה.

1131
00:53:08,810 --> 00:53:10,860
>> אז כמה הודעות מהירות.

1132
00:53:10,860 --> 00:53:11,850
חידון אפס מתקרב.

1133
00:53:11,850 --> 00:53:14,600
נוסף על כך באתר האינטרנט של הקורס
במשך כמה ימים הבאים.

1134
00:53:14,600 --> 00:53:17,120
היום השני של lecture-- זה חג
כאן בהרווארד ביום שני.

1135
00:53:17,120 --> 00:53:18,850
זה לא בניו הייבן,
כך אנחנו לוקחים הכיתה

1136
00:53:18,850 --> 00:53:20,310
לניו הייבן להרצאה ביום שני.

1137
00:53:20,310 --> 00:53:22,550
הכל יהיה מצולם
וישודר בשידור חי כרגיל,

1138
00:53:22,550 --> 00:53:24,900
אבל בואו לסיים היום
עם 30 בקליפ שני

1139
00:53:24,900 --> 00:53:26,910
"מחשבות עמוקות" בשם
על ידי ךייבן פארנהאם, ש

1140
00:53:26,910 --> 00:53:30,850
היה בהשראה בשנה שעברה עד יום שבת
"המחשבות עמוקות" של נייט לייב

1141
00:53:30,850 --> 00:53:35,700
על ידי ג'ק הנדי, ש
עכשיו צריך הגיוני.

1142
00:53:35,700 --> 00:53:38,810
>> סרט: ועכשיו, "דיפ
מחשבות "על ידי ךייבן פארנהאם.

1143
00:53:38,810 --> 00:53:42,100

1144
00:53:42,100 --> 00:53:42,870
שולחן חשיש.

1145
00:53:42,870 --> 00:53:45,940

1146
00:53:45,940 --> 00:53:47,660
>> 1 SPEAKER: בסדר, זהו זה לעת עתה.

1147
00:53:47,660 --> 00:53:48,805
נתראה בשבוע הבא.

1148
00:53:48,805 --> 00:53:55,380

1149
00:53:55,380 --> 00:53:56,680
>> דאג: כדי לראות אותו בפעולה.

1150
00:53:56,680 --> 00:53:58,304
אז בואו נסתכל על זה עכשיו.

1151
00:53:58,304 --> 00:53:59,890
אז הנה, יש לנו מערך לא ממוינת.

1152
00:53:59,890 --> 00:54:04,860
>> איאן: דאג, אתה יכול ללכת קדימה והפעלה מחדש
זה רק שני אחת, בבקשה.

1153
00:54:04,860 --> 00:54:08,562
בסדר, מצלמות מתגלגלות, כך
פעולה בכל פעם שאתה מוכן, דאג, בסדר?

1154
00:54:08,562 --> 00:54:11,020
דאג: בסדר, אז מה אנחנו
יש כאן הוא מערך לא ממוינת.

1155
00:54:11,020 --> 00:54:13,960
ואני כבר בצבע את כל האלמנטים
אדום כדי לציין שזה, למעשה,

1156
00:54:13,960 --> 00:54:14,460
לא ממוינת.

1157
00:54:14,460 --> 00:54:17,960
אז זוכר שהדבר הראשון שאנחנו עושים
הוא למיין את המחצית השמאלית של המערך.

1158
00:54:17,960 --> 00:54:20,630
אז למיין תקין
מחצית מהמערך.

1159
00:54:20,630 --> 00:54:22,830
ויא-דה, יא-דה, יא-דה,
אנחנו למזג אותם יחד.

1160
00:54:22,830 --> 00:54:24,520
ויש לנו מערך ממוין לחלוטין.

1161
00:54:24,520 --> 00:54:25,360
אז ככה למזג סוג עובד.

1162
00:54:25,360 --> 00:54:27,109
>> איאן: וואו, וואו, וואו,
לחתוך, לחתוך, לחתוך, לחתוך.

1163
00:54:27,109 --> 00:54:30,130
דאג, אתה פשוט לא יכול יה-דה, יא-דה,
יה-דה, דרכך סוג המיזוג.

1164
00:54:30,130 --> 00:54:31,970
>> דאג: אני רק עשיתי.

1165
00:54:31,970 --> 00:54:32,832
זה בסדר.

1166
00:54:32,832 --> 00:54:33,540
אנחנו טובים ללכת.

1167
00:54:33,540 --> 00:54:34,760
בואו פשוט לשמור מתגלגל.

1168
00:54:34,760 --> 00:54:35,380
אז בכל מקרה,

1169
00:54:35,380 --> 00:54:37,800
>> איאן: אתה צריך להסביר
זה באופן מלא יותר מזה.

1170
00:54:37,800 --> 00:54:39,999
זה פשוט לא מספיק.

1171
00:54:39,999 --> 00:54:41,790
דאג: איאן, אנחנו לא
צריך לחזור לאחד.

1172
00:54:41,790 --> 00:54:42,350
זה בסדר.

1173
00:54:42,350 --> 00:54:45,690
אז בכל מקרה, אם נמשיך עם merge--
איאן, אנחנו באמצע צילומים.

1174
00:54:45,690 --> 00:54:46,612
>> איאן: אני יודע.

1175
00:54:46,612 --> 00:54:49,320
ואנחנו פשוט לא יכולים יה-דה, יא-דה,
יה-דה, את כל התהליך.

1176
00:54:49,320 --> 00:54:52,200
אתה צריך להסביר איך
שני צדדים לקבל התמזגו יחד.

1177
00:54:52,200 --> 00:54:53,570
>> דאג: אבל יש לנו כבר
הסביר כיצד שני sides--

1178
00:54:53,570 --> 00:54:55,321
>> איאן: אתה כבר רק לראות
שלהם מערך מיזוג.

1179
00:54:55,321 --> 00:54:56,486
דאג: הם יודעים את התהליך.

1180
00:54:56,486 --> 00:54:57,172
הם בסדר גמור.

1181
00:54:57,172 --> 00:54:58,380
כבר דברנו על זה עשר פעמים.

1182
00:54:58,380 --> 00:55:00,330
>> איאן: אתה פשוט דילגת מעליו.

1183
00:55:00,330 --> 00:55:03,360
אנחנו חוזרים לאחד, אתה
אין באפשרותך יא-דה, יא-דה על זה.

1184
00:55:03,360 --> 00:55:05,480
בסדר, חזרה לאחד.

1185
00:55:05,480 --> 00:55:07,833
>> דאג: אני צריך לחזור
דרך כל השקופיות?

1186
00:55:07,833 --> 00:55:08,332
אלוהים.

1187
00:55:08,332 --> 00:55:11,008

1188
00:55:11,008 --> 00:55:13,004
זה כמו בפעם השישית, איאן.

1189
00:55:13,004 --> 00:55:13,940
זה בסדר.

1190
00:55:13,940 --> 00:55:15,200
>> איאן: בסדר.

1191
00:55:15,200 --> 00:55:16,590
אתה מוכן?

1192
00:55:16,590 --> 00:55:17,400
גדול.

1193
00:55:17,400 --> 00:55:18,950
פעולה.