1
00:00:00,000 --> 00:00:00,500

2
00:00:00,500 --> 00:00:05,120
[REPRODUCCIÓN DE MÚSICA]

3
00:00:05,120 --> 00:00:12,026

4
00:00:12,026 --> 00:00:12,900
ALTAVOZ 1: De acuerdo.

5
00:00:12,900 --> 00:00:14,600
Todo el mundo la bienvenida de nuevo a la sección.

6
00:00:14,600 --> 00:00:18,660
Espero que todos ustedes estén con éxito
recuperado de su concurso

7
00:00:18,660 --> 00:00:19,510
desde la semana pasada.

8
00:00:19,510 --> 00:00:22,564
Sé que es un poco loco a veces.

9
00:00:22,564 --> 00:00:25,230
Como decía antes, si estás
dentro de la desviación estándar,

10
00:00:25,230 --> 00:00:28,188
realmente no te preocupes por eso, sobre todo
para una sección menos cómodo.

11
00:00:28,188 --> 00:00:30,230
Eso es donde debe estar.

12
00:00:30,230 --> 00:00:32,850
>> Si lo hizo muy bien, entonces impresionante.

13
00:00:32,850 --> 00:00:33,650
Felicitaciones a usted.

14
00:00:33,650 --> 00:00:36,149
Y si usted siente que necesita
un poco más de ayuda, por favor

15
00:00:36,149 --> 00:00:38,140
no dude en llegar
a cualquiera de los TFS.

16
00:00:38,140 --> 00:00:40,030
Todos estamos aquí para ayudar.

17
00:00:40,030 --> 00:00:40,960
>> Es por eso que enseñamos.

18
00:00:40,960 --> 00:00:44,550
Es por eso que estoy aquí todos los lunes para usted
chicos y en la oficina horas los jueves.

19
00:00:44,550 --> 00:00:48,130
Así que por favor no dude en hacérmelo saber
si usted está preocupado acerca de cualquier cosa

20
00:00:48,130 --> 00:00:52,450
o si hay algo en el concurso
que realmente te gustaría abordar.

21
00:00:52,450 --> 00:00:56,940
>> Así que el orden del día de hoy es
todo acerca de las estructuras de datos.

22
00:00:56,940 --> 00:01:01,520
Algunos de éstos son sólo va a ser justo
para ayudarle a familiarizarse con ellas.

23
00:01:01,520 --> 00:01:04,870
¿Alguna vez no puede aplicar
en esta clase.

24
00:01:04,870 --> 00:01:08,690
Algunos de ellos se quiere,
como para su conjunto de procesadores ortografía.

25
00:01:08,690 --> 00:01:11,380
>> Usted tiene su opción
entre tablas hash y tries.

26
00:01:11,380 --> 00:01:13,680
Así que sin duda nos vamos sobre aquellos.

27
00:01:13,680 --> 00:01:18,690
Va a ser, sin duda más de clase
de una sección de alto nivel hoy en día, sin embargo,

28
00:01:18,690 --> 00:01:22,630
porque hay una gran cantidad de ellos, y si
entramos en los detalles de implementación

29
00:01:22,630 --> 00:01:26,490
en todos ellos, que no lo haría
incluso conseguir a través de las listas enlazadas

30
00:01:26,490 --> 00:01:28,520
y tal vez un poco de tablas hash.

31
00:01:28,520 --> 00:01:31,200
>> Así que tengan paciencia conmigo.

32
00:01:31,200 --> 00:01:33,530
No vamos a estar haciendo
tanto de codificación de este tiempo.

33
00:01:33,530 --> 00:01:36,870
Si usted tiene alguna pregunta acerca de ella
o si desea verlo en práctica

34
00:01:36,870 --> 00:01:39,260
o probarlo por ti mismo,
Sin duda, recomiendo

35
00:01:39,260 --> 00:01:44,250
ir a study.cs50.net, que
tiene ejemplos de todos estos.

36
00:01:44,250 --> 00:01:46,400
Tendrá mis presentaciones en PowerPoint
con las notas que nos

37
00:01:46,400 --> 00:01:50,860
tienden a usar, así como algo de programación
ejercicios, sobre todo para las cosas

38
00:01:50,860 --> 00:01:55,250
como listas enlazadas y binario
árboles pilas y señales.

39
00:01:55,250 --> 00:01:59,590
Tan poco nivel más alto, lo que
podría ser bueno para ustedes.

40
00:01:59,590 --> 00:02:01,320
>> Así que con eso, vamos a empezar.

41
00:02:01,320 --> 00:02:03,060
Y también, concursos sí--.

42
00:02:03,060 --> 00:02:06,550
Creo que la mayoría de ustedes que están en
mi sección tiene sus pruebas,

43
00:02:06,550 --> 00:02:12,060
pero nadie viene en o alguna razón usted
no hacerlo, están aquí mismo en la parte delantera.

44
00:02:12,060 --> 00:02:12,740
>> Así vinculado listas.

45
00:02:12,740 --> 00:02:15,650
Sé que este tipo de va
antes de hacer una copia de su cuestionario.

46
00:02:15,650 --> 00:02:17,940
Eso fue la semana anterior
que nos enteramos de esto.

47
00:02:17,940 --> 00:02:21,040
Pero en este caso, sólo tendremos que
ir un poco más en profundidad.

48
00:02:21,040 --> 00:02:25,900
>> ¿Entonces por qué podríamos elegir un
lista enlazada a través de una matriz?

49
00:02:25,900 --> 00:02:27,130
¿Qué los distingue?

50
00:02:27,130 --> 00:02:27,630
¿Sí?

51
00:02:27,630 --> 00:02:30,464
>> AUDIENCIA: Usted puede ampliar una vinculada
listar versus tamaño fijo de una matriz.

52
00:02:30,464 --> 00:02:31,171
ALTAVOZ 1: Derecho.

53
00:02:31,171 --> 00:02:33,970
Una matriz ha fijado tamaño mientras que una
lista enlazada tiene un tamaño variable.

54
00:02:33,970 --> 00:02:36,970
Así que si no sabemos cómo
mucho que queremos almacenar,

55
00:02:36,970 --> 00:02:39,880
una lista enlazada nos da una gran
manera de hacer eso porque podemos simplemente

56
00:02:39,880 --> 00:02:43,730
añadir en otro nodo y añadir en
otro nodo y agregar en otro nodo.

57
00:02:43,730 --> 00:02:45,750
Pero lo que podría ser una solución de compromiso?

58
00:02:45,750 --> 00:02:49,521
¿Alguien recuerda el trade-off
entre matrices y listas enlazadas?

59
00:02:49,521 --> 00:02:50,020
Mmhmm?

60
00:02:50,020 --> 00:02:51,460
>> AUDIENCIA: Usted tiene que
ir a través de todo el camino

61
00:02:51,460 --> 00:02:53,738
a través de la lista enlazada
encontrar un elemento en una lista.

62
00:02:53,738 --> 00:02:55,570
En una matriz, se puede
simplemente encontrar un elemento.

63
00:02:55,570 --> 00:02:56,278
>> ALTAVOZ 1: Derecho.

64
00:02:56,278 --> 00:02:57,120
Así que con arrays--

65
00:02:57,120 --> 00:02:58,500
>> AUDIENCIA: [inaudible].

66
00:02:58,500 --> 00:03:01,090
>> ALTAVOZ 1: Con los arreglos, tenemos
lo que se llama acceso aleatorio.

67
00:03:01,090 --> 00:03:04,820
Significa que si queremos lo que es
nunca el quinto punto de la lista

68
00:03:04,820 --> 00:03:07,230
o el quinto punto de nuestra
matriz, que sólo puede agarrarlo.

69
00:03:07,230 --> 00:03:10,440
Si se trata de una lista enlazada, tenemos
para recorrer, ¿no?

70
00:03:10,440 --> 00:03:14,020
Así que el acceso a un elemento en
una matriz es la constante de tiempo,

71
00:03:14,020 --> 00:03:19,530
mientras que con una lista enlazada que lo haría
más probable es que el tiempo lineal porque a lo mejor

72
00:03:19,530 --> 00:03:21,370
nuestro elemento es todo el camino al final.

73
00:03:21,370 --> 00:03:23,446
Tenemos que buscar a través de todo.

74
00:03:23,446 --> 00:03:25,320
Así, con todos estos datos
estructuras que vamos

75
00:03:25,320 --> 00:03:29,330
a pasar un poco más de tiempo en,
¿cuáles son los puntos positivos y negativos.

76
00:03:29,330 --> 00:03:31,480
¿Cuándo podríamos querer
utilizar uno sobre el otro?

77
00:03:31,480 --> 00:03:34,970
Y eso es algo de la
Lo más grande para llevar.

78
00:03:34,970 --> 00:03:40,140
>> Así que tenemos aquí la
definición de un nodo.

79
00:03:40,140 --> 00:03:43,040
Es como uno de los elementos
nuestra lista enlazada, ¿verdad?

80
00:03:43,040 --> 00:03:46,180
Así que estamos todos familiarizados
con nuestras estructuras typedef,

81
00:03:46,180 --> 00:03:47,980
que nos fuimos en la revisión última vez.

82
00:03:47,980 --> 00:03:53,180
Era básicamente la creación de
otro tipo de datos que podríamos utilizar.

83
00:03:53,180 --> 00:03:57,930
>> Y en este caso, es algún nodo
que se celebrará en algún entero.

84
00:03:57,930 --> 00:04:00,210
Y entonces ¿cuál es la segunda parte aquí?

85
00:04:00,210 --> 00:04:03,192

86
00:04:03,192 --> 00:04:05,677
Cualquier persona?

87
00:04:05,677 --> 00:04:06,680
>> AUDIENCIA: [inaudible].

88
00:04:06,680 --> 00:04:07,020
>> ALTAVOZ 1: Sí.

89
00:04:07,020 --> 00:04:08,400
Es un puntero al siguiente nodo.

90
00:04:08,400 --> 00:04:12,610
Así que esto se debe en realidad estar aquí arriba.

91
00:04:12,610 --> 00:04:18,790
Esto es un puntero del tipo de
nodo a la siguiente cosa.

92
00:04:18,790 --> 00:04:22,410
Y eso es lo que
abarca nuestra nodo.

93
00:04:22,410 --> 00:04:24,060
Enfriar.

94
00:04:24,060 --> 00:04:29,390
>> Muy bien, así que con la búsqueda, ya que estábamos
sólo decir antes de la mano, si estás

95
00:04:29,390 --> 00:04:31,840
ir a buscar a través de,
usted tiene que repetir en realidad

96
00:04:31,840 --> 00:04:33,660
a través de su lista enlazada.

97
00:04:33,660 --> 00:04:38,530
Así que si estamos buscando el número
9, empezaríamos a nuestra cabeza

98
00:04:38,530 --> 00:04:41,520
y que nos señala al principio
de nuestra lista enlazada, ¿verdad?

99
00:04:41,520 --> 00:04:44,600
Y decimos, bien, lo hace
nodo contiene el número 9?

100
00:04:44,600 --> 00:04:45,690
¿No?

101
00:04:45,690 --> 00:04:47,500
>> Muy bien, vaya a la siguiente.

102
00:04:47,500 --> 00:04:48,312
Síguelo.

103
00:04:48,312 --> 00:04:49,520
¿Contiene el número 9?

104
00:04:49,520 --> 00:04:50,570
No.

105
00:04:50,570 --> 00:04:51,550
Siga el siguiente.

106
00:04:51,550 --> 00:04:55,490
>> Así que tenemos que recorrer en realidad
a través de nuestra lista enlazada.

107
00:04:55,490 --> 00:05:00,070
No podemos ir directamente a donde 9 es.

108
00:05:00,070 --> 00:05:05,860
Y si ustedes realmente quiere
ver algunos pseudo-código allá arriba.

109
00:05:05,860 --> 00:05:10,420
Tenemos alguna función de búsqueda aquí
que toma en-- ¿qué se necesita en?

110
00:05:10,420 --> 00:05:13,110

111
00:05:13,110 --> 00:05:14,320
Qué piensas?

112
00:05:14,320 --> 00:05:15,960
Tan fácil uno.

113
00:05:15,960 --> 00:05:17,784
Qué es esto?

114
00:05:17,784 --> 00:05:18,700
AUDIENCIA: [inaudible].

115
00:05:18,700 --> 00:05:20,366
ALTAVOZ 1: El número que estamos buscando.

116
00:05:20,366 --> 00:05:20,980
Derecha?

117
00:05:20,980 --> 00:05:22,875
¿Y qué sería esto correspondería a?

118
00:05:22,875 --> 00:05:25,020
Es un puntero a?

119
00:05:25,020 --> 00:05:26,000
>> AUDIENCIA: Un nodo.

120
00:05:26,000 --> 00:05:28,980
>> ALTAVOZ 1: Un nodo a la lista
que estamos viendo, ¿no?

121
00:05:28,980 --> 00:05:33,700
Así que tenemos algunos nodos son puntero aquí.

122
00:05:33,700 --> 00:05:37,240
Este es un punto que va a
realmente recorrer nuestra lista.

123
00:05:37,240 --> 00:05:39,630
Nos propusimos que igual a la lista
porque eso es sólo

124
00:05:39,630 --> 00:05:44,380
estableciendo que igual a la
comenzar de nuestra lista enlazada.

125
00:05:44,380 --> 00:05:50,660
>> Y si bien no es NULL, mientras que
todavía tenemos cosas en nuestra lista,

126
00:05:50,660 --> 00:05:55,580
comprobar para ver si ese nodo tiene
el número que estamos buscando.

127
00:05:55,580 --> 00:05:57,740
Devuelve verdadero.

128
00:05:57,740 --> 00:06:01,070
De lo contrario, actualizarla, ¿no?

129
00:06:01,070 --> 00:06:04,870
>> Si es NULL, salimos de nuestra
while y return false

130
00:06:04,870 --> 00:06:08,340
porque eso significa que no hemos encontrado.

131
00:06:08,340 --> 00:06:11,048
¿Todo el mundo consigue cómo funciona?

132
00:06:11,048 --> 00:06:11,548
Okay.

133
00:06:11,548 --> 00:06:14,940

134
00:06:14,940 --> 00:06:20,260
>> Así que con la inserción, se
tener tres formas diferentes.

135
00:06:20,260 --> 00:06:25,250
Puede anteponer, puede anexar
y se puede insertar en surtido.

136
00:06:25,250 --> 00:06:28,215
En este caso, estamos
vamos a hacer un prefijo.

137
00:06:28,215 --> 00:06:33,380
¿Alguien sabe cómo los
tres casos pueden ser diferentes?

138
00:06:33,380 --> 00:06:36,920
>> Así que anteponer significa que se pone
que en la parte delantera de su lista.

139
00:06:36,920 --> 00:06:39,770
Así que eso significaría que no importa
lo que su nodo es, no importa

140
00:06:39,770 --> 00:06:43,160
lo que el valor es, vas
para ponerlo aquí delante, ¿de acuerdo?

141
00:06:43,160 --> 00:06:45,160
Va a ser la primera
elemento en su lista.

142
00:06:45,160 --> 00:06:49,510
>> Si anexa que, va
para ir a la parte de atrás de su lista.

143
00:06:49,510 --> 00:06:54,010
Y se insertan en surtidos significa que eres
va a poner realmente en el lugar

