1
00:00:00,000 --> 00:00:03,423
>> [REPRODUCCIÓN DE MÚSICA]

2
00:00:03,423 --> 00:00:05,380

3
00:00:05,380 --> 00:00:08,210
>> ANDI Peng: Bienvenidos a la semana 6 de la sección.

4
00:00:08,210 --> 00:00:11,620
Nos desviamos de nuestro estándar
tiempo de la sección del martes

5
00:00:11,620 --> 00:00:14,130
por la tarde a esta hermosa mañana de domingo.

6
00:00:14,130 --> 00:00:17,330
Gracias por todo el mundo que
me acompañan hoy, pero en serio,

7
00:00:17,330 --> 00:00:18,170
una ronda de aplausos.

8
00:00:18,170 --> 00:00:20,600
>> Esa es una muy grande esfuerzo.

9
00:00:20,600 --> 00:00:23,600
Casi ni siquiera hago
en el tiempo, pero estaba bien.

10
00:00:23,600 --> 00:00:27,520
Así que sé que todos ustedes
simplemente han llegado a la prueba.

11
00:00:27,520 --> 00:00:30,370
En primer lugar, la bienvenida a
la otra cara de eso.

12
00:00:30,370 --> 00:00:32,917
>> En segundo lugar, vamos a hablar sobre ello.

13
00:00:32,917 --> 00:00:34,000
Hablaremos de la prueba.

14
00:00:34,000 --> 00:00:35,700
Hablaremos de cómo
que estás haciendo en la clase.

15
00:00:35,700 --> 00:00:36,550
Estarás bien.

16
00:00:36,550 --> 00:00:39,080
Tengo sus cuestionarios para
que al final de aquí,

17
00:00:39,080 --> 00:00:42,120
así que si ustedes quieren tener
una mirada en ella, totalmente bien.

18
00:00:42,120 --> 00:00:46,590
>> Así que rápidamente antes de comenzar, el
orden del día de hoy es el siguiente.

19
00:00:46,590 --> 00:00:48,430
Como se puede ver, estamos
despido básicamente rápida

20
00:00:48,430 --> 00:00:52,120
a través de un montón de estructuras de datos
muy, muy, muy rápido.

21
00:00:52,120 --> 00:00:54,380
Así que, como tal, no será
hoy muy interactiva.

22
00:00:54,380 --> 00:00:59,620
Sólo será mi clase de gritos
cosas que usted, y si te confundo,

23
00:00:59,620 --> 00:01:02,680
si voy demasiado rápido, que me haga saber.

24
00:01:02,680 --> 00:01:05,200
No son más que diversos datos
estructuras, y como parte

25
00:01:05,200 --> 00:01:07,070
del conjunto de procesadores para este
próxima semana, podrás

26
00:01:07,070 --> 00:01:10,340
se le pregunte para implementar uno de ellos,
quizás dos de ellos-- dos de ellas

27
00:01:10,340 --> 00:01:12,319
en su conjunto de procesadores.

28
00:01:12,319 --> 00:01:14,610
OK, así que sólo voy a
comenzar con algunos anuncios.

29
00:01:14,610 --> 00:01:19,070
Vamos a repasar pilas y colas más en
profundidad que lo que hicimos antes de la prueba.

30
00:01:19,070 --> 00:01:20,990
Vamos a repasar unidos
lista de nuevo, una vez más,

31
00:01:20,990 --> 00:01:23,899
más en profundidad de lo que
que teníamos antes de la prueba.

32
00:01:23,899 --> 00:01:26,440
Y luego hablaremos de hachís
tablas, árboles y tries, que

33
00:01:26,440 --> 00:01:28,890
son todos bastante necesario para su conjunto de procesadores.

34
00:01:28,890 --> 00:01:32,925
Y luego vamos a repasar algunos
consejos útiles para pset5.

35
00:01:32,925 --> 00:01:37,360
>> OK, así que prueba 0.

36
00:01:37,360 --> 00:01:41,090
El promedio fue de un 58%.

37
00:01:41,090 --> 00:01:45,370
Era muy bajo, y así ustedes todo
hizo muy, muy bien, de acuerdo

38
00:01:45,370 --> 00:01:46,510
con ese.

39
00:01:46,510 --> 00:01:49,970
>> Más o menos, regla de oro es que si usted es
dentro de una desviación estándar de la media

40
00:01:49,970 --> 00:01:52,990
sobre todo porque estamos en un menor
sección cómodo, estás totalmente bien.

41
00:01:52,990 --> 00:01:54,120
Usted está en pista.

42
00:01:54,120 --> 00:01:55,190
La vida es buena.

43
00:01:55,190 --> 00:01:58,952
>> Sé que es miedo pensar que
Tengo como un 40% en esta prueba.

44
00:01:58,952 --> 00:02:00,160
Voy a dejar esta clase.

45
00:02:00,160 --> 00:02:02,243
Te lo prometo, no estás
va a fallar la clase.

46
00:02:02,243 --> 00:02:03,680
Usted es totalmente bien.

47
00:02:03,680 --> 00:02:06,850
>> Para aquellos de ustedes que lo superó
la media, impresionante, impresionante,

48
00:02:06,850 --> 00:02:08,780
como, en serio bien hecho.

49
00:02:08,780 --> 00:02:09,689
Los tengo conmigo.

50
00:02:09,689 --> 00:02:11,730
No dude en venir conseguirlos
al final de la sección.

51
00:02:11,730 --> 00:02:14,520
Déjeme saber si usted tiene cualquiera
cuestiones, preguntas con ellas.

52
00:02:14,520 --> 00:02:17,204
Si sumamos su calificación
mal, háganoslo saber.

53
00:02:17,204 --> 00:02:21,240
>> OK, así pset5, esto es una realidad
semana raro para Yale en el sentido

54
00:02:21,240 --> 00:02:24,240
que nuestro conjunto de procesadores se debe
Miércoles al mediodía incluidos

55
00:02:24,240 --> 00:02:27,317
a finales del día, por lo que es en realidad
debido teóricamente Martes al mediodía.

56
00:02:27,317 --> 00:02:29,150
Probablemente nadie terminó
Martes al mediodía.

57
00:02:29,150 --> 00:02:30,830
Eso es totalmente bien.

58
00:02:30,830 --> 00:02:33,700
Vamos a tener horas de oficina
esta noche, así como la noche del lunes.

59
00:02:33,700 --> 00:02:36,810
Y todas las secciones de esta semana lo hará
en realidad convertirse en talleres,

60
00:02:36,810 --> 00:02:38,800
así que siéntete libre para hacer estallar en
cualquier sección que desee,

61
00:02:38,800 --> 00:02:42,810
y van a estar especie de mini-pset
talleres para ayuda en eso.

62
00:02:42,810 --> 00:02:45,620
Así que, como tal, esta es la única sección de
donde estamos material didáctico.

63
00:02:45,620 --> 00:02:49,220
Todas las otras secciones se centrarán
exclusivamente en la ayuda para el conjunto de procesadores.

64
00:02:49,220 --> 00:02:50,146
¿Sí?

65
00:02:50,146 --> 00:02:52,000
>> AUDIENCIA: ¿Dónde están las horas de oficina?

66
00:02:52,000 --> 00:02:56,120
>> ANDI Peng: Las horas de oficina
esta noche-- oh, buena pregunta.

67
00:02:56,120 --> 00:03:00,580
Creo que las horas de oficina esta noche
están en el trullo o al Commons.

68
00:03:00,580 --> 00:03:02,984
Si marca en línea CS50
y usted va a las horas de oficina,

69
00:03:02,984 --> 00:03:05,650
debe haber un horario que
dónde todos ellos son dice.

70
00:03:05,650 --> 00:03:07,954
>> Yo sé bien esta noche
o mañana es trullo,

71
00:03:07,954 --> 00:03:10,120
y creo que podemos tener
bienes comunes de la otra noche.

72
00:03:10,120 --> 00:03:11,020
No estoy seguro.

73
00:03:11,020 --> 00:03:11,700
Buena pregunta.

74
00:03:11,700 --> 00:03:14,430
Compruebe en CS50.

75
00:03:14,430 --> 00:03:18,780
>> Cool, preguntas sobre el
calendario para la próxima como tres días?

76
00:03:18,780 --> 00:03:21,690
Te prometo que ustedes como David
dijo, se trata de la parte superior de la colina.

77
00:03:21,690 --> 00:03:23,050
Ustedes son casi allí.

78
00:03:23,050 --> 00:03:24,644
A sólo tres días más.

79
00:03:24,644 --> 00:03:26,310
Llegar allí, y luego todos nos vendremos abajo.

80
00:03:26,310 --> 00:03:28,114
Vamos a tener un buen descanso CS-libre.

81
00:03:28,114 --> 00:03:28,780
Bienvenido de nuevo.

82
00:03:28,780 --> 00:03:30,779
Nos sumergimos en la web
programación y desarrollo,

83
00:03:30,779 --> 00:03:35,150
cosas que son muy divertido compararon
a algunos de los otros conjuntos de procesadores.

84
00:03:35,150 --> 00:03:37,974
Y va a ser frío y
vamos a tener un montón de diversión.

85
00:03:37,974 --> 00:03:38,890
Tendremos más dulces.

86
00:03:38,890 --> 00:03:39,730
Lo siento por los dulces.

87
00:03:39,730 --> 00:03:40,945
Olvidé dulces.

88
00:03:40,945 --> 00:03:43,310
Era una mañana áspera.

89
00:03:43,310 --> 00:03:46,340
Así que chicos está casi allí,
y estoy muy orgulloso de ustedes.

90
00:03:46,340 --> 00:03:49,570
>> OK, así que apila.

91
00:03:49,570 --> 00:03:53,331
Quién amó a la pregunta acerca de Jack
y su ropa en el concurso?

92
00:03:53,331 --> 00:03:53,830
¿Nadie?

93
00:03:53,830 --> 00:03:56,500
OK eso está bien.

94
00:03:56,500 --> 00:04:00,200
>> Así que, esencialmente como puedas
foto de Jack, este chico aquí,

95
00:04:00,200 --> 00:04:03,350
le encanta tomar la ropa
de la parte superior de la pila,

96
00:04:03,350 --> 00:04:05,750
y se pone de nuevo en
la pila después de que ha hecho.

97
00:04:05,750 --> 00:04:07,600
Así de esta manera, nunca
parece estar cada vez

98
00:04:07,600 --> 00:04:10,090
a la parte inferior de la
apilar en su ropa.

99
00:04:10,090 --> 00:04:12,600
Por lo tanto este tipo de describe
la estructura de datos básica

100
00:04:12,600 --> 00:04:16,610
de cómo se implementa una pila.

101
00:04:16,610 --> 00:04:20,060
>> Esencialmente, pensar en un
apilar como cualquier pila de objetos

102
00:04:20,060 --> 00:04:24,900
donde poner las cosas en la parte superior, y
luego los hace estallar hacia fuera de la parte superior.

103
00:04:24,900 --> 00:04:28,600
Así LIFO es el acrónimo que nos gusta
al servicio- Last In, First Out.

104
00:04:28,600 --> 00:04:32,480
Y así, la última en la parte superior de la
pila es el primero que sale.

105
00:04:32,480 --> 00:04:34,260
Y así los dos términos
nos gusta asociar

106
00:04:34,260 --> 00:04:36,190
con eso que se llama empuje y pop.

107
00:04:36,190 --> 00:04:39,790
Cuando empujas algo sobre la
apilar, y usted hace estallar una copia de seguridad.

108
00:04:39,790 --> 00:04:43,422
>> Así que supongo que esto es una especie de
concepto abstracto para aquellos de ustedes

109
00:04:43,422 --> 00:04:45,630
que quieren ver como un
aplicación real de este

110
00:04:45,630 --> 00:04:46,740
en el mundo real.

111
00:04:46,740 --> 00:04:50,170
¿Cuántos de ustedes han escrito un ensayo
tal vez como una hora antes de que se debió,

112
00:04:50,170 --> 00:04:54,510
y has borrado accidentalmente un enorme
parte de ella, como por accidente?

113
00:04:54,510 --> 00:04:58,560
Y entonces lo mando hacer
que utilizamos para poner de nuevo?

114
00:04:58,560 --> 00:05:00,030
Control-Z, sí?

115
00:05:00,030 --> 00:05:03,640
Control-Z, por lo que la cantidad de veces
que Control-Z ha salvado la vida,

116
00:05:03,640 --> 00:05:08,820
ha salvado el culo, cada vez que
eso es implementado a través de una pila.

117
00:05:08,820 --> 00:05:13,020
>> Esencialmente toda la información
que está en el documento de Word,

118
00:05:13,020 --> 00:05:15,080
que es empujado y se metió en la voluntad.

119
00:05:15,080 --> 00:05:19,460
Y así, en esencia cada vez que
borrar nada, usted hace estallar una copia de seguridad.

120
00:05:19,460 --> 00:05:22,820
Y entonces, si usted lo necesita de nuevo, que
empujarla, que es lo que hace de Control-C.

121
00:05:22,820 --> 00:05:26,770
Y la función mundo tan real
de la estructura de datos de lo simple

122
00:05:26,770 --> 00:05:28,690
puede ayudarle con su vida cotidiana.

123
00:05:28,690 --> 00:05:31,710

124
00:05:31,710 --> 00:05:40,150
>> Así que un struct es la forma en que
que realmente creamos una pila.

125
00:05:40,150 --> 00:05:44,720
Escribimos definir estructura, y luego
lo llamamos la pila en la parte inferior.

126
00:05:44,720 --> 00:05:47,440
Y dentro de la pila,
tenemos dos parámetros

127
00:05:47,440 --> 00:05:51,580
que esencialmente se puede manipular,
así que tenemos carbón capacidad cuerdas estrella.

128
00:05:51,580 --> 00:05:55,150
>> Todo lo que se está haciendo
es la creación de una matriz

129
00:05:55,150 --> 00:05:58,835
que podemos almacenar lo que quieras
el cual podemos determinar su capacidad.

130
00:05:58,835 --> 00:06:01,990
La capacidad es la cantidad máxima de
artículos que se pueden poner en esta matriz.

131
00:06:01,990 --> 00:06:05,660
int size es el contador que mantiene
un registro de cuántos elementos son actualmente

132
00:06:05,660 --> 00:06:07,850
en la pila.

133
00:06:07,850 --> 00:06:11,860
Así entonces podemos perder de vista, A,
tanto lo grande la pila real es,

134
00:06:11,860 --> 00:06:14,850
y, B, cuánto de esa pila
llenamos porque no queremos

135
00:06:14,850 --> 00:06:18,800
a desbordarse sobre lo que nuestra capacidad es.

136
00:06:18,800 --> 00:06:24,340
>> Así, por ejemplo, esta hermosa
pregunta era en su cuestionario.

137
00:06:24,340 --> 00:06:28,160
En esencia, ¿cómo empujamos
en la parte superior de una pila.

138
00:06:28,160 --> 00:06:28,830
Bastante simple.

139
00:06:28,830 --> 00:06:30,621
Si nos fijamos en ella,
vamos a caminar a través de este.

140
00:06:30,621 --> 00:06:32,640
Si [inaudible] size--
recuerde, siempre que

141
00:06:32,640 --> 00:06:35,300
quiere acceder a cualquier
parámetro dentro de una estructura,

142
00:06:35,300 --> 00:06:40,320
lo hace el nombre de la struct.parameter.

143
00:06:40,320 --> 00:06:42,720
>> En este caso, s es
el nombre de nuestro stack.

144
00:06:42,720 --> 00:06:46,230
Queremos acceder el tamaño
de la misma, por lo que hacemos s.size.

145
00:06:46,230 --> 00:06:50,280
Así que, mientras el tamaño no es
igual a la capacidad o tan largo

146
00:06:50,280 --> 00:06:52,940
ya que es menos de la capacidad,
ya sea que trabajar aquí.

147
00:06:52,940 --> 00:06:57,180
>> ¿Quieres acceder al interior
de la pila, por lo s.strings,

148
00:06:57,180 --> 00:07:00,790
y usted va a poner ese nuevo número
que desea insertar en allí.

149
00:07:00,790 --> 00:07:05,030
Digamos que vamos a querer
inserte int n en la pila,

150
00:07:05,030 --> 00:07:08,905
podríamos hacer s.strings,
soportes, s.size es igual a n.

151
00:07:08,905 --> 00:07:11,030
Debido a que el tamaño es donde nos
Actualmente se encuentran en la pila

152
00:07:11,030 --> 00:07:14,590
si vamos a empujar
en, simplemente accedemos

153
00:07:14,590 --> 00:07:17,370
donde el tamaño es, la
plenitud actual de la pila,

154
00:07:17,370 --> 00:07:21,729
y empujamos la int n en la misma.

155
00:07:21,729 --> 00:07:24,770
Y luego queremos asegurarnos de que
también estamos incrementando el tamaño de la n,

156
00:07:24,770 --> 00:07:27,436
para que podamos hacer un seguimiento de que hemos
añade algo extra a la pila.

157
00:07:27,436 --> 00:07:29,660
Ahora tenemos un tamaño mayor.

158
00:07:29,660 --> 00:07:33,196
¿Esto aquí tiene sentido
todo el mundo, ¿cómo lógicamente funciona?

159
00:07:33,196 --> 00:07:34,160
Era una especie de rápido.

160
00:07:34,160 --> 00:07:39,535

161
00:07:39,535 --> 00:07:42,160
AUDIENCIA: ¿Puede ir más
los s.stringss.strings [s.size] de nuevo?

