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
>> [REPRODUCIÓN DE VIDEO]

4
00:00:11,610 --> 00:00:13,640
>> -El Está mentindo.

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

6
00:00:14,380 --> 00:00:17,182
>> -Eu Non sei.

7
00:00:17,182 --> 00:00:19,990
>> -Entón, ¿Que sabemos?

8
00:00:19,990 --> 00:00:23,145
>> -Iso Ás 9:15, Ray
Santoya estaba no cadro electrónico.

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

10
00:00:23,644 --> 00:00:27,030
Entón a pregunta é, o que
estaba facendo en 09:16?

11
00:00:27,030 --> 00:00:29,720
>> -Shooting A nove milímetros en algo.

12
00:00:29,720 --> 00:00:31,540
Quizais el viu o tire.

13
00:00:31,540 --> 00:00:33,412
>> -ou Estaba traballando con el.

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

15
00:00:34,340 --> 00:00:36,200
Volva un.

16
00:00:36,200 --> 00:00:36,975
>> -O Que ve?

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

18
00:00:44,400 --> 00:00:47,805
>> -Trazer A cara superior pantalla completa.

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

20
00:00:48,680 --> 00:00:50,060
>> -Hai Unha reflexión.

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

22
00:01:00,455 --> 00:01:02,280
>> -É O equipo de béisbol Nuevitas.

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

24
00:01:03,110 --> 00:01:05,820
>> -E Está falando con
quen está a usar esa chaqueta.

25
00:01:05,820 --> 00:01:06,670
>> [FIN DE REPRODUCIÓN]

26
00:01:06,670 --> 00:01:07,628
>> DAVID Malan: Todo ben.

27
00:01:07,628 --> 00:01:11,210
Esta é CS50 e iso é un pouco máis
de [inaudível] coa que está

28
00:01:11,210 --> 00:01:12,890
xogar con problema establecer catro.

29
00:01:12,890 --> 00:01:16,606
Hoxe comezamos a mirar un pouco máis
profundamente para isto chamadas punteiros,

30
00:01:16,606 --> 00:01:18,480
que a pesar de ser
un tema moi misterioso,

31
00:01:18,480 --> 00:01:20,813
verifícase que vai
a ser o medio a través do cal nós

32
00:01:20,813 --> 00:01:24,320
Pode comezar a construír e montar
programas moito máis sofisticado.

33
00:01:24,320 --> 00:01:28,150
Pero o que fixemos o mércores pasado
por medio dalgúns claymation primeiro.

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

35
00:01:30,190 --> 00:01:33,148
para dar un ollo a un programa que
realmente non fai nada de interesante,

36
00:01:33,148 --> 00:01:34,950
pero revelou algúns problemas.

37
00:01:34,950 --> 00:01:38,570
Entón, para comezar hoxe, por que non podemos andar
rapidamente a través de algúns destes pasos,

38
00:01:38,570 --> 00:01:41,920
tentar destilar en termos de humanos
exactamente o que está a suceder aquí

39
00:01:41,920 --> 00:01:45,410
e por que iso é malo, e, a continuación, seguir adiante
e realmente comezar a construír algo

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

41
00:01:46,309 --> 00:01:48,350
Entón, eses foron os primeiros
dúas liñas neste programa

42
00:01:48,350 --> 00:01:51,340
e en termos leigos, que
son estas dúas liñas facendo?

43
00:01:51,340 --> 00:01:55,600
Alguén que é razoablemente cómodo
co que está declarado na pantalla?

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

45
00:01:58,340 --> 00:02:00,120
Cales son esas dúas liñas que fan?

46
00:02:00,120 --> 00:02:02,070
Non é todo o que
diferente dunha semana,

47
00:02:02,070 --> 00:02:03,611
pero hai algún novo símbolo especial.

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

49
00:02:04,152 --> 00:02:05,628
Volver alí.

50
00:02:05,628 --> 00:02:07,092
>> Audiencia: Declarando punteiros?

51
00:02:07,092 --> 00:02:08,050
DAVID Malan: Diga novo?

52
00:02:08,050 --> 00:02:08,860
Audiencia: Declarando punteiros?

53
00:02:08,860 --> 00:02:11,776
DAVID Malan: Declarando e punteiros
Imos refinala-lo un pouco máis.

54
00:02:11,776 --> 00:02:14,050
Audiencia: [inaudível]
dirección e, a continuación, x y.

55
00:02:14,050 --> 00:02:15,300
DAVID Malan: E, a continuación, abordar.

56
00:02:15,300 --> 00:02:18,550
Entón, especialmente o que estamos facendo
é que estamos a declarar dúas variables.

57
00:02:18,550 --> 00:02:21,252
Estas variables, con todo, van
para ser do tipo int estrela, que

58
00:02:21,252 --> 00:02:23,210
significa concreto
eles van para almacenar

59
00:02:23,210 --> 00:02:26,450
a dirección de un int,
respectivamente, X e Y.

60
00:02:26,450 --> 00:02:27,660
Agora hai calquera valores?

61
00:02:27,660 --> 00:02:32,621
Hai algún enderezos reais nestes
dúas variables neste momento no tempo?

62
00:02:32,621 --> 00:02:33,120
Non.

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

64
00:02:35,030 --> 00:02:38,120
Se realmente non asignar un
variable, o que estaba na RAM

65
00:02:38,120 --> 00:02:42,224
anteriormente vai cubrir con ceros
e as dúas desas variables.

66
00:02:42,224 --> 00:02:44,140
Pero aínda non sabemos
o que son e que é

67
00:02:44,140 --> 00:02:47,060
será a clave para por que Binky
perdeu a cabeza a semana pasada.

68
00:02:47,060 --> 00:02:49,980
>> Polo tanto, este foi o claymation
encarnación do presente

69
00:02:49,980 --> 00:02:53,580
en que ten só dúas variables,
pequenos anacos circulares de arxila,

70
00:02:53,580 --> 00:02:57,330
que pode almacenar variables, pero canto
as frechas implicadas enriba suxiren,

71
00:02:57,330 --> 00:03:00,640
eles non están realmente apuntando
a calquera lugar coñecido per se.

72
00:03:00,640 --> 00:03:03,670
Entón, despois, tivo esta liña, e esta
era novo a semana pasada, malloc para a memoria

73
00:03:03,670 --> 00:03:07,130
asignación, que é só un xeito elegante
de dicir ao sistema operativo, Linux

74
00:03:07,130 --> 00:03:09,750
ou Mac OS ou Windows,
hey, me dea un pouco de memoria,

75
00:03:09,750 --> 00:03:11,780
e todo o que ten que dicir
o sistema operativo

76
00:03:11,780 --> 00:03:14,699
é o que cando pedíndolle para a memoria.

77
00:03:14,699 --> 00:03:16,990
El non vai importar co
vai facer con el,

78
00:03:16,990 --> 00:03:19,786
pero ten que dicir ao funcionamento
sistema que por medio de malloc.

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

80
00:03:20,286 --> 00:03:21,078
>> Audiencia: Canto?

81
00:03:21,078 --> 00:03:21,994
DAVID Malan: Canto?

82
00:03:21,994 --> 00:03:25,280
Canto en bytes, e así, este, de novo,
un exemplo artificial, está só dicindo,

83
00:03:25,280 --> 00:03:27,360
dáme o tamaño dun int.

84
00:03:27,360 --> 00:03:30,550
Agora, o tamaño dun int
é de catro bytes ou 32 bits.

85
00:03:30,550 --> 00:03:32,850
Polo tanto, esta é só unha forma de
dicindo, hey, sistema operativo,

86
00:03:32,850 --> 00:03:37,290
dáme catro bytes de memoria
que podo usar a miña disposición,

87
00:03:37,290 --> 00:03:40,560
e, especialmente, o que fai
retorno malloc respecto

88
00:03:40,560 --> 00:03:41,795
para ese anaco de catro bytes?

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

90
00:03:44,110 --> 00:03:44,860
Audiencia: Enderezo?

91
00:03:44,860 --> 00:03:45,901
DAVID Malan: O enderezo.

92
00:03:45,901 --> 00:03:47,580
O enderezo dese anaco de catro bytes.

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

94
00:03:48,190 --> 00:03:51,430
E iso é o que está almacenado en definitiva,
en x e é por iso que nós realmente non

95
00:03:51,430 --> 00:03:55,240
importa o que o número de que
dirección é, se é OX1 ou ox2

96
00:03:55,240 --> 00:03:57,110
ou algún enderezo hexadecimal enigmática.

97
00:03:57,110 --> 00:03:59,850
Nós só coidar pictoricamente
que esa variable x é agora

98
00:03:59,850 --> 00:04:01,630
apuntando a que o anaco de memoria.

99
00:04:01,630 --> 00:04:05,570
Así, a frecha representa un punteiro, ou
máis especificamente, un enderezo de memoria.

100
00:04:05,570 --> 00:04:09,120
Pero, de novo, non importa tipicamente
o que estes enderezos son reais.

101
00:04:09,120 --> 00:04:11,780
Agora, esta liña di
o que en termos leigos?

102
00:04:11,780 --> 00:04:14,330
Estrela x recibe 42 punto e coma.

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

104
00:04:17,390 --> 00:04:18,200
Quere ir?

105
00:04:18,200 --> 00:04:20,102
Non arranhe seu pescozo.

106
00:04:20,102 --> 00:04:22,360
>> Audiencia: O enderezo x está no 42.

107
00:04:22,360 --> 00:04:24,300
>> DAVID Malan: O enderezo de x é a 42.

108
00:04:24,300 --> 00:04:25,190
Non é ben así.

109
00:04:25,190 --> 00:04:28,485
Tan preto, pero non completamente, porque non hai
a estrela que está prefixing este x.

110
00:04:28,485 --> 00:04:29,860
Por iso, necesitamos axustar un pouco.

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

112
00:04:31,032 --> 00:04:36,044
>> Audiencia: O valor que
punteiro x está a apuntar cara é de 42.

113
00:04:36,044 --> 00:04:36,710
DAVID Malan: Aceptar.

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

115
00:04:40,840 --> 00:04:44,165
ou dito doutra forma, a estrela
x di, ir a calquera outro enderezo

116
00:04:44,165 --> 00:04:48,340
está x, tanto se se trata dunha Oxford
Rúa 33 ou Oxford Street

117
00:04:48,340 --> 00:04:51,850
ou OX1 ou ox33, calquera que sexa
que dirección numérico é,

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

119
00:04:54,380 --> 00:04:57,297
Entón, vai a este enderezo e
a continuación, poñer o número 42 alí.

120
00:04:57,297 --> 00:04:59,380
Así que sería un
xeito equivalente a dicir iso.

121
00:04:59,380 --> 00:05:01,860
Entón, iso é todo moi ben e, a continuación,
que representaría a imaxe

122
00:05:01,860 --> 00:05:05,370
deste xeito, onde nós engadimos
o 42 a ese pedazo de catro

123
00:05:05,370 --> 00:05:09,370
bytes no lateral dereita, pero
esta liña foi onde as cousas deron mal

124
00:05:09,370 --> 00:05:11,120
ea cabeza de Binky estalou
fóra neste punto,

125
00:05:11,120 --> 00:05:15,290
porque cousas malas suceden cando
vostede dereference valores de lixo

126
00:05:15,290 --> 00:05:18,210
ou cancelar a referencia válida
punteiros, e digo non válido

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

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

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

130
00:05:25,360 --> 00:05:26,115
Que é iso?

131
00:05:26,115 --> 00:05:26,990
>> Audiencia: Este enderezo.

132
00:05:26,990 --> 00:05:28,460
DAVID Malan: Este enderezo.

133
00:05:28,460 --> 00:05:31,910
Debe ser un enderezo
pero teño inicializar-lo?

134
00:05:31,910 --> 00:05:32,800
Entón eu non teño aínda.

135
00:05:32,800 --> 00:05:35,430
Entón, o que é coñecido por ser aí?

136
00:05:35,430 --> 00:05:37,590
É só un valor de lixo.

137
00:05:37,590 --> 00:05:41,500
Podería ser calquera enderezo de cero a
2 millóns se ten dous Gb de RAM,

138
00:05:41,500 --> 00:05:44,289
ou cero a 4 millóns se ten
ten catro gigabytes de memoria RAM.

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

140
00:05:46,080 --> 00:05:48,200
que o sistema operativo,
se non lle deu

141
00:05:48,200 --> 00:05:51,140
que pedazo de memoria especialmente
que estás ir,

142
00:05:51,140 --> 00:05:54,650
vai xeralmente para causar o que
vimos como un fallo de segmento.

143
00:05:54,650 --> 00:05:57,810
Entón, en realidade, calquera de vostedes que teñen
esforzouse en problemas no horario de oficina

144
00:05:57,810 --> 00:06:00,393
ou en problemas que é máis
xeralmente con tentando descubrir

145
00:06:00,393 --> 00:06:02,150
un fallo de segmentación,
que xeralmente significa

146
00:06:02,150 --> 00:06:05,017
está tocando un segmento de
memoria que non debe ser.

147
00:06:05,017 --> 00:06:07,350
Está tocando memoria que
o sistema operativo non ten

148
00:06:07,350 --> 00:06:10,450
permítelle tocar, se é
por ir demasiado lonxe na súa matriz

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

150
00:06:12,870 --> 00:06:14,780
memoria que é só un valor de lixo.

151
00:06:14,780 --> 00:06:18,230
>> Así facendo estrela x aquí é
tipo de comportamento indefinido.

152
00:06:18,230 --> 00:06:22,030
Vostede non debe facelo porque as probabilidades
son, o programa só vai fallar,

153
00:06:22,030 --> 00:06:24,050
porque está dicindo,
vaia a este enderezo

154
00:06:24,050 --> 00:06:27,000
e non ten idea de onde
este enderezo realmente é.

155
00:06:27,000 --> 00:06:30,300
Así, o sistema operativo é probable
indo para frear o seu programa

156
00:06:30,300 --> 00:06:33,840
como resultado e, de feito, iso é
o que pasou alí para Binky.

157
00:06:33,840 --> 00:06:37,210
Entón, finalmente, fixado Binky
este problema con este.

158
00:06:37,210 --> 00:06:38,909
Así que o programa en si foi fallo.

