1
00:00:00,000 --> 00:00:12,350
>> [Música tocando]

2
00:00:12,350 --> 00:00:13,050
>> ROB BOWDEN: Oi

3
00:00:13,050 --> 00:00:13,640
Estou Rob.

4
00:00:13,640 --> 00:00:16,210
E imos a solución para fóra.

5
00:00:16,210 --> 00:00:20,070
Entón, aquí imos aplicar
unha táboa xeral.

6
00:00:20,070 --> 00:00:24,090
Vemos que o no struct do noso
mesa se ve así.

7
00:00:24,090 --> 00:00:28,710
Por iso, vai ter unha palabra de char
matriz de tamaño Lonxitude + 1.

8
00:00:28,710 --> 00:00:32,259
Non esqueza do + 1, xa que o máximo
palabra no dicionario é de 45

9
00:00:32,259 --> 00:00:33,130
caracteres.

10
00:00:33,130 --> 00:00:37,070
E entón nós imos ter un adicional
caracteres para o cero, barra invertida.

11
00:00:37,070 --> 00:00:40,870
>> E entón a nosa hashtable en cada
balde vai almacenar unha

12
00:00:40,870 --> 00:00:42,320
lista ligada de nós.

13
00:00:42,320 --> 00:00:44,420
Non estamos facendo lineal enquisa aquí.

14
00:00:44,420 --> 00:00:48,430
E así, a fin de obrigar á seguinte
elemento no balde, necesitamos un

15
00:00:48,430 --> 00:00:50,390
struct node * seguinte.

16
00:00:50,390 --> 00:00:51,110
Aceptar.

17
00:00:51,110 --> 00:00:53,090
Entón é iso que un nodo se parece.

18
00:00:53,090 --> 00:00:56,180
>> Agora aquí é a declaración
da nosa hashtable.

19
00:00:56,180 --> 00:00:59,640
Terá 16834 baldes.

20
00:00:59,640 --> 00:01:01,910
Pero ese número non importa realmente.

21
00:01:01,910 --> 00:01:05,450
E, finalmente, imos ter o
hashtable tamaño variable global, que

22
00:01:05,450 --> 00:01:07,000
comezará como cero.

23
00:01:07,000 --> 00:01:10,760
E iso vai manterse ao tanto de como
moitas palabras están no noso dicionario.

24
00:01:10,760 --> 00:01:13,710
>> Entón, imos dar un ollo a carga.

25
00:01:13,710 --> 00:01:16,390
Teña en conta que a carga, el retorna un bool.

26
00:01:16,390 --> 00:01:20,530
Vostede volve verdadeiro se fose correctamente
cargado e false se non.

27
00:01:20,530 --> 00:01:23,990
E leva un const char * dicionario,
que é o dicionario

28
00:01:23,990 --> 00:01:25,280
que quere abrir.

29
00:01:25,280 --> 00:01:27,170
Así que esta é o primeiro
imos facer.

30
00:01:27,170 --> 00:01:29,500
>> Estamos indo ao fopen
dicionario para a lectura.

31
00:01:29,500 --> 00:01:31,680
E nós imos ter que facer
seguro de que el conseguiu.

32
00:01:31,680 --> 00:01:35,920
Entón, se voltou NULL, entón nós non
abrir con éxito o dicionario.

33
00:01:35,920 --> 00:01:37,440
E necesitamos voltar false.

34
00:01:37,440 --> 00:01:41,580
Pero supoñendo que fixo correctamente
aberta, así que queremos ler a

35
00:01:41,580 --> 00:01:42,400
dicionario.

36
00:01:42,400 --> 00:01:46,450
Polo tanto, manter looping ata que atopemos algún
motivo para romper ese ciclo,

37
00:01:46,450 --> 00:01:47,570
que imos ver.

38
00:01:47,570 --> 00:01:48,920
Polo tanto, manter looping.

39
00:01:48,920 --> 00:01:51,780
>> E agora nós imos
malloc un único nodo.

40
00:01:51,780 --> 00:01:54,020
E está claro que necesitamos
ao aire prema aquí.

41
00:01:54,020 --> 00:01:58,680
Entón, se mallocing non tivo éxito, entón
queremos descargar calquera nodo que

42
00:01:58,680 --> 00:02:02,590
pasou con malloc antes, pechar o
dicionario e voltar false.

43
00:02:02,590 --> 00:02:06,830
Pero ignorar que, asumindo que
conseguiu, entón queremos usar fscanf

44
00:02:06,830 --> 00:02:12,400
para ler unha soa palabra da nosa
dicionario para o noso nodo.

45
00:02:12,400 --> 00:02:17,940
Entón recorda que a entrada> palabra é o carácter
tapón palabra de tamaño Lenghth + 1

46
00:02:17,940 --> 00:02:20,300
que nós estamos indo para almacenar a palabra dentro

