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

2
00:00:08,250 --> 00:00:12,680
>> Jason Hirschhorn: Sexan benvidos
á Sección de Sete.

3
00:00:12,680 --> 00:00:15,040
Estamos na semana de sete do curso.

4
00:00:15,040 --> 00:00:18,440
E esta próximo xoves
Halloween é así que eu son

5
00:00:18,440 --> 00:00:21,420
vestido como unha cabaza.

6
00:00:21,420 --> 00:00:23,460
Eu non podía curvar e poñer en
meus zapatos, entón é por iso que eu son

7
00:00:23,460 --> 00:00:25,660
só vestindo medias.

8
00:00:25,660 --> 00:00:29,220
Eu tampouco estou usando nada por baixo
iso, entón eu non podo tirá-lo, se é

9
00:00:29,220 --> 00:00:29,950
distraendo a vostede.

10
00:00:29,950 --> 00:00:31,860
Pido desculpas por adiantado por iso.

11
00:00:31,860 --> 00:00:33,170
Non precisa de imaxinar
o que está pasando.

12
00:00:33,170 --> 00:00:34,240
Estou usando cueca.

13
00:00:34,240 --> 00:00:36,170
Entón, é todo de bo.

14
00:00:36,170 --> 00:00:41,120
>> Eu teño unha longa historia sobre por que estou
vestido como unha cabaza, pero eu vou

15
00:00:41,120 --> 00:00:45,110
gardar para máis tarde nesta sección
porque quero comezar.

16
00:00:45,110 --> 00:00:47,720
Temos unha morea de cousas interesantes
para ir ao longo desta semana.

17
00:00:47,720 --> 00:00:51,810
A maioría deles están directamente relacionadas con esta
conxunto de problemas da semana, erros de ortografía.

18
00:00:51,810 --> 00:00:54,680
Nós imos estar pasando por riba conectado
listas e táboas hash

19
00:00:54,680 --> 00:00:57,160
para toda a sección.

20
00:00:57,160 --> 00:01:02,490
Coloque esta lista cada semana, unha lista de
recursos para que poida axudar con

21
00:01:02,490 --> 00:01:04,120
O material deste curso.

22
00:01:04,120 --> 00:01:07,600
Se a unha perda ou se buscar algunha
obter máis información, confía un dos

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

24
00:01:09,930 --> 00:01:14,530
>> Unha vez máis, é pset6 erros ortográficos,
pset desta semana.

25
00:01:14,530 --> 00:01:17,690
E tamén anima ti, e eu
incentivos-lo, usar algún outro

26
00:01:17,690 --> 00:01:20,320
recursos especialmente para este pset.

27
00:01:20,320 --> 00:01:23,390
En particular, os tres que eu teño
listado na pantalla -

28
00:01:23,390 --> 00:01:27,160
gdb, que fomos familiarizado con
e usado por un tempo agora, é

29
00:01:27,160 --> 00:01:29,270
vai ser moi útil nesta semana.

30
00:01:29,270 --> 00:01:30,190
Entón eu coloque iso aquí enriba.

31
00:01:30,190 --> 00:01:32,910
Pero sempre que está a traballar con C,
ten que sempre estar usando gdb para

32
00:01:32,910 --> 00:01:34,430
depurar os seus programas.

33
00:01:34,430 --> 00:01:36,660
Esta semana tamén Valgrind.

34
00:01:36,660 --> 00:01:38,535
Alguén sabe o que Valgrind fai?

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

36
00:01:42,184 --> 00:01:43,890
>> Audiencia: El verifica se hai perdas de memoria?

37
00:01:43,890 --> 00:01:45,950
>> Jason Hirschhorn: Valgrind
comproba se hai perdas de memoria.

38
00:01:45,950 --> 00:01:49,970
Entón, se malloc algo no seu
programa, está pedindo para a memoria.

39
00:01:49,970 --> 00:01:52,920
Ao final do seu programa, ten
libre para escribir sobre todo o que teño

40
00:01:52,920 --> 00:01:54,800
malloced para dar a memoria de volta.

41
00:01:54,800 --> 00:01:58,420
Se non escribir libre ao final e
o programa chega a unha conclusión,

42
00:01:58,420 --> 00:02:00,000
todo automaticamente
ser liberado.

43
00:02:00,000 --> 00:02:02,340
E para pequenos programas, é
non un gran negocio.

44
00:02:02,340 --> 00:02:05,250
Pero se está escribindo unha longa carreira
programa que non parar,

45
00:02:05,250 --> 00:02:09,180
necesariamente, nun par de minutos ou unha
uns segundos, a continuación, perdas de memoria

46
00:02:09,180 --> 00:02:10,710
pode facer un gran negocio.

47
00:02:10,710 --> 00:02:14,940
>> Así, para pset6, a esperanza é que
vai ter cero derrames de memoria con

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

49
00:02:15,910 --> 00:02:18,690
Para comprobar se hai perdas de memoria, Valgrind realizar
e só pode darlle algún bo

50
00:02:18,690 --> 00:02:21,190
saída que permite que vostede sabe se
ou non todo estaba libre.

51
00:02:21,190 --> 00:02:23,940
Imos practicar con el máis tarde
hoxe, eu espero.

52
00:02:23,940 --> 00:02:25,790
>> Por último, a orde dif.

53
00:02:25,790 --> 00:02:28,900
Usou algo semellante a el
en pset5 coa ferramenta espiar.

54
00:02:28,900 --> 00:02:30,780
Permitiu-lle ollar para dentro.

55
00:02:30,780 --> 00:02:33,400
Tamén usou diff, tamén, por
o conxunto de problemas spec.

56
00:02:33,400 --> 00:02:35,950
Pero, permítelle
comparar dous arquivos.

57
00:02:35,950 --> 00:02:39,180
Podería comparar o ficheiro de mapa de bits e
Información cabeceiras dunha solución persoal e

58
00:02:39,180 --> 00:02:42,200
a súa solución en pset5 se
Escolleu usalo.

59
00:02:42,200 --> 00:02:44,030
Dif permitirá que
facelo, tamén.

60
00:02:44,030 --> 00:02:48,620
Pode comparar a resposta correcta para
problema desta semana para definir a súa resposta

61
00:02:48,620 --> 00:02:52,210
e ver se se Aliñar ou ver
en que os erros son.

62
00:02:52,210 --> 00:02:55,870
>> Polo tanto, estas son tres boas ferramentas que
pode usar para esta semana, e

63
00:02:55,870 --> 00:02:58,130
definitivamente comprobar o seu programa
con estas tres ferramentas

64
00:02:58,130 --> 00:03:00,520
antes de virar-lo dentro

65
00:03:00,520 --> 00:03:04,650
Unha vez máis, como xa mencionado cada semana,
se ten algún comentario para min - tanto

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

67
00:03:06,470 --> 00:03:09,930
sentir-se libre para ir ao sitio web
na parte inferior da diapositiva

68
00:03:09,930 --> 00:03:11,270
e introducir-la alí.

69
00:03:11,270 --> 00:03:13,440
Eu realmente aprecio calquera
e todos os comentarios.

70
00:03:13,440 --> 00:03:17,360
E se me dar cousas específicas que
Que podo facer para mellorar ou que eu son

71
00:03:17,360 --> 00:03:21,350
facendo ben que lle gustaría que eu
continuar, eu levo iso en serio e

72
00:03:21,350 --> 00:03:24,040
realmente se esforzo para escoitar
para o seu producto.

73
00:03:24,040 --> 00:03:27,720
Eu non podo prometer que vou facer
todo, porén, como levar unha

74
00:03:27,720 --> 00:03:30,700
cabaza traxe cada semana.

75
00:03:30,700 --> 00:03:34,020
>> Entón imos pasar a maior parte
sección, como xa referín, fala

76
00:03:34,020 --> 00:03:37,240
listas ligadas e táboas de hash, que
será directamente aplicable ao

77
00:03:37,240 --> 00:03:38,780
conxunto de problemas esta semana.

78
00:03:38,780 --> 00:03:42,580
Listas encadeadas, imos pasar por riba de concepto
axiña, porque nós pasamos un pouco máis xusto

79
00:03:42,580 --> 00:03:44,930
tempo indo sobre el na sección.

80
00:03:44,930 --> 00:03:48,680
E entón imos directo ao
codificación problemas para listas ligadas.

81
00:03:48,680 --> 00:03:52,740
E entón ao final imos falar
táboas hash e como se aplican a este

82
00:03:52,740 --> 00:03:55,280
O problema da semana definido.

83
00:03:55,280 --> 00:03:57,560
>> Xa viu este código antes.

84
00:03:57,560 --> 00:04:02,730
Esta é unha estrutura, e que consiste en establecer
algo novo chamado nó.

85
00:04:02,730 --> 00:04:10,660
E dentro dun nodo existe un número enteiro
aquí e alí é un punteiro para

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

87
00:04:11,830 --> 00:04:12,790
Nós xa vimos isto antes.

88
00:04:12,790 --> 00:04:14,830
Iso foi chegando a
un par de semanas agora.

89
00:04:14,830 --> 00:04:18,680
El combina os punteiros, que fomos
traballar con, e estruturas, que permiten

90
00:04:18,680 --> 00:04:22,079
nos a combinar dous diferentes
cousas nun tipo de datos.

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

92
00:04:24,830 --> 00:04:26,490
>> Hai moita cousa a suceder na pantalla.

93
00:04:26,490 --> 00:04:30,220
Pero todo isto debe ser relativamente
familiarizado con vostede.

94
00:04:30,220 --> 00:04:33,810
Na primeira liña, nós
declarar un novo nodo.

95
00:04:33,810 --> 00:04:41,650
E, a continuación, dentro dese novo nodo, eu definir
o enteiro en que o nodo a un.

96
00:04:41,650 --> 00:04:44,950
Vemos a próxima liña que eu estou facendo un
printf mando, pero eu xa esmaecidas

97
00:04:44,950 --> 00:04:48,080
a orde printf, porque a verdade
parte importante é esta liña aquí -

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

99
00:04:50,020 --> 00:04:51,270
O que fai o punto significa?

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

101
00:04:53,810 --> 00:04:57,240
>> Audiencia: Ir a nó e
avaliar o valor n a el.

102
00:04:57,240 --> 00:04:58,370
>> Jason Hirschhorn: Isto é
exactamente correcto.

103
00:04:58,370 --> 00:05:03,300
Dot significa acceder a parte n
deste novo nodo.

104
00:05:03,300 --> 00:05:05,690
A seguinte liña fai o que?

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
>> Audiencia: Crea outro nodo
que pode apuntar para o novo nodo.

108
00:05:21,910 --> 00:05:24,870
>> Jason Hirschhorn: Entón non fai
crear un novo nodo.

109
00:05:24,870 --> 00:05:26,120
El crea un o que?

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

111
00:05:28,300 --> 00:05:29,300
>> Audiencia: Un punteiro.

112
00:05:29,300 --> 00:05:33,460
>> Jason Hirschhorn: Un enlace a un nodo,
indicadas por este nodo * aquí.

113
00:05:33,460 --> 00:05:34,800
Así, créase un punteiro a un nodo.

114
00:05:34,800 --> 00:05:37,490
E cal nodo é apuntando
para, Michael?

115
00:05:37,490 --> 00:05:38,440
>> Audiencia: Novo nodo?

116
00:05:38,440 --> 00:05:39,240
>> Jason Hirschhorn: Novo nodo.

117
00:05:39,240 --> 00:05:43,020
E está a apuntar alí porque temos
dado o enderezo do novo nodo.

118
00:05:43,020 --> 00:05:45,820
E agora nesta liña podemos ver
dous xeitos diferentes de

119
00:05:45,820 --> 00:05:46,910
expresando o mesmo.

120
00:05:46,910 --> 00:05:49,650
E eu quería salientar a forma na que estes
dúas cousas son o mesmo.

121
00:05:49,650 --> 00:05:54,740
Na primeira liña, nós desreferenciava
o punteiro.

122
00:05:54,740 --> 00:05:55,830
Entón imos ao nodo.

123
00:05:55,830 --> 00:05:56,830
Iso é o que esta estrela significa.

124
00:05:56,830 --> 00:05:57,930
Nós xa vimos isto antes con punteiros.

125
00:05:57,930 --> 00:05:59,280
Ir a aquel nó.

126
00:05:59,280 --> 00:06:00,370
Isto é entre parénteses.

127
00:06:00,370 --> 00:06:04,610
E, a continuación, acceder a través do operador punto
o elemento n dese nodo.

128
00:06:04,610 --> 00:06:08,430
>> Entón, que está tomando a sintaxe
vimos aquí e agora

129
00:06:08,430 --> 00:06:09,670
usalo cun punteiro.

130
00:06:09,670 --> 00:06:13,730
Por suposto, está un pouco ocupado
está escribindo eses parénteses -

131
00:06:13,730 --> 00:06:14,940
que estrela e que punto.

132
00:06:14,940 --> 00:06:16,220
Queda un pouco ocupado.

133
00:06:16,220 --> 00:06:18,500
Polo tanto, temos un pouco de azucre sintático.

134
00:06:18,500 --> 00:06:19,920
E esta liña 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
Isto fai exactamente o mesmo.

138
00:06:28,000 --> 00:06:30,840
Entón, estas dúas liñas de código son
equivalente e fará

139
00:06:30,840 --> 00:06:31,650
exactamente o mesmo.

140
00:06:31,650 --> 00:06:34,210
>> Pero eu quería sinalar aqueles antes
de ir máis lonxe para que poida entender

141
00:06:34,210 --> 00:06:39,000
que realmente esta cousa aquí é
só azucre sintático para dereferencing

142
00:06:39,000 --> 00:06:44,200
o punteiro e logo, indo a
a parte n desta estrutura.

143
00:06:44,200 --> 00:06:45,525
Calquera dúbida sobre este foto?

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

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

146
00:06:54,390 --> 00:06:58,510
>> Entón imos pasar por unha parella
de operacións que pode facer na

147
00:06:58,510 --> 00:06:59,730
listas ligadas.

148
00:06:59,730 --> 00:07:05,770
Unha lista ligada, recall, é unha serie de
nós que ligan un ao outro.

149
00:07:05,770 --> 00:07:12,470
E nós xeralmente comezan cun punteiro
chamado cabeza, en xeral, que apunta a

150
00:07:12,470 --> 00:07:14,040
o primeiro na lista.

151
00:07:14,040 --> 00:07:18,900
Entón, na primeira liña aquí, nós
temos o noso L orixinal primeiros.

152
00:07:18,900 --> 00:07:21,370
Entón aquela cousa que pode pensar - este
texto aquí pode pensar en como

153
00:07:21,370 --> 00:07:23,560
só o punteiro temos almacenados
que nalgún lugar puntos

154
00:07:23,560 --> 00:07:24,670
ao primeiro elemento.

155
00:07:24,670 --> 00:07:27,500
E nesta lista ligada
temos catro nós.

156
00:07:27,500 --> 00:07:29,530
Cada nó é unha caixa grande.

157
00:07:29,530 --> 00:07:33,430
O cadro máis grande dentro da gran
caixa é a parte enteira.

158
00:07:33,430 --> 00:07:37,400
E entón nós temos unha parte do punteiro.

159
00:07:37,400 --> 00:07:39,630
>> Esas caixas non son atraídos a
escala, xa que o grande é

160
00:07:39,630 --> 00:07:42,320
un número enteiro de bytes?

161
00:07:42,320 --> 00:07:43,290
Como gran agora?

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

163
00:07:43,710 --> 00:07:45,470
E o grande é un punteiro?

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

165
00:07:45,940 --> 00:07:48,180
Entón, realmente, se fose deseñar
esta para escalar as dúas caixas

166
00:07:48,180 --> 00:07:49,690
sería o mesmo tamaño.

167
00:07:49,690 --> 00:07:52,870
Neste caso, queremos introducir
algo na lista encadeada.

168
00:07:52,870 --> 00:07:57,190
Así pode ver aquí abaixo estamos inserindo
Nós cinco atravesar o

169
00:07:57,190 --> 00:08:01,310
lista ligada, atopar onde cinco
vai, e, a continuación, introduza-o.

170
00:08:01,310 --> 00:08:03,560
>> Imos romper ese abaixo e ir
algo máis a modo.

171
00:08:03,560 --> 00:08:05,510
Vou apuntar para o consello.

172
00:08:05,510 --> 00:08:09,930
Entón, nós temos o noso nodo cinco que
creamos en mallocs.

173
00:08:09,930 --> 00:08:11,190
Por que todos están rindo?

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

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

176
00:08:13,310 --> 00:08:14,820
Entón nós malloced cinco.

177
00:08:14,820 --> 00:08:16,310
Creamos este nodo
noutro lugar.

178
00:08:16,310 --> 00:08:17,740
Nós temo-lo preparado para ir.

179
00:08:17,740 --> 00:08:20,130
Comezamos diante
nosa lista con dous.

180
00:08:20,130 --> 00:08:22,380
E nós queremos introducir
dunha forma ordenada.

181
00:08:22,380 --> 00:08:27,550
>> Entón, se vemos dous e queremos poñer
en cinco anos, o que facemos cando vemos

182
00:08:27,550 --> 00:08:28,800
algo menos que nós?

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

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

185
00:08:33,520 --> 00:08:36,750
Queremos introducir cinco a este
lista ligada, manténdose clasificada.

186
00:08:36,750 --> 00:08:37,520
Vemos o número dous.

187
00:08:37,520 --> 00:08:38,769
Entón, o que facemos?

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

189
00:08:39,179 --> 00:08:40,679
>> Audiencia: Chama o punteiro
ao seguinte nodo.

190
00:08:40,679 --> 00:08:42,530
>> Jason Hirschhorn: E por que
imos ao seguinte?

191
00:08:42,530 --> 00:08:45,970
>> Audiencia: Porque é a
seguinte nodo da lista.

192
00:08:45,970 --> 00:08:48,310
E só sabemos que outro local.

193
00:08:48,310 --> 00:08:50,410
>> Jason Hirschhorn: E cinco é maior
que dous, en particular.

194
00:08:50,410 --> 00:08:51,600
Porque queremos mantelo ordenado.

195
00:08:51,600 --> 00:08:52,730
Así, cinco é maior que dous.

196
00:08:52,730 --> 00:08:54,460
Entón, imos pasar á seguinte.

197
00:08:54,460 --> 00:08:55,240
E agora chegamos a catro.

198
00:08:55,240 --> 00:08:56,490
E o que pasa cando chegamos a catro?

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

200
00:08:58,920 --> 00:09:00,310
>> Cinco é maior que catro.

201
00:09:00,310 --> 00:09:01,460
Por iso, manter-se ir.