159
00:06:38,909 --> 00:06:41,450
Pero se especie de avanzar
e executar esta liña no seu lugar,

160
00:06:41,450 --> 00:06:45,580
y é igual x significa só o que quere
dirección é un x, tamén poñelas y.

161
00:06:45,580 --> 00:06:48,740
>> E así pictoricamente, temos
esta representada con dúas frechas

162
00:06:48,740 --> 00:06:51,570
desde xe de y ligazón
para o mesmo lugar.

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

164
00:06:55,760 --> 00:07:00,300
almacenar a mesma
enderezo, ergo apuntando para 42,

165
00:07:00,300 --> 00:07:04,910
e agora, cando di estrela
y, vaia ao enderezo en y,

166
00:07:04,910 --> 00:07:06,790
este ten un efecto secundario interesante.

167
00:07:06,790 --> 00:07:10,320
Así, a dirección na que y é a
mesmo que a dirección en x.

168
00:07:10,320 --> 00:07:15,060
Entón, se di que ir ao enderezo
en y e cambie o valor para 13,

169
00:07:15,060 --> 00:07:17,140
Quen máis é afectado?

170
00:07:17,140 --> 00:07:21,100
X é, punto D, por así dicir,
deben ser afectados tamén.

171
00:07:21,100 --> 00:07:24,340
>> E, de feito, como Nick tirei esta foto
en claymation foi exactamente iso.

172
00:07:24,340 --> 00:07:28,665
Aínda que nós seguimos o punteiro
y, acabamos no mesmo lugar,

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

174
00:07:32,780 --> 00:07:35,720
entón veriamos o valor de 13.

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

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

177
00:07:39,760 --> 00:07:42,460
dicir a palabra pointee,
o que está apuntado

178
00:07:42,460 --> 00:07:44,650
no, pero a consistencia
co vídeo, entende

179
00:07:44,650 --> 00:07:47,520
iso é todo o que era
significaba nesa situación.

180
00:07:47,520 --> 00:07:54,190
Así dúbidas sobre claymation
ou punteiros ou só malloc aínda?

181
00:07:54,190 --> 00:07:54,850
Non?

182
00:07:54,850 --> 00:07:55,470
Todo ben.

183
00:07:55,470 --> 00:07:58,560
>> Así, sen máis
delongas, imos dar un ollo

184
00:07:58,560 --> 00:08:00,700
onde iso ten realmente
foi utilizado durante algún tempo.

185
00:08:00,700 --> 00:08:03,580
Entón tivemos esta biblioteca CS50
que ten todas estas funcións.

186
00:08:03,580 --> 00:08:06,810
Usamos GetInt moito, GetString,
probablemente GetLongLong anterior

187
00:08:06,810 --> 00:08:09,840
Na miña PSet un ou máis, pero
o que está realmente a suceder?

188
00:08:09,840 --> 00:08:12,920
Ben, imos dar un ollo rápida
por baixo do capuz con un programa que

189
00:08:12,920 --> 00:08:17,017
inspira por que nós dámoslle o CS50
biblioteca, e de feito como a semana pasada,

190
00:08:17,017 --> 00:08:18,850
que comezou a tomar os
Rodas pequenas.

191
00:08:18,850 --> 00:08:21,080
Entón, iso agora está clasificada
dun post-mortem que

192
00:08:21,080 --> 00:08:23,690
xa se arrastra
dentro da biblioteca CS50,

193
00:08:23,690 --> 00:08:27,250
aínda que agora comezará a moverse
lonxe dela para a maioría dos programas.

194
00:08:27,250 --> 00:08:29,460
>> Polo tanto, este é un programa chamado scanf 0.

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

196
00:08:30,510 --> 00:08:33,909
El só ten estas liñas, pero
introduce unha función chamada scanf

197
00:08:33,909 --> 00:08:36,909
que en realidade estamos indo a ver en
un momento no interior da biblioteca CS50,

198
00:08:36,909 --> 00:08:38,600
aínda que dunha forma un pouco diferente.

199
00:08:38,600 --> 00:08:41,330
Polo tanto, este programa na liña 16
é declarar unha variable x.

200
00:08:41,330 --> 00:08:43,150
Entón me dea catro bytes por int.

201
00:08:43,150 --> 00:08:45,750
El dixo a usuario,
número por favor, e, a continuación,

202
00:08:45,750 --> 00:08:49,010
esta é unha liña que interesante
realmente une a semana pasada

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

204
00:08:49,790 --> 00:08:53,230
Scanf, e, a continuación, entender que é preciso un
formato de cadea, así como printf,

205
00:08:53,230 --> 00:08:57,480
% I significa un int, e, a continuación, leva un
segundo argumento que parece un 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ó vin iso xa a semana pasada.

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

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

210
00:09:06,210 --> 00:09:08,450
¿Que facer en C e comercial?

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

212
00:09:08,950 --> 00:09:10,024
>> Audiencia: O enderezo de.

213
00:09:10,024 --> 00:09:11,190
DAVID Malan: O enderezo de.

214
00:09:11,190 --> 00:09:13,190
Polo tanto, é o contrario
o operador de estrela,

215
00:09:13,190 --> 00:09:17,270
mentres que o operador estrela di, ir
Neste enderezo, o operador E comercial

216
00:09:17,270 --> 00:09:20,280
di, descubrir a
dirección desa variable,

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

218
00:09:23,530 --> 00:09:26,320
é comprobar o usuario de
a entrada do teclado,

219
00:09:26,320 --> 00:09:29,970
dependendo do que el ou ela
tipos, e, a continuación, ler a entrada dese usuario

220
00:09:29,970 --> 00:09:32,970
nunha variable, pero nós
viu nas últimas dúas semanas

221
00:09:32,970 --> 00:09:36,080
que a referida función de conmutación que
intentou sen esforzo para aplicar

222
00:09:36,080 --> 00:09:37,110
só estaba roto.

223
00:09:37,110 --> 00:09:42,470
Lembre que coa función de intercambio,
se nós só declarado A e B como ints,

224
00:09:42,470 --> 00:09:47,040
fixemos intercambiar con éxito o
dúas variables dentro intercambio

225
00:09:47,040 --> 00:09:50,080
Así como con leite e DO,
pero así como intercambio volveu,

226
00:09:50,080 --> 00:09:55,200
cal foi o resultado respecto
a x e y, os valores orixinais?

227
00:09:55,200 --> 00:09:55,700
Nada.

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

229
00:09:56,200 --> 00:09:59,754
Nada aconteceu naquela época, porque
swaps cambiar só as súas copias locais,

230
00:09:59,754 --> 00:10:01,670
o que quere dicir, todos
esta vez, sempre que temos

231
00:10:01,670 --> 00:10:04,010
foi pasando argumentos
ás funcións, estamos

232
00:10:04,010 --> 00:10:05,939
só de paso copias destes argumentos.

233
00:10:05,939 --> 00:10:07,980
Pode facer que
o que quere con eles,

234
00:10:07,980 --> 00:10:10,890
pero eles van ter ningún
efecto sobre os valores orixinais.

235
00:10:10,890 --> 00:10:13,650
Entón, iso é problemático se
quero ter unha función como scanf

236
00:10:13,650 --> 00:10:17,170
na vida, cuxo obxectivo é facer a pescudas
a entrada do usuario desde o teclado

237
00:10:17,170 --> 00:10:22,010
e despois encher os espazos en branco, para
falar, é dicir, dar unha variable como x

238
00:10:22,010 --> 00:10:25,410
un valor, porque se eu fose
só para pasar x para scanf,

239
00:10:25,410 --> 00:10:28,790
se considerar a lóxica da última
semana, scanf pode facer o que quere

240
00:10:28,790 --> 00:10:33,100
cunha copia de x, pero non podía
cambiar permanentemente x salvo que damos

241
00:10:33,100 --> 00:10:37,120
scanf un mapa do tesouro, por así dicir,
onde X marca o lugar, en que

242
00:10:37,120 --> 00:10:41,860
pasamos a dirección x para que
scanf pode ir alí e realmente cambiar

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

244
00:10:42,920 --> 00:10:45,080
E así, de feito, todo
que este programa fai

245
00:10:45,080 --> 00:10:53,180
se eu fai scanf 0, na miña fonte
Directorio 5m, facer scanf 0,

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

247
00:10:57,730 --> 00:11:01,020
>> Polo tanto, non é tan interesante,
pero o que está de feito a suceder

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

249
00:11:04,820 --> 00:11:06,410
está sendo permanentemente cambiar.

250
00:11:06,410 --> 00:11:08,335
Agora, iso parece bo e
bo, e de feito,

251
00:11:08,335 --> 00:11:11,200
Parece que realmente non precisa
a biblioteca CS50 en todo máis.

252
00:11:11,200 --> 00:11:13,960
Por exemplo, imos realizar
isto unha vez aquí.

253
00:11:13,960 --> 00:11:15,750
Déixeme reabrídelo por un segundo.

254
00:11:15,750 --> 00:11:20,600
Imos tentar un número por favor e
en vez de dicir 50 como antes,

255
00:11:20,600 --> 00:11:22,810
imos só dicir non.

256
00:11:22,810 --> 00:11:24,000
OK, iso é un pouco raro.

257
00:11:24,000 --> 00:11:25,270
Aceptar.

258
00:11:25,270 --> 00:11:28,680
E só algunhas bobadas aquí.

259
00:11:28,680 --> 00:11:31,170
Por iso, non parece
xestionar situacións erradas.

260
00:11:31,170 --> 00:11:33,620
Entón, necesitamos minimamente inicio
engadindo un pouco de verificación de erros

261
00:11:33,620 --> 00:11:37,460
para asegurarse de que o usuario ten
ingresaran nun número real como 50,

262
00:11:37,460 --> 00:11:40,720
porque, ao parecer, escribindo palabras
non se detecta como problemática,

263
00:11:40,720 --> 00:11:42,020
pero probablemente debe ser.

264
00:11:42,020 --> 00:11:46,450
>> Imos ollar para esta versión agora que é
miña tentativa de reimplementar GetString.

265
00:11:46,450 --> 00:11:48,437
Se scanf ten todo isto
funcionalidade incorporada,

266
00:11:48,437 --> 00:11:51,270
por que fomos a xogar con estas
Rodas pequenas como GetString?

267
00:11:51,270 --> 00:11:55,450
Ben, aquí é, quizais, o meu propio
versión simple do GetString

268
00:11:55,450 --> 00:12:00,766
en que unha semana, eu podería dicir,
dáme unha corda e chamalo de buffer.

269
00:12:00,766 --> 00:12:03,390
Hoxe, eu vou comezar só
dicindo estrela char, que, recall,

270
00:12:03,390 --> 00:12:04,400
é só sinónimo.

271
00:12:04,400 --> 00:12:06,629
Parece asustado, pero é
exactamente o mesmo.

272
00:12:06,629 --> 00:12:09,420
Entón me dea un buffer variable chamada
que está indo a almacenar unha secuencia de caracteres,

273
00:12:09,420 --> 00:12:12,780
dicir a cadea user por favor,
e, a continuación, como antes,

274
00:12:12,780 --> 00:12:17,760
imos tratar prestar esta lección scanf
% S neste momento e, a continuación, pasar en tapón.

275
00:12:17,760 --> 00:12:19,310
Agora, unha comprobación de sanidade rápida.

276
00:12:19,310 --> 00:12:22,120
Por que non estou dicindo
E comercial tapón esta 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
Audiencia: Char estrela é un punteiro.

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

281
00:12:29,920 --> 00:12:34,080
estrela xa é un punteiro, un enderezo,
por definición, de estar alí aquela estrela.

282
00:12:34,080 --> 00:12:37,530
E se scanf espera un enderezo,
basta só pasar tapón.

283
00:12:37,530 --> 00:12:39,260
Non preciso dicir tapón e comercial.

284
00:12:39,260 --> 00:12:42,177
Para os curiosos, podería
facer algo así.

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

286
00:12:43,510 --> 00:12:47,240
Isto lle daría un punteiro
dun punteiro, o cal é en realidade

287
00:12:47,240 --> 00:12:50,050
unha cousa válida en C, pero para
Agora, imos mantelo simple

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

289
00:12:51,750 --> 00:12:54,100
Eu só vou pasar en
tapón e iso é correcto.

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

291
00:12:56,487 --> 00:12:58,820
Deixe-me ir adiante e executar ese
programa tras compilalo.

292
00:12:58,820 --> 00:13:00,902
Fai 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 un segundo.

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

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

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

298
00:13:10,880 --> 00:13:11,380
Aceptar.

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

300
00:13:12,720 --> 00:13:14,280
Necesítoo.

301
00:13:14,280 --> 00:13:16,750
CS50 ID ten varios
configuración

302
00:13:16,750 --> 00:13:18,280
que protexen vostede contra ti mesmo.

303
00:13:18,280 --> 00:13:21,300
Eu precisaba desactivar os de
executando clang manualmente polo de agora.

304
00:13:21,300 --> 00:13:22,140
Entón cadea por favor.

305
00:13:22,140 --> 00:13:25,560
Eu estou indo a ir adiante e escribir
no meu mundo Ola favorito.

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

307
00:13:26,490 --> 00:13:27,700
Isto non é o que eu escriba.

308
00:13:27,700 --> 00:13:29,690
Polo que é indicativo de
que algo está mal.

309
00:13:29,690 --> 00:13:33,920
Deixe-me ir adiante e escriba
nun tempo moi longo cadea.

310
00:13:33,920 --> 00:13:37,210
Grazas pola nulo e non sei
se eu vou ser capaz de lanzalo.

311
00:13:37,210 --> 00:13:40,240
Imos tentar un pouco de copia
pegar e ver se iso axuda.

312
00:13:40,240 --> 00:13:43,290
Pode pegar unha morea de presente.

313
00:13:43,290 --> 00:13:47,310
É en definitiva un maior
cadea que o habitual.

314
00:13:47,310 --> 00:13:51,450
Nós só realmente escribilo.

315
00:13:51,450 --> 00:13:51,950
Non.

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

317
00:13:52,650 --> 00:13:53,480
Non comandar atopados.

318
00:13:53,480 --> 00:13:54,550
Entón, iso é non relacionado.

