1
00:00:00,000 --> 00:00:11,460

2
00:00:11,460 --> 00:00:12,250
>> DAVID Malan: Todo ben.

3
00:00:12,250 --> 00:00:13,860
Benvido de volta ao CS50.

4
00:00:13,860 --> 00:00:16,190
Este é o inicio da semana 8.

5
00:00:16,190 --> 00:00:21,320
E lembrar que problema set rematou 5
cun pouco de un reto.

6
00:00:21,320 --> 00:00:25,210
Así, supoñendo que recuperou todo o seu
Compañeiros de ensino e fotografías da CA

7
00:00:25,210 --> 00:00:30,480
no ficheiro card.raw, vostede é elegível
agora atopar todas esas persoas, e

8
00:00:30,480 --> 00:00:34,510
un afortunado gañador vai a pé a casa cun
destas cousas, o movemento salto

9
00:00:34,510 --> 00:00:37,450
dispositivo que pode usar para a final
proxectos, por exemplo.

10
00:00:37,450 --> 00:00:39,860
>> Este, cada ano, leva a
un pouco de bizarrice.

11
00:00:39,860 --> 00:00:43,480
E así que eu penso que eu ía facer é compartir
contigo algunhas das notas que teñen

12
00:00:43,480 --> 00:00:47,370
ir para atrás e cara adiante sobre
a lista de funcionarios da tarde.

13
00:00:47,370 --> 00:00:51,110
Por exemplo, onte á noite, citas
unquote, a partir dun dos funcionarios

14
00:00:51,110 --> 00:00:55,000
membros ", eu só tiña unha batida estudante
na miña porta para sacar unha foto comigo.

15
00:00:55,000 --> 00:00:59,020
Stalkers, eu lle digo. "Empezou
moi descriptivo e despois nos mudamos

16
00:00:59,020 --> 00:01:02,830
para, unha hora máis tarde, "Eu tiven un
estudante esperando por min despois da sección

17
00:01:02,830 --> 00:01:06,080
e tiña todos os nosos nomes e fotos
nalgunhas follas de papel. "Todo ben.

18
00:01:06,080 --> 00:01:09,230
Así organizado, pero non
todo o que asustado aínda.

19
00:01:09,230 --> 00:01:12,520
>> Entón, "Eu estaba fóra da cidade neste fin de semana,
e cando volvín, había un en

20
00:01:12,520 --> 00:01:12,630
meu

21
00:01:12,630 --> 00:01:16,740
cuarto. "[risas]

22
00:01:16,740 --> 00:01:20,410
DAVID Malan: Next cita dun equipo
membro ", dixo un alumno chegou á miña casa en

23
00:01:20,410 --> 00:01:25,330
Somerville ás 4 da mañá, esta mañá. "Next
persoal, "Eu cheguei ao meu hotel en San

24
00:01:25,330 --> 00:01:30,016
Francisco e un alumno estaba esperando por
me no hall de entrada con tres DSLRs. "

25
00:01:30,016 --> 00:01:31,510
Tipo de cámara.

26
00:01:31,510 --> 00:01:34,980
"Eu non estou nin no equipo neste semestre,
pero un estudante invadiu a miña casa esta

27
00:01:34,980 --> 00:01:40,480
mañá e rexistrou a cousa toda
con vidro de Google. "E entón, finalmente,

28
00:01:40,480 --> 00:01:43,650
"Polo menos 12 persoas foron avidamente
agardando para min cando eu saín do meu

29
00:01:43,650 --> 00:01:44,800
limo, e entón eu

30
00:01:44,800 --> 00:01:46,970
espertei. "Todo ben.

31
00:01:46,970 --> 00:01:57,690
Así, entre as fotografías, como pode
lembrar, son este home aquí, que

32
00:01:57,690 --> 00:02:01,850
pode saber como Milo bananas, que vive
con Lauren Carballo, a nosa cabeza

33
00:02:01,850 --> 00:02:02,905
ensino Fellow.

34
00:02:02,905 --> 00:02:05,170
Milo, Milo, ven acá neno.

35
00:02:05,170 --> 00:02:06,320
Milo.

36
00:02:06,320 --> 00:02:08,650
Milo.

37
00:02:08,650 --> 00:02:12,230
Lembre, está a usar Google de vidro, de xeito
imos amosar todo isto despois.

38
00:02:12,230 --> 00:02:16,190
Polo tanto, esta é Milo se desexa
tirar unha foto con el despois.

39
00:02:16,190 --> 00:02:18,240
Se desexa ollar para fóra
para o público alí.

40
00:02:18,240 --> 00:02:19,430
Aceptar.

41
00:02:19,430 --> 00:02:20,200
Isto é bo filmación.

42
00:02:20,200 --> 00:02:22,556
Ben, Milo bananas.

43
00:02:22,556 --> 00:02:23,941
Oh, non fagas iso.

44
00:02:23,941 --> 00:02:29,020
>> [Risas]

45
00:02:29,020 --> 00:02:29,470
>> Aceptar.

46
00:02:29,470 --> 00:02:34,550
Así, unha palabra, a continuación, sobre o que está por vir,
porque cando comezamos a transición,

47
00:02:34,550 --> 00:02:38,410
esta semana en concreto, a partir de C, nunha
ámbito de liña de comandos para PHP e

48
00:02:38,410 --> 00:02:42,720
Javascript e SQL e HTML e CSS en
un ambiente baseado na web, estaremos

49
00:02:42,720 --> 00:02:44,490
equipando o con toda
máis coñecemento para

50
00:02:44,490 --> 00:02:46,010
potenciais proxectos finais.

51
00:02:46,010 --> 00:02:49,240
Para iso, o curso ten unha
tradición de realización de seminarios que

52
00:02:49,240 --> 00:02:50,950
son sobre temas tanxenciais
ao curso.

53
00:02:50,950 --> 00:02:54,330
Moi relacionado coa programación e
desenvolvemento de aplicacións e así por diante, pero

54
00:02:54,330 --> 00:02:57,010
non necesariamente por explotado
propio plan de estudos da carreira.

55
00:02:57,010 --> 00:03:00,250
>> Entón, se podería estar interesado en un
ou máis de seminarios deste ano,

56
00:03:00,250 --> 00:03:02,530
rexistrar en cs50.net/seminar.

57
00:03:02,530 --> 00:03:06,170
Existen seminarios anciás
en cs50.net/seminars.

58
00:03:06,170 --> 00:03:10,620
E o conxunto, ata agora, para este ano
son sorprendentes aplicacións web con Ruby on

59
00:03:10,620 --> 00:03:13,580
Coches, que é unha alternativa
linguaxe para PHP.

60
00:03:13,580 --> 00:03:14,900
Lingüística computacional.

61
00:03:14,900 --> 00:03:18,710
Introdución á iOS, que é o
plataforma que se usa para o iPhone e

62
00:03:18,710 --> 00:03:19,850
desenvolvemento iPad.

63
00:03:19,850 --> 00:03:22,890
JavaScript para Web Apps, imos cubrir
iso, pero neste seminario, vai

64
00:03:22,890 --> 00:03:24,070
en máis detalle.

65
00:03:24,070 --> 00:03:27,390
>> Leap Movemento, entón imos realmente ter algún
dos nosos amigos da Leap Movemento,

66
00:03:27,390 --> 00:03:29,160
da propia empresa, unirse a nós.

67
00:03:29,160 --> 00:03:31,800
Mañá, en realidade, para facilitar
un hands-on seminario, se

68
00:03:31,800 --> 00:03:33,320
do seu interese.

69
00:03:33,320 --> 00:03:38,770
Meteor.js, unha técnica alternativa para
mediante JavaScript e non nun navegador,

70
00:03:38,770 --> 00:03:39,970
mais nun servidor.

71
00:03:39,970 --> 00:03:42,110
Node.js., que é moi
nesa vea ben.

72
00:03:42,110 --> 00:03:43,650
Deseño elegante Android.

73
00:03:43,650 --> 00:03:46,990
Android ser unha alternativa moi popular
para iOS e Windows Phone

74
00:03:46,990 --> 00:03:48,790
e outras plataformas móbiles.

75
00:03:48,790 --> 00:03:51,180
Correo web Active defensiva Seguridade.

76
00:03:51,180 --> 00:03:54,590
>> Entón, en realidade, se quere
involucrarse en iso, déixeme

77
00:03:54,590 --> 00:03:55,840
anota isto.

78
00:03:55,840 --> 00:03:57,790
Estamos moi felices en dicir que
nosos amigos en Salto

79
00:03:57,790 --> 00:03:59,140
De movemento, que é unha inicialización -

80
00:03:59,140 --> 00:04:01,300
este dispositivo realmente acabou
fóra hai uns meses -

81
00:04:01,300 --> 00:04:05,960
graciosamente doaron 30 dispositivos
para a clase de como moitos alumnos, se

82
00:04:05,960 --> 00:04:08,670
quere pedir o hardware
cara ao final do semestre, e usalo para

83
00:04:08,670 --> 00:04:10,390
un proxecto real final.

84
00:04:10,390 --> 00:04:11,890
Eles soportan varios idiomas.

85
00:04:11,890 --> 00:04:16,040
Ningún deles C, ningún deles PHP, así
entender un ou máis destes seminarios

86
00:04:16,040 --> 00:04:16,899
pode revelar-se de interese.

87
00:04:16,899 --> 00:04:19,730
E todos eles van ser filmado en
caso en que non é capaz

88
00:04:19,730 --> 00:04:21,380
para comparecer en persoa.

89
00:04:21,380 --> 00:04:25,000
A programación será anunciada vía
enviar correo-e como se solidificar cuartos.

90
00:04:25,000 --> 00:04:28,460
>> E, por último, se vai a
projects.cs.50.net, este é un sitio

91
00:04:28,460 --> 00:04:31,450
temos cada ano que invitados
persoas da comunidade, profesores,

92
00:04:31,450 --> 00:04:36,420
departamentos, funcionarios e dous
nun lado de fóra de CS50 para

93
00:04:36,420 --> 00:04:37,730
propoñer ideas para proxectos.

94
00:04:37,730 --> 00:04:39,050
Cousas de interese para grupos de estudantes.

95
00:04:39,050 --> 00:04:40,600
Cousas de interese para os departamentos.

96
00:04:40,600 --> 00:04:43,990
Entón non virar alí, se está loitando
coa incerteza en canto ao que

97
00:04:43,990 --> 00:04:46,700
se quere afrontar.

98
00:04:46,700 --> 00:04:51,760
>> Entón última vez que introduciu unha indiscutibelmente
estrutura de datos máis complexa do que tiñamos

99
00:04:51,760 --> 00:04:53,300
ver nas últimas semanas.

100
00:04:53,300 --> 00:04:56,550
Estabamos a usar matrices moi
feliz como un útil se

101
00:04:56,550 --> 00:04:58,160
estrutura de datos simplista.

102
00:04:58,160 --> 00:05:00,570
Entón, nós introducimos estes, que
por suposto están ligados listas.

103
00:05:00,570 --> 00:05:05,470
E o que foi unha das motivacións para
introducindo esta estrutura de datos?

104
00:05:05,470 --> 00:05:06,930
Si?

105
00:05:06,930 --> 00:05:07,250
¿Que é iso?

106
00:05:07,250 --> 00:05:08,080
>> Audiencia: tamaño dinámico.

107
00:05:08,080 --> 00:05:09,040
>> DAVID Malan: tamaño dinámico.

108
00:05:09,040 --> 00:05:11,890
Así, mentres en orde, ten que
coñecer con antelación o seu tamaño cando

109
00:05:11,890 --> 00:05:12,740
vostede reservar-lo.

110
00:05:12,740 --> 00:05:14,380
Na lista ligada, non
ten que saber iso.

111
00:05:14,380 --> 00:05:17,610
Pode só malloc, ou, máis xeralmente,
asignar un adicional

112
00:05:17,610 --> 00:05:20,720
no, por así dicir, en calquera momento
pretende introducir máis datos.

113
00:05:20,720 --> 00:05:22,670
O nodo ten ningún significado pre-determinado.

114
00:05:22,670 --> 00:05:25,580
É só un termo xenérico que describe
algún tipo de recipiente que estamos

115
00:05:25,580 --> 00:05:29,610
usar na nosa estrutura de datos para almacenar
algún elemento de interese, que neste

116
00:05:29,610 --> 00:05:31,750
caso ocorrer de ser enteiros.

117
00:05:31,750 --> 00:05:33,160
>> Pero sempre hai un intercambio.

118
00:05:33,160 --> 00:05:38,070
Entón, temos tamaños dinámica dos datos
estrutura, pero o prezo que imos pagar?

119
00:05:38,070 --> 00:05:40,040
Cal é a desvantaxe de listas ligadas?

120
00:05:40,040 --> 00:05:41,006
Si?

121
00:05:41,006 --> 00:05:41,980
>> Audiencia: Require máis memoria.

122
00:05:41,980 --> 00:05:44,240
>> DAVID Malan: Esixe máis
memoria, como exactamente?

123
00:05:44,240 --> 00:05:46,440
>> Audiencia: [inaudível].

124
00:05:46,440 --> 00:05:47,050
>> DAVID Malan: Exactamente.

125
00:05:47,050 --> 00:05:50,460
Entón, agora temos punteiros ocupando
memoria adicional que anteriormente

126
00:05:50,460 --> 00:05:53,040
non precisa, xa que a vantaxe
dunha matriz, por suposto, é que

127
00:05:53,040 --> 00:05:54,860
todo é contiguo, de volta
de volta cara atrás, o que

128
00:05:54,860 --> 00:05:56,380
dálle acceso aleatorio.

129
00:05:56,380 --> 00:06:00,710
Porque só usando corchete
notación, ou máis técnicamente punteiro

130
00:06:00,710 --> 00:06:03,580
aritmética, adición moi sinxelo,
pode acceder a calquera

131
00:06:03,580 --> 00:06:05,700
elementos en tempo constante.

132
00:06:05,700 --> 00:06:08,975
E, de feito, este é o tipo de insinuando
outro prezo que estamos pagando cun

133
00:06:08,975 --> 00:06:09,760
lista ligada.

