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

2
00:00:11,860 --> 00:00:13,120
>> ALTAVOZ 1: Muy bien, así que estamos de vuelta.

3
00:00:13,120 --> 00:00:14,480
Bienvenido a CS50.

4
00:00:14,480 --> 00:00:16,510
Este es el final de la séptima semana.

5
00:00:16,510 --> 00:00:20,200
Así que recordar que la última vez, empezamos
mirando ligeramente más sofisticado

6
00:00:20,200 --> 00:00:21,100
estructuras de datos.

7
00:00:21,100 --> 00:00:25,110
Dado que hasta ahora, todo lo que teníamos realmente
a nuestra disposición era esto, una matriz.

8
00:00:25,110 --> 00:00:29,340
>> Pero antes de descartar la matriz como no
todo lo que interesante, que de hecho se

9
00:00:29,340 --> 00:00:33,570
realmente es, ¿cuáles son algunas de las
ventajas de estos datos sencilla

10
00:00:33,570 --> 00:00:34,560
estructurar hasta el momento?

11
00:00:34,560 --> 00:00:36,110
¿Qué es lo bueno?

12
00:00:36,110 --> 00:00:39,450
Por lo que hemos visto?

13
00:00:39,450 --> 00:00:42,540
¿Qué tienes?

14
00:00:42,540 --> 00:00:44,028
Nada.

15
00:00:44,028 --> 00:00:45,020
>> ESTUDIANTE: [inaudible].

16
00:00:45,020 --> 00:00:45,395
>> ALTAVOZ 1: ¿Qué es eso?

17
00:00:45,395 --> 00:00:46,410
>> ESTUDIANTE: [inaudible].

18
00:00:46,410 --> 00:00:47,000
>> ALTAVOZ 1: Tamaño fijo.

19
00:00:47,000 --> 00:00:51,260
OK, así que ¿por qué es bueno, aunque de tamaño fijo?

20
00:00:51,260 --> 00:00:53,180
>> ESTUDIANTE: [inaudible].

21
00:00:53,180 --> 00:00:56,240
>> ALTAVOZ 1: OK, así que es eficiente en la
el sentido de que se puede asignar una

22
00:00:56,240 --> 00:01:00,070
cantidad fija de espacio, lo cual es de esperar
es precisamente tanto

23
00:01:00,070 --> 00:01:01,180
espacio que quieras.

24
00:01:01,180 --> 00:01:02,720
Así que podría ser absolutamente una ventaja.

25
00:01:02,720 --> 00:01:06,530
>> ¿Cuál es la otra cara de una matriz?

26
00:01:06,530 --> 00:01:07,610
¿Sí?

27
00:01:07,610 --> 00:01:08,750
>> ESTUDIANTE: [inaudible].

28
00:01:08,750 --> 00:01:09,550
>> ALTAVOZ 1: Todo el - lo siento?

29
00:01:09,550 --> 00:01:11,270
>> ESTUDIANTE: [inaudible].

30
00:01:11,270 --> 00:01:13,620
>> ALTAVOZ 1: Todos los cuadros en la memoria
o uno junto al otro.

31
00:01:13,620 --> 00:01:15,220
Y eso es útil - por qué?

32
00:01:15,220 --> 00:01:15,970
Eso es muy cierto.

33
00:01:15,970 --> 00:01:18,611
Pero ¿cómo podemos aprovechar esa verdad?

34
00:01:18,611 --> 00:01:21,500
>> ESTUDIANTE: [inaudible].

35
00:01:21,500 --> 00:01:24,490
>> ALTAVOZ 1: Exactamente, podemos mantener un registro de
donde todo es sólo saber

36
00:01:24,490 --> 00:01:28,560
una dirección, a saber, la dirección de la
primer byte de ese trozo de memoria.

37
00:01:28,560 --> 00:01:30,420
O en el caso de la cadena,
la dirección de la primera

38
00:01:30,420 --> 00:01:31,460
charla en esa cadena.

39
00:01:31,460 --> 00:01:33,330
Y a partir de ahí, podemos encontrar
el final de la cadena.

40
00:01:33,330 --> 00:01:35,710
Podemos encontrar el segundo elemento, el
tercer elemento, y así sucesivamente.

41
00:01:35,710 --> 00:01:38,740
>> Y así, la manera elegante de describir que
característica es que las matrices nos dan

42
00:01:38,740 --> 00:01:40,020
de acceso aleatorio.

43
00:01:40,020 --> 00:01:44,330
Sólo mediante el uso del corchete
notación y un número, puede saltar a

44
00:01:44,330 --> 00:01:48,070
un elemento específico de la matriz
en tiempo constante, gran O

45
00:01:48,070 --> 00:01:49,810
de uno, por así decirlo.

46
00:01:49,810 --> 00:01:51,080
>> Pero ha habido algunos inconvenientes.

47
00:01:51,080 --> 00:01:53,110
Lo que un conjunto no lo hacen con mucha facilidad?

48
00:01:53,110 --> 00:01:55,810

49
00:01:55,810 --> 00:01:57,170
¿Qué no hacer bien?

50
00:01:57,170 --> 00:01:58,810
>> ESTUDIANTE: [inaudible].

51
00:01:58,810 --> 00:01:59,860
>> ALTAVOZ 1: ¿Qué es eso?

52
00:01:59,860 --> 00:02:00,530
>> ESTUDIANTE: [inaudible].

53
00:02:00,530 --> 00:02:01,460
>> ALTAVOZ 1: Ampliación de tamaño.

54
00:02:01,460 --> 00:02:04,800
Así que los aspectos negativos de la matriz son
precisamente lo contrario de lo que el

55
00:02:04,800 --> 00:02:05,540
Upsides son.

56
00:02:05,540 --> 00:02:07,610
Así que una de las desventajas es
que es un tamaño fijo.

57
00:02:07,610 --> 00:02:09,400
Así que realmente no se puede crecer.

58
00:02:09,400 --> 00:02:13,510
Puede reasignar un pedazo más grande de
la memoria y, a continuación, mover los elementos antiguos

59
00:02:13,510 --> 00:02:14,460
en la nueva matriz.

60
00:02:14,460 --> 00:02:18,060
Y luego liberar la matriz de edad, para los
ejemplo, mediante el uso de malloc o similar

61
00:02:18,060 --> 00:02:21,180
función llamada realloc, que
reasigna memoria.

62
00:02:21,180 --> 00:02:25,490
>> Realloc, como un aparte, intenta darle
memoria que está al lado de la matriz

63
00:02:25,490 --> 00:02:26,610
que ya tiene.

64
00:02:26,610 --> 00:02:28,740
Pero podría mover cosas
alrededor del todo.

65
00:02:28,740 --> 00:02:30,710
Pero en fin, eso es caro, ¿no?

66
00:02:30,710 --> 00:02:33,440
Porque si tienes un trozo de memoria de
este tamaño, pero realmente quieres uno

67
00:02:33,440 --> 00:02:36,710
de este tamaño, y desea conservar
los elementos originales, que tienen

68
00:02:36,710 --> 00:02:40,510
más o menos un proceso de copia de tiempo lineal
eso tiene que suceder de

69
00:02:40,510 --> 00:02:41,900
antigua matriz a la nueva.

70
00:02:41,900 --> 00:02:44,630
Y la realidad está pidiendo a la operación
sistema una y otra vez y

71
00:02:44,630 --> 00:02:48,340
de nuevo por grandes trozos de la memoria puede comenzar
que le costará algo de tiempo también.

72
00:02:48,340 --> 00:02:52,250
Así que es tanto una bendición como una maldición en
disfrazar, el hecho de que estas matrices

73
00:02:52,250 --> 00:02:53,860
son de tamaño fijo.

74
00:02:53,860 --> 00:02:56,790
Pero si introducimos en cambio algo
como éste, que hemos denominado una ligado

75
00:02:56,790 --> 00:03:00,580
lista, tenemos unas cuantas ventajas y
algunas desventajas también aquí.

76
00:03:00,580 --> 00:03:05,780
>> Así que una lista enlazada es simplemente un dato
estructura compuesta de C estructuras en esta

77
00:03:05,780 --> 00:03:09,850
caso, en que una estructura, el recuerdo, es sólo
un contenedor para una o más específica

78
00:03:09,850 --> 00:03:11,100
tipos de variables.

79
00:03:11,100 --> 00:03:16,110
En este caso, lo que hacen los tipos de datos
parecen estar dentro de la estructura que

80
00:03:16,110 --> 00:03:17,600
última vez que se llama un nodo?

81
00:03:17,600 --> 00:03:19,380
Cada uno de estos rectángulos es un nodo.

82
00:03:19,380 --> 00:03:22,660
Y cada uno de los rectángulos más pequeños
dentro de ella es un tipo de datos.

83
00:03:22,660 --> 00:03:25,300
¿Qué tipos dijimos
estaban el lunes?

84
00:03:25,300 --> 00:03:26,478
¿Sí?

85
00:03:26,478 --> 00:03:27,870
>> ESTUDIANTE: [inaudible].

86
00:03:27,870 --> 00:03:30,721
>> ALTAVOZ 1: Una variable y un puntero, o
más específicamente, un int, para n,

87
00:03:30,721 --> 00:03:32,180
y un puntero en la parte inferior.

88
00:03:32,180 --> 00:03:35,360
Tanto de los que pasan a ser de 32 bits, por lo
menos en un equipo como éste CS50

89
00:03:35,360 --> 00:03:37,980
Appliance y por lo que son
dibujado por igual en tamaño.

90
00:03:37,980 --> 00:03:42,260
>> Entonces, ¿qué está utilizando el puntero
aunque para parecer?

91
00:03:42,260 --> 00:03:47,690
¿Por qué añadir esta flecha ahora, cuando las matrices fueron
tan agradable y limpio y simple?

92
00:03:47,690 --> 00:03:50,460
¿Cuál es el puntero haciendo por
nosotros en cada uno de estos nodos?

93
00:03:50,460 --> 00:03:52,160
>> ESTUDIANTE: [inaudible].

94
00:03:52,160 --> 00:03:52,465
>> ALTAVOZ 1: Exactamente.

95
00:03:52,465 --> 00:03:54,120
Le está diciendo a donde
el siguiente es.

96
00:03:54,120 --> 00:03:57,350
Así que en cierto modo me utilizo la analogía de
utilizando un hilo a una especie de

97
00:03:57,350 --> 00:03:59,180
enhebrar estos nodos juntos.

98
00:03:59,180 --> 00:04:01,760
Y eso es exactamente lo que estamos haciendo con
punteros porque cada uno de estos

99
00:04:01,760 --> 00:04:06,360
trozos de memoria pueden o no pueden ser
contigua, espalda con espalda hacia atrás

100
00:04:06,360 --> 00:04:09,500
dentro de la memoria RAM, ya que cada vez que
llamada diciendo malloc, dame suficiente

101
00:04:09,500 --> 00:04:12,510
bytes para un nuevo nodo, podría
estar aquí o podría estar aquí.

102
00:04:12,510 --> 00:04:13,120
Podría estar aquí.

103
00:04:13,120 --> 00:04:13,730
Podría estar aquí.

104
00:04:13,730 --> 00:04:14,640
Usted simplemente no sabe.

105
00:04:14,640 --> 00:04:17,880
>> Pero el uso de punteros en las direcciones de
esos nodos, puede coserlos

106
00:04:17,880 --> 00:04:22,370
juntos en una manera que parece visualmente
como una lista, incluso si estas cosas son

107
00:04:22,370 --> 00:04:26,770
todo extendido en todo su ser o
su dos o tus cuatro gigabytes de RAM

108
00:04:26,770 --> 00:04:28,760
dentro de su propio equipo.

109
00:04:28,760 --> 00:04:33,230
>> De modo que el lado negativo, pues, de
una lista enlazada es lo que?

110
00:04:33,230 --> 00:04:34,670
¿Qué es un precio que estamos
al parecer, el pago?

111
00:04:34,670 --> 00:04:36,010
>> ESTUDIANTE: [inaudible].

112
00:04:36,010 --> 00:04:36,920
>> ALTAVOZ 1: Más espacio, ¿no?

113
00:04:36,920 --> 00:04:39,340
Hemos, en este caso, duplicamos la cantidad
de espacio, porque hemos ido

114
00:04:39,340 --> 00:04:43,500
de 32 bits para cada nodo, para cada uno
int, por lo que ahora de 64 bits, ya que tiene que

115
00:04:43,500 --> 00:04:45,050
mantener en torno a un puntero también.

116
00:04:45,050 --> 00:04:48,860
Usted obtiene más eficiencia si su estructura
es más grande que esta cosa simple.

117
00:04:48,860 --> 00:04:52,020
Si usted realmente tiene un estudiante en el interior
de que es un par de cadenas de

118
00:04:52,020 --> 00:04:55,430
nombre y la casa, tal vez un número de identificación,
tal vez algunos otros campos en total.

119
00:04:55,430 --> 00:04:59,000
>> Así que si usted tiene un gran suficiente estructura,
entonces tal vez el costo del puntero es

120
00:04:59,000 --> 00:05:00,010
no es una cosa muy importante.

121
00:05:00,010 --> 00:05:03,570
Esto es un poco de un caso límite en que
estamos almacenando una sencilla primitiva, tales

122
00:05:03,570 --> 00:05:04,760
dentro de la lista enlazada.

123
00:05:04,760 --> 00:05:05,790
Pero el punto es el mismo.

124
00:05:05,790 --> 00:05:08,230
Definitivamente estás gastando más
memoria, pero que está recibiendo

125
00:05:08,230 --> 00:05:08,990
flexibilidad.

126
00:05:08,990 --> 00:05:12,280
Porque ahora si quiero agregar un elemento
al principio de esta lista,

127
00:05:12,280 --> 00:05:14,340
Tengo que asignar un nuevo nodo.

128
00:05:14,340 --> 00:05:17,180
Y tengo que acaba de actualizar los
flechas de alguna manera, con sólo mover

129
00:05:17,180 --> 00:05:17,980
algunos indicadores alrededor.

130
00:05:17,980 --> 00:05:20,580
>> Si quiero insertar algo en el
mitad de la lista, no tiene por qué

131
00:05:20,580 --> 00:05:24,410
empujar a todos a un lado como lo hicimos en
pasado semanas con nuestros voluntarios que

132
00:05:24,410 --> 00:05:25,700
representado una matriz.

133
00:05:25,700 --> 00:05:29,470
Yo sólo puedo asignar un nuevo nodo y
a continuación, sólo apuntar las flechas en

134
00:05:29,470 --> 00:05:32,290
diferentes direcciones, ya que no hace
que permanecer en real

135
00:05:32,290 --> 00:05:35,670
memoria una verdadera línea como he dibujado
aquí en la pantalla.

136
00:05:35,670 --> 00:05:38,400
>> Y luego, por último, si desea insertar
algo al final de la lista, es

137
00:05:38,400 --> 00:05:39,210
aún más fácil.

138
00:05:39,210 --> 00:05:43,320
Esta es una especie de notación arbitraria,
pero un triple de 34, tomar una conjetura.

139
00:05:43,320 --> 00:05:46,710
¿Cuál es el valor de su indicador más
probablemente dibujado algo así como un viejo

140
00:05:46,710 --> 00:05:47,700
antena de escuela allí?

141
00:05:47,700 --> 00:05:48,920
>> ESTUDIANTE: [inaudible].

