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

2
00:00:08,250 --> 00:00:12,680
>> JASON Hirschhorn: Benvinguts a tots
a la Secció Set.

3
00:00:12,680 --> 00:00:15,040
Estem en la setena setmana del curs.

4
00:00:15,040 --> 00:00:18,440
I aquest proper dijous
és Halloween, així que estic

5
00:00:18,440 --> 00:00:21,420
vestit com una carbassa.

6
00:00:21,420 --> 00:00:23,460
Jo no podia ajupir-se i posar en
les meves sabates, així que és per això que estic

7
00:00:23,460 --> 00:00:25,660
només l'ús de mitjons.

8
00:00:25,660 --> 00:00:29,220
Així mateix, no porto res a sota
això, així que no puc llevar si és

9
00:00:29,220 --> 00:00:29,950
distreure a vostè.

10
00:00:29,950 --> 00:00:31,860
Em disculpo per endavant per això.

11
00:00:31,860 --> 00:00:33,170
No cal imaginar
Què està passant.

12
00:00:33,170 --> 00:00:34,240
Jo porto calçotets.

13
00:00:34,240 --> 00:00:36,170
Així que està tot bé.

14
00:00:36,170 --> 00:00:41,120
>> Tinc una història més llarga de per què estic
vestit com una carbassa, però jo vaig a

15
00:00:41,120 --> 00:00:45,110
guardar per més endavant en aquesta secció
perquè jo vull començar.

16
00:00:45,110 --> 00:00:47,720
Tenim un munt de coses interessants
per repassar aquesta setmana.

17
00:00:47,720 --> 00:00:51,810
La majoria d'ells es refereixen directament a aquest
conjunt de problemes de la setmana, les faltes d'ortografia.

18
00:00:51,810 --> 00:00:54,680
Anem a anar sobre lligat
llistes i taules hash

19
00:00:54,680 --> 00:00:57,160
per a tota la secció.

20
00:00:57,160 --> 00:01:02,490
Poso aquesta llista cada setmana, una llista de
recursos per a vostè per ajudar amb

21
00:01:02,490 --> 00:01:04,120
el material d'aquest curs.

22
00:01:04,120 --> 00:01:07,600
Si en una pèrdua o si busca alguna
obtenir més informació, fes un cop d'ull a un

23
00:01:07,600 --> 00:01:09,930
aquests recursos.

24
00:01:09,930 --> 00:01:14,530
>> Un cop més, és pset6 faltes d'ortografia,
conjunt de processadors d'aquesta setmana.

25
00:01:14,530 --> 00:01:17,690
I també t'anima, i jo
animar-vos, utilitzar algun altre

26
00:01:17,690 --> 00:01:20,320
recursos específicament per a aquest conjunt de processadors.

27
00:01:20,320 --> 00:01:23,390
En particular, els tres que he
enumerat a la pantalla -

28
00:01:23,390 --> 00:01:27,160
gdb, que hem estat familiaritzats amb
i estat utilitzant des de fa un temps, és

29
00:01:27,160 --> 00:01:29,270
serà de molta ajuda aquesta setmana.

30
00:01:29,270 --> 00:01:30,190
Així que vaig posar que fins aquí.

31
00:01:30,190 --> 00:01:32,910
Però cada vegada que es treballa amb C,
sempre s'ha d'utilitzar gdb per

32
00:01:32,910 --> 00:01:34,430
depurar els programes.

33
00:01:34,430 --> 00:01:36,660
Aquesta setmana també valgrind.

34
00:01:36,660 --> 00:01:38,535
Algú sap el que valgrind fa?

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

36
00:01:42,184 --> 00:01:43,890
>> AUDIÈNCIA: Comprova si hi ha fuites de memòria?

37
00:01:43,890 --> 00:01:45,950
>> JASON Hirschhorn: Valgrind
xecs per a les pèrdues de memòria.

38
00:01:45,950 --> 00:01:49,970
Així que si alguna cosa malloc en el seu
programa, estàs demanant memòria.

39
00:01:49,970 --> 00:01:52,920
Al final del seu programa, vostè té
per escriure lliure de tot el que has

40
00:01:52,920 --> 00:01:54,800
malloced per donar la memòria.

41
00:01:54,800 --> 00:01:58,420
Si no escrius lliure al final i
el seu programa arriba a una conclusió,

42
00:01:58,420 --> 00:02:00,000
tot automàticament
ser alliberat.

43
00:02:00,000 --> 00:02:02,340
I per als petits programes, que és
No és gran cosa.

44
00:02:02,340 --> 00:02:05,250
Però si vostè està escrivint un rodatge més llarg
programa que no es tanca,

45
00:02:05,250 --> 00:02:09,180
necessàriament, en un parell de minuts o un
parell de segons, a continuació, pèrdues de memòria

46
00:02:09,180 --> 00:02:10,710
pot esdevenir un gran negoci.

47
00:02:10,710 --> 00:02:14,940
>> Així que per pset6, l'expectativa és que
vostè tindrà pèrdues de memòria zero amb

48
00:02:14,940 --> 00:02:15,910
seu programa.

49
00:02:15,910 --> 00:02:18,690
Per comprovar si hi ha fuites de memòria, valgrind executar
i et vaig a donar algunes bones

50
00:02:18,690 --> 00:02:21,190
sortida que li permet saber si
o no tot era gratis.

51
00:02:21,190 --> 00:02:23,940
Practicarem amb ell més endavant
avui, amb sort.

52
00:02:23,940 --> 00:02:25,790
>> Finalment, la comanda diff.

53
00:02:25,790 --> 00:02:28,900
Ha utilitzat alguna cosa similar a ella
en pset5 amb l'eina cop d'ull.

54
00:02:28,900 --> 00:02:30,780
Li ha permès observar l'interior.

55
00:02:30,780 --> 00:02:33,400
També vas usar diff, també, per
el problema estableix especificacions.

56
00:02:33,400 --> 00:02:35,950
Però en que permet
comparar dos arxius.

57
00:02:35,950 --> 00:02:39,180
Es podria comparar l'arxiu de mapa de bits i
info encapçalats d'una solució personal i

58
00:02:39,180 --> 00:02:42,200
la seva solució en pset5 si
opta per utilitzar-lo.

59
00:02:42,200 --> 00:02:44,030
Dif li permetrà
fer això, també.

60
00:02:44,030 --> 00:02:48,620
Pot comparar la resposta correcta per
El problema d'aquesta setmana estableix en la seva resposta

61
00:02:48,620 --> 00:02:52,210
i veure si s'alineï o veure
on són els errors.

62
00:02:52,210 --> 00:02:55,870
>> Així que aquests són tres bones eines que
vostè ha d'utilitzar per a aquesta setmana, i

63
00:02:55,870 --> 00:02:58,130
Definitivament revisar el seu programa de
amb aquestes tres eines

64
00:02:58,130 --> 00:03:00,520
abans de donar volta polz

65
00:03:00,520 --> 00:03:04,650
Un cop més, com ja he esmentat totes les setmanes,
si té alguna reacció per a mi - tant

66
00:03:04,650 --> 00:03:06,470
positiva i constructiva -

67
00:03:06,470 --> 00:03:09,930
no dubti en dirigir-se a la pàgina web
a la part inferior d'aquesta diapositiva

68
00:03:09,930 --> 00:03:11,270
i l'entrada allà.

69
00:03:11,270 --> 00:03:13,440
Realment estima qualsevol
i tots els comentaris.

70
00:03:13,440 --> 00:03:17,360
I si em dones les coses específiques que
Que puc fer per millorar o que sóc

71
00:03:17,360 --> 00:03:21,350
fent així que m'agradaria
Continuo, em prenc molt a pit i

72
00:03:21,350 --> 00:03:24,040
realment s'esforcen per escoltar
per a la seva regeneració.

73
00:03:24,040 --> 00:03:27,720
No puc prometre que faré
tot, però, com portar una

74
00:03:27,720 --> 00:03:30,700
carbassa disfressa cada setmana.

75
00:03:30,700 --> 00:03:34,020
>> Així que anem a passar la major part de
secció, com ja he dit, parlant de

76
00:03:34,020 --> 00:03:37,240
llistes enllaçades i taules hash, que
serà directament aplicable a la

77
00:03:37,240 --> 00:03:38,780
problema establert aquesta setmana.

78
00:03:38,780 --> 00:03:42,580
Les llistes enllaçades repassarem relativament
ràpidament, perquè hem passat una mica just

79
00:03:42,580 --> 00:03:44,930
de temps d'anar-hi a la secció.

80
00:03:44,930 --> 00:03:48,680
I així anem a arribar directament a la
problemes de codificació per a llistes enllaçades.

81
00:03:48,680 --> 00:03:52,740
I després, al final anem a parlar de
taules hash i com s'apliquen a aquest

82
00:03:52,740 --> 00:03:55,280
Problema de la setmana.

83
00:03:55,280 --> 00:03:57,560
>> Vostè ha vist aquest codi abans.

84
00:03:57,560 --> 00:04:02,730
Aquesta és una estructura, i que està definint
alguna cosa nova anomenat node.

85
00:04:02,730 --> 00:04:10,660
I dins d'un node no és un enter
aquí i allà és un punter a

86
00:04:10,660 --> 00:04:11,830
un altre node.

87
00:04:11,830 --> 00:04:12,790
Hem vist això abans.

88
00:04:12,790 --> 00:04:14,830
Això ha estat pujant de
un parell de setmanes ara.

89
00:04:14,830 --> 00:04:18,680
Combina els punters, que hem estat
treballar amb, i estructures, que permeten

90
00:04:18,680 --> 00:04:22,079
ens permet combinar dos diferents
coses en un sol tipus de dades.

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

92
00:04:24,830 --> 00:04:26,490
>> Hi ha molt a fer a la pantalla.

93
00:04:26,490 --> 00:04:30,220
Però tot això ha de ser relativament
familiaritzat amb vostè.

94
00:04:30,220 --> 00:04:33,810
A la primera línia, que
declarar un nou node.

95
00:04:33,810 --> 00:04:41,650
I després, dins d'aquest nou node, em vaig posar
el nombre sencer en aquest node a un.

96
00:04:41,650 --> 00:04:44,950
Veiem en la següent línia que estic fent un
printf comandament, però he atenuats

97
00:04:44,950 --> 00:04:48,080
la comanda printf perquè la veritat
part important és aquesta línia aquí -

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

99
00:04:50,020 --> 00:04:51,270
Què significa el punt?

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

101
00:04:53,810 --> 00:04:57,240
>> AUDIÈNCIA: Aneu al node i
avaluar el valor de n per a això.

102
00:04:57,240 --> 00:04:58,370
>> JASON Hirschhorn: Això és
exactament correcte.

103
00:04:58,370 --> 00:05:03,300
Dot significa accedir a la part n
d'aquest nou node.

104
00:05:03,300 --> 00:05:05,690
Aquesta línia següent fa què?

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
>> AUDIÈNCIA: Es crea un altre node
que s'apunti al nou node.

108
00:05:21,910 --> 00:05:24,870
>> JASON Hirschhorn: Així que no fa
crear un nou node.

109
00:05:24,870 --> 00:05:26,120
Es crea un què?

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

111
00:05:28,300 --> 00:05:29,300
>> AUDIÈNCIA: Un punter.

112
00:05:29,300 --> 00:05:33,460
>> JASON Hirschhorn: Un punter a un node,
com dictamina aquest node * aquí.

113
00:05:33,460 --> 00:05:34,800
Per tant, crea un punter a un node.

114
00:05:34,800 --> 00:05:37,490
I què node es ho apunta
a, Michael?

115
00:05:37,490 --> 00:05:38,440
>> AUDIÈNCIA: Nou node?

116
00:05:38,440 --> 00:05:39,240
>> JASON Hirschhorn: Nou node.

117
00:05:39,240 --> 00:05:43,020
I està apuntant allà perquè hem
atès que la direcció del nou node.

118
00:05:43,020 --> 00:05:45,820
I ara en aquesta línia veiem
dues maneres diferents de

119
00:05:45,820 --> 00:05:46,910
expressar la mateixa cosa.

120
00:05:46,910 --> 00:05:49,650
I jo volia assenyalar com aquests
dues coses són el mateix.

121
00:05:49,650 --> 00:05:54,740
A la primera línia, eliminar la referència
el punter.

122
00:05:54,740 --> 00:05:55,830
Així que anem al node.

123
00:05:55,830 --> 00:05:56,830
Això és el que significa aquest estel.

124
00:05:56,830 --> 00:05:57,930
Hem vist que abans amb els punters.

125
00:05:57,930 --> 00:05:59,280
Anar a aquest node.

126
00:05:59,280 --> 00:06:00,370
Això està en parèntesis.

127
00:06:00,370 --> 00:06:04,610
I a continuació, accedir a través de l'operador de punt
l'element n d'aquest node.

128
00:06:04,610 --> 00:06:08,430
>> Així que això prendre la sintaxi
vam veure aquí i ara

129
00:06:08,430 --> 00:06:09,670
usar-la amb un punter.

130
00:06:09,670 --> 00:06:13,730
Per descomptat, es posa una mica ocupat si
vostè està escrivint aquests parèntesi -

131
00:06:13,730 --> 00:06:14,940
aquesta estrella i aquest punt.

132
00:06:14,940 --> 00:06:16,220
Es posa una mica ocupat.

133
00:06:16,220 --> 00:06:18,500
Així que tenim una mica de sucre sintàctica.

134
00:06:18,500 --> 00:06:19,920
I aquesta línia aquí -

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
Que fa exactament el mateix.

138
00:06:28,000 --> 00:06:30,840
Així que aquestes dues línies de codi són
equivalent i ho farà

139
00:06:30,840 --> 00:06:31,650
exactament el mateix.

140
00:06:31,650 --> 00:06:34,210
>> Però jo volia assenyalar els abans
d'anar més lluny perquè vostè entengui

141
00:06:34,210 --> 00:06:39,000
que realment aquesta cosa aquí és
només el sucre sintàctica per a eliminació de referències

142
00:06:39,000 --> 00:06:44,200
el punter i després anar a
la part n d'aquesta estructura.

143
00:06:44,200 --> 00:06:45,525
Una pregunta sobre aquesta diapositiva?

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

145
00:06:53,020 --> 00:06:54,390
D'acord.

146
00:06:54,390 --> 00:06:58,510
>> Així que anem a anar a través d'un parell
de les operacions que es poden fer en

147
00:06:58,510 --> 00:06:59,730
llistes enllaçades.

148
00:06:59,730 --> 00:07:05,770
Una llista enllaçada, el record, és una sèrie de
nodes que apunten l'un a l'altre.

149
00:07:05,770 --> 00:07:12,470
I en general, vam començar amb un punter
anomenat el cap, generalment, que apunta

150
00:07:12,470 --> 00:07:14,040
el primer a la llista.

151
00:07:14,040 --> 00:07:18,900
Així que a la primera línia aquí,
tenir primer l'original L.

152
00:07:18,900 --> 00:07:21,370
Així que aquesta cosa que es pugui imaginar - això
text aquí es pot pensar en com

153
00:07:21,370 --> 00:07:23,560
només el punter hem emmagatzemat
en algun lloc que els punts

154
00:07:23,560 --> 00:07:24,670
per al primer element.

155
00:07:24,670 --> 00:07:27,500
I en aquesta llista enllaçada
tenim quatre nodes.

156
00:07:27,500 --> 00:07:29,530
Cada node és una caixa gran.

157
00:07:29,530 --> 00:07:33,430
La caixa més gran dins de la gran
caixa és la part sencera.

158
00:07:33,430 --> 00:07:37,400
I després tenim una part punter.

159
00:07:37,400 --> 00:07:39,630
>> Aquestes caixes no estan dibuixats a
escala a causa del gran que és

160
00:07:39,630 --> 00:07:42,320
un enter en bytes?

161
00:07:42,320 --> 00:07:43,290
Què tan gran ara?

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

163
00:07:43,710 --> 00:07:45,470
I què tan gran és un punter?

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

165
00:07:45,940 --> 00:07:48,180
Així que en realitat, si haguéssim de dibuixar
això és a escala dues caixes

166
00:07:48,180 --> 00:07:49,690
seria la mateixa mida.

167
00:07:49,690 --> 00:07:52,870
En aquest cas, volem inserir
alguna cosa a la llista enllaçada.

168
00:07:52,870 --> 00:07:57,190
Així que vostè pot veure aquí baix estem inserint
05:00 Travessem a través de la

169
00:07:57,190 --> 00:08:01,310
llista enllaçada, on trobarà 05:00
va, i després inserir-lo.

170
00:08:01,310 --> 00:08:03,560
>> Anem a trencar això i van
una mica més lentament.

171
00:08:03,560 --> 00:08:05,510
Vaig a assenyalar a la junta.

172
00:08:05,510 --> 00:08:09,930
Així que tenim el nostre node cinc que
hem creat en mallocs.

173
00:08:09,930 --> 00:08:11,190
Per què s'està rient de tot el món?

174
00:08:11,190 --> 00:08:12,130
És broma.

175
00:08:12,130 --> 00:08:13,310
D'acord.

176
00:08:13,310 --> 00:08:14,820
Així que hem malloced 05:00.

177
00:08:14,820 --> 00:08:16,310
Hem creat aquest node
en un altre lloc.

178
00:08:16,310 --> 00:08:17,740
Nosaltres ho tenim llest per anar.

179
00:08:17,740 --> 00:08:20,130
Comencem a la part frontal de
llistat amb dos.

180
00:08:20,130 --> 00:08:22,380
I volem inserir
d'una manera ordenada.

181
00:08:22,380 --> 00:08:27,550
>> Així que si veiem a dos i volem posar
en cinc, què fem quan veiem

182
00:08:27,550 --> 00:08:28,800
una mica menys que nosaltres?

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

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

185
00:08:33,520 --> 00:08:36,750
Volem inserir cinc en aquest
llista enllaçada, mantenint ordenat.

186
00:08:36,750 --> 00:08:37,520
Veiem el número dos.

187
00:08:37,520 --> 00:08:38,769
Llavors, què fem?

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

189
00:08:39,179 --> 00:08:40,679
>> AUDIÈNCIA: Truqui al punter
al següent node.

190
00:08:40,679 --> 00:08:42,530
>> JASON Hirschhorn: I per què
ens anem a la següent?

191
00:08:42,530 --> 00:08:45,970
>> AUDIÈNCIA: Perquè és la
següent node de la llista.

192
00:08:45,970 --> 00:08:48,310
I només se sap que una altra ubicació.

193
00:08:48,310 --> 00:08:50,410
>> JASON Hirschhorn: I cinc és més gran
de dos, en particular.

194
00:08:50,410 --> 00:08:51,600
Perquè volem mantenir ordenada.

195
00:08:51,600 --> 00:08:52,730
Així 05:00 és més gran que dos.

