1
00:00:00,000 --> 00:00:12,350
>> [השמעת מוסיקה]

2
00:00:12,350 --> 00:00:13,050
>> ROB אודן: היי.

3
00:00:13,050 --> 00:00:13,640
אני רוב.

4
00:00:13,640 --> 00:00:16,210
ובואו פתרון זה החוצה.

5
00:00:16,210 --> 00:00:20,070
אז הנה אנחנו הולכים ליישם
שולחן רחב.

6
00:00:20,070 --> 00:00:24,090
אנו רואים כי צומת struct שלנו
השולחן הולך להיראות כך.

7
00:00:24,090 --> 00:00:28,710
אז זה הולך להיות מילת char
מערך של אורך גודל + 1.

8
00:00:28,710 --> 00:00:32,259
אל תשכח + 1, שכן לכל היותר
מילה במילון היא 45

9
00:00:32,259 --> 00:00:33,130
תווים.

10
00:00:33,130 --> 00:00:37,070
ואז אנחנו הולכים צריכים אחד נוסף
אופי לאפס הקו הנטוי ההפוך.

11
00:00:37,070 --> 00:00:40,870
>> ולאחר מכן hashtable שלנו בכל אחד
דלי הולך לאחסון

12
00:00:40,870 --> 00:00:42,320
רשימה מקושרת של צמתים.

13
00:00:42,320 --> 00:00:44,420
אנחנו לא עושים ליניארי חיטוט כאן.

14
00:00:44,420 --> 00:00:48,430
וזאת על מנת לקשר למשנהו
אלמנט בדלי, שאנחנו צריכים

15
00:00:48,430 --> 00:00:50,390
צומת struct * הבא.

16
00:00:50,390 --> 00:00:51,110
על אישור.

17
00:00:51,110 --> 00:00:53,090
אז זה מה שצומת נראית.

18
00:00:53,090 --> 00:00:56,180
>> עכשיו היא כאן ההכרזה
של hashtable שלנו.

19
00:00:56,180 --> 00:00:59,640
זה הולך להיות 16,834 דליים.

20
00:00:59,640 --> 00:01:01,910
אבל מספר זה לא ממש משנה.

21
00:01:01,910 --> 00:01:05,450
ולבסוף, אנחנו הולכים יש לי
גודל hashtable משתנה גלובלי, אשר

22
00:01:05,450 --> 00:01:07,000
הוא הולך להתחיל כמו אפס.

23
00:01:07,000 --> 00:01:10,760
וזה הולך לעקוב אחר אופן
מילות רבות נמצאות במילון שלנו.

24
00:01:10,760 --> 00:01:13,710
>> אז בואו נסתכל על עומס.

25
00:01:13,710 --> 00:01:16,390
שים לב שעומס, היא מחזירה bool.

26
00:01:16,390 --> 00:01:20,530
אתה חוזר נכון אם זה היה בהצלחה
נטען, ושקר אחר.

27
00:01:20,530 --> 00:01:23,990
וזה לוקח מילון char * const,
המהווה את המילון

28
00:01:23,990 --> 00:01:25,280
כי אנחנו רוצים לפתוח.

29
00:01:25,280 --> 00:01:27,170
אז זה הדבר הראשון
אנחנו הולכים לעשות.

30
00:01:27,170 --> 00:01:29,500
>> אנחנו הולכים fopen
מילון לקריאה.

31
00:01:29,500 --> 00:01:31,680
ואנחנו הולכים צריכים לעשות
בטוח שזה הצליח.

32
00:01:31,680 --> 00:01:35,920
אז אם זה חזר NULL, אז אנחנו לא
בהצלחה לפתוח את המילון.

33
00:01:35,920 --> 00:01:37,440
ואנחנו צריכים לחזור שווא.

34
00:01:37,440 --> 00:01:41,580
אבל בהנחה שזה עשה בהצלחה
פתוח, אז אנחנו רוצים לקרוא

35
00:01:41,580 --> 00:01:42,400
מילון.

36
00:01:42,400 --> 00:01:46,450
אז לשמור על הלולאה עד שנמצא כמה
סיבה לפרוץ את המעגל הזה,

37
00:01:46,450 --> 00:01:47,570
שבו אנו נראה.

38
00:01:47,570 --> 00:01:48,920
אז לשמור על לולאות.

39
00:01:48,920 --> 00:01:51,780
>> ועכשיו אנחנו הולכים
malloc צומת אחת.

40
00:01:51,780 --> 00:01:54,020
וכמובן שאנחנו צריכים
כדי לאוורר לבדוק שוב.

41
00:01:54,020 --> 00:01:58,680
אז אם mallocing לא הצליח, ואז
אנחנו רוצים לפרוק את כל צומת שאנחנו

42
00:01:58,680 --> 00:02:02,590
קרה לי malloc לפני, סגור את
מילון ותמורת שווא.

43
00:02:02,590 --> 00:02:06,830
אבל התעלמות שאנחנו בהנחה,
הצלחנו, אז אנחנו רוצים להשתמש fscanf

44
00:02:06,830 --> 00:02:12,400
לקרוא לו מילה אחת משלנו
מילון לצומת שלנו.

45
00:02:12,400 --> 00:02:17,940
אז לזכור כי כניסה> מילה הוא char
מילת חיץ של LENGHTH גודל + 1

46
00:02:17,940 --> 00:02:20,300
שאנחנו הולכים לאחסן את המילה פנימה

47
00:02:20,300 --> 00:02:25,070
>> אז fscanf הולך להחזיר 1, עוד
כפי שהיה מסוגל בהצלחה

