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

2
00:00:00,530 --> 00:00:03,070
>> COLUNA 1: Vamos dar
esta solução uma tentativa.

3
00:00:03,070 --> 00:00:07,130
Então, vamos dar uma olhada no que o nosso
Nó Struct será semelhante.

4
00:00:07,130 --> 00:00:11,040
Aqui, vemos que vamos ter um
Bool Word e um nó estrela Struct

5
00:00:11,040 --> 00:00:12,990
Crianças entre parênteses alfabeto.

6
00:00:12,990 --> 00:00:18,720
Então a primeira coisa que você pode estar se perguntando:
por isso é de hash alfabeto definido como 27?

7
00:00:18,720 --> 00:00:22,540
Bem, lembre-se que nós vamos precisar
estar lidando com o apóstrofo, de modo

8
00:00:22,540 --> 00:00:25,610
que vai ser um pouco de um especial
caso ao longo deste programa.

9
00:00:25,610 --> 00:00:28,780
>> OK, agora, lembre-se como um
Trie realmente funciona.

10
00:00:28,780 --> 00:00:33,420
Digamos que estamos indexando a palavra gatos,
em seguida, a partir da raiz do nosso Trie,

11
00:00:33,420 --> 00:00:36,670
vamos olhar para as Crianças
array, e vamos olhar para o

12
00:00:36,670 --> 00:00:42,250
índice que corresponde à letra
C. Para que seria índice dois.

13
00:00:42,250 --> 00:00:46,400
Assim, dado que, que nos dará
um novo nó, e depois vamos

14
00:00:46,400 --> 00:00:47,880
trabalhar a partir desse nó.

15
00:00:47,880 --> 00:00:51,830
>> Assim, dado que nós, que estamos mais uma vez
vai olhar para a matriz Crianças,

16
00:00:51,830 --> 00:00:56,170
e nós estamos indo olhar índice zero
corresponder ao A no gato.

17
00:00:56,170 --> 00:01:01,240
Então nós estamos indo para ir para esse nó,
e dado que nós, vamos

18
00:01:01,240 --> 00:01:05,170
olhar para o índice que corresponde
para T. E passar para esse nó,

19
00:01:05,170 --> 00:01:09,590
finalmente, temos completamente olhou
através do nosso gato palavra, e agora Bool

20
00:01:09,590 --> 00:01:15,020
Palavra deve indicar se
esta palavra dada é na verdade uma palavra.

21
00:01:15,020 --> 00:01:17,530
>> Então, por que precisamos nesse caso especial?

22
00:01:17,530 --> 00:01:21,680
Bem, e se a catástrofe palavra
está no nosso dicionário, mas

23
00:01:21,680 --> 00:01:24,120
a palavra gato não é?

24
00:01:24,120 --> 00:01:29,030
Assim, em olhando para ver se a palavra gato é
em nosso dicionário, vamos

25
00:01:29,030 --> 00:01:34,880
olhar com sucesso através dos índices
C-A-T e chegar a um nó, mas isso é

26
00:01:34,880 --> 00:01:39,760
só porque catástrofe aconteceu
criar nós no caminho de C-A-T todos

27
00:01:39,760 --> 00:01:41,250
o caminho para o fim da palavra.

28
00:01:41,250 --> 00:01:46,520
Então Bool Word é usado indicar se
este local especial, na verdade,

29
00:01:46,520 --> 00:01:48,370
indica uma palavra.

30
00:01:48,370 --> 00:01:52,920
>> Tudo bem, então agora que sabemos o que é um
Trie está indo olhar como, vamos olhar

31
00:01:52,920 --> 00:01:54,800
na função de carga.

32
00:01:54,800 --> 00:01:58,670
Assim carga vai retornar um Bool
para saber se com sucesso ou

33
00:01:58,670 --> 00:02:03,020
dicionário e, sem sucesso, carregado
este vai ser o dicionário

34
00:02:03,020 --> 00:02:04,520
que deseja carregar.

35
00:02:04,520 --> 00:02:08,310
Então a primeira coisa que vamos fazer é abrir
até que dicionário para a leitura.

