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

2
00:00:00,500 --> 00:00:05,120
[Música tocando]

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

4
00:00:12,026 --> 00:00:12,900
COLUMNA 1: Todo ben.

5
00:00:12,900 --> 00:00:14,600
Todos benvidos de volta á sección.

6
00:00:14,600 --> 00:00:18,660
Espero que todos están correctamente
recuperado do seu quiz

7
00:00:18,660 --> 00:00:19,510
desde a semana pasada.

8
00:00:19,510 --> 00:00:22,564
Sei que é un pouco tolo, ás veces.

9
00:00:22,564 --> 00:00:25,230
Como eu estaba dicindo antes, se está
dentro do desvío estándar,

10
00:00:25,230 --> 00:00:28,188
realmente non se preocupe con iso, especialmente
para unha sección menos cómodo.

11
00:00:28,188 --> 00:00:30,230
Isto é sobre onde debería estar.

12
00:00:30,230 --> 00:00:32,850
>> Se fixo grande, entón incrible.

13
00:00:32,850 --> 00:00:33,650
Kudos para vostede.

14
00:00:33,650 --> 00:00:36,149
E se pensas que precisa
un pouco máis de axuda, por favor

15
00:00:36,149 --> 00:00:38,140
Sinto-se libre para chegar
fóra a calquera dos FT.

16
00:00:38,140 --> 00:00:40,030
Estamos todos aquí para axudar.

17
00:00:40,030 --> 00:00:40,960
>> É por iso que nós ensinamos.

18
00:00:40,960 --> 00:00:44,550
É por iso que eu estou aquí toda luns para ti
rapaces e na oficina horas os xoves.

19
00:00:44,550 --> 00:00:48,130
Entón, por favor, Sinto-se a liberdade de me deixar saber
se está preocupado nada

20
00:00:48,130 --> 00:00:52,450
ou se hai algo sobre o quiz
que realmente quere abordar.

21
00:00:52,450 --> 00:00:56,940
>> Así, a axenda para hoxe é
todo sobre estruturas de datos.

22
00:00:56,940 --> 00:01:01,520
Algunhas delas son só vai ser só
para que obteña familiarizado con estes.

23
00:01:01,520 --> 00:01:04,870
Non poderá aplicar
los nesta clase.

24
00:01:04,870 --> 00:01:08,690
Algúns deles vai,
como para a súa pset ortográfico.

25
00:01:08,690 --> 00:01:11,380
>> Terá a súa elección
entre táboas hash e intentos.

26
00:01:11,380 --> 00:01:13,680
Entón, nós imos, sen dúbida imos sobre aqueles.

27
00:01:13,680 --> 00:01:18,690
Será sempre máis do tipo
unha sección de alto nivel hoxe, con todo,

28
00:01:18,690 --> 00:01:22,630
porque hai unha morea deles, e se
fomos para os detalles de implementación

29
00:01:22,630 --> 00:01:26,490
en todas elas, non teriamos
mesmo pasar por listas ligadas

30
00:01:26,490 --> 00:01:28,520
e quizais un pouco de táboas de hash.

31
00:01:28,520 --> 00:01:31,200
>> Entón, teña paciencia comigo.

32
00:01:31,200 --> 00:01:33,530
Non estamos indo facer
tanto de codificación desta vez.

33
00:01:33,530 --> 00:01:36,870
Se tes algunha preguntas sobre o tema
ou quere ver implementado

34
00:01:36,870 --> 00:01:39,260
ou probar por si mesmo,
Recomendo definitivamente

35
00:01:39,260 --> 00:01:44,250
indo study.cs50.net, que
ten exemplos de todos estes.

36
00:01:44,250 --> 00:01:46,400
Vai ter meus PowerPoints
coas notas que nós

37
00:01:46,400 --> 00:01:50,860
tenden a usar, así como algunha programación
exercicios, sobre todo para as cousas

38
00:01:50,860 --> 00:01:55,250
como listas ligadas e binario
árbores pilas e suxestións.

39
00:01:55,250 --> 00:01:59,590
Tan pouco máis alto nivel, que
Pode ser bo para vós.

40
00:01:59,590 --> 00:02:01,320
>> Entón, con iso, imos comezar.

41
00:02:01,320 --> 00:02:03,060
E tamén, quizzes sim--.

42
00:02:03,060 --> 00:02:06,550
Creo que a maioría de vostedes que están en
miña sección ten os seus cuestionarios,

43
00:02:06,550 --> 00:02:12,060
pero ninguén entra ou algún motivo
non, están aquí diante.

44
00:02:12,060 --> 00:02:12,740
>> Así listas ligadas.

45
00:02:12,740 --> 00:02:15,650
Sei que este tipo de vai
atrás antes do seu quiz.

46
00:02:15,650 --> 00:02:17,940
Esa foi a semana antes
que aprenden sobre iso.

47
00:02:17,940 --> 00:02:21,040
Pero, neste caso, nós imos
ir un pouco máis en profundidade.

48
00:02:21,040 --> 00:02:25,900
>> Entón, por que poderiamos elixir un
lista ligada a través dunha matriz?

49
00:02:25,900 --> 00:02:27,130
Que os distingue?

50
00:02:27,130 --> 00:02:27,630
Si?

51
00:02:27,630 --> 00:02:30,464
>> Audiencia: Pode ampliar un conectado
lista contra tamaño fixo dun array.

52
00:02:30,464 --> 00:02:31,171
COLUMNA 1: Certo.

53
00:02:31,171 --> 00:02:33,970
Unha matriz ten tamaño fixo mentres que unha
lista ligada ten un tamaño variable.

54
00:02:33,970 --> 00:02:36,970
Entón, se nós non sabemos como
tanto que queremos almacenar,

55
00:02:36,970 --> 00:02:39,880
unha lista ligada nos dá unha gran
forma de facelo porque podemos só

56
00:02:39,880 --> 00:02:43,730
engadir noutro nodo e engadir
outro nó e engadir noutro nodo.

57
00:02:43,730 --> 00:02:45,750
Pero o que podería ser un trade-off?

58
00:02:45,750 --> 00:02:49,521
Alguén se lembra do trade-off
entre matrices e listas ligadas?

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

60
00:02:50,020 --> 00:02:51,460
>> Audiencia: Ten que
percorrer todo o camiño

61
00:02:51,460 --> 00:02:53,738
a través da lista ligada
atopar un elemento nunha lista.

62
00:02:53,738 --> 00:02:55,570
Nunha matriz, pode
só atopar un elemento.

63
00:02:55,570 --> 00:02:56,278
>> COLUMNA 1: Certo.

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

65
00:02:57,120 --> 00:02:58,500
>> Audiencia: [inaudível].

66
00:02:58,500 --> 00:03:01,090
>> COLUMNA 1: Con matrices, temos
o que se chama de acceso aleatorio.

67
00:03:01,090 --> 00:03:04,820
Significa que, se queremos o que é
xa o quinto punto dunha lista

68
00:03:04,820 --> 00:03:07,230
ou o quinto punto da nosa
array podemos só agarralo.

69
00:03:07,230 --> 00:03:10,440
Se é unha lista ligada, temos
para percorrer, non?

70
00:03:10,440 --> 00:03:14,020
Entón acceder a un elemento en
unha matriz é constante de tempo,

71
00:03:14,020 --> 00:03:19,530
mentres que con unha lista ligada que sería
probablemente será o tempo lineal, porque quizais

72
00:03:19,530 --> 00:03:21,370
noso elemento é todo o camiño ao final.

73
00:03:21,370 --> 00:03:23,446
Temos que buscar a través de todo.

74
00:03:23,446 --> 00:03:25,320
Así, con todos estes datos
estruturas que imos

75
00:03:25,320 --> 00:03:29,330
gastar un pouco máis de tempo en diante,
cales son os puntos positivos e negativos.

76
00:03:29,330 --> 00:03:31,480
Cando podería queremos
usar un sobre o outro?

77
00:03:31,480 --> 00:03:34,970
E ese é o tipo de
gran cousa para levar.

78
00:03:34,970 --> 00:03:40,140
>> Polo tanto, temos aquí a
definición dun nodo.

79
00:03:40,140 --> 00:03:43,040
É como un elemento
nosa lista ligada, non?

80
00:03:43,040 --> 00:03:46,180
Entón, estamos todos familiarizado
coas nosas estruturas typedef,

81
00:03:46,180 --> 00:03:47,980
que fomos na avaliación da última vez.

82
00:03:47,980 --> 00:03:53,180
Era basicamente só crear
outro tipo de datos que poderiamos usar.

83
00:03:53,180 --> 00:03:57,930
>> E neste caso, é un nó
que realizará algún enteiro en.

84
00:03:57,930 --> 00:04:00,210
E entón o que é a segunda parte aquí?

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

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

87
00:04:05,677 --> 00:04:06,680
>> Audiencia: [inaudível].

88
00:04:06,680 --> 00:04:07,020
>> COLUMNA 1: Si.

89
00:04:07,020 --> 00:04:08,400
É un punteiro ao seguinte nodo.

90
00:04:08,400 --> 00:04:12,610
Polo tanto, este debe realmente estar aquí enriba.

91
00:04:12,610 --> 00:04:18,790
Este é un tipo de punteiro
nó á seguinte cousa.

92
00:04:18,790 --> 00:04:22,410
E iso é o que eles
engloba o noso nó.

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

94
00:04:24,060 --> 00:04:29,390
>> Todo ben, entón coa investigación, como estabamos
só dicindo antes da man, se está

95
00:04:29,390 --> 00:04:31,840
vai investigar,
ten que realmente facer unha iteración

96
00:04:31,840 --> 00:04:33,660
a través da súa lista ligada.

97
00:04:33,660 --> 00:04:38,530
Entón, se nós estamos mirando para o número
9, que comezaría na nosa cabeza

98
00:04:38,530 --> 00:04:41,520
e que nos sinala para o inicio
da nosa lista ligada, non?

99
00:04:41,520 --> 00:04:44,600
E nós dicimos: OK, fai iso
nó conter o número 9?

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

101
00:04:45,690 --> 00:04:47,500
>> Todo ben, vaia á seguinte.

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

103
00:04:48,312 --> 00:04:49,520
Será que contén o número 9?

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

105
00:04:50,570 --> 00:04:51,550
Segue o próximo.

106
00:04:51,550 --> 00:04:55,490
>> Entón temos que realmente iteración
a través da nosa lista ligada.

107
00:04:55,490 --> 00:05:00,070
Non podemos simplemente ir directamente onde 9 é.

108
00:05:00,070 --> 00:05:05,860
E se vostedes realmente queren
ver algúns pseudo-código alí enriba.

109
00:05:05,860 --> 00:05:10,420
Temos algunha función de busca aquí
que leva em-- o que fai falta en?

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

111
00:05:13,110 --> 00:05:14,320
¿Que pensas?

112
00:05:14,320 --> 00:05:15,960
Unha tan fácil.

113
00:05:15,960 --> 00:05:17,784
¿Que é iso?

114
00:05:17,784 --> 00:05:18,700
Audiencia: [inaudível].

115
00:05:18,700 --> 00:05:20,366
COLUMNA 1: O número que estamos buscando.

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

117
00:05:20,980 --> 00:05:22,875
E o que sería iso corresponde a?

118
00:05:22,875 --> 00:05:25,020
É un punteiro para?

119
00:05:25,020 --> 00:05:26,000
>> Audiencia: un nó.

120
00:05:26,000 --> 00:05:28,980
>> COLUMNA 1: Un nó á lista
que nós estamos mirando, non?

121
00:05:28,980 --> 00:05:33,700
Polo tanto, temos algúns nós son punteiro aquí.

122
00:05:33,700 --> 00:05:37,240
Este é un punto que vai
realmente iterado nosa lista.

123
00:05:37,240 --> 00:05:39,630
Nós configure-lo igual a lista
porque iso é só

124
00:05:39,630 --> 00:05:44,380
fixándose a igual ao
inicio da nosa lista ligada.

125
00:05:44,380 --> 00:05:50,660
>> E mentres non se NULL, mentres
aínda temos cousas na nosa lista,

126
00:05:50,660 --> 00:05:55,580
comprobar a ver se ese nodo ten
o número que estamos buscando.

127
00:05:55,580 --> 00:05:57,740
Devolve certo.

128
00:05:57,740 --> 00:06:01,070
Se non, actualiza-lo, non?

129
00:06:01,070 --> 00:06:04,870
>> De ser NULL, saímos nosa
while e voltar falso

130
00:06:04,870 --> 00:06:08,340
porque iso significa que non telo atopado.

131
00:06:08,340 --> 00:06:11,048
Será que todo o mundo comeza como funciona isto?

132
00:06:11,048 --> 00:06:11,548
Está ben.

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

134
00:06:14,940 --> 00:06:20,260
>> Así, coa inserción, ten
ter tres formas diferentes.

135
00:06:20,260 --> 00:06:25,250
Pode preceder, pode engadir
e pode introducir en sorte.

136
00:06:25,250 --> 00:06:28,215
Neste caso, estamos
vai facer un preceder.

137
00:06:28,215 --> 00:06:33,380
Alguén sabe como aqueles
tres casos pode ser diferente?

138
00:06:33,380 --> 00:06:36,920
>> Entón preceder significa que poñer
el diante da súa lista.

139
00:06:36,920 --> 00:06:39,770
Entón, isto significa que non importa
que o nodo é, non importa

140
00:06:39,770 --> 00:06:43,160
cal é o valor, vai
para poñelas aquí diante, OK?

141
00:06:43,160 --> 00:06:45,160
Será o primeiro
elemento na súa lista.

142
00:06:45,160 --> 00:06:49,510
>> Se anexo-lo, que vai
para ir á parte de atrás da súa lista.

143
00:06:49,510 --> 00:06:54,010
E inserir en variados significa que está
vai poñer realmente no lugar

144
00:06:54,010 --> 00:06:57,700
onde mantén a súa lista ligada ordenada.

145
00:06:57,700 --> 00:07:00,810
Unha vez máis, como se usa
os e cando usa

146
00:07:00,810 --> 00:07:02,530
vai ser variar segundo o caso.

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

148
00:07:05,834 --> 00:07:07,750
Se non ten
ser clasificado, anteposta tende