319
00:13:54,550 --> 00:13:56,440
Isto é porque eu colei
algúns personaxes malos,

320
00:13:56,440 --> 00:13:59,780
pero iso acaba non vai traballar.

321
00:13:59,780 --> 00:14:03,510
>> Imos tentar que unha vez máis, porque
é máis divertido se realmente lanzalo.

322
00:14:03,510 --> 00:14:09,116
Imos escribir isto e agora, eu son
indo para copiar unha cadea moi longa

323
00:14:09,116 --> 00:14:10,990
e agora imos ver se nós
pode bater esa cousa.

324
00:14:10,990 --> 00:14:14,235
Repare que eu omitido espazos e
novas liñas correo comas

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

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

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

328
00:14:21,090 --> 00:14:22,880
E agora a rede só sendo lento.

329
00:14:22,880 --> 00:14:27,460
I preme Command-V moito tempo, claro.

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

331
00:14:28,190 --> 00:14:29,260
Non comandar atopados.

332
00:14:29,260 --> 00:14:29,780
>> Aceptar.

333
00:14:29,780 --> 00:14:32,240
Ben, o punto é
con todo, o seguinte.

334
00:14:32,240 --> 00:14:36,910
Entón, o que está realmente a suceder
sobre a presente declaración

335
00:14:36,910 --> 00:14:39,240
de tapón estrela carácter na liña 16?

336
00:14:39,240 --> 00:14:41,820
Entón, o que estou a recibir
cando declarar un punteiro?

337
00:14:41,820 --> 00:14:47,440
Todo o que eu estou a recibir é un valor de catro bytes
chamado de buffer, pero 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
É só un valor de lixo.

340
00:14:50,930 --> 00:14:54,170
Porque calquera momento declarar unha variable
en C, é só un valor de lixo,

341
00:14:54,170 --> 00:14:56,220
e estamos empezando a
viaxe sobre esta realidade.

342
00:14:56,220 --> 00:14:59,720
Agora, cando digo scanf,
vaia a este enderezo

343
00:14:59,720 --> 00:15:01,520
e poñer o que o usuario escribe.

344
00:15:01,520 --> 00:15:06,400
Se o usuario escribe Ola
mundo, así, onde me gustaría poñelas?

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

346
00:15:07,750 --> 00:15:11,510
>> Entón, iso é como unha especie de frecha
que está a apuntar quen sabe onde.

347
00:15:11,510 --> 00:15:13,880
Quizais está apuntando
ben aquí na miña memoria.

348
00:15:13,880 --> 00:15:16,560
E así, cando o usuario
tipo en Ola mundo,

349
00:15:16,560 --> 00:15:22,380
o programa tenta poñer o
Ola mundo secuencia barra invertida 0

350
00:15:22,380 --> 00:15:23,910
nese anaco de memoria.

351
00:15:23,910 --> 00:15:27,070
Pero, con alta probabilidade, pero
claramente non o 100% de probabilidade,

352
00:15:27,070 --> 00:15:30,440
o ordenador vai entón fallar
o programa porque este non é

353
00:15:30,440 --> 00:15:32,490
memoria que eu debería ser permitido tocar.

354
00:15:32,490 --> 00:15:36,330
Así, en breve, este programa é
fallo para exactamente ese motivo.

355
00:15:36,330 --> 00:15:38,070
Eu fundamentalmente non estou facendo o que?

356
00:15:38,070 --> 00:15:42,366
Que medidas teñen omitir, así como
nós omitimos co primeiro exemplo de Binky?

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

358
00:15:42,866 --> 00:15:43,710
>> Audiencia: reserva de memoria?

359
00:15:43,710 --> 00:15:45,001
>> DAVID Malan: distribución de memoria.

360
00:15:45,001 --> 00:15:48,400
Eu realmente non teño asignado
calquera memoria para esa secuencia.

361
00:15:48,400 --> 00:15:50,270
Así, podemos fixar iso nun par de formas.

362
00:15:50,270 --> 00:15:52,700
Un, podemos mantelo simple
e, de feito, agora está

363
00:15:52,700 --> 00:15:55,116
comezará a ver unha indefinición
das liñas entre o que

364
00:15:55,116 --> 00:15:58,520
unha matriz é, o que é unha cadea, o que é un
Char estrela, o que unha matriz de caracteres

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

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

367
00:16:02,450 --> 00:16:05,690
todo o que eu fixen en liña
16 é, en vez de dicir

368
00:16:05,690 --> 00:16:09,530
tapón que vai ser un char
estrela, un punteiro para un bloque de memoria,

369
00:16:09,530 --> 00:16:14,057
Vou dar moito proativamente
me un buffer para 16 caracteres,

370
00:16:14,057 --> 00:16:16,390
e de feito, se está familiarizado
co termo de tamponamento,

371
00:16:16,390 --> 00:16:20,570
probablemente dende o mundo dos vídeos,
onde un 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
Ben, cal é a conexión aquí?

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

375
00:16:24,960 --> 00:16:27,200
xeralmente é unha matriz
que é maior que 16.

376
00:16:27,200 --> 00:16:30,340
Pode ser unha matriz de tamaño
megabyte, quizais 10 megabytes,

377
00:16:30,340 --> 00:16:34,330
e para esa matriz fai seu navegador
descargar unha morea de bytes,

378
00:16:34,330 --> 00:16:37,500
un grupo enteiro de megabytes de
vídeo e reprodutor de vídeo,

379
00:16:37,500 --> 00:16:40,930
YouTube ou de quen queira que estea, comeza
lendo os bytes de matriz que,

380
00:16:40,930 --> 00:16:43,530
e en calquera momento ve o
palabra buffering, buffering,

381
00:16:43,530 --> 00:16:46,350
que significa que o xogador posúe
unha fin dese array.

382
00:16:46,350 --> 00:16:50,430
A rede é tan lento que non ten
recarreguen a matriz con máis bytes

383
00:16:50,430 --> 00:16:55,610
e entón está fóra de bits
para amosar para o usuario.

384
00:16:55,610 --> 00:16:59,430
>> Entón tapón é un termo apt aquí en que
é só unha matriz, unha peza de memoria.

385
00:16:59,430 --> 00:17:02,530
E iso vai resolve-lo
pois parece que

386
00:17:02,530 --> 00:17:07,410
que pode tratar matrices como se
son enderezos, aínda tapón

387
00:17:07,410 --> 00:17:10,710
é só un símbolo, é unha
secuencia de caracteres, buffer,

388
00:17:10,710 --> 00:17:14,760
que é útil para min, o programador,
pode pasar ao redor do seu nome

389
00:17:14,760 --> 00:17:17,079
como se fose un
punteiro, coma se

390
00:17:17,079 --> 00:17:21,000
foron a dirección dun anaco
de memoria para 16 caracteres.

391
00:17:21,000 --> 00:17:24,530
Entón, iso é para dicir, podo pasar
o scanf exactamente esa palabra

392
00:17:24,530 --> 00:17:30,670
e agora, se eu fai este programa,
facer scanf 2, punto scanf barra 2,

393
00:17:30,670 --> 00:17:35,386
e escriba Ola mundo,
Intro, que tempo--

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

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

396
00:17:39,340 --> 00:17:41,430
O que eu fixen de malo?

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

398
00:17:43,800 --> 00:17:44,705
Hola 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á facendo.

401
00:17:49,420 --> 00:17:49,920
Aceptar.

402
00:17:49,920 --> 00:17:51,628
Entón está lendo-se
ata que o primeiro espazo.

403
00:17:51,628 --> 00:17:55,680
Entón, imos enganar por só un momento e
dicir que eu só quería escribir algo

404
00:17:55,680 --> 00:18:01,408
realmente longa como esta é unha frase longa
iso é un, dous, tres, catro, 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
Aceptar.

407
00:18:05,300 --> 00:18:07,600
En realidade, é unha frase longa.

408
00:18:07,600 --> 00:18:10,710
Entón, esta frase é
máis de 16 caracteres

409
00:18:10,710 --> 00:18:13,670
e entón cando prema Intro,
o que vai pasar?

410
00:18:13,670 --> 00:18:16,940
Ben, neste caso do
tapón historia, eu declarara

411
00:18:16,940 --> 00:18:22,190
para ser realmente unha matriz
con 16 caracteres preparado para ir.

412
00:18:22,190 --> 00:18:27,426
Entón, un, dous, tres, catro, 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
Así, 16 caracteres, e agora, cando
ler en algo así como este é un longo

415
00:18:34,410 --> 00:18:43,950
sentenza, o que vai pasar é
que eu vou ler este é un 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
>> Polo tanto, esta é deliberadamente
algo malo que eu

418
00:18:52,270 --> 00:18:55,060
continuar a escribir máis aló do
límites da miña matriz,

419
00:18:55,060 --> 00:18:56,660
máis alá do meu tapón.

420
00:18:56,660 --> 00:19:00,100
Eu podería ter sorte e do programa
seguirá a funcionar e non me importa,

421
00:19:00,100 --> 00:19:03,450
pero dun modo xeral, esta
vai realmente bater o meu programa,

422
00:19:03,450 --> 00:19:06,440
e é un erro no meu
codificar o momento que eu paso

423
00:19:06,440 --> 00:19:08,576
máis alá
desa matriz, porque

424
00:19:08,576 --> 00:19:10,450
Non sei se é
necesariamente vai fallar

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ón, iso é problemático porque en
Neste caso, parece funcionar

427
00:19:15,750 --> 00:19:20,931
e imos tratar o destino aquí, aínda
o IDE parece tolerar un pouco

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

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

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

431
00:19:23,240 --> 00:19:26,470
Entón, eu son o único que pode ver iso.

432
00:19:26,470 --> 00:19:29,630
Entón, eu só tiña unha chea de diversión dixitación
unha frase real moi longo

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

434
00:19:32,800 --> 00:19:38,050
ingresaran nesta longa multi-liña tolo
frase, a continuación, teña en conta o que pasou.

435
00:19:38,050 --> 00:19:41,110
O programa intentou imprimir lo
e, a continuación, ten un fallo de segmento

436
00:19:41,110 --> 00:19:44,430
e fallos de segmentación é cando
algo como isto ocorre

437
00:19:44,430 --> 00:19:47,650
eo sistema operativo di
non, non pode tocar esa memoria.

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

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

440
00:19:51,180 --> 00:19:54,540
Eu mellorei o programa polo cal
polo menos, ter algunha memoria,

441
00:19:54,540 --> 00:19:58,000
pero isto parece limitarse
o GetString función para

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

443
00:20:00,780 --> 00:20:04,200
Entón, se quere apoiar máis
frases que 16 caracteres,

444
00:20:04,200 --> 00:20:04,880
que fas?

445
00:20:04,880 --> 00:20:07,970
Ben, pode aumentar o
tamaño desta reserva para 32

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

447
00:20:09,190 --> 00:20:12,260
Por que non imos só facer
que 1000, pero empurrar cara atrás.

448
00:20:12,260 --> 00:20:17,100
Cal é a resposta intuitivamente de
só evitar este problema, facendo

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 aplicar GetString deste xeito.

451
00:20:23,470 --> 00:20:27,130
O que é bo ou malo aquí?

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

453
00:20:28,033 --> 00:20:30,574
Audiencia: Se conectar unha morea
de espazo e non usalo,

454
00:20:30,574 --> 00:20:33,500
entón non pode redistribuir ese espazo.

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

456
00:20:34,500 --> 00:20:38,480
É un desperdicio na medida en que se non o fai
realmente precisa deses 900 bytes

457
00:20:38,480 --> 00:20:41,057
e aínda así está pedindo
1.000 en total de calquera xeito,

458
00:20:41,057 --> 00:20:44,140
só está consumindo máis memoria
o ordenador do usuario do que precisa,

459
00:20:44,140 --> 00:20:45,740
e despois de todo, algúns
xa atopou

460
00:20:45,740 --> 00:20:47,620
na vida que cando está
executando moitos programas

461
00:20:47,620 --> 00:20:50,470
e eles están comendo moita memoria,
isto pode realmente afectar o desempeño

462
00:20:50,470 --> 00:20:52,220
e experiencia do usuario
no ordenador.

463
00:20:52,220 --> 00:20:56,090
Entón, ese é o tipo de solución preguiceiro,
con certeza, e, inversamente,

464
00:20:56,090 --> 00:21:00,140
non é só un desperdicio, cal é o problema
aínda permanece, aínda que fago o meu tapón

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

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

467
00:21:02,600 --> 00:21:04,475
>> Audiencia: A cadea de lonxitude é 1.001.

468
00:21:04,475 --> 00:21:05,350
DAVID Malan: Exactamente.

469
00:21:05,350 --> 00:21:08,280
Se a secuencia de lonxitude é 1001,
tes exactamente o mesmo problema,

470
00:21:08,280 --> 00:21:10,705
e polo meu argumento, eu o faría
só, a continuación, facelo 2000,

471
00:21:10,705 --> 00:21:12,830
pero non sabe en
avanzar o quão grande debe ser,

472
00:21:12,830 --> 00:21:16,890
e aínda, eu teño que compilar meu programa
antes de deixar as persoas empregan e descargue

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

474
00:21:17,390 --> 00:21:21,490
Polo tanto, este é o tipo de
cousas que os intentos de biblioteca CS50

475
00:21:21,490 --> 00:21:24,750
para axudarnos con e nós só vai mirar
nalgúns dos implementación subxacente

476
00:21:24,750 --> 00:21:29,790
aquí, pero este é CS50 punto C. Este
é o ficheiro que estivo en CS50 IDE

477
00:21:29,790 --> 00:21:31,420
todas estas semanas que está a usar.

478
00:21:31,420 --> 00:21:34,280
É precompilados e ten
foi usalo automaticamente

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

480
00:21:38,780 --> 00:21:42,300
pero se eu rolar para abaixo a través de todos
estas funcións, é aquí GetString,

481
00:21:42,300 --> 00:21:44,636
e só para lle dar un
gústame o que está pasando,

482
00:21:44,636 --> 00:21:46,760
imos dar un ollo rápida en
a relativa complexidade.

483
00:21:46,760 --> 00:21:48,870
Non é un super longa
función, pero non o fixemos