196
00:08:52,730 --> 00:08:54,460
Així que passem a la següent.

197
00:08:54,460 --> 00:08:55,240
I ara arribem a quatre.

198
00:08:55,240 --> 00:08:56,490
I què passa quan arribem a quatre?

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

200
00:08:58,920 --> 00:09:00,310
>> El cinc és més gran que quatre.

201
00:09:00,310 --> 00:09:01,460
Així que seguim endavant.

202
00:09:01,460 --> 00:09:03,110
I ara estem a les sis.

203
00:09:03,110 --> 00:09:04,360
I què és el que veiem a les sis?

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

205
00:09:08,672 --> 00:09:09,608
Sí, Carles?

206
00:09:09,608 --> 00:09:10,544
>> AUDIÈNCIA: Six és més gran que cinc.

207
00:09:10,544 --> 00:09:11,480
>> JASON Hirschhorn: Six és
major que cinc.

208
00:09:11,480 --> 00:09:13,660
Així que aquí és on volem
per inserir 05:00.

209
00:09:13,660 --> 00:09:17,320
No obstant això, tingueu en compte que si ens
només tenen un punter aquí -

210
00:09:17,320 --> 00:09:19,840
aquest és el nostre punter extra que és
travessant per la llista.

211
00:09:19,840 --> 00:09:21,860
I estem apuntant a sis.

212
00:09:21,860 --> 00:09:25,010
Hem perdut la pista del
ve abans de les sis.

213
00:09:25,010 --> 00:09:29,130
Així que si volem inserir alguna cosa en
aquesta llista mantenir ordenada, que

214
00:09:29,130 --> 00:09:31,630
probablement necessitarà el nombre de punters?

215
00:09:31,630 --> 00:09:32,280
>> AUDIÈNCIA: Dos.

216
00:09:32,280 --> 00:09:32,920
>> JASON Hirschhorn: Dos.

217
00:09:32,920 --> 00:09:35,720
Un per realitzar un seguiment del corrent
un i un per realitzar un seguiment de

218
00:09:35,720 --> 00:09:37,050
l'anterior.

219
00:09:37,050 --> 00:09:38,450
Aquesta és només una llista vinculada individualment.

220
00:09:38,450 --> 00:09:39,670
Només va en una direcció.

221
00:09:39,670 --> 00:09:43,220
Si tinguéssim una llista doblement enllaçada, on
tot apuntava a la cosa

222
00:09:43,220 --> 00:09:46,240
després d'ella i la cosa abans que, a continuació,
no tindríem necessitat de fer això.

223
00:09:46,240 --> 00:09:49,350
Però en aquest cas no volem perdre
un seguiment del que hi va haver abans de nosaltres en cas de

224
00:09:49,350 --> 00:09:53,350
hem d'inserir 05:00 en algun lloc
en el medi.

225
00:09:53,350 --> 00:09:55,610
Diguem que Inserim nou.

226
00:09:55,610 --> 00:09:57,260
Què passaria quan
arribem a les vuit?

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

228
00:10:01,860 --> 00:10:04,880
>> AUDIÈNCIA: Vostè hauria de
aconseguir que el punt nul.

229
00:10:04,880 --> 00:10:07,820
En lloc de tenir punt nul hauries
per afegir un element i després tenir

230
00:10:07,820 --> 00:10:09,216
que apunti a nou.

231
00:10:09,216 --> 00:10:09,700
>> JASON Hirschhorn: Exactament.

232
00:10:09,700 --> 00:10:10,600
Així que tenim vuit.

233
00:10:10,600 --> 00:10:13,140
Arribem al final de la llista a causa de
això apunta null.

234
00:10:13,140 --> 00:10:16,330
I ara, en lloc d'haver de apunti a
nul tenim que apunti al nostre nou node.

235
00:10:16,330 --> 00:10:19,870
I posem el punter a
nostre nou node a null.

236
00:10:19,870 --> 00:10:21,445
Algú té alguna pregunta
sobre la inserció?

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

238
00:10:25,620 --> 00:10:28,100
Què passa si no es preocupen per
mantenir la llista ordenada?

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

240
00:10:31,701 --> 00:10:34,350
>> AUDIÈNCIA: Estic it al
principi o al final.

241
00:10:34,350 --> 00:10:35,510
>> JASON Hirschhorn: enganxeu en
al principi o al final.

242
00:10:35,510 --> 00:10:37,276
Quin hem de fer?

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

244
00:10:38,770 --> 00:10:41,020
Per què al final?

245
00:10:41,020 --> 00:10:43,250
>> AUDIÈNCIA: Com que el principi
ja està ple.

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

247
00:10:43,575 --> 00:10:44,360
El començament ja està ple.

248
00:10:44,360 --> 00:10:46,090
Qui vol argumentar en contra de Bobby.

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

250
00:10:47,290 --> 00:10:48,910
>> AUDIÈNCIA: Bé, vostè probablement voldrà
enganxar-lo al principi perquè

251
00:10:48,910 --> 00:10:50,140
en cas contrari si vostè ho posa en
final que hauria de

252
00:10:50,140 --> 00:10:51,835
recórrer tota la llista.

253
00:10:51,835 --> 00:10:52,990
>> JASON Hirschhorn: Exactament.

254
00:10:52,990 --> 00:10:57,970
Així que si estem pensant en el temps d'execució, la
temps d'execució de la inserció a l'extrem

255
00:10:57,970 --> 00:11:00,110
seria n, la mida d'aquest.

256
00:11:00,110 --> 00:11:03,080
Quin és el temps d'execució d'O d'inserció
pel principi?

257
00:11:03,080 --> 00:11:04,170
Constant de temps.

258
00:11:04,170 --> 00:11:07,075
Així que si vostè no es preocupen per mantenir
cosa ordenada, molt millor que només

259
00:11:07,075 --> 00:11:08,420
inserir al principi d'aquesta llista.

260
00:11:08,420 --> 00:11:10,320
I això es pot fer en temps constant.

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

262
00:11:13,900 --> 00:11:14,690
>> D'acord.

263
00:11:14,690 --> 00:11:18,870
Operació següent es va trobar que altres -
hem redactar l'cerca.

264
00:11:18,870 --> 00:11:22,470
Però anem a mirar a través de la
llista enllaçada per algun objecte.

265
00:11:22,470 --> 00:11:26,000
Vostès han vist el codi de
buscar abans en la conferència.

266
00:11:26,000 --> 00:11:29,490
Però quin tipus de només vam fer amb
inserir, o almenys la inserció

267
00:11:29,490 --> 00:11:30,580
alguna cosa ordenada.

268
00:11:30,580 --> 00:11:36,350
Et veus a través, passant pel node node,
fins que trobi el nombre que vostè està

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

270
00:11:37,780 --> 00:11:39,670
Què passa si vostè arriba a
al final de la llista?

271
00:11:39,670 --> 00:11:43,020
Diguem que jo estic buscant a les nou i em
arribar al final de la llista.

272
00:11:43,020 --> 00:11:44,270
Què fem?

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

274
00:11:47,147 --> 00:11:48,110
>> AUDIÈNCIA: Tornar fals?

275
00:11:48,110 --> 00:11:48,690
>> JASON Hirschhorn: Torna fals.

276
00:11:48,690 --> 00:11:49,960
No ens trobarà.

277
00:11:49,960 --> 00:11:52,010
Si arriba al final de la llista i
que no va trobar el número al qual està

278
00:11:52,010 --> 00:11:54,170
buscant, no hi és.

279
00:11:54,170 --> 00:11:55,420
Una pregunta sobre trobar?

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

281
00:11:59,530 --> 00:12:04,615
Si es tractava d'una llista ordenada, el que faria
ser diferent per a la nostra recerca?

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

283
00:12:07,370 --> 00:12:08,103
Sí

284
00:12:08,103 --> 00:12:10,600
>> AUDIÈNCIA: Es trobaria el primer valor
és major que el

285
00:12:10,600 --> 00:12:12,390
vostè està buscant i
a continuació, tornar false.

286
00:12:12,390 --> 00:12:13,190
>> JASON Hirschhorn: Exactament.

287
00:12:13,190 --> 00:12:17,310
Així que si es tracta d'una llista ordenada, si arribem a
cosa que és més gran que el

288
00:12:17,310 --> 00:12:20,180
que estem buscant, nosaltres no necessitem
seguir endavant fins al final de la llista.

289
00:12:20,180 --> 00:12:24,060
Podem en aquest punt return false
perquè no trobarem.

290
00:12:24,060 --> 00:12:27,340
La pregunta és ara, hem parlat de
mantenir llistes enllaçades ordenats,

291
00:12:27,340 --> 00:12:28,180
mantenint sense classificar.

292
00:12:28,180 --> 00:12:30,050
Això serà una cosa que et
probablement va a haver de pensar en

293
00:12:30,050 --> 00:12:34,240
quan un problema de codificació establert cinc si
triar una taula hash amb separada

294
00:12:34,240 --> 00:12:36,360
enfocament d'encadenament, que
parlarem més tard.

295
00:12:36,360 --> 00:12:41,400
>> Però val la pena mantenir la llista
ordenada i després ser capaç de tenir potser

296
00:12:41,400 --> 00:12:42,310
Recerques més ràpides?

297
00:12:42,310 --> 00:12:47,220
O és millor per inserir ràpidament
alguna cosa en temps d'execució constant, però després

298
00:12:47,220 --> 00:12:48,430
tenir més temps buscant?

299
00:12:48,430 --> 00:12:52,250
Això és un compromís just aquí que
arribar a decidir què és el més apropiat

300
00:12:52,250 --> 00:12:53,590
per al seu problema específic.

301
00:12:53,590 --> 00:12:56,680
I no és necessàriament una
resposta tota la raó.

302
00:12:56,680 --> 00:12:59,520
Però sens dubte és una decisió que vostè obté
de fer, i probablement bo per defensar

303
00:12:59,520 --> 00:13:05,270
que en, diguem, un comentari o dos per què
que va triar una sobre l'altra.

304
00:13:05,270 --> 00:13:06,490
>> Finalment, l'eliminació.

305
00:13:06,490 --> 00:13:08,100
Hem vist esborrar.

306
00:13:08,100 --> 00:13:09,180
És similar a la cerca.

307
00:13:09,180 --> 00:13:11,020
Busquem l'element.

308
00:13:11,020 --> 00:13:12,390
Diguem que estem tractant d'eliminar 06:00.

309
00:13:12,390 --> 00:13:14,450
Així ens trobem amb sis aquí.

310
00:13:14,450 --> 00:13:18,860
El que hem de assegurar-nos que
fer és que tot el que està apuntant a

311
00:13:18,860 --> 00:13:21,220
06:00 - com veiem en el pas
2 aquí baix -

312
00:13:21,220 --> 00:13:26,500
el que sigui que apunta a sis necessitats a
saltar 06:00 ara i canviar per

313
00:13:26,500 --> 00:13:28,160
qualsevol que sigui sis està apuntant.

314
00:13:28,160 --> 00:13:31,410
No volem deixar orfe vegada la resta de
llistat per l'oblit per establir que

315
00:13:31,410 --> 00:13:32,960
punter anterior.

316
00:13:32,960 --> 00:13:35,960
I a continuació, de vegades, depenent
en el programa, ells només

317
00:13:35,960 --> 00:13:37,380
eliminar aquest node complet.

318
00:13:37,380 --> 00:13:40,135
De vegades vostè voldrà tornar
el valor que està en aquest node.

319
00:13:40,135 --> 00:13:42,490
Així com la supressió de les obres.

320
00:13:42,490 --> 00:13:44,610
Teniu alguna pregunta respecte eliminar?

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

322
00:13:51,280 --> 00:13:53,850
>> AUDIÈNCIA: Així que si vostè va a esborrar
ell, seria simplement utilitzar gratis perquè

323
00:13:53,850 --> 00:13:55,655
presumiblement es malloced?

324
00:13:55,655 --> 00:13:57,976
>> JASON Hirschhorn: Per alliberar
cosa que és exactament correcte i vostè

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

326
00:13:58,540 --> 00:14:00,410
Diguem que volíem tornar a aquest valor.

327
00:14:00,410 --> 00:14:04,010
Podríem tornar sis i després lliure
aquest node i connexió de trucades en ell.

328
00:14:04,010 --> 00:14:06,180
O és probable que anomenaríem lliure primer
i després tornar 6.

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

330
00:14:11,210 --> 00:14:11,580
>> D'acord.

331
00:14:11,580 --> 00:14:14,010
Així que anem a passar a la pràctica de codificació.

332
00:14:14,010 --> 00:14:16,090
Anem a codificar tres funcions.

333
00:14:16,090 --> 00:14:18,260
La primera es diu insert_node.

334
00:14:18,260 --> 00:14:22,170
Així que tens el codi que et vaig enviar, i
si estàs veient això més endavant

335
00:14:22,170 --> 00:14:28,020
es pot accedir al codi en linked.c
en el lloc web CS50.

336
00:14:28,020 --> 00:14:30,880
Però en linked.c, hi ha una mica de
codi esquelet que ja està

337
00:14:30,880 --> 00:14:32,280
ha escrit per a vostè.

338
00:14:32,280 --> 00:14:34,560
I després hi ha un parell de funcions
que necessita per escriure.

339
00:14:34,560 --> 00:14:36,380
>> En primer lloc anem a
escriure insert_node.

340
00:14:36,380 --> 00:14:39,800
I què fa insert_node
és a dir insereix un sencer.

341
00:14:39,800 --> 00:14:42,440
I vostè està donant el nombre enter
en una llista enllaçada.

342
00:14:42,440 --> 00:14:45,470
I, en particular, cal
per mantenir la llista ordenada

343
00:14:45,470 --> 00:14:47,650
des del més petit al més gran.

344
00:14:47,650 --> 00:14:51,360
A més, no vol
inseriu els duplicats.

345
00:14:51,360 --> 00:14:54,600
Finalment, com es pot veure insert_node
retorna un bool.

346
00:14:54,600 --> 00:14:57,140
Així que se suposa que has de saber l'usuari
si o no l'insert era

347
00:14:57,140 --> 00:15:00,800
èxit retornant vertader o fals.

348
00:15:00,800 --> 00:15:02,580
Al final d'aquest programa -

349
00:15:02,580 --> 00:15:05,750
i per aquesta etapa no cal
de preocupar per l'alliberament de qualsevol cosa.

350
00:15:05,750 --> 00:15:11,790
Així que tot el que estem fent és prenent un sencer
i inserint-lo en una llista.

351
00:15:11,790 --> 00:15:13,890
>> Això és el que t'estic demanant que facis ara.

352
00:15:13,890 --> 00:15:17,620
Un cop més, al linked.c, que
tots tenen, és el codi d'esquelet.

353
00:15:17,620 --> 00:15:20,980
I cal veure cap al fons
la declaració de la funció de la mostra.

354
00:15:20,980 --> 00:15:27,390
Abans, però, d'entrar a la codificació que
en C, jo us animo a anar

355
00:15:27,390 --> 00:15:29,330
a través dels passos que hem estat
la pràctica de cada setmana.

356
00:15:29,330 --> 00:15:31,100
Nosaltres ja hem passat per
una foto d'això.

357
00:15:31,100 --> 00:15:33,380
Així que vostè ha de tenir algun coneixement
de com funciona això.

358
00:15:33,380 --> 00:15:36,590
Però m'animo a escriure
alguns pseudocodi abans de submergir polz

359
00:15:36,590 --> 00:15:38,640
I anem a repassar
pseudocodi com un grup.

360
00:15:38,640 --> 00:15:41,470
I una vegada que has escrit el teu
pseudocodi, i un cop hem escrit la nostra

361
00:15:41,470 --> 00:15:45,850
pseudocodi com a grup, pot
entrar a la codificació en C.

362
00:15:45,850 --> 00:15:49,980
>> Com un mà a mà, la funció insert_node
és probablement el més difícil de

363
00:15:49,980 --> 00:15:53,550
els tres que anem a escriure perquè
afegit algunes limitacions al

364
00:15:53,550 --> 00:15:57,190
la seva programació, en particular, que
no vas a inserir qualsevol

365
00:15:57,190 --> 00:15:59,880
duplicats i que la llista
ha de romandre ordenat.

366
00:15:59,880 --> 00:16:02,660
Així que aquest és un programa no trivial
que vostè necessita per codificar.

367
00:16:02,660 --> 00:16:06,470
I per què no et portes 06:55
minuts, per simplement treballar en el

368
00:16:06,470 --> 00:16:07,640
pseudocodi i el codi.

369
00:16:07,640 --> 00:16:09,460
I després anem a començar
anar com un grup.

370
00:16:09,460 --> 00:16:11,680
Un cop més, si vostè té alguna pregunta només
aixecar la mà i vaig a entrar en raó.

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
>> Nosaltres també, en general fem aquests -

375
00:18:30,120 --> 00:18:32,070
o jo no et dic explícitament
pot treballar amb la gent.

376
00:18:32,070 --> 00:18:36,500
Però, òbviament, jo us animo,
si té preguntes, demanar al

377
00:18:36,500 --> 00:18:39,840
veí assegut al teu costat
o fins i tot treballar amb algú

378
00:18:39,840 --> 00:18:40,510
més si vols.

379
00:18:40,510 --> 00:18:42,600
Aquest no ha de ser un individu
activitat silenciosa.

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

381
00:20:11,770 --> 00:20:16,330
>> Anem a començar amb l'escriptura d'alguns
pseudocodi al tauler.

382
00:20:16,330 --> 00:20:19,395
Qui em pot donar la primera línia de
pseudocodi per a aquest programa?

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

384
00:20:22,240 --> 00:20:23,640
Per a aquesta funció, en lloc -
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
>> AUDIÈNCIA: Així que el primer que vaig fer va ser
crear un nou punter al node i jo

388
00:20:36,560 --> 00:20:41,320
inicialitza el que apunta a la mateixa
cosa que la llista està assenyalant.

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

390
00:20:41,550 --> 00:20:45,190
Així que crearà un nou punter
a la llista, no per al node.

391
00:20:45,190 --> 00:20:45,420
>> AUDIÈNCIA: així.

392
00:20:45,420 --> 00:20:46,150
Sí

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

394
00:20:46,540 --> 00:20:48,221
I llavors, què és el que volem fer?

395
00:20:48,221 --> 00:20:49,163
Què hi ha després d'això?

396
00:20:49,163 --> 00:20:50,105
Què passa amb el node?

397
00:20:50,105 --> 00:20:51,050
No tenim un node.

398
00:20:51,050 --> 00:20:52,300
Només tenim un valor.

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

400
00:20:55,918 --> 00:20:58,890
Si volem inserir un node, el que fa que
necessita fer primer abans de poder tan sols

401
00:20:58,890 --> 00:20:59,980
pensar inserir?

402
00:20:59,980 --> 00:21:00,820
>> AUDIÈNCIA: Oh, ho sento.