149
00:07:07,750 --> 00:07:10,460
ser o que a maioría da xente
usar, porque non fai

150
00:07:10,460 --> 00:07:15,680
Ten que pasar por toda a lista
para atopar o fin de engadir lo, non?

151
00:07:15,680 --> 00:07:17,720
Pode simplemente poñelas dereito.

152
00:07:17,720 --> 00:07:21,930
>> Entón, imos pasar por un
inserción 1 agora.

153
00:07:21,930 --> 00:07:26,360
Entón, unha cousa que eu vou
recomendo neste pset

154
00:07:26,360 --> 00:07:29,820
é chamar as cousas, como sempre.

155
00:07:29,820 --> 00:07:35,130
É moi importante que actualice
os punteiros na orde correcta

156
00:07:35,130 --> 00:07:38,620
porque se actualiza-los
un pouco fóra de orde,

157
00:07:38,620 --> 00:07:42,210
vai acabar
perda de partes da súa lista.

158
00:07:42,210 --> 00:07:49,680
>> Así, por exemplo, neste caso, estamos
contando a cabeza para só un punto a 1.

159
00:07:49,680 --> 00:07:56,070
Se nós só facelo
sen gardar este 1,

160
00:07:56,070 --> 00:07:58,570
nós non temos ningunha idea do que
1 debería apuntar agora

161
00:07:58,570 --> 00:08:02,490
porque perdemos o
cabeza apuntada.

162
00:08:02,490 --> 00:08:05,530
Entón, unha cousa para lembrar
cando está facendo un preceder

163
00:08:05,530 --> 00:08:09,630
é gardar o que o
cabeza puntos para o primeiro,

164
00:08:09,630 --> 00:08:15,210
Despois, asigne-o e actualiza
o que o seu novo nodo debe apuntar.

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

166
00:08:20,870 --> 00:08:22,560
Neste caso, esta é unha forma de facelo.

167
00:08:22,560 --> 00:08:25,440
>> Entón, se tivésemos feito isto dese xeito
onde nós só trasladado cabeza,

168
00:08:25,440 --> 00:08:30,320
perdemos basicamente nosa
lista enteira, non?

169
00:08:30,320 --> 00:08:38,000
Unha forma de facelo é ter un punto de
seguinte, e despois ter punto cabeza para 1.

170
00:08:38,000 --> 00:08:42,650
Ou pode facer como o tipo de
almacenamento temporal, de que falei.

171
00:08:42,650 --> 00:08:45,670
>> Pero a reatribuição seu
punteiros na orde correcta

172
00:08:45,670 --> 00:08:48,750
vai ser moi, moi
importante para este pset.

173
00:08:48,750 --> 00:08:53,140
Se non, vai ter un hash
mesa ou un intento que só será

174
00:08:53,140 --> 00:08:56,014
só unha parte das palabras que
quere e entón you're-- mmhmm?

175
00:08:56,014 --> 00:08:58,930
Audiencia: Cal foi o temporal
cousa de almacenamento que estaba falando?

176
00:08:58,930 --> 00:09:00,305
COLUMNA 1: O almacenamento temporal.

177
00:09:00,305 --> 00:09:02,760
Entón, basicamente, outra
xeito que podería facelo

178
00:09:02,760 --> 00:09:07,650
é almacenar o xefe de algo, como
almacena-lo na variable temporal.

179
00:09:07,650 --> 00:09:11,250
Atribuílo la a un e
logo actualizar 1 ao punto

180
00:09:11,250 --> 00:09:13,830
para calquera cabeza usado para ligar a.

181
00:09:13,830 --> 00:09:16,920
Deste xeito é obviamente
máis elegante, porque

182
00:09:16,920 --> 00:09:20,770
Non é necesario un valor temporal, pero
só ofrecer outra forma de facelo.

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

184
00:09:23,999 --> 00:09:25,790
E nós realmente temos
un código para esta.

185
00:09:25,790 --> 00:09:28,080
Así, para lista ligada, nós
realmente ten algún código.

186
00:09:28,080 --> 00:09:31,930
Entón, introduza aquí, este é antecedendo.

187
00:09:31,930 --> 00:09:34,290
Polo tanto, este entra nel na cabeza.

188
00:09:34,290 --> 00:09:38,820
>> Entón o primeiro, ten que
crear o seu novo nodo, por suposto,

189
00:09:38,820 --> 00:09:40,790
e comprobar se hai NULL.

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

191
00:09:43,250 --> 00:09:47,840
E entón tes que para asignar os valores.

192
00:09:47,840 --> 00:09:51,260
Sempre que crea un novo nodo, ten
Non sei o que está a apuntar cara ao próximo,

193
00:09:51,260 --> 00:09:54,560
así que quere arrincar para NULL.

194
00:09:54,560 --> 00:09:58,760
Se acabar apuntando a algo
outra cousa, é trasladado e está todo ben.

195
00:09:58,760 --> 00:10:00,740
Se é o primeiro
na lista, el que

196
00:10:00,740 --> 00:10:04,270
para ligar a NULL porque
iso é o final da lista.

197
00:10:04,270 --> 00:10:12,410
>> Entón para inserir-lo vemos aquí
está atribuíndo o seguinte valor do noso nodo

198
00:10:12,410 --> 00:10:17,380
para ser o cabeza,
que é o que tivemos aquí.

199
00:10:17,380 --> 00:10:19,930
Iso é o que nós fixemos.

200
00:10:19,930 --> 00:10:25,820
E entón nós estamos atribuíndo cabeza para punto
ao noso novo no, porque lembre,

201
00:10:25,820 --> 00:10:31,090
é algún novo punteiro para un nó,
e iso é o que é cabeza.

202
00:10:31,090 --> 00:10:34,370
É exactamente por iso que
ten ese asesor frecha.

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

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

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

206
00:10:38,130 --> 00:10:41,100
>> Audiencia: Será que temos que
arrincar novo xunto a NULL en primeiro lugar,

207
00:10:41,100 --> 00:10:44,240
ou podemos simplemente arrinque-lo de cabeza?

208
00:10:44,240 --> 00:10:48,210
>> COLUMNA 1: New próxima
ten que ser NULL para iniciar

209
00:10:48,210 --> 00:10:53,760
porque non sabe
onde vai ser.

210
00:10:53,760 --> 00:10:56,100
Ademais, esta é unha especie de
Así como un paradigma.

211
00:10:56,100 --> 00:10:59,900
Vostede define-lo igual a NULL só para facer
Asegúrese de que todas as bases están cubertas

212
00:10:59,900 --> 00:11:04,070
antes de facer calquera cambio de modo que
está sempre garantido que vai

213
00:11:04,070 --> 00:11:08,880
estar apuntando para un valor específico
contra como un valor de lixo.

214
00:11:08,880 --> 00:11:12,210
Porque, si, nós atribuímos
novo xunto automaticamente,

215
00:11:12,210 --> 00:11:15,420
pero é máis como unha
boas prácticas para arrincar

216
00:11:15,420 --> 00:11:19,270
desa forma e despois transferir.

217
00:11:19,270 --> 00:11:23,420
>> OK, entón dobremente ligada listas agora.

218
00:11:23,420 --> 00:11:24,601
Que pensamos?

219
00:11:24,601 --> 00:11:26,350
O que hai de diferente con
dobremente ligada listas?

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

221
00:11:30,750 --> 00:11:34,300
>> Así, nas nosas listas ligadas, podemos
só mover nunha dirección, non?

222
00:11:34,300 --> 00:11:35,270
Nós só temos a continuación.

223
00:11:35,270 --> 00:11:36,760
Nós só podemos ir á fronte.

224
00:11:36,760 --> 00:11:40,300
>> Cunha lista dobremente ligada,
Tamén podemos andar para tras.

225
00:11:40,300 --> 00:11:44,810
Polo tanto, temos non só a
número que desexa almacenar,

226
00:11:44,810 --> 00:11:50,110
temos onde apunta ao seguinte
e onde veu.

227
00:11:50,110 --> 00:11:52,865
Entón, iso permite
algúns mellores travesía.

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

229
00:11:56,620 --> 00:12:01,240
>> Entón nós dobremente vinculadas,
moi semellante, non?

230
00:12:01,240 --> 00:12:05,000
A única diferenza é que agora
teñen unha banda e unha anterior.

231
00:12:05,000 --> 00:12:06,235
É a única diferenza.

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

233
00:12:09,570 --> 00:12:14,790
>> Entón, se fósemos para preceder ou append-- nós
non teñen ningunha código para esta aquí - se

234
00:12:14,790 --> 00:12:17,830
pero se fose para intentar
inserir-lo, o importante

235
00:12:17,830 --> 00:12:19,980
é que ten que facer
Asegúrese de que está asignando

236
00:12:19,980 --> 00:12:23,360
tanto o anterior eo seu
preto punteiro correctamente.

237
00:12:23,360 --> 00:12:29,010
Polo tanto, neste caso, faría
non só arrincar seguinte,

238
00:12:29,010 --> 00:12:31,820
vostede arrinque anterior.

239
00:12:31,820 --> 00:12:36,960
Se estamos na parte superior da lista, nós
non só facer a cabeza igual novo,

240
00:12:36,960 --> 00:12:41,750
pero debe ser a nosa nova anterior
apuntar á cabeza, non?

241
00:12:41,750 --> 00:12:43,380
>> Esa é a única diferenza.

242
00:12:43,380 --> 00:12:47,200
E se queres máis práctica con
estes con listas ligadas, coa inserción,

243
00:12:47,200 --> 00:12:49,900
coa exclusión, coa inserción
nunha lista variada,

244
00:12:49,900 --> 00:12:52,670
confía study.cs50.net.

245
00:12:52,670 --> 00:12:54,870
Hai unha morea de grandes exercicios.

246
00:12:54,870 --> 00:12:55,870
Recomendo a eles.

247
00:12:55,870 --> 00:12:59,210
Gustaríame que tivésemos tempo para pasar por eles
pero hai unha morea de estruturas de datos

248
00:12:59,210 --> 00:13:01,530
para pasar.

249
00:13:01,530 --> 00:13:02,650
>> OK, entón táboas de hash.

250
00:13:02,650 --> 00:13:07,070
Este é probablemente o máis
pouco útil para a súa pset

251
00:13:07,070 --> 00:13:11,090
aquí, porque vai ser
implantación dun destes, ou un intento.

252
00:13:11,090 --> 00:13:12,200
Realmente me gusta de táboas de hash.

253
00:13:12,200 --> 00:13:13,110
Son moi legal.

254
00:13:13,110 --> 00:13:17,080
>> Entón, basicamente, o que
pasa é unha táboa hash

255
00:13:17,080 --> 00:13:22,050
é cando nós realmente necesitamos Speedy
inserción, exclusión e investigación.

256
00:13:22,050 --> 00:13:25,010
Estas son as cousas que estamos
priorizar nunha táboa hash.

257
00:13:25,010 --> 00:13:29,500
Poden ser moi grande,
mais, como veremos, con intentos,

258
00:13:29,500 --> 00:13:33,040
hai cousas que son moi grandes.

259
00:13:33,040 --> 00:13:38,330
>> Pero, basicamente, todo un hash
táboa é unha función hash

260
00:13:38,330 --> 00:13:47,215
que lle di que balde para que cada
dos seus datos, cada un dos seus elementos en.

261
00:13:47,215 --> 00:13:51,140
Un xeito sinxelo de pensar nunha táboa hash
é que non é só baldes de cousas,

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

263
00:13:51,770 --> 00:13:59,720
Entón, cando está clasificando as cousas por
como a primeira letra do seu nome,

264
00:13:59,720 --> 00:14:01,820
que é como unha especie de táboa de hash.

265
00:14:01,820 --> 00:14:06,180
>> Entón, se eu fose vostedes grupo é
en grupos de quen quere que o seu nome comeza

266
00:14:06,180 --> 00:14:11,670
cun aquí, ou quen queira que o aniversario
é en xaneiro, febreiro, marzo,

267
00:14:11,670 --> 00:14:15,220
sexa cal sexa, que é eficaz
creación dunha táboa hash.

268
00:14:15,220 --> 00:14:18,120
É só crear baldes que
clasificar os elementos en

269
00:14:18,120 --> 00:14:19,520
para que poida atopalos máis fácil.

270
00:14:19,520 --> 00:14:22,300
Así, deste xeito, cando eu teño
para atopar un de vós,

271
00:14:22,300 --> 00:14:24,680
Non teño que buscar
a través de cada un dos seus nomes.

272
00:14:24,680 --> 00:14:29,490
Podo ser como, oh, sei que
Aniversario de Danielle é em--

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

274
00:14:30,240 --> 00:14:30,948
COLUMNA 1: abril.

275
00:14:30,948 --> 00:14:33,120
Entón eu ollo na miña abril
balde, e con algunha sorte,

276
00:14:33,120 --> 00:14:38,270
vai ser a única persoa dentro, e
meu tempo era constante nese sentido,

277
00:14:38,270 --> 00:14:41,230
mentres que, se eu teño que mirar
a través dun grupo enteiro de persoas,

278
00:14:41,230 --> 00:14:43,090
que vai levar moito máis tempo.

279
00:14:43,090 --> 00:14:45,830
Entón, táboas hash son realmente só baldes.

280
00:14:45,830 --> 00:14:48,630
Un xeito doado de pensar deles.

281
00:14:48,630 --> 00:14:52,930
>> Entón, unha cousa moi importante sobre
unha táboa hash é unha función hash.

282
00:14:52,930 --> 00:14:58,140
Entón, as cousas que eu acabo de falar, como
súa primeira letra do seu nome

283
00:14:58,140 --> 00:15:01,450
ou o mes de aniversario,
estas son ideas que

284
00:15:01,450 --> 00:15:03,070
realmente se correlacionam cunha función hash.

285
00:15:03,070 --> 00:15:08,900
É só un xeito de decidir que
balde está elemento entra, OK?

286
00:15:08,900 --> 00:15:14,850
Polo tanto, para este pset, pode ollar para arriba
practicamente calquera función hash que quere.

287
00:15:14,850 --> 00:15:16,030
>> Non ten que ser o seu propio.

288
00:15:16,030 --> 00:15:21,140
Hai algúns realmente fresco fóra
hai que facer todo tipo de matemáticas tolo.

