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

2
00:00:00,500 --> 00:00:11,137
[MÚSICA DE XOGO]

3
00:00:11,137 --> 00:00:12,220
DAVID J. Malan: Todo ben.

4
00:00:12,220 --> 00:00:13,950
Este é CS50.

5
00:00:13,950 --> 00:00:18,560
Esta é semana de cinco continuou, e nós
teño unha boa noticia e unha mala noticia.

6
00:00:18,560 --> 00:00:21,140
Entón bo é que CS50
lanza este venres.

7
00:00:21,140 --> 00:00:24,430
Se desexa unirse a nós,
cabeza para o URL de costume aquí.

8
00:00:24,430 --> 00:00:28,670
Unha noticia aínda mellor, ningunha charla
vindeiro luns día 13.

9
00:00:28,670 --> 00:00:31,970
Pouco menos mellor noticia,
cuestionario cero é mércores.

10
00:00:31,970 --> 00:00:33,840
Máis detalles poden ser
atopados neste URL aquí.

11
00:00:33,840 --> 00:00:36,340
E ao longo dos próximos dous días
estaremos cubrindo os espazos en branco

12
00:00:36,340 --> 00:00:39,234
no que se refire aos cuartos
que teremos reservados.

13
00:00:39,234 --> 00:00:41,400
Mellor é que non vou
ser unha revisión de todo o curso

14
00:00:41,400 --> 00:00:43,570
sesión o próximo
Luns pola noite.

15
00:00:43,570 --> 00:00:46,270
Sexa en conta para o curso de
Sitio web para localización e detalles.

16
00:00:46,270 --> 00:00:49,290
Seccións, aínda que sexa un
vacacións, tamén vai atender ben.

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

18
00:00:50,490 --> 00:00:52,940
Mellor noticia, charla na próxima venres.

19
00:00:52,940 --> 00:00:56,220
Polo tanto, esta é unha tradición que
teñen, segundo o contido programático.

20
00:00:56,220 --> 00:00:58,100
Apenas-- que será incrible.

21
00:00:58,100 --> 00:01:02,510
Vai ver cousas como
estruturas de datos de tempo constante

22
00:01:02,510 --> 00:01:04,730
e táboas de hash e árbores e intentos.

23
00:01:04,730 --> 00:01:07,150
E imos falar sobre os problemas de aniversario.

24
00:01:07,150 --> 00:01:09,440
Unha morea de cousas
agarda próxima venres.

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

26
00:01:11,212 --> 00:01:12,200
Está ben.

27
00:01:12,200 --> 00:01:13,190
De calquera forma.

28
00:01:13,190 --> 00:01:17,080
>> Entón lembro que fomos
focando esta imaxe do que está

29
00:01:17,080 --> 00:01:18,980
dentro da memoria do noso ordenador.

30
00:01:18,980 --> 00:01:22,875
Así, a memoria ou a memoria RAM é onde os programas
existir mentres está executando-os.

31
00:01:22,875 --> 00:01:25,215
Se fai clic dúas veces un
icona para realizar algún programa

32
00:01:25,215 --> 00:01:27,520
ou prema dúas veces nun
icona para abrir un arquivo,

33
00:01:27,520 --> 00:01:30,430
el é cargado dende o disco
duro ou unidade de estado sólido

34
00:01:30,430 --> 00:01:34,190
na memoria RAM, Random Access Memory, onde
el vive ata se apagar,

35
00:01:34,190 --> 00:01:36,700
a tapa pecha portátil,
ou saír do programa.

36
00:01:36,700 --> 00:01:38,960
>> Agora que a memoria, de
que probablemente ten

37
00:01:38,960 --> 00:01:41,950
1 gigabyte nos días de hoxe, 2
gigabytes, ou mesmo moito máis,

38
00:01:41,950 --> 00:01:44,420
xeralmente é colocado para fóra
para un determinado programa

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

40
00:01:47,170 --> 00:01:50,860
polo que temos a pila na parte inferior
e unha morea de outras cousas na parte superior.

41
00:01:50,860 --> 00:01:53,140
O superior
vimos nesta imaxe

42
00:01:53,140 --> 00:01:55,670
antes, pero nunca falamos sobre
é o chamado segmento de texto.

43
00:01:55,670 --> 00:01:58,419
Segmento de texto é só un xeito elegante
de dicir os ceros e uns que

44
00:01:58,419 --> 00:02:01,150
compoñer o seu programa compilado real.

45
00:02:01,150 --> 00:02:03,910
>> Entón, cando fai clic dúas veces
Microsoft Word no seu Mac ou PC,

46
00:02:03,910 --> 00:02:08,030
ou ao executar o punto barra Mario nun
Ordenador Linux na súa fiestra de terminal,

47
00:02:08,030 --> 00:02:12,460
os ceros e uns que compoñen
Word ou Mario almacénanse temporalmente

48
00:02:12,460 --> 00:02:16,610
na memoria RAM do seu ordenador na chamada
segmento de texto para un programa particular.

49
00:02:16,610 --> 00:02:19,080
Abaixo diso vai iniciar
e datos non inicializado.

50
00:02:19,080 --> 00:02:22,655
Este é o material como variables globais,
que non usei moitos,

51
00:02:22,655 --> 00:02:24,910
pero de cando en vez temos
tiña as variábeis globais

52
00:02:24,910 --> 00:02:28,819
ou estaticamente cordas definido que
é codificado palabras como "Ola"

53
00:02:28,819 --> 00:02:31,860
que non son tidos en do usuario
que son codificados no seu programa.

54
00:02:31,860 --> 00:02:34,230
>> Agora, para abaixo na parte inferior nós
ter a pila de chamada.

55
00:02:34,230 --> 00:02:37,665
E a pila, ata agora, temos sido
usando para que tipo de efectos?

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

57
00:02:39,706 --> 00:02:40,997
Que a pila foi utilizado?

58
00:02:40,997 --> 00:02:41,160
Si?

59
00:02:41,160 --> 00:02:42,070
>> Audiencia: Funcións.

60
00:02:42,070 --> 00:02:43,320
>> DAVID J. Malan: Para funcións?

61
00:02:43,320 --> 00:02:44,980
En que sentido para as funcións?

62
00:02:44,980 --> 00:02:48,660
>> Audiencia: Cando chamar unha función, o
argumentos son copiados para a pila.

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

64
00:02:49,660 --> 00:02:52,650
Cando chama unha función, a
argumentos son copiados para a pila.

65
00:02:52,650 --> 00:02:56,330
Así, calquera Xs ou Y do ou dun ou B
que está pasando a unha función

66
00:02:56,330 --> 00:02:58,680
son temporalmente colocados en
a pila así chamado,

67
00:02:58,680 --> 00:03:02,000
só como un dos Annenberg
bandexas salón-comedor, e tamén as cousas

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

69
00:03:03,190 --> 00:03:06,290
Se a súa función foo ou a súa cambio
función de variables locais,

70
00:03:06,290 --> 00:03:08,602
como temperatura, estes dous
acabar na pila.

71
00:03:08,602 --> 00:03:11,560
Agora, non imos falar moito sobre
eles, pero estas variables de ambiente

72
00:03:11,560 --> 00:03:15,690
na parte inferior que vimos hai un tempo atrás, cando
Estaba mexendo no teclado dun día

73
00:03:15,690 --> 00:03:20,050
e comece a acceder cousas
argv como 100 ou argv 1000,

74
00:03:20,050 --> 00:03:22,320
só elements-- eu esquezo
Números de a, pero que

75
00:03:22,320 --> 00:03:24,330
Non era para acceder por min.

76
00:03:24,330 --> 00:03:26,581
Comezamos a ver algúns
símbolos funk na pantalla.

77
00:03:26,581 --> 00:03:28,330
Aqueles eran chamados
variables de ambiente

78
00:03:28,330 --> 00:03:32,390
como opcións globais para o meu
programa ou para o meu ordenador, non

79
00:03:32,390 --> 00:03:37,090
sen relación coa recente
erro que discutir,

80
00:03:37,090 --> 00:03:39,670
Shellshock, que foi
asola moi poucos ordenadores.

81
00:03:39,670 --> 00:03:42,960
>> Agora, para rematar, en foco de hoxe
que en definitiva será na pila.

82
00:03:42,960 --> 00:03:44,864
Este é un anaco de memoria.

83
00:03:44,864 --> 00:03:47,030
E todo isto fundamentalmente
memoria é o mesmo.

84
00:03:47,030 --> 00:03:48,040
É o mesmo hardware.

85
00:03:48,040 --> 00:03:49,956
Somos só unha especie de
tratamento de distintos grupos

86
00:03:49,956 --> 00:03:51,460
de bytes para distintos fins.

87
00:03:51,460 --> 00:03:56,540
A pila tamén será onde
variables e memoria que solicitar

88
00:03:56,540 --> 00:03:58,810
desde o sistema operativo
é temporalmente almacenado.

89
00:03:58,810 --> 00:04:01,890
>> Pero hai un tipo de problema
aquí, como a foto indica.

90
00:04:01,890 --> 00:04:05,261
Nós medio que temos dous
barcos a piques de chocar.

91
00:04:05,261 --> 00:04:08,010
Porque, como se usa cada vez máis
do conxunto, e como vemos hoxe

92
00:04:08,010 --> 00:04:11,800
para adiante, como se usa cada vez máis a
pila, seguramente as cousas malas poden ocorrer.

93
00:04:11,800 --> 00:04:15,054
E, de feito, podemos inducir que
intencionalmente ou non.

94
00:04:15,054 --> 00:04:16,970
Así, o suspense última
tempo era ese programa,

95
00:04:16,970 --> 00:04:20,570
que non serven calquera funcional
outro propósito ademais de demostrar

96
00:04:20,570 --> 00:04:24,750
como como un cara mal realmente pode ter
vantaxe de erros no programa de alguén

97
00:04:24,750 --> 00:04:28,460
e asumir un programa ou un
sistema informático ou servidor de todo.

98
00:04:28,460 --> 00:04:31,660
Entón, só para ollar brevemente, ten
ter en conta que o principal na parte inferior

99
00:04:31,660 --> 00:04:34,510
toma en liña de comandos
argumentos, por argv.

100
00:04:34,510 --> 00:04:38,480
E ten unha chamada a unha función f,
esencialmente unha función de chamada sen nome

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

102
00:04:40,250 --> 00:04:43,960
>> Entón, calquera palabra que o usuario escribe en polo
a solicitude despois do nome deste programa,

103
00:04:43,960 --> 00:04:49,310
e pode que a función arbitraria up
top, f, leva nunha corda, aka char *,

104
00:04:49,310 --> 00:04:51,720
como comezamos a discutir,
e el simplemente chama de "bar".

105
00:04:51,720 --> 00:04:53,310
Pero poderiamos chamalo nada.

106
00:04:53,310 --> 00:04:57,470
E entón el declara, dentro
de f, unha serie de caracteres

107
00:04:57,470 --> 00:04:59,930
chamado C-- 12 destes personaxes.

108
00:04:59,930 --> 00:05:03,580
>> Agora, pola historia que eu estaba dicindo
un momento atrás, onde na memoria

109
00:05:03,580 --> 00:05:06,720
c é, ou son aqueles 12
PERSONAXES vai acabar?

110
00:05:06,720 --> 00:05:07,570
Só queda claro.

111
00:05:07,570 --> 00:05:08,070
Si?

112
00:05:08,070 --> 00:05:08,590
>> Audiencia: Na pila.

113
00:05:08,590 --> 00:05:09,420
>> DAVID J. Malan: Na pila.

114
00:05:09,420 --> 00:05:10,720
Así, c é unha variable local.

115
00:05:10,720 --> 00:05:14,079
Estamos pedindo para 12 caracteres ou 12 bytes.

116
00:05:14,079 --> 00:05:16,120
Aqueles van acabar
na pila de chamadas.

117
00:05:16,120 --> 00:05:18,530
Agora, por fin, se esta outra función
que é realmente moi útil,

118
00:05:18,530 --> 00:05:20,571
pero non usei moito
nós mesmos, strncopy.

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

120
00:05:21,550 --> 00:05:25,200
Significa copia corda, pero
só n letras, n caracteres.

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

122
00:05:31,990 --> 00:05:32,980
E cantos?

123
00:05:32,980 --> 00:05:34,110
A lonxitude da barra.

124
00:05:34,110 --> 00:05:36,330
Así, noutras palabras, que
unha liña, strncopy,

125
00:05:36,330 --> 00:05:39,500
vai copiar
efectivamente bar no c.

126
00:05:39,500 --> 00:05:42,340
>> Agora, só a especie de anticipar
A moral desta historia,

127
00:05:42,340 --> 00:05:44,750
o que é potencialmente problemático aquí?

128
00:05:44,750 --> 00:05:49,710
Aínda que estamos comprobando a lonxitude
de bar e pasala en strncopy,

129
00:05:49,710 --> 00:05:53,145
o que é o seu intestino dicindo é
aínda roto sobre este programa?

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

131
00:05:54,410 --> 00:05:55,220
Si?

132
00:05:55,220 --> 00:05:57,491
>> Audiencia: Non inclúe
espazo para o carácter nulo.

133
00:05:57,491 --> 00:05:59,990
DAVID J. Malan: Non inclúe
espazo para o carácter nulo.

134
00:05:59,990 --> 00:06:02,073
Potencialmente, a diferenza de
as prácticas do pasado que nin sequera

135
00:06:02,073 --> 00:06:04,810
ten tanto como unha vantaxe de 1 a
acomodar ese carácter nulo.

136
00:06:04,810 --> 00:06:06,649
Pero é aínda peor que iso.

137
00:06:06,649 --> 00:06:07,940
Que máis estamos deixando de facer?

138
00:06:07,940 --> 00:06:08,432
Si?

139
00:06:08,432 --> 00:06:09,307
>> Audiencia: [inaudível]

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

141
00:06:15,440 --> 00:06:16,440
DAVID J. Malan: Perfecto.

142
00:06:16,440 --> 00:06:18,490
Nós codificado 12 moi arbitrariamente.

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

144
00:06:19,497 --> 00:06:21,330
Isto non é tanto a
problema, pero o feito

