1
00:00:00,000 --> 00:00:02,740
[Powered by Google Translate] [Tutorial - Set Problema 5]

2
00:00:02,740 --> 00:00:04,870
[Zamyla Chan - Harvard University]

3
00:00:04,870 --> 00:00:07,190
[Esta es CS50. - CS50.TV]

4
00:00:07,190 --> 00:00:10,400
>> Está bien. Hola a todos y bienvenidos a Tutorial 5.

5
00:00:10,400 --> 00:00:17,400
>> Pset5 es Errores de ortografía, en el que vamos a hacer un corrector ortográfico.

6
00:00:17,400 --> 00:00:21,030
Correctores ortográficos son extremadamente importantes.

7
00:00:21,030 --> 00:00:23,390
Le ha sucedido esto a usted?

8
00:00:23,390 --> 00:00:27,170
Se trabaja muy, muy acumular en un papel para un choque

9
00:00:27,170 --> 00:00:33,120
y aún así terminar encima de conseguir un brillo muy rade como una D o una = D

10
00:00:33,120 --> 00:00:39,390
y todo porque usted es el paté de hígado alerón en la palabra ballena de ancho.

11
00:00:39,390 --> 00:00:44,710
Sí, revisión tus pimientos es una cuestión de la máxima impotencia.

12
00:00:44,710 --> 00:00:49,140
Este es un problema que afecta a los estudiantes masculinos, viriles.

13
00:00:49,140 --> 00:00:56,260
Una vez me dijeron a mi torturador grado sith que nunca me metería en un buen colega.

14
00:00:56,260 --> 00:01:00,250
Y eso es todo lo que quería, eso es todo lo que cualquier chico quiere a mi edad,

15
00:01:00,250 --> 00:01:04,569
sólo para llegar a un buen colega.

16
00:01:04,569 --> 00:01:12,720
Y no cualquier colega. No. Yo quería ir a un colega de Marfil Legal.

17
00:01:12,720 --> 00:01:18,360
Así que si no me mejora, se ha ido serían mis sueños de ir a Harvard,

18
00:01:18,360 --> 00:01:22,730
Jale, o Prisión - usted sabe, en la prisión, Nueva Jersey.

19
00:01:22,730 --> 00:01:25,170
Así que me compré un corrector ortográfico.

20
00:01:25,170 --> 00:01:29,380
Eso es un fragmento pequeño de una de mis artistas favoritas palabra hablada, Taylor Mali.

21
00:01:29,380 --> 00:01:34,630
De todos modos, como él dice, la importancia de contar con un corrector ortográfico es muy importante.

22
00:01:34,630 --> 00:01:39,440
>> Así que bienvenido a Tutorial 5, en el que vamos a estar hablando de pset5: Errores de ortografía,

23
00:01:39,440 --> 00:01:44,300
en el que vamos a hacer nuestro propio corrector ortográfico.

24
00:01:44,300 --> 00:01:50,880
La caja de herramientas para esta semana, el código de distribución, va a ser importante tener en cuenta

25
00:01:50,880 --> 00:01:54,950
sólo para entender las diferentes funciones que el diccionario se va a tener.

26
00:01:54,950 --> 00:02:01,500
Estamos realmente va a tener archivos múltiples c. Que conforman nuestro conjunto de procesadores.

27
00:02:01,500 --> 00:02:05,420
Y así, mirando a través de los diferentes aspectos, a pesar de que no estamos en realidad edición

28
00:02:05,420 --> 00:02:10,770
uno de los archivos, speller.c, sabiendo cómo funciona con relación a dictionary.c,

29
00:02:10,770 --> 00:02:14,100
que vamos a estar escribiendo, va a ser muy importante.

30
00:02:14,100 --> 00:02:16,970
La especificación pset también contiene una gran cantidad de información útil

31
00:02:16,970 --> 00:02:21,360
en términos de cosas que usted puede asumir, reglas y cosas por el estilo,

32
00:02:21,360 --> 00:02:24,710
así que asegúrese de leer la especificación del conjunto de procesadores con cuidado por las propinas.

33
00:02:24,710 --> 00:02:29,310
Y ante la duda de una regla o algo así, entonces siempre se refieren a la especificación de conjunto de procesadores

34
00:02:29,310 --> 00:02:31,550
o discutir.

35
00:02:31,550 --> 00:02:34,060
Este conjunto de procesadores va a depender en gran medida de los punteros,

36
00:02:34,060 --> 00:02:37,890
por lo que queremos asegurarnos de que entendemos la diferencia entre las estrellas añaden

37
00:02:37,890 --> 00:02:41,680
delante del nombre del puntero y símbolos de unión, la manera de liberarlos, etc

38
00:02:41,680 --> 00:02:47,550
Así que ser un maestro de punteros va a ser muy útil en este conjunto de problemas.

39
00:02:47,550 --> 00:02:50,460
Vamos a mirar en las listas enlazadas un poco más,

40
00:02:50,460 --> 00:02:57,790
donde tenemos elementos que nos llaman nodos que tienen tanto un valor, así como un puntero

41
00:02:57,790 --> 00:03:02,520
al nodo siguiente, y así esencialmente que une los diferentes elementos uno tras otro.

42
00:03:02,520 --> 00:03:07,190
Hay algunas opciones diferentes de implementar el diccionario actual.

43
00:03:07,190 --> 00:03:13,150
Vamos a examinar dos métodos principales, que es tablas hash y luego trata.

44
00:03:13,150 --> 00:03:17,660
En ambos de aquellos, implican algún tipo de concepto de una lista enlazada

45
00:03:17,660 --> 00:03:20,790
donde se han elementos vinculados entre sí.

46
00:03:20,790 --> 00:03:25,640
Así que vamos a revisar cómo usted puede ser capaz de operar en torno a las listas enlazadas,

47
00:03:25,640 --> 00:03:29,680
crear ellos, navegar en términos de la forma de, por ejemplo, insertar un nodo en ella

48
00:03:29,680 --> 00:03:32,760
o libre de todos los nodos.

49
00:03:32,760 --> 00:03:34,740
En cuanto a los nodos de desagüe, eso es muy importante

50
00:03:34,740 --> 00:03:37,700
que cada vez que la memoria malloc, después que lo libere.

51
00:03:37,700 --> 00:03:42,910
Así que queremos asegurarnos de que no va unfreed puntero, que no tenemos las fugas de memoria.

52
00:03:42,910 --> 00:03:48,330
Vamos a introducir una herramienta llamada Valgrind que se ejecuta el programa

53
00:03:48,330 --> 00:03:52,260
y comprueba si toda la memoria asignada es entonces liberado.

54
00:03:52,260 --> 00:03:59,080
Su conjunto de procesadores sólo está completa cuando trabaja y cuando su funcionalidad sea completa,

55
00:03:59,080 --> 00:04:03,990
sino también, Valgrind te dice que no hemos encontrado ninguna pérdidas de memoria.

56
00:04:03,990 --> 00:04:06,690
Por último, para este conjunto de procesadores, lo que realmente quiero hacer hincapié en -

57
00:04:06,690 --> 00:04:11,360
Quiero decir, como de costumbre, yo soy definitivamente partidario de usar la pluma y el papel para los conjuntos de problemas,

58
00:04:11,360 --> 00:04:14,840
pero para esto, creo que la pluma y el papel que va a ser especialmente importante

59
00:04:14,840 --> 00:04:19,000
cuando se quiere estar dibujando flechas a las cosas y entender cómo funcionan las cosas.

60
00:04:19,000 --> 00:04:24,440
Así que sin duda intenta utilizar lápiz y papel para dibujar las cosas antes de que te codificación

61
00:04:24,440 --> 00:04:26,970
porque podría ser un poco desordenado.

62
00:04:26,970 --> 00:04:30,700
>> En primer lugar, vamos a entrar en las listas enlazadas un poco.

63
00:04:30,700 --> 00:04:35,510
Las listas enlazadas consisten de nodos, donde cada nodo tiene un valor asociado con ella,

64
00:04:35,510 --> 00:04:39,810
así como un puntero al siguiente nodo después de ella.

65
00:04:39,810 --> 00:04:43,680
Un par de cosas importantes con las listas enlazadas es que tenemos que recordar

66
00:04:43,680 --> 00:04:48,810
donde nuestro primer nodo es, y luego una vez que sabemos que es el primer nodo,

67
00:04:48,810 --> 00:04:52,990
de esa manera podemos acceder al nodo que los puntos de primer nodo

68
00:04:52,990 --> 00:04:55,850
y luego el uno después de eso y el después de eso.

69
00:04:55,850 --> 00:05:00,340
Y el último elemento de la lista enlazada es puntero ese nodo

70
00:05:00,340 --> 00:05:02,340
siempre va a apuntar a NULL.

71
00:05:02,340 --> 00:05:08,230
Cuando un puntos de nodo a NULL, entonces usted sabe que usted ha llegado al final de la lista,

72
00:05:08,230 --> 00:05:12,320
que ese nodo es el último, que no hay nada después de eso.

73
00:05:12,320 --> 00:05:16,970
Aquí, en este esquema, se ve que las flechas son los punteros,

74
00:05:16,970 --> 00:05:20,290
y la sección azul es donde se almacena el valor,

75
00:05:20,290 --> 00:05:24,420
y luego el cuadro rojo con el puntero es puntero del nodo

76
00:05:24,420 --> 00:05:27,050
apuntando al siguiente nodo después de ella.

77
00:05:27,050 --> 00:05:33,730
Y por lo que veo aquí, el nodo D apuntaría a NULL, ya que es el último elemento de la lista.

78
00:05:33,730 --> 00:05:38,240
>> Vamos a ver cómo podemos definir una estructura para un nodo.

79
00:05:38,240 --> 00:05:40,130
Y ya que queremos tener varios nodos,

80
00:05:40,130 --> 00:05:43,180
esto va a ser un typedef struct

81
00:05:43,180 --> 00:05:46,870
en el que vamos a tener varias instancias diferentes de nodos.

82
00:05:46,870 --> 00:05:50,850
Y así lo definen como un nuevo tipo de datos.

83
00:05:50,850 --> 00:05:53,630
Aquí tenemos un nodo typedef struct.

84
00:05:53,630 --> 00:05:56,160
En este ejemplo, estamos tratando con nodos enteros,

85
00:05:56,160 --> 00:06:00,490
por lo que tenemos un valor entero llamado y luego tenemos otro puntero,

86
00:06:00,490 --> 00:06:07,390
y en este caso, es un puntero a un nodo, por lo que tiene un nodo de estructura * llamada siguiente.

87
00:06:07,390 --> 00:06:09,520
Y entonces estamos llamando a este nodo todo.

88
00:06:09,520 --> 00:06:11,110
Asegúrese de que usted siga esta sintaxis.

89
00:06:11,110 --> 00:06:17,940
Observe que el nodo se hace referencia en realidad por encima como por debajo de las llaves.

90
00:06:17,940 --> 00:06:23,400
A continuación, hacer un seguimiento de dónde está mi primer nodo está en esta lista enlazada,

91
00:06:23,400 --> 00:06:29,390
entonces tiene un puntero nodo llamado cabeza, y el espacio malloc suficiente para el tamaño de un nodo.

92
00:06:29,390 --> 00:06:36,240
Nótese, sin embargo, que la cabeza es en realidad un puntero nodo en lugar de un nodo en sí.

93
00:06:36,240 --> 00:06:40,130
Así la cabeza en realidad no contiene ningún valor,

94
00:06:40,130 --> 00:06:45,590
sólo apunta a lo que el primer nodo en mi lista enlazada es.

95
00:06:55,080 --> 00:06:58,340
>> Para tener una mejor idea de las listas enlazadas, porque es muy importante

96
00:06:58,340 --> 00:07:02,220
para realizar un seguimiento de asegurar el mantenimiento de la cadena,

97
00:07:02,220 --> 00:07:09,990
Me gusta pensar en ello como la gente en una línea de la mano,

98
00:07:09,990 --> 00:07:14,330
donde cada persona está de la mano con la siguiente.

99
00:07:14,330 --> 00:07:18,350
No se puede ver en este dibujo, pero en el fondo están apuntando a la siguiente persona

100
00:07:18,350 --> 00:07:23,760
que es en su cadena.