289
00:15:21,140 --> 00:15:25,170
E se quere facer o seu
corrector ortográfico super rápido,

290
00:15:25,170 --> 00:15:27,620
Eu definitivamente
ollar a un destes.

291
00:15:27,620 --> 00:15:32,390
>> Pero hai tamén o son
máis simple, como a computación

292
00:15:32,390 --> 00:15:39,010
a suma das palabras, como
cada letra ten un número.

293
00:15:39,010 --> 00:15:39,940
Calcular a suma.

294
00:15:39,940 --> 00:15:42,230
Que determina o balde.

295
00:15:42,230 --> 00:15:45,430
Eles tamén teñen as máis fáciles que
son só como toda a dun aquí,

296
00:15:45,430 --> 00:15:47,050
todo o B está aquí.

297
00:15:47,050 --> 00:15:48,920
Calquera destes.

298
00:15:48,920 --> 00:15:55,770
>> Basicamente, el só dille que
índice da matriz seu elemento debe ir.

299
00:15:55,770 --> 00:15:58,690
Basta decidir bucket--
é todo unha función hash é.

300
00:15:58,690 --> 00:16:04,180
Polo tanto, temos aquí un exemplo que é
só a primeira letra da cadea

301
00:16:04,180 --> 00:16:05,900
que eu estaba falando.

302
00:16:05,900 --> 00:16:11,900
>> Entón ten algún hash que é só o
primeira letra da frase, menos un,

303
00:16:11,900 --> 00:16:16,090
que lle dará algúns
número entre 0 e 25.

304
00:16:16,090 --> 00:16:20,790
E o que quere facer é
asegúrese de que isto representa

305
00:16:20,790 --> 00:16:24,110
o tamaño do seu hash de mesa--
cantos baldes existen.

306
00:16:24,110 --> 00:16:25,860
Con moitos destes
funcións de hash, son

307
00:16:25,860 --> 00:16:31,630
será o regreso de valores que pode
estar moi por riba do número de depósitos

308
00:16:31,630 --> 00:16:33,610
que realmente ten
na súa táboa de hash,

309
00:16:33,610 --> 00:16:37,240
entón tes que facer
Asegúrese e mod por aqueles.

310
00:16:37,240 --> 00:16:42,190
Se non, que vai dicir,
Oh, el debe estar en balde 5000

311
00:16:42,190 --> 00:16:46,040
pero só ten 30
baldes na súa táboa hash.

312
00:16:46,040 --> 00:16:49,360
E, por suposto, todos sabemos que é
vai producir algúns erros de tolos.

313
00:16:49,360 --> 00:16:52,870
Entón asegúrese de mod polo
tamaño da táboa hash.

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

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

316
00:16:58,930 --> 00:17:00,506
Así colisións.

317
00:17:00,506 --> 00:17:02,620
Están todos ben ata agora?

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

319
00:17:03,120 --> 00:17:05,900
>> Audiencia: Por que
voltar un valor tan grande?

320
00:17:05,900 --> 00:17:09,210
>> COLUMNA 1: En función do algoritmo
que a súa función de hash usa.

321
00:17:09,210 --> 00:17:12,270
Algúns deles han facer
multiplicación tolo.

322
00:17:12,270 --> 00:17:16,270
E é todo sobre a obtención de
unha distribución uniforme,

323
00:17:16,270 --> 00:17:18,490
para que realmente facer algunha
cousas malucas ás veces.

324
00:17:18,490 --> 00:17:20,960
Iso é todo.

325
00:17:20,960 --> 00:17:22,140
Algo máis?

326
00:17:22,140 --> 00:17:22,829
Está ben.

327
00:17:22,829 --> 00:17:24,480
>> Así colisións.

328
00:17:24,480 --> 00:17:29,270
Basicamente, como dixen anteriormente,
no mellor dos casos,

329
00:17:29,270 --> 00:17:32,040
calquera balde eu ollar é
terá unha cousa,

330
00:17:32,040 --> 00:17:34,160
entón eu non teño que mirar para todo, non?

331
00:17:34,160 --> 00:17:37,040
Eu non sei que está aí ou é
Non, e iso é o que realmente queremos.

332
00:17:37,040 --> 00:17:43,960
Pero se temos decenas de miles de
Os puntos de datos e inferior a ese número

333
00:17:43,960 --> 00:17:48,700
de baldes, nós imos ter
colisións onde finalmente algo

334
00:17:48,700 --> 00:17:54,210
terá que acabar nun
balde que xa ten un elemento.

335
00:17:54,210 --> 00:17:57,390
>> Entón a pregunta é, o que
que imos facer nese caso?

336
00:17:57,390 --> 00:17:58,480
O que imos facer?

337
00:17:58,480 --> 00:17:59,300
Xa temos algo alí?

338
00:17:59,300 --> 00:18:00,060
Será que simplemente xoga-lo fóra?

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

340
00:18:00,700 --> 00:18:01,980
Temos que manter os dous.

341
00:18:01,980 --> 00:18:06,400
Así, a forma que nós
normalmente facelo é o que?

342
00:18:06,400 --> 00:18:08,400
Cal é a estrutura de datos
que acabamos de falar?

343
00:18:08,400 --> 00:18:09,316
Audiencia: lista encadeada.

344
00:18:09,316 --> 00:18:10,500
COLUMNA 1: Unha lista ligada.

345
00:18:10,500 --> 00:18:16,640
Entón, agora, en vez de cada un destes
baldes ter só un elemento,

346
00:18:16,640 --> 00:18:24,020
que vai conter unha lista ligada de
os elementos que foron hash dentro del.

347
00:18:24,020 --> 00:18:27,588
OK, que todos tipo de tirou esa idea?

348
00:18:27,588 --> 00:18:30,546
Porque nós non poderiamos ter un array
por que non sabemos cantas cousas

349
00:18:30,546 --> 00:18:31,730
van estar alí.

350
00:18:31,730 --> 00:18:36,540
Unha lista ligada permítenos
ter só o número exacto que

351
00:18:36,540 --> 00:18:38,465
son mesturados que balde, non?

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

353
00:18:42,260 --> 00:18:50,500
>> Entón lineal de sondaxe é
basicamente este idea--

354
00:18:50,500 --> 00:18:52,300
é unha forma de xestionar a colisión.

355
00:18:52,300 --> 00:18:58,010
O que podes facer é, neste
caso, baga foi hash nun

356
00:18:58,010 --> 00:19:01,130
e xa temos
algo alí, só

357
00:19:01,130 --> 00:19:04,840
siga indo para abaixo ata
atopa un slot baleiro.

358
00:19:04,840 --> 00:19:06,370
Esta é unha forma de tratar con isto.

359
00:19:06,370 --> 00:19:09,020
A outra forma de xestionar
é co que acabamos de

360
00:19:09,020 --> 00:19:12,280
called-- o conectado
lista chámase fío.

361
00:19:12,280 --> 00:19:20,510
>> Entón, esa idea funciona se
súa táboa hash que pensa

362
00:19:20,510 --> 00:19:24,150
é moito maior que
seu conxunto de datos ou se

363
00:19:24,150 --> 00:19:28,870
quero tentar minimizar o encadeamento
ata que sexa absolutamente necesario.

364
00:19:28,870 --> 00:19:34,050
Entón, unha cousa é lineal
enquisa, obviamente, significa

365
00:19:34,050 --> 00:19:37,290
que a súa función de hash
non é tan útil

366
00:19:37,290 --> 00:19:42,200
porque vai acabar empregando
súa función de hash, quedando a un punto,

367
00:19:42,200 --> 00:19:46,400
vostede lineal sondar ata
nalgún lugar que está dispoñible.

368
00:19:46,400 --> 00:19:49,670
Pero agora, por suposto, nada
outra cousa que acaba por alí,

369
00:19:49,670 --> 00:19:52,050
vai ter que
buscar aínda máis abaixo.

370
00:19:52,050 --> 00:19:55,650
>> E hai moito máis
gasto de busca que

371
00:19:55,650 --> 00:19:59,820
vai á introdución dun elemento
na súa táboa hash agora, non?

372
00:19:59,820 --> 00:20:05,640
E agora cando vai tentar atopar
baga de novo, vai botar el,

373
00:20:05,640 --> 00:20:07,742
e que vai dicir:
Oh, mira no balde 1,

374
00:20:07,742 --> 00:20:09,700
e non será
no balde 1, entón está

375
00:20:09,700 --> 00:20:11,970
terá que atravesar
a través do resto destes.

376
00:20:11,970 --> 00:20:17,720
Entón, ás veces é útil,
pero na maior parte dos casos,

377
00:20:17,720 --> 00:20:22,660
imos dicir que
encadeamento é o que quere facer.

378
00:20:22,660 --> 00:20:25,520
>> Entón nós falamos sobre iso antes.

379
00:20:25,520 --> 00:20:27,812
Eu teño un pouco por diante de min.

380
00:20:27,812 --> 00:20:33,560
Pero o fío é basicamente que
cada balde na súa táboa hash

381
00:20:33,560 --> 00:20:36,120
é só unha lista ligada.

382
00:20:36,120 --> 00:20:39,660
>> Así, outra forma, é máis técnico
forma, pensar nunha táboa hash

383
00:20:39,660 --> 00:20:44,490
é que non é só unha matriz
de listas ligadas, que

384
00:20:44,490 --> 00:20:49,330
cando está escribindo o seu dicionario
e estás cargalo,

385
00:20:49,330 --> 00:20:52,070
pensar niso como unha
matriz de listas ligadas

386
00:20:52,070 --> 00:20:54,390
fará que sexa moito máis fácil
para que poida arrincar.

387
00:20:54,390 --> 00:20:57,680
>> Audiencia: Entón táboa hash
ten un tamaño pre-determinado,

388
00:20:57,680 --> 00:20:58,980
como un [inaudível] de baldes?

389
00:20:58,980 --> 00:20:59,220
>> COLUMNA 1: Certo.

390
00:20:59,220 --> 00:21:01,655
Por iso, ten un número definido de
baldes que determine--

391
00:21:01,655 --> 00:21:03,530
que vostedes deben
Sinto-se libre para xogar.

392
00:21:03,530 --> 00:21:05,269
Pode ser moi legal
a ver que pasa

393
00:21:05,269 --> 00:21:06,810
como cambiar o seu número de caçamba.

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

395
00:21:09,410 --> 00:21:11,510
Pero si, el ten un
definir o número de baldes.

396
00:21:11,510 --> 00:21:15,360
O que lle permite encaixar como
moitos elementos que precisa

397
00:21:15,360 --> 00:21:19,350
é este fío separado onde
ligaron listas en cada balde.

398
00:21:19,350 --> 00:21:22,850
Isto significa que a súa táboa hash
será exactamente o tamaño

399
00:21:22,850 --> 00:21:25,440
que precisa que sexa, non?

400
00:21:25,440 --> 00:21:27,358
Ese é o punto de listas ligadas.

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

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

403
00:21:32,480 --> 00:21:38,780
>> Por iso, todos OK alí?

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

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

406
00:21:40,300 --> 00:21:41,860
Que pasou?

407
00:21:41,860 --> 00:21:42,960
Realmente agora.

408
00:21:42,960 --> 00:21:45,250
Creo que alguén está me matando.

409
00:21:45,250 --> 00:21:52,060
>> OK, imos entrar
intentos, que son un pouco tolo.

410
00:21:52,060 --> 00:21:53,140
Gústame táboas de hash.

411
00:21:53,140 --> 00:21:54,460
Eu creo que son moi legal.

412
00:21:54,460 --> 00:21:56,710
Tries son legais tamén.

413
00:21:56,710 --> 00:21:59,590
>> Entón, alguén se lembra o que é un intento?

414
00:21:59,590 --> 00:22:01,740
Debería ir máis
brevemente na charla?

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

416
00:22:04,570 --> 00:22:06,377
Vostede recorda do tipo de como funciona?

417
00:22:06,377 --> 00:22:08,460
Audiencia: Eu só estou bailando
que pasar por iso.

418
00:22:08,460 --> 00:22:09,626
COLUMNA 1: Non pasar por iso.

419
00:22:09,626 --> 00:22:13,100
OK, nós realmente estamos indo a ir
sobre el agora é o que estamos dicindo.

420
00:22:13,100 --> 00:22:14,860
>> Audiencia: Isto é para unha árbore de recuperación.

421
00:22:14,860 --> 00:22:15,280
>> COLUMNA 1: Si.

422
00:22:15,280 --> 00:22:16,196
É unha árbore de recuperación.

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

424
00:22:16,960 --> 00:22:23,610
Entón, unha cousa a notar aquí é que nós
Está mirando para caracteres individuais

425
00:22:23,610 --> 00:22:24,480
aquí, non?

426
00:22:24,480 --> 00:22:29,710
>> Polo tanto, antes coa nosa función de hash, que
estaban mirando para as palabras como un todo,

427
00:22:29,710 --> 00:22:32,270
e agora estamos a buscar máis
aos personaxes, non?

428
00:22:32,270 --> 00:22:38,380
Polo tanto, temos Maxwell aquí e Mendel.

429
00:22:38,380 --> 00:22:47,840
Entón, basicamente, un try-- unha forma de pensar
sobre iso é que todos os niveis aquí

430
00:22:47,840 --> 00:22:49,000
é unha matriz de letras.

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

432
00:22:53,310 --> 00:22:55,790
Polo tanto, este é o nó raíz aquí, non?

433
00:22:55,790 --> 00:23:01,980
Isto ten todos os personaxes do
alfabeto ao comezo de cada palabra.

434
00:23:01,980 --> 00:23:06,480
>> E o que quere facer é
digamos, OK, temos algunha palabra M.

435
00:23:06,480 --> 00:23:10,590
Nós imos ollar para Maxwell, de xeito
imos para M. e M apunta a un enteiro

436
00:23:10,590 --> 00:23:14,800
outra matriz onde cada
palabra, mentres haxa

437
00:23:14,800 --> 00:23:17,044
é unha palabra que ten un
como a segunda carta,

438
00:23:17,044 --> 00:23:19,460
mentres que hai unha palabra que
ten B como a segunda carta,

439
00:23:19,460 --> 00:23:24,630
terá un punteiro
indo a algunha próxima matriz.