145
00:06:21,330 --> 00:06:25,630
que non estamos aínda comprobando se
a lonxitude da barra é menos que 12,

146
00:06:25,630 --> 00:06:28,530
caso en que será
seguro para poñelas na memoria

147
00:06:28,530 --> 00:06:30,260
chamada c que temos asignado.

148
00:06:30,260 --> 00:06:32,960
Efectivamente, se a barra é así
20 caracteres,

149
00:06:32,960 --> 00:06:39,010
esta función parece estar copiando
20 personaxes de bar en c, así,

150
00:06:39,010 --> 00:06:41,310
tendo, polo menos, 8 bytes
que non deben ser.

151
00:06:41,310 --> 00:06:42,690
Esta é a implicación aquí.

152
00:06:42,690 --> 00:06:44,347
>> Así, no programa curto, roto.

153
00:06:44,347 --> 00:06:45,180
Non como un gran negocio.

154
00:06:45,180 --> 00:06:46,360
Quizais comeza un fallo de segmento.

155
00:06:46,360 --> 00:06:47,651
Todos nós xa tivemos erros nos programas.

156
00:06:47,651 --> 00:06:50,196
Todos nós pode ter erros
en programas de agora.

157
00:06:50,196 --> 00:06:51,320
Pero cal é a implicación?

158
00:06:51,320 --> 00:06:54,390
Ben, aquí está unha versión máis grande-in de
que imaxe de memoria do meu ordenador.

159
00:06:54,390 --> 00:06:56,230
Este é o fondo do meu stack.

160
00:06:56,230 --> 00:06:59,644
E, de feito, ben no fondo é o que se
chamado pila rutina pai, forma extravagante

161
00:06:59,644 --> 00:07:00,560
de dicir que é principal.

162
00:07:00,560 --> 00:07:03,772
Así que quen chamou a función
f que estamos a falar.

163
00:07:03,772 --> 00:07:05,230
Así, este é o fondo da pila.

164
00:07:05,230 --> 00:07:06,640
Enderezo de retorno é algo novo.

165
00:07:06,640 --> 00:07:08,810
El sempre estivo alí,
sempre estiven nesa imaxe.

166
00:07:08,810 --> 00:07:10,440
Nós só nunca chamou atención a el.

167
00:07:10,440 --> 00:07:15,290
Porque sucede o camiño c funciona é
que cando unha función chama outra,

168
00:07:15,290 --> 00:07:18,780
non só os argumentos para que
función son empurrados para a pila,

169
00:07:18,780 --> 00:07:22,470
non só local de función
variables son empurrados para a pila,

170
00:07:22,470 --> 00:07:26,820
algo chamado un enderezo de retorno
tamén é colocado na pila.

171
00:07:26,820 --> 00:07:33,330
En concreto, as chamadas principais Foo, principais do
propio enderezo en memoria, algo boi,

172
00:07:33,330 --> 00:07:38,240
efectivamente colócase na pila
de xeito que, cando f está feito de executa-lo

173
00:07:38,240 --> 00:07:43,630
sabe onde saltar de volta no texto
segmento, a fin de continuar a execución.

174
00:07:43,630 --> 00:07:47,760
>> Entón, se estamos aquí, conceptualmente,
na principal, entón f é chamada.

175
00:07:47,760 --> 00:07:50,200
Como f saber quen
para control de man de volta?

176
00:07:50,200 --> 00:07:52,020
Ben, este pequeno
breadcrumb en vermello aquí,

177
00:07:52,020 --> 00:07:54,978
chamado a dirección de retorno, el só
cheques, que é o que a dirección de retorno?

178
00:07:54,978 --> 00:07:57,039
Oh, déixeme ir de volta a principal aquí.

179
00:07:57,039 --> 00:07:59,080
E iso é algo
dunha simplificación,

180
00:07:59,080 --> 00:08:00,750
porque os ceros e uns
para principal son tecnicamente

181
00:08:00,750 --> 00:08:01,967
aquí enriba no segmento de tecnoloxía.

182
00:08:01,967 --> 00:08:03,800
Pero esa é a idea. f
só ten que saber o que

183
00:08:03,800 --> 00:08:06,680
en definitiva, no que o control de volta.

184
00:08:06,680 --> 00:08:09,790
>> Pero o xeito no que os ordenadores
Hai moito tempo establecidas as cousas

185
00:08:09,790 --> 00:08:12,320
como variables locais e
argumentos é así.

186
00:08:12,320 --> 00:08:17,180
Así, na parte superior da imaxe en
azul é o cadro de pila para f, entón todo

187
00:08:17,180 --> 00:08:19,630
da memoria que f
especialmente se emprega.

188
00:08:19,630 --> 00:08:22,990
Entón, nese sentido, entender que
bar é neste marco.

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

190
00:08:23,980 --> 00:08:27,240
E defendeu que os argumentos para
funcións son empurrados para a pila.

191
00:08:27,240 --> 00:08:29,910
E c, por suposto, é
Tamén nesta foto.

192
00:08:29,910 --> 00:08:33,520
>> E só para fins de notación,
conta na esquina superior esquerda

193
00:08:33,520 --> 00:08:37,020
é o que sería c soporte 0 e
entón lixeiramente abaixo á dereita

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

195
00:08:38,220 --> 00:08:41,240
Polo tanto, noutras palabras, pode imaxinar
que hai unha reixa de bytes

196
00:08:41,240 --> 00:08:44,380
hai, en primeiro lugar, que é
superior esquerda, abaixo do que

197
00:08:44,380 --> 00:08:48,360
é o último dos 12 bytes.

198
00:08:48,360 --> 00:08:49,930
>> Pero agora tentar avanzar.

199
00:08:49,930 --> 00:08:55,580
O que está a ocorrer se pasarmos
nun bar de cadea que é máis que c?

200
00:08:55,580 --> 00:08:59,130
E non estamos comprobando se
é de feito maior que 12.

201
00:08:59,130 --> 00:09:03,146
Cal parte da imaxe vai
se substituído por bytes 0, 1, 2, 3,

202
00:09:03,146 --> 00:09:07,890
dot dot dot, 11, e, a continuación,
malo, 12, 13 a 19?

203
00:09:07,890 --> 00:09:11,820
O que vai ocorrer aquí,
inferir a partir da ordenación

204
00:09:11,820 --> 00:09:14,790
que c 0 soporte está na parte superior
ec soporte 11 é unha especie de abaixo

205
00:09:14,790 --> 00:09:15,812
á dereita?

206
00:09:15,812 --> 00:09:16,796
Si?

207
00:09:16,796 --> 00:09:19,260
>> Audiencia: Ben, que vai
para substituír o bar char *.

208
00:09:19,260 --> 00:09:22,260
>> DAVID J. Malan: Si, parece que
está indo a substituír carbón bar *.

209
00:09:22,260 --> 00:09:26,245
E peor, se publique nun tempo moi longo
cadea, pode ata substituír o que?

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

211
00:09:27,460 --> 00:09:28,570
O enderezo de retorno.

212
00:09:28,570 --> 00:09:31,380
Que unha vez máis, é como un
breadcrumb para dicir ao programa onde

213
00:09:31,380 --> 00:09:34,060
volver cando f
está feito de ser chamado.

214
00:09:34,060 --> 00:09:37,140
>> Entón, o que bandas adoitan facer
é se atopou con un programa

215
00:09:37,140 --> 00:09:41,290
que son curiosos se é
explorável, cesta, de tal xeito

216
00:09:41,290 --> 00:09:43,550
que el ou ela pode tomar
vantaxe deste erro,

217
00:09:43,550 --> 00:09:45,720
xeralmente non reciben
este dereito por primeira vez.

218
00:09:45,720 --> 00:09:48,590
Eles só comezar a enviar, por exemplo,
secuencias aleatorias no seu programa,

219
00:09:48,590 --> 00:09:50,260
no teclado,
ou, francamente probablemente

220
00:09:50,260 --> 00:09:52,740
escribir un pequeno programa para só
xerar automaticamente cordas,

221
00:09:52,740 --> 00:09:55,430
e comezar a bater o seu programa
o envío de lotes de entradas diferentes

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

223
00:09:56,340 --> 00:09:58,990
>> Así que os seus fallos do programa,
iso é unha cousa incrible.

224
00:09:58,990 --> 00:10:01,020
Porque isto significa que el
ou ela descubriu

225
00:10:01,020 --> 00:10:02,660
o que probablemente é de feito un erro.

226
00:10:02,660 --> 00:10:05,830
E entón poden ser máis intelixente
e comezar a concentrarse máis estreitamente

227
00:10:05,830 --> 00:10:07,420
sobre o xeito de explotar ese erro.

228
00:10:07,420 --> 00:10:11,480
En particular, o que el ou ela pode
facer é enviar, no mellor dos casos, Ola.

229
00:10:11,480 --> 00:10:12,210
Non é gran cousa.

230
00:10:12,210 --> 00:10:14,750
É unha cadea que é suficientemente curto.

231
00:10:14,750 --> 00:10:18,100
Pero e se el ou ela envía,
e imos xeneralizar-lo como,

232
00:10:18,100 --> 00:10:20,890
ataque code-- tan ceros
e os que fan as cousas

233
00:10:20,890 --> 00:10:25,150
rm-rf como, que elimina todo
dende o disco duro ou enviar spam

234
00:10:25,150 --> 00:10:27,000
ou de algunha maneira a atacar máquina?

235
00:10:27,000 --> 00:10:29,570
>> Por iso, cada unha delas
letras A só representa,

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

237
00:10:32,380 --> 00:10:36,410
que alguén escribiu, pero
se esa persoa é intelixente dabondo

238
00:10:36,410 --> 00:10:40,790
non só para incluír todos
destes rm-RFS, pero tamén

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

240
00:10:46,100 --> 00:10:50,540
ao enderezo do seu
ou o seu propio código de ataque

241
00:10:50,540 --> 00:10:53,820
que el ou ela pasou en só
, Dando-lle o poder,

242
00:10:53,820 --> 00:10:58,760
pode efectivamente enganar o ordenador
para entender cando f faise en execución,

243
00:10:58,760 --> 00:11:02,400
Oh, é hora de eu ir
de volta ao enderezo do remitente vermella.

244
00:11:02,400 --> 00:11:06,070
Pero por que el ou ela ten de algunha maneira
sobrepostas que a dirección de retorno

245
00:11:06,070 --> 00:11:09,602
co seu propio número,
e son intelixentes abondo

246
00:11:09,602 --> 00:11:11,560
configurar que
número para referirse, como

247
00:11:11,560 --> 00:11:13,740
ver no super top
esquina esquerda alí,

248
00:11:13,740 --> 00:11:18,020
a dirección real no ordenador de
memoria de parte do seu código de ataque,

249
00:11:18,020 --> 00:11:21,740
un bandido pode enganar o ordenador
para realizar o seu propio código.

250
00:11:21,740 --> 00:11:23,700
>> E ese código, unha vez máis, pode ser calquera cousa.

251
00:11:23,700 --> 00:11:26,120
É xeralmente chamado
código shell, que é só

252
00:11:26,120 --> 00:11:29,030
unha forma de dicir que non é
xeralmente algo tan simple como rm-rf.

253
00:11:29,030 --> 00:11:32,340
Realmente algo como Bash,
ou un programa real que lle dá

254
00:11:32,340 --> 00:11:37,230
ou o seu control programático para realizar
calquera outra cousa que eles queren.

255
00:11:37,230 --> 00:11:40,210
Entón, en definitiva, todo isto
deriva do simple feito

256
00:11:40,210 --> 00:11:44,490
que este erro non implica a comprobación
os límites da súa matriz.

257
00:11:44,490 --> 00:11:47,250
E por que o camiño
ordenadores de traballo é que

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

259
00:11:49,430 --> 00:11:54,830
inferior enriba, pero, a continuación, os elementos
empurrar para a pila crecer de arriba abaixo,

260
00:11:54,830 --> 00:11:56,624
iso é moi problemático.

261
00:11:56,624 --> 00:11:58,290
Agora, hai formas de evitar isto.

262
00:11:58,290 --> 00:12:00,800
E, francamente, hai linguas
coa que traballar en torno a este.

263
00:12:00,800 --> 00:12:03,100
Java é inmune, por exemplo,
a esta cuestión particular.

264
00:12:03,100 --> 00:12:04,110
¿Por que non darlle indicacións.

265
00:12:04,110 --> 00:12:05,943
Eles non dan a vostede
enderezos de memoria directas.

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

267
00:12:08,560 --> 00:12:11,580
que queremos vén, en realidade, un gran risco.

268
00:12:11,580 --> 00:12:12,430
>> Polo tanto, manter un ollo para fóra.

269
00:12:12,430 --> 00:12:14,596
Se, a verdade, nos meses
ou anos, a calquera hora

270
00:12:14,596 --> 00:12:17,740
ler sobre algunha explotación
dun programa ou dun servidor,

271
00:12:17,740 --> 00:12:22,370
se xa viu un toque de algo
como un ataque de estourido de buffer,

272
00:12:22,370 --> 00:12:25,390
ou estourido de pila é outro tipo
de ataque, semellante en espírito,

273
00:12:25,390 --> 00:12:28,770
tanto como inspira o sitio web da
nome, se sabe diso,

274
00:12:28,770 --> 00:12:33,170
todo está falando só
rebordando o tamaño dalgún personaxe

275
00:12:33,170 --> 00:12:36,200
matriz ou matriz dalgún modo máis xeral.

276
00:12:36,200 --> 00:12:38,822
Todas as preguntas, entón, sobre este asunto?

277
00:12:38,822 --> 00:12:39,780
Non intente facer iso na casa.

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

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

280
00:12:42,300 --> 00:12:47,270
Entón malloc, ata agora, foi o noso novo
amigo no que podemos reservar memoria

281
00:12:47,270 --> 00:12:50,540
que non saben necesariamente en
avanzar que queremos de xeito que non temos

282
00:12:50,540 --> 00:12:52,920
código ríxido na nosa
Os números de programas como 12.

283
00:12:52,920 --> 00:12:55,550
Unha vez que o usuario nos di o que
datos que el ou ela quere de entrada,

