1
00:00:00,000 --> 00:00:11,860

2
00:00:11,860 --> 00:00:13,120
>> 1 דובר: בסדר, אז אנחנו בחזרה.

3
00:00:13,120 --> 00:00:14,480
ברוכים הבאים לCS50.

4
00:00:14,480 --> 00:00:16,510
זהו סופו של שבוע שבע.

5
00:00:16,510 --> 00:00:20,200
אז זוכר שהפעם האחרונה, התחלנו
מסתכל על מעט יותר מתוחכם

6
00:00:20,200 --> 00:00:21,100
מבני נתונים.

7
00:00:21,100 --> 00:00:25,110
מאז ועד עכשיו, כל מה שהיו לנו באמת
עומדים לרשותנו היה זה, מערך.

8
00:00:25,110 --> 00:00:29,340
>> אבל לפני שאנחנו זורקים את המערך כלא
כל מה שהמעניין, שאכן אותו

9
00:00:29,340 --> 00:00:33,570
בעצם, מה הם כמה
פלוסים של נתונים פשוטים זו

10
00:00:33,570 --> 00:00:34,560
מבנה עד כה?

11
00:00:34,560 --> 00:00:36,110
מה זה טוב?

12
00:00:36,110 --> 00:00:39,450
עד כה כפי שראינו?

13
00:00:39,450 --> 00:00:42,540
מה יש לך?

14
00:00:42,540 --> 00:00:44,028
שום דבר.

15
00:00:44,028 --> 00:00:45,020
>> תלמיד: [לא ברור].

16
00:00:45,020 --> 00:00:45,395
>> רמקול 1: מה זה?

17
00:00:45,395 --> 00:00:46,410
>> תלמיד: [לא ברור].

18
00:00:46,410 --> 00:00:47,000
>> רמקול 1: גודל קבוע.

19
00:00:47,000 --> 00:00:51,260
בסדר, אז למה הוא גודל קבוע אם כי טוב?

20
00:00:51,260 --> 00:00:53,180
>> תלמיד: [לא ברור].

21
00:00:53,180 --> 00:00:56,240
>> 1 רמקול: אוקיי, אז זה יעיל ב
המובן שאתה יכול להקצות

22
00:00:56,240 --> 00:01:00,070
סכום קבוע של החלל, אשר בתקווה
בדיוק באותה מידה

23
00:01:00,070 --> 00:01:01,180
שטח כפי שאתה רוצה.

24
00:01:01,180 --> 00:01:02,720
כך שבהחלט יכול להיות יתרון.

25
00:01:02,720 --> 00:01:06,530
>> מה צד אחר של את מערך?

26
00:01:06,530 --> 00:01:07,610
כן?

27
00:01:07,610 --> 00:01:08,750
>> תלמיד: [לא ברור].

28
00:01:08,750 --> 00:01:09,550
>> 1 רמקול: כל - הסליחה?

29
00:01:09,550 --> 00:01:11,270
>> תלמיד: [לא ברור].

30
00:01:11,270 --> 00:01:13,620
>> רמקול 1: כל התיבות בזיכרון
או זה לצד זה.

31
00:01:13,620 --> 00:01:15,220
וזה מועיל - למה?

32
00:01:15,220 --> 00:01:15,970
זה לגמרי נכון.

33
00:01:15,970 --> 00:01:18,611
אבל איך אנחנו יכולים לנצל את האמת ש?

34
00:01:18,611 --> 00:01:21,500
>> תלמיד: [לא ברור].

35
00:01:21,500 --> 00:01:24,490
>> רמקול 1: בדיוק, אנחנו יכולים לעקוב אחר
שבו הכל הוא רק על ידי ידיעה

36
00:01:24,490 --> 00:01:28,560
כתובת אחת, כלומר את הכתובת של
הבית הראשון של נתח זה של זיכרון.

37
00:01:28,560 --> 00:01:30,420
או במקרה של המחרוזת,
הכתובת של הראשון

38
00:01:30,420 --> 00:01:31,460
char במחרוזת ש.

39
00:01:31,460 --> 00:01:33,330
ומשם, אנחנו יכולים למצוא
סוף המחרוזת.

40
00:01:33,330 --> 00:01:35,710
אנחנו יכולים למצוא את המרכיב השני,
אלמנט שלישי, וכן הלאה.

41
00:01:35,710 --> 00:01:38,740
>> וכך מתאר את הדרך המפוארת של ש
תכונה היא שנותנים לנו מערכים

42
00:01:38,740 --> 00:01:40,020
גישה אקראית.

43
00:01:40,020 --> 00:01:44,330
רק על ידי שימוש בסוגריים מרובעים
סימון ומספר, אתה יכול לקפוץ ל

44
00:01:44,330 --> 00:01:48,070
אלמנט מסוים במערך
בזמן קבוע, הגדול O

45
00:01:48,070 --> 00:01:49,810
של אחד, אם אפשר לומר כך.

46
00:01:49,810 --> 00:01:51,080
>> אבל היו כמה חסרונות.

47
00:01:51,080 --> 00:01:53,110
מה לא לעשות מערך בקלות רבה?

48
00:01:53,110 --> 00:01:55,810

49
00:01:55,810 --> 00:01:57,170
מה זה לא טוב?

50
00:01:57,170 --> 00:01:58,810
>> תלמיד: [לא ברור].

51
00:01:58,810 --> 00:01:59,860
>> רמקול 1: מה זה?

52
00:01:59,860 --> 00:02:00,530
>> תלמיד: [לא ברור].

53
00:02:00,530 --> 00:02:01,460
>> רמקול 1: הרחבת בגודלו.

54
00:02:01,460 --> 00:02:04,800
אז החסרונות של המערך הם
בדיוק ההפך ממה

55
00:02:04,800 --> 00:02:05,540
upsides הן.

56
00:02:05,540 --> 00:02:07,610
אז אחד החסרונות הוא
שזה גודל קבוע.

57
00:02:07,610 --> 00:02:09,400
אז אתה לא באמת יכול לגדל אותו.

58
00:02:09,400 --> 00:02:13,510
באפשרותך להקצות מחדש את נתח גדול יותר של
זיכרון, ולאחר מכן להעביר את האלמנטים הישנים

59
00:02:13,510 --> 00:02:14,460
למערך החדש.

60
00:02:14,460 --> 00:02:18,060
ולאחר מכן את המערך הישן ללא תשלום, עבור
למשל, על ידי שימוש בmalloc או דומה

61
00:02:18,060 --> 00:02:21,180
פונקציה שנקראת realloc, אשר
reallocates זיכרון.

62
00:02:21,180 --> 00:02:25,490
>> Realloc, כמו בצד, מנסה לתת לך
זיכרון זה לצד המערך

63
00:02:25,490 --> 00:02:26,610
כי כבר יש לך.

64
00:02:26,610 --> 00:02:28,740
אבל זה יכול להזיז דברים
סביב לגמרי.

65
00:02:28,740 --> 00:02:30,710
אבל בקיצור, זה יקר, נכון?

66
00:02:30,710 --> 00:02:33,440
כי אם יש לך נתח של זיכרון
גודל זה, אבל אתה באמת רוצה אחד

67
00:02:33,440 --> 00:02:36,710
בגודל זה, ואתה רוצה לשמור על
את האלמנטים המקוריים, יש לך

68
00:02:36,710 --> 00:02:40,510
בערך תהליך העתקת זמן ליניארי
זה צריך לקרות מ

69
00:02:40,510 --> 00:02:41,900
מערך ישן לחדש.

70
00:02:41,900 --> 00:02:44,630
והמציאות היא מבקשת הפעלה
מערכת שוב ושוב ו

71
00:02:44,630 --> 00:02:48,340
שוב לגושים גדולים של זיכרון יכול להתחיל
יעלה לך קצת זמן גם כן.

72
00:02:48,340 --> 00:02:52,250
אז זה גם ברכה וקללה ב
להסוות את העובדה שמערכים אלה

73
00:02:52,250 --> 00:02:53,860
הם בגודל קבוע.

74
00:02:53,860 --> 00:02:56,790
אבל אם אנחנו מציגים במקום משהו
כמו זה, שבו אנו נקראים מקושר

75
00:02:56,790 --> 00:03:00,580
רשימה, אנחנו מקבלים כמה וupsides
כמה חסרונות גם כאן.

76
00:03:00,580 --> 00:03:05,780
>> אז רשימה מקושרת היא פשוט נתונים
מבנה מורכב מstructs C בזה

77
00:03:05,780 --> 00:03:09,850
מקרה, שבו struct, כזכור, הוא רק
מיכל לאחד או יותר ספציפית

78
00:03:09,850 --> 00:03:11,100
סוגים של משתנים.

79
00:03:11,100 --> 00:03:16,110
במקרה זה, מה שעושה את סוגי הנתונים
להיראות בתוך struct כי

80
00:03:16,110 --> 00:03:17,600
הפעם האחרונה שנקראות צומת?

81
00:03:17,600 --> 00:03:19,380
כל אחד ממלבנים אלו הוא צומת.

82
00:03:19,380 --> 00:03:22,660
וכל אחד מהמלבנים הקטנים יותר
בתוכו הוא סוג הנתונים.

83
00:03:22,660 --> 00:03:25,300
מה סוגים שאנו אומרים
הם היו ביום שני?

84
00:03:25,300 --> 00:03:26,478
כן?

85
00:03:26,478 --> 00:03:27,870
>> תלמיד: [לא ברור].

86
00:03:27,870 --> 00:03:30,721
>> 1 רמקול: משתנה ומצביע, או
ליתר דיוק, int, עבור n,

87
00:03:30,721 --> 00:03:32,180
ומצביע בתחתית.

88
00:03:32,180 --> 00:03:35,360
שני אלה יקרו להיות 32 סיביות, ב
לפחות במחשב כמו זה CS50

89
00:03:35,360 --> 00:03:37,980
מכשיר, ולכן הם
נמשך במידה שווה בגודלו.

90
00:03:37,980 --> 00:03:42,260
>> אז מה משתמש במצביע
אם כי ככל הנראה?

91
00:03:42,260 --> 00:03:47,690
למה להוסיף החץ הזה עכשיו כאשר מערכים היו
כל כך נחמד ונקי ופשוט?

92
00:03:47,690 --> 00:03:50,460
מה שעושה למצביע
לנו בכל אחד מצומת הללו?

93
00:03:50,460 --> 00:03:52,160
>> תלמיד: [לא ברור].

94
00:03:52,160 --> 00:03:52,465
>> רמקול 1: בדיוק.

95
00:03:52,465 --> 00:03:54,120
זה אומר לך איפה
הבא הוא.

96
00:03:54,120 --> 00:03:57,350
אז אני סוג של שימוש באנלוגיה של
שימוש בחוט כדי למיין של

97
00:03:57,350 --> 00:03:59,180
חוט צמתים הללו יחד.

98
00:03:59,180 --> 00:04:01,760
וזה בדיוק מה שאנחנו עושים עם
מצביעים, כי כל אחד מאלה

99
00:04:01,760 --> 00:04:06,360
נתחי הזיכרון עשויים או לא עשויים להיות
רציף, גב אל גב אל גב

100
00:04:06,360 --> 00:04:09,500
חלק פנימי של זיכרון RAM, כי כל פעם שאתה
קורא malloc אומר, תן לי מספיק

101
00:04:09,500 --> 00:04:12,510
בתים עבור צומת חדש, זה עלול
להיות כאן או שזה יכול להיות כאן.

102
00:04:12,510 --> 00:04:13,120
זה יכול להיות כאן.

103
00:04:13,120 --> 00:04:13,730
זה יכול להיות כאן.

104
00:04:13,730 --> 00:04:14,640
אתה פשוט לא יודע.

105
00:04:14,640 --> 00:04:17,880
>> אבל שימוש במצביעים בכתובות של
צמתים האלה, אתה יכול לתפור אותם

106
00:04:17,880 --> 00:04:22,370
יחד בצורה שנראית מבחינה ויזואלית
כמו רשימה גם אם הדברים האלה הם

107
00:04:22,370 --> 00:04:26,770
כל פרוש לאורך אחד או שלך
שתיים שלך או ארבע ג'יגה בייט של זיכרון RAM שלך

108
00:04:26,770 --> 00:04:28,760
חלק פנימי של המחשב שלך.

109
00:04:28,760 --> 00:04:33,230
>> אז החסרון, ואז,
רשימה מקושרת היא מה?

110
00:04:33,230 --> 00:04:34,670
מה מחיר שאנחנו
כנראה משלם?

111
00:04:34,670 --> 00:04:36,010
>> תלמיד: [לא ברור].

112
00:04:36,010 --> 00:04:36,920
>> רמקול 1: יותר חלל, נכון?

113
00:04:36,920 --> 00:04:39,340
יש לנו, במקרה זה, הכפיל את הכמות
של שטח, כי אנחנו כבר הלכנו

114
00:04:39,340 --> 00:04:43,500
מ32 סיביות לכל צומת לכל אחת
int, אז עכשיו 64 סיביות בגלל שיש לנו

115
00:04:43,500 --> 00:04:45,050
לשמור סביב מצביע גם כן.

116
00:04:45,050 --> 00:04:48,860
אתה מקבל יותר יעיל אם struct שלך
גדול יותר מדבר הפשוט הזה.

117
00:04:48,860 --> 00:04:52,020
אם יש לך בעצם תלמיד בתוך
מהם הוא בני זוג של מחרוזות ל

118
00:04:52,020 --> 00:04:55,430
שם ובית, אולי מספר תעודת זהות,
אולי כמה תחומים אחרים לגמרי.

119
00:04:55,430 --> 00:04:59,000
>> אז אם יש לך מספיק struct גדול,
אז אולי את העלות של המצביע היא

120
00:04:59,000 --> 00:05:00,010
לא כזה ביג דיל.

121
00:05:00,010 --> 00:05:03,570
זה קצת של מקרה שבפינה
אנחנו אחסון פרימיטיבי כזה פשוט

122
00:05:03,570 --> 00:05:04,760
בתוך הרשימה המקושרת.

123
00:05:04,760 --> 00:05:05,790
אבל הנקודה היא אותו הדבר.

124
00:05:05,790 --> 00:05:08,230
אתה בהחלט אתה מבלה יותר
זיכרון, אבל אתה מקבל

125
00:05:08,230 --> 00:05:08,990
גמישות.

126
00:05:08,990 --> 00:05:12,280
כי עכשיו אם אני רוצה להוסיף אלמנט
בתחילת רשימה זו,

127
00:05:12,280 --> 00:05:14,340
אני חייב להקצות צומת חדשה.

128
00:05:14,340 --> 00:05:17,180
ויש לי רק כדי לעדכן אותם
חיצים איכשהו פשוט מרגש

129
00:05:17,180 --> 00:05:17,980
כמה עצות מסביב.

130
00:05:17,980 --> 00:05:20,580
>> אם אני רוצה להכניס משהו לתוך
אמצע הרשימה, אין לי ל

131
00:05:20,580 --> 00:05:24,410
לדחוף את כולם הצידה כמו שעשינו ב
העבר של שבועות עם המתנדבים שלנו ש

132
00:05:24,410 --> 00:05:25,700
מיוצג מערך.

133
00:05:25,700 --> 00:05:29,470
אני רק יכול להקצות צומת חדשה ו
אז פשוט להצביע על החצים ב

134
00:05:29,470 --> 00:05:32,290
כיוונים שונים כי זה לא
יש להישאר בבפועל

135
00:05:32,290 --> 00:05:35,670
זכרון קו אמיתי כמו שאני נמשך
אותו כאן על המסך.

136
00:05:35,670 --> 00:05:38,400
>> ואז לבסוף, אם ברצונך להוסיף
משהו בסוף הרשימה, זה

137
00:05:38,400 --> 00:05:39,210
אפילו יותר קל.

138
00:05:39,210 --> 00:05:43,320
זה סוג של סימון שרירותי,
אבל של 34 מצביע, ינחש.

139
00:05:43,320 --> 00:05:46,710
מהו הערך של המצביע שלה ביותר
מיין סביר נמשך כמו ישן

140
00:05:46,710 --> 00:05:47,700
אנטנה בבית הספר שם?

141
00:05:47,700 --> 00:05:48,920
>> תלמיד: [לא ברור].

142
00:05:48,920 --> 00:05:49,900
>> רמקול 1: זה כנראה ריק.

143
00:05:49,900 --> 00:05:52,710
ואכן זה של מחבר אחד
ייצוג של null.

144
00:05:52,710 --> 00:05:56,310
וזה בגלל שאתה ריק לחלוטין
צריך לדעת איפה סוף מקושר

