1
00:00:00,000 --> 00:00:11,860

2
00:00:11,860 --> 00:00:13,120
>> SPEAKER 1: Va bene, quindi siamo indietro.

3
00:00:13,120 --> 00:00:14,480
Benvenuti a CS50.

4
00:00:14,480 --> 00:00:16,510
Questa è la fine della settimana di sette.

5
00:00:16,510 --> 00:00:20,200
Quindi ricorda che l'ultima volta, abbiamo iniziato
guardando un po 'più sofisticato

6
00:00:20,200 --> 00:00:21,100
strutture di dati.

7
00:00:21,100 --> 00:00:25,110
Poiché fino ad ora, tutti abbiamo avuto davvero
a nostra disposizione era questo, un array.

8
00:00:25,110 --> 00:00:29,340
>> Ma prima di scartare l'array come non
affatto interessante, che anzi

9
00:00:29,340 --> 00:00:33,570
in realtà, quali sono alcuni dei
vantaggi di questo semplice dei dati

10
00:00:33,570 --> 00:00:34,560
struttura così lontano?

11
00:00:34,560 --> 00:00:36,110
Che è bravo?

12
00:00:36,110 --> 00:00:39,450
Per quanto abbiamo visto?

13
00:00:39,450 --> 00:00:42,540
Che cos'hai?

14
00:00:42,540 --> 00:00:44,028
Niente.

15
00:00:44,028 --> 00:00:45,020
>> STUDENTE: [incomprensibile].

16
00:00:45,020 --> 00:00:45,395
>> SPEAKER 1: Che cos'è?

17
00:00:45,395 --> 00:00:46,410
>> STUDENTE: [incomprensibile].

18
00:00:46,410 --> 00:00:47,000
>> SPEAKER 1: Dimensione fissa.

19
00:00:47,000 --> 00:00:51,260
OK, quindi perché è dimensione fissa bene però?

20
00:00:51,260 --> 00:00:53,180
>> STUDENTE: [incomprensibile].

21
00:00:53,180 --> 00:00:56,240
>> SPEAKER 1: OK, quindi è efficace in
nel senso che è possibile allocare un

22
00:00:56,240 --> 00:01:00,070
quantità fissa di spazio, che si spera
è precisamente tanto

23
00:01:00,070 --> 00:01:01,180
lo spazio che vuoi.

24
00:01:01,180 --> 00:01:02,720
In modo che possa essere assolutamente un plus.

25
00:01:02,720 --> 00:01:06,530
>> Qual è un altro lato di un array?

26
00:01:06,530 --> 00:01:07,610
Sì?

27
00:01:07,610 --> 00:01:08,750
>> STUDENTE: [incomprensibile].

28
00:01:08,750 --> 00:01:09,550
>> SPEAKER 1: Tutto il - scusate?

29
00:01:09,550 --> 00:01:11,270
>> STUDENTE: [incomprensibile].

30
00:01:11,270 --> 00:01:13,620
>> SPEAKER 1: Tutte le caselle nella memoria
o accanto all'altro.

31
00:01:13,620 --> 00:01:15,220
Ed è utile - perché?

32
00:01:15,220 --> 00:01:15,970
Questo è abbastanza vero.

33
00:01:15,970 --> 00:01:18,611
Ma come possiamo sfruttare questa verità?

34
00:01:18,611 --> 00:01:21,500
>> STUDENTE: [incomprensibile].

35
00:01:21,500 --> 00:01:24,490
>> SPEAKER 1: Esatto, siamo in grado di tenere traccia di
dove tutto è solo conoscendo

36
00:01:24,490 --> 00:01:28,560
un indirizzo, cioè l'indirizzo del
primo byte di quel pezzo di memoria.

37
00:01:28,560 --> 00:01:30,420
O, nel caso della stringa,
l'indirizzo del primo

38
00:01:30,420 --> 00:01:31,460
char in quella stringa.

39
00:01:31,460 --> 00:01:33,330
E da lì, possiamo trovare
la fine della stringa.

40
00:01:33,330 --> 00:01:35,710
Possiamo trovare il secondo elemento, l'
terzo elemento, e così via.

41
00:01:35,710 --> 00:01:38,740
>> E così il modo elegante per descrivere che
caratteristica è che gli array ci danno

42
00:01:38,740 --> 00:01:40,020
accesso casuale.

43
00:01:40,020 --> 00:01:44,330
Semplicemente utilizzando la parentesi quadra
notazione e un numero, è possibile passare alla

44
00:01:44,330 --> 00:01:48,070
uno specifico elemento dell'array
in tempo costante, grande O

45
00:01:48,070 --> 00:01:49,810
di una, per così dire.

46
00:01:49,810 --> 00:01:51,080
>> Ma ci sono stati alcuni aspetti negativi.

47
00:01:51,080 --> 00:01:53,110
Ciò che un array non fare molto facilmente?

48
00:01:53,110 --> 00:01:55,810

49
00:01:55,810 --> 00:01:57,170
Che non bravo?

50
00:01:57,170 --> 00:01:58,810
>> STUDENTE: [incomprensibile].

51
00:01:58,810 --> 00:01:59,860
>> SPEAKER 1: Che cos'è?

52
00:01:59,860 --> 00:02:00,530
>> STUDENTE: [incomprensibile].

53
00:02:00,530 --> 00:02:01,460
>> SPEAKER 1: espansione in formato.

54
00:02:01,460 --> 00:02:04,800
Così i lati negativi della matrice sono
esattamente il contrario di ciò che il

55
00:02:04,800 --> 00:02:05,540
sono aspetti positivi.

56
00:02:05,540 --> 00:02:07,610
Così uno dei lati negativi è
che si tratta di una dimensione fissa.

57
00:02:07,610 --> 00:02:09,400
Così non si può davvero crescere.

58
00:02:09,400 --> 00:02:13,510
È possibile riassegnare un pezzo più grande di
memoria, e quindi spostare i vecchi elementi

59
00:02:13,510 --> 00:02:14,460
nel nuovo array.

60
00:02:14,460 --> 00:02:18,060
E poi libera la vecchia matrice, per
esempio, usando malloc o un analogo

61
00:02:18,060 --> 00:02:21,180
funzione chiamata realloc, che
riallocazione di memoria.

62
00:02:21,180 --> 00:02:25,490
>> Realloc, per inciso, cerca di dare
memoria che è prossima alla matrice

63
00:02:25,490 --> 00:02:26,610
che hai già.

64
00:02:26,610 --> 00:02:28,740
Ma potrebbe spostare le cose
intorno tutto.

65
00:02:28,740 --> 00:02:30,710
Ma insomma, che è costoso, giusto?

66
00:02:30,710 --> 00:02:33,440
Perché se si dispone di un pezzo di memoria di
queste dimensioni, ma si vuole veramente uno

67
00:02:33,440 --> 00:02:36,710
di queste dimensioni, e si desidera conservare
gli elementi originali, avete

68
00:02:36,710 --> 00:02:40,510
circa un processo di copia tempo lineare
che deve avvenire da

69
00:02:40,510 --> 00:02:41,900
vecchia matrice nuova.

70
00:02:41,900 --> 00:02:44,630
E la realtà sta chiedendo il funzionamento
ripetutamente sistema e

71
00:02:44,630 --> 00:02:48,340
ancora per grandi blocchi di memoria possono iniziare
a costare un po 'di tempo pure.

72
00:02:48,340 --> 00:02:52,250
Quindi è sia una benedizione e una maledizione in
mascherare, il fatto che questi array

73
00:02:52,250 --> 00:02:53,860
sono di dimensione fissa.

74
00:02:53,860 --> 00:02:56,790
Ma se introduciamo invece qualcosa
come questo, che abbiamo chiamato un linked

75
00:02:56,790 --> 00:03:00,580
lista, si ottiene un paio di aspetti positivi e
pochi inconvenienti anche qui.

76
00:03:00,580 --> 00:03:05,780
>> Quindi una lista collegata è semplicemente un dato
Struttura composta da strutture del C in questa

77
00:03:05,780 --> 00:03:09,850
caso, in cui una struct, richiamo, è solo
di un contenitore per una o più specifiche

78
00:03:09,850 --> 00:03:11,100
tipi di variabili.

79
00:03:11,100 --> 00:03:16,110
In questo caso, ciò che fanno i tipi di dati
sembrano essere all'interno della struttura che

80
00:03:16,110 --> 00:03:17,600
ultima volta che abbiamo chiamato un nodo?

81
00:03:17,600 --> 00:03:19,380
Ciascuno di questi rettangoli è un nodo.

82
00:03:19,380 --> 00:03:22,660
E ciascuno dei rettangoli più piccoli
all'interno di esso è un tipo di dati.

83
00:03:22,660 --> 00:03:25,300
Quali tipi abbiamo detto
erano il Lunedi?

84
00:03:25,300 --> 00:03:26,478
Sì?

85
00:03:26,478 --> 00:03:27,870
>> STUDENTE: [incomprensibile].

86
00:03:27,870 --> 00:03:30,721
>> SPEAKER 1: Una variabile e di un puntatore, o
più specificamente, un int, per n,

87
00:03:30,721 --> 00:03:32,180
e un puntatore in basso.

88
00:03:32,180 --> 00:03:35,360
Sia di quelli capita di essere a 32 bit, a
almeno su un computer come questo CS50

89
00:03:35,360 --> 00:03:37,980
Appliance, e quindi sono
disegnata in modo uguale in grandezza.

90
00:03:37,980 --> 00:03:42,260
>> Così che cosa sta utilizzando il puntatore
anche se a quanto pare per?

91
00:03:42,260 --> 00:03:47,690
Perché aggiungere questo freccia ora, quando le matrici erano
così bello e pulito e semplice?

92
00:03:47,690 --> 00:03:50,460
Che cosa sta facendo per il puntatore
noi in ciascuno di questi nodi?

93
00:03:50,460 --> 00:03:52,160
>> STUDENTE: [incomprensibile].

94
00:03:52,160 --> 00:03:52,465
>> SPEAKER 1: Esattamente.

95
00:03:52,465 --> 00:03:54,120
E 'che ti dice dove
il prossimo è.

96
00:03:54,120 --> 00:03:57,350
Così ho sorta di usare l'analogia della
utilizzando un filo a sorta di

97
00:03:57,350 --> 00:03:59,180
infilare questi nodi insieme.

98
00:03:59,180 --> 00:04:01,760
E questo è esattamente quello che stiamo facendo con
puntatori perché ciascuno di essi

99
00:04:01,760 --> 00:04:06,360
blocchi di memoria possono essere o non essere
contiguo, back to back to back

100
00:04:06,360 --> 00:04:09,500
all'interno di RAM, perché ogni volta che si
chiamare malloc dicendo, dammi abbastanza

101
00:04:09,500 --> 00:04:12,510
byte per un nuovo nodo, potrebbe
essere qui o potrebbe essere qui.

102
00:04:12,510 --> 00:04:13,120
Potrebbe essere qui.

103
00:04:13,120 --> 00:04:13,730
Potrebbe essere qui.

104
00:04:13,730 --> 00:04:14,640
È solo che non sai.

105
00:04:14,640 --> 00:04:17,880
>> Ma usando puntatori negli indirizzi di
tali nodi, si può cucire loro

106
00:04:17,880 --> 00:04:22,370
insieme in un modo che sembra visivamente
come una lista, anche se queste cose sono

107
00:04:22,370 --> 00:04:26,770
tutti sparsi per tutta la una o
le due o le quattro gigabyte di RAM

108
00:04:26,770 --> 00:04:28,760
all'interno del proprio computer.

109
00:04:28,760 --> 00:04:33,230
>> Così il rovescio della medaglia, allora, di
una lista collegata è che cosa?

110
00:04:33,230 --> 00:04:34,670
Che cosa è un prezzo che siamo
apparentemente pagare?

111
00:04:34,670 --> 00:04:36,010
>> STUDENTE: [incomprensibile].

112
00:04:36,010 --> 00:04:36,920
>> SPEAKER 1: Più spazio, giusto?

113
00:04:36,920 --> 00:04:39,340
Abbiamo, in questo caso, raddoppiato l'importo
di spazio, perché siamo andati

114
00:04:39,340 --> 00:04:43,500
da 32 bit per ogni nodo, per ogni
int, così ora i 64 bit, perché dobbiamo

115
00:04:43,500 --> 00:04:45,050
mantenere intorno un puntatore pure.

116
00:04:45,050 --> 00:04:48,860
Si ottiene una maggiore efficienza se il struct
è più grande di questa cosa semplice.

117
00:04:48,860 --> 00:04:52,020
Se hai in realta 'uno studente all'interno
di cui è una coppia di stringhe per

118
00:04:52,020 --> 00:04:55,430
nome e la casa, forse un numero ID,
forse alcuni altri campi del tutto.

119
00:04:55,430 --> 00:04:59,000
>> Quindi, se si dispone di una grande struttura abbastanza,
poi forse il costo del puntatore è

120
00:04:59,000 --> 00:05:00,010
Non un grande affare.

121
00:05:00,010 --> 00:05:03,570
Questo è un po 'un caso d'angolo in tale
stiamo memorizzare una semplice primitiva tale

122
00:05:03,570 --> 00:05:04,760
all'interno della lista collegata.

123
00:05:04,760 --> 00:05:05,790
Ma il punto è lo stesso.

124
00:05:05,790 --> 00:05:08,230
Stai sicuramente spendere di più
memoria, ma che stai ricevendo

125
00:05:08,230 --> 00:05:08,990
flessibilità.

126
00:05:08,990 --> 00:05:12,280
Perché ora se voglio aggiungere un elemento
all'inizio di questa lista,

127
00:05:12,280 --> 00:05:14,340
Devo assegnare un nuovo nodo.

128
00:05:14,340 --> 00:05:17,180
E devo aggiornare solo quelli
frecce in qualche modo semplicemente spostando

129
00:05:17,180 --> 00:05:17,980
alcune indicazioni circa.

130
00:05:17,980 --> 00:05:20,580
>> Se voglio inserire qualcosa nella
metà della lista, non c'è bisogno di

131
00:05:20,580 --> 00:05:24,410
spingere tutti a parte come abbiamo fatto in
passato settimane con i nostri volontari che

132
00:05:24,410 --> 00:05:25,700
rappresentato un array.

133
00:05:25,700 --> 00:05:29,470
Posso solo assegnare un nuovo nodo e
poi basta puntare il mouse in

134
00:05:29,470 --> 00:05:32,290
direzioni diverse, perché non
devono restare in effettivo

135
00:05:32,290 --> 00:05:35,670
ricordo una vera linea come ho disegnato
qui sullo schermo.

136
00:05:35,670 --> 00:05:38,400
>> E poi, infine, se si desidera inserire
qualcosa alla fine della lista, è

137
00:05:38,400 --> 00:05:39,210
ancora più facile.

138
00:05:39,210 --> 00:05:43,320
Questa è una sorta di notazione arbitraria,
ma pointer di 34, prendere una supposizione.

139
00:05:43,320 --> 00:05:46,710
Qual è il valore del suo puntatore più
probabilmente sorta disegnato come un vecchio

140
00:05:46,710 --> 00:05:47,700
antenna scuola lì?

141
00:05:47,700 --> 00:05:48,920
>> STUDENTE: [incomprensibile].

142
00:05:48,920 --> 00:05:49,900
>> SPEAKER 1: E 'probabilmente nullo.

