1
00:00:00,000 --> 00:00:03,381
>> [RIPRODUZIONE DI BRANI MUSICALI]

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

3
00:00:10,626 --> 00:00:11,610
>> [RIPRODUZIONE VIDEO]

4
00:00:11,610 --> 00:00:13,640
>> -Sta mentendo.

5
00:00:13,640 --> 00:00:14,380
>> -Riguardo cosa?

6
00:00:14,380 --> 00:00:17,182
>> -Non lo so.

7
00:00:17,182 --> 00:00:19,990
>> -Allora Cosa sappiamo?

8
00:00:19,990 --> 00:00:23,145
>> -Che Alle 9:15, Ray
Santoya era al bancomat.

9
00:00:23,145 --> 00:00:23,644
-Già.

10
00:00:23,644 --> 00:00:27,030
Quindi la domanda è, cosa
ci faceva alle 9:16?

11
00:00:27,030 --> 00:00:29,720
>> -Shooting Il 9 millimetri a qualcosa.

12
00:00:29,720 --> 00:00:31,540
Forse ha visto il cecchino.

13
00:00:31,540 --> 00:00:33,412
>> -O Stava lavorando con lui.

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

15
00:00:34,340 --> 00:00:36,200
Torna uno.

16
00:00:36,200 --> 00:00:36,975
>> -Cosa vedi?

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

18
00:00:44,400 --> 00:00:47,805
>> -Portare Il suo volto fino a schermo intero.

19
00:00:47,805 --> 00:00:48,680
>> -Il Suo bicchieri.

20
00:00:48,680 --> 00:00:50,060
>> -C'è Una riflessione.

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

22
00:01:00,455 --> 00:01:02,280
>> -E 'La squadra di baseball Nuevitas.

23
00:01:02,280 --> 00:01:03,110
Questo è il loro logo.

24
00:01:03,110 --> 00:01:05,820
>> -E Sta parlando di
chi indossa quella giacca.

25
00:01:05,820 --> 00:01:06,670
>> [FINE RIPRODUZIONE]

26
00:01:06,670 --> 00:01:07,628
>> DAVID MALAN: Va bene.

27
00:01:07,628 --> 00:01:11,210
Questo è CS50 e questo è un po 'più
di [incomprensibile] con cui sei

28
00:01:11,210 --> 00:01:12,890
dilettarsi con il problema di impostare quattro.

29
00:01:12,890 --> 00:01:16,606
Oggi iniziamo a guardare un po 'di più
profondamente in queste cose chiamate puntatori,

30
00:01:16,606 --> 00:01:18,480
che anche se è
un argomento piuttosto arcano,

31
00:01:18,480 --> 00:01:20,813
si scopre che sta andando
di essere il mezzo con cui

32
00:01:20,813 --> 00:01:24,320
può iniziare a costruire e assemblare
programmi molto più sofisticati.

33
00:01:24,320 --> 00:01:28,150
Ma abbiamo fatto il Mercoledì scorso
attraverso alcuni claymation primo.

34
00:01:28,150 --> 00:01:30,190
Quindi questo, richiamo, è
Binky e abbiamo usato lui

35
00:01:30,190 --> 00:01:33,148
per dare un'occhiata a un programma che
non ha davvero fare qualcosa di interessante,

36
00:01:33,148 --> 00:01:34,950
ma ha rivelato alcuni problemi.

37
00:01:34,950 --> 00:01:38,570
Quindi, per cominciare oggi, perché non camminiamo
rapidamente attraverso alcuni di questi passaggi,

38
00:01:38,570 --> 00:01:41,920
provare a distillare in termini di umani
esattamente quello che sta succedendo qui

39
00:01:41,920 --> 00:01:45,410
e perché questo è un male, e poi passare
ed effettivamente iniziare a costruire qualcosa

40
00:01:45,410 --> 00:01:46,309
con questa tecnica?

41
00:01:46,309 --> 00:01:48,350
Quindi questi sono stati i primi
due righe di questo programma

42
00:01:48,350 --> 00:01:51,340
e in termini profani, cosa
stanno facendo queste due linee?

43
00:01:51,340 --> 00:01:55,600
Qualcuno che è abbastanza confortevole
con ciò che è dichiarato sullo schermo?

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

45
00:01:58,340 --> 00:02:00,120
Quali sono queste due linee che fanno?

46
00:02:00,120 --> 00:02:02,070
Non è tutto ciò che
diverso da prima settimana,

47
00:02:02,070 --> 00:02:03,611
ma c'è qualche nuovo simbolo speciale.

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

49
00:02:04,152 --> 00:02:05,628
Là dietro.

50
00:02:05,628 --> 00:02:07,092
>> PUBBLICO: Dichiarare puntatori?

51
00:02:07,092 --> 00:02:08,050
DAVID MALAN: Dire di nuovo?

52
00:02:08,050 --> 00:02:08,860
PUBBLICO: Dichiarare puntatori?

53
00:02:08,860 --> 00:02:11,776
DAVID MALAN: puntatori Dichiarare e
cerchiamo di affinare un po 'di più.

54
00:02:11,776 --> 00:02:14,050
PUBBLICO: [incomprensibile]
indirizzo x e poi y.

55
00:02:14,050 --> 00:02:15,300
DAVID MALAN: E poi affrontare.

56
00:02:15,300 --> 00:02:18,550
Quindi in particolare quello che stiamo facendo
è che stiamo dichiarando due variabili.

57
00:02:18,550 --> 00:02:21,252
Queste variabili, però, sono in corso
essere di tipo int stella, che

58
00:02:21,252 --> 00:02:23,210
significa più specificamente
stanno andando a memorizzare

59
00:02:23,210 --> 00:02:26,450
l'indirizzo di un int,
rispettivamente, X e Y.

60
00:02:26,450 --> 00:02:27,660
Ora ci sono i valori?

61
00:02:27,660 --> 00:02:32,621
Ci sono indirizzi effettivi in ​​questi
due variabili in questo momento?

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

63
00:02:33,120 --> 00:02:35,030
E 'solo i cosiddetti valori di immondizia.

64
00:02:35,030 --> 00:02:38,120
Se in realtà non si assegna un
variabile, ciò che era nella RAM

65
00:02:38,120 --> 00:02:42,224
in precedenza sta andando a riempire con zeri
e quelle due di queste variabili.

66
00:02:42,224 --> 00:02:44,140
Ma noi non sappiamo ancora
cosa sono e questo è

67
00:02:44,140 --> 00:02:47,060
andando ad essere la chiave per il motivo per cui Binky
perso la testa la scorsa settimana.

68
00:02:47,060 --> 00:02:49,980
>> Quindi questa è stata la claymation
incarnazione di questo

69
00:02:49,980 --> 00:02:53,580
per cui si hanno solo due variabili,
piccoli pezzi circolari di argilla,

70
00:02:53,580 --> 00:02:57,330
che può memorizzare variabili, ma come
le frecce avvolto suggeriscono,

71
00:02:57,330 --> 00:03:00,640
non stanno in realtà punta
al noto ovunque per sé.

72
00:03:00,640 --> 00:03:03,670
Allora abbiamo avuto questa linea, e questo
era nuovo la settimana scorsa, per la memoria malloc

73
00:03:03,670 --> 00:03:07,130
assegnazione, che è solo un modo elegante
di raccontare il sistema operativo, Linux

74
00:03:07,130 --> 00:03:09,750
o Mac OS o Windows,
ehi, dammi un po 'di memoria,

75
00:03:09,750 --> 00:03:11,780
e tutto quello che hai da raccontare
il sistema operativo

76
00:03:11,780 --> 00:03:14,699
è quello che quando si chiede che per la memoria.

77
00:03:14,699 --> 00:03:16,990
Non sta andando a cura ciò che
si sta andando a che fare con esso,

78
00:03:16,990 --> 00:03:19,786
ma si ha bisogno di raccontare la operativo
Sistema cosa per mezzo di malloc.

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

80
00:03:20,286 --> 00:03:21,078
>> PUBBLICO: Quanto?

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

82
00:03:21,994 --> 00:03:25,280
Quanto in byte, e quindi, questo, di nuovo,
un esempio forzato, sta solo dicendo,

83
00:03:25,280 --> 00:03:27,360
dammi la dimensione di un int.

84
00:03:27,360 --> 00:03:30,550
Ora, la dimensione di un int
è quattro byte o 32 bit.

85
00:03:30,550 --> 00:03:32,850
Quindi questo è solo un modo di
dicendo, hey, il sistema operativo,

86
00:03:32,850 --> 00:03:37,290
dammi quattro byte di memoria
che posso usare a mia disposizione,

87
00:03:37,290 --> 00:03:40,560
e in particolare, ciò fa
ritorno malloc rispetto

88
00:03:40,560 --> 00:03:41,795
a quel pezzo di quattro byte?

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

90
00:03:44,110 --> 00:03:44,860
PUBBLICO: Indirizzo?

91
00:03:44,860 --> 00:03:45,901
DAVID MALAN: L'indirizzo.

92
00:03:45,901 --> 00:03:47,580
L'indirizzo di quel pezzo di quattro byte.

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

94
00:03:48,190 --> 00:03:51,430
Ed è quello che è memorizzato in ultima analisi,
in x ed è per questo non lo facciamo davvero

95
00:03:51,430 --> 00:03:55,240
interessa cosa il numero di tale
indirizzo è, che si tratti di OX1 o OX2

96
00:03:55,240 --> 00:03:57,110
o qualche indirizzo esadecimale criptico.

97
00:03:57,110 --> 00:03:59,850
Abbiamo appena preoccupiamo pittoricamente
che la variabile x è ora

98
00:03:59,850 --> 00:04:01,630
punta a quel pezzo di memoria.

99
00:04:01,630 --> 00:04:05,570
Così la freccia rappresenta un puntatore oppure
più specificamente, un indirizzo di memoria.

100
00:04:05,570 --> 00:04:09,120
Ma ancora una volta, non ci importa tipicamente
ciò che quegli indirizzi reali sono.

101
00:04:09,120 --> 00:04:11,780
Ora, questa linea, dice
ciò che in parole povere?

102
00:04:11,780 --> 00:04:14,330
Stella x ottiene 42 e virgola.

103
00:04:14,330 --> 00:04:17,390
Cosa significa questo?

104
00:04:17,390 --> 00:04:18,200
Vuoi andare?

105
00:04:18,200 --> 00:04:20,102
Non graffiare il collo.

106
00:04:20,102 --> 00:04:22,360
>> PUBBLICO: L'indirizzo di x è al 42.

107
00:04:22,360 --> 00:04:24,300
>> DAVID MALAN: L'indirizzo di x è a 42.

108
00:04:24,300 --> 00:04:25,190
Non proprio.

109
00:04:25,190 --> 00:04:28,485
Così vicino, ma non del tutto, perché c'è
la stella che è prefisso questo x.

110
00:04:28,485 --> 00:04:29,860
Quindi abbiamo bisogno di modificare un po '.

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

112
00:04:31,032 --> 00:04:36,044
>> PUBBLICO: Il valore che la
puntatore x sta indicando è 42.

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

114
00:04:36,710 --> 00:04:40,840
Il valore che è il puntatore x
indicando, diciamo, sono 42,

115
00:04:40,840 --> 00:04:44,165
o per dirla in altro modo, la stella
x dice, andare a qualunque indirizzo

116
00:04:44,165 --> 00:04:48,340
è in x, che si tratti di uno di Oxford
Street o 33 Oxford Street

117
00:04:48,340 --> 00:04:51,850
o OX1 o OX33, qualunque
tale indirizzo numerico è,

118
00:04:51,850 --> 00:04:54,380
stella x è la dereferenziazione di x.

119
00:04:54,380 --> 00:04:57,297
Quindi, andare a questo indirizzo e
poi mettere il numero 42 c'è.

120
00:04:57,297 --> 00:04:59,380
Quindi sarebbe un
equivalente di dire che.

121
00:04:59,380 --> 00:05:01,860
In modo che è tutto bene e poi
vorremmo rappresentare l'immagine

122
00:05:01,860 --> 00:05:05,370
come segue dove abbiamo aggiunto
il 42 di quel pezzo di quattro

123
00:05:05,370 --> 00:05:09,370
byte sul lato destro, ma
questa linea era dove le cose sono andate male

124
00:05:09,370 --> 00:05:11,120
e la testa di Binky spuntato
off a questo punto,

125
00:05:11,120 --> 00:05:15,290
perché le cose brutte accadono quando
si dereference valori della spazzatura

126
00:05:15,290 --> 00:05:18,210
oppure si dereference non valida
puntatori, e lo dico non valida

127
00:05:18,210 --> 00:05:21,020
perché a questo punto nel
storia, ciò che è dentro di y?

128
00:05:21,020 --> 00:05:24,440
Qual è il valore di y base
sugli ultimi passi?

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

130
00:05:25,360 --> 00:05:26,115
Che cos'è?

131
00:05:26,115 --> 00:05:26,990
>> PUBBLICO: Un indirizzo.

132
00:05:26,990 --> 00:05:28,460
DAVID MALAN: Un indirizzo.

133
00:05:28,460 --> 00:05:31,910
Dovrebbe essere un indirizzo
ma ho inizializzato esso?

134
00:05:31,910 --> 00:05:32,800
Quindi non ho ancora.

135
00:05:32,800 --> 00:05:35,430
Quindi, ciò che è noto per essere lì?

136
00:05:35,430 --> 00:05:37,590
E 'solo un certo valore spazzatura.

137
00:05:37,590 --> 00:05:41,500
Potrebbe essere qualsiasi indirizzo da zero a
2 miliardi se si hanno due giga di RAM,

138
00:05:41,500 --> 00:05:44,289
o zero a 4 miliardi se hai
ha ottenuto quattro gigabyte di RAM.

139
00:05:44,289 --> 00:05:46,080
E 'certo valore spazzatura,
ma il problema è

140
00:05:46,080 --> 00:05:48,200
che il sistema operativo,
se non è dato

141
00:05:48,200 --> 00:05:51,140
che pezzo di memoria specificamente
che si sta cercando di andare,

142
00:05:51,140 --> 00:05:54,650
è generalmente causerà cosa
abbiamo visto come un segmentation fault.

143
00:05:54,650 --> 00:05:57,810
Quindi, in realtà, qualcuno di voi che hanno
lottato a problemi in orario d'ufficio

144
00:05:57,810 --> 00:06:00,393
o problemi che è più
generalmente con il tentativo di capire

145
00:06:00,393 --> 00:06:02,150
un errore di segmentazione,
questo significa che in genere

146
00:06:02,150 --> 00:06:05,017
stai toccando un segmento di
memoria che non si dovrebbe essere.

147
00:06:05,017 --> 00:06:07,350
Stai toccando memoria
il sistema operativo non ha

148
00:06:07,350 --> 00:06:10,450
vi ha permesso di toccare, che si tratti di
andando troppo lontano nella propria matrice

149
00:06:10,450 --> 00:06:12,870
o da adesso, se
è perché stai toccando

150
00:06:12,870 --> 00:06:14,780
memoria che solo è un valore spazzatura.

151
00:06:14,780 --> 00:06:18,230
>> Così facendo stella x qui è
tipo di comportamento non definito.

152
00:06:18,230 --> 00:06:22,030
Non si dovrebbe mai farlo perché le probabilità
sono, il programma sta solo andando in crash,

153
00:06:22,030 --> 00:06:24,050
perché stai dicendo,
vai a questo indirizzo

154
00:06:24,050 --> 00:06:27,000
e non avete idea di dove
tale indirizzo è in realtà.

155
00:06:27,000 --> 00:06:30,300
Quindi il sistema operativo è probabile
andare a sbattere il vostro programma

156
00:06:30,300 --> 00:06:33,840
come risultato e anzi, che è
quello che è successo lì a Binky.

