1
00:00:00,000 --> 00:00:07,700

2
00:00:07,700 --> 00:00:10,890
>> קווין שמידט: לעתים, בעת בנייה
תכנית, ייתכן שתרצי לנצל

3
00:00:10,890 --> 00:00:13,190
מבנה הנתונים המכונה במילון.

4
00:00:13,190 --> 00:00:17,960
מפתחות מפות מילון, שהם
בדרך כלל מחרוזות, לערכים, ints,

5
00:00:17,960 --> 00:00:21,900
תווים, מצביע לאובייקט כלשהו,
מה שאנחנו רוצים.

6
00:00:21,900 --> 00:00:26,510
זה בדיוק כמו במילונים רגילים
מילות המפה שדרך הגדרות.

7
00:00:26,510 --> 00:00:29,440
>> מילונים לספק לנו את
יכולת לאחסן מידע

8
00:00:29,440 --> 00:00:32,750
קשור עם משהו
ולבדוק את זה מאוחר יותר.

9
00:00:32,750 --> 00:00:36,620
אז איך אנחנו באמת ליישם
מילון, למשל, קוד C שאנחנו יכולים

10
00:00:36,620 --> 00:00:38,460
להשתמש באחת מהתוכניות שלנו?

11
00:00:38,460 --> 00:00:41,790
ובכן, יש הרבה דרכים שבן
אנחנו יכולים ליישם את מילון.

12
00:00:41,790 --> 00:00:45,930
>> עבור אחד, אנחנו יכולים להשתמש במערך שאנחנו
באופן דינמי מחדש את גודל או שאנחנו יכולים להשתמש

13
00:00:45,930 --> 00:00:49,150
רשימה מקושרת, טבלת גיבוב
או עץ בינארי.

14
00:00:49,150 --> 00:00:52,250
אבל כל מה שאנחנו בוחרים, אנחנו צריכים
להיות זהיר של היעילות ו

15
00:00:52,250 --> 00:00:54,300
ביצועים של היישום.

16
00:00:54,300 --> 00:00:57,930
אנחנו צריכים לחשוב על האלגוריתם המשמש
כדי להוסיף ולבדוק את הפריטים לתוך

17
00:00:57,930 --> 00:00:59,120
מבנה הנתונים שלנו.

18
00:00:59,120 --> 00:01:03,060
>> לעת עתה, הבה יניחו לנו כי
רוצה להשתמש במחרוזות כמפתחות.

19
00:01:03,060 --> 00:01:07,290
בואו נדבר על אפשרות אחת,
מבנה נתונים הנקרא הגיבורים.

20
00:01:07,290 --> 00:01:11,210
אז הנה ייצוג חזותי
של הגיבורים.

21
00:01:11,210 --> 00:01:14,590
>> כמו בתמונה מרמזת, הגיבורים
הוא מבנה נתונים עץ עם

22
00:01:14,590 --> 00:01:16,050
צמתים מקושרים יחד.

23
00:01:16,050 --> 00:01:19,420
אנו רואים שיש בבירור שורש
צומת עם כמה קישורים להארכה

24
00:01:19,420 --> 00:01:20,500
צמתים אחרים.

25
00:01:20,500 --> 00:01:23,040
אבל מה משמעות של כל צומת מורכב?

26
00:01:23,040 --> 00:01:26,700
אם נניח שאנחנו אחסון מפתחות
עם דמויות האלפביתי בלבד, ו

27
00:01:26,700 --> 00:01:30,150
לא אכפת לנו על היוון,
הנה הגדרה של צומת ש

28
00:01:30,150 --> 00:01:31,100
יספיק.

29
00:01:31,100 --> 00:01:34,130
>> אובייקט שסוגיו הוא struct
יש צומת שני חלקים

30
00:01:34,130 --> 00:01:35,740
קרא נתונים וילדים.

31
00:01:35,740 --> 00:01:39,200
אנחנו כבר עזבנו את חלק הנתונים כתגובה
כדי להיות מוחלף על ידי רכיב