484
00:21:48,870 --> 00:21:52,530
ten que pensar moito sobre todo
como ir sobre a obtención de cordas.

485
00:21:52,530 --> 00:21:55,660
>> Entón aquí está o meu tapón e eu
parecer Inicialize-o como nulo.

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

487
00:21:57,990 --> 00:22:00,585
pero eu decidir en
execución da biblioteca CS50

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

489
00:22:02,460 --> 00:22:05,770
Non sei de antemán como grande dun
usuarios de cordas van querer obter.

490
00:22:05,770 --> 00:22:08,140
Entón eu vou comezar
con só unha cadea baleira

491
00:22:08,140 --> 00:22:11,507
e eu estou indo a construír o maior
memoria como eu teño para se axustar á cadea user

492
00:22:11,507 --> 00:22:13,340
e se eu non teño
suficiente, eu vou pedir

493
00:22:13,340 --> 00:22:15,010
o sistema operativo para máis memoria.

494
00:22:15,010 --> 00:22:17,510
Eu estou indo a ir a súa secuencia
nun anaco grande de memoria

495
00:22:17,510 --> 00:22:21,847
e eu estou indo a liberar ou liberar o
insuficientemente gran peza de memoria

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

497
00:22:23,680 --> 00:22:25,570
>> Así, un ollo rápida,
aquí é só unha variable

498
00:22:25,570 --> 00:22:28,780
coa que eu vou manter o control
da capacidade do meu buffer.

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

500
00:22:30,071 --> 00:22:32,070
Aquí está unha variable n con
que vou continuar

501
00:22:32,070 --> 00:22:36,200
o control de cantos bytes están realmente en
o tapón ou que o usuario escribiu.

502
00:22:36,200 --> 00:22:39,900
Se non viu iso antes,
pode especificar que unha variable como un int

503
00:22:39,900 --> 00:22:46,370
é non asinado, que como o seu nome indica,
significa que é non negativo, e por que

504
00:22:46,370 --> 00:22:50,590
Nunca quero incomodar especificando
que un int non é só un int,

505
00:22:50,590 --> 00:22:52,540
pero é un int non asinado?

506
00:22:52,540 --> 00:22:55,064
É un int non negativo.

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

508
00:22:56,355 --> 00:22:58,910
>> Audiencia: É describindo unha cantidade
de memoria 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ón, se eu digo non asinado, este é, en realidade,
dándolle un pouco de memoria extra

511
00:23:03,710 --> 00:23:07,440
e parece medio parvo, pero se
ter un pouco de memoria adicional, que

512
00:23:07,440 --> 00:23:09,940
significa que ten o dobre
valores que poden representar,

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

514
00:23:11,570 --> 00:23:14,660
Entón, por defecto, un int pode ser máis ou menos
negativo de 2 millóns de todo o camiño

515
00:23:14,660 --> 00:23:16,030
ata positiva 2 millóns.

516
00:23:16,030 --> 00:23:18,540
Estas son grandes intervalos, pero
aínda é tipo de desperdicio

517
00:23:18,540 --> 00:23:21,280
se só se preocupan
tamaños, que intuitivamente

518
00:23:21,280 --> 00:23:24,620
debe ser non-negativo ou
positivo ou 0, ben, entón,

519
00:23:24,620 --> 00:23:28,884
por que está perdendo 2 millóns
Os valores posibles para números negativos

520
00:23:28,884 --> 00:23:30,300
se vostede non vai usalos?

521
00:23:30,300 --> 00:23:35,350
Así dicindo non asinado, agora meu int poida
estar entre 0 e preto de 4 millóns.

522
00:23:35,350 --> 00:23:39,280
>> Entón aquí é só un int C por razóns
Non imos entrar só agora como

523
00:23:39,280 --> 00:23:42,280
para por iso que é un int no canto
dun char, pero aquí é

524
00:23:42,280 --> 00:23:44,630
a esencia do que está a suceder
, E algúns de vostedes

525
00:23:44,630 --> 00:23:48,340
pode ser utilizando, por exemplo, a
función fgetc mesmo en PSet catro

526
00:23:48,340 --> 00:23:51,580
ou despois desa data, imos velo
novo no conxunto de problemas cinco,

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

528
00:23:55,410 --> 00:23:57,940
é unha función que
recibe un personaxe e así,

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

530
00:24:00,690 --> 00:24:03,110
é que non estamos a usar
scanf do mesmo xeito.

531
00:24:03,110 --> 00:24:07,550
Estamos só rastreando paso a paso
sobre todo o que o usuario introduciu en,

532
00:24:07,550 --> 00:24:10,970
porque sempre podemos asignar unha
char, e para que poidamos sempre con seguridade

533
00:24:10,970 --> 00:24:15,599
ollar para un carácter de cada vez, e
a maxia comeza a ocorrer aquí.

534
00:24:15,599 --> 00:24:17,890
Eu estou indo a rolar para abaixo para
medio desta función

535
00:24:17,890 --> 00:24:20,360
só para introducir brevemente esta función.

536
00:24:20,360 --> 00:24:22,670
Moi como hai un
función malloc, hai

537
00:24:22,670 --> 00:24:27,740
unha función realloc onde realloc
permite recolocar un bloque de memoria

538
00:24:27,740 --> 00:24:29,570
e facela máis ou menos.

539
00:24:29,570 --> 00:24:33,060
Entón, longa historia curta e con
unha onda de man para hoxe,

540
00:24:33,060 --> 00:24:35,620
sabe que o que GetString
está facendo é que é unha especie

541
00:24:35,620 --> 00:24:39,720
Magic de crecemento ou
encollendo o tapón como o usuario

542
00:24:39,720 --> 00:24:41,440
tipo na súa cadea.

543
00:24:41,440 --> 00:24:43,962
>> Polo tanto, se o usuario escribe un
corda curta, este código

544
00:24:43,962 --> 00:24:45,920
única aloca suficiente
memoria para se axustar á cadea.

545
00:24:45,920 --> 00:24:48,086
Se o usuario mantén dixitación
como eu fixen iso de novo e de novo

546
00:24:48,086 --> 00:24:50,330
e de novo, así, se o
tapón do inicialmente esta gran

547
00:24:50,330 --> 00:24:53,310
eo programa entende, a
agarde un minuto, eu estou fóra do espazo,

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

549
00:24:55,410 --> 00:24:59,110
e, a continuación, o dobre do tamaño do buffer
eo código que fai a duplicación,

550
00:24:59,110 --> 00:25:03,170
se miramos para el aquí, é
só iso intelixente one-Liner.

551
00:25:03,170 --> 00:25:06,830
Pode non ter visto esta sintaxe
antes, pero se di que é igual a estrela,

552
00:25:06,830 --> 00:25:10,470
esta é a mesma cousa que
dicindo veces capacidade para 2.

553
00:25:10,470 --> 00:25:13,390
El simplemente continúa dobrando
a capacidade do tapón

554
00:25:13,390 --> 00:25:17,480
e, a continuación, dicindo realloc para dar
Se que moito máis memoria.

555
00:25:17,480 --> 00:25:19,720
>> Agora, como un aparte, hai
son outras funcións aquí

556
00:25:19,720 --> 00:25:23,680
que non imos ollar para calquera detalle
ademais de mostrar en GetInt,

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

558
00:25:26,150 --> 00:25:28,192
Nós consideramos que non é
null, o que, recall,

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

560
00:25:30,400 --> 00:25:31,233
Estamos con falta de memoria.

561
00:25:31,233 --> 00:25:32,310
Mellor comprobar a iso.

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

563
00:25:33,710 --> 00:25:37,850
Pero eu vou retrasar para as observacións canto á
por que e, a continuación, usar este primo de scanf

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

565
00:25:42,100 --> 00:25:45,310
permite que dea un ollo á liña que
o usuario introduciu no e deixalo

566
00:25:45,310 --> 00:25:49,610
analiza-lo e, esencialmente, o que eu son
facendo aquí é que eu estou dicindo a sscanf,

567
00:25:49,610 --> 00:25:54,440
analizar todo o que o usuario ten
escritas e asegurarse de% i,

568
00:25:54,440 --> 00:25:59,250
existe un enteiro nel, e non imos
entrar hoxe exactamente porque hai tamén

569
00:25:59,250 --> 00:26:03,760
un% c aquí, pero que, en poucas palabras permite
nós para detectar se o usuario introduciu

570
00:26:03,760 --> 00:26:06,050
en algo falso despois do número.

571
00:26:06,050 --> 00:26:11,766
Entón a razón que GetInt e GetString
dicirlle para repetir, repetir, repetir

572
00:26:11,766 --> 00:26:13,640
é por mor de todo
que o código que escribimos,

573
00:26:13,640 --> 00:26:17,900
é unha especie de ollar para a entrada do usuario
en asegurarse de que é totalmente numérico

574
00:26:17,900 --> 00:26:21,700
ou é un flotante real
valor de punto ou semellante,

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

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

577
00:26:25,060 --> 00:26:25,710
Aceptar.

578
00:26:25,710 --> 00:26:27,592
Isto foi un bocado
pero o punto aquí é

579
00:26:27,592 --> 00:26:29,550
que a razón que tivemos
as rodas de formación sobre

580
00:26:29,550 --> 00:26:32,880
é porque no nivel máis baixo,
Hai só tantas cousas que

581
00:26:32,880 --> 00:26:35,674
pode dar mal que queriamos
para xestionar cautelarmente

582
00:26:35,674 --> 00:26:38,090
isto seguramente no
primeiras semanas de clase,

583
00:26:38,090 --> 00:26:42,230
pero agora con PSet catro e cinco e PSet
ademais de vai ver que é máis ata

584
00:26:42,230 --> 00:26:45,570
ti, pero tamén é máis capaz
de resolver este tipo de problemas

585
00:26:45,570 --> 00:26:47,180
Se.

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

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

588
00:26:52,630 --> 00:26:55,130
>> Audiencia: Por que ía dobrar
a capacidade do tapón

589
00:26:55,130 --> 00:26:57,630
no canto de só aumentar
polo que a cantidade exacta?

590
00:26:57,630 --> 00:26:58,100
>> DAVID Malan: Boa pregunta.

591
00:26:58,100 --> 00:27:00,474
Por que iríamos duplicar a capacidade
do tapón en oposición

592
00:27:00,474 --> 00:27:02,800
só para aumenta-la
por algún valor constante?

593
00:27:02,800 --> 00:27:03,900
Foi unha decisión deseño.

594
00:27:03,900 --> 00:27:08,590
Nós só decidimos que xa tende a
ser un pouco caro, time-wise preguntar

595
00:27:08,590 --> 00:27:10,440
o sistema operativo
para a memoria, non o fixemos

596
00:27:10,440 --> 00:27:13,210
quere acabar metendo
unha situación para grandes cadeas

597
00:27:13,210 --> 00:27:14,960
que estabamos pedindo
o sistema operativo novo e de novo

598
00:27:14,960 --> 00:27:17,500
e de novo e de novo en
sucesión rápida para a memoria.

599
00:27:17,500 --> 00:27:20,387
Entón, nós só decidiu, un pouco
arbitrariamente, pero esperamos razoablemente,

600
00:27:20,387 --> 00:27:22,720
que, xa sabe o que imos
tentar chegar á fronte de nós mesmos

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

602
00:27:25,520 --> 00:27:29,010
temos que chamar malloc ou
realloc, pero un total de xuízo

603
00:27:29,010 --> 00:27:31,820
chamar a ausencia de saber
o que os usuarios poden querer escribir.

604
00:27:31,820 --> 00:27:33,600
Ambas as formas poden ser discutible.

605
00:27:33,600 --> 00:27:35,430
Indiscutibelmente boa.

606
00:27:35,430 --> 00:27:39,240
>> Entón imos dar un ollo a un par
doutros efectos secundarios de memoria,

607
00:27:39,240 --> 00:27:41,610
cousas que poden dar mal
e ferramentas que 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 todo de ti, aínda que
check50 non lle contou como moito,

610
00:27:47,800 --> 00:27:50,050
teñen escrito de buggy
xa que un código de semana,

611
00:27:50,050 --> 00:27:53,630
mesmo se todas as probas son check50
pasou, e aínda que vostede eo seu TF

612
00:27:53,630 --> 00:27:56,010
son super seguros de que
seu código funciona como previsto.

613
00:27:56,010 --> 00:27:59,190
O seu código foi buggy ou
fallo na que todos vós,

614
00:27:59,190 --> 00:28:02,540
en usar a biblioteca CS50,
foron fuga de memoria.

615
00:28:02,540 --> 00:28:06,040
Foi pedir ao sistema operativo
para memoria na maioría dos programas

616
00:28:06,040 --> 00:28:08,850
escribiu, pero
nunca realmente deu de volta.

617
00:28:08,850 --> 00:28:12,110
Chamou GetString
e GetInt e GetFloat,

618
00:28:12,110 --> 00:28:15,270
pero con GetString, ten
nunca chamou unGetString ou de-

619
00:28:15,270 --> 00:28:19,890
Volver corda ou similar, pero nós vimos
GetString que fai reservar memoria

620
00:28:19,890 --> 00:28:22,810
por medio de malloc ou este
realloc función, que non é máis que

621
00:28:22,810 --> 00:28:25,670
moi semellante en espírito,
e aínda, fomos

622
00:28:25,670 --> 00:28:28,629
pedindo o sistema operativo para
memoria e memoria de novo e de novo

623
00:28:28,629 --> 00:28:29,670
pero nunca dándolle de volta.

624
00:28:29,670 --> 00:28:33,550
>> Agora, como un aparte, verifícase que
cando un programa remata, toda a memoria

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

626
00:28:34,870 --> 00:28:36,150
Polo tanto, non foi un gran negocio.

627
00:28:36,150 --> 00:28:38,590
Non vai romper o
IDE ou retardar as cousas,

628
00:28:38,590 --> 00:28:40,670
Pero cando os programas fan
xeralmente baleirar memoria

629
00:28:40,670 --> 00:28:42,170
e eles están executando por un longo tempo.

630
00:28:42,170 --> 00:28:45,640
Se xa viu a pouco estúpido
bola de praia en Mac OS ou a ampulheta

