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

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

3
00:00:11,137 --> 00:00:12,220
DAVID J. MALAN: Muy bien.

4
00:00:12,220 --> 00:00:13,950
Esto es CS50.

5
00:00:13,950 --> 00:00:18,560
Esta es la quinta semana continuó, y nos
tener algunas buenas noticias y malas noticias.

6
00:00:18,560 --> 00:00:21,140
Así que buena noticia es que CS50
lanza este viernes.

7
00:00:21,140 --> 00:00:24,430
Si usted desea unirse a nosotros,
dirigirse a la dirección URL habitual aquí.

8
00:00:24,430 --> 00:00:28,670
Aún mejor noticia, sin conferencia
el próximo lunes 13.

9
00:00:28,670 --> 00:00:31,970
Algo menos mejores noticias,
cuestionario de cero es el próximo miércoles.

10
00:00:31,970 --> 00:00:33,840
Más detalles pueden ser
encontrado en este URL aquí.

11
00:00:33,840 --> 00:00:36,340
Y en los próximos días
estaremos llenando los espacios en blanco

12
00:00:36,340 --> 00:00:39,234
con respecto a las habitaciones
que habremos reservado.

13
00:00:39,234 --> 00:00:41,400
Mejor noticia es que no voy a
ser un examen de todo el curso

14
00:00:41,400 --> 00:00:43,570
sesión el próximo
Lunes por la noche.

15
00:00:43,570 --> 00:00:46,270
Estén atentos al curso de
sitio web para la ubicación y detalles.

16
00:00:46,270 --> 00:00:49,290
Secciones, a pesar de que es un
día de fiesta, también se reunirá también.

17
00:00:49,290 --> 00:00:50,490

18
00:00:50,490 --> 00:00:52,940
Mejores noticias, conferencia el próximo viernes.

19
00:00:52,940 --> 00:00:56,220
Así que esta es una tradición que
tener, según el plan de estudios.

20
00:00:56,220 --> 00:00:58,100
Solo-- que va a ser increíble.

21
00:00:58,100 --> 00:01:02,510
Usted verá cosas como
estructuras de datos de tiempo constante

22
00:01:02,510 --> 00:01:04,730
y tablas y árboles y tries de patata.

23
00:01:04,730 --> 00:01:07,150
Y vamos a hablar de los problemas de cumpleaños.

24
00:01:07,150 --> 00:01:09,440
Un montón de cosas
espera el próximo viernes.

25
00:01:09,440 --> 00:01:11,212

26
00:01:11,212 --> 00:01:12,200
Okay.

27
00:01:12,200 --> 00:01:13,190
De todos modos.

28
00:01:13,190 --> 00:01:17,080
>> Así recordamos que hemos sido
centrándose en la imagen de lo que está

29
00:01:17,080 --> 00:01:18,980
dentro de la memoria de nuestro ordenador.

30
00:01:18,980 --> 00:01:22,875
Así, la memoria o la memoria RAM es donde los programas
existiendo mientras usted los está corriendo.

31
00:01:22,875 --> 00:01:25,215
Si hace doble clic en un
icono para ejecutar algún programa

32
00:01:25,215 --> 00:01:27,520
o haga doble clic en un
icono para abrir algún archivo,

33
00:01:27,520 --> 00:01:30,430
está cargada de su disco
conducir o unidad de estado sólido

34
00:01:30,430 --> 00:01:34,190
en la memoria RAM, memoria de acceso aleatorio, donde
vive hasta que se desconecte la alimentación,

35
00:01:34,190 --> 00:01:36,700
la tapa del portátil se cierra,
o salir del programa.

36
00:01:36,700 --> 00:01:38,960
>> Ahora que la memoria, de
que es probable que tenga

37
00:01:38,960 --> 00:01:41,950
1 gigabyte estos días, 2
gigabytes, o incluso mucho más,

38
00:01:41,950 --> 00:01:44,420
generalmente se presenta
para un programa dado

39
00:01:44,420 --> 00:01:47,170
en este tipo de rectangular
modelo conceptual

40
00:01:47,170 --> 00:01:50,860
con lo cual tenemos la pila en la parte inferior
y un montón de otras cosas en la parte superior.

41
00:01:50,860 --> 00:01:53,140
La cosa en la parte superior
que hemos visto en esta imagen

42
00:01:53,140 --> 00:01:55,670
antes, pero nunca se habla
es el llamado segmento de texto.

43
00:01:55,670 --> 00:01:58,419
Segmento de texto es sólo una forma elegante
de decir los ceros y unos que

44
00:01:58,419 --> 00:02:01,150
componer su programa compilado real.

45
00:02:01,150 --> 00:02:03,910
>> Así que al hacer doble clic
Microsoft Word en su Mac o PC,

46
00:02:03,910 --> 00:02:08,030
o cuando se ejecuta punto slash Mario en un
Ordenador con Linux en la ventana de terminal,

47
00:02:08,030 --> 00:02:12,460
los ceros y unos que componen
Word o Mario se almacenan temporalmente

48
00:02:12,460 --> 00:02:16,610
en la memoria RAM de su computadora en el llamado
segmento de texto para un programa en particular.

49
00:02:16,610 --> 00:02:19,080
Debajo de eso va inicializado
y datos sin inicializar.

50
00:02:19,080 --> 00:02:22,655
Esto es algo similar a las variables globales,
que nosotros no hemos usado muchos de,

51
00:02:22,655 --> 00:02:24,910
pero en ocasiones nos hemos
tenido variables globales

52
00:02:24,910 --> 00:02:28,819
o estáticamente cuerdas definido que
está codificado palabras como "hola"

53
00:02:28,819 --> 00:02:31,860
que no son tomadas en el usuario desde
que están codificados duro en su programa.

54
00:02:31,860 --> 00:02:34,230
>> Ahora, abajo en la parte inferior que
tener la llamada pila.

55
00:02:34,230 --> 00:02:37,665
Y la pila, hasta ahora, hemos estado
utilizando para qué tipo de propósitos?

56
00:02:37,665 --> 00:02:39,706

57
00:02:39,706 --> 00:02:40,997
Lo que la pila se utiliza?

58
00:02:40,997 --> 00:02:41,160
¿Sí?

59
00:02:41,160 --> 00:02:42,070
>> AUDIENCIA: Funciones.

60
00:02:42,070 --> 00:02:43,320
>> DAVID J. MALAN: Para las funciones?

61
00:02:43,320 --> 00:02:44,980
¿En qué sentido para las funciones?

62
00:02:44,980 --> 00:02:48,660
>> AUDIENCIA: Cuando se llama a una función, el
argumentos se copian en la pila.

63
00:02:48,660 --> 00:02:49,660
>> DAVID J. MALAN: Exactamente.

64
00:02:49,660 --> 00:02:52,650
Cuando se llama a una función, su
argumentos se copian en la pila.

65
00:02:52,650 --> 00:02:56,330
Así que cualquier X o Y o A o B de la
que está pasando en una función

66
00:02:56,330 --> 00:02:58,680
están temporalmente poner en
la llamada pila,

67
00:02:58,680 --> 00:03:02,000
al igual que uno de los Annenberg
bandejas de comedor, y también cosas

68
00:03:02,000 --> 00:03:03,190
como variables locales.

69
00:03:03,190 --> 00:03:06,290
Si su función foo o su canje
función tiene variables locales,

70
00:03:06,290 --> 00:03:08,602
como la temperatura, los dos
terminan en la pila.

71
00:03:08,602 --> 00:03:11,560
Ahora, no vamos a hablar demasiado sobre
ellos, pero estas variables de entorno

72
00:03:11,560 --> 00:03:15,690
en la parte inferior que vimos hace un tiempo cuando
Me pelearse en el teclado un día

73
00:03:15,690 --> 00:03:20,050
y empecé a acceder a las cosas
como argv argv 100 o 1000,

74
00:03:20,050 --> 00:03:22,320
sólo elements-- olvido
la numbers-- pero eso

75
00:03:22,320 --> 00:03:24,330
no se supone que es visitada por mí.

76
00:03:24,330 --> 00:03:26,581
Empezamos a ver algunas
símbolos de funky en la pantalla.

77
00:03:26,581 --> 00:03:28,330
Esos eran los llamados
variables de entorno

78
00:03:28,330 --> 00:03:32,390
como ajustes globales para mi
programa o para mi equipo, no

79
00:03:32,390 --> 00:03:37,090
no relacionado con la reciente
error que hemos discutido,

80
00:03:37,090 --> 00:03:39,670
Shellshock, que ha sido
que azota a un buen número de ordenadores.

81
00:03:39,670 --> 00:03:42,960
>> Ahora, por último, en el enfoque de hoy
vamos a ser en última instancia, en el montón.

82
00:03:42,960 --> 00:03:44,864
Esta es otra parte de la memoria.

83
00:03:44,864 --> 00:03:47,030
Y fundamentalmente todo esto
la memoria es la misma materia.

84
00:03:47,030 --> 00:03:48,040
Es el mismo hardware.

85
00:03:48,040 --> 00:03:49,956
Somos sólo una especie de
el tratamiento de diferentes grupos

86
00:03:49,956 --> 00:03:51,460
de bytes para diferentes propósitos.

87
00:03:51,460 --> 00:03:56,540
El montón también va a estar donde
variables y memoria que usted solicite

88
00:03:56,540 --> 00:03:58,810
desde el sistema operativo
se almacena temporalmente.

89
00:03:58,810 --> 00:04:01,890
>> Pero hay una especie de problema
Aquí, como la imagen implica.

90
00:04:01,890 --> 00:04:05,261
Tenemos suerte de tener dos
barcos a punto de chocar.

91
00:04:05,261 --> 00:04:08,010
Porque como se utiliza cada vez más
de la pila, y como lo vemos hoy en día

92
00:04:08,010 --> 00:04:11,800
adelante, y cuando se utiliza cada vez más de la
montón, seguramente las cosas malas pueden suceder.

93
00:04:11,800 --> 00:04:15,054
Y, de hecho, podemos inducir que
con o sin intención.

94
00:04:15,054 --> 00:04:16,970
Así que el drama de suspenso última
tiempo era este programa,

95
00:04:16,970 --> 00:04:20,570
que no servirá cualquier funcional
propósito que no sea para demostrar

96
00:04:20,570 --> 00:04:24,750
cómo usted como un tipo malo en realidad puede tomar
ventaja de los errores en el programa de alguien

97
00:04:24,750 --> 00:04:28,460
y hacerse cargo de un programa o incluso un
sistema informático totalidad o servidor.

98
00:04:28,460 --> 00:04:31,660
Así que a simple vista brevemente, que
notar que la principal en la parte inferior

99
00:04:31,660 --> 00:04:34,510
toma en la línea de comandos
argumentos, como por argv.

100
00:04:34,510 --> 00:04:38,480
Y tiene una llamada a una función f,
esencialmente una función sin nombre llama

101
00:04:38,480 --> 00:04:40,250
f, y está pasando en argv [1].

102
00:04:40,250 --> 00:04:43,960
>> Así que cualquier palabra que el usuario escribe en al
el símbolo detrás del nombre de este programa,

103
00:04:43,960 --> 00:04:49,310
y luego esta función arbitraria hasta
superior, f, lleva en una cadena, conocido como char *,

104
00:04:49,310 --> 00:04:51,720
como hemos empezado a discutir,
y que sólo lo llama "bar".

105
00:04:51,720 --> 00:04:53,310
Pero podríamos llamarlo nada.

106
00:04:53,310 --> 00:04:57,470
Y entonces se declara, en el interior
de f, un conjunto de caracteres

107
00:04:57,470 --> 00:04:59,930
llamado c-- 12 de estos personajes.

108
00:04:59,930 --> 00:05:03,580
>> Ahora, por la historia que estaba contando
Hace un momento, cuando en la memoria

109
00:05:03,580 --> 00:05:06,720
es c, o son los 12
CHARS va a terminar?

110
00:05:06,720 --> 00:05:07,570
Para que quede claro.

111
00:05:07,570 --> 00:05:08,070
¿Sí?

112
00:05:08,070 --> 00:05:08,590
>> AUDIENCIA: En la pila.

113
00:05:08,590 --> 00:05:09,420
>> DAVID J. MALAN: En la pila.

114
00:05:09,420 --> 00:05:10,720
Así que c es una variable local.

115
00:05:10,720 --> 00:05:14,079
Estamos pidiendo 12 caracteres o 12 bytes.

116
00:05:14,079 --> 00:05:16,120
Esos van a terminar
en la llamada pila.

117
00:05:16,120 --> 00:05:18,530
Ahora, finalmente, es esta otra función
eso es realmente muy útil,

118
00:05:18,530 --> 00:05:20,571
pero nosotros no hemos usado realmente
nosotros mismos, strncopy.

119
00:05:20,571 --> 00:05:21,550

120
00:05:21,550 --> 00:05:25,200
Esto significa copia de cadena, pero
sólo n letras, n caracteres.

121
00:05:25,200 --> 00:05:31,990
Así n caracteres serán
copiado de bar en c.

122
00:05:31,990 --> 00:05:32,980
Y ¿cuántos?

123
00:05:32,980 --> 00:05:34,110
La longitud de la barra.

124
00:05:34,110 --> 00:05:36,330
Así, en otras palabras, que
una línea, strncopy,

125
00:05:36,330 --> 00:05:39,500
va a copiar
prohibir de manera efectiva en al c.

126
00:05:39,500 --> 00:05:42,340
>> Ahora, sólo para tipo de anticipar
la moraleja de esta historia,

127
00:05:42,340 --> 00:05:44,750
lo que es potencialmente problemática aquí?

128
00:05:44,750 --> 00:05:49,710
A pesar de que estamos comprobando la longitud
del bar y de pasarlo en strncopy,

129
00:05:49,710 --> 00:05:53,145
¿Cuál es su intestino diciendo es
todavía roto sobre este programa?

130
00:05:53,145 --> 00:05:54,410

131
00:05:54,410 --> 00:05:55,220
¿Sí?

132
00:05:55,220 --> 00:05:57,491
>> AUDIENCIA: No incluye
espacio para el carácter nulo.

133
00:05:57,491 --> 00:05:59,990
DAVID J. MALAN: No incluye
espacio para el carácter nulo.

134
00:05:59,990 --> 00:06:02,073
Potencialmente, a diferencia de
práctica del pasado que ni siquiera

135
00:06:02,073 --> 00:06:04,810
tener tanto como un plus del 1 al
acomodar ese carácter nulo.

136
00:06:04,810 --> 00:06:06,649
Pero es aún peor que eso.

137
00:06:06,649 --> 00:06:07,940
¿Qué más estamos fallando a hacer?

138
00:06:07,940 --> 00:06:08,432
¿Sí?

139
00:06:08,432 --> 00:06:09,307
>> AUDIENCIA: [inaudible]

140
00:06:09,307 --> 00:06:15,440

141
00:06:15,440 --> 00:06:16,440
DAVID J. MALAN: Perfect.

142
00:06:16,440 --> 00:06:18,490
Duro Hemos codificamos 12 bastante arbitraria.

143
00:06:18,490 --> 00:06:19,497

144
00:06:19,497 --> 00:06:21,330
Eso no es tanto la
problema, pero el hecho de

145
00:06:21,330 --> 00:06:25,630
que ni siquiera estamos comprobando si
la longitud de la barra es de menos de 12,

146
00:06:25,630 --> 00:06:28,530
en cuyo caso va a ser
seguro para ponerlo en la memoria

147
00:06:28,530 --> 00:06:30,260
llamado c que hemos asignado.

