1
00:00:00,000 --> 00:00:00,530

2
00:00:00,530 --> 00:00:03,070
>> Виступаючий 1: Давайте дамо
це рішення спробувати.

3
00:00:03,070 --> 00:00:07,130
Отже, давайте подивимося, що наш
Структура, вузол буде виглядати.

4
00:00:07,130 --> 00:00:11,040
Тут ми бачимо, що ми збираємося мати
Bool Слово і Struct вузол зірки

5
00:00:11,040 --> 00:00:12,990
Діти дужки алфавіт.

6
00:00:12,990 --> 00:00:18,720
Так перше, що ви можете бути здивовані,,
чому алфавіт хеш визначається як 27?

7
00:00:18,720 --> 00:00:22,540
Ну, пам'ятаєте, що ми збираємося потрібно
бути обробки апостроф, так

8
00:00:22,540 --> 00:00:25,610
що буде свого роду спеціальний
місце усюди цієї програми.

9
00:00:25,610 --> 00:00:28,780
>> Добре, тепер, згадайте, як
Trie насправді працює.

10
00:00:28,780 --> 00:00:33,420
Скажімо ми індексації слова кішок,
потім від кореня нашого Trie,

11
00:00:33,420 --> 00:00:36,670
ми будемо дивитися на дітей
Масив, і ми будемо дивитися на

12
00:00:36,670 --> 00:00:42,250
індекс, який відповідає букві
С. Так що було б індекс два.

13
00:00:42,250 --> 00:00:46,400
Тому, враховуючи, що, що дасть нам
новий вузол, а потім ми будемо

14
00:00:46,400 --> 00:00:47,880
працювати з цим вузлом.

15
00:00:47,880 --> 00:00:51,830
>> Тому, враховуючи, що вузол, ми в черговий раз
будемо дивитися на масиві дітей,

16
00:00:51,830 --> 00:00:56,170
і ми будемо дивитися на нульовий індекс
щоб відповідати А в кіт.

17
00:00:56,170 --> 00:01:01,240
Отже, ми збираємося піти на цей вузол,
і враховуючи, що вузол, ми збираємося

18
00:01:01,240 --> 00:01:05,170
дивитися на індекс, який відповідає
Т. і перейти до цього вузла,

19
00:01:05,170 --> 00:01:09,590
нарешті, ми повністю подивився
через нашу слова Cat, а тепер Bool

20
00:01:09,590 --> 00:01:15,020
Слово передбачається вказати, чи є
це дане слово насправді слово.

21
00:01:15,020 --> 00:01:17,530
>> Так чому ж ми повинні, що приватний випадок?

22
00:01:17,530 --> 00:01:21,680
Ну, що, якщо слово катастрофа
знаходиться в нашому словнику, але

23
00:01:21,680 --> 00:01:24,120
слово кішка не є?

24
00:01:24,120 --> 00:01:29,030
Таким чином, в дивився, якщо слово кішка
в нашому словнику, ми збираємося

25
00:01:29,030 --> 00:01:34,880
успішно переглядати індексів
С-А-Т і досягти вузол, але це

26
00:01:34,880 --> 00:01:39,760
тільки тому, що катастрофа сталася в
створити вузли на шляху з C-A-T все

27
00:01:39,760 --> 00:01:41,250
аж до кінця слова.

28
00:01:41,250 --> 00:01:46,520
Так Bool Слово використовується чи вказують
це особливе розташування фактично

29
00:01:46,520 --> 00:01:48,370
вказує на слово.

30
00:01:48,370 --> 00:01:52,920
>> Гаразд, так що тепер, коли ми знаємо, що
Trie збирається виглядати, давайте подивимося

31
00:01:52,920 --> 00:01:54,800
у функції Load.

32
00:01:54,800 --> 00:01:58,670
Так навантаження збирається повертати Bool
для того ми успішно або

33
00:01:58,670 --> 00:02:03,020
безуспішно завантажувалася словник і
це буде словник

34
00:02:03,020 --> 00:02:04,520
що ми хочемо завантажити.

35
00:02:04,520 --> 00:02:08,310
Так перше, що ми збираємося зробити, це відкрити
до цього словника для читання.