134
00:06:09,760 --> 00:06:13,890
>> Que pasa co tempo de execución
algo así como Search, se eu queira

135
00:06:13,890 --> 00:06:17,270
atopar algún valor e no interior
dunha lista ligada?

136
00:06:17,270 --> 00:06:20,290
O que o meu tempo de execución se fixo?

137
00:06:20,290 --> 00:06:21,560
Big O de n.

138
00:06:21,560 --> 00:06:24,060
De ser clasificada para?

139
00:06:24,060 --> 00:06:25,440
E se a estrutura de datos é clasificado?

140
00:06:25,440 --> 00:06:28,640
Eu podo facer mellor que un gran
O de n para a investigación?

141
00:06:28,640 --> 00:06:31,700
Non, porque no peor dos casos pode
moi ben ser clasificado, pero o número

142
00:06:31,700 --> 00:06:32,950
está a buscar pode ser grande.

143
00:06:32,950 --> 00:06:35,370
Pode ser o número 100, o cal
pode ocorrer de ser todo

144
00:06:35,370 --> 00:06:36,410
o camiño ao final.

145
00:06:36,410 --> 00:06:39,950
E por que só se pode acceder a un linked
lista nesta implementación por

146
00:06:39,950 --> 00:06:42,690
camiño de seu primeiro nodo, está
Aínda medio fóra de sorte.

147
00:06:42,690 --> 00:06:47,450
Ten que atravesar a cousa toda
do primeiro ao último, a fin de atopar

148
00:06:47,450 --> 00:06:49,150
que gran valor como 100.

149
00:06:49,150 --> 00:06:51,350
Ou para determinar se é
nin mesmo alí.

150
00:06:51,350 --> 00:06:55,960
>> Polo tanto, non podemos facer o algoritmo nun conxunto de datos
estrutura que se parece con isto?

151
00:06:55,960 --> 00:06:59,460
Non podemos facer busca binária, porque
busca binaria necesario que tiñamos

152
00:06:59,460 --> 00:07:00,740
de acceso aleatorio.

153
00:07:00,740 --> 00:07:04,500
Poderíamos simplemente ir de local para
lugar, sen ter que seguir

154
00:07:04,500 --> 00:07:07,080
estas migas de pan en forma
todas estas indicacións.

155
00:07:07,080 --> 00:07:08,300
>> Agora, como é que imos aplicar iso?

156
00:07:08,300 --> 00:07:12,830
Ben, se somos a pantalla aquí, se
podemos reimplementar rapidamente estes datos

157
00:07:12,830 --> 00:07:13,440
estrutura -

158
00:07:13,440 --> 00:07:15,670
miña carta non é todo o que
gran aquí, pero imos tratar.

159
00:07:15,670 --> 00:07:22,030
Typedef struct Entón, eo que eu fixen
quero chamar esa cousa aquí enriba?

160
00:07:22,030 --> 00:07:22,960
Node.

161
00:07:22,960 --> 00:07:24,580
Entón, eu vou ser un bo comezo.

162
00:07:24,580 --> 00:07:27,860
E agora, o que ten que estar dentro
a estrutura de datos para que, illadamente

163
00:07:27,860 --> 00:07:28,430
lista ligada?

164
00:07:28,430 --> 00:07:29,950
Cantos campos?

165
00:07:29,950 --> 00:07:30,450
>> Así, dous.

166
00:07:30,450 --> 00:07:31,570
Un deles é moi sinxelo.

167
00:07:31,570 --> 00:07:33,050
Entón, int n.

168
00:07:33,050 --> 00:07:35,930
E poderiamos chamar n todo o que queremos,
pero debe ser un int se estamos

169
00:07:35,930 --> 00:07:37,660
implementación dunha lista encadeada para ints.

170
00:07:37,660 --> 00:07:41,920
E agora que é o que a segunda
campo ten que ser?

171
00:07:41,920 --> 00:07:43,460
Struct node *.

172
00:07:43,460 --> 00:07:50,570
Entón, se eu fai struct node *, e entón eu
pode chamar iso tamén o que eu queira,

173
00:07:50,570 --> 00:07:53,510
pero só para quedar claro que vou chamar
lo xunto, como temos benvida a facer.

174
00:07:53,510 --> 00:07:55,270
E entón eu vou pechar meus chaves.

175
00:07:55,270 --> 00:08:00,700
>> E agora, como a última vez,
Engada nó aquí.

176
00:08:00,700 --> 00:08:03,830
Pero se eu estou declarando que é como un
no, por que eu me incomodo de ser tan

177
00:08:03,830 --> 00:08:07,320
detallado aquí na declaración struct
* Nodo seguinte, en oposición

178
00:08:07,320 --> 00:08:09,210
só nodo * next?

179
00:08:09,210 --> 00:08:09,904
Si?

180
00:08:09,904 --> 00:08:12,810
>> Audiencia: [inaudível].

181
00:08:12,810 --> 00:08:14,050
>> DAVID Malan: Exactamente.

182
00:08:14,050 --> 00:08:14,530
Exactamente.

183
00:08:14,530 --> 00:08:18,320
Por C realmente leva literalmente e
ve só a definición de nodo

184
00:08:18,320 --> 00:08:21,230
ata aquí, non pode
consultalo-lo aquí.

185
00:08:21,230 --> 00:08:24,760
Entón temos este tipo de preferencia
declaración aquí, que é recoñecidamente

186
00:08:24,760 --> 00:08:25,390
máis detallado.

187
00:08:25,390 --> 00:08:27,810
Struct nodo, o que significa
agora podemos acceder a ela

188
00:08:27,810 --> 00:08:29,760
no interior da estrutura de datos.

189
00:08:29,760 --> 00:08:33,370
>> E, como unha banda, porque iso é
tornándose un pouco máis subjetiva, agora,

190
00:08:33,370 --> 00:08:36,230
a estrela tecnicamente pode ir aquí,
pode ir aquí, pode

191
00:08:36,230 --> 00:08:37,179
incluso ir no medio.

192
00:08:37,179 --> 00:08:39,890
Adoptado, na guía de estilo para
o curso, o acordo de poñer

193
00:08:39,890 --> 00:08:42,299
a estrela ao lado dos datos
tipo, que, neste caso,

194
00:08:42,299 --> 00:08:43,460
sería no struct.

195
00:08:43,460 --> 00:08:46,620
Pero entender en unha morea de libros e
referencias en liña, pode de feito

196
00:08:46,620 --> 00:08:48,450
vela do outro lado.

197
00:08:48,450 --> 00:08:52,200
Pero só entender que ambos realmente
traballar e ten que simplemente ser

198
00:08:52,200 --> 00:08:52,970
consistente.

199
00:08:52,970 --> 00:08:53,580
>> Todo ben.

200
00:08:53,580 --> 00:08:55,630
Entón esa foi a nosa declaración
de nó struct.

201
00:08:55,630 --> 00:08:59,430
Pero, entón, comezan a facer máis
cousas sofisticadas.

202
00:08:59,430 --> 00:09:03,410
Por exemplo, decidimos introducir
algo así como unha táboa hash.

203
00:09:03,410 --> 00:09:08,160
Entón, aquí está unha táboa hash de tamaño n,
indexados a partir de 0 na esquina superior esquerda para n

204
00:09:08,160 --> 00:09:09,690
menos un na parte inferior esquerda.

205
00:09:09,690 --> 00:09:11,640
Este podería ser un hash
mesa para nada.

206
00:09:11,640 --> 00:09:15,340
Pero que tipo de cousas que falamos
sobre o uso dunha táboa hash para?

207
00:09:15,340 --> 00:09:18,370
Gardar o que?

208
00:09:18,370 --> 00:09:18,800
>> Nomes.

209
00:09:18,800 --> 00:09:20,870
Poderiamos facer nomes como
fixemos a última vez.

210
00:09:20,870 --> 00:09:22,200
E realmente, pode almacenar calquera cousa.

211
00:09:22,200 --> 00:09:24,640
E veremos iso de novo en
PHP e JavaScript.

212
00:09:24,640 --> 00:09:28,550
Unha táboa é un bo tipo de suízo
Canivete que permite que almacene

213
00:09:28,550 --> 00:09:33,690
practicamente todo o que queiras dentro
que asociando chaves con valores.

214
00:09:33,690 --> 00:09:34,770
Chaves con valores.

215
00:09:34,770 --> 00:09:37,800
>> Agora, neste caso simple, a nosa
claves son só números.

216
00:09:37,800 --> 00:09:40,380
Estamos implementando un hash
táboa como unha matriz.

217
00:09:40,380 --> 00:09:43,500
E para que as teclas son 0,
1, 2, e así por diante.

218
00:09:43,500 --> 00:09:47,200
E así nós, como seres humanos, decidiu última
semana que sabe que, se estamos

219
00:09:47,200 --> 00:09:50,410
indo para almacenar nomes, imos
arbitrariamente, pero moi razoable,

220
00:09:50,410 --> 00:09:54,680
supoñer que Alice, un A nome
só vai ser indexado en 0.

221
00:09:54,680 --> 00:09:58,030
E Bob, un nome de B, será indexado
en 1, e así por diante.

222
00:09:58,030 --> 00:10:02,490
Entón, tivemos un mapeamento entre entradas,
que son cordas, eo hash

223
00:10:02,490 --> 00:10:04,560
lugares, que son números.

224
00:10:04,560 --> 00:10:07,740
>> Así que o proceso é xeralmente coñecido como
unha función de hash, e realmente pode

225
00:10:07,740 --> 00:10:09,130
implementar lo en código.

226
00:10:09,130 --> 00:10:12,080
Se eu quixese aplicar unha función hash
que fai exactamente o que nos

227
00:10:12,080 --> 00:10:17,070
acabamos de describir a última vez, eu podería
declarar unha función que recibe como

228
00:10:17,070 --> 00:10:18,330
entrada, por exemplo -

229
00:10:18,330 --> 00:10:22,190
e imos facelo neste
pantalla aquí.

230
00:10:22,190 --> 00:10:26,180
Se eu quixese aplicar un hash
función, eu podería dicir

231
00:10:26,180 --> 00:10:27,410
algo así.

232
00:10:27,410 --> 00:10:29,030
>> Vai voltar un int.

233
00:10:29,030 --> 00:10:33,600
Será chamado de hash, e é
vai aceptar como argumento un

234
00:10:33,600 --> 00:10:38,920
cadea, ou podemos ser máis axeitado agora,
e dicir char *, imos chamalo s.

235
00:10:38,920 --> 00:10:43,840
E entón, esta función ten que facer,
en última instancia, é voltar un int.

236
00:10:43,840 --> 00:10:45,990
Agora, como fai iso pode
non ser tan clara.

237
00:10:45,990 --> 00:10:49,510
Vou aplicar iso sen
forma de comprobación de erros no momento.

238
00:10:49,510 --> 00:10:55,740
Eu só vou dicir cegamente, o regreso
o que está á s soporte 0, menos,

239
00:10:55,740 --> 00:10:58,850
imos dicir, o capital Un punto e coma.

240
00:10:58,850 --> 00:10:59,960
>> Totalmente roto.

241
00:10:59,960 --> 00:11:02,620
Non é perfecto, porque
un, o que se s é nulo?

242
00:11:02,620 --> 00:11:04,000
Cousas malas van ocorrer.

243
00:11:04,000 --> 00:11:07,940
Dous, e se a primeira letra neste
nome non é unha letra maiúscula?

244
00:11:07,940 --> 00:11:09,860
Iso non vai virar
saír ben tamén.

245
00:11:09,860 --> 00:11:11,970
Pode ser unha letra minúscula
ou non unha carta a todos.

246
00:11:11,970 --> 00:11:15,520
Entón, totalmente espazo para melloras aquí,
pero esa é a idea básica.

247
00:11:15,520 --> 00:11:19,010
>> Que describiu a semana pasada como verbalmente
só un proceso de cartografía de Alicia

248
00:11:19,010 --> 00:11:23,360
0 e Bob 1 pode ser expresada
certamente máis formulaically como C

249
00:11:23,360 --> 00:11:24,320
funciona aquí.

250
00:11:24,320 --> 00:11:28,630
Chamado novo hash recibe unha cadea como
entrada e de algunha maneira fai algo

251
00:11:28,630 --> 00:11:31,020
co que a entrada para producir unha saída.

252
00:11:31,020 --> 00:11:34,130
Non moi diferente da nosa descrición da caixa negra
que fixemos moito.

253
00:11:34,130 --> 00:11:36,550
Non sei como iso se pode
traballar debaixo do capó.

254
00:11:36,550 --> 00:11:40,120
>> Polo conxunto de problemas 6, un dos retos
é para vostede decide o que

255
00:11:40,120 --> 00:11:41,920
será a súa función hash ser?

256
00:11:41,920 --> 00:11:45,760
O que vai estar dentro do que o negro
caixa e, presuntamente, será un

257
00:11:45,760 --> 00:11:50,380
pouco máis interesante que iso, e
definitivamente máis propenso a erros

258
00:11:50,380 --> 00:11:53,180
comprobando que este particular
implementación.

259
00:11:53,180 --> 00:11:54,580
>> Pero poden xurdir problemas, non?

260
00:11:54,580 --> 00:11:57,760
Se temos unha estrutura de datos, tal como esta
un, que é un dos problemas

261
00:11:57,760 --> 00:12:01,600
pode realizar ao longo do tempo en que inserir
máis e máis nomes no

262
00:12:01,600 --> 00:12:02,880
táboa hash?

263
00:12:02,880 --> 00:12:04,630
Comeza colisións, non?

264
00:12:04,630 --> 00:12:07,560
E se ten Alicia e Aaron,
dúas persoas cuxos nomes pasou

265
00:12:07,560 --> 00:12:08,190
comezar cun?

266
00:12:08,190 --> 00:12:11,660
Isto levanta a cuestión, onde
poñer o segundo como un nome?

267
00:12:11,660 --> 00:12:15,050
>> Ben, pode, inxenuamente, simplemente poñelas
onde Bob pertence, pero, a continuación, Bob é

268
00:12:15,050 --> 00:12:17,300
tipo de ferrado se tentar
introduce o teu nome xunto e

269
00:12:17,300 --> 00:12:18,240
non hai espazo para el.