145
00:05:56,310 --> 00:06:00,050
רשימה היא, שמא אתה הבא ולשמור
לאחר ובעקבות חצים אלה

146
00:06:00,050 --> 00:06:01,170
לאיזה ערך זבל.

147
00:06:01,170 --> 00:06:06,230
אז null יהיה לסמן שאין
צמתים נוספים לזכותו של מספר 34,

148
00:06:06,230 --> 00:06:07,200
במקרה זה.

149
00:06:07,200 --> 00:06:10,270
>> אז אנחנו מציעים שיכולים ליישם
הצומת הזה בקוד.

150
00:06:10,270 --> 00:06:12,130
ואנחנו לא ראינו סוג זה
תחביר של לפני.

151
00:06:12,130 --> 00:06:15,090
Typedef פשוט מגדיר סוג חדש עבור
אותנו, נותן לנו מילה נרדפת כמו

152
00:06:15,090 --> 00:06:17,100
מחרוזת הייתה לדמות *.

153
00:06:17,100 --> 00:06:21,030
במקרה זה, זה הולך לתת לנו
סימון מקוצר, כך שצומת struct

154
00:06:21,030 --> 00:06:24,010
יכול במקום פשוט להיות כפי שנכתב
צומת, שהוא הרבה יותר נקי.

155
00:06:24,010 --> 00:06:25,360
זה הרבה פחות מפורט.

156
00:06:25,360 --> 00:06:30,080
>> בתוך צומת הוא כנראה int
n בשם, ולאחר מכן struct צומת *

157
00:06:30,080 --> 00:06:34,670
מה שאומר בדיוק את מה שרצינו
חיצים למתכוונים, מצביע למשנהו

158
00:06:34,670 --> 00:06:36,940
צומת של בדיוק את אותו סוג נתונים.

159
00:06:36,940 --> 00:06:40,300
ואני מציע שאפשר ליישם
פונקציית חיפוש כמו זה, שבי

160
00:06:40,300 --> 00:06:41,890
המבט הראשון אולי נראה
מתחם קטן.

161
00:06:41,890 --> 00:06:43,330
אבל בואו לראות בהקשר זה.

162
00:06:43,330 --> 00:06:45,480
>> תן לי לעבור למכשיר כאן.

163
00:06:45,480 --> 00:06:48,460
תן לי לפתוח את קובץ בשם
רשימת אפס נקודת שעות.

164
00:06:48,460 --> 00:06:53,950
ושמכיל את ההגדרה היחידה שאנחנו
ראיתי לפני רגע רק לנתונים אלה

165
00:06:53,950 --> 00:06:55,390
סוג הנקרא צומת.

166
00:06:55,390 --> 00:06:57,350
אז יש לנו לשים את זה בקובץ שעות נקודה.

167
00:06:57,350 --> 00:07:01,430
>> וכמאמר מוסגר, למרות שזה
תכנית שאתה עומד לראות היא

168
00:07:01,430 --> 00:07:05,410
לא כל שמורכב, זה אכן
כינוס בעת כתיבת תכנית

169
00:07:05,410 --> 00:07:10,270
לשים את הדברים כמו סוגי נתונים, כדי למשוך
קבועים לפעמים, בתוך שלך

170
00:07:10,270 --> 00:07:13,210
קובץ כותרת ולא בהכרח ב
קובץ C שלך, ובוודאי כש

171
00:07:13,210 --> 00:07:17,370
תוכניות לקבל גדולות יותר ויותר, כך ש
אתה יודע איפה לחפש הן עבור

172
00:07:17,370 --> 00:07:20,840
תיעוד במקרים מסוימים, או
ליסודות כאלה,

173
00:07:20,840 --> 00:07:22,360
הגדרה של סוג כלשהו.

174
00:07:22,360 --> 00:07:25,680
>> אם אני עכשיו פותח את רשימת אפס נקודה
ג, שימו לב כמה דברים.

175
00:07:25,680 --> 00:07:29,090
הוא כולל כמה קבצי כותרת, רוב
מהם שראינו בעבר.

176
00:07:29,090 --> 00:07:31,980
הוא כולל קובץ הכותרת משלו.

177
00:07:31,980 --> 00:07:35,200
>> וכמאמר מוסגר, למה זה כפול
ציטוטים כאן, בניגוד לזווית

178
00:07:35,200 --> 00:07:38,340
סוגריים על הקו
אני כבר הדגיש שם?

179
00:07:38,340 --> 00:07:39,180
>> תלמיד: [לא ברור].

180
00:07:39,180 --> 00:07:40,460
>> 1 רמקול: כן אז זה קובץ מקומי.

181
00:07:40,460 --> 00:07:44,300
אז אם זה קובץ מקומי שלך כאן
בקו 15, למשל, אתה משתמש

182
00:07:44,300 --> 00:07:46,570
את המרכאות הכפולות במקום
מסוגר הזווית.

183
00:07:46,570 --> 00:07:48,270
>> עכשיו זה די מעניין.

184
00:07:48,270 --> 00:07:51,830
שימו לב, כי אני כבר הכריז גלובלי
משתנה בתכנית זו בקו 18

185
00:07:51,830 --> 00:07:55,910
שם הראשון, את הרעיון שזה הוא
הולך להיות מצביע הראשון

186
00:07:55,910 --> 00:07:59,190
צומת ברשימה המקושרת שלי, ויש לי
אותחל לזה null, כי יש לי

187
00:07:59,190 --> 00:08:02,310
לא הוקצה כל בפועל
בלוטות עדיין.

188
00:08:02,310 --> 00:08:07,570
>> אז זה מייצג, ציורי, מה שאנחנו
ראה לפני רגע בתמונה כמו

189
00:08:07,570 --> 00:08:10,090
מצביע שעל הרבה
עזב את היד בצד.

190
00:08:10,090 --> 00:08:12,260
אז עכשיו, מצביע ה
אין חץ.

191
00:08:12,260 --> 00:08:14,590
זה במקום הוא פשוט ריק.

192
00:08:14,590 --> 00:08:17,880
אבל זה מייצג את מה שתהיה
כתובת של הפועל הראשון

193
00:08:17,880 --> 00:08:19,480
צומת ברשימה זו.

194
00:08:19,480 --> 00:08:22,120
אז שהתקנתי אותו הוא גלובלי
כי, כפי שתראה, כל זה

195
00:08:22,120 --> 00:08:25,310
תכנית אינה בחיים היא ליישם
רשימה מקושרת עבורי.

196
00:08:25,310 --> 00:08:27,050
>> עכשיו יש לי כמה אבות טיפוס כאן.

197
00:08:27,050 --> 00:08:31,190
החלטתי ליישם תכונות כמו
מחיקה, הוספה, חיפוש ו

198
00:08:31,190 --> 00:08:31,740
חציית -

199
00:08:31,740 --> 00:08:35,210
ההליכה פשוט להיות האחרונה על פני
רשימה, מדפיס את מרכיביו.

200
00:08:35,210 --> 00:08:36,750
ועכשיו הנה שגרה העיקרית שלי.

201
00:08:36,750 --> 00:08:39,890
ואנחנו לא מבלים יותר מדי זמן על
אלה, מאחר שזו סוג של, בתקווה

202
00:08:39,890 --> 00:08:41,780
כובע ישן עד עכשיו.

203
00:08:41,780 --> 00:08:45,370
>> אני הולך לבצע את הפעולות הבאות,
בזמן שהמשתמש משתף פעולה.

204
00:08:45,370 --> 00:08:47,300
אז אחד, אני הולך להדפיס
מתוך תפריט זה.

205
00:08:47,300 --> 00:08:49,420
ואני כבר מעוצב אותו כ
נקי ככל שיכולתי.

206
00:08:49,420 --> 00:08:52,240
אם המשתמש מקליד באחד, שפירושו
הם רוצים למחוק משהו.

207
00:08:52,240 --> 00:08:54,560
אם המשתמש מקליד לשניים, שפירושו
הם רוצים להוסיף משהו.

208
00:08:54,560 --> 00:08:55,930
וכן הלאה.

209
00:08:55,930 --> 00:08:58,270
אני הולך אז כדי להנחות
אז לפקודה.

210
00:08:58,270 --> 00:08:59,300
ואז אני הולך להשתמש GetInt.

211
00:08:59,300 --> 00:09:02,790
>> אז זה ממש פשוט menuing
ממשק שבו אתה רק צריך להקליד

212
00:09:02,790 --> 00:09:05,270
מיפוי מספר טלפון לאחד
של פקודות אלה.

213
00:09:05,270 --> 00:09:08,730
ועכשיו יש לי מתג נקי נחמד
הצהרה שהולכת לעבור על

214
00:09:08,730 --> 00:09:10,090
כל מה שמשתמש הקליד פנימה

215
00:09:10,090 --> 00:09:12,180
ואם הם הקלידו אחד, אני
קורא למחוק ולשבור.

216
00:09:12,180 --> 00:09:14,380
אם הם הקלידו שניים, אני יהיה
קורא להוסיף ולשבור.

217
00:09:14,380 --> 00:09:16,490
>> ועכשיו שם לב שמתו אותי בכל
אלה על אותו הקו.

218
00:09:16,490 --> 00:09:18,360
זוהי רק החלטה סגנונית.

219
00:09:18,360 --> 00:09:20,210
בדרך כלל שראינו משהו
כמו זה.

220
00:09:20,210 --> 00:09:23,260
אבל אני פשוט החלטתי, בכנות, התכנית שלי
נראה קריא יותר משום

221
00:09:23,260 --> 00:09:25,980
זה היה רק ​​ארבעה מקרים ל
פשוט מוסיף אותו ככה.

222
00:09:25,980 --> 00:09:28,360
שימוש לגיטימי לחלוטין בסגנון.

223
00:09:28,360 --> 00:09:31,480
ואני הולך לעשות את זה כל עוד
משתמש לא הקליד אפס, שבו אני

224
00:09:31,480 --> 00:09:33,910
החליט לא אומר שהם רוצים להפסיק לעשן.

225
00:09:33,910 --> 00:09:36,630
>> אז עכשיו שים לב למה שאני
הולך לעשות כאן.

226
00:09:36,630 --> 00:09:38,650
אני הולך לשחרר את הרשימה ככל הנראה.

227
00:09:38,650 --> 00:09:40,230
אבל עוד על כך ברגע.

228
00:09:40,230 --> 00:09:41,640
בואו ראשון להפעיל תכנית זו.

229
00:09:41,640 --> 00:09:45,250
אז תן לי לעשות את מסוף גדול יותר
חלון, נקודת רשימת לוכסן 0.

230
00:09:45,250 --> 00:09:49,510
אני הולך קדימה, ולהכניס על ידי
שתיים הקלדה, כמו מספר 50, ועכשיו

231
00:09:49,510 --> 00:09:51,590
תוכל לראות את הרשימה היא עכשיו 50.

232
00:09:51,590 --> 00:09:53,380
והטקסט שלי פשוט לגלול קצת.

233
00:09:53,380 --> 00:09:55,940
אז עכשיו שם לב הרשימה מכילה
מספר 50.

234
00:09:55,940 --> 00:09:58,220
>> בואו ניתן להוסיף עוד על ידי לקיחת שתיים.

235
00:09:58,220 --> 00:10:01,630
בואו להקליד את המספר כמו אחד.

236
00:10:01,630 --> 00:10:03,940
רשימה היא כיום אחד, ואחריו 50.

237
00:10:03,940 --> 00:10:06,020
אז זה רק ייצוג טקסטואלי
מהרשימה.

238
00:10:06,020 --> 00:10:10,550
ובואו תוסיף עוד אחד כמו מספר
מספר 42, שהוא תקווה

239
00:10:10,550 --> 00:10:14,620
הולך בסופו של דבר באמצע, כי
תכנית זו במינים מסוימים זה

240
00:10:14,620 --> 00:10:16,320
אלמנטים כמו שהוא מוסיף אותם.

241
00:10:16,320 --> 00:10:17,220
אז יש לנו את זה.

242
00:10:17,220 --> 00:10:20,730
תכנית פשוטה שיכולה סופר
בהחלט השתמשתי במערך, אבל אני

243
00:10:20,730 --> 00:10:23,280
יקרה לך להיות באמצעות רשימה מקושרת
רק אז אני יכול דינמי

244
00:10:23,280 --> 00:10:24,610
לגדול ולכווץ אותו.

245
00:10:24,610 --> 00:10:28,470
>> אז בואו נסתכל לחיפוש, אם אני
להריץ את הפקודה שלוש, אני רוצה לחפש

246
00:10:28,470 --> 00:10:31,040
, למשל, את המספר 43.

247
00:10:31,040 --> 00:10:34,190
ושום דבר לא נמצא, ככל הנראה,
בגלל שחזרתי ללא תגובה.

248
00:10:34,190 --> 00:10:35,010
אז בואו נעשה את זה שוב.

249
00:10:35,010 --> 00:10:35,690
חיפוש.

250
00:10:35,690 --> 00:10:39,520
בואו לחפש 50, או ליתר דיוק לחפש
ל42, שבה יש נחמד

251
00:10:39,520 --> 00:10:40,850
משמעות עדינה קטנה.

252
00:10:40,850 --> 00:10:42,610
ואני מצאתי את משמעות חיים שם.

253
00:10:42,610 --> 00:10:44,990
מספר 42, אם אתה לא יודע
התייחסות, Google אותו.

254
00:10:44,990 --> 00:10:45,350
בסדר.

255
00:10:45,350 --> 00:10:47,130
אז מה עשה תכנית זו עבורי?

256
00:10:47,130 --> 00:10:50,660
זה פשוט אפשר לי להוסיף ובכך
וחיפוש הרבה לאלמנטים.

257
00:10:50,660 --> 00:10:53,650
>> בואו מהר קדימה, ולאחר מכן, כדי
פונקציה שהציצו ברשימה

258
00:10:53,650 --> 00:10:55,360
ביום שני כטיזר.

259
00:10:55,360 --> 00:10:59,620
אז פונקציה זו, אני טוען, לחיפושים
אלמנט ברשימה על ידי ראשונה

260
00:10:59,620 --> 00:11:03,830
אחד, להציג הודעה למשתמש ולאחר מכן מתקשר
GetInt לקבל int בפועל

261
00:11:03,830 --> 00:11:05,060
שברצונך לחפש.

262
00:11:05,060 --> 00:11:06,460
>> ואז שם לב זה.

263
00:11:06,460 --> 00:11:10,690
אני הולך ליצור משתנה זמני
בקו 188 בשם מצביע -

264
00:11:10,690 --> 00:11:11,270
PTR -

265
00:11:11,270 --> 00:11:12,440
יכל לקרוא לזה שום דבר.

266
00:11:12,440 --> 00:11:16,140
וזה מצביע לצומת
כי אמרתי * צומת שם.

267
00:11:16,140 --> 00:11:19,900
ואני מאתחל אותו להיות שווה ל
ראשון, כך שיש לי ביעילות שלי

268
00:11:19,900 --> 00:11:22,860
אצבע, אם אפשר לומר כך, על מאוד
המרכיב ראשון ברשימה.

269
00:11:22,860 --> 00:11:27,460
אז אם יד הימין שלי כאן היא שאני PTR
מצביע על אותו הדבר שראשון

270
00:11:27,460 --> 00:11:28,670
הוא הצביע על.

271
00:11:28,670 --> 00:11:31,430
>> אז עכשיו שוב בקוד,
מה קורה בהמשך -

272
00:11:31,430 --> 00:11:35,070
זו היא הפרדיגמה נפוצה כאשר iterating
מעל מבנה דמוי

273
00:11:35,070 --> 00:11:35,970
רשימה מקושרת.

274
00:11:35,970 --> 00:11:40,410
אני הולך לבצע את הפעולות הבאות בעת
המצביע אינו שווה ל null אז בזמן

275
00:11:40,410 --> 00:11:47,530
האצבע שלי לא מצביעה על איזה null
ערך, אם מצביע החץ n שווה n.

276
00:11:47,530 --> 00:11:52,290
אנחנו נשים לב ראשון שn הוא מה
משתמש הקליד בGetInts לכל שיחה כאן.

277
00:11:52,290 --> 00:11:54,280
>> ומצביע החץ n מה זה אומר?

278
00:11:54,280 --> 00:11:59,020
ובכן, אם אנחנו חוזרים לתמונה כאן,
אם יש לי את האצבע והצביעה על

279
00:11:59,020 --> 00:12:02,960
שהצומת ראשונה המכילה תשע,
חץ בעצם אומר ללכת כי

280
00:12:02,960 --> 00:12:08,860
צומת ולתפוס את הערך במיקום n,
במקרה זה, שדה נתונים הנקרא n.