36
00:02:08,310 --> 00:02:12,060
Ми повинні переконатися, що ми не забув,
тому, якщо словник ні

37
00:02:12,060 --> 00:02:15,280
успішно відкритий, то він поверне
Ні, в якому випадку ми збираємося

38
00:02:15,280 --> 00:02:16,340
повернутися False.

39
00:02:16,340 --> 00:02:21,290
Але якщо припустити, що він успішно
відкрив, то ми можемо насправді читати

40
00:02:21,290 --> 00:02:22,310
через словнику.

41
00:02:22,310 --> 00:02:24,940
>> Так перше, що ми збираємося
хочу зробити, це у нас є це

42
00:02:24,940 --> 00:02:26,560
глобальна змінна корінь.

43
00:02:26,560 --> 00:02:30,250
Тепер, корінь буде вузол зірка.

44
00:02:30,250 --> 00:02:33,830
Це вершина нашої Trie, що ми
буде ітерації.

45
00:02:33,830 --> 00:02:38,200
Так перше, що ми збираємося хочете
зробити, це виділити пам'ять для нашого кореня.

46
00:02:38,200 --> 00:02:42,040
>> Зверніть увагу, що ми використовуємо Calloc
Функція, яка в основному те ж саме

47
00:02:42,040 --> 00:02:45,560
як функція Malloc, за винятком, що це
гарантовано повернути те, що є

48
00:02:45,560 --> 00:02:47,240
повністю обнуляється.

49
00:02:47,240 --> 00:02:51,350
Так що, якщо ми використовували Malloc, ми повинні були б
пройти через всі покажчики в нашій

50
00:02:51,350 --> 00:02:54,220
вузол і переконайтеся, що
вони все нуль.

51
00:02:54,220 --> 00:02:56,780
Так Calloc зробить це за нас.

52
00:02:56,780 --> 00:03:00,390
>> Тепер, так само, як Malloc, ми повинні зробити
упевнений, що виділення насправді

53
00:03:00,390 --> 00:03:01,580
успішним.

54
00:03:01,580 --> 00:03:04,060
Якщо це повертається нуль, то
потрібно закрити наш словник

55
00:03:04,060 --> 00:03:06,170
файл і повернути False.

56
00:03:06,170 --> 00:03:11,040
Так припускаючи розподіл був
успішно, ми збираємося використовувати вузол

57
00:03:11,040 --> 00:03:14,340
зірки курсора для ітерації
через нашу Trie.

58
00:03:14,340 --> 00:03:17,950
Таким чином, наш корінь ніколи не збирається змінювати,
але ми збираємося використовувати курсор в

59
00:03:17,950 --> 00:03:20,770
насправді йти від вузла до вузла.

60
00:03:20,770 --> 00:03:25,000
>> Гаразд, так що в цьому для циклу, ми
читати через файл словника,

61
00:03:25,000 --> 00:03:26,965
і ми використовуємо в fgetc.

62
00:03:26,965 --> 00:03:30,360
Так fgetc збирається захопити один
персонаж з файлу.

63
00:03:30,360 --> 00:03:33,430
Ми збираємося продовжити захоплення
символів у той час як ми не доходять

64
00:03:33,430 --> 00:03:37,540
кінець файлу, так що є
два випадки, які ми повинні впоратися.

65
00:03:37,540 --> 00:03:41,640
Перший, якщо персонаж не був
Нова лінія, тому ми знаємо, якщо це був новий

66
00:03:41,640 --> 00:03:44,480
лінія, то ми збираємося
перейти до нових словом.

67
00:03:44,480 --> 00:03:49,300
Але якщо припустити, що це не було нової лінії, то
тут, ми хочемо з'ясувати,

68
00:03:49,300 --> 00:03:52,440
Індекс ми збираємося індексу в
в масиві дітей, що

69
00:03:52,440 --> 00:03:53,890
ми дивилися на перед.

70
00:03:53,890 --> 00:03:57,950
>> Так як я вже говорив, ми повинні
Особливий випадок апостроф.

71
00:03:57,950 --> 00:04:01,040
Зверніть увагу, що ми з тризначним оператором
тут, так що ми збираємося читати

72
00:04:01,040 --> 00:04:05,500
це як якщо персонаж ми читаємо, був
апостроф, то ми збираємося

