1
00:00:00,000 --> 00:00:08,250

2
00:00:08,250 --> 00:00:12,680
>> JASON HIRSCHHORN: Benvenuti a tutti
alla sezione Seven.

3
00:00:12,680 --> 00:00:15,040
Siamo nella settimana di sette del corso.

4
00:00:15,040 --> 00:00:18,440
E questo prossimo Giovedi
Halloween è così io sono

5
00:00:18,440 --> 00:00:21,420
vestita come una zucca.

6
00:00:21,420 --> 00:00:23,460
Non riuscivo a piegarmi e mettere su
le mie scarpe, ecco perché io sono

7
00:00:23,460 --> 00:00:25,660
solo indossando calzini.

8
00:00:25,660 --> 00:00:29,220
Non sto anche indossare nulla sotto
questo, quindi non posso toglierlo se è

9
00:00:29,220 --> 00:00:29,950
distrazione a voi.

10
00:00:29,950 --> 00:00:31,860
Mi scuso in anticipo per questo.

11
00:00:31,860 --> 00:00:33,170
Non c'è bisogno di immaginare
cosa sta succedendo.

12
00:00:33,170 --> 00:00:34,240
Sto indossando boxer.

13
00:00:34,240 --> 00:00:36,170
Quindi va tutto bene.

14
00:00:36,170 --> 00:00:41,120
>> Ho una storia più lunga sul perché io sono
vestita come una zucca, ma ho intenzione di

15
00:00:41,120 --> 00:00:45,110
salvo che per avanti in questa sezione
perché io voglio iniziare.

16
00:00:45,110 --> 00:00:47,720
Abbiamo un sacco di cose interessanti
di andare oltre questa settimana.

17
00:00:47,720 --> 00:00:51,810
La maggior parte riguarda direttamente a questo
set problema della settimana, errori ortografici.

18
00:00:51,810 --> 00:00:54,680
Stiamo per andare oltre collegate
elenchi e tabelle hash

19
00:00:54,680 --> 00:00:57,160
per l'intera sezione.

20
00:00:57,160 --> 00:01:02,490
Ho messo questa lista ogni settimana, una lista di
risorse per voi per aiutarvi con

21
00:01:02,490 --> 00:01:04,120
il materiale in questo corso.

22
00:01:04,120 --> 00:01:07,600
Se in perdita o se cerca di qualche
ulteriori informazioni, controllare uno dei

23
00:01:07,600 --> 00:01:09,930
queste risorse.

24
00:01:09,930 --> 00:01:14,530
>> Anche in questo caso, è pset6 errori di ortografia,
pset di questa settimana.

25
00:01:14,530 --> 00:01:17,690
E ti incoraggia, e mi
incoraggiare, usare qualche altro

26
00:01:17,690 --> 00:01:20,320
risorse specificamente per questo pset.

27
00:01:20,320 --> 00:01:23,390
In particolare, i tre che ho
elencati sullo schermo -

28
00:01:23,390 --> 00:01:27,160
gdb, che siamo stati a conoscenza
ed è stato usato per un po 'di tempo, è

29
00:01:27,160 --> 00:01:29,270
sarà molto utile questa settimana.

30
00:01:29,270 --> 00:01:30,190
Così ho messo che fino qui.

31
00:01:30,190 --> 00:01:32,910
Ma ogni volta che si lavora con C,
si dovrebbe sempre utilizzare gdb

32
00:01:32,910 --> 00:01:34,430
eseguire il debug dei programmi.

33
00:01:34,430 --> 00:01:36,660
Questa settimana anche valgrind.

34
00:01:36,660 --> 00:01:38,535
Qualcuno sa che cosa valgrind fa?

35
00:01:38,535 --> 00:01:42,184

36
00:01:42,184 --> 00:01:43,890
>> AUDIENCE: Verifica le perdite di memoria?

37
00:01:43,890 --> 00:01:45,950
>> JASON HIRSCHHORN: Valgrind
i controlli per le perdite di memoria.

38
00:01:45,950 --> 00:01:49,970
Quindi, se si malloc qualcosa nella vostra
programma, si sta chiedendo per la memoria.

39
00:01:49,970 --> 00:01:52,920
Alla fine del programma, è necessario
scrivere libera su tutto ciò che hai

40
00:01:52,920 --> 00:01:54,800
malloced per dare la memoria indietro.

41
00:01:54,800 --> 00:01:58,420
Se non si scrive libero alla fine e
il programma arriva ad una conclusione,

42
00:01:58,420 --> 00:02:00,000
tutto automaticamente
essere liberato.

43
00:02:00,000 --> 00:02:02,340
E per i piccoli programmi, è
Non un grosso problema.

44
00:02:02,340 --> 00:02:05,250
Ma se si sta scrivendo una corsa più lunga
programma che non smettere,

45
00:02:05,250 --> 00:02:09,180
necessariamente, in un paio di minuti o un
paio di secondi, poi perdite di memoria

46
00:02:09,180 --> 00:02:10,710
può diventare un affare enorme.

47
00:02:10,710 --> 00:02:14,940
>> Così per pset6, l'aspettativa è che
si avrà perdite di memoria a zero con

48
00:02:14,940 --> 00:02:15,910
il vostro programma.

49
00:02:15,910 --> 00:02:18,690
Per verificare la presenza di perdite di memoria, valgrind eseguire
e vi darà qualche bella

50
00:02:18,690 --> 00:02:21,190
Uscita ti permette di sapere se
o non tutto era gratuito.

51
00:02:21,190 --> 00:02:23,940
Ti pratica in un secondo momento
oggi, si spera.

52
00:02:23,940 --> 00:02:25,790
>> Infine, il comando diff.

53
00:02:25,790 --> 00:02:28,900
Hai usato qualcosa di simile ad esso
in pset5 con lo strumento peek.

54
00:02:28,900 --> 00:02:30,780
Permesso di guardare dentro.

55
00:02:30,780 --> 00:02:33,400
Hai usato anche diff, troppo, per
il problema set spec.

56
00:02:33,400 --> 00:02:35,950
Ma in voi permesso di
confrontare due file.

57
00:02:35,950 --> 00:02:39,180
Si potrebbe paragonare il file bitmap e
Informazioni intestazioni di una soluzione personale e

58
00:02:39,180 --> 00:02:42,200
la soluzione in pset5 se
si è scelto di utilizzare.

59
00:02:42,200 --> 00:02:44,030
Diff vi permetterà di
farlo, pure.

60
00:02:44,030 --> 00:02:48,620
È possibile confrontare la risposta corretta per
Il problema di questa settimana impostato per la tua risposta

61
00:02:48,620 --> 00:02:52,210
e vedere se si allinei o vedere
dove gli errori sono.

62
00:02:52,210 --> 00:02:55,870
>> Quindi questi sono tre ottimi strumenti che
si consiglia di utilizzare per questa settimana, e

63
00:02:55,870 --> 00:02:58,130
controllare definitivamente il programma
con questi tre strumenti

64
00:02:58,130 --> 00:03:00,520
Prima di accendere dentro

65
00:03:00,520 --> 00:03:04,650
Ancora una volta, come ho già detto ogni settimana,
se avete tutte le risposte per me - sia

66
00:03:04,650 --> 00:03:06,470
positivo e costruttivo -

67
00:03:06,470 --> 00:03:09,930
sentitevi liberi di andare al sito
nella parte inferiore di questa diapositiva

68
00:03:09,930 --> 00:03:11,270
e ingresso lì.

69
00:03:11,270 --> 00:03:13,440
Ho davvero apprezzato ogni
e tutti i feedback.

70
00:03:13,440 --> 00:03:17,360
E se mi dai le cose specifiche che
Posso fare per migliorare o che sono

71
00:03:17,360 --> 00:03:21,350
facendo bene che mi volete
Continuo, mi prendo a cuore e

72
00:03:21,350 --> 00:03:24,040
davvero cercare difficile da ascoltare
per le vostre risposte.

73
00:03:24,040 --> 00:03:27,720
Non posso promettere che ho intenzione di fare
tutto, anche se, come indossare un

74
00:03:27,720 --> 00:03:30,700
zucca costume ogni settimana.

75
00:03:30,700 --> 00:03:34,020
>> Così ci accingiamo a trascorrere la maggior parte del
sezione, come ho detto, parlando

76
00:03:34,020 --> 00:03:37,240
liste concatenate e tabelle hash, che
saranno direttamente applicabile alla

77
00:03:37,240 --> 00:03:38,780
problema impostare questa settimana.

78
00:03:38,780 --> 00:03:42,580
Liste concatenate andremo oltre relativamente
rapidamente perché abbiamo passato un bel po '

79
00:03:42,580 --> 00:03:44,930
di tempo che va su di esso in sezione.

80
00:03:44,930 --> 00:03:48,680
E così ci arriveremo direttamente nel
problemi di codifica per le liste collegate.

81
00:03:48,680 --> 00:03:52,740
E poi alla fine ne parleremo
hash tabelle e come si applicano a questo

82
00:03:52,740 --> 00:03:55,280
problema della settimana impostato.

83
00:03:55,280 --> 00:03:57,560
>> Hai visto questo codice prima.

84
00:03:57,560 --> 00:04:02,730
Questa è una struttura, e sta definendo
qualcosa di nuovo chiamato un nodo.

85
00:04:02,730 --> 00:04:10,660
E all'interno di un nodo è un numero intero
qui e là è un puntatore a

86
00:04:10,660 --> 00:04:11,830
un altro nodo.

87
00:04:11,830 --> 00:04:12,790
Abbiamo visto prima.

88
00:04:12,790 --> 00:04:14,830
Questo è stato in arrivo per
un paio di settimane ormai.

89
00:04:14,830 --> 00:04:18,680
Esso combina puntatori, che siamo stati
lavorare con, e le strutture, che permettono

90
00:04:18,680 --> 00:04:22,079
di combinare due diversi
cose in un tipo di dati.

91
00:04:22,079 --> 00:04:24,830

92
00:04:24,830 --> 00:04:26,490
>> Ci sono un sacco di cose su schermo.

93
00:04:26,490 --> 00:04:30,220
Ma tutto questo dovrebbe essere relativamente
familiarità con voi.

94
00:04:30,220 --> 00:04:33,810
Nella prima riga, abbiamo
dichiarare un nuovo nodo.

95
00:04:33,810 --> 00:04:41,650
E poi all'interno di tale nuovo nodo, ho impostato
il numero intero in quel nodo per uno.

96
00:04:41,650 --> 00:04:44,950
Vediamo sulla riga successiva sto facendo un
printf comando, ma ho visualizzati in grigio

97
00:04:44,950 --> 00:04:48,080
il comando printf, perché la realtà
parte importante è questa linea qui -

98
00:04:48,080 --> 00:04:50,020
new_node.n.

99
00:04:50,020 --> 00:04:51,270
Cosa fa il punto significa?

100
00:04:51,270 --> 00:04:53,810

101
00:04:53,810 --> 00:04:57,240
>> PUBBLICO: Andare al nodo e
valutare il valore di n per esso.

102
00:04:57,240 --> 00:04:58,370
>> JASON HIRSCHHORN: Ecco
esattamente a destra.

103
00:04:58,370 --> 00:05:03,300
Dot significa accedere alla parte n
di questo nuovo nodo.

104
00:05:03,300 --> 00:05:05,690
Questa riga successiva fa che cosa?

105
00:05:05,690 --> 00:05:16,140

106
00:05:16,140 --> 00:05:17,050
Michael.

107
00:05:17,050 --> 00:05:21,910
>> AUDIENCE: Crea un altro nodo
che punterà al nuovo nodo.

108
00:05:21,910 --> 00:05:24,870
>> JASON HIRSCHHORN: Quindi non lo fa
creare un nuovo nodo.

109
00:05:24,870 --> 00:05:26,120
Si crea una cosa?

110
00:05:26,120 --> 00:05:28,300

111
00:05:28,300 --> 00:05:29,300
>> PUBBLICO: Un puntatore.

112
00:05:29,300 --> 00:05:33,460
>> JASON HIRSCHHORN: Un puntatore a un nodo,
come indicato da questo nodo * qui.

113
00:05:33,460 --> 00:05:34,800
Così crea un puntatore a un nodo.

114
00:05:34,800 --> 00:05:37,490
E quale nodo si è rivolta
a, Michael?

115
00:05:37,490 --> 00:05:38,440
>> AUDIENCE: Nuovo nodo?

116
00:05:38,440 --> 00:05:39,240
>> JASON HIRSCHHORN: Nuovo nodo.

117
00:05:39,240 --> 00:05:43,020
Ed è lì che punta perché abbiamo
dato l'indirizzo del nuovo nodo.

118
00:05:43,020 --> 00:05:45,820
E ora in questa linea vediamo
due modi diversi di

119
00:05:45,820 --> 00:05:46,910
esprimendo la stessa cosa.

120
00:05:46,910 --> 00:05:49,650
E volevo sottolineare come questi
due cose sono le stesse.

121
00:05:49,650 --> 00:05:54,740
Nella prima riga, abbiamo dereferenziare
il puntatore.

122
00:05:54,740 --> 00:05:55,830
Così andiamo al nodo.

123
00:05:55,830 --> 00:05:56,830
Questo è ciò che significa questa stella.

124
00:05:56,830 --> 00:05:57,930
Abbiamo visto che prima con i puntatori.

125
00:05:57,930 --> 00:05:59,280
Vai a quel nodo.

126
00:05:59,280 --> 00:06:00,370
Questo è tra parentesi.

127
00:06:00,370 --> 00:06:04,610
E poi accedere tramite l'operatore punto
l'elemento n di tale nodo.

128
00:06:04,610 --> 00:06:08,430
>> Così che sta prendendo la sintassi
abbiamo visto proprio qui e ora

129
00:06:08,430 --> 00:06:09,670
utilizzarlo con un puntatore.

130
00:06:09,670 --> 00:06:13,730
Naturalmente, diventa un po 'affollato, se
si sta scrivendo queste parentesi -

131
00:06:13,730 --> 00:06:14,940
quella stella e quel puntino.

132
00:06:14,940 --> 00:06:16,220
Si diventa un po 'affollato.

133
00:06:16,220 --> 00:06:18,500
Così abbiamo un po 'di zucchero sintattico.

134
00:06:18,500 --> 00:06:19,920
E questa linea qui -

135
00:06:19,920 --> 00:06:21,170
ptr_node-> n.

136
00:06:21,170 --> 00:06:25,400

137
00:06:25,400 --> 00:06:28,000
Che fa la stessa cosa esatta.

138
00:06:28,000 --> 00:06:30,840
Così, queste due linee di codice sono
equivalenti e farà

139
00:06:30,840 --> 00:06:31,650
la stessa identica cosa.

140
00:06:31,650 --> 00:06:34,210
>> Ma ho voluto segnalare quelli fuori prima
di andare avanti in modo da capire

141
00:06:34,210 --> 00:06:39,000
che in realtà questa cosa qui è
solo zucchero sintattico per dereferencing

142
00:06:39,000 --> 00:06:44,200
il puntatore e poi andare a
la parte n di tale struttura.

143
00:06:44,200 --> 00:06:45,525
Avete domande su questa diapositiva?

144
00:06:45,525 --> 00:06:53,020

145
00:06:53,020 --> 00:06:54,390
OK.

146
00:06:54,390 --> 00:06:58,510
>> Quindi stiamo andando a passare attraverso una coppia
di operazioni che si possono fare su

147
00:06:58,510 --> 00:06:59,730
liste collegate.

148
00:06:59,730 --> 00:07:05,770
Una lista concatenata, di richiamo, è una serie di
nodi che puntano l'uno all'altro.

149
00:07:05,770 --> 00:07:12,470
E noi di solito cominciamo con un puntatore
chiamato testa, in generale, che punta a

150
00:07:12,470 --> 00:07:14,040
la prima cosa nella lista.

151
00:07:14,040 --> 00:07:18,900
Così, sulla prima riga qui,
avere prima il nostro L originale.

152
00:07:18,900 --> 00:07:21,370
Quindi, che cosa si può pensare - questo
testo proprio qui si può pensare come

153
00:07:21,370 --> 00:07:23,560
solo il puntatore che abbiamo memorizzato
che da qualche parte i punti

154
00:07:23,560 --> 00:07:24,670
al primo elemento.

155
00:07:24,670 --> 00:07:27,500
E in questa lista collegata
abbiamo quattro nodi.

156
00:07:27,500 --> 00:07:29,530
Ogni nodo è una grande scatola.

157
00:07:29,530 --> 00:07:33,430
La casella più grande all'interno del grande
scatola è la parte intera.

158
00:07:33,430 --> 00:07:37,400
E poi abbiamo una parte puntatore.

159
00:07:37,400 --> 00:07:39,630
>> Queste scatole non sono attratti
scala perché come è grande

160
00:07:39,630 --> 00:07:42,320
un numero intero in byte?

161
00:07:42,320 --> 00:07:43,290
Quanto è grande ora?

162
00:07:43,290 --> 00:07:43,710
Quattro.

163
00:07:43,710 --> 00:07:45,470
E quanto grande è un puntatore?

164
00:07:45,470 --> 00:07:45,940
Quattro.

165
00:07:45,940 --> 00:07:48,180
Quindi, in realtà, se dovessimo disegnare
questo per scalare entrambe le caselle

166
00:07:48,180 --> 00:07:49,690
sarebbe la stessa dimensione.

167
00:07:49,690 --> 00:07:52,870
In questo caso, vogliamo inserire
qualcosa nella lista collegata.

168
00:07:52,870 --> 00:07:57,190
Così si può vedere qui stiamo inserendo
cinque attraversiamo attraverso l'

169
00:07:57,190 --> 00:08:01,310
lista collegata, trovare dove cinque
va, quindi inserirla.

170
00:08:01,310 --> 00:08:03,560
>> Rompiamo che verso il basso e andare
un po 'più lentamente.

171
00:08:03,560 --> 00:08:05,510
Ho intenzione di puntare alla scheda.

172
00:08:05,510 --> 00:08:09,930
Così abbiamo la nostra nodo cinque che
abbiamo creato in mallocs.

173
00:08:09,930 --> 00:08:11,190
Perché tutti ridono?

174
00:08:11,190 --> 00:08:12,130
Sto scherzando.

175
00:08:12,130 --> 00:08:13,310
OK.

176
00:08:13,310 --> 00:08:14,820
Così abbiamo malloced cinque.

177
00:08:14,820 --> 00:08:16,310
Abbiamo creato questo nodo
da qualche altra parte.

178
00:08:16,310 --> 00:08:17,740
Dobbiamo pronto ad andare.

179
00:08:17,740 --> 00:08:20,130
Partiamo nella parte anteriore del
la nostra lista con due.

180
00:08:20,130 --> 00:08:22,380
E vogliamo inserire
in modo ordinato.

181
00:08:22,380 --> 00:08:27,550
>> Quindi, se vediamo due e vogliamo mettere
in cinque, cosa facciamo quando vediamo

182
00:08:27,550 --> 00:08:28,800
qualcosa meno di noi?

183
00:08:28,800 --> 00:08:31,850

184
00:08:31,850 --> 00:08:33,520
Cosa?

185
00:08:33,520 --> 00:08:36,750
Vogliamo inserire cinque in questo
lista collegata, mantenendolo ordinato.

186
00:08:36,750 --> 00:08:37,520
Vediamo numero due.

187
00:08:37,520 --> 00:08:38,769
Allora cosa facciamo?

188
00:08:38,769 --> 00:08:39,179
Marcus?

189
00:08:39,179 --> 00:08:40,679
>> AUDIENCE: Chiamare il puntatore
al nodo successivo.

190
00:08:40,679 --> 00:08:42,530
>> JASON HIRSCHHORN: E perché
andiamo al prossimo?

191
00:08:42,530 --> 00:08:45,970
>> AUDIENCE: Perché è l'
nodo successivo nella lista.

192
00:08:45,970 --> 00:08:48,310
E sappiamo solo che altra posizione.

193
00:08:48,310 --> 00:08:50,410
>> JASON HIRSCHHORN: E cinque è maggiore
di due, in particolare.

194
00:08:50,410 --> 00:08:51,600
Perché vogliamo tenerlo ordinato.

195
00:08:51,600 --> 00:08:52,730
Così cinque è maggiore di due.

196
00:08:52,730 --> 00:08:54,460
Quindi si passa a quello successivo.

197
00:08:54,460 --> 00:08:55,240
Ed ora arriviamo a quattro.

198
00:08:55,240 --> 00:08:56,490
E cosa succede quando arriviamo a quattro?