47
00:02:20,300 --> 00:02:25,070
>> Entón fscanf vai voltar 1, sempre
como era capaz de éxito

48
00:02:25,070 --> 00:02:26,750
ler unha palabra desde o ficheiro.

49
00:02:26,750 --> 00:02:30,460
Se algún erro ocorrer, ou nós
chegar ao final do arquivo,

50
00:02:30,460 --> 00:02:31,950
non volverá 1.

51
00:02:31,950 --> 00:02:35,180
No caso de que el non retorna 1,
estamos finalmente vai saír do

52
00:02:35,180 --> 00:02:37,280
ese loop while.

53
00:02:37,280 --> 00:02:42,770
Así, vemos que xa que temos correctamente
ler unha palabra en

54
00:02:42,770 --> 00:02:48,270
entry> palabra, entón nós estamos indo a que
palabra usando nosa función hash.

55
00:02:48,270 --> 00:02:49,580
>> Imos dar un ollo
a función hash.

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

57
00:02:52,430 --> 00:02:55,610
Entón, o que realmente non precisa
para entender iso.

58
00:02:55,610 --> 00:02:59,460
E, de feito, nós só tirou ese hash
funcionar a partir da Internet.

59
00:02:59,460 --> 00:03:04,010
O único que ten que recoñecer é
que iso leva un const char * palabra.

60
00:03:04,010 --> 00:03:08,960
Entón, el está tomando unha cadea como entrada, e
volvendo un int non asinado como saída.

61
00:03:08,960 --> 00:03:12,360
Entón, iso é todo unha función hash é, é
leva nunha entrada e dálle unha

62
00:03:12,360 --> 00:03:14,490
índice para a táboa hash.

63
00:03:14,490 --> 00:03:18,530
>> Teña en conta que estamos moding por num_buckets,
de xeito que o valor devolto

64
00:03:18,530 --> 00:03:21,730
en realidade, é un índice para a táboa hash
e non indexa ademais do

65
00:03:21,730 --> 00:03:24,320
límites da matriz.

66
00:03:24,320 --> 00:03:28,060
Así, dado que a función, imos
hash a palabra que lemos a

67
00:03:28,060 --> 00:03:29,390
dicionario.

68
00:03:29,390 --> 00:03:31,700
E entón nós imos usar
que hash para introducir o

69
00:03:31,700 --> 00:03:33,750
entrada na táboa hash.

70
00:03:33,750 --> 00:03:38,520
>> Hash Agora hashtable é o actual
lista ligada na táboa.

71
00:03:38,520 --> 00:03:41,410
E é moi posible
que é só NULL.

72
00:03:41,410 --> 00:03:44,960
Queremos introducir a nosa entrada no
inicio desta lista encadeada.

73
00:03:44,960 --> 00:03:48,600
E así nós imos ter a nosa actual
punto de entrada ao que o hashtable

74
00:03:48,600 --> 00:03:50,380
actualmente apunta.

75
00:03:50,380 --> 00:03:53,310
E entón nós estamos indo para almacenar,
no hashtable no

76
00:03:53,310 --> 00:03:55,350
de hash, a entrada actual.

77
00:03:55,350 --> 00:03:59,320
Entón, estas dúas liñas inserir correctamente
a entrada no comezo da

78
00:03:59,320 --> 00:04:02,260
lista ligada no que o índice de
no hashtable.

79
00:04:02,260 --> 00:04:04,900
>> Xa que estamos a facer que, sabemos
que atopamos outra palabra no

80
00:04:04,900 --> 00:04:07,790
dicionario, e incrementar de novo.

81
00:04:07,790 --> 00:04:13,960
Entón, nós continuar facendo isto ata que fscanf
finalmente volveu algo non-1 en

82
00:04:13,960 --> 00:04:16,950
que punto lembrar que
necesitamos entrada gratuíta.

83
00:04:16,950 --> 00:04:19,459
Entón aquí nós malloced unha entrada.

84
00:04:19,459 --> 00:04:21,329
E nós tratamos ler algo
desde o dicionario.

85
00:04:21,329 --> 00:04:23,910
E nós non ler correctamente
algo do dicionario, o

86
00:04:23,910 --> 00:04:26,650
caso en que necesitamos liberar a entrada
que nós nunca realmente poñer no

87
00:04:26,650 --> 00:04:29,140
hashtable, e finalmente romper.

88
00:04:29,140 --> 00:04:32,750
>> Así que saír necesitamos ver, así,
fixemos saír porque non

89
00:04:32,750 --> 00:04:34,360
Foi un erro de lectura do ficheiro?

90
00:04:34,360 --> 00:04:37,120
Ou será que nós saír, porque nós
chegou ao fin do ficheiro?

91
00:04:37,120 --> 00:04:39,480
Se houbo un erro, entón
queremos voltar false.

92
00:04:39,480 --> 00:04:40,930
Porque carga non tivo éxito.