36
00:02:08,310 --> 00:02:12,060
Temos que ter certeza de que não falhou,
por isso, se o dicionário não foi

37
00:02:12,060 --> 00:02:15,280
aberto com sucesso, ele retornará
Não, nesse caso, vamos

38
00:02:15,280 --> 00:02:16,340
retornar False.

39
00:02:16,340 --> 00:02:21,290
Mas, supondo que com sucesso
abriu, então podemos realmente ler

40
00:02:21,290 --> 00:02:22,310
através do dicionário.

41
00:02:22,310 --> 00:02:24,940
>> Então a primeira coisa que vamos
quero fazer é que temos esta

42
00:02:24,940 --> 00:02:26,560
raiz variável global.

43
00:02:26,560 --> 00:02:30,250
Agora, a raiz vai ser uma estrela nó.

44
00:02:30,250 --> 00:02:33,830
É o topo da nossa Trie que estamos
vai ser iterar.

45
00:02:33,830 --> 00:02:38,200
Então a primeira coisa que vamos querer
fazer é alocar memória para a nossa raiz.

46
00:02:38,200 --> 00:02:42,040
>> Observe que estamos usando a calloc
função, a qual é basicamente a mesma

47
00:02:42,040 --> 00:02:45,560
como a função Malloc, exceto que é
garantido para retornar algo que é

48
00:02:45,560 --> 00:02:47,240
completamente zerado.

49
00:02:47,240 --> 00:02:51,350
Então, se nós usamos Malloc, precisaríamos
passar por todos os ponteiros em nossa

50
00:02:51,350 --> 00:02:54,220
nó e certifique-se de que
eles são todos nulos.

51
00:02:54,220 --> 00:02:56,780
Então calloc vai fazer isso por nós.

52
00:02:56,780 --> 00:03:00,390
>> Agora, assim como Malloc, precisamos fazer
Certifique-se que a alocação é realmente

53
00:03:00,390 --> 00:03:01,580
bem sucedida.

54
00:03:01,580 --> 00:03:04,060
Se este retornou nulo, então nós
precisa fechar nosso dicionário

55
00:03:04,060 --> 00:03:06,170
arquivo e retornar False.

56
00:03:06,170 --> 00:03:11,040
Assim, supondo que a alocação foi
bem sucedida, vamos usar um nó

57
00:03:11,040 --> 00:03:14,340
estrelar Cursor para repetir
através do nosso Trie.

58
00:03:14,340 --> 00:03:17,950
Portanto, a nossa raiz nunca vai mudar,
mas nós vamos usar para Cursor

59
00:03:17,950 --> 00:03:20,770
realmente ir de nó em nó.

60
00:03:20,770 --> 00:03:25,000
>> Tudo bem, então neste loop, estamos
leitura através do arquivo de dicionário,

61
00:03:25,000 --> 00:03:26,965
e nós estamos usando a fgetc.

62
00:03:26,965 --> 00:03:30,360
Então fgetc vai pegar um único
personagem a partir do arquivo.

63
00:03:30,360 --> 00:03:33,430
Nós vamos continuar agarrando
caracteres enquanto não atingem o

64
00:03:33,430 --> 00:03:37,540
final do arquivo, por isso há
dois casos que precisamos lidar.

65
00:03:37,540 --> 00:03:41,640
O primeiro, quando o carácter não era um
nova linha, por isso sabemos se era um novo

66
00:03:41,640 --> 00:03:44,480
linha, então estamos prestes a
passar para uma nova palavra.

67
00:03:44,480 --> 00:03:49,300
Mas supondo que ele não era uma nova linha, em seguida,
aqui, queremos descobrir a

68
00:03:49,300 --> 00:03:52,440
índice vamos índice em
na matriz Crianças que

69
00:03:52,440 --> 00:03:53,890
nós olhamos antes.

70
00:03:53,890 --> 00:03:57,950
>> Então, como eu disse antes, nós precisamos
caso especial o apóstrofo.

71
00:03:57,950 --> 00:04:01,040
Observe que estamos usando o operador ternário
aqui, então vamos ler

72
00:04:01,040 --> 00:04:05,500
isso como se o personagem lemos em foi
um apóstrofo, então vamos