199
00:08:56,490 --> 00:08:58,920

200
00:08:58,920 --> 00:09:00,310
>> Cinque è maggiore di quattro.

201
00:09:00,310 --> 00:09:01,460
Quindi noi continuiamo.

202
00:09:01,460 --> 00:09:03,110
E ora siamo a sei.

203
00:09:03,110 --> 00:09:04,360
E che cosa vediamo alle sei?

204
00:09:04,360 --> 00:09:08,672

205
00:09:08,672 --> 00:09:09,608
Sì, Carlos?

206
00:09:09,608 --> 00:09:10,544
>> AUDIENCE: Six è maggiore di cinque.

207
00:09:10,544 --> 00:09:11,480
>> JASON HIRSCHHORN: Six è
maggiore di cinque.

208
00:09:11,480 --> 00:09:13,660
Ecco, questo è dove vogliamo
inserire cinque.

209
00:09:13,660 --> 00:09:17,320
Tuttavia, tenere presente che se si
hanno un solo puntatore qui -

210
00:09:17,320 --> 00:09:19,840
questo è il nostro puntatore in più che è
attraversando l'elenco.

211
00:09:19,840 --> 00:09:21,860
E stiamo puntando a sei.

212
00:09:21,860 --> 00:09:25,010
Abbiamo perso traccia di ciò che
viene prima delle sei.

213
00:09:25,010 --> 00:09:29,130
Quindi, se vogliamo inserire un elemento in
questa lista mantenendolo ordinato, abbiamo

214
00:09:29,130 --> 00:09:31,630
probabilmente bisogno di quanti puntatori?

215
00:09:31,630 --> 00:09:32,280
>> AUDIENCE: Two.

216
00:09:32,280 --> 00:09:32,920
>> JASON Hirschorn: Two.

217
00:09:32,920 --> 00:09:35,720
Uno per tenere traccia della corrente
uno e uno per tenere traccia di

218
00:09:35,720 --> 00:09:37,050
quello precedente.

219
00:09:37,050 --> 00:09:38,450
Questa è solo una lista concatenata.

220
00:09:38,450 --> 00:09:39,670
Va sola direzione.

221
00:09:39,670 --> 00:09:43,220
Se avessimo una lista doppiamente concatenata, dove
tutto era rivolta verso la cosa

222
00:09:43,220 --> 00:09:46,240
dopo di essa e la cosa prima, poi
non avremmo bisogno di farlo.

223
00:09:46,240 --> 00:09:49,350
Ma in questo caso non vogliamo perdere
traccia di ciò che è venuto prima di noi in caso

224
00:09:49,350 --> 00:09:53,350
abbiamo bisogno di inserire cinque da qualche parte
nel mezzo.

225
00:09:53,350 --> 00:09:55,610
Dire che siamo rimasti inseriamo nove.

226
00:09:55,610 --> 00:09:57,260
Che cosa accadrebbe se
siamo arrivati ​​a otto?

227
00:09:57,260 --> 00:10:01,860

228
00:10:01,860 --> 00:10:04,880
>> PUBBLICO: Dovreste
ottenere che il punto zero.

229
00:10:04,880 --> 00:10:07,820
Invece di avere punto zero si avrebbe
aggiungere un elemento e quindi avere

230
00:10:07,820 --> 00:10:09,216
puntare a nove.

231
00:10:09,216 --> 00:10:09,700
>> JASON Hirschorn: Esattamente.

232
00:10:09,700 --> 00:10:10,600
Così otteniamo otto.

233
00:10:10,600 --> 00:10:13,140
Arriviamo alla fine della lista, perché
questo sta puntando a null.

234
00:10:13,140 --> 00:10:16,330
E adesso, invece di puntare a
nullo dobbiamo puntare al nostro nuovo nodo.

235
00:10:16,330 --> 00:10:19,870
E abbiamo impostato il puntatore
il nostro nuovo nodo a null.

236
00:10:19,870 --> 00:10:21,445
Qualcuno ha domande
sull'inserimento?

237
00:10:21,445 --> 00:10:25,620

238
00:10:25,620 --> 00:10:28,100
Cosa succede se non mi preoccupo
mantenere la lista ordinata?

239
00:10:28,100 --> 00:10:31,701

240
00:10:31,701 --> 00:10:34,350
>> AUDIENCE: Bastone alla
inizio o fine.

241
00:10:34,350 --> 00:10:35,510
>> JASON Hirschorn: Bastone a
l'inizio o la fine.

242
00:10:35,510 --> 00:10:37,276
Quale dovremmo fare?

243
00:10:37,276 --> 00:10:38,770
Bobby?

244
00:10:38,770 --> 00:10:41,020
Perché alla fine?

245
00:10:41,020 --> 00:10:43,250
>> AUDIENCE: perché l'inizio
è già riempito.

246
00:10:43,250 --> 00:10:43,575
>> JASON Hirschorn: OK.

247
00:10:43,575 --> 00:10:44,360
L'inizio è già piena.

248
00:10:44,360 --> 00:10:46,090
Chi vuole argomentare contro Bobby.

249
00:10:46,090 --> 00:10:47,290
Marcus.

250
00:10:47,290 --> 00:10:48,910
>> AUDIENCE: Beh, probabilmente si desidera
bastone all'inizio perché

251
00:10:48,910 --> 00:10:50,140
altrimenti se lo metti a
Alla fine dovreste

252
00:10:50,140 --> 00:10:51,835
attraversare l'intero elenco.

253
00:10:51,835 --> 00:10:52,990
>> JASON Hirschorn: Esattamente.

254
00:10:52,990 --> 00:10:57,970
Quindi, se stiamo pensando di runtime, l'
runtime di inserimento alla fine

255
00:10:57,970 --> 00:11:00,110
sarebbe n, la dimensione di questo.

256
00:11:00,110 --> 00:11:03,080
Qual è la grande O runtime di inserimento
all'inizio?

257
00:11:03,080 --> 00:11:04,170
Costante di tempo.

258
00:11:04,170 --> 00:11:07,075
Quindi, se non si cura di tenere
qualcosa di ordinato, molto meglio solo

259
00:11:07,075 --> 00:11:08,420
inserire all'inizio di questa lista.

260
00:11:08,420 --> 00:11:10,320
E questo può essere fatto in tempo costante.

261
00:11:10,320 --> 00:11:13,900

262
00:11:13,900 --> 00:11:14,690
>> OK.

263
00:11:14,690 --> 00:11:18,870
Operazione successiva è trovare, che altro -
abbiamo formulato questo come ricerca.

264
00:11:18,870 --> 00:11:22,470
Ma stiamo andando a guardare attraverso il
lista collegata per qualche oggetto.

265
00:11:22,470 --> 00:11:26,000
Voi ragazzi avete visto il codice per
verificare prima in conferenza.

266
00:11:26,000 --> 00:11:29,490
Ma abbiamo una sorta di appena fatto con
inserire, o almeno inserimento

267
00:11:29,490 --> 00:11:30,580
qualcosa ordinati.

268
00:11:30,580 --> 00:11:36,350
Si guarda attraverso, andando nodo per nodo,
fino a trovare il numero che si sta

269
00:11:36,350 --> 00:11:37,780
cercando.

270
00:11:37,780 --> 00:11:39,670
Cosa succede se si raggiunge
la fine della lista?

271
00:11:39,670 --> 00:11:43,020
Dire che sto cercando nove e io
raggiungere la fine dell'elenco.

272
00:11:43,020 --> 00:11:44,270
Che cosa facciamo?

273
00:11:44,270 --> 00:11:47,147

274
00:11:47,147 --> 00:11:48,110
>> AUDIENCE: Ritorno falso?

275
00:11:48,110 --> 00:11:48,690
>> JASON Hirschorn: Ritorno false.

276
00:11:48,690 --> 00:11:49,960
Non abbiamo trovato.

277
00:11:49,960 --> 00:11:52,010
Se si raggiunge la fine della lista e
Non avete trovato il numero sei

278
00:11:52,010 --> 00:11:54,170
cercando, non è lì.

279
00:11:54,170 --> 00:11:55,420
Hai domande su trovare?

280
00:11:55,420 --> 00:11:59,530

281
00:11:59,530 --> 00:12:04,615
Se questo fosse un elenco ordinato, cosa sarebbe
essere diverso per la nostra ricerca?

282
00:12:04,615 --> 00:12:07,370

283
00:12:07,370 --> 00:12:08,103
Già.

284
00:12:08,103 --> 00:12:10,600
>> AUDIENCE: Sarebbe trovare il primo valore
che è maggiore di quello

285
00:12:10,600 --> 00:12:12,390
stai cercando e
poi tornare false.

286
00:12:12,390 --> 00:12:13,190
>> JASON Hirschorn: Esattamente.

287
00:12:13,190 --> 00:12:17,310
Quindi, se si tratta di un elenco ordinato, se si arriva a
qualcosa che è più grande di quello

288
00:12:17,310 --> 00:12:20,180
stiamo cercando, non abbiamo bisogno di
proseguire fino alla fine della lista.

289
00:12:20,180 --> 00:12:24,060
A quel punto possiamo tornare falso
perché non stiamo andando a trovarlo.

290
00:12:24,060 --> 00:12:27,340
La domanda è ora, abbiamo parlato
mantenendo liste collegate ordinati,

291
00:12:27,340 --> 00:12:28,180
tenerli indifferenziati.

292
00:12:28,180 --> 00:12:30,050
Che sta per essere qualcosa che ti
probabilmente andando ad avere per pensare

293
00:12:30,050 --> 00:12:34,240
quando la codifica problema impostato cinque se si
scegliere una tabella hash con separata

294
00:12:34,240 --> 00:12:36,360
approccio concatenamento, che
parleremo più avanti.

295
00:12:36,360 --> 00:12:41,400
>> Ma ne vale la pena di tenere aggiornato l'elenco
ordinato e quindi essere in grado di avere forse

296
00:12:41,400 --> 00:12:42,310
ricerche più rapide?

297
00:12:42,310 --> 00:12:47,220
O è meglio per inserire rapidamente
qualcosa in runtime costante ma poi

298
00:12:47,220 --> 00:12:48,430
avere più la ricerca?

299
00:12:48,430 --> 00:12:52,250
Questo è un compromesso proprio lì che si
arrivare a decidere che cosa è più appropriato

300
00:12:52,250 --> 00:12:53,590
per il problema specifico.

301
00:12:53,590 --> 00:12:56,680
E non c'è necessariamente una
risposta assolutamente ragione.

302
00:12:56,680 --> 00:12:59,520
Ma è certamente una decisione che si ottiene
per fare, e probabilmente buona per difendere

303
00:12:59,520 --> 00:13:05,270
che, per esempio, un commento o due perché
si è scelto uno sopra l'altro.

304
00:13:05,270 --> 00:13:06,490
>> Infine, l'eliminazione.

305
00:13:06,490 --> 00:13:08,100
Abbiamo visto l'eliminazione.

306
00:13:08,100 --> 00:13:09,180
E 'simile alla ricerca.

307
00:13:09,180 --> 00:13:11,020
Cerchiamo l'elemento.

308
00:13:11,020 --> 00:13:12,390
Dire che stiamo cercando di eliminare sei.

309
00:13:12,390 --> 00:13:14,450
Così troviamo sei proprio qui.

310
00:13:14,450 --> 00:13:18,860
La cosa che dobbiamo fare in modo che
fare è che tutto ciò che sta puntando

311
00:13:18,860 --> 00:13:21,220
sei - come si vede nel passaggio
due quaggiù -

312
00:13:21,220 --> 00:13:26,500
tutto ciò che sta indicando sei esigenze di
saltare sei adesso e essere cambiato

313
00:13:26,500 --> 00:13:28,160
qualunque cosa sei sta indicando.

314
00:13:28,160 --> 00:13:31,410
Noi non vogliamo orfano sempre il resto della
la nostra lista dimenticando di set che

315
00:13:31,410 --> 00:13:32,960
puntatore precedente.

316
00:13:32,960 --> 00:13:35,960
E poi a volte, a seconda
sul programma, faranno solo

317
00:13:35,960 --> 00:13:37,380
eliminare del tutto questo nodo.

318
00:13:37,380 --> 00:13:40,135
A volte si desidera restituire
il valore che è in questo nodo.

319
00:13:40,135 --> 00:13:42,490
Ecco come funziona l'eliminazione.

320
00:13:42,490 --> 00:13:44,610
Tutte le domande di eliminare?

321
00:13:44,610 --> 00:13:51,280

322
00:13:51,280 --> 00:13:53,850
>> AUDIENCE: Quindi, se avete intenzione di eliminare
si, ti basta usare gratuitamente perché

323
00:13:53,850 --> 00:13:55,655
presumibilmente fu malloced?

324
00:13:55,655 --> 00:13:57,976
>> JASON Hirschorn: Se si desidera liberare
qualcosa che è esattamente a destra e si

325
00:13:57,976 --> 00:13:58,540
malloced esso.

326
00:13:58,540 --> 00:14:00,410
Dire abbiamo voluto restituire questo valore.

327
00:14:00,410 --> 00:14:04,010
Potremmo tornare a sei e poi libero
questo nodo e chiamata gratis su di esso.

328
00:14:04,010 --> 00:14:06,180
Oppure avremmo probabilmente chiamiamo libero prima
e poi tornare a sei.

329
00:14:06,180 --> 00:14:11,210

330
00:14:11,210 --> 00:14:11,580
>> OK.

331
00:14:11,580 --> 00:14:14,010
Quindi passiamo alla pratica di codifica.

332
00:14:14,010 --> 00:14:16,090
Stiamo andando a codificare tre funzioni.

333
00:14:16,090 --> 00:14:18,260
Il primo si chiama insert_node.

334
00:14:18,260 --> 00:14:22,170
Così avete il codice che ti ho mandato, e
se stai guardando questo più avanti

335
00:14:22,170 --> 00:14:28,020
è possibile accedere al codice linked.c
sul sito CS50.

336
00:14:28,020 --> 00:14:30,880
Ma in linked.c, c'è qualche
codice scheletro che è già

337
00:14:30,880 --> 00:14:32,280
stato scritto per voi.

338
00:14:32,280 --> 00:14:34,560
E poi ci sono un paio di funzioni
è necessario scrivere.

339
00:14:34,560 --> 00:14:36,380
>> In primo luogo stiamo andando a
scrivere insert_node.

340
00:14:36,380 --> 00:14:39,800
E cosa insert_node fa
IS inserisce un numero intero.

341
00:14:39,800 --> 00:14:42,440
E si sta dando il numero intero
in una lista collegata.

342
00:14:42,440 --> 00:14:45,470
E in particolare, è necessario
per mantenere la lista ordinata

343
00:14:45,470 --> 00:14:47,650
dal più piccolo al più grande.

344
00:14:47,650 --> 00:14:51,360
Inoltre, non si vuole
inserire eventuali duplicati.

345
00:14:51,360 --> 00:14:54,600
Infine, come si può vedere insert_node
restituisce un bool.

346
00:14:54,600 --> 00:14:57,140
Quindi si suppone di consentire all'utente di sapere
se l'inserto era

347
00:14:57,140 --> 00:15:00,800
di successo, restituendo vero o falso.

348
00:15:00,800 --> 00:15:02,580
Alla fine di questo programma -

349
00:15:02,580 --> 00:15:05,750
e per questa fase non è necessario
preoccuparsi di liberare nulla.

350
00:15:05,750 --> 00:15:11,790
Quindi tutto quello che stai facendo è prendere un intero
e inserendolo in un elenco.

351
00:15:11,790 --> 00:15:13,890
>> Questo è quello che ti sto chiedendo di fare adesso.

352
00:15:13,890 --> 00:15:17,620
Ancora una volta, nel linked.c, che si
hanno tutti, è il codice scheletro.

353
00:15:17,620 --> 00:15:20,980
E si dovrebbe vedere verso il basso
la dichiarazione di funzione di esempio.

354
00:15:20,980 --> 00:15:27,390
Tuttavia, prima di andare in codificarlo
in C, vivamente vi incoraggio ad andare

355
00:15:27,390 --> 00:15:29,330
attraverso le fasi siamo stati
praticare ogni settimana.

356
00:15:29,330 --> 00:15:31,100
Abbiamo già passati attraverso
una foto di questo.

357
00:15:31,100 --> 00:15:33,380
Quindi, si dovrebbe avere una certa comprensione
di come funziona.

358
00:15:33,380 --> 00:15:36,590
Ma vorrei incoraggiarvi a scrivere
alcuni pseudocodice prima di tuffarsi dentro

359
00:15:36,590 --> 00:15:38,640
E stiamo per andare oltre
pseudocodice come gruppo.

360
00:15:38,640 --> 00:15:41,470
E poi una volta che hai scritto la tua
pseudocodice, e una volta abbiamo scritto il nostro

361
00:15:41,470 --> 00:15:45,850
pseudocodice come gruppo, è possibile
andare in codifica in C.

362
00:15:45,850 --> 00:15:49,980
>> Come un testa a testa, la funzione insert_node
è probabilmente il più difficile di

363
00:15:49,980 --> 00:15:53,550
tre stiamo andando a scrivere perché io
aggiunto alcuni vincoli aggiuntivi per

364
00:15:53,550 --> 00:15:57,190
la programmazione, in particolare, che
non avete intenzione di inserire qualsiasi

365
00:15:57,190 --> 00:15:59,880
duplicati e che l'elenco
dovrebbe rimanere ordinato.

366
00:15:59,880 --> 00:16:02,660
Quindi questo è un programma non banale
che è necessario codificare.

367
00:16:02,660 --> 00:16:06,470
E perché non ti prendi 5-7
minuti solo per ottenere lavorando sulla

368
00:16:06,470 --> 00:16:07,640
pseudocodice e il codice.

369
00:16:07,640 --> 00:16:09,460
E poi inizieremo
andando come un gruppo.

370
00:16:09,460 --> 00:16:11,680
Anche in questo caso, se avete appena tutte le domande
alzare la mano e vengo in giro.

371
00:16:11,680 --> 00:16:15,258

372
00:16:15,258 --> 00:16:16,508
.

373
00:16:16,508 --> 00:18:28,370

374
00:18:28,370 --> 00:18:30,120
>> Abbiamo anche generalmente facciamo questi -

375
00:18:30,120 --> 00:18:32,070
o io non esplicitamente dici
in grado di lavorare con le persone.

376
00:18:32,070 --> 00:18:36,500
Ma, ovviamente, altamente vi incoraggio,
se avete domande, chiedere al

377
00:18:36,500 --> 00:18:39,840
vicino seduto accanto a te
o anche lavorare con qualcuno

378
00:18:39,840 --> 00:18:40,510
altrimenti se si vuole.

379
00:18:40,510 --> 00:18:42,600
Ciò non deve essere un individuo
attività di silenzio.

380
00:18:42,600 --> 00:20:11,770

381
00:20:11,770 --> 00:20:16,330
>> Cominciamo con la scrittura di alcuni
pseudocodice sulla scheda.

382
00:20:16,330 --> 00:20:19,395
Chi mi può dare la prima linea di
pseudocodice per questo programma?

383
00:20:19,395 --> 00:20:22,240

384
00:20:22,240 --> 00:20:23,640
Per questa funzione, piuttosto -
insert_node.

385
00:20:23,640 --> 00:20:29,960

386
00:20:29,960 --> 00:20:31,830
Alden?

387
00:20:31,830 --> 00:20:36,560
>> AUDIENCE: Quindi la prima cosa che ho fatto è stato
creare un nuovo puntatore al nodo e

388
00:20:36,560 --> 00:20:41,320
inizializzato si punta alla stessa
cosa che la lista sta puntando.

389
00:20:41,320 --> 00:20:41,550
>> JASON Hirschorn: OK.

390
00:20:41,550 --> 00:20:45,190
Quindi, si sta creando un nuovo puntatore
all'elenco, non al nodo.

391
00:20:45,190 --> 00:20:45,420
>> AUDIENCE: Giusto.

392
00:20:45,420 --> 00:20:46,150
Già.

393
00:20:46,150 --> 00:20:46,540
>> JASON Hirschorn: OK.

394
00:20:46,540 --> 00:20:48,221
E allora cosa vogliamo fare?

395
00:20:48,221 --> 00:20:49,163
Cosa c'è dopo?

396
00:20:49,163 --> 00:20:50,105
Che dire del nodo?

397
00:20:50,105 --> 00:20:51,050
Non abbiamo un nodo.