284
00:12:55,550 --> 00:12:58,000
podemos malloc que moita memoria.

285
00:12:58,000 --> 00:13:01,484
>> Entón malloc se ve, ao
medida en que temos que chegou a utilizar,

286
00:13:01,484 --> 00:13:03,900
explicitamente última vez, e logo
vostedes teñen usado

287
00:13:03,900 --> 00:13:08,160
para GetString sen saber para
varias semanas, todos a memoria do malloc

288
00:13:08,160 --> 00:13:09,820
vén o chamado chea.

289
00:13:09,820 --> 00:13:13,852
E é por iso getString, por exemplo,
pode reservar memoria dinámica

290
00:13:13,852 --> 00:13:16,060
sen saber o que está a
vai escribir con antelación,

291
00:13:16,060 --> 00:13:21,520
entrega-lo de volta un punteiro para a memoria,
e que a memoria aínda é o seu para manter,

292
00:13:21,520 --> 00:13:24,080
mesmo despois getString retorna.

293
00:13:24,080 --> 00:13:27,450
Como recordo despois de todo o que o
pila está constantemente indo para arriba e abaixo,

294
00:13:27,450 --> 00:13:27,950
arriba e abaixo.

295
00:13:27,950 --> 00:13:30,230
E así que vai
abaixo, isto significa que calquera memoria

296
00:13:30,230 --> 00:13:33,030
Esta función debe
non ser usado por calquera persoa.

297
00:13:33,030 --> 00:13:34,570
É valores de lixo agora.

298
00:13:34,570 --> 00:13:36,120
>> Pero a pila está aquí enriba.

299
00:13:36,120 --> 00:13:39,360
E o que é agradable sobre malloc é que
cando malloc aloca memoria ata aquí,

300
00:13:39,360 --> 00:13:42,070
non é afectado, pois o
maior parte dos casos, por a pila.

301
00:13:42,070 --> 00:13:46,000
E así calquera función pode acceder
memoria que foi malloc'd,

302
00:13:46,000 --> 00:13:49,120
incluso por unha función como getString,
mesmo despois de ser devoltos.

303
00:13:49,120 --> 00:13:51,700
>> Agora, o inverso do malloc é gratuíto.

304
00:13:51,700 --> 00:13:53,900
E, de feito, a regra que
Debe comezar a adoptar

305
00:13:53,900 --> 00:13:58,950
é calquera, calquera, calquera hora que usar malloc
pode usar-se libre, finalmente,

306
00:13:58,950 --> 00:14:00,280
o mesmo punteiro.

307
00:14:00,280 --> 00:14:03,289
Todo este tempo que vimos escribir
erros, código de buggy, por moitas razóns.

308
00:14:03,289 --> 00:14:05,580
Pero un dos cales foi
a través da biblioteca de CS50, que

309
00:14:05,580 --> 00:14:09,010
en si é deliberadamente
Buggy, que perdas de memoria.

310
00:14:09,010 --> 00:14:11,410
Cada vez que chamou getString
ao longo das últimas semanas

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

312
00:14:13,870 --> 00:14:15,780
E nunca xa dado de volta.

313
00:14:15,780 --> 00:14:17,730
E iso non é, en
practicar, bo.

314
00:14:17,730 --> 00:14:20,330
>> E Valgrind, unha das
ferramentas introducidas no Pset 4,

315
00:14:20,330 --> 00:14:22,900
é todo a axudar
agora atopar erros coma este.

316
00:14:22,900 --> 00:14:27,060
Pero, por sorte para Pset 4 non necesita
para usar a biblioteca CS50 ou getString.

317
00:14:27,060 --> 00:14:31,220
Así, os erros relacionados coa memoria son
en definitiva, será o seu propio.

318
00:14:31,220 --> 00:14:34,060
>> Entón malloc é máis que
conveniente para este propósito.

319
00:14:34,060 --> 00:14:37,420
De feito, podemos agora resolver
fundamentalmente diferentes problemas,

320
00:14:37,420 --> 00:14:41,640
e, fundamentalmente, resolver problemas máis
eficaz como promesa á semana ceros.

321
00:14:41,640 --> 00:14:44,720
Ata agora, esta é a máis sexy
estrutura de datos que tivemos.

322
00:14:44,720 --> 00:14:47,804
E por estrutura de datos Eu só quero dicir
unha forma de memoria conceituar

323
00:14:47,804 --> 00:14:50,720
dunha forma que vai alén de só dicir:
este é un enteiro, este é un caracter.

324
00:14:50,720 --> 00:14:52,930
Podemos comezar coas cousas de cluster xuntos.

325
00:14:52,930 --> 00:14:54,460
>> Así, un conxunto coma este.

326
00:14:54,460 --> 00:14:57,270
E o que foi fundamental en aproximadamente unha
matriz é que lle dá

327
00:14:57,270 --> 00:14:59,724
back-to-back anacos de
memoria, cada unha das cales

328
00:14:59,724 --> 00:15:02,765
será do mesmo tipo, int
int, int, int ou char, char, char,

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

330
00:15:03,330 --> 00:15:04,496
Pero hai algunhas desvantaxes.

331
00:15:04,496 --> 00:15:06,570
Este, por exemplo, é
unha matriz de tamaño seis.

332
00:15:06,570 --> 00:15:10,650
Supoña que enche esa matriz con seis
números e, a continuación, por calquera motivo,

333
00:15:10,650 --> 00:15:13,187
o usuario quere dar
vostede un sétimo número.

334
00:15:13,187 --> 00:15:14,020
Onde puxo?

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

336
00:15:15,490 --> 00:15:18,990
>> Cal é a solución se ten
creada unha matriz sobre a pila,

337
00:15:18,990 --> 00:15:22,030
por exemplo, só coa semana
dous notación que introducimos,

338
00:15:22,030 --> 00:15:23,730
de corchetes cun número dentro?

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

340
00:15:25,160 --> 00:15:27,260
Ben, ten seis
números nestas caixas.

341
00:15:27,260 --> 00:15:28,530
Que os seus instintos ser?

342
00:15:28,530 --> 00:15:29,973
Onde quere poñelas?

343
00:15:29,973 --> 00:15:30,860
>> Audiencia: [inaudível]

344
00:15:30,860 --> 00:15:31,315
>> DAVID J. Malan: Sentímolo?

345
00:15:31,315 --> 00:15:32,380
>> Audiencia: Pon-o ao final.

346
00:15:32,380 --> 00:15:33,796
>> DAVID J. Malan: Pon-o ao final.

347
00:15:33,796 --> 00:15:35,880
Entón, só para a dereita,
fóra da caixa.

348
00:15:35,880 --> 00:15:38,710
O que sería bo, pero
Acontece que non pode facelo.

349
00:15:38,710 --> 00:15:41,350
Porque se non pediu
a este anaco de memoria,

350
00:15:41,350 --> 00:15:44,490
podería ser casualidade que este
está sendo usado por outra variable

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

352
00:15:45,030 --> 00:15:49,210
Debería de volta unha semana ou así cando poñemos
os nomes de Zamyla e Davin e Gabe

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

354
00:15:49,930 --> 00:15:51,638
Estaban literalmente
back to back to back.

355
00:15:51,638 --> 00:15:53,550
Polo tanto, non podemos necesariamente
confiar que todo de

356
00:15:53,550 --> 00:15:55,800
aquí está dispoñible para eu usar.

357
00:15:55,800 --> 00:15:56,990
>> Entón o que máis pode facer?

358
00:15:56,990 --> 00:16:00,282
Ben, xa que entender
precisa dunha matriz de tamaño sete,

359
00:16:00,282 --> 00:16:02,490
pode simplemente crear un
matriz de tamaño sete entón usar

360
00:16:02,490 --> 00:16:05,950
un loop ou un loop while,
copia-lo para o novo matriz,

361
00:16:05,950 --> 00:16:09,680
e, a continuación, dalgún xeito, se librar de
esa matriz ou simplemente deixar de usalo.

362
00:16:09,680 --> 00:16:12,130
Pero iso non é especialmente eficiente.

363
00:16:12,130 --> 00:16:15,340
En suma, as matrices non deixe
redimensionar dinamicamente.

364
00:16:15,340 --> 00:16:17,900
>> Así, por unha banda, obtén
de acceso aleatorio, que é incrible.

365
00:16:17,900 --> 00:16:20,108
Porque nos permite facer cousas
como dividir e conquistar,

366
00:16:20,108 --> 00:16:23,100
busca binaria, todos os cales temos
falou na pantalla aquí.

367
00:16:23,100 --> 00:16:24,950
Pero pintar só nun canto.

368
00:16:24,950 --> 00:16:27,810
Así que acertar
o fin da súa matriz,

369
00:16:27,810 --> 00:16:29,980
ten que facer unha moi
operación dispendiosa

370
00:16:29,980 --> 00:16:33,910
ou escribir unha morea de código
agora xestionar este problema.

371
00:16:33,910 --> 00:16:36,680
>> Entón, o que se no canto tivemos
algo chamado unha lista,

372
00:16:36,680 --> 00:16:38,820
ou unha lista ligada en particular?

373
00:16:38,820 --> 00:16:41,930
E se en vez de ter
rectángulos volta atrás cara atrás,

374
00:16:41,930 --> 00:16:45,730
temos rectángulos que deixan un pouco
pouco espazo de manobra entre eles?

375
00:16:45,730 --> 00:16:49,670
E aínda que eu deseño este
foto ou adaptado esta foto

376
00:16:49,670 --> 00:16:54,696
dende un dos textos aquí para volver ao
volta atrás moi ordenada, en realidade,

377
00:16:54,696 --> 00:16:56,820
un deses rectángulos
podería estar aquí na memoria.

378
00:16:56,820 --> 00:16:58,028
Un deles podería ser ata aquí.

379
00:16:58,028 --> 00:17:00,420
Un deles podería ser ata aquí,
aquí, e así por diante.

380
00:17:00,420 --> 00:17:02,910
>> Pero o que se chamou,
neste caso, frechas

381
00:17:02,910 --> 00:17:05,650
que dalgún xeito vincular estes
rectángulos xuntos?

382
00:17:05,650 --> 00:17:08,170
De feito, vimos un técnico
encarnación dunha frecha.

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

384
00:17:09,839 --> 00:17:13,710
O que temos usado nos últimos anos
días que, debaixo do capó,

385
00:17:13,710 --> 00:17:15,210
é representativa dunha frecha?

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

387
00:17:16,290 --> 00:17:17,349
Un punteiro, non?

388
00:17:17,349 --> 00:17:19,780
>> Entón, o que se, no canto de
só almacenar os números,

389
00:17:19,780 --> 00:17:23,130
como 9, 17, 22, 26, 34,
E se nós non gardados

390
00:17:23,130 --> 00:17:27,079
só un número, pero un enlace
xunto a cada número tal?

391
00:17:27,079 --> 00:17:30,690
Entón, que así como enfiar unha
agulla través de unha chea de tecido,

392
00:17:30,690 --> 00:17:32,950
cousas de algunha maneira de subordinación
en conxunto, de xeito semellante pode

393
00:17:32,950 --> 00:17:35,550
nós con punteiros, como
encarnado por frechas aquí,

394
00:17:35,550 --> 00:17:38,550
tipo de tecer
deses rectángulos individuais

395
00:17:38,550 --> 00:17:41,780
por efectivamente usando un punteiro
xunto a cada número que

396
00:17:41,780 --> 00:17:46,065
apunta para algún número seguinte, que
indica, á súa vez, algúns próximo número?

397
00:17:46,065 --> 00:17:47,940
Polo tanto, noutras palabras, o que
se realmente quería

398
00:17:47,940 --> 00:17:49,820
para aplicar algo coma isto?

399
00:17:49,820 --> 00:17:53,610
Ben, sentímolo, estes rectángulos,
, Polo menos, un con 9, 17, 22,

400
00:17:53,610 --> 00:17:57,040
e así por diante, estes non son máis
prazas agradables con números individuais.

401
00:17:57,040 --> 00:17:59,960
O fondo, rectángulo
por baixo de 9, por exemplo,

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

403
00:18:04,330 --> 00:18:09,460
Agora, eu non estou ao tanto de calquera tipo de datos
en C que lle dá non só un int

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

405
00:18:11,630 --> 00:18:15,020
>> Entón, cal é a solución, se quere
inventar a nosa propia resposta a iso?

406
00:18:15,020 --> 00:18:15,760
Si?

407
00:18:15,760 --> 00:18:16,640
>> Audiencia: [inaudível]

408
00:18:16,640 --> 00:18:17,360
>> DAVID J. Malan: ¿Que é iso?

409
00:18:17,360 --> 00:18:17,880
>> Audiencia: Nova estrutura.

410
00:18:17,880 --> 00:18:19,590
>> DAVID J. Malan: Si, entón por que
Non podemos crear unha nova estrutura,

411
00:18:19,590 --> 00:18:20,920
ou en C, un struct?

412
00:18:20,920 --> 00:18:25,990
Vimos estruturas antes, brevemente,
onde lidamos cunha estrutura de estudante

413
00:18:25,990 --> 00:18:27,780
como este, que tiña un nome e unha casa.

414
00:18:27,780 --> 00:18:31,980
En Pset 3 fuga usou un todo
banda de GRect structs-- e GOvals

415
00:18:31,980 --> 00:18:34,810
Stanford que creou a
información de cluster xuntos.

416
00:18:34,810 --> 00:18:38,580
Entón, o que se tomamos esa mesma idea de
as palabras clave "typedef" e "struct"

417
00:18:38,580 --> 00:18:42,890
e, a continuación, algunhas cousas específicas do alumno,
e evolucionar esta no seguinte:

418
00:18:42,890 --> 00:18:46,210
typedef struct node-- e nodo é
só unha ciencia da computación moi xenérico

419
00:18:46,210 --> 00:18:49,980
prazo para algo nunha estrutura de datos,
un recipiente, dunha estrutura de datos.

420
00:18:49,980 --> 00:18:53,900
Un nó Eu reivindico terá
un int n, totalmente simple,

