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

2
00:00:00,500 --> 00:00:11,137
[GIOCO MUSICA]

3
00:00:11,137 --> 00:00:12,220
DAVID J. MALAN: Va bene.

4
00:00:12,220 --> 00:00:13,950
Questo è CS50.

5
00:00:13,950 --> 00:00:18,560
Questa è la settimana di cinque continuò, e noi
avere qualche buona notizia e una cattiva notizia.

6
00:00:18,560 --> 00:00:21,140
Quindi buona notizia è che CS50
lancia questo Venerdì.

7
00:00:21,140 --> 00:00:24,430
Se volete unirvi a noi,
andare al solito URL qui.

8
00:00:24,430 --> 00:00:28,670
Ancora meglio le notizie, no lezione
il prossimo Lunedi 13.

9
00:00:28,670 --> 00:00:31,970
Leggermente meno notizie migliori,
quiz zero è Mercoledì prossimo.

10
00:00:31,970 --> 00:00:33,840
Maggiori dettagli possono essere
trovato a questo indirizzo qui.

11
00:00:33,840 --> 00:00:36,340
E nei prossimi giorni di coppia
saremo riempire gli spazi vuoti

12
00:00:36,340 --> 00:00:39,234
per quanto riguarda le camere
che avremo riservato.

13
00:00:39,234 --> 00:00:41,400
Meglio notizia è che ci sarà
essere una revisione generale e portate

14
00:00:41,400 --> 00:00:43,570
sessione il prossimo
Lunedi sera.

15
00:00:43,570 --> 00:00:46,270
Restate sintonizzati per il corso di
sito web per la posizione e dettagli.

16
00:00:46,270 --> 00:00:49,290
Sezioni, anche se si tratta di un
vacanza, anche incontrare pure.

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

18
00:00:50,490 --> 00:00:52,940
Miglior notizie, lezione prossimo Venerdì.

19
00:00:52,940 --> 00:00:56,220
Quindi questa è una tradizione che
avere, come da programma.

20
00:00:56,220 --> 00:00:58,100
Solo-- sta andando essere sorprendente.

21
00:00:58,100 --> 00:01:02,510
Vedrete le cose come
strutture di dati costante di tempo

22
00:01:02,510 --> 00:01:04,730
e tabelle hash e alberi e tentativi.

23
00:01:04,730 --> 00:01:07,150
E parleremo di problemi di compleanno.

24
00:01:07,150 --> 00:01:09,440
Un sacco di roba
aspetta il prossimo Venerdì.

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

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

27
00:01:12,200 --> 00:01:13,190
Comunque.

28
00:01:13,190 --> 00:01:17,080
>> Quindi ricordiamo che siamo stati
concentrandosi su questa immagine di ciò che è

29
00:01:17,080 --> 00:01:18,980
all'interno della memoria del nostro computer.

30
00:01:18,980 --> 00:01:22,875
Così memoria o RAM è dove i programmi
esistere mentre li sta eseguendo.

31
00:01:22,875 --> 00:01:25,215
Se si fa doppio clic su un
icona per eseguire qualche programma

32
00:01:25,215 --> 00:01:27,520
o doppio clic su un
icona per aprire qualche file,

33
00:01:27,520 --> 00:01:30,430
è caricato dal disco
guidare o unità a stato solido

34
00:01:30,430 --> 00:01:34,190
nella RAM, Random Access Memory, dove
vive fino a quando non si spegne,

35
00:01:34,190 --> 00:01:36,700
il coperchio del portatile si chiude,
o si chiude il programma.

36
00:01:36,700 --> 00:01:38,960
>> Ora che la memoria, di
che probabilmente avete

37
00:01:38,960 --> 00:01:41,950
1 gigabyte questi giorni, 2
gigabyte, o anche molto di più,

38
00:01:41,950 --> 00:01:44,420
è generalmente disposto
per un dato programma

39
00:01:44,420 --> 00:01:47,170
in questo genere di forma rettangolare
modello concettuale

40
00:01:47,170 --> 00:01:50,860
per cui abbiamo la pila in basso
e un mucchio di altre cose in alto.

41
00:01:50,860 --> 00:01:53,140
La cosa in cima
abbiamo visto in questa immagine

42
00:01:53,140 --> 00:01:55,670
prima, ma mai parlato
è il cosiddetto segmento di testo.

43
00:01:55,670 --> 00:01:58,419
Segmento di testo è solo un modo di fantasia
di dire gli zeri e quelli che

44
00:01:58,419 --> 00:02:01,150
comporre il programma compilato reale.

45
00:02:01,150 --> 00:02:03,910
>> Così, quando si fa doppio clic
Microsoft Word sul vostro Mac o PC,

46
00:02:03,910 --> 00:02:08,030
o quando si esegue puntino tagliare Mario su una
Computer Linux a vostra finestra di terminale,

47
00:02:08,030 --> 00:02:12,460
gli zeri e quelli che compongono
Word o Mario sono memorizzati temporaneamente

48
00:02:12,460 --> 00:02:16,610
nella RAM del computer nella cosiddetta
segmento di testo per un particolare programma.

49
00:02:16,610 --> 00:02:19,080
Sotto che va inizializzato
e dati non inizializzati.

50
00:02:19,080 --> 00:02:22,655
Questa è roba come variabili globali,
che noi non abbiamo usato molti,

51
00:02:22,655 --> 00:02:24,910
ma a volte abbiamo
aveva variabili globali

52
00:02:24,910 --> 00:02:28,819
o staticamente stringhe definito che
è difficile parole come "ciao" codificato

53
00:02:28,819 --> 00:02:31,860
che non sono prese in dall'utente
che sono hardcoded nel programma.

54
00:02:31,860 --> 00:02:34,230
>> Ora, giù in fondo siamo
avere il cosiddetto stack.

55
00:02:34,230 --> 00:02:37,665
E lo stack, finora, siamo stati
usando per che tipo di scopi?

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

57
00:02:39,706 --> 00:02:40,997
Qual è lo stack stato utilizzato per?

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

59
00:02:41,160 --> 00:02:42,070
>> PUBBLICO: Funzioni.

60
00:02:42,070 --> 00:02:43,320
>> DAVID J. MALAN: Per le funzioni?

61
00:02:43,320 --> 00:02:44,980
In che senso per funzioni?

62
00:02:44,980 --> 00:02:48,660
>> PUBBLICO: Quando si chiama una funzione, il
argomenti vengono copiati nello stack.

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

64
00:02:49,660 --> 00:02:52,650
Quando si chiama una funzione, la sua
argomenti vengono copiati nello stack.

65
00:02:52,650 --> 00:02:56,330
Quindi, qualsiasi X o Y o di una di B o di
che si sta passando in una funzione

66
00:02:56,330 --> 00:02:58,680
sono temporaneamente messo su
il cosiddetto stack,

67
00:02:58,680 --> 00:03:02,000
proprio come uno di Annenberg
vassoi sala da pranzo, e anche le cose

68
00:03:02,000 --> 00:03:03,190
come variabili locali.

69
00:03:03,190 --> 00:03:06,290
Se la funzione foo o lo swap
funzione ha variabili locali,

70
00:03:06,290 --> 00:03:08,602
come temperatura, quei due
finire nella pila.

71
00:03:08,602 --> 00:03:11,560
Ora, noi non parleremo troppo di
li, ma queste variabili di ambiente

72
00:03:11,560 --> 00:03:15,690
in fondo abbiamo visto qualche tempo fa, quando
Stavo futzing alla tastiera uno giorno

73
00:03:15,690 --> 00:03:20,050
e ho cominciato accesso cose
come argv 100 o argv 1000,

74
00:03:20,050 --> 00:03:22,320
solo elements-- dimentico
il numbers-- ma che

75
00:03:22,320 --> 00:03:24,330
non avrebbero dovuto essere accessibile da me.

76
00:03:24,330 --> 00:03:26,581
Abbiamo iniziato a vedere un po '
simboli funky sullo schermo.

77
00:03:26,581 --> 00:03:28,330
Quelli erano i cosiddetti
variabili di ambiente

78
00:03:28,330 --> 00:03:32,390
come impostazioni globali per il mio
programma o per il mio computer, non

79
00:03:32,390 --> 00:03:37,090
estranei al recente
bug che abbiamo discusso,

80
00:03:37,090 --> 00:03:39,670
Shellshock, che è stato
che affligge un bel paio di computer.

81
00:03:39,670 --> 00:03:42,960
>> Ora, infine, a fuoco di oggi
saremo in ultima analisi, di essere sul mucchio.

82
00:03:42,960 --> 00:03:44,864
Questo è un altro pezzo di memoria.

83
00:03:44,864 --> 00:03:47,030
E fondamentalmente tutto questo
la memoria è la stessa roba.

84
00:03:47,030 --> 00:03:48,040
E 'lo stesso hardware.

85
00:03:48,040 --> 00:03:49,956
Siamo appena sorta di
trattamento di diversi cluster

86
00:03:49,956 --> 00:03:51,460
di byte per scopi diversi.

87
00:03:51,460 --> 00:03:56,540
L'heap è anche andando a essere dove
variabili e la memoria che si domanda

88
00:03:56,540 --> 00:03:58,810
dal sistema operativo
temporaneamente memorizzato.

89
00:03:58,810 --> 00:04:01,890
>> Ma c'è una specie di problema
qui, come l'immagine implica.

90
00:04:01,890 --> 00:04:05,261
Noi abbiamo due specie di
navi per scontrarsi.

91
00:04:05,261 --> 00:04:08,010
Perché, come si usa sempre di più
della pila, e come vediamo oggi

92
00:04:08,010 --> 00:04:11,800
poi, come si usa sempre di più il
mucchio, sicuramente le cose brutte possono accadere.

93
00:04:11,800 --> 00:04:15,054
E infatti, possiamo indurre che
intenzionalmente o meno.

94
00:04:15,054 --> 00:04:16,970
Così l'ultima Cliffhanger
tempo era questo programma,

95
00:04:16,970 --> 00:04:20,570
che non servire qualsiasi funzionale
scopo diverso da quello di dimostrare

96
00:04:20,570 --> 00:04:24,750
come come un ragazzo cattivo può effettivamente prendere
vantaggio di bug nel programma di qualcuno

97
00:04:24,750 --> 00:04:28,460
e prendere in consegna un programma o anche un
intero sistema di computer o server.

98
00:04:28,460 --> 00:04:31,660
Quindi, solo per un'occhiata brevemente, si
notare che principale sul fondo

99
00:04:31,660 --> 00:04:34,510
prende a riga di comando
argomenti, come da argv.

100
00:04:34,510 --> 00:04:38,480
E ha una chiamata a una funzione f,
essenzialmente una funzione senza nome chiamato

101
00:04:38,480 --> 00:04:40,250
f, e sta passando argv [1].

102
00:04:40,250 --> 00:04:43,960
>> Quindi, qualunque parola l'utente digita in
prompt dopo il nome di questo programma,

103
00:04:43,960 --> 00:04:49,310
e poi questa funzione arbitraria up
top, f, prende in una stringa, AKA char *,

104
00:04:49,310 --> 00:04:51,720
come abbiamo cominciato a discutere,
e appena lo chiama "bar".

105
00:04:51,720 --> 00:04:53,310
Ma potremmo chiamarlo nulla.

106
00:04:53,310 --> 00:04:57,470
E poi dichiara, dentro
di f, un array di caratteri

107
00:04:57,470 --> 00:04:59,930
chiamato C-- 12 tali caratteri.

108
00:04:59,930 --> 00:05:03,580
>> Ora, la storia che stavo raccontando
un momento fa, dove in memoria

109
00:05:03,580 --> 00:05:06,720
è C, o sono quelli 12
Chars andando a finire?

110
00:05:06,720 --> 00:05:07,570
Giusto per essere chiari.

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

112
00:05:08,070 --> 00:05:08,590
>> PUBBLICO: Sul stack.

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

114
00:05:09,420 --> 00:05:10,720
Quindi c è una variabile locale.

115
00:05:10,720 --> 00:05:14,079
Stiamo chiedendo per 12 caratteri o 12 byte.

116
00:05:14,079 --> 00:05:16,120
Coloro che stanno per finire
il cosiddetto stack.

117
00:05:16,120 --> 00:05:18,530
Ora finalmente è questa altra funzione
che è in realtà piuttosto utile,

118
00:05:18,530 --> 00:05:20,571
ma non abbiamo davvero usato
noi stessi, strncopy.

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

120
00:05:21,550 --> 00:05:25,200
Significa copia stringa, ma
solo n lettere, n caratteri.

121
00:05:25,200 --> 00:05:31,990
Così n caratteri saranno
copiato da bar in c.

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

123
00:05:32,980 --> 00:05:34,110
La lunghezza della barra.

124
00:05:34,110 --> 00:05:36,330
Quindi, in altre parole, che
una linea, strncopy,

125
00:05:36,330 --> 00:05:39,500
sta per copiare
efficacemente bar in a c.

126
00:05:39,500 --> 00:05:42,340
>> Ora, giusto per tipo di anticipare
la morale di questa storia,

127
00:05:42,340 --> 00:05:44,750
ciò che è potenzialmente problematico qui?

128
00:05:44,750 --> 00:05:49,710
Anche se stiamo controllando la lunghezza
di bar e passando in strncopy,

129
00:05:49,710 --> 00:05:53,145
Qual è il tuo intestino dice che si è
ancora rotto su questo programma?

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

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

132
00:05:55,220 --> 00:05:57,491
>> PUBBLICO: Non include
spazio per il carattere null.

133
00:05:57,491 --> 00:05:59,990
DAVID J. MALAN: non include
spazio per il carattere null.

134
00:05:59,990 --> 00:06:02,073
Potenzialmente, diversamente
prassi seguita in passato non lo facciamo nemmeno

135
00:06:02,073 --> 00:06:04,810
avere così tanto come un plus 1 a
accogliere tale carattere null.

136
00:06:04,810 --> 00:06:06,649
Ma è ancora peggio di così.

137
00:06:06,649 --> 00:06:07,940
Che altro stiamo fallendo a fare?

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

139
00:06:08,432 --> 00:06:09,307
>> PUBBLICO: [incomprensibile]

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

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

142
00:06:16,440 --> 00:06:18,490
Abbiamo hardcoded 12 piuttosto arbitrariamente.

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

144
00:06:19,497 --> 00:06:21,330
Non è tanto il
problema, ma il fatto

145
00:06:21,330 --> 00:06:25,630
che non stiamo nemmeno controllare se
la lunghezza della barra è inferiore a 12,

146
00:06:25,630 --> 00:06:28,530
nel qual caso sarà
sicuro per metterlo in memoria

147
00:06:28,530 --> 00:06:30,260
chiamato c che abbiamo assegnato.

148
00:06:30,260 --> 00:06:32,960
Infatti, se il bar è come
20 caratteri,

149
00:06:32,960 --> 00:06:39,010
questa funzione sembra essere la copia
20 caratteri da bar in C, quindi