398
00:20:51,050 --> 00:20:52,300
Abbiamo solo un valore.

399
00:20:52,300 --> 00:20:55,918

400
00:20:55,918 --> 00:20:58,890
Se vogliamo inserire un nodo, cosa facciamo
bisogno di fare prima che possiamo ancora

401
00:20:58,890 --> 00:20:59,980
pensare di inserirlo?

402
00:20:59,980 --> 00:21:00,820
>> PUBBLICO: Oh, mi dispiace.

403
00:21:00,820 --> 00:21:02,160
abbiamo bisogno di malloc spazio per un nodo.

404
00:21:02,160 --> 00:21:02,455
>> JASON Hirschorn: Excellent.

405
00:21:02,455 --> 00:21:03,210
Facciamo -

406
00:21:03,210 --> 00:21:04,628
OK.

407
00:21:04,628 --> 00:21:06,065
Non possono raggiungere così in alto.

408
00:21:06,065 --> 00:21:08,939

409
00:21:08,939 --> 00:21:09,897
OK.

410
00:21:09,897 --> 00:21:13,236
Stiamo per scendere, e poi
stiamo usando due colonne.

411
00:21:13,236 --> 00:21:13,732
Non posso andare che -

412
00:21:13,732 --> 00:21:14,982
OK.

413
00:21:14,982 --> 00:21:23,660

414
00:21:23,660 --> 00:21:25,130
Creare un nuovo nodo.

415
00:21:25,130 --> 00:21:29,380
È possibile creare un altro puntatore alla lista
o si può semplicemente utilizzare l'elenco come esiste.

416
00:21:29,380 --> 00:21:30,720
Non c'è davvero bisogno di farlo.

417
00:21:30,720 --> 00:21:31,750
>> Quindi creiamo un nuovo nodo.

418
00:21:31,750 --> 00:21:32,010
Grande.

419
00:21:32,010 --> 00:21:32,840
Questo è quello che facciamo prima.

420
00:21:32,840 --> 00:21:34,870
Quali sono le prospettive?

421
00:21:34,870 --> 00:21:35,080
>> AUDIENCE: Aspetta.

422
00:21:35,080 --> 00:21:38,330
Dovremmo creare un nuovo nodo adesso o
dovremmo aspettare per fare in modo che

423
00:21:38,330 --> 00:21:42,260
non ci sono duplicati del nodo
sulla lista, prima creiamo?

424
00:21:42,260 --> 00:21:43,100
>> JASON Hirschorn: Bella domanda.

425
00:21:43,100 --> 00:21:47,770
Facciamo ritengono che per più tardi perché l'
maggior parte del tempo saremo creando

426
00:21:47,770 --> 00:21:48,220
un nuovo nodo.

427
00:21:48,220 --> 00:21:49,110
Quindi noi terremo qui.

428
00:21:49,110 --> 00:21:51,006
Ma questa è una buona domanda.

429
00:21:51,006 --> 00:21:53,250
Se creiamo e troviamo
un duplicato, quello che dovrebbe

430
00:21:53,250 --> 00:21:54,490
facciamo prima di tornare?

431
00:21:54,490 --> 00:21:55,190
>> AUDIENCE: liberarlo.

432
00:21:55,190 --> 00:21:55,470
>> JASON Hirschorn: Già.

433
00:21:55,470 --> 00:21:56,500
Probabilmente liberarlo.

434
00:21:56,500 --> 00:21:56,760
OK.

435
00:21:56,760 --> 00:21:59,850
Che cosa facciamo dopo che abbiamo
creare un nuovo nodo?

436
00:21:59,850 --> 00:22:02,260
Annie?

437
00:22:02,260 --> 00:22:04,780
>> AUDIENCE: Abbiamo messo la
numero nel nodo?

438
00:22:04,780 --> 00:22:05,140
>> JASON Hirschorn: Esattamente.

439
00:22:05,140 --> 00:22:07,190
Abbiamo messo il numero - abbiamo malloc spazio.

440
00:22:07,190 --> 00:22:08,160
Ho intenzione di lasciare che
tutti come una riga.

441
00:22:08,160 --> 00:22:08,720
Ma hai ragione.

442
00:22:08,720 --> 00:22:10,305
Noi malloc spazio e quindi
abbiamo messo il numero dentro

443
00:22:10,305 --> 00:22:12,585
Possiamo anche impostare il puntatore
parte di esso a null.

444
00:22:12,585 --> 00:22:13,720
Questo è esattamente vero.

445
00:22:13,720 --> 00:22:17,400
E poi che dire dopo?

446
00:22:17,400 --> 00:22:18,490
Abbiamo disegnato questa immagine sul tabellone.

447
00:22:18,490 --> 00:22:21,190
Allora cosa facciamo?

448
00:22:21,190 --> 00:22:22,680
>> AUDIENCE: Andiamo attraverso la lista.

449
00:22:22,680 --> 00:22:23,930
>> JASON Hirschorn: Passare attraverso la lista.

450
00:22:23,930 --> 00:22:30,620

451
00:22:30,620 --> 00:22:31,100
OK.

452
00:22:31,100 --> 00:22:34,280
E che cosa controlliamo per ogni nodo.

453
00:22:34,280 --> 00:22:35,955
Kurt, che cosa controlliamo
per ogni nodo?

454
00:22:35,955 --> 00:22:41,640
>> AUDIENCE: Vedere se il valore di n
tale nodo è maggiore del valore n

455
00:22:41,640 --> 00:22:43,070
del nostro nodo.

456
00:22:43,070 --> 00:22:43,340
>> JASON Hirschorn: OK.

457
00:22:43,340 --> 00:22:44,280
Ho intenzione di fare -

458
00:22:44,280 --> 00:22:45,855
sì, OK.

459
00:22:45,855 --> 00:22:48,160
Quindi è n -

460
00:22:48,160 --> 00:22:59,040
Sto per dire se il valore è maggiore
di questo nodo, allora cosa facciamo?

461
00:22:59,040 --> 00:23:07,290
>> PUBBLICO: Bene, allora inseriamo
la cosa giusta prima.

462
00:23:07,290 --> 00:23:07,970
>> JASON Hirschorn: OK.

463
00:23:07,970 --> 00:23:09,410
Quindi, se è maggiore di questa,
poi vogliamo inserire.

464
00:23:09,410 --> 00:23:14,010
Ma vogliamo inserirlo destra prima
perché anche noi avremmo bisogno di essere

465
00:23:14,010 --> 00:23:16,070
tenere traccia, quindi,
di ciò che era prima.

466
00:23:16,070 --> 00:23:22,690
Quindi inserire prima.

467
00:23:22,690 --> 00:23:25,120
Quindi probabilmente abbiamo perso qualcosa
precedenza.

468
00:23:25,120 --> 00:23:27,770
Probabilmente abbiamo bisogno di essere tenuta
traccia di quello che sta succedendo.

469
00:23:27,770 --> 00:23:28,460
Ma ci arriveremo laggiù.

470
00:23:28,460 --> 00:23:30,160
Quindi, quale valore è inferiore?

471
00:23:30,160 --> 00:23:38,030

472
00:23:38,030 --> 00:23:39,710
Kurt, cosa facciamo se
valore è inferiore?

473
00:23:39,710 --> 00:23:43,000
>> AUDIENCE: Poi basta andare avanti
meno che non sia l'ultimo.

474
00:23:43,000 --> 00:23:43,550
>> JASON Hirschorn: questo mi piace.

475
00:23:43,550 --> 00:23:44,800
Quindi, andare al nodo successivo.

476
00:23:44,800 --> 00:23:47,410

477
00:23:47,410 --> 00:23:48,930
Meno che non sia l'ultima -

478
00:23:48,930 --> 00:23:51,100
probabilmente stiamo controllando che
nei termini di una condizione.

479
00:23:51,100 --> 00:23:54,870
Ma sì, il prossimo nodo.

480
00:23:54,870 --> 00:23:58,680
E questo è sempre troppo basso,
così ci sposteremo qui.

481
00:23:58,680 --> 00:24:02,030
Ma se -

482
00:24:02,030 --> 00:24:03,280
possono tutti vedere questo?

483
00:24:03,280 --> 00:24:07,230

484
00:24:07,230 --> 00:24:11,610
Se siamo uguali cosa facciamo?

485
00:24:11,610 --> 00:24:15,740
Se il valore stiamo cercando di inserire
è uguale al valore di questo nodo?

486
00:24:15,740 --> 00:24:16,320
Sì?

487
00:24:16,320 --> 00:24:18,400
>> AUDIENCE: [incomprensibile].

488
00:24:18,400 --> 00:24:18,850
>> JASON Hirschorn: Già.

489
00:24:18,850 --> 00:24:19,290
Dato questo -

490
00:24:19,290 --> 00:24:20,090
Marcus è giusto.

491
00:24:20,090 --> 00:24:21,330
Avremmo potuto forse fare
qualcosa di diverso.

492
00:24:21,330 --> 00:24:25,360
Ma dato che abbiamo creato, ecco
dobbiamo liberare e poi tornare.

493
00:24:25,360 --> 00:24:26,774
Oh boy.

494
00:24:26,774 --> 00:24:30,080
Va meglio?

495
00:24:30,080 --> 00:24:31,850
Come sarebbe?

496
00:24:31,850 --> 00:24:33,100
OK.

497
00:24:33,100 --> 00:24:35,360

498
00:24:35,360 --> 00:24:37,640
Libero e allora cosa facciamo
ritorno, [incomprensibile]?

499
00:24:37,640 --> 00:24:41,330

500
00:24:41,330 --> 00:24:44,110
OK.

501
00:24:44,110 --> 00:24:45,360
Ci manca qualcosa?

502
00:24:45,360 --> 00:24:53,500

503
00:24:53,500 --> 00:24:59,650
Allora, dove stiamo tenendo traccia
del nodo precedente?

504
00:24:59,650 --> 00:25:02,370
>> PUBBLICO: Penso che sarebbe andare
dopo creare un nuovo nodo.

505
00:25:02,370 --> 00:25:02,600
>> JASON Hirschorn: OK.

506
00:25:02,600 --> 00:25:03,940
Quindi all'inizio faremo probabilmente -

507
00:25:03,940 --> 00:25:07,175
sì, possiamo creare un puntatore a una nuova
nodo, come un puntatore nodo precedente e

508
00:25:07,175 --> 00:25:09,600
un puntatore nodo corrente.

509
00:25:09,600 --> 00:25:12,640
Quindi cerchiamo di inserire qui.

510
00:25:12,640 --> 00:25:15,610

511
00:25:15,610 --> 00:25:26,900
Creare attuale e precedente
puntatori ai nodi.

512
00:25:26,900 --> 00:25:28,955
Ma quando facciamo registriamo tali puntatori?

513
00:25:28,955 --> 00:25:30,205
Dove lo facciamo nel codice?

514
00:25:30,205 --> 00:25:33,830

515
00:25:33,830 --> 00:25:34,160
Jeff?

516
00:25:34,160 --> 00:25:35,170
>> AUDIENCE: - condizioni di valore?

517
00:25:35,170 --> 00:25:36,420
>> JASON Hirschorn: Quale
uno in particolare?

518
00:25:36,420 --> 00:25:39,862

519
00:25:39,862 --> 00:25:40,720
>> PUBBLICO: Sto solo confuso.

520
00:25:40,720 --> 00:25:44,200
Se il valore è maggiore di questo nodo,
Non vuol dire che si vuole andare

521
00:25:44,200 --> 00:25:45,320
al nodo successivo?

522
00:25:45,320 --> 00:25:49,515
>> JASON HIRSCHHORN: Quindi, se il nostro valore è
maggiore del valore di questo nodo.

523
00:25:49,515 --> 00:25:52,130
>> PUBBLICO: Sì, allora che ci si vuole
andare più giù la linea, giusto?

524
00:25:52,130 --> 00:25:52,590
>> JASON HIRSCHHORN: Giusto.

525
00:25:52,590 --> 00:25:53,840
Quindi non inseriamo qui.

526
00:25:53,840 --> 00:25:58,430

527
00:25:58,430 --> 00:26:03,240
Se il valore è inferiore a questo nodo, quindi
andiamo al nodo successivo - e poi noi

528
00:26:03,240 --> 00:26:03,835
inserire prima.

529
00:26:03,835 --> 00:26:05,966
>> PUBBLICO: Aspetta, che è questo
nodo e che è il valore?

530
00:26:05,966 --> 00:26:08,510

531
00:26:08,510 --> 00:26:09,280
>> JASON HIRSCHHORN: Bella domanda.

532
00:26:09,280 --> 00:26:13,260
Valore per questa definizione di funzione
è quello che ci è dato.

533
00:26:13,260 --> 00:26:16,910
Così valore è il numero che stiamo dato.

534
00:26:16,910 --> 00:26:21,120
Quindi, se il valore è inferiore a questo
nodo, abbiamo bisogno di tempo per inserire.

535
00:26:21,120 --> 00:26:24,575
Se il valore è maggiore di questo nodo,
andiamo al nodo successivo.

536
00:26:24,575 --> 00:26:26,790
E torniamo alla domanda iniziale,
però, dove -

537
00:26:26,790 --> 00:26:29,060
>> AUDIENCE: Se il valore è maggiore
di questo nodo.

538
00:26:29,060 --> 00:26:30,310
>> JASON HIRSCHHORN: E così
cosa facciamo qui?

539
00:26:30,310 --> 00:26:36,790

540
00:26:36,790 --> 00:26:38,160
Dolce.

541
00:26:38,160 --> 00:26:38,860
Questo è corretto.

542
00:26:38,860 --> 00:26:41,370
Sto solo andando a scrivere
aggiornamento puntatori.

543
00:26:41,370 --> 00:26:44,010
Ma sì, con quella attuale
si dovrebbe aggiornarlo alla

544
00:26:44,010 --> 00:26:46,080
puntare a quello successivo.

545
00:26:46,080 --> 00:26:47,330
Tutto il resto stiamo manca?

546
00:26:47,330 --> 00:26:52,710

547
00:26:52,710 --> 00:26:54,940
Quindi ho intenzione di scrivere questo
codice in gedit.

548
00:26:54,940 --> 00:26:58,375
E mentre faccio questo, si può avere un
paio di minuti per lavorare sulla codifica

549
00:26:58,375 --> 00:28:19,240
questo in C.

550
00:28:19,240 --> 00:28:20,940
>> Così ho ingresso pseudocodice.

551
00:28:20,940 --> 00:28:22,940
Una breve nota prima di iniziare.

552
00:28:22,940 --> 00:28:25,560
Potremmo non essere in grado di completamente
finire questo in tutti i

553
00:28:25,560 --> 00:28:27,300
tre di queste funzioni.

554
00:28:27,300 --> 00:28:30,630
Ci sono soluzioni corrette a loro
che io con la posta elettronica a voi ragazzi

555
00:28:30,630 --> 00:28:33,730
dopo la sezione, e sarà
essere pubblicato su CS50.net.

556
00:28:33,730 --> 00:28:35,640
Quindi io non ti incoraggio a
andare a vedere le sezioni.

557
00:28:35,640 --> 00:28:40,550
Vi incoraggio a provare questi sul
possedere, e quindi utilizzare la pratica

558
00:28:40,550 --> 00:28:41,760
problemi per controllare le tue risposte.

559
00:28:41,760 --> 00:28:47,070
Essi sono stati progettati per strettamente
riguardare e aderire a quello

560
00:28:47,070 --> 00:28:48,400
devi fare sul problema set.

561
00:28:48,400 --> 00:28:53,820
Quindi vi incoraggio a praticare questo
per conto proprio e quindi utilizzare il codice per

562
00:28:53,820 --> 00:28:54,660
controllare le vostre risposte.

563
00:28:54,660 --> 00:28:57,060
Perché io voglio passare a hash
Tavoli a un certo punto nella sezione.

564
00:28:57,060 --> 00:28:58,150
Così potremmo non ottenere attraverso di essa tutti.

565
00:28:58,150 --> 00:28:59,960
Ma faremo quanto possiamo ora.

566
00:28:59,960 --> 00:29:00,370
>> OK.

567
00:29:00,370 --> 00:29:01,960
Cominciamo.

568
00:29:01,960 --> 00:29:04,770
Asam, come possiamo creare un nuovo nodo?

569
00:29:04,770 --> 00:29:06,810
>> AUDIENCE: Non struct *.

570
00:29:06,810 --> 00:29:09,640
>> JASON HIRSCHHORN: Quindi noi
avere che fino qui.

571
00:29:09,640 --> 00:29:10,040
Oh, mi dispiace.

572
00:29:10,040 --> 00:29:13,530
Dicevi struct *.

573
00:29:13,530 --> 00:29:17,260
>> PUBBLICO: E poi [? tipo?]
nodo o nodo c.

574
00:29:17,260 --> 00:29:17,780
>> JASON HIRSCHHORN: OK.

575
00:29:17,780 --> 00:29:19,740
Ho intenzione di chiamarlo new_node
così possiamo rimanere coerenti.

576
00:29:19,740 --> 00:29:22,646

577
00:29:22,646 --> 00:29:33,180
>> PUBBLICO: E si desidera impostare tale
a testa, il primo nodo.

578
00:29:33,180 --> 00:29:33,580
>> JASON HIRSCHHORN: OK.

579
00:29:33,580 --> 00:29:37,290
Così ora questo punta a - quindi questo
non ha ancora creato un nuovo nodo.

580
00:29:37,290 --> 00:29:41,380
Questo è solo rivolta alla
primo nodo nell'elenco.

581
00:29:41,380 --> 00:29:42,630
Come faccio a creare un nuovo nodo?

582
00:29:42,630 --> 00:29:45,490

583
00:29:45,490 --> 00:29:48,070
Se devo spazio per creare un nuovo nodo.

584
00:29:48,070 --> 00:29:49,230
Malloc.

585
00:29:49,230 --> 00:29:51,710
E quanto è grande?

586
00:29:51,710 --> 00:30:00,390
>> PUBBLICO: La dimensione della struttura.

587
00:30:00,390 --> 00:30:01,150
>> JASON HIRSCHHORN: L'
dimensione della struttura.

588
00:30:01,150 --> 00:30:02,400
E qual è la struttura chiama?

589
00:30:02,400 --> 00:30:09,670

590
00:30:09,670 --> 00:30:09,840
>> AUDIENCE: Nodo?

591
00:30:09,840 --> 00:30:11,640
>> JASON HIRSCHHORN: Node.

592
00:30:11,640 --> 00:30:17,640
Così malloc (sizeof (nodo));
ci dà lo spazio.

593
00:30:17,640 --> 00:30:19,740
Ed è questa linea -

594
00:30:19,740 --> 00:30:21,740
una cosa è errato su questa linea.

595
00:30:21,740 --> 00:30:24,430
È new_node un puntatore ad una struct?

596
00:30:24,430 --> 00:30:25,650
Questo è un nome generico.

597
00:30:25,650 --> 00:30:26,520
Che cosa è -

598
00:30:26,520 --> 00:30:27,450
nodo, esattamente.

599
00:30:27,450 --> 00:30:29,340
Si tratta di un nodo *.

600
00:30:29,340 --> 00:30:33,010
E cosa facciamo subito dopo
abbiamo malloc qualcosa, Asan?

601
00:30:33,010 --> 00:30:34,476
Qual è la prima cosa che facciamo?

602
00:30:34,476 --> 00:30:38,850

603
00:30:38,850 --> 00:30:40,320
E se non funziona?

604
00:30:40,320 --> 00:30:42,430
>> PUBBLICO: Oh, verificare se
punti al nodo?

605
00:30:42,430 --> 00:30:43,310
>> JASON HIRSCHHORN: Esattamente.

606
00:30:43,310 --> 00:30:46,750
Quindi, se si new_node uguale uguale
null, cosa facciamo?

607
00:30:46,750 --> 00:30:51,650

608
00:30:51,650 --> 00:30:54,820
Questo restituisce un bool, questa funzione.

609
00:30:54,820 --> 00:30:57,760
Esattamente.

610
00:30:57,760 --> 00:30:58,450
Sembra buono.

611
00:30:58,450 --> 00:30:59,680
Qualcosa da aggiungere lì?

612
00:30:59,680 --> 00:31:00,670
Aggiungeremo le cose alla fine.

613
00:31:00,670 --> 00:31:03,160
Ma che finora sembra buono.

614
00:31:03,160 --> 00:31:06,170
Creare puntatori attuali e precedenti.

615
00:31:06,170 --> 00:31:08,650
Michael, come faccio a fare questo?