48
00:02:25,070 --> 00:02:26,750
לקרוא מילה מהקובץ.

49
00:02:26,750 --> 00:02:30,460
אם אחד שגיאה קורה, או שאנחנו
להגיע לסוף של הקובץ, זה

50
00:02:30,460 --> 00:02:31,950
לא יחזור 1.

51
00:02:31,950 --> 00:02:35,180
ובמקרה זה לא יחזור 1,
אנחנו סוף סוף הולכים לפרוץ

52
00:02:35,180 --> 00:02:37,280
בעוד לולאה זו.

53
00:02:37,280 --> 00:02:42,770
כך אנו רואים כי ברגע שיש לנו בהצלחה
לקרוא מילה לתוך

54
00:02:42,770 --> 00:02:48,270
כניסה> מילה, ואז אנחנו הולכים לזה
מילה באמצעות פונקציית hash שלנו.

55
00:02:48,270 --> 00:02:49,580
>> בואו נסתכל על
פונקציית hash.

56
00:02:49,580 --> 00:02:52,430

57
00:02:52,430 --> 00:02:55,610
אז אתה לא באמת צריך
כדי להבין את זה.

58
00:02:55,610 --> 00:02:59,460
ובעצם אנחנו רק משכתי חשיש זה
לתפקד מהאינטרנט.

59
00:02:59,460 --> 00:03:04,010
הדבר היחיד שאתה צריך להכיר הוא
כי זה לוקח מילת char * const.

60
00:03:04,010 --> 00:03:08,960
אז זה לוקח מחרוזת כקלט, ו
חוזר int חתום כפלט.

61
00:03:08,960 --> 00:03:12,360
אז זה כל פונקצית חשיש הוא, האם זה
לוקח בקלט ונותן לך

62
00:03:12,360 --> 00:03:14,490
מדד לhashtable.

63
00:03:14,490 --> 00:03:18,530
>> שים לב שאנחנו moding ידי NUM_BUCKETS,
כך חזר הערך ש

64
00:03:18,530 --> 00:03:21,730
למעשה הוא מדד לhashtable
ולא מעבר למדד

65
00:03:21,730 --> 00:03:24,320
גבולות של המערך.

66
00:03:24,320 --> 00:03:28,060
כך שבהתחשב בפונקציה ש, אנחנו הולכים
חשיש המילה שאנו קוראים

67
00:03:28,060 --> 00:03:29,390
מילון.

68
00:03:29,390 --> 00:03:31,700
ואז אנחנו הולכים להשתמש
החשיש שלהכניס את

69
00:03:31,700 --> 00:03:33,750
כניסה לhashtable.

70
00:03:33,750 --> 00:03:38,520
>> החשיש עכשיו hashtable הוא הנוכחי
מקושר רשימה בטבלה.

71
00:03:38,520 --> 00:03:41,410
וזה אפשרי מאוד
שזה רק NULL.

72
00:03:41,410 --> 00:03:44,960
אנחנו רוצים להכניס את הכניסה שלנו ב
התחלה של רשימה מקושרת זה.

73
00:03:44,960 --> 00:03:48,600
וכך אנחנו הולכים יש לנו היום
נקודת כניסה למה hashtable

74
00:03:48,600 --> 00:03:50,380
כרגע מצביע עליו.

75
00:03:50,380 --> 00:03:53,310
ואז אנחנו הולכים לחנות,
בhashtable ב

76
00:03:53,310 --> 00:03:55,350
חשיש, הכניסה הנוכחית.

77
00:03:55,350 --> 00:03:59,320
אז שתי שורות אלה להכניס בהצלחה
הכניסה בתחילת

78
00:03:59,320 --> 00:04:02,260
רשימה מקושרת במדד
בhashtable.

79
00:04:02,260 --> 00:04:04,900
>> ברגע שנסיים עם זה, אנחנו יודעים
שמצאנו מילה אחרת ב

80
00:04:04,900 --> 00:04:07,790
מילון, ואנחנו להגדיל שוב.

81
00:04:07,790 --> 00:04:13,960
אז אנחנו ממשיכים לעשות את זה עד fscanf
סוף סוף חזר משהו שאינו ב1

82
00:04:13,960 --> 00:04:16,950
שנקודה לזכור כי
אנחנו צריכים לשחרר את הכניסה.

83
00:04:16,950 --> 00:04:19,459
אז עד כאן אנחנו malloced כניסה.

84
00:04:19,459 --> 00:04:21,329
וניסינו לקרוא משהו
מהמילון.

85
00:04:21,329 --> 00:04:23,910
ואנחנו לא קראנו בהצלחה
משהו מהמילון, ב

86
00:04:23,910 --> 00:04:26,650
ומקרה זה אנחנו צריכים לשחרר את הכניסה
כי אנחנו אף פעם לא לשים בעצם לתוך

87
00:04:26,650 --> 00:04:29,140
hashtable, ולבסוף לשבור.

88
00:04:29,140 --> 00:04:32,750
>> ברגע שאנו נפרוץ אנחנו צריכים לראות, טובים,
היה לנו לפרוץ החוצה, כי יש

89
00:04:32,750 --> 00:04:34,360
הייתה שגיאה בקריאה מהקובץ?

90
00:04:34,360 --> 00:04:37,120
או שאנחנו פורצים בגלל שאנחנו
הגיע לסוף הקובץ?

91
00:04:37,120 --> 00:04:39,480
אם הייתה טעות, אז
אנחנו רוצים לחזור שווא.

92
00:04:39,480 --> 00:04:40,930
בגלל עומס לא הצליח.

