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

2
00:00:03,423 --> 00:00:05,380

3
00:00:05,380 --> 00:00:08,210
>> ANDI PENG: Benvenuti a settimana 6 della sezione.

4
00:00:08,210 --> 00:00:11,620
Abbiamo deviato dalla nostro standard
ora sezione del Martedì

5
00:00:11,620 --> 00:00:14,130
pomeriggio per questa bella Domenica mattina.

6
00:00:14,130 --> 00:00:17,330
Grazie per tutti coloro che
mi ha raggiunto oggi, ma sul serio,

7
00:00:17,330 --> 00:00:18,170
un applauso.

8
00:00:18,170 --> 00:00:20,600
>> Questo è un bel grande sforzo.

9
00:00:20,600 --> 00:00:23,600
Io quasi non ho nemmeno rendono
in tempo, ma non era male.

10
00:00:23,600 --> 00:00:27,520
Quindi so che tutti voi
hanno appena fatto per il quiz.

11
00:00:27,520 --> 00:00:30,370
Prima di tutto, non esitare a
il rovescio della medaglia di questo.

12
00:00:30,370 --> 00:00:32,917
>> In secondo luogo, parleremo.

13
00:00:32,917 --> 00:00:34,000
Parleremo il quiz.

14
00:00:34,000 --> 00:00:35,700
Parleremo di come
si sta facendo nella classe.

15
00:00:35,700 --> 00:00:36,550
Starai bene.

16
00:00:36,550 --> 00:00:39,080
Ho tuoi quiz per
al termine di qui,

17
00:00:39,080 --> 00:00:42,120
quindi se voi volete prendere
un guardare, tutto bene.

18
00:00:42,120 --> 00:00:46,590
>> Così in fretta prima di cominciare, la
ordine del giorno per oggi è il seguente.

19
00:00:46,590 --> 00:00:48,430
Come potete vedere, siamo
fondamentalmente cottura rapida

20
00:00:48,430 --> 00:00:52,120
attraverso tutta una serie di strutture di dati
davvero, davvero, davvero in fretta.

21
00:00:52,120 --> 00:00:54,380
Quindi, come tale, non sarà
oggi super-interattivo.

22
00:00:54,380 --> 00:00:59,620
Sarà solo me tipo di gridare
cose che voi, e se ti confondo,

23
00:00:59,620 --> 00:01:02,680
se sto andando troppo veloce, fatemelo sapere.

24
00:01:02,680 --> 00:01:05,200
Sono solo i vari dati
strutture, e come parte

25
00:01:05,200 --> 00:01:07,070
del vostro pset per questo
prossima settimana, ti

26
00:01:07,070 --> 00:01:10,340
essere chiesto di attuare uno di loro,
forse due di them-- due di essi

27
00:01:10,340 --> 00:01:12,319
nel pset.

28
00:01:12,319 --> 00:01:14,610
Ok, quindi sto solo andando a
iniziare con alcuni annunci.

29
00:01:14,610 --> 00:01:19,070
Andremo su pile e code più in
profondità di quello che abbiamo fatto prima il quiz.

30
00:01:19,070 --> 00:01:20,990
Andremo oltre legati
elencare nuovamente, ancora una volta,

31
00:01:20,990 --> 00:01:23,899
più in profondità di quanto
abbiamo avuto prima il quiz.

32
00:01:23,899 --> 00:01:26,440
E poi parleremo di hash
tabelle, alberi e tentativi, che

33
00:01:26,440 --> 00:01:28,890
sono tutti abbastanza necessarie per la tua pset.

34
00:01:28,890 --> 00:01:32,925
E poi andremo su alcuni
suggerimenti utili per pset5.

35
00:01:32,925 --> 00:01:37,360
>> OK, quiz 0.

36
00:01:37,360 --> 00:01:41,090
La media era un 58%.

37
00:01:41,090 --> 00:01:45,370
E 'stato molto basso, e così voi ragazzi tutti
fatto molto, molto bene in conformità

38
00:01:45,370 --> 00:01:46,510
con quello.

39
00:01:46,510 --> 00:01:49,970
>> Praticamente, regola generale è che se siete
all'interno di una deviazione standard della media

40
00:01:49,970 --> 00:01:52,990
soprattutto perché siamo in un meno
sezione comodo, sei tutto bene.

41
00:01:52,990 --> 00:01:54,120
Siete sulla buona strada.

42
00:01:54,120 --> 00:01:55,190
La vita è bella.

43
00:01:55,190 --> 00:01:58,952
>> Lo so che è spaventoso pensare che
Ho avuto come un 40% su questo quiz.

44
00:01:58,952 --> 00:02:00,160
Sto andando a fallire questa classe.

45
00:02:00,160 --> 00:02:02,243
Vi prometto che, non sei
andando a fallire la classe.

46
00:02:02,243 --> 00:02:03,680
Sei totalmente bene.

47
00:02:03,680 --> 00:02:06,850
>> Per quelli di voi che ha ottenuto oltre
la media, impressionante, impressionante,

48
00:02:06,850 --> 00:02:08,780
come, seriamente ben fatto.

49
00:02:08,780 --> 00:02:09,689
Li ho con me.

50
00:02:09,689 --> 00:02:11,730
Sentitevi liberi di venire prenderli
alla fine della sezione.

51
00:02:11,730 --> 00:02:14,520
Fatemi sapere se avete qualsiasi
problemi, domande con loro.

52
00:02:14,520 --> 00:02:17,204
Se sommiamo il tuo punteggio
sbagliato, fateci sapere.

53
00:02:17,204 --> 00:02:21,240
>> OK, così pset5, questo è un davvero
Settimana strano per Yale nel senso

54
00:02:21,240 --> 00:02:24,240
che il nostro pset è dovuto
Mercoledì a mezzogiorno compreso

55
00:02:24,240 --> 00:02:27,317
la fine del giorno, quindi è in realtà
teoricamente dovuto Martedì a mezzogiorno.

56
00:02:27,317 --> 00:02:29,150
Probabilmente nessuno finito
a Martedì a mezzogiorno.

57
00:02:29,150 --> 00:02:30,830
Questo è totalmente bene.

58
00:02:30,830 --> 00:02:33,700
Stiamo per avere gli orari d'ufficio
stasera così come Lunedi notte.

59
00:02:33,700 --> 00:02:36,810
E tutte le sezioni di questa settimana sarà
effettivamente trasformate in officine,

60
00:02:36,810 --> 00:02:38,800
quindi sentitevi liberi di pop in
ogni sezione che si desidera,

61
00:02:38,800 --> 00:02:42,810
e saranno di tipo mini-pset
laboratori per aiuto su questo.

62
00:02:42,810 --> 00:02:45,620
Così come tale, questa è l'unica sezione
dove stiamo materiale didattico.

63
00:02:45,620 --> 00:02:49,220
Tutte le altre sezioni si concentreranno
esclusivamente sulla guida per la pset.

64
00:02:49,220 --> 00:02:50,146
Sì?

65
00:02:50,146 --> 00:02:52,000
>> PUBBLICO: Dove sono le ore di ufficio?

66
00:02:52,000 --> 00:02:56,120
>> ANDI PENG: Orario di ricevimento
tonight-- oh, bella domanda.

67
00:02:56,120 --> 00:03:00,580
Penso che le ore di ufficio stasera
sono in Teal oa Commons.

68
00:03:00,580 --> 00:03:02,984
Se si controlla in linea CS50
e si va in orario d'ufficio,

69
00:03:02,984 --> 00:03:05,650
ci dovrebbe essere un programma che
dove tutti sono dice.

70
00:03:05,650 --> 00:03:07,954
>> So che sia stasera
o domani è verde acqua,

71
00:03:07,954 --> 00:03:10,120
e penso che possiamo avere
comuni per l'altra sera.

72
00:03:10,120 --> 00:03:11,020
Non sono sicuro.

73
00:03:11,020 --> 00:03:11,700
Bella domanda.

74
00:03:11,700 --> 00:03:14,430
Controllare il CS50.

75
00:03:14,430 --> 00:03:18,780
>> Cool, qualsiasi domanda relativa al
pianificazione per il prossimo come tre giorni?

76
00:03:18,780 --> 00:03:21,690
Prometto voi ragazzi come David
ha detto, questa è la cima della collina.

77
00:03:21,690 --> 00:03:23,050
Voi ragazzi siete quasi arrivati.

78
00:03:23,050 --> 00:03:24,644
Solo tre più giorni.

79
00:03:24,644 --> 00:03:26,310
Arriviamo, e allora saremo tutti scesi.

80
00:03:26,310 --> 00:03:28,114
Avremo una piacevole pausa CS-libero.

81
00:03:28,114 --> 00:03:28,780
Torneremo.

82
00:03:28,780 --> 00:03:30,779
Ci immergeremo in web
programmazione e sviluppo,

83
00:03:30,779 --> 00:03:35,150
cose che sono molto divertenti a confronto
per alcune delle altre pset.

84
00:03:35,150 --> 00:03:37,974
E sarà freddo, e
avremo un sacco di divertimento.

85
00:03:37,974 --> 00:03:38,890
Avremo più caramelle.

86
00:03:38,890 --> 00:03:39,730
Ci scusiamo per caramelle.

87
00:03:39,730 --> 00:03:40,945
Ho dimenticato la caramella.

88
00:03:40,945 --> 00:03:43,310
Era una mattina di massima.

89
00:03:43,310 --> 00:03:46,340
Quindi voi siete quasi arrivati,
e sono davvero orgoglioso di voi ragazzi.

90
00:03:46,340 --> 00:03:49,570
>> OK, così pile.

91
00:03:49,570 --> 00:03:53,331
Che amava la domanda su Jack
e la sua veste sul quiz?

92
00:03:53,331 --> 00:03:53,830
Nessuno?

93
00:03:53,830 --> 00:03:56,500
Ok va bene.

94
00:03:56,500 --> 00:04:00,200
>> Quindi, in sostanza, come si può
foto Jack, questo ragazzo qui,

95
00:04:00,200 --> 00:04:03,350
ama prendere l'abbigliamento
fuori dalla sommità della pila,

96
00:04:03,350 --> 00:04:05,750
e la mette di nuovo sul
pila dopo che ha fatto.

97
00:04:05,750 --> 00:04:07,600
Quindi, in questo modo, non ha mai
sembra essere sempre

98
00:04:07,600 --> 00:04:10,090
al fondo del
impilare nel suo abbigliamento.

99
00:04:10,090 --> 00:04:12,600
Quindi questo tipo di descrive
la struttura di dati di base

100
00:04:12,600 --> 00:04:16,610
come uno stack è implementato.

101
00:04:16,610 --> 00:04:20,060
>> In sostanza, pensare ad una
impilare come ogni pila di oggetti

102
00:04:20,060 --> 00:04:24,900
dove si mettono le cose sulla parte superiore, e
poi si pop fuori dalla parte superiore.

103
00:04:24,900 --> 00:04:28,600
Così LIFO è l'acronimo che ci piace
a use-- Last In, First Out.

104
00:04:28,600 --> 00:04:32,480
E così durare nel all'inizio della
pila è il primo che esce.

105
00:04:32,480 --> 00:04:34,260
E così i due termini
ci piace associare

106
00:04:34,260 --> 00:04:36,190
con che sono chiamati spinta e pop.

107
00:04:36,190 --> 00:04:39,790
Quando si preme qualcosa sul
stack, e pop il backup.

108
00:04:39,790 --> 00:04:43,422
>> E quindi credo che questo è una specie di un
concetto astratto per quelli di voi

109
00:04:43,422 --> 00:04:45,630
che vogliono vedere come un
attuazione di questa

110
00:04:45,630 --> 00:04:46,740
nel mondo reale.

111
00:04:46,740 --> 00:04:50,170
Quanti di voi hanno scritto un saggio
forse come un'ora prima che fosse dovuto,

112
00:04:50,170 --> 00:04:54,510
e accidentalmente cancellato una enorme
pezzo di esso, come per caso?

113
00:04:54,510 --> 00:04:58,560
E allora cosa fare di controllo
che utilizziamo per rimetterlo?

114
00:04:58,560 --> 00:05:00,030
Control-Z, sì?

115
00:05:00,030 --> 00:05:03,640
Control-Z, quindi la quantità di volte
che Control-Z ha salvato la vita,

116
00:05:03,640 --> 00:05:08,820
ha salvato il culo, ogni volta
che è implementato attraverso un camino.

117
00:05:08,820 --> 00:05:13,020
>> Sostanzialmente tutte le informazioni
questo è il documento di Word,

118
00:05:13,020 --> 00:05:15,080
esso viene spinto e spuntato a volontà.

119
00:05:15,080 --> 00:05:19,460
E così in sostanza ogni volta che si
eliminare qualsiasi cosa, pop il backup.

120
00:05:19,460 --> 00:05:22,820
E poi, se avete bisogno di nuovo su, è
spingere, che è ciò che fa Control-C.

121
00:05:22,820 --> 00:05:26,770
E la funzione di mondo così reale
di come semplice struttura dei dati

122
00:05:26,770 --> 00:05:28,690
può aiutare con la vostra vita di tutti i giorni.

123
00:05:28,690 --> 00:05:31,710

124
00:05:31,710 --> 00:05:40,150
>> Quindi una struct è il modo in cui
abbiamo effettivamente creare uno stack.

125
00:05:40,150 --> 00:05:44,720
Noi scriviamo definire struct, e poi
la chiamiamo pila in fondo.

126
00:05:44,720 --> 00:05:47,440
E all'interno dello stack,
abbiamo due parametri

127
00:05:47,440 --> 00:05:51,580
che possiamo in sostanza manipolare,
così abbiamo char capacità stringhe stelle.

128
00:05:51,580 --> 00:05:55,150
>> Tutto ciò che sta facendo
è la creazione di un array

129
00:05:55,150 --> 00:05:58,835
che possiamo memorizzare quello che volete
che siamo in grado di determinarne la capacità.

130
00:05:58,835 --> 00:06:01,990
La capacità è solo l'importo massimo di
articoli che possono mettere in questo array.

131
00:06:01,990 --> 00:06:05,660
int size è il contatore che tiene
traccia di come molti elementi sono attualmente

132
00:06:05,660 --> 00:06:07,850
nella pila.

133
00:06:07,850 --> 00:06:11,860
Allora possiamo tenere traccia di, A,
sia quanto grande lo stack effettivo è,

134
00:06:11,860 --> 00:06:14,850
e, B, quanto di quella pila
abbiamo riempito perché non vogliamo

135
00:06:14,850 --> 00:06:18,800
traboccare su ciò che la nostra capacità è.

136
00:06:18,800 --> 00:06:24,340
>> Così, per esempio, questa bella
domanda era sul quiz.

137
00:06:24,340 --> 00:06:28,160
Essenzialmente come facciamo a spingere
sulla sommità di una pila.

138
00:06:28,160 --> 00:06:28,830
Abbastanza semplice.

139
00:06:28,830 --> 00:06:30,621
Se la si guarda,
cammineremo attraverso questo.

140
00:06:30,621 --> 00:06:32,640
Se [incomprensibile] size--
ricordare, ogni volta che si

141
00:06:32,640 --> 00:06:35,300
vuole accedere a qualsiasi
parametro all'interno di una struct,

142
00:06:35,300 --> 00:06:40,320
si fa il nome del struct.parameter.

143
00:06:40,320 --> 00:06:42,720
>> In questo caso, è s
il nome del nostro stack.

144
00:06:42,720 --> 00:06:46,230
Vogliamo accedere alle dimensioni
di esso, in modo da fare s.size.

145
00:06:46,230 --> 00:06:50,280
Quindi, fintanto che la dimensione non è
uguale capacità o il tempo

146
00:06:50,280 --> 00:06:52,940
come è inferiore alla capacità,
o avrebbe funzionato qui.

147
00:06:52,940 --> 00:06:57,180
>> Vuoi accedere all'interno
del tuo stack, così s.strings,

148
00:06:57,180 --> 00:07:00,790
e si sta andando a mettere quel nuovo numero
che si desidera inserire in là.

149
00:07:00,790 --> 00:07:05,030
Diciamo solo che vorremo
inserire int n nello stack,

150
00:07:05,030 --> 00:07:08,905
potremmo fare s.strings,
staffe, s.size uguale n.

151
00:07:08,905 --> 00:07:11,030
Perché la dimensione è dove siamo
Attualmente sono in pila

152
00:07:11,030 --> 00:07:14,590
se stiamo andando a spingere
su, abbiamo appena accediamo

153
00:07:14,590 --> 00:07:17,370
ove la dimensione è il
corrente pienezza della pila,

154
00:07:17,370 --> 00:07:21,729
e spingiamo la int n su di esso.

155
00:07:21,729 --> 00:07:24,770
E poi vogliamo fare in modo che
stiamo anche incrementando le dimensioni della n,

156
00:07:24,770 --> 00:07:27,436
in modo da poter tenere traccia di che abbiamo
aggiunto una cosa supplementare alla pila.

157
00:07:27,436 --> 00:07:29,660
Ora abbiamo una dimensione maggiore.

158
00:07:29,660 --> 00:07:33,196
Questo qui ha senso
tutti, come logicamente funziona?

159
00:07:33,196 --> 00:07:34,160
Era una specie di rapido.

160
00:07:34,160 --> 00:07:39,535

161
00:07:39,535 --> 00:07:42,160
PUBBLICO: Si può andare oltre
le s.stringss.strings [s.size] di nuovo?

162
00:07:42,160 --> 00:07:45,808
ANDI PENG: Certo, così che cosa fa
s.size attualmente ci danno?