101
00:07:23,760 --> 00:07:29,270
Así que si usted desea recorrer una lista enlazada donde estas personas -

102
00:07:29,270 --> 00:07:32,830
imaginar todas esas personas tienen valores asociados a ellas

103
00:07:32,830 --> 00:07:36,590
y también apuntar a la siguiente persona en la línea -

104
00:07:36,590 --> 00:07:40,810
si usted desea recorrer la lista vinculada, por ejemplo, para editar los valores por

105
00:07:40,810 --> 00:07:42,830
o buscar un valor o algo así,

106
00:07:42,830 --> 00:07:48,270
entonces usted querrá tener un puntero a la persona en concreto.

107
00:07:48,270 --> 00:07:52,670
Así que vamos a tener un tipo de datos de puntero de nodo.

108
00:07:52,670 --> 00:07:55,580
Para este ejemplo, vamos a llamarlo cursor.

109
00:07:55,580 --> 00:07:59,630
Otra forma común de nombrar esto sería iterador o algo por el estilo

110
00:07:59,630 --> 00:08:05,130
porque es iterar sobre y en realidad mueve el nodo que se está señalando.

111
00:08:05,130 --> 00:08:14,410
Esto aquí será nuestro cursor.

112
00:08:14,410 --> 00:08:20,180
Nuestro primer cursor apuntará al primer elemento de la lista.

113
00:08:20,180 --> 00:08:26,910
Así que lo que quiero hacer es que básicamente se sigue el cursor,

114
00:08:26,910 --> 00:08:29,130
moviéndolo de lado a lado.

115
00:08:29,130 --> 00:08:33,409
En este caso, queremos pasar a la siguiente elemento de la lista.

116
00:08:33,409 --> 00:08:38,480
Con los arreglos, lo que nosotros hacemos es simplemente diría que aumentar el índice 1.

117
00:08:38,480 --> 00:08:46,020
En este caso, lo que tenemos que hacer es encontrar realmente que esta persona persona corriente que hace referencia,

118
00:08:46,020 --> 00:08:48,930
y que va a ser el siguiente valor.

119
00:08:48,930 --> 00:08:53,230
Así que si el cursor es un puntero de nodo, entonces lo que quiero hacer

120
00:08:53,230 --> 00:08:56,320
es que queremos llegar al valor que el cursor está apuntando.

121
00:08:56,320 --> 00:09:01,350
Queremos llegar a ese nodo y, a continuación, una vez que estamos en ese nodo, encontrar dónde está apuntando.

122
00:09:01,350 --> 00:09:05,820
Para llegar al nodo actual que el cursor está apuntando,

123
00:09:05,820 --> 00:09:13,160
por lo general nos indican por (cursor *).

124
00:09:13,160 --> 00:09:19,160
Eso le daría el nodo actual que el cursor está apuntando.

125
00:09:19,160 --> 00:09:21,730
Y después de eso, lo que queremos hacer es que queremos acceder

126
00:09:21,730 --> 00:09:25,680
lo que el siguiente valor de nodo es.

127
00:09:25,680 --> 00:09:32,820
Para ello, para acceder a los valores dentro de la estructura, tenemos el operador punto.

128
00:09:32,820 --> 00:09:39,530
Entonces sería (cursor *). Siguiente.

129
00:09:39,530 --> 00:09:44,840
Pero esto es un poco complicado en términos de tener los corchetes alrededor del cursor *,

130
00:09:44,840 --> 00:09:56,800
por lo que reemplazar esta declaración con toda cursor->.

131
00:09:56,800 --> 00:10:02,700
Este es un guión y luego una señal mayor que, por lo que hacer una flecha.

132
00:10:02,700 --> 00:10:05,840
cursor-> siguiente.

133
00:10:05,840 --> 00:10:12,390
Que en realidad le conseguirá el nodo que el cursor apunte a. Ese valor es de siguiente.

134
00:10:12,390 --> 00:10:16,790
Así que en lugar de tener la estrella y el punto, usted está reemplazando que con una flecha.

135
00:10:16,790 --> 00:10:24,820
Tenga mucho cuidado para asegurarse de que intenta utilizar esta sintaxis.

136
00:10:33,550 --> 00:10:37,620
>> Ahora que tenemos nuestro cursor, si queremos acceder al valor,

137
00:10:37,620 --> 00:10:40,450
antes, teníamos cursor-> siguiente,

138
00:10:40,450 --> 00:10:46,260
pero para acceder al valor en el nodo que el cursor hace referencia, que simplemente decir

139
00:10:46,260 --> 00:10:48,070
nodo-> valor.

140
00:10:48,070 --> 00:10:53,600
A partir de ahí, es del tipo de datos lo que hemos definido los valores y los nodos a ser.

141
00:10:53,600 --> 00:10:59,620
Si se trata de un nodo int, entonces cursor-> valor es sólo va a ser un número entero.

142
00:10:59,620 --> 00:11:04,870
Así que podemos hacer operaciones en eso, comprobar igualdades, asignarle valores diferentes, etc

143
00:11:04,870 --> 00:11:11,090
Así que lo que quiere hacer si desea mover el cursor a la siguiente persona,

144
00:11:11,090 --> 00:11:15,270
realmente cambiar el valor del cursor.

145
00:11:15,270 --> 00:11:19,340
Desde cursor es un puntero nodo, se cambia la dirección del puntero actual

146
00:11:19,340 --> 00:11:23,890
a la dirección del nodo siguiente en su lista.

147
00:11:23,890 --> 00:11:28,930
Esto es sólo parte del código donde se puede iterar.

148
00:11:28,930 --> 00:11:31,230
Donde tengo el comentario de hacer algo,

149
00:11:31,230 --> 00:11:33,850
ahí es donde usted está probablemente va a tener acceso al valor

150
00:11:33,850 --> 00:11:37,850
o hacer algo que ver con ese nodo específico.

151
00:11:37,850 --> 00:11:43,050
Para empezar, tengo que decir que mi cursor al principio

152
00:11:43,050 --> 00:11:48,430
se va a apuntar al primer elemento en la lista enlazada.

153
00:11:48,430 --> 00:11:52,910
Y más adelante, lo define como la cabeza del nodo.

154
00:11:52,910 --> 00:11:57,610
>> Como mencioné antes, la liberación es muy importante.

155
00:11:57,610 --> 00:12:02,440
Usted quiere asegurarse de que liberar a todos los elementos de la lista una vez que haya terminado con él.

156
00:12:02,440 --> 00:12:04,940
Cuando no es necesario hacer referencia a cualquiera de los punteros más,

157
00:12:04,940 --> 00:12:10,620
usted quiere asegurarse de que liberar a todos los punteros.

158
00:12:10,620 --> 00:12:14,460
Pero quiero ser muy cuidadosos en este punto en que se quiere evitar cualquier fuga de memoria.

159
00:12:14,460 --> 00:12:25,080
Si una persona antes de tiempo libre, entonces todos los punteros que para que los puntos de unión

160
00:12:25,080 --> 00:12:26,900
van a perder.

161
00:12:26,900 --> 00:12:32,070
Volviendo al ejemplo de persona para que sea un poco más altas estacas,

162
00:12:32,070 --> 00:12:49,600
vamos a tener a esta gente, sólo que en este caso se cierne sobre un lago con un monstruo.

163
00:12:49,600 --> 00:12:53,200
Queremos asegurarnos de que cada vez que liberarse, no perdemos

164
00:12:53,200 --> 00:12:58,920
y dejar de lado los nodos antes de que hayamos hecho los liberó.

165
00:12:58,920 --> 00:13:05,730
Por ejemplo, si usted fuera a llamar simplemente gratuitamente en este tipo aquí,

166
00:13:05,730 --> 00:13:15,350
entonces sería liberado, pero luego todos estos chicos luego se perdería

167
00:13:15,350 --> 00:13:18,450
y ellos quedarse dormido y caerse.

168
00:13:18,450 --> 00:13:24,900
Así que queremos asegurarnos de que por el contrario, queremos mantener un vínculo con el resto.

169
00:13:37,630 --> 00:13:42,480
Nuestra cabeza puntero, que apunta al primer elemento de la lista.

170
00:13:42,480 --> 00:13:49,990
Es algo así como una cuerda de anclaje en la primera persona.

171
00:13:52,870 --> 00:13:57,470
Lo que usted puede ser que desee hacer cuando se libera un lista se tiene -

172
00:13:57,470 --> 00:14:04,520
Si desea liberar el primer elemento en primer lugar, entonces usted puede tener un puntero temporal

173
00:14:04,520 --> 00:14:07,370
que apunta a lo que el primer elemento es.

174
00:14:07,370 --> 00:14:11,420
Así que tienes el puntero temporal señalando aquí.

175
00:14:11,420 --> 00:14:15,840
De esta manera, tenemos un asimiento del primer nodo.

176
00:14:15,840 --> 00:14:18,930
Y entonces, ya sabemos que el primer nodo va a ser liberado,

177
00:14:18,930 --> 00:14:24,890
entonces podemos mover la cuerda, esta ancla, nuestra cabeza,

178
00:14:24,890 --> 00:14:31,930
señalar realmente a cualquiera que sea el primero está apuntando.

179
00:14:31,930 --> 00:14:38,760
Así que esta cabeza en realidad apunta al segundo elemento ahora.

180
00:14:38,760 --> 00:14:43,980
Ahora se nos permite liberar todo lo que se almacena en temp,

181
00:14:43,980 --> 00:14:53,360
y para que podamos borrar sin que ello ponga en peligro a todos los demás nodos de la lista.

182
00:14:54,140 --> 00:15:05,020
Otra forma en que usted puede hacer esto podría ser

183
00:15:05,020 --> 00:15:08,650
cada vez que se acaba de liberar el último elemento de la lista

184
00:15:08,650 --> 00:15:11,010
porque se garantiza que no se refirió a ninguna parte.

185
00:15:11,010 --> 00:15:15,570
Por lo que sólo podría liberar este, entonces sin éste, entonces libre de éste.

186
00:15:15,570 --> 00:15:21,900
Eso definitivamente funciona, pero es un poco más lento porque por la naturaleza de las listas enlazadas,

187
00:15:21,900 --> 00:15:24,670
no podemos saltar inmediatamente a la última.

188
00:15:24,670 --> 00:15:28,030
Tenemos que atraviesan cada elemento de la lista enlazada

189
00:15:28,030 --> 00:15:31,020
y comprobar si aquél está apuntando a NULL, comprobar cada vez,

190
00:15:31,020 --> 00:15:33,780
y luego una vez que llegamos a la final, entonces sin eso.

191
00:15:33,780 --> 00:15:40,270
Si se va a realizar este proceso, que en realidad sería el registro aquí,

192
00:15:40,270 --> 00:15:44,190
comprobar aquí, a continuación, comprobar aquí, liberándola,

193
00:15:44,190 --> 00:15:47,470
luego volver, comprobando aquí, revisando aquí, liberándola,

194
00:15:47,470 --> 00:15:49,660
comprobando aquí, y luego liberar.

195
00:15:49,660 --> 00:15:52,880
Para eso se necesita algo más de tiempo. Si.

196
00:15:52,880 --> 00:15:59,060
>> [Estudiante] ¿Sería posible hacer una lista enlazada que almacena un puntero de salida hasta el final?

197
00:15:59,060 --> 00:16:01,320
Que sin duda sería posible.

198
00:16:01,320 --> 00:16:08,340
Para repetir la pregunta, es posible tener una estructura de lista enlazada

199
00:16:08,340 --> 00:16:12,490
de tal manera que tiene un puntero que señala el final de la lista enlazada?

200
00:16:12,490 --> 00:16:18,090
Yo diría que eso es posible, y cada vez que se inserta algo en tu lista enlazada

201
00:16:18,090 --> 00:16:21,470
usted tendría que actualizar ese puntero y cosas por el estilo.

202
00:16:21,470 --> 00:16:26,640
Usted tendría una cola * nodo, por ejemplo.

203
00:16:26,640 --> 00:16:29,840
Pero cuando estás implementar esta característica, usted tiene que pensar en las ventajas y desventajas,

204
00:16:29,840 --> 00:16:32,700
como cuántas veces voy a estar interactuando sobre esto,