142
00:05:48,920 --> 00:05:49,900
>> ALTAVOZ 1: Probablemente es nulo.

143
00:05:49,900 --> 00:05:52,710
Y de hecho es uno de los autores de
representación de nulo.

144
00:05:52,710 --> 00:05:56,310
Y es nula, porque a pesar de todo
necesita saber dónde está el final de un vinculado

145
00:05:56,310 --> 00:06:00,050
lista es, para que no se mantiene después y
siguiendo y siguiendo estas flechas

146
00:06:00,050 --> 00:06:01,170
a algún valor de basura.

147
00:06:01,170 --> 00:06:06,230
Así nula significará que no es
más nodos a la derecha del número 34,

148
00:06:06,230 --> 00:06:07,200
en este caso.

149
00:06:07,200 --> 00:06:10,270
>> Así que proponemos que podemos poner en práctica
este nodo en el código.

150
00:06:10,270 --> 00:06:12,130
Y hemos visto este tipo
de sintaxis antes.

151
00:06:12,130 --> 00:06:15,090
Typedef simplemente define un nuevo tipo de
nosotros, nos da un sinónimo como

152
00:06:15,090 --> 00:06:17,100
cadena era para char *.

153
00:06:17,100 --> 00:06:21,030
En este caso, se nos va a dar
notación abreviada de manera que el nodo struct

154
00:06:21,030 --> 00:06:24,010
puede en su lugar sólo puede escribir como
nodo, que es mucho más limpio.

155
00:06:24,010 --> 00:06:25,360
Es mucho menos detallado.

156
00:06:25,360 --> 00:06:30,080
>> Dentro de un nodo es aparentemente un int
llamada n, y luego un nodo de estructura *

157
00:06:30,080 --> 00:06:34,670
lo que significa exactamente lo que queríamos la
flechas para significar, un puntero a otra

158
00:06:34,670 --> 00:06:36,940
nodo del mismo tipo de datos exacta.

159
00:06:36,940 --> 00:06:40,300
Y propongo que podríamos poner en práctica un
función de búsqueda de este tipo, que en

160
00:06:40,300 --> 00:06:41,890
primera vista podría parecer
un poco compleja.

161
00:06:41,890 --> 00:06:43,330
Pero vamos a verlo en su contexto.

162
00:06:43,330 --> 00:06:45,480
>> Quiero pasar al aparato aquí.

163
00:06:45,480 --> 00:06:48,460
Permítanme abrir un archivo llamado
listar cero punto h.

164
00:06:48,460 --> 00:06:53,950
Y que sólo contiene la definición que
acabo de ver hace un momento para estos datos

165
00:06:53,950 --> 00:06:55,390
tipo llamado un nodo.

166
00:06:55,390 --> 00:06:57,350
Así que hemos puesto que en un archivo de puntos h.

167
00:06:57,350 --> 00:07:01,430
>> Y en un aparte, a pesar de que esta
programa que usted está a punto de ver es

168
00:07:01,430 --> 00:07:05,410
no todo lo que complejo, es de hecho
convenciones al escribir un programa para

169
00:07:05,410 --> 00:07:10,270
poner las cosas como los tipos de datos, para sacar
constantes a veces, dentro de su

170
00:07:10,270 --> 00:07:13,210
archivo de cabecera y no necesariamente en
el archivo de C, sobre todo cuando su

171
00:07:13,210 --> 00:07:17,370
programas se hacen más grandes y más grandes, de modo que
usted sabe dónde buscar, tanto para

172
00:07:17,370 --> 00:07:20,840
documentación en algunos casos, o
para lo básico como este, el

173
00:07:20,840 --> 00:07:22,360
definición de algún tipo.

174
00:07:22,360 --> 00:07:25,680
>> Si ahora abro la lista de puntos cero
c, notar un par de cosas.

175
00:07:25,680 --> 00:07:29,090
Incluye unos archivos de cabecera, la mayoría
de los cuales hemos visto antes.

176
00:07:29,090 --> 00:07:31,980
Incluye su propio archivo de cabecera.

177
00:07:31,980 --> 00:07:35,200
>> Y en un aparte, ¿por qué eso es doble
cita aquí, en comparación con el ángulo

178
00:07:35,200 --> 00:07:38,340
soportes en la línea que
He destacado allí?

179
00:07:38,340 --> 00:07:39,180
>> ESTUDIANTE: [inaudible].

180
00:07:39,180 --> 00:07:40,460
>> ALTAVOZ 1: Sí, así que es un archivo local.

181
00:07:40,460 --> 00:07:44,300
Así que si es un archivo local de su propia aquí
en la línea 15, por ejemplo, se utiliza

182
00:07:44,300 --> 00:07:46,570
las comillas dobles en vez
de los paréntesis angulares.

183
00:07:46,570 --> 00:07:48,270
>> Ahora bien, esto es algo interesante.

184
00:07:48,270 --> 00:07:51,830
Nótese que he declarado un mundial
variable en este programa en la línea 18

185
00:07:51,830 --> 00:07:55,910
llamó en primer lugar, la idea de esto es
va a ser un puntero a la primera

186
00:07:55,910 --> 00:07:59,190
nodo en mi lista enlazada, y he
inicializa a null, porque he

187
00:07:59,190 --> 00:08:02,310
no asignado ningún real
nodos por el momento.

188
00:08:02,310 --> 00:08:07,570
>> Así que esto representa, gráficamente, lo que
vi hace un momento en la imagen como

189
00:08:07,570 --> 00:08:10,090
ese puntero en el extremo
a mano izquierda.

190
00:08:10,090 --> 00:08:12,260
Así que ahora mismo, ese puntero
no tiene una flecha.

191
00:08:12,260 --> 00:08:14,590
En su lugar, es nulo.

192
00:08:14,590 --> 00:08:17,880
Pero representa lo que será el
dirección del primer real

193
00:08:17,880 --> 00:08:19,480
nodo en esta lista.

194
00:08:19,480 --> 00:08:22,120
Así que he implementado es un mundial
porque, como se verá, todo esto

195
00:08:22,120 --> 00:08:25,310
programa hace en la vida se implemento
una lista enlazada para mí.

196
00:08:25,310 --> 00:08:27,050
>> Ahora tengo un par de prototipos aquí.

197
00:08:27,050 --> 00:08:31,190
Decidí implementar características como
deleción, inserción, búsqueda y

198
00:08:31,190 --> 00:08:31,740
de recorrido -

199
00:08:31,740 --> 00:08:35,210
el último sólo estar a pie a través de la
lista, la impresión de sus elementos.

200
00:08:35,210 --> 00:08:36,750
Y ahora aquí está mi rutina principal.

201
00:08:36,750 --> 00:08:39,890
Y no vamos a pasar mucho tiempo en
éstas ya que esta es una especie de, ojalá

202
00:08:39,890 --> 00:08:41,780
viejo sombrero por ahora.

203
00:08:41,780 --> 00:08:45,370
>> Voy a hacer lo siguiente,
mientras el usuario coopera.

204
00:08:45,370 --> 00:08:47,300
Así que uno, voy a imprimir
salir de este menú.

205
00:08:47,300 --> 00:08:49,420
Y he formateado como
limpiamente como pude.

206
00:08:49,420 --> 00:08:52,240
Si el usuario escribe en uno, para que los medios
quieren borrar algo.

207
00:08:52,240 --> 00:08:54,560
Si el usuario escribe en dos, que los medios
quieren insertar algo.

208
00:08:54,560 --> 00:08:55,930
Y así sucesivamente.

209
00:08:55,930 --> 00:08:58,270
Voy a continuación, pedirá
a continuación, para un comando.

210
00:08:58,270 --> 00:08:59,300
Y entonces voy a utilizar GetInt.

211
00:08:59,300 --> 00:09:02,790
>> Así que este es un muy simple de menús
interfaz en la que sólo tiene que escribir

212
00:09:02,790 --> 00:09:05,270
una asignación de número a uno
de esos comandos.

213
00:09:05,270 --> 00:09:08,730
Y ahora tengo un interruptor limpio agradable
declaración que va a cambiar el

214
00:09:08,730 --> 00:09:10,090
cualquiera que sea el usuario escribió pulg

215
00:09:10,090 --> 00:09:12,180
Y si ellos escriben uno, voy a
llamar a delete y se rompa.

216
00:09:12,180 --> 00:09:14,380
Si se escriben dos, voy a
llamar inserción y descanso.

217
00:09:14,380 --> 00:09:16,490
>> Y ahora noto que he puesto cada
de estos en la misma línea.

218
00:09:16,490 --> 00:09:18,360
Esto es sólo una decisión estilística.

219
00:09:18,360 --> 00:09:20,210
Normalmente hemos visto algo
como este.

220
00:09:20,210 --> 00:09:23,260
Pero decidí, francamente, mi programa
parecía más fácil de leer porque

221
00:09:23,260 --> 00:09:25,980
era sólo cuatro casos a
sólo lista así.

222
00:09:25,980 --> 00:09:28,360
Totalmente uso legítimo de estilo.

223
00:09:28,360 --> 00:09:31,480
Y yo voy a hacer esto siempre y cuando el
El usuario no ha escrito cero, lo que me

224
00:09:31,480 --> 00:09:33,910
decidido significará que quieren dejar de fumar.

225
00:09:33,910 --> 00:09:36,630
>> Así que ahora doy cuenta de lo que soy
vamos a hacer aquí.

226
00:09:36,630 --> 00:09:38,650
Voy a liberar a la lista aparentemente.

227
00:09:38,650 --> 00:09:40,230
Pero más sobre esto en un momento.

228
00:09:40,230 --> 00:09:41,640
Primero vamos a ejecutar este programa.

229
00:09:41,640 --> 00:09:45,250
Así que permítanme hacer una terminal más grande
ventana, lista slash dot 0.

230
00:09:45,250 --> 00:09:49,510
Voy a seguir adelante e inserte por
escribir dos, un número como 50, y ahora

231
00:09:49,510 --> 00:09:51,590
verás la lista es ahora 50.

232
00:09:51,590 --> 00:09:53,380
Y mi texto sólo desplaza un poco.

233
00:09:53,380 --> 00:09:55,940
Así que ahora cuenta la lista contiene
el número 50.

234
00:09:55,940 --> 00:09:58,220
>> Vamos a hacer otro inserto tomando dos.

235
00:09:58,220 --> 00:10:01,630
Vamos a escribir el número como tal.

236
00:10:01,630 --> 00:10:03,940
Lista es ahora uno, seguido por 50.

237
00:10:03,940 --> 00:10:06,020
Así que esto es sólo una representación textual
de la lista.

238
00:10:06,020 --> 00:10:10,550
Y vamos a insertar un número más como
el número 42, que es de esperar

239
00:10:10,550 --> 00:10:14,620
va a terminar en el medio, porque
este programa de clases particulares que

240
00:10:14,620 --> 00:10:16,320
elementos, ya que los inserta.

241
00:10:16,320 --> 00:10:17,220
Así que ahí lo tenemos.

242
00:10:17,220 --> 00:10:20,730
Programa Súper simple que podría
absolutamente he utilizado una matriz, pero

243
00:10:20,730 --> 00:10:23,280
pasaría a estar usando una lista enlazada
Sólo para que pueda dinámicamente

244
00:10:23,280 --> 00:10:24,610
crecer y reducir su tamaño.

245
00:10:24,610 --> 00:10:28,470
>> Así que echemos un vistazo a la búsqueda, si
comando de tres carreras, quiero buscar

246
00:10:28,470 --> 00:10:31,040
para, por ejemplo, el número 43.

247
00:10:31,040 --> 00:10:34,190
Y nada se encontró al parecer,
porque volví ninguna respuesta.

248
00:10:34,190 --> 00:10:35,010
Así que vamos a hacer esto de nuevo.

249
00:10:35,010 --> 00:10:35,690
Búsqueda.

250
00:10:35,690 --> 00:10:39,520
Vamos a buscar el 50, o más bien buscar
el 42, que tiene una bonita

251
00:10:39,520 --> 00:10:40,850
poco significado sutil.

252
00:10:40,850 --> 00:10:42,610
Y he encontrado el sentido de la vida allí.

253
00:10:42,610 --> 00:10:44,990
Número 42, si usted no sabe
la referencia, Google él.

254
00:10:44,990 --> 00:10:45,350
Está bien.

255
00:10:45,350 --> 00:10:47,130
Entonces, ¿qué ha hecho este programa para mí?

256
00:10:47,130 --> 00:10:50,660
Simplemente me ha permitido insertar este modo
a lo largo y búsqueda de elementos.

257
00:10:50,660 --> 00:10:53,650
>> Vamos a avanzar rápidamente, entonces,
esa función nos miró a

258
00:10:53,650 --> 00:10:55,360
el lunes como un reclamo.

259
00:10:55,360 --> 00:10:59,620
Así que esta función, reclamo, busca
un elemento en la lista por primera

260
00:10:59,620 --> 00:11:03,830
uno, preguntar al usuario y luego llamar
GetInt para obtener un int real

261
00:11:03,830 --> 00:11:05,060
que desea buscar.

262
00:11:05,060 --> 00:11:06,460
>> Entonces note esto.

263
00:11:06,460 --> 00:11:10,690
Voy a crear una variable temporal
en línea 188 llama puntero -

264
00:11:10,690 --> 00:11:11,270
PTR -

265
00:11:11,270 --> 00:11:12,440
podrían haber llamado cualquier cosa.

266
00:11:12,440 --> 00:11:16,140
Y es un puntero a un nodo
porque he dicho nodo * allí.

267
00:11:16,140 --> 00:11:19,900
Y estoy inicializando que sea igual a
primero, para que yo efectivamente tengo mi

268
00:11:19,900 --> 00:11:22,860
dedo de la mano, por así decirlo, en el mismo
primer elemento de la lista.

269
00:11:22,860 --> 00:11:27,460
Así que si mi mano derecha aquí es PTR estoy
apuntando a lo mismo que la primera

270
00:11:27,460 --> 00:11:28,670
está apuntando.

271
00:11:28,670 --> 00:11:31,430
>> Así que ahora de nuevo en el código,
¿qué pasa después -

272
00:11:31,430 --> 00:11:35,070
este es un paradigma común cuando se repite
sobre una estructura como un

273
00:11:35,070 --> 00:11:35,970
lista enlazada.

274
00:11:35,970 --> 00:11:40,410
Yo voy a hacer lo siguiente mientras
puntero no es igual a null Así, mientras que

275
00:11:40,410 --> 00:11:47,530
mi dedo no está apuntando en algún nula
valor, si el puntero de flecha n es igual a n.

276
00:11:47,530 --> 00:11:52,290
Nos daremos cuenta primero que n es lo que el
tecleado por el usuario GetInts llamar aquí.

277
00:11:52,290 --> 00:11:54,280
>> Y puntero de flecha n significa qué?

278
00:11:54,280 --> 00:11:59,020
Bueno, si nos remontamos a la imagen aquí,
si tengo un dedo apuntando a

279
00:11:59,020 --> 00:12:02,960
que primero nodo que contiene nueve, la
flecha esencialmente significa que vaya a

280
00:12:02,960 --> 00:12:08,860
nodo y agarrar el valor en la posición n,
en este caso, el campo de datos llama n.

281
00:12:08,860 --> 00:12:14,120
>> Como acotación al margen - y vimos esto un par
de hace semanas, cuando alguien le preguntó -

282
00:12:14,120 --> 00:12:18,840
esta sintaxis es nuevo, pero no es así
darnos poderes que