421
00:18:53,900 --> 00:18:58,810
e, a continuación, un pouco máis enigmaticamente,
Nesta segunda liña, nó struct * próximo.

422
00:18:58,810 --> 00:19:01,300
Pero, en termos menos técnicos,
que é o que a segunda liña

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

424
00:19:02,980 --> 00:19:03,737
Si?

425
00:19:03,737 --> 00:19:04,851
>> Audiencia: [inaudível]

426
00:19:04,851 --> 00:19:06,600
David J. Malan: Un
punteiro a outro nodo.

427
00:19:06,600 --> 00:19:09,910
Entón, en realidade, sintaxe algo enigmática.

428
00:19:09,910 --> 00:19:13,250
Pero se le-lo, literalmente,
logo é o nome dunha variable.

429
00:19:13,250 --> 00:19:14,410
Cal é o seu tipo de datos?

430
00:19:14,410 --> 00:19:18,206
É un pouco prolixo, esta vez,
pero é o tipo de nodo struct *.

431
00:19:18,206 --> 00:19:22,960
Calquera vez que vimos algo estrela, que
significa que é un punteiro para este tipo de datos.

432
00:19:22,960 --> 00:19:26,810
Entón, a próxima é, ao parecer, un
punteiro para un nó de struct.

433
00:19:26,810 --> 00:19:28,310
>> Agora, o que é un nodo struct?

434
00:19:28,310 --> 00:19:31,044
Ben, observe que ve os
mesmas palabras na esquina superior dereita.

435
00:19:31,044 --> 00:19:33,960
E, de feito, tamén verá a palabra
"Nó" aquí abaixo na parte inferior esquerda.

436
00:19:33,960 --> 00:19:35,640
E iso é realmente só unha conveniencia.

437
00:19:35,640 --> 00:19:39,930
Teña en conta que na nosa definición de estudante
hai a palabra "alumno" só unha vez.

438
00:19:39,930 --> 00:19:42,510
E iso é porque un alumno
obxecto non era auto-referencial.

439
00:19:42,510 --> 00:19:45,340
Non hai nada dentro dun estudante
que debe apuntar a outro estudante,

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

441
00:19:45,610 --> 00:19:47,630
Iso sería unha especie de
estraño no mundo real.

442
00:19:47,630 --> 00:19:50,880
>> Pero, cun nó nunha ligada
lista, queremos un nó

443
00:19:50,880 --> 00:19:53,970
para ser referencial a un obxecto semellante.

444
00:19:53,970 --> 00:19:57,900
E así entender o cambio aquí non é
só o que está dentro das chaves.

445
00:19:57,900 --> 00:20:00,800
Pero engadir a palabra "nó"
, Na parte superior, así como

446
00:20:00,800 --> 00:20:02,930
engadindo-o ao fondo
no canto de "alumno".

447
00:20:02,930 --> 00:20:06,000
E este é só un detalle técnico
de xeito que, de novo, a súa estrutura de datos

448
00:20:06,000 --> 00:20:11,380
pode ser auto-referencial, de xeito que a
nó pode apuntar a outro tal nó.

449
00:20:11,380 --> 00:20:13,840
>> Entón o que é iso, en última instancia
significará para nós?

450
00:20:13,840 --> 00:20:17,560
Ben, un, este material dentro
é o contido do noso nó.

451
00:20:17,560 --> 00:20:19,360
Esta cousa aquí enriba,
superior dereita, é tan

452
00:20:19,360 --> 00:20:20,860
que, unha vez máis, podemos referirnos a nós mesmos.

453
00:20:20,860 --> 00:20:23,401
E entón as cousas máis externa,
aínda nodo é un novo termo

454
00:20:23,401 --> 00:20:25,500
quizais, aínda o é
mesmo como estudante e que

455
00:20:25,500 --> 00:20:27,520
estaba debaixo do capó en SPL.

456
00:20:27,520 --> 00:20:31,095
>> Entón, se nós agora quería comezar
implantación desta lista ligada,

457
00:20:31,095 --> 00:20:33,220
como podemos traducir
algo así para codificar?

458
00:20:33,220 --> 00:20:35,350
Ben, imos ver unha
exemplo dun programa que

459
00:20:35,350 --> 00:20:36,840
en realidade, emprega unha lista ligada.

460
00:20:36,840 --> 00:20:40,870
Entre código de distribución de hoxe
é un programa chamado Lista Cero.

461
00:20:40,870 --> 00:20:44,980
E se eu executar este creei un super
GUI simple, Interface gráfica de usuario,

462
00:20:44,980 --> 00:20:46,460
pero é realmente só printf.

463
00:20:46,460 --> 00:20:50,930
E agora que eu me dei algunhas menú
opções-- DELETE, INSERT, Investigación,

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

465
00:20:51,750 --> 00:20:52,630
E Saír.

466
00:20:52,630 --> 00:20:55,970
Estes son só operacións comúns nun
estrutura de datos coñecida como lista de enlace.

467
00:20:55,970 --> 00:20:58,409
>> Agora Eliminar vai
eliminar un número da lista.

468
00:20:58,409 --> 00:21:00,200
Inserir vai engadir
un número á lista.

469
00:21:00,200 --> 00:21:02,181
Busca vai mirar
ao número da lista.

470
00:21:02,181 --> 00:21:04,930
E travesía é só un xeito elegante
de dicir, percorrer a lista,

471
00:21:04,930 --> 00:21:06,245
imprimir lo, pero é iso.

472
00:21:06,245 --> 00:21:07,720
Non cambia-lo de calquera maneira.

473
00:21:07,720 --> 00:21:08,570
>> Entón, imos tentar iso.

474
00:21:08,570 --> 00:21:10,160
Imos adiante e escriba 2.

475
00:21:10,160 --> 00:21:12,710
E entón eu vou
inserir o número, din 9.

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

477
00:21:13,620 --> 00:21:17,480
E agora o meu programa é só
programa para dicir lista é agora 9.

478
00:21:17,480 --> 00:21:20,190
Agora, se eu ir adiante e
que introducir de novo, imos

479
00:21:20,190 --> 00:21:23,680
me ir adiante e diminuír o zoom e escriba 17.

480
00:21:23,680 --> 00:21:25,770
Agora, a miña lista é 9, entón con 17 anos.

481
00:21:25,770 --> 00:21:27,750
Se eu fai introducir de novo, imos saltar un.

482
00:21:27,750 --> 00:21:32,400
No canto de 22, segundo a imaxe que teño
estado a ollar a aquí, déixeme pasar adiante

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

484
00:21:34,630 --> 00:21:36,230
Entón eu vou para escribir 26.

485
00:21:36,230 --> 00:21:37,755
A lista é como eu esperaba.

486
00:21:37,755 --> 00:21:40,630
Pero agora, só a ver se este código
será flexible, deixe-me agora

487
00:21:40,630 --> 00:21:43,520
Tipo 22, o cal, polo menos
conceptualmente, se temos

488
00:21:43,520 --> 00:21:46,520
Tendo isto resolto, o que é de feito
será outro obxectivo, agora,

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

490
00:21:48,690 --> 00:21:50,270
Entón eu prema Intro.

491
00:21:50,270 --> 00:21:51,380
En realidade, iso funciona.

492
00:21:51,380 --> 00:21:54,950
E agora déixeme introducir o
pasado, por a imaxe, 34.

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

494
00:21:55,450 --> 00:21:58,980
Entón, por agora, deixe-me estipulan que
Eliminar e Traverse e Investigación facer,

495
00:21:58,980 --> 00:21:59,760
de feito, traballar.

496
00:21:59,760 --> 00:22:04,180
En realidade, se eu executar investigación, imos
busque o número 22, Intro.

497
00:22:04,180 --> 00:22:05,010
Constatouse que 22.

498
00:22:05,010 --> 00:22:07,580
Entón é iso que este
Programa Lista Cero fai.

499
00:22:07,580 --> 00:22:10,230
>> Pero o que realmente está a suceder
en que aplica isto?

500
00:22:10,230 --> 00:22:14,530
Ben, primeiro eu podería, e de feito
Eu teño un arquivo chamado list0.h.

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

502
00:22:16,540 --> 00:22:20,690
E nalgún lugar existe esa
liña, typedef, nó struct,

503
00:22:20,690 --> 00:22:24,850
entón eu teño as miñas chaves, int n, e
entón struct-- cal era a definición?

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

505
00:22:26,530 --> 00:22:28,545
Nó struct seguinte.

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

507
00:22:29,920 --> 00:22:31,045
Por iso, necesitamos da estrela.

508
00:22:31,045 --> 00:22:33,420
Agora, tecnicamente, entrar
o costume de debuxar-lo aquí.

509
00:22:33,420 --> 00:22:35,670
Podes ver libros didácticos e
referencias en liña facelo alí.

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

511
00:22:36,660 --> 00:22:37,980
En realidade, iso é un pouco máis típico.

512
00:22:37,980 --> 00:22:40,563
Pero eu vou ser coherente co que
fixemos a última vez e facelo.

513
00:22:40,563 --> 00:22:42,350
E entón, finalmente, eu vou facer iso.

514
00:22:42,350 --> 00:22:45,550
>> Así, nun ficheiro de cabeceira
nalgún lugar, en list0.h

515
00:22:45,550 --> 00:22:49,200
hoxe é esta definición struct,
e quizais algunhas outras cousas.

516
00:22:49,200 --> 00:22:52,580
Mentres tanto, na list0c hai
Vai ser algunhas cousas.

517
00:22:52,580 --> 00:22:54,740
Pero imos só
comezar e non rematar isto.

518
00:22:54,740 --> 00:22:59,690
List0.h é un arquivo que quero
para incluír no meu arquivo C.

519
00:22:59,690 --> 00:23:03,910
E entón, nalgún momento eu son
terá int, principal, anular.

520
00:23:03,910 --> 00:23:06,530
E entón eu vou
Ten algún de tarefas está aquí.

521
00:23:06,530 --> 00:23:10,620
Eu tamén vou ter un
prototipo, como baleiro, procura, int,

522
00:23:10,620 --> 00:23:13,610
n, cuxo propósito na vida é
para buscar un elemento.

523
00:23:13,610 --> 00:23:18,310
E entón aquí eu afirmo en
código de hoxe, baleiro, procura, int, n,

524
00:23:18,310 --> 00:23:21,020
ningún punto e coma, pero claves abertas.

525
00:23:21,020 --> 00:23:25,049
E agora quero buscar algunha maneira
para un elemento da lista.

526
00:23:25,049 --> 00:23:27,340
Pero non temos o suficiente
información sobre a pantalla aínda.

527
00:23:27,340 --> 00:23:29,800
Eu non teño, de feito,
representaba a propia lista.

528
00:23:29,800 --> 00:23:33,070
Polo tanto, unha forma que puidésemos aplicar
unha lista ligada dun programa

529
00:23:33,070 --> 00:23:37,520
é que eu medio que quero facer algo
como declarar lista ligada aquí.

530
00:23:37,520 --> 00:23:40,520
Para simplificar, vou facer
este mundial, aínda que en xeral nos

531
00:23:40,520 --> 00:23:41,645
non debe facelo máis.

532
00:23:41,645 --> 00:23:43,260
Pero vai simplificar este exemplo.

533
00:23:43,260 --> 00:23:45,890
Entón, quero declarar
unha lista ligada aquí.

534
00:23:45,890 --> 00:23:47,010
Agora, como eu podería facelo?

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

536
00:23:48,810 --> 00:23:50,750
>> Aquí está a foto dunha lista encadeada.

537
00:23:50,750 --> 00:23:53,030
E eu realmente non
saber o momento como

538
00:23:53,030 --> 00:23:56,710
Eu estou indo a ir sobre a representación
tantas cousas con só un

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

540
00:23:58,040 --> 00:23:59,160
Pero creo que volta un momento.

541
00:23:59,160 --> 00:24:00,830
Todo este tempo que tivemos
cordas, que despois

542
00:24:00,830 --> 00:24:02,913
revelouse como matrices de
caracteres, que despois

543
00:24:02,913 --> 00:24:05,740
revelou ser só un punteiro
para o primeiro carácter

544
00:24:05,740 --> 00:24:08,890
nun array de caracteres
que ten un terminador nulo.

545
00:24:08,890 --> 00:24:13,530
Entón, por esa lóxica, e con iso
tipo de imaxe de sementar os seus pensamentos,

546
00:24:13,530 --> 00:24:17,964
Para que necesitamos realmente escribir na nosa
código para representar unha lista ligada?

547
00:24:17,964 --> 00:24:21,130
Como moitas desas información que necesitamos
para capturar en código C, diría?

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

549
00:24:22,654 --> 00:24:23,154
Si?

550
00:24:23,154 --> 00:24:24,738
>> Audiencia: Necesitamos un punteiro para un nó.

551
00:24:24,738 --> 00:24:26,237
DAVID J. Malan: Un punteiro para un nó.

552
00:24:26,237 --> 00:24:29,320
En particular, o que sería o seu nó
instintos ser para manter un punteiro para?

553
00:24:29,320 --> 00:24:30,026
>> Audiencias: O primeiro nodo.

554
00:24:30,026 --> 00:24:31,942
>> DAVID J. Malan: Si,
probablemente só o primeiro.

555
00:24:31,942 --> 00:24:34,030
E teña en conta, o primeiro
nó é unha forma distinta.

556
00:24:34,030 --> 00:24:37,690
É só a metade do tamaño da estrutura,
porque é en realidade só un punteiro.

557
00:24:37,690 --> 00:24:44,650
Entón, o que realmente pode facer é declarar
unha lista ligada a ser do tipo nodo *.

558
00:24:44,650 --> 00:24:47,780
E imos chamalo de primeira
e inicialize-o como nulo.

559
00:24:47,780 --> 00:24:49,910
Entón, null, unha vez máis, está chegando
en escena aquí.

560
00:24:49,910 --> 00:24:53,620
Non só é nulo usado como como un especial
valor de retorno para cousas como getString

561
00:24:53,620 --> 00:24:57,770
e malloc, nulo é tamén o cero
punteiro, a falta dun punteiro,

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

563
00:24:58,430 --> 00:25:00,309
Significa só que nada está aínda aquí.