143
00:05:49,900 --> 00:05:52,710
E in effetti questo è uno di autore
rappresentazione del nulla.

144
00:05:52,710 --> 00:05:56,310
Ed è nullo perché è assolutamente
bisogno di sapere dove la fine di un Linked

145
00:05:56,310 --> 00:06:00,050
elenco è, per non continuare a seguire e
seguito e seguendo queste frecce

146
00:06:00,050 --> 00:06:01,170
ad un certo valore immondizia.

147
00:06:01,170 --> 00:06:06,230
Quindi nulla significherà che non c'è
più nodi a destra del numero 34,

148
00:06:06,230 --> 00:06:07,200
in questo caso.

149
00:06:07,200 --> 00:06:10,270
>> Quindi proponiamo che possiamo implementare
questo nodo in codice.

150
00:06:10,270 --> 00:06:12,130
E abbiamo visto questo tipo
di sintassi prima.

151
00:06:12,130 --> 00:06:15,090
Typedef solo definisce un nuovo tipo di
noi, ci dà un sinonimo come

152
00:06:15,090 --> 00:06:17,100
stringa era per char *.

153
00:06:17,100 --> 00:06:21,030
In questo caso, sta andando a darci
notazione abbreviata in modo che il nodo struct

154
00:06:21,030 --> 00:06:24,010
invece può solo essere scritta come
nodo, che è molto più pulito.

155
00:06:24,010 --> 00:06:25,360
E 'molto meno prolisso.

156
00:06:25,360 --> 00:06:30,080
>> All'interno di un nodo è apparentemente un int
chiamato n, e quindi un nodo struct *

157
00:06:30,080 --> 00:06:34,670
che significa esattamente quello che volevamo l'
frecce per dire, un puntatore ad un altro

158
00:06:34,670 --> 00:06:36,940
nodo dello stesso tipo di dati esatto.

159
00:06:36,940 --> 00:06:40,300
E propongo che potremmo implementare un
funzione di ricerca come questo, che a

160
00:06:40,300 --> 00:06:41,890
prima vista potrebbe sembrare
un po 'complessa.

161
00:06:41,890 --> 00:06:43,330
Ma vediamo nel contesto.

162
00:06:43,330 --> 00:06:45,480
>> Lasciatemi passare all'apparecchio qui.

163
00:06:45,480 --> 00:06:48,460
Permettetemi di aprire un file chiamato
Lista zero virgola h.

164
00:06:48,460 --> 00:06:53,950
E che contiene solo la definizione che
appena visto un momento fa per questi dati

165
00:06:53,950 --> 00:06:55,390
tipo denominato nodo.

166
00:06:55,390 --> 00:06:57,350
Così abbiamo messo che in un file h dot.

167
00:06:57,350 --> 00:07:01,430
>> E per inciso, anche se questo
programma che state per vedere è

168
00:07:01,430 --> 00:07:05,410
Non tutto quel complesso, è infatti
convenzione quando si scrive un programma per

169
00:07:05,410 --> 00:07:10,270
mettere le cose come i tipi di dati, per tirare
costanti a volte, all'interno della vostra

170
00:07:10,270 --> 00:07:13,210
file di intestazione e non necessariamente in
il file C, certamente quando la tua

171
00:07:13,210 --> 00:07:17,370
programmi diventano sempre più grandi, in modo che
sapete dove cercare, sia per

172
00:07:17,370 --> 00:07:20,840
documentazione in alcuni casi, o
di base come questo, le

173
00:07:20,840 --> 00:07:22,360
definizione di un certo tipo.

174
00:07:22,360 --> 00:07:25,680
>> Se ora apro list zero virgola
c, notare un paio di cose.

175
00:07:25,680 --> 00:07:29,090
Include una serie di file di intestazione, la maggior parte delle
di cui abbiamo visto prima.

176
00:07:29,090 --> 00:07:31,980
Esso include un proprio file di intestazione.

177
00:07:31,980 --> 00:07:35,200
>> E per inciso, perché questo è doppio
citazioni qui, a differenza dell'angolo

178
00:07:35,200 --> 00:07:38,340
parentesi sulla linea che
Ho evidenziato lì?

179
00:07:38,340 --> 00:07:39,180
>> STUDENTE: [incomprensibile].

180
00:07:39,180 --> 00:07:40,460
>> SPEAKER 1: Sì, quindi è un file locale.

181
00:07:40,460 --> 00:07:44,300
Quindi, se è un file locale del proprio qui
sulla linea 15, per esempio, si utilizza

182
00:07:44,300 --> 00:07:46,570
le doppie virgolette invece
delle parentesi angolari.

183
00:07:46,570 --> 00:07:48,270
>> Ora questo è abbastanza interessante.

184
00:07:48,270 --> 00:07:51,830
Notate che ho dichiarato un globale
variabile in questo programma on line 18

185
00:07:51,830 --> 00:07:55,910
chiamato per primo, l'idea è questa è
sarà un puntatore al primo

186
00:07:55,910 --> 00:07:59,190
nodo nella mia lista collegata, e ho
inizializzato a NULL, perché ho

187
00:07:59,190 --> 00:08:02,310
non assegnato alcun effettivo
nodi ancora pochi.

188
00:08:02,310 --> 00:08:07,570
>> Quindi questo rappresenta, pittoricamente, quello che abbiamo
ha visto un momento fa nella foto come

189
00:08:07,570 --> 00:08:10,090
che puntatore all'estrema
a sinistra lato.

190
00:08:10,090 --> 00:08:12,260
Quindi, in questo momento, che puntatore
non ha una freccia.

191
00:08:12,260 --> 00:08:14,590
E invece è proprio nulla.

192
00:08:14,590 --> 00:08:17,880
Ma rappresenta quello che sarà l'
indirizzo del primo effettivo

193
00:08:17,880 --> 00:08:19,480
nodo in questa lista.

194
00:08:19,480 --> 00:08:22,120
Così ho implementato è un globale
perché, come avrete capito, tutto questo

195
00:08:22,120 --> 00:08:25,310
programma non nella vita è implementare
una lista collegata per me.

196
00:08:25,310 --> 00:08:27,050
>> Ora ho un paio di prototipi qui.

197
00:08:27,050 --> 00:08:31,190
Ho deciso di implementare caratteristiche come
cancellazione, inserimento, ricerca, e

198
00:08:31,190 --> 00:08:31,740
attraversamento -

199
00:08:31,740 --> 00:08:35,210
l'ultimo solo di essere a piedi attraverso il
elenco, stampando i suoi elementi.

200
00:08:35,210 --> 00:08:36,750
Ed ora ecco la mia routine principale.

201
00:08:36,750 --> 00:08:39,890
E noi non spendere troppo tempo su
questi dal momento che questo è una sorta di, si spera

202
00:08:39,890 --> 00:08:41,780
vecchio cappello da ora.

203
00:08:41,780 --> 00:08:45,370
>> Ho intenzione di effettuare le seguenti operazioni,
mentre l'utente collabora.

204
00:08:45,370 --> 00:08:47,300
Quindi uno, ho intenzione di stampare
questo menù.

205
00:08:47,300 --> 00:08:49,420
Ed è stato formattato come
pulito come ho potuto.

206
00:08:49,420 --> 00:08:52,240
Se l'utente digita in uno, il che significa
vogliono cancellare qualcosa.

207
00:08:52,240 --> 00:08:54,560
Se l'utente digita in due, il che significa
vogliono inserire qualcosa.

208
00:08:54,560 --> 00:08:55,930
E così via.

209
00:08:55,930 --> 00:08:58,270
Sto per poi spingere
poi per un comando.

210
00:08:58,270 --> 00:08:59,300
E poi ho intenzione di usare GetInt.

211
00:08:59,300 --> 00:09:02,790
>> Quindi questo è davvero un semplice menuing
interfaccia in cui è sufficiente digitare

212
00:09:02,790 --> 00:09:05,270
una mappatura per un numero
di quei comandi.

213
00:09:05,270 --> 00:09:08,730
E ora ho un interruttore pulito bella
dichiarazione che sta per accendere

214
00:09:08,730 --> 00:09:10,090
qualunque sia l'utente ha digitato dentro

215
00:09:10,090 --> 00:09:12,180
E se digitati uno, io
chiamare cancellare e rompere.

216
00:09:12,180 --> 00:09:14,380
Se hanno scritto due, io
chiamare inserire e rompersi.

217
00:09:14,380 --> 00:09:16,490
>> E ora notato che ho messo ogni
di questi sulla stessa linea.

218
00:09:16,490 --> 00:09:18,360
Questa è solo una decisione stilistica.

219
00:09:18,360 --> 00:09:20,210
In genere abbiamo visto qualcosa
come questo.

220
00:09:20,210 --> 00:09:23,260
Ma ho deciso, francamente, il mio programma
sembrava più leggibile perché

221
00:09:23,260 --> 00:09:25,980
era solo quattro casi di
basta elencare in questo modo.

222
00:09:25,980 --> 00:09:28,360
Uso del tutto legittimo di stile.

223
00:09:28,360 --> 00:09:31,480
E ho intenzione di fare questo a condizione che la
utente non ha digitato zero, che io

224
00:09:31,480 --> 00:09:33,910
deciso significherà che vogliono smettere di fumare.

225
00:09:33,910 --> 00:09:36,630
>> Così ora accorgo che cosa sto
intenzione di fare qui.

226
00:09:36,630 --> 00:09:38,650
Ho intenzione di liberare l'elenco apparentemente.

227
00:09:38,650 --> 00:09:40,230
Ma più su che in un attimo.

228
00:09:40,230 --> 00:09:41,640
Si deve prima eseguire questo programma.

229
00:09:41,640 --> 00:09:45,250
Quindi permettetemi di fare un terminale più grande
finestra, dot barra elenco 0.

230
00:09:45,250 --> 00:09:49,510
Ho intenzione di andare avanti e inserire da
tipizzazione due, un numero come 50, e ora

231
00:09:49,510 --> 00:09:51,590
vedrete la lista è ora 50.

232
00:09:51,590 --> 00:09:53,380
E il mio testo solo scorrere un po '.

233
00:09:53,380 --> 00:09:55,940
Così ora notare la lista contiene
il numero 50.

234
00:09:55,940 --> 00:09:58,220
>> Facciamo un altro inserto prendendo due.

235
00:09:58,220 --> 00:10:01,630
Andiamo a digitare il numero come uno.

236
00:10:01,630 --> 00:10:03,940
List è ora uno, seguito da 50.

237
00:10:03,940 --> 00:10:06,020
Quindi questa è solo una rappresentazione testuale
dell'elenco.

238
00:10:06,020 --> 00:10:10,550
E cerchiamo di inserire un altro numero come
il numero 42, che è auspicabilmente

239
00:10:10,550 --> 00:10:14,620
andando a finire in mezzo, perché
questo programma, in particolare le specie che

240
00:10:14,620 --> 00:10:16,320
elementi come li inserisce.

241
00:10:16,320 --> 00:10:17,220
Quindi non abbiamo.

242
00:10:17,220 --> 00:10:20,730
Super semplice programma che potrebbe
assolutamente ho usato un array, ma io

243
00:10:20,730 --> 00:10:23,280
capita di usare una lista concatenata
solo così posso dinamicamente

244
00:10:23,280 --> 00:10:24,610
crescere e ridurla.

245
00:10:24,610 --> 00:10:28,470
>> Quindi, diamo uno sguardo per la ricerca, se io
comando eseguito tre, voglio cercare

246
00:10:28,470 --> 00:10:31,040
per, ad esempio, il numero 43.

247
00:10:31,040 --> 00:10:34,190
E nulla è stato a quanto pare ha trovato,
perché sono tornato alcuna risposta.

248
00:10:34,190 --> 00:10:35,010
Quindi cerchiamo di farlo di nuovo.

249
00:10:35,010 --> 00:10:35,690
Cerca.

250
00:10:35,690 --> 00:10:39,520
Facciamo ricerca di 50, o meglio la ricerca
per 42, che ha una bella

251
00:10:39,520 --> 00:10:40,850
poco significato sottile.

252
00:10:40,850 --> 00:10:42,610
E ho trovato il senso della vita lì.

253
00:10:42,610 --> 00:10:44,990
Numero 42, se non si conosce
il riferimento, Google esso.

254
00:10:44,990 --> 00:10:45,350
D'accordo.

255
00:10:45,350 --> 00:10:47,130
Così che cosa è questo programma fatto per me?

256
00:10:47,130 --> 00:10:50,660
E 'solo che mi ha permesso di inserire così
lontano e la ricerca di elementi.

257
00:10:50,660 --> 00:10:53,650
>> Andiamo avanti veloce, poi, a
che funzione ci lanciò un'occhiata a

258
00:10:53,650 --> 00:10:55,360
il Lunedi come un teaser.

259
00:10:55,360 --> 00:10:59,620
Quindi questa funzione, io sostengo, ricerche di
un elemento nell'elenco da prima

260
00:10:59,620 --> 00:11:03,830
uno, chiedendo all'utente e quindi chiamando
GetInt per ottenere un int reale

261
00:11:03,830 --> 00:11:05,060
che si desidera cercare.

262
00:11:05,060 --> 00:11:06,460
>> Poi notare questo.

263
00:11:06,460 --> 00:11:10,690
Ho intenzione di creare una variabile temporanea
in linea 188 chiamato puntatore -

264
00:11:10,690 --> 00:11:11,270
PTR -

265
00:11:11,270 --> 00:11:12,440
avrebbe chiamato nulla.

266
00:11:12,440 --> 00:11:16,140
Ed è un puntatore a un nodo
perché ho detto nodo * lì.

267
00:11:16,140 --> 00:11:19,900
E sono in fase di inizializzazione che sia uguale a
prima in modo che io effettivamente ho il mio

268
00:11:19,900 --> 00:11:22,860
dito, per così dire, sul molto
primo elemento della lista.

269
00:11:22,860 --> 00:11:27,460
Quindi, se la mia mano destra qui è PTR sono
indicando la stessa cosa che prima

270
00:11:27,460 --> 00:11:28,670
sta indicando.

271
00:11:28,670 --> 00:11:31,430
>> Così ora torna in codice,
cosa succede dopo -

272
00:11:31,430 --> 00:11:35,070
questo è un paradigma comune quando l'iterazione
su una struttura come un

273
00:11:35,070 --> 00:11:35,970
lista collegata.

274
00:11:35,970 --> 00:11:40,410
Ho intenzione di effettuare le seguenti operazioni mentre
puntatore non è uguale a null Così, mentre

275
00:11:40,410 --> 00:11:47,530
il mio dito non è puntato a un certo nullo
valore, se il puntatore a freccia n è uguale a n.

276
00:11:47,530 --> 00:11:52,290
Ci accorgiamo prima che n è quello che il
utente digitato per GetInts chiamano qui.

277
00:11:52,290 --> 00:11:54,280
>> E puntatore a freccia n significa che cosa?

278
00:11:54,280 --> 00:11:59,020
Beh, se torniamo alla foto qui,
se ho un dito che indica

279
00:11:59,020 --> 00:12:02,960
tale primo nodo contenente nove, l'
freccia essenzialmente significa andare a quel

280
00:12:02,960 --> 00:12:08,860
nodo e afferrare il valore in posizione n,
in questo caso, il campo dati chiamato n.

281
00:12:08,860 --> 00:12:14,120
>> Per inciso - e abbiamo visto una coppia
di settimane fa, quando qualcuno ha chiesto -