440
00:23:24,630 --> 00:23:29,290
>> Probablemente non hai unha
palabra que MP algo,

441
00:23:29,290 --> 00:23:32,980
Así, coa posición P no presente
array, que sería só NULL.

442
00:23:32,980 --> 00:23:38,840
El diría: OK, non hai ningunha palabra
que M seguido por un P, OK?

443
00:23:38,840 --> 00:23:43,100
Entón, se pensamos sobre iso, cada
unha desas cousas pequenas

444
00:23:43,100 --> 00:23:47,990
é realmente un destes
grandes conxuntos de A a Z.

445
00:23:47,990 --> 00:23:55,064
Entón, o que pode ser unha das cousas
que é unha especie de desvantaxe de un intento?

446
00:23:55,064 --> 00:23:56,500
>> Audiencia: Unha gran cantidade de memoria.

447
00:23:56,500 --> 00:23:59,940
>> COLUMNA 1: É unha tonelada de memoria, non?

448
00:23:59,940 --> 00:24:08,750
Cada un destes bloques aquí
representa 26 espazos, 26 matriz elemento.

449
00:24:08,750 --> 00:24:13,680
Entón intenta estar incrible pesada espazo.

450
00:24:13,680 --> 00:24:17,100
>> Pero son moi rápidos.

451
00:24:17,100 --> 00:24:22,540
Entón, incrible rápido, pero
realmente espazo ineficiente.

452
00:24:22,540 --> 00:24:24,810
Medio que ten que descubrir
cal deles quere.

453
00:24:24,810 --> 00:24:29,470
Estes son moi legal para a súa pset,
pero eles ocupan moita memoria,

454
00:24:29,470 --> 00:24:30,290
para que o comercio off.

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

456
00:24:31,480 --> 00:24:34,300
>> Audiencia: Sería posible
configurar un intento e, a continuación,

457
00:24:34,300 --> 00:24:37,967
xa que ten todo o
datos en que need--

458
00:24:37,967 --> 00:24:39,550
Non sei se isto tería sentido.

459
00:24:39,550 --> 00:24:42,200
Eu estaba me librar de todo o
Caracteres nulos, pero, a continuación,

460
00:24:42,200 --> 00:24:42,910
non sería capaz de indexar eles--

461
00:24:42,910 --> 00:24:43,275
>> COLUMNA 1: Aínda que deles.

462
00:24:43,275 --> 00:24:44,854
>> Audiencia: - do mesmo xeito cada vez.

463
00:24:44,854 --> 00:24:45,520
COLUMNA 1: Si.

464
00:24:45,520 --> 00:24:50,460
Debe dos caracteres nulos para deixar
Vostede sabe se non hai unha palabra alí.

465
00:24:50,460 --> 00:24:52,040
Ben se ten algo que quere?

466
00:24:52,040 --> 00:24:52,540
Está ben.

467
00:24:52,540 --> 00:24:54,581
Todo ben, entón imos
para ir un pouco máis

468
00:24:54,581 --> 00:24:58,920
no detalle técnico atrás
intentando traballar cun exemplo.

469
00:24:58,920 --> 00:25:01,490
>> OK, entón iso é o mesmo.

470
00:25:01,490 --> 00:25:06,290
Considerando que, nunha lista ligada, a nosa principal
tipo de-- cal é a palabra que quero? -

471
00:25:06,290 --> 00:25:08,350
como a construción de bloque era un nó.

472
00:25:08,350 --> 00:25:12,280
Nun intento, nós tamén temos un nó,
pero defínese de forma diferente.

473
00:25:12,280 --> 00:25:17,000
>> Polo tanto, temos algúns que bool
representa, en realidade, se unha palabra

474
00:25:17,000 --> 00:25:23,530
existe neste lugar, e logo,
temos algunha variedade aqui-- ou mellor,

475
00:25:23,530 --> 00:25:27,840
este é un punteiro para unha
matriz de 27 caracteres.

476
00:25:27,840 --> 00:25:33,339
E dicir, para, no presente caso, este
27-- Estou seguro que todos vostedes son como, espera,

477
00:25:33,339 --> 00:25:34,880
hai 26 letras no alfabeto.

478
00:25:34,880 --> 00:25:36,010
Por que temos 27?

479
00:25:36,010 --> 00:25:37,870
>> Así, dependendo do
forma de aplicar esta,

480
00:25:37,870 --> 00:25:43,240
dicir dun pset que
permitiu apóstrofos.

481
00:25:43,240 --> 00:25:46,010
É por iso que o extra.

482
00:25:46,010 --> 00:25:50,500
Tamén terá nalgún
casos o terminador nulo

483
00:25:50,500 --> 00:25:53,230
está incluída como un dos
caracteres que se admite ser,

484
00:25:53,230 --> 00:25:56,120
e é así que eles verifican a
ver se é o final da palabra.

485
00:25:56,120 --> 00:26:01,340
Se vostede está interesado, confía
Vídeo de Kevin en study.cs50,

486
00:26:01,340 --> 00:26:04,790
así como a Wikipedia ten
uns bos recursos alí.

487
00:26:04,790 --> 00:26:09,000
>> Pero imos pasar por só unha especie
de como pode traballar a través dun intento

488
00:26:09,000 --> 00:26:11,010
se está dado un.

489
00:26:11,010 --> 00:26:16,230
Polo tanto, temos unha super sinxelo aquí que
Ten as palabras "bat" e "zoom" neles.

490
00:26:16,230 --> 00:26:18,920
E como vemos aquí enriba,
este pequeno espazo aquí

491
00:26:18,920 --> 00:26:22,560
representa o noso bool que
di, si, esta é unha palabra.

492
00:26:22,560 --> 00:26:27,060
E entón iso ten a nosa
arrays de caracteres, non?

493
00:26:27,060 --> 00:26:33,480
>> Entón, nós estamos indo a percorrer
atopar "morcego" nesa intento.

494
00:26:33,480 --> 00:26:38,340
Entón comeza na parte superior, non?

495
00:26:38,340 --> 00:26:46,290
E sabemos que b corresponde a
o segundo índice, o segundo elemento

496
00:26:46,290 --> 00:26:47,840
Nesta matriz, porque a e b.

497
00:26:47,840 --> 00:26:51,340
Así, preto de un segundo.

498
00:26:51,340 --> 00:26:58,820
>> E di, Aceptar, legal, segue que en
a seguinte matriz, porque se nos lembrar,

499
00:26:58,820 --> 00:27:02,160
non é que cada un destes
en realidade, contén o elemento.

500
00:27:02,160 --> 00:27:07,110
Cada unha destas matrices
contén un punteiro, non?

501
00:27:07,110 --> 00:27:10,030
É unha distinción importante a facer.

502
00:27:10,030 --> 00:27:13,450
>> Sei que iso vai ser-- intentos son
realmente difícil de obter o primeiro tempo,

503
00:27:13,450 --> 00:27:15,241
polo que aínda que este é o
segunda ou terceira vez

504
00:27:15,241 --> 00:27:18,370
e aínda é o tipo
de parecer difícil,

505
00:27:18,370 --> 00:27:21,199
Eu prometer que se vai asistir
o mañá curto de novo,

506
00:27:21,199 --> 00:27:22,740
probablemente vai facer moito máis sentido.

507
00:27:22,740 --> 00:27:23,890
Leva moito para dixerir.

508
00:27:23,890 --> 00:27:27,800
Eu ás veces aínda son
como, espera, o que é un intento?

509
00:27:27,800 --> 00:27:29,080
Como eu uso iso?

510
00:27:29,080 --> 00:27:33,880
>> Entón temos b neste caso,
que é o noso segundo índice.

511
00:27:33,880 --> 00:27:40,240
Se tivésemos, por exemplo, c ou
d ou calquera outra carta,

512
00:27:40,240 --> 00:27:45,810
necesitamos mapear que volve ao índice
da nosa matriz que que corresponde a.

513
00:27:45,810 --> 00:27:56,930
Entón, nós tomaríamos como rchar e nós só
restar fóra dun para mapea-lo en 0-25.

514
00:27:56,930 --> 00:27:58,728
Todo o mundo bo como nós
mapear os nosos personaxes?

515
00:27:58,728 --> 00:28:00,440
Está ben.

516
00:28:00,440 --> 00:28:05,980
>> Entón imos para a segunda e nós
ver que, si, el non é NULL.

517
00:28:05,980 --> 00:28:07,780
Podemos pasar ao seguinte matriz.

518
00:28:07,780 --> 00:28:12,300
Entón imos ao seguinte conxunto aquí.

519
00:28:12,300 --> 00:28:15,500
>> E nós dicimos: OK, agora nós
que ver se un está aquí.

520
00:28:15,500 --> 00:28:18,590
É un nulo ou non é
realmente seguir adiante?

521
00:28:18,590 --> 00:28:21,880
Así, en realidade, un move
encamiñar nesta matriz.

522
00:28:21,880 --> 00:28:24,570
E nós dicimos: OK, t é a nosa última carta.

523
00:28:24,570 --> 00:28:27,580
Entón imos ao t no índice.

524
00:28:27,580 --> 00:28:30,120
E, entón, avanzar
porque non hai outro.

525
00:28:30,120 --> 00:28:38,340
E iso se di, basicamente, que, si,
el di que non é unha palabra aquí-

526
00:28:38,340 --> 00:28:41,750
que, se seguir este
camiño, chegou

527
00:28:41,750 --> 00:28:43,210
nunha palabra, que sabemos que é "bat".

528
00:28:43,210 --> 00:28:43,800
Si?

529
00:28:43,800 --> 00:28:46,770
>> Audiencia: É normal ter que
como índice 0 e, a continuación, ter unha especie en 1

530
00:28:46,770 --> 00:28:47,660
ou para ter ao final?

531
00:28:47,660 --> 00:28:48,243
>> COLUMNA 1: Non.

532
00:28:48,243 --> 00:28:55,360
Polo tanto, se miramos para o noso
declaración aquí, é un bool,

533
00:28:55,360 --> 00:28:59,490
polo que é o seu propio elemento no seu nó.

534
00:28:59,490 --> 00:29:03,331
Polo tanto, non é parte da matriz.

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

536
00:29:03,830 --> 00:29:08,370
Entón, cando nos terminais a nosa palabra e estamos
nesta matriz, o que queremos facer

537
00:29:08,370 --> 00:29:12,807
é facer unha comprobación para iso é unha palabra.

538
00:29:12,807 --> 00:29:14,390
E neste caso, el volvería si.

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

540
00:29:17,220 --> 00:29:24,090
>> Entón, nesa nota, sabemos que "zoo" -
sabemos como os seres humanos que "zoo" é unha palabra,

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

542
00:29:24,820 --> 00:29:28,990
Pero se tentar aquí sería
dicir, non, non é.

543
00:29:28,990 --> 00:29:33,980
E diría que porque nós
non designouno como unha palabra aquí.

544
00:29:33,980 --> 00:29:40,440
Aínda que poden atravesar
a través do presente matriz,

545
00:29:40,440 --> 00:29:43,890
este intento diría que non,
zoolóxico non está no seu dicionario

546
00:29:43,890 --> 00:29:47,070
porque non temos
designado como tal.

547
00:29:47,070 --> 00:29:52,870
>> Así, un xeito de facer isso--
Ah, desculpe, este.

548
00:29:52,870 --> 00:29:59,450
Polo tanto, neste caso, "zoo" non é
unha palabra, pero é na nosa intento.

549
00:29:59,450 --> 00:30:05,690
Pero neste, dicir que quere que el
introducir a palabra "baño", o que pasa

550
00:30:05,690 --> 00:30:08,260
é seguirmos through-- b, un t.

551
00:30:08,260 --> 00:30:11,820
Estamos nesa matriz, e
imos para buscar h.

552
00:30:11,820 --> 00:30:15,220
>> Neste caso, cando
mirar para o punteiro no h,

553
00:30:15,220 --> 00:30:17,890
está a apuntar cara NULL, OK?

554
00:30:17,890 --> 00:30:20,780
Entón, a menos que sexa explicitamente
apuntando a outra matriz,

555
00:30:20,780 --> 00:30:25,000
asumir que todo punteiros
nesta matriz están apuntando para null.

556
00:30:25,000 --> 00:30:28,270
Polo tanto, neste caso, h está apuntando
como nulo polo que non podemos facer nada,

557
00:30:28,270 --> 00:30:31,540
polo que sería tamén volver
falsa, "baño" non é aquí.

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

559
00:30:34,102 --> 00:30:35,810
Polo tanto, agora estamos realmente
vai pasar por

560
00:30:35,810 --> 00:30:39,790
como é que nós realmente dicir
que "zoo" é na nosa intento.

561
00:30:39,790 --> 00:30:42,920
Como é que imos introducir "zoo" na nosa intento?

562
00:30:42,920 --> 00:30:47,810
Así, do mesmo xeito que comezou co
nosa lista ligada, comezan na raíz.

563
00:30:47,810 --> 00:30:50,600
Cando estea en dúbida, comece
a raíz destas cousas.

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

565
00:30:53,330 --> 00:30:55,650
z existe neste, e fai.

566
00:30:55,650 --> 00:30:58,370
Entón está movendo
súa próxima matriz, OK?

567
00:30:58,370 --> 00:31:01,482
E entón o próximo,
podemos dicir, OK, se o hai?

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

569
00:31:03,000 --> 00:31:04,330
Este novo.

570
00:31:04,330 --> 00:31:08,670
>> E así, no noso próximo, dixemos,
OK, "zoo" xa existe aquí.

571
00:31:08,670 --> 00:31:12,440
Todo o que necesitamos facer é establecer este xeito
a verdade, que non é unha palabra alí.

572
00:31:12,440 --> 00:31:15,260
Se tivese seguido todo
ata antes dese punto,

573
00:31:15,260 --> 00:31:17,030
é unha palabra, polo que só
configure-lo igual a tal.

574
00:31:17,030 --> 00:31:17,530
Si?

575
00:31:17,530 --> 00:31:22,550
>> Audiencia: Entón fai iso
significa que "ba" é unha palabra tamén?

576
00:31:22,550 --> 00:31:24,120
>> COLUMNA 1: Non.

577
00:31:24,120 --> 00:31:28,870
Polo tanto, neste caso, "ba" obteriamos
aquí, diriamos que é unha palabra,