162
00:07:42,160 --> 00:07:45,808
ANDI Peng: Claro, ¿y qué hace
s.size Actualmente darnos?

163
00:07:45,808 --> 00:07:47,440
AUDIENCIA: Es el tamaño actual.

164
00:07:47,440 --> 00:07:50,890
ANDI Peng: Exactamente, por lo que el
índice actual que nuestro tamaño es a,

165
00:07:50,890 --> 00:07:57,780
y por lo que queremos poner el nuevo número entero
que queremos insertar en s.size.

166
00:07:57,780 --> 00:07:58,760
¿Tiene sentido?

167
00:07:58,760 --> 00:08:01,110
Debido s.strings, todo lo que
es es el nombre de la matriz.

168
00:08:01,110 --> 00:08:03,510
Todo lo que es es el acceso a la
matriz dentro de nuestra estructura,

169
00:08:03,510 --> 00:08:06,030
y por lo que si queremos
colocar n en ese índice,

170
00:08:06,030 --> 00:08:09,651
sólo podemos acceder a él
utilizando soportes s.size.

171
00:08:09,651 --> 00:08:10,150
Guay.

172
00:08:10,150 --> 00:08:13,580

173
00:08:13,580 --> 00:08:18,916
>> Muy bien, pop, me Pseudocódigo fuera
para ustedes, sino concepto similar.

174
00:08:18,916 --> 00:08:19,790
¿Tiene sentido?

175
00:08:19,790 --> 00:08:22,310
Si el tamaño es mayor
que cero, entonces usted

176
00:08:22,310 --> 00:08:25,350
sabe que usted quiere tomar algo
porque si el tamaño no es

177
00:08:25,350 --> 00:08:27,620
mayor que cero, entonces usted
no tienen nada en la pila.

178
00:08:27,620 --> 00:08:29,840
>> Por lo que sólo desea ejecutar
este código, sólo puede

179
00:08:29,840 --> 00:08:32,320
pop si hay algo de pop.

180
00:08:32,320 --> 00:08:35,830
Así que si el tamaño es mayor
de 0, tenemos menos el tamaño.

181
00:08:35,830 --> 00:08:40,020
Nos disminuir el tamaño y luego regresamos
lo que hay dentro de ella porque

182
00:08:40,020 --> 00:08:42,710
haciendo estallar, queremos
Acceso todo lo que se almacena

183
00:08:42,710 --> 00:08:45,694
en el índice de la parte superior de la pila.

184
00:08:45,694 --> 00:08:46,610
Todo tiene sentido?

185
00:08:46,610 --> 00:08:49,693
Si te hice chicos escribir esto,
¿Quieres que chicos capaces de escribirlo?

186
00:08:49,693 --> 00:08:52,029

187
00:08:52,029 --> 00:08:53,570
OK, ustedes pueden jugar un rato con él.

188
00:08:53,570 --> 00:08:55,252
No se preocupe si usted no lo entienden.

189
00:08:55,252 --> 00:08:57,460
No tenemos tiempo para codificar
hacia fuera hoy porque hemos

190
00:08:57,460 --> 00:08:59,959
tiene un montón de estas estructuras
que pasar, pero esencialmente

191
00:08:59,959 --> 00:09:02,214
pseudocódigo, muy, muy similar a empujar.

192
00:09:02,214 --> 00:09:03,380
Sólo tienes que seguir a lo largo de la lógica.

193
00:09:03,380 --> 00:09:06,092
Asegúrese de que está accediendo todo el
características de su estructura correctamente.

194
00:09:06,092 --> 00:09:06,574
¿Sí?

195
00:09:06,574 --> 00:09:09,282
>> AUDIENCIA: Will estas diapositivas y
todo esto sea hoy-ish?

196
00:09:09,282 --> 00:09:11,586
ANDI Peng: Siempre, sí.

197
00:09:11,586 --> 00:09:13,710
Voy a tratar de poner
esto como una hora después.

198
00:09:13,710 --> 00:09:16,626
Voy por correo electrónico David, David intentará
lo puso como una hora después de esto.

199
00:09:16,626 --> 00:09:20,040

200
00:09:20,040 --> 00:09:25,470
>> OK, así que luego nos adentramos en este otro
estructura de datos preciosa llama una cola.

201
00:09:25,470 --> 00:09:30,140
Como ustedes pueden ver aquí, un
cola, para los británicos entre nosotros,

202
00:09:30,140 --> 00:09:32,010
todo lo que es es una línea.

203
00:09:32,010 --> 00:09:34,680
Así que al contrario de lo
crees que una pila es,

204
00:09:34,680 --> 00:09:37,750
una cola es exactamente lo
lógicamente usted piensa que es.

205
00:09:37,750 --> 00:09:41,914
Se lleva a cabo por las reglas de FIFO,
que es First In, First Out.

206
00:09:41,914 --> 00:09:43,705
Si usted es el primero
una en la línea, usted es

207
00:09:43,705 --> 00:09:46,230
el primero que
que sale de la línea.

208
00:09:46,230 --> 00:09:49,680
>> Así que lo que nos gusta llamar a este
se desencolado y encolar.

209
00:09:49,680 --> 00:09:52,380
Si queremos añadir algo
a nuestra cola, nos enqueue.

210
00:09:52,380 --> 00:09:55,690
Si queremos quitar de la cola, o tomar
algo lejos, nos dequeue.

211
00:09:55,690 --> 00:10:03,350
>> Así mismo sentido que estamos tipo de
la creación de elementos de tamaño fijo que

212
00:10:03,350 --> 00:10:06,500
puede almacenar cierta
cosas, sino que también puede

213
00:10:06,500 --> 00:10:10,100
cambiar el lugar donde estamos colocando
parámetros dentro de ellos

214
00:10:10,100 --> 00:10:13,140
sobre la base de qué tipo de
funcionalidad que queremos.

215
00:10:13,140 --> 00:10:16,700
Así pilas, queríamos la última
uno, N para ser el primero en salir.

216
00:10:16,700 --> 00:10:19,800
Cola es que queremos lo primero
en ser el primero que salió.

217
00:10:19,800 --> 00:10:22,510

218
00:10:22,510 --> 00:10:26,710
>> Así que la de tipo struct
definir, como se puede ver,

219
00:10:26,710 --> 00:10:29,470
que es un poco diferente
de lo que era la pila

220
00:10:29,470 --> 00:10:33,120
porque no sólo tenemos que seguir
la pista de donde el tamaño es actualmente,

221
00:10:33,120 --> 00:10:37,420
también queremos hacer un seguimiento de la cabeza
así como en los que actualmente somos.

222
00:10:37,420 --> 00:10:39,580
Así que creo que es más fácil
si me baso esto.

223
00:10:39,580 --> 00:10:53,270
Así que imaginemos que tenemos una cola,
así que digamos que la cabeza está aquí.

224
00:10:53,270 --> 00:10:55,811

225
00:10:55,811 --> 00:10:58,310
El jefe de la línea, vamos a
Basta con decir que es en la actualidad hay,

226
00:10:58,310 --> 00:11:01,809
y queremos insertar
algo en la cola.

227
00:11:01,809 --> 00:11:04,350
Voy a llamar a tamaño esencialmente
es lo mismo que la cola,

228
00:11:04,350 --> 00:11:06,314
Al final de donde quiera que su cola es.

229
00:11:06,314 --> 00:11:07,730
Digamos que el tamaño es justo aquí.

230
00:11:07,730 --> 00:11:14,380

231
00:11:14,380 --> 00:11:18,400
>> Entonces, ¿cómo puede uno factiblemente
insertar algo en una cola?

232
00:11:18,400 --> 00:11:21,000

233
00:11:21,000 --> 00:11:24,130
¿Qué índice queremos colocar
donde queremos insertar en.

234
00:11:24,130 --> 00:11:29,320
Si este es el comienzo de su
cola y este es el final de la misma

235
00:11:29,320 --> 00:11:31,860
o el tamaño de la misma, ¿dónde estamos
que desee agregar el siguiente objeto?

236
00:11:31,860 --> 00:11:32,920
>> AUDIENCIA: [inaudible]

237
00:11:32,920 --> 00:11:35,920
ANDI Peng: Exactamente, desea agregar
que dependiendo has escrito.

238
00:11:35,920 --> 00:11:37,840
O esto es en blanco o que está en blanco.

239
00:11:37,840 --> 00:11:42,630
Así que usted quiere agregar que probablemente
aquí porque si el tamaño es--

240
00:11:42,630 --> 00:11:50,540
si éstos están llenos, desea
añadir aquí mismo, ¿no?

241
00:11:50,540 --> 00:11:57,150
>> Y eso es, aunque muy, muy
simple, no es siempre correcta

242
00:11:57,150 --> 00:12:00,690
debido a que la principal diferencia
entre una cola y una pila

243
00:12:00,690 --> 00:12:04,350
es que la cola puede
en realidad ser manipulado

244
00:12:04,350 --> 00:12:06,980
de modo que los cambios de la cabeza
dependiendo de donde desea

245
00:12:06,980 --> 00:12:08,650
el comienzo de su señal para comenzar.

246
00:12:08,650 --> 00:12:11,900
Y como resultado, su cola
También se va a cambiar.

247
00:12:11,900 --> 00:12:14,770
Y así que échale un vistazo a
este código en este momento.

248
00:12:14,770 --> 00:12:18,620
Como también se les pidió que ustedes
escribir en el concurso, de puesta en cola.

249
00:12:18,620 --> 00:12:22,580
Tal vez vamos a hablar a través de qué
la respuesta era lo que era.

250
00:12:22,580 --> 00:12:26,790
>> No podía encajar bastante esta línea en uno,
pero esencialmente este pedazo de código

251
00:12:26,790 --> 00:12:29,030
debe estar en una sola línea.

252
00:12:29,030 --> 00:12:30,140
Pasa como 30 segundos.

253
00:12:30,140 --> 00:12:33,000
Echa un vistazo, y ver por qué
esta es la manera que lo es.

254
00:12:33,000 --> 00:12:50,030

255
00:12:50,030 --> 00:12:55,420
>> Muy, estructura muy similar, muy, muy
estructura similar a la anterior

256
00:12:55,420 --> 00:12:58,090
apilar excepto quizá
una línea de código.

257
00:12:58,090 --> 00:13:01,190
Y que una línea de código
determina la funcionalidad.

258
00:13:01,190 --> 00:13:03,900
Y lo que realmente diferencia a
una cola de una pila.

259
00:13:03,900 --> 00:13:18,510

260
00:13:18,510 --> 00:13:22,010
>> ¿Alguien quiere tomar una puñalada
al explicar por qué tienes

261
00:13:22,010 --> 00:13:24,980
tengo esta cosa complicada en esta lista?

262
00:13:24,980 --> 00:13:27,845
Nos vemos el regreso de nuestro
maravillosa módulo amigo.

263
00:13:27,845 --> 00:13:31,020
Como ustedes pronto vendrá
a reconocer en la programación,

264
00:13:31,020 --> 00:13:34,910
casi siempre usted necesita algo
para envolver alrededor de cualquier cosa,

265
00:13:34,910 --> 00:13:36,850
módulo va a ser la forma de hacerlo.

266
00:13:36,850 --> 00:13:40,510
Así que sabiendo eso, no quería que nadie
para tratar de explicar esa línea de código?

267
00:13:40,510 --> 00:13:44,060

268
00:13:44,060 --> 00:13:47,507
Sí, todas las respuestas son
aceptada y bienvenida.

269
00:13:47,507 --> 00:13:48,840
AUDIENCIA: ¿Usted está hablando conmigo?

270
00:13:48,840 --> 00:13:49,506
ANDI Peng: Sí.

271
00:13:49,506 --> 00:13:56,200
AUDIENCIA: ¡Oh, no lo siento.

272
00:13:56,200 --> 00:14:00,250
ANDI Peng: OK, así que vamos a
caminar a través de este código.

273
00:14:00,250 --> 00:14:03,642
Así que cuando usted está tratando de
agregar algo en una cola,

274
00:14:03,642 --> 00:14:08,510
en la encantadora caso de que el jefe sucede
para ser justo aquí, es muy fácil para nosotros

275
00:14:08,510 --> 00:14:10,960
que sólo tiene que ir hasta el final
insertar algo, ¿no?

276
00:14:10,960 --> 00:14:14,690
Pero el punto central de una cola es
que el jefe de hecho puede dinámicamente

277
00:14:14,690 --> 00:14:17,280
cambiar dependiendo de donde estamos
quiere que el comienzo de nuestra q sea,

278
00:14:17,280 --> 00:14:19,880
y como tal, la cola
También se va a cambiar.

279
00:14:19,880 --> 00:14:31,100
>> Y así, imagino que esto no era la
cola, sino que más bien se trataba de la cola.

280
00:14:31,100 --> 00:14:37,900

281
00:14:37,900 --> 00:14:39,330
Digamos que la cabeza está aquí.

282
00:14:39,330 --> 00:14:54,900

283
00:14:54,900 --> 00:14:56,980
Digamos que nuestra cola se veía así.

284
00:14:56,980 --> 00:15:00,190
Si quisiéramos cambiar, donde
el comienzo de la línea es,

285
00:15:00,190 --> 00:15:03,400
digamos que cambiamos la cabeza
de esta manera y tallas Aquí.

286
00:15:03,400 --> 00:15:07,100
>> Ahora queremos añadir algo a
esta cola, pero como ustedes pueden ver,

287
00:15:07,100 --> 00:15:11,150
que no es tan sencillo como simplemente
añadir lo es después de que el tamaño

288
00:15:11,150 --> 00:15:13,630
porque entonces nos quedamos sin
límites de nuestra gama actual.

289
00:15:13,630 --> 00:15:16,190
Cuando queremos añadir realmente está aquí.

290
00:15:16,190 --> 00:15:18,610
Esa es la belleza de una cola
es que a nosotros, visualmente

291
00:15:18,610 --> 00:15:22,380
parece que la línea es la siguiente,
pero cuando se almacena en una estructura de datos,

292
00:15:22,380 --> 00:15:29,370
dan como como un ciclo.

293
00:15:29,370 --> 00:15:32,360
En cierto modo se envuelve alrededor
a la parte delantera de la misma manera

294
00:15:32,360 --> 00:15:34,780
que una línea también puede envolver
todo dependiendo de donde quiera que

295
00:15:34,780 --> 00:15:36,279
querer principio de la línea para ser.

296
00:15:36,279 --> 00:15:38,630
Y así, si tomamos una
mira aquí abajo, vamos a

297
00:15:38,630 --> 00:15:40,880
decimos que queríamos crear un
función de llamada en cola.

298
00:15:40,880 --> 00:15:43,980
Queríamos añadir int n en que q.

299
00:15:43,980 --> 00:15:49,250
Si q.size q-- Llamaremos a que nuestros datos
structure-- si nuestro queue.size no

300
00:15:49,250 --> 00:15:52,520
igual a la capacidad o si
que es menos de la capacidad,

301
00:15:52,520 --> 00:15:55,120
q.strings es la matriz dentro de nuestro q.

302
00:15:55,120 --> 00:15:58,380
Vamos a establecer
que igual a q.heads,

303
00:15:58,380 --> 00:16:02,730
que está justo aquí, además q.size
por el módulo de capacidad, que

304
00:16:02,730 --> 00:16:04,290
nos envuelva vuelta por aquí.

305
00:16:04,290 --> 00:16:08,040
>> Así, en este ejemplo, el índice
de la cabeza es 1, ¿verdad?

306
00:16:08,040 --> 00:16:11,480
El índice de tamaño es 0, 1, 2, 3, 4.

307
00:16:11,480 --> 00:16:19,500
Así que podemos hacer 1 más 4 de módulo
por nuestra capacidad, que es 5.

308
00:16:19,500 --> 00:16:20,920
¿Qué nos dan?

309
00:16:20,920 --> 00:16:23,270
¿Cuál es el índice que
que sale de esto?

310
00:16:23,270 --> 00:16:24,080
>> AUDIENCIA: 0.

311
00:16:24,080 --> 00:16:27,870
>> ANDI Peng: 0, lo que
pasa a ser aquí,

312
00:16:27,870 --> 00:16:30,640
y así queremos ser capaces
para insertar en aquí.

313
00:16:30,640 --> 00:16:34,730
Y así esta ecuación aquí especie
de tan sólo funciona con cualquier número

314
00:16:34,730 --> 00:16:36,750
dependiendo de donde su
cabeza y su tamaño son.

315
00:16:36,750 --> 00:16:38,541
Si sabes lo que los
son las cosas, ya sabes

316
00:16:38,541 --> 00:16:43,170
exactamente donde desea insertar
todo lo que sea después de su cola.

317
00:16:43,170 --> 00:16:44,640
¿Eso tiene sentido para todo el mundo?

318
00:16:44,640 --> 00:16:48,560
>> Sé la clase de un cerebro
sumario sobre todo porque este

319
00:16:48,560 --> 00:16:50,512
llegó en las postrimerías de su concurso.

320
00:16:50,512 --> 00:16:52,220
Pero esperemos que todo el mundo
Ahora puede entender

321
00:16:52,220 --> 00:16:57,800
por qué esta solución o esta
función es la forma en que lo es.

322
00:16:57,800 --> 00:16:59,840
Cualquier persona un poco confuso al respecto?

323
00:16:59,840 --> 00:17:03,471

324
00:17:03,471 --> 00:17:03,970
OK.

325
00:17:03,970 --> 00:17:07,109

