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 haxix Imos
esta solución para fóra.

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

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

6
00:00:24,090 --> 00:00:28,710
Por iso, vai ter unha palabra de char
matriz de lonxitude do tamaño 1.

7
00:00:28,710 --> 00:00:32,259
Non esqueza do 1 desde o máximo
palabra no dicionario é de 45

8
00:00:32,259 --> 00:00:35,110
caracteres e, a continuación, imos
precisa dun personaxe 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ón a nosa táboa hash en cada
balde vai almacenar unha

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

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

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

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

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

16
00:00:53,090 --> 00:00:56,180
Agora, aquí é a declaración
da nosa táboa de hash.

17
00:00:56,180 --> 00:01:01,910
Terá 16.384 baldes, pero
ese número non importa realmente.

18
00:01:01,910 --> 00:01:05,450
E, finalmente, imos ter o
hashtable_size variable global, que

19
00:01:05,450 --> 00:01:08,640
comezará como 0, e é
vai manter o control de cantas palabras

20
00:01:08,640 --> 00:01:10,080
estaban na nosa dicionario.

21
00:01:10,080 --> 00:01:10,760
Todo ben.

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

23
00:01:13,190 --> 00:01:16,390
Entón, teña en conta que a carga,
el retorna un bool.

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

25
00:01:20,530 --> 00:01:23,990
E leva un const char * estrelas
dicionario, o cal é o dicionario

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

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

28
00:01:27,170 --> 00:01:30,420
Imos fopen o dicionario para
lectura, e nós imos ter

29
00:01:30,420 --> 00:01:34,700
estar seguro de que conseguiu iso, se
voltou NULL, entón nós non

30
00:01:34,700 --> 00:01:37,440
abrir correctamente o dicionario
e necesitamos voltar false.

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

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

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

34
00:01:46,210 --> 00:01:47,570
lazo que imos ver.

35
00:01:47,570 --> 00:01:51,780
Polo tanto, manter looping, e agora estamos indo
malloc para un único nodo.

36
00:01:51,780 --> 00:01:56,800
E, por suposto, necesitamos de erro de verificación
de novo para se mallocing non tivo éxito

37
00:01:56,800 --> 00:02:00,660
e queremos descargar calquera nodo que
pasou con malloc antes, pechar o

38
00:02:00,660 --> 00:02:02,590
dicionario e voltar false.

39
00:02:02,590 --> 00:02:07,440
>> Pero ignorar que, asumindo que
conseguiu, entón queremos usar fscanf

40
00:02:07,440 --> 00:02:12,400
para ler unha soa palabra da nosa
dicionario para o noso nodo.

41
00:02:12,400 --> 00:02:17,310
Entón lembre que a palabra de entrada-> é o carácter
tapón palabra de lonxitude plus size

42
00:02:17,310 --> 00:02:20,300
que imos
almacenar a palabra dentro

43
00:02:20,300 --> 00:02:25,280
Entón fscanf vai voltar 1, sempre
como era capaz de ler con éxito un

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

45
00:02:26,750 --> 00:02:31,030
>> Se calquera erro ou chegamos
a fin do ficheiro, non vai

46
00:02:31,030 --> 00:02:34,950
voltar un caso en que se iso non acontecer
voltar 1, estamos finalmente vai romper

47
00:02:34,950 --> 00:02:37,280
fóra deste loop while.

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

49
00:02:42,770 --> 00:02:48,270
entry-> palabra, entón nós estamos indo ao hash
esa palabra usando nosa función hash.

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

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

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

53
00:02:55,610 --> 00:02:59,460
E, de feito, nós só tirou este
de hash función de internet.

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

55
00:03:04,010 --> 00:03:08,960
el está tomando unha cadea como entrada e
retornando un int non asinado como saída.

56
00:03:08,960 --> 00:03:12,360
Entón, iso é todo unha función hash é, é
ten en unha entrada, dálle un

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

58
00:03:14,490 --> 00:03:18,530
Teña en conta que estamos modding por num_buckets
polo tanto, o valor hash retorno

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

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

61
00:03:24,320 --> 00:03:27,855
>> Así, dado que a función de hash, imos
hash a palabra que lemos

62
00:03:27,855 --> 00:03:31,700
do dicionario e logo, imos
usar que ten que introducir o

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

64
00:03:33,750 --> 00:03:38,830
Agora mestura hashtable é o actual
lista ligada na táboa de hash, e

65
00:03:38,830 --> 00:03:41,410
é moi posible que sexa só NULL.

66
00:03:41,410 --> 00:03:45,640
Queremos introducir a nosa entrada no
inicio desta lista ligada, e así por

67
00:03:45,640 --> 00:03:48,910
imos ter a nosa entrada actual
apuntan a que a táboa hash actualmente

68
00:03:48,910 --> 00:03:54,030
puntos para e logo, imos para almacenar
na táboa de hash en hash

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

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

71
00:03:59,320 --> 00:04:02,270
lista ligada no que o índice de
na táboa de hash.

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

73
00:04:04,900 --> 00:04:07,800
dicionario e incrementar de novo.

74
00:04:07,800 --> 00:04:13,960
Entón, nós continuar facendo isto ata que fscanf
finalmente volve algo non 1 a

75
00:04:13,960 --> 00:04:18,560
que punto lembrar que necesitamos
entrada gratuíta, polo que ata aquí, nós malloced un

76
00:04:18,560 --> 00:04:21,329
entrada e tentamos ler algo
desde o dicionario.

77
00:04:21,329 --> 00:04:24,110
E nós non ler correctamente
algo do dicionario en que