150
00:06:39,010 --> 00:06:41,310
prendere almeno 8 byte
che non dovrebbe essere.

151
00:06:41,310 --> 00:06:42,690
Questo è l'implicazione qui.

152
00:06:42,690 --> 00:06:44,347
>> Così, in breve programma, rotto.

153
00:06:44,347 --> 00:06:45,180
Non è come un grande affare.

154
00:06:45,180 --> 00:06:46,360
Forse si ottiene un errore di segmentazione.

155
00:06:46,360 --> 00:06:47,651
Abbiamo avuto tutti i bug nei programmi.

156
00:06:47,651 --> 00:06:50,196
Noi tutti potremmo avere bug
nei programmi al momento.

157
00:06:50,196 --> 00:06:51,320
Ma qual è l'implicazione?

158
00:06:51,320 --> 00:06:54,390
Bene, ecco una versione ingrandita di
che l'immagine della memoria del mio computer.

159
00:06:54,390 --> 00:06:56,230
Questo è il fondo del mio stack.

160
00:06:56,230 --> 00:06:59,644
E infatti, in fondo è ciò che è
chiamato pila di routine genitore, modo elegante

161
00:06:59,644 --> 00:07:00,560
di dire che è principale.

162
00:07:00,560 --> 00:07:03,772
Così che chi chiama la funzione
f che stiamo parlando.

163
00:07:03,772 --> 00:07:05,230
Quindi questo è il fondo della pila.

164
00:07:05,230 --> 00:07:06,640
Indirizzo di ritorno è qualcosa di nuovo.

165
00:07:06,640 --> 00:07:08,810
E 'sempre stato lì,
sempre in quella foto.

166
00:07:08,810 --> 00:07:10,440
Abbiamo appena mai chiamato l'attenzione ad esso.

167
00:07:10,440 --> 00:07:15,290
Perché si scopre il modo in cui funziona è c
che quando una funzione richiama un altro,

168
00:07:15,290 --> 00:07:18,780
non fare solo gli argomenti che
funzione get inserito nello stack,

169
00:07:18,780 --> 00:07:22,470
non solo fare locale della funzione
variabili vengono inseriti nello stack,

170
00:07:22,470 --> 00:07:26,820
qualcosa chiamato un indirizzo di ritorno
Inoltre viene messa in pila.

171
00:07:26,820 --> 00:07:33,330
In particolare, se le chiamate principali Foo, principali di
proprio indirizzo in memoria, bue qualcosa,

172
00:07:33,330 --> 00:07:38,240
efficace viene messa in pila
in modo che quando f è fatto eseguirlo

173
00:07:38,240 --> 00:07:43,630
sa dove saltare indietro nel testo
segmento per continuare l'esecuzione.

174
00:07:43,630 --> 00:07:47,760
>> Quindi, se siamo qui concettualmente,
in principale, allora f viene chiamato.

175
00:07:47,760 --> 00:07:50,200
Come fa sapere che f
a comando manuale indietro?

176
00:07:50,200 --> 00:07:52,020
Beh, questo piccolo
breadcrumb in rosso qui,

177
00:07:52,020 --> 00:07:54,978
chiamato l'indirizzo di ritorno, solo
controlli, che cosa è l'indirizzo di ritorno?

178
00:07:54,978 --> 00:07:57,039
Oh, mi permetta di saltare di nuovo alla principale qui.

179
00:07:57,039 --> 00:07:59,080
E questo è un po '
di una semplificazione eccessiva,

180
00:07:59,080 --> 00:08:00,750
perché gli zeri e quelli
per principali sono tecnicamente

181
00:08:00,750 --> 00:08:01,967
qui nel segmento tecnologico.

182
00:08:01,967 --> 00:08:03,800
Ma questa è l'idea. f
deve solo sapere che cosa

183
00:08:03,800 --> 00:08:06,680
al punto in cui il controllo va infine indietro.

184
00:08:06,680 --> 00:08:09,790
>> Ma i computer modo
hanno da tempo stabilito le cose

185
00:08:09,790 --> 00:08:12,320
come variabili locali e
argomenti è come questo.

186
00:08:12,320 --> 00:08:17,180
Quindi, nella parte superiore di questa immagine nella
blu è lo stack frame per f, quindi tutto

187
00:08:17,180 --> 00:08:19,630
della memoria che f
in particolare è in uso.

188
00:08:19,630 --> 00:08:22,990
Quindi di conseguenza, si noti che
bar è in questa foto.

189
00:08:22,990 --> 00:08:23,980
Bar era il suo argomento.

190
00:08:23,980 --> 00:08:27,240
E noi dicemmo che gli argomenti a
funzioni vengono inseriti nello stack.

191
00:08:27,240 --> 00:08:29,910
E C, naturalmente, è
anche in questa foto.

192
00:08:29,910 --> 00:08:33,520
>> E solo per scopi di notazione,
notare in alto a sinistra

193
00:08:33,520 --> 00:08:37,020
è quello che sarebbe c staffa 0 e
poi leggermente verso il basso a destra

194
00:08:37,020 --> 00:08:38,220
è c staffa 11.

195
00:08:38,220 --> 00:08:41,240
Quindi, in altre parole, si può immaginare
che c'è una griglia di byte

196
00:08:41,240 --> 00:08:44,380
lì, prima delle quali è
superiore sinistro, inferiore di cui

197
00:08:44,380 --> 00:08:48,360
è l'ultimo di questi 12 byte.

198
00:08:48,360 --> 00:08:49,930
>> Ma ora cercano di avanzare rapidamente.

199
00:08:49,930 --> 00:08:55,580
Cosa sta per accadere se si passa
in un bar stringa che è più lungo di c?

200
00:08:55,580 --> 00:08:59,130
E non stiamo controllando se
è infatti più lungo di 12.

201
00:08:59,130 --> 00:09:03,146
Quale parte di questo quadro sta per
ottenere sovrascritto da byte 0, 1, 2, 3,

202
00:09:03,146 --> 00:09:07,890
dot dot dot, 11, e poi
male, 12, 13 fino al 19?

203
00:09:07,890 --> 00:09:11,820
Cosa succederà qui,
se ne deducono l'ordine

204
00:09:11,820 --> 00:09:14,790
che c staffa 0 è in alto
c staffa 11 è una sorta di basso

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

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

207
00:09:16,796 --> 00:09:19,260
>> PUBBLICO: Beh, sta andando
per sovrascrivere il char * bar.

208
00:09:19,260 --> 00:09:22,260
>> DAVID J. MALAN: Sì, sembra che
si sta andando a sovrascrivere char * bar.

209
00:09:22,260 --> 00:09:26,245
E peggio ancora, se si invia in un tempo molto lungo
stringa, si potrebbe anche sovrascrivere cosa?

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

211
00:09:27,460 --> 00:09:28,570
L'indirizzo di ritorno.

212
00:09:28,570 --> 00:09:31,380
Che ancora una volta, è come un
breadcrumb per dire al programma dove

213
00:09:31,380 --> 00:09:34,060
per andare indietro a quando f
è fatto di essere chiamato.

214
00:09:34,060 --> 00:09:37,140
>> Così che cosa cattivi di solito fare
è se si imbattono in un programma

215
00:09:37,140 --> 00:09:41,290
che sono curioso di sapere se è
sfruttabile, buggy in modo tale

216
00:09:41,290 --> 00:09:43,550
che lui o lei può prendere
vantaggio di tale bug,

217
00:09:43,550 --> 00:09:45,720
generalmente non ottengono
questo diritto la prima volta.

218
00:09:45,720 --> 00:09:48,590
Hanno appena iniziare a inviare, per esempio,
stringhe casuali nel vostro programma,

219
00:09:48,590 --> 00:09:50,260
se alla tastiera,
o francamente probabilmente

220
00:09:50,260 --> 00:09:52,740
scrivere un piccolo programma di appena
generano automaticamente le stringhe,

221
00:09:52,740 --> 00:09:55,430
e iniziare a battere il tuo programma
l'invio in un sacco di input diversi

222
00:09:55,430 --> 00:09:56,340
a diverse lunghezze.

223
00:09:56,340 --> 00:09:58,990
>> Non appena il tuo programma va in crash,
questa è una cosa incredibile.

224
00:09:58,990 --> 00:10:01,020
Perché vuol dire che
o lei ha scoperto

225
00:10:01,020 --> 00:10:02,660
quello che probabilmente è davvero un bug.

226
00:10:02,660 --> 00:10:05,830
E poi si possono ottenere più intelligente
e iniziare a concentrarsi più strettamente

227
00:10:05,830 --> 00:10:07,420
su come sfruttare il bug.

228
00:10:07,420 --> 00:10:11,480
In particolare, quello che lui o lei potrebbe
fare è inviare, nel migliore dei casi, ciao.

229
00:10:11,480 --> 00:10:12,210
No big deal.

230
00:10:12,210 --> 00:10:14,750
E 'una stringa che è sufficientemente breve.

231
00:10:14,750 --> 00:10:18,100
Ma cosa succede se lui o lei manda,
e noi generalizziamo come,

232
00:10:18,100 --> 00:10:20,890
attacco code-- così zeri
e quelli che fanno cose

233
00:10:20,890 --> 00:10:25,150
come rm-rf, che rimuovere tutto ciò
dal disco rigido o inviare spam

234
00:10:25,150 --> 00:10:27,000
o in qualche modo attaccare la macchina?

235
00:10:27,000 --> 00:10:29,570
>> Quindi, se ciascuno di questi
lettere A solo rappresenta,

236
00:10:29,570 --> 00:10:32,380
concettualmente, attaccare, attaccare,
attacco, attacco, codice cattivo

237
00:10:32,380 --> 00:10:36,410
che qualcun altro ha scritto, ma
se quella persona è abbastanza intelligente

238
00:10:36,410 --> 00:10:40,790
non solo di includere tutti
di quei RM-RFS, ma anche

239
00:10:40,790 --> 00:10:46,100
avere i suoi ultimi byte
essere un numero che corrisponde

240
00:10:46,100 --> 00:10:50,540
l'indirizzo del suo
o il proprio codice di attacco

241
00:10:50,540 --> 00:10:53,820
che lui o lei passava in appena
fornendo al prompt,

242
00:10:53,820 --> 00:10:58,760
si può effettivamente ingannare il computer
nel notare quando f è fatto esecuzione,

243
00:10:58,760 --> 00:11:02,400
oh, è il momento per me di saltare
torna l'indirizzo di ritorno rossa.

244
00:11:02,400 --> 00:11:06,070
Ma perché lui o lei ha in qualche modo
sovrapposte che indirizzo di ritorno

245
00:11:06,070 --> 00:11:09,602
con il proprio numero,
e sono abbastanza intelligente

246
00:11:09,602 --> 00:11:11,560
di aver configurato che
il numero di riferimento, come si

247
00:11:11,560 --> 00:11:13,740
vedere nel super top
angolo sinistro lì,

248
00:11:13,740 --> 00:11:18,020
l'indirizzo effettivo nel computer
la memoria di una parte del loro codice di attacco,

249
00:11:18,020 --> 00:11:21,740
un cattivo ragazzo può ingannare il computer
ad eseguire il proprio codice.

250
00:11:21,740 --> 00:11:23,700
>> E quel codice, ancora una volta, può essere qualsiasi cosa.

251
00:11:23,700 --> 00:11:26,120
E 'generalmente chiamato
codice shell, che è solo

252
00:11:26,120 --> 00:11:29,030
un modo per dire che non è
generalmente qualcosa di semplice come rm-rf.

253
00:11:29,030 --> 00:11:32,340
In realtà è qualcosa di simile a Bash,
o un vero programma che gli dà

254
00:11:32,340 --> 00:11:37,230
o il suo controllo programmatico per eseguire
qualsiasi altra cosa che vogliono.

255
00:11:37,230 --> 00:11:40,210
Così, in breve, tutto questo
deriva dal semplice fatto

256
00:11:40,210 --> 00:11:44,490
che questo bug coinvolto non controllare
i confini della propria matrice.

257
00:11:44,490 --> 00:11:47,250
E perché il modo
computer lavoro è che essi

258
00:11:47,250 --> 00:11:49,430
utilizzare lo stack da
efficace, concettualmente,

259
00:11:49,430 --> 00:11:54,830
bottom su un massimo, ma poi gli elementi
si spinge nello stack crescere verso il basso,

260
00:11:54,830 --> 00:11:56,624
questo è incredibilmente problematico.

261
00:11:56,624 --> 00:11:58,290
Ora, ci sono modi per aggirare questo.

262
00:11:58,290 --> 00:12:00,800
E, francamente, ci sono lingue
con cui risolvere questo.

263
00:12:00,800 --> 00:12:03,100
Java è immune, per esempio,
a questo particolare problema.

264
00:12:03,100 --> 00:12:04,110
Perché non ti danno i puntatori.

265
00:12:04,110 --> 00:12:05,943
Non danno si
indirizzi di memoria diretta.

266
00:12:05,943 --> 00:12:08,560
Quindi, con questo potere che abbiamo
toccare niente in memoria

267
00:12:08,560 --> 00:12:11,580
noi vogliamo arriva, è vero, grande rischio.

268
00:12:11,580 --> 00:12:12,430
>> Quindi tenete gli occhi aperti.

269
00:12:12,430 --> 00:12:14,596
Se, francamente, nei mesi
o anni a venire, in qualsiasi momento

270
00:12:14,596 --> 00:12:17,740
si legge su alcuni sfruttamento
di un programma o di un server,

271
00:12:17,740 --> 00:12:22,370
se avete mai visto un accenno di qualcosa
come un attacco di buffer overflow,

272
00:12:22,370 --> 00:12:25,390
o overflow dello stack è un altro tipo
di attacco, simile nello spirito,

273
00:12:25,390 --> 00:12:28,770
quanto ispira il sito web del
nome, se lo si conosce,

274
00:12:28,770 --> 00:12:33,170
è tutto parlando solo
traboccante la dimensione di qualche personaggio

275
00:12:33,170 --> 00:12:36,200
array o alcune serie più in generale.

276
00:12:36,200 --> 00:12:38,822
Hai domande, poi, su questo?

277
00:12:38,822 --> 00:12:39,780
Non provateci a casa.

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

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

280
00:12:42,300 --> 00:12:47,270
Quindi malloc finora è stato il nostro nuovo
amico in che siamo in grado di allocare memoria

281
00:12:47,270 --> 00:12:50,540
che non necessariamente sapere in
avanziamo che vogliamo così non abbiamo

282
00:12:50,540 --> 00:12:52,920
codificare nel nostro
numeri di programma come 12.

283
00:12:52,920 --> 00:12:55,550
Una volta che l'utente ci dice quanto
Dati lui o lei vuole di ingresso,

284
00:12:55,550 --> 00:12:58,000
possiamo malloc che la quantità di memoria.

285
00:12:58,000 --> 00:13:01,484
>> Così malloc si scopre, per la
misura abbiamo usato esso,

