1
00:00:00,000 --> 00:00:03,423
>> [REPRODUCCIÓ DE MÚSICA]

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

3
00:00:05,380 --> 00:00:08,210
>> ANDI Peng: Benvinguts a la setmana 6 de la secció.

4
00:00:08,210 --> 00:00:11,620
Ens desviem del nostre estàndard
temps de la secció de dimarts

5
00:00:11,620 --> 00:00:14,130
a la tarda a aquesta bella matí de diumenge.

6
00:00:14,130 --> 00:00:17,330
Gràcies per tot el món que
m'acompanyen avui, però de debò,

7
00:00:17,330 --> 00:00:18,170
una ronda d'aplaudiments.

8
00:00:18,170 --> 00:00:20,600
>> Aquesta és una molt gran esforç.

9
00:00:20,600 --> 00:00:23,600
Gairebé ni tan sols faig
en el temps, però estava bé.

10
00:00:23,600 --> 00:00:27,520
Així que sé que tots vostès
simplement han arribat a la prova.

11
00:00:27,520 --> 00:00:30,370
En primer lloc, la benvinguda a
l'altra cara d'això.

12
00:00:30,370 --> 00:00:32,917
>> En segon lloc, parlarem sobre això.

13
00:00:32,917 --> 00:00:34,000
Parlarem de la prova.

14
00:00:34,000 --> 00:00:35,700
Parlarem de com
que estàs fent a la classe.

15
00:00:35,700 --> 00:00:36,550
Vas a estar bé.

16
00:00:36,550 --> 00:00:39,080
Tinc seus qüestionaris per
que al final d'aquí,

17
00:00:39,080 --> 00:00:42,120
així que si vostès volen tenir
una mirada en ella, totalment bé.

18
00:00:42,120 --> 00:00:46,590
>> Així que ràpidament abans de començar, el
ordre del dia d'avui és el següent.

19
00:00:46,590 --> 00:00:48,430
Com es pot veure, estem
acomiadament bàsicament ràpida

20
00:00:48,430 --> 00:00:52,120
a través d'un munt d'estructures de dades
molt, molt, molt ràpid.

21
00:00:52,120 --> 00:00:54,380
Així que, com a tal, no serà
avui molt interactiva.

22
00:00:54,380 --> 00:00:59,620
Només serà la meva classe de crits
coses que vostè, i si et confonc,

23
00:00:59,620 --> 00:01:02,680
si vaig massa ràpid, que em faci saber.

24
00:01:02,680 --> 00:01:05,200
No són més que diverses dades
estructures, i com a part

25
00:01:05,200 --> 00:01:07,070
del conjunt de processadors per a aquest
setmana que ve, podràs

26
00:01:07,070 --> 00:01:10,340
se li pregunti per implementar un d'ells,
potser dos d'ells-- dues d'elles

27
00:01:10,340 --> 00:01:12,319
en el seu conjunt de processadors.

28
00:01:12,319 --> 00:01:14,610
OK, així que només vaig a
començar amb alguns anuncis.

29
00:01:14,610 --> 00:01:19,070
Anem a repassar piles i cues més en
profunditat que el que vam fer abans de la prova.

30
00:01:19,070 --> 00:01:20,990
Anem a repassar units
llista de nou, una vegada més,

31
00:01:20,990 --> 00:01:23,899
més en profunditat del que
que teníem abans de la prova.

32
00:01:23,899 --> 00:01:26,440
I després parlarem d'haixix
taules, arbres i tries, que

33
00:01:26,440 --> 00:01:28,890
són tots bastant necessari per a la seva conjunt de processadors.

34
00:01:28,890 --> 00:01:32,925
I després anem a repassar alguns
consells útils per pset5.

35
00:01:32,925 --> 00:01:37,360
>> OK, així que prova 0.

36
00:01:37,360 --> 00:01:41,090
La mitjana va ser d'un 58%.

37
00:01:41,090 --> 00:01:45,370
Era molt baix, i així vostès tot
va fer molt, molt bé, d'acord

38
00:01:45,370 --> 00:01:46,510
amb aquest.

39
00:01:46,510 --> 00:01:49,970
>> Més o menys, regla d'or és que si vostè és
dins d'una desviació estàndard de la mitjana

40
00:01:49,970 --> 00:01:52,990
sobretot perquè estem en un menor
secció còmode, estàs totalment bé.

41
00:01:52,990 --> 00:01:54,120
Vostè està en pista.

42
00:01:54,120 --> 00:01:55,190
La vida és bona.

43
00:01:55,190 --> 00:01:58,952
>> Sé que és por pensar que
Tinc com un 40% en aquesta prova.

44
00:01:58,952 --> 00:02:00,160
Vaig a deixar aquesta classe.

45
00:02:00,160 --> 00:02:02,243
L'prometo, no estàs
va a fallar la classe.

46
00:02:02,243 --> 00:02:03,680
Vostè és totalment bé.

47
00:02:03,680 --> 00:02:06,850
>> Per a aquells de vostès que ho va superar
la mitjana, impressionant, impressionant,

48
00:02:06,850 --> 00:02:08,780
com, de debò ben fet.

49
00:02:08,780 --> 00:02:09,689
Els tinc amb mi.

50
00:02:09,689 --> 00:02:11,730
Aquí podreu aconseguir-
al final de la secció.

51
00:02:11,730 --> 00:02:14,520
Deixeu-me saber si vostè té qualsevol
qüestions, preguntes amb elles.

52
00:02:14,520 --> 00:02:17,204
Si sumem la seva qualificació
malament, contacteu amb nosaltres.

53
00:02:17,204 --> 00:02:21,240
>> OK, així pset5, això és una realitat
setmana estrany per Yale en el sentit

54
00:02:21,240 --> 00:02:24,240
que el nostre conjunt de processadors s'ha de
Dimecres al migdia inclosos

55
00:02:24,240 --> 00:02:27,317
a la fi del dia, pel que és en realitat
a causa teòricament dimarts al migdia.

56
00:02:27,317 --> 00:02:29,150
Probablement ningú va acabar
Dimarts al migdia.

57
00:02:29,150 --> 00:02:30,830
Això és totalment bé.

58
00:02:30,830 --> 00:02:33,700
Tindrem hores d'oficina
aquesta nit, així com la nit de dilluns.

59
00:02:33,700 --> 00:02:36,810
I totes les seccions d'aquesta setmana ho farà
en realitat convertir-se en tallers,

60
00:02:36,810 --> 00:02:38,800
així que sigues lliure per fer esclatar en
qualsevol secció que desitgi,

61
00:02:38,800 --> 00:02:42,810
i estaran espècie de mini-pset
tallers per a ajuda en això.

62
00:02:42,810 --> 00:02:45,620
Així que, com a tal, aquesta és l'única secció de
on som material didàctic.

63
00:02:45,620 --> 00:02:49,220
Totes les altres seccions se centraran
exclusivament en l'ajuda per al conjunt de processadors.

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

65
00:02:50,146 --> 00:02:52,000
>> AUDIÈNCIA: On són les hores d'oficina?

66
00:02:52,000 --> 00:02:56,120
>> ANDI Peng: Les hores d'oficina
aquesta nit-- oh, bona pregunta.

67
00:02:56,120 --> 00:03:00,580
Crec que les hores d'oficina aquesta nit
estan a la garjola o al Commons.

68
00:03:00,580 --> 00:03:02,984
Si marca en línia CS50
i vostè va a les hores d'oficina,

69
00:03:02,984 --> 00:03:05,650
ha d'haver un horari que
on tots ells són diu.

70
00:03:05,650 --> 00:03:07,954
>> Jo sé bé aquesta nit
o demà és trull,

71
00:03:07,954 --> 00:03:10,120
i crec que podem tenir
béns comuns de l'altra nit.

72
00:03:10,120 --> 00:03:11,020
No estic segur.

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

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

75
00:03:14,430 --> 00:03:18,780
>> Cool, preguntes sobre el
calendari per a la propera com tres dies?

76
00:03:18,780 --> 00:03:21,690
Et prometo que vostès com David
va dir, es tracta de la part superior del turó.

77
00:03:21,690 --> 00:03:23,050
Vostès són gairebé allà.

78
00:03:23,050 --> 00:03:24,644
A només tres dies més.

79
00:03:24,644 --> 00:03:26,310
Arribar allà, i després tots ens vindrem a baix.

80
00:03:26,310 --> 00:03:28,114
Tindrem un bon descans CS-lliure.

81
00:03:28,114 --> 00:03:28,780
Tornarem.

82
00:03:28,780 --> 00:03:30,779
Ens submergim en la web
programació i desenvolupament,

83
00:03:30,779 --> 00:03:35,150
coses que són molt divertit comparar
a alguns dels altres conjunts de processadors.

84
00:03:35,150 --> 00:03:37,974
I va ser fred i
tindrem un munt de diversió.

85
00:03:37,974 --> 00:03:38,890
Tindrem més dolços.

86
00:03:38,890 --> 00:03:39,730
Ho sento pels dolços.

87
00:03:39,730 --> 00:03:40,945
He oblidat dolços.

88
00:03:40,945 --> 00:03:43,310
Era un matí aspra.

89
00:03:43,310 --> 00:03:46,340
Així que nois està gairebé allà,
i estic molt orgullós de vosaltres.

90
00:03:46,340 --> 00:03:49,570
>> OK, així que apila.

91
00:03:49,570 --> 00:03:53,331
Qui va estimar a la pregunta sobre Jack
i la seva roba en el concurs?

92
00:03:53,331 --> 00:03:53,830
Ningú?

93
00:03:53,830 --> 00:03:56,500
OK, això està bé.

94
00:03:56,500 --> 00:04:00,200
>> Per tant, bàsicament com puguis
foto de Jack, aquest noi aquí,

95
00:04:00,200 --> 00:04:03,350
li encanta prendre la roba
de la part superior de la pila,

96
00:04:03,350 --> 00:04:05,750
i es posa de nou en
la pila després que ha fet.

97
00:04:05,750 --> 00:04:07,600
Així d'aquesta manera, mai
sembla estar cada vegada

98
00:04:07,600 --> 00:04:10,090
a la part inferior de la
apilar a la seva roba.

99
00:04:10,090 --> 00:04:12,600
Per tant aquest tipus de descriu
l'estructura de dades bàsica

100
00:04:12,600 --> 00:04:16,610
de com s'implementa una pila.

101
00:04:16,610 --> 00:04:20,060
>> Essencialment, pensar en un
apilar com qualsevol pila d'objectes

102
00:04:20,060 --> 00:04:24,900
on posar les coses a la part superior, i
després els fa esclatar cap a fora de la part superior.

103
00:04:24,900 --> 00:04:28,600
Així LIFO és l'acrònim que ens agrada
al servei- Last In, First Out.

104
00:04:28,600 --> 00:04:32,480
I així, l'última en la part superior de la
pila és el primer que surt.

105
00:04:32,480 --> 00:04:34,260
I així els dos termes
ens agrada associar

106
00:04:34,260 --> 00:04:36,190
amb això que es diu empenta i pop.

107
00:04:36,190 --> 00:04:39,790
Quan empenys alguna cosa sobre la
apilar, i vostè fa esclatar una còpia de seguretat.

108
00:04:39,790 --> 00:04:43,422
>> Així que suposo que això és una mena de
concepte abstracte per a aquells de vostès

109
00:04:43,422 --> 00:04:45,630
que volen veure com un
aplicació real d'aquest

110
00:04:45,630 --> 00:04:46,740
en el món real.

111
00:04:46,740 --> 00:04:50,170
Quants de vosaltres heu escrit un assaig
potser com una hora abans que es va deure,

112
00:04:50,170 --> 00:04:54,510
i has esborrat accidentalment un enorme
part d'ella, com per accident?

113
00:04:54,510 --> 00:04:58,560
I llavors el comandament fer
que utilitzem per posar de nou?

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

115
00:05:00,030 --> 00:05:03,640
Control-Z, de manera que la quantitat de vegades
que Control-Z ha salvat la vida,

116
00:05:03,640 --> 00:05:08,820
ha salvat el cul, cada vegada que
això és implementat a través d'una pila.

117
00:05:08,820 --> 00:05:13,020
>> Essencialment tota la informació
que està en el document de Word,

118
00:05:13,020 --> 00:05:15,080
que és empès i es va ficar en la voluntat.

119
00:05:15,080 --> 00:05:19,460
I així, en essència cada vegada que
esborrar res, vostè fa esclatar una còpia de seguretat.

120
00:05:19,460 --> 00:05:22,820
I llavors, si vostè ho necessita de nou, que
empènyer-la, que és el que fa de Control-C.

121
00:05:22,820 --> 00:05:26,770
I la funció món tan real
de l'estructura de dades del simple

122
00:05:26,770 --> 00:05:28,690
pot ajudar amb la seva vida quotidiana.

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

124
00:05:31,710 --> 00:05:40,150
>> Així que un struct és la forma en què
que realment creem una pila.

125
00:05:40,150 --> 00:05:44,720
Escrivim definir estructura, i després
vam anomenar la pila a la part inferior.

126
00:05:44,720 --> 00:05:47,440
I dins de la pila,
tenim dos paràmetres

127
00:05:47,440 --> 00:05:51,580
que essencialment es pot manipular,
així que tenim carbó capacitat cordes estrella.

128
00:05:51,580 --> 00:05:55,150
>> Tot el que s'està fent
és la creació d'una matriu

129
00:05:55,150 --> 00:05:58,835
que podem emmagatzemar el que vulguis
el qual podem determinar la seva capacitat.

130
00:05:58,835 --> 00:06:01,990
La capacitat és la quantitat màxima de
articles que es poden posar en aquesta matriu.

131
00:06:01,990 --> 00:06:05,660
int size és el comptador que manté
un registre de quants elements són actualment

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

133
00:06:07,850 --> 00:06:11,860
Així llavors podem perdre de vista, A,
tant de res la pila real és,

134
00:06:11,860 --> 00:06:14,850
i, B, quant d'aquesta pila
omplim perquè no volem

135
00:06:14,850 --> 00:06:18,800
a desbordar sobre el que la nostra capacitat és.

136
00:06:18,800 --> 00:06:24,340
>> Així, per exemple, aquesta bella
pregunta era en la seva qüestionari.

137
00:06:24,340 --> 00:06:28,160
En essència, com empenyem
a la part superior d'una pila.

138
00:06:28,160 --> 00:06:28,830
Bastant simple.

139
00:06:28,830 --> 00:06:30,621
Si ens fixem en ella,
anem a caminar a través d'aquest.

140
00:06:30,621 --> 00:06:32,640
Si [inaudible] size--
recordi, sempre que

141
00:06:32,640 --> 00:06:35,300
vol accedir a qualsevol
paràmetre dins d'una estructura,

142
00:06:35,300 --> 00:06:40,320
ho fa el nom de la struct.parameter.

143
00:06:40,320 --> 00:06:42,720
>> En aquest cas, s és
el nom del nostre stack.

144
00:06:42,720 --> 00:06:46,230
Volem accedir la mida
de la mateixa, pel que fem s.size.

145
00:06:46,230 --> 00:06:50,280
Així que, mentre la mida no és
igual a la capacitat o tan llarg

146
00:06:50,280 --> 00:06:52,940
ja que és menys de la capacitat,
ja sigui que treballar aquí.

147
00:06:52,940 --> 00:06:57,180
>> Vols accedir a l'interior
de la pila, per la s.strings,

148
00:06:57,180 --> 00:07:00,790
i vostè va a posar aquest nou número
que desitja inserir en allà.

149
00:07:00,790 --> 00:07:05,030
Diguem que anem a voler
inseriu int n a la pila,

150
00:07:05,030 --> 00:07:08,905
podríem fer s.strings,
suports, s.size és igual a n.

151
00:07:08,905 --> 00:07:11,030
A causa de que la mida és on ens
Actualment es troben a la pila

152
00:07:11,030 --> 00:07:14,590
si anem a empènyer
en, simplement accedim

153
00:07:14,590 --> 00:07:17,370
on la mida és, la
plenitud actual de la pila,

154
00:07:17,370 --> 00:07:21,729
i empenyem la int n en la mateixa.

155
00:07:21,729 --> 00:07:24,770
I després volem assegurar-nos que
també estem incrementant la mida de la n,

156
00:07:24,770 --> 00:07:27,436
perquè puguem fer un seguiment que hem
afegeix una quantitat a la pila.

157
00:07:27,436 --> 00:07:29,660
Ara tenim una mida més gran.

158
00:07:29,660 --> 00:07:33,196
Això aquí té sentit
tothom, com lògicament funciona?

159
00:07:33,196 --> 00:07:34,160
Era una mena de ràpid.

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

161
00:07:39,535 --> 00:07:42,160
AUDIÈNCIA: Pot anar més
els s.stringss.strings [s.size] de nou?

162
00:07:42,160 --> 00:07:45,808
ANDI Peng: És clar, i què fa
s.size Actualment donar-nos?