283
00:12:18,840 --> 00:12:20,040
no ya tienen.

284
00:12:20,040 --> 00:12:25,325
¿Qué era esta frase equivale a utilizar
notación de puntos y protagonizar un par

285
00:12:25,325 --> 00:12:29,490
de hace semanas cuando nos pelamos espalda
esta capa un poco antes de tiempo?

286
00:12:29,490 --> 00:12:31,780
>> ESTUDIANTE: [inaudible].

287
00:12:31,780 --> 00:12:38,880
>> ALTAVOZ 1: Exactamente, era la estrella, y
entonces era punto estrella n, con

288
00:12:38,880 --> 00:12:41,930
paréntesis aquí, lo que se ve,
Francamente, creo que mucha

289
00:12:41,930 --> 00:12:43,320
más críptico de leer.

290
00:12:43,320 --> 00:12:46,270
Pero indicador de la estrella, como siempre,
medios van allí.

291
00:12:46,270 --> 00:12:49,090
¿Y una vez que estás allí, ¿qué datos
qué campo desea acceder?

292
00:12:49,090 --> 00:12:52,730
Pues usted utiliza la notación de puntos para el acceso
un campo de datos estructuras, y yo

293
00:12:52,730 --> 00:12:54,140
específicamente querer n.

294
00:12:54,140 --> 00:12:56,240
>> Francamente, yo diría esto
es simplemente más difícil de leer.

295
00:12:56,240 --> 00:12:58,080
Es más difícil de recordar dónde
salen de los paréntesis, la

296
00:12:58,080 --> 00:12:59,030
estrella y todo eso.

297
00:12:59,030 --> 00:13:02,150
Así que el mundo adoptó algunas sintáctica
azúcar, por así decirlo.

298
00:13:02,150 --> 00:13:04,740
Apenas una manera atractiva de decir,
esto es equivalente, y

299
00:13:04,740 --> 00:13:05,970
quizás más intuitivo.

300
00:13:05,970 --> 00:13:09,600
Si el puntero es de hecho un puntero, el
flecha notación significa ir allí y encontrar

301
00:13:09,600 --> 00:13:11,890
el campo, en este caso llamado n.

302
00:13:11,890 --> 00:13:13,660
>> Así que si lo encuentro, noto lo que hago.

303
00:13:13,660 --> 00:13:17,430
Simplemente me imprimo, encontré ciento i,
enchufar el valor para ese int.

304
00:13:17,430 --> 00:13:20,730
Yo lo llamo el sueño durante un segundo sólo para clase
de hacer una pausa en las cosas en la pantalla para

305
00:13:20,730 --> 00:13:22,900
dar al usuario un segundo para absorber
lo que acaba de suceder.

306
00:13:22,900 --> 00:13:24,290
Y entonces me rompo.

307
00:13:24,290 --> 00:13:26,330
De lo contrario, ¿qué hago?

308
00:13:26,330 --> 00:13:30,960
Actualizo puntero a la igualdad de
puntero flecha siguiente.

309
00:13:30,960 --> 00:13:35,840
>> Así que para ser claros, esto significa ir
allí, usando mi notación de la vieja escuela.

310
00:13:35,840 --> 00:13:39,580
Así que esto sólo significa ir a lo que sea
usted está apuntando a que, en el muy

311
00:13:39,580 --> 00:13:43,660
primer caso es que estoy señalando a
la estructura con nueve en el mismo.

312
00:13:43,660 --> 00:13:44,510
Así que he ido allí.

313
00:13:44,510 --> 00:13:47,880
Y entonces se entiende la notación de puntos,
obtener el valor al siguiente.

314
00:13:47,880 --> 00:13:50,470
>> Pero el valor, a pesar de que se dibuja
como un estrecho, es sólo un número.

315
00:13:50,470 --> 00:13:51,720
Es una dirección numérica.

316
00:13:51,720 --> 00:13:55,670
Así que esta una línea de código, ya sea
escrito como éste, el más críptico

317
00:13:55,670 --> 00:14:00,190
manera, o así, los poco más
manera intuitiva, simplemente significa mover mi mano

318
00:14:00,190 --> 00:14:03,460
desde el primer nodo al siguiente,
y luego el siguiente, y a continuación, la

319
00:14:03,460 --> 00:14:05,320
siguiente, y así sucesivamente.

320
00:14:05,320 --> 00:14:09,920
>> Así que no voy a detenerme en el otro
implementaciones de insertar y eliminar

321
00:14:09,920 --> 00:14:14,030
y el recorrido, los dos primeros de
que son bastante implicados.

322
00:14:14,030 --> 00:14:17,010
Y creo que es muy fácil de conseguir
perdido al hacerlo verbalmente.

323
00:14:17,010 --> 00:14:19,890
Pero lo que podemos hacer aquí es
tratar de determinar cómo

324
00:14:19,890 --> 00:14:21,640
la mejor manera de hacer esto visualmente.

325
00:14:21,640 --> 00:14:24,800
Porque yo propondría que si
desee insertar elementos en esta

326
00:14:24,800 --> 00:14:26,680
lista existente, que
tiene cinco elementos -

327
00:14:26,680 --> 00:14:29,530
9, 17, 22, 26, y 33 -

328
00:14:29,530 --> 00:14:33,300
si yo fuera a implementar esto en
código, tengo que estudiar la manera de ir

329
00:14:33,300 --> 00:14:34,160
haciendo esto.

330
00:14:34,160 --> 00:14:37,720
>> Y yo propondría tomar pasos de bebé
por lo que, en este caso me refiero, ¿cuáles son

331
00:14:37,720 --> 00:14:41,090
los posibles escenarios que nos
podría encontrarse en general?

332
00:14:41,090 --> 00:14:44,120
En la aplicación de inserción para un ligado
lista, esto sólo pasa a ser un

333
00:14:44,120 --> 00:14:46,090
ejemplo concreto de tamaño cinco.

334
00:14:46,090 --> 00:14:50,420
Bueno, si usted desea insertar un número,
como decir el número uno, y

335
00:14:50,420 --> 00:14:53,380
mantener el orden establecido, donde
obviamente, hace el número uno de la necesidad de

336
00:14:53,380 --> 00:14:55,686
ir en este ejemplo específico?

337
00:14:55,686 --> 00:14:56,840
Al igual que al principio.

338
00:14:56,840 --> 00:15:00,030
>> Pero lo interesante no es que
si desea insertar una en este

339
00:15:00,030 --> 00:15:04,100
lista, qué necesidades puntero especiales
ser actualizado aparentemente?

340
00:15:04,100 --> 00:15:04,610
En primer lugar.

341
00:15:04,610 --> 00:15:07,830
Así que yo diría, este es el primer caso
que lo que se quiere tener en cuenta, una

342
00:15:07,830 --> 00:15:11,140
escenario que implica insertar al
el principio de la lista.

343
00:15:11,140 --> 00:15:15,400
>> Vamos a arrancar tal vez una tan fácil o incluso
caso más fácil, relativamente hablando.

344
00:15:15,400 --> 00:15:18,110
Supongamos que quiero insertar el
el número 35 en el orden establecido.

345
00:15:18,110 --> 00:15:20,600
Obviamente pertenece allí.

346
00:15:20,600 --> 00:15:25,320
Entonces, ¿qué puntero obviamente va a
tienen que actualizarse en ese escenario?

347
00:15:25,320 --> 00:15:30,060
Un triple de 34 convirtiéndose no nula
pero la dirección de la estructura

348
00:15:30,060 --> 00:15:31,800
que contiene el número 35.

349
00:15:31,800 --> 00:15:32,750
Así que ese es el caso de dos.

350
00:15:32,750 --> 00:15:36,190
Así que ya, yo soy una especie de cuantificación
la cantidad de trabajo que tengo que hacer aquí.

351
00:15:36,190 --> 00:15:39,880
>> Y, por último, el caso medio obvio es
de hecho, en el medio, si quiero

352
00:15:39,880 --> 00:15:45,870
insertar algo así como decir 23, que va
entre el 23 y el 26, pero

353
00:15:45,870 --> 00:15:48,680
Ahora las cosas se ponen un poco más
participar porque lo

354
00:15:48,680 --> 00:15:52,800
punteros hay que cambiar?

355
00:15:52,800 --> 00:15:56,680
Así 22 obviamente necesita ser cambiado
porque no puede apuntar a 26 más.

356
00:15:56,680 --> 00:16:00,320
Él tiene que apuntar al nuevo nodo que
Voy a tener que destinar llamando

357
00:16:00,320 --> 00:16:01,770
malloc o algún equivalente.

358
00:16:01,770 --> 00:16:05,990
>> Pero también necesito que el nuevo nodo, 23
en este caso, para tener su puntero

359
00:16:05,990 --> 00:16:07,870
señalando a quién?

360
00:16:07,870 --> 00:16:08,560
26.

361
00:16:08,560 --> 00:16:10,380
Y va a ser un
orden de las operaciones aquí.

362
00:16:10,380 --> 00:16:13,410
Porque si hago esto tontamente, y yo
por ejemplo comenzar por el principio de

363
00:16:13,410 --> 00:16:16,040
la lista, y mi objetivo es insertar 23.

364
00:16:16,040 --> 00:16:18,610
Y compruebo, le pertenece
aquí, cerca de las nueve?

365
00:16:18,610 --> 00:16:18,950
No.

366
00:16:18,950 --> 00:16:20,670
¿Pertenece aquí, junto a 17?

367
00:16:20,670 --> 00:16:20,940
No.

368
00:16:20,940 --> 00:16:22,530
¿Le pertenece a este lugar junto a 22?

369
00:16:22,530 --> 00:16:23,300
Sí.

370
00:16:23,300 --> 00:16:26,400
>> Ahora bien, si soy tonto aquí, y no
pensando en esto, yo podría

371
00:16:26,400 --> 00:16:28,320
asignar mi nuevo nodo para 23.

372
00:16:28,320 --> 00:16:32,080
Yo podría actualizar el puntero de
el nodo llamado 22, que señala

373
00:16:32,080 --> 00:16:33,080
que en el nuevo nodo.

374
00:16:33,080 --> 00:16:36,140
Y entonces, ¿qué tengo que actualizar
puntero del nuevo nodo que se va?

375
00:16:36,140 --> 00:16:38,120
>> ESTUDIANTE: [inaudible].

376
00:16:38,120 --> 00:16:38,385
>> ALTAVOZ 1: Exactamente.

377
00:16:38,385 --> 00:16:39,710
Señalando a 26.

378
00:16:39,710 --> 00:16:45,590
Pero dammit si no tuviera ya actualizo
Puntero del 22 al punto en el que este tipo, y

379
00:16:45,590 --> 00:16:48,260
Ahora tengo los huérfanos, el resto
de la lista, por así decirlo.

380
00:16:48,260 --> 00:16:52,140
Así que el fin de las operaciones aquí
va a ser importante.

381
00:16:52,140 --> 00:16:55,100
>> Para ello podría robar,
decir, seis voluntarios.

382
00:16:55,100 --> 00:16:57,650
Y veamos si no podemos hacer esto
visualmente en lugar del código se refiere.

383
00:16:57,650 --> 00:16:59,330
Y tenemos un poco de estrés encantadora
bolas para usted hoy.

384
00:16:59,330 --> 00:17:02,510
Bien, ¿qué hay de una, dos, en el
espalda - en el extremo allí.

385
00:17:02,510 --> 00:17:04,530
tres, cuatro, los dos
chicos en la final.

386
00:17:04,530 --> 00:17:05,579
Y cinco, seis.

387
00:17:05,579 --> 00:17:05,839
Claro.

388
00:17:05,839 --> 00:17:06,450
Cinco y seis.

389
00:17:06,450 --> 00:17:08,390
Está bien y vamos a venir
con ustedes la próxima vez.

390
00:17:08,390 --> 00:17:09,640
Muy bien, vamos arriba.

391
00:17:09,640 --> 00:17:12,010

392
00:17:12,010 --> 00:17:14,819
>> Muy bien, ya que estás aquí primero,
¿te gustaría ser el que torpemente

393
00:17:14,819 --> 00:17:16,119
en Google Glass aquí?

394
00:17:16,119 --> 00:17:19,075
Muy bien, entonces, OK, Glass,
grabar un video.

395
00:17:19,075 --> 00:17:22,720

396
00:17:22,720 --> 00:17:24,589
Bueno, ya está bueno para ir.

397
00:17:24,589 --> 00:17:27,950
>> Muy bien, así que si ustedes pueden venir
aquí, he preparado con antelación

398
00:17:27,950 --> 00:17:30,110
algunos números.

399
00:17:30,110 --> 00:17:31,240
Muy bien, vamos por aquí.

400
00:17:31,240 --> 00:17:33,440
¿Y por qué no te vas un poco
promover de esa manera.

401
00:17:33,440 --> 00:17:35,520
Y vamos a ver, ¿cómo te llamas,
con el cristal de Google?

402
00:17:35,520 --> 00:17:35,910
>> ESTUDIANTE: Ben.

403
00:17:35,910 --> 00:17:36,230
>> ALTAVOZ 1: Ben?

404
00:17:36,230 --> 00:17:38,380
Bueno, Ben, que será la primera, literalmente.

405
00:17:38,380 --> 00:17:40,580
Así que vamos a enviarle
al final de la etapa.

406
00:17:40,580 --> 00:17:41,670
Muy bien, y tu nombre?

407
00:17:41,670 --> 00:17:41,990
>> ESTUDIANTE: Jason.

408
00:17:41,990 --> 00:17:44,530
>> ALTAVOZ 1: Jason, OK tendrás
ser el número nueve.

409
00:17:44,530 --> 00:17:46,700
Así que si quieres seguir Ben de esa manera.

410
00:17:46,700 --> 00:17:47,010
>> ESTUDIANTE: Jill.

411
00:17:47,010 --> 00:17:49,630
>> ALTAVOZ 1: Jill, vas a ser
17, que si yo hubiera hecho esto más

412
00:17:49,630 --> 00:17:51,260
inteligente, que tendría
comenzado en el otro extremo.

413
00:17:51,260 --> 00:17:52,370
Usted va de esa manera.

414
00:17:52,370 --> 00:17:53,030
22.

415
00:17:53,030 --> 00:17:53,670
Y usted es?

416
00:17:53,670 --> 00:17:53,980
>> ESTUDIANTE: María.

417
00:17:53,980 --> 00:17:56,130
>> ALTAVOZ 1: María, que será 22.

418
00:17:56,130 --> 00:17:58,420
Y su nombre es?

419
00:17:58,420 --> 00:17:58,810
>> ESTUDIANTE: Chris.

420
00:17:58,810 --> 00:18:00,100
>> ALTAVOZ 1: Chris, podrás 26.

421
00:18:00,100 --> 00:18:00,740
Y a continuación, por último.

422
00:18:00,740 --> 00:18:01,400
>> ESTUDIANTE: Diana.

423
00:18:01,400 --> 00:18:02,670
>> ALTAVOZ 1: Diana, usted será 34.

424
00:18:02,670 --> 00:18:03,920
Así que vienes por aquí.

425
00:18:03,920 --> 00:18:06,360
>> Muy bien, así que perfecto ordenados
ordenar ya.

426
00:18:06,360 --> 00:18:09,600
Y vamos a seguir adelante y hacer esto
para que podamos realmente -

427
00:18:09,600 --> 00:18:11,720
Ben sólo estás buscando tipo de
hacia la nada allí.