202
00:09:01,460 --> 00:09:03,110
E agora estamos en seis.

203
00:09:03,110 --> 00:09:04,360
E o que vemos ás seis?

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

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

206
00:09:09,608 --> 00:09:10,544
>> Audiencia: Seis é maior que cinco.

207
00:09:10,544 --> 00:09:11,480
>> Jason Hirschhorn: Seis é
maior que cinco.

208
00:09:11,480 --> 00:09:13,660
Entón é aí que queremos
inserir cinco.

209
00:09:13,660 --> 00:09:17,320
Con todo, ten en conta que, se
só ten un punteiro aquí -

210
00:09:17,320 --> 00:09:19,840
este é o noso punteiro extra que é
percorrendo a lista.

211
00:09:19,840 --> 00:09:21,860
E nós estamos apuntando para seis.

212
00:09:21,860 --> 00:09:25,010
Perdemos a noción do que
vén antes das seis.

213
00:09:25,010 --> 00:09:29,130
Polo tanto, se queremos introducir algo na
esta lista manténdose clasificado, que

214
00:09:29,130 --> 00:09:31,630
probablemente precisa de cantos punteiros?

215
00:09:31,630 --> 00:09:32,280
>> Audiencia: Dous.

216
00:09:32,280 --> 00:09:32,920
>> Jason Hirschorn: Dous.

217
00:09:32,920 --> 00:09:35,720
Un para seguir a corrente
un e un para seguir

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

219
00:09:37,050 --> 00:09:38,450
Esta é só unha lista vinculada illadamente.

220
00:09:38,450 --> 00:09:39,670
El só vai unha dirección.

221
00:09:39,670 --> 00:09:43,220
Se tivésemos unha lista dobremente vinculada, onde
todo estaba a apuntar cara a cousa

222
00:09:43,220 --> 00:09:46,240
despois de que el ea cousa antes, entón
nós non precisamos facelo.

223
00:09:46,240 --> 00:09:49,350
Pero neste caso non queremos perder
a par do que viñeron antes de nós, no caso

224
00:09:49,350 --> 00:09:53,350
necesitamos introducir cinco nalgún lugar
no medio.

225
00:09:53,350 --> 00:09:55,610
Digamos que foron inserindo nove.

226
00:09:55,610 --> 00:09:57,260
Que pasaría cando
chegamos a oito?

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

228
00:10:01,860 --> 00:10:04,880
>> Audiencia: Vostede tería que
obter ese punto nulo.

229
00:10:04,880 --> 00:10:07,820
En vez de ter punto nulo que tería
engadir un elemento e, a continuación, teñen

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

231
00:10:09,216 --> 00:10:09,700
>> Jason Hirschorn: Exactamente.

232
00:10:09,700 --> 00:10:10,600
Entón, temos oito.

233
00:10:10,600 --> 00:10:13,140
Chegamos ao final da lista, xa que
este está a apuntar cara null.

234
00:10:13,140 --> 00:10:16,330
E agora, en vez de ter que ligan con
nulo, temos que apuntar para o noso novo nodo.

235
00:10:16,330 --> 00:10:19,870
E imos establecer o punteiro na
noso novo nodo como nulo.

236
00:10:19,870 --> 00:10:21,445
Alguén ten algunha dúbida
sobre como inserir?

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

238
00:10:25,620 --> 00:10:28,100
E se eu non me importa
manter a lista ordenada?

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

240
00:10:31,701 --> 00:10:34,350
>> Audiencia: Cole-o na
inicio ou o final.

241
00:10:34,350 --> 00:10:35,510
>> Jason Hirschorn: Cole-o na
o inicio ou o final.

242
00:10:35,510 --> 00:10:37,276
Cal deles que temos que facer?

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

244
00:10:38,770 --> 00:10:41,020
Por que o fin?

245
00:10:41,020 --> 00:10:43,250
>> Audiencia: Como o principio
xa está cuberto.

246
00:10:43,250 --> 00:10:43,575
>> Jason Hirschorn: Aceptar.

247
00:10:43,575 --> 00:10:44,360
O inicio xa está cheo.

248
00:10:44,360 --> 00:10:46,090
Quen quere argumentar contra Bobby.

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

250
00:10:47,290 --> 00:10:48,910
>> Audiencia: Ben, probablemente vai querer
cola-la no inicio, xa que

251
00:10:48,910 --> 00:10:50,140
en caso contrario, se poñelas
ao final ten que

252
00:10:50,140 --> 00:10:51,835
percorrer a lista enteira.

253
00:10:51,835 --> 00:10:52,990
>> Jason Hirschorn: Exactamente.

254
00:10:52,990 --> 00:10:57,970
Entón, se estamos a pensar en tempo de execución, o
tempo de execución da inserción no extremo

255
00:10:57,970 --> 00:11:00,110
Sería n, o tamaño deste.

256
00:11:00,110 --> 00:11:03,080
Cal é a gran O tempo de execución de inserción
no inicio?

257
00:11:03,080 --> 00:11:04,170
Tempo constante.

258
00:11:04,170 --> 00:11:07,075
Entón, se non lle importa en manter
algo clasificado, moito mellor só

259
00:11:07,075 --> 00:11:08,420
inserir ao principio desta lista.

260
00:11:08,420 --> 00:11:10,320
E iso se pode facer en tempo constante.

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

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

263
00:11:14,690 --> 00:11:18,870
Seguinte operación é atopar, o que outros -
nós formulada isto como investigación.

264
00:11:18,870 --> 00:11:22,470
Pero imos ollar polo
lista ligada por algún obxecto.

265
00:11:22,470 --> 00:11:26,000
Vostedes viron o código para
buscar antes na charla.

266
00:11:26,000 --> 00:11:29,490
Pero nós medio que fixo
introducir, ou polo menos a inserción

267
00:11:29,490 --> 00:11:30,580
algo ordenado.

268
00:11:30,580 --> 00:11:36,350
Mira través, pasando nó por nodo,
ata atopar o número que está a

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

270
00:11:37,780 --> 00:11:39,670
Qué acontece se chegar
Ao final da lista?

271
00:11:39,670 --> 00:11:43,020
Digamos que eu estou buscando nove e eu
acadar o final da lista.

272
00:11:43,020 --> 00:11:44,270
O que imos facer?

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

274
00:11:47,147 --> 00:11:48,110
>> Audiencia: Retorno falso?

275
00:11:48,110 --> 00:11:48,690
>> Jason Hirschorn: Return false.

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

277
00:11:49,960 --> 00:11:52,010
Se chegar ao final da lista e
non atopa o número que está a

278
00:11:52,010 --> 00:11:54,170
buscar, non está alí.

279
00:11:54,170 --> 00:11:55,420
Calquera dúbida sobre atopar?

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

281
00:11:59,530 --> 00:12:04,615
Se isto fose unha lista ordenada, o que sería
ser diferente a nosa procura?

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

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

284
00:12:08,103 --> 00:12:10,600
>> Audiencia: El ía atopar o primeiro valor
que é maior que aquel

285
00:12:10,600 --> 00:12:12,390
está a buscar e
a continuación, regresar false.

286
00:12:12,390 --> 00:12:13,190
>> Jason Hirschorn: Exactamente.

287
00:12:13,190 --> 00:12:17,310
Entón, se é unha lista ordenada, se chegamos a
algo que é maior que o que

288
00:12:17,310 --> 00:12:20,180
nós estamos a buscar, non necesita
continuar ata o final da lista.

289
00:12:20,180 --> 00:12:24,060
Podemos nese punto return false
porque nós non imos atopalo.

290
00:12:24,060 --> 00:12:27,340
A cuestión agora é, nós xa falamos sobre
manter listas ligadas ordenada,

291
00:12:27,340 --> 00:12:28,180
manténdose os domésticos.

292
00:12:28,180 --> 00:12:30,050
Isto vai ser algo que está
probablemente vai ter que pensar sobre

293
00:12:30,050 --> 00:12:34,240
cando o problema de codificación establecer cinco, se
escoller unha táboa hash coa separado

294
00:12:34,240 --> 00:12:36,360
visión de fío, que
falaremos máis tarde.

295
00:12:36,360 --> 00:12:41,400
>> Pero paga a pena manter a lista
ordenada e, a continuación, ser capaz de ter quizais

296
00:12:41,400 --> 00:12:42,310
enquisas rápidas?

297
00:12:42,310 --> 00:12:47,220
Ou é mellor para inserir rapidamente
algo en tempo de execución constante, pero, a continuación,

298
00:12:47,220 --> 00:12:48,430
ter máis tempo buscando?

299
00:12:48,430 --> 00:12:52,250
Isto é un intercambio alí mesmo que
comeza a decidir o que é máis axeitado

300
00:12:52,250 --> 00:12:53,590
para o seu problema específico.

301
00:12:53,590 --> 00:12:56,680
E non é necesariamente un
resposta absolutamente certa.

302
00:12:56,680 --> 00:12:59,520
Pero certamente é unha decisión que comeza
de facer, e probablemente bo para defender

303
00:12:59,520 --> 00:13:05,270
que, digamos, un comentario ou dous por
escolleu un sobre o outro.

304
00:13:05,270 --> 00:13:06,490
>> Por último, excluíndo.

305
00:13:06,490 --> 00:13:08,100
Vimos a borrar.

306
00:13:08,100 --> 00:13:09,180
É semellante a buscar.

307
00:13:09,180 --> 00:13:11,020
Nós miramos para o elemento.

308
00:13:11,020 --> 00:13:12,390
Diga que estamos tentando eliminar seis.

309
00:13:12,390 --> 00:13:14,450
Así, atopamos seis aquí.

310
00:13:14,450 --> 00:13:18,860
O único que temos que estar seguro de que
facer é que todo o que está a apuntar cara

311
00:13:18,860 --> 00:13:21,220
seis - como podemos ver no paso
dous para acá -

312
00:13:21,220 --> 00:13:26,500
todo o que está a apuntar cara seis necesidades para
saltar seis e agora ser cambiado

313
00:13:26,500 --> 00:13:28,160
todo o que está a apuntar cara seis.

314
00:13:28,160 --> 00:13:31,410
Non quero nunca orfos resto da
nosa lista por esquecer de definir que

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

316
00:13:32,960 --> 00:13:35,960
E entón, ás veces, dependendo
sobre o programa, eles só

317
00:13:35,960 --> 00:13:37,380
eliminar este nodo enteiramente.

318
00:13:37,380 --> 00:13:40,135
Ás veces vai querer volver
o valor que está neste nodo.

319
00:13:40,135 --> 00:13:42,490
Entón é así que borrar obras.

320
00:13:42,490 --> 00:13:44,610
Calquera dúbida sobre borrar?

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

322
00:13:51,280 --> 00:13:53,850
>> Audiencia: Entón, se está indo para borrar
que se acaba de usar libre porque

323
00:13:53,850 --> 00:13:55,655
presuntamente foi malloced?

324
00:13:55,655 --> 00:13:57,976
>> Jason Hirschorn: Se quere liberar
algo que é certo e

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

326
00:13:58,540 --> 00:14:00,410
Digamos que quería retornar ese valor.

327
00:14:00,410 --> 00:14:04,010
Poderiamos volver seis anos e, así, libre
este nodo e chamada gratuíta sobre el.

328
00:14:04,010 --> 00:14:06,180
Ou nós probablemente chame gratis primeiro
e despois volver seis.

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

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

331
00:14:11,580 --> 00:14:14,010
Entón, imos pasar á práctica de codificación.

332
00:14:14,010 --> 00:14:16,090
Imos codificar tres funcións.

333
00:14:16,090 --> 00:14:18,260
O primeiro chámase insert_node.

334
00:14:18,260 --> 00:14:22,170
Entón tes o código que eu lle enviou, e
se está a ver isto, máis tarde,

335
00:14:22,170 --> 00:14:28,020
pode acceder ao código en linked.c
na páxina web do CS50.

336
00:14:28,020 --> 00:14:30,880
Pero en linked.c, hai algún
código de esqueleto que xa está

337
00:14:30,880 --> 00:14:32,280
foi escrito para ti.

338
00:14:32,280 --> 00:14:34,560
E despois hai un par de funcións
ten que escribir.

339
00:14:34,560 --> 00:14:36,380
>> Primeiro imos
escribir insert_node.

340
00:14:36,380 --> 00:14:39,800
E o que fai insert_node
sexa inserir un número enteiro.

341
00:14:39,800 --> 00:14:42,440
E está dando o enteiro
nunha lista encadeada.

342
00:14:42,440 --> 00:14:45,470
E, en particular, hai que
para manter a lista ordenada

343
00:14:45,470 --> 00:14:47,650
do menor ao maior.

344
00:14:47,650 --> 00:14:51,360
Ademais, non quere
introducir todos os duplicados.

345
00:14:51,360 --> 00:14:54,600
Finalmente, como se pode ver insert_node
retorna un bool.

346
00:14:54,600 --> 00:14:57,140
Entón está suposto de que o usuario saiba
se ou non a inserción era

347
00:14:57,140 --> 00:15:00,800
éxito, retornando verdadeiro ou falso.

348
00:15:00,800 --> 00:15:02,580
Ao final deste programa -

349
00:15:02,580 --> 00:15:05,750
e para esta fase non é necesario
preocuparse liberando nada.

350
00:15:05,750 --> 00:15:11,790
Entón todo o que está a facer é tomar un enteiro
e inserir-lo nunha lista.

351
00:15:11,790 --> 00:15:13,890
>> Iso é o que eu estou pedindo para lle facer agora.

352
00:15:13,890 --> 00:15:17,620
Unha vez máis, o linked.c, onde
todos teñen, é o código de esqueleto.

353
00:15:17,620 --> 00:15:20,980
E ten que ver para o fondo
a declaración da función mostra.

354
00:15:20,980 --> 00:15:27,390
Con todo, antes de ir a codifica-lo
en C, eu altamente incentivos-lo a ir

355
00:15:27,390 --> 00:15:29,330
a través dos pasos que fomos
practicando cada semana.

356
00:15:29,330 --> 00:15:31,100
Nós xa pasamos por
unha imaxe desta.

357
00:15:31,100 --> 00:15:33,380
Entón ten que ter algún coñecemento
de como funciona isto.

358
00:15:33,380 --> 00:15:36,590
Pero gustaríame incentivos-lo a escribir
algúns pseudocódigo antes de mergullar dentro

359
00:15:36,590 --> 00:15:38,640
E nós imos pasar por riba de
pseudocódigo como un grupo.

360
00:15:38,640 --> 00:15:41,470
E, a continuación, unha vez que teña escrito o
pseudocódigo, e unha vez que escribimos o noso

361
00:15:41,470 --> 00:15:45,850
pseudocódigo como un grupo, pode
ir a codifica-lo en C.

362
00:15:45,850 --> 00:15:49,980
>> Como un heads-up, a función insert_node
é probablemente a máis complicada de

363
00:15:49,980 --> 00:15:53,550
os tres que imos escribir, porque eu
engadiu algunhas restricións adicionais para

364
00:15:53,550 --> 00:15:57,190
súa programación, en particular, que
non está indo para introducir calquera

365
00:15:57,190 --> 00:15:59,880
dobre e que a lista
debe permanecer ordenada.

366
00:15:59,880 --> 00:16:02,660
Polo tanto, este é un programa non-trivial
que precisa para codificar.

367
00:16:02,660 --> 00:16:06,470
E por que non tira 06:55
minutos, só para se traballar na

368
00:16:06,470 --> 00:16:07,640
pseudocódigo eo código.

369
00:16:07,640 --> 00:16:09,460
E entón, imos comezar
indo como un grupo.

370
00:16:09,460 --> 00:16:11,680
De novo, se ten algunha dúbida pode
levante a man e eu vou chegar preto.

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
>> Tamén xeralmente fan estes -

375
00:18:30,120 --> 00:18:32,070
ou eu non explicitamente dicir que
pode traballar con persoas.

376
00:18:32,070 --> 00:18:36,500
Pero, obviamente, eu altamente incentivos-lo,
se ten dúbidas, pedir ao

377
00:18:36,500 --> 00:18:39,840
veciño sentado ao seu lado
ou incluso traballar con alguén

378
00:18:39,840 --> 00:18:40,510
outra cousa, se quere.

379
00:18:40,510 --> 00:18:42,600
Isto non ten que ser un individuo
actividade en silencio.

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

381
00:20:11,770 --> 00:20:16,330
>> Imos comezar coa escrita dalgúns
pseudocódigo na tarxeta.

382
00:20:16,330 --> 00:20:19,395
Quen me pode dar a primeira liña de
pseudocódigo para este programa?

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

384
00:20:22,240 --> 00:20:23,640
Para esta función, en vez -
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
>> Audiencia: Entón, o primeiro que fixen foi
crear un novo punteiro para o nó e I

388
00:20:36,560 --> 00:20:41,320
iniciar el apuntando para o mesmo
que lista está a apuntar.

389
00:20:41,320 --> 00:20:41,550
>> Jason Hirschorn: Aceptar.

390
00:20:41,550 --> 00:20:45,190
Entón, está creando un novo punteiro
á lista, non para o nodo.

391
00:20:45,190 --> 00:20:45,420
>> Audiencia: Certo.

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

393
00:20:46,150 --> 00:20:46,540
>> Jason Hirschorn: Aceptar.

394
00:20:46,540 --> 00:20:48,221
E entón o que é o que queremos facer?

395
00:20:48,221 --> 00:20:49,163
O que hai despois?

396
00:20:49,163 --> 00:20:50,105
E o no?

397
00:20:50,105 --> 00:20:51,050
Nós non temos un nó.

398
00:20:51,050 --> 00:20:52,300
Nós só temos un valor.

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

400
00:20:55,918 --> 00:20:58,890
Se queremos introducir un nodo, o que nós
cómpre facer antes de nós pode incluso

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

402
00:20:59,980 --> 00:21:00,820
>> Audiencia: Oh, desculpe.

403
00:21:00,820 --> 00:21:02,160
necesitamos malloc espazo para un nó.

404
00:21:02,160 --> 00:21:02,455
>> Jason Hirschorn: Excelente.

405
00:21:02,455 --> 00:21:03,210
Imos facer -

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

407
00:21:04,628 --> 00:21:06,065
Non se puido chegar a esa altura.

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

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

410
00:21:09,897 --> 00:21:13,236
Estamos indo para ir para abaixo, e despois
estamos a usar dúas columnas.

411
00:21:13,236 --> 00:21:13,732
Eu non podo ir que -

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

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

414
00:21:23,660 --> 00:21:25,130
Crear un novo nodo.

415
00:21:25,130 --> 00:21:29,380
Pode crear outro punteiro para consultar
ou pode simplemente usar a lista, xa que existe.