616
00:31:08,650 --> 00:31:12,810
>> AUDIENCE: Avreste
fare un nodo *.

617
00:31:12,810 --> 00:31:21,800

618
00:31:21,800 --> 00:31:25,502
Dovreste fare uno non
per new_node ma per il

619
00:31:25,502 --> 00:31:26,905
nodi che già hanno.

620
00:31:26,905 --> 00:31:27,230
>> JASON HIRSCHHORN: OK.

621
00:31:27,230 --> 00:31:29,255
Quindi il nodo corrente siamo su.

622
00:31:29,255 --> 00:31:30,505
Chiamerò che curr.

623
00:31:30,505 --> 00:31:39,650

624
00:31:39,650 --> 00:31:39,770
Bene.

625
00:31:39,770 --> 00:31:41,620
Abbiamo deciso che vogliamo mantenere
due perché abbiamo bisogno di sapere

626
00:31:41,620 --> 00:31:42,870
cosa c'è prima.

627
00:31:42,870 --> 00:31:45,770

628
00:31:45,770 --> 00:31:47,020
Che cosa vengono inizializzati?

629
00:31:47,020 --> 00:31:49,874

630
00:31:49,874 --> 00:31:54,180
>> PUBBLICO: Il loro valore nella nostra lista.

631
00:31:54,180 --> 00:31:58,090
>> JASON HIRSCHHORN: Allora, qual è il
prima cosa sulla nostra lista?

632
00:31:58,090 --> 00:32:04,050
Oppure, come facciamo a sapere dove il
inizio della nostra lista è?

633
00:32:04,050 --> 00:32:08,015
>> AUDIENCE: Non è forse passato
nella funzione?

634
00:32:08,015 --> 00:32:08,466
>> JASON HIRSCHHORN: Giusto.

635
00:32:08,466 --> 00:32:09,716
E 'stata approvata nel proprio qui.

636
00:32:09,716 --> 00:32:15,910

637
00:32:15,910 --> 00:32:18,980
Quindi, se è passato nella funzione, il
inizio della lista, quello che dovremmo

638
00:32:18,980 --> 00:32:21,270
set corrente pari a?

639
00:32:21,270 --> 00:32:22,110
>> AUDIENCE: List.

640
00:32:22,110 --> 00:32:22,900
>> JASON HIRSCHHORN: List.

641
00:32:22,900 --> 00:32:24,090
Questo è esattamente vero.

642
00:32:24,090 --> 00:32:26,290
Ora ha l'indirizzo
l'inizio della nostra lista.

643
00:32:26,290 --> 00:32:28,450
E per quanto riguarda precedente?

644
00:32:28,450 --> 00:32:31,920
>> AUDIENCE: Lista meno uno?

645
00:32:31,920 --> 00:32:32,690
>> JASON HIRSCHHORN: Non c'è
niente prima.

646
00:32:32,690 --> 00:32:34,580
Che cosa possiamo fare per significare nulla?

647
00:32:34,580 --> 00:32:35,050
>> AUDIENCE: Null.

648
00:32:35,050 --> 00:32:35,450
>> JASON HIRSCHHORN: Già.

649
00:32:35,450 --> 00:32:37,950
Sembra una buona idea.

650
00:32:37,950 --> 00:32:38,360
Perfetto.

651
00:32:38,360 --> 00:32:39,630
Grazie.

652
00:32:39,630 --> 00:32:42,850
Passare attraverso la lista.

653
00:32:42,850 --> 00:32:45,490
Costantino, da quanto tempo stiamo andando
per scorrere l'elenco?

654
00:32:45,490 --> 00:32:49,010
>> AUDIENCE: fino a raggiungere nulla.

655
00:32:49,010 --> 00:32:49,390
>> JASON HIRSCHHORN: OK.

656
00:32:49,390 --> 00:32:50,430
Quindi, se, mentre, per il ciclo.

657
00:32:50,430 --> 00:32:52,200
Cosa stiamo facendo?

658
00:32:52,200 --> 00:32:53,320
>> AUDIENCE: Forse un ciclo for?

659
00:32:53,320 --> 00:32:53,910
>> JASON HIRSCHHORN: Facciamo un ciclo for.

660
00:32:53,910 --> 00:32:55,870
OK.

661
00:32:55,870 --> 00:33:02,465
>> PUBBLICO: E diciamo per -

662
00:33:02,465 --> 00:33:09,764

663
00:33:09,764 --> 00:33:13,390
fino a quando il puntatore corrente
non è uguale a zero.

664
00:33:13,390 --> 00:33:19,160
>> JASON HIRSCHHORN: Quindi, se conosciamo il
condizioni, come possiamo scrivere un ciclo

665
00:33:19,160 --> 00:33:21,740
Basato questa condizione.

666
00:33:21,740 --> 00:33:24,380
Che tipo di un ciclo dovremmo usare?

667
00:33:24,380 --> 00:33:25,260
>> AUDIENCE: While.

668
00:33:25,260 --> 00:33:25,590
>> JASON HIRSCHHORN: Già.

669
00:33:25,590 --> 00:33:27,130
Questo rende più senso in base
fuori di quello che hai detto.

670
00:33:27,130 --> 00:33:29,430
Se vogliamo solo andare in noi sarebbe
è sufficiente sapere che cosa, farebbe

671
00:33:29,430 --> 00:33:31,680
senso fare un ciclo while.

672
00:33:31,680 --> 00:33:39,880
Mentre la corrente non è uguale a null,
se il valore è inferiore a questo nodo.

673
00:33:39,880 --> 00:33:41,650
Akshar, dammi questa linea.

674
00:33:41,650 --> 00:33:48,810

675
00:33:48,810 --> 00:33:56,955
>> AUDIENCE: Se la corrente-> n
n meno di valore.

676
00:33:56,955 --> 00:34:00,170

677
00:34:00,170 --> 00:34:03,260
O invertire tale.

678
00:34:03,260 --> 00:34:06,140
Passare quella fascia.

679
00:34:06,140 --> 00:34:06,620
>> JASON HIRSCHHORN: Mi dispiace.

680
00:34:06,620 --> 00:34:08,760
>> AUDIENCE: Modificare la staffa.

681
00:34:08,760 --> 00:34:10,914
>> JASON HIRSCHHORN: Quindi, se è
maggiore del valore.

682
00:34:10,914 --> 00:34:18,719

683
00:34:18,719 --> 00:34:22,120
Perché questo è confusa con l'
commento di cui sopra, ho intenzione di farlo.

684
00:34:22,120 --> 00:34:22,480
Ma sì.

685
00:34:22,480 --> 00:34:25,125
Se il nostro valore è inferiore a questo
nodo, cosa facciamo?

686
00:34:25,125 --> 00:34:25,540
Oh.

687
00:34:25,540 --> 00:34:26,710
Ce l'ho proprio qui.

688
00:34:26,710 --> 00:34:27,960
Inserisci prima.

689
00:34:27,960 --> 00:34:32,080

690
00:34:32,080 --> 00:34:32,370
OK.

691
00:34:32,370 --> 00:34:33,933
Come lo facciamo?

692
00:34:33,933 --> 00:34:34,900
>> PUBBLICO: E 'ancora di me?

693
00:34:34,900 --> 00:34:36,150
>> JASON HIRSCHHORN: Già.

694
00:34:36,150 --> 00:34:38,520

695
00:34:38,520 --> 00:34:39,770
>> AUDIENCE: You -

696
00:34:39,770 --> 00:34:42,909

697
00:34:42,909 --> 00:34:44,159
new_node-> next.

698
00:34:44,159 --> 00:34:46,770

699
00:34:46,770 --> 00:34:50,163
>> JASON HIRSCHHORN: Allora, qual è
che andare a pari?

700
00:34:50,163 --> 00:34:52,070
>> AUDIENCE: Sta andando a corrente pari.

701
00:34:52,070 --> 00:34:53,889
>> JASON HIRSCHHORN: Esattamente.

702
00:34:53,889 --> 00:34:55,730
E così l'altro -

703
00:34:55,730 --> 00:34:56,730
cos'altro abbiamo bisogno di aggiornare?

704
00:34:56,730 --> 00:34:59,982
>> AUDIENCE: Controllare se passato è uguale a null.

705
00:34:59,982 --> 00:35:01,870
>> JASON HIRSCHHORN: Se prev -

706
00:35:01,870 --> 00:35:03,730
quindi se prev uguale a null.

707
00:35:03,730 --> 00:35:05,990
>> AUDIENCE: Ciò significa che sta andando
per diventare il capo.

708
00:35:05,990 --> 00:35:06,780
>> JASON HIRSCHHORN: Ciò significa che
è diventato il capo.

709
00:35:06,780 --> 00:35:07,620
Allora cosa facciamo?

710
00:35:07,620 --> 00:35:12,510
>> AUDIENCE: Facciamo testa uguale new_node.

711
00:35:12,510 --> 00:35:16,690
>> JASON HIRSCHHORN: Testa
uguale new_node.

712
00:35:16,690 --> 00:35:20,540
E perché la testa qui, non elencare?

713
00:35:20,540 --> 00:35:24,940
>> AUDIENCE: perché la testa è un globale
variabile, che è il punto di partenza.

714
00:35:24,940 --> 00:35:26,190
>> JASON HIRSCHHORN: Sweet.

715
00:35:26,190 --> 00:35:33,750

716
00:35:33,750 --> 00:35:34,170
OK.

717
00:35:34,170 --> 00:35:36,150
E -

718
00:35:36,150 --> 00:35:53,796
>> AUDIENCE: Allora non altro Prec.->
successiva è uguale new_node.

719
00:35:53,796 --> 00:35:55,080
E poi si torna vero.

720
00:35:55,080 --> 00:35:59,560

721
00:35:59,560 --> 00:36:02,700
>> JASON HIRSCHHORN: Dove fare
noi mettemmo fine new_node?

722
00:36:02,700 --> 00:36:04,850
>> PUBBLICO: Vorrei -

723
00:36:04,850 --> 00:36:06,180
Ho impostato che alla partenza.

724
00:36:06,180 --> 00:36:07,430
>> JASON HIRSCHHORN: Cosa line?

725
00:36:07,430 --> 00:36:10,000

726
00:36:10,000 --> 00:36:12,598
>> PUBBLICO: Dopo il if
controllando se è noto.

727
00:36:12,598 --> 00:36:13,057
>> JASON HIRSCHHORN: Proprio qui?

728
00:36:13,057 --> 00:36:18,335
>> PUBBLICO: Farei new_node-> n
uguale valore.

729
00:36:18,335 --> 00:36:19,585
>> JASON HIRSCHHORN: Suona bene.

730
00:36:19,585 --> 00:36:21,740

731
00:36:21,740 --> 00:36:25,090
Probabilmente ha senso - non lo facciamo
bisogno di sapere che siamo sulla lista

732
00:36:25,090 --> 00:36:26,280
perché stiamo solo fare
con una lista.

733
00:36:26,280 --> 00:36:29,560
Così una dichiarazione di funzione migliore per
questo è solo per sbarazzarsi di questo

734
00:36:29,560 --> 00:36:34,360
tutto e basta inserire
un valore in testa.

735
00:36:34,360 --> 00:36:35,930
Non abbiamo nemmeno bisogno di sapere
quale lista siamo dentro

736
00:36:35,930 --> 00:36:39,140
Ma terrò per ora e
poi cambiare su di aggiornamento

737
00:36:39,140 --> 00:36:42,590
le diapositive e il codice.

738
00:36:42,590 --> 00:36:44,980
In modo che sembra buono per ora.

739
00:36:44,980 --> 00:36:46,560
Se il valore - che può fare questa linea?

740
00:36:46,560 --> 00:36:47,810
Se -

741
00:36:47,810 --> 00:36:52,240

742
00:36:52,240 --> 00:36:53,840
cosa facciamo qui, Noah.

743
00:36:53,840 --> 00:36:57,890

744
00:36:57,890 --> 00:37:07,100
>> AUDIENCE: Se il valore è maggiore
di curr-> n -

745
00:37:07,100 --> 00:37:16,830

746
00:37:16,830 --> 00:37:18,240
>> JASON HIRSCHHORN: come fare
andiamo al nodo successivo?

747
00:37:18,240 --> 00:37:27,760

748
00:37:27,760 --> 00:37:30,530
>> AUDIENCE: Curr-> n è
pari a new_node.

749
00:37:30,530 --> 00:37:37,630

750
00:37:37,630 --> 00:37:39,195
>> JASON HIRSCHHORN: Allora n è
quale parte della struttura?

751
00:37:39,195 --> 00:37:43,065

752
00:37:43,065 --> 00:37:46,020
Il numero intero.

753
00:37:46,020 --> 00:37:50,420
E new_node è un puntatore a un nodo.

754
00:37:50,420 --> 00:37:51,880
Quindi, quale parte del curr dovremmo aggiornare?

755
00:37:51,880 --> 00:38:03,900

756
00:38:03,900 --> 00:38:05,400
Se no n, allora qual è l'altra parte?

757
00:38:05,400 --> 00:38:21,680

758
00:38:21,680 --> 00:38:22,810
Noè, cosa c'è dall'altra parte.

759
00:38:22,810 --> 00:38:23,570
>> PUBBLICO: Oh, la prossima.

760
00:38:23,570 --> 00:38:25,645
>> JASON HIRSCHHORN: Avanti, esattamente.

761
00:38:25,645 --> 00:38:26,410
Esattamente.

762
00:38:26,410 --> 00:38:28,770
La prossima è quella giusta.

763
00:38:28,770 --> 00:38:31,540
E cos'altro abbiamo bisogno
aggiornare, Noah?

764
00:38:31,540 --> 00:38:32,840
>> PUBBLICO: I puntatori.

765
00:38:32,840 --> 00:38:34,840
>> JASON HIRSCHHORN: So
abbiamo corrente aggiornato.

766
00:38:34,840 --> 00:38:36,090
>> AUDIENCE: Prec.-> next.

767
00:38:36,090 --> 00:38:48,160

768
00:38:48,160 --> 00:38:49,410
>> JASON HIRSCHHORN: Già.

769
00:38:49,410 --> 00:38:57,465

770
00:38:57,465 --> 00:38:58,370
OK, ci fermiamo.

771
00:38:58,370 --> 00:39:02,200
Chi ci può aiutare qui?

772
00:39:02,200 --> 00:39:03,385
Manu, che cosa dobbiamo fare?

773
00:39:03,385 --> 00:39:05,615
>> AUDIENCE: Hai avuto modo di impostare
uguale a curr-> next.

774
00:39:05,615 --> 00:39:09,110

775
00:39:09,110 --> 00:39:11,630
Ma fare prima riga precedente.

776
00:39:11,630 --> 00:39:12,880
>> JASON HIRSCHHORN: OK.

777
00:39:12,880 --> 00:39:16,590

778
00:39:16,590 --> 00:39:18,260
Qualcos'altro?

779
00:39:18,260 --> 00:39:19,170
Akshar.

780
00:39:19,170 --> 00:39:22,680
>> PUBBLICO: Io non penso che tu sia
destinato a cambiare curr-> next.

781
00:39:22,680 --> 00:39:29,270
Penso che sei destinato a fare eguali curr
curr-> next per andare al nodo successivo.

782
00:39:29,270 --> 00:39:30,500
>> JASON HIRSCHHORN: Mi spiace, dove?

783
00:39:30,500 --> 00:39:32,680
Su quale linea?

784
00:39:32,680 --> 00:39:33,420
Questa linea?

785
00:39:33,420 --> 00:39:33,750
>> AUDIENCE: Già.

786
00:39:33,750 --> 00:39:35,745
Fai curr uguale curr-> next.

787
00:39:35,745 --> 00:39:39,690

788
00:39:39,690 --> 00:39:43,360
>> JASON HIRSCHHORN: Quindi è corretto
perché la corrente è un

789
00:39:43,360 --> 00:39:45,220
puntatore a un nodo.

790
00:39:45,220 --> 00:39:48,550
E vogliamo che puntare alla prossima
nodo di ciò che sta facendo attualmente

791
00:39:48,550 --> 00:39:49,930
indicato.

792
00:39:49,930 --> 00:39:54,410
Curr stessa ha un successivo.

793
00:39:54,410 --> 00:39:58,620
Ma se dovessimo aggiornare curr.next, abbiamo
sarebbe l'aggiornamento della nota reale

794
00:39:58,620 --> 00:40:01,430
sé, non dove questa
puntatore stava indicando.

795
00:40:01,430 --> 00:40:02,680
Che dire di questa linea, però.

796
00:40:02,680 --> 00:40:05,160

797
00:40:05,160 --> 00:40:07,330
Avi?

798
00:40:07,330 --> 00:40:09,590
>> AUDIENCE: Prec.-> uguale prossimo curr.

799
00:40:09,590 --> 00:40:12,500

800
00:40:12,500 --> 00:40:19,440
>> JASON HIRSCHHORN: Quindi, di nuovo, se prev è un
puntatore a un nodo, prev-> successivo è l'

801
00:40:19,440 --> 00:40:23,020
puntatore effettivo nel nodo.

802
00:40:23,020 --> 00:40:27,190
Quindi questo sarebbe un aggiornamento
puntatore in un nodo a curr.

803
00:40:27,190 --> 00:40:28,570
Non vogliamo aggiornare
un puntatore in un nodo.

804
00:40:28,570 --> 00:40:30,570
Vogliamo aggiornare precedente.

805
00:40:30,570 --> 00:40:31,850
Quindi, come possiamo farlo?

806
00:40:31,850 --> 00:40:34,250
>> AUDIENCE: sarebbe solo prev.

807
00:40:34,250 --> 00:40:34,565
>> JASON HIRSCHHORN: Giusto.

808
00:40:34,565 --> 00:40:35,560
Prev è un puntatore a un nodo.

809
00:40:35,560 --> 00:40:38,750
Ora stiamo cambiando ad una
nuovo puntatore a un nodo.

810
00:40:38,750 --> 00:40:40,830
OK Passiamo giù.

811
00:40:40,830 --> 00:40:41,940
Infine, questa ultima condizione.

812
00:40:41,940 --> 00:40:44,896
Jeff, cosa facciamo qui?

813
00:40:44,896 --> 00:40:47,515
>> AUDIENCE: Se il valore è
pari al curr-> n.

814
00:40:47,515 --> 00:40:51,030

815
00:40:51,030 --> 00:40:51,300
>> JASON HIRSCHHORN: Mi dispiace.

816
00:40:51,300 --> 00:40:52,372
Oh mio Dio.

817
00:40:52,372 --> 00:40:54,330
Cosa?

818
00:40:54,330 --> 00:40:55,580
Valore == curr-> n.

819
00:40:55,580 --> 00:41:01,050

820
00:41:01,050 --> 00:41:02,300
Che cosa facciamo?

821
00:41:02,300 --> 00:41:04,760

822
00:41:04,760 --> 00:41:10,950
>> AUDIENCE: Faresti liberare la nostra new_node,
e poi ci si torna false.

823
00:41:10,950 --> 00:41:21,410

824
00:41:21,410 --> 00:41:23,460
>> JASON HIRSCHHORN: Questo è ciò che
abbiamo scritto finora.

825
00:41:23,460 --> 00:41:25,710
Qualcuno ha nulla
aggiungere prima che facciamo?

826
00:41:25,710 --> 00:41:35,460

827
00:41:35,460 --> 00:41:35,710
OK.

828
00:41:35,710 --> 00:41:36,960
Proviamo.

829
00:41:36,960 --> 00:41:44,180

830
00:41:44,180 --> 00:41:46,110
Il controllo può raggiungere la fine
di una funzione non nullo.

831
00:41:46,110 --> 00:41:48,310
Avi, cosa sta succedendo?

832
00:41:48,310 --> 00:41:51,380
>> AUDIENCE: dovresti mettere ritorno
vero al di fuori del ciclo while?

833
00:41:51,380 --> 00:41:53,900

834
00:41:53,900 --> 00:41:54,400
>> JASON HIRSCHHORN: Non lo so.

835
00:41:54,400 --> 00:41:54,780
Sei tu mi vuoi?

836
00:41:54,780 --> 00:41:55,520
>> AUDIENCE: Non importa.

837
00:41:55,520 --> 00:41:56,350
No.

838
00:41:56,350 --> 00:41:57,180
>> JASON HIRSCHHORN: Akshar?

839
00:41:57,180 --> 00:41:59,460
>> PUBBLICO: Penso che intendevi
mettere return false alla fine

840
00:41:59,460 --> 00:42:02,230
del ciclo while.

