1
00:00:00,000 --> 00:00:03,423
>> [Música tocando]

2
00:00:03,423 --> 00:00:05,380

3
00:00:05,380 --> 00:00:08,210
>> ANDI Pengo: Benvido á semana 6 da sección.

4
00:00:08,210 --> 00:00:11,620
Nós desviado o noso patrón
tempo sección deste martes

5
00:00:11,620 --> 00:00:14,130
tarde para esta linda mañá de domingo.

6
00:00:14,130 --> 00:00:17,330
Grazas por todos os que
uniuse a min hoxe, pero en serio,

7
00:00:17,330 --> 00:00:18,170
unha salva de palmas.

8
00:00:18,170 --> 00:00:20,600
>> Isto é un ben grande esforzo.

9
00:00:20,600 --> 00:00:23,600
Eu case non mesmo facelo
Se o tempo, pero foi Aceptar.

10
00:00:23,600 --> 00:00:27,520
Entón eu sei que todos vós
que acaba de facer-lo para o quiz.

11
00:00:27,520 --> 00:00:30,370
Primeiro de todo, benvido ao
a outra cara disto.

12
00:00:30,370 --> 00:00:32,917
>> En segundo lugar, imos falar sobre iso.

13
00:00:32,917 --> 00:00:34,000
Imos falar sobre o quiz.

14
00:00:34,000 --> 00:00:35,700
Imos falar sobre como
está facendo na clase.

15
00:00:35,700 --> 00:00:36,550
Vai estar ben.

16
00:00:36,550 --> 00:00:39,080
Teño súas probas para
vostede a finais de aquí,

17
00:00:39,080 --> 00:00:42,120
por iso, se vostedes queren tomar
un ollar para el, totalmente ben.

18
00:00:42,120 --> 00:00:46,590
>> Entón, rapidamente, antes de comezar, o
axenda para hoxe é o seguinte.

19
00:00:46,590 --> 00:00:48,430
Como verás, estamos
queima basicamente rápida

20
00:00:48,430 --> 00:00:52,120
través de unha chea de estruturas de datos
realmente, realmente, realmente rápido.

21
00:00:52,120 --> 00:00:54,380
Así, como tal, non será
hoxe de super interactivo.

22
00:00:54,380 --> 00:00:59,620
Vai ser só me especie de berrar
cousas que, e se eu confundir-lo,

23
00:00:59,620 --> 00:01:02,680
se estou indo demasiado rápido, deixe-me saber.

24
00:01:02,680 --> 00:01:05,200
Son só diferentes datos
estruturas, e como parte

25
00:01:05,200 --> 00:01:07,070
do seu pset para este
semana, vai

26
00:01:07,070 --> 00:01:10,340
ser solicitada para aplicar un deles,
quizais dúas eles-- dous deles

27
00:01:10,340 --> 00:01:12,319
na súa pset.

28
00:01:12,319 --> 00:01:14,610
OK, entón eu estou indo só para
comezar con algúns anuncios.

29
00:01:14,610 --> 00:01:19,070
Nós imos pasar por riba de pilas e colas máis en
profundidade do que o que fixemos antes do quiz.

30
00:01:19,070 --> 00:01:20,990
Nós imos pasar por riba conectado
lista de novo, unha vez máis,

31
00:01:20,990 --> 00:01:23,899
máis en profundidade que o que
tivemos antes do quiz.

32
00:01:23,899 --> 00:01:26,440
E entón nós imos falar sobre haxix
mesas, árbores e intentos, que

33
00:01:26,440 --> 00:01:28,890
son todos moi necesario para o seu pset.

34
00:01:28,890 --> 00:01:32,925
E entón nós imos pasar por riba de algúns
consellos útiles para pset5.

35
00:01:32,925 --> 00:01:37,360
>> OK, entón cuestionario 0.

36
00:01:37,360 --> 00:01:41,090
A media era de 58%.

37
00:01:41,090 --> 00:01:45,370
Foi moi baixa, e así vós todos
fixo moi, moi ben, segundo

38
00:01:45,370 --> 00:01:46,510
con iso.

39
00:01:46,510 --> 00:01:49,970
>> Moi ben, regra de ouro é se está
dentro dun desvío estándar da media

40
00:01:49,970 --> 00:01:52,990
especialmente xa que estamos nun salvo
sección de confort, está totalmente ben.

41
00:01:52,990 --> 00:01:54,120
Está no camiño certo.

42
00:01:54,120 --> 00:01:55,190
A vida é boa.

43
00:01:55,190 --> 00:01:58,952
>> Sei que é asustado pensar que
Eu teño como un 40% neste quiz.

44
00:01:58,952 --> 00:02:00,160
Vou sair clase.

45
00:02:00,160 --> 00:02:02,243
Eu prometer a vostede, non está
vai fallar a clase.

46
00:02:02,243 --> 00:02:03,680
Está totalmente ben.

47
00:02:03,680 --> 00:02:06,850
>> Para aqueles de vostedes que teño máis
a media, impresionante, impresionante,

48
00:02:06,850 --> 00:02:08,780
como, en serio ben feito.

49
00:02:08,780 --> 00:02:09,689
Eu telos comigo.

50
00:02:09,689 --> 00:02:11,730
Sinto-se libre para vir buscalos
ao final da sección.

51
00:02:11,730 --> 00:02:14,520
Deixe-me saber se tes calquera
cuestións, preguntas con eles.

52
00:02:14,520 --> 00:02:17,204
Se sumarmos a súa puntuación
mal, deixe-nos saber.

53
00:02:17,204 --> 00:02:21,240
>> OK, entón pset5, este é realmente un
semana estraño para Yale no sentido

54
00:02:21,240 --> 00:02:24,240
que a nosa pset débese
Mércores ao mediodía, incluíndo

55
00:02:24,240 --> 00:02:27,317
o día de atraso, polo que é, en realidade,
teoricamente debido martes ao mediodía.

56
00:02:27,317 --> 00:02:29,150
Probablemente ninguén terminou
en martes ao mediodía.

57
00:02:29,150 --> 00:02:30,830
Isto é totalmente bo.

58
00:02:30,830 --> 00:02:33,700
Nós imos ter o horario de oficina
esta noite, así como na noite de onte.

59
00:02:33,700 --> 00:02:36,810
E todas as seccións desta semana vai
de feito, pode converter talleres,

60
00:02:36,810 --> 00:02:38,800
tan a gusto para pop en
calquera sección que quere,

61
00:02:38,800 --> 00:02:42,810
e eles van ser unha especie de mini-pset
talleres para axuda sobre iso.

62
00:02:42,810 --> 00:02:45,620
Así, como tal, esta é a única sección
onde estamos material didáctico.

63
00:02:45,620 --> 00:02:49,220
Todas as outras seccións centrarase
exclusivamente na axuda ao pset.

64
00:02:49,220 --> 00:02:50,146
Si?

65
00:02:50,146 --> 00:02:52,000
>> Audiencia: Onde están as horas de expediente?

66
00:02:52,000 --> 00:02:56,120
>> ANDI Pengo: Horario de atención
tonight-- Oh, boa pregunta.

67
00:02:56,120 --> 00:03:00,580
Eu creo que o horario de oficina esta noite
están en Teal ou en Commons.

68
00:03:00,580 --> 00:03:02,984
Se comprobar en liña CS50
e vai para o horario de expediente,

69
00:03:02,984 --> 00:03:05,650
debe haber un programa que
dille onde todos son.

70
00:03:05,650 --> 00:03:07,954
>> Sei tanto esta noite
ou mañá é cerceta,

71
00:03:07,954 --> 00:03:10,120
e eu creo que podemos ter
commons para a outra noite.

72
00:03:10,120 --> 00:03:11,020
Non estou seguro.

73
00:03:11,020 --> 00:03:11,700
Boa pregunta.

74
00:03:11,700 --> 00:03:14,430
Comprobe en CS50.

75
00:03:14,430 --> 00:03:18,780
>> Cool, calquera dúbida sobre o
programa para a próxima como tres días?

76
00:03:18,780 --> 00:03:21,690
Eu prometer a vostedes como David
Dito isto, esta é a parte superior do outeiro.

77
00:03:21,690 --> 00:03:23,050
Vostedes están case alí.

78
00:03:23,050 --> 00:03:24,644
Só tres máis días.

79
00:03:24,644 --> 00:03:26,310
Chegar alí, e entón todos nós imos descender.

80
00:03:26,310 --> 00:03:28,114
Nós imos ter un descanso agradable CS-free.

81
00:03:28,114 --> 00:03:28,780
Nós imos voltar.

82
00:03:28,780 --> 00:03:30,779
Imos mergullar na web
programación e desenvolvemento,

83
00:03:30,779 --> 00:03:35,150
cousas que son moi divertido comparación
para algúns dos outros Serie de exercicios.

84
00:03:35,150 --> 00:03:37,974
E vai ser frío, e
imos ter moita diversión.

85
00:03:37,974 --> 00:03:38,890
Teremos máis doces.

86
00:03:38,890 --> 00:03:39,730
Desculpem-me por doces.

87
00:03:39,730 --> 00:03:40,945
Esquecín de doces.

88
00:03:40,945 --> 00:03:43,310
Era unha mañá áspera.

89
00:03:43,310 --> 00:03:46,340
Entón vostedes están case alí,
e eu estou realmente orgulloso de vós.

90
00:03:46,340 --> 00:03:49,570
>> OK, entón apilar.

91
00:03:49,570 --> 00:03:53,331
Que amaba a pregunta sobre Jack
e as súas vestiduras a proba?

92
00:03:53,331 --> 00:03:53,830
Ninguén?

93
00:03:53,830 --> 00:03:56,500
OK, iso é bo.

94
00:03:56,500 --> 00:04:00,200
>> Entón, basicamente, como pode
imaxe de Jack, este cara aquí,

95
00:04:00,200 --> 00:04:03,350
Quere aproveitar a roupa
fóra do cumio da pila,

96
00:04:03,350 --> 00:04:05,750
e pon-lo de volta para
a pila despois que está feito.

97
00:04:05,750 --> 00:04:07,600
Así, deste xeito, nunca
parece estar quedando

98
00:04:07,600 --> 00:04:10,090
para a parte inferior da
apilar na súa roupa.

99
00:04:10,090 --> 00:04:12,600
Polo tanto, este tipo de describe
a estrutura de base de datos

100
00:04:12,600 --> 00:04:16,610
de como unha pila é aplicada.

101
00:04:16,610 --> 00:04:20,060
>> Esencialmente, pense en un
pila como calquera pila de obxectos

102
00:04:20,060 --> 00:04:24,900
onde poñer as cousas a arriba, e
entón pop-los para fóra do cumio.

103
00:04:24,900 --> 00:04:28,600
Entón LIFO é a sigla que nos gusta
para use-- último In, First Out.

104
00:04:28,600 --> 00:04:32,480
E así durar para arriba da
pila é o primeiro que sae.

105
00:04:32,480 --> 00:04:34,260
E así os dous termos
nos gusta de asociar

106
00:04:34,260 --> 00:04:36,190
que son chamados push e pop.

107
00:04:36,190 --> 00:04:39,790
Cando empurrar algo ao
pila, e poñer-la de volta.

108
00:04:39,790 --> 00:04:43,422
>> E entón eu creo que esta é unha especie de
concepto abstracto para aqueles de vostedes

109
00:04:43,422 --> 00:04:45,630
que queren ver como un
aplicación efectiva deste

110
00:04:45,630 --> 00:04:46,740
no mundo real.

111
00:04:46,740 --> 00:04:50,170
Como moitos de vostedes teñen escrito un ensaio
quizais como unha hora antes do vencemento,

112
00:04:50,170 --> 00:04:54,510
e excluíu accidentalmente un enorme
anaco del, como accidentalmente?

113
00:04:54,510 --> 00:04:58,560
E entón o que facer control
que usan para poñer-lo de volta?

114
00:04:58,560 --> 00:05:00,030
Control-Z, si?

115
00:05:00,030 --> 00:05:03,640
Control-Z, de xeito que a cantidade de veces
que Control-Z salvou a miña vida,

116
00:05:03,640 --> 00:05:08,820
salvo miña bunda, cada vez
que é aplicado a través dunha pila.

117
00:05:08,820 --> 00:05:13,020
>> Esencialmente toda a información
que está no seu documento de Word,

118
00:05:13,020 --> 00:05:15,080
é empurrado e bateu a gusto.

119
00:05:15,080 --> 00:05:19,460
E así, esencialmente, sempre que
eliminar calquera cousa, poñer-la de volta.

120
00:05:19,460 --> 00:05:22,820
E entón se precisa del de novo,
empurralo lo, que é o Control-C fai.

121
00:05:22,820 --> 00:05:26,770
E función mundo tan real
de estrutura de datos como simple

122
00:05:26,770 --> 00:05:28,690
pode axudar coa súa vida cotiá.

123
00:05:28,690 --> 00:05:31,710

124
00:05:31,710 --> 00:05:40,150
>> Así, un struct é o camiño que
realmente crear unha pila.

125
00:05:40,150 --> 00:05:44,720
Nós escriba definir struct, e, a continuación,
chamamos iso de pila na parte inferior.

126
00:05:44,720 --> 00:05:47,440
E dentro do conxunto,
temos dous parámetros

127
00:05:47,440 --> 00:05:51,580
que pode, esencialmente, manipular,
polo que temos de char capacidade cordas estrela.

128
00:05:51,580 --> 00:05:55,150
>> Todo o que está a facer
é a creación dunha matriz

129
00:05:55,150 --> 00:05:58,835
que pode almacenar o que queiras
que podemos determinar a súa capacidade.

130
00:05:58,835 --> 00:06:01,990
Capacidade é a cantidade máxima de
elementos que podemos poñer en esta matriz.

131
00:06:01,990 --> 00:06:05,660
tamaño int é o contador que mantén
o control de cantos elementos están actualmente

132
00:06:05,660 --> 00:06:07,850
na pila.

133
00:06:07,850 --> 00:06:11,860
Entón nós pode seguir, A,
tanto como gran a pila é real,

134
00:06:11,860 --> 00:06:14,850
e, B, canto desa pila
enchemos porque nós non queremos

135
00:06:14,850 --> 00:06:18,800
rebosar sobre o que é a nosa capacidade.

136
00:06:18,800 --> 00:06:24,340
>> Así, por exemplo, esta linda
pregunta era sobre o seu quiz.

137
00:06:24,340 --> 00:06:28,160
Esencialmente, como imos empurrar
sobre o cumio dunha pila.

138
00:06:28,160 --> 00:06:28,830
Moi sinxelo.

139
00:06:28,830 --> 00:06:30,621
Se ollar para el,
imos camiñar por este.

140
00:06:30,621 --> 00:06:32,640
Se [inaudível] size--
Teña en conta que, sempre que

141
00:06:32,640 --> 00:06:35,300
quere acceder calquera
parámetro dentro dunha estrutura,

142
00:06:35,300 --> 00:06:40,320
fai o nome do struct.parameter.

143
00:06:40,320 --> 00:06:42,720
>> Neste caso, s é
o nome da nosa stack.

144
00:06:42,720 --> 00:06:46,230
Queremos acceder ao tamaño
da mesma, polo que facemos s.size.

145
00:06:46,230 --> 00:06:50,280
Así, se o tamaño non é
igual capacidade ou desde

146
00:06:50,280 --> 00:06:52,940
xa que é menos que a capacidade,
quere ía traballar aquí.

147
00:06:52,940 --> 00:06:57,180
>> Quere acceder ao interior
do seu stack, entón s.strings,

148
00:06:57,180 --> 00:07:00,790
e está indo a poñer este novo número
que quere inserir alí.

149
00:07:00,790 --> 00:07:05,030
Nós só dicir que imos querer
inserir int n na pila,

150
00:07:05,030 --> 00:07:08,905
poderíamos facer s.strings,
corchetes, s.size iguala n.

151
00:07:08,905 --> 00:07:11,030
Porque o tamaño é onde nós
Están na pila

152
00:07:11,030 --> 00:07:14,590
se nós estamos indo a empurrar
Lo, nós só acceder

153
00:07:14,590 --> 00:07:17,370
onde queira que o tamaño sexa, o
plenitude corrente da pila,

154
00:07:17,370 --> 00:07:21,729
e nós empurrar o int n nel.

155
00:07:21,729 --> 00:07:24,770
E entón nós queremos estar seguro de que
tamén estamos incrementando tamaño do n,

156
00:07:24,770 --> 00:07:27,436
para que poidamos manter o control de nós temos
engadida unha cousa extra para a pila.

157
00:07:27,436 --> 00:07:29,660
Agora temos un tamaño maior.

158
00:07:29,660 --> 00:07:33,196
Será que isto aquí ten sentido
todos, loxicamente como funciona?

159
00:07:33,196 --> 00:07:34,160
Era unha especie de rápido.

160
00:07:34,160 --> 00:07:39,535