428
00:18:11,720 --> 00:18:15,670
OK, así que vamos a seguir adelante y representan esta
utilizando los brazos, al igual que yo, exactamente,

429
00:18:15,670 --> 00:18:16,250
¿qué está pasando.

430
00:18:16,250 --> 00:18:19,540
Así que adelante y dense un
o dos pies entre ustedes mismos.

431
00:18:19,540 --> 00:18:22,900
Y seguir adelante y punto con una mano para
quienquiera que debe apuntar a

432
00:18:22,900 --> 00:18:23,470
basado en esto.

433
00:18:23,470 --> 00:18:25,890
Y si usted es sólo el punto nulo
directamente hacia el suelo.

434
00:18:25,890 --> 00:18:27,690
OK, así que bien.

435
00:18:27,690 --> 00:18:32,290
>> Así que ahora tenemos una lista enlazada, y me dejó
Propongo que voy a jugar el papel de

436
00:18:32,290 --> 00:18:35,110
PTR, así que no me molestaré
llevar esto alrededor.

437
00:18:35,110 --> 00:18:37,830
Y entonces - alguien convención estúpida -
usted puede llamar a esto todo lo que quieras -

438
00:18:37,830 --> 00:18:39,800
puntero predecesor, puntero pred -

439
00:18:39,800 --> 00:18:43,930
es sólo el apodo que dimos en
nuestro código de ejemplo para la mano izquierda.

440
00:18:43,930 --> 00:18:47,240
La otra parte que va a ser de mantenimiento
Saber quién es quién en la

441
00:18:47,240 --> 00:18:48,400
siguientes escenarios.

442
00:18:48,400 --> 00:18:52,390
>> Así que supongamos que, en primer lugar, quiero arrancar
ese primer ejemplo de inserción, por ejemplo

443
00:18:52,390 --> 00:18:54,330
20, en la lista.

444
00:18:54,330 --> 00:18:57,160
Así que voy a necesitar a alguien que
encarnar el número 20 para nosotros.

445
00:18:57,160 --> 00:18:58,950
Así que tengo que malloc alguien
de la audiencia.

446
00:18:58,950 --> 00:18:59,380
Vamos arriba.

447
00:18:59,380 --> 00:19:00,340
¿Cómo te llamas?

448
00:19:00,340 --> 00:19:01,300
>> ESTUDIANTE: Brian.

449
00:19:01,300 --> 00:19:05,270
>> ALTAVOZ 1: Brian, de acuerdo, por lo que
será el nodo que contiene 20.

450
00:19:05,270 --> 00:19:06,810
Muy bien, vamos por aquí.

451
00:19:06,810 --> 00:19:10,025
Y, obviamente, donde
pertenece Brian?

452
00:19:10,025 --> 00:19:12,190
Así, en medio de - en realidad,
Espera un minuto.

453
00:19:12,190 --> 00:19:13,420
Estamos haciendo esta fuera de orden.

454
00:19:13,420 --> 00:19:17,170
Estamos haciendo esto mucho más difícil
de lo que debe ser en un principio.

455
00:19:17,170 --> 00:19:21,210
Bien, vamos a liberar a Brian
y realloc Brian como cinco.

456
00:19:21,210 --> 00:19:23,680
>> OK, así que ahora queremos insertar
Brian como cinco.

457
00:19:23,680 --> 00:19:25,960
Así que ven aquí al lado
Ben sólo por un momento.

458
00:19:25,960 --> 00:19:28,250
Y, presumiblemente, puede decir
donde esta historia se va.

459
00:19:28,250 --> 00:19:30,500
Pero vamos a pensar cuidadosamente acerca de
el orden de las operaciones.

460
00:19:30,500 --> 00:19:32,880
Y es precisamente esta visual
eso va a alinear

461
00:19:32,880 --> 00:19:34,080
con ese código de ejemplo.

462
00:19:34,080 --> 00:19:40,120
Así que aquí tengo PTR apuntando inicialmente
no a Ben, per se, sino en lo que sea

463
00:19:40,120 --> 00:19:43,245
valor que contiene, que en este caso
es - ¿cuál es tu nombre?

464
00:19:43,245 --> 00:19:43,670
>> ESTUDIANTE: Jason.

465
00:19:43,670 --> 00:19:47,350
>> ALTAVOZ 1: Jason, por lo tanto, Ben y yo estamos
señalando a Jason en este momento.

466
00:19:47,350 --> 00:19:49,700
Así que ahora tengo que determinar,
donde pertenece Brian?

467
00:19:49,700 --> 00:19:53,500
Así que lo único que tengo acceso a
ahora es su elemento de datos n.

468
00:19:53,500 --> 00:19:58,280
Así que voy a comprobar, es
Brian menos de Jason?

469
00:19:58,280 --> 00:19:59,770
La respuesta es verdadera.

470
00:19:59,770 --> 00:20:03,680
>> ¿Y ahora qué tiene que suceder,
en el orden correcto?

471
00:20:03,680 --> 00:20:07,120
Necesito actualizar el número de punteros
en total en esta historia?

472
00:20:07,120 --> 00:20:10,720
Donde mi mano todavía está apuntando a
Jason, y su mano - si usted desea

473
00:20:10,720 --> 00:20:12,930
poner su mano como, más o menos, me
no sé, un signo de interrogación.

474
00:20:12,930 --> 00:20:14,070
Bueno, bueno.

475
00:20:14,070 --> 00:20:15,670
>> Muy bien, por lo que tiene
algunos candidatos.

476
00:20:15,670 --> 00:20:20,500
Cualquiera de Ben, yo o Brian o Jason
o cualquier otra persona, que

477
00:20:20,500 --> 00:20:21,370
punteros tienen que cambiar?

478
00:20:21,370 --> 00:20:23,260
¿Cuántos en total?

479
00:20:23,260 --> 00:20:24,080
>> OK, así que dos.

480
00:20:24,080 --> 00:20:27,090
Mi puntero en realidad no importa ya
porque yo soy sólo temporal.

481
00:20:27,090 --> 00:20:31,370
Así que es a estos dos chicos, supuestamente,
tanto Ben y Brian.

482
00:20:31,370 --> 00:20:34,410
Así que permítanme proponer que actualizamos
Ben, ya que él es primero.

483
00:20:34,410 --> 00:20:36,350
El primer elemento de esta lista
ahora va a ser Brian.

484
00:20:36,350 --> 00:20:38,070
Así que el punto Ben en Brian.

485
00:20:38,070 --> 00:20:39,320
Bien, ¿y ahora qué?

486
00:20:39,320 --> 00:20:41,950

487
00:20:41,950 --> 00:20:43,460
>> ¿Quién se apunta a quién?

488
00:20:43,460 --> 00:20:44,710
>> ESTUDIANTE: [inaudible].

489
00:20:44,710 --> 00:20:46,180
>> ALTAVOZ 1: Aceptar lo que Brian tiene
para apuntar a Jason.

490
00:20:46,180 --> 00:20:48,360
Pero he perdido la cuenta de ese puntero?

491
00:20:48,360 --> 00:20:49,980
¿Sé dónde está Jason?

492
00:20:49,980 --> 00:20:50,790
>> ESTUDIANTE: [inaudible].

493
00:20:50,790 --> 00:20:52,620
>> ALTAVOZ 1: yo, como soy
el puntero temporal.

494
00:20:52,620 --> 00:20:55,110
Y, presumiblemente, no he cambiado
para señalar en el nuevo nodo.

495
00:20:55,110 --> 00:20:58,300
Así que simplemente podemos tener punto de Brian
en el que estoy señalando.

496
00:20:58,300 --> 00:20:59,000
Y ya hemos terminado.

497
00:20:59,000 --> 00:21:01,890
Así caso de que uno, la inserción en el
principio de la lista.

498
00:21:01,890 --> 00:21:02,950
Había dos pasos clave.

499
00:21:02,950 --> 00:21:06,750
Uno de ellos, tenemos que actualizar Ben, y luego
también tenemos que actualizar Brian.

500
00:21:06,750 --> 00:21:09,230
Y entonces yo no tengo que molestar
penosamente a través de el resto de la

501
00:21:09,230 --> 00:21:12,680
enumerar, porque ya encontramos su
ubicación, porque pertenecía a la

502
00:21:12,680 --> 00:21:14,080
la izquierda del primer elemento.

503
00:21:14,080 --> 00:21:15,400
>> Muy bien, así que bastante sencillo.

504
00:21:15,400 --> 00:21:18,110
De hecho, se siente como que estamos casi
haciendo esto demasiado complicado.

505
00:21:18,110 --> 00:21:20,240
Así que ahora vamos a arrancar el final
de la lista, y ver dónde

506
00:21:20,240 --> 00:21:21,380
la complejidad comienza.

507
00:21:21,380 --> 00:21:24,560
Así que si ahora, de asignación de la audiencia.

508
00:21:24,560 --> 00:21:25,540
¿Alguien quiere jugar al 55?

509
00:21:25,540 --> 00:21:26,700
Muy bien, lo vi primero su mano.

510
00:21:26,700 --> 00:21:29,620
Vamos arriba.

511
00:21:29,620 --> 00:21:30,030
Sí.

512
00:21:30,030 --> 00:21:31,177
¿Cómo te llamas?

513
00:21:31,177 --> 00:21:32,310
>> ESTUDIANTE: [inaudible].

514
00:21:32,310 --> 00:21:33,240
>> ALTAVOZ 1: Habata.

515
00:21:33,240 --> 00:21:33,890
Bien, vamos arriba.

516
00:21:33,890 --> 00:21:35,730
Usted será el número 55.

517
00:21:35,730 --> 00:21:37,820
Así que, por supuesto, pertenece
al final de la lista.

518
00:21:37,820 --> 00:21:41,850
Así que vamos a jugar de nuevo la simulación conmigo
siendo el PTR por un momento.

519
00:21:41,850 --> 00:21:44,050
Así que estoy primero va a apuntar a
lo que apunta a Ben.

520
00:21:44,050 --> 00:21:45,900
Los dos estamos apuntando ahora a Brian.

521
00:21:45,900 --> 00:21:48,420
Así que 55 no sea inferior a cinco.

522
00:21:48,420 --> 00:21:52,510
Así que voy a actualizar mi mismo por
apuntando a la siguiente triple de Brian, que

523
00:21:52,510 --> 00:21:54,450
ahora es, por supuesto, Jason.

524
00:21:54,450 --> 00:21:57,310
55 no sea inferior a nueve, por lo que
Voy a actualizar PTR.

525
00:21:57,310 --> 00:21:58,890
Voy a actualizar PTR.

526
00:21:58,890 --> 00:22:02,290
Voy a actualizar PTR
Me va a actualizar PTR.

527
00:22:02,290 --> 00:22:05,060
Y yo voy a - hmm, ¿qué
tu nombre?

528
00:22:05,060 --> 00:22:05,560
>> ESTUDIANTE: Diana.

529
00:22:05,560 --> 00:22:09,190
>> ALTAVOZ 1: Diana está señalando, por supuesto,
en nulo con la mano izquierda.

530
00:22:09,190 --> 00:22:13,030
Así que ¿de dónde viene en realidad Habata
pertenecer claramente?

531
00:22:13,030 --> 00:22:15,050
A la izquierda, aquí.

532
00:22:15,050 --> 00:22:19,460
Entonces, ¿cómo puedo saber que ponerla aquí
Creo que he metido la pata.

533
00:22:19,460 --> 00:22:22,420
Porque lo que es arte PTR
este momento en el tiempo?

534
00:22:22,420 --> 00:22:23,240
Null.

535
00:22:23,240 --> 00:22:25,580
Así que a pesar de que, visualmente, podemos
obviamente ver todos estos

536
00:22:25,580 --> 00:22:26,610
chicos aquí en el escenario.

537
00:22:26,610 --> 00:22:29,680
Yo no he mantenido un seguimiento de la anterior
persona en la lista.

538
00:22:29,680 --> 00:22:33,210
Yo no tengo un dedo señalando,
en este caso, el número de nodo 34.

539
00:22:33,210 --> 00:22:34,760
>> Así que vamos a empezar en realidad esta vez.

540
00:22:34,760 --> 00:22:37,560
Así que ahora realmente necesito
una segunda variable local.

541
00:22:37,560 --> 00:22:40,980
Y esto es lo que verás en el
código de ejemplo C real, en tanto que yo voy,

542
00:22:40,980 --> 00:22:45,860
cuando actualizo mi mano derecha para señalar
Jason, dejando detrás de Brian, me

543
00:22:45,860 --> 00:22:51,440
mejor empezar a usar mi mano izquierda para
Actualiza donde yo estaba, de modo que a medida que avanzo

544
00:22:51,440 --> 00:22:52,700
a través de esta lista -

545
00:22:52,700 --> 00:22:55,040
más torpe de lo que pretendía
ahora aquí visualmente -

546
00:22:55,040 --> 00:22:56,740
Voy a llegar a la
final de la lista.

547
00:22:56,740 --> 00:23:00,020
>> Esta mano es todavía nula, lo cual es bastante
inútil, salvo para indicar

548
00:23:00,020 --> 00:23:02,980
Estoy claramente al final de la lista,
pero ahora por lo menos tengo esta

549
00:23:02,980 --> 00:23:08,270
puntero predecesor señalando aquí, así
ahora lo que las manos y lo que necesitan punteros

550
00:23:08,270 --> 00:23:10,150
ser actualizado?

551
00:23:10,150 --> 00:23:13,214
Cuya mano es lo que quieres
reconfigurar primero?

552
00:23:13,214 --> 00:23:15,190
>> ESTUDIANTE: [inaudible].

553
00:23:15,190 --> 00:23:16,220
>> ALTAVOZ 1: OK, así que Diana.

554
00:23:16,220 --> 00:23:21,110
¿Dónde quieres que señalar
Diana del puntero de la izquierda en?

555
00:23:21,110 --> 00:23:23,620
En 55, presumiblemente, de manera que
hemos insertado allí.

556
00:23:23,620 --> 00:23:25,560
¿Y dónde debería ir el 55 de puntero?

557
00:23:25,560 --> 00:23:27,000
Presionado, que representa un valor nulo.

558
00:23:27,000 --> 00:23:28,890
Y mis manos, en este punto, no lo hacen
importa porque no eran más que

559
00:23:28,890 --> 00:23:30,070
variables temporales.

560
00:23:30,070 --> 00:23:31,030
Así que ahora que hemos terminado.

561
00:23:31,030 --> 00:23:34,650
>> Así que la complejidad adicional allí - y
que no es tan difícil de implementar,

562
00:23:34,650 --> 00:23:38,660
pero necesitamos una variable secundaria para hacer
Asegúrese de que antes de pasar a mi derecho

563
00:23:38,660 --> 00:23:42,140
lado, puedo actualizar el valor de mi izquierda
mano, puntero pred en este caso, por lo

564
00:23:42,140 --> 00:23:45,860
que tengo un indicador de seguimiento
hacer un seguimiento de dónde estaba.

565
00:23:45,860 --> 00:23:49,360
Ahora, como un aparte, si estás pensando en este
a través, esto se siente como si fuera un

566
00:23:49,360 --> 00:23:51,490
poco molesto tener que mantener
seguimiento de esta mano izquierda.

567
00:23:51,490 --> 00:23:54,015
>> ¿Qué sería de otra solución
a este problema han sido?