205
00:16:32,700 --> 00:16:36,100
lo difícil es que va a ser para realizar un seguimiento de la cola y la cabeza del

206
00:16:36,100 --> 00:16:38,400
así como mi iterador, y cosas por el estilo.

207
00:16:40,730 --> 00:16:42,480
¿Eso - >> [Estudiante] Yeah.

208
00:16:42,480 --> 00:16:48,270
Es posible, pero en términos de decisiones de diseño, usted tiene que sopesar las opciones.

209
00:16:53,850 --> 00:17:01,090
>> Aquí hay un esqueleto de código que le permitirá liberar a todos los elementos de una lista enlazada.

210
00:17:01,090 --> 00:17:05,460
Una vez más, ya que estoy iterar sobre una lista enlazada, voy a querer tener algún tipo de cursor

211
00:17:05,460 --> 00:17:08,670
o iterador.

212
00:17:08,670 --> 00:17:14,640
Estamos iterando hasta que el cursor es NULL.

213
00:17:14,640 --> 00:17:17,640
No quiero repetir cuando el cursor es NULL

214
00:17:17,640 --> 00:17:20,579
porque eso significa que no hay nada en la lista.

215
00:17:20,579 --> 00:17:25,069
Así que aquí hago un nodo temporal *

216
00:17:25,069 --> 00:17:29,610
apuntando a lo que estoy considerando es el primero de mi lista,

217
00:17:29,610 --> 00:17:35,340
y luego muevo mi cursor delante 1 y luego libre todo lo que yo tenía en el almacenamiento temporal.

218
00:17:38,460 --> 00:17:43,650
>> Ahora llegamos a la inserción en listas enlazadas.

219
00:18:00,200 --> 00:18:09,660
Tengo tres nodos en mi lista enlazada, y vamos a ir con el caso simple

220
00:18:09,660 --> 00:18:18,970
donde queremos insertar un nodo al final de nuestra lista enlazada.

221
00:18:18,970 --> 00:18:25,980
Para ello, lo único que haría es que atravesaría

222
00:18:25,980 --> 00:18:32,100
para encontrar dónde está el final actual de la lista enlazada es, por lo que cualquier nodo apunta a NULL -

223
00:18:32,100 --> 00:18:33,850
que es éste -

224
00:18:33,850 --> 00:18:37,260
y luego decir, en realidad, éste no va a ser el último nodo;

225
00:18:37,260 --> 00:18:39,830
hecho vamos a tener otro.

226
00:18:39,830 --> 00:18:46,260
Así que tendría esta corriente un punto a lo que estamos insertando.

227
00:18:46,260 --> 00:18:50,080
Así que ahora esta persona rojo se convierte aquí en el último nodo en la lista enlazada.

228
00:18:50,080 --> 00:18:56,080
Y así, la característica del último nodo de la lista enlazada es que apunta a NULL.

229
00:18:56,080 --> 00:19:09,380
Así que lo que tendríamos que hacer es establecer el puntero de este tipo de rojo a NULL. Ya está.

230
00:19:09,380 --> 00:19:25,370
>> Pero lo que si queremos insertar un nodo entre la segunda y la tercera?

231
00:19:25,370 --> 00:19:28,960
Que uno no es tan sencillo, porque queremos asegurarnos

232
00:19:28,960 --> 00:19:34,290
que no dejamos de lado cualquier nodo de la lista ligada.

233
00:19:34,290 --> 00:19:43,450
Lo que tendría que hacer es asegurarse de que nos ancla a cada uno.

234
00:19:43,450 --> 00:19:49,900
Por ejemplo, vamos a llamar a este el segundo.

235
00:19:49,900 --> 00:19:54,390
Si usted dijo que el segundo apunta ahora a esta nueva

236
00:19:54,390 --> 00:20:02,520
y que acaba de hacer un puntero ahí, pues, que daría lugar a un tipo que se pierdan

237
00:20:02,520 --> 00:20:07,830
porque no hay ningún vínculo con él.

238
00:20:07,830 --> 00:20:18,970
En su lugar - Voy a llamar de nuevo. Perdona mis habilidades artísticas.

239
00:20:18,970 --> 00:20:26,570
Sabemos que no podemos conectar directamente 2 a la nueva.

240
00:20:26,570 --> 00:20:30,480
Tenemos que asegurarnos de que nos aferramos a la última.

241
00:20:30,480 --> 00:20:39,200
Lo que puede ser que desee hacer es tener un puntero temporal

242
00:20:39,200 --> 00:20:42,650
para el elemento que va a ser añadido en.

243
00:20:42,650 --> 00:20:45,140
Así que tenemos un puntero temporal allí.

244
00:20:45,140 --> 00:20:50,780
Como sabemos que esta tercera se mantiene un seguimiento de,

245
00:20:50,780 --> 00:20:53,680
2 ahora se puede vincular a nuestro uno nuevo.

246
00:20:53,680 --> 00:20:57,490
Y si este nuevo tipo rojo va a ser entre 2 y 3,

247
00:20:57,490 --> 00:21:05,550
entonces lo que se puntero de ese tipo va a señalar? >> [Estudiante] Temp.

248
00:21:05,550 --> 00:21:07,490
Temperatura Si.

249
00:21:07,490 --> 00:21:15,430
Así que el siguiente valor a este tipo de rojo va a ser temporal.

250
00:21:26,090 --> 00:21:33,010
Cuando usted está insertando en las listas enlazadas, vimos que podíamos

251
00:21:33,010 --> 00:21:38,260
fácilmente añadir algo al final mediante la creación de una matriz temporal,

252
00:21:38,260 --> 00:21:42,850
o si quería añadir algo en el medio de nuestra matriz,

253
00:21:42,850 --> 00:21:46,810
entonces se necesitaría un poco más arrastrando los pies alrededor.

254
00:21:46,810 --> 00:21:50,240
Si lo desea, por ejemplo, tienen una lista ordenada vinculado,

255
00:21:50,240 --> 00:21:54,880
entonces usted tiene que tipo de sopesar los costos y beneficios de esa

256
00:21:54,880 --> 00:21:59,720
porque si usted quiere tener un arreglo ordenado, lo que significa que cada vez que se inserta en ella,

257
00:21:59,720 --> 00:22:01,630
que va a tomar un poco más tiempo.

258
00:22:01,630 --> 00:22:05,500
Sin embargo, si desea más adelante, ya que encontraremos vamos a querer,

259
00:22:05,500 --> 00:22:10,280
búsqueda a través de una lista enlazada, entonces podría ser más fácil si usted sabe que todo está en orden.

260
00:22:10,280 --> 00:22:15,340
Así que es posible que desee considerar los costos y beneficios de eso.

261
00:22:20,150 --> 00:22:27,740
>> Otra manera de insertar en una lista enlazada es para insertar en el principio de una lista.

262
00:22:27,740 --> 00:22:34,700
Si dibujamos el ancla aquí - esta es nuestra cabeza -

263
00:22:34,700 --> 00:22:40,960
y luego tener estas personas vinculadas a la misma,

264
00:22:40,960 --> 00:22:48,460
y entonces tenemos un nuevo nodo a ser insertado en el inicio,

265
00:22:48,460 --> 00:22:52,590
entonces lo que queremos hacer?

266
00:22:55,220 --> 00:23:03,580
¿Qué tendría de malo diciendo que desea vincular el rojo al azul,

267
00:23:03,580 --> 00:23:05,790
porque esa es la primera?

268
00:23:05,790 --> 00:23:08,570
¿Qué pasaría aquí?

269
00:23:08,570 --> 00:23:12,130
Todos estos tres se pierden.

270
00:23:12,130 --> 00:23:14,140
Así que no quiero hacer eso.

271
00:23:14,140 --> 00:23:21,430
Una vez más, hemos aprendido que tenemos que tener algún tipo de puntero temporal.

272
00:23:21,430 --> 00:23:34,470
Vamos a optar por tener un punto temporal a este tipo.

273
00:23:34,470 --> 00:23:39,640
Entonces podemos tener la nada un punto al temporal

274
00:23:39,640 --> 00:23:43,240
y luego el punto rojo al azul.

275
00:23:43,240 --> 00:23:47,830
La razón por la que estoy usando a la gente aquí es porque realmente quiere visualizar

276
00:23:47,830 --> 00:23:53,180
aferrándose a la gente y asegurarse de que tenemos un link a las mismas

277
00:23:53,180 --> 00:23:57,590
antes de soltar otra mano o algo así.

278
00:24:05,630 --> 00:24:10,650
>> Ahora que tenemos una idea de las listas enlazadas - cómo podríamos crear una lista enlazada

279
00:24:10,650 --> 00:24:15,090
y crear las estructuras para que consta de la definición de tipo de un nodo

280
00:24:15,090 --> 00:24:19,060
y luego asegurarse de que tenemos un puntero a la cabeza de esa lista enlazada -

281
00:24:19,060 --> 00:24:23,210
una vez que tengamos eso y sabemos cómo recorrer a través de una matriz,

282
00:24:23,210 --> 00:24:28,200
acceder a los diferentes elementos, sabemos cómo insertar y sabemos cómo liberarlos,

283
00:24:28,200 --> 00:24:30,260
entonces podemos entrar en faltas de ortografía.

284
00:24:30,260 --> 00:24:38,150
Como es habitual, tenemos una sección de preguntas que se utilizó para operar con listas enlazadas

285
00:24:38,150 --> 00:24:41,750
y diferentes estructuras como colas y pilas.

286
00:24:41,750 --> 00:24:46,000
Entonces podemos pasar a errores ortográficos.

287
00:24:46,000 --> 00:24:55,170
>> Errores de ortografía tiene en el código de distribución de un par de archivos de importancia.

288
00:24:55,170 --> 00:24:58,850
En primer lugar nos damos cuenta de que tenemos este Makefile aquí,

289
00:24:58,850 --> 00:25:03,040
que en realidad no hemos visto antes.

290
00:25:03,040 --> 00:25:10,090
Si se miraba en el interior de la carpeta pset5, te darías cuenta de que tiene un archivo. H,

291
00:25:10,090 --> 00:25:12,530
entonces tienes dos archivos. c.

292
00:25:12,530 --> 00:25:18,920
Lo que esto hace es Makefile antes, sólo tendría que escribir y hacer luego el nombre del programa

293
00:25:18,920 --> 00:25:25,550
y entonces veríamos todos estos argumentos y banderas pasado en el compilador.

294
00:25:25,550 --> 00:25:30,580
Lo que el Makefile que hace es que nos permite compilar varios archivos a la vez

295
00:25:30,580 --> 00:25:34,650
y pasar las banderas que queremos.

296
00:25:34,650 --> 00:25:41,300
Aquí sólo ver que hay un archivo de cabecera aquí.

297
00:25:41,300 --> 00:25:43,730
Entonces en realidad tenemos dos archivos de código fuente.

298
00:25:43,730 --> 00:25:47,520
Tenemos speller.c y dictionary.c.

299
00:25:47,520 --> 00:25:54,560
Le invitamos a editar el Makefile si lo desea.

300
00:25:54,560 --> 00:26:03,310
Tenga en cuenta que aquí si escribe limpia, entonces lo que hace es en realidad elimina cualquier cosa

301
00:26:03,310 --> 00:26:06,340
que es el núcleo.

302
00:26:06,340 --> 00:26:09,190
Si tienes un error de segmentación, básicamente se obtiene un volcado de memoria.

303
00:26:09,190 --> 00:26:13,260
Así que este pequeño archivo feo aparecerá en el directorio llamado núcleo.

304
00:26:13,260 --> 00:26:16,310
Usted querrá quitar eso para hacer la limpieza.

305
00:26:16,310 --> 00:26:20,940
Elimina todos los archivos exe y. Archivos o.

306
00:26:27,900 --> 00:26:30,220
>> Vamos a echar un vistazo a dictionary.h.

307
00:26:30,220 --> 00:26:34,410
Esto dice que se declara la funcionalidad de un diccionario.

308
00:26:34,410 --> 00:26:39,530
Contamos con una longitud máxima de cualquier palabra en el diccionario.

309
00:26:39,530 --> 00:26:45,130
Decimos que esto va a ser la palabra más larga posible. Es de longitud 45.

310
00:26:45,130 --> 00:26:48,900
Así que no vamos a tener ninguna palabra que exceden esa longitud.