73
00:04:05,500 --> 00:04:11,740
встановити індекс, рівний алфавіту мінус
1, який буде індекс 26.

74
00:04:11,740 --> 00:04:15,190
В іншому випадку, якщо це не було апостроф,
потім ми збираємося встановити індекс

75
00:04:15,190 --> 00:04:17,820
дорівнює з мінус.

76
00:04:17,820 --> 00:04:23,090
Так що пам'ятайте назад від попередніх наборів р,
з мінус збирається дати нам

77
00:04:23,090 --> 00:04:27,470
алфавітний становище з, так що якщо
з буквою А, ця воля

78
00:04:27,470 --> 00:04:28,770
дати нам нульовий індекс.

79
00:04:28,770 --> 00:04:32,180
Для письма B, це дало б
нам індекс 1, і так далі.

80
00:04:32,180 --> 00:04:37,070
>> Так що це дає нам індекс у
Діти масив, який ми хочемо.

81
00:04:37,070 --> 00:04:42,540
Тепер, якщо цей показник в даний час нульовий в
масив Діти, що означає, що

82
00:04:42,540 --> 00:04:47,470
вузол даний час не існує від
що шлях, так що ми повинні виділити

83
00:04:47,470 --> 00:04:49,220
вузол для цього шляху.

84
00:04:49,220 --> 00:04:50,610
Це те, що ми робимо тут.

85
00:04:50,610 --> 00:04:54,650
Таким чином, ми збираємося, знову ж таки, використовувати Calloc
Функція, щоб ми не повинні

86
00:04:54,650 --> 00:05:00,130
обнулити всі покажчики, і ми,
знову ж, потрібно перевірити, що Calloc

87
00:05:00,130 --> 00:05:01,300
не провалився.

88
00:05:01,300 --> 00:05:04,760
Якщо Calloc нічого не вийде, то ми повинні
вивантажити все, закриваємо

89
00:05:04,760 --> 00:05:06,880
словник, і повернути False.

90
00:05:06,880 --> 00:05:14,110
>> Так припускаючи, що він не забув, то
це створить нового дитини для нас,

91
00:05:14,110 --> 00:05:16,000
а потім ми підемо в цієї дитини.

92
00:05:16,000 --> 00:05:19,030
Наша курсор ітерації
до цієї дитини.

93
00:05:19,030 --> 00:05:23,390
Тепер, якщо це не було порожньою для початку,
то курсор можна просто перебрати

94
00:05:23,390 --> 00:05:26,650
до цієї дитини, практично не
того, щоб виділити нічого.

95
00:05:26,650 --> 00:05:30,790
Це той випадок, коли ми вперше відбулося
виділити слово кішку, і

96
00:05:30,790 --> 00:05:34,390
це означає, що, коли ми йдемо виділити
катастрофа, нам не потрібно створювати

97
00:05:34,390 --> 00:05:35,720
вузли для C-A-T знову.

98
00:05:35,720 --> 00:05:37,620
Вони вже існують.

99
00:05:37,620 --> 00:05:40,140
>> Отже, що ж це за інше?

100
00:05:40,140 --> 00:05:44,600
Це стан, при якому кондиціонер був
коса риса п, де кондиціонер був нова лінія.

101
00:05:44,600 --> 00:05:47,780
Це означає, що ми успішно
завершила слово.

102
00:05:47,780 --> 00:05:51,020
Тепер, що ми хочемо зробити, коли ми
успішно завершила слово?

103
00:05:51,020 --> 00:05:55,250
Ми збираємося використовувати це поле слово
всередині нашого Struct вузла.

104
00:05:55,250 --> 00:06:00,570
>> Ми хочемо, щоб встановити, що до Правда, таким чином, щоб
вказує, що цей вузол вказує

105
00:06:00,570 --> 00:06:03,320
успішним слово актуальною слово.

106
00:06:03,320 --> 00:06:05,050
Тепер встановіть, що Істина.

107
00:06:05,050 --> 00:06:09,210
Ми хочемо, щоб скинути нашу курсор до точки
на початку Trie знову.

108
00:06:09,210 --> 00:06:13,510
І, нарешті, збільшити наш словник
Розмір так як ми знайшли ще одне слово.