286
00:13:01,484 --> 00:13:03,900
esplicitamente l'ultima volta, e poi
voi ragazzi sono state usando

287
00:13:03,900 --> 00:13:08,160
per GetString inconsapevolmente per
diverse settimane, tutti della memoria di malloc

288
00:13:08,160 --> 00:13:09,820
deriva dal cosiddetto heap.

289
00:13:09,820 --> 00:13:13,852
Ed è per questo getString, per esempio,
può allocare memoria dinamicamente

290
00:13:13,852 --> 00:13:16,060
senza sapere cosa si sta
andando a digitare in anticipo,

291
00:13:16,060 --> 00:13:21,520
si restituire un puntatore a quel ricordo,
e che la memoria è ancora il vostro da mantenere,

292
00:13:21,520 --> 00:13:24,080
anche dopo getString ritorni.

293
00:13:24,080 --> 00:13:27,450
Perché richiamo dopo tutto quello che il
pila è costantemente andando su e giù,

294
00:13:27,450 --> 00:13:27,950
su e giù.

295
00:13:27,950 --> 00:13:30,230
E appena va
verso il basso, che significa qualsiasi memoria

296
00:13:30,230 --> 00:13:33,030
questa funzione utilizzata dovrebbe
non essere utilizzato da chiunque altro.

297
00:13:33,030 --> 00:13:34,570
Si tratta di valori di immondizia ora.

298
00:13:34,570 --> 00:13:36,120
>> Ma l'heap è qui.

299
00:13:36,120 --> 00:13:39,360
E cosa c'è di bello malloc è che
quando malloc alloca la memoria qui,

300
00:13:39,360 --> 00:13:42,070
non è influenzato, per la
maggior parte, dallo stack.

301
00:13:42,070 --> 00:13:46,000
E così ogni funzione può accedere
memoria che è stata malloc'd,

302
00:13:46,000 --> 00:13:49,120
anche da una funzione come getString,
anche dopo che è restituito.

303
00:13:49,120 --> 00:13:51,700
>> Ora, il contrario di malloc è gratuito.

304
00:13:51,700 --> 00:13:53,900
E infatti, la regola
necessario avviare l'adozione di

305
00:13:53,900 --> 00:13:58,950
è qualsiasi, qualsiasi, ogni volta che si utilizza malloc
è necessario te stesso uso gratuito, alla fine,

306
00:13:58,950 --> 00:14:00,280
sullo stesso puntatore.

307
00:14:00,280 --> 00:14:03,289
Per tutto questo tempo abbiamo scriviamo
buggy, codice buggy, per molte ragioni.

308
00:14:03,289 --> 00:14:05,580
Ma uno dei quali è stato
utilizzando la libreria CS50, che

309
00:14:05,580 --> 00:14:09,010
si è volutamente
buggy, si perde la memoria.

310
00:14:09,010 --> 00:14:11,410
Ogni volta che hai chiamato getString
nelle ultime settimane

311
00:14:11,410 --> 00:14:13,870
stiamo chiedendo il funzionamento
sistema, Linux, per la memoria.

312
00:14:13,870 --> 00:14:15,780
E non avete mai dato una volta indietro.

313
00:14:15,780 --> 00:14:17,730
E questo non è, in
in pratica, una buona cosa.

314
00:14:17,730 --> 00:14:20,330
>> E Valgrind, uno dei
strumenti introdotti in Pset 4,

315
00:14:20,330 --> 00:14:22,900
è tutto su di te aiutare
ora trovare bug del genere.

316
00:14:22,900 --> 00:14:27,060
Ma fortunatamente per Pset 4 non è necessario
utilizzare la libreria CS50 o getString.

317
00:14:27,060 --> 00:14:31,220
Quindi eventuali bug relativi alla memoria sono
in ultima analisi, sta per essere il vostro.

318
00:14:31,220 --> 00:14:34,060
>> Quindi malloc è più di un semplice
conveniente per questo scopo.

319
00:14:34,060 --> 00:14:37,420
Possiamo davvero ora di risolvere
fondamentalmente diversi problemi,

320
00:14:37,420 --> 00:14:41,640
e fondamentalmente risolvere i problemi più
efficacemente come da promessa settimana zeri.

321
00:14:41,640 --> 00:14:44,720
Finora questo è il più sexy
struttura dati che abbiamo avuto.

322
00:14:44,720 --> 00:14:47,804
E da struttura di dati Volevo solo dire
un modo di memoria concettualizzare

323
00:14:47,804 --> 00:14:50,720
in un modo che va oltre solo dicendo,
questo è un int, questo è un char.

324
00:14:50,720 --> 00:14:52,930
Possiamo iniziare a cose del cluster insieme.

325
00:14:52,930 --> 00:14:54,460
>> Quindi un array sembrava questo.

326
00:14:54,460 --> 00:14:57,270
E quello che era fondamentale in circa
array è che ti dà

327
00:14:57,270 --> 00:14:59,724
back-to-back pezzi di
memoria, ciascuno dei quali

328
00:14:59,724 --> 00:15:02,765
sta per essere dello stesso tipo, int,
int, int, int, o char, char, char,

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

330
00:15:03,330 --> 00:15:04,496
Ma ci sono alcuni aspetti negativi.

331
00:15:04,496 --> 00:15:06,570
Questo, per esempio, è
un array di dimensione sei.

332
00:15:06,570 --> 00:15:10,650
Supponiamo di riempire questo array con sei
numeri e poi, per qualsiasi motivo,

333
00:15:10,650 --> 00:15:13,187
l'utente vuole dare
si un settimo numero.

334
00:15:13,187 --> 00:15:14,020
Dove la metti?

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

336
00:15:15,490 --> 00:15:18,990
>> Qual è la soluzione se si dispone di
creato un array in pila,

337
00:15:18,990 --> 00:15:22,030
per esempio, solo con la settimana
due notazione che abbiamo introdotto,

338
00:15:22,030 --> 00:15:23,730
di parentesi quadre con un numero dentro?

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

340
00:15:25,160 --> 00:15:27,260
Beh, hai sei
numeri in queste caselle.

341
00:15:27,260 --> 00:15:28,530
Quali sarebbero i tuoi istinti essere?

342
00:15:28,530 --> 00:15:29,973
Dove vorreste dire?

343
00:15:29,973 --> 00:15:30,860
>> PUBBLICO: [incomprensibile]

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

345
00:15:31,315 --> 00:15:32,380
>> PUBBLICO: Mettere sul fine.

346
00:15:32,380 --> 00:15:33,796
>> DAVID J. MALAN: Metti sul fine.

347
00:15:33,796 --> 00:15:35,880
Quindi poco più a destra,
al di fuori di questa casella.

348
00:15:35,880 --> 00:15:38,710
Quale sarebbe bello, ma
risulta non è possibile farlo.

349
00:15:38,710 --> 00:15:41,350
Perché se non hai chiesto
per questo pezzo di memoria,

350
00:15:41,350 --> 00:15:44,490
potrebbe essere una coincidenza che questa
viene utilizzato da qualche altra variabile

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

352
00:15:45,030 --> 00:15:49,210
Pensate di una settimana o giù di lì, quando abbiamo posto
i nomi Zamyla e Davin e Gabe di

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

354
00:15:49,930 --> 00:15:51,638
Erano letteralmente
back to back to back.

355
00:15:51,638 --> 00:15:53,550
Quindi non possiamo necessariamente
fiducia che tutto ciò che di

356
00:15:53,550 --> 00:15:55,800
qui è disponibile per me da usare.

357
00:15:55,800 --> 00:15:56,990
>> Quindi, che cosa potrebbe fare?

358
00:15:56,990 --> 00:16:00,282
Beh, una volta che la realizzazione
bisogno di un array di dimensione sette,

359
00:16:00,282 --> 00:16:02,490
si può solo creare un
array di dimensione sette quindi utilizzare

360
00:16:02,490 --> 00:16:05,950
un ciclo for o un ciclo while,
copiarlo nella nuova matrice,

361
00:16:05,950 --> 00:16:09,680
e quindi in qualche modo solo sbarazzarsi di
questo array o semplicemente smettere di usarlo.

362
00:16:09,680 --> 00:16:12,130
Ma non è particolarmente efficiente.

363
00:16:12,130 --> 00:16:15,340
In breve, gli array non lasciare
si ridimensiona dinamicamente.

364
00:16:15,340 --> 00:16:17,900
>> Così da un lato si ottiene
accesso casuale, che è incredibile.

365
00:16:17,900 --> 00:16:20,108
Perché ci permette di fare cose
come divide et impera,

366
00:16:20,108 --> 00:16:23,100
ricerca binaria, tutti di che abbiamo
parlato sullo schermo qui.

367
00:16:23,100 --> 00:16:24,950
Ma si dipinge da soli in un angolo.

368
00:16:24,950 --> 00:16:27,810
Non appena si preme
la fine della matrice,

369
00:16:27,810 --> 00:16:29,980
devi fare molto
un'operazione costosa

370
00:16:29,980 --> 00:16:33,910
o scrivere un sacco di codice
per ora affrontare tale problema.

371
00:16:33,910 --> 00:16:36,680
>> Così che cosa se invece avessimo
qualcosa chiamato un elenco,

372
00:16:36,680 --> 00:16:38,820
o una lista concatenata in particolare?

373
00:16:38,820 --> 00:16:41,930
Che cosa succede se invece di avere
rettangoli back to back to back,

374
00:16:41,930 --> 00:16:45,730
abbiamo rettangoli che lasciano un po '
po 'di spazio di manovra tra di loro?

375
00:16:45,730 --> 00:16:49,670
E anche se ho disegnato questo
foto o adattato questa immagine

376
00:16:49,670 --> 00:16:54,696
da uno dei testi qui per tornare alla
back to back molto ordinata, in realtà,

377
00:16:54,696 --> 00:16:56,820
uno di quei rettangoli
potrebbe essere qui in memoria.

378
00:16:56,820 --> 00:16:58,028
Uno di loro potrebbe essere qui.

379
00:16:58,028 --> 00:17:00,420
Uno di loro potrebbe essere qui,
qui, e così via.

380
00:17:00,420 --> 00:17:02,910
>> Ma cosa succede se abbiamo pareggiato,
in questo caso, frecce

381
00:17:02,910 --> 00:17:05,650
che in qualche modo collegare questi
rettangoli insieme?

382
00:17:05,650 --> 00:17:08,170
Infatti, abbiamo visto un tecnico
incarnazione di una freccia.

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

384
00:17:09,839 --> 00:17:13,710
Cosa abbiamo utilizzato negli ultimi
giorni che, sotto la cappa,

385
00:17:13,710 --> 00:17:15,210
è rappresentativo di una freccia?

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

387
00:17:16,290 --> 00:17:17,349
Un puntatore, giusto?

388
00:17:17,349 --> 00:17:19,780
>> Così che cosa se, invece di
basta memorizzare i numeri,

389
00:17:19,780 --> 00:17:23,130
come 9, 17, 22, 26, 34,
quello che se non memorizzato

390
00:17:23,130 --> 00:17:27,079
solo un numero ma un puntatore
accanto a ogni tale numero?

391
00:17:27,079 --> 00:17:30,690
Così tanto come si farebbe infilare un
ago attraverso un sacco di tessuto,

392
00:17:30,690 --> 00:17:32,950
le cose in qualche modo di legatura
insieme, allo stesso modo può

393
00:17:32,950 --> 00:17:35,550
noi con i puntatori, come
incarnata da frecce qui,

394
00:17:35,550 --> 00:17:38,550
tipo di tessere insieme
questi singoli rettangoli

395
00:17:38,550 --> 00:17:41,780
da efficace utilizzando un puntatore
accanto a ciascun numero

396
00:17:41,780 --> 00:17:46,065
punti a qualche numero successivo, che
punti a, a sua volta, qualche numero successivo?

397
00:17:46,065 --> 00:17:47,940
In altre parole, ciò
se davvero volessimo

398
00:17:47,940 --> 00:17:49,820
di implementare qualcosa di simile?

399
00:17:49,820 --> 00:17:53,610
Ebbene, purtroppo, questi rettangoli,
almeno quella con 9, 17, 22,

400
00:17:53,610 --> 00:17:57,040
e così via, questi non sono più
belle piazze con numeri singoli.

401
00:17:57,040 --> 00:17:59,960
Il fondo, rettangolo
inferiore a 9, per esempio,

402
00:17:59,960 --> 00:18:04,330
rappresenta ciò che dovrebbe
essere un puntatore, 32 bit.

403
00:18:04,330 --> 00:18:09,460
Ora, io non sono ancora a conoscenza di qualsiasi tipo di dati
in C che offre non solo un int

404
00:18:09,460 --> 00:18:11,630
tuttavia il puntatore del tutto.

405
00:18:11,630 --> 00:18:15,020
>> Quindi qual è la soluzione, se vogliamo
a inventare la nostra risposta a questo?

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

407
00:18:15,760 --> 00:18:16,640
>> PUBBLICO: [incomprensibile]

408
00:18:16,640 --> 00:18:17,360
>> DAVID J. MALAN: Che cos'è?

409
00:18:17,360 --> 00:18:17,880
>> PUBBLICO: Nuova struttura.

410
00:18:17,880 --> 00:18:19,590
>> DAVID J. MALAN: Sì, quindi perché
Non creiamo una nuova struttura,

411
00:18:19,590 --> 00:18:20,920
o in C, una struttura?

412
00:18:20,920 --> 00:18:25,990
Abbiamo visto le strutture prima, se per breve tempo,
dove abbiamo affrontato con una struttura studente

413
00:18:25,990 --> 00:18:27,780
come questo, che aveva un nome e una casa.

414
00:18:27,780 --> 00:18:31,980
In Pset 3 breakout si usa un intero
mazzo di GRect structs-- e GOvals

415
00:18:31,980 --> 00:18:34,810
che Stanford creato per
informazioni sul cluster insieme.

416
00:18:34,810 --> 00:18:38,580
Così che cosa se prendiamo questa stessa idea di
le parole chiave "typedef" e "struct"

417
00:18:38,580 --> 00:18:42,890
e poi alcune cose specifiche per studente,
ed evolvere questo in quanto segue:

418
00:18:42,890 --> 00:18:46,210
typedef struct node-- e il nodo è
solo un computer science molto generico

419
00:18:46,210 --> 00:18:49,980
termine per qualcosa in una struttura di dati,
un contenitore in una struttura dati.

420
00:18:49,980 --> 00:18:53,900
Un nodo Rivendico sta per avere
un int n, del tutto semplice,

421
00:18:53,900 --> 00:18:58,810
e poi un po 'più criptico,
questa seconda linea, nodo struct * prossimo.

422
00:18:58,810 --> 00:19:01,300
Ma in termini meno tecnici,
che cosa è che seconda linea

423
00:19:01,300 --> 00:19:02,980
di codice all'interno delle parentesi graffe?

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