578
00:31:28,870 --> 00:31:31,590
e inda sería non.

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

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

581
00:31:33,740 --> 00:31:36,360
>> Audiencia: Entón, cando é un
palabra e di que si, el

582
00:31:36,360 --> 00:31:38,380
conterá a ir m?

583
00:31:38,380 --> 00:31:42,260
>> COLUMNA 1: Entón, isto ten que ver
com-- está cargando iso en.

584
00:31:42,260 --> 00:31:43,640
Vostede di "zoo" é unha palabra.

585
00:31:43,640 --> 00:31:47,020
Cando vai a check--
como, digamos que quere dicir,

586
00:31:47,020 --> 00:31:49,400
significa "zoo" existe neste dicionario?

587
00:31:49,400 --> 00:31:54,200
Só vai buscar "zoo"
e, a continuación, comprobar a ver se é unha palabra.

588
00:31:54,200 --> 00:31:57,291
Vostede non vai moverse
mediante m por iso non é

589
00:31:57,291 --> 00:31:58,290
o que está a procurar.

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

591
00:32:02,690 --> 00:32:08,070
>> Entón, se nós realmente quería
engadir "baño" neste intento,

592
00:32:08,070 --> 00:32:11,390
fariamos o mesmo
como fixemos con "zoo"

593
00:32:11,390 --> 00:32:15,380
excepto veriamos que cando nós
tentar chegar o momento, non existe.

594
00:32:15,380 --> 00:32:20,090
Entón pode pensar niso como un intento
para engadir un novo nodo nunha lista ligada,

595
00:32:20,090 --> 00:32:27,210
de xeito que sería necesario para engadir outro
unha desas matrices, así.

596
00:32:27,210 --> 00:32:35,670
E entón o que facemos é só definir o h
elemento desa matriz apuntando para iso.

597
00:32:35,670 --> 00:32:39,430
>> E entón, o que quere facer aquí?

598
00:32:39,430 --> 00:32:43,110
Engadir lo igual a true
porque é unha palabra.

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

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

601
00:32:48,150 --> 00:32:48,700
Sei.

602
00:32:48,700 --> 00:32:51,170
Tenta non son o máis emocionante.

603
00:32:51,170 --> 00:32:54,250
Confío en min, sei.

604
00:32:54,250 --> 00:32:58,040
>> Entón, unha cousa a entender con intentos,
Eu dixen, son moi eficientes.

605
00:32:58,040 --> 00:33:00,080
Entón, nós vimos eles
levar ata unha tonelada de espazo.

606
00:33:00,080 --> 00:33:01,370
Son o tipo de confundir.

607
00:33:01,370 --> 00:33:03,367
Entón, por que nós nunca usalos?

608
00:33:03,367 --> 00:33:05,450
Usan estes porque son
incrible eficiente.

609
00:33:05,450 --> 00:33:08,130
>> Entón, se está sempre buscando
unha palabra, só son

610
00:33:08,130 --> 00:33:10,450
delimitada pola lonxitude da palabra.

611
00:33:10,450 --> 00:33:15,210
Entón, se está a buscar un
palabra que ten unha lonxitude de cinco,

612
00:33:15,210 --> 00:33:20,940
está sempre só terá que
facer, como máximo, cinco comparacións, OK?

613
00:33:20,940 --> 00:33:25,780
Así, torna-se, basicamente, unha constante.

614
00:33:25,780 --> 00:33:29,150
Como a inserción e investigación
son basicamente constante de tempo.

615
00:33:29,150 --> 00:33:33,750
>> Entón, se pode nunca chegar
algo en tempo constante,

616
00:33:33,750 --> 00:33:35,150
que é tan bo como el gañou.

617
00:33:35,150 --> 00:33:37,990
Non pode ir mellor do que
constante de tempo para estas cousas.

618
00:33:37,990 --> 00:33:43,150
Así que é un dos
enormes vantaxes de intentos.

619
00:33:43,150 --> 00:33:46,780
>> Pero é moito espazo.

620
00:33:46,780 --> 00:33:50,380
Entón medio que ten que decidir
o que é máis importante para vostede.

621
00:33:50,380 --> 00:33:54,700
E en computadores de hoxe, o
espazo que un intento pode levar ata

622
00:33:54,700 --> 00:33:57,740
quizais non afecta
que moito, pero quizais

623
00:33:57,740 --> 00:34:01,350
está lidando con algo
que ten moito, moito máis cousas,

624
00:34:01,350 --> 00:34:02,810
e un intento só non é razoable.

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

626
00:34:03,000 --> 00:34:05,610
>> Audiencia: Agarde, entón ten 26
letras en cada un?

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

628
00:34:07,440 --> 00:34:08,570
Si, ten 26.

629
00:34:08,570 --> 00:34:16,984
Ten algunha é marcador de texto e, a continuación,
ten 26 indicadores en cada un.

630
00:34:16,984 --> 00:34:17,775
E eles están ponto--

631
00:34:17,775 --> 00:34:20,280
>> Audiencia: E cada 26 anos,
que cada un deles ten 26?

632
00:34:20,280 --> 00:34:21,500
>> COLUMNA 1: Si.

633
00:34:21,500 --> 00:34:27,460
E é por iso que, como pode
ver, el se expande rapidamente.

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

635
00:34:28,130 --> 00:34:32,524
Entón, nós estamos indo a entrar en árbores, o que
Eu sinto que é máis fácil e, probablemente,

636
00:34:32,524 --> 00:34:36,150
ser un pouco agradable indulto
desde intentos alí.

637
00:34:36,150 --> 00:34:39,620
Polo tanto, agardamos que a maioría de vós
vin unha árbore antes.

638
00:34:39,620 --> 00:34:41,820
Non como o bastante
os de fóra, que eu

639
00:34:41,820 --> 00:34:44,340
Non sei se alguén
foi ao ar recentemente.

640
00:34:44,340 --> 00:34:49,230
Fun colleita da mazá este fin de semana,
e Oh meu Deus, el era fermoso.

641
00:34:49,230 --> 00:34:52,250
Eu non sabía que as follas
podería parecer que fermosa.

642
00:34:52,250 --> 00:34:53,610
>> Polo tanto, esta é só unha árbore, non?

643
00:34:53,610 --> 00:34:56,790
É só un nó, e
apunta a unha morea de outros nós.

644
00:34:56,790 --> 00:34:59,570
Como pode ver aquí, este é
tipo de un tema recurrente.

645
00:34:59,570 --> 00:35:03,720
Nodes apuntando para nós é unha especie de
a esencia de moitas estruturas de datos.

646
00:35:03,720 --> 00:35:06,670
Depende só de como nós
telos uns a outros para apuntar

647
00:35:06,670 --> 00:35:08,600
e como nós percorremos
a través deles e como nós

648
00:35:08,600 --> 00:35:14,500
inserir cousas que determina
as súas diferentes características.

649
00:35:14,500 --> 00:35:17,600
>> Entón, só tes que algo de terminoloxía,
que eu usei antes.

650
00:35:17,600 --> 00:35:20,010
Entón raíz é o que está na parte superior.

651
00:35:20,010 --> 00:35:21,200
É onde sempre comezar.

652
00:35:21,200 --> 00:35:23,610
Pode pensar niso como a cabeza tamén.

653
00:35:23,610 --> 00:35:28,750
Pero, para as árbores, que tenden a
se refiren a el como a raíz.

654
00:35:28,750 --> 00:35:32,820
>> Calquera cousa no fondo aqui--
no moi, moi bottom--

655
00:35:32,820 --> 00:35:34,500
follas son consideradas.

656
00:35:34,500 --> 00:35:37,210
Por iso, vai xunto co
cousa árbore enteira, non?

657
00:35:37,210 --> 00:35:39,860
As follas son nos bordos da súa árbore.

658
00:35:39,860 --> 00:35:45,820
>> E despois temos tamén un par de
canto de falar de nós en relación

659
00:35:45,820 --> 00:35:46,680
uns cos outros.

660
00:35:46,680 --> 00:35:49,700
Polo tanto, temos pai,
fillos e irmáns.

661
00:35:49,700 --> 00:35:56,260
Polo tanto, neste caso, é o 3
-Nai de 5, 6, e 7.

662
00:35:56,260 --> 00:36:00,370
Entón, o pai é o que está
un paso por riba de todo o que está a

663
00:36:00,370 --> 00:36:02,940
referíndose se, polo que só
como unha árbore xenealóxica.

664
00:36:02,940 --> 00:36:07,090
Afortunadamente, iso é todo un pouco
pouco máis intuitivo que os intentos.

665
00:36:07,090 --> 00:36:10,970
>> Os irmáns son os que teñen
o mesmo pai, non?

666
00:36:10,970 --> 00:36:13,470
Eles están no mesmo nivel aquí.

667
00:36:13,470 --> 00:36:16,960
E entón, como eu estaba
dicindo que os fillos son só

668
00:36:16,960 --> 00:36:22,630
todo o que é un chanzo por baixo
o no en cuestión, OK?

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

670
00:36:23,470 --> 00:36:25,610
Así, unha árbore binaria.

671
00:36:25,610 --> 00:36:31,450
Alguén pode arriscar un palpite nun dos
as características da árbore binaria?

672
00:36:31,450 --> 00:36:32,770
>> Audiencia: Max dúas follas.

673
00:36:32,770 --> 00:36:33,478
>> COLUMNA 1: Certo.

674
00:36:33,478 --> 00:36:34,640
Así máximo de dúas follas.

675
00:36:34,640 --> 00:36:39,730
Así, nun presente antes, tivemos un regalo
que tiña tres, pero dunha árbore binaria,

676
00:36:39,730 --> 00:36:45,000
ten un máximo de dous
nenos por pais, non?

677
00:36:45,000 --> 00:36:46,970
Hai outro
característica interesante.

678
00:36:46,970 --> 00:36:51,550
Alguén sabe iso?

679
00:36:51,550 --> 00:36:52,620
Árbore binaria.

680
00:36:52,620 --> 00:37:00,350
>> Así, unha árbore binaria terá todo
en as-- este non é sorted--

681
00:37:00,350 --> 00:37:05,320
pero dunha árbore binaria clasificados,
todo á dereita

682
00:37:05,320 --> 00:37:08,530
é maior que a nai,
e todo á esquerda

683
00:37:08,530 --> 00:37:10,035
é menor que a nai.

684
00:37:10,035 --> 00:37:15,690
E iso foi un quiz
pregunta antes, entón é bo saber.

685
00:37:15,690 --> 00:37:19,500
Entón, o xeito no que definimos tanto,
de novo, temos outro nodo.

686
00:37:19,500 --> 00:37:21,880
Este é moi parecido ao que?

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

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

689
00:37:28,836 --> 00:37:29,320
>> Audiencia: Linked listas

690
00:37:29,320 --> 00:37:31,100
>> COLUMNA 1: Unha lista ligada dobre, non?

691
00:37:31,100 --> 00:37:33,690
Entón, se substituírmos este
con anterior e seguinte,

692
00:37:33,690 --> 00:37:35,670
esta sería unha lista dobremente ligada.

693
00:37:35,670 --> 00:37:40,125
Pero, neste caso, nós realmente
ter esquerda e dereita e é iso.

694
00:37:40,125 --> 00:37:41,500
Se non, é o mesmo.

695
00:37:41,500 --> 00:37:43,374
Aínda temos o elemento
está a buscar,

696
00:37:43,374 --> 00:37:45,988
e só ten dous punteiros
indo ao que vén a continuación.

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

698
00:37:49,210 --> 00:37:51,870
Si, entón árbore binaria de busca.

699
00:37:51,870 --> 00:37:57,665
Se se decata todo no
aquí é maior than--

700
00:37:57,665 --> 00:37:59,850
ou todo inmediatamente
a dereita aquí

701
00:37:59,850 --> 00:38:02,840
é maior que, todo
aquí é inferior a.

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

703
00:38:06,980 --> 00:38:14,000
>> Entón, se fósemos buscar, el
que mirar moi preto de procura binaria

704
00:38:14,000 --> 00:38:14,910
aquí, non?

705
00:38:14,910 --> 00:38:17,640
Excepto no canto de mirar
na metade da matriz,

706
00:38:17,640 --> 00:38:21,720
estamos só mirando para a esquerda ou
lado ou do lado dereito da árbore.

707
00:38:21,720 --> 00:38:24,850
Entón, el está un pouco máis simple, eu creo.

708
00:38:24,850 --> 00:38:29,300
>> Polo tanto, se a súa raíz é NULL,
obviamente, é simplemente falso.

709
00:38:29,300 --> 00:38:33,470
E se está alí, obviamente, é verdade.

710
00:38:33,470 --> 00:38:35,320
De ser menor que, buscamos a esquerda.

711
00:38:35,320 --> 00:38:37,070
De ser maior que,
buscamos a dereita.

712
00:38:37,070 --> 00:38:39,890
É exactamente como busca binaria,
só unha estrutura de datos diferente

713
00:38:39,890 --> 00:38:40,600
que estamos a usar.

714
00:38:40,600 --> 00:38:42,790
En vez dunha matriz,
é só unha árbore binaria.

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

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

717
00:38:48,090 --> 00:38:51,550
E tamén, parece que
pode ter un pouco de tempo.

718
00:38:51,550 --> 00:38:54,460
Se facemos iso, estou feliz de ir
sobre nada diso de novo.

719
00:38:54,460 --> 00:38:56,856
OK, entón apilar.

720
00:38:56,856 --> 00:39:02,695
Alguén recorda o que stacks--
calquera características dunha pila?

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

722
00:39:05,550 --> 00:39:10,400
>> OK, así que a maioría de nós, eu creo,
comer na cea halls--

723
00:39:10,400 --> 00:39:13,100
tanto como nós pode non gustar.

724
00:39:13,100 --> 00:39:16,900
Pero, obviamente, pode pensar en unha pila
literalmente só como unha pila de bandexas

725
00:39:16,900 --> 00:39:18,460
ou unha pila de cousas.

726
00:39:18,460 --> 00:39:21,820
E o que é importante
para entender é que é

727
00:39:21,820 --> 00:39:26,850
something-- a característica
que podemos chamalo por-- é LIFO.