282
00:12:14,120 --> 00:12:18,840
questa sintassi è nuovo, ma non lo fa
ci danno poteri che noi

283
00:12:18,840 --> 00:12:20,040
non hanno già.

284
00:12:20,040 --> 00:12:25,325
Qual è stata questa frase equivale a utilizzare
dot notazione e la stella di un paio

285
00:12:25,325 --> 00:12:29,490
di settimane fa, quando abbiamo staccata indietro
questo strato un po 'prematuramente?

286
00:12:29,490 --> 00:12:31,780
>> STUDENTE: [incomprensibile].

287
00:12:31,780 --> 00:12:38,880
>> SPEAKER 1: Esatto, era stella, e
poi era stella dot n, con

288
00:12:38,880 --> 00:12:41,930
tra parentesi qui, che guarda,
Francamente, penso che un sacco

289
00:12:41,930 --> 00:12:43,320
più criptico di leggere.

290
00:12:43,320 --> 00:12:46,270
Ma la stella puntatore, come sempre,
mezzo ci vanno.

291
00:12:46,270 --> 00:12:49,090
E una volta che ci sei, quali dati
campo si desidera accedere?

292
00:12:49,090 --> 00:12:52,730
Ebbene si utilizza la notazione del punto di accesso
un campo di dati struct, e io

293
00:12:52,730 --> 00:12:54,140
specificamente vogliono n.

294
00:12:54,140 --> 00:12:56,240
>> Francamente, direi questo
è solo più difficile da leggere.

295
00:12:56,240 --> 00:12:58,080
E 'più difficile di ricordare dove
fanno le parentesi vanno, la

296
00:12:58,080 --> 00:12:59,030
stella e tutto il resto.

297
00:12:59,030 --> 00:13:02,150
Così il mondo ha adottato alcuni sintattica
zucchero, per così dire.

298
00:13:02,150 --> 00:13:04,740
Solo un modo sexy per dire,
questo è equivalente, e

299
00:13:04,740 --> 00:13:05,970
forse più intuitivo.

300
00:13:05,970 --> 00:13:09,600
Se il puntatore è davvero un puntatore, il
freccia significa notazione ci vanno e trovano

301
00:13:09,600 --> 00:13:11,890
il campo in questo caso chiama n.

302
00:13:11,890 --> 00:13:13,660
>> Quindi, se lo trovo, nota quello che faccio.

303
00:13:13,660 --> 00:13:17,430
Ho semplicemente stampare fuori, ho trovato per cento i,
collegare il valore per quella int.

304
00:13:17,430 --> 00:13:20,730
Chiamo dormire per un secondo solo per tipo
di pausa le cose sullo schermo per

305
00:13:20,730 --> 00:13:22,900
dare all'utente una seconda di assorbire
quello che è appena accaduto.

306
00:13:22,900 --> 00:13:24,290
E poi mi rompo.

307
00:13:24,290 --> 00:13:26,330
Altrimenti, che cosa devo fare?

308
00:13:26,330 --> 00:13:30,960
Aggiorno puntatore alla pari
puntatore a freccia accanto.

309
00:13:30,960 --> 00:13:35,840
>> Quindi, tanto per essere chiari, questo significa andare
lì, usando la mia notazione vecchia scuola.

310
00:13:35,840 --> 00:13:39,580
Quindi questo significa solo andare a qualsiasi
si sta indicando, che in molto

311
00:13:39,580 --> 00:13:43,660
primo caso è che sto indicando
la struttura con nove in esso.

312
00:13:43,660 --> 00:13:44,510
Così sono andato lì.

313
00:13:44,510 --> 00:13:47,880
E allora significa che la notazione del punto,
ottenere il valore successivo.

314
00:13:47,880 --> 00:13:50,470
>> Ma il valore, anche se è disegnato
come stretto, è solo un numero.

315
00:13:50,470 --> 00:13:51,720
E 'un indirizzo numerico.

316
00:13:51,720 --> 00:13:55,670
Quindi questa riga di codice, sia
scritto come questo, il più criptico

317
00:13:55,670 --> 00:14:00,190
modo, o come questo, il leggermente più
modo intuitivo, significa solo spostare la mia mano

318
00:14:00,190 --> 00:14:03,460
dal primo nodo a quello successivo,
e poi quella successiva, e poi l'

319
00:14:03,460 --> 00:14:05,320
successivo, e così via.

320
00:14:05,320 --> 00:14:09,920
>> Quindi non ci soffermeremo sull'altro
implementazioni di inserire e cancellare

321
00:14:09,920 --> 00:14:14,030
e di attraversamento, i primi due dei
che sono abbastanza coinvolti.

322
00:14:14,030 --> 00:14:17,010
E penso che sia abbastanza facile da ottenere
perso quando farlo verbalmente.

323
00:14:17,010 --> 00:14:19,890
Ma cosa possiamo fare qui è
cercare di determinare in che modo

324
00:14:19,890 --> 00:14:21,640
farlo al meglio visivamente.

325
00:14:21,640 --> 00:14:24,800
Perché io proporrei che se noi
desiderare di inserire elementi in questa

326
00:14:24,800 --> 00:14:26,680
elenco esistente, che
ha cinque elementi -

327
00:14:26,680 --> 00:14:29,530
9, 17, 22, 26, e 33 -

328
00:14:29,530 --> 00:14:33,300
se dovessi realizzare questo in
codice, ho bisogno di prendere in considerazione come andare

329
00:14:33,300 --> 00:14:34,160
a fare questo.

330
00:14:34,160 --> 00:14:37,720
>> E vorrei proporre piccoli passi
per cui, in questo caso, voglio dire, che cosa sono

331
00:14:37,720 --> 00:14:41,090
i possibili scenari che abbiamo
potrebbe incontrare in generale?

332
00:14:41,090 --> 00:14:44,120
Quando si implementa inserto per un linked
elenco, questo accade solo per essere un

333
00:14:44,120 --> 00:14:46,090
esempio specifico di dimensioni cinque.

334
00:14:46,090 --> 00:14:50,420
Beh, se si desidera inserire un numero,
come dire il numero uno, e

335
00:14:50,420 --> 00:14:53,380
mantenere l'ordine ordinato, dove
ovviamente fa il numero uno necessità di

336
00:14:53,380 --> 00:14:55,686
andare in questo esempio specifico?

337
00:14:55,686 --> 00:14:56,840
Come agli inizi.

338
00:14:56,840 --> 00:15:00,030
>> Ma ciò che è interessante è che
Se si desidera inserire uno in questo

339
00:15:00,030 --> 00:15:04,100
elenco, che cosa speciale puntatore bisogno
essere aggiornati a quanto pare?

340
00:15:04,100 --> 00:15:04,610
Primo.

341
00:15:04,610 --> 00:15:07,830
Quindi direi, questo è il primo caso
che potremmo prendere in considerazione, una

342
00:15:07,830 --> 00:15:11,140
scenario che richiede l'inserimento di
l'inizio della lista.

343
00:15:11,140 --> 00:15:15,400
>> Andiamo coratella fuori forse un facile o addirittura
semplice caso, relativamente parlando.

344
00:15:15,400 --> 00:15:18,110
Supponiamo che io voglio inserire il
numero 35 in modo ordinato.

345
00:15:18,110 --> 00:15:20,600
E, ovviamente, spetta laggiù.

346
00:15:20,600 --> 00:15:25,320
Quindi cosa puntatore ovviamente sta per
devono essere aggiornati in questo scenario?

347
00:15:25,320 --> 00:15:30,060
Puntatore 34 del divenire non nullo
ma l'indirizzo della struct

348
00:15:30,060 --> 00:15:31,800
contenente il numero 35.

349
00:15:31,800 --> 00:15:32,750
Ecco, questo è caso, due.

350
00:15:32,750 --> 00:15:36,190
Così già, io sono sorta di quantizzazione
quanto lavoro che devo fare qui.

351
00:15:36,190 --> 00:15:39,880
>> E, infine, il caso centrale evidente è
anzi, in mezzo, se voglio

352
00:15:39,880 --> 00:15:45,870
inserire qualcosa come dire 23, che va
tra il 23 e il 26, ma

353
00:15:45,870 --> 00:15:48,680
Ora le cose si fanno un po 'più
coinvolto perché ciò che

354
00:15:48,680 --> 00:15:52,800
puntatori devono essere cambiate?

355
00:15:52,800 --> 00:15:56,680
Quindi 22 ha ovviamente bisogno di essere cambiato
perché non può puntare a 26 più.

356
00:15:56,680 --> 00:16:00,320
Ha bisogno di puntare al nuovo nodo che
Dovrò allocare chiamando

357
00:16:00,320 --> 00:16:01,770
malloc o qualche equivalente.

358
00:16:01,770 --> 00:16:05,990
>> Ma poi ho anche bisogno che il nuovo nodo, 23
in questo caso, per avere il suo puntatore

359
00:16:05,990 --> 00:16:07,870
indicando chi?

360
00:16:07,870 --> 00:16:08,560
26.

361
00:16:08,560 --> 00:16:10,380
E ci sara 'un
ordine delle operazioni qui.

362
00:16:10,380 --> 00:16:13,410
Perché se faccio questo stupidamente, e io
per l'avvio esempio all'inizio di

363
00:16:13,410 --> 00:16:16,040
la lista, e il mio obiettivo è quello di inserire 23.

364
00:16:16,040 --> 00:16:18,610
E posso controllare, appartiene
qui, vicino a nove?

365
00:16:18,610 --> 00:16:18,950
No.

366
00:16:18,950 --> 00:16:20,670
Ha appartengono qui, accanto a 17?

367
00:16:20,670 --> 00:16:20,940
No.

368
00:16:20,940 --> 00:16:22,530
Lo fa appartiene qui accanto a 22?

369
00:16:22,530 --> 00:16:23,300
Sì.

370
00:16:23,300 --> 00:16:26,400
>> Ora, se io sono stupido qui, e non
pensare questo attraverso, potrei

371
00:16:26,400 --> 00:16:28,320
allocare il mio nuovo nodo per il 23.

372
00:16:28,320 --> 00:16:32,080
Potrei aggiornare il puntatore da
il nodo chiamato 22, indicando

373
00:16:32,080 --> 00:16:33,080
esso al nuovo nodo.

374
00:16:33,080 --> 00:16:36,140
E allora che cosa devo aggiornare
puntatore del nuovo nodo di essere?

375
00:16:36,140 --> 00:16:38,120
>> STUDENTE: [incomprensibile].

376
00:16:38,120 --> 00:16:38,385
>> SPEAKER 1: Esattamente.

377
00:16:38,385 --> 00:16:39,710
Indicando 26.

378
00:16:39,710 --> 00:16:45,590
Ma dannazione se non avessi già aggiorno
Puntatore del 22 per puntare a questo ragazzo, e

379
00:16:45,590 --> 00:16:48,260
ora ho orfani, il resto
della lista, per così dire.

380
00:16:48,260 --> 00:16:52,140
Così ordine delle operazioni qui
sta per essere importante.

381
00:16:52,140 --> 00:16:55,100
>> Per fare questo potrei rubare,
dire, sei volontari.

382
00:16:55,100 --> 00:16:57,650
E vediamo se non siamo in grado di fare questo
visivamente invece di codice-saggio.

383
00:16:57,650 --> 00:16:59,330
E noi abbiamo qualche bella lo stress
palle per voi oggi.

384
00:16:59,330 --> 00:17:02,510
OK, come su di uno, due, nel
indietro - alla fine lì.

385
00:17:02,510 --> 00:17:04,530
tre, quattro, tutti e due
ragazzi alla fine.

386
00:17:04,530 --> 00:17:05,579
E cinque, sei.

387
00:17:05,579 --> 00:17:05,839
Certo.

388
00:17:05,839 --> 00:17:06,450
Cinque e sei.

389
00:17:06,450 --> 00:17:08,390
Va bene e verremo
a voi la prossima volta.

390
00:17:08,390 --> 00:17:09,640
Va bene, andiamo su.

391
00:17:09,640 --> 00:17:12,010

392
00:17:12,010 --> 00:17:14,819
>> Bene, visto che sei qui in primo luogo,
ti piacerebbe essere quello goffamente

393
00:17:14,819 --> 00:17:16,119
in Google Glass qui?

394
00:17:16,119 --> 00:17:19,075
Va bene, quindi, OK, vetro,
registrare un video.

395
00:17:19,075 --> 00:17:22,720

396
00:17:22,720 --> 00:17:24,589
OK, tu sei a posto.

397
00:17:24,589 --> 00:17:27,950
>> Va bene, quindi se voi ragazzi può venire
qui, ho preparato in anticipo

398
00:17:27,950 --> 00:17:30,110
alcuni numeri.

399
00:17:30,110 --> 00:17:31,240
Va bene, vieni qui.

400
00:17:31,240 --> 00:17:33,440
E perché non te ne vai un po '
inoltre in questo modo.

401
00:17:33,440 --> 00:17:35,520
E vediamo, qual è il tuo nome,
con il vetro di Google?

402
00:17:35,520 --> 00:17:35,910
>> STUDENTE: Ben.

403
00:17:35,910 --> 00:17:36,230
>> SPEAKER 1: Ben?

404
00:17:36,230 --> 00:17:38,380
OK, Ben, è sarà il primo, letteralmente.

405
00:17:38,380 --> 00:17:40,580
Quindi stiamo per inviarti
alla fine della fase.

406
00:17:40,580 --> 00:17:41,670
Va bene, e il tuo nome?

407
00:17:41,670 --> 00:17:41,990
>> STUDENTE: Jason.

408
00:17:41,990 --> 00:17:44,530
>> SPEAKER 1: Jason, OK viene
essere il numero nove.

409
00:17:44,530 --> 00:17:46,700
Quindi, se volete seguire Ben in quel modo.

410
00:17:46,700 --> 00:17:47,010
>> STUDENTE: Jill.

411
00:17:47,010 --> 00:17:49,630
>> SPEAKER 1: Jill, si sta andando ad essere
17, che se avessi fatto questo più

412
00:17:49,630 --> 00:17:51,260
intelligente, avrei
partire all'altra estremità.

413
00:17:51,260 --> 00:17:52,370
Si va così.

414
00:17:52,370 --> 00:17:53,030
22.

415
00:17:53,030 --> 00:17:53,670
E tu sei?

416
00:17:53,670 --> 00:17:53,980
>> STUDENTE: Maria.

417
00:17:53,980 --> 00:17:56,130
>> SPEAKER 1: Maria, sarete 22.

418
00:17:56,130 --> 00:17:58,420
E il tuo nome è?

419
00:17:58,420 --> 00:17:58,810
>> STUDENTE: Chris.

420
00:17:58,810 --> 00:18:00,100
>> SPEAKER 1: Chris, sarete 26.

421
00:18:00,100 --> 00:18:00,740
E poi, infine.

422
00:18:00,740 --> 00:18:01,400
>> STUDENTE: Diana.

423
00:18:01,400 --> 00:18:02,670
>> SPEAKER 1: Diana, sarete 34.

424
00:18:02,670 --> 00:18:03,920
Quindi vieni un po 'qui.

425
00:18:03,920 --> 00:18:06,360
>> Va bene, così perfetto ordinati
ordinare già.

426
00:18:06,360 --> 00:18:09,600
E andiamo avanti e fare questo
in modo che possiamo veramente -