163
00:07:45,808 --> 00:07:47,440
AUDIÈNCIA: És la mida actual.

164
00:07:47,440 --> 00:07:50,890
ANDI Peng: Exactament, de manera que el
índex actual que el nostre mida és a,

165
00:07:50,890 --> 00:07:57,780
i pel que volem posar el nou número sencer
que volem inserir en s.size.

166
00:07:57,780 --> 00:07:58,760
Això té sentit?

167
00:07:58,760 --> 00:08:01,110
A causa s.strings, tot el que
és és el nom de la matriu.

168
00:08:01,110 --> 00:08:03,510
Tot el que és és l'accés a la
matriu dins la nostra estructura,

169
00:08:03,510 --> 00:08:06,030
i pel que si volem
col·locar n en aquest índex,

170
00:08:06,030 --> 00:08:09,651
només podem accedir-hi
utilitzant suports s.size.

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

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

173
00:08:13,580 --> 00:08:18,916
>> Molt bé, pop, em Pseudocodi fora
per a vostès, sinó concepte similar.

174
00:08:18,916 --> 00:08:19,790
Això té sentit?

175
00:08:19,790 --> 00:08:22,310
Si la mida és més gran
que zero, llavors vostè

176
00:08:22,310 --> 00:08:25,350
sap que vostè vol prendre alguna cosa
perquè si la mida no és

177
00:08:25,350 --> 00:08:27,620
més gran que zero, llavors vostè
no tenen res a la pila.

178
00:08:27,620 --> 00:08:29,840
>> Pel que només desitja executar
aquest codi, només pot

179
00:08:29,840 --> 00:08:32,320
pop si hi ha alguna cosa de pop.

180
00:08:32,320 --> 00:08:35,830
Així que si la mida és més gran
de 0, tenim menys la mida.

181
00:08:35,830 --> 00:08:40,020
Ens disminuir la mida i després vam tornar
el que hi ha dins d'ella perquè

182
00:08:40,020 --> 00:08:42,710
fent esclatar, volem
Accés tot el que s'emmagatzema

183
00:08:42,710 --> 00:08:45,694
en l'índex de la part superior de la pila.

184
00:08:45,694 --> 00:08:46,610
Tot té sentit?

185
00:08:46,610 --> 00:08:49,693
Si et vaig fer nois escriure això,
Vols que nois capaços d'escriure?

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

187
00:08:52,029 --> 00:08:53,570
OK, vostès poden jugar una estona amb ell.

188
00:08:53,570 --> 00:08:55,252
No us preocupeu si vostè no ho entenen.

189
00:08:55,252 --> 00:08:57,460
No tenim temps per codificar
cap a fora avui perquè hem

190
00:08:57,460 --> 00:08:59,959
té un munt d'aquestes estructures
de passar, però essencialment

191
00:08:59,959 --> 00:09:02,214
pseudocodi, molt, molt similar a empènyer.

192
00:09:02,214 --> 00:09:03,380
Només has de seguir al llarg de la lògica.

193
00:09:03,380 --> 00:09:06,092
Assegureu-vos que està accedint tot el
característiques de la seva estructura correctament.

194
00:09:06,092 --> 00:09:06,574
Sí?

195
00:09:06,574 --> 00:09:09,282
>> AUDIÈNCIA: Will aquestes diapositives i
tot això sigui avui-ish?

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

197
00:09:11,586 --> 00:09:13,710
Vaig a tractar de posar
això com una hora després.

198
00:09:13,710 --> 00:09:16,626
Vaig per correu electrònic David, David intentarà
el va posar com una hora després d'això.

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

200
00:09:20,040 --> 00:09:25,470
>> OK, així que després ens endinsem en aquest altre
estructura de dades preciosa diu una cua.

201
00:09:25,470 --> 00:09:30,140
Com vostès poden veure aquí, una
cua, per als britànics entre nosaltres,

202
00:09:30,140 --> 00:09:32,010
tot el que és és una línia.

203
00:09:32,010 --> 00:09:34,680
Així que al contrari del que
creus que una pila és,

204
00:09:34,680 --> 00:09:37,750
una cua és exactament el
lògicament vostè pensa que és.

205
00:09:37,750 --> 00:09:41,914
Es porta a terme per les regles de FIFO,
que és First In, First Out.

206
00:09:41,914 --> 00:09:43,705
Si vostè és el primer
una a la línia, vostè és

207
00:09:43,705 --> 00:09:46,230
el primer que
que surt de la línia.

208
00:09:46,230 --> 00:09:49,680
>> Així que el que ens agrada anomenar a aquest
es desencolatge i encolar.

209
00:09:49,680 --> 00:09:52,380
Si volem afegir alguna cosa
a la nostra cua, ens enqueue.

210
00:09:52,380 --> 00:09:55,690
Si volem treure de la cua, o prendre
una mica lluny, ens dequeue.

211
00:09:55,690 --> 00:10:03,350
>> Així mateix sentit que estem tipus de
la creació d'elements de mida fixa que

212
00:10:03,350 --> 00:10:06,500
pot emmagatzemar certa
coses, sinó que també pot

213
00:10:06,500 --> 00:10:10,100
canviar el lloc on estem col·locant
paràmetres dins d'ells

214
00:10:10,100 --> 00:10:13,140
sobre la base de quin tipus de
funcionalitat que volem.

215
00:10:13,140 --> 00:10:16,700
Així piles, volíem l'última
un, N per ser el primer a sortir.

216
00:10:16,700 --> 00:10:19,800
Cola és que volem el primer
en ser el primer que va sortir.

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

218
00:10:22,510 --> 00:10:26,710
>> Així que la de tipus struct
definir, com es pot veure,

219
00:10:26,710 --> 00:10:29,470
que és una mica diferent
del que era la pila

220
00:10:29,470 --> 00:10:33,120
perquè no només hem de seguir
la pista d'on la mida és actualment,

221
00:10:33,120 --> 00:10:37,420
també volem fer un seguiment del cap
així com en els que actualment som.

222
00:10:37,420 --> 00:10:39,580
Així que crec que és més fàcil
si em baso això.

223
00:10:39,580 --> 00:10:53,270
Així que imaginem que tenim una cua,
així que diguem que el cap és aquí.

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

225
00:10:55,811 --> 00:10:58,310
El cap de la línia, anem a
Només cal dir que és en l'actualitat hi ha,

226
00:10:58,310 --> 00:11:01,809
i volem inserir
alguna cosa a la cua.

227
00:11:01,809 --> 00:11:04,350
Vaig a trucar a mida essencialment
és el mateix que la cua,

228
00:11:04,350 --> 00:11:06,314
Al final d'on vulgui que la seva cua és.

229
00:11:06,314 --> 00:11:07,730
Diguem que la mida és just aquí.

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

231
00:11:14,380 --> 00:11:18,400
>> Llavors, com pot un factiblemente
inserir alguna cosa en una cua?

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

233
00:11:21,000 --> 00:11:24,130
Què índex volem col·locar
on volem inserir en.

234
00:11:24,130 --> 00:11:29,320
Si aquest és el començament de la seva
cua i aquest és el final de la mateixa

235
00:11:29,320 --> 00:11:31,860
o la mida de la mateixa, ¿on som
que vulgueu afegir el següent objecte?

236
00:11:31,860 --> 00:11:32,920
>> AUDIÈNCIA: [inaudible]

237
00:11:32,920 --> 00:11:35,920
ANDI Peng: Exactament, voleu afegir
que depenent has escrit.

238
00:11:35,920 --> 00:11:37,840
O això és en blanc o que està en blanc.

239
00:11:37,840 --> 00:11:42,630
Així que vostè vol afegir que probablement
aquí perquè si la mida és--

240
00:11:42,630 --> 00:11:50,540
si aquests estan plens, desitja
afegir aquí mateix, no?

241
00:11:50,540 --> 00:11:57,150
>> I això és, encara que molt, molt
simple, no és sempre correcta

242
00:11:57,150 --> 00:12:00,690
a causa de que la principal diferència
entre una cua i una pila

243
00:12:00,690 --> 00:12:04,350
és que la cua pot
en realitat ser manipulat

244
00:12:04,350 --> 00:12:06,980
de manera que els canvis del cap
depenent d'on voleu

245
00:12:06,980 --> 00:12:08,650
el començament de la seva senyal per començar.

246
00:12:08,650 --> 00:12:11,900
I com a resultat, la seva cua
També es canviarà.

247
00:12:11,900 --> 00:12:14,770
I així que fes un cop d'ull a
aquest codi en aquest moment.

248
00:12:14,770 --> 00:12:18,620
Com també se'ls va demanar que vostès
escriure en el concurs, de posada en cua.

249
00:12:18,620 --> 00:12:22,580
Potser anem a parlar a través de quin
la resposta era el que era.

250
00:12:22,580 --> 00:12:26,790
>> No podia encaixar bastant aquesta línia en un,
però essencialment aquest tros de codi

251
00:12:26,790 --> 00:12:29,030
ha d'estar en una sola línia.

252
00:12:29,030 --> 00:12:30,140
Passa com 30 segons.

253
00:12:30,140 --> 00:12:33,000
Fes un cop d'ull, i veure per què
aquesta és la manera que ho és.

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

255
00:12:50,030 --> 00:12:55,420
>> Molt, estructura molt similar, molt, molt
estructura similar a l'anterior

256
00:12:55,420 --> 00:12:58,090
apilar excepte potser
una línia de codi.

257
00:12:58,090 --> 00:13:01,190
I que una línia de codi
determina la funcionalitat.

258
00:13:01,190 --> 00:13:03,900
I el que realment diferencia
una cua d'una pila.

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

260
00:13:18,510 --> 00:13:22,010
>> Algú vol prendre una punyalada
en explicar per què has

261
00:13:22,010 --> 00:13:24,980
tinc aquesta cosa complicada en aquesta llista?

262
00:13:24,980 --> 00:13:27,845
Ens veiem el retorn del nostre
meravellosa mòdul amic.

263
00:13:27,845 --> 00:13:31,020
Com vostès aviat vindrà
a reconèixer en la programació,

264
00:13:31,020 --> 00:13:34,910
gairebé sempre vostè necessita alguna cosa
per embolicar al voltant de qualsevol cosa,

265
00:13:34,910 --> 00:13:36,850
mòdul serà la forma de fer-ho.

266
00:13:36,850 --> 00:13:40,510
Així que sabent això, no volia que ningú
per tractar d'explicar aquesta línia de codi?

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

268
00:13:44,060 --> 00:13:47,507
Sí, totes les respostes són
acceptada i benvinguda.

269
00:13:47,507 --> 00:13:48,840
AUDIÈNCIA: Vostè està parlant amb mi?

270
00:13:48,840 --> 00:13:49,506
ANDI Peng: Sí.

271
00:13:49,506 --> 00:13:56,200
AUDIÈNCIA: Oh, no ho sento.

272
00:13:56,200 --> 00:14:00,250
ANDI Peng: OK, així que anem a
caminar a través d'aquest codi.

273
00:14:00,250 --> 00:14:03,642
Així que quan vostè està tractant de
afegir alguna cosa en una cua,

274
00:14:03,642 --> 00:14:08,510
a la bonica cas que el cap passa
per ser just aquí, és molt fàcil per a nosaltres

275
00:14:08,510 --> 00:14:10,960
que només ha d'anar fins al final
inserir alguna cosa, no?

276
00:14:10,960 --> 00:14:14,690
Però el punt central d'una cua és
que el cap de fet pot dinàmicament

277
00:14:14,690 --> 00:14:17,280
canviar depenent d'on estem
vol que el començament de la nostra q sigui,

278
00:14:17,280 --> 00:14:19,880
i com a tal, la cua
També es canviarà.

279
00:14:19,880 --> 00:14:31,100
>> I així, imagino que això no era la
cua, sinó que més aviat es tractava de la cua.

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

281
00:14:37,900 --> 00:14:39,330
Diguem que el cap és aquí.

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

283
00:14:54,900 --> 00:14:56,980
Diguem que la nostra cua es veia així.

284
00:14:56,980 --> 00:15:00,190
Si volguéssim canviar, on
el començament de la línia és,

285
00:15:00,190 --> 00:15:03,400
diguem que canviem el cap
d'aquesta manera i talles Aquí.

286
00:15:03,400 --> 00:15:07,100
>> Ara volem afegir alguna cosa a
aquesta cua, però com vostès poden veure,

287
00:15:07,100 --> 00:15:11,150
que no és tan senzill com simplement
afegir el és després que la mida

288
00:15:11,150 --> 00:15:13,630
perquè llavors ens quedem sense
límits de la nostra gamma actual.

289
00:15:13,630 --> 00:15:16,190
Quan volem afegir realment és aquí.

290
00:15:16,190 --> 00:15:18,610
Aquesta és la bellesa d'una cua
és que a nosaltres, visualment

291
00:15:18,610 --> 00:15:22,380
sembla que la línia és la següent,
però quan s'emmagatzema en una estructura de dades,

292
00:15:22,380 --> 00:15:29,370
donen com com un cicle.

293
00:15:29,370 --> 00:15:32,360
En certa manera s'embolica al voltant
a la part davantera de la mateixa manera

294
00:15:32,360 --> 00:15:34,780
que una línia també pot embolicar
tot depenent d'on sigui que

295
00:15:34,780 --> 00:15:36,279
voler principi de la línia per a ser.

296
00:15:36,279 --> 00:15:38,630
I així, si prenem una
mira aquí baix, anem a

297
00:15:38,630 --> 00:15:40,880
diem que volíem crear un
funció de trucada en cua.

298
00:15:40,880 --> 00:15:43,980
Volíem afegir int n en què q.

299
00:15:43,980 --> 00:15:49,250
Si q.size q-- Anomenarem a que les nostres dades
structure-- si el nostre queue.size no

300
00:15:49,250 --> 00:15:52,520
igual a la capacitat o si
que és menys de la capacitat,

301
00:15:52,520 --> 00:15:55,120
q.strings és la matriu dins del nostre q.

302
00:15:55,120 --> 00:15:58,380
Anem a establir
que igual a q.heads,

303
00:15:58,380 --> 00:16:02,730
que està just aquí, a més q.size
pel mòdul de capacitat, que

304
00:16:02,730 --> 00:16:04,290
ens emboliqui volta per aquí.

305
00:16:04,290 --> 00:16:08,040
>> Així, en aquest exemple, l'índex
del cap és 1, oi?

306
00:16:08,040 --> 00:16:11,480
L'índex de grandària és 0, 1, 2, 3, 4.

307
00:16:11,480 --> 00:16:19,500
Així que podem fer 1 més 4 de mòdul
per la nostra capacitat, que és 5.

308
00:16:19,500 --> 00:16:20,920
Què ens donen?

309
00:16:20,920 --> 00:16:23,270
Quin és l'índex que
que surt d'això?

310
00:16:23,270 --> 00:16:24,080
>> AUDIÈNCIA: 0.

311
00:16:24,080 --> 00:16:27,870
>> ANDI Peng: 0, el que
passa a ser aquí,

312
00:16:27,870 --> 00:16:30,640
i així volem ser capaços
per inserir en aquí.

313
00:16:30,640 --> 00:16:34,730
I així aquesta equació aquí espècie
de tan sols funciona amb qualsevol nombre

314
00:16:34,730 --> 00:16:36,750
depenent d'on el seu
cap i la seva grandària són.

315
00:16:36,750 --> 00:16:38,541
Si saps el que els
són les coses, ja saps

316
00:16:38,541 --> 00:16:43,170
exactament on vol inserir
tot el que sigui després de la seva cua.

317
00:16:43,170 --> 00:16:44,640
¿Això té sentit per a tothom?

318
00:16:44,640 --> 00:16:48,560
>> Sé la classe d'un cervell
sumari sobretot perquè aquest

319
00:16:48,560 --> 00:16:50,512
va arribar a les acaballes del seu concurs.

320
00:16:50,512 --> 00:16:52,220
Però esperem que tothom
Ara pot entendre

321
00:16:52,220 --> 00:16:57,800
per què aquesta solució o aquesta
funció és la forma en què ho és.

322
00:16:57,800 --> 00:16:59,840
Qualsevol persona una mica confús al respecte?

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

324
00:17:03,471 --> 00:17:03,970
D'ACORD.

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

326
00:17:07,109 --> 00:17:09,970
>> I ara, si vostè
volgut treure de la cua, aquesta

327
00:17:09,970 --> 00:17:15,240
és on el nostre cap seria el canvi
perquè si haguéssim de treure de la cua,

328
00:17:15,240 --> 00:17:17,030
no prenem fora de la final de la q.

329
00:17:17,030 --> 00:17:19,130
Volem treure el cap, oi?

330
00:17:19,130 --> 00:17:24,260
Així que, com a resultat, el cap canviarà,
i és per això que quan encolar,

331
00:17:24,260 --> 00:17:26,800
has de mantenir un registre de
on el seu cap i la seva mida

