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

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

3
00:00:13,050 --> 00:00:16,210
Estoy Rob, y el hash de let
esta solución fuera.

4
00:00:16,210 --> 00:00:20,070
Así que aquí vamos a poner en práctica
una tabla hash general.

5
00:00:20,070 --> 00:00:24,090
Vemos que el nodo de estructura de nuestra hachís
tabla va a tener este aspecto.

6
00:00:24,090 --> 00:00:28,710
Así que va a tener una palabra caracteres
matriz de longitud más del tamaño 1.

7
00:00:28,710 --> 00:00:32,259
No se olvide el 1, ya que la máxima
palabra en el diccionario es 45

8
00:00:32,259 --> 00:00:35,110
caracteres, y luego nos vamos a
necesitará un personaje extra para el

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

10
00:00:37,070 --> 00:00:40,870
>> Y entonces nuestra tabla hash en cada
cubo se va a almacenar un

11
00:00:40,870 --> 00:00:42,320
lista enlazada de nodos.

12
00:00:42,320 --> 00:00:44,420
No estamos haciendo el sondeo lineal aquí.

13
00:00:44,420 --> 00:00:48,430
Y así, con el fin de vincular a la siguiente
elemento en el cubo, necesitamos un

14
00:00:48,430 --> 00:00:51,110
struct nodo * siguiente.

15
00:00:51,110 --> 00:00:53,090
Así que eso es lo que un nodo se parece.

16
00:00:53,090 --> 00:00:56,180
Ahora, aquí es la declaración
de nuestra tabla hash.

17
00:00:56,180 --> 00:01:01,910
Va a tener 16.384 cubos, pero
ese número en realidad no importa.

18
00:01:01,910 --> 00:01:05,450
Y, por último, vamos a tener la
hashtable_size variable global, que

19
00:01:05,450 --> 00:01:08,640
va a empezar como 0, y es
va a realizar un seguimiento de la cantidad de palabras

20
00:01:08,640 --> 00:01:10,080
estaban en nuestro diccionario.

21
00:01:10,080 --> 00:01:10,760
Está bien.

22
00:01:10,760 --> 00:01:13,190
>> Así que echemos un vistazo a la carga.

23
00:01:13,190 --> 00:01:16,390
Así notar que la carga,
devuelve un bool.

24
00:01:16,390 --> 00:01:20,530
Se vuelve verdad si fue con éxito
cargado y false en caso contrario.

25
00:01:20,530 --> 00:01:23,990
Y se necesita un const char * estrellas
diccionario, que es el diccionario

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

27
00:01:25,280 --> 00:01:27,170
Así que eso es lo primero
que vamos a hacer.

28
00:01:27,170 --> 00:01:30,420
Vamos a fopen el diccionario para
lectura, y vamos a tener

29
00:01:30,420 --> 00:01:34,700
para asegurarse de que tuvo éxito por lo que si
se devuelve NULL, entonces no lo hicimos

30
00:01:34,700 --> 00:01:37,440
abrir correctamente el diccionario
y tenemos que devolver false.

31
00:01:37,440 --> 00:01:41,580
>> Pero suponiendo que lo hizo con éxito
abierto, entonces queremos leer la

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

33
00:01:42,400 --> 00:01:46,210
Así seguirá sonando hasta que encontremos alguna
razón para salir de este

34
00:01:46,210 --> 00:01:47,570
bucle que ya veremos.

35
00:01:47,570 --> 00:01:51,780
Así mantenemos bucle, y ahora vamos
a malloc un solo nodo.

36
00:01:51,780 --> 00:01:56,800
Y, por supuesto, tenemos que error de comprobación
de nuevo por lo que si mallocing no tuvo éxito

37
00:01:56,800 --> 00:02:00,660
y queremos descargar cualquier nodo que
pasó a malloc antes, cierre la

38
00:02:00,660 --> 00:02:02,590
diccionario y devolver false.

39
00:02:02,590 --> 00:02:07,440
>> Pero haciendo caso omiso de eso, suponiendo
tenido éxito, entonces queremos usar fscanf

40
00:02:07,440 --> 00:02:12,400
para leer una sola palabra de nuestro
diccionario de a nuestro nodo.