403
00:21:00,820 --> 00:21:02,160
hem de malloc espai per a un node.

404
00:21:02,160 --> 00:21:02,455
>> JASON Hirschhorn: Excel · lent.

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

406
00:21:03,210 --> 00:21:04,628
D'acord.

407
00:21:04,628 --> 00:21:06,065
No es pot arribar tan alt.

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

409
00:21:08,939 --> 00:21:09,897
D'acord.

410
00:21:09,897 --> 00:21:13,236
Anem a anar cap avall, i després
estem usant dues columnes.

411
00:21:13,236 --> 00:21:13,732
No puc anar a que -

412
00:21:13,732 --> 00:21:14,982
D'acord.

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

414
00:21:23,660 --> 00:21:25,130
Crear un nou node.

415
00:21:25,130 --> 00:21:29,380
Podeu crear un altre punter a la llista
o simplement pot utilitzar la llista, tal com existeix.

416
00:21:29,380 --> 00:21:30,720
Segur que no necessita fer això.

417
00:21:30,720 --> 00:21:31,750
>> Així que vam crear un nou node.

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

419
00:21:32,010 --> 00:21:32,840
Això és el que fem en primer lloc.

420
00:21:32,840 --> 00:21:34,870
Què segueix?

421
00:21:34,870 --> 00:21:35,080
>> AUDIÈNCIA: Esperi.

422
00:21:35,080 --> 00:21:38,330
¿Cal crear un nou node ara o
hem d'esperar per assegurar-se que

423
00:21:38,330 --> 00:21:42,260
no hi ha duplicats del node
en la llista abans que ens ho creguem?

424
00:21:42,260 --> 00:21:43,100
>> JASON Hirschhorn: Bona pregunta.

425
00:21:43,100 --> 00:21:47,770
Anem a sostenir que per més endavant perquè el
major part del temps estarem creant

426
00:21:47,770 --> 00:21:48,220
un nou node.

427
00:21:48,220 --> 00:21:49,110
Així que seguirem això aquí.

428
00:21:49,110 --> 00:21:51,006
Però aquesta és una bona pregunta.

429
00:21:51,006 --> 00:21:53,250
Si creem i ens trobem
un duplicat, el que ha

430
00:21:53,250 --> 00:21:54,490
que fem abans de tornar?

431
00:21:54,490 --> 00:21:55,190
>> AUDIÈNCIA: alliberar-lo.

432
00:21:55,190 --> 00:21:55,470
>> JASON Hirschhorn: Si.

433
00:21:55,470 --> 00:21:56,500
Probablement alliberar-lo.

434
00:21:56,500 --> 00:21:56,760
D'acord.

435
00:21:56,760 --> 00:21:59,850
Què fem després que
crear un nou node?

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

437
00:22:02,260 --> 00:22:04,780
>> AUDIÈNCIA: Posem la
nombre en el node?

438
00:22:04,780 --> 00:22:05,140
>> JASON Hirschhorn: Exactament.

439
00:22:05,140 --> 00:22:07,190
Posem el nombre - que malloc espai.

440
00:22:07,190 --> 00:22:08,160
Vaig a deixar que
tot en una sola línia.

441
00:22:08,160 --> 00:22:08,720
Però tens raó.

442
00:22:08,720 --> 00:22:10,305
Ens malloc espai, i després
posem el nombre polz

443
00:22:10,305 --> 00:22:12,585
Fins i tot podem establir el punter
part d'ella en null.

444
00:22:12,585 --> 00:22:13,720
Això és exactament correcte.

445
00:22:13,720 --> 00:22:17,400
I llavors què passa després d'això?

446
00:22:17,400 --> 00:22:18,490
Dibuixem la imatge en el tauler.

447
00:22:18,490 --> 00:22:21,190
Llavors, què fem?

448
00:22:21,190 --> 00:22:22,680
>> AUDIÈNCIA: Anem a través de la llista.

449
00:22:22,680 --> 00:22:23,930
>> JASON Hirschhorn: Anar a través de la llista.

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

451
00:22:30,620 --> 00:22:31,100
D'acord.

452
00:22:31,100 --> 00:22:34,280
I què anem a comprovar en cada node.

453
00:22:34,280 --> 00:22:35,955
Kurt, què és el comprovar
per a cada node?

454
00:22:35,955 --> 00:22:41,640
>> AUDIÈNCIA: Veure si el valor de n de
aquest node és major que el valor de n

455
00:22:41,640 --> 00:22:43,070
del nostre node.

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

457
00:22:43,340 --> 00:22:44,280
Jo faré -

458
00:22:44,280 --> 00:22:45,855
Sí, està bé.

459
00:22:45,855 --> 00:22:48,160
Així que és n -

460
00:22:48,160 --> 00:22:59,040
Jo vaig a dir si el valor és més gran
d'aquest node, llavors, què fem?

461
00:22:59,040 --> 00:23:07,290
>> AUDIÈNCIA: Bé, llavors ens inserim
el correcte abans d'això.

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

463
00:23:07,970 --> 00:23:09,410
Així que si és més gran que aquest,
llavors volem inserir.

464
00:23:09,410 --> 00:23:14,010
Però volem inserir just abans de
perquè nosaltres també necessitem ser

465
00:23:14,010 --> 00:23:16,070
fer el seguiment i, a continuació,
del que era abans.

466
00:23:16,070 --> 00:23:22,690
Així que inserir abans.

467
00:23:22,690 --> 00:23:25,120
Així que és probable que vam perdre alguna cosa
anteriorment.

468
00:23:25,120 --> 00:23:27,770
Probablement necessitem estar mantenint
un seguiment del que està passant.

469
00:23:27,770 --> 00:23:28,460
Però anem a arribar-hi.

470
00:23:28,460 --> 00:23:30,160
Llavors, quin valor és inferior?

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

472
00:23:38,030 --> 00:23:39,710
Kurt, què fem si
valor és menor que?

473
00:23:39,710 --> 00:23:43,000
>> AUDIÈNCIA: A continuació, només seguir endavant
llevat que sigui l'últim.

474
00:23:43,000 --> 00:23:43,550
>> JASON Hirschhorn: això m'agrada.

475
00:23:43,550 --> 00:23:44,800
Així que anar al següent node.

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

477
00:23:47,410 --> 00:23:48,930
Si no sou l'últim -

478
00:23:48,930 --> 00:23:51,100
és probable que estem comprovant que
en els termes d'una condició.

479
00:23:51,100 --> 00:23:54,870
Però sí, el proper node.

480
00:23:54,870 --> 00:23:58,680
I això no baixi molt,
així que anem a passar per aquí.

481
00:23:58,680 --> 00:24:02,030
Però si -

482
00:24:02,030 --> 00:24:03,280
Tots poden veure això?

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

484
00:24:07,230 --> 00:24:11,610
Si som iguals, què fem?

485
00:24:11,610 --> 00:24:15,740
Si el valor que estem tractant d'inserir
és igual al valor d'aquest node?

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

487
00:24:16,320 --> 00:24:18,400
>> AUDIÈNCIA: [inaudible].

488
00:24:18,400 --> 00:24:18,850
>> JASON Hirschhorn: Si.

489
00:24:18,850 --> 00:24:19,290
Donada aquesta -

490
00:24:19,290 --> 00:24:20,090
Marcus té raó.

491
00:24:20,090 --> 00:24:21,330
Podríem haver fet potser
alguna cosa diferent.

492
00:24:21,330 --> 00:24:25,360
Però tenint en compte que hem creat, aquí
hem alliberar i després tornar.

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

494
00:24:26,774 --> 00:24:30,080
Així està millor?

495
00:24:30,080 --> 00:24:31,850
Com és això?

496
00:24:31,850 --> 00:24:33,100
D'acord.

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

498
00:24:35,360 --> 00:24:37,640
Gratis i llavors, què fem nosaltres
tornar, [inaudible]?

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

500
00:24:41,330 --> 00:24:44,110
D'acord.

501
00:24:44,110 --> 00:24:45,360
Ens estem perdent alguna cosa?

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

503
00:24:53,500 --> 00:24:59,650
Llavors, on fer el seguiment
del node abans?

504
00:24:59,650 --> 00:25:02,370
>> AUDIÈNCIA: Crec que seria anar
després de crear un nou node.

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

506
00:25:02,600 --> 00:25:03,940
Així que al principi probablement anem -

507
00:25:03,940 --> 00:25:07,175
sí, podem crear un punter a una nova
node, com un punter de node anterior i

508
00:25:07,175 --> 00:25:09,600
un punter node actual.

509
00:25:09,600 --> 00:25:12,640
Així que anem a inserir això aquí.

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

511
00:25:15,610 --> 00:25:26,900
Crear actual i anterior
punters als nodes.

512
00:25:26,900 --> 00:25:28,955
Però quan ens ajustem els punters?

513
00:25:28,955 --> 00:25:30,205
On ho fem en el codi?

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
>> AUDIÈNCIA: - condicions de valor?

517
00:25:35,170 --> 00:25:36,420
>> JASON Hirschhorn: Què
un en particular?

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

519
00:25:39,862 --> 00:25:40,720
>> AUDIÈNCIA: Estic confós.

520
00:25:40,720 --> 00:25:44,200
Si el valor és superior a aquest node,
¿Això no significa que vostè vol anar

521
00:25:44,200 --> 00:25:45,320
al següent node?

522
00:25:45,320 --> 00:25:49,515
>> JASON Hirschhorn: Així que si el nostre valor és
més gran que el valor d'aquest node.

523
00:25:49,515 --> 00:25:52,130
>> AUDIÈNCIA: Sí, llavors el que vol
anar més avall de la línia, no?

524
00:25:52,130 --> 00:25:52,590
>> JASON Hirschhorn: així.

525
00:25:52,590 --> 00:25:53,840
Així que no inserim aquí.

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

527
00:25:58,430 --> 00:26:03,240
Si el valor és inferior a aquest node, a continuació,
anem al següent node - o llavors

528
00:26:03,240 --> 00:26:03,835
inserir abans.

529
00:26:03,835 --> 00:26:05,966
>> AUDIÈNCIA: Espera, que és aquest
node i que és el valor?

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

531
00:26:08,510 --> 00:26:09,280
>> JASON Hirschhorn: Bona pregunta.

532
00:26:09,280 --> 00:26:13,260
Valor per aquesta definició de funció
és el que se'ns dóna.

533
00:26:13,260 --> 00:26:16,910
Així que el valor és el nombre que se'ns dóna.

534
00:26:16,910 --> 00:26:21,120
Així que si el valor és menor que aquest
node, necessitem temps per inserir.

535
00:26:21,120 --> 00:26:24,575
Si el valor és superior a aquest node,
anem al següent node.

536
00:26:24,575 --> 00:26:26,790
I tornant a la pregunta original,
però, on -

537
00:26:26,790 --> 00:26:29,060
>> AUDIÈNCIA: Si el valor és més gran
d'aquest node.

538
00:26:29,060 --> 00:26:30,310
>> JASON Hirschhorn: I així
Què fem aquí?

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

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

541
00:26:38,160 --> 00:26:38,860
Això és correcte.

542
00:26:38,860 --> 00:26:41,370
Jo només vaig a escriure
punters d'actualització.

543
00:26:41,370 --> 00:26:44,010
Però això sí, amb l'actual
vol actualitzar a

544
00:26:44,010 --> 00:26:46,080
apuntar a la següent.

545
00:26:46,080 --> 00:26:47,330
Qualsevol altra cosa que s'està perdent?

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

547
00:26:52,710 --> 00:26:54,940
Així que vaig a escriure això
codi en gedit.

548
00:26:54,940 --> 00:26:58,375
I mentre faig això, vostè pot tenir una
parell de minuts més per treballar en la codificació

549
00:26:58,375 --> 00:28:19,240
està en C.

550
00:28:19,240 --> 00:28:20,940
>> Així que he de ingressar el pseudocodi.

551
00:28:20,940 --> 00:28:22,940
Una nota ràpida abans de començar.

552
00:28:22,940 --> 00:28:25,560
Potser no siguem capaços de completament
acabar això en tot

553
00:28:25,560 --> 00:28:27,300
tres d'aquestes funcions.

554
00:28:27,300 --> 00:28:30,630
Hi ha solucions correctes als
que vaig a enviar per correu electrònic a vostès

555
00:28:30,630 --> 00:28:33,730
després de la secció, i ho farà
es publicaran en CS50.net.

556
00:28:33,730 --> 00:28:35,640
Així que no us animo a
anar a buscar a les seccions.

557
00:28:35,640 --> 00:28:40,550
T'animo a que intenti resoldre vostè
posseir, i aleshores utilitzar el la pràctica

558
00:28:40,550 --> 00:28:41,760
problemes per comprovar les seves respostes.

559
00:28:41,760 --> 00:28:47,070
Totes elles han estat dissenyades per a prop
relacionar-se i complir el que

560
00:28:47,070 --> 00:28:48,400
el que has de fer en el conjunt de problemes.

561
00:28:48,400 --> 00:28:53,820
Així que t'animo a practicar aquest
pel seu compte i després utilitzar el codi per

562
00:28:53,820 --> 00:28:54,660
comprovi seves respostes.

563
00:28:54,660 --> 00:28:57,060
Perquè vull seguir endavant per discutir
taules en algun punt de la secció.

564
00:28:57,060 --> 00:28:58,150
Així que podríem no aconseguir en tot moment.

565
00:28:58,150 --> 00:28:59,960
Però farem el més que puguem ara.

566
00:28:59,960 --> 00:29:00,370
>> D'acord.

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

568
00:29:01,960 --> 00:29:04,770
Asam, com creem un nou node?

569
00:29:04,770 --> 00:29:06,810
>> AUDIÈNCIA: Vostè struct *.

570
00:29:06,810 --> 00:29:09,640
>> JASON Hirschhorn: Així que
haver de fins aquí.

571
00:29:09,640 --> 00:29:10,040
Oh, ho sento.

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

573
00:29:13,530 --> 00:29:17,260
>> AUDIÈNCIA: I després [? tipus?]
node o node c.

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

575
00:29:17,780 --> 00:29:19,740
Vaig a dir-new_node
perquè puguem romandre constant.

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

577
00:29:22,646 --> 00:29:33,180
>> AUDIÈNCIA: I vostè desitja establir que
al capdavant, el primer node.

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

579
00:29:33,580 --> 00:29:37,290
Així que ara aquesta apuntant a - pel que aquest
no ha creat un nou node encara.

580
00:29:37,290 --> 00:29:41,380
Això és només apunta a la
primer node a la llista.

581
00:29:41,380 --> 00:29:42,630
Com es crea un nou node?

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

583
00:29:45,490 --> 00:29:48,070
Si necessito espai per crear un nou node.

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

585
00:29:49,230 --> 00:29:51,710
I què tan gran?

586
00:29:51,710 --> 00:30:00,390
>> AUDIÈNCIA: La mida de l'estructura.

587
00:30:00,390 --> 00:30:01,150
>> JASON Hirschhorn: El
mida de l'estructura.

588
00:30:01,150 --> 00:30:02,400
I quina és l'estructura trucada?

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

590
00:30:09,670 --> 00:30:09,840
>> AUDIÈNCIA: Node?

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

592
00:30:11,640 --> 00:30:17,640
Així malloc (sizeof (node));
ens dóna l'espai.

593
00:30:17,640 --> 00:30:19,740
I és aquesta línia -

594
00:30:19,740 --> 00:30:21,740
una cosa és incorrecte en aquesta línia.

595
00:30:21,740 --> 00:30:24,430
És new_node un punter a una estructura?

596
00:30:24,430 --> 00:30:25,650
És un nom genèric.

597
00:30:25,650 --> 00:30:26,520
Què és -

598
00:30:26,520 --> 00:30:27,450
node, exactament.

599
00:30:27,450 --> 00:30:29,340
És un node *.

600
00:30:29,340 --> 00:30:33,010
I, què fem després
que malloc alguna cosa, Asan?

601
00:30:33,010 --> 00:30:34,476
Què és el primer que farem?

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

603
00:30:38,850 --> 00:30:40,320
Què passa si no funciona?

604
00:30:40,320 --> 00:30:42,430
>> AUDIÈNCIA: Oh, comproveu si
apunta al node?

605
00:30:42,430 --> 00:30:43,310
>> JASON Hirschhorn: Exactament.

606
00:30:43,310 --> 00:30:46,750
Així que si vostè new_node iguals iguals
nul, què fem?

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

608
00:30:51,650 --> 00:30:54,820
Això retorna un bool, aquesta funció.

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

610
00:30:57,760 --> 00:30:58,450
Es veu bé.

611
00:30:58,450 --> 00:30:59,680
Qualsevol cosa per afegir aquí?

612
00:30:59,680 --> 00:31:00,670
Anem a afegir coses al final.

613
00:31:00,670 --> 00:31:03,160
Però que fins al moment es veu bé.

614
00:31:03,160 --> 00:31:06,170
Crear indicadors actuals i anteriors.

615
00:31:06,170 --> 00:31:08,650
Michael, com puc fer això?

616
00:31:08,650 --> 00:31:12,810
>> AUDIÈNCIA: Vostè hauria
fer un node *.

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

618
00:31:21,800 --> 00:31:25,502
Hauries de ho fa a un
per new_node però per a la

619
00:31:25,502 --> 00:31:26,905
nodes que ja tenen.

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

621
00:31:27,230 --> 00:31:29,255
Així que el node actual estem en.

622
00:31:29,255 --> 00:31:30,505
Vaig a trucar a aquest curr.

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

624
00:31:39,650 --> 00:31:39,770
Està bé.

625
00:31:39,770 --> 00:31:41,620
Hem decidit que volem mantenir
dos, perquè hem de saber

626
00:31:41,620 --> 00:31:42,870
el que hi ha abans d'ella.

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

628
00:31:45,770 --> 00:31:47,020
Què són inicialitzades a?

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

630
00:31:49,874 --> 00:31:54,180
>> AUDIÈNCIA: El seu valor a la nostra llista.

631
00:31:54,180 --> 00:31:58,090
>> JASON Hirschhorn: Llavors, quin és el
El primer a la nostra llista?

632
00:31:58,090 --> 00:32:04,050
O, com sabem que el
a partir de la nostra llista és?

633
00:32:04,050 --> 00:32:08,015
>> AUDIÈNCIA: No es va aprovar
en la funció de?

634
00:32:08,015 --> 00:32:08,466
>> JASON Hirschhorn: així.

635
00:32:08,466 --> 00:32:09,716
Es va aprovar en aquí.

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

637
00:32:15,910 --> 00:32:18,980
Així que si es passa a la funció, la
inici de la llista, què hem

638
00:32:18,980 --> 00:32:21,270
establir corrent igual a?

639
00:32:21,270 --> 00:32:22,110
>> AUDIÈNCIA: Llista.

640
00:32:22,110 --> 00:32:22,900
>> JASON Hirschhorn: Llista.

