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

2
00:00:00,500 --> 00:00:05,120
[RIPRODUZIONE DI BRANI MUSICALI]

3
00:00:05,120 --> 00:00:12,026

4
00:00:12,026 --> 00:00:12,900
SPEAKER 1: Va bene.

5
00:00:12,900 --> 00:00:14,600
Tutti bentornato alla sezione.

6
00:00:14,600 --> 00:00:18,660
Spero che tutti voi siete con successo
recuperato il quiz

7
00:00:18,660 --> 00:00:19,510
dalla settimana scorsa.

8
00:00:19,510 --> 00:00:22,564
Lo so che è un po 'matti, a volte.

9
00:00:22,564 --> 00:00:25,230
Come dicevo prima, se siete
all'interno della deviazione standard,

10
00:00:25,230 --> 00:00:28,188
in realtà non ti preoccupare, in particolare
per una sezione meno confortevole.

11
00:00:28,188 --> 00:00:30,230
Ecco di dove si dovrebbe essere.

12
00:00:30,230 --> 00:00:32,850
>> Se avete fatto grande, quindi impressionante.

13
00:00:32,850 --> 00:00:33,650
Complimenti a voi.

14
00:00:33,650 --> 00:00:36,149
E se si sente come avete bisogno
un po 'più di aiuto, si prega di

15
00:00:36,149 --> 00:00:38,140
sentitevi liberi di raggiungere
fuori su qualsiasi TF.

16
00:00:38,140 --> 00:00:40,030
Siamo tutti qui per aiutare.

17
00:00:40,030 --> 00:00:40,960
>> È per questo che insegniamo.

18
00:00:40,960 --> 00:00:44,550
È per questo che sono qui ogni Lunedi per voi
ragazzi e presso l'ufficio ore il giovedì.

19
00:00:44,550 --> 00:00:48,130
Quindi, non esitate a farmi sapere
se siete preoccupati di nulla

20
00:00:48,130 --> 00:00:52,450
o se c'è qualcosa sul quiz
che vuoi davvero ad affrontare.

21
00:00:52,450 --> 00:00:56,940
>> Quindi, l'ordine del giorno di oggi è
Tutto su strutture dati.

22
00:00:56,940 --> 00:01:01,520
Alcuni di questi sono solo andando a essere solo
per farti familiarizzare con questi.

23
00:01:01,520 --> 00:01:04,870
L'utente non può mai realizzare
li in questa classe.

24
00:01:04,870 --> 00:01:08,690
Alcuni di loro si vuole,
come per il vostro pset correttore ortografico.

25
00:01:08,690 --> 00:01:11,380
>> Avrete la vostra scelta
tra le tabelle hash e tentativi.

26
00:01:11,380 --> 00:01:13,680
Quindi dovremo sicuramente andando su quelli.

27
00:01:13,680 --> 00:01:18,690
E sarà sicuramente più di tipo
di una sezione di alto livello oggi, però,

28
00:01:18,690 --> 00:01:22,630
perché ci sono un sacco di loro, e se
siamo andati nei dettagli di implementazione

29
00:01:22,630 --> 00:01:26,490
in tutti questi, non sarebbe
anche ottenere attraverso liste collegate

30
00:01:26,490 --> 00:01:28,520
e forse un po 'di tabelle hash.

31
00:01:28,520 --> 00:01:31,200
>> Quindi abbiate pazienza con me.

32
00:01:31,200 --> 00:01:33,530
Non stiamo andando a fare
tanto codifica questa volta.

33
00:01:33,530 --> 00:01:36,870
Se avete domande su di esso
o se si vuole vederlo implementato

34
00:01:36,870 --> 00:01:39,260
o provare di persona,
Lo consiglio vivamente

35
00:01:39,260 --> 00:01:44,250
andare a study.cs50.net, che
ha esempi di tutti questi.

36
00:01:44,250 --> 00:01:46,400
Avrà miei PowerPoint
con le note che abbiamo

37
00:01:46,400 --> 00:01:50,860
tendono ad usare così come alcuni di programmazione
esercizi, soprattutto per le cose

38
00:01:50,860 --> 00:01:55,250
come liste concatenate e binario
alberi pile e spunti.

39
00:01:55,250 --> 00:01:59,590
Così poco livello più alto, che
potrebbe essere bello per voi ragazzi.

40
00:01:59,590 --> 00:02:01,320
>> Quindi, con questo, noi di iniziare.

41
00:02:01,320 --> 00:02:03,060
E anche, quiz yes--.

42
00:02:03,060 --> 00:02:06,550
Penso che la maggior parte di voi che sono in
la mia sezione hanno i tuoi quiz,

43
00:02:06,550 --> 00:02:12,060
ma chiunque viene in o qualche motivo
non lo fanno, sono proprio qui di fronte.

44
00:02:12,060 --> 00:02:12,740
>> Quindi collegate liste.

45
00:02:12,740 --> 00:02:15,650
So che questo tipo di va
per eseguire prima il quiz.

46
00:02:15,650 --> 00:02:17,940
Questa è stata la settimana prima
che abbiamo imparato a conoscere questo.

47
00:02:17,940 --> 00:02:21,040
Ma in questo caso, ci limiteremo a
andare un po 'più in profondità.

48
00:02:21,040 --> 00:02:25,900
>> Quindi perché potremmo scegliere un
linked list su un array?

49
00:02:25,900 --> 00:02:27,130
Che cosa li distingue?

50
00:02:27,130 --> 00:02:27,630
Sì?

51
00:02:27,630 --> 00:02:30,464
>> PUBBLICO: È possibile espandere un collegato
Elenco e dimensione fissa di un array.

52
00:02:30,464 --> 00:02:31,171
SPEAKER 1: Giusto.

53
00:02:31,171 --> 00:02:33,970
Un array ha dimensione fissa, mentre un
lista collegata ha una dimensione variabile.

54
00:02:33,970 --> 00:02:36,970
Quindi, se noi non sappiamo come
tanto che vogliamo memorizzare,

55
00:02:36,970 --> 00:02:39,880
una lista concatenata ci dà una grande
modo per farlo, perché possiamo solo

56
00:02:39,880 --> 00:02:43,730
aggiungere su un altro nodo e aggiungere su
un altro nodo e aggiungere su un altro nodo.

57
00:02:43,730 --> 00:02:45,750
Ma quello che potrebbe essere un trade-off?

58
00:02:45,750 --> 00:02:49,521
Qualcuno ricorda il trade-off
tra array e liste collegate?

59
00:02:49,521 --> 00:02:50,020
Mmhmm?

60
00:02:50,020 --> 00:02:51,460
>> PUBBLICO: Devi
passare attraverso tutto il percorso

61
00:02:51,460 --> 00:02:53,738
attraverso la lista collegata
trovare un elemento in un elenco.

62
00:02:53,738 --> 00:02:55,570
In una matrice, è possibile
basta trovare un elemento.

63
00:02:55,570 --> 00:02:56,278
>> SPEAKER 1: Giusto.

64
00:02:56,278 --> 00:02:57,120
Quindi, con arrays--

65
00:02:57,120 --> 00:02:58,500
>> PUBBLICO: [incomprensibile].

66
00:02:58,500 --> 00:03:01,090
>> SPEAKER 1: Con gli array, abbiamo
quello che chiama ad accesso casuale.

67
00:03:01,090 --> 00:03:04,820
Significa che se vogliamo ciò che è
mai il quinto punto di un elenco

68
00:03:04,820 --> 00:03:07,230
o il quinto punto del nostro
array, si può semplicemente afferrarlo.

69
00:03:07,230 --> 00:03:10,440
Se si tratta di una lista collegata, abbiamo
per scorrere, giusto?

70
00:03:10,440 --> 00:03:14,020
Quindi l'accesso a un elemento in
un array è tempo costante,

71
00:03:14,020 --> 00:03:19,530
mentre con una lista collegata che sarebbe
molto probabilmente il tempo lineare perché forse

72
00:03:19,530 --> 00:03:21,370
nostro elemento è fino alla fine.

73
00:03:21,370 --> 00:03:23,446
Abbiamo per la ricerca in tutto.

74
00:03:23,446 --> 00:03:25,320
Quindi, con tutti questi dati
strutture che andremo

75
00:03:25,320 --> 00:03:29,330
di spendere un po 'di tempo su,
quali sono i vantaggi e negativi.

76
00:03:29,330 --> 00:03:31,480
Quando si potrebbe desiderare di
utilizzare uno sopra l'altro?

77
00:03:31,480 --> 00:03:34,970
E questo è il tipo di
cosa più grande da portare via.

78
00:03:34,970 --> 00:03:40,140
>> Quindi, abbiamo qui la
definizione di un nodo.

79
00:03:40,140 --> 00:03:43,040
È come un elemento
la nostra lista collegata, giusto?

80
00:03:43,040 --> 00:03:46,180
Quindi siamo tutti a conoscenza
con i nostri struct typedef,

81
00:03:46,180 --> 00:03:47,980
che siamo andati oltre in rassegna l'ultima volta.

82
00:03:47,980 --> 00:03:53,180
E 'stato fondamentalmente solo la creazione di
altro tipo di dati che potremmo usare.

83
00:03:53,180 --> 00:03:57,930
>> E in questo caso, è qualche nodo
che si terrà in qualche intero.

84
00:03:57,930 --> 00:04:00,210
E allora qual è la seconda parte qui?

85
00:04:00,210 --> 00:04:03,192

86
00:04:03,192 --> 00:04:05,677
Chiunque?

87
00:04:05,677 --> 00:04:06,680
>> PUBBLICO: [incomprensibile].

88
00:04:06,680 --> 00:04:07,020
>> SPEAKER 1: Sì.

89
00:04:07,020 --> 00:04:08,400
E 'un puntatore al nodo successivo.

90
00:04:08,400 --> 00:04:12,610
Quindi questo dovrebbe in realtà essere qui.

91
00:04:12,610 --> 00:04:18,790
Questo è un puntatore di tipo
nodo per la prossima cosa.

92
00:04:18,790 --> 00:04:22,410
E questo è quello che
comprende il nostro nodo.

93
00:04:22,410 --> 00:04:24,060
Freddo.

94
00:04:24,060 --> 00:04:29,390
>> Va bene, quindi con la ricerca, come eravamo
solo dicendo prima mano, se siete

95
00:04:29,390 --> 00:04:31,840
andando per la ricerca in,
si deve in realtà iterare

96
00:04:31,840 --> 00:04:33,660
attraverso la vostra lista collegata.

97
00:04:33,660 --> 00:04:38,530
Quindi, se stiamo cercando il numero
9, vorremmo iniziare alla nostra testa

98
00:04:38,530 --> 00:04:41,520
e che ci punti all'inizio
della nostra lista collegata, giusto?

99
00:04:41,520 --> 00:04:44,600
E noi diciamo, OK, lo fa
nodo contiene il numero 9?

100
00:04:44,600 --> 00:04:45,690
No?

101
00:04:45,690 --> 00:04:47,500
>> Va bene, andare a quella successiva.

102
00:04:47,500 --> 00:04:48,312
Seguirla.

103
00:04:48,312 --> 00:04:49,520
Contiene il numero 9?

104
00:04:49,520 --> 00:04:50,570
No.

105
00:04:50,570 --> 00:04:51,550
Seguire il prossimo.

106
00:04:51,550 --> 00:04:55,490
>> Quindi dobbiamo realmente iterare
attraverso la lista collegata.

107
00:04:55,490 --> 00:05:00,070
Non possiamo andare direttamente al punto in cui 9 è.

108
00:05:00,070 --> 00:05:05,860
E se voi ragazzi vuole realmente
vedere alcuni pseudo-codice lassù.

109
00:05:05,860 --> 00:05:10,420
Abbiamo qualche funzione di ricerca qui
che prende dentro-- cosa ci vuole a?

110
00:05:10,420 --> 00:05:13,110

111
00:05:13,110 --> 00:05:14,320
Cosa ne pensi?

112
00:05:14,320 --> 00:05:15,960
Così facile.

113
00:05:15,960 --> 00:05:17,784
Cos'è questo?

114
00:05:17,784 --> 00:05:18,700
PUBBLICO: [incomprensibile].

115
00:05:18,700 --> 00:05:20,366
SPEAKER 1: Il numero che stiamo cercando.

116
00:05:20,366 --> 00:05:20,980
Giusto?

117
00:05:20,980 --> 00:05:22,875
E quale sarebbe questo corrispondere a?

118
00:05:22,875 --> 00:05:25,020
E 'un puntatore a?

119
00:05:25,020 --> 00:05:26,000
>> PUBBLICO: Un nodo.

120
00:05:26,000 --> 00:05:28,980
>> SPEAKER 1: Un nodo alla lista
che stiamo guardando, giusto?

121
00:05:28,980 --> 00:05:33,700
Così abbiamo alcuni nodi sono puntatore qui.

122
00:05:33,700 --> 00:05:37,240
Questo è un punto che sta per
in realtà scorrere la nostra lista.

123
00:05:37,240 --> 00:05:39,630
Abbiamo impostato uguale a elencare
perché questo è solo

124
00:05:39,630 --> 00:05:44,380
porla uguale
inizio della nostra lista collegata.

125
00:05:44,380 --> 00:05:50,660
>> E mentre non è NULL, mentre
abbiamo ancora cose nella nostra lista,

126
00:05:50,660 --> 00:05:55,580
controllare per vedere se quel nodo ha
il numero che stiamo cercando.

127
00:05:55,580 --> 00:05:57,740
Restituisce vero.

128
00:05:57,740 --> 00:06:01,070
In caso contrario, l'aggiornamento, giusto?

129
00:06:01,070 --> 00:06:04,870
>> Se è NULL, usciamo il nostro
ciclo while e restituire false

130
00:06:04,870 --> 00:06:08,340
perché significa che non abbiamo trovato.

131
00:06:08,340 --> 00:06:11,048
Ricevono tutti come funziona?

132
00:06:11,048 --> 00:06:11,548
Ok.

133
00:06:11,548 --> 00:06:14,940

134
00:06:14,940 --> 00:06:20,260
>> Quindi, con l'inserimento, è
hanno tre modi diversi.

135
00:06:20,260 --> 00:06:25,250
È possibile anteporre, è possibile aggiungere
ed è possibile inserire in colori assortiti.

136
00:06:25,250 --> 00:06:28,215
In questo caso, siamo
intenzione di fare un anteporre.

137
00:06:28,215 --> 00:06:33,380
Qualcuno sa come quelli
tre casi potrebbero differire?

138
00:06:33,380 --> 00:06:36,920
>> Così anteporre significa che si mette
nella parte anteriore della vostra lista.

139
00:06:36,920 --> 00:06:39,770
Quindi, ciò significherebbe che non importa
ciò che il nodo è, non importa

140
00:06:39,770 --> 00:06:43,160
che cosa è il valore, si sta andando
per dirla proprio qui di fronte, OK?

141
00:06:43,160 --> 00:06:45,160
Sta andando essere il primo
elemento nella lista.

142
00:06:45,160 --> 00:06:49,510
>> Se si aggiunge che, sta andando
per andare sul retro della vostra lista.

143
00:06:49,510 --> 00:06:54,010
E inserire assortiti significa che siete
andando a mettere realmente nel luogo

144
00:06:54,010 --> 00:06:57,700
dove si mantiene la vostra lista concatenata ordinata.