427
00:18:09,600 --> 00:18:11,720
Ben sei solo tipo di ricerca
fuori nel nulla lì.

428
00:18:11,720 --> 00:18:15,670
OK, quindi andiamo avanti e raffigurano questo
usando le braccia, proprio come mi è stato, appunto,

429
00:18:15,670 --> 00:18:16,250
quello che sta succedendo.

430
00:18:16,250 --> 00:18:19,540
Quindi, andare avanti e dare voi stessi un
piede o due tra di voi.

431
00:18:19,540 --> 00:18:22,900
E andare avanti e puntare con una mano per
chi si dovrebbe puntare a

432
00:18:22,900 --> 00:18:23,470
sulla base di questo.

433
00:18:23,470 --> 00:18:25,890
E se sei nullo basta puntare
dritto verso il pavimento.

434
00:18:25,890 --> 00:18:27,690
OK, tutto bene.

435
00:18:27,690 --> 00:18:32,290
>> Così ora abbiamo una lista collegata, e mi ha lasciato
Propongo che io interpreto il ruolo di

436
00:18:32,290 --> 00:18:35,110
PTR, quindi non mi dilungherò
portare questo giro.

437
00:18:35,110 --> 00:18:37,830
E poi - qualcuno stupido convention -
è possibile chiamare questo tutto quello che vuoi -

438
00:18:37,830 --> 00:18:39,800
puntatore del predecessore, puntatore pred -

439
00:18:39,800 --> 00:18:43,930
è solo il soprannome che abbiamo dato in
il nostro codice di esempio per la mia mano sinistra.

440
00:18:43,930 --> 00:18:47,240
L'altra mano che sta per essere tenuta
tenere traccia di chi è chi nel

441
00:18:47,240 --> 00:18:48,400
seguenti scenari.

442
00:18:48,400 --> 00:18:52,390
>> Quindi immagino, prima, voglio cogliere off
quel primo esempio di inserimento, diciamo

443
00:18:52,390 --> 00:18:54,330
20, nella lista.

444
00:18:54,330 --> 00:18:57,160
Quindi ho intenzione di bisogno di qualcuno che
incarnare il numero 20 per noi.

445
00:18:57,160 --> 00:18:58,950
Quindi ho bisogno di qualcuno malloc
da parte del pubblico.

446
00:18:58,950 --> 00:18:59,380
Andiamo su.

447
00:18:59,380 --> 00:19:00,340
Qual è il tuo nome?

448
00:19:00,340 --> 00:19:01,300
>> STUDENTE: Brian.

449
00:19:01,300 --> 00:19:05,270
>> SPEAKER 1: Brian, tutto a posto, in modo da
è il nodo contenente 20.

450
00:19:05,270 --> 00:19:06,810
Va bene, vieni qui.

451
00:19:06,810 --> 00:19:10,025
E ovviamente, dove
Brian non appartiene?

452
00:19:10,025 --> 00:19:12,190
Quindi, nel mezzo di - effettivamente,
aspetta un attimo.

453
00:19:12,190 --> 00:19:13,420
Stiamo facendo questo per ordine.

454
00:19:13,420 --> 00:19:17,170
Stiamo facendo questo molto più difficile
quanto dovrebbe essere a prima.

455
00:19:17,170 --> 00:19:21,210
OK, stiamo andando a libera Brian
e realloc Brian come cinque.

456
00:19:21,210 --> 00:19:23,680
>> OK, ora vogliamo inserire
Brian come cinque.

457
00:19:23,680 --> 00:19:25,960
Quindi forza qui accanto
Ben solo per un momento.

458
00:19:25,960 --> 00:19:28,250
E si può probabilmente dire
dove questa storia sta andando.

459
00:19:28,250 --> 00:19:30,500
Ma cerchiamo di riflettere attentamente su
l'ordine delle operazioni.

460
00:19:30,500 --> 00:19:32,880
Ed è proprio questa visuale
che sta per allineare

461
00:19:32,880 --> 00:19:34,080
con quel codice di esempio.

462
00:19:34,080 --> 00:19:40,120
Così qui ho PTR puntando inizialmente
non a Ben, di per sé, ma a qualsiasi

463
00:19:40,120 --> 00:19:43,245
valore che egli contiene, che in questo caso
è - cosa c'è di nuovo il tuo nome?

464
00:19:43,245 --> 00:19:43,670
>> STUDENTE: Jason.

465
00:19:43,670 --> 00:19:47,350
>> SPEAKER 1: Jason, così sia Ben e io sono
indicando Jason in questo momento.

466
00:19:47,350 --> 00:19:49,700
Così ora ho di determinare,
da dove viene Brian appartiene?

467
00:19:49,700 --> 00:19:53,500
Quindi l'unica cosa che ho accesso a
in questo momento è il suo elemento di dati n.

468
00:19:53,500 --> 00:19:58,280
Quindi ho intenzione di controllo, viene
Brian meno di Jason?

469
00:19:58,280 --> 00:19:59,770
La risposta è vera.

470
00:19:59,770 --> 00:20:03,680
>> Così che ora deve accadere,
nel giusto ordine?

471
00:20:03,680 --> 00:20:07,120
Ho bisogno di aggiornare il numero di puntatori
in totale in questa storia?

472
00:20:07,120 --> 00:20:10,720
Dove la mia mano è ancora puntato verso
Jason, e la tua mano - se si desidera

473
00:20:10,720 --> 00:20:12,930
mettere la mano come, sorta di, mi
non so, un punto di domanda.

474
00:20:12,930 --> 00:20:14,070
OK, bene.

475
00:20:14,070 --> 00:20:15,670
>> Va bene, in modo da avere
alcuni candidati.

476
00:20:15,670 --> 00:20:20,500
Sia Ben o io o Brian o Jason
o di chiunque altro, che

477
00:20:20,500 --> 00:20:21,370
puntatori bisogno di cambiare?

478
00:20:21,370 --> 00:20:23,260
Quanti in tutto?

479
00:20:23,260 --> 00:20:24,080
>> OK, quindi due.

480
00:20:24,080 --> 00:20:27,090
Il mio puntatore non importa più
perché io sono solo temporanei.

481
00:20:27,090 --> 00:20:31,370
Quindi è questi due ragazzi, presumibilmente,
sia Ben e Brian.

482
00:20:31,370 --> 00:20:34,410
Quindi lasciatemi propongo aggiorniamo
Ben, visto che è in primo luogo.

483
00:20:34,410 --> 00:20:36,350
Il primo elemento di questa lista
ora sta per essere Brian.

484
00:20:36,350 --> 00:20:38,070
Così Ben punto a Brian.

485
00:20:38,070 --> 00:20:39,320
OK, ora che cosa?

486
00:20:39,320 --> 00:20:41,950

487
00:20:41,950 --> 00:20:43,460
>> Chi viene puntato contro chi?

488
00:20:43,460 --> 00:20:44,710
>> STUDENTE: [incomprensibile].

489
00:20:44,710 --> 00:20:46,180
>> SPEAKER 1: OK così Brian ha
per puntare a Jason.

490
00:20:46,180 --> 00:20:48,360
Ma ho perso le tracce di tale puntatore?

491
00:20:48,360 --> 00:20:49,980
Posso sapere dove Jason è?

492
00:20:49,980 --> 00:20:50,790
>> STUDENTE: [incomprensibile].

493
00:20:50,790 --> 00:20:52,620
>> SPEAKER 1: che faccio, visto che sono
il puntatore temporaneo.

494
00:20:52,620 --> 00:20:55,110
E presumibilmente, non ho cambiato
per puntare al nuovo nodo.

495
00:20:55,110 --> 00:20:58,300
Così possiamo semplicemente avere Brian punto
a chi sto indicando.

496
00:20:58,300 --> 00:20:59,000
E abbiamo finito.

497
00:20:59,000 --> 00:21:01,890
Così caso uno, inserimento alla
inizio della lista.

498
00:21:01,890 --> 00:21:02,950
Ci sono stati due passaggi chiave.

499
00:21:02,950 --> 00:21:06,750
Uno, dobbiamo aggiornare Ben, e poi
dobbiamo anche aggiornare Brian.

500
00:21:06,750 --> 00:21:09,230
E poi io non devo preoccuparsi
scarpinare attraverso il resto del

501
00:21:09,230 --> 00:21:12,680
lista, perché abbiamo già trovato il suo
posizione, perché apparteneva alla

502
00:21:12,680 --> 00:21:14,080
sinistra del primo elemento.

503
00:21:14,080 --> 00:21:15,400
>> Va bene, quindi abbastanza semplice.

504
00:21:15,400 --> 00:21:18,110
In realtà, si sente come ci siamo quasi
rendendo questo troppo complicato.

505
00:21:18,110 --> 00:21:20,240
Quindi cerchiamo di oggi coratella largo della fine
della lista, e vedere dove

506
00:21:20,240 --> 00:21:21,380
la complessità inizia.

507
00:21:21,380 --> 00:21:24,560
Quindi, se ora, io alloc da parte del pubblico.

508
00:21:24,560 --> 00:21:25,540
Chiunque vuole giocare 55?

509
00:21:25,540 --> 00:21:26,700
Va bene, ho visto la prima mano.

510
00:21:26,700 --> 00:21:29,620
Andiamo su.

511
00:21:29,620 --> 00:21:30,030
Già.

512
00:21:30,030 --> 00:21:31,177
Qual è il tuo nome?

513
00:21:31,177 --> 00:21:32,310
>> STUDENTE: [incomprensibile].

514
00:21:32,310 --> 00:21:33,240
>> SPEAKER 1: Habata.

515
00:21:33,240 --> 00:21:33,890
OK, andiamo su.

516
00:21:33,890 --> 00:21:35,730
Sarete il numero 55.

517
00:21:35,730 --> 00:21:37,820
Quindi, ovviamente, appartiene
alla fine della lista.

518
00:21:37,820 --> 00:21:41,850
Quindi cerchiamo di replay della simulazione con me
essendo il PTR solo per un momento.

519
00:21:41,850 --> 00:21:44,050
Quindi sono prima di andare a puntare a
qualunque Ben sta indicando.

520
00:21:44,050 --> 00:21:45,900
Stiamo entrambi puntando ora a Brian.

521
00:21:45,900 --> 00:21:48,420
Quindi 55 non è inferiore a cinque.

522
00:21:48,420 --> 00:21:52,510
Quindi ho intenzione di aggiornare me stesso
che punta al prossimo puntatore di Brian, che

523
00:21:52,510 --> 00:21:54,450
ora è ovviamente Jason.

524
00:21:54,450 --> 00:21:57,310
55 non è inferiore a nove, così
Ho intenzione di aggiornare PTR.

525
00:21:57,310 --> 00:21:58,890
Ho intenzione di aggiornare PTR.

526
00:21:58,890 --> 00:22:02,290
Ho intenzione di aggiornare PTR
Ho intenzione di aggiornare PTR.

527
00:22:02,290 --> 00:22:05,060
E ho intenzione di - hmm, che cosa è
il tuo nome?

528
00:22:05,060 --> 00:22:05,560
>> STUDENTE: Diana.

529
00:22:05,560 --> 00:22:09,190
>> SPEAKER 1: Diana è rivolto, ovviamente,
a nulla con la mano sinistra.

530
00:22:09,190 --> 00:22:13,030
Così dove Habata realtà
appartengono chiaramente?

531
00:22:13,030 --> 00:22:15,050
A sinistra, qui.

532
00:22:15,050 --> 00:22:19,460
Allora, come faccio a sapere di metterla qui
Penso di aver fatto un casino.

533
00:22:19,460 --> 00:22:22,420
Perché ciò che è arte PTR
questo momento nel tempo?

534
00:22:22,420 --> 00:22:23,240
NULL.

535
00:22:23,240 --> 00:22:25,580
Così, anche se, visivamente, possiamo
ovviamente vedere tutti questi

536
00:22:25,580 --> 00:22:26,610
ragazzi qui sul palco.

537
00:22:26,610 --> 00:22:29,680
Io non ho tenuto traccia del precedente
persona nell'elenco.

538
00:22:29,680 --> 00:22:33,210
Non ho un dito puntato fuori,
in questo caso, il numero di nodo 34.

539
00:22:33,210 --> 00:22:34,760
>> Quindi cerchiamo di iniziare effettivamente questo sopra.

540
00:22:34,760 --> 00:22:37,560
Così ora io in realtà ho bisogno
una seconda variabile locale.

541
00:22:37,560 --> 00:22:40,980
E questo è quello che vedrete nel
codice C campione reale, dove, come vado,

542
00:22:40,980 --> 00:22:45,860
quando aggiorno la mia mano destra per puntare
Jason, lasciando dietro di Brian, ho

543
00:22:45,860 --> 00:22:51,440
meglio iniziare a usare la mano sinistra per
aggiornare dove mi trovavo, in modo che come vado

544
00:22:51,440 --> 00:22:52,700
attraverso questa lista -

545
00:22:52,700 --> 00:22:55,040
più goffamente di quanto volessi
ora qui visivamente -

546
00:22:55,040 --> 00:22:56,740
Ho intenzione di arrivare al
fine dell'elenco.

547
00:22:56,740 --> 00:23:00,020
>> Questa mano è ancora nullo, che è abbastanza
inutile, non per indicare

548
00:23:00,020 --> 00:23:02,980
Sono chiaramente alla fine della lista,
ma ora almeno ho questa

549
00:23:02,980 --> 00:23:08,270
puntatore predecessore puntamento qui, quindi
ora quali mani e quello che hanno bisogno di puntatori

550
00:23:08,270 --> 00:23:10,150
essere aggiornato?

551
00:23:10,150 --> 00:23:13,214
Quale mano vuoi
riconfigurare primo?

552
00:23:13,214 --> 00:23:15,190
>> STUDENTE: [incomprensibile].

553
00:23:15,190 --> 00:23:16,220
>> SPEAKER 1: OK, quindi di Diana.

554
00:23:16,220 --> 00:23:21,110
Dove vuoi puntare
Puntatore a sinistra di Diana a?

555
00:23:21,110 --> 00:23:23,620
In 55, presumibilmente, in modo che
abbiamo inserito lì.

556
00:23:23,620 --> 00:23:25,560
E dove dovrebbe andare 55 puntatore?

557
00:23:25,560 --> 00:23:27,000
Giù, in rappresentanza null.

558
00:23:27,000 --> 00:23:28,890
E le mie mani, a questo punto, non
importa, perché erano solo

559
00:23:28,890 --> 00:23:30,070
variabili temporanee.

560
00:23:30,070 --> 00:23:31,030
Così ora abbiamo finito.

561
00:23:31,030 --> 00:23:34,650
>> Quindi la complessità aggiuntiva lì - e
non è così difficile da attuare,

562
00:23:34,650 --> 00:23:38,660
ma abbiamo bisogno di una variabile secondaria per rendere
Assicurarsi che prima di passare il mio diritto

563
00:23:38,660 --> 00:23:42,140
mano, aggiorno il valore della mia sinistra
mano, puntatore pred in questo caso, così

564
00:23:42,140 --> 00:23:45,860
che ho una freccia scorrevole
per tenere traccia di dove mi trovavo.

565
00:23:45,860 --> 00:23:49,360
Ora, come un a parte, se stai pensando questo
attraverso, questo si sente come se fosse un

566
00:23:49,360 --> 00:23:51,490
poco fastidioso dover tenere
traccia di questa mano sinistra.