631
00:28:45,640 --> 00:28:51,160
en Windows, onde é unha especie de
abrandar ou pensar ou pensar

632
00:28:51,160 --> 00:28:53,770
ou só realmente comeza
para retardar a un rastreando,

633
00:28:53,770 --> 00:28:56,960
moi posiblemente podería ser
o resultado dun escape de memoria.

634
00:28:56,960 --> 00:28:59,970
Os programadores que escribiron
o software que está a usar

635
00:28:59,970 --> 00:29:03,570
pedir ao sistema operativo para a memoria
cada poucos minutos, a cada hora.

636
00:29:03,570 --> 00:29:05,570
Pero se está executando o
software, aínda que sexa

637
00:29:05,570 --> 00:29:08,680
minimizado no seu ordenador
por horas ou días a fío,

638
00:29:08,680 --> 00:29:11,980
pode estar pedindo máis e máis
memoria e nunca realmente usalo

639
00:29:11,980 --> 00:29:15,180
e para que o seu código pode ser, ou
programas poden ser baleirado de memoria,

640
00:29:15,180 --> 00:29:18,350
e se comezar a baleirar memoria,
hai menos memoria para outros programas,

641
00:29:18,350 --> 00:29:21,220
eo efecto é a
retardar todo para abaixo.

642
00:29:21,220 --> 00:29:23,600
>> Agora, este é de lonxe un dos
os programas máis atroces

643
00:29:23,600 --> 00:29:26,350
terá oportunidades
para realizar en CS50, na medida

644
00:29:26,350 --> 00:29:31,650
como a súa produción é aínda máis esotérica que
clang de ou facer ou o todo do comando

645
00:29:31,650 --> 00:29:35,930
programas de liña que xa executados antes, pero
por sorte, incorporado na súa saída

646
00:29:35,930 --> 00:29:39,810
é algúns consellos útiles que super-
ha ser útil tanto para PSet catro

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

648
00:29:41,510 --> 00:29:44,250
Entón valgrind é unha ferramenta
que se pode usar para buscar

649
00:29:44,250 --> 00:29:46,930
para derrames de memoria no seu programa.

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

651
00:29:48,570 --> 00:29:51,420
Corre valgrind e, a continuación, mesmo
pero é un pouco detallado,

652
00:29:51,420 --> 00:29:54,440
trazo verificación de baleirado trazo
é igual a plena e logo dot

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

654
00:29:56,320 --> 00:30:00,010
Entón valgrind, entón, facer o seu programa
e, ao final do seu programa

655
00:30:00,010 --> 00:30:02,240
execución antes de que sae e
dálle outro pedido,

656
00:30:02,240 --> 00:30:04,980
que vai analizar o seu
programa mentres está a executarse

657
00:30:04,980 --> 00:30:07,740
e dicirlle que baleirar
calquera memoria e mellor aínda,

658
00:30:07,740 --> 00:30:10,610
se tocar memoria que
non pertence a vostede?

659
00:30:10,610 --> 00:30:13,700
Non pode incorporarse todo, pero é
moi bo en incorporarse máis cousas.

660
00:30:13,700 --> 00:30:19,700
>> Entón aquí está un exemplo do meu ter prazo
este programa, tendo run valgrind,

661
00:30:19,700 --> 00:30:21,470
nun programa chamado
memoria, e eu vou

662
00:30:21,470 --> 00:30:24,730
para destacar as liñas que son
en definitiva, de interese para nós.

663
00:30:24,730 --> 00:30:27,690
Polo tanto, hai aínda máis distraccións
que teña eliminado do slide.

664
00:30:27,690 --> 00:30:30,930
Pero imos ver o que este
programa é capaz de nos dicir.

665
00:30:30,930 --> 00:30:34,800
É capaz de nos dicir cousas
como gravación válido de tamaño 4.

666
00:30:34,800 --> 00:30:38,020
Noutras palabras, se tocar en memoria,
especialmente 4 bytes de memoria

667
00:30:38,020 --> 00:30:40,350
que non debe ter,
valgrind te podo dicir iso.

668
00:30:40,350 --> 00:30:41,660
Write válido de tamaño 4.

669
00:30:41,660 --> 00:30:43,640
Vostede tocou catro bytes
que non debe ter.

670
00:30:43,640 --> 00:30:44,840
Onde é que fai iso?

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

672
00:30:45,900 --> 00:30:50,000
Dot liña memoria c 21 é onde
asneira e é por iso que é útil.

673
00:30:50,000 --> 00:30:53,410
Moi parecido ao GDB, pode axudar
sinala-lo ao erro real.

674
00:30:53,410 --> 00:30:57,170
>> Agora, este é un pouco máis
detallado, se non confuso.

675
00:30:57,170 --> 00:31:01,307
40 bytes en bloques de 1 son, en definitiva,
perdido no rexistro de perda 1 de 1.

676
00:31:01,307 --> 00:31:02,140
Que significa iso?

677
00:31:02,140 --> 00:31:05,920
Ben, iso significa só que pediu
40 bytes e nunca deulle de volta.

678
00:31:05,920 --> 00:31:08,930
Vostede chamada malloc ou chamada
GetString eo sistema operativo

679
00:31:08,930 --> 00:31:12,450
deulle 40 bytes, pero nunca
liberadas ou que a memoria liberada,

680
00:31:12,450 --> 00:31:15,400
e para ser xusto, nunca amosar
como para darlle a volta a memoria.

681
00:31:15,400 --> 00:31:17,910
Acontece aí é un super-
función simple chamado libre.

682
00:31:17,910 --> 00:31:21,170
Recibe un argumento, a cousa
quere liberar ou dar para atrás,

683
00:31:21,170 --> 00:31:23,430
40 bytes, pero, ao parecer,
neste programa

684
00:31:23,430 --> 00:31:27,300
foron perdidos na liña
20 de memoria punto c.

685
00:31:27,300 --> 00:31:28,650
>> Entón imos ver este programa.

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

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

688
00:31:33,980 --> 00:31:34,920
Entón, imos dar un ollo.

689
00:31:34,920 --> 00:31:39,920
Aquí é principais e principais, observación, chamadas
unha función chamada F e logo retorna.

690
00:31:39,920 --> 00:31:41,550
Entón, non todo o que interesante.

691
00:31:41,550 --> 00:31:42,664
O que fai f facer?

692
00:31:42,664 --> 00:31:44,330
Repare que eu non me incomoda con un prototipo.

693
00:31:44,330 --> 00:31:46,520
Eu quería manter o código
o mínimo posible.

694
00:31:46,520 --> 00:31:49,530
Entón eu coloque f enriba principal e
iso é bo, 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ón f non retorna nada e fai
non levar nada, pero o fai.

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

698
00:31:59,620 --> 00:32:02,682
un punteiro chamado x que está pasando
para almacenar o enderezo dun int.

699
00:32:02,682 --> 00:32:03,890
Entón, iso é o lado esquerdo.

700
00:32:03,890 --> 00:32:07,230
En inglés, o que é o
lado dereito facendo?

701
00:32:07,230 --> 00:32:09,770
Anyone?

702
00:32:09,770 --> 00:32:13,665
¿Que é esta facendo por nós?

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

704
00:32:14,651 --> 00:32:16,623
>> Audiencia: [inaudível]
veces o tamaño dun int

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

706
00:32:19,175 --> 00:32:20,800
DAVID Malan: Boa e déixeme resumir.

707
00:32:20,800 --> 00:32:25,480
Entón reservar espacio suficiente para 10 enteiros
ou 10, o que é do tamaño dun int,

708
00:32:25,480 --> 00:32:29,340
é catro bytes, polo que 10 veces 4 é
40, de xeito que o lado dereito que eu teño

709
00:32:29,340 --> 00:32:33,930
resaltado é darme 40 bytes e
almacenar o enderezo do primeiro byte

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

711
00:32:34,940 --> 00:32:38,380
E agora, por fin, e é aquí que
este programa é buggy, o que é

712
00:32:38,380 --> 00:32:41,540
mal con liña 21 en base a que a lóxica?

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

714
00:32:45,197 --> 00:32:46,280
O que hai de malo con liña 21?

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

716
00:32:46,780 --> 00:32:49,550
Audiencia: Non pode
índice en x [inaudível].

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

718
00:32:50,300 --> 00:32:52,270
Non debería índice en x como esta.

719
00:32:52,270 --> 00:32:53,850
Entón sintaticamente, iso é OK.

720
00:32:53,850 --> 00:32:56,990
O que é bo é, moi parecido contigo
pode tratar o nome dunha matriz

721
00:32:56,990 --> 00:33:01,080
como se fose un punteiro, semellante
pode tratar un punteiro como se fose

722
00:33:01,080 --> 00:33:06,425
unha matriz, e para que eu poida sintaticamente
x soporte dicir algo, x soporte i,

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

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

725
00:33:09,096 --> 00:33:10,910
>> Audiencia: ¿Por que non é no interior.

726
00:33:10,910 --> 00:33:12,390
>> DAVID Malan: non
dentro dese anaco de memoria.

727
00:33:12,390 --> 00:33:15,306
Cal é o maior valor que eu debería
estar poñendo neses corchetes?

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

729
00:33:16,870 --> 00:33:18,160
Debido a indexación cero.

730
00:33:18,160 --> 00:33:20,190
Entón, de 0 a 9 sería óptimo.

731
00:33:20,190 --> 00:33:23,960
Soporte 10 non é boa e
pero, lembre-se, porén, cada vez

732
00:33:23,960 --> 00:33:27,017
Paréceme tentar facer CS50 IDE
accidente, escribindo valores falsos,

733
00:33:27,017 --> 00:33:29,100
non sempre cooperar,
e, de feito, moitas veces

734
00:33:29,100 --> 00:33:31,460
ter sorte de ser o
sistema operativo non

735
00:33:31,460 --> 00:33:35,467
entender que nunca tan pouco
pasar algún anaco de memoria,

736
00:33:35,467 --> 00:33:38,300
porque quedou dentro tecnicamente
seu segmento, pero máis sobre iso

737
00:33:38,300 --> 00:33:40,940
nunha clase de sistemas operativos,
e así por algo así

738
00:33:40,940 --> 00:33:43,000
podería facilmente pasar desapercibido.

739
00:33:43,000 --> 00:33:48,120
O seu programa non vai fallar
consistente, pero quizais xa en moito tempo.

740
00:33:48,120 --> 00:33:50,610
>> E entón imos tentar valgrind
sobre iso, e é aquí

741
00:33:50,610 --> 00:33:52,870
onde imos estar resaltado
por saída momentaneamente.

742
00:33:52,870 --> 00:34:00,810
Entón, faga verificación de baleirado de memoria valgrind
é igual a memoria barra punto cheo.

743
00:34:00,810 --> 00:34:03,040
E aquí está o porqué eu prometer
poderían sobrecargar.

744
00:34:03,040 --> 00:34:05,700
Aquí está o que valgrind, aquí está o que
programador, algúns anos-

745
00:34:05,700 --> 00:34:08,469
decidiu que sería unha boa idea
para a saída a aparencia.

746
00:34:08,469 --> 00:34:09,750
Entón, imos dar sentido a iso.

747
00:34:09,750 --> 00:34:13,120
Entón, todo o camiño na da esquerda
banda sen unha boa razón

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

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

750
00:34:18,030 --> 00:34:19,738
Nós excluído que desde
o slide, pero non

751
00:34:19,738 --> 00:34:22,190
é algunha información útil aquí.

752
00:34:22,190 --> 00:34:24,684
>> Imos rodar ata o cumio.

753
00:34:24,684 --> 00:34:25,600
Aquí é onde comezamos.

754
00:34:25,600 --> 00:34:27,040
Polo tanto, non é tanto así de saída.

755
00:34:27,040 --> 00:34:30,429
Aquí está o que write válido
4 de tamaño na liña 21.

756
00:34:30,429 --> 00:34:31,760
Ben, o que era liña 21?

757
00:34:31,760 --> 00:34:34,500
Liña 21 foi exactamente
este e ten sentido

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

759
00:34:37,290 --> 00:34:40,389
intentando poñer este número enteiro,
o que podería ser calquera cousa,

760
00:34:40,389 --> 00:34:42,370
iso só pasa de ser
cero, pero eu estou tentando

761
00:34:42,370 --> 00:34:44,940
para poñelas nun lugar
que non pertence a min.

762
00:34:44,940 --> 00:34:50,900
Ademais, aquí abaixo, 40 bytes nun
bloques son definitivamente perdidos en ficha 1.

763
00:34:50,900 --> 00:34:56,500
Porque cando eu chamar malloc
aquí, eu nunca realmente liberar a memoria.

764
00:34:56,500 --> 00:34:58,140
>> Entón, como podemos solucionar isto?

765
00:34:58,140 --> 00:35:02,970
Deixe-me ir adiante e ser un pouco máis seguro
e facer 9 alí e me deixe aquí libre x.

766
00:35:02,970 --> 00:35:04,820
Esta é a nova función para hoxe.

767
00:35:04,820 --> 00:35:11,520
Se eu agora realizar novamente facer corte de punto de memoria,
imos realizar valgrind nel de novo,

768
00:35:11,520 --> 00:35:14,990
maximizar miña fiestra e prema Intro.

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

770
00:35:16,900 --> 00:35:19,590
Eles enterran a boa nova
en todo este proceso de saída.

771
00:35:19,590 --> 00:35:20,810
Todos os bloques heap eran libres.

772
00:35:20,810 --> 00:35:23,604
Imos volver ao que o heap
é, pero non hai fugas son posibles.

773
00:35:23,604 --> 00:35:25,520
Polo tanto, este é só un
ferramenta para o seu kit de ferramentas

774
00:35:25,520 --> 00:35:30,220
co cal pode comezar a
agora atopar erros como ese.

775
00:35:30,220 --> 00:35:34,532
>> Pero imos ver o que
máis pode dar mal aquí.

776
00:35:34,532 --> 00:35:38,890
Transición Imos agora
realmente resolver un problema.

777
00:35:38,890 --> 00:35:42,440
Como un aparte, se iso vai aliviar un
pouco de confusión ou tensión,

778
00:35:42,440 --> 00:35:43,430
isto agora é divertido.

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

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

781
00:35:46,900 --> 00:35:49,040
Iso é moi bo.