93
00:04:40,930 --> 00:04:43,890
ובתהליך אנחנו רוצים לפרוק
את כל המילים שאנחנו קוראים ב, ו

94
00:04:43,890 --> 00:04:45,670
לסגור את קובץ המילון.

95
00:04:45,670 --> 00:04:48,740
>> בהנחה שאנחנו לא מצליחים, אז אנחנו פשוט
עדיין צריכה לסגור את המילון

96
00:04:48,740 --> 00:04:53,040
להגיש, ולבסוף לחזור נכון מאז ש
טען בהצלחה את המילון.

97
00:04:53,040 --> 00:04:54,420
וזהו זה לעומס.

98
00:04:54,420 --> 00:04:59,020
אז עכשיו לבדוק, בהתחשב hashtable טעון,
הוא הולך להיראות כך.

99
00:04:59,020 --> 00:05:03,140
אז לבדוק, היא מחזירה bool, שהוא
הולך לציין אם עבר

100
00:05:03,140 --> 00:05:07,530
בתו מילה *, בין אם עבר
במחרוזת הוא במילון שלנו.

101
00:05:07,530 --> 00:05:09,890
אז אם זה במילון,
אם הוא נמצא בhashtable שלנו,

102
00:05:09,890 --> 00:05:11,170
אנו נחזור אמיתיים.

103
00:05:11,170 --> 00:05:13,380
ואם זה לא, נחזור שווא.

104
00:05:13,380 --> 00:05:17,740
>> לאור זאת עברה במילה, אנחנו
הולך חשיש המילה.

105
00:05:17,740 --> 00:05:22,110
עכשיו דבר חשוב להכיר הוא
כי בעומס ידעו שכל

106
00:05:22,110 --> 00:05:23,820
מילות שאנחנו הולכים להיות באותיות קטנות.

107
00:05:23,820 --> 00:05:25,820
אבל כאן אנחנו לא כל כך בטוחים.

108
00:05:25,820 --> 00:05:29,510
אם נסתכל על פונקציית hash שלנו,
פונקציית hash שלנו בעצם

109
00:05:29,510 --> 00:05:32,700
היא מעטפת נמוכה כל תו
של המילה.

110
00:05:32,700 --> 00:05:37,940
אז ללא קשר לשווי של
מילה, פונקציית hash שלנו היא התשואה

111
00:05:37,940 --> 00:05:42,270
אותו מדד לכל
ההיוון היא, כפי שהוא היה צריך

112
00:05:42,270 --> 00:05:45,280
חזרתי לאותיות קטנות לחלוטין
גרסה של המילה.

113
00:05:45,280 --> 00:05:46,600
בסדר.

114
00:05:46,600 --> 00:05:49,790
זה המדד שלנו הוא לתוך
HashTable למילה זו.

115
00:05:49,790 --> 00:05:52,940
>> עכשיו זה ללולאה הולך
לחזר על הרשימה המקושרת

116
00:05:52,940 --> 00:05:55,000
שהיה במדד זה.

117
00:05:55,000 --> 00:05:59,610
אז שמתי לב שאנו מאתחלים כניסה
כדי להצביע על מדד זה.

118
00:05:59,610 --> 00:06:02,750
אנחנו הולכים להמשיך
בזמן כניסה! = NULL.

119
00:06:02,750 --> 00:06:07,770
ותזכור שמעדכנים את המצביע
בכניסה שלנו מקושרת רשימה = כניסה> הבא.

120
00:06:07,770 --> 00:06:14,400
אז יש לנו נקודת הכניסה הנוכחית ל
הפריט הבא ברשימה המקושרת.

121
00:06:14,400 --> 00:06:19,250
>> אז לכל ערך ברשימה המקושרת,
אנחנו הולכים להשתמש strcasecmp.

122
00:06:19,250 --> 00:06:20,330
זה לא strcomp.

123
00:06:20,330 --> 00:06:23,780
כי שוב, אנחנו רוצים
לעשות דברים בחוסר רגיש מקרה.

124
00:06:23,780 --> 00:06:27,870
כך אנו משתמשים strcasecmp כדי להשוות
מילה שעברה זה

125
00:06:27,870 --> 00:06:31,860
פונקציה נגד המילה
כי הוא ברשומה זו.

126
00:06:31,860 --> 00:06:35,570
אם היא מחזירה אפס, זה אומר שלא היה
משחק, ובמקרה כזה אנחנו רוצים

127
00:06:35,570 --> 00:06:36,630
החזר אמיתי.

128
00:06:36,630 --> 00:06:39,590
מצאנו בהצלחה
מילה בhashtable שלנו.

129
00:06:39,590 --> 00:06:43,040
>> אם לא היה במשחק, אז אנחנו
הולך ללולאה שוב ומסתכלים על

130
00:06:43,040 --> 00:06:43,990
הכניסה הבאה.

131
00:06:43,990 --> 00:06:47,640
ואנחנו נמשיך לולאות בעוד יש
הם ערכים ברשימה מקושר זה.

132
00:06:47,640 --> 00:06:50,160
מה קורה אם אנחנו שוברים
מתוך זה ללולאה?

133
00:06:50,160 --> 00:06:55,110
זה אומר שאנחנו לא מצאנו שכניסה
תאם את המילה הזאת, ובמקרה זה

134
00:06:55,110 --> 00:07:00,220
אנחנו חוזרים שווא כדי לציין ש
hashtable לא הכיל את המילה הזאת.

135
00:07:00,220 --> 00:07:02,540
וזה סימון.

136
00:07:02,540 --> 00:07:04,790
>> אז בואו נסתכל על גודל.