332
00:17:26,800 --> 00:17:29,450
han de ser capaç d'inserir
en la posició correcta.

333
00:17:29,450 --> 00:17:32,740
>> I així quan dequeue,
També Pseudocodi a terme.

334
00:17:32,740 --> 00:17:35,480
Siéntase lliure si vol
per intentar codificar aquesta fora.

335
00:17:35,480 --> 00:17:36,980
Vostè vol moure el cap, oi?

336
00:17:36,980 --> 00:17:39,320
Si volia treure de la cua, em
mouria el cap una altra vegada.

337
00:17:39,320 --> 00:17:40,800
Aquesta seria el cap.

338
00:17:40,800 --> 00:17:45,617
>> I el nostre grandària actual faria
restar perquè ja no

339
00:17:45,617 --> 00:17:46,950
tenir quatre elements de la matriu.

340
00:17:46,950 --> 00:17:51,370
Només tenim tres, i després volem
per tornar tot el que s'emmagatzema a l'interior

341
00:17:51,370 --> 00:17:56,260
del cap perquè volem aprofitar aquesta
valor a terme de manera molt similar a la pila.

342
00:17:56,260 --> 00:17:58,010
Només vostè està prenent
des d'un lloc diferent,

343
00:17:58,010 --> 00:18:01,770
i has de tornar a assignar el punter
a diferent lloc com un resultat.

344
00:18:01,770 --> 00:18:03,890
Lògicament, tothom segueix?

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

346
00:18:05,690 --> 00:18:10,156
>> OK, així que anem a parlar una mica
més en profunditat sobre llistes enllaçades

347
00:18:10,156 --> 00:18:13,280
perquè van a estar molt, molt valuosa
perquè en el transcurs d'aquesta setmana de

348
00:18:13,280 --> 00:18:14,964
conjunts de processadors.

349
00:18:14,964 --> 00:18:17,130
Llistes enllaçades, com vostès
record, tot el que són

350
00:18:17,130 --> 00:18:22,570
són nodes que són nodes de certa
valors tant d'un valor i un punter

351
00:18:22,570 --> 00:18:26,290
que estan units entre si
pels punters.

352
00:18:26,290 --> 00:18:29,880
I pel que l'estructura de com
vam crear un node aquí és que

353
00:18:29,880 --> 00:18:33,569
tenir int n, que és el
el valor en una botiga o cadena de n

354
00:18:33,569 --> 00:18:35,610
o el que vulguis
cridar-ho, l'estrella carbó n.

355
00:18:35,610 --> 00:18:41,482
Struct estrella node, que és el punter
que vostè desitja tenir en cada node,

356
00:18:41,482 --> 00:18:43,690
vostè va a haver de
punta punter cap a la següent.

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

358
00:18:48,207 --> 00:18:50,040
Vas a tenir el cap
d'una llista enllaçada que és

359
00:18:50,040 --> 00:18:53,140
va assenyalar la resta d'
els valors així successivament i així successivament

360
00:18:53,140 --> 00:18:55,290
fins a arribar finalment al final.

361
00:18:55,290 --> 00:18:58,040
I aquest últim node és només
anar a no tenir un punter.

362
00:18:58,040 --> 00:18:59,952
Es va a apuntar a
nul, i és llavors quan

363
00:18:59,952 --> 00:19:01,910
saps que has arribat a la
final de la llista enllaçada

364
00:19:01,910 --> 00:19:04,076
és quan la seva última punter
no apunta res.

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

366
00:19:06,670 --> 00:19:10,990
>> Així que anirem una mica més en
de profunditat respecte a com es faria possiblement

367
00:19:10,990 --> 00:19:12,400
cercar una llista enllaçada.

368
00:19:12,400 --> 00:19:15,460
Recorda el que són alguns dels
inconvenients de les llistes enllaçades

369
00:19:15,460 --> 00:19:19,340
versos una sèrie en relació amb les recerques.

370
00:19:19,340 --> 00:19:22,565
Una matriu pot recerca binària, però
per què no es pot fer això en una llista enllaçada?

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

372
00:19:26,834 --> 00:19:30,320
>> AUDIÈNCIA: Perquè estan tots connectats,
però no sé molt bé on

373
00:19:30,320 --> 00:19:31,330
[Inaudible].

374
00:19:31,330 --> 00:19:34,600
>> ANDI Peng: Sí, exactament per tal de recordar
que la brillantor d'un array

375
00:19:34,600 --> 00:19:37,190
va ser el fet que teníem
memòria d'accés aleatori, on

376
00:19:37,190 --> 00:19:41,580
si volia el valor de l'índex
06:00, jo podria dir que l'índex de sis,

377
00:19:41,580 --> 00:19:42,407
dóna'm aquest valor.

378
00:19:42,407 --> 00:19:45,240
I això és perquè les matrius es classifiquen
en un espai contigu de memòria

379
00:19:45,240 --> 00:19:48,020
en un sol lloc, mentre que
tipus de llistes enllaçades

380
00:19:48,020 --> 00:19:52,820
s'intercalen aleatòriament per tot arreu,
i l'única manera que vostè pot trobar un

381
00:19:52,820 --> 00:19:56,890
és a través d'un punter que et diu
l'adreça del lloc en què el pròxim node és.

382
00:19:56,890 --> 00:20:00,290
>> I així, com a resultat, l'única manera de
per buscar a través d'una llista enllaçada

383
00:20:00,290 --> 00:20:01,560
és la recerca lineal.

384
00:20:01,560 --> 00:20:05,890
Perquè jo no sé exactament on
el valor 12 a la llista enllaçada és,

385
00:20:05,890 --> 00:20:08,780
He de travessar la totalitat
d'aquesta llista enllaçada es

386
00:20:08,780 --> 00:20:12,450
per un des del cap fins al primer node,
al segon node, a la tercera node,

387
00:20:12,450 --> 00:20:17,690
tot el camí fins que finalment arribi
a on aquest node que estic buscant és.

388
00:20:17,690 --> 00:20:22,110
I així, en aquest sentit, la recerca
en una llista enllaçada és sempre n.

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

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

391
00:20:25,690 --> 00:20:28,470
>> I pel que el codi en el qual
implementem això, i això

392
00:20:28,470 --> 00:20:32,620
és una mica nou per a vostès des que
nois realment no han parlat ni mai

393
00:20:32,620 --> 00:20:35,000
punters vist en la forma de
cercar a través de punters,

394
00:20:35,000 --> 00:20:37,670
així que anem a caminar a través d'
aquesta molt, molt lentament.

395
00:20:37,670 --> 00:20:40,200
Així que la recerca bool, dreta,
imaginem que volem

396
00:20:40,200 --> 00:20:42,820
per crear una funció anomenada
recerca que retorna true

397
00:20:42,820 --> 00:20:46,820
si vostè troba un valor dins de la vinculada
llista, i retorna false en cas contrari.

398
00:20:46,820 --> 00:20:50,030
Llista d'estrelles de node és
Actualment només el punter

399
00:20:50,030 --> 00:20:52,960
al primer element de la llista enllaçada.

400
00:20:52,960 --> 00:20:56,700
int n és el valor que vostè és
buscar en aquesta llista.

401
00:20:56,700 --> 00:20:58,770
>> Així indicador de l'estrella node és igual a la llista.

402
00:20:58,770 --> 00:21:00,970
Això vol dir que estem configurant
i la creació d'un punter

403
00:21:00,970 --> 00:21:03,592
al primer node dins de la llista.

404
00:21:03,592 --> 00:21:04,300
Tothom amb mi?

405
00:21:04,300 --> 00:21:06,530
Així que si ens anirem
Torna aquí, tindria

406
00:21:06,530 --> 00:21:13,850
inicialitzat un punter que apunta a
el cap del que la llista és.

407
00:21:13,850 --> 00:21:18,600
>> I després una vegada que arribi aquí,
mentre que el punter no és igual a null,

408
00:21:18,600 --> 00:21:22,160
pel que és el bucle en el qual estem
serà posteriorment travessar

409
00:21:22,160 --> 00:21:25,940
la resta de la nostra llista perquè el
succeeix quan el punter equival a nul·la?

410
00:21:25,940 --> 00:21:27,550
Sabem que tener--

411
00:21:27,550 --> 00:21:28,450
>> AUDIÈNCIA: [inaudible]

412
00:21:28,450 --> 00:21:31,491
>> ANDI Peng: Exactament, així que sabem que
hem arribat al final de la llista, no?

413
00:21:31,491 --> 00:21:34,470
Si tornes aquí, cada node
ha d'estar apuntant a un altre node

414
00:21:34,470 --> 00:21:36,550
i així successivament i així successivament
fins a arribar, finalment,

415
00:21:36,550 --> 00:21:41,589
la cua de la llista enllaçada,
que té un punter que acaba

416
00:21:41,589 --> 00:21:43,130
no assenyala en cap altre que no.

417
00:21:43,130 --> 00:21:47,510
Així que, bàsicament, saber que
la llista encara és allà dalt

418
00:21:47,510 --> 00:21:50,900
fins que el punter no és igual a
nul·la perquè una vegada que és igual a null,

419
00:21:50,900 --> 00:21:53,310
vostè sap que no hi ha més coses.

420
00:21:53,310 --> 00:21:56,930
>> Així que aquest és el bucle en el qual estem
va a tenir la recerca real.

421
00:21:56,930 --> 00:22:01,690
I si els pointer-- fan que vegi
aquest tipus de funció sageta en ella?

422
00:22:01,690 --> 00:22:06,930
Així que si punter apunta a n, si
el punter en n és igual és igual a n,

423
00:22:06,930 --> 00:22:09,180
el que significa que si
el punter que ets

424
00:22:09,180 --> 00:22:13,420
buscar a l'extrem de cada
node és en realitat igual al valor

425
00:22:13,420 --> 00:22:15,990
que estàs buscant, llavors
desitja tornar realitat.

426
00:22:15,990 --> 00:22:19,280
Així que, bàsicament, si vostè està en un node que
té el valor que vostè està buscant,

427
00:22:19,280 --> 00:22:23,550
saps que has estat
capaç de buscar amb èxit.

428
00:22:23,550 --> 00:22:27,150
>> Altrament, desitja establir
el punter al següent node.

429
00:22:27,150 --> 00:22:28,850
Això és el que aquesta línia aquí està fent.

430
00:22:28,850 --> 00:22:31,750
Pointer és igual punter següent.

431
00:22:31,750 --> 00:22:33,360
Tothom vegi com això està treballant?

432
00:22:33,360 --> 00:22:36,580
>> I bàsicament vas a només
recórrer la totalitat de la llista,

433
00:22:36,580 --> 00:22:41,920
restablir el punter cada vegada fins
que finalment va colpejar el final de la llista.

434
00:22:41,920 --> 00:22:45,030
I vostè sap que no hi ha
més nodes per buscar a través de,

435
00:22:45,030 --> 00:22:47,999
i llavors vostè pot tornar false
perquè saps que, oh, bé,

436
00:22:47,999 --> 00:22:50,540
si jo he estat capaç de cercar
a través de la totalitat de la llista.

437
00:22:50,540 --> 00:22:54,530
Si en aquest exemple, si volia
per buscar el valor de 10,

438
00:22:54,530 --> 00:22:57,250
i em poso al capdavant, i
Jo busco fins al fons,

439
00:22:57,250 --> 00:23:00,550
i, finalment, vaig arribar a això, que
un punter que apunta a null,

440
00:23:00,550 --> 00:23:04,415
Sé que, merda, suposo que 10 no està en
aquesta llista perquè no vaig poder trobar-lo.

441
00:23:04,415 --> 00:23:06,520
I estic al final de la llista.

442
00:23:06,520 --> 00:23:11,040
I en aquest cas vostè sap
Vaig a tornar false.

443
00:23:11,040 --> 00:23:12,900
>> Anem que remull en una mica.

444
00:23:12,900 --> 00:23:17,350
Aquesta serà bastant
important per a la seva conjunt de processadors.

445
00:23:17,350 --> 00:23:21,140
La lògica que és molt simple, potser
sintàcticament simplement implementar-lo.

446
00:23:21,140 --> 00:23:23,365
Volen fer
Assegureu-vos d'entendre.

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

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

449
00:23:27,650 --> 00:23:32,560
>> OK, així que com ens hauria
la inserció de nodes, la dreta,

450
00:23:32,560 --> 00:23:35,380
en una llista perquè recordi
¿Quins són els què dels beneficis

451
00:23:35,380 --> 00:23:39,230
d'haver una llista enllaçada front
una matriu en termes d'emmagatzematge?

452
00:23:39,230 --> 00:23:41,110
>> AUDIÈNCIA: És dinàmic,
així que és més fàcil A--

453
00:23:41,110 --> 00:23:43,180
>> ANDI Peng: Exactament,
pel que és dinàmic, que

454
00:23:43,180 --> 00:23:46,880
significa que pot expandir-se i contreure
depenent de les necessitats de l'usuari.

455
00:23:46,880 --> 00:23:56,570
I així, en aquest sentit, no necessitem
a perdre la memòria innecessària perquè

456
00:23:56,570 --> 00:24:00,850
si jo no sé quants valors que vull
a la botiga, que no té sentit per a mi

457
00:24:00,850 --> 00:24:04,310
per crear una matriu causa
si vull emmagatzemar 10 valors

458
00:24:04,310 --> 00:24:08,380
i puc crear una matriu de 1000, que és
una gran quantitat de memòria perduda, assignat.

459
00:24:08,380 --> 00:24:11,180
És per això que volem utilitzar una lligat
llista per ser capaç de dinàmicament

460
00:24:11,180 --> 00:24:13,860
canviar o reduir el nostre mida.

461
00:24:13,860 --> 00:24:17,040
>> I pel que fa a la inserció
una mica més complicat.

462
00:24:17,040 --> 00:24:20,810
Ja que no podem accedir aleatòriament elements
la forma en què ens d'una matriu.

463
00:24:20,810 --> 00:24:24,270
Si vull inserir un element
en el setè índex,

464
00:24:24,270 --> 00:24:26,930
Jo només puc inserir
en el setè índex.

465
00:24:26,930 --> 00:24:30,020
En una llista enllaçada, no ho fa
bastant treballar amb la mateixa facilitat,

466
00:24:30,020 --> 00:24:34,947
i així si volíem inserir
l'un aquí a la llista enllaçada,

467
00:24:34,947 --> 00:24:36,280
visualment, és molt fàcil de veure.

468
00:24:36,280 --> 00:24:39,363
Només volem inserir allà mateix,
la dreta en el principi de la llista,

469
00:24:39,363 --> 00:24:40,840
just després del cap.

470
00:24:40,840 --> 00:24:44,579
>> Però la forma en què hem de reassignar
els punters és una mica complicat

471
00:24:44,579 --> 00:24:47,620
o, lògicament, té sentit, però
vostè vol assegurar-se que vostè ho té

472
00:24:47,620 --> 00:24:50,250
completament baix perquè
l'última cosa que vull

473
00:24:50,250 --> 00:24:52,990
és tornar a assignar un punter al
camí que estem fent aquí.

474
00:24:52,990 --> 00:24:58,170
Si eliminar la referència al
punter del cap a 1,

475
00:24:58,170 --> 00:25:01,086
després, de sobte
resta de la seva llista enllaçada

476
00:25:01,086 --> 00:25:04,680
es perd perquè vostè té en realitat no
creat un gens temporal.

477
00:25:04,680 --> 00:25:06,220
Això es va assenyalar a la 2.

478
00:25:06,220 --> 00:25:10,080
Si reassigna el punter, llavors el
resta de la seva llista està totalment perdut.

479
00:25:10,080 --> 00:25:13,310
Així que vols ser
molt, molt acurat aquí

480
00:25:13,310 --> 00:25:17,010
per assignar la primera
punter del que

481
00:25:17,010 --> 00:25:20,150
vol inserir en qualsevol lloc
que vol, i llavors

482
00:25:20,150 --> 00:25:22,710
pot eliminar la referència a la resta de la seva llista.

483
00:25:22,710 --> 00:25:25,250
>> Així que això s'aplica a qualsevol lloc
vostè està tractant d'inserir en.

484
00:25:25,250 --> 00:25:27,520
Si voleu inserir en el
cap, si vols contestar aquí,

485
00:25:27,520 --> 00:25:29,455
si voleu inserir en
Al final, bé, al final em

486
00:25:29,455 --> 00:25:30,910
suposo que ho faria només
tenir cap punter, però

487
00:25:30,910 --> 00:25:33,830
voldrà assegurar-se que vostè no ho fa
perdrà la resta de la llista.

488
00:25:33,830 --> 00:25:36,640
Un sempre vol assegurar-
el nou node apunt

489
00:25:36,640 --> 00:25:39,330
cap al que
vol inserir en,

490
00:25:39,330 --> 00:25:42,170
i llavors vostè pot afegir l'encadenament.