641
00:32:22,900 --> 00:32:24,090
Això és exactament correcte.

642
00:32:24,090 --> 00:32:26,290
Ara que té la direcció de
el principi de la nostra llista.

643
00:32:26,290 --> 00:32:28,450
I què passa amb prèvia?

644
00:32:28,450 --> 00:32:31,920
>> AUDIÈNCIA: Llista menys un?

645
00:32:31,920 --> 00:32:32,690
>> JASON Hirschhorn: No
res abans d'ella.

646
00:32:32,690 --> 00:32:34,580
Llavors, què podem fer per significar res?

647
00:32:34,580 --> 00:32:35,050
>> AUDIÈNCIA: Nul.

648
00:32:35,050 --> 00:32:35,450
>> JASON Hirschhorn: Si.

649
00:32:35,450 --> 00:32:37,950
Això sona com una bona idea.

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

651
00:32:38,360 --> 00:32:39,630
Gràcies.

652
00:32:39,630 --> 00:32:42,850
Anar a través de la llista.

653
00:32:42,850 --> 00:32:45,490
Constantí, quant de temps anem
de passar per la llista?

654
00:32:45,490 --> 00:32:49,010
>> AUDIÈNCIA: fins arribar a nul.

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

656
00:32:49,390 --> 00:32:50,430
Així que si, mentre que, per al bucle.

657
00:32:50,430 --> 00:32:52,200
Què estem fent?

658
00:32:52,200 --> 00:32:53,320
>> AUDIÈNCIA: Potser un bucle?

659
00:32:53,320 --> 00:32:53,910
>> JASON Hirschhorn: Anem a fer un bucle for.

660
00:32:53,910 --> 00:32:55,870
D'acord.

661
00:32:55,870 --> 00:33:02,465
>> AUDIÈNCIA: I diem per -

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

663
00:33:09,764 --> 00:33:13,390
fins que el punter actual
no és igual a nul.

664
00:33:13,390 --> 00:33:19,160
>> JASON Hirschhorn: Així que si coneixem la
condicions, com podem escriure un bucle

665
00:33:19,160 --> 00:33:21,740
amb seu fora aquesta condició.

666
00:33:21,740 --> 00:33:24,380
Quina classe d'un bucle hem d'utilitzar?

667
00:33:24,380 --> 00:33:25,260
>> AUDIÈNCIA: While.

668
00:33:25,260 --> 00:33:25,590
>> JASON Hirschhorn: Si.

669
00:33:25,590 --> 00:33:27,130
Això té més sentit amb base
fora del que vas dir.

670
00:33:27,130 --> 00:33:29,430
Si només volem anar a que ho faria
només sé que cosa, hauria

671
00:33:29,430 --> 00:33:31,680
sentit fer un bucle while.

672
00:33:31,680 --> 00:33:39,880
Mentre que el corrent no és igual a null,
si el valor és inferior a aquest node.

673
00:33:39,880 --> 00:33:41,650
Akshar, dóna'm d'aquesta línia.

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

675
00:33:48,810 --> 00:33:56,955
>> AUDIÈNCIA: Si current-> n
n menys del seu valor.

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

677
00:34:00,170 --> 00:34:03,260
O revertir això.

678
00:34:03,260 --> 00:34:06,140
Canvieu aquesta franja.

679
00:34:06,140 --> 00:34:06,620
>> JASON Hirschhorn: Ho sento.

680
00:34:06,620 --> 00:34:08,760
>> AUDIÈNCIA: Canvieu el suport.

681
00:34:08,760 --> 00:34:10,914
>> JASON Hirschhorn: Així que si és
major que el valor.

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

683
00:34:18,719 --> 00:34:22,120
Perquè això és confús amb la
comenti anteriorment, faré això.

684
00:34:22,120 --> 00:34:22,480
Però si.

685
00:34:22,480 --> 00:34:25,125
Si el nostre valor és menor que aquest
node, què fem?

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

687
00:34:25,540 --> 00:34:26,710
Ho tinc aquí mateix.

688
00:34:26,710 --> 00:34:27,960
Insereix abans.

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

690
00:34:32,080 --> 00:34:32,370
D'acord.

691
00:34:32,370 --> 00:34:33,933
Com fem això?

692
00:34:33,933 --> 00:34:34,900
>> AUDIÈNCIA: Segueix sent el meu?

693
00:34:34,900 --> 00:34:36,150
>> JASON Hirschhorn: Si.

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

695
00:34:38,520 --> 00:34:39,770
>> AUDIÈNCIA: Vostè -

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

697
00:34:42,909 --> 00:34:44,159
new_node-> següent.

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

699
00:34:46,770 --> 00:34:50,163
>> JASON Hirschhorn: Llavors, què
que serà igual?

700
00:34:50,163 --> 00:34:52,070
>> AUDIÈNCIA: Va a la mateixa corrent.

701
00:34:52,070 --> 00:34:53,889
>> JASON Hirschhorn: Exactament.

702
00:34:53,889 --> 00:34:55,730
I així, l'altre -

703
00:34:55,730 --> 00:34:56,730
el que més necessitem per actualitzar?

704
00:34:56,730 --> 00:34:59,982
>> AUDIÈNCIA: Comproveu si el passat és igual a nul.

705
00:34:59,982 --> 00:35:01,870
>> JASON Hirschhorn: Si prev -

706
00:35:01,870 --> 00:35:03,730
pel que si és igual prev nul.

707
00:35:03,730 --> 00:35:05,990
>> AUDIÈNCIA: Això vol dir que va
per esdevenir el cap.

708
00:35:05,990 --> 00:35:06,780
>> JASON Hirschhorn: Això significa
s'ha convertit en el cap.

709
00:35:06,780 --> 00:35:07,620
Llavors, què fem?

710
00:35:07,620 --> 00:35:12,510
>> AUDIÈNCIA: Fem el cap és igual new_node.

711
00:35:12,510 --> 00:35:16,690
>> JASON Hirschhorn: Head
iguals new_node.

712
00:35:16,690 --> 00:35:20,540
I per què el cap aquí, no llista?

713
00:35:20,540 --> 00:35:24,940
>> AUDIÈNCIA: A causa de que el cap és un mundial
variable, que és el punt de partida.

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
D'acord.

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

718
00:35:36,150 --> 00:35:53,796
>> AUDIÈNCIA: Llavors, els altres prev->
següent és igual new_node.

719
00:35:53,796 --> 00:35:55,080
I després pot tornar realitat.

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

721
00:35:59,560 --> 00:36:02,700
>> JASON Hirschhorn: On
ens vam posar fi new_node?

722
00:36:02,700 --> 00:36:04,850
>> AUDIÈNCIA: jo -

723
00:36:04,850 --> 00:36:06,180
Em vaig posar que al començament.

724
00:36:06,180 --> 00:36:07,430
>> JASON Hirschhorn: Llavors, quina línia?

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

726
00:36:10,000 --> 00:36:12,598
>> AUDIÈNCIA: Després de la sentència if
comprovar si se sap.

727
00:36:12,598 --> 00:36:13,057
>> JASON Hirschhorn: Aquí mateix?

728
00:36:13,057 --> 00:36:18,335
>> AUDIÈNCIA: Faria new_node-> n
mateix valor.

729
00:36:18,335 --> 00:36:19,585
>> JASON Hirschhorn: Sona bé.

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

731
00:36:21,740 --> 00:36:25,090
Probablement té sentit - no ho fem
necessita saber el que la llista que estem en

732
00:36:25,090 --> 00:36:26,280
perquè només estem tractant
amb una sola llista.

733
00:36:26,280 --> 00:36:29,560
Per tant una millor declaració de la funció de
això és només per desfer-se d'aquest

734
00:36:29,560 --> 00:36:34,360
completament i només ha d'inserir
un valor al cap.

735
00:36:34,360 --> 00:36:35,930
Ni tan sols necessitem saber
el llista que estem ficats

736
00:36:35,930 --> 00:36:39,140
Però vaig a mantenir tot per ara i
després canviar a l'actualització

737
00:36:39,140 --> 00:36:42,590
les diapositives i codi.

738
00:36:42,590 --> 00:36:44,980
Així que es veu bé, per ara.

739
00:36:44,980 --> 00:36:46,560
Si el valor - que pot fer aquesta línia?

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

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

742
00:36:52,240 --> 00:36:53,840
Què fem aquí, Noah.

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

744
00:36:57,890 --> 00:37:07,100
>> AUDIÈNCIA: Si el valor és més gran
de curr-> n -

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

746
00:37:16,830 --> 00:37:18,240
>> JASON Hirschhorn: Com
anem al següent node?

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

748
00:37:27,760 --> 00:37:30,530
>> AUDIÈNCIA: Curr-> n és
igual a new_node.

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

750
00:37:37,630 --> 00:37:39,195
>> JASON Hirschhorn: Llavors n és
quina part de l'estructura?

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

752
00:37:43,065 --> 00:37:46,020
El nombre enter.

753
00:37:46,020 --> 00:37:50,420
I new_node és un punter a un node.

754
00:37:50,420 --> 00:37:51,880
Llavors, quina part de curr hem d'actualitzar?

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

756
00:38:03,900 --> 00:38:05,400
Si no és n, llavors quina és l'altra part?

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

758
00:38:21,680 --> 00:38:22,810
Noè, quina és l'altra part.

759
00:38:22,810 --> 00:38:23,570
>> AUDIÈNCIA: Oh, la propera.

760
00:38:23,570 --> 00:38:25,645
>> JASON Hirschhorn: A continuació, exactament.

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

762
00:38:26,410 --> 00:38:28,770
Següent és la correcta.

763
00:38:28,770 --> 00:38:31,540
I el que més necessitem
actualitzar, Noah?

764
00:38:31,540 --> 00:38:32,840
>> AUDIÈNCIA: Els punters.

765
00:38:32,840 --> 00:38:34,840
>> JASON Hirschhorn: Així
actualitzem actual.

766
00:38:34,840 --> 00:38:36,090
>> AUDIÈNCIA: Anterior-> següent.

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

768
00:38:48,160 --> 00:38:49,410
>> JASON Hirschhorn: Si.

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

770
00:38:57,465 --> 00:38:58,370
Bé, anem a fer una pausa.

771
00:38:58,370 --> 00:39:02,200
Qui ens pot ajudar?

772
00:39:02,200 --> 00:39:03,385
Manu, què hem de fer?

773
00:39:03,385 --> 00:39:05,615
>> AUDIÈNCIA: Cal establir
és igual a curr-> següent.

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

775
00:39:09,110 --> 00:39:11,630
Però fer això abans de la línia anterior.

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
Alguna cosa més?

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

780
00:39:19,170 --> 00:39:22,680
>> AUDIÈNCIA: Crec que no estàs
la intenció de canviar curr-> següent.

781
00:39:22,680 --> 00:39:29,270
Crec que estàs destinat a fer iguals curr
curr-> següent per anar al següent node.

782
00:39:29,270 --> 00:39:30,500
>> JASON Hirschhorn: Ho sento, on?

783
00:39:30,500 --> 00:39:32,680
En quina línia?

784
00:39:32,680 --> 00:39:33,420
Aquesta línia?

785
00:39:33,420 --> 00:39:33,750
>> AUDIÈNCIA: Si.

786
00:39:33,750 --> 00:39:35,745
Fer curr equival curr-> següent.

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

788
00:39:39,690 --> 00:39:43,360
>> JASON Hirschhorn: Així que això és correcte
perquè el corrent és una

789
00:39:43,360 --> 00:39:45,220
punter a un node.

790
00:39:45,220 --> 00:39:48,550
I volem que apunti a la següent
node del que està rebent en l'actualitat

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

792
00:39:49,930 --> 00:39:54,410
Curr en si té un següent.

793
00:39:54,410 --> 00:39:58,620
Però si haguéssim de actualitzar curr.next, ens
seria l'actualització de la nota real

794
00:39:58,620 --> 00:40:01,430
en si, no on aquesta
punter assenyalava.

795
00:40:01,430 --> 00:40:02,680
Què passa amb aquesta línia, 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
>> AUDIÈNCIA: Anterior-> següent és igual curr.

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

800
00:40:12,500 --> 00:40:19,440
>> JASON Hirschhorn: Així que de nou, en cas anterior és un
punter a un node, anterior-> següent és la

801
00:40:19,440 --> 00:40:23,020
punter actual al node.

802
00:40:23,020 --> 00:40:27,190
Així que aquesta seria l'actualització d'una
punter en un node per curr.

803
00:40:27,190 --> 00:40:28,570
No volem posar al dia
un punter a un node.

804
00:40:28,570 --> 00:40:30,570
Volem posar al dia anterior.

805
00:40:30,570 --> 00:40:31,850
Llavors, com fem això?

806
00:40:31,850 --> 00:40:34,250
>> AUDIÈNCIA: Només es preveu.

807
00:40:34,250 --> 00:40:34,565
>> JASON Hirschhorn: així.

808
00:40:34,565 --> 00:40:35,560
Anterior és un punter a un node.

809
00:40:35,560 --> 00:40:38,750
Ara anem a canviar a un
nou punter a un node.

810
00:40:38,750 --> 00:40:40,830
Acceptar Belluguem-nos cap avall.

811
00:40:40,830 --> 00:40:41,940
Finalment, aquesta última condició.

812
00:40:41,940 --> 00:40:44,896
Jeff, què fem aquí?

813
00:40:44,896 --> 00:40:47,515
>> AUDIÈNCIA: Si el valor és
igual a curr-> n.

814
00:40:47,515 --> 00:40:51,030

815
00:40:51,030 --> 00:40:51,300
>> JASON Hirschhorn: Ho sento.

816
00:40:51,300 --> 00:40:52,372
Oh Déu meu.

817
00:40:52,372 --> 00:40:54,330
Què?

818
00:40:54,330 --> 00:40:55,580
Valor == curr-> n.

819
00:40:55,580 --> 00:41:01,050

820
00:41:01,050 --> 00:41:02,300
Què fem?

821
00:41:02,300 --> 00:41:04,760

822
00:41:04,760 --> 00:41:10,950
>> AUDIÈNCIA: Vostè seria alliberar als nostres new_node,
i després et tornaries falsa.

823
00:41:10,950 --> 00:41:21,410

824
00:41:21,410 --> 00:41:23,460
>> JASON Hirschhorn: Això és el que
que hem escrit fins ara.

825
00:41:23,460 --> 00:41:25,710
Algú té alguna cosa
afegir abans que fem?

826
00:41:25,710 --> 00:41:35,460

827
00:41:35,460 --> 00:41:35,710
D'acord.

828
00:41:35,710 --> 00:41:36,960
Anem a intentar-ho.

829
00:41:36,960 --> 00:41:44,180

830
00:41:44,180 --> 00:41:46,110
El control pot arribar a la final
d'una funció no nul · la.

831
00:41:46,110 --> 00:41:48,310
Avi, què està passant?

832
00:41:48,310 --> 00:41:51,380
>> AUDIÈNCIA: Se suposa posar de retorn
cert fora del bucle while?

833
00:41:51,380 --> 00:41:53,900

834
00:41:53,900 --> 00:41:54,400
>> JASON Hirschhorn: No sé.

835
00:41:54,400 --> 00:41:54,780
Em vols?

836
00:41:54,780 --> 00:41:55,520
>> AUDIÈNCIA: No 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
>> AUDIÈNCIA: Crec que la intenció de
posar return false al final

840
00:41:59,460 --> 00:42:02,230
del bucle while.

841
00:42:02,230 --> 00:42:03,270
>> JASON Hirschhorn: Llavors, on
Què vols que vagi?

842
00:42:03,270 --> 00:42:05,270
>> AUDIÈNCIA: Igual que fora del bucle while.

843
00:42:05,270 --> 00:42:08,800
Així que si surt del bucle while que els mitjans
que ha arribat al final i

844
00:42:08,800 --> 00:42:09,980
no ha passat res.

845
00:42:09,980 --> 00:42:10,410
>> JASON Hirschhorn: OK.

846
00:42:10,410 --> 00:42:12,340
Així que, què fem aquí?

847
00:42:12,340 --> 00:42:13,702
>> AUDIÈNCIA: Vostè torna falsa
allà també.

848
00:42:13,702 --> 00:42:15,040
>> JASON Hirschhorn: Oh,
fer-ho en tots dos llocs?

849
00:42:15,040 --> 00:42:15,650
>> AUDIÈNCIA: Si.

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
Cal anar?

853
00:42:26,160 --> 00:42:26,980
Oh Déu meu.

854
00:42:26,980 --> 00:42:27,290
Ho sento.

855
00:42:27,290 --> 00:42:28,480
Demano disculpes per la pantalla.

856
00:42:28,480 --> 00:42:30,530
És una mica flipant en nosaltres.

857
00:42:30,530 --> 00:42:31,520
Així que has de triar una opció.

858
00:42:31,520 --> 00:42:35,260
Zero, pel codi, es tanca el programa.

859
00:42:35,260 --> 00:42:36,700
Un insereix alguna cosa.

860
00:42:36,700 --> 00:42:37,990
Anem a inserir 03:00.

861
00:42:37,990 --> 00:42:42,900

862
00:42:42,900 --> 00:42:45,380
El inserit no va tenir èxit.

863
00:42:45,380 --> 00:42:46,500
Vaig a imprimir.

864
00:42:46,500 --> 00:42:48,050
Jo no tinc res.

865
00:42:48,050 --> 00:42:48,450
D'acord.

866
00:42:48,450 --> 00:42:50,250
Potser això era només una casualitat.

867
00:42:50,250 --> 00:42:52,810
Inseriu un.

868
00:42:52,810 --> 00:42:55,770
No èxit.

869
00:42:55,770 --> 00:42:57,470
D'acord.

870
00:42:57,470 --> 00:43:02,400
Anem a executar a través de GDB molt ràpid
per comprovar el que està passant.

871
00:43:02,400 --> 00:43:06,055
>> Recordi gdb. / El nom de la seva
programa ens fica al BGF.

872
00:43:06,055 --> 00:43:07,610
És que una gran quantitat d'utilitzar?

873
00:43:07,610 --> 00:43:08,560
El intermitent?

874
00:43:08,560 --> 00:43:10,400
Probablement.

875
00:43:10,400 --> 00:43:12,760
Tanca els ulls i prendre una mica de profunditat
respiracions si et canses

876
00:43:12,760 --> 00:43:13,580
de veure les coses.

877
00:43:13,580 --> 00:43:14,200
Sóc al BGF.

878
00:43:14,200 --> 00:43:15,830
Què és el primer que faig en GDB?

879
00:43:15,830 --> 00:43:17,050
Hem d'esbrinar
Què està passant aquí.

880
00:43:17,050 --> 00:43:17,310
Anem a veure.

881
00:43:17,310 --> 00:43:21,650
Tenim sis minuts de la figura
el que està passant.