137
00:07:04,790 --> 00:07:06,970
עכשיו גודל הולך להיות די פשוט.

138
00:07:06,970 --> 00:07:11,080
מאז זוכר בעומס, לכל מילה
מצאנו, אנחנו מוגדלים גלובליים

139
00:07:11,080 --> 00:07:12,880
גודל hashtable משתנה.

140
00:07:12,880 --> 00:07:16,480
אז פונקצית הגודל היא רק הולכת
לחזור משתנים גלובלי.

141
00:07:16,480 --> 00:07:18,150
וזהו זה.

142
00:07:18,150 --> 00:07:22,300
>> עכשיו סוף סוף, אנחנו צריכים לפרוק את
מילון פעם אחת את כל מה שעשה.

143
00:07:22,300 --> 00:07:25,340
אז איך אנחנו הולכים לעשות את זה?

144
00:07:25,340 --> 00:07:30,440
כאן אנחנו מלפפים על
כל הדליים של השולחן שלנו.

145
00:07:30,440 --> 00:07:33,240
אז יש דליי NUM_BUCKETS.

146
00:07:33,240 --> 00:07:37,410
ועבור כל רשימה מקושרת בנו
hashtable, אנחנו הולכים ללולאה מעל

147
00:07:37,410 --> 00:07:41,070
השלמות של הרשימה המקושרת,
לשחרר את כל רכיב.

148
00:07:41,070 --> 00:07:42,900
>> עכשיו אנחנו צריכים להיות זהירים.

149
00:07:42,900 --> 00:07:47,910
אז הנה יש לנו משתנה זמני
שאחסון את המצביע למשנהו

150
00:07:47,910 --> 00:07:49,730
אלמנט ברשימה המקושרת.

151
00:07:49,730 --> 00:07:52,140
ואז אנחנו הולכים לחופשיים
האלמנט הנוכחי.

152
00:07:52,140 --> 00:07:55,990
אנחנו צריכים להיות בטוחים שאנחנו עושים את זה מאז ש
לא יכול פשוט לשחרר את האלמנט הנוכחי

153
00:07:55,990 --> 00:07:59,180
ולאחר מכן נסה לגשת למצביע הבא,
מאז רגע שאנחנו כבר שחררו אותו,

154
00:07:59,180 --> 00:08:00,870
הזיכרון הופך להיות לא חוקי.

155
00:08:00,870 --> 00:08:04,990
>> אז אנחנו צריכים לשמור על סביב מצביע
האלמנט הבא, אז אנחנו יכולים לשחרר את

156
00:08:04,990 --> 00:08:08,360
אלמנט הנוכחי, ולאחר מכן אנו יכולים לעדכן
האלמנט הנוכחי שלנו כדי להצביע על

157
00:08:08,360 --> 00:08:09,550
האלמנט הבא.

158
00:08:09,550 --> 00:08:12,800
אנחנו לולאה בזמן שיש אלמנטים
ברשימה מקושרת זה.

159
00:08:12,800 --> 00:08:15,620
אנחנו נעשה את זה בשביל כולם קשור
רשימות בhashtable.

160
00:08:15,620 --> 00:08:19,460
וברגע שנסיים עם זה, יש לנו
נפרק לחלוטין hashtable, ו

161
00:08:19,460 --> 00:08:20,190
אנחנו נעשו.

162
00:08:20,190 --> 00:08:23,200
כך שזה בלתי אפשרי עבור לפרוק
אי פעם לחזור שווא.

163
00:08:23,200 --> 00:08:26,470
וכאשר סיימנו, אנחנו
רק החזר אמיתי.

164
00:08:26,470 --> 00:08:29,000
>> בואו לתת פתרון זה לנסות.

165
00:08:29,000 --> 00:08:33,070
אז בואו נסתכל על מה ששלנו
צומת struct תיראה.

166
00:08:33,070 --> 00:08:36,220
כאן אנו רואים שאנחנו הולכים יש לי bool
מילה וצומת struct * ילדים

167
00:08:36,220 --> 00:08:37,470
א"ב סוגר.

168
00:08:37,470 --> 00:08:38,929

169
00:08:38,929 --> 00:08:42,020
אז הדבר הראשון שאתה יכול להיות
תוהה, מדוע הוא א"ב

170
00:08:42,020 --> 00:08:44,660
ed מוגדר כ27?

171
00:08:44,660 --> 00:08:47,900
ובכן, זוכר שאנחנו הולכים צריכים
לטיפול בגרש.

172
00:08:47,900 --> 00:08:51,910
אז זה הולך להיות קצת
מקרה מיוחד במהלך תכנית זו.

173
00:08:51,910 --> 00:08:54,710
>> עכשיו זוכר איך הגיבורים
באמת עובד.

174
00:08:54,710 --> 00:08:59,380
בואו נגיד שאנחנו אינדקס המילה
"חתולים". אז מן השורש של הגיבורים,

175
00:08:59,380 --> 00:09:02,610
אנחנו הולכים להסתכל על הילדים
מערך, ואנחנו הולכים להסתכל על

176
00:09:02,610 --> 00:09:08,090
מדד שמתאים למכתב
ג אז זה יהיה צמוד 2.

177
00:09:08,090 --> 00:09:11,530
אז בהתחשב בכך, שרצונו
לתת לנו צומת חדשה.

178
00:09:11,530 --> 00:09:13,820
ואז אנחנו נעבוד מצומת זה.

179
00:09:13,820 --> 00:09:17,770
>> כך שבהתחשב בצומת זה, אנחנו שוב
הולך להסתכל על מערך הילדים.