163
00:07:45,808 --> 00:07:47,440
PUBBLICO: E 'la dimensione corrente.

164
00:07:47,440 --> 00:07:50,890
ANDI PENG: Esattamente, in modo che il
indice corrente che la nostra dimensione è a,

165
00:07:50,890 --> 00:07:57,780
e così vogliamo mettere il nuovo numero intero
che vogliamo inserire nel s.size.

166
00:07:57,780 --> 00:07:58,760
Questo fa senso?

167
00:07:58,760 --> 00:08:01,110
Poiché s.strings, tutto ciò che
è è il nome della matrice.

168
00:08:01,110 --> 00:08:03,510
Tutto ciò che è è l'accesso alla
matrice all'interno della nostra struct,

169
00:08:03,510 --> 00:08:06,030
e quindi se vogliamo
posizionare n in tale indice,

170
00:08:06,030 --> 00:08:09,651
possiamo semplicemente accedervi
utilizzando le staffe s.size.

171
00:08:09,651 --> 00:08:10,150
Raffreddare.

172
00:08:10,150 --> 00:08:13,580

173
00:08:13,580 --> 00:08:18,916
>> Va bene, pop, ho pseudocodice fuori
per voi ragazzi, ma concetto simile.

174
00:08:18,916 --> 00:08:19,790
Questo fa senso?

175
00:08:19,790 --> 00:08:22,310
Se la dimensione è maggiore
di zero, allora

176
00:08:22,310 --> 00:08:25,350
sai che si vuole prendere qualcosa
out perché se la dimensione non è

177
00:08:25,350 --> 00:08:27,620
maggiore di zero, allora
non hanno nulla in pila.

178
00:08:27,620 --> 00:08:29,840
>> Così si vuole solo eseguire
questo codice, si può solo

179
00:08:29,840 --> 00:08:32,320
pop se c'è qualcosa di pop.

180
00:08:32,320 --> 00:08:35,830
Quindi, se la dimensione è maggiore
di 0, abbiamo meno la dimensione.

181
00:08:35,830 --> 00:08:40,020
Abbiamo decrementa la dimensione e poi ritorniamo
tutto ciò che è dentro di essa, perché

182
00:08:40,020 --> 00:08:42,710
da popping, vogliamo
accesso tutto ciò che è memorizzato

183
00:08:42,710 --> 00:08:45,694
nell'indice della cima della pila.

184
00:08:45,694 --> 00:08:46,610
Tutto ha senso?

185
00:08:46,610 --> 00:08:49,693
Se ho fatto voi ragazzi scrivere questo fuori,
VUOI ragazzi in grado di scrivere fuori?

186
00:08:49,693 --> 00:08:52,029

187
00:08:52,029 --> 00:08:53,570
OK, voi potete giocare con esso.

188
00:08:53,570 --> 00:08:55,252
Non preoccuparti se non si capiscono.

189
00:08:55,252 --> 00:08:57,460
Non abbiamo il tempo di codice
oggi fuori perché abbiamo

190
00:08:57,460 --> 00:08:59,959
avuto un sacco di queste strutture
passare attraverso, ma essenzialmente

191
00:08:59,959 --> 00:09:02,214
pseudocodice, molto, molto simile a spingere.

192
00:09:02,214 --> 00:09:03,380
Basta seguire la logica.

193
00:09:03,380 --> 00:09:06,092
Assicurati di accedere a tutte le
caratteristiche del tuo struct correttamente.

194
00:09:06,092 --> 00:09:06,574
Sì?

195
00:09:06,574 --> 00:09:09,282
>> PUBBLICO: Will queste slide e
questa cosa sia oggi-ish?

196
00:09:09,282 --> 00:09:11,586
ANDI PENG: sempre, sì.

197
00:09:11,586 --> 00:09:13,710
Ho intenzione di provare a mettere
questo in su come un'ora dopo.

198
00:09:13,710 --> 00:09:16,626
Io invieremo un'email David, David cercherà di
metterlo come un'ora dopo.

199
00:09:16,626 --> 00:09:20,040

200
00:09:20,040 --> 00:09:25,470
>> OK, così poi ci spostiamo in questo altro
bella struttura di dati chiamata una coda.

201
00:09:25,470 --> 00:09:30,140
Come voi potete vedere qui, un
coda, per gli inglesi in mezzo a noi,

202
00:09:30,140 --> 00:09:32,010
tutto ciò che è è una linea.

203
00:09:32,010 --> 00:09:34,680
Quindi, contrariamente a quanto
si pensa che un stack è,

204
00:09:34,680 --> 00:09:37,750
una coda è esattamente quello
logicamente si pensa che è.

205
00:09:37,750 --> 00:09:41,914
Si tiene dalle regole del FIFO,
che è First In, First Out.

206
00:09:41,914 --> 00:09:43,705
Se sei il primo
uno nella linea, sei

207
00:09:43,705 --> 00:09:46,230
il primo che
esce dalla linea.

208
00:09:46,230 --> 00:09:49,680
>> Quindi quello che ci piace chiamare questo
è dequeueing e enqueueing.

209
00:09:49,680 --> 00:09:52,380
Se vogliamo aggiungere qualcosa
alla nostra coda, abbiamo enqueue.

210
00:09:52,380 --> 00:09:55,690
Se vogliamo dequeue, o prendere
via qualcosa, noi dequeue.

211
00:09:55,690 --> 00:10:03,350
>> Così lo stesso senso che siamo tipo di
la creazione di elementi di dimensione fissa che abbiamo

212
00:10:03,350 --> 00:10:06,500
in grado di memorizzare certa
cose, ma possiamo anche

213
00:10:06,500 --> 00:10:10,100
cambiare dove stiamo mettendo
parametri all'interno dei quali

214
00:10:10,100 --> 00:10:13,140
in base al tipo di
funzionalità che vogliamo.

215
00:10:13,140 --> 00:10:16,700
Così pile, abbiamo voluto l'ultimo
uno, N per essere il primo ad uscire.

216
00:10:16,700 --> 00:10:19,800
Coda è che vogliamo la prima cosa
per la prima cosa fuori.

217
00:10:19,800 --> 00:10:22,510

218
00:10:22,510 --> 00:10:26,710
>> Così il struct-tipo
definire, come si può vedere,

219
00:10:26,710 --> 00:10:29,470
è un po 'diverso
da ciò che la pila era

220
00:10:29,470 --> 00:10:33,120
perché non solo dobbiamo continuare
traccia di dove la dimensione è attualmente,

221
00:10:33,120 --> 00:10:37,420
vogliamo anche tenere traccia della testa
così come dove attualmente siamo.

222
00:10:37,420 --> 00:10:39,580
Quindi penso che sia più facile
se ne traggo questo.

223
00:10:39,580 --> 00:10:53,270
Quindi cerchiamo di immaginare abbiamo una coda,
quindi diciamo la testa è proprio qui.

224
00:10:53,270 --> 00:10:55,811

225
00:10:55,811 --> 00:10:58,310
Il capo della linea, andiamo
solo dire che è attualmente lì,

226
00:10:58,310 --> 00:11:01,809
e vogliamo inserire
qualcosa nella coda.

227
00:11:01,809 --> 00:11:04,350
Io vado a chiamare formato essenzialmente
è la stessa cosa di coda,

228
00:11:04,350 --> 00:11:06,314
alla fine della coda è ovunque il vostro.

229
00:11:06,314 --> 00:11:07,730
Diciamo solo che la dimensione è proprio qui.

230
00:11:07,730 --> 00:11:14,380

231
00:11:14,380 --> 00:11:18,400
>> Quindi, come si fa a tenerne
inserisci qualcosa in una coda?

232
00:11:18,400 --> 00:11:21,000

233
00:11:21,000 --> 00:11:24,130
Cosa indice vogliamo porre
dove vogliamo inserire in.

234
00:11:24,130 --> 00:11:29,320
Se questo è l'inizio della tua
coda e questa è la fine di esso

235
00:11:29,320 --> 00:11:31,860
o le dimensioni di esso, dove fare noi
vuole aggiungere l'oggetto successivo?

236
00:11:31,860 --> 00:11:32,920
>> PUBBLICO: [incomprensibile]

237
00:11:32,920 --> 00:11:35,920
ANDI PENG: Esattamente, si desidera aggiungere
esso a seconda che hai scritto.

238
00:11:35,920 --> 00:11:37,840
O questo è vuoto o che è vuoto.

239
00:11:37,840 --> 00:11:42,630
Così si vuole aggiungere che probabilmente
qui perché se la dimensione è--

240
00:11:42,630 --> 00:11:50,540
se questi sono tutti pieni, si vuole
per aggiungere proprio qui, giusto?

241
00:11:50,540 --> 00:11:57,150
>> E così che è, mentre molto, molto
semplice, non proprio sempre corretto

242
00:11:57,150 --> 00:12:00,690
perché la differenza principale
tra una coda e una pila

243
00:12:00,690 --> 00:12:04,350
è che la coda può
effettivamente essere manipolato

244
00:12:04,350 --> 00:12:06,980
modo che le modifiche testa
a seconda di dove si vuole

245
00:12:06,980 --> 00:12:08,650
l'inizio del vostro spunto per iniziare.

246
00:12:08,650 --> 00:12:11,900
E come risultato, la coda
sta anche andando a cambiare.

247
00:12:11,900 --> 00:12:14,770
E così dare un'occhiata a
questo codice al momento.

248
00:12:14,770 --> 00:12:18,620
Come voi ragazzi sono stati invitati a
scrivere sul quiz, enqueue.

249
00:12:18,620 --> 00:12:22,580
Magari ne parliamo perché attraverso
la risposta era quello che era.

250
00:12:22,580 --> 00:12:26,790
>> Io non riuscivo a montare questa linea su uno,
ma essenzialmente questo pezzo di codice

251
00:12:26,790 --> 00:12:29,030
dovrebbe essere su una riga.

252
00:12:29,030 --> 00:12:30,140
Spendere come 30 secondi.

253
00:12:30,140 --> 00:12:33,000
Date un'occhiata, e capire perché
questo è il modo in cui è.

254
00:12:33,000 --> 00:12:50,030

255
00:12:50,030 --> 00:12:55,420
>> Molto, struct molto simili, molto, molto
struttura simile alla precedente

256
00:12:55,420 --> 00:12:58,090
impilare tranne forse
una riga di codice.

257
00:12:58,090 --> 00:13:01,190
E che una riga di codice
determina la funzionalità.

258
00:13:01,190 --> 00:13:03,900
E si differenzia davvero
una coda da una pila.

259
00:13:03,900 --> 00:13:18,510

260
00:13:18,510 --> 00:13:22,010
>> Chiunque vuole prendere una pugnalata
di spiegare il motivo per cui hai

261
00:13:22,010 --> 00:13:24,980
ottenuto questa cosa complicata qui dentro?

262
00:13:24,980 --> 00:13:27,845
Vediamo il ritorno del nostro
amico meraviglioso modulo.

263
00:13:27,845 --> 00:13:31,020
Come voi ragazzi presto
riconoscere in programmazione,

264
00:13:31,020 --> 00:13:34,910
quasi in qualsiasi momento avete bisogno di qualcosa
per avvolgere qualsiasi cosa,

265
00:13:34,910 --> 00:13:36,850
modulo sarà il modo per farlo.

266
00:13:36,850 --> 00:13:40,510
Quindi, sapendo che, qualcuno vuole
provare spiegando che riga di codice?

267
00:13:40,510 --> 00:13:44,060

268
00:13:44,060 --> 00:13:47,507
Sì, tutte le risposte sono
accettato e di benvenuto.

269
00:13:47,507 --> 00:13:48,840
PUBBLICO: Stai parlando con me?

270
00:13:48,840 --> 00:13:49,506
ANDI PENG: Sì.

271
00:13:49,506 --> 00:13:56,200
PUBBLICO: Oh, non mi dispiace.

272
00:13:56,200 --> 00:14:00,250
ANDI PENG: OK, quindi cerchiamo di
camminare attraverso questo codice.

273
00:14:00,250 --> 00:14:03,642
Così, quando si sta cercando di
aggiungere qualcosa su una coda,

274
00:14:03,642 --> 00:14:08,510
nella deliziosa caso che la testa succede
di essere qui, è molto facile per noi

275
00:14:08,510 --> 00:14:10,960
andare solo alla fine
inserire qualcosa, giusto?

276
00:14:10,960 --> 00:14:14,690
Ma il punto centrale di una coda è
che la testa può effettivamente dinamicamente

277
00:14:14,690 --> 00:14:17,280
cambiare a seconda di dove ci
vuole l'inizio del nostro q di essere,

278
00:14:17,280 --> 00:14:19,880
e come tale, la coda
sta anche andando a cambiare.

279
00:14:19,880 --> 00:14:31,100
>> E quindi immaginare che questo non era il
coda, ma questo è stato coda.

280
00:14:31,100 --> 00:14:37,900

281
00:14:37,900 --> 00:14:39,330
Diciamo che la testa è proprio qui.

282
00:14:39,330 --> 00:14:54,900

283
00:14:54,900 --> 00:14:56,980
Diciamo che la nostra coda si presentava così.

284
00:14:56,980 --> 00:15:00,190
Se volessimo spostare dove
All'inizio della linea è,

285
00:15:00,190 --> 00:15:03,400
diciamo che abbiamo spostato testa
in questo modo e misure delle taglie Qui.

286
00:15:03,400 --> 00:15:07,100
>> Ora vogliamo aggiungere qualcosa a
questa coda, ma come voi potete vedere,

287
00:15:07,100 --> 00:15:11,150
non è così semplice da solo
aggiungere tutto ciò che è dopo la dimensione

288
00:15:11,150 --> 00:15:13,630
perché allora siamo a corto di
limiti della nostra gamma attuale.

289
00:15:13,630 --> 00:15:16,190
Dove vogliamo aggiungere davvero è qui.

290
00:15:16,190 --> 00:15:18,610
Questo è il bello di una coda
è che per noi, visivamente

291
00:15:18,610 --> 00:15:22,380
si presenta come la linea va come questo,
ma se conservato in una struttura di dati,

292
00:15:22,380 --> 00:15:29,370
danno come come un ciclo.

293
00:15:29,370 --> 00:15:32,360
E 'sorta di avvolge
al fronte stesso modo

294
00:15:32,360 --> 00:15:34,780
che una linea può anche avvolgere
intorno a seconda ovunque tu

295
00:15:34,780 --> 00:15:36,279
vogliono all'inizio della linea di essere.

296
00:15:36,279 --> 00:15:38,630
E quindi se prendiamo un
guardare in basso qui, diamo

297
00:15:38,630 --> 00:15:40,880
diciamo abbiamo voluto creare un
funzione chiamata enqueue.

298
00:15:40,880 --> 00:15:43,980
Abbiamo voluto aggiungere int n in quella q.

299
00:15:43,980 --> 00:15:49,250
Se q.size q-- chiameremo che i nostri dati
structure-- se il nostro queue.size non lo fa

300
00:15:49,250 --> 00:15:52,520
uguale capacità o se
è inferiore alla capacità,

301
00:15:52,520 --> 00:15:55,120
q.strings è la matrice all'interno della nostra q.

302
00:15:55,120 --> 00:15:58,380
Stiamo andando a impostare
che la parità di q.heads,

303
00:15:58,380 --> 00:16:02,730
che è proprio qui, più q.size
modulo dalla capacità che

304
00:16:02,730 --> 00:16:04,290
noi avvolgere di nuovo intorno qui.

305
00:16:04,290 --> 00:16:08,040
>> Quindi in questo esempio, l'indice
di testa è 1, giusto?

306
00:16:08,040 --> 00:16:11,480
L'indice di dimensione è 0, 1, 2, 3, 4.

307
00:16:11,480 --> 00:16:19,500
Così possiamo fare 1 più 4 modulo
dalla nostra capacità, che è 5.

308
00:16:19,500 --> 00:16:20,920
Che cosa ci danno?

309
00:16:20,920 --> 00:16:23,270
Che cosa è l'indice che
esce di questo?

310
00:16:23,270 --> 00:16:24,080
>> PUBBLICO: 0.

311
00:16:24,080 --> 00:16:27,870
>> ANDI PENG: 0, che
sembra essere proprio qui,

312
00:16:27,870 --> 00:16:30,640
e così noi vogliamo essere in grado
da inserire nel proprio qui.

313
00:16:30,640 --> 00:16:34,730
E così questa equazione qui genere
di opere solo con tutti i numeri

314
00:16:34,730 --> 00:16:36,750
a seconda di dove il tuo
testa e il formato sono.

315
00:16:36,750 --> 00:16:38,541
Se sai cosa quelli
le cose sono, sai

316
00:16:38,541 --> 00:16:43,170
esattamente dove si desidera inserire
tutto ciò che è dopo la vostra coda.

317
00:16:43,170 --> 00:16:44,640
Questo fa senso a tutti?

318
00:16:44,640 --> 00:16:48,560
>> So che tipo di un cervello
rompicapo soprattutto perché questo

319
00:16:48,560 --> 00:16:50,512
è venuto a seguito del quiz.

320
00:16:50,512 --> 00:16:52,220
Ma si spera tutti
ora può capire

321
00:16:52,220 --> 00:16:57,800
perché questa soluzione o questa
funzione è il modo in cui è.

322
00:16:57,800 --> 00:16:59,840
Chiunque un po 'poco chiaro su questo?

323
00:16:59,840 --> 00:17:03,471

324
00:17:03,471 --> 00:17:03,970
OK.

325
00:17:03,970 --> 00:17:07,109