281
00:12:08,860 --> 00:12:14,120
>> במאמר מוסגר - וראינו את הזוג הזה
לפני מספר שבועות, כאשר מישהו שאל -

282
00:12:14,120 --> 00:12:18,840
תחביר זה חדש, אבל זה לא עושה
לתת לנו כוחות שאנחנו

283
00:12:18,840 --> 00:12:20,040
לא כבר יש.

284
00:12:20,040 --> 00:12:25,325
מה היה המשפט הזה שווה הערך לשימוש
נקודת סימון וכוכב זוג

285
00:12:25,325 --> 00:12:29,490
לפני שבועות כשקלפנו
שכבה זו קצת מוקדם מדי?

286
00:12:29,490 --> 00:12:31,780
>> תלמיד: [לא ברור].

287
00:12:31,780 --> 00:12:38,880
>> רמקול 1: בדיוק, זה היה כוכב, ו
אז זה היה כוכב dot n, עם

288
00:12:38,880 --> 00:12:41,930
סוגריים כאן, מה שנראה,
בכנות, אני חושב שהרבה

289
00:12:41,930 --> 00:12:43,320
יותר מסתורי לקריאה.

290
00:12:43,320 --> 00:12:46,270
אבל מצביע כוכב, כמו תמיד,
אמצעים ללכת לשם.

291
00:12:46,270 --> 00:12:49,090
וברגע שאתה שם, מה שנתונים
תחום אתה רוצה לגשת?

292
00:12:49,090 --> 00:12:52,730
גם אתה משתמש בסימון הנקודה כדי לגשת
שדה נתוני structs, ואני

293
00:12:52,730 --> 00:12:54,140
במיוחד רוצה n.

294
00:12:54,140 --> 00:12:56,240
>> למען האמת, אני טוען את זה
הוא פשוט קשה יותר לקריאה.

295
00:12:56,240 --> 00:12:58,080
זה יותר קשה לזכור איפה
הולכים הסוגריים,

296
00:12:58,080 --> 00:12:59,030
כוכב וכל זה.

297
00:12:59,030 --> 00:13:02,150
אז העולם אימצה חלק תחבירי
סוכר, אם אפשר לומר כך.

298
00:13:02,150 --> 00:13:04,740
רק דרך סקסית לומר,
זה שווה ערך, ו

299
00:13:04,740 --> 00:13:05,970
אולי יותר אינטואיטיבי.

300
00:13:05,970 --> 00:13:09,600
אם המצביע הוא אכן מצביע,
אמצעי סימון חצים ללכת לשם ולמצוא

301
00:13:09,600 --> 00:13:11,890
השדה במקרה זה נקרא n.

302
00:13:11,890 --> 00:13:13,660
>> אז אם אני מוצא את זה, שים לב למה שאני עושה.

303
00:13:13,660 --> 00:13:17,430
אני פשוט להדפיס, מצאתי לי אחוזים,
חיבור הערך עבור int ש.

304
00:13:17,430 --> 00:13:20,730
אני קורא לישון לשנייה אחת רק לסוג
מלהשהות דברים על המסך כדי

305
00:13:20,730 --> 00:13:22,900
לתת למשתמש שני לספוג
מה בדיוק קרה.

306
00:13:22,900 --> 00:13:24,290
ואז אני שובר.

307
00:13:24,290 --> 00:13:26,330
אחרת, מה עליי לעשות?

308
00:13:26,330 --> 00:13:30,960
אני מעדכן את המצביע לשווה
חץ המצביע הבא.

309
00:13:30,960 --> 00:13:35,840
>> אז רק שיהיה ברור, זה אומר ללכת
שם, באמצעות הסימון בבית הספר הישן שלי.

310
00:13:35,840 --> 00:13:39,580
אז זה רק אומר ללכת לכל מה
אתה מצביע עליו, אשר במאוד

311
00:13:39,580 --> 00:13:43,660
המקרה הראשון הוא שאני מצביע על
struct עם תשע בו.

312
00:13:43,660 --> 00:13:44,510
אז אני כבר הלכתי לשם.

313
00:13:44,510 --> 00:13:47,880
ולאחר מכן סימון נקודת פירושו,
לקבל את הערך בצד.

314
00:13:47,880 --> 00:13:50,470
>> אבל הערך, למרות שזה נמשך
כצר, הוא רק מספר.

315
00:13:50,470 --> 00:13:51,720
זה כתובת מספרית.

316
00:13:51,720 --> 00:13:55,670
אז את הקו הזה אחת של קוד, בין אם
כתב ככה, מסתורי יותר

317
00:13:55,670 --> 00:14:00,190
דרך, או ככה, מעט יותר
אינטואיטיבי דרך, רק אומרת להזיז את היד שלי

318
00:14:00,190 --> 00:14:03,460
מהצומת הראשונה לבא אחריו,
ולאחר מכן הבא, ולאחר מכן

319
00:14:03,460 --> 00:14:05,320
הבא, וכן הלאה.

320
00:14:05,320 --> 00:14:09,920
>> אז אנחנו לא להתעכב על השני
מימושים של להוסיף ולמחוק

321
00:14:09,920 --> 00:14:14,030
וחצייה, שתיים הראשון של
אשר הם די מעורבים.

322
00:14:14,030 --> 00:14:17,010
ואני חושב שזה די קל לקבל
איבוד כאשר עושים את זה באופן מילולי.

323
00:14:17,010 --> 00:14:19,890
אבל מה שאנחנו יכולים לעשות כאן הוא
מנסה לקבוע כיצד

324
00:14:19,890 --> 00:14:21,640
הכי טוב לעשות את זה מבחינה ויזואלית.

325
00:14:21,640 --> 00:14:24,800
כי אני הייתי מציע שאם אנחנו
ברצונך להוסיף אלמנטים לתוך זה

326
00:14:24,800 --> 00:14:26,680
רשימה הקיימת, אשר
יש חמישה אלמנטים -

327
00:14:26,680 --> 00:14:29,530
9, 17, 22, 26, ו -33 -

328
00:14:29,530 --> 00:14:33,300
אם אני הולך ליישם את זה ב
קוד, אני צריך לחשוב איך ללכת

329
00:14:33,300 --> 00:14:34,160
על עושה את זה.

330
00:14:34,160 --> 00:14:37,720
>> ואני הייתי מציע לקחת צעדי תינוק
לפיו, במקרה הזה אני מתכוון, מה הם

331
00:14:37,720 --> 00:14:41,090
התרחישים האפשריים שאנו
עשוי להיתקל באופן כללי?

332
00:14:41,090 --> 00:14:44,120
בעת יישום להוספה מקושרת
רשימה, זה פשוט קורה להיות

333
00:14:44,120 --> 00:14:46,090
דוגמה ספציפית של גודל חמש.

334
00:14:46,090 --> 00:14:50,420
ובכן, אם ברצונך להוסיף מספר,
רוצה לומר מספר אחד, ו

335
00:14:50,420 --> 00:14:53,380
שמירה על סדר מיון, שבו
ברור שעושה מספר אחד צריך

336
00:14:53,380 --> 00:14:55,686
ללכת בדוגמה ספציפית זו?

337
00:14:55,686 --> 00:14:56,840
כמו בהתחלה.

338
00:14:56,840 --> 00:15:00,030
>> אבל מה שהמעניין הוא שיש
אם ברצונך להוסיף אחת לזו

339
00:15:00,030 --> 00:15:04,100
רשימה, מה שמצביע צרכי מיוחדים
להיות מעודכן ככל הנראה?

340
00:15:04,100 --> 00:15:04,610
ראשון.

341
00:15:04,610 --> 00:15:07,830
אז ברצוני לטעון, זה המקרה הראשון
שאולי כדאי לך לשקול,

342
00:15:07,830 --> 00:15:11,140
תרחיש של החדרה ב
תחילתה של הרשימה.

343
00:15:11,140 --> 00:15:15,400
>> בואו לתלוש אולי קל כמו או אפילו
מקרה קל יותר, באופן יחסי.

344
00:15:15,400 --> 00:15:18,110
נניח שאני רוצה להכניס את
מספר 35 על מנת מסודרים.

345
00:15:18,110 --> 00:15:20,600
זה ברור ששייך לשם.

346
00:15:20,600 --> 00:15:25,320
אז מה מצביע ללא ספק הולך
צריך להיות מעודכן בתרחיש זה?

347
00:15:25,320 --> 00:15:30,060
של 34 מצביע הופך לא ריק
אבל הכתובת של struct

348
00:15:30,060 --> 00:15:31,800
המכיל את המספר 35.

349
00:15:31,800 --> 00:15:32,750
אז זה מקרה שתיים.

350
00:15:32,750 --> 00:15:36,190
אז כבר, אני סוג של quantizing
כמה עבודה יש ​​לי לעשות כאן.

351
00:15:36,190 --> 00:15:39,880
>> ולבסוף, במקרה האמצעי הברור הוא
ואכן, באמצע, אם אני רוצה

352
00:15:39,880 --> 00:15:45,870
להכניס משהו כמו 23 אומרים, שהולך
בין 23 ו -26, אבל

353
00:15:45,870 --> 00:15:48,680
עכשיו דברים מקבלים קצת יותר
מעורב משום מה

354
00:15:48,680 --> 00:15:52,800
מצביעים צריכים להיות שונה?

355
00:15:52,800 --> 00:15:56,680
אז ברור שצריכים 22 כדי להיות שונה
בגלל שהוא לא יכול להצביע על 26 יותר.

356
00:15:56,680 --> 00:16:00,320
הוא צריך להצביע על הצומת החדשה ש
אני אצטרך להקצות על ידי קורא

357
00:16:00,320 --> 00:16:01,770
malloc או שווה ערך.

358
00:16:01,770 --> 00:16:05,990
>> אבל אז אני גם צריך שצומת חדשה, 23
במקרה זה, שיהיה לו מצביע

359
00:16:05,990 --> 00:16:07,870
מצביע על מי?

360
00:16:07,870 --> 00:16:08,560
26.

361
00:16:08,560 --> 00:16:10,380
ושם הולך להיות
סדר פעולות כאן.

362
00:16:10,380 --> 00:16:13,410
כי אם אני עושה את זה בטיפשות, ואני
לתחילת מופע בתחילת

363
00:16:13,410 --> 00:16:16,040
הרשימה, והמטרה שלי היא להכניס 23.

364
00:16:16,040 --> 00:16:18,610
ואני בודק, האם זה שייך
כאן, ליד תשע?

365
00:16:18,610 --> 00:16:18,950
לא.

366
00:16:18,950 --> 00:16:20,670
האם זה שייך לכאן, לצד 17?

367
00:16:20,670 --> 00:16:20,940
לא.

368
00:16:20,940 --> 00:16:22,530
האם הוא שייך לכאן לצד 22?

369
00:16:22,530 --> 00:16:23,300
כן.

370
00:16:23,300 --> 00:16:26,400
>> עכשיו, אם אני טיפש כאן, ולא
חשיבה זו דרך, אני יכול

371
00:16:26,400 --> 00:16:28,320
להקצות הצומת החדשה שלי ל -23.

372
00:16:28,320 --> 00:16:32,080
אני יכול לעדכן את המצביע מ
הצומת נקראת 22, והצביעה

373
00:16:32,080 --> 00:16:33,080
זה בצומת החדשה.

374
00:16:33,080 --> 00:16:36,140
ואז מה שאני צריך לעדכן
המצביע של הצומת החדשה יהיה?

375
00:16:36,140 --> 00:16:38,120
>> תלמיד: [לא ברור].

376
00:16:38,120 --> 00:16:38,385
>> רמקול 1: בדיוק.

377
00:16:38,385 --> 00:16:39,710
מצביע על 26.

378
00:16:39,710 --> 00:16:45,590
אבל לעזאזל, אם אני כבר לא עדכנו
המצביע של 22 להצביע על הבחור הזה, ו

379
00:16:45,590 --> 00:16:48,260
עכשיו יש לי יתומים, את שאר
מהרשימה, אם אפשר לומר כך.

380
00:16:48,260 --> 00:16:52,140
אז סדר פעולות כאן
הולך להיות חשוב.

381
00:16:52,140 --> 00:16:55,100
>> כדי לעשות זאת אני יכול לגנוב,
אומר, שש מתנדב.

382
00:16:55,100 --> 00:16:57,650
ובואו נראה אם ​​אנחנו לא יכולים לעשות את זה
מבחינה ויזואלית במקום חכם של קוד.

383
00:16:57,650 --> 00:16:59,330
ויש לנו קצת מתח מקסים
כדורים עבורך היום.

384
00:16:59,330 --> 00:17:02,510
אוקיי, מה דעתך על אחד, שתיים, ב
בחזרה - בסופו של דבר לשם.

385
00:17:02,510 --> 00:17:04,530
שלוש, ארבע, שניכם
החבר 'ה בסופו של הדבר.

386
00:17:04,530 --> 00:17:05,579
וחמש, שש.

387
00:17:05,579 --> 00:17:05,839
בטוח.

388
00:17:05,839 --> 00:17:06,450
חמש ושש.

389
00:17:06,450 --> 00:17:08,390
בסדר ואנחנו נבוא
לחבר 'ה בפעם הבאה.

390
00:17:08,390 --> 00:17:09,640
בסדר, בואו נעלה.

391
00:17:09,640 --> 00:17:12,010

392
00:17:12,010 --> 00:17:14,819
>> בסדר, שכן אתה כאן ראשון,
היית רוצה להיות זה שהמבוכה

393
00:17:14,819 --> 00:17:16,119
בגוגל זכוכית לכאן?

394
00:17:16,119 --> 00:17:19,075
בסדר, כן, בסדר, הזכוכית,
להקליט וידאו.

395
00:17:19,075 --> 00:17:22,720

396
00:17:22,720 --> 00:17:24,589
בסדר, אתה טוב ללכת.

397
00:17:24,589 --> 00:17:27,950
>> בסדר, אז אם אתם יכולים לבוא
כאן, יש לי מוכן מראש

398
00:17:27,950 --> 00:17:30,110
כמה מספרים.

399
00:17:30,110 --> 00:17:31,240
בסדר, בואו לכאן.

400
00:17:31,240 --> 00:17:33,440
ולמה שלא תלכו קצת
עוד יותר ככה.

401
00:17:33,440 --> 00:17:35,520
ובואו נראה, מה השם שלך,
עם זכוכית גוגל?

402
00:17:35,520 --> 00:17:35,910
>> תלמיד: בן.

403
00:17:35,910 --> 00:17:36,230
>> רמקול 1: בן?

404
00:17:36,230 --> 00:17:38,380
בסדר, בן, אתה יהיה ראשון, פשוטו כמשמעו.

405
00:17:38,380 --> 00:17:40,580
אז אנחנו הולכים לשלוח לך
לסיום השלב.

406
00:17:40,580 --> 00:17:41,670
בסדר, ואת השם שלך?

407
00:17:41,670 --> 00:17:41,990
>> תלמיד: ג'ייסון.

408
00:17:41,990 --> 00:17:44,530
>> 1 רמקול: ג'ייסון, בסדר אתה
להיות מספר תשע.

409
00:17:44,530 --> 00:17:46,700
אז אם אתה רוצה לעקוב אחר דרך שבן.

410
00:17:46,700 --> 00:17:47,010
>> תלמיד: ג'יל.

411
00:17:47,010 --> 00:17:49,630
>> רמקול 1: ג'יל, אתה הולך להיות
17, שאם הייתי עושה את זה יותר

412
00:17:49,630 --> 00:17:51,260
בתבונה, הייתי לי
התחיל בקצה השני.

413
00:17:51,260 --> 00:17:52,370
אתה הולך בדרך.

414
00:17:52,370 --> 00:17:53,030
22.

415
00:17:53,030 --> 00:17:53,670
ואתה?

416
00:17:53,670 --> 00:17:53,980
>> תלמיד: מרי.

417
00:17:53,980 --> 00:17:56,130
>> רמקול 1: מרי, תהיה 22.

418
00:17:56,130 --> 00:17:58,420
והשם שלך הוא?

419
00:17:58,420 --> 00:17:58,810
>> תלמיד: כריס.

420
00:17:58,810 --> 00:18:00,100
>> 1 רמקול: כריס, תהיה 26.

421
00:18:00,100 --> 00:18:00,740
ואז לבסוף.

422
00:18:00,740 --> 00:18:01,400
>> תלמיד: דיאנה.

423
00:18:01,400 --> 00:18:02,670
>> 1 רמקול: דיאנה, תהיה 34.

424
00:18:02,670 --> 00:18:03,920
אז אתה בא לכאן ב.

425
00:18:03,920 --> 00:18:06,360
>> בסדר, כל כך מושלם מסודרים
להזמין כבר.