564
00:25:00,309 --> 00:25:02,100
Agora en primeiro lugar, eu podería
chamou iso de nada.

565
00:25:02,100 --> 00:25:04,200
Podería telo chamado "lista"
ou calquera número de outras cousas.

566
00:25:04,200 --> 00:25:06,960
Pero eu estou chamando-o de "primeira" para que
se aliñan con esta imaxe.

567
00:25:06,960 --> 00:25:10,280
Así como unha corda pode ser representado
co enderezo do seu primeiro byte

568
00:25:10,280 --> 00:25:11,280
pode así unha lista ligada.

569
00:25:11,280 --> 00:25:13,480
E veremos outros datos
estruturas ser representado

570
00:25:13,480 --> 00:25:16,700
con só un punteiro,
unha frecha de 32 bits, que apunta

571
00:25:16,700 --> 00:25:18,740
o primeiro nodo na estrutura.

572
00:25:18,740 --> 00:25:20,340
>> Pero agora imos anticipar un problema.

573
00:25:20,340 --> 00:25:23,230
Se eu só estou recordando
no meu programa a dirección

574
00:25:23,230 --> 00:25:27,220
do primeiro nodo, o primeiro
rectángulo nesta estrutura de datos,

575
00:25:27,220 --> 00:25:31,760
o mellor que sexa o caso sobre a
implantación do resto da miña lista?

576
00:25:31,760 --> 00:25:35,820
¿Que é un detalle clave que está a suceder
para asegurar que realmente funciona?

577
00:25:35,820 --> 00:25:39,250
E por "realmente funciona" Eu
É dicir, moi parecido cunha corda,

578
00:25:39,250 --> 00:25:42,180
permítenos ir desde o primeiro carácter
en nome do Davin para o segundo,

579
00:25:42,180 --> 00:25:44,755
para o terceiro, o
cuarto, ata o final,

580
00:25:44,755 --> 00:25:47,880
como sabemos cando estamos ao final
dunha lista encadeada que se parece con isto?

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

582
00:25:50,035 --> 00:25:50,660
Cando é nulo.

583
00:25:50,660 --> 00:25:53,640
E eu teño representado este tipo de como
como unha forza enxeñeiro eléctrico,

584
00:25:53,640 --> 00:25:56,420
co pouco de terra
símbolo, das sortes.

585
00:25:56,420 --> 00:25:58,246
Pero iso só significa nulo neste caso.

586
00:25:58,246 --> 00:26:00,370
Pode deseñar calquera número
de formas, pero o mesmo autor

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

588
00:26:02,800 --> 00:26:06,260
>> Mentres nós estamos amarre
todos estes nodos xuntos,

589
00:26:06,260 --> 00:26:08,600
só lembrando que
o primeiro é, desde

590
00:26:08,600 --> 00:26:11,760
como poñer un símbolo especial no
o último nó na lista,

591
00:26:11,760 --> 00:26:15,130
e usaremos nulo, porque iso é
o que temos á nosa disposición,

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

593
00:26:16,480 --> 00:26:20,190
E aínda que eu só darlle un punteiro para
o primeiro elemento, que, o programador,

594
00:26:20,190 --> 00:26:22,486
certamente pode acceder ao resto.

595
00:26:22,486 --> 00:26:24,360
Pero imos deixar as súas mentes
vagar un pouco,

596
00:26:24,360 --> 00:26:26,140
se eles non están xa
moi wandered-- o que é

597
00:26:26,140 --> 00:26:28,723
será o tempo de execución
atopar algo nesa lista?

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

599
00:26:30,450 --> 00:26:33,470
Porra, é grande o de n,
que non está mal, na xustiza.

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

601
00:26:34,800 --> 00:26:37,980
Temos dado o recurso
de matrices movendo máis

602
00:26:37,980 --> 00:26:43,130
para ese cadro de forma dinámica
entrelazados ou nós conectados?

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

604
00:26:44,970 --> 00:26:46,687
Nós desistimos de acceso aleatorio.

605
00:26:46,687 --> 00:26:48,770
Unha matriz é bo porque
matematicamente todo

606
00:26:48,770 --> 00:26:50,340
está de volta para facer a volta atrás.

607
00:26:50,340 --> 00:26:52,370
Aínda que esta foto
parece moito, e mesmo

608
00:26:52,370 --> 00:26:55,830
pero parece que estes nós
son ben espazos entre si, en realidade

609
00:26:55,830 --> 00:26:56,830
poderían estar en calquera lugar.

610
00:26:56,830 --> 00:27:01,590
OX 1, Ox50, Ox123, Ox99, estes
nós podería estar en calquera lugar.

611
00:27:01,590 --> 00:27:05,960
Porque malloc aloca memoria
do conxunto, pero en calquera lugar do heap.

612
00:27:05,960 --> 00:27:09,080
Non necesariamente sabe que é
será back to back to back.

613
00:27:09,080 --> 00:27:12,460
E así esta foto en realidade
non vai ser moi esta fermosa.

614
00:27:12,460 --> 00:27:16,140
>> Entón, que vai levar un pouco de
traballar para aplicar esta función.

615
00:27:16,140 --> 00:27:17,880
Entón, imos aplicar a investigación agora.

616
00:27:17,880 --> 00:27:20,250
E nós imos ver unha especie de
xeito intelixente de facelo.

617
00:27:20,250 --> 00:27:24,660
Entón, se eu son unha función de busca e
Eu son dado unha variable, enteiro n

618
00:27:24,660 --> 00:27:28,490
buscar, eu teño que saber o
nova sintaxe para ollar para dentro

619
00:27:28,490 --> 00:27:32,400
dunha estrutura que está
apuntou, para atopar n.

620
00:27:32,400 --> 00:27:33,210
Entón, imos facelo.

621
00:27:33,210 --> 00:27:36,030
>> Entón, primeiro eu vou
adiante e declarar un nó *.

622
00:27:36,030 --> 00:27:39,400
E eu vou chamalo
punteiro, só por convención.

623
00:27:39,400 --> 00:27:41,710
E eu estou indo a arrincar o primeiro.

624
00:27:41,710 --> 00:27:43,770
E agora podo facelo
nun número de formas.

625
00:27:43,770 --> 00:27:45,436
Pero eu vou ter unha visión común.

626
00:27:45,436 --> 00:27:50,180
Mentres anotador non coincide
null, e iso é válido sintaxe.

627
00:27:50,180 --> 00:27:54,550
E iso significa só facer o seguinte, de xeito
Sempre que non está a apuntar cara ao nada.

628
00:27:54,550 --> 00:27:55,800
O que quero facer?

629
00:27:55,800 --> 00:28:01,939
>> Se punteiro punto n, déixeme volver
para que, equals-- iguala o que?

630
00:28:01,939 --> 00:28:03,105
Cal o valor que eu estou buscando?

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

632
00:28:04,920 --> 00:28:06,590
O n real que foi pasado.

633
00:28:06,590 --> 00:28:09,020
Entón aquí está a outra característica
de C e moitas linguas.

634
00:28:09,020 --> 00:28:13,705
Aínda que a estrutura chamada nodo
ten un valor de n, totalmente lexítimo

635
00:28:13,705 --> 00:28:17,530
ter un argumento locais
ou variable chamada n.

636
00:28:17,530 --> 00:28:20,085
Porque aínda que, con
Os ollos humanos, pódese distinguir

637
00:28:20,085 --> 00:28:22,087
que esta n é presuntamente
diferente deste n.

638
00:28:22,087 --> 00:28:23,420
Porque a sintaxe é diferente.

639
00:28:23,420 --> 00:28:26,211
Ten un punto e un punteiro,
mentres este non ten tal cousa.

640
00:28:26,211 --> 00:28:27,290
Entón, iso é OK.

641
00:28:27,290 --> 00:28:29,120
Isto é OK para chamar-lles as mesmas cousas.

642
00:28:29,120 --> 00:28:32,380
>> Se eu non atopar iso, eu son
Vai querer facer algo

643
00:28:32,380 --> 00:28:35,000
como anunciar que atopamos n.

644
00:28:35,000 --> 00:28:37,930
E nós imos deixar isto como un
comentar ou código de pseudocódigo.

645
00:28:37,930 --> 00:28:40,190
Outra cousa, e aquí está o
parte interesante, o que

646
00:28:40,190 --> 00:28:47,320
gustaríame facer se o nodo actual
non se conteñen n que eu me importa?

647
00:28:47,320 --> 00:28:50,700
¿Como conseguir o seguinte?

648
00:28:50,700 --> 00:28:53,710
Se o meu dedo na
momento é PTR, e é

649
00:28:53,710 --> 00:28:55,920
apuntando para o que quere que
primeiro está a apuntar,

650
00:28:55,920 --> 00:28:59,290
¿Como mover meu dedo
ao nodo seguinte código?

651
00:28:59,290 --> 00:29:01,915
Ben, cal é a ruta que estamos
vai seguir neste caso?

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

653
00:29:03,464 --> 00:29:04,380
Audiencia: [inaudível].

654
00:29:04,380 --> 00:29:05,630
DAVID J. Malan: Si, por iso a continuación.

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

656
00:29:06,640 --> 00:29:09,824
Entón, se eu volver para o meu
código aquí, en realidade, eu son

657
00:29:09,824 --> 00:29:12,990
indo a ir adiante e dicir punteiro, que
é só un variable-- temporal é

658
00:29:12,990 --> 00:29:15,320
un nome raro, PTR, pero
é como temp--

659
00:29:15,320 --> 00:29:19,234
Vou configurar o punteiro
igual a calquera punteiro é--

660
00:29:19,234 --> 00:29:22,150
e unha vez máis, que vai ser un
buggy pouco para un punto moment-- seguinte.

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

662
00:29:23,551 --> 00:29:26,550
Noutras palabras, eu vou tomar o meu
dedo que está a apuntar para este nodo

663
00:29:26,550 --> 00:29:31,247
aquí e eu vou dicir, xa sabe
o que, bótalle un ollo ao seguinte campo

664
00:29:31,247 --> 00:29:33,330
e mover o dedo
sexa o que está a apuntar.

665
00:29:33,330 --> 00:29:35,163
E iso vai
repetir, repetir, repetir.

666
00:29:35,163 --> 00:29:37,630
Pero cando o meu dedo
deixar de facer algo?

667
00:29:37,630 --> 00:29:40,095
Tan pronto que liña de código en patadas?

668
00:29:40,095 --> 00:29:40,970
Audiencia: [inaudível]

669
00:29:40,970 --> 00:29:43,060
DAVID J. Malan: Si o punto mentres
punteiro non é igual a null.

670
00:29:43,060 --> 00:29:44,900
Nalgún momento o meu dedo do
estará apuntando nulo

671
00:29:44,900 --> 00:29:47,070
e eu estou indo a entender
isto é o final da lista.

672
00:29:47,070 --> 00:29:48,910
Agora, este é un pouco
mentirinha para simplificar.

673
00:29:48,910 --> 00:29:51,580
Acontece que, aínda que
acaba de aprender esta notación de punto

674
00:29:51,580 --> 00:29:55,220
para estruturas, o punteiro non é un struct.

675
00:29:55,220 --> 00:29:56,580
PTR é o que?

676
00:29:56,580 --> 00:29:58,350
Só para ser máis detallista.

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

678
00:29:59,720 --> 00:30:01,360
É un punteiro para un nó.

679
00:30:01,360 --> 00:30:03,120
Non é un nó en si.

680
00:30:03,120 --> 00:30:06,650
Se eu non tiña ningunha estrela aquí, punteiro
absolutely-- é un nó.

681
00:30:06,650 --> 00:30:08,650
Isto é debido a unha semana
declaración dunha variable,

682
00:30:08,650 --> 00:30:10,120
aínda que a palabra "nó" é novo.

683
00:30:10,120 --> 00:30:13,860
>> Pero así que introducir un
estrela, agora é un punteiro para un nó.

684
00:30:13,860 --> 00:30:17,960
E, por desgraza, non pode usar
a notación de punto para un punteiro.

685
00:30:17,960 --> 00:30:21,070
Ten que usar a frecha
notación, o que, sorprendentemente,

686
00:30:21,070 --> 00:30:23,470
é a primeira vez que unha peza
de sintaxe parece intuitiva.

687
00:30:23,470 --> 00:30:25,245
Isto literalmente parece unha frecha.

688
00:30:25,245 --> 00:30:26,370
E iso é unha cousa boa.

689
00:30:26,370 --> 00:30:28,995
E aquí embaixo, literalmente
parece unha frecha.

690
00:30:28,995 --> 00:30:31,870
Entón, eu creo que é a la-- non
creo que estou over-cometer aqui-- I

691
00:30:31,870 --> 00:30:34,120
creo que é a última peza nova
de sintaxe, xa veremos.

692
00:30:34,120 --> 00:30:36,500
E, por sorte, é de feito
algo máis intuitivo.

693
00:30:36,500 --> 00:30:40,090
>> Agora, para aqueles de vostedes que
pode preferir a vella forma,

694
00:30:40,090 --> 00:30:42,550
Aínda pode usar a notación de punto.

695
00:30:42,550 --> 00:30:45,380
Pero por luns de
conversa, primeiro

696
00:30:45,380 --> 00:30:50,530
que ir alí, ir a ese
abordar, a continuación, acceder ao campo.

697
00:30:50,530 --> 00:30:51,897
Entón, iso tamén é correcto.

698
00:30:51,897 --> 00:30:53,730
E, francamente, este é un
pouco máis pedante.

699
00:30:53,730 --> 00:30:56,530
Está literalmente dicindo, desreferenciava
o punteiro e ir máis alá.

700
00:30:56,530 --> 00:30:59,320
Logo, cara .n, o campo chamado n.

701
00:30:59,320 --> 00:31:01,370
Pero, francamente, ninguén quere
para escribir ou ler isto.

702
00:31:01,370 --> 00:31:03,620
E así o mundo inventado
a notación de frecha, que

703
00:31:03,620 --> 00:31:06,980
é equivalente, idéntica,
é só un azucre sintático.

704
00:31:06,980 --> 00:31:10,570
Así, un xeito elegante de dicir iso
parece mellor, ou parece máis simple.