145
00:06:57,700 --> 00:07:00,810
Anche in questo caso, come si usa
chi e quando si utilizza

146
00:07:00,810 --> 00:07:02,530
essi variano a seconda del caso.

147
00:07:02,530 --> 00:07:05,834

148
00:07:05,834 --> 00:07:07,750
Se non deve
da ordinare, anteporre tende

149
00:07:07,750 --> 00:07:10,460
di essere ciò che la maggior parte delle persone
utilizzare perché non lo fai

150
00:07:10,460 --> 00:07:15,680
devono passare attraverso l'intera lista
per trovare la fine di aggiungere su, giusto?

151
00:07:15,680 --> 00:07:17,720
Si può solo attaccare proprio nel.

152
00:07:17,720 --> 00:07:21,930
>> Quindi dovremo passare attraverso un
inserzione di 1 ora.

153
00:07:21,930 --> 00:07:26,360
Quindi, una cosa che ho intenzione di
Consiglio vivamente questo pset

154
00:07:26,360 --> 00:07:29,820
è quello di disegnare le cose, come sempre.

155
00:07:29,820 --> 00:07:35,130
E 'molto importante che si aggiorna
i puntatori nell'ordine corretto

156
00:07:35,130 --> 00:07:38,620
perché se si aggiorna li
leggermente fuori ordine,

157
00:07:38,620 --> 00:07:42,210
si sta andando a finire
perdere parti del proprio elenco.

158
00:07:42,210 --> 00:07:49,680
>> Così, per esempio, in questo caso, siamo
raccontando la testa di solo punto a 1.

159
00:07:49,680 --> 00:07:56,070
Se abbiamo appena facciamo
senza salvare 1,

160
00:07:56,070 --> 00:07:58,570
non abbiamo idea di cosa
1 deve puntare ora

161
00:07:58,570 --> 00:08:02,490
perché abbiamo perso quello che
la testa indicò.

162
00:08:02,490 --> 00:08:05,530
Quindi, una cosa da ricordare
quando stai facendo un anteporre

163
00:08:05,530 --> 00:08:09,630
è quello di salvare ciò che il
punti a testa per primo,

164
00:08:09,630 --> 00:08:15,210
poi riassegnare, e quindi aggiornare
che cosa il vostro nuovo nodo deve puntare.

165
00:08:15,210 --> 00:08:20,870

166
00:08:20,870 --> 00:08:22,560
In questo caso, questo è un modo per farlo.

167
00:08:22,560 --> 00:08:25,440
>> Quindi, se avessimo fatto in questo modo
dove abbiamo appena riassegnato testa,

168
00:08:25,440 --> 00:08:30,320
perdiamo in fondo il nostro
tutto l'elenco, giusto?

169
00:08:30,320 --> 00:08:38,000
Un modo per farlo è quello di avere 1 punto di
prossimo, e poi punto a capo 1.

170
00:08:38,000 --> 00:08:42,650
Oppure si può fare un po 'come il
deposito temporaneo, di cui ho parlato.

171
00:08:42,650 --> 00:08:45,670
>> Ma riassegnando il tuo
puntatori nell'ordine corretto

172
00:08:45,670 --> 00:08:48,750
sta per essere molto, molto
importante per questo pset.

173
00:08:48,750 --> 00:08:53,140
In caso contrario, si sta andando ad avere un hash
tavolo o una prova che è solo andare a essere

174
00:08:53,140 --> 00:08:56,014
solo una parte delle parole che
vuole e poi you're-- mmhmm?

175
00:08:56,014 --> 00:08:58,930
PUBBLICO: Qual è stata la temporanea
cosa di stoccaggio di cui parlavi?

176
00:08:58,930 --> 00:09:00,305
SPEAKER 1: Il deposito temporaneo.

177
00:09:00,305 --> 00:09:02,760
Quindi, in pratica un'altra
modo si potrebbe fare questo

178
00:09:02,760 --> 00:09:07,650
è conservare la testa di qualcosa, come
memorizzare la variabile temporanea.

179
00:09:07,650 --> 00:09:11,250
Assegnarlo a 1 e
quindi aggiornare 1 al punto

180
00:09:11,250 --> 00:09:13,830
a qualunque testa usato per puntare a.

181
00:09:13,830 --> 00:09:16,920
In questo modo è ovviamente
più elegante perché si

182
00:09:16,920 --> 00:09:20,770
non hanno bisogno di un valore temporaneo, ma
solo offrendo un altro modo per farlo.

183
00:09:20,770 --> 00:09:23,999

184
00:09:23,999 --> 00:09:25,790
E in realtà hanno
del codice per questo.

185
00:09:25,790 --> 00:09:28,080
Così per la lista collegata, abbiamo
in realtà avere un po 'di codice.

186
00:09:28,080 --> 00:09:31,930
Quindi inserire qui, questo è preponendo.

187
00:09:31,930 --> 00:09:34,290
Quindi questo vi entra in testa.

188
00:09:34,290 --> 00:09:38,820
>> Quindi, prima cosa, è necessario
creare il nuovo nodo, naturalmente,

189
00:09:38,820 --> 00:09:40,790
e verificare la presenza di NULL.

190
00:09:40,790 --> 00:09:43,250
Sempre buono.

191
00:09:43,250 --> 00:09:47,840
E poi è necessario assegnare i valori.

192
00:09:47,840 --> 00:09:51,260
Ogni volta che si crea un nuovo nodo, è
non so cosa sta indicando il prossimo,

193
00:09:51,260 --> 00:09:54,560
così si desidera inizializzare a NULL.

194
00:09:54,560 --> 00:09:58,760
Se non finisce che punta a qualcosa
altro, viene riassegnato e va bene.

195
00:09:58,760 --> 00:10:00,740
Se è la prima cosa
nella lista, di cui ha bisogno

196
00:10:00,740 --> 00:10:04,270
per puntare a NULL perché
questa è la fine della lista.

197
00:10:04,270 --> 00:10:12,410
>> Allora per inserirlo, vediamo qui
stanno assegnando il valore successivo del nostro nodo

198
00:10:12,410 --> 00:10:17,380
di essere ciò che è testa,
che è quello che abbiamo avuto qui.

199
00:10:17,380 --> 00:10:19,930
Questo è quello che abbiamo appena fatto.

200
00:10:19,930 --> 00:10:25,820
E poi stiamo assegnando testa al punto
al nostro nuovo nodo, perché ricordate,

201
00:10:25,820 --> 00:10:31,090
nuovo qualche puntatore a un nodo,
e questo è esattamente ciò che la testa è.

202
00:10:31,090 --> 00:10:34,370
Questo è esattamente il motivo per cui
avere questa freccia di accesso.

203
00:10:34,370 --> 00:10:37,030

204
00:10:37,030 --> 00:10:37,530
Cool?

205
00:10:37,530 --> 00:10:38,130
Mmhmm?

206
00:10:38,130 --> 00:10:41,100
>> PUBBLICO: Dobbiamo
inizializzare nuovo accanto a NULL prima,

207
00:10:41,100 --> 00:10:44,240
o possiamo semplicemente inizializzarlo a testa?

208
00:10:44,240 --> 00:10:48,210
>> SPEAKER 1: Nuovo accanto
deve essere NULL per iniziare

209
00:10:48,210 --> 00:10:53,760
perché non si sa
dove sta andando essere.

210
00:10:53,760 --> 00:10:56,100
Inoltre, questo è una specie di
proprio come un paradigma.

211
00:10:56,100 --> 00:10:59,900
Si imposta uguale a NULL solo per fare
Assicurarsi che tutte le basi sono coperti

212
00:10:59,900 --> 00:11:04,070
prima di fare qualsiasi riassegnazione in modo che
sei sempre la garanzia che lo farà

213
00:11:04,070 --> 00:11:08,880
essere che punta a un valore specifico
contro come un valore spazzatura.

214
00:11:08,880 --> 00:11:12,210
Perché, sì, assegniamo
nuova successivo automaticamente,

215
00:11:12,210 --> 00:11:15,420
ma è più proprio come un
buone pratiche per inizializzarlo

216
00:11:15,420 --> 00:11:19,270
in questo modo e poi riassegnare.

217
00:11:19,270 --> 00:11:23,420
>> OK, quindi doppiamente legata liste ora.

218
00:11:23,420 --> 00:11:24,601
Che cosa pensiamo?

219
00:11:24,601 --> 00:11:26,350
Cosa c'è di diverso con
doppiamente legato liste?

220
00:11:26,350 --> 00:11:30,750

221
00:11:30,750 --> 00:11:34,300
>> Quindi, nelle nostre liste collegate, possiamo
muoversi solo in una direzione, giusto?

222
00:11:34,300 --> 00:11:35,270
Abbiamo solo il prossimo.

223
00:11:35,270 --> 00:11:36,760
Possiamo solo andare avanti.

224
00:11:36,760 --> 00:11:40,300
>> Con una lista doppiamente concatenata,
possiamo anche tornare indietro.

225
00:11:40,300 --> 00:11:44,810
Così abbiamo non solo la
numero che si vuole memorizzare,

226
00:11:44,810 --> 00:11:50,110
abbiamo dove a cui punta il prossimo
e dove siamo appena tornati da.

227
00:11:50,110 --> 00:11:52,865
Quindi questo permette
alcuni meglio di attraversamento.

228
00:11:52,865 --> 00:11:56,620

229
00:11:56,620 --> 00:12:01,240
>> Nodi in modo doppiamente collegate,
molto simile, giusto?

230
00:12:01,240 --> 00:12:05,000
L'unica differenza è che ora
un successivo e precedente.

231
00:12:05,000 --> 00:12:06,235
E 'l'unica differenza.

232
00:12:06,235 --> 00:12:09,570

233
00:12:09,570 --> 00:12:14,790
>> Quindi, se dovessimo anteporre o append-- noi
non hanno alcun codice per questo in su qui--

234
00:12:14,790 --> 00:12:17,830
ma se si dovesse cercare di
inserirla, la cosa importante

235
00:12:17,830 --> 00:12:19,980
è quello che dovete fare
che si sta assegnando

236
00:12:19,980 --> 00:12:23,360
sia il precedente e il vostro
prossimo puntatore correttamente.

237
00:12:23,360 --> 00:12:29,010
Quindi, in questo caso, si farebbe
non solo inizializzare il prossimo,

238
00:12:29,010 --> 00:12:31,820
si inizializza precedente.

239
00:12:31,820 --> 00:12:36,960
Se siamo in testa alla lista, ci
potrebbe non solo rendere testa pari nuovo,

240
00:12:36,960 --> 00:12:41,750
ma il nostro nuovo precedente dovrebbe
puntare alla testa, giusto?

241
00:12:41,750 --> 00:12:43,380
>> Questa è l'unica differenza.

242
00:12:43,380 --> 00:12:47,200
E se volete più pratica con
questi con liste concatenate, con l'inserimento,

243
00:12:47,200 --> 00:12:49,900
con l'eliminazione, con inserto
in una lista di assortiti,

244
00:12:49,900 --> 00:12:52,670
si prega di consultare study.cs50.net.

245
00:12:52,670 --> 00:12:54,870
C'è un mucchio di grandi esercizi.

246
00:12:54,870 --> 00:12:55,870
Io li consiglio vivamente.

247
00:12:55,870 --> 00:12:59,210
Mi sarebbe piaciuto avere il tempo di passare attraverso di loro
ma ci sono un sacco di strutture di dati

248
00:12:59,210 --> 00:13:01,530
per ottenere attraverso.

249
00:13:01,530 --> 00:13:02,650
>> OK, quindi tabelle hash.

250
00:13:02,650 --> 00:13:07,070
Questo è probabilmente il più
bit utili per il vostro pset

251
00:13:07,070 --> 00:13:11,090
qui perché si sta andando ad essere
attuare una di queste, o una prova.

252
00:13:11,090 --> 00:13:12,200
Mi piace molto tabelle hash.

253
00:13:12,200 --> 00:13:13,110
Sono piuttosto fresco.

254
00:13:13,110 --> 00:13:17,080
>> Quindi, in pratica ciò che
accade è una tabella hash

255
00:13:17,080 --> 00:13:22,050
è quando abbiamo veramente bisogno veloce
inserimento, cancellazione e ricerca.

256
00:13:22,050 --> 00:13:25,010
Queste sono le cose che siamo
priorità in una tabella hash.

257
00:13:25,010 --> 00:13:29,500
Possono ottenere abbastanza grande,
ma come vedremo con tentativi,

258
00:13:29,500 --> 00:13:33,040
ci sono cose che sono molto più grandi.

259
00:13:33,040 --> 00:13:38,330
>> Ma in fondo, tutto un hash
tabella è una funzione hash

260
00:13:38,330 --> 00:13:47,215
che ti dice che secchio per mettere ogni
dei dati, ciascuno dei vostri elementi.

261
00:13:47,215 --> 00:13:51,140
Un modo semplice di pensare a una tabella hash
è che è solo secchi di cose,

262
00:13:51,140 --> 00:13:51,770
giusto?

263
00:13:51,770 --> 00:13:59,720
Così, quando si ordina le cose da
come la prima lettera del loro nome,

264
00:13:59,720 --> 00:14:01,820
questo è un po 'come una tabella hash.

265
00:14:01,820 --> 00:14:06,180
>> Quindi, se dovessi gruppo di ragazzi è
in gruppi di chiunque di nome inizia

266
00:14:06,180 --> 00:14:11,670
con A qui, o chi per il compleanno
è nel mese di gennaio, febbraio, marzo,

267
00:14:11,670 --> 00:14:15,220
qualunque, cioè efficace
la creazione di una tabella hash.

268
00:14:15,220 --> 00:14:18,120
E 'solo la creazione di secchi che
si ordinano gli elementi in

269
00:14:18,120 --> 00:14:19,520
in modo che si può trovare più facilmente.

270
00:14:19,520 --> 00:14:22,300
Così, in questo modo, quando ho bisogno
per trovare uno di voi,

271
00:14:22,300 --> 00:14:24,680
Non ho per la ricerca
attraverso ciascuno dei vostri nomi.

272
00:14:24,680 --> 00:14:29,490
Posso essere come, oh, so che
Compleanno di Danielle è dentro--

273
00:14:29,490 --> 00:14:30,240
PUBBLICO: --April.

274
00:14:30,240 --> 00:14:30,948
SPEAKER 1: aprile.

275
00:14:30,948 --> 00:14:33,120
Quindi io guardo nel mio aprile
secchio, e con po 'di fortuna,

276
00:14:33,120 --> 00:14:38,270
lei sarà l'unica in là e
il mio tempo è stato costante in questo senso,

277
00:14:38,270 --> 00:14:41,230
mentre se devo guardare
attraverso un intero gruppo di persone,

278
00:14:41,230 --> 00:14:43,090
sta andando a prendere molto più tempo.

279
00:14:43,090 --> 00:14:45,830
Quindi, tabelle hash sono in realtà solo secchi.

280
00:14:45,830 --> 00:14:48,630
Un modo semplice di pensare a loro.

281
00:14:48,630 --> 00:14:52,930
>> Quindi, una cosa molto importante su
una tabella di hash è una funzione di hash.

282
00:14:52,930 --> 00:14:58,140
Quindi le cose che ho appena parlato, come
la tua prima lettera del nome