491
00:25:42,170 --> 00:25:43,330
Tothom clar?

492
00:25:43,330 --> 00:25:45,427
>> Això serà
un dels problemes reals.

493
00:25:45,427 --> 00:25:48,010
Un dels problemes de la majoria de les
vostè va a tenir en el seu conjunt de processadors

494
00:25:48,010 --> 00:25:51,340
és que vostè va a tractar de crear
una llista enllaçada i les coses d'inserció

495
00:25:51,340 --> 00:25:53,340
però llavors només perdrà el
resta de la seva llista enllaçada.

496
00:25:53,340 --> 00:25:54,900
I tu seràs com,
no sé per què està succeint això?

497
00:25:54,900 --> 00:25:58,040
I és un dolor de passar per
i buscar tots els seus punters.

498
00:25:58,040 --> 00:26:02,100
>> I et garanteixo en aquest conjunt de processadors,
escriure i dibuixar aquests nodes fora

499
00:26:02,100 --> 00:26:03,344
serà molt, molt servicial.

500
00:26:03,344 --> 00:26:06,010
Així que vostè pot mantenir per complet la pista
d'on tots els seus punters són,

501
00:26:06,010 --> 00:26:08,540
el que va malament,
on tots els nodes són,

502
00:26:08,540 --> 00:26:12,660
el que ha de fer per accedir o
inserir o eliminar o qualsevol d'ells.

503
00:26:12,660 --> 00:26:14,550
Tothom bé amb això?

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

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

506
00:26:19,300 --> 00:26:22,600
>> Així que si volíem mirar el codi?

507
00:26:22,600 --> 00:26:24,470
Oh, no sé si
pot veure ell-- OK, així

508
00:26:24,470 --> 00:26:27,940
a la part superior de tot el que és és una funció
inserit anomenat on volem

509
00:26:27,940 --> 00:26:31,365
inserir int n en la llista enllaçada.

510
00:26:31,365 --> 00:26:32,740
Anem a caminar a través d'això.

511
00:26:32,740 --> 00:26:34,770
És una gran quantitat de codi, una gran quantitat de nova sintaxi.

512
00:26:34,770 --> 00:26:36,220
Estarem bé.

513
00:26:36,220 --> 00:26:39,120
>> Així que a la part superior, sempre que sigui
volem crear res

514
00:26:39,120 --> 00:26:42,380
¿Què és el que hem de fer, especialment si vostè
vull que no s'emmagatzema a la pila

515
00:26:42,380 --> 00:26:43,920
però en el munt?

516
00:26:43,920 --> 00:26:45,460
Anem a un malloc, oi?

517
00:26:45,460 --> 00:26:48,240
Així que anem a crear un punter.

518
00:26:48,240 --> 00:26:52,074
Nodes, punter, nous iguals
malloc la mida d'un node

519
00:26:52,074 --> 00:26:53,740
perquè volem que el node que es crearà.

520
00:26:53,740 --> 00:26:56,720
Volem que la quantitat de
memòria que un node ocupa

521
00:26:56,720 --> 00:26:59,300
per ser assignat per al
creació del nou node.

522
00:26:59,300 --> 00:27:02,270
>> I després anem a comprovar per
veure si els nous iguals és igual a zero.

523
00:27:02,270 --> 00:27:03,370
Recorda el que vam dir?

524
00:27:03,370 --> 00:27:06,470
Facis el que malloc,
¿Què ha de fer sempre?

525
00:27:06,470 --> 00:27:09,490
Vostè ha de comprovar sempre per veure
si és o no és nul.

526
00:27:09,490 --> 00:27:13,620
>> Per exemple, si el seu funcionament
sistema estava completament ple,

527
00:27:13,620 --> 00:27:17,060
si no tingués més memòria en
tot i tractes de malloc,

528
00:27:17,060 --> 00:27:18,410
tornaria nul per a vostè.

529
00:27:18,410 --> 00:27:21,094
I pel que si intenta utilitzar-
quan s'estava apuntant a null,

530
00:27:21,094 --> 00:27:23,260
no vas a poder
per accedir a aquesta informació.

531
00:27:23,260 --> 00:27:27,010
I així, com a tal, hem volgut fer
Assegureu-vos que cada vegada que estiguis mallocing,

532
00:27:27,010 --> 00:27:30,500
sempre estàs comprovant si
que la memòria que li ha assignat és nul.

533
00:27:30,500 --> 00:27:33,670
I si no ho és, llavors podem moure
amb la resta del nostre codi.

534
00:27:33,670 --> 00:27:36,140
>> Així que anem a
inicialitzar el nou node.

535
00:27:36,140 --> 00:27:39,050
Farem nova n és igual a n.

536
00:27:39,050 --> 00:27:42,390
I després farem
setembre nou el punter de nou

537
00:27:42,390 --> 00:27:46,900
en nul perquè en aquest moment no ho fem
vull res perquè apunti a.

538
00:27:46,900 --> 00:27:48,755
No tenim ni idea d'on
que posarà vostè,

539
00:27:48,755 --> 00:27:50,630
i després, si volem
inserir al cap,

540
00:27:50,630 --> 00:27:53,820
llavors podem reassignar
el punter al capdavant.

541
00:27:53,820 --> 00:27:58,530
Tothom segueix la lògica
d'on això està passant?

542
00:27:58,530 --> 00:28:02,502
>> Tot el que estem fent és crear una nova
node, establint el punter a null,

543
00:28:02,502 --> 00:28:04,210
i després reassignar
al cap si

544
00:28:04,210 --> 00:28:06,320
sabem que volem per inserir al cap.

545
00:28:06,320 --> 00:28:09,420
I llavors el cap va a
apuntar cap a aquest nou node.

546
00:28:09,420 --> 00:28:11,060
Tothom d'acord amb això?

547
00:28:11,060 --> 00:28:12,380
>> Així que és un procés de dos passos.

548
00:28:12,380 --> 00:28:14,760
Cal assignar primer
el que està creant.

549
00:28:14,760 --> 00:28:18,260
Establir aquest punter a la
referència, i després

550
00:28:18,260 --> 00:28:21,400
pot espècie d'eliminar la referència
la primera punter

551
00:28:21,400 --> 00:28:22,972
i apunti cap al nou node.

552
00:28:22,972 --> 00:28:25,680
On sigui que vol inserir,
que la lògica va ser veritat.

553
00:28:25,680 --> 00:28:27,530
>> És una cosa així com l'assignació de
variables temporals.

554
00:28:27,530 --> 00:28:28,700
Recordi, vostè té
per assegurar-se que vostè

555
00:28:28,700 --> 00:28:30,346
no perdre de vista que si estàs intercanviant.

556
00:28:30,346 --> 00:28:33,470
Vostè vol assegurar-se que vostè té un
variable temporal aquest tipus de guarda

557
00:28:33,470 --> 00:28:35,620
la pista d'on aquesta cosa
s'emmagatzema perquè

558
00:28:35,620 --> 00:28:41,190
no perdi cap valor en el curs
de com jugar una mica amb ell.

559
00:28:41,190 --> 00:28:42,710
>> OK, així que el codi estarà aquí.

560
00:28:42,710 --> 00:28:45,020
Vostès mirin després de la secció.

561
00:28:45,020 --> 00:28:48,060
Serà allà.

562
00:28:48,060 --> 00:28:50,280
>> Així que suposo que ho fa
aquesta diferència si volíem

563
00:28:50,280 --> 00:28:52,300
per inserir al mig o al final?

564
00:28:52,300 --> 00:28:57,892
Algú té una idea del que és la
pseudocodi com la referència lògica

565
00:28:57,892 --> 00:29:00,350
que prendríem si volíem
per inserir-lo al mig?

566
00:29:00,350 --> 00:29:03,391
Així que si volíem per inserir-lo al
cap, tot el que fem és crear un nou node.

567
00:29:03,391 --> 00:29:06,311
Hem creat el punter d'aquest
nou node a qualsevol que sigui el cap,

568
00:29:06,311 --> 00:29:08,310
i després ens vam posar al cap
al nou node, oi?

569
00:29:08,310 --> 00:29:11,560
Si volguéssim per inserir-lo al mig
de la llista, el que hauríem de fer?

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

571
00:29:14,108 --> 00:29:16,110
>> AUDIÈNCIA: Seguiria
ser un procés similar

572
00:29:16,110 --> 00:29:19,114
de com l'assignació de punter i
després assignar aquest punter,

573
00:29:19,114 --> 00:29:20,530
però hauríem de situar allà.

574
00:29:20,530 --> 00:29:23,560
>> ANDI Peng: Exactament, així que exactament
el mateix procés, excepte vostè

575
00:29:23,560 --> 00:29:27,820
que localitzar el lloc exacte que
vol que el nou punter a entrar en,

576
00:29:27,820 --> 00:29:44,790
pel que si vull inserir en
el mitjà de lligat pel·lícules-- OK,

577
00:29:44,790 --> 00:29:46,370
diguem que és la nostra llista enllaçada.

578
00:29:46,370 --> 00:29:49,500
Si volem inserir aquí mateix,
crearem un nou node.

579
00:29:49,500 --> 00:29:50,520
Anem a malloc.

580
00:29:50,520 --> 00:29:52,220
Crearem un nou node.

581
00:29:52,220 --> 00:29:55,940
Anem a assignar el
punter d'aquest node aquí.

582
00:29:55,940 --> 00:29:58,335
>> Però el problema que difereix
des d'on el cap és

583
00:29:58,335 --> 00:30:00,490
és que sabíem exactament
on el cap és.

584
00:30:00,490 --> 00:30:01,930
Va ser just en el primer, no?

585
00:30:01,930 --> 00:30:04,870
Però aquí hem de seguir la pista
d'on estem inserir-lo en.

586
00:30:04,870 --> 00:30:07,930
Si estem inserint la nostra
node d'aquí, tenim

587
00:30:07,930 --> 00:30:12,270
per assegurar-se que la
anterior a aquest node

588
00:30:12,270 --> 00:30:14,172
és el que reassigna el punter.

589
00:30:14,172 --> 00:30:16,380
Llavors vostè ha de tipus de
no perdre de vista dues coses.

590
00:30:16,380 --> 00:30:19,420
Si es manté la pista d'on aquesta
node actualment està inserint en.

591
00:30:19,420 --> 00:30:23,280
També cal perdre de vista on
el node anterior que vostè està buscant en

592
00:30:23,280 --> 00:30:24,340
També hi era.

593
00:30:24,340 --> 00:30:25,830
Tothom bé amb això?

594
00:30:25,830 --> 00:30:26,500
D'ACORD.

595
00:30:26,500 --> 00:30:28,000
>> Què hi ha de la inserció al final?

596
00:30:28,000 --> 00:30:34,220
Si jo volia afegir que aquí-- si volia
afegir un nou node a la final d'una llista,

597
00:30:34,220 --> 00:30:37,009
Com podria jo anar fent això?

598
00:30:37,009 --> 00:30:39,300
AUDIÈNCIA: Llavors, en l'actualitat, la
assenyalar l'última a nul.

599
00:30:39,300 --> 00:30:40,960
ANDI Peng: Sí.

600
00:30:40,960 --> 00:30:43,560
Exactament, així que aquest
Actualment es va assenyalar a conèixer,

601
00:30:43,560 --> 00:30:46,720
i així que suposo que, en aquest sentit, és
molt fàcil afegir al final d'una llista.

602
00:30:46,720 --> 00:30:51,810
Tot el que has de fer és establir que
igual a null i després auge.

603
00:30:51,810 --> 00:30:53,070
Allà mateix, molt fàcil.

604
00:30:53,070 --> 00:30:53,960
Molt senzill.

605
00:30:53,960 --> 00:30:56,430
>> Molt similar a la
cap, però lògicament que

606
00:30:56,430 --> 00:30:59,690
voldrà assegurar-se que els passos
prendre cap fer res d'això,

607
00:30:59,690 --> 00:31:01,500
estàs seguint.

608
00:31:01,500 --> 00:31:04,420
És molt fàcil, al mig
del seu codi, posar-se al dia,

609
00:31:04,420 --> 00:31:05,671
oh, tinc tants punters.

610
00:31:05,671 --> 00:31:07,461
Jo no sé d'on
res està assenyalant.

611
00:31:07,461 --> 00:31:09,170
Ni tan sols sé què node estic.

612
00:31:09,170 --> 00:31:11,490
Què està passant?

613
00:31:11,490 --> 00:31:13,620
>> Relaxeu-vos, calmar-se, prendre una respiració profunda.

614
00:31:13,620 --> 00:31:15,530
Dibuixa la teva llista enllaçada.

615
00:31:15,530 --> 00:31:18,800
Si dius, sé on exactament
Necessito inserir això en

616
00:31:18,800 --> 00:31:22,970
i sé exactament com reassignar meu
punters, molt, molt més fàcil d'imaginar

617
00:31:22,970 --> 00:31:27,200
fora-- molt, molt més fàcil no
perdre en els errors del seu codi.

618
00:31:27,200 --> 00:31:29,410
Tothom d'acord amb això?

619
00:31:29,410 --> 00:31:31,380
D'ACORD.

620
00:31:31,380 --> 00:31:35,120
>> Així que suposo que un concepte que no tenim
realment parlat fins ara,

621
00:31:35,120 --> 00:31:38,131
i jo el crec, probablement
no es trobarà molt yet--

622
00:31:38,131 --> 00:31:40,880
és una espècie de concept-- avançada
és que en realitat tenim una dada

623
00:31:40,880 --> 00:31:43,900
estructura anomenada una llista doblement enllaçada.

624
00:31:43,900 --> 00:31:46,390
Així com vostès poden veure,
tot el que estem fent és crear

625
00:31:46,390 --> 00:31:50,400
un valor real, un extra
capdavanter en cadascun dels nostres nodes

626
00:31:50,400 --> 00:31:52,660
que també apunta al node anterior.

627
00:31:52,660 --> 00:31:58,170
Així que no només tenim la nostra
nodes apunten a la següent.

628
00:31:58,170 --> 00:32:01,430
També apunten a l'anterior.

629
00:32:01,430 --> 00:32:04,310
Vaig a ignorar aquests dos ara.

630
00:32:04,310 --> 00:32:06,740
>> Llavors vostè té una cadena
que es pot moure en tots dos sentits,

631
00:32:06,740 --> 00:32:09,630
i llavors és una mica més fàcil
seguir lògicament junt.

632
00:32:09,630 --> 00:32:11,896
Igual que aquí, en lloc de
no perdre de vista, oh,

633
00:32:11,896 --> 00:32:14,520
ha de saber que aquest node és
el que he de tornar a assignar,

634
00:32:14,520 --> 00:32:17,532
Jo només puc anar aquí i
simplement tiri de l'anterior.

635
00:32:17,532 --> 00:32:19,490
Llavors sé exactament on
és a dir, i llavors

636
00:32:19,490 --> 00:32:21,130
no han de travessar la
totalitat de la llista enllaçada.

637
00:32:21,130 --> 00:32:22,180
És una mica més fàcil.

638
00:32:22,180 --> 00:32:24,960
>> Però com a tal, té una doble
la quantitat de punters,

639
00:32:24,960 --> 00:32:26,960
això és el doble de la quantitat de memòria.

640
00:32:26,960 --> 00:32:28,950
És un munt de consells per a no perdre de vista.

641
00:32:28,950 --> 00:32:32,140
És una mica més complex, però és
una mica més fàcil d'usar funció

642
00:32:32,140 --> 00:32:34,080
en el que estem tractant d'aconseguir.

643
00:32:34,080 --> 00:32:36,910
>> Així que aquest tipus de dades
estructura totalment existeix,

644
00:32:36,910 --> 00:32:40,280
i l'estructura de és molt, molt
simple, excepte tot el que està tenint és a dir,

645
00:32:40,280 --> 00:32:43,850
en lloc de només un punter al següent,
vostè també té un punter a l'anterior.

646
00:32:43,850 --> 00:32:45,940
Aquesta és tota la diferència va ser.

647
00:32:45,940 --> 00:32:47,740
Tothom bé amb això?

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

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

650
00:32:50,940 --> 00:32:53,280
>> Molt bé, així que ara estic
passar molt probablement

651
00:32:53,280 --> 00:32:56,870
com 15 a 20 minuts o el major
de la resta del temps en la secció

652
00:32:56,870 --> 00:32:58,360
parlant sobre taules hash.

653
00:32:58,360 --> 00:33:02,590
Quants de vostès
han llegit spec pset5?

654
00:33:02,590 --> 00:33:03,620
Molt bé, molt bé.

655
00:33:03,620 --> 00:33:06,160
Això és més alt que el 50% dels normalment.

656
00:33:06,160 --> 00:33:07,560
Està bé.

657
00:33:07,560 --> 00:33:10,345
>> Així com vostès veuran,
ets desafiament en pset5

658
00:33:10,345 --> 00:33:16,790
serà la d'aplicar un diccionari
on es carrega més de 140.000 paraules