326
00:17:07,109 --> 00:17:09,970
>> Y ahora, si usted
querido quitar de la cola, esta

327
00:17:09,970 --> 00:17:15,240
es donde nuestra cabeza sería el cambio
porque si tuviéramos que quitar de la cola,

328
00:17:15,240 --> 00:17:17,030
no tomamos fuera de la final de la q.

329
00:17:17,030 --> 00:17:19,130
Queremos sacar la cabeza, ¿verdad?

330
00:17:19,130 --> 00:17:24,260
Así que, como resultado, la cabeza va a cambiar,
y es por eso que cuando encolar,

331
00:17:24,260 --> 00:17:26,800
tienes que mantener un registro de
donde su cabeza y su tamaño

332
00:17:26,800 --> 00:17:29,450
han de ser capaz de insertar
en la posición correcta.

333
00:17:29,450 --> 00:17:32,740
>> Y así cuando dequeue,
También Pseudocódigo a cabo.

334
00:17:32,740 --> 00:17:35,480
Siéntase libre si quiere
para intentar codificar esta fuera.

335
00:17:35,480 --> 00:17:36,980
Usted desea mover la cabeza, ¿verdad?

336
00:17:36,980 --> 00:17:39,320
Si quería quitar de la cola, me
movería la cabeza otra vez.

337
00:17:39,320 --> 00:17:40,800
Esta sería la cabeza.

338
00:17:40,800 --> 00:17:45,617
>> Y nuestro tamaño actual haría
restar porque ya no

339
00:17:45,617 --> 00:17:46,950
tener cuatro elementos de la matriz.

340
00:17:46,950 --> 00:17:51,370
Sólo tenemos tres, y luego queremos
para devolver todo lo que se almacena en el interior

341
00:17:51,370 --> 00:17:56,260
de la cabeza porque queremos aprovechar esta
valor a cabo de manera muy similar a la pila.

342
00:17:56,260 --> 00:17:58,010
Sólo usted está tomando
desde un lugar diferente,

343
00:17:58,010 --> 00:18:01,770
y tienes que volver a asignar el puntero
a diferente lugar como un resultado.

344
00:18:01,770 --> 00:18:03,890
Lógicamente, todo el mundo sigue?

345
00:18:03,890 --> 00:18:05,690
Excelente.

346
00:18:05,690 --> 00:18:10,156
>> OK, así que vamos a hablar un poco
más en profundidad sobre listas enlazadas

347
00:18:10,156 --> 00:18:13,280
porque van a estar muy, muy valiosa
para que en el transcurso de esta semana de

348
00:18:13,280 --> 00:18:14,964
conjuntos de procesadores.

349
00:18:14,964 --> 00:18:17,130
Listas enlazadas, como ustedes
recuerdo, todo lo que son

350
00:18:17,130 --> 00:18:22,570
son nodos que son nodos de cierta
valores tanto de un valor y un puntero

351
00:18:22,570 --> 00:18:26,290
que están unidos entre sí
por los punteros.

352
00:18:26,290 --> 00:18:29,880
Y por lo que la estructura de cómo
creamos un nodo aquí es que

353
00:18:29,880 --> 00:18:33,569
tener int n, que es lo
el valor en una tienda o cadena de n

354
00:18:33,569 --> 00:18:35,610
o lo que quieras
llamarlo, la estrella carbón n.

355
00:18:35,610 --> 00:18:41,482
Struct estrella nodo, que es el puntero
que usted desea tener en cada nodo,

356
00:18:41,482 --> 00:18:43,690
usted va a tener que
punta puntero hacia la siguiente.

357
00:18:43,690 --> 00:18:48,207

358
00:18:48,207 --> 00:18:50,040
Vas a tener la cabeza
de una lista enlazada que es

359
00:18:50,040 --> 00:18:53,140
va a señalar el resto de
los valores así sucesivamente y así sucesivamente

360
00:18:53,140 --> 00:18:55,290
hasta llegar finalmente al final.

361
00:18:55,290 --> 00:18:58,040
Y este último nodo es sólo
ir a no tener un puntero.

362
00:18:58,040 --> 00:18:59,952
Se va a apuntar a
nulo, y es entonces cuando

363
00:18:59,952 --> 00:19:01,910
sabes que has llegado a la
final de la lista enlazada

364
00:19:01,910 --> 00:19:04,076
es cuando su última puntero
no apunta a nada.

365
00:19:04,076 --> 00:19:06,670

366
00:19:06,670 --> 00:19:10,990
>> Así que vamos a ir un poco más en
de profundidad con respecto a cómo se haría posiblemente

367
00:19:10,990 --> 00:19:12,400
buscar una lista enlazada.

368
00:19:12,400 --> 00:19:15,460
Recuerda lo que son algunos de los
inconvenientes de las listas enlazadas

369
00:19:15,460 --> 00:19:19,340
versos una serie en relación con las búsquedas.

370
00:19:19,340 --> 00:19:22,565
Una matriz puede búsqueda binaria, pero
por qué no se puede hacer eso en una lista enlazada?

371
00:19:22,565 --> 00:19:26,834

372
00:19:26,834 --> 00:19:30,320
>> AUDIENCIA: Porque están todos conectados,
pero no sé muy bien dónde

373
00:19:30,320 --> 00:19:31,330
[INAUDIBLE].

374
00:19:31,330 --> 00:19:34,600
>> ANDI Peng: Sí, exactamente a fin de recordar
que la brillantez de un array

375
00:19:34,600 --> 00:19:37,190
fue el hecho de que teníamos
memoria de acceso aleatorio, donde

376
00:19:37,190 --> 00:19:41,580
si quería el valor del índice
seis, yo podría decir que el índice de seis,

377
00:19:41,580 --> 00:19:42,407
dame ese valor.

378
00:19:42,407 --> 00:19:45,240
Y eso es porque las matrices se clasifican
en un espacio contiguo de memoria

379
00:19:45,240 --> 00:19:48,020
en un solo lugar, mientras que
tipo de listas enlazadas

380
00:19:48,020 --> 00:19:52,820
se intercalan aleatoriamente por todas partes,
y la única manera que usted puede encontrar uno

381
00:19:52,820 --> 00:19:56,890
es a través de un puntero que te dice
la dirección del lugar en que el próximo nodo es.

382
00:19:56,890 --> 00:20:00,290
>> Y así, como resultado, la única manera de
para buscar a través de una lista enlazada

383
00:20:00,290 --> 00:20:01,560
es la búsqueda lineal.

384
00:20:01,560 --> 00:20:05,890
Porque yo no sé exactamente dónde
el valor 12 en la lista enlazada es,

385
00:20:05,890 --> 00:20:08,780
Tengo que atravesar la totalidad
de esa lista enlazada se

386
00:20:08,780 --> 00:20:12,450
por uno desde la cabeza hasta el primer nodo,
al segundo nodo, a la tercera nodo,

387
00:20:12,450 --> 00:20:17,690
todo el camino hasta que finalmente llegue
a donde ese nodo que estoy buscando es.

388
00:20:17,690 --> 00:20:22,110
Y así, en este sentido, la búsqueda
en una lista enlazada es siempre n.

389
00:20:22,110 --> 00:20:23,040
Siempre es n.

390
00:20:23,040 --> 00:20:25,690
Siempre en el tiempo lineal.

391
00:20:25,690 --> 00:20:28,470
>> Y por lo que el código en el que
implementamos esto, y esto

392
00:20:28,470 --> 00:20:32,620
es un poco nuevo para ustedes desde que
chicos realmente no han hablado ni nunca

393
00:20:32,620 --> 00:20:35,000
punteros visto en la forma de
buscar a través de punteros,

394
00:20:35,000 --> 00:20:37,670
así que vamos a caminar a través de
esta muy, muy lentamente.

395
00:20:37,670 --> 00:20:40,200
Así que la búsqueda bool, derecha,
imaginemos que queremos

396
00:20:40,200 --> 00:20:42,820
para crear una función llamada
búsqueda que devuelve true

397
00:20:42,820 --> 00:20:46,820
si usted encuentra un valor dentro de la vinculada
lista, y devuelve false en caso contrario.

398
00:20:46,820 --> 00:20:50,030
Lista de estrellas de nodo es
Actualmente sólo el puntero

399
00:20:50,030 --> 00:20:52,960
al primer elemento de la lista enlazada.

400
00:20:52,960 --> 00:20:56,700
int n es el valor que usted es
buscar en esa lista.

401
00:20:56,700 --> 00:20:58,770
>> Así indicador de la estrella nodo es igual a la lista.

402
00:20:58,770 --> 00:21:00,970
Eso significa que estamos configurando
y la creación de un puntero

403
00:21:00,970 --> 00:21:03,592
al primer nodo dentro de la lista.

404
00:21:03,592 --> 00:21:04,300
Todo el mundo conmigo?

405
00:21:04,300 --> 00:21:06,530
Así que si nos vamos a ir
Vuelve aquí, tendría

406
00:21:06,530 --> 00:21:13,850
inicializado un puntero que apunta a
la cabeza de lo que la lista es.

407
00:21:13,850 --> 00:21:18,600
>> Y luego una vez que llegue aquí,
mientras que el puntero no es igual a null,

408
00:21:18,600 --> 00:21:22,160
por lo que es el bucle en el que estamos
va a ser posteriormente atravesar

409
00:21:22,160 --> 00:21:25,940
el resto de nuestra lista porque lo
sucede cuando el puntero equivale a nula?

410
00:21:25,940 --> 00:21:27,550
Sabemos que tener--

411
00:21:27,550 --> 00:21:28,450
>> AUDIENCIA: [inaudible]

412
00:21:28,450 --> 00:21:31,491
>> ANDI Peng: Exactamente, así que sabemos que
hemos llegado al final de la lista, ¿no?

413
00:21:31,491 --> 00:21:34,470
Si vuelves aquí, cada nodo
debe estar apuntando a otro nodo

414
00:21:34,470 --> 00:21:36,550
y así sucesivamente y así sucesivamente
hasta llegar, finalmente,

415
00:21:36,550 --> 00:21:41,589
la cola de la lista enlazada,
que tiene un puntero que acaba

416
00:21:41,589 --> 00:21:43,130
no señala en ningún otro que no.

417
00:21:43,130 --> 00:21:47,510
Así que, básicamente, saber que
tu lista todavía está allí arriba

418
00:21:47,510 --> 00:21:50,900
hasta que el puntero no es igual a
nula porque una vez que es igual a null,

419
00:21:50,900 --> 00:21:53,310
usted sabe que no hay más cosas.

420
00:21:53,310 --> 00:21:56,930
>> Así que ese es el bucle en el que estamos
va a tener la búsqueda real.

421
00:21:56,930 --> 00:22:01,690
Y si los pointer-- hacen que vea
ese tipo de función saeta en ella?

422
00:22:01,690 --> 00:22:06,930
Así que si puntero apunta a n, si
el puntero en n es igual es igual a n,

423
00:22:06,930 --> 00:22:09,180
lo que significa que si
el puntero que eres

424
00:22:09,180 --> 00:22:13,420
buscar en el extremo de cada
nodo es en realidad igual al valor

425
00:22:13,420 --> 00:22:15,990
que estás buscando, entonces
desea volver realidad.

426
00:22:15,990 --> 00:22:19,280
Así que, básicamente, si usted está en un nodo que
tiene el valor que usted está buscando,

427
00:22:19,280 --> 00:22:23,550
sabes que has estado
capaz de buscar con éxito.

428
00:22:23,550 --> 00:22:27,150
>> De lo contrario, desea establecer
el puntero al siguiente nodo.

429
00:22:27,150 --> 00:22:28,850
Eso es lo que esa línea aquí está haciendo.

430
00:22:28,850 --> 00:22:31,750
Pointer es igual puntero siguiente.

431
00:22:31,750 --> 00:22:33,360
Todo el mundo vea cómo eso está trabajando?

432
00:22:33,360 --> 00:22:36,580
>> Y básicamente vas a solo
recorrer la totalidad de la lista,

433
00:22:36,580 --> 00:22:41,920
restablecer el puntero cada vez hasta
que finalmente golpeó el final de la lista.

434
00:22:41,920 --> 00:22:45,030
Y usted sabe que no hay
más nodos para buscar a través de,

435
00:22:45,030 --> 00:22:47,999
y entonces usted puede devolver false
porque sabes que, oh, bueno,

436
00:22:47,999 --> 00:22:50,540
si yo he sido capaz de buscar
a través de la totalidad de la lista.

437
00:22:50,540 --> 00:22:54,530
Si en este ejemplo, si quería
para buscar el valor de 10,

438
00:22:54,530 --> 00:22:57,250
y me pongo a la cabeza, y
Yo busco hasta el fondo,

439
00:22:57,250 --> 00:23:00,550
y, finalmente, llegué a esto, que
un puntero que apunta a null,

440
00:23:00,550 --> 00:23:04,415
Sé que, mierda, supongo que 10 no está en
esta lista porque no pude encontrarlo.

441
00:23:04,415 --> 00:23:06,520
Y estoy al final de la lista.

442
00:23:06,520 --> 00:23:11,040
Y en este caso usted sabe
Voy a devolver false.

443
00:23:11,040 --> 00:23:12,900
>> Vamos que remojo en un poco.

444
00:23:12,900 --> 00:23:17,350
Esta será bastante
importante para su conjunto de procesadores.

445
00:23:17,350 --> 00:23:21,140
La lógica de que es muy simple, tal vez
sintácticamente simplemente implementarlo.

446
00:23:21,140 --> 00:23:23,365
¿Quieren hacer
Asegúrese de entender.

447
00:23:23,365 --> 00:23:25,870

448
00:23:25,870 --> 00:23:27,650
Guay.

449
00:23:27,650 --> 00:23:32,560
>> OK, así que ¿cómo nos habría
la inserción de nodos, la derecha,

450
00:23:32,560 --> 00:23:35,380
en una lista porque recuerde
¿cuáles son los qué de los beneficios

451
00:23:35,380 --> 00:23:39,230
de tener una lista enlazada frente
una matriz en términos de almacenamiento?

452
00:23:39,230 --> 00:23:41,110
>> AUDIENCIA: Es dinámico,
así que es más fácil a--

453
00:23:41,110 --> 00:23:43,180
>> ANDI Peng: Exactamente,
por lo que es dinámico, que

454
00:23:43,180 --> 00:23:46,880
significa que puede expandirse y contraerse
dependiendo de las necesidades del usuario.

455
00:23:46,880 --> 00:23:56,570
Y así, en este sentido, no necesitamos
a perder la memoria innecesaria porque

456
00:23:56,570 --> 00:24:00,850
si yo no sé cuántos valores que quiero
a la tienda, que no tiene sentido para mí

457
00:24:00,850 --> 00:24:04,310
para crear una matriz debido
si quiero almacenar 10 valores

458
00:24:04,310 --> 00:24:08,380
y puedo crear una matriz de 1000, que es
una gran cantidad de memoria perdida, asignado.

459
00:24:08,380 --> 00:24:11,180
Es por eso que queremos utilizar una ligado
lista para ser capaz de dinámicamente

460
00:24:11,180 --> 00:24:13,860
cambiar o reducir nuestro tamaño.

461
00:24:13,860 --> 00:24:17,040
>> Y por lo que hace la inserción
un poco más complicado.

462
00:24:17,040 --> 00:24:20,810
Ya que no podemos acceder aleatoriamente elementos
la forma en que nos de una matriz.

463
00:24:20,810 --> 00:24:24,270
Si quiero insertar un elemento
en el séptimo índice,

464
00:24:24,270 --> 00:24:26,930
Yo sólo puedo insertarlo
en el séptimo índice.

465
00:24:26,930 --> 00:24:30,020
En una lista enlazada, no lo hace
bastante trabajar con la misma facilidad,

466
00:24:30,020 --> 00:24:34,947
y así si queríamos insertar
el uno aquí en la lista enlazada,

467
00:24:34,947 --> 00:24:36,280
visualmente, es muy fácil de ver.

468
00:24:36,280 --> 00:24:39,363
Sólo queremos insertar allí mismo,
la derecha en el principio de la lista,

469
00:24:39,363 --> 00:24:40,840
justo después de la cabeza.

470
00:24:40,840 --> 00:24:44,579
>> Pero la forma en la que tenemos que reasignar
los punteros es un poco complicado

471
00:24:44,579 --> 00:24:47,620
o, lógicamente, tiene sentido, pero
usted quiere asegurarse de que usted lo tiene

472
00:24:47,620 --> 00:24:50,250
completamente abajo porque
la última cosa que quiero

473
00:24:50,250 --> 00:24:52,990
es volver a asignar un puntero al
camino que estamos haciendo aquí.

474
00:24:52,990 --> 00:24:58,170
Si eliminar la referencia al
puntero de la cabeza a 1,

475
00:24:58,170 --> 00:25:01,086
luego, de repente
resto de su lista enlazada

476
00:25:01,086 --> 00:25:04,680
se pierde porque usted tiene en realidad no
creado un nada temporal.

477
00:25:04,680 --> 00:25:06,220
Eso se señaló a la 2.

478
00:25:06,220 --> 00:25:10,080
Si reasigna el puntero, entonces el
resto de su lista está totalmente perdido.

479
00:25:10,080 --> 00:25:13,310
Así que quieres ser
muy, muy cuidadoso aquí

480
00:25:13,310 --> 00:25:17,010
para asignar la primera
puntero de lo que

481
00:25:17,010 --> 00:25:20,150
quiere insertar en cualquier lugar
que quiere, y entonces