326
00:17:07,109 --> 00:17:09,970
>> E così ora, se si
voluto dequeue, questo

327
00:17:09,970 --> 00:17:15,240
è dove la nostra testa sarebbe spostamento
perché se dovessimo dequeue,

328
00:17:15,240 --> 00:17:17,030
non prendiamo fuori alla fine del q.

329
00:17:17,030 --> 00:17:19,130
Vogliamo prendere la testa, giusto?

330
00:17:19,130 --> 00:17:24,260
Così come risultato, testa sta per cambiare,
ed è per questo che quando si enqueue,

331
00:17:24,260 --> 00:17:26,800
hai avuto modo di tenere traccia di
dove la testa e la tua taglia

332
00:17:26,800 --> 00:17:29,450
devono essere in grado di inserire
nella posizione corretta.

333
00:17:29,450 --> 00:17:32,740
>> E così quando si dequeue,
Ho anche pseudocodice fuori.

334
00:17:32,740 --> 00:17:35,480
Sentitevi liberi di se volete
per tentare di codifica questo fuori.

335
00:17:35,480 --> 00:17:36,980
Si desidera spostare la testa, giusto?

336
00:17:36,980 --> 00:17:39,320
Se volessi dequeue, io
sarebbe spostare la testa sopra.

337
00:17:39,320 --> 00:17:40,800
Questa sarebbe la testa.

338
00:17:40,800 --> 00:17:45,617
>> E il nostro dimensioni attuali sarebbe
sottrarre perché non siamo più

339
00:17:45,617 --> 00:17:46,950
avere quattro elementi dell'array.

340
00:17:46,950 --> 00:17:51,370
Abbiamo solo tre, e poi vogliamo
per tornare ciò che è stato memorizzato all'interno

341
00:17:51,370 --> 00:17:56,260
della testa perché vogliamo prendere questo
valore in modo molto simile alla pila.

342
00:17:56,260 --> 00:17:58,010
Appena si sta prendendo
da un posto diverso,

343
00:17:58,010 --> 00:18:01,770
e si deve riassegnare il puntatore
al posto differente come risultato.

344
00:18:01,770 --> 00:18:03,890
Logicamente, tutti seguire?

345
00:18:03,890 --> 00:18:05,690
Grande.

346
00:18:05,690 --> 00:18:10,156
>> Ok, quindi stiamo andando a parlare un po '
più in profondità su liste collegate

347
00:18:10,156 --> 00:18:13,280
perché sarà molto, molto prezioso
per voi nel corso di questa settimana di

348
00:18:13,280 --> 00:18:14,964
pset.

349
00:18:14,964 --> 00:18:17,130
Liste collegate, come voi ragazzi
può ricordare, tutto quello che sono

350
00:18:17,130 --> 00:18:22,570
sono nodi che sono i nodi di alcuni
valori sia un valore e un puntatore

351
00:18:22,570 --> 00:18:26,290
che sono collegati tra loro
da quei puntatori.

352
00:18:26,290 --> 00:18:29,880
E così la struct su come
creiamo un nodo qui è noi

353
00:18:29,880 --> 00:18:33,569
avere int n, che è tutto ciò che
il valore in un negozio o una stringa n

354
00:18:33,569 --> 00:18:35,610
o quello che volete
chiamarlo, il carattere stella n.

355
00:18:35,610 --> 00:18:41,482
Struct stella nodo, che è il puntatore
che si desidera avere in ogni nodo,

356
00:18:41,482 --> 00:18:43,690
si sta andando ad avere quel
punto puntatore verso il prossimo.

357
00:18:43,690 --> 00:18:48,207

358
00:18:48,207 --> 00:18:50,040
Avrete la testa
di una lista collegata che è

359
00:18:50,040 --> 00:18:53,140
andando a puntare al resto
i valori così via e così via

360
00:18:53,140 --> 00:18:55,290
fino a quando alla fine si raggiunge la fine.

361
00:18:55,290 --> 00:18:58,040
E questo ultimo nodo è solo
andando a non avere un puntatore.

362
00:18:58,040 --> 00:18:59,952
Sta andando a puntare a
nullo, e che quando

363
00:18:59,952 --> 00:19:01,910
sai che hai colpito il
fine della vostra lista collegata

364
00:19:01,910 --> 00:19:04,076
è quando il tuo ultimo puntatore
non punta a nulla.

365
00:19:04,076 --> 00:19:06,670

366
00:19:06,670 --> 00:19:10,990
>> Quindi stiamo per andare un po 'più a
profondità per quanto riguarda come si farebbe forse

367
00:19:10,990 --> 00:19:12,400
cercare una lista collegata.

368
00:19:12,400 --> 00:19:15,460
Ricordate che cosa sono alcuni dei
inconvenienti delle liste collegate

369
00:19:15,460 --> 00:19:19,340
versetti una matrice per quanto riguarda le ricerche.

370
00:19:19,340 --> 00:19:22,565
Un array è possibile ricerca binaria, ma
perché non si può fare che in una lista concatenata?

371
00:19:22,565 --> 00:19:26,834

372
00:19:26,834 --> 00:19:30,320
>> PUBBLICO: Perché sono tutti collegati,
ma non si sa bene dove

373
00:19:30,320 --> 00:19:31,330
[Incomprensibile].

374
00:19:31,330 --> 00:19:34,600
>> ANDI PENG: Sì, esattamente in modo da ricordare
che la brillantezza di un array

375
00:19:34,600 --> 00:19:37,190
era il fatto che abbiamo avuto
memoria ad accesso casuale in cui

376
00:19:37,190 --> 00:19:41,580
se volevo il valore dall'indice
sei, potrei solo dire indice di sei,

377
00:19:41,580 --> 00:19:42,407
dammi quel valore.

378
00:19:42,407 --> 00:19:45,240
E questo perché gli array sono ordinati
in uno spazio contiguo di memoria

379
00:19:45,240 --> 00:19:48,020
in un unico luogo, mentre
tipo di liste concatenate

380
00:19:48,020 --> 00:19:52,820
sono intervallati in modo casuale in tutto,
e l'unico modo è possibile trovare uno

381
00:19:52,820 --> 00:19:56,890
è attraverso un puntatore che ti dice
l'indirizzo di dove tale nodo successivo è.

382
00:19:56,890 --> 00:20:00,290
>> E così, come risultato, l'unico modo
per la ricerca in una lista concatenata

383
00:20:00,290 --> 00:20:01,560
è ricerca lineare.

384
00:20:01,560 --> 00:20:05,890
Perché io non so esattamente dove
il valore 12 nella lista collegata è,

385
00:20:05,890 --> 00:20:08,780
Devo attraversare la totalità
di quella lista collegata uno

386
00:20:08,780 --> 00:20:12,450
da uno dalla testa al primo nodo,
al secondo nodo, al terzo nodo,

387
00:20:12,450 --> 00:20:17,690
tutta la strada fino a quando ho finalmente
dove quel nodo che sto cercando è.

388
00:20:17,690 --> 00:20:22,110
E così, in questo senso, la ricerca
su una lista concatenata è sempre n.

389
00:20:22,110 --> 00:20:23,040
E 'sempre n.

390
00:20:23,040 --> 00:20:25,690
E 'sempre in tempo lineare.

391
00:20:25,690 --> 00:20:28,470
>> E così il codice in cui
attuiamo questo, e questo

392
00:20:28,470 --> 00:20:32,620
è un po 'nuova per voi ragazzi da voi
ragazzi non hanno davvero parlato o mai

393
00:20:32,620 --> 00:20:35,000
visto puntatori in come
la ricerca in puntatori,

394
00:20:35,000 --> 00:20:37,670
così noi cammineremo attraverso
questo molto, molto lentamente.

395
00:20:37,670 --> 00:20:40,200
Quindi ricerca bool, a destra,
immaginiamo che vogliamo

396
00:20:40,200 --> 00:20:42,820
per creare una funzione denominata
di ricerca che restituisce true

397
00:20:42,820 --> 00:20:46,820
se hai trovato un valore all'interno del collegato
elencare, e restituisce false altrimenti.

398
00:20:46,820 --> 00:20:50,030
Elenco dei nodi stella è
attualmente appena il puntatore

399
00:20:50,030 --> 00:20:52,960
al primo elemento nella lista collegata.

400
00:20:52,960 --> 00:20:56,700
int n è il valore che si sta
cercando in tale elenco.

401
00:20:56,700 --> 00:20:58,770
>> Così puntatore nodo stella uguale lista.

402
00:20:58,770 --> 00:21:00,970
Questo significa che stiamo impostando
e creando un puntatore

403
00:21:00,970 --> 00:21:03,592
a tale primo nodo all'interno della lista.

404
00:21:03,592 --> 00:21:04,300
Tutti con me?

405
00:21:04,300 --> 00:21:06,530
Quindi, se dovessimo andare
di nuovo qui, avrei

406
00:21:06,530 --> 00:21:13,850
inizializzato un puntatore che punta a
il capo di tutto ciò che tale elenco.

407
00:21:13,850 --> 00:21:18,600
>> E poi una volta arrivati ​​qui,
mentre il puntatore non è uguale nullo,

408
00:21:18,600 --> 00:21:22,160
così che è il ciclo in cui siamo
sta per essere successivamente attraversare

409
00:21:22,160 --> 00:21:25,940
il resto della nostra lista perché ciò che
succede quando il puntatore è uguale a zero?

410
00:21:25,940 --> 00:21:27,550
Sappiamo che have--

411
00:21:27,550 --> 00:21:28,450
>> PUBBLICO: [incomprensibile]

412
00:21:28,450 --> 00:21:31,491
>> ANDI PENG: Esattamente, quindi sappiamo che
abbiamo raggiunto la fine della lista, giusto?

413
00:21:31,491 --> 00:21:34,470
Se si va indietro qui, ogni nodo
dovrebbe essere che punta a un altro nodo

414
00:21:34,470 --> 00:21:36,550
E così via e così via
fino a colpire alla fine

415
00:21:36,550 --> 00:21:41,589
la coda della lista collegata,
che ha un puntatore che solo

416
00:21:41,589 --> 00:21:43,130
non punta ovunque a parte no.

417
00:21:43,130 --> 00:21:47,510
E in modo da sapere in sostanza che
la vostra lista vi è ancora in piedi

418
00:21:47,510 --> 00:21:50,900
fino a quando il puntatore non è uguale
nullo perché una volta che è uguale a zero,

419
00:21:50,900 --> 00:21:53,310
si sa che non c'è più roba.

420
00:21:53,310 --> 00:21:56,930
>> In modo che sia il ciclo in cui siamo
andando ad avere la ricerca vera e propria.

421
00:21:56,930 --> 00:22:01,690
E se i pointer-- Vedete
che tipo di funzione freccia lì?

422
00:22:01,690 --> 00:22:06,930
Quindi, se i punti di puntatore a n, se
il puntatore n è uguale uguale a n,

423
00:22:06,930 --> 00:22:09,180
in modo che significa che se
il puntatore che sei

424
00:22:09,180 --> 00:22:13,420
cercare sull'estremità di ciascun
nodo è effettivamente uguale al valore

425
00:22:13,420 --> 00:22:15,990
che stai cercando, quindi
si vuole restituire true.

426
00:22:15,990 --> 00:22:19,280
Quindi, fondamentalmente, se siete a un nodo che
ha il valore che si sta cercando,

427
00:22:19,280 --> 00:22:23,550
lo sai che sei stato
in grado di cercare con successo.

428
00:22:23,550 --> 00:22:27,150
>> In caso contrario, si desidera impostare
il puntatore al nodo successivo.

429
00:22:27,150 --> 00:22:28,850
Questo è ciò che la linea qui sta facendo.

430
00:22:28,850 --> 00:22:31,750
Puntatore uguale indicatore accanto.

431
00:22:31,750 --> 00:22:33,360
Vedere a tutti come che sta lavorando?

432
00:22:33,360 --> 00:22:36,580
>> E in sostanza, si sta andando a solo
attraversare la totalità della lista,

433
00:22:36,580 --> 00:22:41,920
reimpostare il puntatore ogni volta fino a
alla fine si colpisce la fine della lista.

434
00:22:41,920 --> 00:22:45,030
E si sa che non ci sono
più nodi per la ricerca attraverso,

435
00:22:45,030 --> 00:22:47,999
e poi si può tornare falso
perché si sa che, oh, beh,

436
00:22:47,999 --> 00:22:50,540
se sono stato in grado di cercare
attraverso la totalità della lista.

437
00:22:50,540 --> 00:22:54,530
Se in questo esempio, se volevo
per cercare il valore di 10,

438
00:22:54,530 --> 00:22:57,250
e mi metto in testa, e
Cerco fino in fondo,

439
00:22:57,250 --> 00:23:00,550
e alla fine ho avuto modo tale che
un puntatore che punta a null,

440
00:23:00,550 --> 00:23:04,415
So che, merda, credo che 10 non è in
questa lista perché non riuscivo a trovarlo.

441
00:23:04,415 --> 00:23:06,520
E io sono alla fine della lista.

442
00:23:06,520 --> 00:23:11,040
E in questo caso si sa
Ho intenzione di restituire false.

443
00:23:11,040 --> 00:23:12,900
>> Vediamo che in ammollo per un po '.

444
00:23:12,900 --> 00:23:17,350
Questo sarà piuttosto
importante per il vostro pset.

445
00:23:17,350 --> 00:23:21,140
La logica è molto semplice, forse
sintatticamente appena attuazione.

446
00:23:21,140 --> 00:23:23,365
Voi ragazzi vogliono fare
Assicurarsi di aver compreso.

447
00:23:23,365 --> 00:23:25,870

448
00:23:25,870 --> 00:23:27,650
Raffreddare.

449
00:23:27,650 --> 00:23:32,560
>> OK, così come ci sarebbe
l'inserimento di nodi, a destra,

450
00:23:32,560 --> 00:23:35,380
in un elenco, perché ricordare
quali sono le quali i vantaggi

451
00:23:35,380 --> 00:23:39,230
di avere una lista collegata contro
una matrice in termini di stoccaggio?

452
00:23:39,230 --> 00:23:41,110
>> PUBBLICO: E 'dinamica,
quindi è più facile a--

453
00:23:41,110 --> 00:23:43,180
>> ANDI PENG: Esattamente,
quindi è dinamico, che

454
00:23:43,180 --> 00:23:46,880
significa che può espandersi e contrarsi
a seconda delle esigenze dell'utente.

455
00:23:46,880 --> 00:23:56,570
E così, in questo senso, non abbiamo bisogno di
sprecare memoria inutile perché

456
00:23:56,570 --> 00:24:00,850
se non so quanti valori che voglio
a negozio, non ha senso per me

457
00:24:00,850 --> 00:24:04,310
per creare una matrice, poiché
se voglio memorizzare 10 valori

458
00:24:04,310 --> 00:24:08,380
e creo una serie di 1000, che è
un sacco di memoria sprecata, assegnato.

459
00:24:08,380 --> 00:24:11,180
Ecco perché vogliamo usare un collegato
lista per poter dinamicamente

460
00:24:11,180 --> 00:24:13,860
modificare o ridurre la nostra dimensione.

461
00:24:13,860 --> 00:24:17,040
>> E in modo che rende l'inserimento
un po 'più complicato.

462
00:24:17,040 --> 00:24:20,810
Dal momento che non possiamo accedere in modo casuale elementi
il modo in cui avremmo di un array.

463
00:24:20,810 --> 00:24:24,270
Se voglio inserire un elemento
nel settimo index,

464
00:24:24,270 --> 00:24:26,930
Ho appena può inserirla
nel settimo indice.

465
00:24:26,930 --> 00:24:30,020
Su una lista collegata, non è così
abbastanza lavorare con la stessa facilità,

466
00:24:30,020 --> 00:24:34,947
e quindi se volevamo inserire
quella qui nella lista collegata,

467
00:24:34,947 --> 00:24:36,280
visivamente, è molto facile da vedere.

468
00:24:36,280 --> 00:24:39,363
Vogliamo solo inserire proprio lì,
proprio all'inizio della lista,

469
00:24:39,363 --> 00:24:40,840
subito dopo la testa.

470
00:24:40,840 --> 00:24:44,579
>> Ma il modo in cui dobbiamo riassegnare
i puntatori è un po 'contorto

471
00:24:44,579 --> 00:24:47,620
o, logicamente, ha senso, ma
si vuole fare in modo che avete

472
00:24:47,620 --> 00:24:50,250
fino in fondo perché
l'ultima cosa che vuoi

473
00:24:50,250 --> 00:24:52,990
è quello di riassegnare un puntatore
modo in cui stiamo facendo qui.

474
00:24:52,990 --> 00:24:58,170
Se si dereference il
puntatore da capo a 1,

475
00:24:58,170 --> 00:25:01,086
poi tutto ad un tratto la
resto della vostra lista collegata

476
00:25:01,086 --> 00:25:04,680
è perso perché non avete realmente
ha creato un qualcosa di temporaneo.

477
00:25:04,680 --> 00:25:06,220
Questo è rilevato al 2.

478
00:25:06,220 --> 00:25:10,080
Se si riassegna il puntatore, allora la
resto della vostra lista è completamente persa.

479
00:25:10,080 --> 00:25:13,310
Così si vuole essere
molto, molto attenti qui

480
00:25:13,310 --> 00:25:17,010
per assegnare la prima
puntatore da tutto ciò che

481
00:25:17,010 --> 00:25:20,150
vogliono inserire nel ovunque
si vuole, e poi si

482
00:25:20,150 --> 00:25:22,710
possono dereference il resto della vostra lista.