148
00:06:30,260 --> 00:06:32,960
En efecto, si la barra es como
20 caracteres de largo,

149
00:06:32,960 --> 00:06:39,010
esta función parece estar copiando
20 personajes de bar en c, por lo tanto

150
00:06:39,010 --> 00:06:41,310
teniendo al menos 8 bytes
que no debe ser.

151
00:06:41,310 --> 00:06:42,690
Esa es la implicación aquí.

152
00:06:42,690 --> 00:06:44,347
>> Así que en breve programa, roto.

153
00:06:44,347 --> 00:06:45,180
No como una gran cosa.

154
00:06:45,180 --> 00:06:46,360
Tal vez usted consigue un error de segmentación.

155
00:06:46,360 --> 00:06:47,651
Todos hemos tenido errores en los programas.

156
00:06:47,651 --> 00:06:50,196
Todos nosotros podríamos tener errores
en los programas en estos momentos.

157
00:06:50,196 --> 00:06:51,320
Pero ¿cuál es la implicación?

158
00:06:51,320 --> 00:06:54,390
Bueno, aquí está una versión ampliada en de
que la imagen de la memoria de mi ordenador.

159
00:06:54,390 --> 00:06:56,230
Este es el fondo de mi stack.

160
00:06:56,230 --> 00:06:59,644
Y, en efecto, en la parte inferior es lo que hay
llamada pila rutina padre, forma elegante

161
00:06:59,644 --> 00:07:00,560
de decir que es principal.

162
00:07:00,560 --> 00:07:03,772
Así que todo el que llama a la función
f que estamos hablando.

163
00:07:03,772 --> 00:07:05,230
Así que esta es la parte inferior de la pila.

164
00:07:05,230 --> 00:07:06,640
Dirección de retorno es algo nuevo.

165
00:07:06,640 --> 00:07:08,810
Siempre ha estado ahí,
siempre ha sido en esa foto.

166
00:07:08,810 --> 00:07:10,440
Nosotros nunca llamamos la atención sobre él.

167
00:07:10,440 --> 00:07:15,290
Porque resulta que la forma c funciona es
que cuando una función llama a otra,

168
00:07:15,290 --> 00:07:18,780
no sólo los argumentos que
función get inserta en la pila,

169
00:07:18,780 --> 00:07:22,470
no sólo hacer local de la función
variables de quedarse relegados en la pila,

170
00:07:22,470 --> 00:07:26,820
algo que se llama una dirección de retorno
También consigue poner en la pila.

171
00:07:26,820 --> 00:07:33,330
En concreto, si las llamadas principales Foo, principales
propia dirección en la memoria, el buey algo,

172
00:07:33,330 --> 00:07:38,240
efectivamente consigue poner en la pila
de modo que cuando f se hace ejecutarlo

173
00:07:38,240 --> 00:07:43,630
sabe dónde para saltar de nuevo a en el texto
segmento con el fin de continuar con la ejecución.

174
00:07:43,630 --> 00:07:47,760
>> Así que si estamos aquí conceptualmente,
en principal, entonces f es llamado.

175
00:07:47,760 --> 00:07:50,200
¿Cómo se sabe que f
al control de la mano de vuelta?

176
00:07:50,200 --> 00:07:52,020
Bueno, este pequeño
miga de pan en rojo aquí,

177
00:07:52,020 --> 00:07:54,978
llamado el remite, sólo
cheques, lo que es que la dirección del remitente?

178
00:07:54,978 --> 00:07:57,039
Oh, déjame saltar de nuevo al principal aquí.

179
00:07:57,039 --> 00:07:59,080
Y eso es un poco
de una simplificación excesiva,

180
00:07:59,080 --> 00:08:00,750
porque los ceros y unos
por principales son técnicamente

181
00:08:00,750 --> 00:08:01,967
aquí en el segmento de tecnología.

182
00:08:01,967 --> 00:08:03,800
Pero esa es la idea. f
sólo tiene que saber lo que

183
00:08:03,800 --> 00:08:06,680
a donde el control en última instancia se remonta.

184
00:08:06,680 --> 00:08:09,790
>> Pero la forma en ordenadores
han sentado durante mucho tiempo fuera cosas

185
00:08:09,790 --> 00:08:12,320
como las variables locales y
argumentos es así.

186
00:08:12,320 --> 00:08:17,180
Así que en la parte superior de esta imagen en
azul es el marco de pila de f, por lo que todo

187
00:08:17,180 --> 00:08:19,630
de la memoria que f
específicamente está utilizando.

188
00:08:19,630 --> 00:08:22,990
Así que en consecuencia, observe que
bar está en esta foto.

189
00:08:22,990 --> 00:08:23,980
Bar era su argumento.

190
00:08:23,980 --> 00:08:27,240
Y reclamamos que los argumentos a
funciones quedarse relegados en la pila.

191
00:08:27,240 --> 00:08:29,910
Y C, por supuesto, es
También en esta imagen.

192
00:08:29,910 --> 00:08:33,520
>> Y sólo para propósitos de notación,
cuenta en la esquina superior izquierda

193
00:08:33,520 --> 00:08:37,020
es lo que se c soporte 0 y
a continuación, un poco hacia la derecha

194
00:08:37,020 --> 00:08:38,220
c es el soporte 11.

195
00:08:38,220 --> 00:08:41,240
En otras palabras, se puede imaginar
que hay una rejilla de bytes

196
00:08:41,240 --> 00:08:44,380
allí, primero de los cuales es
arriba a la izquierda, parte inferior de las cuales

197
00:08:44,380 --> 00:08:48,360
es el último de esos 12 bytes.

198
00:08:48,360 --> 00:08:49,930
>> Pero ahora tratar de avanzar rápidamente.

199
00:08:49,930 --> 00:08:55,580
¿Qué va a ocurrir si pasamos
en un bar de cadena que es más de c?

200
00:08:55,580 --> 00:08:59,130
Y no estamos comprobando si
es de hecho más de 12.

201
00:08:59,130 --> 00:09:03,146
¿Qué parte de esta imagen va a
conseguir sobreescrito por bytes 0, 1, 2, 3,

202
00:09:03,146 --> 00:09:07,890
dot dot dot, 11, y luego
malo, 12, 13 a través de 19?

203
00:09:07,890 --> 00:09:11,820
¿Qué va a pasar aquí,
si usted deducir del ordenamiento

204
00:09:11,820 --> 00:09:14,790
que c abrazadera 0 está en la parte superior
y c abrazadera 11 es una especie de abajo

205
00:09:14,790 --> 00:09:15,812
a la derecha?

206
00:09:15,812 --> 00:09:16,796
¿Sí?

207
00:09:16,796 --> 00:09:19,260
>> AUDIENCIA: Bueno, va
sobrescribir el bar char *.

208
00:09:19,260 --> 00:09:22,260
>> DAVID J. MALAN: Sí, parece que
usted va a sobrescribir char * bar.

209
00:09:22,260 --> 00:09:26,245
Y peor aún, si usted envía en un tiempo muy largo
cadena, que incluso podría sobrescribir qué?

210
00:09:26,245 --> 00:09:27,460

211
00:09:27,460 --> 00:09:28,570
La dirección de retorno.

212
00:09:28,570 --> 00:09:31,380
Que a su vez, es igual que un
ruta de navegación para decirle al programa donde

213
00:09:31,380 --> 00:09:34,060
para ir de nuevo a cuando f
se hace la que llama.

214
00:09:34,060 --> 00:09:37,140
>> Entonces, ¿qué chicos malos suelen hacer
es si se encuentran con un programa

215
00:09:37,140 --> 00:09:41,290
que son curiosos si es
explotable, con errores de forma

216
00:09:41,290 --> 00:09:43,550
que él o ella puede tomar
ventaja de ese error,

217
00:09:43,550 --> 00:09:45,720
generalmente no reciben
esta bien la primera vez.

218
00:09:45,720 --> 00:09:48,590
Sólo empezar a enviar, por ejemplo,
cadenas aleatorias en su programa,

219
00:09:48,590 --> 00:09:50,260
ya sea en el teclado,
o francamente que probablemente

220
00:09:50,260 --> 00:09:52,740
escribir un pequeño programa que acaba de
generan automáticamente las cadenas,

221
00:09:52,740 --> 00:09:55,430
y empezar a golpear en su programa
el envío de gran cantidad de diferentes insumos

222
00:09:55,430 --> 00:09:56,340
en diferentes longitudes.

223
00:09:56,340 --> 00:09:58,990
>> Tan pronto como sus errores en el programa,
eso es una cosa increíble.

224
00:09:58,990 --> 00:10:01,020
Debido a que significa que él
o que ha descubierto

225
00:10:01,020 --> 00:10:02,660
lo que probablemente es de hecho un error.

226
00:10:02,660 --> 00:10:05,830
Y entonces pueden conseguir más inteligente
y empezar a centrarse más estrechamente

227
00:10:05,830 --> 00:10:07,420
sobre la forma de explotar ese error.

228
00:10:07,420 --> 00:10:11,480
En particular, lo que él o ella podría
hacer es enviar, en el mejor de los casos, hola.

229
00:10:11,480 --> 00:10:12,210
No es gran cosa.

230
00:10:12,210 --> 00:10:14,750
Es una cadena que es suficientemente corto.

231
00:10:14,750 --> 00:10:18,100
Pero ¿y si él o ella envía,
y vamos a generalizar como,

232
00:10:18,100 --> 00:10:20,890
ataque code-- tan ceros
y los que hacen las cosas

233
00:10:20,890 --> 00:10:25,150
como rm-rf, que quitar todo
desde el disco duro o enviar spam

234
00:10:25,150 --> 00:10:27,000
o atacar de alguna manera la máquina?

235
00:10:27,000 --> 00:10:29,570
>> Así que si cada uno de estos
letras A sólo representa,

236
00:10:29,570 --> 00:10:32,380
conceptualmente, ataque, ataque,
ataque, ataque, algunas malas código

237
00:10:32,380 --> 00:10:36,410
que alguien más escribió, pero
si esa persona es lo suficientemente inteligente

238
00:10:36,410 --> 00:10:40,790
no sólo para incluir toda
de esos rm-RFS, sino también

239
00:10:40,790 --> 00:10:46,100
tener sus últimos bytes
ser un número que corresponde

240
00:10:46,100 --> 00:10:50,540
a la dirección de su
o su propio código de ataque

241
00:10:50,540 --> 00:10:53,820
que él o ella pasó en apenas
proporcionando en el prompt,

242
00:10:53,820 --> 00:10:58,760
se puede engañar a la computadora con eficacia
en darse cuenta cuando f se realiza la ejecución,

243
00:10:58,760 --> 00:11:02,400
oh, es el momento para que salte
de nuevo a la dirección de retorno rojo.

244
00:11:02,400 --> 00:11:06,070
Pero debido a que él o ella tiene de alguna manera
superpuestas que remite

245
00:11:06,070 --> 00:11:09,602
con su propio número,
y son lo suficientemente inteligentes

246
00:11:09,602 --> 00:11:11,560
haber configurado que
número de referencia, ya que

247
00:11:11,560 --> 00:11:13,740
ver en el top estupendo
esquina izquierda hay,

248
00:11:13,740 --> 00:11:18,020
la dirección real en el ordenador de
memoria de algunos de su código de ataque,

249
00:11:18,020 --> 00:11:21,740
un chico malo puede engañar a la computadora
en la ejecución de su propio código.

250
00:11:21,740 --> 00:11:23,700
>> Y ese código, de nuevo, puede ser cualquier cosa.

251
00:11:23,700 --> 00:11:26,120
Generalmente, se llama
código shell, que es justo

252
00:11:26,120 --> 00:11:29,030
una forma de decir que no es
generalmente algo tan simple como rm-rf.

253
00:11:29,030 --> 00:11:32,340
En realidad es algo así como Bash,
o un programa que le da

254
00:11:32,340 --> 00:11:37,230
o su control de programación para ejecutar
cualquier otra cosa que ellos quieren.

255
00:11:37,230 --> 00:11:40,210
Así que en resumen, todo esto
deriva del simple hecho de

256
00:11:40,210 --> 00:11:44,490
que este error en cuestión no comprobación
los límites de la matriz.

257
00:11:44,490 --> 00:11:47,250
Y debido a la forma en
equipos de trabajo es que

258
00:11:47,250 --> 00:11:49,430
utilizar la pila de
efectivamente, conceptualmente,

259
00:11:49,430 --> 00:11:54,830
parte inferior hacia arriba, pero luego los elementos
usted empuja en la pila crezca arriba hacia abajo,

260
00:11:54,830 --> 00:11:56,624
esto es muy problemático.

261
00:11:56,624 --> 00:11:58,290
Ahora, hay maneras de evitar este.

262
00:11:58,290 --> 00:12:00,800
Y, francamente, hay lenguas
con el que trabajar alrededor de esto.

263
00:12:00,800 --> 00:12:03,100
Java es inmune, por ejemplo,
a este tema en particular.

264
00:12:03,100 --> 00:12:04,110
Porque ellos no te dan consejos.

265
00:12:04,110 --> 00:12:05,943
Ellos no te dan
direcciones de memoria directa.

266
00:12:05,943 --> 00:12:08,560
Así que con este poder que tenemos
tocar nada en la memoria

267
00:12:08,560 --> 00:12:11,580
queremos que viene, sin duda, un gran riesgo.

268
00:12:11,580 --> 00:12:12,430
>> Así que mantener un ojo hacia fuera.

269
00:12:12,430 --> 00:12:14,596
Si, francamente, en los meses de
o años por venir, en cualquier momento

270
00:12:14,596 --> 00:12:17,740
usted lea acerca de cierto tipo de explotación
de un programa o un servidor,

271
00:12:17,740 --> 00:12:22,370
si usted ve un atisbo de algo
como un ataque de desbordamiento de búfer,

272
00:12:22,370 --> 00:12:25,390
o desbordamiento de pila es otro tipo
de ataque, similar en espíritu,

273
00:12:25,390 --> 00:12:28,770
tanto como inspira el sitio web de
nombrar, si lo conoce,

274
00:12:28,770 --> 00:12:33,170
todo está hablando sólo de
rebosar el tamaño de algunos de carácter

275
00:12:33,170 --> 00:12:36,200
matriz o alguna variedad más general.

276
00:12:36,200 --> 00:12:38,822
Cualquier pregunta, entonces, sobre esto?

277
00:12:38,822 --> 00:12:39,780
No intente hacer esto en casa.

278
00:12:39,780 --> 00:12:41,620

279
00:12:41,620 --> 00:12:42,300
>> Bien.

280
00:12:42,300 --> 00:12:47,270
Así malloc hasta ahora ha sido nuestro nuevo
amigo en que podemos asignar memoria

281
00:12:47,270 --> 00:12:50,540
que no sabemos necesariamente en
adelantamos que queremos lo que no tenemos

282
00:12:50,540 --> 00:12:52,920
a codificar en nuestra
números de programas como 12.

283
00:12:52,920 --> 00:12:55,550
Una vez que el usuario nos dice cuánto
datos que él o ella quiere de entrada,

284
00:12:55,550 --> 00:12:58,000
podemos malloc que gran parte de la memoria.

285
00:12:58,000 --> 00:13:01,484
>> Así malloc resulta, a la
medida en que hemos estado usando,

286
00:13:01,484 --> 00:13:03,900
explícitamente la última vez, y luego
ustedes han estado usando

287
00:13:03,900 --> 00:13:08,160
getString para saberlo para
varias semanas, todos los de la memoria de malloc

288
00:13:08,160 --> 00:13:09,820
proviene de la llamada pila.