180
00:09:17,770 --> 00:09:22,110
ואנחנו הולכים להסתכל על מדד אפס
למתאים בחתול.

181
00:09:22,110 --> 00:09:27,170
אז אנחנו הולכים ללכת לצומת ש,
וניתנו צומת שאנחנו הולכים

182
00:09:27,170 --> 00:09:31,090
להסתכל בסוף זה מתכתב
לט ועבר לצומת ש,

183
00:09:31,090 --> 00:09:35,530
סוף סוף, יש לנו נראים לחלוטין
באמצעות המילה שלנו "חתול". ועכשיו בול

184
00:09:35,530 --> 00:09:40,960
מילה אמורה לציין אם
מילת נתונה זה היא למעשה מילה.

185
00:09:40,960 --> 00:09:43,470
>> אז למה אנחנו צריכים את זה מקרה מיוחד?

186
00:09:43,470 --> 00:09:47,700
ובכן "קטסטרופה" מה של המילה
הוא במילון שלנו, אבל

187
00:09:47,700 --> 00:09:50,150
מילה "חתול" הוא לא?

188
00:09:50,150 --> 00:09:54,580
אז ומחפש לראות אם המילה "חתול"
הוא במילון שלנו, אנחנו

189
00:09:54,580 --> 00:09:59,970
הולך להסתכל בהצלחה באמצעות
המדדים C-A-T בצומת אזור.

190
00:09:59,970 --> 00:10:04,290
אבל זה רק בגלל אסון
קרה כדי ליצור צמתים בדרך

191
00:10:04,290 --> 00:10:07,190
מ-C-A-T, כל הדרך אל
הסוף של המילה.

192
00:10:07,190 --> 00:10:12,020
אז bool מילה משמשת כדי לציין אם
מיקום המסוים הזה

193
00:10:12,020 --> 00:10:14,310
למעשה מצביע על מילה.

194
00:10:14,310 --> 00:10:15,140
>> בסדר.

195
00:10:15,140 --> 00:10:19,310
אז עכשיו שאנחנו יודעים מה זה הגיבורים הוא
הולך להיראות, בואו נסתכל על

196
00:10:19,310 --> 00:10:20,730
לטעון פונקציה.

197
00:10:20,730 --> 00:10:24,610
אז העומס הולך לחזור bool
לאם אנחנו בהצלחה או

198
00:10:24,610 --> 00:10:26,720
ללא הצלחה העמיס את המילון.

199
00:10:26,720 --> 00:10:30,460
וזה הולך להיות המילון
שאנחנו רוצים לטעון.

200
00:10:30,460 --> 00:10:33,930
>> דבר אז קודם כל אנחנו צריכים לעשות זה פתוח
עד שהמילון לקריאה.

201
00:10:33,930 --> 00:10:36,160
ואנחנו צריכים לוודא
שלא להיכשל.

202
00:10:36,160 --> 00:10:39,580
אז אם המילון לא היה
נפתח בהצלחה, הוא יחזור

203
00:10:39,580 --> 00:10:42,400
null, ובמקרה זה אנחנו
הולך בתמורת שווא.

204
00:10:42,400 --> 00:10:47,230
אבל בהנחה שזה בהצלחה
פתחתי, אז אנחנו יכולים באמת לקרוא

205
00:10:47,230 --> 00:10:48,220
באמצעות המילון.

206
00:10:48,220 --> 00:10:50,880
>> דבר אז קודם כל אנחנו הולכים
רוצה לעשות זה יש לנו את זה

207
00:10:50,880 --> 00:10:52,500
שורש משתנה גלובלי.

208
00:10:52,500 --> 00:10:56,190
עכשיו שורש הולך להיות צומת *.

209
00:10:56,190 --> 00:10:59,760
זה החלק העליון של הגיבורים שלנו, כי אנחנו
הולך להיות iterating דרך.

210
00:10:59,760 --> 00:11:02,660
אז הדבר הראשון שאנחנו הולכים
לרוצה לעשות הוא להקצות

211
00:11:02,660 --> 00:11:04,140
זיכרון לשורש שלנו.

212
00:11:04,140 --> 00:11:07,980
שים לב שאנחנו משתמשים calloc
פונקציה, שהוא בעצם אותו הדבר

213
00:11:07,980 --> 00:11:11,500
כפונקציה malloc, למעט זה
מובטח להחזיר משהו שהוא

214
00:11:11,500 --> 00:11:13,180
מאופס בחוץ לגמרי.

215
00:11:13,180 --> 00:11:17,290
אז אם אנחנו משמשים malloc, היינו צריך
לעבור את כל המצביעים בנו

216
00:11:17,290 --> 00:11:20,160
צומת, ולוודא כי
הם כולם ריקים.

217
00:11:20,160 --> 00:11:22,710
אז calloc יעשה את זה בשבילנו.

218
00:11:22,710 --> 00:11:26,330
>> עכשיו בדיוק כמו malloc, אנחנו צריכים לעשות
בטוח שההקצאה הייתה למעשה

219
00:11:26,330 --> 00:11:27,520
מוצלח.

220
00:11:27,520 --> 00:11:29,990
אם זה חזר ריק, אז אנחנו
צריך לסגור או מילון

221
00:11:29,990 --> 00:11:32,100
להגיש ותמורת שווא.

222
00:11:32,100 --> 00:11:36,835
אז בהנחה שהקצאה שהיה
מוצלח, אנחנו הולכים להשתמש בצומת *

223
00:11:36,835 --> 00:11:40,270
סמן ללחזר דרך הגיבורים שלנו.