841
00:42:02,230 --> 00:42:03,270
>> JASON HIRSCHHORN: Allora, dove
vuoi che vada?

842
00:42:03,270 --> 00:42:05,270
>> AUDIENCE: Come al di fuori del ciclo while.

843
00:42:05,270 --> 00:42:08,800
Quindi, se si esce dal ciclo while che i mezzi di
che hai raggiunto alla fine e

844
00:42:08,800 --> 00:42:09,980
è successo niente.

845
00:42:09,980 --> 00:42:10,410
>> JASON HIRSCHHORN: OK.

846
00:42:10,410 --> 00:42:12,340
Allora cosa facciamo qui?

847
00:42:12,340 --> 00:42:13,702
>> PUBBLICO: Si ritorna falso
lì.

848
00:42:13,702 --> 00:42:15,040
>> JASON HIRSCHHORN: Oh, abbiamo
farlo in entrambi i luoghi?

849
00:42:15,040 --> 00:42:15,650
>> AUDIENCE: Già.

850
00:42:15,650 --> 00:42:16,900
>> JASON HIRSCHHORN: OK.

851
00:42:16,900 --> 00:42:24,840

852
00:42:24,840 --> 00:42:26,160
Dovremmo andare?

853
00:42:26,160 --> 00:42:26,980
Oh mio Dio.

854
00:42:26,980 --> 00:42:27,290
Mi dispiace.

855
00:42:27,290 --> 00:42:28,480
Mi scuso per lo schermo.

856
00:42:28,480 --> 00:42:30,530
È un po 'andando fuori di testa su di noi.

857
00:42:30,530 --> 00:42:31,520
Quindi scegliere un'opzione.

858
00:42:31,520 --> 00:42:35,260
Zero, per il codice, si chiude il programma.

859
00:42:35,260 --> 00:42:36,700
Un inserisce qualcosa.

860
00:42:36,700 --> 00:42:37,990
Inseriamo tre.

861
00:42:37,990 --> 00:42:42,900

862
00:42:42,900 --> 00:42:45,380
L'inserto non ha avuto successo.

863
00:42:45,380 --> 00:42:46,500
Io vado a stampare.

864
00:42:46,500 --> 00:42:48,050
Io non ho nulla.

865
00:42:48,050 --> 00:42:48,450
OK.

866
00:42:48,450 --> 00:42:50,250
Forse era solo un colpo di fortuna.

867
00:42:50,250 --> 00:42:52,810
Inserire uno.

868
00:42:52,810 --> 00:42:55,770
Non è successo.

869
00:42:55,770 --> 00:42:57,470
OK.

870
00:42:57,470 --> 00:43:02,400
Corriamo attraverso la GDB molto velocemente
verificare che cosa sta succedendo.

871
00:43:02,400 --> 00:43:06,055
>> Ricorda gdb. / Il nome del
programma ci mette in GDB.

872
00:43:06,055 --> 00:43:07,610
È che un sacco di gestire?

873
00:43:07,610 --> 00:43:08,560
Il lampeggiante?

874
00:43:08,560 --> 00:43:10,400
Probabilmente.

875
00:43:10,400 --> 00:43:12,760
Chiudete gli occhi e prendere un po 'profonda
respiri se vi stancate

876
00:43:12,760 --> 00:43:13,580
di vedere la cosa.

877
00:43:13,580 --> 00:43:14,200
Sono in GDB.

878
00:43:14,200 --> 00:43:15,830
Qual è la prima cosa che faccio in GDB?

879
00:43:15,830 --> 00:43:17,050
Dobbiamo capire
cosa sta succedendo qui.

880
00:43:17,050 --> 00:43:17,310
Vediamo.

881
00:43:17,310 --> 00:43:21,650
Abbiamo sei minuti per capire
cosa sta succedendo.

882
00:43:21,650 --> 00:43:22,900
Rompere principale.

883
00:43:22,900 --> 00:43:25,950

884
00:43:25,950 --> 00:43:28,130
E allora cosa faccio?

885
00:43:28,130 --> 00:43:29,180
Carlos?

886
00:43:29,180 --> 00:43:31,060
Esegui.

887
00:43:31,060 --> 00:43:32,250
OK.

888
00:43:32,250 --> 00:43:34,160
Scegliamo un'opzione.

889
00:43:34,160 --> 00:43:36,330
E cosa significa N fare?

890
00:43:36,330 --> 00:43:38,480
Avanti.

891
00:43:38,480 --> 00:43:38,950
Già.

892
00:43:38,950 --> 00:43:39,740
>> AUDIENCE: Non si parla -

893
00:43:39,740 --> 00:43:45,230
Non hai detto che la testa, era
inizializzato per nulla all'inizio.

894
00:43:45,230 --> 00:43:47,140
Ma non avevi detto che era OK.

895
00:43:47,140 --> 00:43:50,040

896
00:43:50,040 --> 00:43:52,640
>> JASON HIRSCHHORN: Andiamo - diamo un'occhiata
in GDB, e poi ci torneremo.

897
00:43:52,640 --> 00:43:54,910
Ma suona come avete già
alcune idee su quello che sta succedendo.

898
00:43:54,910 --> 00:43:58,340
Quindi vogliamo inserire qualcosa.

899
00:43:58,340 --> 00:43:59,390
OK.

900
00:43:59,390 --> 00:44:00,150
Abbiamo inserire.

901
00:44:00,150 --> 00:44:00,770
Si prega di inserire un int.

902
00:44:00,770 --> 00:44:01,990
Ci inseriamo tre.

903
00:44:01,990 --> 00:44:03,000
E poi io sono su questa linea.

904
00:44:03,000 --> 00:44:07,030
Come posso fare avviare il debug
l'inserto nota funzione?

905
00:44:07,030 --> 00:44:08,280
Oh mio Dio.

906
00:44:08,280 --> 00:44:10,990

907
00:44:10,990 --> 00:44:12,240
Questo è un sacco.

908
00:44:12,240 --> 00:44:14,372

909
00:44:14,372 --> 00:44:16,445
È che andando fuori di testa un sacco?

910
00:44:16,445 --> 00:44:19,696

911
00:44:19,696 --> 00:44:21,680
>> PUBBLICO: Oh, è morto.

912
00:44:21,680 --> 00:44:22,930
>> JASON HIRSCHHORN: Ho appena
tirato fuori.

913
00:44:22,930 --> 00:44:27,364

914
00:44:27,364 --> 00:44:28,310
OK.

915
00:44:28,310 --> 00:44:29,560
>> AUDIENCE: Forse è il
altra estremità del filo.

916
00:44:29,560 --> 00:44:37,000

917
00:44:37,000 --> 00:44:39,470
>> JASON HIRSCHHORN: Wow.

918
00:44:39,470 --> 00:44:42,330
Così la linea di fondo -

919
00:44:42,330 --> 00:44:43,470
che cosa hai detto?

920
00:44:43,470 --> 00:44:46,040
>> PUBBLICO: Ho detto l'ironia del tecnico
difficoltà di questa classe.

921
00:44:46,040 --> 00:44:46,410
>> JASON HIRSCHHORN: Lo so.

922
00:44:46,410 --> 00:44:48,660
Se solo avessi avuto il controllo su quella parte.

923
00:44:48,660 --> 00:44:49,910
[Incomprensibile]

924
00:44:49,910 --> 00:44:54,430

925
00:44:54,430 --> 00:44:55,400
Sembra fantastico.

926
00:44:55,400 --> 00:44:58,680
Perché non cominciare a pensare ragazzi
quello che avremmo potuto fare di sbagliato,

927
00:44:58,680 --> 00:45:01,140
e saremo di nuovo in 90 secondi.

928
00:45:01,140 --> 00:46:18,160

929
00:46:18,160 --> 00:46:23,010
>> Avica, ho intenzione di chiedere a voi come fare
all'interno insert_node di debug.

930
00:46:23,010 --> 00:46:28,940

931
00:46:28,940 --> 00:46:31,460
Quindi questo è dove abbiamo l'ultima lasciato.

932
00:46:31,460 --> 00:46:35,110
Come faccio ad andare dentro insert_node, Avica,
per esaminare cosa sta succedendo?

933
00:46:35,110 --> 00:46:36,360
Quale comando GDB?

934
00:46:36,360 --> 00:46:41,050

935
00:46:41,050 --> 00:46:42,390
Rottura non mi avrebbe portato dentro.

936
00:46:42,390 --> 00:46:46,200

937
00:46:46,200 --> 00:46:47,130
Lo sa Marquise?

938
00:46:47,130 --> 00:46:48,240
>> AUDIENCE: Cosa?

939
00:46:48,240 --> 00:46:51,780
>> JASON HIRSCHHORN: Quale comando GDB
Io uso per andare all'interno di questa funzione?

940
00:46:51,780 --> 00:46:52,070
>> AUDIENCE: Passo?

941
00:46:52,070 --> 00:46:55,140
>> JASON HIRSCHHORN: Step via
S. Questo mi porta dentro.

942
00:46:55,140 --> 00:46:55,476
OK.

943
00:46:55,476 --> 00:46:58,040
New_node mallocing po 'di spazio.

944
00:46:58,040 --> 00:46:59,120
Che tutto sembra proprio andare.

945
00:46:59,120 --> 00:47:00,370
Esaminiamo new_node.

946
00:47:00,370 --> 00:47:03,270

947
00:47:03,270 --> 00:47:05,410
Ha ottenuto un certo indirizzo di memoria.

948
00:47:05,410 --> 00:47:07,440
Diamo un'occhiata -

949
00:47:07,440 --> 00:47:08,500
che è tutto corretto.

950
00:47:08,500 --> 00:47:12,220
Quindi tutto qui sembra
funzionare correttamente.

951
00:47:12,220 --> 00:47:14,530
>> AUDIENCE: Qual è la differenza
tra P e display?

952
00:47:14,530 --> 00:47:16,160
>> JASON HIRSCHHORN: P sta per la stampa.

953
00:47:16,160 --> 00:47:19,310
E così stai chiedendo qual è la
differenza tra questo e questo?

954
00:47:19,310 --> 00:47:22,330
In questo caso, nulla.

955
00:47:22,330 --> 00:47:26,960
Ma in generale ci sono
alcune differenze.

956
00:47:26,960 --> 00:47:28,220
E si dovrebbe guardare nel manuale GDB.

957
00:47:28,220 --> 00:47:29,560
Ma in questo caso, nulla.

958
00:47:29,560 --> 00:47:31,460
Noi tendiamo a usare la stampa, però, perché
non abbiamo bisogno di fare molto di più

959
00:47:31,460 --> 00:47:33,960
stampare un singolo valore.

960
00:47:33,960 --> 00:47:34,640
>> OK.

961
00:47:34,640 --> 00:47:40,300
Quindi siamo sulla linea 80 del nostro codice,
Impostazione nodo * curr uguale alla lista.

962
00:47:40,300 --> 00:47:42,500
Cerchiamo di stampiamo curr.

963
00:47:42,500 --> 00:47:45,260

964
00:47:45,260 --> 00:47:46,840
E 'uguale lista.

965
00:47:46,840 --> 00:47:48,850
Dolce.

966
00:47:48,850 --> 00:47:49,340
Aspetta.

967
00:47:49,340 --> 00:47:50,590
E 'uguale a qualcosa.

968
00:47:50,590 --> 00:47:53,680

969
00:47:53,680 --> 00:47:56,190
Non mi sembra giusto.

970
00:47:56,190 --> 00:47:56,840
Ci andiamo.

971
00:47:56,840 --> 00:47:59,470
È perché in GDB, a destra, se
è la linea sei su di esso

972
00:47:59,470 --> 00:48:00,330
non ancora eseguita.

973
00:48:00,330 --> 00:48:03,100
Quindi è necessario digitare realtà
successivo per eseguire la riga

974
00:48:03,100 --> 00:48:05,230
prima di vedere i risultati.

975
00:48:05,230 --> 00:48:06,680
Così eccoci qui.

976
00:48:06,680 --> 00:48:09,490
Abbiamo appena eseguita questa linea,
precedente è uguale a null.

977
00:48:09,490 --> 00:48:13,590
Quindi, di nuovo, se stampiamo precedente
non vedremo nulla di strano.

978
00:48:13,590 --> 00:48:18,680
Ma se abbiamo effettivamente eseguiamo che
linea, poi vedremo

979
00:48:18,680 --> 00:48:20,380
che quella linea ha funzionato.

980
00:48:20,380 --> 00:48:21,060
>> Così abbiamo curr.

981
00:48:21,060 --> 00:48:23,180
Quelli sono entrambi buoni.

982
00:48:23,180 --> 00:48:24,010
Giusto?

983
00:48:24,010 --> 00:48:28,130
Ora siamo su questa linea qui.

984
00:48:28,130 --> 00:48:29,310
Mentre curr non è uguale null.

985
00:48:29,310 --> 00:48:31,110
Ebbene, che cosa fa curr uguali?

986
00:48:31,110 --> 00:48:32,450
Abbiamo appena visto pari a null.

987
00:48:32,450 --> 00:48:33,210
Abbiamo stampato fuori.

988
00:48:33,210 --> 00:48:35,110
Io stamparlo di nuovo.

989
00:48:35,110 --> 00:48:36,720
Così è che il ciclo while
andando da eseguire?

990
00:48:36,720 --> 00:48:37,270
>> PUBBLICO: No.

991
00:48:37,270 --> 00:48:39,790
>> JASON HIRSCHHORN: Così, quando ho scritto che
linea, vedete abbiamo saltato tutta la strada

992
00:48:39,790 --> 00:48:41,390
fino in fondo, restituire false.

993
00:48:41,390 --> 00:48:44,520
E poi andremo a restituire false
e tornare al nostro programma e

994
00:48:44,520 --> 00:48:48,020
eventualmente stampare, come abbiamo visto,
l'inserto non ha avuto successo.

995
00:48:48,020 --> 00:48:51,010
Così, qualcuno ha qualche idea su cosa
dobbiamo fare per risolvere questo problema?

996
00:48:51,010 --> 00:48:54,200

997
00:48:54,200 --> 00:48:57,570
Ho intenzione di aspettare fino a quando vedo
un paio di mani salire.

998
00:48:57,570 --> 00:48:58,830
Noi non eseguiamo questo.

999
00:48:58,830 --> 00:49:01,660
Tenete a mente, questa era la prima
cosa stavamo facendo.

1000
00:49:01,660 --> 00:49:02,430
Non ho intenzione di fare una coppia.

1001
00:49:02,430 --> 00:49:03,670
Io vado a fare un paio.

1002
00:49:03,670 --> 00:49:04,830
Perché un paio significa due.

1003
00:49:04,830 --> 00:49:07,620
Ti aspetto per più di due.

1004
00:49:07,620 --> 00:49:10,690
>> Il primo inserimento, curr,
per default è uguale a null.

1005
00:49:10,690 --> 00:49:14,050
E questo ciclo viene eseguito solo
se curr non è nullo.

1006
00:49:14,050 --> 00:49:18,740
Così come posso ottenere intorno a questo?

1007
00:49:18,740 --> 00:49:19,990
Vedo tre mani.

1008
00:49:19,990 --> 00:49:28,490

1009
00:49:28,490 --> 00:49:29,780
Ti aspetto per più di tre.

1010
00:49:29,780 --> 00:49:33,460

1011
00:49:33,460 --> 00:49:35,940
Marcus, cosa ne pensi?

1012
00:49:35,940 --> 00:49:37,730
>> PUBBLICO: Beh, se avete bisogno di
eseguire più di una volta, basta

1013
00:49:37,730 --> 00:49:39,948
cambiarlo in un ciclo do-while.

1014
00:49:39,948 --> 00:49:41,250
>> JASON HIRSCHHORN: OK.

1015
00:49:41,250 --> 00:49:44,240
Sarà che risolvere il nostro problema, però?

1016
00:49:44,240 --> 00:49:47,750
>> AUDIENCE: In questo caso no, perché di
il fatto che l'elenco è vuoto.

1017
00:49:47,750 --> 00:49:52,150
Allora probabilmente solo bisogno di aggiungere
una dichiarazione che, se il ciclo termina

1018
00:49:52,150 --> 00:49:55,312
allora devi essere alla fine del
l'elenco, a quel punto si

1019
00:49:55,312 --> 00:49:56,562
può semplicemente inserirlo.

1020
00:49:56,562 --> 00:49:58,920

1021
00:49:58,920 --> 00:49:59,680
>> JASON HIRSCHHORN: questo mi piace.

1022
00:49:59,680 --> 00:50:00,500
Questo ha un senso.

1023
00:50:00,500 --> 00:50:03,390
Se il ciclo termina -

1024
00:50:03,390 --> 00:50:04,800
perché tornerà falso qui.

1025
00:50:04,800 --> 00:50:08,220
Quindi, se l'uscita dal ciclo, quindi siamo in
la fine della lista, o forse l'

1026
00:50:08,220 --> 00:50:10,690
avviare di una lista se non c'è niente
esso, che è la stessa come la fine.

1027
00:50:10,690 --> 00:50:12,770
Così ora vogliamo inserire
qualcosa qui.

1028
00:50:12,770 --> 00:50:17,380
Così come fa quel codice guarda, Marcus?

1029
00:50:17,380 --> 00:50:21,600
>> AUDIENCE: Se hai già ottenuto il nodo
malloced, si può solo dire

1030
00:50:21,600 --> 00:50:25,400
new_node-> next uguale nullo perché
deve essere alla fine.

1031
00:50:25,400 --> 00:50:27,510
Oppure new_node-> equivale prossimo null.

1032
00:50:27,510 --> 00:50:27,765
>> JASON HIRSCHHORN: OK.

1033
00:50:27,765 --> 00:50:28,190
Scusi.

1034
00:50:28,190 --> 00:50:35,760
New_node-> next uguale nullo
perché siamo alla fine.

1035
00:50:35,760 --> 00:50:36,460
Questo non metterla dentro

1036
00:50:36,460 --> 00:50:37,710
Come la mettiamo nella lista?

1037
00:50:37,710 --> 00:50:46,130

1038
00:50:46,130 --> 00:50:46,460
Giusto.

1039
00:50:46,460 --> 00:50:47,750
Questo è solo l'impostazione è uguale a.

1040
00:50:47,750 --> 00:50:50,940
No come possiamo effettivamente
metterlo nella lista?

1041
00:50:50,940 --> 00:50:54,170
Che cosa sta indicando la
fine della lista?

1042
00:50:54,170 --> 00:50:56,090
>> AUDIENCE: Head.

1043
00:50:56,090 --> 00:50:57,566
>> JASON HIRSCHHORN: Sorry?

1044
00:50:57,566 --> 00:50:59,440
>> AUDIENCE: Testa punta
alla fine della lista.

1045
00:50:59,440 --> 00:51:01,480
>> JASON HIRSCHHORN: Se non c'è nulla in
la lista, la testa è rivolta al

1046
00:51:01,480 --> 00:51:04,170
fine dell'elenco.

1047
00:51:04,170 --> 00:51:06,920
Così che lavorerà per il
primo inserimento.

1048
00:51:06,920 --> 00:51:09,810
Che dire se ci sono un paio
le cose nella lista?

1049
00:51:09,810 --> 00:51:12,470
Che noi non vogliamo impostare
testa pari a new_node.

1050
00:51:12,470 --> 00:51:13,790
Che cosa vogliamo fare?

1051
00:51:13,790 --> 00:51:15,610
Sì?

1052
00:51:15,610 --> 00:51:16,860
Probabilmente precedente.

1053
00:51:16,860 --> 00:51:23,560

1054
00:51:23,560 --> 00:51:24,810
Sarà che lavorare?

1055
00:51:24,810 --> 00:51:28,950

1056
00:51:28,950 --> 00:51:33,050
Ricordiamo che precedente è solo
un puntatore a un nodo.

1057
00:51:33,050 --> 00:51:34,770
Ed precedente è una variabile locale.

1058
00:51:34,770 --> 00:51:38,080
Quindi questa linea imposterà una variabile locale,
precedente, pari o

1059
00:51:38,080 --> 00:51:39,380
indicando questo nuovo nodo.

1060
00:51:39,380 --> 00:51:41,500
Che non sarà effettivamente messo
nella nostra lista, però.

1061
00:51:41,500 --> 00:51:44,330
Come abbiamo messo nella nostra lista?

1062
00:51:44,330 --> 00:51:45,620
Akchar?

1063
00:51:45,620 --> 00:51:46,870
>> PUBBLICO: penso che tu
fare corrente-> next.