289
00:13:09,820 --> 00:13:13,852
Y es por eso getString, por ejemplo,
puede asignar memoria dinámicamente

290
00:13:13,852 --> 00:13:16,060
sin saber lo que eres
va a escribir de antemano,

291
00:13:16,060 --> 00:13:21,520
que devolver un puntero a la memoria,
y que la memoria sigue siendo tuyo para siempre,

292
00:13:21,520 --> 00:13:24,080
incluso después GetString rendimientos.

293
00:13:24,080 --> 00:13:27,450
Porque recuerdo después de todo lo que el
pila está constantemente subiendo y bajando,

294
00:13:27,450 --> 00:13:27,950
arriba y abajo.

295
00:13:27,950 --> 00:13:30,230
Y tan pronto como va
abajo, eso significa que cualquier memoria

296
00:13:30,230 --> 00:13:33,030
esta función utilizada debe
No ser utilizado por ninguna otra persona.

297
00:13:33,030 --> 00:13:34,570
Es valores de basura ahora.

298
00:13:34,570 --> 00:13:36,120
>> Pero el montón está aquí arriba.

299
00:13:36,120 --> 00:13:39,360
Y lo que es bueno de malloc es que
cuando malloc asigna memoria hasta aquí,

300
00:13:39,360 --> 00:13:42,070
no está afectada, para la
mayor parte, por la pila.

301
00:13:42,070 --> 00:13:46,000
Y por lo que cualquier función puede acceder
memoria que se ha malloc'd,

302
00:13:46,000 --> 00:13:49,120
incluso por una función como getString,
incluso después de que se devuelve.

303
00:13:49,120 --> 00:13:51,700
>> Ahora, lo contrario de malloc es gratis.

304
00:13:51,700 --> 00:13:53,900
Y, en efecto, la regla que
que tenga que empezar a adoptar

305
00:13:53,900 --> 00:13:58,950
es cualquier, cualquier, cualquier momento usted utiliza malloc
debe usted utilizar libre, con el tiempo,

306
00:13:58,950 --> 00:14:00,280
en ese mismo puntero.

307
00:14:00,280 --> 00:14:03,289
Durante todo este tiempo hemos estado escribiendo
con errores, código erróneo, por muchas razones.

308
00:14:03,289 --> 00:14:05,580
Pero uno de los cuales ha sido
utilizando la biblioteca de CS50, que

309
00:14:05,580 --> 00:14:09,010
sí es deliberadamente
con errores, se pierde memoria.

310
00:14:09,010 --> 00:14:11,410
Cada vez que usted ha llamado getString
durante las últimas semanas

311
00:14:11,410 --> 00:14:13,870
estamos haciendo la operación
sistema, Linux, para la memoria.

312
00:14:13,870 --> 00:14:15,780
Y usted nunca una vez dado por ti.

313
00:14:15,780 --> 00:14:17,730
Y esto no es, en
practicar, una buena cosa.

314
00:14:17,730 --> 00:14:20,330
>> Y Valgrind, uno de los
herramientas introducidas en el juego de parámetros 4,

315
00:14:20,330 --> 00:14:22,900
se trata de ayudar usted
ahora encontrar errores como ese.

316
00:14:22,900 --> 00:14:27,060
Pero por suerte para Pset 4 no es necesario
utilizar la biblioteca CS50 o getString.

317
00:14:27,060 --> 00:14:31,220
Así que cualquier error relacionados con la memoria son
en última instancia, va a ser la suya.

318
00:14:31,220 --> 00:14:34,060
>> Así malloc es algo más que
conveniente para este propósito.

319
00:14:34,060 --> 00:14:37,420
En realidad, ahora podemos resolver
fundamentalmente diferentes problemas,

320
00:14:37,420 --> 00:14:41,640
y resolver fundamentalmente los problemas más
eficazmente como por la promesa de la semana cero.

321
00:14:41,640 --> 00:14:44,720
Hasta el momento esta es la más sexy
estructura de datos que hemos tenido.

322
00:14:44,720 --> 00:14:47,804
Y por la estructura de los datos que acabo de decir
una forma de memoria conceptualizar

323
00:14:47,804 --> 00:14:50,720
de una manera que va más allá de sólo decir,
este es un int, este es un char.

324
00:14:50,720 --> 00:14:52,930
Podemos empezar junto a las cosas de racimo.

325
00:14:52,930 --> 00:14:54,460
>> Así que una matriz se veía así.

326
00:14:54,460 --> 00:14:57,270
Y lo que fue clave en aproximadamente una
array es que te da

327
00:14:57,270 --> 00:14:59,724
back-to-back trozos de
memoria, cada uno de los cuales

328
00:14:59,724 --> 00:15:02,765
va a ser del mismo tipo, int,
int, int, int o char, char, char,

329
00:15:02,765 --> 00:15:03,330
Char.

330
00:15:03,330 --> 00:15:04,496
Pero hay algunas desventajas.

331
00:15:04,496 --> 00:15:06,570
Esto por ejemplo, es
una matriz de tamaño seis.

332
00:15:06,570 --> 00:15:10,650
Supongamos que usted llene esta matriz con seis
números y luego, por las razones que sean,

333
00:15:10,650 --> 00:15:13,187
el usuario quiere dar
que un séptimo número.

334
00:15:13,187 --> 00:15:14,020
¿Dónde lo pusiste?

335
00:15:14,020 --> 00:15:15,490

336
00:15:15,490 --> 00:15:18,990
>> ¿Cuál es la solución si usted tiene
creado una matriz en la pila,

337
00:15:18,990 --> 00:15:22,030
por ejemplo, sólo con la semana
dos notación que hemos introducido,

338
00:15:22,030 --> 00:15:23,730
de corchetes con un número en su interior?

339
00:15:23,730 --> 00:15:25,160

340
00:15:25,160 --> 00:15:27,260
Bueno, usted tiene seis
los números en estas cajas.

341
00:15:27,260 --> 00:15:28,530
¿Cuáles serían sus instintos?

342
00:15:28,530 --> 00:15:29,973
¿Dónde te gustaría ponerlo?

343
00:15:29,973 --> 00:15:30,860
>> AUDIENCIA: [inaudible]

344
00:15:30,860 --> 00:15:31,315
>> DAVID J. MALAN: Lo siento?

345
00:15:31,315 --> 00:15:32,380
>> AUDIENCIA: Ponlo en el final.

346
00:15:32,380 --> 00:15:33,796
>> DAVID J. MALAN: Ponlo en el extremo.

347
00:15:33,796 --> 00:15:35,880
Así que un poco más a la derecha,
fuera de esta caja de texto.

348
00:15:35,880 --> 00:15:38,710
¿Qué estaría bien, pero
resulta que no puede hacer eso.

349
00:15:38,710 --> 00:15:41,350
Porque si no lo has pedido
para esta parte de la memoria,

350
00:15:41,350 --> 00:15:44,490
podría ser por casualidad que esta
está siendo utilizado por alguna otra variable

351
00:15:44,490 --> 00:15:45,030
por completo.

352
00:15:45,030 --> 00:15:49,210
Piense de nuevo una semana o así que cuando nos acostamos
los nombres Zamyla y Davin y Gabe de

353
00:15:49,210 --> 00:15:49,930
en la memoria.

354
00:15:49,930 --> 00:15:51,638
Eran, literalmente,
espalda con espalda con espalda.

355
00:15:51,638 --> 00:15:53,550
Así que no podemos necesariamente
confiar en que cualesquiera de

356
00:15:53,550 --> 00:15:55,800
aquí está disponible para que yo use.

357
00:15:55,800 --> 00:15:56,990
>> Entonces, ¿qué otra cosa podría hacer?

358
00:15:56,990 --> 00:16:00,282
Bueno, una vez que darse cuenta de que
necesitará una matriz de tamaño siete,

359
00:16:00,282 --> 00:16:02,490
usted podría crear un
matriz de tamaño siete después utilice

360
00:16:02,490 --> 00:16:05,950
un bucle for o un bucle while,
copiarlo en la nueva matriz,

361
00:16:05,950 --> 00:16:09,680
y entonces de alguna manera simplemente deshacerse de
esta matriz o simplemente deje de usarlo.

362
00:16:09,680 --> 00:16:12,130
Pero eso no es particularmente eficiente.

363
00:16:12,130 --> 00:16:15,340
En resumen, las matrices no dejan
cambiar el tamaño de forma dinámica.

364
00:16:15,340 --> 00:16:17,900
>> Así que por un lado se obtiene
acceso aleatorio, que es increíble.

365
00:16:17,900 --> 00:16:20,108
Debido a que nos permite hacer cosas
como divide y vencerás,

366
00:16:20,108 --> 00:16:23,100
búsqueda binaria, todo lo cual hemos
hablado en la pantalla aquí.

367
00:16:23,100 --> 00:16:24,950
Pero se pinta a sí mismo en una esquina.

368
00:16:24,950 --> 00:16:27,810
Tan pronto como se golpeó
Al final de su matriz,

369
00:16:27,810 --> 00:16:29,980
usted tiene que hacer un muy
operación costosa

370
00:16:29,980 --> 00:16:33,910
o escribir un montón de código
que lidiar ahora con ese problema.

371
00:16:33,910 --> 00:16:36,680
>> ¿Y qué si su lugar, teníamos
algo que se llama una lista,

372
00:16:36,680 --> 00:16:38,820
o una lista vinculada en particular?

373
00:16:38,820 --> 00:16:41,930
¿Qué pasa si en lugar de tener
rectángulos espalda con espalda con espalda,

374
00:16:41,930 --> 00:16:45,730
tenemos rectángulos que dejan un poco
poco de margen de maniobra en medio de ellos?

375
00:16:45,730 --> 00:16:49,670
Y a pesar de que he dibujado este
foto o adaptado esta foto

376
00:16:49,670 --> 00:16:54,696
de uno de los textos aquí para estar de nuevo a
espalda con espalda muy ordenada, en la realidad,

377
00:16:54,696 --> 00:16:56,820
uno de esos rectángulos
podría ser de hasta aquí en la memoria.

378
00:16:56,820 --> 00:16:58,028
Uno de ellos podría estar aquí.

379
00:16:58,028 --> 00:17:00,420
Uno de ellos podría estar aquí arriba,
aquí, y así sucesivamente.

380
00:17:00,420 --> 00:17:02,910
>> Pero lo que si dibujamos,
en este caso, las flechas

381
00:17:02,910 --> 00:17:05,650
que de alguna manera vincularlos
rectángulos juntos?

382
00:17:05,650 --> 00:17:08,170
De hecho, hemos visto una técnica
encarnación de una flecha.

383
00:17:08,170 --> 00:17:09,839

384
00:17:09,839 --> 00:17:13,710
¿Qué hemos utilizado en los últimos
día que, debajo de la campana,

385
00:17:13,710 --> 00:17:15,210
es representativa de una flecha?

386
00:17:15,210 --> 00:17:16,290

387
00:17:16,290 --> 00:17:17,349
Un puntero, ¿verdad?

388
00:17:17,349 --> 00:17:19,780
>> ¿Y qué si, en lugar de
almacenar sólo los números,

389
00:17:19,780 --> 00:17:23,130
como 9, 17, 22, 26, 34,
¿y si no almacenamos

390
00:17:23,130 --> 00:17:27,079
sólo un número, pero un puntero
junto a cada uno de tales número?

391
00:17:27,079 --> 00:17:30,690
Así que al igual que se enhebrar una
aguja a través de un manojo entero de la tela,

392
00:17:30,690 --> 00:17:32,950
cosas de alguna forma de vinculación
juntos, de manera similar puede

393
00:17:32,950 --> 00:17:35,550
que con los punteros, como
encarnado por flechas aquí,

394
00:17:35,550 --> 00:17:38,550
tipo de tejer
estos rectángulos individuales

395
00:17:38,550 --> 00:17:41,780
por la utilización eficaz de un puntero
uno al lado del número que

396
00:17:41,780 --> 00:17:46,065
apunta a algunos siguiente número, que
señala, a su vez, algunos siguiente número?

397
00:17:46,065 --> 00:17:47,940
Así que en otras palabras, lo que
si en realidad queríamos

398
00:17:47,940 --> 00:17:49,820
para implementar algo como esto?

399
00:17:49,820 --> 00:17:53,610
Bien por desgracia, estos rectángulos,
al menos el uno con 9, 17, 22,

400
00:17:53,610 --> 00:17:57,040
y así sucesivamente, estos ya no son
bonitas plazas con números individuales.

401
00:17:57,040 --> 00:17:59,960
La parte inferior, rectángulo
por debajo de 9, por ejemplo,

402
00:17:59,960 --> 00:18:04,330
representa lo que debe
ser un puntero, 32 bits.

403
00:18:04,330 --> 00:18:09,460
Ahora, todavía no estoy al tanto de cualquier tipo de datos
en C que le da no sólo un int

404
00:18:09,460 --> 00:18:11,630
pero un puntero por completo.

405
00:18:11,630 --> 00:18:15,020
>> Entonces, ¿cuál es la solución si queremos
inventar nuestra propia respuesta a esto?

406
00:18:15,020 --> 00:18:15,760
¿Sí?

407
00:18:15,760 --> 00:18:16,640
>> AUDIENCIA: [inaudible]

408
00:18:16,640 --> 00:18:17,360
>> DAVID J. MALAN: ¿Qué es eso?

409
00:18:17,360 --> 00:18:17,880
>> AUDIENCIA: Nueva estructura.

410
00:18:17,880 --> 00:18:19,590
>> DAVID J. MALAN: Sí, ¿y por qué
Por qué no creamos una nueva estructura,

411
00:18:19,590 --> 00:18:20,920
o en C, una estructura?

412
00:18:20,920 --> 00:18:25,990
Hemos visto estructuras antes, aunque brevemente,
donde nos topamos con una estructura estudiante

413
00:18:25,990 --> 00:18:27,780
como éste, que tenía un nombre y una casa.

414
00:18:27,780 --> 00:18:31,980
En Pset 3 breakout usted utiliza en su conjunto
manojo de GRect structs-- y GOvals

415
00:18:31,980 --> 00:18:34,810
que Stanford creado para
información de clúster juntos.

416
00:18:34,810 --> 00:18:38,580
¿Y qué si tomamos esta misma idea de
las palabras clave "typedef" y "struct"

417
00:18:38,580 --> 00:18:42,890
y luego un poco de materia específica del estudiante,
y evolucionar esto en lo siguiente:

418
00:18:42,890 --> 00:18:46,210
typedef struct node-- y nodo es
sólo una ciencia de la computación muy genérico

419
00:18:46,210 --> 00:18:49,980
plazo para algo en una estructura de datos,
un contenedor en una estructura de datos.

420
00:18:49,980 --> 00:18:53,900
Un nodo reclamo va a tener
un int n, totalmente sencillo,

421
00:18:53,900 --> 00:18:58,810
y luego un poco más críptica,
esta segunda línea, el nodo struct * siguiente.

422
00:18:58,810 --> 00:19:01,300
Pero en términos menos técnicos,
lo que es que la segunda línea

423
00:19:01,300 --> 00:19:02,980
de código dentro de las llaves?

424
00:19:02,980 --> 00:19:03,737
¿Sí?

425
00:19:03,737 --> 00:19:04,851
>> AUDIENCIA: [inaudible]

426
00:19:04,851 --> 00:19:06,600
DAVID J. MALAN: Un
puntero a otro nodo.

427
00:19:06,600 --> 00:19:09,910
Así que sin duda, la sintaxis un poco críptico.

