1
00:00:00,000 --> 00:00:03,381
>> [Música tocando]

2
00:00:03,381 --> 00:00:10,626

3
00:00:10,626 --> 00:00:11,610
>> [REPRODUÇÃO DE VÍDEO]

4
00:00:11,610 --> 00:00:13,640
>> -Ele está mentindo.

5
00:00:13,640 --> 00:00:14,380
>> -Sobre o que?

6
00:00:14,380 --> 00:00:17,182
>> -Eu não sei.

7
00:00:17,182 --> 00:00:19,990
>> -Então, O que sabemos?

8
00:00:19,990 --> 00:00:23,145
>> -Isso Às 9:15, Ray
Santoya estava no caixa eletrônico.

9
00:00:23,145 --> 00:00:23,644
-Sim.

10
00:00:23,644 --> 00:00:27,030
Então a questão é, o que
ele estava fazendo em 09:16?

11
00:00:27,030 --> 00:00:29,720
>> -Shooting A nove milímetros em alguma coisa.

12
00:00:29,720 --> 00:00:31,540
Talvez ele viu o atirador.

13
00:00:31,540 --> 00:00:33,412
>> -Ou Estava trabalhando com ele.

14
00:00:33,412 --> 00:00:34,340
>> -Aguarde.

15
00:00:34,340 --> 00:00:36,200
Volte um.

16
00:00:36,200 --> 00:00:36,975
>> -O que você vê?

17
00:00:36,975 --> 00:00:44,400

18
00:00:44,400 --> 00:00:47,805
>> -Trazer O rosto para cima tela cheia.

19
00:00:47,805 --> 00:00:48,680
>> Vidros -His.

20
00:00:48,680 --> 00:00:50,060
>> -Há Uma reflexão.

21
00:00:50,060 --> 00:01:00,455

22
00:01:00,455 --> 00:01:02,280
>> -É O time de beisebol Nuevitas.

23
00:01:02,280 --> 00:01:03,110
Esse é o seu logotipo.

24
00:01:03,110 --> 00:01:05,820
>> -E Ele está falando com
quem está usando aquela jaqueta.

25
00:01:05,820 --> 00:01:06,670
>> [FIM DE REPRODUÇÃO]

26
00:01:06,670 --> 00:01:07,628
>> DAVID MALAN: Tudo bem.

27
00:01:07,628 --> 00:01:11,210
Esta é CS50 e isso é um pouco mais
de [inaudível] com a qual você está

28
00:01:11,210 --> 00:01:12,890
brincar com problema definir quatro.

29
00:01:12,890 --> 00:01:16,606
Hoje começamos a olhar um pouco mais
profundamente para essas coisas chamadas ponteiros,

30
00:01:16,606 --> 00:01:18,480
que apesar de ser
um tópico muito misterioso,

31
00:01:18,480 --> 00:01:20,813
verifica-se que ele vai
a ser o meio através do qual nós

32
00:01:20,813 --> 00:01:24,320
pode começar a construir e montar
programas muito mais sofisticado.

33
00:01:24,320 --> 00:01:28,150
Mas o que fizemos na quarta-feira passada
por meio de alguns claymation primeiro.

34
00:01:28,150 --> 00:01:30,190
Portanto, este, recall, é
Binky e usamos-lo

35
00:01:30,190 --> 00:01:33,148
para dar uma olhada em um programa que
realmente não faz nada de interessante,

36
00:01:33,148 --> 00:01:34,950
mas revelou alguns problemas.

37
00:01:34,950 --> 00:01:38,570
Então, para começar hoje, por que não podemos andar
rapidamente através de alguns destes passos,

38
00:01:38,570 --> 00:01:41,920
tentar destilar em termos de humanos
exatamente o que está acontecendo aqui

39
00:01:41,920 --> 00:01:45,410
e por que isso é ruim, e, em seguida, seguir em frente
e realmente começar a construir algo

40
00:01:45,410 --> 00:01:46,309
com esta técnica?

41
00:01:46,309 --> 00:01:48,350
Então, esses foram os primeiros
duas linhas neste programa

42
00:01:48,350 --> 00:01:51,340
e em termos leigos, o que
são estas duas linhas fazendo?

43
00:01:51,340 --> 00:01:55,600
Alguém que é razoavelmente confortável
com o que está declarado na tela?

44
00:01:55,600 --> 00:01:58,340

45
00:01:58,340 --> 00:02:00,120
Quais são essas duas linhas que fazem?

46
00:02:00,120 --> 00:02:02,070
Não é tudo o que
diferente de uma semana,

47
00:02:02,070 --> 00:02:03,611
mas há algum novo símbolo especial.

48
00:02:03,611 --> 00:02:04,152
Sim?

49
00:02:04,152 --> 00:02:05,628
Ali atrás.

50
00:02:05,628 --> 00:02:07,092
>> AUDIÊNCIA: Declarando ponteiros?

51
00:02:07,092 --> 00:02:08,050
DAVID MALAN: Diga outra vez?

52
00:02:08,050 --> 00:02:08,860
AUDIÊNCIA: Declarando ponteiros?

53
00:02:08,860 --> 00:02:11,776
DAVID MALAN: Declarando e ponteiros
Vamos refiná-lo um pouco mais.

54
00:02:11,776 --> 00:02:14,050
AUDIÊNCIA: [inaudível]
endereço e, em seguida, x y.

55
00:02:14,050 --> 00:02:15,300
DAVID MALAN: E, em seguida, abordar.

56
00:02:15,300 --> 00:02:18,550
Então, especificamente o que estamos fazendo
é que estamos a declarar duas variáveis.

57
00:02:18,550 --> 00:02:21,252
Essas variáveis, no entanto, vão
para ser do tipo int estrela, que

58
00:02:21,252 --> 00:02:23,210
significa mais especificamente
eles estão indo para armazenar

59
00:02:23,210 --> 00:02:26,450
o endereço de um int,
respectivamente, X e Y.

60
00:02:26,450 --> 00:02:27,660
Agora existem quaisquer valores?

61
00:02:27,660 --> 00:02:32,621
Há algum endereços reais nestes
duas variáveis ​​neste momento no tempo?

62
00:02:32,621 --> 00:02:33,120
Não.

63
00:02:33,120 --> 00:02:35,030
É apenas chamados valores de lixo.

64
00:02:35,030 --> 00:02:38,120
Se você realmente não atribuir um
variável, o que estava na RAM

65
00:02:38,120 --> 00:02:42,224
anteriormente vai preencher com zeros
e as duas dessas variáveis.

66
00:02:42,224 --> 00:02:44,140
Mas nós ainda não sabemos
o que são e que é

67
00:02:44,140 --> 00:02:47,060
vai ser a chave para por que Binky
perdeu a cabeça na semana passada.

68
00:02:47,060 --> 00:02:49,980
>> Portanto, este foi o claymation
encarnação do presente

69
00:02:49,980 --> 00:02:53,580
em que você tem apenas duas variáveis,
pequenos pedaços circulares de argila,

70
00:02:53,580 --> 00:02:57,330
que pode armazenar variáveis, mas quanto
as setas envolvidas acima sugerem,

71
00:02:57,330 --> 00:03:00,640
eles não estão realmente apontando
para qualquer lugar conhecido per se.

72
00:03:00,640 --> 00:03:03,670
Então, depois, teve esta linha, e esta
era novo na semana passada, malloc para a memória

73
00:03:03,670 --> 00:03:07,130
atribuição, que é apenas uma maneira elegante
de dizer ao sistema operacional, Linux

74
00:03:07,130 --> 00:03:09,750
ou Mac OS ou Windows,
hey, me dê um pouco de memória,

75
00:03:09,750 --> 00:03:11,780
e tudo que você tem a dizer
o sistema operativo

76
00:03:11,780 --> 00:03:14,699
é o que quando pedindo-lhe para a memória.

77
00:03:14,699 --> 00:03:16,990
Ele não vai se importar com o
você vai fazer com ele,

78
00:03:16,990 --> 00:03:19,786
mas você precisa dizer ao funcionamento
sistema que por meio de malloc.

79
00:03:19,786 --> 00:03:20,286
Sim?

80
00:03:20,286 --> 00:03:21,078
>> AUDIÊNCIA: Quanto?

81
00:03:21,078 --> 00:03:21,994
DAVID MALAN: Quanto?

82
00:03:21,994 --> 00:03:25,280
Quanto em bytes, e assim, este, de novo,
um exemplo artificial, está apenas dizendo,

83
00:03:25,280 --> 00:03:27,360
dá-me o tamanho de um int.

84
00:03:27,360 --> 00:03:30,550
Agora, o tamanho de um int
é de quatro bytes ou 32 bits.

85
00:03:30,550 --> 00:03:32,850
Portanto, esta é apenas uma forma de
dizendo, hey, sistema operacional,

86
00:03:32,850 --> 00:03:37,290
dá-me quatro bytes de memória
que eu posso usar a minha disposição,

87
00:03:37,290 --> 00:03:40,560
e, especificamente, o que faz
retorno malloc com respeito

88
00:03:40,560 --> 00:03:41,795
para esse pedaço de quatro bytes?

89
00:03:41,795 --> 00:03:44,110

90
00:03:44,110 --> 00:03:44,860
AUDIÊNCIA: Morada?

91
00:03:44,860 --> 00:03:45,901
DAVID MALAN: O endereço.

92
00:03:45,901 --> 00:03:47,580
O endereço desse pedaço de quatro bytes.

93
00:03:47,580 --> 00:03:48,190
Exatamente.

94
00:03:48,190 --> 00:03:51,430
E é isso o que está armazenado em última análise,
em x e é por isso que nós realmente não

95
00:03:51,430 --> 00:03:55,240
importo com o que o número de que
endereço é, se é OX1 ou ox2

96
00:03:55,240 --> 00:03:57,110
ou algum endereço hexadecimal enigmática.

97
00:03:57,110 --> 00:03:59,850
Nós apenas cuidar pictoricamente
que essa variável x é agora

98
00:03:59,850 --> 00:04:01,630
apontando para que o pedaço de memória.

99
00:04:01,630 --> 00:04:05,570
Assim, a seta representa um ponteiro, ou
mais especificamente, um endereço de memória.

100
00:04:05,570 --> 00:04:09,120
Mas, novamente, não importa tipicamente
o que esses endereços são reais.

101
00:04:09,120 --> 00:04:11,780
Agora, esta linha diz
o que em termos leigos?

102
00:04:11,780 --> 00:04:14,330
Estrela x recebe 42 ponto e vírgula.

103
00:04:14,330 --> 00:04:17,390
O que isto significa?

104
00:04:17,390 --> 00:04:18,200
Você quer ir?

105
00:04:18,200 --> 00:04:20,102
Não arranhe seu pescoço.

106
00:04:20,102 --> 00:04:22,360
>> AUDIÊNCIA: O endereço de x está no 42.

107
00:04:22,360 --> 00:04:24,300
>> DAVID MALAN: O endereço de x é a 42.

108
00:04:24,300 --> 00:04:25,190
Não é bem assim.

109
00:04:25,190 --> 00:04:28,485
Tão perto, mas não completamente, porque não há
a estrela que está prefixing este x.

110
00:04:28,485 --> 00:04:29,860
Por isso, precisamos de ajustar um pouco.

111
00:04:29,860 --> 00:04:31,032
Sim?

112
00:04:31,032 --> 00:04:36,044
>> AUDIÊNCIA: O valor que o
ponteiro x está apontando para é de 42.

113
00:04:36,044 --> 00:04:36,710
DAVID MALAN: OK.

114
00:04:36,710 --> 00:04:40,840
O valor que o ponteiro x é
apontando para, digamos, será 42,

115
00:04:40,840 --> 00:04:44,165
ou dito de outra forma, a estrela
x diz, ir para qualquer outro endereço

116
00:04:44,165 --> 00:04:48,340
está em x, quer se trate de uma Oxford
Rua 33 ou Oxford Street

117
00:04:48,340 --> 00:04:51,850
ou OX1 ou ox33, qualquer que seja
que endereço numérico é,

118
00:04:51,850 --> 00:04:54,380
estrela x é a dereferencing de x.

119
00:04:54,380 --> 00:04:57,297
Então, vá para esse endereço e
em seguida, colocar o número 42 lá.

120
00:04:57,297 --> 00:04:59,380
Assim que seria um
maneira equivalente a dizer isso.

121
00:04:59,380 --> 00:05:01,860
Então, isso é tudo muito bem e, em seguida,
que representaria a imagem

122
00:05:01,860 --> 00:05:05,370
como se segue, onde nós adicionamos
o 42 a esse pedaço de quatro

123
00:05:05,370 --> 00:05:09,370
bytes na lateral direita, mas
esta linha foi onde as coisas deram errado

124
00:05:09,370 --> 00:05:11,120
ea cabeça de Binky estalou
fora neste ponto,

125
00:05:11,120 --> 00:05:15,290
porque coisas ruins acontecem quando
você dereference valores de lixo

126
00:05:15,290 --> 00:05:18,210
ou você cancelar a referência inválida
ponteiros, e eu digo inválido

127
00:05:18,210 --> 00:05:21,020
porque neste momento no
história, o que está dentro de y?

128
00:05:21,020 --> 00:05:24,440
Qual é o valor de base y
nas poucas etapas passadas?

129
00:05:24,440 --> 00:05:25,360
Sim?

130
00:05:25,360 --> 00:05:26,115
O que é isso?

131
00:05:26,115 --> 00:05:26,990
>> AUDIÊNCIA: Um endereço.

132
00:05:26,990 --> 00:05:28,460
DAVID MALAN: Um endereço.

133
00:05:28,460 --> 00:05:31,910
Deve ser um endereço
mas tenho inicializado-lo?

134
00:05:31,910 --> 00:05:32,800
Então eu não tenho ainda.

135
00:05:32,800 --> 00:05:35,430
Então, o que é conhecido por ser aí?

136
00:05:35,430 --> 00:05:37,590
É apenas algum valor de lixo.

137
00:05:37,590 --> 00:05:41,500
Poderia ser qualquer endereço de zero a
2 bilhões se você tiver dois GB de RAM,

138
00:05:41,500 --> 00:05:44,289
ou zero a 4 bilhões se você tiver
tem quatro gigabytes de RAM.

139
00:05:44,289 --> 00:05:46,080
É algum valor de lixo,
mas o problema é

140
00:05:46,080 --> 00:05:48,200
que o sistema operacional,
se ele não lhe deu

141
00:05:48,200 --> 00:05:51,140
que pedaço de memória especificamente
que você está tentando ir,

142
00:05:51,140 --> 00:05:54,650
ele vai geralmente para causar o que
temos visto como uma falha de segmentação.

143
00:05:54,650 --> 00:05:57,810
Então, na verdade, qualquer um de vocês que têm
esforçou-se em problemas no horário de expediente

144
00:05:57,810 --> 00:06:00,393
ou em problemas que é mais
geralmente com tentando descobrir

145
00:06:00,393 --> 00:06:02,150
uma falha de segmentação,
que geralmente significa

146
00:06:02,150 --> 00:06:05,017
você está tocando um segmento de
memória que você não deve ser.

147
00:06:05,017 --> 00:06:07,350
Você está tocando memória que
o sistema operacional não tem

148
00:06:07,350 --> 00:06:10,450
permitiu-lhe tocar, se é
por ir longe demais em sua matriz

149
00:06:10,450 --> 00:06:12,870
ou a partir de agora, se
é porque você está tocando

150
00:06:12,870 --> 00:06:14,780
memória que é apenas algum valor de lixo.

151
00:06:14,780 --> 00:06:18,230
>> Assim fazendo estrela x aqui é
tipo de comportamento indefinido.

152
00:06:18,230 --> 00:06:22,030
Você nunca deve fazê-lo porque as probabilidades
são, o programa só vai falhar,

153
00:06:22,030 --> 00:06:24,050
porque você está dizendo,
vá a este endereço

154
00:06:24,050 --> 00:06:27,000
e você não tem idéia de onde
esse endereço realmente é.

155
00:06:27,000 --> 00:06:30,300
Assim, o sistema operacional é provável
indo para travar o seu programa

156
00:06:30,300 --> 00:06:33,840
como resultado e, na verdade, isso é
o que aconteceu lá para Binky.

157
00:06:33,840 --> 00:06:37,210
Então, finalmente, fixado Binky
este problema com este.