32
00:01:39,200 --> 00:01:43,190
הכרזה כאשר צומת struct היא
שולב בתכנית C.

33
00:01:43,190 --> 00:01:47,040
חלק הנתונים של צומת עלול להיות
ערך בוליאני כדי לציין אם או

34
00:01:47,040 --> 00:01:51,160
לא את הצומת מייצגת את ההשלמה
של מפתח מילון או שזה יכול להיות

35
00:01:51,160 --> 00:01:54,240
מחרוזת המייצגת את ההגדרה
של מילה במילון.

36
00:01:54,240 --> 00:01:58,870
>> אנו נשתמש בפרצוף מחייך כדי לציין
כאשר הנתונים קיים בצומת.

37
00:01:58,870 --> 00:02:02,310
ישנן 26 אלמנטים בנו
מערך ילדים, מדד אחד

38
00:02:02,310 --> 00:02:03,690
לכל תו האלפביתי.

39
00:02:03,690 --> 00:02:06,570
נצטרך לראות את המשמעות
מרגע זה.

40
00:02:06,570 --> 00:02:10,759
>> בואו לקבל מבט קרוב יותר של צומת השורש
בדיאגרמה שלנו, שבו יש אין נתונים

41
00:02:10,759 --> 00:02:14,740
הקשורים אליו, כפי שצוין על ידי
העדרו של פרצוף המחייך ב

42
00:02:14,740 --> 00:02:16,110
חלק הנתונים.

43
00:02:16,110 --> 00:02:19,910
החיצים המשתרעים מהחלקים
ילדי המערך מייצגים הלא צומת

44
00:02:19,910 --> 00:02:21,640
מצביעים לצומת אחרים.

45
00:02:21,640 --> 00:02:25,500
לדוגמא, החץ המשתרעת
האלמנט השני של ילדים

46
00:02:25,500 --> 00:02:28,400
מייצג את האות B
במפתח במילון.

47
00:02:28,400 --> 00:02:31,920
ובתרשים הגדול יותר
אנחנו מתייגים אותו עם B.

48
00:02:31,920 --> 00:02:35,810
>> שים לב כי בתרשים הגדול יותר, כאשר אנו
לצייר מצביע לצומת אחרת, זה

49
00:02:35,810 --> 00:02:39,100
לא משנה איפה ראש החץ
עונה שצומת אחרת.

50
00:02:39,100 --> 00:02:43,850
הגיבורים מילון מדגם שלנו מכילים
שתי מילות, ושזום.

51
00:02:43,850 --> 00:02:47,040
בואו ללכת דרך דוגמא
מחפש את הנתונים למפתח.

52
00:02:47,040 --> 00:02:50,800
>> נניח שאנחנו רוצים להסתכל למעלה
מתאים ערך עבור האמבטיה המפתח.

53
00:02:50,800 --> 00:02:53,610
אנו נתחיל את המראה שלנו
בצומת השורש.

54
00:02:53,610 --> 00:02:57,870
ואז ניקח את האות הראשונה שלנו
מפתח, ב ', ולמצוא את מתאים

55
00:02:57,870 --> 00:03:00,020
לזהות במערך הילדים שלנו.

56
00:03:00,020 --> 00:03:04,490
שים לב שיש בדיוק 26 נקודות
במערך, אחד עבור כל אות של

57
00:03:04,490 --> 00:03:05,330
האלפבית.

58
00:03:05,330 --> 00:03:08,800
ויהיה לנו את הנקודות מייצגות את
אותיות האלף בית לפי סדר.

59
00:03:08,800 --> 00:03:13,960
>> אנחנו נסתכל על המדד השני לאחר מכן,
מדד אחד, עבור ב 'באופן כללי, אם אנחנו

60
00:03:13,960 --> 00:03:17,990
יש לי כמה אנחנו C התו האלפביתי
אפשר לקבוע את הנקודה המקבילה

61
00:03:17,990 --> 00:03:21,520
במערך הילדים באמצעות
חישוב כזה.

62
00:03:21,520 --> 00:03:25,140
היינו יכולים להשתמש בילדים גדולים יותר
מערך אם אנחנו רוצים להציע מבט מ