93
00:04:40,930 --> 00:04:43,890
E no proceso, queremos descargar
todas as palabras que lemos, e

94
00:04:43,890 --> 00:04:45,670
pechar o ficheiro de dicionario.

95
00:04:45,670 --> 00:04:48,740
>> Asumindo que tivo éxito, entón nós só
aínda que pechar o dicionario

96
00:04:48,740 --> 00:04:53,040
ficheiro e, finalmente, volver certo, xa que
cargou con éxito o dicionario.

97
00:04:53,040 --> 00:04:54,420
E iso por carga.

98
00:04:54,420 --> 00:04:59,020
Entón agora comprobar, dado un hashtable cargado,
se ve así.

99
00:04:59,020 --> 00:05:03,140
Polo tanto, asegúrese de, el retorna un bool, que é
vai indicar se o pasado

100
00:05:03,140 --> 00:05:07,530
en char * palabra, o pasado
na secuencia está no noso dicionario.

101
00:05:07,530 --> 00:05:09,890
Entón, se é no dicionario,
se é do noso hashtable,

102
00:05:09,890 --> 00:05:11,170
imos voltar true.

103
00:05:11,170 --> 00:05:13,380
E se non é, imos voltar false.

104
00:05:13,380 --> 00:05:17,740
>> Dada esta aprobada en palabra, estamos
vai botar a palabra.

105
00:05:17,740 --> 00:05:22,110
Agora unha cousa importante a recoñecer é
que na carga sabiamos que todo o

106
00:05:22,110 --> 00:05:23,820
palabras que imos estar en minúsculas.

107
00:05:23,820 --> 00:05:25,820
Pero aquí non ten tanta certeza.

108
00:05:25,820 --> 00:05:29,510
Se derme un ollo a nosa función de hash,
nosa función hash realmente

109
00:05:29,510 --> 00:05:32,700
é máis baixa cobertura de cada personaxe
da palabra.

110
00:05:32,700 --> 00:05:37,940
Polo tanto, con independencia da capitalización de
palabra, a nosa función de hash é o retorno

111
00:05:37,940 --> 00:05:42,270
o mesmo índice por calquera que sexa o
capitalización é, como el

112
00:05:42,270 --> 00:05:45,280
retorno a unha totalmente minúsculas
versión da palabra.

113
00:05:45,280 --> 00:05:46,600
Todo ben.

114
00:05:46,600 --> 00:05:49,790
Ese é o noso índice é o
Hashtable a esta palabra.

115
00:05:49,790 --> 00:05:52,940
>> Agora, este loop vai
iterado sobre a lista ligada

116
00:05:52,940 --> 00:05:55,000
que estaba naquel índice.

117
00:05:55,000 --> 00:05:59,610
Entón, teña en conta que estamos arrincando entrada
para apuntar a este índice.

118
00:05:59,610 --> 00:06:02,750
Nós imos seguir
mentres entrada! = NULL.

119
00:06:02,750 --> 00:06:07,770
E lembre que a actualización do punteiro
na nosa entrada ligada list = entry> seguinte.

120
00:06:07,770 --> 00:06:14,400
Entón temos o noso punto de entrada cadea para
o seguinte elemento da lista encadeada.

121
00:06:14,400 --> 00:06:19,250
>> Así, para cada entrada na lista ligada,
imos usar strcasecmp.

122
00:06:19,250 --> 00:06:20,330
Non é SeqComp.

123
00:06:20,330 --> 00:06:23,780
Porque, unha vez máis, queremos
facer as cousas caso insensible.

124
00:06:23,780 --> 00:06:27,870
Entón, usamos strcasecmp comparar a
palabra que foi pasado a través desta

125
00:06:27,870 --> 00:06:31,860
función contra a palabra
que é nesa entrada.

126
00:06:31,860 --> 00:06:35,570
Se volve cero, é dicir que houbo
un partido, caso en que queremos

127
00:06:35,570 --> 00:06:36,630
return true.

128
00:06:36,630 --> 00:06:39,590
Atopamos con éxito a
palabra na nosa hashtable.

129
00:06:39,590 --> 00:06:43,040
>> Se non foi un xogo, entón estamos
indo a repetir de novo e ollar para o

130
00:06:43,040 --> 00:06:43,990
seguinte entrada.

131
00:06:43,990 --> 00:06:47,640
E nós imos seguir looping mentres non
son entradas nesta lista ligada.

132
00:06:47,640 --> 00:06:50,160
Qué acontece se romper
fóra deste loop for?

133
00:06:50,160 --> 00:06:55,110
Isto significa que non atopou unha entrada que
combinaba esta palabra, caso en que

134
00:06:55,110 --> 00:07:00,220
retornamos false para indicar que o noso
hashtable non contiña esta palabra.

135
00:07:00,220 --> 00:07:02,540
E iso é un cheque.