144
00:06:54,010 --> 00:06:57,700
donde mantiene su lista enlazada ordenada.

145
00:06:57,700 --> 00:07:00,810
Una vez más, cómo se utiliza
esos y cuando se utiliza

146
00:07:00,810 --> 00:07:02,530
ellos variarán dependiendo de su caso.

147
00:07:02,530 --> 00:07:05,834

148
00:07:05,834 --> 00:07:07,750
Si no necesita
ser ordenados, anteponga tiende

149
00:07:07,750 --> 00:07:10,460
a ser lo que la mayoría de la gente
utilizar porque no lo hace

150
00:07:10,460 --> 00:07:15,680
tener que pasar por toda la lista
para encontrar el final para agregarlo en, ¿verdad?

151
00:07:15,680 --> 00:07:17,720
Usted sólo puede pegarlo directamente.

152
00:07:17,720 --> 00:07:21,930
>> Así que vamos a ir a través de un
inserción 1 en este momento.

153
00:07:21,930 --> 00:07:26,360
Así que una cosa que voy a
Recomiendo altamente a este conjunto de procesadores

154
00:07:26,360 --> 00:07:29,820
es dibujar las cosas, como siempre.

155
00:07:29,820 --> 00:07:35,130
Es muy importante que actualice
sus punteros en el orden correcto

156
00:07:35,130 --> 00:07:38,620
porque si ellos actualizar
un poco fuera de lugar,

157
00:07:38,620 --> 00:07:42,210
usted va a terminar
perder partes de su lista.

158
00:07:42,210 --> 00:07:49,680
>> Así, por ejemplo, en este caso, estamos
contando la cabeza a punto justo a 1.

159
00:07:49,680 --> 00:07:56,070
Si sólo hacemos
sin guardar este 1,

160
00:07:56,070 --> 00:07:58,570
no tenemos idea de lo que
1 debe apuntar a ahora

161
00:07:58,570 --> 00:08:02,490
porque hemos perdido lo que
la cabeza señaló.

162
00:08:02,490 --> 00:08:05,530
Así que una cosa que hay que recordar
cuando estás haciendo un prepend

163
00:08:05,530 --> 00:08:09,630
es salvar lo que el
puntos de la cabeza a la primera,

164
00:08:09,630 --> 00:08:15,210
a continuación, volver a asignar, y luego actualizar
lo que su nuevo nodo debería apuntar.

165
00:08:15,210 --> 00:08:20,870

166
00:08:20,870 --> 00:08:22,560
En este caso, esta es una manera de hacerlo.

167
00:08:22,560 --> 00:08:25,440
>> Así que si hubiéramos hecho así
en el que sólo reasignados cabeza,

168
00:08:25,440 --> 00:08:30,320
perdemos básicamente nuestra
lista completa, ¿no?

169
00:08:30,320 --> 00:08:38,000
Una forma de hacerlo es tener un punto de
siguiente y, a continuación, tener la cabeza a punto 1.

170
00:08:38,000 --> 00:08:42,650
O usted puede hacer algo así como el
el almacenamiento temporal, la cual hablé sobre.

171
00:08:42,650 --> 00:08:45,670
>> Pero la reasignación de su
punteros en el orden correcto

172
00:08:45,670 --> 00:08:48,750
va a ser muy, muy
importante para este conjunto de procesadores.

173
00:08:48,750 --> 00:08:53,140
De lo contrario, usted va a tener un hash
mesa o una oportunidad que sólo va a ser

174
00:08:53,140 --> 00:08:56,014
sólo una parte de las palabras que usted
quieren y luego you're-- mmhmm?

175
00:08:56,014 --> 00:08:58,930
AUDIENCIA: ¿Cuál fue el temporal
Lo almacenamiento que hablabas?

176
00:08:58,930 --> 00:09:00,305
ALTAVOZ 1: El almacenamiento temporal.

177
00:09:00,305 --> 00:09:02,760
Así que, básicamente, otra
manera usted puede hacer esto

178
00:09:02,760 --> 00:09:07,650
se guarde la cabeza de algo, como
almacenarlo la variable temporal.

179
00:09:07,650 --> 00:09:11,250
Asigne a 1 y
a continuación, actualice 1 para señalar

180
00:09:11,250 --> 00:09:13,830
a lo que la cabeza utiliza para apuntar.

181
00:09:13,830 --> 00:09:16,920
De esta manera es obviamente
más elegante, ya que

182
00:09:16,920 --> 00:09:20,770
no necesitan un valor temporal, pero
sólo ofrecer otra manera de hacerlo.

183
00:09:20,770 --> 00:09:23,999

184
00:09:23,999 --> 00:09:25,790
Y que en realidad tienen
algo de código para esto.

185
00:09:25,790 --> 00:09:28,080
Así, por lista enlazada, nos
en realidad tienen algo de código.

186
00:09:28,080 --> 00:09:31,930
Así que insertar aquí, esto se anteponiendo.

187
00:09:31,930 --> 00:09:34,290
Así que esto entra en él a la cabeza.

188
00:09:34,290 --> 00:09:38,820
>> Así que lo primero, es necesario
crear su nuevo nodo, por supuesto,

189
00:09:38,820 --> 00:09:40,790
y compruebe que no NULL.

190
00:09:40,790 --> 00:09:43,250
Siempre bueno.

191
00:09:43,250 --> 00:09:47,840
Y entonces usted necesita para asignar los valores.

192
00:09:47,840 --> 00:09:51,260
Cada vez que se crea un nuevo nodo,
no saben lo que está apuntando a la siguiente,

193
00:09:51,260 --> 00:09:54,560
por lo que desea inicializarlo a NULL.

194
00:09:54,560 --> 00:09:58,760
Si no terminan apuntando a algo
otra cosa, se reasignó y que está bien.

195
00:09:58,760 --> 00:10:00,740
Si es lo primero
en la lista, que necesita

196
00:10:00,740 --> 00:10:04,270
para señalar a NULL porque
ese es el final de la lista.

197
00:10:04,270 --> 00:10:12,410
>> Así que para insertarlo, vemos aquí
se asigna el siguiente valor de nuestro nodo

198
00:10:12,410 --> 00:10:17,380
a ser lo que es la cabeza,
que es lo que teníamos aquí.

199
00:10:17,380 --> 00:10:19,930
Eso es lo que acabamos de hacer.

200
00:10:19,930 --> 00:10:25,820
Y entonces estamos asignando la cabeza a punto
a nuestro nuevo nodo, porque recuerde,

201
00:10:25,820 --> 00:10:31,090
nueva alguna puntero a un nodo,
y eso es exactamente lo que es la cabeza.

202
00:10:31,090 --> 00:10:34,370
Eso es exactamente por eso que
tener esta flecha de acceso.

203
00:10:34,370 --> 00:10:37,030

204
00:10:37,030 --> 00:10:37,530
Fresco?

205
00:10:37,530 --> 00:10:38,130
Mmhmm?

206
00:10:38,130 --> 00:10:41,100
>> AUDIENCIA: ¿Tenemos que
inicializar nuevo junto a NULL en primer lugar,

207
00:10:41,100 --> 00:10:44,240
o podemos simplemente inicializarlo a la cabeza?

208
00:10:44,240 --> 00:10:48,210
>> ALTAVOZ 1: Nuevo próxima
necesita ser NULL para comenzar

209
00:10:48,210 --> 00:10:53,760
porque usted no sabe
donde va a ser.

210
00:10:53,760 --> 00:10:56,100
Además, esto es una especie de
Al igual que un paradigma.

211
00:10:56,100 --> 00:10:59,900
Se configura igual a NULL sólo para hacer
Asegúrese de que todas las bases están cubiertas

212
00:10:59,900 --> 00:11:04,070
antes de hacer cualquier cambio de destino de manera que
usted siempre tiene la garantía de que así será

213
00:11:04,070 --> 00:11:08,880
estar apuntando a un valor específico
frente como un valor de la basura.

214
00:11:08,880 --> 00:11:12,210
Porque, sí, asignamos
nuevo siguiente de forma automática,

215
00:11:12,210 --> 00:11:15,420
pero es más como un
buena práctica inicializarlo

216
00:11:15,420 --> 00:11:19,270
de esa manera y luego reasignar.

217
00:11:19,270 --> 00:11:23,420
>> OK, así doblemente enlazada listas ahora.

218
00:11:23,420 --> 00:11:24,601
¿Qué pensamos?

219
00:11:24,601 --> 00:11:26,350
Lo que es diferente con
doblemente enlazada listas?

220
00:11:26,350 --> 00:11:30,750

221
00:11:30,750 --> 00:11:34,300
>> Así que en nuestras listas enlazadas, podemos
sólo se mueven en una dirección, ¿no?

222
00:11:34,300 --> 00:11:35,270
Sólo tenemos al lado.

223
00:11:35,270 --> 00:11:36,760
Sólo podemos seguir adelante.

224
00:11:36,760 --> 00:11:40,300
>> Con una lista doblemente enlazada,
también podemos mover hacia atrás.

225
00:11:40,300 --> 00:11:44,810
Así que no sólo tenemos la
número que queremos almacenar,

226
00:11:44,810 --> 00:11:50,110
tenemos donde apunta a la siguiente
y en el que sólo venimos.

227
00:11:50,110 --> 00:11:52,865
Así que esto permite
algunos mejor recorrido.

228
00:11:52,865 --> 00:11:56,620

229
00:11:56,620 --> 00:12:01,240
>> Así nodos doblemente enlazados,
muy similar, ¿no?

230
00:12:01,240 --> 00:12:05,000
La única diferencia es que ahora
tener un lado y una anterior.

231
00:12:05,000 --> 00:12:06,235
Es la única diferencia.

232
00:12:06,235 --> 00:12:09,570

233
00:12:09,570 --> 00:12:14,790
>> Así que si tuviéramos que anteponer o append-- nosotros
no tienen ningún código para esto aquí--

234
00:12:14,790 --> 00:12:17,830
pero si usted fuera a tratar de
insertarlo, lo importante

235
00:12:17,830 --> 00:12:19,980
es lo que necesita para hacer
asegurarse de que está asignando

236
00:12:19,980 --> 00:12:23,360
tanto su anterior y su
siguiente puntero correctamente.

237
00:12:23,360 --> 00:12:29,010
Así que en este caso, lo haría
no sólo inicializar siguiente,

238
00:12:29,010 --> 00:12:31,820
inicializar anterior.

239
00:12:31,820 --> 00:12:36,960
Si estamos a la cabeza de la lista,
no sólo hacer que la cabeza igual nueva,

240
00:12:36,960 --> 00:12:41,750
pero debe nuestro nuevo anterior
apuntar a la cabeza, ¿verdad?

241
00:12:41,750 --> 00:12:43,380
>> Esa es la única diferencia.

242
00:12:43,380 --> 00:12:47,200
Y si quieres más práctica con
estos con listas enlazadas, con inserción,

243
00:12:47,200 --> 00:12:49,900
con la supresión, con inserción
en una lista de surtido,

244
00:12:49,900 --> 00:12:52,670
por favor visite study.cs50.net.

245
00:12:52,670 --> 00:12:54,870
Hay un montón de grandes ejercicios.

246
00:12:54,870 --> 00:12:55,870
Lo recomiendo.

247
00:12:55,870 --> 00:12:59,210
Ojalá hubiéramos tenido tiempo para ir a través de ellos
pero hay una gran cantidad de estructuras de datos

248
00:12:59,210 --> 00:13:01,530
conseguir a través.

249
00:13:01,530 --> 00:13:02,650
>> Aceptar, por lo que las tablas hash.

250
00:13:02,650 --> 00:13:07,070
Este es probablemente el más
poco útil para el conjunto de procesadores

251
00:13:07,070 --> 00:13:11,090
aquí porque usted va a ser
la implementación de uno de estos, o un intento.

252
00:13:11,090 --> 00:13:12,200
Me gusta mucho las tablas hash.

253
00:13:12,200 --> 00:13:13,110
Son bastante fresco.

254
00:13:13,110 --> 00:13:17,080
>> Así que, básicamente, lo que
que pasa es una tabla hash

255
00:13:17,080 --> 00:13:22,050
es cuando realmente necesitamos rápida
inserción, eliminación y búsqueda.

256
00:13:22,050 --> 00:13:25,010
Esas son las cosas que estamos
priorizando en una tabla hash.

257
00:13:25,010 --> 00:13:29,500
Pueden ser bastante grande,
pero como veremos con tries,

258
00:13:29,500 --> 00:13:33,040
hay cosas que son mucho más grandes.

259
00:13:33,040 --> 00:13:38,330
>> Pero, básicamente, todo un hash
tabla es una función hash

260
00:13:38,330 --> 00:13:47,215
que te dice que cubo para poner cada uno
de sus datos, cada uno de sus elementos en.

261
00:13:47,215 --> 00:13:51,140
Una forma simple de pensar en una tabla hash
es que es sólo cubos de cosas,

262
00:13:51,140 --> 00:13:51,770
¿verdad?

263
00:13:51,770 --> 00:13:59,720
Así que cuando usted está ordenando las cosas por
como la primera letra de su nombre,

264
00:13:59,720 --> 00:14:01,820
que es algo así como una tabla hash.

265
00:14:01,820 --> 00:14:06,180
>> Así que si yo fuera a grupo de chicos es
en grupos de todo el que de nombre comienza

266
00:14:06,180 --> 00:14:11,670
con A por aquí, o quien sea el cumpleaños
es en enero, febrero, marzo,

267
00:14:11,670 --> 00:14:15,220
lo que sea, que es efectivamente
la creación de una tabla hash.

268
00:14:15,220 --> 00:14:18,120
Es sólo la creación de cubos que
ordenar los elementos en

269
00:14:18,120 --> 00:14:19,520
para que usted pueda encontrarlos más fácil.

270
00:14:19,520 --> 00:14:22,300
Así de esta manera cuando necesito
para encontrar uno de ustedes,

271
00:14:22,300 --> 00:14:24,680
Yo no tengo que buscar
a través de cada uno de sus nombres.

272
00:14:24,680 --> 00:14:29,490
Yo puedo ser como, oh, yo sé que
El cumpleaños de Danielle es en--

273
00:14:29,490 --> 00:14:30,240
AUDIENCIA: --April.

274
00:14:30,240 --> 00:14:30,948
ALTAVOZ 1: abril.

275
00:14:30,948 --> 00:14:33,120
Así que me veo en mi abril
cubo, y con un poco de suerte,

276
00:14:33,120 --> 00:14:38,270
ella será la única en la que hay y
mi tiempo era constante en ese sentido,

277
00:14:38,270 --> 00:14:41,230
mientras que si tengo que buscar
a través de un montón de gente,

278
00:14:41,230 --> 00:14:43,090
que va a tomar mucho más tiempo.

279
00:14:43,090 --> 00:14:45,830
Así tablas hash son realmente sólo cubos.

280
00:14:45,830 --> 00:14:48,630
Una forma sencilla de pensar en ellos.

281
00:14:48,630 --> 00:14:52,930
>> Así que una cosa muy importante sobre
una tabla hash es una función hash.

282
00:14:52,930 --> 00:14:58,140
Así que las cosas que acabo de hablar, al igual que
su primera letra de su nombre

283
00:14:58,140 --> 00:15:01,450
o su mes de cumpleaños,
estas son ideas que