428
00:19:09,910 --> 00:19:13,250
Pero si usted lee literalmente,
siguiente es el nombre de una variable.

429
00:19:13,250 --> 00:19:14,410
¿Cuál es su tipo de datos?

430
00:19:14,410 --> 00:19:18,206
Es un poco verboso este momento,
pero es de tipo struct nodo *.

431
00:19:18,206 --> 00:19:22,960
Cada vez que hemos visto algo de la estrella, que
significa que es un puntero a ese tipo de datos.

432
00:19:22,960 --> 00:19:26,810
Así que la próxima es al parecer un
puntero a un nodo de estructura.

433
00:19:26,810 --> 00:19:28,310
>> Ahora, ¿qué es un nodo de estructura?

434
00:19:28,310 --> 00:19:31,044
Bueno, observa que vea los
mismas palabras en la parte superior derecha.

435
00:19:31,044 --> 00:19:33,960
Y, en efecto, se ve también la palabra
"Nodo" aquí abajo en la parte inferior izquierda.

436
00:19:33,960 --> 00:19:35,640
Y esto es en realidad sólo una conveniencia.

437
00:19:35,640 --> 00:19:39,930
Tenga en cuenta que en nuestra definición estudiante
ahí está la palabra "estudiante" sólo una vez.

438
00:19:39,930 --> 00:19:42,510
Y es que un estudiante
objeto no era auto-referencial.

439
00:19:42,510 --> 00:19:45,340
No hay nada en el interior de un estudiante
que tiene que apuntar a otro estudiante,

440
00:19:45,340 --> 00:19:45,610
persay.

441
00:19:45,610 --> 00:19:47,630
Eso sería una especie de
raro en el mundo real.

442
00:19:47,630 --> 00:19:50,880
>> Pero con un nodo en una ligado
lista, sí queremos un nodo

443
00:19:50,880 --> 00:19:53,970
ser referencial a un objeto similar.

444
00:19:53,970 --> 00:19:57,900
Y así cuenta del cambio aquí no es
sólo lo que está dentro de las llaves.

445
00:19:57,900 --> 00:20:00,800
Pero añadimos la palabra "nodo"
en la parte superior, así como

446
00:20:00,800 --> 00:20:02,930
de añadir a la parte inferior
en lugar de "estudiante".

447
00:20:02,930 --> 00:20:06,000
Y esto es sólo un detalle técnico
de modo que, de nuevo, la estructura de datos

448
00:20:06,000 --> 00:20:11,380
puede ser auto-referencial, por lo que un
nodo puede apuntar a otra tal nodo.

449
00:20:11,380 --> 00:20:13,840
>> Entonces, ¿qué es esta última instancia
va a significar para nosotros?

450
00:20:13,840 --> 00:20:17,560
Bueno, uno, esto dentro
es el contenido de nuestro nodo.

451
00:20:17,560 --> 00:20:19,360
Esta cosa aquí,
arriba a la derecha, es tan

452
00:20:19,360 --> 00:20:20,860
que, de nuevo, podemos referirnos a nosotros mismos.

453
00:20:20,860 --> 00:20:23,401
Y luego las cosas más externa,
a pesar de que el nodo es un nuevo término,

454
00:20:23,401 --> 00:20:25,500
tal vez, que sigue siendo el
mismo que los estudiantes y lo que

455
00:20:25,500 --> 00:20:27,520
estaba debajo de la capucha en SPL.

456
00:20:27,520 --> 00:20:31,095
>> Así que si ahora queríamos empezar
la aplicación de esta lista enlazada,

457
00:20:31,095 --> 00:20:33,220
¿cómo podríamos traducir
algo como esto para codificar?

458
00:20:33,220 --> 00:20:35,350
Bueno, vamos a ver un
ejemplo de un programa que

459
00:20:35,350 --> 00:20:36,840
en realidad utiliza una lista enlazada.

460
00:20:36,840 --> 00:20:40,870
Entre código de distribución de hoy
es un programa que se llama Lista Cero.

461
00:20:40,870 --> 00:20:44,980
Y si me quedo esta creé un super
GUI simple, interfaz gráfica de usuario,

462
00:20:44,980 --> 00:20:46,460
pero no deja de ser printf.

463
00:20:46,460 --> 00:20:50,930
Y ahora yo mismo he dado unos cuantos menú
options-- Eliminar, Insertar, Buscar,

464
00:20:50,930 --> 00:20:51,750
y Traverse.

465
00:20:51,750 --> 00:20:52,630
Y en Salir.

466
00:20:52,630 --> 00:20:55,970
Estas son operaciones comunes en un solo
estructura de datos conocida como una lista de enlaces.

467
00:20:55,970 --> 00:20:58,409
>> Ahora, Eliminar va a
eliminar un número de la lista.

468
00:20:58,409 --> 00:21:00,200
Inserte va a añadir
un número a la lista.

469
00:21:00,200 --> 00:21:02,181
La búsqueda se va a ver
de número en la lista.

470
00:21:02,181 --> 00:21:04,930
Y travesía es sólo una forma elegante
de decir, caminar a través de la lista,

471
00:21:04,930 --> 00:21:06,245
imprimirlo, pero eso es todo.

472
00:21:06,245 --> 00:21:07,720
No cambie de ninguna manera.

473
00:21:07,720 --> 00:21:08,570
>> Así que vamos a probar esto.

474
00:21:08,570 --> 00:21:10,160
Vamos a seguir adelante y tipo 2.

475
00:21:10,160 --> 00:21:12,710
Y luego voy a
insertar el número, por ejemplo 9.

476
00:21:12,710 --> 00:21:13,620
Intro.

477
00:21:13,620 --> 00:21:17,480
Y ahora mi programa es sólo
programada decir, la lista es ahora 9.

478
00:21:17,480 --> 00:21:20,190
Ahora, si me voy por delante y
no Inserte de nuevo, dejar que

479
00:21:20,190 --> 00:21:23,680
me voy por delante y alejar y escribo en 17.

480
00:21:23,680 --> 00:21:25,770
Ahora mi lista es 9, entonces de 17 años.

481
00:21:25,770 --> 00:21:27,750
Si lo hago inserte de nuevo, vamos a saltar uno.

482
00:21:27,750 --> 00:21:32,400
En lugar de 22, de acuerdo con la imagen que hemos
estado viendo aquí, déjame ir por delante

483
00:21:32,400 --> 00:21:34,630
e inserte el 26 próximo.

484
00:21:34,630 --> 00:21:36,230
Así que voy a escribir 26.

485
00:21:36,230 --> 00:21:37,755
La lista es la que espero.

486
00:21:37,755 --> 00:21:40,630
Pero ahora, sólo para ver si el código
va a ser flexible, dejadme que ahora

487
00:21:40,630 --> 00:21:43,520
tipo 22, que al menos
conceptualmente, si estamos

488
00:21:43,520 --> 00:21:46,520
Teniendo esto ordenadas, que es de hecho
va a ser otro de los objetivos en este momento,

489
00:21:46,520 --> 00:21:48,690
debe ir en entre el 17 y el 26.

490
00:21:48,690 --> 00:21:50,270
Así que pulsé Enter.

491
00:21:50,270 --> 00:21:51,380
De hecho, eso funciona.

492
00:21:51,380 --> 00:21:54,950
Y ahora permítanme insertar el
pasado, por la imagen, 34.

493
00:21:54,950 --> 00:21:55,450
>> Bien.

494
00:21:55,450 --> 00:21:58,980
Así que por ahora déjame estipulo que
Borrar y Traverse y Search hacen,

495
00:21:58,980 --> 00:21:59,760
de hecho, trabajar.

496
00:21:59,760 --> 00:22:04,180
De hecho, si yo corro búsqueda, vamos a
buscar el número 22, Enter.

497
00:22:04,180 --> 00:22:05,010
Se encontraron 22.

498
00:22:05,010 --> 00:22:07,580
Así que eso es lo que esta
programa de lista Zero hace.

499
00:22:07,580 --> 00:22:10,230
>> Pero lo que realmente está pasando
en que implementa esto?

500
00:22:10,230 --> 00:22:14,530
Bueno, primero voy a tener, y de hecho
Yo tengo, un archivo llamado list0.h.

501
00:22:14,530 --> 00:22:16,540

502
00:22:16,540 --> 00:22:20,690
Y en algún lugar existe este
línea, typedef, struct nodo,

503
00:22:20,690 --> 00:22:24,850
entonces tengo mis llaves, int n, y
entonces struct-- cuál es la definición?

504
00:22:24,850 --> 00:22:26,530

505
00:22:26,530 --> 00:22:28,545
Struct nodo siguiente.

506
00:22:28,545 --> 00:22:29,920

507
00:22:29,920 --> 00:22:31,045
Así que tenemos la estrella.

508
00:22:31,045 --> 00:22:33,420
Ahora técnicamente nos metemos en
el hábito de dibujar aquí.

509
00:22:33,420 --> 00:22:35,670
Es posible que vea los libros de texto y
referencias en línea lo hacen allí.

510
00:22:35,670 --> 00:22:36,660
Es funcionalmente equivalente.

511
00:22:36,660 --> 00:22:37,980
De hecho, este es un poco más típico.

512
00:22:37,980 --> 00:22:40,563
Pero voy a ser coherente con lo que
que hicimos la última vez y hacemos esto.

513
00:22:40,563 --> 00:22:42,350
Y luego, por último, voy a hacer esto.

514
00:22:42,350 --> 00:22:45,550
>> Así que en un archivo de cabecera
en algún lugar, en list0.h

515
00:22:45,550 --> 00:22:49,200
hoy es esta definición struct,
y tal vez algunas otras cosas.

516
00:22:49,200 --> 00:22:52,580
Mientras tanto, en list0c hay
va a ser un par de cosas.

517
00:22:52,580 --> 00:22:54,740
Pero vamos a simplemente
iniciar y no terminar esto.

518
00:22:54,740 --> 00:22:59,690
List0.h es un archivo que quiero
incluir en mi archivo C.

519
00:22:59,690 --> 00:23:03,910
Y luego, en algún momento me estoy
va a tener int, principal, anulará.

520
00:23:03,910 --> 00:23:06,530
Y luego voy a
tienen algunas cosas por hacer está aquí.

521
00:23:06,530 --> 00:23:10,620
Yo también voy a tener una
prototipo, como vacío, búsqueda, int,

522
00:23:10,620 --> 00:23:13,610
n, cuyo propósito en la vida es
para buscar un elemento.

523
00:23:13,610 --> 00:23:18,310
Y entonces aquí yo reclamo en
el código de hoy, nula búsqueda, int, n,

524
00:23:18,310 --> 00:23:21,020
hay punto y coma, pero las llaves abiertas.

525
00:23:21,020 --> 00:23:25,049
Y ahora quiero buscar alguna manera
un elemento en esta lista.

526
00:23:25,049 --> 00:23:27,340
Pero nosotros no tenemos suficiente
información en la pantalla todavía.

527
00:23:27,340 --> 00:23:29,800
No tengo en realidad
representada la propia lista.

528
00:23:29,800 --> 00:23:33,070
Así que una manera que podríamos aplicar
una lista enlazada en un programa

529
00:23:33,070 --> 00:23:37,520
está como que quiero hacer algo
como declaran lista enlazada aquí.

530
00:23:37,520 --> 00:23:40,520
Para simplificar, voy a hacer
este mundial, a pesar de que en general, nos

531
00:23:40,520 --> 00:23:41,645
No debería hacer esto demasiado.

532
00:23:41,645 --> 00:23:43,260
Pero va a simplificar este ejemplo.

533
00:23:43,260 --> 00:23:45,890
Así que quiero declarar
una lista enlazada aquí.

534
00:23:45,890 --> 00:23:47,010
Ahora, ¿cómo podría yo hacer eso?

535
00:23:47,010 --> 00:23:48,810

536
00:23:48,810 --> 00:23:50,750
>> Aquí está la foto de una lista enlazada.

537
00:23:50,750 --> 00:23:53,030
Y realmente no me
conocer al momento cómo

538
00:23:53,030 --> 00:23:56,710
Voy a ir sobre lo que representa
tantas cosas con un solo

539
00:23:56,710 --> 00:23:58,040
variable en la memoria.

540
00:23:58,040 --> 00:23:59,160
Pero pensar de nuevo un momento.

541
00:23:59,160 --> 00:24:00,830
Durante todo este tiempo que hemos tenido
cuerdas, que luego

542
00:24:00,830 --> 00:24:02,913
revelado a ser matrices de
personajes, que luego

543
00:24:02,913 --> 00:24:05,740
revelado a ser sólo un puntero
hasta el primer carácter

544
00:24:05,740 --> 00:24:08,890
en una matriz de caracteres
eso está terminada en nulo.

545
00:24:08,890 --> 00:24:13,530
Así que por esa lógica, y con este
foto tipo de sembrar sus pensamientos,

546
00:24:13,530 --> 00:24:17,964
lo que necesitamos realmente escribimos en nuestra
código para representar una lista enlazada?

547
00:24:17,964 --> 00:24:21,130
¿Qué parte de esta información necesitamos
capturar en código C, qué le dirías?

548
00:24:21,130 --> 00:24:22,654

549
00:24:22,654 --> 00:24:23,154
¿Sí?

550
00:24:23,154 --> 00:24:24,738
>> AUDIENCIA: Necesitamos un puntero a un nodo.

551
00:24:24,738 --> 00:24:26,237
DAVID J. MALAN: Un puntero a un nodo.

552
00:24:26,237 --> 00:24:29,320
En particular, lo que haría con su nodo
instintos ser mantener un puntero?

553
00:24:29,320 --> 00:24:30,026
>> AUDIENCIA: El primer nodo.

554
00:24:30,026 --> 00:24:31,942
>> DAVID J. MALAN: Sí,
probablemente sólo la primera.

555
00:24:31,942 --> 00:24:34,030
Y note, la primera
nodo es una forma diferente.

556
00:24:34,030 --> 00:24:37,690
Es sólo la mitad del tamaño de la estructura,
porque es de hecho sólo un puntero.

557
00:24:37,690 --> 00:24:44,650
Así que lo que realmente puede hacer es declarar
una lista enlazada sea de nodo de tipo *.

558
00:24:44,650 --> 00:24:47,780
Y vamos a llamarlo primero
y inicializarlo a null.

559
00:24:47,780 --> 00:24:49,910
Así nula, de nuevo, es procedente
en la imagen aquí.

560
00:24:49,910 --> 00:24:53,620
No sólo se utiliza null como como un especial
valor de retorno para cosas como getString

561
00:24:53,620 --> 00:24:57,770
y malloc, null es también el cero
puntero, la falta de un puntero,

562
00:24:57,770 --> 00:24:58,430
si se quiere.

563
00:24:58,430 --> 00:25:00,309
Sólo significa que aún no hay nada aquí.

564
00:25:00,309 --> 00:25:02,100
Ahora en primer lugar, que hubiera podido
llamado a este nada.

565
00:25:02,100 --> 00:25:04,200
Yo podría haber llamado "lista"
o cualquier número de otras cosas.

566
00:25:04,200 --> 00:25:06,960
Pero yo estoy llamando "primero" para que
líneas arriba con esta imagen.

567
00:25:06,960 --> 00:25:10,280
Así que al igual que una cadena se puede representar
con la dirección de su primer byte,

568
00:25:10,280 --> 00:25:11,280
por lo que puede una lista enlazada.

569
00:25:11,280 --> 00:25:13,480
Y veremos otros datos
pueden representar estructuras

570
00:25:13,480 --> 00:25:16,700
con sólo un puntero,
una flecha de 32 bits, señalando