426
00:18:06,360 --> 00:18:09,600
ובואו נלך קדימה ולעשות את זה
כך שאנחנו יכולים באמת -

427
00:18:09,600 --> 00:18:11,720
בן אתה פשוט סוג של מבט
אל שום מקום שם.

428
00:18:11,720 --> 00:18:15,670
אוקיי, אז בואו נלך קדימה ומתאר את זה
שימוש בנשק, ממש כמו שאני היה, בדיוק,

429
00:18:15,670 --> 00:18:16,250
מה קורה.

430
00:18:16,250 --> 00:18:19,540
אז קדימה, לתת לעצמכם
רגל או שניים בין עצמכם.

431
00:18:19,540 --> 00:18:22,900
וקדימה, להצביע ביד אחת כדי
כל מי שאתה צריך להיות בהצבעה

432
00:18:22,900 --> 00:18:23,470
על בסיס זה.

433
00:18:23,470 --> 00:18:25,890
ואם אתה רק נקודת אפס
ישר למטה לרצפה.

434
00:18:25,890 --> 00:18:27,690
אוקיי, אז טוב.

435
00:18:27,690 --> 00:18:32,290
>> אז עכשיו יש לנו רשימה מקושרת, ונתנו לי
מציע שאני אשחק את תפקידו של

436
00:18:32,290 --> 00:18:35,110
PTR, ולכן אני לא אטריד
הנושא הזה בסביבה.

437
00:18:35,110 --> 00:18:37,830
ולאחר מכן - כנס טיפש מישהו -
אתה יכול להתקשר לכל דבר הזה שאתה רוצה -

438
00:18:37,830 --> 00:18:39,800
מצביע קודמו, מצביע pred -

439
00:18:39,800 --> 00:18:43,930
זה רק הכינוי שנתנו ב
הקוד לדוגמא שלנו את יד השמאל שלי.

440
00:18:43,930 --> 00:18:47,240
מצד השני, שהולך להיות שמירה
אחר מי הוא מי ב

441
00:18:47,240 --> 00:18:48,400
בעקבות תרחישים.

442
00:18:48,400 --> 00:18:52,390
>> אז נניח, ראשית, אני רוצה לתלוש
שהדוגמא הראשונה של הכנסה, אומרת

443
00:18:52,390 --> 00:18:54,330
20, נכנס לרשימה.

444
00:18:54,330 --> 00:18:57,160
אז אני הולך צריך שמישהו
מגלם את המספר 20 בשבילנו.

445
00:18:57,160 --> 00:18:58,950
אז אני צריך מישהו malloc
מהקהל.

446
00:18:58,950 --> 00:18:59,380
בואו נעלה.

447
00:18:59,380 --> 00:19:00,340
מה שמך?

448
00:19:00,340 --> 00:19:01,300
>> תלמיד: בריאן.

449
00:19:01,300 --> 00:19:05,270
>> 1 רמקול: בריאן, בסדר, אז אתה
יהיה הצומת שמכילה 20.

450
00:19:05,270 --> 00:19:06,810
בסדר, בואו לכאן.

451
00:19:06,810 --> 00:19:10,025
וכמובן, שבו
אין בריאן שייך?

452
00:19:10,025 --> 00:19:12,190
אז, באמצע - למעשה,
חכה רגע.

453
00:19:12,190 --> 00:19:13,420
אנחנו עושים את זה מחוץ לסדר.

454
00:19:13,420 --> 00:19:17,170
אנחנו עושים את זה הרבה יותר קשה
ממה שהוא צריך להיות בהתחלה.

455
00:19:17,170 --> 00:19:21,210
אוקיי, אנחנו הולכים חופשיים בריאן
וrealloc בריאן כחמש.

456
00:19:21,210 --> 00:19:23,680
>> אוקיי, אז עכשיו אנחנו רוצים להכניס
בריאן כחמש.

457
00:19:23,680 --> 00:19:25,960
אז תבואו לכאן בסמוך ל
בן רק לרגע.

458
00:19:25,960 --> 00:19:28,250
ואתה כנראה יכול להגיד לי
לאן הסיפור הזה הולך.

459
00:19:28,250 --> 00:19:30,500
אבל בואו לחשוב היטב על
את סדר פעולות.

460
00:19:30,500 --> 00:19:32,880
וזה בדיוק את זה ויזואלית
זה הולך לעמוד בתור

461
00:19:32,880 --> 00:19:34,080
עם קוד לדוגמה ש.

462
00:19:34,080 --> 00:19:40,120
אז הנה יש לי בתחילה PTR מצביע
לא בבן, כשלעצמה, אבל בכל מה

463
00:19:40,120 --> 00:19:43,245
ערך שהוא מכיל, שבמקרה זה
הוא - איך קוראים לך שוב?

464
00:19:43,245 --> 00:19:43,670
>> תלמיד: ג'ייסון.

465
00:19:43,670 --> 00:19:47,350
>> 1 רמקול: ג'ייסון, ולכן גם בן ואני
מצביע על ג'ייסון ברגע זה.

466
00:19:47,350 --> 00:19:49,700
אז עכשיו אני צריך לקבוע,
שבו בריאן שייך?

467
00:19:49,700 --> 00:19:53,500
אז הדבר היחיד שיש לי גישה ל
עכשיו הוא פריט נתונים n.

468
00:19:53,500 --> 00:19:58,280
אז אני הולך לבדוק, הוא
בריאן פחות מ ג'ייסון?

469
00:19:58,280 --> 00:19:59,770
התשובה היא נכונה.

470
00:19:59,770 --> 00:20:03,680
>> אז מה עכשיו צריך לקרות,
בבסדר הנכון?

471
00:20:03,680 --> 00:20:07,120
אני צריך לעדכן כמה עצות
בסך הכל בסיפור הזה?

472
00:20:07,120 --> 00:20:10,720
איפה היד שלי עדיין מצביעה על
ג'ייסון, ואת היד שלך - אם אתה רוצה

473
00:20:10,720 --> 00:20:12,930
שם את היד שלך כמו, בערך, אני
לא יודע, סימן שאלה.

474
00:20:12,930 --> 00:20:14,070
בסדר, טוב.

475
00:20:14,070 --> 00:20:15,670
>> בסדר, אז יש לך
כמה מועמדים.

476
00:20:15,670 --> 00:20:20,500
כך או בן או אני או בריאן או ג'ייסון
או כל אחד אחר, אשר

477
00:20:20,500 --> 00:20:21,370
מצביעים צריכים לשנות?

478
00:20:21,370 --> 00:20:23,260
כמה בסך הכל?

479
00:20:23,260 --> 00:20:24,080
>> אוקיי, אז שתיים.

480
00:20:24,080 --> 00:20:27,090
המצביע שלי לא ממש משנה יותר
בגלל שאני רק זמני.

481
00:20:27,090 --> 00:20:31,370
אז זה שני החבר 'ה האלה, יש להניח,
גם בן ובריאן.

482
00:20:31,370 --> 00:20:34,410
אז הרשה לי להציע שאנחנו נעדכן
בן, שכן הוא ראשון.

483
00:20:34,410 --> 00:20:36,350
האלמנט הראשון של רשימה זו
עכשיו הוא הולך להיות בריאן.

484
00:20:36,350 --> 00:20:38,070
אז בן נקודה בבריאן.

485
00:20:38,070 --> 00:20:39,320
אוקיי, עכשיו מה?

486
00:20:39,320 --> 00:20:41,950

487
00:20:41,950 --> 00:20:43,460
>> מי מקבל הצביע על מי?

488
00:20:43,460 --> 00:20:44,710
>> תלמיד: [לא ברור].

489
00:20:44,710 --> 00:20:46,180
>> רמקול 1: אוקיי אז יש לי בריאן
כדי להצביע על ג'ייסון.

490
00:20:46,180 --> 00:20:48,360
אך איבדתי את המסלול של מצביע זה?

491
00:20:48,360 --> 00:20:49,980
האם אני יודע איפה הוא ג'ייסון?

492
00:20:49,980 --> 00:20:50,790
>> תלמיד: [לא ברור].

493
00:20:50,790 --> 00:20:52,620
>> 1 דובר: אני עושה, שכן אני
המצביע הזמני.

494
00:20:52,620 --> 00:20:55,110
ומן הסתם, אני לא השתנה
כדי להצביע על הצומת החדשה.

495
00:20:55,110 --> 00:20:58,300
אז יכול פשוט יש לנו בריאן נקודה
במי אני מצביע.

496
00:20:58,300 --> 00:20:59,000
ואנחנו נעשו.

497
00:20:59,000 --> 00:21:01,890
אז במקרה אחד, כניסה ב
תחילתה של הרשימה.

498
00:21:01,890 --> 00:21:02,950
היו שני שלבים עיקריים.

499
00:21:02,950 --> 00:21:06,750
אחד, אנחנו צריכים לעדכן את בן, ולאחר מכן
יש לנו גם לעדכן את בריאן.

500
00:21:06,750 --> 00:21:09,230
ואז אני לא צריך לטרוח
לשוטט דרך שאר

501
00:21:09,230 --> 00:21:12,680
רשימה, כי אנחנו כבר מצאנו את שלו
מיקום, כי הוא שייך ל

502
00:21:12,680 --> 00:21:14,080
שמאלי של הרכיב הראשון.

503
00:21:14,080 --> 00:21:15,400
>> בסדר, אז די פשוט.

504
00:21:15,400 --> 00:21:18,110
למעשה, מרגיש כאילו אנחנו כמעט
מה שהופך את זה מסובך מדי.

505
00:21:18,110 --> 00:21:20,240
אז בואו עכשיו למרוט את הסוף
מהרשימה, ורואה בו

506
00:21:20,240 --> 00:21:21,380
המורכבות מתחילה.

507
00:21:21,380 --> 00:21:24,560
אז אם עכשיו, אני alloc מהקהל.

508
00:21:24,560 --> 00:21:25,540
כל מי שרוצה לשחק 55?

509
00:21:25,540 --> 00:21:26,700
בסדר, ראיתי את היד שלך ראשון.

510
00:21:26,700 --> 00:21:29,620
בואו נעלה.

511
00:21:29,620 --> 00:21:30,030
כן.

512
00:21:30,030 --> 00:21:31,177
מה שמך?

513
00:21:31,177 --> 00:21:32,310
>> תלמיד: [לא ברור].

514
00:21:32,310 --> 00:21:33,240
>> רמקול 1: Habata.

515
00:21:33,240 --> 00:21:33,890
אוקיי, בואו נעלה.

516
00:21:33,890 --> 00:21:35,730
אתה תהיה המספר 55.

517
00:21:35,730 --> 00:21:37,820
אז אתה, כמובן, שייך
בסוף הרשימה.

518
00:21:37,820 --> 00:21:41,850
אז בואו להפעיל שוב את הסימולציה איתי
להיות PTR רק לרגע.

519
00:21:41,850 --> 00:21:44,050
אז אני ראשון הולך להצביע על
כל מה שבן מצביע ב.

520
00:21:44,050 --> 00:21:45,900
אנחנו מצביעים עכשיו גם בבריאן.

521
00:21:45,900 --> 00:21:48,420
אז 55 לא פחות מחמש.

522
00:21:48,420 --> 00:21:52,510
אז אני הולך לעדכן את עצמי על ידי
מצביע למצביע הבא של בריאן, ש

523
00:21:52,510 --> 00:21:54,450
כרגע הוא כמובן ג'ייסון.

524
00:21:54,450 --> 00:21:57,310
55 היא לא פחות מתשע, ולכן
אני הולך לעדכן PTR.

525
00:21:57,310 --> 00:21:58,890
אני הולך לעדכן PTR.

526
00:21:58,890 --> 00:22:02,290
אני הולך לעדכן PTR
אני הולך לעדכן PTR.

527
00:22:02,290 --> 00:22:05,060
ואני הולך - הממ, מה זה
השם שלך שוב?

528
00:22:05,060 --> 00:22:05,560
>> תלמיד: דיאנה.

529
00:22:05,560 --> 00:22:09,190
>> 1 רמקול: דיאנה היא מצביעה, כמובן,
בריק עם ידה השמאלית.

530
00:22:09,190 --> 00:22:13,030
אז איפה בעצם Habata
שייך באופן ברור?

531
00:22:13,030 --> 00:22:15,050
משמאל, כאן.

532
00:22:15,050 --> 00:22:19,460
אז איך אני יודע לשים אותה כאן
אני חושב שפשלתי.

533
00:22:19,460 --> 00:22:22,420
משום מה הוא PTR אמנות
רגע זה בזמן?

534
00:22:22,420 --> 00:22:23,240
Null.

535
00:22:23,240 --> 00:22:25,580
אז למרות ש, מבחינה ויזואלית, אנחנו יכולים
כמובן לראות את כל אלה

536
00:22:25,580 --> 00:22:26,610
החבר 'ה כאן על במה.

537
00:22:26,610 --> 00:22:29,680
אני כבר לא עקבתי אחר קודם
אדם ברשימה.

538
00:22:29,680 --> 00:22:33,210
אין לי את האצבע וציינה,
במקרה זה, מספר הצומת 34.

539
00:22:33,210 --> 00:22:34,760
>> אז בואו נתחיל דווקא על זה.

540
00:22:34,760 --> 00:22:37,560
אז עכשיו אני באמת צריך
משתנה מקומי שנייה.

541
00:22:37,560 --> 00:22:40,980
וזה מה שתראה ב
קוד C מדגם בפועל, שבו כמו שאני הולך,

542
00:22:40,980 --> 00:22:45,860
כאשר אני מעדכן את ידי הימנית כדי להצביע
ג'ייסון, ובכך משאיר מאחורי בריאן, אני

543
00:22:45,860 --> 00:22:51,440
עדיף להתחיל להשתמש ביד שמאל כדי
לעדכן היכן אני נמצא, אז זה כמו שאני אלך

544
00:22:51,440 --> 00:22:52,700
באמצעות רשימה זו -

545
00:22:52,700 --> 00:22:55,040
יותר מוזר ממה שהתכוונתי
עכשיו כאן מבחינה ויזואלית -

546
00:22:55,040 --> 00:22:56,740
אני הולך להגיע ל
סוף הרשימה.

547
00:22:56,740 --> 00:23:00,020
>> היד הזאת היא עדיין ריקה, וזה די
חסר תועלת, חוץ מלהצביע

548
00:23:00,020 --> 00:23:02,980
אני באופן ברור בסוף הרשימה,
אבל עכשיו לפחות יש לי את זה

549
00:23:02,980 --> 00:23:08,270
מצביע קודמו הצבעה כאן, אז
עכשיו מה ידיים ומה שמצביעים צריכים

550
00:23:08,270 --> 00:23:10,150
להיות מעודכן?

551
00:23:10,150 --> 00:23:13,214
ידו של מי שאתה רוצה
כדי להגדיר מחדש ראשון?

552
00:23:13,214 --> 00:23:15,190
>> תלמיד: [לא ברור].

553
00:23:15,190 --> 00:23:16,220
>> רמקול 1: אוקיי, אז של דיאנה.

554
00:23:16,220 --> 00:23:21,110
לאן אתה רוצה להצביע
המצביע השמאלי של דיאנה ב?

555
00:23:21,110 --> 00:23:23,620
בגיל 55, ככל הנראה, כך ש
אנחנו כבר הוכנסו לשם.

556
00:23:23,620 --> 00:23:25,560
ושבו צריך 55 מצביע ללכת?

557
00:23:25,560 --> 00:23:27,000
למטה, המייצג את האפס.

558
00:23:27,000 --> 00:23:28,890
וידי שלי, בשלב זה, לא
משנה כי הם היו פשוט

559
00:23:28,890 --> 00:23:30,070
משתנים זמניים.

560
00:23:30,070 --> 00:23:31,030
אז עכשיו אנחנו נעשה.

561
00:23:31,030 --> 00:23:34,650
>> אז מורכבות נוספת לשם - ו
זה לא כל כך קשה ליישום,

562
00:23:34,650 --> 00:23:38,660
אבל אנחנו צריכים לעשות משתנים משני
בטוח שלפני שאני מזיז את זכותי

563
00:23:38,660 --> 00:23:42,140
לעומת זאת, אני מעדכן את הערך שלי שמאלי
לעומת זאת, מצביע pred במקרה זה, ולכן

564
00:23:42,140 --> 00:23:45,860
שיש לי מצביע נגרר
כדי לעקוב אחר שבו אני היה.

565
00:23:45,860 --> 00:23:49,360
עכשיו במאמר מוסגר, אם אתה חושב כך
דרך, זה מרגיש כאילו זה