483
00:25:22,710 --> 00:25:25,250
>> Quindi, questo vale per ovunque
si sta cercando di inserire nel.

484
00:25:25,250 --> 00:25:27,520
Se si desidera inserire al
testa, se si desidera rispondere qui,

485
00:25:27,520 --> 00:25:29,455
se si desidera inserire in
Alla fine, beh, alla fine ho

486
00:25:29,455 --> 00:25:30,910
Immagino che sarebbe solo
non hanno puntatore, ma voi

487
00:25:30,910 --> 00:25:33,830
vuole fare in modo che non si
perdere il resto della vostra lista.

488
00:25:33,830 --> 00:25:36,640
Si vuole sempre fare in modo
il vostro nuovo nodo punta

489
00:25:36,640 --> 00:25:39,330
verso tutto ciò che
vogliono inserire,

490
00:25:39,330 --> 00:25:42,170
e quindi è possibile aggiungere il concatenamento su.

491
00:25:42,170 --> 00:25:43,330
Tutti chiaro?

492
00:25:43,330 --> 00:25:45,427
>> Questo sta per essere
uno dei problemi reali.

493
00:25:45,427 --> 00:25:48,010
Una delle questioni più importanti
si sta andando ad avere sul vostro pset

494
00:25:48,010 --> 00:25:51,340
è che si sta andando a cercare di creare
una lista collegata e cose inserto

495
00:25:51,340 --> 00:25:53,340
ma poi solo perdere il
resto della vostra lista collegata.

496
00:25:53,340 --> 00:25:54,900
E si sta andando ad essere come, io
non so perché questo sta accadendo?

497
00:25:54,900 --> 00:25:58,040
Ed è un dolore di passare attraverso
e cercare tutti i puntatori.

498
00:25:58,040 --> 00:26:02,100
>> E vi garantisco su questo pset,
scrivere e disegnare questi nodi fuori

499
00:26:02,100 --> 00:26:03,344
sarà molto, molto utile.

500
00:26:03,344 --> 00:26:06,010
Così si può tenere completamente traccia
di dove tutti i vostri puntatori sono,

501
00:26:06,010 --> 00:26:08,540
cosa sta andando male,
in cui tutti i nodi sono,

502
00:26:08,540 --> 00:26:12,660
che cosa dovete fare per accedere o
inserire o eliminare o uno di essi.

503
00:26:12,660 --> 00:26:14,550
Tutti bene con quello?

504
00:26:14,550 --> 00:26:15,050
Raffreddare.

505
00:26:15,050 --> 00:26:19,300

506
00:26:19,300 --> 00:26:22,600
>> Quindi, se volessimo guardare il codice?

507
00:26:22,600 --> 00:26:24,470
Oh, non so se siamo
può vedere the-- OK, così

508
00:26:24,470 --> 00:26:27,940
in alto tutto ciò che è è una funzione
chiamato inserto dove vogliamo

509
00:26:27,940 --> 00:26:31,365
inserire int n alla lista linkata.

510
00:26:31,365 --> 00:26:32,740
Stiamo andando a camminare attraverso questo.

511
00:26:32,740 --> 00:26:34,770
E 'un sacco di codice, un sacco di nuova sintassi.

512
00:26:34,770 --> 00:26:36,220
Saremo OK.

513
00:26:36,220 --> 00:26:39,120
>> Così nella parte superiore, ogniqualvolta
vogliamo creare qualcosa di

514
00:26:39,120 --> 00:26:42,380
che cosa dobbiamo fare, soprattutto se si
vogliamo che non da memorizzare nello stack

515
00:26:42,380 --> 00:26:43,920
ma nel mucchio?

516
00:26:43,920 --> 00:26:45,460
Andiamo in un malloc, giusto?

517
00:26:45,460 --> 00:26:48,240
Quindi stiamo andando a creare un puntatore.

518
00:26:48,240 --> 00:26:52,074
Nodo, puntatore, nuove eguali
malloc la dimensione di un nodo

519
00:26:52,074 --> 00:26:53,740
perché vogliamo che il nodo da creare.

520
00:26:53,740 --> 00:26:56,720
Vogliamo la quantità di
memoria che un nodo riprende

521
00:26:56,720 --> 00:26:59,300
da assegnare per il
creazione del nuovo nodo.

522
00:26:59,300 --> 00:27:02,270
>> E poi andremo a controllare
vedere se le nuove uguali equivale a nulla.

523
00:27:02,270 --> 00:27:03,370
Ricordate ciò che abbiamo detto?

524
00:27:03,370 --> 00:27:06,470
Qualunque cosa tu malloc,
cosa deve sempre fare?

525
00:27:06,470 --> 00:27:09,490
Si deve sempre verificare
se questo è nullo.

526
00:27:09,490 --> 00:27:13,620
>> Per esempio, se il vostro operativo
sistema era completamente pieno,

527
00:27:13,620 --> 00:27:17,060
se non aveste più memoria a
tutto e si tenta di malloc,

528
00:27:17,060 --> 00:27:18,410
sarebbe restituire null per voi.

529
00:27:18,410 --> 00:27:21,094
E così, se si tenta di utilizzarlo
quando stava puntando a null,

530
00:27:21,094 --> 00:27:23,260
tu non hai intenzione di poter
per accedere a tali informazioni.

531
00:27:23,260 --> 00:27:27,010
E così, come tale, abbiamo voluto fare
Assicurarsi che ogni volta che si sta mallocing,

532
00:27:27,010 --> 00:27:30,500
sei sempre il controllo per vedere se
che la memoria dato a voi è nullo.

533
00:27:30,500 --> 00:27:33,670
E se non lo è, allora possiamo passare
con il resto del nostro codice.

534
00:27:33,670 --> 00:27:36,140
>> Quindi stiamo andando a
inizializzare il nuovo nodo.

535
00:27:36,140 --> 00:27:39,050
Stiamo andando a fare nuova n è uguale a n.

536
00:27:39,050 --> 00:27:42,390
E poi andremo a fare
set nuovo il puntatore sulla nuova

537
00:27:42,390 --> 00:27:46,900
a nulla perché in questo momento non lo facciamo
voglio niente per poter puntare a.

538
00:27:46,900 --> 00:27:48,755
Non abbiamo idea di dove
sta andando a mettere voi,

539
00:27:48,755 --> 00:27:50,630
e poi se vogliamo
inserirla in testa,

540
00:27:50,630 --> 00:27:53,820
allora possiamo riassegnare
il puntatore alla testa.

541
00:27:53,820 --> 00:27:58,530
Non tutti seguono la logica
di dove che sta succedendo?

542
00:27:58,530 --> 00:28:02,502
>> Tutto quello che stiamo facendo è la creazione di un nuovo
nodo, l'impostazione del puntatore a null,

543
00:28:02,502 --> 00:28:04,210
e poi riassegnare
alla testa se

544
00:28:04,210 --> 00:28:06,320
sappiamo che vogliamo inserirla in testa.

545
00:28:06,320 --> 00:28:09,420
E poi la testa sta per
puntare verso quel nuovo nodo.

546
00:28:09,420 --> 00:28:11,060
Tutti d'accordo con questo?

547
00:28:11,060 --> 00:28:12,380
>> Quindi è un processo in due fasi.

548
00:28:12,380 --> 00:28:14,760
Hai avuto modo di prima assegnazione
qualunque cosa si sta creando.

549
00:28:14,760 --> 00:28:18,260
Impostare che puntatore
riferimento, e poi si

550
00:28:18,260 --> 00:28:21,400
può tipo di dereference
il primo puntatore

551
00:28:21,400 --> 00:28:22,972
e puntarlo verso il nuovo nodo.

552
00:28:22,972 --> 00:28:25,680
Ovunque si vuole inserire,
che la logica sta per tenere vero.

553
00:28:25,680 --> 00:28:27,530
>> E 'un po' come l'assegnazione di
variabili temporanee.

554
00:28:27,530 --> 00:28:28,700
Ricordate, hai
per fare in modo che si

555
00:28:28,700 --> 00:28:30,346
non perdere le tracce di se si sta scambiando.

556
00:28:30,346 --> 00:28:33,470
Si vuole fare in modo di avere una
variabile temporanea quel tipo di conserva

557
00:28:33,470 --> 00:28:35,620
traccia di dove quella cosa
è memorizzato in modo che si

558
00:28:35,620 --> 00:28:41,190
non perdono alcun valore nel corso
di come fare in giro con esso.

559
00:28:41,190 --> 00:28:42,710
>> OK, il codice sarà qui.

560
00:28:42,710 --> 00:28:45,020
Voi ragazzi Date un'occhiata dopo la sezione.

561
00:28:45,020 --> 00:28:48,060
Sarà lì.

562
00:28:48,060 --> 00:28:50,280
>> Quindi credo che come fa
questo diverso se volevamo

563
00:28:50,280 --> 00:28:52,300
inserire nella metà o alla fine?

564
00:28:52,300 --> 00:28:57,892
Qualcuno ha un'idea di ciò che è la
pseudocodice come riferimento logico

565
00:28:57,892 --> 00:29:00,350
che noi prenderemmo se volevamo
per inserirlo nel mezzo?

566
00:29:00,350 --> 00:29:03,391
Quindi, se volessimo per inserirlo al
testa, tutto ciò che facciamo è creare un nuovo nodo.

567
00:29:03,391 --> 00:29:06,311
Abbiamo impostato il puntatore di quel
nuovo nodo per qualunque sia la testa,

568
00:29:06,311 --> 00:29:08,310
e poi abbiamo impostato la testa
per il nuovo nodo, giusto?

569
00:29:08,310 --> 00:29:11,560
Volendo inserire nel mezzo
della lista, che cosa dobbiamo fare?

570
00:29:11,560 --> 00:29:14,108

571
00:29:14,108 --> 00:29:16,110
>> PUBBLICO: Sarebbe ancora
essere un processo simile

572
00:29:16,110 --> 00:29:19,114
di come l'assegnazione di puntatore e
assegnando tale puntatore,

573
00:29:19,114 --> 00:29:20,530
ma avremmo dovuto trovare lì.

574
00:29:20,530 --> 00:29:23,560
>> ANDI PENG: Esattamente, così esattamente
lo stesso processo tranne voi

575
00:29:23,560 --> 00:29:27,820
devono individuare dove esattamente si
vuole che il nuovo puntatore per andare in,

576
00:29:27,820 --> 00:29:44,790
quindi se voglio inserire nel
al centro della collegata list-- OK,

577
00:29:44,790 --> 00:29:46,370
diciamo che è la nostra lista collegata.

578
00:29:46,370 --> 00:29:49,500
Se vogliamo inserire proprio qui,
stiamo andando a creare un nuovo nodo.

579
00:29:49,500 --> 00:29:50,520
Stiamo andando a malloc.

580
00:29:50,520 --> 00:29:52,220
Stiamo per creare un nuovo nodo.

581
00:29:52,220 --> 00:29:55,940
Stiamo per assegnare il
indicatore di questo nodo qui.

582
00:29:55,940 --> 00:29:58,335
>> Ma il problema che differisce
da cui la testa è

583
00:29:58,335 --> 00:30:00,490
è che noi sapevamo esattamente
dove la testa è.

584
00:30:00,490 --> 00:30:01,930
E 'stato proprio in occasione della prima, giusto?

585
00:30:01,930 --> 00:30:04,870
Ma qui dobbiamo tenere traccia
di dove stiamo inserendo in.

586
00:30:04,870 --> 00:30:07,930
Se stiamo inserendo la nostra
nodo qui, abbiamo

587
00:30:07,930 --> 00:30:12,270
per assicurarsi che il
precedente per questo nodo

588
00:30:12,270 --> 00:30:14,172
è quella che riassegna il puntatore.

589
00:30:14,172 --> 00:30:16,380
Allora dovete tipo di
tenere traccia delle due cose.

590
00:30:16,380 --> 00:30:19,420
Se si tiene traccia di dove questo
nodo attualmente sta inserendo in.

591
00:30:19,420 --> 00:30:23,280
Dovete anche tenere traccia di dove
il nodo precedente che si sta guardando

592
00:30:23,280 --> 00:30:24,340
è stato anche lì.

593
00:30:24,340 --> 00:30:25,830
Tutti bene con quello?

594
00:30:25,830 --> 00:30:26,500
OK.

595
00:30:26,500 --> 00:30:28,000
>> Che ne dite di inserire nella parte finale?

596
00:30:28,000 --> 00:30:34,220
Se volessi aggiungere che qui-- se volevo
aggiungere un nuovo nodo alla fine di un elenco,

597
00:30:34,220 --> 00:30:37,009
come potrei fare per fare che?

598
00:30:37,009 --> 00:30:39,300
PUBBLICO: Così attualmente, il
di ultimo indicava nulla.

599
00:30:39,300 --> 00:30:40,960
ANDI PENG: Sì.

600
00:30:40,960 --> 00:30:43,560
Esattamente, quindi questo uno
attualmente è puntato a conoscere,

601
00:30:43,560 --> 00:30:46,720
e quindi credo che, in questo senso, è
molto facile da aggiungere alla fine di un elenco.

602
00:30:46,720 --> 00:30:51,810
Tutto quello che dovete fare è impostare la
uguale a null e poi espandersi.

603
00:30:51,810 --> 00:30:53,070
Proprio lì, molto facile.

604
00:30:53,070 --> 00:30:53,960
Molto semplice.

605
00:30:53,960 --> 00:30:56,430
>> Molto simile al
testa, ma logicamente si

606
00:30:56,430 --> 00:30:59,690
vuole fare in modo che i passi
si prende in direzione di fare nulla di tutto questo,

607
00:30:59,690 --> 00:31:01,500
si sta seguendo.

608
00:31:01,500 --> 00:31:04,420
E 'molto facile, in mezzo
del codice, preso su su,

609
00:31:04,420 --> 00:31:05,671
oh, ho tanti puntatori.

610
00:31:05,671 --> 00:31:07,461
Io non so dove
niente sta indicando.

611
00:31:07,461 --> 00:31:09,170
Io non so nemmeno quale nodo sto.

612
00:31:09,170 --> 00:31:11,490
Cosa sta succedendo?

613
00:31:11,490 --> 00:31:13,620
>> Relax, calmati, prendere un respiro profondo.

614
00:31:13,620 --> 00:31:15,530
Disegna la tua lista collegata.

615
00:31:15,530 --> 00:31:18,800
Se dici, io so dove esattamente
Ho bisogno di inserire questo in

616
00:31:18,800 --> 00:31:22,970
e so esattamente come riassegnare la mia
puntatori, molto, molto più facile da immagine

617
00:31:22,970 --> 00:31:27,200
fuori-- molto, molto più facile da non
perdersi nei bug del codice.

618
00:31:27,200 --> 00:31:29,410
Tutti d'accordo con questo?

619
00:31:29,410 --> 00:31:31,380
OK.

620
00:31:31,380 --> 00:31:35,120
>> Quindi credo che un concetto che non abbiamo
davvero parlato prima d'ora,

621
00:31:35,120 --> 00:31:38,131
e credo che probabilmente
non si incontrano molto yet--

622
00:31:38,131 --> 00:31:40,880
è una specie di un concept-- avanzata
è che in realtà abbiamo un dato

623
00:31:40,880 --> 00:31:43,900
struttura chiamata una lista doppiamente concatenata.

624
00:31:43,900 --> 00:31:46,390
Così come voi potete vedere,
tutto quello che stiamo facendo è la creazione di

625
00:31:46,390 --> 00:31:50,400
un valore effettivo, un extra
puntatore su ciascuno dei nostri nodi

626
00:31:50,400 --> 00:31:52,660
che punti anche al nodo precedente.

627
00:31:52,660 --> 00:31:58,170
Quindi non solo abbiamo il nostro
nodi indicano quello successivo.

628
00:31:58,170 --> 00:32:01,430
Essi indicano anche alla precedente.

629
00:32:01,430 --> 00:32:04,310
Ho intenzione di ignorare questi due al momento.

630
00:32:04,310 --> 00:32:06,740
>> Allora avete una catena
che può muoversi in entrambe le direzioni,

631
00:32:06,740 --> 00:32:09,630
e quindi è un po 'più facile
a seguire logicamente lungo.

632
00:32:09,630 --> 00:32:11,896
Come qui, anziché
tenere traccia di, oh,

633
00:32:11,896 --> 00:32:14,520
devono sapere che questo nodo è
quello che ho da riassegnare,

634
00:32:14,520 --> 00:32:17,532
Posso solo andare qui e
basta tirare la precedente.

635
00:32:17,532 --> 00:32:19,490
Poi so esattamente dove
che è, e poi si

636
00:32:19,490 --> 00:32:21,130
non c'è bisogno di attraversare la
elementi della lista collegata.

637
00:32:21,130 --> 00:32:22,180
E 'un po' più facile.

638
00:32:22,180 --> 00:32:24,960
>> Ma, come tale, si dispone doppiamente
la quantità di puntatori,

639
00:32:24,960 --> 00:32:26,960
che è il doppio della quantità di memoria.

640
00:32:26,960 --> 00:32:28,950
E 'un sacco di puntatori per tenere traccia di.

641
00:32:28,950 --> 00:32:32,140
E 'un po' più complesso, ma è
un po 'più facile da usare a seconda

642
00:32:32,140 --> 00:32:34,080
su ciò che si sta cercando di realizzare.

643
00:32:34,080 --> 00:32:36,910
>> Quindi questo tipo di dati
struttura totalmente esiste,

644
00:32:36,910 --> 00:32:40,280
e la struttura per è molto, molto
semplice salvo tutto quello che stai avendo è,