571
00:25:16,700 --> 00:25:18,740
en el primer nodo de la estructura.

572
00:25:18,740 --> 00:25:20,340
>> Pero ahora vamos a anticipar un problema.

573
00:25:20,340 --> 00:25:23,230
Si yo sólo estoy recordando
en mi programa de la dirección

574
00:25:23,230 --> 00:25:27,220
del primer nodo, la primera
rectángulo en esta estructura de datos,

575
00:25:27,220 --> 00:25:31,760
lo que tenía ser mejor el caso sobre el
ejecución del resto de mi lista?

576
00:25:31,760 --> 00:25:35,820
¿Qué es un detalle clave que está pasando
para asegurar que esto funciona en realidad?

577
00:25:35,820 --> 00:25:39,250
Y por "realmente funciona" I
decir, como un string,

578
00:25:39,250 --> 00:25:42,180
nos deja ir desde el primer carácter
en el nombre de Davin a la segunda,

579
00:25:42,180 --> 00:25:44,755
a la tercera, a la
cuarto, hasta el final,

580
00:25:44,755 --> 00:25:47,880
¿Cómo sabemos cuando estamos al final
de una lista enlazada que tiene este aspecto?

581
00:25:47,880 --> 00:25:50,035

582
00:25:50,035 --> 00:25:50,660
Cuando es nulo.

583
00:25:50,660 --> 00:25:53,640
Y yo he representado este tipo de como
como una fuerza ingeniero eléctrico,

584
00:25:53,640 --> 00:25:56,420
con la poca tierra
símbolo, de todo tipo.

585
00:25:56,420 --> 00:25:58,246
Pero eso sólo significa nula en este caso.

586
00:25:58,246 --> 00:26:00,370
Usted puede dibujar cualquier número
maneras, pero este autor

587
00:26:00,370 --> 00:26:02,800
pasado a utilizar este símbolo aquí.

588
00:26:02,800 --> 00:26:06,260
>> Mientras estamos encadenando
todos estos nodos entre sí,

589
00:26:06,260 --> 00:26:08,600
sólo recordar dónde
la primera es, siempre

590
00:26:08,600 --> 00:26:11,760
como ponemos un símbolo especial en
el último nodo de la lista,

591
00:26:11,760 --> 00:26:15,130
y usaremos nulo, porque eso es
lo que tenemos a nuestra disposición,

592
00:26:15,130 --> 00:26:16,480
esta lista es completa.

593
00:26:16,480 --> 00:26:20,190
Y aunque yo sólo le dan un puntero a
el primer elemento, usted, el programador,

594
00:26:20,190 --> 00:26:22,486
sin duda puede acceder al resto de la misma.

595
00:26:22,486 --> 00:26:24,360
Pero vamos a dejar que sus mentes
pasear un poco,

596
00:26:24,360 --> 00:26:26,140
si no lo son ya
bastante wandered-- lo que es

597
00:26:26,140 --> 00:26:28,723
va a ser el tiempo de ejecución de
encontrar nada en esta lista?

598
00:26:28,723 --> 00:26:30,450

599
00:26:30,450 --> 00:26:33,470
Maldita sea, es grande O de n,
lo cual no es malo, para ser justos.

600
00:26:33,470 --> 00:26:34,800
Pero es lineal.

601
00:26:34,800 --> 00:26:37,980
Hemos renunciado a lo que característica
de arrays moviendo más

602
00:26:37,980 --> 00:26:43,130
hacia la imagen de forma dinámica
entrelazados o nodos vinculados?

603
00:26:43,130 --> 00:26:44,970

604
00:26:44,970 --> 00:26:46,687
Hemos renunciado acceso aleatorio.

605
00:26:46,687 --> 00:26:48,770
Una matriz es agradable porque
todo matemáticamente

606
00:26:48,770 --> 00:26:50,340
ha vuelto a la espalda con espalda con espalda.

607
00:26:50,340 --> 00:26:52,370
A pesar de que esta foto
se ve bastante, e incluso

608
00:26:52,370 --> 00:26:55,830
aunque parece que estos nodos
están bien separados, en realidad

609
00:26:55,830 --> 00:26:56,830
podrían estar en cualquier parte.

610
00:26:56,830 --> 00:27:01,590
Ox1, OX50, Ox123, Ox99, éstos
nodos podrían estar en cualquier parte.

611
00:27:01,590 --> 00:27:05,960
Debido a malloc hace asignar memoria
del montón, pero en cualquier lugar en el montón.

612
00:27:05,960 --> 00:27:09,080
Usted no necesariamente sabe que es
va a estar espalda con espalda con espalda.

613
00:27:09,080 --> 00:27:12,460
Y así esta foto en la realidad de
No va a ser bastante esta bonita.

614
00:27:12,460 --> 00:27:16,140
>> Así que va a tomar un poco de
trabajar para implementar esta función.

615
00:27:16,140 --> 00:27:17,880
Así que vamos a poner en práctica la búsqueda ahora.

616
00:27:17,880 --> 00:27:20,250
Y vamos a ver una especie de
forma inteligente de hacerlo.

617
00:27:20,250 --> 00:27:24,660
Así que si yo soy una función de búsqueda y
Me dan una variable, entero n

618
00:27:24,660 --> 00:27:28,490
a buscar, necesito saber la
nueva sintaxis para mirar dentro

619
00:27:28,490 --> 00:27:32,400
de una estructura que es
señalado, para encontrar n.

620
00:27:32,400 --> 00:27:33,210
Así que vamos a hacer esto.

621
00:27:33,210 --> 00:27:36,030
>> Así que primero voy a ir
adelante y declarar un nodo *.

622
00:27:36,030 --> 00:27:39,400
Y yo voy a llamarlo
puntero, sólo por convención.

623
00:27:39,400 --> 00:27:41,710
Y yo voy a inicializarlo a primera.

624
00:27:41,710 --> 00:27:43,770
Y ahora que puedo hacer esto
en un número de maneras.

625
00:27:43,770 --> 00:27:45,436
Pero me voy a tomar un enfoque común.

626
00:27:45,436 --> 00:27:50,180
Mientras puntero no es igual a
nula, y eso es una sintaxis válida.

627
00:27:50,180 --> 00:27:54,550
Y sólo significa hacer lo siguiente, por lo que
siempre y cuando usted no está apuntando a la nada.

628
00:27:54,550 --> 00:27:55,800
¿Qué quiero hacer?

629
00:27:55,800 --> 00:28:01,939
>> Si dot puntero n, dejarme volver
para que, equals-- igual qué?

630
00:28:01,939 --> 00:28:03,105
¿Qué valor que estoy buscando?

631
00:28:03,105 --> 00:28:04,920

632
00:28:04,920 --> 00:28:06,590
El n real que se pasó.

633
00:28:06,590 --> 00:28:09,020
Así que aquí está otra de las características
de C y muchos idiomas.

634
00:28:09,020 --> 00:28:13,705
A pesar de que el nodo de estructura llamada
tiene un valor de n, totalmente legítimo

635
00:28:13,705 --> 00:28:17,530
tener también un argumento locales
o variable llamada n.

636
00:28:17,530 --> 00:28:20,085
Porque nosotros también, con
los ojos humanos, pueden distinguir

637
00:28:20,085 --> 00:28:22,087
que este n es presumiblemente
diferente de este n.

638
00:28:22,087 --> 00:28:23,420
Debido a que la sintaxis es diferente.

639
00:28:23,420 --> 00:28:26,211
Tienes un punto y un puntero,
mientras que éste no tiene tal cosa.

640
00:28:26,211 --> 00:28:27,290
Así que esto está bien.

641
00:28:27,290 --> 00:28:29,120
Eso está bien llamarlos las mismas cosas.

642
00:28:29,120 --> 00:28:32,380
>> Si yo te encuentro esto, estoy
va a querer hacer algo

643
00:28:32,380 --> 00:28:35,000
como anunciamos que nos encontramos n.

644
00:28:35,000 --> 00:28:37,930
Y eso se lo dejamos como
comentar o código pseudocódigo.

645
00:28:37,930 --> 00:28:40,190
Si no, y aquí está la
Lo interesante, lo que

646
00:28:40,190 --> 00:28:47,320
hago lo que quiero hacer si el nodo actual
no se contiene n que me importa?

647
00:28:47,320 --> 00:28:50,700
¿Cómo puedo lograr lo siguiente?

648
00:28:50,700 --> 00:28:53,710
Si mi dedo en el
momento es PTR, y es

649
00:28:53,710 --> 00:28:55,920
que apunta a lo que sea
primero está apuntando a,

650
00:28:55,920 --> 00:28:59,290
¿cómo puedo mover mi dedo
al siguiente nodo en el código?

651
00:28:59,290 --> 00:29:01,915
Bueno, ¿cuál es la ruta de navegación que estamos
va a seguir en este caso?

652
00:29:01,915 --> 00:29:03,464

653
00:29:03,464 --> 00:29:04,380
AUDIENCIA: [inaudible].

654
00:29:04,380 --> 00:29:05,630
DAVID J. MALAN: Sí, así que la próxima.

655
00:29:05,630 --> 00:29:06,640

656
00:29:06,640 --> 00:29:09,824
Así que si vuelvo a mi
código aquí, de hecho, estoy

657
00:29:09,824 --> 00:29:12,990
va a seguir adelante y decir puntero, que
es sólo una variable-- temporal es

658
00:29:12,990 --> 00:29:15,320
un nombre raro, ptr, pero
es como temp--

659
00:29:15,320 --> 00:29:19,234
Voy a establecer puntero
igual a lo que sea puntero es--

660
00:29:19,234 --> 00:29:22,150
y de nuevo, esto va a ser un
de errores, para insertar un punto moment-- siguiente.

661
00:29:22,150 --> 00:29:23,551

662
00:29:23,551 --> 00:29:26,550
En otras palabras, me voy a tomar mi
dedo que está señalando a este nodo

663
00:29:26,550 --> 00:29:31,247
aquí y yo voy a decir, ya sabes
qué, eche un vistazo a el siguiente campo

664
00:29:31,247 --> 00:29:33,330
y mover el dedo para
como sea que se señala en.

665
00:29:33,330 --> 00:29:35,163
Y esto va a
repetir, repetir, repetir.

666
00:29:35,163 --> 00:29:37,630
Pero cuando lo hace mi dedo
dejar de hacer nada en absoluto?

667
00:29:37,630 --> 00:29:40,095
Tan pronto como qué línea de código en patadas?

668
00:29:40,095 --> 00:29:40,970
AUDIENCIA: [inaudible]

669
00:29:40,970 --> 00:29:43,060
DAVID J. MALAN: Si el punto mientras
puntero no es igual a null.

670
00:29:43,060 --> 00:29:44,900
En algún momento de mi dedo de
va a estar apuntando a nula

671
00:29:44,900 --> 00:29:47,070
y yo voy a realizar
ese es el final de esta lista.

672
00:29:47,070 --> 00:29:48,910
Ahora, esto es un poco
mentira piadosa para la simplicidad.

673
00:29:48,910 --> 00:29:51,580
Resulta que a pesar de que
acaba de enterar esta notación de puntos

674
00:29:51,580 --> 00:29:55,220
para estructuras, puntero no es una estructura.

675
00:29:55,220 --> 00:29:56,580
ptr es qué?

676
00:29:56,580 --> 00:29:58,350
Sólo para ser más quisquillosa.

677
00:29:58,350 --> 00:29:59,720

678
00:29:59,720 --> 00:30:01,360
Es un puntero a un nodo.

679
00:30:01,360 --> 00:30:03,120
No es un nodo en sí.

680
00:30:03,120 --> 00:30:06,650
Si no tuviera la estrella aquí, puntero
absolutely-- es un nodo.

681
00:30:06,650 --> 00:30:08,650
Esto es como una semana
declaración de una variable,

682
00:30:08,650 --> 00:30:10,120
a pesar de que la palabra "nodo" es nueva.

683
00:30:10,120 --> 00:30:13,860
>> Pero tan pronto como se introduce un
estrella, ahora es un puntero a un nodo.

684
00:30:13,860 --> 00:30:17,960
Y, por desgracia no se puede utilizar
la notación de puntos para un puntero.

685
00:30:17,960 --> 00:30:21,070
Usted tiene que usar la flecha
notación, que, sorprendentemente,

686
00:30:21,070 --> 00:30:23,470
es la primera vez que un pedazo
de sintaxis parece intuitivo.

687
00:30:23,470 --> 00:30:25,245
Esto se ve, literalmente, como una flecha.

688
00:30:25,245 --> 00:30:26,370
Y eso es una buena cosa.

689
00:30:26,370 --> 00:30:28,995
Y aquí abajo, literalmente,
se parece a una flecha.

690
00:30:28,995 --> 00:30:31,870
Así que creo que esa es la la-- no lo hago
Creo que estoy demasiado cometer aquí-- I

691
00:30:31,870 --> 00:30:34,120
Creo que es la última pieza nueva
de la sintaxis que vamos a ver.

692
00:30:34,120 --> 00:30:36,500
Y por suerte, es de hecho
un poco más intuitivo.

693
00:30:36,500 --> 00:30:40,090
>> Ahora, para aquellos de ustedes que
podrían preferir la manera antigua,

694
00:30:40,090 --> 00:30:42,550
aún puede utilizar la notación de puntos.

695
00:30:42,550 --> 00:30:45,380
Pero según Lunes de
conversación, primero

696
00:30:45,380 --> 00:30:50,530
que tenga que ir allí, ir a ese
abordar, y luego acceder al campo.

697
00:30:50,530 --> 00:30:51,897
Así que esto también es correcto.

698
00:30:51,897 --> 00:30:53,730
Y, francamente, este es un
poco más pedante.

699
00:30:53,730 --> 00:30:56,530
Usted está literalmente diciendo desreferenciar
el puntero e ir allí.

700
00:30:56,530 --> 00:30:59,320
Entonces agarra .n, el campo llamado n.

701
00:30:59,320 --> 00:31:01,370
Pero, francamente, nadie quiere
para escribir o leer esto.

702
00:31:01,370 --> 00:31:03,620
Y así el mundo inventó
la notación flecha, que

703
00:31:03,620 --> 00:31:06,980
es equivalente, idéntico,
es sólo el azúcar sintáctica.

704
00:31:06,980 --> 00:31:10,570
Así que una forma elegante de decir esto
se ve mejor, o se ve más simple.

705
00:31:10,570 --> 00:31:12,296
>> Así que ahora me voy a hacer otra cosa.

706
00:31:12,296 --> 00:31:15,420
Voy a decir "break" Una vez que he
encontró, así que no la guardo en busca de ella.

707
00:31:15,420 --> 00:31:17,620
Pero esta es la esencia
de una función de búsqueda.

708
00:31:17,620 --> 00:31:21,710
Pero es mucho más fácil, en el
final, no caminar a través del código.

709
00:31:21,710 --> 00:31:25,570
Esta es de hecho la aplicación formal
de búsqueda de código de distribución actual.

710
00:31:25,570 --> 00:31:30,530
Me atrevo a decir que la inserción no es
particularmente divertido caminar por

711
00:31:30,530 --> 00:31:33,180
visualmente, ni tampoco eliminar, incluso
aunque al final del día

712
00:31:33,180 --> 00:31:35,460
se reducen a bastante
heurísticas simples.

713
00:31:35,460 --> 00:31:36,330
>> Así que vamos a hacer esto.

714
00:31:36,330 --> 00:31:39,250
Si Usted humor conmigo aquí, lo hice
traer un montón de bolas de estrés.

715
00:31:39,250 --> 00:31:40,620
Me trajo un montón de números.