284
00:15:01,450 --> 00:15:03,070
realmente correlacionar a una función hash.

285
00:15:03,070 --> 00:15:08,900
Es sólo una manera de decidir qué
usted balde es EL elemento entra en, ¿de acuerdo?

286
00:15:08,900 --> 00:15:14,850
Así que para este conjunto de procesadores, puede mirar hacia arriba
casi cualquier función hash que desea.

287
00:15:14,850 --> 00:15:16,030
>> No tiene que ser la suya.

288
00:15:16,030 --> 00:15:21,140
Hay algunos realmente fresco fuera
hay que hacer todo tipo de loco matemáticas.

289
00:15:21,140 --> 00:15:25,170
Y si usted desea hacer su
corrector ortográfico súper rápido,

290
00:15:25,170 --> 00:15:27,620
Sin duda,
mirar en uno de esos.

291
00:15:27,620 --> 00:15:32,390
>> Pero también la hay
los simples, como el cómputo

292
00:15:32,390 --> 00:15:39,010
la suma de las palabras, como
cada letra tiene un número.

293
00:15:39,010 --> 00:15:39,940
Calcule la suma.

294
00:15:39,940 --> 00:15:42,230
Que determina el cubo.

295
00:15:42,230 --> 00:15:45,430
También tienen las más fáciles que
son al igual que todos los de un aquí,

296
00:15:45,430 --> 00:15:47,050
todos los de la B es aquí.

297
00:15:47,050 --> 00:15:48,920
Cualquiera de esos.

298
00:15:48,920 --> 00:15:55,770
>> Básicamente, sólo se le dice que
índice de la matriz de su elemento debe entrar.

299
00:15:55,770 --> 00:15:58,690
Sólo decidir el bucket--
todo es una función de hash es.

300
00:15:58,690 --> 00:16:04,180
Así que aquí tenemos un ejemplo que es
sólo la primera letra de la cadena

301
00:16:04,180 --> 00:16:05,900
que me estaba hablando.

302
00:16:05,900 --> 00:16:11,900
>> Así que tienes un poco de hash que es sólo la
primera letra de la cadena de menos A,

303
00:16:11,900 --> 00:16:16,090
que le dará un poco de
número entre 0 y 25.

304
00:16:16,090 --> 00:16:20,790
Y lo que quieres hacer es
asegurarse de que esto representa

305
00:16:20,790 --> 00:16:24,110
el tamaño de su picadillo table--
cuántos cubos hay.

306
00:16:24,110 --> 00:16:25,860
Con muchos de estos
funciones hash, que son

307
00:16:25,860 --> 00:16:31,630
va a ser la devolución de valores que podrían
estar muy por encima del número de cubos

308
00:16:31,630 --> 00:16:33,610
que usted realmente tiene
en su tabla hash,

309
00:16:33,610 --> 00:16:37,240
por lo que necesita para hacer
Seguro y mod por aquellos.

310
00:16:37,240 --> 00:16:42,190
De lo contrario, va a decir,
oh, debe ser en balde 5000

311
00:16:42,190 --> 00:16:46,040
pero sólo tiene 30
cubos en su tabla hash.

312
00:16:46,040 --> 00:16:49,360
Y, por supuesto, todos sabemos que es
va a dar lugar a algunos errores de locos.

313
00:16:49,360 --> 00:16:52,870
Así que asegúrese de mod por el
tamaño de la tabla hash.

314
00:16:52,870 --> 00:16:58,430

315
00:16:58,430 --> 00:16:58,930
Enfriar.

316
00:16:58,930 --> 00:17:00,506
Así colisiones.

317
00:17:00,506 --> 00:17:02,620
¿Están todos bien hasta ahora?

318
00:17:02,620 --> 00:17:03,120
Mmhmm?

319
00:17:03,120 --> 00:17:05,900
>> AUDIENCIA: ¿Por qué se
devolver un valor tan masiva?

320
00:17:05,900 --> 00:17:09,210
>> ALTAVOZ 1: Dependiendo del algoritmo
que su función hash utiliza.

321
00:17:09,210 --> 00:17:12,270
Algunos de ellos lo hará
multiplicación loco.

322
00:17:12,270 --> 00:17:16,270
Y es todo sobre conseguir
una distribución uniforme,

323
00:17:16,270 --> 00:17:18,490
por lo que hacen algunos realmente
locuras a veces.

324
00:17:18,490 --> 00:17:20,960
Eso es todo.

325
00:17:20,960 --> 00:17:22,140
Algo más?

326
00:17:22,140 --> 00:17:22,829
Okay.

327
00:17:22,829 --> 00:17:24,480
>> Así colisiones.

328
00:17:24,480 --> 00:17:29,270
Básicamente, como he dicho antes,
en el mejor de los casos,

329
00:17:29,270 --> 00:17:32,040
cualquier cubo miro en es
va a tener una cosa,

330
00:17:32,040 --> 00:17:34,160
así que no tengo que mirar a todos, ¿verdad?

331
00:17:34,160 --> 00:17:37,040
Yo bien sé que está ahí o es
no, y eso es lo que realmente queremos.

332
00:17:37,040 --> 00:17:43,960
Pero si tenemos decenas de miles de
los puntos de datos y menos de ese número

333
00:17:43,960 --> 00:17:48,700
de cubos, que vamos a tener
colisiones donde finalmente algo

334
00:17:48,700 --> 00:17:54,210
se va a tener que terminar en un
cubo que ya cuenta con un elemento.

335
00:17:54,210 --> 00:17:57,390
>> Así que la pregunta es, ¿qué
Qué hacemos en ese caso?

336
00:17:57,390 --> 00:17:58,480
¿Qué hacemos?

337
00:17:58,480 --> 00:17:59,300
Ya tenemos algo allí?

338
00:17:59,300 --> 00:18:00,060
¿Nos echamos un vistazo?

339
00:18:00,060 --> 00:18:00,700
>> No.

340
00:18:00,700 --> 00:18:01,980
Tenemos que mantener los dos.

341
00:18:01,980 --> 00:18:06,400
Así que la forma en que
suelen hacerlo es lo que?

342
00:18:06,400 --> 00:18:08,400
¿Cuál es la estructura de datos
que acabamos de hablar?

343
00:18:08,400 --> 00:18:09,316
AUDIENCIA: lista Vinculado.

344
00:18:09,316 --> 00:18:10,500
ALTAVOZ 1: Una lista enlazada.

345
00:18:10,500 --> 00:18:16,640
Así que ahora, en lugar de cada uno de estos
cubos sólo tener un elemento,

346
00:18:16,640 --> 00:18:24,020
que va a contener una lista enlazada de
los elementos que fueron ordenada en ella.

347
00:18:24,020 --> 00:18:27,588
Bueno, no todo el mundo clase de esa idea?

348
00:18:27,588 --> 00:18:30,546
Debido a que no podíamos tener una matriz
porque no sabemos cuántas cosas

349
00:18:30,546 --> 00:18:31,730
van a estar ahí.

350
00:18:31,730 --> 00:18:36,540
Una lista enlazada nos permite
tener sólo el número exacto que

351
00:18:36,540 --> 00:18:38,465
se hash en ese cubo, ¿verdad?

352
00:18:38,465 --> 00:18:42,260

353
00:18:42,260 --> 00:18:50,500
>> Así sondeo lineal es
básicamente esta idea--

354
00:18:50,500 --> 00:18:52,300
es una manera de hacer frente a una colisión.

355
00:18:52,300 --> 00:18:58,010
Lo que puede hacer es si, en este
caso, baya fue ordenada en 1

356
00:18:58,010 --> 00:19:01,130
y ya tenemos
algo ahí, sólo

357
00:19:01,130 --> 00:19:04,840
seguir bajando hasta
a encontrar una ranura vacía.

358
00:19:04,840 --> 00:19:06,370
Esa es una manera de manejar la situación.

359
00:19:06,370 --> 00:19:09,020
La otra manera de manejar
que es con lo que acabamos de

360
00:19:09,020 --> 00:19:12,280
called-- el vinculado
lista se llama encadenamiento.

361
00:19:12,280 --> 00:19:20,510
>> Así que esta idea funciona si
su tabla hash usted piensa

362
00:19:20,510 --> 00:19:24,150
es mucho mayor que
su conjunto de datos o si

363
00:19:24,150 --> 00:19:28,870
quieren tratar de minimizar el encadenamiento
hasta que sea absolutamente necesario.

364
00:19:28,870 --> 00:19:34,050
Así que una cosa es lineal
sondeo obviamente significa

365
00:19:34,050 --> 00:19:37,290
que su función hash
no es tan útil

366
00:19:37,290 --> 00:19:42,200
porque vas a terminar con
su función hash, llegando a un punto,

367
00:19:42,200 --> 00:19:46,400
le LINEAL sondea hasta
algún lugar que está disponible.

368
00:19:46,400 --> 00:19:49,670
Pero ahora, por supuesto, cualquier cosa
otra cosa que termina allí,

369
00:19:49,670 --> 00:19:52,050
usted va a tener que
buscar incluso más abajo.

370
00:19:52,050 --> 00:19:55,650
>> Y hay mucho más
expensas de búsqueda que

371
00:19:55,650 --> 00:19:59,820
entra en la introducción de un elemento
en su tabla hash ahora, ¿verdad?

372
00:19:59,820 --> 00:20:05,640
Y ahora cuando vas y tratas de encontrar
baya de nuevo, vas a hash de ella,

373
00:20:05,640 --> 00:20:07,742
y que va a decir,
oh, mira en el cubo 1,

374
00:20:07,742 --> 00:20:09,700
y no va a ser
en cubo 1, por lo que es

375
00:20:09,700 --> 00:20:11,970
va a tener que atravesar
por el resto de estos.

376
00:20:11,970 --> 00:20:17,720
Así que a veces es útil,
pero en la mayoría de los casos,

377
00:20:17,720 --> 00:20:22,660
vamos a decir que
El encadenamiento es lo que quieres hacer.

378
00:20:22,660 --> 00:20:25,520
>> Así que hablamos de esto antes.

379
00:20:25,520 --> 00:20:27,812
Me puse un poco por delante de mí mismo.

380
00:20:27,812 --> 00:20:33,560
Pero el encadenamiento es básicamente que
cada cubo en su tabla hash

381
00:20:33,560 --> 00:20:36,120
es sólo una lista enlazada.

382
00:20:36,120 --> 00:20:39,660
>> Así que de otra manera, o más técnico
manera, pensar en una tabla hash

383
00:20:39,660 --> 00:20:44,490
es que es sólo un arreglo
de las listas enlazadas, que

384
00:20:44,490 --> 00:20:49,330
cuando usted está escribiendo su diccionario
y usted está tratando de cargarlo,

385
00:20:49,330 --> 00:20:52,070
pensar en ello como una
variedad de listas enlazadas

386
00:20:52,070 --> 00:20:54,390
hará que sea mucho más fácil
para inicializar.

387
00:20:54,390 --> 00:20:57,680
>> AUDIENCIA: Así tabla hash
tiene un tamaño predeterminado,

388
00:20:57,680 --> 00:20:58,980
como un [inaudible] de cubos?

389
00:20:58,980 --> 00:20:59,220
>> ALTAVOZ 1: Derecho.

390
00:20:59,220 --> 00:21:01,655
Por lo tanto, tiene un número determinado de
cubos que determine--

391
00:21:01,655 --> 00:21:03,530
que ustedes deben
sentirse libre para jugar.

392
00:21:03,530 --> 00:21:05,269
Puede ser muy bien
a ver qué pasa

393
00:21:05,269 --> 00:21:06,810
a medida que cambia su número de cubos.

394
00:21:06,810 --> 00:21:09,410

395
00:21:09,410 --> 00:21:11,510
Pero sí, tiene una
establecer el número de cubos.

396
00:21:11,510 --> 00:21:15,360
Lo que le permite ajustar como
muchos elementos que usted necesita

397
00:21:15,360 --> 00:21:19,350
es este encadenamiento separado donde
han vinculado las listas en cada cubo.

398
00:21:19,350 --> 00:21:22,850
Esto significa que su tabla hash
será exactamente el tamaño

399
00:21:22,850 --> 00:21:25,440
que usted necesita que sea, ¿no?

400
00:21:25,440 --> 00:21:27,358
Ese es todo el punto de las listas enlazadas.

401
00:21:27,358 --> 00:21:30,850

402
00:21:30,850 --> 00:21:32,480
Enfriar.

403
00:21:32,480 --> 00:21:38,780
>> Así que todo el mundo bien allí?

404
00:21:38,780 --> 00:21:39,801
Bien.

405
00:21:39,801 --> 00:21:40,300
Ah.

406
00:21:40,300 --> 00:21:41,860
¿Qué acaba de suceder?

407
00:21:41,860 --> 00:21:42,960
Realmente ahora.

408
00:21:42,960 --> 00:21:45,250
Supongo que alguien me está matando.

409
00:21:45,250 --> 00:21:52,060
>> Aceptar que vamos a entrar en
tries, que son un poco loco.

410
00:21:52,060 --> 00:21:53,140
Me gusta tablas hash.

411
00:21:53,140 --> 00:21:54,460
Creo que son muy cool.

412
00:21:54,460 --> 00:21:56,710
Tries son frescas, también.

413
00:21:56,710 --> 00:21:59,590
>> Así que ¿alguien recuerda lo que es una oportunidad?

414
00:21:59,590 --> 00:22:01,740
Usted debería haber ido más
brevemente en la conferencia?

415
00:22:01,740 --> 00:22:04,570

416
00:22:04,570 --> 00:22:06,377
¿Te acuerdas de clase de cómo funciona?

417
00:22:06,377 --> 00:22:08,460
AUDIENCIA: Sólo estoy asintiendo
que nos fuimos por encima.

418
00:22:08,460 --> 00:22:09,626
ALTAVOZ 1: Nosotros vamos sobre ella.

419
00:22:09,626 --> 00:22:13,100
Bueno, realmente vamos a ir
sobre ella ahora es lo que estamos diciendo.

420
00:22:13,100 --> 00:22:14,860
>> AUDIENCIA: Eso es para un árbol de recuperación.

421
00:22:14,860 --> 00:22:15,280
>> ALTAVOZ 1: Sí.

422
00:22:15,280 --> 00:22:16,196
Es un árbol de la recuperación.

423
00:22:16,196 --> 00:22:16,960
Impresionante.

424
00:22:16,960 --> 00:22:23,610
Así que una cosa a notar aquí es que nosotros
están mirando a caracteres individuales

425
00:22:23,610 --> 00:22:24,480
aquí, ¿verdad?

426
00:22:24,480 --> 00:22:29,710
>> Así que antes con nuestra función de hash, que
estaban mirando las palabras en su conjunto,

427
00:22:29,710 --> 00:22:32,270
y ahora estamos buscando más
a los personajes, ¿no?

428
00:22:32,270 --> 00:22:38,380
Así que tenemos Maxwell aquí y Mendel.

429
00:22:38,380 --> 00:22:47,840
Así que, básicamente, un try-- una manera de pensar
de esto es que todos los niveles aquí

430
00:22:47,840 --> 00:22:49,000
es una serie de letras.

431
00:22:49,000 --> 00:22:53,310

432
00:22:53,310 --> 00:22:55,790
Así que este es su nodo raíz aquí, ¿verdad?