157
00:06:33,840 --> 00:06:37,210
Quindi in definitiva, Binky fisso
questo problema con questo.

158
00:06:37,210 --> 00:06:38,909
In modo che il programma stesso è stato difettoso.

159
00:06:38,909 --> 00:06:41,450
Ma se si ordina di andare avanti
ed eseguire questa linea, invece,

160
00:06:41,450 --> 00:06:45,580
y è uguale x significa semplicemente qualunque
indirizzo è un x, messa anche in y.

161
00:06:45,580 --> 00:06:48,740
>> E così pittoricamente, abbiamo
questo rappresentato con due frecce

162
00:06:48,740 --> 00:06:51,570
da x e y da puntamento
nello stesso posto.

163
00:06:51,570 --> 00:06:55,760
Così semanticamente, x è uguale
ay a causa sia di quelli

164
00:06:55,760 --> 00:07:00,300
sono la conservazione della stessa
indirizzo, ergo che punta a 42,

165
00:07:00,300 --> 00:07:04,910
e ora, quando si dice stella
y, andare all'indirizzo di y,

166
00:07:04,910 --> 00:07:06,790
questo ha un effetto collaterale interessante.

167
00:07:06,790 --> 00:07:10,320
Così l'indirizzo in y è il
stessa cosa come l'indirizzo di x.

168
00:07:10,320 --> 00:07:15,060
Quindi, se si dice andare all'indirizzo
in y e modificare il valore di 13,

169
00:07:15,060 --> 00:07:17,140
chi altro è interessato?

170
00:07:17,140 --> 00:07:21,100
X è, punto D, per così dire,
dovrebbero essere colpiti pure.

171
00:07:21,100 --> 00:07:24,340
>> E in effetti, come Nick ha disegnato questa immagine
in claymation era esattamente questo.

172
00:07:24,340 --> 00:07:28,665
Anche se seguiamo il puntatore
y, abbiamo finito nello stesso posto,

173
00:07:28,665 --> 00:07:32,780
e quindi se dovessimo stampare
fuori x o pointee di y,

174
00:07:32,780 --> 00:07:35,720
allora vedremmo il valore di 13.

175
00:07:35,720 --> 00:07:37,927
Ora, io dico di essere pointee
coerente con il video.

176
00:07:37,927 --> 00:07:39,760
I programmatori, al mio
conoscenza, mai realmente

177
00:07:39,760 --> 00:07:42,460
dire la parola pointee,
ciò che è appuntita

178
00:07:42,460 --> 00:07:44,650
a, ma per coerenza
con il video, realizzare

179
00:07:44,650 --> 00:07:47,520
questo è tutto quello che era
inteso in tale situazione.

180
00:07:47,520 --> 00:07:54,190
Quindi tutte le domande su claymation
o puntatori o malloc appena ancora?

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

182
00:07:54,850 --> 00:07:55,470
Tutto ok.

183
00:07:55,470 --> 00:07:58,560
>> Quindi, senza ulteriori
indugi, diamo uno sguardo

184
00:07:58,560 --> 00:08:00,700
dove questo ha in realtà
stato utilizzato per qualche tempo.

185
00:08:00,700 --> 00:08:03,580
Così abbiamo avuto questa libreria CS50
che è avuto tutte queste funzioni.

186
00:08:03,580 --> 00:08:06,810
Abbiamo utilizzato GetInt molto, GetString,
probabilmente GetLongLong precedenza

187
00:08:06,810 --> 00:08:09,840
nel mio PSet uno o così, ma
cosa sta realmente succedendo?

188
00:08:09,840 --> 00:08:12,920
Bene, diamo un rapido sguardo
sotto la cappa ad un programma che

189
00:08:12,920 --> 00:08:17,017
ispira per questo che vi diamo il CS50
biblioteca, e anzi come della scorsa settimana,

190
00:08:17,017 --> 00:08:18,850
abbiamo iniziato a prendere quelli
ruote di formazione off.

191
00:08:18,850 --> 00:08:21,080
Quindi questo è ora ordinato
di un post-mortem di ciò che

192
00:08:21,080 --> 00:08:23,690
va avanti
all'interno della libreria CS50,

193
00:08:23,690 --> 00:08:27,250
anche se ora inizia a muoversi
lontano da essa per la maggior parte dei programmi.

194
00:08:27,250 --> 00:08:29,460
>> Quindi questo è un programma chiamato scanf 0.

195
00:08:29,460 --> 00:08:30,510
E 'super breve.

196
00:08:30,510 --> 00:08:33,909
Ha solo queste righe, ma
introduce una funzione chiamata scanf

197
00:08:33,909 --> 00:08:36,909
che realmente stiamo andando a vedere in
un momento all'interno della biblioteca CS50,

198
00:08:36,909 --> 00:08:38,600
anche se in una forma leggermente diversa.

199
00:08:38,600 --> 00:08:41,330
Quindi questo programma on line 16
è dichiarazione di una variabile x.

200
00:08:41,330 --> 00:08:43,150
Quindi dammi quattro byte per un int.

201
00:08:43,150 --> 00:08:45,750
E 'stato dice utente,
numero di favore, e poi

202
00:08:45,750 --> 00:08:49,010
questa è una linea interessante che
in realtà lega insieme la scorsa settimana

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

204
00:08:49,790 --> 00:08:53,230
Scanf, e quindi notare ci vuole un
stringa di formato, proprio come printf,

205
00:08:53,230 --> 00:08:57,480
% i significa un int, e quindi ci vuole un
Il secondo argomento che sembra un po '

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

207
00:08:58,260 --> 00:09:01,880
E 'commerciale x, e ricordare,
abbiamo visto solo una volta la settimana scorsa.

208
00:09:01,880 --> 00:09:03,465
Che cosa significa e commerciale x rappresenta?

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

210
00:09:06,210 --> 00:09:08,450
Cosa fa e commerciale fa in C?

211
00:09:08,450 --> 00:09:08,950
Sì?

212
00:09:08,950 --> 00:09:10,024
>> PUBBLICO: L'indirizzo del.

213
00:09:10,024 --> 00:09:11,190
DAVID MALAN: L'indirizzo.

214
00:09:11,190 --> 00:09:13,190
Quindi è il contrario
dell'operatore stella,

215
00:09:13,190 --> 00:09:17,270
mentre l'operatore stella dice, andare a
questo indirizzo, l'operatore commerciale

216
00:09:17,270 --> 00:09:20,280
dice, capire il
indirizzo di questa variabile,

217
00:09:20,280 --> 00:09:23,530
e quindi questo è fondamentale, perché
scopo di scanf nella vita

218
00:09:23,530 --> 00:09:26,320
è quello di eseguire la scansione l'utente del
input dalla tastiera,

219
00:09:26,320 --> 00:09:29,970
seconda qualunque lui o lei
tipi, e poi leggere input dell'utente

220
00:09:29,970 --> 00:09:32,970
in una variabile, ma
ha visto nelle ultime due settimane

221
00:09:32,970 --> 00:09:36,080
che tale funzione di scambio che abbiamo
cercato sforzo per implementare

222
00:09:36,080 --> 00:09:37,110
è stato appena rotto.

223
00:09:37,110 --> 00:09:42,470
Ricordiamo che con la funzione swap,
se abbiamo appena dichiarato A e B come interi,

224
00:09:42,470 --> 00:09:47,040
abbiamo scambiamo con successo il
due variabili all'interno di scambio

225
00:09:47,040 --> 00:09:50,080
proprio come con il latte e succo d'arancia,
ma non appena tornato scambio,

226
00:09:50,080 --> 00:09:55,200
quello che era il risultato con rispetto
axey, i valori originali?

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

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

229
00:09:56,200 --> 00:09:59,754
Non è successo niente quel tempo, perché
swap cambiano solo i suoi copie locali,

230
00:09:59,754 --> 00:10:01,670
vale a dire, tutte
questa volta, ogni volta che abbiamo

231
00:10:01,670 --> 00:10:04,010
stato passando argomenti
alle funzioni, siamo

232
00:10:04,010 --> 00:10:05,939
solo di passaggio le copie di tali argomenti.

233
00:10:05,939 --> 00:10:07,980
Si può fare con quel
quello che vuoi con loro,

234
00:10:07,980 --> 00:10:10,890
ma che stanno andando a non avere
effetto sui valori originali.

235
00:10:10,890 --> 00:10:13,650
Quindi questo è problematico se si
vogliono avere una funzione come scanf

236
00:10:13,650 --> 00:10:17,170
in vita, il cui scopo è quello di eseguire la scansione
input dell'utente dalla tastiera

237
00:10:17,170 --> 00:10:22,010
e poi riempire gli spazi vuoti, in modo da
parlare, cioè, dare una variabile come x

238
00:10:22,010 --> 00:10:25,410
un valore, perché se fossi
passare solo x a scanf,

239
00:10:25,410 --> 00:10:28,790
se si considera la logica dello scorso
settimana, scanf può fare quello che vuole

240
00:10:28,790 --> 00:10:33,100
con una copia di x, ma non poteva
modificare in modo permanente x se non diamo

241
00:10:33,100 --> 00:10:37,120
scanf una mappa del tesoro, per così dire,
dove x indica il luogo, in cui

242
00:10:37,120 --> 00:10:41,860
passiamo l'indirizzo di x in modo che
scanf può andare lì e in realtà il cambiamento

243
00:10:41,860 --> 00:10:42,920
il valore di x.

244
00:10:42,920 --> 00:10:45,080
E così effettivamente, tutte
che questo programma fa

245
00:10:45,080 --> 00:10:53,180
se faccio scanf 0, a mia fonte
Directory 5m, fare scanf 0,

246
00:10:53,180 --> 00:10:57,730
dot taglio su scanf, numero
si prega di 50, grazie per il 50.

247
00:10:57,730 --> 00:11:01,020
>> Quindi non è tutto così interessante,
ma quello che sta succedendo davvero

248
00:11:01,020 --> 00:11:04,820
è che non appena mi chiamo
scanf qui, il valore di x

249
00:11:04,820 --> 00:11:06,410
viene cambiato in modo permanente.

250
00:11:06,410 --> 00:11:08,335
Ora, questo sembra bello e
buona, e infatti,

251
00:11:08,335 --> 00:11:11,200
sembra che non abbiamo veramente bisogno
la biblioteca CS50 affatto più.

252
00:11:11,200 --> 00:11:13,960
Ad esempio, corriamo
questo ancora una volta qui.

253
00:11:13,960 --> 00:11:15,750
Mi permetta di riaprire per un secondo.

254
00:11:15,750 --> 00:11:20,600
Proviamo un numero per favore e
invece di dire 50 come prima,

255
00:11:20,600 --> 00:11:22,810
diciamo solo che non.

256
00:11:22,810 --> 00:11:24,000
OK, questo è un po 'strano.

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

258
00:11:25,270 --> 00:11:28,680
E proprio qualche sciocchezza qui.

259
00:11:28,680 --> 00:11:31,170
Quindi non sembra
gestire le situazioni sbagliate.

260
00:11:31,170 --> 00:11:33,620
Quindi abbiamo bisogno di minimamente inizio
l'aggiunta di un po 'di controllo degli errori

261
00:11:33,620 --> 00:11:37,460
per assicurarsi che l'utente disponga
digitato un numero reale come 50,

262
00:11:37,460 --> 00:11:40,720
perché le parole apparentemente di battitura
Non viene rilevato come problematico,

263
00:11:40,720 --> 00:11:42,020
ma probabilmente dovrebbe essere.

264
00:11:42,020 --> 00:11:46,450
>> Diamo un'occhiata a questa versione ora che è
il mio tentativo di reimplementare GetString.

265
00:11:46,450 --> 00:11:48,437
Se scanf ha tutto questo
funzionalità integrato,

266
00:11:48,437 --> 00:11:51,270
perché abbiamo stato dilettarsi con questi
ruote di formazione come GetString?

267
00:11:51,270 --> 00:11:55,450
Bene, qui è forse la mia
semplice versione del GetString

268
00:11:55,450 --> 00:12:00,766
per cui una settimana fa, avrei potuto dire,
dammi una stringa e lo chiamano tampone.

269
00:12:00,766 --> 00:12:03,390
Oggi, ho intenzione di iniziare a solo
dicendo char stella, che, ricordo,

270
00:12:03,390 --> 00:12:04,400
è solo sinonimo.

271
00:12:04,400 --> 00:12:06,629
Sembra più paura, ma è
la stessa identica cosa.

272
00:12:06,629 --> 00:12:09,420
Quindi dammi un buffer variabile chiamata
che sta per memorizzare una stringa,

273
00:12:09,420 --> 00:12:12,780
dire la stringa user per favore,
e poi, proprio come prima,

274
00:12:12,780 --> 00:12:17,760
cerchiamo di prendere in prestito questa lezione scanf
% s questa volta e quindi passare in tampone.

275
00:12:17,760 --> 00:12:19,310
Ora, un controllo di integrità rapido.

276
00:12:19,310 --> 00:12:22,120
Perché non mi dicendo
ampersand tampone questa volta?

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

278
00:12:25,190 --> 00:12:26,625
Dedurre dall'esempio precedente.

279
00:12:26,625 --> 00:12:28,000
PUBBLICO: Char stella è un puntatore.

280
00:12:28,000 --> 00:12:29,920
DAVID MALAN: Esattamente,
perché questa volta, char

281
00:12:29,920 --> 00:12:34,080
stella è già un puntatore, un indirizzo,
per definizione, di quella stella essere lì.

282
00:12:34,080 --> 00:12:37,530
E se scanf aspetta un indirizzo,
è sufficiente solo per passare in tampone.

283
00:12:37,530 --> 00:12:39,260
Non ho bisogno di dire di buffer e commerciale.

284
00:12:39,260 --> 00:12:42,177
Per i curiosi, si potrebbe
fare qualcosa di simile.

285
00:12:42,177 --> 00:12:43,510
Avrebbe significato diverso.

286
00:12:43,510 --> 00:12:47,240
Questo darebbe un puntatore
a un puntatore, che è in realtà

287
00:12:47,240 --> 00:12:50,050
una cosa valida in C, ma per
ora, teniamolo semplice

288
00:12:50,050 --> 00:12:51,750
e mantenere la storia coerente.

289
00:12:51,750 --> 00:12:54,100
Sto solo andando a passare in
tampone e questo è corretto.

290
00:12:54,100 --> 00:12:56,487
Il problema è se questo.

291
00:12:56,487 --> 00:12:58,820
Lasciami andare avanti ed eseguire questo
programma dopo compilarlo.

292
00:12:58,820 --> 00:13:00,902
Fai scanf 1.

293
00:13:00,902 --> 00:13:02,610
Dannazione, il mio compilatore di
cattura il mio errore.

294
00:13:02,610 --> 00:13:04,090
Dammi un secondo.

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

296
00:13:05,460 --> 00:13:06,990
Diciamo che scanf-1.c.

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

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

299
00:13:11,380 --> 00:13:12,720
Ci siamo.

300
00:13:12,720 --> 00:13:14,280
Ne ho bisogno.

301
00:13:14,280 --> 00:13:16,750
ID CS50 ha varie
impostazioni di configurazione

302
00:13:16,750 --> 00:13:18,280
che si proteggono contro se stessi.

303
00:13:18,280 --> 00:13:21,300
Avevo bisogno di disattivare quelle di
esecuzione clang manualmente questo momento.

304
00:13:21,300 --> 00:13:22,140
Quindi, per favore corda.

305
00:13:22,140 --> 00:13:25,560
Ho intenzione di andare avanti e digitare
nel mio mondo ciao preferito.

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

307
00:13:26,490 --> 00:13:27,700
Non è quello che ho scritto.

308
00:13:27,700 --> 00:13:29,690
Quindi è indicativo di
qualcosa che è sbagliato.