882
00:43:21,650 --> 00:43:22,900
Trencar principal.

883
00:43:22,900 --> 00:43:25,950

884
00:43:25,950 --> 00:43:28,130
I llavors, què faig?

885
00:43:28,130 --> 00:43:29,180
Carles?

886
00:43:29,180 --> 00:43:31,060
Executar.

887
00:43:31,060 --> 00:43:32,250
D'acord.

888
00:43:32,250 --> 00:43:34,160
Anem a escollir una opció.

889
00:43:34,160 --> 00:43:36,330
I què té N fer?

890
00:43:36,330 --> 00:43:38,480
Següent.

891
00:43:38,480 --> 00:43:38,950
Sí

892
00:43:38,950 --> 00:43:39,740
>> AUDIÈNCIA: No ho dius -

893
00:43:39,740 --> 00:43:45,230
què no em vas dir que el cap, que era
inicialitza en null al principi.

894
00:43:45,230 --> 00:43:47,140
Però vaig pensar que havies dit que estava bé.

895
00:43:47,140 --> 00:43:50,040

896
00:43:50,040 --> 00:43:52,640
>> JASON Hirschhorn: Anem - veurem
en GDB, i després tornarem.

897
00:43:52,640 --> 00:43:54,910
Però sembla que vostè ja té
algunes idees sobre el que està passant.

898
00:43:54,910 --> 00:43:58,340
Així que volem inserir alguna cosa.

899
00:43:58,340 --> 00:43:59,390
D'acord.

900
00:43:59,390 --> 00:44:00,150
Hem inserir.

901
00:44:00,150 --> 00:44:00,770
Posa un int.

902
00:44:00,770 --> 00:44:01,990
Nosaltres inserirem 3.

903
00:44:01,990 --> 00:44:03,000
I llavors estic en aquesta línia.

904
00:44:03,000 --> 00:44:07,030
Com puc iniciar la depuració
la inserció de la funció coneguda?

905
00:44:07,030 --> 00:44:08,280
Oh Déu meu.

906
00:44:08,280 --> 00:44:10,990

907
00:44:10,990 --> 00:44:12,240
Això és un munt.

908
00:44:12,240 --> 00:44:14,372

909
00:44:14,372 --> 00:44:16,445
Això embogint molt?

910
00:44:16,445 --> 00:44:19,696

911
00:44:19,696 --> 00:44:21,680
>> AUDIÈNCIA: Oh, va morir.

912
00:44:21,680 --> 00:44:22,930
>> JASON Hirschhorn: Acabo
el va treure.

913
00:44:22,930 --> 00:44:27,364

914
00:44:27,364 --> 00:44:28,310
D'acord.

915
00:44:28,310 --> 00:44:29,560
>> AUDIÈNCIA: Potser és el
altre extrem del cable.

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
Així que la conclusió -

919
00:44:42,330 --> 00:44:43,470
Què li vas dir?

920
00:44:43,470 --> 00:44:46,040
>> AUDIÈNCIA: Vaig dir que la ironia de la tècnica
dificultats en aquesta classe.

921
00:44:46,040 --> 00:44:46,410
>> JASON Hirschhorn: Ho sé.

922
00:44:46,410 --> 00:44:48,660
Si tan sols tingués el control sobre aquesta part.

923
00:44:48,660 --> 00:44:49,910
[Inaudible]

924
00:44:49,910 --> 00:44:54,430

925
00:44:54,430 --> 00:44:55,400
Això sona molt bé.

926
00:44:55,400 --> 00:44:58,680
Per què no començar a pensar en els nois
el que podríem haver fet malament,

927
00:44:58,680 --> 00:45:01,140
i estarem de tornada en 90 segons.

928
00:45:01,140 --> 00:46:18,160

929
00:46:18,160 --> 00:46:23,010
>> AVICA, vaig a preguntar-li com anar
insert_node interior per depurar.

930
00:46:23,010 --> 00:46:28,940

931
00:46:28,940 --> 00:46:31,460
Així que aquí és on ens va deixar l'última vegada.

932
00:46:31,460 --> 00:46:35,110
Com em vaig endins insert_node, AVICA,
examinar el que està passant?

933
00:46:35,110 --> 00:46:36,360
Què comandament GDB?

934
00:46:36,360 --> 00:46:41,050

935
00:46:41,050 --> 00:46:42,390
Pausa no em portaria al seu interior.

936
00:46:42,390 --> 00:46:46,200

937
00:46:46,200 --> 00:46:47,130
Ho sap Marquise?

938
00:46:47,130 --> 00:46:48,240
>> AUDIÈNCIA: Què?

939
00:46:48,240 --> 00:46:51,780
>> JASON Hirschhorn: Què comandament GDB
Jo ús per anar dins d'aquesta funció?

940
00:46:51,780 --> 00:46:52,070
>> AUDIÈNCIA: Step?

941
00:46:52,070 --> 00:46:55,140
>> JASON Hirschhorn: Pas a través d'
S. Això em porta dins.

942
00:46:55,140 --> 00:46:55,476
D'acord.

943
00:46:55,476 --> 00:46:58,040
New_node mallocing una mica d'espai.

944
00:46:58,040 --> 00:46:59,120
Tot això sembla que va.

945
00:46:59,120 --> 00:47:00,370
Anem a examinar new_node.

946
00:47:00,370 --> 00:47:03,270

947
00:47:03,270 --> 00:47:05,410
Es va posar una mica de direcció de memòria.

948
00:47:05,410 --> 00:47:07,440
Anem a veure -

949
00:47:07,440 --> 00:47:08,500
això és tot el correcte.

950
00:47:08,500 --> 00:47:12,220
Així que tot el que aquí sembla
estar funcionant correctament.

951
00:47:12,220 --> 00:47:14,530
>> AUDIÈNCIA: Quina és la diferència
entre P i la pantalla?

952
00:47:14,530 --> 00:47:16,160
>> JASON Hirschhorn: P correspon a la impressió.

953
00:47:16,160 --> 00:47:19,310
I pel que s'està preguntant quina és la
diferència entre això i això?

954
00:47:19,310 --> 00:47:22,330
En aquest cas, res.

955
00:47:22,330 --> 00:47:26,960
Però generalment hi
algunes diferències.

956
00:47:26,960 --> 00:47:28,220
I vostè ha de buscar en el manual d'GDB.

957
00:47:28,220 --> 00:47:29,560
Però en aquest cas, res.

958
00:47:29,560 --> 00:47:31,460
Tenim la tendència a utilitzar la impressió, però, perquè
nosaltres no hem de fer molt més que

959
00:47:31,460 --> 00:47:33,960
imprimir un sol valor.

960
00:47:33,960 --> 00:47:34,640
>> D'acord.

961
00:47:34,640 --> 00:47:40,300
Així que estem en la línia 80 del nostre codi,
establint node * curr igual a llista.

962
00:47:40,300 --> 00:47:42,500
Anem a imprimim curr.

963
00:47:42,500 --> 00:47:45,260

964
00:47:45,260 --> 00:47:46,840
És igual a la llista.

965
00:47:46,840 --> 00:47:48,850
Sweet.

966
00:47:48,850 --> 00:47:49,340
Esperi.

967
00:47:49,340 --> 00:47:50,590
És igual a alguna cosa.

968
00:47:50,590 --> 00:47:53,680

969
00:47:53,680 --> 00:47:56,190
Això no em sembla correcte.

970
00:47:56,190 --> 00:47:56,840
Això és.

971
00:47:56,840 --> 00:47:59,470
És perquè en GDB, bé, si
que és la línia que està en ell

972
00:47:59,470 --> 00:48:00,330
encara no s'ha executat.

973
00:48:00,330 --> 00:48:03,100
Així que cal escriure en realitat
següent per executar la línia de

974
00:48:03,100 --> 00:48:05,230
abans de veure els resultats.

975
00:48:05,230 --> 00:48:06,680
Així que aquí estem.

976
00:48:06,680 --> 00:48:09,490
Simplement executa aquesta línia,
anterior equival a nul · la.

977
00:48:09,490 --> 00:48:13,590
Així que de nou, si imprimim anterior
no veurem res estrany.

978
00:48:13,590 --> 00:48:18,680
Però si realment executen a què
línia, llavors veurem

979
00:48:18,680 --> 00:48:20,380
que aquesta línia va funcionar.

980
00:48:20,380 --> 00:48:21,060
>> Així que tenim curr.

981
00:48:21,060 --> 00:48:23,180
Aquests són els dos bons.

982
00:48:23,180 --> 00:48:24,010
Cert?

983
00:48:24,010 --> 00:48:28,130
Ara estem en aquesta línia aquí.

984
00:48:28,130 --> 00:48:29,310
Mentre curr no és igual a nul.

985
00:48:29,310 --> 00:48:31,110
Bé, el que fa curr iguals?

986
00:48:31,110 --> 00:48:32,450
Acabem de veure que va igualar nul.

987
00:48:32,450 --> 00:48:33,210
Imprimim a terme.

988
00:48:33,210 --> 00:48:35,110
Vaig a imprimir cap fos una altra vegada.

989
00:48:35,110 --> 00:48:36,720
Així és que mentre que bucle
va a executar?

990
00:48:36,720 --> 00:48:37,270
>> AUDIÈNCIA: No

991
00:48:37,270 --> 00:48:39,790
>> JASON Hirschhorn: Així que quan he escrit que
línia, veurà que va saltar tot el camí

992
00:48:39,790 --> 00:48:41,390
fins a la part inferior, tornarà false.

993
00:48:41,390 --> 00:48:44,520
I després anem a tornar false
i tornar al nostre programa i

994
00:48:44,520 --> 00:48:48,020
finalment, imprimir, com hem vist,
l'insert no va tenir èxit.

995
00:48:48,020 --> 00:48:51,010
Per tant, ningú té alguna idea sobre el que
que hem de fer per arreglar això?

996
00:48:51,010 --> 00:48:54,200

997
00:48:54,200 --> 00:48:57,570
Vaig a esperar fins que vegi
un parell de mans pugen.

998
00:48:57,570 --> 00:48:58,830
No executem això.

999
00:48:58,830 --> 00:49:01,660
Tingueu en compte que aquesta va ser la primera
El que estàvem fent.

1000
00:49:01,660 --> 00:49:02,430
Jo no faré un parell.

1001
00:49:02,430 --> 00:49:03,670
Vaig a fer alguns.

1002
00:49:03,670 --> 00:49:04,830
Com que un parell significa dues.

1003
00:49:04,830 --> 00:49:07,620
Vaig a esperar per més de dos.

1004
00:49:07,620 --> 00:49:10,690
>> La primera inserció, corr,
per defecte és igual a nul.

1005
00:49:10,690 --> 00:49:14,050
I aquest cicle només s'executa
si curr no és nul.

1006
00:49:14,050 --> 00:49:18,740
Llavors, com puc solucionar això?

1007
00:49:18,740 --> 00:49:19,990
Veig 3 mans.

1008
00:49:19,990 --> 00:49:28,490

1009
00:49:28,490 --> 00:49:29,780
Vaig a esperar per més de tres.

1010
00:49:29,780 --> 00:49:33,460

1011
00:49:33,460 --> 00:49:35,940
Marcus, què et sembla?

1012
00:49:35,940 --> 00:49:37,730
>> AUDIÈNCIA: Bé, si vostè ho necessita
executar més d'una vegada, només

1013
00:49:37,730 --> 00:49:39,948
canviar-ho a un bucle do-while.

1014
00:49:39,948 --> 00:49:41,250
>> JASON Hirschhorn: OK.

1015
00:49:41,250 --> 00:49:44,240
Serà que resoldre el nostre problema, però?

1016
00:49:44,240 --> 00:49:47,750
>> AUDIÈNCIA: En aquest cas no, perquè de
el fet que la llista és buida.

1017
00:49:47,750 --> 00:49:52,150
Així que és probable que només necessita afegir
una declaració que si se surt del bucle

1018
00:49:52,150 --> 00:49:55,312
llavors vostè ha d'estar al final de la
la llista, moment en què vostè

1019
00:49:55,312 --> 00:49:56,562
només pot inserir.

1020
00:49:56,562 --> 00:49:58,920

1021
00:49:58,920 --> 00:49:59,680
>> JASON Hirschhorn: això m'agrada.

1022
00:49:59,680 --> 00:50:00,500
Això té sentit.

1023
00:50:00,500 --> 00:50:03,390
Si se surt del bucle -

1024
00:50:03,390 --> 00:50:04,800
perquè va a tornar false aquí.

1025
00:50:04,800 --> 00:50:08,220
Així que si se surt del bucle, llavors estem en
Al final de la llista, o potser el

1026
00:50:08,220 --> 00:50:10,690
inici d'una llista si no hi ha res a
, El que és el mateix que el final.

1027
00:50:10,690 --> 00:50:12,770
Així que ara volem inserir
alguna cosa aquí.

1028
00:50:12,770 --> 00:50:17,380
Llavors, com aquest codi mira, Marcus?

1029
00:50:17,380 --> 00:50:21,600
>> AUDIÈNCIA: Si ja tens el node
malloced, podeu dir

1030
00:50:21,600 --> 00:50:25,400
new_node-> següent és igual a nul · la perquè
ha de ser al final.

1031
00:50:25,400 --> 00:50:27,510
O new_node-> següent és igual a nul.

1032
00:50:27,510 --> 00:50:27,765
>> JASON Hirschhorn: OK.

1033
00:50:27,765 --> 00:50:28,190
Ho sento.

1034
00:50:28,190 --> 00:50:35,760
New_node-> següent és igual a nul
perquè estem al final.

1035
00:50:35,760 --> 00:50:36,460
Això no ho va posar polz

1036
00:50:36,460 --> 00:50:37,710
Com ens posem a la llista?

1037
00:50:37,710 --> 00:50:46,130

1038
00:50:46,130 --> 00:50:46,460
Dreta.

1039
00:50:46,460 --> 00:50:47,750
Això és només la creació és igual a.

1040
00:50:47,750 --> 00:50:50,940
No, com en realitat
el va posar a la llista?

1041
00:50:50,940 --> 00:50:54,170
El que apunta a la
final de la llista?

1042
00:50:54,170 --> 00:50:56,090
>> AUDIÈNCIA: Head.

1043
00:50:56,090 --> 00:50:57,566
>> JASON Hirschhorn: Ho sents?

1044
00:50:57,566 --> 00:50:59,440
>> AUDIÈNCIA: Head està apuntant
al final de la llista.

1045
00:50:59,440 --> 00:51:01,480
>> JASON Hirschhorn: Si no hi ha res a
la llista, el cap està apuntant a la

1046
00:51:01,480 --> 00:51:04,170
final de la llista.

1047
00:51:04,170 --> 00:51:06,920
Així que això funcionarà per a la
primera inserció.

1048
00:51:06,920 --> 00:51:09,810
Què passa si hi ha un parell
les coses a la llista?

1049
00:51:09,810 --> 00:51:12,470
Que no volem establir
cap igual a new_node.

1050
00:51:12,470 --> 00:51:13,790
Què és el que volem fer allà?

1051
00:51:13,790 --> 00:51:15,610
Sí?

1052
00:51:15,610 --> 00:51:16,860
Probablement anterior.

1053
00:51:16,860 --> 00:51:23,560

1054
00:51:23,560 --> 00:51:24,810
Funcionarà?

1055
00:51:24,810 --> 00:51:28,950

1056
00:51:28,950 --> 00:51:33,050
Recordem que anterior és només
un punter a un node.

1057
00:51:33,050 --> 00:51:34,770
I anterior és una variable local.

1058
00:51:34,770 --> 00:51:38,080
Així que aquesta línia crearà una variable local,
anterior, igual o

1059
00:51:38,080 --> 00:51:39,380
assenyalant a aquest nou node.

1060
00:51:39,380 --> 00:51:41,500
Això no posarà realment es
a la llista, però.

1061
00:51:41,500 --> 00:51:44,330
Com ens posem en la nostra llista?

1062
00:51:44,330 --> 00:51:45,620
Akchar?

1063
00:51:45,620 --> 00:51:46,870
>> AUDIÈNCIA: Crec que
fer actual-> següent.

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-> següent.

1067
00:51:54,010 --> 00:51:58,768
Així que de nou, l'única raó per la qual estem sota
aquí és el que fa de corrent igual?

1068
00:51:58,768 --> 00:51:59,760
>> AUDIÈNCIA: igual a nul.

1069
00:51:59,760 --> 00:52:01,790
>> JASON Hirschhorn: I així ho
que passa si ho fem nul-> next?

1070
00:52:01,790 --> 00:52:02,810
Què aconseguirà?

1071
00:52:02,810 --> 00:52:04,060
Aconseguirem una fallada de segmentació.

1072
00:52:04,060 --> 00:52:06,600

1073
00:52:06,600 --> 00:52:08,880
>> AUDIÈNCIA: Do curr equival a nul · la.

1074
00:52:08,880 --> 00:52:10,760
>> JASON Hirschhorn: Això és el mateix
com anterior, però, perquè no hi ha

1075
00:52:10,760 --> 00:52:12,820
una variable local que estem establint
igual a aquest nou node.

1076
00:52:12,820 --> 00:52:16,680

1077
00:52:16,680 --> 00:52:20,920
Tornem a la nostra imatge
d'inserir alguna cosa.

1078
00:52:20,920 --> 00:52:25,500
Diguem que estem inserint al final
de la llista, pel que aquí.

1079
00:52:25,500 --> 00:52:30,010
Tenim un punter actual que és
apuntant a null i un punt anterior

1080
00:52:30,010 --> 00:52:32,800
això apunta a 8.

1081
00:52:32,800 --> 00:52:35,330
Llavors, què hem de actualitzar, Avi?

1082
00:52:35,330 --> 00:52:36,680
>> AUDIÈNCIA: Anterior-> següent?

1083
00:52:36,680 --> 00:52:41,980
>> JASON Hirschhorn: Anterior-> següent és el que
volem posar al dia causa que

1084
00:52:41,980 --> 00:52:44,960
en realitat s'insereix en
al final de la llista.

1085
00:52:44,960 --> 00:52:47,220
Encara tenim una bestiola, però,
que anem a executar en.

1086
00:52:47,220 --> 00:52:50,090
Què és aquest bitxo?

1087
00:52:50,090 --> 00:52:50,790
Sí?

1088
00:52:50,790 --> 00:52:53,860
>> AUDIÈNCIA: Es va a tornar
falsa en aquest cas?

1089
00:52:53,860 --> 00:52:56,380
>> JASON Hirschhorn: Oh, és que
tornarà false.

1090
00:52:56,380 --> 00:52:57,430
Però hi ha un altre error.

1091
00:52:57,430 --> 00:52:58,930
Així que haurem de posar a canvi veritable.

1092
00:52:58,930 --> 00:53:01,370
>> AUDIÈNCIA: Això segueix igual
nul en la part superior de la llista?