433
00:22:55,790 --> 00:23:01,980
Esto tiene todos los caracteres de la
alfabeto para el inicio de cada palabra.

434
00:23:01,980 --> 00:23:06,480
>> Y lo que quieres hacer es
por ejemplo, OK, tenemos alguna palabra M.

435
00:23:06,480 --> 00:23:10,590
Vamos a buscar a Maxwell, por lo que
vamos a los puntos M. y M a un todo

436
00:23:10,590 --> 00:23:14,800
otro una matriz en la que cada
palabra, mientras haya

437
00:23:14,800 --> 00:23:17,044
es una palabra que tiene un
como la segunda carta,

438
00:23:17,044 --> 00:23:19,460
siempre y cuando no hay una palabra que
tiene B como la segunda carta,

439
00:23:19,460 --> 00:23:24,630
que tendrá un puntero
ir a algún lado array.

440
00:23:24,630 --> 00:23:29,290
>> Probablemente no es un
palabra que MP algo,

441
00:23:29,290 --> 00:23:32,980
por lo que en la posición P en este
matriz, que sólo sería NULL.

442
00:23:32,980 --> 00:23:38,840
Se diría, está bien, no hay una palabra
que ha seguido de una M P, ¿de acuerdo?

443
00:23:38,840 --> 00:23:43,100
Así que si lo pensamos bien, cada
una de estas cosas más pequeñas

444
00:23:43,100 --> 00:23:47,990
es en realidad uno de ellos
grandes conjuntos de la A a la Z.

445
00:23:47,990 --> 00:23:55,064
Así que lo que podría ser una de las cosas
que es una especie de inconveniente de una oportunidad?

446
00:23:55,064 --> 00:23:56,500
>> AUDIENCIA: Una gran cantidad de memoria.

447
00:23:56,500 --> 00:23:59,940
>> ALTAVOZ 1: Es una tonelada de memoria, ¿verdad?

448
00:23:59,940 --> 00:24:08,750
Cada uno de estos bloques aquí
representa 26 espacios, 26 elemento de la matriz.

449
00:24:08,750 --> 00:24:13,680
Así que intenta conseguir espacio increíblemente pesado.

450
00:24:13,680 --> 00:24:17,100
>> Pero ellos son muy rápidos.

451
00:24:17,100 --> 00:24:22,540
Tan increíblemente rápido, pero
realmente espacio ineficiente.

452
00:24:22,540 --> 00:24:24,810
Tipo de tener que averiguar
a cuál de ellos desea.

453
00:24:24,810 --> 00:24:29,470
Estos son realmente fresco para su conjunto de procesadores,
pero sí tener una gran cantidad de memoria,

454
00:24:29,470 --> 00:24:30,290
por lo que el comercio fuera.

455
00:24:30,290 --> 00:24:31,480
¿Sí?

456
00:24:31,480 --> 00:24:34,300
>> AUDIENCIA: ¿Sería posible
la creación de una oportunidad y luego

457
00:24:34,300 --> 00:24:37,967
una vez que tenga toda la
datos en él que usted need--

458
00:24:37,967 --> 00:24:39,550
No sé si eso tiene sentido.

459
00:24:39,550 --> 00:24:42,200
Me va a deshacer de todo el
Caracteres NULL, pero a continuación,

460
00:24:42,200 --> 00:24:42,910
usted no sería capaz de indexar ellos--

461
00:24:42,910 --> 00:24:43,275
>> ALTAVOZ 1: Usted todavía los necesitan.

462
00:24:43,275 --> 00:24:44,854
>> AUDIENCIA: - de la misma manera cada vez.

463
00:24:44,854 --> 00:24:45,520
ALTAVOZ 1: Sí.

464
00:24:45,520 --> 00:24:50,460
Usted necesita los caracteres NULL para que
Cómo saber si no hay una palabra allí.

465
00:24:50,460 --> 00:24:52,040
Ben no tienes algo que quieres?

466
00:24:52,040 --> 00:24:52,540
Okay.

467
00:24:52,540 --> 00:24:54,581
Muy bien, así que vamos
para ir un poco más

468
00:24:54,581 --> 00:24:58,920
en los detalles técnicos detrás
un tratar de trabajar a través de un ejemplo.

469
00:24:58,920 --> 00:25:01,490
>> Aceptar, por lo que esta es la misma cosa.

470
00:25:01,490 --> 00:25:06,290
Mientras que en una lista enlazada, nuestra principal
tipo de-- ¿cuál es la palabra que quiero? -

471
00:25:06,290 --> 00:25:08,350
como la construcción de bloque era un nodo.

472
00:25:08,350 --> 00:25:12,280
En una oportunidad, también tenemos un nodo,
pero se define de manera diferente.

473
00:25:12,280 --> 00:25:17,000
>> Así que tenemos algunos bool que
representa si una palabra en realidad

474
00:25:17,000 --> 00:25:23,530
existe en esta ubicación, y luego
tenemos algo de variedad aquí-- o más bien,

475
00:25:23,530 --> 00:25:27,840
este es un puntero a una
serie de 27 caracteres.

476
00:25:27,840 --> 00:25:33,339
Y esto es para, en este caso, esta
27-- Estoy seguro de que todos ustedes son como, espero,

477
00:25:33,339 --> 00:25:34,880
hay 26 letras en el alfabeto.

478
00:25:34,880 --> 00:25:36,010
¿Por qué tenemos 27?

479
00:25:36,010 --> 00:25:37,870
>> Así que dependiendo de la
forma de implementar esto,

480
00:25:37,870 --> 00:25:43,240
esto es de un conjunto de procesadores que
permitió apóstrofes.

481
00:25:43,240 --> 00:25:46,010
Así que por eso el uno extra.

482
00:25:46,010 --> 00:25:50,500
También tendrá en algunos
casos, el terminador nulo

483
00:25:50,500 --> 00:25:53,230
se incluye como una de las
personajes que prohibe ser,

484
00:25:53,230 --> 00:25:56,120
y eso es lo que verifican
ver si es el final de la palabra.

485
00:25:56,120 --> 00:26:01,340
Si estás interesado, visita
Vídeo de Kevin en study.cs50,

486
00:26:01,340 --> 00:26:04,790
así como Wikipedia tiene
algunos buenos recursos allí.

487
00:26:04,790 --> 00:26:09,000
>> Pero vamos a ir a través de sólo un poco
de cómo se puede trabajar a través de un try

488
00:26:09,000 --> 00:26:11,010
si te dan una.

489
00:26:11,010 --> 00:26:16,230
Así que tenemos un super sencillo aquí que
tiene la palabra "bat" y "zoom" en ellos.

490
00:26:16,230 --> 00:26:18,920
Y como vemos aquí,
este pequeño espacio aquí

491
00:26:18,920 --> 00:26:22,560
representa nuestra bool que
dice, sí, esta es una palabra.

492
00:26:22,560 --> 00:26:27,060
Y entonces esto tiene nuestra
matrices de caracteres, ¿no?

493
00:26:27,060 --> 00:26:33,480
>> Así que vamos a ir a través de
la búsqueda de "murciélago" en este intento.

494
00:26:33,480 --> 00:26:38,340
Así que comience por la parte superior, a la derecha?

495
00:26:38,340 --> 00:26:46,290
Y sabemos que B corresponde a
el segundo índice, el segundo elemento

496
00:26:46,290 --> 00:26:47,840
en esta matriz, debido a y b.

497
00:26:47,840 --> 00:26:51,340
Así que aproximadamente el segundo.

498
00:26:51,340 --> 00:26:58,820
>> Y dice, bien, fresco, se sigue que en
la siguiente matriz, ya que si recordamos,

499
00:26:58,820 --> 00:27:02,160
no es que cada uno de estos
en realidad contiene el elemento.

500
00:27:02,160 --> 00:27:07,110
Cada una de estas matrices
contiene un puntero, ¿verdad?

501
00:27:07,110 --> 00:27:10,030
Es una distinción importante que hacer.

502
00:27:10,030 --> 00:27:13,450
>> Sé que esto va a ser: tries son
muy difícil de conseguir en la primera vez,

503
00:27:13,450 --> 00:27:15,241
por lo que incluso si este es el
segunda o tercera vez

504
00:27:15,241 --> 00:27:18,370
y es todavía tipo
de parecer difícil,

505
00:27:18,370 --> 00:27:21,199
Te prometo que si vas reloj
la mañana de nuevo a corto,

506
00:27:21,199 --> 00:27:22,740
es probable que va a hacer mucho más sentido.

507
00:27:22,740 --> 00:27:23,890
Se necesita mucho para digerir.

508
00:27:23,890 --> 00:27:27,800
Todavía a veces soy
como, espera, lo que es una oportunidad?

509
00:27:27,800 --> 00:27:29,080
¿Cómo utilizo esto?

510
00:27:29,080 --> 00:27:33,880
>> Así que hemos B en este caso,
que es nuestro segundo índice.

511
00:27:33,880 --> 00:27:40,240
Si tuviéramos, por ejemplo, o c
d o cualquier otra letra,

512
00:27:40,240 --> 00:27:45,810
tenemos que mapear que volver al índice
de nuestra matriz que que corresponde a.

513
00:27:45,810 --> 00:27:56,930
Así que tomaríamos como rchar y sólo
restar de una a Localizar en un mapa en 0 a 25.

514
00:27:56,930 --> 00:27:58,728
Todo el mundo bien cómo
mapear nuestros personajes?

515
00:27:58,728 --> 00:28:00,440
Okay.

516
00:28:00,440 --> 00:28:05,980
>> Así que vamos a la segunda, y que
ver que, sí, no es NULL.

517
00:28:05,980 --> 00:28:07,780
Podemos pasar a esta nueva matriz.

518
00:28:07,780 --> 00:28:12,300
Así que pasamos a esta próxima serie aquí.

519
00:28:12,300 --> 00:28:15,500
>> Y decimos, bien, ahora nos
que tenga que ver si a es aquí.

520
00:28:15,500 --> 00:28:18,590
Es un valor nulo o lo hace
realmente avanzar?

521
00:28:18,590 --> 00:28:21,880
Así que una se mueve realmente
hacia adelante en esta serie.

522
00:28:21,880 --> 00:28:24,570
Y decimos, OK, t es nuestra última carta.

523
00:28:24,570 --> 00:28:27,580
Así que vamos a la t en el índice.

524
00:28:27,580 --> 00:28:30,120
Y luego nos movemos hacia adelante
porque no hay otro.

525
00:28:30,120 --> 00:28:38,340
Y éste dice básicamente que, sí,
se dice que hay una palabra aquí--

526
00:28:38,340 --> 00:28:41,750
que si usted sigue este
camino, usted ha llegado

527
00:28:41,750 --> 00:28:43,210
en una palabra, que sabemos que es "murciélago".

528
00:28:43,210 --> 00:28:43,800
¿Sí?

529
00:28:43,800 --> 00:28:46,770
>> AUDIENCIA: ¿Es normal tener que
como el índice 0 y luego tener una especie en 1

530
00:28:46,770 --> 00:28:47,660
o para que al final?

531
00:28:47,660 --> 00:28:48,243
>> ALTAVOZ 1: No.

532
00:28:48,243 --> 00:28:55,360
Así que si miramos hacia atrás en nuestra
declaración aquí, es un bool,

533
00:28:55,360 --> 00:28:59,490
por lo que es su propio elemento en su nodo.

534
00:28:59,490 --> 00:29:03,331
Así que no es parte de la matriz.

535
00:29:03,331 --> 00:29:03,830
Enfriar.

536
00:29:03,830 --> 00:29:08,370
Así que cuando terminemos nuestra palabra y estamos
en esta matriz, lo que queremos hacer

537
00:29:08,370 --> 00:29:12,807
es hacer un cheque por esta es una palabra.

538
00:29:12,807 --> 00:29:14,390
Y en este caso, sería volver sí.

539
00:29:14,390 --> 00:29:17,220

540
00:29:17,220 --> 00:29:24,090
>> Así que en ese sentido, sabemos que "zoo" -
que conocemos como seres humanos que "zoo" es una palabra,

541
00:29:24,090 --> 00:29:24,820
¿verdad?

542
00:29:24,820 --> 00:29:28,990
Pero se trate de aquí sería
decir, no, no lo es.

543
00:29:28,990 --> 00:29:33,980
Y diría que debido a que
no han designado como una palabra aquí.

544
00:29:33,980 --> 00:29:40,440
A pesar de que podemos atravesar
a través de esta matriz,

545
00:29:40,440 --> 00:29:43,890
este intento diría que no,
zoológico no está en su diccionario

546
00:29:43,890 --> 00:29:47,070
porque nosotros no tenemos
designada como tal.

547
00:29:47,070 --> 00:29:52,870
>> Así que una manera de hacerlo que--
oh, lo siento, esta.

548
00:29:52,870 --> 00:29:59,450
Así que en este caso, "zoo" no es
una palabra, pero está en nuestro intento.

549
00:29:59,450 --> 00:30:05,690
Pero en éste, decimos que queremos que
introducir la palabra "baño", lo que sucede

550
00:30:05,690 --> 00:30:08,260
es que seguimos through-- b, a, t.

551
00:30:08,260 --> 00:30:11,820
Estamos en esta matriz, y
vamos a buscar h.

552
00:30:11,820 --> 00:30:15,220
>> En este caso, cuando
mirar el puntero en h,

553
00:30:15,220 --> 00:30:17,890
está apuntando a NULL, ¿de acuerdo?

554
00:30:17,890 --> 00:30:20,780
Así que a menos que sea explícitamente
apuntando a otra matriz,

555
00:30:20,780 --> 00:30:25,000
usted asume que todos los punteros
en esta matriz están apuntando a null.

556
00:30:25,000 --> 00:30:28,270
Así pues, en este caso, h está apuntando
para anular lo que no podemos hacer nada,

557
00:30:28,270 --> 00:30:31,540
por lo que también sería volver
falsa, "baño" no es aquí.

558
00:30:31,540 --> 00:30:34,102

559
00:30:34,102 --> 00:30:35,810
Así que ahora estamos en realidad
va a ir a través de

560
00:30:35,810 --> 00:30:39,790
¿cómo podemos realmente decir
que "zoo" es en nuestro intento.

561
00:30:39,790 --> 00:30:42,920
¿Cómo nos insertamos "zoo" en nuestro intento?

562
00:30:42,920 --> 00:30:47,810
Así que de la misma manera que comenzamos con
nuestra lista enlazada, que comienzan en la raíz.

563
00:30:47,810 --> 00:30:50,600
En caso de duda, comience en
la raíz de estas cosas.

564
00:30:50,600 --> 00:30:53,330
>> Y vamos a decir, OK, z.

565
00:30:53,330 --> 00:30:55,650
existe z en esto, y lo hace.

566
00:30:55,650 --> 00:30:58,370
Así que usted está de pasar a
su siguiente serie, ¿de acuerdo?

567
00:30:58,370 --> 00:31:01,482
Y a continuación, en la siguiente,
decimos, bien, sí existe o?

568
00:31:01,482 --> 00:31:03,000
Lo hace.

569
00:31:03,000 --> 00:31:04,330
Esto de nuevo.

570
00:31:04,330 --> 00:31:08,670
>> Y así, en nuestro próximo uno, que hemos dicho,
Aceptar, "zoo" ya existe aquí.