224
00:11:40,270 --> 00:11:43,890
אז השורשים שלנו אף פעם לא הולכים להשתנות,
אבל אנחנו הולכים להשתמש בסמן ל

225
00:11:43,890 --> 00:11:47,875
בעצם ללכת מצומת לצומת.

226
00:11:47,875 --> 00:11:50,940
>> אז בזה ללולאה אנו קוראים
באמצעות קובץ המילון.

227
00:11:50,940 --> 00:11:53,670
ואנחנו משתמשים fgetc.

228
00:11:53,670 --> 00:11:56,290
Fgetc הולך לתפוס אחת
דמות מהקובץ.

229
00:11:56,290 --> 00:11:59,370
אנחנו הולכים להמשיך תופס
דמויות בזמן שאנחנו לא מגיעים

230
00:11:59,370 --> 00:12:01,570
סוף הקובץ.

231
00:12:01,570 --> 00:12:03,480
>> ישנם שני מקרים שאנחנו צריכים להתמודד איתו.

232
00:12:03,480 --> 00:12:06,610
הראשון, אם הדמות
לא היה בשורה חדשה.

233
00:12:06,610 --> 00:12:10,450
אז אנחנו יודעים אם היה זה קו חדש, ולאחר מכן
אנחנו עומדים לעבור למילה חדשה.

234
00:12:10,450 --> 00:12:15,240
אבל בהנחה שזה לא היה בשורה חדשה, ולאחר מכן
כאן אנחנו רוצים להבין

235
00:12:15,240 --> 00:12:18,380
מדד שאנחנו הולכים לאינדקס לתוך
במערך שהילדים

236
00:12:18,380 --> 00:12:19,810
הסתכלנו בעבר.

237
00:12:19,810 --> 00:12:23,880
>> אז, כמו שאמרתי קודם, שאנחנו צריכים
מקרה מיוחד הגרש.

238
00:12:23,880 --> 00:12:26,220
שים לב שאתה משתמש משולש
מפעיל כאן.

239
00:12:26,220 --> 00:12:29,580
אז אנחנו הולכים לקרוא את זה כמו, אם
הדמות שאנו קוראים בהייתה

240
00:12:29,580 --> 00:12:35,330
גרש, אז אנחנו הולכים להקים
מדד = "אלף" -1, אשר יהיה

241
00:12:35,330 --> 00:12:37,680
יהיה המדד 26.

242
00:12:37,680 --> 00:12:41,130
>> דבר אחר, אם זה לא היה גרש, יש
אנחנו הולכים להגדיר את המדד

243
00:12:41,130 --> 00:12:43,760
שווה ג -.

244
00:12:43,760 --> 00:12:49,030
אז זוכר בחזרה מהעבר p-סטים,
ג - הוא הולך לתת לנו

245
00:12:49,030 --> 00:12:53,410
עמדה אלפביתית של ג אז אם
C היא האות, זה יהיה

246
00:12:53,410 --> 00:12:54,700
לתת לנו מדד אפס.

247
00:12:54,700 --> 00:12:58,120
לאות B, זה ייתן לי
שלנו המדד 1, וכן הלאה.

248
00:12:58,120 --> 00:13:03,010
>> אז זה נותן לנו המדד ל
מערך ילדים שאנחנו רוצים.

249
00:13:03,010 --> 00:13:08,890
עכשיו, אם מדד זה הוא ריק כרגע
הילדים, זה אומר שצומת

250
00:13:08,890 --> 00:13:11,830
לא קיימות כיום
מדרך זו.

251
00:13:11,830 --> 00:13:15,160
אז אנחנו צריכים להקצות
צומת לנתיב.

252
00:13:15,160 --> 00:13:16,550
זה מה שנעשינו כאן.

253
00:13:16,550 --> 00:13:20,690
>> אז אנחנו הולכים להשתמש calloc שוב
פונקציה, כך שאנחנו לא צריכה

254
00:13:20,690 --> 00:13:22,880
לאפס את כל המצביעים.

255
00:13:22,880 --> 00:13:27,240
ואנחנו צריכים שוב לבדוק
calloc שלא להיכשל.

256
00:13:27,240 --> 00:13:30,700
אם calloc לא להיכשל, אז אנחנו צריכים
לפרוק הכל, לסוגרנו

257
00:13:30,700 --> 00:13:32,820
מילון, ותמורת שווא.

258
00:13:32,820 --> 00:13:40,050
אז בהנחה שזה לא נכשל, ולאחר מכן
זה יהיה ליצור ילד חדש עבורנו.

259
00:13:40,050 --> 00:13:41,930
ואז אנחנו נלך לילד הזה.

260
00:13:41,930 --> 00:13:44,960
הסמן שלנו לחזר
עד אותו ילד.

261
00:13:44,960 --> 00:13:49,330
>> עכשיו, אם זה לא היה ריק מלכתחילה,
לאחר מכן הסמן יכול רק לחזר

262
00:13:49,330 --> 00:13:52,590
עד שהילד מבלי
יש להקצות כל דבר.

263
00:13:52,590 --> 00:13:56,730
זה המקרה שבו אנו קרו ראשון
להקצות את המילה "חתול". ו -

264
00:13:56,730 --> 00:14:00,330
זה אומר שכאשר אנחנו הולכים להקצות
"קטסטרופה", אנחנו לא צריכים ליצור

265
00:14:00,330 --> 00:14:01,680
בלוטות לC-A-T שוב.

266
00:14:01,680 --> 00:14:04,830
הם כבר קיימים.

267
00:14:04,830 --> 00:14:06,080
>> מה זה אחר?