425
00:19:03,737 --> 00:19:04,851
>> PUBBLICO: [incomprensibile]

426
00:19:04,851 --> 00:19:06,600
DAVID J. MALAN: A
puntatore a un altro nodo.

427
00:19:06,600 --> 00:19:09,910
Quindi è vero, la sintassi un po 'criptica.

428
00:19:09,910 --> 00:19:13,250
Ma se lo si legge alla lettera,
successivo è il nome di una variabile.

429
00:19:13,250 --> 00:19:14,410
Qual è il suo tipo di dati?

430
00:19:14,410 --> 00:19:18,206
E 'un po' prolissa questa volta,
ma è di tipo struct nodo *.

431
00:19:18,206 --> 00:19:22,960
Ogni volta che abbiamo visto qualcosa di stella, che
significa che è un puntatore a quel tipo di dati.

432
00:19:22,960 --> 00:19:26,810
Così la prossima è apparentemente un
puntatore ad una struct nodo.

433
00:19:26,810 --> 00:19:28,310
>> Ora, che cosa è un nodo struct?

434
00:19:28,310 --> 00:19:31,044
Beh, nota vedete quelle
stesse parole in alto a destra.

435
00:19:31,044 --> 00:19:33,960
E in effetti, si vede anche la parola
"Nodo" qui in basso a sinistra.

436
00:19:33,960 --> 00:19:35,640
E questo è in realtà solo una comodità.

437
00:19:35,640 --> 00:19:39,930
Si noti che nella nostra definizione studente
c'è la parola "studente" solo una volta.

438
00:19:39,930 --> 00:19:42,510
E questo perché uno studente
oggetto non era autoreferenziale.

439
00:19:42,510 --> 00:19:45,340
Non c'è nulla all'interno di uno studente
che deve puntare a un altro studente,

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

441
00:19:45,610 --> 00:19:47,630
Sarebbe una sorta di
strano nel mondo reale.

442
00:19:47,630 --> 00:19:50,880
>> Ma con un nodo in una collegata
lista, noi vogliamo un nodo

443
00:19:50,880 --> 00:19:53,970
essere referenziale di un oggetto simile.

444
00:19:53,970 --> 00:19:57,900
E così notare il cambiamento qui non è
solo ciò che c'è dentro le parentesi graffe.

445
00:19:57,900 --> 00:20:00,800
Ma aggiungiamo la parola "nodo"
nella parte superiore e

446
00:20:00,800 --> 00:20:02,930
aggiungendo al fondo
in luogo di "studente".

447
00:20:02,930 --> 00:20:06,000
E questo è solo un dettaglio tecnico
in modo che, ancora una volta, la struttura dati

448
00:20:06,000 --> 00:20:11,380
può essere auto-referenziale, in modo che un
nodo può puntare ad un altro tale nodo.

449
00:20:11,380 --> 00:20:13,840
>> Così che cosa è questo in definitiva
andando a significare per noi?

450
00:20:13,840 --> 00:20:17,560
Beh, si, questa roba dentro
è il contenuto del nostro nodo.

451
00:20:17,560 --> 00:20:19,360
Questa cosa qui,
in alto a destra, è proprio così

452
00:20:19,360 --> 00:20:20,860
che, ancora una volta, si può fare riferimento a noi stessi.

453
00:20:20,860 --> 00:20:23,401
E poi la roba più esterno,
anche se il nodo è un nuovo termine,

454
00:20:23,401 --> 00:20:25,500
forse, è ancora il
stesso come studente e quello

455
00:20:25,500 --> 00:20:27,520
era sotto il cofano in SPL.

456
00:20:27,520 --> 00:20:31,095
>> Quindi, se ora volevamo iniziare
l'attuazione del presente lista collegata,

457
00:20:31,095 --> 00:20:33,220
come potremmo tradurre
qualcosa di simile al codice?

458
00:20:33,220 --> 00:20:35,350
Beh, diciamo solo vedere un
esempio di un programma che

459
00:20:35,350 --> 00:20:36,840
in realtà utilizza una lista collegata.

460
00:20:36,840 --> 00:20:40,870
Tra il codice di distribuzione di oggi
è un programma chiamato List Zero.

461
00:20:40,870 --> 00:20:44,980
E se corro questo ho creato un super
semplice GUI, Graphical User Interface,

462
00:20:44,980 --> 00:20:46,460
ma è davvero solo printf.

463
00:20:46,460 --> 00:20:50,930
E ora io stesso ho dato un paio di menu
options-- Delete, Insert, Ricerca,

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

465
00:20:51,750 --> 00:20:52,630
E Quit.

466
00:20:52,630 --> 00:20:55,970
Questi sono solo operazioni comuni in un
struttura dati nota come un elenco di link.

467
00:20:55,970 --> 00:20:58,409
>> Ora, Elimina sta per
eliminare un numero dalla lista.

468
00:20:58,409 --> 00:21:00,200
Inserisci sta per aggiungere
un numero all'elenco.

469
00:21:00,200 --> 00:21:02,181
Ricerca sta a guardare
per numero nell'elenco.

470
00:21:02,181 --> 00:21:04,930
E traversata è solo un modo di fantasia
di dire, a piedi attraverso la lista,

471
00:21:04,930 --> 00:21:06,245
stamparlo, ma questo è tutto.

472
00:21:06,245 --> 00:21:07,720
Non modificare in alcun modo.

473
00:21:07,720 --> 00:21:08,570
>> Quindi proviamo questo.

474
00:21:08,570 --> 00:21:10,160
Andiamo avanti e digitare 2.

475
00:21:10,160 --> 00:21:12,710
E poi ho intenzione di
inserire il numero, dire 9.

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

477
00:21:13,620 --> 00:21:17,480
E ora il mio programma è solo
programmato per dire, la lista è ora 9.

478
00:21:17,480 --> 00:21:20,190
Ora, se vado avanti e
non inserire di nuovo, lasciare

479
00:21:20,190 --> 00:21:23,680
andare avanti e Zoom indietro e digitare 17.

480
00:21:23,680 --> 00:21:25,770
Ora la mia lista è 9, quindi 17.

481
00:21:25,770 --> 00:21:27,750
Se lo faccio inserire di nuovo, cerchiamo di saltare uno.

482
00:21:27,750 --> 00:21:32,400
Invece di 22, secondo l'immagine che abbiamo
stato a guardare qui, mi permetta di saltare avanti

483
00:21:32,400 --> 00:21:34,630
e inserire 26 successivo.

484
00:21:34,630 --> 00:21:36,230
Quindi ho intenzione di digitare 26.

485
00:21:36,230 --> 00:21:37,755
La lista è come mi aspetto.

486
00:21:37,755 --> 00:21:40,630
Ma ora, solo per vedere se questo codice
sta per essere flessibile, lasciami ora

487
00:21:40,630 --> 00:21:43,520
tipo 22, che almeno
concettualmente, se siamo

488
00:21:43,520 --> 00:21:46,520
Tenendo questo allineati, che è davvero
sarà un altro obiettivo in questo momento,

489
00:21:46,520 --> 00:21:48,690
dovrebbe andare tra 17 e 26.

490
00:21:48,690 --> 00:21:50,270
Così ho colpito Invio.

491
00:21:50,270 --> 00:21:51,380
Infatti, che funziona.

492
00:21:51,380 --> 00:21:54,950
E così ora lasciatemi inserisco l'
ultimo, per l'immagine, 34.

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

494
00:21:55,450 --> 00:21:58,980
Quindi per ora mi permetta di stabilire che
Elimina e Traverse e ricerca fanno,

495
00:21:58,980 --> 00:21:59,760
infatti, lavorare.

496
00:21:59,760 --> 00:22:04,180
In realtà, se non me ne corro Cerca, cerchiamo di
cercare il numero 22, Enter.

497
00:22:04,180 --> 00:22:05,010
Ha trovato 22.

498
00:22:05,010 --> 00:22:07,580
Quindi questo è ciò che questo
programma Lista Zero fa.

499
00:22:07,580 --> 00:22:10,230
>> Ma ciò che sta realmente succedendo
su che implementa questo?

500
00:22:10,230 --> 00:22:14,530
Beh, prima avrei potuto, e anzi
Io ce l'ho, un file chiamato list0.h.

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

502
00:22:16,540 --> 00:22:20,690
E da qualche parte c'è questo
linea, typedef, struct nodo,

503
00:22:20,690 --> 00:22:24,850
poi ho i miei parentesi graffe, int n, e
allora struct-- qual era la definizione?

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

505
00:22:26,530 --> 00:22:28,545
Struct node successivo.

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

507
00:22:29,920 --> 00:22:31,045
Quindi abbiamo bisogno della stella.

508
00:22:31,045 --> 00:22:33,420
Ora tecnicamente entriamo in
l'abitudine di disegnare qui.

509
00:22:33,420 --> 00:22:35,670
Si potrebbe vedere i libri di testo e
riferimenti online fanno lì.

510
00:22:35,670 --> 00:22:36,660
E 'funzionalmente equivalente.

511
00:22:36,660 --> 00:22:37,980
In realtà, questo è un po 'più tipico.

512
00:22:37,980 --> 00:22:40,563
Ma sarò coerente con quanto
abbiamo fatto l'ultima volta e facciamo.

513
00:22:40,563 --> 00:22:42,350
E poi, infine, ho intenzione di fare questo.

514
00:22:42,350 --> 00:22:45,550
>> Quindi, in un file di intestazione
da qualche parte, in list0.h

515
00:22:45,550 --> 00:22:49,200
oggi è questa definizione struct,
e forse alcune altre cose.

516
00:22:49,200 --> 00:22:52,580
Intanto in list0c c'è
sta per essere un paio di cose.

517
00:22:52,580 --> 00:22:54,740
Ma stiamo andando a poco
cominciare e non finire questo.

518
00:22:54,740 --> 00:22:59,690
List0.h è un file che voglio
di includere nel mio file C.

519
00:22:59,690 --> 00:23:03,910
E poi ad un certo punto sono
andando ad avere int, principale, annullare.

520
00:23:03,910 --> 00:23:06,530
E poi ho intenzione di
hanno qualche cosa da fare è qui.

521
00:23:06,530 --> 00:23:10,620
Ho anche intenzione di avere un
prototipo, come il vuoto, la ricerca, int,

522
00:23:10,620 --> 00:23:13,610
n, il cui scopo nella vita è
per la ricerca di un elemento.

523
00:23:13,610 --> 00:23:18,310
E poi qui rivendico in
codice di oggi, vuoto, di ricerca, int, n,

524
00:23:18,310 --> 00:23:21,020
nessun punto e virgola ma parentesi graffe aperte.

525
00:23:21,020 --> 00:23:25,049
Ed ora voglio cercare in qualche modo
per un elemento in questo elenco.

526
00:23:25,049 --> 00:23:27,340
Ma non abbiamo abbastanza
informazioni sullo schermo ancora.

527
00:23:27,340 --> 00:23:29,800
Non ho in realtà
rappresentato la lista stessa.

528
00:23:29,800 --> 00:23:33,070
Quindi un modo che potremmo implementare
una lista collegata a un programma

529
00:23:33,070 --> 00:23:37,520
è che tipo di voglia di fare qualcosa
come dichiaro collegati elenco qui.

530
00:23:37,520 --> 00:23:40,520
Per semplicità, ho intenzione di fare
questo mondiale, anche se in generale si

531
00:23:40,520 --> 00:23:41,645
non dovrebbe fare questo troppo.

532
00:23:41,645 --> 00:23:43,260
Ma sarà semplificare questo esempio.

533
00:23:43,260 --> 00:23:45,890
Quindi voglio dichiarare
una lista collegata qui.

534
00:23:45,890 --> 00:23:47,010
Ora, come potrei farlo?

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

536
00:23:48,810 --> 00:23:50,750
>> Ecco l'immagine di una lista collegata.

537
00:23:50,750 --> 00:23:53,030
E non ho davvero
so al momento come

538
00:23:53,030 --> 00:23:56,710
Ho intenzione di andare su rappresentanza
tante cose con un solo

539
00:23:56,710 --> 00:23:58,040
variabile in memoria.

540
00:23:58,040 --> 00:23:59,160
Ma ripensare un attimo.

541
00:23:59,160 --> 00:24:00,830
Per tutto questo tempo abbiamo avuto
corde, che poi

542
00:24:00,830 --> 00:24:02,913
rivelata matrici di
personaggi, che poi

543
00:24:02,913 --> 00:24:05,740
rivelata solo un puntatore
al primo carattere

544
00:24:05,740 --> 00:24:08,890
in un array di caratteri
che è nullo terminato.

545
00:24:08,890 --> 00:24:13,530
Così da questa logica, e con questo
immagine tipo di semina vostri pensieri,

546
00:24:13,530 --> 00:24:17,964
Che bisogno abbiamo effettivamente scriviamo nel nostro
codice per rappresentare una lista concatenata?

547
00:24:17,964 --> 00:24:21,130
Quanto di queste informazioni abbiamo bisogno
per catturare in codice C, diresti?

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

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

550
00:24:23,154 --> 00:24:24,738
>> PUBBLICO: Abbiamo bisogno di un puntatore a un nodo.

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

552
00:24:26,237 --> 00:24:29,320
In particolare, quale nodo sarebbe la tua
istinti essere quello di mantenere un puntatore a?

553
00:24:29,320 --> 00:24:30,026
>> PUBBLICO: Il primo nodo.

554
00:24:30,026 --> 00:24:31,942
>> DAVID J. MALAN: Sì,
probabilmente solo il primo.

555
00:24:31,942 --> 00:24:34,030
E notare, il primo
nodo è una forma diversa.

556
00:24:34,030 --> 00:24:37,690
E 'solo la metà della dimensione della struttura,
perché è davvero solo un puntatore.

557
00:24:37,690 --> 00:24:44,650
Che cosa si può davvero fare è dichiarare
una lista collegata di essere nodo di tipo *.

558
00:24:44,650 --> 00:24:47,780
E facciamo solo chiamano prima
e inizializzarla a null.

559
00:24:47,780 --> 00:24:49,910
Quindi nulla, ancora una volta, è venuta
nella foto qui.

560
00:24:49,910 --> 00:24:53,620
Non solo è nullo utilizzato come come una speciale
valore di ritorno per le cose come getString

561
00:24:53,620 --> 00:24:57,770
e malloc, null è anche lo zero
puntatore, la mancanza di un puntatore,

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

563
00:24:58,430 --> 00:25:00,309
Significa solo nulla è ancora qui.

564
00:25:00,309 --> 00:25:02,100
Ora prima, avrei potuto
chiamato questo nulla.

565
00:25:02,100 --> 00:25:04,200
Avrei potuto chiamato "lista"
o un qualsiasi numero di altre cose.

566
00:25:04,200 --> 00:25:06,960
Ma sto chiamando "prima" in modo che
Linee it up con questa immagine.

567
00:25:06,960 --> 00:25:10,280
Quindi, proprio come una stringa può essere rappresentato
con l'indirizzo del primo byte,