482
00:25:20,150 --> 00:25:22,710
puede eliminar la referencia al resto de su lista.

483
00:25:22,710 --> 00:25:25,250
>> Así que esto se aplica a cualquier lugar
usted está tratando de insertar en.

484
00:25:25,250 --> 00:25:27,520
Si desea insertar en el
cabeza, si quieres contestar aquí,

485
00:25:27,520 --> 00:25:29,455
si desea insertar en
Al final, bueno, al final me

486
00:25:29,455 --> 00:25:30,910
supongo que lo haría solo
tener ningún puntero, pero

487
00:25:30,910 --> 00:25:33,830
querrá asegurarse de que usted no lo hace
perderá el resto de la lista.

488
00:25:33,830 --> 00:25:36,640
Uno siempre quiere asegurarse
el nuevo nodo apunte

489
00:25:36,640 --> 00:25:39,330
hacia lo que
quiere insertar en,

490
00:25:39,330 --> 00:25:42,170
y entonces usted puede añadir el encadenamiento.

491
00:25:42,170 --> 00:25:43,330
Todo el mundo claro?

492
00:25:43,330 --> 00:25:45,427
>> Esto va a ser
uno de los problemas reales.

493
00:25:45,427 --> 00:25:48,010
Uno de los problemas de la mayoría de las
usted va a tener en su conjunto de procesadores

494
00:25:48,010 --> 00:25:51,340
es que usted va a tratar de crear
una lista enlazada y las cosas de inserción

495
00:25:51,340 --> 00:25:53,340
pero entonces sólo perderá el
resto de su lista enlazada.

496
00:25:53,340 --> 00:25:54,900
Y tú vas a ser como,
no sé por qué está sucediendo esto?

497
00:25:54,900 --> 00:25:58,040
Y es un dolor que pasar por
y buscar todos sus punteros.

498
00:25:58,040 --> 00:26:02,100
>> Y te garantizo en este conjunto de procesadores,
escribir y dibujar estos nodos fuera

499
00:26:02,100 --> 00:26:03,344
va a ser muy, muy servicial.

500
00:26:03,344 --> 00:26:06,010
Así que usted puede mantener por completo la pista
de donde todos sus punteros son,

501
00:26:06,010 --> 00:26:08,540
lo que va mal,
donde todos los nodos son,

502
00:26:08,540 --> 00:26:12,660
lo que tiene que hacer para acceder o
insertar o eliminar o cualquiera de ellos.

503
00:26:12,660 --> 00:26:14,550
Todo el mundo bien con eso?

504
00:26:14,550 --> 00:26:15,050
Guay.

505
00:26:15,050 --> 00:26:19,300

506
00:26:19,300 --> 00:26:22,600
>> Así que si queríamos mirar el código?

507
00:26:22,600 --> 00:26:24,470
Oh, no sé si
puede ver el-- OK, así

508
00:26:24,470 --> 00:26:27,940
en la parte superior de todo lo que es es una función
inserto llamado donde queremos

509
00:26:27,940 --> 00:26:31,365
insertar int n en la lista enlazada.

510
00:26:31,365 --> 00:26:32,740
Vamos a caminar a través de esto.

511
00:26:32,740 --> 00:26:34,770
Es una gran cantidad de código, una gran cantidad de nueva sintaxis.

512
00:26:34,770 --> 00:26:36,220
Vamos a estar bien.

513
00:26:36,220 --> 00:26:39,120
>> Así que en la parte superior, siempre que sea
queremos crear nada

514
00:26:39,120 --> 00:26:42,380
¿qué es lo que tenemos que hacer, especialmente si usted
quiero que no se almacena en la pila

515
00:26:42,380 --> 00:26:43,920
pero en el montón?

516
00:26:43,920 --> 00:26:45,460
Vamos a un malloc, ¿verdad?

517
00:26:45,460 --> 00:26:48,240
Así que vamos a crear un puntero.

518
00:26:48,240 --> 00:26:52,074
Nodos, puntero, nuevos iguales
malloc el tamaño de un nodo

519
00:26:52,074 --> 00:26:53,740
porque queremos que el nodo que se creará.

520
00:26:53,740 --> 00:26:56,720
Queremos que la cantidad de
memoria que un nodo ocupa

521
00:26:56,720 --> 00:26:59,300
para ser asignado para el
creación del nuevo nodo.

522
00:26:59,300 --> 00:27:02,270
>> Y luego vamos a comprobar para
ver si los nuevos iguales es igual a cero.

523
00:27:02,270 --> 00:27:03,370
Recuerda lo que dijimos?

524
00:27:03,370 --> 00:27:06,470
Hagas lo que malloc,
¿qué debe hacer siempre?

525
00:27:06,470 --> 00:27:09,490
Usted debe comprobar siempre para ver
si es o no es nulo.

526
00:27:09,490 --> 00:27:13,620
>> Por ejemplo, si su funcionamiento
sistema estaba completamente lleno,

527
00:27:13,620 --> 00:27:17,060
si no tuviera más memoria en
todo y tratas de malloc,

528
00:27:17,060 --> 00:27:18,410
volvería nulo para usted.

529
00:27:18,410 --> 00:27:21,094
Y por lo que si intenta utilizarlo
cuando se estaba apuntando a null,

530
00:27:21,094 --> 00:27:23,260
no vas a poder
para acceder a esa información.

531
00:27:23,260 --> 00:27:27,010
Y así, como tal, hemos querido hacer
Asegúrese de que cada vez que estés mallocing,

532
00:27:27,010 --> 00:27:30,500
siempre estás comprobando si
que la memoria que le ha asignado es nulo.

533
00:27:30,500 --> 00:27:33,670
Y si no lo es, entonces podemos mover
con el resto de nuestro código.

534
00:27:33,670 --> 00:27:36,140
>> Así que vamos a
inicializar el nuevo nodo.

535
00:27:36,140 --> 00:27:39,050
Vamos a hacer nueva n es igual a n.

536
00:27:39,050 --> 00:27:42,390
Y luego vamos a hacer
set nuevo el puntero de nuevo

537
00:27:42,390 --> 00:27:46,900
en nulo porque en este momento no lo hacemos
quiero nada para que apunte a.

538
00:27:46,900 --> 00:27:48,755
No tenemos ni idea de dónde
que va a poner usted,

539
00:27:48,755 --> 00:27:50,630
y luego, si queremos
insertarlo en la cabeza,

540
00:27:50,630 --> 00:27:53,820
entonces podemos reasignar
el puntero a la cabeza.

541
00:27:53,820 --> 00:27:58,530
¿Todo el mundo sigue la lógica
de donde eso está pasando?

542
00:27:58,530 --> 00:28:02,502
>> Todo lo que estamos haciendo es crear una nueva
nodo, estableciendo el puntero a null,

543
00:28:02,502 --> 00:28:04,210
y luego reasignar
a la cabeza si

544
00:28:04,210 --> 00:28:06,320
sabemos que queremos para insertarlo en la cabeza.

545
00:28:06,320 --> 00:28:09,420
Y entonces la cabeza va a
apuntar hacia ese nuevo nodo.

546
00:28:09,420 --> 00:28:11,060
Todo el mundo de acuerdo con eso?

547
00:28:11,060 --> 00:28:12,380
>> Así que es un proceso de dos pasos.

548
00:28:12,380 --> 00:28:14,760
Hay que asignar primero
lo que está creando.

549
00:28:14,760 --> 00:28:18,260
Establecer ese puntero a la
referencia, y luego

550
00:28:18,260 --> 00:28:21,400
puede especie de eliminar la referencia
la primera puntero

551
00:28:21,400 --> 00:28:22,972
y apunte hacia el nuevo nodo.

552
00:28:22,972 --> 00:28:25,680
Dondequiera que usted desea insertarlo,
que la lógica va a ser verdad.

553
00:28:25,680 --> 00:28:27,530
>> Es algo así como la asignación de
variables temporales.

554
00:28:27,530 --> 00:28:28,700
Recuerde, usted tiene
para asegurarse de que usted

555
00:28:28,700 --> 00:28:30,346
no perder de vista que si estás intercambiando.

556
00:28:30,346 --> 00:28:33,470
Usted quiere asegurarse de que usted tiene un
variable temporal ese tipo de guarda

557
00:28:33,470 --> 00:28:35,620
la pista de donde esa cosa
se almacena para que

558
00:28:35,620 --> 00:28:41,190
no pierda ningún valor en el curso
de como jugar un poco con él.

559
00:28:41,190 --> 00:28:42,710
>> OK, así que el código estará aquí.

560
00:28:42,710 --> 00:28:45,020
Ustedes miren después de la sección.

561
00:28:45,020 --> 00:28:48,060
Será allí.

562
00:28:48,060 --> 00:28:50,280
>> Así que supongo que lo hace
esta diferencia si queríamos

563
00:28:50,280 --> 00:28:52,300
para insertar en el medio o al final?

564
00:28:52,300 --> 00:28:57,892
¿Alguien tiene una idea de lo que es la
pseudocódigo como la referencia lógica

565
00:28:57,892 --> 00:29:00,350
que tomaríamos si queríamos
para insertarlo en el medio?

566
00:29:00,350 --> 00:29:03,391
Así que si queríamos para insertarlo en el
cabeza, todo lo que hacemos es crear un nuevo nodo.

567
00:29:03,391 --> 00:29:06,311
Hemos creado el puntero de ese
nuevo nodo a cualquiera que sea la cabeza,

568
00:29:06,311 --> 00:29:08,310
y luego nos pusimos en la cabeza
al nuevo nodo, ¿verdad?

569
00:29:08,310 --> 00:29:11,560
Si quisiéramos para insertarlo en el medio
de la lista, lo que tendríamos que hacer?

570
00:29:11,560 --> 00:29:14,108

571
00:29:14,108 --> 00:29:16,110
>> AUDIENCIA: Seguiría
ser un proceso similar

572
00:29:16,110 --> 00:29:19,114
de como la asignación de puntero y
luego asignar ese puntero,

573
00:29:19,114 --> 00:29:20,530
pero tendríamos que ubicar allí.

574
00:29:20,530 --> 00:29:23,560
>> ANDI Peng: Exactamente, así que exactamente
el mismo proceso, excepto usted

575
00:29:23,560 --> 00:29:27,820
que localizar el lugar exacto que
quiere que el nuevo puntero a entrar en,

576
00:29:27,820 --> 00:29:44,790
por lo que si quiero insertar en
el medio de ligado películas-- OK,

577
00:29:44,790 --> 00:29:46,370
digamos que es nuestra lista enlazada.

578
00:29:46,370 --> 00:29:49,500
Si queremos insertar aquí mismo,
vamos a crear un nuevo nodo.

579
00:29:49,500 --> 00:29:50,520
Vamos a malloc.

580
00:29:50,520 --> 00:29:52,220
Vamos a crear un nuevo nodo.

581
00:29:52,220 --> 00:29:55,940
Vamos a asignar el
puntero de este nodo aquí.

582
00:29:55,940 --> 00:29:58,335
>> Pero el problema que difiere
desde donde la cabeza es

583
00:29:58,335 --> 00:30:00,490
es que sabíamos exactamente
donde la cabeza es.

584
00:30:00,490 --> 00:30:01,930
Fue justo en el primero, ¿no?

585
00:30:01,930 --> 00:30:04,870
Pero aquí tenemos que seguir la pista
de donde estamos insertarlo en.

586
00:30:04,870 --> 00:30:07,930
Si estamos insertando nuestra
nodo de aquí, tenemos

587
00:30:07,930 --> 00:30:12,270
para asegurarse de que la
anterior a este nodo

588
00:30:12,270 --> 00:30:14,172
es el que reasigna el puntero.

589
00:30:14,172 --> 00:30:16,380
Entonces usted tiene que tipo de
no perder de vista dos cosas.

590
00:30:16,380 --> 00:30:19,420
Si se mantiene la pista de donde esta
nodo actualmente está insertando en.

591
00:30:19,420 --> 00:30:23,280
También hay que perder de vista donde
el nodo anterior de que usted está buscando en

592
00:30:23,280 --> 00:30:24,340
También estaba allí.

593
00:30:24,340 --> 00:30:25,830
Todo el mundo bien con eso?

594
00:30:25,830 --> 00:30:26,500
OK.

595
00:30:26,500 --> 00:30:28,000
>> ¿Qué hay de la inserción en el final?

596
00:30:28,000 --> 00:30:34,220
Si yo quería añadir que aquí-- si quería
añadir un nuevo nodo a la final de una lista,

597
00:30:34,220 --> 00:30:37,009
¿Cómo podría yo ir haciendo eso?

598
00:30:37,009 --> 00:30:39,300
AUDIENCIA: Entonces, en la actualidad, la
señaló la última en nulo.

599
00:30:39,300 --> 00:30:40,960
ANDI Peng: Sí.

600
00:30:40,960 --> 00:30:43,560
Exactamente, así que éste
Actualmente se señaló a conocer,

601
00:30:43,560 --> 00:30:46,720
y así que supongo que, en este sentido, es
muy fácil añadir al final de una lista.

602
00:30:46,720 --> 00:30:51,810
Todo lo que tienes que hacer es establecer que
igual a null y luego auge.

603
00:30:51,810 --> 00:30:53,070
Allí mismo, muy fácil.

604
00:30:53,070 --> 00:30:53,960
Muy sencillo.

605
00:30:53,960 --> 00:30:56,430
>> Muy similar a la
cabeza, pero lógicamente que

606
00:30:56,430 --> 00:30:59,690
querrá asegurarse de que los pasos
tomar hacia hacer nada de esto,

607
00:30:59,690 --> 00:31:01,500
estás siguiendo.

608
00:31:01,500 --> 00:31:04,420
Es muy fácil, en el medio
de su código, ponerse al día,

609
00:31:04,420 --> 00:31:05,671
oh, tengo tantos punteros.

610
00:31:05,671 --> 00:31:07,461
Yo no sé de dónde
nada está señalando.

611
00:31:07,461 --> 00:31:09,170
Ni siquiera sé qué nodo estoy.

612
00:31:09,170 --> 00:31:11,490
¿Que esta pasando?

613
00:31:11,490 --> 00:31:13,620
>> Relájese, calmarse, tomar una respiración profunda.

614
00:31:13,620 --> 00:31:15,530
Dibuja tu lista enlazada.

615
00:31:15,530 --> 00:31:18,800
Si dices, sé dónde exactamente
Necesito insertar esto en

616
00:31:18,800 --> 00:31:22,970
y sé exactamente cómo reasignar mi
punteros, mucho, mucho más fácil de imaginar

617
00:31:22,970 --> 00:31:27,200
fuera-- mucho, mucho más fácil no
perderse en los errores de su código.

618
00:31:27,200 --> 00:31:29,410
Todo el mundo de acuerdo con eso?

619
00:31:29,410 --> 00:31:31,380
OK.

620
00:31:31,380 --> 00:31:35,120
>> Así que supongo que un concepto que no tenemos
realmente hablado hasta ahora,

621
00:31:35,120 --> 00:31:38,131
y yo le creo, probablemente
no se encontrará mucho yet--

622
00:31:38,131 --> 00:31:40,880
es una especie de concept-- avanzada
es que en realidad tenemos un dato

623
00:31:40,880 --> 00:31:43,900
estructura llamada una lista doblemente enlazada.

624
00:31:43,900 --> 00:31:46,390
Así como ustedes pueden ver,
todo lo que estamos haciendo es crear

625
00:31:46,390 --> 00:31:50,400
un valor real, un extra
puntero en cada uno de nuestros nodos

626
00:31:50,400 --> 00:31:52,660
que también apunta al nodo anterior.

627
00:31:52,660 --> 00:31:58,170
Así que no sólo tenemos nuestra
nodos apuntan a la siguiente.

628
00:31:58,170 --> 00:32:01,430
También apuntan a la anterior.

629
00:32:01,430 --> 00:32:04,310
Voy a ignorar estos dos ahora.

630
00:32:04,310 --> 00:32:06,740
>> Entonces usted tiene una cadena
que puede moverse en ambos sentidos,

631
00:32:06,740 --> 00:32:09,630
y entonces es un poco más fácil
seguir lógicamente junto.

632
00:32:09,630 --> 00:32:11,896
Al igual que aquí, en lugar de
no perder de vista, oh,

633
00:32:11,896 --> 00:32:14,520
tiene que saber que este nodo es
el que tengo que volver a asignar,

634
00:32:14,520 --> 00:32:17,532
Yo sólo puedo ir aquí y
simplemente tire de la anterior.

635
00:32:17,532 --> 00:32:19,490
Entonces sé exactamente dónde
es decir, y entonces

636
00:32:19,490 --> 00:32:21,130
no tienen que atravesar la
totalidad de la lista enlazada.

637
00:32:21,130 --> 00:32:22,180
Es un poco más fácil.

638
00:32:22,180 --> 00:32:24,960
>> Pero como tal, tiene una doble
la cantidad de punteros,

639
00:32:24,960 --> 00:32:26,960
eso es el doble de la cantidad de memoria.

640
00:32:26,960 --> 00:32:28,950
Es un montón de consejos para no perder de vista.

641
00:32:28,950 --> 00:32:32,140
Es un poco más complejo, pero es
un poco más fácil de usar función

642
00:32:32,140 --> 00:32:34,080
en lo que estamos tratando de lograr.

643
00:32:34,080 --> 00:32:36,910
>> Así que este tipo de datos
estructura totalmente existe,

644
00:32:36,910 --> 00:32:40,280
y la estructura de es muy, muy
simple, excepto todo lo que está teniendo es decir,