1064
00:51:46,870 --> 00:51:50,186

1065
00:51:50,186 --> 00:51:52,550
>> JASON HIRSCHHORN: OK.

1066
00:51:52,550 --> 00:51:54,010
curr-> next.

1067
00:51:54,010 --> 00:51:58,768
Così ancora una volta, l'unica ragione per cui siamo giù
ecco, quello che fa corrente uguale?

1068
00:51:58,768 --> 00:51:59,760
>> AUDIENCE: Equals nullo.

1069
00:51:59,760 --> 00:52:01,790
>> JASON HIRSCHHORN: E allora cosa
succede se facciamo nulla-> next?

1070
00:52:01,790 --> 00:52:02,810
Cosa si vuole ottenere?

1071
00:52:02,810 --> 00:52:04,060
Avremo un segmentation fault.

1072
00:52:04,060 --> 00:52:06,600

1073
00:52:06,600 --> 00:52:08,880
>> AUDIENCE: Do curr uguale a null.

1074
00:52:08,880 --> 00:52:10,760
>> JASON HIRSCHHORN: Che è la stessa cosa
come precedente, però, perché c'è

1075
00:52:10,760 --> 00:52:12,820
una variabile locale stiamo impostando
uguale a questo nuovo nodo.

1076
00:52:12,820 --> 00:52:16,680

1077
00:52:16,680 --> 00:52:20,920
Torniamo alla nostra immagine
di inserire qualcosa.

1078
00:52:20,920 --> 00:52:25,500
Dire che stiamo inserendo alla fine
della lista, quindi proprio qui.

1079
00:52:25,500 --> 00:52:30,010
Abbiamo un puntatore corrente che è
che punta a null e un punto precedente

1080
00:52:30,010 --> 00:52:32,800
che sta puntando a 8.

1081
00:52:32,800 --> 00:52:35,330
Quindi cosa abbiamo bisogno di aggiornare, Avi?

1082
00:52:35,330 --> 00:52:36,680
>> AUDIENCE: precedente-> next?

1083
00:52:36,680 --> 00:52:41,980
>> JASON HIRSCHHORN: precedente-> successivo è quello
vogliamo aggiornare perché

1084
00:52:41,980 --> 00:52:44,960
effettivamente inserirla in
la fine dell'elenco.

1085
00:52:44,960 --> 00:52:47,220
Abbiamo ancora un bug, però,
che stiamo andando a correre in.

1086
00:52:47,220 --> 00:52:50,090
Qual è il bug?

1087
00:52:50,090 --> 00:52:50,790
Sì?

1088
00:52:50,790 --> 00:52:53,860
>> PUBBLICO: E 'intenzione di tornare
falso in questo caso?

1089
00:52:53,860 --> 00:52:56,380
>> JASON HIRSCHHORN: Oh, è sta
andando a restituire false.

1090
00:52:56,380 --> 00:52:57,430
Ma c'è un altro bug.

1091
00:52:57,430 --> 00:52:58,930
Quindi abbiamo bisogno di mettere in cambio vero.

1092
00:52:58,930 --> 00:53:01,370
>> AUDIENCE: Fa precedente ancora pari
nulla in cima alla lista?

1093
00:53:01,370 --> 00:53:03,645
>> JASON HIRSCHHORN: ancora So precedente
pari nullo all'inizio.

1094
00:53:03,645 --> 00:53:07,480

1095
00:53:07,480 --> 00:53:10,440
Quindi, come possiamo ottenere oltre che?

1096
00:53:10,440 --> 00:53:10,950
Sì?

1097
00:53:10,950 --> 00:53:15,280
>> PUBBLICO: Penso che si possa fare un controllo
prima che il ciclo while per vedere se è

1098
00:53:15,280 --> 00:53:16,610
una lista vuota.

1099
00:53:16,610 --> 00:53:17,000
>> JASON HIRSCHHORN: OK.

1100
00:53:17,000 --> 00:53:17,710
Quindi cerchiamo di andare qui.

1101
00:53:17,710 --> 00:53:18,530
Fare un controllo.

1102
00:53:18,530 --> 00:53:19,380
Se -

1103
00:53:19,380 --> 00:53:20,770
>> AUDIENCE: Quindi se la testa
uguale uguale a null.

1104
00:53:20,770 --> 00:53:24,300

1105
00:53:24,300 --> 00:53:26,320
>> JASON HIRSCHHORN: Se la testa
uguale uguale null -

1106
00:53:26,320 --> 00:53:27,790
che ci ti dirò se si tratta di un elenco vuoto.

1107
00:53:27,790 --> 00:53:31,090
>> PUBBLICO: E poi si
fare di testa equivale a nuovo.

1108
00:53:31,090 --> 00:53:34,740
>> JASON HIRSCHHORN: Testa
uguale new_node?

1109
00:53:34,740 --> 00:53:35,730
E che altro dobbiamo fare?

1110
00:53:35,730 --> 00:53:37,020
>> PUBBLICO: E poi si torna vero.

1111
00:53:37,020 --> 00:53:37,535
>> JASON HIRSCHHORN: Non proprio.

1112
00:53:37,535 --> 00:53:38,785
Ci manca un solo passo.

1113
00:53:38,785 --> 00:53:41,590

1114
00:53:41,590 --> 00:53:43,710
>> AUDIENCE: New_node prossimo
deve puntare a null.

1115
00:53:43,710 --> 00:53:44,570
>> JASON HIRSCHHORN: Esattamente, Alden.

1116
00:53:44,570 --> 00:53:46,600
E allora possiamo restituire true.

1117
00:53:46,600 --> 00:53:47,560
OK.

1118
00:53:47,560 --> 00:53:51,630
Ma è ancora una buona idea per fare le cose
alla fine della lista, giusto?

1119
00:53:51,630 --> 00:53:51,950
Bene.

1120
00:53:51,950 --> 00:53:54,450
Abbiamo ancora potrebbe effettivamente ottenere
alla fine della lista.

1121
00:53:54,450 --> 00:53:57,870
Quindi questo è il codice bene se siamo al
fine dell'elenco e ci sono alcuni

1122
00:53:57,870 --> 00:53:59,120
le cose nella lista?

1123
00:53:59,120 --> 00:54:01,830

1124
00:54:01,830 --> 00:54:02,040
Giusto?

1125
00:54:02,040 --> 00:54:03,540
Perché abbiamo ancora idea di Marcus.

1126
00:54:03,540 --> 00:54:06,870
Potremmo uscire da questo ciclo perché
siamo alla fine della lista.

1127
00:54:06,870 --> 00:54:09,308
Quindi cosa vogliamo ancora questo
codice qui?

1128
00:54:09,308 --> 00:54:10,520
>> PUBBLICO: Sì.

1129
00:54:10,520 --> 00:54:11,000
>> JASON HIRSCHHORN: Già.

1130
00:54:11,000 --> 00:54:14,190
E che cosa dobbiamo cambiare questo?

1131
00:54:14,190 --> 00:54:15,440
Vero.

1132
00:54:15,440 --> 00:54:19,580

1133
00:54:19,580 --> 00:54:21,640
Fa che il buon suono
a tutti fino ad ora?

1134
00:54:21,640 --> 00:54:22,420
Qualcuno ha -

1135
00:54:22,420 --> 00:54:23,480
Avi, hai qualcosa da aggiungere?

1136
00:54:23,480 --> 00:54:23,920
>> PUBBLICO: No.

1137
00:54:23,920 --> 00:54:25,276
>> JASON HIRSCHHORN: OK.

1138
00:54:25,276 --> 00:54:27,010
Così abbiamo fatto un paio di modifiche.

1139
00:54:27,010 --> 00:54:29,540
Abbiamo fatto questo controllo prima di
siamo andati in un elenco vuoto.

1140
00:54:29,540 --> 00:54:31,790
Così abbiamo preso cura di una lista vuota.

1141
00:54:31,790 --> 00:54:35,500
E qui abbiamo preso cura di inserimento
qualcosa alla fine dell'elenco.

1142
00:54:35,500 --> 00:54:38,930
Così sembra che questa presa ciclo while
cura delle cose in mezzo,

1143
00:54:38,930 --> 00:54:41,920
qualche parte nella lista se
sono cose nella lista.

1144
00:54:41,920 --> 00:54:42,280
>> OK.

1145
00:54:42,280 --> 00:54:44,310
Corriamo ancora questo programma.

1146
00:54:44,310 --> 00:54:50,170

1147
00:54:50,170 --> 00:54:50,755
Non è successo.

1148
00:54:50,755 --> 00:54:52,190
>> AUDIENCE: Non hai fatto esso.

1149
00:54:52,190 --> 00:54:53,940
>> JASON HIRSCHHORN: Oh,
Non ce l'ho fatta.

1150
00:54:53,940 --> 00:54:56,250
Buon punto, Michael.

1151
00:54:56,250 --> 00:54:57,500
Aggiungiamo un make collegato.

1152
00:54:57,500 --> 00:55:01,590

1153
00:55:01,590 --> 00:55:04,830
Linea 87 c'è un errore.

1154
00:55:04,830 --> 00:55:05,420
Linea 87.

1155
00:55:05,420 --> 00:55:06,600
Alden, questa era la linea che mi hai dato.

1156
00:55:06,600 --> 00:55:08,962
Cosa c'è di sbagliato?

1157
00:55:08,962 --> 00:55:10,710
>> AUDIENCE: Deve essere null.

1158
00:55:10,710 --> 00:55:11,000
>> JASON HIRSCHHORN: Excellent.

1159
00:55:11,000 --> 00:55:11,630
Esattamente.

1160
00:55:11,630 --> 00:55:13,290
Dovrebbe essere nullo.

1161
00:55:13,290 --> 00:55:15,210
Facciamo di nuovo.

1162
00:55:15,210 --> 00:55:17,220
Compilare.

1163
00:55:17,220 --> 00:55:17,890
OK.

1164
00:55:17,890 --> 00:55:19,400
Inseriamo tre.

1165
00:55:19,400 --> 00:55:20,570
L'inserto ha avuto successo.

1166
00:55:20,570 --> 00:55:21,660
Diciamo stamparlo.

1167
00:55:21,660 --> 00:55:23,590
Oh, se solo potessimo controllare.

1168
00:55:23,590 --> 00:55:25,500
Ma non abbiamo fatto il
stampare ancora la funzione.

1169
00:55:25,500 --> 00:55:27,840
Entriamo qualcos'altro.

1170
00:55:27,840 --> 00:55:29,090
Che cosa dovremmo entrare?

1171
00:55:29,090 --> 00:55:31,120

1172
00:55:31,120 --> 00:55:31,940
>> AUDIENCE: Seven.

1173
00:55:31,940 --> 00:55:33,340
>> JASON HIRSCHHORN: Seven?

1174
00:55:33,340 --> 00:55:34,590
>> PUBBLICO: Sì.

1175
00:55:34,590 --> 00:55:38,680

1176
00:55:38,680 --> 00:55:39,780
>> JASON HIRSCHHORN: Abbiamo un guasto seg.

1177
00:55:39,780 --> 00:55:43,760
Così abbiamo trovato uno, ma abbiamo chiaramente
non è possibile ottenere due.

1178
00:55:43,760 --> 00:55:45,690
E '5:07.

1179
00:55:45,690 --> 00:55:48,370
Così abbiamo potuto eseguire il debug di questo
per tre minuti.

1180
00:55:48,370 --> 00:55:51,240
Ma ho intenzione di lasciarci qui
e passare a tabelle hash.

1181
00:55:51,240 --> 00:55:54,290
Ma ancora una volta, le risposte di questo codice
Io con la posta elettronica a voi in un po '.

1182
00:55:54,290 --> 00:55:55,440
Siamo molto vicini ad esso.

1183
00:55:55,440 --> 00:55:58,300
I consigliamo vivamente di capire
cosa sta succedendo qui e risolverlo.

1184
00:55:58,300 --> 00:56:02,400
Quindi ti email È questo codice come
ben oltre la soluzione -

1185
00:56:02,400 --> 00:56:03,670
probabilmente la soluzione più tardi.

1186
00:56:03,670 --> 00:56:05,110
Prima di questo codice.

1187
00:56:05,110 --> 00:56:08,290
>> L'altra cosa che voglio fare prima di
finale è che non abbiamo liberato nulla.

1188
00:56:08,290 --> 00:56:10,370
Quindi voglio mostrarvi che cosa
valgrind assomiglia.

1189
00:56:10,370 --> 00:56:14,310
Se corriamo confini valgrind
sul nostro programma,. / collegato.

1190
00:56:14,310 --> 00:56:22,540
Sempre secondo questa diapositiva, abbiamo
dovrebbe funzionare valgrind con un certo tipo di

1191
00:56:22,540 --> 00:56:26,410
opzione, in questo caso
- Perdita-check = pieno.

1192
00:56:26,410 --> 00:56:27,660
Quindi cerchiamo di scrivere valgrind
- Perdita-check = pieno.

1193
00:56:27,660 --> 00:56:31,910

1194
00:56:31,910 --> 00:56:35,080
Quindi, questo verrà eseguito valgrind
sul nostro programma.

1195
00:56:35,080 --> 00:56:37,000
Ed ora il programma effettivamente eseguito.

1196
00:56:37,000 --> 00:56:40,190
Quindi stiamo andando a correre proprio come
prima, mettere qualcosa dentro

1197
00:56:40,190 --> 00:56:40,830
Ho intenzione di mettere in tre.

1198
00:56:40,830 --> 00:56:41,790
Che funziona.

1199
00:56:41,790 --> 00:56:43,202
Non ho intenzione di provare a mettere in qualcosa
altro, perché stiamo andando a

1200
00:56:43,202 --> 00:56:44,710
ottenere un falso segmento in quel caso.

1201
00:56:44,710 --> 00:56:46,700
Così sto solo andando a smettere.

1202
00:56:46,700 --> 00:56:50,160
>> E ora vedete qui
perdite e sintesi heap.

1203
00:56:50,160 --> 00:56:52,310
Queste sono le cose buone che
che si desidera controllare.

1204
00:56:52,310 --> 00:56:56,780
Così la sintesi heap - dice, in uso
all'uscita - otto byte in un blocco.

1205
00:56:56,780 --> 00:56:58,370
Che un blocco è l'
nodo che malloced.

1206
00:56:58,370 --> 00:57:02,230
Michael, hai detto prima che un nodo è di otto
punture perché ha il numero intero

1207
00:57:02,230 --> 00:57:02,680
e il puntatore.

1208
00:57:02,680 --> 00:57:04,550
Ecco, questo è il nostro nodo.

1209
00:57:04,550 --> 00:57:08,170
E poi si dice che abbiamo utilizzato malloc
sette volte e abbiamo liberato

1210
00:57:08,170 --> 00:57:08,940
qualcosa sei volte.

1211
00:57:08,940 --> 00:57:13,680
Ma non abbiamo mai chiamato libero, quindi non ho
idea di cosa sta parlando.

1212
00:57:13,680 --> 00:57:18,490
>> Ma basti dire che quando il
programma viene eseguito, malloc viene chiamato

1213
00:57:18,490 --> 00:57:20,330
in alcuni altri luoghi che
non c'è bisogno di preoccuparsi.

1214
00:57:20,330 --> 00:57:22,460
Così malloc fu probabilmente chiamato
in alcuni luoghi.

1215
00:57:22,460 --> 00:57:24,480
Non abbiamo bisogno di preoccuparsi dove.

1216
00:57:24,480 --> 00:57:26,240
Ma questo è davvero noi.

1217
00:57:26,240 --> 00:57:27,380
Questa prima linea è noi.

1218
00:57:27,380 --> 00:57:28,320
Abbiamo lasciato quel blocco.

1219
00:57:28,320 --> 00:57:30,330
E si può vedere che qui
nel riassunto perdita.

1220
00:57:30,330 --> 00:57:31,950
Ancora raggiungibile -

1221
00:57:31,950 --> 00:57:32,930
otto byte in un blocco.

1222
00:57:32,930 --> 00:57:34,100
Ciò significa che la memoria -

1223
00:57:34,100 --> 00:57:35,730
abbiamo trapelato che la memoria.

1224
00:57:35,730 --> 00:57:37,570
Definitivamente perso -

1225
00:57:37,570 --> 00:57:38,770
qualcosa si perde per sempre.

1226
00:57:38,770 --> 00:57:40,590
In genere, non sarà
vedi nulla.

1227
00:57:40,590 --> 00:57:44,780
Ancora raggiungibile è generalmente dove
vedrai cose, dove si vuole

1228
00:57:44,780 --> 00:57:48,900
guardare per vedere quale codice si dovrebbe
hanno liberato ma si è dimenticato di liberare.

1229
00:57:48,900 --> 00:57:53,170
>> E poi se questo non era il caso,
se abbiamo fatto tutto gratuito,

1230
00:57:53,170 --> 00:57:54,360
possiamo controllare quello.

1231
00:57:54,360 --> 00:57:57,330
Diciamo solo eseguire il programma
non mettere in nulla.

1232
00:57:57,330 --> 00:57:59,800
Vedrete qui in uso in uscita -

1233
00:57:59,800 --> 00:58:01,310
zero byte in blocchi zero.

1234
00:58:01,310 --> 00:58:06,310
Ciò significa che non avevamo niente di sinistra
quando questo programma terminato.

1235
00:58:06,310 --> 00:58:12,090
Quindi, prima di girare in pset6, eseguire valgrind
e assicurarsi che non si dispone di

1236
00:58:12,090 --> 00:58:15,310
eventuali perdite di memoria nel vostro programma.

1237
00:58:15,310 --> 00:58:17,910
Se avete qualunque domande con valgrind,
sentitevi liberi di raggiungere.

1238
00:58:17,910 --> 00:58:18,700
Ma questo è come lo si utilizza.

1239
00:58:18,700 --> 00:58:20,890
Molto semplice - vedere se si
avere in uso all'uscita -

1240
00:58:20,890 --> 00:58:22,270
tutti i byte in tutti i blocchi.

1241
00:58:22,270 --> 00:58:27,890

1242
00:58:27,890 --> 00:58:29,580
>> Così stavamo lavorando sul nodo di inserimento.

1243
00:58:29,580 --> 00:58:33,840
Ho avuto altre due funzioni qui -
stampare i nodi e nodi liberi.

1244
00:58:33,840 --> 00:58:37,780
Anche queste sono funzioni che sono
sarà un bene per voi di praticare

1245
00:58:37,780 --> 00:58:40,990
perché vi aiuterà non solo con
questi esercizi di esempio, ma anche

1246
00:58:40,990 --> 00:58:42,180
sul problema posto.

1247
00:58:42,180 --> 00:58:44,230
Hanno una mappa su praticamente vicino alle cose
si sta andando ad avere a che fare in

1248
00:58:44,230 --> 00:58:45,010
problema set.

1249
00:58:45,010 --> 00:58:47,640
Ma io voglio fare in modo
Tocchiamo tutto.

1250
00:58:47,640 --> 00:58:50,400
E le tabelle hash sono essenziali anche per
quello che stiamo facendo in questa sezione

1251
00:58:50,400 --> 00:58:51,980
settimana - o nel problema proposto.

1252
00:58:51,980 --> 00:58:55,200
>> Quindi stiamo andando a finire la sezione
parlando di tabelle hash.

1253
00:58:55,200 --> 00:58:58,140
Se notate ho fatto un
piccola tabella hash.

1254
00:58:58,140 --> 00:59:00,020
Non è questo che stiamo parlando
in merito, tuttavia.

1255
00:59:00,020 --> 00:59:03,540
Stiamo parlando di un diverso
tipo di tabelle hash.

1256
00:59:03,540 --> 00:59:07,300
E al suo interno, una tabella hash
non è altro che un

1257
00:59:07,300 --> 00:59:08,860
matrice più una funzione di hash.

1258
00:59:08,860 --> 00:59:11,150
Stiamo andando a parlare per un po 'solo per
assicurarsi che tutti capiscono quello che un

1259
00:59:11,150 --> 00:59:12,110
funzione hash è.

1260
00:59:12,110 --> 00:59:15,420
E io ti sto dicendo ora che è
niente di più di due cose -

1261
00:59:15,420 --> 00:59:18,590
una matrice e una funzione hash.

1262
00:59:18,590 --> 00:59:20,716
E qui sono i passi attraverso
che tale opera.

1263
00:59:20,716 --> 00:59:31,560

1264
00:59:31,560 --> 00:59:32,810
>> Ecco il nostro array.

1265
00:59:32,810 --> 00:59:38,460