568
00:25:10,280 --> 00:25:11,280
così può una lista collegata.

569
00:25:11,280 --> 00:25:13,480
E vedremo altri dati
Strutture essere rappresentati

570
00:25:13,480 --> 00:25:16,700
con un solo puntatore,
una freccia a 32 bit, che indica

571
00:25:16,700 --> 00:25:18,740
al primo nodo della struttura.

572
00:25:18,740 --> 00:25:20,340
>> Ma ora cerchiamo di anticipare un problema.

573
00:25:20,340 --> 00:25:23,230
Se sto solo ricordando
nel mio programma l'indirizzo

574
00:25:23,230 --> 00:25:27,220
del primo nodo, il primo
rettangolo in questa struttura dati,

575
00:25:27,220 --> 00:25:31,760
quello che era meglio essere il caso per il
l'attuazione del resto della mia lista?

576
00:25:31,760 --> 00:25:35,820
Che cosa è un dettaglio fondamentale che sta succedendo
per garantire questo funziona davvero?

577
00:25:35,820 --> 00:25:39,250
E per "funziona davvero" I
media, molto simile a una corda,

578
00:25:39,250 --> 00:25:42,180
ci lascia andare dal primo carattere
in nome di Davin al secondo,

579
00:25:42,180 --> 00:25:44,755
al terzo, al
quarto, fino alla fine,

580
00:25:44,755 --> 00:25:47,880
come facciamo a sapere quando siamo alla fine
di una lista collegata che assomiglia a questo?

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

582
00:25:50,035 --> 00:25:50,660
Quando è nullo.

583
00:25:50,660 --> 00:25:53,640
E ho rappresentato questa sorta di come
come una forza ingegnere elettrico,

584
00:25:53,640 --> 00:25:56,420
con la piccola messa a terra
simbolo, di sorta.

585
00:25:56,420 --> 00:25:58,246
Ma che vuol dire proprio nulla in questo caso.

586
00:25:58,246 --> 00:26:00,370
Si può disegnare qualsiasi numero
di modi, ma questo autore

587
00:26:00,370 --> 00:26:02,800
è successo a utilizzare questo simbolo qui.

588
00:26:02,800 --> 00:26:06,260
>> Finché stiamo tesatura
tutti questi nodi insieme,

589
00:26:06,260 --> 00:26:08,600
solo ricordare dove
il primo è, così a lungo

590
00:26:08,600 --> 00:26:11,760
come abbiamo messo un simbolo speciale
l'ultimo nodo della lista,

591
00:26:11,760 --> 00:26:15,130
e useremo nulla, perché è
quello che abbiamo a nostra disposizione,

592
00:26:15,130 --> 00:26:16,480
questo elenco è completo.

593
00:26:16,480 --> 00:26:20,190
E anche se io solo darvi un puntatore a
il primo elemento, si, il programmatore,

594
00:26:20,190 --> 00:26:22,486
può certamente accedere al resto.

595
00:26:22,486 --> 00:26:24,360
Ma lasciamo le vostre menti
vagare un po ',

596
00:26:24,360 --> 00:26:26,140
se non sono già
abbastanza wandered-- ciò che è

597
00:26:26,140 --> 00:26:28,723
sarà il tempo di esecuzione di
trovare nulla in questa lista?

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

599
00:26:30,450 --> 00:26:33,470
Dannazione, è grande O di n,
che non è male, in tutta onestà.

600
00:26:33,470 --> 00:26:34,800
Ma è lineare.

601
00:26:34,800 --> 00:26:37,980
Abbiamo dato a ciò caratteristica
di array spostando più

602
00:26:37,980 --> 00:26:43,130
verso questa immagine di dinamica
tessuti insieme o nodi collegati?

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

604
00:26:44,970 --> 00:26:46,687
Abbiamo dato l'accesso casuale.

605
00:26:46,687 --> 00:26:48,770
Un array è bello perché
matematicamente tutto

606
00:26:48,770 --> 00:26:50,340
è back to back to back to back.

607
00:26:50,340 --> 00:26:52,370
Anche se questa immagine
sembra piuttosto, e anche

608
00:26:52,370 --> 00:26:55,830
anche se sembra che questi nodi
sono ben distanziati, in realtà

609
00:26:55,830 --> 00:26:56,830
potrebbero essere ovunque.

610
00:26:56,830 --> 00:27:01,590
OX1, Ox50, Ox123, Ox99, questi
nodi potrebbero essere ovunque.

611
00:27:01,590 --> 00:27:05,960
Poiché malloc fa allocare memoria
dal mucchio, ma ovunque nel mucchio.

612
00:27:05,960 --> 00:27:09,080
Non necessariamente sapere che è
sta per essere back to back to back.

613
00:27:09,080 --> 00:27:12,460
E così questa immagine nella realtà di
non andare a essere abbastanza questa bella.

614
00:27:12,460 --> 00:27:16,140
>> Così sta andando a prendere un po 'di
lavorare per implementare questa funzione.

615
00:27:16,140 --> 00:27:17,880
Quindi cerchiamo di implementare la ricerca adesso.

616
00:27:17,880 --> 00:27:20,250
E vedremo una specie di
modo intelligente di fare questo.

617
00:27:20,250 --> 00:27:24,660
Quindi se io sono una funzione di ricerca e
Ho dato una variabile, intero n

618
00:27:24,660 --> 00:27:28,490
a cercare, ho bisogno di sapere il
nuova sintassi per guardare dentro

619
00:27:28,490 --> 00:27:32,400
di una struttura che è
indicato, per trovare n.

620
00:27:32,400 --> 00:27:33,210
Quindi cerchiamo di fare questo.

621
00:27:33,210 --> 00:27:36,030
>> Così prima ho intenzione di andare
avanti e dichiarare un nodo *.

622
00:27:36,030 --> 00:27:39,400
E ho intenzione di chiamare
puntatore, solo per convenzione.

623
00:27:39,400 --> 00:27:41,710
E ho intenzione di inizializzare a prima.

624
00:27:41,710 --> 00:27:43,770
E ora posso fare questo
in un numero di modi.

625
00:27:43,770 --> 00:27:45,436
Ma ho intenzione di adottare un approccio comune.

626
00:27:45,436 --> 00:27:50,180
Mentre puntatore non è uguale a
nullo, e questo è sintassi valida.

627
00:27:50,180 --> 00:27:54,550
E significa solo fare il seguente, così
Finché non sei che punta a nulla.

628
00:27:54,550 --> 00:27:55,800
Cosa voglio fare?

629
00:27:55,800 --> 00:28:01,939
>> Se il puntatore dot n, mi permetta di tornare
a che, equals-- uguale cosa?

630
00:28:01,939 --> 00:28:03,105
Che valore sto cercando?

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

632
00:28:04,920 --> 00:28:06,590
L'attuale n che è stato passato in.

633
00:28:06,590 --> 00:28:09,020
Quindi, ecco un'altra caratteristica
di C e di molte lingue.

634
00:28:09,020 --> 00:28:13,705
Anche se il nodo struttura chiamata
ha un valore n, totalmente legittimo

635
00:28:13,705 --> 00:28:17,530
di avere anche un argomento locale
o variabile chiamata n.

636
00:28:17,530 --> 00:28:20,085
Perché anche noi, con
occhi umani, riescono a distinguere

637
00:28:20,085 --> 00:28:22,087
che questo n è presumibilmente
diverso da questo n.

638
00:28:22,087 --> 00:28:23,420
Poiché la sintassi è diversa.

639
00:28:23,420 --> 00:28:26,211
Hai un punto e un puntatore,
che ciò si ha nulla di simile.

640
00:28:26,211 --> 00:28:27,290
Quindi questo è OK.

641
00:28:27,290 --> 00:28:29,120
Questo è OK per chiamare loro le stesse cose.

642
00:28:29,120 --> 00:28:32,380
>> Se io vi trovo, io sono
andando a voler fare qualcosa

643
00:28:32,380 --> 00:28:35,000
come annunciamo che abbiamo trovato n.

644
00:28:35,000 --> 00:28:37,930
E lasceremo che come
commento o codice pseudocodice.

645
00:28:37,930 --> 00:28:40,190
Else, ed ecco la
parte interessante, cosa

646
00:28:40,190 --> 00:28:47,320
voglio fare se il nodo corrente
non contenente n che mi interessa?

647
00:28:47,320 --> 00:28:50,700
Come faccio a raggiungere i seguenti?

648
00:28:50,700 --> 00:28:53,710
Se il mio dito contro il
momento è PTR, ed è

649
00:28:53,710 --> 00:28:55,920
che punta a qualsiasi
prima è puntato verso,

650
00:28:55,920 --> 00:28:59,290
come faccio a spostare il dito
al nodo successivo nel codice?

651
00:28:59,290 --> 00:29:01,915
Ebbene, qual è il breadcrumb siamo
andando a seguire in questo caso?

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

653
00:29:03,464 --> 00:29:04,380
PUBBLICO: [incomprensibile].

654
00:29:04,380 --> 00:29:05,630
DAVID J. MALAN: Sì, così la prossima.

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

656
00:29:06,640 --> 00:29:09,824
Quindi, se torno al mio
codice qui, anzi, io sono

657
00:29:09,824 --> 00:29:12,990
intenzione di andare avanti e dire pointer, che
è solo un variable-- temporanea è

658
00:29:12,990 --> 00:29:15,320
un nome strano, ptr, ma
è proprio come temp--

659
00:29:15,320 --> 00:29:19,234
Ho intenzione di impostare il puntatore
uguale a qualsiasi puntatore è--

660
00:29:19,234 --> 00:29:22,150
e di nuovo, questo sta andando essere un
poco buggy per un punto moment-- successivo.

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

662
00:29:23,551 --> 00:29:26,550
In altre parole, io vado a prendere la mia
dito che sta puntando a questo nodo

663
00:29:26,550 --> 00:29:31,247
qui e ho intenzione di dire, sai
cosa, dare un'occhiata al campo successivo

664
00:29:31,247 --> 00:29:33,330
e spostare il dito per
come diavolo si punta a.

665
00:29:33,330 --> 00:29:35,163
E questo sta per
ripetere, ripetere, ripetere.

666
00:29:35,163 --> 00:29:37,630
Ma quando lo fa il mio dito
smettere di fare qualcosa?

667
00:29:37,630 --> 00:29:40,095
Appena quale linea di calci di codice in?

668
00:29:40,095 --> 00:29:40,970
PUBBLICO: [incomprensibile]

669
00:29:40,970 --> 00:29:43,060
DAVID J. MALAN: Se il punto mentre
puntatore non è uguale a null.

670
00:29:43,060 --> 00:29:44,900
Ad un certo punto il mio dito del
sta per essere punta a nulla

671
00:29:44,900 --> 00:29:47,070
e ho intenzione di realizzare
che è la fine di questo elenco.

672
00:29:47,070 --> 00:29:48,910
Ora, questo è un po
bugia bianca per semplicità.

673
00:29:48,910 --> 00:29:51,580
Si scopre che anche se abbiamo
appena appreso questa notazione dot

674
00:29:51,580 --> 00:29:55,220
per le strutture, il puntatore non è una struct.

675
00:29:55,220 --> 00:29:56,580
ptr è ciò?

676
00:29:56,580 --> 00:29:58,350
Giusto per essere più pignoli.

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

678
00:29:59,720 --> 00:30:01,360
E 'un puntatore a un nodo.

679
00:30:01,360 --> 00:30:03,120
Non è un nodo stesso.

680
00:30:03,120 --> 00:30:06,650
Se non avevo stella qui, puntatore
absolutely-- si tratta di un nodo.

681
00:30:06,650 --> 00:30:08,650
Questo è come una settimana
la dichiarazione di una variabile,

682
00:30:08,650 --> 00:30:10,120
anche se la parola "nodo" è nuovo.

683
00:30:10,120 --> 00:30:13,860
>> Ma non appena si introduce un
stella, è ora un puntatore a un nodo.

684
00:30:13,860 --> 00:30:17,960
E purtroppo non è possibile utilizzare
la notazione dot per un puntatore.

685
00:30:17,960 --> 00:30:21,070
Devi usare la freccia
notazione, che, sorprendentemente,

686
00:30:21,070 --> 00:30:23,470
è la prima volta ogni pezzo
di sintassi sembra intuitivo.

687
00:30:23,470 --> 00:30:25,245
Questo appare letteralmente come una freccia.

688
00:30:25,245 --> 00:30:26,370
E così che è una buona cosa.

689
00:30:26,370 --> 00:30:28,995
E qui, letteralmente
si presenta come una freccia.

690
00:30:28,995 --> 00:30:31,870
Quindi penso che sia il la-- non lo faccio
penso che io sto troppo commettere qui-- I

691
00:30:31,870 --> 00:30:34,120
credo che sia l'ultimo nuovo pezzo
di sintassi che andremo a vedere.

692
00:30:34,120 --> 00:30:36,500
E per fortuna, è infatti
un po 'più intuitivo.

693
00:30:36,500 --> 00:30:40,090
>> Ora, per quelli di voi che
potrebbe preferire il vecchio modo,

694
00:30:40,090 --> 00:30:42,550
è comunque possibile utilizzare la notazione del punto.

695
00:30:42,550 --> 00:30:45,380
Ma, come per ogni lunedì di
conversazione, abbiamo prima

696
00:30:45,380 --> 00:30:50,530
bisogno di andare lì, andare a quella
affrontare, e quindi accedere al campo.

697
00:30:50,530 --> 00:30:51,897
Quindi questo è anche corretto.

698
00:30:51,897 --> 00:30:53,730
E, francamente, questo è un
poco più pedante.

699
00:30:53,730 --> 00:30:56,530
Stai dicendo letteralmente, dereferenziare
il puntatore e andare lì.

700
00:30:56,530 --> 00:30:59,320
Poi afferrare .n, il campo denominato n.

701
00:30:59,320 --> 00:31:01,370
Ma francamente, nessuno vuole
digitare o leggere questo.

702
00:31:01,370 --> 00:31:03,620
E così il mondo inventato
la notazione freccia, che

703
00:31:03,620 --> 00:31:06,980
è equivalente, identico,
è solo zucchero sintattico.

704
00:31:06,980 --> 00:31:10,570
Quindi un modo elegante per dire questo
guarda meglio, o sembra più semplice.

705
00:31:10,570 --> 00:31:12,296
>> Così ora ho intenzione di fare un'altra cosa.

706
00:31:12,296 --> 00:31:15,420
Io vado a dire "rompere" una volta ho
trovato così non tengo in cerca di esso.

707
00:31:15,420 --> 00:31:17,620
Ma questo è il succo
di una funzione di ricerca.

708
00:31:17,620 --> 00:31:21,710
Ma è molto più facile, in
fine, non a piedi attraverso il codice.

709
00:31:21,710 --> 00:31:25,570
Questo è infatti l'implementazione formale
di ricerca in codice della distribuzione di oggi.