158
00:06:37,210 --> 00:06:38,909
Assim que o programa em si foi falho.

159
00:06:38,909 --> 00:06:41,450
Mas se você espécie de avançar
e executar essa linha em vez disso,

160
00:06:41,450 --> 00:06:45,580
y é igual x significa apenas o que quer
endereço é um x, também colocá-lo em y.

161
00:06:45,580 --> 00:06:48,740
>> E assim pictoricamente, nós temos
esta representada com duas setas

162
00:06:48,740 --> 00:06:51,570
a partir de x e de y apontador
para o mesmo local.

163
00:06:51,570 --> 00:06:55,760
Assim semanticamente, x é igual
para y, porque ambos daqueles

164
00:06:55,760 --> 00:07:00,300
armazenar a mesma
endereço, ergo apontando para 42,

165
00:07:00,300 --> 00:07:04,910
e agora, quando você diz estrela
y, vá para o endereço em y,

166
00:07:04,910 --> 00:07:06,790
este tem um efeito secundário interessante.

167
00:07:06,790 --> 00:07:10,320
Assim, o endereço em que y é a
mesma coisa que o endereço em x.

168
00:07:10,320 --> 00:07:15,060
Então, se você diz que ir para o endereço
em y e altere o valor para 13,

169
00:07:15,060 --> 00:07:17,140
Quem mais é afetado?

170
00:07:17,140 --> 00:07:21,100
X é, ponto D, por assim dizer,
devem ser afetados também.

171
00:07:21,100 --> 00:07:24,340
>> E, de fato, como Nick tirei esta imagem
em claymation foi exatamente isso.

172
00:07:24,340 --> 00:07:28,665
Mesmo que nós seguimos o ponteiro
y, acabamos no mesmo lugar,

173
00:07:28,665 --> 00:07:32,780
e assim se estivéssemos a imprimir
out x ou y de pointee,

174
00:07:32,780 --> 00:07:35,720
então veríamos o valor de 13.

175
00:07:35,720 --> 00:07:37,927
Agora, eu digo pointee ser
consistente com o vídeo.

176
00:07:37,927 --> 00:07:39,760
Programmers, ao meu
conhecimento, nunca realmente

177
00:07:39,760 --> 00:07:42,460
dizer a palavra pointee,
o que está apontado

178
00:07:42,460 --> 00:07:44,650
no, mas a consistência
com o vídeo, percebe

179
00:07:44,650 --> 00:07:47,520
isso é tudo o que era
significava nessa situação.

180
00:07:47,520 --> 00:07:54,190
Assim dúvidas sobre claymation
ou ponteiros ou apenas malloc ainda?

181
00:07:54,190 --> 00:07:54,850
Não?

182
00:07:54,850 --> 00:07:55,470
Tudo certo.

183
00:07:55,470 --> 00:07:58,560
>> Assim, sem mais
delongas, vamos dar uma olhada

184
00:07:58,560 --> 00:08:00,700
para onde isso tem realmente
sido utilizado durante algum tempo.

185
00:08:00,700 --> 00:08:03,580
Então nós tivemos esta biblioteca CS50
que tem todas essas funções.

186
00:08:03,580 --> 00:08:06,810
Nós usamos GetInt muito, GetString,
provavelmente GetLongLong anterior

187
00:08:06,810 --> 00:08:09,840
Na minha PSet um ou mais, mas
o que está realmente acontecendo?

188
00:08:09,840 --> 00:08:12,920
Bem, vamos dar uma olhada rápida
por baixo do capuz com um programa que

189
00:08:12,920 --> 00:08:17,017
inspira por que nós damos-lhe o CS50
biblioteca, e de fato como da semana passada,

190
00:08:17,017 --> 00:08:18,850
que começou a tomar os
rodinhas.

191
00:08:18,850 --> 00:08:21,080
Então, isso agora está classificada
de um post-mortem do que

192
00:08:21,080 --> 00:08:23,690
já se arrasta
dentro da biblioteca CS50,

193
00:08:23,690 --> 00:08:27,250
mesmo que agora vai começar a se mover
longe dela para a maioria dos programas.

194
00:08:27,250 --> 00:08:29,460
>> Portanto, este é um programa chamado scanf 0.

195
00:08:29,460 --> 00:08:30,510
É super curta.

196
00:08:30,510 --> 00:08:33,909
Ele só tem estas linhas, mas
introduz uma função chamada scanf

197
00:08:33,909 --> 00:08:36,909
que na verdade estamos indo para ver em
um momento no interior da biblioteca CS50,

198
00:08:36,909 --> 00:08:38,600
embora de uma forma um pouco diferente.

199
00:08:38,600 --> 00:08:41,330
Portanto, este programa na linha 16
é declarar uma variável x.

200
00:08:41,330 --> 00:08:43,150
Então me dê quatro bytes para um int.

201
00:08:43,150 --> 00:08:45,750
Ele tem dito a usuário,
número por favor, e, em seguida,

202
00:08:45,750 --> 00:08:49,010
esta é uma linha que interessante
realmente une na semana passada

203
00:08:49,010 --> 00:08:49,790
e isso.

204
00:08:49,790 --> 00:08:53,230
Scanf, e, em seguida, perceber que é preciso um
formato de cadeia, assim como printf,

205
00:08:53,230 --> 00:08:57,480
% i significa um int, e, em seguida, leva um
segundo argumento que parece um pouco

206
00:08:57,480 --> 00:08:58,260
descolados.

207
00:08:58,260 --> 00:09:01,880
É ampersand x, e para recordar,
nós só vi isso uma vez na semana passada.

208
00:09:01,880 --> 00:09:03,465
O que faz e comercial x representam?

209
00:09:03,465 --> 00:09:06,210

210
00:09:06,210 --> 00:09:08,450
O que fazer em C e comercial?

211
00:09:08,450 --> 00:09:08,950
Sim?

212
00:09:08,950 --> 00:09:10,024
>> AUDIÊNCIA: O endereço de.

213
00:09:10,024 --> 00:09:11,190
DAVID MALAN: O endereço de.

214
00:09:11,190 --> 00:09:13,190
Portanto, é o oposto
o operador de estrela,

215
00:09:13,190 --> 00:09:17,270
enquanto o operador estrela diz, ir para
Neste endereço, o operador E comercial

216
00:09:17,270 --> 00:09:20,280
diz, descobrir a
endereço dessa variável,

217
00:09:20,280 --> 00:09:23,530
e por isso esta é a chave, porque
O propósito de scanf na vida

218
00:09:23,530 --> 00:09:26,320
é verificar o usuário de
a entrada do teclado,

219
00:09:26,320 --> 00:09:29,970
dependendo do que ele ou ela
tipos, e, em seguida, ler a entrada desse usuário

220
00:09:29,970 --> 00:09:32,970
em uma variável, mas nós
viu nas últimas duas semanas

221
00:09:32,970 --> 00:09:36,080
que a referida função de comutação que nós
tentou sem esforço para implementar

222
00:09:36,080 --> 00:09:37,110
só estava quebrado.

223
00:09:37,110 --> 00:09:42,470
Lembre-se que com a função swap,
se nós apenas declarado A e B como ints,

224
00:09:42,470 --> 00:09:47,040
fizemos trocar com sucesso o
duas variáveis ​​dentro de troca

225
00:09:47,040 --> 00:09:50,080
Assim como com o leite e JO,
mas assim como swap voltou,

226
00:09:50,080 --> 00:09:55,200
qual foi o resultado com respeito
a x e y, os valores originais?

227
00:09:55,200 --> 00:09:55,700
Nenhuma coisa.

228
00:09:55,700 --> 00:09:56,200
Sim.

229
00:09:56,200 --> 00:09:59,754
Nada aconteceu naquela época, porque
swaps alterar apenas suas cópias locais,

230
00:09:59,754 --> 00:10:01,670
o que quer dizer, todos
desta vez, sempre que temos

231
00:10:01,670 --> 00:10:04,010
foi passando argumentos
às funções, estamos

232
00:10:04,010 --> 00:10:05,939
só de passagem cópias desses argumentos.

233
00:10:05,939 --> 00:10:07,980
Você pode fazer com que
o que quiser com eles,

234
00:10:07,980 --> 00:10:10,890
mas eles vão ter nenhum
efeito sobre os valores originais.

235
00:10:10,890 --> 00:10:13,650
Então, isso é problemático se você
quero ter uma função como scanf

236
00:10:13,650 --> 00:10:17,170
na vida, cujo objetivo é fazer a varredura
a entrada do usuário a partir do teclado

237
00:10:17,170 --> 00:10:22,010
e depois preencher os espaços em branco, de modo a
falar, isto é, dar uma variável como x

238
00:10:22,010 --> 00:10:25,410
um valor, porque se eu fosse
apenas para passar x para scanf,

239
00:10:25,410 --> 00:10:28,790
se você considerar a lógica da última
semana, scanf pode fazer o que quiser

240
00:10:28,790 --> 00:10:33,100
com uma cópia de x, mas não podia
alterar permanentemente x a menos que nós damos

241
00:10:33,100 --> 00:10:37,120
scanf um mapa do tesouro, por assim dizer,
onde X marca o local, em que

242
00:10:37,120 --> 00:10:41,860
passamos o endereço de x para que
scanf pode ir lá e realmente mudar

243
00:10:41,860 --> 00:10:42,920
o valor de x.

244
00:10:42,920 --> 00:10:45,080
E assim, de fato, todos
que este programa faz

245
00:10:45,080 --> 00:10:53,180
se eu fizer scanf 0, em minha fonte
Diretório 5m, fazer scanf 0,

246
00:10:53,180 --> 00:10:57,730
dot cortar scanf, número
por favor 50, graças ao 50.

247
00:10:57,730 --> 00:11:01,020
>> Portanto, não é tão interessante,
mas o que está de fato acontecendo

248
00:11:01,020 --> 00:11:04,820
é que assim que eu chamo
scanf aqui, o valor de x

249
00:11:04,820 --> 00:11:06,410
está a ser permanentemente alterado.

250
00:11:06,410 --> 00:11:08,335
Agora, isso parece bom e
bom, e na verdade,

251
00:11:08,335 --> 00:11:11,200
Parece que nós realmente não precisa
a biblioteca CS50 em tudo mais.

252
00:11:11,200 --> 00:11:13,960
Por exemplo, vamos executar
isto mais uma vez aqui.

253
00:11:13,960 --> 00:11:15,750
Deixe-me reabri-lo por um segundo.

254
00:11:15,750 --> 00:11:20,600
Vamos tentar um número por favor e
em vez de dizer 50 como antes,

255
00:11:20,600 --> 00:11:22,810
vamos apenas dizer não.

256
00:11:22,810 --> 00:11:24,000
OK, isso é um pouco estranho.

257
00:11:24,000 --> 00:11:25,270
ESTÁ BEM.

258
00:11:25,270 --> 00:11:28,680
E apenas algumas bobagens aqui.

259
00:11:28,680 --> 00:11:31,170
Por isso, não parece
lidar com situações erradas.

260
00:11:31,170 --> 00:11:33,620
Então, precisamos minimamente início
adicionando um pouco de verificação de erros

261
00:11:33,620 --> 00:11:37,460
para se certificar de que o usuário tem
digitado em um número real como 50,

262
00:11:37,460 --> 00:11:40,720
porque, aparentemente, digitando palavras
não é detectada como problemática,

263
00:11:40,720 --> 00:11:42,020
mas provavelmente deve ser.

264
00:11:42,020 --> 00:11:46,450
>> Vamos olhar para esta versão agora que é
minha tentativa de reimplementar GetString.

265
00:11:46,450 --> 00:11:48,437
Se scanf tem tudo isso
funcionalidade incorporada,

266
00:11:48,437 --> 00:11:51,270
por que temos sido a brincar com estas
rodinhas como GetString?

267
00:11:51,270 --> 00:11:55,450
Bem, aqui é, talvez, o meu próprio
versão simples do GetString

268
00:11:55,450 --> 00:12:00,766
em que uma semana atrás, eu poderia ter dito,
dá-me uma corda e chamá-lo de buffer.

269
00:12:00,766 --> 00:12:03,390
Hoje, eu vou começar apenas
dizendo estrela char, que, recall,

270
00:12:03,390 --> 00:12:04,400
é apenas sinônimo.

271
00:12:04,400 --> 00:12:06,629
Parece assustador, mas é
exatamente a mesma coisa.

272
00:12:06,629 --> 00:12:09,420
Então me dê um buffer variável chamada
que está indo para armazenar uma seqüência de caracteres,

273
00:12:09,420 --> 00:12:12,780
dizer a string user por favor,
e, em seguida, como antes,

274
00:12:12,780 --> 00:12:17,760
vamos tentar emprestar esta lição scanf
% s neste momento e, em seguida, passar em tampão.

275
00:12:17,760 --> 00:12:19,310
Agora, uma verificação de sanidade rápida.

276
00:12:19,310 --> 00:12:22,120
Por que não estou dizendo
E comercial tampão desta vez?

277
00:12:22,120 --> 00:12:25,190

278
00:12:25,190 --> 00:12:26,625
Inferir a partir do exemplo anterior.

279
00:12:26,625 --> 00:12:28,000
AUDIÊNCIA: Char estrela é um ponteiro.

280
00:12:28,000 --> 00:12:29,920
DAVID MALAN: Exatamente,
porque este tempo, char

281
00:12:29,920 --> 00:12:34,080
estrela já é um ponteiro, um endereço,
por definição, de estar ali aquela estrela.

282
00:12:34,080 --> 00:12:37,530
E se scanf espera um endereço,
basta apenas passar em tampão.

283
00:12:37,530 --> 00:12:39,260
Eu não preciso dizer tampão e comercial.

284
00:12:39,260 --> 00:12:42,177
Para os curiosos, você poderia
fazer algo assim.

285
00:12:42,177 --> 00:12:43,510
Ele teria significado diferente.

286
00:12:43,510 --> 00:12:47,240
Isto lhe daria um ponteiro
de um ponteiro, o qual é na verdade

287
00:12:47,240 --> 00:12:50,050
uma coisa válida em C, mas para
Agora, vamos mantê-lo simples

288
00:12:50,050 --> 00:12:51,750
e manter a história consistente.

289
00:12:51,750 --> 00:12:54,100
Eu só vou passar em
tampão e isso é correto.

290
00:12:54,100 --> 00:12:56,487
O problema, porém, é este.

291
00:12:56,487 --> 00:12:58,820
Deixe-me ir em frente e executar esse
programa depois de compilá-lo.

292
00:12:58,820 --> 00:13:00,902
Faça scanf 1.

293
00:13:00,902 --> 00:13:02,610
Porra, meu compilador de
pegando o meu erro.

294
00:13:02,610 --> 00:13:04,090
Dê-me um segundo.

295
00:13:04,090 --> 00:13:05,460
Clang.

296
00:13:05,460 --> 00:13:06,990
Vamos dizer que scanf-1.c.

297
00:13:06,990 --> 00:13:10,880

298
00:13:10,880 --> 00:13:11,380
ESTÁ BEM.

299
00:13:11,380 --> 00:13:12,720
Aí vamos nós.

300
00:13:12,720 --> 00:13:14,280
Eu preciso disso.

301
00:13:14,280 --> 00:13:16,750
CS50 ID tem vários
definições de configuração

302
00:13:16,750 --> 00:13:18,280
que protegem você contra você mesmo.

303
00:13:18,280 --> 00:13:21,300
Eu precisava desativar os de
executando clang manualmente neste momento.

304
00:13:21,300 --> 00:13:22,140
Então cadeia por favor.

305
00:13:22,140 --> 00:13:25,560
Eu estou indo para ir em frente e digite
no meu mundo Olá favorito.

306
00:13:25,560 --> 00:13:26,490
OK, null.

307
00:13:26,490 --> 00:13:27,700
Isso não é o que eu digitei.

308
00:13:27,700 --> 00:13:29,690
Por isso é indicativo de
que algo está errado.

309
00:13:29,690 --> 00:13:33,920
Deixe-me ir em frente e digite
em um tempo muito longo string.

310
00:13:33,920 --> 00:13:37,210
Obrigado pela nulo e eu não sei
se eu vou ser capaz de lançá-lo.