567
00:23:51,490 --> 00:23:54,015
>> Cosa sarebbe un'altra soluzione
a questo problema sono stati?

568
00:23:54,015 --> 00:23:56,500
Se avete avuto modo di ridisegnare i dati
struttura stiamo parlando

569
00:23:56,500 --> 00:23:59,630
attraversando in questo momento?

570
00:23:59,630 --> 00:24:02,690
Se questo solo tipo di sente un po '
fastidioso avere, tipo, due puntatori

571
00:24:02,690 --> 00:24:08,430
passare attraverso la lista, chi altro potrebbe
hanno, in un mondo ideale, mantenuto

572
00:24:08,430 --> 00:24:10,160
informazioni di cui abbiamo bisogno?

573
00:24:10,160 --> 00:24:11,360
Sì?

574
00:24:11,360 --> 00:24:12,610
>> STUDENTE: [incomprensibile].

575
00:24:12,610 --> 00:24:15,160

576
00:24:15,160 --> 00:24:16,150
>> SPEAKER 1: Esattamente.

577
00:24:16,150 --> 00:24:19,130
Destra così non c'è in realtà un interessante
germe di un'idea.

578
00:24:19,130 --> 00:24:22,470
E questa idea di un puntatore precedente,
indicando l'elemento precedente.

579
00:24:22,470 --> 00:24:25,580
Che cosa succede se ho appena incarnata che
all'interno della lista stessa?

580
00:24:25,580 --> 00:24:27,810
E sta andando essere difficile da visualizzare
questo senza tutta la carta

581
00:24:27,810 --> 00:24:28,830
cadere a terra.

582
00:24:28,830 --> 00:24:31,860
Ma supponiamo che questi ragazzi utilizzati sia
delle loro mani per avere una precedente

583
00:24:31,860 --> 00:24:35,950
puntatore, e un puntatore prossimo, così
attuare quello che chiameremo un doppiamente

584
00:24:35,950 --> 00:24:36,830
lista collegata.

585
00:24:36,830 --> 00:24:41,090
Questo mi avrebbe permesso a sorta di rewind,
molto più facilmente senza di me, la

586
00:24:41,090 --> 00:24:43,800
programmatore, dover tenere
traccia manualmente -

587
00:24:43,800 --> 00:24:44,980
veramente manualmente -

588
00:24:44,980 --> 00:24:47,280
di dove ero stato precedentemente
nell'elenco.

589
00:24:47,280 --> 00:24:48,110
Quindi non lo faremo.

590
00:24:48,110 --> 00:24:50,950
Vi terremo le cose semplici perché è
intenzione di venire ad un prezzo, il doppio

591
00:24:50,950 --> 00:24:53,450
molto spazio per i puntatori,
se si vuole un secondo.

592
00:24:53,450 --> 00:24:55,760
Ma questa è davvero una comune
struttura di dati nota come

593
00:24:55,760 --> 00:24:57,410
doppiamente lista collegata.

594
00:24:57,410 --> 00:25:01,310
>> Facciamo l'esempio finale qui e mettere
questi ragazzi fuori dalla loro miseria.

595
00:25:01,310 --> 00:25:03,270
Così malloc 20.

596
00:25:03,270 --> 00:25:05,320
Vieni su dalla navata lì.

597
00:25:05,320 --> 00:25:06,280
Va bene, come ti chiami?

598
00:25:06,280 --> 00:25:07,440
>> STUDENTE: [incomprensibile].

599
00:25:07,440 --> 00:25:07,855
>> SPEAKER 1: Scusa?

600
00:25:07,855 --> 00:25:08,480
>> STUDENTE: [incomprensibile].

601
00:25:08,480 --> 00:25:09,410
>> SPEAKER 1: Demeron?

602
00:25:09,410 --> 00:25:10,230
OK andiamo su.

603
00:25:10,230 --> 00:25:11,910
Tu sarai 20.

604
00:25:11,910 --> 00:25:14,720
È, ovviamente, sta per
appartengono tra il 17 e il 22.

605
00:25:14,720 --> 00:25:16,150
Quindi, mi permetta di imparare la lezione.

606
00:25:16,150 --> 00:25:18,150
Ho intenzione di iniziare puntatore
indicando Brian.

607
00:25:18,150 --> 00:25:21,190
E ho intenzione di avere la mia mano sinistra
aggiornare solo a Brian come mi muovo a

608
00:25:21,190 --> 00:25:23,600
Jason, il controllo fa 20 meno di nove anni?

609
00:25:23,600 --> 00:25:24,060
No.

610
00:25:24,060 --> 00:25:25,430
È di 20 meno di 17?

611
00:25:25,430 --> 00:25:25,880
No.

612
00:25:25,880 --> 00:25:27,450
È di 20 meno di 22?

613
00:25:27,450 --> 00:25:28,440
Sì.

614
00:25:28,440 --> 00:25:34,070
Quindi cosa puntatori o le mani hanno bisogno di cambiare
dove stanno puntando ora?

615
00:25:34,070 --> 00:25:37,070
>> Così siamo in grado di fare 17 che punta a 20.

616
00:25:37,070 --> 00:25:37,860
Così va bene.

617
00:25:37,860 --> 00:25:40,080
Dove vogliamo puntare
il puntatore del momento?

618
00:25:40,080 --> 00:25:41,330
Al 22.

619
00:25:41,330 --> 00:25:45,410
E sappiamo dove 22 è, ancora una volta grazie
al mio puntatore temporaneo.

620
00:25:45,410 --> 00:25:46,760
Quindi siamo OK lì.

621
00:25:46,760 --> 00:25:49,440
Quindi, a causa di tale memorizzazione temporanea
Ho tenuto traccia di dove tutti sono.

622
00:25:49,440 --> 00:25:55,055
E ora si può andare visivamente in cui
si appartiene, e ora abbiamo bisogno di 1, 2, 3,

623
00:25:55,055 --> 00:25:58,410
4, 5, 6, 7, 8, 9 stress balls,
e un applauso per

624
00:25:58,410 --> 00:25:59,770
questi ragazzi, se potessimo.

625
00:25:59,770 --> 00:26:00,410
Ben fatto.

626
00:26:00,410 --> 00:26:05,320
>> [Applausi]

627
00:26:05,320 --> 00:26:06,330
>> SPEAKER 1: Va bene.

628
00:26:06,330 --> 00:26:09,860
E si può tenere i pezzi
di carta come ricordi.

629
00:26:09,860 --> 00:26:15,930
>> Va bene, allora, mi creda è molto
più facile da attraversare, che con

630
00:26:15,930 --> 00:26:17,680
esseri umani di quanto lo sia con il codice vero e proprio.

631
00:26:17,680 --> 00:26:22,690
Ma ciò che troverete in un attimo
ora, è che la stessa - Oh, grazie.

632
00:26:22,690 --> 00:26:23,630
Grazie -

633
00:26:23,630 --> 00:26:29,360
è che troverete che gli stessi dati
struttura, una lista collegata, può effettivamente

634
00:26:29,360 --> 00:26:33,200
essere utilizzato come blocco di ancora più
strutture dati sofisticate.

635
00:26:33,200 --> 00:26:37,620
>> E realizzare anche il tema qui è che
abbiamo assolutamente introdotto più

636
00:26:37,620 --> 00:26:40,060
complessità in attuazione
di questo algoritmo.

637
00:26:40,060 --> 00:26:43,940
Di inserimento, e se siamo andati attraverso di essa,
la cancellazione e la ricerca, è un po '

638
00:26:43,940 --> 00:26:46,660
più complicato di quanto
era con un array.

639
00:26:46,660 --> 00:26:48,040
Ma ci guadagno un po 'di dinamismo.

640
00:26:48,040 --> 00:26:50,180
Otteniamo una struttura dati adattivo.

641
00:26:50,180 --> 00:26:54,010
>> Ma ancora una volta, paghiamo un prezzo di avere un po 'di
ulteriori complessità, sia nella

642
00:26:54,010 --> 00:26:54,910
attuazione.

643
00:26:54,910 --> 00:26:56,750
E si sta per fornire l'accesso casuale.

644
00:26:56,750 --> 00:27:00,450
E ad essere onesti, non c'è qualche bella
pulire vetrino posso darti che

645
00:27:00,450 --> 00:27:03,120
dice qui è perché una lista concatenata
è meglio di un array.

646
00:27:03,120 --> 00:27:04,100
E lasciare le cose come stanno.

647
00:27:04,100 --> 00:27:07,520
Poiché il tema ricorrente ora, anche
di più nelle prossime settimane, è

648
00:27:07,520 --> 00:27:10,200
che non c'è necessariamente
una risposta corretta.

649
00:27:10,200 --> 00:27:13,830
>> Questo è il motivo per cui abbiamo l'asse separato
di progettazione per set problema.

650
00:27:13,830 --> 00:27:17,700
Sarà molto sensibili al contesto
se si desidera utilizzare questi dati

651
00:27:17,700 --> 00:27:21,750
struttura o quello, e sarà
dipenderà da ciò che conta per voi in termini

652
00:27:21,750 --> 00:27:24,620
delle risorse e la complessità.

653
00:27:24,620 --> 00:27:28,830
>> Ma lasciate che propongo i dati ideali
struttura, il Santo Graal, sarebbe

654
00:27:28,830 --> 00:27:32,200
qualcosa che è tempo costante,
indipendentemente dalla quantità di roba è

655
00:27:32,200 --> 00:27:36,940
al suo interno, non sarebbe sorprendente se un
struttura dati restituiti risposte in

656
00:27:36,940 --> 00:27:37,920
tempo costante.

657
00:27:37,920 --> 00:27:38,330
Sì.

658
00:27:38,330 --> 00:27:40,110
Questa parola è nel vostro dizionario enorme.

659
00:27:40,110 --> 00:27:41,550
Oppure no, questa parola non è.

660
00:27:41,550 --> 00:27:43,270
O qualsiasi problema.

661
00:27:43,270 --> 00:27:46,360
Bene vediamo se non possiamo almeno
fare un passo in quella direzione.

662
00:27:46,360 --> 00:27:50,190
>> Permettetemi di proporre una nuova struttura dati che
può essere utilizzato per diverse cose,

663
00:27:50,190 --> 00:27:52,260
in questo caso denominata tabella hash.

664
00:27:52,260 --> 00:27:55,590
E così siamo tornati alla realtà guardando
in una matrice, in questo caso, e

665
00:27:55,590 --> 00:28:00,550
un po 'arbitrariamente, ho disegnato questo
tabella hash come un array con una sorta di

666
00:28:00,550 --> 00:28:02,810
array bidimensionale -

667
00:28:02,810 --> 00:28:05,410
o meglio, è raffigurato qui come due
matrice bidimensionale - ma questo è solo

668
00:28:05,410 --> 00:28:10,770
un array di dimensione 26, tale che se ci
richiamare la tabella matrice, staffa da tavolo

669
00:28:10,770 --> 00:28:12,440
zero è il rettangolo in alto.

670
00:28:12,440 --> 00:28:15,090
Tabella staffa 25 è il rettangolo
in basso.

671
00:28:15,090 --> 00:28:18,620
Ed è così che avrei potuto disegnare un dato
struttura in cui voglio conservare

672
00:28:18,620 --> 00:28:19,790
nomi delle persone.

673
00:28:19,790 --> 00:28:24,370
>> Così, per esempio, e non voglio disegnare la
cosa tutto qui sulla testa, se io

674
00:28:24,370 --> 00:28:29,160
avuto questa matrice, che ora sto andando a
chiamare una tabella hash, e questo è di nuovo

675
00:28:29,160 --> 00:28:31,360
posizione zero.

676
00:28:31,360 --> 00:28:34,840
Questa qui è la posizione
uno, e così via.

677
00:28:34,840 --> 00:28:37,880
Io affermo che voglio usare questi dati
struttura, per amore di discussione,

678
00:28:37,880 --> 00:28:42,600
per memorizzare i nomi delle persone, Alice e Bob
e Charlie e altri nomi.

679
00:28:42,600 --> 00:28:46,110
Quindi, pensare a questo ora come gli inizi
di, diciamo, un dizionario

680
00:28:46,110 --> 00:28:47,520
con un sacco di parole.

681
00:28:47,520 --> 00:28:49,435
Capita di essere nomi
nel nostro esempio qui.

682
00:28:49,435 --> 00:28:52,560
E questo è tutto troppo germano, forse, per
l'attuazione di un correttore ortografico, come abbiamo

683
00:28:52,560 --> 00:28:54,400
potrebbe per il problema definito sei.

684
00:28:54,400 --> 00:28:59,300
>> Quindi, se abbiamo un array di dimensioni totali 26
in modo che questa è la posizione 25

685
00:28:59,300 --> 00:29:03,390
in fondo, e io sostengo che Alice è
la prima parola nel dizionario di

686
00:29:03,390 --> 00:29:07,260
nomi che voglio inserire nella RAM,
in questa struttura dati, in cui sono

687
00:29:07,260 --> 00:29:12,480
istinto che ti dice che di Alice
nome dovrebbe andare in questa serie?

688
00:29:12,480 --> 00:29:13,510
>> Abbiamo 26 opzioni.

689
00:29:13,510 --> 00:29:14,990
Dove vogliamo metterla?

690
00:29:14,990 --> 00:29:16,200
Vogliamo che lei in staffa a zero, giusto?

691
00:29:16,200 --> 00:29:18,280
A per Alice, chiamiamolo che zero.

692
00:29:18,280 --> 00:29:20,110
E B sarà uno, e C saranno due.

693
00:29:20,110 --> 00:29:22,600
Quindi andremo a scrivere
Nome qui di Alice.

694
00:29:22,600 --> 00:29:24,890
Se poi inseriamo Bob, il suo
nome andrà qui.

695
00:29:24,890 --> 00:29:27,280
Charlie andrà qui.

696
00:29:27,280 --> 00:29:30,500
E così via verso il basso attraverso
questa struttura dati.

697
00:29:30,500 --> 00:29:32,090
>> Questa è una struttura dati meraviglioso.

698
00:29:32,090 --> 00:29:32,730
Perché?

699
00:29:32,730 --> 00:29:37,460
Beh, che cosa è il tempo di esecuzione di
inserendo il nome di un essere umano in questo

700
00:29:37,460 --> 00:29:39,850
dati di struttura in questo momento?

701
00:29:39,850 --> 00:29:43,702
Dato che questa tabella è implementato,
veramente, come un array.

702
00:29:43,702 --> 00:29:44,940
Beh, è ​​un tempo costante.

703
00:29:44,940 --> 00:29:45,800
E 'ordine di uno.

704
00:29:45,800 --> 00:29:46,360
Perché?

705
00:29:46,360 --> 00:29:48,630
>> Beh come si fa a determinare
dove Alice appartiene?

706
00:29:48,630 --> 00:29:51,000
Si guarda a quale lettera del suo nome?

707
00:29:51,000 --> 00:29:51,490
Il primo.

708
00:29:51,490 --> 00:29:54,350
E si può arrivare, se si tratta di una stringa,
solo guardando stringa

709
00:29:54,350 --> 00:29:55,200
Staffa zero.

710
00:29:55,200 --> 00:29:57,110
Quindi, il carattere zero della stringa.

711
00:29:57,110 --> 00:29:57,610
Questo è facile.