645
00:32:40,280 --> 00:32:43,850
invece di un puntatore successivo,
anche voi avete un puntatore al precedente.

646
00:32:43,850 --> 00:32:45,940
Questa è la differenza era.

647
00:32:45,940 --> 00:32:47,740
Tutti bene con quello?

648
00:32:47,740 --> 00:32:48,240
Raffreddare.

649
00:32:48,240 --> 00:32:50,940

650
00:32:50,940 --> 00:32:53,280
>> Va bene, ora sto
di spendere davvero probabilmente

651
00:32:53,280 --> 00:32:56,870
come 15 a 20 minuti o il bulk
il resto del tempo in sezione

652
00:32:56,870 --> 00:32:58,360
parlare di tabelle hash.

653
00:32:58,360 --> 00:33:02,590
Quanti di voi ragazzi
hanno letto pset5 specifiche?

654
00:33:02,590 --> 00:33:03,620
Va bene, bene.

655
00:33:03,620 --> 00:33:06,160
Questo è superiore al 50% del normale.

656
00:33:06,160 --> 00:33:07,560
Va bene.

657
00:33:07,560 --> 00:33:10,345
>> Così come voi ragazzi vedere,
siete sfida in pset5

658
00:33:10,345 --> 00:33:16,790
sarà quello di implementare un dizionario
dove si caricano oltre 140.000 parole

659
00:33:16,790 --> 00:33:20,610
che vi diamo e controllo ortografico
contro tutto il testo.

660
00:33:20,610 --> 00:33:22,580
Ti daremo casuale
pezzi di letteratura.

661
00:33:22,580 --> 00:33:23,520
Ti daremo l'Odissea.

662
00:33:23,520 --> 00:33:24,561
Ti daremo l'Iliade.

663
00:33:24,561 --> 00:33:26,350
Ti daremo Austin Powers.

664
00:33:26,350 --> 00:33:28,220
>> E la tua sfida
sarà per il controllo ortografico

665
00:33:28,220 --> 00:33:31,760
ogni singola parola in tutta la
di tali dizionari

666
00:33:31,760 --> 00:33:34,960
essenzialmente con il nostro correttore ortografico.

667
00:33:34,960 --> 00:33:38,620
E così ci sono alcune parti
della creazione di questo pset,

668
00:33:38,620 --> 00:33:41,970
prima si vuole essere
in grado di caricare effettivamente

669
00:33:41,970 --> 00:33:43,970
tutte le parole nel vostro
dizionario, e poi si

670
00:33:43,970 --> 00:33:45,530
vogliono poter
controllo ortografico tutti loro.

671
00:33:45,530 --> 00:33:48,780
E così, come tale, si sta andando a richiedere
una struttura di dati che può fare questo veloce

672
00:33:48,780 --> 00:33:50,790
ed efficiente e dinamicamente.

673
00:33:50,790 --> 00:33:52,900
>> Quindi suppongo che il più facile
modo per fare questo, è

674
00:33:52,900 --> 00:33:55,010
probabilmente creare un array, giusto?

675
00:33:55,010 --> 00:33:58,910
Il modo più semplice di archiviazione è voi
in grado di creare una serie di 140.000 parole

676
00:33:58,910 --> 00:34:03,400
e appena li posto lì e
poi attraversare dalla ricerca binaria

677
00:34:03,400 --> 00:34:06,780
o dalle selezioni o not--
mi dispiace che è l'ordinamento.

678
00:34:06,780 --> 00:34:10,729
È possibile ordinare loro e poi li attraversare
per ricerca binaria o la ricerca semplicemente lineare

679
00:34:10,729 --> 00:34:13,730
e appena finali le parole, ma che
prende un enorme quantità di memoria,

680
00:34:13,730 --> 00:34:15,190
e non è molto efficiente.

681
00:34:15,190 --> 00:34:18,350
>> E così stiamo per iniziare
parlando di modi di fare

682
00:34:18,350 --> 00:34:20,110
il nostro tempo di esecuzione più efficiente.

683
00:34:20,110 --> 00:34:23,190
E il nostro obiettivo è quello di ottenere
costante di tempo in cui

684
00:34:23,190 --> 00:34:25,810
è quasi come gli array, dove
si ha accesso istantaneo.

685
00:34:25,810 --> 00:34:28,560
Se volessi cercare qualsiasi cosa,
Voglio essere in grado di solo,

686
00:34:28,560 --> 00:34:30,810
asta, trovo esattamente, ed estrarlo.

687
00:34:30,810 --> 00:34:34,100
E così una struttura in cui
saremo diventando molto vicino

688
00:34:34,100 --> 00:34:37,569
per poter accedere costanti
tempo, questo Santo Graal

689
00:34:37,569 --> 00:34:41,370
in programmazione costante
tempo è chiamato una tabella hash.

690
00:34:41,370 --> 00:34:45,370
E così Davide accennato in precedenza il
[Incomprensibile] un po 'a lezione,

691
00:34:45,370 --> 00:34:49,100
ma stiamo andando a davvero
tuffo nel profondo di questa settimana

692
00:34:49,100 --> 00:34:51,780
su un pezzo che è per quanto riguarda
come una tabella hash funziona.

693
00:34:51,780 --> 00:34:53,949
>> Quindi il modo che un hash
opere tavola, per esempio,

694
00:34:53,949 --> 00:35:00,230
se volessi memorizzare un mucchio di parole, un
mucchio di parole in lingua inglese,

695
00:35:00,230 --> 00:35:02,940
Potrei teoricamente mettere
banana, mela, kiwi, mango, coppia,

696
00:35:02,940 --> 00:35:04,980
e melone tutto solo su un array.

697
00:35:04,980 --> 00:35:07,044
Tutti potevano adattarsi ed essere trovare.

698
00:35:07,044 --> 00:35:09,210
Sarebbe una specie di dolore per
la ricerca in e di accesso,

699
00:35:09,210 --> 00:35:12,920
ma il modo più semplice per farlo è
che possiamo creare effettivamente una struttura

700
00:35:12,920 --> 00:35:15,680
chiamato una tabella hash dove hash.

701
00:35:15,680 --> 00:35:19,880
Noi usiamo tutti i nostri chiavi attraverso
una funzione hash, un'equazione,

702
00:35:19,880 --> 00:35:22,600
che li trasforma in
una sorta di un valore

703
00:35:22,600 --> 00:35:28,740
che allora possiamo memorizzare su
essenzialmente un array di lista collegata.

704
00:35:28,740 --> 00:35:32,570
>> Ed ecco, se abbiamo voluto
per memorizzare le parole inglesi,

705
00:35:32,570 --> 00:35:37,250
potremmo potenzialmente semplicemente, non lo faccio
conoscere, girare tutte le prime lettere

706
00:35:37,250 --> 00:35:39,630
in una sorta di un numero.

707
00:35:39,630 --> 00:35:43,140
E così, per esempio, se volevo
Una di essere sinonimo di apple--

708
00:35:43,140 --> 00:35:47,460
o con l'indice di 0, e
B per essere sinonimo di 1,

709
00:35:47,460 --> 00:35:51,030
possiamo avere 26 iscrizioni
che può solo memorizzare

710
00:35:51,030 --> 00:35:53,610
tutte le lettere del
alfabeto che inizieremo con.

711
00:35:53,610 --> 00:35:56,130
E allora possiamo avere
mela l'indice di 0.

712
00:35:56,130 --> 00:35:59,160
Possiamo avere banana l'indice
1, melone all'indice di 2,

713
00:35:59,160 --> 00:36:00,540
E così via e così via.

714
00:36:00,540 --> 00:36:04,460
E così se volevo cercare
il mio hash tavolo e accesso mela,

715
00:36:04,460 --> 00:36:07,560
So mela inizia con
una A, e so esattamente

716
00:36:07,560 --> 00:36:10,860
che deve essere e l'hash
tavolo indice 0 perché

717
00:36:10,860 --> 00:36:13,620
della funzione precedentemente assegnato.

718
00:36:13,620 --> 00:36:16,572
>> Quindi io non lo so, siamo
un programma utente in cui

719
00:36:16,572 --> 00:36:18,780
ti verrà addebitato con
arbitrarily-- non arbitrariamente,

720
00:36:18,780 --> 00:36:22,530
con il tentativo di pensieroso
pensare di buone equazioni

721
00:36:22,530 --> 00:36:25,460
essere in grado di diffondersi
tutti i tuoi valori

722
00:36:25,460 --> 00:36:29,370
in modo che possano facilmente accedere
in un secondo momento con come un'equazione

723
00:36:29,370 --> 00:36:31,130
che voi, voi stessi, so.

724
00:36:31,130 --> 00:36:35,210
Così, nel senso se volevo andare a
mango, lo so, oh, si inizia con m.

725
00:36:35,210 --> 00:36:37,134
Deve essere in corrispondenza dell'indice di 12.

726
00:36:37,134 --> 00:36:38,800
Non ho per la ricerca in qualsiasi cosa.

727
00:36:38,800 --> 00:36:42,080
So exactly-- ho potuto solo andare a
l'indice di 12 e tirare che fuori.

728
00:36:42,080 --> 00:36:45,520
>> Tutti chiare su come una
La funzione di tabella di hash funziona?

729
00:36:45,520 --> 00:36:48,380
E 'una specie di solo una matrice più complessa.

730
00:36:48,380 --> 00:36:50,010
Questo è tutto ciò che è.

731
00:36:50,010 --> 00:36:51,630
OK.

732
00:36:51,630 --> 00:36:57,690
>> Quindi credo che ci imbattiamo in
la questione di ciò che

733
00:36:57,690 --> 00:37:06,390
succede se si dispone di più le cose
che ti danno lo stesso indice?

734
00:37:06,390 --> 00:37:10,570
Quindi dire la nostra funzione, tutto ciò che
fatto è stato prendere quella prima lettera

735
00:37:10,570 --> 00:37:14,490
e trasformarla in un
rispettivi 0 a 25 indice.

736
00:37:14,490 --> 00:37:17,137
Che è totalmente bene se
hai solo uno di ciascuno.

737
00:37:17,137 --> 00:37:18,970
Ma la seconda si avvia
avendo più, sei

738
00:37:18,970 --> 00:37:20,910
andando ad avere quella che viene chiamata una collisione.

739
00:37:20,910 --> 00:37:25,580
>> Quindi, se provo ad inserire seppellire in un hash
tabella che ha già banane su di esso,

740
00:37:25,580 --> 00:37:27,870
cosa succederà quando
si tenta di inserire questo?

741
00:37:27,870 --> 00:37:30,930
Cose cattive perché banane
esiste già all'interno dell'indice

742
00:37:30,930 --> 00:37:33,800
che si desidera memorizzare in.

743
00:37:33,800 --> 00:37:35,560
Berry tipo di è come, ah, cosa devo fare?

744
00:37:35,560 --> 00:37:37,080
Io non so dove andare.

745
00:37:37,080 --> 00:37:38,410
Come posso risolvere questo?

746
00:37:38,410 --> 00:37:41,150
>> E così voi ragazzi sarà di tipo
vediamo facciamo questa cosa difficile

747
00:37:41,150 --> 00:37:44,810
dove possiamo tipo di realtà
creare lista collegata nel nostro array.

748
00:37:44,810 --> 00:37:46,840
E così il modo più semplice
a pensare a questo,

749
00:37:46,840 --> 00:37:50,830
tutto tabella hash è un
array di liste concatenate.

750
00:37:50,830 --> 00:37:55,670
E così, in questo senso, è necessario
questa bella serie di puntatori,

751
00:37:55,670 --> 00:37:58,740
e poi ogni puntatore in
tale valore, in tale indice,

752
00:37:58,740 --> 00:38:00,740
può effettivamente puntare ad altre cose.

753
00:38:00,740 --> 00:38:05,720
E in modo da avere tutte queste separata
catene venuta fuori di una grande matrice.

754
00:38:05,720 --> 00:38:07,960
>> Ed ecco, se io
ha voluto inserire bacca,

755
00:38:07,960 --> 00:38:11,220
Lo so, va bene, ho intenzione di ingresso
attraverso la mia funzione di hash.

756
00:38:11,220 --> 00:38:15,070
Io vado a finire con l'indice
1, e poi ho intenzione di essere in grado di avere

757
00:38:15,070 --> 00:38:20,410
solo un sottoinsieme più piccolo di questo
gigante dizionario 140.000 parola.

758
00:38:20,410 --> 00:38:24,220
E poi posso solo guardare
attraverso 1/26 di quello.

759
00:38:24,220 --> 00:38:27,910
>> E così poi posso basta inserire
bacca, prima o dopo la banana

760
00:38:27,910 --> 00:38:28,820
in questo caso?

761
00:38:28,820 --> 00:38:29,700
Dopo, giusto?

762
00:38:29,700 --> 00:38:33,920
E così si sta andando a voler
inserire questo nodo dopo la banana,

763
00:38:33,920 --> 00:38:36,667
e così si sta andando ad inserire
in coda che lista collegata.

764
00:38:36,667 --> 00:38:38,500
Ho intenzione di tornare indietro
a questa diapositiva precedente,

765
00:38:38,500 --> 00:38:40,680
così voi potete vedere come
funzione hash funziona.

766
00:38:40,680 --> 00:38:43,980
>> Quindi funzione hash è questa equazione
che si sta eseguendo tipo di vostro input

767
00:38:43,980 --> 00:38:46,940
attraverso per ottenere qualunque indice
si vuole assegnare verso.

768
00:38:46,940 --> 00:38:51,130
E così, in questo esempio, tutti volevamo
fare era prendere la prima lettera,

769
00:38:51,130 --> 00:38:55,890
trasformarla in un indice, poi siamo
in grado di memorizzare che nella nostra funzione di hash.

770
00:38:55,890 --> 00:39:00,160
Tutto quello che stiamo facendo qui è che siamo
convertire la prima lettera.

771
00:39:00,160 --> 00:39:04,770
Così KeyKey [0] è solo la prima lettera
di qualsiasi stringa che stiamo avendo,

772
00:39:04,770 --> 00:39:05,720
stiamo passando.

773
00:39:05,720 --> 00:39:09,740
Stiamo convertendo che a superiore, e
stiamo sottraendo dalla A maiuscola,

774
00:39:09,740 --> 00:39:11,740
perciò tutto quello che sta facendo
ci sta dando un numero

775
00:39:11,740 --> 00:39:13,670
in cui possiamo hash nostri valori su.

776
00:39:13,670 --> 00:39:16,550
>> E poi andremo a
tornare hash modulo SIZE.

777
00:39:16,550 --> 00:39:19,340
Essere molto, molto attenti
perché, in teoria, qui

778
00:39:19,340 --> 00:39:21,870
il vostro valore di hash potrebbe essere infinita.

779
00:39:21,870 --> 00:39:23,660
Si potrebbe semplicemente andare avanti e avanti e avanti.

780
00:39:23,660 --> 00:39:26,080
Potrebbe essere qualche davvero,
davvero grande valore,

781
00:39:26,080 --> 00:39:29,849
ma perché la vostra tabella di hash che
hai creato ha solo 26 indici,

782
00:39:29,849 --> 00:39:31,890
si vuole assicurarsi che il proprio
modulusing modo che si

783
00:39:31,890 --> 00:39:33,848
non run-- è la stessa
cosa come il vostro queue--

784
00:39:33,848 --> 00:39:36,320
in modo che non si esegue fuori
fondo della vostra funzione di hash.

785
00:39:36,320 --> 00:39:39,210
>> Si vuole avvolgere indietro intorno
allo stesso modo in [incomprensibile] quando

786
00:39:39,210 --> 00:39:41,750
hai avuto come un molto,
molto grande lettera,

787
00:39:41,750 --> 00:39:43,740
non ha voluto che a
appena scappare alla fine.

788
00:39:43,740 --> 00:39:46,948
Stessa cosa qui, si vuole fare in modo
non scappare alla fine avvolgendo

789
00:39:46,948 --> 00:39:48,330
intorno alla parte superiore della tabella.

790
00:39:48,330 --> 00:39:50,530
Quindi questo è solo un molto
semplice funzione di hash.

791
00:39:50,530 --> 00:39:56,570
Tutto ciò che ha fatto è stato prendere la prima
lettera di qualunque sia il nostro ingresso era

792
00:39:56,570 --> 00:40:01,660
e trasformarla in un indice che
potremmo mettere nella nostra tabella di hash.

793
00:40:01,660 --> 00:40:05,450
>> Gia ', e così come ho detto prima,
il modo in cui risolvere le collisioni

794
00:40:05,450 --> 00:40:09,330
nel nostro hash tabelle stanno avendo,
ciò che chiamiamo, concatenamento.

795
00:40:09,330 --> 00:40:13,860
Quindi, se si tenta di inserire più
parole che iniziano con la stessa cosa,

796
00:40:13,860 --> 00:40:16,145
si sta andando ad avere un valore di hash.

797
00:40:16,145 --> 00:40:18,770
Avocado e mele, se hai
eseguirlo tramite il nostro funzione di hash,

798
00:40:18,770 --> 00:40:21,450
stanno per dare il
stesso numero, il numero di 0.

799
00:40:21,450 --> 00:40:24,550
E così il nostro modo di risolvere cioè
che possiamo effettivamente tipo di collegarli

800
00:40:24,550 --> 00:40:27,010
insieme attraverso liste collegate.

801
00:40:27,010 --> 00:40:29,600
>> E così in questo senso,
voi potete vedere tipo

802
00:40:29,600 --> 00:40:32,640
di come le strutture di dati che
abbiamo impostazione precedentemente