109
00:06:13,510 --> 00:06:16,450
>> Гаразд, так що ми збираємося продовжувати робити
що, читаючи характер по

110
00:06:16,450 --> 00:06:21,960
характер, побудови нових вузлів в
наша Trie і для кожного слова в

111
00:06:21,960 --> 00:06:26,810
словник, поки ми нарешті не досягне гр
одно EOF, в цьому випадку, ми порушуємо

112
00:06:26,810 --> 00:06:28,100
з файлу.

113
00:06:28,100 --> 00:06:31,110
Тепер, є два випадки під
які ми могли б потрапити EOF.

114
00:06:31,110 --> 00:06:35,680
Перший, якщо сталася помилка
читання з файлу, так що якщо не було

115
00:06:35,680 --> 00:06:39,280
про помилку, ми повинні зробити типовий
вивантажити все, закрийте файл,

116
00:06:39,280 --> 00:06:40,520
повернутися False.

117
00:06:40,520 --> 00:06:43,870
Припускаючи, що не було помилок, які
просто означає, що ми насправді потрапив в кінці

118
00:06:43,870 --> 00:06:47,820
файл, в якому випадку, ми закриваємо
файл і повернутися Правда, так як ми

119
00:06:47,820 --> 00:06:51,010
успішно завантажений словник
в нашій Trie.

120
00:06:51,010 --> 00:06:54,240
>> Гаразд, так що тепер давайте
Виїзд Заїзд.

121
00:06:54,240 --> 00:06:58,780
Дивлячись на перевірки функції, ми бачимо,
що Перевірити збирається повертати Bool.

122
00:06:58,780 --> 00:07:03,740
Вона повертає Правда, якщо це слово, що це
передається в нашій Trie.

123
00:07:03,740 --> 00:07:06,170
Вона повертає значення False у противному випадку.

124
00:07:06,170 --> 00:07:10,110
>> Так як ми збираємося визначити, чи є
це слово в нашому Trie?

125
00:07:10,110 --> 00:07:14,270
Ми бачимо тут, що, як і раніше,
ми збираємося використовувати курсор для перебору

126
00:07:14,270 --> 00:07:16,010
через нашу Trie.

127
00:07:16,010 --> 00:07:20,650
Тепер, ось, ми збираємося ітерації
над усім нашим словом.

128
00:07:20,650 --> 00:07:24,680
Так ітерації слова ми
пройшло, ми збираємося визначити

129
00:07:24,680 --> 00:07:29,280
індекс у масиві дітей, що
відповідає слово кронштейна I.

130
00:07:29,280 --> 00:07:34,150
Так що це буде виглядати так само, як
Навантаження, де, якщо слово кронштейн я є

131
00:07:34,150 --> 00:07:38,110
апостроф, то ми хочемо використовувати індекс
алфавіт мінус 1, тому що ми визначили

132
00:07:38,110 --> 00:07:41,160
тобто, куди ми йдемо
для зберігання апострофи.

133
00:07:41,160 --> 00:07:44,440
>> Решту ми збираємося використовувати ToLower
Слово кронштейн я.

134
00:07:44,440 --> 00:07:48,270
Так що пам'ятайте, що слово може мати довільне
капіталізація, і тому ми

135
00:07:48,270 --> 00:07:51,590
хочете, щоб переконатися, що ми використовуємо
рядкової версією речей.

136
00:07:51,590 --> 00:07:55,300
А потім відняти з цієї нижньому регістрі
щоб, знову ж таки, дають нам

137
00:07:55,300 --> 00:07:57,940
алфавітний положення
з цього символу.

138
00:07:57,940 --> 00:08:01,740
Так що це буде наш індекс
в масиві дітей.

139
00:08:01,740 --> 00:08:06,480
>> І тепер, якщо що індекс в інтересах дітей
Масив є порожнім, що означає, що ми

140
00:08:06,480 --> 00:08:09,050
більше не може продовжувати ітерації
вниз нашої Trie.

141
00:08:09,050 --> 00:08:13,320
Якщо це так, то це слово не може
можливо, буде в нашому Trie, так як, якщо він