283
00:14:58,140 --> 00:15:01,450
o il tuo mese di compleanno,
queste sono idee che

284
00:15:01,450 --> 00:15:03,070
davvero correlare ad una funzione di hash.

285
00:15:03,070 --> 00:15:08,900
E 'solo un modo di decidere quale
tu sei secchio elemento va in, OK?

286
00:15:08,900 --> 00:15:14,850
Quindi, per questo pset, è possibile cercare
praticamente qualsiasi funzione di hash che si desidera.

287
00:15:14,850 --> 00:15:16,030
>> Non deve essere il vostro.

288
00:15:16,030 --> 00:15:21,140
Ci sono alcuni tra quelli davvero cool fuori
lì che fare ogni sorta di matematica pazzo.

289
00:15:21,140 --> 00:15:25,170
E se si desidera rendere il vostro
correttore ortografico super veloce,

290
00:15:25,170 --> 00:15:27,620
Mi sarebbe sicuramente
guardare in uno di quelli.

291
00:15:27,620 --> 00:15:32,390
>> Ma ci sono anche il
quelli semplici, come il calcolo

292
00:15:32,390 --> 00:15:39,010
la somma delle parole, come
ogni lettera ha un numero.

293
00:15:39,010 --> 00:15:39,940
Calcolare la somma.

294
00:15:39,940 --> 00:15:42,230
Che determina il secchio.

295
00:15:42,230 --> 00:15:45,430
Essi hanno anche i più facili che
sono proprio come tutti gli A è qui,

296
00:15:45,430 --> 00:15:47,050
tutta la B è qui.

297
00:15:47,050 --> 00:15:48,920
Ogni uno di quelli.

298
00:15:48,920 --> 00:15:55,770
>> In sostanza, si dice solo che
indice dell'array vostro elemento dovrebbe andare in.

299
00:15:55,770 --> 00:15:58,690
Basta decidere il bucket--
è tutto una funzione di hash è.

300
00:15:58,690 --> 00:16:04,180
Quindi qui abbiamo un esempio che è
solo la prima lettera della stringa

301
00:16:04,180 --> 00:16:05,900
che stavo solo parlando.

302
00:16:05,900 --> 00:16:11,900
>> In modo da avere un po 'di hash che è solo il
prima lettera della stringa meno A,

303
00:16:11,900 --> 00:16:16,090
che vi darà un po '
numero compreso tra 0 e 25.

304
00:16:16,090 --> 00:16:20,790
E ciò che si vuole fare è
fare in modo che questo rappresenta

305
00:16:20,790 --> 00:16:24,110
la dimensione del hash table--
quanti secchi ci sono.

306
00:16:24,110 --> 00:16:25,860
Con molti di questi
funzioni di hash, sono

307
00:16:25,860 --> 00:16:31,630
sta per essere i valori di ritorno che potrebbe
essere di gran lunga superiore al numero di bucket

308
00:16:31,630 --> 00:16:33,610
che in realtà hanno
nella tabella hash,

309
00:16:33,610 --> 00:16:37,240
quindi è necessario fare
sicuro e mod da chi.

310
00:16:37,240 --> 00:16:42,190
In caso contrario, si sta per dire,
oh, che dovrebbe essere in secchio 5.000

311
00:16:42,190 --> 00:16:46,040
ma hai solo 30
secchi nella vostra tabella hash.

312
00:16:46,040 --> 00:16:49,360
E, naturalmente, sappiamo tutti che è
andando a causare alcuni errori pazzeschi.

313
00:16:49,360 --> 00:16:52,870
Quindi assicuratevi di mod dal
dimensione della tabella hash.

314
00:16:52,870 --> 00:16:58,430

315
00:16:58,430 --> 00:16:58,930
Freddo.

316
00:16:58,930 --> 00:17:00,506
Così le collisioni.

317
00:17:00,506 --> 00:17:02,620
Sono tutti bene finora?

318
00:17:02,620 --> 00:17:03,120
Mmhmm?

319
00:17:03,120 --> 00:17:05,900
>> PUBBLICO: perché è vero
restituire un valore così massiccio?

320
00:17:05,900 --> 00:17:09,210
>> SPEAKER 1: A seconda dell'algoritmo
che la vostra funzione di hash utilizza.

321
00:17:09,210 --> 00:17:12,270
Alcuni di loro faranno
moltiplicazione pazzo.

322
00:17:12,270 --> 00:17:16,270
Ed è tutto su come ottenere
una distribuzione uniforme,

323
00:17:16,270 --> 00:17:18,490
in modo da fare un po 'davvero
cose folli a volte.

324
00:17:18,490 --> 00:17:20,960
Questo è tutto.

325
00:17:20,960 --> 00:17:22,140
Qualunque altra cosa?

326
00:17:22,140 --> 00:17:22,829
Ok.

327
00:17:22,829 --> 00:17:24,480
>> Così le collisioni.

328
00:17:24,480 --> 00:17:29,270
In sostanza, come ho detto prima,
nel migliore dei casi,

329
00:17:29,270 --> 00:17:32,040
qualsiasi secchio guardo è
andando ad avere una cosa,

330
00:17:32,040 --> 00:17:34,160
quindi non devo guardare a tutti, giusto?

331
00:17:34,160 --> 00:17:37,040
Mi sia so che è lì o è
non, e questo è ciò che vogliamo davvero.

332
00:17:37,040 --> 00:17:43,960
Ma se abbiamo decine di migliaia di
punti dati e meno di quel numero

333
00:17:43,960 --> 00:17:48,700
di benne, stiamo andando ad avere
collisioni in cui alla fine qualcosa

334
00:17:48,700 --> 00:17:54,210
sta andando ad avere per finire in un
benna che ha già un elemento.

335
00:17:54,210 --> 00:17:57,390
>> Quindi la domanda è, cosa
facciamo in questo caso?

336
00:17:57,390 --> 00:17:58,480
Che cosa facciamo?

337
00:17:58,480 --> 00:17:59,300
Abbiamo già qualcosa lì?

338
00:17:59,300 --> 00:18:00,060
Dobbiamo solo buttare fuori?

339
00:18:00,060 --> 00:18:00,700
>> No.

340
00:18:00,700 --> 00:18:01,980
Dobbiamo continuare a ciascuno di essi.

341
00:18:01,980 --> 00:18:06,400
Quindi il modo in cui
tipicamente farlo è quello?

342
00:18:06,400 --> 00:18:08,400
Qual è la struttura dei dati
abbiamo appena parlato?

343
00:18:08,400 --> 00:18:09,316
PUBBLICO: lista collegata.

344
00:18:09,316 --> 00:18:10,500
SPEAKER 1: Una lista concatenata.

345
00:18:10,500 --> 00:18:16,640
Così ora, invece di ciascuno di questi
benne solo che hanno un elemento,

346
00:18:16,640 --> 00:18:24,020
sta andando a contenere una lista concatenata di
gli elementi che sono stati hash in esso.

347
00:18:24,020 --> 00:18:27,588
OK, non tutti i tipi di ottenere che idea?

348
00:18:27,588 --> 00:18:30,546
Perché non abbiamo potuto avere una matrice
perché non sappiamo quante cose

349
00:18:30,546 --> 00:18:31,730
stanno per essere lì.

350
00:18:31,730 --> 00:18:36,540
Una lista concatenata ci consente di
avere solo il numero esatto

351
00:18:36,540 --> 00:18:38,465
sono hash in quel secchio, giusto?

352
00:18:38,465 --> 00:18:42,260

353
00:18:42,260 --> 00:18:50,500
>> Così scansione lineare è
fondamentalmente questo idea--

354
00:18:50,500 --> 00:18:52,300
è un modo per affrontare una collisione.

355
00:18:52,300 --> 00:18:58,010
Che cosa si può fare è se, in questo
caso, frutti di bosco è stato eseguito l'hashing in 1

356
00:18:58,010 --> 00:19:01,130
e abbiamo già
qualcosa lì, basta

357
00:19:01,130 --> 00:19:04,840
andare avanti fino a quando
a trovare uno slot vuoto.

358
00:19:04,840 --> 00:19:06,370
Questo è un modo per gestire la cosa.

359
00:19:06,370 --> 00:19:09,020
L'altro modo di gestire
è con quello che abbiamo appena

360
00:19:09,020 --> 00:19:12,280
called-- il collegato
lista si chiama concatenamento.

361
00:19:12,280 --> 00:19:20,510
>> Quindi questa idea funziona se
la tabella hash si pensa

362
00:19:20,510 --> 00:19:24,150
è molto più grande
i tuoi dati impostati o se si

363
00:19:24,150 --> 00:19:28,870
vuole cercare di ridurre al minimo il concatenamento
fino a quando è assolutamente necessario.

364
00:19:28,870 --> 00:19:34,050
Quindi una cosa è lineare
sondare significa, ovviamente,

365
00:19:34,050 --> 00:19:37,290
che la funzione di hash
non è altrettanto utile

366
00:19:37,290 --> 00:19:42,200
perché si sta andando a finire con
la funzione di hash, di arrivare a un punto,

367
00:19:42,200 --> 00:19:46,400
si lineare sondare fino a
un posto che è disponibile.

368
00:19:46,400 --> 00:19:49,670
Ma ora, naturalmente, qualsiasi cosa
altra cosa che finisce lì,

369
00:19:49,670 --> 00:19:52,050
si sta andando ad avere per
cercare ancora più in basso.

370
00:19:52,050 --> 00:19:55,650
>> E c'è molto di più
Ricerca spesa che

371
00:19:55,650 --> 00:19:59,820
va in immissione di un elemento
nella tabella hash ora, giusto?

372
00:19:59,820 --> 00:20:05,640
E ora quando si va e cercare di trovare
bacche di nuovo, si sta andando ad hash esso,

373
00:20:05,640 --> 00:20:07,742
e sta andando a dire,
Oh, guarda nel secchio 1,

374
00:20:07,742 --> 00:20:09,700
e non sarà
nel secchio 1, quindi sei

375
00:20:09,700 --> 00:20:11,970
andando ad avere per attraversare
per il resto di questi.

376
00:20:11,970 --> 00:20:17,720
Quindi è a volte utile,
ma nella maggior parte dei casi,

377
00:20:17,720 --> 00:20:22,660
stiamo andando a dire che
concatenamento è ciò che si vuole fare.

378
00:20:22,660 --> 00:20:25,520
>> Così abbiamo parlato di questo in precedenza.

379
00:20:25,520 --> 00:20:27,812
Ho avuto un po 'più avanti di me stesso.

380
00:20:27,812 --> 00:20:33,560
Ma concatenamento è, fondamentalmente, che
ciascun segmento della tabella hash

381
00:20:33,560 --> 00:20:36,120
è solo una lista collegata.

382
00:20:36,120 --> 00:20:39,660
>> Quindi un altro modo, o più tecnico
modo, di pensare a una tabella hash

383
00:20:39,660 --> 00:20:44,490
è che è solo un array
di liste collegate, che

384
00:20:44,490 --> 00:20:49,330
quando si sta scrivendo il dizionario
e si sta cercando di caricarlo,

385
00:20:49,330 --> 00:20:52,070
pensare come un
array di liste concatenate

386
00:20:52,070 --> 00:20:54,390
renderà molto più facile
per di inizializzare.

387
00:20:54,390 --> 00:20:57,680
>> PUBBLICO: Così tabella hash
ha una dimensione predeterminata,

388
00:20:57,680 --> 00:20:58,980
come un [incomprensibile] di secchi?

389
00:20:58,980 --> 00:20:59,220
>> SPEAKER 1: Giusto.

390
00:20:59,220 --> 00:21:01,655
Così ha un determinato numero di
secchi che si determine--

391
00:21:01,655 --> 00:21:03,530
che voi ragazzi dovrebbero
sentitevi liberi di giocare.

392
00:21:03,530 --> 00:21:05,269
Può essere piuttosto fresco
per vedere cosa succede

393
00:21:05,269 --> 00:21:06,810
come si cambia il numero di segmenti.

394
00:21:06,810 --> 00:21:09,410

395
00:21:09,410 --> 00:21:11,510
Ma sì, ha un
numero impostato di secchi.

396
00:21:11,510 --> 00:21:15,360
Ciò che permette di montare come
molti elementi di cui hai bisogno

397
00:21:15,360 --> 00:21:19,350
è questo concatenazioni separate dove
hanno collegato le liste in ciascun segmento.

398
00:21:19,350 --> 00:21:22,850
Ciò significa che la tua tabella di hash
sarà esattamente la dimensione

399
00:21:22,850 --> 00:21:25,440
che è necessario che sia, giusto?

400
00:21:25,440 --> 00:21:27,358
Questo è il punto centrale di liste collegate.

401
00:21:27,358 --> 00:21:30,850

402
00:21:30,850 --> 00:21:32,480
Freddo.

403
00:21:32,480 --> 00:21:38,780
>> Così tutti OK lì?

404
00:21:38,780 --> 00:21:39,801
Bene.

405
00:21:39,801 --> 00:21:40,300
Ah.

406
00:21:40,300 --> 00:21:41,860
Che cosa è successo?

407
00:21:41,860 --> 00:21:42,960
Veramente ora.

408
00:21:42,960 --> 00:21:45,250
Immagino che qualcuno mi sta uccidendo.

409
00:21:45,250 --> 00:21:52,060
>> OK stiamo per andare in
paesi, che sono un po 'pazzo.

410
00:21:52,060 --> 00:21:53,140
Mi piace tabelle hash.

411
00:21:53,140 --> 00:21:54,460
Penso che siano davvero cool.

412
00:21:54,460 --> 00:21:56,710
Mete sono fresche, troppo.

413
00:21:56,710 --> 00:21:59,590
>> Così qualcuno si ricorda che cosa è una prova?

414
00:21:59,590 --> 00:22:01,740
Si dovrebbe avere superato
brevemente in conferenza?

415
00:22:01,740 --> 00:22:04,570

416
00:22:04,570 --> 00:22:06,377
Ti ricordi una specie di come funziona?

417
00:22:06,377 --> 00:22:08,460
PUBBLICO: Sto solo facendo un cenno
che siamo andati su di esso.

418
00:22:08,460 --> 00:22:09,626
SPEAKER 1: Noi andiamo su di esso.

419
00:22:09,626 --> 00:22:13,100
OK, siamo davvero intenzione di andare
su di esso ora è quello che stiamo dicendo.

420
00:22:13,100 --> 00:22:14,860
>> PUBBLICO: Questo è un albero di recupero.

421
00:22:14,860 --> 00:22:15,280
>> SPEAKER 1: Sì.

422
00:22:15,280 --> 00:22:16,196
E 'un albero di recupero.

423
00:22:16,196 --> 00:22:16,960
Impressionante.

424
00:22:16,960 --> 00:22:23,610
Quindi, una cosa da notare qui è che noi
stanno guardando i singoli caratteri

425
00:22:23,610 --> 00:22:24,480
qui, giusto?

426
00:22:24,480 --> 00:22:29,710
>> Quindi, prima con la nostra funzione di hash, si
state guardando le parole nel suo complesso,

427
00:22:29,710 --> 00:22:32,270
e ora stiamo cercando di più
i personaggi, giusto?

428
00:22:32,270 --> 00:22:38,380
Così abbiamo Maxwell qui e Mendel.

429
00:22:38,380 --> 00:22:47,840
Quindi, fondamentalmente un try-- un modo di pensare
di questo è che ogni livello qui