73
00:04:05,500 --> 00:04:11,740
definir índice igual ao alfabeto menos
1, que será o índice de 26.

74
00:04:11,740 --> 00:04:15,190
Outra coisa, se não fosse um apóstrofo,
em seguida, vamos definir o índice

75
00:04:15,190 --> 00:04:17,820
igual a c, menos um.

76
00:04:17,820 --> 00:04:23,090
Então lembre-se de volta a partir de conjuntos p anteriores,
c menos uma vai nos dar o

77
00:04:23,090 --> 00:04:27,470
posição alfabética de c, por isso, se
c é a letra A, esta vontade

78
00:04:27,470 --> 00:04:28,770
dá-nos o índice zero.

79
00:04:28,770 --> 00:04:32,180
Para a letra B, que daria
us o índice 1, e assim por diante.

80
00:04:32,180 --> 00:04:37,070
>> Então, isso nos dá o índice para a
Crianças matriz que nós queremos.

81
00:04:37,070 --> 00:04:42,540
Agora, se esse índice é actualmente nulo na
a matriz Crianças, isso significa que

82
00:04:42,540 --> 00:04:47,470
um nó não existe atualmente de
esse caminho, por isso precisamos de atribuir um

83
00:04:47,470 --> 00:04:49,220
nó para esse caminho.

84
00:04:49,220 --> 00:04:50,610
Isso é o que fazemos aqui.

85
00:04:50,610 --> 00:04:54,650
Então, vamos, mais uma vez, use o calloc
função de modo que não temos

86
00:04:54,650 --> 00:05:00,130
para zerar todos os ponteiros, e nós,
de novo, precisa verificar se calloc

87
00:05:00,130 --> 00:05:01,300
não falhou.

88
00:05:01,300 --> 00:05:04,760
Se calloc deixou, então precisamos
para descarregar tudo, fechar o nosso

89
00:05:04,760 --> 00:05:06,880
dicionário, e retornar False.

90
00:05:06,880 --> 00:05:14,110
>> Assim, supondo que ele não falhou, então
isso irá criar um novo filho para nós,

91
00:05:14,110 --> 00:05:16,000
e, em seguida, iremos para aquela criança.

92
00:05:16,000 --> 00:05:19,030
Nossa cursor irá iterar
para baixo para aquela criança.

93
00:05:19,030 --> 00:05:23,390
Agora, se isso não fosse nulo, para começar,
em seguida, o cursor pode simplesmente iterar

94
00:05:23,390 --> 00:05:26,650
até aquela criança sem realmente
ter de alocar qualquer coisa.

95
00:05:26,650 --> 00:05:30,790
Este é o caso em que aconteceu pela primeira vez
alocar a palavra gato, e

96
00:05:30,790 --> 00:05:34,390
isso significa que quando vamos para alocar
catástrofe, não precisa criar

97
00:05:34,390 --> 00:05:35,720
nós para C-A-T novamente.

98
00:05:35,720 --> 00:05:37,620
Eles já existem.

99
00:05:37,620 --> 00:05:40,140
>> OK, então o que é essa pessoa?

100
00:05:40,140 --> 00:05:44,600
Esta é a condição em que c é
barra invertida n, onde c é uma nova linha.

101
00:05:44,600 --> 00:05:47,780
Isso significa que nós temos com sucesso
completou uma palavra.

102
00:05:47,780 --> 00:05:51,020
Agora, o que nós queremos fazer quando
concluiu com êxito uma palavra?

103
00:05:51,020 --> 00:05:55,250
Vamos usar este campo palavra
dentro do nosso nó Struct.

104
00:05:55,250 --> 00:06:00,570
>> Queremos definir isso como True, de modo que
indica que este nó indica uma

105
00:06:00,570 --> 00:06:03,320
palavra sucesso uma palavra real.

106
00:06:03,320 --> 00:06:05,050
Agora, definir que para True.

107
00:06:05,050 --> 00:06:09,210
Queremos redefinir a nossa cursor para o ponto
para o início do Trie novamente.