1266
00:59:38,460 --> 00:59:39,460
C'è la nostra funzione.

1267
00:59:39,460 --> 00:59:43,180
In particolare, le funzioni di hash devono
fare un paio di cose con questo.

1268
00:59:43,180 --> 00:59:45,040
Io vado a parlare specificamente
su questo problema impostato.

1269
00:59:45,040 --> 00:59:46,450
E 'probabilmente andando a
prendere in una stringa.

1270
00:59:46,450 --> 00:59:50,570

1271
00:59:50,570 --> 00:59:51,770
E che cosa sta andando a tornare?

1272
00:59:51,770 --> 00:59:52,640
Che tipo di dati?

1273
00:59:52,640 --> 00:59:54,260
Alden?

1274
00:59:54,260 --> 00:59:55,760
Ritorno, la vostra funzione di hash?

1275
00:59:55,760 --> 00:59:58,760
Un numero intero.

1276
00:59:58,760 --> 01:00:01,700
Quindi questo è ciò che l'hash
tabella consiste di -

1277
01:00:01,700 --> 01:00:05,430
una tabella in forma di matrice
e una funzione hash.

1278
01:00:05,430 --> 01:00:06,010
Come funziona?

1279
01:00:06,010 --> 01:00:07,300
Funziona in tre fasi.

1280
01:00:07,300 --> 01:00:08,740
Diamo un tasto.

1281
01:00:08,740 --> 01:00:11,470
In questo caso, daremo una stringa.

1282
01:00:11,470 --> 01:00:18,140
Chiamiamo la funzione di hash per passo uno
sulla chiave e otteniamo un valore.

1283
01:00:18,140 --> 01:00:20,310
>> In particolare, diremo
otteniamo un numero intero.

1284
01:00:20,310 --> 01:00:25,630
Tale numero intero, ci sono molto specifici
limiti a ciò che può essere intero.

1285
01:00:25,630 --> 01:00:28,880
In questo esempio, la serie
è di dimensione tre.

1286
01:00:28,880 --> 01:00:32,330
Quindi, quali numeri può che essere intero.

1287
01:00:32,330 --> 01:00:35,970
Qual è il range di valori validi per
che integer, il tipo restituito di questo

1288
01:00:35,970 --> 01:00:37,220
hash funzione?

1289
01:00:37,220 --> 01:00:40,440

1290
01:00:40,440 --> 01:00:42,110
Zero, uno e due.

1291
01:00:42,110 --> 01:00:46,060
Il punto della funzione di hash è quello
capire il posto nella matrice

1292
01:00:46,060 --> 01:00:47,790
dove la nostra chiave sta andando.

1293
01:00:47,790 --> 01:00:51,290
Ci sono solo tre possibili
posti qui -

1294
01:00:51,290 --> 01:00:52,130
zero, uno, o due.

1295
01:00:52,130 --> 01:00:55,360
Quindi questa funzione meglio di restituzione
zero, uno, o due.

1296
01:00:55,360 --> 01:00:58,740
Alcuni indice valido in questo array.

1297
01:00:58,740 --> 01:01:02,770
>> E poi, a seconda di dove ritorna,
potete vedere ci open array

1298
01:01:02,770 --> 01:01:03,730
inquadrare il valore.

1299
01:01:03,730 --> 01:01:05,800
Ecco dove abbiamo messo la chiave.

1300
01:01:05,800 --> 01:01:11,280
Così ci buttiamo nella zucca,
usciamo zero.

1301
01:01:11,280 --> 01:01:15,540
A supporto di matrice 0, abbiamo messo la zucca.

1302
01:01:15,540 --> 01:01:21,070
Gettiamo nei gatti, usciamo uno.

1303
01:01:21,070 --> 01:01:24,110
Abbiamo messo gatto in uno.

1304
01:01:24,110 --> 01:01:25,480
Abbiamo messo in ragno.

1305
01:01:25,480 --> 01:01:26,710
Scendiamo due.

1306
01:01:26,710 --> 01:01:30,200
Abbiamo messo ragno a staffa due array.

1307
01:01:30,200 --> 01:01:32,300
Sarebbe così bello se
ha funzionato così.

1308
01:01:32,300 --> 01:01:35,570
Ma purtroppo, come vedremo,
è un po 'più complicato.

1309
01:01:35,570 --> 01:01:37,570
>> Prima di arrivare lì, tutte le domande
su questa base

1310
01:01:37,570 --> 01:01:38,820
set-up di una tabella di hash?

1311
01:01:38,820 --> 01:01:49,050

1312
01:01:49,050 --> 01:01:51,940
Questa è l'immagine di esattamente
quello che abbiamo disegnato sul tabellone.

1313
01:01:51,940 --> 01:01:55,420
Ma poiché abbiamo disegnato sulla lavagna, mi
Non ho intenzione di andare in ulteriormente.

1314
01:01:55,420 --> 01:02:00,430
Essenzialmente chiavi, la scatola nera magica -
o in questo caso, scatola verde acqua - di un

1315
01:02:00,430 --> 01:02:02,410
funzione di hash li mette in secchi.

1316
01:02:02,410 --> 01:02:04,690
E in questo esempio siamo
non mettere il nome.

1317
01:02:04,690 --> 01:02:07,880
Stiamo mettendo il telefono associato
numero del nome nel secchio.

1318
01:02:07,880 --> 01:02:10,430
Ma si potrebbe benissimo solo
mettere il nome nel secchio.

1319
01:02:10,430 --> 01:02:12,950
>> Questo è solo un quadro di ciò che
abbiamo disegnato sulla scheda.

1320
01:02:12,950 --> 01:02:14,460
Abbiamo potenziali insidie, però.

1321
01:02:14,460 --> 01:02:17,470
E ci sono due in particolare
diapositive che voglio andare oltre.

1322
01:02:17,470 --> 01:02:20,230
Il primo è di circa
una funzione hash.

1323
01:02:20,230 --> 01:02:22,620
Così ho fatto la domanda, che cosa
fa una buona funzione di hash?

1324
01:02:22,620 --> 01:02:24,220
Io do due risposte.

1325
01:02:24,220 --> 01:02:26,630
Il primo è che è deterministico.

1326
01:02:26,630 --> 01:02:29,660
Nel contesto di funzioni hash,
cosa significa questo?

1327
01:02:29,660 --> 01:02:37,840

1328
01:02:37,840 --> 01:02:39,282
Sì?

1329
01:02:39,282 --> 01:02:42,850
>> PUBBLICO: Si può trovare l'
indice in tempo costante?

1330
01:02:42,850 --> 01:02:43,810
>> JASON HIRSCHHORN: Che
Non è ciò che significa.

1331
01:02:43,810 --> 01:02:44,725
Ma questa è una buona congettura.

1332
01:02:44,725 --> 01:02:46,100
Chiunque altro ha una supposizione
a cosa significa questo?

1333
01:02:46,100 --> 01:02:47,780
Che una buona funzione di hash
è deterministico?

1334
01:02:47,780 --> 01:02:48,280
Annie?

1335
01:02:48,280 --> 01:02:51,680
>> AUDIENCE: che una chiave può essere mappato solo
ad un posto nella tabella hash.

1336
01:02:51,680 --> 01:02:53,070
>> JASON HIRSCHHORN: Ecco
esattamente a destra.

1337
01:02:53,070 --> 01:02:57,430
Ogni volta che si mette in zucca,
restituisce sempre zero.

1338
01:02:57,430 --> 01:03:01,660
Se si mette in zucca e il vostro hash
funzione restituisce zero, ma ha un

1339
01:03:01,660 --> 01:03:06,060
probabilità di ritorno qualcosa
altro maggiore di zero -

1340
01:03:06,060 --> 01:03:09,280
così forse si può tornare a volte si
o altre due volte -

1341
01:03:09,280 --> 01:03:11,100
che non è una buona funzione hash.

1342
01:03:11,100 --> 01:03:11,800
Hai perfettamente ragione.

1343
01:03:11,800 --> 01:03:15,680
La vostra funzione hash dovrebbe restituire l'
stesso intero esatto, in questo caso, per

1344
01:03:15,680 --> 01:03:17,780
la stessa stringa esatta.

1345
01:03:17,780 --> 01:03:22,210
>> Forse restituisce lo stesso intero esatto
per la stessa stringa esatta

1346
01:03:22,210 --> 01:03:24,430
indipendentemente dalla capitalizzazione.

1347
01:03:24,430 --> 01:03:27,980
Ma in questo caso è ancora
deterministica perché le cose più

1348
01:03:27,980 --> 01:03:29,350
sono mappati sullo stesso valore.

1349
01:03:29,350 --> 01:03:30,170
Va bene.

1350
01:03:30,170 --> 01:03:32,615
Finché vi è un solo
uscita per un dato ingresso.

1351
01:03:32,615 --> 01:03:35,630

1352
01:03:35,630 --> 01:03:36,350
>> OK.

1353
01:03:36,350 --> 01:03:38,340
La seconda cosa è che
restituisce indici validi.

1354
01:03:38,340 --> 01:03:40,220
Abbiamo portato up che in precedenza.

1355
01:03:40,220 --> 01:03:41,860
Questa funzione hash -

1356
01:03:41,860 --> 01:03:43,710
oh boy -

1357
01:03:43,710 --> 01:03:46,840
una funzione di hash deve
ritorno indici validi.

1358
01:03:46,840 --> 01:03:47,740
Così dicono -

1359
01:03:47,740 --> 01:03:48,990
torniamo a questo esempio.

1360
01:03:48,990 --> 01:03:52,580

1361
01:03:52,580 --> 01:03:57,540
La mia funzione hash conta up
le lettere della parola.

1362
01:03:57,540 --> 01:03:58,380
Questa è la funzione hash.

1363
01:03:58,380 --> 01:03:59,740
E che restituisce intero.

1364
01:03:59,740 --> 01:04:04,280
Quindi, se ho la parola A, è
andando a tornare uno.

1365
01:04:04,280 --> 01:04:06,900
E sta andando a mettere un proprio qui.

1366
01:04:06,900 --> 01:04:09,430
Cosa succede se metto nella parola pipistrello?

1367
01:04:09,430 --> 01:04:11,310
E 'intenzione di tornare tre.

1368
01:04:11,310 --> 01:04:12,560
Dov'è bat va?

1369
01:04:12,560 --> 01:04:18,730

1370
01:04:18,730 --> 01:04:19,750
>> E non va bene.

1371
01:04:19,750 --> 01:04:21,000
Ma ha bisogno di andare da qualche parte.

1372
01:04:21,000 --> 01:04:23,340
Questa è la mia tabella di hash, dopo tutto, e
tutto deve andare da qualche parte.

1373
01:04:23,340 --> 01:04:24,590
Allora, dove dovrebbe andare pipistrello?

1374
01:04:24,590 --> 01:04:28,020

1375
01:04:28,020 --> 01:04:28,710
Qualche idea?

1376
01:04:28,710 --> 01:04:29,450
Indovina?

1377
01:04:29,450 --> 01:04:30,280
Buone ipotesi?

1378
01:04:30,280 --> 01:04:31,220
>> AUDIENCE: Zero.

1379
01:04:31,220 --> 01:04:32,120
>> JASON HIRSCHHORN: Perché lo zero?

1380
01:04:32,120 --> 01:04:35,990
>> AUDIENCE: Perché tre
modulo a tre è pari a zero?

1381
01:04:35,990 --> 01:04:38,620
>> JASON HIRSCHHORN: Three
modulo tre è zero.

1382
01:04:38,620 --> 01:04:40,810
Questa è una grande congettura,
e questo è corretto.

1383
01:04:40,810 --> 01:04:43,870
Quindi in questo caso dovrebbe
probabilmente andare a zero.

1384
01:04:43,870 --> 01:04:51,080
Quindi un buon modo per garantire che questo hash
funzione restituisce solo gli indici validi è

1385
01:04:51,080 --> 01:04:54,580
a con modulo per la dimensione della tabella.

1386
01:04:54,580 --> 01:04:57,360
Se si MODULO qualunque cosa rendimenti
tre, si sta andando sempre di ottenere

1387
01:04:57,360 --> 01:05:00,930
qualcosa tra zero, uno e due.

1388
01:05:00,930 --> 01:05:05,160
E se questo ritorna sempre sette, e
sempre Modulo per tre, sei

1389
01:05:05,160 --> 01:05:06,030
sempre andando ad ottenere la stessa cosa.

1390
01:05:06,030 --> 01:05:09,270
>> Quindi è ancora deterministica
se MODULO.

1391
01:05:09,270 --> 01:05:11,420
Ma che farà in modo che si
mai ottenere qualcosa -

1392
01:05:11,420 --> 01:05:12,940
un settore non valida.

1393
01:05:12,940 --> 01:05:16,840
In generale, tale modulo dovrebbe accadere
all'interno della vostra funzione di hash.

1394
01:05:16,840 --> 01:05:18,240
Quindi non c'è bisogno di preoccuparsi di questo.

1395
01:05:18,240 --> 01:05:20,555
È solo possibile garantire che
questo è un indice valido.

1396
01:05:20,555 --> 01:05:23,700

1397
01:05:23,700 --> 01:05:26,700
Tutte le domande su questo
potenziale problema?

1398
01:05:26,700 --> 01:05:36,590

1399
01:05:36,590 --> 01:05:39,060
>> OK.

1400
01:05:39,060 --> 01:05:40,290
E ci andiamo.

1401
01:05:40,290 --> 01:05:42,890
Avanti potenziale insidia, e
questo è quello grande.

1402
01:05:42,890 --> 01:05:46,880
Che cosa succede se due tasti mappa
allo stesso valore?

1403
01:05:46,880 --> 01:05:49,350
Quindi ci sono due modi per gestire questo.

1404
01:05:49,350 --> 01:05:53,140

1405
01:05:53,140 --> 01:05:56,020
Il primo si chiama lineare
sondaggio, che sono

1406
01:05:56,020 --> 01:05:57,300
non intenzione di andare oltre.

1407
01:05:57,300 --> 01:06:01,120
Ma è necessario avere familiarità con il modo
che funziona e di cosa si tratta.

1408
01:06:01,120 --> 01:06:05,610
>> La seconda ho intenzione di andare oltre
perché è quello che molti

1409
01:06:05,610 --> 01:06:08,290
persone probabilmente finirà per decidere
da utilizzare nel loro insieme problema.

1410
01:06:08,290 --> 01:06:09,820
Naturalmente, non è necessario.

1411
01:06:09,820 --> 01:06:15,280
Ma per il set problema, molte persone
tendono a scegliere di creare una tabella hash

1412
01:06:15,280 --> 01:06:17,950
con concatenazioni separate da implementare
loro vocabolario.

1413
01:06:17,950 --> 01:06:21,390
Quindi stiamo intenzione di andare oltre ciò che significa
per creare una tabella hash con

1414
01:06:21,390 --> 01:06:23,890
concatenazioni separate.

1415
01:06:23,890 --> 01:06:26,260
>> Così ho messo in zucca.

1416
01:06:26,260 --> 01:06:29,560
Esso restituisce zero.

1417
01:06:29,560 --> 01:06:31,410
E ho messo la zucca qui.

1418
01:06:31,410 --> 01:06:35,880

1419
01:06:35,880 --> 01:06:37,930
Poi ho messo in -

1420
01:06:37,930 --> 01:06:39,922
che cosa è un'altra cosa Halloween a tema?

1421
01:06:39,922 --> 01:06:42,200
>> AUDIENCE: Candy.

1422
01:06:42,200 --> 01:06:42,770
>> JASON HIRSCHHORN: Candy!

1423
01:06:42,770 --> 01:06:43,910
Questo è un grande.

1424
01:06:43,910 --> 01:06:47,760
Ho messo in caramelle e caramelle
Mi dà anche zero.

1425
01:06:47,760 --> 01:06:49,350
Cosa faccio?

1426
01:06:49,350 --> 01:06:51,940
Tutte le idee?

1427
01:06:51,940 --> 01:06:53,940
Perché tutti voi sapete sorta di
ciò concatenazioni separate è.

1428
01:06:53,940 --> 01:06:55,190
Quindi, tutte le idee che cosa fare?

1429
01:06:55,190 --> 01:06:58,170

1430
01:06:58,170 --> 01:06:59,110
Già.

1431
01:06:59,110 --> 01:07:03,810
>> AUDIENCE: Mettere la stringa
effettivamente nella tabella hash.

1432
01:07:03,810 --> 01:07:08,910
>> JASON HIRSCHHORN: Così stiamo andando a
disegnare la buona idea qui.

1433
01:07:08,910 --> 01:07:09,340
OK.

1434
01:07:09,340 --> 01:07:12,290
>> AUDIENCE: Avere la hashtable
[Incomprensibile]

1435
01:07:12,290 --> 01:07:16,640
il puntatore che punta a
l'inizio di un elenco.

1436
01:07:16,640 --> 01:07:20,930
E poi hanno la zucca essere il primo valore
in tale lista collegata e caramelle essere

1437
01:07:20,930 --> 01:07:22,800
il secondo valore in quella lista collegata.

1438
01:07:22,800 --> 01:07:23,420
>> JASON HIRSCHHORN: OK.

1439
01:07:23,420 --> 01:07:24,670
Marcus, che era eccezionale.

1440
01:07:24,670 --> 01:07:26,160
Io vado a rompere che verso il basso.

1441
01:07:26,160 --> 01:07:28,890
Marcus sta dicendo di non
sovrascrivere zucca.

1442
01:07:28,890 --> 01:07:30,660
Che sarebbe male.

1443
01:07:30,660 --> 01:07:33,640
Non mettere caramelle da qualche altra parte.

1444
01:07:33,640 --> 01:07:35,390
Stiamo andando a metterli entrambi a zero.

1445
01:07:35,390 --> 01:07:37,770
Ma stiamo andando ad affrontare
mettendoli a zero

1446
01:07:37,770 --> 01:07:39,395
creazione di un elenco a zero.

1447
01:07:39,395 --> 01:07:42,430
E stiamo andando a creare un elenco di
tutto ciò che mappato a zero.

1448
01:07:42,430 --> 01:07:47,960
E il modo migliore che abbiamo imparato a creare
una lista che può crescere e ridursi

1449
01:07:47,960 --> 01:07:49,840
non è dinamicamente all'interno
un altro array.

1450
01:07:49,840 --> 01:07:51,510
Quindi non un array multi-dimensionale.

1451
01:07:51,510 --> 01:07:54,080
Ma per creare solo una lista collegata.

1452
01:07:54,080 --> 01:07:55,330
>> Così che cosa ha proposto -

1453
01:07:55,330 --> 01:07:57,950

1454
01:07:57,950 --> 01:07:59,200
Ho intenzione di ottenere un nuovo -

1455
01:07:59,200 --> 01:08:15,380

1456
01:08:15,380 --> 01:08:19,689
è creare un array con i puntatori,
un array di puntatori.

1457
01:08:19,689 --> 01:08:20,580
OK.

1458
01:08:20,580 --> 01:08:24,180
Qualsiasi idea o suggerimento che tipo
di questi puntatori dovrebbe essere?

1459
01:08:24,180 --> 01:08:26,290
Marcus?

1460
01:08:26,290 --> 01:08:27,250
>> AUDIENCE: Puntatori a -

1461
01:08:27,250 --> 01:08:28,609
>> JASON HIRSCHHORN: Perché
ha detto una lista collegata, così -

1462
01:08:28,609 --> 01:08:29,520
>> AUDIENCE: puntatori nodo?

1463
01:08:29,520 --> 01:08:30,670
>> JASON HIRSCHHORN: puntatori nodo.

1464
01:08:30,670 --> 01:08:32,830
Se le cose nel nostro collegati
elenco sono nodi poi

1465
01:08:32,830 --> 01:08:34,370
dovrebbe essere puntatori nodi.

1466
01:08:34,370 --> 01:08:35,939
E cosa uguali inizialmente?

1467
01:08:35,939 --> 01:08:36,990
>> AUDIENCE: Null.

1468
01:08:36,990 --> 01:08:38,240
>> JASON HIRSCHHORN: Null.

1469
01:08:38,240 --> 01:08:44,540

1470
01:08:44,540 --> 01:08:46,080
Quindi c'è la cosa vuota.

1471
01:08:46,080 --> 01:08:47,170
Ritorna zucca zero.

1472
01:08:47,170 --> 01:08:48,569
Che cosa facciamo?

1473
01:08:48,569 --> 01:08:49,609
Camminare me attraverso di essa?