161
00:07:39,535 --> 00:07:42,160
Audiencia: Pode pasar por riba
os s.stringss.strings [s.size] de novo?

162
00:07:42,160 --> 00:07:45,808
ANDI Pengo: Correcto, entón o que fai
s.size actualmente dar?

163
00:07:45,808 --> 00:07:47,440
Audiencia: É o tamaño actual.

164
00:07:47,440 --> 00:07:50,890
ANDI Pengo: Exactamente, polo que a
índice actual que o noso tamaño é en,

165
00:07:50,890 --> 00:07:57,780
e por iso queremos poñer o novo enteiro
que queremos introducir s.size.

166
00:07:57,780 --> 00:07:58,760
Isto ten sentido?

167
00:07:58,760 --> 00:08:01,110
Porque s.strings, todo isto
é é o nome da matriz.

168
00:08:01,110 --> 00:08:03,510
Todo o que é acceder ao
matriz dentro da nosa estrutura,

169
00:08:03,510 --> 00:08:06,030
e así, se queremos
poña n en que o índice,

170
00:08:06,030 --> 00:08:09,651
podemos simplemente acceder a ela
utilizando soportes s.size.

171
00:08:09,651 --> 00:08:10,150
Legal.

172
00:08:10,150 --> 00:08:13,580

173
00:08:13,580 --> 00:08:18,916
>> Todo ben, pop, eu Pseudocódigo para fóra
para vós, pero concepto similar.

174
00:08:18,916 --> 00:08:19,790
Isto ten sentido?

175
00:08:19,790 --> 00:08:22,310
Se o tamaño é maior
que cero, entón

176
00:08:22,310 --> 00:08:25,350
sei que quere tomar algo
porque se o tamaño non é

177
00:08:25,350 --> 00:08:27,620
maior que cero, entón
ten nada na pila.

178
00:08:27,620 --> 00:08:29,840
>> Así, só quere executar
este código, el só pode

179
00:08:29,840 --> 00:08:32,320
pop se hai algo que estalar.

180
00:08:32,320 --> 00:08:35,830
Así, se o tamaño é maior
que 0, que menos o tamaño.

181
00:08:35,830 --> 00:08:40,020
Nós diminuír o tamaño e, a continuación, voltar
o que está dentro dela, porque

182
00:08:40,020 --> 00:08:42,710
estalado, queremos
acceso todo o que está almacenado

183
00:08:42,710 --> 00:08:45,694
no índice do cume da pila.

184
00:08:45,694 --> 00:08:46,610
Todo ten sentido?

185
00:08:46,610 --> 00:08:49,693
Se eu fixen convosco escribir isto,
se vós poder escribilo lo?

186
00:08:49,693 --> 00:08:52,029

187
00:08:52,029 --> 00:08:53,570
OK, podedes xogar con el.

188
00:08:53,570 --> 00:08:55,252
Non te preocupes se non obtelo.

189
00:08:55,252 --> 00:08:57,460
Non temos tempo para codificar
Lo hoxe, porque temos

190
00:08:57,460 --> 00:08:59,959
ten unha morea de estas estruturas
para percorrer, pero, esencialmente,

191
00:08:59,959 --> 00:09:02,214
pseudocódigo, moi, moi semellante ao empurrar.

192
00:09:02,214 --> 00:09:03,380
Só ten que seguir ao longo da lóxica.

193
00:09:03,380 --> 00:09:06,092
Asegúrese de que está accedendo todo o
características da súa estrutura correctamente.

194
00:09:06,092 --> 00:09:06,574
Si?

195
00:09:06,574 --> 00:09:09,282
>> Audiencia: Será que estes diapositivas e
esa cousa toda ser ata hoxe-ish?

196
00:09:09,282 --> 00:09:11,586
ANDI Pengo: Sempre, si.

197
00:09:11,586 --> 00:09:13,710
Vou tentar poñer
isto como unha hora despois.

198
00:09:13,710 --> 00:09:16,626
Vou enviar correo-e David, David vai
poñelas como unha hora despois diso.

199
00:09:16,626 --> 00:09:20,040

200
00:09:20,040 --> 00:09:25,470
>> OK, entón, a continuación, nos movemos para estoutro
estrutura de datos encantador chamada de cola.

201
00:09:25,470 --> 00:09:30,140
Como podedes ver aquí, un
cola, para os británicos entre nós,

202
00:09:30,140 --> 00:09:32,010
todo isto é unha liña.

203
00:09:32,010 --> 00:09:34,680
Así, a diferenza do que
Pensas que é unha pila,

204
00:09:34,680 --> 00:09:37,750
unha fila é o que
loxicamente que pensa que é.

205
00:09:37,750 --> 00:09:41,914
É realizado polas regras do FIFO,
que é first in, first out.

206
00:09:41,914 --> 00:09:43,705
Se é a primeira
un na liña, está

207
00:09:43,705 --> 00:09:46,230
que o primeiro
sae da liña.

208
00:09:46,230 --> 00:09:49,680
>> Entón, o que nos gusta chamar este
é dequeueing e enqueueing.

209
00:09:49,680 --> 00:09:52,380
Se queremos engadir algo
a nosa cola, nós enfileirar.

210
00:09:52,380 --> 00:09:55,690
Se queremos retirar da cola, ou tomar
algo lonxe, nós retirar da cola.

211
00:09:55,690 --> 00:10:03,350
>> Así mesmo sentido que somos tipo de
a creación de elementos de tamaño fixo que

212
00:10:03,350 --> 00:10:06,500
pode almacenar certa
cousas, pero nós tamén podemos

213
00:10:06,500 --> 00:10:10,100
pasar a onde estamos poñendo
parámetros dentro deles

214
00:10:10,100 --> 00:10:13,140
a base do que tipo de
funcionalidade que queremos.

215
00:10:13,140 --> 00:10:16,700
Entón, pilas, queriamos a última
un, N para ser o primeiro en saír.

216
00:10:16,700 --> 00:10:19,800
Cola é que queremos o primeiro
para ser o primeiro para fóra.

217
00:10:19,800 --> 00:10:22,510

218
00:10:22,510 --> 00:10:26,710
>> Así, o tipo struct
definir, como se pode ver,

219
00:10:26,710 --> 00:10:29,470
é un pouco diferente
desde o que foi a pila

220
00:10:29,470 --> 00:10:33,120
porque non só temos que manter
o control de onde o tamaño é actualmente,

221
00:10:33,120 --> 00:10:37,420
tamén queremos manter o control da cabeza
así como onde estamos actualmente.

222
00:10:37,420 --> 00:10:39,580
Entón, eu creo que é máis fácil
se eu sacar iso.

223
00:10:39,580 --> 00:10:53,270
Entón, imos imaxinar que temos unha fila,
entón imos dicir que a cabeza está ben aquí.

224
00:10:53,270 --> 00:10:55,811

225
00:10:55,811 --> 00:10:58,310
O xefe da liña, imos
só dicir que é actualmente alí,

226
00:10:58,310 --> 00:11:01,809
e queremos introducir
algo na cola.

227
00:11:01,809 --> 00:11:04,350
Vou chamar ao tamaño esencialmente
é o mesmo que a cola,

228
00:11:04,350 --> 00:11:06,314
o fin da cola é sempre que o seu.

229
00:11:06,314 --> 00:11:07,730
Nós só dicir que tamaño é aquí.

230
00:11:07,730 --> 00:11:14,380

231
00:11:14,380 --> 00:11:18,400
>> Así como un practicable
introducir algo nunha cola?

232
00:11:18,400 --> 00:11:21,000

233
00:11:21,000 --> 00:11:24,130
O índice queremos poñer
onde queremos inserir.

234
00:11:24,130 --> 00:11:29,320
Se este é o inicio da súa
cola e este é o fin de todo

235
00:11:29,320 --> 00:11:31,860
ou o tamaño del, onde é que imos
quere engadir o seguinte obxecto?

236
00:11:31,860 --> 00:11:32,920
>> Audiencia: [inaudível]

237
00:11:32,920 --> 00:11:35,920
ANDI Pengo: Exactamente, quere engadir
Lo dependendo escribiu el.

238
00:11:35,920 --> 00:11:37,840
Ou este é en branco ou que está baleiro.

239
00:11:37,840 --> 00:11:42,630
Entón quere engadir lo probablemente
aquí porque, se o tamaño é--

240
00:11:42,630 --> 00:11:50,540
se estes son todos completo, quere
engadir lo aquí, non?

241
00:11:50,540 --> 00:11:57,150
>> E así que é, á vez moi, moi
simple, non é ben sempre correcto

242
00:11:57,150 --> 00:12:00,690
porque a principal diferenza
entre unha cola e unha pila

243
00:12:00,690 --> 00:12:04,350
é que a cola pode
de feito, ser manipulado

244
00:12:04,350 --> 00:12:06,980
de xeito que os cambios de cabeza
dependendo de onde queiras

245
00:12:06,980 --> 00:12:08,650
o inicio da súa suxestión para comezar.

246
00:12:08,650 --> 00:12:11,900
E, como resultado, a súa cola
tamén vai cambiar.

247
00:12:11,900 --> 00:12:14,770
E entón bótalle un ollo
este código agora.

248
00:12:14,770 --> 00:12:18,620
Como vostedes tamén foron convidados a
escribir sobre o quiz, enqueue.

249
00:12:18,620 --> 00:12:22,580
Quizais nós imos falar a través por
a resposta era o que era.

250
00:12:22,580 --> 00:12:26,790
>> Eu non podía encaixar esta liña nun,
pero, esencialmente, este anaco de código

251
00:12:26,790 --> 00:12:29,030
debe estar nunha liña.

252
00:12:29,030 --> 00:12:30,140
Gastar como 30 segundos.

253
00:12:30,140 --> 00:12:33,000
Bótalle un ollo, e mira por que
esta é a forma que é.

254
00:12:33,000 --> 00:12:50,030

255
00:12:50,030 --> 00:12:55,420
>> Moi, moi semellante struct, moi, moi
estrutura semellante á do anterior

256
00:12:55,420 --> 00:12:58,090
apilar agás, quizais,
unha liña de código.

257
00:12:58,090 --> 00:13:01,190
E que unha liña de código
determina a funcionalidade.

258
00:13:01,190 --> 00:13:03,900
E iso realmente diferencia
unha fila dunha pila.

259
00:13:03,900 --> 00:13:18,510

260
00:13:18,510 --> 00:13:22,010
>> Quen queira tomar unha facada
para explicar por que ten

261
00:13:22,010 --> 00:13:24,980
ten esa cousa complicada aquí?

262
00:13:24,980 --> 00:13:27,845
Vemos o retorno do noso
marabilloso módulo amigo.

263
00:13:27,845 --> 00:13:31,020
Como vostedes virá logo
de recoñecer na programación,

264
00:13:31,020 --> 00:13:34,910
case en calquera momento precisas algo
para involucrar calquera cousa,

265
00:13:34,910 --> 00:13:36,850
módulo será a forma de facelo.

266
00:13:36,850 --> 00:13:40,510
Entón, sabendo que, alguén quere
para tratar de explicar esta liña de código?

267
00:13:40,510 --> 00:13:44,060

268
00:13:44,060 --> 00:13:47,507
Si, as respostas son
aceptado e benvido.

269
00:13:47,507 --> 00:13:48,840
Audiencia: Está falando comigo?

270
00:13:48,840 --> 00:13:49,506
ANDI Pengo: Si.

271
00:13:49,506 --> 00:13:56,200
Audiencia: Oh, non me desculpe.

272
00:13:56,200 --> 00:14:00,250
ANDI Pengo: OK, entón imos
camiñar por este código.

273
00:14:00,250 --> 00:14:03,642
Entón, cando está tentando
engadir algo nunha cola,

274
00:14:03,642 --> 00:14:08,510
no caso encantador que a cabeza pasa
para estar aquí, é moi doado para nós

275
00:14:08,510 --> 00:14:10,960
só para ir ata o final
introducir algo, non?

276
00:14:10,960 --> 00:14:14,690
Pero o punto enteiro dunha fila é
que a cabeza pode realmente dinamicamente

277
00:14:14,690 --> 00:14:17,280
cambiar, dependendo de onde nós
quere o inicio da nosa q ser,

278
00:14:17,280 --> 00:14:19,880
e, como tal, a cola
tamén vai cambiar.

279
00:14:19,880 --> 00:14:31,100
>> E así imaxinar que este non era o
cola, pero esta foi a cola.

280
00:14:31,100 --> 00:14:37,900

281
00:14:37,900 --> 00:14:39,330
Imos dicir que a cabeza está ben aquí.

282
00:14:39,330 --> 00:14:54,900

283
00:14:54,900 --> 00:14:56,980
Imos dicir que a nosa cola mirou como esta.

284
00:14:56,980 --> 00:15:00,190
Se quixésemos desprazarse onde
o inicio da liña é,

285
00:15:00,190 --> 00:15:03,400
imos dicir que cambiou cabeza
Deste xeito e tamaños aquí.

286
00:15:03,400 --> 00:15:07,100
>> Agora queremos engadir algo ao
esa cola, pero como podedes ver,

287
00:15:07,100 --> 00:15:11,150
non é tan sinxelo como só
engadir o que é despois do tamaño

288
00:15:11,150 --> 00:15:13,630
porque entón nós funcionan fóra do
límites da nosa matriz real.

289
00:15:13,630 --> 00:15:16,190
Onde queremos realmente é here.

290
00:15:16,190 --> 00:15:18,610
Esa é a beleza dunha fila
é que, para nós, visualmente

291
00:15:18,610 --> 00:15:22,380
Parece que a liña vai como esta,
pero cando gardada nunha estrutura de datos,

292
00:15:22,380 --> 00:15:29,370
eles dan-lo como como un ciclo.

293
00:15:29,370 --> 00:15:32,360
É o tipo de implica
á fronte do mesmo xeito

294
00:15:32,360 --> 00:15:34,780
que unha liña tamén pode envolve
en torno dependendo de onde queira que

295
00:15:34,780 --> 00:15:36,279
quere inicio da liña para ser.

296
00:15:36,279 --> 00:15:38,630
E por iso, se derme un
mirar para abaixo aquí, imos

297
00:15:38,630 --> 00:15:40,880
dicir que quería crear un
función chamada enqueue.

298
00:15:40,880 --> 00:15:43,980
Queriamos engadir int n en que q.

299
00:15:43,980 --> 00:15:49,250
Se q.size nós q-- chamaremos que os nosos datos
structure-- o noso queue.size non

300
00:15:49,250 --> 00:15:52,520
igual capacidade ou
é menos que a capacidade,

301
00:15:52,520 --> 00:15:55,120
q.strings é a matriz dentro da nosa q.

302
00:15:55,120 --> 00:15:58,380
Estamos indo para definir
que igual a q.heads,

303
00:15:58,380 --> 00:16:02,730
que é aquí, ademais de q.size
módulo pola capacidade que

304
00:16:02,730 --> 00:16:04,290
envolve-nos de volta por aquí.

305
00:16:04,290 --> 00:16:08,040
>> Así, neste exemplo, o índice de
de cabeza é un, non?

306
00:16:08,040 --> 00:16:11,480
O índice de tamaño é 0, 1, 2, 3, 4.

307
00:16:11,480 --> 00:16:19,500
Entón, podemos facer un módulo 4
pola nosa capacidade, que é 5.

308
00:16:19,500 --> 00:16:20,920
O que isto nos dá?

309
00:16:20,920 --> 00:16:23,270
Que o índice
sae desta?

310
00:16:23,270 --> 00:16:24,080
>> Audiencia: 0.

311
00:16:24,080 --> 00:16:27,870
>> ANDI Pengo: 0, que
pasa a ser aquí,

312
00:16:27,870 --> 00:16:30,640
e por iso queremos ser capaces
para introducir aquí.

313
00:16:30,640 --> 00:16:34,730
E así esta ecuación tipo aquí
de só funciona con todos os números

314
00:16:34,730 --> 00:16:36,750
dependendo de que o seu
cabeza eo seu tamaño é.

315
00:16:36,750 --> 00:16:38,541
Se sabe o que os
as cousas son, vostede sabe

316
00:16:38,541 --> 00:16:43,170
exactamente onde quere inserir
todo o que é despois da súa cola.

317
00:16:43,170 --> 00:16:44,640
Isto ten sentido para todos?

318
00:16:44,640 --> 00:16:48,560
>> Eu sei que tipo de un cerebro
provocación especialmente xa que este

319
00:16:48,560 --> 00:16:50,512
veu tras o seu quiz.

320
00:16:50,512 --> 00:16:52,220
Pero espero que todos
agora pode entender

321
00:16:52,220 --> 00:16:57,800
por iso que esta solución ou este
función é a forma que é.

322
00:16:57,800 --> 00:16:59,840
Calquera algo incerto sobre iso?

323
00:16:59,840 --> 00:17:03,471

324
00:17:03,471 --> 00:17:03,970
Aceptar.

325
00:17:03,970 --> 00:17:07,109