728
00:39:26,850 --> 00:39:28,450
Alguén sabe o que significa isto?

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

730
00:39:29,070 --> 00:39:30,650
>> Audiencia: último a entrar, primeiro en saír.

731
00:39:30,650 --> 00:39:32,250
>> COLUMNA 1: Dereito, último a entrar, primeiro en saír.

732
00:39:32,250 --> 00:39:36,585
Entón, se sabemos si imos apilar as cousas
se, a cousa máis fácil de coller off--

733
00:39:36,585 --> 00:39:39,570
e quizais o único que pode incorporarse
off, a nosa pila é grande enough--

734
00:39:39,570 --> 00:39:40,850
é aquel elemento superior.

735
00:39:40,850 --> 00:39:43,460
Entón o que foi posto en
last-- como vemos aquí,

736
00:39:43,460 --> 00:39:46,370
todo o que foi empurrado
na maioría recently-- é

737
00:39:46,370 --> 00:39:51,160
será o primeiro
cousa que nós pop off, OK?

738
00:39:51,160 --> 00:39:56,324
>> Entón o que temos aquí é
outra struct typedef.

739
00:39:56,324 --> 00:39:58,740
Isto é realmente só como un
Bater Curso de estrutura de datos,

740
00:39:58,740 --> 00:40:01,650
por iso hai moito xogado vós.

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

742
00:40:02,540 --> 00:40:04,970
Entón, unha struct.

743
00:40:04,970 --> 00:40:06,740
Yay para estruturas.

744
00:40:06,740 --> 00:40:16,660
>> E neste caso, é un punteiro
para unha matriz que ten algunha capacidade.

745
00:40:16,660 --> 00:40:20,830
Entón, iso representa a nosa pila
aquí, como a nosa matriz real

746
00:40:20,830 --> 00:40:22,520
que está sostendo os nosos elementos.

747
00:40:22,520 --> 00:40:24,850
E entón aquí temos algúns tamaño.

748
00:40:24,850 --> 00:40:31,170
>> E xeralmente, quere manter
pista de quão grande é a túa stack

749
00:40:31,170 --> 00:40:36,180
porque o que permitirá
cómpre facer é se sabe o tamaño,

750
00:40:36,180 --> 00:40:39,170
el permite que di,
OK, eu son a capacidade?

751
00:40:39,170 --> 00:40:40,570
Podo engadir algo máis?

752
00:40:40,570 --> 00:40:44,650
E tamén lle di
onde a parte superior do seu stack

753
00:40:44,650 --> 00:40:48,180
É así que sabe o que
pode realmente despegar.

754
00:40:48,180 --> 00:40:51,760
E iso realmente vai
ser un pouco máis claro.

755
00:40:51,760 --> 00:40:57,350
>> Así, por impulso, unha cousa, se
nunca foron para aplicar impulso,

756
00:40:57,350 --> 00:41:01,330
como eu estaba dicindo, o
pila ten un tamaño limitado, non?

757
00:41:01,330 --> 00:41:03,990
A nosa matriz tiña algunha capacidade.

758
00:41:03,990 --> 00:41:04,910
É unha matriz.

759
00:41:04,910 --> 00:41:08,930
É un tamaño fixo, polo que necesitamos
asegúrese de que non estamos poñendo máis

760
00:41:08,930 --> 00:41:11,950
na nosa matriz do que nós
realmente ten espazo para.

761
00:41:11,950 --> 00:41:16,900
>> Entón, cando está creando un impulso
función, o primeiro que fai é dicir, OK,

762
00:41:16,900 --> 00:41:18,570
eu teño espazo na miña pila?

763
00:41:18,570 --> 00:41:23,330
Porque se eu non fai iso, desculpe,
Non podo gardar o seu elemento.

764
00:41:23,330 --> 00:41:28,980
Se eu fai iso, entón quere almacenar
Lo na parte superior da pila, á dereita?

765
00:41:28,980 --> 00:41:31,325
>> E é por iso que temos
manter o control do noso tamaño.

766
00:41:31,325 --> 00:41:35,290
Se non manter o control do noso tamaño,
Non sabemos onde poñelas.

767
00:41:35,290 --> 00:41:39,035
Non sabemos cantas cousas
están na nosa matriz xa.

768
00:41:39,035 --> 00:41:41,410
Como evidentemente hai formas
que quizais podería facelo.

769
00:41:41,410 --> 00:41:44,610
Pode arrincar todo para NULL
e, a continuación, comproba o último NULL,

770
00:41:44,610 --> 00:41:47,950
pero unha cousa moito máis fácil é só
quere dicir, OK, manter o control de tamaño.

771
00:41:47,950 --> 00:41:51,840
Como sei que eu teño catro elementos
na miña matriz, entón a seguinte cousa

772
00:41:51,840 --> 00:41:55,930
que poñer, somos
indo para almacenar o índice 4.

773
00:41:55,930 --> 00:42:00,940
E entón, por suposto, isto significa que
vostede empurrou algo correctamente

774
00:42:00,940 --> 00:42:03,320
no seu stack, ten
quere aumentar o tamaño

775
00:42:03,320 --> 00:42:08,880
para que vostede sabe onde está a
que pode empurrar máis cousas sobre.

776
00:42:08,880 --> 00:42:12,730
>> Entón, se estamos tentando pop
algo fóra da pila,

777
00:42:12,730 --> 00:42:16,072
o que podería ser o primeiro
que quere comprobar?

778
00:42:16,072 --> 00:42:18,030
Estás a tomar
algo fóra da súa pila.

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

780
00:42:21,710 --> 00:42:24,781
Está seguro de que hai
algo na súa pila?

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

782
00:42:25,280 --> 00:42:26,894
Entón, o que podemos querer comprobar?

783
00:42:26,894 --> 00:42:27,810
>> Audiencia: [inaudível].

784
00:42:27,810 --> 00:42:29,880
COLUMNA 1: Comprobe o tamaño?

785
00:42:29,880 --> 00:42:31,840
Tamaño.

786
00:42:31,840 --> 00:42:38,520
Por iso, queremos comprobar se
noso tamaño é maior que 0, OK?

787
00:42:38,520 --> 00:42:44,970
E se é, entón queremos diminuír
noso tamaño por 0 e voltar iso.

788
00:42:44,970 --> 00:42:45,840
Por que?

789
00:42:45,840 --> 00:42:49,950
>> No primeiro fomos
empurrando, nós empurrou

790
00:42:49,950 --> 00:42:52,460
sobre o tamaño eo tamaño actualizado.

791
00:42:52,460 --> 00:42:57,850
Neste caso, estamos diminuíndo o tamaño
e despois tiralo, arrancando-o

792
00:42:57,850 --> 00:42:58,952
da nosa matriz.

793
00:42:58,952 --> 00:42:59,826
Por que facemos isto?

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

795
00:43:04,800 --> 00:43:11,811
Entón, se eu teño unha cousa na miña pila,
cal sería o meu tamaño en que punto?

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

797
00:43:13,140 --> 00:43:15,180
>> E onde está almacenado o elemento 1?

798
00:43:15,180 --> 00:43:17,621
En que índice?

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

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

801
00:43:19,060 --> 00:43:22,800
Polo tanto, neste caso, nos
sempre que facer sure--

802
00:43:22,800 --> 00:43:27,630
no canto de volver
tamaño menos 1, porque nós

803
00:43:27,630 --> 00:43:31,730
saber que o noso elemento é
será almacenado a unha menor

804
00:43:31,730 --> 00:43:34,705
calquera que sexa o noso tamaño é, este
só coida del.

805
00:43:34,705 --> 00:43:36,080
É un xeito un pouco máis elegante.

806
00:43:36,080 --> 00:43:41,220
E nós só diminuír a nosa
tamaño e, a continuación, voltar tamaño.

807
00:43:41,220 --> 00:43:42,330
Mmhmm?

808
00:43:42,330 --> 00:43:45,300
>> Audiencia: Creo que só en xeral,
por que esta estrutura de datos

809
00:43:45,300 --> 00:43:47,800
ser beneficioso?

810
00:43:47,800 --> 00:43:50,660
>> COLUMNA 1: Depende do seu contexto.

811
00:43:50,660 --> 00:43:57,420
Así, para algunhas das teorías,
se está a traballar com-- OK,

812
00:43:57,420 --> 00:44:02,750
déixeme ver se hai un beneficioso
que é beneficioso para máis de fóra

813
00:44:02,750 --> 00:44:05,420
de CS.

814
00:44:05,420 --> 00:44:15,780
Con pilas, a calquera hora que precisa
manter o control de algo que

815
00:44:15,780 --> 00:44:20,456
é o engadido máis recentemente é cando
vai querer usar unha pila.

816
00:44:20,456 --> 00:44:24,770
>> E eu non podo pensar en unha boa
exemplo do que agora.

817
00:44:24,770 --> 00:44:29,955
Pero sempre que a última
cousa é máis importante para vostede,

818
00:44:29,955 --> 00:44:31,705
que é cando unha pila
será útil.

819
00:44:31,705 --> 00:44:35,797

820
00:44:35,797 --> 00:44:39,330
Estou intentando pensar se
hai unha boa para iso.

821
00:44:39,330 --> 00:44:43,720
Se eu pensar nun bo exemplo na seguinte
20 minutos, seguramente vou che dicir.

822
00:44:43,720 --> 00:44:49,455
>> Pero en xeral, se hai algo,
como dixen a maioría, onde máis recente

823
00:44:49,455 --> 00:44:52,470
é o máis importante, que é
onde unha pila entra en xogo.

824
00:44:52,470 --> 00:44:58,860
Considerando as filas son unha especie de oposto.

825
00:44:58,860 --> 00:44:59,870
E todos os cans pequenos.

826
00:44:59,870 --> 00:45:00,890
Non é esta a gran, non?

827
00:45:00,890 --> 00:45:03,299
Eu sinto que eu debería
só ten un video coello

828
00:45:03,299 --> 00:45:05,090
á dereita no medio
sección para vós

829
00:45:05,090 --> 00:45:08,870
porque este é un corte intenso.

830
00:45:08,870 --> 00:45:10,480
>> Entón unha cola.

831
00:45:10,480 --> 00:45:12,710
Basicamente, unha fila é como unha liña.

832
00:45:12,710 --> 00:45:15,780
Vostedes Estou seguro de que uso iso todos os días,
así como nas nosas salas de cea.

833
00:45:15,780 --> 00:45:18,160
Entón, nós temos que ir en
e chegar nas nosas bandexas, eu son

834
00:45:18,160 --> 00:45:21,260
se ten que esperar na cola
para roubar ou obter o seu alimento.

835
00:45:21,260 --> 00:45:24,650
>> Así, a diferenza aquí
é que este é o FIFO.

836
00:45:24,650 --> 00:45:30,090
Entón, se LIFO foi o último en entrar, primeiro
fóra, FIFO é o primeiro en entrar, primeiro fóra.

837
00:45:30,090 --> 00:45:33,400
Polo tanto, este é o lugar onde todo o que poñer
en primeiro lugar é a súa máis importante.

838
00:45:33,400 --> 00:45:35,540
Entón, se estaba esperando
nun linha-- pode vostede

839
00:45:35,540 --> 00:45:39,130
imaxina se fose a
ir buscar o novo iPhone

840
00:45:39,130 --> 00:45:42,800
e era unha pila en que a
última persoa da cola chegou primeiro,

841
00:45:42,800 --> 00:45:44,160
a xente ían matar un ao outro.

842
00:45:44,160 --> 00:45:49,800
>> Entón FIFO, estamos todos moi familiarizado
con no mundo real aquí,

843
00:45:49,800 --> 00:45:54,930
e todo isto ten que ver coa realidade
tipo de recrear esta liña enteira

844
00:45:54,930 --> 00:45:56,900
e colas estrutura.

845
00:45:56,900 --> 00:46:02,390
Así, mentres que coa pila,
temos push pop.

846
00:46:02,390 --> 00:46:06,440
Cunha cola, temos
enfileiramento e retirar da cola.

847
00:46:06,440 --> 00:46:10,910
Entón enfileiramento significa, basicamente,
poñelas na parte de atrás,

848
00:46:10,910 --> 00:46:13,680
e medios dequeue tomar
fóra a partir da fronte.

849
00:46:13,680 --> 00:46:18,680
Polo tanto, a nosa estrutura de datos é un
pouco máis complicado.

850
00:46:18,680 --> 00:46:21,060
Temos unha segunda cousa a seguir.

851
00:46:21,060 --> 00:46:25,950
>> Así, sen a cabeza, esta
é exactamente unha pila, non?

852
00:46:25,950 --> 00:46:27,900
Esta é a mesma estrutura que unha pila.

853
00:46:27,900 --> 00:46:32,480
O único diferente agora é que
ten esa cabeza, que o que pensa

854
00:46:32,480 --> 00:46:34,272
vai seguir?

855
00:46:34,272 --> 00:46:35,510
>> Audiencia: O primeiro.

856
00:46:35,510 --> 00:46:38,685
>> COLUMNA 1: Dereito, o
primeiro que poñemos no.

857
00:46:38,685 --> 00:46:41,130
O xefe da nosa fila.

858
00:46:41,130 --> 00:46:42,240
Quen é o primeiro da fila.

859
00:46:42,240 --> 00:46:45,300

860
00:46:45,300 --> 00:46:49,420
Todo ben, entón se facemos enfileiramento.

861
00:46:49,420 --> 00:46:52,720

862
00:46:52,720 --> 00:46:55,920
Unha vez máis, con calquera de
estas estruturas de datos,

863
00:46:55,920 --> 00:46:59,760
xa que estamos lidando con un array,
necesitamos comprobar que temos espazo.

864
00:46:59,760 --> 00:47:03,290
>> Este é tipo de como me dicindo
vós, se abrir un ficheiro,

865
00:47:03,290 --> 00:47:04,760
ten que comprobar a null.

866
00:47:04,760 --> 00:47:08,330
Con calquera destas pilas
e as filas, ten que

867
00:47:08,330 --> 00:47:13,420
a ver se hai espazo porque estamos
xestionar unha matriz de tamaño fixo,

868
00:47:13,420 --> 00:47:16,030
como vemos aqui-- 0, 1 todo ata 5.