309
00:13:29,690 --> 00:13:33,920
Lasciami andare avanti e digito
in una lunghissima corda.

310
00:13:33,920 --> 00:13:37,210
Grazie per il nulla e non so
se ho intenzione di essere in grado di crash.

311
00:13:37,210 --> 00:13:40,240
Proviamo un po 'di copia
incolla e vedere se questo aiuta.

312
00:13:40,240 --> 00:13:43,290
Basta incollare un sacco di questo.

313
00:13:43,290 --> 00:13:47,310
E 'sicuramente un grande
stringa del solito.

314
00:13:47,310 --> 00:13:51,450
Diciamo solo davvero scrivere.

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

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

317
00:13:52,650 --> 00:13:53,480
Comando non trovato.

318
00:13:53,480 --> 00:13:54,550
Ecco, questo è estraneo.

319
00:13:54,550 --> 00:13:56,440
Ecco perché ho incollato
alcuni personaggi cattivi,

320
00:13:56,440 --> 00:13:59,780
ma questo risulta non è andare a lavorare.

321
00:13:59,780 --> 00:14:03,510
>> Proviamo questo una volta di più, perché
è più divertente se abbiamo effettivamente crash.

322
00:14:03,510 --> 00:14:09,116
Proviamo quindi a digitare questo e ora, io sono
andando a copiare una lunghissima corda

323
00:14:09,116 --> 00:14:10,990
e ora vediamo se siamo
può mandare in crash questa cosa.

324
00:14:10,990 --> 00:14:14,235
Notate ho omesso spazi e
nuove linee e punti e virgola

325
00:14:14,235 --> 00:14:16,035
e tutti i personaggi funky.

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

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

328
00:14:21,090 --> 00:14:22,880
E ora la rete è solo di essere lento.

329
00:14:22,880 --> 00:14:27,460
Ho tenuto giù Comando-V troppo lungo, chiaramente.

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

331
00:14:28,190 --> 00:14:29,260
Comando non trovato.

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

333
00:14:29,780 --> 00:14:32,240
Bene, il punto è
comunque il seguente.

334
00:14:32,240 --> 00:14:36,910
Così che cosa sta realmente accadendo
su alla presente dichiarazione

335
00:14:36,910 --> 00:14:39,240
di char buffer di stella sulla linea 16?

336
00:14:39,240 --> 00:14:41,820
Così Cosa ottengo
quando dichiaro un puntatore?

337
00:14:41,820 --> 00:14:47,440
Tutto quello che sto ricevendo è un valore quattro byte
chiamato buffer, ma quello che c'è dentro di esso

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

339
00:14:49,540 --> 00:14:50,930
E 'solo un certo valore spazzatura.

340
00:14:50,930 --> 00:14:54,170
Perché ogni volta che si dichiara una variabile
in C, è solo un po 'di valore spazzatura,

341
00:14:54,170 --> 00:14:56,220
e stiamo cominciando a
viaggio su questa realtà.

342
00:14:56,220 --> 00:14:59,720
Ora, quando dico scanf,
vai a questo indirizzo

343
00:14:59,720 --> 00:15:01,520
e mettere qualunque l'utente digita.

344
00:15:01,520 --> 00:15:06,400
Se l'utente digita ciao
mondo, beh, dove lo metto?

345
00:15:06,400 --> 00:15:07,750
Buffer è un valore spazzatura.

346
00:15:07,750 --> 00:15:11,510
>> Ecco, questo è un po 'come una freccia
che sta puntando chissà dove.

347
00:15:11,510 --> 00:15:13,880
Forse è rivolto
proprio qui nella mia memoria.

348
00:15:13,880 --> 00:15:16,560
Così, quando l'utente
Tipi di mondo, ciao

349
00:15:16,560 --> 00:15:22,380
il programma tenta di mettere il
stringa ciao mondo backslash 0

350
00:15:22,380 --> 00:15:23,910
in quel pezzo di memoria.

351
00:15:23,910 --> 00:15:27,070
Ma con alta probabilità, ma
chiaramente non 100% di probabilità,

352
00:15:27,070 --> 00:15:30,440
il computer sta per schiantarsi poi
il programma perché questo non è

353
00:15:30,440 --> 00:15:32,490
ricordo che dovrebbe essere permesso di toccare.

354
00:15:32,490 --> 00:15:36,330
Così, in breve, questo programma è
incrinato proprio per questo motivo.

355
00:15:36,330 --> 00:15:38,070
Io non sto facendo quello che fondamentalmente?

356
00:15:38,070 --> 00:15:42,366
Quali passi sono ho omesso, proprio come
abbiamo omesso di primo esempio di Binky?

357
00:15:42,366 --> 00:15:42,866
Sì?

358
00:15:42,866 --> 00:15:43,710
>> PUBBLICO: Allocazione di memoria?

359
00:15:43,710 --> 00:15:45,001
>> DAVID MALAN: allocazione della memoria.

360
00:15:45,001 --> 00:15:48,400
Non ho effettivamente allocato
qualsiasi memoria per quella stringa.

361
00:15:48,400 --> 00:15:50,270
Così siamo in grado di risolvere questo in un paio di modi.

362
00:15:50,270 --> 00:15:52,700
Uno, siamo in grado di mantenere le cose semplici
e in effetti, ora sei

363
00:15:52,700 --> 00:15:55,116
sta per iniziare a vedere una sfocatura
delle linee tra ciò che

364
00:15:55,116 --> 00:15:58,520
un array è, ciò che una stringa è, ciò che un
char stella è, ciò che un array di caratteri

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

366
00:15:59,020 --> 00:16:02,450
Ecco un secondo esempio
coinvolgendo stringhe e preavviso

367
00:16:02,450 --> 00:16:05,690
tutto quello che ho fatto on line
16 è, invece di dire

368
00:16:05,690 --> 00:16:09,530
tale buffer sarà un char
stella, un puntatore a un pezzo di memoria,

369
00:16:09,530 --> 00:16:14,057
Ho intenzione di dare molto in modo proattivo
io un buffer per 16 caratteri,

370
00:16:14,057 --> 00:16:16,390
e in effetti, se si ha familiarità
con il termine buffering,

371
00:16:16,390 --> 00:16:20,570
probabilmente dal mondo di video,
dove un video è buffering, buffering,

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

373
00:16:21,175 --> 00:16:22,550
Ebbene, qual è la connessione qui?

374
00:16:22,550 --> 00:16:24,960
Beh, Dentro di YouTube
e dentro di lettori video

375
00:16:24,960 --> 00:16:27,200
generalmente è un array
che è più grande di 16 anni.

376
00:16:27,200 --> 00:16:30,340
Potrebbe essere un array di dimensione uno
megabyte, forse 10 megabyte,

377
00:16:30,340 --> 00:16:34,330
e in tale matrice fa il browser
scaricare un sacco di byte,

378
00:16:34,330 --> 00:16:37,500
un sacco di megabyte di
video e il lettore video,

379
00:16:37,500 --> 00:16:40,930
YouTube o chiunque sia, inizia
leggere i byte da quella matrice,

380
00:16:40,930 --> 00:16:43,530
e ogni volta che si vede il
parola buffering, buffering,

381
00:16:43,530 --> 00:16:46,350
questo significa che il giocatore ha
ottenuto al termine di tale matrice.

382
00:16:46,350 --> 00:16:50,430
La rete è così lento che non ha
riempito l'array con più byte

383
00:16:50,430 --> 00:16:55,610
e così sei fuori di bit
per visualizzare all'utente.

384
00:16:55,610 --> 00:16:59,430
>> Quindi buffer è un termine adatto qui in quella
è solo un array, un pezzo di memoria.

385
00:16:59,430 --> 00:17:02,530
E questo lo risolverà
perché si scopre

386
00:17:02,530 --> 00:17:07,410
che è possibile trattare gli array come se
sono indirizzi, anche se tampone

387
00:17:07,410 --> 00:17:10,710
è solo un simbolo, è un
sequenza di caratteri, tampone,

388
00:17:10,710 --> 00:17:14,760
che è utile per me, il programmatore,
si può passare il suo nome in giro

389
00:17:14,760 --> 00:17:17,079
come se si trattasse di un
puntatore, come se

390
00:17:17,079 --> 00:17:21,000
erano l'indirizzo di un pezzo
di memoria per 16 caratteri.

391
00:17:21,000 --> 00:17:24,530
Ecco, questo è da dire, posso passare
scanf esattamente quella parola

392
00:17:24,530 --> 00:17:30,670
e così ora, se faccio questo programma,
fare scanf 2, puntino barra scanf 2,

393
00:17:30,670 --> 00:17:35,386
e digitare ciao mondo,
Invio, che tempo--

394
00:17:35,386 --> 00:17:37,590
>> Hmm, che cosa è successo?

395
00:17:37,590 --> 00:17:39,340
Stringa prego.

396
00:17:39,340 --> 00:17:41,430
Che cosa ho fatto di sbagliato?

397
00:17:41,430 --> 00:17:43,800
Ciao mondo, buffer.

398
00:17:43,800 --> 00:17:44,705
Ciao mondo.

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

400
00:17:48,201 --> 00:17:49,420
Ah, io so quello che sta facendo.

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

402
00:17:49,920 --> 00:17:51,628
Quindi è leggendo
fino al primo spazio.

403
00:17:51,628 --> 00:17:55,680
Quindi cerchiamo di imbrogliare per un attimo e
Dico Volevo solo digitare qualcosa

404
00:17:55,680 --> 00:18:01,408
molto lungo come questo è una lunga frase
questo è uno, due, tre, quattro, cinque,

405
00:18:01,408 --> 00:18:04,420
sei, sette, otto, nove,
10, 11, 12, 13, 14, 15, 16.

406
00:18:04,420 --> 00:18:05,300
OK.

407
00:18:05,300 --> 00:18:07,600
Si tratta infatti di una lunga frase.

408
00:18:07,600 --> 00:18:10,710
Così questa frase è
più di 16 caratteri

409
00:18:10,710 --> 00:18:13,670
e così quando ho colpito Enter,
che cosa accadrà?

410
00:18:13,670 --> 00:18:16,940
Ebbene, in questo caso del
buffer di storia, avevo dichiarato

411
00:18:16,940 --> 00:18:22,190
in realtà essere una matrice
con 16 caratteri pronto a partire.

412
00:18:22,190 --> 00:18:27,426
Quindi uno, due, tre, quattro, cinque, sei,
sette, otto, 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
Così 16 personaggi, e ora, quando io
letto in qualcosa di simile a questo è un lungo

415
00:18:34,410 --> 00:18:43,950
frase, cosa sta andando accadere è
che ho intenzione di leggere in questo è una lunga

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

417
00:18:49,660 --> 00:18:52,270
>> Quindi questo è volutamente
una cosa negativa che ho

418
00:18:52,270 --> 00:18:55,060
continuare a scrivere al di là del
confini della mia matrice,

419
00:18:55,060 --> 00:18:56,660
oltre i confini della mia buffer.

420
00:18:56,660 --> 00:19:00,100
Potrei avere fortuna e il programma
continuerà a correre e non si preoccupano,

421
00:19:00,100 --> 00:19:03,450
ma in generale, questo
sarà davvero in crash il mio programma,

422
00:19:03,450 --> 00:19:06,440
e si tratta di un bug nel mio
codificare il momento faccio un passo

423
00:19:06,440 --> 00:19:08,576
oltre i confini
di tale matrice, perché io

424
00:19:08,576 --> 00:19:10,450
Non so se si tratta di
necessariamente andare a sbattere

425
00:19:10,450 --> 00:19:12,120
o se sto solo andando di avere fortuna.

426
00:19:12,120 --> 00:19:15,750
Quindi questo è problematico perché in
questo caso, non sembra funzionare

427
00:19:15,750 --> 00:19:20,931
e cerchiamo di sfidare il destino qui, anche se
l'IDE sembra tollerare un po '

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

429
00:19:21,430 --> 00:19:22,040
>> Ci siamo.

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

431
00:19:23,240 --> 00:19:26,470
Quindi io sono l'unico che può vedere questo.

432
00:19:26,470 --> 00:19:29,630
Così ho avuto un sacco di divertimento battitura
fuori una lunghissima frase reale

433
00:19:29,630 --> 00:19:32,800
che certamente superato
16 byte, perché io

434
00:19:32,800 --> 00:19:38,050
digitato in questo lungo multi-linea pazzo
frase, e poi notare ciò che è accaduto.

435
00:19:38,050 --> 00:19:41,110
Il programma ha tentato di stamparlo
e poi abbiamo preso un segmentation fault

436
00:19:41,110 --> 00:19:44,430
e difetti di segmentazione è quando
qualcosa di simile accade

437
00:19:44,430 --> 00:19:47,650
e il sistema operativo dice
no, non si può toccare quel ricordo.

438
00:19:47,650 --> 00:19:49,570
Stiamo andando a uccidere
il programma del tutto.

439
00:19:49,570 --> 00:19:51,180
>> Quindi questo sembra problematico.

440
00:19:51,180 --> 00:19:54,540
Ho migliorato il programma per cui
almeno avere qualche ricordo,

441
00:19:54,540 --> 00:19:58,000
ma questo sembra confinare
la funzione GetString per ottenere

442
00:19:58,000 --> 00:20:00,780
stringhe di qualche lunghezza finita 16.

443
00:20:00,780 --> 00:20:04,200
Quindi, se volete sostenere più a lungo
frasi di 16 caratteri,

444
00:20:04,200 --> 00:20:04,880
che fai?

445
00:20:04,880 --> 00:20:07,970
Beh, è ​​possibile aumentare la
dimensioni di questo buffer a 32

446
00:20:07,970 --> 00:20:09,190
o che sembra genere di breve.

447
00:20:09,190 --> 00:20:12,260
Perché non solo facciamo
essa 1.000 ma spingere indietro.

448
00:20:12,260 --> 00:20:17,100
Qual è la risposta intuitivamente di
semplicemente evitare questo problema rendendo

449
00:20:17,100 --> 00:20:20,660
il mio tampone più grande, come 1.000 caratteri?

450
00:20:20,660 --> 00:20:23,470
Con l'implementazione di GetString questo modo.

451
00:20:23,470 --> 00:20:27,130
Cosa c'è di buono o cattivo qui?

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

453
00:20:28,033 --> 00:20:30,574
PUBBLICO: Se si associa un sacco
di spazio e non ne fanno uso,

454
00:20:30,574 --> 00:20:33,500
allora non si può riallocare lo spazio.

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

456
00:20:34,500 --> 00:20:38,480
E 'uno spreco, in quanto se non lo fai
effettivamente bisogno 900 di quei byte

457
00:20:38,480 --> 00:20:41,057
ma stai chiedendo
1.000 in totale in ogni caso,

458
00:20:41,057 --> 00:20:44,140
si sta solo consumando più memoria su
il computer dell'utente che è necessario,

459
00:20:44,140 --> 00:20:45,740
e dopo tutto, alcuni
hai già incontrato

460
00:20:45,740 --> 00:20:47,620
nella vita che quando sei
esecuzione di un sacco di programmi

461
00:20:47,620 --> 00:20:50,470
e che stanno divorando grandi quantità di memoria,
questo può effettivamente influire sulle prestazioni

462
00:20:50,470 --> 00:20:52,220
e l'esperienza dell'utente
sul computer.

463
00:20:52,220 --> 00:20:56,090
Ecco, questo è una specie di soluzione di pigro,
di sicuro, e viceversa,

464
00:20:56,090 --> 00:21:00,140
non è solo uno spreco, quale problema
rimane ancora, anche se mi metto a tampone

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

466
00:21:02,100 --> 00:21:02,600
Sì?

467
00:21:02,600 --> 00:21:04,475
>> PUBBLICO: La stringa è di lunghezza 1.001.

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

469
00:21:05,350 --> 00:21:08,280
Se la stringa è di lunghezza 1.001,
si ha lo stesso identico problema,