136
00:07:02,540 --> 00:07:04,790
>> Entón, imos dar un ollo ao tamaño.

137
00:07:04,790 --> 00:07:06,970
Agora o tamaño será moi sinxelo.

138
00:07:06,970 --> 00:07:11,080
Xa que lembrar en carga, para cada palabra
atopamos, temos incrementado un mundial

139
00:07:11,080 --> 00:07:12,880
tamaño variable hashtable.

140
00:07:12,880 --> 00:07:16,480
Así, a función de tamaño é só ir
para volver variable global.

141
00:07:16,480 --> 00:07:18,150
E é iso.

142
00:07:18,150 --> 00:07:22,300
>> Agora, por fin, hai que descargar o
dicionario xa que todo está feito.

143
00:07:22,300 --> 00:07:25,340
Entón, como imos facelo?

144
00:07:25,340 --> 00:07:30,440
Aquí estamos loop sobre
todo baldes de nosa mesa.

145
00:07:30,440 --> 00:07:33,240
Polo tanto, hai num_buckets baldes.

146
00:07:33,240 --> 00:07:37,410
E para cada lista ligada na nosa
hashtable, imos varrer

147
00:07:37,410 --> 00:07:41,070
a totalidade da lista encadeada,
liberando cada elemento.

148
00:07:41,070 --> 00:07:42,900
>> Agora, necesitamos ter coidado.

149
00:07:42,900 --> 00:07:47,910
Entón aquí temos unha variable temporal
que ten de almacenar o punteiro ao seguinte

150
00:07:47,910 --> 00:07:49,730
elemento da lista encadeada.

151
00:07:49,730 --> 00:07:52,140
E entón nós estamos indo a libre
o elemento actual.

152
00:07:52,140 --> 00:07:55,990
Necesitamos estar seguro de que facemos isto dende que
non pode só liberar o elemento actual

153
00:07:55,990 --> 00:07:59,180
e probe acceder o seguinte punteiro,
pois, unha vez que xa liberou-o,

154
00:07:59,180 --> 00:08:00,870
a memoria se fai válida.

155
00:08:00,870 --> 00:08:04,990
>> Entón, necesitamos manter en torno a un punteiro para
o seguinte elemento, entón podemos liberar o

156
00:08:04,990 --> 00:08:08,360
elemento actual, e entón podemos actualizar
noso elemento actual para ligar a

157
00:08:08,360 --> 00:08:09,550
o seguinte elemento.

158
00:08:09,550 --> 00:08:12,800
Imos loop while hai elementos
nesta lista encadeada.

159
00:08:12,800 --> 00:08:15,620
Imos facelo para todos conectados
listas na táboa hash.

160
00:08:15,620 --> 00:08:19,460
E xa que estamos a facer que, temos
completamente descargada a hashtable, e

161
00:08:19,460 --> 00:08:20,190
estamos a facer.

162
00:08:20,190 --> 00:08:23,200
Polo tanto, é imposible para descargar
para sempre voltar false.

163
00:08:23,200 --> 00:08:26,470
E cando estea listo, nós
basta voltar certo.

164
00:08:26,470 --> 00:08:29,000
>> Imos dar a esta solución un intento.

165
00:08:29,000 --> 00:08:33,070
Entón, imos dar un ollo ao que o noso
nó struct será semellante.

166
00:08:33,070 --> 00:08:36,220
Aquí vemos que imos ter un bool
palabra e un nó struct * nenos

167
00:08:36,220 --> 00:08:37,470
Alfabeto soporte.

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

169
00:08:38,929 --> 00:08:42,020
Entón o primeiro que pode ser
pregunta, por que é alfabeto

170
00:08:42,020 --> 00:08:44,660
ed axusta 27?

171
00:08:44,660 --> 00:08:47,900
Ben, lembre que nós imos ter
estar lidando co apóstrofo.

172
00:08:47,900 --> 00:08:51,910
Entón iso vai ser un pouco de un
caso especial durante todo este programa.

173
00:08:51,910 --> 00:08:54,710
>> Agora lembre-se como un trie
realmente funciona.

174
00:08:54,710 --> 00:08:59,380
Digamos que estamos indexando a palabra
"Gatos". A continuación, a partir da raíz de trie,

175
00:08:59,380 --> 00:09:02,610
imos ollar para os nenos
array, e imos ollar para o

176
00:09:02,610 --> 00:09:08,090
índice que corresponde á letra
C. Así que será indexado 2.

177
00:09:08,090 --> 00:09:11,530
Entón, xa que, que a vontade
ofrécenos un novo nodo.

178
00:09:11,530 --> 00:09:13,820
E entón nós imos traballar a partir dese nodo.

179
00:09:13,820 --> 00:09:17,770
>> Así, dado que nós, que estamos unha vez máis
vai mirar para a matriz fillos.

