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 vamos a solução para fora.

5
00:00:16,210 --> 00:00:20,070
Então, aqui vamos implementar
uma tabela geral.

6
00:00:20,070 --> 00:00:24,090
Vemos que o nó struct do nosso
mesa vai ficar assim.

7
00:00:24,090 --> 00:00:28,710
Por isso, vai ter uma palavra de char
matriz de tamanho COMPRIMENTO + 1.

8
00:00:28,710 --> 00:00:32,259
Não se esqueça do + 1, já que o máximo
palavra no dicionário é de 45

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

10
00:00:33,130 --> 00:00:37,070
E então nós vamos precisar de um adicional
caracteres para o zero, barra invertida.

11
00:00:37,070 --> 00:00:40,870
>> E então nossa hashtable em cada
balde vai armazenar uma

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

13
00:00:42,320 --> 00:00:44,420
Nós não estamos fazendo linear sondagem aqui.

14
00:00:44,420 --> 00:00:48,430
E assim, a fim de vincular a próxima
elemento no balde, precisamos de um

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

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

17
00:00:51,110 --> 00:00:53,090
Então é isso que um nó se parece.

18
00:00:53,090 --> 00:00:56,180
>> Agora aqui é a declaração
da nossa hashtable.

19
00:00:56,180 --> 00:00:59,640
Vai ter 16834 baldes.

20
00:00:59,640 --> 00:01:01,910
Mas esse número não importa realmente.

21
00:01:01,910 --> 00:01:05,450
E, finalmente, vamos ter o
hashtable tamanho variável global, que

22
00:01:05,450 --> 00:01:07,000
vai começar como zero.

23
00:01:07,000 --> 00:01:10,760
E isso vai se manter a par de como
muitas palavras estão em nosso dicionário.

24
00:01:10,760 --> 00:01:13,710
>> Então, vamos dar uma olhada em carga.

25
00:01:13,710 --> 00:01:16,390
Observe que a carga, ele retorna um bool.

26
00:01:16,390 --> 00:01:20,530
Você retorna verdadeiro se fosse com sucesso
carregado e false caso contrário.

27
00:01:20,530 --> 00:01:23,990
E leva um const char * dicionário,
que é o dicionário

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

29
00:01:25,280 --> 00:01:27,170
Então essa é a primeira coisa
vamos fazer.

30
00:01:27,170 --> 00:01:29,500
>> Nós estamos indo para o fopen
dicionário para a leitura.

31
00:01:29,500 --> 00:01:31,680
E nós vamos ter que fazer
certeza de que ele conseguiu.

32
00:01:31,680 --> 00:01:35,920
Então, se ele retornou NULL, então nós não
abrir com êxito o dicionário.

33
00:01:35,920 --> 00:01:37,440
E nós precisamos retornar false.

34
00:01:37,440 --> 00:01:41,580
Mas supondo que ele fez com sucesso
aberta, então nós queremos ler a

35
00:01:41,580 --> 00:01:42,400
dicionário.

36
00:01:42,400 --> 00:01:46,450
Portanto, manter looping até que encontremos algum
motivo para romper esse ciclo,

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

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

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

40
00:01:51,780 --> 00:01:54,020
E é claro que precisamos
para o ar clique aqui.

41
00:01:54,020 --> 00:01:58,680
Então, se mallocing não teve sucesso, então
queremos descarregar qualquer nó que

42
00:01:58,680 --> 00:02:02,590
aconteceu com malloc antes, fechar o
dicionário e retornar false.

43
00:02:02,590 --> 00:02:06,830
Mas ignorar que, assumindo que
conseguiu, então nós queremos usar fscanf

44
00:02:06,830 --> 00:02:12,400
para ler uma única palavra do nosso
dicionário para o nosso nó.

45
00:02:12,400 --> 00:02:17,940
Então lembre-se que a entrada> palavra é o caractere
tampão palavra de tamanho Lenghth + 1

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

47
00:02:20,300 --> 00:02:25,070
>> Então fscanf vai retornar 1, contanto
como era capaz de sucesso

48
00:02:25,070 --> 00:02:26,750
ler uma palavra a partir do arquivo.

49
00:02:26,750 --> 00:02:30,460
Se algum erro acontecer, ou nós
chegar ao final do arquivo, ele