270
00:12:18,240 --> 00:12:21,400
Entón pode pór Bob onde Charlie é,
e pode imaxinar iso moi rápido

271
00:12:21,400 --> 00:12:23,020
devolvendo nun pouco de confusión.

272
00:12:23,020 --> 00:12:25,600
Algo lineal, ao final, onde
Só ten que buscar a cousa toda

273
00:12:25,600 --> 00:12:28,190
buscando Alicia ou Bob
ou Aaron ou Charlie.

274
00:12:28,190 --> 00:12:33,230
>> Entón, en vez diso, propuxo, no canto de só
linearmente enquisa para espazos abertos

275
00:12:33,230 --> 00:12:36,450
e estatelando os nomes alí, nos
propuxo unha visión máis extravagante.

276
00:12:36,450 --> 00:12:41,740
Unha táboa implementada aínda cun
variedade de índices, pero o tipo de datos

277
00:12:41,740 --> 00:12:44,500
estes índices eran agora punteiros.

278
00:12:44,500 --> 00:12:47,360
Punteiros para que?

279
00:12:47,360 --> 00:12:48,730
Punteiros para listas ligadas.

280
00:12:48,730 --> 00:12:53,330
>> Porque lembran que unha lista ligada é
en realidade, só un punteiro a un nodo, e

281
00:12:53,330 --> 00:12:57,110
o nodo ten un campo seguinte, e que o nodo
ten un campo seguinte, e así por diante.

282
00:12:57,110 --> 00:13:00,690
Entón, agora pode pensar desa matriz en
o lado esquerdo dunha táboa de hash

283
00:13:00,690 --> 00:13:01,820
levando a unha lista ligada.

284
00:13:01,820 --> 00:13:07,000
A vantaxe é que se incorporarse un
colisión entre Alicia e Aaron,

285
00:13:07,000 --> 00:13:09,300
O que fai o
segundo tal persoa?

286
00:13:09,300 --> 00:13:14,150
Acaba de conectar-lle para o
extremo, ou mesmo o inicio

287
00:13:14,150 --> 00:13:15,490
desta lista ligada.

288
00:13:15,490 --> 00:13:17,340
>> E de feito, imos só mediante pasta
que por só un segundo.

289
00:13:17,340 --> 00:13:18,640
Onde faría máis sentido?

290
00:13:18,640 --> 00:13:22,060
Se eu introducir Alicia e ela acaba
a primeira posición, entón eu intento

291
00:13:22,060 --> 00:13:25,310
insira o nome de Aaron, e non hai
obviamente unha colisión, debo poñer

292
00:13:25,310 --> 00:13:27,400
el no inicio
da lista ligada?

293
00:13:27,400 --> 00:13:30,944
Isto é polo que a primeira posición,
ou ao final?

294
00:13:30,944 --> 00:13:31,440
>> Audiencia: [inaudível].

295
00:13:31,440 --> 00:13:31,990
>> DAVID Malan: Aceptar.

296
00:13:31,990 --> 00:13:32,490
Oín comezando.

297
00:13:32,490 --> 00:13:33,903
Por que no inicio?

298
00:13:33,903 --> 00:13:34,750
>> Audiencia: [inaudível].

299
00:13:34,750 --> 00:13:34,940
>> DAVID Malan: Aceptar.

300
00:13:34,940 --> 00:13:36,520
É alfabética, de xeito que é bo.

301
00:13:36,520 --> 00:13:37,330
Esta é unha boa propiedade.

302
00:13:37,330 --> 00:13:39,335
El me vai aforrar tempo potencialmente.

303
00:13:39,335 --> 00:13:43,290
Non me vai deixar facer busca binaria, pero eu
pode polo menos ser capaz de saír

304
00:13:43,290 --> 00:13:47,340
dun loop, se eu entender, ben, eu son moi
pasado eran Aaron estaría nesta

305
00:13:47,340 --> 00:13:48,310
clasificadas lista encadeada.

306
00:13:48,310 --> 00:13:50,360
Non teño que perder o meu tempo buscando
todo o camiño ata o final.

307
00:13:50,360 --> 00:13:51,530
Entón, iso é razoable.

308
00:13:51,530 --> 00:13:54,710
Por que máis pode querer inserir
nome colidindo no

309
00:13:54,710 --> 00:13:56,660
inicio da lista?

310
00:13:56,660 --> 00:13:57,397
¿Que é iso?

311
00:13:57,397 --> 00:13:58,680
>> Audiencia: [inaudível].

312
00:13:58,680 --> 00:14:00,820
>> DAVID Malan: Pode levar moito tempo
a chegar ao final da lista.

313
00:14:00,820 --> 00:14:02,490
E, de feito, máis e máis.

314
00:14:02,490 --> 00:14:04,920
Canto máis nomes que inserir
Comece unha, máis que

315
00:14:04,920 --> 00:14:06,280
cadea se ve.

316
00:14:06,280 --> 00:14:07,890
Canto máis tempo que ligaba
lista se ve.

317
00:14:07,890 --> 00:14:09,420
Entón é realmente só
perdendo o seu tempo.

318
00:14:09,420 --> 00:14:14,070
Quizais sexa mellor manter
tempo de inserción constante, gran O de 1,

319
00:14:14,070 --> 00:14:18,470
por sempre poñendo o nome de chocar en
o inicio da lista encadeada,

320
00:14:18,470 --> 00:14:21,230
e non se preocupe tanto
sobre a clasificación.

321
00:14:21,230 --> 00:14:22,600
>> Cal é a mellor resposta?

322
00:14:22,600 --> 00:14:23,320
Non está claro.

323
00:14:23,320 --> 00:14:26,140
É o tipo de depende do que o
a distribución é, cal é o defecto é

324
00:14:26,140 --> 00:14:27,850
dos nomes que está introducindo.

325
00:14:27,850 --> 00:14:29,430
Non é necesariamente
unha resposta obvia.

326
00:14:29,430 --> 00:14:33,100
Pero aquí, unha vez máis, é
unha oportunidade de deseño.

327
00:14:33,100 --> 00:14:37,220
>> Entón, a continuación, mirou para esa cousa, que
en realidade é a outra gran oportunidade

328
00:14:37,220 --> 00:14:38,180
ao p-conxunto 6.

329
00:14:38,180 --> 00:14:41,770
E entender, se non ten xa,
Zamyla mergulla ambos, hash

330
00:14:41,770 --> 00:14:43,260
mesas e trata, de forma máis detallada.

331
00:14:43,260 --> 00:14:45,630
E o paso a paso de vídeo
incorporado xuntos p-spec.

332
00:14:45,630 --> 00:14:46,590
Este foi un trie -

333
00:14:46,590 --> 00:14:51,670
T-R-I-E. E o que era interesante
isto era que o tempo de execución

334
00:14:51,670 --> 00:14:59,510
de buscar un nome, como Maxwell
última vez, era grande o de que?

335
00:14:59,510 --> 00:15:01,040
¿Que é iso?

336
00:15:01,040 --> 00:15:01,920
>> Audiencia: O número de letras.

337
00:15:01,920 --> 00:15:02,550
>> DAVID Malan: Número letras.

338
00:15:02,550 --> 00:15:03,210
Oín dúas cousas.

339
00:15:03,210 --> 00:15:04,630
Número de letras e de tempo constante.

340
00:15:04,630 --> 00:15:05,540
Entón imos coa primeira.

341
00:15:05,540 --> 00:15:06,410
O número de letras.

342
00:15:06,410 --> 00:15:10,195
Ben, esta estrutura de datos, aviso, é
como unha árbore, unha árbore de familia, cada un dos

343
00:15:10,195 --> 00:15:12,860
nós cuxas son feitas de matrices.

344
00:15:12,860 --> 00:15:16,300
E estas matrices son punteiros para
outros tales nós, ou outras, tales

345
00:15:16,300 --> 00:15:17,670
matrices na árbore.

346
00:15:17,670 --> 00:15:22,890
>> Entón, se nós queriamos, entón, determinar
Maxwell se está aquí, eu podería ir

347
00:15:22,890 --> 00:15:26,890
para a primeira matriz, na parte superior de
a árbore, o chamado raíz, arriba

348
00:15:26,890 --> 00:15:30,521
o trie, e segue o punteiro m,
a continuación, a un punteiro, entón x,

349
00:15:30,521 --> 00:15:31,710
S, E, L, L.

350
00:15:31,710 --> 00:15:34,910
E entón cando vexo algún símbolo especial,
denotado aquí como un triángulo.

351
00:15:34,910 --> 00:15:38,480
No código verás que nos propoñemos que
implementado como un bool, só dicindo si

352
00:15:38,480 --> 00:15:40,540
ou non, a palabra para aquí.

353
00:15:40,540 --> 00:15:45,270
>> Ben, xa que fun á M-A-X-W-E-L-L,
Parece que sete, quizais

354
00:15:45,270 --> 00:15:48,910
oito se somos un pasado, oito
pasos para atopar Maxwell.

355
00:15:48,910 --> 00:15:53,050
Ou imos chamalo K. Pero lembre-se pasado
banda, argumentou que, se hai

356
00:15:53,050 --> 00:15:57,540
realista lonxitude máxima nunha
palabra, como algúns personaxes de 40 e tantos, un

357
00:15:57,540 --> 00:16:00,810
lonxitude máxima implica
un valor constante.

358
00:16:00,810 --> 00:16:05,770
Entón, en realidade, si, é tecnicamente gran O
de 8 ou 7, ou realmente grande O de K. Pero

359
00:16:05,770 --> 00:16:09,420
se hai un límite finito no que
K pode ser, é unha constante.

360
00:16:09,420 --> 00:16:12,080
E por iso é grande de 1 a
ao final do día.

361
00:16:12,080 --> 00:16:13,040
>> Non no mundo real.

362
00:16:13,040 --> 00:16:15,960
Non cando realmente comezar a asistir
o reloxo de carreira do seu programa.

363
00:16:15,960 --> 00:16:20,690
É absolutamente vai ser un pouco
máis lento que verdadeiramente constante

364
00:16:20,690 --> 00:16:21,840
co tempo un chanzo.

365
00:16:21,840 --> 00:16:25,540
Vai ser sete ou oito etapas,
senón que é moi, moito mellor

366
00:16:25,540 --> 00:16:30,080
que un algoritmo como o gran de n que
depende do tamaño do que está no

367
00:16:30,080 --> 00:16:31,220
estrutura de datos.

368
00:16:31,220 --> 00:16:34,970
>> Observe a cabeza aquí é que podemos introducir
máis dun millón de nomes para este

369
00:16:34,970 --> 00:16:38,170
estrutura de datos, pero cantos máis pasos
é el que vai levarnos a atopar

370
00:16:38,170 --> 00:16:40,480
Maxwell, neste caso?

371
00:16:40,480 --> 00:16:40,780
Ningún.

372
00:16:40,780 --> 00:16:41,820
El é afectado.

373
00:16:41,820 --> 00:16:45,480
E ata agora, eu non creo que nós vimos
un exemplo dunha estrutura de datos ou un

374
00:16:45,480 --> 00:16:48,560
algoritmo que foi completamente
afectado por factores externos

375
00:16:48,560 --> 00:16:50,040
comportamentos coma este.

376
00:16:50,040 --> 00:16:51,160
Pero iso non pode ser incrible.

377
00:16:51,160 --> 00:16:52,900
Esta non pode ser a única solución
ao p-conxunto

378
00:16:52,900 --> 00:16:53,570
>> E non o é.

379
00:16:53,570 --> 00:16:55,980
Esta non é, necesariamente, os datos
estrutura debe gravitar para,

380
00:16:55,980 --> 00:16:58,220
porque, como táboas de hash, tradeoff.

381
00:16:58,220 --> 00:17:00,500
Cal é o prezo que se paga aquí?

382
00:17:00,500 --> 00:17:00,940
Memoria.

383
00:17:00,940 --> 00:17:02,890
Quero dicir, isto é unha atroz
cantidade de memoria.

384
00:17:02,890 --> 00:17:05,569
E non podes velo aquí, porque
o autor da imaxe

385
00:17:05,569 --> 00:17:09,420
obviamente truncado as matrices,
e nós non estamos a ver moitas A e

386
00:17:09,420 --> 00:17:12,700
B e C eo Q e E
e Z do nesas matrices.

387
00:17:12,700 --> 00:17:13,630
Pero eles están alí.

388
00:17:13,630 --> 00:17:17,660
>> Cada un destes nós é unha matriz enteira
de preto de 26 ou máis bytes, cada un dos

389
00:17:17,660 --> 00:17:19,170
que representa unha letra.

390
00:17:19,170 --> 00:17:22,920
27 no noso caso, para que poidamos apoiar
apóstrofos no conxunto de problemas.

391
00:17:22,920 --> 00:17:27,030
Polo tanto, esta estrutura de datos é, en realidade,
realmente densa e ampla.

392
00:17:27,030 --> 00:17:30,880
E iso só pode acabar retardando
as cousas, ou polo menos lle custa unha

393
00:17:30,880 --> 00:17:32,240
moito máis espazo.

394
00:17:32,240 --> 00:17:34,020
Pero, de novo, podemos extraer
comparacións aquí.

395
00:17:34,020 --> 00:17:39,190
>> Lembre-se de un tempo, nós conseguimos moito
tempo de carreira máis emocionante na clasificación

396
00:17:39,190 --> 00:17:42,880
cando usamos merge sort, pero o prezo
pagamos para acadar n log n para fusión

397
00:17:42,880 --> 00:17:46,930
tipo esixe que gastamos
máis que recurso?

398
00:17:46,930 --> 00:17:47,690
Máis espazo.

399
00:17:47,690 --> 00:17:50,530
Necesitabamos dunha matriz secundaria a
copiar a xente, así como

400
00:17:50,530 --> 00:17:51,620
fixemos aquí no escenario.

401
00:17:51,620 --> 00:17:55,880
Entón, de novo, hai claros gañadores,
pero só proxecto subxectiva

402
00:17:55,880 --> 00:17:57,710
decisións a tomar.

403
00:17:57,710 --> 00:17:58,060
>> Todo ben.

404
00:17:58,060 --> 00:17:59,130
Entón, que tal isto?