430
00:22:47,840 --> 00:22:49,000
è una serie di lettere.

431
00:22:49,000 --> 00:22:53,310

432
00:22:53,310 --> 00:22:55,790
Quindi questo è il nodo radice qui, giusto?

433
00:22:55,790 --> 00:23:01,980
Questo ha tutti i caratteri della
alfabeto per l'inizio di ogni parola.

434
00:23:01,980 --> 00:23:06,480
>> E ciò che si vuole fare è
per esempio, OK, abbiamo qualche parola M.

435
00:23:06,480 --> 00:23:10,590
Stiamo andando a cercare Maxwell, in modo da
andiamo a M. M punti per un intero

436
00:23:10,590 --> 00:23:14,800
altra una matrice dove ogni
parola, finché ci

437
00:23:14,800 --> 00:23:17,044
è una parola che ha un
la seconda lettera,

438
00:23:17,044 --> 00:23:19,460
finché c'è una parola che
B ha la seconda lettera,

439
00:23:19,460 --> 00:23:24,630
avrà un puntatore
andare a qualche serie successiva.

440
00:23:24,630 --> 00:23:29,290
>> Probabilmente non è un
parola che MP qualcosa,

441
00:23:29,290 --> 00:23:32,980
così nella posizione P in questa
matrice, sarebbe solo essere NULL.

442
00:23:32,980 --> 00:23:38,840
Sarebbe dire, OK, non c'è parola
che è M seguito da una P, OK?

443
00:23:38,840 --> 00:23:43,100
Quindi, se ci pensiamo bene, ogni
una di queste piccole cose

444
00:23:43,100 --> 00:23:47,990
è in realtà uno di questi
matrici di grandi dimensioni da A a Z.

445
00:23:47,990 --> 00:23:55,064
Quindi, quello che potrebbe essere una delle cose
cioè tipo di inconveniente di un tentativo?

446
00:23:55,064 --> 00:23:56,500
>> PUBBLICO: Un sacco di memoria.

447
00:23:56,500 --> 00:23:59,940
>> SPEAKER 1: E 'un sacco di memoria, giusto?

448
00:23:59,940 --> 00:24:08,750
Ognuno di questi blocchi qui
rappresenta 26 spazi, 26 array di elementi.

449
00:24:08,750 --> 00:24:13,680
Quindi cerca ottengono incredibilmente spazio pesante.

450
00:24:13,680 --> 00:24:17,100
>> Ma sono molto veloci.

451
00:24:17,100 --> 00:24:22,540
Così incredibilmente veloce, ma
molto spazio inefficiente.

452
00:24:22,540 --> 00:24:24,810
Tipo di dover calcolare
quale quello che si desidera.

453
00:24:24,810 --> 00:24:29,470
Questi sono davvero cool per il vostro pset,
ma lo fanno prendere un sacco di memoria,

454
00:24:29,470 --> 00:24:30,290
in modo compromesso.

455
00:24:30,290 --> 00:24:31,480
Sì?

456
00:24:31,480 --> 00:24:34,300
>> PUBBLICO: Sarebbe possibile
di istituire una prova e poi

457
00:24:34,300 --> 00:24:37,967
una volta che avete tutto il
i dati in esso che si need--

458
00:24:37,967 --> 00:24:39,550
Non so se questo avrebbe senso.

459
00:24:39,550 --> 00:24:42,200
Mi è stato sbarazzarsi di tutte le
Caratteri NULL, ma poi

460
00:24:42,200 --> 00:24:42,910
non sarebbe in grado di indicizzare them--

461
00:24:42,910 --> 00:24:43,275
>> SPEAKER 1: Hai ancora bisogno di loro.

462
00:24:43,275 --> 00:24:44,854
>> PUBBLICO: - allo stesso modo ogni volta.

463
00:24:44,854 --> 00:24:45,520
SPEAKER 1: Sì.

464
00:24:45,520 --> 00:24:50,460
È necessario i caratteri NULL per far
sapere se non c'è una parola lì.

465
00:24:50,460 --> 00:24:52,040
Ben fatto di avere qualcosa che si desidera?

466
00:24:52,040 --> 00:24:52,540
Ok.

467
00:24:52,540 --> 00:24:54,581
Va bene, quindi stiamo andando
per andare un po 'di più

468
00:24:54,581 --> 00:24:58,920
nel dettaglio tecnico dietro
una prova e lavorare con un esempio.

469
00:24:58,920 --> 00:25:01,490
>> OK, quindi questo è la stessa cosa.

470
00:25:01,490 --> 00:25:06,290
Mentre in una lista collegata, il principale
tipo di-- qual è la parola che voglio? -

471
00:25:06,290 --> 00:25:08,350
come la costruzione di blocco è stato un nodo.

472
00:25:08,350 --> 00:25:12,280
In una prova, abbiamo anche un nodo,
ma è definito in modo diverso.

473
00:25:12,280 --> 00:25:17,000
>> Così abbiamo un po 'bool che
rappresenta sia una parola in realtà

474
00:25:17,000 --> 00:25:23,530
esiste in questa posizione, e quindi
abbiamo alcune serie qui-- o meglio,

475
00:25:23,530 --> 00:25:27,840
questo è un puntatore a un
array di 27 caratteri.

476
00:25:27,840 --> 00:25:33,339
E questo per, in questo caso, questo
27-- Sono sicuro che tutti voi sono come, aspetta,

477
00:25:33,339 --> 00:25:34,880
ci sono 26 lettere nell'alfabeto.

478
00:25:34,880 --> 00:25:36,010
Perché abbiamo 27?

479
00:25:36,010 --> 00:25:37,870
>> Quindi, a seconda della
modo si implementa questa,

480
00:25:37,870 --> 00:25:43,240
questo è da un pset che
permesso di apostrofi.

481
00:25:43,240 --> 00:25:46,010
Ecco, questo è il motivo per cui l'uno in più.

482
00:25:46,010 --> 00:25:50,500
Avrete anche in alcuni
casi il terminatore nullo

483
00:25:50,500 --> 00:25:53,230
è incluso come una delle
caratteri che è permesso di essere,

484
00:25:53,230 --> 00:25:56,120
ed è così che controllano a
vedere se è la fine della parola.

485
00:25:56,120 --> 00:26:01,340
Se siete interessati, il check-out
Il video di Kevin su study.cs50,

486
00:26:01,340 --> 00:26:04,790
così come Wikipedia ha
alcune buone risorse là.

487
00:26:04,790 --> 00:26:09,000
>> Ma stiamo andando a passare attraverso solo tipo
di come si potrebbe lavorare attraverso una prova

488
00:26:09,000 --> 00:26:11,010
se sei dato uno.

489
00:26:11,010 --> 00:26:16,230
Così abbiamo un super semplice qui che
ha la parola "pipistrello" e "zoom" in loro.

490
00:26:16,230 --> 00:26:18,920
E come vediamo qui,
questo piccolo spazio qui

491
00:26:18,920 --> 00:26:22,560
rappresenta il nostro bool che
dice, sì, questa è una parola.

492
00:26:22,560 --> 00:26:27,060
E poi questo è il nostro
array di caratteri, giusto?

493
00:26:27,060 --> 00:26:33,480
>> Così ci accingiamo a passare attraverso
trovare "bat" in questo tentativo.

494
00:26:33,480 --> 00:26:38,340
Così iniziano in alto, giusto?

495
00:26:38,340 --> 00:26:46,290
E sappiamo che b corrisponde a
il secondo indice, il secondo elemento

496
00:26:46,290 --> 00:26:47,840
in questo array, perché ae b.

497
00:26:47,840 --> 00:26:51,340
Quindi circa il secondo.

498
00:26:51,340 --> 00:26:58,820
>> E dice, OK, fresco, ne consegue che in
l'array successivo, perché se ci ricordiamo,

499
00:26:58,820 --> 00:27:02,160
non è che ciascuno di questi
effettivamente contiene l'elemento.

500
00:27:02,160 --> 00:27:07,110
Ognuno di questi array
contiene un puntatore, giusto?

501
00:27:07,110 --> 00:27:10,030
Si tratta di una distinzione importante da fare.

502
00:27:10,030 --> 00:27:13,450
>> So che questo sta per essere-- tentativi sono
davvero difficile andare avanti per la prima volta,

503
00:27:13,450 --> 00:27:15,241
quindi, anche se questo è il
seconda o terza volta

504
00:27:15,241 --> 00:27:18,370
ed è ancora un po '
di sembrare difficile,

505
00:27:18,370 --> 00:27:21,199
Ti prometto se si va orologio
breve di nuovo domani,

506
00:27:21,199 --> 00:27:22,740
che probabilmente ha molto più senso.

507
00:27:22,740 --> 00:27:23,890
Ci vuole un sacco da digerire.

508
00:27:23,890 --> 00:27:27,800
Io ancora a volte sono
come, aspetta, che cosa è una prova?

509
00:27:27,800 --> 00:27:29,080
Come si usa questo?

510
00:27:29,080 --> 00:27:33,880
>> Così abbiamo B in questo caso,
che è il nostro secondo indice.

511
00:27:33,880 --> 00:27:40,240
Se avessimo, per esempio, c o
d o qualsiasi altra lettera,

512
00:27:40,240 --> 00:27:45,810
abbiamo bisogno di mappare che torna all'indice
di una matrice che corrisponde.

513
00:27:45,810 --> 00:27:56,930
Così vorremmo prendere come rchar e abbiamo appena
sottrarre fuori una di mappa in 0 a 25.

514
00:27:56,930 --> 00:27:58,728
Tutti bene il modo in cui
mappa i nostri personaggi?

515
00:27:58,728 --> 00:28:00,440
Ok.

516
00:28:00,440 --> 00:28:05,980
>> Quindi andiamo al secondo e
vedere che, sì, non è NULL.

517
00:28:05,980 --> 00:28:07,780
Siamo in grado di passare a questa nuova serie.

518
00:28:07,780 --> 00:28:12,300
Così andiamo avanti per la prossima serie qui.

519
00:28:12,300 --> 00:28:15,500
>> E noi diciamo, OK, ora siamo
bisogno di vedere se a è qui.

520
00:28:15,500 --> 00:28:18,590
A è NULL o lo fa
in realtà andare avanti?

521
00:28:18,590 --> 00:28:21,880
Così una realtà si muove
avanti in questo array.

522
00:28:21,880 --> 00:28:24,570
E noi diciamo, OK, t è la nostra ultima lettera.

523
00:28:24,570 --> 00:28:27,580
Quindi andiamo al t in corrispondenza dell'indice.

524
00:28:27,580 --> 00:28:30,120
E allora andiamo avanti
perché ce n'è un altro.

525
00:28:30,120 --> 00:28:38,340
E questo in pratica dice che, sì,
si dice che c'è una parola qui--

526
00:28:38,340 --> 00:28:41,750
che se si segue questa
percorso, siete arrivati

527
00:28:41,750 --> 00:28:43,210
in una parola, che noi sappiamo è "bat".

528
00:28:43,210 --> 00:28:43,800
Sì?

529
00:28:43,800 --> 00:28:46,770
>> PUBBLICO: E 'normale avere quel
come indice 0 e quindi avere una sorta a 1

530
00:28:46,770 --> 00:28:47,660
o di avere alla fine?

531
00:28:47,660 --> 00:28:48,243
>> SPEAKER 1: No.

532
00:28:48,243 --> 00:28:55,360
Quindi, se guardiamo indietro al nostro
dichiarazione di qui, è un bool,

533
00:28:55,360 --> 00:28:59,490
quindi è il suo elemento nel nodo.

534
00:28:59,490 --> 00:29:03,331
Quindi non è parte della matrice.

535
00:29:03,331 --> 00:29:03,830
Freddo.

536
00:29:03,830 --> 00:29:08,370
Così, quando abbiamo finito la nostra parola e siamo
a questo array, quello che vogliamo fare

537
00:29:08,370 --> 00:29:12,807
è fare un controllo per questo è una parola.

538
00:29:12,807 --> 00:29:14,390
E in questo caso, sarebbe tornare sì.

539
00:29:14,390 --> 00:29:17,220

540
00:29:17,220 --> 00:29:24,090
>> Quindi, su questa nota, sappiamo che "zoo" -
che noi conosciamo come gli esseri umani che "zoo" è una parola,

541
00:29:24,090 --> 00:29:24,820
giusto?

542
00:29:24,820 --> 00:29:28,990
Ma sono provate qui sarebbe
dire, no, non lo è.

543
00:29:28,990 --> 00:29:33,980
E sarebbe dire che perché noi
non hanno designato come una parola qui.

544
00:29:33,980 --> 00:29:40,440
Anche se siamo in grado di attraversare
attraverso a questo array,

545
00:29:40,440 --> 00:29:43,890
questa meta sarebbe dire che, no,
zoo non è nel dizionario

546
00:29:43,890 --> 00:29:47,070
perché non abbiamo
designato come tale.

547
00:29:47,070 --> 00:29:52,870
>> Quindi un modo per fare che--
oh, scusate, questo.

548
00:29:52,870 --> 00:29:59,450
Quindi, in questo caso, "zoo" non è
una parola, ma è nel nostro tentativo.

549
00:29:59,450 --> 00:30:05,690
Ma in questo, diciamo che vogliamo
introdurre la parola "bagno", cosa succede

550
00:30:05,690 --> 00:30:08,260
è che seguiamo through-- b, a, t.

551
00:30:08,260 --> 00:30:11,820
Siamo in questa matrice, e
andiamo a cercare per ore.

552
00:30:11,820 --> 00:30:15,220
>> In questo caso, quando
guardare il puntatore h,

553
00:30:15,220 --> 00:30:17,890
è che punta a NULL, OK?

554
00:30:17,890 --> 00:30:20,780
Quindi a meno che non sia esplicitamente
che punta a un altro array,

555
00:30:20,780 --> 00:30:25,000
si assume che tutti i puntatori
in questo array si punta a null.

556
00:30:25,000 --> 00:30:28,270
Quindi in questo caso, h punta
null in modo da non possiamo fare nulla,

557
00:30:28,270 --> 00:30:31,540
quindi sarebbe anche restituire
falso, "bagno" non è qui.

558
00:30:31,540 --> 00:30:34,102

559
00:30:34,102 --> 00:30:35,810
Così ora siamo in realtà
intenzione di passare attraverso

560
00:30:35,810 --> 00:30:39,790
come potremmo effettivamente dire
che "zoo" è nel nostro tentativo.

561
00:30:39,790 --> 00:30:42,920
Come inseriamo "zoo" in nostro tentativo?

562
00:30:42,920 --> 00:30:47,810
Quindi, nello stesso modo in cui abbiamo iniziato con
la nostra lista collegata, si parte alla radice.

563
00:30:47,810 --> 00:30:50,600
In caso di dubbio, iniziare a
la radice di queste cose.

564
00:30:50,600 --> 00:30:53,330
>> E diremo, OK, z.

565
00:30:53,330 --> 00:30:55,650
z esiste in questo, e lo fa.

566
00:30:55,650 --> 00:30:58,370
Quindi, si sta spostando verso
il vostro prossimo array, OK?

567
00:30:58,370 --> 00:31:01,482
E poi su quella successiva,
si dice, OK, non o esiste?

568
00:31:01,482 --> 00:31:03,000
Lo fa.