659
00:33:16,790 --> 00:33:20,610
que li donem i corrector ortogràfic
contra tot el text.

660
00:33:20,610 --> 00:33:22,580
Li donarem a l'atzar
peces de la literatura.

661
00:33:22,580 --> 00:33:23,520
Li donarem l'Odissea.

662
00:33:23,520 --> 00:33:24,561
Li donarem la Ilíada.

663
00:33:24,561 --> 00:33:26,350
Li donarem Austin Powers.

664
00:33:26,350 --> 00:33:28,220
>> I el seu repte
serà de lletrejar verificació

665
00:33:28,220 --> 00:33:31,760
cada paraula en tot
d'aquests diccionaris

666
00:33:31,760 --> 00:33:34,960
essencialment amb el nostre corrector ortogràfic.

667
00:33:34,960 --> 00:33:38,620
I així hi ha algunes parts
de la creació d'aquest conjunt de processadors,

668
00:33:38,620 --> 00:33:41,970
primer que vols ser
capaç de carregar realitat

669
00:33:41,970 --> 00:33:43,970
totes les paraules en el seu
diccionari, i després

670
00:33:43,970 --> 00:33:45,530
vull ser capaç de
revisar l'ortografia de tots ells.

671
00:33:45,530 --> 00:33:48,780
I així, com a tal, vostè va a requerir
una estructura de dades que pot fer això ràpid

672
00:33:48,780 --> 00:33:50,790
i eficientment i de forma dinàmica.

673
00:33:50,790 --> 00:33:52,900
>> Així que suposo que el més fàcil
manera de fer això,

674
00:33:52,900 --> 00:33:55,010
probablement crear una matriu, no?

675
00:33:55,010 --> 00:33:58,910
La forma més senzilla d'emmagatzematge que és
pot crear una matriu de 140.000 paraules

676
00:33:58,910 --> 00:34:03,400
i acaba de col·locar a tots allí i
després travessar els binari de cerca

677
00:34:03,400 --> 00:34:06,780
o seleccions o no--
sento que això classificació.

678
00:34:06,780 --> 00:34:10,729
Pot ordenar-los i després recórrer els
per recerca binària o de cerca simplement lineal

679
00:34:10,729 --> 00:34:13,730
i just finals de les paraules, però que
té una enorme quantitat de memòria,

680
00:34:13,730 --> 00:34:15,190
i no és molt eficient.

681
00:34:15,190 --> 00:34:18,350
>> Així que anem a començar
parlant de formes de fer

682
00:34:18,350 --> 00:34:20,110
nostre temps de funcionament més eficient.

683
00:34:20,110 --> 00:34:23,190
I el nostre objectiu és aconseguir
constant de temps on

684
00:34:23,190 --> 00:34:25,810
és gairebé com arrays, on
vostè té accés instantani.

685
00:34:25,810 --> 00:34:28,560
Si volia buscar alguna cosa,
Vull ser capaç de simplement,

686
00:34:28,560 --> 00:34:30,810
auge, saber exactament, i tiri d'ella.

687
00:34:30,810 --> 00:34:34,100
I així una estructura en la qual
estarem tornant molt a prop

688
00:34:34,100 --> 00:34:37,569
per poder accedir a la constant
temps, aquest sant grial

689
00:34:37,569 --> 00:34:41,370
en la programació de la constant
temps es diu una taula hash.

690
00:34:41,370 --> 00:34:45,370
I així David va esmentar anteriorment la
[Inaudible] una mica en la conferència,

691
00:34:45,370 --> 00:34:49,100
però anem a realment
busseig en profunditat aquesta setmana

692
00:34:49,100 --> 00:34:51,780
en una peça que està en relació amb
com una taula hash funciona.

693
00:34:51,780 --> 00:34:53,949
>> Així que la forma en què un hash
obres de taula, per exemple,

694
00:34:53,949 --> 00:35:00,230
si volia guardar un munt de paraules, un
manat de paraules en l'idioma anglès,

695
00:35:00,230 --> 00:35:02,940
Jo teòricament podria posar
plàtan, poma, kiwi, mango, parell,

696
00:35:02,940 --> 00:35:04,980
i meló tot en tot just una matriu.

697
00:35:04,980 --> 00:35:07,044
Tots ells podrien encaixar i ser trobar.

698
00:35:07,044 --> 00:35:09,210
Seria una mena de mal de
buscar a través d'i l'accés,

699
00:35:09,210 --> 00:35:12,920
però la manera més fàcil de fer això és
que podem crear en realitat una estructura

700
00:35:12,920 --> 00:35:15,680
cridada una taula hash on hash.

701
00:35:15,680 --> 00:35:19,880
Correm totes les nostres claus a través
una funció hash, una equació,

702
00:35:19,880 --> 00:35:22,600
que tots ells es converteix en
una espècie d'un valor

703
00:35:22,600 --> 00:35:28,740
que podem emmagatzemar en
essencialment un conjunt de llista enllaçada.

704
00:35:28,740 --> 00:35:32,570
>> I aquí, si volíem
per emmagatzemar les paraules en anglès,

705
00:35:32,570 --> 00:35:37,250
podríem potencialment simplement, no fer
saber, convertir totes les primeres lletres

706
00:35:37,250 --> 00:35:39,630
en una mena d'un nombre.

707
00:35:39,630 --> 00:35:43,140
I així, per exemple, si volia
Un ésser sinònim de Apple--

708
00:35:43,140 --> 00:35:47,460
o amb l'índex de 0, i
B a ser sinònim d'1,

709
00:35:47,460 --> 00:35:51,030
podem tenir 26 entrades
que només pot emmagatzemar

710
00:35:51,030 --> 00:35:53,610
totes les lletres del
alfabet que començarem amb.

711
00:35:53,610 --> 00:35:56,130
I després podem tenir
poma en l'índex de 0.

712
00:35:56,130 --> 00:35:59,160
Podem tenir plàtan en l'índex de
1, el meló en l'índex de 2,

713
00:35:59,160 --> 00:36:00,540
i així successivament i així successivament.

714
00:36:00,540 --> 00:36:04,460
I així si volia buscar
la meva hash de taula i l'accés de la poma,

715
00:36:04,460 --> 00:36:07,560
Sigues poma comença amb
una A, i sé exactament

716
00:36:07,560 --> 00:36:10,860
que ha de ser i el hash
taula en l'índex 0, perquè

717
00:36:10,860 --> 00:36:13,620
de la funció assignada prèviament.

718
00:36:13,620 --> 00:36:16,572
>> Així que no sé, som
un programa d'usuari, on

719
00:36:16,572 --> 00:36:18,780
se l'acusa de
no arbitrarily-- arbitràriament,

720
00:36:18,780 --> 00:36:22,530
amb intentar pensatiu
pensar en bones equacions

721
00:36:22,530 --> 00:36:25,460
ser capaç de propagar-
a terme tots els seus valors

722
00:36:25,460 --> 00:36:29,370
de manera que puguin accedir fàcilment
més endavant amb com una equació

723
00:36:29,370 --> 00:36:31,130
que vostè, vostè mateix, saben.

724
00:36:31,130 --> 00:36:35,210
Així, en el sentit que si volia anar a
mànec, ho sé, oh, comença amb m.

725
00:36:35,210 --> 00:36:37,134
Ha de ser en l'índex de 12.

726
00:36:37,134 --> 00:36:38,800
Jo no he de buscar a través de qualsevol cosa.

727
00:36:38,800 --> 00:36:42,080
Sigues exactly-- tan sols pogués anar a
l'índex de 12 i tiri d'això.

728
00:36:42,080 --> 00:36:45,520
>> Tothom clara sobre com 1
La funció de taula hash funciona?

729
00:36:45,520 --> 00:36:48,380
És una espècie de només un conjunt més complex.

730
00:36:48,380 --> 00:36:50,010
Això és tot el que és.

731
00:36:50,010 --> 00:36:51,630
D'ACORD.

732
00:36:51,630 --> 00:36:57,690
>> Així que suposo que ens trobem
aquest tema del que

733
00:36:57,690 --> 00:37:06,390
que passa si té diverses coses
que li donen el mateix índex?

734
00:37:06,390 --> 00:37:10,570
Així que dir que la nostra funció, tot el que
va fer va ser prendre aquesta primera carta

735
00:37:10,570 --> 00:37:14,490
i convertir això en un
0 respectiva a través de 25 d'índex.

736
00:37:14,490 --> 00:37:17,137
Això és totalment bé si
és suficient amb un de cada un.

737
00:37:17,137 --> 00:37:18,970
Però el segon de començar
tenir més, ets

738
00:37:18,970 --> 00:37:20,910
va a tenir el que s'anomena una col·lisió.

739
00:37:20,910 --> 00:37:25,580
>> Així que si intento inserir enterrar en un hash
taula que ja té el plàtan en ell,

740
00:37:25,580 --> 00:37:27,870
el que passarà quan
intenta inserir això?

741
00:37:27,870 --> 00:37:30,930
Les coses dolentes perquè el plàtan
que ja existeix en l'índex

742
00:37:30,930 --> 00:37:33,800
que desitja emmagatzemar-lo en.

743
00:37:33,800 --> 00:37:35,560
Berry tipus de és com, ah, què faig?

744
00:37:35,560 --> 00:37:37,080
No sé a on anar.

745
00:37:37,080 --> 00:37:38,410
Com puc solucionar això?

746
00:37:38,410 --> 00:37:41,150
>> I així vostès faran classe de
veiem que fem aquesta cosa difícil

747
00:37:41,150 --> 00:37:44,810
on podem tipus de realitat
crear llista enllaçada a les nostres matrius.

748
00:37:44,810 --> 00:37:46,840
I així, la manera més fàcil
per pensar en això,

749
00:37:46,840 --> 00:37:50,830
totes taula hash és una
varietat de llistes enllaçades.

750
00:37:50,830 --> 00:37:55,670
I així, en aquest sentit, cal
aquest bell arranjament d'apuntadors,

751
00:37:55,670 --> 00:37:58,740
i després cada punter en
aquest valor, en aquest índex,

752
00:37:58,740 --> 00:38:00,740
en realitat pot apuntar a altres coses.

753
00:38:00,740 --> 00:38:05,720
I pel que té tots aquests separada
cadenes que surten d'una gran varietat.

754
00:38:05,720 --> 00:38:07,960
>> I aquí, si jo
volgut inserir baia,

755
00:38:07,960 --> 00:38:11,220
Ja ho sé, OK, vaig a l'entrada
a través de la meva funció hash.

756
00:38:11,220 --> 00:38:15,070
Vaig a acabar amb l'índex de
1, i després em vaig a ser capaç de tenir

757
00:38:15,070 --> 00:38:20,410
només un subconjunt més petit d'aquest
gegant diccionari de 140.000 paraules.

758
00:38:20,410 --> 00:38:24,220
I llavors puc simplement mirar
a través de 1/26 d'això.

759
00:38:24,220 --> 00:38:27,910
>> I així llavors puc només cal inserir
baia ja sigui abans o després de plàtan

760
00:38:27,910 --> 00:38:28,820
en aquest cas?

761
00:38:28,820 --> 00:38:29,700
Després, oi?

762
00:38:29,700 --> 00:38:33,920
I pel que anem a voler
inserir aquest node després de plàtan,

763
00:38:33,920 --> 00:38:36,667
i així vas a inserir
a la cua de la llista enllaçada.

764
00:38:36,667 --> 00:38:38,500
Vaig a tornar
a aquesta diapositiva anterior,

765
00:38:38,500 --> 00:38:40,680
així que vostès poden veure com
funció hash funciona.

766
00:38:40,680 --> 00:38:43,980
>> Així funció hash és aquesta equació
que s'està executant la classe de la seva entrada

767
00:38:43,980 --> 00:38:46,940
a través d'aconseguir el Índex
que desitja assignar la directa cap.

768
00:38:46,940 --> 00:38:51,130
I així, en aquest exemple, tot el que volíem
de fer era prendre la primera lletra,

769
00:38:51,130 --> 00:38:55,890
convertir això en un índex, llavors nosaltres
pot emmagatzemar que en la nostra funció hash.

770
00:38:55,890 --> 00:39:00,160
Tot el que estem fent aquí és que estem
la conversió de la primera lletra.

771
00:39:00,160 --> 00:39:04,770
Així KeyKey [0] és només la primera lletra
de qualsevol cadena que estem tenint,

772
00:39:04,770 --> 00:39:05,720
estem passant.

773
00:39:05,720 --> 00:39:09,740
Estem convertir això a superior, i
estem restant per majúscules A,

774
00:39:09,740 --> 00:39:11,740
així que tot el que està fent
ens està donant una sèrie

775
00:39:11,740 --> 00:39:13,670
en el qual podem hash dels nostres valors en.

776
00:39:13,670 --> 00:39:16,550
>> I després anem a
tornar picada MIDA mòdul.

777
00:39:16,550 --> 00:39:19,340
Sigui molt, molt acurat
perquè, en teoria, aquí

778
00:39:19,340 --> 00:39:21,870
seu valor de resum podria ser infinita.

779
00:39:21,870 --> 00:39:23,660
Només podria seguir i seguir i seguir.

780
00:39:23,660 --> 00:39:26,080
Podria ser alguna cosa realment,
molt gran valor,

781
00:39:26,080 --> 00:39:29,849
sinó perquè la seva taula hash que
vostè ha creat només compta amb 26 índexs,

782
00:39:29,849 --> 00:39:31,890
vostè vol assegurar-se que la seva
modulusing perquè

783
00:39:31,890 --> 00:39:33,848
no run-- és el mateix
cosa com la seva queue--

784
00:39:33,848 --> 00:39:36,320
perquè no es quedi fora de la
part inferior de la funció hash.

785
00:39:36,320 --> 00:39:39,210
>> Vostè vol embolicar volta
de la mateixa manera a [inaudible] quan

786
00:39:39,210 --> 00:39:41,750
que tenia com un molt,
gran carta,

787
00:39:41,750 --> 00:39:43,740
no vull que això
n'hi ha prou amb executar fora de la final.

788
00:39:43,740 --> 00:39:46,948
El mateix aquí, vostè vol assegurar-se
no s'executa fora de la final embolicant

789
00:39:46,948 --> 00:39:48,330
voltant de la part superior de la taula.

790
00:39:48,330 --> 00:39:50,530
Així que això és només una molt
funció hash simple.

791
00:39:50,530 --> 00:39:56,570
Tot el que va fer va ser prendre la primera
carta de qualsevol que sigui la nostra entrada era

792
00:39:56,570 --> 00:40:01,660
i convertir això en un índex que
podríem posar a la nostra taula hash.

793
00:40:01,660 --> 00:40:05,450
>> Sí, i així com he dit abans,
la forma en què resolem col·lisions

794
00:40:05,450 --> 00:40:09,330
en el nostre hash de taules estan tenint,
el que anomenem, encadenament.

795
00:40:09,330 --> 00:40:13,860
Així que si vostè intenta inserir múltiples
paraules que comencen amb la mateixa cosa,

796
00:40:13,860 --> 00:40:16,145
vostè va a tenir un valor de resum.

797
00:40:16,145 --> 00:40:18,770
Alvocats i poma, si tens
executar a través de la nostra funció hash,

798
00:40:18,770 --> 00:40:21,450
es va a donar la
mateix nombre, el nombre de 0.

799
00:40:21,450 --> 00:40:24,550
I així, la forma en què resoldre això és
que podem realment bo de vincular-

800
00:40:24,550 --> 00:40:27,010
si a través de llistes enllaçades.

801
00:40:27,010 --> 00:40:29,600
>> I així, en aquest sentit,
vostès poden veure tipus

802
00:40:29,600 --> 00:40:32,640
de com les estructures de dades que
hem estat establint prèviament

803
00:40:32,640 --> 00:40:35,870
com una passa lligat llista tipus
de poden unir-se en una de sola.

804
00:40:35,870 --> 00:40:38,860
I llavors vostè pot crear ara
estructures de dades més eficients

805
00:40:38,860 --> 00:40:43,350
que pot manejar grans quantitats de
dades, canviar la mida de forma dinàmica en funció

806
00:40:43,350 --> 00:40:44,870
de les seves necessitats.

807
00:40:44,870 --> 00:40:45,620
Tothom clar?

808
00:40:45,620 --> 00:40:47,580
Tothom la classe de clara
en el que passa aquí?

809
00:40:47,580 --> 00:40:52,110
>> Si volia insert-- el que és un
fruita que comença amb, no sé,

810
00:40:52,110 --> 00:40:54,726
B, amb excepció de la baia, plàtan.

811
00:40:54,726 --> 00:40:55,710
>> AUDIÈNCIA: Blackberry.

812
00:40:55,710 --> 00:40:57,910
>> ANDI Peng: Blackberry, blackberry.

813
00:40:57,910 --> 00:41:00,530
D'on ve la esbarzer anar aquí?