268
00:14:06,080 --> 00:14:10,480
זה המצב שבו היה ג
n הלוכסן ההפוך, שבו ג היה קו חדש.

269
00:14:10,480 --> 00:14:13,710
משמעות דבר היא שיש לנו בהצלחה
השלים מילה.

270
00:14:13,710 --> 00:14:16,860
עכשיו מה שאנחנו רוצים לעשות כשאנחנו
הושלם בהצלחה מילה?

271
00:14:16,860 --> 00:14:21,100
אנחנו הולכים להשתמש במילת תחום זה
בתוך צומת struct שלנו.

272
00:14:21,100 --> 00:14:23,390
אנחנו רוצים להגדיר את זה נכון.

273
00:14:23,390 --> 00:14:27,150
אז זה מצביע על כך שפסק זו
מציין מוצלח

274
00:14:27,150 --> 00:14:29,250
מילה, מילה בפועל.

275
00:14:29,250 --> 00:14:30,940
>> עכשיו להגדיר את זה נכון.

276
00:14:30,940 --> 00:14:35,150
אנחנו רוצים לאפס את הסמן שלנו לנקודה
לתחילת הגיבורים שוב.

277
00:14:35,150 --> 00:14:40,160
ולבסוף, להגדיל המילון שלנו
גודל, מאז שמצאנו עבודה אחרת.

278
00:14:40,160 --> 00:14:43,230
אז אנחנו הולכים להמשיך לעשות את זה,
קריאה בתו אחרי תו,

279
00:14:43,230 --> 00:14:49,150
בניית צמתים חדשים בגיבורים שלנו ו
עבור כל מילה במילון, עד

280
00:14:49,150 --> 00:14:54,020
סוף סוף אנחנו מגיעים C! = EOF, שבו
למקרה שנפרוץ של הקובץ.

281
00:14:54,020 --> 00:14:57,050
>> עכשיו יש שני מקרים תחת
שבו אנו יכולים להיות פגעו EOF.

282
00:14:57,050 --> 00:15:00,980
הראשון הוא אם יש שגיאה
קריאה מהקובץ.

283
00:15:00,980 --> 00:15:03,470
אז אם לא הייתה טעות, אנחנו
צריך לעשות טיפוסי.

284
00:15:03,470 --> 00:15:06,460
לפרוק הכל, קרוב
הקובץ, בתמורת שווא.

285
00:15:06,460 --> 00:15:09,810
בהנחה שלא הייתה טעות, כי
רק אומר שאנחנו באמת פגעו בסופו של

286
00:15:09,810 --> 00:15:13,750
את הקובץ, ובמקרה זה, אנחנו סוגרים
להגיש ולחזור נכון מאז ש

287
00:15:13,750 --> 00:15:17,330
מילון נטען בהצלחה
לגיבורים שלנו.

288
00:15:17,330 --> 00:15:20,170
>> אז עכשיו בואו לבדוק את הסימון.

289
00:15:20,170 --> 00:15:25,156
כאשר מסתכלים על פונקצית הסימון, אנו רואים
הסימון שהוא הולך לחזור bool.

290
00:15:25,156 --> 00:15:29,680
זה מחזיר אמת אם המילה הזאת שזה
שעבר הוא בגיבורים שלנו.

291
00:15:29,680 --> 00:15:32,110
היא מחזירה שקר אחר.

292
00:15:32,110 --> 00:15:36,050
אז איך אתה לקבוע אם
מילה זו היא בגיבורים שלנו?

293
00:15:36,050 --> 00:15:40,190
>> אנו רואים כאן, בדיוק כמו בעבר,
אנחנו הולכים להשתמש בסמן ללחזר

294
00:15:40,190 --> 00:15:41,970
דרך הגיבורים שלנו.

295
00:15:41,970 --> 00:15:46,600
עכשיו הנה אנחנו הולכים לחזר
על כל המילה שלנו.

296
00:15:46,600 --> 00:15:50,620
אז iterating מעל המילה אנחנו בעבר,
אנחנו הולכים לקבוע את

297
00:15:50,620 --> 00:15:56,400
מדד לתוך מערך שהילדים
מתאים לI. סוגריים מילה אז זה

298
00:15:56,400 --> 00:15:59,670
הוא הולך להיראות בדיוק כמו
עומס, שבו אם מילה [i]

299
00:15:59,670 --> 00:16:03,310
הוא גרש, אז אנחנו רוצים
להשתמש "אלף" אינדקס - 1.

300
00:16:03,310 --> 00:16:05,350
מכיוון שקבענו כי ש
מקום שבו אנחנו הולכים לאחסון

301
00:16:05,350 --> 00:16:07,100
גרשיים.

302
00:16:07,100 --> 00:16:11,780
>> אחר אנחנו הולכים להשתמש בשתי מילה תחתונה
אני סוגר אז לזכור מילה שיכולה

303
00:16:11,780 --> 00:16:13,920
יש לי ההיוון שרירותית.

304
00:16:13,920 --> 00:16:17,540
ולכן אנחנו רוצים לוודא שאנחנו
משתמש בגרסה קטנה של דברים.

305
00:16:17,540 --> 00:16:21,920
וכך להפחית מזה '"לרגע
שוב לתת לנו את אלפביתי

306
00:16:21,920 --> 00:16:23,880
עמדתו של התו.

307
00:16:23,880 --> 00:16:27,680
אז זה הולך להיות האינדקס שלנו
למערך הילדים.

308
00:16:27,680 --> 00:16:32,420
>> ועכשיו, אם מדד שלילדים
המערך הוא ריק, זה אומר שאנחנו