566
00:23:49,360 --> 00:23:51,490
קצת מעצבן שיש לשמור
אחר יד השמאל הזה.

567
00:23:51,490 --> 00:23:54,015
>> מה היית פתרון אחר
לבעיה זו היית?

568
00:23:54,015 --> 00:23:56,500
אם יש לך לעצב מחדש את הנתונים
מבנה שאנחנו מדברים

569
00:23:56,500 --> 00:23:59,630
עובר עכשיו?

570
00:23:59,630 --> 00:24:02,690
אם רק זה סוג של מרגיש קצת
מעצבן שיש, אוהב, שני מצביעים

571
00:24:02,690 --> 00:24:08,430
עובר ברשימה, מי עוד יכול
יש, בעולם אידיאלי, נשמר

572
00:24:08,430 --> 00:24:10,160
מידע שאנחנו צריכים?

573
00:24:10,160 --> 00:24:11,360
כן?

574
00:24:11,360 --> 00:24:12,610
>> תלמיד: [לא ברור].

575
00:24:12,610 --> 00:24:15,160

576
00:24:15,160 --> 00:24:16,150
>> רמקול 1: בדיוק.

577
00:24:16,150 --> 00:24:19,130
נכון, כך יש בעצם מעניין
נבט של רעיון.

578
00:24:19,130 --> 00:24:22,470
והרעיון הזה של מצביע קודם,
מצביע על האלמנט הקודם.

579
00:24:22,470 --> 00:24:25,580
מה אם אני רק מגולם כי
בתוך הרשימה עצמה?

580
00:24:25,580 --> 00:24:27,810
וזה הולך להיות קשה לדמיין
זה ללא כל הנייר

581
00:24:27,810 --> 00:24:28,830
נופל לרצפה.

582
00:24:28,830 --> 00:24:31,860
אבל נניח שהחבר 'ה האלה משמש גם
ידיים שלהם יש קודם

583
00:24:31,860 --> 00:24:35,950
מצביע, ומצביע הבא, ובכך
יישום מה שאנחנו נתקשר כפליים

584
00:24:35,950 --> 00:24:36,830
רשימה מקושרת.

585
00:24:36,830 --> 00:24:41,090
שיאפשר לי למיין של אחורה,
הרבה יותר בקלות בלעדיי,

586
00:24:41,090 --> 00:24:43,800
מתכנת, שיש לשמור על
לעקוב באופן ידני -

587
00:24:43,800 --> 00:24:44,980
באמת באופן ידני -

588
00:24:44,980 --> 00:24:47,280
מקום שבו הייתי בעבר
ברשימה.

589
00:24:47,280 --> 00:24:48,110
אז אנחנו לא עושים את זה.

590
00:24:48,110 --> 00:24:50,950
אנחנו נשמור את זה פשוט כי זה
הולך לבוא במחיר, פי שתיים

591
00:24:50,950 --> 00:24:53,450
הרבה מקום לעצות,
אם אתה רוצה שנייה אחת.

592
00:24:53,450 --> 00:24:55,760
אבל זה אכן נפוץ
מבנה נתונים המכונה

593
00:24:55,760 --> 00:24:57,410
רשימה מקושרת כפליים.

594
00:24:57,410 --> 00:25:01,310
>> בואו נעשה את הדוגמא האחרונה לכאן ולשים
החבר 'ה האלה מייסוריהם.

595
00:25:01,310 --> 00:25:03,270
אז malloc 20.

596
00:25:03,270 --> 00:25:05,320
בואו נעלה מהמעבר לשם.

597
00:25:05,320 --> 00:25:06,280
בסדר, מה השם שלך?

598
00:25:06,280 --> 00:25:07,440
>> תלמיד: [לא ברור].

599
00:25:07,440 --> 00:25:07,855
>> 1 דובר: סליחה?

600
00:25:07,855 --> 00:25:08,480
>> תלמיד: [לא ברור].

601
00:25:08,480 --> 00:25:09,410
>> רמקול 1: Demeron?

602
00:25:09,410 --> 00:25:10,230
אישור מגיע בעד.

603
00:25:10,230 --> 00:25:11,910
אתה תהיה 20.

604
00:25:11,910 --> 00:25:14,720
ברור שאתה הולך
שייכים בין 17 ו -22.

605
00:25:14,720 --> 00:25:16,150
אז תן לי ללמוד את הלקח שלי.

606
00:25:16,150 --> 00:25:18,150
אני הולך להתחיל מצביע
מצביע על בריאן.

607
00:25:18,150 --> 00:25:21,190
ואני הולך לי יד השמאל
רק לעדכן לבריאן כמו שאני עובר ל

608
00:25:21,190 --> 00:25:23,600
ג'ייסון, הבדיקה עושה 20 פחות מתשעה?

609
00:25:23,600 --> 00:25:24,060
לא.

610
00:25:24,060 --> 00:25:25,430
האם 20 פחות מ 17?

611
00:25:25,430 --> 00:25:25,880
לא.

612
00:25:25,880 --> 00:25:27,450
האם 20 פחות מ 22?

613
00:25:27,450 --> 00:25:28,440
כן.

614
00:25:28,440 --> 00:25:34,070
אז מה מצביעים או ידיים צריכים לשנות
שבו הם מצביעים עכשיו?

615
00:25:34,070 --> 00:25:37,070
>> אז אנחנו יכולים לעשות 17 מצביעים על 20.

616
00:25:37,070 --> 00:25:37,860
אז זה בסדר.

617
00:25:37,860 --> 00:25:40,080
לאן אנחנו רוצים להצביע
המצביע שלך עכשיו?

618
00:25:40,080 --> 00:25:41,330
בגיל 22.

619
00:25:41,330 --> 00:25:45,410
ואנחנו יודעים איפה הוא 22, שוב תודה
למצביע הזמני שלי.

620
00:25:45,410 --> 00:25:46,760
אז אנחנו בסדר שם.

621
00:25:46,760 --> 00:25:49,440
אז בגלל זה אחסון זמני
אני כל הזמן אחר שבו כולם.

622
00:25:49,440 --> 00:25:55,055
ועכשיו לך מבחינה ויזואלית יכול להיכנס לשם
אתה שייך, ועכשיו אנחנו צריכים 1, 2, 3,

623
00:25:55,055 --> 00:25:58,410
4, 5, 6, 7, 8, 9 כדורי לחץ,
ומחיאות כפות ל

624
00:25:58,410 --> 00:25:59,770
החבר 'ה האלה, אם אנחנו יכולים.

625
00:25:59,770 --> 00:26:00,410
יפה עשה.

626
00:26:00,410 --> 00:26:05,320
>> [מחיאות כפות]

627
00:26:05,320 --> 00:26:06,330
>> רמקול 1: בסדר.

628
00:26:06,330 --> 00:26:09,860
ואתה יכול לשמור את החתיכות
נייר כמזכרות.

629
00:26:09,860 --> 00:26:15,930
>> בסדר, אז, יאמין לי שזה הרבה
קל יותר לעבור את זה עם

630
00:26:15,930 --> 00:26:17,680
בני אדם מאשר עם קוד בפועל.

631
00:26:17,680 --> 00:26:22,690
אבל מה יגיד לך למצוא ברגע
עכשיו, הוא שאותו - הו, תודה לך.

632
00:26:22,690 --> 00:26:23,630
תודה לך -

633
00:26:23,630 --> 00:26:29,360
הוא שאתה תמצא כי אותם נתונים
מבנה, רשימה מקושרת, יכולה למעשה

634
00:26:29,360 --> 00:26:33,200
לשמש כאבן בניין לעוד יותר
מבני נתונים מתוחכמים.

635
00:26:33,200 --> 00:26:37,620
>> ומבין גם את ערכת נושא כאן הוא כי
בהחלט יש לנו הצגנו יותר

636
00:26:37,620 --> 00:26:40,060
מורכבות ביישום
של אלגוריתם זה.

637
00:26:40,060 --> 00:26:43,940
הכנסה, ואם אנחנו עברנו את זה,
מחיקה וחיפוש, הוא קצת

638
00:26:43,940 --> 00:26:46,660
יותר מסובך ממה שזה
היה עם מערך.

639
00:26:46,660 --> 00:26:48,040
אבל אנחנו להרוויח קצת דינמי.

640
00:26:48,040 --> 00:26:50,180
אנחנו מקבלים את מבנה הנתונים אדפטיבית.

641
00:26:50,180 --> 00:26:54,010
>> אבל שוב, אנחנו משלמים מחיר של שיש קצת
מורכבות נוספות, הן ב

642
00:26:54,010 --> 00:26:54,910
יישום זה.

643
00:26:54,910 --> 00:26:56,750
ואנחנו מוותרים גישה אקראית.

644
00:26:56,750 --> 00:27:00,450
ואם להיות כנים, אין איזו נחמד
לנקות שקופית שאני יכול לתת לך את זה

645
00:27:00,450 --> 00:27:03,120
אומר כאן היא מדוע רשימה מקושרת
הוא טוב יותר ממערך.

646
00:27:03,120 --> 00:27:04,100
ותשאיר את זה ככה.

647
00:27:04,100 --> 00:27:07,520
בגלל הנושא reoccurring עכשיו, אפילו
יותר מכך, בשבועות הקרובים, הוא

648
00:27:07,520 --> 00:27:10,200
כי אין בהכרח
תשובה נכונה.

649
00:27:10,200 --> 00:27:13,830
>> זו הסיבה שיש לנו את הציר הנפרד
של עיצוב סטים לבעייתיים.

650
00:27:13,830 --> 00:27:17,700
זה יהיה מאוד רגיש להקשר
אם ברצונך להשתמש בנתונים אלה

651
00:27:17,700 --> 00:27:21,750
מבנה או אחר, וזה יהיה
תלוי במה שחשוב לך במונחים

652
00:27:21,750 --> 00:27:24,620
במשאבים ובמורכבות.

653
00:27:24,620 --> 00:27:28,830
>> אבל הרשה לי להציע כי הנתונים האידיאליים
מבנה, הגביע הקדוש, יהיה

654
00:27:28,830 --> 00:27:32,200
משהו שהוא זמן קבוע,
בלי קשר לכמה חומר יש

655
00:27:32,200 --> 00:27:36,940
בתוכו, לא יהיה זה מדהים אם
מבנה הנתונים חזר בתשובות

656
00:27:36,940 --> 00:27:37,920
זמן קבוע.

657
00:27:37,920 --> 00:27:38,330
כן.

658
00:27:38,330 --> 00:27:40,110
מילה זו היא במילון הענק שלך.

659
00:27:40,110 --> 00:27:41,550
או לא, זה לא מילה.

660
00:27:41,550 --> 00:27:43,270
או כל בעיה כזו שם.

661
00:27:43,270 --> 00:27:46,360
ובכן בואו תראו אם אנחנו לא יכולים לפחות
לקחת צעד לכיוון זה.

662
00:27:46,360 --> 00:27:50,190
>> הרשה לי להציע מבנה נתונים חדש ה
ניתן להשתמש בו לדברים שונים,

663
00:27:50,190 --> 00:27:52,260
במקרה הזה שנקרא שולחן חשיש.

664
00:27:52,260 --> 00:27:55,590
וכך אנחנו בעצם חזרה למציצים
במערך, במקרה זה, ו

665
00:27:55,590 --> 00:28:00,550
באופן שרירותי למדי, שנמשך זה
שולחן חשיש כמערך עם סוג של

666
00:28:00,550 --> 00:28:02,810
מערך דו - ממדים

667
00:28:02,810 --> 00:28:05,410
או ליתר דיוק, הוא מתואר כאן כשניים
מערך ממדי - אבל זה רק

668
00:28:05,410 --> 00:28:10,770
מערך של גודל 26, כך שאם אנחנו
קורא את טבלת המערך, סוגר שולחן

669
00:28:10,770 --> 00:28:12,440
אפס הוא המלבן בחלקו העליון.

670
00:28:12,440 --> 00:28:15,090
טבלה סוגר 25 הוא המלבן
בתחתית.

671
00:28:15,090 --> 00:28:18,620
ואת זה איך אני יכול לצייר נתונים
מבנה שבו אני רוצה לאחסן

672
00:28:18,620 --> 00:28:19,790
שמות של אנשים.

673
00:28:19,790 --> 00:28:24,370
>> כך למשל, ואני לא לצייר
כל דבר כאן על התקורה, אם אני

674
00:28:24,370 --> 00:28:29,160
היה לי המערך הזה, שעכשיו אני הולך
קורא לשולחן חשיש, וזה שוב

675
00:28:29,160 --> 00:28:31,360
מיקום אפס.

676
00:28:31,360 --> 00:28:34,840
זה כאן הוא מיקום
אחד, וכן הלאה.

677
00:28:34,840 --> 00:28:37,880
אני טוען שאני רוצה להשתמש בנתונים אלה
מבנה, למען הדיון,

678
00:28:37,880 --> 00:28:42,600
כדי לאחסן את השמות של אנשים, אליס ובוב
וצ'רלי ושמות כאלה אחרים.

679
00:28:42,600 --> 00:28:46,110
אז תחשוב על זה עכשיו כהתחלה
של, יניח, מילון

680
00:28:46,110 --> 00:28:47,520
עם הרבה מילים.

681
00:28:47,520 --> 00:28:49,435
הם קורים להיות שמות
בדוגמא שלנו כאן.

682
00:28:49,435 --> 00:28:52,560
וזה כל מה ששייך גם, אולי, כדי
יישום בודק איות, כפי שאנו

683
00:28:52,560 --> 00:28:54,400
אולי לבעיה להגדיר שש.

684
00:28:54,400 --> 00:28:59,300
>> אז אם יש לנו מערך של גודל כולל 26
כך שזה המיקום שה -25

685
00:28:59,300 --> 00:29:03,390
בתחתית, ואני טוען שאליס היא
המילה הראשונה במילון של

686
00:29:03,390 --> 00:29:07,260
שמות שאני רוצה להכניס לזכרון RAM,
למבנה נתונים זה, שבו הם

687
00:29:07,260 --> 00:29:12,480
אינסטינקטים אומרים לך ששל אליס
שם צריך ללכת במערך הזה?

688
00:29:12,480 --> 00:29:13,510
>> יש לנו 26 אפשרויות.

689
00:29:13,510 --> 00:29:14,990
שבו אנחנו רוצים לשים אותה?

690
00:29:14,990 --> 00:29:16,200
אנחנו רוצים אותה במדרגת אפס, נכון?

691
00:29:16,200 --> 00:29:18,280
לאליס, בואו נקראים לזה אפס.

692
00:29:18,280 --> 00:29:20,110
ו-B יהיה אחד, ו-C יהיה שתיים.

693
00:29:20,110 --> 00:29:22,600
אז אנחנו הולכים לכתוב
שמה של אליס כאן למעלה.

694
00:29:22,600 --> 00:29:24,890
אם לאחר מכן להוסיף את בוב,
שם ילכו כאן.

695
00:29:24,890 --> 00:29:27,280
צ'רלי ילך כאן.

696
00:29:27,280 --> 00:29:30,500
וכל כך למטה שוב דרך
מבנה נתונים זה.

697
00:29:30,500 --> 00:29:32,090
>> זהו מבנה נתונים נפלא.

698
00:29:32,090 --> 00:29:32,730
למה?

699
00:29:32,730 --> 00:29:37,460
ובכן מה הוא זמן הריצה של
הוספת שמו של אדם לתוך זה

700
00:29:37,460 --> 00:29:39,850
נתוני מבנה עכשיו?

701
00:29:39,850 --> 00:29:43,702
בהתחשב בעובדה שהשולחן הזה מיושם,
באמת, כמו מערך.

702
00:29:43,702 --> 00:29:44,940
ובכן זה זמן קבוע.

703
00:29:44,940 --> 00:29:45,800
זה סדר אחד.

704
00:29:45,800 --> 00:29:46,360
למה?

705
00:29:46,360 --> 00:29:48,630
>> ובכן איך אתה לקבוע
איפה אליס שייכת?

706
00:29:48,630 --> 00:29:51,000
אתה מסתכל על המכתב שקורא לה?

707
00:29:51,000 --> 00:29:51,490
הראשון.

708
00:29:51,490 --> 00:29:54,350
ואתה יכול להגיע לשם, אם זה מחרוזת,
רק על ידי הסתכלות במחרוזת

709
00:29:54,350 --> 00:29:55,200
סוגר אפס.

710
00:29:55,200 --> 00:29:57,110
אז את דמות האפס של המחרוזת.

711
00:29:57,110 --> 00:29:57,610
זה קל.

712
00:29:57,610 --> 00:30:00,350
אנחנו עשינו את זה בסתר
לפני שבועות הקצאה.