814
00:41:00,530 --> 00:41:04,251
Bé, en realitat no hem classificat
això encara, però teòricament

815
00:41:04,251 --> 00:41:06,250
si volíem tenir aquest
en ordre alfabètic,

816
00:41:06,250 --> 00:41:07,944
on la mora s'ha d'anar?

817
00:41:07,944 --> 00:41:09,210
>> AUDIÈNCIA: [inaudible]

818
00:41:09,210 --> 00:41:11,100
>> ANDI Peng: Exactament, després d'aquí, no?

819
00:41:11,100 --> 00:41:14,950
Però ja que és molt difícil
reorder-- Suposo que depèn de vostès.

820
00:41:14,950 --> 00:41:17,920
Vostès poden totalment
implementar el que vulguis.

821
00:41:17,920 --> 00:41:20,730
La forma més eficient
de fer això potser

822
00:41:20,730 --> 00:41:24,570
seria per ordenar la teva vinculats
una llista en ordre alfabètic,

823
00:41:24,570 --> 00:41:26,520
i així quan estàs
inserint coses, desitja

824
00:41:26,520 --> 00:41:28,632
per assegurar-se inserir
en ordre alfabètic

825
00:41:28,632 --> 00:41:30,590
perquè després, quan estigui
tractant de buscar ells,

826
00:41:30,590 --> 00:41:32,410
vostè no ha de travessar tot.

827
00:41:32,410 --> 00:41:35,290
Vostè sap exactament on
que és, i que és més fàcil.

828
00:41:35,290 --> 00:41:39,100
>> Però si que tipus de tenir
coses barrejades a l'atzar,

829
00:41:39,100 --> 00:41:41,420
vostè encara va a tenir
per travessar totes maneres.

830
00:41:41,420 --> 00:41:44,990
I així, si volia simplement
inseriu blackberry aquí

831
00:41:44,990 --> 00:41:47,470
i volia buscar
que, sé, oh, blackberry

832
00:41:47,470 --> 00:41:52,012
ha de començar amb l'índex d'1, així que
saber instantàniament només la recerca en 1.

833
00:41:52,012 --> 00:41:53,970
I llavors puc classe de
recórrer la llista enllaçada

834
00:41:53,970 --> 00:41:56,120
fins que arribi a la mora,
i llavors-- ¿sí?

835
00:41:56,120 --> 00:41:59,550
>> AUDIÈNCIA: Si vostè està tractant de create--
Suposo que aquesta és una molt simple de hash

836
00:41:59,550 --> 00:42:00,050
funció.

837
00:42:00,050 --> 00:42:02,835
I si el que volíem fer
múltiples capes de que igual que,

838
00:42:02,835 --> 00:42:05,870
OK, volem separar en
com totes les lletres de l'alfabet

839
00:42:05,870 --> 00:42:09,040
i després una altra vegada a com un altre conjunt
de les lletres de l'alfabet en què,

840
00:42:09,040 --> 00:42:11,715
estem posant com un hash
taula dins d'una taula hash,

841
00:42:11,715 --> 00:42:13,256
o com una funció dins d'una funció?

842
00:42:13,256 --> 00:42:14,880
O és que--

843
00:42:14,880 --> 00:42:17,510
>> ANDI Peng: Així que el seu picada
function-- seva taula hash

844
00:42:17,510 --> 00:42:19,360
pot ser tan gran com vostè desitja.

845
00:42:19,360 --> 00:42:21,930
Així que en aquest sentit, vaig pensar
va ser molt fàcil, molt

846
00:42:21,930 --> 00:42:25,320
simple per a mi basen només una espècie
en lletres de la primera paraula.

847
00:42:25,320 --> 00:42:28,690
I així, només hi ha 26 opcions.

848
00:42:28,690 --> 00:42:32,650
Només puc obtenir 26 opcions de
0 a 25, ja que només pot

849
00:42:32,650 --> 00:42:36,510
començar de l'A a la Z. Però Si volies
afegir, potser, una major complexitat

850
00:42:36,510 --> 00:42:39,260
o més ràpid el temps d'execució del seu
taula hash, malgrat tot

851
00:42:39,260 --> 00:42:40,760
pot fer tot tipus de coses.

852
00:42:40,760 --> 00:42:43,330
Vostè pot fer el seu propi
equació que li dóna

853
00:42:43,330 --> 00:42:48,000
més distribució en el seu
paraules, llavors quan vostè busca,

854
00:42:48,000 --> 00:42:49,300
que serà més ràpid.

855
00:42:49,300 --> 00:42:52,100
>> És totalment de vostès
com vol implementar això.

856
00:42:52,100 --> 00:42:55,140
Penseu en això com només cubs.

857
00:42:55,140 --> 00:42:57,376
Si jo volia tenir
26 cubs, vaig

858
00:42:57,376 --> 00:42:59,420
per ordenar les coses en aquests cubs.

859
00:42:59,420 --> 00:43:02,980
Però jo vaig a tenir un munt
de coses a cada cub,

860
00:43:02,980 --> 00:43:05,890
així que si vostè vol que sigui
més ràpid i més eficient,

861
00:43:05,890 --> 00:43:07,190
dóna'm cent cubs.

862
00:43:07,190 --> 00:43:09,290
>> Però llavors vostè ha de trobar una
manera d'ordenar les coses pel que són

863
00:43:09,290 --> 00:43:11,040
en el cub adequat han d'estar en.

864
00:43:11,040 --> 00:43:13,331
Però després, quan en realitat
que desitgi veure a la galleda,

865
00:43:13,331 --> 00:43:16,410
que és molt més ràpid perquè hi ha
menys coses a cada cub.

866
00:43:16,410 --> 00:43:20,250
I així, sí, això és en realitat
el truc per a vostès en pset5

867
00:43:20,250 --> 00:43:22,360
és que podràs
el repte de crear només

868
00:43:22,360 --> 00:43:26,170
tot el que és el més eficient
funció que es pugui imaginar per a ser

869
00:43:26,170 --> 00:43:28,520
capaç d'emmagatzemar i comprovar aquests valors.

870
00:43:28,520 --> 00:43:30,840
>> Totalment d'vostès
però vostè vol fer-ho,

871
00:43:30,840 --> 00:43:32,229
però això és un molt bon punt.

872
00:43:32,229 --> 00:43:34,520
Que el tipus de lògica que
vull començar a pensar en

873
00:43:34,520 --> 00:43:37,236
és, també, per què no puc fer més cubs.

874
00:43:37,236 --> 00:43:39,527
I llavors he de buscar
menys coses, i llavors potser

875
00:43:39,527 --> 00:43:41,640
tenir una funció de hash diferent.

876
00:43:41,640 --> 00:43:45,500
>> Sí, hi ha un munt de maneres de fer això
pset, alguns són més ràpids que altres.

877
00:43:45,500 --> 00:43:50,630
Estic totalment d'anar a veure el
va ser ràpid els nois de més ràpid voluntat

878
00:43:50,630 --> 00:43:55,170
ser capaç d'obtenir les seves funcions per treballar.

879
00:43:55,170 --> 00:43:58,176
OK, tots bé en
taules d'encadenament i croquetes?

880
00:43:58,176 --> 00:44:00,800
En realitat és com un molt simple
concepte, si es pensa en això.

881
00:44:00,800 --> 00:44:05,160
Tot el que és és el que separa
les seves entrades són en cubs,

882
00:44:05,160 --> 00:44:10,670
classificar-los, i després buscar el
llistes que no està associada amb.

883
00:44:10,670 --> 00:44:11,852
>> Fresc.

884
00:44:11,852 --> 00:44:18,160
Molt bé, ara tenim una espècie diferent
d'estructura de dades que es diu un arbre.

885
00:44:18,160 --> 00:44:20,850
Seguim i parlar d'intents
que són clarament diferents,

886
00:44:20,850 --> 00:44:22,330
però en la mateixa categoria.

887
00:44:22,330 --> 00:44:29,010
Essencialment, tot és un arbre en lloc
d'organitzar les dades en la forma lineal

888
00:44:29,010 --> 00:44:32,560
que una taula hash que does--
sabem, té una part superior i una part inferior

889
00:44:32,560 --> 00:44:37,900
i quin tipus d'enllaç fora de it-- 1
arbre té un superior que es diu a l'arrel,

890
00:44:37,900 --> 00:44:40,220
i llavors té fulles al seu voltant.

891
00:44:40,220 --> 00:44:42,390
>> I així, tot el que tens aquí
és només el node superior

892
00:44:42,390 --> 00:44:45,980
que apunta a altres nodes, que els punts
a més nodes, i així successivament i així successivament.

893
00:44:45,980 --> 00:44:48,130
I pel que només té branques de divisió.

894
00:44:48,130 --> 00:44:53,255
És només una forma diferent d'organitzar
dades, i perquè en diem un arbre,

895
00:44:53,255 --> 00:44:56,270
vostès sol-- és només
modelada a buscar un arbre.

896
00:44:56,270 --> 00:44:57,670
És per això que en diem arbres.

897
00:44:57,670 --> 00:44:59,370
>> Taula hash s'assembla a una taula.

898
00:44:59,370 --> 00:45:01,310
Un arbre només s'assembla a un arbre.

899
00:45:01,310 --> 00:45:03,300
Tot el que és és una separada
forma d'organitzar els nodes

900
00:45:03,300 --> 00:45:06,020
depenent de quines són les seves necessitats.

901
00:45:06,020 --> 00:45:11,810
>> Així que hi ha una arrel i
llavors vostè té fulles.

902
00:45:11,810 --> 00:45:15,380
La forma en què podem particular
pensar-hi és un arbre binari,

903
00:45:15,380 --> 00:45:18,150
un arbre binari és només una
tipus específic d'un arbre

904
00:45:18,150 --> 00:45:22,450
on cada node únics punts
que, en el màxim, dos nodes.

905
00:45:22,450 --> 00:45:25,434
I així que aquí teniu diferent
simetria en el seu arbre

906
00:45:25,434 --> 00:45:28,600
que fa que sigui més fàcil de tipus de mirada
en quins valors són perquè llavors

907
00:45:28,600 --> 00:45:30,150
tenir sempre a l'esquerra o la dreta.

908
00:45:30,150 --> 00:45:33,150
Mai hi ha com una tercera esquerra des
l'esquerra o quart des de l'esquerra.

909
00:45:33,150 --> 00:45:36,358
És només vostè té una esquerra i una dreta
i vostè pot buscar qualsevol dels dos.

910
00:45:36,358 --> 00:45:38,980
I per què és això útil?

911
00:45:38,980 --> 00:45:40,980
La forma en que això és
útil és que si estàs buscant

912
00:45:40,980 --> 00:45:42,890
per buscar a través de valors, no?

913
00:45:42,890 --> 00:45:45,640
En lloc d'implementar binari
buscar en una matriu d'error,

914
00:45:45,640 --> 00:45:49,260
si vostè vol ser capaç d'inserir nodes
i treure-li nodes a voluntat i també

915
00:45:49,260 --> 00:45:52,185
preservar la recerca
capacitats de cerca binària.

916
00:45:52,185 --> 00:45:54,560
Així d'aquesta manera, estem tipus de
tricking-- recordar quan ens

917
00:45:54,560 --> 00:45:56,530
dit llistes enllaçades no pot binari de cerca?

918
00:45:56,530 --> 00:46:01,700
Estem espècie de la creació d'una estructura de dades
que trucs que a treballar.

919
00:46:01,700 --> 00:46:05,034
>> I les llistes perquè vinculats són lineals,
que només enllacen un després de l'altre.

920
00:46:05,034 --> 00:46:06,950
Podem tipus de tenir
diferent tipus de punters

921
00:46:06,950 --> 00:46:09,408
que apunten a diferents nodes
que ens pot ajudar amb la cerca.

922
00:46:09,408 --> 00:46:12,590
I aquí, si volia
tenir un arbre de cerca binària,

923
00:46:12,590 --> 00:46:14,090
Jo sé que el meu mitjà si 55.

924
00:46:14,090 --> 00:46:18,280
Jo només vaig a crear aquest
com el meu mitjà, com el meu arrel,

925
00:46:18,280 --> 00:46:20,770
i després em vaig a tenir
valors giren fora d'ella.

926
00:46:20,770 --> 00:46:25,610
>> Així que aquí, si jo vaig a buscar
el valor de 66, puc començar als 55.

927
00:46:25,610 --> 00:46:27,310
És 66 més gran que 55?

928
00:46:27,310 --> 00:46:30,970
Sí que ho és, així que sé que busco mus
i n el punter dret d'aquest arbre.

929
00:46:30,970 --> 00:46:32,440
Vaig al 77.

930
00:46:32,440 --> 00:46:35,367
OK, és 66 menor o major que 77?

931
00:46:35,367 --> 00:46:37,950
És menor que, pel que sé, oh,
que ha de ser el node de l'esquerra.

932
00:46:37,950 --> 00:46:41,410
>> Així que aquí estem tipus de preservació
totes les grans coses sobre matrius,

933
00:46:41,410 --> 00:46:44,420
així com el canvi de mida dinàmic
d'objectes, sent

934
00:46:44,420 --> 00:46:49,530
capaç d'inserir i eliminar a voluntat,
sense haver de preocupar-se pel fix

935
00:46:49,530 --> 00:46:50,370
quantitat d'espai.

936
00:46:50,370 --> 00:46:52,820
Encara conservem tots
aquestes coses meravelloses

937
00:46:52,820 --> 00:46:57,140
al mateix temps ser capaç de preservar la
registrar i buscar el temps de recerca binària

938
00:46:57,140 --> 00:47:00,450
que només estàvem prèviament
capaç d'obtenir una frase.

939
00:47:00,450 --> 00:47:06,310
>> Estructura de dades fresca, tipus de
complex d'implementar, el node.

940
00:47:06,310 --> 00:47:08,311
Com es pot veure, tot el que
és l'estructura del node

941
00:47:08,311 --> 00:47:10,143
és que vostè té a l'esquerra
i un punter dret.

942
00:47:10,143 --> 00:47:11,044
Això és tot el que és.

943
00:47:11,044 --> 00:47:12,960
Així que en lloc de només
que té una x o una anterior.

944
00:47:12,960 --> 00:47:15,920
Vostè té una esquerra o una dreta i després
pots tipus d'enllaçar-

945
00:47:15,920 --> 00:47:16,836
No obstant això així ho desitja.

946
00:47:16,836 --> 00:47:21,080

947
00:47:21,080 --> 00:47:24,270
>> OK, estem en realitat va
simplement prendre uns minuts.

948
00:47:24,270 --> 00:47:25,790
Així que anem a tornar aquí.

949
00:47:25,790 --> 00:47:28,270
Com he dit anteriorment,
Jo com que vaig explicar

950
00:47:28,270 --> 00:47:31,520
la lògica darrere de la forma en què
seria buscar a través d'això.

951
00:47:31,520 --> 00:47:33,860
Anem a tractar
pseudocoding això a veure

952
00:47:33,860 --> 00:47:38,000
si podem aplicar el tipus de
mateixa lògica de cerca binària

953
00:47:38,000 --> 00:47:40,055
a un tipus diferent d'estructura de dades.

954
00:47:40,055 --> 00:47:45,049
Si vostès volen prendre com una parella
minuts per només pensar en això.

955
00:47:45,049 --> 00:48:45,927

956
00:48:45,927 --> 00:48:46,925
D'ACORD.

957
00:48:46,925 --> 00:48:51,407
Molt bé, vaig a
en realitat només li donen ell-- no,

958
00:48:51,407 --> 00:48:52,990
parlarem sobre el pseudocodi primer.

959
00:48:52,990 --> 00:48:56,580
Així que no vol que ningú
per donar una punyalada en el

960
00:48:56,580 --> 00:49:02,100
el primer que vol fer quan
vostè està començant la recerca és?

961
00:49:02,100 --> 00:49:04,460
Si estem buscant
el valor de 66, el que és

962
00:49:04,460 --> 00:49:07,940
el primer que volem fer en cas de
volem binari buscar aquest arbre?

963
00:49:07,940 --> 00:49:10,760
>> AUDIÈNCIA: Vols veure a la dreta
i buscar esquerra i veure [inaudible]

964
00:49:10,760 --> 00:49:11,230
major nombre.

965
00:49:11,230 --> 00:49:12,271
>> ANDI Peng: Sí, exactament.

966
00:49:12,271 --> 00:49:15,350
Així que anem a mirar a la seva arrel.

967
00:49:15,350 --> 00:49:18,180
Hi ha un munt de maneres que vostè pot trucar
que, diuen a la seva gent node pare.

968
00:49:18,180 --> 00:49:21,317
M'agrada dir que l'arrel perquè
això és com l'arrel de l'arbre.

969
00:49:21,317 --> 00:49:23,400
Vostè va a mirar
el node arrel, i ja està

970
00:49:23,400 --> 00:49:26,940
veurem és 66 més
que o menor que 55.