50
00:02:30,460 --> 00:02:31,950
não retornará 1.

51
00:02:31,950 --> 00:02:35,180
No caso em que ele não retorna 1,
estamos finalmente vai sair do

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

53
00:02:37,280 --> 00:02:42,770
Assim, vemos que uma vez que temos com sucesso
ler uma palavra em

54
00:02:42,770 --> 00:02:48,270
entry> palavra, então nós estamos indo para que
palavra usando nossa função hash.

55
00:02:48,270 --> 00:02:49,580
>> Vamos dar uma olhada
a função hash.

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

57
00:02:52,430 --> 00:02:55,610
Então, você realmente não precisa
para entender isso.

58
00:02:55,610 --> 00:02:59,460
E, na verdade, nós apenas puxou esse hash
funcionar a partir da internet.

59
00:02:59,460 --> 00:03:04,010
A única coisa que você precisa reconhecer é
que isso leva um const char * palavra.

60
00:03:04,010 --> 00:03:08,960
Então, ele está tomando uma string como entrada, e
retornando um int não assinado como saída.

61
00:03:08,960 --> 00:03:12,360
Então, isso é tudo uma função hash é, é
leva em uma entrada e dá-lhe uma

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

63
00:03:14,490 --> 00:03:18,530
>> Observe que estamos moding por num_buckets,
de modo que o valor devolvido

64
00:03:18,530 --> 00:03:21,730
na verdade, é um índice para a tabela hash
e não indexa além do

65
00:03:21,730 --> 00:03:24,320
limites da matriz.

66
00:03:24,320 --> 00:03:28,060
Assim, dado que a função, vamos
hash a palavra que lemos a

67
00:03:28,060 --> 00:03:29,390
dicionário.

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

69
00:03:31,700 --> 00:03:33,750
entrada na tabela hash.

70
00:03:33,750 --> 00:03:38,520
>> Hash Agora hashtable é o atual
lista ligada na tabela.

71
00:03:38,520 --> 00:03:41,410
E é muito possível
que é apenas NULL.

72
00:03:41,410 --> 00:03:44,960
Queremos inserir a nossa entrada no
início desta lista encadeada.

73
00:03:44,960 --> 00:03:48,600
E assim nós vamos ter a nossa atual
ponto de entrada para o que o hashtable

74
00:03:48,600 --> 00:03:50,380
atualmente aponta.

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

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

77
00:03:55,350 --> 00:03:59,320
Então, essas duas linhas inserir com sucesso
a entrada no começo da

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

79
00:04:02,260 --> 00:04:04,900
>> Uma vez que estamos a fazer com que, nós sabemos
que encontramos uma outra palavra no

80
00:04:04,900 --> 00:04:07,790
dicionário, e incrementar novamente.

81
00:04:07,790 --> 00:04:13,960
Então, nós continuar fazendo isso até que fscanf
finalmente voltou algo não-1 em

82
00:04:13,960 --> 00:04:16,950
que ponto se lembrar que
precisamos entrada gratuita.

83
00:04:16,950 --> 00:04:19,459
Então aqui nós malloced uma entrada.

84
00:04:19,459 --> 00:04:21,329
E nós tentamos ler algo
a partir do dicionário.

85
00:04:21,329 --> 00:04:23,910
E nós não lido com sucesso
algo do dicionário, no

86
00:04:23,910 --> 00:04:26,650
caso em que precisamos de libertar a entrada
que nós nunca realmente colocar no

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

88
00:04:29,140 --> 00:04:32,750
>> Assim que sair nós precisamos ver, bem,
fizemos sair porque não

89
00:04:32,750 --> 00:04:34,360
Foi um erro de leitura do arquivo?

90
00:04:34,360 --> 00:04:37,120
Ou será que nós sair, porque nós
chegou ao fim do arquivo?

91
00:04:37,120 --> 00:04:39,480
Se houve um erro, então
queremos retornar false.

92
00:04:39,480 --> 00:04:40,930
Porque carga não teve êxito.

93
00:04:40,930 --> 00:04:43,890
E no processo, queremos descarregar
todas as palavras que lemos, e

94
00:04:43,890 --> 00:04:45,670
fechar o arquivo de dicionário.

95
00:04:45,670 --> 00:04:48,740
>> Assumindo que teve sucesso, então nós apenas
ainda precisa fechar o dicionário