645
00:32:40,280 --> 00:32:43,850
en lugar de sólo un puntero al siguiente,
usted también tiene un puntero al anterior.

646
00:32:43,850 --> 00:32:45,940
Esa es toda la diferencia fue.

647
00:32:45,940 --> 00:32:47,740
Todo el mundo bien con eso?

648
00:32:47,740 --> 00:32:48,240
Guay.

649
00:32:48,240 --> 00:32:50,940

650
00:32:50,940 --> 00:32:53,280
>> Muy bien, así que ahora estoy
pasar muy probablemente

651
00:32:53,280 --> 00:32:56,870
como 15 a 20 minutos o el mayor
del resto del tiempo en la sección

652
00:32:56,870 --> 00:32:58,360
hablando sobre tablas hash.

653
00:32:58,360 --> 00:33:02,590
¿Cuántos de ustedes
han leído spec pset5?

654
00:33:02,590 --> 00:33:03,620
Muy bien, muy bien.

655
00:33:03,620 --> 00:33:06,160
Eso es más alto que el 50% de los normalmente.

656
00:33:06,160 --> 00:33:07,560
Esta bien.

657
00:33:07,560 --> 00:33:10,345
>> Así como ustedes verán,
eres desafío en pset5

658
00:33:10,345 --> 00:33:16,790
será la de aplicar un diccionario
donde se carga más de 140.000 palabras

659
00:33:16,790 --> 00:33:20,610
que le demos y corrector ortográfico
contra todo el texto.

660
00:33:20,610 --> 00:33:22,580
Le daremos al azar
piezas de la literatura.

661
00:33:22,580 --> 00:33:23,520
Le daremos la Odisea.

662
00:33:23,520 --> 00:33:24,561
Le daremos la Ilíada.

663
00:33:24,561 --> 00:33:26,350
Le daremos Austin Powers.

664
00:33:26,350 --> 00:33:28,220
>> Y su reto
será de deletrear verificación

665
00:33:28,220 --> 00:33:31,760
cada palabra en todo
de esos diccionarios

666
00:33:31,760 --> 00:33:34,960
esencialmente con nuestro corrector ortográfico.

667
00:33:34,960 --> 00:33:38,620
Y así hay algunas partes
de la creación de este conjunto de procesadores,

668
00:33:38,620 --> 00:33:41,970
primero que quieres ser
capaz de cargar realidad

669
00:33:41,970 --> 00:33:43,970
todas las palabras en su
diccionario, y luego

670
00:33:43,970 --> 00:33:45,530
quiero ser capaz de
revisar la ortografía de todos ellos.

671
00:33:45,530 --> 00:33:48,780
Y así, como tal, usted va a requerir
una estructura de datos que puede hacer esto rápido

672
00:33:48,780 --> 00:33:50,790
y eficientemente y de forma dinámica.

673
00:33:50,790 --> 00:33:52,900
>> Así que supongo que el más fácil
manera de hacer esto,

674
00:33:52,900 --> 00:33:55,010
probablemente crear una matriz, ¿no?

675
00:33:55,010 --> 00:33:58,910
La forma más sencilla de almacenamiento que es
puede crear una matriz de 140.000 palabras

676
00:33:58,910 --> 00:34:03,400
y acaba de colocar a todos allí y
luego atravesar les binario de búsqueda

677
00:34:03,400 --> 00:34:06,780
o selecciones o no--
siento que eso clasificación.

678
00:34:06,780 --> 00:34:10,729
Puede ordenarlos y luego recorrer los
por búsqueda binaria o de búsqueda simplemente lineal

679
00:34:10,729 --> 00:34:13,730
y justo finales de las palabras, pero que
tiene una enorme cantidad de memoria,

680
00:34:13,730 --> 00:34:15,190
y no es muy eficiente.

681
00:34:15,190 --> 00:34:18,350
>> Así que vamos a empezar
hablando de formas de hacer

682
00:34:18,350 --> 00:34:20,110
nuestro tiempo de funcionamiento más eficiente.

683
00:34:20,110 --> 00:34:23,190
Y nuestro objetivo es conseguir
constante de tiempo donde

684
00:34:23,190 --> 00:34:25,810
es casi como arrays, donde
usted tiene acceso instantáneo.

685
00:34:25,810 --> 00:34:28,560
Si quería buscar algo,
Quiero ser capaz de simplemente,

686
00:34:28,560 --> 00:34:30,810
auge, saber exactamente, y tire de ella.

687
00:34:30,810 --> 00:34:34,100
Y así una estructura en la cual
estaremos volviendo muy cerca

688
00:34:34,100 --> 00:34:37,569
para poder acceder a la constante
tiempo, este santo grial

689
00:34:37,569 --> 00:34:41,370
en la programación de la constante
tiempo se llama una tabla hash.

690
00:34:41,370 --> 00:34:45,370
Y así David mencionó anteriormente la
[Inaudible] un poco en la conferencia,

691
00:34:45,370 --> 00:34:49,100
pero vamos a realmente
buceo en profundidad esta semana

692
00:34:49,100 --> 00:34:51,780
en una pieza que está en relación con
cómo una tabla hash funciona.

693
00:34:51,780 --> 00:34:53,949
>> Así que la forma en que un hash
obras de mesa, por ejemplo,

694
00:34:53,949 --> 00:35:00,230
si quería guardar un montón de palabras, un
manojo de palabras en el idioma Inglés,

695
00:35:00,230 --> 00:35:02,940
Yo teóricamente podría poner
plátano, manzana, kiwi, mango, par,

696
00:35:02,940 --> 00:35:04,980
y melón todo en apenas una matriz.

697
00:35:04,980 --> 00:35:07,044
Todos ellos podrían encajar y ser encontrar.

698
00:35:07,044 --> 00:35:09,210
Sería una especie de dolor de
buscar a través de y el acceso,

699
00:35:09,210 --> 00:35:12,920
pero la manera más fácil de hacer esto es
que podemos crear en realidad una estructura

700
00:35:12,920 --> 00:35:15,680
llamada una tabla hash donde hash.

701
00:35:15,680 --> 00:35:19,880
Corremos todas nuestras claves a través
una función hash, una ecuación,

702
00:35:19,880 --> 00:35:22,600
que todos ellos se convierte en
una especie de un valor

703
00:35:22,600 --> 00:35:28,740
que podemos almacenar en
esencialmente un conjunto de lista enlazada.

704
00:35:28,740 --> 00:35:32,570
>> Y aquí, si queríamos
para almacenar las palabras en inglés,

705
00:35:32,570 --> 00:35:37,250
podríamos potencialmente simplemente, no hacer
saber, convertir todas las primeras letras

706
00:35:37,250 --> 00:35:39,630
en una especie de un número.

707
00:35:39,630 --> 00:35:43,140
Y así, por ejemplo, si quería
Un ser sinónimo de apple--

708
00:35:43,140 --> 00:35:47,460
o con el índice de 0, y
B a ser sinónimo de 1,

709
00:35:47,460 --> 00:35:51,030
podemos tener 26 entradas
que solo puede almacenar

710
00:35:51,030 --> 00:35:53,610
todas las letras del
alfabeto que vamos a empezar con.

711
00:35:53,610 --> 00:35:56,130
Y luego podemos tener
manzana en el índice de 0.

712
00:35:56,130 --> 00:35:59,160
Podemos tener plátano en el índice de
1, el melón en el índice de 2,

713
00:35:59,160 --> 00:36:00,540
y así sucesivamente y así sucesivamente.

714
00:36:00,540 --> 00:36:04,460
Y así si quería buscar
mi hash de mesa y el acceso de la manzana,

715
00:36:04,460 --> 00:36:07,560
Sé manzana comienza con
una A, y sé exactamente

716
00:36:07,560 --> 00:36:10,860
que debe ser y el hash
mesa en el índice 0, porque

717
00:36:10,860 --> 00:36:13,620
de la función asignada previamente.

718
00:36:13,620 --> 00:36:16,572
>> Así que no sé, somos
un programa de usuario, donde

719
00:36:16,572 --> 00:36:18,780
se le acusa de
no arbitrarily-- arbitrariamente,

720
00:36:18,780 --> 00:36:22,530
con intentar pensativo
pensar en buenas ecuaciones

721
00:36:22,530 --> 00:36:25,460
ser capaz de propagarse
a cabo todos sus valores

722
00:36:25,460 --> 00:36:29,370
de manera que puedan acceder fácilmente
más adelante con como una ecuación

723
00:36:29,370 --> 00:36:31,130
que usted, usted mismo, saben.

724
00:36:31,130 --> 00:36:35,210
Así, en el sentido de que si quería ir a
mango, lo sé, oh, comienza con m.

725
00:36:35,210 --> 00:36:37,134
Debe ser en el índice de 12.

726
00:36:37,134 --> 00:36:38,800
Yo no tengo que buscar a través de cualquier cosa.

727
00:36:38,800 --> 00:36:42,080
Sé exactly-- tan sólo pudiera ir a
el índice de 12 y tire de eso.

728
00:36:42,080 --> 00:36:45,520
>> Todo el mundo clara sobre cómo un
La función de tabla hash funciona?

729
00:36:45,520 --> 00:36:48,380
Es una especie de sólo un conjunto más complejo.

730
00:36:48,380 --> 00:36:50,010
Eso es todo lo que es.

731
00:36:50,010 --> 00:36:51,630
OK.

732
00:36:51,630 --> 00:36:57,690
>> Así que supongo que nos encontramos
este tema de lo

733
00:36:57,690 --> 00:37:06,390
que pasa si tiene varias cosas
que le dan el mismo índice?

734
00:37:06,390 --> 00:37:10,570
Así que decir que nuestra función, todo lo que
hizo fue tomar esa primera carta

735
00:37:10,570 --> 00:37:14,490
y convertir eso en un
0 respectiva a través de 25 de índice.

736
00:37:14,490 --> 00:37:17,137
Eso es totalmente bien si
es suficiente con uno de cada uno.

737
00:37:17,137 --> 00:37:18,970
Pero el segundo de empezar
tener más, eres

738
00:37:18,970 --> 00:37:20,910
va a tener lo que se llama una colisión.

739
00:37:20,910 --> 00:37:25,580
>> Así que si trato de insertar enterrar en un hash
tabla que ya tiene el plátano en él,

740
00:37:25,580 --> 00:37:27,870
lo que va a pasar cuando
intenta insertar eso?

741
00:37:27,870 --> 00:37:30,930
Las cosas malas porque el plátano
que ya existe en el índice

742
00:37:30,930 --> 00:37:33,800
que desea almacenarlo en.

743
00:37:33,800 --> 00:37:35,560
Berry tipo de es como, ah, ¿qué hago?

744
00:37:35,560 --> 00:37:37,080
No sé a dónde ir.

745
00:37:37,080 --> 00:37:38,410
¿Cómo puedo solucionar esto?

746
00:37:38,410 --> 00:37:41,150
>> Y así ustedes harán clase de
vemos que hacemos esta cosa difícil

747
00:37:41,150 --> 00:37:44,810
donde podemos tipo de realidad
crear lista enlazada en nuestras matrices.

748
00:37:44,810 --> 00:37:46,840
Y así, la manera más fácil
para pensar en esto,

749
00:37:46,840 --> 00:37:50,830
todas tabla hash es una
variedad de listas enlazadas.

750
00:37:50,830 --> 00:37:55,670
Y así, en ese sentido, hay que
este hermoso arreglo de apuntadores,

751
00:37:55,670 --> 00:37:58,740
y luego cada puntero en
ese valor, en ese índice,

752
00:37:58,740 --> 00:38:00,740
en realidad puede apuntar a otras cosas.

753
00:38:00,740 --> 00:38:05,720
Y por lo que tiene todos estos separada
cadenas que salen de una gran variedad.

754
00:38:05,720 --> 00:38:07,960
>> Y aquí, si yo
querido insertar baya,

755
00:38:07,960 --> 00:38:11,220
Lo sé, OK, voy a la entrada
a través de mi función hash.

756
00:38:11,220 --> 00:38:15,070
Voy a terminar con el índice de
1, y luego me voy a ser capaz de tener

757
00:38:15,070 --> 00:38:20,410
sólo un subconjunto más pequeño de este
gigante diccionario de 140.000 palabras.

758
00:38:20,410 --> 00:38:24,220
Y entonces puedo simplemente mirar
a través de 1/26 de eso.

759
00:38:24,220 --> 00:38:27,910
>> Y así entonces puedo basta con insertar
baya ya sea antes o después de plátano

760
00:38:27,910 --> 00:38:28,820
¿en este caso?

761
00:38:28,820 --> 00:38:29,700
Después, ¿verdad?

762
00:38:29,700 --> 00:38:33,920
Y por lo que vamos a querer
insertar este nodo después de plátano,

763
00:38:33,920 --> 00:38:36,667
y así vas a insertar
a la cola de la lista enlazada.

764
00:38:36,667 --> 00:38:38,500
Voy a volver
a esta diapositiva anterior,

765
00:38:38,500 --> 00:38:40,680
así que ustedes pueden ver cómo
función hash funciona.

766
00:38:40,680 --> 00:38:43,980
>> Así función hash es esta ecuación
que se está ejecutando la clase de su entrada

767
00:38:43,980 --> 00:38:46,940
a través de conseguir lo Índice
que desea asignar la directa hacia.

768
00:38:46,940 --> 00:38:51,130
Y así, en este ejemplo, todo lo que queríamos
que hacer era tomar la primera letra,

769
00:38:51,130 --> 00:38:55,890
convertir eso en un índice, entonces nosotros
puede almacenar que en nuestra función hash.

770
00:38:55,890 --> 00:39:00,160
Todo lo que estamos haciendo aquí es que estamos
la conversión de la primera letra.

771
00:39:00,160 --> 00:39:04,770
Así KeyKey [0] es sólo la primera letra
de cualquier cadena que estamos teniendo,

772
00:39:04,770 --> 00:39:05,720
estamos pasando.

773
00:39:05,720 --> 00:39:09,740
Estamos convertir eso a superior, y
estamos restando por mayúsculas A,

774
00:39:09,740 --> 00:39:11,740
así que todo lo que está haciendo
nos está dando una serie

775
00:39:11,740 --> 00:39:13,670
en el que podemos hash de nuestros valores en.

776
00:39:13,670 --> 00:39:16,550
>> Y luego vamos a
volver picadillo TAMAÑO módulo.

777
00:39:16,550 --> 00:39:19,340
Sea muy, muy cuidadoso
porque, en teoría, aquí

778
00:39:19,340 --> 00:39:21,870
su valor hash podría ser infinita.

779
00:39:21,870 --> 00:39:23,660
Sólo podría seguir y seguir y seguir.

780
00:39:23,660 --> 00:39:26,080
Podría ser algo realmente,
muy grande valor,

781
00:39:26,080 --> 00:39:29,849
sino porque su tabla hash que
usted ha creado solamente cuenta con 26 índices,

782
00:39:29,849 --> 00:39:31,890
usted quiere asegurarse de que su
modulusing para que

783
00:39:31,890 --> 00:39:33,848
no run-- es lo mismo
cosa como su queue--

784
00:39:33,848 --> 00:39:36,320
para que no se quede fuera de la
parte inferior de la función hash.

785
00:39:36,320 --> 00:39:39,210
>> Usted quiere envolverlo vuelta
del mismo modo en [inaudible] cuando

786
00:39:39,210 --> 00:39:41,750
que tenía como un muy,
gran carta,

787
00:39:41,750 --> 00:39:43,740
no quiero que eso
basta con ejecutar fuera de la final.

788
00:39:43,740 --> 00:39:46,948
Lo mismo aquí, usted quiere asegurarse de
no se ejecuta fuera de la final envolviendo

789
00:39:46,948 --> 00:39:48,330
alrededor de la parte superior de la tabla.

790
00:39:48,330 --> 00:39:50,530
Así que esto es sólo una muy
función hash simple.

791
00:39:50,530 --> 00:39:56,570
Todo lo que hizo fue tomar la primera
carta de cualquiera que sea nuestra entrada era

792
00:39:56,570 --> 00:40:01,660
y convertir eso en un índice que
podríamos poner en nuestra tabla hash.

793
00:40:01,660 --> 00:40:05,450
>> Sí, y así como he dicho antes,
la forma en que resolvemos colisiones

794
00:40:05,450 --> 00:40:09,330
en nuestro hash de mesas están teniendo,
lo que llamamos, encadenamiento.

795
00:40:09,330 --> 00:40:13,860
Así que si usted intenta insertar múltiples
palabras que comienzan con la misma cosa,

796
00:40:13,860 --> 00:40:16,145
usted va a tener un valor hash.

797
00:40:16,145 --> 00:40:18,770
Aguacates y manzana, si tienes
ejecutar a través de nuestra función hash,

798
00:40:18,770 --> 00:40:21,450
se va a dar la
mismo número, el número de 0.

799
00:40:21,450 --> 00:40:24,550
Y así, la forma en que resolver esto es
que podemos realmente bueno de vincularlos

800
00:40:24,550 --> 00:40:27,010
sí a través de listas enlazadas.

801
00:40:27,010 --> 00:40:29,600
>> Y así, en este sentido,
ustedes pueden ver tipo

802
00:40:29,600 --> 00:40:32,640
de cómo las estructuras de datos que
hemos estado estableciendo previamente

803
00:40:32,640 --> 00:40:35,870
como una pasa ligado lista tipo
de pueden unirse en una sola.