41
00:02:12,400 --> 00:02:17,310
Así que recuerde que la palabra de entrada-> es el carbón de leña
búfer palabra de longitud más tamaño

42
00:02:17,310 --> 00:02:20,300
uno que vamos a
guardar la palabra pulg

43
00:02:20,300 --> 00:02:25,280
Así fscanf va a regresar 1, siempre y
ya que era capaz de leer correctamente un

44
00:02:25,280 --> 00:02:26,750
Palabras del archivo.

45
00:02:26,750 --> 00:02:31,030
>> Si sucede, ya sea un error o se llega
el final del archivo, no lo hará

46
00:02:31,030 --> 00:02:34,950
devuelve 1, en cuyo caso si no lo hace
devuelve 1, finalmente vamos a romper

47
00:02:34,950 --> 00:02:37,280
fuera de este bucle while.

48
00:02:37,280 --> 00:02:42,770
Así que vemos que una vez que tengamos éxito
leer una palabra en

49
00:02:42,770 --> 00:02:48,270
entrada-> palabra, entonces vamos para discutir
esa palabra usando nuestra función hash.

50
00:02:48,270 --> 00:02:49,580
Echemos un vistazo a
la función hash.

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

52
00:02:52,430 --> 00:02:55,610
>> Así que usted realmente no necesita
para entender esto.

53
00:02:55,610 --> 00:02:59,460
Y, de hecho, nos detuvimos este
función hash de la Internet.

54
00:02:59,460 --> 00:03:04,010
La única cosa que hay que reconocer es
que esto toma un char * const palabra,

55
00:03:04,010 --> 00:03:08,960
así que está teniendo una cadena como entrada y
devolver un int sin signo como salida.

56
00:03:08,960 --> 00:03:12,360
Así que eso es todo, una función hash es, ¿es
toma en una entrada, se le da un

57
00:03:12,360 --> 00:03:14,490
índice en la tabla hash.

58
00:03:14,490 --> 00:03:18,530
Nótese que estamos modding por NUM_BUCKETS
por lo que el valor hash devuelto

59
00:03:18,530 --> 00:03:21,730
en realidad es un índice en la tabla hash
y no indexa más allá de la

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

61
00:03:24,320 --> 00:03:27,855
>> Así que teniendo en cuenta que la función hash, vamos
para discutir la palabra que leemos

62
00:03:27,855 --> 00:03:31,700
del diccionario y después vamos
para usar que tiene que insertar el

63
00:03:31,700 --> 00:03:33,750
entrada en la tabla hash.

64
00:03:33,750 --> 00:03:38,830
Ahora, el hash tabla hash es la corriente
lista vinculada en la tabla hash, y

65
00:03:38,830 --> 00:03:41,410
es muy posible que sea simplemente NULL.

66
00:03:41,410 --> 00:03:45,640
Queremos insertar nuestra entrada en el
a partir de esta lista enlazada, y así

67
00:03:45,640 --> 00:03:48,910
vamos a tener nuestra entrada actual
apuntar a lo que la tabla hash actualmente

68
00:03:48,910 --> 00:03:54,030
puntos y luego vamos a almacenar
en la tabla hash en el hash

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

70
00:03:55,350 --> 00:03:59,320
>> Así pues, estas dos líneas se insertan con éxito
la entrada al principio de la

71
00:03:59,320 --> 00:04:02,270
lista enlazada en ese índice
en la tabla hash.

72
00:04:02,270 --> 00:04:04,900
Una vez que hemos terminado con eso, sabemos
que encontramos otra palabra en el

73
00:04:04,900 --> 00:04:07,800
diccionario y que se incrementan de nuevo.

74
00:04:07,800 --> 00:04:13,960
Así que seguimos haciendo eso hasta fscanf
finalmente regresa algo no 1 en

75
00:04:13,960 --> 00:04:18,560
cuyo punto recordar que tenemos que
entrada gratuita, por lo que hasta aquí, nos malloced un

76
00:04:18,560 --> 00:04:21,329
entrada y tratamos de leer algo
del diccionario.

77
00:04:21,329 --> 00:04:24,110
Y no nos leemos con éxito
algo del diccionario en el cual

78
00:04:24,110 --> 00:04:27,440
caso de que necesitemos para liberar la entrada que nos
En realidad nunca puesto en la tabla hash