1474
01:08:49,609 --> 01:08:50,810
In realtà, Marcus già mi ha dato.

1475
01:08:50,810 --> 01:08:52,439
Qualcun altro me a piedi attraverso di essa.

1476
01:08:52,439 --> 01:08:54,760
Cosa facciamo quando -

1477
01:08:54,760 --> 01:08:56,609
questo sembra molto simile a
quello che stavamo solo facendo.

1478
01:08:56,609 --> 01:08:57,396
Avi.

1479
01:08:57,396 --> 01:08:59,090
>> PUBBLICO: Vado a prendere una congettura.

1480
01:08:59,090 --> 01:09:01,250
Così, quando si arriva caramelle.

1481
01:09:01,250 --> 01:09:01,640
>> JASON HIRSCHHORN: Già.

1482
01:09:01,640 --> 01:09:03,120
Beh, abbiamo ottenuto la zucca.

1483
01:09:03,120 --> 01:09:03,870
Prendiamo il nostro primo.

1484
01:09:03,870 --> 01:09:04,324
Abbiamo ottenuto zucca.

1485
01:09:04,324 --> 01:09:04,779
>> AUDIENCE: OK.

1486
01:09:04,779 --> 01:09:05,880
Ritorna zucca zero.

1487
01:09:05,880 --> 01:09:08,770
Così si mette in questo.

1488
01:09:08,770 --> 01:09:10,810
O addirittura, lo metti
nella lista collegata.

1489
01:09:10,810 --> 01:09:13,550
>> JASON HIRSCHHORN: Come facciamo a
metterlo nella lista collegata?

1490
01:09:13,550 --> 01:09:15,479
>> PUBBLICO: Oh, la sintassi?

1491
01:09:15,479 --> 01:09:16,240
>> JASON HIRSCHHORN: Solo a piedi -

1492
01:09:16,240 --> 01:09:16,740
dire di più.

1493
01:09:16,740 --> 01:09:19,310
Che cosa facciamo?

1494
01:09:19,310 --> 01:09:22,100
>> AUDIENCE: Devi solo inserire
come primo nodo.

1495
01:09:22,100 --> 01:09:22,675
>> JASON HIRSCHHORN: OK.

1496
01:09:22,675 --> 01:09:29,069
Così abbiamo il nostro nodo, zucca.

1497
01:09:29,069 --> 01:09:31,560
E ora come faccio inserisco?

1498
01:09:31,560 --> 01:09:34,590

1499
01:09:34,590 --> 01:09:37,090
>> PUBBLICO: È possibile assegnare
al puntatore.

1500
01:09:37,090 --> 01:09:37,970
>> JASON HIRSCHHORN: Quale puntatore?

1501
01:09:37,970 --> 01:09:39,620
>> PUBBLICO: Il puntatore a zero.

1502
01:09:39,620 --> 01:09:41,420
>> JASON HIRSCHHORN: Allora, dove
fa questo punto?

1503
01:09:41,420 --> 01:09:42,810
>> PUBBLICO: A nulla adesso.

1504
01:09:42,810 --> 01:09:43,529
>> JASON HIRSCHHORN: Beh,
è rivolto a null.

1505
01:09:43,529 --> 01:09:44,499
Ma sto mettendo in zucca.

1506
01:09:44,499 --> 01:09:46,053
Allora, dove dovrebbe puntare?

1507
01:09:46,053 --> 01:09:46,880
>> PUBBLICO: Per zucca.

1508
01:09:46,880 --> 01:09:47,399
>> JASON HIRSCHHORN: Per zucca.

1509
01:09:47,399 --> 01:09:48,760
Esattamente.

1510
01:09:48,760 --> 01:09:50,010
Quindi questo indica zucca.

1511
01:09:50,010 --> 01:09:52,500

1512
01:09:52,500 --> 01:09:54,250
E da dove viene questo puntatore
al punto di zucca?

1513
01:09:54,250 --> 01:09:57,986

1514
01:09:57,986 --> 01:09:58,340
A

1515
01:09:58,340 --> 01:09:58,590
>> AUDIENCE: Null.

1516
01:09:58,590 --> 01:09:59,210
>> JASON HIRSCHHORN: NULL.

1517
01:09:59,210 --> 01:10:00,460
Esattamente.

1518
01:10:00,460 --> 01:10:03,570

1519
01:10:03,570 --> 01:10:05,140
Così abbiamo appena inserito qualcosa
nella lista collegata.

1520
01:10:05,140 --> 01:10:07,210
Abbiamo appena scritto questo codice per fare questo.

1521
01:10:07,210 --> 01:10:09,520
Quasi abbiamo quasi ottenuto
completamente incrinato.

1522
01:10:09,520 --> 01:10:10,790
Ora inseriamo caramelle.

1523
01:10:10,790 --> 01:10:13,480
La nostra caramella va anche a zero.

1524
01:10:13,480 --> 01:10:16,100
Allora cosa facciamo con la caramella?

1525
01:10:16,100 --> 01:10:18,790
>> AUDIENCE: Dipende se o
Non stiamo cercando di risolvere.

1526
01:10:18,790 --> 01:10:19,640
>> JASON HIRSCHHORN: Ecco
esattamente a destra.

1527
01:10:19,640 --> 01:10:21,070
Dipende se o non
stiamo cercando di risolvere.

1528
01:10:21,070 --> 01:10:22,660
Supponiamo che non siamo
andando a risolverlo.

1529
01:10:22,660 --> 01:10:24,880
>> PUBBLICO: E allora, come abbiamo discusso
prima, è semplice basta metterlo

1530
01:10:24,880 --> 01:10:28,590
proprio all'inizio in modo che il puntatore
da zero punti a caramella.

1531
01:10:28,590 --> 01:10:29,020
>> JASON HIRSCHHORN: OK.

1532
01:10:29,020 --> 01:10:29,380
Aspetta.

1533
01:10:29,380 --> 01:10:30,630
Permettetemi di creare caramelle proprio qui.

1534
01:10:30,630 --> 01:10:34,030

1535
01:10:34,030 --> 01:10:35,150
Quindi questo puntatore -

1536
01:10:35,150 --> 01:10:37,590
>> PUBBLICO: Sì, ora dovrebbe
si punta a caramelle.

1537
01:10:37,590 --> 01:10:40,580
Poi hanno il puntatore da
Punto di caramelle per la zucca.

1538
01:10:40,580 --> 01:10:43,140

1539
01:10:43,140 --> 01:10:44,560
>> JASON HIRSCHHORN: Ti piace questo?

1540
01:10:44,560 --> 01:10:47,380
E dire che abbiamo ottenuto un altro
cosa per mappare a zero?

1541
01:10:47,380 --> 01:10:48,660
>> PUBBLICO: Beh, basta
fare la stessa cosa?

1542
01:10:48,660 --> 01:10:50,290
>> JASON HIRSCHHORN: Fate la stessa cosa.

1543
01:10:50,290 --> 01:10:53,700
Quindi, in questo caso, se non lo facciamo
desidera mantenere ordinati esso

1544
01:10:53,700 --> 01:10:55,270
suoni piuttosto semplice.

1545
01:10:55,270 --> 01:10:59,920
Prendiamo il puntatore Indice
dato dalla nostra funzione di hash.

1546
01:10:59,920 --> 01:11:03,830
Dobbiamo quel punto il nostro nuovo nodo.

1547
01:11:03,830 --> 01:11:07,830
E poi qualunque cosa puntava
precedentemente -

1548
01:11:07,830 --> 01:11:10,620
in questo caso nulla, nella
secondo caso pumpkin -

1549
01:11:10,620 --> 01:11:15,310
che, qualunque cosa sta puntando a
precedenza, si aggiunge nella successiva

1550
01:11:15,310 --> 01:11:17,810
il nuovo nodo.

1551
01:11:17,810 --> 01:11:19,650
Stiamo inserendo qualcosa
all'inizio.

1552
01:11:19,650 --> 01:11:22,900
In realtà questo è molto più semplice di
cercando di mantenere la lista ordinata.

1553
01:11:22,900 --> 01:11:25,340
Ma ancora una volta, la ricerca sarà
più complicato qui.

1554
01:11:25,340 --> 01:11:28,300
Avremo sempre di andare fino alla fine.

1555
01:11:28,300 --> 01:11:29,650
>> OK.

1556
01:11:29,650 --> 01:11:32,750
Avete domande su concatenazioni separate?

1557
01:11:32,750 --> 01:11:34,690
Come funziona?

1558
01:11:34,690 --> 01:11:35,820
Si prega di chiedere adesso.

1559
01:11:35,820 --> 01:11:39,260
Ho molta voglia di assicurarsi che tutti i
capire questo prima di testa fuori.

1560
01:11:39,260 --> 01:11:48,410

1561
01:11:48,410 --> 01:11:52,060
>> AUDIENCE: Perché metti la zucca
e caramelle nella stessa

1562
01:11:52,060 --> 01:11:54,108
parte della tabella hash?

1563
01:11:54,108 --> 01:11:55,860
>> JASON HIRSCHHORN: Bella domanda.

1564
01:11:55,860 --> 01:11:59,140
Perché li mettiamo nella stessa
parte della tabella hash?

1565
01:11:59,140 --> 01:12:03,200
Beh, in questo caso la nostra funzione di hash
restituisce zero per entrambi.

1566
01:12:03,200 --> 01:12:05,310
Quindi hanno bisogno di andare a zero indice
perché è lì che stiamo andando a

1567
01:12:05,310 --> 01:12:07,420
cercarli, se mai
voglia di guardare in su.

1568
01:12:07,420 --> 01:12:11,750
Anche in questo caso, con un approccio scansione lineare
noi non li avremmo messi entrambi a zero.

1569
01:12:11,750 --> 01:12:13,900
Ma nell'approccio catena separata,
stiamo andando a metterli entrambi a zero

1570
01:12:13,900 --> 01:12:16,620
e quindi creare un elenco off pari a zero.

1571
01:12:16,620 --> 01:12:20,140
>> E noi non vogliamo sovrascrivere zucca
solo per questo, perché allora faremo

1572
01:12:20,140 --> 01:12:21,860
per scontato che la zucca era
mai inserito.

1573
01:12:21,860 --> 01:12:25,230
Se ci limitiamo a tenere una cosa in
posizione che sarebbe male.

1574
01:12:25,230 --> 01:12:28,590
Allora non ci sarebbe
possibilità di noi ha mai -

1575
01:12:28,590 --> 01:12:31,660
se abbiamo mai avuto un duplicato, poi abbiamo
sarebbe solo cancellare il nostro valore iniziale.

1576
01:12:31,660 --> 01:12:34,090
Ecco perché facciamo questo approccio.

1577
01:12:34,090 --> 01:12:36,580
O è per questo che abbiamo scelto - ma ancora una volta, abbiamo
ha scelto l'approccio concatenazioni separate,

1578
01:12:36,580 --> 01:12:39,670
che ci sono molti altri approcci
si può scegliere.

1579
01:12:39,670 --> 01:12:41,185
Questo risponde alla tua domanda?

1580
01:12:41,185 --> 01:12:41,660
>> OK.

1581
01:12:41,660 --> 01:12:42,910
Carlos.

1582
01:12:42,910 --> 01:12:46,130

1583
01:12:46,130 --> 01:12:47,720
Scansione lineare comporterebbe -

1584
01:12:47,720 --> 01:12:51,913
se abbiamo trovato una collisione a zero, abbiamo
apparirebbe nel punto successivo per vedere se

1585
01:12:51,913 --> 01:12:54,310
era aperto e messo lì.

1586
01:12:54,310 --> 01:12:57,320
E poi guardiamo nel prossimo sport e
vedere se era aperto e metterlo lì.

1587
01:12:57,320 --> 01:12:59,780
Così troviamo il successivo
luogo aperto e messo lì.

1588
01:12:59,780 --> 01:13:02,580

1589
01:13:02,580 --> 01:13:03,890
Tutte le altre domande?

1590
01:13:03,890 --> 01:13:05,370
Sì, Avi.

1591
01:13:05,370 --> 01:13:07,490
>> AUDIENCE: Come un follow-up a ciò,
cosa si intende per il prossimo posto?

1592
01:13:07,490 --> 01:13:10,250
Nella tabella hash o in una lista collegata.

1593
01:13:10,250 --> 01:13:12,100
>> JASON HIRSCHHORN: Per lineari
programmazione, liste collegate.

1594
01:13:12,100 --> 01:13:13,400
Il punto successivo sulla tabella hash.

1595
01:13:13,400 --> 01:13:13,820
>> AUDIENCE: OK.

1596
01:13:13,820 --> 01:13:17,570
Quindi la tabella di hash sarebbe
inizializzato alla dimensione -

1597
01:13:17,570 --> 01:13:19,560
come il numero di stringhe
che si stava inserendo?

1598
01:13:19,560 --> 01:13:22,170
>> JASON HIRSCHHORN: Lo faresti
voglio che sia davvero grande.

1599
01:13:22,170 --> 01:13:23,910
Sì.

1600
01:13:23,910 --> 01:13:27,900
Ecco una foto di quello che abbiamo
appena richiamato sulla scheda.

1601
01:13:27,900 --> 01:13:29,470
Ancora una volta, abbiamo una collisione proprio qui.

1602
01:13:29,470 --> 01:13:30,710
a 152.

1603
01:13:30,710 --> 01:13:33,570
E vedrete che abbiamo creato
una lista collegata fuori di esso.

1604
01:13:33,570 --> 01:13:38,200

1605
01:13:38,200 --> 01:13:41,850
Anche in questo caso, la tabella hash concatenazioni separate
approccio non è quello che si

1606
01:13:41,850 --> 01:13:45,590
prendere per impostare i problemi
sei, ma è uno che un sacco di

1607
01:13:45,590 --> 01:13:47,100
gli studenti tendono a prendere.

1608
01:13:47,100 --> 01:13:51,140
Quindi, su questa nota, parliamo brevemente
prima di testa fuori per il problema sei,

1609
01:13:51,140 --> 01:13:52,160
e poi io condividere una storia con te.

1610
01:13:52,160 --> 01:13:55,120
Abbiamo tre minuti.

1611
01:13:55,120 --> 01:13:55,750
>> Problema set di sei.

1612
01:13:55,750 --> 01:13:57,790
Avete quattro funzioni -

1613
01:13:57,790 --> 01:14:02,430
carico, controllare, le dimensioni e scarico.

1614
01:14:02,430 --> 01:14:03,380
Load -

1615
01:14:03,380 --> 01:14:07,120
bene, stiamo andando
sopra il carico solo ora.

1616
01:14:07,120 --> 01:14:09,330
Abbiamo disegnato il carico sul bordo.

1617
01:14:09,330 --> 01:14:13,230
E abbiamo anche iniziato la codifica di un sacco di
inserimento in una lista collegata.

1618
01:14:13,230 --> 01:14:18,020
Così carico non è molto più di
quello che abbiamo fatto appena.

1619
01:14:18,020 --> 01:14:21,070
>> Arrivo è una volta che avete
qualcosa caricato.

1620
01:14:21,070 --> 01:14:22,580
E 'lo stesso processo come questo.

1621
01:14:22,580 --> 01:14:26,845
Le stesse prime due parti in cui si passi
qualcosa nella funzione di hash

1622
01:14:26,845 --> 01:14:29,190
e ottenere il suo valore.

1623
01:14:29,190 --> 01:14:30,700
Ma ora non stiamo inserirla.

1624
01:14:30,700 --> 01:14:33,350
Ora stiamo cercando.

1625
01:14:33,350 --> 01:14:37,130
Ho scritto il codice di esempio per la ricerca
qualcosa in una lista collegata.

1626
01:14:37,130 --> 01:14:38,250
Vi incoraggio a praticare questo.

1627
01:14:38,250 --> 01:14:43,000
Ma intuitivamente trovare qualcosa sta
molto simile a inserire qualcosa.

1628
01:14:43,000 --> 01:14:46,540
Infatti, abbiamo disegnato un quadro di trovare
qualcosa in una lista collegata, spostando

1629
01:14:46,540 --> 01:14:48,910
attraverso finché si è giunti alla fine.

1630
01:14:48,910 --> 01:14:52,430
E se avete ottenuto alla fine e non poteva
lo trova, allora non c'è.

1631
01:14:52,430 --> 01:14:55,400
Ecco, questo è il check, in sostanza.

1632
01:14:55,400 --> 01:14:57,030
>> Avanti è la dimensione.

1633
01:14:57,030 --> 01:14:57,910
Saltiamo dimensioni.

1634
01:14:57,910 --> 01:15:00,040
Finalmente hai scarico.

1635
01:15:00,040 --> 01:15:02,890
Scaricamento è uno che non abbiamo disegnato
sul bordo o ancora codificate.

1636
01:15:02,890 --> 01:15:05,990
Ma vi incoraggio a provare la codifica è
nel nostro campione lista d'esempio.

1637
01:15:05,990 --> 01:15:11,440
Ma scarico intuitivamente
è simile a gratis -

1638
01:15:11,440 --> 01:15:14,010
o che voglio dire è simile a controllare.

1639
01:15:14,010 --> 01:15:17,350
Tranne che per ora ogni volta che si sta andando
attraverso, non stai semplicemente controllando

1640
01:15:17,350 --> 01:15:19,090
vedere se avete il vostro valore lì.

1641
01:15:19,090 --> 01:15:22,490
Ma stai prendendo quel nodo e
liberandola, essenzialmente.

1642
01:15:22,490 --> 01:15:23,610
Questo è quello che scarico si chiede di fare.

1643
01:15:23,610 --> 01:15:24,670
Tutto libero che hai malloced.

1644
01:15:24,670 --> 01:15:27,480
Quindi stai passando l'intera lista
nuovamente, passando attraverso l'intero hash

1645
01:15:27,480 --> 01:15:27,760
Tavolo di nuovo.

1646
01:15:27,760 --> 01:15:29,240
Questa volta non controlla
per vedere cosa c'è.

1647
01:15:29,240 --> 01:15:31,080
Basta liberare cosa c'è.

1648
01:15:31,080 --> 01:15:33,260
>> E infine le dimensioni.

1649
01:15:33,260 --> 01:15:34,350
Dimensione dovrebbe essere attuato.

1650
01:15:34,350 --> 01:15:35,590
Se non si implementa dimensioni -

1651
01:15:35,590 --> 01:15:36,250
Dirò come questo.

1652
01:15:36,250 --> 01:15:39,740
Se non si implementa dimensioni esattamente
una riga di codice compresa la

1653
01:15:39,740 --> 01:15:43,760
ritorno economico, si è
facendo formato errato.

1654
01:15:43,760 --> 01:15:47,170
Quindi assicuratevi dimensioni, per la progettazione completa
punti, si sta facendo esattamente quello

1655
01:15:47,170 --> 01:15:49,970
riga di codice, compreso
l'istruzione return.

1656
01:15:49,970 --> 01:15:52,450
>> E non le valigie ancora, Akchar.

1657
01:15:52,450 --> 01:15:53,700
Castoro Eager.

1658
01:15:53,700 --> 01:15:55,820

1659
01:15:55,820 --> 01:16:01,300
Volevo dire grazie ragazzi
per venire a sezione.

1660
01:16:01,300 --> 01:16:02,550
Avere un Happy Halloween.

1661
01:16:02,550 --> 01:16:05,300

1662
01:16:05,300 --> 01:16:05,960
Questo è il mio costume.

1663
01:16:05,960 --> 01:16:08,850
Sarò indossare questo il Giovedi
se ti vedo in orario di ufficio.

1664
01:16:08,850 --> 01:16:14,640
E se siete curiosi di sapere un po 'di più
come sfondo a questo costume, si sentono

1665
01:16:14,640 --> 01:16:19,135
libero di controllare 2011 sezione
per una storia sul perché io sono

1666
01:16:19,135 --> 01:16:20,900
indossare il costume da zucca.

1667
01:16:20,900 --> 01:16:23,680
Ed è una storia triste.

1668
01:16:23,680 --> 01:16:27,050
Quindi assicuratevi di avere
alcuni tessuti vicini.

1669
01:16:27,050 --> 01:16:28,680
Ma su questo, se avete qualche
domande che ti attaccano intorno

1670
01:16:28,680 --> 01:16:29,960
fuori dopo la sezione.

1671
01:16:29,960 --> 01:16:31,510
Buona fortuna per il problema definito sei.

1672
01:16:31,510 --> 01:16:33,540
E come sempre, se avete qualche
domande, fammi sapere.

1673
01:16:33,540 --> 01:16:35,584