710
00:31:25,570 --> 00:31:30,530
Oserei dire che inserto non è
particolarmente divertente camminare attraverso

711
00:31:30,530 --> 00:31:33,180
visivamente, né è eliminare, anche
se al termine della giornata

712
00:31:33,180 --> 00:31:35,460
si riducono a abbastanza
euristiche semplici.

713
00:31:35,460 --> 00:31:36,330
>> Quindi cerchiamo di fare questo.

714
00:31:36,330 --> 00:31:39,250
Se ti umorismo me qui, ho fatto
portare un mucchio di palle di stress.

715
00:31:39,250 --> 00:31:40,620
Ho portato un po 'di numeri.

716
00:31:40,620 --> 00:31:46,562
E abbiamo potuto ottenere solo pochi volontari
per rappresentare 9, 17, 20, 22, 29, e 34?

717
00:31:46,562 --> 00:31:48,270
Quindi in sostanza tutti
che è qui oggi.

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

719
00:31:50,170 --> 00:31:52,760
Quello era uno, due, tre,
quattro, cinque, sei persone.

720
00:31:52,760 --> 00:31:55,740
E mi è stato chiesto di go-- vedere, non
uno nella parte posteriore solleva le mani.

721
00:31:55,740 --> 00:32:01,910
OK, uno, due, tre, quattro,
five-- fammi caricare balance-- sei.

722
00:32:01,910 --> 00:32:03,051
OK, tu sei venuto in su.

723
00:32:03,051 --> 00:32:04,050
Avremo bisogno di altre persone.

724
00:32:04,050 --> 00:32:05,460
Abbiamo portato le palle stress supplementare.

725
00:32:05,460 --> 00:32:08,200
E se si potesse, per
solo un attimo, linea

726
00:32:08,200 --> 00:32:10,490
voi stessi su appena
come questa immagine qui.

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

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

729
00:32:15,959 --> 00:32:17,125
Vediamo, qual è il tuo nome?

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

731
00:32:17,550 --> 00:32:18,800
>> DAVID J. MALAN: Andrew,
sei il numero 9.

732
00:32:18,800 --> 00:32:19,540
Piacere di conoscerti.

733
00:32:19,540 --> 00:32:20,400
Ecco qui.

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

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

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

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

738
00:32:23,162 --> 00:32:23,765
Numero 17.

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

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

741
00:32:25,450 --> 00:32:26,400
>> PUBBLICO: Sono Julia.

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

743
00:32:26,980 --> 00:32:27,545
Numero 20.

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

745
00:32:28,507 --> 00:32:29,340
PUBBLICO: Christian.

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

747
00:32:30,715 --> 00:32:31,541
Numero 22.

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

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

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

751
00:32:33,440 --> 00:32:34,880
Numero 29.

752
00:32:34,880 --> 00:32:37,080
Quindi, andare avanti e ottenere dentro-- Uh oh.

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

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

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

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

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

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

759
00:32:42,390 --> 00:32:43,682
Qualcuno ha un pennarello?

760
00:32:43,682 --> 00:32:44,890
PUBBLICO: Ho un pennarello.

761
00:32:44,890 --> 00:32:45,660
DAVID J. MALAN: Hai un pennarello?

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

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

764
00:32:47,577 --> 00:32:49,160
E qualcuno ha un pezzo di carta?

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

766
00:32:51,562 --> 00:32:52,270
Salvare la lezione.

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

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

769
00:32:55,362 --> 00:32:56,320
PUBBLICO: l'abbiamo.

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

771
00:32:57,600 --> 00:32:58,577
Va bene, grazie.

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

773
00:33:01,380 --> 00:33:02,520
Eccoci qui.

774
00:33:02,520 --> 00:33:03,582
Era questo da voi?

775
00:33:03,582 --> 00:33:04,540
Hai appena salvato la giornata.

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

777
00:33:05,670 --> 00:33:07,220
Così 29.

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

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

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

781
00:33:13,360 --> 00:33:14,890
Ho scritto male 29, ma OK.

782
00:33:14,890 --> 00:33:15,720
Vai avanti.

783
00:33:15,720 --> 00:33:18,114
Va bene, ti darò
la penna torna momentaneamente.

784
00:33:18,114 --> 00:33:19,280
Così abbiamo queste persone qui.

785
00:33:19,280 --> 00:33:20,330
Facciamo un altro.

786
00:33:20,330 --> 00:33:23,750
Gabe, vuoi per giocare
il primo elemento qui?

787
00:33:23,750 --> 00:33:25,705
Avremo bisogno di puntare
a queste belle persone.

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

789
00:33:26,930 --> 00:33:31,030
Quindi 9, 17, 20, 22, specie
di 29, e poi 34.

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

791
00:33:32,160 --> 00:33:33,325
Abbiamo perso qualcuno?

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

793
00:33:33,950 --> 00:33:36,730
Dove did-- OK, chi vuole essere 34?

794
00:33:36,730 --> 00:33:37,605
OK, andiamo su, 34.

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

796
00:33:39,280 --> 00:33:41,220
Va bene, questo sarà
vale la pena il culmine.

797
00:33:41,220 --> 00:33:41,550
Come ti chiami?

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

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

800
00:33:43,456 --> 00:33:46,810
Va bene, quindi ecco una
tutta una serie di nodi.

801
00:33:46,810 --> 00:33:49,060
Ognuno di voi rappresenta
uno di questi rettangoli.

802
00:33:49,060 --> 00:33:51,930
E Gabe, il po 'strano
Man Out, rappresenta il primo.

803
00:33:51,930 --> 00:33:54,850
Così il suo puntatore è un po 'più piccola
sullo schermo di tutti gli altri.

804
00:33:54,850 --> 00:33:58,120
E in questo caso, ognuno di sinistra
mani sta per entrambi puntare verso il basso,

805
00:33:58,120 --> 00:34:01,085
rappresentando quindi nullo, così
solo l'assenza di un puntatore,

806
00:34:01,085 --> 00:34:03,210
o che sta per essere puntamento
ad un nodo accanto a voi.

807
00:34:03,210 --> 00:34:05,440
>> Così adesso, se si adornano
voi stessi come l'immagine

808
00:34:05,440 --> 00:34:07,585
qui, andare avanti e punto
a vicenda, con Gabe

809
00:34:07,585 --> 00:34:11,030
in particolare che punta a
numero 9 per rappresentare la lista.

810
00:34:11,030 --> 00:34:14,050
OK, e il numero 34, la mano sinistra
deve solo essere puntato verso il pavimento.

811
00:34:14,050 --> 00:34:15,750
>> OK, quindi questa è la lista collegata.

812
00:34:15,750 --> 00:34:17,580
Quindi questo è lo scenario in questione.

813
00:34:17,580 --> 00:34:20,210
E in effetti, questo è rappresentativo
di una classe di problemi

814
00:34:20,210 --> 00:34:21,929
che si potrebbe provare a risolvere con il codice.

815
00:34:21,929 --> 00:34:25,020
Si desidera inserire definitiva
un nuovo elemento nella lista.

816
00:34:25,020 --> 00:34:27,494
In questo caso, stiamo andando a
provare a inserire il numero 55.

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

818
00:34:28,500 --> 00:34:30,860
Ma ci sara '
diversi casi da considerare.

819
00:34:30,860 --> 00:34:34,409
E in effetti, questo sta per essere uno
del big-picture take away qui, è,

820
00:34:34,409 --> 00:34:35,659
quali sono i diversi casi.

821
00:34:35,659 --> 00:34:39,120
Quali sono i diversi se le condizioni o
rami che il programma potrebbe avere?

822
00:34:39,120 --> 00:34:42,024
>> Ebbene, il numero che si sta cercando di
inserto, che ora sappiamo essere 55,

823
00:34:42,024 --> 00:34:44,650
ma se non lo sapevate
in anticipo, oserei dire

824
00:34:44,650 --> 00:34:47,840
cade in almeno tre
possibili situazioni.

825
00:34:47,840 --> 00:34:49,717
Quando un nuovo elemento potrebbe essere?

826
00:34:49,717 --> 00:34:51,050
PUBBLICO: E la fine o medio.

827
00:34:51,050 --> 00:34:54,150
DAVID J. MALAN: Alla fine, in
mezzo, o all'inizio.

828
00:34:54,150 --> 00:34:56,650
Quindi io sostengo che ci sia almeno
tre problemi che devono risolvere.

829
00:34:56,650 --> 00:34:58,691
Scegliamo ciò che è forse
probabilmente il più semplice

830
00:34:58,691 --> 00:35:01,090
uno, dove il nuovo elemento
appartiene all'inizio.

831
00:35:01,090 --> 00:35:04,040
Quindi ho intenzione di avere il codice abbastanza
come la ricerca, che ho appena scritto.

832
00:35:04,040 --> 00:35:07,670
E ho intenzione di avere ptr, che
Io rappresento qui con il mio dito,

833
00:35:07,670 --> 00:35:08,370
come di solito.

834
00:35:08,370 --> 00:35:12,430
>> E ricordate, che valore
abbiamo inizializziamo ptr a?

835
00:35:12,430 --> 00:35:15,300
Così abbiamo inizializzato a NULL inizialmente.

836
00:35:15,300 --> 00:35:16,410

837
00:35:16,410 --> 00:35:19,770
Ma allora cosa abbiamo fatto una volta
erano all'interno della nostra funzione di ricerca?

838
00:35:19,770 --> 00:35:20,940

839
00:35:20,940 --> 00:35:24,870
Abbiamo impostato uguale a prima,
che non significa fare questo.

840
00:35:24,870 --> 00:35:25,890

841
00:35:25,890 --> 00:35:30,570
Se ho impostato ptr uguale alla prima, che cosa
dovrebbe davvero essere la mia mano che punta a?

842
00:35:30,570 --> 00:35:31,070
Destra.

843
00:35:31,070 --> 00:35:33,290
Quindi, se Gabe e io stiamo andando
essere valori uguali qui,

844
00:35:33,290 --> 00:35:34,760
abbiamo bisogno di entrambi punto al numero 9.

845
00:35:34,760 --> 00:35:36,420
>> Quindi questo è stato l'inizio della nostra storia.

846
00:35:36,420 --> 00:35:38,700
E ora questo è solo semplice,
anche se la sintassi è nuovo.

847
00:35:38,700 --> 00:35:40,580
Concettualmente questo è solo ricerca lineare.

848
00:35:40,580 --> 00:35:42,750
Is 55, pari al 9?

849
00:35:42,750 --> 00:35:45,559
O meglio, diciamo meno di 9.

850
00:35:45,559 --> 00:35:47,600
Perché io sto cercando di
capire dove mettere 55.

851
00:35:47,600 --> 00:35:51,270
Meno 9, meno di 17, meno
di 20, meno di 22, meno di 29,

852
00:35:51,270 --> 00:35:52,510
meno di 34, no.

853
00:35:52,510 --> 00:35:55,080
Così ora siamo nel caso
uno degli almeno tre.

854
00:35:55,080 --> 00:35:59,910
>> Se voglio inserire 55 qui, cosa
righe di codice per necessità vengono eseguiti?

855
00:35:59,910 --> 00:36:01,890
Come funziona questo quadro di
gli esseri umani hanno bisogno di cambiare?

856
00:36:01,890 --> 00:36:03,181
Cosa devo fare con la mia mano sinistra?

857
00:36:03,181 --> 00:36:04,530

858
00:36:04,530 --> 00:36:07,360
Questo dovrebbe essere nullo inizialmente,
perché io sono alla fine della lista.

859
00:36:07,360 --> 00:36:09,318
E che cosa dovrebbe accadere
qui con Peter, vero?

860
00:36:09,318 --> 00:36:10,520

861
00:36:10,520 --> 00:36:12,430
Lui, ovviamente, andando a puntare a me.

862
00:36:12,430 --> 00:36:15,580
Quindi io rivendico ci sono almeno due linee
di codice nel codice di esempio da oggi

863
00:36:15,580 --> 00:36:18,570
che sta per implementare questa
scenario di aggiungere 55 alla coda.

864
00:36:18,570 --> 00:36:20,950
E potrei avere qualcuno hop
e solo rappresentano il 55?

865
00:36:20,950 --> 00:36:22,200
Va bene, tu sei il nuovo 55.

866
00:36:22,200 --> 00:36:23,580

867
00:36:23,580 --> 00:36:27,054
>> Così ora che cosa se il prossimo
scenario arriva,

868
00:36:27,054 --> 00:36:29,720
e vogliamo inserire al
inizio o il capo di questa lista?

869
00:36:29,720 --> 00:36:31,100
E qual è il tuo nome, il numero 55?

870
00:36:31,100 --> 00:36:31,420
>> PUBBLICO: Jack.

871
00:36:31,420 --> 00:36:32,295
>> DAVID J. MALAN: Jack?

872
00:36:32,295 --> 00:36:33,585
OK, piacere di conoscerti.

873
00:36:33,585 --> 00:36:34,210
Benvenuto a bordo.

874
00:36:34,210 --> 00:36:36,640
Così ora stiamo andando a
inserire, per esempio, il numero 5.

875
00:36:36,640 --> 00:36:39,840
Ecco il secondo caso del
tre siamo arrivati ​​a prima.

876
00:36:39,840 --> 00:36:43,050
Quindi, se 5 appartiene all'inizio,
vediamo come troviamo che fuori.

877
00:36:43,050 --> 00:36:46,310
Io inizializzo il mio ptr
puntatore al numero 9 di nuovo.

878
00:36:46,310 --> 00:36:49,140
E mi sono reso conto, oh, 5 è inferiore a 9.

879
00:36:49,140 --> 00:36:50,880
Quindi fissare questa immagine per noi.

880
00:36:50,880 --> 00:36:54,820
Le cui mani, Gabe di David o di
o- qual è il nome del numero 9?

881
00:36:54,820 --> 00:36:55,740
>> PUBBLICO: Jen.

882
00:36:55,740 --> 00:36:58,406
>> DAVID J. MALAN: hands-- di Jen
che delle nostre mani hanno bisogno di cambiare?

883
00:36:58,406 --> 00:36:58,905

884
00:36:58,905 --> 00:37:00,970
OK, così Gabe indica a che ora?

885
00:37:00,970 --> 00:37:01,640
A me.

886
00:37:01,640 --> 00:37:02,750
Sono il nuovo nodo.

887
00:37:02,750 --> 00:37:04,870
Quindi mi limiterò solo tipo di movimento
qui per vedere visivamente.

888
00:37:04,870 --> 00:37:06,435
E intanto quello che faccio che punto?

889
00:37:06,435 --> 00:37:07,910

890
00:37:07,910 --> 00:37:09,020
Ancora dove sto indicando.

891
00:37:09,020 --> 00:37:10,000
Quindi questo è tutto.

892
00:37:10,000 --> 00:37:13,717
Quindi basta davvero una linea di correzioni di codice
questo particolare problema, sembrerebbe.