405
00:17:59,130 --> 00:18:02,050
Calquera persoa recoñecer que D-Hall?

406
00:18:02,050 --> 00:18:02,440
Aceptar.

407
00:18:02,440 --> 00:18:03,170
Así, tres de nós.

408
00:18:03,170 --> 00:18:03,750
Mather House.

409
00:18:03,750 --> 00:18:05,070
Polo tanto, esta é para unha cea de Mather.

410
00:18:05,070 --> 00:18:09,650
¿Podería supoñer que todos os comedores teñen
pila de bandexas coma este.

411
00:18:09,650 --> 00:18:11,950
E iso é realmente representativo
de algo que xa

412
00:18:11,950 --> 00:18:13,050
obviamente, xa visto.

413
00:18:13,050 --> 00:18:14,850
Chamamos-lle, literalmente, unha pila.

414
00:18:14,850 --> 00:18:18,970
E a pila, en termos da súa
memoria do ordenador, é onde os datos van

415
00:18:18,970 --> 00:18:20,460
mentres que as funcións están a ser chamados.

416
00:18:20,460 --> 00:18:23,410
>> Por exemplo, que tipo de cousas
na pila respecto ao

417
00:18:23,410 --> 00:18:27,420
esquema de memoria que discutir
nas últimas semanas?

418
00:18:27,420 --> 00:18:28,736
¿Que é iso?

419
00:18:28,736 --> 00:18:29,670
>> Audiencia: Chamadas a funcións.

420
00:18:29,670 --> 00:18:30,260
>> DAVID Malan: Eu sinto moito.

421
00:18:30,260 --> 00:18:31,210
>> Audiencia: Chamadas a funcións.

422
00:18:31,210 --> 00:18:33,590
>> DAVID Malan: Chamadas para funcións, pero
En concreto, o que está dentro de cada un

423
00:18:33,590 --> 00:18:35,340
estes cadros?

424
00:18:35,340 --> 00:18:37,220
Que tipo de cousas?

425
00:18:37,220 --> 00:18:37,460
Si

426
00:18:37,460 --> 00:18:38,500
Así, as variables locais.

427
00:18:38,500 --> 00:18:43,080
Sempre que necesitabamos dalgún almacenamento local,
como un argumento, ou int I, ou int

428
00:18:43,080 --> 00:18:45,940
temp, ou calquera que sexa o lugar de
variable é, fomos

429
00:18:45,940 --> 00:18:47,210
poñendo que na pila.

430
00:18:47,210 --> 00:18:49,610
E chamamos iso de unha pila por
desa idea de estratificación.

431
00:18:49,610 --> 00:18:52,940
Só un tipo de xogos con realidade,
o concepto do mesmo.

432
00:18:52,940 --> 00:18:56,650
>> Pero resulta que unha pila pode tamén
pode ver como unha estrutura de datos, un

433
00:18:56,650 --> 00:19:00,110
alternativa a unha matriz, unha alternativa
para unha lista ligada.

434
00:19:00,110 --> 00:19:02,770
Algo conceptualmente máis interesante
que pode ser

435
00:19:02,770 --> 00:19:06,030
aplicado a usar un destes
cousas, pero é un tipo de

436
00:19:06,030 --> 00:19:09,140
estrutura de datos de apoio, en realidade,
só dúas operacións.

437
00:19:09,140 --> 00:19:11,000
Pero pode engadir máis sofisticado
características do que estes.

438
00:19:11,000 --> 00:19:12,180
Pero estes son os principios básicos -

439
00:19:12,180 --> 00:19:13,510
push e pop.

440
00:19:13,510 --> 00:19:19,240
>> E a idea cunha pila é que se eu
ten aquí, con ou sen Annenberg

441
00:19:19,240 --> 00:19:22,880
saber, unha bandexa xunto
co número 9 nel.

442
00:19:22,880 --> 00:19:23,870
Entón, simplemente un int.

443
00:19:23,870 --> 00:19:26,990
E quero empurrar este para os datos
estrutura, que actualmente está baleiro.

444
00:19:26,990 --> 00:19:28,790
Considerar este o fondo da pila.

445
00:19:28,790 --> 00:19:33,150
Eu levaría ese número 9 ao
apilar, e agora está alí.

446
00:19:33,150 --> 00:19:36,040
>> Pero a cousa interesante sobre unha pila
é que se eu agora quere empurrar

447
00:19:36,040 --> 00:19:40,210
algún outro valor, como 17 anos, e eu empurro
esta en a pila, eu vou facer

448
00:19:40,210 --> 00:19:43,290
o único intuitivo, eu só vou
para poñelas exactamente onde nós, seres humanos

449
00:19:43,290 --> 00:19:45,180
estaría inclinado a poñelas, na parte superior.

450
00:19:45,180 --> 00:19:48,850
Pero o que é interesante agora
é, como fago para chegar a 9?

451
00:19:48,850 --> 00:19:50,670
Vostede sabe, eu non sen algún esforzo.

452
00:19:50,670 --> 00:19:54,070
>> Entón, o que é interesante sobre
unha pila é que, ao deseño,

453
00:19:54,070 --> 00:19:56,330
é unha estrutura de datos LIFO.

454
00:19:56,330 --> 00:19:59,680
Estraña forma de describir
last in, first out.

455
00:19:59,680 --> 00:20:03,280
Así, o último número na
nesta época tiña 17 anos.

456
00:20:03,280 --> 00:20:07,540
Entón, se eu queira aparecer algo fóra
do conxunto, que só pode ser 17.

457
00:20:07,540 --> 00:20:11,890
Polo tanto, hai unha orde obrigatoria de
operacións aquí, onde o último elemento

458
00:20:11,890 --> 00:20:14,260
en ten que ser o primeiro en saír.

459
00:20:14,260 --> 00:20:16,440
De aí a sigla, LIFO.

460
00:20:16,440 --> 00:20:19,160
>> Entón, por que isto pode ser útil?

461
00:20:19,160 --> 00:20:22,690
Son os seus contextos en que tiña
quere unha estrutura de datos como este?

462
00:20:22,690 --> 00:20:24,810
Ben, iso certamente foi útil
no interior dun ordenador.

463
00:20:24,810 --> 00:20:29,050
Entón, usar sistemas operativos claramente esta
tipo de estrutura de datos para Stacks.

464
00:20:29,050 --> 00:20:32,800
Veremos tamén a mesma idea
cando se trata de páxinas web.

465
00:20:32,800 --> 00:20:35,890
Entón, esta semana e na próxima semana e ademais,
e como comezar a aplicar web

466
00:20:35,890 --> 00:20:39,490
páxinas nunha linguaxe chamada HTML, pode
realmente usar unha estrutura de datos como

467
00:20:39,490 --> 00:20:42,690
isto para determinar se a páxina
está formatado correctamente.

468
00:20:42,690 --> 00:20:47,170
Porque imos ver todas as páxinas seguen
unha especie de xerarquía, un retroceso

469
00:20:47,170 --> 00:20:52,030
que, ao final do día, ser un
estrutura de árbore debaixo do capó.

470
00:20:52,030 --> 00:20:53,620
Así, máis do que en só un bit.

471
00:20:53,620 --> 00:20:56,560
>> Pero, por agora, imos propoñer un
momento, como poderiamos ir sobre

472
00:20:56,560 --> 00:20:58,830
representando o que é unha pila?

473
00:20:58,830 --> 00:21:03,370
Déixeme propoñer que Implementar
unha pila cun código coma este.

474
00:21:03,370 --> 00:21:07,990
Así, unha pila terá no seu interior
dúas cousas, unha matriz, chamados de taboleiros,

475
00:21:07,990 --> 00:21:09,510
só para ser coherente co demo.

476
00:21:09,510 --> 00:21:12,660
E cada un dos elementos desa matriz
será un tipo int.

477
00:21:12,660 --> 00:21:14,740
Ea capacidade é presuntamente o que?

478
00:21:14,740 --> 00:21:18,796
Porque eu non teño escrito o
definición completa aquí.

479
00:21:18,796 --> 00:21:21,535
>> É, probablemente, o máximo
tamaño da matriz.

480
00:21:21,535 --> 00:21:25,150
E probablemente é declarado como un forte
establecer, na parte superior do ficheiro, algúns

481
00:21:25,150 --> 00:21:28,450
tipo de constante como implícito
a mera capitalización.

482
00:21:28,450 --> 00:21:32,250
Así, a capacidade é definida algures
medida que o tamaño máximo posible.

483
00:21:32,250 --> 00:21:35,590
Mentres tanto, dentro da estrutura de datos
coñecida como unha pila haberá

484
00:21:35,590 --> 00:21:38,630
ser un número enteiro só coñecido
simplemente como tamaño.

485
00:21:38,630 --> 00:21:43,400
>> Entón, se eu fose para representar esta empresa
pictoricamente, imos supor que este

486
00:21:43,400 --> 00:21:48,070
Cada caixa negra representa a miña stack.

487
00:21:48,070 --> 00:21:50,070
Dentro é dúas variables.

488
00:21:50,070 --> 00:21:54,780
Entón, eu vou chamar a
como unha primeira dimensión.

489
00:21:54,780 --> 00:21:57,420
E o segundo que eu vou
para debuxar como unha matriz.

490
00:21:57,420 --> 00:22:01,060
>> Pero só para manter as cousas en orde,
normalmente gustaríame chamar unha matriz como

491
00:22:01,060 --> 00:22:04,910
iso, pero é unha especie de bo
se corresponde coa realidade, ou

492
00:22:04,910 --> 00:22:06,230
coincidir co modelo mental.

493
00:22:06,230 --> 00:22:12,880
Entón déixeme en vez de chamar a matriz
vertical, o que é xusto, unha vez máis,

494
00:22:12,880 --> 00:22:13,840
interpretación do artista.

495
00:22:13,840 --> 00:22:16,610
Realmente non importa o que
está debaixo do capó.

496
00:22:16,610 --> 00:22:20,350
E imos dicir que, por defecto,
capacidade será tres.

497
00:22:20,350 --> 00:22:23,480
Polo tanto, este será lugar 0, este
será de localización 1, o presente

498
00:22:23,480 --> 00:22:25,740
será localización 2.

499
00:22:25,740 --> 00:22:29,330
>> Se eu subornar con unha bola de estrés, sería
alguén que gusta de aparecer e realizar o

500
00:22:29,330 --> 00:22:30,870
Suba aquí por un momento?

501
00:22:30,870 --> 00:22:31,960
OK, vin o de primeira man.

502
00:22:31,960 --> 00:22:33,950
Imos para arriba.

503
00:22:33,950 --> 00:22:36,500
Todo ben.

504
00:22:36,500 --> 00:22:38,760
Entón, eu creo que é Steven.

505
00:22:38,760 --> 00:22:40,035
Imos para arriba.

506
00:22:40,035 --> 00:22:40,770
Todo ben.

507
00:22:40,770 --> 00:22:46,760
>> Pero supoñamos agora que volver á de inicio
estado do mundo onde

508
00:22:46,760 --> 00:22:52,180
só declararon unha pila, e é
terá unha capacidade de tres.

509
00:22:52,180 --> 00:22:54,470
Pero o tamaño non foi determinada.

510
00:22:54,470 --> 00:22:56,100
Bandexas aínda non foi determinada.

511
00:22:56,100 --> 00:22:57,300
Así, un par de preguntas en primeiro lugar.

512
00:22:57,300 --> 00:23:01,310
E déixeme darlle micrófono para que poida
participar máis activamente neste proceso.

513
00:23:01,310 --> 00:23:05,190
>> Entón, o que está dentro do tamaño neste momento
o tempo, se todo o que eu teño feito é

514
00:23:05,190 --> 00:23:09,340
declarou unha pila con
unha liña de código?

515
00:23:09,340 --> 00:23:10,100
>> Steven: Non moito.

516
00:23:10,100 --> 00:23:12,080
>> DAVID Malan: OK, non moito.

517
00:23:12,080 --> 00:23:14,410
Non sabemos o que está dentro do tamaño,
sabemos o que está dentro

518
00:23:14,410 --> 00:23:16,330
desa matriz aquí?

519
00:23:16,330 --> 00:23:18,630
>> Steven: Só código aleatorio, non?

520
00:23:18,630 --> 00:23:20,220
Just -

521
00:23:20,220 --> 00:23:23,230
>> DAVID Malan: Si, eu vou
chamalo de código, pero aleatoria -

522
00:23:23,230 --> 00:23:23,820
>> Steven: Cousas.

523
00:23:23,820 --> 00:23:28,290
>> DAVID Malan: Cousas como chou

524
00:23:28,290 --> 00:23:28,870
>> Steven: Bits.

525
00:23:28,870 --> 00:23:29,530
>> DAVID Malan: Bits, non?

526
00:23:29,530 --> 00:23:31,190
Así, os valores de lixo, non?

527
00:23:31,190 --> 00:23:33,470
Entón permutacións de 0 e 1 do.

528
00:23:33,470 --> 00:23:35,920
Restos de usos anteriores
desta memoria.

529
00:23:35,920 --> 00:23:38,150
E nós realmente non sei cales son os valores
son, polo tanto, normalmente atraelos

530
00:23:38,150 --> 00:23:38,930
como puntos de interrogação.

531
00:23:38,930 --> 00:23:41,990
>> Entón o primeiro que estamos presuntamente
vai querer facer aquí -

532
00:23:41,990 --> 00:23:46,630
e deixe-me dar este campo dentro
de aí o nome - bandexas.

533
00:23:46,630 --> 00:23:49,540
O que temos que presuntamente arrincar
tamaño para se queremos

534
00:23:49,540 --> 00:23:51,040
comezar a usar esta pila?

535
00:23:51,040 --> 00:23:53,070
>> Steven: Bandexa é sub 3.

536
00:23:53,070 --> 00:23:53,910
>> DAVID Malan: Entón, Aceptar.

537
00:23:53,910 --> 00:23:56,710
Para ser claro, a capacidade é declarado
noutros lugares como tres.

538
00:23:56,710 --> 00:23:58,570
E iso é o que eu usei
para asignar a matriz.

539
00:23:58,570 --> 00:24:03,535
Tamaño vai referirse cantos
bandexas son actualmente na pila.