712
00:29:57,610 --> 00:30:00,350
Lo abbiamo fatto in crypto
assegnazione settimane fa.

713
00:30:00,350 --> 00:30:05,310
E poi una volta che si sa che Alice
lettera è maiuscola, siamo in grado di sottrarre

714
00:30:05,310 --> 00:30:08,160
off 65 o maiuscola se stessa,
che ci dà zero.

715
00:30:08,160 --> 00:30:10,940
Così ora sappiamo che Alice appartiene
in posizione zero.

716
00:30:10,940 --> 00:30:14,240
>> E dato un puntatore a questi dati
struttura, di qualche tipo, per quanto tempo fa

717
00:30:14,240 --> 00:30:18,840
mi ci vorrà per trovare posizione
zero in un array?

718
00:30:18,840 --> 00:30:22,080
Solo un passo, a destra E 'tempo costante
causa dell'accesso casuale abbiamo

719
00:30:22,080 --> 00:30:23,780
proposto era una caratteristica di una matrice.

720
00:30:23,780 --> 00:30:28,570
Così, in breve, cercando di capire che cosa l'indice
del nome di Alice è, che è, in

721
00:30:28,570 --> 00:30:32,610
questo caso, è A, o facciamo solo risolvere
che a zero, dove B è una e C è

722
00:30:32,610 --> 00:30:34,900
due, pensando che fuori
è tempo costante.

723
00:30:34,900 --> 00:30:38,510
Non mi resta che guardarla prima lettera,
cercare di capire dove zero è un

724
00:30:38,510 --> 00:30:40,460
array è anche tempo costante.

725
00:30:40,460 --> 00:30:42,140
Quindi tecnicamente questo è
come due gradini ora.

726
00:30:42,140 --> 00:30:43,330
Ma questo è ancora costante.

727
00:30:43,330 --> 00:30:46,880
Quindi noi chiamiamo grande O di uno, quindi abbiamo
Alice inserito in questa tabella in

728
00:30:46,880 --> 00:30:48,440
tempo costante.

729
00:30:48,440 --> 00:30:50,960
>> Ma, naturalmente, devo essere
ingenuo qui, giusto?

730
00:30:50,960 --> 00:30:53,240
E se ci fosse un Aaron nella classe?

731
00:30:53,240 --> 00:30:53,990
O Alicia?

732
00:30:53,990 --> 00:30:57,230
O altri nomi che iniziano con
A. Dove stiamo andando a mettere

733
00:30:57,230 --> 00:31:00,800
quella persona, giusto?

734
00:31:00,800 --> 00:31:03,420
Voglio dire, in questo momento ci sono solo tre
persone sul tavolo, quindi forse abbiamo

735
00:31:03,420 --> 00:31:07,490
dovrebbe mettere Aaron a posizione
zero uno due tre.

736
00:31:07,490 --> 00:31:09,480
>> Giusto, potrei mettere una qui.

737
00:31:09,480 --> 00:31:13,350
Ma allora, se proviamo a inserire Davide in
questo elenco, da dove viene David andare?

738
00:31:13,350 --> 00:31:15,170
Ora il nostro sistema inizia rottura
verso il basso, giusto?

739
00:31:15,170 --> 00:31:19,210
Perché ora David finisce qui
se Aaron è in realtà qui.

740
00:31:19,210 --> 00:31:23,060
E così ora tutta questa idea di avere un
struttura dati pulita che ci dà

741
00:31:23,060 --> 00:31:28,010
inserimenti di tempo costanti non è più
costante di tempo, perché devo

742
00:31:28,010 --> 00:31:31,240
controllare, oh, dannazione, qualcuno è già
in posizione di Alice.

743
00:31:31,240 --> 00:31:35,320
>> Permettetemi di sondare il resto di questi dati
struttura, alla ricerca di un posto per mettere

744
00:31:35,320 --> 00:31:37,130
chi, come il nome di Aaron.

745
00:31:37,130 --> 00:31:39,390
E così anche questo sta iniziando
di prendere tempo lineare.

746
00:31:39,390 --> 00:31:42,710
Inoltre, se la società vuole trovare il
Aaron in questa struttura dati, e si

747
00:31:42,710 --> 00:31:45,430
controllo, e il nome di Aaron non è qui.

748
00:31:45,430 --> 00:31:47,960
Idealmente, si dovrebbe solo dire Aaron
non nella struttura dati.

749
00:31:47,960 --> 00:31:51,530
Ma se si fa iniziare a fare spazio a
Aaron dove non avrebbe dovuto essere un D

750
00:31:51,530 --> 00:31:55,600
o una E, si, nel peggiore dei casi, è necessario controllare
la struttura di dati interi, in

751
00:31:55,600 --> 00:31:59,480
qual caso essa devolve in qualcosa
lineare nella dimensione della tabella.

752
00:31:59,480 --> 00:32:00,920
>> Quindi tutto bene, io sistemo questo.

753
00:32:00,920 --> 00:32:04,200
Il problema qui è che ho avuto
26 elementi in questo array.

754
00:32:04,200 --> 00:32:05,000
Permettetemi di cambiarlo.

755
00:32:05,000 --> 00:32:06,010
Whoops.

756
00:32:06,010 --> 00:32:10,600
Permettetemi di modificarlo in modo che, invece di essere di
taglia 26 in totale, notare il fondo

757
00:32:10,600 --> 00:32:12,720
indice sta per cambiare per n meno 1.

758
00:32:12,720 --> 00:32:16,610
Se 26 è chiaramente troppo piccolo per gli esseri umani '
nomi, perché ci sono migliaia di

759
00:32:16,610 --> 00:32:20,830
nomi del mondo, facciamo solo fare
a 100 o 1000 o 10000.

760
00:32:20,830 --> 00:32:22,960
Diciamo solo destinare molto più spazio.

761
00:32:22,960 --> 00:32:27,230
>> Beh, questo non significa necessariamente diminuire
la probabilità che non avremo due

762
00:32:27,230 --> 00:32:31,510
persone con nomi che iniziano con A, e
così, si andavano a cercare di mettere un

763
00:32:31,510 --> 00:32:33,120
I nomi di luogo a zero ancora.

764
00:32:33,120 --> 00:32:36,850
Stanno ancora andando a collidere, che
significa che abbiamo bisogno di una soluzione per mettere

765
00:32:36,850 --> 00:32:41,020
Alice e Aronne e Alicia e le altre
nomi che iniziano con A altrove.

766
00:32:41,020 --> 00:32:43,460
Ma quanto di un problema è questo?

767
00:32:43,460 --> 00:32:46,870
Qual è la probabilità che si
avere collisioni in un dato

768
00:32:46,870 --> 00:32:48,240
struttura come questa?

769
00:32:48,240 --> 00:32:52,570
>> Beh, mi permetta - ci torneremo
a questa domanda qui.

770
00:32:52,570 --> 00:32:55,530
E guarda come potremmo
risolverlo prima.

771
00:32:55,530 --> 00:32:58,480
Permettetemi di tirare su questa proposta qui.

772
00:32:58,480 --> 00:33:02,020
Ciò che abbiamo appena descritto è un algoritmo,
una euristica chiamato lineare

773
00:33:02,020 --> 00:33:05,030
sondaggio in base al quale, se si è tentato di inserire
qualcosa qui in questi dati

774
00:33:05,030 --> 00:33:08,920
struttura, che si chiama una tabella hash,
e non c'è spazio lì, si

775
00:33:08,920 --> 00:33:12,000
veramente sondare la struttura dati
controllo, è disponibile questo?

776
00:33:12,000 --> 00:33:13,430
È questo Disponibile è disponibile questo?

777
00:33:13,430 --> 00:33:13,980
È questo a disposizione?

778
00:33:13,980 --> 00:33:17,550
E quando finalmente è, si inserisce il
nome che si originariamente previsto

779
00:33:17,550 --> 00:33:19,370
altrove in quella posizione.

780
00:33:19,370 --> 00:33:23,360
Ma nel caso peggiore, l'unico punto
potrebbe essere la molto inferiore dei dati di

781
00:33:23,360 --> 00:33:25,090
struttura, alla fine della matrice.

782
00:33:25,090 --> 00:33:30,130
>> Così scansione lineare, nel caso peggiore,
devolve in un algoritmo lineare dove

783
00:33:30,130 --> 00:33:34,500
Aaron, se gli capita di essere inserito all'ultimo
in questa struttura dati, potrebbe

784
00:33:34,500 --> 00:33:39,540
collidere con questa prima posizione, ma
poi finiscono per sfortuna, alla fine molto.

785
00:33:39,540 --> 00:33:43,940
Quindi questa non è una costante
tempo santo graal per noi.

786
00:33:43,940 --> 00:33:47,650
Questo metodo di inserimento di elementi in
una struttura dati chiamata hash

787
00:33:47,650 --> 00:33:52,050
tabella non sembra essere tempo costante
almeno non nel caso generale.

788
00:33:52,050 --> 00:33:54,000
Si può devolvere in qualcosa di lineare.

789
00:33:54,000 --> 00:33:56,970
>> Che importa se risolviamo collisioni
un po 'diverso?

790
00:33:56,970 --> 00:34:00,740
Quindi, ecco un più sofisticato
avvicinarsi a ciò che è ancora

791
00:34:00,740 --> 00:34:02,800
denominata tabella hash.

792
00:34:02,800 --> 00:34:05,890
E da hash, per inciso, che cosa
Insomma è l'indice che

793
00:34:05,890 --> 00:34:07,070
Mi riferivo prima.

794
00:34:07,070 --> 00:34:09,810
Per hash qualcosa può essere
pensato come un verbo.

795
00:34:09,810 --> 00:34:13,690
>> Quindi, se si hash Alice è un nome,
una funzione hash, per così dire,

796
00:34:13,690 --> 00:34:14,710
dovrebbe restituire un numero.

797
00:34:14,710 --> 00:34:18,199
In questo caso è pari a zero se lei appartiene a
posizione zero, uno, se lei appartiene a

798
00:34:18,199 --> 00:34:20,000
ubicazione uno, e così via.

799
00:34:20,000 --> 00:34:24,360
Quindi la mia funzione di hash finora è stato
super semplice, solo guardando il

800
00:34:24,360 --> 00:34:26,159
prima lettera nel nome di qualcuno.

801
00:34:26,159 --> 00:34:29,090
Ma una funzione hash prende come
Ingresso qualche pezzo di dati, un

802
00:34:29,090 --> 00:34:30,210
stringa, int, qualunque cosa.

803
00:34:30,210 --> 00:34:32,239
E sputa fuori in genere un numero.

804
00:34:32,239 --> 00:34:35,739
E questo numero è qui che i dati
elemento appartiene in una struttura dati

805
00:34:35,739 --> 00:34:37,800
conosciuto qui come una tabella hash.

806
00:34:37,800 --> 00:34:41,400
>> Quindi, solo intuitivamente, questo è un
contesto leggermente diverso.

807
00:34:41,400 --> 00:34:44,170
Questo in realtà si riferisce ad un esempio
compleanni a cui partecipano

808
00:34:44,170 --> 00:34:46,850
ci potrebbero essere fino a
31 giorni del mese.

809
00:34:46,850 --> 00:34:52,239
Ma che cosa ha fatto questa persona decide di
fare in caso di collisione?

810
00:34:52,239 --> 00:34:55,304
Contesto ora essere, non una collisione di
nomi, ma uno scontro di compleanni,

811
00:34:55,304 --> 00:35:00,760
se due persone hanno lo stesso compleanno
il 2 ottobre, per esempio.

812
00:35:00,760 --> 00:35:02,120
>> STUDENTE: [incomprensibile].

813
00:35:02,120 --> 00:35:05,010
>> SPEAKER 1: Sì, così qui abbiamo
la valorizzazione delle liste collegate.

814
00:35:05,010 --> 00:35:07,830
Quindi sembra un po 'diverso
che abbiamo disegnato in precedenza.

815
00:35:07,830 --> 00:35:10,790
Ma sembra che abbiamo a un array
sul lato sinistro.

816
00:35:10,790 --> 00:35:13,230
Questo è un indice, per non
motivo particolare.

817
00:35:13,230 --> 00:35:14,630
Ma è ancora un array.

818
00:35:14,630 --> 00:35:16,160
Si tratta di un array di puntatori.

819
00:35:16,160 --> 00:35:20,670
E ciascuno di questi elementi, ciascuno dei
questi cerchi o barre - lo slash

820
00:35:20,670 --> 00:35:23,970
che rappresenta null - ciascuno di questi
puntatori è apparentemente indicando

821
00:35:23,970 --> 00:35:25,730
quale struttura dati?

822
00:35:25,730 --> 00:35:26,890
Una lista concatenata.

823
00:35:26,890 --> 00:35:30,530
>> Così ora abbiamo la possibilità di
codificare nel nostro programma

824
00:35:30,530 --> 00:35:32,010
la dimensione della tabella.

825
00:35:32,010 --> 00:35:35,360
In questo caso, sappiamo che non c'è mai
più di 31 giorni in un mese.

826
00:35:35,360 --> 00:35:38,480
Così difficile codifica un valore come 31 è
ragionevole in quel contesto.

827
00:35:38,480 --> 00:35:42,700
Nel contesto di nomi, codifica duro
26 non è irragionevole che sia la gente

828
00:35:42,700 --> 00:35:46,340
nomi iniziano solo con, per esempio,
l'alfabeto coinvolgendo A alla Z.

829
00:35:46,340 --> 00:35:50,180
>> Siamo in grado di stipare tutti in quei dati
struttura finché, quando otteniamo una

830
00:35:50,180 --> 00:35:55,330
collisione, non mettiamo i nomi qui,
noi invece pensiamo di queste cellule

831
00:35:55,330 --> 00:36:00,270
non come corde stesse, ma come
puntatori a, per esempio, Alice.

832
00:36:00,270 --> 00:36:03,660
E allora Alice può avere un altro puntatore
ad un altro nome che inizia con

833
00:36:03,660 --> 00:36:06,150
A. E Bob in realtà va qui.

834
00:36:06,150 --> 00:36:10,850
>> E se c'è un altro nome che inizia
con B, finisce qui.

835
00:36:10,850 --> 00:36:15,070
E così ciascuno degli elementi di questa
tavolo due, se abbiamo progettato questo un

836
00:36:15,070 --> 00:36:17,350
po 'più intelligente -

837
00:36:17,350 --> 00:36:18,125
andiamo -

838
00:36:18,125 --> 00:36:22,950
se abbiamo progettato questo un po 'più
abilmente, diventa ora un dato adattivi

839
00:36:22,950 --> 00:36:27,720
struttura, dove non c'è limite rigido
da quanti elementi è possibile inserire

840
00:36:27,720 --> 00:36:30,700
in esso, perché se lo fai avere
una collisione, che va bene.

841
00:36:30,700 --> 00:36:34,690
Basta andare avanti e aggiungerla
quello che abbiamo visto un po 'fa era

842
00:36:34,690 --> 00:36:38,290
noto come un elenco collegato.

843
00:36:38,290 --> 00:36:39,690
>> Bene cerchiamo di mettere in pausa per un momento.

844
00:36:39,690 --> 00:36:42,570
Qual è la probabilità di una collisione
in primo luogo?

845
00:36:42,570 --> 00:36:45,480
Giusto, forse sto più pensando, forse
Sono più di ingegnerizzare questo problema,

846
00:36:45,480 --> 00:36:46,370
perché si sa che cosa?