311
00:26:48,900 --> 00:26:50,980
Aquí sólo tenemos los prototipos de funciones.

312
00:26:50,980 --> 00:26:55,290
No tenemos la aplicación real porque eso es lo que vamos a hacer en este conjunto de procesadores.

313
00:26:55,290 --> 00:26:59,940
Pero lo que hace esto es debido a que estamos tratando con archivos más grandes aquí

314
00:26:59,940 --> 00:27:06,650
y funcionalidad en una escala más grande, es útil disponer de un archivo. h

315
00:27:06,650 --> 00:27:11,290
para que otra persona la lectura o el uso de su código puede entender lo que está pasando.

316
00:27:11,290 --> 00:27:17,910
Y tal vez desee implementar intenta si lo hizo tablas hash o viceversa.

317
00:27:17,910 --> 00:27:21,850
Entonces diría que mi función de carga,

318
00:27:21,850 --> 00:27:26,950
la aplicación real que se va a diferir, pero este prototipo no va a cambiar.

319
00:27:26,950 --> 00:27:33,280
Aquí hemos comprobar, que devuelve verdadero si una palabra dada está en el diccionario.

320
00:27:33,280 --> 00:27:39,800
Entonces tenemos carga, que, básicamente, tiene en un archivo de diccionario

321
00:27:39,800 --> 00:27:44,360
y luego se carga en alguna estructura de datos.

322
00:27:44,360 --> 00:27:47,500
Tenemos tamaño, que, cuando es llamada, devuelve el tamaño de su diccionario,

323
00:27:47,500 --> 00:27:50,310
cuántas palabras se almacenan en el mismo,

324
00:27:50,310 --> 00:27:54,390
y descarga, lo que libera toda la memoria que usted puede haber tomado

325
00:27:54,390 --> 00:27:57,900
al tiempo que su diccionario.

326
00:28:01,070 --> 00:28:03,590
>> Vamos a echar un vistazo a dictionary.c.

327
00:28:03,590 --> 00:28:10,490
Vemos que es muy similar a dictionary.h, excepto que ahora sólo tiene todas estas TODOs en ella.

328
00:28:10,490 --> 00:28:16,980
Así que es tu trabajo. Con el tiempo, se le rellenando speller.c con todo este código.

329
00:28:16,980 --> 00:28:21,540
Dictionary.c, cuando se ejecuta, no es realmente va a hacer nada,

330
00:28:21,540 --> 00:28:29,590
así que mirar hacia speller.c para ver la aplicación real de la corrección ortográfica.

331
00:28:29,590 --> 00:28:32,060
A pesar de que usted no va a ser la edición de cualquiera de este código,

332
00:28:32,060 --> 00:28:38,050
es importante leer, comprender cuando se carga llamara, cuando estoy llamando cheque,

333
00:28:38,050 --> 00:28:42,350
sólo para entender, asigne a cabo, ver cómo trabaja la función.

334
00:28:42,350 --> 00:28:49,860
Vemos que se está comprobando el uso correcto.

335
00:28:49,860 --> 00:28:55,200
Esencialmente, cuando alguien se queda speller, esto indica que es opcional

336
00:28:55,200 --> 00:29:00,950
para que puedan pasar en un archivo de diccionario, porque no va a ser un archivo de diccionario por defecto.

337
00:29:00,950 --> 00:29:05,410
Y luego tienen que pasar en el texto que se va revise la ortografía.

338
00:29:05,410 --> 00:29:11,410
ofertas rusage con el tiempo porque una parte de este conjunto de procesadores que nos ocuparemos más adelante

339
00:29:11,410 --> 00:29:14,790
no sólo para conseguir un funcionamiento corrector ortográfico de trabajo

340
00:29:14,790 --> 00:29:17,190
pero en realidad cada vez que sea rápido.

341
00:29:17,190 --> 00:29:22,040
Y entonces ahí es donde rusage va a venir pulg

342
00:29:22,040 --> 00:29:28,740
Aquí, vemos la primera llamada a uno de nuestros archivos dictionary.c, que es de carga.

343
00:29:28,740 --> 00:29:34,720
Carga devuelve verdadero o falso - verdadero en el éxito, false en caso de fallo.

344
00:29:34,720 --> 00:29:41,400
Así que si el diccionario no se carga correctamente, entonces el speller.c devolverá 1 y dejar de fumar.

345
00:29:41,400 --> 00:29:47,920
Pero si se carga correctamente, entonces va a continuar.

346
00:29:47,920 --> 00:29:50,740
Seguimos, y vemos algún archivo I / O aquí,

347
00:29:50,740 --> 00:29:56,210
donde va a estar tratando con abrir el archivo de texto.

348
00:29:56,210 --> 00:30:04,640
Aquí, lo que hace es corrector comprueba cada palabra en el texto.

349
00:30:04,640 --> 00:30:09,270
Entonces, ¿qué está haciendo speller.c aquí se itera sobre cada una de las palabras en el archivo de texto

350
00:30:09,270 --> 00:30:12,790
y luego la comprobación en el diccionario.

351
00:30:24,680 --> 00:30:32,350
Aquí tenemos un booleano mal escrita que ver si el cheque devuelve true o no.

352
00:30:32,350 --> 00:30:37,110
Si la palabra es en realidad en el diccionario, entonces cheque devolverá true.

353
00:30:37,110 --> 00:30:39,760
Eso significa que la palabra no está mal escrito.

354
00:30:39,760 --> 00:30:45,330
Así que mal escrito sería falso, y es por eso que tenemos la explosión allí, la indicación.

355
00:30:45,330 --> 00:30:56,320
Seguimos adelante, y luego se hace un seguimiento de la cantidad de palabras mal escritas

356
00:30:56,320 --> 00:30:58,910
existen en el archivo.

357
00:30:58,910 --> 00:31:03,870
Se sigue y cierra el archivo.

358
00:31:03,870 --> 00:31:09,250
Entonces aquí, se informa de la cantidad de palabras mal escritas que tenía.

359
00:31:09,250 --> 00:31:12,680
Calcula la cantidad de tiempo que se tardó en cargar el diccionario,

360
00:31:12,680 --> 00:31:15,080
cuánto tiempo se tardó en comprobar,

361
00:31:15,080 --> 00:31:18,510
la cantidad de tiempo que tomó para calcular el tamaño,

362
00:31:18,510 --> 00:31:21,260
que, como veremos adelante, debe ser muy pequeña,

363
00:31:21,260 --> 00:31:25,390
y ¿cuánto tiempo se tardó en descargar el diccionario.

364
00:31:25,390 --> 00:31:27,700
Aquí arriba podemos ver la llamada a descargar aquí.

365
00:31:27,700 --> 00:31:52,690
Si vamos a comprobar el tamaño aquí,

366
00:31:52,690 --> 00:31:59,050
entonces podemos ver que aquí es la llamada a tamaño, donde determina el tamaño del diccionario.

367
00:32:05,730 --> 00:32:07,100
Awesome.

368
00:32:07,100 --> 00:32:10,920
>> Nuestra tarea en este conjunto de procesadores es la implementación de carga, que se carga el diccionario

369
00:32:10,920 --> 00:32:15,480
estructura de datos - lo que usted elija, ya sea una tabla hash o intentar a -

370
00:32:15,480 --> 00:32:18,810
con palabras del archivo de diccionario.

371
00:32:18,810 --> 00:32:25,290
Entonces usted tiene tamaño, que devolverá el número de palabras en el diccionario.

372
00:32:25,290 --> 00:32:29,860
Y si implementa la carga de una manera inteligente, a continuación, el tamaño debe ser bastante fácil.

373
00:32:29,860 --> 00:32:33,860
Entonces usted ha cheque, que comprobará si una palabra dada está en el diccionario.

374
00:32:33,860 --> 00:32:38,690
Así speller.c pasa en una cadena, y entonces usted tiene que comprobar si esa cadena

375
00:32:38,690 --> 00:32:41,610
está contenida dentro de su diccionario.

376
00:32:41,610 --> 00:32:46,750
Tenga en cuenta que por lo general tenemos los diccionarios estándar,

377
00:32:46,750 --> 00:32:53,020
pero en este conjunto de procesadores, básicamente cualquier diccionario aprobada en en cualquier idioma.

378
00:32:53,020 --> 00:32:57,040
Así que no podemos asumir que la palabra la que hay dentro.

379
00:32:57,040 --> 00:33:03,090
El FOOBAR palabra puede ser definido en un diccionario seguro que pasamos pulg

380
00:33:03,090 --> 00:33:07,920
Y entonces hemos descarga, lo que libera el diccionario de la memoria.

381
00:33:07,920 --> 00:33:11,930
>> En primer lugar, me gustaría ir sobre el método de la tabla de hash

382
00:33:11,930 --> 00:33:14,630
acerca de cómo podemos poner en práctica todas esas cuatro funciones,

383
00:33:14,630 --> 00:33:18,650
y luego voy a ir sobre la trata de método, cómo aplicar esas cuatro funciones,

384
00:33:18,650 --> 00:33:22,720
y al final de la conversación sobre algunos consejos generales cuando estás haciendo el conjunto de procesadores

385
00:33:22,720 --> 00:33:27,870
y también cómo es posible que pueda usar Valgrind para comprobar si hay fugas de memoria.

386
00:33:27,870 --> 00:33:30,550
>> Vamos a entrar en el método de la tabla hash.

387
00:33:30,550 --> 00:33:35,910
Una tabla hash consiste en una lista de cubos.

388
00:33:35,910 --> 00:33:43,010
Todos los valores, cada palabra, se va a ir a uno de estos cubos.

389
00:33:43,010 --> 00:33:53,200
Una tabla hash idealmente distribuye de manera uniforme todos esos valores que está pasando en

390
00:33:53,200 --> 00:33:57,160
y luego se rellena en el cubo de tal manera que cada cubo

391
00:33:57,160 --> 00:34:02,000
tiene aproximadamente el mismo número de valores en ella.

392
00:34:02,000 --> 00:34:09,630
La estructura de una tabla hash, tenemos una serie de listas enlazadas.

393
00:34:09,630 --> 00:34:17,900
Lo que hacemos es cuando se pasa de un valor, donde se comprueba que el valor debería pertenecer,

394
00:34:17,900 --> 00:34:23,840
que cubo al que pertenece, y luego se coloca en la lista enlazada asociada a ese cubo.

395
00:34:23,840 --> 00:34:28,199
Aquí, lo que tengo es una función hash.

396
00:34:28,199 --> 00:34:31,320
Es una tabla hash int.

397
00:34:31,320 --> 00:34:38,540
Así que para el primer segmento, cualquier número entero por debajo de 10 entran en el primer cubo.

398
00:34:38,540 --> 00:34:42,190
Los números enteros superiores a 10 pero inferior a 20 ir a la segunda,

399
00:34:42,190 --> 00:34:44,179
y, a continuación así sucesivamente y así sucesivamente.

400
00:34:44,179 --> 00:34:52,370
Para mí, cada segmento representa a estos números.

401
00:34:52,370 --> 00:34:59,850
Sin embargo, decir que me iban a pasar en el 50, por ejemplo.

402
00:34:59,850 --> 00:35:07,490
Parece como si las tres primeras contienen una serie de diez números.

403
00:35:07,490 --> 00:35:12,570
Pero yo quiero que mi tabla hash para tomar en cualquier tipo de números enteros,

404
00:35:12,570 --> 00:35:19,860
entonces yo tendría que filtrar todos los números por encima de 30 en el último segmento.

405
00:35:19,860 --> 00:35:26,660
Y así, pues, que se traduciría en una especie de tabla hash desequilibrada.

406
00:35:31,330 --> 00:35:35,640
Para reiterar, una tabla hash es sólo un conjunto de cubos

407
00:35:35,640 --> 00:35:38,590
donde cada cubo es una lista enlazada.

408
00:35:38,590 --> 00:35:43,730
Y así, para determinar dónde va cada valor, el cual entra en balde,

409
00:35:43,730 --> 00:35:46,260
usted va a querer lo que se llama una función hash

410
00:35:46,260 --> 00:35:55,010
que toma un valor y luego dice: este valor corresponde a un cubo determinado.

411
00:35:55,010 --> 00:36:00,970
Así que allá arriba, en este ejemplo, mi función hash tomó cada valor.