869
00:47:16,030 --> 00:47:20,690
Entón o que facer nese caso é de selección
a ver se aínda temos espazo.

870
00:47:20,690 --> 00:47:23,110
É o noso tamaño inferior a capacidade?

871
00:47:23,110 --> 00:47:28,480
>> Se é así, hai que almacena-lo en
a cola e nós actualizamos noso tamaño.

872
00:47:28,480 --> 00:47:30,250
Entón, o que pode ser a cola neste caso?

873
00:47:30,250 --> 00:47:32,360
Non está explicitamente escrita para fóra.

874
00:47:32,360 --> 00:47:33,380
Como podemos almacena-lo?

875
00:47:33,380 --> 00:47:34,928
Cal sería a cola ser?

876
00:47:34,928 --> 00:47:38,600

877
00:47:38,600 --> 00:47:40,190
>> Entón, imos camiñar por este exemplo.

878
00:47:40,190 --> 00:47:44,590
Polo tanto, esta é unha matriz de tamaño 6, non?

879
00:47:44,590 --> 00:47:49,220
E temos agora, o noso tamaño é 5.

880
00:47:49,220 --> 00:47:55,240
E cando nós poñelas, que vai
ir ao quinto índice, non?

881
00:47:55,240 --> 00:47:57,030
Así almacenar polo rabo.

882
00:47:57,030 --> 00:48:05,600
>> Outro xeito de escribir cola sería só
ser a nosa matriz no índice de tamaño, non?

883
00:48:05,600 --> 00:48:07,560
Isto é de tamaño 5.

884
00:48:07,560 --> 00:48:11,490
A seguinte cousa que vai entrar en cinco.

885
00:48:11,490 --> 00:48:12,296
Legal?

886
00:48:12,296 --> 00:48:13,290
Está ben.

887
00:48:13,290 --> 00:48:16,350
El queda un pouco máis complicado
cando comezamos a xogar coa cabeza.

888
00:48:16,350 --> 00:48:17,060
Si?

889
00:48:17,060 --> 00:48:20,090
>> Audiencia: Isto significa que nós
declararía unha matriz que

890
00:48:20,090 --> 00:48:23,880
era de cinco elementos de lonxitude e
entón nós estamos engadindo a el?

891
00:48:23,880 --> 00:48:24,730
>> COLUMNA 1: Non.

892
00:48:24,730 --> 00:48:27,560
Polo tanto, neste caso, esta é unha pila.

893
00:48:27,560 --> 00:48:31,760
Este sería declarada
como unha matriz de tamaño 6.

894
00:48:31,760 --> 00:48:37,120
E neste caso, nós
só ten un espazo á esquerda.

895
00:48:37,120 --> 00:48:42,720
>> OK, entón unha cousa é neste
caso, se a nosa cabeza está en 0,

896
00:48:42,720 --> 00:48:45,270
entón nós só pode engadir lo en tamaño.

897
00:48:45,270 --> 00:48:51,020
Pero queda un pouco máis complicado
porque, en realidade,

898
00:48:51,020 --> 00:48:52,840
Non ten unha foto
para iso, entón eu vou

899
00:48:52,840 --> 00:48:56,670
deseñar un porque non é
tan sinxelo, xa que

900
00:48:56,670 --> 00:48:59,230
comezar a se librar das cousas.

901
00:48:59,230 --> 00:49:03,920
Así, mentres que cunha pila
só ten

902
00:49:03,920 --> 00:49:08,920
preocuparse polo que o tamaño é
cando está engadindo algo sobre,

903
00:49:08,920 --> 00:49:15,710
cunha cola que tamén cómpre facer
Asegúrese de que a súa cabeza está contabilizado,

904
00:49:15,710 --> 00:49:20,760
porque unha cousa legal sobre filas
é que se non está coa súa capacidade,

905
00:49:20,760 --> 00:49:23,040
pode realmente facer iso enrole.

906
00:49:23,040 --> 00:49:28,810
>> OK, entón un coisa-- Oh,
iso é terrible giz.

907
00:49:28,810 --> 00:49:31,815
Unha cousa a considerar é o caso.

908
00:49:31,815 --> 00:49:35,514

909
00:49:35,514 --> 00:49:37,140
Nós imos só facer cinco.

910
00:49:37,140 --> 00:49:41,810
OK, entón nós estamos indo a
din que a cabeza está aquí.

911
00:49:41,810 --> 00:49:46,140
Este é 0, 1, 2, 3, 4.

912
00:49:46,140 --> 00:49:54,210
>> A cabeza está aí, e
por favor, ten cousas en si.

913
00:49:54,210 --> 00:49:58,340
E queremos engadir algo, non?

914
00:49:58,340 --> 00:50:01,170
Entón, o único que necesitamos
sabe é que a cabeza é sempre

915
00:50:01,170 --> 00:50:05,620
vai moverse deste xeito e
logo volta ao comezo volta, OK?

916
00:50:05,620 --> 00:50:10,190
>> Polo tanto, esta cola ten espazo, non?

917
00:50:10,190 --> 00:50:13,950
Ten espazo en principio,
tipo de diante deste.

918
00:50:13,950 --> 00:50:17,920
Entón o que necesitamos facer é nós
precisa para calcular a cola.

919
00:50:17,920 --> 00:50:20,530
Se sabe que o seu
cabeza non cambiou, cola

920
00:50:20,530 --> 00:50:24,630
é só a súa matriz en
o índice do tamaño.

921
00:50:24,630 --> 00:50:30,000
>> Pero, en realidade, se está a usar unha fila,
súa cabeza probablemente está a ser actualizado.

922
00:50:30,000 --> 00:50:33,890
Entón o que ten que facer é
en realidade calcular a cola.

923
00:50:33,890 --> 00:50:39,990
Entón, o que facemos é esta fórmula
aquí, que eu vou deixar

924
00:50:39,990 --> 00:50:42,680
vostedes pensan sobre e
entón imos falar sobre iso.

925
00:50:42,680 --> 00:50:49,567

926
00:50:49,567 --> 00:50:50,400
Polo tanto, esta é a capacidade.

927
00:50:50,400 --> 00:50:55,890

928
00:50:55,890 --> 00:50:59,660
>> Entón, iso vai realmente
darlle unha forma de facelo.

929
00:50:59,660 --> 00:51:03,205

930
00:51:03,205 --> 00:51:04,330
Porque neste caso, o que?

931
00:51:04,330 --> 00:51:09,205
A nosa cabeza está en 1, o noso tamaño é 4.

932
00:51:09,205 --> 00:51:11,760

933
00:51:11,760 --> 00:51:18,490
Se nós mod que por 5, obtemos 0,
que é onde debe introducir-lo.

934
00:51:18,490 --> 00:51:23,320

935
00:51:23,320 --> 00:51:26,080
>> Entón, a continuación, no caso seguinte,
se tivésemos que facelo,

936
00:51:26,080 --> 00:51:33,390
podemos dicir, OK, imos desenfileirá algo.

937
00:51:33,390 --> 00:51:34,390
Nós desenfileirá iso.

938
00:51:34,390 --> 00:51:37,740
Tomamos a este elemento, non?

939
00:51:37,740 --> 00:51:47,930
>> E agora a nosa cabeza está a apuntar aquí,
e queremos engadir noutra cousa.

940
00:51:47,930 --> 00:51:52,470
Este é basicamente o
de atrás da nosa liña, non?

941
00:51:52,470 --> 00:51:55,450
As colas poden involucrar ao redor da matriz.

942
00:51:55,450 --> 00:51:57,310
Esta é unha das principais diferenzas.

943
00:51:57,310 --> 00:51:58,780
Pilas, non pode facelo.

944
00:51:58,780 --> 00:52:01,140
>> Con colas, pode
porque todo o que importa

945
00:52:01,140 --> 00:52:03,940
é que sabe o que
engadiuse máis recentemente.

946
00:52:03,940 --> 00:52:10,650
Xa que todo vai ser engadido en
neste sentido cara á esquerda, no caso en apreciado,

947
00:52:10,650 --> 00:52:16,480
e logo enrole arredor, pode
seguir poñendo en novos elementos

948
00:52:16,480 --> 00:52:18,830
na parte de diante da matriz
porque non é realmente

949
00:52:18,830 --> 00:52:20,640
diante da matriz máis.

950
00:52:20,640 --> 00:52:26,320
Pode pensar no inicio do
matriz como na súa cabeza realmente é.

951
00:52:26,320 --> 00:52:29,710
>> Polo tanto, esta fórmula é como
calcular a súa cola.

952
00:52:29,710 --> 00:52:32,780

953
00:52:32,780 --> 00:52:35,610
Será que isto ten sentido?

954
00:52:35,610 --> 00:52:36,110
Está ben.

955
00:52:36,110 --> 00:52:39,400

956
00:52:39,400 --> 00:52:44,040
OK, dequeue, e logo
Vostedes teñen 10 minutos

957
00:52:44,040 --> 00:52:48,840
para me preguntar calquera preguntas de aclaración
quere, porque sei que é loucura.

958
00:52:48,840 --> 00:52:51,980
>> Todo ben, entón o mesmo maneira--
Non sei se vostedes notaron,

959
00:52:51,980 --> 00:52:53,450
pero CS é todo sobre patróns.

960
00:52:53,450 --> 00:52:57,370
As cousas son moi fermoso o
mesmo, só con pequenos axustes.

961
00:52:57,370 --> 00:52:58,950
Entón mesmo aquí.

962
00:52:58,950 --> 00:53:04,040
Necesitamos comprobar a ver se realmente
teñen algo na nosa cola, non?

963
00:53:04,040 --> 00:53:05,960
Dicir, OK, é o noso tamaño maior que 0?

964
00:53:05,960 --> 00:53:06,730
Legal.

965
00:53:06,730 --> 00:53:10,690
>> Se o facemos, entón nós nos movemos nosa cabeza, que
é o que eu acabo demostrado aquí.

966
00:53:10,690 --> 00:53:13,870
Nós actualizamos a nosa cabeza para ser máis un.

967
00:53:13,870 --> 00:53:18,390
E despois de que nós diminuiremos nosa
tamaño e voltar o elemento.

968
00:53:18,390 --> 00:53:21,000

969
00:53:21,000 --> 00:53:26,250
>> Hai moito máis concreto
código en study.cs50.net,

970
00:53:26,250 --> 00:53:29,440
e eu recomendo ir
por iso, se ten tempo,

971
00:53:29,440 --> 00:53:30,980
aínda que sexa só un pseudo-código.

972
00:53:30,980 --> 00:53:35,980
E se vostedes queren falar a través
que comigo un a un, por favor, me deixe

973
00:53:35,980 --> 00:53:37,500
sei.

974
00:53:37,500 --> 00:53:38,770
Eu sería feliz en.

975
00:53:38,770 --> 00:53:42,720
As estruturas de datos, se
tomar CS 124, vai

976
00:53:42,720 --> 00:53:47,830
sabemos que as estruturas de datos queda moi
diversión e este é só o comezo.

977
00:53:47,830 --> 00:53:50,350
>> Entón, sei que é difícil.

978
00:53:50,350 --> 00:53:51,300
Está certo.

979
00:53:51,300 --> 00:53:52,410
Nós loitamos.

980
00:53:52,410 --> 00:53:53,630
Eu sigo a facer.

981
00:53:53,630 --> 00:53:56,660
Entón non se preocupe moito con iso.

982
00:53:56,660 --> 00:54:02,390
>> Pero iso é basicamente o
Crash Course en estruturas de datos.

983
00:54:02,390 --> 00:54:03,400
Sei que é moito.

984
00:54:03,400 --> 00:54:06,860
Hai algo que nós
quere ir de novo?

985
00:54:06,860 --> 00:54:09,400
O que quero falar a través?

986
00:54:09,400 --> 00:54:10,060
Si?

987
00:54:10,060 --> 00:54:16,525
>> Audiencia: Para este exemplo, de xeito
a cola nova é a 0 sobre iso?

988
00:54:16,525 --> 00:54:17,150
COLUMNA 1: Si.

989
00:54:17,150 --> 00:54:18,230
Audiencia: Aceptar.

990
00:54:18,230 --> 00:54:24,220
Entón pasando,
que tería un máis 4 ou-

991
00:54:24,220 --> 00:54:27,671
>> COLUMNA 1: Entón estaba dicindo,
cando queremos ir facelo de novo?

992
00:54:27,671 --> 00:54:28,296
Audiencia: Yeah.

993
00:54:28,296 --> 00:54:38,290
Entón, se estaba imaxinando out-- onde están
calcular a cola da niso?

994
00:54:38,290 --> 00:54:44,260
>> COLUMNA 1: Entón a cola
foi em-- eu mudei iso.

995
00:54:44,260 --> 00:54:52,010
Así, neste exemplo aquí, esta foi
a matriz que estamos mirando, OK?

996
00:54:52,010 --> 00:54:54,670
Polo tanto, temos cousas en 1, 2, 3 e 4.

997
00:54:54,670 --> 00:55:05,850
Polo tanto, temos a nosa cabeza é igual a 1 no
Neste punto, o tamaño e a é igual a 4

998
00:55:05,850 --> 00:55:07,050
neste punto, non?

999
00:55:07,050 --> 00:55:08,960
>> Vós todos están de acordo que é o caso?

1000
00:55:08,960 --> 00:55:14,620
Entón nós facemos a cabeza máis o tamaño, o que
dános 5, e entón nós mod por 5.

1001
00:55:14,620 --> 00:55:20,690
Recibimos 0, o que nos di que 0 é
onde está a nosa cola, onde temos espazo.

1002
00:55:20,690 --> 00:55:22,010
>> Audiencia: ¿Que é un cap?

1003
00:55:22,010 --> 00:55:23,520
>> COLUMNA 1: A capacidade.

1004
00:55:23,520 --> 00:55:24,020
Sentímolo.

1005
00:55:24,020 --> 00:55:29,640
Entón ese é o tamaño da súa matriz.

1006
00:55:29,640 --> 00:55:35,210

1007
00:55:35,210 --> 00:55:36,047
Si?

1008
00:55:36,047 --> 00:55:39,210
>> Audiencia: [inaudível] antes
devolvemos o elemento?

1009
00:55:39,210 --> 00:55:46,270
>> COLUMNA 1: Entón, pasamos a
ir ou volver do momento?

