1
00:00:00,000 --> 00:00:11,856

2
00:00:11,856 --> 00:00:13,050
>> ROB BOWDEN: Oi.

3
00:00:13,050 --> 00:00:16,210
Estou Rob, e haxixe Vamos
esta solução para fora.

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

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

6
00:00:24,090 --> 00:00:28,710
Por isso, vai ter uma palavra de char
matriz de comprimento do tamanho 1.

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

8
00:00:32,259 --> 00:00:35,110
caracteres e, em seguida, vamos
precisa de um personagem extra para o

9
00:00:35,110 --> 00:00:37,070
barra invertida 0.

10
00:00:37,070 --> 00:00:40,870
>> E então a nossa tabela hash em cada
balde vai armazenar uma

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

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

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

14
00:00:48,430 --> 00:00:51,110
struct node * seguinte.

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

16
00:00:53,090 --> 00:00:56,180
Agora, aqui é a declaração
da nossa tabela de hash.

17
00:00:56,180 --> 00:01:01,910
Vai ter 16.384 baldes, mas
esse número não importa realmente.

18
00:01:01,910 --> 00:01:05,450
E, finalmente, vamos ter o
hashtable_size variável global, que

19
00:01:05,450 --> 00:01:08,640
vai começar como 0, e é
vai manter o controle de quantas palavras

20
00:01:08,640 --> 00:01:10,080
estavam em nosso dicionário.

21
00:01:10,080 --> 00:01:10,760
Tudo bem.

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

23
00:01:13,190 --> 00:01:16,390
Então, observe que a carga,
ele retorna um bool.

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

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

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

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

28
00:01:27,170 --> 00:01:30,420
Vamos fopen o dicionário para
leitura, e nós vamos ter

29
00:01:30,420 --> 00:01:34,700
ter certeza de que ele conseguiu isso, se
ele retornou NULL, então nós não

30
00:01:34,700 --> 00:01:37,440
abrir com sucesso o dicionário
e precisamos retornar false.

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

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

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

34
00:01:46,210 --> 00:01:47,570
laço que vamos ver.

35
00:01:47,570 --> 00:01:51,780
Portanto, manter looping, e agora nós estamos indo
malloc para um único nó.

36
00:01:51,780 --> 00:01:56,800
E, claro, precisamos de erro de verificação
novamente para se mallocing não teve sucesso

37
00:01:56,800 --> 00:02:00,660
e queremos descarregar qualquer nó que
aconteceu com malloc antes, fechar o

38
00:02:00,660 --> 00:02:02,590
dicionário e retornar false.

39
00:02:02,590 --> 00:02:07,440
>> Mas ignorar que, assumindo que
conseguiu, então nós queremos usar fscanf

40
00:02:07,440 --> 00:02:12,400
para ler uma única palavra do nosso
dicionário para o nosso nó.

41
00:02:12,400 --> 00:02:17,310
Então lembre-se que a palavra de entrada-> é o caractere
tampão palavra de comprimento plus size

42
00:02:17,310 --> 00:02:20,300
que vamos
armazenar a palavra dentro

43
00:02:20,300 --> 00:02:25,280
Então fscanf vai retornar 1, desde
como ele era capaz de ler com sucesso um

44
00:02:25,280 --> 00:02:26,750
palavra do arquivo.

45
00:02:26,750 --> 00:02:31,030
>> Se qualquer um erro acontece ou chegarmos
o fim do arquivo, ele não vai

46
00:02:31,030 --> 00:02:34,950
retornar um caso em que se isso não acontecer
retornar 1, estamos finalmente vai quebrar

47
00:02:34,950 --> 00:02:37,280
fora deste loop while.

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

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

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

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

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

53
00:02:55,610 --> 00:02:59,460
E, na verdade, nós apenas puxou este
de hash função da internet.

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

55
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.

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

57
00:03:12,360 --> 00:03:14,490
índice na tabela de hash.