311
00:13:37,210 --> 00:13:40,240
Vamos tentar um pouco de cópia
colar e ver se isso ajuda.

312
00:13:40,240 --> 00:13:43,290
Basta colar um monte de presente.

313
00:13:43,290 --> 00:13:47,310
É definitivamente um maior
cadeia do que o habitual.

314
00:13:47,310 --> 00:13:51,450
Vamos apenas realmente escrevê-lo.

315
00:13:51,450 --> 00:13:51,950
Não.

316
00:13:51,950 --> 00:13:52,650
Caramba.

317
00:13:52,650 --> 00:13:53,480
Comando não encontrado.

318
00:13:53,480 --> 00:13:54,550
Então, isso é não relacionado.

319
00:13:54,550 --> 00:13:56,440
Isso é porque eu colei
alguns personagens maus,

320
00:13:56,440 --> 00:13:59,780
mas isso acaba não está indo trabalhar.

321
00:13:59,780 --> 00:14:03,510
>> Vamos tentar isso mais uma vez, porque
é mais divertido se nós realmente lançá-lo.

322
00:14:03,510 --> 00:14:09,116
Vamos escrever isso e agora, eu sou
indo para copiar uma cadeia muito longa

323
00:14:09,116 --> 00:14:10,990
e agora vamos ver se nós
pode bater essa coisa.

324
00:14:10,990 --> 00:14:14,235
Repare que eu omitido espaços e
novas linhas e-vírgulas

325
00:14:14,235 --> 00:14:16,035
e todos os personagens de funky.

326
00:14:16,035 --> 00:14:16,535
Enter.

327
00:14:16,535 --> 00:14:21,090

328
00:14:21,090 --> 00:14:22,880
E agora a rede está apenas sendo lento.

329
00:14:22,880 --> 00:14:27,460
I pressionado Command-V muito tempo, claramente.

330
00:14:27,460 --> 00:14:28,190
Caramba!

331
00:14:28,190 --> 00:14:29,260
Comando não encontrado.

332
00:14:29,260 --> 00:14:29,780
>> ESTÁ BEM.

333
00:14:29,780 --> 00:14:32,240
Bem, o ponto é
no entanto, o seguinte.

334
00:14:32,240 --> 00:14:36,910
Então, o que está realmente acontecendo
sobre a presente declaração

335
00:14:36,910 --> 00:14:39,240
de tampão estrela caractere na linha 16?

336
00:14:39,240 --> 00:14:41,820
Então, o que estou recebendo
quando eu declarar um ponteiro?

337
00:14:41,820 --> 00:14:47,440
Tudo o que eu estou recebendo é um valor de quatro bytes
chamado de buffer, mas o que está dentro dela

338
00:14:47,440 --> 00:14:49,540
no momento?

339
00:14:49,540 --> 00:14:50,930
É apenas algum valor de lixo.

340
00:14:50,930 --> 00:14:54,170
Porque qualquer momento você declarar uma variável
em C, é apenas algum valor de lixo,

341
00:14:54,170 --> 00:14:56,220
e estamos começando a
viagem sobre esta realidade.

342
00:14:56,220 --> 00:14:59,720
Agora, quando eu digo scanf,
vá a este endereço

343
00:14:59,720 --> 00:15:01,520
e colocar o que o usuário digita.

344
00:15:01,520 --> 00:15:06,400
Se o usuário digita Olá
mundo, bem, onde eu gostaria de colocá-lo?

345
00:15:06,400 --> 00:15:07,750
Buffer é um valor de lixo.

346
00:15:07,750 --> 00:15:11,510
>> Então, isso é como uma espécie de seta
que está apontando quem sabe onde.

347
00:15:11,510 --> 00:15:13,880
Talvez ele está apontando
bem aqui na minha memória.

348
00:15:13,880 --> 00:15:16,560
E assim, quando o usuário
tipos em Olá mundo,

349
00:15:16,560 --> 00:15:22,380
o programa tenta colocar o
Olá mundo seqüência barra invertida 0

350
00:15:22,380 --> 00:15:23,910
nesse pedaço de memória.

351
00:15:23,910 --> 00:15:27,070
Mas, com alta probabilidade, mas
claramente não 100% de probabilidade,

352
00:15:27,070 --> 00:15:30,440
o computador vai então falhar
o programa porque este não é

353
00:15:30,440 --> 00:15:32,490
memória que eu deveria ser permitido tocar.

354
00:15:32,490 --> 00:15:36,330
Assim, em breve, este programa é
falho para exatamente esse motivo.

355
00:15:36,330 --> 00:15:38,070
Eu fundamentalmente não estou fazendo o que?

356
00:15:38,070 --> 00:15:42,366
Que medidas têm omiti, assim como
nós omitimos com o primeiro exemplo de Binky?

357
00:15:42,366 --> 00:15:42,866
Sim?

358
00:15:42,866 --> 00:15:43,710
>> AUDIÊNCIA: alocação de memória?

359
00:15:43,710 --> 00:15:45,001
>> DAVID MALAN: alocação de memória.

360
00:15:45,001 --> 00:15:48,400
Eu realmente não tenho alocado
qualquer memória para essa seqüência.

361
00:15:48,400 --> 00:15:50,270
Assim, podemos consertar isso em um par de formas.

362
00:15:50,270 --> 00:15:52,700
Um, podemos mantê-lo simples
e, de fato, agora você está

363
00:15:52,700 --> 00:15:55,116
vai começar a ver uma indefinição
das linhas entre o que

364
00:15:55,116 --> 00:15:58,520
uma matriz é, o que é uma string, o que é um
Char estrela é, o que uma matriz de caracteres

365
00:15:58,520 --> 00:15:59,020
é.

366
00:15:59,020 --> 00:16:02,450
Aqui está um segundo exemplo
envolvendo cordas e aviso

367
00:16:02,450 --> 00:16:05,690
tudo que eu fiz em linha
16 é, em vez de dizer

368
00:16:05,690 --> 00:16:09,530
tampão que vai ser um char
estrela, um ponteiro para um bloco de memória,

369
00:16:09,530 --> 00:16:14,057
Eu vou dar muito proativamente
me um buffer para 16 caracteres,

370
00:16:14,057 --> 00:16:16,390
e de fato, se você estiver familiarizado
com o termo de tamponamento,

371
00:16:16,390 --> 00:16:20,570
provavelmente a partir do mundo dos vídeos,
onde um buffer de vídeo é, de tamponamento,

372
00:16:20,570 --> 00:16:21,175
buffering.

373
00:16:21,175 --> 00:16:22,550
Bem, qual é a conexão aqui?

374
00:16:22,550 --> 00:16:24,960
Bem, interior de YouTube
e dentro de players de vídeo

375
00:16:24,960 --> 00:16:27,200
geralmente é uma matriz
que é maior do que 16.

376
00:16:27,200 --> 00:16:30,340
Ele pode ser uma matriz de um tamanho
megabyte, talvez 10 megabytes,

377
00:16:30,340 --> 00:16:34,330
e para essa matriz faz seu browser
baixar um monte de bytes,

378
00:16:34,330 --> 00:16:37,500
um grupo inteiro de megabytes de
vídeo e leitor de vídeo,

379
00:16:37,500 --> 00:16:40,930
YouTube ou de quem quer que esteja, começa
lendo os bytes de matriz que,

380
00:16:40,930 --> 00:16:43,530
ea qualquer momento você vê o
palavra buffering, buffering,

381
00:16:43,530 --> 00:16:46,350
que significa que o jogador possui
chegado ao fim desse array.

382
00:16:46,350 --> 00:16:50,430
A rede é tão lento que não tem
recarregados a matriz com mais bytes

383
00:16:50,430 --> 00:16:55,610
e então você está fora de bits
para exibir para o usuário.

384
00:16:55,610 --> 00:16:59,430
>> Então tampão é um termo apt aqui em que
é apenas uma matriz, um pedaço de memória.

385
00:16:59,430 --> 00:17:02,530
E isso vai corrigi-lo
pois verifica-se

386
00:17:02,530 --> 00:17:07,410
que você pode tratar matrizes como se
eles são endereços, embora tampão

387
00:17:07,410 --> 00:17:10,710
é apenas um símbolo, é uma
sequência de caracteres, buffer,

388
00:17:10,710 --> 00:17:14,760
que é útil para mim, o programador,
você pode passar em torno de seu nome

389
00:17:14,760 --> 00:17:17,079
como se fosse um
ponteiro, como se

390
00:17:17,079 --> 00:17:21,000
foram o endereço de um pedaço
de memória para 16 caracteres.

391
00:17:21,000 --> 00:17:24,530
Então, isso é para dizer, eu posso passar
o scanf exatamente essa palavra

392
00:17:24,530 --> 00:17:30,670
e agora, se eu fizer este programa,
fazer scanf 2, ponto scanf barra 2,

393
00:17:30,670 --> 00:17:35,386
e digite Olá mundo,
Enter, que tempo--

394
00:17:35,386 --> 00:17:37,590
>> Hmm, o que aconteceu?

395
00:17:37,590 --> 00:17:39,340
Corda por favor.

396
00:17:39,340 --> 00:17:41,430
O que eu fiz errado?

397
00:17:41,430 --> 00:17:43,800
Olá, mundo, buffer.

398
00:17:43,800 --> 00:17:44,705
Ola mundo.

399
00:17:44,705 --> 00:17:48,201

400
00:17:48,201 --> 00:17:49,420
Ah, eu sei o que está fazendo.

401
00:17:49,420 --> 00:17:49,920
ESTÁ BEM.

402
00:17:49,920 --> 00:17:51,628
Então está lendo-se
até que o primeiro espaço.

403
00:17:51,628 --> 00:17:55,680
Então, vamos enganar por apenas um momento e
dizer que eu só queria escrever algo

404
00:17:55,680 --> 00:18:01,408
realmente longa como esta é uma frase longa
isso é um, dois, três, quatro, cinco,

405
00:18:01,408 --> 00:18:04,420
seis, sete, oito, nove,
10, 11, 12, 13, 14, 15, 16.

406
00:18:04,420 --> 00:18:05,300
ESTÁ BEM.

407
00:18:05,300 --> 00:18:07,600
Na verdade, é uma frase longa.

408
00:18:07,600 --> 00:18:10,710
Então, esta frase é
mais de 16 caracteres

409
00:18:10,710 --> 00:18:13,670
e então quando eu pressione Enter,
o que vai acontecer?

410
00:18:13,670 --> 00:18:16,940
Bem, neste caso do
tampão história, eu tinha declarado

411
00:18:16,940 --> 00:18:22,190
para ser realmente uma matriz
com 16 caracteres pronto para ir.

412
00:18:22,190 --> 00:18:27,426
Então, um, dois, três, quatro, cinco, seis,
sete, oito, nove, 10, 11, 12, 13, 14,

413
00:18:27,426 --> 00:18:29,440
15, 16.

414
00:18:29,440 --> 00:18:34,410
Assim, 16 caracteres, e agora, quando eu
ler em algo como este é um longo

415
00:18:34,410 --> 00:18:43,950
sentença, o que vai acontecer é
que eu vou ler em este é um longo

416
00:18:43,950 --> 00:18:49,660
S-E-N-A-C-N-C-E, frase.

417
00:18:49,660 --> 00:18:52,270
>> Portanto, esta é deliberadamente
uma coisa ruim que eu

418
00:18:52,270 --> 00:18:55,060
continuar a escrever para além do
limites da minha matriz,

419
00:18:55,060 --> 00:18:56,660
para além dos limites do meu tampão.

420
00:18:56,660 --> 00:19:00,100
Eu poderia ter sorte e do programa
vai continuar a correr e não me importo,

421
00:19:00,100 --> 00:19:03,450
mas de um modo geral, esta
vai realmente bater o meu programa,

422
00:19:03,450 --> 00:19:06,440
e é um bug no meu
codificar o momento que eu passo

423
00:19:06,440 --> 00:19:08,576
para além dos limites
dessa matriz, porque eu

424
00:19:08,576 --> 00:19:10,450
Não sei se é
necessariamente vai falhar

425
00:19:10,450 --> 00:19:12,120
ou se eu estou indo só para ter sorte.

426
00:19:12,120 --> 00:19:15,750
Então, isso é problemático porque em
Neste caso, ele parece funcionar

427
00:19:15,750 --> 00:19:20,931
e vamos tentar o destino aqui, embora
o IDE parece tolerar um pouco

428
00:19:20,931 --> 00:19:21,430
de--

429
00:19:21,430 --> 00:19:22,040
>> Aí vamos nós.

430
00:19:22,040 --> 00:19:23,240
Finalmente.

431
00:19:23,240 --> 00:19:26,470
Então, eu sou o único que pode ver isso.

432
00:19:26,470 --> 00:19:29,630
Então, eu só tinha um monte de diversão digitação
uma frase real muito longo

433
00:19:29,630 --> 00:19:32,800
que certamente excedido
16 bytes, porque

434
00:19:32,800 --> 00:19:38,050
digitado nesta longa multi-linha louco
frase, em seguida, observe o que aconteceu.

435
00:19:38,050 --> 00:19:41,110
O programa tentou imprimi-lo
e, em seguida, tem uma falha de segmentação

436
00:19:41,110 --> 00:19:44,430
e falhas de segmentação é quando
algo como isso acontece

437
00:19:44,430 --> 00:19:47,650
e o sistema operativo diz
não, não pode tocar essa memória.

438
00:19:47,650 --> 00:19:49,570
Nós vamos matar
o programa completo.

439
00:19:49,570 --> 00:19:51,180
>> Portanto, este parece problemático.

440
00:19:51,180 --> 00:19:54,540
Eu melhorei o programa pelo qual
pelo menos, ter alguma memória,

441
00:19:54,540 --> 00:19:58,000
mas isto parece limitar
o GetString função para obter

442
00:19:58,000 --> 00:20:00,780
cordas de algum tempo finito 16.

443
00:20:00,780 --> 00:20:04,200
Então, se você quer apoiar mais
frases do que 16 caracteres,

444
00:20:04,200 --> 00:20:04,880
o que você faz?

445
00:20:04,880 --> 00:20:07,970
Bem, você pode aumentar o
tamanho desta reserva para 32

446
00:20:07,970 --> 00:20:09,190
ou que parece tipo de short.

447
00:20:09,190 --> 00:20:12,260
Por que não vamos apenas fazer
que 1000, mas empurrar para trás.

448
00:20:12,260 --> 00:20:17,100
Qual é a resposta intuitivamente de
apenas evitar este problema, tornando

449
00:20:17,100 --> 00:20:20,660
meu buffer maior, como 1.000 caracteres?

450
00:20:20,660 --> 00:20:23,470
Ao implementar GetString desta forma.

451
00:20:23,470 --> 00:20:27,130
O que é bom ou ruim aqui?

452
00:20:27,130 --> 00:20:28,033
Sim?

453
00:20:28,033 --> 00:20:30,574
Audiência: Se você ligar um monte
de espaço e você não usá-lo,

454
00:20:30,574 --> 00:20:33,500
então você não pode redistribuir esse espaço.

455
00:20:33,500 --> 00:20:34,500
DAVID MALAN: Absolutamente.

456
00:20:34,500 --> 00:20:38,480
É um desperdício na medida em que se não o fizer
realmente precisa desses 900 bytes

457
00:20:38,480 --> 00:20:41,057
e ainda assim você está pedindo
1.000 no total de qualquer maneira,

458
00:20:41,057 --> 00:20:44,140
você apenas está consumindo mais memória
o computador do usuário do que você precisa,

459
00:20:44,140 --> 00:20:45,740
e depois de tudo, alguns
você já encontrou

460
00:20:45,740 --> 00:20:47,620
na vida que quando você está
executando muitos programas

461
00:20:47,620 --> 00:20:50,470
e eles estão comendo muita memória,
isso pode realmente afetar o desempenho

462
00:20:50,470 --> 00:20:52,220
e experiência do usuário
no computador.

463
00:20:52,220 --> 00:20:56,090
Então, esse é o tipo de uma solução preguiçoso,
com certeza, e, inversamente,

464
00:20:56,090 --> 00:21:00,140
não é apenas um desperdício, qual é o problema
ainda permanece, mesmo se eu faço o meu tampão

465
00:21:00,140 --> 00:21:02,100
1000?

466
00:21:02,100 --> 00:21:02,600
Sim?