412
00:36:00,970 --> 00:36:03,020
Se comprobó si era menos de 10.

413
00:36:03,020 --> 00:36:05,360
Si lo fuera, habría que poner en el primer cubo.

414
00:36:05,360 --> 00:36:08,910
Comprueba si es menor de 20, lo coloca en el segundo si es cierto,

415
00:36:08,910 --> 00:36:12,880
comprueba si es menos de 30, y luego lo pone en el tercer cubo,

416
00:36:12,880 --> 00:36:16,990
y entonces todo lo demás cae justo al cubo cuarto.

417
00:36:16,990 --> 00:36:20,110
Así que cada vez que tenga un valor, la función hash

418
00:36:20,110 --> 00:36:25,420
colocará ese valor en el cubo adecuado.

419
00:36:25,420 --> 00:36:32,430
La función hash, básicamente, tiene que saber cómo cubos que tiene.

420
00:36:32,430 --> 00:36:37,960
Su tamaño de la tabla hash, el número de depósitos que tiene,

421
00:36:37,960 --> 00:36:41,190
que va a ser un número fijo que depende de usted, para que usted decida,

422
00:36:41,190 --> 00:36:43,590
pero va a ser un número fijo.

423
00:36:43,590 --> 00:36:51,840
Así que su función hash se confía en que para determinar qué cubeta cada llave entra en

424
00:36:51,840 --> 00:36:54,450
tal que es uniformemente distribuida.

425
00:36:56,150 --> 00:37:03,820
Al igual que en nuestra implementación de las listas enlazadas, ahora cada nodo en la tabla hash

426
00:37:03,820 --> 00:37:07,000
es en realidad va a tener un tipo char.

427
00:37:07,000 --> 00:37:14,340
Así que tenemos una matriz de caracteres llamado palabra y luego otro puntero al nodo siguiente,

428
00:37:14,340 --> 00:37:19,010
lo cual tiene sentido porque va a ser una lista enlazada.

429
00:37:19,010 --> 00:37:24,350
¿Recuerdas cuando había listas enlazadas, hice un llamado nodo * cabeza

430
00:37:24,350 --> 00:37:31,060
que estaba apuntando al primer nodo en la lista enlazada.

431
00:37:31,060 --> 00:37:34,020
Pero para nuestra tabla hash, ya que tenemos varias listas enlazadas,

432
00:37:34,020 --> 00:37:37,520
lo que queremos es que queremos que nuestra tabla hash para ser como, "¿Qué es un cubo?"

433
00:37:37,520 --> 00:37:43,340
Un cubo es simplemente una lista de punteros a nodos,

434
00:37:43,340 --> 00:37:50,620
y por lo que cada elemento en el cubo está apuntando a su lista vinculado correspondiente.

435
00:37:56,180 --> 00:38:01,520
Para volver a este esquema, se ve que los propios cubos son las flechas,

436
00:38:01,520 --> 00:38:06,980
No nodos reales.

437
00:38:11,680 --> 00:38:16,420
Una característica esencial de las funciones de hash es que son deterministas.

438
00:38:16,420 --> 00:38:19,440
Eso significa que cada vez que el hash del número 2,

439
00:38:19,440 --> 00:38:22,270
siempre debe devolver el mismo cubo.

440
00:38:22,270 --> 00:38:26,440
Cada valor único que se dedica a la función hash, si se repite,

441
00:38:26,440 --> 00:38:29,690
tiene que conseguir el mismo índice.

442
00:38:29,690 --> 00:38:34,210
Así que su función hash devuelve el índice de la matriz

443
00:38:34,210 --> 00:38:38,530
cuando dicho valor pertenece.

444
00:38:38,530 --> 00:38:41,790
Como mencioné antes, el número de depósitos es fijo,

445
00:38:41,790 --> 00:38:49,630
por lo que su índice que vuelva tiene que ser menor que el número de cubos

446
00:38:49,630 --> 00:38:52,680
pero mayor que 0.

447
00:38:52,680 --> 00:39:00,780
La razón por la que tenemos funciones de hash en lugar de sólo una lista simplemente enlazada

448
00:39:00,780 --> 00:39:09,290
o una sola matriz es que queremos ser capaces de saltar a una determinada sección más fácilmente

449
00:39:09,290 --> 00:39:11,720
si se conoce la característica de un valor -

450
00:39:11,720 --> 00:39:14,760
en lugar de tener que buscar a través de todo el diccionario entero,

451
00:39:14,760 --> 00:39:18,320
ser capaz de saltar a una determinada sección de la misma.

452
00:39:19,880 --> 00:39:24,440
Su función hash debe tener en cuenta que, idealmente,

453
00:39:24,440 --> 00:39:28,980
cada cubo tiene aproximadamente el mismo número de teclas.

454
00:39:28,980 --> 00:39:35,040
Puesto que la tabla hash es una serie de listas enlazadas,

455
00:39:35,040 --> 00:39:38,480
a continuación, las listas enlazadas mismos van a tener más de un nodo.

456
00:39:38,480 --> 00:39:43,210
En el ejemplo anterior, dos números diferentes, a pesar de que no eran iguales,

457
00:39:43,210 --> 00:39:46,950
cuando hash, volvería el mismo índice.

458
00:39:46,950 --> 00:39:53,620
Así que cuando se trata de palabras, una palabra cuando hashed

459
00:39:53,620 --> 00:39:57,450
sería el mismo valor hash como una palabra más.

460
00:39:57,450 --> 00:40:04,140
Eso es lo que llamamos una colisión, cuando tenemos un nodo que, cuando se aplica un algoritmo hash,

461
00:40:04,140 --> 00:40:09,610
la lista vinculada a ese cubo no está vacío.

462
00:40:09,610 --> 00:40:14,180
La técnica que se llama sondeo lineal,

463
00:40:14,180 --> 00:40:22,550
donde vaya a la lista enlazada y luego encontrar la que desea insertar el nodo

464
00:40:22,550 --> 00:40:25,520
porque hay una colisión.

465
00:40:25,520 --> 00:40:28,070
Se puede ver que podría haber un trade-off, ¿verdad?

466
00:40:28,070 --> 00:40:33,760
Si usted tiene una tabla hash muy pequeño, un número muy pequeño de cubos,

467
00:40:33,760 --> 00:40:36,380
entonces usted va a tener un montón de colisiones.

468
00:40:36,380 --> 00:40:40,460
Pero entonces, si usted hace una tabla hash muy grande,

469
00:40:40,460 --> 00:40:44,110
usted está probablemente va a minimizar las colisiones,

470
00:40:44,110 --> 00:40:47,170
pero va a ser una estructura de datos muy grandes.

471
00:40:47,170 --> 00:40:49,310
Va a ser ventajas y desventajas con eso.

472
00:40:49,310 --> 00:40:51,310
Así que cuando usted está haciendo su conjunto de procesadores, trate de jugar

473
00:40:51,310 --> 00:40:54,210
entre tal vez hacer una tabla hash de menor

474
00:40:54,210 --> 00:41:02,100
pero a sabiendas de que va a tomar un poco más de tiempo para recorrer los diferentes elementos

475
00:41:02,100 --> 00:41:04,270
de las listas enlazadas.

476
00:41:04,270 --> 00:41:09,500
>> ¿Qué carga se va a hacer es iterar sobre cada palabra en el diccionario.

477
00:41:09,500 --> 00:41:13,180
Se pasa un puntero al archivo de diccionario.

478
00:41:13,180 --> 00:41:18,050
Así que vamos a aprovechar el archivo de funciones I / O que dominan en pset4

479
00:41:18,050 --> 00:41:23,010
e iterar sobre cada palabra en el diccionario.

480
00:41:23,010 --> 00:41:26,620
Usted quisiera que cada palabra en el diccionario para convertirse en un nuevo nodo,

481
00:41:26,620 --> 00:41:32,730
y usted va a colocar cada uno de los nodos dentro de la estructura de datos del diccionario.

482
00:41:32,730 --> 00:41:36,560
Siempre que reciba una nueva palabra, usted sabe que va a convertirse en un nodo.

483
00:41:36,560 --> 00:41:46,590
Así que usted puede ir inmediatamente y malloc un puntero de nodo para cada nueva palabra que usted tiene.

484
00:41:46,590 --> 00:41:52,610
Aquí estoy llamando a mi new_node puntero de nodo y estoy mallocing qué? El tamaño de un nodo.

485
00:41:52,610 --> 00:41:59,190
Luego de leer la cadena real de un archivo, ya que el diccionario se almacena

486
00:41:59,190 --> 00:42:03,340
por una palabra y una nueva línea, lo que podemos aprovechar

487
00:42:03,340 --> 00:42:06,520
es la función fscanf,

488
00:42:06,520 --> 00:42:10,280
por lo que es el archivo de diccionario que nos pasa adentro,

489
00:42:10,280 --> 00:42:18,900
por lo que analiza el archivo para una cadena y coloca esa cadena en el argumento anterior.

490
00:42:18,900 --> 00:42:26,890
Si se llama a una de las conferencias, cuando nos fuimos

491
00:42:26,890 --> 00:42:29,320
y el tipo de pelado de las capas de nuevo en la biblioteca CS50,

492
00:42:29,320 --> 00:42:33,430
vimos una implementación de fscanf allí.

493
00:42:33,430 --> 00:42:37,700
Para volver a fscanf, tenemos el archivo que estamos leyendo,

494
00:42:37,700 --> 00:42:42,570
estamos buscando una cadena en el archivo, y luego lo vamos a poner en

495
00:42:42,570 --> 00:42:48,340
aquí tengo new_node-> new_node palabra porque es un puntero de nodo,

496
00:42:48,340 --> 00:42:50,380
no un nodo real.

497
00:42:50,380 --> 00:42:57,100
Así que lo que estoy diciendo new_node, quiero ir al nodo que está apuntando a

498
00:42:57,100 --> 00:43:01,190
y después asignar ese valor a la palabra.

499
00:43:01,190 --> 00:43:08,540
Queremos aprovechar entonces la palabra y la inserta en la tabla hash.

500
00:43:08,540 --> 00:43:13,750
Darse cuenta de que hemos hecho new_node un puntero nodo

501
00:43:13,750 --> 00:43:18,230
porque vamos a querer saber cuál es la dirección de nodo que es

502
00:43:18,230 --> 00:43:23,940
cuando se inserta en porque la estructura de los propios nodos, de la estructura,

503
00:43:23,940 --> 00:43:26,380
es que tienen un puntero a un nuevo nodo.

504
00:43:26,380 --> 00:43:30,820
Entonces, ¿cuál es la dirección del nodo que va a señalar?

505
00:43:30,820 --> 00:43:34,550
Esa dirección va a ser new_node.

506
00:43:34,550 --> 00:43:42,140
¿Tiene sentido, ¿por qué estamos haciendo new_node a * nodo en lugar de un nodo?

507
00:43:43,700 --> 00:43:45,700
Bien.

508
00:43:45,700 --> 00:43:52,840
Tenemos una palabra. Ese valor es new_node-> palabra.

509
00:43:52,840 --> 00:43:55,970
Que contiene la palabra del diccionario que desea ingresar.

510
00:43:55,970 --> 00:44:00,210
Así que lo que quiero hacer es que queremos llamar a nuestra función hash en esa cadena

511
00:44:00,210 --> 00:44:03,780
porque nuestra función hash toma una cadena y luego nos devuelve un entero,

512
00:44:03,780 --> 00:44:12,090
donde ese entero es el índice de tabla hash donde en ese índice representa el cubo.

513
00:44:12,090 --> 00:44:18,260
Queremos aprovechar ese índice y luego ir a ese índice de la tabla hash

514
00:44:18,260 --> 00:44:26,960
y luego usar esa lista vinculada a insertar el nodo en new_node.

515
00:44:26,960 --> 00:44:31,950
Recuerde que sin embargo decide insertar el nodo,

516
00:44:31,950 --> 00:44:34,370
ya sea en el medio si desea ordenar

517
00:44:34,370 --> 00:44:39,650
o al principio o al final, sólo asegúrese de que el último nodo siempre apunta a NULL

518
00:44:39,650 --> 00:44:46,730
porque esa es la única manera de saber dónde está el último elemento de la lista enlazada es.