847
00:36:46,370 --> 00:36:49,070
Sì, posso venire con arbitraria
Esempi di fuori della parte superiore della mia testa, come

848
00:36:49,070 --> 00:36:52,870
Allison e Aaron, ma in realtà,
data una distribuzione uniforme di

849
00:36:52,870 --> 00:36:56,990
ingressi, cioè alcuni inserimenti casuali
in una struttura di dati, ciò che è veramente

850
00:36:56,990 --> 00:36:58,580
la probabilità di una collisione?

851
00:36:58,580 --> 00:37:01,670
Ebbene si rivela, in realtà è
altissima.

852
00:37:01,670 --> 00:37:03,850
Permettetemi di generalizzare questo
problema è come questo.

853
00:37:03,850 --> 00:37:08,890
>> Quindi, in una stanza di n CS50 studenti, che cosa è
la probabilità che almeno

854
00:37:08,890 --> 00:37:11,010
due studenti in sala
hanno la stessa data di nascita?

855
00:37:11,010 --> 00:37:13,346
Quindi non c'è cosa. alcuni Hund -

856
00:37:13,346 --> 00:37:16,790
200, 300 persone qui e diversi
centinaia di persone a casa oggi.

857
00:37:16,790 --> 00:37:20,670
Quindi, se si voleva chiederci che cosa è
la probabilità di due persone

858
00:37:20,670 --> 00:37:23,930
in questa stanza hanno lo stesso compleanno,
siamo in grado di capirlo.

859
00:37:23,930 --> 00:37:26,250
E io sostengo in realtà ci sono due
persone con lo stesso compleanno.

860
00:37:26,250 --> 00:37:29,560
>> Per esempio, qualcuno
hanno compleanno oggi?

861
00:37:29,560 --> 00:37:31,340
Ieri?

862
00:37:31,340 --> 00:37:32,590
Domani?

863
00:37:32,590 --> 00:37:35,980
Va bene, così ci si sente come sto andando
di avere a che fare questo 363 o giù di lì più

864
00:37:35,980 --> 00:37:39,500
volte per capire effettivamente fuori
Se abbiamo una collisione.

865
00:37:39,500 --> 00:37:42,350
Oppure potremmo fare questo matematicamente
piuttosto che noiosamente

866
00:37:42,350 --> 00:37:43,200
fare questo.

867
00:37:43,200 --> 00:37:44,500
E proporre la seguente.

868
00:37:44,500 --> 00:37:48,740
>> Quindi propongo che potremmo modellare la
probabilità di due persone che hanno la

869
00:37:48,740 --> 00:37:55,320
stessa data di nascita come la probabilità di 1
meno la probabilità di avere nessuno

870
00:37:55,320 --> 00:37:56,290
lo stesso compleanno.

871
00:37:56,290 --> 00:37:59,960
Quindi, per ottenere questo, e questo è solo il
modo elegante per scrivere questo, per il

872
00:37:59,960 --> 00:38:03,090
prima persona nella stanza, lui o lei
può avere uno qualsiasi dei possibili

873
00:38:03,090 --> 00:38:07,370
compleanni assumendo 365 giorni l'anno,
con tante scuse a persone con

874
00:38:07,370 --> 00:38:08,760
il 29 ° compleanno di febbraio.

875
00:38:08,760 --> 00:38:13,470
>> Così la prima persona in questa stanza è libera
per avere un qualsiasi numero di compleanni

876
00:38:13,470 --> 00:38:18,280
fuori delle 365 possibilità in modo che
lo faremo 365 diviso per 365,

877
00:38:18,280 --> 00:38:18,990
che è uno.

878
00:38:18,990 --> 00:38:22,700
La prossima persona nella stanza, se l'obiettivo
è quello di evitare una collisione, può solo

879
00:38:22,700 --> 00:38:26,460
avere il suo compleanno su come
molte diverse possibili giorni?

880
00:38:26,460 --> 00:38:27,610
364.

881
00:38:27,610 --> 00:38:31,430
Quindi il secondo termine in questa espressione è
sostanza, facendo che la matematica per noi

882
00:38:31,430 --> 00:38:33,460
sottraendo fuori un giorno possibile.

883
00:38:33,460 --> 00:38:36,390
E poi il giorno dopo, il giorno successivo, il
giorno seguente difetto al numero totale

884
00:38:36,390 --> 00:38:38,100
di persone nella stanza.

885
00:38:38,100 --> 00:38:41,290
>> E se si considera poi, qual è allora
la probabilità di non avere tutti

886
00:38:41,290 --> 00:38:45,265
compleanni uniche, ma di nuovo 1 meno
che, ciò che otteniamo è espressione

887
00:38:45,265 --> 00:38:47,810
che può molto fantasiosamente
simile a questa.

888
00:38:47,810 --> 00:38:50,330
Ma è più interessante
da guardare visivamente.

889
00:38:50,330 --> 00:38:55,120
Questo è un grafico in cui sul asse x è
il numero di persone nella stanza, il

890
00:38:55,120 --> 00:38:56,180
numero di compleanni.

891
00:38:56,180 --> 00:38:59,840
Sulla asse y è la probabilità
di una collisione, due persone

892
00:38:59,840 --> 00:39:01,230
avendo lo stesso compleanno.

893
00:39:01,230 --> 00:39:05,020
>> E l'asporto da questa curva è
che, non appena si arriva a come 40

894
00:39:05,020 --> 00:39:11,110
studenti, siete in su in una probabilità del 90%
combinatorically di due

895
00:39:11,110 --> 00:39:13,550
o più persone che hanno
lo stesso compleanno.

896
00:39:13,550 --> 00:39:18,600
E una volta che si arriva a come 58 persone che è
quasi il 100% di una possibilità due

897
00:39:18,600 --> 00:39:21,310
persone in sala stanno per avere la
stessa data di nascita, anche se non c'è

898
00:39:21,310 --> 00:39:26,650
365 o 366 possibili secchi, e
solo 58 persone nella stanza.

899
00:39:26,650 --> 00:39:29,900
Proprio statisticamente è molto probabile che
ottenere collisioni, che in breve

900
00:39:29,900 --> 00:39:31,810
motiva questa discussione.

901
00:39:31,810 --> 00:39:35,890
Che anche se otteniamo fantasioso qui, e
iniziare con queste catene, siamo ancora

902
00:39:35,890 --> 00:39:36,950
intenzione di avere collisioni.

903
00:39:36,950 --> 00:39:42,710
>> In modo che pone la domanda, qual è la
costo di fare inserimenti ed eliminazioni

904
00:39:42,710 --> 00:39:44,850
in una struttura dati come questo?

905
00:39:44,850 --> 00:39:46,630
Ebbene vorrei propongo -

906
00:39:46,630 --> 00:39:51,570
e lasciatemi tornare alla schermata sopra
qui - se abbiamo n elementi nel

907
00:39:51,570 --> 00:39:56,330
elenco, quindi se stiamo cercando di inserire
n elementi, e abbiamo

908
00:39:56,330 --> 00:39:58,050
quanti secchi totali?

909
00:39:58,050 --> 00:40:03,450
Diciamo che 31 secchi totali
nel caso di compleanni.

910
00:40:03,450 --> 00:40:09,240
Qual è la lunghezza massima di un
di queste catene potenzialmente?

911
00:40:09,240 --> 00:40:12,670
>> Se ancora non c'è 31 possibili
compleanni in un dato mese.

912
00:40:12,670 --> 00:40:14,580
E siamo solo grumi tutti -

913
00:40:14,580 --> 00:40:15,580
in realtà questo è un esempio stupido.

914
00:40:15,580 --> 00:40:16,960
Facciamo 26 invece.

915
00:40:16,960 --> 00:40:20,890
Quindi, se in realtà sono persone i cui nomi
iniziare con A a Z, dando così

916
00:40:20,890 --> 00:40:22,780
noi 26 possibilità.

917
00:40:22,780 --> 00:40:25,920
E stiamo usando una struttura dati come
quello che abbiamo appena visto, per cui abbiamo

918
00:40:25,920 --> 00:40:30,210
un array di puntatori, ciascuno dei quali
indica una lista collegata dove l'

919
00:40:30,210 --> 00:40:32,360
primo elenco è di tutti
con il nome Alice.

920
00:40:32,360 --> 00:40:35,770
Il secondo elenco è ogni con l'
nome che inizia con A, a partire

921
00:40:35,770 --> 00:40:36,980
con B, e così via.

922
00:40:36,980 --> 00:40:41,020
>> Qual è la durata probabile di ciascuno di
tali elenchi se si assume una bella pulita

923
00:40:41,020 --> 00:40:45,410
distribuzione dei nomi da A a Z
attraverso l'intera struttura dati?

924
00:40:45,410 --> 00:40:50,210
Ci sono n persone nella struttura dati
diviso per 26, se sono ben

925
00:40:50,210 --> 00:40:52,110
sparsi su tutto il
struttura dati.

926
00:40:52,110 --> 00:40:54,970
Quindi la lunghezza di ciascuno di questi
catene è n diviso per 26.

927
00:40:54,970 --> 00:40:57,380
Ma nella grande notazione O, che cos'è?

928
00:40:57,380 --> 00:41:00,100

929
00:41:00,100 --> 00:41:02,440
Che cosa è che davvero?

930
00:41:02,440 --> 00:41:04,150
Quindi è davvero solo n, giusto?

931
00:41:04,150 --> 00:41:06,620
Perché abbiamo detto in passato,
ugh che si divide per 26.

932
00:41:06,620 --> 00:41:08,710
Sì, in realtà è più veloce.

933
00:41:08,710 --> 00:41:12,720
Ma in teoria, non è fondamentalmente
tutto questo veloce.

934
00:41:12,720 --> 00:41:16,040
>> Quindi, non ci sembra di essere più di tanto
più vicino a questo Santo Graal.

935
00:41:16,040 --> 00:41:17,750
In realtà, questo è solo il tempo lineare.

936
00:41:17,750 --> 00:41:20,790
Heck, a questo punto, perché non ci
basta usare una lista collegata enorme?

937
00:41:20,790 --> 00:41:23,510
Perché non basta usare un enorme
matrice per memorizzare i nomi dei

938
00:41:23,510 --> 00:41:25,010
tutti nella stanza?

939
00:41:25,010 --> 00:41:28,280
Beh, c'è ancora qualcosa
avvincente di una tabella di hash?

940
00:41:28,280 --> 00:41:30,810
C'è ancora qualcosa di interessante
una struttura dati

941
00:41:30,810 --> 00:41:33,940
che assomiglia a questo?

942
00:41:33,940 --> 00:41:35,182
Questo.

943
00:41:35,182 --> 00:41:37,050
>> STUDENTE: [incomprensibile].

944
00:41:37,050 --> 00:41:39,840
>> SPEAKER 1: Giusto, e di nuovo se è solo
un algoritmo di tempo lineare, e un

945
00:41:39,840 --> 00:41:42,780
struttura di dati in tempo lineare, perché non ho
basta memorizzare il nome di tutti in una grande

946
00:41:42,780 --> 00:41:44,210
array o in una grande lista collegata?

947
00:41:44,210 --> 00:41:47,010
E smettere di fare CS così molto più difficile
di quanto dovrebbe essere?

948
00:41:47,010 --> 00:41:49,600

949
00:41:49,600 --> 00:41:53,190
Ciò che è interessante su questo, anche
anche se ho graffiato fuori?

950
00:41:53,190 --> 00:41:54,930
>> STUDENTE: [incomprensibile].

951
00:41:54,930 --> 00:41:57,040
>> SPEAKER 1: Inserimenti non lo sono?

952
00:41:57,040 --> 00:41:58,140
Più costoso.

953
00:41:58,140 --> 00:42:03,390
Così inserimenti potenzialmente potrebbe ancora
essere costante di tempo, anche se i dati

954
00:42:03,390 --> 00:42:07,910
la struttura si presenta così, una serie di
puntatori, ognuno dei quali sta puntando

955
00:42:07,910 --> 00:42:09,550
potenzialmente una lista collegata.

956
00:42:09,550 --> 00:42:15,220
Come si potrebbe ottenere costante
inserimento tempo di nomi?

957
00:42:15,220 --> 00:42:16,280
Stick it in fronte, giusto?

958
00:42:16,280 --> 00:42:19,290
>> Se sacrifichiamo un obiettivo di progettazione da
in precedenza, in cui abbiamo voluto mantenere

959
00:42:19,290 --> 00:42:22,650
nome di tutti, per esempio, in ordine,
o tutti i numeri sul palco ordinati,

960
00:42:22,650 --> 00:42:25,020
supponiamo di avere un
lista collegata indifferenziati.

961
00:42:25,020 --> 00:42:29,960
E solo ci costa uno o due passi,
come nel caso di Ben e Brian

962
00:42:29,960 --> 00:42:32,750
precedenza, per inserire un elemento in
l'inizio della lista.

963
00:42:32,750 --> 00:42:36,090
Quindi, se non ci preoccupiamo di smistamento tutti
dei nomi che iniziano con A o tutti

964
00:42:36,090 --> 00:42:39,660
i nomi che iniziano con B, possiamo ancora
conseguire costante inserimento tempo.

965
00:42:39,660 --> 00:42:43,900
Ora guardando Alice o Bob o qualsiasi nome
più in generale, è ancora quello?

966
00:42:43,900 --> 00:42:48,100
È grande O di n diviso per 26, nella
caso ideale in cui tutti sono uniformemente

967
00:42:48,100 --> 00:42:51,190
distribuito, dove c'è il maggior numero di un
come ci sono le Z, che è probabilmente

968
00:42:51,190 --> 00:42:52,220
irrealistico.

969
00:42:52,220 --> 00:42:53,880
Ma questo è ancora lineare.

970
00:42:53,880 --> 00:42:57,120
>> Ma qui, torniamo al punto di
di notazione asintotica essere

971
00:42:57,120 --> 00:42:58,600
teoricamente vero.

972
00:42:58,600 --> 00:43:02,960
Ma nel mondo reale, se io affermo che
il mio programma può fare qualcosa di 26 volte

973
00:43:02,960 --> 00:43:06,210
più veloce della tua, il cui programma
hai intenzione di preferire usando?

974
00:43:06,210 --> 00:43:09,660
Tua o la mia, che
è 26 volte più veloce?

975
00:43:09,660 --> 00:43:14,320
Realisticamente, la persona di cui è 26
volte più veloce, anche se teoricamente

976
00:43:14,320 --> 00:43:18,790
i nostri algoritmi eseguiti nella stessa
asintotica tempo di esecuzione.

977
00:43:18,790 --> 00:43:20,940
>> Lasciatemi propongo un diverso
soluzione del tutto.

978
00:43:20,940 --> 00:43:24,380
E se questo non vi lascia sbalorditi,
siamo fuori di strutture di dati.

979
00:43:24,380 --> 00:43:27,420
Quindi questo è un trie -

980
00:43:27,420 --> 00:43:28,520
genere di un nome stupido.

981
00:43:28,520 --> 00:43:32,880
Viene da recuperi, e la parola
è scritto trie, t-r-i-e, a causa di

982
00:43:32,880 --> 00:43:34,450
recupero naturalmente suona come trie.

983
00:43:34,450 --> 00:43:36,580
Ma questa è la storia
della parola trie.

984
00:43:36,580 --> 00:43:40,980
>> Quindi un trie è infatti una specie di albero,
ed è anche un gioco di quella parola.