470
00:21:08,280 --> 00:21:10,705
e il mio argomento, vorrei
solo poi ne fanno 2000,

471
00:21:10,705 --> 00:21:12,830
ma non si sa in
anticipo quanto grande dovrebbe essere,

472
00:21:12,830 --> 00:21:16,890
e tuttavia, devo compilare il mio programma
prima di lasciare la gente usa e scaricare

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

474
00:21:17,390 --> 00:21:21,490
Quindi questo è esattamente il tipo di
roba che i tentativi di libreria CS50

475
00:21:21,490 --> 00:21:24,750
per aiutarci con e faremo solo colpo d'occhio
ad alcuni dei implementazione sottostante

476
00:21:24,750 --> 00:21:29,790
qui, ma questo è CS50 punto C. Questo
è il file che è stato il CS50 IDE

477
00:21:29,790 --> 00:21:31,420
tutte queste settimane che hai utilizzato.

478
00:21:31,420 --> 00:21:34,280
E 'pre-compilato e hai
stati utilizzando automaticamente

479
00:21:34,280 --> 00:21:38,780
dalla natura di avere la
dash L bandiera CS50 con clangore,

480
00:21:38,780 --> 00:21:42,300
ma se ho scorrere verso il basso attraverso tutti
queste funzioni, ecco GetString,

481
00:21:42,300 --> 00:21:44,636
e solo per darvi un
assaggio di quello che sta succedendo,

482
00:21:44,636 --> 00:21:46,760
diamo un rapido sguardo a
la relativa complessità.

483
00:21:46,760 --> 00:21:48,870
Non è un super lunga
funzione, ma non l'abbiamo fatto

484
00:21:48,870 --> 00:21:52,530
deve pensare tutto dura circa
come fare per ottenere stringhe.

485
00:21:52,530 --> 00:21:55,660
>> Quindi, ecco il mio buffer e io
a quanto pare inizializzarla a null.

486
00:21:55,660 --> 00:21:57,990
Questo, naturalmente, è il
stessa cosa come char stelle,

487
00:21:57,990 --> 00:22:00,585
ma ho deciso di
attuazione della biblioteca CS50

488
00:22:00,585 --> 00:22:02,460
che se stiamo andando a
essere completamente dinamico,

489
00:22:02,460 --> 00:22:05,770
Non so in anticipo come di un grande
gli utenti di stringa stanno andando a voler ottenere.

490
00:22:05,770 --> 00:22:08,140
Quindi ho intenzione di iniziare a
con solo una stringa vuota

491
00:22:08,140 --> 00:22:11,507
e ho intenzione di costruire il più
memoria, come ho bisogno di adattare la stringa user

492
00:22:11,507 --> 00:22:13,340
e se non ho
abbastanza, ho intenzione di chiedere

493
00:22:13,340 --> 00:22:15,010
il sistema operativo per più memoria.

494
00:22:15,010 --> 00:22:17,510
Ho intenzione di spostare la loro corda
in un pezzo più grande di memoria

495
00:22:17,510 --> 00:22:21,847
e ho intenzione di rilasciare o liberare il
sufficientemente grande pezzo di memoria

496
00:22:21,847 --> 00:22:23,680
e stiamo solo andando
per fare questo in modo iterativo.

497
00:22:23,680 --> 00:22:25,570
>> Quindi una rapida occhiata,
qui è solo una variabile

498
00:22:25,570 --> 00:22:28,780
con cui ho intenzione di tenere traccia
della capacità del mio tampone.

499
00:22:28,780 --> 00:22:30,071
Il numero di byte posso andare bene?

500
00:22:30,071 --> 00:22:32,070
Ecco una variabile n con
che ho intenzione di continuare a

501
00:22:32,070 --> 00:22:36,200
traccia di quanti byte sono in realtà in
il buffer o che l'utente ha digitato.

502
00:22:36,200 --> 00:22:39,900
Se non avete visto questo prima,
può indicare che una variabile come un int

503
00:22:39,900 --> 00:22:46,370
non è firmato, che come suggerisce il nome,
significa che è non negativo, e perché avrebbe fatto

504
00:22:46,370 --> 00:22:50,590
Ho sempre voglia di preoccuparsi specificando
che un int non è solo un int,

505
00:22:50,590 --> 00:22:52,540
ma è un unsigned int?

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

507
00:22:55,064 --> 00:22:56,355
Che cosa significa il [incomprensibile] significa?

508
00:22:56,355 --> 00:22:58,910
>> PUBBLICO: Si descrive un importo
di memoria che può essere [incomprensibile].

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

510
00:22:59,660 --> 00:23:03,710
Quindi, se io dico senza segno, questo è in realtà
dando un bit di memoria aggiuntiva

511
00:23:03,710 --> 00:23:07,440
e sembra sorta di sciocco, ma se si
avere un bit di memoria aggiuntiva, che

512
00:23:07,440 --> 00:23:09,940
significa avere il doppio
I valori si possono rappresentare,

513
00:23:09,940 --> 00:23:11,570
perché può essere 0 o 1.

514
00:23:11,570 --> 00:23:14,660
Così per impostazione predefinita, un int può essere più o meno
negativo 2 miliardi di tutta la strada

515
00:23:14,660 --> 00:23:16,030
fino a 2 miliardi di positivo.

516
00:23:16,030 --> 00:23:18,540
Questi sono grandi cucine, ma
è ancora un po 'uno spreco

517
00:23:18,540 --> 00:23:21,280
se vi interessa soltanto
dimensioni, che solo intuitivamente

518
00:23:21,280 --> 00:23:24,620
dovrebbe essere non negativo o
positivo o 0, beh, allora,

519
00:23:24,620 --> 00:23:28,884
perché stai sprecando 2 miliardi
valori possibili per i numeri negativi

520
00:23:28,884 --> 00:23:30,300
se non si è mai intenzione di usarli?

521
00:23:30,300 --> 00:23:35,350
Così dicendo non firmato, ora il mio int possibile
essere compreso tra 0 e circa 4 miliardi.

522
00:23:35,350 --> 00:23:39,280
>> Quindi, ecco solo un int C per motivi
noi non entreremo in proprio ora come

523
00:23:39,280 --> 00:23:42,280
per questo che è un int invece
di un carattere, ma qui è

524
00:23:42,280 --> 00:23:44,630
il senso di quello che sta succedendo
, e alcuni di voi

525
00:23:44,630 --> 00:23:48,340
potrebbe utilizzare, per esempio, la
funzione fgetc anche in PSet quattro

526
00:23:48,340 --> 00:23:51,580
o successivamente, lo vedremo
di nuovo in cinque set problema,

527
00:23:51,580 --> 00:23:55,410
fgetc è bello perché, come il nome
tipo di, una sorta di arcanamente suggerisce,

528
00:23:55,410 --> 00:23:57,940
è una funzione che
ottiene un personaggio e così,

529
00:23:57,940 --> 00:24:00,690
cosa c'è di fondamentalmente diverso
su quello che stiamo facendo in GetString

530
00:24:00,690 --> 00:24:03,110
è che non stiamo usando
scanf nello stesso modo.

531
00:24:03,110 --> 00:24:07,550
Stiamo solo strisciando lungo passo-passo
su tutto ciò che l'utente ha digitato,

532
00:24:07,550 --> 00:24:10,970
perché possiamo sempre attribuire uno
char, e in modo che possiamo sempre tranquillamente

533
00:24:10,970 --> 00:24:15,599
guardare uno char alla volta, e
la magia comincia ad accadere qui.

534
00:24:15,599 --> 00:24:17,890
Io vado a scorrere verso il basso per
Al centro di questa funzione

535
00:24:17,890 --> 00:24:20,360
solo introdurre brevemente questa funzione.

536
00:24:20,360 --> 00:24:22,670
Proprio come c'è un
la funzione malloc, c'è

537
00:24:22,670 --> 00:24:27,740
una funzione realloc dove realloc
consente di riallocare un pezzo di memoria

538
00:24:27,740 --> 00:24:29,570
e renderlo più grande o più piccolo.

539
00:24:29,570 --> 00:24:33,060
Così lunga storia breve e con
un gesto della mano per oggi,

540
00:24:33,060 --> 00:24:35,620
sapere che ciò che GetString
sta facendo è una specie

541
00:24:35,620 --> 00:24:39,720
di magicamente crescita o
riducendo il buffer come utente

542
00:24:39,720 --> 00:24:41,440
tipi della sua corda.

543
00:24:41,440 --> 00:24:43,962
>> Quindi, se l'utente digita una
breve stringa, questo codice

544
00:24:43,962 --> 00:24:45,920
alloca solamente abbastanza
memoria per adattarsi alla stringa.

545
00:24:45,920 --> 00:24:48,086
Se l'utente tiene digitazione
come ho fatto ancora e ancora

546
00:24:48,086 --> 00:24:50,330
e ancora, bene, se la
Buffer di questo grande inizialmente

547
00:24:50,330 --> 00:24:53,310
e il programma realizza, a
aspetta un attimo, sono fuori dello spazio,

548
00:24:53,310 --> 00:24:55,410
sta andando a raddoppiare
la dimensione del buffer

549
00:24:55,410 --> 00:24:59,110
e quindi il doppio della dimensione del buffer
e il codice che fa il raddoppio,

550
00:24:59,110 --> 00:25:03,170
se guardiamo qui, è
solo questo intelligente one-liner.

551
00:25:03,170 --> 00:25:06,830
Si potrebbe non aver visto questa sintassi
prima, ma se dici stella è uguale,

552
00:25:06,830 --> 00:25:10,470
questa è la stessa cosa
dicendo volte di capacità 2.

553
00:25:10,470 --> 00:25:13,390
Quindi continua a raddoppiare
la capacità del buffer

554
00:25:13,390 --> 00:25:17,480
e poi dire realloc per dare
sé che molto più memoria.

555
00:25:17,480 --> 00:25:19,720
>> Ora, come una digressione, ci
sono altre funzioni in qui

556
00:25:19,720 --> 00:25:23,680
che non vedremo nei dettagli
altro che mostrare a GetInt,

557
00:25:23,680 --> 00:25:26,150
usiamo GetString in GetInt.

558
00:25:26,150 --> 00:25:28,192
Controlliamo che non è
null, che, ricordo,

559
00:25:28,192 --> 00:25:30,400
è il valore speciale che
significa qualcosa è andato storto.

560
00:25:30,400 --> 00:25:31,233
Siamo esaurito la memoria.

561
00:25:31,233 --> 00:25:32,310
Meglio controllare per questo.

562
00:25:32,310 --> 00:25:33,710
E torniamo un valore sentinella.

563
00:25:33,710 --> 00:25:37,850
Ma io rimetto ai commenti per quanto riguarda
perché e poi usiamo questo cugino di scanf

564
00:25:37,850 --> 00:25:42,100
chiamò sscanf e si scopre
che scanf sscanf, o una stringa,

565
00:25:42,100 --> 00:25:45,310
consente di dare un'occhiata alla linea che
l'utente ha digitato e consentono di

566
00:25:45,310 --> 00:25:49,610
analizzare essenzialmente e cosa sto
facendo qui è che sto dicendo sscanf,

567
00:25:49,610 --> 00:25:54,440
analizzare ciò che l'utente ha
digitato e assicurarsi% i,

568
00:25:54,440 --> 00:25:59,250
vi è un numero intero, e noi non lo farà
entrare oggi esattamente il motivo per cui c'è anche

569
00:25:59,250 --> 00:26:03,760
un% c qui, ma che in poche parole permette
di rilevare se l'utente ha digitato

570
00:26:03,760 --> 00:26:06,050
in qualcosa falso dopo il numero.

571
00:26:06,050 --> 00:26:11,766
Quindi la ragione che GetInt e GetString
dirvi di riprovare, riprovare, riprovare

572
00:26:11,766 --> 00:26:13,640
è causa di tutti
che codice che abbiamo scritto,

573
00:26:13,640 --> 00:26:17,900
è una specie di guardare l'input dell'utente
nel fare in modo che sia interamente numerico

574
00:26:17,900 --> 00:26:21,700
o si tratta di un vero e proprio galleggiamento
valore del punto o simili,

575
00:26:21,700 --> 00:26:24,233
a seconda che valore
funzione che si sta utilizzando.

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

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

578
00:26:25,710 --> 00:26:27,592
Quello era un boccone
ma il punto qui è

579
00:26:27,592 --> 00:26:29,550
che il motivo per cui abbiamo avuto
quelle ruote di formazione su

580
00:26:29,550 --> 00:26:32,880
perché è al livello più basso,
ci sono solo tante cose che

581
00:26:32,880 --> 00:26:35,674
può andare male che volevamo
di gestire preventivamente

582
00:26:35,674 --> 00:26:38,090
quelle cose certamente in
prime settimane della classe,

583
00:26:38,090 --> 00:26:42,230
ma ora con PSet quattro e cinque e PSet
là si vede che è più unto

584
00:26:42,230 --> 00:26:45,570
voi, ma anche sei più capace
di risolvere questo tipo di problemi

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

586
00:26:47,180 --> 00:26:51,770
Hai domande su GetString o GetInt?

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

588
00:26:52,630 --> 00:26:55,130
>> PUBBLICO: Perché si raddoppiare
la capacità del buffer

589
00:26:55,130 --> 00:26:57,630
piuttosto che solo l'aumento
facendo l'importo esatto?

590
00:26:57,630 --> 00:26:58,100
>> DAVID MALAN: Bella domanda.

591
00:26:58,100 --> 00:27:00,474
Perché dovremmo raddoppiare la capacità
del buffer in opposizione

592
00:27:00,474 --> 00:27:02,800
ad appena aumentandola
da qualche valore costante?

593
00:27:02,800 --> 00:27:03,900
E 'stata una decisione di progettazione.

594
00:27:03,900 --> 00:27:08,590
Abbiamo appena deciso che in quanto tende a
essere un po 'costoso di tempo-saggio di chiedere

595
00:27:08,590 --> 00:27:10,440
il sistema operativo
per la memoria, non abbiamo

596
00:27:10,440 --> 00:27:13,210
vuole finire per ottenere in
una situazione per i grandi archi

597
00:27:13,210 --> 00:27:14,960
che abbiamo chiesto
ripetutamente l'OS

598
00:27:14,960 --> 00:27:17,500
e ancora e ancora in
rapida successione per la memoria.

599
00:27:17,500 --> 00:27:20,387
Così abbiamo semplicemente deciso, un po '
arbitrariamente ma speriamo ragionevolmente,

600
00:27:20,387 --> 00:27:22,720
che, si sa che cosa, cerchiamo di
cercare di andare avanti di noi stessi

601
00:27:22,720 --> 00:27:25,520
e tenere solo il raddoppio in modo che
minimizziamo la quantità di volte

602
00:27:25,520 --> 00:27:29,010
dobbiamo chiamare malloc o
realloc, ma un giudizio totale

603
00:27:29,010 --> 00:27:31,820
chiamare in assenza di sapere
ciò che gli utenti potrebbero voler digitare.

604
00:27:31,820 --> 00:27:33,600
Entrambi i modi possono essere discutibili.

605
00:27:33,600 --> 00:27:35,430
Probabilmente buona.

606
00:27:35,430 --> 00:27:39,240
>> Quindi, diamo un'occhiata a un paio
di altri effetti collaterali di memoria,

607
00:27:39,240 --> 00:27:41,610
cose che possono andare male
e strumenti che è possibile

608
00:27:41,610 --> 00:27:43,880
usare per la cattura di questi tipi di errori.

609
00:27:43,880 --> 00:27:47,800
Si scopre tutto di te, anche se
check50 non è detto che il più,

610
00:27:47,800 --> 00:27:50,050
hanno scritto buggy
codice dalla settimana uno,