519
00:44:50,790 --> 00:44:59,710
>> Si el tamaño es un número entero que representa el número de palabras en un diccionario,

520
00:44:59,710 --> 00:45:03,060
entonces una forma de hacer esto es que cada vez que se llama tamaño

521
00:45:03,060 --> 00:45:05,840
vamos a través de cada elemento en nuestra tabla hash

522
00:45:05,840 --> 00:45:09,410
y luego iterar a través de cada lista enlazada dentro de la tabla hash

523
00:45:09,410 --> 00:45:13,770
y luego calcular la longitud de ello, el aumento de nuestra contador 1 en 1.

524
00:45:13,770 --> 00:45:16,580
Pero cada vez que el tamaño se llama, que va a tomar mucho tiempo

525
00:45:16,580 --> 00:45:22,120
porque vamos a ser linealmente sondeo cada lista simplemente enlazada.

526
00:45:22,120 --> 00:45:30,530
En su lugar, va a ser mucho más fácil si usted mantiene un registro de cuántas palabras se pasa pulg

527
00:45:30,530 --> 00:45:36,330
Así que si usted incluye un contador dentro de su función de carga

528
00:45:36,330 --> 00:45:42,430
que se actualiza según sea necesario, a continuación, contador, si lo establece en una variable global,

529
00:45:42,430 --> 00:45:44,930
será capaz de acceder por tamaño.

530
00:45:44,930 --> 00:45:51,450
Entonces, ¿qué tamaño podría simplemente hacer es en una sola línea, simplemente devuelva el valor del contador,

531
00:45:51,450 --> 00:45:55,500
el tamaño del diccionario, que ya se trataron en carga.

532
00:45:55,500 --> 00:46:05,190
Eso es lo que quise decir cuando dije que si implementa la carga de una manera útil,

533
00:46:05,190 --> 00:46:08,540
entonces el tamaño va a ser bastante fácil.

534
00:46:08,540 --> 00:46:11,350
>> Así que ahora tenemos que comprobar.

535
00:46:11,350 --> 00:46:15,960
Ahora nos enfrentamos con las palabras del archivo de texto de entrada,

536
00:46:15,960 --> 00:46:19,910
y así vamos a estar revisando si todas esas palabras de entrada

537
00:46:19,910 --> 00:46:22,520
son en realidad en el diccionario o no.

538
00:46:22,520 --> 00:46:26,520
Al igual que Scramble, queremos permitir que no se distingan.

539
00:46:26,520 --> 00:46:32,110
Usted quiere asegurarse de que todas las palabras salieron de adentro, aunque son mayúsculas y minúsculas,

540
00:46:32,110 --> 00:46:37,840
cuando se llama con cadena de comparación, son equivalentes.

541
00:46:37,840 --> 00:46:42,450
Las palabras en los archivos de diccionario de texto son realmente minúsculas.

542
00:46:42,450 --> 00:46:49,280
Otra cosa es que se puede asumir que cada palabra pasada en, cada cadena,

543
00:46:49,280 --> 00:46:53,200
va a ser alfabético o contener apóstrofos.

544
00:46:53,200 --> 00:46:58,010
Apostrophes van a ser válidos palabras en el diccionario.

545
00:46:58,010 --> 00:47:06,470
Así que si usted tiene una palabra con apóstrofo S, que es una palabra real legítimo en su diccionario

546
00:47:06,470 --> 00:47:11,650
que va a ser uno de los nodos de la tabla hash.

547
00:47:13,470 --> 00:47:18,350
Compruebe si funciona con la palabra existe, entonces tiene que estar en nuestra tabla hash.

548
00:47:18,350 --> 00:47:22,210
Si la palabra está en el diccionario, entonces todas las palabras en el diccionario se encuentran en la tabla hash,

549
00:47:22,210 --> 00:47:26,560
así que vamos a buscar esta palabra en la tabla hash.

550
00:47:26,560 --> 00:47:29,250
Sabemos que desde que implementamos nuestra función hash

551
00:47:29,250 --> 00:47:38,420
de tal manera que cada palabra única es siempre ordenadas por el mismo valor,

552
00:47:38,420 --> 00:47:43,340
entonces sabemos que en lugar de buscar a través de toda nuestra tabla hash entero,

553
00:47:43,340 --> 00:47:48,310
en realidad podemos encontrar la lista enlazada que esa palabra debería pertenecer.

554
00:47:48,310 --> 00:47:51,850
Si fuera en el diccionario, entonces sería en ese cubo.

555
00:47:51,850 --> 00:47:57,140
¿Qué podemos hacer, si la palabra es el nombre de nuestra cadena pasada,

556
00:47:57,140 --> 00:48:01,560
podemos simplemente hash que palabra y mirada a la lista enlazada

557
00:48:01,560 --> 00:48:06,410
en el valor de la tabla hash [hash (palabra)].

558
00:48:06,410 --> 00:48:12,410
A partir de ahí, lo que podemos hacer es que tenemos un pequeño subconjunto de nodos para buscar esta palabra,

559
00:48:12,410 --> 00:48:16,770
por lo que puede atravesar la lista enlazada, con un ejemplo de antes en el tutorial,

560
00:48:16,770 --> 00:48:24,110
y luego llamar a comparación de cadenas en la palabra siempre que el cursor está apuntando,

561
00:48:24,110 --> 00:48:28,430
esa palabra, y ver si los que comparar.

562
00:48:30,280 --> 00:48:35,110
Dependiendo de la forma en que organizan su función hash,

563
00:48:35,110 --> 00:48:39,260
si está ordenado, es posible que pueda volver falso un poco antes,

564
00:48:39,260 --> 00:48:43,440
pero si se trata de clasificar, entonces usted quiere seguir recorriendo a través de su lista enlazada

565
00:48:43,440 --> 00:48:46,480
hasta encontrar el último elemento de la lista.

566
00:48:46,480 --> 00:48:53,320
Y si todavía no has encontrado la palabra por el tiempo que has llegado al final de la lista enlazada,

567
00:48:53,320 --> 00:48:56,890
que significa que su palabra no existe en el diccionario,

568
00:48:56,890 --> 00:48:59,410
y para que la palabra no es válido,

569
00:48:59,410 --> 00:49:02,730
y el cheque debe devolver false.

570
00:49:02,730 --> 00:49:09,530
>> Ahora llegamos a la descarga, donde queremos liberar a todos los nodos que hemos malloc'd,

571
00:49:09,530 --> 00:49:14,050
tan libre de todos los nodos dentro de nuestra tabla hash.

572
00:49:14,050 --> 00:49:20,270
Vamos a querer iterar sobre todas las listas enlazadas y libres de todos los nodos en eso.

573
00:49:20,270 --> 00:49:29,350
Si se mira más arriba en el tutorial para el ejemplo en el que liberar a una lista enlazada,

574
00:49:29,350 --> 00:49:35,140
entonces usted querrá repetir este proceso para cada elemento en la tabla hash.

575
00:49:35,140 --> 00:49:37,780
Y voy a ir más de esto hacia el final del tutorial,

576
00:49:37,780 --> 00:49:46,600
pero Valgrind es una herramienta donde se puede ver si se ha liberado correctamente

577
00:49:46,600 --> 00:49:53,600
cada nodo que ha malloc'd o cualquier otra cosa que hayas malloc'd, cualquier otro puntero.

578
00:49:55,140 --> 00:50:00,530
Así que eso es tablas hash, donde tenemos un número finito de cubos

579
00:50:00,530 --> 00:50:09,220
y una función hash que tendrá un valor y asignar ese valor a un cubo determinado.

580
00:50:09,220 --> 00:50:13,340
>> Ahora llegamos a intentos.

581
00:50:13,340 --> 00:50:18,750
Trata tipo de mirada así, y también voy a sacar un ejemplo.

582
00:50:18,750 --> 00:50:25,630
Básicamente, usted tiene toda una serie de cartas posibles,

583
00:50:25,630 --> 00:50:29,210
y entonces cada vez que usted está construyendo una palabra,

584
00:50:29,210 --> 00:50:36,490
carta que pueden enlazarse para un diccionario para una amplia gama de posibilidades.

585
00:50:36,490 --> 00:50:40,840
Algunas palabras comienzan con C, pero luego continuar con A,

586
00:50:40,840 --> 00:50:42,960
pero otros continúan con O, por ejemplo.

587
00:50:42,960 --> 00:50:51,090
Un trie es una manera de visualizar todas las posibles combinaciones de esas palabras.

588
00:50:51,090 --> 00:50:59,070
Un trie se va a realizar un seguimiento de la secuencia de letras que forman las palabras,

589
00:50:59,070 --> 00:51:08,280
ramifica cuando sea necesario, cuando una sola letra puede ser seguido por un múltiplo de cartas,

590
00:51:08,280 --> 00:51:16,630
y al final indican en cada punto si esa palabra es válida o no

591
00:51:16,630 --> 00:51:30,120
porque si usted está deletreando la palabra MAT, MA No creo que es una palabra válida, pero es MAT.

592
00:51:30,120 --> 00:51:37,820
Y así, en el trie, lo que indicaría que, después de MAT que en realidad es una palabra válida.

593
00:51:41,790 --> 00:51:48,590
Cada nodo en nuestro trie es en realidad va a contener una matriz de punteros de nodos,

594
00:51:48,590 --> 00:51:52,970
y vamos a tener, en concreto, 27 de esos punteros a nodos,

595
00:51:52,970 --> 00:52:00,550
una para cada letra del alfabeto, así como el carácter de apóstrofo.

596
00:52:00,550 --> 00:52:10,450
Cada elemento de la matriz se está yendo al punto a otro nodo.

597
00:52:10,450 --> 00:52:14,020
Así que si ese nodo es NULL, si no hay nada después de eso,

598
00:52:14,020 --> 00:52:20,550
entonces sabemos que no hay más cartas en esa secuencia de palabras.

599
00:52:20,550 --> 00:52:26,950
Pero si ese nodo no es NULL, que significa que hay más cartas en que secuencia de letras.

600
00:52:26,950 --> 00:52:32,160
Y además, cada nodo indica si es el último carácter de una palabra o no.

601
00:52:38,110 --> 00:52:43,170
>> Vamos a entrar en un ejemplo de un trie.

602
00:52:50,500 --> 00:52:58,340
Primero tengo espacio para 27 nodos en esta matriz.

603
00:52:58,340 --> 00:53:03,200
Si tengo la palabra BAR -

604
00:53:13,310 --> 00:53:15,370
Si tengo la palabra BAR y quiero insertar en que,

605
00:53:15,370 --> 00:53:22,700
la primera letra es B, así que si mi trie está vacío,

606
00:53:22,700 --> 00:53:29,910
B es la segunda letra del alfabeto, así que voy a optar por poner esto aquí en este índice.

607
00:53:29,910 --> 00:53:33,450
Voy a tener B aquí.

608
00:53:33,450 --> 00:53:42,400
B va a ser un nodo que apunta a otra matriz de todos los personajes posibles

609
00:53:42,400 --> 00:53:45,870
que puede seguir después de la letra B.

610
00:53:45,870 --> 00:53:57,610
En este caso, estoy tratando con la palabra BAR, por lo que A se ve aquí.

611
00:54:02,000 --> 00:54:08,990
Después de una, yo tengo la letra R, por lo que entonces A Puntos ahora para su propia combinación,

612
00:54:08,990 --> 00:54:15,120
y R estarán aquí.

613
00:54:15,120 --> 00:54:22,470
BAR es una palabra completa, entonces yo voy a tener el punto R a otro nodo

614
00:54:22,470 --> 00:54:33,990
que dice que esa palabra es válida.

615
00:54:36,010 --> 00:54:40,970
Ese nodo también va a tener un conjunto de nodos,

616
00:54:40,970 --> 00:54:45,260
pero los que podrían ser NULL.

617
00:54:45,260 --> 00:54:49,080
Pero, básicamente, se puede seguir así.

618
00:54:49,080 --> 00:54:54,250
Eso será un poco más claro cuando vamos a un ejemplo diferente,

619
00:54:54,250 --> 00:54:56,780
así que tengan paciencia conmigo allí.

620
00:54:56,780 --> 00:55:02,050
Ahora tenemos BAR interior de nuestro diccionario.