58
00:03:14,490 --> 00:03:18,530
Observe que estamos modding por num_buckets
portanto, o valor hash retornado

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

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

61
00:03:24,320 --> 00:03:27,855
>> Assim, dado que a função de hash, vamos
hash a palavra que lemos

62
00:03:27,855 --> 00:03:31,700
do dicionário e, em seguida, vamos
usar que tem que inserir o

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

64
00:03:33,750 --> 00:03:38,830
Agora, mistura hashtable é o atual
lista ligada na tabela de hash, e

65
00:03:38,830 --> 00:03:41,410
é muito possível que seja apenas NULL.

66
00:03:41,410 --> 00:03:45,640
Queremos inserir a nossa entrada no
início desta lista ligada, e assim por

67
00:03:45,640 --> 00:03:48,910
vamos ter a nossa entrada atual
apontam para que a tabela hash atualmente

68
00:03:48,910 --> 00:03:54,030
pontos para e, em seguida, vamos para armazenar
na tabela de hash em hash

69
00:03:54,030 --> 00:03:55,350
a entrada atual.

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

71
00:03:59,320 --> 00:04:02,270
lista ligada em que o índice de
na tabela de hash.

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

73
00:04:04,900 --> 00:04:07,800
dicionário e incrementar novamente.

74
00:04:07,800 --> 00:04:13,960
Então, nós continuar fazendo isso até que fscanf
finalmente retorna algo não 1 a

75
00:04:13,960 --> 00:04:18,560
que ponto se lembrar que nós precisamos
entrada gratuita, por isso até aqui, nós malloced um

76
00:04:18,560 --> 00:04:21,329
entrada e tentamos ler algo
a partir do dicionário.

77
00:04:21,329 --> 00:04:24,110
E nós não lido com sucesso
algo do dicionário em que

78
00:04:24,110 --> 00:04:27,440
caso, precisamos de libertar a entrada que nós
nunca realmente colocar em tabela hash

79
00:04:27,440 --> 00:04:29,110
e, finalmente, se quebrar.

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

81
00:04:32,750 --> 00:04:35,840
Foi um erro de leitura do arquivo, ou
fizemos sair porque nós alcançamos

82
00:04:35,840 --> 00:04:37,120
o fim do ficheiro?

83
00:04:37,120 --> 00:04:40,150
Se houve um erro, então nós queremos
return false porque a carga não

84
00:04:40,150 --> 00:04:43,260
sucesso, e, no processo, nós queremos
descarregar todas as palavras que lemos

85
00:04:43,260 --> 00:04:45,670
e feche o arquivo de dicionário.

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

87
00:04:48,740 --> 00:04:51,970
arquivo e, finalmente, retornar true desde
nós carregou com êxito o

88
00:04:51,970 --> 00:04:53,040
dicionário.

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

90
00:04:54,420 --> 00:04:59,020
>> Então agora verificar, dada uma tabela hash carregado,
vai ficar assim.

91
00:04:59,020 --> 00:05:02,690
Portanto, verifique, ele retorna um bool, que
vai indicar se a

92
00:05:02,690 --> 00:05:07,530
passou-in char * palavra, se o
string passada-in está em nosso dicionário.

93
00:05:07,530 --> 00:05:10,530
Então, se é no dicionário, se for
na nossa tabela hash, vamos voltar

94
00:05:10,530 --> 00:05:13,380
verdade, e se não é,
vamos retornar false.

95
00:05:13,380 --> 00:05:17,770
Dada esta palavra passou-in, estamos
vai botar a palavra.

96
00:05:17,770 --> 00:05:22,020
>> Agora, uma coisa importante a reconhecer é
que em carga, sabíamos que todos

97
00:05:22,020 --> 00:05:25,820
as palavras iam ser minúsculas,
mas aqui, não tem tanta certeza.

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

99
00:05:29,510 --> 00:05:32,700
é lowercasing cada personagem
da palavra.

100
00:05:32,700 --> 00:05:37,580
Portanto, independentemente da capitalização de
palavra, a nossa função hash vai