309
00:16:32,420 --> 00:16:34,990
כבר לא יכול להמשיך iterating
את הגיבורים שלנו.

310
00:16:34,990 --> 00:16:38,870
אם זה המקרה, מילה זו לא יכולה
אולי להיות בגיבורים שלנו.

311
00:16:38,870 --> 00:16:42,340
שכן אם זה היה, זה היית
אומר שלא יהיה נתיב

312
00:16:42,340 --> 00:16:43,510
עד למילה זו.

313
00:16:43,510 --> 00:16:45,290
ואתה אף פעם לא היה נתקל באפס.

314
00:16:45,290 --> 00:16:47,850
אז נתקל null, אנחנו חוזרים שווא.

315
00:16:47,850 --> 00:16:49,840
המילה אינה נמצאת במילון.

316
00:16:49,840 --> 00:16:53,660
אם זה לא היה ריק, אז אנחנו
הולך להמשיך iterating.

317
00:16:53,660 --> 00:16:57,220
>> אז אנחנו יוצאים הסמן שם
כדי להצביע על כי בפרט

318
00:16:57,220 --> 00:16:59,760
צומת במדד זה.

319
00:16:59,760 --> 00:17:03,150
אנחנו ממשיכים לעשות את זה לאורך כל
כל המילה, בהנחה

320
00:17:03,150 --> 00:17:03,950
אנחנו אף פעם לא פגעו null.

321
00:17:03,950 --> 00:17:07,220
זה אומר שהיינו מסוגל לעבור את
כל המילה ולמצוא

322
00:17:07,220 --> 00:17:08,920
צומת בניסיון שלנו.

323
00:17:08,920 --> 00:17:10,770
אבל אנחנו לא עשינו די עדיין.

324
00:17:10,770 --> 00:17:12,290
>> אנחנו לא רוצים רק כדי לחזור נכון.

325
00:17:12,290 --> 00:17:14,770
אנחנו רוצים לחזור מילת סמן>.

326
00:17:14,770 --> 00:17:18,980
מאז לזכור שוב, הוא "חתול" אינו
במילון שלנו, ו" קטסטרופה "

327
00:17:18,980 --> 00:17:22,935
הוא, ואז נוכל בהצלחה אנחנו מקבלים
באמצעות המילה "חתול". אבל סמן

328
00:17:22,935 --> 00:17:25,760
מילה תהיה כוזבת ולא נכונה.

329
00:17:25,760 --> 00:17:30,930
אז אנחנו חוזרים מילת סמן כדי לציין
אם פסק זו היא למעשה מילה.

330
00:17:30,930 --> 00:17:32,470
וזה אותו לבדיקה.

331
00:17:32,470 --> 00:17:34,250
>> אז בואו לבדוק את הגודל.

332
00:17:34,250 --> 00:17:37,350
אז הגודל הולך להיות די קל
מאז, זכרו בעומס, אנחנו

333
00:17:37,350 --> 00:17:41,430
להגדיל כל גודל מילון
כל מילה שאנו פוגשים.

334
00:17:41,430 --> 00:17:45,350
אז גודל הוא רק הולך
לחזור גודל מילון.

335
00:17:45,350 --> 00:17:47,390
וזהו זה.

336
00:17:47,390 --> 00:17:50,590
>> אז לבסוף יש לנו לפרוק.

337
00:17:50,590 --> 00:17:55,100
אז לפרוק, אנחנו הולכים להשתמש
פונקציה רקורסיבית בעצם לעשות את כל

338
00:17:55,100 --> 00:17:56,530
של העבודה בשבילנו.

339
00:17:56,530 --> 00:17:59,340
אז הפונקציה שלנו הולכת
להיקרא על פורק.

340
00:17:59,340 --> 00:18:01,650
מה פורק הוא הולך לעשות?

341
00:18:01,650 --> 00:18:06,580
אנו רואים כאן פורקים כי הוא הולך
לחזר על כל הילדים ב

342
00:18:06,580 --> 00:18:08,410
הצומת הזה בפרט.

343
00:18:08,410 --> 00:18:11,750
ואם את צומת הילד אינה
null, אז אנחנו הולכים

344
00:18:11,750 --> 00:18:13,730
לפרוק את צומת הילד.

345
00:18:13,730 --> 00:18:18,010
>> אז זה אתה באופן רקורסיבי לפרוק
כל הילדים שלנו.

346
00:18:18,010 --> 00:18:21,080
ברגע שאנחנו בטוחים שכל הילדים שלנו
כבר פרק, אז אנחנו

347
00:18:21,080 --> 00:18:25,210
יכול לשחרר את עצמנו, ולכן
לפרוק את עצמנו.

348
00:18:25,210 --> 00:18:29,460
זה יעבוד באופן רקורסיבי
לפרוק את כל הגיבורים.

349
00:18:29,460 --> 00:18:32,850
ואז ברגע שזה נעשה,
אנחנו יכולים רק לחזור נכון.

350
00:18:32,850 --> 00:18:34,210
לפרוק לא יכול להיכשל.

351
00:18:34,210 --> 00:18:35,710
אנחנו רק משחררים את הדברים.

352
00:18:35,710 --> 00:18:38,870
אז ברגע שנסיים לשחרר
הכל, החזר אמיתי.

353
00:18:38,870 --> 00:18:40,320
וזהו זה.

354
00:18:40,320 --> 00:18:41,080
השם שלי הוא רוב.

355
00:18:41,080 --> 00:18:42,426
וזה היה איות.

356
00:18:42,426 --> 00:18:47,830
>> [השמעת מוסיקה]