611
00:27:50,050 --> 00:27:53,630
anche se tutti i test sono check50
passò, e anche se tu e il tuo TF

612
00:27:53,630 --> 00:27:56,010
sono super sicuri che
il tuo codice funziona come previsto.

613
00:27:56,010 --> 00:27:59,190
Il tuo codice è stato buggy o
viziato in che tutti voi,

614
00:27:59,190 --> 00:28:02,540
utilizzando la libreria CS50,
sono state perdite di memoria.

615
00:28:02,540 --> 00:28:06,040
Sei stato chiedendo il sistema operativo
per la memoria nella maggior parte dei programmi

616
00:28:06,040 --> 00:28:08,850
che hai scritto, ma hai
in realtà mai dato indietro.

617
00:28:08,850 --> 00:28:12,110
Hai chiamato GetString
e GetInt e getFloat,

618
00:28:12,110 --> 00:28:15,270
ma con GetString, hai
mai chiamato unGetString o dare

619
00:28:15,270 --> 00:28:19,890
Posteriore della stringa o simili, ma abbiamo visto
che GetString fa allocare memoria

620
00:28:19,890 --> 00:28:22,810
attraverso malloc o questo
la funzione realloc, che è solo

621
00:28:22,810 --> 00:28:25,670
molto simile nello spirito,
e tuttavia, siamo stati

622
00:28:25,670 --> 00:28:28,629
chiedendo il sistema operativo
memoria e la memoria ripetutamente

623
00:28:28,629 --> 00:28:29,670
ma non mollare mai indietro.

624
00:28:29,670 --> 00:28:33,550
>> Ora, come una digressione, si scopre che
quando un programma viene chiuso, tutta la memoria

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

626
00:28:34,870 --> 00:28:36,150
Quindi non è stato un grande affare.

627
00:28:36,150 --> 00:28:38,590
Non sta andando a rompere il
IDE o rallentare le cose,

628
00:28:38,590 --> 00:28:40,670
ma quando i programmi fanno
generalmente una perdita di memoria

629
00:28:40,670 --> 00:28:42,170
e sono in esecuzione per molto tempo.

630
00:28:42,170 --> 00:28:45,640
Se hai mai visto il piccolo stupido
pallone da spiaggia in Mac OS o la clessidra

631
00:28:45,640 --> 00:28:51,160
su Windows dove è una specie di
rallentando o pensare o pensando

632
00:28:51,160 --> 00:28:53,770
o semplicemente inizia davvero
a rallentare a passo d'uomo,

633
00:28:53,770 --> 00:28:56,960
che molto probabilmente potrebbe essere
il risultato di una perdita di memoria.

634
00:28:56,960 --> 00:28:59,970
I programmatori che hanno scritto
il software che si sta utilizzando

635
00:28:59,970 --> 00:29:03,570
richiedere al sistema operativo per la memoria
ogni pochi minuti, ogni ora.

636
00:29:03,570 --> 00:29:05,570
Ma se si sta eseguendo il
software, anche se è

637
00:29:05,570 --> 00:29:08,680
minimizzato nel vostro computer
per ore o giorni e giorni,

638
00:29:08,680 --> 00:29:11,980
si potrebbe chiedere di più e di più
memoria e mai effettivamente usarlo

639
00:29:11,980 --> 00:29:15,180
e così il vostro codice potrebbe essere, o
programmi potrebbero essere perdite di memoria,

640
00:29:15,180 --> 00:29:18,350
e se si inizia a perdere la memoria,
c'è meno memoria per altri programmi,

641
00:29:18,350 --> 00:29:21,220
e l'effetto è quello
rallenta tutto giù.

642
00:29:21,220 --> 00:29:23,600
>> Ora, questo è di gran lunga uno
i programmi più atroci

643
00:29:23,600 --> 00:29:26,350
avrete opportunità
per l'esecuzione in CS50 misura

644
00:29:26,350 --> 00:29:31,650
come la sua uscita è ancora più esoterico di
clang di effettuare o di o del comando

645
00:29:31,650 --> 00:29:35,930
programmi da linea che abbiamo eseguito prima ma
per fortuna, all'interno della sua uscita

646
00:29:35,930 --> 00:29:39,810
è alcuni suggerimenti utili che super-
sarà utile sia per PSet quattro

647
00:29:39,810 --> 00:29:41,510
o certamente PConfigurare cinque.

648
00:29:41,510 --> 00:29:44,250
Così Valgrind è uno strumento
che può essere utilizzato per guardare

649
00:29:44,250 --> 00:29:46,930
per perdite di memoria nel programma.

650
00:29:46,930 --> 00:29:48,570
E 'relativamente semplice da eseguire.

651
00:29:48,570 --> 00:29:51,420
Si esegue valgrind e poi, anche
anche se è un po 'prolisso,

652
00:29:51,420 --> 00:29:54,440
dash controllo delle perdite dash
è uguale a pieno, e poi dot

653
00:29:54,440 --> 00:29:56,320
slash il nome del programma.

654
00:29:56,320 --> 00:30:00,010
Così valgrind poi eseguire il programma
e alla fine del programma

655
00:30:00,010 --> 00:30:02,240
esecuzione prima si chiude e
ti dà un altro prompt,

656
00:30:02,240 --> 00:30:04,980
sta andando ad analizzare il tuo
programma mentre è stato in esecuzione

657
00:30:04,980 --> 00:30:07,740
e dire hai fatto Hai perdite
qualsiasi memoria e meglio ancora,

658
00:30:07,740 --> 00:30:10,610
hai toccato memoria
non appartengono a voi?

659
00:30:10,610 --> 00:30:13,700
Non può catturare tutto, ma è
abbastanza bravo a catturare la maggior parte delle cose.

660
00:30:13,700 --> 00:30:19,700
>> Quindi, ecco un esempio di mia hanno percorso
questo programma, che hanno percorso valgrind,

661
00:30:19,700 --> 00:30:21,470
su un programma chiamato
la memoria, e ho intenzione

662
00:30:21,470 --> 00:30:24,730
per evidenziare le linee che sono
in ultima analisi, di interesse per noi.

663
00:30:24,730 --> 00:30:27,690
Quindi c'è ancora più distrazioni
che ho cancellato dalla diapositiva.

664
00:30:27,690 --> 00:30:30,930
Ma facciamo solo vedere cosa questo
programma è in grado di dirci.

665
00:30:30,930 --> 00:30:34,800
E 'in grado di dirci cose
come scrive invalido di dimensioni 4.

666
00:30:34,800 --> 00:30:38,020
In altre parole, se si tocca la memoria,
in particolare 4 byte di memoria

667
00:30:38,020 --> 00:30:40,350
che non si dovrebbero avere,
Valgrind posso dire che.

668
00:30:40,350 --> 00:30:41,660
Scrittura non valido di dimensioni 4.

669
00:30:41,660 --> 00:30:43,640
Hai toccato quattro byte
che non si deve avere.

670
00:30:43,640 --> 00:30:44,840
Dove l'hai fatto?

671
00:30:44,840 --> 00:30:45,900
Questa è la bellezza.

672
00:30:45,900 --> 00:30:50,000
Dot memoria c linea 21 è dove si
incasinato ed è per questo che è utile.

673
00:30:50,000 --> 00:30:53,410
Proprio come GDB, può aiutare
si punta a l'errore effettivo.

674
00:30:53,410 --> 00:30:57,170
>> Ora, questo è un po 'più
verbose, se non confusione.

675
00:30:57,170 --> 00:31:01,307
40 byte in 1 blocchi sono sicuramente
perso in perdita record 1 di 1.

676
00:31:01,307 --> 00:31:02,140
Che cosa significa?

677
00:31:02,140 --> 00:31:05,920
Beh, significa solo che hai chiesto per
40 byte e hai mai dato indietro.

678
00:31:05,920 --> 00:31:08,930
Hai chiamato malloc o hai chiamato
GetString e il sistema operativo

679
00:31:08,930 --> 00:31:12,450
voi 40 byte, ma ti ha dato mai
liberato o rilasciato quella memoria,

680
00:31:12,450 --> 00:31:15,400
e ad essere onesti, non abbiamo mai mostriamo
come dare indietro la memoria.

681
00:31:15,400 --> 00:31:17,910
Si scopre che c'è un super
semplice funzione chiamata gratuita.

682
00:31:17,910 --> 00:31:21,170
Prende un argomento, la cosa
si vuole liberare o restituire,

683
00:31:21,170 --> 00:31:23,430
ma 40 byte, a quanto pare,
in questo programma

684
00:31:23,430 --> 00:31:27,300
sono stati persi in linea
20 della memoria dot c.

685
00:31:27,300 --> 00:31:28,650
>> Quindi cerchiamo di vedere questo programma.

686
00:31:28,650 --> 00:31:31,020
E 'super inutile.

687
00:31:31,020 --> 00:31:33,980
Dimostra solo
questo particolare errore.

688
00:31:33,980 --> 00:31:34,920
Quindi, diamo uno sguardo.

689
00:31:34,920 --> 00:31:39,920
Ecco principali e principali, avviso, chiamate
una funzione chiamata restituisce fe poi.

690
00:31:39,920 --> 00:31:41,550
Quindi non tutto ciò che interessante.

691
00:31:41,550 --> 00:31:42,664
Cosa fa f fare?

692
00:31:42,664 --> 00:31:44,330
Notate Non ho disturbato con un prototipo.

693
00:31:44,330 --> 00:31:46,520
Volevo mantenere il codice
come minimo possibile.

694
00:31:46,520 --> 00:31:49,530
Così ho messo sopra f principale e
va bene, certo,

695
00:31:49,530 --> 00:31:51,500
per i programmi brevi come questo.

696
00:31:51,500 --> 00:31:56,910
Quindi f non restituisce nulla e fa
Non prendere nulla, ma lo fa fare questo.

697
00:31:56,910 --> 00:31:59,620
Dichiara, molto simile
nell'esempio Binky,

698
00:31:59,620 --> 00:32:02,682
un puntatore chiamato x che sta andando
per memorizzare l'indirizzo di un int.

699
00:32:02,682 --> 00:32:03,890
Ecco, questo è il lato sinistro.

700
00:32:03,890 --> 00:32:07,230
In inglese, qual è la
lato destro facendo?

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

702
00:32:09,770 --> 00:32:13,665
Che cosa sta facendo questo per noi?

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

704
00:32:14,651 --> 00:32:16,623
>> PUBBLICO: [incomprensibile]
volte la dimensione di un int

705
00:32:16,623 --> 00:32:19,175
che è 10 volte che [incomprensibile]

706
00:32:19,175 --> 00:32:20,800
DAVID MALAN: Buon e vorrei riassumere.

707
00:32:20,800 --> 00:32:25,480
Così allocare spazio sufficiente per 10 numeri interi
o 10, qual è la dimensione di un int,

708
00:32:25,480 --> 00:32:29,340
è quattro byte, quindi 10 volte 4 è
40, in modo che a destra che ho

709
00:32:29,340 --> 00:32:33,930
evidenziata è dammi 40 byte e
memorizzare l'indirizzo del primo byte

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

711
00:32:34,940 --> 00:32:38,380
Ed ora, infine, e qui è dove
questo programma è bacato, che cosa è

712
00:32:38,380 --> 00:32:41,540
sbagliato con la linea 21, basato su questa logica?

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

714
00:32:45,197 --> 00:32:46,280
Cosa c'è di sbagliato con la linea 21?

715
00:32:46,280 --> 00:32:46,780
Sì?

716
00:32:46,780 --> 00:32:49,550
PUBBLICO: non è possibile
indice in x [incomprensibile].

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

718
00:32:50,300 --> 00:32:52,270
Non dovrei indice in x del genere.

719
00:32:52,270 --> 00:32:53,850
Così sintatticamente, va bene.

720
00:32:53,850 --> 00:32:56,990
Il bello è, proprio come si
può trattare il nome di un array

721
00:32:56,990 --> 00:33:01,080
come se fosse un puntatore, similmente
si può trattare di un puntatore come se fosse

722
00:33:01,080 --> 00:33:06,425
un array, e quindi posso sintatticamente
dire x staffa qualcosa, x staffa i,

723
00:33:06,425 --> 00:33:07,800
ma il 10 è problematica.

724
00:33:07,800 --> 00:33:09,096
Perché?

725
00:33:09,096 --> 00:33:10,910
>> PUBBLICO: Perché non è dentro.

726
00:33:10,910 --> 00:33:12,390
>> DAVID MALAN: Non è
dentro quel pezzo di memoria.

727
00:33:12,390 --> 00:33:15,306
Qual è il valore più grande che dovrebbe
essere messa in quelle parentesi quadre?

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

729
00:33:16,870 --> 00:33:18,160
A causa dello zero indicizzazione.

730
00:33:18,160 --> 00:33:20,190
Così da 0 a 9 andrebbe bene.

731
00:33:20,190 --> 00:33:23,960
Staffa 10 non è buono e
ma, ricordare però, ogni volta

732
00:33:23,960 --> 00:33:27,017
Mi sembra di provare a fare CS50 IDE
incidente digitando valori falsi,

733
00:33:27,017 --> 00:33:29,100
non sempre collabora,
e anzi, spesso

734
00:33:29,100 --> 00:33:31,460
fortunato solo perché il
sistema operativo non lo fa

735
00:33:31,460 --> 00:33:35,467
notare che si sempre leggermente
passare qualche pezzo di memoria,

736
00:33:35,467 --> 00:33:38,300
perché Sei già entro tecnicamente
proprio segmento, ma più su quello

737
00:33:38,300 --> 00:33:40,940
in una classe di sistemi operativi,
e così qualcosa di simile

738
00:33:40,940 --> 00:33:43,000
potrebbe facilmente passare inosservate.

739
00:33:43,000 --> 00:33:48,120
Il vostro programma è mai andare a sbattere
costantemente ma forse una volta ogni tanto.

740
00:33:48,120 --> 00:33:50,610
>> E così proviamo valgrind
su questo, ed ecco

741
00:33:50,610 --> 00:33:52,870
dove ci arriveremo sopraffatti
dall'uscita momentaneamente.

742
00:33:52,870 --> 00:34:00,810
Quindi, fare memoria controllo delle perdite valgrind
uguale pieno di memoria puntino barra.

743
00:34:00,810 --> 00:34:03,040
Ed ecco perché lo prometto
questo sarebbe sopraffare.

744
00:34:03,040 --> 00:34:05,700
Ecco cosa valgrind, ecco cosa
un programmatore, alcuni anni fa-

745
00:34:05,700 --> 00:34:08,469
ha deciso che sarebbe una buona idea
per l'uscita per assomigliare.

746
00:34:08,469 --> 00:34:09,750
Quindi cerchiamo di dare un senso di questo.

747
00:34:09,750 --> 00:34:13,120
Quindi tutto il percorso sulla mano sinistra
lato per nessuna buona ragione

748
00:34:13,120 --> 00:34:16,620
è l'ID di processo del programma
abbiamo appena corriamo, l'identificatore univoco

749
00:34:16,620 --> 00:34:18,030
per il programma abbiamo appena finito.

750
00:34:18,030 --> 00:34:19,738
Abbiamo eliminato che dal
la slitta, ma ci

751
00:34:19,738 --> 00:34:22,190
alcune informazioni utili qui.

752
00:34:22,190 --> 00:34:24,684
>> Facciamo scorrere fino alla cima.

753
00:34:24,684 --> 00:34:25,600
Ecco dove abbiamo cominciato.

754
00:34:25,600 --> 00:34:27,040
Quindi non è più di tanto l'uscita.

755
00:34:27,040 --> 00:34:30,429
Ecco che in scrittura non valida
di dimensioni 4 sulla linea 21.

756
00:34:30,429 --> 00:34:31,760
Ebbene, qual era la linea 21?

757
00:34:31,760 --> 00:34:34,500
Linea 21 era esattamente
questo e ha senso