78
00:04:24,110 --> 00:04:27,440
caso, necesitamos liberar a entrada que
nunca realmente poñer en táboa hash

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

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

81
00:04:32,750 --> 00:04:35,840
Foi un erro de lectura do ficheiro, ou
fixemos saír porque alcanzamos

82
00:04:35,840 --> 00:04:37,120
a fin do ficheiro?

83
00:04:37,120 --> 00:04:40,150
Se houbo un erro, entón queremos
return false porque a carga non

84
00:04:40,150 --> 00:04:43,260
éxito, e, no proceso, queremos
descargar todas as palabras que lemos

85
00:04:43,260 --> 00:04:45,670
e pecha o arquivo de dicionario.

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

87
00:04:48,740 --> 00:04:51,970
ficheiro e, finalmente, volver true desde
nós cargou con éxito o

88
00:04:51,970 --> 00:04:53,040
dicionario.

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

90
00:04:54,420 --> 00:04:59,020
>> Entón agora comprobar, dada unha táboa hash cargado,
se ve así.

91
00:04:59,020 --> 00:05:02,690
Polo tanto, asegúrese de, el retorna un bool, que
vai indicar a

92
00:05:02,690 --> 00:05:07,530
pasou-in char * palabra, se o
cadea pasada-in está no noso dicionario.

93
00:05:07,530 --> 00:05:10,530
Entón, se é no dicionario, de ser o
na nosa táboa hash, imos voltar

94
00:05:10,530 --> 00:05:13,380
verdade, e se non é,
imos voltar false.

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

96
00:05:17,770 --> 00:05:22,020
>> Agora, unha cousa importante a recoñecer é
que en carga, sabiamos que todo

97
00:05:22,020 --> 00:05:25,820
as palabras ían ser minúsculas,
pero aquí, non ten tanta certeza.

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

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

100
00:05:32,700 --> 00:05:37,580
Polo tanto, con independencia da capitalización de
palabra, a nosa función hash vai

101
00:05:37,580 --> 00:05:42,270
volver o mesmo índice para calquera que sexa o
capitalización é o que

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

103
00:05:45,280 --> 00:05:45,950
Todo ben.

104
00:05:45,950 --> 00:05:47,410
>> Entón, este é o noso índice.

105
00:05:47,410 --> 00:05:49,790
É a táboa de hash para esa palabra.

106
00:05:49,790 --> 00:05:52,940
Agora, este loop vai
a máis dunha lista ligada

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

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

109
00:05:59,630 --> 00:06:03,480
Nós imos seguir mentres entrada fai
non coincide NULL, e recorda que

110
00:06:03,480 --> 00:06:08,350
actualizar o punteiro na nosa lista ligada
entrada é igual a entrada-> seguinte, así que ten

111
00:06:08,350 --> 00:06:13,840
noso punto de entrada actual ao
elemento seguinte da lista ligada.

112
00:06:13,840 --> 00:06:14,400
Todo ben.

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

114
00:06:19,150 --> 00:06:23,780
Non é strcmp porque unha vez máis, nós
queren facer as cousas caso insensible.

115
00:06:23,780 --> 00:06:28,830
Entón, usamos strcasecmp comparar a palabra
que foi pasado para esta función

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

117
00:06:31,860 --> 00:06:35,570
Se voltar 0, que significa que houbo
un partido, caso en que queremos

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

119
00:06:36,630 --> 00:06:39,590
Atopamos con éxito a
palabra na nosa táboa de hash.

120
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

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

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

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

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

125
00:06:55,110 --> 00:07:00,220
retornamos false para indicar que o noso
táboa hash non contiña esta palabra.

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

127
00:07:01,910 --> 00:07:02,540
Todo ben.

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

129
00:07:04,790 --> 00:07:09,280
Agora, o tamaño será moi sinxelo
Teña en conta que, unha vez en carga, para cada palabra

130
00:07:09,280 --> 00:07:12,880
descubrimos que incrementado un mundial
hashtable_size variable.

131
00:07:12,880 --> 00:07:15,830
Así, a función de tamaño é só
Vai voltar ese mundial

132
00:07:15,830 --> 00:07:18,150
variable, e é iso.

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

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

135
00:07:25,340 --> 00:07:30,440
Aquí, nós estamos loop para todos
baldes de nosa táboa de hash.

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

137
00:07:33,240 --> 00:07:37,490
E para cada lista ligada na nosa de hash
mesa, imos 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, hai que ter coidado, entón aquí nós
ten unha variable temporal que se

140
00:07:46,070 --> 00:07:49,740
gardar o punteiro ao seguinte
elemento da lista encadeada.

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

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

143
00:07:55,990 --> 00:07:59,260
e probe acceder o seguinte punteiro
desde xa que liberou-se o

144
00:07:59,260 --> 00:08:00,870
memoria convértese en incorrecto.

145
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

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

147
00:08:08,360 --> 00:08:09,590
o seguinte elemento.

148
00:08:09,590 --> 00:08:12,770
>> Imos loop while hai elementos
nesta lista encadeada.

149
00:08:12,770 --> 00:08:16,450
Nós imos facer isto para todas as listas ligadas en
táboa hash, e xa que estamos a facer

150
00:08:16,450 --> 00:08:20,180
con iso, temos completamente descargada
táboa hash, e estamos a facer.

151
00:08:20,180 --> 00:08:24,050
Polo tanto, é imposible que descarrega para sempre
return false, e cando estea listo, nós

152
00:08:24,050 --> 00:08:25,320
basta voltar certo.

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