63
00:03:25,140 --> 00:03:28,380
מפתחות עם מגוון רחב יותר של תווים,
כמו כל

64
00:03:28,380 --> 00:03:29,880
תווי ASCII מוגדרים.

65
00:03:29,880 --> 00:03:32,630
>> במקרה זה, את המצביע
במערך הילדים שלנו ב

66
00:03:32,630 --> 00:03:34,320
מדד אחד הוא לא ריק.

67
00:03:34,320 --> 00:03:36,600
אז אנחנו נמשיך לחפש
את האמבטיה המרכזית.

68
00:03:36,600 --> 00:03:40,130
אם אי פעם נתקלו במצביע null
במקום הנכון בילדים

69
00:03:40,130 --> 00:03:43,230
מערך בזמן שאנחנו חציתי את צמתים,
אז אנחנו נצטרך להגיד לנו ש

70
00:03:43,230 --> 00:03:45,630
לא הצליח למצוא שום דבר לאותו מקש.

71
00:03:45,630 --> 00:03:49,370
>> עכשיו, ניקח את המכתב השני של
המפתח שלנו, ותמשיך הבא

72
00:03:49,370 --> 00:03:52,400
מצביעים בדרך זו עד ש
להגיע לסוף של המפתח שלנו.

73
00:03:52,400 --> 00:03:56,530
אם נגיע לסוף את המפתח ללא
להכות כל מבוי סתום, מצביעי null,

74
00:03:56,530 --> 00:03:59,730
כמו במקרה כאן, אז אנחנו היחידים
צריך לבדוק עוד דבר אחד.

75
00:03:59,730 --> 00:04:02,110
האם מפתח זה בעצם
במילון?

76
00:04:02,110 --> 00:04:07,660
>> אם כך, אנחנו צריכים למצוא ערך, גם
סמיילי אייקון פרצוף בדיאגרמה שלנו שבו

77
00:04:07,660 --> 00:04:08,750
המילה מסתיימת.

78
00:04:08,750 --> 00:04:12,270
אם יש משהו אחר מאוחסן עם
את הנתונים, אז אנחנו יכולים להחזיר אותו.

79
00:04:12,270 --> 00:04:16,500
לדוגמא, גן החיות המפתח היא לא ב
מילון, למרות שיש לנו יכולים

80
00:04:16,500 --> 00:04:19,810
הגיע לסוף מפתח זה מבלי
להכות מצביע null, בזמן שאנחנו

81
00:04:19,810 --> 00:04:21,089
איטרציות בגיבורים.

82
00:04:21,089 --> 00:04:25,436
>> אם ניסינו לחפש את האמבטיה המרכזית,
שני לאינדקס של המערך שעברה את הצומת,

83
00:04:25,436 --> 00:04:28,750
מקביל לאות H, הייתי
קיימתי מצביע null.

84
00:04:28,750 --> 00:04:31,120
אז אמבטיה היא לא נמצאת במילון.

85
00:04:31,120 --> 00:04:34,800
וכך הגיבורים הוא ייחודיים בכך שהמפתחות
אף פעם לא מאוחסנים באופן מפורש ב

86
00:04:34,800 --> 00:04:36,650
מבנה הנתונים.

87
00:04:36,650 --> 00:04:38,810
אז איך אנחנו מכניסים משהו
לגיבורים?

88
00:04:38,810 --> 00:04:41,780
>> בואו להכניס את המפתח
גן חיות לגיבורים שלנו.

89
00:04:41,780 --> 00:04:46,120
זכור כי הסמיילי בצומת
יכול מתאימות בקוד לפשוט

90
00:04:46,120 --> 00:04:50,170
ערך בוליאני כדי לציין שגן חיות
הוא במילון או שזה יכול

91
00:04:50,170 --> 00:04:53,710
מתאימות לקבלת מידע נוספת שאנו
רצון לקשר עם גן החיות המרכזיות,

92
00:04:53,710 --> 00:04:56,860
כמו ההגדרה של
מילה או משהו אחר.