540
00:24:03,535 --> 00:24:03,880
>> Steven: Cero.

541
00:24:03,880 --> 00:24:04,460
>> DAVID Malan: Así debe ser cero.

542
00:24:04,460 --> 00:24:07,760
Entón vai adiante, e con calquera dedo,
sacar un cero en tamaño.

543
00:24:07,760 --> 00:24:08,440
Todo ben.

544
00:24:08,440 --> 00:24:10,920
Entón, agora, o que está dentro dese
aquí, nós non sabemos.

545
00:24:10,920 --> 00:24:12,160
Estes son realmente só valores de lixo.

546
00:24:12,160 --> 00:24:14,800
Entón, poderíamos extraer puntos de interrogación, pero
imos manter a tarxeta limpa, polo de agora

547
00:24:14,800 --> 00:24:16,300
porque non importa
o que está aí.

548
00:24:16,300 --> 00:24:19,130
Non necesitamos arrincar a matriz
para nada, porque se sabe que

549
00:24:19,130 --> 00:24:23,100
o tamaño da pila é igual a cero, tamén, nos
non debe estar mirando para nada en

550
00:24:23,100 --> 00:24:25,590
esa matriz de calquera maneira en
Neste punto o tempo.

551
00:24:25,590 --> 00:24:29,970
>> Entón, supoña que empurrar o
o número 9 na pila.

552
00:24:29,970 --> 00:24:33,750
Como debemos actualizar a estrutura de datos
dentro desta caixa negra?

553
00:24:33,750 --> 00:24:35,540
Cales valores teñen que cambiar?

554
00:24:35,540 --> 00:24:36,200
>> Steven: Dentro -

555
00:24:36,200 --> 00:24:37,400
o tamaño?

556
00:24:37,400 --> 00:24:37,650
>> DAVID Malan: Aceptar.

557
00:24:37,650 --> 00:24:38,770
Tamaño debe facer-se o que?

558
00:24:38,770 --> 00:24:39,580
>> Steven: arquivo sería un.

559
00:24:39,580 --> 00:24:39,870
>> DAVID Malan: Aceptar.

560
00:24:39,870 --> 00:24:41,110
Así, o tamaño que se fan un.

561
00:24:41,110 --> 00:24:42,540
Así, pode facelo de algunhas formas.

562
00:24:42,540 --> 00:24:46,920
Deixe-me dar-lle, agora o seu
dedo é unha goma.

563
00:24:46,920 --> 00:24:47,260
Todo ben.

564
00:24:47,260 --> 00:24:49,960
Entón agora o dedo é un pincel.

565
00:24:49,960 --> 00:24:50,330
Todo ben.

566
00:24:50,330 --> 00:24:52,820
E agora, o que máis ten que cambiar,
obviamente, na estrutura de datos?

567
00:24:52,820 --> 00:24:57,060
>> Steven: Nós imos a partir de
de abaixo arriba a 9.

568
00:24:57,060 --> 00:24:57,760
>> DAVID Malan: 9.

569
00:24:57,760 --> 00:24:58,420
OK, Good.

570
00:24:58,420 --> 00:25:01,550
Entón, non importa o que está no
localización de un ou dous, porque son

571
00:25:01,550 --> 00:25:04,520
valores de lixo, pero non debe preocuparse
mirando alí porque o tamaño é

572
00:25:04,520 --> 00:25:07,540
dicirnos que só o primeiro elemento
é realmente lexítimo.

573
00:25:07,540 --> 00:25:10,400
Entón agora eu empurrar 17 da lista.

574
00:25:10,400 --> 00:25:11,830
Que pasa con esta imaxe?

575
00:25:11,830 --> 00:25:14,720
>> Steven: So tamaño está indo a ir a dous.

576
00:25:14,720 --> 00:25:15,300
>> DAVID Malan: Aceptar.

577
00:25:15,300 --> 00:25:16,070
Está Eraser -

578
00:25:16,070 --> 00:25:16,810
oops.

579
00:25:16,810 --> 00:25:18,026
Vostede é unha goma.

580
00:25:18,026 --> 00:25:18,840
>> Steven: Eraser.

581
00:25:18,840 --> 00:25:19,720
>> DAVID Malan: Vostede é un pincel.

582
00:25:19,720 --> 00:25:20,560
>> Steven: Brush.

583
00:25:20,560 --> 00:25:20,920
>> DAVID Malan: Aceptar.

584
00:25:20,920 --> 00:25:21,600
E o que máis?

585
00:25:21,600 --> 00:25:22,600
>> Steven: E entón nós -

586
00:25:22,600 --> 00:25:22,915
>> DAVID Malan: Nós empuxamos 17.

587
00:25:22,915 --> 00:25:24,760
>> Steven: Nós furamos 17 enriba, por iso -

588
00:25:24,760 --> 00:25:25,710
>> DAVID Malan: OK, moi bo.

589
00:25:25,710 --> 00:25:27,040
>> Steven: - déixase caer.

590
00:25:27,040 --> 00:25:27,530
>> DAVID Malan: Todo ben.

591
00:25:27,530 --> 00:25:27,940
Está quedando máis fácil.

592
00:25:27,940 --> 00:25:29,300
Eu non estou indo a axudar neste momento.

593
00:25:29,300 --> 00:25:30,510
Empurre 22.

594
00:25:30,510 --> 00:25:31,720
>> Steven: Feito.

595
00:25:31,720 --> 00:25:34,870
Tornándose unha goma.

596
00:25:34,870 --> 00:25:37,340
Estou me facendo un pincel.

597
00:25:37,340 --> 00:25:39,340
E entón eu estou poñendo 22.

598
00:25:39,340 --> 00:25:40,100
>> DAVID Malan: 22.

599
00:25:40,100 --> 00:25:40,620
Excelente.

600
00:25:40,620 --> 00:25:41,380
Así, unha vez máis.

601
00:25:41,380 --> 00:25:44,280
Agora estou indo a empurrar
para a pila 26.

602
00:25:44,280 --> 00:25:46,350
>> Steven: Ooh.

603
00:25:46,350 --> 00:25:50,278
Oh Deus.

604
00:25:50,278 --> 00:25:52,520
Realmente me colleu desprevenido.

605
00:25:52,520 --> 00:25:53,703
>> DAVID Malan: Non fixo
ver esta chegada?

606
00:25:53,703 --> 00:25:55,930
>> Steven: Non vin isto chegando.

607
00:25:55,930 --> 00:25:58,756
Poderiamos capacidade de re-inicio?

608
00:25:58,756 --> 00:25:59,790
>> DAVID Malan: Esa é unha boa pregunta.

609
00:25:59,790 --> 00:26:02,360
Entón, temos unha especie de nós mesmos pintado
nunha esquina aquí.

610
00:26:02,360 --> 00:26:06,740
Non hai realmente nada bo fóra a Steven
porque temos asignado esa matriz

611
00:26:06,740 --> 00:26:09,130
estaticamente, por así dicir, dentro
da estrutura de datos.

612
00:26:09,130 --> 00:26:12,170
E temos esencialmente codificado
que sexa de tamaño tres.

613
00:26:12,170 --> 00:26:14,170
Polo tanto, non podemos realmente realocá lo.

614
00:26:14,170 --> 00:26:20,020
>> Poderiamos se volvemos, nos
redefinido bandexas para ser un punteiro que

615
00:26:20,020 --> 00:26:22,300
Axiña, usan a memoria malloc man.

616
00:26:22,300 --> 00:26:25,050
Porque, se temos a memoria de
o monte vía malloc, nos

617
00:26:25,050 --> 00:26:26,430
entón podería libralo.

618
00:26:26,430 --> 00:26:29,630
Pero, antes de libera-lo, poderiamos
recolocar unha porción maior de memoria,

619
00:26:29,630 --> 00:26:31,330
actualizar o punteiro, e así por diante.

620
00:26:31,330 --> 00:26:33,500
Pero, polo de agora, iso é realmente
o mellor que podemos facer.

621
00:26:33,500 --> 00:26:36,360
Push pop son seguramente
ter para sinalizar un erro.

622
00:26:36,360 --> 00:26:40,270
>> Así, por exemplo, a nosa implantación
de impulso podería voltar un booleano que

623
00:26:40,270 --> 00:26:42,390
previamente retorno realidade, verdade, verdade.

624
00:26:42,390 --> 00:26:48,390
Pero, por cuarta vez, que vai ter
para voltar false, por exemplo.

625
00:26:48,390 --> 00:26:48,540
Todo ben.

626
00:26:48,540 --> 00:26:49,540
Moi ben feito.

627
00:26:49,540 --> 00:26:50,060
Parabéns.

628
00:26:50,060 --> 00:26:52,160
Vostede gañou a súa bola de estrés hoxe.

629
00:26:52,160 --> 00:26:53,110
>> [Aplausos]

630
00:26:53,110 --> 00:26:54,382
>> Steven: Grazas.

631
00:26:54,382 --> 00:26:55,680
>> DAVID Malan: Grazas.

632
00:26:55,680 --> 00:26:59,740
OK, entón iso non parece ser moi
dun paso adiante, non?

633
00:26:59,740 --> 00:27:01,410
Describimos esta estrutura de datos.

634
00:27:01,410 --> 00:27:02,320
Foi interesante, non?

635
00:27:02,320 --> 00:27:03,200
Os sistemas operativos gusta.

636
00:27:03,200 --> 00:27:06,360
Ao parecer, a web pode facer uso desta,
e outras aplicacións aínda.

637
00:27:06,360 --> 00:27:10,870
Pero o que unha limitación estúpida que estamos
volver a unha especie de semana dous límites

638
00:27:10,870 --> 00:27:12,880
onde se fixaron tamaño arrays.

639
00:27:12,880 --> 00:27:15,010
>> Polo tanto, hai en realidade un par de
formas que poderiamos resolver iso.

640
00:27:15,010 --> 00:27:18,750
Poderiamos reservar dinámicamente o array,
non polo difícil codifica-lo como eu

641
00:27:18,750 --> 00:27:22,600
feito aquí, pero re-declarando
iso, só para quedar claro, como

642
00:27:22,600 --> 00:27:23,830
algo así.

643
00:27:23,830 --> 00:27:29,040
Int * bandexas, non decidir
Aínda nunha capacidade.

644
00:27:29,040 --> 00:27:35,460
Pero cando declarar a pila noutro lugar
no meu código, eu podería entón chamar malloc,

645
00:27:35,460 --> 00:27:38,250
obter o enderezo de unha peza de
memoria, e eu podía asignar

646
00:27:38,250 --> 00:27:39,980
ese enderezo para bandexas.

647
00:27:39,980 --> 00:27:43,340
>> E entón, por que é só unha peza de
memoria, eu podería continuar a utilizar cadrado

648
00:27:43,340 --> 00:27:45,450
a notación de soporte do xeito habitual.

649
00:27:45,450 --> 00:27:49,020
Porque unha vez máis, hai unha especie de agasallo
equivalente funcional de matrices e

650
00:27:49,020 --> 00:27:50,820
bloques de memoria que veñen
redor de malloc.

651
00:27:50,820 --> 00:27:53,090
Podemos tratar un como o outro
mediante a aritmética de punteiro ou

652
00:27:53,090 --> 00:27:54,440
notación de corchete.

653
00:27:54,440 --> 00:27:55,660
Entón esta é unha visión.

654
00:27:55,660 --> 00:28:00,120
>> Pero de que outra forma poderiamos aplicar este
mesma estrutura de datos, podendo?

655
00:28:00,120 --> 00:28:00,280
Non?

656
00:28:00,280 --> 00:28:04,530
Eu sinto que nós só resolveu este
problema como hai unha semana.

657
00:28:04,530 --> 00:28:08,860
Cal foi a solución a este problema
que Steven correu?

658
00:28:08,860 --> 00:28:10,370
Listas ligadas entre si, certo.

659
00:28:10,370 --> 00:28:13,410
>> O problema é que estamos pintando
nos a un canto, alocando

660
00:28:13,410 --> 00:28:17,580
anticipadamente moi pouca memoria que
logo ter que tratar de algunha maneira co ben,

661
00:28:17,580 --> 00:28:19,880
porque non só evitar que
emitir por completo?

662
00:28:19,880 --> 00:28:26,170
¿Por que non basta declarar bandexas para ser un
punteiro para un nó, ergo unha lista ligada,

663
00:28:26,170 --> 00:28:30,740
e despois simplemente reservar novos nós
cada vez que Steven necesaria para atender a unha

664
00:28:30,740 --> 00:28:32,400
Número na estrutura de datos.

665
00:28:32,400 --> 00:28:34,200
>> Así, a imaxe tería que cambiar.

666
00:28:34,200 --> 00:28:38,220
Non vai ser tan limpa e tan
simple como un conxunto de tres enteiros.

667
00:28:38,220 --> 00:28:42,970
Agora será un punteiro a un
struct, e que struct vai

668
00:28:42,970 --> 00:28:44,830
ter un int e un punteiro próximo.

669
00:28:44,830 --> 00:28:47,670
Levará a través dese punteiro
a outra estrutura para tal

670
00:28:47,670 --> 00:28:48,600
outro tal estrutura.

671
00:28:48,600 --> 00:28:50,560
Así, o cadro sería realmente
estar un pouco máis confusa.

672
00:28:50,560 --> 00:28:52,950
E teriamos frechas amarre
todo xuntos.

673
00:28:52,950 --> 00:28:55,280
>> Pero iso é bo, correcto, porque
vimos como facelo.

674
00:28:55,280 --> 00:28:58,180
E unha vez que sentirse cómodo
aplicar algo como un linked

675
00:28:58,180 --> 00:29:01,450
lista, que vai ter que facer se
decide aplicar unha táboa hash coa

676
00:29:01,450 --> 00:29:05,120
fío separado para p-set 6, pode
usalo como un bloque de construción, ou un

677
00:29:05,120 --> 00:29:08,870
ingrediente, ou en scratch dicir, un
procedemento, algo que poñer, que

678
00:29:08,870 --> 00:29:12,560
creou a súa propia peza do puzzle
, Que pode reutilizar.

679
00:29:12,560 --> 00:29:17,090
Compensacións que si, pero as posibles solucións
que temos realmente visto antes.