416
00:21:29,380 --> 00:21:30,720
Realmente non ten que facelo.

417
00:21:30,720 --> 00:21:31,750
>> Entón, creamos un novo nodo.

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

419
00:21:32,010 --> 00:21:32,840
Isto é o que facer primeiro.

420
00:21:32,840 --> 00:21:34,870
Cal é o próximo?

421
00:21:34,870 --> 00:21:35,080
>> Audiencia: Agarde.

422
00:21:35,080 --> 00:21:38,330
Debemos crear un novo nodo agora ou
hai que esperar para ter seguro de que

423
00:21:38,330 --> 00:21:42,260
non hai ningunha duplicado do nodo
na lista antes de crealo?

424
00:21:42,260 --> 00:21:43,100
>> Jason Hirschorn: Boa pregunta.

425
00:21:43,100 --> 00:21:47,770
Imos manter isto para despois, porque a
maior parte do tempo nós imos estar creando

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

427
00:21:48,220 --> 00:21:49,110
Entón, imos manter isto aquí.

428
00:21:49,110 --> 00:21:51,006
Pero iso é unha boa pregunta.

429
00:21:51,006 --> 00:21:53,250
Se nós o creamos e vemos
un dobre, o que debe

430
00:21:53,250 --> 00:21:54,490
o que facemos antes de regresar?

431
00:21:54,490 --> 00:21:55,190
>> Audiencia: Liberar-lo.

432
00:21:55,190 --> 00:21:55,470
>> Jason Hirschorn: Yeah.

433
00:21:55,470 --> 00:21:56,500
Probablemente liberalo la.

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

435
00:21:56,760 --> 00:21:59,850
O que imos facer despois de que
crear un novo nodo?

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

437
00:22:02,260 --> 00:22:04,780
>> Audiencia: Poñemos o
número do nodo?

438
00:22:04,780 --> 00:22:05,140
>> Jason Hirschorn: Exactamente.

439
00:22:05,140 --> 00:22:07,190
Poñemos o número - que malloc espazo.

440
00:22:07,190 --> 00:22:08,160
Vou deixar que
todo como unha liña.

441
00:22:08,160 --> 00:22:08,720
Pero está certo.

442
00:22:08,720 --> 00:22:10,305
Nós malloc espazo, e, a continuación,
imos poñer o número de polgadas

443
00:22:10,305 --> 00:22:12,585
Podemos incluso facer que o punteiro
parte del para null.

444
00:22:12,585 --> 00:22:13,720
Isto é exactamente correcto.

445
00:22:13,720 --> 00:22:17,400
E entón o que dicir despois diso?

446
00:22:17,400 --> 00:22:18,490
Nós tirei esta foto no cadro.

447
00:22:18,490 --> 00:22:21,190
Entón, o que facemos?

448
00:22:21,190 --> 00:22:22,680
>> Audiencia: Imos a través da lista.

449
00:22:22,680 --> 00:22:23,930
>> Jason Hirschorn: Vai á lista.

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

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

452
00:22:31,100 --> 00:22:34,280
E que é o que imos comprobar a en cada nodo.

453
00:22:34,280 --> 00:22:35,955
Kurt, o que nós consideramos
para en cada nó?

454
00:22:35,955 --> 00:22:41,640
>> Audiencia: Vexa o valor de n
este nodo é maior que o valor de n

455
00:22:41,640 --> 00:22:43,070
do noso nodo.

456
00:22:43,070 --> 00:22:43,340
>> Jason Hirschorn: Aceptar.

457
00:22:43,340 --> 00:22:44,280
Vou facer -

458
00:22:44,280 --> 00:22:45,855
si, Aceptar.

459
00:22:45,855 --> 00:22:48,160
Por iso, é n -

460
00:22:48,160 --> 00:22:59,040
Eu vou dicir que se o valor é maior
que este nodo, entón o que facemos?

461
00:22:59,040 --> 00:23:07,290
>> Audiencia: Ben, entón nós inserimos
as cousas ben antes diso.

462
00:23:07,290 --> 00:23:07,970
>> Jason Hirschorn: Aceptar.

463
00:23:07,970 --> 00:23:09,410
Entón, se é maior que iso,
entón nós queremos introducir.

464
00:23:09,410 --> 00:23:14,010
Pero queremos inserir-lo logo antes
porque nós tamén precisaría ser

465
00:23:14,010 --> 00:23:16,070
manter o control e, a continuación,
do que era antes.

466
00:23:16,070 --> 00:23:22,690
Entón, introduza antes.

467
00:23:22,690 --> 00:23:25,120
Entón, nós probablemente perdeu algo
anteriormente.

468
00:23:25,120 --> 00:23:27,770
Nós probablemente hai que manter
a par do que está pasando.

469
00:23:27,770 --> 00:23:28,460
Pero imos volver alí.

470
00:23:28,460 --> 00:23:30,160
Entón, o valor é menor que?

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

472
00:23:38,030 --> 00:23:39,710
Kurt, o que imos facer se
valor é menor que?

473
00:23:39,710 --> 00:23:43,000
>> Audiencia: Entón só manterá
a menos que sexa o último.

474
00:23:43,000 --> 00:23:43,550
>> Jason Hirschorn: Eu gusto diso.

475
00:23:43,550 --> 00:23:44,800
Entón, vai ao seguinte nodo.

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

477
00:23:47,410 --> 00:23:48,930
A menos que sexa o último -

478
00:23:48,930 --> 00:23:51,100
nós probablemente estamos comprobando para que
nos termos dunha condición.

479
00:23:51,100 --> 00:23:54,870
Pero si, preto nó.

480
00:23:54,870 --> 00:23:58,680
E iso está quedando moi baixo,
así que imos pasar aquí.

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

482
00:24:02,030 --> 00:24:03,280
pode todo o mundo ve iso?

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

484
00:24:07,230 --> 00:24:11,610
Si somos iguais, o que facemos?

485
00:24:11,610 --> 00:24:15,740
O valor que estamos intentando introducir
é igual ao valor deste nodo?

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

487
00:24:16,320 --> 00:24:18,400
>> Audiencia: [inaudível].

488
00:24:18,400 --> 00:24:18,850
>> Jason Hirschorn: Yeah.

489
00:24:18,850 --> 00:24:19,290
Dada esta -

490
00:24:19,290 --> 00:24:20,090
Marcus está certo.

491
00:24:20,090 --> 00:24:21,330
Poderiamos ter feito quizais
algo diferente.

492
00:24:21,330 --> 00:24:25,360
Pero dado que creamos, aquí
debemos liberar e despois volver.

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

494
00:24:26,774 --> 00:24:30,080
Está mellor?

495
00:24:30,080 --> 00:24:31,850
Como é iso?

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

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

498
00:24:35,360 --> 00:24:37,640
Libre e, a continuación, que é o que imos
volver, [inaudível]?

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

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

501
00:24:44,110 --> 00:24:45,360
Será que estamos perdendo algo?

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

503
00:24:53,500 --> 00:24:59,650
Entón para onde estamos mantendo o control
do nodo anterior?

504
00:24:59,650 --> 00:25:02,370
>> Audiencia: Coido que ía
despois de crear un novo nodo.

505
00:25:02,370 --> 00:25:02,600
>> Jason Hirschorn: Aceptar.

506
00:25:02,600 --> 00:25:03,940
Así, a principios probablemente imos -

507
00:25:03,940 --> 00:25:07,175
si, podemos crear un punteiro a unha nova
no, como un punteiro nodo anterior e

508
00:25:07,175 --> 00:25:09,600
un punteiro nodo actual.

509
00:25:09,600 --> 00:25:12,640
Entón, imos introducir este aquí.

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

511
00:25:15,610 --> 00:25:26,900
Crear actual e anterior
punteiros para os nós.

512
00:25:26,900 --> 00:25:28,955
Pero cando é que imos establecer os punteiros?

513
00:25:28,955 --> 00:25:30,205
Onde é que imos facelo no código?

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
>> Audiencia: - condicións de valor?

517
00:25:35,170 --> 00:25:36,420
>> Jason Hirschorn: Cal
un en particular?

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

519
00:25:39,862 --> 00:25:40,720
>> Audiencia: Eu só estou confuso.

520
00:25:40,720 --> 00:25:44,200
O valor é maior que este nodo,
non quere dicir que quere ir

521
00:25:44,200 --> 00:25:45,320
ao seguinte nodo?

522
00:25:45,320 --> 00:25:49,515
>> Jason Hirschhorn: Entón se o seu valor é
maior que o valor de este nodo.

523
00:25:49,515 --> 00:25:52,130
>> Audiencia: É, entón vai querer
ir máis abaixo da liña, non?

524
00:25:52,130 --> 00:25:52,590
>> Jason Hirschhorn: Certo.

525
00:25:52,590 --> 00:25:53,840
Entón, nós non inserir-lo aquí.

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

527
00:25:58,430 --> 00:26:03,240
O valor é inferior a este nodo, logo
imos ao seguinte nodo - ou entón nós

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

529
00:26:03,835 --> 00:26:05,966
>> Audiencia: Espere, o que é iso
nó e que é valor?

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

531
00:26:08,510 --> 00:26:09,280
>> Jason Hirschhorn: Boa pregunta.

532
00:26:09,280 --> 00:26:13,260
Valor por esta definición de función
é o que está dado.

533
00:26:13,260 --> 00:26:16,910
Así, o valor é o número que está dado.

534
00:26:16,910 --> 00:26:21,120
Entón, se o valor é menor que iso
no, necesitamos tempo para inserir.

535
00:26:21,120 --> 00:26:24,575
O valor é maior que este nodo,
imos ao seguinte nodo.

536
00:26:24,575 --> 00:26:26,790
E de volta á pregunta orixinal,
con todo, onde -

537
00:26:26,790 --> 00:26:29,060
>> Audiencia: O valor é maior
que este nodo.

538
00:26:29,060 --> 00:26:30,310
>> Jason Hirschhorn: E así
Que facemos aquí?

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

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

541
00:26:38,160 --> 00:26:38,860
Isto é correcto.

542
00:26:38,860 --> 00:26:41,370
Eu só vou escribir
punteiros de actualización.

543
00:26:41,370 --> 00:26:44,010
Pero, si, co actual
actualiza-lo para

544
00:26:44,010 --> 00:26:46,080
apuntar á seguinte.

545
00:26:46,080 --> 00:26:47,330
Calquera outra cousa que falta?

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

547
00:26:52,710 --> 00:26:54,940
Entón, eu estou indo a introducir esta
código en gedit.

548
00:26:54,940 --> 00:26:58,375
E mentres eu fai iso, pode ter un
máis uns minutos para traballar na codificación

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

550
00:28:19,240 --> 00:28:20,940
>> Entón, eu teño a entrada do pseudocódigo.

551
00:28:20,940 --> 00:28:22,940
Unha nota rápida antes de comezar.

552
00:28:22,940 --> 00:28:25,560
Podemos non ser capaces de completamente
rematar esta en todos

553
00:28:25,560 --> 00:28:27,300
estas tres funcións.

554
00:28:27,300 --> 00:28:30,630
Hai solucións correctas para eles
que eu vou enviar correo-e para vós

555
00:28:30,630 --> 00:28:33,730
despois de sección, e vai
ser posta en CS50.net.

556
00:28:33,730 --> 00:28:35,640
Entón eu non incentivos-lo a
ir ollar para as seccións.

557
00:28:35,640 --> 00:28:40,550
Estimula-vos a probar estes no seu
posuír, e logo use o da práctica

558
00:28:40,550 --> 00:28:41,760
problemas para revisar as súas respostas.

559
00:28:41,760 --> 00:28:47,070
Estes foron deseñados para preto
relacionar-se e unirse ao que

560
00:28:47,070 --> 00:28:48,400
ten que facer no set problema.

561
00:28:48,400 --> 00:28:53,820
Entón eu animou-vos a practicar este
no seu propio país e, a continuación, usar o código para

562
00:28:53,820 --> 00:28:54,660
comprobar as súas respostas.

563
00:28:54,660 --> 00:28:57,060
Porque quero pasar ao hash
mesas nalgún momento na sección.

564
00:28:57,060 --> 00:28:58,150
Por iso, non pode ir con el en todo momento.

565
00:28:58,150 --> 00:28:59,960
Pero imos facer o máximo que pudermos agora.

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

567
00:29:00,370 --> 00:29:01,960
Imos comezar.

568
00:29:01,960 --> 00:29:04,770
Asam, como é que imos crear un novo nodo?

569
00:29:04,770 --> 00:29:06,810
>> Audiencia: Vostede struct *.

570
00:29:06,810 --> 00:29:09,640
>> Jason Hirschhorn: Entón nós
teñen que aquí enriba.

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

572
00:29:10,040 --> 00:29:13,530
Vostede estaba dicindo struct *.

573
00:29:13,530 --> 00:29:17,260
>> Audiencia: E entón [? tipo?]
nó ou nodo c.

574
00:29:17,260 --> 00:29:17,780
>> Jason Hirschhorn: Aceptar.

575
00:29:17,780 --> 00:29:19,740
Vou chamalo NEW_NODE
para que poidamos estar consistente.

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

577
00:29:22,646 --> 00:29:33,180
>> Audiencia: E quere establecer que
a cabeza, o primeiro nodo.

578
00:29:33,180 --> 00:29:33,580
>> Jason Hirschhorn: Aceptar.

579
00:29:33,580 --> 00:29:37,290
Entón, agora está a apuntar cara - de xeito que este
non creou un novo nodo aínda.

580
00:29:37,290 --> 00:29:41,380
Isto é só apuntando para o
primeiro nodo da lista.

581
00:29:41,380 --> 00:29:42,630
¿Como crear un novo nodo?

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

583
00:29:45,490 --> 00:29:48,070
Se eu ter de espazo para crear un novo nodo.

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

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

586
00:29:51,710 --> 00:30:00,390
>> Audiencia: O tamaño da estrutura.

587
00:30:00,390 --> 00:30:01,150
>> Jason Hirschhorn: O
tamaño da estrutura.

588
00:30:01,150 --> 00:30:02,400
E o que está a struct chamado?

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

590
00:30:09,670 --> 00:30:09,840
>> Audiencia: Nó?

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

592
00:30:11,640 --> 00:30:17,640
Entón malloc (sizeof (node));
dános espazo.

593
00:30:17,640 --> 00:30:19,740
E é nesa liña -

594
00:30:19,740 --> 00:30:21,740
unha cousa é incorrecta nesta liña.

595
00:30:21,740 --> 00:30:24,430
É NEW_NODE un punteiro a un struct?

596
00:30:24,430 --> 00:30:25,650
Este é un nome xenérico.

597
00:30:25,650 --> 00:30:26,520
Que é -

598
00:30:26,520 --> 00:30:27,450
no, exactamente.

599
00:30:27,450 --> 00:30:29,340
É un nó *.

600
00:30:29,340 --> 00:30:33,010
E o que imos facer logo
nós malloc algo, Asan?

601
00:30:33,010 --> 00:30:34,476
Cal é o primeiro que facemos?

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

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

604
00:30:40,320 --> 00:30:42,430
>> Audiencia: Oh, comprobar se
apunta para o no?

605
00:30:42,430 --> 00:30:43,310
>> Jason Hirschhorn: Exactamente.

606
00:30:43,310 --> 00:30:46,750
Entón, se é igual a NEW_NODE iguais
nulo, o que imos facer?

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

608
00:30:51,650 --> 00:30:54,820
Isto retorna un bool, esa función.

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

610
00:30:57,760 --> 00:30:58,450
Parece bo.

611
00:30:58,450 --> 00:30:59,680
Algo que engadir aí?

612
00:30:59,680 --> 00:31:00,670
Nós imos engadir cousas ao final.

613
00:31:00,670 --> 00:31:03,160
Pero que ata agora parece ser bo.

614
00:31:03,160 --> 00:31:06,170
Crear indicadores actuais e anteriores.

615
00:31:06,170 --> 00:31:08,650
Michael, como fago isto?

616
00:31:08,650 --> 00:31:12,810
>> Audiencia: Vostede tería
para facer un nó *.

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

618
00:31:21,800 --> 00:31:25,502
Vostede tería que facer un non
para NEW_NODE pero para o

619
00:31:25,502 --> 00:31:26,905
nós xa temos.

620
00:31:26,905 --> 00:31:27,230
>> Jason Hirschhorn: Aceptar.

621
00:31:27,230 --> 00:31:29,255
Así, o nodo actual no que estamos.

622
00:31:29,255 --> 00:31:30,505
Vou chamar a que curro.

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

624
00:31:39,650 --> 00:31:39,770
Todo ben.

625
00:31:39,770 --> 00:31:41,620
Nós decidimos que queremos manter
dous, porque necesitamos saber

626
00:31:41,620 --> 00:31:42,870
o que está á súa fronte.

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

628
00:31:45,770 --> 00:31:47,020
Que son inicializados a?

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

630
00:31:49,874 --> 00:31:54,180
>> Audiencia: O seu valor na nosa lista.

631
00:31:54,180 --> 00:31:58,090
>> Jason Hirschhorn: Entón, cal é o
primeiro na nosa lista?

632
00:31:58,090 --> 00:32:04,050
Ou como é que sabemos onde a
inicio da nosa lista é?

633
00:32:04,050 --> 00:32:08,015
>> Audiencia: Non é pasado
para a función?

634
00:32:08,015 --> 00:32:08,466
>> Jason Hirschhorn: Certo.

635
00:32:08,466 --> 00:32:09,716
Foi aprobada en aquí.

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

637
00:32:15,910 --> 00:32:18,980
Entón, se é pasado para a función, o
inicio da lista, o que temos

638
00:32:18,980 --> 00:32:21,270
definir corrente igual?

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

640
00:32:22,110 --> 00:32:22,900
>> Jason Hirschhorn: List.

641
00:32:22,900 --> 00:32:24,090
Isto é exactamente correcto.

642
00:32:24,090 --> 00:32:26,290
Agora que ten o enderezo de
o inicio da nosa lista.

643
00:32:26,290 --> 00:32:28,450
E que dicir anterior?

644
00:32:28,450 --> 00:32:31,920
>> Audiencia: Lista menos un?

645
00:32:31,920 --> 00:32:32,690
>> Jason Hirschhorn: Hai
nada antes del.

646
00:32:32,690 --> 00:32:34,580
Entón o que podemos facer para significar nada?

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

648
00:32:35,050 --> 00:32:35,450
>> Jason Hirschhorn: Yeah.

649
00:32:35,450 --> 00:32:37,950
Isto soa como unha boa idea.

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

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