705
00:31:10,570 --> 00:31:12,296
>> Entón, agora eu vou facer outra cousa.

706
00:31:12,296 --> 00:31:15,420
Eu vou dicir "romper" xa que eu
penso tan non seguir mirando para el.

707
00:31:15,420 --> 00:31:17,620
Pero esta é a esencia
dunha función de investigación.

708
00:31:17,620 --> 00:31:21,710
Pero é moito máis doado, no
final, non andar a través do código.

709
00:31:21,710 --> 00:31:25,570
Este é de feito a implementación formal
de investigación en código de distribución de hoxe.

710
00:31:25,570 --> 00:31:30,530
Ouso dicir que inserir non é
particularmente diversión a pé

711
00:31:30,530 --> 00:31:33,180
visualmente, nin borrar, mesmo
con todo, ao final do día

712
00:31:33,180 --> 00:31:35,460
eles se resumen a moi
heurísticas simple.

713
00:31:35,460 --> 00:31:36,330
>> Entón, imos facelo.

714
00:31:36,330 --> 00:31:39,250
Se vai humor me aquí, eu fixen
traer unha morea de bolas de estrés.

715
00:31:39,250 --> 00:31:40,620
Eu trouxo unha morea de números.

716
00:31:40,620 --> 00:31:46,562
E poderiamos obter uns poucos voluntarios
para representar a 9, 17, 20, 22, 29, e 34?

717
00:31:46,562 --> 00:31:48,270
Entón, basicamente todo
quen está aquí hoxe.

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

719
00:31:50,170 --> 00:31:52,760
Isto foi un, dous, tres,
catro, cinco, seis persoas.

720
00:31:52,760 --> 00:31:55,740
E eu fun convidado a vai-- ver, non
unha na parte de atrás levanta as mans.

721
00:31:55,740 --> 00:32:01,910
OK, un, dous, tres, catro,
cinco-- déixeme subir balance-- seis.

722
00:32:01,910 --> 00:32:03,051
OK, vostede seis suba.

723
00:32:03,051 --> 00:32:04,050
Imos ter que outros.

724
00:32:04,050 --> 00:32:05,460
Trouxo estrés bolas extras.

725
00:32:05,460 --> 00:32:08,200
E se podería, por
só un momento, a liña

726
00:32:08,200 --> 00:32:10,490
-vos só
como esta foto aquí.

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

728
00:32:15,200 --> 00:32:15,959
>> Todo correcto.

729
00:32:15,959 --> 00:32:17,125
A ver, cal é o seu nome?

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

731
00:32:17,550 --> 00:32:18,800
>> DAVID J. Malan: Andrew,
é o número 9.

732
00:32:18,800 --> 00:32:19,540
Pracer en coñece-lo.

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

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
Si?

741
00:32:25,450 --> 00:32:26,400
>> Audiencia: Eu son 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: Christian.

746
00:32:29,340 --> 00:32:30,715
DAVID J. Malan: Christian, David.

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

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

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
Entón vai adiante e obter em-- 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
Espérase.

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
Alguén ten un favorito?

760
00:32:43,682 --> 00:32:44,890
Audiencia: Eu teño unha sharpie.

761
00:32:44,890 --> 00:32:45,660
DAVID J. Malan: Ten un sharpie?

762
00:32:45,660 --> 00:32:46,159
Está ben.

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

764
00:32:47,577 --> 00:32:49,160
E alguén ten un anaco de papel?

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

766
00:32:51,562 --> 00:32:52,270
Salva a charla.

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

768
00:32:53,810 --> 00:32:55,362
Veña.

769
00:32:55,362 --> 00:32:56,320
Audiencia: Temos iso.

770
00:32:56,320 --> 00:32:57,600
DAVID J. Malan: Temos isto?

771
00:32:57,600 --> 00:32:58,577
Todo ben, grazas.

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

773
00:33:01,380 --> 00:33:02,520
Aquí imos nós.

774
00:33:02,520 --> 00:33:03,582
Foi iso de ti?

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

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

777
00:33:05,670 --> 00:33:07,220
Entón, 29.

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

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

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

781
00:33:13,360 --> 00:33:14,890
Eu mal escrito 29, pero Aceptar.

782
00:33:14,890 --> 00:33:15,720
Continúe.

783
00:33:15,720 --> 00:33:18,114
Todo ben, eu vou che dar
a pluma de volta momentaneamente.

784
00:33:18,114 --> 00:33:19,280
Entón, temos esas persoas aquí.

785
00:33:19,280 --> 00:33:20,330
Imos ter outro.

786
00:33:20,330 --> 00:33:23,750
Gabe, quere xogar
o primeiro elemento aquí?

787
00:33:23,750 --> 00:33:25,705
Imos ter que vostede para ligar
a estas persoas finas.

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

789
00:33:26,930 --> 00:33:31,030
Entón, 9, 17, 20, 22, especie
de 29, e despois 34.

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

791
00:33:32,160 --> 00:33:33,325
Será que imos perder alguén?

792
00:33:33,325 --> 00:33:33,950
Eu teño un 34.

793
00:33:33,950 --> 00:33:36,730
Onde fez-- OK, quen quere ser 34?

794
00:33:36,730 --> 00:33:37,605
OK, imos para arriba, 34.

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

796
00:33:39,280 --> 00:33:41,220
Todo ben, este será
valeu a pena o clímax.

797
00:33:41,220 --> 00:33:41,550
Cal é o seu nome?

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

799
00:33:42,040 --> 00:33:43,456
>> DAVID J. Malan: Peter, imos cara arriba.

800
00:33:43,456 --> 00:33:46,810
Todo ben, entón aquí está un
grupo enteiro de nós.

801
00:33:46,810 --> 00:33:49,060
Cada un de vós representa
un deses rectángulos.

802
00:33:49,060 --> 00:33:51,930
E Gabe, a un pouco raro
home para fóra, representa o primeiro.

803
00:33:51,930 --> 00:33:54,850
Así, o seu punteiro é algo menor
na pantalla do que todos os outros.

804
00:33:54,850 --> 00:33:58,120
E neste caso, cada un a súa esquerda
mans vai ou apuntar cara a abaixo,

805
00:33:58,120 --> 00:34:01,085
representando, así, nulo, de xeito
só na ausencia dun punteiro,

806
00:34:01,085 --> 00:34:03,210
ou que vai estar apuntando
nun nó xunto a ti.

807
00:34:03,210 --> 00:34:05,440
>> Entón, agora, se adornar
vós similares a imaxe

808
00:34:05,440 --> 00:34:07,585
aquí, vai adiante e punto
un para o outro, con Gabe

809
00:34:07,585 --> 00:34:11,030
en particular, que apunta ao
o número 9 para representar a lista.

810
00:34:11,030 --> 00:34:14,050
OK, eo número 34, a súa man esquerda
debe só estar apuntando para o chan.

811
00:34:14,050 --> 00:34:15,750
>> OK, entón esta é a lista encadeada.

812
00:34:15,750 --> 00:34:17,580
Polo tanto, este é o escenario en cuestión.

813
00:34:17,580 --> 00:34:20,210
E, de feito, este é representante
dunha clase de problemas

814
00:34:20,210 --> 00:34:21,929
que pode tentar resolver co código.

815
00:34:21,929 --> 00:34:25,020
Quere introducir en última instancia
un novo elemento na lista.

816
00:34:25,020 --> 00:34:27,494
Neste caso, imos
intente inserir o número 55.

817
00:34:27,494 --> 00:34:28,500

818
00:34:28,500 --> 00:34:30,860
Pero non vai ser
casos diferentes a considerar.

819
00:34:30,860 --> 00:34:34,409
E, de feito, este será un
do gran-retrato takeaways aquí, é,

820
00:34:34,409 --> 00:34:35,659
cales son os diferentes casos.

821
00:34:35,659 --> 00:34:39,120
Cales son os distintos as condicións ou
ramas que o programa poida ter?

822
00:34:39,120 --> 00:34:42,024
>> Ben, o número que estás
inserción, que sabemos agora para ser 55,

823
00:34:42,024 --> 00:34:44,650
pero se non sabía
con antelación, eu diría

824
00:34:44,650 --> 00:34:47,840
cae, polo menos, tres
situacións posibles.

825
00:34:47,840 --> 00:34:49,717
Onde pode un elemento novo ser?

826
00:34:49,717 --> 00:34:51,050
Audiencia: E o fin ou medio.

827
00:34:51,050 --> 00:34:54,150
David J. Malan: Ao final, en
no medio, ou no inicio.

828
00:34:54,150 --> 00:34:56,650
Entón, eu afirmo que hai polo menos
tres problemas que necesitamos resolver.

829
00:34:56,650 --> 00:34:58,691
Imos escoller o que é, se cadra,
sen dúbida o máis simple

830
00:34:58,691 --> 00:35:01,090
un, en que o novo elemento
pertence ao principio.

831
00:35:01,090 --> 00:35:04,040
Entón, eu vou ter bastante código
como buscar, o que eu acabo de escribir.

832
00:35:04,040 --> 00:35:07,670
E eu vou ter PTR, que
Vou representar aquí co meu dedo,

833
00:35:07,670 --> 00:35:08,370
como de costume.

834
00:35:08,370 --> 00:35:12,430
>> E lembre, o valor
fixemos arrincar PTR para?

835
00:35:12,430 --> 00:35:15,300
Por iso, el inicializar como nulo inicialmente.

836
00:35:15,300 --> 00:35:16,410

837
00:35:16,410 --> 00:35:19,770
Pero entón o que fixemos, xa que
estaban dentro da nosa función de procura?

838
00:35:19,770 --> 00:35:20,940

839
00:35:20,940 --> 00:35:24,870
Nós configure-lo igual ao primeiro,
o que non significa facelo.

840
00:35:24,870 --> 00:35:25,890

841
00:35:25,890 --> 00:35:30,570
Se eu definir PTR igual ao primeiro, o que
debe ser realmente a miña man apuntando?

842
00:35:30,570 --> 00:35:31,070
Certo.

843
00:35:31,070 --> 00:35:33,290
Entón, se Gabe e eu imos
ser valores iguais aquí,

844
00:35:33,290 --> 00:35:34,760
necesitamos tanto do punto no número 9.

845
00:35:34,760 --> 00:35:36,420
>> Polo tanto, este foi o inicio da nosa historia.

846
00:35:36,420 --> 00:35:38,700
E agora este é só simple,
aínda que a sintaxe é novo.

847
00:35:38,700 --> 00:35:40,580
Conceptualmente, esta é só a busca lineal.

848
00:35:40,580 --> 00:35:42,750
É 55 igual a 9?

849
00:35:42,750 --> 00:35:45,559
Ou mellor, imos dicir menos que 9.

850
00:35:45,559 --> 00:35:47,600
Porque eu estou tentando
descubrir onde poñer 55.

851
00:35:47,600 --> 00:35:51,270
Menos de 9, menos de 17, menos
de 20, menos de 22, menos de 29,

852
00:35:51,270 --> 00:35:52,510
menos que 34, n.

853
00:35:52,510 --> 00:35:55,080
Polo tanto, agora estamos en caso
un de polo menos tres.

854
00:35:55,080 --> 00:35:59,910
>> Se eu queira inserir 55 para aquí, o que
liñas de código necesidade de ter executado?

855
00:35:59,910 --> 00:36:01,890
Como é que ese cadro de
os seres humanos necesitan cambiar?

856
00:36:01,890 --> 00:36:03,181
O que fago coa man esquerda?

857
00:36:03,181 --> 00:36:04,530

858
00:36:04,530 --> 00:36:07,360
Isto debe ser inicialmente nula,
porque eu estou no final da lista.

859
00:36:07,360 --> 00:36:09,318
E o que debe ocorrer
aquí con Peter, foi?

860
00:36:09,318 --> 00:36:10,520

861
00:36:10,520 --> 00:36:12,430
Está, obviamente, vai apuntar para min.

862
00:36:12,430 --> 00:36:15,580
Entón, eu afirmo que hai polo menos dúas liñas
de código no código de exemplo a partir de hoxe

863
00:36:15,580 --> 00:36:18,570
que vai aplicar este
escenario de adición de 55 na cola.

864
00:36:18,570 --> 00:36:20,950
E eu podería alguén hop
e representan só 55?

865
00:36:20,950 --> 00:36:22,200
Todo ben, que é o novo 55.

866
00:36:22,200 --> 00:36:23,580

867
00:36:23,580 --> 00:36:27,054
>> Entón, agora que o próximo
escenario ven xunto,

868
00:36:27,054 --> 00:36:29,720
e queremos introducir o
inicio ou a cabeza de lista?

869
00:36:29,720 --> 00:36:31,100
E cal é o seu nome, o 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
OK, pracer de coñece-lo.

873
00:36:33,585 --> 00:36:34,210
Benvido a bordo.

874
00:36:34,210 --> 00:36:36,640
Entón agora nós imos
introducir, por exemplo, o número 5.

875
00:36:36,640 --> 00:36:39,840
Este é o segundo caso do
tres nós vimos con antes.

876
00:36:39,840 --> 00:36:43,050
Así, se pertence 5 ao principio,
imos ver como podemos descubrir iso.

877
00:36:43,050 --> 00:36:46,310
Eu arrincar o meu PTR
punteiro ao 9 de novo.

878
00:36:46,310 --> 00:36:49,140
E podo entender, oh, 5 é inferior a 9.

879
00:36:49,140 --> 00:36:50,880
Entón corrixir esta foto para nós.

880
00:36:50,880 --> 00:36:54,820
Cuxas mans, Gabe é David de
ou-- cal é o nome do número 9?

881
00:36:54,820 --> 00:36:55,740
>> Audiencia: Jen.

882
00:36:55,740 --> 00:36:58,406
>> DAVID J. Malan: hands-- de Jen
que das nosas mans que cambiar?

883
00:36:58,406 --> 00:36:58,905

884
00:36:58,905 --> 00:37:00,970
OK, entón Gabe apunta ao que agora?

885
00:37:00,970 --> 00:37:01,640
Para min.