569
00:31:03,000 --> 00:31:04,330
Questo ancora una volta.

570
00:31:04,330 --> 00:31:08,670
>> E così il nostro prossimo, abbiamo detto,
OK, "zoo" è già qui.

571
00:31:08,670 --> 00:31:12,440
Tutto quello che dobbiamo fare è impostare questo uguale
al vero, che c'è una parola lì.

572
00:31:12,440 --> 00:31:15,260
Se tu avessi seguito tutto
fino a prima di tale momento,

573
00:31:15,260 --> 00:31:17,030
è una parola, quindi basta
impostarlo a tale.

574
00:31:17,030 --> 00:31:17,530
Sì?

575
00:31:17,530 --> 00:31:22,550
>> PUBBLICO: Allora fa che
significa che "ba" è anche una parola?

576
00:31:22,550 --> 00:31:24,120
>> SPEAKER 1: No.

577
00:31:24,120 --> 00:31:28,870
Quindi, in questo caso, "ba" otterremmo
qui, possiamo dire è che una parola,

578
00:31:28,870 --> 00:31:31,590
e sarebbe ancora no.

579
00:31:31,590 --> 00:31:32,822
Ok?

580
00:31:32,822 --> 00:31:33,740
Mmhmm?

581
00:31:33,740 --> 00:31:36,360
>> PUBBLICO: Quindi una volta che si tratta di un
parola e lei dice di sì, allora

582
00:31:36,360 --> 00:31:38,380
conterrà per andare in m?

583
00:31:38,380 --> 00:31:42,260
>> SPEAKER 1: Quindi questo ha a che fare
with-- si sta caricando in questo.

584
00:31:42,260 --> 00:31:43,640
Tu dici "zoo" è una parola.

585
00:31:43,640 --> 00:31:47,020
Quando si va a check--
come, dici che vuoi dire,

586
00:31:47,020 --> 00:31:49,400
si intende per "zoo" esiste in questo dizionario?

587
00:31:49,400 --> 00:31:54,200
Stai solo andando a cercare "zoo"
e poi controllare per vedere se si tratta di una parola.

588
00:31:54,200 --> 00:31:57,291
Non riuscirai mai a muoversi
fino alla m perché non è

589
00:31:57,291 --> 00:31:58,290
quello che stai cercando.

590
00:31:58,290 --> 00:32:02,690

591
00:32:02,690 --> 00:32:08,070
>> Quindi, se davvero volessimo
aggiungere "bagno" in questo tentativo,

592
00:32:08,070 --> 00:32:11,390
faremmo la stessa cosa
come abbiamo fatto con "zoo"

593
00:32:11,390 --> 00:32:15,380
tranne vedremmo che quando
cercare di ottenere di h, non esiste.

594
00:32:15,380 --> 00:32:20,090
Così si può pensare a questo come cercare
aggiungere un nuovo nodo in una lista collegata,

595
00:32:20,090 --> 00:32:27,210
quindi ci sarebbe bisogno di aggiungere altro
uno di questi array, in questo modo.

596
00:32:27,210 --> 00:32:35,670
E poi quello che facciamo è che abbiamo appena impostato il h
elemento di questa matrice punta a questo.

597
00:32:35,670 --> 00:32:39,430
>> E allora che cosa vorremmo fare qui?

598
00:32:39,430 --> 00:32:43,110
Aggiungi uguale a vero
perché è una parola.

599
00:32:43,110 --> 00:32:46,350

600
00:32:46,350 --> 00:32:48,150
Freddo.

601
00:32:48,150 --> 00:32:48,700
Lo so.

602
00:32:48,700 --> 00:32:51,170
Mete non sono la più emozionante.

603
00:32:51,170 --> 00:32:54,250
Fidati di me, lo so.

604
00:32:54,250 --> 00:32:58,040
>> Quindi, una cosa da realizzare con i tentativi,
Ho detto, sono molto efficienti.

605
00:32:58,040 --> 00:33:00,080
Così abbiamo visto che
prendere un sacco di spazio.

606
00:33:00,080 --> 00:33:01,370
Sono specie di confusione.

607
00:33:01,370 --> 00:33:03,367
Allora perché dovremmo mai usare questi?

608
00:33:03,367 --> 00:33:05,450
Usiamo questi perché sono
incredibilmente efficiente.

609
00:33:05,450 --> 00:33:08,130
>> Quindi, se siete mai cercando
una parola, tu sei solo

610
00:33:08,130 --> 00:33:10,450
delimitata dalla lunghezza della parola.

611
00:33:10,450 --> 00:33:15,210
Quindi, se siete alla ricerca di un
parola che è di lunghezza cinque,

612
00:33:15,210 --> 00:33:20,940
si sta sempre e solo andando ad avere per
rendere al massimo cinque confronti, OK?

613
00:33:20,940 --> 00:33:25,780
Quindi rende praticamente costante.

614
00:33:25,780 --> 00:33:29,150
Come l'inserimento e la ricerca
sono sostanzialmente costante di tempo.

615
00:33:29,150 --> 00:33:33,750
>> Quindi, se si può mai ottenere
qualcosa in tempo costante,

616
00:33:33,750 --> 00:33:35,150
questo è quanto di meglio si possa.

617
00:33:35,150 --> 00:33:37,990
Non si può trovare di meglio
costante di tempo per queste cose.

618
00:33:37,990 --> 00:33:43,150
Quindi questo è uno degli
enormi vantaggi di tentativi.

619
00:33:43,150 --> 00:33:46,780
>> Ma è un sacco di spazio.

620
00:33:46,780 --> 00:33:50,380
Così è sorta di decidere
che cosa è più importante per voi.

621
00:33:50,380 --> 00:33:54,700
E sui computer di oggi, il
spazio che una prova può richiedere fino

622
00:33:54,700 --> 00:33:57,740
forse non interessa
più di tanto, ma forse

623
00:33:57,740 --> 00:34:01,350
hai a che fare con qualcosa di
che ha molto, molto di più le cose,

624
00:34:01,350 --> 00:34:02,810
e una prova solo che non è ragionevole.

625
00:34:02,810 --> 00:34:03,000
Sì?

626
00:34:03,000 --> 00:34:05,610
>> PUBBLICO: Aspetta, in modo da avere 26
lettere in ognuno?

627
00:34:05,610 --> 00:34:07,440
>> SPEAKER 1: Mmhmm.

628
00:34:07,440 --> 00:34:08,570
Sì, avete 26.

629
00:34:08,570 --> 00:34:16,984
Hai qualche marcatore è parola e poi
si dispone di 26 puntatori a tutti.

630
00:34:16,984 --> 00:34:17,775
E sono point--

631
00:34:17,775 --> 00:34:20,280
>> PUBBLICO: E ogni 26,
fanno ogni hanno 26?

632
00:34:20,280 --> 00:34:21,500
>> SPEAKER 1: Sì.

633
00:34:21,500 --> 00:34:27,460
Ed è per questo che, come si può
vedere, si espande rapidamente.

634
00:34:27,460 --> 00:34:28,130
Bene.

635
00:34:28,130 --> 00:34:32,524
Quindi stiamo per entrare in alberi, che
Mi sento come è più facile e probabilmente

636
00:34:32,524 --> 00:34:36,150
essere un bel po 'di tregua
da tentativi lì.

637
00:34:36,150 --> 00:34:39,620
Così si spera la maggior parte di voi
hanno visto un albero prima.

638
00:34:39,620 --> 00:34:41,820
Non come la bella
quelli di fuori, che mi

639
00:34:41,820 --> 00:34:44,340
non so se qualcuno
è andato fuori di recente.

640
00:34:44,340 --> 00:34:49,230
Sono andato la raccolta delle mele in questo fine settimana,
e oh mio Dio, è stato bellissimo.

641
00:34:49,230 --> 00:34:52,250
Non sapevo che le foglie
poteva guardare quella bella.

642
00:34:52,250 --> 00:34:53,610
>> Quindi, questo è solo un albero, giusto?

643
00:34:53,610 --> 00:34:56,790
È solo alcuni nodi, e
punti a un gruppo di altri nodi.

644
00:34:56,790 --> 00:34:59,570
Come potete vedere qui, questo è
specie di un tema ricorrente.

645
00:34:59,570 --> 00:35:03,720
Nodi che punta ai nodi è una specie di
l'essenza di molte strutture dati.

646
00:35:03,720 --> 00:35:06,670
Dipende solo dal modo in cui
li hanno indicano reciprocamente

647
00:35:06,670 --> 00:35:08,600
e come attraversiamo
attraverso di loro e il modo in cui

648
00:35:08,600 --> 00:35:14,500
inserire cose che determina
le loro diverse caratteristiche.

649
00:35:14,500 --> 00:35:17,600
>> Quindi, solo un po 'di terminologia,
che ho usato prima.

650
00:35:17,600 --> 00:35:20,010
Così radice è tutto ciò che è in cima.

651
00:35:20,010 --> 00:35:21,200
è dove partiamo sempre.

652
00:35:21,200 --> 00:35:23,610
Si può pensare ad esso come la testa anche.

653
00:35:23,610 --> 00:35:28,750
Ma per gli alberi, si tende a
fare riferimento ad esso come la radice.

654
00:35:28,750 --> 00:35:32,820
>> Tutto ciò in qui-- fondo
al più, molto bottom--

655
00:35:32,820 --> 00:35:34,500
sono le foglie considerati.

656
00:35:34,500 --> 00:35:37,210
Così va insieme alla
tutto l'albero, giusto?

657
00:35:37,210 --> 00:35:39,860
Le foglie sono ai bordi del vostro albero.

658
00:35:39,860 --> 00:35:45,820
>> E poi abbiamo anche un paio di
termini per parlare di nodi in relazione

659
00:35:45,820 --> 00:35:46,680
tra loro.

660
00:35:46,680 --> 00:35:49,700
Così abbiamo genitore,
figli, e fratelli.

661
00:35:49,700 --> 00:35:56,260
Quindi in questo caso, 3 è il
madre di 5, 6 e 7.

662
00:35:56,260 --> 00:36:00,370
Così il genitore è tutto ciò che è
un gradino sopra quello che sei

663
00:36:00,370 --> 00:36:02,940
riferendosi a, quindi basta
come un albero genealogico.

664
00:36:02,940 --> 00:36:07,090
Speriamo che questo è tutto un po '
po 'più intuitivo rispetto ai tentativi.

665
00:36:07,090 --> 00:36:10,970
>> I fratelli sono quelle che hanno
lo stesso genitore, giusto?

666
00:36:10,970 --> 00:36:13,470
Sono allo stesso livello qui.

667
00:36:13,470 --> 00:36:16,960
E poi, come mi è stato
dicendo, i bambini sono solo

668
00:36:16,960 --> 00:36:22,630
tutto ciò che è un gradino sotto
il nodo in questione, OK?

669
00:36:22,630 --> 00:36:23,470
Freddo.

670
00:36:23,470 --> 00:36:25,610
Così un albero binario.

671
00:36:25,610 --> 00:36:31,450
Qualcuno può azzardare un'ipotesi su una delle
le caratteristiche dell'albero binario?

672
00:36:31,450 --> 00:36:32,770
>> PUBBLICO: Max due foglie.

673
00:36:32,770 --> 00:36:33,478
>> SPEAKER 1: Giusto.

674
00:36:33,478 --> 00:36:34,640
Quindi massimo di due foglie.

675
00:36:34,640 --> 00:36:39,730
Quindi, in questa prima, abbiamo avuto questo
che aveva tre, ma in un albero binario,

676
00:36:39,730 --> 00:36:45,000
si dispone di un massimo di due
bambini per genitori, giusto?

677
00:36:45,000 --> 00:36:46,970
C'è un altro
Caratteristica interessante.

678
00:36:46,970 --> 00:36:51,550
Qualcuno lo sa?

679
00:36:51,550 --> 00:36:52,620
Albero binario.

680
00:36:52,620 --> 00:37:00,350
>> Così un albero binario avrà tutto
su the-- questo non è sorted--

681
00:37:00,350 --> 00:37:05,320
ma in un albero binario filtrate,
tutto a destra

682
00:37:05,320 --> 00:37:08,530
è maggiore del genitore,
e tutto a sinistra

683
00:37:08,530 --> 00:37:10,035
è inferiore al genitore.

684
00:37:10,035 --> 00:37:15,690
E questo è stato un quiz
domanda prima, così bene da sapere.

685
00:37:15,690 --> 00:37:19,500
Quindi il modo in cui definiamo questo,
ancora una volta, abbiamo un altro nodo.

686
00:37:19,500 --> 00:37:21,880
Questo sembra molto simile a quello che?

687
00:37:21,880 --> 00:37:28,336

688
00:37:28,336 --> 00:37:28,836
Doppiamente

689
00:37:28,836 --> 00:37:29,320
>> PUBBLICO: Collegato liste

690
00:37:29,320 --> 00:37:31,100
>> SPEAKER 1: Una doppia lista collegata, giusto?

691
00:37:31,100 --> 00:37:33,690
Quindi, se sostituiamo questo
con precedente e successivo,

692
00:37:33,690 --> 00:37:35,670
questo sarebbe una lista doppiamente concatenata.

693
00:37:35,670 --> 00:37:40,125
Ma in questo caso, abbiamo effettivamente
avere a destra ea sinistra e il gioco è fatto.

694
00:37:40,125 --> 00:37:41,500
In caso contrario, è esattamente lo stesso.

695
00:37:41,500 --> 00:37:43,374
Abbiamo ancora l'elemento
che stai cercando,

696
00:37:43,374 --> 00:37:45,988
e basta avere due puntatori
andare a tutto ciò che è il prossimo.

697
00:37:45,988 --> 00:37:49,210

698
00:37:49,210 --> 00:37:51,870
Sì, albero di ricerca in modo binario.

699
00:37:51,870 --> 00:37:57,665
Se notiamo, tutto sul
proprio qui è maggiore than--

700
00:37:57,665 --> 00:37:59,850
o tutto e subito
a destra qui

701
00:37:59,850 --> 00:38:02,840
è maggiore di tutto
qui è inferiore.

702
00:38:02,840 --> 00:38:06,980

703
00:38:06,980 --> 00:38:14,000
>> Quindi, se siamo stati per la ricerca in, è
dovrebbe guardare molto vicino alla ricerca binaria

704
00:38:14,000 --> 00:38:14,910
qui, giusto?

705
00:38:14,910 --> 00:38:17,640
Tranne invece di guardare
a metà dell'array,

706
00:38:17,640 --> 00:38:21,720
stiamo solo guardando o sinistra
lato o sul lato destro dell'albero.

707
00:38:21,720 --> 00:38:24,850
Così diventa un po 'più semplice, credo.

708
00:38:24,850 --> 00:38:29,300
>> Così, se il root è NULL,
ovviamente è solo falso.

709
00:38:29,300 --> 00:38:33,470
E se c'è, ovviamente, è vero.

710
00:38:33,470 --> 00:38:35,320
Se è inferiore, cerchiamo sinistra.

711
00:38:35,320 --> 00:38:37,070
Se è superiore,
cerchiamo destra.

712
00:38:37,070 --> 00:38:39,890
E 'esattamente come la ricerca binaria,
solo una struttura dati diversa

713
00:38:39,890 --> 00:38:40,600
che stiamo usando.

714
00:38:40,600 --> 00:38:42,790
Al posto di un array,
è solo un albero binario.