180
00:09:17,770 --> 00:09:22,110
E nós estamos indo ollar índice cero
corresponden ao A o gato.

181
00:09:22,110 --> 00:09:27,170
Entón nós estamos indo a ir a este nodo,
e dado que imos

182
00:09:27,170 --> 00:09:31,090
mirar para o final, é unha corresponde
para T. E pasar a este nodo,

183
00:09:31,090 --> 00:09:35,530
finalmente, temos totalmente mirou
a través da nosa palabra "gato". E agora bool

184
00:09:35,530 --> 00:09:40,960
palabra se quere indicar se
esta palabra dada é en realidade unha palabra.

185
00:09:40,960 --> 00:09:43,470
>> Entón, por que necesitamos nese caso especial?

186
00:09:43,470 --> 00:09:47,700
Ben, o que a palabra "catástrofe"
está no noso dicionario, pero o

187
00:09:47,700 --> 00:09:50,150
palabra "gato" non é?

188
00:09:50,150 --> 00:09:54,580
Así, e mirando a ver se a palabra "gato"
está no noso dicionario, estamos

189
00:09:54,580 --> 00:09:59,970
vai mirar con éxito a través
os índices de C-A-T na rexión do nodo.

190
00:09:59,970 --> 00:10:04,290
Pero isto é só porque catástrofe
pasou para crear nós no camiño

191
00:10:04,290 --> 00:10:07,190
desde C-A-T, todo o camiño ata
o fin da palabra.

192
00:10:07,190 --> 00:10:12,020
Entón bool palabra é usada para indicar se
este lugar especial

193
00:10:12,020 --> 00:10:14,310
realmente indica unha palabra.

194
00:10:14,310 --> 00:10:15,140
>> Todo ben.

195
00:10:15,140 --> 00:10:19,310
Polo tanto, agora que sabemos o que é trie
indo ollar como, imos ollar para o

196
00:10:19,310 --> 00:10:20,730
Cargando función.

197
00:10:20,730 --> 00:10:24,610
Así, a carga vai voltar un booleano
para saber se correctamente ou

198
00:10:24,610 --> 00:10:26,720
sen éxito cargado no dicionario.

199
00:10:26,720 --> 00:10:30,460
E este será o dicionario
que quere cargar.

200
00:10:30,460 --> 00:10:33,930
>> Entón o primeiro que estamos a facer é abrir
ata que dicionario para a lectura.

201
00:10:33,930 --> 00:10:36,160
E nós temos que estar seguro de
non falla.

202
00:10:36,160 --> 00:10:39,580
Polo tanto, se o dicionario non era
aberto correctamente, el volverá

203
00:10:39,580 --> 00:10:42,400
nula, caso en que estamos
Vai voltar false.

204
00:10:42,400 --> 00:10:47,230
Pero, supoñendo que correctamente
abriu, entón podemos realmente ler

205
00:10:47,230 --> 00:10:48,220
a través do dicionario.

206
00:10:48,220 --> 00:10:50,880
>> Entón o primeiro que imos
quero facer é que temos esta

207
00:10:50,880 --> 00:10:52,500
raíz variable global.

208
00:10:52,500 --> 00:10:56,190
Agora raíz será un nodo *.

209
00:10:56,190 --> 00:10:59,760
É o principio da nosa trie que estamos
será iterado.

210
00:10:59,760 --> 00:11:02,660
Entón o primeiro que imos
querer facer é reservar

211
00:11:02,660 --> 00:11:04,140
memoria para a nosa raíz.

212
00:11:04,140 --> 00:11:07,980
Teña en conta que estamos a usar a calloc
función, a cal é basicamente o mesmo

213
00:11:07,980 --> 00:11:11,500
como a función malloc, agás que se
garantido para voltar algo que é

214
00:11:11,500 --> 00:11:13,180
totalmente zerado.

215
00:11:13,180 --> 00:11:17,290
Entón, se usamos malloc, necesitariamos
pasar por todos os punteiros na nosa

216
00:11:17,290 --> 00:11:20,160
no, e asegúrese de que
son todos nulos.

217
00:11:20,160 --> 00:11:22,710
Entón calloc vai facelo por nós.

218
00:11:22,710 --> 00:11:26,330
>> Agora só como malloc, necesitamos facer
Asegúrese de que a dotación era de feito

219
00:11:26,330 --> 00:11:27,520
exitosa.

220
00:11:27,520 --> 00:11:29,990
Se este regresou nulo, entón nós
Debe pechar ou dicionario

221
00:11:29,990 --> 00:11:32,100
arquivo e voltar false.

222
00:11:32,100 --> 00:11:36,835
Así, supoñendo que a distribución se
exitosa, imos usar un nodo *

223
00:11:36,835 --> 00:11:40,270
cursor percorrer o noso trie.

224
00:11:40,270 --> 00:11:43,890
Entón nosas raíces nunca vai cambiar,
pero imos usar o cursor