571
00:31:08,670 --> 00:31:12,440
Todo lo que necesitamos hacer es establecer esta igualdad
a la verdadera, que no es una palabra allí.

572
00:31:12,440 --> 00:31:15,260
Si hubieras seguido todo
hasta antes de ese punto,

573
00:31:15,260 --> 00:31:17,030
se trata de una palabra, por lo que sólo
configurarlo igual a tales.

574
00:31:17,030 --> 00:31:17,530
¿Sí?

575
00:31:17,530 --> 00:31:22,550
>> AUDIENCIA: Entonces sí que
significa que "ba" es una palabra también?

576
00:31:22,550 --> 00:31:24,120
>> ALTAVOZ 1: No.

577
00:31:24,120 --> 00:31:28,870
Así que en este caso, "ba" obtendríamos
aquí, diríamos que es una palabra,

578
00:31:28,870 --> 00:31:31,590
y aún sería no.

579
00:31:31,590 --> 00:31:32,822
¿De acuerdo?

580
00:31:32,822 --> 00:31:33,740
Mmhmm?

581
00:31:33,740 --> 00:31:36,360
>> AUDIENCIA: Así que una vez que se trata de una
palabra y dice que sí, entonces

582
00:31:36,360 --> 00:31:38,380
contendrá ir al m?

583
00:31:38,380 --> 00:31:42,260
>> ALTAVOZ 1: Así que esto tiene que ver
con-- va a cargar esto en.

584
00:31:42,260 --> 00:31:43,640
Usted dice "zoo" es una palabra.

585
00:31:43,640 --> 00:31:47,020
Cuando usted va a check--
como, digamos que usted quiere decir,

586
00:31:47,020 --> 00:31:49,400
existe "zoo" en este diccionario?

587
00:31:49,400 --> 00:31:54,200
Sólo vas a buscar "zoológico"
y después comprobar para ver si se trata de una palabra.

588
00:31:54,200 --> 00:31:57,291
Nunca vas a moverse
a través de m porque eso no es

589
00:31:57,291 --> 00:31:58,290
lo que estás buscando.

590
00:31:58,290 --> 00:32:02,690

591
00:32:02,690 --> 00:32:08,070
>> Así que si realmente queríamos
añadir "baño" en este intento,

592
00:32:08,070 --> 00:32:11,390
que íbamos a hacer lo mismo
como lo hicimos con "zoo"

593
00:32:11,390 --> 00:32:15,380
excepto veríamos que cuando nos
tratar de llegar a h, que no existe.

594
00:32:15,380 --> 00:32:20,090
Así que usted puede pensar en esto como tratando
para agregar un nuevo nodo en una lista enlazada,

595
00:32:20,090 --> 00:32:27,210
por lo que tendríamos que añadir otro
una de estas matrices, como tal.

596
00:32:27,210 --> 00:32:35,670
Y entonces lo que hacemos es apenas fijamos el h
elemento de esta matriz que apunta a esto.

597
00:32:35,670 --> 00:32:39,430
>> Y entonces, ¿qué íbamos a querer hacer aquí?

598
00:32:39,430 --> 00:32:43,110
Añádelo igual a verdadero
porque es una palabra.

599
00:32:43,110 --> 00:32:46,350

600
00:32:46,350 --> 00:32:48,150
Enfriar.

601
00:32:48,150 --> 00:32:48,700
Lo sé.

602
00:32:48,700 --> 00:32:51,170
Intentos no son las más emocionantes.

603
00:32:51,170 --> 00:32:54,250
Confía en mí, lo sé.

604
00:32:54,250 --> 00:32:58,040
>> Así que una cosa que se da cuenta con tries,
Yo dije, son muy eficientes.

605
00:32:58,040 --> 00:33:00,080
Así que hemos visto que
llevar hasta una tonelada de espacio.

606
00:33:00,080 --> 00:33:01,370
Están un poco confuso.

607
00:33:01,370 --> 00:33:03,367
Así que ¿por qué habríamos nunca utilizar estos?

608
00:33:03,367 --> 00:33:05,450
Utilizamos estos porque son
increíblemente eficiente.

609
00:33:05,450 --> 00:33:08,130
>> Así que si estás buscando alguna vez
una palabra, usted es sólo

610
00:33:08,130 --> 00:33:10,450
limitada por la longitud de la palabra.

611
00:33:10,450 --> 00:33:15,210
Así que si usted está buscando un
palabra que tiene una longitud de cinco,

612
00:33:15,210 --> 00:33:20,940
usted está solo nunca va a tener que
hacer en la mayoría de los cinco comparaciones, ¿de acuerdo?

613
00:33:20,940 --> 00:33:25,780
Por lo tanto, hace que sea básicamente una constante.

614
00:33:25,780 --> 00:33:29,150
Al igual que la inserción y búsqueda
son básicamente constante de tiempo.

615
00:33:29,150 --> 00:33:33,750
>> Así que si alguna vez se puede obtener
algo en el tiempo constante,

616
00:33:33,750 --> 00:33:35,150
eso es tan bueno como se pone.

617
00:33:35,150 --> 00:33:37,990
No puede ser mejor que
constante de tiempo para estas cosas.

618
00:33:37,990 --> 00:33:43,150
Así que ese es uno de los
enormes ventajas de intentos.

619
00:33:43,150 --> 00:33:46,780
>> Pero es un montón de espacio.

620
00:33:46,780 --> 00:33:50,380
Así que tipo de tener que decidir
lo que es más importante para ti.

621
00:33:50,380 --> 00:33:54,700
Y en los ordenadores de hoy en día, la
espacio que una oportunidad puede tomar hasta

622
00:33:54,700 --> 00:33:57,740
tal vez no afecta
que mucho, pero tal vez

623
00:33:57,740 --> 00:34:01,350
usted está tratando con algo
que tiene mucho, mucho más las cosas,

624
00:34:01,350 --> 00:34:02,810
y una oportunidad simplemente no es razonable.

625
00:34:02,810 --> 00:34:03,000
¿Sí?

626
00:34:03,000 --> 00:34:05,610
>> AUDIENCIA: Espere, por lo que tiene 26
letras en cada uno?

627
00:34:05,610 --> 00:34:07,440
>> ALTAVOZ 1: Mmhmm.

628
00:34:07,440 --> 00:34:08,570
Sí, usted tiene 26.

629
00:34:08,570 --> 00:34:16,984
Usted tiene algunos es marcador de palabra y después
usted tiene 26 punteros en cada uno.

630
00:34:16,984 --> 00:34:17,775
Y están point--

631
00:34:17,775 --> 00:34:20,280
>> AUDIENCIA: Y cada 26,
es lo que cada uno tiene 26?

632
00:34:20,280 --> 00:34:21,500
>> ALTAVOZ 1: Sí.

633
00:34:21,500 --> 00:34:27,460
Y es por eso, que pueda
ver, se expande muy rápidamente.

634
00:34:27,460 --> 00:34:28,130
Bien.

635
00:34:28,130 --> 00:34:32,524
Así que vamos a entrar en los árboles, que
Me siento como es más fácil y probablemente

636
00:34:32,524 --> 00:34:36,150
ser un pequeño respiro
de tries allí.

637
00:34:36,150 --> 00:34:39,620
Así que espero que la mayoría de ustedes
han visto un árbol antes.

638
00:34:39,620 --> 00:34:41,820
No como el bonito
los exteriores, que yo

639
00:34:41,820 --> 00:34:44,340
no sé si alguien
se fue al aire libre recientemente.

640
00:34:44,340 --> 00:34:49,230
Fui recolección de manzanas este fin de semana,
y, ¡oh, Dios mío, que era preciosa.

641
00:34:49,230 --> 00:34:52,250
Yo no sabía hojas
podría mirar que bonita.

642
00:34:52,250 --> 00:34:53,610
>> Así que esto es sólo un árbol, ¿no?

643
00:34:53,610 --> 00:34:56,790
Es sólo un poco de nodo, y
apunta a un montón de otros nodos.

644
00:34:56,790 --> 00:34:59,570
Como se ve aquí, este es
tipo de un tema recurrente.

645
00:34:59,570 --> 00:35:03,720
Los nodos que apunta a los nodos es una especie de
la esencia de muchas estructuras de datos.

646
00:35:03,720 --> 00:35:06,670
Sólo depende de la forma en que
tienen ellos señalan el uno al otro

647
00:35:06,670 --> 00:35:08,600
y cómo atravesamos
a través de ellos y la forma en que

648
00:35:08,600 --> 00:35:14,500
insertar las cosas que determina
sus diferentes características.

649
00:35:14,500 --> 00:35:17,600
>> Así que sólo algunos de los términos,
que he usado antes.

650
00:35:17,600 --> 00:35:20,010
Así que la raíz es lo que está en la parte superior.

651
00:35:20,010 --> 00:35:21,200
que es donde siempre empezamos.

652
00:35:21,200 --> 00:35:23,610
Usted puede pensar en él como la cabeza también.

653
00:35:23,610 --> 00:35:28,750
Pero para los árboles, tendemos a
se refieren a ella como la raíz.

654
00:35:28,750 --> 00:35:32,820
>> Cualquier cosa en la parte inferior aquí--
en el muy, muy bottom--

655
00:35:32,820 --> 00:35:34,500
son considerados hojas.

656
00:35:34,500 --> 00:35:37,210
Por lo tanto, va de la mano con la
Lo árbol entero, ¿no?

657
00:35:37,210 --> 00:35:39,860
Las hojas son en los bordes de su árbol.

658
00:35:39,860 --> 00:35:45,820
>> Y luego también tenemos un par de
términos para hablar de nodos de relación

659
00:35:45,820 --> 00:35:46,680
el uno al otro.

660
00:35:46,680 --> 00:35:49,700
Así que tenemos los padres,
hijos y hermanos.

661
00:35:49,700 --> 00:35:56,260
Así pues, en este caso, 3 es el
matriz de 5, 6, y 7.

662
00:35:56,260 --> 00:36:00,370
Así que el padre es lo que es
un paso por encima de lo que sea que estés

663
00:36:00,370 --> 00:36:02,940
en referencia a, por lo que sólo
como un árbol genealógico.

664
00:36:02,940 --> 00:36:07,090
Con suerte, esto es todo un poco
poco más intuitivo que los intentos.

665
00:36:07,090 --> 00:36:10,970
>> Los hermanos son cualquiera que tenga
el mismo padre, ¿verdad?

666
00:36:10,970 --> 00:36:13,470
Están en el mismo nivel aquí.

667
00:36:13,470 --> 00:36:16,960
Y entonces, como yo
diciendo, los niños son sólo

668
00:36:16,960 --> 00:36:22,630
lo que es un paso por debajo
el nodo en cuestión, ¿de acuerdo?

669
00:36:22,630 --> 00:36:23,470
Enfriar.

670
00:36:23,470 --> 00:36:25,610
Así, un árbol binario.

671
00:36:25,610 --> 00:36:31,450
¿Alguien puede aventurar una respuesta en uno de
las características del árbol binario?

672
00:36:31,450 --> 00:36:32,770
>> AUDIENCIA: Max dos hojas.

673
00:36:32,770 --> 00:36:33,478
>> ALTAVOZ 1: Derecho.

674
00:36:33,478 --> 00:36:34,640
Así máximo de dos hojas.

675
00:36:34,640 --> 00:36:39,730
Así que en esto antes, tuvimos éste
que tenía tres, pero en un árbol binario,

676
00:36:39,730 --> 00:36:45,000
Tiene un máximo de dos
hijos por los padres, ¿no?

677
00:36:45,000 --> 00:36:46,970
Hay otro
característica interesante.

678
00:36:46,970 --> 00:36:51,550
¿Alguien sabe que?

679
00:36:51,550 --> 00:36:52,620
Árbol binario.

680
00:36:52,620 --> 00:37:00,350
>> Así que un árbol binario tendrá todo
en el-- éste no es sorted--

681
00:37:00,350 --> 00:37:05,320
pero en un árbol binario ordenado,
todo a la derecha

682
00:37:05,320 --> 00:37:08,530
es mayor que la de los padres,
y todo a la izquierda

683
00:37:08,530 --> 00:37:10,035
es menor que la de los padres.

684
00:37:10,035 --> 00:37:15,690
Y eso ha sido un concurso
cuestión que, por lo bueno saber.

685
00:37:15,690 --> 00:37:19,500
Así que la forma en que definimos esto,
una vez más, tenemos otro nodo.

686
00:37:19,500 --> 00:37:21,880
Esto se ve muy similar a lo que?

687
00:37:21,880 --> 00:37:28,336

688
00:37:28,336 --> 00:37:28,836
Doblemente

689
00:37:28,836 --> 00:37:29,320
>> AUDIENCIA: Vinculado listas

690
00:37:29,320 --> 00:37:31,100
>> ALTAVOZ 1: Una lista enlazada doble, ¿no?

691
00:37:31,100 --> 00:37:33,690
Así que si reemplazamos este
con anterior y siguiente,

692
00:37:33,690 --> 00:37:35,670
esto sería una lista doblemente enlazada.

693
00:37:35,670 --> 00:37:40,125
Pero en este caso, en realidad
tener a la izquierda y la derecha y eso es todo.

694
00:37:40,125 --> 00:37:41,500
De lo contrario, es exactamente el mismo.

695
00:37:41,500 --> 00:37:43,374
Todavía tenemos el elemento
que usted está buscando,

696
00:37:43,374 --> 00:37:45,988
y sólo hay dos punteros
ir a lo que se viene.

697
00:37:45,988 --> 00:37:49,210

698
00:37:49,210 --> 00:37:51,870
Sí, así binario árbol de búsqueda.

699
00:37:51,870 --> 00:37:57,665
Si nos damos cuenta, todo en el
aquí es mayor no sea:

700
00:37:57,665 --> 00:37:59,850
o todo inmediatamente
a la derecha aquí

701
00:37:59,850 --> 00:38:02,840
es mayor que, todo
aquí es inferior.

702
00:38:02,840 --> 00:38:06,980

703
00:38:06,980 --> 00:38:14,000
>> Así que si tuviéramos que buscar a través, que
debe mirar muy cerca de búsqueda binaria

704
00:38:14,000 --> 00:38:14,910
aquí, ¿verdad?

705
00:38:14,910 --> 00:38:17,640
Excepto que en vez de mirar
a la mitad de la matriz,

706
00:38:17,640 --> 00:38:21,720
sólo estamos buscando, ya sea en la izquierda
lado o del lado derecho del árbol.

707
00:38:21,720 --> 00:38:24,850
Así que se pone un poco más simple, creo.

708
00:38:24,850 --> 00:38:29,300
>> Así que si su raíz es NULL,
obviamente es sólo falsa.

709
00:38:29,300 --> 00:38:33,470
Y si está allí, obviamente, es la verdad.

710
00:38:33,470 --> 00:38:35,320
Si es menor que, buscamos la izquierda.

711
00:38:35,320 --> 00:38:37,070
Si es mayor que,
buscamos la derecha.

712
00:38:37,070 --> 00:38:39,890
Es exactamente igual que la búsqueda binaria,
sólo una estructura de datos diferente

713
00:38:39,890 --> 00:38:40,600
que estamos usando.

714
00:38:40,600 --> 00:38:42,790
En lugar de una matriz,
es sólo un árbol binario.

715
00:38:42,790 --> 00:38:45,820

716
00:38:45,820 --> 00:38:48,090
>> Aceptar, pilas.