79
00:04:27,440 --> 00:04:29,110
y finalmente romperse.

80
00:04:29,110 --> 00:04:32,750
>> Una vez que empezamos, tenemos que ver, bueno,
qué nos separamos porque hay

81
00:04:32,750 --> 00:04:35,840
estaba leyendo un error desde el archivo o
qué nos separamos porque llegamos a

82
00:04:35,840 --> 00:04:37,120
el final del archivo?

83
00:04:37,120 --> 00:04:40,150
Si hubo un error, entonces queremos
return false porque la carga no lo hizo

84
00:04:40,150 --> 00:04:43,260
éxito, y en el proceso, queremos
descargar todas las palabras que leemos

85
00:04:43,260 --> 00:04:45,670
en y cierre el archivo de diccionario.

86
00:04:45,670 --> 00:04:48,740
Asumiendo que tuvimos éxito, entonces sólo
todavía tienen que cerrar el diccionario

87
00:04:48,740 --> 00:04:51,970
presentar, y finalmente regresar cierto ya
nos hemos cargado con éxito el

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

89
00:04:53,040 --> 00:04:54,420
Y eso es todo por la carga.

90
00:04:54,420 --> 00:04:59,020
>> Así que ahora comprobar, dada una tabla hash cargado,
que va a tener este aspecto.

91
00:04:59,020 --> 00:05:02,690
A fin de comprobar, devuelve un bool, que
va a indicar si el

92
00:05:02,690 --> 00:05:07,530
pasado como char * palabra, si la
cadena pasada-in es en el diccionario.

93
00:05:07,530 --> 00:05:10,530
Así que si está en el diccionario, si es
en nuestra tabla hash, volveremos

94
00:05:10,530 --> 00:05:13,380
verdad, y si no lo es,
vamos a devolver false.

95
00:05:13,380 --> 00:05:17,770
Dada esta palabra-pasajero en, somos
ir para discutir la palabra.

96
00:05:17,770 --> 00:05:22,020
>> Ahora, una cosa importante a reconocer es
que en la carga, sabíamos que todos

97
00:05:22,020 --> 00:05:25,820
las palabras iban a ser minúsculas,
pero aquí, no estamos tan seguros.

98
00:05:25,820 --> 00:05:29,510
Si echamos un vistazo a nuestra función hash,
nuestra función hash realidad

99
00:05:29,510 --> 00:05:32,700
está en minúscula cada personaje
de la palabra.

100
00:05:32,700 --> 00:05:37,580
Así que, independientemente de la capitalización de
palabra, nuestra función hash se va a

101
00:05:37,580 --> 00:05:42,270
devolver el mismo índice para cualquiera que sea el
capitalización es, ya que tendría

102
00:05:42,270 --> 00:05:45,280
regresado para una completamente en minúsculas
versión de la palabra.

103
00:05:45,280 --> 00:05:45,950
Está bien.

104
00:05:45,950 --> 00:05:47,410
>> Así que ese es nuestro índice.

105
00:05:47,410 --> 00:05:49,790
Es la tabla hash de esta palabra.

106
00:05:49,790 --> 00:05:52,940
Ahora, este bucle se va
a más de la lista enlazada

107
00:05:52,940 --> 00:05:55,000
que era en ese índice.

108
00:05:55,000 --> 00:05:59,630
Así notamos que estamos inicializando entrada
para señalar a ese índice.

109
00:05:59,630 --> 00:06:03,480
Vamos a seguir mientras que la entrada no
no NULL de igualdad, y recordar que

110
00:06:03,480 --> 00:06:08,350
actualizar el puntero en nuestra lista enlazada
entrada es igual a la entrada-> siguiente, por lo que tienen

111
00:06:08,350 --> 00:06:13,840
nuestro punto de entrada actual a la
siguiente elemento de lista enlazada.

112
00:06:13,840 --> 00:06:14,400
Está bien.

113
00:06:14,400 --> 00:06:19,150
>> Así que para cada entrada de la lista enlazada,
vamos a utilizar strcasecmp.

114
00:06:19,150 --> 00:06:23,780
No es strcmp porque una vez más, hemos
querer hacer si las cosas minúsculas.

115
00:06:23,780 --> 00:06:28,830
Así que usamos strcasecmp comparar la palabra
que se hizo pasar a esta función