716
00:31:40,620 --> 00:31:46,562
Y podríamos conseguir unos pocos voluntarios
para representar 9, 17, 20, 22, 29, y 34?

717
00:31:46,562 --> 00:31:48,270
Así que, esencialmente todo el mundo
quien está aquí hoy.

718
00:31:48,270 --> 00:31:50,170

719
00:31:50,170 --> 00:31:52,760
Ese fue uno, dos, tres,
cuatro, cinco, seis personas.

720
00:31:52,760 --> 00:31:55,740
Y me han pedido que ir-- ver, no
una en la parte posterior levanta sus manos.

721
00:31:55,740 --> 00:32:01,910
Bueno, uno, dos, tres, cuatro,
cinco-- déjame cargar balance-- seis.

722
00:32:01,910 --> 00:32:03,051
OK, vamos hasta seis.

723
00:32:03,051 --> 00:32:04,050
Necesitaremos otras personas.

724
00:32:04,050 --> 00:32:05,460
Trajimos bolas de estrés adicionales.

725
00:32:05,460 --> 00:32:08,200
Y si pudiera, para
un momento, la línea

726
00:32:08,200 --> 00:32:10,490
ustedes justo
te gusta esta foto aquí.

727
00:32:10,490 --> 00:32:15,200

728
00:32:15,200 --> 00:32:15,959
>> Bien.

729
00:32:15,959 --> 00:32:17,125
Vamos a ver, ¿cómo te llamas?

730
00:32:17,125 --> 00:32:17,550
>> AUDIENCIA: Andrew.

731
00:32:17,550 --> 00:32:18,800
>> DAVID J. MALAN: Andrew,
eres el número 9.

732
00:32:18,800 --> 00:32:19,540
Encantada de conocerte.

733
00:32:19,540 --> 00:32:20,400
Aquí tienes.

734
00:32:20,400 --> 00:32:21,593

735
00:32:21,593 --> 00:32:22,176
AUDIENCIA: Jen.

736
00:32:22,176 --> 00:32:22,662
DAVID J. MALAN: Jen.

737
00:32:22,662 --> 00:32:23,162
David.

738
00:32:23,162 --> 00:32:23,765
Número 17.

739
00:32:23,765 --> 00:32:24,950

740
00:32:24,950 --> 00:32:25,450
Sí?

741
00:32:25,450 --> 00:32:26,400
>> AUDIENCIA: Soy Julia.

742
00:32:26,400 --> 00:32:26,980
>> DAVID J. MALAN: Julia, David.

743
00:32:26,980 --> 00:32:27,545
Número 20.

744
00:32:27,545 --> 00:32:28,507

745
00:32:28,507 --> 00:32:29,340
AUDIENCIA: Cristiano.

746
00:32:29,340 --> 00:32:30,715
DAVID J. MALAN: Cristiano, David.

747
00:32:30,715 --> 00:32:31,541
Número 22.

748
00:32:31,541 --> 00:32:32,040
Y?

749
00:32:32,040 --> 00:32:32,649
>> AUDIENCIA: JP.

750
00:32:32,649 --> 00:32:33,440
DAVID J. MALAN: JP.

751
00:32:33,440 --> 00:32:34,880
Número 29.

752
00:32:34,880 --> 00:32:37,080
Así que adelante y obtener en-- Uh oh.

753
00:32:37,080 --> 00:32:38,486

754
00:32:38,486 --> 00:32:38,985
Uh oh.

755
00:32:38,985 --> 00:32:39,650

756
00:32:39,650 --> 00:32:40,150
Standby.

757
00:32:40,150 --> 00:32:41,360

758
00:32:41,360 --> 00:32:42,390
20.

759
00:32:42,390 --> 00:32:43,682
¿Alguien tiene un marcador?

760
00:32:43,682 --> 00:32:44,890
AUDIENCIA: Tengo un Sharpie.

761
00:32:44,890 --> 00:32:45,660
DAVID J. MALAN: ¿Tienes un Sharpie?

762
00:32:45,660 --> 00:32:46,159
Okay.

763
00:32:46,159 --> 00:32:47,577

764
00:32:47,577 --> 00:32:49,160
Y ¿alguien tiene un pedazo de papel?

765
00:32:49,160 --> 00:32:51,562

766
00:32:51,562 --> 00:32:52,270
Guarde la conferencia.

767
00:32:52,270 --> 00:32:53,810

768
00:32:53,810 --> 00:32:55,362
Venga.

769
00:32:55,362 --> 00:32:56,320
AUDIENCIA: lo tenemos.

770
00:32:56,320 --> 00:32:57,600
DAVID J. MALAN: lo conseguimos?

771
00:32:57,600 --> 00:32:58,577
Muy bien, gracias.

772
00:32:58,577 --> 00:33:01,380

773
00:33:01,380 --> 00:33:02,520
Aquí vamos.

774
00:33:02,520 --> 00:33:03,582
¿Era esto de ti?

775
00:33:03,582 --> 00:33:04,540
Acabas de salvar el día.

776
00:33:04,540 --> 00:33:05,670

777
00:33:05,670 --> 00:33:07,220
Así 29.

778
00:33:07,220 --> 00:33:10,510

779
00:33:10,510 --> 00:33:11,110
Bien.

780
00:33:11,110 --> 00:33:13,360

781
00:33:13,360 --> 00:33:14,890
Lo escribo mal el 29, pero no está mal.

782
00:33:14,890 --> 00:33:15,720
Seguir adelante.

783
00:33:15,720 --> 00:33:18,114
Muy bien, te voy a dar
su pluma hacia atrás momentáneamente.

784
00:33:18,114 --> 00:33:19,280
Así que tenemos a esta gente aquí.

785
00:33:19,280 --> 00:33:20,330
Vamos a tener otro.

786
00:33:20,330 --> 00:33:23,750
Gabe, ¿quieres jugar
el primer elemento en esta lista?

787
00:33:23,750 --> 00:33:25,705
Te necesitamos para que apunte
a esta buena gente.

788
00:33:25,705 --> 00:33:26,930

789
00:33:26,930 --> 00:33:31,030
Así que 9, 17, 20, 22, especie
de 29, y luego 34.

790
00:33:31,030 --> 00:33:32,160

791
00:33:32,160 --> 00:33:33,325
¿Perdimos a alguien?

792
00:33:33,325 --> 00:33:33,950
Tengo un 34.

793
00:33:33,950 --> 00:33:36,730
Dónde hizo-- bien, que quiere ser 34?

794
00:33:36,730 --> 00:33:37,605
Bien, vamos hacia arriba, 34.

795
00:33:37,605 --> 00:33:39,280

796
00:33:39,280 --> 00:33:41,220
Muy bien, esto será
bien vale la pena el clímax.

797
00:33:41,220 --> 00:33:41,550
Cuál es tu nombre?

798
00:33:41,550 --> 00:33:42,040
>> AUDIENCIA: Peter.

799
00:33:42,040 --> 00:33:43,456
>> DAVID J. MALAN: Peter, vamos arriba.

800
00:33:43,456 --> 00:33:46,810
Muy bien, así que aquí tiene un
todo grupo de nodos.

801
00:33:46,810 --> 00:33:49,060
Cada uno de ustedes representa
uno de estos rectángulos.

802
00:33:49,060 --> 00:33:51,930
Y Gabe, el poco extraño
al hombre, representa en primer lugar.

803
00:33:51,930 --> 00:33:54,850
Así que su puntero es un poco más pequeño
en la pantalla de todos los demás.

804
00:33:54,850 --> 00:33:58,120
Y en este caso, cada uno de su izquierda
manos va a apuntar hacia abajo o bien,

805
00:33:58,120 --> 00:34:01,085
lo cual representa una nula, por lo que
sólo la ausencia de un puntero,

806
00:34:01,085 --> 00:34:03,210
o que va a estar apuntando
en un nodo al lado de usted.

807
00:34:03,210 --> 00:34:05,440
>> Así que ahora mismo, si adornas
ustedes como la imagen

808
00:34:05,440 --> 00:34:07,585
aquí, seguir adelante y punto
el uno al otro, con Gabe

809
00:34:07,585 --> 00:34:11,030
en particular, apuntando a
número 9 para representar la lista.

810
00:34:11,030 --> 00:34:14,050
Aceptar, y el número 34, la mano izquierda
sólo deben estar apuntando hacia el suelo.

811
00:34:14,050 --> 00:34:15,750
>> Aceptar, por lo que esta es la lista enlazada.

812
00:34:15,750 --> 00:34:17,580
Así que este es el escenario en cuestión.

813
00:34:17,580 --> 00:34:20,210
Y, de hecho, esto es representativo
de una clase de problemas

814
00:34:20,210 --> 00:34:21,929
que usted puede tratar de resolver con el código.

815
00:34:21,929 --> 00:34:25,020
Usted quiere insertar en última instancia
un nuevo elemento en la lista.

816
00:34:25,020 --> 00:34:27,494
En este caso, vamos a
tratar de insertar el número 55.

817
00:34:27,494 --> 00:34:28,500

818
00:34:28,500 --> 00:34:30,860
Pero no va a ser
diferentes casos a considerar.

819
00:34:30,860 --> 00:34:34,409
Y, de hecho, esto va a ser una
de la gran imagen comida para llevar aquí, es,

820
00:34:34,409 --> 00:34:35,659
¿cuáles son los diferentes casos.

821
00:34:35,659 --> 00:34:39,120
¿Cuáles son los diferentes si las condiciones o
ramas que su programa podría tener?

822
00:34:39,120 --> 00:34:42,024
>> Bueno, el número al que está tratando de
inserción, que ahora sabemos que ser 55,

823
00:34:42,024 --> 00:34:44,650
pero si usted no lo sabía
de antemano, me atrevo a decir

824
00:34:44,650 --> 00:34:47,840
cae en al menos tres
posibles situaciones.

825
00:34:47,840 --> 00:34:49,717
¿Dónde podría ser un nuevo elemento?

826
00:34:49,717 --> 00:34:51,050
AUDIENCIA: Y al final o en medio.

827
00:34:51,050 --> 00:34:54,150
DAVID J. MALAN: Al final, en
el medio, o al principio.

828
00:34:54,150 --> 00:34:56,650
Así que yo reclamo que hay al menos
tres problemas que tienen que resolver.

829
00:34:56,650 --> 00:34:58,691
Vamos a elegir lo que es tal vez
posiblemente el más simple

830
00:34:58,691 --> 00:35:01,090
uno, cuando el elemento nuevo
pertenece al principio.

831
00:35:01,090 --> 00:35:04,040
Así que voy a tener bastante código
como la búsqueda, que sólo escribí.

832
00:35:04,040 --> 00:35:07,670
Y yo voy a tener ptr, que
Voy represento aquí con mi dedo,

833
00:35:07,670 --> 00:35:08,370
como siempre.

834
00:35:08,370 --> 00:35:12,430
>> Y recuerda, ¿qué valor
hicimos inicializamos ptr a?

835
00:35:12,430 --> 00:35:15,300
Así que hemos inicializado en null inicialmente.

836
00:35:15,300 --> 00:35:16,410

837
00:35:16,410 --> 00:35:19,770
Pero entonces ¿qué hicimos una vez que
estaban dentro de nuestra función de búsqueda?

838
00:35:19,770 --> 00:35:20,940

839
00:35:20,940 --> 00:35:24,870
La fijamos igual al primero,
lo que no significa hacer esto.

840
00:35:24,870 --> 00:35:25,890

841
00:35:25,890 --> 00:35:30,570
Si fijo ptr igual al primero, lo que
debe ser realmente mi mano apuntando a?

842
00:35:30,570 --> 00:35:31,070
Derecha.

843
00:35:31,070 --> 00:35:33,290
Así que si Gabe y yo vamos
ser valores iguales aquí,

844
00:35:33,290 --> 00:35:34,760
necesitamos tanto el punto en el número 9.

845
00:35:34,760 --> 00:35:36,420
>> Así que este fue el comienzo de nuestra historia.

846
00:35:36,420 --> 00:35:38,700
Y ahora esto es sólo sencillo,
a pesar de que la sintaxis es nueva.

847
00:35:38,700 --> 00:35:40,580
Conceptualmente esto es sólo búsqueda lineal.

848
00:35:40,580 --> 00:35:42,750
Is 55, igual a 9?

849
00:35:42,750 --> 00:35:45,559
O más bien, digamos menos de 9.

850
00:35:45,559 --> 00:35:47,600
Porque yo estoy tratando de
averiguar dónde poner 55.

851
00:35:47,600 --> 00:35:51,270
Menos de 9, a menos de 17, menos
de 20, menos de 22, menos de 29,

852
00:35:51,270 --> 00:35:52,510
menos de 34, no.

853
00:35:52,510 --> 00:35:55,080
Así que ahora estamos en el caso
uno de al menos tres.

854
00:35:55,080 --> 00:35:59,910
>> Si quiero insertar 55 por aquí, lo que
líneas de necesidad código se ejecutan?

855
00:35:59,910 --> 00:36:01,890
¿Cómo funciona este cuadro de
los seres humanos tienen que cambiar?

856
00:36:01,890 --> 00:36:03,181
¿Qué hago con mi mano izquierda?

857
00:36:03,181 --> 00:36:04,530

858
00:36:04,530 --> 00:36:07,360
Esto debería ser nula inicialmente,
porque estoy en el final de la lista.

859
00:36:07,360 --> 00:36:09,318
Y lo que debería ocurrir
aquí con Peter, ¿verdad?

860
00:36:09,318 --> 00:36:10,520

861
00:36:10,520 --> 00:36:12,430
Él, obviamente, va a apuntar a mí.

862
00:36:12,430 --> 00:36:15,580
Así que yo reclamo que hay al menos dos líneas
de código en el código de ejemplo a partir de hoy

863
00:36:15,580 --> 00:36:18,570
eso va a implementar este
escenario de la adición de 55 en la cola.

864
00:36:18,570 --> 00:36:20,950
Y podría tener a alguien hop
y sólo representan el 55?

865
00:36:20,950 --> 00:36:22,200
Muy bien, usted es el nuevo 55.

866
00:36:22,200 --> 00:36:23,580

867
00:36:23,580 --> 00:36:27,054
>> Así que ahora lo que si el próximo
escenario se presenta,

868
00:36:27,054 --> 00:36:29,720
y queremos insertar en el
comenzando o la cabeza de esta lista?

869
00:36:29,720 --> 00:36:31,100
¿Y cuál es su nombre, el número 55?

870
00:36:31,100 --> 00:36:31,420
>> AUDIENCIA: Jack.

871
00:36:31,420 --> 00:36:32,295
>> DAVID J. MALAN: Jack?

872
00:36:32,295 --> 00:36:33,585
Bueno, encantado de conocerte.

873
00:36:33,585 --> 00:36:34,210
Bienvenido a bordo.

874
00:36:34,210 --> 00:36:36,640
Así que ahora vamos a
insertar, por ejemplo, el número 5.

875
00:36:36,640 --> 00:36:39,840
Aquí está el segundo caso de la
tres se nos ocurrió antes.

876
00:36:39,840 --> 00:36:43,050
Así que si 5 pertenece al principio,
vamos a ver cómo nos encontramos con que fuera.

877
00:36:43,050 --> 00:36:46,310
Puedo inicializar mi ptr
puntero a número 9 de nuevo.

878
00:36:46,310 --> 00:36:49,140
Y me di cuenta, oh, 5 es menor que 9.

879
00:36:49,140 --> 00:36:50,880
Así que arreglar esta imagen para nosotros.