713
00:30:00,350 --> 00:30:05,310
ואז ברגע שאתה יודע את זה של אליס
מכתב הון, אנחנו יכולים להחסיר

714
00:30:05,310 --> 00:30:08,160
מעל 65 או בהון עצמו,
זה נותן לנו אפס.

715
00:30:08,160 --> 00:30:10,940
אז עכשיו אנחנו יודעים שאליס שייכת
במיקום אפס.

716
00:30:10,940 --> 00:30:14,240
>> ונתן מצביע לנתונים אלה
מבנה, מסוג כלשהו, ​​כמה זמן

717
00:30:14,240 --> 00:30:18,840
ייקח לי למצוא את המיקום
לאפס במערך?

718
00:30:18,840 --> 00:30:22,080
צעד אחד פשוט, נכון הגיע זמן קבוע
בגלל הגישה האקראית

719
00:30:22,080 --> 00:30:23,780
ההצעה הייתה תכונה של מערך.

720
00:30:23,780 --> 00:30:28,570
אז בקיצור, להבין מה המדד
שמו של אליס הוא, שהוא, ב

721
00:30:28,570 --> 00:30:32,610
מקרה זה, הוא, או בואו פשוט לפתור
כי לאפס, שבו ב 'הוא אחד וC היא

722
00:30:32,610 --> 00:30:34,900
שתיים, בהנחה שיצאה
זמן קבוע.

723
00:30:34,900 --> 00:30:38,510
אני רק צריך להסתכל על המכתב הראשון שלה,
להבין היכן הוא אפס

724
00:30:38,510 --> 00:30:40,460
מערך הוא גם זמן קבוע.

725
00:30:40,460 --> 00:30:42,140
אז מבחינה טכנית זה
כמו שני צעדים עכשיו.

726
00:30:42,140 --> 00:30:43,330
אבל זה עדיין קבוע.

727
00:30:43,330 --> 00:30:46,880
אז אנחנו קוראים לזה O הגדול של אחד, ולכן יש לנו
הוכנס לאליס בטבלה זו

728
00:30:46,880 --> 00:30:48,440
זמן קבוע.

729
00:30:48,440 --> 00:30:50,960
>> אבל כמובן, אני מדבר
נאיבי כאן, נכון?

730
00:30:50,960 --> 00:30:53,240
מה אם יש אהרון בכיתה?

731
00:30:53,240 --> 00:30:53,990
או אליסיה?

732
00:30:53,990 --> 00:30:57,230
או כל שמות אחרים מתחילים עם
א 'לאן אנחנו הולכים לשים

733
00:30:57,230 --> 00:31:00,800
אדם זה, נכון?

734
00:31:00,800 --> 00:31:03,420
אני מתכוון, עכשיו יש רק שלושה
אנשים שעל השולחן, אז אולי

735
00:31:03,420 --> 00:31:07,490
צריך לשים את אהרון במיקום
אפס אחת שניים שלוש.

736
00:31:07,490 --> 00:31:09,480
>> נכון, אני יכול לשים כאן.

737
00:31:09,480 --> 00:31:13,350
אבל אז, אם תנסו להכניס לתוך דוד
רשימה זו, שבו אין דוד ללכת?

738
00:31:13,350 --> 00:31:15,170
כעת המערכת שלנו מתחילה לשבור
למטה, נכון?

739
00:31:15,170 --> 00:31:19,210
כי עכשיו דוד מסתיים כאן
אם אהרון הוא בעצם כאן.

740
00:31:19,210 --> 00:31:23,060
ועכשיו כל הרעיון הזה כל כך שיש לו
מבנה נתונים נקי שנותן לנו

741
00:31:23,060 --> 00:31:28,010
הוספות זמן קבועות היא כבר לא
זמן קבוע, משום שיש לי

742
00:31:28,010 --> 00:31:31,240
לבדוק, הו, לעזאזל, מישהו כבר
במיקומה של אליס.

743
00:31:31,240 --> 00:31:35,320
>> תן לי לבדוק את שאר הנתונים
מבנה, מחפש מקום לשים

744
00:31:35,320 --> 00:31:37,130
מישהו כמו שמו של אהרון.

745
00:31:37,130 --> 00:31:39,390
וכדי שגם הוא מתחיל
לקחת את הזמן ליניארי.

746
00:31:39,390 --> 00:31:42,710
יתר על כן, אם אתה עכשיו רוצה למצוא
אהרון במבנה נתונים זה, ואתה

747
00:31:42,710 --> 00:31:45,430
לבדוק, ואת שמו של אהרון הוא לא כאן.

748
00:31:45,430 --> 00:31:47,960
באופן אידיאלי, היית פשוט אומר לאהרן
לא במבנה הנתונים.

749
00:31:47,960 --> 00:31:51,530
אבל אם אתה עושה את מה שהופך את המקום למתחיל
אהרן שבו אמור היה להיות D

750
00:31:51,530 --> 00:31:55,600
או דואר, אתה, במקרה הגרוע ביותר, צריך לבדוק
כל מבנה נתונים, ב

751
00:31:55,600 --> 00:31:59,480
ומקרה זה מוטל למשהו
ליניארי בגודל של השולחן.

752
00:31:59,480 --> 00:32:00,920
>> אז בסדר, אני אסדר את זה.

753
00:32:00,920 --> 00:32:04,200
הבעיה כאן היא שיש לי
26 גורמים במערך זה.

754
00:32:04,200 --> 00:32:05,000
תן לי לשנות את זה.

755
00:32:05,000 --> 00:32:06,010
אופס.

756
00:32:06,010 --> 00:32:10,600
תן לי לשנות אותו כך שבמקום להיות של
גודל 26 בסך הכל, שים לב לתחתית

757
00:32:10,600 --> 00:32:12,720
המדד עומד לשנות לn מינוס 1.

758
00:32:12,720 --> 00:32:16,610
אם 26 הוא בבירור קטנה מדי עבור בני אדם "
שמות, כי יש אלפי

759
00:32:16,610 --> 00:32:20,830
שמות של העולם, בואו פשוט לעשות
ב100 או 1,000 או 10,000.

760
00:32:20,830 --> 00:32:22,960
בואו פשוט להקצות הרבה יותר מקום.

761
00:32:22,960 --> 00:32:27,230
>> ובכן זה לא בהכרח להקטין
ההסתברות שלא תהיה לנו שתיים

762
00:32:27,230 --> 00:32:31,510
אנשים עם שמות החל, ו
כך, שאתה הולך לנסות לשים

763
00:32:31,510 --> 00:32:33,120
שמות במיקום עדיין אפס.

764
00:32:33,120 --> 00:32:36,850
הם עדיין הולכים להתנגש, אשר
משמעות הדבר היא שאנחנו עדיין זקוקים לפתרון לשים

765
00:32:36,850 --> 00:32:41,020
אליס ואהרון ואלישיה ואחרים
שמות שמתחילים במקום אחר.

766
00:32:41,020 --> 00:32:43,460
אבל איזה חלק מבעיה היא זו?

767
00:32:43,460 --> 00:32:46,870
מה ההסתברות שאתה
יש התנגשויות בנתונים

768
00:32:46,870 --> 00:32:48,240
מבנה כזה?

769
00:32:48,240 --> 00:32:52,570
>> ובכן, הרשה לי - אנחנו נחזור
לשאלה הזאת כאן.

770
00:32:52,570 --> 00:32:55,530
ולהסתכל איך אנחנו יכולים
לפתור אותה ראשונה.

771
00:32:55,530 --> 00:32:58,480
תן לי למשוך את ההצעה הזו כאן.

772
00:32:58,480 --> 00:33:02,020
מה שתוארנו הוא אלגוריתם,
היוריסטי הנקרא ליניארי

773
00:33:02,020 --> 00:33:05,030
חיטוט לפיו, אם היית מנסה להכניס
משהו כאן בנתונים אלה

774
00:33:05,030 --> 00:33:08,920
מבנה, שנקרא שולחן חשיש,
ושאין מקום שם, אתה

775
00:33:08,920 --> 00:33:12,000
באמת לחקור את מבנה הנתונים
בדיקה, האם זה זמין?

776
00:33:12,000 --> 00:33:13,430
האם זה זמין הוא זה זמין?

777
00:33:13,430 --> 00:33:13,980
האם זה זמין?

778
00:33:13,980 --> 00:33:17,550
וגם כשזה סוף סוף הוא, שאתה מכניס את
שם שנועדת במקור

779
00:33:17,550 --> 00:33:19,370
במקום אחר באותו מיקום.

780
00:33:19,370 --> 00:33:23,360
אבל במקרה הגרוע ביותר, המקום היחיד
יכול להיות מאוד תחתון של הנתונים

781
00:33:23,360 --> 00:33:25,090
מבנה, ממש בסוף של המערך.

782
00:33:25,090 --> 00:33:30,130
>> אז ליניארי חיטוט, במקרה הגרוע ביותר,
מוטל לתוך אלגוריתם ליניארי שבו

783
00:33:30,130 --> 00:33:34,500
אהרון, אם הוא קורה להיות מוכנס אחרון
במבנה נתונים זה, שהוא אולי

784
00:33:34,500 --> 00:33:39,540
מתנגש עם המיקום הראשון, אבל
אז בסופו של מזל רע בסוף.

785
00:33:39,540 --> 00:33:43,940
אז זה לא קבוע
זמן גביע קדוש עבורנו.

786
00:33:43,940 --> 00:33:47,650
גישה זו של החדרת אלמנטים לתוך
מבנה נתונים בשם חשיש

787
00:33:47,650 --> 00:33:52,050
נראית טבלה לא להיות זמן קבוע
לפחות לא במקרה הכללי.

788
00:33:52,050 --> 00:33:54,000
זה יכול להתפתח למשהו ליניארי.

789
00:33:54,000 --> 00:33:56,970
>> אז מה אם אנו פותרים התנגשויות
קצת אחר?

790
00:33:56,970 --> 00:34:00,740
אז הנה מתוחכם יותר
מתקרב למה שעדיין

791
00:34:00,740 --> 00:34:02,800
נקרא שולחן חשיש.

792
00:34:02,800 --> 00:34:05,890
ועל ידי חשיש, במאמר מוסגר, מה
אני מתכוון לומר הוא שהמדד

793
00:34:05,890 --> 00:34:07,070
אני התייחסתי קודם לכן.

794
00:34:07,070 --> 00:34:09,810
למשהו חשיש יכול להיות
חשב עליו כפועל.

795
00:34:09,810 --> 00:34:13,690
>> אז אם אתה חשיש אליס זה שם,
פונקציית hash, כביכול,

796
00:34:13,690 --> 00:34:14,710
צריך להחזיר מספר.

797
00:34:14,710 --> 00:34:18,199
במקרה זה הוא אפס, אם היא שייכת ב
אפס מקום, אחד אם היא שייכת ב

798
00:34:18,199 --> 00:34:20,000
מיקום אחד, וכן הלאה.

799
00:34:20,000 --> 00:34:24,360
אז פונקציית hash שלי עד כה הייתה
סופר פשוט, רק מסתכל

800
00:34:24,360 --> 00:34:26,159
האות ראשונה בשמו של מישהו.

801
00:34:26,159 --> 00:34:29,090
אבל פונקציית hash לוקחת כ
קלט מסוים פיסת המידע,

802
00:34:29,090 --> 00:34:30,210
מחרוזת, int, לא משנה מה.

803
00:34:30,210 --> 00:34:32,239
וזה בדרך כלל יורק את מספר.

804
00:34:32,239 --> 00:34:35,739
ומספר זה הוא שבו נתונים
אלמנט שייך במבנה נתונים

805
00:34:35,739 --> 00:34:37,800
מכונה כאן שולחן חשיש.

806
00:34:37,800 --> 00:34:41,400
>> אז רק באופן אינטואיטיבי, זה
הקשר מעט שונה.

807
00:34:41,400 --> 00:34:44,170
בעצם זה מתייחס לדוגמה
ימי הולדת, מעורב בי

808
00:34:44,170 --> 00:34:46,850
ייתכן שיש רבים כמו
31 ימים בחודש.

809
00:34:46,850 --> 00:34:52,239
אבל מה שהאדם הזה מחליט
לעשות במקרה של התנגשות?

810
00:34:52,239 --> 00:34:55,304
הקשר עכשיו להיות, ולא התנגשות של
שמות, אבל התנגשות של ימי הולדת,

811
00:34:55,304 --> 00:35:00,760
אם יש שני אנשים באותו יום הולדת על
ב -2 באוקטובר, למשל.

812
00:35:00,760 --> 00:35:02,120
>> תלמיד: [לא ברור].

813
00:35:02,120 --> 00:35:05,010
>> רמקול 1: כן, אז יש לנו כאן
המינוף של רשימות מקושרות.

814
00:35:05,010 --> 00:35:07,830
אז זה נראה קצת אחר
ממה שאנחנו ציירנו אותו קודם לכן.

815
00:35:07,830 --> 00:35:10,790
אבל נראה שיש לנו למערך
בצד השמאל.

816
00:35:10,790 --> 00:35:13,230
זה מדד אחד, בלי שום
סיבה מסוימת.

817
00:35:13,230 --> 00:35:14,630
אבל זה עדיין מערך.

818
00:35:14,630 --> 00:35:16,160
זה מערך של מצביעים.

819
00:35:16,160 --> 00:35:20,670
וכל אחד מהאלמנטים האלה, שכל אחד
חוגים אלה ונטויים - הלוכסן

820
00:35:20,670 --> 00:35:23,970
מייצג null - כל אחד מאלה
מצביעים הוא ככל הנראה מצביעים על

821
00:35:23,970 --> 00:35:25,730
מה מבנה הנתונים?

822
00:35:25,730 --> 00:35:26,890
רשימה מקושרת.

823
00:35:26,890 --> 00:35:30,530
>> אז עכשיו יש לנו את היכולת
קוד קשה לתכנית שלנו

824
00:35:30,530 --> 00:35:32,010
גודלו של השולחן.

825
00:35:32,010 --> 00:35:35,360
במקרה זה, אנחנו יודעים שאף פעם אין
יותר מ 31 ימים בחודש.

826
00:35:35,360 --> 00:35:38,480
כל כך קשה קידוד ערך כמו 31 הוא
סביר בהקשר זה.

827
00:35:38,480 --> 00:35:42,700
בהקשר של שמות, קשה קידוד
26 היא לא בלתי סביר זה של אנשים

828
00:35:42,700 --> 00:35:46,340
שמות להתחיל רק עם, למשל,
האלפבית מעורב דרך ז'

829
00:35:46,340 --> 00:35:50,180
>> אנחנו יכולים לדחוס את כולם לנתונים
מבנה כל עוד, כשנגיע

830
00:35:50,180 --> 00:35:55,330
התנגשות, שאנו לא לשים את השמות כאן,
אנחנו חושבים שבמקום תאים אלה

831
00:35:55,330 --> 00:36:00,270
לא כמחרוזות עצמם, אבל כמו
מצביעים ל, למשל, אליס.

832
00:36:00,270 --> 00:36:03,660
ואז אליס יכולה להיות מצביע אחר
לשם אחרת מתחילים עם

833
00:36:03,660 --> 00:36:06,150
א ובוב ניגש דווקא כאן.

834
00:36:06,150 --> 00:36:10,850
>> ואם יש שם אחר מתחיל
עם ב ', שהוא בסופו לכאן.

835
00:36:10,850 --> 00:36:15,070
וכך כל אחד מהאלמנטים של זה
שולחן שתיים, אם זה נועד

836
00:36:15,070 --> 00:36:17,350
קצת יותר בחוכמה -

837
00:36:17,350 --> 00:36:18,125
יאללה -

838
00:36:18,125 --> 00:36:22,950
אם עיצבנו יותר קטן הזה
חוכמה, עכשיו הופך לנתונים מסתגלים

839
00:36:22,950 --> 00:36:27,720
מבנה, שבו אין מגבלה קשה
על כמה אלמנטים שאתה יכול להוסיף

840
00:36:27,720 --> 00:36:30,700
לתוך זה כי אם אתה עושה יש לי
התנגשות, וזה בסדר.

841
00:36:30,700 --> 00:36:34,690
רק קדימה ולצרף אותו ל
מה שראינו לפני קצת היה

842
00:36:34,690 --> 00:36:38,290
ידוע כרשימה מקושרת.

843
00:36:38,290 --> 00:36:39,690
>> ובכן בואו לעצור לרגע.

844
00:36:39,690 --> 00:36:42,570
מה ההסתברות של התנגשות
במקום הראשון?

845
00:36:42,570 --> 00:36:45,480
נכון, אולי אני חושב על, אולי
אני מעל הנדסת בעיה זו,