652
00:32:39,630 --> 00:32:42,850
Vai á lista.

653
00:32:42,850 --> 00:32:45,490
Constantino, canto tempo é que imos
para percorrer a lista?

654
00:32:45,490 --> 00:32:49,010
>> Audiencia: ata chegarmos nulo.

655
00:32:49,010 --> 00:32:49,390
>> Jason Hirschhorn: Aceptar.

656
00:32:49,390 --> 00:32:50,430
Polo tanto, se, á vez, polo loop.

657
00:32:50,430 --> 00:32:52,200
O que estamos facendo?

658
00:32:52,200 --> 00:32:53,320
>> Audiencia: Quizais un loop?

659
00:32:53,320 --> 00:32:53,910
>> Jason Hirschhorn: Imos facer un loop for.

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

661
00:32:55,870 --> 00:33:02,465
>> Audiencia: E dicimos para -

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

663
00:33:09,764 --> 00:33:13,390
ata que o punteiro actual
non é igual a cero.

664
00:33:13,390 --> 00:33:19,160
>> Jason Hirschhorn: Entón, se sabemos que o
condición, como podemos escribir un loop

665
00:33:19,160 --> 00:33:21,740
baseado fóra desa condición.

666
00:33:21,740 --> 00:33:24,380
Que tipo de lazo que debemos usar?

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

668
00:33:25,260 --> 00:33:25,590
>> Jason Hirschhorn: Yeah.

669
00:33:25,590 --> 00:33:27,130
Isto fai máis sentido en base
fóra do que dixo.

670
00:33:27,130 --> 00:33:29,430
Se nós só quere ir para nós sería
só sei que cousa, non faría

671
00:33:29,430 --> 00:33:31,680
sentido de facer un loop while.

672
00:33:31,680 --> 00:33:39,880
Aínda actual non é igual a cero,
se o valor é inferior a este nodo.

673
00:33:39,880 --> 00:33:41,650
Akshar, dáme desa liña.

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

675
00:33:48,810 --> 00:33:56,955
>> Audiencia: Se a cadea-> n
n menor que o valor.

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

677
00:34:00,170 --> 00:34:03,260
Ou desfacer iso.

678
00:34:03,260 --> 00:34:06,140
Cambiar este soporte.

679
00:34:06,140 --> 00:34:06,620
>> Jason Hirschhorn: Sentímolo.

680
00:34:06,620 --> 00:34:08,760
>> Audiencia: Cambiar o soporte.

681
00:34:08,760 --> 00:34:10,914
>> Jason Hirschhorn: Entón, se é
maior que o valor.

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

683
00:34:18,719 --> 00:34:22,120
Porque iso é confuso co
comentario anterior, eu vou facelo.

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

685
00:34:22,480 --> 00:34:25,125
O noso valor é menor que iso
no, o que imos facer?

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

687
00:34:25,540 --> 00:34:26,710
Teño-o aquí.

688
00:34:26,710 --> 00:34:27,960
Inserir antes.

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

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

691
00:34:32,370 --> 00:34:33,933
Como facemos iso?

692
00:34:33,933 --> 00:34:34,900
>> Audiencia: Éme aínda?

693
00:34:34,900 --> 00:34:36,150
>> Jason Hirschhorn: Yeah.

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

695
00:34:38,520 --> 00:34:39,770
>> Audiencia: Entra -

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

697
00:34:42,909 --> 00:34:44,159
NEW_NODE-> seguinte.

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

699
00:34:46,770 --> 00:34:50,163
>> Jason Hirschhorn: Entón, cal é
que será igual?

700
00:34:50,163 --> 00:34:52,070
>> Audiencia: Vai igual actual.

701
00:34:52,070 --> 00:34:53,889
>> Jason Hirschhorn: Exactamente.

702
00:34:53,889 --> 00:34:55,730
E así o outro -

703
00:34:55,730 --> 00:34:56,730
o que máis necesitamos para actualizar?

704
00:34:56,730 --> 00:34:59,982
>> Audiencia: Asegúrese de que pasado é igual a cero.

705
00:34:59,982 --> 00:35:01,870
>> Jason Hirschhorn: se prev -

706
00:35:01,870 --> 00:35:03,730
por iso, se prev igual nulo.

707
00:35:03,730 --> 00:35:05,990
>> Audiencia: Isto significa que vai
para facer a cabeza.

708
00:35:05,990 --> 00:35:06,780
>> Jason Hirschhorn: Isto significa que
tornouse a cabeza.

709
00:35:06,780 --> 00:35:07,620
Entón o que facemos?

710
00:35:07,620 --> 00:35:12,510
>> Audiencia: Facemos cabeza coincide NEW_NODE.

711
00:35:12,510 --> 00:35:16,690
>> Jason Hirschhorn: Cabeza
coincide NEW_NODE.

712
00:35:16,690 --> 00:35:20,540
E por cabeza aquí, non lista?

713
00:35:20,540 --> 00:35:24,940
>> Audiencia: Por cabeza é unha organización global
variable, que é o punto 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
Aceptar.

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

718
00:35:36,150 --> 00:35:53,796
>> Audiencia: Entón máis prev->
preto coincide NEW_NODE.

719
00:35:53,796 --> 00:35:55,080
E entón voltar true.

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

721
00:35:59,560 --> 00:36:02,700
>> Jason Hirschhorn: Onde
montar final NEW_NODE?

722
00:36:02,700 --> 00:36:04,850
>> Audiencia: eu -

723
00:36:04,850 --> 00:36:06,180
Eu establecer que ao principio.

724
00:36:06,180 --> 00:36:07,430
>> Jason Hirschhorn: Entón o que liña?

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

726
00:36:10,000 --> 00:36:12,598
>> Audiencia: Tras a instrución if
comprobando se é coñecido.

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

728
00:36:13,057 --> 00:36:18,335
>> Audiencia: Eu faría NEW_NODE-> n
igual valor.

729
00:36:18,335 --> 00:36:19,585
>> Jason Hirschhorn: Parece bo.

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

731
00:36:21,740 --> 00:36:25,090
Probablemente ten sentido - non
Debe saber o que estamos na lista

732
00:36:25,090 --> 00:36:26,280
porque estamos lidando só
cunha lista.

733
00:36:26,280 --> 00:36:29,560
Así, unha declaración de función mellor para
isto é só para se librar desa

734
00:36:29,560 --> 00:36:34,360
enteiramente e só introducir
un valor na cabeza.

735
00:36:34,360 --> 00:36:35,930
Nós nin sequera ten que saber
que lista que está dentro

736
00:36:35,930 --> 00:36:39,140
Pero vou perder la por agora e
entón cambia-lo despois da actualización

737
00:36:39,140 --> 00:36:42,590
os diapositivas e código.

738
00:36:42,590 --> 00:36:44,980
Así que parece ser bo para agora.

739
00:36:44,980 --> 00:36:46,560
O valor - que pode facelo en liña?

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

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

742
00:36:52,240 --> 00:36:53,840
o que facemos aquí, Noah.

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

744
00:36:57,890 --> 00:37:07,100
>> Audiencia: O valor é maior
que curro-> n -

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

746
00:37:16,830 --> 00:37:18,240
>> Jason Hirschhorn: Como facer
imos ao seguinte nodo?

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

748
00:37:27,760 --> 00:37:30,530
>> Audiencia: curro-> n é
igual a NEW_NODE.

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

750
00:37:37,630 --> 00:37:39,195
>> Jason Hirschhorn: Entón n é
que parte da estrutura?

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

752
00:37:43,065 --> 00:37:46,020
O enteiro.

753
00:37:46,020 --> 00:37:50,420
E NEW_NODE é un enlace a un nodo.

754
00:37:50,420 --> 00:37:51,880
Entón, o que parte do curro hai actualizar?

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

756
00:38:03,900 --> 00:38:05,400
Se non é n, entón o que é a outra parte?

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

758
00:38:21,680 --> 00:38:22,810
Noé, que é a outra parte.

759
00:38:22,810 --> 00:38:23,570
>> Audiencia: Oh, á beira.

760
00:38:23,570 --> 00:38:25,645
>> Jason Hirschhorn: Next, exactamente.

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

762
00:38:26,410 --> 00:38:28,770
A continuación é a correcta.

763
00:38:28,770 --> 00:38:31,540
E o que máis necesitamos
para actualizar, Noah?

764
00:38:31,540 --> 00:38:32,840
>> Audiencia: Os punteiros.

765
00:38:32,840 --> 00:38:34,840
>> Jason Hirschhorn: Entón
actualizamos actual.

766
00:38:34,840 --> 00:38:36,090
>> Audiencia: Prev-> seguinte.

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

768
00:38:48,160 --> 00:38:49,410
>> Jason Hirschhorn: Yeah.

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

770
00:38:57,465 --> 00:38:58,370
OK, imos facer unha pausa.

771
00:38:58,370 --> 00:39:02,200
Quen pode axudarnos aquí?

772
00:39:02,200 --> 00:39:03,385
Manu, o que temos que facer?

773
00:39:03,385 --> 00:39:05,615
>> Audiencia: Ten que definir
el igual a curro-> seguinte.

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

775
00:39:09,110 --> 00:39:11,630
Pero facelo antes da liña anterior.

776
00:39:11,630 --> 00:39:12,880
>> Jason Hirschhorn: Aceptar.

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

778
00:39:16,590 --> 00:39:18,260
Algo máis?

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

780
00:39:19,170 --> 00:39:22,680
>> Audiencia: Eu non creo que é
destínase a cambiar curro-> seguinte.

781
00:39:22,680 --> 00:39:29,270
Eu creo que está destinado a facer iguais curro
curro-> xunto a ir ao seguinte nodo.

782
00:39:29,270 --> 00:39:30,500
>> Jason Hirschhorn: So sorry, onde?

783
00:39:30,500 --> 00:39:32,680
En cal liña?

784
00:39:32,680 --> 00:39:33,420
Esta liña?

785
00:39:33,420 --> 00:39:33,750
>> Audiencia: Yeah.

786
00:39:33,750 --> 00:39:35,745
Fai curro igual curro-> seguinte.

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

788
00:39:39,690 --> 00:39:43,360
>> Jason Hirschhorn: Entón, iso é correcto
porque a cadea é unha

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

790
00:39:45,220 --> 00:39:48,550
E queremos que el apunta ao seguinte
nodo do que está a recibir actualmente

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

792
00:39:49,930 --> 00:39:54,410
Curro si ten un lado.

793
00:39:54,410 --> 00:39:58,620
Pero, se fósemos actualizar curr.next, nós
sería actualizar a nota real

794
00:39:58,620 --> 00:40:01,430
en si, non onde esta
punteiro estaba apuntando.

795
00:40:01,430 --> 00:40:02,680
E sobre esta liña, con todo.

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
>> Audiencia: Prev-> next igual curro.

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

800
00:40:12,500 --> 00:40:19,440
>> Jason Hirschhorn: Entón, de novo, se prev é un
punteiro a un nodo, prev-> seguinte é o

801
00:40:19,440 --> 00:40:23,020
punteiro efectiva no nodo.

802
00:40:23,020 --> 00:40:27,190
Polo tanto, esta sería a actualización dun
punteiro en un nó para curro.

803
00:40:27,190 --> 00:40:28,570
Non queremos para actualizar
unha ligazón nun nodo.

804
00:40:28,570 --> 00:40:30,570
Queremos actualizar anterior.

805
00:40:30,570 --> 00:40:31,850
Entón, como imos facelo?

806
00:40:31,850 --> 00:40:34,250
>> Audiencia: Sería só prev.

807
00:40:34,250 --> 00:40:34,565
>> Jason Hirschhorn: Certo.

808
00:40:34,565 --> 00:40:35,560
Ant é unha ligazón a un nodo.

809
00:40:35,560 --> 00:40:38,750
Agora, estamos cambiando-o para un
novo punteiro a un nodo.

810
00:40:38,750 --> 00:40:40,830
Aceptar Imos descender.

811
00:40:40,830 --> 00:40:41,940
Finalmente, esta última condición.

812
00:40:41,940 --> 00:40:44,896
Jeff, o que facemos aquí?

813
00:40:44,896 --> 00:40:47,515
>> Audiencia: O valor é
igual a curro-> n.

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

815
00:40:51,030 --> 00:40:51,300
>> Jason Hirschhorn: Sentímolo.

816
00:40:51,300 --> 00:40:52,372
Oh meu Deus.

817
00:40:52,372 --> 00:40:54,330
O que?

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

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

820
00:41:01,050 --> 00:41:02,300
O que imos facer?

821
00:41:02,300 --> 00:41:04,760

822
00:41:04,760 --> 00:41:10,950
>> Audiencia: Ía liberar o noso NEW_NODE,
e entón voltar false.

823
00:41:10,950 --> 00:41:21,410

824
00:41:21,410 --> 00:41:23,460
>> Jason Hirschhorn: Isto é o que
temos escrito ata agora.

825
00:41:23,460 --> 00:41:25,710
Alguén ten algunha cousa
a engadir antes de facer?

826
00:41:25,710 --> 00:41:35,460

827
00:41:35,460 --> 00:41:35,710
Aceptar.

828
00:41:35,710 --> 00:41:36,960
Imos probar.

829
00:41:36,960 --> 00:41:44,180

830
00:41:44,180 --> 00:41:46,110
Control poderá chegar ao final
dunha función non baleiro.

831
00:41:46,110 --> 00:41:48,310
Rar, o que está a suceder?

832
00:41:48,310 --> 00:41:51,380
>> Audiencia: Debe poñer retorno
certo fóra do loop while?

833
00:41:51,380 --> 00:41:53,900

834
00:41:53,900 --> 00:41:54,400
>> Jason Hirschhorn: Eu non sei.

835
00:41:54,400 --> 00:41:54,780
Vostede me quere?

836
00:41:54,780 --> 00:41:55,520
>> Audiencia: Non importa.

837
00:41:55,520 --> 00:41:56,350
Non

838
00:41:56,350 --> 00:41:57,180
>> Jason Hirschhorn: Akshar?

839
00:41:57,180 --> 00:41:59,460
>> Audiencia: Coido que quería
poñer retorno falso ao final

840
00:41:59,460 --> 00:42:02,230
do loop while.

841
00:42:02,230 --> 00:42:03,270
>> Jason Hirschhorn: Entón, onde
queres que vaia?

842
00:42:03,270 --> 00:42:05,270
>> Audiencia: Como fóra do loop while.

843
00:42:05,270 --> 00:42:08,800
Entón, se saír do loop while que medios
que xa chegou ao fin e

844
00:42:08,800 --> 00:42:09,980
nada aconteceu.

845
00:42:09,980 --> 00:42:10,410
>> Jason Hirschhorn: Aceptar.

846
00:42:10,410 --> 00:42:12,340
Entón, o que facemos aquí?

847
00:42:12,340 --> 00:42:13,702
>> Audiencia: Vostede volve teito
alí tamén.

848
00:42:13,702 --> 00:42:15,040
>> Jason Hirschhorn: Oh, nós
facelo en ambos os lugares?

849
00:42:15,040 --> 00:42:15,650
>> Audiencia: Yeah.

850
00:42:15,650 --> 00:42:16,900
>> Jason Hirschhorn: Aceptar.

851
00:42:16,900 --> 00:42:24,840

852
00:42:24,840 --> 00:42:26,160
Imos?

853
00:42:26,160 --> 00:42:26,980
Oh meu Deus.

854
00:42:26,980 --> 00:42:27,290
Sinto moito.

855
00:42:27,290 --> 00:42:28,480
Pido desculpas para a pantalla.

856
00:42:28,480 --> 00:42:30,530
É unha especie de surtando sobre nós.

857
00:42:30,530 --> 00:42:31,520
Entón, escolle unha opción.

858
00:42:31,520 --> 00:42:35,260
Cero, por código, sae do programa.

859
00:42:35,260 --> 00:42:36,700
Un inserir algo.

860
00:42:36,700 --> 00:42:37,990
Imos introducir tres.

861
00:42:37,990 --> 00:42:42,900

862
00:42:42,900 --> 00:42:45,380
A inserción non foi exitosa.

863
00:42:45,380 --> 00:42:46,500
Vou imprimir.

864
00:42:46,500 --> 00:42:48,050
Eu non teño nada.

865
00:42:48,050 --> 00:42:48,450
Aceptar.

866
00:42:48,450 --> 00:42:50,250
Talvez fose só un acaso.

867
00:42:50,250 --> 00:42:52,810
Insire un.

868
00:42:52,810 --> 00:42:55,770
Non exitosa.

869
00:42:55,770 --> 00:42:57,470
Aceptar.

870
00:42:57,470 --> 00:43:02,400
Imos percorrer GDB moi rapidamente
para comprobar o que está pasando.

871
00:43:02,400 --> 00:43:06,055
>> Lembre gdb. / O nome do seu
programa nos deixa en GDB.

872
00:43:06,055 --> 00:43:07,610
Isto é unha morea de tratar?

873
00:43:07,610 --> 00:43:08,560
O palpebrar?

874
00:43:08,560 --> 00:43:10,400
Probablemente.

875
00:43:10,400 --> 00:43:12,760
Pecha os ollos e tomar algunha profundidade
respiracións se queda canso

876
00:43:12,760 --> 00:43:13,580
de ollar para el.

877
00:43:13,580 --> 00:43:14,200
Estou en GDB.

878
00:43:14,200 --> 00:43:15,830
Cal é o primeiro que fago en GDB?

879
00:43:15,830 --> 00:43:17,050
Temos que descubrir
o que está pasando aquí.

880
00:43:17,050 --> 00:43:17,310
Imos ver.

881
00:43:17,310 --> 00:43:21,650
Temos seis minutos para a figura
o que está pasando.

882
00:43:21,650 --> 00:43:22,900
Rompe principal.

883
00:43:22,900 --> 00:43:25,950

884
00:43:25,950 --> 00:43:28,130
E entón o que fago?

885
00:43:28,130 --> 00:43:29,180
Carlos?

886
00:43:29,180 --> 00:43:31,060
Executar.

887
00:43:31,060 --> 00:43:32,250
Aceptar.

888
00:43:32,250 --> 00:43:34,160
Imos escoller unha opción.

889
00:43:34,160 --> 00:43:36,330
E o que facer N?

890
00:43:36,330 --> 00:43:38,480
Seguinte.

891
00:43:38,480 --> 00:43:38,950
É.

892
00:43:38,950 --> 00:43:39,740
>> Audiencia: Non mencionou -

893
00:43:39,740 --> 00:43:45,230
non dixo que a cabeza, que era
iniciar con nulo ao principio.

894
00:43:45,230 --> 00:43:47,140
Pero eu penso que dixo que estaba ben.