880
00:36:50,880 --> 00:36:54,820
¿Qué manos, Gabe o David de
o-- ¿cómo se llama el número del 9?

881
00:36:54,820 --> 00:36:55,740
>> AUDIENCIA: Jen.

882
00:36:55,740 --> 00:36:58,406
>> DAVID J. MALAN: manos-- de Jen
cuál de nuestras manos que tenga que cambiar?

883
00:36:58,406 --> 00:36:58,905

884
00:36:58,905 --> 00:37:00,970
OK, así que Gabe señala en qué ahora?

885
00:37:00,970 --> 00:37:01,640
En mí.

886
00:37:01,640 --> 00:37:02,750
Yo soy el nuevo nodo.

887
00:37:02,750 --> 00:37:04,870
Así que voy a clase de movimiento
aquí para verlo visualmente.

888
00:37:04,870 --> 00:37:06,435
Y mientras tanto, ¿qué debo señalar que?

889
00:37:06,435 --> 00:37:07,910

890
00:37:07,910 --> 00:37:09,020
Aún donde estoy apuntando.

891
00:37:09,020 --> 00:37:10,000
Así que es eso.

892
00:37:10,000 --> 00:37:13,717
Así que en realidad una línea de arreglos de código
este tema en particular, lo que parece.

893
00:37:13,717 --> 00:37:14,800
Muy bien, así que eso es bueno.

894
00:37:14,800 --> 00:37:17,580
Y alguien puede ser un marcador de posición para el 5?

895
00:37:17,580 --> 00:37:18,080
Vamos arriba.

896
00:37:18,080 --> 00:37:20,270

897
00:37:20,270 --> 00:37:21,320
Te llevaremos la próxima vez.

898
00:37:21,320 --> 00:37:24,280
>> Muy bien, así que ahora-- y
Como acotación al margen, los nombres

899
00:37:24,280 --> 00:37:28,510
No voy a hacer mención explícita del derecho
Ahora, pred puntero, puntero predecesor

900
00:37:28,510 --> 00:37:31,260
y nuevo puntero, que es
sólo los nombres dado

901
00:37:31,260 --> 00:37:35,280
en el código de ejemplo a los punteros o
mis manos, que es una especie de apuntando alrededor.

902
00:37:35,280 --> 00:37:36,060
Cuál es tu nombre?

903
00:37:36,060 --> 00:37:36,700
>> AUDIENCIA: Christine.

904
00:37:36,700 --> 00:37:37,100
>> DAVID J. MALAN: Christine.

905
00:37:37,100 --> 00:37:38,090
Bienvenido a bordo.

906
00:37:38,090 --> 00:37:42,180
Muy bien, así que vamos a considerar ahora
un escenario ligeramente más molesto,

907
00:37:42,180 --> 00:37:46,350
por el que quiero insertar
algo así como 26 en esto.

908
00:37:46,350 --> 00:37:47,090
20?

909
00:37:47,090 --> 00:37:47,590
¿Qué?

910
00:37:47,590 --> 00:37:50,510
Estos son-- buena cosa que tenemos esta pluma.

911
00:37:50,510 --> 00:37:51,955
Muy bien, 20.

912
00:37:51,955 --> 00:37:53,640

913
00:37:53,640 --> 00:37:57,570
Si alguien puede conseguir otra pieza de
papel listo, por si caso-- bien.

914
00:37:57,570 --> 00:37:58,370
Oh, interesante.

915
00:37:58,370 --> 00:37:59,760

916
00:37:59,760 --> 00:38:02,390
Bueno, esto es un ejemplo
de un error de conferencias.

917
00:38:02,390 --> 00:38:03,894
Aceptar ¿cuál es tu nombre?

918
00:38:03,894 --> 00:38:04,560
AUDIENCIA: Julia.

919
00:38:04,560 --> 00:38:07,559
DAVID J. MALAN: Julia, ¿puede estallar
y pretender que nunca estuvieron ahí?

920
00:38:07,559 --> 00:38:09,040
OK, esto nunca sucedió.

921
00:38:09,040 --> 00:38:09,680
Gracias.

922
00:38:09,680 --> 00:38:12,180
Así que supongamos que queremos insertar
Julia en esta lista enlazada.

923
00:38:12,180 --> 00:38:13,780
Ella es la número 20.

924
00:38:13,780 --> 00:38:15,530
Y, por supuesto, ella es
va a pertenecer al

925
00:38:15,530 --> 00:38:17,521
begin-- no apunte a nada todavía.

926
00:38:17,521 --> 00:38:20,020
Así que tu mano puede ser tipo de
abajo nulo o algún valor basura.

927
00:38:20,020 --> 00:38:21,210
Digamos la historia rápida.

928
00:38:21,210 --> 00:38:22,980
Estoy señalando en el número 5 de este tiempo.

929
00:38:22,980 --> 00:38:23,880
Entonces compruebo 9.

930
00:38:23,880 --> 00:38:25,130
Luego reviso 17.

931
00:38:25,130 --> 00:38:26,247
Luego reviso 22.

932
00:38:26,247 --> 00:38:27,650

933
00:38:27,650 --> 00:38:32,485
Y me doy cuenta, ooh, Julia
tiene que ir antes de los 22.

934
00:38:32,485 --> 00:38:33,580

935
00:38:33,580 --> 00:38:34,660
Entonces, ¿qué tiene que suceder?

936
00:38:34,660 --> 00:38:35,786

937
00:38:35,786 --> 00:38:36,910
¿Qué manos tienen que cambiar?

938
00:38:36,910 --> 00:38:38,360
Julia, la mía, o--
¿cuál es tu nombre?

939
00:38:38,360 --> 00:38:39,230
>> AUDIENCIA: Cristiano.

940
00:38:39,230 --> 00:38:40,060
>> DAVID J. MALAN: Cristiano o?

941
00:38:40,060 --> 00:38:40,560
>> AUDIENCIA: Andy.

942
00:38:40,560 --> 00:38:40,905
>> DAVID J. MALAN: Andy.

943
00:38:40,905 --> 00:38:41,654
Cristiano o Andy?

944
00:38:41,654 --> 00:38:44,280

945
00:38:44,280 --> 00:38:45,690
Andy tiene que apuntar a?

946
00:38:45,690 --> 00:38:46,780

947
00:38:46,780 --> 00:38:47,341
Julia.

948
00:38:47,341 --> 00:38:47,840
Bien.

949
00:38:47,840 --> 00:38:48,960
Así que Andy, qué quieres apuntar a Julia?

950
00:38:48,960 --> 00:38:50,120
Pero espere un minuto.

951
00:38:50,120 --> 00:38:53,260
En la historia hasta el momento,
Yo soy el tipo de uno

952
00:38:53,260 --> 00:38:56,800
a cargo, en el sentido de que
puntero es la cosa que es

953
00:38:56,800 --> 00:38:57,850
moviéndose a través de la lista.

954
00:38:57,850 --> 00:39:00,800
Puede ser que tengamos un nombre para Andy, pero
no hay variable llamada Andy.

955
00:39:00,800 --> 00:39:04,320
La única otra variable que tenemos es
en primer lugar, que está representado por Gabe.

956
00:39:04,320 --> 00:39:07,690
>> Así que esto es en realidad la razón por lo tanto
Hasta aquí no hemos necesitado esto.

957
00:39:07,690 --> 00:39:10,846
Pero ahora en la pantalla no es
mencionar de nuevo de puntero pred.

958
00:39:10,846 --> 00:39:11,970
Así que permítanme ser más explícito.

959
00:39:11,970 --> 00:39:14,820
Si esta es puntero, tuve una mejor
ser un poco más inteligente

960
00:39:14,820 --> 00:39:15,950
sobre mi iteración.

961
00:39:15,950 --> 00:39:19,580
Si no te importa mi pasar por aquí
de nuevo, señalando aquí, señalando aquí.

962
00:39:19,580 --> 00:39:22,500
Pero déjame tener un puntero pred,
puntero predecesor, que es

963
00:39:22,500 --> 00:39:24,740
especie de que apunta a la
elemento que estaba justo en.

964
00:39:24,740 --> 00:39:27,330
Así que cuando voy aquí, ahora
mis actualizaciones mano izquierda.

965
00:39:27,330 --> 00:39:29,370
Cuando voy allí a mis actualizaciones de la mano izquierda.

966
00:39:29,370 --> 00:39:33,090
Y ahora tengo no sólo un puntero a
el elemento que va detrás de Julia,

967
00:39:33,090 --> 00:39:36,300
Todavía tengo un puntero a
Andy, el elemento antes.

968
00:39:36,300 --> 00:39:39,430
Así que usted tiene acceso, en esencia,
pan rallado, si se quiere,

969
00:39:39,430 --> 00:39:41,500
a todos los punteros necesarios.

970
00:39:41,500 --> 00:39:43,710
>> Así que si yo estoy apuntando a
Andy y yo también estoy apuntando

971
00:39:43,710 --> 00:39:47,105
en cristiano, cuyas manos
ahora debe ser señalado en otro lugar?

972
00:39:47,105 --> 00:39:48,770

973
00:39:48,770 --> 00:39:51,960
Así que Andy ahora puede apuntar a Julia.

974
00:39:51,960 --> 00:39:54,460
Julia ahora puede apuntar a Cristiano.

975
00:39:54,460 --> 00:39:56,950
Porque ella puede copiar mi
puntero de la mano derecha.

976
00:39:56,950 --> 00:40:00,044
Y eso te pone con eficacia
de nuevo en este lugar aquí.

977
00:40:00,044 --> 00:40:02,460
Así que en resumen, a pesar de que esta
nos está tomando clase de siempre

978
00:40:02,460 --> 00:40:04,510
para actualizar en realidad un
lista enlazada, se dan cuenta

979
00:40:04,510 --> 00:40:06,580
que las operaciones
son relativamente simples.

980
00:40:06,580 --> 00:40:10,030
Es de uno, dos, tres
líneas de código en última instancia.

981
00:40:10,030 --> 00:40:12,780
Pero envuelto alrededor de los
líneas de código, presumiblemente,

982
00:40:12,780 --> 00:40:16,350
es que efectivamente un poco de lógica
hace la pregunta, ¿dónde estamos?

983
00:40:16,350 --> 00:40:18,970
¿Estamos en el comienzo,
el medio, o al final?

984
00:40:18,970 --> 00:40:21,890
>> Ahora, sin duda hay alguna otra
operaciones que podríamos poner en práctica.

985
00:40:21,890 --> 00:40:24,880
Y estas fotos aquí sólo representan
lo que acabamos de hacer con los seres humanos.

986
00:40:24,880 --> 00:40:26,080
¿Qué pasa con la eliminación?

987
00:40:26,080 --> 00:40:30,650
Si quiero, por ejemplo,
quitar el número 34 o 55,

988
00:40:30,650 --> 00:40:34,680
Puede que tenga el mismo tipo de código,
pero voy a necesitar uno o dos pasos.

989
00:40:34,680 --> 00:40:36,110
Porque lo que hay de nuevo?

990
00:40:36,110 --> 00:40:40,460
Si elimino a alguien al final,
como el número 55 y luego 34,

991
00:40:40,460 --> 00:40:42,995
lo que también tiene que cambiar como yo que?

992
00:40:42,995 --> 00:40:44,870
Tengo que no evict--
¿cuál es tu nombre?

993
00:40:44,870 --> 00:40:45,380
>> AUDIENCIA: Jack.

994
00:40:45,380 --> 00:40:46,255
>> DAVID J. MALAN: Jack.

995
00:40:46,255 --> 00:40:49,770
Tengo que no sólo evict-- libre Jack,
tan literalmente llamar gratis Jack, o al menos

996
00:40:49,770 --> 00:40:53,530
el puntero allí también, pero ahora
lo que hay que cambiar con Peter?

997
00:40:53,530 --> 00:40:55,510
Su mano mejor comienzo que apunta hacia abajo.

998
00:40:55,510 --> 00:40:59,300
Porque tan pronto como yo lo llamo gratuito
Jack, si sigue apuntando de Pedro en Jack

999
00:40:59,300 --> 00:41:02,530
y por lo tanto sigo recorriendo
la lista y el acceso este puntero,

1000
00:41:02,530 --> 00:41:05,650
que es cuando nuestro amigo segmentación de edad
criticar realidad podría poner en.

1001
00:41:05,650 --> 00:41:07,860
Porque nos hemos dado la
volver la memoria a Jack.

1002
00:41:07,860 --> 00:41:10,760
>> Puede permanecer allí
torpemente por un momento.

1003
00:41:10,760 --> 00:41:13,410
Porque tenemos sólo un par
operaciones finales a tener en cuenta.

1004
00:41:13,410 --> 00:41:15,600
Extracción de la cabeza de la lista,
o la principio-- y éste de

1005
00:41:15,600 --> 00:41:16,349
un poco molesto.

1006
00:41:16,349 --> 00:41:19,640
Porque tenemos que saber que Gabe
es una especie de especial en este programa.

1007
00:41:19,640 --> 00:41:21,440
Porque de hecho, él tiene su propio puntero.

1008
00:41:21,440 --> 00:41:24,860
Él simplemente no está siendo señaló,
como casi todos los demás aquí.

1009
00:41:24,860 --> 00:41:28,112
>> Así que cuando la cabeza de la lista es
eliminado, cuyas manos que tenga que cambiar ahora?

1010
00:41:28,112 --> 00:41:29,070
¿Cuál es tu nombre?

1011
00:41:29,070 --> 00:41:29,450
>> AUDIENCIA: Christine.

1012
00:41:29,450 --> 00:41:31,408
>> DAVID J. MALAN: Soy horrible
en nombres, al parecer.

1013
00:41:31,408 --> 00:41:34,011
Así Christine y Gabe,
cuyas manos necesite cambiar

1014
00:41:34,011 --> 00:41:36,510
cuando tratamos de eliminar Christine,
número 5, de la foto?

1015
00:41:36,510 --> 00:41:37,550

1016
00:41:37,550 --> 00:41:38,820
OK, así que vamos a hacerlo Gabe.

1017
00:41:38,820 --> 00:41:40,950
Gabe va a apuntar,
presumiblemente, en el número 9.

1018
00:41:40,950 --> 00:41:42,230

1019
00:41:42,230 --> 00:41:44,642
Pero lo siguiente que debería ocurrir?

1020
00:41:44,642 --> 00:41:46,600
AUDIENCIA: Christine debe
ser nulo [inaudible].

1021
00:41:46,600 --> 00:41:50,244
DAVID J. MALAN: OK, probablemente deberíamos
make-- oí "nulo" en algún lugar.

1022
00:41:50,244 --> 00:41:51,410
AUDIENCIA: Null y liberarla.

1023
00:41:51,410 --> 00:41:51,855
DAVID J. MALAN: null qué?

1024
00:41:51,855 --> 00:41:53,074
AUDIENCIA: Null y liberarla.

1025
00:41:53,074 --> 00:41:54,490
DAVID J. MALAN: Null y liberarla.

1026
00:41:54,490 --> 00:41:55,422
Así que esto es muy fácil.

1027
00:41:55,422 --> 00:41:58,380
Y es perfecto que ahora eres una especie
de pie allí, que no pertenece.

1028
00:41:58,380 --> 00:42:00,430
Porque has sido
desacoplado de la lista.

1029
00:42:00,430 --> 00:42:02,820
Has sido efectivamente
huérfanos de la lista.

1030
00:42:02,820 --> 00:42:07,770
Y así nos habíamos mejor llamar gratis ahora
Christine de dar ese memoria.