971
00:49:26,940 --> 00:49:30,360
I si és més gran que, a més, és
més gran que, cap a on volem veure?

972
00:49:30,360 --> 00:49:32,000
On volem buscar, no?

973
00:49:32,000 --> 00:49:34,340
Volem buscar la
meitat dreta d'aquest arbre.

974
00:49:34,340 --> 00:49:38,390
>> Així tenim que, convenientment, 1
punter que apunta a la dreta.

975
00:49:38,390 --> 00:49:44,325
I així llavors podem establir
la nostra nova arrel per ser 77.

976
00:49:44,325 --> 00:49:46,450
Només podem anar on vulgui
el punter està apuntant.

977
00:49:46,450 --> 00:49:49,100
Bé, oh, aquí estem començant
als 77, i podem simplement

978
00:49:49,100 --> 00:49:51,172
fer això de forma recursiva i una altra.

979
00:49:51,172 --> 00:49:52,880
D'aquesta manera, vostè classe
tenir una funció.

980
00:49:52,880 --> 00:49:57,430
Vostè té una manera de buscar que
simplement pot repetir una i altra vegada i una altra,

981
00:49:57,430 --> 00:50:02,720
depenent d'on vols buscar
fins que finalment arribi al valor

982
00:50:02,720 --> 00:50:04,730
que vostè està buscant.

983
00:50:04,730 --> 00:50:05,230
Té sentit?

984
00:50:05,230 --> 00:50:07,800
>> Estic a punt de mostrar que l'actual
codi, i és una gran quantitat de codi.

985
00:50:07,800 --> 00:50:08,674
No hi ha necessitat de s'espanti.

986
00:50:08,674 --> 00:50:09,910
Parlarem a través d'ell.

987
00:50:09,910 --> 00:50:13,410

988
00:50:13,410 --> 00:50:14,020
>> En realitat, no.

989
00:50:14,020 --> 00:50:15,061
Això va ser només pseudocodi.

990
00:50:15,061 --> 00:50:17,860
OK, això va ser només el pseudocodi,
que és una mica complex,

991
00:50:17,860 --> 00:50:19,751
però és totalment bé.

992
00:50:19,751 --> 00:50:21,000
Tothom seguint al llarg d'aquí?

993
00:50:21,000 --> 00:50:24,260
Si l'arrel és nul, el retorn
fals, perquè això significa

994
00:50:24,260 --> 00:50:26,850
que ni tan sols té res allà.

995
00:50:26,850 --> 00:50:31,376
>> Si l'arrel n és el valor, pel que si
passa a ser el que vostè està mirant,

996
00:50:31,376 --> 00:50:34,000
llavors vostè va a tornar true
perquè saps que ho has vist.

997
00:50:34,000 --> 00:50:36,250
Però si el valor és menor
arran de n, ets

998
00:50:36,250 --> 00:50:38,332
anar a buscar a l'esquerra
nen o el full esquerra,

999
00:50:38,332 --> 00:50:39,540
el que vulguis dir.

1000
00:50:39,540 --> 00:50:41,750
I si el valor és més gran que l'arrel,
vostè va a buscar l'arbre adequat,

1001
00:50:41,750 --> 00:50:44,610
després simplement executar la funció
a través de la recerca de nou.

1002
00:50:44,610 --> 00:50:48,037
>> I si l'arrel és nul, que aquesta
vol dir que ha arribat al final?

1003
00:50:48,037 --> 00:50:50,120
Això vol dir que no té
més més fulles per buscar,

1004
00:50:50,120 --> 00:50:52,230
llavors vostè sap, oh,
suposo que no hi ha aquí

1005
00:50:52,230 --> 00:50:55,063
perquè després he mirat a través
tot l'assumpte i no és aquí,

1006
00:50:55,063 --> 00:50:56,930
que només podria no ser aquí.

1007
00:50:56,930 --> 00:50:58,350
>> ¿Això té sentit per a tothom?

1008
00:50:58,350 --> 00:51:03,230
Així és com la recerca binària preservar
les capacitats de llistes enllaçades.

1009
00:51:03,230 --> 00:51:09,200
Fresc, de manera que el segon tipus
de l'estructura de dades que vostès

1010
00:51:09,200 --> 00:51:13,180
pot provar l'aplicació en el seu conjunt de processadors,
només has de triar un mètode.

1011
00:51:13,180 --> 00:51:19,430
Però potser un mètode alternatiu per
la taula hash és el que anomenem un trie.

1012
00:51:19,430 --> 00:51:24,080
>> Tot un trie és un
tipus específic d'arbre que

1013
00:51:24,080 --> 00:51:28,600
té valors que van a altres valors.

1014
00:51:28,600 --> 00:51:31,450
Així que en lloc de tenir un binari
arbre en el sentit que només un

1015
00:51:31,450 --> 00:51:35,940
El pot apuntar a dos, vostè pot tenir
punt d'una cosa a moltes, moltes coses.

1016
00:51:35,940 --> 00:51:39,450
Vostè essencialment té arrays
dins dels quals s'emmagatzemen

1017
00:51:39,450 --> 00:51:41,790
punters que apunten a altres matrius.

1018
00:51:41,790 --> 00:51:45,210

1019
00:51:45,210 --> 00:51:49,460
>> Així que el node de la forma en què
definiria 1 trie

1020
00:51:49,460 --> 00:51:52,590
és que volem tenir un
Boole, c paraula, oi?

1021
00:51:52,590 --> 00:51:54,920
Així que el node és de Boole
com a veritable o falsa,

1022
00:51:54,920 --> 00:51:58,490
en primer lloc al capdavant de
aquesta matriu, es tracta d'una paraula?

1023
00:51:58,490 --> 00:52:03,620
En segon lloc, vostè vol tenir punters
al que la resta d'ells ho són.

1024
00:52:03,620 --> 00:52:07,470
Una mica complex, una mica abstracte, però
Vaig a explicar el que tots els mitjans.

1025
00:52:07,470 --> 00:52:13,800
>> Així que aquí, a la part superior, si
té un arsenal ja va declarar,

1026
00:52:13,800 --> 00:52:17,040
un node on es té una de Boole
valor emmagatzemat a la part davantera

1027
00:52:17,040 --> 00:52:19,490
que li diu que és aquesta una paraula?

1028
00:52:19,490 --> 00:52:20,520
¿No és això una paraula?

1029
00:52:20,520 --> 00:52:23,240
I llavors vostè té la
resta de la seva matriu que

1030
00:52:23,240 --> 00:52:26,040
realment emmagatzema tota la
possibilitats del que podria ser.

1031
00:52:26,040 --> 00:52:28,660
Així, per exemple, com
a la part superior que té

1032
00:52:28,660 --> 00:52:32,140
el primer que diu veritat o
fals, sí o no, es tracta d'una paraula.

1033
00:52:32,140 --> 00:52:38,130
>> I llavors vostè té de 0 a 26 de
les lletres que es poden emmagatzemar.

1034
00:52:38,130 --> 00:52:42,790
Si volgués buscar aquí
de pal, me'n vaig a la part superior

1035
00:52:42,790 --> 00:52:49,200
i busco B. Trobada B en el meu
matriu, i pel que sé, està bé, és B una paraula?

1036
00:52:49,200 --> 00:52:53,010
B no és una paraula, per tant,
He de seguir buscant.

1037
00:52:53,010 --> 00:52:56,410
Vaig de B, i miro a la
punter que apunta cap a B

1038
00:52:56,410 --> 00:53:00,900
i veig una altra gamma d'informació,
la mateixa estructura que teníem abans.

1039
00:53:00,900 --> 00:53:05,240
>> I aquí-- oh, la propera
carta a la [inaudible] és A.

1040
00:53:05,240 --> 00:53:07,210
Així que mirem en aquesta matriu.

1041
00:53:07,210 --> 00:53:10,860
Ens trobem amb el vuitè valor,
i després mirem a veure, oh,

1042
00:53:10,860 --> 00:53:12,840
bo, és que una paraula, és B-A una paraula?

1043
00:53:12,840 --> 00:53:13,807
No és una paraula.

1044
00:53:13,807 --> 00:53:14,890
Hem de seguir buscant.

1045
00:53:14,890 --> 00:53:17,850
>> I així llavors mirem cap a on
el punter d'un punts,

1046
00:53:17,850 --> 00:53:21,130
i apunta a una altra forma en
que tenim més valor emmagatzemat.

1047
00:53:21,130 --> 00:53:24,150
I, finalment, arribem a
B-A-T, que és una paraula.

1048
00:53:24,150 --> 00:53:25,970
I així, la propera vegada
es mira, vas

1049
00:53:25,970 --> 00:53:30,850
per tenir el registre d'entrada de, sí,
aquesta funció booleana és veritable.

1050
00:53:30,850 --> 00:53:35,450
I així, en el sentit que estem tipus
d'haver un arbre amb matrius.

1051
00:53:35,450 --> 00:53:39,890
>> Així que vostè pot classe de recerca sota.

1052
00:53:39,890 --> 00:53:43,650
En lloc d'una funció de hash i
l'assignació de valors de llista enllaçada,

1053
00:53:43,650 --> 00:53:49,190
que només pot posar en pràctica un
trie que busca downwords.

1054
00:53:49,190 --> 00:53:50,850
Molt, molt complicat les coses.

1055
00:53:50,850 --> 00:53:54,060
No és fàcil de pensar, perquè jo sóc com
escopir tantes estructures de dades fora

1056
00:53:54,060 --> 00:53:58,710
a tu, però ho fa a tots tipus de
entendre com funciona la lògica d'això?

1057
00:53:58,710 --> 00:54:01,920
>> D'acord, guai.

1058
00:54:01,920 --> 00:54:05,600
Així B-A-T, i després
vostè va a buscar.

1059
00:54:05,600 --> 00:54:07,940
La propera vegada que et vas
per veure, oh, bé, això és cert,

1060
00:54:07,940 --> 00:54:09,273
per tant sé que això ha de ser una paraula.

1061
00:54:09,273 --> 00:54:12,030

1062
00:54:12,030 --> 00:54:13,770
>> El mateix per al zoològic.

1063
00:54:13,770 --> 00:54:17,960
Així que aquí està la cosa ara mateix, si
volgut buscar zoològic, en aquest moment,

1064
00:54:17,960 --> 00:54:20,780
Actualment zoològic no és un
paraula en el diccionari

1065
00:54:20,780 --> 00:54:25,300
perquè, com vostès poden veure, el
primer lloc que tenim un booleà

1066
00:54:25,300 --> 00:54:28,590
return true és al final del zoom.

1067
00:54:28,590 --> 00:54:30,430
Tenim Z-O-O-M.

1068
00:54:30,430 --> 00:54:33,900
>> I aquí, no en realitat tenim
la paraula, el zoològic, al diccionari

1069
00:54:33,900 --> 00:54:36,070
perquè aquesta casella no està marcada.

1070
00:54:36,070 --> 00:54:39,540
Així que l'equip no
saber que el zoològic és una paraula

1071
00:54:39,540 --> 00:54:42,430
perquè la forma en què hem
emmagatzemada, només un zoom aquí

1072
00:54:42,430 --> 00:54:44,920
en realitat té un valor booleà
això s'ha convertit cert.

1073
00:54:44,920 --> 00:54:49,380
Així que si volem inserir el
paraula, parc zoològic, en el nostre diccionari,

1074
00:54:49,380 --> 00:54:51,770
¿Com podríem anar fent això?

1075
00:54:51,770 --> 00:54:55,960
Què hem de fer per assegurar-nos que el nostre
ordinador sap que Z-O-O és una paraula

1076
00:54:55,960 --> 00:54:58,130
i no és la primera paraula és Z-O-O-M?

1077
00:54:58,130 --> 00:54:59,360
>> AUDIÈNCIA: [inaudible]

1078
00:54:59,360 --> 00:55:01,450
>> ANDI Peng: Exactament, ens
voldrà assegurar-se que aquest

1079
00:55:01,450 --> 00:55:07,890
aquí, que el valor booleà és
comprovar a part que és veritat.

1080
00:55:07,890 --> 00:55:13,297
Z-O-O, a continuació, anem a comprovar que,
així que sabem exactament, hey, el zoològic és una paraula.

1081
00:55:13,297 --> 00:55:15,380
Vaig a dir-li al
equip que és una paraula tan

1082
00:55:15,380 --> 00:55:18,000
que quan els controls informàtics,
se sap que el zoològic és una paraula.

1083
00:55:18,000 --> 00:55:21,269
>> A causa de recordar totes aquestes dades
estructures, és molt fàcil per a nosaltres

1084
00:55:21,269 --> 00:55:22,310
dir, oh, bat d'una paraula.

1085
00:55:22,310 --> 00:55:22,851
Zoo és una paraula.

1086
00:55:22,851 --> 00:55:23,611
Ampliar una paraula.

1087
00:55:23,611 --> 00:55:25,860
Però quan vostè està construint ell,
l'equip té ni idea.

1088
00:55:25,860 --> 00:55:28,619
>> Així que has de dir-li exactament
¿En quin punt es tracta d'una paraula?

1089
00:55:28,619 --> 00:55:29,910
En quin punt no és que una paraula?

1090
00:55:29,910 --> 00:55:31,784
I ¿en quin moment fer jo
de buscar coses,

1091
00:55:31,784 --> 00:55:34,000
i en quin moment què he d'anar ara?

1092
00:55:34,000 --> 00:55:37,010
Tothom clara d'això?

1093
00:55:37,010 --> 00:55:39,540
Fresc.

1094
00:55:39,540 --> 00:55:42,530
>> I llavors ve la
problema de com ho faríem

1095
00:55:42,530 --> 00:55:45,560
anar sobre la inserció d'alguna cosa
que en realitat no hi és?

1096
00:55:45,560 --> 00:55:49,090
Així que diguem que volem inserir
la paraula, bany, en la nostra trie.

1097
00:55:49,090 --> 00:55:53,589
Com vostès poden veure com actualment
tot el que tenim ara és B-A-T,

1098
00:55:53,589 --> 00:55:55,630
i aquesta nova estructura de dades
Tenia una pinta que

1099
00:55:55,630 --> 00:55:59,740
assenyalat nul·la perquè suposem
que, oh, no hi ha paraules després de B-A-T,

1100
00:55:59,740 --> 00:56:02,530
Per què necessitem per mantenir
tenir les coses després que T.

1101
00:56:02,530 --> 00:56:06,581
>> Però el problema sorgeix si fem que
vull tenir una paraula que ve després

1102
00:56:06,581 --> 00:56:07,080
del T.

1103
00:56:07,080 --> 00:56:09,500
Si vostè té bany, ets
voldrà un dret H.

1104
00:56:09,500 --> 00:56:13,290
I així el camí que farem això és
crearem un node separat.

1105
00:56:13,290 --> 00:56:16,840
No estem assignem qualsevol quantitat
de la memòria d'aquesta nova matriu,

1106
00:56:16,840 --> 00:56:20,720
i anem a assignar punters.

1107
00:56:20,720 --> 00:56:22,947
>> Anem a assignar el
H, En primer lloc, aquest nul·la,

1108
00:56:22,947 --> 00:56:24,030
anem a desfer-se'n.

1109
00:56:24,030 --> 00:56:26,590
Tindrem
els baix del punt H.

1110
00:56:26,590 --> 00:56:30,600
Si veiem una H, volem que
anar a un altre lloc.

1111
00:56:30,600 --> 00:56:33,910
>> Aquí, podem llavors marqui si.

1112
00:56:33,910 --> 00:56:38,170
Si arribem a una H després de la T, oh,
llavors sabem que es tracta d'una paraula.

1113
00:56:38,170 --> 00:56:41,110
El booleana va tornar realitat.

1114
00:56:41,110 --> 00:56:42,950
Tothom clara sobre com va succeir això?

1115
00:56:42,950 --> 00:56:45,110
D'ACORD.

1116
00:56:45,110 --> 00:56:47,214
>> Per tant, bàsicament, tots
aquestes estructures de dades

1117
00:56:47,214 --> 00:56:50,130
que hem repassat l'actualitat, tinc
anat per sobre d'ells molt, molt ràpidament

1118
00:56:50,130 --> 00:56:52,192
i no en molt
detall, i això està bé.

1119
00:56:52,192 --> 00:56:53,900
Una vegada que comenci a jugar
amb ella, podràs

1120
00:56:53,900 --> 00:56:55,733
no perdre de vista on
tots els punters són,

1121
00:56:55,733 --> 00:56:58,060
el que està passant al seu
estructures de dades, etcètera.

1122
00:56:58,060 --> 00:56:59,810
Seran molt útil,
i li toca a vostè

1123
00:56:59,810 --> 00:57:03,890
nois per esbrinar totalment com
vol implementar coses.

1124
00:57:03,890 --> 00:57:07,650
>> I així pset4, de 5-- oh, això és incorrecte.