895
00:43:47,140 --> 00:43:50,040

896
00:43:50,040 --> 00:43:52,640
>> Jason Hirschhorn: Imos - imos ollar
en GDB, e despois imos volver.

897
00:43:52,640 --> 00:43:54,910
Pero parece que xa ten
algunhas ideas sobre o que está a suceder.

898
00:43:54,910 --> 00:43:58,340
Por iso, queremos introducir algo.

899
00:43:58,340 --> 00:43:59,390
Aceptar.

900
00:43:59,390 --> 00:44:00,150
Temos inserir.

901
00:44:00,150 --> 00:44:00,770
Por favor, introduza un int.

902
00:44:00,770 --> 00:44:01,990
Nós imos introducir tres.

903
00:44:01,990 --> 00:44:03,000
E entón eu estou nesa liña.

904
00:44:03,000 --> 00:44:07,030
Como fago para ir comezar a depuración
función da inserción coñecido?

905
00:44:07,030 --> 00:44:08,280
Oh meu Deus.

906
00:44:08,280 --> 00:44:10,990

907
00:44:10,990 --> 00:44:12,240
Isto é un monte.

908
00:44:12,240 --> 00:44:14,372

909
00:44:14,372 --> 00:44:16,445
É que pirando moito?

910
00:44:16,445 --> 00:44:19,696

911
00:44:19,696 --> 00:44:21,680
>> Audiencia: Ah, el morreu.

912
00:44:21,680 --> 00:44:22,930
>> Jason Hirschhorn: Eu só
tirou-o para fora.

913
00:44:22,930 --> 00:44:27,364

914
00:44:27,364 --> 00:44:28,310
Aceptar.

915
00:44:28,310 --> 00:44:29,560
>> Audiencia: Quizais sexa o
o outro extremo do fío.

916
00:44:29,560 --> 00:44:37,000

917
00:44:37,000 --> 00:44:39,470
>> Jason Hirschhorn: Guau.

918
00:44:39,470 --> 00:44:42,330
Así, a liña de fondo -

919
00:44:42,330 --> 00:44:43,470
o que dixo?

920
00:44:43,470 --> 00:44:46,040
>> Audiencia: Eu dixo a ironía de técnico
dificultades nesta clase.

921
00:44:46,040 --> 00:44:46,410
>> Jason Hirschhorn: Eu sei.

922
00:44:46,410 --> 00:44:48,660
Se eu tivese o control sobre esta parte.

923
00:44:48,660 --> 00:44:49,910
[Inaudível]

924
00:44:49,910 --> 00:44:54,430

925
00:44:54,430 --> 00:44:55,400
Isto soa moi ben.

926
00:44:55,400 --> 00:44:58,680
Por que vostedes non comezar a pensar sobre
o que poderiamos ter feito de malo,

927
00:44:58,680 --> 00:45:01,140
e imos estar de volta en 90 segundos.

928
00:45:01,140 --> 00:46:18,160

929
00:46:18,160 --> 00:46:23,010
>> Avica, vou preguntar a vostede como ir
insert_node dentro depurá-lo.

930
00:46:23,010 --> 00:46:28,940

931
00:46:28,940 --> 00:46:31,460
Entón é aquí que deixamos atrás.

932
00:46:31,460 --> 00:46:35,110
¿Como entrar insert_node, Avica,
para examinar o que está pasando?

933
00:46:35,110 --> 00:46:36,360
A orde GDB?

934
00:46:36,360 --> 00:46:41,050

935
00:46:41,050 --> 00:46:42,390
Pausa non me levaría para dentro.

936
00:46:42,390 --> 00:46:46,200

937
00:46:46,200 --> 00:46:47,130
A Marquise sabe?

938
00:46:47,130 --> 00:46:48,240
>> Audiencia: O que?

939
00:46:48,240 --> 00:46:51,780
>> Jason Hirschhorn: Cal comando GDB
Eu uso para ir dentro desa función?

940
00:46:51,780 --> 00:46:52,070
>> Audiencia: Step?

941
00:46:52,070 --> 00:46:55,140
>> Jason Hirschhorn: Step vía
S. Isto me leva cara a dentro.

942
00:46:55,140 --> 00:46:55,476
Aceptar.

943
00:46:55,476 --> 00:46:58,040
NEW_NODE mallocing algún espazo.

944
00:46:58,040 --> 00:46:59,120
Iso todo parece que vai.

945
00:46:59,120 --> 00:47:00,370
Imos examinar NEW_NODE.

946
00:47:00,370 --> 00:47:03,270

947
00:47:03,270 --> 00:47:05,410
Ten algún enderezo de memoria.

948
00:47:05,410 --> 00:47:07,440
Imos comprobar -

949
00:47:07,440 --> 00:47:08,500
iso é todo correcto.

950
00:47:08,500 --> 00:47:12,220
Entón, todo aquí parece
estar funcionando correctamente.

951
00:47:12,220 --> 00:47:14,530
>> Audiencia: Cal é a diferenza
entre P e exhibición?

952
00:47:14,530 --> 00:47:16,160
>> Jason Hirschhorn: P está a imprimir.

953
00:47:16,160 --> 00:47:19,310
E así que está pregunta o que é o
diferenza entre isto e isto?

954
00:47:19,310 --> 00:47:22,330
Neste caso, nada.

955
00:47:22,330 --> 00:47:26,960
Pero normalmente hai
algunhas diferenzas.

956
00:47:26,960 --> 00:47:28,220
E ten que mirar na guía de GDB.

957
00:47:28,220 --> 00:47:29,560
Pero neste caso, nada.

958
00:47:29,560 --> 00:47:31,460
Nós tendemos a usar impresión, porén, porque
Non necesitamos facer moito máis do que

959
00:47:31,460 --> 00:47:33,960
imprimir un único valor.

960
00:47:33,960 --> 00:47:34,640
>> Aceptar.

961
00:47:34,640 --> 00:47:40,300
Polo tanto, estamos na liña 80 do noso código,
configuración nodo * curro igual a lista.

962
00:47:40,300 --> 00:47:42,500
Imos imprimir curro.

963
00:47:42,500 --> 00:47:45,260

964
00:47:45,260 --> 00:47:46,840
El é igual a lista.

965
00:47:46,840 --> 00:47:48,850
Doce.

966
00:47:48,850 --> 00:47:49,340
Espera.

967
00:47:49,340 --> 00:47:50,590
El é igual a algo.

968
00:47:50,590 --> 00:47:53,680

969
00:47:53,680 --> 00:47:56,190
Isto non parece certo.

970
00:47:56,190 --> 00:47:56,840
Alí imos nós.

971
00:47:56,840 --> 00:47:59,470
É porque en GDB, non si
é a liña que está nel

972
00:47:59,470 --> 00:48:00,330
non executou aínda.

973
00:48:00,330 --> 00:48:03,100
Entón, ten que realmente escribir
próximo para realizar a liña

974
00:48:03,100 --> 00:48:05,230
antes de ver os resultados.

975
00:48:05,230 --> 00:48:06,680
Entón aquí estamos nós.

976
00:48:06,680 --> 00:48:09,490
Nós só executou esta liña,
anterior é igual a cero.

977
00:48:09,490 --> 00:48:13,590
Entón, de novo, se imprimir anterior
non veremos nada raro.

978
00:48:13,590 --> 00:48:18,680
Pero se realmente realizar que
liña, entón imos ver

979
00:48:18,680 --> 00:48:20,380
que a devandita liña de traballado.

980
00:48:20,380 --> 00:48:21,060
>> Polo tanto, temos curro.

981
00:48:21,060 --> 00:48:23,180
Estas son boas.

982
00:48:23,180 --> 00:48:24,010
Non?

983
00:48:24,010 --> 00:48:28,130
Agora estamos nesa liña aquí.

984
00:48:28,130 --> 00:48:29,310
Mentres curro non é igual a cero.

985
00:48:29,310 --> 00:48:31,110
Ben, o que fai curro iguais?

986
00:48:31,110 --> 00:48:32,450
Nós só vimos el igualou nulo.

987
00:48:32,450 --> 00:48:33,210
Imprimir lo.

988
00:48:33,210 --> 00:48:35,110
Vou imprimir lo de novo.

989
00:48:35,110 --> 00:48:36,720
Así é que, mentres lazo
vai realizar?

990
00:48:36,720 --> 00:48:37,270
>> Audiencia: Non

991
00:48:37,270 --> 00:48:39,790
>> Jason Hirschhorn: Entón, cando eu escriba que
liña, ve que pulou todo o camiño

992
00:48:39,790 --> 00:48:41,390
ata o fondo, voltar false.

993
00:48:41,390 --> 00:48:44,520
E entón nós estamos indo para voltar false
e volver para o noso programa e

994
00:48:44,520 --> 00:48:48,020
finalmente, imprimir, como vimos,
a inserción non foi exitosa.

995
00:48:48,020 --> 00:48:51,010
Entón, alguén ten algunha idea sobre o que
o que necesitamos facer para solucionar isto?

996
00:48:51,010 --> 00:48:54,200

997
00:48:54,200 --> 00:48:57,570
Vou esperar ata que eu vexa
un par de mans levantadas.

998
00:48:57,570 --> 00:48:58,830
Non realizar este.

999
00:48:58,830 --> 00:49:01,660
Teña presente, este foi o primeiro
que estabamos facendo.

1000
00:49:01,660 --> 00:49:02,430
Non vou facer unha parella.

1001
00:49:02,430 --> 00:49:03,670
Vou facer algúns.

1002
00:49:03,670 --> 00:49:04,830
Por unha parella significa dous.

1003
00:49:04,830 --> 00:49:07,620
Vou agardar por máis de dous.

1004
00:49:07,620 --> 00:49:10,690
>> A primeira inserción, curro,
por omisión é igual a cero.

1005
00:49:10,690 --> 00:49:14,050
E este lazo só executa
curro se non é nulo.

1006
00:49:14,050 --> 00:49:18,740
Entón, como podo solucionar isto?

1007
00:49:18,740 --> 00:49:19,990
Vexo tres mans.

1008
00:49:19,990 --> 00:49:28,490

1009
00:49:28,490 --> 00:49:29,780
Vou agardar por máis de tres.

1010
00:49:29,780 --> 00:49:33,460

1011
00:49:33,460 --> 00:49:35,940
Marcus, o que pensas?

1012
00:49:35,940 --> 00:49:37,730
>> Audiencia: Ben, se precisa del para
executar máis dunha vez, só se

1013
00:49:37,730 --> 00:49:39,948
cambia-lo para un loop do-while.

1014
00:49:39,948 --> 00:49:41,250
>> Jason Hirschhorn: Aceptar.

1015
00:49:41,250 --> 00:49:44,240
Será que isto resolve o noso problema, entón?

1016
00:49:44,240 --> 00:49:47,750
>> Audiencia: Neste caso, non debido a
o feito de que a lista está baleira.

1017
00:49:47,750 --> 00:49:52,150
Entón probablemente só precisa engadir
unha declaración de que o loop

1018
00:49:52,150 --> 00:49:55,312
logo ten que estar no extremo da
da lista, en que punto

1019
00:49:55,312 --> 00:49:56,562
pode só inserir-lo.

1020
00:49:56,562 --> 00:49:58,920

1021
00:49:58,920 --> 00:49:59,680
>> Jason Hirschhorn: Eu gusto diso.

1022
00:49:59,680 --> 00:50:00,500
Isto ten sentido.

1023
00:50:00,500 --> 00:50:03,390
O circuíto sae -

1024
00:50:03,390 --> 00:50:04,800
porque vai voltar false aquí.

1025
00:50:04,800 --> 00:50:08,220
Entón, se o loop, entón estamos en
Ao final da lista, ou que o

1026
00:50:08,220 --> 00:50:10,690
inicio dunha lista, se non hai nada no
, O que é o mesmo que o final.

1027
00:50:10,690 --> 00:50:12,770
Entón, agora queremos introducir
algo aquí.

1028
00:50:12,770 --> 00:50:17,380
Entón, como parece que o código, Marcus?

1029
00:50:17,380 --> 00:50:21,600
>> Audiencia: Se xa ten o nó
malloced, podería simplemente dicir

1030
00:50:21,600 --> 00:50:25,400
NEW_NODE-> next igual a nulo porque
ten que ser ao final.

1031
00:50:25,400 --> 00:50:27,510
Ou NEW_NODE-> next igual a nulo.

1032
00:50:27,510 --> 00:50:27,765
>> Jason Hirschhorn: Aceptar.

1033
00:50:27,765 --> 00:50:28,190
Sentímolo.

1034
00:50:28,190 --> 00:50:35,760
NEW_NODE-> next igual a nulo
porque estamos na final.

1035
00:50:35,760 --> 00:50:36,460
Isto non poñer-lo dentro

1036
00:50:36,460 --> 00:50:37,710
Como é que imos poñelas na lista?

1037
00:50:37,710 --> 00:50:46,130

1038
00:50:46,130 --> 00:50:46,460
Correcto.

1039
00:50:46,460 --> 00:50:47,750
Isto é só configure-lo igual a.

1040
00:50:47,750 --> 00:50:50,940
Non coma nós, en realidade,
poñelas na lista?

1041
00:50:50,940 --> 00:50:54,170
O que está a apuntar cara o
final da lista?

1042
00:50:54,170 --> 00:50:56,090
>> Audiencia: Head.

1043
00:50:56,090 --> 00:50:57,566
>> Jason Hirschhorn: Sentímolo?

1044
00:50:57,566 --> 00:50:59,440
>> Audiencia: Cabeza está a apuntar
ao final da lista.

1045
00:50:59,440 --> 00:51:01,480
>> Jason Hirschhorn: Se non hai nada en
a lista, a cabeza está a apuntar cara a

1046
00:51:01,480 --> 00:51:04,170
final da lista.

1047
00:51:04,170 --> 00:51:06,920
Entón, que vai traballar para a
primeira inserción.

1048
00:51:06,920 --> 00:51:09,810
E se hai un par
cousas na lista?

1049
00:51:09,810 --> 00:51:12,470
Do que nós non queremos para definir
cabeza igual NEW_NODE.

1050
00:51:12,470 --> 00:51:13,790
O que queremos facer alí?

1051
00:51:13,790 --> 00:51:15,610
Si?

1052
00:51:15,610 --> 00:51:16,860
Probablemente anterior.

1053
00:51:16,860 --> 00:51:23,560

1054
00:51:23,560 --> 00:51:24,810
Será que funciona?

1055
00:51:24,810 --> 00:51:28,950

1056
00:51:28,950 --> 00:51:33,050
Lembre que é só anterior
un punteiro a un nodo.

1057
00:51:33,050 --> 00:51:34,770
E anterior é unha variable local.

1058
00:51:34,770 --> 00:51:38,080
Polo tanto, esta liña vai definir unha variable local,
anterior, igual ou

1059
00:51:38,080 --> 00:51:39,380
apuntando a este novo nodo.

1060
00:51:39,380 --> 00:51:41,500
Isto realmente non vai poñelas
na nosa lista, con todo.

1061
00:51:41,500 --> 00:51:44,330
Como é que imos poñer-lo na nosa lista?

1062
00:51:44,330 --> 00:51:45,620
Akchar?

1063
00:51:45,620 --> 00:51:46,870
>> Audiencia: Eu creo que
facer current-> seguinte.

1064
00:51:46,870 --> 00:51:50,186

1065
00:51:50,186 --> 00:51:52,550
>> Jason Hirschhorn: Aceptar.

1066
00:51:52,550 --> 00:51:54,010
curro-> seguinte.

1067
00:51:54,010 --> 00:51:58,768
Entón, de novo, a única razón que nós estamos para abaixo
aquí é, o que fai de corrente igual?

1068
00:51:58,768 --> 00:51:59,760
>> Audiencia: Igual nulo.

1069
00:51:59,760 --> 00:52:01,790
>> Jason Hirschhorn: E entón o que
acontece se o facemos null-> next?

1070
00:52:01,790 --> 00:52:02,810
O que se ve?

1071
00:52:02,810 --> 00:52:04,060
Nós imos ter un fallo de segmento.

1072
00:52:04,060 --> 00:52:06,600

1073
00:52:06,600 --> 00:52:08,880
>> Audiencia: Do curro igual nulo.

1074
00:52:08,880 --> 00:52:10,760
>> Jason Hirschhorn: Isto é o mesmo
como prev, con todo, porque non hai

1075
00:52:10,760 --> 00:52:12,820
unha variable local que estamos definindo
igual a este novo nodo.

1076
00:52:12,820 --> 00:52:16,680

1077
00:52:16,680 --> 00:52:20,920
Imos volver á nosa imaxe
de inserir algo.

1078
00:52:20,920 --> 00:52:25,500
Digamos que está inserindo ao final
da lista, polo que aquí.

1079
00:52:25,500 --> 00:52:30,010
Temos un punteiro actual que é
apuntando nulo e un punto anterior

1080
00:52:30,010 --> 00:52:32,800
que está a apuntar cara 8.

1081
00:52:32,800 --> 00:52:35,330
Entón o que necesitamos actualizar, Avi?

1082
00:52:35,330 --> 00:52:36,680
>> Audiencia: Anterior-> next?

1083
00:52:36,680 --> 00:52:41,980
>> Jason Hirschhorn: Anterior-> seguinte é o que
queremos actualizar porque iso

1084
00:52:41,980 --> 00:52:44,960
vai realmente inserir-lo no
Ao final da lista.

1085
00:52:44,960 --> 00:52:47,220
Aínda temos un erro, con todo,
que imos correr en.

1086
00:52:47,220 --> 00:52:50,090
¿Que é iso erro?

1087
00:52:50,090 --> 00:52:50,790
Si?

1088
00:52:50,790 --> 00:52:53,860
>> Audiencia: Vai volver
falsa neste caso?

1089
00:52:53,860 --> 00:52:56,380
>> Jason Hirschhorn: Ah, e é
Vai voltar false.

1090
00:52:56,380 --> 00:52:57,430
Pero hai outro erro.

1091
00:52:57,430 --> 00:52:58,930
Entón, imos ter para poñer en return true.

1092
00:52:58,930 --> 00:53:01,370
>> Audiencia: O anterior aínda igual
nula na parte superior da lista de?

1093
00:53:01,370 --> 00:53:03,645
>> Jason Hirschhorn: aínda Entón anterior
é igual a nulo ao principio.

1094
00:53:03,645 --> 00:53:07,480

1095
00:53:07,480 --> 00:53:10,440
Entón, como podemos superar isto?

1096
00:53:10,440 --> 00:53:10,950
Si?

1097
00:53:10,950 --> 00:53:15,280
>> Audiencia: Eu creo que pode facer unha comprobación
antes do loop while para ver se é