621
00:55:02,050 --> 00:55:05,980
Ahora digamos que tenemos la palabra BAZ.

622
00:55:05,980 --> 00:55:12,630
Comenzamos con B, y ya tenemos B como una de las letras que hay en nuestro diccionario.

623
00:55:12,630 --> 00:55:15,170
Esto es seguido por A. Tenemos una ya.

624
00:55:15,170 --> 00:55:19,250
Pero en su lugar, tenemos lo siguiente Z.

625
00:55:19,250 --> 00:55:25,490
Así pues, un elemento en nuestra matriz va a ser Z,

626
00:55:25,490 --> 00:55:30,810
y es así, que se va a apuntar a otra final válido de la palabra.

627
00:55:30,810 --> 00:55:36,930
Así vemos que cuando seguimos a través de B y luego A,

628
00:55:36,930 --> 00:55:43,480
hay dos opciones diferentes en la actualidad en nuestro diccionario para las palabras que comienzan con B y A.

629
00:55:49,650 --> 00:55:57,460
Digamos que quería insertar la palabra pepe.

630
00:55:57,460 --> 00:56:05,620
Entonces nos volveríamos a hacer una entrada en F.

631
00:56:05,620 --> 00:56:11,320
F es un nodo que apunta a una matriz completa.

632
00:56:11,320 --> 00:56:22,790
Nos encontraríamos O, vaya a O, O entonces enlaza a una lista completa.

633
00:56:22,790 --> 00:56:35,340
Tendríamos B y continuar luego, tendríamos entonces A y R.

634
00:56:35,340 --> 00:56:43,570
Entonces atraviesa foobar todo el camino hasta FOOBAR es una palabra correcta.

635
00:56:43,570 --> 00:56:52,590
Y así, entonces esto sería una palabra válida.

636
00:56:52,590 --> 00:57:00,170
Ahora que nuestra próxima palabra en el diccionario es en realidad la palabra FOO.

637
00:57:00,170 --> 00:57:03,530
Diríamos F. Lo que sigue a F?

638
00:57:03,530 --> 00:57:06,190
De hecho ya tenemos un espacio para O, así que voy a continuar.

639
00:57:06,190 --> 00:57:09,150
No es necesario hacer una nueva. Continuar.

640
00:57:09,150 --> 00:57:15,500
FOO es una palabra válida en este diccionario, por lo que a continuación voy a indicar

641
00:57:15,500 --> 00:57:21,660
que es válida.

642
00:57:21,660 --> 00:57:28,370
Si dejo mi secuencia allí, que sería correcto.

643
00:57:28,370 --> 00:57:33,050
Pero si continuamos con nuestra secuencia de FOO hasta B

644
00:57:33,050 --> 00:57:39,750
y sólo tenía foob, foob no es una palabra, y eso no es indicado como una válida.

645
00:57:47,370 --> 00:57:57,600
En un trie, tienes todo el nodo que indica si se trata de una palabra válida o no,

646
00:57:57,600 --> 00:58:05,840
y entonces cada nodo también tiene una serie de 27 punteros a nodos

647
00:58:05,840 --> 00:58:09,520
que a continuación punto a nodos en sí mismos.

648
00:58:09,520 --> 00:58:12,940
>> Esta es una manera de cómo es posible que desee definir esto.

649
00:58:12,940 --> 00:58:17,260
Sin embargo, al igual que en el ejemplo de la tabla hash, donde tuvimos un nodo cabeza *

650
00:58:17,260 --> 00:58:21,320
para indicar el comienzo de nuestra lista enlazada, también vamos a querer

651
00:58:21,320 --> 00:58:29,150
alguna manera de saber dónde está el principio de nuestra trie es.

652
00:58:29,150 --> 00:58:34,110
Algunos llaman a la gente trata de árboles, y ahí es donde viene de la raíz.

653
00:58:34,110 --> 00:58:36,910
Así que queremos que la raíz de nuestro árbol para asegurarse de que nos quedamos a tierra

654
00:58:36,910 --> 00:58:39,570
a donde nuestro trie es.

655
00:58:42,910 --> 00:58:46,300
Ya fui tipo de

656
00:58:46,300 --> 00:58:50,240
la forma en que podía pensar en cargar cada palabra en el diccionario.

657
00:58:50,240 --> 00:58:54,540
Esencialmente, por cada palabra que vas a querer recorrer su trie

658
00:58:54,540 --> 00:58:59,590
y sabiendo que todos los elementos de los niños - lo llamamos niños en este caso -

659
00:58:59,590 --> 00:59:04,290
corresponde a una letra diferente, usted va a desear para comprobar los valores

660
00:59:04,290 --> 00:59:08,320
en ese índice en particular que corresponde a la letra.

661
00:59:08,320 --> 00:59:11,260
Así que pensando todo el camino de vuelta a César y Vigenère,

662
00:59:11,260 --> 00:59:16,070
sabiendo que cada letra puede tipo de mapa a un índice alfabético,

663
00:59:16,070 --> 00:59:20,690
Definitivamente la A a la Z va a ser muy fácil de asignar a una letra del alfabeto,

664
00:59:20,690 --> 00:59:25,200
pero, por desgracia, apóstrofos son también un carácter aceptada en palabras.

665
00:59:25,200 --> 00:59:31,650
Ni siquiera estoy seguro de cuál es el valor ASCII es,

666
00:59:31,650 --> 00:59:39,250
por lo que para que si quieres encontrar un índice para decidir si usted quiere que ser el primero

667
00:59:39,250 --> 00:59:44,550
o el último, usted tendrá que hacer un cheque duro codificado para que

668
00:59:44,550 --> 00:59:48,930
y luego poner que en el índice de 26, por ejemplo.

669
00:59:48,930 --> 00:59:55,300
Así que usted está comprobando el valor en los niños [i]

670
00:59:55,300 --> 00:59:58,400
donde [e] corresponde a cualquier carta que usted está en.

671
00:59:58,400 --> 01:00:04,110
Si es NULL, lo que significa que no hay actualmente ningún cartas posibles

672
01:00:04,110 --> 01:00:08,150
derivada de la secuencia anterior, por lo que vas a querer a malloc

673
01:00:08,150 --> 01:00:13,150
y crea un nuevo nodo y que los niños tienen [i] apuntan a que

674
01:00:13,150 --> 01:00:17,890
por lo que cree - cuando inserta una letra en el rectángulo -

675
01:00:17,890 --> 01:00:23,680
hacer que los niños no nulo y el punto en que el nuevo nodo.

676
01:00:23,680 --> 01:00:28,340
Pero si eso no es NULL, como en nuestro ejemplo de FOO

677
01:00:28,340 --> 01:00:34,570
cuando ya teníamos FOOBAR, continuamos,

678
01:00:34,570 --> 01:00:44,010
y no estamos siempre haciendo un nuevo nodo, sino sólo establecer en true is_word

679
01:00:44,010 --> 01:00:47,790
al final de la palabra.

680
01:00:50,060 --> 01:00:55,340
>> Así que, como antes, porque aquí estamos tratando con todas las cartas a la vez,

681
01:00:55,340 --> 01:01:01,470
que va a ser más fácil para usted para el tamaño, en lugar de tener que calcular

682
01:01:01,470 --> 01:01:06,910
y pasar por todo el árbol y calcular cuántos hijos tengo

683
01:01:06,910 --> 01:01:10,850
y luego se ramifica, recordando cuántos están en el lado izquierdo y en el lado derecho

684
01:01:10,850 --> 01:01:12,850
y cosas por el estilo, va a ser mucho más fácil para usted

685
01:01:12,850 --> 01:01:16,220
si usted acaba de hacer un seguimiento de la cantidad de palabras que está añadiendo en

686
01:01:16,220 --> 01:01:18,080
cuando usted está tratando con carga.

687
01:01:18,080 --> 01:01:22,630
Y así, luego de que el tamaño medio sólo puede devolver una variable global de tamaño.

688
01:01:25,320 --> 01:01:28,530
>> Ahora vamos a comprobar.

689
01:01:28,530 --> 01:01:33,920
Mismas normas que antes, en la que desea permitir para que no se distingan.

690
01:01:33,920 --> 01:01:40,400
Además, se supone que las cadenas son caracteres alfabéticos o apóstrofos sólo los

691
01:01:40,400 --> 01:01:44,000
porque los niños es una matriz de 27 de largo,

692
01:01:44,000 --> 01:01:48,480
así que todas las letras del alfabeto más el apóstrofe.

693
01:01:48,480 --> 01:01:53,800
Para comprobar lo que usted querrá hacer es que usted querrá empezar en la raíz

694
01:01:53,800 --> 01:01:58,440
porque la raíz se apuntan a una matriz que contiene

695
01:01:58,440 --> 01:02:01,630
todas las cartas posibles a partir de una palabra.

696
01:02:01,630 --> 01:02:03,680
Vas a empezar por ahí,

697
01:02:03,680 --> 01:02:11,590
y entonces usted va a comprobar es el valor NULL o no,

698
01:02:11,590 --> 01:02:16,490
porque si el valor es NULL, que significa que el diccionario no tiene ningún valor

699
01:02:16,490 --> 01:02:21,480
que contiene esa carta en ese orden particular.

700
01:02:21,480 --> 01:02:24,970
Si es NULL, entonces eso significa que la palabra está mal escrita en seguida.

701
01:02:24,970 --> 01:02:27,110
Pero si no es NULL, entonces usted puede continuar,

702
01:02:27,110 --> 01:02:34,090
decir que la primera letra es una letra posible por primera vez en una palabra,

703
01:02:34,090 --> 01:02:40,630
por lo que ahora quiero comprobar si la segunda letra, esa secuencia, está en mi diccionario.

704
01:02:40,630 --> 01:02:46,540
Así que vamos a ir al índice de los hijos del primer nodo

705
01:02:46,540 --> 01:02:50,720
y comprobar si esa segunda carta existe.

706
01:02:50,720 --> 01:02:57,440
A continuación, repita este proceso para comprobar si esa secuencia es válida o no

707
01:02:57,440 --> 01:02:59,060
dentro de su trie.

708
01:02:59,060 --> 01:03:06,430
Cada vez que los niños de nodo en que los puntos de índice en NULL,

709
01:03:06,430 --> 01:03:10,710
Sabe usted que esa secuencia no existe,

710
01:03:10,710 --> 01:03:16,230
pero si se llega al final de la palabra que ha introducido,

711
01:03:16,230 --> 01:03:20,070
entonces usted quiere comprobar ahora que he terminado esta secuencia

712
01:03:20,070 --> 01:03:27,610
y se encontró en medio de mi trie, es esa palabra válida o no?

713
01:03:27,610 --> 01:03:32,480
Y entonces usted quiere comprobar esto, y es que cuando si has encontrado esa secuencia,

714
01:03:32,480 --> 01:03:35,120
entonces usted quiere comprobar si esa palabra es válida o no

715
01:03:35,120 --> 01:03:40,290
porque recuerdo que en el caso anterior que dibujé donde tuvimos foob,

716
01:03:40,290 --> 01:03:48,410
que era una secuencia válida que hemos encontrado, pero no era una palabra real válido en sí.

717
01:03:50,570 --> 01:03:59,000
>> Del mismo modo, para descargar en los intentos que desea descargar todos los nodos del trie.

718
01:03:59,000 --> 01:04:04,790
Lo siento. Similar a las tablas hash en donde descargar liberamos todos los nodos,

719
01:04:04,790 --> 01:04:09,740
en los intentos que queremos liberar también a todos los nodos.

720
01:04:09,740 --> 01:04:15,000
Descargue en realidad será más fácil trabajar de abajo hacia arriba

721
01:04:15,000 --> 01:04:19,290
porque son esencialmente las listas enlazadas.

722
01:04:19,290 --> 01:04:22,540
Así que queremos asegurarnos de que nos aferramos a todos los valores

723
01:04:22,540 --> 01:04:25,700
y libre de todos ellos de forma explícita.

724
01:04:25,700 --> 01:04:28,840
¿Qué vas a querer hacer si usted está trabajando con un trie

725
01:04:28,840 --> 01:04:35,640
es viajar a la parte inferior y libre en el nodo más bajo posible en primer lugar

726
01:04:35,640 --> 01:04:39,190
y luego ir a todos esos niños y luego liberar a todos aquellos,