717
00:38:48,090 --> 00:38:51,550
Y también, parece que
podría tener un poco de tiempo.

718
00:38:51,550 --> 00:38:54,460
Si lo hacemos, estoy feliz de ir
sobre cualquiera de esto otra vez.

719
00:38:54,460 --> 00:38:56,856
OK, así que pilas.

720
00:38:56,856 --> 00:39:02,695
¿Alguien recuerda lo que stacks--
cualquier característica de una pila?

721
00:39:02,695 --> 00:39:05,550

722
00:39:05,550 --> 00:39:10,400
>> Aceptar, por lo que la mayoría de nosotros, creo,
comer en el comedor halls--

723
00:39:10,400 --> 00:39:13,100
tanto como es posible que no les gusta.

724
00:39:13,100 --> 00:39:16,900
Pero, obviamente, se puede pensar en una pila
literalmente, al igual que una pila de bandejas

725
00:39:16,900 --> 00:39:18,460
o una pila de cosas.

726
00:39:18,460 --> 00:39:21,820
Y lo que es importante
es darse cuenta de que es

727
00:39:21,820 --> 00:39:26,850
algo-- la característica
que nosotros llamamos por-- es LIFO.

728
00:39:26,850 --> 00:39:28,450
¿Alguien sabe lo que eso representa?

729
00:39:28,450 --> 00:39:29,070
Mmhmm?

730
00:39:29,070 --> 00:39:30,650
>> AUDIENCIA: último en entrar, primero en salir.

731
00:39:30,650 --> 00:39:32,250
>> ALTAVOZ 1: Derecha, último en entrar, primero en salir.

732
00:39:32,250 --> 00:39:36,585
Así que si sabemos, si estamos apilando cosas
arriba, la cosa más fácil de agarrar off--

733
00:39:36,585 --> 00:39:39,570
y tal vez el único que puede tomar
fuera si nuestra pila es grande enough--

734
00:39:39,570 --> 00:39:40,850
es que elemento superior.

735
00:39:40,850 --> 00:39:43,460
Así que cualquier cosa se puso en
last-- como vemos aquí,

736
00:39:43,460 --> 00:39:46,370
lo que fue empujado
en la mayoría recently-- es

737
00:39:46,370 --> 00:39:51,160
va a ser el primero
cosa que nos pop fuera, ¿de acuerdo?

738
00:39:51,160 --> 00:39:56,324
>> Así que lo que tenemos aquí es
otro struct typedef.

739
00:39:56,324 --> 00:39:58,740
Esto es realmente sólo como un
Curso acelerado en la estructura de datos,

740
00:39:58,740 --> 00:40:01,650
así que hay un montón lanzada contra ustedes.

741
00:40:01,650 --> 00:40:02,540
Lo sé.

742
00:40:02,540 --> 00:40:04,970
Así otra struct.

743
00:40:04,970 --> 00:40:06,740
Yay para estructuras.

744
00:40:06,740 --> 00:40:16,660
>> Y en este caso, se trata de algún puntero
a una matriz que tiene una cierta capacidad.

745
00:40:16,660 --> 00:40:20,830
Así que esto representa nuestra pila
aquí, al igual que nuestra gama actual

746
00:40:20,830 --> 00:40:22,520
eso es la celebración de nuestros elementos.

747
00:40:22,520 --> 00:40:24,850
Y entonces aquí tenemos algo de tamaño.

748
00:40:24,850 --> 00:40:31,170
>> Y por lo general, que desea conservar
pista de cuán grande es su pila es

749
00:40:31,170 --> 00:40:36,180
porque lo que va a permitir
usted pueda hacer es si usted sabe el tamaño,

750
00:40:36,180 --> 00:40:39,170
que le permite decir,
Bien, ¿estoy en capacidad?

751
00:40:39,170 --> 00:40:40,570
¿Puedo añadir algo más?

752
00:40:40,570 --> 00:40:44,650
Y también te dice
donde la parte superior de la pila

753
00:40:44,650 --> 00:40:48,180
es por lo que usted sabe lo que
en realidad puede despegar.

754
00:40:48,180 --> 00:40:51,760
Y eso es en realidad va a
ser un poco más claro aquí.

755
00:40:51,760 --> 00:40:57,350
>> Así, por empuje, una cosa, si usted
fueron nunca para aplicar empuje,

756
00:40:57,350 --> 00:41:01,330
como yo estaba diciendo, su
pila tiene un tamaño limitado, ¿verdad?

757
00:41:01,330 --> 00:41:03,990
Nuestra gama tenía alguna capacidad.

758
00:41:03,990 --> 00:41:04,910
Es una matriz.

759
00:41:04,910 --> 00:41:08,930
Es un tamaño fijo, por lo que necesitamos
asegurarse de que no estamos poniendo más

760
00:41:08,930 --> 00:41:11,950
en nuestra gama de lo que
en realidad tienen espacio para.

761
00:41:11,950 --> 00:41:16,900
>> Así que cuando usted está creando un empuje
función, lo primero que haces es decir, OK,

762
00:41:16,900 --> 00:41:18,570
¿tengo espacio en mi pila?

763
00:41:18,570 --> 00:41:23,330
Porque si no lo hago, lo siento,
No puedo guardar el elemento.

764
00:41:23,330 --> 00:41:28,980
Si lo hago, entonces usted desea almacenar
en la parte superior de la pila, ¿no?

765
00:41:28,980 --> 00:41:31,325
>> Y es por eso que tenemos
hacer un seguimiento de nuestro tamaño.

766
00:41:31,325 --> 00:41:35,290
Si no mantenemos un registro de nuestro tamaño,
no sabemos dónde ponerlo.

767
00:41:35,290 --> 00:41:39,035
No sabemos cuántas cosas
están en nuestra gama ya.

768
00:41:39,035 --> 00:41:41,410
Al igual que, obviamente, hay formas
que tal vez usted podría hacerlo.

769
00:41:41,410 --> 00:41:44,610
Usted podría inicializar todo a NULL
y luego comprobar si la última NULL,

770
00:41:44,610 --> 00:41:47,950
pero una cosa mucho más fácil es simplemente
decir, OK, no perder de vista el tamaño.

771
00:41:47,950 --> 00:41:51,840
Al igual que yo sé que tengo cuatro elementos
en mi matriz, por lo que la siguiente cosa

772
00:41:51,840 --> 00:41:55,930
que nos ponemos, estamos
va a almacenar en el índice 4.

773
00:41:55,930 --> 00:42:00,940
Y entonces, por supuesto, esto significa que
usted ha empujado con éxito algo

774
00:42:00,940 --> 00:42:03,320
en su pila,
desee aumentar el tamaño

775
00:42:03,320 --> 00:42:08,880
para que usted sepa donde usted está tan
que usted puede empujar más cosas sobre.

776
00:42:08,880 --> 00:42:12,730
>> Así que si estamos tratando de hacer estallar
algo fuera de la pila,

777
00:42:12,730 --> 00:42:16,072
lo que podría ser la primera cosa
que queremos comprobar?

778
00:42:16,072 --> 00:42:18,030
Usted está tratando de tomar
algo fuera de su pila.

779
00:42:18,030 --> 00:42:21,710

780
00:42:21,710 --> 00:42:24,781
¿Estás seguro de que hay
algo en su pila?

781
00:42:24,781 --> 00:42:25,280
No.

782
00:42:25,280 --> 00:42:26,894
Entonces, ¿qué podríamos querer comprobar?

783
00:42:26,894 --> 00:42:27,810
>> AUDIENCIA: [inaudible].

784
00:42:27,810 --> 00:42:29,880
ALTAVOZ 1: Verifique el tamaño?

785
00:42:29,880 --> 00:42:31,840
Tamaño.

786
00:42:31,840 --> 00:42:38,520
Así que queremos comprobar para ver si
nuestro tamaño es mayor que 0, ¿de acuerdo?

787
00:42:38,520 --> 00:42:44,970
Y si lo es, entonces queremos disminuir
nuestro tamaño por 0 y volver eso.

788
00:42:44,970 --> 00:42:45,840
¿Por qué?

789
00:42:45,840 --> 00:42:49,950
>> En la primera estábamos
empujar, nos empujamos

790
00:42:49,950 --> 00:42:52,460
en tamaño y tamaño entonces actualizado.

791
00:42:52,460 --> 00:42:57,850
En este caso, estamos decrementar el tamaño
y luego quitárselo, desplumado que

792
00:42:57,850 --> 00:42:58,952
de nuestra matriz.

793
00:42:58,952 --> 00:42:59,826
¿Por qué podríamos hacer eso?

794
00:42:59,826 --> 00:43:04,800

795
00:43:04,800 --> 00:43:11,811
Así que si tengo una cosa en mi pila,
lo que sería el tamaño de mi en ese momento?

796
00:43:11,811 --> 00:43:13,140
1.

797
00:43:13,140 --> 00:43:15,180
>> ¿Y dónde está el elemento 1 se almacena?

798
00:43:15,180 --> 00:43:17,621
¿A qué índice?

799
00:43:17,621 --> 00:43:18,120
AUDIENCIA: 0.

800
00:43:18,120 --> 00:43:19,060
ALTAVOZ 1: 0.

801
00:43:19,060 --> 00:43:22,800
Así que en este caso,
Siempre que tenga que hacer sure--

802
00:43:22,800 --> 00:43:27,630
en lugar de regresar
tamaño de menos 1, ya que

803
00:43:27,630 --> 00:43:31,730
sabe que es nuestro elemento
va a ser almacenado en un menor

804
00:43:31,730 --> 00:43:34,705
cualquiera que sea nuestro tamaño es, esta
sólo se ocupa de ella.

805
00:43:34,705 --> 00:43:36,080
Es una manera un poco más elegante.

806
00:43:36,080 --> 00:43:41,220
Y acabamos nuestra decrementamos
tamaño y luego regresar tamaño.

807
00:43:41,220 --> 00:43:42,330
Mmhmm?

808
00:43:42,330 --> 00:43:45,300
>> AUDIENCIA: Creo que sólo en general,
¿por qué esta estructura de datos

809
00:43:45,300 --> 00:43:47,800
ser beneficioso?

810
00:43:47,800 --> 00:43:50,660
>> ALTAVOZ 1: Depende de su contexto.

811
00:43:50,660 --> 00:43:57,420
Así que para algunos de la teoría,
si está trabajando con-- Aceptar,

812
00:43:57,420 --> 00:44:02,750
déjame ver si hay un uno beneficioso
que es beneficioso para más de fuera

813
00:44:02,750 --> 00:44:05,420
de CS.

814
00:44:05,420 --> 00:44:15,780
Con pilas, cualquier momento usted necesita
hacer un seguimiento de algo que

815
00:44:15,780 --> 00:44:20,456
es el más recientemente añadido es cuando
usted va a querer usar una pila.

816
00:44:20,456 --> 00:44:24,770
>> Y no puedo pensar en una buena
ejemplo de eso en este momento.

817
00:44:24,770 --> 00:44:29,955
Pero cada vez que el más reciente
Lo que es más importante para usted,

818
00:44:29,955 --> 00:44:31,705
que es cuando una pila
va a ser de utilidad.

819
00:44:31,705 --> 00:44:35,797

820
00:44:35,797 --> 00:44:39,330
Estoy tratando de pensar si
hay un buen año para esto.

821
00:44:39,330 --> 00:44:43,720
Si pienso en un buen ejemplo en la siguiente
20 minutos, que sin duda le dirá.

822
00:44:43,720 --> 00:44:49,455
>> Pero en general, si hay algo,
como he dicho más, donde más reciente

823
00:44:49,455 --> 00:44:52,470
es más importante, eso es
donde una pila entra en juego.

824
00:44:52,470 --> 00:44:58,860
Mientras que las colas son un poco lo contrario.

825
00:44:58,860 --> 00:44:59,870
Y todos los pequeños perros.

826
00:44:59,870 --> 00:45:00,890
¿No es genial, ¿verdad?

827
00:45:00,890 --> 00:45:03,299
Me siento como que debería
sólo hay un video conejito

828
00:45:03,299 --> 00:45:05,090
justo en el medio de
sección para ustedes

829
00:45:05,090 --> 00:45:08,870
porque esta es una sección intensa.

830
00:45:08,870 --> 00:45:10,480
>> Así que una cola.

831
00:45:10,480 --> 00:45:12,710
Básicamente una cola es como una línea.

832
00:45:12,710 --> 00:45:15,780
Ustedes Estoy seguro de que este uso cotidiano,
al igual que en nuestros comedores.

833
00:45:15,780 --> 00:45:18,160
Así que tenemos que ir en
y tener en nuestras bandejas, estoy

834
00:45:18,160 --> 00:45:21,260
Seguro que tienes que esperar en línea
para deslizar o conseguir su comida.

835
00:45:21,260 --> 00:45:24,650
>> Así que la diferencia aquí
es que esto es FIFO.

836
00:45:24,650 --> 00:45:30,090
Así que si LIFO la última en entrar, primero
cabo, FIFO es primero en entrar, primero en salir.

837
00:45:30,090 --> 00:45:33,400
Así que aquí es donde lo que pones
el primero es el más importante.

838
00:45:33,400 --> 00:45:35,540
Así que si estabas esperando
en un line-- ¿verdad

839
00:45:35,540 --> 00:45:39,130
imagínese si usted fue a
ir a buscar el nuevo iPhone

840
00:45:39,130 --> 00:45:42,800
y era una pila donde el
última persona de la fila lo consiguió en primer lugar,

841
00:45:42,800 --> 00:45:44,160
personas matarían entre sí.

842
00:45:44,160 --> 00:45:49,800
>> Así FIFO, estamos todos muy familiar
con en el mundo real aquí,

843
00:45:49,800 --> 00:45:54,930
y todo tiene que ver con la realidad
especie de recreación de toda esta línea

844
00:45:54,930 --> 00:45:56,900
y colas estructura.

845
00:45:56,900 --> 00:46:02,390
Así que mientras que con la pila,
tenemos empuje y el pop.

846
00:46:02,390 --> 00:46:06,440
Con una cola, tenemos
enqueue y quitar de la cola.

847
00:46:06,440 --> 00:46:10,910
Así que, básicamente, significa enqueue
lo puso en la parte trasera,

848
00:46:10,910 --> 00:46:13,680
y medios dequeue toman
fuera de la parte delantera.

849
00:46:13,680 --> 00:46:18,680
Así que nuestra estructura de datos es un
poco más complicado.

850
00:46:18,680 --> 00:46:21,060
Tenemos un segundo que hay que seguir la pista.

851
00:46:21,060 --> 00:46:25,950
>> Así que sin la cabeza, este
es exactamente una pila, ¿no?

852
00:46:25,950 --> 00:46:27,900
Esta es la misma estructura que una pila.

853
00:46:27,900 --> 00:46:32,480
Lo único diferente es que ahora
tener esta cabeza, que ¿qué te parece

854
00:46:32,480 --> 00:46:34,272
se va a realizar un seguimiento de?

855
00:46:34,272 --> 00:46:35,510
>> AUDIENCIA: El primero.

856
00:46:35,510 --> 00:46:38,685
>> ALTAVOZ 1: Derecho, la
Lo primero que nos pusimos en.

857
00:46:38,685 --> 00:46:41,130
El jefe de nuestra cola.