1098
00:53:15,280 --> 00:53:16,610
unha lista baleira.

1099
00:53:16,610 --> 00:53:17,000
>> Jason Hirschhorn: Aceptar.

1100
00:53:17,000 --> 00:53:17,710
Entón imos aquí.

1101
00:53:17,710 --> 00:53:18,530
Fai unha comprobación.

1102
00:53:18,530 --> 00:53:19,380
Se -

1103
00:53:19,380 --> 00:53:20,770
>> Audiencia: Entón, se a cabeza
coincide é igual a cero.

1104
00:53:20,770 --> 00:53:24,300

1105
00:53:24,300 --> 00:53:26,320
>> Jason Hirschhorn: Se a cabeza
coincide é igual a null -

1106
00:53:26,320 --> 00:53:27,790
que vai dicir se é unha lista baleira.

1107
00:53:27,790 --> 00:53:31,090
>> Audiencia: E entón
facer a cabeza é igual a novo.

1108
00:53:31,090 --> 00:53:34,740
>> Jason Hirschhorn: Cabeza
coincide NEW_NODE?

1109
00:53:34,740 --> 00:53:35,730
E o que máis necesitamos facer?

1110
00:53:35,730 --> 00:53:37,020
>> Audiencia: E entón voltar true.

1111
00:53:37,020 --> 00:53:37,535
>> Jason Hirschhorn: Non é ben así.

1112
00:53:37,535 --> 00:53:38,785
Estamos perdendo unha etapa.

1113
00:53:38,785 --> 00:53:41,590

1114
00:53:41,590 --> 00:53:43,710
>> Audiencia: NEW_NODE seguinte
ten que apuntar para null.

1115
00:53:43,710 --> 00:53:44,570
>> Jason Hirschhorn: Exactamente, Alden.

1116
00:53:44,570 --> 00:53:46,600
E entón podemos voltar true.

1117
00:53:46,600 --> 00:53:47,560
Aceptar.

1118
00:53:47,560 --> 00:53:51,630
Senón que é unha boa idea para facer as cousas
ao final da lista, dereita?

1119
00:53:51,630 --> 00:53:51,950
Todo ben.

1120
00:53:51,950 --> 00:53:54,450
Aínda pode realmente comezar
ao final da lista.

1121
00:53:54,450 --> 00:53:57,870
Entón é este código ben se estamos na
final da lista e hai algúns

1122
00:53:57,870 --> 00:53:59,120
cousas na lista?

1123
00:53:59,120 --> 00:54:01,830

1124
00:54:01,830 --> 00:54:02,040
Non?

1125
00:54:02,040 --> 00:54:03,540
Porque aínda temos a idea de Marcus.

1126
00:54:03,540 --> 00:54:06,870
Podemos saír deste ciclo, xa que
estamos ao final da lista.

1127
00:54:06,870 --> 00:54:09,308
Polo tanto, queremos aínda este
código aquí abaixo?

1128
00:54:09,308 --> 00:54:10,520
>> Audiencia: si.

1129
00:54:10,520 --> 00:54:11,000
>> Jason Hirschhorn: Yeah.

1130
00:54:11,000 --> 00:54:14,190
E o que necesitamos cambiar isto?

1131
00:54:14,190 --> 00:54:15,440
Certo.

1132
00:54:15,440 --> 00:54:19,580

1133
00:54:19,580 --> 00:54:21,640
Será que un bo son
a todos ata agora?

1134
00:54:21,640 --> 00:54:22,420
Alguén ten algunha -

1135
00:54:22,420 --> 00:54:23,480
Rar, ten algo que engadir?

1136
00:54:23,480 --> 00:54:23,920
>> Audiencia: Non

1137
00:54:23,920 --> 00:54:25,276
>> Jason Hirschhorn: Aceptar.

1138
00:54:25,276 --> 00:54:27,010
Entón, fixemos algúns cambios.

1139
00:54:27,010 --> 00:54:29,540
Nós fixemos esta comprobación antes de nós
entrou unha lista baleira.

1140
00:54:29,540 --> 00:54:31,790
Entón, temos tido o coidado dunha lista baleira.

1141
00:54:31,790 --> 00:54:35,500
E aquí nós tomamos o coidado de introducir
algo ao final da lista.

1142
00:54:35,500 --> 00:54:38,930
Entón, parece que esa toma loop while
conta das cousas no medio,

1143
00:54:38,930 --> 00:54:41,920
nalgún lugar da lista, se hai
son cousas da lista.

1144
00:54:41,920 --> 00:54:42,280
>> Aceptar.

1145
00:54:42,280 --> 00:54:44,310
Imos realizar este programa de novo.

1146
00:54:44,310 --> 00:54:50,170

1147
00:54:50,170 --> 00:54:50,755
Non exitosa.

1148
00:54:50,755 --> 00:54:52,190
>> Audiencia: Non facelo.

1149
00:54:52,190 --> 00:54:53,940
>> Jason Hirschhorn: Oh,
Eu non fixen iso.

1150
00:54:53,940 --> 00:54:56,250
Bo punto, Michael.

1151
00:54:56,250 --> 00:54:57,500
Imos engadir un make conectados.

1152
00:54:57,500 --> 00:55:01,590

1153
00:55:01,590 --> 00:55:04,830
Liña 87 hai un erro.

1154
00:55:04,830 --> 00:55:05,420
Liña 87.

1155
00:55:05,420 --> 00:55:06,600
Alden, esta foi a liña que me deu.

1156
00:55:06,600 --> 00:55:08,962
O que hai de malo?

1157
00:55:08,962 --> 00:55:10,710
>> Audiencia: Ten que ser como nulo.

1158
00:55:10,710 --> 00:55:11,000
>> Jason Hirschhorn: Excelente.

1159
00:55:11,000 --> 00:55:11,630
Exactamente.

1160
00:55:11,630 --> 00:55:13,290
Debe ser nulo.

1161
00:55:13,290 --> 00:55:15,210
Imos facer de novo.

1162
00:55:15,210 --> 00:55:17,220
Compilar.

1163
00:55:17,220 --> 00:55:17,890
Aceptar.

1164
00:55:17,890 --> 00:55:19,400
Imos introducir tres.

1165
00:55:19,400 --> 00:55:20,570
A inserción foi exitosa.

1166
00:55:20,570 --> 00:55:21,660
Imos imprimir lo.

1167
00:55:21,660 --> 00:55:23,590
Oh, se puidésemos comprobar.

1168
00:55:23,590 --> 00:55:25,500
Pero nós non fixemos a
imprimir función aínda.

1169
00:55:25,500 --> 00:55:27,840
Imos entrar outra cousa.

1170
00:55:27,840 --> 00:55:29,090
O que temos que entrar?

1171
00:55:29,090 --> 00:55:31,120

1172
00:55:31,120 --> 00:55:31,940
>> Audiencia: Sete.

1173
00:55:31,940 --> 00:55:33,340
>> Jason Hirschhorn: Seven?

1174
00:55:33,340 --> 00:55:34,590
>> Audiencia: si.

1175
00:55:34,590 --> 00:55:38,680

1176
00:55:38,680 --> 00:55:39,780
>> Jason Hirschhorn: Temos un fallo seg.

1177
00:55:39,780 --> 00:55:43,760
Entón, temos un, pero claramente
non pode estar dous.

1178
00:55:43,760 --> 00:55:45,690
É 05:07.

1179
00:55:45,690 --> 00:55:48,370
Así poderiamos depurar este
por tres minutos.

1180
00:55:48,370 --> 00:55:51,240
Pero eu vou deixar-nos aquí
e seguir adiante para hash táboas.

1181
00:55:51,240 --> 00:55:54,290
Pero, de novo, as respostas a este código
Vou enviar correo-e para ti en breve.

1182
00:55:54,290 --> 00:55:55,440
Estamos moi próximos a el.

1183
00:55:55,440 --> 00:55:58,300
Eu altamente incentivos-lo a descubrir
o que está pasando aquí e resolve-lo.

1184
00:55:58,300 --> 00:56:02,400
Entón, eu vou enviar correo-e que este código como
ben máis alá da solución -

1185
00:56:02,400 --> 00:56:03,670
probablemente, a solución máis tarde.

1186
00:56:03,670 --> 00:56:05,110
Primeiro este código.

1187
00:56:05,110 --> 00:56:08,290
>> A outra cousa que quero facer antes de nós
acabado é que non liberaron nada.

1188
00:56:08,290 --> 00:56:10,370
Entón, quero amosar o que
Valgrind parece.

1189
00:56:10,370 --> 00:56:14,310
Se corrermos límites Valgrind
no noso programa,. / activada.

1190
00:56:14,310 --> 00:56:22,540
De novo, de acordo con esta corredías, nós
debe realizar Valgrind con algún tipo de

1191
00:56:22,540 --> 00:56:26,410
opción, neste caso
- Check-baleirado = a foto.

1192
00:56:26,410 --> 00:56:27,660
Entón imos escribir Valgrind
- Check-baleirado = a foto.

1193
00:56:27,660 --> 00:56:31,910

1194
00:56:31,910 --> 00:56:35,080
Polo tanto, este será executado Valgrind
no noso programa.

1195
00:56:35,080 --> 00:56:37,000
E agora o programa realmente funciona.

1196
00:56:37,000 --> 00:56:40,190
Entón, imos executa-lo só como
antes, poñer algo dentro

1197
00:56:40,190 --> 00:56:40,830
Vou poñer en tres.

1198
00:56:40,830 --> 00:56:41,790
Isto funciona.

1199
00:56:41,790 --> 00:56:43,202
Eu non estou indo a tentar poñer en algo
outra cousa, porque nós imos

1200
00:56:43,202 --> 00:56:44,710
obter un falso seg nese caso.

1201
00:56:44,710 --> 00:56:46,700
Entón, eu só vou saír.

1202
00:56:46,700 --> 00:56:50,160
>> E agora ves aquí
baleirar e resumo heap.

1203
00:56:50,160 --> 00:56:52,310
Estas son as cousas boas que
queira dar un ollo.

1204
00:56:52,310 --> 00:56:56,780
Así, o resumo pila - di, en uso
na saída - oito bytes nun bloque.

1205
00:56:56,780 --> 00:56:58,370
Este bloque é o
nó que malloced.

1206
00:56:58,370 --> 00:57:02,230
Michael, dixo antes dun nodo é de oito
picaduras xa que posúe o número enteiro

1207
00:57:02,230 --> 00:57:02,680
eo punteiro.

1208
00:57:02,680 --> 00:57:04,550
Entón, este é o noso nodo.

1209
00:57:04,550 --> 00:57:08,170
E entón el di que usamos malloc
sete veces e que liberou

1210
00:57:08,170 --> 00:57:08,940
algo seis veces.

1211
00:57:08,940 --> 00:57:13,680
Pero nós nunca chama libre, entón eu non teño
idea do que iso está falando.

1212
00:57:13,680 --> 00:57:18,490
>> Pero basta dicir que, cando o seu
carreiras do programa, malloc está a ser chamado

1213
00:57:18,490 --> 00:57:20,330
nalgúns outros lugares que nós
Non se preocupe.

1214
00:57:20,330 --> 00:57:22,460
Entón malloc probablemente foi chamado
nalgúns lugares.

1215
00:57:22,460 --> 00:57:24,480
Non se preocupe onde.

1216
00:57:24,480 --> 00:57:26,240
Pero iso é realmente nós.

1217
00:57:26,240 --> 00:57:27,380
Esta primeira liña é a xente.

1218
00:57:27,380 --> 00:57:28,320
Deixamos este bloque.

1219
00:57:28,320 --> 00:57:30,330
E podes ver que aquí
no resumo baleirado.

1220
00:57:30,330 --> 00:57:31,950
Aínda alcançável -

1221
00:57:31,950 --> 00:57:32,930
oito bytes nun bloque.

1222
00:57:32,930 --> 00:57:34,100
Isto significa que a memoria -

1223
00:57:34,100 --> 00:57:35,730
que baleiraron esa memoria.

1224
00:57:35,730 --> 00:57:37,570
Definitivamente perdida -

1225
00:57:37,570 --> 00:57:38,770
algo está perdido para sempre.

1226
00:57:38,770 --> 00:57:40,590
Xeralmente, non vai
ver nada alí.

1227
00:57:40,590 --> 00:57:44,780
Aínda accesible adoita onde
vai ver as cousas, onde queira

1228
00:57:44,780 --> 00:57:48,900
ollar para ver o que o código que debería
liberar, pero se esqueceu de liberar.

1229
00:57:48,900 --> 00:57:53,170
>> E entón, se este non foi o caso,
se fixemos todo libre,

1230
00:57:53,170 --> 00:57:54,360
podemos comprobar iso.

1231
00:57:54,360 --> 00:57:57,330
Imos realizar o programa
non poñer en calquera cousa.

1232
00:57:57,330 --> 00:57:59,800
Vai ver aquí abaixo en uso na saída -

1233
00:57:59,800 --> 00:58:01,310
cero bytes cero de bloques.

1234
00:58:01,310 --> 00:58:06,310
Isto significa que non tiña máis nada
cando este programa saíu.

1235
00:58:06,310 --> 00:58:12,090
Entón, antes de virar pset6, executa Valgrind
e asegúrese de que non ten

1236
00:58:12,090 --> 00:58:15,310
calquera perdas de memoria no seu programa.

1237
00:58:15,310 --> 00:58:17,910
Se ten algunha dúbida con Valgrind,
sexa a vontade para chegar.

1238
00:58:17,910 --> 00:58:18,700
Pero isto é como usalo.

1239
00:58:18,700 --> 00:58:20,890
Moi simple - vexa se
ter en uso na saída -

1240
00:58:20,890 --> 00:58:22,270
calquera bytes en todos os bloques.

1241
00:58:22,270 --> 00:58:27,890

1242
00:58:27,890 --> 00:58:29,580
>> Entón nós estabamos traballando no nó de inserción.

1243
00:58:29,580 --> 00:58:33,840
Eu tiña dúas outras funcións aquí -
imprimir nós e nós libres.

1244
00:58:33,840 --> 00:58:37,780
De novo, estas son funcións que son
vai ser bo para ti practicar

1245
00:58:37,780 --> 00:58:40,990
porque eles van axudar non só con
estes exercicios de mostra, pero tamén

1246
00:58:40,990 --> 00:58:42,180
sobre o conxunto de problemas.

1247
00:58:42,180 --> 00:58:44,230
Eles mapeiam en ben de preto para as cousas
vai ter que facer no

1248
00:58:44,230 --> 00:58:45,010
conxunto de problemas.

1249
00:58:45,010 --> 00:58:47,640
Pero quero que seguro
tocamos en todo.

1250
00:58:47,640 --> 00:58:50,400
E táboas de hash tamén son cruciais para
o que estamos facendo na sección deste

1251
00:58:50,400 --> 00:58:51,980
semana - ou no conxunto problema.

1252
00:58:51,980 --> 00:58:55,200
>> Entón, nós estamos indo a rematar a sección
falando de táboas de hash.

1253
00:58:55,200 --> 00:58:58,140
Se notar que fixen un
mesiña hash.

1254
00:58:58,140 --> 00:59:00,020
Isto non é o que estamos a falar
sobre, con todo.

1255
00:59:00,020 --> 00:59:03,540
Estamos falando dun diferente
tipo de táboas de hash.

1256
00:59:03,540 --> 00:59:07,300
E no seu núcleo, unha táboa hash
non é máis que unha

1257
00:59:07,300 --> 00:59:08,860
disposición unha función hash.

1258
00:59:08,860 --> 00:59:11,150
Imos falar un pouco só para
asegurarse de todo o mundo entende o que é un

1259
00:59:11,150 --> 00:59:12,110
función hash é.

1260
00:59:12,110 --> 00:59:15,420
E eu estou te dicindo agora que é
nada máis que dúas cousas -

1261
00:59:15,420 --> 00:59:18,590
unha matriz e unha función de hash.

1262
00:59:18,590 --> 00:59:20,716
E aquí están os pasos a través de
que esta opera.

1263
00:59:20,716 --> 00:59:31,560

1264
00:59:31,560 --> 00:59:32,810
>> Non é a nosa matriz.

1265
00:59:32,810 --> 00:59:38,460

1266
00:59:38,460 --> 00:59:39,460
Non é a nosa función.

1267
00:59:39,460 --> 00:59:43,180
En particular, as funcións de hash ten
facer un par de cousas con iso.

1268
00:59:43,180 --> 00:59:45,040
Vou falar especificamente
sobre este conxunto de problemas.

1269
00:59:45,040 --> 00:59:46,450
El probablemente vai
tomar en un cadea.

1270
00:59:46,450 --> 00:59:50,570

1271
00:59:50,570 --> 00:59:51,770
E o que é o que vai volver?

1272
00:59:51,770 --> 00:59:52,640
Que tipo de datos?

1273
00:59:52,640 --> 00:59:54,260
Alden?

1274
00:59:54,260 --> 00:59:55,760
A súa función hash retornar?

1275
00:59:55,760 --> 00:59:58,760
Un enteiro.

1276
00:59:58,760 --> 01:00:01,700
Entón é iso que o hash
táboa consiste en -

1277
01:00:01,700 --> 01:00:05,430
unha mesa en forma de abano
e unha función de hash.

1278
01:00:05,430 --> 01:00:06,010
Como funciona?

1279
01:00:06,010 --> 01:00:07,300
Funciona en tres etapas.

1280
01:00:07,300 --> 01:00:08,740
Nós darlle unha chave.

1281
01:00:08,740 --> 01:00:11,470
Neste caso, nós imos dar-lle unha corda.

1282
01:00:11,470 --> 01:00:18,140
Chamamos a función hash por unha etapa
na clave e temos un valor.

1283
01:00:18,140 --> 01:00:20,310
>> Especificamente, imos dicir
obtemos un número enteiro.

1284
01:00:20,310 --> 01:00:25,630
Ese número enteiro, non son moi específicos
límites ao número enteiro que pode ser.

1285
01:00:25,630 --> 01:00:28,880
Neste exemplo, a matriz
é de tamaño tres.

1286
01:00:28,880 --> 01:00:32,330
Entón, o que os números poden ser enteiro.

1287
01:00:32,330 --> 01:00:35,970
Cal é o intervalo de valores válidos para
que enteiro, o tipo de retorno dese

1288
01:00:35,970 --> 01:00:37,220
de hash función?

1289
01:00:37,220 --> 01:00:40,440

1290
01:00:40,440 --> 01:00:42,110
Cero, un e dous.

1291
01:00:42,110 --> 01:00:46,060
O punto de partida da función hash é
descubrir o lugar na matriz