803
00:40:32,640 --> 00:40:35,870
come un passito collegato lista genere
di può venire insieme in un unico.

804
00:40:35,870 --> 00:40:38,860
E allora si può creare lontano
strutture dati più efficienti

805
00:40:38,860 --> 00:40:43,350
in grado di gestire grandi quantità di
i dati, che ridimensionare in modo dinamico a seconda

806
00:40:43,350 --> 00:40:44,870
alle vostre esigenze.

807
00:40:44,870 --> 00:40:45,620
Tutti chiaro?

808
00:40:45,620 --> 00:40:47,580
Tutti i tipi di chiara
su quello che succede qui?

809
00:40:47,580 --> 00:40:52,110
>> Se volevo insert-- ciò che è un
frutto che inizia con, non lo so,

810
00:40:52,110 --> 00:40:54,726
B, diversi da bacca, banana.

811
00:40:54,726 --> 00:40:55,710
>> PUBBLICO: Blackberry.

812
00:40:55,710 --> 00:40:57,910
>> ANDI PENG: Mora, mora.

813
00:40:57,910 --> 00:41:00,530
Da dove viene mora va qui?

814
00:41:00,530 --> 00:41:04,251
Beh, in realtà non abbiamo ordinato
questo ancora, ma in teoria

815
00:41:04,251 --> 00:41:06,250
se volevamo avere questo
in ordine alfabetico,

816
00:41:06,250 --> 00:41:07,944
dove dovrebbe andare mora?

817
00:41:07,944 --> 00:41:09,210
>> PUBBLICO: [incomprensibile]

818
00:41:09,210 --> 00:41:11,100
>> ANDI PENG: Esattamente, dopo qui, giusto?

819
00:41:11,100 --> 00:41:14,950
Ma dal momento che è molto difficile
reorder-- Credo che tocca a voi ragazzi.

820
00:41:14,950 --> 00:41:17,920
Voi ragazzi può totalmente
implementa quello che vuoi.

821
00:41:17,920 --> 00:41:20,730
Il modo più efficiente
di fare questo forse

822
00:41:20,730 --> 00:41:24,570
sarebbe quella di ordinare la vostra collegato
elencare in ordine alfabetico,

823
00:41:24,570 --> 00:41:26,520
e così quando sei
l'inserimento di cose, si vuole

824
00:41:26,520 --> 00:41:28,632
per essere sicuri di inserirli
in ordine alfabetico

825
00:41:28,632 --> 00:41:30,590
in modo che poi quando sei
cercando di loro la ricerca,

826
00:41:30,590 --> 00:41:32,410
non c'è bisogno di attraversare tutto.

827
00:41:32,410 --> 00:41:35,290
Si sa esattamente dove
è, ed è più facile.

828
00:41:35,290 --> 00:41:39,100
>> Ma se avete tipo di
cose intervallati in modo casuale,

829
00:41:39,100 --> 00:41:41,420
si sta ancora andando ad avere
per attraversare comunque.

830
00:41:41,420 --> 00:41:44,990
E così se volevo solo
inserisci mora qui

831
00:41:44,990 --> 00:41:47,470
e volevo cercare
si, lo so, oh, mora

832
00:41:47,470 --> 00:41:52,012
deve iniziare con l'indice di 1, in modo da
conoscere istantaneamente basta cercare a 1.

833
00:41:52,012 --> 00:41:53,970
E poi posso tipo di
attraversare la lista collegata

834
00:41:53,970 --> 00:41:56,120
fino a ottenere alla mora,
e then-- sì?

835
00:41:56,120 --> 00:41:59,550
>> PUBBLICO: Se stai cercando di create--
Credo che in questo modo è molto semplice hash

836
00:41:59,550 --> 00:42:00,050
funzione.

837
00:42:00,050 --> 00:42:02,835
E se volessimo fare
più livelli di che, come,

838
00:42:02,835 --> 00:42:05,870
OK, vogliamo separare in
come tutte le lettere alfabetiche

839
00:42:05,870 --> 00:42:09,040
e poi di nuovo a come un altro set
di lettere alfabetiche all'interno di quella,

840
00:42:09,040 --> 00:42:11,715
stiamo mettendo come un hash
tabella all'interno di una tabella hash,

841
00:42:11,715 --> 00:42:13,256
o come una funzione all'interno di una funzione?

842
00:42:13,256 --> 00:42:14,880
O è che--

843
00:42:14,880 --> 00:42:17,510
>> ANDI PENG: Così il vostro hash
function-- la tua tabella di hash

844
00:42:17,510 --> 00:42:19,360
può essere grande come si desidera.

845
00:42:19,360 --> 00:42:21,930
Quindi, in questo senso, ho pensato
era molto facile, molto

846
00:42:21,930 --> 00:42:25,320
semplice per me basano appena sorta
sulle lettere della prima parola.

847
00:42:25,320 --> 00:42:28,690
E così ci sono solo 26 opzioni.

848
00:42:28,690 --> 00:42:32,650
Posso solo 26 opzioni da
0-25, perché solo è possibile

849
00:42:32,650 --> 00:42:36,510
iniziare dalla A alla Z. Ma se si voleva
aggiungere, forse, più complessità

850
00:42:36,510 --> 00:42:39,260
o più veloce il tempo di esecuzione per la vostra
tabella di hash, è assolutamente

851
00:42:39,260 --> 00:42:40,760
può fare un sacco di cose.

852
00:42:40,760 --> 00:42:43,330
È possibile rendere il proprio
equazione che ti dà

853
00:42:43,330 --> 00:42:48,000
più la distribuzione nella vostra
parole, poi quando si cerca,

854
00:42:48,000 --> 00:42:49,300
che sta per essere più veloce.

855
00:42:49,300 --> 00:42:52,100
>> E 'totalmente a voi ragazzi
come si desidera attuare tale.

856
00:42:52,100 --> 00:42:55,140
Pensate a come appena secchi.

857
00:42:55,140 --> 00:42:57,376
Se volevo avere
26 secchi, sto andando

858
00:42:57,376 --> 00:42:59,420
per sistemare le cose in quelli secchi.

859
00:42:59,420 --> 00:43:02,980
Ma ho intenzione di avere un gruppo
di roba di ciascun segmento,

860
00:43:02,980 --> 00:43:05,890
quindi se si vuole fare
più veloce ed efficiente,

861
00:43:05,890 --> 00:43:07,190
mi permetta di avere un centinaio di secchi.

862
00:43:07,190 --> 00:43:09,290
>> Ma poi si deve capire un
modo per ordinare le cose in modo che siano

863
00:43:09,290 --> 00:43:11,040
nel secchio corretta dovrebbero essere in.

864
00:43:11,040 --> 00:43:13,331
Ma allora quando realmente
vuole guardare quel secchio,

865
00:43:13,331 --> 00:43:16,410
è molto più veloce perché non c'è
meno roba in ciascun segmento.

866
00:43:16,410 --> 00:43:20,250
E così, sì, questo è in realtà
il trucco per voi ragazzi a pset5

867
00:43:20,250 --> 00:43:22,360
è che sarete
sfidati a creare solo

868
00:43:22,360 --> 00:43:26,170
Qualunque sia la più efficiente
funzione che si può pensare di essere

869
00:43:26,170 --> 00:43:28,520
in grado di memorizzare e controllare questi valori.

870
00:43:28,520 --> 00:43:30,840
>> Totalmente a voi ragazzi
comunque lo si voglia fare,

871
00:43:30,840 --> 00:43:32,229
ma questo è davvero un buon punto.

872
00:43:32,229 --> 00:43:34,520
Che il tipo di logica che si
voglia di iniziare a pensare

873
00:43:34,520 --> 00:43:37,236
è, beh, perché non faccio più secchi.

874
00:43:37,236 --> 00:43:39,527
E poi devo cercare
meno cose, e poi forse

875
00:43:39,527 --> 00:43:41,640
hanno una funzione hash differente.

876
00:43:41,640 --> 00:43:45,500
>> Sì, ci sono un sacco di modi per fare questo
pset, alcuni sono più veloci di altri.

877
00:43:45,500 --> 00:43:50,630
Sono totalmente andando a vedere quanto
veloce è stato il più veloce voi ragazzi

878
00:43:50,630 --> 00:43:55,170
essere in grado di ottenere le funzioni per lavorare.

879
00:43:55,170 --> 00:43:58,176
OK, tutti bene su
concatenamento e hash tabelle?

880
00:43:58,176 --> 00:44:00,800
In realtà è come una molto semplice
concetto se ci pensate.

881
00:44:00,800 --> 00:44:05,160
Tutto ciò che è è ciò che separa
gli ingressi sono in secchi,

882
00:44:05,160 --> 00:44:10,670
loro ordinamento, e quindi la ricerca del
elenca che vi è associato.

883
00:44:10,670 --> 00:44:11,852
>> Raffreddare.

884
00:44:11,852 --> 00:44:18,160
Va bene, ora abbiamo una specie diversa
di struttura dati che è chiamato un albero.

885
00:44:18,160 --> 00:44:20,850
Andiamo avanti e parlare di tentativi
quali sono nettamente diverso,

886
00:44:20,850 --> 00:44:22,330
ma nella stessa categoria.

887
00:44:22,330 --> 00:44:29,010
Essenzialmente, tutto un albero è invece
di organizzare i dati in modo lineare

888
00:44:29,010 --> 00:44:32,560
che una tabella hash si does--
Sai, che ha un alto e un basso

889
00:44:32,560 --> 00:44:37,900
e quindi è sorta di collegare al largo di un it--
albero ha una parte superiore, che si chiama la radice,

890
00:44:37,900 --> 00:44:40,220
e quindi ha foglie tutto intorno.

891
00:44:40,220 --> 00:44:42,390
>> E così tutto quello che avete qui
è solo il nodo superiore

892
00:44:42,390 --> 00:44:45,980
che punta ad altri nodi, che i punti
a più nodi, e così via e così via.

893
00:44:45,980 --> 00:44:48,130
E quindi basta avere i rami di divisione.

894
00:44:48,130 --> 00:44:53,255
E 'solo un modo diverso di organizzare
dati, e perché si parla di un albero,

895
00:44:53,255 --> 00:44:56,270
voi ragazzi solo-- è solo
modellato a guardare come un albero.

896
00:44:56,270 --> 00:44:57,670
Ecco perché lo chiamiamo alberi.

897
00:44:57,670 --> 00:44:59,370
>> Tabella hash si presenta come un tavolo.

898
00:44:59,370 --> 00:45:01,310
Un albero appare come un albero.

899
00:45:01,310 --> 00:45:03,300
Tutto ciò che è è un separato
modo di organizzare i nodi

900
00:45:03,300 --> 00:45:06,020
a seconda di cosa i vostri bisogni sono.

901
00:45:06,020 --> 00:45:11,810
>> In modo da avere una radice e
allora avete foglie.

902
00:45:11,810 --> 00:45:15,380
Il modo in cui possiamo particolarmente
pensarci è un albero binario,

903
00:45:15,380 --> 00:45:18,150
un albero binario è solo un
tipo specifico di un albero

904
00:45:18,150 --> 00:45:22,450
dove solo ogni nodo punti
a, al massimo, due altri nodi.

905
00:45:22,450 --> 00:45:25,434
Ed ecco avete distinti
simmetria nel tuo albero

906
00:45:25,434 --> 00:45:28,600
che rende più facile per tipo di look
a quali valori si sono perché poi si

907
00:45:28,600 --> 00:45:30,150
avere sempre a sinistra o destra.

908
00:45:30,150 --> 00:45:33,150
Non c'è mai come un terzo da sinistra
sinistra o un quarto da sinistra.

909
00:45:33,150 --> 00:45:36,358
E 'solo avete una sinistra e una destra
e si può cercare uno di quei due.

910
00:45:36,358 --> 00:45:38,980
E allora perché è utile?

911
00:45:38,980 --> 00:45:40,980
Il modo in cui questo è
utile è se stai cercando

912
00:45:40,980 --> 00:45:42,890
per la ricerca in valori, giusto?

913
00:45:42,890 --> 00:45:45,640
Invece di attuazione binario
cerca in un array di errore,

914
00:45:45,640 --> 00:45:49,260
se si voleva essere in grado di inserire i nodi
e portare via i nodi a volontà e anche

915
00:45:49,260 --> 00:45:52,185
preservare la ricerca
capacità di ricerca binaria.

916
00:45:52,185 --> 00:45:54,560
Quindi, in questo modo, siamo sorta di
tricking-- ricordo quando abbiamo

917
00:45:54,560 --> 00:45:56,530
detto liste concatenate non può ricerca binaria?

918
00:45:56,530 --> 00:46:01,700
Stiamo tipo di creazione di una struttura di dati
che trucchi che a lavorare.

919
00:46:01,700 --> 00:46:05,034
>> E le liste perché collegate sono lineari,
si collegano solo uno dopo l'altro.

920
00:46:05,034 --> 00:46:06,950
Possiamo sorta di avere
diverso tipo di puntatori

921
00:46:06,950 --> 00:46:09,408
quel punto a differenti nodi
che ci può aiutare con la ricerca.

922
00:46:09,408 --> 00:46:12,590
Ed ecco, se volevo
avere un albero binario di ricerca,

923
00:46:12,590 --> 00:46:14,090
So che il mio mezzo, se 55.

924
00:46:14,090 --> 00:46:18,280
Sto solo andando a creare quella
come il mio mezzo, come la mia radice,

925
00:46:18,280 --> 00:46:20,770
e poi ho intenzione di avere
I valori di spin fuori di esso.

926
00:46:20,770 --> 00:46:25,610
>> Così qui, se io vado a cercare
il valore di 66, posso iniziare a 55.

927
00:46:25,610 --> 00:46:27,310
È 66 maggiore di 55?

928
00:46:27,310 --> 00:46:30,970
Sì, è, quindi so che MUS cerco
i n il puntatore a destra di questo albero.

929
00:46:30,970 --> 00:46:32,440
Vado a 77.

930
00:46:32,440 --> 00:46:35,367
OK, è inferiore a 66 o superiore a 77?

931
00:46:35,367 --> 00:46:37,950
E 'meno, in modo da sapere, oh,
che deve essere il nodo di sinistra.

932
00:46:37,950 --> 00:46:41,410
>> Ed ecco che stiamo tipo di preservare
tutte le grandi cose su array,

933
00:46:41,410 --> 00:46:44,420
così come il ridimensionamento dinamico
di oggetti, essendo

934
00:46:44,420 --> 00:46:49,530
in grado di inserire e cancellare a piacimento,
senza doversi preoccupare del fisso

935
00:46:49,530 --> 00:46:50,370
quantità di spazio.

936
00:46:50,370 --> 00:46:52,820
Abbiamo ancora conserviamo tutti
quelle cose meravigliose

937
00:46:52,820 --> 00:46:57,140
pur essendo in grado di preservare la
log e cercare il tempo di ricerca binaria

938
00:46:57,140 --> 00:47:00,450
che eravamo solo in precedenza
in grado di ottenere una frase.

939
00:47:00,450 --> 00:47:06,310
>> Struttura dati fresco, tipo di
complesso da attuare, il nodo.

940
00:47:06,310 --> 00:47:08,311
Come potete vedere, tutto ciò che
è la struct del nodo

941
00:47:08,311 --> 00:47:10,143
è che si dispone di un sinistro
e un puntatore a destra.

942
00:47:10,143 --> 00:47:11,044
Questo è tutto ciò che è.

943
00:47:11,044 --> 00:47:12,960
Quindi, piuttosto che solo
avere un x o di un precedente.

944
00:47:12,960 --> 00:47:15,920
Si dispone di un sinistro o un diritto, e quindi
è possibile tipo di collegarli insieme

945
00:47:15,920 --> 00:47:16,836
tuttavia lo desidera.

946
00:47:16,836 --> 00:47:21,080

947
00:47:21,080 --> 00:47:24,270
>> OK, stiamo effettivamente andando
basta prendere un paio di minuti.

948
00:47:24,270 --> 00:47:25,790
Quindi stiamo per tornare qui.

949
00:47:25,790 --> 00:47:28,270
Come ho detto in precedenza,
I tipi di spiegai

950
00:47:28,270 --> 00:47:31,520
la logica dietro il modo in cui
sarebbe la ricerca in questo.

951
00:47:31,520 --> 00:47:33,860
Stiamo andando a provare
pseudocoding questo fuori per vedere

952
00:47:33,860 --> 00:47:38,000
se siamo in grado di applicare il tipo
stessa logica di ricerca binaria

953
00:47:38,000 --> 00:47:40,055
ad un diverso tipo di struttura dati.

954
00:47:40,055 --> 00:47:45,049
Se voi ragazzi volete prendere come una coppia
minuti per pensare solo di questo.

955
00:47:45,049 --> 00:48:45,927

956
00:48:45,927 --> 00:48:46,925
OK.

957
00:48:46,925 --> 00:48:51,407
Va bene, vado a
in realtà solo darvi the-- no,

958
00:48:51,407 --> 00:48:52,990
parleremo il pseudocodice prima.

959
00:48:52,990 --> 00:48:56,580
Così qualcuno vuole
per dare una pugnalata a ciò che

960
00:48:56,580 --> 00:49:02,100
la prima cosa che voglio fare quando
si sta partendo la ricerca è?

961
00:49:02,100 --> 00:49:04,460
Se stiamo cercando
il valore di 66, ciò che è

962
00:49:04,460 --> 00:49:07,940
la prima cosa che vogliamo fare se
vogliamo in binario cercare questo albero?