467
00:21:02,600 --> 00:21:04,475
>> AUDIÊNCIA: A cadeia de comprimento é 1.001.

468
00:21:04,475 --> 00:21:05,350
DAVID MALAN: Exatamente.

469
00:21:05,350 --> 00:21:08,280
Se a seqüência de comprimento é 1001,
você tem exatamente o mesmo problema,

470
00:21:08,280 --> 00:21:10,705
e pelo meu argumento, eu o faria
apenas, em seguida, torná-lo 2000,

471
00:21:10,705 --> 00:21:12,830
mas você não sabe em
avançar o quão grande ele deve ser,

472
00:21:12,830 --> 00:21:16,890
e ainda, eu tenho que compilar meu programa
antes de deixar as pessoas usam e faça o download

473
00:21:16,890 --> 00:21:17,390
isto.

474
00:21:17,390 --> 00:21:21,490
Portanto, este é exatamente o tipo de
coisas que as tentativas de biblioteca CS50

475
00:21:21,490 --> 00:21:24,750
para nos ajudar com e nós só vai olhar
em alguns dos implementação subjacente

476
00:21:24,750 --> 00:21:29,790
aqui, mas este é CS50 ponto C. Este
é o arquivo que tem estado em CS50 IDE

477
00:21:29,790 --> 00:21:31,420
todas essas semanas que você está usando.

478
00:21:31,420 --> 00:21:34,280
É pré-compilados e você tem
sido usá-lo automaticamente

479
00:21:34,280 --> 00:21:38,780
por natureza de ter o
traço L bandeira CS50 com clang,

480
00:21:38,780 --> 00:21:42,300
mas se eu rolar para baixo através de todos
estas funções, é aqui GetString,

481
00:21:42,300 --> 00:21:44,636
e só para lhe dar um
gosto do que está acontecendo,

482
00:21:44,636 --> 00:21:46,760
vamos dar uma olhada rápida em
a relativa complexidade.

483
00:21:46,760 --> 00:21:48,870
Não é um super longa
função, mas não o fizemos

484
00:21:48,870 --> 00:21:52,530
tem que pensar muito sobre tudo
como ir sobre a obtenção de cordas.

485
00:21:52,530 --> 00:21:55,660
>> Então aqui está o meu tampão e eu
aparentemente, inicialize-o como nulo.

486
00:21:55,660 --> 00:21:57,990
Isto, naturalmente, é o
mesma coisa como char estrela,

487
00:21:57,990 --> 00:22:00,585
mas eu decidi em
execução da biblioteca CS50

488
00:22:00,585 --> 00:22:02,460
que, se nós estamos indo para
ser completamente dinâmico,

489
00:22:02,460 --> 00:22:05,770
Eu não sei com antecedência como grande de um
usuários de cordas vão querer obter.

490
00:22:05,770 --> 00:22:08,140
Então eu vou começar
com apenas uma cadeia vazia

491
00:22:08,140 --> 00:22:11,507
e eu estou indo para construir o máximo
memória como eu preciso para se ajustar à string user

492
00:22:11,507 --> 00:22:13,340
e se eu não tenho
suficiente, eu vou pedir

493
00:22:13,340 --> 00:22:15,010
o sistema operacional para mais memória.

494
00:22:15,010 --> 00:22:17,510
Eu estou indo para mover sua seqüência
em um pedaço maior de memória

495
00:22:17,510 --> 00:22:21,847
e eu estou indo para liberar ou libertar o
insuficientemente grande pedaço de memória

496
00:22:21,847 --> 00:22:23,680
e nós apenas estamos indo
para fazer isso de forma iterativa.

497
00:22:23,680 --> 00:22:25,570
>> Assim, uma olhada rápida,
aqui é apenas uma variável

498
00:22:25,570 --> 00:22:28,780
com a qual eu vou manter o controle
da capacidade do meu buffer.

499
00:22:28,780 --> 00:22:30,071
Quantos bytes eu pode caber?

500
00:22:30,071 --> 00:22:32,070
Aqui está uma variável n com
que eu vou continuar

501
00:22:32,070 --> 00:22:36,200
o controle de quantos bytes estão realmente em
o tampão ou que o usuário digitou.

502
00:22:36,200 --> 00:22:39,900
Se você não viu isso antes, você
pode especificar que uma variável como um int

503
00:22:39,900 --> 00:22:46,370
é não assinado, que como o nome sugere,
significa que é não negativo, e por que

504
00:22:46,370 --> 00:22:50,590
Eu nunca quero incomodar especificando
que um int não é apenas um int,

505
00:22:50,590 --> 00:22:52,540
mas é um int não assinado?

506
00:22:52,540 --> 00:22:55,064
É um int não negativo.

507
00:22:55,064 --> 00:22:56,355
O que o [inaudível] significa?

508
00:22:56,355 --> 00:22:58,910
>> AUDIÊNCIA: É descrevendo uma quantidade
de memória que pode ser [inaudível].

509
00:22:58,910 --> 00:22:59,660
>> DAVID MALAN: Yeah.

510
00:22:59,660 --> 00:23:03,710
Então, se eu disser não assinado, este é, na verdade,
dando-lhe um pouco de memória extra

511
00:23:03,710 --> 00:23:07,440
e parece meio bobo, mas se você
ter um pouco de memória adicional, que

512
00:23:07,440 --> 00:23:09,940
significa que você tem o dobro
valores que podem representar,

513
00:23:09,940 --> 00:23:11,570
porque ele pode ser um 0 ou um 1.

514
00:23:11,570 --> 00:23:14,660
Então, por padrão, um int pode ser mais ou menos
negativo de 2 bilhões de todo o caminho

515
00:23:14,660 --> 00:23:16,030
até positiva 2 bilhões.

516
00:23:16,030 --> 00:23:18,540
Essas são grandes intervalos, mas
ainda é tipo de desperdício

517
00:23:18,540 --> 00:23:21,280
se você só se preocupam com
tamanhos, que apenas intuitivamente

518
00:23:21,280 --> 00:23:24,620
deve ser não-negativo ou
positivo ou 0, bem, então,

519
00:23:24,620 --> 00:23:28,884
por que você está desperdiçando 2 bilhões
Os valores possíveis para números negativos

520
00:23:28,884 --> 00:23:30,300
se você nunca vai usá-los?

521
00:23:30,300 --> 00:23:35,350
Assim dizendo não assinado, agora meu int puder
estar entre 0 e cerca de 4 bilhões.

522
00:23:35,350 --> 00:23:39,280
>> Então aqui é apenas um int C por razões
não vamos entrar apenas agora como

523
00:23:39,280 --> 00:23:42,280
para por isso que é um int em vez
de um char, mas aqui é

524
00:23:42,280 --> 00:23:44,630
a essência do que está acontecendo
, e alguns de vocês

525
00:23:44,630 --> 00:23:48,340
pode ser utilizando, por exemplo, a
função fgetc mesmo em PSet quatro

526
00:23:48,340 --> 00:23:51,580
ou após essa data, vamos vê-lo
novamente no conjunto de problemas cinco,

527
00:23:51,580 --> 00:23:55,410
fgetc é bom porque como o nome
tipo de, tipo de arcanely sugere,

528
00:23:55,410 --> 00:23:57,940
é uma função que
recebe um personagem e assim,

529
00:23:57,940 --> 00:24:00,690
o que é fundamentalmente diferente
sobre o que estamos fazendo em GetString

530
00:24:00,690 --> 00:24:03,110
é que não estamos usando
scanf da mesma maneira.

531
00:24:03,110 --> 00:24:07,550
Estamos apenas rastejando passo-a-passo
sobre tudo o que o usuário digitou em,

532
00:24:07,550 --> 00:24:10,970
porque sempre podemos atribuir uma
char, e para que possamos sempre com segurança

533
00:24:10,970 --> 00:24:15,599
olhar para um caractere de cada vez, e
a magia começa a acontecer aqui.

534
00:24:15,599 --> 00:24:17,890
Eu estou indo para rolar para baixo para
meio desta função

535
00:24:17,890 --> 00:24:20,360
apenas para introduzir brevemente esta função.

536
00:24:20,360 --> 00:24:22,670
Muito como há um
função malloc, há

537
00:24:22,670 --> 00:24:27,740
uma função realloc onde realloc
permite realocar um bloco de memória

538
00:24:27,740 --> 00:24:29,570
e torná-la maior ou menor.

539
00:24:29,570 --> 00:24:33,060
Então, longa história curta e com
uma onda de minha mão para hoje,

540
00:24:33,060 --> 00:24:35,620
sabe que o que GetString
está fazendo é que é uma espécie

541
00:24:35,620 --> 00:24:39,720
magicamente de crescimento ou
encolhendo o tampão como o utilizador

542
00:24:39,720 --> 00:24:41,440
tipos em sua cadeia.

543
00:24:41,440 --> 00:24:43,962
>> Portanto, se o usuário digita um
corda curta, este código

544
00:24:43,962 --> 00:24:45,920
única aloca suficiente
memória para se ajustar à string.

545
00:24:45,920 --> 00:24:48,086
Se o usuário mantém digitação
como eu fiz isso de novo e de novo

546
00:24:48,086 --> 00:24:50,330
e novamente, bem, se o
tampão do inicialmente esta grande

547
00:24:50,330 --> 00:24:53,310
e o programa percebe, a
espere um minuto, eu estou fora do espaço,

548
00:24:53,310 --> 00:24:55,410
que vai dobrar
o tamanho do buffer

549
00:24:55,410 --> 00:24:59,110
e, em seguida, o dobro do tamanho do buffer
e o código que faz a duplicação,

550
00:24:59,110 --> 00:25:03,170
se olharmos para ele aqui, é
apenas isso inteligente one-liner.

551
00:25:03,170 --> 00:25:06,830
Você pode não ter visto esta sintaxe
antes, mas se você diz que é igual a estrela,

552
00:25:06,830 --> 00:25:10,470
esta é a mesma coisa que
dizendo vezes capacidade para 2.

553
00:25:10,470 --> 00:25:13,390
Então ele simplesmente continua dobrando
a capacidade do tampão

554
00:25:13,390 --> 00:25:17,480
e, em seguida, dizendo realloc para dar
-se que muito mais memória.

555
00:25:17,480 --> 00:25:19,720
>> Agora, como um aparte, há
são outras funções aqui

556
00:25:19,720 --> 00:25:23,680
que não vamos olhar para qualquer detalhe
além de mostrar em GetInt,

557
00:25:23,680 --> 00:25:26,150
usamos GetString em GetInt.

558
00:25:26,150 --> 00:25:28,192
Nós verificamos que não é
null, o que, recall,

559
00:25:28,192 --> 00:25:30,400
é o valor especial que
significa algo correu mal.

560
00:25:30,400 --> 00:25:31,233
Estamos com falta de memória.

561
00:25:31,233 --> 00:25:32,310
Melhor verificar para isso.

562
00:25:32,310 --> 00:25:33,710
E nós devolver um valor de sentinela.

563
00:25:33,710 --> 00:25:37,850
Mas eu vou adiar para as observações quanto à
por que e, em seguida, usar esse primo de scanf

564
00:25:37,850 --> 00:25:42,100
chamado sscanf e despeja
que scanf sscanf, ou corda,

565
00:25:42,100 --> 00:25:45,310
permite que você dê uma olhada na linha que
o usuário digitou no e deixá-lo

566
00:25:45,310 --> 00:25:49,610
analisá-lo e, essencialmente, o que eu sou
fazendo aqui é que eu estou dizendo a sscanf,

567
00:25:49,610 --> 00:25:54,440
analisar tudo o que o usuário tem
digitadas e certificar-se de% i,

568
00:25:54,440 --> 00:25:59,250
existe um inteiro nele, e não vamos
entrar hoje exatamente porque há também

569
00:25:59,250 --> 00:26:03,760
um% c aqui, mas que, em poucas palavras permite
nós para detectar se o usuário digitou

570
00:26:03,760 --> 00:26:06,050
em algo falso após o número.

571
00:26:06,050 --> 00:26:11,766
Então a razão que GetInt e GetString
dizer-lhe para repetir, repetir, repetir

572
00:26:11,766 --> 00:26:13,640
é por causa de tudo
que o código que nós escrevemos,

573
00:26:13,640 --> 00:26:17,900
é uma espécie de olhar para a entrada do usuário
em certificar-se que é inteiramente numérico

574
00:26:17,900 --> 00:26:21,700
ou é um flutuante real
valor de ponto ou semelhante,

575
00:26:21,700 --> 00:26:24,233
dependendo do que o valor
funcionar você está usando.

576
00:26:24,233 --> 00:26:25,060
>> Ufa.

577
00:26:25,060 --> 00:26:25,710
ESTÁ BEM.

578
00:26:25,710 --> 00:26:27,592
Isso foi um bocado
mas o ponto aqui é

579
00:26:27,592 --> 00:26:29,550
que a razão que tivemos
as rodas de formação sobre

580
00:26:29,550 --> 00:26:32,880
é porque no nível mais baixo,
Há apenas tantas coisas que

581
00:26:32,880 --> 00:26:35,674
pode dar errado que queríamos
para lidar com preventivamente

582
00:26:35,674 --> 00:26:38,090
essas coisas certamente no
primeiras semanas de classe,

583
00:26:38,090 --> 00:26:42,230
mas agora com PSet quatro e cinco e PSet
além de você vai ver que é mais até

584
00:26:42,230 --> 00:26:45,570
você, mas também você é mais capaz
de resolver esses tipos de problemas

585
00:26:45,570 --> 00:26:47,180
você mesmo.

586
00:26:47,180 --> 00:26:51,770
Quaisquer perguntas sobre GetString ou GetInt?

587
00:26:51,770 --> 00:26:52,630
Sim?

588
00:26:52,630 --> 00:26:55,130
>> AUDIÊNCIA: Por que você iria dobrar
a capacidade do tampão

589
00:26:55,130 --> 00:26:57,630
em vez de apenas aumentar
por isso a quantidade exacta?

590
00:26:57,630 --> 00:26:58,100
>> DAVID MALAN: Boa pergunta.

591
00:26:58,100 --> 00:27:00,474
Por que iríamos duplicar a capacidade
do tampão em oposição

592
00:27:00,474 --> 00:27:02,800
apenas para aumentá-la
por algum valor constante?

593
00:27:02,800 --> 00:27:03,900
Foi uma decisão design.

594
00:27:03,900 --> 00:27:08,590
Nós apenas decidimos que porque tende a
ser um pouco caro, time-wise perguntar

595
00:27:08,590 --> 00:27:10,440
o sistema operativo
para a memória, não o fizemos

596
00:27:10,440 --> 00:27:13,210
quer acabar se metendo
uma situação para grandes cadeias

597
00:27:13,210 --> 00:27:14,960
que estávamos pedindo
o sistema operacional novo e de novo

598
00:27:14,960 --> 00:27:17,500
e de novo e de novo em
sucessão rápida para a memória.

599
00:27:17,500 --> 00:27:20,387
Então, nós apenas decidiu, um pouco
arbitrariamente, mas esperamos razoavelmente,

600
00:27:20,387 --> 00:27:22,720
que, você sabe o que, vamos
tentar chegar à frente de nós mesmos

601
00:27:22,720 --> 00:27:25,520
e manter apenas dobrando-o para que
nós minimizar a quantidade de vezes

602
00:27:25,520 --> 00:27:29,010
temos que chamar malloc ou
realloc, mas um total de julgamento

603
00:27:29,010 --> 00:27:31,820
chamar a ausência de saber
o que os usuários podem querer digitar.

604
00:27:31,820 --> 00:27:33,600
Ambas as formas podem ser discutível.

605
00:27:33,600 --> 00:27:35,430
Indiscutivelmente bom.

606
00:27:35,430 --> 00:27:39,240
>> Então vamos dar uma olhada em um par
de outros efeitos colaterais de memória,

607
00:27:39,240 --> 00:27:41,610
coisas que podem dar errado
e ferramentas que você pode

608
00:27:41,610 --> 00:27:43,880
usar para capturar estes tipos de erros.

609
00:27:43,880 --> 00:27:47,800
Acontece tudo de você, mesmo que
check50 não lhe contou como muito,

610
00:27:47,800 --> 00:27:50,050
têm escrito de buggy
uma vez que um código de semana,