886
00:37:01,640 --> 00:37:02,750
Eu son o novo nodo.

887
00:37:02,750 --> 00:37:04,870
Entón eu vou tipo de movemento
aquí para velo visualmente.

888
00:37:04,870 --> 00:37:06,435
E mentres tanto o que eu apuntar isto?

889
00:37:06,435 --> 00:37:07,910

890
00:37:07,910 --> 00:37:09,020
Aínda así, onde estou a apuntar.

891
00:37:09,020 --> 00:37:10,000
Entón é iso.

892
00:37:10,000 --> 00:37:13,717
Entón, só realmente unha liña de correccións de código
esta cuestión en particular, ao parecer.

893
00:37:13,717 --> 00:37:14,800
Todo ben, entón iso é bo.

894
00:37:14,800 --> 00:37:17,580
E alguén pode ser un marcador a 5?

895
00:37:17,580 --> 00:37:18,080
Imos cara arriba.

896
00:37:18,080 --> 00:37:20,270

897
00:37:20,270 --> 00:37:21,320
Nós imos aproveitar vostede da próxima vez.

898
00:37:21,320 --> 00:37:24,280
>> Todo ben, entón agora-- e
Como un aparte, os nomes

899
00:37:24,280 --> 00:37:28,510
Eu non estou facendo mención explícita de dereito
agora, punteiro pred, punteiro antecesor

900
00:37:28,510 --> 00:37:31,260
e novo punteiro, que é
só os nomes dado

901
00:37:31,260 --> 00:37:35,280
no código de exemplo para os punteiros ou
miñas mans que é tipo de apuntar ao redor.

902
00:37:35,280 --> 00:37:36,060
Cal é o seu nome?

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
Benvido a bordo.

906
00:37:38,090 --> 00:37:42,180
Todo ben, entón imos considerar agora
un escenario un pouco máis aburrido,

907
00:37:42,180 --> 00:37:46,350
polo cal quero inserir
algo así como 26 para iso.

908
00:37:46,350 --> 00:37:47,090
20?

909
00:37:47,090 --> 00:37:47,590
O que?

910
00:37:47,590 --> 00:37:50,510
Estes é-- cousa boa que temos esta pluma.

911
00:37:50,510 --> 00:37:51,955
Todo ben, 20.

912
00:37:51,955 --> 00:37:53,640

913
00:37:53,640 --> 00:37:57,570
Se alguén puidese ter outra peza de
papel preparado, só en caso-- todo ben.

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
Ben, este é un exemplo
dun erro charla.

917
00:38:02,390 --> 00:38:03,894
OK entón, cal é o seu nome?

918
00:38:03,894 --> 00:38:04,560
Audiencia: Julia.

919
00:38:04,560 --> 00:38:07,559
DAVID J. Malan: Julia, pode pop
para fóra, e finxir que nunca foron alí?

920
00:38:07,559 --> 00:38:09,040
OK, iso nunca sucedeu.

921
00:38:09,040 --> 00:38:09,680
Grazas.

922
00:38:09,680 --> 00:38:12,180
Entón, supoña que queremos inserir
Julia para esta lista ligada.

923
00:38:12,180 --> 00:38:13,780
Ela é o número 20.

924
00:38:13,780 --> 00:38:15,530
E, por suposto, é
vai pertencer ao

925
00:38:15,530 --> 00:38:17,521
begin-- non apuntan nada aínda.

926
00:38:17,521 --> 00:38:20,020
Entón a súa man se pode tipo de
valor nulo ou algún lixo.

927
00:38:20,020 --> 00:38:21,210
Imos contar a historia rápida.

928
00:38:21,210 --> 00:38:22,980
Estou apuntando ao número 5 esta vez.

929
00:38:22,980 --> 00:38:23,880
Entón eu verifico 9.

930
00:38:23,880 --> 00:38:25,130
Entón eu verifico 17.

931
00:38:25,130 --> 00:38:26,247
Entón eu verifico 22.

932
00:38:26,247 --> 00:38:27,650

933
00:38:27,650 --> 00:38:32,485
E eu entendo, ooh, Julia
que ir antes de 22.

934
00:38:32,485 --> 00:38:33,580

935
00:38:33,580 --> 00:38:34,660
Entón, o que ten que ocorrer?

936
00:38:34,660 --> 00:38:35,786

937
00:38:35,786 --> 00:38:36,910
Cuxas mans que cambiar?

938
00:38:36,910 --> 00:38:38,360
Julia, miña, ou--
Cal é o seu nome?

939
00:38:38,360 --> 00:38:39,230
>> Audiencia: Christian.

940
00:38:39,230 --> 00:38:40,060
>> DAVID J. Malan: Christian ou?

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
Christian ou Andy?

944
00:38:41,654 --> 00:38:44,280

945
00:38:44,280 --> 00:38:45,690
Andy ten apuntar?

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
Todo correcto.

949
00:38:47,840 --> 00:38:48,960
Entón, Andy, quere apuntar Julia?

950
00:38:48,960 --> 00:38:50,120
Pero agarde un minuto.

951
00:38:50,120 --> 00:38:53,260
Na historia, ata agora,
Eu son o tipo de unha

952
00:38:53,260 --> 00:38:56,800
en carga, no sentido de que
punteiro é o que é

953
00:38:56,800 --> 00:38:57,850
movéndose a través da lista.

954
00:38:57,850 --> 00:39:00,800
Podemos ter un nome para Andy, pero
non hai ningunha variábel chamada Andy.

955
00:39:00,800 --> 00:39:04,320
A única outra variable que temos é
primeiro, que está representado por Gabe.

956
00:39:04,320 --> 00:39:07,690
>> Polo tanto, este é, en realidade, porque así
agora non teño necesidade diso.

957
00:39:07,690 --> 00:39:10,846
Pero agora na pantalla existe
falar de novo do punteiro pred.

958
00:39:10,846 --> 00:39:11,970
Entón deixe-me ser máis explícita.

959
00:39:11,970 --> 00:39:14,820
Se esta é punteiro, eu tiña mellor
estar un pouco máis intelixente

960
00:39:14,820 --> 00:39:15,950
sobre a miña iteración.

961
00:39:15,950 --> 00:39:19,580
Se non lle importa de pasar por aquí
de novo, que apunta aquí, que apunta aquí.

962
00:39:19,580 --> 00:39:22,500
Pero deixe-me ter un punteiro pred,
punteiro antecesor, que é

963
00:39:22,500 --> 00:39:24,740
tipo de apuntar ao
elemento que eu estaba só no.

964
00:39:24,740 --> 00:39:27,330
Entón, cando eu ir máis alá, agora
miña esquerda actualizacións manuais.

965
00:39:27,330 --> 00:39:29,370
Cando vou aquí miñas actualizacións man esquerda.

966
00:39:29,370 --> 00:39:33,090
E agora eu teño non só un punteiro para
o elemento que vai detrás de Julia,

967
00:39:33,090 --> 00:39:36,300
Eu aínda teño un punteiro para
Andy, o elemento antes.

968
00:39:36,300 --> 00:39:39,430
Entón, ten acceso, esencialmente,
fariña de rosca, se quere,

969
00:39:39,430 --> 00:39:41,500
para todas as indicacións necesarias.

970
00:39:41,500 --> 00:39:43,710
>> Entón, se eu estou a apuntar cara
Andy e eu tamén estou a apuntar

971
00:39:43,710 --> 00:39:47,105
na cristiá, cuxas mans
agora debe ser apuntado noutro lugar?

972
00:39:47,105 --> 00:39:48,770

973
00:39:48,770 --> 00:39:51,960
Entón Andy agora pode apuntar Julia.

974
00:39:51,960 --> 00:39:54,460
Julia agora pode apuntar Christian.

975
00:39:54,460 --> 00:39:56,950
Porque pode copiar a miña
punteiro do lado dereito.

976
00:39:56,950 --> 00:40:00,044
E que efectivamente pon
de volta a este sitio aquí.

977
00:40:00,044 --> 00:40:02,460
Así, en breve, aínda que iso
está nos levando especie de sempre

978
00:40:02,460 --> 00:40:04,510
realmente actualizar un
lista ligada, entender

979
00:40:04,510 --> 00:40:06,580
que as operacións
son relativamente simple.

980
00:40:06,580 --> 00:40:10,030
É de un, dous, tres
liñas de código ao final.

981
00:40:10,030 --> 00:40:12,780
Pero envolto en torno de quen
liñas de código presuntamente

982
00:40:12,780 --> 00:40:16,350
é un pouco de lóxica que efectivamente
fai a pregunta: ¿onde estamos?

983
00:40:16,350 --> 00:40:18,970
Estamos no principio,
no medio, ou o fin?

984
00:40:18,970 --> 00:40:21,890
>> Agora, por suposto hai algunha outra
operacións que poidan aplicar.

985
00:40:21,890 --> 00:40:24,880
E estas fotos aquí só retratan
o que fixemos cos seres humanos.

986
00:40:24,880 --> 00:40:26,080
E como a retirada?

987
00:40:26,080 --> 00:40:30,650
Se eu queira, por exemplo,
eliminar o número 34 ou 55,

988
00:40:30,650 --> 00:40:34,680
Podería ter o mesmo tipo de código,
pero eu vou ter un ou dous pasos.

989
00:40:34,680 --> 00:40:36,110
Porque o que hai de novo?

990
00:40:36,110 --> 00:40:40,460
Se eu eliminar alguén ao final,
como número 55 e logo 34,

991
00:40:40,460 --> 00:40:42,995
o que tamén ten que cambiar como fago isto?

992
00:40:42,995 --> 00:40:44,870
Teño que non evict--
Cal é o seu nome?

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
Teño non só evict-- libre Jack,
tan literalmente conectar balde Jack, ou polo menos

996
00:40:49,770 --> 00:40:53,530
o punteiro alí tamén, pero agora
o que ten que cambiar con Peter?

997
00:40:53,530 --> 00:40:55,510
A súa man mellor comezar a apuntar cara a abaixo.

998
00:40:55,510 --> 00:40:59,300
Porque así que eu chamo libre en
Jack, se de Pedro aínda apuntando para Jack

999
00:40:59,300 --> 00:41:02,530
e, polo tanto, eu sigo percorrendo
Árbore e acceso este punteiro,

1000
00:41:02,530 --> 00:41:05,650
que é cando o noso vello amigo segmentación
fallo realmente chutar.

1001
00:41:05,650 --> 00:41:07,860
Porque temos dado o
memoria de volta a Jack.

1002
00:41:07,860 --> 00:41:10,760
>> Pode estar alí
torpes por só un momento.

1003
00:41:10,760 --> 00:41:13,410
Porque temos só un par
operacións finais a considerar.

1004
00:41:13,410 --> 00:41:15,600
Eliminar o cabeza de lista,
ou o beginning-- e este de

1005
00:41:15,600 --> 00:41:16,349
un pouco aburrido.

1006
00:41:16,349 --> 00:41:19,640
Porque temos que saber que Gabe
é unha especie de especial neste programa.

1007
00:41:19,640 --> 00:41:21,440
Porque, en realidade, ten o seu propio punteiro.

1008
00:41:21,440 --> 00:41:24,860
Non está só a ser apuntada para,
como é case todo o mundo aquí.

1009
00:41:24,860 --> 00:41:28,112
>> Así, cando a cabeza da lista é
eliminada, cuxas mans que cambiar agora?

1010
00:41:28,112 --> 00:41:29,070
Cal é o seu nome?

1011
00:41:29,070 --> 00:41:29,450
>> Audiencia: Christine.

1012
00:41:29,450 --> 00:41:31,408
>> DAVID J. Malan: Eu son terrible
en nomes, aparentemente.

1013
00:41:31,408 --> 00:41:34,011
Entón Christine e Gabe,
cuxas mans que cambiar

1014
00:41:34,011 --> 00:41:36,510
cando tentamos eliminar Christine,
número 5, a partir da imaxe?

1015
00:41:36,510 --> 00:41:37,550

1016
00:41:37,550 --> 00:41:38,820
OK, entón imos facer Gabe.

1017
00:41:38,820 --> 00:41:40,950
Gabe vai apuntar,
presuntamente, no número 9.

1018
00:41:40,950 --> 00:41:42,230

1019
00:41:42,230 --> 00:41:44,642
Pero o que debe ocorrer o próximo?

1020
00:41:44,642 --> 00:41:46,600
Audiencia: Christine debería
ser nulo [inaudível].

1021
00:41:46,600 --> 00:41:50,244
DAVID J. Malan: OK, nós temos que ser
make-- escoitei "nulo" en algún lugar.

1022
00:41:50,244 --> 00:41:51,410
Audiencia: Null e liberalo la.

1023
00:41:51,410 --> 00:41:51,855
DAVID J. Malan: null o que?

1024
00:41:51,855 --> 00:41:53,074
Audiencia: Null e liberalo la.

1025
00:41:53,074 --> 00:41:54,490
DAVID J. Malan: Null e liberalo la.

1026
00:41:54,490 --> 00:41:55,422
Entón iso é moi fácil.

1027
00:41:55,422 --> 00:41:58,380
E é perfecto que agora é especie
de pé, non pertencer.

1028
00:41:58,380 --> 00:42:00,430
Porque foi
dissociado da lista.

1029
00:42:00,430 --> 00:42:02,820
Vostede foi eficaz
orfos a partir da lista.

1030
00:42:02,820 --> 00:42:07,770
E así sería mellor chamar gratuitamente agora
Christine dar esa memoria de volta.

1031
00:42:07,770 --> 00:42:10,240
Se non, cada vez que
borrar un nodo da lista

1032
00:42:10,240 --> 00:42:14,230
fósemos facer a lista
máis curto, pero non realmente a diminuír

1033
00:42:14,230 --> 00:42:15,096
o tamaño da memoria.

1034
00:42:15,096 --> 00:42:17,720
E así se continuar a engadir e
engadindo, engadindo cousas para a lista,

1035
00:42:17,720 --> 00:42:19,280
meu ordenador pode ser máis lento
e máis lento e máis lento,

1036
00:42:19,280 --> 00:42:21,740
porque eu estou quedando sen
memoria, aínda que eu non son realmente