326
00:17:07,109 --> 00:17:09,970
>> E agora, se
quería para retirar da cola, este

327
00:17:09,970 --> 00:17:15,240
é onde a nosa cabeza sería desprazando
porque se fósemos para retirar da cola,

328
00:17:15,240 --> 00:17:17,030
nós non aproveitar a fin de q.

329
00:17:17,030 --> 00:17:19,130
Queremos aproveitar a cabeza, non?

330
00:17:19,130 --> 00:17:24,260
Entón, como resultado, a cabeza vai cambiar,
e é por iso que cando enfileirar,

331
00:17:24,260 --> 00:17:26,800
ten que manter o control de
onde a súa cabeza eo seu tamaño

332
00:17:26,800 --> 00:17:29,450
son para poder introducir
para a posición correcta.

333
00:17:29,450 --> 00:17:32,740
>> E así, cando retirar da cola,
Eu tamén Pseudocódigo-lo.

334
00:17:32,740 --> 00:17:35,480
Sinto-se libre para se quere
o intento de codificación iso.

335
00:17:35,480 --> 00:17:36,980
Quere mover a cabeza, non?

336
00:17:36,980 --> 00:17:39,320
Se eu quixese para retirar da cola, eu
movería a cabeza sobre.

337
00:17:39,320 --> 00:17:40,800
Esta sería a cabeza.

338
00:17:40,800 --> 00:17:45,617
>> E o noso tamaño actual faría
restar porque xa non

339
00:17:45,617 --> 00:17:46,950
temos catro elementos na matriz.

340
00:17:46,950 --> 00:17:51,370
Nós só temos tres, e entón nós queremos
para voltar o que estaba almacenado dentro

341
00:17:51,370 --> 00:17:56,260
da cabeza porque queremos aproveitar esta
valor para fóra de modo moi similar ao do conxunto.

342
00:17:56,260 --> 00:17:58,010
Así está tomando
dun lugar distinto,

343
00:17:58,010 --> 00:18:01,770
e ten que volver a asignar o punteiro
a lugar diferente como resultado.

344
00:18:01,770 --> 00:18:03,890
Loxicamente, todos sigan?

345
00:18:03,890 --> 00:18:05,690
Gran.

346
00:18:05,690 --> 00:18:10,156
>> OK, entón imos falar un pouco
máis en profundidade sobre listas ligadas

347
00:18:10,156 --> 00:18:13,280
que vai ser moi, moi valioso
para que no transcurso desta semana

348
00:18:13,280 --> 00:18:14,964
Serie de exercicios.

349
00:18:14,964 --> 00:18:17,130
Listas ligadas, como vostedes
lembro, todos eles son

350
00:18:17,130 --> 00:18:22,570
son os nós que son nós de certa
valores de ambos un valor e un punteiro

351
00:18:22,570 --> 00:18:26,290
que están ligados entre si
por eses punteiros.

352
00:18:26,290 --> 00:18:29,880
E así, a estrutura de como
creamos un nó aquí é nós

353
00:18:29,880 --> 00:18:33,569
ten int n, que é o que quere
o valor nunha tenda ou cadea de n

354
00:18:33,569 --> 00:18:35,610
ou o que sexa
chama-lo, o carácter estrela n.

355
00:18:35,610 --> 00:18:41,482
Struct estrela no, que é o punteiro
que quere ter en cada nodo,

356
00:18:41,482 --> 00:18:43,690
vai ter que
punteiro punto cara ao lado.

357
00:18:43,690 --> 00:18:48,207

358
00:18:48,207 --> 00:18:50,040
Vai ter a cabeza
dunha lista ligada que está

359
00:18:50,040 --> 00:18:53,140
indo para ligar para o resto
os valores así por diante e así por diante

360
00:18:53,140 --> 00:18:55,290
ata que finalmente chegar ao final.

361
00:18:55,290 --> 00:18:58,040
E esta última nodo é só
indo para non ter un punteiro.

362
00:18:58,040 --> 00:18:59,952
Vai apuntar
null, e que, cando

363
00:18:59,952 --> 00:19:01,910
sabe que bateu o
final da lista ligada

364
00:19:01,910 --> 00:19:04,076
é cando o último punteiro
non apunta a algo.

365
00:19:04,076 --> 00:19:06,670

366
00:19:06,670 --> 00:19:10,990
>> Entón, nós estamos indo a ir un pouco máis en
profundidade acerca de como se faría posiblemente

367
00:19:10,990 --> 00:19:12,400
buscar unha lista ligada.

368
00:19:12,400 --> 00:19:15,460
Teña en conta que o que son algúns dos
inconvenientes das listas ligadas

369
00:19:15,460 --> 00:19:19,340
versículos unha matriz sobre investigacións.

370
00:19:19,340 --> 00:19:22,565
Unha matriz que poida busca binaria, pero
por que non pode facer iso nunha lista vinculada?

371
00:19:22,565 --> 00:19:26,834

372
00:19:26,834 --> 00:19:30,320
>> Audiencia: Porque están todos conectados,
pero non sei ben onde

373
00:19:30,320 --> 00:19:31,330
[Inaudível].

374
00:19:31,330 --> 00:19:34,600
>> ANDI Pengo: Si, exactamente por iso Lembre
que o brillo dunha matriz

375
00:19:34,600 --> 00:19:37,190
foi o feito de que tiñamos
memoria de acceso aleatorio onde

376
00:19:37,190 --> 00:19:41,580
se eu quería o valor do índice
seis, eu podería só dicir índice seis,

377
00:19:41,580 --> 00:19:42,407
dáme ese valor.

378
00:19:42,407 --> 00:19:45,240
E iso é porque as matrices son clasificadas
nun espazo contiguo de memoria

379
00:19:45,240 --> 00:19:48,020
nun só lugar, mentres que
tipo de listas ligadas

380
00:19:48,020 --> 00:19:52,820
son intercaladas aleatoriamente por todas partes,
ea única forma que pode atopar un

381
00:19:52,820 --> 00:19:56,890
é a través dun punteiro que lle di
a dirección de onde a seguinte nodo é.

382
00:19:56,890 --> 00:20:00,290
>> E así, como resultado, o único xeito
para buscar unha lista ligada

383
00:20:00,290 --> 00:20:01,560
é a procura lineal.

384
00:20:01,560 --> 00:20:05,890
Porque eu non sei exactamente onde
o valor 12º na lista ligada é,

385
00:20:05,890 --> 00:20:08,780
Teño que atravesar a totalidade
desa lista un conectado

386
00:20:08,780 --> 00:20:12,450
a un, da cabeza para o primeiro nodo,
para o segundo no, para o terceiro no,

387
00:20:12,450 --> 00:20:17,690
todo o camiño ata que finalmente chegar
onde este nodo eu estou buscando é.

388
00:20:17,690 --> 00:20:22,110
E así, neste sentido, busca
nunha lista ligada sempre n.

389
00:20:22,110 --> 00:20:23,040
Sempre n.

390
00:20:23,040 --> 00:20:25,690
Sempre en tempo lineal.

391
00:20:25,690 --> 00:20:28,470
>> E así o código en que
imos aplicar isto, e isto

392
00:20:28,470 --> 00:20:32,620
é un pouco novo para vostedes sempre que
caras realmente non teño falado ou nunca

393
00:20:32,620 --> 00:20:35,000
punteiros visto en como
buscar a través de punteiros,

394
00:20:35,000 --> 00:20:37,670
entón imos percorrer
esta moi, moi lentamente.

395
00:20:37,670 --> 00:20:40,200
Así, busca bool, dereito,
imos imaxinar que queremos

396
00:20:40,200 --> 00:20:42,820
para crear unha función chamada
investigación que retorna certo

397
00:20:42,820 --> 00:20:46,820
Se atopou un valor dentro do ligada
lista, e retorna false doutra forma.

398
00:20:46,820 --> 00:20:50,030
Lista estrela nodo é
Actualmente só o punteiro

399
00:20:50,030 --> 00:20:52,960
para o primeiro elemento na súa lista ligada.

400
00:20:52,960 --> 00:20:56,700
int n é o valor que está
buscando na lista.

401
00:20:56,700 --> 00:20:58,770
>> Entón punteiro estrela nó lista é igual.

402
00:20:58,770 --> 00:21:00,970
Isto significa que estamos establecendo
e creando un punteiro

403
00:21:00,970 --> 00:21:03,592
para que o primeiro nodo dentro da lista.

404
00:21:03,592 --> 00:21:04,300
Todos comigo?

405
00:21:04,300 --> 00:21:06,530
Entón, se tivésemos que ir
volver aquí, eu tería

406
00:21:06,530 --> 00:21:13,850
iniciar un punteiro que indica
o cabeza de todo o que é lista.

407
00:21:13,850 --> 00:21:18,600
>> E, a continuación, unha vez que chegar aquí,
mentres punteiro non é igual a null,

408
00:21:18,600 --> 00:21:22,160
de xeito que é o ciclo no que estamos
será, subsecuentemente, atravesando

409
00:21:22,160 --> 00:21:25,940
resto da nosa lista, xa que o que
ocorre cando o punteiro é igual a null?

410
00:21:25,940 --> 00:21:27,550
Sabemos que have--

411
00:21:27,550 --> 00:21:28,450
>> Audiencia: [inaudível]

412
00:21:28,450 --> 00:21:31,491
>> ANDI Pengo: Exactamente, polo que sabemos que
chegamos ao final da lista, non?

413
00:21:31,491 --> 00:21:34,470
Se volver aquí, cada nodo
debe estar apuntando a outro nodo

414
00:21:34,470 --> 00:21:36,550
e así por diante e así por diante
ata chegar finalmente

415
00:21:36,550 --> 00:21:41,589
a cola da lista ligada,
que ten un punteiro que

416
00:21:41,589 --> 00:21:43,130
non apunta calquera lugar que non.

417
00:21:43,130 --> 00:21:47,510
E para que vostede sabe que, basicamente,
súa lista aínda está alí enriba

418
00:21:47,510 --> 00:21:50,900
ata punteiro non é igual
nula porque unha vez que é igual a null,

419
00:21:50,900 --> 00:21:53,310
vostede sabe que non hai máis cousas.

420
00:21:53,310 --> 00:21:56,930
>> Entón ese é o ciclo no que estamos
terá a investigación real.

421
00:21:56,930 --> 00:22:01,690
E se os pointer-- ve
este tipo de función frecha alí?

422
00:22:01,690 --> 00:22:06,930
Polo tanto, se o punteiro apunta n, se
o punteiro na que n é igual é igual a N,

423
00:22:06,930 --> 00:22:09,180
de modo que significa que se
o punteiro que é

424
00:22:09,180 --> 00:22:13,420
buscando no extremo de cada
nodo é efectivamente igual ao valor

425
00:22:13,420 --> 00:22:15,990
está a buscar, a continuación,
quere voltar certo.

426
00:22:15,990 --> 00:22:19,280
Entón, basicamente, se está en un nó que
ten o valor que está a buscar,

427
00:22:19,280 --> 00:22:23,550
vostede sabe que estivo
capaz de investigación con éxito.

428
00:22:23,550 --> 00:22:27,150
>> Se non, quere establecer
o punteiro ao seguinte nodo.

429
00:22:27,150 --> 00:22:28,850
Iso é o que esta liña está facendo aquí.

430
00:22:28,850 --> 00:22:31,750
Punteiro é igual punteiro próximo.

431
00:22:31,750 --> 00:22:33,360
Todo o mundo ver como é que está a traballar?

432
00:22:33,360 --> 00:22:36,580
>> E, esencialmente, vai só
atravesan a totalidade da lista,

433
00:22:36,580 --> 00:22:41,920
axustar o punteiro á vez ata
finalmente bateu o final da lista.

434
00:22:41,920 --> 00:22:45,030
E vostede sabe que non hai
máis nós para buscar,

435
00:22:45,030 --> 00:22:47,999
e entón pode volver false
porque sabe que, oh, así,

436
00:22:47,999 --> 00:22:50,540
se eu fun capaz de buscar
a través da totalidade da lista.

437
00:22:50,540 --> 00:22:54,530
Neste exemplo, se eu quixese
a ollar para o valor de 10,

438
00:22:54,530 --> 00:22:57,250
e eu comezo na cabeza, e
Eu busco todo o camiño,

439
00:22:57,250 --> 00:23:00,550
e finalmente cheguei a esta, que
un punteiro que apunta a null,

440
00:23:00,550 --> 00:23:04,415
Sei que, un porco, eu creo que 10 non está en
esta lista porque eu non podería atopalo.

441
00:23:04,415 --> 00:23:06,520
E eu estou no final da lista.

442
00:23:06,520 --> 00:23:11,040
E no caso de que vostede sabe
Eu estou indo a voltar falso.

443
00:23:11,040 --> 00:23:12,900
>> Deixe que salsa en algo.

444
00:23:12,900 --> 00:23:17,350
Isto vai ser moi
importante para o seu pset.

445
00:23:17,350 --> 00:23:21,140
A lóxica del é moi sinxelo, quizais
sintaticamente só implementar lo.

446
00:23:21,140 --> 00:23:23,365
Vós queredes facer
Asegúrese de que entenda.

447
00:23:23,365 --> 00:23:25,870

448
00:23:25,870 --> 00:23:27,650
Legal.

449
00:23:27,650 --> 00:23:32,560
>> OK, entón como nós ficaríamos
inserción de nós, seguro,

450
00:23:32,560 --> 00:23:35,380
nunha lista de lembrar, porque
o que son o que os beneficios

451
00:23:35,380 --> 00:23:39,230
de ter unha lista vinculada contra
unha matriz en termos de almacenamento?

452
00:23:39,230 --> 00:23:41,110
>> Audiencia: É dinámico,
polo que é máis fácil a--

453
00:23:41,110 --> 00:23:43,180
>> ANDI Pengo: Exactamente,
polo que é dinámica, o que

454
00:23:43,180 --> 00:23:46,880
significa que pode expandir-se e encoller
dependendo das necesidades do usuario.

455
00:23:46,880 --> 00:23:56,570
E así, neste sentido, non precisamos
perder memoria innecesaria porque

456
00:23:56,570 --> 00:24:00,850
se eu non sei cantos valores que quero
a tenda, non ten sentido para min

457
00:24:00,850 --> 00:24:04,310
para crear unha matriz porque
se eu queira gardar 10 valores

458
00:24:04,310 --> 00:24:08,380
e eu crear unha matriz de 1000, que é
unha gran cantidade de memoria desperdiçada, asignado.

459
00:24:08,380 --> 00:24:11,180
É por iso que queremos usar un conectado
lista para poder dinamicamente

460
00:24:11,180 --> 00:24:13,860
cambiar ou diminuír o tamaño da nosa.

461
00:24:13,860 --> 00:24:17,040
>> E así que fai a inserción
un pouco máis complicado.

462
00:24:17,040 --> 00:24:20,810
Xa que non podemos acceder ao azar elementos
do xeito que queremos unha matriz.

463
00:24:20,810 --> 00:24:24,270
Se eu queira inserir un elemento
na sétima índice,

464
00:24:24,270 --> 00:24:26,930
Só pode inserir-lo
na sétima índice.

465
00:24:26,930 --> 00:24:30,020
Nunha lista ligada, iso non acontece
bastante traballar tan facilmente,

466
00:24:30,020 --> 00:24:34,947
e polo que se queriamos para introducir
aquí na lista ligada,

467
00:24:34,947 --> 00:24:36,280
visualmente, é moi fácil de ver.

468
00:24:36,280 --> 00:24:39,363
Nós só queremos inserir-lo alí mesmo,
ao comezo da lista,

469
00:24:39,363 --> 00:24:40,840
logo da cabeza.

470
00:24:40,840 --> 00:24:44,579
>> Pero o xeito no que temos que volver asignar
os punteiros é un pouco complicado

471
00:24:44,579 --> 00:24:47,620
ou, loxicamente, ten sentido, pero
quere estar seguro de que ten-

472
00:24:47,620 --> 00:24:50,250
completamente abaixo, porque
a última cousa que quere

473
00:24:50,250 --> 00:24:52,990
é reatribuído un punteiro a
xeito que nós estamos facendo aquí.

474
00:24:52,990 --> 00:24:58,170
Se eliminar a referencia ao
punteiro da cabeza aos 1,

475
00:24:58,170 --> 00:25:01,086
entón, de súpeto, o
resto da súa lista ligada

476
00:25:01,086 --> 00:25:04,680
está perdido, porque non ten, en realidade,
creado un nada temporal.

477
00:25:04,680 --> 00:25:06,220
Isto sinalou o 2.

478
00:25:06,220 --> 00:25:10,080
Se trasladar o punteiro, entón o
resto da súa lista está totalmente perdido.

479
00:25:10,080 --> 00:25:13,310
Entón quere ser
moi, moi coidado aquí

480
00:25:13,310 --> 00:25:17,010
para asignar o primeiro
punteiro de todo o que

481
00:25:17,010 --> 00:25:20,150
quere inserir en calquera lugar
quere, e entón