680
00:29:17,090 --> 00:29:20,560
>> Entón, moitas veces, vostede ve iso todo
ano ou dous, cando lanzamentos de Apple

681
00:29:20,560 --> 00:29:23,060
algo novo, e todas as persoas tolas
liña do lado de fóra da Mazá

682
00:29:23,060 --> 00:29:27,050
tenda a mercar o seu marxinal
actualizar o hardware.

683
00:29:27,050 --> 00:29:30,420
Digo isto, está todo ben, porque
Eu son unha desas persoas.

684
00:29:30,420 --> 00:29:35,140
Entón, que tipo de estrutura de datos
pode representar esa realidade?

685
00:29:35,140 --> 00:29:36,980
>> Ben, imos chamalo dunha fila, nunha liña.

686
00:29:36,980 --> 00:29:40,270
So British chamaría tanto tipicamente un
cola de todas as maneiras, polo que é un bo nome.

687
00:29:40,270 --> 00:29:44,960
E as dúas operacións que a cola
apoia imos chamar a enfileirar

688
00:29:44,960 --> 00:29:48,900
operación e unha operación de eliminación da fila,
que son similares en

689
00:29:48,900 --> 00:29:50,120
espírito de push e pop.

690
00:29:50,120 --> 00:29:54,060
É só unha especie de diferente en
convención, o que estamos chamando eses.

691
00:29:54,060 --> 00:29:57,680
Pero para enfileirar algo significa para engadir
ou inserir-lo na estrutura de datos.

692
00:29:57,680 --> 00:29:59,570
Para desenfileirar medios para eliminar-lo.

693
00:29:59,570 --> 00:30:05,170
Pero, mentres unha pila era un dos datos LIFO
estrutura, unha fila é un primeiro,

694
00:30:05,170 --> 00:30:06,740
por primeira vez a estrutura de datos.

695
00:30:06,740 --> 00:30:10,050
>> Se é a primeira persoa na cola,
será a primeira persoa en chegar

696
00:30:10,050 --> 00:30:12,420
fóra de liña e mercar o seu novo dispositivo.

697
00:30:12,420 --> 00:30:18,070
Imaxina o quão chat estas persoas sería
se a Apple en canto usou unha pila, a

698
00:30:18,070 --> 00:30:21,250
exemplo, para aplicar a colleita
up do seu novo xoguete.

699
00:30:21,250 --> 00:30:24,310
Entón filas teñen sentido, por suposto, e
podemos pensar en todo tipo de

700
00:30:24,310 --> 00:30:27,480
aplicacións, presuntamente, a filas,
especialmente cando quere xustiza.

701
00:30:27,480 --> 00:30:30,040
Entón, como podemos implementar las
como unha estrutura de datos?

702
00:30:30,040 --> 00:30:33,680
>> Ben, eu propoño que poidamos
Debe facelo deste xeito.

703
00:30:33,680 --> 00:30:35,225
Entón, eu vou agora ter números.

704
00:30:35,225 --> 00:30:38,190
Entón, imos manter as cousas simples e non
necesariamente falar en termos de bandexas.

705
00:30:38,190 --> 00:30:40,220
Só números que a xente de comezara.

706
00:30:40,220 --> 00:30:43,760
Capacidade vai, unha vez máis, resolver o
número total de persoas que poden estar en

707
00:30:43,760 --> 00:30:46,900
Nesta liña, como tres ou
calquera outro valor.

708
00:30:46,900 --> 00:30:50,760
>> Pero propoño que eu teño para manter o control
non só do tamaño da

709
00:30:50,760 --> 00:30:52,370
cola, cantas cousas están na mesma.

710
00:30:52,370 --> 00:30:56,310
Así, o tamaño é o tamaño actual, a capacidade
é o tamaño máximo.

711
00:30:56,310 --> 00:30:58,540
Así de novo, a nomenclatura
por convención.

712
00:30:58,540 --> 00:31:03,680
Por que eu teño un int adicional dentro
dunha cola para seguir o que está en

713
00:31:03,680 --> 00:31:05,365
fronte da liña?

714
00:31:05,365 --> 00:31:07,930

715
00:31:07,930 --> 00:31:10,910
Por que eu teño que facer iso neste caso?

716
00:31:10,910 --> 00:31:14,750

717
00:31:14,750 --> 00:31:16,190
>> Ben, como é esta foto
vai cambiar?

718
00:31:16,190 --> 00:31:19,280
Eu probablemente pode reutilizar máis
da imaxe.

719
00:31:19,280 --> 00:31:21,480
Déixeme ir adiante e borrar o que está aquí.

720
00:31:21,480 --> 00:31:24,580
Nós imos dar a este un pouco
nome diferente aquí.

721
00:31:24,580 --> 00:31:28,930
Imos nos librar dos 17, imos nos librar
do 9, imos nos librar do 3.

722
00:31:28,930 --> 00:31:30,410
E imos engadir unha outra cousa.

723
00:31:30,410 --> 00:31:34,710
Propoño que eu teño para manter o control de
a fronte da lista, que é só

724
00:31:34,710 --> 00:31:35,570
será un int ben.

725
00:31:35,570 --> 00:31:36,550
E nós imos mantelo simple.

726
00:31:36,550 --> 00:31:37,740
Ningunha lista ligada por agora.

727
00:31:37,740 --> 00:31:40,900
>> Imos admitir que imos
bater-se contra este límite.

728
00:31:40,900 --> 00:31:43,720
Pero o que quero ver
pasar esta vez?

729
00:31:43,720 --> 00:31:47,240
Entón, supoñamos que eu dalle o primeiro
persoa ven na liña, e

730
00:31:47,240 --> 00:31:48,560
é o número 9.

731
00:31:48,560 --> 00:31:49,680
Temos bolas de estrés.

732
00:31:49,680 --> 00:31:51,330
Podo roubar, digamos, dúas ou tres persoas?

733
00:31:51,330 --> 00:31:52,690
Un, dous, tres?

734
00:31:52,690 --> 00:31:53,120
Imos para arriba.

735
00:31:53,120 --> 00:31:56,022
Dereito de fronte, xa que
nós imos facer este rápido.

736
00:31:56,022 --> 00:31:59,415
>> Cada un de vós é agora será
un neno fan na cola de Apple.

737
00:31:59,415 --> 00:32:03,970

738
00:32:03,970 --> 00:32:06,210
Non vai recibir o hardware de Apple
a finais deste aínda.

739
00:32:06,210 --> 00:32:06,500
Todo ben.

740
00:32:06,500 --> 00:32:09,430
Entón, vostede é o número 9, está
número 17, número 22.

741
00:32:09,430 --> 00:32:12,130
Estes son números arbitrarios, como
IDs de estudante ou outros enfeites.

742
00:32:12,130 --> 00:32:14,550
E en só un momento, imos comezar
para comezar a engadir as cousas.

743
00:32:14,550 --> 00:32:16,000
E eu vou correr o consello aquí neste momento.

744
00:32:16,000 --> 00:32:19,570
>> Polo tanto, neste caso, eu xa inicializar
diante para ser -

745
00:32:19,570 --> 00:32:22,380
En realidade, eu realmente non me importa o que o
diante é porque o tamaño é igual a cero.

746
00:32:22,380 --> 00:32:24,480
Polo tanto, este pode moi ben
ser un punto de interrogación.

747
00:32:24,480 --> 00:32:26,170
Estes son todos os puntos de interrogación.

748
00:32:26,170 --> 00:32:29,880
Entón, agora nós imos realmente comezar a ver algúns
persoas facendo cola na tenda.

749
00:32:29,880 --> 00:32:33,320
>> Entón, se o número 9, que é o primeiro
alí 05:00, vai adiante e aliñar,

750
00:32:33,320 --> 00:32:34,210
ou na noite anterior.

751
00:32:34,210 --> 00:32:34,580
Aceptar.

752
00:32:34,580 --> 00:32:35,940
Entón agora 9 é aquí.

753
00:32:35,940 --> 00:32:37,940
Así 9 é diante da lista.

754
00:32:37,940 --> 00:32:41,440
Entón, eu estou indo a ir adiante e actualizar
o tamaño dos datos actuais

755
00:32:41,440 --> 00:32:44,740
estrutura para non ser máis 0,
pero para ser 1.

756
00:32:44,740 --> 00:32:47,630
Vou poñer 9 na
cabeza da lista.

757
00:32:47,630 --> 00:32:51,020
Déixeme ir adiante e cambiar a pantalla
así podemos ver por nós aquí.

758
00:32:51,020 --> 00:32:53,220
>> E agora o que quero
para poñer adiante?

759
00:32:53,220 --> 00:32:56,240
Vou manter o control que o
cabeza da cola agora

760
00:32:56,240 --> 00:32:58,570
está na posición 0.

761
00:32:58,570 --> 00:33:00,510
Porque o que está próximo vai pasar?

762
00:33:00,510 --> 00:33:03,000
Ben, supoño que agora enfileirar
17 tamén.

763
00:33:03,000 --> 00:33:04,510
Entón hop en liña alí.

764
00:33:04,510 --> 00:33:07,060
E, de novo, o tipo de porta ao
tenda estará aquí.

765
00:33:07,060 --> 00:33:08,700
Entón agora eu engade 17.

766
00:33:08,700 --> 00:33:10,810
E aínda que estes faces están bloqueando
da pantalla, que é OK,

767
00:33:10,810 --> 00:33:12,300
porque podemos velo aquí.

768
00:33:12,300 --> 00:33:12,910
Sentímolo.

769
00:33:12,910 --> 00:33:13,810
>> Audiencia: Podemos cambiar -

770
00:33:13,810 --> 00:33:14,660
>> DAVID Malan: Non, iso é OK.

771
00:33:14,660 --> 00:33:16,000
É enorme alí enriba.

772
00:33:16,000 --> 00:33:18,580
Así, é agora 17 dentro da cola.

773
00:33:18,580 --> 00:33:21,332
Eu teño actualizar o que
campos agora que?

774
00:33:21,332 --> 00:33:23,210
OK, en definitiva tamaño.

775
00:33:23,210 --> 00:33:26,430
E como a cabeza?

776
00:33:26,430 --> 00:33:27,040
OK, non.

777
00:33:27,040 --> 00:33:30,200
Fronte non debe cambiar, porque
a diferenza dunha pila,

778
00:33:30,200 --> 00:33:31,370
quere manter a equidade.

779
00:33:31,370 --> 00:33:35,150
Entón, se 9 quedou en primeiro lugar, queremos 9
para ser o primeiro en saír da liña

780
00:33:35,150 --> 00:33:36,420
e para a tenda.

781
00:33:36,420 --> 00:33:37,220
>> De feito, imos ver iso.

782
00:33:37,220 --> 00:33:42,235
Antes de inserir 22, imos
dalle dequeue 9.

783
00:33:42,235 --> 00:33:42,970
Cal é o seu nome?

784
00:33:42,970 --> 00:33:43,680
>> Audiencia: Jake.

785
00:33:43,680 --> 00:33:45,440
>> DAVID Malan: Jake vai
para ser será agora.

786
00:33:45,440 --> 00:33:48,050
Entón comeza a entrar na tenda.

787
00:33:48,050 --> 00:33:49,880
E finxir que a tenda
está alí.

788
00:33:49,880 --> 00:33:51,970
Entón, agora o que ten - dit-dit-dit!

789
00:33:51,970 --> 00:33:53,400
Que ten que pasar agora?

790
00:33:53,400 --> 00:33:54,490
Decisión de deseño.

791
00:33:54,490 --> 00:33:56,825
Entón, non é un mal instinto, pero -
cal é o seu nome?

792
00:33:56,825 --> 00:33:57,090
>> Audiencia: David.

793
00:33:57,090 --> 00:33:57,500
>> DAVID Malan: David.

794
00:33:57,500 --> 00:33:58,810
Entón, o que fixo David?

795
00:33:58,810 --> 00:34:02,590
Estaba intentando resolver de corrixir os datos
estrutura e movemento a partir da súa localización

796
00:34:02,590 --> 00:34:04,100
na antiga ubicación do Jake.

797
00:34:04,100 --> 00:34:06,740
E iso é bo, se estamos dispostos
para aceptar isto como unha

798
00:34:06,740 --> 00:34:08,199
detalle de implementación.

799
00:34:08,199 --> 00:34:11,100
Pero, primeiro, imos actualizar os datos
estrutura antes de facelo.

800
00:34:11,100 --> 00:34:14,139
Porque eu non estou gustando a idea de todo
a xente desprazando nesta liña.

801
00:34:14,139 --> 00:34:17,360
>> Non é gran cousa se David fai
un paso, pero, de novo, creo que volve

802
00:34:17,360 --> 00:34:20,360
cando tivemos oito voluntarios na
escenario e fixemos como inserción

803
00:34:20,360 --> 00:34:22,600
tipo, no que tivemos que comezar
movéndose a todos arredor.

804
00:34:22,600 --> 00:34:23,790
Isto ten cara, non?

805
00:34:23,790 --> 00:34:28,330
Isto faime encoller sobre o gran
de n, gran O de n ao cadrado de novo.

806
00:34:28,330 --> 00:34:30,650
Non está sentindo como
un resultado ideal.

807
00:34:30,650 --> 00:34:32,080
>> Entón imos actualizar isto.

808
00:34:32,080 --> 00:34:35,120
Así, o tamaño da cola
xa non é 2.

809
00:34:35,120 --> 00:34:37,090
Agora é simplemente un.

810
00:34:37,090 --> 00:34:40,360
Pero agora podo actualizar algo
Non actualizar antes, a

811
00:34:40,360 --> 00:34:41,130
cabeza da lista.

812
00:34:41,130 --> 00:34:45,420
Podería só dicir, é que unha situación?

813
00:34:45,420 --> 00:34:49,770
Polo tanto, agora temos valor de lixo aquí,
valor de lixo aquí, e David no

814
00:34:49,770 --> 00:34:51,469
medio dese lixo.

815
00:34:51,469 --> 00:34:54,980
Pero, a estrutura de datos
aínda está intacto.

816
00:34:54,980 --> 00:34:58,540
>> E, de feito, eu nin preciso
cambiar ex número un do Jake