568
00:23:54,015 --> 00:23:56,500
Si has llegado a rediseñar los datos
estructura que estamos hablando

569
00:23:56,500 --> 00:23:59,630
a través de estos momentos?

570
00:23:59,630 --> 00:24:02,690
Si sólo un poco se siente un poco
molesto tener, como, dos punteros

571
00:24:02,690 --> 00:24:08,430
pasando por la lista, ¿quién más podría
han, en un mundo ideal, mantenido

572
00:24:08,430 --> 00:24:10,160
información que necesitamos?

573
00:24:10,160 --> 00:24:11,360
¿Sí?

574
00:24:11,360 --> 00:24:12,610
>> ESTUDIANTE: [inaudible].

575
00:24:12,610 --> 00:24:15,160

576
00:24:15,160 --> 00:24:16,150
>> ALTAVOZ 1: Exactamente.

577
00:24:16,150 --> 00:24:19,130
Justo lo que hay realmente una interesante
germen de una idea.

578
00:24:19,130 --> 00:24:22,470
Y esta idea de un puntero anterior,
señalando el elemento anterior.

579
00:24:22,470 --> 00:24:25,580
¿Y si sólo encarnó ese
dentro de la propia lista?

580
00:24:25,580 --> 00:24:27,810
Y va a ser difícil de visualizar
esto sin todo el papel

581
00:24:27,810 --> 00:24:28,830
cayendo al suelo.

582
00:24:28,830 --> 00:24:31,860
Pero supongamos que estos chicos utilizan tanto
de sus manos para tener un anterior

583
00:24:31,860 --> 00:24:35,950
puntero, y un indicador de siguiente, con lo que
aplicación de lo que vamos a llamar a un doble

584
00:24:35,950 --> 00:24:36,830
lista enlazada.

585
00:24:36,830 --> 00:24:41,090
Eso me permitiría especie de rebobinado,
mucho más fácilmente sin mí, el

586
00:24:41,090 --> 00:24:43,800
programador, tener que mantener
seguimiento manual -

587
00:24:43,800 --> 00:24:44,980
verdaderamente manualmente -

588
00:24:44,980 --> 00:24:47,280
de donde había estado previamente
en la lista.

589
00:24:47,280 --> 00:24:48,110
Así que no vamos a hacer eso.

590
00:24:48,110 --> 00:24:50,950
Vamos a mantenerlo simple, porque eso es
va a tener un precio, el doble de

591
00:24:50,950 --> 00:24:53,450
mucho espacio para los punteros,
si quieres una segunda.

592
00:24:53,450 --> 00:24:55,760
Pero eso es de hecho una común
estructura de datos conocida como una

593
00:24:55,760 --> 00:24:57,410
lista doblemente enlazada.

594
00:24:57,410 --> 00:25:01,310
>> Vamos a hacer el último ejemplo aquí y poner
estos chicos fuera de su miseria.

595
00:25:01,310 --> 00:25:03,270
Así malloc 20.

596
00:25:03,270 --> 00:25:05,320
Vamos desde el pasillo allí.

597
00:25:05,320 --> 00:25:06,280
Muy bien, ¿cuál es tu nombre?

598
00:25:06,280 --> 00:25:07,440
>> ESTUDIANTE: [inaudible].

599
00:25:07,440 --> 00:25:07,855
>> ALTAVOZ 1: ¿Cómo dice?

600
00:25:07,855 --> 00:25:08,480
>> ESTUDIANTE: [inaudible].

601
00:25:08,480 --> 00:25:09,410
>> ALTAVOZ 1: Demeron?

602
00:25:09,410 --> 00:25:10,230
Aceptar vamos arriba.

603
00:25:10,230 --> 00:25:11,910
Usted será el 20.

604
00:25:11,910 --> 00:25:14,720
Usted, evidentemente, va a
pertenecen entre el 17 y el 22.

605
00:25:14,720 --> 00:25:16,150
Así que vamos a aprender la lección.

606
00:25:16,150 --> 00:25:18,150
Voy a empezar puntero
señalando a Brian.

607
00:25:18,150 --> 00:25:21,190
Y yo voy a tener mi mano izquierda
sólo actualizar a Brian como me mudo a

608
00:25:21,190 --> 00:25:23,600
Jason, la comprobación hace 20 menos de nueve?

609
00:25:23,600 --> 00:25:24,060
No.

610
00:25:24,060 --> 00:25:25,430
Es 20 menos de 17?

611
00:25:25,430 --> 00:25:25,880
No.

612
00:25:25,880 --> 00:25:27,450
Es 20 menos de 22?

613
00:25:27,450 --> 00:25:28,440
Sí.

614
00:25:28,440 --> 00:25:34,070
Entonces, ¿qué consejos o las manos deben cambiar
donde están apuntando ahora?

615
00:25:34,070 --> 00:25:37,070
>> Así que podemos hacer 17 que apunta a los 20.

616
00:25:37,070 --> 00:25:37,860
Así que eso está bien.

617
00:25:37,860 --> 00:25:40,080
¿Dónde queremos señalar
el puntero ahora?

618
00:25:40,080 --> 00:25:41,330
A los 22 años.

619
00:25:41,330 --> 00:25:45,410
Y sabemos donde 22 es, de nuevo, gracias
a mi puntero temporal.

620
00:25:45,410 --> 00:25:46,760
Así que estamos bien allí.

621
00:25:46,760 --> 00:25:49,440
Así que debido a esto el almacenamiento temporal
He mantenido un seguimiento de dónde es cada uno.

622
00:25:49,440 --> 00:25:55,055
Y ahora usted puede ir visualmente en donde
al que pertenece, y ahora nos necesita 1, 2, 3,

623
00:25:55,055 --> 00:25:58,410
4, 5, 6, 7, 8, 9 bolas de la tensión,
y una ronda de aplausos para

624
00:25:58,410 --> 00:25:59,770
estos chicos, si pudiéramos.

625
00:25:59,770 --> 00:26:00,410
Muy bien hecho.

626
00:26:00,410 --> 00:26:05,320
>> [Aplausos]

627
00:26:05,320 --> 00:26:06,330
>> ALTAVOZ 1: Muy bien.

628
00:26:06,330 --> 00:26:09,860
Y es posible mantener las piezas
de papel como recuerdos.

629
00:26:09,860 --> 00:26:15,930
>> Muy bien, entonces, confía en mí que es mucho
fácil de caminar a través de eso con

630
00:26:15,930 --> 00:26:17,680
los seres humanos que es con código real.

631
00:26:17,680 --> 00:26:22,690
Pero lo que encontrará en un momento
ahora, es el mismo - oh, gracias.

632
00:26:22,690 --> 00:26:23,630
Gracias -

633
00:26:23,630 --> 00:26:29,360
es que usted encontrará que los mismos datos
estructura, una lista enlazada, puede en realidad

634
00:26:29,360 --> 00:26:33,200
ser utilizado como un bloque de construcción para aún más
estructuras de datos sofisticadas.

635
00:26:33,200 --> 00:26:37,620
>> Y se dan cuenta demasiado el tema aquí es que
que absolutamente hemos introducido más

636
00:26:37,620 --> 00:26:40,060
complejidad en la implementación
de este algoritmo.

637
00:26:40,060 --> 00:26:43,940
Inserción, y si nos fuimos a través de él,
supresión y búsqueda, es un poco de

638
00:26:43,940 --> 00:26:46,660
más complicado de lo que
estaba con una matriz.

639
00:26:46,660 --> 00:26:48,040
Pero ganamos algo de dinamismo.

640
00:26:48,040 --> 00:26:50,180
Tenemos una estructura de datos de adaptación.

641
00:26:50,180 --> 00:26:54,010
>> Pero, de nuevo, tenemos que pagar un precio de tener alguna
complejidad adicional, tanto en

642
00:26:54,010 --> 00:26:54,910
su aplicación.

643
00:26:54,910 --> 00:26:56,750
Y se nos da el acceso aleatorio.

644
00:26:56,750 --> 00:27:00,450
Y para ser honesto, no hay algún buen
portaobjetos limpio me puede dar esa

645
00:27:00,450 --> 00:27:03,120
dice aquí es por qué una lista enlazada
es mejor que una matriz.

646
00:27:03,120 --> 00:27:04,100
Y dejar las cosas así.

647
00:27:04,100 --> 00:27:07,520
Debido a que el tema recurrente ahora, incluso
más aún en las próximas semanas, es

648
00:27:07,520 --> 00:27:10,200
que no es necesariamente
una respuesta correcta.

649
00:27:10,200 --> 00:27:13,830
>> Es por eso que tenemos el eje por separado
de diseñar para los boletines de problemas.

650
00:27:13,830 --> 00:27:17,700
Va a ser muy sensible al contexto
si desea utilizar estos datos

651
00:27:17,700 --> 00:27:21,750
estructura o que uno, y lo hará
dependerá de lo que te importa en términos

652
00:27:21,750 --> 00:27:24,620
de los recursos y la complejidad.

653
00:27:24,620 --> 00:27:28,830
>> Pero permítanme proponer que los datos ideales
estructura, el santo grial, sería

654
00:27:28,830 --> 00:27:32,200
algo que es constante de tiempo,
independientemente de la cantidad de cosas es

655
00:27:32,200 --> 00:27:36,940
dentro de él, ¿no sería increíble si un
estructura de datos devuelve respuestas en

656
00:27:36,940 --> 00:27:37,920
constante de tiempo.

657
00:27:37,920 --> 00:27:38,330
Sí.

658
00:27:38,330 --> 00:27:40,110
Esta palabra es en su gran diccionario.

659
00:27:40,110 --> 00:27:41,550
O no, esta palabra no es.

660
00:27:41,550 --> 00:27:43,270
O tal problema.

661
00:27:43,270 --> 00:27:46,360
Bueno vamos a ver si no podemos, al menos,
dar un paso en esa dirección.

662
00:27:46,360 --> 00:27:50,190
>> Permítanme proponer una nueva estructura de datos que
puede ser utilizado para diferentes cosas,

663
00:27:50,190 --> 00:27:52,260
en este caso se llama una tabla hash.

664
00:27:52,260 --> 00:27:55,590
Y por lo que estamos realmente de nuevo a mirar
en una matriz, en este caso, y

665
00:27:55,590 --> 00:28:00,550
algo arbitrariamente, he dibujado esta
la tabla de hash como una matriz con una especie de

666
00:28:00,550 --> 00:28:02,810
matriz de dos dimensiones -

667
00:28:02,810 --> 00:28:05,410
o más bien que está representado aquí como dos
matriz bidimensional - pero esto es sólo

668
00:28:05,410 --> 00:28:10,770
una matriz de tamaño 26, de tal manera que si nos
llame a la mesa de matriz, soporte de mesa

669
00:28:10,770 --> 00:28:12,440
cero es el rectángulo en la parte superior.

670
00:28:12,440 --> 00:28:15,090
Tabla soporte 25 es el rectángulo
en la parte inferior.

671
00:28:15,090 --> 00:28:18,620
Y así es como yo podría dibujar un datos
estructura en la que quiero para almacenar

672
00:28:18,620 --> 00:28:19,790
nombres de las personas.

673
00:28:19,790 --> 00:28:24,370
>> Así por ejemplo, y no voy a señalar a la
Todo aquí en la cabeza, si me

674
00:28:24,370 --> 00:28:29,160
tenido esta matriz, que ahora voy a
llamar a una tabla hash, y esto es de nuevo

675
00:28:29,160 --> 00:28:31,360
ubicación cero.

676
00:28:31,360 --> 00:28:34,840
Esto aquí es la ubicación
uno, y así sucesivamente.

677
00:28:34,840 --> 00:28:37,880
Afirmo que quiero utilizar estos datos
estructura, por el bien de la discusión,

678
00:28:37,880 --> 00:28:42,600
para almacenar nombres de las personas, Alice y Bob
y Charlie y otros nombres.

679
00:28:42,600 --> 00:28:46,110
Así que pensar en esto ahora como el inicio
de, por ejemplo, un diccionario

680
00:28:46,110 --> 00:28:47,520
con un montón de palabras.

681
00:28:47,520 --> 00:28:49,435
Ellos resultan ser nombres
en nuestro ejemplo aquí.

682
00:28:49,435 --> 00:28:52,560
Y esto es muy pertinente, tal vez, para
la implementación de un corrector ortográfico, como hemos

683
00:28:52,560 --> 00:28:54,400
fuerza para la solución seises.

684
00:28:54,400 --> 00:28:59,300
>> Así que si tenemos una matriz de tamaño total de 26
de manera que esta es la ubicación 25a

685
00:28:59,300 --> 00:29:03,390
en la parte inferior, y yo sostengo que Alice es
la primera palabra en el diccionario de

686
00:29:03,390 --> 00:29:07,260
nombres que quiero insertar en la memoria RAM,
en esta estructura de datos, donde son

687
00:29:07,260 --> 00:29:12,480
instintos que le dice que de Alice
nombre debe ir en esta serie?

688
00:29:12,480 --> 00:29:13,510
>> Tenemos 26 opciones.

689
00:29:13,510 --> 00:29:14,990
Dónde queremos ponerla?

690
00:29:14,990 --> 00:29:16,200
Nosotros la queremos en soporte de cero, ¿no?

691
00:29:16,200 --> 00:29:18,280
Una de Alice, vamos a llamar a ese cero.

692
00:29:18,280 --> 00:29:20,110
Y B será uno, y C será de dos.

693
00:29:20,110 --> 00:29:22,600
Así que vamos a escribir
El nombre de Alice aquí.

694
00:29:22,600 --> 00:29:24,890
Si a continuación, insertamos Bob, su
nombre pasará aquí.

695
00:29:24,890 --> 00:29:27,280
Charlie va a ir aquí.

696
00:29:27,280 --> 00:29:30,500
Y así sucesivamente a lo largo de
esta estructura de datos.

697
00:29:30,500 --> 00:29:32,090
>> Esta es una estructura de datos maravillosa.

698
00:29:32,090 --> 00:29:32,730
¿Por qué?

699
00:29:32,730 --> 00:29:37,460
Bueno, ¿qué es el tiempo de ejecución de
insertar el nombre de un ser humano en este

700
00:29:37,460 --> 00:29:39,850
estructura de datos en este momento?

701
00:29:39,850 --> 00:29:43,702
Teniendo en cuenta que esta tabla se implementa,
verdaderamente, como una matriz.

702
00:29:43,702 --> 00:29:44,940
Bueno, es la constante de tiempo.

703
00:29:44,940 --> 00:29:45,800
Es el fin de una.

704
00:29:45,800 --> 00:29:46,360
¿Por qué?

705
00:29:46,360 --> 00:29:48,630
>> Bueno, ¿cómo determinar
donde pertenece Alice?

706
00:29:48,630 --> 00:29:51,000
Te ves en qué letra de su nombre?

707
00:29:51,000 --> 00:29:51,490
El primero.

708
00:29:51,490 --> 00:29:54,350
Y se puede llegar, si se trata de una cadena,
con sólo mirar cadena

709
00:29:54,350 --> 00:29:55,200
soporte de cero.

710
00:29:55,200 --> 00:29:57,110
Así el carácter de orden cero de la cadena.

711
00:29:57,110 --> 00:29:57,610
Eso es fácil.

712
00:29:57,610 --> 00:30:00,350
Hicimos eso en la criptografía
Hace asignación semana.

713
00:30:00,350 --> 00:30:05,310
Y luego, una vez que sabes que de Alice
letra es mayúscula, podemos restar