858
00:46:41,130 --> 00:46:42,240
El que es primero en la fila.

859
00:46:42,240 --> 00:46:45,300

860
00:46:45,300 --> 00:46:49,420
Muy bien, así que si lo hacemos en cola.

861
00:46:49,420 --> 00:46:52,720

862
00:46:52,720 --> 00:46:55,920
Una vez más, con cualquiera de
estas estructuras de datos,

863
00:46:55,920 --> 00:46:59,760
ya que estamos tratando con una matriz,
tenemos que comprobar si tenemos espacio.

864
00:46:59,760 --> 00:47:03,290
>> Esto es algo así como diciéndome
ustedes, si se abre un archivo,

865
00:47:03,290 --> 00:47:04,760
usted necesita para comprobar nula.

866
00:47:04,760 --> 00:47:08,330
Con cualquiera de estas pilas
y las colas, que necesitan

867
00:47:08,330 --> 00:47:13,420
para ver si hay espacio porque somos
tratar con una matriz de tamaño fijo,

868
00:47:13,420 --> 00:47:16,030
como vemos aquí-- 0, 1 todo hasta 5.

869
00:47:16,030 --> 00:47:20,690
Así que lo que hacemos en ese caso es cheque
para ver si todavía tenemos espacio.

870
00:47:20,690 --> 00:47:23,110
Es nuestro tamaño menor que la capacidad?

871
00:47:23,110 --> 00:47:28,480
>> Si es así, tenemos que lo conserve en su
la cola y actualizamos nuestro tamaño.

872
00:47:28,480 --> 00:47:30,250
Entonces, ¿cuál podría ser la cola en este caso?

873
00:47:30,250 --> 00:47:32,360
No está escrito explícitamente.

874
00:47:32,360 --> 00:47:33,380
¿Cómo podríamos almacenarla?

875
00:47:33,380 --> 00:47:34,928
¿Cuál sería la cola?

876
00:47:34,928 --> 00:47:38,600

877
00:47:38,600 --> 00:47:40,190
>> Así que vamos a caminar a través de este ejemplo.

878
00:47:40,190 --> 00:47:44,590
Así que esta es una matriz de tamaño 6, ¿no?

879
00:47:44,590 --> 00:47:49,220
Y tenemos en este momento, nuestro tamaño es 5.

880
00:47:49,220 --> 00:47:55,240
Y cuando lo ponemos en, va
para entrar en el quinto índice, ¿no?

881
00:47:55,240 --> 00:47:57,030
Así que almacenar en la cola.

882
00:47:57,030 --> 00:48:05,600
>> Otra forma de escribir cola haría sólo
sea ​​nuestro arsenal en el índice de tamaño, ¿no?

883
00:48:05,600 --> 00:48:07,560
Este es el tamaño 5.

884
00:48:07,560 --> 00:48:11,490
Lo siguiente que se va a ir a 5.

885
00:48:11,490 --> 00:48:12,296
Fresco?

886
00:48:12,296 --> 00:48:13,290
Okay.

887
00:48:13,290 --> 00:48:16,350
Se pone un poco más complicado
cuando empezamos a jugar con la cabeza.

888
00:48:16,350 --> 00:48:17,060
¿Sí?

889
00:48:17,060 --> 00:48:20,090
>> AUDIENCIA: ¿Significa que tenemos que
habría declarado una matriz que

890
00:48:20,090 --> 00:48:23,880
fue cinco elementos de largo y
entonces estamos añadiendo en él?

891
00:48:23,880 --> 00:48:24,730
>> ALTAVOZ 1: No.

892
00:48:24,730 --> 00:48:27,560
Así pues, en este caso, se trata de una pila.

893
00:48:27,560 --> 00:48:31,760
Este sería declarado
como una matriz de tamaño 6.

894
00:48:31,760 --> 00:48:37,120
Y en este caso,
sólo hay una plaza de izquierda.

895
00:48:37,120 --> 00:48:42,720
>> Aceptar, por lo que una cosa es en este
caso, si nuestra cabeza está en 0,

896
00:48:42,720 --> 00:48:45,270
entonces sólo podemos añadir que en del mismo tamaño.

897
00:48:45,270 --> 00:48:51,020
Pero se pone un poco más complicado
porque en realidad,

898
00:48:51,020 --> 00:48:52,840
no tienen una diapositiva
para esto, así que voy

899
00:48:52,840 --> 00:48:56,670
para dibujar una porque no es
tan sencillo una vez que

900
00:48:56,670 --> 00:48:59,230
empezar a deshacerse de las cosas.

901
00:48:59,230 --> 00:49:03,920
Así que mientras que con una pila
para que sólo tenga

902
00:49:03,920 --> 00:49:08,920
que preocuparse por lo que el tamaño es
cuando va a añadir algo sobre,

903
00:49:08,920 --> 00:49:15,710
con una cola también tiene que hacer
Asegúrese de que su cabeza se contabiliza,

904
00:49:15,710 --> 00:49:20,760
porque una cosa divertida acerca de las colas
es que si usted no está en capacidad,

905
00:49:20,760 --> 00:49:23,040
en realidad se puede hacer que sea envolver alrededor.

906
00:49:23,040 --> 00:49:28,810
>> Aceptar, por lo que uno cosa-- oh,
esto es terrible tiza.

907
00:49:28,810 --> 00:49:31,815
Una cosa a tener en cuenta es el caso.

908
00:49:31,815 --> 00:49:35,514

909
00:49:35,514 --> 00:49:37,140
Haremos sólo cinco.

910
00:49:37,140 --> 00:49:41,810
OK, así que vamos a
dicen que la cabeza está aquí.

911
00:49:41,810 --> 00:49:46,140
Esta es 0, 1, 2, 3, 4.

912
00:49:46,140 --> 00:49:54,210
>> La cabeza está ahí, y
por favor tenga cosas en ellos.

913
00:49:54,210 --> 00:49:58,340
Y queremos añadir algo, ¿no?

914
00:49:58,340 --> 00:50:01,170
Así que lo que necesitamos
saber es que la cabeza es siempre

915
00:50:01,170 --> 00:50:05,620
va a mover de un lado a
entonces bucle alrededor, ¿de acuerdo?

916
00:50:05,620 --> 00:50:10,190
>> Así que esta cola dispone de espacio, ¿no?

917
00:50:10,190 --> 00:50:13,950
Tiene espacio en el principio,
clase de lo contrario de esto.

918
00:50:13,950 --> 00:50:17,920
Así que lo que tenemos que hacer es que
que calcular la cola.

919
00:50:17,920 --> 00:50:20,530
Si usted sabe que su
la cabeza no se ha movido, cola

920
00:50:20,530 --> 00:50:24,630
es sólo su matriz en
el índice del tamaño.

921
00:50:24,630 --> 00:50:30,000
>> Pero en realidad, si usted está utilizando una cola,
su cabeza, probablemente se está actualizando.

922
00:50:30,000 --> 00:50:33,890
Así que lo que hay que hacer es
realmente calcular la cola.

923
00:50:33,890 --> 00:50:39,990
Así que lo que hacemos es la siguiente fórmula
aquí, que voy a dejarte

924
00:50:39,990 --> 00:50:42,680
chicos piensan acerca de, y
entonces vamos a hablar de ello.

925
00:50:42,680 --> 00:50:49,567

926
00:50:49,567 --> 00:50:50,400
Así que esta es la capacidad.

927
00:50:50,400 --> 00:50:55,890

928
00:50:55,890 --> 00:50:59,660
>> Así que esto lo hará realidad
le dará una forma de hacerlo.

929
00:50:59,660 --> 00:51:03,205

930
00:51:03,205 --> 00:51:04,330
Debido a que en este caso, ¿qué?

931
00:51:04,330 --> 00:51:09,205
Nuestra cabeza está en 1, nuestro tamaño es 4.

932
00:51:09,205 --> 00:51:11,760

933
00:51:11,760 --> 00:51:18,490
Si mod que por 5, obtenemos 0,
que es donde debe ingresar la misma.

934
00:51:18,490 --> 00:51:23,320

935
00:51:23,320 --> 00:51:26,080
>> Así que en el siguiente caso,
si tuviéramos que hacer esto,

936
00:51:26,080 --> 00:51:33,390
decimos, OK, vamos a quitar de la cola algo.

937
00:51:33,390 --> 00:51:34,390
Nos dequeue esto.

938
00:51:34,390 --> 00:51:37,740
Tomamos un vistazo a este elemento, ¿no?

939
00:51:37,740 --> 00:51:47,930
>> Y ahora nuestra cabeza está señalando aquí,
y queremos añadir en otra cosa.

940
00:51:47,930 --> 00:51:52,470
Esta es básicamente la
parte de atrás de nuestra línea, ¿verdad?

941
00:51:52,470 --> 00:51:55,450
Las colas pueden envolver alrededor de la matriz.

942
00:51:55,450 --> 00:51:57,310
Esa es una de las principales diferencias.

943
00:51:57,310 --> 00:51:58,780
Pilas, usted no puede hacer esto.

944
00:51:58,780 --> 00:52:01,140
>> Con las colas, se puede
porque todo lo que importa

945
00:52:01,140 --> 00:52:03,940
es que usted sabe lo que
se añadió más recientemente.

946
00:52:03,940 --> 00:52:10,650
Ya que todo va a ser añadido en
esta dirección hacia la izquierda, en este caso,

947
00:52:10,650 --> 00:52:16,480
y luego envolver alrededor, usted puede
seguir poniendo en nuevos elementos

948
00:52:16,480 --> 00:52:18,830
en la parte delantera de la matriz
porque no es realmente

949
00:52:18,830 --> 00:52:20,640
la parte delantera de la matriz más.

950
00:52:20,640 --> 00:52:26,320
Usted puede pensar en el inicio de la
matriz como cuando la cabeza es en realidad.

951
00:52:26,320 --> 00:52:29,710
>> Así que esta fórmula es cómo
calcular su cola.

952
00:52:29,710 --> 00:52:32,780

953
00:52:32,780 --> 00:52:35,610
¿Eso tiene sentido?

954
00:52:35,610 --> 00:52:36,110
Okay.

955
00:52:36,110 --> 00:52:39,400

956
00:52:39,400 --> 00:52:44,040
Aceptar, quitar de la cola, y luego
ustedes tienen 10 minutos

957
00:52:44,040 --> 00:52:48,840
en hacer cualquier preguntas aclaratorias
que quieres, porque sé que es una locura.

958
00:52:48,840 --> 00:52:51,980
>> Muy bien, por lo que en la misma manera--
No sé si ustedes se dio cuenta,

959
00:52:51,980 --> 00:52:53,450
pero CS tiene que ver con los patrones.

960
00:52:53,450 --> 00:52:57,370
Las cosas son más o menos la
mismo, sólo con pequeños retoques.

961
00:52:57,370 --> 00:52:58,950
Así mismo aquí.

962
00:52:58,950 --> 00:53:04,040
Tenemos que comprobar para ver si en realidad
tienen algo en nuestra cola, ¿no?

963
00:53:04,040 --> 00:53:05,960
Diga, OK, es nuestro tamaño mayor que 0?

964
00:53:05,960 --> 00:53:06,730
Enfriar.

965
00:53:06,730 --> 00:53:10,690
>> Si lo hacemos, entonces nos movemos nuestra cabeza, que
es lo que acaba de demostrarse aquí.

966
00:53:10,690 --> 00:53:13,870
Actualizamos nuestra cabeza para ser uno más.

967
00:53:13,870 --> 00:53:18,390
Y luego nos decrementamos nuestra
tamaño y devolver el elemento.

968
00:53:18,390 --> 00:53:21,000

969
00:53:21,000 --> 00:53:26,250
>> Hay mucho más concreto
código en study.cs50.net,

970
00:53:26,250 --> 00:53:29,440
y yo recomiendo ir
a través de él si tienes tiempo,

971
00:53:29,440 --> 00:53:30,980
incluso si es sólo un pseudo-código.

972
00:53:30,980 --> 00:53:35,980
Y si ustedes quieren hablar a través de
que conmigo uno a uno, por favor me deja

973
00:53:35,980 --> 00:53:37,500
saber.

974
00:53:37,500 --> 00:53:38,770
Yo estaría encantado de.

975
00:53:38,770 --> 00:53:42,720
Las estructuras de datos, si
usted toma CS 124, podrás

976
00:53:42,720 --> 00:53:47,830
saben que las estructuras de datos se ponen muy
diversión y esto recién empieza.

977
00:53:47,830 --> 00:53:50,350
>> Así que sé que es difícil.

978
00:53:50,350 --> 00:53:51,300
Está bien.

979
00:53:51,300 --> 00:53:52,410
Luchamos.

980
00:53:52,410 --> 00:53:53,630
Yo todavía lo hago.

981
00:53:53,630 --> 00:53:56,660
Así que no te preocupes demasiado por ello.

982
00:53:56,660 --> 00:54:02,390
>> Pero eso es básicamente su
Curso acelerado en las estructuras de datos.

983
00:54:02,390 --> 00:54:03,400
Sé que es mucho.

984
00:54:03,400 --> 00:54:06,860
¿Hay algo que nos
le gustaría ir otra vez?

985
00:54:06,860 --> 00:54:09,400
Cualquier cosa que queremos hablar a través de?

986
00:54:09,400 --> 00:54:10,060
¿Sí?

987
00:54:10,060 --> 00:54:16,525
>> AUDIENCIA: Para ese ejemplo, por lo que
la nueva cola es a 0 sobre eso?

988
00:54:16,525 --> 00:54:17,150
ALTAVOZ 1: Sí.

989
00:54:17,150 --> 00:54:18,230
AUDIENCIA: OK.

990
00:54:18,230 --> 00:54:24,220
Así que ir a través de,
tendrías 1 más 4 o--

991
00:54:24,220 --> 00:54:27,671
>> ALTAVOZ 1: Por lo que estaban diciendo,
cuando queremos ir a hacer esto otra vez?

992
00:54:27,671 --> 00:54:28,296
AUDIENCIA: Sí.

993
00:54:28,296 --> 00:54:38,290
Así que si estás calculando fuera-- dónde están
que el cálculo de la cola de en eso?

994
00:54:38,290 --> 00:54:44,260
>> ALTAVOZ 1: Así que la cola
Estaba en-- cambié esto.

995
00:54:44,260 --> 00:54:52,010
Así que en este ejemplo aquí, esto era
la matriz que estamos viendo, ¿de acuerdo?

996
00:54:52,010 --> 00:54:54,670
Así que tenemos cosas en 1, 2, 3, y 4.

997
00:54:54,670 --> 00:55:05,850
Así que tenemos nuestra cabeza es igual a 1 en
este punto, y nuestro tamaño es igual a 4

998
00:55:05,850 --> 00:55:07,050
en este punto, ¿no?

999
00:55:07,050 --> 00:55:08,960
>> Usted acepta que todo es el caso?

1000
00:55:08,960 --> 00:55:14,620
Así que hacemos la cabeza, más el tamaño, lo que
nos da 5, y luego nos MOD por 5.

1001
00:55:14,620 --> 00:55:20,690
Obtenemos 0, lo que nos dice que 0 es
¿dónde está nuestra cola, donde tenemos espacio.

1002
00:55:20,690 --> 00:55:22,010
>> AUDIENCIA: ¿Qué es un casquillo?