96
00:04:48,740 --> 00:04:53,040
arquivo e, finalmente, retornar verdadeiro, uma vez que
carregou com êxito o dicionário.

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

98
00:04:54,420 --> 00:04:59,020
Então agora verificar, dado um hashtable carregado,
vai ficar assim.

99
00:04:59,020 --> 00:05:03,140
Portanto, verifique, ele retorna um bool, que é
vai indicar se o passado

100
00:05:03,140 --> 00:05:07,530
em char * palavra, se o passado
na seqüência está no nosso dicionário.

101
00:05:07,530 --> 00:05:09,890
Então, se é no dicionário,
se é do nosso hashtable,

102
00:05:09,890 --> 00:05:11,170
vamos retornar true.

103
00:05:11,170 --> 00:05:13,380
E se não for, vamos retornar false.

104
00:05:13,380 --> 00:05:17,740
>> Dada esta aprovada em palavra, estamos
vai botar a palavra.

105
00:05:17,740 --> 00:05:22,110
Agora uma coisa importante a reconhecer é
que na carga sabíamos que toda a

106
00:05:22,110 --> 00:05:23,820
palavras que vamos estar em minúsculas.

107
00:05:23,820 --> 00:05:25,820
Mas aqui não tem tanta certeza.

108
00:05:25,820 --> 00:05:29,510
Se dermos uma olhada em nossa função de hash,
nossa função hash realmente

109
00:05:29,510 --> 00:05:32,700
é mais baixa cobertura de cada personagem
da palavra.

110
00:05:32,700 --> 00:05:37,940
Portanto, independentemente da capitalização de
palavra, a nossa função de hash é o retorno

111
00:05:37,940 --> 00:05:42,270
o mesmo índice por qualquer que seja o
capitalização é, como ele teria

112
00:05:42,270 --> 00:05:45,280
retornado para uma completamente minúsculas
versão da palavra.

113
00:05:45,280 --> 00:05:46,600
Tudo bem.

114
00:05:46,600 --> 00:05:49,790
Esse é o nosso índice é no
Hashtable para esta palavra.

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

116
00:05:52,940 --> 00:05:55,000
que estava naquele índice.

117
00:05:55,000 --> 00:05:59,610
Então, observe que estamos inicializando entrada
para apontar para esse índice.

118
00:05:59,610 --> 00:06:02,750
Nós vamos continuar
enquanto entrada! = NULL.

119
00:06:02,750 --> 00:06:07,770
E lembre-se que a atualização do ponteiro
em nossa entrada ligada list = entry> seguinte.

120
00:06:07,770 --> 00:06:14,400
Então temos o nosso ponto de entrada corrente para
o próximo item na lista encadeada.

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

122
00:06:19,250 --> 00:06:20,330
Não é SeqComp.

123
00:06:20,330 --> 00:06:23,780
Porque, mais uma vez, nós queremos
fazer as coisas caso insensível.

124
00:06:23,780 --> 00:06:27,870
Então, nós usamos strcasecmp comparar a
palavra que foi passado através desta

125
00:06:27,870 --> 00:06:31,860
função contra a palavra
que é nessa entrada.

126
00:06:31,860 --> 00:06:35,570
Se ela retorna zero, que significa que houve
uma partida, caso em que queremos

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

128
00:06:36,630 --> 00:06:39,590
Encontramos com sucesso a
palavra em nossa hashtable.

129
00:06:39,590 --> 00:06:43,040
>> Se não foi um jogo, então estamos
indo para repetir novamente e olhar para o

130
00:06:43,040 --> 00:06:43,990
próxima entrada.

131
00:06:43,990 --> 00:06:47,640
E nós vamos continuar looping enquanto não
são entradas nesta lista ligada.

132
00:06:47,640 --> 00:06:50,160
O que acontece se quebrar
fora deste loop for?

133
00:06:50,160 --> 00:06:55,110
Isso significa que não encontrou uma entrada que
combinava esta palavra, caso em que

134
00:06:55,110 --> 00:07:00,220
retornamos false para indicar que o nosso
hashtable não continha esta palavra.

135
00:07:00,220 --> 00:07:02,540
E isso é um cheque.