108
00:06:09,210 --> 00:06:13,510
E, finalmente, aumentar nosso dicionário
tamanho desde que encontramos outra palavra.

109
00:06:13,510 --> 00:06:16,450
>> Tudo bem, então vamos continuar fazendo
que, lendo em caráter de

110
00:06:16,450 --> 00:06:21,960
personagem, construção de novos nós na
nossa Trie e para cada palavra na

111
00:06:21,960 --> 00:06:26,810
dicionário, até que, finalmente, chegar c
é igual a EOF, caso em que, se quebrar

112
00:06:26,810 --> 00:06:28,100
fora do arquivo.

113
00:06:28,100 --> 00:06:31,110
Agora, há dois casos em
que poderíamos ter atingido EOF.

114
00:06:31,110 --> 00:06:35,680
A primeira é se houve um erro
a leitura do arquivo, por isso, se houve

115
00:06:35,680 --> 00:06:39,280
um erro, o que precisamos fazer o típico
descarregar tudo, fechar o arquivo,

116
00:06:39,280 --> 00:06:40,520
retornar False.

117
00:06:40,520 --> 00:06:43,870
Assumindo que não houve um erro, que
significa apenas que nós realmente bater o fim do

118
00:06:43,870 --> 00:06:47,820
o arquivo, caso em que, vamos fechar o
arquivo e retornar True, uma vez que

119
00:06:47,820 --> 00:06:51,010
carregados com sucesso o dicionário
em nosso Trie.

120
00:06:51,010 --> 00:06:54,240
>> Tudo bem, então agora vamos
confira Cheque.

121
00:06:54,240 --> 00:06:58,780
Olhando para a função de verificação, vemos
Verifique que vai retornar um Bool.

122
00:06:58,780 --> 00:07:03,740
Ele retorna True se esta palavra, que é
sendo passado está em nosso Trie.

123
00:07:03,740 --> 00:07:06,170
Ele retorna false caso contrário.

124
00:07:06,170 --> 00:07:10,110
>> Então, como é que vamos determinar se
esta palavra é em nossa Trie?

125
00:07:10,110 --> 00:07:14,270
Vemos aqui que, como antes,
vamos usar cursor para iterar

126
00:07:14,270 --> 00:07:16,010
através do nosso Trie.

127
00:07:16,010 --> 00:07:20,650
Agora, aqui, nós vamos fazer uma iteração
ao longo de toda a nossa palavra.

128
00:07:20,650 --> 00:07:24,680
Então iteração sobre a palavra que estamos
passou, vamos determinar a

129
00:07:24,680 --> 00:07:29,280
índice para a matriz Crianças que
corresponde à palavra suporte i.

130
00:07:29,280 --> 00:07:34,150
Então, isso vai parecer exatamente como
Carga, onde se suporte palavra i é um

131
00:07:34,150 --> 00:07:38,110
apóstrofo, então nós queremos usar o índice
alfabeto menos 1 por julgarmos

132
00:07:38,110 --> 00:07:41,160
que é para onde estamos indo
para armazenar apóstrofo.

133
00:07:41,160 --> 00:07:44,440
>> Else vamos usar tolower
suporte palavra i.

134
00:07:44,440 --> 00:07:48,270
Então lembre-se que a palavra pode ter arbitrária
capitalização, e por isso

135
00:07:48,270 --> 00:07:51,590
quer ter a certeza que estamos usando
uma versão minúscula das coisas.

136
00:07:51,590 --> 00:07:55,300
E, em seguida, subtrair que minúsculas
ao, mais uma vez, dá-nos a

137
00:07:55,300 --> 00:07:57,940
posição alfabética
desse personagem.

138
00:07:57,940 --> 00:08:01,740
Então isso vai ser o nosso índice
na matriz Crianças.

139
00:08:01,740 --> 00:08:06,480
>> E agora, se esse índice para as Crianças
matriz é nulo, isso significa que

140
00:08:06,480 --> 00:08:09,050
não pode mais continuar a iteração
para baixo a nossa Trie.

141
00:08:09,050 --> 00:08:13,320
Se for esse o caso, esta palavra não pode
possivelmente no nosso Trie, uma vez que se ele