804
00:40:35,870 --> 00:40:38,860
Y entonces usted puede crear ahora
estructuras de datos más eficientes

805
00:40:38,860 --> 00:40:43,350
que puede manejar grandes cantidades de
datos, cambiar el tamaño de forma dinámica en función

806
00:40:43,350 --> 00:40:44,870
de sus necesidades.

807
00:40:44,870 --> 00:40:45,620
Todo el mundo claro?

808
00:40:45,620 --> 00:40:47,580
Todo el mundo la clase de clara
en lo que sucede aquí?

809
00:40:47,580 --> 00:40:52,110
>> Si quería insert-- lo que es un
fruta que empieza con, no sé,

810
00:40:52,110 --> 00:40:54,726
B, con excepción de la baya, plátano.

811
00:40:54,726 --> 00:40:55,710
>> AUDIENCIA: Blackberry.

812
00:40:55,710 --> 00:40:57,910
>> ANDI Peng: Blackberry, blackberry.

813
00:40:57,910 --> 00:41:00,530
¿De dónde viene la zarzamora ir aquí?

814
00:41:00,530 --> 00:41:04,251
Bueno, en realidad no hemos clasificado
esto todavía, pero teóricamente

815
00:41:04,251 --> 00:41:06,250
si queríamos tener este
en orden alfabético,

816
00:41:06,250 --> 00:41:07,944
donde la mora se debe ir?

817
00:41:07,944 --> 00:41:09,210
>> AUDIENCIA: [inaudible]

818
00:41:09,210 --> 00:41:11,100
>> ANDI Peng: Exactamente, después de aquí, ¿no?

819
00:41:11,100 --> 00:41:14,950
Pero ya que es muy difícil
reorder-- Supongo que depende de ustedes.

820
00:41:14,950 --> 00:41:17,920
Ustedes pueden totalmente
implementar lo que quieras.

821
00:41:17,920 --> 00:41:20,730
La forma más eficiente
de hacer esto quizá

822
00:41:20,730 --> 00:41:24,570
sería para ordenar tu vinculados
una lista en orden alfabético,

823
00:41:24,570 --> 00:41:26,520
y así cuando estás
insertando cosas, desea

824
00:41:26,520 --> 00:41:28,632
para asegurarse de insertarlos
en orden alfabético

825
00:41:28,632 --> 00:41:30,590
para que luego, cuando esté
tratando de buscar ellos,

826
00:41:30,590 --> 00:41:32,410
usted no tiene que atravesar todo.

827
00:41:32,410 --> 00:41:35,290
Usted sabe exactamente donde
que es, y que es más fácil.

828
00:41:35,290 --> 00:41:39,100
>> Pero si que tipo de tener
cosas entremezcladas al azar,

829
00:41:39,100 --> 00:41:41,420
usted todavía va a tener
para atravesar todos modos.

830
00:41:41,420 --> 00:41:44,990
Y así, si quería simplemente
inserte blackberry aquí

831
00:41:44,990 --> 00:41:47,470
y quería buscar
que, sé, oh, blackberry

832
00:41:47,470 --> 00:41:52,012
debe comenzar con el índice de 1, así que
saber instantáneamente sólo la búsqueda en 1.

833
00:41:52,012 --> 00:41:53,970
Y entonces puedo clase de
recorrer la lista enlazada

834
00:41:53,970 --> 00:41:56,120
hasta que llegue a la mora,
y entonces-- ¿sí?

835
00:41:56,120 --> 00:41:59,550
>> AUDIENCIA: Si usted está tratando de create--
Supongo que esta es una muy simple de hash

836
00:41:59,550 --> 00:42:00,050
función.

837
00:42:00,050 --> 00:42:02,835
Y si lo que queríamos hacer
múltiples capas de que al igual que,

838
00:42:02,835 --> 00:42:05,870
OK, queremos separar en
como todas las letras del alfabeto

839
00:42:05,870 --> 00:42:09,040
y luego otra vez a como otro conjunto
de las letras del alfabeto en que,

840
00:42:09,040 --> 00:42:11,715
estamos poniendo como un hash
tabla dentro de una tabla hash,

841
00:42:11,715 --> 00:42:13,256
o como una función dentro de una función?

842
00:42:13,256 --> 00:42:14,880
¿O es que--

843
00:42:14,880 --> 00:42:17,510
>> ANDI Peng: Así que su picadillo
function-- su tabla hash

844
00:42:17,510 --> 00:42:19,360
puede ser tan grande como usted desea.

845
00:42:19,360 --> 00:42:21,930
Así que en este sentido, pensé
fue muy fácil, muy

846
00:42:21,930 --> 00:42:25,320
simple para mí basan sólo una especie
en letras de la primera palabra.

847
00:42:25,320 --> 00:42:28,690
Y así, sólo hay 26 opciones.

848
00:42:28,690 --> 00:42:32,650
Sólo puedo obtener 26 opciones de
0 a 25, ya que sólo puede

849
00:42:32,650 --> 00:42:36,510
comenzar de la A a la Z. Pero Si querías
añadir, tal vez, una mayor complejidad

850
00:42:36,510 --> 00:42:39,260
o más rápido el tiempo de ejecución de su
tabla hash, a pesar de todo

851
00:42:39,260 --> 00:42:40,760
puede hacer todo tipo de cosas.

852
00:42:40,760 --> 00:42:43,330
Usted puede hacer su propio
ecuación que le da

853
00:42:43,330 --> 00:42:48,000
más distribución en su
palabras, entonces cuando usted busca,

854
00:42:48,000 --> 00:42:49,300
que va a ser más rápido.

855
00:42:49,300 --> 00:42:52,100
>> Es totalmente de ustedes
cómo desea implementar eso.

856
00:42:52,100 --> 00:42:55,140
Piense en ello como sólo cubos.

857
00:42:55,140 --> 00:42:57,376
Si yo quería tener
26 cubos, voy

858
00:42:57,376 --> 00:42:59,420
para ordenar las cosas en esos cubos.

859
00:42:59,420 --> 00:43:02,980
Pero yo voy a tener un montón
de cosas en cada cubo,

860
00:43:02,980 --> 00:43:05,890
así que si usted quiere que sea
más rápido y más eficiente,

861
00:43:05,890 --> 00:43:07,190
dame cien cubos.

862
00:43:07,190 --> 00:43:09,290
>> Pero entonces usted tiene que encontrar una
manera de ordenar las cosas por lo que son

863
00:43:09,290 --> 00:43:11,040
en el cubo adecuado deben estar en.

864
00:43:11,040 --> 00:43:13,331
Pero luego, cuando en realidad
que desee ver en el cubo,

865
00:43:13,331 --> 00:43:16,410
que es mucho más rápido porque hay
menos cosas en cada cubo.

866
00:43:16,410 --> 00:43:20,250
Y así, sí, eso es en realidad
el truco para ustedes en pset5

867
00:43:20,250 --> 00:43:22,360
es que podrás
el reto de crear sólo

868
00:43:22,360 --> 00:43:26,170
todo lo que es el más eficiente
función que se pueda imaginar para ser

869
00:43:26,170 --> 00:43:28,520
capaz de almacenar y comprobar estos valores.

870
00:43:28,520 --> 00:43:30,840
>> Totalmente de ustedes
sin embargo usted quiere hacerlo,

871
00:43:30,840 --> 00:43:32,229
pero eso es un muy buen punto.

872
00:43:32,229 --> 00:43:34,520
Que el tipo de lógica que
quiero empezar a pensar en

873
00:43:34,520 --> 00:43:37,236
es, también, por qué no puedo hacer más cubos.

874
00:43:37,236 --> 00:43:39,527
Y entonces tengo que buscar
menos cosas, y entonces tal vez

875
00:43:39,527 --> 00:43:41,640
tener una función de hash diferente.

876
00:43:41,640 --> 00:43:45,500
>> Sí, hay un montón de maneras de hacer esto
pset, algunos son más rápidos que otros.

877
00:43:45,500 --> 00:43:50,630
Estoy totalmente de ir a ver lo
fue rápido los chicos de más rápido voluntad

878
00:43:50,630 --> 00:43:55,170
ser capaz de obtener sus funciones para trabajar.

879
00:43:55,170 --> 00:43:58,176
OK, todos bien en
tablas de encadenamiento y croquetas?

880
00:43:58,176 --> 00:44:00,800
En realidad es como un muy simple
concepto, si se piensa en ello.

881
00:44:00,800 --> 00:44:05,160
Todo lo que es es lo que separa
sus entradas son en cubos,

882
00:44:05,160 --> 00:44:10,670
clasificarlos, y luego buscar el
listas que no está asociada con.

883
00:44:10,670 --> 00:44:11,852
>> Guay.

884
00:44:11,852 --> 00:44:18,160
Muy bien, ahora tenemos una especie diferente
de estructura de datos que se llama un árbol.

885
00:44:18,160 --> 00:44:20,850
Sigamos y hablar de intentos
que son claramente diferentes,

886
00:44:20,850 --> 00:44:22,330
pero en la misma categoría.

887
00:44:22,330 --> 00:44:29,010
Esencialmente, todo es un árbol en lugar
de organizar los datos en la forma lineal

888
00:44:29,010 --> 00:44:32,560
que una tabla hash que does--
sabemos, tiene una parte superior y una parte inferior

889
00:44:32,560 --> 00:44:37,900
y que tipo de enlace fuera de it-- un
árbol tiene un superior que se llama a la raíz,

890
00:44:37,900 --> 00:44:40,220
y entonces tiene hojas a su alrededor.

891
00:44:40,220 --> 00:44:42,390
>> Y así, todo lo que tienes aquí
es sólo el nodo superior

892
00:44:42,390 --> 00:44:45,980
que apunta a otros nodos, que los puntos
a más nodos, y así sucesivamente y así sucesivamente.

893
00:44:45,980 --> 00:44:48,130
Y por lo que sólo tiene ramas de división.

894
00:44:48,130 --> 00:44:53,255
Es sólo una forma diferente de organizar
datos, y porque lo llamamos un árbol,

895
00:44:53,255 --> 00:44:56,270
ustedes solo-- es sólo
modelada a buscar un árbol.

896
00:44:56,270 --> 00:44:57,670
Es por eso que lo llamamos árboles.

897
00:44:57,670 --> 00:44:59,370
>> Tabla hash se parece a una tabla.

898
00:44:59,370 --> 00:45:01,310
Un árbol sólo se parece a un árbol.

899
00:45:01,310 --> 00:45:03,300
Todo lo que es es una separada
forma de organizar los nodos

900
00:45:03,300 --> 00:45:06,020
dependiendo de cuáles son sus necesidades.

901
00:45:06,020 --> 00:45:11,810
>> Así que hay una raíz y
entonces usted tiene hojas.

902
00:45:11,810 --> 00:45:15,380
La forma en que podemos particular
pensar en ello es un árbol binario,

903
00:45:15,380 --> 00:45:18,150
un árbol binario es sólo una
tipo específico de un árbol

904
00:45:18,150 --> 00:45:22,450
donde cada nodo únicos puntos
que, en el máximo, otros dos nodos.

905
00:45:22,450 --> 00:45:25,434
Y así que aquí tenéis distinta
simetría en su árbol

906
00:45:25,434 --> 00:45:28,600
que hace que sea más fácil de tipo de mirada
en qué valores son porque entonces

907
00:45:28,600 --> 00:45:30,150
tener siempre a la izquierda o la derecha.

908
00:45:30,150 --> 00:45:33,150
Nunca hay como una tercera izquierda desde
la izquierda o cuarto desde la izquierda.

909
00:45:33,150 --> 00:45:36,358
Es sólo usted tiene una izquierda y una derecha
y usted puede buscar cualquiera de los dos.

910
00:45:36,358 --> 00:45:38,980
Y ¿por qué es esto útil?

911
00:45:38,980 --> 00:45:40,980
La forma en que esto es
útil es que si estás buscando

912
00:45:40,980 --> 00:45:42,890
para buscar a través de valores, ¿no?

913
00:45:42,890 --> 00:45:45,640
En lugar de implementar binario
buscar en una matriz de error,

914
00:45:45,640 --> 00:45:49,260
si usted quiere ser capaz de insertar nodos
y quitarle nodos a voluntad y también

915
00:45:49,260 --> 00:45:52,185
preservar la búsqueda
capacidades de búsqueda binaria.

916
00:45:52,185 --> 00:45:54,560
Así de esta manera, estamos tipo de
tricking-- recordar cuando nos

917
00:45:54,560 --> 00:45:56,530
dicho listas enlazadas no puede binario de búsqueda?

918
00:45:56,530 --> 00:46:01,700
Estamos especie de la creación de una estructura de datos
que trucos que a trabajar.

919
00:46:01,700 --> 00:46:05,034
>> Y las listas porque vinculados son lineales,
que sólo enlazan uno después del otro.

920
00:46:05,034 --> 00:46:06,950
Podemos tipo de tener
diferente tipo de punteros

921
00:46:06,950 --> 00:46:09,408
que apuntan a diferentes nodos
que nos puede ayudar con la búsqueda.

922
00:46:09,408 --> 00:46:12,590
Y aquí, si quería
tener un árbol de búsqueda binaria,

923
00:46:12,590 --> 00:46:14,090
Yo sé que mi medio si 55.

924
00:46:14,090 --> 00:46:18,280
Yo sólo voy a crear ese
como mi medio, como mi raíz,

925
00:46:18,280 --> 00:46:20,770
y luego me voy a tener
valores giran fuera de ella.

926
00:46:20,770 --> 00:46:25,610
>> Así que aquí, si yo voy a buscar
el valor de 66, puedo comenzar a los 55.

927
00:46:25,610 --> 00:46:27,310
Es 66 mayor que 55?

928
00:46:27,310 --> 00:46:30,970
Sí lo es, así que sé que busco mus
i n el puntero derecho de este árbol.

929
00:46:30,970 --> 00:46:32,440
Voy al 77.

930
00:46:32,440 --> 00:46:35,367
OK, es 66 menor o mayor que 77?

931
00:46:35,367 --> 00:46:37,950
Es menor que, por lo que sé, oh,
que tiene que ser el nodo de la izquierda.

932
00:46:37,950 --> 00:46:41,410
>> Así que aquí estamos tipo de preservación
todas las grandes cosas acerca de matrices,

933
00:46:41,410 --> 00:46:44,420
así como el cambio de tamaño dinámico
de objetos, siendo

934
00:46:44,420 --> 00:46:49,530
capaz de insertar y eliminar a voluntad,
sin tener que preocuparse por el fijo

935
00:46:49,530 --> 00:46:50,370
cantidad de espacio.

936
00:46:50,370 --> 00:46:52,820
Todavía conservamos todos
esas cosas maravillosas

937
00:46:52,820 --> 00:46:57,140
al mismo tiempo ser capaz de preservar la
registrar y buscar el tiempo de búsqueda binaria

938
00:46:57,140 --> 00:47:00,450
que sólo estábamos previamente
capaz de obtener una frase.

939
00:47:00,450 --> 00:47:06,310
>> Estructura de datos fresca, tipo de
complejo de implementar, el nodo.

940
00:47:06,310 --> 00:47:08,311
Como se puede ver, todo lo que
es la estructura del nodo

941
00:47:08,311 --> 00:47:10,143
es que usted tiene a la izquierda
y un puntero derecho.

942
00:47:10,143 --> 00:47:11,044
Eso es todo lo que es.

943
00:47:11,044 --> 00:47:12,960
Así que en lugar de sólo
que tiene una x o una anterior.

944
00:47:12,960 --> 00:47:15,920
Usted tiene una izquierda o una derecha y luego
puedes tipo de enlazarlos

945
00:47:15,920 --> 00:47:16,836
Sin embargo así lo desea.

946
00:47:16,836 --> 00:47:21,080

947
00:47:21,080 --> 00:47:24,270
>> OK, estamos en realidad va
simplemente tomar unos minutos.

948
00:47:24,270 --> 00:47:25,790
Así que vamos a volver aquí.

949
00:47:25,790 --> 00:47:28,270
Como he dicho anteriormente,
Yo como que expliqué

950
00:47:28,270 --> 00:47:31,520
la lógica detrás de la forma en que
sería buscar a través de esto.

951
00:47:31,520 --> 00:47:33,860
Vamos a tratar
pseudocoding esto a ver

952
00:47:33,860 --> 00:47:38,000
si podemos aplicar el tipo de
misma lógica de búsqueda binaria

953
00:47:38,000 --> 00:47:40,055
a un tipo diferente de estructura de datos.

954
00:47:40,055 --> 00:47:45,049
Si ustedes quieren tomar como una pareja
minutos para sólo pensar en esto.

955
00:47:45,049 --> 00:48:45,927

956
00:48:45,927 --> 00:48:46,925
OK.

957
00:48:46,925 --> 00:48:51,407
Muy bien, voy a
en realidad sólo le dan el-- no,

958
00:48:51,407 --> 00:48:52,990
hablaremos sobre el pseudocódigo primero.

959
00:48:52,990 --> 00:48:56,580
Así que no quiere que nadie
para dar una puñalada en lo

960
00:48:56,580 --> 00:49:02,100
lo primero que quiere hacer cuando
usted está comenzando la búsqueda es?

961
00:49:02,100 --> 00:49:04,460
Si estamos buscando
el valor de 66, lo que es

962
00:49:04,460 --> 00:49:07,940
lo primero que queremos hacer en caso de
queremos binario buscar este árbol?

963
00:49:07,940 --> 00:49:10,760
>> AUDIENCIA: ¿Quieres ver a la derecha
y buscar izquierda y ver [inaudible]