136
00:07:02,540 --> 00:07:04,790
>> Então, vamos dar uma olhada no tamanho.

137
00:07:04,790 --> 00:07:06,970
Agora o tamanho vai ser muito simples.

138
00:07:06,970 --> 00:07:11,080
Uma vez que se lembrar em carga, para cada palavra
encontramos, temos incrementado um mundial

139
00:07:11,080 --> 00:07:12,880
tamanho variável hashtable.

140
00:07:12,880 --> 00:07:16,480
Assim, a função de tamanho é só ir
para voltar variável global.

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

142
00:07:18,150 --> 00:07:22,300
>> Agora, finalmente, é preciso descarregar o
dicionário uma vez que tudo é feito.

143
00:07:22,300 --> 00:07:25,340
Então, como vamos fazer isso?

144
00:07:25,340 --> 00:07:30,440
Aqui estamos loop sobre
todos os baldes de nossa mesa.

145
00:07:30,440 --> 00:07:33,240
Portanto, há num_buckets baldes.

146
00:07:33,240 --> 00:07:37,410
E para cada lista ligada em nosso
hashtable, vamos 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, precisamos ter cuidado.

149
00:07:42,900 --> 00:07:47,910
Então aqui nós temos uma variável temporária
que tem de armazenar o ponteiro para o próximo

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

151
00:07:49,730 --> 00:07:52,140
E então nós estamos indo para livre
o elemento atual.

152
00:07:52,140 --> 00:07:55,990
Precisamos ter certeza de que fazemos isso desde que
não pode apenas liberar o elemento atual

153
00:07:55,990 --> 00:07:59,180
e tente acessar o próximo ponteiro,
pois, uma vez que já libertou-o,

154
00:07:59,180 --> 00:08:00,870
a memória se torna inválida.

155
00:08:00,870 --> 00:08:04,990
>> Então, precisamos manter em torno de um ponteiro para
o próximo elemento, então podemos liberar o

156
00:08:04,990 --> 00:08:08,360
elemento atual, e então nós podemos atualizar
nosso elemento atual para apontar para

157
00:08:08,360 --> 00:08:09,550
o próximo elemento.

158
00:08:09,550 --> 00:08:12,800
Vamos loop while há elementos
nesta lista encadeada.

159
00:08:12,800 --> 00:08:15,620
Vamos fazer isso para todos ligados
listas na tabela hash.

160
00:08:15,620 --> 00:08:19,460
E uma vez que estamos a fazer com que, nós temos
completamente descarregada a hashtable, e

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

162
00:08:20,190 --> 00:08:23,200
Portanto, é impossível para descarregar
para sempre retornar false.

163
00:08:23,200 --> 00:08:26,470
E quando estiver pronto, nós
basta retornar verdadeiro.

164
00:08:26,470 --> 00:08:29,000
>> Vamos dar a esta solução uma tentativa.

165
00:08:29,000 --> 00:08:33,070
Então, vamos dar uma olhada no que o nosso
nó struct será semelhante.

166
00:08:33,070 --> 00:08:36,220
Aqui vemos que vamos ter um bool
palavra e um nó struct * crianças

167
00:08:36,220 --> 00:08:37,470
ALFABETO suporte.

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

169
00:08:38,929 --> 00:08:42,020
Então a primeira coisa que você pode ser
perguntando, por que é ALFABETO

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

171
00:08:44,660 --> 00:08:47,900
Bem, lembre-se que nós vamos precisar
estar lidando com o apóstrofo.

172
00:08:47,900 --> 00:08:51,910
Então isso vai ser um pouco de um
caso especial durante todo este programa.

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

174
00:08:54,710 --> 00:08:59,380
Digamos que estamos indexando a palavra
"gatos". Em seguida, a partir da raiz de trie,

175
00:08:59,380 --> 00:09:02,610
vamos olhar para as crianças
array, e vamos olhar para o

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

177
00:09:08,090 --> 00:09:11,530
Então, uma vez que, que a vontade
dá-nos um novo nó.

178
00:09:11,530 --> 00:09:13,820
E então nós vamos trabalhar a partir desse nó.

179
00:09:13,820 --> 00:09:17,770
>> Assim, dado que nós, que estamos mais uma vez
vai olhar para a matriz filhos.