1031
00:42:07,770 --> 00:42:10,240
De lo contrario, cada vez que
eliminar un nodo de la lista

1032
00:42:10,240 --> 00:42:14,230
que podríamos estar haciendo la lista
más corto, pero en realidad no disminuyendo

1033
00:42:14,230 --> 00:42:15,096
el tamaño en memoria.

1034
00:42:15,096 --> 00:42:17,720
Y por lo que si estamos añadiendo y
añadiendo, añadiendo cosas a la lista,

1035
00:42:17,720 --> 00:42:19,280
mi equipo podría conseguir más lento
y más y más lento,

1036
00:42:19,280 --> 00:42:21,740
porque me estoy quedando sin
memoria, incluso si no estoy realmente

1037
00:42:21,740 --> 00:42:25,580
usando bytes de Christine
de la memoria más.

1038
00:42:25,580 --> 00:42:28,500
>> Así que al final hay otra
escenarios, de la eliminación supuesto--

1039
00:42:28,500 --> 00:42:30,640
en el medio, la eliminación
al final, como hemos visto.

1040
00:42:30,640 --> 00:42:32,348
Pero el más interesante
reto ahora es

1041
00:42:32,348 --> 00:42:34,770
va a ser considerar exactamente
lo que el tiempo de ejecución es.

1042
00:42:34,770 --> 00:42:36,640
Así que no sólo se puede mantener un
trozos de papel, si, Gabe,

1043
00:42:36,640 --> 00:42:38,640
que no le importaría dar
todos una bola de la tensión.

1044
00:42:38,640 --> 00:42:42,100
Muchas gracias a nuestra lista enlazada
de voluntarios aquí, si pudiera.

1045
00:42:42,100 --> 00:42:45,320
>> [Aplausos]

1046
00:42:45,320 --> 00:42:46,700
>> DAVID J. MALAN: Muy bien.

1047
00:42:46,700 --> 00:42:51,110
Así que un par de analítica
preguntas luego, si pudiera.

1048
00:42:51,110 --> 00:42:59,670
Hemos visto esta notación antes,
gran O y omega, límites superiores

1049
00:42:59,670 --> 00:43:02,520
y cotas inferiores de la
tiempo de algún algoritmo se ejecuta.

1050
00:43:02,520 --> 00:43:04,950
Así que vamos a considerar sólo
un par de preguntas.

1051
00:43:04,950 --> 00:43:07,090
>> Uno, y lo dijimos
antes, lo que es la gestión

1052
00:43:07,090 --> 00:43:10,647
tiempo de búsqueda de un
lista en términos de gran O?

1053
00:43:10,647 --> 00:43:13,480
¿Qué es un límite superior en el funcionamiento
tiempo de búsqueda una lista enlazada

1054
00:43:13,480 --> 00:43:16,340
tal como se aplica por nuestros voluntarios aquí?

1055
00:43:16,340 --> 00:43:17,820
Es grande O de n, lineal.

1056
00:43:17,820 --> 00:43:20,630
Debido a que en el peor de los casos,
el elemento, como 55,

1057
00:43:20,630 --> 00:43:23,830
podríamos estar buscando podríamos estar donde
Jack era, todo el camino al final.

1058
00:43:23,830 --> 00:43:28,250
Y, por desgracia, a diferencia de una matriz
no podemos conseguir la suposición este momento.

1059
00:43:28,250 --> 00:43:31,820
A pesar de todos nuestros seres humanos eran
ordenados de elementos pequeños, 5,

1060
00:43:31,820 --> 00:43:35,900
todo el camino hasta el elemento más grande,
55, que suele ser una buena cosa.

1061
00:43:35,900 --> 00:43:38,815
¿Pero qué tiene esa suposición
ya no nos permite hacer?

1062
00:43:38,815 --> 00:43:39,775

1063
00:43:39,775 --> 00:43:40,650
AUDIENCIA: [inaudible]

1064
00:43:40,650 --> 00:43:40,920
DAVID J. MALAN: Diga otra vez?

1065
00:43:40,920 --> 00:43:41,800
AUDIENCIA: Acceso aleatorio.

1066
00:43:41,800 --> 00:43:43,049
DAVID J. MALAN: Acceso aleatorio.

1067
00:43:43,049 --> 00:43:46,330
Y a su vez, eso significa que puede no
ya utilizar ceros débil, la intuición,

1068
00:43:46,330 --> 00:43:49,365
y la evidencia de la utilización de binario
buscar y dividir y conquistar.

1069
00:43:49,365 --> 00:43:51,240
Porque a pesar de que
los seres humanos podían obviamente

1070
00:43:51,240 --> 00:43:54,610
ver que Andy o cristiano fueron
más o menos en el medio de la lista,

1071
00:43:54,610 --> 00:43:57,670
sólo sabemos que como
ordenador con una lectura rápida de la lista

1072
00:43:57,670 --> 00:43:59,029
desde el principio.

1073
00:43:59,029 --> 00:44:00,570
Así que nos hemos dado hasta que el acceso aleatorio.

1074
00:44:00,570 --> 00:44:04,380
>> Así que gran O de n ahora es el superior
con destino en nuestro tiempo de búsqueda.

1075
00:44:04,380 --> 00:44:07,920
¿Qué pasa con el omega de nuestra búsqueda?

1076
00:44:07,920 --> 00:44:11,535
¿Cuál es el límite inferior en la búsqueda
para algún número en esta lista?

1077
00:44:11,535 --> 00:44:12,410
AUDIENCIA: [inaudible]

1078
00:44:12,410 --> 00:44:13,040
DAVID J. MALAN: Diga otra vez?

1079
00:44:13,040 --> 00:44:13,420
AUDIENCIA: Una.

1080
00:44:13,420 --> 00:44:13,800
DAVID J. MALAN: Una.

1081
00:44:13,800 --> 00:44:14,760
Así que el tiempo constante.

1082
00:44:14,760 --> 00:44:17,020
En el mejor de los casos, Christine es
de hecho, al principio de la lista.

1083
00:44:17,020 --> 00:44:19,020
Y estamos buscando
número 5, por lo que la encontró.

1084
00:44:19,020 --> 00:44:19,787
Así que no es gran cosa.

1085
00:44:19,787 --> 00:44:22,370
Pero ella tiene que estar en el
a partir de la lista en este caso.

1086
00:44:22,370 --> 00:44:23,745
¿Qué tal algo como ¿Eliminar?

1087
00:44:23,745 --> 00:44:24,717

1088
00:44:24,717 --> 00:44:26,300
¿Qué pasa si usted quiere eliminar un elemento?

1089
00:44:26,300 --> 00:44:29,200
¿Cuál es el límite superior y el límite inferior
sobre la eliminación de algo de un vinculado

1090
00:44:29,200 --> 00:44:29,699
enumerar?

1091
00:44:29,699 --> 00:44:35,195

1092
00:44:35,195 --> 00:44:36,070
AUDIENCIA: [inaudible]

1093
00:44:36,070 --> 00:44:36,420
DAVID J. MALAN: Diga otra vez?

1094
00:44:36,420 --> 00:44:37,067
AUDIENCIA: n.

1095
00:44:37,067 --> 00:44:38,900
DAVID J. MALAN: n es
de hecho, el límite superior.

1096
00:44:38,900 --> 00:44:41,700
Debido a que en el peor de los casos que tratamos
eliminar Jack, como nosotros lo hicimos.

1097
00:44:41,700 --> 00:44:43,050
Él es todo el camino al final.

1098
00:44:43,050 --> 00:44:45,419
Nos lleva para siempre, o
n pasos para encontrarlo.

1099
00:44:45,419 --> 00:44:46,460
Así que eso es un límite superior.

1100
00:44:46,460 --> 00:44:47,430
Eso es lineal, seguro.

1101
00:44:47,430 --> 00:44:50,970
Y el tiempo el mejor de los casos en ejecución, o
los límites inferiores en el mejor de los casos

1102
00:44:50,970 --> 00:44:51,975
sería constante de tiempo.

1103
00:44:51,975 --> 00:44:54,600
Porque tal vez tratamos de eliminar
Christine, y acabamos de tener suerte

1104
00:44:54,600 --> 00:44:55,558
ella está en el comienzo.

1105
00:44:55,558 --> 00:44:56,350
Espera un minuto.

1106
00:44:56,350 --> 00:44:59,370
Gabe también era en el principio,
y también tuvimos que actualizar Gabe.

1107
00:44:59,370 --> 00:45:01,150
Así que no era sólo un paso.

1108
00:45:01,150 --> 00:45:04,210
Por lo que es de hecho constante
tiempo, en el mejor de los casos,

1109
00:45:04,210 --> 00:45:06,345
para eliminar el elemento más pequeño?

1110
00:45:06,345 --> 00:45:07,360

1111
00:45:07,360 --> 00:45:10,960
Es, a pesar de que podría ser dos,
tres, o incluso 100 líneas de código,

1112
00:45:10,960 --> 00:45:14,000
si es el mismo número de
líneas, no en un bucle,

1113
00:45:14,000 --> 00:45:16,577
e independiente del tamaño
de la lista, por supuesto.

1114
00:45:16,577 --> 00:45:18,660
Eliminar el elemento en
el principio de la lista,

1115
00:45:18,660 --> 00:45:21,940
incluso si tenemos que hacer frente a
Gabe, todavía estamos a tiempo constante.

1116
00:45:21,940 --> 00:45:24,220
>> Así que esto parece una
enorme paso hacia atrás.

1117
00:45:24,220 --> 00:45:27,000
Y lo que una pérdida de tiempo
si, en la primera semana y la semana

1118
00:45:27,000 --> 00:45:30,250
cero no sólo tuvimos
código pseudocódigo pero el código real

1119
00:45:30,250 --> 00:45:35,780
para poner en práctica algo que es registro
base de n, o ingrese, más bien, de n, base 2,

1120
00:45:35,780 --> 00:45:37,150
en cuanto a su tiempo de ejecución.

1121
00:45:37,150 --> 00:45:40,710
Así que ¿por qué diablos tendría que desee comenzar
usando algo como una lista enlazada?

1122
00:45:40,710 --> 00:45:41,517
Sí.

1123
00:45:41,517 --> 00:45:44,022
>> AUDIENCIA: Así que usted puede añadir
elementos a la matriz.

1124
00:45:44,022 --> 00:45:46,230
DAVID J. MALAN: Así que usted puede
añadir elementos a la matriz.

1125
00:45:46,230 --> 00:45:47,550
Y esto también es temático.

1126
00:45:47,550 --> 00:45:49,740
Y vamos a seguir para ver
esto, esta compensación, mucho

1127
00:45:49,740 --> 00:45:51,573
como hemos visto un
trade-off con merge sort.

1128
00:45:51,573 --> 00:45:54,606
Realmente podríamos acelerar
buscar u ordenar, más bien,

1129
00:45:54,606 --> 00:45:57,480
si nos pasamos un poco más de espacio y
tener un trozo adicional de una memoria

1130
00:45:57,480 --> 00:45:58,760
o una matriz de tipo de combinación.

1131
00:45:58,760 --> 00:46:01,270
Pero gastamos más
espacio, pero nos ahorramos tiempo.

1132
00:46:01,270 --> 00:46:04,820
En este caso, estamos
renunciar a tiempo, pero estamos

1133
00:46:04,820 --> 00:46:08,170
ganar flexibilidad,
dinamismo si se quiere,

1134
00:46:08,170 --> 00:46:10,280
que es sin duda una característica positiva.

1135
00:46:10,280 --> 00:46:11,520
>> También nos estamos gastando el espacio.

1136
00:46:11,520 --> 00:46:13,710
¿En qué sentido es un ligado
enumerar más caro

1137
00:46:13,710 --> 00:46:15,700
en términos de espacio de una matriz?

1138
00:46:15,700 --> 00:46:18,379

1139
00:46:18,379 --> 00:46:19,920
¿Dónde está el espacio extra viene?

1140
00:46:19,920 --> 00:46:20,460
¿Sí?

1141
00:46:20,460 --> 00:46:21,800
>> AUDIENCIA: [inaudible] puntero.

1142
00:46:21,800 --> 00:46:23,310
>> DAVID J. MALAN: Sí,
también tienen el puntero.

1143
00:46:23,310 --> 00:46:25,560
Así que esto es molesto minorly
en que ya no soy

1144
00:46:25,560 --> 00:46:27,780
Yo almacenar sólo un int
para representar un int.

1145
00:46:27,780 --> 00:46:30,990
Estoy almacenando un int y un
puntero, que también es de 32 bits.

1146
00:46:30,990 --> 00:46:33,470
Así que estoy literalmente duplicar
la cantidad de espacio involucrado.

1147
00:46:33,470 --> 00:46:36,040
Así que eso es un trade-off, pero
eso es en el caso de int.

1148
00:46:36,040 --> 00:46:39,580
Supongamos que usted no está almacenando int,
pero supongamos que cada uno de estos rectángulos

1149
00:46:39,580 --> 00:46:43,290
o cada uno de estos seres humanos representaba a
una palabra, una palabra en Inglés que

1150
00:46:43,290 --> 00:46:46,430
podría ser cinco caracteres, 10
personajes, tal vez incluso más.

1151
00:46:46,430 --> 00:46:49,940
Luego de añadir sólo 32 más bits
podría ser menos de gran cosa.

1152
00:46:49,940 --> 00:46:52,160
>> ¿Qué pasaría si cada uno de los estudiantes
en la manifestación

1153
00:46:52,160 --> 00:46:55,107
Estábamos literalmente estructuras estudiantiles que
tienen nombres y casas y tal vez

1154
00:46:55,107 --> 00:46:57,065
números de teléfono y Twitter
mangos y similares.

1155
00:46:57,065 --> 00:46:59,564
Así que todos los campos que empezamos
hablando el otro día,

1156
00:46:59,564 --> 00:47:02,410
mucho menos de un gran problema ya
nuestros nodos se ponen más interesantes

1157
00:47:02,410 --> 00:47:05,972
y grande para gastar, eh, un adicional
indicador acaba de vincular entre sí.

1158
00:47:05,972 --> 00:47:07,180
Pero de hecho, es un trade-off.

1159
00:47:07,180 --> 00:47:09,560
Y, en efecto, el código es
más complejo, ya que tendrás

1160
00:47:09,560 --> 00:47:11,770
ver con una lectura rápida a través
ese ejemplo particular.

1161
00:47:11,770 --> 00:47:14,302
Pero ¿y si hubiera
algún santo grial aquí.

1162
00:47:14,302 --> 00:47:17,010
¿Qué pasa si no tomamos un paso
hacia atrás, pero un gran paso hacia adelante

1163
00:47:17,010 --> 00:47:19,180
e implementar un dato
estructura a través de la cual

1164
00:47:19,180 --> 00:47:22,870
puede encontrar elementos como Jack o
Christine o cualesquiera otros elementos

1165
00:47:22,870 --> 00:47:25,870
en esta matriz en la verdadera constante de tiempo?

1166
00:47:25,870 --> 00:47:26,920
La búsqueda es constante.

1167
00:47:26,920 --> 00:47:28,320
Eliminar es constante.

1168
00:47:28,320 --> 00:47:29,570
Inserte es constante.

1169
00:47:29,570 --> 00:47:32,260
Todas estas operaciones son constantes.

1170
00:47:32,260 --> 00:47:33,750
Ese sería nuestro santo grial.

1171
00:47:33,750 --> 00:47:36,690
Y ahí es donde estamos
recogerá la próxima vez.

1172
00:47:36,690 --> 00:47:38,600
Nos vemos entonces.

1173
00:47:38,600 --> 00:47:39,371