758
00:34:34,500 --> 00:34:37,290
che sono in validamente
scrivere 4 byte perché io sono

759
00:34:37,290 --> 00:34:40,389
cercando di mettere questo intero,
che potrebbe essere qualsiasi cosa,

760
00:34:40,389 --> 00:34:42,370
succede solo per essere
pari a zero, ma sto cercando

761
00:34:42,370 --> 00:34:44,940
per dirla in una posizione
che non appartiene a me.

762
00:34:44,940 --> 00:34:50,900
Inoltre, quaggiù, 40 byte in uno
blocchi sono definitivamente persi nel record 1.

763
00:34:50,900 --> 00:34:56,500
Questo perché quando chiamo malloc
qui, non ho mai realmente liberare la memoria.

764
00:34:56,500 --> 00:34:58,140
>> Quindi, come possiamo risolvere questo problema?

765
00:34:58,140 --> 00:35:02,970
Lasciami andare avanti ed essere un po 'più sicuro
e fare 9 lì e mi lasciare qui gratis x.

766
00:35:02,970 --> 00:35:04,820
Questa è la nuova funzione per oggi.

767
00:35:04,820 --> 00:35:11,520
Se ora eseguire di nuovo fare puntino memoria barra,
corriamo valgrind nuovo su di esso,

768
00:35:11,520 --> 00:35:14,990
massimizzare la mia finestra e premere Invio.

769
00:35:14,990 --> 00:35:16,900
Ora, va bene.

770
00:35:16,900 --> 00:35:19,590
Seppelliscono la buona notizia
in tutta questa uscita.

771
00:35:19,590 --> 00:35:20,810
Tutti i blocchi heap erano liberi.

772
00:35:20,810 --> 00:35:23,604
Torneremo a quello che il cumulo
è, ma perdite sono possibili.

773
00:35:23,604 --> 00:35:25,520
Quindi questo è solo un altro
strumento per il vostro kit di attrezzi

774
00:35:25,520 --> 00:35:30,220
con la quale si può iniziare a
ora trovare gli errori del genere.

775
00:35:30,220 --> 00:35:34,532
>> Ma vediamo cosa
più può sbagliare.

776
00:35:34,532 --> 00:35:38,890
Diamo ora a transizione
effettivamente risolvere un problema.

777
00:35:38,890 --> 00:35:42,440
Per inciso, se questo sarà alleviare un
po 'di confusione o di tensione,

778
00:35:42,440 --> 00:35:43,430
questo è ora divertente.

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

780
00:35:46,400 --> 00:35:46,900
Già.

781
00:35:46,900 --> 00:35:49,040
Questo è abbastanza buono.

782
00:35:49,040 --> 00:35:50,890
Poiché i puntatori sono
indirizzi e indirizzi

783
00:35:50,890 --> 00:35:53,098
sono generalmente per convenzione
scritto con esadecimale.

784
00:35:53,098 --> 00:35:54,650
Ah, ah, questo è divertente ora.

785
00:35:54,650 --> 00:35:58,390
Comunque, quindi cerchiamo di ora
in realtà risolvere un problema.

786
00:35:58,390 --> 00:36:00,840
Questo è stato eccellente,
super-basso livello finora,

787
00:36:00,840 --> 00:36:03,950
e possiamo effettivamente fare utili
le cose con questi dettagli di basso livello.

788
00:36:03,950 --> 00:36:06,710
>> Così abbiamo introdotto un paio di settimane
fa l'idea di un array.

789
00:36:06,710 --> 00:36:09,177
Un array era bello perché
è difficile per ripulire il nostro codice

790
00:36:09,177 --> 00:36:11,760
perché se volevamo scrivere un
programma con più studenti

791
00:36:11,760 --> 00:36:15,270
o più nomi e case e
dormitori e collegi e tutto questo,

792
00:36:15,270 --> 00:36:19,430
abbiamo potuto conservare tutto più
pulito all'interno di una matrice.

793
00:36:19,430 --> 00:36:23,039
Ma proporre uno svantaggio
di un array finora.

794
00:36:23,039 --> 00:36:26,080
Anche se non hai sofferto da te
in un programma, solo per istinto,

795
00:36:26,080 --> 00:36:30,870
ciò che è una brutta cosa
su un array, forse?

796
00:36:30,870 --> 00:36:32,337
Ho sentito alcuni mormorii.

797
00:36:32,337 --> 00:36:34,170
PUBBLICO: E 'difficile
per modificare le dimensioni.

798
00:36:34,170 --> 00:36:36,128
DAVID MALAN: E 'difficile
per modificare le dimensioni.

799
00:36:36,128 --> 00:36:38,660
Non è possibile modificare le dimensioni
di una matrice, infatti, di per sé

800
00:36:38,660 --> 00:36:43,040
in C. È possibile assegnare un altro array,
spostare tutto da quello vecchio

801
00:36:43,040 --> 00:36:45,380
nel nuovo, e ora
avere un po 'di spazio in più,

802
00:36:45,380 --> 00:36:47,469
ma non è come un
linguaggio come Java o Python

803
00:36:47,469 --> 00:36:49,760
o un qualsiasi numero di altri
lingue con le quali alcuni di voi

804
00:36:49,760 --> 00:36:52,070
potrebbe essere familiare in cui si
può solo continuare ad aggiungere le cose

805
00:36:52,070 --> 00:36:53,930
nausea alla fine di un array.

806
00:36:53,930 --> 00:36:57,880
Quando si dispone di una serie di
dimensioni 6, che è la sua dimensione,

807
00:36:57,880 --> 00:37:01,970
e così tanto come l'idea precedente
avente un buffer di una certa dimensione,

808
00:37:01,970 --> 00:37:05,940
dovete indovinare fuori dal cancello
che formato voi volete che sia?

809
00:37:05,940 --> 00:37:07,880
Se si indovina troppo grande,
stai sprecando spazio.

810
00:37:07,880 --> 00:37:10,950
Se si indovina troppo piccolo, si
non può memorizzare i dati, almeno

811
00:37:10,950 --> 00:37:12,940
senza un lavoro molto di più.

812
00:37:12,940 --> 00:37:18,180
>> Così oggi, grazie a puntatori, possiamo
iniziare a cucire insieme la nostra personalizzato

813
00:37:18,180 --> 00:37:20,989
strutture di dati, ed in
Infatti, qui è qualcosa

814
00:37:20,989 --> 00:37:23,030
che sembra un po 'di più
criptico a prima vista,

815
00:37:23,030 --> 00:37:26,440
ma questo è ciò che chiameremo un collegato
lista, e il suo nome tipo di sintetizza

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

817
00:37:26,940 --> 00:37:29,550
Si tratta di una lista di numeri, o in
questo caso, un elenco di numeri,

818
00:37:29,550 --> 00:37:33,480
ma potrebbe essere un elenco di nulla, ma
è collegato insieme per mezzo di frecce,

819
00:37:33,480 --> 00:37:36,380
e basta prendere una supposizione
con quale tecnica

820
00:37:36,380 --> 00:37:38,310
abbiamo intenzione di essere in grado
a cucire insieme,

821
00:37:38,310 --> 00:37:42,540
una specie di popcorn con un filo,
una legata elenca rettangoli qui?

822
00:37:42,540 --> 00:37:43,936
I suoi numeri?

823
00:37:43,936 --> 00:37:45,560
Qual è la caratteristica del linguaggio di base?

824
00:37:45,560 --> 00:37:46,350
>> PUBBLICO: Un puntatore.

825
00:37:46,350 --> 00:37:47,308
>> DAVID MALAN: Un puntatore.

826
00:37:47,308 --> 00:37:51,700
Così ognuno di questi rappresenta frecce qui
un puntatore o semplicemente un indirizzo.

827
00:37:51,700 --> 00:37:54,590
Quindi, in altre parole, se voglio
per memorizzare un elenco di numeri,

828
00:37:54,590 --> 00:37:59,040
Non posso conservarla se voglio
la capacità di crescere e ridursi

829
00:37:59,040 --> 00:38:00,990
la mia struttura dati in un array.

830
00:38:00,990 --> 00:38:03,000
Così ho bisogno di avere un po '
più raffinatezza,

831
00:38:03,000 --> 00:38:05,720
a meno di notare che questo
foto tipo di suggerisce

832
00:38:05,720 --> 00:38:08,650
che se hai appena avuto piccoli fili
collegando tutto insieme,

833
00:38:08,650 --> 00:38:13,100
Probabilmente non è così difficile fare spazio
tra due di detti rettangoli

834
00:38:13,100 --> 00:38:16,750
o due di quei nodi, come inizieremo
li chiama, messo in un nuovo nodo,

835
00:38:16,750 --> 00:38:19,547
e poi con qualche nuovo thread, solo
fosso i tre nodi insieme,

836
00:38:19,547 --> 00:38:22,880
il primo, l'ultimo, e quello
che appena inserito in mezzo.

837
00:38:22,880 --> 00:38:26,000
>> E in effetti una lista collegata,
a differenza di una matrice, è dinamico.

838
00:38:26,000 --> 00:38:27,840
Si può crescere e può
compattare e non fare

839
00:38:27,840 --> 00:38:32,434
devono sapere o di assistenza in anticipo come
molti dati che si sta andando ad essere l'archiviazione,

840
00:38:32,434 --> 00:38:35,600
ma si scopre che dobbiamo essere un po '
attenti a come implementare questa.

841
00:38:35,600 --> 00:38:39,070
Quindi, prima prendiamo in considerazione il modo in cui implementiamo
uno di questi piccoli rettangoli.

842
00:38:39,070 --> 00:38:40,690
E 'facile da implementare un int.

843
00:38:40,690 --> 00:38:44,000
Basta dire int n e poi
si ottiene 4 byte per un int,

844
00:38:44,000 --> 00:38:49,089
ma come faccio a ottenere un int, chiamare n,
e poi un puntatore, chiamiamolo prossimo.

845
00:38:49,089 --> 00:38:50,880
Potremmo chiamare questi
cose tutto ciò che vogliamo

846
00:38:50,880 --> 00:38:53,590
ma ho bisogno di una struttura di dati personalizzato.

847
00:38:53,590 --> 00:38:54,257
Sì?

848
00:38:54,257 --> 00:38:57,020
>> PUBBLICO: Ampersand [incomprensibile].

849
00:38:57,020 --> 00:39:00,940
>> DAVID MALAN: Così commerciale useremo per
ottenere l'indirizzo di un nodo potenzialmente.

850
00:39:00,940 --> 00:39:02,740
Ma abbiamo bisogno di un altro
caratteristica di C al fine

851
00:39:02,740 --> 00:39:06,700
per darmi la possibilità di creare
questo rettangolo usanza, questa usanza

852
00:39:06,700 --> 00:39:08,919
variabile se si vuole, in memoria.

853
00:39:08,919 --> 00:39:09,710
PUBBLICO: Un struct.

854
00:39:09,710 --> 00:39:10,626
DAVID MALAN: una struct.

855
00:39:10,626 --> 00:39:14,310
Richiamo dalla settimana scorsa, abbiamo introdotto
struct, questo relativamente semplice parola chiave

856
00:39:14,310 --> 00:39:16,254
che ci permette di fare cose come questa.

857
00:39:16,254 --> 00:39:18,420
C non è venuto con un data
struttura chiamata studente.

858
00:39:18,420 --> 00:39:22,190
Viene fornito con int e float e char e
tale, ma non sono dotati di studente,

859
00:39:22,190 --> 00:39:26,750
ma siamo in grado di creare un tipo di dati degli studenti,
una struttura studente, con la seguente sintassi

860
00:39:26,750 --> 00:39:27,250
Qui.

861
00:39:27,250 --> 00:39:28,350
E vedrete di nuovo e di nuovo.

862
00:39:28,350 --> 00:39:30,426
Quindi non preoccuparti
memorizzare le parole chiave,

863
00:39:30,426 --> 00:39:33,300
ma la parola chiave che è importante è
solo il fatto che abbiamo detto struct

864
00:39:33,300 --> 00:39:37,590
e poi abbiamo chiamato studente e dentro
dello studente era un nome e una casa

865
00:39:37,590 --> 00:39:39,390
o un dormitorio o simili.

866
00:39:39,390 --> 00:39:41,980
>> E così ora di oggi, cerchiamo di proporre questo.

867
00:39:41,980 --> 00:39:45,240
Ho aggiunto qualche parola, ma se voglio
di attuare questo rettangolo che è

868
00:39:45,240 --> 00:39:48,440
ottenuto sia un int e un
puntatore, si sa che cosa, io sono

869
00:39:48,440 --> 00:39:51,540
andando a dichiarare una struct chiamato nodo.

870
00:39:51,540 --> 00:39:55,630
Sono anche, al suo interno, per dire
che un nodo, questo rettangolo, ha un int

871
00:39:55,630 --> 00:39:59,730
e che chiameremo n e
ha un puntatore successivo.

872
00:39:59,730 --> 00:40:02,540
E questo è un po 'prolisso,
ma se ci pensate,

873
00:40:02,540 --> 00:40:07,300
le frecce che erano nella foto
un momento fa sono di che tipo di dati?

874
00:40:07,300 --> 00:40:12,330
Dove ognuno di quelle frecce sta indicando
a quale tipo di struttura dati?

875
00:40:12,330 --> 00:40:14,332
Non è rivolto solo a un int di per sé.

876
00:40:14,332 --> 00:40:16,165
Si punta alla
tutto rettangolare

877
00:40:16,165 --> 00:40:18,720
e che cosa rettangolari,
abbiamo detto, è chiamato un nodo.

878
00:40:18,720 --> 00:40:21,720
E così abbiamo tipo di dover
ricorsivamente definire questo come

879
00:40:21,720 --> 00:40:26,270
che un nodo, diremo,
conterrà un int chiamato n

880
00:40:26,270 --> 00:40:31,070
e un puntatore chiamato successivo e la
tipo di struttura dati a cui

881
00:40:31,070 --> 00:40:35,770
che i punti di puntatore è apparentemente
sta per essere nodo struct.

882
00:40:35,770 --> 00:40:41,550
>> Quindi questo è fastidiosamente verbose
e solo per essere pedanti,

883
00:40:41,550 --> 00:40:44,100
il motivo per cui non possiamo
solo dire questo, che francamente

884
00:40:44,100 --> 00:40:46,860
sembra molto più leggibile,
è perché ricordo che C Lettura

885
00:40:46,860 --> 00:40:48,710
cose dall'alto in basso, da sinistra a destra.

886
00:40:48,710 --> 00:40:54,120
Non è fino a quando si ottiene il punto e virgola
che il nodo parola esiste realmente.

887
00:40:54,120 --> 00:40:57,980
Quindi, se vogliamo avere questo tipo di
riferimento ciclica interna dei dati

888
00:40:57,980 --> 00:41:02,120
struttura, dobbiamo fare questo, dove
diciamo struct node in alto, che

889
00:41:02,120 --> 00:41:06,770
ci dà un modo più lungo di descrivere questo
cosa, poi dentro diciamo nodo struct,

890
00:41:06,770 --> 00:41:09,560
e poi l'ultima riga
diciamo, va bene, C, tra l'altro,

891
00:41:09,560 --> 00:41:12,060
basta chiamare tutta questa maledetta
cosa un nodo e fermarsi

892
00:41:12,060 --> 00:41:14,360
utilizzando la parola chiave struct del tutto.

893
00:41:14,360 --> 00:41:18,030
Quindi questo è solo una sorta di sintattica
trucco che permette alla fine a creare

894
00:41:18,030 --> 00:41:21,370
qualcosa che appare esattamente come questo.

895
00:41:21,370 --> 00:41:25,010
>> Quindi, se assumiamo ora possiamo
implementare questa cosa in C,