180
00:09:17,770 --> 00:09:22,110
E nós estamos indo olhar índice zero
corresponder ao A no gato.

181
00:09:22,110 --> 00:09:27,170
Então nós estamos indo para ir para esse nó,
e dado que nós vamos

182
00:09:27,170 --> 00:09:31,090
de olhar para o final, é uma corresponde
para T. E passar para esse nó,

183
00:09:31,090 --> 00:09:35,530
finalmente, temos completamente olhou
através da nossa palavra "gato". E agora bool

184
00:09:35,530 --> 00:09:40,960
palavra é suposto indicar se
esta palavra dada é na verdade uma palavra.

185
00:09:40,960 --> 00:09:43,470
>> Então, por que precisamos nesse caso especial?

186
00:09:43,470 --> 00:09:47,700
Bem, o que a palavra "catástrofe"
está no nosso dicionário, mas o

187
00:09:47,700 --> 00:09:50,150
palavra "gato" não é?

188
00:09:50,150 --> 00:09:54,580
Assim, e olhando para ver se a palavra "gato"
está no nosso dicionário, estamos

189
00:09:54,580 --> 00:09:59,970
vai olhar com sucesso através
os índices de C-A-T na região do nó.

190
00:09:59,970 --> 00:10:04,290
Mas isso é só porque catástrofe
aconteceu para criar nós no caminho

191
00:10:04,290 --> 00:10:07,190
a partir de C-A-T, todo o caminho até
o fim da palavra.

192
00:10:07,190 --> 00:10:12,020
Então bool palavra é usada para indicar se
este local especial

193
00:10:12,020 --> 00:10:14,310
realmente indica uma palavra.

194
00:10:14,310 --> 00:10:15,140
>> Tudo bem.

195
00:10:15,140 --> 00:10:19,310
Portanto, agora que sabemos o que é trie
indo olhar como, vamos olhar para o

196
00:10:19,310 --> 00:10:20,730
carregar função.

197
00:10:20,730 --> 00:10:24,610
Assim, a carga vai retornar um booleano
para saber se com sucesso ou

198
00:10:24,610 --> 00:10:26,720
sem sucesso carregado no dicionário.

199
00:10:26,720 --> 00:10:30,460
E este vai ser o dicionário
que deseja carregar.

200
00:10:30,460 --> 00:10:33,930
>> Então a primeira coisa que estamos a fazer é abrir
até que dicionário para a leitura.

201
00:10:33,930 --> 00:10:36,160
E nós temos que ter certeza de
nós não falhar.

202
00:10:36,160 --> 00:10:39,580
Portanto, se o dicionário não era
aberto com sucesso, ele retornará

203
00:10:39,580 --> 00:10:42,400
nula, caso em que estamos
vai retornar false.

204
00:10:42,400 --> 00:10:47,230
Mas, supondo que com sucesso
abriu, então podemos realmente ler

205
00:10:47,230 --> 00:10:48,220
através do dicionário.

206
00:10:48,220 --> 00:10:50,880
>> Então a primeira coisa que vamos
quero fazer é que temos esta

207
00:10:50,880 --> 00:10:52,500
raiz variável global.

208
00:10:52,500 --> 00:10:56,190
Agora raiz vai ser um nó *.

209
00:10:56,190 --> 00:10:59,760
É o topo da nossa trie que estamos
vai ser iterar.

210
00:10:59,760 --> 00:11:02,660
Então a primeira coisa que vamos
querer fazer é alocar

211
00:11:02,660 --> 00:11:04,140
memória para a nossa raiz.

212
00:11:04,140 --> 00:11:07,980
Observe que estamos usando a calloc
função, a qual é basicamente a mesma

213
00:11:07,980 --> 00:11:11,500
como a função malloc, exceto que é
garantido para retornar algo que é

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

215
00:11:13,180 --> 00:11:17,290
Então, se nós usamos malloc, precisaríamos
passar por todos os ponteiros em nossa

216
00:11:17,290 --> 00:11:20,160
nó, e certifique-se de que
eles são todos nulos.

217
00:11:20,160 --> 00:11:22,710
Então calloc vai fazer isso por nós.

218
00:11:22,710 --> 00:11:26,330
>> Agora apenas como malloc, precisamos fazer
Certifique-se que a dotação era de fato

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