142
00:08:13,320 --> 00:08:18,000
foram, isso significaria que haveria uma
caminho até essa palavra, e se fosse

143
00:08:18,000 --> 00:08:19,350
nunca encontrar nulo.

144
00:08:19,350 --> 00:08:21,910
Assim, encontrando nulo, voltamos False.

145
00:08:21,910 --> 00:08:23,810
A palavra não está no dicionário.

146
00:08:23,810 --> 00:08:28,200
Se não fosse nulo, então vamos
continuar iterando, por isso estamos indo

147
00:08:28,200 --> 00:08:33,150
para atualizar o nosso cursor para apontar para que
determinado nó nesse índice.

148
00:08:33,150 --> 00:08:36,659
>> Então, nós continuar fazendo isso ao longo
a palavra inteira.

149
00:08:36,659 --> 00:08:40,630
Assumindo que nunca bateu nulo, isso significa
fomos capazes de passar por todo o

150
00:08:40,630 --> 00:08:44,840
mundo e encontrar um nó na nossa Trie,
mas não estamos completamente feito ainda.

151
00:08:44,840 --> 00:08:46,350
Nós não queremos apenas retornar True.

152
00:08:46,350 --> 00:08:51,400
Queremos voltar palavra erro cursor
uma vez que, lembre-se, novamente, se gato não é

153
00:08:51,400 --> 00:08:55,140
em nosso dicionário e catástrofe é,
então vamos obter sucesso através de

154
00:08:55,140 --> 00:08:59,810
o gato palavra, mas a palavra cursor
será falso e não é verdade.

155
00:08:59,810 --> 00:09:04,990
Então voltamos palavra cursor para indicar
se este nó é realmente uma palavra,

156
00:09:04,990 --> 00:09:06,530
e é isso por cheque.

157
00:09:06,530 --> 00:09:08,310
>> Então, vamos verificar Size.

158
00:09:08,310 --> 00:09:11,410
Então Tamanho vai ser muito fácil
uma vez que, lembre-se de carga, estamos

159
00:09:11,410 --> 00:09:15,480
incrementando tamanho do dicionário para
cada palavra que encontramos.

160
00:09:15,480 --> 00:09:20,820
Então Tamanho é só ir para retornar
tamanho do dicionário, e é isso.

161
00:09:20,820 --> 00:09:24,650
>> Tudo bem, então, por último, temos Unload.

162
00:09:24,650 --> 00:09:29,050
Então Unload, vamos usar um
função recursiva para realmente fazer tudo

163
00:09:29,050 --> 00:09:33,390
do trabalho por nós, para a nossa função
vai ser chamado Descarregador.

164
00:09:33,390 --> 00:09:35,830
O que está Unloader vai fazer?

165
00:09:35,830 --> 00:09:40,640
Vemos aqui que Unloader vai
iterar sobre todas as crianças em

166
00:09:40,640 --> 00:09:45,810
este nó particular, e se a criança
nó não for nulo, então vamos

167
00:09:45,810 --> 00:09:47,760
descarregar o nó filho.

168
00:09:47,760 --> 00:09:52,070
>> Então, isso vai de forma recursiva
descarregar todas as nossas crianças.

169
00:09:52,070 --> 00:09:55,140
Uma vez que temos a certeza de que todos os nossos filhos
tenham sido descarregadas, então nós

170
00:09:55,140 --> 00:09:58,830
pode libertar-nos, por isso, descarregar a nós mesmos.

171
00:09:58,830 --> 00:10:04,550
Então, isso vai recursivamente descarregar o
todo Trie, e então uma vez que é

172
00:10:04,550 --> 00:10:06,910
feito, podemos simplesmente retornar True.

173
00:10:06,910 --> 00:10:09,770
Unload não pode falhar, estamos
apenas liberando as coisas.

174
00:10:09,770 --> 00:10:12,985
Assim, uma vez que estamos a fazer liberando
tudo, retornar True.

175
00:10:12,985 --> 00:10:14,380
E é isso.

176
00:10:14,380 --> 00:10:16,792
Meu nome é Rob, e este
foi [inaudível].

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