964
00:49:10,760 --> 00:49:11,230
mayor número.

965
00:49:11,230 --> 00:49:12,271
>> ANDI Peng: Sí, exactamente.

966
00:49:12,271 --> 00:49:15,350
Así que vamos a mirar a su raíz.

967
00:49:15,350 --> 00:49:18,180
Hay un montón de maneras que usted puede llamar
que, dicen a su gente nodo padre.

968
00:49:18,180 --> 00:49:21,317
Me gusta decir que la raíz porque
eso es como la raíz del árbol.

969
00:49:21,317 --> 00:49:23,400
Usted va a mirar
el nodo raíz, y ya está

970
00:49:23,400 --> 00:49:26,940
vamos a ver es 66 mayor
que o menor que 55.

971
00:49:26,940 --> 00:49:30,360
Y si es mayor que, además, es
mayor que, ¿hacia dónde queremos ver?

972
00:49:30,360 --> 00:49:32,000
¿Dónde queremos buscar, ¿no?

973
00:49:32,000 --> 00:49:34,340
Queremos buscar la
mitad derecha de este árbol.

974
00:49:34,340 --> 00:49:38,390
>> Así tenemos que, convenientemente, un
puntero que apunta a la derecha.

975
00:49:38,390 --> 00:49:44,325
Y así entonces podemos establecer
nuestra nueva raíz para ser 77.

976
00:49:44,325 --> 00:49:46,450
Sólo podemos ir a donde quiera
el puntero está apuntando.

977
00:49:46,450 --> 00:49:49,100
Bueno, oh, aquí estamos empezando
a los 77, y podemos simplemente

978
00:49:49,100 --> 00:49:51,172
hacer esto de forma recursiva y otra vez.

979
00:49:51,172 --> 00:49:52,880
De esta manera, usted clase
de tener una función.

980
00:49:52,880 --> 00:49:57,430
Usted tiene una manera de buscar que
simplemente puede repetir una y otra y otra vez,

981
00:49:57,430 --> 00:50:02,720
dependiendo de donde quieres buscar
hasta que finalmente llegue al valor

982
00:50:02,720 --> 00:50:04,730
que usted está buscando.

983
00:50:04,730 --> 00:50:05,230
¿Tener sentido?

984
00:50:05,230 --> 00:50:07,800
>> Estoy a punto de mostrar que el actual
código, y es una gran cantidad de código.

985
00:50:07,800 --> 00:50:08,674
No hay necesidad de asuste.

986
00:50:08,674 --> 00:50:09,910
Hablaremos a través de él.

987
00:50:09,910 --> 00:50:13,410

988
00:50:13,410 --> 00:50:14,020
>> En realidad no.

989
00:50:14,020 --> 00:50:15,061
Eso fue sólo pseudocódigo.

990
00:50:15,061 --> 00:50:17,860
OK, eso fue sólo el pseudocódigo,
que es un poco complejo,

991
00:50:17,860 --> 00:50:19,751
pero es totalmente bien.

992
00:50:19,751 --> 00:50:21,000
Todo el mundo siguiendo a lo largo de aquí?

993
00:50:21,000 --> 00:50:24,260
Si la raíz es nulo, el regreso
falso, porque eso significa

994
00:50:24,260 --> 00:50:26,850
que ni siquiera tiene nada allí.

995
00:50:26,850 --> 00:50:31,376
>> Si la raíz n es el valor, por lo que si
pasa a ser el que usted está mirando,

996
00:50:31,376 --> 00:50:34,000
entonces usted va a devolver true
porque sabes que lo has visto.

997
00:50:34,000 --> 00:50:36,250
Pero si el valor es menor
a raíz de n, eres

998
00:50:36,250 --> 00:50:38,332
ir a buscar a la izquierda
niño o la hoja izquierda,

999
00:50:38,332 --> 00:50:39,540
lo que quieras llamarlo.

1000
00:50:39,540 --> 00:50:41,750
Y si el valor es mayor que la raíz,
usted va a buscar el árbol adecuado,

1001
00:50:41,750 --> 00:50:44,610
luego simplemente ejecutar la función
a través de la búsqueda de nuevo.

1002
00:50:44,610 --> 00:50:48,037
>> Y si la raíz es nulo, que esa
significa que ha llegado al final?

1003
00:50:48,037 --> 00:50:50,120
Eso significa que no tiene
más más hojas para buscar,

1004
00:50:50,120 --> 00:50:52,230
entonces usted sabe, oh,
supongo que no hay aquí

1005
00:50:52,230 --> 00:50:55,063
porque después he mirado a través
todo el asunto y no está aquí,

1006
00:50:55,063 --> 00:50:56,930
que sólo podría no estar aquí.

1007
00:50:56,930 --> 00:50:58,350
>> ¿Eso tiene sentido para todo el mundo?

1008
00:50:58,350 --> 00:51:03,230
Así es como la búsqueda binaria preservar
las capacidades de listas enlazadas.

1009
00:51:03,230 --> 00:51:09,200
Fresco, por lo que el segundo tipo
de la estructura de datos que ustedes

1010
00:51:09,200 --> 00:51:13,180
puede probar la aplicación en su conjunto de procesadores,
sólo tienes que elegir un método.

1011
00:51:13,180 --> 00:51:19,430
Pero tal vez un método alternativo para
la tabla hash es lo que llamamos un trie.

1012
00:51:19,430 --> 00:51:24,080
>> Todo un trie es un
tipo específico de árbol que

1013
00:51:24,080 --> 00:51:28,600
tiene valores que van a otros valores.

1014
00:51:28,600 --> 00:51:31,450
Así que en lugar de tener un binario
árbol en el sentido de que sólo uno

1015
00:51:31,450 --> 00:51:35,940
Lo puede apuntar a dos, usted puede tener
punto de una cosa a muchas, muchas cosas.

1016
00:51:35,940 --> 00:51:39,450
Usted esencialmente tiene arrays
dentro de los cuales se almacenan

1017
00:51:39,450 --> 00:51:41,790
punteros que apuntan a otras matrices.

1018
00:51:41,790 --> 00:51:45,210

1019
00:51:45,210 --> 00:51:49,460
>> Así que el nodo de la forma en que
definiría un trie

1020
00:51:49,460 --> 00:51:52,590
es que queremos tener un
Boole, c palabra, ¿verdad?

1021
00:51:52,590 --> 00:51:54,920
Así que el nodo es de Boole
como verdadera o falsa,

1022
00:51:54,920 --> 00:51:58,490
en primer lugar a la cabeza de
esa matriz, se trata de una palabra?

1023
00:51:58,490 --> 00:52:03,620
En segundo lugar, usted quiere tener punteros
a lo que el resto de ellos lo son.

1024
00:52:03,620 --> 00:52:07,470
Un poco complejo, un poco abstracto, pero
Voy a explicar lo que todos los medios.

1025
00:52:07,470 --> 00:52:13,800
>> Así que aquí, en la parte superior, si
tiene un arsenal ya declaró,

1026
00:52:13,800 --> 00:52:17,040
un nodo donde se tiene una de Boole
valor almacenado en la parte delantera

1027
00:52:17,040 --> 00:52:19,490
que le dice que es esta una palabra?

1028
00:52:19,490 --> 00:52:20,520
¿No es esto una palabra?

1029
00:52:20,520 --> 00:52:23,240
Y entonces usted tiene la
resto de su matriz que

1030
00:52:23,240 --> 00:52:26,040
realmente almacena toda la
posibilidades de lo que podría ser.

1031
00:52:26,040 --> 00:52:28,660
Así, por ejemplo, como
en la parte superior que tiene

1032
00:52:28,660 --> 00:52:32,140
lo primero que dice verdad o
falso, sí o no, se trata de una palabra.

1033
00:52:32,140 --> 00:52:38,130
>> Y entonces usted tiene de 0 a 26 de
las letras que se pueden almacenar.

1034
00:52:38,130 --> 00:52:42,790
Si quisiera buscar aquí
de palo, me voy a la parte superior

1035
00:52:42,790 --> 00:52:49,200
y busco B. Encuentro B en mi
matriz, y por lo que sé, está bien, es B una palabra?

1036
00:52:49,200 --> 00:52:53,010
B no es una palabra, por lo tanto,
Tengo que seguir buscando.

1037
00:52:53,010 --> 00:52:56,410
Voy de B, y miro a la
puntero que apunta hacia B

1038
00:52:56,410 --> 00:53:00,900
y veo otra gama de información,
la misma estructura que teníamos antes.

1039
00:53:00,900 --> 00:53:05,240
>> Y aquí-- oh, la próxima
carta en la [inaudible] es A.

1040
00:53:05,240 --> 00:53:07,210
Así que miramos en esa matriz.

1041
00:53:07,210 --> 00:53:10,860
Nos encontramos con el octavo valor,
y luego miramos a ver, oh,

1042
00:53:10,860 --> 00:53:12,840
bueno, es que una palabra, es B-A una palabra?

1043
00:53:12,840 --> 00:53:13,807
No es una palabra.

1044
00:53:13,807 --> 00:53:14,890
Tenemos que seguir buscando.

1045
00:53:14,890 --> 00:53:17,850
>> Y así entonces miramos hacia donde
el puntero de un puntos,

1046
00:53:17,850 --> 00:53:21,130
y apunta a otra forma en
que tenemos más valor almacenado.

1047
00:53:21,130 --> 00:53:24,150
Y, finalmente, llegamos a
B-A-T, que es una palabra.

1048
00:53:24,150 --> 00:53:25,970
Y así, la próxima vez
se mira, vas

1049
00:53:25,970 --> 00:53:30,850
para tener el registro de entrada de, sí,
esta función booleana es verdadera.

1050
00:53:30,850 --> 00:53:35,450
Y así, en el sentido de que estamos tipo
de tener un árbol con matrices.

1051
00:53:35,450 --> 00:53:39,890
>> Así que usted puede clase de búsqueda abajo.

1052
00:53:39,890 --> 00:53:43,650
En lugar de una función de hash y
la asignación de valores de lista enlazada,

1053
00:53:43,650 --> 00:53:49,190
que sólo puede poner en práctica un
trie que busca downwords.

1054
00:53:49,190 --> 00:53:50,850
Muy, muy complicado las cosas.

1055
00:53:50,850 --> 00:53:54,060
No es fácil de pensar, porque yo soy como
escupir tantas estructuras de datos fuera

1056
00:53:54,060 --> 00:53:58,710
a ti, pero lo hace a todos tipo de
entender cómo funciona la lógica de esto?

1057
00:53:58,710 --> 00:54:01,920
>> Vale, guay.

1058
00:54:01,920 --> 00:54:05,600
Así B-A-T, y luego
usted va a buscar.

1059
00:54:05,600 --> 00:54:07,940
La próxima vez que te vas
para ver, oh, bueno, eso es cierto,

1060
00:54:07,940 --> 00:54:09,273
por lo tanto sé que esto debe ser una palabra.

1061
00:54:09,273 --> 00:54:12,030

1062
00:54:12,030 --> 00:54:13,770
>> Lo mismo para el zoológico.

1063
00:54:13,770 --> 00:54:17,960
Así que aquí está la cosa ahora mismo, si
querido buscar zoológico, en este momento,

1064
00:54:17,960 --> 00:54:20,780
Actualmente zoológico no es un
palabra en el diccionario

1065
00:54:20,780 --> 00:54:25,300
porque, como ustedes pueden ver, el
primer lugar que tenemos un booleano

1066
00:54:25,300 --> 00:54:28,590
return true es al final del zoom.

1067
00:54:28,590 --> 00:54:30,430
Tenemos Z-O-O-M.

1068
00:54:30,430 --> 00:54:33,900
>> Y aquí, no en realidad tenemos
la palabra, el zoológico, en el diccionario

1069
00:54:33,900 --> 00:54:36,070
porque esta casilla no está marcada.

1070
00:54:36,070 --> 00:54:39,540
Así que el equipo no
saber que el zoológico es una palabra

1071
00:54:39,540 --> 00:54:42,430
porque la forma en que hemos
almacenada, sólo un zoom aquí

1072
00:54:42,430 --> 00:54:44,920
en realidad tiene un valor booleano
eso se ha convertido cierto.

1073
00:54:44,920 --> 00:54:49,380
Así que si queremos insertar el
palabra, parque zoológico, en nuestro diccionario,

1074
00:54:49,380 --> 00:54:51,770
¿cómo podríamos ir haciendo eso?

1075
00:54:51,770 --> 00:54:55,960
¿Qué tenemos que hacer para asegurarnos de que nuestro
computadora sabe que Z-O-O es una palabra

1076
00:54:55,960 --> 00:54:58,130
y no es la primera palabra es Z-O-O-M?

1077
00:54:58,130 --> 00:54:59,360
>> AUDIENCIA: [inaudible]

1078
00:54:59,360 --> 00:55:01,450
>> ANDI Peng: Exactamente, nos
querrá asegurarse de que este

1079
00:55:01,450 --> 00:55:07,890
aquí, que el valor booleano es
comprobar fuera de que es verdad.

1080
00:55:07,890 --> 00:55:13,297
Z-O-O, a continuación, vamos a comprobar que,
así que sabemos exactamente, hey, el zoológico es una palabra.

1081
00:55:13,297 --> 00:55:15,380
Voy a decirle al
equipo que es una palabra tan

1082
00:55:15,380 --> 00:55:18,000
que cuando los controles informáticos,
se sabe que el zoológico es una palabra.

1083
00:55:18,000 --> 00:55:21,269
>> Debido a recordar todos estos datos
estructuras, es muy fácil para nosotros

1084
00:55:21,269 --> 00:55:22,310
decir, oh, bate de una palabra.

1085
00:55:22,310 --> 00:55:22,851
Zoo es una palabra.

1086
00:55:22,851 --> 00:55:23,611
Ampliar una palabra.

1087
00:55:23,611 --> 00:55:25,860
Pero cuando usted está construyendo él,
el equipo tiene ni idea.

1088
00:55:25,860 --> 00:55:28,619
>> Así que tienes que decirle exactamente
¿en qué punto se trata de una palabra?

1089
00:55:28,619 --> 00:55:29,910
¿En qué punto no es que una palabra?

1090
00:55:29,910 --> 00:55:31,784
Y ¿en qué momento hacer yo
que buscar cosas,

1091
00:55:31,784 --> 00:55:34,000
y en qué momento qué tengo que ir ahora?

1092
00:55:34,000 --> 00:55:37,010
Todo el mundo clara de eso?

1093
00:55:37,010 --> 00:55:39,540
Guay.

1094
00:55:39,540 --> 00:55:42,530
>> Y entonces viene la
problema de cómo lo haríamos

1095
00:55:42,530 --> 00:55:45,560
ir sobre la inserción de algo
que en realidad no está ahí?

1096
00:55:45,560 --> 00:55:49,090
Así que digamos que queremos insertar
la palabra, baño, en nuestra trie.

1097
00:55:49,090 --> 00:55:53,589
Como ustedes pueden ver como actualmente
todo lo que tenemos ahora es B-A-T,

1098
00:55:53,589 --> 00:55:55,630
y esta nueva estructura de datos
Tenía una pinta que

1099
00:55:55,630 --> 00:55:59,740
señalado nula porque suponemos
que, oh, no hay palabras después de B-A-T,

1100
00:55:59,740 --> 00:56:02,530
¿por qué necesitamos para mantener
tener las cosas después de que T.

1101
00:56:02,530 --> 00:56:06,581
>> Pero el problema surge si hacemos que
quiero tener una palabra que viene después

1102
00:56:06,581 --> 00:56:07,080
del T.

1103
00:56:07,080 --> 00:56:09,500
Si usted tiene baño, eres
va a querer un derecho H.

1104
00:56:09,500 --> 00:56:13,290
Y así el camino que vamos a hacer eso es
vamos a crear un nodo separado.

1105
00:56:13,290 --> 00:56:16,840
No estamos asignamos cualquier cantidad
de la memoria de esta nueva matriz,

1106
00:56:16,840 --> 00:56:20,720
y vamos a asignar punteros.

1107
00:56:20,720 --> 00:56:22,947
>> Vamos a asignar el
H, En primer lugar, este nula,

1108
00:56:22,947 --> 00:56:24,030
vamos a deshacerse de él.

1109
00:56:24,030 --> 00:56:26,590
Vamos a tener
los abajo del punto H.

1110
00:56:26,590 --> 00:56:30,600
Si vemos una H, queremos que
ir a otro lugar.

1111
00:56:30,600 --> 00:56:33,910
>> Aquí, podemos entonces marque sí.

1112
00:56:33,910 --> 00:56:38,170
Si llegamos a una H después de la T, oh,
entonces sabemos que se trata de una palabra.

1113
00:56:38,170 --> 00:56:41,110
El booleana va a volver realidad.

1114
00:56:41,110 --> 00:56:42,950
Todo el mundo clara sobre cómo sucedió eso?

1115
00:56:42,950 --> 00:56:45,110
OK.

1116
00:56:45,110 --> 00:56:47,214
>> Así que, esencialmente, todos
estas estructuras de datos

1117
00:56:47,214 --> 00:56:50,130
que hemos repasado la actualidad, tengo
ido por encima de ellos muy, muy rápidamente

1118
00:56:50,130 --> 00:56:52,192
y no en mucho
detalle, y eso está bien.

1119
00:56:52,192 --> 00:56:53,900
Una vez que empiece jugar
con ella, podrás