1037
00:42:21,740 --> 00:42:25,580
usando bytes de Christine
de memoria máis.

1038
00:42:25,580 --> 00:42:28,500
>> Entón, ao final, hai outra
escenarios, de eliminación course--

1039
00:42:28,500 --> 00:42:30,640
no medio, a eliminación
ao final, como vimos.

1040
00:42:30,640 --> 00:42:32,348
Pero o máis interesante
reto agora é

1041
00:42:32,348 --> 00:42:34,770
será a considerar exactamente
que o tempo de execución é.

1042
00:42:34,770 --> 00:42:36,640
Así, non só pode manter a súa
anacos de papel, se, Gabe,

1043
00:42:36,640 --> 00:42:38,640
non lle importaría de dar
todo un balón antiestrés.

1044
00:42:38,640 --> 00:42:42,100
Moitas grazas á nosa lista ligada
de voluntarios aquí, se puidese.

1045
00:42:42,100 --> 00:42:45,320
>> [Aplausos]

1046
00:42:45,320 --> 00:42:46,700
>> DAVID J. Malan: Todo ben.

1047
00:42:46,700 --> 00:42:51,110
Así, un par de analítica
preguntas, entón, se eu puidese.

1048
00:42:51,110 --> 00:42:59,670
Xa vimos que antes de notación,
O grande e omega, límites superiores

1049
00:42:59,670 --> 00:43:02,520
e límites máis baixos no
tempo de funcionamento dun algoritmo.

1050
00:43:02,520 --> 00:43:04,950
Entón, imos considerar só
un par de preguntas.

1051
00:43:04,950 --> 00:43:07,090
>> Un deles, e nós dixemos que
antes, o que é o funcionamento

1052
00:43:07,090 --> 00:43:10,647
tempo de busca por un
lista en termos de gran O?

1053
00:43:10,647 --> 00:43:13,480
¿Que é un límite superior sobre o funcionamento
tempo de busca dunha lista ligada

1054
00:43:13,480 --> 00:43:16,340
como aplicado polos nosos voluntarios aquí?

1055
00:43:16,340 --> 00:43:17,820
É grande o de n, lineal.

1056
00:43:17,820 --> 00:43:20,630
Porque, no peor dos casos,
o elemento, como 55,

1057
00:43:20,630 --> 00:43:23,830
que pode estar a buscar pode ser onde
Jack era, todo o camiño ao final.

1058
00:43:23,830 --> 00:43:28,250
E, por desgraza, a diferenza dun array
non podemos comezar a fantasía neste momento.

1059
00:43:28,250 --> 00:43:31,820
A pesar de todos os nosos seres humanos eran
clasificadas desde pequenos elementos, 5,

1060
00:43:31,820 --> 00:43:35,900
todo o camiño ata o elemento de maior,
55, que xeralmente é unha cousa boa.

1061
00:43:35,900 --> 00:43:38,815
Pero o que fai esa suposición
xa non nos permiten facer?

1062
00:43:38,815 --> 00:43:39,775

1063
00:43:39,775 --> 00:43:40,650
Audiencia: [inaudível]

1064
00:43:40,650 --> 00:43:40,920
DAVID J. Malan: Diga de novo?

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
E á súa vez, isto significa que non podemos
máis usar ceros feble, intuición,

1068
00:43:46,330 --> 00:43:49,365
e evidencia de uso de binarios
buscar e dividir e conquistar.

1069
00:43:49,365 --> 00:43:51,240
Porque, aínda nos
os seres humanos poderían obviamente

1070
00:43:51,240 --> 00:43:54,610
ver que Andy é Christian foron
máis ou menos no medio da lista,

1071
00:43:54,610 --> 00:43:57,670
só sabemos que como un
ordenador por desnatação á lista

1072
00:43:57,670 --> 00:43:59,029
dende o principio.

1073
00:43:59,029 --> 00:44:00,570
Entón, nós temos que desistiu de acceso aleatorio.

1074
00:44:00,570 --> 00:44:04,380
>> Tan grande O de n agora é o superior
grazas no noso tempo de busca.

1075
00:44:04,380 --> 00:44:07,920
E sobre omega de nosa procura?

1076
00:44:07,920 --> 00:44:11,535
Cal é o límite inferior na busca
para algún número nesta lista?

1077
00:44:11,535 --> 00:44:12,410
Audiencia: [inaudível]

1078
00:44:12,410 --> 00:44:13,040
DAVID J. Malan: Diga de novo?

1079
00:44:13,040 --> 00:44:13,420
Audiencia: One.

1080
00:44:13,420 --> 00:44:13,800
DAVID J. Malan: One.

1081
00:44:13,800 --> 00:44:14,760
Tempo tan constante.

1082
00:44:14,760 --> 00:44:17,020
No mellor dos casos, é Christine
de feito, no inicio da lista.

1083
00:44:17,020 --> 00:44:19,020
E nós estamos a buscar
número 5, de xeito que a atopou.

1084
00:44:19,020 --> 00:44:19,787
Polo tanto, non é gran cousa.

1085
00:44:19,787 --> 00:44:22,370
Pero ela ten que estar no
inicio da lista, neste caso.

1086
00:44:22,370 --> 00:44:23,745
Que tal algo como eliminar?

1087
00:44:23,745 --> 00:44:24,717

1088
00:44:24,717 --> 00:44:26,300
E se queres eliminar un elemento?

1089
00:44:26,300 --> 00:44:29,200
Cal é o límite superior e límite inferior
sobre a eliminación de algo a partir dun conectado

1090
00:44:29,200 --> 00:44:29,699
lista?

1091
00:44:29,699 --> 00:44:35,195

1092
00:44:35,195 --> 00:44:36,070
Audiencia: [inaudível]

1093
00:44:36,070 --> 00:44:36,420
DAVID J. Malan: Diga de novo?

1094
00:44:36,420 --> 00:44:37,067
Audiencia: n.

1095
00:44:37,067 --> 00:44:38,900
David J. Malan: n é
en realidade, o límite superior.

1096
00:44:38,900 --> 00:44:41,700
Porque, no peor caso intentamos
eliminar Jack, como acabamos de facer.

1097
00:44:41,700 --> 00:44:43,050
El é todo o camiño ao final.

1098
00:44:43,050 --> 00:44:45,419
Leva connosco para sempre, ou
n pasos para atopalo.

1099
00:44:45,419 --> 00:44:46,460
Entón, iso é un límite superior.

1100
00:44:46,460 --> 00:44:47,430
Isto é lineal, con certeza.

1101
00:44:47,430 --> 00:44:50,970
E o mellor caso de tempo de execución, ou
os límites inferiores no mellor dos casos

1102
00:44:50,970 --> 00:44:51,975
habería tempo constante.

1103
00:44:51,975 --> 00:44:54,600
Porque quizais a xente probe eliminar
Christine, e só ter sorte

1104
00:44:54,600 --> 00:44:55,558
está no comezo.

1105
00:44:55,558 --> 00:44:56,350
Agora, agarde un minuto.

1106
00:44:56,350 --> 00:44:59,370
Gabe tamén estaba en principio,
e nós tamén tivemos que actualizar Gabe.

1107
00:44:59,370 --> 00:45:01,150
Para que non foi só un paso.

1108
00:45:01,150 --> 00:45:04,210
Entón é iso, xa constante
tempo, no mellor dos casos,

1109
00:45:04,210 --> 00:45:06,345
para eliminar o elemento máis pequeno?

1110
00:45:06,345 --> 00:45:07,360

1111
00:45:07,360 --> 00:45:10,960
É, aínda que poida ser de dous,
tres, ou ata 100 liñas de código,

1112
00:45:10,960 --> 00:45:14,000
se é o mesmo número de
liñas, non en algún loop,

1113
00:45:14,000 --> 00:45:16,577
e independente do tamaño
da lista, con certeza.

1114
00:45:16,577 --> 00:45:18,660
Excluíndo o elemento no
o inicio da lista,

1115
00:45:18,660 --> 00:45:21,940
aínda que teñamos de xestionar
Gabe, aínda é tempo constante.

1116
00:45:21,940 --> 00:45:24,220
>> Polo tanto, este parece ser un
enorme paso atrás.

1117
00:45:24,220 --> 00:45:27,000
E o que é un desperdicio de tempo
Se, nunha semana e na semana

1118
00:45:27,000 --> 00:45:30,250
cero, tivemos non só
código pseudocódigo que o código real

1119
00:45:30,250 --> 00:45:35,780
para aplicar algo que é rexistro
base de n, ou rexistro, no seu lugar, de n, base 2,

1120
00:45:35,780 --> 00:45:37,150
en termos do seu tempo de execución.

1121
00:45:37,150 --> 00:45:40,710
Entón, por que diaños sería queremos comezar
usando algo así como unha lista ligada?

1122
00:45:40,710 --> 00:45:41,517
Si.

1123
00:45:41,517 --> 00:45:44,022
>> Audiencia: Entón, pode engadir
elementos para a matriz.

1124
00:45:44,022 --> 00:45:46,230
DAVID J. Malan: Entón pode
engadir elementos á matriz.

1125
00:45:46,230 --> 00:45:47,550
E iso tamén é temática.

1126
00:45:47,550 --> 00:45:49,740
E imos seguir vendo
este, este trade-off, moi

1127
00:45:49,740 --> 00:45:51,573
como xa vimos un
trade-off con merge sort.

1128
00:45:51,573 --> 00:45:54,606
Nós realmente podería acelerar
buscar ou clasificar, no seu lugar,

1129
00:45:54,606 --> 00:45:57,480
se pasar un pouco máis de espazo e
ten un anaco dunha memoria adicional

1130
00:45:57,480 --> 00:45:58,760
ou unha matriz a merge sort.

1131
00:45:58,760 --> 00:46:01,270
Pero nós gastamos máis
espazo, pero aforrar tempo.

1132
00:46:01,270 --> 00:46:04,820
Neste caso, estamos
dando-se tempo, pero estamos

1133
00:46:04,820 --> 00:46:08,170
gañando flexibilidade,
dinamismo, se quixeren,

1134
00:46:08,170 --> 00:46:10,280
que é sen dúbida unha característica positiva.

1135
00:46:10,280 --> 00:46:11,520
>> Tamén estamos gastando espazo.

1136
00:46:11,520 --> 00:46:13,710
En que sentido é un conectado
consultar máis caro

1137
00:46:13,710 --> 00:46:15,700
en termos de espazo dunha matriz?

1138
00:46:15,700 --> 00:46:18,379

1139
00:46:18,379 --> 00:46:19,920
Onde está o espazo extra vén?

1140
00:46:19,920 --> 00:46:20,460
Si?

1141
00:46:20,460 --> 00:46:21,800
>> Audiencia: punteiro [inaudível].

1142
00:46:21,800 --> 00:46:23,310
>> DAVID J. Malan: Si, nós
tamén ten o punteiro.

1143
00:46:23,310 --> 00:46:25,560
Entón, iso é aburrido minorly
en que non son máis

1144
00:46:25,560 --> 00:46:27,780
Eu gardar só un int
representar un int.

1145
00:46:27,780 --> 00:46:30,990
Eu son almacenar un int e un
anotador, que é tamén de 32 bits.

1146
00:46:30,990 --> 00:46:33,470
Entón, eu estou literalmente dobrando
a cantidade de espazo parte.

1147
00:46:33,470 --> 00:46:36,040
Entón iso é un trade-off, pero
que é, no caso de int.

1148
00:46:36,040 --> 00:46:39,580
Supoña que non está almacenando int,
pero supoño que cada un destes rectángulos

1149
00:46:39,580 --> 00:46:43,290
ou cada un destes seres humanos estaba representando
unha palabra, unha palabra en inglés que

1150
00:46:43,290 --> 00:46:46,430
pode ser de cinco caracteres, 10
caracteres, quizais ata máis.

1151
00:46:46,430 --> 00:46:49,940
Logo, engadindo só 32 máis bits
pode ser menos de un gran negocio.

1152
00:46:49,940 --> 00:46:52,160
>> Que cada un dos estudantes
na manifestación

1153
00:46:52,160 --> 00:46:55,107
foron literalmente estruturas estudantís que
teñen nomes e casas e quizais

1154
00:46:55,107 --> 00:46:57,065
números de teléfono e Twitter
trata e similares.

1155
00:46:57,065 --> 00:46:59,564
Así, todos os campos que comezamos
falando o outro día,

1156
00:46:59,564 --> 00:47:02,410
moito menos de un gran negocio,
nosos nós están máis interesantes

1157
00:47:02,410 --> 00:47:05,972
e gran para gastar, eh, un adicional
punteiro só para conecta-los.

1158
00:47:05,972 --> 00:47:07,180
Pero, en realidade, é un trade-off.

1159
00:47:07,180 --> 00:47:09,560
E, de feito, o código é
máis complexa, como vai

1160
00:47:09,560 --> 00:47:11,770
ver ao percorre
que o exemplo concreto.

1161
00:47:11,770 --> 00:47:14,302
Pero o que se había
algún Santo Graal aquí.

1162
00:47:14,302 --> 00:47:17,010
E se nós non dar un paso
cara atrás, pero un gran paso para adiante

1163
00:47:17,010 --> 00:47:19,180
e aplicar un conxunto de datos
estrutura a través do cal se

1164
00:47:19,180 --> 00:47:22,870
pode atopar elementos como Jack ou
Christine ou outros elementos

1165
00:47:22,870 --> 00:47:25,870
nesa matriz en certo tempo constante?

1166
00:47:25,870 --> 00:47:26,920
A procura é constante.

1167
00:47:26,920 --> 00:47:28,320
Eliminar é constante.

1168
00:47:28,320 --> 00:47:29,570
Insert é constante.

1169
00:47:29,570 --> 00:47:32,260
Todas estas operacións son constantes.

1170
00:47:32,260 --> 00:47:33,750
Iso sería o noso Santo Graal.

1171
00:47:33,750 --> 00:47:36,690
E é aí onde nós
vai pegar a próxima vez.

1172
00:47:36,690 --> 00:47:38,600
Vexo vostedes despois.

1173
00:47:38,600 --> 00:47:39,371