225
00:11:43,890 --> 00:11:47,875
realmente ir de nó en nó.

226
00:11:47,875 --> 00:11:50,940
>> Polo tanto, neste loop for que estamos lendo
a través do arquivo de dicionario.

227
00:11:50,940 --> 00:11:53,670
E nós estamos usando fgetc.

228
00:11:53,670 --> 00:11:56,290
Fgetc vai pegar un único
personaxe a partir do ficheiro.

229
00:11:56,290 --> 00:11:59,370
Nós imos seguir agarrando
caracteres mentres non acadan o

230
00:11:59,370 --> 00:12:01,570
final do arquivo.

231
00:12:01,570 --> 00:12:03,480
>> Hai dous casos que debemos tratar.

232
00:12:03,480 --> 00:12:06,610
A primeira, cando o carácter
Non foi unha nova liña.

233
00:12:06,610 --> 00:12:10,450
Entón, nós sabemos si foi unha nova liña, a continuación,
estamos a piques de pasar a unha nova palabra.

234
00:12:10,450 --> 00:12:15,240
Pero supoñendo que el non era unha nova liña, a continuación,
aquí queremos descubrir a

235
00:12:15,240 --> 00:12:18,380
índice imos índice en
na matriz nenos que

236
00:12:18,380 --> 00:12:19,810
nós miramos antes.

237
00:12:19,810 --> 00:12:23,880
>> Entón, como dixen antes, necesitamos
caso especial o apóstrofo.

238
00:12:23,880 --> 00:12:26,220
Teña en conta que estamos a usar o ternário
operador aquí.

239
00:12:26,220 --> 00:12:29,580
Entón, imos ler isto como,
o personaxe que lemos na era

240
00:12:29,580 --> 00:12:35,330
apóstrofo, entón imos definir
index = "alfabeto" -1, que será

241
00:12:35,330 --> 00:12:37,680
ser o índice 26.

242
00:12:37,680 --> 00:12:41,130
>> Outra cousa, se non fose un apóstrofo, non
imos establecer o índice

243
00:12:41,130 --> 00:12:43,760
igual a c - a.

244
00:12:43,760 --> 00:12:49,030
Entón lembre-se de volta a partir anteriormente p-sets,
c - unha vai dar o

245
00:12:49,030 --> 00:12:53,410
posición alfabética de C. Polo tanto, se
C é a letra A, este será

246
00:12:53,410 --> 00:12:54,700
ofrécenos o índice cero.

247
00:12:54,700 --> 00:12:58,120
Para a letra B, que vai che dar
us o índice 1, e así por diante.

248
00:12:58,120 --> 00:13:03,010
>> Entón, iso dános o índice para a
variedade nenos que queremos.

249
00:13:03,010 --> 00:13:08,890
Agora, se ese contido é actualmente nulo na
os nenos, o que significa que un nó

250
00:13:08,890 --> 00:13:11,830
Non existe actualmente
dese camiño.

251
00:13:11,830 --> 00:13:15,160
Entón, necesitamos reservar
un nodo a este camiño.

252
00:13:15,160 --> 00:13:16,550
Iso é o que imos facer aquí.

253
00:13:16,550 --> 00:13:20,690
>> Entón imos utilizar de novo o calloc
función, de xeito que non ten por

254
00:13:20,690 --> 00:13:22,880
Restablecer todos os punteiros.

255
00:13:22,880 --> 00:13:27,240
E unha vez máis que comprobar
calloc que non fallou.

256
00:13:27,240 --> 00:13:30,700
Se calloc deixou, entón necesitamos
para descargar todo, pechar o noso

257
00:13:30,700 --> 00:13:32,820
dicionario, e voltar false.

258
00:13:32,820 --> 00:13:40,050
Así, supoñendo que non fallou, entón
iso pode crear un novo fillo para nós.

259
00:13:40,050 --> 00:13:41,930
E, a continuación, iremos para aquela neno.

260
00:13:41,930 --> 00:13:44,960
Nosa cursor ha iterado
abaixo para aquela neno.

261
00:13:44,960 --> 00:13:49,330
>> Agora, se iso non foi nula, para comezar,
a continuación, o cursor pode simplemente iterado

262
00:13:49,330 --> 00:13:52,590
ata aquela neno sen realmente
ter que reservar calquera cousa.

263
00:13:52,590 --> 00:13:56,730
Este é o caso en que pasou por primeira vez
reservar a palabra "gato". E

264
00:13:56,730 --> 00:14:00,330
isto significa que cando imos para reservar
"Catástrofe", que non precisa crear

265
00:14:00,330 --> 00:14:01,680
nós para C-A-T novo.

266
00:14:01,680 --> 00:14:04,830
Xa existen.

267
00:14:04,830 --> 00:14:06,080
>> Que é esa persoa?