714
00:30:05,310 --> 00:30:08,160
off 65 o la propia capital de A,
eso nos da cero.

715
00:30:08,160 --> 00:30:10,940
Así que ahora sabemos que Alice pertenece
en la posición cero.

716
00:30:10,940 --> 00:30:14,240
>> Y teniendo en cuenta un puntero a estos datos
estructura, de algún tipo, hace cuánto tiempo

717
00:30:14,240 --> 00:30:18,840
que me lleve a encontrar la ubicación
cero en una matriz?

718
00:30:18,840 --> 00:30:22,080
A sólo un paso, ¿no es la constante de tiempo
por la que el acceso aleatorio

719
00:30:22,080 --> 00:30:23,780
propuso fue una característica de una matriz.

720
00:30:23,780 --> 00:30:28,570
Así que en resumen, averiguar lo que el índice de
el nombre de de Alice es, que es, en

721
00:30:28,570 --> 00:30:32,610
este caso, es A, o vamos a resolver
que a cero, donde B es uno y C es

722
00:30:32,610 --> 00:30:34,900
dos, pensando que fuera
es la constante de tiempo.

723
00:30:34,900 --> 00:30:38,510
Sólo tengo que mirar en su primera carta,
averiguar donde cero es un

724
00:30:38,510 --> 00:30:40,460
matriz es también constante de tiempo.

725
00:30:40,460 --> 00:30:42,140
Así que técnicamente eso es
como dos pasos ahora.

726
00:30:42,140 --> 00:30:43,330
Pero eso sigue siendo constante.

727
00:30:43,330 --> 00:30:46,880
Así que llamamos a esa gran O de uno, por lo que hemos
Alice inserta en esta tabla en

728
00:30:46,880 --> 00:30:48,440
constante de tiempo.

729
00:30:48,440 --> 00:30:50,960
>> Pero, por supuesto, estoy siendo
ingenuo, ¿no?

730
00:30:50,960 --> 00:30:53,240
¿Qué pasa si hay un Aarón en la clase?

731
00:30:53,240 --> 00:30:53,990
O Alicia?

732
00:30:53,990 --> 00:30:57,230
O cualquier otro nombre que comience con
A. ¿Dónde vamos a poner

733
00:30:57,230 --> 00:31:00,800
esa persona, ¿verdad?

734
00:31:00,800 --> 00:31:03,420
Quiero decir, ahora mismo sólo hay tres
gente en la mesa, así que tal vez

735
00:31:03,420 --> 00:31:07,490
debe poner Aaron en la ubicación
cero uno dos tres.

736
00:31:07,490 --> 00:31:09,480
>> Bien, yo podría poner una aquí.

737
00:31:09,480 --> 00:31:13,350
Pero entonces, si se quiere insertar en David
esta lista, ¿a dónde va David?

738
00:31:13,350 --> 00:31:15,170
Ahora nuestro sistema comienza a metabolizar
abajo, derecha?

739
00:31:15,170 --> 00:31:19,210
Porque ahora David termina aquí
si Aaron es en realidad aquí.

740
00:31:19,210 --> 00:31:23,060
Y por lo que ahora esta todo idea de tener un
estructura de datos limpia que nos da

741
00:31:23,060 --> 00:31:28,010
inserciones de tiempo constantes ya no es
constante de tiempo, porque tengo que

742
00:31:28,010 --> 00:31:31,240
comprobar, oh, maldita sea, ya hay alguien trabajando
en la ubicación de Alice.

743
00:31:31,240 --> 00:31:35,320
>> Permítame sondear el resto de estos datos
estructura, en busca de un lugar para poner

744
00:31:35,320 --> 00:31:37,130
alguien como el nombre de Aarón.

745
00:31:37,130 --> 00:31:39,390
Y para que también está empezando
tomar el tiempo lineal.

746
00:31:39,390 --> 00:31:42,710
Por otra parte, si ahora quieres encontrar el
Aaron en esta estructura de datos, y

747
00:31:42,710 --> 00:31:45,430
cheque, y el nombre de Aarón no está aquí.

748
00:31:45,430 --> 00:31:47,960
Lo ideal sería que usted acaba de decir de Aarón
no en la estructura de datos.

749
00:31:47,960 --> 00:31:51,530
Pero si usted comienza a hacer espacio para
Aaron donde debería haber sido un D

750
00:31:51,530 --> 00:31:55,600
o un correo, usted, peor de los casos, tiene que comprobar
toda la estructura de datos, en

751
00:31:55,600 --> 00:31:59,480
cuyo caso se convirtiera en algo
lineal en el tamaño de la tabla.

752
00:31:59,480 --> 00:32:00,920
>> Así bien, voy a arreglar esto.

753
00:32:00,920 --> 00:32:04,200
El problema aquí es que tuve
26 elementos de esta matriz.

754
00:32:04,200 --> 00:32:05,000
Permítanme cambiaré.

755
00:32:05,000 --> 00:32:06,010
¡Vaya.

756
00:32:06,010 --> 00:32:10,600
Déjame cambiar de tal manera que en lugar de ser de
talla 26 en total, cuenta de la parte inferior

757
00:32:10,600 --> 00:32:12,720
índice se va a cambiar a n menos 1.

758
00:32:12,720 --> 00:32:16,610
Si 26 es claramente demasiado pequeño para los seres humanos "
nombres, porque hay miles de

759
00:32:16,610 --> 00:32:20,830
nombres del mundo, vamos a hacer
en 100 o 1000 o 10000.

760
00:32:20,830 --> 00:32:22,960
Vamos a asignar un espacio mucho más.

761
00:32:22,960 --> 00:32:27,230
>> Bueno, eso no disminuye necesariamente
la probabilidad de que no vamos a tener dos

762
00:32:27,230 --> 00:32:31,510
personas con nombres que empiecen con A, y
así, que iba a tratar de poner un

763
00:32:31,510 --> 00:32:33,120
nombres en lugar de cero aún.

764
00:32:33,120 --> 00:32:36,850
Siguen yendo a chocar, que
significa que todavía necesitamos una solución para poner

765
00:32:36,850 --> 00:32:41,020
Alice y Aarón y Alicia y otros
nombres que empiecen con A otro lugar.

766
00:32:41,020 --> 00:32:43,460
Pero, ¿cuánto de un problema es el siguiente?

767
00:32:43,460 --> 00:32:46,870
¿Cuál es la probabilidad de que
tener colisiones en un datos

768
00:32:46,870 --> 00:32:48,240
estructura como esta?

769
00:32:48,240 --> 00:32:52,570
>> Bueno, déjame - volveremos
a esa pregunta aquí.

770
00:32:52,570 --> 00:32:55,530
Y mira cómo podríamos
resolverlo primero.

771
00:32:55,530 --> 00:32:58,480
Déjame sacar esta propuesta aquí.

772
00:32:58,480 --> 00:33:02,020
Lo que acabamos de describir es un algoritmo,
una heurística llamada lineal

773
00:33:02,020 --> 00:33:05,030
sondeo según el cual, si se trató de insertar
algo aquí en estos datos

774
00:33:05,030 --> 00:33:08,920
estructura, que se llama una tabla hash,
y no hay lugar allí,

775
00:33:08,920 --> 00:33:12,000
verdaderamente sondear la estructura de datos
cheques, es este disponible?

776
00:33:12,000 --> 00:33:13,430
¿Es esta disponible es esta disponible?

777
00:33:13,430 --> 00:33:13,980
Es esta disposición?

778
00:33:13,980 --> 00:33:17,550
Y cuando finalmente es, insertar el
nombre que la intención original

779
00:33:17,550 --> 00:33:19,370
en otro lugar en esa ubicación.

780
00:33:19,370 --> 00:33:23,360
Pero en el peor de los casos, el único punto
podría ser la parte inferior de los datos

781
00:33:23,360 --> 00:33:25,090
estructura, el final de la matriz.

782
00:33:25,090 --> 00:33:30,130
>> Así sondeo lineal, en el peor de los casos,
recae en un algoritmo lineal en

783
00:33:30,130 --> 00:33:34,500
Aaron, si él pasa a ser insertado última
en esta estructura de datos, que podría

784
00:33:34,500 --> 00:33:39,540
colisionar con esta primera ubicación, pero
luego terminar por la mala suerte en el final.

785
00:33:39,540 --> 00:33:43,940
Así que esto no es una constante
santo grial tiempo para nosotros.

786
00:33:43,940 --> 00:33:47,650
Este enfoque de la inserción de elementos en
una estructura de datos llamada un valor hash

787
00:33:47,650 --> 00:33:52,050
tabla no parece ser la constante de tiempo
al menos no en el caso general.

788
00:33:52,050 --> 00:33:54,000
Puede delegar en algo lineal.

789
00:33:54,000 --> 00:33:56,970
>> ¿Y qué si resolvemos las colisiones
algo diferente?

790
00:33:56,970 --> 00:34:00,740
Así que aquí está una más sofisticada
aproximación a lo que es aún

791
00:34:00,740 --> 00:34:02,800
denominada tabla hash.

792
00:34:02,800 --> 00:34:05,890
Y por hash, como un aparte, lo que
Quiero decir es el índice que

793
00:34:05,890 --> 00:34:07,070
Me he referido antes.

794
00:34:07,070 --> 00:34:09,810
Para discutir algo puede ser
considerado como un verbo.

795
00:34:09,810 --> 00:34:13,690
>> Así que si el hash de Alice un nombre,
una función hash, por así decirlo,

796
00:34:13,690 --> 00:34:14,710
debe devolver un número.

797
00:34:14,710 --> 00:34:18,199
En este caso es cero si pertenece a
posición cero, uno si ella pertenece al

798
00:34:18,199 --> 00:34:20,000
ubicación uno, y así sucesivamente.

799
00:34:20,000 --> 00:34:24,360
Así que mi función hash hasta ahora ha sido
super simple, sólo mirando el

800
00:34:24,360 --> 00:34:26,159
primera letra del nombre de alguien.

801
00:34:26,159 --> 00:34:29,090
Pero una función hash toma como
entrada de alguna pieza de datos, un

802
00:34:29,090 --> 00:34:30,210
cadena, un entero, lo que sea.

803
00:34:30,210 --> 00:34:32,239
Y escupe típicamente un número.

804
00:34:32,239 --> 00:34:35,739
Y ese número es donde los datos
elemento pertenece en una estructura de datos

805
00:34:35,739 --> 00:34:37,800
conocido aquí como una tabla hash.

806
00:34:37,800 --> 00:34:41,400
>> Por lo que sólo intuitivamente, se trata de una
un contexto ligeramente distinto.

807
00:34:41,400 --> 00:34:44,170
En realidad, esto se refiere a un ejemplo
involucrando los cumpleaños, donde

808
00:34:44,170 --> 00:34:46,850
puede haber tantos como
31 días en el mes.

809
00:34:46,850 --> 00:34:52,239
Pero lo que hizo esta persona decide
hacer en caso de una colisión?

810
00:34:52,239 --> 00:34:55,304
Contexto siendo ahora, no un choque de
nombres, pero una colisión de los cumpleaños,

811
00:34:55,304 --> 00:35:00,760
si dos personas tienen la misma fecha de nacimiento en
el 2 de octubre, por ejemplo.

812
00:35:00,760 --> 00:35:02,120
>> ESTUDIANTE: [inaudible].

813
00:35:02,120 --> 00:35:05,010
>> ALTAVOZ 1: Sí, así que aquí tenemos
el aprovechamiento de las listas enlazadas.

814
00:35:05,010 --> 00:35:07,830
Así se ve un poco diferente
que dibujamos antes.

815
00:35:07,830 --> 00:35:10,790
Pero parece que tenemos a un array
en el lado de mano izquierda.

816
00:35:10,790 --> 00:35:13,230
Eso es un índice, por ninguna
en particular la razón.

817
00:35:13,230 --> 00:35:14,630
Pero sigue siendo una matriz.

818
00:35:14,630 --> 00:35:16,160
Es una matriz de punteros.

819
00:35:16,160 --> 00:35:20,670
Y cada uno de esos elementos, cada uno de los
estos círculos o rayas verticales - la raya vertical

820
00:35:20,670 --> 00:35:23,970
representando nula - cada uno de estos
punteros es aparentemente señalando

821
00:35:23,970 --> 00:35:25,730
qué estructura de datos?

822
00:35:25,730 --> 00:35:26,890
Una lista enlazada.

823
00:35:26,890 --> 00:35:30,530
>> Así que ahora tenemos la capacidad de
codificar directamente en nuestro programa

824
00:35:30,530 --> 00:35:32,010
el tamaño de la tabla.

825
00:35:32,010 --> 00:35:35,360
En este caso, sabemos que nunca hay
más de 31 días en un mes.

826
00:35:35,360 --> 00:35:38,480
Tan duro codificando un valor como 31 es
razonable en ese contexto.

827
00:35:38,480 --> 00:35:42,700
En el contexto de los nombres, de codificación duro
26 no es irrazonable, la gente de

828
00:35:42,700 --> 00:35:46,340
sólo nombres comienzan con, por ejemplo,
el alfabeto de la A a la participación de Z.

829
00:35:46,340 --> 00:35:50,180
>> Podemos meter a todos en que los datos
estructura, siempre que, cuando tenemos una

830
00:35:50,180 --> 00:35:55,330
colisión, no ponemos los nombres aquí,
nosotros en cambio pensamos en estas células

831
00:35:55,330 --> 00:36:00,270
no como cadenas de sí mismos, sino como
punteros a, por ejemplo, Alice.

832
00:36:00,270 --> 00:36:03,660
Y entonces Javier puede tener otro puntero
a otro nombre que comience con

833
00:36:03,660 --> 00:36:06,150
A. Y Bob realidad va por aquí.

834
00:36:06,150 --> 00:36:10,850
>> Y si hay otro nombre de partida
con B, termina aquí.

835
00:36:10,850 --> 00:36:15,070
Y así cada uno de los elementos de este
mesa dos, si hemos diseñado este un

836
00:36:15,070 --> 00:36:17,350
poco más inteligentemente -

837
00:36:17,350 --> 00:36:18,125
vamos -

838
00:36:18,125 --> 00:36:22,950
si hemos diseñado este un poco más
inteligentemente, ahora se convierte en un dato de adaptación

839
00:36:22,950 --> 00:36:27,720
estructura, donde no hay límite duro
de la cantidad de elementos que se pueden insertar

840
00:36:27,720 --> 00:36:30,700
en ella, porque si usted tiene
una colisión, eso está bien.

841
00:36:30,700 --> 00:36:34,690
Sólo tienes que ir adelante y añadirlo al
lo que vimos hace poco era

842
00:36:34,690 --> 00:36:38,290
conocida como una lista enlazada.

843
00:36:38,290 --> 00:36:39,690
>> Bueno hagamos una pausa por un momento.

844
00:36:39,690 --> 00:36:42,570
¿Cuál es la probabilidad de una colisión
en el primer lugar?

845
00:36:42,570 --> 00:36:45,480
Bien, tal vez soy más de pensar, tal vez
Yo soy más de la ingeniería de este problema,

846
00:36:45,480 --> 00:36:46,370
porque ¿sabes qué?

847
00:36:46,370 --> 00:36:49,070
Sí, puedo llegar a arbitraria
ejemplos de la parte superior de mi cabeza, como

848
00:36:49,070 --> 00:36:52,870
Allison y Aarón, pero en realidad,
dada una distribución uniforme de