1292
01:00:46,060 --> 01:00:47,790
onde a nosa clave está indo.

1293
01:00:47,790 --> 01:00:51,290
Hai só tres posibles
lugares aquí -

1294
01:00:51,290 --> 01:00:52,130
cero, un ou dous.

1295
01:00:52,130 --> 01:00:55,360
Polo tanto, esta función mellor retorno
cero, un ou dous.

1296
01:00:55,360 --> 01:00:58,740
Algúns indice válido neste array.

1297
01:00:58,740 --> 01:01:02,770
>> E, a continuación, dependendo de onde el retorna,
podes ver que hai disposición aberta

1298
01:01:02,770 --> 01:01:03,730
entre parénteses o valor.

1299
01:01:03,730 --> 01:01:05,800
Isto é onde poñemos a clave.

1300
01:01:05,800 --> 01:01:11,280
Por iso, xogar a cabaza,
sairmos cero.

1301
01:01:11,280 --> 01:01:15,540
No conxunto do soporte 0, poñemos cabaza.

1302
01:01:15,540 --> 01:01:21,070
Xogamos en gatos, saímos un.

1303
01:01:21,070 --> 01:01:24,110
Poñemos nun gato.

1304
01:01:24,110 --> 01:01:25,480
Poñemos en araña.

1305
01:01:25,480 --> 01:01:26,710
Saímos dúas.

1306
01:01:26,710 --> 01:01:30,200
Poñemos araña en soporte disposición dous.

1307
01:01:30,200 --> 01:01:32,300
Sería tan bo se
funcionou así.

1308
01:01:32,300 --> 01:01:35,570
Pero, desgraciadamente, como veremos,
é un pouco máis complicado.

1309
01:01:35,570 --> 01:01:37,570
>> Antes de chegar alí, as preguntas
sobre o básico

1310
01:01:37,570 --> 01:01:38,820
set-up dunha táboa hash?

1311
01:01:38,820 --> 01:01:49,050

1312
01:01:49,050 --> 01:01:51,940
Esta é unha imaxe de exactamente
o que chamou a bordo.

1313
01:01:51,940 --> 01:01:55,420
Pero desde que o deseñou o cadro, eu
Non vou entrar en lo aínda máis.

1314
01:01:55,420 --> 01:02:00,430
Esencialmente claves, a caixa negra máxica -
ou, neste caso, a caixa azul - dun

1315
01:02:00,430 --> 01:02:02,410
función hash poñelos baldes.

1316
01:02:02,410 --> 01:02:04,690
E, neste exemplo, estamos
non poñer o nome.

1317
01:02:04,690 --> 01:02:07,880
Estamos poñendo o teléfono asociado
número do nome no balde.

1318
01:02:07,880 --> 01:02:10,430
Pero podería moi ben só
poñer o nome no balde.

1319
01:02:10,430 --> 01:02:12,950
>> Este é só un retrato do que
trazamos no taboleiro.

1320
01:02:12,950 --> 01:02:14,460
Temos potenciais trampas, con todo.

1321
01:02:14,460 --> 01:02:17,470
E hai dous en particular
diapositivas que quero pasar por riba.

1322
01:02:17,470 --> 01:02:20,230
A primeira é sobre
unha función hash.

1323
01:02:20,230 --> 01:02:22,620
Entón eu fixen a pregunta, o que
fai unha boa función hash?

1324
01:02:22,620 --> 01:02:24,220
Dou dúas respostas.

1325
01:02:24,220 --> 01:02:26,630
O primeiro é que non é determinista.

1326
01:02:26,630 --> 01:02:29,660
No contexto das funcións hash,
o que significa isto?

1327
01:02:29,660 --> 01:02:37,840

1328
01:02:37,840 --> 01:02:39,282
Si?

1329
01:02:39,282 --> 01:02:42,850
>> Audiencia: Atopará o
índice en tempo constante?

1330
01:02:42,850 --> 01:02:43,810
>> Jason Hirschhorn: Isto
non é o que ela significa.

1331
01:02:43,810 --> 01:02:44,725
Pero iso é un bo palpite.

1332
01:02:44,725 --> 01:02:46,100
Alguén máis ten un palpite
para que isto significa?

1333
01:02:46,100 --> 01:02:47,780
Que unha boa función de hash
é determinista?

1334
01:02:47,780 --> 01:02:48,280
Annie?

1335
01:02:48,280 --> 01:02:51,680
>> Audiencia: É unha clave só se pode mapeado
a un lugar na táboa de hash.

1336
01:02:51,680 --> 01:02:53,070
>> Jason Hirschhorn: Isto é
exactamente correcto.

1337
01:02:53,070 --> 01:02:57,430
Cada vez que poñer na cabaza,
el sempre volve cero.

1338
01:02:57,430 --> 01:03:01,660
Se pór en cabaza ea súa mestura
función devolve cero, pero ten un

1339
01:03:01,660 --> 01:03:06,060
probabilidade de volver algo
outra cousa maior que cero -

1340
01:03:06,060 --> 01:03:09,280
quizais por iso, ás veces, pode voltar un
ou dúas veces -

1341
01:03:09,280 --> 01:03:11,100
que non é unha boa función hash.

1342
01:03:11,100 --> 01:03:11,800
Está absolutamente certo.

1343
01:03:11,800 --> 01:03:15,680
A súa función hash debe devolver o
mesmo número enteiro exacto, neste caso, a

1344
01:03:15,680 --> 01:03:17,780
a mesma secuencia exacta.

1345
01:03:17,780 --> 01:03:22,210
>> Quizais el retorna o mesmo número enteiro exacto
para a mesma secuencia exacta

1346
01:03:22,210 --> 01:03:24,430
independentemente da capitalización.

1347
01:03:24,430 --> 01:03:27,980
Pero, nese caso, aínda é
determinista, pois moitas cousas

1348
01:03:27,980 --> 01:03:29,350
son mapeados ao mesmo valor.

1349
01:03:29,350 --> 01:03:30,170
Iso é bo.

1350
01:03:30,170 --> 01:03:32,615
Mentres hai só unha
saída para unha dada entrada.

1351
01:03:32,615 --> 01:03:35,630

1352
01:03:35,630 --> 01:03:36,350
>> Aceptar.

1353
01:03:36,350 --> 01:03:38,340
A segunda cousa é que
retorna índices válidos.

1354
01:03:38,340 --> 01:03:40,220
Trouxo-se que antes.

1355
01:03:40,220 --> 01:03:41,860
Esta función hash -

1356
01:03:41,860 --> 01:03:43,710
oh boy -

1357
01:03:43,710 --> 01:03:46,840
unha función de hash debe
voltar índices válidos.

1358
01:03:46,840 --> 01:03:47,740
Entón diga -

1359
01:03:47,740 --> 01:03:48,990
imos voltar a este exemplo.

1360
01:03:48,990 --> 01:03:52,580

1361
01:03:52,580 --> 01:03:57,540
A miña función hash conta ata
as letras da palabra.

1362
01:03:57,540 --> 01:03:58,380
Esa é a función hash.

1363
01:03:58,380 --> 01:03:59,740
E volve este número enteiro.

1364
01:03:59,740 --> 01:04:04,280
Entón, se eu teño a palabra A, é
vai volver un.

1365
01:04:04,280 --> 01:04:06,900
E vai poñer un aquí.

1366
01:04:06,900 --> 01:04:09,430
E se eu poñer a palabra morcego?

1367
01:04:09,430 --> 01:04:11,310
Volverá tres.

1368
01:04:11,310 --> 01:04:12,560
Onde o morcego ir?

1369
01:04:12,560 --> 01:04:18,730

1370
01:04:18,730 --> 01:04:19,750
>> Non serve.

1371
01:04:19,750 --> 01:04:21,000
Pero el que ir a algún lugar.

1372
01:04:21,000 --> 01:04:23,340
Esta é a miña táboa hash Despois de todo, e
todo ten que ir a algún lugar.

1373
01:04:23,340 --> 01:04:24,590
Entón, a onde debe ir morcego?

1374
01:04:24,590 --> 01:04:28,020

1375
01:04:28,020 --> 01:04:28,710
Calquera pensamentos?

1376
01:04:28,710 --> 01:04:29,450
Adiviña?

1377
01:04:29,450 --> 01:04:30,280
Bos historiadores?

1378
01:04:30,280 --> 01:04:31,220
>> Audiencia: Cero.

1379
01:04:31,220 --> 01:04:32,120
>> Jason Hirschhorn: Porque a cero?

1380
01:04:32,120 --> 01:04:35,990
>> Audiencia: Por tres
módulo tres é igual a cero?

1381
01:04:35,990 --> 01:04:38,620
>> Jason Hirschhorn: Three
módulo de tres é igual a cero.

1382
01:04:38,620 --> 01:04:40,810
Isto é un gran palpite,
e iso é correcto.

1383
01:04:40,810 --> 01:04:43,870
Polo tanto, neste caso debería
probablemente ir a cero.

1384
01:04:43,870 --> 01:04:51,080
Así, unha boa forma de garantir que este hash
función só retorna índices válidos é

1385
01:04:51,080 --> 01:04:54,580
Módulo para isto por o tamaño da táboa.

1386
01:04:54,580 --> 01:04:57,360
Se queres que este modulo retorno
tres, está sempre indo para obter

1387
01:04:57,360 --> 01:05:00,930
algo entre cero, un e dous.

1388
01:05:00,930 --> 01:05:05,160
E se isto sempre regresa sete, e
sempre modulo por tres, está

1389
01:05:05,160 --> 01:05:06,030
sempre se ve o mesmo.

1390
01:05:06,030 --> 01:05:09,270
>> Entón, aínda é determinística
se módulo.

1391
01:05:09,270 --> 01:05:11,420
Pero iso vai garantir que
nunca conseguir algo -

1392
01:05:11,420 --> 01:05:12,940
unha industria válido.

1393
01:05:12,940 --> 01:05:16,840
Xeralmente, este módulo debe acontecer
dentro da súa función de hash.

1394
01:05:16,840 --> 01:05:18,240
Así que non se preocupe con iso.

1395
01:05:18,240 --> 01:05:20,555
Só pode garantir que
este é un indice válido.

1396
01:05:20,555 --> 01:05:23,700

1397
01:05:23,700 --> 01:05:26,700
Calquera dúbida sobre este
trampa potencial?

1398
01:05:26,700 --> 01:05:36,590

1399
01:05:36,590 --> 01:05:39,060
>> Aceptar.

1400
01:05:39,060 --> 01:05:40,290
E alí imos nós.

1401
01:05:40,290 --> 01:05:42,890
Seguinte trampa potencial, e
este é un dos grandes.

1402
01:05:42,890 --> 01:05:46,880
E se dúas chaves mapa
para o mesmo valor de?

1403
01:05:46,880 --> 01:05:49,350
Polo tanto, hai dúas formas de tratar con isto.

1404
01:05:49,350 --> 01:05:53,140

1405
01:05:53,140 --> 01:05:56,020
O primeiro chámase lineal
enquisa, o que eu son

1406
01:05:56,020 --> 01:05:57,300
non vai pasar por riba.

1407
01:05:57,300 --> 01:06:01,120
Pero ten que estar familiarizado coa forma
que funciona e que é.

1408
01:06:01,120 --> 01:06:05,610
>> A segunda eu vou pasar por riba
porque esta é a única que moitos

1409
01:06:05,610 --> 01:06:08,290
persoas probablemente vai acabar decidindo
para usar no seu conxunto de problemas.

1410
01:06:08,290 --> 01:06:09,820
Por suposto, non precisa.

1411
01:06:09,820 --> 01:06:15,280
Pero, para o conxunto de problemas, moitas persoas
tenden a optar por crear unha táboa hash

1412
01:06:15,280 --> 01:06:17,950
con fío separado para aplicar
seu dicionario.

1413
01:06:17,950 --> 01:06:21,390
Entón, nós estamos indo ir sobre o que significa isto
para crear unha táboa hash coa

1414
01:06:21,390 --> 01:06:23,890
encadeamento separado.

1415
01:06:23,890 --> 01:06:26,260
>> Entón eu coloque na cabaza.

1416
01:06:26,260 --> 01:06:29,560
El retorna cero.

1417
01:06:29,560 --> 01:06:31,410
E eu coloque cabaza aquí.

1418
01:06:31,410 --> 01:06:35,880

1419
01:06:35,880 --> 01:06:37,930
Entón eu coloque en -

1420
01:06:37,930 --> 01:06:39,922
o que é outra cousa Halloween-temático?

1421
01:06:39,922 --> 01:06:42,200
>> Audiencia: Candy.

1422
01:06:42,200 --> 01:06:42,770
>> Jason Hirschhorn: doces!

1423
01:06:42,770 --> 01:06:43,910
Isto é un gran home.

1424
01:06:43,910 --> 01:06:47,760
Engada en doces, e doces
tamén me dá cero.

1425
01:06:47,760 --> 01:06:49,350
O que fago?

1426
01:06:49,350 --> 01:06:51,940
Algunha idea?

1427
01:06:51,940 --> 01:06:53,940
Porque toda a sorte de coñecer
o fío separado é.

1428
01:06:53,940 --> 01:06:55,190
Entón, algunha idea do que facer?

1429
01:06:55,190 --> 01:06:58,170

1430
01:06:58,170 --> 01:06:59,110
É.

1431
01:06:59,110 --> 01:07:03,810
>> Audiencia: Poñer a corda
de feito, na táboa de hash.

1432
01:07:03,810 --> 01:07:08,910
>> Jason Hirschhorn: Entón nós imos
deseñar a boa idea por aquí.

1433
01:07:08,910 --> 01:07:09,340
Aceptar.

1434
01:07:09,340 --> 01:07:12,290
>> Audiencia: Teña o hashtable
[Inaudível]

1435
01:07:12,290 --> 01:07:16,640
o punteiro que apunta a
o inicio dunha lista.

1436
01:07:16,640 --> 01:07:20,930
E entón, cabaza ser o primeiro valor
nesa lista conexionada e doces ser

1437
01:07:20,930 --> 01:07:22,800
o segundo valor nesa lista encadeada.

1438
01:07:22,800 --> 01:07:23,420
>> Jason Hirschhorn: Aceptar.

1439
01:07:23,420 --> 01:07:24,670
Marcus, que foi excelente.

1440
01:07:24,670 --> 01:07:26,160
Vou romper ese abaixo.

1441
01:07:26,160 --> 01:07:28,890
Marcus di non
substituír cabaza.

1442
01:07:28,890 --> 01:07:30,660
Isto sería malo.

1443
01:07:30,660 --> 01:07:33,640
Non coloque doces noutro lugar.

1444
01:07:33,640 --> 01:07:35,390
Imos poñer-los a cero.

1445
01:07:35,390 --> 01:07:37,770
Pero estamos indo para xestionar
poñelos cero por

1446
01:07:37,770 --> 01:07:39,395
creación dunha lista de cero.

1447
01:07:39,395 --> 01:07:42,430
E imos crear unha lista de
todo o que mapeada a cero.

1448
01:07:42,430 --> 01:07:47,960
E a mellor forma que aprenden a crear
unha lista que pode aumentar e diminuír

1449
01:07:47,960 --> 01:07:49,840
dinámica non está dentro
outra matriz.

1450
01:07:49,840 --> 01:07:51,510
Polo tanto, non un array multi-dimensional.

1451
01:07:51,510 --> 01:07:54,080
Pero só crear unha lista ligada.

1452
01:07:54,080 --> 01:07:55,330
>> Entón, o que el propuxo -

1453
01:07:55,330 --> 01:07:57,950

1454
01:07:57,950 --> 01:07:59,200
Eu estou indo a obter un novo -

1455
01:07:59,200 --> 01:08:15,380

1456
01:08:15,380 --> 01:08:19,689
é crear unha matriz con punteiros,
unha matriz de punteiros.

1457
01:08:19,689 --> 01:08:20,580
Aceptar.

1458
01:08:20,580 --> 01:08:24,180
Calquera idea ou suxestión que o tipo
desta punteiros debe ser?

1459
01:08:24,180 --> 01:08:26,290
Marcus?

1460
01:08:26,290 --> 01:08:27,250
>> Audiencia: Punteiros para -

1461
01:08:27,250 --> 01:08:28,609
>> Jason Hirschhorn: Por ti
dixo unha lista ligada, por iso -

1462
01:08:28,609 --> 01:08:29,520
>> Audiencia: punteiros do nodo?

1463
01:08:29,520 --> 01:08:30,670
>> Jason Hirschhorn: punteiros no.

1464
01:08:30,670 --> 01:08:32,830
Se as cousas na nosa conectado
lista son os nós, entón eles

1465
01:08:32,830 --> 01:08:34,370
debe ser punteiros do nodo.

1466
01:08:34,370 --> 01:08:35,939
E o que eles igual inicialmente?

1467
01:08:35,939 --> 01:08:36,990
>> Audiencia: Null.

1468
01:08:36,990 --> 01:08:38,240
>> Jason Hirschhorn: Null.

1469
01:08:38,240 --> 01:08:44,540

1470
01:08:44,540 --> 01:08:46,080
Polo tanto, non é a nosa cousa baleira.

1471
01:08:46,080 --> 01:08:47,170
Cabaza retorna cero.

1472
01:08:47,170 --> 01:08:48,569
O que imos facer?

1473
01:08:48,569 --> 01:08:49,609
Camiño comigo a través dela?

1474
01:08:49,609 --> 01:08:50,810
En realidade, Marcus xa me deu.

1475
01:08:50,810 --> 01:08:52,439
Alguén me atravesalo-la.

1476
01:08:52,439 --> 01:08:54,760
Que facemos cando -

1477
01:08:54,760 --> 01:08:56,609
este é moi parecido
o que nós estabamos facendo.

1478
01:08:56,609 --> 01:08:57,396
Avi.

1479
01:08:57,396 --> 01:08:59,090
>> Audiencia: Vou dar un palpite.

1480
01:08:59,090 --> 01:09:01,250
Entón, cando comeza doces.

1481
01:09:01,250 --> 01:09:01,640
>> Jason Hirschhorn: Yeah.

1482
01:09:01,640 --> 01:09:03,120
Así, temos de cabaza.

1483
01:09:03,120 --> 01:09:03,870
Imos buscar o noso primeiro.

1484
01:09:03,870 --> 01:09:04,324
Temos cabaza.

1485
01:09:04,324 --> 01:09:04,779
>> Audiencia: Aceptar.

1486
01:09:04,779 --> 01:09:05,880
Cabaza retorna cero.

1487
01:09:05,880 --> 01:09:08,770
Entón poñelas niso.