1093
00:53:01,370 --> 00:53:03,645
>> JASON Hirschhorn: Encara Així anterior
és igual a nul des del principi.

1094
00:53:03,645 --> 00:53:07,480

1095
00:53:07,480 --> 00:53:10,440
Llavors, com podem superar això?

1096
00:53:10,440 --> 00:53:10,950
Sí?

1097
00:53:10,950 --> 00:53:15,280
>> AUDIÈNCIA: Crec que es pot fer una verificació
abans que el bucle while per veure si és

1098
00:53:15,280 --> 00:53:16,610
una llista buida.

1099
00:53:16,610 --> 00:53:17,000
>> JASON Hirschhorn: OK.

1100
00:53:17,000 --> 00:53:17,710
Així que anirem aquí.

1101
00:53:17,710 --> 00:53:18,530
Feu una revisió.

1102
00:53:18,530 --> 00:53:19,380
Si -

1103
00:53:19,380 --> 00:53:20,770
>> AUDIÈNCIA: Així que si el cap
és igual a és igual a nul.

1104
00:53:20,770 --> 00:53:24,300

1105
00:53:24,300 --> 00:53:26,320
>> JASON Hirschhorn: Si el cap
és igual a és igual a nul · -

1106
00:53:26,320 --> 00:53:27,790
que ens dirà si es tracta d'una llista buida.

1107
00:53:27,790 --> 00:53:31,090
>> AUDIÈNCIA: I llavors vostè
fer el cap és igual a nou.

1108
00:53:31,090 --> 00:53:34,740
>> JASON Hirschhorn: Head
iguals new_node?

1109
00:53:34,740 --> 00:53:35,730
I què més hem de fer?

1110
00:53:35,730 --> 00:53:37,020
>> AUDIÈNCIA: I després pot tornar realitat.

1111
00:53:37,020 --> 00:53:37,535
>> JASON Hirschhorn: No del tot.

1112
00:53:37,535 --> 00:53:38,785
Ens cal un pas.

1113
00:53:38,785 --> 00:53:41,590

1114
00:53:41,590 --> 00:53:43,710
>> AUDIÈNCIA: New_node següent
ha d'apuntar a null.

1115
00:53:43,710 --> 00:53:44,570
>> JASON Hirschhorn: Exactament, Alden.

1116
00:53:44,570 --> 00:53:46,600
I llavors podem tornar true.

1117
00:53:46,600 --> 00:53:47,560
D'acord.

1118
00:53:47,560 --> 00:53:51,630
Però segueix sent una bona idea de fer les coses
al final de la llista, no?

1119
00:53:51,630 --> 00:53:51,950
Està bé.

1120
00:53:51,950 --> 00:53:54,450
Encara podríem aconseguir realment
al final de la llista.

1121
00:53:54,450 --> 00:53:57,870
Així és aquest codi bé si estem en el
final de la llista i hi ha alguns

1122
00:53:57,870 --> 00:53:59,120
les coses a la llista?

1123
00:53:59,120 --> 00:54:01,830

1124
00:54:01,830 --> 00:54:02,040
Cert?

1125
00:54:02,040 --> 00:54:03,540
Com que encara tenim idea de Marcus.

1126
00:54:03,540 --> 00:54:06,870
Podem sortir d'aquest bucle, perquè
estem en el final de la llista.

1127
00:54:06,870 --> 00:54:09,308
Llavors, encara volem aquest
codi ací baix?

1128
00:54:09,308 --> 00:54:10,520
>> AUDIÈNCIA: Si.

1129
00:54:10,520 --> 00:54:11,000
>> JASON Hirschhorn: Si.

1130
00:54:11,000 --> 00:54:14,190
I què és el que hem de canviar això?

1131
00:54:14,190 --> 00:54:15,440
Veritable.

1132
00:54:15,440 --> 00:54:19,580

1133
00:54:19,580 --> 00:54:21,640
¿Sona bé
a tothom fins al moment?

1134
00:54:21,640 --> 00:54:22,420
Algú té alguna -

1135
00:54:22,420 --> 00:54:23,480
Avi, Tens alguna cosa que afegir?

1136
00:54:23,480 --> 00:54:23,920
>> AUDIÈNCIA: No

1137
00:54:23,920 --> 00:54:25,276
>> JASON Hirschhorn: OK.

1138
00:54:25,276 --> 00:54:27,010
Així que hem fet un parell de canvis.

1139
00:54:27,010 --> 00:54:29,540
Hem fet aquesta comprovació abans que
vam per a una llista buida.

1140
00:54:29,540 --> 00:54:31,790
Així que ens hem ocupat d'una llista buida.

1141
00:54:31,790 --> 00:54:35,500
I aquí ens ocupem de la inserció
a final de la llista.

1142
00:54:35,500 --> 00:54:38,930
Així que sembla que aquesta presa de bucle while
cura de les coses en el medi,

1143
00:54:38,930 --> 00:54:41,920
en algun lloc de la llista si hi ha
són les coses a la llista.

1144
00:54:41,920 --> 00:54:42,280
>> D'acord.

1145
00:54:42,280 --> 00:54:44,310
Correm aquest programa de nou.

1146
00:54:44,310 --> 00:54:50,170

1147
00:54:50,170 --> 00:54:50,755
No èxit.

1148
00:54:50,755 --> 00:54:52,190
>> AUDIÈNCIA: No ho fan.

1149
00:54:52,190 --> 00:54:53,940
>> JASON Hirschhorn: Oh,
Jo no ho vaig fer.

1150
00:54:53,940 --> 00:54:56,250
Bon punt, Michael.

1151
00:54:56,250 --> 00:54:57,500
Anem a afegir una marca vinculada.

1152
00:54:57,500 --> 00:55:01,590

1153
00:55:01,590 --> 00:55:04,830
Línia 87 hi ha un error.

1154
00:55:04,830 --> 00:55:05,420
Línia 87.

1155
00:55:05,420 --> 00:55:06,600
Alden, aquesta va ser la línia que em vas donar.

1156
00:55:06,600 --> 00:55:08,962
Què passa?

1157
00:55:08,962 --> 00:55:10,710
>> AUDIÈNCIA: Ha de ser null.

1158
00:55:10,710 --> 00:55:11,000
>> JASON Hirschhorn: Excel · lent.

1159
00:55:11,000 --> 00:55:11,630
Exactament dreta.

1160
00:55:11,630 --> 00:55:13,290
Ha de ser nul.

1161
00:55:13,290 --> 00:55:15,210
Anem a fer de nou.

1162
00:55:15,210 --> 00:55:17,220
Compilació.

1163
00:55:17,220 --> 00:55:17,890
D'acord.

1164
00:55:17,890 --> 00:55:19,400
Anem a inserir 03:00.

1165
00:55:19,400 --> 00:55:20,570
L'insert va ser reeixida.

1166
00:55:20,570 --> 00:55:21,660
Anem a imprimir cap a fora.

1167
00:55:21,660 --> 00:55:23,590
Oh, si tan sols poguéssim comprovar.

1168
00:55:23,590 --> 00:55:25,500
Però no hem fet el
imprimir funció encara.

1169
00:55:25,500 --> 00:55:27,840
Ens endinsarem en una altra cosa.

1170
00:55:27,840 --> 00:55:29,090
Què hem d'entrar?

1171
00:55:29,090 --> 00:55:31,120

1172
00:55:31,120 --> 00:55:31,940
>> AUDIÈNCIA: Set.

1173
00:55:31,940 --> 00:55:33,340
>> JASON Hirschhorn: Seven?

1174
00:55:33,340 --> 00:55:34,590
>> AUDIÈNCIA: Si.

1175
00:55:34,590 --> 00:55:38,680

1176
00:55:38,680 --> 00:55:39,780
>> JASON Hirschhorn: Tenim una falla seg.

1177
00:55:39,780 --> 00:55:43,760
Així que ens van donar una, però clarament
no pot aconseguir dues.

1178
00:55:43,760 --> 00:55:45,690
És 05:07.

1179
00:55:45,690 --> 00:55:48,370
Així que podem depurar aquest
durant tres minuts.

1180
00:55:48,370 --> 00:55:51,240
Però jo vaig a deixar-nos aquí
i passar a taules hash.

1181
00:55:51,240 --> 00:55:54,290
Però, de nou, les respostes d'aquest codi
Vaig a enviar per correu electrònic a vostè en un moment.

1182
00:55:54,290 --> 00:55:55,440
Estem molt a prop d'ella.

1183
00:55:55,440 --> 00:55:58,300
Jo us animo a descobrir
Què està passant aquí i arreglar-ho.

1184
00:55:58,300 --> 00:56:02,400
Així que vaig a per correu electrònic aquest codi com
així més la solució -

1185
00:56:02,400 --> 00:56:03,670
probablement la solució més endavant.

1186
00:56:03,670 --> 00:56:05,110
En primer lloc aquest codi.

1187
00:56:05,110 --> 00:56:08,290
>> L'altra cosa que vull fer abans que
final és que no hem alliberat a res.

1188
00:56:08,290 --> 00:56:10,370
Així que vull que li mostri el
valgrind sembla.

1189
00:56:10,370 --> 00:56:14,310
Si correm límits valgrind
en el nostre programa. / enllaçat.

1190
00:56:14,310 --> 00:56:22,540
Un cop més, d'acord amb aquesta diapositiva, ens
ha d'executar valgrind amb algun tipus de

1191
00:56:22,540 --> 00:56:26,410
opció, en aquest cas
- Fuga-check = full.

1192
00:56:26,410 --> 00:56:27,660
Així que anem a escriure valgrind
- Fuga-check = full.

1193
00:56:27,660 --> 00:56:31,910

1194
00:56:31,910 --> 00:56:35,080
Així que això funcionarà valgrind
en el nostre programa.

1195
00:56:35,080 --> 00:56:37,000
I ara el programa realment funciona.

1196
00:56:37,000 --> 00:56:40,190
Així que anem a executar com
abans, posar una mica polz

1197
00:56:40,190 --> 00:56:40,830
Em vaig a posar en tres.

1198
00:56:40,830 --> 00:56:41,790
Això funciona.

1199
00:56:41,790 --> 00:56:43,202
No vaig a tractar de posar en alguna cosa
més perquè anem a

1200
00:56:43,202 --> 00:56:44,710
aconseguir un fals segons en aquest cas.

1201
00:56:44,710 --> 00:56:46,700
Així que només vaig a deixar de fumar.

1202
00:56:46,700 --> 00:56:50,160
>> I ara que es veu aquí sota
fuites i resum munt.

1203
00:56:50,160 --> 00:56:52,310
Aquestes són les coses bones que
voleu comprovar.

1204
00:56:52,310 --> 00:56:56,780
Així que el resum del munt - diu, en ús
a la sortida - 08:00 bytes en un bloc.

1205
00:56:56,780 --> 00:56:58,370
Aquest bloc és el
node que malloced.

1206
00:56:58,370 --> 00:57:02,230
Michael, va dir abans d'un node és de vuit
picades perquè té el número sencer

1207
00:57:02,230 --> 00:57:02,680
i el punter.

1208
00:57:02,680 --> 00:57:04,550
Així que aquest és el nostre node.

1209
00:57:04,550 --> 00:57:08,170
I després diu que fem servir malloc
set vegades i ens alliberem

1210
00:57:08,170 --> 00:57:08,940
alguna cosa en sis ocasions.

1211
00:57:08,940 --> 00:57:13,680
Però mai es diu lliure, així que no tinc
idea del que està parlant.

1212
00:57:13,680 --> 00:57:18,490
>> Però només cal dir que quan el seu
programa s'executa, malloc s'està cridant

1213
00:57:18,490 --> 00:57:20,330
en alguns altres llocs que
no cal preocupar-se.

1214
00:57:20,330 --> 00:57:22,460
Així malloc probablement va ser anomenat
en alguns llocs.

1215
00:57:22,460 --> 00:57:24,480
Nosaltres no hem de preocupar on.

1216
00:57:24,480 --> 00:57:26,240
Però això és realment nosaltres.

1217
00:57:26,240 --> 00:57:27,380
Aquesta primera línia és nosaltres.

1218
00:57:27,380 --> 00:57:28,320
Sortim d'aquest bloc.

1219
00:57:28,320 --> 00:57:30,330
I es pot veure que aquí
en el resum de fuites.

1220
00:57:30,330 --> 00:57:31,950
Encara assolible -

1221
00:57:31,950 --> 00:57:32,930
08:00 bytes en un bloc.

1222
00:57:32,930 --> 00:57:34,100
Això vol dir que la memòria -

1223
00:57:34,100 --> 00:57:35,730
hem escapat aquest record.

1224
00:57:35,730 --> 00:57:37,570
Definitivament perdut -

1225
00:57:37,570 --> 00:57:38,770
alguna cosa es perd per sempre.

1226
00:57:38,770 --> 00:57:40,590
En general, no ho faràs
veure res allà.

1227
00:57:40,590 --> 00:57:44,780
Encara pot arribar és generalment on
veuràs les coses, on voldrà

1228
00:57:44,780 --> 00:57:48,900
de mirar per veure quin codi ha de vostè
s'han alliberat però es va oblidar d'alliberar.

1229
00:57:48,900 --> 00:57:53,170
>> I després, si aquest no era el cas,
si ho féssim tot gratis,

1230
00:57:53,170 --> 00:57:54,360
podem comprovar això.

1231
00:57:54,360 --> 00:57:57,330
Anem a executar el programa
no posar en qualsevol cosa.

1232
00:57:57,330 --> 00:57:59,800
Vostè veurà aquí a ús en la sortida -

1233
00:57:59,800 --> 00:58:01,310
zero bytes en zero blocs.

1234
00:58:01,310 --> 00:58:06,310
Això vol dir que ja no tenia res
quan aquest programa es tanca.

1235
00:58:06,310 --> 00:58:12,090
Així que abans de donar volta a pset6, valgrind executar
i assegureu-vos que vostè no té

1236
00:58:12,090 --> 00:58:15,310
qualsevol pèrdues de memòria en el seu programa.

1237
00:58:15,310 --> 00:58:17,910
Si vostè té alguna pregunta amb valgrind,
no dubti en apropar-se.

1238
00:58:17,910 --> 00:58:18,700
Però això és com ho fa servir.

1239
00:58:18,700 --> 00:58:20,890
Molt senzill - si vostè
tenir en ús a la sortida -

1240
00:58:20,890 --> 00:58:22,270
qualsevol byte en qualsevol bloc.

1241
00:58:22,270 --> 00:58:27,890

1242
00:58:27,890 --> 00:58:29,580
>> Així que estàvem treballant en el node d'inserció.

1243
00:58:29,580 --> 00:58:33,840
Tenia dues funcions aquí -
imprimir els nodes i els nodes lliures.

1244
00:58:33,840 --> 00:58:37,780
Una vegada més, es tracta de funcions que són
serà bo perquè practiquis

1245
00:58:37,780 --> 00:58:40,990
ja que l'ajudarà no només amb
aquests exercicis de mostra, sinó també

1246
00:58:40,990 --> 00:58:42,180
en el conjunt de problemes.

1247
00:58:42,180 --> 00:58:44,230
Es corresponen en molt de prop a les coses
vostè va a haver de fer al

1248
00:58:44,230 --> 00:58:45,010
estableix problema.

1249
00:58:45,010 --> 00:58:47,640
Però jo vull estar segur
Toquem tot.

1250
00:58:47,640 --> 00:58:50,400
I les taules hash també són crucials per
el que estem fent a la secció d'aquest

1251
00:58:50,400 --> 00:58:51,980
setmana - o en el conjunt de problemes.

1252
00:58:51,980 --> 00:58:55,200
>> Així que anem a acabar la secció
parlant de les taules hash.

1253
00:58:55,200 --> 00:58:58,140
Si vostè nota que vaig fer una
petita taula hash.

1254
00:58:58,140 --> 00:59:00,020
Això no és el que estem parlant
sobre, però.

1255
00:59:00,020 --> 00:59:03,540
Estem parlant d'un diferent
tipus de taules hash.

1256
00:59:03,540 --> 00:59:07,300
I en el fons, una taula hash
no és més que una

1257
00:59:07,300 --> 00:59:08,860
gamma més una funció hash.

1258
00:59:08,860 --> 00:59:11,150
Anem a parlar una mica només per
assegureu-vos que tothom entén el que és un

1259
00:59:11,150 --> 00:59:12,110
funció hash és.

1260
00:59:12,110 --> 00:59:15,420
I et dic ara que és
res més que dues coses -

1261
00:59:15,420 --> 00:59:18,590
una matriu i una funció hash.

1262
00:59:18,590 --> 00:59:20,716
I aquests són els passos a través de
que aquesta opera.

1263
00:59:20,716 --> 00:59:31,560

1264
00:59:31,560 --> 00:59:32,810
>> Aquí està la nostra matriu.

1265
00:59:32,810 --> 00:59:38,460

1266
00:59:38,460 --> 00:59:39,460
Aquí està la nostra funció.

1267
00:59:39,460 --> 00:59:43,180
En particular, les funcions de hash necessiten
fer un parell de coses amb això.

1268
00:59:43,180 --> 00:59:45,040
Vaig a parlar específicament
sobre estableix aquest problema.

1269
00:59:45,040 --> 00:59:46,450
Probablement va a
prendre en una cadena.

1270
00:59:46,450 --> 00:59:50,570

1271
00:59:50,570 --> 00:59:51,770
I què tornarà?

1272
00:59:51,770 --> 00:59:52,640
Quin tipus de dades?

1273
00:59:52,640 --> 00:59:54,260
Alden?

1274
00:59:54,260 --> 00:59:55,760
Retorni la seva funció hash?

1275
00:59:55,760 --> 00:59:58,760
Un sencer.

1276
00:59:58,760 --> 01:00:01,700
Així que això és el que el hash
taula consta de -

1277
01:00:01,700 --> 01:00:05,430
una taula en forma de matriu
i una funció de hash.

1278
01:00:05,430 --> 01:00:06,010
Com funciona?

1279
01:00:06,010 --> 01:00:07,300
Funciona en tres passos.

1280
01:00:07,300 --> 01:00:08,740
Li donem una clau.

1281
01:00:08,740 --> 01:00:11,470
En aquest cas, anem a donar-li una cadena.

1282
01:00:11,470 --> 01:00:18,140
Cridem a la funció hash pel pas 1
a la clau i obtenim un valor.

1283
01:00:18,140 --> 01:00:20,310
>> En concret, direm
obtenim un nombre enter.

1284
01:00:20,310 --> 01:00:25,630
Aquest nombre enter, no són molt específics
límits al que pot ser sencer.

1285
01:00:25,630 --> 01:00:28,880
En aquest exemple, la nostra matriu
és de grandària 3.

1286
01:00:28,880 --> 01:00:32,330
Llavors, què números pot ser aquest sencer.