482
00:25:20,150 --> 00:25:22,710
pode cancelar o resto da súa lista.

483
00:25:22,710 --> 00:25:25,250
>> Entón, iso é aplicable a onde quere
estás inserir.

484
00:25:25,250 --> 00:25:27,520
Se desexa inserir no
cabeza, se quere responder aquí,

485
00:25:27,520 --> 00:25:29,455
se quere inserir no
Ao final, así, a fin I

486
00:25:29,455 --> 00:25:30,910
creo que faría só
Non ten un punteiro, pero

487
00:25:30,910 --> 00:25:33,830
Quere ter a certeza de que non facer
perder o resto da súa lista.

488
00:25:33,830 --> 00:25:36,640
Sempre quere estar seguro
o novo nó está apuntando

489
00:25:36,640 --> 00:25:39,330
no sentido de todo o que
quere introducir,

490
00:25:39,330 --> 00:25:42,170
e entón pode engadir o fío diante.

491
00:25:42,170 --> 00:25:43,330
Todo o mundo é clara?

492
00:25:43,330 --> 00:25:45,427
>> Este será
unha das cuestións reais.

493
00:25:45,427 --> 00:25:48,010
Unha das máis importantes cuestións
terá no seu pset

494
00:25:48,010 --> 00:25:51,340
é que está indo a tentar crear
unha lista encadeada e as cousas de inserción

495
00:25:51,340 --> 00:25:53,340
pero despois é só perder o
resto da súa lista ligada.

496
00:25:53,340 --> 00:25:54,900
E vai ser como eu
Non sei por que isto está a suceder?

497
00:25:54,900 --> 00:25:58,040
E é unha dor de pasar por
e buscar todos os seus punteiros.

498
00:25:58,040 --> 00:26:02,100
>> E eu asegura que nesta pset,
escribir e debuxar eses nós fóra

499
00:26:02,100 --> 00:26:03,344
vai ser moi, moi útil.

500
00:26:03,344 --> 00:26:06,010
Para que poida manter completamente a noción
de onde os seus punteiros son,

501
00:26:06,010 --> 00:26:08,540
o que está a suceder de malo,
onde todos os seus nodos son,

502
00:26:08,540 --> 00:26:12,660
o que cómpre facer para acceder ou
inserir ou eliminar ou ningún deles.

503
00:26:12,660 --> 00:26:14,550
Todos ben con iso?

504
00:26:14,550 --> 00:26:15,050
Legal.

505
00:26:15,050 --> 00:26:19,300

506
00:26:19,300 --> 00:26:22,600
>> Entón, se nós quería mirar o código?

507
00:26:22,600 --> 00:26:24,470
Oh, eu non sei se nós
pode ver as-- OK, entón

508
00:26:24,470 --> 00:26:27,940
na parte superior de todo, é unha función
inserción nomeado onde queremos

509
00:26:27,940 --> 00:26:31,365
para inserir int n na lista ligada.

510
00:26:31,365 --> 00:26:32,740
Nós imos camiñar por este.

511
00:26:32,740 --> 00:26:34,770
É unha morea de código, unha morea de nova sintaxe.

512
00:26:34,770 --> 00:26:36,220
Nós imos estar ben.

513
00:26:36,220 --> 00:26:39,120
>> Así, na parte superior, sempre que
queremos crear nada

514
00:26:39,120 --> 00:26:42,380
o que necesitamos facer, especialmente se
quere que non debe ser almacenado na pila

515
00:26:42,380 --> 00:26:43,920
pero na pila?

516
00:26:43,920 --> 00:26:45,460
Nós imos para un malloc, non?

517
00:26:45,460 --> 00:26:48,240
Entón imos crear un punteiro.

518
00:26:48,240 --> 00:26:52,074
No, punteiro, novas equals
malloc o tamaño dun nodo

519
00:26:52,074 --> 00:26:53,740
porque queremos que nó a crear.

520
00:26:53,740 --> 00:26:56,720
Queremos que a cantidade de
memoria que un nó ocupa

521
00:26:56,720 --> 00:26:59,300
sendo asignado ao
creación do novo nó.

522
00:26:59,300 --> 00:27:02,270
>> E entón nós imos comprobar a
ver se é igual a novos iguais nulo.

523
00:27:02,270 --> 00:27:03,370
Teña en conta que do que dixemos?

524
00:27:03,370 --> 00:27:06,470
Todo o que malloc,
o que ten que sempre facer?

525
00:27:06,470 --> 00:27:09,490
Ten que sempre comprobar a ver
se iso é ou non nulo.

526
00:27:09,490 --> 00:27:13,620
>> Por exemplo, se o seu funcionamento
sistema foi completamente cheo,

527
00:27:13,620 --> 00:27:17,060
se non tiña máis memoria
todo e intentar malloc,

528
00:27:17,060 --> 00:27:18,410
ía voltar nulo para ti.

529
00:27:18,410 --> 00:27:21,094
E por iso, se tentar usalo
cando estaba a apuntar cara null,

530
00:27:21,094 --> 00:27:23,260
non vai poder
para acceder a esta información.

531
00:27:23,260 --> 00:27:27,010
E así, como tal, nós queriamos facer
Asegúrese de que sempre que está mallocing,

532
00:27:27,010 --> 00:27:30,500
está sempre comprobando se
que a memoria dado a ti é nulo.

533
00:27:30,500 --> 00:27:33,670
E se non é, entón podemos pasar
co resto do noso código.

534
00:27:33,670 --> 00:27:36,140
>> Entón, nós estamos indo a
iniciar o novo nó.

535
00:27:36,140 --> 00:27:39,050
Nós imos facer nova n é igual a n.

536
00:27:39,050 --> 00:27:42,390
E entón nós imos facer
definir novo o punteiro na nova

537
00:27:42,390 --> 00:27:46,900
como nulo porque agora non
quere nada para el para apuntar.

538
00:27:46,900 --> 00:27:48,755
Nós non temos ningunha idea de onde
vai poñer-lo,

539
00:27:48,755 --> 00:27:50,630
e, a continuación, se queremos
inserir-lo na cabeza,

540
00:27:50,630 --> 00:27:53,820
entón podemos asignar novo
o punteiro para a cabeza.

541
00:27:53,820 --> 00:27:58,530
Será que todo o mundo seguir a lóxica
de onde isto está a suceder?

542
00:27:58,530 --> 00:28:02,502
>> Todo o que estamos facendo é crear unha nova
no, establecer o punteiro para null,

543
00:28:02,502 --> 00:28:04,210
e, a continuación, a reasignación
Lo á cabeza se

544
00:28:04,210 --> 00:28:06,320
sabemos que queremos para inserir-lo na cabeza.

545
00:28:06,320 --> 00:28:09,420
E, a continuación, a cabeza vai
apuntan que o novo nó.

546
00:28:09,420 --> 00:28:11,060
Todos ben con iso?

547
00:28:11,060 --> 00:28:12,380
>> Polo tanto, é un proceso de dúas etapas.

548
00:28:12,380 --> 00:28:14,760
Ten que primeiro asignar
o que quere que está creando.

549
00:28:14,760 --> 00:28:18,260
Establecer que punteiro para o
referencia, e entón

550
00:28:18,260 --> 00:28:21,400
pode tipo de dereference
o primeiro punteiro

551
00:28:21,400 --> 00:28:22,972
e sinala-lo para o novo nó.

552
00:28:22,972 --> 00:28:25,680
Onde queira que quere inserir-lo,
que a lóxica vai realizar certo.

553
00:28:25,680 --> 00:28:27,530
>> É unha especie de como asignar
variables temporais.

554
00:28:27,530 --> 00:28:28,700
Lembre, ten
para asegurarse de que

555
00:28:28,700 --> 00:28:30,346
non perder de vista que está cambiando.

556
00:28:30,346 --> 00:28:33,470
Quere estar seguro de que vostede ten un
variable temporal este tipo de garda

557
00:28:33,470 --> 00:28:35,620
o control de onde esa cousa
se garda para que

558
00:28:35,620 --> 00:28:41,190
non perden calquera valor no curso
de como xogar con el.

559
00:28:41,190 --> 00:28:42,710
>> OK, entón o código será aquí.

560
00:28:42,710 --> 00:28:45,020
Vostedes vexan despois da sección.

561
00:28:45,020 --> 00:28:48,060
Vai estar alí.

562
00:28:48,060 --> 00:28:50,280
>> Entón eu creo que como é que
iso difire se quixésemos

563
00:28:50,280 --> 00:28:52,300
introducir no medio ou no fin?

564
00:28:52,300 --> 00:28:57,892
Alguén ten unha idea de cal é o
pseudocódigo como referencia lóxica

565
00:28:57,892 --> 00:29:00,350
que levaría se quixésemos
para inserir-lo no medio?

566
00:29:00,350 --> 00:29:03,391
Entón, se nós quería para inserir-lo no
cabeza, todo o que facemos é crear un novo nodo.

567
00:29:03,391 --> 00:29:06,311
Nós axustar o punteiro do que
novo nodo a todo o que a cabeza,

568
00:29:06,311 --> 00:29:08,310
e, a continuación, imos definir o cabeza
ao novo nodo, non?

569
00:29:08,310 --> 00:29:11,560
Se quixésemos para inserir-lo no medio
da lista, o que tería que facer?

570
00:29:11,560 --> 00:29:14,108

571
00:29:14,108 --> 00:29:16,110
>> Audiencia: É aínda faría
ser un proceso semellante

572
00:29:16,110 --> 00:29:19,114
de como a asignación de punteiro e
a continuación, atribuíndo este punteiro,

573
00:29:19,114 --> 00:29:20,530
pero teriamos que atopar alí.

574
00:29:20,530 --> 00:29:23,560
>> ANDI Pengo: Exactamente, exactamente por iso
o mesmo proceso, agás que

575
00:29:23,560 --> 00:29:27,820
ten que atopar onde exactamente
quere que o novo punteiro para entrar,

576
00:29:27,820 --> 00:29:44,790
por iso, se quero introducir en
no medio ligado lista-- OK,

577
00:29:44,790 --> 00:29:46,370
imos dicir que esa é a nosa lista ligada.

578
00:29:46,370 --> 00:29:49,500
Se queremos inserir-lo aquí,
imos crear unha nova no.

579
00:29:49,500 --> 00:29:50,520
Estamos indo para malloc.

580
00:29:50,520 --> 00:29:52,220
Nós imos crear unha nova no.

581
00:29:52,220 --> 00:29:55,940
Nós imos asignar o
punteiro deste nodo aquí.

582
00:29:55,940 --> 00:29:58,335
>> Pero o problema que difire
de onde a cabeza é

583
00:29:58,335 --> 00:30:00,490
é que nós sabiamos exactamente
onde está a cabeza.

584
00:30:00,490 --> 00:30:01,930
Foi á dereita na primeira, non?

585
00:30:01,930 --> 00:30:04,870
Pero aquí temos que manter o control
de onde estamos introducindo-o.

586
00:30:04,870 --> 00:30:07,930
Se estamos introducindo noso
nó aquí, temos

587
00:30:07,930 --> 00:30:12,270
para asegurarse de que o
anterior a este nodo

588
00:30:12,270 --> 00:30:14,172
é aquel que atribúe novo o punteiro.

589
00:30:14,172 --> 00:30:16,380
Entón tes que tipo de
manter o control de dúas cousas.

590
00:30:16,380 --> 00:30:19,420
Se manter o control de onde esta
nó actualmente está inserindo.

591
00:30:19,420 --> 00:30:23,280
Tamén ten que manter o control de onde
o no anterior que está mirando

592
00:30:23,280 --> 00:30:24,340
tamén estaba alí.

593
00:30:24,340 --> 00:30:25,830
Todos ben con iso?

594
00:30:25,830 --> 00:30:26,500
Aceptar.

595
00:30:26,500 --> 00:30:28,000
>> Como case introducir ao final?

596
00:30:28,000 --> 00:30:34,220
Se eu quería engadir lo aqui-- se eu quería
para engadir un novo nodo ao final dunha lista,

597
00:30:34,220 --> 00:30:37,009
como eu podería ir sobre como facelo?

598
00:30:37,009 --> 00:30:39,300
Audiencia: Entón, actualmente, a
do último apuntado como nulo.

599
00:30:39,300 --> 00:30:40,960
ANDI Pengo: Si.

600
00:30:40,960 --> 00:30:43,560
Exactamente, polo que este
Actualmente é apuntado saber,

601
00:30:43,560 --> 00:30:46,720
e entón eu creo que, nese sentido, é
moi fácil de engadir ao final dunha lista.

602
00:30:46,720 --> 00:30:51,810
Todo o que tes que facer é configurar-lo
igual a nulo e despois crecer.

603
00:30:51,810 --> 00:30:53,070
Ben alí, moi fácil.

604
00:30:53,070 --> 00:30:53,960
Moi sinxelo.

605
00:30:53,960 --> 00:30:56,430
>> Moi semellante ao
cabeza, pero loxicamente vostede

606
00:30:56,430 --> 00:30:59,690
quere estar seguro de que os pasos
tomar para facer nada diso,

607
00:30:59,690 --> 00:31:01,500
está acompañando.

608
00:31:01,500 --> 00:31:04,420
É moi fácil, no medio
do seu código, collo,

609
00:31:04,420 --> 00:31:05,671
Oh, eu teño tantos punteiros.

610
00:31:05,671 --> 00:31:07,461
Non sei onde
nada está a apuntar.

611
00:31:07,461 --> 00:31:09,170
Eu non sei cal o nodo no que estou.

612
00:31:09,170 --> 00:31:11,490
Qué está a pasar?

613
00:31:11,490 --> 00:31:13,620
>> Relax, calme-se, tomar unha respiración profunda.

614
00:31:13,620 --> 00:31:15,530
Debuxe a súa lista ligada.

615
00:31:15,530 --> 00:31:18,800
Se digo, eu sei onde exactamente
Necesito inserir isto en

616
00:31:18,800 --> 00:31:22,970
e sei exactamente como recolocar o meu
punteiros, moito, moito máis fácil de imaxinar

617
00:31:22,970 --> 00:31:27,200
out-- moito máis fácil de non
perderse nos erros do seu código.

618
00:31:27,200 --> 00:31:29,410
Todos ben con iso?

619
00:31:29,410 --> 00:31:31,380
Aceptar.

620
00:31:31,380 --> 00:31:35,120
>> Entón eu creo que un concepto que non ten
realmente falamos antes agora,

621
00:31:35,120 --> 00:31:38,131
e eu creo que probablemente
Non vai atopar moi yet--

622
00:31:38,131 --> 00:31:40,880
é unha especie de un concept-- avanzada
é que realmente temos un conxunto de datos

623
00:31:40,880 --> 00:31:43,900
estrutura chamada unha lista dobremente ligada.

624
00:31:43,900 --> 00:31:46,390
Entón, como podedes ver,
todo o que estamos facendo é crear

625
00:31:46,390 --> 00:31:50,400
un valor real, un extra
punteiro en cada unha das nosas nós

626
00:31:50,400 --> 00:31:52,660
que tamén apunta para o nodo anterior.

627
00:31:52,660 --> 00:31:58,170
Polo tanto, non só temos o noso
nós apuntar á seguinte.

628
00:31:58,170 --> 00:32:01,430
Eles apuntan ao anterior.

629
00:32:01,430 --> 00:32:04,310
Vou ignorar estas dúas agora.

630
00:32:04,310 --> 00:32:06,740
>> Entón tes unha cadea
que pode moverse en ambos os sentidos,

631
00:32:06,740 --> 00:32:09,630
e entón é un pouco máis fácil
a continuación loxicamente xunto.

632
00:32:09,630 --> 00:32:11,896
Como aquí, en vez de
manter o control de, oh, I

633
00:32:11,896 --> 00:32:14,520
Ten que saber que este nodo é
o que eu teño que volver a asignar,

634
00:32:14,520 --> 00:32:17,532
Só podo ir aquí e
basta tirar o anterior.

635
00:32:17,532 --> 00:32:19,490
Entón eu sei exactamente onde
que é, e entón

636
00:32:19,490 --> 00:32:21,130
Non ten que atravesar a
totalidade da lista ligada.

637
00:32:21,130 --> 00:32:22,180
É un pouco máis fácil.

638
00:32:22,180 --> 00:32:24,960
>> Pero, como tal, ten dobremente
a cantidade de punteiros,

639
00:32:24,960 --> 00:32:26,960
que é o dobre da cantidade de memoria.

640
00:32:26,960 --> 00:32:28,950
É unha morea de agullas para acompañar.

641
00:32:28,950 --> 00:32:32,140
É un pouco máis complexo, pero é
un pouco máis agradable, dependendo

642
00:32:32,140 --> 00:32:34,080
o que estás a realizar.

643
00:32:34,080 --> 00:32:36,910
>> Polo tanto, este tipo de datos
estrutura existe totalmente,