611
00:27:50,050 --> 00:27:53,630
mesmo se todos os testes são check50
passou, e mesmo se você e seu TF

612
00:27:53,630 --> 00:27:56,010
são super confiantes de que
seu código funciona como previsto.

613
00:27:56,010 --> 00:27:59,190
Seu código foi buggy ou
falho em que todos vocês,

614
00:27:59,190 --> 00:28:02,540
em usar a biblioteca CS50,
foram fuga de memória.

615
00:28:02,540 --> 00:28:06,040
Você foi pedir ao sistema operacional
para memória na maioria dos programas

616
00:28:06,040 --> 00:28:08,850
você escreveu, mas você
nunca realmente dado de volta.

617
00:28:08,850 --> 00:28:12,110
Você chamou GetString
e GetInt e GetFloat,

618
00:28:12,110 --> 00:28:15,270
mas com GetString, você tem
nunca chamou unGetString ou dê-

619
00:28:15,270 --> 00:28:19,890
Voltar corda ou similar, mas nós vimos
GetString que faz alocar memória

620
00:28:19,890 --> 00:28:22,810
por meio de malloc ou este
realloc função, que é apenas

621
00:28:22,810 --> 00:28:25,670
muito semelhante em espírito,
e ainda, temos sido

622
00:28:25,670 --> 00:28:28,629
pedindo o sistema operacional para
memória e memória novamente e novamente

623
00:28:28,629 --> 00:28:29,670
mas nunca dando-lhe de volta.

624
00:28:29,670 --> 00:28:33,550
>> Agora, como um aparte, verifica-se que
quando um programa termina, toda a memória

625
00:28:33,550 --> 00:28:34,870
é automaticamente liberado.

626
00:28:34,870 --> 00:28:36,150
Portanto, não foi um grande negócio.

627
00:28:36,150 --> 00:28:38,590
Ele não vai quebrar o
IDE ou retardar as coisas,

628
00:28:38,590 --> 00:28:40,670
Mas quando os programas fazem
geralmente vazar memória

629
00:28:40,670 --> 00:28:42,170
e eles estão correndo por um longo tempo.

630
00:28:42,170 --> 00:28:45,640
Se você já viu o pouco estúpido
bola de praia em Mac OS ou a ampulheta

631
00:28:45,640 --> 00:28:51,160
no Windows, onde é uma espécie de
abrandar ou pensando ou pensando

632
00:28:51,160 --> 00:28:53,770
ou apenas realmente começa
para retardar a um rastejamento,

633
00:28:53,770 --> 00:28:56,960
muito possivelmente poderia ser
o resultado de um vazamento de memória.

634
00:28:56,960 --> 00:28:59,970
Os programadores que escreveram
o software que você está usando

635
00:28:59,970 --> 00:29:03,570
pedir ao sistema operacional para a memória
cada poucos minutos, a cada hora.

636
00:29:03,570 --> 00:29:05,570
Mas se você estiver executando o
software, mesmo que seja

637
00:29:05,570 --> 00:29:08,680
minimizado no seu computador
por horas ou dias a fio,

638
00:29:08,680 --> 00:29:11,980
você pode estar pedindo mais e mais
memória e nunca realmente utilizá-lo

639
00:29:11,980 --> 00:29:15,180
e para que o seu código pode ser, ou
programas podem ser vazamento de memória,

640
00:29:15,180 --> 00:29:18,350
e se você começar a vazar memória,
há menos memória para outros programas,

641
00:29:18,350 --> 00:29:21,220
e o efeito é a
retardar tudo para baixo.

642
00:29:21,220 --> 00:29:23,600
>> Agora, este é de longe um dos
os programas mais atrozes

643
00:29:23,600 --> 00:29:26,350
você terá oportunidades
para executar em CS50, na medida

644
00:29:26,350 --> 00:29:31,650
como sua produção é ainda mais esotérica do que
clang de ou fazer ou o todo do comando

645
00:29:31,650 --> 00:29:35,930
programas de linha que já executados antes, mas
felizmente, incorporado em sua saída

646
00:29:35,930 --> 00:29:39,810
é algumas dicas úteis que super-
irá ser útil quer para PSet quatro

647
00:29:39,810 --> 00:29:41,510
ou certamente PConfigurar cinco.

648
00:29:41,510 --> 00:29:44,250
Então valgrind é uma ferramenta
que pode ser usado para procurar

649
00:29:44,250 --> 00:29:46,930
para vazamentos de memória em seu programa.

650
00:29:46,930 --> 00:29:48,570
É relativamente simples de executar.

651
00:29:48,570 --> 00:29:51,420
Você corre valgrind e, em seguida, mesmo
mas é um pouco detalhado,

652
00:29:51,420 --> 00:29:54,440
traço verificação de vazamento traço
é igual a plena e, em seguida dot

653
00:29:54,440 --> 00:29:56,320
corte e o nome do seu programa.

654
00:29:56,320 --> 00:30:00,010
Então valgrind, então, executar o seu programa
e, no final do seu programa

655
00:30:00,010 --> 00:30:02,240
execução antes de ele sai e
dá-lhe um outro pedido,

656
00:30:02,240 --> 00:30:04,980
que vai analisar o seu
programa enquanto ele está em execução

657
00:30:04,980 --> 00:30:07,740
e dizer-lhe que você vazar
qualquer memória e melhor ainda,

658
00:30:07,740 --> 00:30:10,610
se você tocar memória que
não pertence a você?

659
00:30:10,610 --> 00:30:13,700
Não pode pegar tudo, mas é
muito bom em pegar mais coisas.

660
00:30:13,700 --> 00:30:19,700
>> Então aqui está um exemplo de meu ter prazo
este programa, tendo run valgrind,

661
00:30:19,700 --> 00:30:21,470
em um programa chamado
memória, e eu vou

662
00:30:21,470 --> 00:30:24,730
para destacar as linhas que são
em última análise, de interesse para nós.

663
00:30:24,730 --> 00:30:27,690
Portanto, há ainda mais distrações
que eu tenha excluído do slide.

664
00:30:27,690 --> 00:30:30,930
Mas vamos ver o que este
programa é capaz de nos dizer.

665
00:30:30,930 --> 00:30:34,800
Ele é capaz de nos dizer coisas
como gravação inválido de tamanho 4.

666
00:30:34,800 --> 00:30:38,020
Em outras palavras, se você tocar em memória,
especificamente 4 bytes de memória

667
00:30:38,020 --> 00:30:40,350
que você não deve ter,
valgrind posso te dizer isso.

668
00:30:40,350 --> 00:30:41,660
Write inválido de tamanho 4.

669
00:30:41,660 --> 00:30:43,640
Você tocou quatro bytes
que você não deve ter.

670
00:30:43,640 --> 00:30:44,840
Onde é que você faz isso?

671
00:30:44,840 --> 00:30:45,900
Esta é a beleza.

672
00:30:45,900 --> 00:30:50,000
Dot linha memória c 21 é onde você
asneira e é por isso que é útil.

673
00:30:50,000 --> 00:30:53,410
Muito parecido com o GDB, pode ajudar
apontá-lo ao erro real.

674
00:30:53,410 --> 00:30:57,170
>> Agora, este é um pouco mais
detalhado, se não confuso.

675
00:30:57,170 --> 00:31:01,307
40 bytes em blocos de 1 são, definitivamente,
perdido no registro de perda 1 de 1.

676
00:31:01,307 --> 00:31:02,140
O que isso significa?

677
00:31:02,140 --> 00:31:05,920
Bem, isso significa apenas que você pediu
40 bytes e você nunca deu-lhe de volta.

678
00:31:05,920 --> 00:31:08,930
Você chamada malloc ou você chamada
GetString e o sistema operativo

679
00:31:08,930 --> 00:31:12,450
deu-lhe 40 bytes, mas você nunca
libertadas ou que a memória liberada,

680
00:31:12,450 --> 00:31:15,400
e para ser justo, nós nunca mostrar
como para dar a volta a memória.

681
00:31:15,400 --> 00:31:17,910
Acontece lá fora é um super-
função simples chamado livre.

682
00:31:17,910 --> 00:31:21,170
Recebe um argumento, a coisa
você quer libertar ou dar para trás,

683
00:31:21,170 --> 00:31:23,430
40 bytes, mas, aparentemente,
neste programa

684
00:31:23,430 --> 00:31:27,300
foram perdidos na linha
20 de memória ponto c.

685
00:31:27,300 --> 00:31:28,650
>> Então vamos ver este programa.

686
00:31:28,650 --> 00:31:31,020
É super inútil.

687
00:31:31,020 --> 00:31:33,980
Isso só demonstra
este erro particular.

688
00:31:33,980 --> 00:31:34,920
Então, vamos dar uma olhada.

689
00:31:34,920 --> 00:31:39,920
Aqui é principais e principais, observação, chamadas
uma função chamada F e depois retorna.

690
00:31:39,920 --> 00:31:41,550
Então, nem tudo o que interessante.

691
00:31:41,550 --> 00:31:42,664
O que faz f fazer?

692
00:31:42,664 --> 00:31:44,330
Repare que eu não me incomodei com um protótipo.

693
00:31:44,330 --> 00:31:46,520
Eu queria manter o código
o mínimo possível.

694
00:31:46,520 --> 00:31:49,530
Então eu coloquei f acima principal e
isso é bom, certamente,

695
00:31:49,530 --> 00:31:51,500
para programas curtos como este.

696
00:31:51,500 --> 00:31:56,910
Então f não retorna nada e faz
não levar nada, mas faz isso.

697
00:31:56,910 --> 00:31:59,620
Declara, bem como
no exemplo Binky,

698
00:31:59,620 --> 00:32:02,682
um ponteiro chamado x que está acontecendo
para armazenar o endereço de um int.

699
00:32:02,682 --> 00:32:03,890
Então, isso é o lado esquerdo.

700
00:32:03,890 --> 00:32:07,230
Em Inglês, o que é o
lado direito fazendo?

701
00:32:07,230 --> 00:32:09,770
Alguém?

702
00:32:09,770 --> 00:32:13,665
O que é esta fazendo por nós?

703
00:32:13,665 --> 00:32:14,651
Sim?

704
00:32:14,651 --> 00:32:16,623
>> AUDIÊNCIA: [inaudível]
vezes o tamanho de um int

705
00:32:16,623 --> 00:32:19,175
que é 10 vezes que [inaudível]

706
00:32:19,175 --> 00:32:20,800
DAVID MALAN: Boa e deixe-me resumir.

707
00:32:20,800 --> 00:32:25,480
Então alocar espaço suficiente para 10 inteiros
ou 10, o que é do tamanho de um int,

708
00:32:25,480 --> 00:32:29,340
é quatro bytes, por isso 10 vezes 4 é
40, de modo que o lado direito que eu tenho

709
00:32:29,340 --> 00:32:33,930
realçado é dar-me 40 bytes e
armazenar o endereço do primeiro byte

710
00:32:33,930 --> 00:32:34,940
em x.

711
00:32:34,940 --> 00:32:38,380
E agora, finalmente, e é aqui que
este programa é buggy, o que é

712
00:32:38,380 --> 00:32:41,540
errado com linha 21 com base em que a lógica?

713
00:32:41,540 --> 00:32:45,197

714
00:32:45,197 --> 00:32:46,280
O que há de errado com linha 21?

715
00:32:46,280 --> 00:32:46,780
Sim?

716
00:32:46,780 --> 00:32:49,550
AUDIÊNCIA: Você não pode
índice em x [inaudível].

717
00:32:49,550 --> 00:32:50,300
DAVID MALAN: Yeah.

718
00:32:50,300 --> 00:32:52,270
Eu não deveria índice em x como essa.

719
00:32:52,270 --> 00:32:53,850
Então sintaticamente, isso é OK.

720
00:32:53,850 --> 00:32:56,990
O que é bom é, muito parecido com você
pode tratar o nome de uma matriz

721
00:32:56,990 --> 00:33:01,080
como se fosse um ponteiro, semelhante
você pode tratar um ponteiro como se fosse

722
00:33:01,080 --> 00:33:06,425
uma matriz, e para que eu possa sintaticamente
x suporte dizer alguma coisa, x suporte de i,

723
00:33:06,425 --> 00:33:07,800
mas a 10 é problemática.

724
00:33:07,800 --> 00:33:09,096
Por quê?

725
00:33:09,096 --> 00:33:10,910
>> AUDIÊNCIA: Porque não é no interior.

726
00:33:10,910 --> 00:33:12,390
>> DAVID MALAN: Não é
dentro desse pedaço de memória.

727
00:33:12,390 --> 00:33:15,306
Qual é o maior valor que eu deveria
estar colocando nesses colchetes?

728
00:33:15,306 --> 00:33:16,870
9, de 0 a 9.

729
00:33:16,870 --> 00:33:18,160
Devido a indexação zero.

730
00:33:18,160 --> 00:33:20,190
Então, de 0 a 9 seria ótimo.

731
00:33:20,190 --> 00:33:23,960
Suporte 10 não é boa e
mas, lembre-se, porém, cada vez

732
00:33:23,960 --> 00:33:27,017
Parece-me tentar fazer CS50 IDE
acidente, digitando valores falsos,

733
00:33:27,017 --> 00:33:29,100
nem sempre cooperar,
e, na verdade, muitas vezes você

734
00:33:29,100 --> 00:33:31,460
ter sorte só porque o
sistema operacional não

735
00:33:31,460 --> 00:33:35,467
perceber que você nunca tão pouco
passar algum pedaço de memória,

736
00:33:35,467 --> 00:33:38,300
porque você ficou dentro tecnicamente
seu segmento, mas mais sobre isso

737
00:33:38,300 --> 00:33:40,940
em uma classe de sistemas operacionais,
e assim por algo como isto

738
00:33:40,940 --> 00:33:43,000
poderia muito facilmente passar despercebido.

739
00:33:43,000 --> 00:33:48,120
Seu programa nunca vai falhar
consistentemente, mas talvez uma vez em algum tempo.

740
00:33:48,120 --> 00:33:50,610
>> E então vamos tentar valgrind
sobre isso, e é aqui

741
00:33:50,610 --> 00:33:52,870
onde vamos ficar sobrecarregado
por a saída momentaneamente.

742
00:33:52,870 --> 00:34:00,810
Então, faça verificação de vazamento de memória valgrind
é igual a memória barra ponto cheio.

743
00:34:00,810 --> 00:34:03,040
E aqui está o porquê eu prometo
isso iria sobrecarregar.

744
00:34:03,040 --> 00:34:05,700
Aqui está o que valgrind, aqui está o que
um programador, alguns anos-

745
00:34:05,700 --> 00:34:08,469
decidiu que seria uma boa idéia
para a saída a aparência.

746
00:34:08,469 --> 00:34:09,750
Então, vamos dar sentido a isso.

747
00:34:09,750 --> 00:34:13,120
Então, todo o caminho na da esquerda
lado sem uma boa razão

748
00:34:13,120 --> 00:34:16,620
é o ID do processo do programa
nós apenas executado, o identificador único

749
00:34:16,620 --> 00:34:18,030
para o programa que nós apenas correu.

750
00:34:18,030 --> 00:34:19,738
Nós excluído que a partir de
o slide, mas não

751
00:34:19,738 --> 00:34:22,190
é alguma informação útil aqui.

752
00:34:22,190 --> 00:34:24,684
>> Vamos rolar até o topo.

753
00:34:24,684 --> 00:34:25,600
Aqui é onde começamos.

754
00:34:25,600 --> 00:34:27,040
Portanto, não é tanto assim de saída.

755
00:34:27,040 --> 00:34:30,429
Aqui está o que write inválido
4 de tamanho na linha 21.

756
00:34:30,429 --> 00:34:31,760
Bem, o que era linha 21?

757
00:34:31,760 --> 00:34:34,500
Linha 21 foi exatamente
este e faz sentido

758
00:34:34,500 --> 00:34:37,290
que eu estou no validamente
escrito 4 bytes, porque eu sou

759
00:34:37,290 --> 00:34:40,389
tentando colocar este número inteiro,
o que poderia ser qualquer coisa,

760
00:34:40,389 --> 00:34:42,370
isso só acontece de ser
zero, mas eu estou tentando

761
00:34:42,370 --> 00:34:44,940
para colocá-lo em um local
que não pertence a mim.