1287
01:00:32,330 --> 01:00:35,970
Quin és el rang de valors vàlids per
aquest sencer, el tipus de retorn d'aquesta

1288
01:00:35,970 --> 01:00:37,220
funció hash?

1289
01:00:37,220 --> 01:00:40,440

1290
01:00:40,440 --> 01:00:42,110
Zero, un i dos.

1291
01:00:42,110 --> 01:00:46,060
El punt de la funció hash és
esbrinar el lloc de la matriu

1292
01:00:46,060 --> 01:00:47,790
on la clau va.

1293
01:00:47,790 --> 01:00:51,290
Només hi ha tres possibles
llocs aquí -

1294
01:00:51,290 --> 01:00:52,130
zero, un, o dos.

1295
01:00:52,130 --> 01:00:55,360
Així que aquesta funció millor retorn
zero, un, o dos.

1296
01:00:55,360 --> 01:00:58,740
Alguns índex vàlida en aquest array.

1297
01:00:58,740 --> 01:01:02,770
>> I a continuació, depenent d'on torna,
es pot veure que hi ha antena oberta

1298
01:01:02,770 --> 01:01:03,730
entre parèntesis el valor.

1299
01:01:03,730 --> 01:01:05,800
Aquí és on posem la clau.

1300
01:01:05,800 --> 01:01:11,280
Així que tirem a la carabassa,
sortim zero.

1301
01:01:11,280 --> 01:01:15,540
En conjunt suport 0, posem carbassa.

1302
01:01:15,540 --> 01:01:21,070
Ens tirem en els gats, tenim a un.

1303
01:01:21,070 --> 01:01:24,110
Posem en un gat.

1304
01:01:24,110 --> 01:01:25,480
Posem a aranya.

1305
01:01:25,480 --> 01:01:26,710
Sortim 02:00.

1306
01:01:26,710 --> 01:01:30,200
Posem aranya en conjunt suport de dos.

1307
01:01:30,200 --> 01:01:32,300
Seria molt bo si
funcionar d'aquesta manera.

1308
01:01:32,300 --> 01:01:35,570
Però, per desgràcia, com veurem,
que és una mica més complicat.

1309
01:01:35,570 --> 01:01:37,570
>> Abans d'arribar-hi, qualsevol pregunta
sobre aquest bàsic

1310
01:01:37,570 --> 01:01:38,820
posada a punt d'una taula hash?

1311
01:01:38,820 --> 01:01:49,050

1312
01:01:49,050 --> 01:01:51,940
Aquesta és una imatge d'exactament
el que dibuixem al tauler.

1313
01:01:51,940 --> 01:01:55,420
Però ja ho dibuixem en el tauler, em
No vaig a entrar-hi encara més.

1314
01:01:55,420 --> 01:02:00,430
Essencialment, les claus, el quadre negre de màgia -
o en aquest cas, la caixa verd blavós - d'un

1315
01:02:00,430 --> 01:02:02,410
funció hash els posa en galledes.

1316
01:02:02,410 --> 01:02:04,690
I en aquest exemple estem
no posar el nom.

1317
01:02:04,690 --> 01:02:07,880
Estem posant el telèfon associat
nombre del nom al cub.

1318
01:02:07,880 --> 01:02:10,430
Però molt bé podria simplement
posar el nom al cub.

1319
01:02:10,430 --> 01:02:12,950
>> Això és només una imatge del que
dibuixem en el tauler.

1320
01:02:12,950 --> 01:02:14,460
Tenim dificultats potencials, però.

1321
01:02:14,460 --> 01:02:17,470
I hi ha dues en particular
Les diapositives que vull anar.

1322
01:02:17,470 --> 01:02:20,230
La primera d'elles és d'aproximadament
una funció hash.

1323
01:02:20,230 --> 01:02:22,620
Així que vaig fer la pregunta, què
fa una bona funció hash?

1324
01:02:22,620 --> 01:02:24,220
Li dono dues respostes.

1325
01:02:24,220 --> 01:02:26,630
La primera és que és determinista.

1326
01:02:26,630 --> 01:02:29,660
En el context de les funcions de hash,
Què vol dir això?

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
>> AUDIÈNCIA: Podeu trobar el
índex constant de temps?

1330
01:02:42,850 --> 01:02:43,810
>> JASON Hirschhorn: Que
no és el que significa.

1331
01:02:43,810 --> 01:02:44,725
Però això és una bona suposició.

1332
01:02:44,725 --> 01:02:46,100
Algú més té una conjectura
al que això significa?

1333
01:02:46,100 --> 01:02:47,780
Que una bona funció hash
és determinista?

1334
01:02:47,780 --> 01:02:48,280
Annie?

1335
01:02:48,280 --> 01:02:51,680
>> AUDIÈNCIA: Que una tecla només es pot assignar
a un lloc en la taula hash.

1336
01:02:51,680 --> 01:02:53,070
>> JASON Hirschhorn: Això és
exactament correcte.

1337
01:02:53,070 --> 01:02:57,430
Cada vegada que posa a la carbassa,
sempre torna zero.

1338
01:02:57,430 --> 01:03:01,660
Si vostè posa a la carbassa i l'haixix
la funció retorna zero, però té un

1339
01:03:01,660 --> 01:03:06,060
probabilitat de tornar alguna cosa
més gran que zero -

1340
01:03:06,060 --> 01:03:09,280
així que potser pot tornar un a vegades
o dues vegades -

1341
01:03:09,280 --> 01:03:11,100
això no és una bona funció hash.

1342
01:03:11,100 --> 01:03:11,800
Tens tota la raó.

1343
01:03:11,800 --> 01:03:15,680
La seva funció hash ha de tornar el
mateix nombre enter exacte, en aquest cas, per

1344
01:03:15,680 --> 01:03:17,780
la mateixa cadena exacta.

1345
01:03:17,780 --> 01:03:22,210
>> Potser retorna el mateix nombre enter exacte
per a la mateixa cadena exacta

1346
01:03:22,210 --> 01:03:24,430
independentment de la capitalització.

1347
01:03:24,430 --> 01:03:27,980
Però en aquest cas és encara
determinista perquè diverses coses

1348
01:03:27,980 --> 01:03:29,350
s'assignen en el mateix valor.

1349
01:03:29,350 --> 01:03:30,170
Això està bé.

1350
01:03:30,170 --> 01:03:32,615
Mentre que només hi ha una
de sortida per a una entrada donada.

1351
01:03:32,615 --> 01:03:35,630

1352
01:03:35,630 --> 01:03:36,350
>> D'acord.

1353
01:03:36,350 --> 01:03:38,340
La segona cosa és que
torna índexs vàlids.

1354
01:03:38,340 --> 01:03:40,220
Vam portar fins que abans.

1355
01:03:40,220 --> 01:03:41,860
Aquesta funció hash -

1356
01:03:41,860 --> 01:03:43,710
oh boy -

1357
01:03:43,710 --> 01:03:46,840
una funció hash ha de
tornar índexs vàlids.

1358
01:03:46,840 --> 01:03:47,740
Així ho diuen -

1359
01:03:47,740 --> 01:03:48,990
anem a tornar a aquest exemple.

1360
01:03:48,990 --> 01:03:52,580

1361
01:03:52,580 --> 01:03:57,540
La meva funció hash compte fins
les lletres de la paraula.

1362
01:03:57,540 --> 01:03:58,380
Aquesta és la funció hash.

1363
01:03:58,380 --> 01:03:59,740
I torna aquest sencer.

1364
01:03:59,740 --> 01:04:04,280
Així que si tinc la paraula A, és
tornarà un.

1365
01:04:04,280 --> 01:04:06,900
I es posarà una aquí.

1366
01:04:06,900 --> 01:04:09,430
Què passa si em poso en la paraula ratpenat?

1367
01:04:09,430 --> 01:04:11,310
Es va a tornar tres.

1368
01:04:11,310 --> 01:04:12,560
A on va ratpenat?

1369
01:04:12,560 --> 01:04:18,730

1370
01:04:18,730 --> 01:04:19,750
>> No encaixa.

1371
01:04:19,750 --> 01:04:21,000
Però ha d'anar a algun lloc.

1372
01:04:21,000 --> 01:04:23,340
Aquest és el meu taula hash després de tot, i
tot ha d'anar a algun lloc.

1373
01:04:23,340 --> 01:04:24,590
Llavors, on ha d'anar ratpenat?

1374
01:04:24,590 --> 01:04:28,020

1375
01:04:28,020 --> 01:04:28,710
Alguna idea?

1376
01:04:28,710 --> 01:04:29,450
Conjectures?

1377
01:04:29,450 --> 01:04:30,280
Les bones conjectures?

1378
01:04:30,280 --> 01:04:31,220
>> AUDIÈNCIA: Zero.

1379
01:04:31,220 --> 01:04:32,120
>> JASON Hirschhorn: Per què zero?

1380
01:04:32,120 --> 01:04:35,990
>> AUDIÈNCIA: Perquè tres
mòdul 3 és igual a zero?

1381
01:04:35,990 --> 01:04:38,620
>> JASON Hirschhorn: Triple
mòdul de tres és zero.

1382
01:04:38,620 --> 01:04:40,810
Aquesta és una gran suposició,
i això és correcte.

1383
01:04:40,810 --> 01:04:43,870
Així que en aquest cas s'ha de
Probablement vagi a zero.

1384
01:04:43,870 --> 01:04:51,080
Així que una bona manera d'assegurar que aquest hash
funció només retorna índexs vàlids es

1385
01:04:51,080 --> 01:04:54,580
al mòdul que per la mida de la taula.

1386
01:04:54,580 --> 01:04:57,360
Si Mòdul Sigui el torna per
tres, sempre es va a aconseguir

1387
01:04:57,360 --> 01:05:00,930
alguna cosa entre zero, un i dos.

1388
01:05:00,930 --> 01:05:05,160
I si això sempre torna 7, i
sempre Mòdul per tres, ets

1389
01:05:05,160 --> 01:05:06,030
sempre va a aconseguir el mateix.

1390
01:05:06,030 --> 01:05:09,270
>> Pel que és encara determinista
si MÒDUL.

1391
01:05:09,270 --> 01:05:11,420
Però això va a assegurar que vostè
mai aconseguir alguna cosa -

1392
01:05:11,420 --> 01:05:12,940
una indústria no vàlid.

1393
01:05:12,940 --> 01:05:16,840
Generalment, mòdul que hauria de passar
dins de la seva funció de hash.

1394
01:05:16,840 --> 01:05:18,240
Així que vostè no ha de preocupar-se per això.

1395
01:05:18,240 --> 01:05:20,555
Només assegurar-vos que
aquest és un índex vàlida.

1396
01:05:20,555 --> 01:05:23,700

1397
01:05:23,700 --> 01:05:26,700
Teniu alguna pregunta respecte aquest
potencial escull?

1398
01:05:26,700 --> 01:05:36,590

1399
01:05:36,590 --> 01:05:39,060
>> D'acord.

1400
01:05:39,060 --> 01:05:40,290
I aquí anem.

1401
01:05:40,290 --> 01:05:42,890
Següent error potencial i
aquesta és la gran.

1402
01:05:42,890 --> 01:05:46,880
Què passa si dues claus mapa
en el mateix valor?

1403
01:05:46,880 --> 01:05:49,350
Així que hi ha dues maneres de gestionar això.

1404
01:05:49,350 --> 01:05:53,140

1405
01:05:53,140 --> 01:05:56,020
La primera es diu lineal
sondeig, que estic

1406
01:05:56,020 --> 01:05:57,300
No vaig a anar una altra vegada.

1407
01:05:57,300 --> 01:06:01,120
Però vostè ha d'estar familiaritzat amb la forma
que funciona i el que és això.

1408
01:06:01,120 --> 01:06:05,610
>> El segon, vaig a anar més
ja que és el que molts

1409
01:06:05,610 --> 01:06:08,290
la gent probablement va a acabar de decidir
per utilitzar en el seu conjunt de problemes.

1410
01:06:08,290 --> 01:06:09,820
Per descomptat, vostè no ha de fer-ho.

1411
01:06:09,820 --> 01:06:15,280
No obstant això, per al conjunt de problemes, moltes persones
tendeixen a optar per crear una taula hash

1412
01:06:15,280 --> 01:06:17,950
amb encadenament separat per implementar
seu diccionari.

1413
01:06:17,950 --> 01:06:21,390
Així que anirem més del que significa
per crear una taula hash amb

1414
01:06:21,390 --> 01:06:23,890
encadenament separat.

1415
01:06:23,890 --> 01:06:26,260
>> Així que em vaig posar en carbassa.

1416
01:06:26,260 --> 01:06:29,560
Retorna zero.

1417
01:06:29,560 --> 01:06:31,410
I vaig posar carbassa aquí.

1418
01:06:31,410 --> 01:06:35,880

1419
01:06:35,880 --> 01:06:37,930
Llavors em vaig posar en -

1420
01:06:37,930 --> 01:06:39,922
el que és una altra cosa amb temes de Halloween?

1421
01:06:39,922 --> 01:06:42,200
>> AUDIÈNCIA: Candy.

1422
01:06:42,200 --> 01:06:42,770
>> JASON Hirschhorn: caramel!

1423
01:06:42,770 --> 01:06:43,910
Això és un gran un.

1424
01:06:43,910 --> 01:06:47,760
Vaig posar en els dolços i caramels
També em fa zero.

1425
01:06:47,760 --> 01:06:49,350
Què faig?

1426
01:06:49,350 --> 01:06:51,940
Alguna idea?

1427
01:06:51,940 --> 01:06:53,940
Com que tota la classe de sap
el encadenament separat és.

1428
01:06:53,940 --> 01:06:55,190
Així que qualsevol idea de què fer?

1429
01:06:55,190 --> 01:06:58,170

1430
01:06:58,170 --> 01:06:59,110
Sí

1431
01:06:59,110 --> 01:07:03,810
>> AUDIÈNCIA: Posar la cadena
realitat a la taula hash.

1432
01:07:03,810 --> 01:07:08,910
>> JASON Hirschhorn: Així que anem a
dibuixar la bona idea aquí.

1433
01:07:08,910 --> 01:07:09,340
D'acord.

1434
01:07:09,340 --> 01:07:12,290
>> AUDIÈNCIA: Tenir la taula hash
[Inaudible]

1435
01:07:12,290 --> 01:07:16,640
el punter que apunta a
el principi d'una llista.

1436
01:07:16,640 --> 01:07:20,930
I després han carbassa ser el primer valor
en aquesta llista i dolços vinculat ser

1437
01:07:20,930 --> 01:07:22,800
el segon valor en aquesta llista enllaçada.

1438
01:07:22,800 --> 01:07:23,420
>> JASON Hirschhorn: OK.

1439
01:07:23,420 --> 01:07:24,670
Marcus, que era excepcional.

1440
01:07:24,670 --> 01:07:26,160
Vaig a trencar això.

1441
01:07:26,160 --> 01:07:28,890
Marcus està dient que no
sobreescriure carbassa.

1442
01:07:28,890 --> 01:07:30,660
Això seria dolent.

1443
01:07:30,660 --> 01:07:33,640
No posar el caramel en un altre lloc.

1444
01:07:33,640 --> 01:07:35,390
Anem a posar a tots dos en zero.

1445
01:07:35,390 --> 01:07:37,770
Però anem a fer front a
posant-los a zero

1446
01:07:37,770 --> 01:07:39,395
la creació d'una llista en zero.

1447
01:07:39,395 --> 01:07:42,430
I anem a crear una llista de
tot el que s'assigna a zero.

1448
01:07:42,430 --> 01:07:47,960
I la millor manera que hem après per crear
una llista que pot créixer i encongir

1449
01:07:47,960 --> 01:07:49,840
dinàmica no està dins
una altra matriu.

1450
01:07:49,840 --> 01:07:51,510
Així que no és una matriu multidimensional.

1451
01:07:51,510 --> 01:07:54,080
Però n'hi ha prou amb crear una llista enllaçada.

1452
01:07:54,080 --> 01:07:55,330
>> Així que el que ell va proposar -

1453
01:07:55,330 --> 01:07:57,950

1454
01:07:57,950 --> 01:07:59,200
Vaig a aconseguir un nou -

1455
01:07:59,200 --> 01:08:15,380

1456
01:08:15,380 --> 01:08:19,689
és crear una matriu amb punters,
una matriu de punters.

1457
01:08:19,689 --> 01:08:20,580
D'acord.

1458
01:08:20,580 --> 01:08:24,180
Qualsevol idea o suggeriment del que el tipus de
d'aquests indicadors hauria de ser?

1459
01:08:24,180 --> 01:08:26,290
Marcus?

1460
01:08:26,290 --> 01:08:27,250
>> AUDIÈNCIA: Punters a -

1461
01:08:27,250 --> 01:08:28,609
>> JASON Hirschhorn: Com que vostè
va dir una llista enllaçada, així -

1462
01:08:28,609 --> 01:08:29,520
>> AUDIÈNCIA: punters de node?

1463
01:08:29,520 --> 01:08:30,670
>> JASON Hirschhorn: Punters de node.

1464
01:08:30,670 --> 01:08:32,830
Si les coses a la nostra vinculats
llista de nodes són llavors

1465
01:08:32,830 --> 01:08:34,370
ha de ser punters de node.

1466
01:08:34,370 --> 01:08:35,939
I què és el que equivalen a un principi?

1467
01:08:35,939 --> 01:08:36,990
>> AUDIÈNCIA: Nul.

1468
01:08:36,990 --> 01:08:38,240
>> JASON Hirschhorn: Nul.

1469
01:08:38,240 --> 01:08:44,540

1470
01:08:44,540 --> 01:08:46,080
Així que no és el nostre buit.

1471
01:08:46,080 --> 01:08:47,170
Torna carbassa zero.

1472
01:08:47,170 --> 01:08:48,569
Què fem?

1473
01:08:48,569 --> 01:08:49,609
Camina amb mi a través d'ell?

1474
01:08:49,609 --> 01:08:50,810
En realitat, Marcus ja em va donar.

1475
01:08:50,810 --> 01:08:52,439
Algú més em caminar a través d'ell.

1476
01:08:52,439 --> 01:08:54,760
Què fem quan -

1477
01:08:54,760 --> 01:08:56,609
això es veu molt similar a
el que estàvem fent.

1478
01:08:56,609 --> 01:08:57,396
Avi.

1479
01:08:57,396 --> 01:08:59,090
>> AUDIÈNCIA: Me'n vaig a prendre una conjectura.

1480
01:08:59,090 --> 01:09:01,250
Així que quan vostè aconsegueix el caramel.

1481
01:09:01,250 --> 01:09:01,640
>> JASON Hirschhorn: Si.

1482
01:09:01,640 --> 01:09:03,120
Bé, tenim carbassa.

1483
01:09:03,120 --> 01:09:03,870
Anem a la nostra primera.