846
00:36:45,480 --> 00:36:46,370
כי אתה יודע מה?

847
00:36:46,370 --> 00:36:49,070
כן, אני יכול לבוא עם שרירותי
דוגמאות את החלק העליון של הראש שלי כמו

848
00:36:49,070 --> 00:36:52,870
אליסון ואהרון, אבל במציאות,
ניתנו התפלגות אחידה של

849
00:36:52,870 --> 00:36:56,990
תשומות, כלומר כמה הוספות אקראיות
למבנה הנתונים, מה באמת היא

850
00:36:56,990 --> 00:36:58,580
ההסתברות להתנגשות?

851
00:36:58,580 --> 00:37:01,670
ובכן מתברר, זה בעצם
סופר גבוה.

852
00:37:01,670 --> 00:37:03,850
הרשה לי להכליל את זה
בעיה היא שזה.

853
00:37:03,850 --> 00:37:08,890
>> אז בחדר של n CS50 תלמידים, מה
ההסתברות שלפחות

854
00:37:08,890 --> 00:37:11,010
שני סטודנטים בחדר
יש לו יום ההולדת?

855
00:37:11,010 --> 00:37:13,346
אז מה יש. כמה הונט -

856
00:37:13,346 --> 00:37:16,790
200, 300 אנשים פה וכמה
מאה אנשים בבית היום.

857
00:37:16,790 --> 00:37:20,670
אז אם אתם רוצים לשאול את עצמנו מה
ההסתברות של שני אנשים

858
00:37:20,670 --> 00:37:23,930
בחדר הזה שיש באותו יום הולדת,
אנחנו יכולים להבין את זה.

859
00:37:23,930 --> 00:37:26,250
ואני טוען שלמעשה יש שתיים
אנשים עם אותו יום ההולדת.

860
00:37:26,250 --> 00:37:29,560
>> למשל, האם מישהו
יש יום הולדת היום?

861
00:37:29,560 --> 00:37:31,340
אתמול?

862
00:37:31,340 --> 00:37:32,590
מחר?

863
00:37:32,590 --> 00:37:35,980
בסדר, אז זה מרגיש כאילו אני הולך
צריך לעשות את זה 363 או כך יותר

864
00:37:35,980 --> 00:37:39,500
פעמים כדי להבין באמת
אם אנחנו עושים יש התנגשות.

865
00:37:39,500 --> 00:37:42,350
או שאנחנו פשוט יכולים לעשות את זה מבחינה מתמטית
במקום עייפה

866
00:37:42,350 --> 00:37:43,200
עושה את זה.

867
00:37:43,200 --> 00:37:44,500
ולהציע את הפעולות הבאות.

868
00:37:44,500 --> 00:37:48,740
>> אז אני מציע שאנחנו יכולים לעצב את
הסתברות של שני אנשים שיש

869
00:37:48,740 --> 00:37:55,320
אותו יום הולדת כמו ההסתברות של 1
מינוס הסתברות לאף אחד שיש

870
00:37:55,320 --> 00:37:56,290
באותו יום ההולדת.

871
00:37:56,290 --> 00:37:59,960
אז כדי לקבל את זה, וזה פשוט
דרך מפוארת של כותב את זה, עבור

872
00:37:59,960 --> 00:38:03,090
האדם ראשון בחדר, הוא או היא
יכול להיות כל אחת מאפשרי

873
00:38:03,090 --> 00:38:07,370
ימי הולדת בהנחת 365 ימים בשנה,
עם התנצלות לאנשים עם

874
00:38:07,370 --> 00:38:08,760
יום הולדת פבואר 29.

875
00:38:08,760 --> 00:38:13,470
>> אז האדם הראשון בחדר הזה הוא ללא תשלום
יש כל מספר של ימי הולדת

876
00:38:13,470 --> 00:38:18,280
מתוך 365 האפשרויות, כך
אנחנו נעשה את זה 365 חלקי 365,

877
00:38:18,280 --> 00:38:18,990
שהוא אחד.

878
00:38:18,990 --> 00:38:22,700
האדם הבא בחדר, אם המטרה
הוא להימנע מהתנגשות, יכול רק

879
00:38:22,700 --> 00:38:26,460
יש לו יום ההולדת שלה או על איך
ימים אפשריים רבים ושונים?

880
00:38:26,460 --> 00:38:27,610
364.

881
00:38:27,610 --> 00:38:31,430
אז הקדנציה השנייה בביטוי זה היא
עושה מתמטיקה שבעצם בשבילנו

882
00:38:31,430 --> 00:38:33,460
על ידי הפחתה מיום אחד אפשרי.

883
00:38:33,460 --> 00:38:36,390
ואז למחרת, ביום שלמחרת,
למחרת ירדתי למספר הכולל

884
00:38:36,390 --> 00:38:38,100
של אנשים בחדר.

885
00:38:38,100 --> 00:38:41,290
>> ואם לאחר מכן, אנו רואים, אז מה הוא
ההסתברות לא של כולם שיש

886
00:38:41,290 --> 00:38:45,265
ימי הולדת ייחודיים, אבל שוב מינוס 1
כי, מה שאנחנו מקבלים הוא ביטוי

887
00:38:45,265 --> 00:38:47,810
כי יכול מאוד גחמנות
נראה ככה.

888
00:38:47,810 --> 00:38:50,330
אבל זה יותר מעניין
להסתכל על ראייה.

889
00:38:50,330 --> 00:38:55,120
זהו תרשים שבו על ציר ה-x הוא
מספר האנשים בחדר,

890
00:38:55,120 --> 00:38:56,180
מספר ימי ההולדת.

891
00:38:56,180 --> 00:38:59,840
על ציר ה-Y היא ההסתברות
של התנגשות, שני אנשים

892
00:38:59,840 --> 00:39:01,230
נתקל באותה יום ההולדת.

893
00:39:01,230 --> 00:39:05,020
>> והאוכל המוכן מעקומה זו הוא
כי ברגע שאתה מקבל לחן 40

894
00:39:05,020 --> 00:39:11,110
סטודנטים, אתה למעלה בהסתברות 90%
combinatorically של שתיים

895
00:39:11,110 --> 00:39:13,550
אנשים או יותר שיש
באותו יום ההולדת.

896
00:39:13,550 --> 00:39:18,600
וברגע שאתה מקבל 58 אנשים אוהבים את זה
כמעט 100% מסיכוי שתיים

897
00:39:18,600 --> 00:39:21,310
אנשים בחדר הולכים להיות
אותו יום הולדת, למרות שיש

898
00:39:21,310 --> 00:39:26,650
365 או 366 דליים אפשריים, ו
רק 58 אנשים בחדר.

899
00:39:26,650 --> 00:39:29,900
פשוט סטטיסטי אתה צפוי
לקבל התנגשויות, אשר בקיצור

900
00:39:29,900 --> 00:39:31,810
מניע את הדיון הזה.

901
00:39:31,810 --> 00:39:35,890
כי גם אם אנחנו מקבלים כאן מפוארים, ו
הפעלה שיש רשתות אלה, אנחנו עדיין

902
00:39:35,890 --> 00:39:36,950
הולך להיות התנגשויות.

903
00:39:36,950 --> 00:39:42,710
>> אז זה מעלה את השאלה, מה הוא
עלות של עשיית הוספות ומחיקות

904
00:39:42,710 --> 00:39:44,850
למבנה נתונים כזה?

905
00:39:44,850 --> 00:39:46,630
ובכן תנו לי להציע -

906
00:39:46,630 --> 00:39:51,570
ותנו לי לחזור למסך מעל
כאן - אם יש לנו n אלמנטים ב

907
00:39:51,570 --> 00:39:56,330
רשימה, כך שאם אנחנו מנסים להכניס
אלמנטי N, ושיש לנו

908
00:39:56,330 --> 00:39:58,050
כמה דליי סך הכל?

909
00:39:58,050 --> 00:40:03,450
נניח 31 דליים כלל
במקרה של ימי הולדת.

910
00:40:03,450 --> 00:40:09,240
מה האורך המרבי של אחד
של רשתות אלה פוטנציאלי?

911
00:40:09,240 --> 00:40:12,670
>> אם שוב יש 31 אפשרי
ימי הולדת בחודש נתון.

912
00:40:12,670 --> 00:40:14,580
ואנחנו רק clumping כולם -

913
00:40:14,580 --> 00:40:15,580
למעשה זו דוגמה טיפשית.

914
00:40:15,580 --> 00:40:16,960
בואו לעשות במקום 26.

915
00:40:16,960 --> 00:40:20,890
אז אם באמת יש אנשים ששמות
להתחיל עם עד Z, ​​ובכך נותן

916
00:40:20,890 --> 00:40:22,780
שלנו 26 אפשרויות.

917
00:40:22,780 --> 00:40:25,920
ואנחנו משתמשים במבנה נתונים כמו
אחד שראינו כרגע, לפיה יש לנו

918
00:40:25,920 --> 00:40:30,210
מערך של מצביעים, כל אחד מהם
מצביע על רשימה מקושרת שבי

919
00:40:30,210 --> 00:40:32,360
הרשימה הראשונה היא כולם
עם השם אליס.

920
00:40:32,360 --> 00:40:35,770
הרשימה השנייה היא כל עם
שם החל, החל

921
00:40:35,770 --> 00:40:36,980
עם ב ', וכן הלאה.

922
00:40:36,980 --> 00:40:41,020
>> מה האורך הסביר של כל אחד
רשימות אלה אם נניח נקיים נחמדים

923
00:40:41,020 --> 00:40:45,410
חלוקת שמות עד Z
מעבר לכל מבנה נתונים?

924
00:40:45,410 --> 00:40:50,210
יש אנשי n במבנה נתונים
מחולק ב 26, אם הם יפה

925
00:40:50,210 --> 00:40:52,110
המתפרסים על פני כולה
מבנה הנתונים.

926
00:40:52,110 --> 00:40:54,970
אז אורכו של כל אחד מאלה
שרשרות היא n מחולקת ב -26.

927
00:40:54,970 --> 00:40:57,380
אבל בסימון O גדול, מה זה?

928
00:40:57,380 --> 00:41:00,100

929
00:41:00,100 --> 00:41:02,440
מה זה באמת?

930
00:41:02,440 --> 00:41:04,150
אז זה באמת רק n, נכון?

931
00:41:04,150 --> 00:41:06,620
בגלל שאמרנו בעבר,
איכס שאתה מחלק על ידי 26.

932
00:41:06,620 --> 00:41:08,710
כן, במציאות זה יותר מהר.

933
00:41:08,710 --> 00:41:12,720
אבל בתאוריה, זה לא מהותי
כל מה שיותר מהר.

934
00:41:12,720 --> 00:41:16,040
>> אז נראים שאנחנו לא להיות כל כך הרבה
קרוב יותר לגביע קדוש זה.

935
00:41:16,040 --> 00:41:17,750
למעשה, זה בדיוק הזמן ליניארי.

936
00:41:17,750 --> 00:41:20,790
לעזאזל, בשלב זה, למה לא אנחנו
פשוט להשתמש ברשימה מקושרת אחד ענק?

937
00:41:20,790 --> 00:41:23,510
למה שלא פשוט לנו להשתמש באחד ענק
מערך כדי לאחסן את שמות

938
00:41:23,510 --> 00:41:25,010
כולם בחדר?

939
00:41:25,010 --> 00:41:28,280
ובכן, האם יש עדיין משהו
משכנע על שולחן חשיש?

940
00:41:28,280 --> 00:41:30,810
האם יש עדיין משהו משכנע
על מבנה הנתונים

941
00:41:30,810 --> 00:41:33,940
שנראה כמו זה?

942
00:41:33,940 --> 00:41:35,182
זה.

943
00:41:35,182 --> 00:41:37,050
>> תלמיד: [לא ברור].

944
00:41:37,050 --> 00:41:39,840
>> רמקול 1: נכון, ושוב אם זה רק
אלגוריתם זמן ליניארי, ו

945
00:41:39,840 --> 00:41:42,780
מבנה נתוני זמן ליניארי, למה שאני לא
רק לאחסן את שמו של כל אחד בגדול

946
00:41:42,780 --> 00:41:44,210
מערך, או ברשימה מקושרת גדולה?

947
00:41:44,210 --> 00:41:47,010
ותפסיק לעשות כל כך הרבה יותר קשה CS
ממה שהוא צריך להיות?

948
00:41:47,010 --> 00:41:49,600

949
00:41:49,600 --> 00:41:53,190
מהו משכנע על זה, אפילו
למרות שגרדתי אותו החוצה?

950
00:41:53,190 --> 00:41:54,930
>> תלמיד: [לא ברור].

951
00:41:54,930 --> 00:41:57,040
>> רמקול 1: הוספות לא?

952
00:41:57,040 --> 00:41:58,140
יקר יותר.

953
00:41:58,140 --> 00:42:03,390
אז הוספות עלולות עדיין
להיות זמן קבוע, גם אם הנתונים שלך

954
00:42:03,390 --> 00:42:07,910
מבנה נראה כך, מערך של
מצביעים, כל אחד מהם מצביעים על

955
00:42:07,910 --> 00:42:09,550
פוטנציאל רשימה מקושרת.

956
00:42:09,550 --> 00:42:15,220
איך אתה יכול להשיג מתמיד
החדרת זמן של שמות?

957
00:42:15,220 --> 00:42:16,280
לתקוע אותו בחזית, נכון?

958
00:42:16,280 --> 00:42:19,290
>> אם אנחנו מקריבים ממטרת עיצוב
קודם לכן, שבו אנו רוצים לשמור

959
00:42:19,290 --> 00:42:22,650
שמו של כל אחד, למשל, מיון,
או את כל המספרים מסודרים על במה,

960
00:42:22,650 --> 00:42:25,020
נניח אנו
רשימה מקושרת לא ממוינת.

961
00:42:25,020 --> 00:42:29,960
זה עולה לנו רק שלב אחד או שתיים,
כמו במקרה של בן ובריאן

962
00:42:29,960 --> 00:42:32,750
מוקדם יותר, כדי להוסיף אלמנט ב
תחילתה של הרשימה.

963
00:42:32,750 --> 00:42:36,090
אז אם לא אכפת לנו על כל מיון
מהשמות שמתחילים בכל או

964
00:42:36,090 --> 00:42:39,660
השמות שמתחילים בארוחת בוקר, אנחנו עדיין יכולים
להשיג החדרת זמן קבועה.

965
00:42:39,660 --> 00:42:43,900
עכשיו מחפש את אליס או בוב או כל שם
באופן כללי יותר הוא עדיין מה?

966
00:42:43,900 --> 00:42:48,100
זה גדול O של n מחולק ב 26, ב
מקרה אידיאלי שבו כולם באופן אחיד

967
00:42:48,100 --> 00:42:51,190
להפיץ, שבו יש כמה של
כמו שיש נחירות בלילה, שהוא כנראה

968
00:42:51,190 --> 00:42:52,220
לא מציאותי.

969
00:42:52,220 --> 00:42:53,880
אבל זה עדיין ליניארי.

970
00:42:53,880 --> 00:42:57,120
>> אבל כאן, אנחנו חוזרים לנקודה
של סימון אסימפטוטי להיות

971
00:42:57,120 --> 00:42:58,600
תיאורטית נכון.

972
00:42:58,600 --> 00:43:02,960
אבל בעולם האמיתי, אם אני טוען כי
התכנית שלי יכולה לעשות משהו 26 פעמים

973
00:43:02,960 --> 00:43:06,210
מהר יותר משלך, התכנית שלהם
אתה הולך למעדיף להשתמש?

974
00:43:06,210 --> 00:43:09,660
שלך או שלי, אשר
הוא 26 פעמים מהר יותר?

975
00:43:09,660 --> 00:43:14,320
באופן מעשי, האדם שהוא 26
פעמים מהר יותר, גם אם באופן תיאורטי

976
00:43:14,320 --> 00:43:18,790
האלגוריתמים שלנו יפעלו באותו
ריצת אסימפטוטי זמן.

977
00:43:18,790 --> 00:43:20,940
>> הרשה לי להציע שונה
פתרון לגמרי.

978
00:43:20,940 --> 00:43:24,380
ואם זה לא לפוצץ את דעתך,
אנחנו מתוך מבני נתונים.

979
00:43:24,380 --> 00:43:27,420
אז זהו זה trie -

980
00:43:27,420 --> 00:43:28,520
מין שם טיפשי.

981
00:43:28,520 --> 00:43:32,880
זה בא מאחזורים, והמילה
מאוית trie, T-R-i-E, בגלל

982
00:43:32,880 --> 00:43:34,450
אחזור כמובן נשמע כמו trie.