715
00:38:42,790 --> 00:38:45,820

716
00:38:45,820 --> 00:38:48,090
>> OK, pile.

717
00:38:48,090 --> 00:38:51,550
E poi, sembra che ci
potrebbe avere un po 'di tempo.

718
00:38:51,550 --> 00:38:54,460
Se lo facciamo, io sono felice di andare
su tutto questo ancora una volta.

719
00:38:54,460 --> 00:38:56,856
OK, così stack.

720
00:38:56,856 --> 00:39:02,695
Qualcuno ricorda cosa stacks--
eventuali caratteristiche di una pila?

721
00:39:02,695 --> 00:39:05,550

722
00:39:05,550 --> 00:39:10,400
>> OK, quindi la maggior parte di noi, credo,
mangiare nella sala da halls--

723
00:39:10,400 --> 00:39:13,100
quanto potremmo non piace.

724
00:39:13,100 --> 00:39:16,900
Ma, ovviamente, si può pensare di una pila
letteralmente come una pila di vassoi

725
00:39:16,900 --> 00:39:18,460
o una pila di cose.

726
00:39:18,460 --> 00:39:21,820
E ciò che è importante
rendersi conto è che è

727
00:39:21,820 --> 00:39:26,850
something-- la caratteristica
che noi chiamiamo by-- è LIFO.

728
00:39:26,850 --> 00:39:28,450
Qualcuno sa di cosa si sta per?

729
00:39:28,450 --> 00:39:29,070
Mmhmm?

730
00:39:29,070 --> 00:39:30,650
>> PUBBLICO: last in, first out.

731
00:39:30,650 --> 00:39:32,250
>> SPEAKER 1: Destra, last in, first out.

732
00:39:32,250 --> 00:39:36,585
Quindi, se noi sappiamo, se siamo accatastamento cose
up, la cosa più facile da afferrare off--

733
00:39:36,585 --> 00:39:39,570
e forse l'unica cosa che può afferrare
off se il nostro stack è grande enough--

734
00:39:39,570 --> 00:39:40,850
è l'elemento superiore.

735
00:39:40,850 --> 00:39:43,460
Quindi, qualunque sia stato messo su
last-- come vediamo qui,

736
00:39:43,460 --> 00:39:46,370
tutto ciò che è stato spinto
sulla maggior parte recently-- è

737
00:39:46,370 --> 00:39:51,160
sarà il primo
cosa che abbiamo pop off, OK?

738
00:39:51,160 --> 00:39:56,324
>> Quindi, quello che abbiamo qui è
un'altra struct typedef.

739
00:39:56,324 --> 00:39:58,740
Questo è davvero come solo un
Crash Course in struttura di dati,

740
00:39:58,740 --> 00:40:01,650
quindi c'è un sacco gettato a voi ragazzi.

741
00:40:01,650 --> 00:40:02,540
Lo so.

742
00:40:02,540 --> 00:40:04,970
Quindi, ancora un altro struct.

743
00:40:04,970 --> 00:40:06,740
Yay per le strutture.

744
00:40:06,740 --> 00:40:16,660
>> E in questo caso, è qualche puntatore
ad una matrice che ha una certa capacità.

745
00:40:16,660 --> 00:40:20,830
Quindi questo rappresenta la nostra pila
qui, come la nostra gamma attuale

746
00:40:20,830 --> 00:40:22,520
che è in possesso di nostri elementi.

747
00:40:22,520 --> 00:40:24,850
E poi qui abbiamo una certa dimensione.

748
00:40:24,850 --> 00:40:31,170
>> E in genere, si desidera mantenere
traccia di come grande il vostro stack è

749
00:40:31,170 --> 00:40:36,180
perché quello che sta andando a consentire
di fare è se si conosce la dimensione,

750
00:40:36,180 --> 00:40:39,170
permette di dire,
OK, sono io a capacità?

751
00:40:39,170 --> 00:40:40,570
Posso aggiungere qualcosa di più?

752
00:40:40,570 --> 00:40:44,650
E ve lo dice anche
in cui la parte superiore della pila

753
00:40:44,650 --> 00:40:48,180
è in modo da sapere cosa si
può effettivamente decollare.

754
00:40:48,180 --> 00:40:51,760
E che in realtà sta per
essere un po 'più chiaro qui.

755
00:40:51,760 --> 00:40:57,350
>> Così, per spinta, una cosa, se si
erano mai ad attuare spinta,

756
00:40:57,350 --> 00:41:01,330
come ho appena detto, la tua
pila ha una dimensione limitata, giusto?

757
00:41:01,330 --> 00:41:03,990
La nostra serie ha avuto una certa capacità.

758
00:41:03,990 --> 00:41:04,910
Si tratta di un array.

759
00:41:04,910 --> 00:41:08,930
Si tratta di una dimensione fissa, quindi abbiamo bisogno di
assicurarsi che non stiamo mettendo più

760
00:41:08,930 --> 00:41:11,950
nella nostra matrice di noi
in realtà hanno spazio per.

761
00:41:11,950 --> 00:41:16,900
>> Così, quando si sta creando una spinta
funzione, prima cosa da fare è dire, OK,

762
00:41:16,900 --> 00:41:18,570
devo spazio nel mio stack?

763
00:41:18,570 --> 00:41:23,330
Perché se non lo faccio, mi dispiace,
Non riesco a memorizzare il vostro elemento.

764
00:41:23,330 --> 00:41:28,980
Se lo faccio, poi si desidera memorizzare
in cima alla pila, giusto?

765
00:41:28,980 --> 00:41:31,325
>> E questo è il motivo per cui abbiamo
per tenere traccia delle nostre dimensioni.

766
00:41:31,325 --> 00:41:35,290
Se non teniamo traccia delle nostre dimensioni,
non sappiamo dove metterlo.

767
00:41:35,290 --> 00:41:39,035
Non sappiamo quante cose
sono la nostra gamma già.

768
00:41:39,035 --> 00:41:41,410
Come, ovviamente, ci sono modi
che forse si potrebbe fare.

769
00:41:41,410 --> 00:41:44,610
Si potrebbe inizializzare tutto a NULL
e quindi controllare per le ultime NULL,

770
00:41:44,610 --> 00:41:47,950
ma una cosa molto più facile è solo
per dire, OK, tenere traccia di dimensioni.

771
00:41:47,950 --> 00:41:51,840
Come so che ho quattro elementi
nel mio array, quindi la prossima cosa

772
00:41:51,840 --> 00:41:55,930
che abbiamo messo su, siamo
andando a memorizzare all'indice 4.

773
00:41:55,930 --> 00:42:00,940
E poi, ovviamente, ciò significa che
che avete trasmesso con successo qualcosa

774
00:42:00,940 --> 00:42:03,320
sul vostro stack,
vogliono aumentare le dimensioni

775
00:42:03,320 --> 00:42:08,880
in modo da sapere dove sei così
che si può spingere più cose su.

776
00:42:08,880 --> 00:42:12,730
>> Quindi, se stiamo cercando di pop
qualcosa dallo stack,

777
00:42:12,730 --> 00:42:16,072
quello che potrebbe essere la prima cosa
che vogliamo controllare?

778
00:42:16,072 --> 00:42:18,030
Stai cercando di prendere
qualcosa che il vostro stack.

779
00:42:18,030 --> 00:42:21,710

780
00:42:21,710 --> 00:42:24,781
Sei sicuro che non c'è
qualcosa nel tuo stack?

781
00:42:24,781 --> 00:42:25,280
No.

782
00:42:25,280 --> 00:42:26,894
Allora, cosa potremmo desiderare di controllare?

783
00:42:26,894 --> 00:42:27,810
>> PUBBLICO: [incomprensibile].

784
00:42:27,810 --> 00:42:29,880
SPEAKER 1: Controllare le dimensioni?

785
00:42:29,880 --> 00:42:31,840
Dimensione.

786
00:42:31,840 --> 00:42:38,520
Quindi, vogliamo verificare se
la nostra dimensione è maggiore di 0, OK?

787
00:42:38,520 --> 00:42:44,970
E se lo è, allora vogliamo diminuire
la nostra dimensione di 0 e tornare quello.

788
00:42:44,970 --> 00:42:45,840
Perché?

789
00:42:45,840 --> 00:42:49,950
>> Nella prima eravamo
spingere, abbiamo spinto esso

790
00:42:49,950 --> 00:42:52,460
sulla dimensione e la dimensione poi aggiornato.

791
00:42:52,460 --> 00:42:57,850
In questo caso, stiamo decrementare dimensioni
e poi toglierlo, strappando esso

792
00:42:57,850 --> 00:42:58,952
dal nostro array.

793
00:42:58,952 --> 00:42:59,826
Perché potremmo farlo?

794
00:42:59,826 --> 00:43:04,800

795
00:43:04,800 --> 00:43:11,811
Quindi, se ho una cosa sul mio stack,
quello che sarebbe il mio numero a quel punto?

796
00:43:11,811 --> 00:43:13,140
1.

797
00:43:13,140 --> 00:43:15,180
>> E in cui è memorizzato l'elemento 1?

798
00:43:15,180 --> 00:43:17,621
A quale indice?

799
00:43:17,621 --> 00:43:18,120
PUBBLICO: 0.

800
00:43:18,120 --> 00:43:19,060
SPEAKER 1: 0.

801
00:43:19,060 --> 00:43:22,800
Quindi, in questo caso,
sempre bisogno di fare sure--

802
00:43:22,800 --> 00:43:27,630
invece di restituire
dimensione meno 1, perché noi

803
00:43:27,630 --> 00:43:31,730
sa che il nostro elemento è
sta per essere conservato a 1 meno

804
00:43:31,730 --> 00:43:34,705
qualunque sia la nostra dimensione è, questo
appena si prende cura di esso.

805
00:43:34,705 --> 00:43:36,080
E 'un modo un po' più elegante.

806
00:43:36,080 --> 00:43:41,220
E abbiamo appena decrementa il nostro
dimensioni e poi tornare dimensioni.

807
00:43:41,220 --> 00:43:42,330
Mmhmm?

808
00:43:42,330 --> 00:43:45,300
>> PUBBLICO: Credo che solo in generale,
perché sarebbe questa struttura dati

809
00:43:45,300 --> 00:43:47,800
essere utile?

810
00:43:47,800 --> 00:43:50,660
>> SPEAKER 1: Dipende dal vostro contesto.

811
00:43:50,660 --> 00:43:57,420
Così per alcuni della teoria,
se si sta lavorando with-- OK,

812
00:43:57,420 --> 00:44:02,750
fammi vedere se vi è una benefica
cioè vantaggioso per più di fuori

813
00:44:02,750 --> 00:44:05,420
di CS.

814
00:44:05,420 --> 00:44:15,780
Con stack, ogni volta che si ha bisogno
per tenere traccia di qualcosa che

815
00:44:15,780 --> 00:44:20,456
è la più recente aggiunta è quando
si sta andando a voler utilizzare una pila.

816
00:44:20,456 --> 00:44:24,770
>> E non riesco a pensare ad un buon
esempio di che in questo momento.

817
00:44:24,770 --> 00:44:29,955
Ma quando il più recente
cosa è più importante per voi,

818
00:44:29,955 --> 00:44:31,705
in quel momento una pila
sta per essere utile.

819
00:44:31,705 --> 00:44:35,797

820
00:44:35,797 --> 00:44:39,330
Sto cercando di pensare se
c'è una buona per questo.

821
00:44:39,330 --> 00:44:43,720
Se penso a un buon esempio nel prossimo
20 minuti, ci tornerò sicuramente dirà.

822
00:44:43,720 --> 00:44:49,455
>> Ma nel complesso, se c'è qualcosa,
come ho detto la maggior parte, in cui più recente

823
00:44:49,455 --> 00:44:52,470
è più importante, che è
dove una pila entra in gioco.

824
00:44:52,470 --> 00:44:58,860
Considerando che le code sono di tipo opposto.

825
00:44:58,860 --> 00:44:59,870
E tutti i piccoli cani.

826
00:44:59,870 --> 00:45:00,890
Non è questo grande, giusto?

827
00:45:00,890 --> 00:45:03,299
Mi sento come dovrei
basta avere un video coniglio

828
00:45:03,299 --> 00:45:05,090
proprio nel mezzo di
sezione per voi ragazzi

829
00:45:05,090 --> 00:45:08,870
perché questa è una sezione intenso.

830
00:45:08,870 --> 00:45:10,480
>> Così una coda.

831
00:45:10,480 --> 00:45:12,710
Fondamentalmente una coda è come una linea.

832
00:45:12,710 --> 00:45:15,780
Voi ragazzi sono sicuro che uso questo tutti i giorni,
proprio come nelle nostre sale da pranzo.

833
00:45:15,780 --> 00:45:18,160
Quindi dobbiamo andare a
e ottenere i nostri vassoi, sono

834
00:45:18,160 --> 00:45:21,260
Assicurati di avere di attendere in linea
di strisciare o ottenere il vostro cibo.

835
00:45:21,260 --> 00:45:24,650
>> Quindi la differenza qui
è che questo è FIFO.

836
00:45:24,650 --> 00:45:30,090
Quindi, se LIFO ultimo entrato, primo
out, FIFO è il primo entrato, primo uscito.

837
00:45:30,090 --> 00:45:33,400
Quindi questo è dove tutto ciò che si mette
il primo è il vostro più importante.

838
00:45:33,400 --> 00:45:35,540
Quindi, se stavate aspettando
in un line-- anche voi

839
00:45:35,540 --> 00:45:39,130
immaginate se si è andato a
andare a prendere il nuovo iPhone

840
00:45:39,130 --> 00:45:42,800
ed era una pila in cui la
ultima persona in linea ha in primo luogo,

841
00:45:42,800 --> 00:45:44,160
persone si uccidono a vicenda.

842
00:45:44,160 --> 00:45:49,800
>> Così FIFO, siamo tutti molto familiare
con nel mondo reale qui

843
00:45:49,800 --> 00:45:54,930
e tutto ha a che fare con la realtà
tipo di ricreare tutta questa linea

844
00:45:54,930 --> 00:45:56,900
e in coda la struttura.

845
00:45:56,900 --> 00:46:02,390
Così, mentre con lo stack,
abbiamo push e pop.

846
00:46:02,390 --> 00:46:06,440
Con una coda, abbiamo
accodamento e dequeue.

847
00:46:06,440 --> 00:46:10,910
Così enqueue significa fondamentalmente
metterlo sul retro,

848
00:46:10,910 --> 00:46:13,680
e mezzi dequeue prendono
dalla parte anteriore.

849
00:46:13,680 --> 00:46:18,680
Così la nostra struttura dati è un
po 'più complicata.

850
00:46:18,680 --> 00:46:21,060
Abbiamo una seconda cosa da tenere traccia di.

851
00:46:21,060 --> 00:46:25,950
>> Così, senza la testa, questo
è esattamente una pila, giusto?

852
00:46:25,950 --> 00:46:27,900
Questa è la stessa struttura di una pila.

853
00:46:27,900 --> 00:46:32,480
L'unica cosa diversa è che ora
avere questa testa, che cosa ne pensi

854
00:46:32,480 --> 00:46:34,272
sta per tenere traccia di?

855
00:46:34,272 --> 00:46:35,510
>> Pubblico: Il primo.