1120
00:56:53,900 --> 00:56:55,733
no perder de vista donde
todos los punteros son,

1121
00:56:55,733 --> 00:56:58,060
lo que está pasando en su
estructuras de datos, etcétera.

1122
00:56:58,060 --> 00:56:59,810
Van a ser muy útil,
y le toca a usted

1123
00:56:59,810 --> 00:57:03,890
chicos para averiguar totalmente cómo
desea implementar cosas.

1124
00:57:03,890 --> 00:57:07,650
>> Y así pset4, de 5-- oh, eso es incorrecto.

1125
00:57:07,650 --> 00:57:10,140
Pset5 es faltas de ortografía.

1126
00:57:10,140 --> 00:57:13,710
Como he dicho antes, usted va a, una vez
otra vez, descarga el código fuente de nosotros.

1127
00:57:13,710 --> 00:57:16,210
No va a haber tres principales
Cosas que se descargan.

1128
00:57:16,210 --> 00:57:18,470
Vas a descargar los diccionarios,
kers y textos.

1129
00:57:18,470 --> 00:57:21,660
>> Todas esas cosas son son
ya sea diccionarios de palabras

1130
00:57:21,660 --> 00:57:25,190
que queremos que usted compruebe
o la prueba de la información

1131
00:57:25,190 --> 00:57:26,930
que queremos que el corrector ortográfico.

1132
00:57:26,930 --> 00:57:29,670
Y así los diccionarios
damos vas

1133
00:57:29,670 --> 00:57:34,870
para darle palabras reales que queremos
que le permite almacenar de alguna manera en una forma que es

1134
00:57:34,870 --> 00:57:36,530
más eficiente que una matriz.

1135
00:57:36,530 --> 00:57:38,470
Y a continuación, los textos son
va a ser lo que somos

1136
00:57:38,470 --> 00:57:43,900
pidiéndole que corrector ortográfico para asegurarse
todas las palabras son palabras reales allí.

1137
00:57:43,900 --> 00:57:47,970
>> Y así los tres bloques de
programas que le daremos

1138
00:57:47,970 --> 00:57:51,130
se llaman dictionary.c,
dictionary.h, y speller.c.

1139
00:57:51,130 --> 00:57:56,500
Y luego todo se hace dictionary.c
lo que se le pide que implementar.

1140
00:57:56,500 --> 00:57:57,880
Carga palabras.

1141
00:57:57,880 --> 00:58:02,000
Se explican los controles, y se asegura
que todo lo que se ha insertado correctamente.

1142
00:58:02,000 --> 00:58:05,180
>> diction.h es sólo un archivo de biblioteca
que declara todas esas funciones.

1143
00:58:05,180 --> 00:58:07,650
Y speller.c, vamos a darle.

1144
00:58:07,650 --> 00:58:09,290
No es necesario modificar nada de eso.

1145
00:58:09,290 --> 00:58:14,290
Todo speller.c no es tomar que,
lo carga, comprueba la velocidad de la misma,

1146
00:58:14,290 --> 00:58:19,190
pone a prueba el punto de referencia de como la forma
rápidamente que eres capaz de hacer las cosas.

1147
00:58:19,190 --> 00:58:20,410
>> Es un corrector ortográfico.

1148
00:58:20,410 --> 00:58:23,920
Simplemente no te metas con ella, pero que
Asegúrese de entender lo que está haciendo.

1149
00:58:23,920 --> 00:58:28,090
Nosotros usamos una función llamada getrusage que
pone a prueba el rendimiento de su hechizo

1150
00:58:28,090 --> 00:58:28,590
inspector.

1151
00:58:28,590 --> 00:58:32,200
Todo lo que hace es básicamente probar la
tiempo de todo en su diccionario,

1152
00:58:32,200 --> 00:58:33,680
así que asegúrate de que lo entiendes.

1153
00:58:33,680 --> 00:58:36,660
Tenga cuidado de no meterse con ella o
las demás cosas no funcionarán correctamente.

1154
00:58:36,660 --> 00:58:39,740

1155
00:58:39,740 --> 00:58:44,170
>> Y la mayor parte de este desafío es para
chicos Para modificar realmente dictionary.c.

1156
00:58:44,170 --> 00:58:48,526
Vamos a darle
140.000 palabras en un diccionario.

1157
00:58:48,526 --> 00:58:50,900
Vamos a darle un texto
archivo que tiene esas palabras,

1158
00:58:50,900 --> 00:58:54,840
y queremos que usted sea capaz de organizar
en una tabla de hash o un trie

1159
00:58:54,840 --> 00:58:58,140
porque cuando le pedimos que deletrear
check-- imaginar si eres hechizo

1160
00:58:58,140 --> 00:59:00,690
comprobar como la Odisea de Homero.

1161
00:59:00,690 --> 00:59:03,010
Es como este gran, gran prueba,.

1162
00:59:03,010 --> 00:59:05,190
>> Imagínese si todos y cada uno
palabra que había que mirar

1163
00:59:05,190 --> 00:59:08,100
a través de una matriz de 140.000 valores.

1164
00:59:08,100 --> 00:59:10,350
Eso llevaría para siempre
para su máquina para correr.

1165
00:59:10,350 --> 00:59:14,490
Por eso queremos organizar nuestra
datos en estructuras de datos más eficientes

1166
00:59:14,490 --> 00:59:17,270
como una tabla hash o un trie.

1167
00:59:17,270 --> 00:59:20,700
Y entonces ustedes pueden clase
de cuando se busca el acceso

1168
00:59:20,700 --> 00:59:22,570
las cosas más fácilmente y con mayor rapidez.

1169
00:59:22,570 --> 00:59:24,934
>> Y así que ten cuidado para resolver las colisiones.

1170
00:59:24,934 --> 00:59:27,350
Vas a tener un montón
de palabras de ese comienzo con A.

1171
00:59:27,350 --> 00:59:29,957
Vas a conseguir un manojo palabras
que empezar con B. Hasta que

1172
00:59:29,957 --> 00:59:31,290
chicos cómo quieres resolverlo.

1173
00:59:31,290 --> 00:59:34,144
Tal vez hay más
función hash eficiente

1174
00:59:34,144 --> 00:59:36,810
que sólo la primera letra
algo, y por lo que toca a usted

1175
00:59:36,810 --> 00:59:38,190
chicos para hacer la clase de lo que quieras.

1176
00:59:38,190 --> 00:59:40,148
>> Tal vez desee agregar
todas las letras juntas.

1177
00:59:40,148 --> 00:59:43,410
Tal vez usted quiere gustaría hacer cosas extrañas
para tener en cuenta el número de letras,

1178
00:59:43,410 --> 00:59:43,970
lo que sea.

1179
00:59:43,970 --> 00:59:45,386
Hasta que ustedes lo que quieres hacer.

1180
00:59:45,386 --> 00:59:49,262
Si quieres hacer una tabla hash, si usted
Inténtalo de un trie, totalmente de usted.

1181
00:59:49,262 --> 00:59:52,470
Voy a advertirle delante de tiempo que el
trie es típicamente un poco más difícil

1182
00:59:52,470 --> 00:59:54,520
sólo porque hay mucho
más punteros a no perder de vista.

1183
00:59:54,520 --> 00:59:55,645
Pero totalmente de ustedes.

1184
00:59:55,645 --> 00:59:58,742
Es mucho más eficiente
en la mayoria de los casos.

1185
00:59:58,742 --> 01:00:01,450
¿Quieres ser realmente capaz de mantener
un registro de todos sus punteros.

1186
01:00:01,450 --> 01:00:03,850
Como hacer la misma cosa
que estaba haciendo aquí.

1187
01:00:03,850 --> 01:00:06,871
Cuando usted está tratando de insertar
valores en una tabla hash o eliminar,

1188
01:00:06,871 --> 01:00:08,620
asegúrese de que usted es
realmente hacer el seguimiento

1189
01:00:08,620 --> 01:00:11,860
de donde todo es debido
es muy fácil porque si yo soy

1190
01:00:11,860 --> 01:00:14,727
intentar insertar como la palabra, andy.

1191
01:00:14,727 --> 01:00:16,810
Digamos que es una
palabra real, la palabra, andy,

1192
01:00:16,810 --> 01:00:19,640
en una lista gigante de una palabras.

1193
01:00:19,640 --> 01:00:22,450
>> Si lo que pasa es reasignar
un mal indicador, oops,

1194
01:00:22,450 --> 01:00:24,940
ahí va la totalidad de
el resto de mi lista enlazada.

1195
01:00:24,940 --> 01:00:26,897
Ahora, la única palabra que
tener es andy, y ahora

1196
01:00:26,897 --> 01:00:29,230
todas las otras palabras
diccionario se han perdido.

1197
01:00:29,230 --> 01:00:31,370
Y por lo que desea asegurarse de que
llevar un registro de todos sus punteros

1198
01:00:31,370 --> 01:00:33,661
o de lo contrario va a conseguir
enormes problemas en su código.

1199
01:00:33,661 --> 01:00:35,840
Dibuja las cosas con cuidado, paso a paso.

1200
01:00:35,840 --> 01:00:37,870
Esto hace que sea mucho más fácil de imaginar.

1201
01:00:37,870 --> 01:00:40,910
>> Y, por último, que desea ser capaz de
probar el rendimiento de su programa

1202
01:00:40,910 --> 01:00:41,618
en el gran tablero.

1203
01:00:41,618 --> 01:00:43,710
Si ustedes toman un
mira CS50 en este momento,

1204
01:00:43,710 --> 01:00:45,210
tenemos lo que se llama el gran tablero.

1205
01:00:45,210 --> 01:00:50,200
Es la hoja de puntuación de los más rápidos
deletrear tiempos de cheques a través de todas CS50

1206
01:00:50,200 --> 01:00:55,720
en este momento, creo que la parte superior como 10
veces pienso que ocho de ellos son personal.

1207
01:00:55,720 --> 01:00:57,960
Realmente queremos que ustedes nos ganaron.

1208
01:00:57,960 --> 01:01:00,870
>> Todos nosotros estábamos tratando de poner en práctica
el código rápido como sea posible.

1209
01:01:00,870 --> 01:01:04,880
Queremos que ustedes tratan de desafiar
nos e implementar más rápido que todos nosotros

1210
01:01:04,880 --> 01:01:05,550
poder.

1211
01:01:05,550 --> 01:01:07,970
Y por lo que este es realmente
la primera vez que estamos

1212
01:01:07,970 --> 01:01:12,680
pidiendo a ustedes para hacer un conjunto de procesadores que
usted puede hacer realidad en cualquier método

1213
01:01:12,680 --> 01:01:13,760
quieres.

1214
01:01:13,760 --> 01:01:17,730
>> Yo siempre digo, esto es más afín
a una solución de la vida real, ¿verdad?

1215
01:01:17,730 --> 01:01:19,550
Yo digo, hey, necesito que hagas esto.

1216
01:01:19,550 --> 01:01:21,380
Construir un programa que hace esto por mí.

1217
01:01:21,380 --> 01:01:22,630
Hazlo como quieras.

1218
01:01:22,630 --> 01:01:24,271
Sólo sé que quiero ayunar.

1219
01:01:24,271 --> 01:01:25,770
Ese es su reto para esta semana.

1220
01:01:25,770 --> 01:01:27,531
Ustedes, que va
para darle una tarea.

1221
01:01:27,531 --> 01:01:29,030
Vamos a darle un desafío.

1222
01:01:29,030 --> 01:01:31,559
Y luego le toca a ustedes
completamente solo averiguar

1223
01:01:31,559 --> 01:01:34,100
¿cuál es la más rápida y más
forma eficiente para implementar esto.

1224
01:01:34,100 --> 01:01:34,600
¿Sí?

1225
01:01:34,600 --> 01:01:37,476
>> AUDIENCIA: ¿Estamos autorizados a si
Queríamos investigar maneras más rápidas

1226
01:01:37,476 --> 01:01:40,821
hacer tablas hash en línea, podemos hacer
eso y citar el código de otra persona?

1227
01:01:40,821 --> 01:01:42,070
ANDI Peng: Sí, totalmente bien.

1228
01:01:42,070 --> 01:01:44,320
Así que si ustedes leen el
especificaciones, hay una línea

1229
01:01:44,320 --> 01:01:48,310
en la especificación que dice que ustedes
son totalmente libres a la investigación de hash

1230
01:01:48,310 --> 01:01:51,070
funciones en lo que son algunos
de las funciones de hash más rápidos

1231
01:01:51,070 --> 01:01:54,720
para ejecutar las cosas como
siempre y cuando se cite ese código.

1232
01:01:54,720 --> 01:01:57,220
Así que algunas personas ya tienen
descubierto maneras rápidas

1233
01:01:57,220 --> 01:02:00,250
de hacer los correctores ortográficos, de rápido
formas de almacenar información.

1234
01:02:00,250 --> 01:02:02,750
Totalmente de ustedes si
quiere tomar sólo eso, ¿verdad?

1235
01:02:02,750 --> 01:02:04,045
Asegúrese de que está citando.

1236
01:02:04,045 --> 01:02:06,170
El reto aquí realmente
que estamos tratando de probar

1237
01:02:06,170 --> 01:02:09,750
es asegurarse de que usted sabe
su manera alrededor de punteros.

1238
01:02:09,750 --> 01:02:12,700
Por lo que usted implementación
la función hash real

1239
01:02:12,700 --> 01:02:15,070
y dar con igual
las matemáticas para hacer eso,

1240
01:02:15,070 --> 01:02:17,570
ustedes pueden investigar lo que sea
métodos en línea que ustedes quieren.

1241
01:02:17,570 --> 01:02:17,996
¿Sí?

1242
01:02:17,996 --> 01:02:19,700
>> AUDIENCIA: ¿Podemos citar sólo
mediante el uso de la [inaudible]?

1243
01:02:19,700 --> 01:02:20,120
>> ANDI Peng: Sí.

1244
01:02:20,120 --> 01:02:22,328
Usted puede simplemente, en su comentario,
se puede citar como, oh,

1245
01:02:22,328 --> 01:02:26,127
tomado de bla, bla,
yada, función hash.

1246
01:02:26,127 --> 01:02:27,210
¿Alguien tiene alguna pregunta?

1247
01:02:27,210 --> 01:02:29,694
En realidad breezed
en la sección de hoy.

1248
01:02:29,694 --> 01:02:31,610
Voy a estar aquí para
responder a las preguntas también.

1249
01:02:31,610 --> 01:02:36,570
>> Además, como ya he dicho, la oficina
horas de esta noche y mañana.

1250
01:02:36,570 --> 01:02:40,307
La especificación de esta semana es en realidad
super fácil y super corto de leer.

1251
01:02:40,307 --> 01:02:43,140
Yo sugeriría tomar una mirada, justo
leer a través de la totalidad de la misma.

1252
01:02:43,140 --> 01:02:45,730
>> Y Zamyla realidad que camina
a través de cada una de las funciones

1253
01:02:45,730 --> 01:02:49,796
que necesita para implementar, y por lo que es
muy, muy claro cómo hacer todo.

1254
01:02:49,796 --> 01:02:51,920
Sólo para asegurarse de que está
hacer el seguimiento de los punteros.

1255
01:02:51,920 --> 01:02:53,650
Se trata de un conjunto de procesadores muy difícil.

1256
01:02:53,650 --> 01:02:56,744
>> No es un reto porque al igual que,
oh, los conceptos son mucho más

1257
01:02:56,744 --> 01:02:59,160
difícil, o usted tiene que aprender
tanto nueva sintaxis de la manera

1258
01:02:59,160 --> 01:03:00,650
que usted hizo por última pset.

1259
01:03:00,650 --> 01:03:03,320
Este conjunto de procesadores es difícil porque
hay tantos punteros,

1260
01:03:03,320 --> 01:03:06,980
y entonces es muy, muy fácil de una vez
usted tiene un error en su código que no pueda

1261
01:03:06,980 --> 01:03:08,315
encontrar donde ese error es.

1262
01:03:08,315 --> 01:03:13,200
>> Y tan completa y absoluta fe en ti
chicos sean capaces de superar nuestra [inaudible]

1263
01:03:13,200 --> 01:03:13,700
ortografía.

1264
01:03:13,700 --> 01:03:16,640
En realidad no tengo ninguna mina escrita
todavía, pero estoy a punto de escribir la mía.

1265
01:03:16,640 --> 01:03:19,070
Así, mientras que usted está escribiendo
el suyo, voy a estar escribiendo la mía.

1266
01:03:19,070 --> 01:03:21,070
Voy a tratar de hacer
mina más rápido que el suyo.

1267
01:03:21,070 --> 01:03:23,940
Vamos a ver quién tiene el más rápido.

1268
01:03:23,940 --> 01:03:27,340
>> Y sí, voy a ver todos
ustedes aquí el martes.

1269
01:03:27,340 --> 01:03:29,510
Voy a correr una especie como un taller conjunto de procesadores.

1270
01:03:29,510 --> 01:03:32,640
Todas las secciones este
semana son talleres PSet,

1271
01:03:32,640 --> 01:03:36,690
por lo que ustedes tienen muchas oportunidades
en busca de ayuda, las horas de oficina como siempre,

1272
01:03:36,690 --> 01:03:41,330
y realmente espero con interés
leer todo el código a sus chicos.

1273
01:03:41,330 --> 01:03:44,160
Tengo pruebas aquí si
chicos quieren venir conseguirlos.

1274
01:03:44,160 --> 01:03:45,880
Eso es todo.

1275
01:03:45,880 --> 01:03:48,180