985
00:43:40,980 --> 00:43:46,330
E anche se non riesco a vederlo
con questa visualizzazione, un trie è un

986
00:43:46,330 --> 00:43:50,790
albero strutturato, come un albero di famiglia con
un antenato in alto e molto altro

987
00:43:50,790 --> 00:43:54,530
di nipoti e pronipoti
come le foglie sul fondo.

988
00:43:54,530 --> 00:43:58,100
Ma ogni nodo in un trie è un array.

989
00:43:58,100 --> 00:44:00,680
Ed è in un array - e sia di
una semplificazione delle per un momento - è un

990
00:44:00,680 --> 00:44:04,600
array, in questo caso, di dimensioni 26, dove
ogni nodo nuovo è una matrice di dimensione

991
00:44:04,600 --> 00:44:09,000
26, dove l'elemento zeroth in tale
Una matrice rappresenta, e l'ultimo

992
00:44:09,000 --> 00:44:11,810
elemento in ogni tale
matrice rappresenta Z.

993
00:44:11,810 --> 00:44:15,520
>> Quindi propongo, quindi, che questi dati
struttura, noto come un trie, può essere

994
00:44:15,520 --> 00:44:17,600
utilizzato anche per memorizzare le parole.

995
00:44:17,600 --> 00:44:21,740
Abbiamo visto un momento fa, come abbiamo potuto conservare
parole, o in questo caso i nomi, e noi

996
00:44:21,740 --> 00:44:25,440
visto in precedenza come possiamo memorizzare i numeri,
ma se ci concentriamo sui nomi o stringhe

997
00:44:25,440 --> 00:44:27,460
qui, notare ciò che è interessante.

998
00:44:27,460 --> 00:44:32,210
Io sostengo che il nome Maxwell è
interno di questa struttura dati.

999
00:44:32,210 --> 00:44:33,730
Dove vedi Maxwell?

1000
00:44:33,730 --> 00:44:35,140
>> STUDENTE: [incomprensibile].

1001
00:44:35,140 --> 00:44:36,240
>> SPEAKER 1: A sinistra.

1002
00:44:36,240 --> 00:44:39,910
Quindi, ciò che è interessante di questi dati
la struttura è piuttosto che il negozio

1003
00:44:39,910 --> 00:44:46,200
stringa M-A-X-W-E-L-L backslash zero, l'intera
contiguo, quello che invece fa

1004
00:44:46,200 --> 00:44:46,890
sta seguendo.

1005
00:44:46,890 --> 00:44:50,510
Se questo è un trie come la struttura di dati,
ciascuno dei nodi di cui è ancora una volta un array,

1006
00:44:50,510 --> 00:44:54,650
e si desidera memorizzare Maxwell, è prima
indice e quindi il nodo della radice, in modo

1007
00:44:54,650 --> 00:44:57,810
di parlare, il nodo più in alto,
in posizione M, a destra, in modo da

1008
00:44:57,810 --> 00:44:59,160
approssimativamente in mezzo.

1009
00:44:59,160 --> 00:45:03,740
E poi da lì, si segue un
puntatore ad una nodi figlio, per così dire.

1010
00:45:03,740 --> 00:45:06,150
Quindi, nella struttura di senso di famiglia,
si segue verso il basso.

1011
00:45:06,150 --> 00:45:09,030
E che si portano a un altro nodo
sulla sinistra, che è

1012
00:45:09,030 --> 00:45:10,540
solo un altro array.

1013
00:45:10,540 --> 00:45:14,710
>> E poi se si desidera memorizzare Maxwell,
si trova il puntatore che rappresenta

1014
00:45:14,710 --> 00:45:16,430
A, che è questo qui.

1015
00:45:16,430 --> 00:45:17,840
Poi si passa al nodo successivo.

1016
00:45:17,840 --> 00:45:20,100
E di gara - questo è il motivo della foto
un po 'ingannevole -

1017
00:45:20,100 --> 00:45:21,990
questo nodo look super minuscola.

1018
00:45:21,990 --> 00:45:26,050
Ma a destra di questa è Y e Z.
E 'solo l'autore ha troncato la

1019
00:45:26,050 --> 00:45:27,630
immagine in modo che effettivamente
vedere le cose.

1020
00:45:27,630 --> 00:45:30,400
Altrimenti questa immagine
sarebbe estremamente ampia.

1021
00:45:30,400 --> 00:45:36,180
Così ora si indice nella posizione X, allora
W, allora E, poi L, poi L. Allora qual è

1022
00:45:36,180 --> 00:45:37,380
questa curiosità?

1023
00:45:37,380 --> 00:45:41,250
>> Beh, se stiamo usando questa sorta di nuovo
assumere come memorizzare una stringa in un

1024
00:45:41,250 --> 00:45:44,500
struttura dei dati, è comunque necessario
controllare essenzialmente off nei dati

1025
00:45:44,500 --> 00:45:47,250
struttura che una parola finisce qui.

1026
00:45:47,250 --> 00:45:50,830
In altre parole, ciascuno di questi nodi
ha in qualche modo ricordare che siamo

1027
00:45:50,830 --> 00:45:53,500
effettivamente seguito tutti i puntatori
e stanno lasciando un po '

1028
00:45:53,500 --> 00:45:58,370
pangrattato al fondo di questa qui
Struttura per indicare M-A-X-W-E-L-L è

1029
00:45:58,370 --> 00:46:00,230
infatti in questa struttura dati.

1030
00:46:00,230 --> 00:46:02,040
>> Così potremmo farlo in questo modo.

1031
00:46:02,040 --> 00:46:06,810
Ciascuno dei nodi del quadro che abbiamo appena
sega ha uno, un array di dimensione 27.

1032
00:46:06,810 --> 00:46:10,550
Ed è ora 27, perché in p definito sei,
avremo effettivamente dare un apostrofo,

1033
00:46:10,550 --> 00:46:13,590
così possiamo avere nomi come O'Reilly
e altri con apostrofi.

1034
00:46:13,590 --> 00:46:14,820
Ma la stessa idea.

1035
00:46:14,820 --> 00:46:17,710
Ciascuno di tali elementi nella
punti array ad una struct

1036
00:46:17,710 --> 00:46:19,320
nodo, quindi basta un nodo.

1037
00:46:19,320 --> 00:46:21,430
Quindi questo è molto ricorda
della nostra lista collegata.

1038
00:46:21,430 --> 00:46:24,550
>> E poi ho un booleano, che verrà
chiamare Parola, che è solo andare a essere

1039
00:46:24,550 --> 00:46:29,120
vero se una parola finisce nel
nodo nell'albero.

1040
00:46:29,120 --> 00:46:32,870
Esso rappresenta efficacemente il piccolo
triangolo abbiamo visto un momento fa.

1041
00:46:32,870 --> 00:46:37,190
Quindi se una parola termina in quel nodo nel
albero, quel campo parola sarà vero,

1042
00:46:37,190 --> 00:46:41,990
che sta controllando concettualmente off, o
stiamo disegnando questo triangolo, sì, ci

1043
00:46:41,990 --> 00:46:44,080
è una parola qui.

1044
00:46:44,080 --> 00:46:45,120
>> Quindi questo è un trie.

1045
00:46:45,120 --> 00:46:48,540
E ora la domanda è: che cosa
è il suo tempo di esecuzione?

1046
00:46:48,540 --> 00:46:49,930
E 'grande O di n?

1047
00:46:49,930 --> 00:46:51,410
E 'qualcosa d'altro?

1048
00:46:51,410 --> 00:46:57,330
Beh, se hai n nomi di questi dati
struttura, Maxwell essere solo uno di

1049
00:46:57,330 --> 00:47:02,330
loro, che cosa è il tempo di esecuzione di
l'inserimento o la ricerca di Maxwell?

1050
00:47:02,330 --> 00:47:06,230

1051
00:47:06,230 --> 00:47:09,050
Qual è il tempo di esecuzione
di inserimento di Maxwell?

1052
00:47:09,050 --> 00:47:11,740
Se ci sono n altri nomi
già nella tabella?

1053
00:47:11,740 --> 00:47:12,507
Sì?

1054
00:47:12,507 --> 00:47:15,429
>> STUDENTE: [incomprensibile].

1055
00:47:15,429 --> 00:47:17,550
>> SPEAKER 1: Sì, è la lunghezza
del nome, giusto?

1056
00:47:17,550 --> 00:47:24,420
Quindi M-a-x-w-e-l-l così ci si sente come questo
algoritmo è O grande di sette.

1057
00:47:24,420 --> 00:47:26,580
Ora, naturalmente, il nome
varieranno in lunghezza.

1058
00:47:26,580 --> 00:47:27,380
Forse è un nome breve.

1059
00:47:27,380 --> 00:47:28,600
Forse è un nome più lungo.

1060
00:47:28,600 --> 00:47:33,390
Ma ciò che è fondamentale è che
si tratta di un numero costante.

1061
00:47:33,390 --> 00:47:36,810
E forse non è proprio costante,
Ma Dio, se realisticamente, in un

1062
00:47:36,810 --> 00:47:41,570
dizionario, probabilmente c'è qualche limite
il numero di lettere in un

1063
00:47:41,570 --> 00:47:43,820
il nome della persona in un determinato paese.

1064
00:47:43,820 --> 00:47:46,940
>> E così possiamo supporre che
valore è una costante.

1065
00:47:46,940 --> 00:47:47,750
Io non so cosa sia.

1066
00:47:47,750 --> 00:47:50,440
E 'probabilmente più grande di
pensiamo che sia.

1067
00:47:50,440 --> 00:47:52,720
Perché c'è sempre qualche angolo
caso con un nome folle lungo.

1068
00:47:52,720 --> 00:47:56,360
Quindi chiamiamola k, ma è pur sempre un
costante presumibilmente, perché ogni

1069
00:47:56,360 --> 00:48:00,190
nome nel mondo, almeno in una
particolare paese, è che la lunghezza o

1070
00:48:00,190 --> 00:48:01,780
più breve, quindi è costante.

1071
00:48:01,780 --> 00:48:04,490
Ma quando abbiamo detto qualcosa è grande
O di un valore costante, che cosa è che

1072
00:48:04,490 --> 00:48:07,760
davvero equivalente a?

1073
00:48:07,760 --> 00:48:10,420
Questa è davvero la stessa cosa
come dire tempo costante.

1074
00:48:10,420 --> 00:48:11,530
>> Ora siamo un po 'barare, giusto?

1075
00:48:11,530 --> 00:48:15,340
Siamo un po 'sfruttando qualche teoria
qui per dire che bene, l'ordine di k è

1076
00:48:15,340 --> 00:48:17,450
davvero solo ordinare di uno,
ed è tempo costante.

1077
00:48:17,450 --> 00:48:18,200
Ma è davvero.

1078
00:48:18,200 --> 00:48:22,550
Perché l'intuizione chiave qui è che
se abbiamo n nomi già in questa

1079
00:48:22,550 --> 00:48:26,010
struttura dati, e inseriamo Maxwell,
è la quantità di tempo che ci vuole per

1080
00:48:26,010 --> 00:48:29,530
inserire Maxwell affatto interessata
da quante altre persone

1081
00:48:29,530 --> 00:48:31,100
sono nella struttura dati?

1082
00:48:31,100 --> 00:48:31,670
Non sembra essere.

1083
00:48:31,670 --> 00:48:36,280
Se avessi un miliardo di altri elementi a questa
trie, e quindi inserire Maxwell, è

1084
00:48:36,280 --> 00:48:38,650
ha affatto influenzato?

1085
00:48:38,650 --> 00:48:39,050
No.

1086
00:48:39,050 --> 00:48:42,950
E questo è diverso da tutti i dati al giorno
strutture che abbiamo visto finora, dove

1087
00:48:42,950 --> 00:48:46,820
il tempo di esecuzione del vostro algoritmo è
completamente indipendente quanta

1088
00:48:46,820 --> 00:48:51,430
roba è o non è già
in tale struttura di dati.

1089
00:48:51,430 --> 00:48:54,650
>> E così con questo che consente di godere ora è un
opportunità di p set di sei, che sarà

1090
00:48:54,650 --> 00:48:58,310
ancora una volta coinvolgere di implementare un
correttore ortografico, la lettura a 150.000

1091
00:48:58,310 --> 00:49:01,050
parole, il modo migliore per conservare quella
non è necessariamente evidente.

1092
00:49:01,050 --> 00:49:04,030
E se ho aspirato a trovare
il Santo Graal, non mi

1093
00:49:04,030 --> 00:49:05,330
sostengono che un trie è.

1094
00:49:05,330 --> 00:49:09,810
Infatti, una tabella hash può benissimo
rivelarsi molto più efficiente.

1095
00:49:09,810 --> 00:49:10,830
Ma questi sono solo -

1096
00:49:10,830 --> 00:49:14,620
questa è solo una delle decisioni di progettazione
si dovrà fare.

1097
00:49:14,620 --> 00:49:18,920
>> Ma in chiusura prendiamo 50 o giù di lì
secondi per dare uno sguardo a ciò che sta

1098
00:49:18,920 --> 00:49:22,190
avanti la prossima settimana e al di là di noi transizione
da questa linea di comando

1099
00:49:22,190 --> 00:49:26,220
mondo, se programmi in C per cose web
base e linguaggi come PHP e

1100
00:49:26,220 --> 00:49:30,350
Javascript e la stessa Internet,
protocolli come HTTP, il quale hai

1101
00:49:30,350 --> 00:49:32,870
dato per scontato per anni
ora, e digitato la maggior parte ogni

1102
00:49:32,870 --> 00:49:34,440
giorno, forse, o visto.

1103
00:49:34,440 --> 00:49:37,420
E inizieremo a staccare il
strati di ciò che è internet.

1104
00:49:37,420 --> 00:49:40,650
E qual è il codice che
alla base gli strumenti di oggi.

1105
00:49:40,650 --> 00:49:43,230
Quindi 50 secondi di questo teaser qui.

1106
00:49:43,230 --> 00:49:46,570
Vi do Guerrieri della rete.

1107
00:49:46,570 --> 00:49:51,370
>> [RIPRODUZIONE VIDEO]

1108
00:49:51,370 --> 00:49:56,764
>> -E 'venuto con un messaggio.

1109
00:49:56,764 --> 00:50:00,687
Con un protocollo tutto suo.

1110
00:50:00,687 --> 00:50:13,370

1111
00:50:13,370 --> 00:50:19,780
Egli è venuto per un mondo di crudeli firewall,
router menefreghista, e pericoli lontano

1112
00:50:19,780 --> 00:50:22,600
peggiore della morte.

1113
00:50:22,600 --> 00:50:23,590
E 'veloce.

1114
00:50:23,590 --> 00:50:25,300
Lui è forte.

1115
00:50:25,300 --> 00:50:27,700
Lui è TCPIP.

1116
00:50:27,700 --> 00:50:30,420
E ha il vostro indirizzo.

1117
00:50:30,420 --> 00:50:32,920

1118
00:50:32,920 --> 00:50:34,590
Guerrieri della rete.

1119
00:50:34,590 --> 00:50:35,290
>> [FINE RIPRODUZIONE VIDEO]

1120
00:50:35,290 --> 00:50:38,070
>> SPEAKER 1: Questo è il modo in internet
devono lavorare come della prossima settimana.

1121
00:50:38,070 --> 00:50:40,406