93
00:04:56,860 --> 00:05:00,350
במובנים מסוימים, התהליך להוספה
משהו לגיבורים דומה ל

94
00:05:00,350 --> 00:05:02,060
מחפש משהו בגיבורים.

95
00:05:02,060 --> 00:05:05,720
>> נתחיל עם צומת השורש שוב,
המצביעים הבאים המתאימים

96
00:05:05,720 --> 00:05:07,990
מכתבי המפתח שלנו.

97
00:05:07,990 --> 00:05:11,310
למזלנו, היינו יכול לעקוב אחרי מצביעים
כל הדרך עד שהגענו

98
00:05:11,310 --> 00:05:12,770
הסוף של המפתח.

99
00:05:12,770 --> 00:05:16,480
מאז גן החיות היא קידומת של המילה
זום, שהוא חבר

100
00:05:16,480 --> 00:05:19,440
מילון, אנחנו לא צריכים
להקצות כל צמתים חדשים.

101
00:05:19,440 --> 00:05:23,140
>> אנחנו יכולים לשנות את הצומת כדי לציין כי
דרכן של הדמויות מובילות ל

102
00:05:23,140 --> 00:05:25,360
הוא מייצג מפתח במילון שלנו.

103
00:05:25,360 --> 00:05:28,630
עכשיו, בואו ננסה להכניס את
BATH מפתח לגיבורים.

104
00:05:28,630 --> 00:05:32,260
נתחיל בצומת השורש
ועיקבו אחרי מצביעים שוב.

105
00:05:32,260 --> 00:05:35,620
אבל במצב הזה, אנחנו פגעו מתים
בסופו לפני שאנחנו מסוגלים להגיע ל

106
00:05:35,620 --> 00:05:36,940
הסוף של המפתח.

107
00:05:36,940 --> 00:05:40,980
עכשיו, נצטרך להקצות חלק חדש
בלוטות יצטרכו להקצות חדש אחד

108
00:05:40,980 --> 00:05:43,660
צומת לכל שנותר
מכתב של המפתח שלנו.

109
00:05:43,660 --> 00:05:46,740
>> במקרה זה, אנחנו רק צריכים
להקצות צומת אחד חדשה.

110
00:05:46,740 --> 00:05:50,590
ואז נצטרך לעשות את מדד H
התייחסות צומת חדשה זה.

111
00:05:50,590 --> 00:05:54,070
שוב, אנו יכולים לשנות את הצומת כדי
מצביע על כך שהדרך של תווים

112
00:05:54,070 --> 00:05:57,120
שמוביל אליו מייצג
מפתח במילון שלנו.

113
00:05:57,120 --> 00:06:00,730
בואו סיבה על אסימפטוטי
מורכבות של התהליכים שלנו לאלה

114
00:06:00,730 --> 00:06:02,110
שני ניתוחים.

115
00:06:02,110 --> 00:06:06,420
>> אנו שמים לב כי בשני המקרים המספר
של השלבים האלגוריתם שלנו לקח היה

116
00:06:06,420 --> 00:06:09,470
ביחס ישר למספר
אותיות במילות מפתח.

117
00:06:09,470 --> 00:06:10,220
זה נכון.

118
00:06:10,220 --> 00:06:13,470
כאשר אתה רוצה לחפש מילה ב
הגיבורים אתה רק צריך לחזר דרך

119
00:06:13,470 --> 00:06:17,100
המכתבים האחד אחד עד שאתה או
להגיע לסוף של המילה או

120
00:06:17,100 --> 00:06:19,060
הגיע למבוי סתום בגיבורים.

121
00:06:19,060 --> 00:06:22,470
>> וכאשר אתה רוצה להכניס מפתח
זוג ערך לגיבורים באמצעות

122
00:06:22,470 --> 00:06:26,250
הליך דנו, במקרה הגרוע ביותר
יהיה לך הקצאת צומת חדשה

123
00:06:26,250 --> 00:06:27,550
עבור כל אות.