963
00:49:07,940 --> 00:49:10,760
>> PUBBLICO: Si vuole guardare a destra
e guardare a sinistra e vedere [incomprensibile]

964
00:49:10,760 --> 00:49:11,230
numero maggiore.

965
00:49:11,230 --> 00:49:12,271
>> ANDI PENG: Sì, esattamente.

966
00:49:12,271 --> 00:49:15,350
Così si sta andando a guardare root.

967
00:49:15,350 --> 00:49:18,180
Ci sono molti modi è possibile chiamare
esso, il tuo popolo nodo genitore dire.

968
00:49:18,180 --> 00:49:21,317
Mi piace dire radice perché
che è come la radice dell'albero.

969
00:49:21,317 --> 00:49:23,400
Si sta andando a guardare
il nodo principale, e sei

970
00:49:23,400 --> 00:49:26,940
andando a vedere è maggiore 66
o minore di 55.

971
00:49:26,940 --> 00:49:30,360
E se è maggiore di, beh, è
superiore, dove vogliamo guardare?

972
00:49:30,360 --> 00:49:32,000
Dove vogliamo per cercare ora, giusto?

973
00:49:32,000 --> 00:49:34,340
Noi vogliamo cercare la
metà destra di questo albero.

974
00:49:34,340 --> 00:49:38,390
>> Così abbiamo, comodamente, un
puntatore che punta a destra.

975
00:49:38,390 --> 00:49:44,325
E così poi possiamo impostare
la nostra nuova radice per essere 77.

976
00:49:44,325 --> 00:49:46,450
Possiamo solo andare ovunque
il puntatore punta.

977
00:49:46,450 --> 00:49:49,100
Beh, oh, qui stiamo iniziando
a 77, e possiamo solo

978
00:49:49,100 --> 00:49:51,172
fare questo in modo ricorsivo ancora e ancora.

979
00:49:51,172 --> 00:49:52,880
In questo modo, è sorta
di avere una funzione.

980
00:49:52,880 --> 00:49:57,430
Avete un modo di cercare che si
può solo ripetere più e più e più volte,

981
00:49:57,430 --> 00:50:02,720
a seconda di dove si vuole guardare
fino ad arrivare alla fine del valore

982
00:50:02,720 --> 00:50:04,730
che si sta cercando.

983
00:50:04,730 --> 00:50:05,230
Ha senso?

984
00:50:05,230 --> 00:50:07,800
>> Sto per mostrarvi la reale
codice, ed è un sacco di codice.

985
00:50:07,800 --> 00:50:08,674
Non c'è bisogno di fuori di testa.

986
00:50:08,674 --> 00:50:09,910
Parleremo attraverso di essa.

987
00:50:09,910 --> 00:50:13,410

988
00:50:13,410 --> 00:50:14,020
>> In realtà, no.

989
00:50:14,020 --> 00:50:15,061
Quello era solo pseudocodice.

990
00:50:15,061 --> 00:50:17,860
OK, questo era solo l'pseudocodice,
che è un po 'complessa,

991
00:50:17,860 --> 00:50:19,751
ma è assolutamente soddisfacente.

992
00:50:19,751 --> 00:50:21,000
Ognuno seguendo lungo qui?

993
00:50:21,000 --> 00:50:24,260
Se la radice è nullo, il ritorno
falso perché questo significa

994
00:50:24,260 --> 00:50:26,850
voi non hanno nemmeno bisogno nulla.

995
00:50:26,850 --> 00:50:31,376
>> Se radice n è il valore, quindi se
sembra essere quello che si sta guardando,

996
00:50:31,376 --> 00:50:34,000
allora si sta andando a restituire true
perché sai hai trovato.

997
00:50:34,000 --> 00:50:36,250
Ma se il valore è inferiore
di radice di n, sei

998
00:50:36,250 --> 00:50:38,332
andando a cercare la sinistra
bambino o la foglia di sinistra,

999
00:50:38,332 --> 00:50:39,540
qualunque cosa si voglia chiamare.

1000
00:50:39,540 --> 00:50:41,750
E se il valore è maggiore di radice,
si sta andando a cercare l'albero giusto,

1001
00:50:41,750 --> 00:50:44,610
poi basta eseguire la funzione
attraverso la ricerca di nuovo.

1002
00:50:44,610 --> 00:50:48,037
>> E se radice è nullo, che tale
significa che hai raggiunto la fine?

1003
00:50:48,037 --> 00:50:50,120
Ciò significa che non avete
più più foglie per la ricerca,

1004
00:50:50,120 --> 00:50:52,230
poi si sa, oh,
Immagino che non è qui

1005
00:50:52,230 --> 00:50:55,063
perché dopo che ho guardato attraverso
il tutto e non è qui,

1006
00:50:55,063 --> 00:50:56,930
semplicemente non potrebbe essere qui.

1007
00:50:56,930 --> 00:50:58,350
>> Questo fa senso a tutti?

1008
00:50:58,350 --> 00:51:03,230
Così è come la ricerca binaria preservare
le capacità di liste collegate.

1009
00:51:03,230 --> 00:51:09,200
Fresco, e così il secondo tipo
di strutture dati voi ragazzi

1010
00:51:09,200 --> 00:51:13,180
può provare l'attuazione sul pset,
devi solo scegliere un metodo.

1011
00:51:13,180 --> 00:51:19,430
Ma forse un metodo alternativo per
la tabella hash è ciò che chiamiamo un trie.

1012
00:51:19,430 --> 00:51:24,080
>> Tutto un trie è un
specifico tipo di albero che

1013
00:51:24,080 --> 00:51:28,600
ha valori che vanno ad altri valori.

1014
00:51:28,600 --> 00:51:31,450
Così, invece di avere un binario
albero nel senso che un solo

1015
00:51:31,450 --> 00:51:35,940
cosa può puntare a due, si può avere
punto una cosa da molte, molte cose.

1016
00:51:35,940 --> 00:51:39,450
Hai essenzialmente matrici
all'interno del quale si memorizza

1017
00:51:39,450 --> 00:51:41,790
puntatori che puntano ad altri array.

1018
00:51:41,790 --> 00:51:45,210

1019
00:51:45,210 --> 00:51:49,460
>> Quindi il nodo di come
definirebbe un trie

1020
00:51:49,460 --> 00:51:52,590
è che vogliamo avere un
Booleano, c parola, giusto?

1021
00:51:52,590 --> 00:51:54,920
Quindi il nodo è booleano
come vero o falso,

1022
00:51:54,920 --> 00:51:58,490
prima di tutto alla testa
tale matrice, si tratta di una parola?

1023
00:51:58,490 --> 00:52:03,620
In secondo luogo, si vuole avere puntatori
a qualunque il resto di loro sono.

1024
00:52:03,620 --> 00:52:07,470
Un po 'complesso, un po' astratto, ma
Spiegherò cosa che tutti i mezzi.

1025
00:52:07,470 --> 00:52:13,800
>> Così qui, in alto, se si
hanno una matrice dichiarato già,

1026
00:52:13,800 --> 00:52:17,040
un nodo in cui si dispone di un booleano
valore memorizzato nella parte anteriore

1027
00:52:17,040 --> 00:52:19,490
che ti dice è questa una parola?

1028
00:52:19,490 --> 00:52:20,520
Non è questa una parola?

1029
00:52:20,520 --> 00:52:23,240
E poi ci sono la
resto del vostro array

1030
00:52:23,240 --> 00:52:26,040
in realtà memorizza tutte le
possibilità di ciò che potrebbe essere.

1031
00:52:26,040 --> 00:52:28,660
Così, per esempio, come
in alto si ha

1032
00:52:28,660 --> 00:52:32,140
la prima cosa che dice vero o
falso, sì o no, questa è una parola.

1033
00:52:32,140 --> 00:52:38,130
>> E poi ci sono da 0 a 26 di
le lettere che è possibile memorizzare.

1034
00:52:38,130 --> 00:52:42,790
Se volessi cercare
per pipistrello, vado al top

1035
00:52:42,790 --> 00:52:49,200
e cerco B. trovo nel mio B
array, e quindi so, OK, è B una parola?

1036
00:52:49,200 --> 00:52:53,010
B non è una parola, così così
Devo continuare a cercare.

1037
00:52:53,010 --> 00:52:56,410
Vado da B, e guardo al
puntatore che punta verso B

1038
00:52:56,410 --> 00:53:00,900
e vedo un altro array di informazioni,
la stessa struttura che avevamo prima.

1039
00:53:00,900 --> 00:53:05,240
>> E qui-- oh, il prossimo
lettera [incomprensibile] è A.

1040
00:53:05,240 --> 00:53:07,210
Quindi guardiamo in tale matrice.

1041
00:53:07,210 --> 00:53:10,860
Troviamo l'ottavo del valore,
e poi guardiamo a vedere, oh,

1042
00:53:10,860 --> 00:53:12,840
ehi, che è una parola, è B-A una parola?

1043
00:53:12,840 --> 00:53:13,807
Non è una parola.

1044
00:53:13,807 --> 00:53:14,890
Dobbiamo continuare a cercare.

1045
00:53:14,890 --> 00:53:17,850
>> E così poi guardiamo a dove
l'indicatore di punti A,

1046
00:53:17,850 --> 00:53:21,130
e indica un altro modo in
che abbiamo più valore memorizzato.

1047
00:53:21,130 --> 00:53:24,150
E alla fine, si arriva a
B-A-T, che è una parola.

1048
00:53:24,150 --> 00:53:25,970
E così la prossima volta
si guarda, si sta andando

1049
00:53:25,970 --> 00:53:30,850
per avere quel controllo di, sì,
questa funzione booleana è vero.

1050
00:53:30,850 --> 00:53:35,450
E così, nel senso che siamo tipo
di avere un albero con array.

1051
00:53:35,450 --> 00:53:39,890
>> Così allora si può tipo di ricerca in giù.

1052
00:53:39,890 --> 00:53:43,650
Invece di una funzione hash e
assegnando valori da lista collegata,

1053
00:53:43,650 --> 00:53:49,190
si può solo attuare un
trie che cerca downwords.

1054
00:53:49,190 --> 00:53:50,850
Davvero, davvero complicato roba.

1055
00:53:50,850 --> 00:53:54,060
Non è facile pensare, perché sono come
sputando tante strutture di dati fuori

1056
00:53:54,060 --> 00:53:58,710
a voi, ma lo fa tutti i tipi di
capire come funziona la logica di questo?

1057
00:53:58,710 --> 00:54:01,920
>> Ok bello.

1058
00:54:01,920 --> 00:54:05,600
Quindi B-A-T, e quindi
si sta andando a cercare.

1059
00:54:05,600 --> 00:54:07,940
La prossima volta che si sta andando
per vedere, oh, ehi, è vero,

1060
00:54:07,940 --> 00:54:09,273
quindi so che questo deve essere una parola.

1061
00:54:09,273 --> 00:54:12,030

1062
00:54:12,030 --> 00:54:13,770
>> Stessa cosa per lo zoo.

1063
00:54:13,770 --> 00:54:17,960
Quindi, ecco la cosa in questo momento, se si
voluto per cercare zoo, in questo momento,

1064
00:54:17,960 --> 00:54:20,780
attualmente zoo non è un
parola nel nostro dizionario

1065
00:54:20,780 --> 00:54:25,300
perché, come voi potete vedere, il
primo posto che abbiamo un valore booleano

1066
00:54:25,300 --> 00:54:28,590
ritorno vero è a fine zoom.

1067
00:54:28,590 --> 00:54:30,430
Abbiamo Z-O-O-M.

1068
00:54:30,430 --> 00:54:33,900
>> Ed ecco, noi non abbiamo in realtà
la parola, zoo, nel nostro dizionario

1069
00:54:33,900 --> 00:54:36,070
perché questa casella non è selezionata.

1070
00:54:36,070 --> 00:54:39,540
Quindi il computer non si
sa che lo zoo è una parola

1071
00:54:39,540 --> 00:54:42,430
perché il modo che abbiamo
memorizzata esso, solo uno zoom qui

1072
00:54:42,430 --> 00:54:44,920
in realtà ha un valore booleano
ciò che è stato trasformato vero.

1073
00:54:44,920 --> 00:54:49,380
Quindi, se vogliamo inserire la
parola, zoo, nel nostro dizionario,

1074
00:54:49,380 --> 00:54:51,770
come potremmo fare per fare che?

1075
00:54:51,770 --> 00:54:55,960
Cosa dobbiamo fare per assicurarsi che il nostro
computer sa che Z-O-O è una parola

1076
00:54:55,960 --> 00:54:58,130
e non la prima parola è Z-O-O-M?

1077
00:54:58,130 --> 00:54:59,360
>> PUBBLICO: [incomprensibile]

1078
00:54:59,360 --> 00:55:01,450
>> ANDI PENG: Esattamente, abbiamo
vuole fare in modo che questo

1079
00:55:01,450 --> 00:55:07,890
qui, che è valore booleano
spuntata che è vero.

1080
00:55:07,890 --> 00:55:13,297
Z-O-O, allora stiamo andando a verificare che,
così sappiamo esattamente, ehi, lo zoo è una parola.

1081
00:55:13,297 --> 00:55:15,380
Io vado a dire la
computer che è una parola così

1082
00:55:15,380 --> 00:55:18,000
che quando il computer controlla,
sa che lo zoo è una parola.

1083
00:55:18,000 --> 00:55:21,269
>> Perché ricordare tutti questi dati
strutture, è molto facile per noi

1084
00:55:21,269 --> 00:55:22,310
per dire, oh, pipistrello è una parola.

1085
00:55:22,310 --> 00:55:22,851
Zoo è una parola.

1086
00:55:22,851 --> 00:55:23,611
Zoom è una parola.

1087
00:55:23,611 --> 00:55:25,860
Ma quando si sta costruendo essa,
il computer non ha idea.

1088
00:55:25,860 --> 00:55:28,619
>> Quindi devi dire esattamente
a che punto è questa una parola?

1089
00:55:28,619 --> 00:55:29,910
A che punto non è forse una parola?

1090
00:55:29,910 --> 00:55:31,784
E a che punto devo
bisogno di cercare le cose,

1091
00:55:31,784 --> 00:55:34,000
ea che punto devo andare dopo?

1092
00:55:34,000 --> 00:55:37,010
Ognuno chiaro di che?

1093
00:55:37,010 --> 00:55:39,540
Raffreddare.

1094
00:55:39,540 --> 00:55:42,530
>> E così poi arriva il
problema di come sarebbe noi

1095
00:55:42,530 --> 00:55:45,560
andare sull'inserimento qualcosa
questo non è davvero lì?

1096
00:55:45,560 --> 00:55:49,090
Quindi diciamo solo che vogliamo inserire
la parola, il bagno, nel nostro trie.

1097
00:55:49,090 --> 00:55:53,589
Come voi ragazzi possono vedere come attualmente
tutto quello che abbiamo ora è B-A-T,

1098
00:55:53,589 --> 00:55:55,630
e questa nuova struttura di dati
vi era una pinta che

1099
00:55:55,630 --> 00:55:59,740
indicò nullo perché si suppone
che, oh, non ci sono parole dopo B-A-T,

1100
00:55:59,740 --> 00:56:02,530
perché abbiamo bisogno di mantenere
avere cose dopo che T.

1101
00:56:02,530 --> 00:56:06,581
>> Ma il problema si pone se non facciamo voi
vogliono avere una parola che viene dopo

1102
00:56:06,581 --> 00:56:07,080
il T.

1103
00:56:07,080 --> 00:56:09,500
Se si dispone di vasca da bagno, sei
intenzione di voler un diritto H.

1104
00:56:09,500 --> 00:56:13,290
E così il modo in cui stiamo andando per farlo è
stiamo andando a creare un nodo separato.

1105
00:56:13,290 --> 00:56:16,840
Non stiamo assegniamo qualsiasi importo
di memoria per questo nuovo array,

1106
00:56:16,840 --> 00:56:20,720
e abbiamo intenzione di riassegnare i puntatori.

1107
00:56:20,720 --> 00:56:22,947
>> Stiamo per assegnare il
H, Prima di tutto, questo nullo,

1108
00:56:22,947 --> 00:56:24,030
stiamo andando a sbarazzarsi.

1109
00:56:24,030 --> 00:56:26,590
Stiamo per avere
le basso punto H.

1110
00:56:26,590 --> 00:56:30,600
Se vediamo un H, lo vogliamo
per andare da qualche altra parte.

1111
00:56:30,600 --> 00:56:33,910
>> Qui, possiamo allora spuntare sì.

1112
00:56:33,910 --> 00:56:38,170
Se abbiamo raggiunto una H dopo la T, oh,
allora sappiamo che si tratta di una parola.

1113
00:56:38,170 --> 00:56:41,110
Il booleana sta per restituire true.

1114
00:56:41,110 --> 00:56:42,950
Ognuno chiaro su come quello che è successo?

1115
00:56:42,950 --> 00:56:45,110
OK.

1116
00:56:45,110 --> 00:56:47,214
>> Quindi, in sostanza, tutti
queste strutture dati

1117
00:56:47,214 --> 00:56:50,130
che siamo andati oltre oggi, ho
passati su di loro molto, molto in fretta

1118
00:56:50,130 --> 00:56:52,192
e non per molto
dettaglio, e questo è OK.

1119
00:56:52,192 --> 00:56:53,900
Una volta che si inizia a fare scherzi
con essa, sarete

1120
00:56:53,900 --> 00:56:55,733
tenere traccia di dove
tutti i puntatori sono,

1121
00:56:55,733 --> 00:56:58,060
cosa sta succedendo nella vostra
strutture di dati, eccetera.