762
00:34:44,940 --> 00:34:50,900
Além disso, aqui em baixo, 40 bytes em um
blocos são definitivamente perdidos em ficha 1.

763
00:34:50,900 --> 00:34:56,500
Isso porque quando eu chamar malloc
aqui, eu nunca realmente liberar a memória.

764
00:34:56,500 --> 00:34:58,140
>> Então, como podemos corrigir isso?

765
00:34:58,140 --> 00:35:02,970
Deixe-me ir em frente e ser um pouco mais seguro
e fazer 9 lá e me deixe aqui livre x.

766
00:35:02,970 --> 00:35:04,820
Esta é a nova função para hoje.

767
00:35:04,820 --> 00:35:11,520
Se eu agora executar novamente fazer corte de ponto de memória,
vamos executar valgrind nele novamente,

768
00:35:11,520 --> 00:35:14,990
maximizar minha janela e pressione Enter.

769
00:35:14,990 --> 00:35:16,900
Agora, é bom.

770
00:35:16,900 --> 00:35:19,590
Eles enterram a boa notícia
em todo este processo de saída.

771
00:35:19,590 --> 00:35:20,810
Todos os blocos heap eram livres.

772
00:35:20,810 --> 00:35:23,604
Vamos voltar ao que o heap
é, mas não há fugas são possíveis.

773
00:35:23,604 --> 00:35:25,520
Portanto, este é apenas mais um
ferramenta para o seu kit de ferramentas

774
00:35:25,520 --> 00:35:30,220
com o qual você pode começar a
agora encontrar erros como esse.

775
00:35:30,220 --> 00:35:34,532
>> Mas vamos ver o que
mais pode dar errado aqui.

776
00:35:34,532 --> 00:35:38,890
Transição Vamos agora
realmente resolver um problema.

777
00:35:38,890 --> 00:35:42,440
Como um aparte, se isso vai aliviar um
pouco de confusão ou tensão,

778
00:35:42,440 --> 00:35:43,430
isto agora é engraçado.

779
00:35:43,430 --> 00:35:46,400

780
00:35:46,400 --> 00:35:46,900
Sim.

781
00:35:46,900 --> 00:35:49,040
Isso é muito bom.

782
00:35:49,040 --> 00:35:50,890
Porque ponteiros são
endereços e endereços

783
00:35:50,890 --> 00:35:53,098
são, em geral, por convenção
escrito com hexadecimal.

784
00:35:53,098 --> 00:35:54,650
Ha, ha, isso é engraçado agora.

785
00:35:54,650 --> 00:35:58,390
De qualquer forma, por isso vamos agora
realmente resolver um problema.

786
00:35:58,390 --> 00:36:00,840
Isto tem sido super,
super baixo-nível, até agora,

787
00:36:00,840 --> 00:36:03,950
e nós podemos realmente fazer útil
coisas com esses detalhes de baixo nível.

788
00:36:03,950 --> 00:36:06,710
>> Então, nós introduzimos algumas semanas
atrás, a noção de uma matriz.

789
00:36:06,710 --> 00:36:09,177
Uma matriz foi bom porque
é difícil de limpar o nosso código

790
00:36:09,177 --> 00:36:11,760
porque se quiséssemos escrever uma
programa com vários alunos

791
00:36:11,760 --> 00:36:15,270
ou vários nomes e casas e
dormitórios e faculdades e tudo isso,

792
00:36:15,270 --> 00:36:19,430
poderíamos armazenar tudo mais
limpa dentro de uma matriz.

793
00:36:19,430 --> 00:36:23,039
Mas propor uma desvantagem
de uma matriz, até agora.

794
00:36:23,039 --> 00:36:26,080
Mesmo se você não sofri it yourself
em um programa, apenas instintivamente,

795
00:36:26,080 --> 00:36:30,870
o que é uma coisa ruim
sobre uma matriz, talvez?

796
00:36:30,870 --> 00:36:32,337
Ouço alguns murmúrios.

797
00:36:32,337 --> 00:36:34,170
AUDIÊNCIA: É difícil
para alterar o tamanho.

798
00:36:34,170 --> 00:36:36,128
DAVID MALAN: É difícil
para alterar o tamanho.

799
00:36:36,128 --> 00:36:38,660
Você não pode mudar o tamanho
de uma matriz, de facto, por si só

800
00:36:38,660 --> 00:36:43,040
em C. Você pode alocar outro array,
mover tudo, desde o antigo

801
00:36:43,040 --> 00:36:45,380
para o novo, e agora
ter algum espaço extra,

802
00:36:45,380 --> 00:36:47,469
mas não é como um
linguagem como Java ou Python

803
00:36:47,469 --> 00:36:49,760
ou qualquer número de outros
línguas com que alguns de vocês

804
00:36:49,760 --> 00:36:52,070
pode estar familiarizado onde você
pode simplesmente continuar adicionando coisas

805
00:36:52,070 --> 00:36:53,930
saciedade ao fim de uma matriz.

806
00:36:53,930 --> 00:36:57,880
Quando você tem uma série de
tamanho 6, que é o seu tamanho,

807
00:36:57,880 --> 00:37:01,970
e tão parecido com a idéia anterior
tendo um tampão de um determinado tamanho,

808
00:37:01,970 --> 00:37:05,940
você tem que adivinhar fora do portão
qual é o tamanho que você quer que ele seja?

809
00:37:05,940 --> 00:37:07,880
Se você adivinhar muito grande,
você está perdendo espaço.

810
00:37:07,880 --> 00:37:10,950
Se você adivinhar muito pequeno, você
Não é possível armazenar os dados, pelo menos,

811
00:37:10,950 --> 00:37:12,940
sem muito trabalho.

812
00:37:12,940 --> 00:37:18,180
>> Então, hoje, graças aos ponteiros, nós podemos
começar a costurar o nosso próprio costume

813
00:37:18,180 --> 00:37:20,989
estruturas de dados, e em
verdade, aqui é algo

814
00:37:20,989 --> 00:37:23,030
que parece um pouco mais
enigmática, à primeira vista,

815
00:37:23,030 --> 00:37:26,440
mas isso é o que nós vamos chamar um ligado
lista, e seu tipo de nome resume

816
00:37:26,440 --> 00:37:26,940
isto.

817
00:37:26,940 --> 00:37:29,550
É uma lista de números, ou em
Neste caso, uma lista de números,

818
00:37:29,550 --> 00:37:33,480
mas pode ser uma lista de tudo, mas
ela ligados entre si por meio de setas,

819
00:37:33,480 --> 00:37:36,380
e apenas dar um palpite
com qual técnica

820
00:37:36,380 --> 00:37:38,310
vamos ser capazes
para unir,

821
00:37:38,310 --> 00:37:42,540
tipo de como pipoca com um fio,
uma ligada listas retângulos aqui?

822
00:37:42,540 --> 00:37:43,936
Seus números?

823
00:37:43,936 --> 00:37:45,560
O que é o recurso de linguagem subjacente?

824
00:37:45,560 --> 00:37:46,350
>> AUDIÊNCIA: Um ponteiro.

825
00:37:46,350 --> 00:37:47,308
>> DAVID MALAN: Um ponteiro.

826
00:37:47,308 --> 00:37:51,700
Então cada um desses setas representa aqui
um ponteiro ou apenas um endereço.

827
00:37:51,700 --> 00:37:54,590
Portanto, em outras palavras, se eu quiser
para armazenar uma lista de números,

828
00:37:54,590 --> 00:37:59,040
Eu não posso simplesmente armazená-lo se eu quiser
a capacidade para aumentar e diminuir

829
00:37:59,040 --> 00:38:00,990
minha estrutura de dados em uma matriz.

830
00:38:00,990 --> 00:38:03,000
Então eu preciso ter um pouco
mais sofisticação,

831
00:38:03,000 --> 00:38:05,720
de notar que esta
tipo de imagem sugere

832
00:38:05,720 --> 00:38:08,650
que, se você só tem pequenos tópicos
ligar tudo em conjunto,

833
00:38:08,650 --> 00:38:13,100
provavelmente não é tão difícil de fazer espaço
entre dois destes rectângulos

834
00:38:13,100 --> 00:38:16,750
ou dois desses nós, como vamos começar
chamando-os, coloque em um novo nó,

835
00:38:16,750 --> 00:38:19,547
e depois com uma nova linha, apenas
abandonar os três nós juntos,

836
00:38:19,547 --> 00:38:22,880
a primeira, a última, e por um
que você acabou de inserir no meio.

837
00:38:22,880 --> 00:38:26,000
>> E, de fato uma lista ligada,
ao contrário de uma matriz, é dinâmico.

838
00:38:26,000 --> 00:38:27,840
Ela pode crescer e pode
encolher e você não faz

839
00:38:27,840 --> 00:38:32,434
tem que saber ou se importar com antecedência como
quantidade de dados que você vai estar armazenando,

840
00:38:32,434 --> 00:38:35,600
mas acontece que nós temos que ser um pouco
cuidadoso sobre como implementar isso.

841
00:38:35,600 --> 00:38:39,070
Então, primeiro vamos considerar como vamos implementar
um destes pequenos retângulos.

842
00:38:39,070 --> 00:38:40,690
É fácil de implementar um int.

843
00:38:40,690 --> 00:38:44,000
Você acabou de dizer int n e, em seguida,
você obtém 4 bytes para um int,

844
00:38:44,000 --> 00:38:49,089
mas como faço para obter um int, chamá-lo de n,
e, em seguida, um ponteiro, vamos chamá-lo em seguida.

845
00:38:49,089 --> 00:38:50,880
Poderíamos chamar essas
coisas qualquer coisa que quisermos

846
00:38:50,880 --> 00:38:53,590
mas eu preciso de uma estrutura de dados personalizado.

847
00:38:53,590 --> 00:38:54,257
Sim?

848
00:38:54,257 --> 00:38:57,020
>> AUDIÊNCIA: Ampersand [inaudível].

849
00:38:57,020 --> 00:39:00,940
>> DAVID MALAN: Então e comercial, vamos utilizar para
obter o endereço de um nó potencialmente.

850
00:39:00,940 --> 00:39:02,740
Mas precisamos de outro
O recurso de C em ordem

851
00:39:02,740 --> 00:39:06,700
para me dar a capacidade de criar
este retângulo costume, este costume

852
00:39:06,700 --> 00:39:08,919
variável se você, na memória.

853
00:39:08,919 --> 00:39:09,710
AUDIÊNCIA: Uma struct.

854
00:39:09,710 --> 00:39:10,626
DAVID MALAN: Uma struct.

855
00:39:10,626 --> 00:39:14,310
Lembre-se da última semana, introduzimos
struct, esta palavra-chave relativamente simples

856
00:39:14,310 --> 00:39:16,254
que nos permite fazer coisas como esta.

857
00:39:16,254 --> 00:39:18,420
C não veio com um conjunto de dados
estrutura chamada estudante.

858
00:39:18,420 --> 00:39:22,190
Ele vem com int e bóia e carvão animal e
tal, mas ele não vem com o aluno,

859
00:39:22,190 --> 00:39:26,750
mas podemos criar um tipo de dados do aluno,
uma estrutura estudante, com esta sintaxe

860
00:39:26,750 --> 00:39:27,250
Aqui.

861
00:39:27,250 --> 00:39:28,350
E você vai ver isso de novo e de novo.

862
00:39:28,350 --> 00:39:30,426
Então não se preocupe com
memorizar as palavras-chave,

863
00:39:30,426 --> 00:39:33,300
mas a palavra-chave que é importante é
apenas o fato de que nós dissemos struct

864
00:39:33,300 --> 00:39:37,590
e, em seguida, nós o chamamos de estudante e no interior
do aluno era um nome e uma casa

865
00:39:37,590 --> 00:39:39,390
ou um dormitório ou similares.

866
00:39:39,390 --> 00:39:41,980
>> E agora, hoje, vamos propor isso.

867
00:39:41,980 --> 00:39:45,240
Eu adicionei algumas palavras, mas se eu quiser
para implementar este retângulo que é

868
00:39:45,240 --> 00:39:48,440
tem tanto um int e um
ponteiro, você sabe, eu sou

869
00:39:48,440 --> 00:39:51,540
vai declarar uma estrutura chamado nó.

870
00:39:51,540 --> 00:39:55,630
Eu também sou, dentro dele, vai dizer
que um nó, rectângulo, tem um int

871
00:39:55,630 --> 00:39:59,730
e vamos chamá-lo e n
ele tem um ponteiro próximo.

872
00:39:59,730 --> 00:40:02,540
E isso é um pouco detalhado,
mas se você pensar sobre isso,

873
00:40:02,540 --> 00:40:07,300
as setas que estavam na imagem
um momento atrás são de que tipo de dados?

874
00:40:07,300 --> 00:40:12,330
Quando cada um desses setas apontando está
a que tipo de estrutura de dados?

875
00:40:12,330 --> 00:40:14,332
Não é apenas que aponta para um int per se.

876
00:40:14,332 --> 00:40:16,165
Ele está apontando para o
coisa toda rectangular

877
00:40:16,165 --> 00:40:18,720
e que coisa retangular,
nós dissemos, é chamado de nó.

878
00:40:18,720 --> 00:40:21,720
E então nós meio que tem que
recursivamente definir esta tais

879
00:40:21,720 --> 00:40:26,270
que um nó, digamos,
irá conter um int chamado n

880
00:40:26,270 --> 00:40:31,070
e um ponteiro chamado seguinte e no
tipo de estrutura de dados para o qual

881
00:40:31,070 --> 00:40:35,770
que os pontos de ponteiro é, aparentemente,
vai ser nó struct.

882
00:40:35,770 --> 00:40:41,550
>> Portanto, este é irritantemente verboso
e apenas para ser pedante,

883
00:40:41,550 --> 00:40:44,100
a razão pela qual nós não podemos
apenas dizer isto, que, francamente,

884
00:40:44,100 --> 00:40:46,860
parece muito mais legível,
é porque lembre-se que C ler

885
00:40:46,860 --> 00:40:48,710
as coisas de cima para baixo, da esquerda para a direita.

886
00:40:48,710 --> 00:40:54,120
Não é até chegarmos a ponto e vírgula
que a palavra-chave nó realmente existe.

887
00:40:54,120 --> 00:40:57,980
Portanto, se queremos ter esse tipo de
referência cíclico dentro dos dados

888
00:40:57,980 --> 00:41:02,120
estrutura, nós temos que fazer isso, onde
dizemos nó struct na parte superior, que

889
00:41:02,120 --> 00:41:06,770
dá-nos uma mais maneira de descrever este
coisa, então dentro dizemos nó struct,

890
00:41:06,770 --> 00:41:09,560
e depois na última linha
podemos dizer, tudo bem, C, a propósito,

891
00:41:09,560 --> 00:41:12,060
basta ligar para todo este maldito
coisa que um nó e parar

892
00:41:12,060 --> 00:41:14,360
usando a palavra-chave struct completamente.

893
00:41:14,360 --> 00:41:18,030
Portanto, esta é apenas uma espécie de sintática
truque que finalmente nos permite criar

894
00:41:18,030 --> 00:41:21,370
algo que se parece exatamente com isso.

895
00:41:21,370 --> 00:41:25,010
>> Então, se nós agora podemos assumir
implementar essa coisa em C,

896
00:41:25,010 --> 00:41:28,040
como é que nós, na verdade,
iniciar atravessando este?

897
00:41:28,040 --> 00:41:32,360
Bem, na verdade, tudo o que temos a fazer é
iteração da esquerda para a direita e apenas

898
00:41:32,360 --> 00:41:35,960
tipo de inserir os nós ou excluir nós
ou procurar coisas onde quisermos,

899
00:41:35,960 --> 00:41:39,560
mas para fazer isso, vamos em frente e fazer
as coisas um pouco mais real, porque isso

900
00:41:39,560 --> 00:41:42,560
tem sido super-baixo nível até agora.

901
00:41:42,560 --> 00:41:45,700
Será que alguém literalmente gostaria de ser o primeiro?

902
00:41:45,700 --> 00:41:46,200
ESTÁ BEM.

903
00:41:46,200 --> 00:41:47,092
Vamos lá para cima.

904
00:41:47,092 --> 00:41:47,800
Qual o seu nome?

905
00:41:47,800 --> 00:41:48,499
>> DAVID: David.