782
00:35:49,040 --> 00:35:50,890
Porque punteiros son
enderezos e enderezos

783
00:35:50,890 --> 00:35:53,098
son, en xeral, por convención
escrito con hexadecimal.

784
00:35:53,098 --> 00:35:54,650
Ha, ha, iso é divertido agora.

785
00:35:54,650 --> 00:35:58,390
En calquera caso, así que imos agora
realmente resolver un problema.

786
00:35:58,390 --> 00:36:00,840
Isto foi super,
super baixo-nivel, ata agora,

787
00:36:00,840 --> 00:36:03,950
e podemos realmente facer útil
cousas con estes detalles de baixo nivel.

788
00:36:03,950 --> 00:36:06,710
>> Entón, nós introducimos algunhas semanas
atrás, a noción dunha matriz.

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

790
00:36:09,177 --> 00:36:11,760
porque se quixésemos escribir
programa con varios alumnos

791
00:36:11,760 --> 00:36:15,270
ou varios nomes e casas e
dormitorios e facultades e todo iso,

792
00:36:15,270 --> 00:36:19,430
poderiamos almacenar todo máis
limpa dentro dunha matriz.

793
00:36:19,430 --> 00:36:23,039
Pero propoñer unha desvantaxe
dunha matriz, ata agora.

794
00:36:23,039 --> 00:36:26,080
Mesmo se non sufrín it yourself
nun programa, só instintivamente,

795
00:36:26,080 --> 00:36:30,870
o que é algo malo
sobre unha matriz, quizais?

796
00:36:30,870 --> 00:36:32,337
Escoito uns murmurios.

797
00:36:32,337 --> 00:36:34,170
Audiencia: É difícil
para cambiar o tamaño.

798
00:36:34,170 --> 00:36:36,128
DAVID Malan: É difícil
para cambiar o tamaño.

799
00:36:36,128 --> 00:36:38,660
Non pode cambiar o tamaño
dunha matriz, de feito, por si só

800
00:36:38,660 --> 00:36:43,040
en C. Podes reservar outro array,
mover todo, dende o antigo

801
00:36:43,040 --> 00:36:45,380
ao novo, e agora
ter un espazo extra,

802
00:36:45,380 --> 00:36:47,469
pero non é como un
linguaxe como Java ou Python

803
00:36:47,469 --> 00:36:49,760
ou calquera número de outros
linguas que algúns de vós

804
00:36:49,760 --> 00:36:52,070
pode estar familiarizado onde
pode simplemente seguir engadindo cousas

805
00:36:52,070 --> 00:36:53,930
saciedade despois dunha matriz.

806
00:36:53,930 --> 00:36:57,880
Cando ten unha serie de
tamaño 6, que é o seu tamaño,

807
00:36:57,880 --> 00:37:01,970
e tan parecido a idea anterior
tendo un tapón dun determinado tamaño,

808
00:37:01,970 --> 00:37:05,940
tes que adiviñar fóra da porta
cal é o tamaño que queres que sexa?

809
00:37:05,940 --> 00:37:07,880
Se adiviñar moi grande,
está perdendo espazo.

810
00:37:07,880 --> 00:37:10,950
Se adiviñar moi pequeno,
Non se pode gardar os datos, polo menos,

811
00:37:10,950 --> 00:37:12,940
sen moito traballo.

812
00:37:12,940 --> 00:37:18,180
>> Entón, hoxe, grazas aos punteiros, podemos
comezar a coser o noso propio costume

813
00:37:18,180 --> 00:37:20,989
estruturas de datos, e en
feito, aquí é algo

814
00:37:20,989 --> 00:37:23,030
que parece un pouco máis
enigmática, a primeira vista,

815
00:37:23,030 --> 00:37:26,440
pero iso é o que nós imos chamar un conectado
lista, eo seu tipo de nome resume

816
00:37:26,440 --> 00:37:26,940
lo.

817
00:37:26,940 --> 00:37:29,550
É unha lista de números, ou en
Neste caso, unha lista de números,

818
00:37:29,550 --> 00:37:33,480
pero pode ser unha lista de todo, pero
ela ligados entre si a través de frechas,

819
00:37:33,480 --> 00:37:36,380
e só dar un palpite
con cal técnica

820
00:37:36,380 --> 00:37:38,310
imos ser capaces
para unir,

821
00:37:38,310 --> 00:37:42,540
tipo de como pipoca cun fío,
unha ligada listas rectángulos aquí?

822
00:37:42,540 --> 00:37:43,936
Os seus números?

823
00:37:43,936 --> 00:37:45,560
Qué é o recurso de linguaxe subxacente?

824
00:37:45,560 --> 00:37:46,350
>> Audiencia: Un punteiro.

825
00:37:46,350 --> 00:37:47,308
>> DAVID Malan: Un punteiro.

826
00:37:47,308 --> 00:37:51,700
Entón cada un destes frechas representa aquí
un punteiro ou só unha dirección.

827
00:37:51,700 --> 00:37:54,590
Polo tanto, noutras palabras, se eu queira
para almacenar unha lista de números,

828
00:37:54,590 --> 00:37:59,040
Non podo simplemente almacena-lo se eu queira
a capacidade para aumentar e diminuír

829
00:37:59,040 --> 00:38:00,990
miña estrutura de datos nunha matriz.

830
00:38:00,990 --> 00:38:03,000
Entón eu preciso ter un pouco
máis sofisticación,

831
00:38:03,000 --> 00:38:05,720
de ter en conta que esta
tipo de imaxe suxire

832
00:38:05,720 --> 00:38:08,650
que, se só ten pequenos temas
conectar todo en conxunto,

833
00:38:08,650 --> 00:38:13,100
probablemente non é tan difícil de facer espazo
entre dous destes rectángulos

834
00:38:13,100 --> 00:38:16,750
ou dous destes nós, como imos comezar
chamando-os, coloque un novo nodo,

835
00:38:16,750 --> 00:38:19,547
e despois con unha nova liña, só
abandonar os tres nós xuntos,

836
00:38:19,547 --> 00:38:22,880
a primeira, a última, e por un
que acaba de introducir no medio.

837
00:38:22,880 --> 00:38:26,000
>> E, de feito unha lista ligada,
ao contrario dunha matriz, é dinámico.

838
00:38:26,000 --> 00:38:27,840
Ela pode crecer e pode
encoller e non fai

839
00:38:27,840 --> 00:38:32,434
Ten que saber ou importarlle con antelación como
cantidade de datos que vai estar almacenando,

840
00:38:32,434 --> 00:38:35,600
pero resulta que temos que ser un pouco
coidadoso sobre como aplicar iso.

841
00:38:35,600 --> 00:38:39,070
Entón, primeiro imos considerar como imos implementar
un destes pequenos rectángulos.

842
00:38:39,070 --> 00:38:40,690
É doado de aplicar un int.

843
00:38:40,690 --> 00:38:44,000
Acaba de dicir int n e, a continuación,
obtén 4 bytes para un int,

844
00:38:44,000 --> 00:38:49,089
pero como fago para obter un int, chamalo de n,
e, a continuación, un punteiro, imos chamalo axiña.

845
00:38:49,089 --> 00:38:50,880
Poderiamos chamar estas
cousas algo que queremos

846
00:38:50,880 --> 00:38:53,590
pero eu teño unha estrutura de datos personalizado.

847
00:38:53,590 --> 00:38:54,257
Si?

848
00:38:54,257 --> 00:38:57,020
>> Audiencia: Ampersand [inaudível].

849
00:38:57,020 --> 00:39:00,940
>> DAVID Malan: Entón e comercial, imos utilizar para
obter o enderezo dun nodo potencialmente.

850
00:39:00,940 --> 00:39:02,740
Pero precisamos doutro
O recurso de C en orde

851
00:39:02,740 --> 00:39:06,700
para me dar a capacidade de crear
este rectángulo costume, este costume

852
00:39:06,700 --> 00:39:08,919
variable se, na memoria.

853
00:39:08,919 --> 00:39:09,710
Audiencia: Unha struct.

854
00:39:09,710 --> 00:39:10,626
DAVID Malan: Unha struct.

855
00:39:10,626 --> 00:39:14,310
Teña en conta que a última semana, introducimos
struct, esta palabra chave relativamente simple

856
00:39:14,310 --> 00:39:16,254
que nos permite facer cousas como esta.

857
00:39:16,254 --> 00:39:18,420
C non veu con un conxunto de datos
estrutura chamada estudante.

858
00:39:18,420 --> 00:39:22,190
Ven con int e boia e carbón animal e
tal, pero non vén co alumno,

859
00:39:22,190 --> 00:39:26,750
pero podemos crear un tipo de datos do alumno,
unha estrutura estudante, con esta sintaxe

860
00:39:26,750 --> 00:39:27,250
aquí.

861
00:39:27,250 --> 00:39:28,350
E vai ver iso de novo e de novo.

862
00:39:28,350 --> 00:39:30,426
Non te preocupes
Recordar as palabras clave,

863
00:39:30,426 --> 00:39:33,300
pero a palabra clave que é importante é
só o feito de que nós dixemos struct

864
00:39:33,300 --> 00:39:37,590
e, a continuación, nós o chamamos estudante e no interior
do alumno era un nome e unha casa

865
00:39:37,590 --> 00:39:39,390
ou un dormitorio ou similares.

866
00:39:39,390 --> 00:39:41,980
>> E agora, hoxe, imos propoñer iso.

867
00:39:41,980 --> 00:39:45,240
Eu engade algunhas palabras, pero se eu queira
para aplicar este rectángulo que é

868
00:39:45,240 --> 00:39:48,440
ten tanto un int e un
punteiro, vostede sabe, eu son

869
00:39:48,440 --> 00:39:51,540
vai declarar unha estrutura chamada nó.

870
00:39:51,540 --> 00:39:55,630
Eu tamén son, dentro del, vai dicir
que un nó, rectángulo, ten un int

871
00:39:55,630 --> 00:39:59,730
e imos chamalo e n
ten un punteiro próximo.

872
00:39:59,730 --> 00:40:02,540
E iso é un pouco detallado,
pero se pensar sobre iso,

873
00:40:02,540 --> 00:40:07,300
as frechas que estaban na imaxe
un momento atrás son de que tipo de datos?

874
00:40:07,300 --> 00:40:12,330
Cando cada un destes frechas apuntando está
a que tipo de estrutura de datos?

875
00:40:12,330 --> 00:40:14,332
Non é só que apunta a un int per se.

876
00:40:14,332 --> 00:40:16,165
Está apuntando para o
cousa toda rectangular

877
00:40:16,165 --> 00:40:18,720
e que cousa rectangular,
nós dixemos, chámase nó.

878
00:40:18,720 --> 00:40:21,720
E entón nós medio que ten que
recursivamente definir esta tales

879
00:40:21,720 --> 00:40:26,270
que un nó, digamos,
contén un int chamado n

880
00:40:26,270 --> 00:40:31,070
e un punteiro chamado seguinte e no
tipo de estrutura de datos para o que

881
00:40:31,070 --> 00:40:35,770
que os puntos de punteiro é, ao parecer,
será nó struct.

882
00:40:35,770 --> 00:40:41,550
>> Polo tanto, este é irritante verboso
e só para ser pedante,

883
00:40:41,550 --> 00:40:44,100
a razón pola que nós non podemos
só dicir isto, que, a verdade,

884
00:40:44,100 --> 00:40:46,860
parece moito máis lexible,
é porque recorda que C ler

885
00:40:46,860 --> 00:40:48,710
as cousas de arriba abaixo, de esquerda a dereita.

886
00:40:48,710 --> 00:40:54,120
Non é ata chegar a punto e coma
que a palabra chave nó realmente existe.

887
00:40:54,120 --> 00:40:57,980
Polo tanto, se queremos ter ese tipo de
referencia cíclico dentro dos datos

888
00:40:57,980 --> 00:41:02,120
estrutura, temos que facelo, onde
dicimos nó struct na parte superior, que

889
00:41:02,120 --> 00:41:06,770
ofrécenos unha máis forma de describir este
cousa, entón dentro dicimos nó struct,

890
00:41:06,770 --> 00:41:09,560
e despois na última liña
podemos dicir, todo ben, C, a propósito,

891
00:41:09,560 --> 00:41:12,060
pode conectar a todo este maldito
cousa que un nó e deixar

892
00:41:12,060 --> 00:41:14,360
usando a palabra chave struct completamente.

893
00:41:14,360 --> 00:41:18,030
Polo tanto, esta é só unha especie de sintáctica
truco que finalmente nos permite crear

894
00:41:18,030 --> 00:41:21,370
algo que se parece exactamente con iso.

895
00:41:21,370 --> 00:41:25,010
>> Entón, se nós agora podemos asumir
aplicar esa cousa en C,

896
00:41:25,010 --> 00:41:28,040
como é que nós, en realidade,
iniciar atravesando este?

897
00:41:28,040 --> 00:41:32,360
Ben, en realidade, todo o que temos que facer é
iteración de esquerda a dereita e só

898
00:41:32,360 --> 00:41:35,960
tipo de introducir os nós ou eliminar nós
ou buscar cousas onde queremos,

899
00:41:35,960 --> 00:41:39,560
pero para facelo, imos adiante e facer
as cousas un pouco máis real, porque iso

900
00:41:39,560 --> 00:41:42,560
foi super-baixo nivel ata agora.

901
00:41:42,560 --> 00:41:45,700
Será que alguén literalmente quere ser o primeiro?

902
00:41:45,700 --> 00:41:46,200
Aceptar.

903
00:41:46,200 --> 00:41:47,092
Imos cara arriba.

904
00:41:47,092 --> 00:41:47,800
Cal é o teu 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
Encantado de coñecerte.

908
00:41:49,998 --> 00:41:50,960
Eu tamén.

909
00:41:50,960 --> 00:41:52,450
Todo ben.

910
00:41:52,450 --> 00:41:53,990
E necesitamos un número 9.

911
00:41:53,990 --> 00:41:55,240
Non é tan bo como o primeiro, quizais.

912
00:41:55,240 --> 00:41:56,430
OK, número 9.

913
00:41:56,430 --> 00:41:59,667
Un número 17, por favor.