1003
00:55:22,010 --> 00:55:23,520
>> ALTAVOZ 1: La capacidad.

1004
00:55:23,520 --> 00:55:24,020
Lo siento.

1005
00:55:24,020 --> 00:55:29,640
Así que ese es el tamaño de su arsenal.

1006
00:55:29,640 --> 00:55:35,210

1007
00:55:35,210 --> 00:55:36,047
¿Sí?

1008
00:55:36,047 --> 00:55:39,210
>> AUDIENCIA: [inaudible] antes
volvemos el elemento?

1009
00:55:39,210 --> 00:55:46,270
>> ALTAVOZ 1: Así que movemos el
dirigirse o volver el momento?

1010
00:55:46,270 --> 00:55:52,680
Así que si nos movemos uno, disminuir el tamaño?

1011
00:55:52,680 --> 00:55:54,150
Espere.

1012
00:55:54,150 --> 00:55:55,770
Definitivamente me olvidé otra.

1013
00:55:55,770 --> 00:56:00,646

1014
00:56:00,646 --> 00:56:01,990
No importa.

1015
00:56:01,990 --> 00:56:04,980
No hay otra fórmula.

1016
00:56:04,980 --> 00:56:09,980
Sí, usted quiere volver
la cabeza y luego se movió hacia atrás.

1017
00:56:09,980 --> 00:56:13,270
>> AUDIENCIA: OK, porque en este
punto, la cabeza estaba a 0,

1018
00:56:13,270 --> 00:56:18,452
y luego desea volver
el índice 0 y luego hacer la cabeza 1?

1019
00:56:18,452 --> 00:56:19,870
>> ALTAVOZ 1: Derecho.

1020
00:56:19,870 --> 00:56:22,820
Creo que hay otra
fórmula algo así como esto.

1021
00:56:22,820 --> 00:56:26,970
Yo no lo tengo en la parte superior de mi cabeza como
No quiero darte la equivocada.

1022
00:56:26,970 --> 00:56:35,470
Pero creo que es perfectamente válido
por ejemplo, Aceptar, guarde este element-- lo que sea

1023
00:56:35,470 --> 00:56:40,759
elemento de cabeza es-- decrementar su
tamaño, mover su cabeza otra vez, y el retorno

1024
00:56:40,759 --> 00:56:41,800
cualquiera que sea ese elemento es.

1025
00:56:41,800 --> 00:56:44,760
Eso es perfectamente válido.

1026
00:56:44,760 --> 00:56:45,260
Okay.

1027
00:56:45,260 --> 00:56:48,360

1028
00:56:48,360 --> 00:56:53,560
Siento que esto no es
como el most-- no estás

1029
00:56:53,560 --> 00:56:55,740
va a salir de aquí
como, sí, ya sé intentos.

1030
00:56:55,740 --> 00:56:56,880
Lo tengo todo.

1031
00:56:56,880 --> 00:56:57,670
Eso está bien.

1032
00:56:57,670 --> 00:57:00,200
Prometo.

1033
00:57:00,200 --> 00:57:05,240
Pero las estructuras de datos son algo que
que se necesita una gran cantidad de tiempo para acostumbrarse.

1034
00:57:05,240 --> 00:57:10,010
Probablemente uno de los más difíciles
las cosas, creo que, en el curso.

1035
00:57:10,010 --> 00:57:15,330
>> Así que definitivamente toma
repetición y mirando at-- I

1036
00:57:15,330 --> 00:57:20,050
No sabía realmente listas enlazadas
hasta que me hice demasiado con ellos,

1037
00:57:20,050 --> 00:57:22,550
de la misma manera que no lo hice
realmente entender punteros

1038
00:57:22,550 --> 00:57:27,040
hasta que me he tenido que enseñarla para dos
años y hacer mis propios conjuntos de procesadores con él.

1039
00:57:27,040 --> 00:57:28,990
Se necesita mucho de la reiteración y el tiempo.

1040
00:57:28,990 --> 00:57:32,600
Y, finalmente, será de tipo clic.

1041
00:57:32,600 --> 00:57:36,320
>> Pero mientras tanto, si usted tiene tipo
de una comprensión de alto nivel de lo que

1042
00:57:36,320 --> 00:57:39,321
éstos hacen, sus pros
y que es lo que cons--

1043
00:57:39,321 --> 00:57:41,820
que realmente tienden a enfatizar,
especialmente en el curso de introducción.

1044
00:57:41,820 --> 00:57:45,511
Al igual que, ¿por qué habríamos de utilizar
una oportunidad más de una matriz?

1045
00:57:45,511 --> 00:57:48,010
Al igual que, ¿cuáles son los aspectos positivos
y negativos de cada uno de esos?

1046
00:57:48,010 --> 00:57:51,610
>> Y la comprensión de las ventajas y desventajas
entre cada una de estas estructuras

1047
00:57:51,610 --> 00:57:54,910
es lo que es mucho más importante en este momento.

1048
00:57:54,910 --> 00:57:58,140
Puede haber un loco
o dos preguntas que es

1049
00:57:58,140 --> 00:58:03,710
va a pedir que aplicar empuje o
implementar pop o de puesta en cola y quitar de la cola.

1050
00:58:03,710 --> 00:58:07,340
Pero en su mayor parte, teniendo que
mayor comprensión de nivel y más

1051
00:58:07,340 --> 00:58:09,710
de una comprensión intuitiva es
más importante que en realidad

1052
00:58:09,710 --> 00:58:11,250
ser capaz de ponerlo en práctica.

1053
00:58:11,250 --> 00:58:14,880
>> Sería realmente impresionante si todos ustedes
podría salir e ir implementar un intento,

1054
00:58:14,880 --> 00:58:19,720
pero entendemos que no es necesariamente
lo más razonable en este momento.

1055
00:58:19,720 --> 00:58:23,370
Pero usted puede en su conjunto de procesadores, si quieres
para, a continuación, que obtendrá la práctica,

1056
00:58:23,370 --> 00:58:27,200
y luego tal vez usted
realmente entenderlo.

1057
00:58:27,200 --> 00:58:27,940
¿Sí?

1058
00:58:27,940 --> 00:58:30,440
>> AUDIENCIA: OK, así que cuáles son
nos referimos a utilizar en el conjunto de procesadores?

1059
00:58:30,440 --> 00:58:31,916
¿Tengo que usar uno de ellos?

1060
00:58:31,916 --> 00:58:32,540
ALTAVOZ 1: Sí.

1061
00:58:32,540 --> 00:58:34,199
Así que usted tiene su opción.

1062
00:58:34,199 --> 00:58:36,740
Supongo que en este caso, podemos
hablar del conjunto de procesadores un poco

1063
00:58:36,740 --> 00:58:40,480
porque me encontré a través de estos.

1064
00:58:40,480 --> 00:58:47,779
Así que en su conjunto de procesadores, que tenga su
elección de intentos o tablas hash.

1065
00:58:47,779 --> 00:58:49,570
Algunas personas intentarán
y el uso de filtros de floración,

1066
00:58:49,570 --> 00:58:51,840
pero los que técnicamente no son correctas.

1067
00:58:51,840 --> 00:58:55,804
Debido a su naturaleza probabilística,
dan falsos positivos veces.

1068
00:58:55,804 --> 00:58:57,095
Son mirada fresca en, sin embargo.

1069
00:58:57,095 --> 00:58:59,030
Muy recomendable buscar
en ellos al menos.

1070
00:58:59,030 --> 00:59:03,260
Pero usted tiene su opción
entre una tabla hash y una oportunidad.

1071
00:59:03,260 --> 00:59:06,660
Y eso va a ser donde
se carga en su diccionario.

1072
00:59:06,660 --> 00:59:09,230
>> Y tú tendrás que elegir
su función hash,

1073
00:59:09,230 --> 00:59:13,420
tendrá que elegir el número de
cubos que tiene, y que variará.

1074
00:59:13,420 --> 00:59:17,440
Al igual que si usted tiene más cubos,
tal vez que va a correr más rápido.

1075
00:59:17,440 --> 00:59:22,790
Pero tal vez usted está perdiendo una
gran cantidad de espacio de esa manera, sin embargo.

1076
00:59:22,790 --> 00:59:26,320
Tienes que entenderlo.

1077
00:59:26,320 --> 00:59:27,140
Mmhmm?

1078
00:59:27,140 --> 00:59:29,875
>> AUDIENCIA: Usted dijo antes que
podemos utilizar otras funciones hash,

1079
00:59:29,875 --> 00:59:31,750
que nosotros no tenemos que
crear una función hash?

1080
00:59:31,750 --> 00:59:32,666
>> ALTAVOZ 1: Sí, correcto.

1081
00:59:32,666 --> 00:59:38,150
Así que, literalmente, de su función de control,
como google "función hash"

1082
00:59:38,150 --> 00:59:40,770
y buscar algunos más fresco.

1083
00:59:40,770 --> 00:59:43,250
No se espera construir
sus propias funciones hash.

1084
00:59:43,250 --> 00:59:46,100
La gente pasa su
tesis sobre estas cosas.

1085
00:59:46,100 --> 00:59:50,250
>> Así que no te preocupes por la construcción de su propia.

1086
00:59:50,250 --> 00:59:53,350
Encontrar una línea para empezar.

1087
00:59:53,350 --> 00:59:56,120
Algunos de ellos hay que
manipular un poco

1088
00:59:56,120 --> 00:59:59,430
para hacer tipos de retorno seguro coinciden
y todo eso, así que en principio,

1089
00:59:59,430 --> 01:00:02,420
Yo recomiendo usar algo
muy fácil que tal vez sólo

1090
01:00:02,420 --> 01:00:04,680
hashes en la primera letra.

1091
01:00:04,680 --> 01:00:08,760
Y a continuación, una vez que tenga que trabajar,
la incorporación de una función hash más fresco.

1092
01:00:08,760 --> 01:00:09,260
Mmhmm?

1093
01:00:09,260 --> 01:00:13,020
>> AUDIENCIA: ¿Quieres probar un ser o
eficiente, pero sólo más difícil, como--

1094
01:00:13,020 --> 01:00:15,880
>> ALTAVOZ 1: Así que un intento, creo,
es intuitivamente difícil de implementar

1095
01:00:15,880 --> 01:00:18,310
pero es muy rápido.

1096
01:00:18,310 --> 01:00:20,620
Sin embargo, ocupa más espacio.

1097
01:00:20,620 --> 01:00:25,270
Una vez más, puede optimizar tanto de los de
diferentes maneras y hay maneras a--

1098
01:00:25,270 --> 01:00:26,770
AUDIENCIA: ¿Cómo estamos calificados en esto?

1099
01:00:26,770 --> 01:00:27,540
¿Se matter--

1100
01:00:27,540 --> 01:00:29,164
>> ALTAVOZ 1: Así que tú eres clasifican de manera normal.

1101
01:00:29,164 --> 01:00:31,330
Usted va a ser clasificado en el diseño.

1102
01:00:31,330 --> 01:00:36,020
Sea cual sea la forma en que lo hace, usted quiere
asegúrese de que es tan elegante como puede ser

1103
01:00:36,020 --> 01:00:38,610
y lo más eficiente posible.

1104
01:00:38,610 --> 01:00:41,950
Pero si usted elige un try o hachís
mesa, mientras funciona,

1105
01:00:41,950 --> 01:00:45,350
estamos contentos con eso.

1106
01:00:45,350 --> 01:00:48,370
Y si utiliza algo que hashes
en la primera letra, eso está bien,

1107
01:00:48,370 --> 01:00:51,410
como tal vez como-diseño inteligente.

1108
01:00:51,410 --> 01:00:53,410
También estamos llegando a la
punto en este semester--

1109
01:00:53,410 --> 01:00:55,340
No sé si usted
chicos noticed-- si estás

1110
01:00:55,340 --> 01:00:58,780
grados PSet declinan un poco
debido al diseño y otras cosas,

1111
01:00:58,780 --> 01:00:59,900
que está perfectamente bien.

1112
01:00:59,900 --> 01:01:02,960
Se está haciendo a un punto en que su
los programas son cada vez más complicado.

1113
01:01:02,960 --> 01:01:04,830
Hay más lugares
se puede mejorar.

1114
01:01:04,830 --> 01:01:06,370
>> Así que es perfectamente normal.

1115
01:01:06,370 --> 01:01:08,810
No es que usted es
haciendo peor en su conjunto de procesadores.

1116
01:01:08,810 --> 01:01:11,885
Es sólo que estamos siendo más duro para usted ahora.

1117
01:01:11,885 --> 01:01:13,732
Así que todo el mundo está sintiendo.

1118
01:01:13,732 --> 01:01:14,940
Acabo califiqué todos sus conjuntos de procesadores.

1119
01:01:14,940 --> 01:01:16,490
Sé que todo el mundo está sintiendo.

1120
01:01:16,490 --> 01:01:19,600
>> Así que no te preocupes por eso.

1121
01:01:19,600 --> 01:01:23,580
Y si usted tiene alguna pregunta sobre
conjuntos de procesadores anteriores o maneras en que puede mejorar,

1122
01:01:23,580 --> 01:01:27,760
Trato y comento lo específico
lugares, pero a veces ya es tarde

1123
01:01:27,760 --> 01:01:30,840
y me canso.

1124
01:01:30,840 --> 01:01:34,885
¿Hay otras cosas
sobre estructuras de datos?

1125
01:01:34,885 --> 01:01:37,510
Estoy seguro de que los chicos realmente no
quiero hablar de ellos nunca más,

1126
01:01:37,510 --> 01:01:42,650
pero si hay, estoy feliz de
ir sobre ellos, así como cualquier cosa

1127
01:01:42,650 --> 01:01:45,580
de conferencia el pasado
semana o la semana pasada.

1128
01:01:45,580 --> 01:01:51,580
>> Sé que la semana pasada fue todo examen, por lo que
podemos haber saltado alguna opinión

1129
01:01:51,580 --> 01:01:54,190
de conferencia.

1130
01:01:54,190 --> 01:01:58,230
¿Alguna otra pregunta que puedo responder?

1131
01:01:58,230 --> 01:01:59,350
Bien, bien.

1132
01:01:59,350 --> 01:02:02,400
Bueno, ustedes salir 15 minutos antes.

1133
01:02:02,400 --> 01:02:08,370
>> Espero que esto era semi-útil, al menos,
y voy a ver ustedes la próxima semana,

1134
01:02:08,370 --> 01:02:12,150
o las horas de oficina Jueves.

1135
01:02:12,150 --> 01:02:15,285
¿Hay solicitudes de aperitivos
para la semana que viene, que es la cosa?

1136
01:02:15,285 --> 01:02:17,459
Porque me olvidé de caramelo hoy.

1137
01:02:17,459 --> 01:02:19,750
Y he traído dulces último
semana, pero que era el Día de Colón,

1138
01:02:19,750 --> 01:02:25,400
por lo que no eran como seis personas que
tenía cuatro bolsas de dulces a sí mismos.

1139
01:02:25,400 --> 01:02:28,820
Puedo traer Starbursts
de nuevo si lo desea.

1140
01:02:28,820 --> 01:02:29,580
Starbursts?

1141
01:02:29,580 --> 01:02:32,250
Bien, suena bien.

1142
01:02:32,250 --> 01:02:35,050
Que tengan un buen día, chicos.

1143
01:02:35,050 --> 01:02:39,510