101
00:05:37,580 --> 00:05:42,270
retornar o mesmo índice para qualquer que seja o
capitalização é o que teria

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

103
00:05:45,280 --> 00:05:45,950
Tudo bem.

104
00:05:45,950 --> 00:05:47,410
>> Então, esse é o nosso índice.

105
00:05:47,410 --> 00:05:49,790
É a tabela de hash para essa palavra.

106
00:05:49,790 --> 00:05:52,940
Agora, este loop vai
para mais de uma lista ligada

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

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

109
00:05:59,630 --> 00:06:03,480
Nós vamos continuar enquanto entrada faz
não é igual NULL, e lembre-se que

110
00:06:03,480 --> 00:06:08,350
atualizar o ponteiro na nossa lista ligada
entrada é igual a entrada-> seguinte, assim que tem

111
00:06:08,350 --> 00:06:13,840
nosso ponto de entrada atual para o
item seguinte na lista ligada.

112
00:06:13,840 --> 00:06:14,400
Tudo bem.

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

114
00:06:19,150 --> 00:06:23,780
Não é strcmp porque mais uma vez, nós
querem fazer as coisas caso insensível.

115
00:06:23,780 --> 00:06:28,830
Então, nós usamos strcasecmp comparar a palavra
que foi passado para esta função

116
00:06:28,830 --> 00:06:31,860
contra a palavra que
é nessa entrada.

117
00:06:31,860 --> 00:06:35,570
Se retornar 0, que significa que houve
uma partida, caso em que queremos

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

119
00:06:36,630 --> 00:06:39,590
Encontramos com sucesso a
palavra em nossa tabela de hash.

120
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

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

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

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

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

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

126
00:07:00,220 --> 00:07:01,910
E é isso por cheque.

127
00:07:01,910 --> 00:07:02,540
Tudo bem.

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

129
00:07:04,790 --> 00:07:09,280
Agora, o tamanho vai ser muito simples
lembre-se, uma vez em carga, para cada palavra

130
00:07:09,280 --> 00:07:12,880
descobrimos que incrementado um mundial
hashtable_size variável.

131
00:07:12,880 --> 00:07:15,830
Assim, a função de tamanho é apenas
vai retornar esse mundial

132
00:07:15,830 --> 00:07:18,150
variável, e é isso.

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

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

135
00:07:25,340 --> 00:07:30,440
Aqui, nós estamos loop para todos
baldes de nossa tabela de hash.

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

137
00:07:33,240 --> 00:07:37,490
E para cada lista ligada em nosso de hash
mesa, vamos varrer o

138
00:07:37,490 --> 00:07:41,070
totalidade da lista ligada
liberando cada elemento.

139
00:07:41,070 --> 00:07:46,070
Agora, é preciso ter cuidado, então aqui nós
tem uma variável temporária que é

140
00:07:46,070 --> 00:07:49,740
armazenar o ponteiro para o próximo
elemento na lista encadeada.

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

142
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

143
00:07:55,990 --> 00:07:59,260
e tente acessar o próximo ponteiro
desde uma vez que libertou-se o

144
00:07:59,260 --> 00:08:00,870
memória torna-se inválido.

145
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

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

147
00:08:08,360 --> 00:08:09,590
o próximo elemento.

148
00:08:09,590 --> 00:08:12,770
>> Vamos loop while há elementos
nesta lista encadeada.

149
00:08:12,770 --> 00:08:16,450
Nós vamos fazer isso para todas as listas ligadas em
tabela hash, e uma vez que estamos a fazer

150
00:08:16,450 --> 00:08:20,180
com isso, temos completamente descarregada
tabela hash, e estamos a fazer.

151
00:08:20,180 --> 00:08:24,050
Portanto, é impossível que descarrega para sempre
return false, e quando estiver pronto, nós

152
00:08:24,050 --> 00:08:25,320
basta retornar verdadeiro.

153
00:08:25,320 --> 00:08:27,563