849
00:36:52,870 --> 00:36:56,990
insumos, es decir algunas inserciones aleatorias
en una estructura de datos, lo que realmente es

850
00:36:56,990 --> 00:36:58,580
la probabilidad de una colisión?

851
00:36:58,580 --> 00:37:01,670
Pues resulta que, en realidad es
super alta.

852
00:37:01,670 --> 00:37:03,850
Permítanme generalizar este
problema es como este.

853
00:37:03,850 --> 00:37:08,890
>> Así que en una habitación de estudiantes n CS50, lo que es
la probabilidad de que al menos

854
00:37:08,890 --> 00:37:11,010
dos estudiantes en la sala de
tener la misma fecha de nacimiento?

855
00:37:11,010 --> 00:37:13,346
Así que no hay de qué. algunos Hund -

856
00:37:13,346 --> 00:37:16,790
200, 300 personas aquí y varios
cientos de personas en el país hoy en día.

857
00:37:16,790 --> 00:37:20,670
Así que si quería que nos preguntemos cuál es
la probabilidad de que dos personas

858
00:37:20,670 --> 00:37:23,930
en esta sala que tiene el mismo cumpleaños,
podemos resolver esto.

859
00:37:23,930 --> 00:37:26,250
Y yo pretendo en realidad hay dos
las personas con el mismo cumpleaños.

860
00:37:26,250 --> 00:37:29,560
>> Por ejemplo, ¿alguien
tiene cumpleaños hoy?

861
00:37:29,560 --> 00:37:31,340
Ayer?

862
00:37:31,340 --> 00:37:32,590
¿Mañana?

863
00:37:32,590 --> 00:37:35,980
Muy bien, así que se siente como que voy
a tener que hacer esto 363 o así más

864
00:37:35,980 --> 00:37:39,500
veces a la figura en realidad a cabo
si tenemos una colisión.

865
00:37:39,500 --> 00:37:42,350
O podríamos hacer esto matemáticamente
en lugar de tediosamente

866
00:37:42,350 --> 00:37:43,200
haciendo esto.

867
00:37:43,200 --> 00:37:44,500
Y proponer lo siguiente.

868
00:37:44,500 --> 00:37:48,740
>> Así que propongo que podríamos modelar el
probabilidad de que dos personas tengan el

869
00:37:48,740 --> 00:37:55,320
mismo día que la probabilidad de 1
menos la probabilidad de que nadie que tiene

870
00:37:55,320 --> 00:37:56,290
el mismo cumpleaños.

871
00:37:56,290 --> 00:37:59,960
Así que para conseguir esto, y esto es sólo el
forma elegante de escribir esto, para el

872
00:37:59,960 --> 00:38:03,090
primera persona en la habitación, él o ella
puede tener uno cualquiera de los posibles

873
00:38:03,090 --> 00:38:07,370
cumpleaños asumiendo 365 días en el año,
con perdón de las personas con

874
00:38:07,370 --> 00:38:08,760
el cumpleaños 29 de febrero.

875
00:38:08,760 --> 00:38:13,470
>> Así que la primera persona en esta habitación es gratis
para tener cualquier número de cumpleaños

876
00:38:13,470 --> 00:38:18,280
de las 365 posibilidades para que
que vamos a hacer que 365 dividido por 365,

877
00:38:18,280 --> 00:38:18,990
que es uno.

878
00:38:18,990 --> 00:38:22,700
La siguiente persona en la sala, si el objetivo
es para evitar una colisión, sólo puede

879
00:38:22,700 --> 00:38:26,460
tener su cumpleaños sobre cómo
muchos días diferentes posibles?

880
00:38:26,460 --> 00:38:27,610
364.

881
00:38:27,610 --> 00:38:31,430
Así que el segundo término de esta expresión es
esencialmente haciendo que las matemáticas para nosotros

882
00:38:31,430 --> 00:38:33,460
restando fuera de una posible día.

883
00:38:33,460 --> 00:38:36,390
Y a continuación, el día siguiente, el día siguiente, la
día siguiente hasta el número total

884
00:38:36,390 --> 00:38:38,100
de personas en la habitación.

885
00:38:38,100 --> 00:38:41,290
>> Y si consideramos a continuación, ¿qué es, entonces,
la probabilidad de que no todo el mundo tener

886
00:38:41,290 --> 00:38:45,265
cumpleaños únicos, pero una vez más 1 menos
que, lo que tenemos es una expresión

887
00:38:45,265 --> 00:38:47,810
que puede muy caprichosamente
tener este aspecto.

888
00:38:47,810 --> 00:38:50,330
Pero es más interesante
a ver visualmente.

889
00:38:50,330 --> 00:38:55,120
Este es un gráfico donde en el eje x es
el número de personas en la habitación, el

890
00:38:55,120 --> 00:38:56,180
número de cumpleaños.

891
00:38:56,180 --> 00:38:59,840
En el eje y es la probabilidad
de una colisión, dos personas

892
00:38:59,840 --> 00:39:01,230
que tiene el mismo cumpleaños.

893
00:39:01,230 --> 00:39:05,020
>> Y la comida para llevar de esta curva es
que tan pronto como se llega a gustar 40

894
00:39:05,020 --> 00:39:11,110
estudiantes, que están haciendo en un 90% de probabilidad
combinatorically de dos

895
00:39:11,110 --> 00:39:13,550
personas o más tienen
el mismo cumpleaños.

896
00:39:13,550 --> 00:39:18,600
Y una vez que llegue a gustar 58 personas es
casi el 100% de una ocasión los dos

897
00:39:18,600 --> 00:39:21,310
personas en la habitación se va a tener la
mismo día, a pesar de que no hay

898
00:39:21,310 --> 00:39:26,650
365 o 366 posibles cubetas y
sólo 58 personas en la sala.

899
00:39:26,650 --> 00:39:29,900
Sólo estadísticamente es muy probable que
obtener las colisiones, que en definitiva

900
00:39:29,900 --> 00:39:31,810
motiva esta discusión.

901
00:39:31,810 --> 00:39:35,890
Que incluso si conseguimos extravagancias, y
empezar a tener estas cadenas, todavía estamos

902
00:39:35,890 --> 00:39:36,950
va a tener colisiones.

903
00:39:36,950 --> 00:39:42,710
>> Así que plantea la pregunta, ¿cuál es la
costo de hacer inserciones y deleciones

904
00:39:42,710 --> 00:39:44,850
en una estructura de datos como este?

905
00:39:44,850 --> 00:39:46,630
Pues permítanme proponer -

906
00:39:46,630 --> 00:39:51,570
y déjame volver a la pantalla durante
aquí - si tenemos n elementos en el

907
00:39:51,570 --> 00:39:56,330
lista, por lo que si estamos tratando de insertar
n elementos, y tenemos

908
00:39:56,330 --> 00:39:58,050
cuántos cubos total de?

909
00:39:58,050 --> 00:40:03,450
Digamos 31 cubos en total
en el caso de los cumpleaños.

910
00:40:03,450 --> 00:40:09,240
¿Cuál es la longitud máxima de un
de estas cadenas potencialmente?

911
00:40:09,240 --> 00:40:12,670
>> Si de nuevo hay 31 posibles
cumpleaños en un mes determinado.

912
00:40:12,670 --> 00:40:14,580
Y sólo estamos aglutinación todos -

913
00:40:14,580 --> 00:40:15,580
En realidad eso es un ejemplo tonto.

914
00:40:15,580 --> 00:40:16,960
Vamos a hacer 26 en su lugar.

915
00:40:16,960 --> 00:40:20,890
Así que si realmente tienen las personas cuyos nombres
Comience con una Z a través, lo que da

916
00:40:20,890 --> 00:40:22,780
nos 26 posibilidades.

917
00:40:22,780 --> 00:40:25,920
Y estamos utilizando una estructura de datos como
el que acabamos de ver, por lo que tenemos

918
00:40:25,920 --> 00:40:30,210
una matriz de punteros, cada uno de los cuales
apunta a una lista enlazada donde el

919
00:40:30,210 --> 00:40:32,360
primera lista están todos
con el nombre de Alice.

920
00:40:32,360 --> 00:40:35,770
La segunda lista es cada con el
Nombre que comienza con A, a partir

921
00:40:35,770 --> 00:40:36,980
con B, y así sucesivamente.

922
00:40:36,980 --> 00:40:41,020
>> ¿Cuál es la duración probable de cada una de
esas listas si asumimos un bonito y limpio

923
00:40:41,020 --> 00:40:45,410
distribución de los nombres de la A a la Z
a través de toda la estructura de datos?

924
00:40:45,410 --> 00:40:50,210
Hay n personas en la estructura de datos
dividido por 26, si están bien

925
00:40:50,210 --> 00:40:52,110
repartidas en el conjunto
estructura de datos.

926
00:40:52,110 --> 00:40:54,970
Así la longitud de cada uno de estos
cadenas se n divididos por 26.

927
00:40:54,970 --> 00:40:57,380
Pero en notación O grande, ¿qué es eso?

928
00:40:57,380 --> 00:41:00,100

929
00:41:00,100 --> 00:41:02,440
¿Qué es eso en realidad?

930
00:41:02,440 --> 00:41:04,150
Así que no deja de ser n, ¿verdad?

931
00:41:04,150 --> 00:41:06,620
Debido a que hemos dicho en el pasado,
que Ugh se divide por 26.

932
00:41:06,620 --> 00:41:08,710
Sí, en realidad es más rápido.

933
00:41:08,710 --> 00:41:12,720
Pero en teoría, no es fundamentalmente
todo lo que más rápido.

934
00:41:12,720 --> 00:41:16,040
>> Así que no parece que sea todo lo que mucho
más cerca de este santo grial.

935
00:41:16,040 --> 00:41:17,750
De hecho, esto es sólo el tiempo lineal.

936
00:41:17,750 --> 00:41:20,790
Heck, en este punto, ¿por qué no nos
sólo tiene que utilizar una lista enlazada enorme?

937
00:41:20,790 --> 00:41:23,510
Por qué no nos limitamos a usar una enorme
matriz para almacenar los nombres de los

938
00:41:23,510 --> 00:41:25,010
todos en la sala?

939
00:41:25,010 --> 00:41:28,280
Bueno, ¿hay todavía algo
convincente sobre una tabla hash?

940
00:41:28,280 --> 00:41:30,810
¿Hay todavía algo convincente
sobre una estructura de datos

941
00:41:30,810 --> 00:41:33,940
que se parece a esto?

942
00:41:33,940 --> 00:41:35,182
Este.

943
00:41:35,182 --> 00:41:37,050
>> ESTUDIANTE: [inaudible].

944
00:41:37,050 --> 00:41:39,840
>> ALTAVOZ 1: Correcto, y otra vez si es sólo
un algoritmo de tiempo lineal, y un

945
00:41:39,840 --> 00:41:42,780
estructura de datos de tiempo lineal, ¿por qué no me
simplemente almacenar el nombre de todos en una gran

946
00:41:42,780 --> 00:41:44,210
matriz o en una lista enlazada grande?

947
00:41:44,210 --> 00:41:47,010
Y dejar de hacer CS mucho más difícil
de lo que debe ser?

948
00:41:47,010 --> 00:41:49,600

949
00:41:49,600 --> 00:41:53,190
¿Qué es convincente acerca de esto, incluso
aunque me rasqué la saca?

950
00:41:53,190 --> 00:41:54,930
>> ESTUDIANTE: [inaudible].

951
00:41:54,930 --> 00:41:57,040
>> ALTAVOZ 1: Inserciones no lo son?

952
00:41:57,040 --> 00:41:58,140
Caro ya.

953
00:41:58,140 --> 00:42:03,390
Así inserciones potencialmente podría todavía
ser constante de tiempo, incluso si los datos

954
00:42:03,390 --> 00:42:07,910
estructura se parece a esto, una serie de
punteros, cada uno de ellos está apuntando a

955
00:42:07,910 --> 00:42:09,550
potencialmente una lista enlazada.

956
00:42:09,550 --> 00:42:15,220
¿Cómo puedes lograr constante
tiempo de inserción de los nombres?

957
00:42:15,220 --> 00:42:16,280
Se adhieren en la parte delantera, la derecha?

958
00:42:16,280 --> 00:42:19,290
>> Si sacrificamos un objetivo de diseño de
antes, donde nos queríamos mantener

959
00:42:19,290 --> 00:42:22,650
el nombre de todos, por ejemplo, clasificar,
o la totalidad de los números en el escenario ordenados,

960
00:42:22,650 --> 00:42:25,020
supongamos que tenemos un
lista enlazada sin clasificar.

961
00:42:25,020 --> 00:42:29,960
Sólo nos cuesta uno o dos pasos,
como en el caso de Ben y Brian

962
00:42:29,960 --> 00:42:32,750
anteriormente, para insertar un elemento en
el principio de la lista.

963
00:42:32,750 --> 00:42:36,090
Así que si no nos preocupamos acerca de la ordenación de todo
de los nombres que empiecen con A o la totalidad

964
00:42:36,090 --> 00:42:39,660
los nombres que comienzan con B, que todavía podemos
lograr la inserción de tiempo constante.

965
00:42:39,660 --> 00:42:43,900
Ahora, mirando hacia arriba Alice o Bob o cualquier nombre
más en general sigue siendo qué?

966
00:42:43,900 --> 00:42:48,100
Es grande O de n dividido por 26, en el
caso ideal, donde todo el mundo está uniformemente

967
00:42:48,100 --> 00:42:51,190
distribuida, donde hay tantos doctores
ya que hay Z, que es probablemente

968
00:42:51,190 --> 00:42:52,220
poco realista.

969
00:42:52,220 --> 00:42:53,880
Pero eso sigue siendo lineal.

970
00:42:53,880 --> 00:42:57,120
>> Pero aquí volvemos al punto
ser notación asintótica de

971
00:42:57,120 --> 00:42:58,600
teóricamente cierto.

972
00:42:58,600 --> 00:43:02,960
Pero en el mundo real, si afirmo que
mi programa puede hacer algo 26 veces

973
00:43:02,960 --> 00:43:06,210
más rápido que el tuyo, cuyo programa
vas a preferir el uso de?

974
00:43:06,210 --> 00:43:09,660
La tuya o la mía, que
es 26 veces más rápido?

975
00:43:09,660 --> 00:43:14,320
Siendo realistas, la persona cuyo es 26
veces más rápido, incluso si teóricamente

976
00:43:14,320 --> 00:43:18,790
nuestros algoritmos se ejecutan en el mismo
tiempo de ejecución asintótica.

977
00:43:18,790 --> 00:43:20,940
>> Permítanme proponer un diferente
solución en conjunto.

978
00:43:20,940 --> 00:43:24,380
Y si esto no sopla tu mente,
estamos fuera de las estructuras de datos.

979
00:43:24,380 --> 00:43:27,420
Así que este es un trie -

980
00:43:27,420 --> 00:43:28,520
clase de nombre estúpido.

981
00:43:28,520 --> 00:43:32,880
Viene de recuperaciones, y la palabra
se escribe trie, t-r-i-e, a causa de

982
00:43:32,880 --> 00:43:34,450
recuperación de golf suena como trie.

983
00:43:34,450 --> 00:43:36,580
Pero esa es la historia
de la palabra trie.

984
00:43:36,580 --> 00:43:40,980
>> Así que un trie es de hecho una especie de árbol,
y también es un juego de la palabra.