983
00:43:34,450 --> 00:43:36,580
אבל זה ההיסטוריה
של המילה trie.

984
00:43:36,580 --> 00:43:40,980
>> אז trie הוא אכן סוג של עץ,
וזה גם מחזה על מילה הזאת.

985
00:43:40,980 --> 00:43:46,330
ולמרות שאתה לא ממש יכול לראות את זה
עם הדמיה זו, הוא trie

986
00:43:46,330 --> 00:43:50,790
בנוי עץ, כמו עץ ​​משפחה עם
אב קדמון אחד בראש והרבה

987
00:43:50,790 --> 00:43:54,530
של נכדים ונינים
כמו עלים בחלקו התחתון.

988
00:43:54,530 --> 00:43:58,100
אבל כל צומת בtrie היא מערך.

989
00:43:58,100 --> 00:44:00,680
וזה במערך - ובואו
פשטנות יתרה לרגע - זה

990
00:44:00,680 --> 00:44:04,600
מערך, במקרה הזה, של גודל 26, שבו
כל צומת שוב היא מערך בגודל

991
00:44:04,600 --> 00:44:09,000
26, שבו אלמנט האפס שב
מערך מייצג, והאחרון

992
00:44:09,000 --> 00:44:11,810
בכל אלמנט כזה
מערך מייצג ז'

993
00:44:11,810 --> 00:44:15,520
>> אז אני מציע, אם כן, שנתונים אלה
מבנה, המכונה trie, יכול להיות

994
00:44:15,520 --> 00:44:17,600
משמש גם לאחסון דברים.

995
00:44:17,600 --> 00:44:21,740
ראינו את זה לפני רגע איך אנחנו יכולים לאחסן
מילים, או במקרה השמות הזה, ואנחנו

996
00:44:21,740 --> 00:44:25,440
ראה קודם איך אנחנו יכולים לאחסן מספרים,
אבל אם אנו מתמקדים בשמות או מחרוזות

997
00:44:25,440 --> 00:44:27,460
כאן, שים לב למה זה מעניין.

998
00:44:27,460 --> 00:44:32,210
אני טוען שאת השם מקסוול הוא
חלק פנימי של מבנה נתונים זה.

999
00:44:32,210 --> 00:44:33,730
איפה אתה רואה את מקסוול?

1000
00:44:33,730 --> 00:44:35,140
>> תלמיד: [לא ברור].

1001
00:44:35,140 --> 00:44:36,240
>> רמקול 1: בצד השמאל.

1002
00:44:36,240 --> 00:44:39,910
אז מה מעניין עם נתונים אלה
מבנה הוא לא חנות

1003
00:44:39,910 --> 00:44:46,200
מחרוזת M-X--W-E-L-L קו נטוי אפס, כל
סמיכות, מה שאתה עושה במקום

1004
00:44:46,200 --> 00:44:46,890
עוקב אחרי.

1005
00:44:46,890 --> 00:44:50,510
אם זה trie כמו מבנה נתונים,
כל אחד מצומת שלהם הוא שוב מערך,

1006
00:44:50,510 --> 00:44:54,650
ואתה רוצה לאחסן את מקסוול, אתה ראשון
מדד וכן הצומת של השורש, ולכן

1007
00:44:54,650 --> 00:44:57,810
לדבר, הצומת העליונה ביותר,
במיקום M, נכון, ולכן

1008
00:44:57,810 --> 00:44:59,160
בערך באמצע.

1009
00:44:59,160 --> 00:45:03,740
ואז משם, אתה מבין
מצביע לבלוטות ילד, כביכול.

1010
00:45:03,740 --> 00:45:06,150
אז במובן עץ המשפחה,
אתה מבין את זה כלפי מטה.

1011
00:45:06,150 --> 00:45:09,030
וזה יוביל אותך לצומת אחרת
בצד השמאל יש, שהוא

1012
00:45:09,030 --> 00:45:10,540
רק עוד מערך.

1013
00:45:10,540 --> 00:45:14,710
>> ואז אם אתה רוצה לאחסן את מקסוול,
אתה מוצא את המצביע המייצג

1014
00:45:14,710 --> 00:45:16,430
, שהוא זה כאן.

1015
00:45:16,430 --> 00:45:17,840
ואז אתה הולך לצומת הבאה.

1016
00:45:17,840 --> 00:45:20,100
ושים לב - זו הסיבה של התמונה
קצת מטעה -

1017
00:45:20,100 --> 00:45:21,990
הצומת הזה נראה סופר זעיר.

1018
00:45:21,990 --> 00:45:26,050
אבל לזכותו של זה הוא Y ו-Z
זה פשוט המחבר קטום

1019
00:45:26,050 --> 00:45:27,630
תמונה, כך שאתה בעצם
רואה את הדברים.

1020
00:45:27,630 --> 00:45:30,400
אחרת התמונה הזאת
יהיה הרבה מאוד רחב.

1021
00:45:30,400 --> 00:45:36,180
אז עכשיו אתה מדד למיקום X, ולאחר מכן
W, E ואז, אז L, ואז ל 'אז מה

1022
00:45:36,180 --> 00:45:37,380
סקרנות זו?

1023
00:45:37,380 --> 00:45:41,250
>> ובכן, אם אנחנו משתמשים בסוג זה של חדש
לקחת על עצמו כיצד לאחסן במחרוזת

1024
00:45:41,250 --> 00:45:44,500
מבנה הנתונים, אתה עדיין צריך
למעשה לבדוק את הנתונים ב

1025
00:45:44,500 --> 00:45:47,250
מבנה שמילה מסתיימת כאן.

1026
00:45:47,250 --> 00:45:50,830
במילים אחרות, כל אחד מצומת הללו
איכשהו יש לזכור שאנחנו

1027
00:45:50,830 --> 00:45:53,500
למעשה אחרי כל המצביעים האלה
והם קצת עוזבים

1028
00:45:53,500 --> 00:45:58,370
פירור לחם בתחתית של זה כאן
מבנה כדי לציין M-X--W-E-L-L הוא

1029
00:45:58,370 --> 00:46:00,230
אכן במבנה נתונים זה.

1030
00:46:00,230 --> 00:46:02,040
>> אז אנחנו יכולים לעשות את זה באופן הבא.

1031
00:46:02,040 --> 00:46:06,810
כל אחד מצומת בתמונה אנחנו פשוט
יש ראיתי אחד, מערך של גודל 27.

1032
00:46:06,810 --> 00:46:10,550
וזה עכשיו 27, כי בעמ להגדיר שש,
אנחנו באמת אתן לך גרש,

1033
00:46:10,550 --> 00:46:13,590
כך אנחנו יכולים להיות שמות כמו אוריילי
ואחרים עם גרשיים.

1034
00:46:13,590 --> 00:46:14,820
אבל אותו רעיון.

1035
00:46:14,820 --> 00:46:17,710
כל אחד מאותם גורמים ב
נקודות מערך למבנה

1036
00:46:17,710 --> 00:46:19,320
צומת, כל כך פשוט צומת.

1037
00:46:19,320 --> 00:46:21,430
אז זה מאוד מזכיר
הרשימה המקושרת שלנו.

1038
00:46:21,430 --> 00:46:24,550
>> ואז יש לי בוליאני, שבו אני
קורא מילה, שרק הולך להיות

1039
00:46:24,550 --> 00:46:29,120
נכון אם מילה מסתיימת בזה
צומת בעץ.

1040
00:46:29,120 --> 00:46:32,870
זה למעשה מייצג את המעט
משולש שראינו לפני רגע.

1041
00:46:32,870 --> 00:46:37,190
אז אם מילה מסתיימת בצומת שב
העץ, שהמילה שדה יהיה נכון,

1042
00:46:37,190 --> 00:46:41,990
אשר בודק את מושגית, או
אנחנו ציור המשולש הזה, כן יש

1043
00:46:41,990 --> 00:46:44,080
הוא מילה כאן.

1044
00:46:44,080 --> 00:46:45,120
>> אז זה trie.

1045
00:46:45,120 --> 00:46:48,540
ועכשיו השאלה היא, מה
הוא פועל זמן?

1046
00:46:48,540 --> 00:46:49,930
האם זה גדול O של n?

1047
00:46:49,930 --> 00:46:51,410
האם זה משהו אחר?

1048
00:46:51,410 --> 00:46:57,330
ובכן, אם יש לך n שמות בנתונים אלה
מבנה, מקסוול להיות רק אחד

1049
00:46:57,330 --> 00:47:02,330
שלהם, מהו זמן הריצה של
הוספה או מציאת מקסוול?

1050
00:47:02,330 --> 00:47:06,230

1051
00:47:06,230 --> 00:47:09,050
מה זמן הריצה
החדרה של מקסוול?

1052
00:47:09,050 --> 00:47:11,740
אם יש שמות אחרים n
כבר בטבלה?

1053
00:47:11,740 --> 00:47:12,507
כן?

1054
00:47:12,507 --> 00:47:15,429
>> תלמיד: [לא ברור].

1055
00:47:15,429 --> 00:47:17,550
>> 1 רמקול: כן, זה האורך
משם, נכון?

1056
00:47:17,550 --> 00:47:24,420
אז M-X--W-e-L-L אז זה מרגיש ככה
אלגוריתם הוא O הגדול של שבע.

1057
00:47:24,420 --> 00:47:26,580
עכשיו, כמובן, את שמו
משתנה באורך.

1058
00:47:26,580 --> 00:47:27,380
אולי זה שם קצר.

1059
00:47:27,380 --> 00:47:28,600
אולי זה שם ארוך יותר.

1060
00:47:28,600 --> 00:47:33,390
אבל מה שמפתח כאן הוא כי
זה מספר קבוע.

1061
00:47:33,390 --> 00:47:36,810
ואולי זה לא באמת קבוע,
אבל אלוהים, אם באופן מעשי, ב

1062
00:47:36,810 --> 00:47:41,570
מילון, יש כנראה איזה גבול
על מספר המכתבים ב

1063
00:47:41,570 --> 00:47:43,820
שמו של האדם במדינה מסוימת.

1064
00:47:43,820 --> 00:47:46,940
>> וכך אנו יכולים להניח כי
הערך הוא קבוע.

1065
00:47:46,940 --> 00:47:47,750
אני לא יודע מה זה.

1066
00:47:47,750 --> 00:47:50,440
זה כנראה גדול יותר
אנחנו חושבים שזה הוא.

1067
00:47:50,440 --> 00:47:52,720
כי תמיד יש איזו פינה
מקרה עם שם ארוך מטורף.

1068
00:47:52,720 --> 00:47:56,360
אז בואו נקראים לזה K, אבל זה עדיין
קבועה יש להניח, כי בכל

1069
00:47:56,360 --> 00:48:00,190
שם בעולם, לפחות ב
מדינה מסוימת, היא שאורך או

1070
00:48:00,190 --> 00:48:01,780
קצר יותר, כך שזה קבוע.

1071
00:48:01,780 --> 00:48:04,490
אבל כאשר אנחנו אומרים משהו הוא גדול
O של ערך קבוע, מה זה

1072
00:48:04,490 --> 00:48:07,760
באמת שווה?

1073
00:48:07,760 --> 00:48:10,420
זה באמת אותו הדבר
כאומר זמן קבוע.

1074
00:48:10,420 --> 00:48:11,530
>> עכשיו אנחנו סוג של רמאות, נכון?

1075
00:48:11,530 --> 00:48:15,340
אנחנו סוג של מינוף איזו תאוריה
לכאן כדי לומר שכן, סדר k הוא

1076
00:48:15,340 --> 00:48:17,450
באמת רק סדר אחד,
וזה זמן קבוע.

1077
00:48:17,450 --> 00:48:18,200
אבל זה באמת.

1078
00:48:18,200 --> 00:48:22,550
בגלל תובנה המפתח כאן היא כי
אם יש לנו n שמות כבר בזה

1079
00:48:22,550 --> 00:48:26,010
מבנה הנתונים, ואנחנו הוספת מקסוול,
היא כמות הזמן שלוקח לנו

1080
00:48:26,010 --> 00:48:29,530
הכנס מקסוול בכלל המושפע
על ידי כמה אנשים אחרים

1081
00:48:29,530 --> 00:48:31,100
נמצאים במבנה נתונים?

1082
00:48:31,100 --> 00:48:31,670
לא נראה שיהיה.

1083
00:48:31,670 --> 00:48:36,280
אם היה לי מליארד אלמנטים נוספים לזה
trie, ולאחר מכן להוסיף מקסוול, הוא

1084
00:48:36,280 --> 00:48:38,650
הוא בכלל השפיע?

1085
00:48:38,650 --> 00:48:39,050
לא.

1086
00:48:39,050 --> 00:48:42,950
וזה שונה מכל היום של הנתונים
מבנים שראינו עד כה, שבו

1087
00:48:42,950 --> 00:48:46,820
זמן הריצה של האלגוריתם שלך הוא
עצמאי לחלוטין של כמה

1088
00:48:46,820 --> 00:48:51,430
דברים הם או היא לא כבר
במבנה נתונים זה.

1089
00:48:51,430 --> 00:48:54,650
>> וכך, עם זה מקנה לך כרגע הוא
הזדמנות עבור p שישה סט, שיהיה

1090
00:48:54,650 --> 00:48:58,310
שוב כרוך ביישום שלך
בודק איות, קריאה ב150,000

1091
00:48:58,310 --> 00:49:01,050
מילים, איך הכי טוב לאחסן כי
לא בהכרח ברור.

1092
00:49:01,050 --> 00:49:04,030
ואף על פי שאפיתי למצוא
הגביע הקדוש, אני לא

1093
00:49:04,030 --> 00:49:05,330
טוען שהוא trie.

1094
00:49:05,330 --> 00:49:09,810
למעשה, שולחן חשיש עשוי היטב
להוכיח להיות הרבה יותר יעיל.

1095
00:49:09,810 --> 00:49:10,830
אבל אלה הם רק -

1096
00:49:10,830 --> 00:49:14,620
זה רק אחד מהחלטות העיצוב
אתה תצטרך לעשות.

1097
00:49:14,620 --> 00:49:18,920
>> אבל בסגירת בואו ניקח 50 או משהו כזה
שניות כדי להציץ מה נמצא

1098
00:49:18,920 --> 00:49:22,190
השבוע הבא קדימה ומעבר אנו מעבר
משורת הפקודה זה

1099
00:49:22,190 --> 00:49:26,220
עולם אם C תוכניות לדברי אינטרנט
בהתבסס ושפות כמו PHP ו

1100
00:49:26,220 --> 00:49:30,350
JavaScript והאינטרנט עצמו,
פרוטוקולים כמו HTTP, שיש לך

1101
00:49:30,350 --> 00:49:32,870
מובן מאליו במשך שנים
עכשיו, וכל הקלדה ביותר

1102
00:49:32,870 --> 00:49:34,440
היום, אולי, או ראו.

1103
00:49:34,440 --> 00:49:37,420
ואנו מתחילים לקלף
שכבות של מה באינטרנט.

1104
00:49:37,420 --> 00:49:40,650
ומהו הקוד ש
עומד בבסיס הכלים של היום.

1105
00:49:40,650 --> 00:49:43,230
אז 50 שניות של טיזר זה כאן.

1106
00:49:43,230 --> 00:49:46,570
אני נותן לך לוחמים של הרשת.

1107
00:49:46,570 --> 00:49:51,370
>> [השמעת וידאו]

1108
00:49:51,370 --> 00:49:56,764
>> -הוא בא עם מסר.

1109
00:49:56,764 --> 00:50:00,687
עם פרוטוקול כולו שלו.

1110
00:50:00,687 --> 00:50:13,370

1111
00:50:13,370 --> 00:50:19,780
הוא הגיע לעולם של חומות אש אכזריות,
אדישים, נתבים וסכנות כה

1112
00:50:19,780 --> 00:50:22,600
יותר גרוע ממוות.

1113
00:50:22,600 --> 00:50:23,590
הוא מהיר.

1114
00:50:23,590 --> 00:50:25,300
הוא חזק.

1115
00:50:25,300 --> 00:50:27,700
הוא TCPIP.

1116
00:50:27,700 --> 00:50:30,420
ויש לו את הכתובת שלך.

1117
00:50:30,420 --> 00:50:32,920

1118
00:50:32,920 --> 00:50:34,590
לוחמים של הרשת.

1119
00:50:34,590 --> 00:50:35,290
>> [השמעת וידאו הסוף]

1120
00:50:35,290 --> 00:50:38,070
>> 1 רמקול: ככה האינטרנט
יפעל החל מהשבוע הבא.

1121
00:50:38,070 --> 00:50:40,406