268
00:14:06,080 --> 00:14:10,480
Esta é a condición na que c é
barra invertida n, onde c é unha nova liña.

269
00:14:10,480 --> 00:14:13,710
Isto significa que temos correctamente
completou unha palabra.

270
00:14:13,710 --> 00:14:16,860
Agora, o que queremos facer cando
rematou con éxito unha palabra?

271
00:14:16,860 --> 00:14:21,100
Imos usar este campo palabra
dentro do noso nodo struct.

272
00:14:21,100 --> 00:14:23,390
Queremos establecer que a verdade.

273
00:14:23,390 --> 00:14:27,150
Así que indica que este nodo
indica un éxito

274
00:14:27,150 --> 00:14:29,250
palabra, unha palabra real.

275
00:14:29,250 --> 00:14:30,940
>> Agora estableza que a verdade.

276
00:14:30,940 --> 00:14:35,150
Queremos redefinir a nosa cursor ao punto
para o inicio de trie novo.

277
00:14:35,150 --> 00:14:40,160
E, finalmente, aumentar o noso dicionario
tamaño, xa que atopamos outro traballo.

278
00:14:40,160 --> 00:14:43,230
Entón, nós imos seguir facendo iso,
a lectura en carácter por carácter,

279
00:14:43,230 --> 00:14:49,150
construción de novos nós na nosa trie e
para cada palabra no dicionario, ata

280
00:14:49,150 --> 00:14:54,020
finalmente chegar a C! = fin de ficheiro no que
caso, saír do arquivo.

281
00:14:54,020 --> 00:14:57,050
>> Agora, hai dous casos baixo
que poderiamos atinxir EOF.

282
00:14:57,050 --> 00:15:00,980
O primeiro é se houbo un erro
a lectura do ficheiro.

283
00:15:00,980 --> 00:15:03,470
Entón, se houbo un erro, nós
que facer o típico.

284
00:15:03,470 --> 00:15:06,460
Descargar todo, preto
o ficheiro, voltar false.

285
00:15:06,460 --> 00:15:09,810
Asumindo que non houbo un erro, que
significa só que realmente bater o fin do

286
00:15:09,810 --> 00:15:13,750
o ficheiro, caso en que, imos pechar o
arquivo e volver true, xa que

287
00:15:13,750 --> 00:15:17,330
dicionario cargado con éxito
na nosa trie.

288
00:15:17,330 --> 00:15:20,170
>> Entón agora imos comprobar cheque.

289
00:15:20,170 --> 00:15:25,156
Mirando para a función de comprobación, vemos
o cheque vai voltar un booleano.

290
00:15:25,156 --> 00:15:29,680
El retorna true se esta palabra, que é
sendo pasado está no noso trie.

291
00:15:29,680 --> 00:15:32,110
El retorna false caso contrario.

292
00:15:32,110 --> 00:15:36,050
Entón, como determinar se
esta palabra é na nosa trie?

293
00:15:36,050 --> 00:15:40,190
>> Vemos aquí que, como antes,
imos usar cursor iterado

294
00:15:40,190 --> 00:15:41,970
a través da nosa trie.

295
00:15:41,970 --> 00:15:46,600
Agora, aquí imos facer unha iteración
ao longo de toda a nosa palabra.

296
00:15:46,600 --> 00:15:50,620
Entón iteración sobre a palabra que estamos pasado
imos determinar a

297
00:15:50,620 --> 00:15:56,400
índice para a matriz que os nenos
corresponde á palabra soporte I. Polo tanto, este

298
00:15:56,400 --> 00:15:59,670
vai parecer exactamente como
de carga, onde se palabra [i]

299
00:15:59,670 --> 00:16:03,310
é un apóstrofo, entón queremos
usar index "alfabeto" - 1.

300
00:16:03,310 --> 00:16:05,350
Porque foi determinado que a referida
é o lugar onde nós estamos indo para almacenar

301
00:16:05,350 --> 00:16:07,100
apóstrofos.

302
00:16:07,100 --> 00:16:11,780
>> Else imos usar dous inferiores palabra
soporte I. Entón lembre que a palabra pode

303
00:16:11,780 --> 00:16:13,920
ten capitalización arbitraria.

304
00:16:13,920 --> 00:16:17,540
E por iso queremos estar seguro de que estamos
usando unha versión minúscula das cousas.

305
00:16:17,540 --> 00:16:21,920
E, a continuación, restar de que 'a' para unha vez
novo dar a alfabética

306
00:16:21,920 --> 00:16:23,880
posición dese personaxe.

307
00:16:23,880 --> 00:16:27,680
Entón iso vai ser o noso índice
para a matriz de nenos.

308
00:16:27,680 --> 00:16:32,420
>> E agora, se este índice para os nenos
matriz é nulo, isto significa que

309
00:16:32,420 --> 00:16:34,990
non pode seguir iteración
abaixo a nosa trie.