906
00:41:48,499 --> 00:41:49,290
DAVID MALAN: David.

907
00:41:49,290 --> 00:41:49,998
Bom te conhecer.

908
00:41:49,998 --> 00:41:50,960
Eu também.

909
00:41:50,960 --> 00:41:52,450
Tudo certo.

910
00:41:52,450 --> 00:41:53,990
E precisamos de um número 9.

911
00:41:53,990 --> 00:41:55,240
Não é tão bom como o primeiro, talvez.

912
00:41:55,240 --> 00:41:56,430
OK, número 9.

913
00:41:56,430 --> 00:41:59,667
Um número 17, por favor.

914
00:41:59,667 --> 00:42:01,000
Deixe-me voltar um pouco mais longe.

915
00:42:01,000 --> 00:42:03,980
Number 22, por favor, e
e quanto a mais para trás

916
00:42:03,980 --> 00:42:06,344
se eu posso ver nenhuma mão
com toda a luz ou não.

917
00:42:06,344 --> 00:42:08,010
Alguém está sendo ofereceu ali.

918
00:42:08,010 --> 00:42:08,968
Você quer chegar?

919
00:42:08,968 --> 00:42:10,450
Seu antebraço é forçado a subir.

920
00:42:10,450 --> 00:42:12,340
OK, 17.

921
00:42:12,340 --> 00:42:13,690
22.

922
00:42:13,690 --> 00:42:15,120
26 está vindo para baixo.

923
00:42:15,120 --> 00:42:18,450
Será que ninguém gosta de
forcefully-- Vamos lá para cima.

924
00:42:18,450 --> 00:42:21,030
Um voluntário real.

925
00:42:21,030 --> 00:42:23,330
>> Então, muito rapidamente, se
vocês poderiam organizar

926
00:42:23,330 --> 00:42:26,550
-se apenas como
os nós na tela.

927
00:42:26,550 --> 00:42:27,510
Obrigado.

928
00:42:27,510 --> 00:42:29,234
E você vai ser 26.

929
00:42:29,234 --> 00:42:30,650
Todas as introduções certas e rápidas.

930
00:42:30,650 --> 00:42:32,139
Então, eu estou David e você também?

931
00:42:32,139 --> 00:42:32,680
DAVID: David.

932
00:42:32,680 --> 00:42:33,721
DAVID MALAN: E você é?

933
00:42:33,721 --> 00:42:34,229
JAKE: Jake.

934
00:42:34,229 --> 00:42:34,729
SUE: Sue.

935
00:42:34,729 --> 00:42:35,229
ALEX: Alex.

936
00:42:35,229 --> 00:42:36,475
RAPHAEL: Raphael.

937
00:42:36,475 --> 00:42:37,100
TAYLOR: Taylor.

938
00:42:37,100 --> 00:42:37,466
DAVID MALAN: Taylor.

939
00:42:37,466 --> 00:42:37,590
Excelente.

940
00:42:37,590 --> 00:42:39,810
Então, esses são nossos voluntários
para hoje e ir em frente

941
00:42:39,810 --> 00:42:43,090
e mudar um pouco dessa forma,
e apenas ir em frente e manter

942
00:42:43,090 --> 00:42:47,024
segurando seus números como você é ou o seu
primeiro sinal e com a mão esquerda,

943
00:42:47,024 --> 00:42:48,940
vá em frente e apenas implementar
essas flechas, apenas

944
00:42:48,940 --> 00:42:51,360
de modo que a mão esquerda é, literalmente,
apontando para o que você deve apontar

945
00:42:51,360 --> 00:42:54,610
na, e dar-se algum espaço para que
podemos ver visualmente os braços, na verdade,

946
00:42:54,610 --> 00:42:58,120
apontando, e você pode apenas apontar
tipo de para o chão está bem.

947
00:42:58,120 --> 00:43:03,040
>> Portanto, temos aqui uma lista ligada de um,
dois, três, quatro, cinco nódulos inicialmente,

948
00:43:03,040 --> 00:43:05,860
e perceber que temos este especial
ponteiro no início quem é

949
00:43:05,860 --> 00:43:09,770
chave, porque temos de manter o controle
de toda a lista de comprimento de alguma forma.

950
00:43:09,770 --> 00:43:13,590
Esses caras, mesmo que sejam deixadas
para a direita, volta para trás na memória,

951
00:43:13,590 --> 00:43:15,950
na verdade, eles podem estar em qualquer lugar
na memória do computador.

952
00:43:15,950 --> 00:43:18,240
Então, esses caras poderiam ser
em pé em qualquer lugar na fase

953
00:43:18,240 --> 00:43:20,960
e isso é bom, contanto que eles são
na verdade, apontando para o outro,

954
00:43:20,960 --> 00:43:22,770
mas para manter as coisas
limpo e simples, nós vamos

955
00:43:22,770 --> 00:43:25,728
apenas desenhá-los esquerda para direita
este, mas pode haver lacunas maciças

956
00:43:25,728 --> 00:43:26,790
entre esses nós.

957
00:43:26,790 --> 00:43:30,710
>> Agora, se eu quero realmente inserir alguns
novo valor, vamos em frente e fazer isso.

958
00:43:30,710 --> 00:43:33,720
Nós temos uma oportunidade agora
para escolher outro nó.

959
00:43:33,720 --> 00:43:39,820
Digamos que vamos começar com mallocing 55.

960
00:43:39,820 --> 00:43:41,320
Será que alguém poderia me importo de ser malloc?

961
00:43:41,320 --> 00:43:42,280
OK, vamos lá para cima.

962
00:43:42,280 --> 00:43:42,992
Qual o seu nome?

963
00:43:42,992 --> 00:43:43,700
RAINBOW: Arco-íris.

964
00:43:43,700 --> 00:43:44,050
DAVID MALAN: Arco-íris?

965
00:43:44,050 --> 00:43:44,810
Tudo certo.

966
00:43:44,810 --> 00:43:46,600
Malloc do arco-íris.

967
00:43:46,600 --> 00:43:47,450
Vamos lá para cima.

968
00:43:47,450 --> 00:43:51,610
Portanto, agora temos de nos perguntar
algorithmically onde podemos colocar 55.

969
00:43:51,610 --> 00:43:53,610
Então, todos nós sabemos,
obviamente, onde ela provavelmente

970
00:43:53,610 --> 00:43:55,401
pertence, se nós estamos tentando
para manter este classificado

971
00:43:55,401 --> 00:43:58,299
e se vocês poderiam tomar uma
um passo para trás para que não caia

972
00:43:58,299 --> 00:43:59,590
o palco, que seria ótimo.

973
00:43:59,590 --> 00:44:01,420
Então, na verdade, Arco-Íris,
começar de novo aqui comigo,

974
00:44:01,420 --> 00:44:04,200
porque nós, como o computador pode agora
só vê uma variável de cada vez.

975
00:44:04,200 --> 00:44:05,190
Assim, se este é o primeiro nó.

976
00:44:05,190 --> 00:44:07,160
Observe que ele não é um nó,
ele é apenas um ponteiro,

977
00:44:07,160 --> 00:44:10,270
e é por isso que ele está desenhado para ser
apenas o tamanho de um ponteiro, não

978
00:44:10,270 --> 00:44:11,780
um desses rectângulos completos.

979
00:44:11,780 --> 00:44:16,650
Então, nós estamos indo para verificar em cada
iteração é de 55 a menos de 9?

980
00:44:16,650 --> 00:44:17,150
Não.

981
00:44:17,150 --> 00:44:19,060
É de 55 a menos de 17?

982
00:44:19,060 --> 00:44:19,720
Não.

983
00:44:19,720 --> 00:44:20,800
Menos de 22?

984
00:44:20,800 --> 00:44:22,020
Menos de 26?

985
00:44:22,020 --> 00:44:23,390
Menos de 34?

986
00:44:23,390 --> 00:44:25,890
E agora, obviamente,
Íris pertence no final.

987
00:44:25,890 --> 00:44:27,270
Então, para ser claro, eo que
era o seu nome, Taylor?

988
00:44:27,270 --> 00:44:27,895
>> TAYLOR: Taylor.

989
00:44:27,895 --> 00:44:32,510
DAVID MALAN: Então entre Taylor
mão esquerda e as mãos do arco-íris aqui,

990
00:44:32,510 --> 00:44:38,324
cuja mão precisa apontar para o que em
Para inserir 55 nesta lista?

991
00:44:38,324 --> 00:44:39,240
O que precisamos fazer?

992
00:44:39,240 --> 00:44:39,700
Sim?

993
00:44:39,700 --> 00:44:41,140
>> AUDIÊNCIA: a mão de Taylor
precisa apontar esquerda.

994
00:44:41,140 --> 00:44:41,680
>> DAVID MALAN: Exatamente.

995
00:44:41,680 --> 00:44:43,800
Então, a inserção de um nó
para o fim da lista

996
00:44:43,800 --> 00:44:47,140
é muito simples, porque Taylor apenas
tem a ponto, ao invés de para o chão

997
00:44:47,140 --> 00:44:49,640
ou vamos chamá-lo nulo,
nulo é uma espécie de ausência

998
00:44:49,640 --> 00:44:51,640
de um ponteiro ou uma especial
ponteiro zero, você está

999
00:44:51,640 --> 00:44:53,740
vai apontar com sua esquerda
mão no arco-íris e, em seguida, Arco-Íris,

1000
00:44:53,740 --> 00:44:55,910
Onde deve a sua esquerda
mão, provavelmente, apontar?

1001
00:44:55,910 --> 00:44:56,570
Baixa.

1002
00:44:56,570 --> 00:45:00,140
Não é bom se sua mão é uma espécie
de apontar fora aqui ou qualquer tipo de

1003
00:45:00,140 --> 00:45:00,640
que maneira.

1004
00:45:00,640 --> 00:45:02,407
Isso seria considerado
um valor de lixo,

1005
00:45:02,407 --> 00:45:04,240
mas se ela aponta para
algum valor conhecido, vamos

1006
00:45:04,240 --> 00:45:07,360
chamá-lo de zero ou nulo, que é OK
porque temos um termo neste

1007
00:45:07,360 --> 00:45:09,390
e sabemos que a lista agora está completa.

1008
00:45:09,390 --> 00:45:11,550
>> Então, o que é outra
caso relativamente simples?

1009
00:45:11,550 --> 00:45:13,125
Poderíamos malloc 5?

1010
00:45:13,125 --> 00:45:14,010
Vamos lá para cima.

1011
00:45:14,010 --> 00:45:14,782
Qual o seu nome?

1012
00:45:14,782 --> 00:45:15,490
TIFFANY: Tiffany.

1013
00:45:15,490 --> 00:45:16,000
DAVID MALAN: me desculpe?

1014
00:45:16,000 --> 00:45:16,470
TIFFANY: Tiffany.

1015
00:45:16,470 --> 00:45:16,880
DAVID MALAN: Tiffany.

1016
00:45:16,880 --> 00:45:17,110
Tudo certo.

1017
00:45:17,110 --> 00:45:19,071
Tiffany foi malloced
com o valor 5.

1018
00:45:19,071 --> 00:45:19,570
Vamos lá para cima.

1019
00:45:19,570 --> 00:45:23,820
Este é relativamente fácil demais, mas
vamos considerar a ordem das operações agora.

1020
00:45:23,820 --> 00:45:25,820
Foi muito fácil
com Taylor no final.

1021
00:45:25,820 --> 00:45:30,302
Número 5 é, naturalmente, menos do que 9,
e por isso temos David, dispomos de Tiffany,

1022
00:45:30,302 --> 00:45:31,260
e qual era o seu nome?

1023
00:45:31,260 --> 00:45:31,680
>> JAKE: Jake.

1024
00:45:31,680 --> 00:45:32,470
>> DAVID MALAN: Jake.

1025
00:45:32,470 --> 00:45:34,300
Tiffany, Jake, e David.

1026
00:45:34,300 --> 00:45:36,580
Cuja mão deve ser atualizado primeiro?

1027
00:45:36,580 --> 00:45:39,260

1028
00:45:39,260 --> 00:45:40,590
O que você quer fazer aqui?

1029
00:45:40,590 --> 00:45:45,244
Há um par de maneiras possíveis, mas
há também uma ou mais formas erradas.

1030
00:45:45,244 --> 00:45:46,620
>> AUDIÊNCIA: Comece com mais à esquerda.

1031
00:45:46,620 --> 00:45:47,800
>> DAVID MALAN: Comece com o mais à esquerda.

1032
00:45:47,800 --> 00:45:49,008
Quem é o mais à esquerda aqui, então?

1033
00:45:49,008 --> 00:45:49,700
AUDIÊNCIA: First.

1034
00:45:49,700 --> 00:45:50,366
>> DAVID MALAN: OK.

1035
00:45:50,366 --> 00:45:53,781
Então comece com o primeiro e onde você
quer atualizar mãos de David para ser?

1036
00:45:53,781 --> 00:45:54,780
AUDIÊNCIA: Rumo a 5.

1037
00:45:54,780 --> 00:45:55,446
DAVID MALAN: OK.

1038
00:45:55,446 --> 00:45:59,026
Então David, ponto em cinco
ou Tiffany aqui, e agora?

1039
00:45:59,026 --> 00:46:01,072
>> AUDIÊNCIA: Tiffany aponta para o 9?

1040
00:46:01,072 --> 00:46:04,030
DAVID MALAN: Perfeito, exceto de Binky
cabeça apenas uma espécie de caiu, certo?

1041
00:46:04,030 --> 00:46:06,820
Porque o que há de errado com
esta imagem, literalmente?

1042
00:46:06,820 --> 00:46:08,070
AUDIÊNCIA: Nada está apontando.

1043
00:46:08,070 --> 00:46:09,945
DAVID MALAN: Nada é
apontando para Jake agora.

1044
00:46:09,945 --> 00:46:13,360
Temos literalmente órfão 9
e 17, e nós temos literalmente

1045
00:46:13,360 --> 00:46:18,450
vazou tudo isso de memória, porque,
atualizar a mão de David em primeiro lugar, que é

1046
00:46:18,450 --> 00:46:21,660
bem, na medida em que é corretamente
apontando para Tiffany agora,

1047
00:46:21,660 --> 00:46:25,410
mas se ninguém tinha o
clarividência de apontar para Jake,

1048
00:46:25,410 --> 00:46:27,490
então nós perdemos o
totalidade dessa lista.

1049
00:46:27,490 --> 00:46:28,200
Então, vamos desfazer.

1050
00:46:28,200 --> 00:46:30,950
Então isso foi uma coisa boa para
tropeçar mas vamos corrigir agora.

1051
00:46:30,950 --> 00:46:33,624
O que devemos fazer primeiro em vez disso?

1052
00:46:33,624 --> 00:46:34,124
Sim?

1053
00:46:34,124 --> 00:46:35,791
>> AUDIÊNCIA: Tiffany deve apontar para o 9?

1054
00:46:35,791 --> 00:46:37,582
DAVID MALAN: Eu não posso
chegar tão perto de você.

1055
00:46:37,582 --> 00:46:38,720
Quem deve apontar para o 9?

1056
00:46:38,720 --> 00:46:39,220
>> AUDIÊNCIA: Tiffany.

1057
00:46:39,220 --> 00:46:39,390
>> DAVID MALAN: Tudo bem.

1058
00:46:39,390 --> 00:46:41,200
Então Tiffany deve primeiro ponto no 9.

1059
00:46:41,200 --> 00:46:43,550
Então Tiffany deve tomar
em um valor idêntico

1060
00:46:43,550 --> 00:46:45,820
para David, que parece
redundante, por um momento,

1061
00:46:45,820 --> 00:46:48,820
mas isso é bom porque agora, segundo
passo, podemos atualizar a mão de David

1062
00:46:48,820 --> 00:46:52,680
para apontar para Tiffany, e então se
Nós meio que limpar as coisas

1063
00:46:52,680 --> 00:46:55,740
como se este é o tipo de primavera-like,
agora que é uma inserção correcta.

1064
00:46:55,740 --> 00:46:56,700
Assim excelente.

1065
00:46:56,700 --> 00:46:57,970
Portanto, agora estamos quase lá.

1066
00:46:57,970 --> 00:47:01,075
Vamos inserir um final,
valor como o valor 20.

1067
00:47:01,075 --> 00:47:03,010
Se pudéssemos malloc um voluntário final?