644
00:32:36,910 --> 00:32:40,280
ea estrutura para é moi, moi
simple, excepto todo o que está a ter é,

645
00:32:40,280 --> 00:32:43,850
no canto de só un punteiro para o próximo,
tamén ten un punteiro para anterior.

646
00:32:43,850 --> 00:32:45,940
Isto é todo o que a diferenza era.

647
00:32:45,940 --> 00:32:47,740
Todos ben con iso?

648
00:32:47,740 --> 00:32:48,240
Legal.

649
00:32:48,240 --> 00:32:50,940

650
00:32:50,940 --> 00:32:53,280
>> Todo ben, entón agora eu son
para realmente pasar seguramente

651
00:32:53,280 --> 00:32:56,870
como 15 a 20 minutos ou a granel
do resto do tempo na sección

652
00:32:56,870 --> 00:32:58,360
falando de táboas de hash.

653
00:32:58,360 --> 00:33:02,590
Como moitos de vostedes
lin pset5 especificación?

654
00:33:02,590 --> 00:33:03,620
Todo ben, bo.

655
00:33:03,620 --> 00:33:06,160
Iso é máis elevado que o 50% do normal.

656
00:33:06,160 --> 00:33:07,560
Está ben.

657
00:33:07,560 --> 00:33:10,345
>> Entón, como vostedes van ver,
es desafío en pset5

658
00:33:10,345 --> 00:33:16,790
será a posta en marcha dun dicionario
onde cargar máis de 140.000 palabras

659
00:33:16,790 --> 00:33:20,610
que nós dámoslle e corrector ortográfico
contra todo o texto.

660
00:33:20,610 --> 00:33:22,580
Nós imos darlle aleatoria
pezas de literatura.

661
00:33:22,580 --> 00:33:23,520
Nós imos darlle o Odyssey.

662
00:33:23,520 --> 00:33:24,561
Nós imos dar-lle a Ilíada.

663
00:33:24,561 --> 00:33:26,350
Nós imos darlle Austin Powers.

664
00:33:26,350 --> 00:33:28,220
>> E o seu desafío
será a de corrector ortográfico

665
00:33:28,220 --> 00:33:31,760
cada palabra en todo
destes dicionarios

666
00:33:31,760 --> 00:33:34,960
esencialmente co noso corrector ortográfico.

667
00:33:34,960 --> 00:33:38,620
E por iso hai poucas partes
de crear este pset,

668
00:33:38,620 --> 00:33:41,970
primeiro quere ser
capaz de cargar, de feito,

669
00:33:41,970 --> 00:33:43,970
todas as palabras no seu
dicionario, e entón

670
00:33:43,970 --> 00:33:45,530
Quere ser capaz de
corrector ortográfico todos eles.

671
00:33:45,530 --> 00:33:48,780
E así, como tal, está indo para esixir
unha estrutura de datos que pode facelo rápido

672
00:33:48,780 --> 00:33:50,790
e eficiente e de forma dinámica.

673
00:33:50,790 --> 00:33:52,900
>> Entón, eu supoño que o máis fácil
xeito de facelo,

674
00:33:52,900 --> 00:33:55,010
probablemente crear unha matriz, non?

675
00:33:55,010 --> 00:33:58,910
O xeito máis doado de almacenamento é vostede
Pode crear unha matriz de 140.000 palabras

676
00:33:58,910 --> 00:34:03,400
e só poñer-los todos alí e
entón atravesala los por busca binaria

677
00:34:03,400 --> 00:34:06,780
ou polas seleccións ou não--
Lamentamos que é a clasificación.

678
00:34:06,780 --> 00:34:10,729
Pode clasificalos los e despois atravesa-los
por busca binaria ou busca só lineal

679
00:34:10,729 --> 00:34:13,730
e só as palabras finais, pero que
leva unha gran cantidade de memoria,

680
00:34:13,730 --> 00:34:15,190
e non é moi eficiente.

681
00:34:15,190 --> 00:34:18,350
>> E así imos comezar
fala de formas de facer

682
00:34:18,350 --> 00:34:20,110
noso tempo de funcionamento máis eficiente.

683
00:34:20,110 --> 00:34:23,190
E o noso obxectivo é facer que
constante de tempo onde

684
00:34:23,190 --> 00:34:25,810
é case como matrices, onde
ten acceso instantáneo.

685
00:34:25,810 --> 00:34:28,560
Se eu quixese buscar calquera cousa,
Quero ser capaz de só,

686
00:34:28,560 --> 00:34:30,810
crecemento, atopalo exactamente, e puxe-o para fora.

687
00:34:30,810 --> 00:34:34,100
E así unha estrutura na que
nós imos estar a facer-se moi preto

688
00:34:34,100 --> 00:34:37,569
para acceder a constante
tempo, ese Santo Graal

689
00:34:37,569 --> 00:34:41,370
na programación da constante
tempo chámase táboa de hash.

690
00:34:41,370 --> 00:34:45,370
E así por David mencionado anteriormente o
[Inaudível] un pouco na charla,

691
00:34:45,370 --> 00:34:49,100
pero nós imos realmente
mergullo en profundidade esta semana

692
00:34:49,100 --> 00:34:51,780
nun anaco que está sobre
como unha táboa hash funciona.

693
00:34:51,780 --> 00:34:53,949
>> Así, a forma que un hash
obras de mesa, por exemplo,

694
00:34:53,949 --> 00:35:00,230
se eu quería gardar un monte de palabras, un
chea de palabras no idioma inglés,

695
00:35:00,230 --> 00:35:02,940
Eu podería, en teoría, poñer
bananas, mazá, kiwi, mango, par,

696
00:35:02,940 --> 00:35:04,980
e melón todo en só unha matriz.

697
00:35:04,980 --> 00:35:07,044
Todos eles poderían encaixar e ser atopar.

698
00:35:07,044 --> 00:35:09,210
Sería unha especie de dor para
buscar e acceso,

699
00:35:09,210 --> 00:35:12,920
pero o xeito máis doado de facelo é
que pode crear efectivamente unha estrutura

700
00:35:12,920 --> 00:35:15,680
chamado unha táboa hash onde nós hash.

701
00:35:15,680 --> 00:35:19,880
Corremos todos os nosos chaves través
unha función hash, unha ecuación,

702
00:35:19,880 --> 00:35:22,600
que transforma-los todos
algún tipo de valor

703
00:35:22,600 --> 00:35:28,740
que entón podemos almacenar en
esencialmente un array de lista ligada.

704
00:35:28,740 --> 00:35:32,570
>> E aquí, se quixésemos
para almacenar palabras en inglés,

705
00:35:32,570 --> 00:35:37,250
Podemos potencialmente só, eu non
sabe, transformar as primeiras letras

706
00:35:37,250 --> 00:35:39,630
en algún tipo de un número.

707
00:35:39,630 --> 00:35:43,140
E así, por exemplo, se eu quixese
Un a ser sinónimo de apple--

708
00:35:43,140 --> 00:35:47,460
ou co índice de 0, e
B sendo sinónimo de 1,

709
00:35:47,460 --> 00:35:51,030
podemos ter 26 entradas
que poden só almacenar

710
00:35:51,030 --> 00:35:53,610
todas as letras do
alfabeto que imos comezar.

711
00:35:53,610 --> 00:35:56,130
E entón podemos ter
mazá no índice de 0.

712
00:35:56,130 --> 00:35:59,160
Podemos ter de bananas no índice de
1, melón no índice de 2,

713
00:35:59,160 --> 00:36:00,540
e así por diante e así por diante.

714
00:36:00,540 --> 00:36:04,460
E, así, se eu quixese buscar
meu hash de mesa e acceso mazá,

715
00:36:04,460 --> 00:36:07,560
Sei que Apple comeza con
un A, e sei exactamente

716
00:36:07,560 --> 00:36:10,860
que debe ser eo hash
táboa no índice 0, pois

717
00:36:10,860 --> 00:36:13,620
da función asignado anteriormente.

718
00:36:13,620 --> 00:36:16,572
>> Entón, eu non sei, somos
un programa de usuario, onde

719
00:36:16,572 --> 00:36:18,780
vai ser cobra con
non arbitrarily-- arbitrariamente,

720
00:36:18,780 --> 00:36:22,530
coa tentativa de pensativamente
pensar en boas ecuacións

721
00:36:22,530 --> 00:36:25,460
para poder estenderse
fóra todos os seus valores

722
00:36:25,460 --> 00:36:29,370
dun xeito que poden acceder facilmente
Lo máis tarde con como unha ecuación

723
00:36:29,370 --> 00:36:31,130
que, vostede mesmo, sabe.

724
00:36:31,130 --> 00:36:35,210
Así, no sentido de que eu quería ir a
manga, sei, oh, el comeza con m.

725
00:36:35,210 --> 00:36:37,134
Debe ser no índice de 12.

726
00:36:37,134 --> 00:36:38,800
Non teño a busca a través de calquera cousa.

727
00:36:38,800 --> 00:36:42,080
Sei exactly-- eu podería só ir
o índice de 12 e tirar iso.

728
00:36:42,080 --> 00:36:45,520
>> Todos clara sobre como un
A función da táboa hash funciona?

729
00:36:45,520 --> 00:36:48,380
É unha especie de só unha matriz máis complexa.

730
00:36:48,380 --> 00:36:50,010
Isto é todo o que é.

731
00:36:50,010 --> 00:36:51,630
Aceptar.

732
00:36:51,630 --> 00:36:57,690
>> Entón eu creo que correr en
esta cuestión que

733
00:36:57,690 --> 00:37:06,390
acontece se ten moitas cousas
que darlle o mesmo índice?

734
00:37:06,390 --> 00:37:10,570
Entón, dicir que a nosa función, o único que
fixo foi tomar esta primeira letra

735
00:37:10,570 --> 00:37:14,490
e transformar isto nun
respectivo contido 0 a 25.

736
00:37:14,490 --> 00:37:17,137
Isto é totalmente ben se
só ten un de cada.

737
00:37:17,137 --> 00:37:18,970
Pero a segunda comeza
ter máis, é

738
00:37:18,970 --> 00:37:20,910
terá o que se chama unha colisión.

739
00:37:20,910 --> 00:37:25,580
>> Entón, se eu tentar inserir enterrar nun hash
táboa que xa bananas nel,

740
00:37:25,580 --> 00:37:27,870
o que vai pasar cando
tentar inserir iso?

741
00:37:27,870 --> 00:37:30,930
Cousas malas debido á banana
Xa existe dentro do índice

742
00:37:30,930 --> 00:37:33,800
que quere almacena-lo.

743
00:37:33,800 --> 00:37:35,560
Berry tipo de é como, ah, o que fago?

744
00:37:35,560 --> 00:37:37,080
Non sei onde ir.

745
00:37:37,080 --> 00:37:38,410
Como podo solucionar isto?

746
00:37:38,410 --> 00:37:41,150
>> E así vostedes van tipo de
ver o que facemos esta cousa complicada

747
00:37:41,150 --> 00:37:44,810
onde podemos tipo de verdade
crear lista ligada nas nosas matrices.

748
00:37:44,810 --> 00:37:46,840
E así, o xeito máis doado
para pensar sobre iso,

749
00:37:46,840 --> 00:37:50,830
todo é unha táboa hash
matriz de listas ligadas.

750
00:37:50,830 --> 00:37:55,670
E así, neste sentido, ten
esta fermosa matriz de punteiros,

751
00:37:55,670 --> 00:37:58,740
e, a continuación, en cada punteiro
este valor, no que o índice,

752
00:37:58,740 --> 00:38:00,740
realmente apuntar para outras cousas.

753
00:38:00,740 --> 00:38:05,720
E entón tes todos eses separado
cadeas saíndo dunha gran matriz.

754
00:38:05,720 --> 00:38:07,960
>> E aquí, se eu
quería introducir baga,

755
00:38:07,960 --> 00:38:11,220
Sei, OK, eu estou indo a introducir
Lo través da miña función hash.

756
00:38:11,220 --> 00:38:15,070
Vou acabar co índice de
1, e entón eu vou ser capaz de ter

757
00:38:15,070 --> 00:38:20,410
só un subconxunto menor desta
xigante dicionario de 140.000 palabras.

758
00:38:20,410 --> 00:38:24,220
E entón eu podo só ollar
mediante 1/26 do que iso.

759
00:38:24,220 --> 00:38:27,910
>> E entón eu só podo inserir
baga, tanto antes ou despois da banana

760
00:38:27,910 --> 00:38:28,820
neste caso?

761
00:38:28,820 --> 00:38:29,700
Despois, non?

762
00:38:29,700 --> 00:38:33,920
E entón vai querer
inserir ese nó despois de bananas,

763
00:38:33,920 --> 00:38:36,667
e entón vai para introducir
en que a cola de lista ligada.

764
00:38:36,667 --> 00:38:38,500
Vou volver
a este slide anterior,

765
00:38:38,500 --> 00:38:40,680
para que vostedes poidan ver como
función hash funciona.

766
00:38:40,680 --> 00:38:43,980
>> Entón función hash é esta ecuación
que está executando o seu tipo de entrada

767
00:38:43,980 --> 00:38:46,940
través de obter o que quere índice
desexa asignar-lo para.

768
00:38:46,940 --> 00:38:51,130
E así, neste exemplo, todo o que queriamos
a facer era tomar a primeira letra,

769
00:38:51,130 --> 00:38:55,890
transformar isto nun índice, entón nós
pode almacenar que na nosa función hash.

770
00:38:55,890 --> 00:39:00,160
Todo o que estamos facendo aquí é que estamos
converter a primeira letra.

771
00:39:00,160 --> 00:39:04,770
Entón KeyKey [0] é só a primeira letra
de calquera secuencia que estamos tendo,

772
00:39:04,770 --> 00:39:05,720
estamos pasando.

773
00:39:05,720 --> 00:39:09,740
Estamos convertendo que a superior, e
estamos subtraindo por letras maiúsculas A,

774
00:39:09,740 --> 00:39:11,740
así todo o que está facendo
está nos dando un número

775
00:39:11,740 --> 00:39:13,670
no que podemos botar nosos valores para.

776
00:39:13,670 --> 00:39:16,550
>> E entón nós imos
voltar de hash TAMAÑO módulo.

777
00:39:16,550 --> 00:39:19,340
Sexa moito, moito coidado
porque, en teoría, aquí

778
00:39:19,340 --> 00:39:21,870
o seu valor de hash pode ser infinita.

779
00:39:21,870 --> 00:39:23,660
El podería simplemente ir sobre e sobre e sobre.

780
00:39:23,660 --> 00:39:26,080
Pode haber algunha verdade,
realmente grande valor,

781
00:39:26,080 --> 00:39:29,849
senón porque a súa táboa hash que
que creou posúe só 26 índices,

782
00:39:29,849 --> 00:39:31,890
quere estar seguro do seu
modulusing para que

783
00:39:31,890 --> 00:39:33,848
non run-- é o mesmo
cousa como o seu queue--

784
00:39:33,848 --> 00:39:36,320
para que non corra fóra da
inferior da súa función hash.

785
00:39:36,320 --> 00:39:39,210
>> Quere envolve-la de volta de todo
do mesmo xeito en [inaudível] cando

786
00:39:39,210 --> 00:39:41,750
tivo como un moito,
moi grande carta, vostede

787
00:39:41,750 --> 00:39:43,740
Non quería que isto
basta realizar fóra da final.

788
00:39:43,740 --> 00:39:46,948
Mesmo aquí, quere asegurarse de
non se executa fóra da final por implicación

789
00:39:46,948 --> 00:39:48,330
en torno ao principio da mesa.

790
00:39:48,330 --> 00:39:50,530
Polo tanto, esta é só unha moi
función hash simple.

791
00:39:50,530 --> 00:39:56,570
Todo o que fixen foi dar o primeiro
carta de todo o que o noso contribución foi

792
00:39:56,570 --> 00:40:01,660
e transformar isto nun índice que
poderiamos poñer na nosa táboa de hash.

793
00:40:01,660 --> 00:40:05,450
>> Si, e así como dixen antes,
a forma que nós resolver colisións

794
00:40:05,450 --> 00:40:09,330
na nosa hash de táboas están tendo,
o que chamamos fío.

795
00:40:09,330 --> 00:40:13,860
Entón, se tentar inserir múltiple
palabras que comezan con o mesmo,

796
00:40:13,860 --> 00:40:16,145
terá un valor de hash.

797
00:40:16,145 --> 00:40:18,770
Aguacate e mazá, se ten
executa-lo a través da nosa función hash,

798
00:40:18,770 --> 00:40:21,450
vai darlle a
mesmo número, o número de 0.

799
00:40:21,450 --> 00:40:24,550
E así a nosa forma de solucionar isto é
que podemos realmente tipo de vincula-los

800
00:40:24,550 --> 00:40:27,010
xuntos vía listas ligadas.

801
00:40:27,010 --> 00:40:29,600
>> E así, neste sentido,
podedes ver especie