1010
00:55:46,270 --> 00:55:52,680
Entón, se nós nos movemos un, diminuír o tamaño?

1011
00:55:52,680 --> 00:55:54,150
Aguante.

1012
00:55:54,150 --> 00:55:55,770
Eu definitivamente esqueceu o outro.

1013
00:55:55,770 --> 00:56:00,646

1014
00:56:00,646 --> 00:56:01,990
Non importa.

1015
00:56:01,990 --> 00:56:04,980
Non hai outra fórmula.

1016
00:56:04,980 --> 00:56:09,980
Si, desexa volver
a cabeza e, a continuación, movelo de volta.

1017
00:56:09,980 --> 00:56:13,270
>> Audiencia: OK, porque neste
punto, a cabeza estaba en 0,

1018
00:56:13,270 --> 00:56:18,452
e despois quere regresar
índice 0 e, a continuación, facer a cabeza 1?

1019
00:56:18,452 --> 00:56:19,870
>> COLUMNA 1: Certo.

1020
00:56:19,870 --> 00:56:22,820
Eu creo que hai outro
tipo fórmula de como esta.

1021
00:56:22,820 --> 00:56:26,970
Non teño iso na parte superior da miña cabeza como
Non quero darlle a persoa errada.

1022
00:56:26,970 --> 00:56:35,470
Pero eu creo que é perfectamente válida para
digamos, OK, garde esta element-- o que quere

1023
00:56:35,470 --> 00:56:40,759
elemento de cabeza é-- diminuír a súa
tamaño, mover a cabeza máis, e retorno

1024
00:56:40,759 --> 00:56:41,800
o que quere que ese elemento é.

1025
00:56:41,800 --> 00:56:44,760
Isto é perfectamente válido.

1026
00:56:44,760 --> 00:56:45,260
Está ben.

1027
00:56:45,260 --> 00:56:48,360

1028
00:56:48,360 --> 00:56:53,560
Eu sinto que iso non é
como o most-- non está

1029
00:56:53,560 --> 00:56:55,740
vai saír de aquí
como, si, sei intentos.

1030
00:56:55,740 --> 00:56:56,880
Teño todo.

1031
00:56:56,880 --> 00:56:57,670
Isto está ok.

1032
00:56:57,670 --> 00:57:00,200
Eu prometer.

1033
00:57:00,200 --> 00:57:05,240
Pero estruturas de datos que son algo
hai que moito tempo para se acostumar.

1034
00:57:05,240 --> 00:57:10,010
Probablemente unha das máis difíciles
cousas, eu creo que, no curso.

1035
00:57:10,010 --> 00:57:15,330
>> Por iso, en definitiva leva
repetición e mirando at-- I

1036
00:57:15,330 --> 00:57:20,050
realmente non sei listas ligadas
ata que eu fixen máis con eles,

1037
00:57:20,050 --> 00:57:22,550
do mesmo xeito que eu non fixen
realmente entender punteiros

1038
00:57:22,550 --> 00:57:27,040
ata que eu tiven que ensino-lo para dous
anos e fago os meus propios Serie de exercicios con el.

1039
00:57:27,040 --> 00:57:28,990
Ten unha morea de reiteración e do tempo.

1040
00:57:28,990 --> 00:57:32,600
E, finalmente, que vai tipo de clic.

1041
00:57:32,600 --> 00:57:36,320
>> Pero, mentres tanto, se ten o tipo
dun elevado nivel de comprensión que

1042
00:57:36,320 --> 00:57:39,321
estes fan, os seus pros
e que é o que cons--

1043
00:57:39,321 --> 00:57:41,820
nós realmente tenden a enfatizar,
especialmente no curso de introdución.

1044
00:57:41,820 --> 00:57:45,511
Como, por que usaría
un intento a través dunha matriz?

1045
00:57:45,511 --> 00:57:48,010
Como, cales son os aspectos positivos
e negativos de cada un deles?

1046
00:57:48,010 --> 00:57:51,610
>> E entender os trade-offs
entre cada unha destas estruturas

1047
00:57:51,610 --> 00:57:54,910
é o que é moito máis importante agora.

1048
00:57:54,910 --> 00:57:58,140
Non pode ser un tolo
ou dúas preguntas que se

1049
00:57:58,140 --> 00:58:03,710
vai pedirlle para aplicar impulso ou
aplicar pop ou enfileiramento e retirar da cola.

1050
00:58:03,710 --> 00:58:07,340
Pero, na maior parte, tendo esta
maior nivel de comprensión e máis

1051
00:58:07,340 --> 00:58:09,710
dunha comprensión intuitiva é
máis importante que realmente

1052
00:58:09,710 --> 00:58:11,250
poder implementar lo.

1053
00:58:11,250 --> 00:58:14,880
>> Sería realmente marabilloso se todos vostedes
podía saír e ir aplicar un intento,

1054
00:58:14,880 --> 00:58:19,720
pero entendemos que non é necesariamente
o máis razoable agora.

1055
00:58:19,720 --> 00:58:23,370
Pero pode no seu pset, se quere
para, a continuación, vai comezar a práctica,

1056
00:58:23,370 --> 00:58:27,200
e logo, quizais
realmente entende-la.

1057
00:58:27,200 --> 00:58:27,940
Si?

1058
00:58:27,940 --> 00:58:30,440
>> Audiencia: OK, entón cales son
que pretendía usar no pset?

1059
00:58:30,440 --> 00:58:31,916
Necesito usar un deles?

1060
00:58:31,916 --> 00:58:32,540
COLUMNA 1: Si.

1061
00:58:32,540 --> 00:58:34,199
Entón tes a súa elección.

1062
00:58:34,199 --> 00:58:36,740
Creo que, neste caso, podemos
falar do pset algo

1063
00:58:36,740 --> 00:58:40,480
porque eu execute a través destes.

1064
00:58:40,480 --> 00:58:47,779
Así, no seu pset, ten o seu
elección de intentos ou táboas de hash.

1065
00:58:47,779 --> 00:58:49,570
Algunhas persoas van tentar
e utilizar filtros de Bloom,

1066
00:58:49,570 --> 00:58:51,840
pero os que tecnicamente non son correctos.

1067
00:58:51,840 --> 00:58:55,804
Debido á súa natureza probabilística,
eles dan falsos positivos, ás veces.

1068
00:58:55,804 --> 00:58:57,095
San ollar frío en, con todo.

1069
00:58:57,095 --> 00:58:59,030
Recomendo ollar
para eles, polo menos.

1070
00:58:59,030 --> 00:59:03,260
Pero ten a súa elección
entre unha táboa hash e un intento.

1071
00:59:03,260 --> 00:59:06,660
E iso vai ser onde
leva no seu dicionario.

1072
00:59:06,660 --> 00:59:09,230
>> E terá que escoller
súa función de hash,

1073
00:59:09,230 --> 00:59:13,420
ten que escoller cantos
baldes ten, e vai variar.

1074
00:59:13,420 --> 00:59:17,440
Como se ten máis baldes,
quizais el vai executar máis rápido.

1075
00:59:17,440 --> 00:59:22,790
Pero quizais está perdendo un
moito espazo dese xeito, con todo.

1076
00:59:22,790 --> 00:59:26,320
Ten que descubrir iso.

1077
00:59:26,320 --> 00:59:27,140
Mmhmm?

1078
00:59:27,140 --> 00:59:29,875
>> Audiencia: Vostede dixo antes que
podemos utilizar outras funcións de hash,

1079
00:59:29,875 --> 00:59:31,750
que non temos a
crear unha función hash?

1080
00:59:31,750 --> 00:59:32,666
>> COLUMNA 1: Si, certo.

1081
00:59:32,666 --> 00:59:38,150
Entón, literalmente, para a súa función de hash,
como Google "función hash"

1082
00:59:38,150 --> 00:59:40,770
e ollar para algúns dos máis interesantes.

1083
00:59:40,770 --> 00:59:43,250
Non está prevista a construción
súas propias funcións de hash.

1084
00:59:43,250 --> 00:59:46,100
As persoas gastan o seu
teses sobre estas cousas.

1085
00:59:46,100 --> 00:59:50,250
>> Entón non se preocupe sobre a construción do seu propio país.

1086
00:59:50,250 --> 00:59:53,350
Buscar unha liña para comezar.

1087
00:59:53,350 --> 00:59:56,120
Algúns deles ten que
manipular algo

1088
00:59:56,120 --> 00:59:59,430
para garantir que tipo de retorno igualar-se
e outros enfeites, así, en principio,

1089
00:59:59,430 --> 01:00:02,420
Eu recomenda usar algo
realmente fácil que quizais só

1090
01:00:02,420 --> 01:00:04,680
hashes na primeira letra.

1091
01:00:04,680 --> 01:00:08,760
E, a continuación, xa que ten que traballar,
incorporando unha función hash máis frío.

1092
01:00:08,760 --> 01:00:09,260
Mmhmm?

1093
01:00:09,260 --> 01:00:13,020
>> Audiencia: Será que un intente ser ou
eficiente, pero só máis difícil, como--

1094
01:00:13,020 --> 01:00:15,880
>> COLUMNA 1: Entón unha oportunidade, eu creo,
é intuitivamente difícil de aplicar

1095
01:00:15,880 --> 01:00:18,310
pero é moi rápido.

1096
01:00:18,310 --> 01:00:20,620
Con todo, ocupa máis espazo.

1097
01:00:20,620 --> 01:00:25,270
De novo, pode optimizar tanto dos que están no
diferentes xeitos e hai formas a--

1098
01:00:25,270 --> 01:00:26,770
Audiencia: Como estamos clasificados sobre iso?

1099
01:00:26,770 --> 01:00:27,540
Será que matter--

1100
01:00:27,540 --> 01:00:29,164
>> COLUMNA 1: Entón está clasificado como normal.

1101
01:00:29,164 --> 01:00:31,330
Vai ser graduada en deseño.

1102
01:00:31,330 --> 01:00:36,020
Independentemente da forma como fai, quere
que seguro que é tan elegante como pode ser

1103
01:00:36,020 --> 01:00:38,610
e tan eficiente canto posible.

1104
01:00:38,610 --> 01:00:41,950
Pero se escolle un intento ou de hash
mesa, con tal de que funciona,

1105
01:00:41,950 --> 01:00:45,350
estamos felices con iso.

1106
01:00:45,350 --> 01:00:48,370
E se usa algo que hashes
na primeira letra, iso é bo,

1107
01:00:48,370 --> 01:00:51,410
como é posible que como deseño-wise.

1108
01:00:51,410 --> 01:00:53,410
Tamén estamos acadando o
punto neste semester--

1109
01:00:53,410 --> 01:00:55,340
Non sei se
caras noticed-- se está

1110
01:00:55,340 --> 01:00:58,780
graos PSet diminuír un pouco
debido ao deseño e outros enfeites,

1111
01:00:58,780 --> 01:00:59,900
iso é perfectamente normal.

1112
01:00:59,900 --> 01:01:02,960
Está quedando a un punto onde a súa
programas están ficando cada vez máis complicado.

1113
01:01:02,960 --> 01:01:04,830
Hai máis lugares
pode mellorar.

1114
01:01:04,830 --> 01:01:06,370
>> Por iso é perfectamente normal.

1115
01:01:06,370 --> 01:01:08,810
Non é que está
facendo peor no seu pset.

1116
01:01:08,810 --> 01:01:11,885
É só que estamos sendo máis difícil para vostede agora.

1117
01:01:11,885 --> 01:01:13,732
Entón, todo o mundo está sentindo isto.

1118
01:01:13,732 --> 01:01:14,940
Eu só graduada todos os seus Serie de exercicios.

1119
01:01:14,940 --> 01:01:16,490
Sei que todo o mundo está sentindo isto.

1120
01:01:16,490 --> 01:01:19,600
>> Polo tanto, non se preocupe con iso.

1121
01:01:19,600 --> 01:01:23,580
E se ten calquera dúbida
Serie de exercicios anteriores ou formas que pode mellorar,

1122
01:01:23,580 --> 01:01:27,760
Intento e comentar o específico
lugares, pero ás veces é tarde

1123
01:01:27,760 --> 01:01:30,840
e eu fico canso.

1124
01:01:30,840 --> 01:01:34,885
Existen outras cousas
sobre estruturas de datos?

1125
01:01:34,885 --> 01:01:37,510
Estou seguro de que vostedes realmente non
quero falar máis deles,

1126
01:01:37,510 --> 01:01:42,650
pero se hai, eu estou feliz de
pasar por riba deles, así como calquera cousa

1127
01:01:42,650 --> 01:01:45,580
de charla pasado
semana ou a semana pasada.

1128
01:01:45,580 --> 01:01:51,580
>> Sei que a semana pasada foi toda a revisión, de xeito
podemos ter pulado algunha revisión

1129
01:01:51,580 --> 01:01:54,190
da charla.

1130
01:01:54,190 --> 01:01:58,230
Todas as outras preguntas podo responder?

1131
01:01:58,230 --> 01:01:59,350
OK, todo ben.

1132
01:01:59,350 --> 01:02:02,400
Ben, vostedes saír 15 minutos máis cedo.

1133
01:02:02,400 --> 01:02:08,370
>> Esperamos que este era semi-útil, polo menos,
e eu vou ver vostedes a próxima semana,

1134
01:02:08,370 --> 01:02:12,150
ou o horario de expediente xoves.

1135
01:02:12,150 --> 01:02:15,285
Hai peticións de merendas
á seguinte semana, que é a cousa?

1136
01:02:15,285 --> 01:02:17,459
Porque eu esquezo de doces hoxe.

1137
01:02:17,459 --> 01:02:19,750
E eu trouxo doces última
semana, pero era día de Colón,

1138
01:02:19,750 --> 01:02:25,400
non eran como seis persoas que
tiña catro bolsas de doces para ti.

1139
01:02:25,400 --> 01:02:28,820
Podo traer Starbursts
novo se queres.

1140
01:02:28,820 --> 01:02:29,580
Starbursts?

1141
01:02:29,580 --> 01:02:32,250
OK, parece bo.

1142
01:02:32,250 --> 01:02:35,050
Ten un gran día, persoal.

1143
01:02:35,050 --> 01:02:39,510