1122
00:56:58,060 --> 00:56:59,810
Saranno molto utili,
e tocca a voi

1123
00:56:59,810 --> 00:57:03,890
ragazzi per capire completamente come
si desidera implementare le cose.

1124
00:57:03,890 --> 00:57:07,650
>> E così pset4, di 5-- oh, questo è sbagliato.

1125
00:57:07,650 --> 00:57:10,140
Pset5 è errori di ortografia.

1126
00:57:10,140 --> 00:57:13,710
Come ho detto prima, si sta andando a, una volta
ancora una volta, scaricare il codice sorgente da noi.

1127
00:57:13,710 --> 00:57:16,210
Ci sara 'tre principali
cose sarete scaricando.

1128
00:57:16,210 --> 00:57:18,470
Potrai scaricare dizionari,
kers, e testi.

1129
00:57:18,470 --> 00:57:21,660
>> Tutte queste cose sono sono
sia dizionari di parole

1130
00:57:21,660 --> 00:57:25,190
che vogliamo di controllare
o il test di informazioni

1131
00:57:25,190 --> 00:57:26,930
che vogliamo farvi Controllo ortografico.

1132
00:57:26,930 --> 00:57:29,670
E così il dizionari
diamo si sta andando

1133
00:57:29,670 --> 00:57:34,870
per darvi parole reali che vogliamo
di memorizzare in qualche modo in un modo che è

1134
00:57:34,870 --> 00:57:36,530
più efficiente di una matrice.

1135
00:57:36,530 --> 00:57:38,470
E poi i testi sono
sta per essere ciò che siamo

1136
00:57:38,470 --> 00:57:43,900
si chiede di controllo ortografico per assicurarsi
tutte le parole ci sono parole reali.

1137
00:57:43,900 --> 00:57:47,970
>> E così i tre blocchi di
programmi che vi daremo

1138
00:57:47,970 --> 00:57:51,130
sono chiamati dictionary.c,
dictionary.h, e speller.c.

1139
00:57:51,130 --> 00:57:56,500
E così tutto si fa dictionary.c
quello che ti viene chiesto di implementare.

1140
00:57:56,500 --> 00:57:57,880
Carica parole.

1141
00:57:57,880 --> 00:58:02,000
E 'incantesimo controlli loro, e si assicura
che tutto sia inserito correttamente.

1142
00:58:02,000 --> 00:58:05,180
>> diction.h è solo un file di libreria
dichiara che tutte quelle funzioni.

1143
00:58:05,180 --> 00:58:07,650
E speller.c, stiamo per darvi.

1144
00:58:07,650 --> 00:58:09,290
Non è necessario modificare qualsiasi di esso.

1145
00:58:09,290 --> 00:58:14,290
Tutti speller.c non è prendere che,
lo carica, controlla la velocità di esso,

1146
00:58:14,290 --> 00:58:19,190
prove il punto di riferimento di come come
rapidamente siete in grado di fare le cose.

1147
00:58:19,190 --> 00:58:20,410
>> E 'un correttore ortografico.

1148
00:58:20,410 --> 00:58:23,920
Basta che non si scherza con esso, ma fare
sicuri di capire quello che sta facendo.

1149
00:58:23,920 --> 00:58:28,090
Noi usiamo una funzione chiamata getrusage che
test le prestazioni del vostro incantesimo

1150
00:58:28,090 --> 00:58:28,590
checker.

1151
00:58:28,590 --> 00:58:32,200
Tutto ciò che fa è fondamentalmente testare il
tempo di tutto nel vostro dizionario,

1152
00:58:32,200 --> 00:58:33,680
quindi assicuratevi di capire.

1153
00:58:33,680 --> 00:58:36,660
Fare attenzione a non pasticciare con essa o
altra cosa non verranno eseguiti correttamente.

1154
00:58:36,660 --> 00:58:39,740

1155
00:58:39,740 --> 00:58:44,170
>> E la maggior parte di questa sfida è per
voi ragazzi a modificare realmente dictionary.c.

1156
00:58:44,170 --> 00:58:48,526
Stiamo per darvi
140.000 parole in un dizionario.

1157
00:58:48,526 --> 00:58:50,900
Stiamo per darvi un testo
file con quelle parole,

1158
00:58:50,900 --> 00:58:54,840
e noi vogliamo che tu sia in grado di organizzare
li in una tabella hash o un trie

1159
00:58:54,840 --> 00:58:58,140
perché quando ti chiediamo di precisare
check-- immaginare se siete magia

1160
00:58:58,140 --> 00:59:00,690
controllo come l'Odissea di Omero.

1161
00:59:00,690 --> 00:59:03,010
E 'come questo enorme, enorme prova.

1162
00:59:03,010 --> 00:59:05,190
>> Immaginate se ogni singolo
parola si doveva guardare

1163
00:59:05,190 --> 00:59:08,100
attraverso una serie di 140.000 valori.

1164
00:59:08,100 --> 00:59:10,350
Che avrebbe preso per sempre
per la vostra macchina per l'esecuzione.

1165
00:59:10,350 --> 00:59:14,490
Per questo motivo vogliamo organizzare la nostra
i dati in strutture dati più efficienti

1166
00:59:14,490 --> 00:59:17,270
ad esempio una tabella hash o un trie.

1167
00:59:17,270 --> 00:59:20,700
E poi voi ragazzi può tipo
di quando si cerca l'accesso

1168
00:59:20,700 --> 00:59:22,570
le cose più facilmente e più velocemente.

1169
00:59:22,570 --> 00:59:24,934
>> E quindi state attenti a risolvere le collisioni.

1170
00:59:24,934 --> 00:59:27,350
Stai andando a ottenere un mucchio
di parole di che iniziano con A.

1171
00:59:27,350 --> 00:59:29,957
Stai andando a ottenere un mazzo parole
che iniziano con B. Fino a voi

1172
00:59:29,957 --> 00:59:31,290
ragazzi come si desidera risolvere esso.

1173
00:59:31,290 --> 00:59:34,144
Forse non c'è più
funzione hash efficiente

1174
00:59:34,144 --> 00:59:36,810
che solo la prima lettera del
qualcosa, e in modo che tocca a voi

1175
00:59:36,810 --> 00:59:38,190
ragazzi al tipo di fare quello che vuoi.

1176
00:59:38,190 --> 00:59:40,148
>> Forse si vuole aggiungere
tutte le lettere insieme.

1177
00:59:40,148 --> 00:59:43,410
Forse si vuole piace fare cose strane
per spiegare il numero di lettere,

1178
00:59:43,410 --> 00:59:43,970
che cosa mai.

1179
00:59:43,970 --> 00:59:45,386
Fino a voi ragazzi come si desidera fare.

1180
00:59:45,386 --> 00:59:49,262
Se si vuole fare una tabella di hash, se
vuole provare un trie, totalmente a voi.

1181
00:59:49,262 --> 00:59:52,470
Io vi avvertirà in anticipo che il
trie è in genere un po 'più difficile

1182
00:59:52,470 --> 00:59:54,520
solo perché c'è un sacco
ulteriori riferimenti a tenere traccia di.

1183
00:59:54,520 --> 00:59:55,645
Ma totalmente a voi ragazzi.

1184
00:59:55,645 --> 00:59:58,742
E 'molto più efficiente
nella maggior parte dei casi.

1185
00:59:58,742 --> 01:00:01,450
Si vuole essere veramente in grado di mantenere
traccia di tutti i tuoi puntatori.

1186
01:00:01,450 --> 01:00:03,850
Come fare la stessa cosa
che stavo facendo qui.

1187
01:00:03,850 --> 01:00:06,871
Quando si sta cercando di inserire
valori in una tabella hash o cancellare,

1188
01:00:06,871 --> 01:00:08,620
fare in modo che tu sia
davvero tenere traccia

1189
01:00:08,620 --> 01:00:11,860
di dove tutto è perché
è davvero facile per se sono

1190
01:00:11,860 --> 01:00:14,727
cercando di inserire come la parola, andy.

1191
01:00:14,727 --> 01:00:16,810
Diciamo solo che è un
vera parola, la parola, andy,

1192
01:00:16,810 --> 01:00:19,640
in una lista gigante di un parole.

1193
01:00:19,640 --> 01:00:22,450
>> Se mi capita di riassegnare
un puntatore sbagliato, oops,

1194
01:00:22,450 --> 01:00:24,940
ci va l'interezza della
il resto della mia lista collegata.

1195
01:00:24,940 --> 01:00:26,897
Ora l'unica parola che mi
avere è Andy, e ora

1196
01:00:26,897 --> 01:00:29,230
tutte le altre parole del
dizionario sono andati perduti.

1197
01:00:29,230 --> 01:00:31,370
E così si vuole fare in modo che si
tenere traccia di tutti i tuoi puntatori

1198
01:00:31,370 --> 01:00:33,661
oppure si sta andando ad ottenere
enormi problemi nel codice.

1199
01:00:33,661 --> 01:00:35,840
Disegna le cose con cura passo dopo passo.

1200
01:00:35,840 --> 01:00:37,870
Lo rende molto più facile pensare.

1201
01:00:37,870 --> 01:00:40,910
>> E, infine, si vuole essere in grado di
testare le prestazioni del vostro programma

1202
01:00:40,910 --> 01:00:41,618
sul grande tabellone.

1203
01:00:41,618 --> 01:00:43,710
Se voi ragazzi prendere una
guardare CS50 in questo momento,

1204
01:00:43,710 --> 01:00:45,210
noi abbiamo quello che si chiama il grande tavola.

1205
01:00:45,210 --> 01:00:50,200
E 'la scheda di valutazione dei più veloci
ortografico tempi di controllo in tutti CS50

1206
01:00:50,200 --> 01:00:55,720
in questo momento, penso che il top come 10
volte penso che otto di loro sono personale.

1207
01:00:55,720 --> 01:00:57,960
Vogliamo davvero che voi ragazzi a battere noi.

1208
01:00:57,960 --> 01:01:00,870
>> Tutti noi stavano cercando di attuare
il codice più veloce possibile.

1209
01:01:00,870 --> 01:01:04,880
Vogliamo che voi ragazzi per cercare di sfidare i
noi e implementare più velocemente di tutti noi

1210
01:01:04,880 --> 01:01:05,550
lattina.

1211
01:01:05,550 --> 01:01:07,970
E così questo è davvero
la prima volta che siamo

1212
01:01:07,970 --> 01:01:12,680
chiedendo ragazzi di fare un pset che
si può davvero fare a qualsiasi metodo

1213
01:01:12,680 --> 01:01:13,760
tu vuoi.

1214
01:01:13,760 --> 01:01:17,730
>> Io dico sempre, questo è più simile
ad una soluzione di vita reale, giusto?

1215
01:01:17,730 --> 01:01:19,550
Dico, ehi, ho bisogno che tu faccia questo.

1216
01:01:19,550 --> 01:01:21,380
Costruire un programma che fa questo per me.

1217
01:01:21,380 --> 01:01:22,630
Farlo nel modo desiderato.

1218
01:01:22,630 --> 01:01:24,271
So solo che voglio digiunare.

1219
01:01:24,271 --> 01:01:25,770
Questa è la tua sfida per questa settimana.

1220
01:01:25,770 --> 01:01:27,531
Ragazzi, ci sta andando
per darvi un compito.

1221
01:01:27,531 --> 01:01:29,030
Stiamo per darvi una sfida.

1222
01:01:29,030 --> 01:01:31,559
E poi tocca a voi ragazzi
completamente solo capire

1223
01:01:31,559 --> 01:01:34,100
qual è il più veloce e più
modo efficace per implementare questo.

1224
01:01:34,100 --> 01:01:34,600
Sì?

1225
01:01:34,600 --> 01:01:37,476
>> PUBBLICO: Stiamo permesso di se
wanted alla ricerca metodi più veloci

1226
01:01:37,476 --> 01:01:40,821
a fare tabelle hash in linea, possiamo fare
che e citare il codice di qualcun altro?

1227
01:01:40,821 --> 01:01:42,070
ANDI PENG: Sì, tutto bene.

1228
01:01:42,070 --> 01:01:44,320
Quindi, se voi ragazzi leggere il
spec, c'è una linea

1229
01:01:44,320 --> 01:01:48,310
nelle specifiche che dice voi ragazzi
sono totalmente gratuito per la ricerca di hash

1230
01:01:48,310 --> 01:01:51,070
funzioni quali sono alcune
delle funzioni hash rapidi

1231
01:01:51,070 --> 01:01:54,720
a correre le cose attraverso come
Finché si cita quel codice.

1232
01:01:54,720 --> 01:01:57,220
Così alcune persone hanno già
capito modi veloci

1233
01:01:57,220 --> 01:02:00,250
di fare correttori ortografici, di veloce
modalità di archiviazione delle informazioni.

1234
01:02:00,250 --> 01:02:02,750
Totalmente a voi ragazzi, se si
vuole prendere proprio questo, giusto?

1235
01:02:02,750 --> 01:02:04,045
Assicurarsi che si sta citando.

1236
01:02:04,045 --> 01:02:06,170
La sfida qui davvero
che stiamo cercando di testare

1237
01:02:06,170 --> 01:02:09,750
è fare in modo che si sa
il modo per aggirare puntatori.

1238
01:02:09,750 --> 01:02:12,700
Per quanto si attuazione
la reale funzione di hash

1239
01:02:12,700 --> 01:02:15,070
e venire con come
la matematica per farlo,

1240
01:02:15,070 --> 01:02:17,570
voi potete ricercare qualunque
metodi in linea voi ragazzi vogliono.

1241
01:02:17,570 --> 01:02:17,996
Sì?

1242
01:02:17,996 --> 01:02:19,700
>> PUBBLICO: Possiamo citare solo
utilizzando il [incomprensibile]?

1243
01:02:19,700 --> 01:02:20,120
>> ANDI PENG: Sì.

1244
01:02:20,120 --> 01:02:22,328
Si può solo, nel tuo commento,
si può citare come, oh,

1245
01:02:22,328 --> 01:02:26,127
tratto da bla, bla,
bla, funzione hash.

1246
01:02:26,127 --> 01:02:27,210
Qualcuno ha delle domande?

1247
01:02:27,210 --> 01:02:29,694
Abbiamo effettivamente bellicose
attraverso la sezione oggi.

1248
01:02:29,694 --> 01:02:31,610
Sarò qui a
rispondere alle domande pure.

1249
01:02:31,610 --> 01:02:36,570
>> Inoltre, come ho già detto, ufficio
ore stasera e domani.

1250
01:02:36,570 --> 01:02:40,307
Le specifiche di questa settimana è in realtà
super facile e super breve da leggere.

1251
01:02:40,307 --> 01:02:43,140
Vorrei suggerire di dare un'occhiata, basta
leggere attraverso la totalità di esso.

1252
01:02:43,140 --> 01:02:45,730
>> E Zamyla realtà ti guida
attraverso ciascuna delle funzioni

1253
01:02:45,730 --> 01:02:49,796
è necessario implementare, e quindi è
molto, molto chiaro come fare tutto.

1254
01:02:49,796 --> 01:02:51,920
Giusto per assicurarsi che si sta
tenere traccia dei puntatori.

1255
01:02:51,920 --> 01:02:53,650
Si tratta di un pset molto impegnativo.

1256
01:02:53,650 --> 01:02:56,744
>> Non è difficile perché, come,
oh, i concetti sono molto di più

1257
01:02:56,744 --> 01:02:59,160
difficile, o si deve imparare
tanto nuova sintassi il modo

1258
01:02:59,160 --> 01:03:00,650
che avete fatto per l'ultimo pset.

1259
01:03:00,650 --> 01:03:03,320
Questo pset è difficile perché
ci sono così tanti punti,

1260
01:03:03,320 --> 01:03:06,980
e quindi è molto, molto facile una volta
si dispone di un bug nel codice non essere in grado

1261
01:03:06,980 --> 01:03:08,315
per trovare dove tale bug è.

1262
01:03:08,315 --> 01:03:13,200
>> E così completa e la fede assoluta in te
ragazzi di essere in grado di battere il nostro [incomprensibile]

1263
01:03:13,200 --> 01:03:13,700
ortografia.

1264
01:03:13,700 --> 01:03:16,640
Io in realtà non ho alcuna mio scritto
ancora, ma sto per scrivere la mia.

1265
01:03:16,640 --> 01:03:19,070
Così, mentre si sta scrivendo
tuo, io scriverò la mia.

1266
01:03:19,070 --> 01:03:21,070
Ho intenzione di provare a fare
il mio più veloce della tua.

1267
01:03:21,070 --> 01:03:23,940
Vedremo chi ha quello più veloce.

1268
01:03:23,940 --> 01:03:27,340
>> E sì, vedrò tutti
voi ragazzi qui il Martedì.

1269
01:03:27,340 --> 01:03:29,510
Corro un genere come un laboratorio pset.

1270
01:03:29,510 --> 01:03:32,640
Tutte le sezioni questo
settimana sono laboratori pset,

1271
01:03:32,640 --> 01:03:36,690
così voi ragazzi hanno un sacco di opportunità
per chiedere aiuto, le ore d'ufficio come sempre,

1272
01:03:36,690 --> 01:03:41,330
e non vedo l'ora di
la lettura di tutti i codici vostri ragazzi '.

1273
01:03:41,330 --> 01:03:44,160
Ho quiz qui se
ragazzi vogliono venire ottenere quelle.

1274
01:03:44,160 --> 01:03:45,880
Questo è tutto.

1275
01:03:45,880 --> 01:03:48,180