116
00:06:28,830 --> 00:06:31,860
en contra de la palabra que
es en esta entrada.

117
00:06:31,860 --> 00:06:35,570
Si devuelve 0, que significa que hubo
un partido, en el que caso de que queramos

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

119
00:06:36,630 --> 00:06:39,590
Nos encontramos con éxito el
palabra en nuestra tabla hash.

120
00:06:39,590 --> 00:06:43,040
>> Si no había un partido, entonces estamos
ir a la vuelta de nuevo y mirar el

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

122
00:06:43,990 --> 00:06:47,640
Y continuaremos bucle mientras que hay
son entradas de esta lista enlazada.

123
00:06:47,640 --> 00:06:50,160
¿Qué sucede si rompemos
fuera de este bucle?

124
00:06:50,160 --> 00:06:55,110
Eso significa que no encontramos una entrada que
emparejado esta palabra, en cuyo caso

125
00:06:55,110 --> 00:07:00,220
volvemos false para indicar que nuestra
tabla hash no contiene esta palabra.

126
00:07:00,220 --> 00:07:01,910
Y eso es todo por cheque.

127
00:07:01,910 --> 00:07:02,540
Está bien.

128
00:07:02,540 --> 00:07:04,790
>> Así que echemos un vistazo a tamaño.

129
00:07:04,790 --> 00:07:09,280
Ahora, el tamaño va a ser bastante simple
recordar ya que en la carga, para cada palabra

130
00:07:09,280 --> 00:07:12,880
nos encontramos que incrementa un mundial
hashtable_size variable.

131
00:07:12,880 --> 00:07:15,830
Así la función de tamaño es sólo
va a devolver ese mundial

132
00:07:15,830 --> 00:07:18,150
variables, y eso es todo.

133
00:07:18,150 --> 00:07:22,300
>> Ahora, por fin, tenemos que descargar el
diccionario una vez que todo está hecho.

134
00:07:22,300 --> 00:07:25,340
Entonces, ¿cómo vamos a hacer eso?

135
00:07:25,340 --> 00:07:30,440
Aquí, estamos en bucle sobre todos
cubos de nuestra tabla hash.

136
00:07:30,440 --> 00:07:33,240
Así que hay NUM_BUCKETS cubos.

137
00:07:33,240 --> 00:07:37,490
Y para cada lista enlazada en nuestra hachís
mesa, vamos a lazo sobre el

138
00:07:37,490 --> 00:07:41,070
totalidad de la lista enlazada
la liberación de cada elemento.

139
00:07:41,070 --> 00:07:46,070
Ahora, tenemos que ser cuidadosos, así que aquí estamos
tener una variable temporal que es

140
00:07:46,070 --> 00:07:49,740
almacenar el puntero a la siguiente
elemento de la lista enlazada.

141
00:07:49,740 --> 00:07:52,140
Y luego vamos a la libre
el elemento actual.

142
00:07:52,140 --> 00:07:55,990
>> Tenemos que estar seguros de que hacemos esto desde que
no puede simplemente liberar el elemento actual

143
00:07:55,990 --> 00:07:59,260
y luego tratar de acceder a la siguiente puntero
ya que una vez que liberamos a la

144
00:07:59,260 --> 00:08:00,870
la memoria no es válida.

145
00:08:00,870 --> 00:08:04,990
Así que tenemos que mantener en torno a un puntero a
el siguiente elemento, entonces podemos liberar el

146
00:08:04,990 --> 00:08:08,360
elemento actual, y entonces podemos actualizar
nuestra elemento actual para apuntar a

147
00:08:08,360 --> 00:08:09,590
el siguiente elemento.

148
00:08:09,590 --> 00:08:12,770
>> Vamos bucle while hay elementos
en esta lista enlazada.

149
00:08:12,770 --> 00:08:16,450
Haremos eso en todas las listas vinculadas en
la tabla hash, y una vez que hayamos terminado

150
00:08:16,450 --> 00:08:20,180
con eso, que hemos descargado completamente
la tabla hash, y hemos terminado.

151
00:08:20,180 --> 00:08:24,050
Así que es imposible que se descarga a la vez
return false, y cuando hayamos terminado, nos

152
00:08:24,050 --> 00:08:25,320
simplemente devuelva true.

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