142
00:08:13,320 --> 00:08:18,000
були, це означатиме, що буде
Шлях вниз до цього слова, і ви б

143
00:08:18,000 --> 00:08:19,350
ніколи не стикаються нуль.

144
00:08:19,350 --> 00:08:21,910
Так зустрічаючи нуль, ми повертаємося False.

145
00:08:21,910 --> 00:08:23,810
Слово немає у словнику.

146
00:08:23,810 --> 00:08:28,200
Якби не нуль, то ми збираємося
продовження ітерацій, так що ми збираємося

147
00:08:28,200 --> 00:08:33,150
оновити наш курсор, щоб вказати на що
конкретний вузол за цим індексом.

148
00:08:33,150 --> 00:08:36,659
>> Таким чином, ми продовжувати робити це протягом
все слово.

149
00:08:36,659 --> 00:08:40,630
Припустимо, що ми ніколи не вдарив нуль, що означає
ми змогли пройти через весь

150
00:08:40,630 --> 00:08:44,840
світ і знайти вузол в нашому Trie,
але ми ще не закінчили ще.

151
00:08:44,840 --> 00:08:46,350
Ми не хочемо, щоб просто повернути True.

152
00:08:46,350 --> 00:08:51,400
Ми хочемо повернутися курсора помилку слово
так, пам'ятайте, знову ж, якщо кішка не

153
00:08:51,400 --> 00:08:55,140
в наш словник і катастрофа,
тоді ми будемо успішно пройти

154
00:08:55,140 --> 00:08:59,810
слово кішка, але курсор слово
буде Брехня і неправда.

155
00:08:59,810 --> 00:09:04,990
Так ми повертаємося курсора слово для позначення
Чи цей вузол насправді слово,

156
00:09:04,990 --> 00:09:06,530
і ось воно що для перевірки.

157
00:09:06,530 --> 00:09:08,310
>> Так давайте перевіримо Розмір.

158
00:09:08,310 --> 00:09:11,410
Так Розмір буде досить легко
так, пам'ятаєте, в Load, ми

159
00:09:11,410 --> 00:09:15,480
збільшуючи розмір словника для
кожне слово, що ми стикаємося з.

160
00:09:15,480 --> 00:09:20,820
Так Розмір тільки збирається повернутися
розмір словника, і ось воно що.

161
00:09:20,820 --> 00:09:24,650
>> Гаразд, нарешті, у нас є Unload.

162
00:09:24,650 --> 00:09:29,050
Так вивантаження, ми збираємося використовувати
рекурсивна функція насправді робити все

163
00:09:29,050 --> 00:09:33,390
роботи для нас, тому нашій функції
збирається назвати Розвантажувач.

164
00:09:33,390 --> 00:09:35,830
Що Розвантажувач збираєтеся робити?

165
00:09:35,830 --> 00:09:40,640
Ми бачимо тут, що Розвантажувач збирається
перебору всіх дітей у

166
00:09:40,640 --> 00:09:45,810
цей конкретний вузол, і якщо дитина
вузол не є нульовим, то ми збираємося

167
00:09:45,810 --> 00:09:47,760
вивантажити дочірній вузол.

168
00:09:47,760 --> 00:09:52,070
>> Так це буде рекурсивно
вивантажити всі наші діти.

169
00:09:52,070 --> 00:09:55,140
Після того, як ми впевнені, що всі наші діти
були вивантажені, то ми

170
00:09:55,140 --> 00:09:58,830
може звільнитися, тому розвантажити OURSELF.

171
00:09:58,830 --> 00:10:04,550
Так що це буде рекурсивно вивантажити
Весь Trie, а потім один раз це

172
00:10:04,550 --> 00:10:06,910
зроблено, ми можемо просто повернути True.

173
00:10:06,910 --> 00:10:09,770
Вивантаження не може потерпіти невдачу, ми
просто звільняючи речі.

174
00:10:09,770 --> 00:10:12,985
Тому, як тільки ми закінчимо звільняючи
все, повернутися Правда.

175
00:10:12,985 --> 00:10:14,380
І це все.

176
00:10:14,380 --> 00:10:16,792
Мене звуть Боб, і це
був [нерозбірливо].

177
00:10:16,792 --> 00:10:21,888