893
00:37:13,717 --> 00:37:14,800
Va bene, quindi questo è un bene.

894
00:37:14,800 --> 00:37:17,580
E qualcuno può essere un segnaposto per 5?

895
00:37:17,580 --> 00:37:18,080
Andiamo su.

896
00:37:18,080 --> 00:37:20,270

897
00:37:20,270 --> 00:37:21,320
Ti porteremo la prossima volta.

898
00:37:21,320 --> 00:37:24,280
>> Va bene, così now-- e
Per inciso, i nomi

899
00:37:24,280 --> 00:37:28,510
Non sto facendo esplicita menzione del diritto
ora, pred puntatore, puntatore predecessore

900
00:37:28,510 --> 00:37:31,260
e nuovo puntatore, che è
solo i nomi dato

901
00:37:31,260 --> 00:37:35,280
nel codice di esempio per i puntatori o
le mie mani che è tipo di punta intorno.

902
00:37:35,280 --> 00:37:36,060
Come ti chiami?

903
00:37:36,060 --> 00:37:36,700
>> PUBBLICO: Christine.

904
00:37:36,700 --> 00:37:37,100
>> DAVID J. MALAN: Christine.

905
00:37:37,100 --> 00:37:38,090
Benvenuto a bordo.

906
00:37:38,090 --> 00:37:42,180
Va bene, quindi consideriamo ora
uno scenario leggermente più fastidioso,

907
00:37:42,180 --> 00:37:46,350
in base al quale voglio inserire
qualcosa come 26 in questo.

908
00:37:46,350 --> 00:37:47,090
20?

909
00:37:47,090 --> 00:37:47,590
Che cosa?

910
00:37:47,590 --> 00:37:50,510
Questi are-- buona cosa che abbiamo questa penna.

911
00:37:50,510 --> 00:37:51,955
Va bene, 20.

912
00:37:51,955 --> 00:37:53,640

913
00:37:53,640 --> 00:37:57,570
Se qualcuno potrebbe ottenere un altro pezzo di
carta pronto, giusto in case-- tutto bene.

914
00:37:57,570 --> 00:37:58,370
Oh, interessante.

915
00:37:58,370 --> 00:37:59,760

916
00:37:59,760 --> 00:38:02,390
Beh, questo è un esempio
di un bug lezione.

917
00:38:02,390 --> 00:38:03,894
OK così che cosa è nuovo il tuo nome?

918
00:38:03,894 --> 00:38:04,560
PUBBLICO: Julia.

919
00:38:04,560 --> 00:38:07,559
DAVID J. MALAN: Julia, si può pop
fuori e far finta che eri mai lì?

920
00:38:07,559 --> 00:38:09,040
OK, questo non è mai accaduto.

921
00:38:09,040 --> 00:38:09,680
Grazie.

922
00:38:09,680 --> 00:38:12,180
Quindi supponiamo di voler inserire
Julia in questa lista collegata.

923
00:38:12,180 --> 00:38:13,780
Lei è la numero 20.

924
00:38:13,780 --> 00:38:15,530
E naturalmente lei è
intenzione di appartenere alla

925
00:38:15,530 --> 00:38:17,521
begin-- ancora non puntare a qualche cosa.

926
00:38:17,521 --> 00:38:20,020
Così la vostra mano può essere di tipo
giù nullo o un valore spazzatura.

927
00:38:20,020 --> 00:38:21,210
Diciamo la storia veloce.

928
00:38:21,210 --> 00:38:22,980
Sto puntando al numero 5 questa volta.

929
00:38:22,980 --> 00:38:23,880
Poi verifico 9.

930
00:38:23,880 --> 00:38:25,130
Poi posso controllare 17.

931
00:38:25,130 --> 00:38:26,247
Poi posso controllare 22.

932
00:38:26,247 --> 00:38:27,650

933
00:38:27,650 --> 00:38:32,485
E mi rendo conto, ooh, Julia
deve andare prima del 22.

934
00:38:32,485 --> 00:38:33,580

935
00:38:33,580 --> 00:38:34,660
Così che cosa deve accadere?

936
00:38:34,660 --> 00:38:35,786

937
00:38:35,786 --> 00:38:36,910
Le cui mani hanno bisogno di cambiare?

938
00:38:36,910 --> 00:38:38,360
Julia, la mia, o-
cosa c'è di nuovo il tuo nome?

939
00:38:38,360 --> 00:38:39,230
>> PUBBLICO: Christian.

940
00:38:39,230 --> 00:38:40,060
>> DAVID J. MALAN: cristiano o?

941
00:38:40,060 --> 00:38:40,560
>> PUBBLICO: Andy.

942
00:38:40,560 --> 00:38:40,905
>> DAVID J. MALAN: Andy.

943
00:38:40,905 --> 00:38:41,654
Cristiano o Andy?

944
00:38:41,654 --> 00:38:44,280

945
00:38:44,280 --> 00:38:45,690
Andy deve puntare a?

946
00:38:45,690 --> 00:38:46,780

947
00:38:46,780 --> 00:38:47,341
Julia.

948
00:38:47,341 --> 00:38:47,840
Bene.

949
00:38:47,840 --> 00:38:48,960
Così Andy, vuoi puntare a Julia?

950
00:38:48,960 --> 00:38:50,120
Ma aspettate un minuto.

951
00:38:50,120 --> 00:38:53,260
Nella storia finora,
Io sono il tipo di una

952
00:38:53,260 --> 00:38:56,800
responsabile, nel senso che
puntatore è la cosa che è

953
00:38:56,800 --> 00:38:57,850
si muove attraverso la lista.

954
00:38:57,850 --> 00:39:00,800
Potremmo avere un nome per Andy, ma
non c'è variabile chiamata Andy.

955
00:39:00,800 --> 00:39:04,320
L'unica altra variabile che abbiamo è
prima, che è rappresentato da Gabe.

956
00:39:04,320 --> 00:39:07,690
>> Quindi questo è in realtà il motivo per cui così
Fino ad ora non abbiamo bisogno di questo.

957
00:39:07,690 --> 00:39:10,846
Ma ora sullo schermo c'è
parlare di nuovo di puntatore pred.

958
00:39:10,846 --> 00:39:11,970
Permettetemi di essere più esplicito.

959
00:39:11,970 --> 00:39:14,820
Se questo è il puntatore, ho avuto meglio
ottenere un po 'più intelligente

960
00:39:14,820 --> 00:39:15,950
sul mio iterazione.

961
00:39:15,950 --> 00:39:19,580
Se non ti dispiace il mio andare di qui
di nuovo, indicando qui, indicando qui.

962
00:39:19,580 --> 00:39:22,500
Ma mi permetta di avere un puntatore pred,
puntatore predecessore, che è

963
00:39:22,500 --> 00:39:24,740
tipo di punta verso la
elemento Ero solo a.

964
00:39:24,740 --> 00:39:27,330
Così quando vado qui, ora
i miei aggiornamenti mano sinistra.

965
00:39:27,330 --> 00:39:29,370
Quando vado qui i miei aggiornamenti della mano sinistra.

966
00:39:29,370 --> 00:39:33,090
E ora non ho solo un puntatore a
l'elemento che va dopo Julia,

967
00:39:33,090 --> 00:39:36,300
Ho ancora un puntatore a
Andy, l'elemento prima.

968
00:39:36,300 --> 00:39:39,430
Così si ha accesso, in sostanza,
pangrattato, se si vuole,

969
00:39:39,430 --> 00:39:41,500
a tutti i puntatori necessari.

970
00:39:41,500 --> 00:39:43,710
>> Quindi se sto puntando a
Andy ed io sto puntando anche

971
00:39:43,710 --> 00:39:47,105
a Christian, le cui mani
dovrebbe ora essere osservato altrove?

972
00:39:47,105 --> 00:39:48,770

973
00:39:48,770 --> 00:39:51,960
Così Andy ora può puntare a Julia.

974
00:39:51,960 --> 00:39:54,460
Julia ora può puntare a Christian.

975
00:39:54,460 --> 00:39:56,950
Perché lei può copiare il mio
puntatore di destra.

976
00:39:56,950 --> 00:40:00,044
E che ti mette in modo efficace
di nuovo in questo posto qui.

977
00:40:00,044 --> 00:40:02,460
Così, in breve, anche se questo
ci sta prendendo tipo di sempre

978
00:40:02,460 --> 00:40:04,510
aggiornare realtà un
lista collegata, realizzare

979
00:40:04,510 --> 00:40:06,580
che le operazioni
sono relativamente semplici.

980
00:40:06,580 --> 00:40:10,030
E 'di uno, due, tre
righe di codice in ultima analisi.

981
00:40:10,030 --> 00:40:12,780
Ma avvolto attorno a quelli
righe di codice presumibilmente

982
00:40:12,780 --> 00:40:16,350
che è effettivamente un po 'di logica
pone la domanda, a che punto siamo?

983
00:40:16,350 --> 00:40:18,970
Siamo all'inizio,
la metà o la fine?

984
00:40:18,970 --> 00:40:21,890
>> Ora, ci sono sicuramente alcuni altri
operazioni potremmo implementare.

985
00:40:21,890 --> 00:40:24,880
E queste immagini qui solo raffigurano
quello che abbiamo appena fatto con gli esseri umani.

986
00:40:24,880 --> 00:40:26,080
Che dire di rimozione?

987
00:40:26,080 --> 00:40:30,650
Se voglio, per esempio,
rimuovere il numero 34 o 55,

988
00:40:30,650 --> 00:40:34,680
Potrei avere lo stesso tipo di codice,
ma ho intenzione di bisogno di uno o due passi.

989
00:40:34,680 --> 00:40:36,110
Perché quello che c'è di nuovo?

990
00:40:36,110 --> 00:40:40,460
Se rimuovo qualcuno, alla fine,
come il numero 55 e poi 34,

991
00:40:40,460 --> 00:40:42,995
ciò che deve anche cambiare come faccio?

992
00:40:42,995 --> 00:40:44,870
Devo non evict--
cosa c'è di nuovo il tuo nome?

993
00:40:44,870 --> 00:40:45,380
>> PUBBLICO: Jack.

994
00:40:45,380 --> 00:40:46,255
>> DAVID J. MALAN: Jack.

995
00:40:46,255 --> 00:40:49,770
Devo non solo evict-- libero Jack,
così letteralmente chiamare il Jack, o almeno

996
00:40:49,770 --> 00:40:53,530
il puntatore anche lì, ma ora
ciò che deve cambiare con Peter?

997
00:40:53,530 --> 00:40:55,510
La sua mano meglio iniziare punta verso il basso.

998
00:40:55,510 --> 00:40:59,300
Perché non appena chiamo gratuito
Jack, se di Peter ancora punta a Jack

999
00:40:59,300 --> 00:41:02,530
e pertanto continuo attraversamento
l'elenco e l'accesso questo puntatore,

1000
00:41:02,530 --> 00:41:05,650
che quando il nostro amico segmentazione vecchio
guasto potrebbe effettivamente calci in.

1001
00:41:05,650 --> 00:41:07,860
Perché abbiamo dato il
memoria torna a Jack.

1002
00:41:07,860 --> 00:41:10,760
>> Si può stare lì
goffamente solo per un attimo.

1003
00:41:10,760 --> 00:41:13,410
Perché abbiamo solo un paio
operazioni finali da considerare.

1004
00:41:13,410 --> 00:41:15,600
Rimuovere la testa della lista,
o la beginning-- e questo proprio

1005
00:41:15,600 --> 00:41:16,349
un po 'fastidioso.

1006
00:41:16,349 --> 00:41:19,640
Perché dobbiamo sapere che Gabe
è una specie di speciale in questo programma.

1007
00:41:19,640 --> 00:41:21,440
Perché in effetti, egli ha il suo puntatore.

1008
00:41:21,440 --> 00:41:24,860
Egli non è solo di essere puntato,
come quasi tutti gli altri qui.

1009
00:41:24,860 --> 00:41:28,112
>> Così, quando la testa della lista è
rimosso, le cui mani hanno bisogno di cambiare ora?

1010
00:41:28,112 --> 00:41:29,070
Qual è il tuo nuovo nome?

1011
00:41:29,070 --> 00:41:29,450
>> PUBBLICO: Christine.

1012
00:41:29,450 --> 00:41:31,408
>> DAVID J. MALAN: io sono terribile
a nomi, a quanto pare.

1013
00:41:31,408 --> 00:41:34,011
Così Christine e Gabe,
le cui mani hanno bisogno di cambiare

1014
00:41:34,011 --> 00:41:36,510
quando cerchiamo di rimuovere Christine,
numero 5, dalla foto?

1015
00:41:36,510 --> 00:41:37,550

1016
00:41:37,550 --> 00:41:38,820
OK, quindi cerchiamo di fare Gabe.

1017
00:41:38,820 --> 00:41:40,950
Gabe sta andando al punto,
presumibilmente, al numero 9.

1018
00:41:40,950 --> 00:41:42,230

1019
00:41:42,230 --> 00:41:44,642
Ma cosa dovrebbe accadere il prossimo?

1020
00:41:44,642 --> 00:41:46,600
PUBBLICO: Christine dovrebbe
essere nullo [incomprensibile].

1021
00:41:46,600 --> 00:41:50,244
DAVID J. MALAN: OK, dovremmo probabilmente
make-- ho sentito "nulla" da qualche parte.

1022
00:41:50,244 --> 00:41:51,410
PUBBLICO: Null e libera la sua.

1023
00:41:51,410 --> 00:41:51,855
DAVID J. MALAN: null cosa?

1024
00:41:51,855 --> 00:41:53,074
PUBBLICO: Null e libera la sua.

1025
00:41:53,074 --> 00:41:54,490
DAVID J. MALAN: Null e libera la sua.

1026
00:41:54,490 --> 00:41:55,422
Quindi questo è molto facile.

1027
00:41:55,422 --> 00:41:58,380
Ed è perfetto che ora sei specie
di lì, non appartenenza.

1028
00:41:58,380 --> 00:42:00,430
Perché sei stato
disaccoppiato dalla lista.

1029
00:42:00,430 --> 00:42:02,820
Sei stato efficacemente
orfano dalla lista.

1030
00:42:02,820 --> 00:42:07,770
E così faremmo meglio a chiamare gratis su
Christine dare che la memoria indietro.

1031
00:42:07,770 --> 00:42:10,240
In caso contrario, ogni volta che
eliminare un nodo dall'elenco

1032
00:42:10,240 --> 00:42:14,230
potremmo essere facendo la lista
più breve, ma non effettivamente decrescente

1033
00:42:14,230 --> 00:42:15,096
la dimensione in memoria.

1034
00:42:15,096 --> 00:42:17,720
E così se continuiamo aggiungendo e
aggiungendo, aggiungendo cose alla lista,

1035
00:42:17,720 --> 00:42:19,280
il mio computer potrebbe ottenere più lento
e più lento e più lento,