856
00:46:35,510 --> 00:46:38,685
>> SPEAKER 1: a destra, il
prima cosa che abbiamo messo in.

857
00:46:38,685 --> 00:46:41,130
Il capo della nostra coda.

858
00:46:41,130 --> 00:46:42,240
Chi è in prima linea.

859
00:46:42,240 --> 00:46:45,300

860
00:46:45,300 --> 00:46:49,420
Va bene, quindi se facciamo accodamento.

861
00:46:49,420 --> 00:46:52,720

862
00:46:52,720 --> 00:46:55,920
Ancora, con qualsiasi
queste strutture di dati,

863
00:46:55,920 --> 00:46:59,760
dal momento che abbiamo a che fare con una matrice,
abbiamo bisogno di controllare se abbiamo spazio.

864
00:46:59,760 --> 00:47:03,290
>> Questo è un po 'come dirmi
voi ragazzi, se si apre un file,

865
00:47:03,290 --> 00:47:04,760
è necessario controllare per nulla.

866
00:47:04,760 --> 00:47:08,330
Con qualsiasi di queste pile
e le code, è necessario

867
00:47:08,330 --> 00:47:13,420
per vedere se c'è lo spazio perché siamo
si tratta di un array di dimensione fissa,

868
00:47:13,420 --> 00:47:16,030
come si vede qui-- 0, 1 tutto a 5.

869
00:47:16,030 --> 00:47:20,690
Quindi, ciò che facciamo in questo caso è di controllo
per vedere se abbiamo ancora spazio.

870
00:47:20,690 --> 00:47:23,110
È la nostra dimensione inferiore alla capacità?

871
00:47:23,110 --> 00:47:28,480
>> Se è così, abbiamo bisogno di conservarlo a
la coda e aggiorniamo la nostra dimensione.

872
00:47:28,480 --> 00:47:30,250
Così che cosa potrebbe essere la coda in questo caso?

873
00:47:30,250 --> 00:47:32,360
Non è esplicitamente scritto fuori.

874
00:47:32,360 --> 00:47:33,380
Come possiamo conservarlo?

875
00:47:33,380 --> 00:47:34,928
Quale sarebbe la coda essere?

876
00:47:34,928 --> 00:47:38,600

877
00:47:38,600 --> 00:47:40,190
>> Quindi cerchiamo di camminare attraverso questo esempio.

878
00:47:40,190 --> 00:47:44,590
Quindi questo è un array di dimensione 6, giusto?

879
00:47:44,590 --> 00:47:49,220
E noi abbiamo in questo momento, il nostro formato è 5.

880
00:47:49,220 --> 00:47:55,240
E quando abbiamo messo dentro, è in corso
per entrare nel quinto indice, giusto?

881
00:47:55,240 --> 00:47:57,030
Così conservare a coda.

882
00:47:57,030 --> 00:48:05,600
>> Un altro modo di scrivere la coda sarebbe solo
sia la nostra gamma all'indice di dimensioni, giusto?

883
00:48:05,600 --> 00:48:07,560
Questa è la dimensione 5.

884
00:48:07,560 --> 00:48:11,490
La prossima cosa sta per andare in 5.

885
00:48:11,490 --> 00:48:12,296
Cool?

886
00:48:12,296 --> 00:48:13,290
Ok.

887
00:48:13,290 --> 00:48:16,350
Diventa un po 'più complicato
quando iniziamo scherzi con la testa.

888
00:48:16,350 --> 00:48:17,060
Sì?

889
00:48:17,060 --> 00:48:20,090
>> PUBBLICO: Questo significa che noi
avrebbe dichiarato un array che

890
00:48:20,090 --> 00:48:23,880
era lunga cinque elementi e
allora stiamo aggiungendo su di esso?

891
00:48:23,880 --> 00:48:24,730
>> SPEAKER 1: No.

892
00:48:24,730 --> 00:48:27,560
Quindi, in questo caso, si tratta di uno stack.

893
00:48:27,560 --> 00:48:31,760
Questo sarebbe dichiarato
come un array di dimensione 6.

894
00:48:31,760 --> 00:48:37,120
E in questo caso,
solo avere uno spazio a sinistra.

895
00:48:37,120 --> 00:48:42,720
>> OK, quindi una cosa è in questo
caso, se la nostra testa è a 0,

896
00:48:42,720 --> 00:48:45,270
poi abbiamo appena possiamo aggiungere che nelle dimensioni.

897
00:48:45,270 --> 00:48:51,020
Ma diventa un po 'più complicato
perché in realtà, si

898
00:48:51,020 --> 00:48:52,840
non hanno una diapositiva
per questo, quindi ho intenzione

899
00:48:52,840 --> 00:48:56,670
disegnare uno perché non è
è così semplice una volta che si

900
00:48:56,670 --> 00:48:59,230
iniziare a sbarazzarsi delle cose.

901
00:48:59,230 --> 00:49:03,920
Così mentre con una pila
solamente mai avuto

902
00:49:03,920 --> 00:49:08,920
preoccuparsi di ciò che la dimensione è
quando si aggiunge qualcosa,

903
00:49:08,920 --> 00:49:15,710
con una coda è inoltre necessario fare
Assicurarsi che la testa è rappresentato,

904
00:49:15,710 --> 00:49:20,760
perché una cosa bella di code
è che se non sei al massimo della capacità,

905
00:49:20,760 --> 00:49:23,040
si può effettivamente rendere più avvolgente.

906
00:49:23,040 --> 00:49:28,810
>> OK, così si cosa-- oh,
questo è terribile gesso.

907
00:49:28,810 --> 00:49:31,815
Una cosa da considerare è il caso.

908
00:49:31,815 --> 00:49:35,514

909
00:49:35,514 --> 00:49:37,140
Dobbiamo solo fare cinque.

910
00:49:37,140 --> 00:49:41,810
OK, quindi stiamo andando a
dire la testa è qui.

911
00:49:41,810 --> 00:49:46,140
Questo è 0, 1, 2, 3, 4.

912
00:49:46,140 --> 00:49:54,210
>> La testa è lì, e
si prega di avere delle cose in loro.

913
00:49:54,210 --> 00:49:58,340
E vogliamo aggiungere qualcosa, giusto?

914
00:49:58,340 --> 00:50:01,170
Quindi la cosa che abbiamo bisogno di
sapere è che la testa è sempre

915
00:50:01,170 --> 00:50:05,620
andando a muoversi in questo modo e
poi loop back in giro, OK?

916
00:50:05,620 --> 00:50:10,190
>> Quindi questa coda ha spazio, giusto?

917
00:50:10,190 --> 00:50:13,950
Ha spazio fin dall'inizio,
tipo l'opposto di questo.

918
00:50:13,950 --> 00:50:17,920
Quindi quello che dobbiamo fare è che
necessario calcolare la coda.

919
00:50:17,920 --> 00:50:20,530
Se sapete che il vostro
testa non si è mosso, coda

920
00:50:20,530 --> 00:50:24,630
è solo l'array a
l'indice delle dimensioni.

921
00:50:24,630 --> 00:50:30,000
>> Ma in realtà, se si sta utilizzando una coda,
la testa è probabilmente in fase di aggiornamento.

922
00:50:30,000 --> 00:50:33,890
Quindi quello che dovete fare è
effettivamente calcolare la coda.

923
00:50:33,890 --> 00:50:39,990
Quindi, quello che facciamo è questa formula
qui, che ho intenzione di farvi

924
00:50:39,990 --> 00:50:42,680
ragazzi pensano, e
poi ne parliamo.

925
00:50:42,680 --> 00:50:49,567

926
00:50:49,567 --> 00:50:50,400
Quindi questa è la capacità.

927
00:50:50,400 --> 00:50:55,890

928
00:50:55,890 --> 00:50:59,660
>> Quindi questo sarà effettivamente
vi darà un modo per farlo.

929
00:50:59,660 --> 00:51:03,205

930
00:51:03,205 --> 00:51:04,330
Perché in questo caso, che cosa?

931
00:51:04,330 --> 00:51:09,205
La nostra testa è a 1, il nostro formato è 4.

932
00:51:09,205 --> 00:51:11,760

933
00:51:11,760 --> 00:51:18,490
Se noi mod che da 5, si ottiene 0,
che è dove dovremmo inserirlo.

934
00:51:18,490 --> 00:51:23,320

935
00:51:23,320 --> 00:51:26,080
>> Dunque, nel caso successivo,
se dovessimo fare questo,

936
00:51:26,080 --> 00:51:33,390
si dice, OK, facciamo dequeue qualcosa.

937
00:51:33,390 --> 00:51:34,390
Si dequeue questo.

938
00:51:34,390 --> 00:51:37,740
Prendiamo questo elemento, giusto?

939
00:51:37,740 --> 00:51:47,930
>> E ora la nostra testa è rivolta qui,
e vogliamo aggiungere un'altra cosa.

940
00:51:47,930 --> 00:51:52,470
Questa è fondamentalmente la
posteriore della nostra linea, giusto?

941
00:51:52,470 --> 00:51:55,450
Le code possono avvolgere intorno alla matrice.

942
00:51:55,450 --> 00:51:57,310
Questa è una delle principali differenze.

943
00:51:57,310 --> 00:51:58,780
Stacks, non si può fare questo.

944
00:51:58,780 --> 00:52:01,140
>> Con le code, è possibile
perché tutto quello che conta

945
00:52:01,140 --> 00:52:03,940
è che si sa che cosa
è stato recentemente aggiunto.

946
00:52:03,940 --> 00:52:10,650
Dal momento che tutto sta per essere aggiunto
questa direzione verso sinistra, in questo caso,

947
00:52:10,650 --> 00:52:16,480
e poi avvolgere intorno, è possibile
continuare a mettere in nuovi elementi

948
00:52:16,480 --> 00:52:18,830
nella parte anteriore della matrice
perché non è davvero

949
00:52:18,830 --> 00:52:20,640
la parte anteriore della matrice più.

950
00:52:20,640 --> 00:52:26,320
Si può pensare all'inizio del
array come se la testa è in realtà.

951
00:52:26,320 --> 00:52:29,710
>> Quindi, questa formula è il modo
si calcola la coda.

952
00:52:29,710 --> 00:52:32,780

953
00:52:32,780 --> 00:52:35,610
Fa questo ha un senso?

954
00:52:35,610 --> 00:52:36,110
Ok.

955
00:52:36,110 --> 00:52:39,400

956
00:52:39,400 --> 00:52:44,040
OK, dequeue, e poi
voi ragazzi avete 10 minuti

957
00:52:44,040 --> 00:52:48,840
di farmi tutte le domande chiarendo gli
si vuole, perché so che è pazzesco.

958
00:52:48,840 --> 00:52:51,980
>> Va bene, così nella stessa way--
Non so se voi ragazzi notato,

959
00:52:51,980 --> 00:52:53,450
ma CS è tutto su modelli.

960
00:52:53,450 --> 00:52:57,370
Le cose sono più o meno la
stesso, solo con piccoli ritocchi.

961
00:52:57,370 --> 00:52:58,950
Quindi, stessa cosa qui.

962
00:52:58,950 --> 00:53:04,040
Abbiamo bisogno di controllare per vedere se abbiamo effettivamente
avere qualcosa nella nostra coda, giusto?

963
00:53:04,040 --> 00:53:05,960
Di ', OK, è la nostra dimensione maggiore di 0?

964
00:53:05,960 --> 00:53:06,730
Freddo.

965
00:53:06,730 --> 00:53:10,690
>> Se lo facciamo, allora ci spostiamo la nostra testa, che
è quello che ho appena dimostrato qui.

966
00:53:10,690 --> 00:53:13,870
Aggiorniamo la nostra testa di essere un altro.

967
00:53:13,870 --> 00:53:18,390
E poi abbiamo decrementa il nostro
dimensioni e restituire l'elemento.

968
00:53:18,390 --> 00:53:21,000

969
00:53:21,000 --> 00:53:26,250
>> C'è molto di più concreto
codice su study.cs50.net,

970
00:53:26,250 --> 00:53:29,440
e mi raccomando di andare
attraverso di essa se avete tempo,

971
00:53:29,440 --> 00:53:30,980
anche se è solo una pseudo-codice.

972
00:53:30,980 --> 00:53:35,980
E se voi volete parlare attraverso
che con me uno contro uno, per favore fatemelo

973
00:53:35,980 --> 00:53:37,500
conoscere.

974
00:53:37,500 --> 00:53:38,770
Sarei felice di.

975
00:53:38,770 --> 00:53:42,720
Strutture di dati, se
si prende CS 124, ti

976
00:53:42,720 --> 00:53:47,830
sanno che le strutture di dati diventano molto
divertimento e questo è solo all'inizio.

977
00:53:47,830 --> 00:53:50,350
>> Quindi so che è difficile.

978
00:53:50,350 --> 00:53:51,300
Va bene.

979
00:53:51,300 --> 00:53:52,410
Noi lottiamo.

980
00:53:52,410 --> 00:53:53,630
Faccio ancora.

981
00:53:53,630 --> 00:53:56,660
Quindi non preoccupatevi troppo su di esso.

982
00:53:56,660 --> 00:54:02,390
>> Ma questo è in fondo il tuo
Crash Course in strutture di dati.

983
00:54:02,390 --> 00:54:03,400
Lo so che è un sacco.

984
00:54:03,400 --> 00:54:06,860
C'è qualcosa che noi
vorrebbe andare di nuovo?

985
00:54:06,860 --> 00:54:09,400
Qualsiasi cosa vogliamo parlare fino in fondo?

986
00:54:09,400 --> 00:54:10,060
Sì?

987
00:54:10,060 --> 00:54:16,525
>> PUBBLICO: Per questo esempio, così
la nuova coda è a 0 su quella?

988
00:54:16,525 --> 00:54:17,150
SPEAKER 1: Sì.

989
00:54:17,150 --> 00:54:18,230
PUBBLICO: OK.

990
00:54:18,230 --> 00:54:24,220
Così poi passare attraverso,
avresti 1 più 4 o-

991
00:54:24,220 --> 00:54:27,671
>> SPEAKER 1: Così dicevano,
quando vogliamo andare farlo di nuovo?

992
00:54:27,671 --> 00:54:28,296
PUBBLICO: Sì.

993
00:54:28,296 --> 00:54:38,290
Quindi, se si dovesse capire fuori-- dove sono
a calcolare la coda da in questo?

994
00:54:38,290 --> 00:54:44,260
>> SPEAKER 1: Così la coda
ero dentro-- ho cambiato questo.

995
00:54:44,260 --> 00:54:52,010
Quindi in questo esempio qui, questo era
l'array che stiamo guardando, OK?

996
00:54:52,010 --> 00:54:54,670
Così abbiamo cose in 1, 2, 3, e 4.

997
00:54:54,670 --> 00:55:05,850
Così abbiamo la nostra testa è uguale a 1 a
questo punto, e il formato è uguale a 4

998
00:55:05,850 --> 00:55:07,050
a questo punto, giusto?

999
00:55:07,050 --> 00:55:08,960
>> Voi tutti d'accordo che è il caso?

1000
00:55:08,960 --> 00:55:14,620
Così facciamo la testa più il formato, che
ci dà 5, e poi ci Mod per 5.

1001
00:55:14,620 --> 00:55:20,690
Otteniamo 0, il che ci dice che 0 è
dove è la nostra coda, dove abbiamo spazio.

