1
00:00:00,000 --> 00:00:02,740
[Powered by Google Translate] [Walkthrough - סט בעיה 5]

2
00:00:02,740 --> 00:00:04,870
[Zamyla צ'אן - אוניברסיטת הרווארד]

3
00:00:04,870 --> 00:00:07,190
[זה CS50. - CS50.TV]

4
00:00:07,190 --> 00:00:10,400
>> בסדר. שלום לכולם, וברוך הבאים לWalkthrough 5.

5
00:00:10,400 --> 00:00:17,400
>> Pset5 הוא שגיאות כתיב, שבו אנחנו יהיו ביצוע של בדק איות.

6
00:00:17,400 --> 00:00:21,030
בודקי איות הם מאוד חשובים.

7
00:00:21,030 --> 00:00:23,390
האם זה אי פעם קרה לך?

8
00:00:23,390 --> 00:00:27,170
אתה עובד מאוד מאוד אוגר על נייר להתנגשות

9
00:00:27,170 --> 00:00:33,120
ואז עדיין בסופו של דבר מקבל rade זוהר מאוד כמו D או D =

10
00:00:33,120 --> 00:00:39,390
והכול מפני שאתה ספוילר הנקניק הכבד במילה הרחבה הלווייתן.

11
00:00:39,390 --> 00:00:44,710
כן, גהת הפלפלים שלך היא עניין של, אימפוטנציה העליונה.

12
00:00:44,710 --> 00:00:49,140
זו בעיה שמשפיעה על תלמידים גבריים, גבריים.

13
00:00:49,140 --> 00:00:56,260
נאמרתי לי פעם על ידי מענה הכיתה הסית שלעולם לא יצליח להגיע לקולגה טוב.

14
00:00:56,260 --> 00:01:00,250
וזה כל מה שאי פעם רציתי, זה כל מה שכל ילד רוצה בגיל שלי,

15
00:01:00,250 --> 00:01:04,569
רק כדי להיכנס לעמית טוב.

16
00:01:04,569 --> 00:01:12,720
ולא סתם עמית לעבודה. לא, אני רוצה ללכת לקולגה משפטי שנהב.

17
00:01:12,720 --> 00:01:18,360
אז אם אני לא עשיתי שיפור, הלך יהיו החלומות שלי ילך לרווארד,

18
00:01:18,360 --> 00:01:22,730
Jale, או כלא - אתה יודע, בכלא, ניו ג'רזי.

19
00:01:22,730 --> 00:01:25,170
אז יש לי את עצמי בודק איות.

20
00:01:25,170 --> 00:01:29,380
זה קטע קטן מאחד האמנים האהובים עליי מילה המדוברים, טיילור Mali.

21
00:01:29,380 --> 00:01:34,630
בכל מקרה, כמו שהוא אומר, את החשיבות של בעל בודק איות היא חשובה מאוד.

22
00:01:34,630 --> 00:01:39,440
>> אז מוזמן Walkthrough 5, שבו אנו יהיו לדבר על pset5: שגיאות כתיב,

23
00:01:39,440 --> 00:01:44,300
שבו אנחנו יהיו ביצוע של בדק האיות שלנו מאוד משלו.

24
00:01:44,300 --> 00:01:50,880
ארגז הכלים לשבוע הזה, קוד ההפצה, הוא הולך להיות חשוב להסתכל על

25
00:01:50,880 --> 00:01:54,950
רק כדי להבין את הפונקציות השונות שהמילון שלך הולך להיות.

26
00:01:54,950 --> 00:02:01,500
אנחנו בעצם הולכים להיות שקבצי c מרובים. שביחד הופכים pset.

27
00:02:01,500 --> 00:02:05,420
וכך לעבור על היבטים השונים, למרות שאנחנו ממש לא עריכה

28
00:02:05,420 --> 00:02:10,770
אחד מהקבצים, speller.c, לדעת איך זה עובד ביחס לdictionary.c,

29
00:02:10,770 --> 00:02:14,100
שיהיה לנו לכתוב, הוא הולך להיות חשוב מאוד.

30
00:02:14,100 --> 00:02:16,970
מפרט pset גם מכיל הרבה מידע שימושי

31
00:02:16,970 --> 00:02:21,360
במונחים של דברים שאתה יכול להניח, חוקים ודברים כאלה,

32
00:02:21,360 --> 00:02:24,710
כדי להיות בטוח כדי לקרוא בעיון את מפרט pset לטיפים.

33
00:02:24,710 --> 00:02:29,310
וכאשר יש ספק של כלל או משהו כזה, אז תמיד מתייחס למפרט pset

34
00:02:29,310 --> 00:02:31,550
או דיון.

35
00:02:31,550 --> 00:02:34,060
pset זה הולך להסתמך בכבדות על מצביעים,

36
00:02:34,060 --> 00:02:37,890
לכן אנחנו רוצים לוודא שאנחנו מבינים את ההבדל בין כוכבי הוספה

37
00:02:37,890 --> 00:02:41,680
לפני שמו של המצביע והאמפרסנד, איך לשחרר אותם, וכו '

38
00:02:41,680 --> 00:02:47,550
אז להיות אדון של מצביעים הולך להיות מאוד מועיל בסט בעיה זו.

39
00:02:47,550 --> 00:02:50,460
אנחנו הולכים לבדוק את הרשימות מקושרות קצת יותר,

40
00:02:50,460 --> 00:02:57,790
שם יש לנו אלמנטים שאנו מכנים צומת שיש להם גם ערך וגם כמצביע

41
00:02:57,790 --> 00:03:02,520
לצומת הבאה, וכך למעשה מקשר אלמנטים שונים בזה אחר זה.

42
00:03:02,520 --> 00:03:07,190
יש כמה אפשרויות שונות של יישום המילון שלך בפועל.

43
00:03:07,190 --> 00:03:13,150
אנחנו הולכים לבדוק את שתי שיטות עיקריות, שהיא שולחנות חשיש, ואז מנסה.

44
00:03:13,150 --> 00:03:17,660
בשני אלה, הם כרוכים באיזשהו רעיון של רשימה מקושרת

45
00:03:17,660 --> 00:03:20,790
שם יש לך אלמנטים קשורים אחד לשנייה.

46
00:03:20,790 --> 00:03:25,640
וכך אנחנו הולכים להסתכל על איך אתה יכול להיות מסוגל לפעול בסביבת רשימות מקושרות,

47
00:03:25,640 --> 00:03:29,680
ליצור אותם, לנווט במונחים של איך, למשל, להכניס לתוכו צומת

48
00:03:29,680 --> 00:03:32,760
או בחינם כל כמו גם את צומת.

49
00:03:32,760 --> 00:03:34,740
במונחים של בלוטות לשחרר, זה באמת חשוב

50
00:03:34,740 --> 00:03:37,700
כי בכל פעם שאנו זכרון malloc, אחר כך אנו משחררים אותו.

51
00:03:37,700 --> 00:03:42,910
אז אנחנו רוצים לוודא שאין מצביע הולך unfreed, שאין לנו כל דליפות זיכרון.

52
00:03:42,910 --> 00:03:48,330
אנחנו הולכים להציג את כלי שנקרא Valgrind שמפעיל את התכנית שלך

53
00:03:48,330 --> 00:03:52,260
ובודק אם כל הזיכרון שהוקצה אז הוא שוחרר.

54
00:03:52,260 --> 00:03:59,080
pset להשלים רק כשזה עובד ויש לו פונקציונליות מלאה,

55
00:03:59,080 --> 00:04:03,990
אלא גם, Valgrind אומר לך שלא מצא דליפות זיכרון.

56
00:04:03,990 --> 00:04:06,690
לבסוף, לpset זה, אני באמת רוצה להדגיש -

57
00:04:06,690 --> 00:04:11,360
אני מתכוון, כרגיל, אני בהחלט תומך בשימוש בעט ונייר לסטי הבעיה שלך,

58
00:04:11,360 --> 00:04:14,840
אבל בשביל זה, אני חושב שעט ונייר הולך להיות חשוב במיוחד

59
00:04:14,840 --> 00:04:19,000
כשאתה רוצה להיות ציור חצים לדברים ולהבין כיצד דברים עובדים.

60
00:04:19,000 --> 00:04:24,440
אז בהחלט תנסה להשתמש בעט ונייר כדי להוציא דברים לפני שאתה מקבל הקידוד

61
00:04:24,440 --> 00:04:26,970
בגלל שהוא יכול לקבל קצת מבולגן.

62
00:04:26,970 --> 00:04:30,700
>> ראשית, בואו נכנסנו לרשימות מקושרות קצת.

63
00:04:30,700 --> 00:04:35,510
רשימות מקושרות מורכבות מצומת, שבו כל צומת יש ערך הקשורים אליו,

64
00:04:35,510 --> 00:04:39,810
כמו גם כמצביע לצומת הבאה אחריו.

65
00:04:39,810 --> 00:04:43,680
כמה דברים חשובים עם הרשימות המקושרות הם שאנחנו צריכים לזכור

66
00:04:43,680 --> 00:04:48,810
בי הצומת הראשונה שלנו היא, ואז ברגע שאנחנו יודעים לאן היא הצומת הראשונה,

67
00:04:48,810 --> 00:04:52,990
שהדרך בה אנו יכולים לגשת לצומת שאת נקודתי הצומת הראשונות ל

68
00:04:52,990 --> 00:04:55,850
ואז זה שאחריו וזה שאחריו.

69
00:04:55,850 --> 00:05:00,340
ולאחר מכן את הרכיב האחרון ברשימה המקושרת שלך הוא שהמצביע של הצומת

70
00:05:00,340 --> 00:05:02,340
הוא תמיד הולך להצביע ל NULL.

71
00:05:02,340 --> 00:05:08,230
כאשר נקודות לצומת NULL, אז אתה יודע שאתה כבר הגעת לסוף הרשימה,

72
00:05:08,230 --> 00:05:12,320
כי צומת שהיא אחרון, שאין שום דבר אחרי זה.

73
00:05:12,320 --> 00:05:16,970
כאן בשרטוט זה, אתה רואה שהחיצים הם המצביעים,

74
00:05:16,970 --> 00:05:20,290
והקטע הכחול שבו בערך,

75
00:05:20,290 --> 00:05:24,420
ולאחר מכן התיבה האדומה עם המצביע למצביע זה של הצומת

76
00:05:24,420 --> 00:05:27,050
מצביע לצומת הבאה אחריו.

77
00:05:27,050 --> 00:05:33,730
ואז אתה רואה כאן, צומת D תצביע על NULL כי זה האלמנט האחרון ברשימה.

78
00:05:33,730 --> 00:05:38,240
>> בואו נסתכל על איך אנחנו יכולים להגדיר struct לצומת.

79
00:05:38,240 --> 00:05:40,130
מכיוון שאנחנו רוצים שנהיה לי צומת מרובים ו,

80
00:05:40,130 --> 00:05:43,180
זה הולך להיות struct typedef

81
00:05:43,180 --> 00:05:46,870
שבו אנחנו הולכים להיות מספר מופעים שונים של צמתים.

82
00:05:46,870 --> 00:05:50,850
וכך אנו מגדירים אותו כסוג נתונים חדש.

83
00:05:50,850 --> 00:05:53,630
הנה, יש לנו צומת struct typedef.

84
00:05:53,630 --> 00:05:56,160
בדוגמה זו, יש לנו עסק עם בלוטות שלמות,

85
00:05:56,160 --> 00:06:00,490
לכן יש לנו ערך בשם שלם ולאחר מכן יש לנו מצביע אחר,

86
00:06:00,490 --> 00:06:07,390
ובמקרה הזה, זה מצביע לצומת, ולכן יש לנו struct צומת * שם הבא.

87
00:06:07,390 --> 00:06:09,520
ואז אנחנו קוראים הצומת כל העניין הזה.

88
00:06:09,520 --> 00:06:11,110
ודא שאתה מבין את תחביר זה.

89
00:06:11,110 --> 00:06:17,940
שים לב שצומת היא למעשה הפניה למעלה כמו גם למטה בסוגריים המסולסלים.

90
00:06:17,940 --> 00:06:23,400
אז כדי לעקוב אחר שבו הצומת הראשונה שלי היא ברשימה מקושרת זה,

91
00:06:23,400 --> 00:06:29,390
אז יש לי מצביע צומת נקרא ראש, ואני מרחב malloc מספיק לגודל של צומת.

92
00:06:29,390 --> 00:06:36,240
שים לב, עם זאת, הראש שהוא למעשה מצביע צומת בניגוד לצומת בפועל עצמו.

93
00:06:36,240 --> 00:06:40,130
אז הראש בעצם לא מכיל שום ערך,

94
00:06:40,130 --> 00:06:45,590
זה רק מצביע לאיזה הצומת הראשונה ברשימה המקושרת שלי היא.

95
00:06:55,080 --> 00:06:58,340
>> כדי לקבל תחושה טובה יותר של רשימות מקושרות, כי זה מאוד חשוב

96
00:06:58,340 --> 00:07:02,220
לעקוב, לוודא שאתה לשמור על השרשרת,

97
00:07:02,220 --> 00:07:09,990
אני אוהב לחשוב על זה כעל אנשים בשורה ומחזיקים ידות,

98
00:07:09,990 --> 00:07:14,330
שבו כל אדם מחזיק ידות עם הבא בתור.

99
00:07:14,330 --> 00:07:18,350
אתה לא יכול לראות בציור הזה, אבל בעצם הם מצביעים לאדם הבא

100
00:07:18,350 --> 00:07:23,760
זה בשרשרת שלהם.

101
00:07:23,760 --> 00:07:29,270
ואז אם אתה רוצה לחצות רשימה מקושרת שבו האנשים האלה -

102
00:07:29,270 --> 00:07:32,830
דמיינו את כל האנשים האלה יש ערכים הקשורים בם

103
00:07:32,830 --> 00:07:36,590
וגם להצביע לאדם הבא בקו -

104
00:07:36,590 --> 00:07:40,810
אם אתה רוצה לעבור את הרשימה המקושרת, למשל, לכל אחד לערוך את הערכים

105
00:07:40,810 --> 00:07:42,830
או חפש ערך או משהו כזה,

106
00:07:42,830 --> 00:07:48,270
אז אתה רוצה שיהיה מצביע לאדם הספציפי.

107
00:07:48,270 --> 00:07:52,670
אז אנחנו הולכים להיות מצביע צומת סוג נתונים.

108
00:07:52,670 --> 00:07:55,580
למשל זה, בואו נקראים לזה סמן.

109
00:07:55,580 --> 00:07:59,630
דרך נפוצה נוספת לשם זה תהיה איטרטור או משהו כזה

110
00:07:59,630 --> 00:08:05,130
כי זה iterating שוב ולמעשה נע שצומת זה מצביע.

111
00:08:05,130 --> 00:08:14,410
זה כאן יהיה הסמן שלנו.

112
00:08:14,410 --> 00:08:20,180
הסמן שלנו יהיה נקודה ראשונה על הרכיב הראשון ברשימה שלנו.

113
00:08:20,180 --> 00:08:26,910
ואז מה שאנחנו רוצים לעשות הוא היינו בעצם ממשיכים את הסמן,

114
00:08:26,910 --> 00:08:29,130
שתזיז אותו מהצד לצד.

115
00:08:29,130 --> 00:08:33,409
במקרה זה, אנחנו רוצים להעביר אותו לאלמנט הבא ברשימה.

116
00:08:33,409 --> 00:08:38,480
עם מערכים, מה שאנחנו עושים הוא פשוט הייתי אומרים שאנחנו להגדיל את האינדקס על ידי 1.

117
00:08:38,480 --> 00:08:46,020
במקרה זה, מה שאנחנו צריכים לעשות הוא בעצם למצוא אדם שהאדם הנוכחי הוא מצביע,

118
00:08:46,020 --> 00:08:48,930
וזה הולך להיות הערך הבא.

119
00:08:48,930 --> 00:08:53,230
אז אם הסמן נמצא בדיוק מצביע צומת, אז מה שאנחנו רוצים לעשות

120
00:08:53,230 --> 00:08:56,320
הוא שאנחנו רוצים להגיע לשווי שהסמן כדי להצביע.

121
00:08:56,320 --> 00:09:01,350
אנחנו רוצים להגיע לצומת ואז, ברגע שאנחנו כבר בצומת, תמצאו בו הוא מצביע.

122
00:09:01,350 --> 00:09:05,820
כדי להגיע לצומת בפועל שהסמן מצביע,

123
00:09:05,820 --> 00:09:13,160
בדרך כלל אנחנו מציינים אותו על ידי (* סמן).

124
00:09:13,160 --> 00:09:19,160
זה ייתן לך את הצומת שבפועל את הסמן כדי להצביע.

125
00:09:19,160 --> 00:09:21,730
ואז אחרי זה, מה שאנחנו רוצים לעשות הוא שאנחנו רוצים לגשת

126
00:09:21,730 --> 00:09:25,680
כל מה שהערך הבא של הצומת הוא.

127
00:09:25,680 --> 00:09:32,820
כדי לעשות זאת, כדי לגשת לערכים הפנימיים של struct, יש לנו מפעיל הנקודה.

128
00:09:32,820 --> 00:09:39,530
אז זה יהיה (* סמן). הבא.

129
00:09:39,530 --> 00:09:44,840
אבל זה קצת מבולגן במושגים של הסוגריים סביב הסמן *,

130
00:09:44,840 --> 00:09:56,800
ואז אנחנו מחליפים כל הצהרה זו עם סמן->.

131
00:09:56,800 --> 00:10:02,700
זה מקף ולאחר מכן עולה על סימן, ולכן ביצוע חץ.

132
00:10:02,700 --> 00:10:05,840
סמן-> הבא.

133
00:10:05,840 --> 00:10:12,390
שבעצם תקבל את הצומת שנקודתי הסמן. שהערך הנו הבא.

134
00:10:12,390 --> 00:10:16,790
אז במקום שיש את הכוכב והנקודה, אתה מחליף את זה עם חץ.

135
00:10:16,790 --> 00:10:24,820
היו זהיר מאוד כדי לוודא שאתה מנסה להשתמש בתחביר זה.

136
00:10:33,550 --> 00:10:37,620
>> עכשיו יש לנו את הסמן שלנו, אם אנחנו רוצים לגשת הערך,

137
00:10:37,620 --> 00:10:40,450
בעבר, היו לנו סמן-> הבא,

138
00:10:40,450 --> 00:10:46,260
אבל לגישת הערך בצומת שהסמן מצביע, אנחנו רק אומרים בפשטות

139
00:10:46,260 --> 00:10:48,070
ערך צומת>.

140
00:10:48,070 --> 00:10:53,600
משם, הוא מסוג הנתונים מה אנו מגדירים את הערכים והבלוטות ליהיו.

141
00:10:53,600 --> 00:10:59,620
אם זה int צומת, ולאחר מכן סמן-> ערך הוא פשוט הולך להיות מספר שלם.

142
00:10:59,620 --> 00:11:04,870
כדי שנוכל לעשות פעולות בזה, תבדוק בשוויון, להקצות לו ערכים שונים, וכו '

143
00:11:04,870 --> 00:11:11,090
אז מה שאתה רוצה לעשות, אם ברצונך להעביר את הסמן לאדם הבא,

144
00:11:11,090 --> 00:11:15,270
אתה בעצם לשנות את הערך של הסמן.

145
00:11:15,270 --> 00:11:19,340
מאז הסמן הוא מצביע צומת, אתה משנה את כתובת המצביע בפועל

146
00:11:19,340 --> 00:11:23,890
לכתובת של הצומת הבאה ברשימה שלך.

147
00:11:23,890 --> 00:11:28,930
זה רק חלק הקוד בו אתה יכול לחזר.

148
00:11:28,930 --> 00:11:31,230
איפה יש לי את ההערה לעשות משהו,

149
00:11:31,230 --> 00:11:33,850
זה שבו אתה כנראה הולך לגשת הערך

150
00:11:33,850 --> 00:11:37,850
או לעשות משהו שקשור בצומת ספציפית.

151
00:11:37,850 --> 00:11:43,050
כדי להתחיל אותו, אני אומר שהסמן שלי בתחילה

152
00:11:43,050 --> 00:11:48,430
הולך להצביע על המרכיב הראשון ברשימה המקושרת.

153
00:11:48,430 --> 00:11:52,910
וכך מלפנים, הגדיר אותו כראש של הצומת.

154
00:11:52,910 --> 00:11:57,610
>> כפי שציינתי קודם, לשחרר הוא באמת חשוב.

155
00:11:57,610 --> 00:12:02,440
אתה רוצה לוודא שאתה לשחרר את כל אלמנט ברשימה לאחר שתסיים עם זה.

156
00:12:02,440 --> 00:12:04,940
כאשר אתה לא צריך להפנות לכל אחד מהמצביעים האלה יותר,

157
00:12:04,940 --> 00:12:10,620
אתה רוצה לוודא שאתה לשחרר את כל המצביעים האלה.

158
00:12:10,620 --> 00:12:14,460
אבל אתה רוצה להיות מאוד זהיר שברצונך למנוע דליפות זיכרון.

159
00:12:14,460 --> 00:12:25,080
אם אתה אדם אחד חינם בטרם עת, ולאחר מכן את כל המצביעים שנקודתי צומת ל

160
00:12:25,080 --> 00:12:26,900
הולכים לאיבוד.

161
00:12:26,900 --> 00:12:32,070
אם יחזור לדוגמה של האדם לעשות את זה קצת סכומים גבוהים יותר,

162
00:12:32,070 --> 00:12:49,600
בואו האנשים האלה, אלא במקרה זה הם מרחפים מעל אגם עם מפלצת.

163
00:12:49,600 --> 00:12:53,200
אנו רוצים לוודא שבכל פעם שאנו משחררים, אנחנו לא מפסידים

164
00:12:53,200 --> 00:12:58,920
ולשחרר את כל צומת לפני שאנחנו משחררים אותם בפועל.

165
00:12:58,920 --> 00:13:05,730
לדוגמה, אם היית פשוט להתקשר בחינם על זה, כאן,

166
00:13:05,730 --> 00:13:15,350
אז הוא ישוחרר, אבל אז כל החבר 'ה האלה היו אז יאבדו

167
00:13:15,350 --> 00:13:18,450
והם היו שוקעים ונופלים.

168
00:13:18,450 --> 00:13:24,900
אז אנחנו רוצים לוודא שבמקום, אנחנו רוצים לשמור על קישור לשאר.

169
00:13:37,630 --> 00:13:42,480
המצביע שלנו בראש, שמצביע על הרכיב הראשון ברשימה.

170
00:13:42,480 --> 00:13:49,990
זה כמו סוג של חבל עיגון בגוף הראשון.

171
00:13:52,870 --> 00:13:57,470
מה שאולי תרצה לעשות כאשר אתה משחרר רשימה יש -

172
00:13:57,470 --> 00:14:04,520
אם אתה רוצה לשחרר את האלמנט הראשון ראשון, אז אתה יכול להיות מצביע זמני

173
00:14:04,520 --> 00:14:07,370
שזה מצביע מה המרכיב הראשון הוא.

174
00:14:07,370 --> 00:14:11,420
אז יש לך המצביע הזמני שלך מצביע לכאן.

175
00:14:11,420 --> 00:14:15,840
באופן זה, יש לנו את אחיזה של הצומת הראשונה.

176
00:14:15,840 --> 00:14:18,930
ואז, מאחר שאנו יודעים שהצומת הראשונה הוא הולכת להיות משוחרר,

177
00:14:18,930 --> 00:14:24,890
אז אנחנו יכולים לעבור חבל זה, העוגן הזה, הראש שלנו,

178
00:14:24,890 --> 00:14:31,930
למעשה להצביע על מה את הראשון כדי להצביע.

179
00:14:31,930 --> 00:14:38,760
אז בראש זה למעשה מצביע על האלמנט השני עכשיו.

180
00:14:38,760 --> 00:14:43,980
עכשיו מותר לנו לשחרר את כל מה שהוא מאוחסן בטמפ,

181
00:14:43,980 --> 00:14:53,360
וכדי שנוכל למחוק כי בלי זה מסכן את כל צומת האחרים ברשימה שלנו.

182
00:14:54,140 --> 00:15:05,020
דרך נוספת שאתה יכול לעשות זה יכול להיות

183
00:15:05,020 --> 00:15:08,650
בכל פעם שאתה רק לשחרר את הרכיב האחרון ברשימה

184
00:15:08,650 --> 00:15:11,010
בגלל שהם מבטיחים שהיא לא יהיה הצביע על שום דבר.

185
00:15:11,010 --> 00:15:15,570
אז אתה יכול פשוט לשחרר את זה, אז זה בחינם אחת, ואז זה בחינם 1.

186
00:15:15,570 --> 00:15:21,900
זה בהחלט עובד, אבל הוא מעט איטי יותר, כי על ידי הטבע מהרשימות המקושרות,

187
00:15:21,900 --> 00:15:24,670
אנחנו לא יכולים פשוט לקפוץ מייד לאחרון.

188
00:15:24,670 --> 00:15:28,030
אנחנו צריכים לעבור כל אלמנט ברשימה המקושרת

189
00:15:28,030 --> 00:15:31,020
ולבדוק האם אחד שמצביע על NULL ולבדוק כל זמן,

190
00:15:31,020 --> 00:15:33,780
ואז ברגע שאנחנו מגיעים לסוף, שאז ש.

191
00:15:33,780 --> 00:15:40,270
אם היית עושה את התהליך הזה, שהיית למעשה תבדוק כאן,

192
00:15:40,270 --> 00:15:44,190
בדיקה כאן, ולאחר מכן לבדוק פה, לשחרר אותו,

193
00:15:44,190 --> 00:15:47,470
אז לחזור, בודק פה, בודק כאן, לשחרר אותו,

194
00:15:47,470 --> 00:15:49,660
בדיקה לכאן, ואז לשחרר אותו.

195
00:15:49,660 --> 00:15:52,880
זה לוקח קצת יותר זמן. כן.

196
00:15:52,880 --> 00:15:59,060
>> [תלמיד] האם יהיה אפשר לעשות רשימה מקושרת שמאחסנת מצביע יציאה לסוף?

197
00:15:59,060 --> 00:16:01,320
זה בהחלט יהיה אפשרי.

198
00:16:01,320 --> 00:16:08,340
לחזור על השאלה, האם זה אפשרי שיהיה לי מבנה רשימה מקושרת

199
00:16:08,340 --> 00:16:12,490
כזה שיש לך מצביע מצביע לסוף הרשימה המקושרת?

200
00:16:12,490 --> 00:16:18,090
אני הייתי אומר שזה אפשרי, ובכל פעם שאתה מכניס משהו לתוך הרשימה המקושרת שלך

201
00:16:18,090 --> 00:16:21,470
היית צריך לעדכן את מצביע ושדברים כאלה.

202
00:16:21,470 --> 00:16:26,640
היית זנב * צומת, למשל.

203
00:16:26,640 --> 00:16:29,840
אבל כאשר אתה מיישם תכונה זו, אתה צריך לחשוב על הפשרות,

204
00:16:29,840 --> 00:16:32,700
רוצים כמה פעמים אני הולך להיות חוזר ונשנה בעניין זה,

205
00:16:32,700 --> 00:16:36,100
כמה קשה זה הולך להיות כדי לעקוב אחר הזנב, כמו גם את הראש

206
00:16:36,100 --> 00:16:38,400
כמו גם איטרטור שלי, ודברים כאלה.

207
00:16:40,730 --> 00:16:42,480
האם זה -? >> [תלמיד] כן.

208
00:16:42,480 --> 00:16:48,270
זה אפשרי, אבל במונחים של החלטות עיצוב, אתה צריך לשקול את האפשרויות.

209
00:16:53,850 --> 00:17:01,090
>> הנה שלד של קוד שיאפשר לך לשחרר את כל אלמנט ברשימה מקושרת.

210
00:17:01,090 --> 00:17:05,460
שוב, מאז אני iterating על רשימה מקושרת, אני הולך לרוצה לקבל קצת סוג של סמן

211
00:17:05,460 --> 00:17:08,670
או איטרטור.

212
00:17:08,670 --> 00:17:14,640
אנו iterating עד שהסמן הוא NULL.

213
00:17:14,640 --> 00:17:17,640
אתה לא רוצה לחזר כאשר הסמן נמצא NULL

214
00:17:17,640 --> 00:17:20,579
כי זה אומר שאין שום דבר ברשימה.

215
00:17:20,579 --> 00:17:25,069
אז הנה אני עושה * צומת זמנית

216
00:17:25,069 --> 00:17:29,610
מצביע על מה שאני שוקל הוא ראשון מהרשימה שלי,

217
00:17:29,610 --> 00:17:35,340
ואז להעביר את הסמן שלי קדימה 1, ואז כל מה שהיה לי חופשי באחסון הזמני.

218
00:17:38,460 --> 00:17:43,650
>> כעת אנו מגיעים להחדרה לתוך רשימות מקושרות.

219
00:18:00,200 --> 00:18:09,660
יש לי שלושה צומת ברשימה המקושרת שלי, ובואו נלך עם מקרה הפשוט

220
00:18:09,660 --> 00:18:18,970
לאן אנחנו רוצים להכניס צומת אחר בסוף הרשימה המקושרת שלנו.

221
00:18:18,970 --> 00:18:25,980
כדי לעשות זאת, כל מה שאנחנו עושים הוא שהיינו חוצים

222
00:18:25,980 --> 00:18:32,100
למצוא בי הסוף הנוכחי של הרשימה המקושרת הוא, כך לפי צומת מצביע על NULL -

223
00:18:32,100 --> 00:18:33,850
זה את זה -

224
00:18:33,850 --> 00:18:37,260
ואז אומר, בעצם, זה לא הולך להיות הצומת האחרונה;

225
00:18:37,260 --> 00:18:39,830
אנחנו בעצם הולכים לעוד אחד.

226
00:18:39,830 --> 00:18:46,260
אז שנהיה לנו נקודה זו נוכחית אחד למה שאנחנו מכניסים.

227
00:18:46,260 --> 00:18:50,080
אז עכשיו האדם האדום הזה כאן הופך את הצומת האחרונה ברשימה המקושרת.

228
00:18:50,080 --> 00:18:56,080
וכך האופייני לצומת האחרונה ברשימה המקושרת הוא שזה מצביע על NULL.

229
00:18:56,080 --> 00:19:09,380
אז מה הייתי צריך לעשות הוא להגדיר מצביע של בחור אדום זה NULL. יש.

230
00:19:09,380 --> 00:19:25,370
>> אבל מה אם אנחנו רוצים להכניס בצומת בין השנייה ושלישית?

231
00:19:25,370 --> 00:19:28,960
כי אחד היא לא ממש פשוט כמו שאנחנו רוצים לוודא

232
00:19:28,960 --> 00:19:34,290
שאנחנו לא להרפות מכל צומת ברשימה המקושרת שלנו.

233
00:19:34,290 --> 00:19:43,450
מה הייתי צריך לעשות הוא לוודא שאנחנו לעגן את עצם לכל אחד.

234
00:19:43,450 --> 00:19:49,900
לדוגמה, בואו נקראים לזה שני אחת.

235
00:19:49,900 --> 00:19:54,390
אם אמר שנייה אחת מצביע כעת לזו חדשה

236
00:19:54,390 --> 00:20:02,520
ואתה פשוט עשה מצביע יש, אז זה יגרום לאיבוד הבחור הזה

237
00:20:02,520 --> 00:20:07,830
מכיוון שאין כל קשר אליו.

238
00:20:07,830 --> 00:20:18,970
במקום - אני אצייר את זה שוב. תסלח היכולות האמנותיות שלי.

239
00:20:18,970 --> 00:20:26,570
אנחנו יודעים שאנחנו לא יכולים פשוט מקשרים ישירות 2 לאחד החדש.

240
00:20:26,570 --> 00:20:30,480
אנחנו צריכים לוודא שאנחנו נאחזים באחרון.

241
00:20:30,480 --> 00:20:39,200
מה שאולי תרצו לעשות הוא להיות מצביע זמני

242
00:20:39,200 --> 00:20:42,650
לאלמנט זה הולך להיות מצורפים ב.

243
00:20:42,650 --> 00:20:45,140
אז יש לנו מצביע זמני שם.

244
00:20:45,140 --> 00:20:50,780
מאחר שאנחנו יודעים שזה השליש נשמר אחר,

245
00:20:50,780 --> 00:20:53,680
2 ניתן כעת לקשר לאחד החדש שלנו.

246
00:20:53,680 --> 00:20:57,490
ואם הבחור האדום חדש זה הולך להיות בין 2 ו 3,

247
00:20:57,490 --> 00:21:05,550
אז מה שמצביע שהבחור הולך להצביע? >> [תלמיד] טמפ.

248
00:21:05,550 --> 00:21:07,490
טמפ. כן.

249
00:21:07,490 --> 00:21:15,430
אז הערך הבא של הבחור אדום זה הולך להיות זמני.

250
00:21:26,090 --> 00:21:33,010
כשאתה מכניס לרשימות מקושרות, ראינו שאנחנו יכולים

251
00:21:33,010 --> 00:21:38,260
בקלות להוסיף משהו לסיום על ידי יצירת מערך זמני,

252
00:21:38,260 --> 00:21:42,850
אם אנחנו רוצים להוסיף משהו לאמצע המערך שלנו, או,

253
00:21:42,850 --> 00:21:46,810
אז זה ייקח קצת יותר ולדשדש.

254
00:21:46,810 --> 00:21:50,240
אם אתה רוצה, למשל, יש לך רשימה מקושרת ממוינת

255
00:21:50,240 --> 00:21:54,880
אז יש לך לסוג של לשקול את העלויות ותועלות של ש

256
00:21:54,880 --> 00:21:59,720
כי אם אתה רוצה להיות מערך ממוין, זה אומר שכל פעם שאתה מכניס לתוכו,

257
00:21:59,720 --> 00:22:01,630
זה הולך לקחת קצת יותר זמן.

258
00:22:01,630 --> 00:22:05,500
עם זאת, אם אתה רוצה בהמשך, כפי שנמצא אנחנו רוצים,

259
00:22:05,500 --> 00:22:10,280
חיפוש באמצעות רשימה מקושרת, אז זה יכול להיות קל יותר אם אתה יודע שהכל בסדר.

260
00:22:10,280 --> 00:22:15,340
אז אולי כדאי לך לשקול את העלויות ותועלות של זה.

261
00:22:20,150 --> 00:22:27,740
>> דרך נוספת להוסיף לרשימה מקושרת היא להוסיף להתחלה של רשימה.

262
00:22:27,740 --> 00:22:34,700
אם אנו מפנים את העוגן שלנו כאן - זה בראש שלנו -

263
00:22:34,700 --> 00:22:40,960
ואז יש את האנשים האלה קשורים אליו,

264
00:22:40,960 --> 00:22:48,460
ואז יש לנו צומת חדשה להיות מוכנס לתוך ההתחלה,

265
00:22:48,460 --> 00:22:52,590
אז מה עלולים אנחנו רוצים לעשות?

266
00:22:55,220 --> 00:23:03,580
מה יהיה רע בסתם להגיד שאני רוצה לקשר האדום לכחול,

267
00:23:03,580 --> 00:23:05,790
כי זה ראשון?

268
00:23:05,790 --> 00:23:08,570
מה היה קורה כאן?

269
00:23:08,570 --> 00:23:12,130
כל שלושה אלה היו הולכים לאיבוד.

270
00:23:12,130 --> 00:23:14,140
אז אנחנו לא רוצים לעשות את זה.

271
00:23:14,140 --> 00:23:21,430
שוב, למדנו שאנחנו צריכים קצת סוג של מצביע זמני.

272
00:23:21,430 --> 00:23:34,470
בואו לבחור נקודה זמנית לבחור הזה.

273
00:23:34,470 --> 00:23:39,640
אז יכול להיות לנו נקודה הכחולה האחת הזמני

274
00:23:39,640 --> 00:23:43,240
ולאחר מכן את הנקודה האדומה לכחולים.

275
00:23:43,240 --> 00:23:47,830
הסיבה שאני משתמש באנשים כאן היא שאנחנו באמת רוצים לדמיין

276
00:23:47,830 --> 00:23:53,180
אוחז באנשים ולוודא שיש לנו את קישור אליהם

277
00:23:53,180 --> 00:23:57,590
לפני שעזבנו את יד אחרת או משהו כזה.

278
00:24:05,630 --> 00:24:10,650
>> עכשיו יש לנו תחושה של רשימות מקושרות - כיצד תוכל ליצור רשימה מקושרת

279
00:24:10,650 --> 00:24:15,090
וליצור את המבנים שלמורכבים מהגדרת הסוג לצומת

280
00:24:15,090 --> 00:24:19,060
ולאחר מכן לוודא שיש לנו מצביע לראש הרשימה מקושרת ש--

281
00:24:19,060 --> 00:24:23,210
פעם אחת יש לנו את זה ואנחנו יודעים איך לעבור דרך מערך,

282
00:24:23,210 --> 00:24:28,200
לגשת לגורמים שונים, אנחנו יודעים איך להוסיף ואנו יודעים כיצד לשחרר אותם,

283
00:24:28,200 --> 00:24:30,260
אז אנחנו יכולים להיכנס לשגיאות כתיב.

284
00:24:30,260 --> 00:24:38,150
כרגיל, יש לנו קטע של שאלות שיקבלו בו השתמש להפעלה עם רשימות מקושרות

285
00:24:38,150 --> 00:24:41,750
ומבנים שונים כגון תורים וערמות.

286
00:24:41,750 --> 00:24:46,000
אז אנחנו יכולים לעבור לשגיאות כתיב.

287
00:24:46,000 --> 00:24:55,170
>> שגיאות כתיב יש בקוד ההפצה כמה קבצים בעלי חשיבות.

288
00:24:55,170 --> 00:24:58,850
ראשית עלינו להבחין כי יש לנו Makefile זה כאן,

289
00:24:58,850 --> 00:25:03,040
שאנחנו לא באמת נתקלנו בעבר.

290
00:25:03,040 --> 00:25:10,090
אם נבחן היטב את pset5 התיקייה, היית מבחין שיש לך. קובץ h,

291
00:25:10,090 --> 00:25:12,530
אז יש לך שני קבצים. ג.

292
00:25:12,530 --> 00:25:18,920
מה המשמעות של זה הוא Makefile לפני, הייתי פשוט הקלד ולאחר מכן להפוך את שם התכנית

293
00:25:18,920 --> 00:25:25,550
ואז הייתי רואה את כל הטיעונים והדגלים האלה עברו במהדר.

294
00:25:25,550 --> 00:25:30,580
מה Makefile עושה הוא מאפשר לנו לאסוף כמה קבצים בבת אחת

295
00:25:30,580 --> 00:25:34,650
ותעבור בדגלים שאנחנו רוצים.

296
00:25:34,650 --> 00:25:41,300
כאן אנחנו רואים שיש קובץ כותרת כאן.

297
00:25:41,300 --> 00:25:43,730
אז אנחנו ממש יש שני קבצי מקור.

298
00:25:43,730 --> 00:25:47,520
יש לנו speller.c וdictionary.c.

299
00:25:47,520 --> 00:25:54,560
אתם מוזמנים לערוך את Makefile אם תרצה.

300
00:25:54,560 --> 00:26:03,310
שים לב שאם תקליד כאן נקי, אז מה שהוא עושה הוא בעצם מסיר כל דבר

301
00:26:03,310 --> 00:26:06,340
שהוא הליבה.

302
00:26:06,340 --> 00:26:09,190
אם יש לך תקלת פילוח, בעצם אתה מקבל מזבלת ליבה.

303
00:26:09,190 --> 00:26:13,260
אז הקובץ הקטן והמכוער הזה יופיע בספרייה שלך שנקראת ליבה.

304
00:26:13,260 --> 00:26:16,310
אתה רוצה להסיר שכדי לעשות את זה נקי.

305
00:26:16,310 --> 00:26:20,940
היא מסירה את כל קבצי exe ו. קבצי o.

306
00:26:27,900 --> 00:26:30,220
>> בואו נסתכל לdictionary.h.

307
00:26:30,220 --> 00:26:34,410
זה אומר שהוא מצהיר פונקציונלי של מילון.

308
00:26:34,410 --> 00:26:39,530
יש לנו אורך מרבי עבור כל מילה במילון.

309
00:26:39,530 --> 00:26:45,130
אנחנו אומרים שזה הולך להיות המילה הארוכה ביותר האפשרית. זה באורך 45.

310
00:26:45,130 --> 00:26:48,900
אז אנחנו לא הולכים לשום מילים שעולות אורך ש.

311
00:26:48,900 --> 00:26:50,980
כאן אנחנו רק צריכים את אבות טיפוס לפונקציות.

312
00:26:50,980 --> 00:26:55,290
אין לנו יישום בפועל, כי זה מה שאנחנו הולכים לעשות לpset זה.

313
00:26:55,290 --> 00:26:59,940
אבל מה המשמעות של זה הוא שכן יש לנו עסק עם קבצים גדולים יותר כאן

314
00:26:59,940 --> 00:27:06,650
ופונקציונלי בקנה מידה גדול יותר, זה שימושי. קובץ h

315
00:27:06,650 --> 00:27:11,290
כך שמישהו קורא או באמצעות הקוד שלך אחר לא יכול להבין מה קורה.

316
00:27:11,290 --> 00:27:17,910
ואולי הם רוצים ליישם מנסה אם עשו שולחנות חשיש או להיפך.

317
00:27:17,910 --> 00:27:21,850
אז הם היינו אומרים פונקצית העומס שלי,

318
00:27:21,850 --> 00:27:26,950
היישום בפועל הוא הולך להיות שונה, אבל אב טיפוס זה לא ישתנה.

319
00:27:26,950 --> 00:27:33,280
כאן יש לנו לבדוק, שמחזיר אמת אם מילה מסוימת היא במילון.

320
00:27:33,280 --> 00:27:39,800
אז יש לנו עומס, שבעצם לוקח בקובץ מילון

321
00:27:39,800 --> 00:27:44,360
ולאחר מכן טוען אותה לאיזה מבנה נתונים.

322
00:27:44,360 --> 00:27:47,500
יש לנו גודל, אשר, כאשר קראו, מחזיר את הגודל של המילון שלך,

323
00:27:47,500 --> 00:27:50,310
כמה מילים מאוחסנים בו,

324
00:27:50,310 --> 00:27:54,390
ואז לפרוק, שמשחרר את כל הזיכרון שאולי לקח את

325
00:27:54,390 --> 00:27:57,900
תוך המילון שלך.

326
00:28:01,070 --> 00:28:03,590
>> בואו נסתכל dictionary.c.

327
00:28:03,590 --> 00:28:10,490
אנו רואים שזה נראה דומה מאוד לdictionary.h, אלא שעכשיו זה בדיוק יש את כל אלה בטודוס.

328
00:28:10,490 --> 00:28:16,980
וכדי שזה התפקיד שלך. סופו של דבר, אתה תהיה מילוי speller.c עם כל הקוד הזה.

329
00:28:16,980 --> 00:28:21,540
Dictionary.c, כאשר לרוץ, הוא לא באמת הולך לעשות שום דבר,

330
00:28:21,540 --> 00:28:29,590
אז אנחנו מסתכלים לכיוון speller.c לראות ביצוע בפועל של בודק האיות.

331
00:28:29,590 --> 00:28:32,060
למרות שאתה לא הולך להיות עורך של כל הקוד הזה,

332
00:28:32,060 --> 00:28:38,050
זה חשוב לקרוא, להבין מתי נקרא עומס, כאשר אני קורא סימון,

333
00:28:38,050 --> 00:28:42,350
רק כדי להבין, למפות אותו, לראות איך הפונקציה עובדת.

334
00:28:42,350 --> 00:28:49,860
אנחנו רואים שזה בדיקה לשימוש הנכון.

335
00:28:49,860 --> 00:28:55,200
בעיקרון, כאשר מישהו רץ איות, זה מצביע על כך שזה לא חובה

336
00:28:55,200 --> 00:29:00,950
שאעבור בקובץ מילון, כי עומד להיות קובץ מילון ברירת מחדל.

337
00:29:00,950 --> 00:29:05,410
ואז הם צריכים לעבור בטקסט להיות איות מסומנת.

338
00:29:05,410 --> 00:29:11,410
עסקות rusage עם זמן, כי חלק מpset זה שיתמודדו עם המשך

339
00:29:11,410 --> 00:29:14,790
הוא לא רק מקבל תפקוד של בדק איות של עובד

340
00:29:14,790 --> 00:29:17,190
אבל בעצם מקבל את זה כדי להיות מהיר.

341
00:29:17,190 --> 00:29:22,040
ואם כך זה המקום שבי rusage הולך להיכנס

342
00:29:22,040 --> 00:29:28,740
כאן, אנו רואים את השיחה הראשונה לאחד מקבצי dictionary.c, אשר הוא עומס.

343
00:29:28,740 --> 00:29:34,720
עומס מחזיר אמת או שקר - אמיתי על הצלחה, שווא בעת התקלה.

344
00:29:34,720 --> 00:29:41,400
אז אם המילון לא נטען כראוי, אז speller.c יחזיר 1 ולהתפטר.

345
00:29:41,400 --> 00:29:47,920
אבל אם זה עושה עומס כמו שצריך, אז זה הולך להמשיך.

346
00:29:47,920 --> 00:29:50,740
אנחנו ממשיכים, ואנו רואים כמה קבצי הקלט / פלט לכאן,

347
00:29:50,740 --> 00:29:56,210
איפה זה הולך להיות התמודדות עם פתיחת קובץ הטקסט.

348
00:29:56,210 --> 00:30:04,640
הנה, מה המשמעות של זה הוא בודקת איות כל מילה ומילה בטקסט.

349
00:30:04,640 --> 00:30:09,270
אז מה עושה ברגע speller.c כאן iterating מעל כל אחת מהמילים בקובץ הטקסט

350
00:30:09,270 --> 00:30:12,790
ובדיקתן במילון.

351
00:30:24,680 --> 00:30:32,350
הנה, יש לנו בוליאני השגוי שיראו אם השק חוזר נכון או לא.

352
00:30:32,350 --> 00:30:37,110
אם המילה היא למעשה במילון, אז הסימון יהיה החזר אמיתי.

353
00:30:37,110 --> 00:30:39,760
זה אומר שהמילה אינה שגויה.

354
00:30:39,760 --> 00:30:45,330
אז שגוי יהיה שקר, ובגלל זה יש לנו את המפץ שם, האינדיקציה.

355
00:30:45,330 --> 00:30:56,320
אנחנו ממשיכים, ואז זה עוקב אחר כמה מילים באיות שגויה

356
00:30:56,320 --> 00:30:58,910
יש בקובץ.

357
00:30:58,910 --> 00:31:03,870
זה ממשיך ובסוגר את הקובץ.

358
00:31:03,870 --> 00:31:09,250
אז הנה, הוא מדווח כמה מילים באיות שגויה שהיה לך.

359
00:31:09,250 --> 00:31:12,680
היא מחשבת כמה זמן לקח כדי לטעון מילון,

360
00:31:12,680 --> 00:31:15,080
כמה זמן זה לקח כדי לבדוק אותו,

361
00:31:15,080 --> 00:31:18,510
כמה זמן זה לקח כדי לחשב את הגודל,

362
00:31:18,510 --> 00:31:21,260
אשר, כפי שנמשיך, צריך להיות קטן מאוד,

363
00:31:21,260 --> 00:31:25,390
ואז כמה זמן זה לקח לפרוק את המילון.

364
00:31:25,390 --> 00:31:27,700
כאן למעלה אנו רואים את השיחה כדי לפרוק כאן.

365
00:31:27,700 --> 00:31:52,690
אם תבדקו לגודל כאן,

366
00:31:52,690 --> 00:31:59,050
אז אנו רואים שכאן הוא הקריאה לגודל שבו היא קובעת את הגודל של המילון.

367
00:32:05,730 --> 00:32:07,100
מדהים.

368
00:32:07,100 --> 00:32:10,920
>> המשימה שלנו לpset זו היא ליישם עומס, שיטען את המילון

369
00:32:10,920 --> 00:32:15,480
מבנה נתונים - משנה מה תבחר, יהיה זה שולחן חשיש או לנסות -

370
00:32:15,480 --> 00:32:18,810
עם מילים מקובץ המילון.

371
00:32:18,810 --> 00:32:25,290
ואז יש לך גודל, שיחזיר את מספר מילים במילון.

372
00:32:25,290 --> 00:32:29,860
ואם תיישם את העומס בצורה חכמה, אז גודל צריך להיות די קל.

373
00:32:29,860 --> 00:32:33,860
ואז יש לך לבדוק, שיבדוק אם מילה מסוימת היא במילון.

374
00:32:33,860 --> 00:32:38,690
אז speller.c עובר בחוט, ואז אתה צריך לבדוק אם חוט ש

375
00:32:38,690 --> 00:32:41,610
הוא הכיל בתוך המילון שלך.

376
00:32:41,610 --> 00:32:46,750
שים לב שאנו בדרך כלל יש מילונים רגילים,

377
00:32:46,750 --> 00:32:53,020
אבל בpset זה, בעצם כל עבר מילון בכל שפה.

378
00:32:53,020 --> 00:32:57,040
אז אנחנו לא יכולים פשוט להניח שהמילה היא בפנים.

379
00:32:57,040 --> 00:33:03,090
המילה foobar יכול להיות מוגדר במילון מסוים שאנו עוברים פנימה

380
00:33:03,090 --> 00:33:07,920
ואז יש לנו לפרוק, אשר משחרר את המילון מזיכרון.

381
00:33:07,920 --> 00:33:11,930
>> ראשית, אני רוצה ללכת על שיטת שולחן החשיש

382
00:33:11,930 --> 00:33:14,630
על איך אנחנו יכולים ליישם את כל ארבעה התפקידים האלה,

383
00:33:14,630 --> 00:33:18,650
ואז אני אלך על שיטה מנסה, איך אנחנו מיישמים ארבע הפונקציות הללו,

384
00:33:18,650 --> 00:33:22,720
ובסופו של דבר השיחה על כמה טיפים כלליים כאשר אתה עושה pset

385
00:33:22,720 --> 00:33:27,870
וגם איך ייתכן שתוכלו להשתמש Valgrind לבדוק דליפות זיכרון.

386
00:33:27,870 --> 00:33:30,550
>> בואו ניכנס לשיטת שולחן החשיש.

387
00:33:30,550 --> 00:33:35,910
שולחן חשיש מורכב מרשימה של דליים.

388
00:33:35,910 --> 00:33:43,010
כל ערך, כל מילה, הוא הולך להיכנס לאחד דליים אלה.

389
00:33:43,010 --> 00:33:53,200
שולחן חשיש באופן אידיאלי באופן שווה מפיץ את כל הערכים האלה שאתה עובר ב

390
00:33:53,200 --> 00:33:57,160
ולאחר מכן מאכלס אותם בדלי כזה שכל דלי

391
00:33:57,160 --> 00:34:02,000
יש על מספר שווה של ערכים בזה.

392
00:34:02,000 --> 00:34:09,630
המבנה לשולחן חשיש, יש לנו מערך של רשימות מקושרות.

393
00:34:09,630 --> 00:34:17,900
מה שאנחנו עושים הוא שאנחנו נפגשים בערך, אנחנו בודקים איפה ערך שצריך להיות שייך,

394
00:34:17,900 --> 00:34:23,840
הדלי שהוא שייך אליו, ואז למקם אותו לרשימה המקושרת המשויכת לדלי.

395
00:34:23,840 --> 00:34:28,199
הנה, מה שיש לי הוא פונקציית hash.

396
00:34:28,199 --> 00:34:31,320
זה שולחן חשיש int.

397
00:34:31,320 --> 00:34:38,540
אז לדלי הראשון, מספרים שלמים כלשהם מתחת 10 להיכנס לסל הראשון.

398
00:34:38,540 --> 00:34:42,190
כל מספרים שלמים מעל 10 אך מתחת 20 להיכנס לשנייה,

399
00:34:42,190 --> 00:34:44,179
ואז כן הלאה וכן הלאה.

400
00:34:44,179 --> 00:34:52,370
מבחינתי, כל אחד מסלים מייצגים את המספרים האלה.

401
00:34:52,370 --> 00:34:59,850
עם זאת, אומר שהיית אמור להעביר ב50, למשל.

402
00:34:59,850 --> 00:35:07,490
נראה כאילו שלושה הראשונים מכילים מגוון של 10 מספרים.

403
00:35:07,490 --> 00:35:12,570
אבל אני רוצה לאפשר לשולחן החשיש שלי לקחת בכל סוג של מספרים שלמים,

404
00:35:12,570 --> 00:35:19,860
כל כך אז הייתי צריך לסנן את כל המספרים מעל 30 לתוך הדלי שעבר.

405
00:35:19,860 --> 00:35:26,660
וכך אז שיביא בסוג של שולחן חשיש לא מאוזן.

406
00:35:31,330 --> 00:35:35,640
כדי לחזור ולהדגיש, שולחן חשיש הוא רק מערך של דליים

407
00:35:35,640 --> 00:35:38,590
איפה כל דלי הוא רשימה מקושרת.

408
00:35:38,590 --> 00:35:43,730
וכן לקבוע בו כל ערך עובר, שזה הולך לתוך הדלי,

409
00:35:43,730 --> 00:35:46,260
אתה הולך רוצה מה שנקרא פונקציית hash

410
00:35:46,260 --> 00:35:55,010
שלוקח את ערך ולאחר מכן אומר שערך זה מתאים לדלי מסוים.

411
00:35:55,010 --> 00:36:00,970
למעלה, כך בדוגמה זו, פונקציית hash שלי לקחה את כל ערך.

412
00:36:00,970 --> 00:36:03,020
זה בדק אם זה היה פחות מ 10.

413
00:36:03,020 --> 00:36:05,360
אם זה היה, זה היה לשים אותו לתוך הדלי הראשון.

414
00:36:05,360 --> 00:36:08,910
זה בודק אם זה פחות מ 20, מכניס אותו לתוך 2 אם זה נכון,

415
00:36:08,910 --> 00:36:12,880
בודק אם זה פחות מ 30, ואז מכניס אותו לתוך הדלי השלישי,

416
00:36:12,880 --> 00:36:16,990
ואז כל שאר פשוט נופל לדלי הרביעי.

417
00:36:16,990 --> 00:36:20,110
אז בכל פעם שיש לך ערך, פונקציית hash

418
00:36:20,110 --> 00:36:25,420
יציב את הערך שלתוך הדלי המתאים.

419
00:36:25,420 --> 00:36:32,430
פונקציית hash בעצם צריכה לדעת כמה דליים יש לך.

420
00:36:32,430 --> 00:36:37,960
גודל שולחן החשיש שלך, את מספר הסלים שיש לך,

421
00:36:37,960 --> 00:36:41,190
שהולך להיות מספר קבוע שתלוי בך, אתה צריך להחליט,

422
00:36:41,190 --> 00:36:43,590
אבל זה הולך להיות מספר קבוע.

423
00:36:43,590 --> 00:36:51,840
אז פונקציית hash שלך יהיה להסתמך על זה כדי לקבוע אילו דלי כל מקש נכנס

424
00:36:51,840 --> 00:36:54,450
כזה שהוא מופץ באופן שווה.

425
00:36:56,150 --> 00:37:03,820
בדומה ליישום שלנו של רשימות מקושרות, עכשיו כל צומת בטבלת החשיש

426
00:37:03,820 --> 00:37:07,000
למעשה הוא הולך להיות סוג char.

427
00:37:07,000 --> 00:37:14,340
אז יש לנו מערך char בשם מילה ולאחר מכן עוד מצביע לצומת הבאה,

428
00:37:14,340 --> 00:37:19,010
וזה הגיוני כי זה הולך להיות רשימה מקושרת.

429
00:37:19,010 --> 00:37:24,350
זכור שכאשר אנו מקושרים רשימות, עשיתי * צומת נקראת הראש

430
00:37:24,350 --> 00:37:31,060
שהצביע על הצומת הראשונה ברשימה המקושרת.

431
00:37:31,060 --> 00:37:34,020
אבל לשולחן החשיש שלנו, כי יש לנו רשימות מקושרות מרובות,

432
00:37:34,020 --> 00:37:37,520
מה שאנחנו רוצים הוא שאנחנו רוצים שולחן החשיש להיות כמו, "מה הוא דלי?"

433
00:37:37,520 --> 00:37:43,340
דלי הוא רק רשימה של מצביעי צומת,

434
00:37:43,340 --> 00:37:50,620
וכן כל אלמנט בדלי הוא למעשה מצביע לרשימה המקושרת המתאימה לו.

435
00:37:56,180 --> 00:38:01,520
כדי לחזור לשרטוט זה, אתה רואה שאת הדליים עצמם בחיצים,

436
00:38:01,520 --> 00:38:06,980
לא בלוטות בפועל.

437
00:38:11,680 --> 00:38:16,420
אחד נכס מהותי של פונקציות hash הוא שהם דטרמיניסטיים.

438
00:38:16,420 --> 00:38:19,440
זה אומר שכל פעם שאתה חשיש המספר 2,

439
00:38:19,440 --> 00:38:22,270
זה תמיד צריך לחזור באותו הדלי.

440
00:38:22,270 --> 00:38:26,440
כל ערך יחיד שנכנס לפונקציית hash, אם חזר,

441
00:38:26,440 --> 00:38:29,690
צריך לקבל את אותו המדד.

442
00:38:29,690 --> 00:38:34,210
אז פונקציית hash שלך מחזירה את האינדקס של המערך

443
00:38:34,210 --> 00:38:38,530
שם ערך ששייך.

444
00:38:38,530 --> 00:38:41,790
כפי שציינתי קודם, מספר הסלים קבוע,

445
00:38:41,790 --> 00:38:49,630
וכך המדד שלך שאתה חוזר צריך להיות פחות ממספר הסלים

446
00:38:49,630 --> 00:38:52,680
אך גדול מ 0.

447
00:38:52,680 --> 00:39:00,780
הסיבה שיש לנו פונקציות hash רק במקום אחד רשימה מקושרת אחת

448
00:39:00,780 --> 00:39:09,290
או מערך אחד הוא שאנחנו רוצים להיות מסוגלים לקפוץ לקטע מסוים בקלות

449
00:39:09,290 --> 00:39:11,720
אם אנחנו יודעים את המאפיין של ערך -

450
00:39:11,720 --> 00:39:14,760
במקום שיצטרך לחפש בכל המילון השלם,

451
00:39:14,760 --> 00:39:18,320
להיות מסוגל לקפוץ לקטע מסוים שלו.

452
00:39:19,880 --> 00:39:24,440
פונקציית hash שלך צריכה לקחת בחשבון שאופן אידיאלי,

453
00:39:24,440 --> 00:39:28,980
כל אחד מסלים יש בערך אותו מספר המפתחות.

454
00:39:28,980 --> 00:39:35,040
מאז שולחן החשיש הוא סדרה של רשימות מקושרות,

455
00:39:35,040 --> 00:39:38,480
אז את הרשימות המקושרים עצמם הולכות להיות צומת אחד או יותר.

456
00:39:38,480 --> 00:39:43,210
בדוגמא הקודמת, שני מספרים שונים, למרות שהם לא היו שווים,

457
00:39:43,210 --> 00:39:46,950
כשמרוסק, היה חוזר אותו המדד.

458
00:39:46,950 --> 00:39:53,620
לכן, כאשר אתם עוסקים במילים, מילה אחת כשמרוסק

459
00:39:53,620 --> 00:39:57,450
יהיה אותו ערך Hash כמילה אחרת.

460
00:39:57,450 --> 00:40:04,140
זה מה שאנו מכנים התנגשות, כאשר יש לנו צומת, שכאשר מרוסקות,

461
00:40:04,140 --> 00:40:09,610
הרשימה המקושרת שבדלי אינה ריקה.

462
00:40:09,610 --> 00:40:14,180
הטכניקה שאנו מכנים יש יניארי חיטוט,

463
00:40:14,180 --> 00:40:22,550
לאן אתה הולך לרשימה המקושרת ולאחר מכן למצוא בו ברצונך להוסיף צומת כי

464
00:40:22,550 --> 00:40:25,520
כי יש לך התנגשות.

465
00:40:25,520 --> 00:40:28,070
אתה יכול לראות שאולי יש תחלופה כאן, נכון?

466
00:40:28,070 --> 00:40:33,760
אם יש לך שולחן קטן מאוד חשיש, מספר קטן מאוד של דליים,

467
00:40:33,760 --> 00:40:36,380
ואז אתה הולך להיות הרבה התנגשויות.

468
00:40:36,380 --> 00:40:40,460
אבל אז אם אתה עושה טבלת חשיש גדולה מאוד,

469
00:40:40,460 --> 00:40:44,110
אתה כנראה הולך ללמזער התנגשויות,

470
00:40:44,110 --> 00:40:47,170
אבל זה הולך להיות מבנה נתונים גדול מאוד.

471
00:40:47,170 --> 00:40:49,310
יש הולך להיות פשרות עם זה.

472
00:40:49,310 --> 00:40:51,310
אז כשאתה עושה pset, נסה לשחק

473
00:40:51,310 --> 00:40:54,210
בין מה שהופך שולחן חשיש קטן אולי

474
00:40:54,210 --> 00:41:02,100
אבל אז ידע שזה הולך לקחת קצת יותר זמן לעבור את האלמנטים השונים

475
00:41:02,100 --> 00:41:04,270
רשימות המקושרות אלה.

476
00:41:04,270 --> 00:41:09,500
>> מה עומס הולך לעשות הוא לחזר על כל מלה במילון.

477
00:41:09,500 --> 00:41:13,180
זה עובר במצביע לקובץ המילון.

478
00:41:13,180 --> 00:41:18,050
אז אתה הולך לנצל את קובץ I / O פונקציות שאתה שולט בpset4

479
00:41:18,050 --> 00:41:23,010
ולחזר על כל מלה במילון.

480
00:41:23,010 --> 00:41:26,620
אתה רוצה שכל מילה במילון כדי להיות צומת חדש,

481
00:41:26,620 --> 00:41:32,730
ואתה הולך למקום בכל אחד מצומת פנימיים של מבנה נתוני המילון שלך.

482
00:41:32,730 --> 00:41:36,560
בכל פעם שאתה מקבל מילה חדשה, אתה יודע שזה הולך להיות צומת.

483
00:41:36,560 --> 00:41:46,590
אז אתה יכול ללכת ישר וmalloc מצביע צומת עבור כל מילה חדשה שיש לך.

484
00:41:46,590 --> 00:41:52,610
הנה אני מתקשר new_node מצביע צומתי ואני mallocing מה? גודלו של צומת.

485
00:41:52,610 --> 00:41:59,190
ואז לקרוא את המחרוזת בפועל מקובץ, משום שהמילון מאוחסן בפועל

486
00:41:59,190 --> 00:42:03,340
על ידי מילה ולאחר מכן קו חדש, מה שאנחנו יכולים לנצל את היתרון של

487
00:42:03,340 --> 00:42:06,520
הוא fscanf הפונקציה,

488
00:42:06,520 --> 00:42:10,280
לפי קובץ הוא קובץ המילון שאנחנו עוברים ב,

489
00:42:10,280 --> 00:42:18,900
אז זה סורק את הקובץ למחרוזת ומקומות שמחרוזת לטענה האחרונה.

490
00:42:18,900 --> 00:42:26,890
אם אתה זוכר בחזרה לאחת מההרצאות, כשעלינו על

491
00:42:26,890 --> 00:42:29,320
וסוג של קלף את השכבות בחזרה על ספריית CS50,

492
00:42:29,320 --> 00:42:33,430
ראינו יישום fscanf שם.

493
00:42:33,430 --> 00:42:37,700
כדי לחזור לfscanf, יש לנו את הקובץ שאנחנו קוראים מ,

494
00:42:37,700 --> 00:42:42,570
אנחנו מחפשים מחרוזת שבקובץ, ולאחר מכן אנחנו מניחים אותו לתוך

495
00:42:42,570 --> 00:42:48,340
כאן יש לי new_node> מילה משום new_node הוא מצביע צומת,

496
00:42:48,340 --> 00:42:50,380
לא צומת עצמו.

497
00:42:50,380 --> 00:42:57,100
אז אני אומר new_node, אני רוצה ללכת לצומת שזה מצביע על

498
00:42:57,100 --> 00:43:01,190
ולאחר מכן להקצות את ערך שלמילה.

499
00:43:01,190 --> 00:43:08,540
אנחנו רוצים ואז לקחת את המילה ושלהכניס אותו לתוך שולחן החשיש.

500
00:43:08,540 --> 00:43:13,750
להבין שאנחנו עשינו new_node מצביע צומת

501
00:43:13,750 --> 00:43:18,230
בגלל שאנחנו הולכים רוצים לדעת מה הכתובת של צומת היא

502
00:43:18,230 --> 00:43:23,940
כאשר אנו מכניסים אותה בגלל המבנה של הבלוטות עצמן, של struct,

503
00:43:23,940 --> 00:43:26,380
הוא שיש להם מצביעים לצומת חדשה.

504
00:43:26,380 --> 00:43:30,820
אז מה הכתובת של צומת שהולכת להצביע ל?

505
00:43:30,820 --> 00:43:34,550
כתובת זו הולכת להיות new_node.

506
00:43:34,550 --> 00:43:42,140
האם זה הגיוני, למה אנחנו עושים את new_node * צומת בניגוד לצומת?

507
00:43:43,700 --> 00:43:45,700
אוקיי.

508
00:43:45,700 --> 00:43:52,840
יש לנו מילה. שהערך הוא new_node-> מילה.

509
00:43:52,840 --> 00:43:55,970
המכיל את המילה מהמילון שאנחנו רוצים קלט.

510
00:43:55,970 --> 00:44:00,210
אז מה שאנחנו רוצים לעשות הוא שאנחנו רוצים לקרוא לפונקציית hash על מייתר

511
00:44:00,210 --> 00:44:03,780
כי פונקציית hash שלנו לוקחת במחרוזת ולאחר מכן מחזירה אותנו מספר שלם,

512
00:44:03,780 --> 00:44:12,090
שם שלם שהוא המדד בי hashtable שבמדד מייצג דלי ש.

513
00:44:12,090 --> 00:44:18,260
אנחנו רוצים לקחת את האינדקס ולאחר מכן ללכת לאותו מדד של שולחן החשיש

514
00:44:18,260 --> 00:44:26,960
ולאחר מכן להשתמש ברשימה מקושרת כדי להוסיף את הצומת בnew_node.

515
00:44:26,960 --> 00:44:31,950
זכור כי זאת אתם מחליטים להכניס הצומת שלך,

516
00:44:31,950 --> 00:44:34,370
בין אם זה באמצע, אם ברצונך למיין אותו

517
00:44:34,370 --> 00:44:39,650
או בתחילתו או בסופו של דבר, רק לוודא שהצומת האחרונה שלך תמיד מצביעה על NULL

518
00:44:39,650 --> 00:44:46,730
משום שזו הדרך היחידה שאנחנו יודעים איפה את הרכיב האחרון של הרשימה המקושרת שלנו הוא.

519
00:44:50,790 --> 00:44:59,710
>> אם הגודל הוא מספר שלם שמייצג את מספר מילים במילון,

520
00:44:59,710 --> 00:45:03,060
אז דרך אחת לעשות את זה היא שבכל פעם הגודל נקרא

521
00:45:03,060 --> 00:45:05,840
אנו עוברים כל אלמנט בטבלת החשיש

522
00:45:05,840 --> 00:45:09,410
ואז לחזר דרך כל רשימה מקושרת בתוך שולחן החשיש

523
00:45:09,410 --> 00:45:13,770
ואז לחשב את האורך ש, הגדלה 1 נגדנו על ידי 1.

524
00:45:13,770 --> 00:45:16,580
אבל בכל פעם שהגודל נקרא, כי זה הולך לקחת זמן רב

525
00:45:16,580 --> 00:45:22,120
כי אנחנו הולכים להיות ליניארי חיטוט בכל רשימה מקושרת אחת.

526
00:45:22,120 --> 00:45:30,530
במקום זאת, זה הולך להיות הרבה יותר קל אם אתה לעקוב אחר כמה מילים מועברים פנימה

527
00:45:30,530 --> 00:45:36,330
אז אם אתה כולל דלפק בתוך פונקצית הטעינה שלך

528
00:45:36,330 --> 00:45:42,430
שעדכונים בהתאם לצורך, ולאחר מכן מונה, אם תגדיר אותו למשתנה גלובלית,

529
00:45:42,430 --> 00:45:44,930
תוכל לגשת לפי גודל.

530
00:45:44,930 --> 00:45:51,450
אז מה גודל פשוט יכול לעשות הוא בשורה אחת, רק להחזיר את ערך הדלפק,

531
00:45:51,450 --> 00:45:55,500
גודלו של המילון, שכבר עסק בעומס.

532
00:45:55,500 --> 00:46:05,190
זה מה שהתכוונתי כשאמרתי שאם אתה מיישם את עומס בצורה מועילה,

533
00:46:05,190 --> 00:46:08,540
אז הגודל הולך להיות די קל.

534
00:46:08,540 --> 00:46:11,350
>> אז עכשיו אנחנו מקבלים כדי לבדוק.

535
00:46:11,350 --> 00:46:15,960
עכשיו אנחנו עוסקים במילים מקובץ טקסט הקלט,

536
00:46:15,960 --> 00:46:19,910
וכך אנחנו הולכים לבדיקה כל אם של המילים האלה הקלט

537
00:46:19,910 --> 00:46:22,520
הם למעשה במילון או לא.

538
00:46:22,520 --> 00:46:26,520
בדומה למירוץ, אנחנו רוצים לאפשר למקרה חוסר רגישות.

539
00:46:26,520 --> 00:46:32,110
אתה רוצה לוודא שכל המילים בעברו, למרות שהם במקרה מעורב,

540
00:46:32,110 --> 00:46:37,840
כשהתקשרתי עם compare מחרוזת, הם שווים ערך.

541
00:46:37,840 --> 00:46:42,450
את המילים במילון קבצי הטקסט הן למעשה כל האותיות קטנות.

542
00:46:42,450 --> 00:46:49,280
דבר נוסף הוא שאתה יכול להניח שכל מילה שעברה בכל מחרוזת,

543
00:46:49,280 --> 00:46:53,200
הולך להיות אלפביתי או מכילים גרשיים.

544
00:46:53,200 --> 00:46:58,010
גרשיים הולכים להיות תקפות מילים במילון שלנו.

545
00:46:58,010 --> 00:47:06,470
אז אם יש לך מילה עם הגרש S, זה מילה לגיטימית בפועל במילון שלך

546
00:47:06,470 --> 00:47:11,650
זה הולך להיות אחד מצומת בטבלת החשיש שלך.

547
00:47:13,470 --> 00:47:18,350
בדקו אם פועל עם המילה קיימת, אז זה חייב להיות בטבלת החשיש שלנו.

548
00:47:18,350 --> 00:47:22,210
אם המילה נמצאת במילון, אז כל מילים שבמילון הוא בשולחן החשיש,

549
00:47:22,210 --> 00:47:26,560
אז בואו נחפש את המילה הזאת בטבלת החשיש.

550
00:47:26,560 --> 00:47:29,250
אנחנו יודעים שמאז שיישמנו פונקציית hash

551
00:47:29,250 --> 00:47:38,420
כך שכל מילה ייחודית תמיד מופיעה באופן חלקי לאותו הערך,

552
00:47:38,420 --> 00:47:43,340
אז אנחנו יודעים שבמקום לחפש דרך שולחן החשיש כל כולו שלנו,

553
00:47:43,340 --> 00:47:48,310
אנחנו באמת יכולים למצוא את הרשימה המקושרת שהמילה שצריכה להשתייך אליו.

554
00:47:48,310 --> 00:47:51,850
אם זה היה במילון, אז זה יהיה בדלי.

555
00:47:51,850 --> 00:47:57,140
מה אנחנו יכולים לעשות, אם מילה היא השם של המחרוזת שלנו עברה ב,

556
00:47:57,140 --> 00:48:01,560
אנחנו יכולים רק חשיש שמילה ומבט ברשימה המקושרת

557
00:48:01,560 --> 00:48:06,410
בשווי של hashtable [החשיש (מילה)].

558
00:48:06,410 --> 00:48:12,410
משם, מה שאנו יכולים לעשות הוא שיש לנו קבוצת משנה קטנה יותר של צמתים כדי לחפש את המילה הזאת,

559
00:48:12,410 --> 00:48:16,770
וכדי שנוכל לעבור את הרשימה המקושרת, באמצעות דוגמה מקודם בהדרכה,

560
00:48:16,770 --> 00:48:24,110
ואז להתקשר מחרוזת להשוות על המילה בכל מקום שהסמן מצביע על,

561
00:48:24,110 --> 00:48:28,430
שמילה, ולראות אם אלה להשוות.

562
00:48:30,280 --> 00:48:35,110
בהתאם לאופן שבו לך לארגן את פונקציית hash שלך,

563
00:48:35,110 --> 00:48:39,260
אם זה מיון, ייתכן שתוכל לחזור כוזב קצת קודם לכן,

564
00:48:39,260 --> 00:48:43,440
אבל אם זה לא ממוין, אז אתה רוצה להמשיך חוצה דרך הרשימה המקושרת שלך

565
00:48:43,440 --> 00:48:46,480
עד שתמצא את הרכיב האחרון של הרשימה.

566
00:48:46,480 --> 00:48:53,320
ואם אתה עדיין לא מצאת את המילה בזמן שכבר הגיע לסוף הרשימה המקושרת,

567
00:48:53,320 --> 00:48:56,890
זה אומר שהמילה שלך לא קיימת במילון,

568
00:48:56,890 --> 00:48:59,410
וכן המילה שאינה חוקית,

569
00:48:59,410 --> 00:49:02,730
וסימון צריך לחזור שווא.

570
00:49:02,730 --> 00:49:09,530
>> כעת אנו מגיעים לפריקה, שבו אנו רוצים לשחרר את כל צומת שיש לנו malloc'd,

571
00:49:09,530 --> 00:49:14,050
כל כך חופשי כל צומת הפנימיים של שולחן החשיש שלנו.

572
00:49:14,050 --> 00:49:20,270
אנחנו הולכים לרוצים לחזר על כל הרשימות המקושרים וכל צומת שבבחינם.

573
00:49:20,270 --> 00:49:29,350
אם תסתכל למעלה בהדרכה לדוגמא שבה אנו משחררים רשימה מקושרת,

574
00:49:29,350 --> 00:49:35,140
אז אתה רוצה לחזור על תהליך שעל כל אלמנט בטבלת החשיש.

575
00:49:35,140 --> 00:49:37,780
ואני מתכוון לעבור על זה לקראת סוף ההדרכה,

576
00:49:37,780 --> 00:49:46,600
אבל Valgrind הוא כלי שבו אתה יכול לראות אם יש לך שחררת כראוי

577
00:49:46,600 --> 00:49:53,600
כל צומת שאתה malloc'd או כל דבר אחר, כי אתה כבר malloc'd, כל מצביע אחר.

578
00:49:55,140 --> 00:50:00,530
אז זה שולחנות חשיש, שם יש לנו מספר סופי של דליים

579
00:50:00,530 --> 00:50:09,220
ופונקציית hash שייקח ערך ולאחר מכן להקצות את הערך שלדלי מסוים.

580
00:50:09,220 --> 00:50:13,340
>> כעת אנו מגיעים לניסיונות.

581
00:50:13,340 --> 00:50:18,750
מנסה סוג של מבט כזה, ואני גם מצייר את דוגמה.

582
00:50:18,750 --> 00:50:25,630
בעיקרון, יש לך שורה שלמה של מכתבים פוטנציאליים,

583
00:50:25,630 --> 00:50:29,210
ואז כל פעם שאתה בונה מילה,

584
00:50:29,210 --> 00:50:36,490
מכתב שיכול להיות מקושר למילון למגוון רחב של אפשרויות.

585
00:50:36,490 --> 00:50:40,840
כמה מילים להתחיל עם C אבל אז תמשכנה עם,

586
00:50:40,840 --> 00:50:42,960
אבל אחרים ימשיכו בO, למשל.

587
00:50:42,960 --> 00:50:51,090
איירי היא דרך של לדמיין את כל הצירופים האפשריים של המילים האלה.

588
00:50:51,090 --> 00:50:59,070
איירי הולכת לעקוב אחר הרצף של אותיות המרכיבות את מילים,

589
00:50:59,070 --> 00:51:08,280
הסתעפות בעת צורך, כאשר ניתן בעקבות מכתב אחד בכפולה של מכתבים,

590
00:51:08,280 --> 00:51:16,630
ובסופו מצביעים בכל נקודה אם המילה שהיא חוקית או לא

591
00:51:16,630 --> 00:51:30,120
כי אם אתה איות המילה MAT, תואר שני אני לא חושב שמילה הוא חוקית, אבל MAT הוא.

592
00:51:30,120 --> 00:51:37,820
וכך באיירי שלך, זה היה מציין כי לאחר MAT זה בעצם מילה תקפה.

593
00:51:41,790 --> 00:51:48,590
בכל צומת באיירי היא בעצם הולכת למכילה מערך של מצביעי צומת,

594
00:51:48,590 --> 00:51:52,970
ואנחנו הולכים לעשות, במיוחד, 27 של מצביעי הצומת האלה,

595
00:51:52,970 --> 00:52:00,550
אחד לכל אות באלף הבית, כמו גם את אופי הגרש.

596
00:52:00,550 --> 00:52:10,450
כל אלמנט שבמערך עצמו הולך להצביע לצומת אחרת.

597
00:52:10,450 --> 00:52:14,020
אז אם צומת שהוא NULL, אם אין שום דבר אחרי זה,

598
00:52:14,020 --> 00:52:20,550
אז אנחנו יודעים שאין עוד מכתבים שבמילת רצף.

599
00:52:20,550 --> 00:52:26,950
אבל אם צומת שאינה NULL, זה אומר שיש יותר אותיות שברצף אותיות.

600
00:52:26,950 --> 00:52:32,160
ולאחר מכן מעבר לכך, בכל צומת מציינת אם זה התו האחרון של מילה או לא.

601
00:52:38,110 --> 00:52:43,170
>> בואו נלך לדוגמה של איירי.

602
00:52:50,500 --> 00:52:58,340
ראשית יש לי חדר במשך 27 צומת במערך הזה.

603
00:52:58,340 --> 00:53:03,200
אם יש לי מילה ברת -

604
00:53:13,310 --> 00:53:15,370
אם יש לי את המילה ברה ואני רוצה להוסיף כי ב,

605
00:53:15,370 --> 00:53:22,700
האות הראשונה היא ב ', כך שאם איירי שלי ריק,

606
00:53:22,700 --> 00:53:29,910
ב 'הוא האות השנייה של האלפבית, אז אני הולך לבחור לשים את זה כאן במדד זה.

607
00:53:29,910 --> 00:53:33,450
אני הולך להיות כאן ב '.

608
00:53:33,450 --> 00:53:42,400
B הולך להיות צומת שמצביע למערך נוסף של כל הדמויות האפשריות

609
00:53:42,400 --> 00:53:45,870
שיכול לעקוב אחרי המכתב ב '

610
00:53:45,870 --> 00:53:57,610
במקרה זה, אני מתמודד עם המילה הברה, כך ילך כאן.

611
00:54:02,000 --> 00:54:08,990
אחרי, יש לי את אות R, אז A נקודות עכשיו כדי השילוב שלה,

612
00:54:08,990 --> 00:54:15,120
ואז R יהיה כאן.

613
00:54:15,120 --> 00:54:22,470
בר הוא מילה שלמה, אז אני הולך יש נקודת R לצומת אחרת

614
00:54:22,470 --> 00:54:33,990
שאומר שמילה שהיא בתוקף.

615
00:54:36,010 --> 00:54:40,970
כי צומת היא גם הולך להיות מערך של צמתים,

616
00:54:40,970 --> 00:54:45,260
אבל אלה עשויים להיות NULL.

617
00:54:45,260 --> 00:54:49,080
אבל בעצם, זה יכול להמשיך ככה.

618
00:54:49,080 --> 00:54:54,250
שיהפוך לקצת יותר ברור כאשר אנו הולכים לדוגמה אחרת,

619
00:54:54,250 --> 00:54:56,780
אז פשוט תהיה סבלני איתי שם.

620
00:54:56,780 --> 00:55:02,050
עכשיו יש לנו בר הפנימי של המילון שלנו.

621
00:55:02,050 --> 00:55:05,980
עכשיו אומרים שיש לנו מילה באז.

622
00:55:05,980 --> 00:55:12,630
אנחנו מתחילים עם ב ', וכבר יש לנו ב' כאחד מהמכתבים שנמצאו במילון שלנו.

623
00:55:12,630 --> 00:55:15,170
אחרי זה עם א 'יש לנו כבר.

624
00:55:15,170 --> 00:55:19,250
אבל אז במקום זה, יש לנו בא Z.

625
00:55:19,250 --> 00:55:25,490
אז אלמנט במערך שלנו הולך להיות Z,

626
00:55:25,490 --> 00:55:30,810
וכך אז שאחד לא הולך להצביע לסיום חוקי אחר של המילה.

627
00:55:30,810 --> 00:55:36,930
כך אנו רואים שכאשר אנו ממשיכים דרך B ולאחר מכן,

628
00:55:36,930 --> 00:55:43,480
יש שתי אפשרויות שונות כרגע במילון שלנו למילים שמתחילות ב-B וא

629
00:55:49,650 --> 00:55:57,460
אומר שאנחנו רוצים להוסיף את המילה foobar.

630
00:55:57,460 --> 00:56:05,620
אז אנחנו נעשה את כניסה בפ

631
00:56:05,620 --> 00:56:11,320
F הוא צומת שמצביעה על כל מערך.

632
00:56:11,320 --> 00:56:22,790
היינו מוצא O, ללכת להו, הו, אז קישורים לכל רשימה.

633
00:56:22,790 --> 00:56:35,340
שנהיה לנו ב 'ולאחר מכן נמשיך, נהיה לנו, ואז ר'

634
00:56:35,340 --> 00:56:43,570
אז חוצה foobar כל הדרך למטה עד foobar היא מילה נכונה.

635
00:56:43,570 --> 00:56:52,590
וכך אז זה יהיה מילה תקפה.

636
00:56:52,590 --> 00:57:00,170
עכשיו תגיד את המילה הבאה שלנו במילון היא למעשה המילה FOO.

637
00:57:00,170 --> 00:57:03,530
היינו אומר פ 'מה להלן F?

638
00:57:03,530 --> 00:57:06,190
אני בעצם כבר יש לך מקום לO, אז אני הולך להמשיך.

639
00:57:06,190 --> 00:57:09,150
אני לא צריך לעשות אחת חדשה. המשך.

640
00:57:09,150 --> 00:57:15,500
FOO הוא מילה חוקית במילון זה, אז אני הולך להצביע

641
00:57:15,500 --> 00:57:21,660
שזה חוקי.

642
00:57:21,660 --> 00:57:28,370
אם אני אעצור את הרצף שלי שם, זה יהיה נכון.

643
00:57:28,370 --> 00:57:33,050
אבל אם המשכנו הרצף שלנו מFOO למטה ל-B

644
00:57:33,050 --> 00:57:39,750
ופשוט הייתה לי FOOB, FOOB היא לא מילה, וזה לא צוין כתקין.

645
00:57:47,370 --> 00:57:57,600
באיירי, שכל צומת שמציינת אם זה חוקי או לא מילה,

646
00:57:57,600 --> 00:58:05,840
ולאחר מכן בכל צומת יש גם מערך של 27 מצביעי צומת

647
00:58:05,840 --> 00:58:09,520
שלאחר מכן צבע על צומת עצמם.

648
00:58:09,520 --> 00:58:12,940
>> הנה דרך של איך ייתכן שתרצה להגדיר את זה.

649
00:58:12,940 --> 00:58:17,260
עם זאת, בדיוק כמו בדוגמא שולחן החשיש, שבו היה לנו ראש * צומת

650
00:58:17,260 --> 00:58:21,320
כדי לציין את תחילתה של הרשימה המקושרת שלנו, אנחנו גם נרצה

651
00:58:21,320 --> 00:58:29,150
איזו דרך לדעת לאן תחילת איירי היא.

652
00:58:29,150 --> 00:58:34,110
כמה אנשים קוראים מנסה עצים, ושם שורש מגיע מ.

653
00:58:34,110 --> 00:58:36,910
אז אנחנו רוצים השורש של העץ שלנו כדי לוודא שאנחנו נישאר מקורקעים

654
00:58:36,910 --> 00:58:39,570
לכל המקום שאיירי היא.

655
00:58:42,910 --> 00:58:46,300
כבר אנחנו סוג של ניגשנו

656
00:58:46,300 --> 00:58:50,240
כפי שאתה יכול לחשוב על כל מילת טעינה למילון.

657
00:58:50,240 --> 00:58:54,540
בעיקרו של דבר, לכל מילה שאתה הולך רוצה לחזר דרך איירי

658
00:58:54,540 --> 00:58:59,590
וידיעה שכל אלמנט בילדים - שקראנו לו ילדים במקרה זה -

659
00:58:59,590 --> 00:59:04,290
מתאים לאות אחרת, אתה הולך רוצה לבדוק ערכים אלה

660
00:59:04,290 --> 00:59:08,320
באותו מדד מסוים שמתאים למכתב.

661
00:59:08,320 --> 00:59:11,260
אז חשבתי כל הדרך חזרה לקיסר וVigenere,

662
00:59:11,260 --> 00:59:16,070
ידיעה שכל אות שאתה יכול מעין המפה חזרה לאינדקס אלפביתי,

663
00:59:16,070 --> 00:59:20,690
בהחלט עד Z הולך להיות די קלה למיפוי למכתב אלפביתי,

664
00:59:20,690 --> 00:59:25,200
אך למרבה הצער, גרשיים הם גם דמות מקובלת במילים.

665
00:59:25,200 --> 00:59:31,650
אני אפילו לא בטוח מה ערך ASCII הוא,

666
00:59:31,650 --> 00:59:39,250
כך שלאם אתה רוצה למצוא את אינדקס כדי להחליט אם אתה רוצה את זה כדי להיות ראשון

667
00:59:39,250 --> 00:59:44,550
או האחרון, תצטרך לבצע בדיקה מקודדת קשה בשביל זה

668
00:59:44,550 --> 00:59:48,930
ואז לשים את זה בעמוד 26, למשל.

669
00:59:48,930 --> 00:59:55,300
אז אתה בודק את הערך בילדים [i]

670
00:59:55,300 --> 00:59:58,400
שם [i] מקבילה לכל מכתב שאתה.

671
00:59:58,400 --> 01:00:04,110
אם זה NULL, זה אומר שאין כרגע כל מכתבים אפשריים

672
01:00:04,110 --> 01:00:08,150
נובע מהרצף הקודם, אז אתה הולך רוצה malloc

673
01:00:08,150 --> 01:00:13,150
ולהפוך את צומת חדשה ויש לי שילדים [i] צבע עליו

674
01:00:13,150 --> 01:00:17,890
כך שאתה יוצר - כאשר הכנסנו מכתב למלבן -

675
01:00:17,890 --> 01:00:23,680
קבלת ילדים שאינם ריקה ונקודה שלצומת החדשה.

676
01:00:23,680 --> 01:00:28,340
אבל אם זה לא ריק, כמו בדוגמא שלנו FOO

677
01:00:28,340 --> 01:00:34,570
כאשר כבר היו לנו foobar, אנחנו ממשיכים,

678
01:00:34,570 --> 01:00:44,010
ואנחנו לא תמיד עושים צומת חדש אלא רק הגדרת is_word לאמיתי

679
01:00:44,010 --> 01:00:47,790
בסוף של מילה.

680
01:00:50,060 --> 01:00:55,340
>> אז כמו קודם, כי כאן יש לך עסק עם כל אות בכל פעם,

681
01:00:55,340 --> 01:01:01,470
זה הולך להיות יותר קל לך לגודל, במקום שיש לחשב

682
01:01:01,470 --> 01:01:06,910
ולעבור את כל העץ ולחשב כמה ילדים יש לי

683
01:01:06,910 --> 01:01:10,850
ולאחר מכן הסתעפות, נזכר כמה מהם בצד השמאל ובצד ימין

684
01:01:10,850 --> 01:01:12,850
ודברים כאלה, זה הולכים להיות הרבה יותר קל לך

685
01:01:12,850 --> 01:01:16,220
אם אתה רק לעקוב אחר כמה מילים אתה מוסיף ב

686
01:01:16,220 --> 01:01:18,080
כאשר אתה מתעסק עם עומס.

687
01:01:18,080 --> 01:01:22,630
ואם כך, שדרך הגודל יכול פשוט להחזיר משתנה גלובלי של גודל.

688
01:01:25,320 --> 01:01:28,530
>> כעת אנו מגיעים לסימון.

689
01:01:28,530 --> 01:01:33,920
סטנדרטים כמו קודם, שבו אנחנו רוצים לאפשר למקרה חוסר רגישות.

690
01:01:33,920 --> 01:01:40,400
כמו כן, אנו מניחים כי בחוטים הם להשתמש באותיות בלבד או את הגרשיים

691
01:01:40,400 --> 01:01:44,000
מכיוון שילדים הוא מערך של 27 ארוכים,

692
01:01:44,000 --> 01:01:48,480
לכן כל האותיות האלפבית בתוספת הגרש.

693
01:01:48,480 --> 01:01:53,800
ללבדוק מה שאתה רוצה לעשות היא שאתה רוצה להתחיל בשורש

694
01:01:53,800 --> 01:01:58,440
כי השורש יצביע על מערך שמכיל

695
01:01:58,440 --> 01:02:01,630
כל האותיות החל האפשריות של מילה.

696
01:02:01,630 --> 01:02:03,680
אתה הולך להתחיל שם,

697
01:02:03,680 --> 01:02:11,590
ואז אתה הולך לבדוק הוא NULL זה ערך או לא,

698
01:02:11,590 --> 01:02:16,490
כי אם הערך הוא NULL, זה אומר שהמילון לא מכיל ערכים

699
01:02:16,490 --> 01:02:21,480
שמכיל מכתב שלפי סדר מסוים.

700
01:02:21,480 --> 01:02:24,970
אם NULL זה, אז זה אומר שהמילה שגויה באופן מיידי.

701
01:02:24,970 --> 01:02:27,110
אבל אם זה לא ריק, אז אתה יכול להמשיך,

702
01:02:27,110 --> 01:02:34,090
אומר שהאות הראשונה היא אות ראשונה במילה אפשרית,

703
01:02:34,090 --> 01:02:40,630
אז עכשיו אני רוצה לבדוק אם המכתב השני, הרצף הזה, נמצא במילון שלי.

704
01:02:40,630 --> 01:02:46,540
אז אתה הולך למדד של ילדי הצומת הראשונה

705
01:02:46,540 --> 01:02:50,720
ולבדוק אם זה מכתב שני קיים.

706
01:02:50,720 --> 01:02:57,440
ואז אתה חוזר על תהליך שכדי לבדוק אם הרצף שהוא חוקי או לא

707
01:02:57,440 --> 01:02:59,060
בתוך איירי.

708
01:02:59,060 --> 01:03:06,430
כל פעם שילדי צומת באותו נקודתי מדד ל NULL,

709
01:03:06,430 --> 01:03:10,710
אתה יודע שרצף שלא קיים,

710
01:03:10,710 --> 01:03:16,230
אבל אז אם אתה מגיע לסוף של המילה, כי אתה כבר הוזנת,

711
01:03:16,230 --> 01:03:20,070
אז אתה רוצה לבדוק עכשיו אחרי שהשלמתי את הרצף הזה

712
01:03:20,070 --> 01:03:27,610
ומצאתי אותו בתוכי איירי, היא מילה חוקית או לא זה?

713
01:03:27,610 --> 01:03:32,480
וכך אז אתה רוצה לבדוק את זה, וזה כאשר אם כבר מצא את הרצף הזה,

714
01:03:32,480 --> 01:03:35,120
אז אתה רוצה לבדוק אם המילה שהיא חוקית או לא

715
01:03:35,120 --> 01:03:40,290
כי תזכור בחזרה במקרה הקודם שבו ציירתי לנו FOOB,

716
01:03:40,290 --> 01:03:48,410
זה היה רצף חוקי שמצאנו אבל לא היה מילה תקפה בפועל עצמו.

717
01:03:50,570 --> 01:03:59,000
>> בדומה לכך, לפריקה בניסיונות שאתה רוצה לפרוק את כל צומת באיירי.

718
01:03:59,000 --> 01:04:04,790
סליחה. דומה לטבלאות בי החשיש בלפורקנו שחררתי את כל צומת,

719
01:04:04,790 --> 01:04:09,740
בניסיונות שאנחנו רוצים גם לשחרר את כל צומת.

720
01:04:09,740 --> 01:04:15,000
לפרוק יהיה ממש לעבוד קל מלמטה למעלה

721
01:04:15,000 --> 01:04:19,290
כי אלה הם רשימות המקושרים במהות.

722
01:04:19,290 --> 01:04:22,540
אז אנחנו רוצים לוודא שאנחנו נאחזים בכל הערכים

723
01:04:22,540 --> 01:04:25,700
וחופשי לכולם באופן מפורש.

724
01:04:25,700 --> 01:04:28,840
מה אתה הולך רוצה לעשות אם אתה עובד עם איירי

725
01:04:28,840 --> 01:04:35,640
הוא לנסוע לתחתית והחופשית הצומת הנמוכה ביותר האפשרית 1

726
01:04:35,640 --> 01:04:39,190
ואז לעלות לכל הילדים האלה ואחר כך חופשיים כל אלה,

727
01:04:39,190 --> 01:04:43,050
עולה ואז חופשיים וכו ',

728
01:04:43,050 --> 01:04:48,790
כמו סוג של התמודדות עם השכבה התחתונה של איירי 1

729
01:04:48,790 --> 01:04:51,940
ואז הולך למעלה ברגע ששחררת את הכל.

730
01:04:51,940 --> 01:04:56,720
זו דוגמה טובה למקום בו פונקציה רקורסיבית יכולה להיות שימושי.

731
01:04:56,720 --> 01:05:03,830
לאחר ששחררת את השכבה התחתונה של איירי,

732
01:05:03,830 --> 01:05:08,000
אז אתה קורא לפרוק על כל השאר,

733
01:05:08,000 --> 01:05:13,620
וודא כי אתה לשחרר כל מיני -

734
01:05:13,620 --> 01:05:16,410
אתה סוג של יכול לדמיין את זה כניסיונות מיניים.

735
01:05:23,300 --> 01:05:28,990
אז יש לך שורש שלך כאן.

736
01:05:30,840 --> 01:05:35,230
אני רק לפשט את זה אז אני לא צריך לצייר 26 מהם.

737
01:05:37,250 --> 01:05:43,770
אז יש לך אלה, ולאחר מכן אלה מייצגים רצפים של מילים

738
01:05:43,770 --> 01:05:54,620
שבו כל העיגולים הקטנים האלה הם מכתבים שהם רצפים חוקיים של אותיות.

739
01:06:03,040 --> 01:06:07,160
בואו נמשיך עוד קצת.

740
01:06:15,110 --> 01:06:25,750
מה אתה הולך רוצה לעשות הוא חופשי תחתון כאן ואז זה בחינם 1

741
01:06:25,750 --> 01:06:31,640
ואז זה בחינם אחד בתחתית לפני שתשחרר את האחד למעלה כאן

742
01:06:31,640 --> 01:06:38,180
כי אם משהו חופשי ברמה השנייה כאן,

743
01:06:38,180 --> 01:06:47,230
אז אתה בעצם היה מאבד את הערך הזה כאן.

744
01:06:47,230 --> 01:06:54,780
לכן זה חשוב בלפרוק לאיירי כדי לוודא שאתה לשחרר את התחתית ראשונה.

745
01:06:54,780 --> 01:06:59,480
מה שאולי תרצה לעשות הוא לומר לכל צומת

746
01:06:59,480 --> 01:07:06,430
אני רוצה שאפרוק את כל הילדים.

747
01:07:16,060 --> 01:07:22,140
>> עכשיו שאנחנו כבר נעלמנו מעל לפרוק לשיטת שולחן החשיש, כמו גם שיטת איירי,

748
01:07:22,140 --> 01:07:27,020
אנחנו הולכים רוצים להסתכל על Valgrind.

749
01:07:27,020 --> 01:07:29,640
Valgrind אתם רצים עם את הפקודות הבאות.

750
01:07:29,640 --> 01:07:32,700
יש לך valgrind-V.

751
01:07:32,700 --> 01:07:40,960
אתה בודק עבור כל ההדלפות כאשר אתה מפעיל אית ניתן טקסט המסוים הזה

752
01:07:40,960 --> 01:07:46,980
בגלל איות צריכה לקחת בקובץ טקסט.

753
01:07:46,980 --> 01:07:52,330
אז Valgrind יהיה להפעיל את התכנית שלך, להגיד לך כמה בתים שהוקצית,

754
01:07:52,330 --> 01:07:57,150
כמה בתים ששוחררת, ואת זה יגיד לך אם אתה משוחרר מספיק

755
01:07:57,150 --> 01:07:58,930
או אם אתה לא חופשי מספיק,

756
01:07:58,930 --> 01:08:02,850
או לפעמים אתה יכול אפילו על חינם, כמו חופשית צומת שכבר שוחררת

757
01:08:02,850 --> 01:08:05,140
ואז זה יחזיר לך שגיאות.

758
01:08:05,140 --> 01:08:11,600
אם אתה משתמש Valgrind, זה ייתן לך כמה הודעות

759
01:08:11,600 --> 01:08:15,970
המציינת אם אתה כבר שחררת או פחות ממספיק, מספיק,

760
01:08:15,970 --> 01:08:19,609
או יותר ממספיק פעמים.

761
01:08:24,370 --> 01:08:30,410
>> חלק מpset זה, זה לא חובה לאתגר את הלוח הגדול.

762
01:08:30,410 --> 01:08:35,790
אבל כאשר יש לנו עסק עם מבני נתונים אלה

763
01:08:35,790 --> 01:08:40,689
זה סוג של כיף לראות כמה מהר וכמה יעילים מבני הנתונים שלך יכולים להיות.

764
01:08:40,689 --> 01:08:44,490
האם תוצאת פונקציית hash בהרבה התנגשויות?

765
01:08:44,490 --> 01:08:46,300
או שגודל הנתונים שלך ממש גדול?

766
01:08:46,300 --> 01:08:49,420
זה לוקח הרבה זמן לעבור?

767
01:08:49,420 --> 01:08:54,800
ביומן של איות, זה פלטים כמה זמן אתה משתמש לטעינה,

768
01:08:54,800 --> 01:08:57,700
כדי לבדוק, לנהל גודל, ולפרוק,

769
01:08:57,700 --> 01:09:00,720
ולכן אלה מתפרסמים בלוח הגדול,

770
01:09:00,720 --> 01:09:03,600
שבו תוכל להתחרות נגד חבריך לכיתת

771
01:09:03,600 --> 01:09:11,350
וכמה חברי צוות כדי לראות שיש לו את בודק האיות המהירה ביותר.

772
01:09:11,350 --> 01:09:14,760
דבר אחד שהייתי רוצה לציין על שולחנות חשיש

773
01:09:14,760 --> 01:09:20,470
הן שיש כמה פונקציות hash די פשוטות שאנחנו יכולים לחשוב עליו.

774
01:09:20,470 --> 01:09:27,240
לדוגמה, יש לך 26 דליים, ואז כל דלי

775
01:09:27,240 --> 01:09:30,200
מתאים לאות הראשונה במילה,

776
01:09:30,200 --> 01:09:35,229
אבל זה הולך לגרום לשולחן חשיש די לא מאוזן

777
01:09:35,229 --> 01:09:40,979
כי יש דברים הרבה פחות שמתחילים עם X מהתחלה עם M, למשל.

778
01:09:40,979 --> 01:09:47,890
דרך אחת ללכת על אית היא אם אתה רוצה לקבל את כל הפונקציונליות האחרת למטה,

779
01:09:47,890 --> 01:09:53,240
אז פשוט להשתמש בפונקציית hash פשוט כדי להיות מסוגל לקבל את הקוד שלך פועל

780
01:09:53,240 --> 01:09:58,650
ולאחר מכן לחזור ולשנות את הגודל של שולחן החשיש ואת ההגדרה.

781
01:09:58,650 --> 01:10:03,430
יש הרבה משאבים באינטרנט לפונקציות hash,

782
01:10:03,430 --> 01:10:08,250
וכן לpset זה אתה רשאי לחקור פונקציות hash באינטרנט

783
01:10:08,250 --> 01:10:15,560
לכמה רמזים והשראה, כל עוד אתה מקפיד לצטט איפה קנית אותו מ.

784
01:10:15,560 --> 01:10:22,060
אתם מוזמנים לחפש ולפרש חלק פונקציית hash שאתה מוצא באינטרנט.

785
01:10:22,060 --> 01:10:27,460
אחזור לזה, ייתכן שתוכל, כדי לראות אם מישהו השתמש איירי

786
01:10:27,460 --> 01:10:31,700
אם היישום שלהם הוא מהיר יותר מאשר שולחן החשיש או לא.

787
01:10:31,700 --> 01:10:35,290
אתה יכול להגיש ללוח הגדול מספר פעמים.

788
01:10:35,290 --> 01:10:37,660
זה יהיה להקליט הכניסה האחרונה שלך.

789
01:10:37,660 --> 01:10:44,300
אז אולי תשנה את פונקציית hash שלך ואז אני מבין שבעצם זה הרבה יותר מהר

790
01:10:44,300 --> 01:10:46,780
או הרבה יותר איטי מאשר בעבר.

791
01:10:46,780 --> 01:10:50,960
זה קצת דרך מהנה.

792
01:10:50,960 --> 01:10:57,190
תמיד יש 1 או 2 אנשי צוות שמנסים להפוך את המילון האיטי ביותר האפשרי,

793
01:10:57,190 --> 01:11:00,210
כך שתמיד כיף להסתכל עליו.

794
01:11:00,210 --> 01:11:07,630
>> השימוש לpset הוא שאתה מפעיל אית עם מילון אופציונלי

795
01:11:07,630 --> 01:11:12,840
ואז קובץ טקסט חובה.

796
01:11:12,840 --> 01:11:18,380
כברירת מחדל כאשר אתה מפעיל אית רק עם קובץ טקסט ולא תציין מילון,

797
01:11:18,380 --> 01:11:24,410
זה הולך להשתמש בקובץ טקסט המילון, אחד הגדול

798
01:11:24,410 --> 01:11:27,920
בתיקיית cs50/pset5/dictionaries.

799
01:11:27,920 --> 01:11:32,760
אחד שיש מעל 100,000 מילים.

800
01:11:32,760 --> 01:11:37,950
יש להם גם מילון קטן שבו יש הרבה פחות מילים

801
01:11:37,950 --> 01:11:40,730
שCS50 עשה בשבילך.

802
01:11:40,730 --> 01:11:44,050
עם זאת, אתה יכול מאוד בקלות פשוט לעשות מילון משלך

803
01:11:44,050 --> 01:11:47,150
אם אתה רק רוצה שזה עובד בדוגמאות קטנות -

804
01:11:47,150 --> 01:11:51,140
למשל, אם ברצונך להשתמש gdb ואתה יודע את הערכים הספציפיים

805
01:11:51,140 --> 01:11:53,560
שברצונך לשולחן החשיש למפות ל.

806
01:11:53,560 --> 01:12:00,430
אז אתה יכול פשוט להפוך את קובץ הטקסט שלך רק עם בר, באז, פ.ו., וfoobar,

807
01:12:00,430 --> 01:12:04,860
לעשות את זה בקובץ טקסט, פרד כל אלה עם קו 1,

808
01:12:04,860 --> 01:12:12,670
ולאחר מכן להפוך את קובץ הטקסט שלך, פשוטו כמשמעו, שמכיל אולי 1 או 2 מילים בלבד

809
01:12:12,670 --> 01:12:15,950
כך שאתה יודע בדיוק מה צריך להיות הפלט.

810
01:12:15,950 --> 01:12:21,870
חלק מקבצי הטקסט לדוגמא שעל הלוח הגדול כשאתה מפעיל את האתגר יבדוק

811
01:12:21,870 --> 01:12:25,580
הם מלחמה ושלום ורומן אוסטן ג'יין או משהו כזה.

812
01:12:25,580 --> 01:12:30,450
לכן, כאשר אתה מתחיל, זה הרבה יותר קל לעשות קבצי טקסט משלך

813
01:12:30,450 --> 01:12:34,160
שמכיל רק כמה מילים או אולי 10

814
01:12:34,160 --> 01:12:38,280
כך שאתה יכול לחזות מה יהיה התוצאה צריכה להיות

815
01:12:38,280 --> 01:12:42,880
ואז לבדוק את זה מול זה, ולכן יותר מדוגמה מבוקרת.

816
01:12:42,880 --> 01:12:45,820
וכך מאז שאנחנו עוסקים בניבוי וציור דברים מסביב,

817
01:12:45,820 --> 01:12:48,690
שוב אני רוצה לעודד אותך להשתמש בעט ונייר

818
01:12:48,690 --> 01:12:50,700
כי זה באמת הולך לעזור לך עם זה -

819
01:12:50,700 --> 01:12:55,620
ציור החצים, איך שולחן החשיש או איך איירי שלך נראית,

820
01:12:55,620 --> 01:12:57,980
כשאתה משחרר משהו שבו החצים הולכים,

821
01:12:57,980 --> 01:13:01,730
אתה מחזיק במספיק, אתה רואה כל קשר נעלם

822
01:13:01,730 --> 01:13:05,750
ונופל לתהום של זיכרון דלף.

823
01:13:05,750 --> 01:13:11,070
אז אנא, נסה לצייר אותו עוד לפני שמגיע לכתיבת קוד.

824
01:13:11,070 --> 01:13:14,520
לצייר דברים החוצה, כך שאתה מבין איך דברים הולכים לעבוד

825
01:13:14,520 --> 01:13:22,750
כי אז אני מבטיח לך לרוץ לתוך מבוכות מצביע פחות שם.

826
01:13:24,270 --> 01:13:25,910
>> בסדר.

827
01:13:25,910 --> 01:13:28,780
אני רוצה לאחל לך את הטוב ביותר של מזל עם pset זה.

828
01:13:28,780 --> 01:13:31,980
זה כנראה הכי הקשה.

829
01:13:31,980 --> 01:13:40,360
אז נסה להתחיל מוקדם, לצייר דברים החוצה, לצייר דברים, ומזל טוב.

830
01:13:40,360 --> 01:13:42,980
זה היה Walkthrough 5.

831
01:13:45,160 --> 01:13:47,000
>> [CS50.TV]