914
00:41:59,667 --> 00:42:01,000
Déixeme volver un pouco máis lonxe.

915
00:42:01,000 --> 00:42:03,980
Number 22, por favor, e
e canto máis atrás

916
00:42:03,980 --> 00:42:06,344
se podo ver ningunha man
con toda a luz ou non.

917
00:42:06,344 --> 00:42:08,010
Alguén está a ser ofreceu alí.

918
00:42:08,010 --> 00:42:08,968
Quere chegar?

919
00:42:08,968 --> 00:42:10,450
Seu antebrazo é forzado 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á a benvida para abaixo.

923
00:42:15,120 --> 00:42:18,450
Será que ninguén gusta de
forcefully-- Imos cara arriba.

924
00:42:18,450 --> 00:42:21,030
Un voluntario real.

925
00:42:21,030 --> 00:42:23,330
>> Entón, moi rapidamente, se
vostedes poderían organizar

926
00:42:23,330 --> 00:42:26,550
Se só como
os nós na pantalla.

927
00:42:26,550 --> 00:42:27,510
Grazas.

928
00:42:27,510 --> 00:42:29,234
E vai ser 26.

929
00:42:29,234 --> 00:42:30,650
Todas as introducións certas e rápidas.

930
00:42:30,650 --> 00:42:32,139
Entón, eu estou David e tamén?

931
00:42:32,139 --> 00:42:32,680
DAVID: David.

932
00:42:32,680 --> 00:42:33,721
DAVID Malan: E é?

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ón, eses son os nosos voluntarios
para hoxe e ir adiante

941
00:42:39,810 --> 00:42:43,090
e cambiar un pouco desa forma,
e só ir adiante e manter

942
00:42:43,090 --> 00:42:47,024
sostendo o seu número como é ou o seu
primeiro sinal e coa man esquerda,

943
00:42:47,024 --> 00:42:48,940
dalle só aplicar
esas frechas, só

944
00:42:48,940 --> 00:42:51,360
de xeito que a man esquerda é, literalmente,
apuntando para o que ten que apuntar

945
00:42:51,360 --> 00:42:54,610
na, e dar-se un espazo para que
vemos visualmente os brazos, en realidade,

946
00:42:54,610 --> 00:42:58,120
apuntando, e pode só apuntar
tipo de cara ao chan está ben.

947
00:42:58,120 --> 00:43:03,040
>> Polo tanto, temos aquí unha lista ligada dun,
dous, tres, catro, cinco nódulos inicialmente,

948
00:43:03,040 --> 00:43:05,860
e entender que temos este especial
punteiro no inicio quen é

949
00:43:05,860 --> 00:43:09,770
clave, xa que hai que manter o control
de toda a lista de lonxitude de algunha maneira.

950
00:43:09,770 --> 00:43:13,590
Eses faces, aínda que sexan deixadas
á dereita, volve atrás na memoria,

951
00:43:13,590 --> 00:43:15,950
de feito, poden estar en calquera lugar
na memoria do ordenador.

952
00:43:15,950 --> 00:43:18,240
Entón, estes faces poderían ser
en pé en calquera lugar na fase

953
00:43:18,240 --> 00:43:20,960
e iso é bo, sempre que son
de feito, apuntando para o outro,

954
00:43:20,960 --> 00:43:22,770
pero para manter as cousas
limpo e simple, nós imos

955
00:43:22,770 --> 00:43:25,728
só deseña-los esquerda a dereita
este, pero pode haber lagoas masivas

956
00:43:25,728 --> 00:43:26,790
entre eses nós.

957
00:43:26,790 --> 00:43:30,710
>> Agora, se eu quero realmente introducir algúns
novo valor, imos adiante e facelo.

958
00:43:30,710 --> 00:43:33,720
Temos unha oportunidade agora
para escoller un nó.

959
00:43:33,720 --> 00:43:39,820
Digamos que imos comezar con mallocing 55.

960
00:43:39,820 --> 00:43:41,320
Será que alguén podería me importa ser malloc?

961
00:43:41,320 --> 00:43:42,280
OK, imos cara arriba.

962
00:43:42,280 --> 00:43:42,992
Cal é o teu nome?

963
00:43:42,992 --> 00:43:43,700
RAINBOW: Arco da vella.

964
00:43:43,700 --> 00:43:44,050
DAVID Malan: Arco da vella?

965
00:43:44,050 --> 00:43:44,810
Todo ben.

966
00:43:44,810 --> 00:43:46,600
Malloc do arco da vella.

967
00:43:46,600 --> 00:43:47,450
Imos cara arriba.

968
00:43:47,450 --> 00:43:51,610
Polo tanto, agora temos que preguntarnos
algorithmically onde podemos poñer 55.

969
00:43:51,610 --> 00:43:53,610
Entón, todos sabemos,
obviamente, onde pode que

970
00:43:53,610 --> 00:43:55,401
pertence, se nós estamos tentando
para manter este clasificado

971
00:43:55,401 --> 00:43:58,299
e se vós poderían tomar unha
un paso atrás para que non caia

972
00:43:58,299 --> 00:43:59,590
o escenario, que sería óptimo.

973
00:43:59,590 --> 00:44:01,420
Entón, en realidade, Arco-Iris,
comezar de novo aquí comigo,

974
00:44:01,420 --> 00:44:04,200
porque, como o ordenador pode agora
só ve unha variable de cada vez.

975
00:44:04,200 --> 00:44:05,190
Así, se este é o primeiro no.

976
00:44:05,190 --> 00:44:07,160
Teña en conta que non é un nodo,
el é só un punteiro,

977
00:44:07,160 --> 00:44:10,270
e é por iso que está deseñado para ser
só o tamaño dun punteiro, non

978
00:44:10,270 --> 00:44:11,780
un deses rectángulos completos.

979
00:44:11,780 --> 00:44:16,650
Entón, nós estamos indo para comprobar en cada
iteración é de 55 a menos de 9?

980
00:44:16,650 --> 00:44:17,150
Non.

981
00:44:17,150 --> 00:44:19,060
É de 55 a menos de 17?

982
00:44:19,060 --> 00:44:19,720
Non.

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,
Iris pertence ao final.

987
00:44:25,890 --> 00:44:27,270
Entón, para ser claro, e 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ón entre Taylor
man esquerda e as mans do arco da vella aquí,

990
00:44:32,510 --> 00:44:38,324
cuxa man ten que apuntar cara a que en
Para inserir 55 nesta lista?

991
00:44:38,324 --> 00:44:39,240
O que necesitamos facer?

992
00:44:39,240 --> 00:44:39,700
Si?

993
00:44:39,700 --> 00:44:41,140
>> Audiencia: a man de Taylor
Debe apuntar esquerda.

994
00:44:41,140 --> 00:44:41,680
>> DAVID Malan: Exactamente.

995
00:44:41,680 --> 00:44:43,800
Entón, a inserción dun nodo
ao final da lista

996
00:44:43,800 --> 00:44:47,140
é moi sinxelo, porque Taylor só
ten a punto, en vez de para o chan

997
00:44:47,140 --> 00:44:49,640
ou imos chamalo nulo,
nulo é unha especie de ausencia

998
00:44:49,640 --> 00:44:51,640
dun punteiro ou unha especial
punteiro cero, está

999
00:44:51,640 --> 00:44:53,740
vai apuntar coa súa esquerda
man no arco da vella e, a continuación, Arco iris,

1000
00:44:53,740 --> 00:44:55,910
Onde debe a súa esquerda
man, probablemente, apuntar?

1001
00:44:55,910 --> 00:44:56,570
Down.

1002
00:44:56,570 --> 00:45:00,140
Non é bo se a súa man é unha especie
de apuntar fóra aquí ou calquera tipo de

1003
00:45:00,140 --> 00:45:00,640
que xeito.

1004
00:45:00,640 --> 00:45:02,407
Isto sería considerado
un valor de lixo,

1005
00:45:02,407 --> 00:45:04,240
pero se apunta
algún valor coñecido, imos

1006
00:45:04,240 --> 00:45:07,360
chamalo cero ou nulo, que é OK
porque temos un termo neste

1007
00:45:07,360 --> 00:45:09,390
e sabemos que a lista xa está completa.

1008
00:45:09,390 --> 00:45:11,550
>> Entón, o que é outra
caso relativamente simple?

1009
00:45:11,550 --> 00:45:13,125
Poderiamos malloc 5?

1010
00:45:13,125 --> 00:45:14,010
Imos cara arriba.

1011
00:45:14,010 --> 00:45:14,782
Cal é o teu 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
Todo ben.

1017
00:45:17,110 --> 00:45:19,071
Tiffany foi malloced
co valor 5.

1018
00:45:19,071 --> 00:45:19,570
Imos cara arriba.

1019
00:45:19,570 --> 00:45:23,820
Este é relativamente fácil de máis, pero
imos considerar a orde das operacións agora.

1020
00:45:23,820 --> 00:45:25,820
Foi moi fácil
con Taylor ao final.

1021
00:45:25,820 --> 00:45:30,302
Número 5 é, por suposto, menos que 9,
e por iso temos David, dispoñemos de Tiffany,

1022
00:45:30,302 --> 00:45:31,260
e cal 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
Cuxa man debe ser actualizado primeiro?

1027
00:45:36,580 --> 00:45:39,260

1028
00:45:39,260 --> 00:45:40,590
O que quere facer aquí?

1029
00:45:40,590 --> 00:45:45,244
Hai un par de formas posíbeis, mais
hai tamén unha ou máis formas erradas.

1030
00:45:45,244 --> 00:45:46,620
>> Audiencia: Comece máis á esquerda.

1031
00:45:46,620 --> 00:45:47,800
>> DAVID Malan: Comece o máis á esquerda.

1032
00:45:47,800 --> 00:45:49,008
Quen é o máis á esquerda aquí, entón?

1033
00:45:49,008 --> 00:45:49,700
Audiencia: First.

1034
00:45:49,700 --> 00:45:50,366
>> DAVID Malan: Aceptar.

1035
00:45:50,366 --> 00:45:53,781
Entón comeza co primeiro e onde
quere actualizar mans de David para ser?

1036
00:45:53,781 --> 00:45:54,780
Audiencia: Cara a 5.

1037
00:45:54,780 --> 00:45:55,446
DAVID Malan: Aceptar.

1038
00:45:55,446 --> 00:45:59,026
Entón David, punto en cinco
ou Tiffany aquí, e agora?

1039
00:45:59,026 --> 00:46:01,072
>> Audiencia: Tiffany apunta para o 9?

1040
00:46:01,072 --> 00:46:04,030
DAVID Malan: Perfecto, excepto de Binky
cabeza só unha especie de caeu, non?

1041
00:46:04,030 --> 00:46:06,820
Porque o que hai de malo con
esta imaxe, literalmente?

1042
00:46:06,820 --> 00:46:08,070
Audiencia: Nada está apuntando.

1043
00:46:08,070 --> 00:46:09,945
DAVID Malan: Nada é
apuntando a Jake agora.

1044
00:46:09,945 --> 00:46:13,360
Temos literalmente orfo 9
e 17, e temos literalmente

1045
00:46:13,360 --> 00:46:18,450
filtrou todo isto de memoria, porque,
actualizar a man de David en primeiro lugar, que é

1046
00:46:18,450 --> 00:46:21,660
ben, na medida en que é correctamente
apuntando para Tiffany agora,

1047
00:46:21,660 --> 00:46:25,410
pero se ninguén o
clarividencia de apuntar Jake,

1048
00:46:25,410 --> 00:46:27,490
entón perdemos o
totalidade desa lista.

1049
00:46:27,490 --> 00:46:28,200
Entón, imos desfacer.

1050
00:46:28,200 --> 00:46:30,950
Así, foi bo para
tropezar pero imos corrixir agora.

1051
00:46:30,950 --> 00:46:33,624
O que temos que facer primeiro no seu canto?

1052
00:46:33,624 --> 00:46:34,124
Si?

1053
00:46:34,124 --> 00:46:35,791
>> Audiencia: Tiffany debería apuntar o 9?

1054
00:46:35,791 --> 00:46:37,582
DAVID Malan: Non podo
chegar tan preto de ti.

1055
00:46:37,582 --> 00:46:38,720
Quen debería apuntar o 9?

1056
00:46:38,720 --> 00:46:39,220
>> Audiencia: Tiffany.

1057
00:46:39,220 --> 00:46:39,390
>> DAVID Malan: Todo ben.

1058
00:46:39,390 --> 00:46:41,200
Entón Tiffany que primeiro punto no 9.

1059
00:46:41,200 --> 00:46:43,550
Entón Tiffany que tomar
nun valor idéntico

1060
00:46:43,550 --> 00:46:45,820
David, que parece
redundante, por un momento,

1061
00:46:45,820 --> 00:46:48,820
pero iso é bo porque agora, segundo
paso, podemos actualizar a man de David

1062
00:46:48,820 --> 00:46:52,680
para ligar a Tiffany, e entón se
Nós medio que limpar as cousas

1063
00:46:52,680 --> 00:46:55,740
coma se este é o tipo de primavera-like,
agora que é unha inserción correcta.

1064
00:46:55,740 --> 00:46:56,700
Así excelente.

1065
00:46:56,700 --> 00:46:57,970
Polo tanto, agora estamos case alí.

1066
00:46:57,970 --> 00:47:01,075
Imos introducir un final,
valor como o valor 20.

1067
00:47:01,075 --> 00:47:03,010
Se puidésemos malloc un voluntario final?

1068
00:47:03,010 --> 00:47:04,140
Imos cara arriba.

1069
00:47:04,140 --> 00:47:06,224
Entón, este é un pouco máis complicado.

1070
00:47:06,224 --> 00:47:08,390
Pero, realmente, o código estamos
escribir, aínda que verbalmente,

1071
00:47:08,390 --> 00:47:10,610
é como ter unha chea
as condicións de agora, non?

1072
00:47:10,610 --> 00:47:12,318
Tivemos unha condición
comprobando se pertence

1073
00:47:12,318 --> 00:47:13,840
ao final, quizais o principio.

1074
00:47:13,840 --> 00:47:15,940
Necesitamos a algún tipo de bucle para
atopar o punto no medio.