220
00:11:27,520 --> 00:11:29,990
Se este retornou nulo, então nós
precisa fechar ou dicionário

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

222
00:11:32,100 --> 00:11:36,835
Assim, supondo que a alocação foi
bem sucedida, vamos usar um nó *

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

224
00:11:40,270 --> 00:11:43,890
Então nossas raízes nunca vai mudar,
mas vamos usar o cursor para

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

226
00:11:47,875 --> 00:11:50,940
>> Portanto, neste loop for que estamos lendo
através do arquivo de dicionário.

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 um único
personagem a partir do arquivo.

229
00:11:56,290 --> 00:11:59,370
Nós vamos continuar agarrando
caracteres enquanto não atingem o

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

231
00:12:01,570 --> 00:12:03,480
>> Há dois casos que temos de lidar.

232
00:12:03,480 --> 00:12:06,610
O primeiro, quando o carácter
Não foi uma nova linha.

233
00:12:06,610 --> 00:12:10,450
Então, nós sabemos se foi uma nova linha, em seguida,
estamos prestes a passar para uma nova palavra.

234
00:12:10,450 --> 00:12:15,240
Mas supondo que ele não era uma nova linha, em seguida,
aqui nós queremos descobrir a

235
00:12:15,240 --> 00:12:18,380
índice vamos índice em
na matriz crianças que

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

237
00:12:19,810 --> 00:12:23,880
>> Então, como eu disse antes, nós precisamos
caso especial o apóstrofo.

238
00:12:23,880 --> 00:12:26,220
Observe que estamos usando o ternário
operador aqui.

239
00:12:26,220 --> 00:12:29,580
Então, vamos ler isso como, se
o personagem que lemos na era

240
00:12:29,580 --> 00:12:35,330
apóstrofo, então vamos 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 coisa, se não fosse um apóstrofo, não
vamos definir 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ão lembre-se de volta a partir anteriormente p-sets,
c - uma vai nos dar o

245
00:12:49,030 --> 00:12:53,410
posição alfabética de C. Portanto, se
C é a letra A, este será

246
00:12:53,410 --> 00:12:54,700
dá-nos o índice zero.

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

248
00:12:58,120 --> 00:13:03,010
>> Então, isso nos dá o índice para a
variedade crianças que nós queremos.

249
00:13:03,010 --> 00:13:08,890
Agora, se esse índice é actualmente nulo na
as crianças, o que significa que um nó

250
00:13:08,890 --> 00:13:11,830
não existe actualmente
desse caminho.

251
00:13:11,830 --> 00:13:15,160
Então, precisamos alocar
um nó para esse caminho.

252
00:13:15,160 --> 00:13:16,550
Isso é o que nós vamos fazer aqui.

253
00:13:16,550 --> 00:13:20,690
>> Então vamos usar novamente o calloc
função, de modo que não temos a

254
00:13:20,690 --> 00:13:22,880
zerar todos os ponteiros.

255
00:13:22,880 --> 00:13:27,240
E mais uma vez precisa verificar
calloc que não falhou.

256
00:13:27,240 --> 00:13:30,700
Se calloc deixou, então precisamos
para descarregar tudo, fechar o nosso

257
00:13:30,700 --> 00:13:32,820
dicionário, e retornar false.

258
00:13:32,820 --> 00:13:40,050
Assim, supondo que ele não falhou, então
isso irá criar um novo filho para nós.

259
00:13:40,050 --> 00:13:41,930
E, em seguida, iremos para aquela criança.

260
00:13:41,930 --> 00:13:44,960
Nossa cursor irá iterar
para baixo para aquela criança.

261
00:13:44,960 --> 00:13:49,330
>> Agora, se isso não foi nula, para começar,
em seguida, o cursor pode simplesmente iterar

262
00:13:49,330 --> 00:13:52,590
até aquela criança sem realmente
ter de alocar qualquer coisa.

263
00:13:52,590 --> 00:13:56,730
Este é o caso em que aconteceu pela primeira vez
alocar a palavra "gato". E

264
00:13:56,730 --> 00:14:00,330
isso significa que quando vamos para alocar
"Catástrofe", que não precisa criar

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

266
00:14:01,680 --> 00:14:04,830
Eles já existem.

267
00:14:04,830 --> 00:14:06,080
>> O que é essa pessoa?