896
00:41:25,010 --> 00:41:28,040
come si fa in realtà
iniziare l'attraversamento di questa?

897
00:41:28,040 --> 00:41:32,360
Beh, in effetti, tutto quello che dobbiamo fare è
scorrere da sinistra a destra e basta

898
00:41:32,360 --> 00:41:35,960
tipo di inserire nodi o eliminare i nodi
o la ricerca di cose dove vogliamo,

899
00:41:35,960 --> 00:41:39,560
ma per fare questo, andiamo avanti e fare
le cose un po 'più reale perché questo

900
00:41:39,560 --> 00:41:42,560
è stato super-basso livello finora.

901
00:41:42,560 --> 00:41:45,700
Chiunque sarebbe letteralmente piace essere il primo?

902
00:41:45,700 --> 00:41:46,200
OK.

903
00:41:46,200 --> 00:41:47,092
Vieni su.

904
00:41:47,092 --> 00:41:47,800
Come ti chiami?

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
Felice di conoscerti.

908
00:41:49,998 --> 00:41:50,960
Anch'io.

909
00:41:50,960 --> 00:41:52,450
Tutto ok.

910
00:41:52,450 --> 00:41:53,990
E abbiamo bisogno di un numero 9.

911
00:41:53,990 --> 00:41:55,240
Non buono come prima, forse.

912
00:41:55,240 --> 00:41:56,430
OK, numero 9.

913
00:41:56,430 --> 00:41:59,667
Un numero 17, per favore.

914
00:41:59,667 --> 00:42:01,000
Torniamo un po 'più lontano.

915
00:42:01,000 --> 00:42:03,980
Numero 22, per favore, e
come su più indietro

916
00:42:03,980 --> 00:42:06,344
se riesco a vedere tutte le mani
con tutta la luce o no.

917
00:42:06,344 --> 00:42:08,010
Qualcuno è essere volontariamente proprio lì.

918
00:42:08,010 --> 00:42:08,968
Vuoi venire?

919
00:42:08,968 --> 00:42:10,450
Il vostro avambraccio viene forzatamente salendo.

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 è venuta giù.

923
00:42:15,120 --> 00:42:18,450
Qualcuno altro piacerebbe
forcefully-- Vieni su.

924
00:42:18,450 --> 00:42:21,030
Un volontario effettivo.

925
00:42:21,030 --> 00:42:23,330
>> Quindi molto rapidamente, se
voi ragazzi potrebbe organizzare

926
00:42:23,330 --> 00:42:26,550
Proprio come voi
i nodi sullo schermo.

927
00:42:26,550 --> 00:42:27,510
Grazie.

928
00:42:27,510 --> 00:42:29,234
E sarete 26.

929
00:42:29,234 --> 00:42:30,650
Tutte le introduzioni di destra e veloci.

930
00:42:30,650 --> 00:42:32,139
Quindi sono Davide e tu sei anche?

931
00:42:32,139 --> 00:42:32,680
DAVID: David.

932
00:42:32,680 --> 00:42:33,721
DAVID MALAN: E tu sei?

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
Eccellente.

940
00:42:37,590 --> 00:42:39,810
Quindi questi sono i nostri volontari
per oggi e andare avanti

941
00:42:39,810 --> 00:42:43,090
e spostare un po 'in questo modo,
e solo andare avanti e mantenere

942
00:42:43,090 --> 00:42:47,024
tiene i numeri come siete o il vostro
primo segno e con la mano sinistra,

943
00:42:47,024 --> 00:42:48,940
andare avanti e basta implementare
queste frecce, solo

944
00:42:48,940 --> 00:42:51,360
in modo che la mano sinistra è letteralmente
che punta a qualunque è necessario indicare la

945
00:42:51,360 --> 00:42:54,610
a, e datevi qualche camera in modo che
possiamo vedere visivamente le braccia in realtà

946
00:42:54,610 --> 00:42:58,120
puntamento, e si può solo puntare
sorta di a terra va bene.

947
00:42:58,120 --> 00:43:03,040
>> Quindi qui abbiamo una lista concatenata di uno,
due, tre, quattro, cinque nodi inizialmente,

948
00:43:03,040 --> 00:43:05,860
e notare abbiamo questo speciale
puntatore all'inizio che è

949
00:43:05,860 --> 00:43:09,770
chiave perché dobbiamo tenere traccia
di tutta la lista di lunghezza in qualche modo.

950
00:43:09,770 --> 00:43:13,590
Questi ragazzi, anche se sono lasciati
a destra, back to back in memoria,

951
00:43:13,590 --> 00:43:15,950
essi possono effettivamente essere ovunque
nella memoria del computer.

952
00:43:15,950 --> 00:43:18,240
Così questi ragazzi potrebbero essere
piedi ovunque sul palco

953
00:43:18,240 --> 00:43:20,960
e va bene, fintanto che sono
in realtà indica l'un l'altro,

954
00:43:20,960 --> 00:43:22,770
ma per mantenere le cose
pulito e semplice, faremo

955
00:43:22,770 --> 00:43:25,728
disegnarle semplicemente da sinistra a destra come
questo, ma ci potrebbe essere lacune enormi

956
00:43:25,728 --> 00:43:26,790
tra questi nodi.

957
00:43:26,790 --> 00:43:30,710
>> Ora, se voglio inserire in realtà un po '
il nuovo valore, andiamo avanti e fare questo.

958
00:43:30,710 --> 00:43:33,720
Abbiamo un'opportunità ora
di scegliere un altro nodo.

959
00:43:33,720 --> 00:43:39,820
Dire cominciamo via con mallocing 55.

960
00:43:39,820 --> 00:43:41,320
Qualcuno dispiacerebbe essere malloc?

961
00:43:41,320 --> 00:43:42,280
OK, andiamo su.

962
00:43:42,280 --> 00:43:42,992
Come ti chiami?

963
00:43:42,992 --> 00:43:43,700
RAINBOW: Rainbow.

964
00:43:43,700 --> 00:43:44,050
DAVID MALAN: Rainbow?

965
00:43:44,050 --> 00:43:44,810
Tutto ok.

966
00:43:44,810 --> 00:43:46,600
Malloc Arcobaleno.

967
00:43:46,600 --> 00:43:47,450
Vieni su.

968
00:43:47,450 --> 00:43:51,610
Quindi ora dobbiamo chiederci
algoritmicamente dove possiamo mettere 55.

969
00:43:51,610 --> 00:43:53,610
Quindi, tutti noi sappiamo,
ovviamente, dove probabilmente

970
00:43:53,610 --> 00:43:55,401
appartiene se stiamo cercando
per mantenere questa risolto

971
00:43:55,401 --> 00:43:58,299
e se voi ragazzi poteste prendere una
un passo indietro in modo da non cadere fuori

972
00:43:58,299 --> 00:43:59,590
il palcoscenico, che sarebbe grande.

973
00:43:59,590 --> 00:44:01,420
Quindi, in realtà, Arcobaleno,
iniziare qui con me,

974
00:44:01,420 --> 00:44:04,200
perché noi, come il computer può ora
vedere solo una variabile alla volta.

975
00:44:04,200 --> 00:44:05,190
Quindi, se questo è il primo nodo.

976
00:44:05,190 --> 00:44:07,160
Notate che non è un nodo,
lui è solo un puntatore,

977
00:44:07,160 --> 00:44:10,270
ed è per questo che ha disegnato per essere
solo la dimensione di un puntatore, non

978
00:44:10,270 --> 00:44:11,780
uno di quei rettangoli pieni.

979
00:44:11,780 --> 00:44:16,650
Quindi stiamo andando a controllare ad ogni
iterazione è 55 inferiore a 9?

980
00:44:16,650 --> 00:44:17,150
No.

981
00:44:17,150 --> 00:44:19,060
È 55 meno di 17?

982
00:44:19,060 --> 00:44:19,720
No.

983
00:44:19,720 --> 00:44:20,800
Meno di 22?

984
00:44:20,800 --> 00:44:22,020
Meno di 26?

985
00:44:22,020 --> 00:44:23,390
Meno di 34?

986
00:44:23,390 --> 00:44:25,890
E così ora, ovviamente
Arcobaleno appartiene alla fine.

987
00:44:25,890 --> 00:44:27,270
Quindi, per essere chiari, e che cosa
era il tuo nome, Taylor?

988
00:44:27,270 --> 00:44:27,895
>> TAYLOR: Taylor.

989
00:44:27,895 --> 00:44:32,510
DAVID MALAN: Quindi fra Taylor
la mano sinistra e le mani di Arcobaleno qui,

990
00:44:32,510 --> 00:44:38,324
la cui mano ha bisogno di puntare a che cosa
Per inserire 55 in questa lista?

991
00:44:38,324 --> 00:44:39,240
Che cosa dobbiamo fare?

992
00:44:39,240 --> 00:44:39,700
Sì?

993
00:44:39,700 --> 00:44:41,140
>> PUBBLICO: La mano di Taylor
deve puntare a sinistra.

994
00:44:41,140 --> 00:44:41,680
>> DAVID MALAN: Esattamente.

995
00:44:41,680 --> 00:44:43,800
Quindi inserendo un nodo
nella fine dell'elenco

996
00:44:43,800 --> 00:44:47,140
è abbastanza semplice perché basta Taylor
deve puntare, anziché alla terra

997
00:44:47,140 --> 00:44:49,640
o che chiameremo nullo,
null è una sorta di assenza

998
00:44:49,640 --> 00:44:51,640
di un puntatore o una speciale
puntatore a zero, sei

999
00:44:51,640 --> 00:44:53,740
andando a puntare con la sinistra
mano a Rainbow e poi Arcobaleno,

1000
00:44:53,740 --> 00:44:55,910
dove dovrebbe sinistra
mano probabilmente puntare?

1001
00:44:55,910 --> 00:44:56,570
Giù.

1002
00:44:56,570 --> 00:45:00,140
Non va bene se la sua mano è sorta
di puntamento off qui o qualsiasi tipo di

1003
00:45:00,140 --> 00:45:00,640
quale via.

1004
00:45:00,640 --> 00:45:02,407
Che potrebbe essere considerato
un valore spazzatura,

1005
00:45:02,407 --> 00:45:04,240
ma se lei indica
qualche valore noto, faremo

1006
00:45:04,240 --> 00:45:07,360
chiamare zero o nullo, va bene
perché abbiamo un termine in questo

1007
00:45:07,360 --> 00:45:09,390
e sappiamo che la lista ora è completo.

1008
00:45:09,390 --> 00:45:11,550
>> Allora, qual è un altro
caso relativamente semplice?

1009
00:45:11,550 --> 00:45:13,125
Potremmo malloc 5?

1010
00:45:13,125 --> 00:45:14,010
Vieni su.

1011
00:45:14,010 --> 00:45:14,782
Come ti chiami?

1012
00:45:14,782 --> 00:45:15,490
TIFFANY: Tiffany.

1013
00:45:15,490 --> 00:45:16,000
DAVID MALAN: Mi dispiace?

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
Tutto ok.

1017
00:45:17,110 --> 00:45:19,071
Tiffany è stato malloced
con il valore 5.

1018
00:45:19,071 --> 00:45:19,570
Vieni su.

1019
00:45:19,570 --> 00:45:23,820
Questo è relativamente facile troppo, ma
prendiamo in considerazione ordine delle operazioni ora.

1020
00:45:23,820 --> 00:45:25,820
E 'stato abbastanza facile
con Taylor alla fine.

1021
00:45:25,820 --> 00:45:30,302
Numero 5 è ovviamente inferiore a 9,
e quindi abbiamo David, abbiamo Tiffany,

1022
00:45:30,302 --> 00:45:31,260
e qual era il tuo 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
La cui mano dovrebbe essere aggiornato prima?

1027
00:45:36,580 --> 00:45:39,260

1028
00:45:39,260 --> 00:45:40,590
Cosa vuoi fare qui?

1029
00:45:40,590 --> 00:45:45,244
C'è un paio di modi possibili, ma
c'è anche uno o sensi più sbagliate.

1030
00:45:45,244 --> 00:45:46,620
>> PUBBLICO: Inizia con più a sinistra.

1031
00:45:46,620 --> 00:45:47,800
>> DAVID MALAN: Iniziare con il più a sinistra.

1032
00:45:47,800 --> 00:45:49,008
Chi è il più a sinistra qui, allora?

1033
00:45:49,008 --> 00:45:49,700
PUBBLICO: Primo.

1034
00:45:49,700 --> 00:45:50,366
>> DAVID MALAN: OK.

1035
00:45:50,366 --> 00:45:53,781
Così inizia con la prima e dove si fa
desidera aggiornare le mani di David di essere?

1036
00:45:53,781 --> 00:45:54,780
AUDIENCE: verso il 5.

1037
00:45:54,780 --> 00:45:55,446
DAVID MALAN: OK.

1038
00:45:55,446 --> 00:45:59,026
Davide, punto in cinque
o Tiffany qui, e ora?

1039
00:45:59,026 --> 00:46:01,072
>> PUBBLICO: Tiffany punta al 9?

1040
00:46:01,072 --> 00:46:04,030
DAVID MALAN: Perfetto, tranne Binky di
testa solo tipo di caduto, giusto?

1041
00:46:04,030 --> 00:46:06,820
Perché quello che c'è di sbagliato con
questa immagine letteralmente?

1042
00:46:06,820 --> 00:46:08,070
AUDIENCE: Nulla sta indicando.

1043
00:46:08,070 --> 00:46:09,945
DAVID MALAN: Niente è
indicando Jake ora.

1044
00:46:09,945 --> 00:46:13,360
Abbiamo letteralmente orfani 9
e 17, e abbiamo letteralmente

1045
00:46:13,360 --> 00:46:18,450
perdeva di questa memoria, perché da
aggiornare la mano di David prima, che è

1046
00:46:18,450 --> 00:46:21,660
bene nella misura in cui è correttamente
che punta a Tiffany ora,

1047
00:46:21,660 --> 00:46:25,410
ma se nessuno aveva il
lungimiranza di puntare a Jake,

1048
00:46:25,410 --> 00:46:27,490
poi abbiamo perso il
totalità di tale elenco.

1049
00:46:27,490 --> 00:46:28,200
Quindi cerchiamo di annullare.

1050
00:46:28,200 --> 00:46:30,950
Così che era una buona cosa per
inciampare ma cerchiamo di correggere ora.

1051
00:46:30,950 --> 00:46:33,624
Cosa dobbiamo fare prima, invece?

1052
00:46:33,624 --> 00:46:34,124
Sì?

1053
00:46:34,124 --> 00:46:35,791
>> PUBBLICO: Tiffany dovrebbe puntare al 9?

1054
00:46:35,791 --> 00:46:37,582
DAVID MALAN: non posso
ottenere che vicino a voi.

1055
00:46:37,582 --> 00:46:38,720
Chi dovrebbe puntare al 9?

1056
00:46:38,720 --> 00:46:39,220
>> PUBBLICO: Tiffany.

1057
00:46:39,220 --> 00:46:39,390
>> DAVID MALAN: Va bene.

1058
00:46:39,390 --> 00:46:41,200
Così Tiffany dovrebbe primo punto al 9.

1059
00:46:41,200 --> 00:46:43,550
Così Tiffany dovrebbe prendere
su un valore identico

1060
00:46:43,550 --> 00:46:45,820
David, che sembra
ridondante per un istante,

1061
00:46:45,820 --> 00:46:48,820
ma va bene perché ora, secondo
passo, possiamo aggiornare la mano di David

1062
00:46:48,820 --> 00:46:52,680
per indicare a Tiffany, e poi se
abbiamo solo tipo di pulire le cose

1063
00:46:52,680 --> 00:46:55,740
come se questo è una specie di primaverile,
ora che è un corretto inserimento.

1064
00:46:55,740 --> 00:46:56,700
Così eccellente.