817
00:34:58,540 --> 00:35:00,460
9, porque quen lle importa.

818
00:35:00,460 --> 00:35:04,470
Eu teño bastante información agora no
tamaño que sei que hai unha persoa en

819
00:35:04,470 --> 00:35:05,030
esa cola.

820
00:35:05,030 --> 00:35:08,340
E sei que esa persoa
está na posición 1, e non 0.

821
00:35:08,340 --> 00:35:09,760
Non estou contando.

822
00:35:09,760 --> 00:35:11,300
Así, un ben.

823
00:35:11,300 --> 00:35:13,410
Así, a estrutura de datos aínda é OK.

824
00:35:13,410 --> 00:35:14,330
>> Ben, o que ocorre?

825
00:35:14,330 --> 00:35:15,010
Imos enfileirar -

826
00:35:15,010 --> 00:35:15,370
cal é o seu nome?

827
00:35:15,370 --> 00:35:16,160
>> Audiencia: Callen.

828
00:35:16,160 --> 00:35:16,580
>> DAVID Malan: Callen.

829
00:35:16,580 --> 00:35:20,770
Imos enfileirar unha Callen, e
22 xa está na cola.

830
00:35:20,770 --> 00:35:22,300
Entón, agora o que ten que cambiar aquí?

831
00:35:22,300 --> 00:35:24,380
Fronte non vai
cambiar, obviamente.

832
00:35:24,380 --> 00:35:27,160
Tamaño vai pasar a ser 2 novo.

833
00:35:27,160 --> 00:35:31,590
E 22 acaba aquí, 9 aínda está presente,
pero é efectivamente un

834
00:35:31,590 --> 00:35:32,600
valor de lixo agora.

835
00:35:32,600 --> 00:35:35,910
É só un remanescente de Jake pasado.

836
00:35:35,910 --> 00:35:39,200
>> Entón agora o que pasa se
Eu desenfileirar David?

837
00:35:39,200 --> 00:35:41,560
Unha última operación, dequeue David.

838
00:35:41,560 --> 00:35:46,070
Poderiamos cambiar, pero propoño imos
facer tan pouco traballo como sexa posible.

839
00:35:46,070 --> 00:35:50,280
Agora a miña estrutura de datos vai
atrás en tamaño de 2 a 1.

840
00:35:50,280 --> 00:35:53,730
Pero a cabeza da cola
agora pasa a ser 2.

841
00:35:53,730 --> 00:35:56,640
Eu non teño cambiar estas cifras
pero só porque son

842
00:35:56,640 --> 00:35:58,230
só os valores de lixo.

843
00:35:58,230 --> 00:35:59,720
>> Pero, agora, o que pasa?

844
00:35:59,720 --> 00:36:03,280
Supoñamos que me enfileirar, 26?

845
00:36:03,280 --> 00:36:05,890
Eu sinto que eu pertenzo aquí.

846
00:36:05,890 --> 00:36:06,890
Entón, eu estou sendo enfileirado.

847
00:36:06,890 --> 00:36:08,760
Entón eu medio que pertenzo aquí.

848
00:36:08,760 --> 00:36:11,300
E aínda que non fai ben
apreciar este aspecto no escenario,

849
00:36:11,300 --> 00:36:15,075
porque temos moito espazo, eu debería
non estar aquí, por que?

850
00:36:15,075 --> 00:36:16,290
>> Audiencia: Está fóra dos límites.

851
00:36:16,290 --> 00:36:16,370
>> DAVID Malan: Correcto.

852
00:36:16,370 --> 00:36:16,940
Estou fóra dos límites.

853
00:36:16,940 --> 00:36:19,330
Eu indexado alén do
límites desta matriz.

854
00:36:19,330 --> 00:36:23,420
Realmente debería estar nun dos
tres localizacións posibles.

855
00:36:23,420 --> 00:36:25,150
Agora, onde é máis natural para ir?

856
00:36:25,150 --> 00:36:27,760
Propoño que alavancou
unha semana un truco.

857
00:36:27,760 --> 00:36:30,150
O operador mod, porcentaxe.

858
00:36:30,150 --> 00:36:36,850
Porque estou tecnicamente en pé
localización 3, pero fago 3 capacidade mod,

859
00:36:36,850 --> 00:36:40,250
para 3, un sinal de porcentaxe, 3 -

860
00:36:40,250 --> 00:36:40,970
capacidade é 3.

861
00:36:40,970 --> 00:36:41,720
¿Que é iso?

862
00:36:41,720 --> 00:36:43,700
Cal é o resto cando
dividir 3 por 3?

863
00:36:43,700 --> 00:36:44,070
0.

864
00:36:44,070 --> 00:36:48,140
>> Así que me pon foron Jake era,
o que é realmente bo.

865
00:36:48,140 --> 00:36:50,370
Entón, agora a posta en marcha
desa cousa vai

866
00:36:50,370 --> 00:36:51,250
ser un pouco de dor de cabeza.

867
00:36:51,250 --> 00:36:53,740
É realmente só unha liña
de dor de cabeza, de código.

868
00:36:53,740 --> 00:36:56,580
Pero polo menos agora hai lixo
valor aquí, pero hai dous

869
00:36:56,580 --> 00:36:57,910
ints lexítimos aquí.

870
00:36:57,910 --> 00:37:04,160
E eu afirmo que agora fixemos
exactamente o que cómpre facer, sempre que

871
00:37:04,160 --> 00:37:08,600
podemos cambiar o que Jake
valor sería 26.

872
00:37:08,600 --> 00:37:12,110
>> Agora temos información suficiente aínda
para manter a integridade

873
00:37:12,110 --> 00:37:13,060
esta estrutura de datos.

874
00:37:13,060 --> 00:37:17,160
Nós aínda estamos medio fóra de sorte cando nós
quere inserir catro ou máis Total

875
00:37:17,160 --> 00:37:20,740
elementos, pero podo polo menos facer moito
uso eficiente da presente constante

876
00:37:20,740 --> 00:37:21,740
tempo, en realidade.

877
00:37:21,740 --> 00:37:27,150
Non se preocupe con cambio
todos, como inclinación de David era.

878
00:37:27,150 --> 00:37:30,816
>> Calquera dúbida sobre pilas,
ou esta cola?

879
00:37:30,816 --> 00:37:32,184
>> Audiencia: É a razón pola cal
precisa de tamaño para que vostede sabe

880
00:37:32,184 --> 00:37:34,010
onde se ten unha persoa?

881
00:37:34,010 --> 00:37:34,770
>> DAVID Malan: Exactamente.

882
00:37:34,770 --> 00:37:38,230
Eu teño que saber o tamaño da matriz
por que eu teño que saber exactamente como

883
00:37:38,230 --> 00:37:41,940
Moitos deses valores son lexítimas,
e para que eu poida atopar onde colocar

884
00:37:41,940 --> 00:37:42,800
a seguinte persoa.

885
00:37:42,800 --> 00:37:43,300
Exactamente.

886
00:37:43,300 --> 00:37:44,580
O tamaño é -

887
00:37:44,580 --> 00:37:46,360
En realidade, nós non actualizar iso aínda.

888
00:37:46,360 --> 00:37:48,380
Eu me engadido aos 26 anos.

889
00:37:48,380 --> 00:37:51,760
O tamaño é agora, non un, senón dous.

890
00:37:51,760 --> 00:37:57,780
Entón, agora este feito me axuda a atopar o
cabeza de lista, o que non é 0, non

891
00:37:57,780 --> 00:37:59,250
1, pero é 2.

892
00:37:59,250 --> 00:38:01,665
A parte dianteira da lista
é de feito o número 22.

893
00:38:01,665 --> 00:38:05,120
Porque quedou en primeiro lugar, polo que debe
ser autorizados a entrar na tenda antes de min,

894
00:38:05,120 --> 00:38:08,780
malia visual estou
máis preto da tenda.

895
00:38:08,780 --> 00:38:09,220
>> Todo ben?

896
00:38:09,220 --> 00:38:12,410
Unha salva de palmas para estes faces
e nós imos deixar los de alí.

897
00:38:12,410 --> 00:38:17,090
>> [Aplausos]

898
00:38:17,090 --> 00:38:18,150
>> DAVID Malan: eu podería deixar
manteña a bandexa.

899
00:38:18,150 --> 00:38:20,760
Puidemos ver o que pasa se
quere, pero quizais non.

900
00:38:20,760 --> 00:38:21,590
Todo ben.

901
00:38:21,590 --> 00:38:25,380
Entón, o que agora é que iso nos deixa?

902
00:38:25,380 --> 00:38:28,900
Ben, deixe-me propor que hai un
algunhas outras estruturas de datos que poderían

903
00:38:28,900 --> 00:38:33,810
comezar a engadir ao noso kit de ferramentas que van
realmente ser moi, moi relevante como

904
00:38:33,810 --> 00:38:35,270
nós mergullo cousas web.

905
00:38:35,270 --> 00:38:38,150
Que á súa vez, ten algún tipo de conexión
a árbores, baixo a forma de

906
00:38:38,150 --> 00:38:40,550
algo chamado DOM, documento
modelo de obxecto.

907
00:38:40,550 --> 00:38:42,370
Pero imos ver máis de
que en pouco tempo.

908
00:38:42,370 --> 00:38:46,260
>> Déixeme propoñer que por definición
chamar árbore agora o que se pode saber como

909
00:38:46,260 --> 00:38:48,820
máis dunha árbore de familia, onde
ter algún antepasado en

910
00:38:48,820 --> 00:38:49,790
raíces da árbore.

911
00:38:49,790 --> 00:38:54,480
A matriarca patriarcal ou na
o cumio da árbore.

912
00:38:54,480 --> 00:38:56,700
Sen o seu cónxuxe, neste caso.

913
00:38:56,700 --> 00:39:00,940
Pero agora temos que chamaremos
nenos, que son os nós que penden

914
00:39:00,940 --> 00:39:05,480
fóra o fillo esquerdo ou o dereito do neno,
frechas como descrito aquí.

915
00:39:05,480 --> 00:39:10,490
>> Noutras palabras, unha estrutura de datos en árbore
en ordenador, unha árbore ten cero

916
00:39:10,490 --> 00:39:11,480
ou máis nós.

917
00:39:11,480 --> 00:39:13,500
Se ten polo menos un nodo,
que se chama raíz.

918
00:39:13,500 --> 00:39:15,700
É as cousas visualmente que
trazamos na parte superior.

919
00:39:15,700 --> 00:39:20,280
E este nodo, como calquera outro no, pode
ter cero, unha ou dúas, ou tres,

920
00:39:20,280 --> 00:39:23,600
ou cantos fillos o
estrutura de datos soporta.

921
00:39:23,600 --> 00:39:29,150
Neste caso, a raíz, o almacenamento
valor un, ten dous fillos, 2 e 3,

922
00:39:29,150 --> 00:39:33,020
así que normalmente chamamos 2 á esquerda
neno e 3 o neno correcta.

923
00:39:33,020 --> 00:39:36,940
>> E entón, cando chegamos a 5, 6 e
7, 6 pode ser chamado o fillo do medio.

924
00:39:36,940 --> 00:39:38,940
Se ten catro fillos,
el queda confuso.

925
00:39:38,940 --> 00:39:42,260
Entón, deixe de usar este tipo
de acceso verbalmente.

926
00:39:42,260 --> 00:39:44,580
Pero é realmente só unha árbore xenealóxica.

927
00:39:44,580 --> 00:39:48,880
E as follas aquí son os nós que
eles mesmos non teñen fillos.

928
00:39:48,880 --> 00:39:52,540
Fican fóra da parte inferior da árbore.

929
00:39:52,540 --> 00:39:56,940
>> Entón, como podemos implementar unha árbore que
ten só dous fillos maxima?

930
00:39:56,940 --> 00:39:58,410
Imos chamalo dunha árbore binaria.

931
00:39:58,410 --> 00:40:00,960
Bi novo significando dous, neste
caso, como co binario.

932
00:40:00,960 --> 00:40:04,830
E, polo tanto, pode ter cero, unha
ou os dous fillos maxima.

933
00:40:04,830 --> 00:40:08,650
>> Vou propoñer que imos aplicar o no
a esta estrutura, cun int n,

934
00:40:08,650 --> 00:40:11,910
e logo, dous enlaces, un chamado
á esquerda, un chamado á dereita.

935
00:40:11,910 --> 00:40:14,830
Pero estes son só bo
convencións arbitrarias.

936
00:40:14,830 --> 00:40:18,170
E o que é bo momento, especialmente se
tipo de dificultade conceptual con

937
00:40:18,170 --> 00:40:21,300
recursão, ou pensar que non era
realmente unha solución a nada,

938
00:40:21,300 --> 00:40:23,120
especialmente se puidese
sen memoria.

939
00:40:23,120 --> 00:40:26,600
Agora que estamos a falar de datos
estruturas e algoritmos que permiten

940
00:40:26,600 --> 00:40:31,030
nos a atravesar e manipula-los,
Acontece que a recursividade volta en

941
00:40:31,030 --> 00:40:34,240
unha moito máis atractivo
se non é bo camiño.

942
00:40:34,240 --> 00:40:38,670
>> Entón, iso eu propoño é a implementación
dunha función de investigación.

943
00:40:38,670 --> 00:40:39,870
Dadas dúas entradas -

944
00:40:39,870 --> 00:40:41,570
polo que pense nisto como unha caixa negra.

945
00:40:41,570 --> 00:40:46,560
Dadas dúas entradas, N, un int, e un
punteiro para unha árbore, un punteiro para unha

946
00:40:46,560 --> 00:40:50,020
no, ou realmente a raíz dunha árbore, eu
alegación de que esta función pode volver

947
00:40:50,020 --> 00:40:53,530
verdadeira ou falsa, isto valor n
É dentro desta árbore.

948
00:40:53,530 --> 00:40:55,210
>> O que ten dentro desa caixa negra?

949
00:40:55,210 --> 00:40:57,440
Así, catro ramas.

950
00:40:57,440 --> 00:40:58,385
O primeiro só verifica.

951
00:40:58,385 --> 00:41:00,490
Se a árbore é nula, simplemente voltar falso.