268
00:14:06,080 --> 00:14:10,480
Esta é a condição em que c é
barra invertida n, onde c é uma nova linha.

269
00:14:10,480 --> 00:14:13,710
Isso significa que nós temos com sucesso
completou uma palavra.

270
00:14:13,710 --> 00:14:16,860
Agora, o que nós queremos fazer quando
concluiu com êxito uma palavra?

271
00:14:16,860 --> 00:14:21,100
Vamos usar este campo palavra
dentro do nosso nó struct.

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

273
00:14:23,390 --> 00:14:27,150
Assim que indica que este nó
indica um sucesso

274
00:14:27,150 --> 00:14:29,250
palavra, uma palavra real.

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

276
00:14:30,940 --> 00:14:35,150
Queremos redefinir a nossa cursor para o ponto
para o início de trie novamente.

277
00:14:35,150 --> 00:14:40,160
E, finalmente, aumentar nosso dicionário
tamanho, uma vez que encontramos um outro trabalho.

278
00:14:40,160 --> 00:14:43,230
Então, nós vamos continuar fazendo isso,
a leitura em caractere por caractere,

279
00:14:43,230 --> 00:14:49,150
construção de novos nós na nossa trie e
para cada palavra no dicionário, até

280
00:14:49,150 --> 00:14:54,020
finalmente chegar a C! = EOF, em que
caso, sair do arquivo.

281
00:14:54,020 --> 00:14:57,050
>> Agora, existem dois casos sob
que poderíamos ter atingido EOF.

282
00:14:57,050 --> 00:15:00,980
A primeira é se houve um erro
a leitura do arquivo.

283
00:15:00,980 --> 00:15:03,470
Então, se houve um erro, nós
precisa fazer o típico.

284
00:15:03,470 --> 00:15:06,460
Descarregar tudo, perto
o arquivo, retornar false.

285
00:15:06,460 --> 00:15:09,810
Assumindo que não houve um erro, que
significa apenas que nós realmente bater o fim do

286
00:15:09,810 --> 00:15:13,750
o arquivo, caso em que, vamos fechar o
arquivo e retornar true, uma vez que

287
00:15:13,750 --> 00:15:17,330
dicionário carregado com êxito
em nosso trie.

288
00:15:17,330 --> 00:15:20,170
>> Então agora vamos verificar cheque.

289
00:15:20,170 --> 00:15:25,156
Olhando para a função de verificação, vemos
o cheque vai retornar um booleano.

290
00:15:25,156 --> 00:15:29,680
Ele retorna true se esta palavra, que é
sendo passado está em nosso trie.

291
00:15:29,680 --> 00:15:32,110
Ele retorna false caso contrário.

292
00:15:32,110 --> 00:15:36,050
Então, como você determinar se
esta palavra é em nossa trie?

293
00:15:36,050 --> 00:15:40,190
>> Vemos aqui que, como antes,
vamos usar cursor para iterar

294
00:15:40,190 --> 00:15:41,970
através do nosso trie.

295
00:15:41,970 --> 00:15:46,600
Agora, aqui vamos fazer uma iteração
ao longo de toda a nossa palavra.

296
00:15:46,600 --> 00:15:50,620
Então iteração sobre a palavra que estamos passado,
vamos determinar a

297
00:15:50,620 --> 00:15:56,400
índice para a matriz que as crianças
corresponde à palavra suporte I. Portanto, este

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

299
00:15:59,670 --> 00:16:03,310
é um apóstrofo, então nós 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 armazenar

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

302
00:16:07,100 --> 00:16:11,780
>> Else vamos usar dois inferiores palavra
suporte I. Então lembre-se que a palavra pode

303
00:16:11,780 --> 00:16:13,920
tem capitalização arbitrária.

304
00:16:13,920 --> 00:16:17,540
E por isso queremos ter certeza de que estamos
usando uma versão minúscula das coisas.

305
00:16:17,540 --> 00:16:21,920
E, em seguida, subtrair de que 'a' para uma vez
novamente nos dar a alfabética

306
00:16:21,920 --> 00:16:23,880
posição desse personagem.

307
00:16:23,880 --> 00:16:27,680
Então isso vai ser o nosso índice
para a matriz de crianças.