1065
00:46:56,700 --> 00:46:57,970
Così ora ci siamo quasi.

1066
00:46:57,970 --> 00:47:01,075
Inseriamo un finale
valore come il valore 20.

1067
00:47:01,075 --> 00:47:03,010
Se potessimo malloc un volontario finale?

1068
00:47:03,010 --> 00:47:04,140
Vieni su.

1069
00:47:04,140 --> 00:47:06,224
Quindi questo è un po 'più complicato.

1070
00:47:06,224 --> 00:47:08,390
Ma in realtà, il codice siamo
la scrittura, anche se verbalmente,

1071
00:47:08,390 --> 00:47:10,610
è proprio come avere un mucchio
se le condizioni di ora, giusto?

1072
00:47:10,610 --> 00:47:12,318
Abbiamo avuto una condizione
controllare se appartiene

1073
00:47:12,318 --> 00:47:13,840
alla fine, forse l'inizio.

1074
00:47:13,840 --> 00:47:15,940
Abbiamo bisogno di un qualche tipo di ciclo per
trovare il punto nel mezzo.

1075
00:47:15,940 --> 00:47:17,400
Allora, facciamo che con quello che è il tuo 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
Felice di conoscerti.

1080
00:47:19,368 --> 00:47:20,490
Quindi abbiamo 20.

1081
00:47:20,490 --> 00:47:21,220
Meno di cinque?

1082
00:47:21,220 --> 00:47:21,530
No.

1083
00:47:21,530 --> 00:47:22,160
Meno di nove?

1084
00:47:22,160 --> 00:47:22,410
No.

1085
00:47:22,410 --> 00:47:23,050
Meno di 17?

1086
00:47:23,050 --> 00:47:23,550
No.

1087
00:47:23,550 --> 00:47:23,740
OK.

1088
00:47:23,740 --> 00:47:25,701
Egli appartiene qui e
i nomi sono di nuovo?

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
Le cui mani hanno bisogno di ottenere aggiornato prima?

1096
00:47:32,140 --> 00:47:32,930
>> PUBBLICO: Eric.

1097
00:47:32,930 --> 00:47:33,429
OK.

1098
00:47:33,429 --> 00:47:35,200
Così Eric dovrebbero puntare a dove?

1099
00:47:35,200 --> 00:47:35,930
A 22 anni.

1100
00:47:35,930 --> 00:47:36,430
Bene.

1101
00:47:36,430 --> 00:47:38,180
E ora che cosa è il prossimo?

1102
00:47:38,180 --> 00:47:40,800
Sue può quindi puntare a Eric
e ora, se voi ragazzi solo

1103
00:47:40,800 --> 00:47:44,077
fare spazio, che va bene
visivamente, ora abbiamo fatto l'inserimento.

1104
00:47:44,077 --> 00:47:47,160
Quindi cerchiamo di Consideriamo una domanda ma
grazie mille per i nostri volontari.

1105
00:47:47,160 --> 00:47:48,090
Molto ben fatto.

1106
00:47:48,090 --> 00:47:50,831
È possibile mantenere quelle, se volete.

1107
00:47:50,831 --> 00:47:54,140
E abbiamo un bel regalo d'addio se
avresti ogni piace prendere una palla antistress.

1108
00:47:54,140 --> 00:47:56,030
Lasciatemi passare questo giù.

1109
00:47:56,030 --> 00:47:58,430
Allora, qual è l'asporto di questo?

1110
00:47:58,430 --> 00:48:02,430
Questo sembra essere sorprendente
nella misura in cui abbiamo ora

1111
00:48:02,430 --> 00:48:06,360
introdotto alternativa a una
matrice che non è così limitato

1112
00:48:06,360 --> 00:48:07,780
a un array di qualche dimensione fissa.

1113
00:48:07,780 --> 00:48:09,380
Possono crescere in modo dinamico.

1114
00:48:09,380 --> 00:48:13,220
>> Ma proprio come abbiamo visto in settimane
passato, non abbiamo mai ottenere nulla gratis,

1115
00:48:13,220 --> 00:48:15,740
come sicuramente c'è un trade-off qui.

1116
00:48:15,740 --> 00:48:18,890
Quindi, con un rialzo di un collegato
lista, è questo dinamismo?

1117
00:48:18,890 --> 00:48:21,590
Questa capacità di crescere e, francamente,
avremmo potuto fare di cancellazione

1118
00:48:21,590 --> 00:48:23,570
e abbiamo potuto ridursi a seconda delle necessità.

1119
00:48:23,570 --> 00:48:24,710
Quale prezzo stiamo pagando?

1120
00:48:24,710 --> 00:48:28,510

1121
00:48:28,510 --> 00:48:30,340
Doppio dello spazio, prima di tutto.

1122
00:48:30,340 --> 00:48:34,010
Se guardate la foto, non più
sono io Memorizzazione di una lista di numeri interi.

1123
00:48:34,010 --> 00:48:36,740
Sto memorizzare una lista di
interi più puntatori.

1124
00:48:36,740 --> 00:48:38,240
Così sto raddoppiando la quantità di spazio.

1125
00:48:38,240 --> 00:48:40,740
Ora, forse non è così
un grande affare 4 byte, 8 byte,

1126
00:48:40,740 --> 00:48:43,160
ma potrebbe certamente aggiungere
per grandi insiemi di dati.

1127
00:48:43,160 --> 00:48:45,570
Che cosa è un altro aspetto negativo?

1128
00:48:45,570 --> 00:48:46,070
Sì?

1129
00:48:46,070 --> 00:48:48,010
>> PUBBLICO: Dobbiamo
attraversarli uno per uno.

1130
00:48:48,010 --> 00:48:48,760
DAVID MALAN: Sì.

1131
00:48:48,760 --> 00:48:50,260
Dobbiamo attraversare loro uno per uno.

1132
00:48:50,260 --> 00:48:53,860
Sai una cosa, abbiamo rinunciato questo super
comoda funzione di parentesi quadra

1133
00:48:53,860 --> 00:48:57,240
notazione, più propriamente
noto come accesso casuale,

1134
00:48:57,240 --> 00:48:59,280
dove possiamo saltare solo
ad un singolo elemento

1135
00:48:59,280 --> 00:49:01,470
ma ora se avevo ancora
i miei volontari qui,

1136
00:49:01,470 --> 00:49:04,660
se volevo trovare il
il numero 22, non posso solo

1137
00:49:04,660 --> 00:49:06,620
saltare a staffa qualcosa qualcosa.

1138
00:49:06,620 --> 00:49:10,530
Devo guardare oltre l'elenco, tanto
come i nostri esempi Ricerca in modo lineare,

1139
00:49:10,530 --> 00:49:12,260
per trovare il numero 22.

1140
00:49:12,260 --> 00:49:14,340
Quindi ci sembra di aver pagato un prezzo lì.

1141
00:49:14,340 --> 00:49:16,430
Ma possiamo comunque
risolvere altri problemi.

1142
00:49:16,430 --> 00:49:18,587
>> In realtà, mi permetta di introdurre
solo un paio di immagini.

1143
00:49:18,587 --> 00:49:20,920
Quindi, se siete stati fino a
Mather Dining Hall di recente,

1144
00:49:20,920 --> 00:49:23,320
vi ricordate che il loro
pile di vassoi come questo,

1145
00:49:23,320 --> 00:49:26,300
abbiamo preso in prestito da questi
Annenberg prima della lezione.

1146
00:49:26,300 --> 00:49:28,930
Quindi questa pila di vassoi, però,
è in realtà rappresentativa

1147
00:49:28,930 --> 00:49:30,860
di una struttura di dati informatica.

1148
00:49:30,860 --> 00:49:32,910
Vi è una struttura di dati
in informatica

1149
00:49:32,910 --> 00:49:38,010
noto come uno stack molto ben
si presta ad esattamente questo visiva.

1150
00:49:38,010 --> 00:49:41,380
Quindi, se ciascuno di questi vassoi non è un
vassoio ma come un numero e volevo

1151
00:49:41,380 --> 00:49:45,010
di memorizzare i numeri, io
potrebbe mettere uno qui,

1152
00:49:45,010 --> 00:49:48,320
e ho potuto mettere un altro qui,
e continuare numeri accatastamento

1153
00:49:48,320 --> 00:49:53,180
uno sopra l'altro, e ciò che è
potenzialmente utile su questo

1154
00:49:53,180 --> 00:49:55,450
è che ciò che è l'implicazione
di questa struttura dati?

1155
00:49:55,450 --> 00:49:58,045
Quale numero posso tirare fuori
prima il più convenientemente?

1156
00:49:58,045 --> 00:50:00,640

1157
00:50:00,640 --> 00:50:03,030
La più recente una calzata lì.

1158
00:50:03,030 --> 00:50:06,430
>> Quindi questo è quello che noi chiameremmo in
informatica una struttura dati LIFO.

1159
00:50:06,430 --> 00:50:08,070
Last in, first out.

1160
00:50:08,070 --> 00:50:10,800
E vedremo fra poco perché
che potrebbe essere utile, ma per ora,

1161
00:50:10,800 --> 00:50:12,200
basta considerare la proprietà.

1162
00:50:12,200 --> 00:50:15,158
Ed è una specie di stupido se si pensa
su come la sala da pranzo lo fa.

1163
00:50:15,158 --> 00:50:17,910
Ogni volta che i vassoi e puliti
mettere quelli freschi sulla parte superiore,

1164
00:50:17,910 --> 00:50:22,160
si potrebbe avere una precedentemente pulito
ma alla fine molto sporca e polverosa

1165
00:50:22,160 --> 00:50:24,360
vassoio in fondo
se non avete mai realmente

1166
00:50:24,360 --> 00:50:26,820
andare a fondo di tale
pila, perché basta

1167
00:50:26,820 --> 00:50:29,380
continuare a mettere il nuovo e
quelle pulite su di esso.

1168
00:50:29,380 --> 00:50:31,840
La stessa cosa potrebbe accadere
in un supermercato troppo.

1169
00:50:31,840 --> 00:50:35,450
Se si dispone di una vetrina
di latte e ogni volta CVS

1170
00:50:35,450 --> 00:50:37,610
o chi ottiene più latte,
basta infilare il latte

1171
00:50:37,610 --> 00:50:39,880
hai già alla schiena e
si mettono i nuovi in ​​attacco,

1172
00:50:39,880 --> 00:50:43,088
si sta andando ad avere un po 'piuttosto brutta
latte alla fine della struttura di dati,

1173
00:50:43,088 --> 00:50:46,390
perché è sempre in fondo o
equivalentemente è sempre sul retro.

1174
00:50:46,390 --> 00:50:50,407
>> Ma c'è un altro modo di pensare
fila di dati e per esempio, questo.

1175
00:50:50,407 --> 00:50:53,490
Se siete una di quelle persone che ama
a schierarsi al di fuori di negozi di Apple

1176
00:50:53,490 --> 00:50:55,610
quando un nuovo prodotto viene
fuori, probabilmente sei

1177
00:50:55,610 --> 00:50:58,780
non si utilizza una pila di dati
struttura perché si

1178
00:50:58,780 --> 00:51:03,070
sarebbe alienare tutti gli altri che è
in fila per l'acquisto di qualche nuovo giocattolo.

1179
00:51:03,070 --> 00:51:06,610
Piuttosto, probabilmente stai usando
che tipo di struttura dati

1180
00:51:06,610 --> 00:51:10,050
o che tipo di sistema
nel mondo reale?

1181
00:51:10,050 --> 00:51:13,493
Speriamo che sia una linea, o più
correttamente o altro britannico-like, una coda.

1182
00:51:13,493 --> 00:51:17,700
E si scopre una coda è anche un
struttura dati in informatica,

1183
00:51:17,700 --> 00:51:19,700
ma una coda ha una molto
proprietà diversa.

1184
00:51:19,700 --> 00:51:20,820
Non è LIFO.

1185
00:51:20,820 --> 00:51:21,990
Last in, first out.

1186
00:51:21,990 --> 00:51:22,800
Dio non voglia.

1187
00:51:22,800 --> 00:51:24,280
E 'invece FIFO.

1188
00:51:24,280 --> 00:51:26,110
Il primo che entra è il primo ad uscire.

1189
00:51:26,110 --> 00:51:27,970
E questa è una buona cosa
per l'amor di equità '

1190
00:51:27,970 --> 00:51:30,428
certamente quando si sta in fila
up molto presto la mattina.

1191
00:51:30,428 --> 00:51:33,400
Se si arriva prima, è
vuole uscire prima pure.

1192
00:51:33,400 --> 00:51:35,880
>> E così tutti questi dati
strutture, code e pile

1193
00:51:35,880 --> 00:51:39,220
e mazzi di altri, risulta voi
può pensare a questo come solo un array.

1194
00:51:39,220 --> 00:51:41,820
Questo è un array, forse
una dimensione fissa a 4, ma che sarebbe

1195
00:51:41,820 --> 00:51:44,990
essere genere di bello se potessimo solo accumulare
vassoi quasi infinitamente alto se

1196
00:51:44,990 --> 00:51:46,780
avere che molti vassoi o numeri.

1197
00:51:46,780 --> 00:51:48,840
Così forse vogliamo
utilizzare una lista collegata qui,

1198
00:51:48,840 --> 00:51:51,800
ma il trade-off sarà
potenzialmente che abbiamo bisogno di più memoria,

1199
00:51:51,800 --> 00:51:55,930
prende un po 'di tempo, ma noi
non limitano l'altezza della pila,

1200
00:51:55,930 --> 00:51:59,550
tanto come vetrina di Mather
potrebbe limitare la dimensione dello stack,

1201
00:51:59,550 --> 00:52:03,117
e così si tratta di decisioni di progettazione o
opzioni a nostra disposizione definitiva.

1202
00:52:03,117 --> 00:52:04,950
Quindi, con questi dati
strutture, abbiamo iniziato

1203
00:52:04,950 --> 00:52:09,360
vedere nuovi limiti superiori potenzialmente
su quello che in precedenza era super veloce

1204
00:52:09,360 --> 00:52:11,260
e dove lasceremo
via oggi e dove

1205
00:52:11,260 --> 00:52:13,200
ci auguriamo di arrivare a
è il Mercoledì, faremo

1206
00:52:13,200 --> 00:52:15,740
iniziare a guardare un dato
struttura che ci permette di ricercata

1207
00:52:15,740 --> 00:52:18,260
attraverso i dati in tempo fine del registro di nuovo.

1208
00:52:18,260 --> 00:52:21,470
E abbiamo visto che, ricordano, in settimana lo zero
e uno con ricerca binaria o dividere

1209
00:52:21,470 --> 00:52:22,180
e conquistare.

1210
00:52:22,180 --> 00:52:26,240
Sta tornando e meglio ancora,
il Santo Graal per questo Mercoledì

1211
00:52:26,240 --> 00:52:29,510
sarà quello di venire con la
struttura di dati che corre veramente

1212
00:52:29,510 --> 00:52:32,070
o teoricamente in
costante di tempo, per cui

1213
00:52:32,070 --> 00:52:34,760
non importa quanti
milioni o miliardi di cose

1214
00:52:34,760 --> 00:52:38,470
abbiamo nella struttura dati, lo farà
Ci vorrà del tempo costante, forse un passo

1215
00:52:38,470 --> 00:52:41,387
o due passi o 10 passi,
ma i numeri costanti passi

1216
00:52:41,387 --> 00:52:42,970
per la ricerca in tale struttura di dati.

1217
00:52:42,970 --> 00:52:46,300
Che in effetti sarà il Santo Graal
ma più che il Mercoledì.

1218
00:52:46,300 --> 00:52:49,045
Ci vediamo allora.

1219
00:52:49,045 --> 00:52:53,704
>> [RIPRODUZIONE DI BRANI MUSICALI]

1220
00:52:53,704 --> 00:56:08,448