952
00:41:00,490 --> 00:41:04,580
Se non o houbera ningún nodo, non hai n,
non hai ningún número, só volverá false.

953
00:41:04,580 --> 00:41:12,330
Se, con todo, n, o valor que está a buscar
a, é menor que a árbore frecha ne

954
00:41:12,330 --> 00:41:15,180
só para quedar claro, o que quere dicir cando
Escribo árbore e, a continuación, a frecha

955
00:41:15,180 --> 00:41:18,150
notación, n?

956
00:41:18,150 --> 00:41:18,690
Exactamente.

957
00:41:18,690 --> 00:41:21,970
Isto significa que desreferenciava
punteiro chamado árbore.

958
00:41:21,970 --> 00:41:26,750
Vaia alí, e, a continuación, entrar dentro que
nó e conseguir o seu campo chamado n.

959
00:41:26,750 --> 00:41:30,810
E, a continuación, comparar o n real que se
pasou para Investigación contra el.

960
00:41:30,810 --> 00:41:35,390
>> Así, se n é menor que o valor n
no propio nodo da árbore, así,

961
00:41:35,390 --> 00:41:36,720
O que significa isto?

962
00:41:36,720 --> 00:41:40,690
Iso non significa nada a primeira vista.

963
00:41:40,690 --> 00:41:40,900
Non?

964
00:41:40,900 --> 00:41:45,560
Así como cando ten un conxunto de
valores, pode gusta de aplicar binario

965
00:41:45,560 --> 00:41:48,290
investigación como unha forma de división
e conquistar.

966
00:41:48,290 --> 00:41:51,790
Pero o presuposto de que necesitamos facer
para investigación binaria para traballar en conxunto

967
00:41:51,790 --> 00:41:54,510
no libro de teléfono e
exemplos anteriores?

968
00:41:54,510 --> 00:41:55,530
>> Como ser clasificados.

969
00:41:55,530 --> 00:41:59,490
Entón, imos refinar a definición de árbore
aquí para non ser só unha árbore, que pode

970
00:41:59,490 --> 00:42:00,880
ter calquera número de fillos.

971
00:42:00,880 --> 00:42:04,700
Non é só unha árbore binaria, o que pode
ter 0, 1 ou 2 maxima.

972
00:42:04,700 --> 00:42:09,700
Pero, como unha árbore de busca binaria, ou CEST,
que é só un xeito elegante de dicir a

973
00:42:09,700 --> 00:42:15,430
árbore binaria de xeito que de cada nodo
fillo esquerdo, presente, é

974
00:42:15,430 --> 00:42:16,830
menos que o nó.

975
00:42:16,830 --> 00:42:20,170
Correo neno o dereito de cada nó,
se está presente, é máis grande

976
00:42:20,170 --> 00:42:21,740
do que o propio nó.

977
00:42:21,740 --> 00:42:25,200
>> Polo tanto, noutras palabras, se fose deseñar
a saída da árbore, as cifras son

978
00:42:25,200 --> 00:42:30,620
coidadosamente equilibrado como este, para que se
ten 55 como a raíz, de 33 anos pode ir

979
00:42:30,620 --> 00:42:33,090
á súa esquerda, xa que é inferior a 55.

980
00:42:33,090 --> 00:42:36,430
77 pode ir ao seu dereito, xa que
é superior a 55.

981
00:42:36,430 --> 00:42:40,750
Pero, agora, entender, a mesma definición,
é unha definición recursiva verbalmente,

982
00:42:40,750 --> 00:42:42,600
cómpre pedir 33.

983
00:42:42,600 --> 00:42:47,610
33 do fillo esquerdo debe ser menor que,
e dereito do neno de 33, 44, debe ser

984
00:42:47,610 --> 00:42:48,580
maior que iso.

985
00:42:48,580 --> 00:42:51,670
>> Polo tanto, esta é unha árbore de busca binaria, e
Propoño, usando un pouco de

986
00:42:51,670 --> 00:42:53,910
recursão, agora podemos atopar n.

987
00:42:53,910 --> 00:42:59,160
Así, se n é menor que o valor de n, que é
No actual, eu estou indo a ir

988
00:42:59,160 --> 00:43:04,090
adiante e punto, por así dicir, e só
devolver calquera que sexa a resposta é de

989
00:43:04,090 --> 00:43:08,470
busca de n en
fillo esquerdo da árbore.

990
00:43:08,470 --> 00:43:11,370
Teña en conta unha vez máis, esta función só
espera unha estrela no, un

991
00:43:11,370 --> 00:43:12,780
punteiro para un nó.

992
00:43:12,780 --> 00:43:17,360
Entón, por suposto eu só podo facer árbore
frecha para a esquerda, o que levará

993
00:43:17,360 --> 00:43:18,400
me a outro nodo.

994
00:43:18,400 --> 00:43:19,480
Pero o que é este nó?

995
00:43:19,480 --> 00:43:22,820
>> Ben, de acordo con esta declaración,
esquerda é só un punteiro, de xeito que só

996
00:43:22,820 --> 00:43:27,090
Significa que eu estou pasando para a función de busca
un indicador diferente, en particular

997
00:43:27,090 --> 00:43:30,750
o que supón un
árbore do meu fillo esquerdo.

998
00:43:30,750 --> 00:43:36,040
Polo tanto, neste caso, o punteiro a 33, se
esta é a nosa mostra de entrada obstante, se

999
00:43:36,040 --> 00:43:40,740
n é maior que o valor de n en
No actual na árbore, entón eu estou

1000
00:43:40,740 --> 00:43:43,370
indo a ir adiante e punto na outra
dirección e dicir, eu non

1001
00:43:43,370 --> 00:43:47,280
sabe se este valor n está na árbore,
pero eu sei que si é, é a miña

1002
00:43:47,280 --> 00:43:49,090
sector dereito, por así dicir.

1003
00:43:49,090 --> 00:43:53,120
Entón deixe-me chamar recursivamente buscar,
pasar un n de novo, pero pasando unha

1004
00:43:53,120 --> 00:43:54,580
punteiro para o meu fillo dereito.

1005
00:43:54,580 --> 00:44:00,020
>> Noutras palabras, se eu estou actualmente en 55
e eu estou buscando 99, sei que 99

1006
00:44:00,020 --> 00:44:04,270
é maior que 55, entón como eu Rompín
o libro de teléfono desde hai semanas e nós

1007
00:44:04,270 --> 00:44:07,140
foi á dereita, do mesmo xeito somos nós
Vai estar ben aquí.

1008
00:44:07,140 --> 00:44:11,960
E eu non sei se é a miña dereita
neno, e non é, de 77 está aí, pero

1009
00:44:11,960 --> 00:44:13,210
Sei que é nesa dirección.

1010
00:44:13,210 --> 00:44:18,770
Entón, eu chamo de busca no meu fillo dereito,
77, e que a figura de investigación a partir

1011
00:44:18,770 --> 00:44:24,950
alí se 99 deste arbitraria
exemplo é realmente alí.

1012
00:44:24,950 --> 00:44:26,900
>> Senón, o que é o caso final?

1013
00:44:26,900 --> 00:44:28,620
Se a árbore é nula é un caso.

1014
00:44:28,620 --> 00:44:31,890
Se non for menor que a corrente do nodo
valor é outro caso.

1015
00:44:31,890 --> 00:44:35,120
Se n é maior que o actual
valor do nodo é un terceiro caso.

1016
00:44:35,120 --> 00:44:38,250
Qué é o cuarto e último caso?

1017
00:44:38,250 --> 00:44:39,480
Creo que estamos fóra dos casos, non?

1018
00:44:39,480 --> 00:44:44,690
Debe ser, no que n é o
nodo actual que estou.

1019
00:44:44,690 --> 00:44:49,640
>> Entón, se eu estou buscando 55 neste momento
na historia, ese sector da

1020
00:44:49,640 --> 00:44:51,780
árbore volvería verdade.

1021
00:44:51,780 --> 00:44:55,380
Entón, o que é interesante aquí é que nós
en realidade, a diferenza de semana pasado, nós medio

1022
00:44:55,380 --> 00:44:56,740
de ter dous casos base.

1023
00:44:56,740 --> 00:44:58,300
E eles non teñen a
estar na parte superior.

1024
00:44:58,300 --> 00:45:01,390
O principio é un caso base, porque se o
árbore é nulo, non hai nada que facer.

1025
00:45:01,390 --> 00:45:03,410
Só ten que voltar un disco codificado
valor false.

1026
00:45:03,410 --> 00:45:07,400
>> A rama inferior é unha especie de
defecto, polo cal se teña comprobado para

1027
00:45:07,400 --> 00:45:11,550
nulo, temos comprobado que debe ser
á esquerda, pero non debe ser, temos

1028
00:45:11,550 --> 00:45:14,640
Comprobarase se debe estar seguro, pero
non debe ser, claro, ten que ser

1029
00:45:14,640 --> 00:45:15,870
exactamente onde estamos.

1030
00:45:15,870 --> 00:45:16,780
Isto é un caso base.

1031
00:45:16,780 --> 00:45:19,920
Polo tanto, hai dous casos recursivas
entalado alí no medio.

1032
00:45:19,920 --> 00:45:21,630
Pero eu podería escribir
isto en calquera orde.

1033
00:45:21,630 --> 00:45:24,520
Eu só penso que tipo de pareceume natural
primeiro comprobar un posible erro,

1034
00:45:24,520 --> 00:45:28,340
a continuación, comproba a esquerda, a continuación, asegúrese de ben, entón
supoñer que está no nodo

1035
00:45:28,340 --> 00:45:30,630
está realmente a buscar.

1036
00:45:30,630 --> 00:45:36,240
>> Entón, por que isto pode ser útil?

1037
00:45:36,240 --> 00:45:37,910
Así, verifica-se -

1038
00:45:37,910 --> 00:45:42,110
e deixe-me ir a un teaser
aquí que está na web.

1039
00:45:42,110 --> 00:45:44,920
Nós imos comezar a usar non é unha
linguaxe de programación en principio, pero a

1040
00:45:44,920 --> 00:45:46,030
linguaxe de reserva.

1041
00:45:46,030 --> 00:45:48,740
A linguaxe de marcación que é ser un
similares en espírito á programación

1042
00:45:48,740 --> 00:45:51,715
linguaxe, pero el non lle dá o
capacidade de expresarse de forma lóxica.

1043
00:45:51,715 --> 00:45:55,070
El só lle dá a capacidade de
expresar-se estruturalmente.

1044
00:45:55,070 --> 00:45:57,960
>> Onde quere poñer algo
na páxina, a páxina web?

1045
00:45:57,960 --> 00:45:59,200
Cal é a cor que quere facer isto?

1046
00:45:59,200 --> 00:46:00,950
O tamaño do tipo de letra que quere facer isto?

1047
00:46:00,950 --> 00:46:02,970
Que palabras o que realmente
quere na páxina web?

1048
00:46:02,970 --> 00:46:04,060
Así que esta é unha linguaxe de marcación.

1049
00:46:04,060 --> 00:46:07,690
Pero, entón, imos presentar moi rapidamente
JavaScript, que é un verdadeiro

1050
00:46:07,690 --> 00:46:08,560
linguaxe de programación.

1051
00:46:08,560 --> 00:46:12,530
Moi semellante sintaticamente no aspecto
a C, pero vai ter un

1052
00:46:12,530 --> 00:46:15,200
bo, máis potente, máis
características de fácil utilización.

1053
00:46:15,200 --> 00:46:18,050
>> E unha das frustracións neste
punto no semestre é que imos

1054
00:46:18,050 --> 00:46:22,065
pronto aplicar Speller en moito menos
liñas de código, utilizando outras linguaxes

1055
00:46:22,065 --> 00:46:25,580
que a propia C permite, pero por motivo de
en breve imos entender.

1056
00:46:25,580 --> 00:46:27,750
Este será o primeiro nesta páxina web.

1057
00:46:27,750 --> 00:46:30,120
Será completamente por baixo do esperado,
o primeiro que facemos.

1058
00:46:30,120 --> 00:46:31,400
Vai simplemente dicir: Ola mundo.

1059
00:46:31,400 --> 00:46:34,010
Pero se nunca viu
antes, este é HTML,

1060
00:46:34,010 --> 00:46:35,670
HyperText Markup Language.

1061
00:46:35,670 --> 00:46:39,310
>> Se vai a unha determinada opción de menú
máis calquera navegador, en calquera páxina web en

1062
00:46:39,310 --> 00:46:43,160
a Internet, podes ver o HTML
que algunhas persoas escribiron para

1063
00:46:43,160 --> 00:46:44,400
crear esta páxina web.

1064
00:46:44,400 --> 00:46:47,850
E probablemente non parece tan
breve ou tan puro coma este.

1065
00:46:47,850 --> 00:46:51,400
Pero vai seguir o estándar destes
corchetes abertos e barras e

1066
00:46:51,400 --> 00:46:53,660
letras e números. potencialmente

1067
00:46:53,660 --> 00:46:56,770
>> Penso en darlle un teaser
do que vai ser capaz de facer

1068
00:46:56,770 --> 00:46:57,950
despois de tomar CS50.

1069
00:46:57,950 --> 00:47:02,620
Déixeme ir cs.harvard.edu / roubo,
páxina de inicio nosa propia Rob Bowden.

1070
00:47:02,620 --> 00:47:06,080
Fíxoo por nós.

1071
00:47:06,080 --> 00:47:07,490
Así, en breve vai ser capaz de facelo.

1072
00:47:07,490 --> 00:47:10,660
E tamén, o que escoitou
esta mañá -

1073
00:47:10,660 --> 00:47:12,480
o que escoitou esta mañá -

1074
00:47:12,480 --> 00:47:13,780
>> [Hamster baile music]

1075
00:47:13,780 --> 00:47:15,702
>> - Será capaz de facer isto.

1076
00:47:15,702 --> 00:47:16,790
Que nos espera o mércores.

1077
00:47:16,790 --> 00:47:17,791
Imos velo axiña.

1078
00:47:17,791 --> 00:47:22,950
>> [Hamster baile music]

1079
00:47:22,950 --> 00:47:24,300
DAVID Malan: Na seguinte CS50 -

1080
00:47:24,300 --> 00:47:31,670