1075
00:47:15,940 --> 00:47:17,400
Entón imos facelo co que é o 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
Encantado de coñecerte.

1080
00:47:19,368 --> 00:47:20,490
Polo tanto, temos 20.

1081
00:47:20,490 --> 00:47:21,220
Menos de cinco?

1082
00:47:21,220 --> 00:47:21,530
Non.

1083
00:47:21,530 --> 00:47:22,160
Menos de nove?

1084
00:47:22,160 --> 00:47:22,410
Non.

1085
00:47:22,410 --> 00:47:23,050
Menos de 17?

1086
00:47:23,050 --> 00:47:23,550
Non.

1087
00:47:23,550 --> 00:47:23,740
Aceptar.

1088
00:47:23,740 --> 00:47:25,701
Pertence aquí e
seus nomes son de novo?

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
Cuxas mans necesitas estar actualizado en primeiro lugar?

1096
00:47:32,140 --> 00:47:32,930
>> Audiencia: Eric.

1097
00:47:32,930 --> 00:47:33,429
Aceptar.

1098
00:47:33,429 --> 00:47:35,200
Entón Eric debe apuntar cara a onde?

1099
00:47:35,200 --> 00:47:35,930
Aos 22 anos.

1100
00:47:35,930 --> 00:47:36,430
Bo.

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
Súe pode, entón, ligar a Eric
e agora, se vostedes só

1103
00:47:40,800 --> 00:47:44,077
facer un espazo, o que é bo
visualmente, agora que fixemos a inserción.

1104
00:47:44,077 --> 00:47:47,160
Entón, imos agora considerar unha pregunta, pero
moitas grazas para os nosos voluntarios.

1105
00:47:47,160 --> 00:47:48,090
Moi ben feito.

1106
00:47:48,090 --> 00:47:50,831
Pode manter estes, se lle gusta.

1107
00:47:50,831 --> 00:47:54,140
E nós temos un fermoso agasallo de despedida se
vostede cada gustaría ter unha bola de estrés.

1108
00:47:54,140 --> 00:47:56,030
Déixeme só pasar isto para abaixo.

1109
00:47:56,030 --> 00:47:58,430
Entón, cal é o takeaway deste?

1110
00:47:58,430 --> 00:48:02,430
Este parece ser incrible
na medida en que temos agora

1111
00:48:02,430 --> 00:48:06,360
Presentar unha alternativa para unha
matriz que non é tan confinado

1112
00:48:06,360 --> 00:48:07,780
para unha matriz de algún tamaño fixo.

1113
00:48:07,780 --> 00:48:09,380
Poden crecer de forma dinámica.

1114
00:48:09,380 --> 00:48:13,220
>> Pero moito como vimos en semanas
pasado, nunca conseguir nada de balde,

1115
00:48:13,220 --> 00:48:15,740
como seguramente hai un trade-off aquí.

1116
00:48:15,740 --> 00:48:18,890
Así, cun Upside dun conectado
lista, é ese dinamismo?

1117
00:48:18,890 --> 00:48:21,590
Esta capacidade de crecer e, a verdade,
que poderiamos ter feito de exclusión

1118
00:48:21,590 --> 00:48:23,570
e poderiamos encoller corresponda.

1119
00:48:23,570 --> 00:48:24,710
Cara a un prezo que estamos pagando?

1120
00:48:24,710 --> 00:48:28,510

1121
00:48:28,510 --> 00:48:30,340
Dúas veces máis espazo, en primeiro lugar.

1122
00:48:30,340 --> 00:48:34,010
Se ollar para a foto, non máis
Eu son almacenar unha lista de enteiros.

1123
00:48:34,010 --> 00:48:36,740
Estou almacenando unha lista de
enteiros máis punteiros.

1124
00:48:36,740 --> 00:48:38,240
Entón, eu estou dobrando a cantidade de espazo.

1125
00:48:38,240 --> 00:48:40,740
Agora, quizais iso non é tan
un gran negocio 4 bytes, 8 bytes,

1126
00:48:40,740 --> 00:48:43,160
pero certamente podería engadir
Se a grandes conxuntos de datos.

1127
00:48:43,160 --> 00:48:45,570
¿Que é outra desvantaxe?

1128
00:48:45,570 --> 00:48:46,070
Si?

1129
00:48:46,070 --> 00:48:48,010
>> Audiencia: Temos que
atravesalo-los un por un.

1130
00:48:48,010 --> 00:48:48,760
DAVID Malan: Yeah.

1131
00:48:48,760 --> 00:48:50,260
Temos que atravesa-los un por un.

1132
00:48:50,260 --> 00:48:53,860
Vostede sabe o que, que deron este super
recurso conveniente de corchete

1133
00:48:53,860 --> 00:48:57,240
notación, máis propiamente
coñecido como acceso aleatorio,

1134
00:48:57,240 --> 00:48:59,280
onde podemos simplemente saltar
a un elemento individual

1135
00:48:59,280 --> 00:49:01,470
pero agora eu tiña
meus voluntarios aquí,

1136
00:49:01,470 --> 00:49:04,660
se eu quería atopar o
número 22, eu non podo só

1137
00:49:04,660 --> 00:49:06,620
ir para soporte algo algo.

1138
00:49:06,620 --> 00:49:10,530
Teño que ollar sobre a lista, moi
como os nosos exemplos de investigación de forma lineal,

1139
00:49:10,530 --> 00:49:12,260
para atopar o número 22.

1140
00:49:12,260 --> 00:49:14,340
Entón, nós parecen pagado un prezo alí.

1141
00:49:14,340 --> 00:49:16,430
Pero a xente pode, con todo,
resolver outros problemas.

1142
00:49:16,430 --> 00:49:18,587
>> De feito, deixe-me presentar
só un par de elementos visuais.

1143
00:49:18,587 --> 00:49:20,920
Entón, se foi para abaixo para
Mather do Comedor recentemente,

1144
00:49:20,920 --> 00:49:23,320
ten que se lembrar que a súa
pilas de bandexas coma este,

1145
00:49:23,320 --> 00:49:26,300
nós emprestamos estes desde
Annenberg antes da clase.

1146
00:49:26,300 --> 00:49:28,930
Polo tanto, esta pila de bandexas, porén,
en realidade, é representativa

1147
00:49:28,930 --> 00:49:30,860
dunha estrutura de datos informática.

1148
00:49:30,860 --> 00:49:32,910
Existe unha estrutura de datos
en ciencia da computación

1149
00:49:32,910 --> 00:49:38,010
coñecida como unha pila que moi ben
préstase a exactamente ese visual.

1150
00:49:38,010 --> 00:49:41,380
Por iso, cada unha destas bandexas non é un
bandexa, pero como un número e eu quería

1151
00:49:41,380 --> 00:49:45,010
para almacenar números, eu
podería poñer un aquí en baixo,

1152
00:49:45,010 --> 00:49:48,320
e eu podería poñer outro aquí en baixo,
e continuar empilhado números

1153
00:49:48,320 --> 00:49:53,180
enriba do outro, e que está
potencialmente útil sobre esta

1154
00:49:53,180 --> 00:49:55,450
é que o que é a implicación
desta estrutura de datos?

1155
00:49:55,450 --> 00:49:58,045
Que número podo retirar
primeiro o máis cómodo?

1156
00:49:58,045 --> 00:50:00,640

1157
00:50:00,640 --> 00:50:03,030
O máis recentemente, un posto alí.

1158
00:50:03,030 --> 00:50:06,430
>> Entón é iso que nós chamariamos en
ciencia da computación unha estrutura de datos LIFO.

1159
00:50:06,430 --> 00:50:08,070
Último a entrar, primeiro en saír.

1160
00:50:08,070 --> 00:50:10,800
E veremos pronto por que
que pode ser útil, pero, polo momento,

1161
00:50:10,800 --> 00:50:12,200
basta considerar o inmoble.

1162
00:50:12,200 --> 00:50:15,158
E é unha especie de idiota se pensas
sobre como o salón-comedor fai.

1163
00:50:15,158 --> 00:50:17,910
Cada vez que bandexas limpas e
poñer os máis frescos na parte superior,

1164
00:50:17,910 --> 00:50:22,160
podería ter unha limpo anteriormente
pero, finalmente, moi sucio e empoeirado

1165
00:50:22,160 --> 00:50:24,360
bandexa na parte inferior
se nunca realmente

1166
00:50:24,360 --> 00:50:26,820
chegar ao fondo da referida
pila, porque só

1167
00:50:26,820 --> 00:50:29,380
manter poñendo o novo e
os limpos enriba dela.

1168
00:50:29,380 --> 00:50:31,840
O mesmo pode ocorrer
nun supermercado tamén.

1169
00:50:31,840 --> 00:50:35,450
Se tes un caso de exhibición
de leite e cada vez CVS

1170
00:50:35,450 --> 00:50:37,610
ou quen recibe máis leite,
só empurrar os leites

1171
00:50:37,610 --> 00:50:39,880
xa ten a parte de atrás e
poñer os novos na fronte,

1172
00:50:39,880 --> 00:50:43,088
terá algúns bastante desagradable
leite ao final da estrutura de datos,

1173
00:50:43,088 --> 00:50:46,390
porque sempre no fondo ou
equivalentemente sempre na parte de atrás.

1174
00:50:46,390 --> 00:50:50,407
>> Pero hai outra forma de pensar sobre
aliñados datos e por exemplo, isto.

1175
00:50:50,407 --> 00:50:53,490
Se é unha desas persoas que lle gusta
a liña de fóra de tendas de Apple

1176
00:50:53,490 --> 00:50:55,610
cando un novo produto vén
fóra, probablemente está

1177
00:50:55,610 --> 00:50:58,780
Non usar unha pila de datos
estrutura porque

1178
00:50:58,780 --> 00:51:03,070
alienaria todos os outros que se
facendo cola para mercar algún xoguete novo.

1179
00:51:03,070 --> 00:51:06,610
Pola contra, probablemente está a usar
que tipo de estrutura de datos

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 sexa unha liña, ou máis
ou que máis británico-like, unha cola.

1182
00:51:13,493 --> 00:51:17,700
E verifícase unha cola é tamén un
estrutura de datos en ciencia da computación,

1183
00:51:17,700 --> 00:51:19,700
pero unha fila ten unha moi
propiedade diferente.

1184
00:51:19,700 --> 00:51:20,820
Non é LIFO.

1185
00:51:20,820 --> 00:51:21,990
Último a entrar, primeiro en saír.

1186
00:51:21,990 --> 00:51:22,800
Deus me libre.

1187
00:51:22,800 --> 00:51:24,280
É, en vez FIFO.

1188
00:51:24,280 --> 00:51:26,110
Primeiro en entrar, primeiro en saír.

1189
00:51:26,110 --> 00:51:27,970
E iso é bo
de xustiza amor '

1190
00:51:27,970 --> 00:51:30,428
seguramente cando está aliñados
super inicio da mañá.

1191
00:51:30,428 --> 00:51:33,400
Se chegar alí primeiro,
quere saír primeiro tamén.

1192
00:51:33,400 --> 00:51:35,880
>> E así todos estes datos
estruturas, colas e pilas

1193
00:51:35,880 --> 00:51:39,220
e acios de outros, acaba por ti
pode pensar niso como só unha matriz.

1194
00:51:39,220 --> 00:51:41,820
Esta é unha matriz, quizais
un tamaño fixo 4, pero tiña

1195
00:51:41,820 --> 00:51:44,990
ser unha especie de bo se puidésemos simplemente amontoar
bandexas case infinitamente alto se

1196
00:51:44,990 --> 00:51:46,780
teñen que moitas bandexas ou números.

1197
00:51:46,780 --> 00:51:48,840
Entón, talvez queremos
usar unha lista ligada aquí,

1198
00:51:48,840 --> 00:51:51,800
pero o trade-off será
potencialmente que necesitamos máis memoria,

1199
00:51:51,800 --> 00:51:55,930
leva un pouco máis de tempo, pero nós
non limitar a altura da pila,

1200
00:51:55,930 --> 00:51:59,550
así como escaparate de Mather
pode limitar o tamaño da pila,

1201
00:51:59,550 --> 00:52:03,117
e así que estas son decisións de proxecto ou
opcións dispoñibles para nós en última instancia.

1202
00:52:03,117 --> 00:52:04,950
Así, con estes datos
estruturas, comezan

1203
00:52:04,950 --> 00:52:09,360
vendo novos límites superiores potencialmente
sobre o que anteriormente foi super rápido

1204
00:52:09,360 --> 00:52:11,260
e onde imos deixar
fóra hoxe e onde

1205
00:52:11,260 --> 00:52:13,200
imos esperar a chegar a
é o mércores, nós imos

1206
00:52:13,200 --> 00:52:15,740
comezar a ollar para un conxunto de datos
estrutura que nos permite buscar

1207
00:52:15,740 --> 00:52:18,260
a través de datos en rexistro tempo final de novo.

1208
00:52:18,260 --> 00:52:21,470
E vimos que, lembre, a semana de cero
e un con busca binaria ou dividir

1209
00:52:21,470 --> 00:52:22,180
e conquistar.

1210
00:52:22,180 --> 00:52:26,240
Vén de volta e mellor aínda,
o Santo Graal para este mércores

1211
00:52:26,240 --> 00:52:29,510
será a de chegar co
estrutura de datos que corre verdadeiramente

1212
00:52:29,510 --> 00:52:32,070
ou en teoría
constante de tempo, a través de que

1213
00:52:32,070 --> 00:52:34,760
non importa cantas
millóns ou billóns de cousas

1214
00:52:34,760 --> 00:52:38,470
temos na estrutura de datos, será
levarnos tempo constante, quizais un paso

1215
00:52:38,470 --> 00:52:41,387
ou dous pasos ou 10 pasos,
pero os números de pasos constantes

1216
00:52:41,387 --> 00:52:42,970
para buscar esa estrutura de datos.

1217
00:52:42,970 --> 00:52:46,300
Que de feito será o Santo Graal
pero máis sobre iso o mércores.

1218
00:52:46,300 --> 00:52:49,045
See ya entón.

1219
00:52:49,045 --> 00:52:53,704
>> [Música tocando]

1220
00:52:53,704 --> 00:56:08,448