802
00:40:29,600 --> 00:40:32,640
de forma que as estruturas de datos
vimos creación anteriormente

803
00:40:32,640 --> 00:40:35,870
como unha uva pasa ligada lista especie
de poden unirse nun só.

804
00:40:35,870 --> 00:40:38,860
E entón podes crear moito
estruturas de datos máis eficientes

805
00:40:38,860 --> 00:40:43,350
que pode tratar con grandes cantidades de
datos, que redimensionar dinamicamente dependendo

806
00:40:43,350 --> 00:40:44,870
das súas necesidades.

807
00:40:44,870 --> 00:40:45,620
Todo o mundo é clara?

808
00:40:45,620 --> 00:40:47,580
Todos tipo de clara
sobre o que pasa aquí?

809
00:40:47,580 --> 00:40:52,110
>> Se eu quixese insert-- o que é un
froita que comeza con, eu non sei,

810
00:40:52,110 --> 00:40:54,726
B, con excepción baga, bananas.

811
00:40:54,726 --> 00:40:55,710
>> Audiencia: Blackberry.

812
00:40:55,710 --> 00:40:57,910
>> ANDI Pengo: Blackberry, amor.

813
00:40:57,910 --> 00:41:00,530
Onde é que blackberry aquí?

814
00:41:00,530 --> 00:41:04,251
Ben, nós realmente non resolver
iso aínda, pero, en teoría,

815
00:41:04,251 --> 00:41:06,250
se quixésemos ter este
por orde alfabética,

816
00:41:06,250 --> 00:41:07,944
onde debe ir blackberry?

817
00:41:07,944 --> 00:41:09,210
>> Audiencia: [inaudível]

818
00:41:09,210 --> 00:41:11,100
>> ANDI Pengo: Exactamente, tras aquí, non?

819
00:41:11,100 --> 00:41:14,950
Pero xa que é moi difícil
reorder-- Coido que cómpre a vostedes.

820
00:41:14,950 --> 00:41:17,920
Podedes totalmente
aplicar o que quere.

821
00:41:17,920 --> 00:41:20,730
O xeito máis eficaz
de facelo, quizais,

822
00:41:20,730 --> 00:41:24,570
sería a de clasificar a súa conectado
lista en orde alfabética,

823
00:41:24,570 --> 00:41:26,520
e entón cando está
inserción de cousas, quere

824
00:41:26,520 --> 00:41:28,632
estar seguro de inserir-los
en orde alfabética

825
00:41:28,632 --> 00:41:30,590
para que, a continuación, cando está
intentando buscalos,

826
00:41:30,590 --> 00:41:32,410
non ten que atravesar todo.

827
00:41:32,410 --> 00:41:35,290
Vostede sabe exactamente onde
que é, e é máis fácil.

828
00:41:35,290 --> 00:41:39,100
>> Pero se tipo de
cousas intercalado azar,

829
00:41:39,100 --> 00:41:41,420
aínda vai ter
para cruzalo de calquera maneira.

830
00:41:41,420 --> 00:41:44,990
E entón se eu quería só
inserir blackberry aquí

831
00:41:44,990 --> 00:41:47,470
e eu quería buscar
iso, eu sei, ah, blackberry

832
00:41:47,470 --> 00:41:52,012
debe comezar co índice de 1, entón eu
saber instantáneamente pode buscar a 1.

833
00:41:52,012 --> 00:41:53,970
E entón eu podo tipo de
atravesar a lista vinculada

834
00:41:53,970 --> 00:41:56,120
ata chegar ao BlackBerry,
e entăo-- si?

835
00:41:56,120 --> 00:41:59,550
>> Audiencia: Se estás a create--
Creo que como este é un hash moi sinxelo

836
00:41:59,550 --> 00:42:00,050
función.

837
00:42:00,050 --> 00:42:02,835
E se o que queriamos facer
varias capas de que, como o

838
00:42:02,835 --> 00:42:05,870
OK, queremos separar en
como todas as letras do alfabeto

839
00:42:05,870 --> 00:42:09,040
e logo de novo a gustar doutro conxunto
de letras do alfabeto en que,

840
00:42:09,040 --> 00:42:11,715
que estamos poñendo como un hash
táboa dentro dunha táboa hash,

841
00:42:11,715 --> 00:42:13,256
ou como unha función dentro dunha función?

842
00:42:13,256 --> 00:42:14,880
Ou é isso--

843
00:42:14,880 --> 00:42:17,510
>> ANDI Pengo: Entón seu haxix
function-- súa táboa hash

844
00:42:17,510 --> 00:42:19,360
pode ser tan grande como queres que.

845
00:42:19,360 --> 00:42:21,930
Polo tanto, neste sentido, penso
era moi fácil, moi

846
00:42:21,930 --> 00:42:25,320
simple para min en base só sorte
en cartas de primeira palabra.

847
00:42:25,320 --> 00:42:28,690
E por iso hai só 26 opcións.

848
00:42:28,690 --> 00:42:32,650
Só pode obter 26 opcións de
0-25 porque só poden

849
00:42:32,650 --> 00:42:36,510
comezar da a Z. Pero Se quería
que engadir, quizais, máis complexidade

850
00:42:36,510 --> 00:42:39,260
ou máis rápido tempo de execución para o seu
táboa de hash, é absolutamente

851
00:42:39,260 --> 00:42:40,760
pode facer todo tipo de cousas.

852
00:42:40,760 --> 00:42:43,330
Podes facer o seu propio
ecuación que dá a vostede

853
00:42:43,330 --> 00:42:48,000
máis na súa distribución
palabras, entón cando procura,

854
00:42:48,000 --> 00:42:49,300
que vai ser máis rápido.

855
00:42:49,300 --> 00:42:52,100
>> É totalmente ata vós
como quere aplicar iso.

856
00:42:52,100 --> 00:42:55,140
Pense nisso como só baldes.

857
00:42:55,140 --> 00:42:57,376
Se eu quería ter
26 baldes, eu vou

858
00:42:57,376 --> 00:42:59,420
para resolver as cousas para os baldes.

859
00:42:59,420 --> 00:43:02,980
Pero eu vou ter unha chea
de material en cada balde,

860
00:43:02,980 --> 00:43:05,890
por iso, se quere facelo
máis rápido e máis eficiente,

861
00:43:05,890 --> 00:43:07,190
déixeme ter cen baldes.

862
00:43:07,190 --> 00:43:09,290
>> Pero entón tes que descubrir unha
forma de resolver as cousas para que sexan

863
00:43:09,290 --> 00:43:11,040
no balde adecuada deben estar en.

864
00:43:11,040 --> 00:43:13,331
Pero entón cando realmente
quero ver ese balde,

865
00:43:13,331 --> 00:43:16,410
é moito máis rápido porque non hai
menos cousas en cada balde.

866
00:43:16,410 --> 00:43:20,250
E entón, si, iso é verdade,
o truco para vós en pset5

867
00:43:20,250 --> 00:43:22,360
é que vai ser
reto a crear só

868
00:43:22,360 --> 00:43:26,170
calquera que sexa o máis eficiente
función que pode pensar de ser

869
00:43:26,170 --> 00:43:28,520
capaz de almacenar e comprobar eses valores.

870
00:43:28,520 --> 00:43:30,840
>> Totalmente ata vós
con todo, quere facelo,

871
00:43:30,840 --> 00:43:32,229
pero iso é un punto moi bo.

872
00:43:32,229 --> 00:43:34,520
Que tipo de lóxica que
quere comezar a pensar en

873
00:43:34,520 --> 00:43:37,236
é, así, por que non podo facer máis baldes.

874
00:43:37,236 --> 00:43:39,527
E entón eu teño que buscar
menos cousas, e entón quizais eu

875
00:43:39,527 --> 00:43:41,640
ten unha función hash diferente.

876
00:43:41,640 --> 00:43:45,500
>> Si, hai unha morea de formas de facelo
pset, algúns son máis rápidos que outros.

877
00:43:45,500 --> 00:43:50,630
Estou totalmente vai só ver como
rápido foi o máis rápido que vostedes van

878
00:43:50,630 --> 00:43:55,170
poder obter as súas funcións para traballar.

879
00:43:55,170 --> 00:43:58,176
OK, todo en bo
fío e hash táboas?

880
00:43:58,176 --> 00:44:00,800
É realmente como unha forma moi simple
concepto, se pensar sobre iso.

881
00:44:00,800 --> 00:44:05,160
Todo o que é separar o que quere
súas entradas están en baldes,

882
00:44:05,160 --> 00:44:10,670
clasificándose os, a continuación, buscar o
lista que non está asociado.

883
00:44:10,670 --> 00:44:11,852
>> Legal.

884
00:44:11,852 --> 00:44:18,160
Todo ben, agora temos un tipo
de estrutura de datos que se chama unha árbore.

885
00:44:18,160 --> 00:44:20,850
Imos seguir adiante e falar intentos
que son distintas diferentes,

886
00:44:20,850 --> 00:44:22,330
pero na mesma categoría.

887
00:44:22,330 --> 00:44:29,010
Esencialmente, toda a árbore é xa
de organización de datos en forma lineal

888
00:44:29,010 --> 00:44:32,560
que unha táboa hash does-- vostede
sabe, ten un superior e un inferior

889
00:44:32,560 --> 00:44:37,900
e, a continuación, tipo de conexión fóra dun ele--
árbore ten un top que chamar a raíz,

890
00:44:37,900 --> 00:44:40,220
e logo, ten as follas toda en torno a el.

891
00:44:40,220 --> 00:44:42,390
>> E así todo o que tes aquí
é só o nodo superior

892
00:44:42,390 --> 00:44:45,980
que apunta a outros nós, que puntos
para máis nós, e así por diante e así por diante.

893
00:44:45,980 --> 00:44:48,130
E así só ten ramas de división.

894
00:44:48,130 --> 00:44:53,255
É só un xeito diferente de organizar
datos, e porque o chamamos dunha árbore,

895
00:44:53,255 --> 00:44:56,270
vostedes só-- é só
modelado para parecerse a unha árbore.

896
00:44:56,270 --> 00:44:57,670
É por iso que nós o chamamos árbores.

897
00:44:57,670 --> 00:44:59,370
>> Táboa de hash parece unha táboa.

898
00:44:59,370 --> 00:45:01,310
Unha árbore só parece unha árbore.

899
00:45:01,310 --> 00:45:03,300
Todo o que é un separado
forma de organizar os nós

900
00:45:03,300 --> 00:45:06,020
dependendo de cales son as súas necesidades.

901
00:45:06,020 --> 00:45:11,810
>> Entón tes unha raíz e
entón tes follas.

902
00:45:11,810 --> 00:45:15,380
O xeito que podemos particularmente
pensar sobre iso é unha árbore binaria,

903
00:45:15,380 --> 00:45:18,150
unha árbore binaria é só un
tipo específico dunha árbore

904
00:45:18,150 --> 00:45:22,450
onde cada nodo únicos puntos
a, como máximo, dous outros nós.

905
00:45:22,450 --> 00:45:25,434
E por iso aquí tes distintas
simetría na súa árbore

906
00:45:25,434 --> 00:45:28,600
que fará máis tipo de ollar
en que os valores que son, porque entón

907
00:45:28,600 --> 00:45:30,150
ter sempre un esquerdo ou dereito.

908
00:45:30,150 --> 00:45:33,150
Nunca hai como unha terceira esquerda de
á esquerda ou un cuarto da esquerda.

909
00:45:33,150 --> 00:45:36,358
É só ten unha esquerda e unha dereita
e pode buscar calquera dos dous.

910
00:45:36,358 --> 00:45:38,980
E así por que isto é útil?

911
00:45:38,980 --> 00:45:40,980
O xeito que se trata
é útil se está a buscar

912
00:45:40,980 --> 00:45:42,890
a procura a través de valores, non?

913
00:45:42,890 --> 00:45:45,640
No canto de aplicar binario
buscar nunha matriz de erro,

914
00:45:45,640 --> 00:45:49,260
se quería ser capaz de inserir os nós
e aproveitar os nós a gusto e tamén

915
00:45:49,260 --> 00:45:52,185
preservar a busca
capacidades de procura binaria.

916
00:45:52,185 --> 00:45:54,560
Así, deste xeito, somos tipo de
tricking-- lembro cando

917
00:45:54,560 --> 00:45:56,530
dixo listas ligadas non podo busca binaria?

918
00:45:56,530 --> 00:46:01,700
Estamos tipo de creación dunha estrutura de datos
que trucos que traballar.

919
00:46:01,700 --> 00:46:05,034
>> E iso porque listas ligadas son lineais,
eles só conectar un despois do outro.

920
00:46:05,034 --> 00:46:06,950
Podemos tipo de
distinto tipo de punteiros

921
00:46:06,950 --> 00:46:09,408
que ligan con diferentes nós
que pode axudarnos coa investigación.

922
00:46:09,408 --> 00:46:12,590
E aquí, se eu quixese
ter unha árbore de busca binaria,

923
00:46:12,590 --> 00:46:14,090
Sei que o meu medio se 55.

924
00:46:14,090 --> 00:46:18,280
Eu só vou crear este
como o meu medio, como a miña raíz,

925
00:46:18,280 --> 00:46:20,770
e entón eu vou ter
valores xirar fóra del.

926
00:46:20,770 --> 00:46:25,610
>> Entón, aquí, se eu vou buscar
o valor de 66, podo comezar a 55.

927
00:46:25,610 --> 00:46:27,310
É 66 maior que 55?

928
00:46:27,310 --> 00:46:30,970
Si, é, entón eu sei que mus investigación
i n o punteiro dereita da árbore.

929
00:46:30,970 --> 00:46:32,440
Eu vou a 77.

930
00:46:32,440 --> 00:46:35,367
OK, é menos que 66 ou maior que 77?

931
00:46:35,367 --> 00:46:37,950
É menos que, por iso, vostede sabe, oh,
que ten que ser o no da esquerda.

932
00:46:37,950 --> 00:46:41,410
>> E entón aquí estamos tipo de preservación
todas as grandes cousas sobre arrays,

933
00:46:41,410 --> 00:46:44,420
así como redimensionamento dinámico
de obxectos, sendo

934
00:46:44,420 --> 00:46:49,530
capaz de inserir e eliminar a gusto,
sen ter que se preocupar co fixo

935
00:46:49,530 --> 00:46:50,370
cantidade de espazo.

936
00:46:50,370 --> 00:46:52,820
Aínda preservar todos
aquelas cousas marabillosas

937
00:46:52,820 --> 00:46:57,140
mentres tamén é capaz de conservar a
rexistro e tempo de procura binaria investigación

938
00:46:57,140 --> 00:47:00,450
que só anteriormente
capaz de obter unha frase.

939
00:47:00,450 --> 00:47:06,310
>> Estrutura de datos legal, tipo de
complexo de implementar, o no.

940
00:47:06,310 --> 00:47:08,311
Como verás, todo o que
representa a estrutura do nodo

941
00:47:08,311 --> 00:47:10,143
é que ten unha esquerda
e un punteiro dereito.

942
00:47:10,143 --> 00:47:11,044
Isto é todo o que é.

943
00:47:11,044 --> 00:47:12,960
Entón, en vez de só
Tendo un X ou unha anterior.

944
00:47:12,960 --> 00:47:15,920
Ten unha esquerda ou á dereita, e, a continuación,
pode tipo de liga-los xuntos

945
00:47:15,920 --> 00:47:16,836
con todo escolle así.

946
00:47:16,836 --> 00:47:21,080

947
00:47:21,080 --> 00:47:24,270
>> OK, imos realmente
basta sacar algúns minutos.

948
00:47:24,270 --> 00:47:25,790
Entón imos voltar aquí.

949
00:47:25,790 --> 00:47:28,270
Como dixen anteriormente,
Eu medio que explicou

950
00:47:28,270 --> 00:47:31,520
a lóxica por tras de como nós
ía buscar por iso.

951
00:47:31,520 --> 00:47:33,860
Estamos indo para tratar de
pseudocoding este para fóra para ver

952
00:47:33,860 --> 00:47:38,000
se podemos aplicar o tipo de
mesma lóxica de busca binaria

953
00:47:38,000 --> 00:47:40,055
a un tipo de estrutura de datos.

954
00:47:40,055 --> 00:47:45,049
Se vós queredes tomar como unha parella
minutos para só pensar sobre iso.

955
00:47:45,049 --> 00:48:45,927

956
00:48:45,927 --> 00:48:46,925
Aceptar.

957
00:48:46,925 --> 00:48:51,407
Todo ben, eu vou
en realidade, só darlle as-- non,

958
00:48:51,407 --> 00:48:52,990
imos falar do pseudocódigo primeiro.

959
00:48:52,990 --> 00:48:56,580
Entón, alguén quere
para dar unha facada en que

960
00:48:56,580 --> 00:49:02,100
o primeiro que quere facer cando
está empezando a procura?

961
00:49:02,100 --> 00:49:04,460
Se estamos a buscar
o valor de 66, o que é