1125
00:57:07,650 --> 00:57:10,140
Pset5 és faltes d'ortografia.

1126
00:57:10,140 --> 00:57:13,710
Com he dit abans, vostè va a, un cop
una altra vegada, descarrega el codi font de nosaltres.

1127
00:57:13,710 --> 00:57:16,210
No hi haurà tres principals
Coses que es descarreguen.

1128
00:57:16,210 --> 00:57:18,470
Esteu descarregar els diccionaris,
kers i textos.

1129
00:57:18,470 --> 00:57:21,660
>> Totes aquestes coses són són
ja sigui diccionaris de paraules

1130
00:57:21,660 --> 00:57:25,190
que volem que vostè comprovi
o la prova de la informació

1131
00:57:25,190 --> 00:57:26,930
que volem que el corrector ortogràfic.

1132
00:57:26,930 --> 00:57:29,670
I així els diccionaris
donem vas

1133
00:57:29,670 --> 00:57:34,870
per donar-li paraules reals que volem
que li permet emmagatzemar d'alguna manera en una forma que és

1134
00:57:34,870 --> 00:57:36,530
més eficient que una matriu.

1135
00:57:36,530 --> 00:57:38,470
I a continuació, els textos són
va ser el que som

1136
00:57:38,470 --> 00:57:43,900
demanant-li que corrector ortogràfic per assegurar
totes les paraules són paraules reals allà.

1137
00:57:43,900 --> 00:57:47,970
>> I així els tres blocs de
programes que li donarem

1138
00:57:47,970 --> 00:57:51,130
es diuen dictionary.c,
dictionary.h, i speller.c.

1139
00:57:51,130 --> 00:57:56,500
I després tot es fa dictionary.c
el que se li demana que implementar.

1140
00:57:56,500 --> 00:57:57,880
Càrrega paraules.

1141
00:57:57,880 --> 00:58:02,000
S'expliquen els controls, i s'assegura
que tot el que s'ha inserit correctament.

1142
00:58:02,000 --> 00:58:05,180
>> diction.h és només un arxiu de biblioteca
que declara totes aquestes funcions.

1143
00:58:05,180 --> 00:58:07,650
I speller.c, anem a donar-li.

1144
00:58:07,650 --> 00:58:09,290
No cal modificar res d'això.

1145
00:58:09,290 --> 00:58:14,290
Tot speller.c no és prendre que,
el carrega, comprova la velocitat de la mateixa,

1146
00:58:14,290 --> 00:58:19,190
posa a prova el punt de referència de com la forma
ràpidament que ets capaç de fer les coses.

1147
00:58:19,190 --> 00:58:20,410
>> És un corrector ortogràfic.

1148
00:58:20,410 --> 00:58:23,920
Simplement no vulguis saber res d'ella, però que
Assegureu-vos d'entendre el que està fent.

1149
00:58:23,920 --> 00:58:28,090
Nosaltres fem servir una funció anomenada getrusage que
posa a prova el rendiment del seu encanteri

1150
00:58:28,090 --> 00:58:28,590
corrector.

1151
00:58:28,590 --> 00:58:32,200
Tot el que fa és bàsicament provar la
temps de tot en el seu diccionari,

1152
00:58:32,200 --> 00:58:33,680
així que assegura't que ho entens.

1153
00:58:33,680 --> 00:58:36,660
Aneu amb compte de no ficar-se amb ella o
les altres coses no funcionaran correctament.

1154
00:58:36,660 --> 00:58:39,740

1155
00:58:39,740 --> 00:58:44,170
>> I la major part d'aquest desafiament és per
nois Per modificar realment dictionary.c.

1156
00:58:44,170 --> 00:58:48,526
Anem a donar-li
140.000 paraules en un diccionari.

1157
00:58:48,526 --> 00:58:50,900
Anem a donar-li un text
arxiu que té aquestes paraules,

1158
00:58:50,900 --> 00:58:54,840
i volem que vostè sigui capaç d'organitzar
en una taula de hash o trie

1159
00:58:54,840 --> 00:58:58,140
perquè quan li demanem que lletrejar
check-- imaginar si ets encanteri

1160
00:58:58,140 --> 00:59:00,690
comprovar com l'Odissea d'Homer.

1161
00:59:00,690 --> 00:59:03,010
És com aquest gran, gran prova ,.

1162
00:59:03,010 --> 00:59:05,190
>> Imagineu si tots i cada un
paraula que calia mirar

1163
00:59:05,190 --> 00:59:08,100
a través d'una matriu de 140.000 valors.

1164
00:59:08,100 --> 00:59:10,350
Això portaria per sempre
per a la seva màquina per córrer.

1165
00:59:10,350 --> 00:59:14,490
Per això volem organitzar la nostra
dades en estructures de dades més eficients

1166
00:59:14,490 --> 00:59:17,270
com una taula hash o trie.

1167
00:59:17,270 --> 00:59:20,700
I llavors vostès poden classe
de quan es busca l'accés

1168
00:59:20,700 --> 00:59:22,570
les coses més fàcilment i amb més rapidesa.

1169
00:59:22,570 --> 00:59:24,934
>> I així que vés amb compte per resoldre les col·lisions.

1170
00:59:24,934 --> 00:59:27,350
Vas a tenir un munt
de paraules d'aquest començament amb A.

1171
00:59:27,350 --> 00:59:29,957
Vas a aconseguir un grapat paraules
de començar amb B. Fins que

1172
00:59:29,957 --> 00:59:31,290
nois com vols resoldre-ho.

1173
00:59:31,290 --> 00:59:34,144
Potser hi ha més
funció hash eficient

1174
00:59:34,144 --> 00:59:36,810
que només la primera lletra
alguna cosa, i pel que toca a vostè

1175
00:59:36,810 --> 00:59:38,190
nois per fer la classe del que vulguis.

1176
00:59:38,190 --> 00:59:40,148
>> Potser vulgueu afegir
totes les lletres juntes.

1177
00:59:40,148 --> 00:59:43,410
Potser vostè vol agradaria fer coses estranyes
per tenir en compte el nombre de lletres,

1178
00:59:43,410 --> 00:59:43,970
el que sigui.

1179
00:59:43,970 --> 00:59:45,386
Fins que vostès el que vols fer.

1180
00:59:45,386 --> 00:59:49,262
Si vols fer una taula hash, si vostè
Intenta-ho d'un trie, totalment de vostè.

1181
00:59:49,262 --> 00:59:52,470
Vaig a advertir davant de temps que el
trie és típicament una mica més difícil

1182
00:59:52,470 --> 00:59:54,520
només perquè hi ha molt
més punters a no perdre de vista.

1183
00:59:54,520 --> 00:59:55,645
Però totalment de vostès.

1184
00:59:55,645 --> 00:59:58,742
És molt més eficient
en la majoria dels casos.

1185
00:59:58,742 --> 01:00:01,450
Vols ser realment capaç de mantenir
un registre de tots els seus punters.

1186
01:00:01,450 --> 01:00:03,850
Com fer la mateixa cosa
que estava fent aquí.

1187
01:00:03,850 --> 01:00:06,871
Quan vostè està tractant d'inserir
valors en una taula hash o eliminar,

1188
01:00:06,871 --> 01:00:08,620
assegureu-vos que vostè és
realment fer el seguiment

1189
01:00:08,620 --> 01:00:11,860
d'on tot és degut
és molt fàcil perquè si jo sóc

1190
01:00:11,860 --> 01:00:14,727
intentar inserir com la paraula, andy.

1191
01:00:14,727 --> 01:00:16,810
Diguem que és una
paraula real, la paraula, andy,

1192
01:00:16,810 --> 01:00:19,640
en una llista gegant d'una paraules.

1193
01:00:19,640 --> 01:00:22,450
>> Si el que passa és reassignar
un mal indicador, oops,

1194
01:00:22,450 --> 01:00:24,940
aquí va la totalitat de
la resta de la cistella enllaçada.

1195
01:00:24,940 --> 01:00:26,897
Ara, l'única paraula que
tenir és andy, i ara

1196
01:00:26,897 --> 01:00:29,230
totes les altres paraules
diccionari s'han perdut.

1197
01:00:29,230 --> 01:00:31,370
I pel que desitja assegurar-se que
portar un registre de tots els seus punters

1198
01:00:31,370 --> 01:00:33,661
o en cas contrari va a aconseguir
enormes problemes en el seu codi.

1199
01:00:33,661 --> 01:00:35,840
Dibuixa les coses amb cura, pas a pas.

1200
01:00:35,840 --> 01:00:37,870
Això fa que sigui molt més fàcil d'imaginar.

1201
01:00:37,870 --> 01:00:40,910
>> I, finalment, que desitja ser capaç de
provar el rendiment del seu programa

1202
01:00:40,910 --> 01:00:41,618
en el gran tauler.

1203
01:00:41,618 --> 01:00:43,710
Si vostès prenen un
mira CS50 en aquest moment,

1204
01:00:43,710 --> 01:00:45,210
tenim el que es diu el gran tauler.

1205
01:00:45,210 --> 01:00:50,200
És el full de puntuació dels més ràpids
lletrejar temps de xecs a través de totes CS50

1206
01:00:50,200 --> 01:00:55,720
en aquest moment, crec que la part superior com 10
vegades penso que vuit d'ells són personal.

1207
01:00:55,720 --> 01:00:57,960
Realment volem que vostès ens van guanyar.

1208
01:00:57,960 --> 01:01:00,870
>> Tots nosaltres estàvem tractant de posar en pràctica
el codi ràpid com sigui possible.

1209
01:01:00,870 --> 01:01:04,880
Volem que vostès tracten de desafiar
ens i implementar més ràpid que tots nosaltres

1210
01:01:04,880 --> 01:01:05,550
pot.

1211
01:01:05,550 --> 01:01:07,970
I pel que aquest és realment
la primera vegada que estem

1212
01:01:07,970 --> 01:01:12,680
demanant a vostès per fer un conjunt de processadors que
vostè pot fer realitat en qualsevol mètode

1213
01:01:12,680 --> 01:01:13,760
Vols.

1214
01:01:13,760 --> 01:01:17,730
>> Jo sempre dic, això és més afí
a una solució de la vida real, oi?

1215
01:01:17,730 --> 01:01:19,550
Jo dic, hey, necessito que facis això.

1216
01:01:19,550 --> 01:01:21,380
Construir un programa que fa això per mi.

1217
01:01:21,380 --> 01:01:22,630
Fes-ho com vulguis.

1218
01:01:22,630 --> 01:01:24,271
Només sé que vull dejunar.

1219
01:01:24,271 --> 01:01:25,770
Aquest és el seu repte per a aquesta setmana.

1220
01:01:25,770 --> 01:01:27,531
Vostès, que va
per donar-li una tasca.

1221
01:01:27,531 --> 01:01:29,030
Anem a donar-li un desafiament.

1222
01:01:29,030 --> 01:01:31,559
I després li toca a vostès
completament sol esbrinar

1223
01:01:31,559 --> 01:01:34,100
¿Quina és la més ràpida i més
forma eficient per implementar això.

1224
01:01:34,100 --> 01:01:34,600
Sí?

1225
01:01:34,600 --> 01:01:37,476
>> AUDIÈNCIA: Estem autoritzats a si
Volíem investigar maneres més ràpides

1226
01:01:37,476 --> 01:01:40,821
fer taules hash en línia, podem fer
això i citar el codi d'una altra persona?

1227
01:01:40,821 --> 01:01:42,070
ANDI Peng: Sí, totalment bé.

1228
01:01:42,070 --> 01:01:44,320
Així que si vostès llegeixen el
especificacions, hi ha una línia

1229
01:01:44,320 --> 01:01:48,310
en l'especificació que diu que vostès
són totalment lliures a la investigació de hash

1230
01:01:48,310 --> 01:01:51,070
funcions en el que són alguns
de les funcions de hash més ràpids

1231
01:01:51,070 --> 01:01:54,720
per executar les coses com
sempre que se citi aquest codi.

1232
01:01:54,720 --> 01:01:57,220
Així que algunes persones ja tenen
descobert maneres ràpides

1233
01:01:57,220 --> 01:02:00,250
de fer els correctors ortogràfics, de ràpid
formes d'emmagatzemar informació.

1234
01:02:00,250 --> 01:02:02,750
Totalment de vostès si
vol prendre només això, oi?

1235
01:02:02,750 --> 01:02:04,045
Assegureu-vos que està citant.

1236
01:02:04,045 --> 01:02:06,170
El repte aquí realment
que estem tractant de provar

1237
01:02:06,170 --> 01:02:09,750
és assegurar-se que vostè sap
la seva manera voltant de punters.

1238
01:02:09,750 --> 01:02:12,700
Pel que vostè implementació
la funció hash real

1239
01:02:12,700 --> 01:02:15,070
i donar amb igual
les matemàtiques per fer això,

1240
01:02:15,070 --> 01:02:17,570
vostès poden investigar el que sigui
mètodes en línia que vostès volen.

1241
01:02:17,570 --> 01:02:17,996
Sí?

1242
01:02:17,996 --> 01:02:19,700
>> AUDIÈNCIA: Podem citar només
mitjançant l'ús de la [inaudible]?

1243
01:02:19,700 --> 01:02:20,120
>> ANDI Peng: Sí.

1244
01:02:20,120 --> 01:02:22,328
Vostè pot simplement, en el seu comentari,
es pot citar com, oh,

1245
01:02:22,328 --> 01:02:26,127
pres de bla, bla,
Yada, funció hash.

1246
01:02:26,127 --> 01:02:27,210
Algú té alguna pregunta?

1247
01:02:27,210 --> 01:02:29,694
En realitat breezed
a la secció d'avui.

1248
01:02:29,694 --> 01:02:31,610
Vaig a ser aquí per
respondre a les preguntes també.

1249
01:02:31,610 --> 01:02:36,570
>> A més, com ja he dit, l'oficina
hores d'aquesta nit i demà.

1250
01:02:36,570 --> 01:02:40,307
L'especificació d'aquesta setmana és en realitat
super fàcil i super curt de llegir.

1251
01:02:40,307 --> 01:02:43,140
Jo suggeriria prendre una mirada, just
llegir a través de la totalitat de la mateixa.

1252
01:02:43,140 --> 01:02:45,730
>> I Zamyla realitat que camina
a través de cadascuna de les funcions

1253
01:02:45,730 --> 01:02:49,796
que necessita per implementar, i pel que és
molt, molt clar com fer tot.

1254
01:02:49,796 --> 01:02:51,920
Només per assegurar-se que està
fer el seguiment dels punters.

1255
01:02:51,920 --> 01:02:53,650
Es tracta d'un conjunt de processadors molt difícil.

1256
01:02:53,650 --> 01:02:56,744
>> No és un repte perquè igual que,
oh, els conceptes són molt més

1257
01:02:56,744 --> 01:02:59,160
difícil, o vostè ha d'aprendre
tant nova sintaxi de la manera

1258
01:02:59,160 --> 01:03:00,650
que vostè va fer per última pset.

1259
01:03:00,650 --> 01:03:03,320
Aquest conjunt de processadors és difícil perquè
hi ha tants punters,

1260
01:03:03,320 --> 01:03:06,980
i llavors és molt, molt fàcil d'una vegada
vostè té un error en el seu codi que no pugui

1261
01:03:06,980 --> 01:03:08,315
trobar on aquest error és.

1262
01:03:08,315 --> 01:03:13,200
>> I tan completa i absoluta fe en tu
nois siguin capaços de superar la nostra [inaudible]

1263
01:03:13,200 --> 01:03:13,700
ortografia.

1264
01:03:13,700 --> 01:03:16,640
En realitat no tinc cap mina escrita
encara, però estic a punt d'escriure la meva.

1265
01:03:16,640 --> 01:03:19,070
Així, mentre que vostè està escrivint
el seu, estaré escrivint la meva.

1266
01:03:19,070 --> 01:03:21,070
Vaig a tractar de fer
mina més ràpid que el seu.

1267
01:03:21,070 --> 01:03:23,940
Anem a veure qui té el més ràpid.

1268
01:03:23,940 --> 01:03:27,340
>> I sí, vaig a veure tots
vostès aquí dimarts.

1269
01:03:27,340 --> 01:03:29,510
Vaig a córrer una espècie com un taller conjunt de processadors.

1270
01:03:29,510 --> 01:03:32,640
Totes les seccions aquest
setmana són tallers PSet,

1271
01:03:32,640 --> 01:03:36,690
pel que vostès tenen moltes oportunitats
a la recerca d'ajuda, les hores d'oficina com sempre,

1272
01:03:36,690 --> 01:03:41,330
i realment espero amb interès
llegir tot el codi als seus nois.

1273
01:03:41,330 --> 01:03:44,160
Tinc proves aquí si
nois volen venir aconseguir-los.

1274
01:03:44,160 --> 01:03:45,880
Això és tot.

1275
01:03:45,880 --> 01:03:48,180