1484
01:09:03,870 --> 01:09:04,324
Tenim carbassa.

1485
01:09:04,324 --> 01:09:04,779
>> AUDIÈNCIA: OK.

1486
01:09:04,779 --> 01:09:05,880
Torna carbassa zero.

1487
01:09:05,880 --> 01:09:08,770
Així ho poses en això.

1488
01:09:08,770 --> 01:09:10,810
O en realitat, el poses
en la llista enllaçada.

1489
01:09:10,810 --> 01:09:13,550
>> JASON Hirschhorn: Com
el va posar a la llista enllaçada?

1490
01:09:13,550 --> 01:09:15,479
>> AUDIÈNCIA: Oh, la sintaxi actual?

1491
01:09:15,479 --> 01:09:16,240
>> JASON Hirschhorn: Només cal passar -

1492
01:09:16,240 --> 01:09:16,740
dir més.

1493
01:09:16,740 --> 01:09:19,310
Què fem?

1494
01:09:19,310 --> 01:09:22,100
>> AUDIÈNCIA: Només cal inserir
com el primer node.

1495
01:09:22,100 --> 01:09:22,675
>> JASON Hirschhorn: OK.

1496
01:09:22,675 --> 01:09:29,069
Així que tenim el nostre node, carbassa.

1497
01:09:29,069 --> 01:09:31,560
I ara com ho introdueixo?

1498
01:09:31,560 --> 01:09:34,590

1499
01:09:34,590 --> 01:09:37,090
>> AUDIÈNCIA: Vostè assigna
en el punter.

1500
01:09:37,090 --> 01:09:37,970
>> JASON Hirschhorn: Què punter?

1501
01:09:37,970 --> 01:09:39,620
>> AUDIÈNCIA: L'indicador en zero.

1502
01:09:39,620 --> 01:09:41,420
>> JASON Hirschhorn: Llavors, on
fa aquest punt?

1503
01:09:41,420 --> 01:09:42,810
>> AUDIÈNCIA: Per nul en aquests moments.

1504
01:09:42,810 --> 01:09:43,529
>> JASON Hirschhorn: Bé,
està apuntant a null.

1505
01:09:43,529 --> 01:09:44,499
Però em vaig a posar a la carabassa.

1506
01:09:44,499 --> 01:09:46,053
Llavors, on hauria d'apuntar?

1507
01:09:46,053 --> 01:09:46,880
>> AUDIÈNCIA: Per carbassa.

1508
01:09:46,880 --> 01:09:47,399
>> JASON Hirschhorn: Per carbassa.

1509
01:09:47,399 --> 01:09:48,760
Exactament.

1510
01:09:48,760 --> 01:09:50,010
Així que això apunta a la carabassa.

1511
01:09:50,010 --> 01:09:52,500

1512
01:09:52,500 --> 01:09:54,250
I d'on ve aquest punter
en el punt de carbassa?

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
>> AUDIÈNCIA: Nul.

1516
01:09:58,590 --> 01:09:59,210
>> JASON Hirschhorn: null.

1517
01:09:59,210 --> 01:10:00,460
Exactament.

1518
01:10:00,460 --> 01:10:03,570

1519
01:10:03,570 --> 01:10:05,140
Així que només ens inserim una mica
a la llista enllaçada.

1520
01:10:05,140 --> 01:10:07,210
Acabem d'escriure el codi per fer això.

1521
01:10:07,210 --> 01:10:09,520
Gairebé gairebé ens ho
completament esquerdat.

1522
01:10:09,520 --> 01:10:10,790
Ara inserim el caramel.

1523
01:10:10,790 --> 01:10:13,480
El nostre dolços també tendeix a zero.

1524
01:10:13,480 --> 01:10:16,100
Llavors, què fem amb els dolços?

1525
01:10:16,100 --> 01:10:18,790
>> AUDIÈNCIA: Depèn de si
No estem tractant de resoldre.

1526
01:10:18,790 --> 01:10:19,640
>> JASON Hirschhorn: Això és
exactament correcte.

1527
01:10:19,640 --> 01:10:21,070
Depèn de si és o no
que estem tractant de solucionar el problema.

1528
01:10:21,070 --> 01:10:22,660
Anem a suposar que no estem
solucionarà el problema.

1529
01:10:22,660 --> 01:10:24,880
>> AUDIÈNCIA: Doncs bé, com hem comentat
abans, és més senzill només per posar

1530
01:10:24,880 --> 01:10:28,590
des del principi de manera que el punter
de zero punts als dolços.

1531
01:10:28,590 --> 01:10:29,020
>> JASON Hirschhorn: OK.

1532
01:10:29,020 --> 01:10:29,380
Espera.

1533
01:10:29,380 --> 01:10:30,630
Déjame crear dolços aquí.

1534
01:10:30,630 --> 01:10:34,030

1535
01:10:34,030 --> 01:10:35,150
Així que aquest punter -

1536
01:10:35,150 --> 01:10:37,590
>> AUDIÈNCIA: Sí, ara ha
apuntar als dolços.

1537
01:10:37,590 --> 01:10:40,580
Després que el punter de
punt de caramel per a la carabassa.

1538
01:10:40,580 --> 01:10:43,140

1539
01:10:43,140 --> 01:10:44,560
>> JASON Hirschhorn: Així?

1540
01:10:44,560 --> 01:10:47,380
I diem que tenim una altra
cosa per assignar a zero?

1541
01:10:47,380 --> 01:10:48,660
>> AUDIÈNCIA: Bé, vostè acaba de
fer el mateix?

1542
01:10:48,660 --> 01:10:50,290
>> JASON Hirschhorn: Fer el mateix.

1543
01:10:50,290 --> 01:10:53,700
Així que en aquest cas, si no ho fem
volen mantenir el resolt que

1544
01:10:53,700 --> 01:10:55,270
Sona bastant simple.

1545
01:10:55,270 --> 01:10:59,920
Prenem el punter en l'índex
donada per la nostra funció hash.

1546
01:10:59,920 --> 01:11:03,830
Hem de apunten al nostre nou node.

1547
01:11:03,830 --> 01:11:07,830
I llavors el que estava assenyalant
prèviament -

1548
01:11:07,830 --> 01:11:10,620
en aquest cas nul, al
segon cas carbassa -

1549
01:11:10,620 --> 01:11:15,310
que, sigui el que està assenyalant
anteriorment, s'afegeix en el següent de

1550
01:11:15,310 --> 01:11:17,810
nostre nou node.

1551
01:11:17,810 --> 01:11:19,650
Estem inserint alguna cosa
en el començament.

1552
01:11:19,650 --> 01:11:22,900
De fet, això és molt més simple que
tractant de mantenir la llista ordenada.

1553
01:11:22,900 --> 01:11:25,340
Però, de nou, la cerca serà
més complicat aquí.

1554
01:11:25,340 --> 01:11:28,300
Sempre haurem d'anar fins al final.

1555
01:11:28,300 --> 01:11:29,650
>> D'acord.

1556
01:11:29,650 --> 01:11:32,750
Una pregunta sobre encadenament separat?

1557
01:11:32,750 --> 01:11:34,690
Com funciona?

1558
01:11:34,690 --> 01:11:35,820
Si us plau, pregunteu ara.

1559
01:11:35,820 --> 01:11:39,260
Tinc moltes ganes d'assegurar-se que tots els
entendre això abans que ens dirigim.

1560
01:11:39,260 --> 01:11:48,410

1561
01:11:48,410 --> 01:11:52,060
>> AUDIÈNCIA: Per què et poses de carbassa
i els dolços en el mateix

1562
01:11:52,060 --> 01:11:54,108
part de la taula hash?

1563
01:11:54,108 --> 01:11:55,860
>> JASON Hirschhorn: Bona pregunta.

1564
01:11:55,860 --> 01:11:59,140
Per què els posem en la mateixa
part de la taula hash?

1565
01:11:59,140 --> 01:12:03,200
Bé, en aquest cas la nostra funció hash
retorna zero per als dos.

1566
01:12:03,200 --> 01:12:05,310
Així que han d'anar a zero índex
perquè aquí és on anem a

1567
01:12:05,310 --> 01:12:07,420
buscar si mai
voler mirar cap amunt.

1568
01:12:07,420 --> 01:12:11,750
Una vegada més, amb un enfocament de sondeig lineal
nosaltres no posaríem els dos al zero.

1569
01:12:11,750 --> 01:12:13,900
Però en l'enfocament de la cadena independent,
ens posarem a tots dos en zero

1570
01:12:13,900 --> 01:12:16,620
a continuació, crear una llista de zero.

1571
01:12:16,620 --> 01:12:20,140
>> I no volem sobreescriure carbassa
simplement per això, perquè llavors anem a

1572
01:12:20,140 --> 01:12:21,860
assumir que la carabassa era
mai inserit.

1573
01:12:21,860 --> 01:12:25,230
Si acabem de tenir una cosa en la
ubicació que seria dolent.

1574
01:12:25,230 --> 01:12:28,590
Llavors no hi hauria
oportunitat de nosaltres -

1575
01:12:28,590 --> 01:12:31,660
si hem tingut un duplicat, llavors
seria simplement esborrar el nostre valor inicial.

1576
01:12:31,660 --> 01:12:34,090
Així que per això fem aquest enfocament.

1577
01:12:34,090 --> 01:12:36,580
O és per això que vam triar - però de nou,
va triar l'enfocament d'encadenament separat,

1578
01:12:36,580 --> 01:12:39,670
que hi ha molts altres enfocaments
un pot triar.

1579
01:12:39,670 --> 01:12:41,185
Respon això a la seva pregunta?

1580
01:12:41,185 --> 01:12:41,660
>> D'acord.

1581
01:12:41,660 --> 01:12:42,910
Carles.

1582
01:12:42,910 --> 01:12:46,130

1583
01:12:46,130 --> 01:12:47,720
Sondeig lineal implicaria -

1584
01:12:47,720 --> 01:12:51,913
si trobem una col · lisió a zero,
es veuria en el punt següent per veure si

1585
01:12:51,913 --> 01:12:54,310
que estava obert i el va posar allà.

1586
01:12:54,310 --> 01:12:57,320
I llavors ens mirem en el següent esport i
veure si estava obert i el va posar allà.

1587
01:12:57,320 --> 01:12:59,780
Així ens trobem amb la següent disposició
lloc obert i el va posar allà.

1588
01:12:59,780 --> 01:13:02,580

1589
01:13:02,580 --> 01:13:03,890
Alguna altra pregunta?

1590
01:13:03,890 --> 01:13:05,370
Sí, Avi.

1591
01:13:05,370 --> 01:13:07,490
>> AUDIÈNCIA: Com seguiment a això,
Què vol dir el proper acte?

1592
01:13:07,490 --> 01:13:10,250
A la taula hash o en una llista enllaçada.

1593
01:13:10,250 --> 01:13:12,100
>> JASON Hirschhorn: Per lineal
programació, no hi ha llistes enllaçades.

1594
01:13:12,100 --> 01:13:13,400
El següent punt a la taula hash.

1595
01:13:13,400 --> 01:13:13,820
>> AUDIÈNCIA: OK.

1596
01:13:13,820 --> 01:13:17,570
Així que la taula hash seria
inicialitzat a la mida -

1597
01:13:17,570 --> 01:13:19,560
com el nombre de cadenes
que estigués inserint?

1598
01:13:19,560 --> 01:13:22,170
>> JASON Hirschhorn: El faries
vull que sigui molt gran.

1599
01:13:22,170 --> 01:13:23,910
Sí

1600
01:13:23,910 --> 01:13:27,900
Aquí està una foto del que
acaba de dibuixar al tauler.

1601
01:13:27,900 --> 01:13:29,470
Un cop més, tenim una col · lisió aquí.

1602
01:13:29,470 --> 01:13:30,710
a 152.

1603
01:13:30,710 --> 01:13:33,570
I veuràs que hem creat
una llista enllaçada fora.

1604
01:13:33,570 --> 01:13:38,200

1605
01:13:38,200 --> 01:13:41,850
Un cop més, la taula hash encadenament separat
enfocament no és el que vostè

1606
01:13:41,850 --> 01:13:45,590
han de prendre per establir els problemes
sis, però és una que molta

1607
01:13:45,590 --> 01:13:47,100
els estudiants tendeixen a prendre.

1608
01:13:47,100 --> 01:13:51,140
Així que en aquest sentit, parlarem breument
abans que ens dirigim a terme sobre el problema de les sis,

1609
01:13:51,140 --> 01:13:52,160
i després vaig a compartir amb vostès una història.

1610
01:13:52,160 --> 01:13:55,120
Tenim tres minuts.

1611
01:13:55,120 --> 01:13:55,750
>> Problema 6 set.

1612
01:13:55,750 --> 01:13:57,790
Vostè té quatre funcions -

1613
01:13:57,790 --> 01:14:02,430
càrrega, comprovar, la mida i descàrrega.

1614
01:14:02,430 --> 01:14:03,380
Load -

1615
01:14:03,380 --> 01:14:07,120
bo, hem estat anant
sobrecàrrega en aquest moment.

1616
01:14:07,120 --> 01:14:09,330
Dibuixem la càrrega en el tauler.

1617
01:14:09,330 --> 01:14:13,230
I fins i tot ens vam començar a codificar una gran quantitat de
inserir en una llista enllaçada.

1618
01:14:13,230 --> 01:14:18,020
Així que la càrrega no és molt més que
el que hem estat fent.

1619
01:14:18,020 --> 01:14:21,070
>> Descobreix que és un cop
una mica carregat.

1620
01:14:21,070 --> 01:14:22,580
És el mateix procés que aquest.

1621
01:14:22,580 --> 01:14:26,845
Les mateixes dues primeres parts on vostè llança
alguna cosa dins de la funció hash

1622
01:14:26,845 --> 01:14:29,190
i obtenir el seu valor.

1623
01:14:29,190 --> 01:14:30,700
Però ara no estem d'inserir-lo.

1624
01:14:30,700 --> 01:14:33,350
Ara estem buscant.

1625
01:14:33,350 --> 01:14:37,130
He escrit el codi d'exemple per trobar
alguna cosa en una llista enllaçada.

1626
01:14:37,130 --> 01:14:38,250
Us animo a practicar això.

1627
01:14:38,250 --> 01:14:43,000
Però intuïtivament trobar alguna cosa que es
bastant similar a la inserció d'alguna cosa.

1628
01:14:43,000 --> 01:14:46,540
De fet, ens va fer un dibuix de la recerca
alguna cosa en una llista enllaçada, movent-se

1629
01:14:46,540 --> 01:14:48,910
a través fins que vam arribar a la final.

1630
01:14:48,910 --> 01:14:52,430
I si arribem a la final i no podia
troba, llavors no hi és.

1631
01:14:52,430 --> 01:14:55,400
Així que això és xec, essencialment.

1632
01:14:55,400 --> 01:14:57,030
>> Següent és la mida.

1633
01:14:57,030 --> 01:14:57,910
Anem a saltar mida.

1634
01:14:57,910 --> 01:15:00,040
Finalment has descarregar.

1635
01:15:00,040 --> 01:15:02,890
Unload és que no hem elaborat
a la pissarra o encara codificada.

1636
01:15:02,890 --> 01:15:05,990
Però m'animo a provar a programar
en la nostra mostra exemple de llista enllaçada.

1637
01:15:05,990 --> 01:15:11,440
Però descarregar intuïtiva
és similar a la lliure -

1638
01:15:11,440 --> 01:15:14,010
o que vull dir és similar a comprovar.

1639
01:15:14,010 --> 01:15:17,350
Excepte moment cada vegada que vostè va
a través, no estàs seleccionant

1640
01:15:17,350 --> 01:15:19,090
veure si vostè té el seu valor allà.

1641
01:15:19,090 --> 01:15:22,490
Però vostè està prenent aquest node i
alliberant, essencialment.

1642
01:15:22,490 --> 01:15:23,610
Això és el que es baixa et demana que facis.

1643
01:15:23,610 --> 01:15:24,670
Tot el lliure que ha malloced.

1644
01:15:24,670 --> 01:15:27,480
Així que vas a través de tota la llista
de nou, passant per tot el hash

1645
01:15:27,480 --> 01:15:27,760
taula de nou.

1646
01:15:27,760 --> 01:15:29,240
Aquesta vegada no marca
per veure el que hi ha.

1647
01:15:29,240 --> 01:15:31,080
Només alliberar el que hi ha.

1648
01:15:31,080 --> 01:15:33,260
>> I finalment mida.

1649
01:15:33,260 --> 01:15:34,350
Mida ha de ser implementat.

1650
01:15:34,350 --> 01:15:35,590
Si no s'implementa la mida -

1651
01:15:35,590 --> 01:15:36,250
Vaig a dir-ho d'aquesta manera.

1652
01:15:36,250 --> 01:15:39,740
Si no s'implementa mida exactament
una línia de codi que inclou el

1653
01:15:39,740 --> 01:15:43,760
tornar declaració, vostè és
fent mida incorrectament.

1654
01:15:43,760 --> 01:15:47,170
Així que assegureu-vos que la mida, per al disseny complet
punts, ho estàs fent exactament en un

1655
01:15:47,170 --> 01:15:49,970
línia de codi, incloent
la sentència return.

1656
01:15:49,970 --> 01:15:52,450
>> I no les maletes, però, Akchar.

1657
01:15:52,450 --> 01:15:53,700
Eager Beaver.

1658
01:15:53,700 --> 01:15:55,820

1659
01:15:55,820 --> 01:16:01,300
Volia donar les gràcies nois
per venir a la secció.

1660
01:16:01,300 --> 01:16:02,550
Tingueu un feliç Halloween.

1661
01:16:02,550 --> 01:16:05,300

1662
01:16:05,300 --> 01:16:05,960
Aquest és el meu disfressa.

1663
01:16:05,960 --> 01:16:08,850
Portaré aquest dijous
si et veig en horari d'oficina.

1664
01:16:08,850 --> 01:16:14,640
I si ets curiós sobre una mica més
fons per a aquest vestit, se senten

1665
01:16:14,640 --> 01:16:19,135
lliure de visitar la secció 2011
per a una història sobre per què estic

1666
01:16:19,135 --> 01:16:20,900
vestint el vestit de carbassa.

1667
01:16:20,900 --> 01:16:23,680
I és una història trista.

1668
01:16:23,680 --> 01:16:27,050
Així que segur de tindre
alguns teixits propers.

1669
01:16:27,050 --> 01:16:28,680
Però en això, si vostè té qualsevol
preguntes que em quedaré per aquí

1670
01:16:28,680 --> 01:16:29,960
fora després de la secció.

1671
01:16:29,960 --> 01:16:31,510
Bona sort en problema sisos.

1672
01:16:31,510 --> 01:16:33,540
I com sempre, si té alguna
preguntes, que em faci saber.

1673
01:16:33,540 --> 01:16:35,584