962
00:49:04,460 --> 00:49:07,940
o primeiro que queremos facer, se
queremos Busca binaria esta árbore?

963
00:49:07,940 --> 00:49:10,760
>> Audiencia: Quere ollar dereito
e mirar esquerda para ver [inaudível]

964
00:49:10,760 --> 00:49:11,230
maior número.

965
00:49:11,230 --> 00:49:12,271
>> ANDI Pengo: Si, exactamente.

966
00:49:12,271 --> 00:49:15,350
Entón, vai mirar para a súa raíz.

967
00:49:15,350 --> 00:49:18,180
Hai moitas formas que pode chamar
el, o seu nó pai persoas din.

968
00:49:18,180 --> 00:49:21,317
Eu gusto de dicir porque raíz
que é como a raíz da árbore.

969
00:49:21,317 --> 00:49:23,400
Vai mirar para
o no raíz, e está

970
00:49:23,400 --> 00:49:26,940
vai ver é 66 maior
que é menor que 55.

971
00:49:26,940 --> 00:49:30,360
E se é maior que, así, é
superior, onde é que imos querer ollar?

972
00:49:30,360 --> 00:49:32,000
Onde queremos buscar agora, non?

973
00:49:32,000 --> 00:49:34,340
Queremos buscar o
metade dereita da árbore.

974
00:49:34,340 --> 00:49:38,390
>> Polo tanto, temos, convenientemente, un
punteiro que apunta cara á dereita.

975
00:49:38,390 --> 00:49:44,325
E entón podemos definir
nosa nova raíz para ser 77.

976
00:49:44,325 --> 00:49:46,450
Podemos só ir onde queira
o punteiro está apuntando.

977
00:49:46,450 --> 00:49:49,100
Ben, oh, aquí estamos empezando
aos 77 anos, e podemos só

978
00:49:49,100 --> 00:49:51,172
facelo de forma recursiva novo e de novo.

979
00:49:51,172 --> 00:49:52,880
Deste xeito, medio
de ter unha función.

980
00:49:52,880 --> 00:49:57,430
Ten unha forma de buscar que
pode só repetir máis e máis e máis,

981
00:49:57,430 --> 00:50:02,720
dependendo de onde quere ollar
ata finalmente chegar ao valor

982
00:50:02,720 --> 00:50:04,730
que está a procurar.

983
00:50:04,730 --> 00:50:05,230
Ten sentido?

984
00:50:05,230 --> 00:50:07,800
>> Estou a piques de amosar-lle o real
código, e é unha morea de código.

985
00:50:07,800 --> 00:50:08,674
Non é necesario asustar.

986
00:50:08,674 --> 00:50:09,910
Imos falar con el.

987
00:50:09,910 --> 00:50:13,410

988
00:50:13,410 --> 00:50:14,020
>> En realidade, non.

989
00:50:14,020 --> 00:50:15,061
Isto foi só pseudocódigo.

990
00:50:15,061 --> 00:50:17,860
OK, iso foi só o pseudocódigo,
que é un pouco complexo,

991
00:50:17,860 --> 00:50:19,751
pero é totalmente bo.

992
00:50:19,751 --> 00:50:21,000
Todos seguindo ao longo aquí?

993
00:50:21,000 --> 00:50:24,260
Se a raíz é nulo, o retorno
falso, porque iso significa

994
00:50:24,260 --> 00:50:26,850
non ten sequera algo alí.

995
00:50:26,850 --> 00:50:31,376
>> Se raíz n é o valor, polo que se
pasa a ser o que está mirando,

996
00:50:31,376 --> 00:50:34,000
entón está indo para volver true
porque sabe que atopou.

997
00:50:34,000 --> 00:50:36,250
Pero, se o valor é inferior
de raíz n, es

998
00:50:36,250 --> 00:50:38,332
vai buscar á esquerda
neno ou a folla esquerda,

999
00:50:38,332 --> 00:50:39,540
todo o que sexa chamalo.

1000
00:50:39,540 --> 00:50:41,750
E se o valor é superior a raíz,
está indo a buscar a árbore dereita,

1001
00:50:41,750 --> 00:50:44,610
a continuación, pode realizar a función
a través de busca de novo.

1002
00:50:44,610 --> 00:50:48,037
>> E se a raíz é nulo, para que aquel
Significa que chegou ao fin?

1003
00:50:48,037 --> 00:50:50,120
Isto significa que non ten ningunha
máis máis follas de investigación,

1004
00:50:50,120 --> 00:50:52,230
entón vostede sabe, oh, I
creo que non é aquí

1005
00:50:52,230 --> 00:50:55,063
porque despois de que eu olhei través
a cousa toda e non é aquí,

1006
00:50:55,063 --> 00:50:56,930
el só podería non estar aquí.

1007
00:50:56,930 --> 00:50:58,350
>> Isto ten sentido para todos?

1008
00:50:58,350 --> 00:51:03,230
Entón, é como busca binaria preservación
as capacidades de listas ligadas.

1009
00:51:03,230 --> 00:51:09,200
Arrefecer, e de xeito que o segundo tipo
de estrutura de datos que vostedes

1010
00:51:09,200 --> 00:51:13,180
pode tentar implementar no seu pset,
só tes que escoller un método.

1011
00:51:13,180 --> 00:51:19,430
Pero quizais un método alternativo para
a táboa hash é o que chamamos un trie.

1012
00:51:19,430 --> 00:51:24,080
>> Todo é un trie é un
tipo específico de árbore que

1013
00:51:24,080 --> 00:51:28,600
ten valores que van a outros valores.

1014
00:51:28,600 --> 00:51:31,450
Entón, en vez de ter un par
árbore no sentido de que un

1015
00:51:31,450 --> 00:51:35,940
cousa pode ligar a dous, pode que
unha cousa apunte a moitas, moitas cousas.

1016
00:51:35,940 --> 00:51:39,450
Ten basicamente matrices
dentro do cal almacena

1017
00:51:39,450 --> 00:51:41,790
punteiros que ligan con outras matrices.

1018
00:51:41,790 --> 00:51:45,210

1019
00:51:45,210 --> 00:51:49,460
>> Así, o no de como nós
definiría un trie

1020
00:51:49,460 --> 00:51:52,590
é que queremos ter un
Booleano, palabra c, non?

1021
00:51:52,590 --> 00:51:54,920
Así, o nodo é booleano
como verdadeira ou falsa,

1022
00:51:54,920 --> 00:51:58,490
en primeiro lugar, por diante de
esa matriz, iso é unha palabra?

1023
00:51:58,490 --> 00:52:03,620
En segundo lugar, quere ter punteiros
a todo o que o resto deles son.

1024
00:52:03,620 --> 00:52:07,470
Un pouco complexo, un pouco abstracto, mais
Vou explicar o que todo isto significa.

1025
00:52:07,470 --> 00:52:13,800
>> Entón, aquí, na parte superior, se
teño unha matriz xa declarou,

1026
00:52:13,800 --> 00:52:17,040
un nó no que ten un valor booleano
valor almacenado diante

1027
00:52:17,040 --> 00:52:19,490
que lle di é esta unha palabra?

1028
00:52:19,490 --> 00:52:20,520
Non é esta unha palabra?

1029
00:52:20,520 --> 00:52:23,240
E entón tes o
resto da súa matriz que

1030
00:52:23,240 --> 00:52:26,040
de feito, almacena todas as
posibilidades do que podería ser.

1031
00:52:26,040 --> 00:52:28,660
Así, por exemplo, como
na parte superior ten

1032
00:52:28,660 --> 00:52:32,140
o primeiro que di certa ou
falso, si ou non, esta é unha palabra.

1033
00:52:32,140 --> 00:52:38,130
>> E entón tes de 0 a 26
as cartas que pode almacenar.

1034
00:52:38,130 --> 00:52:42,790
Se eu quixese buscar aquí
para morcego, eu ir para arriba

1035
00:52:42,790 --> 00:52:49,200
e eu ollo para B. Creo B na miña
array, e entón eu sei, OK, é unha palabra B?

1036
00:52:49,200 --> 00:52:53,010
B non é unha palabra, así que así
Debo seguir buscando.

1037
00:52:53,010 --> 00:52:56,410
Vou de B, e eu ollo para o
punteiro que apunta a B

1038
00:52:56,410 --> 00:53:00,900
e vexo outro conxunto de información,
a mesma estrutura que tiñamos antes.

1039
00:53:00,900 --> 00:53:05,240
>> E aqui-- oh, o seguinte
carta en [inaudível] é A.

1040
00:53:05,240 --> 00:53:07,210
Entón, nós miramos nese array.

1041
00:53:07,210 --> 00:53:10,860
Atopamos o oitavo valor,
e, despois, ollar para ver, oh,

1042
00:53:10,860 --> 00:53:12,840
hey, que é unha palabra, é B-A unha palabra?

1043
00:53:12,840 --> 00:53:13,807
Non é unha palabra.

1044
00:53:13,807 --> 00:53:14,890
Temos que seguir buscando.

1045
00:53:14,890 --> 00:53:17,850
>> E entón miramos para onde
o punteiro de puntos A,

1046
00:53:17,850 --> 00:53:21,130
e apunta a outra forma en
que temos máis valor almacenado.

1047
00:53:21,130 --> 00:53:24,150
E, finalmente, hai que
B-A-T, o que é unha palabra.

1048
00:53:24,150 --> 00:53:25,970
E así a próxima vez
mira, está indo

1049
00:53:25,970 --> 00:53:30,850
para ter ese cheque de si,
esta función booleana é certa.

1050
00:53:30,850 --> 00:53:35,450
E así, no sentido de que estamos especie
de ter unha árbore con matrices.

1051
00:53:35,450 --> 00:53:39,890
>> Entón podes tipo de busca para abaixo.

1052
00:53:39,890 --> 00:53:43,650
En vez de unha función hash e
atribuíndo valores de lista ligada,

1053
00:53:43,650 --> 00:53:49,190
pode simplemente aplicar un
trie que busca downwords.

1054
00:53:49,190 --> 00:53:50,850
Realmente, realmente complicado cousas.

1055
00:53:50,850 --> 00:53:54,060
Non é doado pensar, porque son como
cuspindo tantas estruturas de datos para fóra

1056
00:53:54,060 --> 00:53:58,710
en ti, pero como todo tipo de
entender como a lóxica de todo isto funciona?

1057
00:53:58,710 --> 00:54:01,920
>> OK, legal.

1058
00:54:01,920 --> 00:54:05,600
Así B-A-T e logo
vai buscar.

1059
00:54:05,600 --> 00:54:07,940
A próxima vez que está indo
para ver, oh, hey, é certo,

1060
00:54:07,940 --> 00:54:09,273
así, sei que isto debe ser unha palabra.

1061
00:54:09,273 --> 00:54:12,030

1062
00:54:12,030 --> 00:54:13,770
>> Mesmo para xardín zoolóxico.

1063
00:54:13,770 --> 00:54:17,960
Entón aquí é o correcto agora, se nós
quería buscar zoo, agora,

1064
00:54:17,960 --> 00:54:20,780
Actualmente non é un xardín zoolóxico
palabra na nosa dicionario

1065
00:54:20,780 --> 00:54:25,300
porque, como podedes ver, o
o primeiro que temos un booleano

1066
00:54:25,300 --> 00:54:28,590
return true é a finais de zoom.

1067
00:54:28,590 --> 00:54:30,430
Temos Z-O-O-H.

1068
00:54:30,430 --> 00:54:33,900
>> E aquí, non realmente ter
a palabra, zoo, no noso dicionario

1069
00:54:33,900 --> 00:54:36,070
porque esta caixa de verificación non está marcada.

1070
00:54:36,070 --> 00:54:39,540
Así, o ordenador non fai
sei que zoo é unha palabra

1071
00:54:39,540 --> 00:54:42,430
porque a forma que temos
almacenados, só un zoom aquí

1072
00:54:42,430 --> 00:54:44,920
de feito ten un valor booleano
que foi virou verdade.

1073
00:54:44,920 --> 00:54:49,380
Polo tanto, se queremos introducir o
palabra, zoo, no noso dicionario,

1074
00:54:49,380 --> 00:54:51,770
como é que imos facer sobre iso?

1075
00:54:51,770 --> 00:54:55,960
O que temos que facer para garantir que a nosa
ordenador sabe que Z-O-O é unha palabra

1076
00:54:55,960 --> 00:54:58,130
e non a primeira palabra é Z-O-O-H?

1077
00:54:58,130 --> 00:54:59,360
>> Audiencia: [inaudível]

1078
00:54:59,360 --> 00:55:01,450
>> ANDI Pengo: Exactamente, nós
Quere ter a certeza de que este

1079
00:55:01,450 --> 00:55:07,890
aquí, que é valor booleano
Comprobarase fóra que é verdade.

1080
00:55:07,890 --> 00:55:13,297
Z-O-O, a continuación, imos comprobar que,
polo que sabemos exactamente, hey, xardín zoolóxico é unha palabra.

1081
00:55:13,297 --> 00:55:15,380
Eu vou dicir a
ordenador que é unha palabra tan

1082
00:55:15,380 --> 00:55:18,000
que cando o equipo verifica,
el sabe que zoo é unha palabra.

1083
00:55:18,000 --> 00:55:21,269
>> Porque lembre se todos estes datos
estruturas, é moi doado para nós

1084
00:55:21,269 --> 00:55:22,310
quere dicir, oh, morcego é unha palabra.

1085
00:55:22,310 --> 00:55:22,851
Zoo é unha palabra.

1086
00:55:22,851 --> 00:55:23,611
Zoom é unha palabra.

1087
00:55:23,611 --> 00:55:25,860
Pero cando está construíndo,
o ordenador non ten idea.

1088
00:55:25,860 --> 00:55:28,619
>> Entón tes que dicir a el exactamente
en que punto é esta unha palabra?

1089
00:55:28,619 --> 00:55:29,910
En que punto é que nin unha palabra?

1090
00:55:29,910 --> 00:55:31,784
E en que punto I
que buscar cousas,

1091
00:55:31,784 --> 00:55:34,000
e en que punto eu teño ir a continuación?

1092
00:55:34,000 --> 00:55:37,010
Todos clara de que?

1093
00:55:37,010 --> 00:55:39,540
Legal.

1094
00:55:39,540 --> 00:55:42,530
>> E entón vén o
problema de como sería de nós

1095
00:55:42,530 --> 00:55:45,560
ir sobre como inserir algo
que, en realidade, non é?

1096
00:55:45,560 --> 00:55:49,090
Entón imos dicir que queremos introducir
a palabra, baño, na nosa trie.

1097
00:55:49,090 --> 00:55:53,589
Como podedes ver como actualmente
todo o que temos agora é B-A-T,

1098
00:55:53,589 --> 00:55:55,630
e esta nova estrutura de datos
alí tiña unha cunca que

1099
00:55:55,630 --> 00:55:59,740
sinalou nula porque asumimos
que, oh, non hai palabras tras B-A-T,

1100
00:55:59,740 --> 00:56:02,530
por que necesitamos para manter
ter as cousas despois de que T.

1101
00:56:02,530 --> 00:56:06,581
>> Pero o problema xorde se
quero ter unha palabra que vén despois

1102
00:56:06,581 --> 00:56:07,080
a T.

1103
00:56:07,080 --> 00:56:09,500
Se ten bañeira, está
Vai querer un dereito H.

1104
00:56:09,500 --> 00:56:13,290
E así, o xeito que nós estamos indo a facelo é
imos crear un nó separado.

1105
00:56:13,290 --> 00:56:16,840
Non imos poñer calquera cantidade
de memoria para esta nova matriz,

1106
00:56:16,840 --> 00:56:20,720
e imos volver a asignar punteiros.

1107
00:56:20,720 --> 00:56:22,947
>> Nós imos asignar o
H, Primeiro de todo, este nulo,

1108
00:56:22,947 --> 00:56:24,030
nós estamos indo a se librar.

1109
00:56:24,030 --> 00:56:26,590
Nós imos ter
os abaixo punto H.

1110
00:56:26,590 --> 00:56:30,600
Se vemos un H, queremos que
para ir a outro lugar.

1111
00:56:30,600 --> 00:56:33,910
>> Desde aquí, entón podemos marcar si.

1112
00:56:33,910 --> 00:56:38,170
Se se loita un H despois do T, oh,
entón sabemos que esta é unha palabra.

1113
00:56:38,170 --> 00:56:41,110
O booleano vai voltar true.

1114
00:56:41,110 --> 00:56:42,950
Todos clara sobre como isto aconteceu?

1115
00:56:42,950 --> 00:56:45,110
Aceptar.

1116
00:56:45,110 --> 00:56:47,214
>> Así, esencialmente, todo
estas estruturas de datos

1117
00:56:47,214 --> 00:56:50,130
que temos ido máis hoxe, teño
ir sobre eles moito, moi rapidamente

1118
00:56:50,130 --> 00:56:52,192
e en que non máis
detalle, e iso é OK.