308
00:16:27,680 --> 00:16:32,420
>> E agora, se esse índice para as crianças
matriz é nulo, isso significa que

309
00:16:32,420 --> 00:16:34,990
não pode mais continuar a iteração
para baixo a nossa trie.

310
00:16:34,990 --> 00:16:38,870
Se for esse o caso, esta palavra não pode
possivelmente estar na nossa trie.

311
00:16:38,870 --> 00:16:42,340
Desde que fosse, que seria
significa que haveria um caminho

312
00:16:42,340 --> 00:16:43,510
para baixo para essa palavra.

313
00:16:43,510 --> 00:16:45,290
E você nunca iria encontrar nulo.

314
00:16:45,290 --> 00:16:47,850
Assim, encontrando nulo, nós retornar false.

315
00:16:47,850 --> 00:16:49,840
A palavra não está no dicionário.

316
00:16:49,840 --> 00:16:53,660
Se não fosse nulo, então estamos
vai continuar a iteração.

317
00:16:53,660 --> 00:16:57,220
>> Então, vamos lá fora cursor
de salientar que a especial

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

319
00:16:59,760 --> 00:17:03,150
Nós continuar fazendo isso ao longo
a palavra inteira, assumindo

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

321
00:17:03,950 --> 00:17:07,220
Isso significa que fomos capazes de passar
toda a palavra e encontrar

322
00:17:07,220 --> 00:17:08,920
um nó na nossa tentativa.

323
00:17:08,920 --> 00:17:10,770
Mas nós não estamos completamente feito ainda.

324
00:17:10,770 --> 00:17:12,290
>> Nós não queremos apenas retornar true.

325
00:17:12,290 --> 00:17:14,770
Queremos voltar cursor> palavra.

326
00:17:14,770 --> 00:17:18,980
Desde lembrar mais uma vez, é o "gato" não é
em nosso dicionário, e "catástrofe"

327
00:17:18,980 --> 00:17:22,935
é, então vamos com sucesso obtemos
através da palavra "gato". Mas cursor

328
00:17:22,935 --> 00:17:25,760
palavra será falso e não é verdade.

329
00:17:25,760 --> 00:17:30,930
Então voltamos palavra cursor para indicar
se este nó é realmente uma palavra.

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

331
00:17:32,470 --> 00:17:34,250
>> Então, vamos verificar o tamanho.

332
00:17:34,250 --> 00:17:37,350
Assim, o tamanho vai ser muito fácil
uma vez que, lembre-se da carga, nós somos

333
00:17:37,350 --> 00:17:41,430
incrementando tamanho do dicionário para
cada palavra que encontramos.

334
00:17:41,430 --> 00:17:45,350
Assim, o tamanho é só ir a
retornar tamanho do dicionário.

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

336
00:17:47,390 --> 00:17:50,590
>> Então, por fim, temos descarregar.

337
00:17:50,590 --> 00:17:55,100
Então, descarregar, vamos usar um
função recursiva para realmente fazer tudo

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

339
00:17:56,530 --> 00:17:59,340
Portanto, a nossa função vai
ser chamado de descarga.

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

341
00:18:01,650 --> 00:18:06,580
Vemos aqui que descarregador vai
iterar sobre todas as crianças em

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

343
00:18:08,410 --> 00:18:11,750
E se o nó filho não é
nulo, então vamos

344
00:18:11,750 --> 00:18:13,730
descarregar o nó filho.

345
00:18:13,730 --> 00:18:18,010
>> Portanto, este é você recursivamente descarregar
todos os nossos filhos.

346
00:18:18,010 --> 00:18:21,080
Uma vez que temos a certeza de que todos os nossos filhos
tenham sido descarregadas, então nós

347
00:18:21,080 --> 00:18:25,210
pode libertar-nos, por isso,
nós descarregar.

348
00:18:25,210 --> 00:18:29,460
Isto irá trabalhar de forma recursiva
descarregar toda a trie.

349
00:18:29,460 --> 00:18:32,850
E, em seguida, uma vez que é feito,
podemos simplesmente retornar true.

350
00:18:32,850 --> 00:18:34,210
Unload não pode falhar.

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

352
00:18:35,710 --> 00:18:38,870
Assim, uma vez que estamos a fazer liberando
tudo, retornar true.

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

354
00:18:40,320 --> 00:18:41,080
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]