124
00:06:27,550 --> 00:06:31,290
ואנו מניחים כי הקצאה
הוא פעולת זמן קבועה.

125
00:06:31,290 --> 00:06:35,850
אז אם יניח שאורך המפתח הוא
מוקף תמידי קבוע, שניהם

126
00:06:35,850 --> 00:06:39,400
הכנסה ולהסתכל למעלה הם קבועים
פעולות זמן לגיבורים.

127
00:06:39,400 --> 00:06:42,930
>> אם אנחנו לא עושים את ההנחה הזאת ש
אורך המפתח הוא חסום על ידי קבוע

128
00:06:42,930 --> 00:06:46,650
קבוע, ולאחר מכן כניסה ולהסתכל למעלה,
במקרה הגרוע ביותר, הם ליניאריים ב

129
00:06:46,650 --> 00:06:48,240
אורכו של המפתח.

130
00:06:48,240 --> 00:06:51,800
שים לב כי מספר הפריטים המאוחסן
בגיבורים אינו משפיע על המראה

131
00:06:51,800 --> 00:06:52,820
או זמן כניסה.

132
00:06:52,820 --> 00:06:55,360
זה השפיע רק על ידי
אורכו של המפתח.

133
00:06:55,360 --> 00:06:59,300
>> לעומת זאת, הוספת ערכים, למשל,
שולחן חשיש נוטה לעשות

134
00:06:59,300 --> 00:07:01,250
העתיד להסתכל למעלה איטי יותר.

135
00:07:01,250 --> 00:07:04,520
אמנם זה אולי נשמע מושך בהתחלה,
אנחנו צריכים לזכור כי

136
00:07:04,520 --> 00:07:08,740
מורכבות אסימפטוטי חיוביות לא
אומר שבפועל הנתונים

137
00:07:08,740 --> 00:07:11,410
מבנה הוא בהכרח
מעבר לתוכחת.

138
00:07:11,410 --> 00:07:15,860
עלינו גם לשקול כי לאחסון
מילה בגיבורים שאנחנו צריכים, במקרה הרע

139
00:07:15,860 --> 00:07:19,700
מקרה, מידתי מספר צמתים
לאורכה של המילה עצמה.

140
00:07:19,700 --> 00:07:21,880
>> ניסיונות נוטים להשתמש הרבה מקום.

141
00:07:21,880 --> 00:07:25,620
זה בניגוד לשולחן חשיש,
שבו אנו זקוקים לצומת חדשה אחד בלבד

142
00:07:25,620 --> 00:07:27,940
לאחסן כמה זוג ערך מפתח.

143
00:07:27,940 --> 00:07:31,370
עכשיו, שוב בתאוריה, חלל גדול
הצריכה לא נראית כמו גדול

144
00:07:31,370 --> 00:07:34,620
להתמודד, במיוחד בהתחשב בכך שמודרני
יש מחשבים ג'יגה ו

145
00:07:34,620 --> 00:07:36,180
ג'יגה בייט של זיכרון.

146
00:07:36,180 --> 00:07:39,200
אבל מסתבר שעדיין יש לנו
לדאוג שימוש וזיכרון

147
00:07:39,200 --> 00:07:42,540
ארגון למען
ביצועים, שכן מחשבים מודרניים

148
00:07:42,540 --> 00:07:46,960
יש מנגנונים במקום תחת
מכסה המנוע כדי להאיץ את הגישה לזיכרון.

149
00:07:46,960 --> 00:07:51,180
>> אבל המנגנונים האלה עובדים הכי טובים כאשר
כניסות זיכרון נעשות בקומפקטי

150
00:07:51,180 --> 00:07:52,810
אזורים או תחומים.

151
00:07:52,810 --> 00:07:55,910
וצומת של הגיבורים יכולים להתגורר
בכל מקום בערימה ש.

152
00:07:55,910 --> 00:07:58,390
אבל אלה פשרות
שאנחנו חייבים לקחת בחשבון.

153
00:07:58,390 --> 00:08:01,440
>> זכור כי, בעת בחירת נתונים
מבנה למשימה מסוימת, אנחנו