1119
00:56:52,192 --> 00:56:53,900
Unha vez que comezar a xogar
con el, pode

1120
00:56:53,900 --> 00:56:55,733
manter o control de onde
Todos os punteiros son,

1121
00:56:55,733 --> 00:56:58,060
o que está a suceder na súa
estruturas de datos, etcétera.

1122
00:56:58,060 --> 00:56:59,810
Eles van ser moi útil,
e cómpre a vostede

1123
00:56:59,810 --> 00:57:03,890
caras para descubrir como totalmente fóra
quere aplicar cousas.

1124
00:57:03,890 --> 00:57:07,650
>> E así PSet4, de 5-- Oh, iso é incorrecto.

1125
00:57:07,650 --> 00:57:10,140
Pset5 é erros.

1126
00:57:10,140 --> 00:57:13,710
Como dixo antes, vai, xa
de novo, descargar o código fonte de nós.

1127
00:57:13,710 --> 00:57:16,210
Non vai ser de tres principal
cousas que vai ser a descarga.

1128
00:57:16,210 --> 00:57:18,470
Vai baixar dicionarios,
KERS e textos.

1129
00:57:18,470 --> 00:57:21,660
>> Todas estas cousas son son
quere dicionarios de palabras

1130
00:57:21,660 --> 00:57:25,190
que queremos que vaia
ou proba de información

1131
00:57:25,190 --> 00:57:26,930
que queremos que verificación ortográfica.

1132
00:57:26,930 --> 00:57:29,670
E así os dicionarios
nós dámoslle van

1133
00:57:29,670 --> 00:57:34,870
para darlle palabras reais que queremos
almacenar algunha maneira en forma que é

1134
00:57:34,870 --> 00:57:36,530
máis eficiente que unha matriz.

1135
00:57:36,530 --> 00:57:38,470
E, a continuación, os textos son
será o que somos

1136
00:57:38,470 --> 00:57:43,900
pedíndolle para deletrear comproba
todas as palabras son palabras reais alí.

1137
00:57:43,900 --> 00:57:47,970
>> E así os tres bloques de
programas que nós imos dar-lle

1138
00:57:47,970 --> 00:57:51,130
son chamados dictionary.c,
dictionary.h, e speller.c.

1139
00:57:51,130 --> 00:57:56,500
E así todo o dictionary.c fai é
o que está invitado a aplicar.

1140
00:57:56,500 --> 00:57:57,880
El leva palabras.

1141
00:57:57,880 --> 00:58:02,000
El ortográfico comproba-los, e iso pasa a ser de
que todo está inserida correctamente.

1142
00:58:02,000 --> 00:58:05,180
>> diction.h é só un arquivo de biblioteca
que declara todas esas funcións.

1143
00:58:05,180 --> 00:58:07,650
E speller.c, nós imos dar-lle.

1144
00:58:07,650 --> 00:58:09,290
Non precisa modificar nada diso.

1145
00:58:09,290 --> 00:58:14,290
Todos speller.c fai é tomar que,
leva-lo, verifica a velocidade do mesmo,

1146
00:58:14,290 --> 00:58:19,190
examina o valor de referencia de como como
rapidamente é capaz de facer as cousas.

1147
00:58:19,190 --> 00:58:20,410
>> É un corrector ortográfico.

1148
00:58:20,410 --> 00:58:23,920
Só non xogar con iso, pero facer
seguro que entende o que está facendo.

1149
00:58:23,920 --> 00:58:28,090
Usamos unha función chamada getrusage que
examina o desempeño do seu feitizo

1150
00:58:28,090 --> 00:58:28,590
tomada.

1151
00:58:28,590 --> 00:58:32,200
Todo o que fai é basicamente probar a
tempo de todo no seu dicionario,

1152
00:58:32,200 --> 00:58:33,680
polo que asegúrese de comprende-lo.

1153
00:58:33,680 --> 00:58:36,660
Teña coidado de non xogar con el ou
as outras cousas non funcionará correctamente.

1154
00:58:36,660 --> 00:58:39,740

1155
00:58:39,740 --> 00:58:44,170
>> E a maior parte dese reto é para
vostedes para realmente modificar dictionary.c.

1156
00:58:44,170 --> 00:58:48,526
Nós imos darlle
140.000 palabras nun dicionario.

1157
00:58:48,526 --> 00:58:50,900
Nós imos dar-lle un texto
ficheiro que teña estas palabras,

1158
00:58:50,900 --> 00:58:54,840
e queremos que sexa capaz de organizar
Los nunha táboa hash ou un trie

1159
00:58:54,840 --> 00:58:58,140
porque cando pedimos-lle para deletrear
check-- imaxine se é máxica

1160
00:58:58,140 --> 00:59:00,690
comprobar como a Odisea de Homero.

1161
00:59:00,690 --> 00:59:03,010
É como esta enorme proba enorme ,.

1162
00:59:03,010 --> 00:59:05,190
>> Imaxina se cada
palabra que tiña que ollar

1163
00:59:05,190 --> 00:59:08,100
mediante unha matriz de valores de 140.000.

1164
00:59:08,100 --> 00:59:10,350
Isto levaría para sempre
para a súa máquina para funcionar.

1165
00:59:10,350 --> 00:59:14,490
É por iso que queremos organizar a nosa
datos en estruturas de datos máis eficientes

1166
00:59:14,490 --> 00:59:17,270
como unha táboa de hash ou un trie.

1167
00:59:17,270 --> 00:59:20,700
E entón podedes tipo
de cando busca acceso

1168
00:59:20,700 --> 00:59:22,570
cousas con máis facilidade e máis rápido.

1169
00:59:22,570 --> 00:59:24,934
>> E por iso Tomé coidado para resolver colisións.

1170
00:59:24,934 --> 00:59:27,350
Está indo a obter unha banda
de palabras de que comezo con A.

1171
00:59:27,350 --> 00:59:29,957
Vai ter unha morea palabras
que comezan con B Ata

1172
00:59:29,957 --> 00:59:31,290
caras como quere resolver.

1173
00:59:31,290 --> 00:59:34,144
Se houbese máis
función hash eficiente

1174
00:59:34,144 --> 00:59:36,810
que só a primeira letra
algo, e por iso é ata

1175
00:59:36,810 --> 00:59:38,190
caras para tipo de facer o que quere.

1176
00:59:38,190 --> 00:59:40,148
>> Quizais quere engadir
todas as letras xuntas.

1177
00:59:40,148 --> 00:59:43,410
Quizais quere como facer cousas estrañas
para contabilizar o número de letras,

1178
00:59:43,410 --> 00:59:43,970
o que quere.

1179
00:59:43,970 --> 00:59:45,386
Ata vós como quere facer.

1180
00:59:45,386 --> 00:59:49,262
Se queres facer unha táboa hash, se
quere probar unha trie, totalmente ata.

1181
00:59:49,262 --> 00:59:52,470
Vou aviso-lo antes de tempo que o
trie é normalmente un pouco máis difícil

1182
00:59:52,470 --> 00:59:54,520
só porque hai unha morea
máis punteiros para acompañar.

1183
00:59:54,520 --> 00:59:55,645
Pero totalmente ata vós.

1184
00:59:55,645 --> 00:59:58,742
É moito máis eficiente
na maioría dos casos.

1185
00:59:58,742 --> 01:00:01,450
Quere realmente ser capaz de manter
a par de todos os seus punteiros.

1186
01:00:01,450 --> 01:00:03,850
Como facer o mesmo
que eu estaba facendo aquí.

1187
01:00:03,850 --> 01:00:06,871
Cando estás a introducir
valores nunha táboa hash ou eliminar,

1188
01:00:06,871 --> 01:00:08,620
asegúrese de que vostede é
realmente manter o control

1189
01:00:08,620 --> 01:00:11,860
de onde todo é porque
é realmente doado para se estou

1190
01:00:11,860 --> 01:00:14,727
intentando introducir como a palabra, Andy.

1191
01:00:14,727 --> 01:00:16,810
Nós só dicir que é un
palabra certa, a palabra, Andy,

1192
01:00:16,810 --> 01:00:19,640
nunha lista xigante dun palabras.

1193
01:00:19,640 --> 01:00:22,450
>> Se eu só terá lugar a reasignación
un punteiro mal, oops,

1194
01:00:22,450 --> 01:00:24,940
alí se vai a totalidade do
o resto da miña lista ligada.

1195
01:00:24,940 --> 01:00:26,897
Agora, a única palabra que eu
ten é Andy, e agora

1196
01:00:26,897 --> 01:00:29,230
todas as outras palabras do
dicionario ser perdida.

1197
01:00:29,230 --> 01:00:31,370
E así que quere estar seguro de que vostede
manter o control de todos os seus punteiros

1198
01:00:31,370 --> 01:00:33,661
ou entón está indo para obter
enormes problemas no seu código.

1199
01:00:33,661 --> 01:00:35,840
Debuxe as cousas con coidado, paso a paso.

1200
01:00:35,840 --> 01:00:37,870
Isto torna moito máis doado de pensar.

1201
01:00:37,870 --> 01:00:40,910
>> E, finalmente, quere ser capaz de
probar o seu rendemento do seu programa

1202
01:00:40,910 --> 01:00:41,618
no gran taboleiro.

1203
01:00:41,618 --> 01:00:43,710
Se vós tomar unha
mirar para CS50 agora,

1204
01:00:43,710 --> 01:00:45,210
temos o que se chama o gran cadro.

1205
01:00:45,210 --> 01:00:50,200
É a acta dos máis rápidos
deletrear tempos de aferição, en todos CS50

1206
01:00:50,200 --> 01:00:55,720
agora, eu creo que o top 10 como
veces creo que oito deles son empregados.

1207
01:00:55,720 --> 01:00:57,960
Nós realmente queremos que vós nos vencer.

1208
01:00:57,960 --> 01:01:00,870
>> Todos estabamos intentando aplicar
o código máis rápido posible.

1209
01:01:00,870 --> 01:01:04,880
Queremos que vós tentar desafiar
nós e aplicar máis rápido que todos

1210
01:01:04,880 --> 01:01:05,550
pode.

1211
01:01:05,550 --> 01:01:07,970
E así, este é realmente
a primeira vez que somos

1212
01:01:07,970 --> 01:01:12,680
pedindo a vostedes para facer un pset que
realmente pode facer en calquera método

1213
01:01:12,680 --> 01:01:13,760
quere.

1214
01:01:13,760 --> 01:01:17,730
>> Eu sempre digo, este é máis parecido
a unha solución da vida real, non?

1215
01:01:17,730 --> 01:01:19,550
Digo, hey, eu teño de ti para facelo.

1216
01:01:19,550 --> 01:01:21,380
Construír un programa que fai isto para min.

1217
01:01:21,380 --> 01:01:22,630
Facelo como sexa.

1218
01:01:22,630 --> 01:01:24,271
Eu só sei que quero jejuar.

1219
01:01:24,271 --> 01:01:25,770
Ese é o seu reto para esta semana.

1220
01:01:25,770 --> 01:01:27,531
Vostedes, imos
para darlle unha tarefa.

1221
01:01:27,531 --> 01:01:29,030
Nós imos dar-lle un desafío.

1222
01:01:29,030 --> 01:01:31,559
E entón cómpre a vostedes
completamente só descubrir

1223
01:01:31,559 --> 01:01:34,100
cal é a máis rápida e máis
xeito eficiente de aplicar iso.

1224
01:01:34,100 --> 01:01:34,600
Si?

1225
01:01:34,600 --> 01:01:37,476
>> Audiencia: Permítese se
quería buscar formas máis rápidas

1226
01:01:37,476 --> 01:01:40,821
para facer táboas de hash en liña, podemos facer
que e citar código de outra persoa?

1227
01:01:40,821 --> 01:01:42,070
ANDI Pengo: Si, totalmente ben.

1228
01:01:42,070 --> 01:01:44,320
Entón, se vostedes lendo
spec, hai unha liña

1229
01:01:44,320 --> 01:01:48,310
na especificación que di que vostedes
son totalmente libres para buscar de hash

1230
01:01:48,310 --> 01:01:51,070
funcións en que son algúns
das funcións hash máis rápidos

1231
01:01:51,070 --> 01:01:54,720
para realizar as cousas a través como
Sempre que citar este código.

1232
01:01:54,720 --> 01:01:57,220
Por iso, algunhas persoas xa teñen
descubrín formas rápidas

1233
01:01:57,220 --> 01:02:00,250
de facer correctores ortográficos, de rápida
formas de almacenar información.

1234
01:02:00,250 --> 01:02:02,750
Totalmente ata que vostedes se
quero tomar só iso, non?

1235
01:02:02,750 --> 01:02:04,045
Asegúrese de que está citando.

1236
01:02:04,045 --> 01:02:06,170
O reto aquí é realmente
que estamos tentando probar

1237
01:02:06,170 --> 01:02:09,750
é que seguro que vostede sabe
o camiño de volta punteiros.

1238
01:02:09,750 --> 01:02:12,700
Tanto como aplicar
a función hash real

1239
01:02:12,700 --> 01:02:15,070
e chegando con como
a matemática para facelo,

1240
01:02:15,070 --> 01:02:17,570
podedes buscar o que quere
métodos en liña que vostedes queren.

1241
01:02:17,570 --> 01:02:17,996
Si?

1242
01:02:17,996 --> 01:02:19,700
>> Audiencia: Podemos citar só
usando o [inaudível]?

1243
01:02:19,700 --> 01:02:20,120
>> ANDI Pengo: Si.

1244
01:02:20,120 --> 01:02:22,328
Pode só, no seu comentario,
pode citar como, oh,

1245
01:02:22,328 --> 01:02:26,127
tomado de Yada, Yada,
Yada, a función hash.

1246
01:02:26,127 --> 01:02:27,210
Alguén ten algunha pregunta?

1247
01:02:27,210 --> 01:02:29,694
Nós, en realidade breezed
a sección de hoxe.

1248
01:02:29,694 --> 01:02:31,610
Eu vou estar aquí a
responder a preguntas ben.

1249
01:02:31,610 --> 01:02:36,570
>> Ademais, como dixen, oficina
horas esta noite e mañá.

1250
01:02:36,570 --> 01:02:40,307
A especificación desta semana é, en realidade,
super doado e super rápido de ler.

1251
01:02:40,307 --> 01:02:43,140
Eu quere suxerir a ter un ollar, só
ler a través da totalidade do mesmo.

1252
01:02:43,140 --> 01:02:45,730
>> E Zamyla realmente anda vostede
a través de cada unha das funcións

1253
01:02:45,730 --> 01:02:49,796
precisa para aplicar, e por iso é
moi, moi claro como facer todo.

1254
01:02:49,796 --> 01:02:51,920
Só para ter seguro que é
manter o control dos punteiros.

1255
01:02:51,920 --> 01:02:53,650
Este é un pset moi reto.

1256
01:02:53,650 --> 01:02:56,744
>> Non é un reto porque, como,
Oh, os conceptos son moito máis

1257
01:02:56,744 --> 01:02:59,160
difícil, ou ten que aprender
moi nova sintaxe do camiño

1258
01:02:59,160 --> 01:03:00,650
que fixo a última pset.

1259
01:03:00,650 --> 01:03:03,320
Isto é difícil porque pset
hai moitos puntos,

1260
01:03:03,320 --> 01:03:06,980
e entón é moi, moi fácil de unha vez
ten un erro no seu código non poder

1261
01:03:06,980 --> 01:03:08,315
para descubrir onde é que o erro.

1262
01:03:08,315 --> 01:03:13,200
>> E así completa e absoluta fe en ti
caras para poder bater o noso [inaudível]

1263
01:03:13,200 --> 01:03:13,700
grafías.

1264
01:03:13,700 --> 01:03:16,640
En realidade, eu non teño ningún mina escrito
Aínda non, pero estou a piques de escribir o meu.

1265
01:03:16,640 --> 01:03:19,070
Entón, mentres está escribindo
seu, eu vou estar escribindo meu.

1266
01:03:19,070 --> 01:03:21,070
Vou tentar facer
mina máis rápido que o seu.

1267
01:03:21,070 --> 01:03:23,940
A ver quen ten o máis rápido.

1268
01:03:23,940 --> 01:03:27,340
>> E si, vou ver todos
vostedes aquí o martes.

1269
01:03:27,340 --> 01:03:29,510
Vou correr un tipo como un taller pset.

1270
01:03:29,510 --> 01:03:32,640
Todas as seccións este
semana son talleres PSet,

1271
01:03:32,640 --> 01:03:36,690
entón vostedes teñen moitas oportunidades
por axuda, o horario de oficina, como sempre,

1272
01:03:36,690 --> 01:03:41,330
e realmente ansioso para
ler todo o código dos seus rapaces.

1273
01:03:41,330 --> 01:03:44,160
Teño quizzes-se aquí se
caras queren vir buscar aqueles.

1274
01:03:44,160 --> 01:03:45,880
Iso é todo.

1275
01:03:45,880 --> 01:03:48,180