1002
00:55:20,690 --> 00:55:22,010
>> PUBBLICO: Che cosa è un tappo?

1003
00:55:22,010 --> 00:55:23,520
>> SPEAKER 1: La capacità.

1004
00:55:23,520 --> 00:55:24,020
Scusi.

1005
00:55:24,020 --> 00:55:29,640
In modo che è la dimensione dell'array.

1006
00:55:29,640 --> 00:55:35,210

1007
00:55:35,210 --> 00:55:36,047
Sì?

1008
00:55:36,047 --> 00:55:39,210
>> PUBBLICO: [incomprensibile] prima
torniamo l'elemento?

1009
00:55:39,210 --> 00:55:46,270
>> SPEAKER 1: Così si passa il
testa o restituire il momento?

1010
00:55:46,270 --> 00:55:52,680
Quindi, se ci muoviamo uno, diminuire le dimensioni?

1011
00:55:52,680 --> 00:55:54,150
Resisti.

1012
00:55:54,150 --> 00:55:55,770
Ho sicuramente dimenticato un'altra.

1013
00:55:55,770 --> 00:56:00,646

1014
00:56:00,646 --> 00:56:01,990
Non importa.

1015
00:56:01,990 --> 00:56:04,980
Non c'è un'altra formula.

1016
00:56:04,980 --> 00:56:09,980
Sì, si vorrebbe tornare
la testa e poi spostarlo indietro.

1017
00:56:09,980 --> 00:56:13,270
>> PUBBLICO: OK, perché in questo
punto, la testa era a 0,

1018
00:56:13,270 --> 00:56:18,452
e poi si desidera tornare
indice 0 e poi fare capo 1?

1019
00:56:18,452 --> 00:56:19,870
>> SPEAKER 1: Giusto.

1020
00:56:19,870 --> 00:56:22,820
Penso che ci sia un altro
formula un po 'come questo.

1021
00:56:22,820 --> 00:56:26,970
Io non ce l'ho in alto la mia testa come
Non voglio darvi quella sbagliata.

1022
00:56:26,970 --> 00:56:35,470
Ma penso che sia perfettamente valido
per esempio, OK, conservare questo element-- qualunque

1023
00:56:35,470 --> 00:56:40,759
elemento di testa è-- diminuire il tuo
dimensione, muovere la testa su e ritorno

1024
00:56:40,759 --> 00:56:41,800
qualunque cosa questo elemento è.

1025
00:56:41,800 --> 00:56:44,760
Questo è perfettamente valido.

1026
00:56:44,760 --> 00:56:45,260
Ok.

1027
00:56:45,260 --> 00:56:48,360

1028
00:56:48,360 --> 00:56:53,560
Mi sento come se questo non è
come il most-- non sei

1029
00:56:53,560 --> 00:56:55,740
andando a uscire di qui
come, sì, lo so tentativi.

1030
00:56:55,740 --> 00:56:56,880
Ho capito tutto.

1031
00:56:56,880 --> 00:56:57,670
Va bene.

1032
00:56:57,670 --> 00:57:00,200
Prometto.

1033
00:57:00,200 --> 00:57:05,240
Ma le strutture di dati sono qualcosa che
ci vuole un sacco di tempo per abituarsi.

1034
00:57:05,240 --> 00:57:10,010
Probabilmente uno dei più difficili
cose, credo, nel corso.

1035
00:57:10,010 --> 00:57:15,330
>> Quindi ci vuole sicuramente
ripetizione e guardando at-- I

1036
00:57:15,330 --> 00:57:20,050
non sapevamo veramente liste collegate
fino a quando ho fatto troppo con loro,

1037
00:57:20,050 --> 00:57:22,550
nello stesso modo in cui non ho fatto
davvero capire puntatori

1038
00:57:22,550 --> 00:57:27,040
fino a quando ho dovuto insegnare per due
anni e fare la mia p-set con esso.

1039
00:57:27,040 --> 00:57:28,990
Ci vuole un sacco di reiterazione e di tempo.

1040
00:57:28,990 --> 00:57:32,600
E alla fine, sarà di tipo fare clic su.

1041
00:57:32,600 --> 00:57:36,320
>> Ma nel frattempo, se si dispone di genere
di un elevato livello di comprensione di ciò che

1042
00:57:36,320 --> 00:57:39,321
questi fanno, i loro pro
e cons-- che è ciò che

1043
00:57:39,321 --> 00:57:41,820
abbiamo davvero tendiamo a sottolineare,
specialmente nel corso di introduzione.

1044
00:57:41,820 --> 00:57:45,511
Come, perché dovremmo usare
una prova su un array?

1045
00:57:45,511 --> 00:57:48,010
Come, quali sono gli aspetti positivi
e negativi di ciascuno di questi?

1046
00:57:48,010 --> 00:57:51,610
>> E la comprensione dei trade-off
tra ciascuna di queste strutture

1047
00:57:51,610 --> 00:57:54,910
è ciò che è molto più importante in questo momento.

1048
00:57:54,910 --> 00:57:58,140
Ci può essere un pazzo
domanda o due che è

1049
00:57:58,140 --> 00:58:03,710
andare a chiedere di implementare spingere o
implementare pop o accodamento e dequeue.

1050
00:58:03,710 --> 00:58:07,340
Ma per la maggior parte, avendo tale
comprensione di livello più alto e più

1051
00:58:07,340 --> 00:58:09,710
di una comprensione intuitiva è
più importante della realtà

1052
00:58:09,710 --> 00:58:11,250
essere in grado di attuarla.

1053
00:58:11,250 --> 00:58:14,880
>> Sarebbe davvero fantastico se tutti voi
potrebbe uscire e andare a realizzare una prova,

1054
00:58:14,880 --> 00:58:19,720
ma si capisce che non è necessariamente
la cosa più ragionevole in questo momento.

1055
00:58:19,720 --> 00:58:23,370
Ma è possibile nel vostro pset, se si desidera
di, e poi si otterrà la pratica,

1056
00:58:23,370 --> 00:58:27,200
e allora forse avrete
davvero capirlo.

1057
00:58:27,200 --> 00:58:27,940
Sì?

1058
00:58:27,940 --> 00:58:30,440
>> PUBBLICO: OK, quindi quali sono
intendevamo utilizzare nel pset?

1059
00:58:30,440 --> 00:58:31,916
Ho bisogno di utilizzare uno di loro?

1060
00:58:31,916 --> 00:58:32,540
SPEAKER 1: Sì.

1061
00:58:32,540 --> 00:58:34,199
In modo da avere la vostra scelta.

1062
00:58:34,199 --> 00:58:36,740
Credo che in questo caso, possiamo
parlare del pset un po '

1063
00:58:36,740 --> 00:58:40,480
perché mi sono imbattuto attraverso questi.

1064
00:58:40,480 --> 00:58:47,779
Quindi nel tuo pset, avete la vostra
scelta di tentativi o tabelle hash.

1065
00:58:47,779 --> 00:58:49,570
Alcune persone cercano
e utilizzare filtri fioritura,

1066
00:58:49,570 --> 00:58:51,840
ma quelli che tecnicamente non sono corrette.

1067
00:58:51,840 --> 00:58:55,804
A causa della loro natura probabilistica,
danno falsi positivi a volte.

1068
00:58:55,804 --> 00:58:57,095
Sono look fresco in, però.

1069
00:58:57,095 --> 00:58:59,030
Consiglio vivamente cercando
a loro almeno.

1070
00:58:59,030 --> 00:59:03,260
Ma avete la vostra scelta
tra una tabella di hash e una prova.

1071
00:59:03,260 --> 00:59:06,660
E che sta per essere dove
si carica nel dizionario.

1072
00:59:06,660 --> 00:59:09,230
>> E avrete bisogno di scegliere
la funzione di hash,

1073
00:59:09,230 --> 00:59:13,420
è necessario scegliere il numero di
Benne avete, e varierà.

1074
00:59:13,420 --> 00:59:17,440
Come se avete più secchi,
forse ti correre più veloce.

1075
00:59:17,440 --> 00:59:22,790
Ma forse stai sprecando un
molto spazio in questo modo, però.

1076
00:59:22,790 --> 00:59:26,320
Devi capirlo.

1077
00:59:26,320 --> 00:59:27,140
Mmhmm?

1078
00:59:27,140 --> 00:59:29,875
>> PUBBLICO: Lei ha detto prima che
siamo in grado di utilizzare altre funzioni di hash,

1079
00:59:29,875 --> 00:59:31,750
che non abbiamo a
creare una funzione di hash?

1080
00:59:31,750 --> 00:59:32,666
>> SPEAKER 1: Sì, giusto.

1081
00:59:32,666 --> 00:59:38,150
Così letteralmente per la vostra funzione di hash,
come google "funzione di hash"

1082
00:59:38,150 --> 00:59:40,770
e potete trovare alcuni tra quelli freddi.

1083
00:59:40,770 --> 00:59:43,250
Non si aspetta di costruire
le proprie funzioni di hash.

1084
00:59:43,250 --> 00:59:46,100
Le persone trascorrono la loro
tesi su queste cose.

1085
00:59:46,100 --> 00:59:50,250
>> Quindi non preoccuparti per costruire il proprio.

1086
00:59:50,250 --> 00:59:53,350
Trova uno on-line per iniziare.

1087
00:59:53,350 --> 00:59:56,120
Alcuni di loro si deve
manipolare un po '

1088
00:59:56,120 --> 00:59:59,430
per assicurarsi che i tipi restituiti corrispondono
e quant'altro, così in principio,

1089
00:59:59,430 --> 01:00:02,420
Ti consiglio di utilizzare qualcosa
molto semplice che forse solo

1090
01:00:02,420 --> 01:00:04,680
hash sulla prima lettera.

1091
01:00:04,680 --> 01:00:08,760
E poi una volta che hai questo lavoro,
incorpora una funzione di hash refrigerante.

1092
01:00:08,760 --> 01:00:09,260
Mmhmm?

1093
01:00:09,260 --> 01:00:13,020
>> PUBBLICO: Sarebbe una prova sia o
efficiente, ma solo più difficile da, like--

1094
01:00:13,020 --> 01:00:15,880
>> SPEAKER 1: Quindi una prova, credo,
è intuitivamente difficile da attuare

1095
01:00:15,880 --> 01:00:18,310
ma è molto veloce.

1096
01:00:18,310 --> 01:00:20,620
Tuttavia, occupa più spazio.

1097
01:00:20,620 --> 01:00:25,270
Anche in questo caso, è possibile ottimizzare sia di quelli in
modi diversi e ci sono modi a--

1098
01:00:25,270 --> 01:00:26,770
PUBBLICO: Come siamo graduata su questo?

1099
01:00:26,770 --> 01:00:27,540
Ha matter--

1100
01:00:27,540 --> 01:00:29,164
>> SPEAKER 1: Quindi sei classificati come di consueto.

1101
01:00:29,164 --> 01:00:31,330
Si sta andando ad essere classificato sul design.

1102
01:00:31,330 --> 01:00:36,020
Qualunque sia il tuo modo di fare, si vuole
assicurarsi che sia elegante come può essere

1103
01:00:36,020 --> 01:00:38,610
ed efficiente come può essere.

1104
01:00:38,610 --> 01:00:41,950
Ma se si sceglie una meta o hash
tavolo, finché funziona,

1105
01:00:41,950 --> 01:00:45,350
siamo felici di questo.

1106
01:00:45,350 --> 01:00:48,370
E se si usa qualcosa che gli hash
sulla prima lettera, va bene,

1107
01:00:48,370 --> 01:00:51,410
come forse come il design-saggio.

1108
01:00:51,410 --> 01:00:53,410
Stiamo raggiungendo anche la
punto in questo semester--

1109
01:00:53,410 --> 01:00:55,340
Non so se si
ragazzi noticed-- se siete

1110
01:00:55,340 --> 01:00:58,780
gradi pset declinano un po '
a causa del design e quant'altro,

1111
01:00:58,780 --> 01:00:59,900
che è perfettamente bene.

1112
01:00:59,900 --> 01:01:02,960
E 'sempre ad un punto in cui il
i programmi sono sempre più complicato.

1113
01:01:02,960 --> 01:01:04,830
Non ci sono più posti
si può migliorare.

1114
01:01:04,830 --> 01:01:06,370
>> Quindi è perfettamente normale.

1115
01:01:06,370 --> 01:01:08,810
Non è che sei
facendo peggio sul vostro pset.

1116
01:01:08,810 --> 01:01:11,885
E 'solo che ci stanno di più su di te ora.

1117
01:01:11,885 --> 01:01:13,732
Così tutti si sente.

1118
01:01:13,732 --> 01:01:14,940
Ho appena classificato tutti i vostri p-set.

1119
01:01:14,940 --> 01:01:16,490
So che tutti si sente esso.

1120
01:01:16,490 --> 01:01:19,600
>> Quindi non essere preoccupato per questo.

1121
01:01:19,600 --> 01:01:23,580
E se avete domande su
pset precedenti o modi per migliorare,

1122
01:01:23,580 --> 01:01:27,760
Cerco di commentare la specifica
luoghi, ma a volte è tardi

1123
01:01:27,760 --> 01:01:30,840
e mi stanco.

1124
01:01:30,840 --> 01:01:34,885
Ci sono altre cose
su strutture di dati?

1125
01:01:34,885 --> 01:01:37,510
Sono sicuro che voi ragazzi non lo fanno veramente
voglia di parlarne più,

1126
01:01:37,510 --> 01:01:42,650
ma se ci sono, sono felice di
andare su di loro, così come qualsiasi

1127
01:01:42,650 --> 01:01:45,580
dalla conferenza lo scorso
settimana o la settimana scorsa.

1128
01:01:45,580 --> 01:01:51,580
>> So che la settimana scorsa era tutto revisione, in modo da
possiamo aver saltato qualche recensione

1129
01:01:51,580 --> 01:01:54,190
da lezione.

1130
01:01:54,190 --> 01:01:58,230
Tutte le altre domande posso rispondere?

1131
01:01:58,230 --> 01:01:59,350
OK, va bene.

1132
01:01:59,350 --> 01:02:02,400
Beh, voi ragazzi uscire 15 minuti di anticipo.

1133
01:02:02,400 --> 01:02:08,370
>> Spero che questo era semi-utile, almeno,
e ci vediamo ragazzi la prossima settimana,

1134
01:02:08,370 --> 01:02:12,150
o giovedì l'orario d'ufficio.

1135
01:02:12,150 --> 01:02:15,285
Ci sono le richieste di snack
per la prossima settimana, è la cosa?

1136
01:02:15,285 --> 01:02:17,459
Perché ho dimenticato la caramella oggi.

1137
01:02:17,459 --> 01:02:19,750
E ho portato caramelle ultimo
settimana, ma era Columbus Day,

1138
01:02:19,750 --> 01:02:25,400
quindi non erano come sei persone che
aveva quattro sacchetti di caramelle a se stessi.

1139
01:02:25,400 --> 01:02:28,820
Posso portare Starbursts
ancora una volta, se volete.

1140
01:02:28,820 --> 01:02:29,580
Starbursts?

1141
01:02:29,580 --> 01:02:32,250
OK, suona bene.

1142
01:02:32,250 --> 01:02:35,050
Hanno un grande giorno, ragazzi.

1143
01:02:35,050 --> 01:02:39,510