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