1036
00:42:19,280 --> 00:42:21,740
perché sono a corto di
memoria, anche se io non sono in realtà

1037
00:42:21,740 --> 00:42:25,580
utilizzando i byte di Christine
di memoria più.

1038
00:42:25,580 --> 00:42:28,500
>> Così alla fine ci sono altri
scenari, di rimozione naturalmente--

1039
00:42:28,500 --> 00:42:30,640
nel mezzo, la rimozione
alla fine, come abbiamo visto.

1040
00:42:30,640 --> 00:42:32,348
Ma il più interessante
sfida ora è

1041
00:42:32,348 --> 00:42:34,770
andando a essere quello di considerare esattamente
ciò che il tempo di esecuzione è.

1042
00:42:34,770 --> 00:42:36,640
Quindi non solo è possibile mantenere il vostro
pezzi di carta, se, Gabe,

1043
00:42:36,640 --> 00:42:38,640
che non mi dispiacerebbe dare
tutti una palla antistress.

1044
00:42:38,640 --> 00:42:42,100
Grazie mille alla nostra lista concatenata
di volontari qui, se potessi.

1045
00:42:42,100 --> 00:42:45,320
>> [Applausi]

1046
00:42:45,320 --> 00:42:46,700
>> DAVID J. MALAN: Va bene.

1047
00:42:46,700 --> 00:42:51,110
Così un paio di analitica
domande poi, se potessi.

1048
00:42:51,110 --> 00:42:59,670
Abbiamo visto questa notazione prima,
O grande e omega, limiti superiori

1049
00:42:59,670 --> 00:43:02,520
e limiti inferiori sul
tempo di qualche algoritmo esecuzione.

1050
00:43:02,520 --> 00:43:04,950
Quindi prendiamo in considerazione solo
un paio di domande.

1051
00:43:04,950 --> 00:43:07,090
>> Uno, e abbiamo detto
prima, che cosa è il funzionamento

1052
00:43:07,090 --> 00:43:10,647
tempo di ricerca di un
lista in termini di grande O?

1053
00:43:10,647 --> 00:43:13,480
Che cosa è un limite superiore per il funzionamento
tempo di cercare una lista concatenata

1054
00:43:13,480 --> 00:43:16,340
come attuato dai nostri volontari qui?

1055
00:43:16,340 --> 00:43:17,820
E 'grande O di n, lineare.

1056
00:43:17,820 --> 00:43:20,630
Perché nel caso peggiore,
l'elemento, come 55,

1057
00:43:20,630 --> 00:43:23,830
potremmo essere alla ricerca di potrebbe essere dove
Jack era, fino alla fine.

1058
00:43:23,830 --> 00:43:28,250
E purtroppo, a differenza di un array
non possiamo ottenere di fantasia questa volta.

1059
00:43:28,250 --> 00:43:31,820
Anche se tutti i nostri uomini erano
ordinati da piccoli elementi, 5,

1060
00:43:31,820 --> 00:43:35,900
tutto il percorso fino all'elemento più grande,
55, che di solito è una buona cosa.

1061
00:43:35,900 --> 00:43:38,815
Ma cosa significa questo presupposto
non ci permettono di fare?

1062
00:43:38,815 --> 00:43:39,775

1063
00:43:39,775 --> 00:43:40,650
PUBBLICO: [incomprensibile]

1064
00:43:40,650 --> 00:43:40,920
DAVID J. MALAN: dire ancora?

1065
00:43:40,920 --> 00:43:41,800
PUBBLICO: accesso casuale.

1066
00:43:41,800 --> 00:43:43,049
DAVID J. MALAN: accesso casuale.

1067
00:43:43,049 --> 00:43:46,330
E a sua volta questo significa che non possiamo
utilizzare più zeri deboli, l'intuizione,

1068
00:43:46,330 --> 00:43:49,365
e ovvietà di usare binario
cercare e dividere e conquistare.

1069
00:43:49,365 --> 00:43:51,240
Perché anche se abbiamo
gli esseri umani potrebbero ovviamente

1070
00:43:51,240 --> 00:43:54,610
vedere che Andy o cristiana erano
all'incirca a metà della lista,

1071
00:43:54,610 --> 00:43:57,670
sappiamo solo che come
computer scrematura della lista

1072
00:43:57,670 --> 00:43:59,029
fin dall'inizio.

1073
00:43:59,029 --> 00:44:00,570
Così abbiamo dato a tale accesso casuale.

1074
00:44:00,570 --> 00:44:04,380
>> Così grande O di n ora è il superiore
bound sul nostro tempo di ricerca.

1075
00:44:04,380 --> 00:44:07,920
Che dire omega della nostra ricerca?

1076
00:44:07,920 --> 00:44:11,535
Qual è il limite inferiore per la ricerca
per un certo numero in questo elenco?

1077
00:44:11,535 --> 00:44:12,410
PUBBLICO: [incomprensibile]

1078
00:44:12,410 --> 00:44:13,040
DAVID J. MALAN: dire ancora?

1079
00:44:13,040 --> 00:44:13,420
PUBBLICO: One.

1080
00:44:13,420 --> 00:44:13,800
DAVID J. MALAN: One.

1081
00:44:13,800 --> 00:44:14,760
Tempo così costante.

1082
00:44:14,760 --> 00:44:17,020
Nel migliore dei casi, Christine è
infatti, all'inizio della lista.

1083
00:44:17,020 --> 00:44:19,020
E stiamo cercando
numero 5, così l'abbiamo trovato.

1084
00:44:19,020 --> 00:44:19,787
Quindi un grosso problema.

1085
00:44:19,787 --> 00:44:22,370
Ma lei ha di essere al
inizio della lista in questo caso.

1086
00:44:22,370 --> 00:44:23,745
Che dire qualcosa come Cancellare?

1087
00:44:23,745 --> 00:44:24,717

1088
00:44:24,717 --> 00:44:26,300
Che cosa succede se si desidera eliminare un elemento?

1089
00:44:26,300 --> 00:44:29,200
Qual è il limite superiore e il limite inferiore
sull'eliminazione di qualcosa da un collegato

1090
00:44:29,200 --> 00:44:29,699
elencare?

1091
00:44:29,699 --> 00:44:35,195

1092
00:44:35,195 --> 00:44:36,070
PUBBLICO: [incomprensibile]

1093
00:44:36,070 --> 00:44:36,420
DAVID J. MALAN: dire ancora?

1094
00:44:36,420 --> 00:44:37,067
PUBBLICO: n.

1095
00:44:37,067 --> 00:44:38,900
DAVID J. MALAN: n è
infatti il ​​limite superiore.

1096
00:44:38,900 --> 00:44:41,700
Perché nel caso peggiore proviamo
per cancellare Jack, come abbiamo appena fatto.

1097
00:44:41,700 --> 00:44:43,050
E 'tutto il senso alla fine.

1098
00:44:43,050 --> 00:44:45,419
Ci prende per sempre, o
n passi per trovare lui.

1099
00:44:45,419 --> 00:44:46,460
Quindi questo è un limite superiore.

1100
00:44:46,460 --> 00:44:47,430
Questo è lineare, certo.

1101
00:44:47,430 --> 00:44:50,970
E il caso migliore tempo di esecuzione, o
i limiti inferiori nel migliore dei casi

1102
00:44:50,970 --> 00:44:51,975
sarebbe tempo costante.

1103
00:44:51,975 --> 00:44:54,600
Perché forse cerchiamo di eliminare
Christine, e abbiamo appena fortunati

1104
00:44:54,600 --> 00:44:55,558
lei è all'inizio.

1105
00:44:55,558 --> 00:44:56,350
Ora aspetta un minuto.

1106
00:44:56,350 --> 00:44:59,370
Gabe era anche all'inizio,
e abbiamo anche avuto per aggiornare Gabe.

1107
00:44:59,370 --> 00:45:01,150
Quindi non era solo un passo.

1108
00:45:01,150 --> 00:45:04,210
Quindi è davvero costante
tempo, nel migliore dei casi,

1109
00:45:04,210 --> 00:45:06,345
per rimuovere l'elemento più piccolo?

1110
00:45:06,345 --> 00:45:07,360

1111
00:45:07,360 --> 00:45:10,960
È, anche se potrebbe essere due,
tre, o anche 100 righe di codice,

1112
00:45:10,960 --> 00:45:14,000
se è lo stesso numero di
linee, non in alcuni loop,

1113
00:45:14,000 --> 00:45:16,577
e indipendente dalla dimensione
della lista, assolutamente.

1114
00:45:16,577 --> 00:45:18,660
Eliminare l'elemento in
all'inizio della lista,

1115
00:45:18,660 --> 00:45:21,940
anche se abbiamo a che fare con
Gabe, è ancora tempo costante.

1116
00:45:21,940 --> 00:45:24,220
>> Quindi questo sembra un
enorme passo indietro.

1117
00:45:24,220 --> 00:45:27,000
E che una perdita di tempo
se, in una settimana e settimana

1118
00:45:27,000 --> 00:45:30,250
pari a zero abbiamo avuto non solo
Codice pseudocodice ma il codice effettivo

1119
00:45:30,250 --> 00:45:35,780
di implementare qualcosa che è log
di base n, o log, piuttosto, di n, base 2,

1120
00:45:35,780 --> 00:45:37,150
in termini di tempo di esecuzione.

1121
00:45:37,150 --> 00:45:40,710
Allora perché diavolo dovrebbe vogliamo iniziare
usando qualcosa come una lista concatenata?

1122
00:45:40,710 --> 00:45:41,517
Già.

1123
00:45:41,517 --> 00:45:44,022
>> Pubblico: Così si può aggiungere
elementi all'array.

1124
00:45:44,022 --> 00:45:46,230
DAVID J. MALAN: Così si può
aggiungere elementi all'array.

1125
00:45:46,230 --> 00:45:47,550
E anche questo è tematica.

1126
00:45:47,550 --> 00:45:49,740
E continueremo a vedere
questo, questo trade-off, molto

1127
00:45:49,740 --> 00:45:51,573
come abbiamo visto un
trade-off con merge sort.

1128
00:45:51,573 --> 00:45:54,606
Potremmo davvero accelerare
la ricerca o l'ordinamento, piuttosto,

1129
00:45:54,606 --> 00:45:57,480
se passiamo un po 'più di spazio e
avere un pezzo aggiuntivo di una memoria

1130
00:45:57,480 --> 00:45:58,760
o un array di merge sort.

1131
00:45:58,760 --> 00:46:01,270
Ma passiamo più
spazio, ma risparmiamo tempo.

1132
00:46:01,270 --> 00:46:04,820
In questo caso, siamo
dando il tempo ma siamo

1133
00:46:04,820 --> 00:46:08,170
guadagnando flessibilità,
dinamismo se si vuole,

1134
00:46:08,170 --> 00:46:10,280
che è probabilmente una caratteristica positiva.

1135
00:46:10,280 --> 00:46:11,520
>> Stiamo anche spendendo spazio.

1136
00:46:11,520 --> 00:46:13,710
In che senso è un collegato
elencare più costoso

1137
00:46:13,710 --> 00:46:15,700
in termini di spazio di un array?

1138
00:46:15,700 --> 00:46:18,379

1139
00:46:18,379 --> 00:46:19,920
Dove si trova lo spazio in più proviene?

1140
00:46:19,920 --> 00:46:20,460
Sì?

1141
00:46:20,460 --> 00:46:21,800
>> PUBBLICO: [incomprensibile] puntatore.

1142
00:46:21,800 --> 00:46:23,310
>> DAVID J. MALAN: Sì, abbiamo
hanno anche il puntatore.

1143
00:46:23,310 --> 00:46:25,560
Quindi questo è minorly fastidioso
in quanto non sono più

1144
00:46:25,560 --> 00:46:27,780
Ho memorizzare solo un int
per rappresentare un int.

1145
00:46:27,780 --> 00:46:30,990
Sto memorizzazione di un int e un
puntatore, che è anche 32 bit.

1146
00:46:30,990 --> 00:46:33,470
Così sto letteralmente il raddoppio
la quantità di spazio coinvolto.

1147
00:46:33,470 --> 00:46:36,040
Quindi questo è un trade-off, ma
che è nel caso di int.

1148
00:46:36,040 --> 00:46:39,580
Supponiamo che non sei memorizzazione int,
ma supponiamo che ciascuno di questi rettangoli

1149
00:46:39,580 --> 00:46:43,290
o ciascuno di questi esseri umani rappresentava
una parola, una parola inglese che

1150
00:46:43,290 --> 00:46:46,430
potrebbe essere cinque caratteri, 10
personaggi, forse anche di più.

1151
00:46:46,430 --> 00:46:49,940
Poi l'aggiunta di soli 32 più bit
potrebbe essere meno di un grosso problema.

1152
00:46:49,940 --> 00:46:52,160
>> E se ognuno degli studenti
nella dimostrazione

1153
00:46:52,160 --> 00:46:55,107
erano letteralmente le strutture studentesche che
hanno nomi e case e forse

1154
00:46:55,107 --> 00:46:57,065
numeri di telefono e Twitter
maniglie e simili.

1155
00:46:57,065 --> 00:46:59,564
Così tutti i campi abbiamo iniziato
parlando l'altro giorno,

1156
00:46:59,564 --> 00:47:02,410
molto meno di un grande affare come
i nostri nodi si fanno più interessanti

1157
00:47:02,410 --> 00:47:05,972
e grande per spendere, eh, un ulteriore
puntatore solo per collegarli tra loro.

1158
00:47:05,972 --> 00:47:07,180
Ma in effetti, si tratta di un trade-off.

1159
00:47:07,180 --> 00:47:09,560
E infatti, il codice è
più complesso, come avrete

1160
00:47:09,560 --> 00:47:11,770
vedere da sfogliando
quel particolare esempio.

1161
00:47:11,770 --> 00:47:14,302
Ma cosa succede se ci fossero
qualche santo graal qui.

1162
00:47:14,302 --> 00:47:17,010
E se noi non facciamo un passo
indietro ma un passo enorme in avanti

1163
00:47:17,010 --> 00:47:19,180
e implementare un data
struttura attraverso la quale si

1164
00:47:19,180 --> 00:47:22,870
possono trovare elementi come Jack o
Christine o altri elementi

1165
00:47:22,870 --> 00:47:25,870
in questo array in vero tempo costante?

1166
00:47:25,870 --> 00:47:26,920
La ricerca è costante.

1167
00:47:26,920 --> 00:47:28,320
Elimina è costante.

1168
00:47:28,320 --> 00:47:29,570
Inserisci è costante.

1169
00:47:29,570 --> 00:47:32,260
Tutte queste operazioni sono costanti.

1170
00:47:32,260 --> 00:47:33,750
Sarebbe il nostro Santo Graal.

1171
00:47:33,750 --> 00:47:36,690
Ed è qui che abbiamo
prenderà la prossima volta.

1172
00:47:36,690 --> 00:47:38,600
Vediamo allora.

1173
00:47:38,600 --> 00:47:39,371