1068
00:47:03,010 --> 00:47:04,140
Vamos lá para cima.

1069
00:47:04,140 --> 00:47:06,224
Então, este é um pouco mais complicado.

1070
00:47:06,224 --> 00:47:08,390
Mas, realmente, o código estamos
escrever, ainda que verbalmente,

1071
00:47:08,390 --> 00:47:10,610
é como ter um monte
se as condições de agora, certo?

1072
00:47:10,610 --> 00:47:12,318
Tivemos uma condição
verificando se ele pertence

1073
00:47:12,318 --> 00:47:13,840
no final, talvez o início.

1074
00:47:13,840 --> 00:47:15,940
Nós precisamos de algum tipo de loop para
encontrar o ponto no meio.

1075
00:47:15,940 --> 00:47:17,400
Então vamos fazer isso com o que é seu nome?

1076
00:47:17,400 --> 00:47:17,700
>> ERIC: Eric.

1077
00:47:17,700 --> 00:47:18,340
>> DAVID MALAN: Eric?

1078
00:47:18,340 --> 00:47:18,660
Eric.

1079
00:47:18,660 --> 00:47:19,368
Bom te conhecer.

1080
00:47:19,368 --> 00:47:20,490
Portanto, temos 20.

1081
00:47:20,490 --> 00:47:21,220
Menos de cinco?

1082
00:47:21,220 --> 00:47:21,530
Não.

1083
00:47:21,530 --> 00:47:22,160
Menos de nove?

1084
00:47:22,160 --> 00:47:22,410
Não.

1085
00:47:22,410 --> 00:47:23,050
Menos de 17?

1086
00:47:23,050 --> 00:47:23,550
Não.

1087
00:47:23,550 --> 00:47:23,740
ESTÁ BEM.

1088
00:47:23,740 --> 00:47:25,701
Ele pertence aqui e
seus nomes são novamente?

1089
00:47:25,701 --> 00:47:26,200
SUE: Sue.

1090
00:47:26,200 --> 00:47:26,880
DAVID MALAN: Sue.

1091
00:47:26,880 --> 00:47:27,379
ALEX: Alex.

1092
00:47:27,379 --> 00:47:28,790
DAVID MALAN: Sue, Alex, e?

1093
00:47:28,790 --> 00:47:29,290
ERIC: Eric.

1094
00:47:29,290 --> 00:47:30,120
DAVID MALAN: Eric.

1095
00:47:30,120 --> 00:47:32,140
Cujas mãos precisa ficar atualizado em primeiro lugar?

1096
00:47:32,140 --> 00:47:32,930
>> AUDIÊNCIA: Eric.

1097
00:47:32,930 --> 00:47:33,429
ESTÁ BEM.

1098
00:47:33,429 --> 00:47:35,200
Então Eric deve apontar para onde?

1099
00:47:35,200 --> 00:47:35,930
Aos 22 anos.

1100
00:47:35,930 --> 00:47:36,430
Boa.

1101
00:47:36,430 --> 00:47:38,180
E agora o que é o próximo?

1102
00:47:38,180 --> 00:47:40,800
Sue pode, então, apontar para Eric
e agora, se vocês apenas

1103
00:47:40,800 --> 00:47:44,077
fazer algum espaço, o que é bom
visualmente, agora que temos feito a inserção.

1104
00:47:44,077 --> 00:47:47,160
Então, vamos agora considerar uma pergunta, mas
muito obrigado para os nossos voluntários.

1105
00:47:47,160 --> 00:47:48,090
Muito bem feito.

1106
00:47:48,090 --> 00:47:50,831
Você pode manter esses, se você gosta.

1107
00:47:50,831 --> 00:47:54,140
E nós temos um belo presente de despedida se
você cada gostaria de ter uma bola de stress.

1108
00:47:54,140 --> 00:47:56,030
Deixe-me apenas passar isso para baixo.

1109
00:47:56,030 --> 00:47:58,430
Então, qual é o takeaway deste?

1110
00:47:58,430 --> 00:48:02,430
Este parece ser incrível
na medida em que temos agora

1111
00:48:02,430 --> 00:48:06,360
Apresentar uma alternativa para uma
matriz que não é tão confinado

1112
00:48:06,360 --> 00:48:07,780
para uma matriz de algum tamanho fixo.

1113
00:48:07,780 --> 00:48:09,380
Elas podem crescer de forma dinâmica.

1114
00:48:09,380 --> 00:48:13,220
>> Mas muito como temos visto em semanas
passado, nós nunca conseguir nada de graça,

1115
00:48:13,220 --> 00:48:15,740
como certamente há um trade-off aqui.

1116
00:48:15,740 --> 00:48:18,890
Assim, com um upside de um ligado
lista, é esse dinamismo?

1117
00:48:18,890 --> 00:48:21,590
Esta capacidade de crescer e, francamente,
que poderíamos ter feito de exclusão

1118
00:48:21,590 --> 00:48:23,570
e poderíamos encolher conforme necessário.

1119
00:48:23,570 --> 00:48:24,710
Qual o preço que estamos pagando?

1120
00:48:24,710 --> 00:48:28,510

1121
00:48:28,510 --> 00:48:30,340
Duas vezes mais espaço, em primeiro lugar.

1122
00:48:30,340 --> 00:48:34,010
Se você olhar para a foto, não mais
Eu sou armazenar uma lista de inteiros.

1123
00:48:34,010 --> 00:48:36,740
Eu estou armazenando uma lista de
inteiros mais ponteiros.

1124
00:48:36,740 --> 00:48:38,240
Então, eu estou dobrando a quantidade de espaço.

1125
00:48:38,240 --> 00:48:40,740
Agora, talvez isso não seja tão
um grande negócio 4 bytes, 8 bytes,

1126
00:48:40,740 --> 00:48:43,160
mas certamente poderia adicionar
-se para grandes conjuntos de dados.

1127
00:48:43,160 --> 00:48:45,570
O que é outra desvantagem?

1128
00:48:45,570 --> 00:48:46,070
Sim?

1129
00:48:46,070 --> 00:48:48,010
>> AUDIÊNCIA: Nós temos que
atravessá-los um por um.

1130
00:48:48,010 --> 00:48:48,760
DAVID MALAN: Yeah.

1131
00:48:48,760 --> 00:48:50,260
Nós temos que atravessá-los um por um.

1132
00:48:50,260 --> 00:48:53,860
Você sabe o que, que deram este super
recurso conveniente de colchete

1133
00:48:53,860 --> 00:48:57,240
notação, mais propriamente
conhecido como acesso aleatório,

1134
00:48:57,240 --> 00:48:59,280
onde podemos simplesmente pular
a um elemento individual

1135
00:48:59,280 --> 00:49:01,470
mas agora se eu ainda tinha
meus voluntários aqui,

1136
00:49:01,470 --> 00:49:04,660
se eu queria encontrar o
número 22, eu não posso apenas

1137
00:49:04,660 --> 00:49:06,620
saltar para suporte algo algo.

1138
00:49:06,620 --> 00:49:10,530
Eu tenho que olhar sobre a lista, muito
como nossos exemplos de pesquisa de forma linear,

1139
00:49:10,530 --> 00:49:12,260
para encontrar o número 22.

1140
00:49:12,260 --> 00:49:14,340
Então, nós parecem ter pago um preço lá.

1141
00:49:14,340 --> 00:49:16,430
Mas a gente pode, no entanto,
resolver outros problemas.

1142
00:49:16,430 --> 00:49:18,587
>> Na verdade, deixe-me apresentar
apenas um par de elementos visuais.

1143
00:49:18,587 --> 00:49:20,920
Então, se você foi para baixo para
Mather do Refeitório recentemente,

1144
00:49:20,920 --> 00:49:23,320
você deve se lembrar que a sua
pilhas de bandejas como este,

1145
00:49:23,320 --> 00:49:26,300
nós emprestamos estes a partir de
Annenberg antes da aula.

1146
00:49:26,300 --> 00:49:28,930
Portanto, esta pilha de bandejas, porém,
na verdade, é representativa

1147
00:49:28,930 --> 00:49:30,860
de uma estrutura de dados informática.

1148
00:49:30,860 --> 00:49:32,910
Existe uma estrutura de dados
em ciência da computação

1149
00:49:32,910 --> 00:49:38,010
conhecida como uma pilha que muito bem
presta-se a exatamente esse visual.

1150
00:49:38,010 --> 00:49:41,380
Por isso, se cada uma destas bandejas não é um
bandeja, mas como um número e eu queria

1151
00:49:41,380 --> 00:49:45,010
para armazenar números, eu
poderia colocar um aqui em baixo,

1152
00:49:45,010 --> 00:49:48,320
e eu poderia colocar outro aqui em baixo,
e continuar empilhamento números

1153
00:49:48,320 --> 00:49:53,180
em cima do outro, e que está
potencialmente útil sobre esta

1154
00:49:53,180 --> 00:49:55,450
é que o que é a implicação
desta estrutura de dados?

1155
00:49:55,450 --> 00:49:58,045
Que número posso retirar
primeiro o mais convenientemente?

1156
00:49:58,045 --> 00:50:00,640

1157
00:50:00,640 --> 00:50:03,030
O mais recentemente, um posto lá.

1158
00:50:03,030 --> 00:50:06,430
>> Então é isso que nós chamaríamos em
ciência da computação uma estrutura de dados LIFO.

1159
00:50:06,430 --> 00:50:08,070
Último a entrar, primeiro a sair.

1160
00:50:08,070 --> 00:50:10,800
E vamos ver em breve por que
que pode ser útil, mas, por agora,

1161
00:50:10,800 --> 00:50:12,200
basta considerar o imóvel.

1162
00:50:12,200 --> 00:50:15,158
E é uma espécie de idiota se você acha
sobre como o salão de jantar faz.

1163
00:50:15,158 --> 00:50:17,910
Toda vez que eles bandejas limpas e
colocar os mais frescos no topo,

1164
00:50:17,910 --> 00:50:22,160
você poderia ter uma limpo anteriormente
mas, eventualmente, muito sujo e empoeirado

1165
00:50:22,160 --> 00:50:24,360
bandeja na parte inferior
se você nunca realmente

1166
00:50:24,360 --> 00:50:26,820
chegar ao fundo da referida
pilha, porque você só

1167
00:50:26,820 --> 00:50:29,380
manter colocando o novo e
os limpos em cima dela.

1168
00:50:29,380 --> 00:50:31,840
A mesma coisa pode acontecer
num supermercado também.

1169
00:50:31,840 --> 00:50:35,450
Se você tem um caso de exibição
de leite e cada vez CVS

1170
00:50:35,450 --> 00:50:37,610
ou quem recebe mais leite,
você apenas empurrar os leites

1171
00:50:37,610 --> 00:50:39,880
você já tem a parte de trás e
você colocar os novos na frente,

1172
00:50:39,880 --> 00:50:43,088
você vai ter alguns bastante desagradável
leite no final da estrutura de dados,

1173
00:50:43,088 --> 00:50:46,390
porque é sempre na parte inferior ou
equivalentemente é sempre na parte de trás.

1174
00:50:46,390 --> 00:50:50,407
>> Mas há outra maneira de pensar sobre
alinhando dados e por exemplo, isso.

1175
00:50:50,407 --> 00:50:53,490
Se você é uma daquelas pessoas que gosta
a linha de fora de lojas da Apple

1176
00:50:53,490 --> 00:50:55,610
quando um novo produto vem
fora, você provavelmente está

1177
00:50:55,610 --> 00:50:58,780
Não usando uma pilha de dados
estrutura porque você

1178
00:50:58,780 --> 00:51:03,070
alienaria todos os outros que é
fazendo fila para comprar algum brinquedo novo.

1179
00:51:03,070 --> 00:51:06,610
Em vez disso, você provavelmente está usando
que tipo de estrutura de dados

1180
00:51:06,610 --> 00:51:10,050
ou que tipo de sistema
no mundo real?

1181
00:51:10,050 --> 00:51:13,493
Esperemos que seja uma linha, ou mais
corretamente ou mais britânico-like, uma fila.

1182
00:51:13,493 --> 00:51:17,700
E verifica-se uma fila é também um
estrutura de dados em ciência da computação,

1183
00:51:17,700 --> 00:51:19,700
mas uma fila tem uma muito
propriedade diferente.

1184
00:51:19,700 --> 00:51:20,820
Não é LIFO.

1185
00:51:20,820 --> 00:51:21,990
Último a entrar, primeiro a sair.

1186
00:51:21,990 --> 00:51:22,800
Deus me livre.

1187
00:51:22,800 --> 00:51:24,280
É, em vez FIFO.

1188
00:51:24,280 --> 00:51:26,110
Primeiro a entrar, primeiro a sair.

1189
00:51:26,110 --> 00:51:27,970
E isso é uma coisa boa
de justiça amor '

1190
00:51:27,970 --> 00:51:30,428
certamente quando você está alinhando
super início da manhã.

1191
00:51:30,428 --> 00:51:33,400
Se você chegar lá primeiro, você
quer sair primeiro também.

1192
00:51:33,400 --> 00:51:35,880
>> E assim todos estes dados
estruturas, filas e pilhas

1193
00:51:35,880 --> 00:51:39,220
e cachos de outros, acaba por você
pode pensar nisso como apenas uma matriz.

1194
00:51:39,220 --> 00:51:41,820
Esta é uma matriz, talvez
um tamanho fixo 4, mas tinha

1195
00:51:41,820 --> 00:51:44,990
ser uma espécie de bom se pudéssemos simplesmente amontoar
bandejas quase infinitamente alto se

1196
00:51:44,990 --> 00:51:46,780
têm que muitas bandejas ou números.

1197
00:51:46,780 --> 00:51:48,840
Então, talvez nós queremos
usar uma lista ligada aqui,

1198
00:51:48,840 --> 00:51:51,800
mas o trade-off vai ser
potencialmente que precisamos de mais memória,

1199
00:51:51,800 --> 00:51:55,930
leva um pouco mais de tempo, mas nós
não limitar a altura da pilha,

1200
00:51:55,930 --> 00:51:59,550
bem como vitrine de Mather
pode limitar o tamanho da pilha,

1201
00:51:59,550 --> 00:52:03,117
e assim que estas são decisões de projeto ou
opções disponíveis para nós em última instância.

1202
00:52:03,117 --> 00:52:04,950
Assim, com estes dados
estruturas, nós começamos

1203
00:52:04,950 --> 00:52:09,360
vendo novos limites superiores potencialmente
sobre o que anteriormente foi super rápido

1204
00:52:09,360 --> 00:52:11,260
e onde vamos deixá
fora hoje e onde

1205
00:52:11,260 --> 00:52:13,200
vamos esperar para chegar a
é na quarta-feira, nós vamos

1206
00:52:13,200 --> 00:52:15,740
começar a olhar para um conjunto de dados
estrutura que nos permite pesquisar

1207
00:52:15,740 --> 00:52:18,260
através de dados em log tempo final novamente.

1208
00:52:18,260 --> 00:52:21,470
E vimos que, lembre-se, na semana de zero
e um com busca binária ou dividir

1209
00:52:21,470 --> 00:52:22,180
e conquistar.

1210
00:52:22,180 --> 00:52:26,240
Está vindo de volta e melhor ainda,
o Santo Graal para nesta quarta-feira

1211
00:52:26,240 --> 00:52:29,510
será a de chegar com o
estrutura de dados que corre verdadeiramente

1212
00:52:29,510 --> 00:52:32,070
ou em teoricamente
constante de tempo, por meio de que

1213
00:52:32,070 --> 00:52:34,760
não importa quantas
milhões ou bilhões de coisas

1214
00:52:34,760 --> 00:52:38,470
temos na estrutura de dados, ele será
levar-nos tempo constante, talvez um passo

1215
00:52:38,470 --> 00:52:41,387
ou dois passos ou 10 passos,
mas números de passos constantes

1216
00:52:41,387 --> 00:52:42,970
para procurar por essa estrutura de dados.

1217
00:52:42,970 --> 00:52:46,300
Que de fato será o santo graal
mas mais sobre isso na quarta-feira.

1218
00:52:46,300 --> 00:52:49,045
See ya então.

1219
00:52:49,045 --> 00:52:53,704
>> [Música tocando]

1220
00:52:53,704 --> 00:56:08,448