727
01:04:39,190 --> 01:04:43,050
subir, etc, entonces libre

728
01:04:43,050 --> 01:04:48,790
Tipo de como tratar con la capa inferior de la primera trie

729
01:04:48,790 --> 01:04:51,940
y luego ir hasta la parte superior una vez que haya liberado todo.

730
01:04:51,940 --> 01:04:56,720
Este es un buen ejemplo de que la función recursiva puede ser útil.

731
01:04:56,720 --> 01:05:03,830
Una vez que haya liberado la capa inferior de su trie,

732
01:05:03,830 --> 01:05:08,000
luego se llama a descargar sobre el resto de la misma,

733
01:05:08,000 --> 01:05:13,620
asegurándose de liberar a todos los mini -

734
01:05:13,620 --> 01:05:16,410
Puedes tipo de visualizarlo como intentos mini.

735
01:05:23,300 --> 01:05:28,990
Así que tiene su raíz aquí.

736
01:05:30,840 --> 01:05:35,230
Yo sólo lo estoy simplificando así que no tienes que dibujar 26 de ellos.

737
01:05:37,250 --> 01:05:43,770
Así que los tiene, y entonces éstos representan secuencias de palabras

738
01:05:43,770 --> 01:05:54,620
donde todos estos pequeños círculos son letras que son secuencias válidas de cartas.

739
01:06:03,040 --> 01:06:07,160
Vamos a seguir un poco más.

740
01:06:15,110 --> 01:06:25,750
¿Qué vas a querer hacer es liberar el fondo aquí y luego liberar esta

741
01:06:25,750 --> 01:06:31,640
y entonces libre este en la parte inferior antes de liberar la parte superior hasta aquí

742
01:06:31,640 --> 01:06:38,180
porque si algo libre en el segundo nivel aquí,

743
01:06:38,180 --> 01:06:47,230
entonces usted realmente perder este valor aquí.

744
01:06:47,230 --> 01:06:54,780
Es por eso que es importante para descargar en un trie para asegurarse de que usted libere la parte inferior primero.

745
01:06:54,780 --> 01:06:59,480
Lo que usted puede ser que desee hacer es decir por cada nodo

746
01:06:59,480 --> 01:07:06,430
Quiero descargar todo de los niños.

747
01:07:16,060 --> 01:07:22,140
>> Ahora que hemos repasado descargar para el método de tabla hash, así como el método trie,

748
01:07:22,140 --> 01:07:27,020
vamos a querer mirar Valgrind.

749
01:07:27,020 --> 01:07:29,640
Valgrind se ejecuta con los siguientes comandos.

750
01:07:29,640 --> 01:07:32,700
Usted tiene valgrind-v.

751
01:07:32,700 --> 01:07:40,960
Estás comprobación de todas las fugas cuando se ejecuta speller dado este texto determinado

752
01:07:40,960 --> 01:07:46,980
porque ortografía tiene que tomar en un archivo de texto.

753
01:07:46,980 --> 01:07:52,330
Así Valgrind ejecutará el programa, le dirá la cantidad de bytes que asigna,

754
01:07:52,330 --> 01:07:57,150
cantidad de bytes que liberó, y ella le dirá si usted liberado lo suficiente

755
01:07:57,150 --> 01:07:58,930
o si usted no lo hizo lo suficientemente libre,

756
01:07:58,930 --> 01:08:02,850
o, a veces incluso se puede sobre-libre, libre como un nodo que ya ha sido liberado

757
01:08:02,850 --> 01:08:05,140
y por lo que le devuelven errores.

758
01:08:05,140 --> 01:08:11,600
Si utiliza Valgrind, que le dará algunos mensajes

759
01:08:11,600 --> 01:08:15,970
indica si se ha liberado ni menos que suficiente, lo suficiente,

760
01:08:15,970 --> 01:08:19,609
o más de lo suficiente.

761
01:08:24,370 --> 01:08:30,410
>> Una parte de este conjunto de procesadores, es opcional para desafiar a la Junta Grande.

762
01:08:30,410 --> 01:08:35,790
Pero cuando nos enfrentamos a estas estructuras de datos

763
01:08:35,790 --> 01:08:40,689
es una especie de divertido ver la rapidez y la eficiencia de sus estructuras de datos podría ser.

764
01:08:40,689 --> 01:08:44,490
¿Su resultado de la función hash en una gran cantidad de colisiones?

765
01:08:44,490 --> 01:08:46,300
¿O es su tamaño de datos muy grande?

766
01:08:46,300 --> 01:08:49,420
¿Se necesita mucho tiempo para recorrer?

767
01:08:49,420 --> 01:08:54,800
En el registro de ortografía, nos devuelve la cantidad de tiempo que se utiliza para cargar,

768
01:08:54,800 --> 01:08:57,700
para comprobar, para llevar a cabo tamaño, y descargar a,

769
01:08:57,700 --> 01:09:00,720
y por lo que aquellos se publican en la Bolsa de Nueva York,

770
01:09:00,720 --> 01:09:03,600
donde puedes competir contra tus compañeros de clase

771
01:09:03,600 --> 01:09:11,350
y algunos miembros del personal para ver quién tiene el más rápido corrector ortográfico.

772
01:09:11,350 --> 01:09:14,760
Una cosa que me gustaría destacar sobre las tablas hash

773
01:09:14,760 --> 01:09:20,470
es que hay algunas funciones hash bastante simples que podríamos imaginar.

774
01:09:20,470 --> 01:09:27,240
Por ejemplo, tienes 26 cubos, y así cada cubo

775
01:09:27,240 --> 01:09:30,200
corresponde a la primera letra de una palabra,

776
01:09:30,200 --> 01:09:35,229
pero eso va a resultar en una tabla hash bastante desequilibrada

777
01:09:35,229 --> 01:09:40,979
porque hay muchas menos palabras que comienzan con X que comienza con M, por ejemplo.

778
01:09:40,979 --> 01:09:47,890
Una manera de ir sobre la ortografía es si usted desea obtener toda la funcionalidad de otro hacia abajo,

779
01:09:47,890 --> 01:09:53,240
a continuación, sólo tiene que utilizar una función hash simple para ser capaz de obtener su código que se ejecuta

780
01:09:53,240 --> 01:09:58,650
y después volver atrás y cambiar el tamaño de la tabla hash y la definición.

781
01:09:58,650 --> 01:10:03,430
Hay un montón de recursos en Internet para las funciones hash,

782
01:10:03,430 --> 01:10:08,250
por lo que para este conjunto de procesadores se le permite investigar las funciones de hash en Internet

783
01:10:08,250 --> 01:10:15,560
para algunos consejos e inspiración, siempre y cuando, es imprescindible citar dónde lo obtuvo.

784
01:10:15,560 --> 01:10:22,060
Le invitamos a mirar e interpretar una función hash que usted encuentra en el Internet.

785
01:10:22,060 --> 01:10:27,460
Volver a eso, usted podría ser capaz de ver si alguien utiliza un trie

786
01:10:27,460 --> 01:10:31,700
si su aplicación es más rápida que la tabla hash o no.

787
01:10:31,700 --> 01:10:35,290
Usted puede presentar a la Bolsa de Nueva York varias veces.

788
01:10:35,290 --> 01:10:37,660
Se registrará su entrada más reciente.

789
01:10:37,660 --> 01:10:44,300
Así que tal vez cambie su función de control y luego darse cuenta de que en realidad es mucho más rápido

790
01:10:44,300 --> 01:10:46,780
o mucho más lento que antes.

791
01:10:46,780 --> 01:10:50,960
Eso es un poco de una forma divertida.

792
01:10:50,960 --> 01:10:57,190
Siempre hay uno o dos miembros del personal que tratan de hacer que el diccionario más lento posible,

793
01:10:57,190 --> 01:11:00,210
por lo que siempre es divertido para mirar.

794
01:11:00,210 --> 01:11:07,630
>> El uso para el conjunto de procesadores se ejecuta con un diccionario ortográfico opcional

795
01:11:07,630 --> 01:11:12,840
y a continuación, un archivo de texto obligatorio.

796
01:11:12,840 --> 01:11:18,380
De forma predeterminada cuando se ejecuta abecedario con sólo un archivo de texto y no se especifica un diccionario,

797
01:11:18,380 --> 01:11:24,410
que va a utilizar el archivo de texto diccionario, el grande

798
01:11:24,410 --> 01:11:27,920
en la carpeta cs50/pset5/dictionaries.

799
01:11:27,920 --> 01:11:32,760
Que uno tiene más de 100.000 palabras.

800
01:11:32,760 --> 01:11:37,950
También tienen un pequeño diccionario de palabras que tiene considerablemente menos

801
01:11:37,950 --> 01:11:40,730
CS50 que ha hecho para ti.

802
01:11:40,730 --> 01:11:44,050
Sin embargo, puede muy fácilmente con sólo hacer su propio diccionario

803
01:11:44,050 --> 01:11:47,150
si lo que desea es estar trabajando en pequeños ejemplos -

804
01:11:47,150 --> 01:11:51,140
por ejemplo, si desea utilizar gdb y usted sabe los valores específicos

805
01:11:51,140 --> 01:11:53,560
que desea que la tabla hash para mapear a.

806
01:11:53,560 --> 01:12:00,430
Por lo que sólo puede hacer su propio archivo de texto sólo con BAR, BAZ, FOO, y FOOBAR,

807
01:12:00,430 --> 01:12:04,860
hacen que en un archivo de texto, separe cada uno con los que 1 línea,

808
01:12:04,860 --> 01:12:12,670
y luego hacer su propio archivo de texto que contiene, literalmente, sólo tal vez 1 o 2 palabras

809
01:12:12,670 --> 01:12:15,950
para que usted sepa exactamente lo que el resultado debería ser.

810
01:12:15,950 --> 01:12:21,870
Algunos de los archivos de texto que muestra la Bolsa de Nueva York cuando se ejecuta reto comprobará

811
01:12:21,870 --> 01:12:25,580
son Guerra y Paz y una novela de Jane Austen o algo por el estilo.

812
01:12:25,580 --> 01:12:30,450
Así que cuando estás empezando, es mucho más fácil de hacer sus propios archivos de texto

813
01:12:30,450 --> 01:12:34,160
que contienen sólo un par de palabras, o tal vez 10

814
01:12:34,160 --> 01:12:38,280
por lo que se puede predecir cuál será el resultado debe ser

815
01:12:38,280 --> 01:12:42,880
y luego compárelo con eso, así que más de un ejemplo controlado.

816
01:12:42,880 --> 01:12:45,820
Y ya que estamos tratando con la predicción y el dibujo las cosas,

817
01:12:45,820 --> 01:12:48,690
más quiero animaros a utilizar lápiz y papel

818
01:12:48,690 --> 01:12:50,700
porque es realmente va a ayudar con esto -

819
01:12:50,700 --> 01:12:55,620
dibujar las flechas, cómo la tabla hash o cómo se ve tu trie,

820
01:12:55,620 --> 01:12:57,980
cuando estás liberando algo donde las flechas van,

821
01:12:57,980 --> 01:13:01,730
lo llevas a poco, ve usted ningún enlace desapareciendo

822
01:13:01,730 --> 01:13:05,750
y caer en el abismo de la memoria perdida.

823
01:13:05,750 --> 01:13:11,070
Así que por favor, por favor, trate de sacar las cosas incluso antes de llegar a escribir código abajo.

824
01:13:11,070 --> 01:13:14,520
Dibuja las cosas para que pueda entender cómo las cosas van a trabajar

825
01:13:14,520 --> 01:13:22,750
porque entonces te garantizo que te encuentres a confusiones puntero menos allí.

826
01:13:24,270 --> 01:13:25,910
>> Está bien.

827
01:13:25,910 --> 01:13:28,780
Quiero desearle la mejor de las suertes con este conjunto de procesadores.

828
01:13:28,780 --> 01:13:31,980
Es probablemente el más difícil.

829
01:13:31,980 --> 01:13:40,360
Así que trate de empezar pronto, dibujar las cosas, sacar las cosas, y buena suerte.

830
01:13:40,360 --> 01:13:42,980
Esto era Tutorial 5.

831
01:13:45,160 --> 01:13:47,000
>> [CS50.TV]