154
00:08:01,440 --> 00:08:04,420
צריך לחשוב על איזה סוג של
פעולות מבנה הנתונים צריכה

155
00:08:04,420 --> 00:08:07,140
תמיכה וכמה ביצועים
של כל אחד מאלה

156
00:08:07,140 --> 00:08:09,080
ענייני פעולות לנו.

157
00:08:09,080 --> 00:08:11,300
פעולות אלו אף עלולות
להרחיב מעבר פשוט

158
00:08:11,300 --> 00:08:13,430
מבט למעלה בסיסי וכניסה.

159
00:08:13,430 --> 00:08:17,010
נניח שאנחנו רוצים ליישם סוג
פונקציונליות אוטומטי מלאה, הרבה

160
00:08:17,010 --> 00:08:18,890
כמו מנוע חיפוש גוגל עושה.

161
00:08:18,890 --> 00:08:22,210
כלומר, להחזיר את כל המפתחות ואת
פוטנציאל ערכים ה

162
00:08:22,210 --> 00:08:24,130
יש לי קידומת נתון.

163
00:08:24,130 --> 00:08:27,050
>> הגיבורים הוא ייחודי שימושיים
עבור פעולה זו.

164
00:08:27,050 --> 00:08:29,890
זה פשוט כדי לחזר דרך
הגיבורים עבור כל תו של

165
00:08:29,890 --> 00:08:30,950
הקידומת.

166
00:08:30,950 --> 00:08:33,559
בדיוק כמו מבצע להסתכל למעלה,
נוכל לעקוב אחר מצביעים

167
00:08:33,559 --> 00:08:35,400
תו אחרי תו.

168
00:08:35,400 --> 00:08:38,659
ואז, כאשר אנחנו מגיעים בסוף
קידומת, אנחנו יכולים לחזר דרך

169
00:08:38,659 --> 00:08:42,049
חלק הנותר של מבנה הנתונים
מאז כל אחד מהמקשים מעבר

170
00:08:42,049 --> 00:08:43,980
יש שלב זה את הקידומת.

171
00:08:43,980 --> 00:08:47,670
>> זה גם קל להשיג רשימה זו
בסדר אלפביתי מאז

172
00:08:47,670 --> 00:08:50,970
אלמנטים של מערך הילדים
מסודרים בסדר אלפביתי.

173
00:08:50,970 --> 00:08:54,420
אז אני מקווה שאתה תשקלי
נתינה מנסה לנסות.

174
00:08:54,420 --> 00:08:56,085
אני קווין שמידט, וזה CS50.

175
00:08:56,085 --> 00:08:58,745

176
00:08:58,745 --> 00:09:00,790
>> אה, זה הוא תחילתו
של הירידה.

177
00:09:00,790 --> 00:09:01,350
אני מצטער.

178
00:09:01,350 --> 00:09:01,870
סליחה.

179
00:09:01,870 --> 00:09:02,480
סליחה.

180
00:09:02,480 --> 00:09:03,130
סליחה.

181
00:09:03,130 --> 00:09:03,950
>> שביתת ארבעה.

182
00:09:03,950 --> 00:09:04,360
אני בחוץ.

183
00:09:04,360 --> 00:09:05,280
סליחה.

184
00:09:05,280 --> 00:09:06,500
סליחה.

185
00:09:06,500 --> 00:09:07,490
סליחה.

186
00:09:07,490 --> 00:09:12,352
מצטער לעשיית האדם
צריך לערוך את זה להשתגע.

187
00:09:12,352 --> 00:09:13,280
>> סליחה.

188
00:09:13,280 --> 00:09:13,880
סליחה.

189
00:09:13,880 --> 00:09:15,080
סליחה.

190
00:09:15,080 --> 00:09:15,680
סליחה.

191
00:09:15,680 --> 00:09:16,280
>> SPEAKER 1: עבודה טובה.

192
00:09:16,280 --> 00:09:17,530
זה נעשה ממש טוב.

193
00:09:17,530 --> 00:09:18,430