310
00:16:34,990 --> 00:16:38,870
En tal caso, esta palabra non pode
posiblemente estar na nosa trie.

311
00:16:38,870 --> 00:16:42,340
Sempre que fose, que sería
quere dicir que habería un camiño

312
00:16:42,340 --> 00:16:43,510
abaixo para esa palabra.

313
00:16:43,510 --> 00:16:45,290
E nunca ía atopar nulo.

314
00:16:45,290 --> 00:16:47,850
Así, atopando nulo, nós voltar false.

315
00:16:47,850 --> 00:16:49,840
A palabra non está no dicionario.

316
00:16:49,840 --> 00:16:53,660
Se non fose nulo, entón estamos
seguirá a iteración.

317
00:16:53,660 --> 00:16:57,220
>> Entón, imos por aí cursor
salientar que a especial

318
00:16:57,220 --> 00:16:59,760
nó nese índice.

319
00:16:59,760 --> 00:17:03,150
Nós continuar facendo iso ao longo
a palabra, asumindo

320
00:17:03,150 --> 00:17:03,950
nunca bateu nulo.

321
00:17:03,950 --> 00:17:07,220
Isto significa que fomos capaces de pasar
toda a palabra e atopar

322
00:17:07,220 --> 00:17:08,920
un nó na nosa intento.

323
00:17:08,920 --> 00:17:10,770
Pero nós non estamos totalmente feito aínda.

324
00:17:10,770 --> 00:17:12,290
>> Non queremos só retornar true.

325
00:17:12,290 --> 00:17:14,770
Queremos volver cursor> palabra.

326
00:17:14,770 --> 00:17:18,980
Desde lembrar unha vez máis, é o "gato" non é
na nosa dicionario, e "catástrofe"

327
00:17:18,980 --> 00:17:22,935
é, entón imos correctamente obtemos
a través da palabra "gato". Pero cursor

328
00:17:22,935 --> 00:17:25,760
palabra será falso e non é verdade.

329
00:17:25,760 --> 00:17:30,930
Entón volvemos palabra cursor indicar
se este nodo é realmente unha palabra.

330
00:17:30,930 --> 00:17:32,470
E iso por cheque.

331
00:17:32,470 --> 00:17:34,250
>> Entón, imos comprobar o tamaño.

332
00:17:34,250 --> 00:17:37,350
Así, o tamaño será moi fácil
xa que, lembre-se da carga, somos

333
00:17:37,350 --> 00:17:41,430
incrementando tamaño do dicionario para
cada palabra que atopamos.

334
00:17:41,430 --> 00:17:45,350
Así, o tamaño é só ir a
voltar tamaño do dicionario.

335
00:17:45,350 --> 00:17:47,390
E é iso.

336
00:17:47,390 --> 00:17:50,590
>> Entón, por fin, temos descargar.

337
00:17:50,590 --> 00:17:55,100
Entón, descargar, imos utilizar un
función recursiva para realmente facer todo

338
00:17:55,100 --> 00:17:56,530
do traballo para nós.

339
00:17:56,530 --> 00:17:59,340
Polo tanto, a nosa función vai
ser chamado descarga.

340
00:17:59,340 --> 00:18:01,650
O que está Descarregador vai facer?

341
00:18:01,650 --> 00:18:06,580
Vemos aquí que Descarregador vai
iterado sobre todos os nenos en

342
00:18:06,580 --> 00:18:08,410
este nodo particular.

343
00:18:08,410 --> 00:18:11,750
E se o nodo fillo non é
nulo, entón imos

344
00:18:11,750 --> 00:18:13,730
descargar o no fillo.

345
00:18:13,730 --> 00:18:18,010
>> Polo tanto, este é vostede recursivamente descargar
todos os nosos fillos.

346
00:18:18,010 --> 00:18:21,080
Unha vez que temos a certeza de que todos os nosos fillos
fosen descargados, entón nós

347
00:18:21,080 --> 00:18:25,210
pode liberar-nos, por iso,
nós descargar.

348
00:18:25,210 --> 00:18:29,460
Isto ha traballar de forma recursiva
descargar toda a trie.

349
00:18:29,460 --> 00:18:32,850
E, a continuación, unha vez que está feito,
podemos simplemente voltar true.

350
00:18:32,850 --> 00:18:34,210
Unload non pode fallar.

351
00:18:34,210 --> 00:18:35,710
Nós só estamos liberando cousas.

352
00:18:35,710 --> 00:18:38,870
Así, unha vez que estamos a facer liberando
todo, volver true.

353
00:18:38,870 --> 00:18:40,320
E é iso.

354
00:18:40,320 --> 00:18:41,080
O meu nome é Rob.

355
00:18:41,080 --> 00:18:42,426
E esta foi Speller.

356
00:18:42,426 --> 00:18:47,830
>> [Música tocando]