985
00:43:40,980 --> 00:43:46,330
Y aunque usted no puede verlo del todo
con esta visualización, un trie es un

986
00:43:46,330 --> 00:43:50,790
árbol estructurado, como un árbol de la familia con
un antepasado en la parte superior y un montón

987
00:43:50,790 --> 00:43:54,530
de nietos y bisnietos
como las hojas en la parte inferior.

988
00:43:54,530 --> 00:43:58,100
Pero cada nodo en un trie es una matriz.

989
00:43:58,100 --> 00:44:00,680
Y está en una matriz - y deje de
simplificar demasiado por un momento - es una

990
00:44:00,680 --> 00:44:04,600
matriz, en este caso, de tamaño 26, en donde
cada nodo de nuevo es una matriz de tamaño

991
00:44:04,600 --> 00:44:09,000
26, donde el elemento de orden cero en ese
matriz representa A, y el último

992
00:44:09,000 --> 00:44:11,810
elemento en cada uno de tales
matriz representa Z.

993
00:44:11,810 --> 00:44:15,520
>> Así que propongo, entonces, que estos datos
estructura, conocida como un trie, puede ser

994
00:44:15,520 --> 00:44:17,600
utilizado también para almacenar palabras.

995
00:44:17,600 --> 00:44:21,740
Nos vimos hace un momento cómo podríamos almacenar
palabras, o en este caso, los nombres y nosotros

996
00:44:21,740 --> 00:44:25,440
Vimos anteriormente cómo podemos almacenar números,
pero si nos centramos en los nombres o cadenas

997
00:44:25,440 --> 00:44:27,460
aquí, darse cuenta de lo interesante.

998
00:44:27,460 --> 00:44:32,210
Afirmo que el nombre es Maxwell
en el interior de esta estructura de datos.

999
00:44:32,210 --> 00:44:33,730
¿Dónde ve usted Maxwell?

1000
00:44:33,730 --> 00:44:35,140
>> ESTUDIANTE: [inaudible].

1001
00:44:35,140 --> 00:44:36,240
>> ALTAVOZ 1: A la izquierda.

1002
00:44:36,240 --> 00:44:39,910
Así que lo que es interesante con estos datos
estructura es más bien que tienda la

1003
00:44:39,910 --> 00:44:46,200
cadena M-A-X-W-E-L-L barra invertida cero, todo
contigua, lo que en su lugar lo hace

1004
00:44:46,200 --> 00:44:46,890
está siguiendo.

1005
00:44:46,890 --> 00:44:50,510
Si este es un trie como estructura de datos,
cada uno de cuyos nodos es de nuevo una matriz,

1006
00:44:50,510 --> 00:44:54,650
y desea almacenar Maxwell, primero
índice y así nodo de la raíz, por lo que

1007
00:44:54,650 --> 00:44:57,810
a hablar, el primer nodo,
en la posición M, la derecha, por lo que

1008
00:44:57,810 --> 00:44:59,160
más o menos en el centro.

1009
00:44:59,160 --> 00:45:03,740
Y luego, desde allí, se sigue un
Puntero a una nodos secundarios, por así decirlo.

1010
00:45:03,740 --> 00:45:06,150
Así, en el sentido árbol genealógico,
sigue hacia abajo.

1011
00:45:06,150 --> 00:45:09,030
Y que te llevan a otro nodo
A la izquierda, que es

1012
00:45:09,030 --> 00:45:10,540
sólo otro array.

1013
00:45:10,540 --> 00:45:14,710
>> Y luego, si desea almacenar Maxwell,
usted encuentra el puntero que representa

1014
00:45:14,710 --> 00:45:16,430
A, que es este de aquí.

1015
00:45:16,430 --> 00:45:17,840
Después de ir al siguiente nodo.

1016
00:45:17,840 --> 00:45:20,100
Y note - es por eso la imagen del
un poco engañoso -

1017
00:45:20,100 --> 00:45:21,990
este nodo mirar minúsculo estupendo.

1018
00:45:21,990 --> 00:45:26,050
Pero a la derecha de ésta es Y y Z.
Es que el autor ha truncado la

1019
00:45:26,050 --> 00:45:27,630
foto, así que en realidad
ver las cosas.

1020
00:45:27,630 --> 00:45:30,400
De lo contrario, la imagen
sería enormemente amplia.

1021
00:45:30,400 --> 00:45:36,180
Así que ahora usted índice en la ubicación X, a continuación,
W, A continuación, E, entonces L, entonces L. Entonces cuál es

1022
00:45:36,180 --> 00:45:37,380
esta curiosidad?

1023
00:45:37,380 --> 00:45:41,250
>> Bueno, si estamos utilizando este tipo de nuevo
asumir la forma de almacenar una cadena en un

1024
00:45:41,250 --> 00:45:44,500
estructura de datos, usted todavía tiene que
esencialmente marcar en los datos

1025
00:45:44,500 --> 00:45:47,250
estructura que una palabra termina aquí.

1026
00:45:47,250 --> 00:45:50,830
En otras palabras, cada uno de estos nodos
de alguna manera tiene que recordar que nosotros

1027
00:45:50,830 --> 00:45:53,500
de hecho seguido todos estos punteros
y están dejando un poco

1028
00:45:53,500 --> 00:45:58,370
miga de pan en la parte inferior de esta aquí
estructura para indicar M-A-X-W-E-L-L es

1029
00:45:58,370 --> 00:46:00,230
de hecho, en esta estructura de datos.

1030
00:46:00,230 --> 00:46:02,040
>> Así que podríamos hacerlo de la siguiente.

1031
00:46:02,040 --> 00:46:06,810
Cada uno de los nodos de la imagen que acabamos de
sierra tiene una, una matriz de tamaño 27.

1032
00:46:06,810 --> 00:46:10,550
Y es ahora de 27 años, ya que en p establecido seis,
haremos realidad le damos un apóstrofe,

1033
00:46:10,550 --> 00:46:13,590
para que podamos tener nombres como O'Reilly
y otros con apóstrofes.

1034
00:46:13,590 --> 00:46:14,820
Pero la misma idea.

1035
00:46:14,820 --> 00:46:17,710
Cada uno de esos elementos en el
array apunta a una estructura

1036
00:46:17,710 --> 00:46:19,320
nodo, por lo que sólo un nodo.

1037
00:46:19,320 --> 00:46:21,430
Así que esto es muy reminiscente
de nuestra lista enlazada.

1038
00:46:21,430 --> 00:46:24,550
>> Y luego tengo un booleano, que lo voy a hacer
palabra llamada, que sólo va a ser

1039
00:46:24,550 --> 00:46:29,120
cierto si una palabra termina en este
nodo en el árbol.

1040
00:46:29,120 --> 00:46:32,870
Se representa efectivamente la pequeña
triángulo que vimos hace un momento.

1041
00:46:32,870 --> 00:46:37,190
Así que si una palabra termina en ese nodo en el
árbol, ese campo palabra será verdad,

1042
00:46:37,190 --> 00:46:41,990
que es conceptualmente marcando o
estamos dibujando este triángulo, sí hay

1043
00:46:41,990 --> 00:46:44,080
es una palabra aquí.

1044
00:46:44,080 --> 00:46:45,120
>> Así que este es un trie.

1045
00:46:45,120 --> 00:46:48,540
Y ahora la pregunta es, ¿qué
es su tiempo de ejecución?

1046
00:46:48,540 --> 00:46:49,930
¿Es grande O de n?

1047
00:46:49,930 --> 00:46:51,410
¿Es algo más?

1048
00:46:51,410 --> 00:46:57,330
Bueno, si usted tiene n los nombres de estos datos
estructura, Maxwell es sólo uno de

1049
00:46:57,330 --> 00:47:02,330
ellos, lo que es el tiempo de ejecución de
la inserción o la búsqueda de Maxwell?

1050
00:47:02,330 --> 00:47:06,230

1051
00:47:06,230 --> 00:47:09,050
¿Qué es el tiempo de ejecución
de la inserción de Maxwell?

1052
00:47:09,050 --> 00:47:11,740
Si hay n otros nombres
ya en la mesa?

1053
00:47:11,740 --> 00:47:12,507
¿Sí?

1054
00:47:12,507 --> 00:47:15,429
>> ESTUDIANTE: [inaudible].

1055
00:47:15,429 --> 00:47:17,550
>> ALTAVOZ 1: Sí, es la longitud
del nombre, ¿verdad?

1056
00:47:17,550 --> 00:47:24,420
Así M-a-x-w-e-l-l así que se siente como esto
algoritmo es O grande de siete.

1057
00:47:24,420 --> 00:47:26,580
Ahora, por supuesto, el nombre
variará en longitud.

1058
00:47:26,580 --> 00:47:27,380
Tal vez es un nombre corto.

1059
00:47:27,380 --> 00:47:28,600
Tal vez sea un nombre más largo.

1060
00:47:28,600 --> 00:47:33,390
Pero lo que es clave aquí es que
es un número constante.

1061
00:47:33,390 --> 00:47:36,810
Y tal vez en realidad no es constante,
Pero Dios, si de manera realista, en un

1062
00:47:36,810 --> 00:47:41,570
diccionario, es probable que haya algún límite
en el número de cartas en un

1063
00:47:41,570 --> 00:47:43,820
nombre de la persona en un país determinado.

1064
00:47:43,820 --> 00:47:46,940
>> Y por lo que podemos asumir que
valor es una constante.

1065
00:47:46,940 --> 00:47:47,750
No sé lo que es.

1066
00:47:47,750 --> 00:47:50,440
Es probable que sea más grande que
creemos que es.

1067
00:47:50,440 --> 00:47:52,720
Porque siempre hay algún rincón
Caso con un nombre largo loco.

1068
00:47:52,720 --> 00:47:56,360
Así que vamos a llamarlo k, pero sigue siendo un
constante, presumiblemente, debido a que cada

1069
00:47:56,360 --> 00:48:00,190
nombre en el mundo, al menos en un
país en particular, es que la longitud o

1070
00:48:00,190 --> 00:48:01,780
más corto, por lo que es constante.

1071
00:48:01,780 --> 00:48:04,490
Pero cuando hemos dicho algo es grande
O de un valor constante, lo que hay que

1072
00:48:04,490 --> 00:48:07,760
realmente equivalente a?

1073
00:48:07,760 --> 00:48:10,420
Eso es realmente la misma cosa
diciendo que la constante de tiempo.

1074
00:48:10,420 --> 00:48:11,530
>> Ahora estamos como hacer trampa, ¿no?

1075
00:48:11,530 --> 00:48:15,340
Estamos como el aprovechamiento de alguna teoría
aquí para decir que así, el orden de k es

1076
00:48:15,340 --> 00:48:17,450
Para realmente sólo de uno,
y es hora de constante.

1077
00:48:17,450 --> 00:48:18,200
Pero lo que realmente es.

1078
00:48:18,200 --> 00:48:22,550
Porque la idea clave aquí es que
si tenemos n nombres ya en este

1079
00:48:22,550 --> 00:48:26,010
estructura de datos, y la insertamos Maxwell,
es la cantidad de tiempo que nos lleva a

1080
00:48:26,010 --> 00:48:29,530
inserte Maxwell en absoluto afectada
por la cantidad de otras personas

1081
00:48:29,530 --> 00:48:31,100
se encuentran en la estructura de datos?

1082
00:48:31,100 --> 00:48:31,670
No parece ser.

1083
00:48:31,670 --> 00:48:36,280
Si tuviera un billón más elementos a esta
trie, y luego insertar Maxwell, es

1084
00:48:36,280 --> 00:48:38,650
que en absoluto afectada?

1085
00:48:38,650 --> 00:48:39,050
No.

1086
00:48:39,050 --> 00:48:42,950
Y eso es a diferencia de cualquiera de los datos de días
estructuras que hemos visto hasta ahora, donde

1087
00:48:42,950 --> 00:48:46,820
el tiempo de funcionamiento de su algoritmo es
completamente independiente de la cantidad

1088
00:48:46,820 --> 00:48:51,430
material es o no es ya
en esa estructura de datos.

1089
00:48:51,430 --> 00:48:54,650
>> Y así, con esto le produce ahora es una
oportunidad para p conjunto de seis, que se

1090
00:48:54,650 --> 00:48:58,310
nuevo implicar la implementación de su propia
corrector ortográfico, la lectura en 150.000

1091
00:48:58,310 --> 00:49:01,050
Es decir, la mejor manera de almacenar esa
no es necesariamente evidente.

1092
00:49:01,050 --> 00:49:04,030
Y aunque he aspirado a encontrar
el santo grial, yo no

1093
00:49:04,030 --> 00:49:05,330
afirman que un trie es.

1094
00:49:05,330 --> 00:49:09,810
De hecho, una tabla hash puede muy bien
llegar a ser mucho más eficiente.

1095
00:49:09,810 --> 00:49:10,830
Pero esos son sólo -

1096
00:49:10,830 --> 00:49:14,620
eso es sólo una de las decisiones de diseño
usted tendrá que hacer.

1097
00:49:14,620 --> 00:49:18,920
>> Pero en el cierre vamos a echar 50 o así
segundos para echar un vistazo a lo que las mentiras

1098
00:49:18,920 --> 00:49:22,190
con antelación la próxima semana y más allá de la transición que
de esta línea de comandos

1099
00:49:22,190 --> 00:49:26,220
mundo si los programas en C para cosas web
basado y lenguajes como PHP y

1100
00:49:26,220 --> 00:49:30,350
JavaScript y la propia Internet,
protocolos como HTTP, que tienes

1101
00:49:30,350 --> 00:49:32,870
se da por sentado por años
ahora, y escrito la mayoría de cada

1102
00:49:32,870 --> 00:49:34,440
día, tal vez, o visto.

1103
00:49:34,440 --> 00:49:37,420
Y vamos a empezar a pelar la
capas de lo que es el Internet.

1104
00:49:37,420 --> 00:49:40,650
¿Y cuál es el código que
subyace en las herramientas actuales.

1105
00:49:40,650 --> 00:49:43,230
Así que 50 segundos de este teaser aquí.

1106
00:49:43,230 --> 00:49:46,570
Te doy Guerreros de la red.

1107
00:49:46,570 --> 00:49:51,370
>> [REPRODUCCIÓN DE VÍDEO]

1108
00:49:51,370 --> 00:49:56,764
>> -Él vino con un mensaje.

1109
00:49:56,764 --> 00:50:00,687
Con un protocolo propio.

1110
00:50:00,687 --> 00:50:13,370

1111
00:50:13,370 --> 00:50:19,780
Él vino a un mundo de los servidores de seguridad crueles,
routers indiferentes y peligros lejos

1112
00:50:19,780 --> 00:50:22,600
peor que la muerte.

1113
00:50:22,600 --> 00:50:23,590
Es rápido.

1114
00:50:23,590 --> 00:50:25,300
Es fuerte.

1115
00:50:25,300 --> 00:50:27,700
Es TCPIP.

1116
00:50:27,700 --> 00:50:30,420
Y tiene su dirección.

1117
00:50:30,420 --> 00:50:32,920

1118
00:50:32,920 --> 00:50:34,590
Warriors of the Net.

1119
00:50:34,590 --> 00:50:35,290
>> [VIDEO PLAYBACK FIN]

1120
00:50:35,290 --> 00:50:38,070
>> ALTAVOZ 1: Eso es cómo el Internet
trabajará a partir de la próxima semana.

1121
00:50:38,070 --> 00:50:40,406