1488
01:09:08,770 --> 01:09:10,810
Ou, en realidade, poñelas
na lista encadeada.

1489
01:09:10,810 --> 01:09:13,550
>> Jason Hirschhorn: Como é que nós
poñelas na lista ligada?

1490
01:09:13,550 --> 01:09:15,479
>> Audiencia: Oh, a sintaxe real?

1491
01:09:15,479 --> 01:09:16,240
>> Jason Hirschhorn: Só ten que andar -

1492
01:09:16,240 --> 01:09:16,740
dicir máis.

1493
01:09:16,740 --> 01:09:19,310
O que imos facer?

1494
01:09:19,310 --> 01:09:22,100
>> Audiencia: Acaba de inserir
el como o primeiro nodo.

1495
01:09:22,100 --> 01:09:22,675
>> Jason Hirschhorn: Aceptar.

1496
01:09:22,675 --> 01:09:29,069
Entón, nós temos o noso nodo, cabaza.

1497
01:09:29,069 --> 01:09:31,560
E agora como fago para inserir-lo?

1498
01:09:31,560 --> 01:09:34,590

1499
01:09:34,590 --> 01:09:37,090
>> Audiencia: Vostede atribúe
lo para o punteiro.

1500
01:09:37,090 --> 01:09:37,970
>> Jason Hirschhorn: Cal punteiro?

1501
01:09:37,970 --> 01:09:39,620
>> Audiencia: O punteiro do cero.

1502
01:09:39,620 --> 01:09:41,420
>> Jason Hirschhorn: Entón, onde
fai ese punto?

1503
01:09:41,420 --> 01:09:42,810
>> Audiencia: Para nulo agora.

1504
01:09:42,810 --> 01:09:43,529
>> Jason Hirschhorn: Ben,
está a apuntar cara null.

1505
01:09:43,529 --> 01:09:44,499
Pero eu estou poñendo en cabaza.

1506
01:09:44,499 --> 01:09:46,053
Entón, onde debe apuntar?

1507
01:09:46,053 --> 01:09:46,880
>> Audiencia: Para cabaza.

1508
01:09:46,880 --> 01:09:47,399
>> Jason Hirschhorn: Para cabaza.

1509
01:09:47,399 --> 01:09:48,760
Exactamente.

1510
01:09:48,760 --> 01:09:50,010
Entón, iso apunta a cabaza.

1511
01:09:50,010 --> 01:09:52,500

1512
01:09:52,500 --> 01:09:54,250
E onde é que este punteiro
ao momento de cabaza?

1513
01:09:54,250 --> 01:09:57,986

1514
01:09:57,986 --> 01:09:58,340
Para

1515
01:09:58,340 --> 01:09:58,590
>> Audiencia: Null.

1516
01:09:58,590 --> 01:09:59,210
>> Jason Hirschhorn: Para nulo.

1517
01:09:59,210 --> 01:10:00,460
Exactamente.

1518
01:10:00,460 --> 01:10:03,570

1519
01:10:03,570 --> 01:10:05,140
Entón, nós só inserido algo
na lista encadeada.

1520
01:10:05,140 --> 01:10:07,210
Nós só escribín este código para facelo.

1521
01:10:07,210 --> 01:10:09,520
Case que case conseguiu
totalmente rachado.

1522
01:10:09,520 --> 01:10:10,790
Agora imos introducir doces.

1523
01:10:10,790 --> 01:10:13,480
Noso doces tamén vai a cero.

1524
01:10:13,480 --> 01:10:16,100
Entón, o que imos facer con doces?

1525
01:10:16,100 --> 01:10:18,790
>> Audiencia: Depende ou
Non estamos intentando resolver iso.

1526
01:10:18,790 --> 01:10:19,640
>> Jason Hirschhorn: Isto é
exactamente correcto.

1527
01:10:19,640 --> 01:10:21,070
Depende de se ou non
Estamos intentando resolver iso.

1528
01:10:21,070 --> 01:10:22,660
Imos supor que non estamos
indo a clasificalos lo.

1529
01:10:22,660 --> 01:10:24,880
>> Audiencia: Ben, entón, como discutir
antes, é máis simple só para poñelas

1530
01:10:24,880 --> 01:10:28,590
ao comezo para que o punteiro
de cero puntos a doces.

1531
01:10:28,590 --> 01:10:29,020
>> Jason Hirschhorn: Aceptar.

1532
01:10:29,020 --> 01:10:29,380
Espere un pouco.

1533
01:10:29,380 --> 01:10:30,630
Déixeme crear doces aquí.

1534
01:10:30,630 --> 01:10:34,030

1535
01:10:34,030 --> 01:10:35,150
Polo tanto, este punteiro -

1536
01:10:35,150 --> 01:10:37,590
>> Audiencia: Si, debe agora
estar apuntando para doces.

1537
01:10:37,590 --> 01:10:40,580
Entón, o punteiro de
punto doce para cabaza.

1538
01:10:40,580 --> 01:10:43,140

1539
01:10:43,140 --> 01:10:44,560
>> Jason Hirschhorn: Así?

1540
01:10:44,560 --> 01:10:47,380
E dicir que ten outro
cousa para mapear a cero?

1541
01:10:47,380 --> 01:10:48,660
>> Audiencia: Ben, só
facer o mesmo?

1542
01:10:48,660 --> 01:10:50,290
>> Jason Hirschhorn: Fai o mesmo.

1543
01:10:50,290 --> 01:10:53,700
Polo tanto, neste caso, se non o facemos
quere mantelo ordenados

1544
01:10:53,700 --> 01:10:55,270
soa moi sinxelo.

1545
01:10:55,270 --> 01:10:59,920
Tomamos o punteiro no indice
dada pola nosa función hash.

1546
01:10:59,920 --> 01:11:03,830
Temos que apuntan ao noso novo nodo.

1547
01:11:03,830 --> 01:11:07,830
E entón, o que quere que estaba apuntando
previamente -

1548
01:11:07,830 --> 01:11:10,620
neste caso, nulo, o
segundo caso cabaza -

1549
01:11:10,620 --> 01:11:15,310
que, sexa o que está a apuntar cara
anteriormente, engadir ao seguinte de

1550
01:11:15,310 --> 01:11:17,810
o noso novo nodo.

1551
01:11:17,810 --> 01:11:19,650
Estamos introducindo algo
no inicio.

1552
01:11:19,650 --> 01:11:22,900
En realidade, este é moito máis simple do que
tentando manter a lista ordenada.

1553
01:11:22,900 --> 01:11:25,340
Pero, de novo, a investigación será
máis complicado aquí.

1554
01:11:25,340 --> 01:11:28,300
Sempre teremos que ir ata o final.

1555
01:11:28,300 --> 01:11:29,650
>> Aceptar.

1556
01:11:29,650 --> 01:11:32,750
Calquera dúbida sobre o encadeamento separado?

1557
01:11:32,750 --> 01:11:34,690
Como funciona isto?

1558
01:11:34,690 --> 01:11:35,820
Por favor, pregunta-los agora.

1559
01:11:35,820 --> 01:11:39,260
Eu realmente quero estar seguro de que todo
entender iso antes de cabeza para fóra.

1560
01:11:39,260 --> 01:11:48,410

1561
01:11:48,410 --> 01:11:52,060
>> Audiencia: Por que poña a cabaza
e doces na mesma

1562
01:11:52,060 --> 01:11:54,108
parte da táboa de hash?

1563
01:11:54,108 --> 01:11:55,860
>> Jason Hirschhorn: Boa pregunta.

1564
01:11:55,860 --> 01:11:59,140
Por que poñer-los na mesma
parte da táboa de hash?

1565
01:11:59,140 --> 01:12:03,200
Ben, neste caso, a nosa función de hash
retorna cero para ambos.

1566
01:12:03,200 --> 01:12:05,310
Entón, eles teñen que ir ao indice de cero
porque é onde nós estamos indo

1567
01:12:05,310 --> 01:12:07,420
buscalos se algunha vez
quere procura-los.

1568
01:12:07,420 --> 01:12:11,750
Unha vez máis, cunha visión lineal sondaxe
non ía poñer-los a cero.

1569
01:12:11,750 --> 01:12:13,900
Pero, na visión da cadea separada,
imos poñer-los a cero

1570
01:12:13,900 --> 01:12:16,620
e, a continuación, crear unha lista fóra de cero.

1571
01:12:16,620 --> 01:12:20,140
>> E nós non queremos substituír cabaza
simplemente por iso, porque entón nós

1572
01:12:20,140 --> 01:12:21,860
asumir que cabaza foi
nunca inserido.

1573
01:12:21,860 --> 01:12:25,230
Se nós só manter unha cousa en
local que sería malo.

1574
01:12:25,230 --> 01:12:28,590
Entón, non habería
posibilidade de nós nunca -

1575
01:12:28,590 --> 01:12:31,660
se algunha vez tivo un dobre, entón nós
sería só borrar o seu valor inicial.

1576
01:12:31,660 --> 01:12:34,090
Entón é por iso que facemos esta visión.

1577
01:12:34,090 --> 01:12:36,580
Ou é por iso que nós escoller - pero de novo,
escolleu o achegamento de fío separado,

1578
01:12:36,580 --> 01:12:39,670
que hai moitas outras abordaxes
pódese escoller.

1579
01:12:39,670 --> 01:12:41,185
Isto responde a súa pregunta?

1580
01:12:41,185 --> 01:12:41,660
>> Aceptar.

1581
01:12:41,660 --> 01:12:42,910
Carlos.

1582
01:12:42,910 --> 01:12:46,130

1583
01:12:46,130 --> 01:12:47,720
Sondaxe lineal envolvería -

1584
01:12:47,720 --> 01:12:51,913
se atopamos unha colisión en cero, nós
ficaría no seguinte punto a ver se

1585
01:12:51,913 --> 01:12:54,310
era aberto e poñelas alí.

1586
01:12:54,310 --> 01:12:57,320
E entón nós miramos a próxima deporte e
ver se estaba aberto e poñelas alí.

1587
01:12:57,320 --> 01:12:59,780
Así, atopamos o seguinte dispoñible
lugar aberto e poñelas alí.

1588
01:12:59,780 --> 01:13:02,580

1589
01:13:02,580 --> 01:13:03,890
Algunha pregunta?

1590
01:13:03,890 --> 01:13:05,370
Si, Avi.

1591
01:13:05,370 --> 01:13:07,490
>> Audiencia: No seguimento diso,
o que quere dicir con preto punto?

1592
01:13:07,490 --> 01:13:10,250
Na táboa de hash ou nunha lista vinculada.

1593
01:13:10,250 --> 01:13:12,100
>> Jason Hirschhorn: Para lineal
programación, hai listas ligadas.

1594
01:13:12,100 --> 01:13:13,400
O seguinte punto na táboa de hash.

1595
01:13:13,400 --> 01:13:13,820
>> Audiencia: Aceptar.

1596
01:13:13,820 --> 01:13:17,570
Así, a táboa hash sería
iniciar a dimensión -

1597
01:13:17,570 --> 01:13:19,560
como o número de cadeas
que estaba inserindo?

1598
01:13:19,560 --> 01:13:22,170
>> Jason Hirschhorn: Faria
quere que sexa realmente grande.

1599
01:13:22,170 --> 01:13:23,910
Si

1600
01:13:23,910 --> 01:13:27,900
Aquí está unha foto do que nós
acaba de deseñar o cadro.

1601
01:13:27,900 --> 01:13:29,470
Unha vez máis, temos unha colisión ben aquí.

1602
01:13:29,470 --> 01:13:30,710
en 152.

1603
01:13:30,710 --> 01:13:33,570
E vai ver que creamos
unha lista ligada fóra del.

1604
01:13:33,570 --> 01:13:38,200

1605
01:13:38,200 --> 01:13:41,850
Unha vez máis, a táboa hash encadeamento separado
visión non é o que

1606
01:13:41,850 --> 01:13:45,590
ten que tomar para definir problemas
seis, pero é un que unha morea de

1607
01:13:45,590 --> 01:13:47,100
os alumnos tenden a tomar.

1608
01:13:47,100 --> 01:13:51,140
Entón, con esta nota, imos falar brevemente
antes de cabeza para fóra sobre o problema seis,

1609
01:13:51,140 --> 01:13:52,160
e entón eu vou compartir unha historia con vostede.

1610
01:13:52,160 --> 01:13:55,120
Temos tres minutos.

1611
01:13:55,120 --> 01:13:55,750
>> Problema definir seis.

1612
01:13:55,750 --> 01:13:57,790
Ten catro funcións -

1613
01:13:57,790 --> 01:14:02,430
carga, comprobar o tamaño ea descarga.

1614
01:14:02,430 --> 01:14:03,380
Carga -

1615
01:14:03,380 --> 01:14:07,120
ben, imos
sobre a carga agora.

1616
01:14:07,120 --> 01:14:09,330
Trazamos carga na tarxeta.

1617
01:14:09,330 --> 01:14:13,230
E nós nin sequera comezou a codificación de unha chea de
inserción nunha lista encadeada.

1618
01:14:13,230 --> 01:14:18,020
Así, a carga non é moito máis do que
o que acabamos facendo.

1619
01:14:18,020 --> 01:14:21,070
>> Check é cando ten
algo cargado.

1620
01:14:21,070 --> 01:14:22,580
É o mesmo proceso como este.

1621
01:14:22,580 --> 01:14:26,845
As mesmas dúas primeiras partes onde xoga
algo na función de hash

1622
01:14:26,845 --> 01:14:29,190
e conseguir o seu valor.

1623
01:14:29,190 --> 01:14:30,700
Pero agora non imos inserir-lo.

1624
01:14:30,700 --> 01:14:33,350
Agora nós estamos mirando para el.

1625
01:14:33,350 --> 01:14:37,130
Teño código de exemplo escrito por atopar
algo nunha lista encadeada.

1626
01:14:37,130 --> 01:14:38,250
Estimula-vos a practicar iso.

1627
01:14:38,250 --> 01:14:43,000
Pero intuitivamente atopar algo é
moi semellante ao da inserción de algo.

1628
01:14:43,000 --> 01:14:46,540
De feito, fixo un deseño de atopar
algo nunha lista encadeada, movendo-se

1629
01:14:46,540 --> 01:14:48,910
totalmente ata que chegou ao final.

1630
01:14:48,910 --> 01:14:52,430
E se chegou ao final e non podía
atopalo, el non está alí.

1631
01:14:52,430 --> 01:14:55,400
Entón, iso é cheque, esencialmente.

1632
01:14:55,400 --> 01:14:57,030
>> A continuación é o tamaño.

1633
01:14:57,030 --> 01:14:57,910
Imos saltar tamaño.

1634
01:14:57,910 --> 01:15:00,040
Finalmente descargar.

1635
01:15:00,040 --> 01:15:02,890
Unload é unha que non teñen atraído
na tarxeta ou codificados aínda.

1636
01:15:02,890 --> 01:15:05,990
Pero eu encouraged-lo a tentar codifica-lo
na nosa mostra exemplo lista encadeada.

1637
01:15:05,990 --> 01:15:11,440
Pero descargar intuitivamente
é semellante ao libre -

1638
01:15:11,440 --> 01:15:14,010
ou quero dicir é semellante para comprobar.

1639
01:15:14,010 --> 01:15:17,350
Excepto agora cada vez que vai
a través, non está simplemente comprobando a

1640
01:15:17,350 --> 01:15:19,090
mira se tes o valor alí.

1641
01:15:19,090 --> 01:15:22,490
Pero está tomando este nodo e
liberando-o, esencialmente.

1642
01:15:22,490 --> 01:15:23,610
Iso é o que descargar lle pide para facer.

1643
01:15:23,610 --> 01:15:24,670
Todo gratis vostede malloced.

1644
01:15:24,670 --> 01:15:27,480
Entón, está pasando por toda a lista
unha vez máis, pasando por todo o hash

1645
01:15:27,480 --> 01:15:27,760
mesa de novo.

1646
01:15:27,760 --> 01:15:29,240
Esta vez, Desactive
a ver que está aí.

1647
01:15:29,240 --> 01:15:31,080
Só liberar o que está aí.

1648
01:15:31,080 --> 01:15:33,260
>> E, finalmente, o tamaño.

1649
01:15:33,260 --> 01:15:34,350
Tamaño debe ser aplicada.

1650
01:15:34,350 --> 01:15:35,590
Se non aplicar o tamaño -

1651
01:15:35,590 --> 01:15:36,250
Vou dicir así.

1652
01:15:36,250 --> 01:15:39,740
Se non aplicar o tamaño exactamente
unha liña de código, incluíndo a

1653
01:15:39,740 --> 01:15:43,760
volver declaración, que é
facendo tamaño incorrectamente.

1654
01:15:43,760 --> 01:15:47,170
Polo tanto, asegúrese de que o tamaño, para o proxecto completo
puntos, está facendo isto en exactamente un

1655
01:15:47,170 --> 01:15:49,970
liña de código, incluíndo
a instrución de retorno.

1656
01:15:49,970 --> 01:15:52,450
>> E non aparcar aínda, Akchar.

1657
01:15:52,450 --> 01:15:53,700
Castor Eager.

1658
01:15:53,700 --> 01:15:55,820

1659
01:15:55,820 --> 01:16:01,300
Quería agradecer a vostedes
para vir a sección.

1660
01:16:01,300 --> 01:16:02,550
Teña un feliz Día das meiga.

1661
01:16:02,550 --> 01:16:05,300

1662
01:16:05,300 --> 01:16:05,960
Este é o meu traxe.

1663
01:16:05,960 --> 01:16:08,850
Eu vou estar a levar posto este xoves
se eu velo en horario de oficina.

1664
01:16:08,850 --> 01:16:14,640
E se está curioso para saber un pouco máis
fondo canto a este traxe, sentir

1665
01:16:14,640 --> 01:16:19,135
libre para comprobar a sección 2011
para unha historia sobre iso que eu son

1666
01:16:19,135 --> 01:16:20,900
vestindo a fantasía de cabaza.

1667
01:16:20,900 --> 01:16:23,680
E é unha historia triste.

1668
01:16:23,680 --> 01:16:27,050
Polo tanto, comproba que tes
algúns tecidos próximos.

1669
01:16:27,050 --> 01:16:28,680
Pero por que, se ten algunha
preguntas que eu vou ir por aquí

1670
01:16:28,680 --> 01:16:29,960
fóra despois de sección.

1671
01:16:29,960 --> 01:16:31,510
Boa sorte no conxunto de problemas seis.

1672
01:16:31,510 --> 01:16:33,540
E como sempre, se ten calquera
preguntas, deixe-me saber.

1673
01:16:33,540 --> 01:16:35,584