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

2
00:00:11,860 --> 00:00:13,120
>> ALTAVEU 1: D'acord, estem de tornada.

3
00:00:13,120 --> 00:00:14,480
Benvingut a CS50.

4
00:00:14,480 --> 00:00:16,510
Aquest és el final de la setena setmana.

5
00:00:16,510 --> 00:00:20,200
Així que recorda que l'última vegada, comencem
mirar una mica més sofisticat

6
00:00:20,200 --> 00:00:21,100
estructures de dades.

7
00:00:21,100 --> 00:00:25,110
Com fins ara, tot el que tenia realment
a la nostra disposició era això, una matriu.

8
00:00:25,110 --> 00:00:29,340
>> Però abans de descartar la matriu que no
tot el que interessant, que de fet es

9
00:00:29,340 --> 00:00:33,570
en realitat és, quins són alguns dels
avantatges d'aquests senzills dades

10
00:00:33,570 --> 00:00:34,560
estructura fins ara?

11
00:00:34,560 --> 00:00:36,110
Com és bo?

12
00:00:36,110 --> 00:00:39,450
Pel que hem vist?

13
00:00:39,450 --> 00:00:42,540
Què tens?

14
00:00:42,540 --> 00:00:44,028
Res.

15
00:00:44,028 --> 00:00:45,020
>> ESTUDIANT: [inaudible].

16
00:00:45,020 --> 00:00:45,395
>> ALTAVEU 1: Què és això?

17
00:00:45,395 --> 00:00:46,410
>> ESTUDIANT: [inaudible].

18
00:00:46,410 --> 00:00:47,000
>> ALTAVEU 1: Mida fix.

19
00:00:47,000 --> 00:00:51,260
OK, així que per què és bo, encara que de mida fixa?

20
00:00:51,260 --> 00:00:53,180
>> ESTUDIANT: [inaudible].

21
00:00:53,180 --> 00:00:56,240
>> ALTAVEU 1: OK, així que és eficient en la
el sentit que es pot assignar un

22
00:00:56,240 --> 00:01:00,070
quantitat fixa d'espai, que s'espera
és precisament tant

23
00:01:00,070 --> 00:01:01,180
l'espai que desitgi.

24
00:01:01,180 --> 00:01:02,720
Així que podria ser absolutament un avantatge.

25
00:01:02,720 --> 00:01:06,530
>> Quin és l'altre costat d'una matriu?

26
00:01:06,530 --> 00:01:07,610
Sí?

27
00:01:07,610 --> 00:01:08,750
>> ESTUDIANT: [inaudible].

28
00:01:08,750 --> 00:01:09,550
>> ALTAVEU 1: Tots els - ho sento?

29
00:01:09,550 --> 00:01:11,270
>> ESTUDIANT: [inaudible].

30
00:01:11,270 --> 00:01:13,620
>> ALTAVEU 1: Tots els quadres en la memòria
o un al costat de l'altre.

31
00:01:13,620 --> 00:01:15,220
I això és útil - per què?

32
00:01:15,220 --> 00:01:15,970
Això és molt cert.

33
00:01:15,970 --> 00:01:18,611
Però com podem aprofitar aquesta veritat?

34
00:01:18,611 --> 00:01:21,500
>> ESTUDIANT: [inaudible].

35
00:01:21,500 --> 00:01:24,490
>> ALTAVEU 1: Exactament, es pot realitzar un seguiment de
on tot és només saber

36
00:01:24,490 --> 00:01:28,560
una adreça, a saber, la direcció de la
primer byte d'aquest tros de la memòria.

37
00:01:28,560 --> 00:01:30,420
O en el cas de la cadena,
la direcció de la primera

38
00:01:30,420 --> 00:01:31,460
xerrada en aquesta cadena.

39
00:01:31,460 --> 00:01:33,330
I a partir d'aquí, podem trobar
al final de la cadena.

40
00:01:33,330 --> 00:01:35,710
Podem trobar la segona part, el
tercer element, i així successivament.

41
00:01:35,710 --> 00:01:38,740
>> I així, la forma elegant de descriure que
característica és que les matrius ens donen

42
00:01:38,740 --> 00:01:40,020
d'accés aleatori.

43
00:01:40,020 --> 00:01:44,330
Només mitjançant l'ús dels claudàtors
notació i un nombre, pot saltar a

44
00:01:44,330 --> 00:01:48,070
un element específic de la matriu
en temps constant, gran O

45
00:01:48,070 --> 00:01:49,810
d'un, per dir-ho.

46
00:01:49,810 --> 00:01:51,080
>> Però hi ha hagut alguns inconvenients.

47
00:01:51,080 --> 00:01:53,110
El que una matriu no fer molt fàcilment?

48
00:01:53,110 --> 00:01:55,810

49
00:01:55,810 --> 00:01:57,170
Què no fer bé?

50
00:01:57,170 --> 00:01:58,810
>> ESTUDIANT: [inaudible].

51
00:01:58,810 --> 00:01:59,860
>> ALTAVEU 1: Què és això?

52
00:01:59,860 --> 00:02:00,530
>> ESTUDIANT: [inaudible].

53
00:02:00,530 --> 00:02:01,460
>> ALTAVEU 1: Ampliació de mida.

54
00:02:01,460 --> 00:02:04,800
Així que els aspectes negatius de la matriu són
precisament el contrari del que el

55
00:02:04,800 --> 00:02:05,540
Upside són.

56
00:02:05,540 --> 00:02:07,610
Així que una de les desavantatges és
que és una mida fixa.

57
00:02:07,610 --> 00:02:09,400
Així que realment no es pot créixer.

58
00:02:09,400 --> 00:02:13,510
Pot reassignar una part més gran de
la memòria i, a continuació, mogui els elements antics

59
00:02:13,510 --> 00:02:14,460
en la nova matriu.

60
00:02:14,460 --> 00:02:18,060
I llavors lliure de l'antiga matriu, per
exemple, mitjançant l'ús de malloc o similar

61
00:02:18,060 --> 00:02:21,180
funció anomenada realloc, que
reassignació memòria.

62
00:02:21,180 --> 00:02:25,490
>> Realloc, en un apart, intenta donar-li
memòria que està al costat de la matriu

63
00:02:25,490 --> 00:02:26,610
que vostè ja té.

64
00:02:26,610 --> 00:02:28,740
Però podria canviar les coses
al voltant de per complet.

65
00:02:28,740 --> 00:02:30,710
Però en fi, això és car, no?

66
00:02:30,710 --> 00:02:33,440
Perquè si tens un tros de memòria de
aquesta mida, però realment vull un

67
00:02:33,440 --> 00:02:36,710
d'aquesta mida, i desitja conservar
els elements originals, que tenen

68
00:02:36,710 --> 00:02:40,510
més o menys un procés de còpia temps lineal
això ha de succeir d'

69
00:02:40,510 --> 00:02:41,900
antiga matriu a la nova.

70
00:02:41,900 --> 00:02:44,630
I la realitat està demanant a l'operació
sistema d'una i altra vegada i

71
00:02:44,630 --> 00:02:48,340
de nou per grans trossos de la memòria pot començar
a costar algun temps també.

72
00:02:48,340 --> 00:02:52,250
Així que és tant una benedicció com una maledicció en
disfressa, el fet que aquestes matrius

73
00:02:52,250 --> 00:02:53,860
són de grandària fixa.

74
00:02:53,860 --> 00:02:56,790
Però si introduïm vegada alguna cosa
així, el que anomenem una vinculada

75
00:02:56,790 --> 00:03:00,580
llista, tenim alguns avantatges i
alguns desavantatges també aquí.

76
00:03:00,580 --> 00:03:05,780
>> Així que una llista enllaçada és simplement un conjunt de dades
estructura composta per estructures de C en aquest

77
00:03:05,780 --> 00:03:09,850
cas, en què una estructura, el record, és només
un contenidor per a una o més específica

78
00:03:09,850 --> 00:03:11,100
tipus de variables.

79
00:03:11,100 --> 00:03:16,110
En aquest cas, el que ho fan els tipus de dades
semblen estar dins de l'estructura que

80
00:03:16,110 --> 00:03:17,600
última vegada que es diu un node?

81
00:03:17,600 --> 00:03:19,380
Cada un d'aquests rectangles és un node.

82
00:03:19,380 --> 00:03:22,660
I cada un dels rectangles més petits
dins d'ella és un tipus de dades.

83
00:03:22,660 --> 00:03:25,300
Quins tipus vam dir
estaven el dilluns?

84
00:03:25,300 --> 00:03:26,478
Sí?

85
00:03:26,478 --> 00:03:27,870
>> ESTUDIANT: [inaudible].

86
00:03:27,870 --> 00:03:30,721
>> ALTAVEU 1: Una variable i un punter, o
més específicament, un int, per a n,

87
00:03:30,721 --> 00:03:32,180
i un punter a la part inferior.

88
00:03:32,180 --> 00:03:35,360
Tant dels que resulten ser de 32 bits, per la qual
almenys en un equip com aquest CS50

89
00:03:35,360 --> 00:03:37,980
Appliance i pel que són
dibuixat per igual en grandària.

90
00:03:37,980 --> 00:03:42,260
>> Llavors, què estan utilitzant el punter
encara que per semblar?

91
00:03:42,260 --> 00:03:47,690
Per què afegir aquesta fletxa ara, quan les matrius van ser
molt agradable i net i simple?

92
00:03:47,690 --> 00:03:50,460
Què està fent el punter per
nosaltres en cada un d'aquests nodes?

93
00:03:50,460 --> 00:03:52,160
>> ESTUDIANT: [inaudible].

94
00:03:52,160 --> 00:03:52,465
>> ALTAVEU 1: Exactament.

95
00:03:52,465 --> 00:03:54,120
Li està dient que
el següent és.

96
00:03:54,120 --> 00:03:57,350
Així que en certa manera em utilitzo l'analogia de
utilitzant un fil a la classe de

97
00:03:57,350 --> 00:03:59,180
enfilar aquests nodes entre si.

98
00:03:59,180 --> 00:04:01,760
I això és exactament el que estem fent amb
punters perquè cada un d'aquests

99
00:04:01,760 --> 00:04:06,360
trossos de memòria poden o poden no estar
contigua, esquena amb esquena amb esquena

100
00:04:06,360 --> 00:04:09,500
interior de RAM, perquè cada vegada que
trucar a malloc dient dóna'm suficient

101
00:04:09,500 --> 00:04:12,510
bytes d'un nou node, podria
ser aquí o podria ser aquí.

102
00:04:12,510 --> 00:04:13,120
Podria ser aquí.

103
00:04:13,120 --> 00:04:13,730
Podria ser aquí.

104
00:04:13,730 --> 00:04:14,640
Vostè simplement no sap.

105
00:04:14,640 --> 00:04:17,880
>> Però l'ús de punters a les adreces d'
els nodes, pot cosir

106
00:04:17,880 --> 00:04:22,370
junts d'una manera que sembla visualment
com una llista, fins i tot si aquestes coses són

107
00:04:22,370 --> 00:04:26,770
totes disperses en tot el seu ser o
els dos o els quatre gigabytes de RAM

108
00:04:26,770 --> 00:04:28,760
dins del seu propi equip.

109
00:04:28,760 --> 00:04:33,230
>> Així que la banda negativa, doncs, de
una llista enllaçada és què?

110
00:04:33,230 --> 00:04:34,670
Què és un preu que estem
Aparentment pagar?

111
00:04:34,670 --> 00:04:36,010
>> ESTUDIANT: [inaudible].

112
00:04:36,010 --> 00:04:36,920
>> ALTAVEU 1: Més espai, no?

113
00:04:36,920 --> 00:04:39,340
Tenim, en aquest cas, es va duplicar la quantitat
l'espai, ja que hem anat

114
00:04:39,340 --> 00:04:43,500
de 32 bits per a cada node, per a cadascun
int, de manera que ara de 64 bits perquè hem de

115
00:04:43,500 --> 00:04:45,050
mantenir al voltant d'un punter també.

116
00:04:45,050 --> 00:04:48,860
Vostè obté més eficiència si la seva estructura
és més gran que aquesta cosa simple.

117
00:04:48,860 --> 00:04:52,020
Si vostè té actualment un estudiant a l'interior
dels quals és un parell de cadenes de

118
00:04:52,020 --> 00:04:55,430
nom i la casa, potser un número d'identificació,
potser alguns altres camps en total.

119
00:04:55,430 --> 00:04:59,000
>> Així que si vostè té una gran estructura suficient,
llavors potser el cost del punter està

120
00:04:59,000 --> 00:05:00,010
no és un gran problema.

121
00:05:00,010 --> 00:05:03,570
Això és una mica d'un cas de la cantonada en què
estem emmagatzemant una simple primitiva tals

122
00:05:03,570 --> 00:05:04,760
dins de la llista enllaçada.

123
00:05:04,760 --> 00:05:05,790
Però el punt és el mateix.

124
00:05:05,790 --> 00:05:08,230
Definitivament estàs gastant més
memòria, però que està rebent

125
00:05:08,230 --> 00:05:08,990
flexibilitat.

126
00:05:08,990 --> 00:05:12,280
Perquè ara si vull afegir un element
al principi d'aquesta llista,

127
00:05:12,280 --> 00:05:14,340
He de assignar un nou node.

128
00:05:14,340 --> 00:05:17,180
I he de actualitzar només els
fletxes d'alguna manera, amb només moure

129
00:05:17,180 --> 00:05:17,980
alguns indicadors voltant.

130
00:05:17,980 --> 00:05:20,580
>> Si vull inserir alguna cosa al
meitat de la llista, no té per què

131
00:05:20,580 --> 00:05:24,410
empènyer a tots a un costat com ho vam fer en
passat setmanes amb els nostres voluntaris que

132
00:05:24,410 --> 00:05:25,700
representa una matriu.

133
00:05:25,700 --> 00:05:29,470
Només puc assignar un nou node i
després simplement apuntar les fletxes

134
00:05:29,470 --> 00:05:32,290
diferents direccions, ja que no
haurà de romandre en el reial

135
00:05:32,290 --> 00:05:35,670
memòria d'una veritable línia com he dibuixat
aquí a la pantalla.

136
00:05:35,670 --> 00:05:38,400
>> I finalment, si voleu inserir
cosa que al final de la llista, és

137
00:05:38,400 --> 00:05:39,210
encara més fàcil.

138
00:05:39,210 --> 00:05:43,320
Aquesta és una espècie de notació arbitrària,
però un triple de 34, prendre una conjectura.

139
00:05:43,320 --> 00:05:46,710
Quin és el valor del seu indicador més
probablement una mena de dibuixat com un vell

140
00:05:46,710 --> 00:05:47,700
antena de l'escola allà?

141
00:05:47,700 --> 00:05:48,920
>> ESTUDIANT: [inaudible].

142
00:05:48,920 --> 00:05:49,900
>> ALTAVEU 1: Probablement és nul.

143
00:05:49,900 --> 00:05:52,710
I de fet aquesta és una de l'autor
representació de nul.

144
00:05:52,710 --> 00:05:56,310
I és nul · la, perquè malgrat tot
necessitat de saber on és el final d'un vinculat

145
00:05:56,310 --> 00:06:00,050
llista és, perquè no es manté després i
seguint i seguint aquestes fletxes

146
00:06:00,050 --> 00:06:01,170
a un valor d'escombraries.

147
00:06:01,170 --> 00:06:06,230
Així nul significarà que no hi ha
més nodes a la dreta del número 34,

148
00:06:06,230 --> 00:06:07,200
en aquest cas.

149
00:06:07,200 --> 00:06:10,270
>> Per tant, proposem que podem posar en pràctica
aquest node en el codi.

150
00:06:10,270 --> 00:06:12,130
I hem vist aquest tipus
abans de la sintaxi.

151
00:06:12,130 --> 00:06:15,090
Typedef simplement defineix un nou tipus de
nosaltres, ens dóna un sinònim com

152
00:06:15,090 --> 00:06:17,100
cadena era per char *.

153
00:06:17,100 --> 00:06:21,030
En aquest cas, ens donarà
notació abreujada per a aquest node struct

154
00:06:21,030 --> 00:06:24,010
pot en el seu lloc només pot escriure com
node, que és molt més net.

155
00:06:24,010 --> 00:06:25,360
És molt menys detallat.

156
00:06:25,360 --> 00:06:30,080
>> A l'interior d'un node és aparentment un int
anomenada n, i a continuació, un node d'estructura *

157
00:06:30,080 --> 00:06:34,670
el que significa exactament el que volíem la
fletxes per dir, un punter a un altre

158
00:06:34,670 --> 00:06:36,940
node del mateix tipus de dades exacta.

159
00:06:36,940 --> 00:06:40,300
I proposo que podríem implementar un
funció de cerca d'aquest tipus, que en

160
00:06:40,300 --> 00:06:41,890
primera vista pot semblar
una mica complex.

161
00:06:41,890 --> 00:06:43,330
Però anem a veure-ho en el seu context.

162
00:06:43,330 --> 00:06:45,480
>> Vull passar l'aparell aquí.

163
00:06:45,480 --> 00:06:48,460
Permetin-me obrir un fitxer anomenat
llista de punts h zero.

164
00:06:48,460 --> 00:06:53,950
I que només conté la definició que
acabo de veure fa un moment per a aquestes dades

165
00:06:53,950 --> 00:06:55,390
Tipus El node.

166
00:06:55,390 --> 00:06:57,350
Així que hem posat això en un arxiu de punts h.

167
00:06:57,350 --> 00:07:01,430
>> I en un a part, tot i que aquesta
programa que està a punt de veure és

168
00:07:01,430 --> 00:07:05,410
no és tan complexa, que és de fet
convencions en escriure un programa per

169
00:07:05,410 --> 00:07:10,270
posar les coses com els tipus de dades, per treure
constants, de vegades, dins del seu

170
00:07:10,270 --> 00:07:13,210
arxiu de capçalera i no necessàriament en
l'arxiu de C, sobretot quan el seu

171
00:07:13,210 --> 00:07:17,370
programes es fan més grans i més grans, pel que
vostè sap on buscar, tant per

172
00:07:17,370 --> 00:07:20,840
documentació en alguns casos, o
per el bàsic com aquest, els

173
00:07:20,840 --> 00:07:22,360
definició d'algun tipus.

174
00:07:22,360 --> 00:07:25,680
>> Si ara obro llista de zero punts
c, es va adonar d'algunes coses.

175
00:07:25,680 --> 00:07:29,090
Conté una sèrie d'arxius de capçalera, la majoria dels
dels quals hem vist abans.

176
00:07:29,090 --> 00:07:31,980
Inclou el seu propi arxiu de capçalera.

177
00:07:31,980 --> 00:07:35,200
>> I en un a part, per què això és doble
cites aquí, en contraposició a l'angle

178
00:07:35,200 --> 00:07:38,340
suports en la línia que
He destacat allà?

179
00:07:38,340 --> 00:07:39,180
>> ESTUDIANT: [inaudible].

180
00:07:39,180 --> 00:07:40,460
>> ALTAVEU 1: Sí, per la qual cosa és un fitxer local.

181
00:07:40,460 --> 00:07:44,300
Així que si és un fitxer local de la seva pròpia aquí
en la línia 15, per exemple, s'utilitza

182
00:07:44,300 --> 00:07:46,570
les cometes dobles en lloc
dels suports en angle.

183
00:07:46,570 --> 00:07:48,270
>> Ara bé, això és una cosa interessant.

184
00:07:48,270 --> 00:07:51,830
Tingueu en compte que he declarat un Mundial
variable en aquest programa a la línia 18

185
00:07:51,830 --> 00:07:55,910
va cridar en primer lloc, la idea d'això és
serà un punter a la primera

186
00:07:55,910 --> 00:07:59,190
node a la meva llista enllaçada, i he
inicialitza a null, perquè he

187
00:07:59,190 --> 00:08:02,310
no assignat cap real
nodes encara.

188
00:08:02,310 --> 00:08:07,570
>> Així que això representa, gràficament, el que
vaig veure fa un moment en la imatge com

189
00:08:07,570 --> 00:08:10,090
aquest punter a l'extrem
esquerra costat.

190
00:08:10,090 --> 00:08:12,260
Així que ara mateix, aquest punter
no té una fletxa.

191
00:08:12,260 --> 00:08:14,590
En el seu lloc, és nul.

192
00:08:14,590 --> 00:08:17,880
Però representa el que serà el
direcció del primer real

193
00:08:17,880 --> 00:08:19,480
node en aquesta llista.

194
00:08:19,480 --> 00:08:22,120
Així que he implementat és un mundial
perquè, com es veurà, tot això

195
00:08:22,120 --> 00:08:25,310
programa no a la vida és posar en pràctica
una llista enllaçada per a mi.

196
00:08:25,310 --> 00:08:27,050
>> Ara tinc uns prototips aquí.

197
00:08:27,050 --> 00:08:31,190
Vaig decidir implementar característiques com
eliminació, inserció, recerca i

198
00:08:31,190 --> 00:08:31,740
de recorregut -

199
00:08:31,740 --> 00:08:35,210
l'últim només estar a peu a través de la
llista, imprimint els seus elements.

200
00:08:35,210 --> 00:08:36,750
I ara aquí està la meva rutina principal.

201
00:08:36,750 --> 00:08:39,890
I no anem a passar molt temps en
aquestes ja que aquesta és una espècie de, tant de bo

202
00:08:39,890 --> 00:08:41,780
barret vell ja.

203
00:08:41,780 --> 00:08:45,370
>> Vaig a fer el següent,
mentre que l'usuari col · labora.

204
00:08:45,370 --> 00:08:47,300
Així que un, vaig a imprimir
aquest menú.

205
00:08:47,300 --> 00:08:49,420
I he formatat com
netament com vaig poder.

206
00:08:49,420 --> 00:08:52,240
Si l'usuari escriu en un, això significa
volen esborrar alguna cosa.

207
00:08:52,240 --> 00:08:54,560
Si l'usuari escriu en dos, el que significa
volen inserir alguna cosa.

208
00:08:54,560 --> 00:08:55,930
I així successivament.

209
00:08:55,930 --> 00:08:58,270
Vaig a suggerir a continuació,
a continuació d'un comando.

210
00:08:58,270 --> 00:08:59,300
I llavors vaig a utilitzar GetInt.

211
00:08:59,300 --> 00:09:02,790
>> Així que aquesta és una molt simple menuing
interfície en la qual només ha d'escriure

212
00:09:02,790 --> 00:09:05,270
una assignació de número a un
d'aquests comandaments.

213
00:09:05,270 --> 00:09:08,730
I ara tinc un interruptor net agradable
declaració que canviarà el

214
00:09:08,730 --> 00:09:10,090
tot el que l'usuari va escriure polz

215
00:09:10,090 --> 00:09:12,180
I si s'escriuen un, vaig a
trucar a esborrar i trencar.

216
00:09:12,180 --> 00:09:14,380
Si escriuen dues, vaig a
trucar a inserir i trencar-se.

217
00:09:14,380 --> 00:09:16,490
>> I ara noto que he posat cada
d'aquests en la mateixa línia.

218
00:09:16,490 --> 00:09:18,360
Això és només una decisió estilística.

219
00:09:18,360 --> 00:09:20,210
En general hem vist alguna cosa
d'aquesta manera.

220
00:09:20,210 --> 00:09:23,260
Però vaig decidir, francament, el meu programa
semblava més fàcil de llegir, perquè

221
00:09:23,260 --> 00:09:25,980
era només quatre casos a
només la llista així.

222
00:09:25,980 --> 00:09:28,360
Totalment ús legítim d'estil.

223
00:09:28,360 --> 00:09:31,480
I jo faré això sempre que el
persona no ha posat zero, el que em

224
00:09:31,480 --> 00:09:33,910
decidir significarà que volen deixar de fumar.

225
00:09:33,910 --> 00:09:36,630
>> Així que ara compta del que sóc
farem aquí.

226
00:09:36,630 --> 00:09:38,650
Vaig a alliberar la llista aparentment.

227
00:09:38,650 --> 00:09:40,230
Però més sobre això en un moment.

228
00:09:40,230 --> 00:09:41,640
Primer anem a executar aquest programa.

229
00:09:41,640 --> 00:09:45,250
Així que permetin-me fer un terminal més gran
finestra, punt slash llista 0.

230
00:09:45,250 --> 00:09:49,510
Vaig a seguir endavant i inseriu a la
escriure dos un nombre com 50, i ara

231
00:09:49,510 --> 00:09:51,590
veuràs la llista és ara 50.

232
00:09:51,590 --> 00:09:53,380
I el meu text només desplaça una mica.

233
00:09:53,380 --> 00:09:55,940
Així que ara compta la llista conté
el número 50.

234
00:09:55,940 --> 00:09:58,220
>> Anem a fer un altre inserit prenent dos.

235
00:09:58,220 --> 00:10:01,630
Escriurem el nombre com a tal.

236
00:10:01,630 --> 00:10:03,940
Llista és ara un, seguit per 50.

237
00:10:03,940 --> 00:10:06,020
Així que això és només una representació textual
de la llista.

238
00:10:06,020 --> 00:10:10,550
I anem a inserir una més igual nombre
el número 42, que és d'esperar

239
00:10:10,550 --> 00:10:14,620
va a acabar en el medi, perquè
aquest programa a les classes particulars que

240
00:10:14,620 --> 00:10:16,320
elements, ja que els insereix.

241
00:10:16,320 --> 00:10:17,220
Així que aquí ho tenim.

242
00:10:17,220 --> 00:10:20,730
Programa Súper simple que podria
absolutament he utilitzat una matriu, però

243
00:10:20,730 --> 00:10:23,280
passar a ser l'ús d'una llista enllaçada
perquè jo pugui dinàmicament

244
00:10:23,280 --> 00:10:24,610
créixer i reduir la seva grandària.

245
00:10:24,610 --> 00:10:28,470
>> Així que anem a fer una ullada per a la recerca, si
ordre de tres funcionar, vull buscar

246
00:10:28,470 --> 00:10:31,040
per, per exemple, el nombre 43.

247
00:10:31,040 --> 00:10:34,190
I res es va trobar que sembla,
perquè vaig tornar resposta.

248
00:10:34,190 --> 00:10:35,010
Així que anem a fer això una altra vegada.

249
00:10:35,010 --> 00:10:35,690
Cercar.

250
00:10:35,690 --> 00:10:39,520
Buscarem 50, o més aviat buscar
el 42, que té un bon

251
00:10:39,520 --> 00:10:40,850
poc significat subtil.

252
00:10:40,850 --> 00:10:42,610
I vaig trobar el significat de la vida allà.

253
00:10:42,610 --> 00:10:44,990
Número 42, si vostè no sap
la referència, google.

254
00:10:44,990 --> 00:10:45,350
Està bé.

255
00:10:45,350 --> 00:10:47,130
Llavors, què té aquest programa fet per mi?

256
00:10:47,130 --> 00:10:50,660
És que m'ha permès inserir tant
al llarg i recerca d'elements.

257
00:10:50,660 --> 00:10:53,650
>> Anem a avançar ràpidament, llavors,
aquesta funció ens va mirar a

258
00:10:53,650 --> 00:10:55,360
dilluns com un reclam.

259
00:10:55,360 --> 00:10:59,620
Així que aquesta funció, reclam, busca
un element a la llista per primera

260
00:10:59,620 --> 00:11:03,830
un, preguntar a l'usuari i després trucar
GetInt per obtenir un int real

261
00:11:03,830 --> 00:11:05,060
que voleu cercar.

262
00:11:05,060 --> 00:11:06,460
>> Després compte d'això.

263
00:11:06,460 --> 00:11:10,690
Vaig a crear una variable temporal
en la línia 188 diu punter -

264
00:11:10,690 --> 00:11:11,270
PTR -

265
00:11:11,270 --> 00:11:12,440
podria haver anomenat res.

266
00:11:12,440 --> 00:11:16,140
I és un punter a un node
perquè he dit node * allà.

267
00:11:16,140 --> 00:11:19,900
I estic inicialitzant que sigui igual a
primer perquè efectivament tinc el meu

268
00:11:19,900 --> 00:11:22,860
dit, per així dir-ho, en el mateix
primer element de la llista.

269
00:11:22,860 --> 00:11:27,460
Així que si la meva mà aquí és PTR estic
apuntant al mateix que la primera

270
00:11:27,460 --> 00:11:28,670
està assenyalant.

271
00:11:28,670 --> 00:11:31,430
>> Així que ara de nou en el codi,
Què passa després -

272
00:11:31,430 --> 00:11:35,070
aquest és un paradigma comú quan es repeteix
sobre una estructura com un

273
00:11:35,070 --> 00:11:35,970
llista enllaçada.

274
00:11:35,970 --> 00:11:40,410
Jo faré el següent mentre
punter no és igual a null Així, mentre que

275
00:11:40,410 --> 00:11:47,530
el meu dit no assenyala en algun nul
valor, si el punter fletxa n és igual a n.

276
00:11:47,530 --> 00:11:52,290
Ens vam adonar per primera vegada que n és el que el
usuari va escriure en per GetInts cridar aquí.

277
00:11:52,290 --> 00:11:54,280
>> I punter de fletxa n vol dir què?

278
00:11:54,280 --> 00:11:59,020
Bé, si ens remuntem a la imatge aquí,
si tinc un dit apuntant a

279
00:11:59,020 --> 00:12:02,960
que primer node que conté nou, la
fletxa essencialment vol dir anar a la

280
00:12:02,960 --> 00:12:08,860
node i prendre el valor en la posició n,
en aquest cas, el camp de dades flama n.

281
00:12:08,860 --> 00:12:14,120
>> Com acotació al marge - i ens vam veure un parell
de setmanes enrere, quan algú li va preguntar -

282
00:12:14,120 --> 00:12:18,840
aquesta sintaxi és nou, però no ho fa
donar-nos poders que

283
00:12:18,840 --> 00:12:20,040
no tenen ja.

284
00:12:20,040 --> 00:12:25,325
Quin era aquesta frase equival a utilitzar
notació de punts i l'estrella d'un parell

285
00:12:25,325 --> 00:12:29,490
de setmanes quan va desprendre
aquesta capa una mica abans de temps?

286
00:12:29,490 --> 00:12:31,780
>> ESTUDIANT: [inaudible].

287
00:12:31,780 --> 00:12:38,880
>> ALTAVEU 1: Exactament, era l'estrella, i
després va ser l'estrella del punt n, amb

288
00:12:38,880 --> 00:12:41,930
parèntesi aquí, el que es veu,
Francament, crec que molts

289
00:12:41,930 --> 00:12:43,320
més críptic de llegir.

290
00:12:43,320 --> 00:12:46,270
Però indicador de l'estrella, com sempre,
significa anar-hi.

291
00:12:46,270 --> 00:12:49,090
I una vegada que estàs allà, quines dades
camp és el que vols accedir?

292
00:12:49,090 --> 00:12:52,730
Bé utilitza la notació de punts d'accés
un camp de dades d'estructures, i

293
00:12:52,730 --> 00:12:54,140
específicament vol n.

294
00:12:54,140 --> 00:12:56,240
>> Francament, jo diria que aquest
només és més difícil de llegir.

295
00:12:56,240 --> 00:12:58,080
És més difícil de recordar on
Com els parèntesis anar, el

296
00:12:58,080 --> 00:12:59,030
estrelles i tot això.

297
00:12:59,030 --> 00:13:02,150
Així que el món s'ha adoptat alguna sintàctica
sucre, per dir-ho.

298
00:13:02,150 --> 00:13:04,740
Només una forma atractiva de dir,
això és equivalent, i

299
00:13:04,740 --> 00:13:05,970
potser més intuïtiu.

300
00:13:05,970 --> 00:13:09,600
Si punter és de fet un punter, el
fletxa mitjans notació anar allà i trobar

301
00:13:09,600 --> 00:13:11,890
el camp, en aquest cas anomenat núm.

302
00:13:11,890 --> 00:13:13,660
>> Així que si el trobo, adonar-se del que faig.

303
00:13:13,660 --> 00:13:17,430
Simplement em imprimeixo, vaig trobar cent i,
endollar el valor per a aquest int.

304
00:13:17,430 --> 00:13:20,730
Truco dormir durant un segon sol a la classe
de pausa les coses a la pantalla per

305
00:13:20,730 --> 00:13:22,900
donar a l'usuari un segon per absorbir
el que acaba de succeir.

306
00:13:22,900 --> 00:13:24,290
I llavors trenco.

307
00:13:24,290 --> 00:13:26,330
En cas contrari, què faig?

308
00:13:26,330 --> 00:13:30,960
Com actualitzo punter a la igualtat de
fletxa de punter següent.

309
00:13:30,960 --> 00:13:35,840
>> Així que per ser clars, això vol dir anar
allà, amb la meva notació de la vella escola.

310
00:13:35,840 --> 00:13:39,580
Així que això només significa anar a qualsevol
vostè està apuntant a que, en el

311
00:13:39,580 --> 00:13:43,660
primer cas és que estic assenyalant
l'estructura amb nou en el mateix.

312
00:13:43,660 --> 00:13:44,510
Així que he anat.

313
00:13:44,510 --> 00:13:47,880
I a continuació, significa la notació de punts,
obtenir el valor al següent.

314
00:13:47,880 --> 00:13:50,470
>> Però el valor, tot i que ha dibuixat
com un estret, és només un nombre.

315
00:13:50,470 --> 00:13:51,720
És una adreça numèrica.

316
00:13:51,720 --> 00:13:55,670
Així que una línia de codi, ja sigui
escrit com aquest, el més críptic

317
00:13:55,670 --> 00:14:00,190
així, o així, els poc més
manera intuïtiva, simplement vol dir moure la mà

318
00:14:00,190 --> 00:14:03,460
des del primer node al següent,
i després el següent, i a continuació, la

319
00:14:03,460 --> 00:14:05,320
següent, i així successivament.

320
00:14:05,320 --> 00:14:09,920
>> Així que no vaig a detenir-me en l'altre
implementacions d'inserir i eliminar

321
00:14:09,920 --> 00:14:14,030
i el recorregut, els dos primers de
que són bastant implicats.

322
00:14:14,030 --> 00:14:17,010
I crec que és molt fàcil d'aconseguir
perdut en fer-ho verbalment.

323
00:14:17,010 --> 00:14:19,890
Però el que podem fer aquí és
tractar de determinar com

324
00:14:19,890 --> 00:14:21,640
millor fer-ho visualment.

325
00:14:21,640 --> 00:14:24,800
Perquè jo proposaria que si
voleu inserir elements en aquesta

326
00:14:24,800 --> 00:14:26,680
llista existent, que
té cinc elements -

327
00:14:26,680 --> 00:14:29,530
9, 17, 22, 26, i 33 -

328
00:14:29,530 --> 00:14:33,300
si jo fos a implementar això en
codi, he d'estudiar la forma d'anar

329
00:14:33,300 --> 00:14:34,160
fent això.

330
00:14:34,160 --> 00:14:37,720
>> I jo proposaria prendre passos de nadó
pel que, en aquest cas em refereixo al que són

331
00:14:37,720 --> 00:14:41,090
els possibles escenaris que
poden sorgir en general?

332
00:14:41,090 --> 00:14:44,120
Quan l'aplicació d'inserció per a un lligat
llista, això només passa a ser un

333
00:14:44,120 --> 00:14:46,090
exemple específic de mida de cinc.

334
00:14:46,090 --> 00:14:50,420
Bé, si vol inserir un número,
com diuen el número u, i

335
00:14:50,420 --> 00:14:53,380
mantenir l'ordre establert, on
òbviament, fa el número u necessita

336
00:14:53,380 --> 00:14:55,686
anar en aquest exemple concret?

337
00:14:55,686 --> 00:14:56,840
Igual que al principi.

338
00:14:56,840 --> 00:15:00,030
>> Però el més interessant no és que
si voleu inserir una en aquest

339
00:15:00,030 --> 00:15:04,100
llista, el que necessita punter especial
ser actualitzat aparentment?

340
00:15:04,100 --> 00:15:04,610
En primer lloc.

341
00:15:04,610 --> 00:15:07,830
Així que jo diria, aquest és el primer cas
que el que es vol tenir en compte, un

342
00:15:07,830 --> 00:15:11,140
escenari en el qual la inserció en
el principi de la llista.

343
00:15:11,140 --> 00:15:15,400
>> Anem a arrencar potser una tan fàcil o fins i tot
el cas més senzill, en termes relatius.

344
00:15:15,400 --> 00:15:18,110
Suposem que vull inserir la
el número 35 en l'ordre establert.

345
00:15:18,110 --> 00:15:20,600
Òbviament pertany allà.

346
00:15:20,600 --> 00:15:25,320
Llavors, quin indicador òbviament va a
d'actualitzar en aquest escenari?

347
00:15:25,320 --> 00:15:30,060
Punter de 34 convertint no nul · la
però la direcció de l'estructura

348
00:15:30,060 --> 00:15:31,800
que conté el número 35.

349
00:15:31,800 --> 00:15:32,750
Així que això és el cas de dos.

350
00:15:32,750 --> 00:15:36,190
Així que ja, jo sóc una mena de quantificació
la quantitat de treball que he de fer aquí.

351
00:15:36,190 --> 00:15:39,880
>> I, finalment, el cas mitjà és obvi
de fet, en el medi, si vull

352
00:15:39,880 --> 00:15:45,870
inserir una cosa així com dir 23, que va
entre el 23 i el 26, però

353
00:15:45,870 --> 00:15:48,680
Ara les coses es posen una mica més
participar perquè ho

354
00:15:48,680 --> 00:15:52,800
punters necessiten ser canviat?

355
00:15:52,800 --> 00:15:56,680
Així que, òbviament, 22 necessita ser canviat
perquè no pot apuntar a 26 més.

356
00:15:56,680 --> 00:16:00,320
Ell ha d'apuntar al nou node que
Vaig a haver de destinar trucant

357
00:16:00,320 --> 00:16:01,770
malloc o algun equivalent.

358
00:16:01,770 --> 00:16:05,990
>> Però també necessito que el nou node, 23
en aquest cas, per tenir la seva punter

359
00:16:05,990 --> 00:16:07,870
assenyalant a qui?

360
00:16:07,870 --> 00:16:08,560
26.

361
00:16:08,560 --> 00:16:10,380
I no serà un
ordre de les operacions aquí.

362
00:16:10,380 --> 00:16:13,410
Perquè si ho faig tontament, i
per exemple inici al començament de

363
00:16:13,410 --> 00:16:16,040
la llista, i el meu objectiu és inserir 23.

364
00:16:16,040 --> 00:16:18,610
I comprovo, li pertany
Aquí, prop de nou?

365
00:16:18,610 --> 00:16:18,950
No

366
00:16:18,950 --> 00:16:20,670
Pertany aquí, al costat 17?

367
00:16:20,670 --> 00:16:20,940
No

368
00:16:20,940 --> 00:16:22,530
Li pertany a aquest lloc al costat de 22?

369
00:16:22,530 --> 00:16:23,300
Sí

370
00:16:23,300 --> 00:16:26,400
>> Ara bé, si sóc tonto aquí, i no
pensant en això, jo podria

371
00:16:26,400 --> 00:16:28,320
assignar meu nou node 23.

372
00:16:28,320 --> 00:16:32,080
Jo podria actualitzar el punter del
el node de flama 22, que assenyala

373
00:16:32,080 --> 00:16:33,080
que en el nou node.

374
00:16:33,080 --> 00:16:36,140
I llavors, ¿què he de actualitzar
Punter del nou node sigui?

375
00:16:36,140 --> 00:16:38,120
>> ESTUDIANT: [inaudible].

376
00:16:38,120 --> 00:16:38,385
>> ALTAVEU 1: Exactament.

377
00:16:38,385 --> 00:16:39,710
Assenyalant a 26.

378
00:16:39,710 --> 00:16:45,590
Però maleïda sigui si no ja actualitzo
Punter de 22 per assenyalar a aquest tipus, i

379
00:16:45,590 --> 00:16:48,260
ara tinc orfes, la resta
de la llista, per dir-ho.

380
00:16:48,260 --> 00:16:52,140
Així que la finalitat de les operacions aquí
serà important.

381
00:16:52,140 --> 00:16:55,100
>> Per a això podria robar,
dir, sis voluntaris.

382
00:16:55,100 --> 00:16:57,650
I anem a veure si podem fer això
visualment en lloc del codi es refereix.

383
00:16:57,650 --> 00:16:59,330
I tenim una mica d'estrès encantadora
boles per al dia d'avui.

384
00:16:59,330 --> 00:17:02,510
Bé, què hi ha d'una, dues, al
tornada - a l'extrem allà.

385
00:17:02,510 --> 00:17:04,530
tres, quatre, els dos
nois a la final.

386
00:17:04,530 --> 00:17:05,579
I cinc, sis.

387
00:17:05,579 --> 00:17:05,839
Clar.

388
00:17:05,839 --> 00:17:06,450
Cinc-sis.

389
00:17:06,450 --> 00:17:08,390
Està bé i anem a arribar
amb vostès la propera vegada.

390
00:17:08,390 --> 00:17:09,640
Bé, anem amunt.

391
00:17:09,640 --> 00:17:12,010

392
00:17:12,010 --> 00:17:14,819
>> Bé, ja que ets aquí primer,
T'agradaria ser la malaptesa

393
00:17:14,819 --> 00:17:16,119
a Google Glass aquí?

394
00:17:16,119 --> 00:17:19,075
D'acord, llavors, OK, Glass,
gravar un vídeo.

395
00:17:19,075 --> 00:17:22,720

396
00:17:22,720 --> 00:17:24,589
Bé, ja està bo per anar.

397
00:17:24,589 --> 00:17:27,950
>> Molt bé, així que si vostès poden venir
aquí, he preparat amb antelació

398
00:17:27,950 --> 00:17:30,110
alguns números.

399
00:17:30,110 --> 00:17:31,240
Bé, anem per aquí.

400
00:17:31,240 --> 00:17:33,440
¿I per què no et vas una mica
més d'aquesta manera.

401
00:17:33,440 --> 00:17:35,520
I anem a veure, quin és el teu nom,
amb el vidre de Google?

402
00:17:35,520 --> 00:17:35,910
>> ESTUDIANT: Ben.

403
00:17:35,910 --> 00:17:36,230
>> ALTAVEU 1: Ben?

404
00:17:36,230 --> 00:17:38,380
Bé, Ben, que serà la primera, literalment.

405
00:17:38,380 --> 00:17:40,580
Així que anem a enviar
al final de l'etapa.

406
00:17:40,580 --> 00:17:41,670
Molt bé, i el teu nom?

407
00:17:41,670 --> 00:17:41,990
>> ESTUDIANT: Jason.

408
00:17:41,990 --> 00:17:44,530
>> ALTAVEU 1: Jason, OK Vas
ser el número nou.

409
00:17:44,530 --> 00:17:46,700
Així que si vols seguir Ben així.

410
00:17:46,700 --> 00:17:47,010
>> ESTUDIANT: Jill.

411
00:17:47,010 --> 00:17:49,630
>> ALTAVEU 1: Jill, que serà
17, que si hagués fet això més

412
00:17:49,630 --> 00:17:51,260
intel · ligent, hauria
començat en l'altre extrem.

413
00:17:51,260 --> 00:17:52,370
Pots anar per aquest camí.

414
00:17:52,370 --> 00:17:53,030
22.

415
00:17:53,030 --> 00:17:53,670
I vostè és?

416
00:17:53,670 --> 00:17:53,980
>> ESTUDIANT: Maria.

417
00:17:53,980 --> 00:17:56,130
>> ALTAVEU 1: Mary, podràs 22.

418
00:17:56,130 --> 00:17:58,420
I el seu nom és?

419
00:17:58,420 --> 00:17:58,810
>> ESTUDIANT: Chris.

420
00:17:58,810 --> 00:18:00,100
>> ALTAVEU 1: Chris, seràs 26.

421
00:18:00,100 --> 00:18:00,740
I a continuació, finalment.

422
00:18:00,740 --> 00:18:01,400
>> ESTUDIANT: Diana.

423
00:18:01,400 --> 00:18:02,670
>> ALTAVEU 1: Diana, que serà 34.

424
00:18:02,670 --> 00:18:03,920
Així que véns per aquí.

425
00:18:03,920 --> 00:18:06,360
>> Molt bé, així que perfecte ordenats
ordenar ia.

426
00:18:06,360 --> 00:18:09,600
I seguirem endavant i fer això
perquè puguem realment -

427
00:18:09,600 --> 00:18:11,720
Ben vostè és només una mica de mirar
cap al no res allà.

428
00:18:11,720 --> 00:18:15,670
OK, així que seguirem endavant i representen el
l'ús d'armes, igual que jo, precisament,

429
00:18:15,670 --> 00:18:16,250
el que està passant.

430
00:18:16,250 --> 00:18:19,540
Així que endavant i donen-1
o dos peus entre vosaltres.

431
00:18:19,540 --> 00:18:22,900
I seguir endavant i apuntar amb una mà per
qualsevol que ha d'apuntar a

432
00:18:22,900 --> 00:18:23,470
en base a això.

433
00:18:23,470 --> 00:18:25,890
I si vostè és nul · la simplement apunt
directament cap a terra.

434
00:18:25,890 --> 00:18:27,690
Bé, molt bé.

435
00:18:27,690 --> 00:18:32,290
>> Així que ara tenim una llista enllaçada, i em va deixar
Proposo que jugaré el paper de

436
00:18:32,290 --> 00:18:35,110
PTR, així que no et molestis
portar això al voltant.

437
00:18:35,110 --> 00:18:37,830
I llavors - a algú convenció estúpid -
es pot trucar a això tot el que vulguis -

438
00:18:37,830 --> 00:18:39,800
punter predecessor, punter pred -

439
00:18:39,800 --> 00:18:43,930
és només el sobrenom que li vam donar a
nostre codi d'exemple per a la mà esquerra.

440
00:18:43,930 --> 00:18:47,240
L'altre, que mantindrà
un registre de qui és qui en el

441
00:18:47,240 --> 00:18:48,400
següents escenaris.

442
00:18:48,400 --> 00:18:52,390
>> Així que suposo que, en primer lloc, vull arrencar
que primer exemple de la inserció de, diguem

443
00:18:52,390 --> 00:18:54,330
20, a la llista.

444
00:18:54,330 --> 00:18:57,160
Així que vaig a necessitar a algú que
encarnar el número 20 per a nosaltres.

445
00:18:57,160 --> 00:18:58,950
Així que necessito a algú malloc
de l'audiència.

446
00:18:58,950 --> 00:18:59,380
Anem amunt.

447
00:18:59,380 --> 00:19:00,340
Com et dius?

448
00:19:00,340 --> 00:19:01,300
>> ESTUDIANT: Brian.

449
00:19:01,300 --> 00:19:05,270
>> ALTAVEU 1: Brian, d'acord, per la qual cosa
serà el node que conté 20.

450
00:19:05,270 --> 00:19:06,810
Bé, anem per aquí.

451
00:19:06,810 --> 00:19:10,025
I, òbviament, on
pertany Brian?

452
00:19:10,025 --> 00:19:12,190
Així, enmig de - en realitat,
Espera un minut.

453
00:19:12,190 --> 00:19:13,420
Estem fent aquesta fora d'ordre.

454
00:19:13,420 --> 00:19:17,170
Estem fent això molt més difícil
del que ha de ser en un principi.

455
00:19:17,170 --> 00:19:21,210
Bé, anem a la lliure Brian
i realloc Brian com cinc.

456
00:19:21,210 --> 00:19:23,680
>> OK, així que ara volem inserir
Brian com cinc.

457
00:19:23,680 --> 00:19:25,960
Així que veuen aquí al costat
Ben per un moment.

458
00:19:25,960 --> 00:19:28,250
I vostè pot dir probablement
quan aquesta història va.

459
00:19:28,250 --> 00:19:30,500
Però anem a pensar acuradament sobre
l'ordre de les operacions.

460
00:19:30,500 --> 00:19:32,880
I és precisament aquesta visual
que va a alinear

461
00:19:32,880 --> 00:19:34,080
amb aquest codi de mostra.

462
00:19:34,080 --> 00:19:40,120
Així que aquí he PTR apuntant inicialment
no en Ben, per se, sinó en el que sigui

463
00:19:40,120 --> 00:19:43,245
valoren que conté, que en aquest cas
és - ¿quin és el teu nom?

464
00:19:43,245 --> 00:19:43,670
>> ESTUDIANT: Jason.

465
00:19:43,670 --> 00:19:47,350
>> ALTAVEU 1: Jason, per tant Ben i jo som
assenyalant a Jason en aquest moment.

466
00:19:47,350 --> 00:19:49,700
Així que ara he de determinar,
on pertany Brian?

467
00:19:49,700 --> 00:19:53,500
Així que l'únic que tinc accés a
ara és el seu element de dades n.

468
00:19:53,500 --> 00:19:58,280
Així que vaig a comprovar, està
Brian menys de Jason?

469
00:19:58,280 --> 00:19:59,770
La resposta és vertadera.

470
00:19:59,770 --> 00:20:03,680
>> ¿I ara què ha de succeir,
en l'ordre correcte?

471
00:20:03,680 --> 00:20:07,120
Necessito actualitzar quants punters
en total en aquesta història?

472
00:20:07,120 --> 00:20:10,720
Quan la meva mà se segueix apuntant a
Jason, i la seva mà - si vol

473
00:20:10,720 --> 00:20:12,930
posar la seva mà com, més o menys, em
no sé, un signe d'interrogació.

474
00:20:12,930 --> 00:20:14,070
Bé, bé.

475
00:20:14,070 --> 00:20:15,670
>> Bé, pel que té
alguns candidats.

476
00:20:15,670 --> 00:20:20,500
Qualsevol de Ben, jo o Brian o Jason
o qualsevol altra persona, que

477
00:20:20,500 --> 00:20:21,370
punters han de canviar?

478
00:20:21,370 --> 00:20:23,260
Quants en total?

479
00:20:23,260 --> 00:20:24,080
>> OK, així que dos.

480
00:20:24,080 --> 00:20:27,090
El meu punter en realitat no importa ja
perquè jo sóc només temporal.

481
00:20:27,090 --> 00:20:31,370
Així que aquests dos homes, presumiblement,
tant Ben i Brian.

482
00:20:31,370 --> 00:20:34,410
Així que em proposo que actualitzem
Ben, ja que ell és primer.

483
00:20:34,410 --> 00:20:36,350
El primer element de la llista
Ara serà Brian.

484
00:20:36,350 --> 00:20:38,070
Així que el punt a Ben Brian.

485
00:20:38,070 --> 00:20:39,320
Bé, i ara què?

486
00:20:39,320 --> 00:20:41,950

487
00:20:41,950 --> 00:20:43,460
>> Qui aconsegueix assenyalar qui?

488
00:20:43,460 --> 00:20:44,710
>> ESTUDIANT: [inaudible].

489
00:20:44,710 --> 00:20:46,180
>> ALTAVEU 1: Acceptar el que Brian té
per apuntar a Jason.

490
00:20:46,180 --> 00:20:48,360
Però he perdut el compte de que el punter?

491
00:20:48,360 --> 00:20:49,980
Sé que Jason és?

492
00:20:49,980 --> 00:20:50,790
>> ESTUDIANT: [inaudible].

493
00:20:50,790 --> 00:20:52,620
>> ALTAVEU 1: jo, com sóc
el punter temporal.

494
00:20:52,620 --> 00:20:55,110
I presumiblement, no he canviat
per assenyalar en el nou node.

495
00:20:55,110 --> 00:20:58,300
Així que podem tenir simplement el punt Brian
en què estic assenyalant.

496
00:20:58,300 --> 00:20:59,000
I ja està.

497
00:20:59,000 --> 00:21:01,890
Així cas que un, la inserció en el
principi de la llista.

498
00:21:01,890 --> 00:21:02,950
Hi havia dos passos clau.

499
00:21:02,950 --> 00:21:06,750
Un d'ells, hem de actualitzar Ben, i després
també hem de actualitzar Brian.

500
00:21:06,750 --> 00:21:09,230
I llavors no he de preocupar
penosament a través de la resta de la

501
00:21:09,230 --> 00:21:12,680
llista, perquè ja trobem la seva
lloc, perquè pertanyia a la

502
00:21:12,680 --> 00:21:14,080
a l'esquerra del primer element.

503
00:21:14,080 --> 00:21:15,400
>> Molt bé, així que bastant senzill.

504
00:21:15,400 --> 00:21:18,110
De fet, se sent com que estem gairebé
fent això massa complicat.

505
00:21:18,110 --> 00:21:20,240
Així que ara arrencar al final
de la llista, i veure on

506
00:21:20,240 --> 00:21:21,380
s'inicia la complexitat.

507
00:21:21,380 --> 00:21:24,560
Així que si ara, Alloc de l'audiència.

508
00:21:24,560 --> 00:21:25,540
Algú vol jugar a 55?

509
00:21:25,540 --> 00:21:26,700
Bé, vaig veure la seva mà primer.

510
00:21:26,700 --> 00:21:29,620
Anem amunt.

511
00:21:29,620 --> 00:21:30,030
Si.

512
00:21:30,030 --> 00:21:31,177
Com et dius?

513
00:21:31,177 --> 00:21:32,310
>> ESTUDIANT: [inaudible].

514
00:21:32,310 --> 00:21:33,240
>> ALTAVEU 1: Habata.

515
00:21:33,240 --> 00:21:33,890
Bé, anem amunt.

516
00:21:33,890 --> 00:21:35,730
Vostè serà el número 55.

517
00:21:35,730 --> 00:21:37,820
Així que, per descomptat, pertany
al final de la llista.

518
00:21:37,820 --> 00:21:41,850
Així que anem a reproduir la simulació amb mi
sent el PTX per un moment.

519
00:21:41,850 --> 00:21:44,050
Així que estic primer va a apuntar a
Ben ho està apuntant.

520
00:21:44,050 --> 00:21:45,900
Els dos estem apuntant ara a Brian.

521
00:21:45,900 --> 00:21:48,420
Així que 55 no sigui inferior a cinc.

522
00:21:48,420 --> 00:21:52,510
Així que vaig a actualitzar el meu mateix
apuntant a la triple de Brian, que

523
00:21:52,510 --> 00:21:54,450
Ara és, per descomptat, Jason.

524
00:21:54,450 --> 00:21:57,310
55 No és menys de nou anys, per la
Vaig a actualitzar PTR.

525
00:21:57,310 --> 00:21:58,890
Vaig a actualitzar PTR.

526
00:21:58,890 --> 00:22:02,290
Vaig a actualitzar PTR
Em va a actualitzar PTR.

527
00:22:02,290 --> 00:22:05,060
I jo vaig a - hmm, què
el teu nom?

528
00:22:05,060 --> 00:22:05,560
>> ESTUDIANT: Diana.

529
00:22:05,560 --> 00:22:09,190
>> ALTAVEU 1: Diana està assenyalant, per descomptat,
en nul amb la mà esquerra.

530
00:22:09,190 --> 00:22:13,030
Llavors, on Habata realitat
pertanyen clarament?

531
00:22:13,030 --> 00:22:15,050
A l'esquerra, aquí.

532
00:22:15,050 --> 00:22:19,460
Llavors, com puc saber que posar aquí
Crec que m'he cagat.

533
00:22:19,460 --> 00:22:22,420
Perquè el que és l'art PTR
aquest moment en el temps?

534
00:22:22,420 --> 00:22:23,240
Null.

535
00:22:23,240 --> 00:22:25,580
Així que tot i que, visualment, podem
òbviament veure tots aquests

536
00:22:25,580 --> 00:22:26,610
nois aquí a l'escenari.

537
00:22:26,610 --> 00:22:29,680
No he seguit la pista dels anteriors
persona en la llista.

538
00:22:29,680 --> 00:22:33,210
Jo no tinc un dit assenyalant,
en aquest cas, el nombre de node 34.

539
00:22:33,210 --> 00:22:34,760
>> Així que anem a començar realment sobre això.

540
00:22:34,760 --> 00:22:37,560
Així que ara realment necessito
una segona variable local.

541
00:22:37,560 --> 00:22:40,980
I això és el que veuràs al
codi C mostra real, en tant que jo vaig,

542
00:22:40,980 --> 00:22:45,860
quan actualitzo la meva mà dreta per indicar
Jason, deixant per tant darrere de Brian, em

543
00:22:45,860 --> 00:22:51,440
millor començar a utilitzar la mà esquerra per
actualitzar on era, pel que a mesura que vagi

544
00:22:51,440 --> 00:22:52,700
a través d'aquesta llista -

545
00:22:52,700 --> 00:22:55,040
més maldestre del que pensava
Ara aquí visual -

546
00:22:55,040 --> 00:22:56,740
Vaig a arribar a la
final de la llista.

547
00:22:56,740 --> 00:23:00,020
>> Aquesta part segueix sent nul, la qual cosa és bastant
inútil, excepte per indicar

548
00:23:00,020 --> 00:23:02,980
Estic clarament al final de la llista,
però ara almenys tinc aquesta

549
00:23:02,980 --> 00:23:08,270
punter predecessor assenyalant aquí, així
¿I ara què mans i quins indicadors s'han

550
00:23:08,270 --> 00:23:10,150
d'actualitzar?

551
00:23:10,150 --> 00:23:13,214
Qual la mà és el que vols
tornar a configurar per primera vegada?

552
00:23:13,214 --> 00:23:15,190
>> ESTUDIANT: [inaudible].

553
00:23:15,190 --> 00:23:16,220
>> ALTAVEU 1: OK, així que Diana.

554
00:23:16,220 --> 00:23:21,110
On vol assenyalar
Punter esquerre de Diana a?

555
00:23:21,110 --> 00:23:23,620
En 55, presumiblement, de manera que
hem inserit allà.

556
00:23:23,620 --> 00:23:25,560
¿I on hauria d'anar 55 punter?

557
00:23:25,560 --> 00:23:27,000
Pressionat, que representa un valor nul.

558
00:23:27,000 --> 00:23:28,890
I les mans, en aquest punt, no
importa perquè no eren més que

559
00:23:28,890 --> 00:23:30,070
variables temporals.

560
00:23:30,070 --> 00:23:31,030
Així que ara que hem acabat.

561
00:23:31,030 --> 00:23:34,650
>> Així que la complexitat addicional allà - i
que no és tan difícil d'implementar,

562
00:23:34,650 --> 00:23:38,660
però necessitem una variable secundària per fer
Assegureu-vos que abans de passar al meu dret

563
00:23:38,660 --> 00:23:42,140
banda, puc actualitzar el valor de la meva esquerra
mà, punter pred en aquest cas, per la

564
00:23:42,140 --> 00:23:45,860
que tinc un indicador de seguiment
fer un seguiment d'on era.

565
00:23:45,860 --> 00:23:49,360
Ara, en un apart, si estàs pensant en aquest
a través, això se sent com si fos un

566
00:23:49,360 --> 00:23:51,490
mica molest haver de mantenir
seguiment d'aquesta mà esquerra.

567
00:23:51,490 --> 00:23:54,015
>> Com seria una altra solució
a aquest problema han estat?

568
00:23:54,015 --> 00:23:56,500
Si has arribat a redissenyar les dades
estructura que estem parlant

569
00:23:56,500 --> 00:23:59,630
a través d'aquests moments?

570
00:23:59,630 --> 00:24:02,690
Si aquest tipus només se sent una mica de
molest tenir, com, dos punters

571
00:24:02,690 --> 00:24:08,430
passant per la llista, qui més podria
han, en un món ideal, mantingut

572
00:24:08,430 --> 00:24:10,160
informació que necessitem?

573
00:24:10,160 --> 00:24:11,360
Sí?

574
00:24:11,360 --> 00:24:12,610
>> ESTUDIANT: [inaudible].

575
00:24:12,610 --> 00:24:15,160

576
00:24:15,160 --> 00:24:16,150
>> ALTAVEU 1: Exactament.

577
00:24:16,150 --> 00:24:19,130
Just el que en realitat hi ha una interessant
germen d'una idea.

578
00:24:19,130 --> 00:24:22,470
I aquesta idea d'un punter anterior,
assenyalant l'element anterior.

579
00:24:22,470 --> 00:24:25,580
Què passa si jo encarnat que
dins de la pròpia llista?

580
00:24:25,580 --> 00:24:27,810
I serà difícil de visualitzar
això sense tot el paper

581
00:24:27,810 --> 00:24:28,830
caure a terra.

582
00:24:28,830 --> 00:24:31,860
Però suposem que aquests nois utilitzen tant
de les seves mans per tenir una prèvia

583
00:24:31,860 --> 00:24:35,950
punter, i un indicador de següent, així
aplicació del que anem a trucar a un doble

584
00:24:35,950 --> 00:24:36,830
llista enllaçada.

585
00:24:36,830 --> 00:24:41,090
Això em permetrà espècie de rebobinat,
molt més fàcil i sense mi, el

586
00:24:41,090 --> 00:24:43,800
programador, haver de mantenir
seguiment manual -

587
00:24:43,800 --> 00:24:44,980
veritablement manualment -

588
00:24:44,980 --> 00:24:47,280
d'on havia estat prèviament
a la llista.

589
00:24:47,280 --> 00:24:48,110
Així que no farem això.

590
00:24:48,110 --> 00:24:50,950
Anem a mantenir simple, perquè això és
tindrà un preu, el doble de

591
00:24:50,950 --> 00:24:53,450
molt espai per als punters,
si vols una segona.

592
00:24:53,450 --> 00:24:55,760
Però això és realment un comú
estructura de dades coneguda com

593
00:24:55,760 --> 00:24:57,410
llista doblement enllaçada.

594
00:24:57,410 --> 00:25:01,310
>> Anem a fer l'últim exemple aquí i posar
aquests nois de la seva misèria.

595
00:25:01,310 --> 00:25:03,270
Així malloc 20.

596
00:25:03,270 --> 00:25:05,320
Anem a partir del passadís allà.

597
00:25:05,320 --> 00:25:06,280
Bé, quin és el teu nom?

598
00:25:06,280 --> 00:25:07,440
>> ESTUDIANT: [inaudible].

599
00:25:07,440 --> 00:25:07,855
>> ALTAVEU 1: Com?

600
00:25:07,855 --> 00:25:08,480
>> ESTUDIANT: [inaudible].

601
00:25:08,480 --> 00:25:09,410
>> ALTAVEU 1: Demeron?

602
00:25:09,410 --> 00:25:10,230
Acceptar anem amunt.

603
00:25:10,230 --> 00:25:11,910
Vostè serà el 20.

604
00:25:11,910 --> 00:25:14,720
Vostè, evidentment, va a
pertanyen entre el 17 i el 22.

605
00:25:14,720 --> 00:25:16,150
Així que anem a aprendre la lliçó.

606
00:25:16,150 --> 00:25:18,150
Vaig a començar punter
assenyalant a Brian.

607
00:25:18,150 --> 00:25:21,190
I jo tindré la meva mà esquerra
només actualitzar a Brian com em mut a

608
00:25:21,190 --> 00:25:23,600
Jason, la comprovació de fa 20 a menys de nou?

609
00:25:23,600 --> 00:25:24,060
No

610
00:25:24,060 --> 00:25:25,430
És 20 menys de 17?

611
00:25:25,430 --> 00:25:25,880
No

612
00:25:25,880 --> 00:25:27,450
És 20 menys de 22?

613
00:25:27,450 --> 00:25:28,440
Sí

614
00:25:28,440 --> 00:25:34,070
Llavors, ¿quins consells o les mans han de canviar
on estan apuntant ara?

615
00:25:34,070 --> 00:25:37,070
>> Així que podem fer 17 apuntant a 20.

616
00:25:37,070 --> 00:25:37,860
Així està bé.

617
00:25:37,860 --> 00:25:40,080
On volem assenyalar
el punter ara?

618
00:25:40,080 --> 00:25:41,330
Als 22 anys.

619
00:25:41,330 --> 00:25:45,410
I sabem que 22 és, de nou, gràcies
al meu punter temporal.

620
00:25:45,410 --> 00:25:46,760
Així que estem bé.

621
00:25:46,760 --> 00:25:49,440
Així que per la seva emmagatzematge temporal
He mantingut un seguiment d'on és cadascú.

622
00:25:49,440 --> 00:25:55,055
I ara vostè pot anar visualment on
al qual pertany, i ara necessita 1, 2, 3,

623
00:25:55,055 --> 00:25:58,410
4, 5, 6, 7, 8, 9 boles de la tensió,
i una ronda d'aplaudiments per

624
00:25:58,410 --> 00:25:59,770
aquests nois, si poguéssim.

625
00:25:59,770 --> 00:26:00,410
Molt ben fet.

626
00:26:00,410 --> 00:26:05,320
>> [Aplaudiments]

627
00:26:05,320 --> 00:26:06,330
>> ALTAVEU 1: D'acord.

628
00:26:06,330 --> 00:26:09,860
I és possible mantenir les peces
de paper com records.

629
00:26:09,860 --> 00:26:15,930
>> D'acord, llavors, confia en mi, és molt
fàcil de caminar a través que, amb

630
00:26:15,930 --> 00:26:17,680
els humans del que és amb codi real.

631
00:26:17,680 --> 00:26:22,690
Però el que trobarà en un moment
Ara, és el mateix - Oh, gràcies.

632
00:26:22,690 --> 00:26:23,630
Gràcies -

633
00:26:23,630 --> 00:26:29,360
és que trobareu que les mateixes dades
estructura, una llista enllaçada, en realitat es pot

634
00:26:29,360 --> 00:26:33,200
pot utilitzar com un bloc de construcció per més
estructures de dades sofisticades.

635
00:26:33,200 --> 00:26:37,620
>> I compte també el tema aquí és que
hem absolutament introduït més

636
00:26:37,620 --> 00:26:40,060
complexitat en la implementació
d'aquest algorisme.

637
00:26:40,060 --> 00:26:43,940
Inserció, i si passem per ella,
eliminació i recerca, és una mica

638
00:26:43,940 --> 00:26:46,660
més complicat del que
estava amb una matriu.

639
00:26:46,660 --> 00:26:48,040
Però vam guanyar cert dinamisme.

640
00:26:48,040 --> 00:26:50,180
Tenim una estructura de dades d'adaptació.

641
00:26:50,180 --> 00:26:54,010
>> Però, de nou, hem de pagar un preu de tenir algun
complexitat addicional, tant en

642
00:26:54,010 --> 00:26:54,910
seva aplicació.

643
00:26:54,910 --> 00:26:56,750
I se'ns dóna l'accés aleatori.

644
00:26:56,750 --> 00:27:00,450
I per ser honest, no hi ha algun bon
netejar diapositiva que puc donar-te que

645
00:27:00,450 --> 00:27:03,120
diu aquí és per què una llista enllaçada
és millor que una matriu.

646
00:27:03,120 --> 00:27:04,100
I deixar les coses així.

647
00:27:04,100 --> 00:27:07,520
A causa de que el tema es repeteixi ara, fins i tot
més en les pròximes setmanes, és

648
00:27:07,520 --> 00:27:10,200
que no és necessàriament
una resposta correcta.

649
00:27:10,200 --> 00:27:13,830
>> És per això que tenim l'eix independent
de disseny per als butlletins de problemes.

650
00:27:13,830 --> 00:27:17,700
Serà molt sensibles al context
si voleu utilitzar aquestes dades

651
00:27:17,700 --> 00:27:21,750
estructura o allò, i ho farà
dependrà del que li importa a vostè en termes

652
00:27:21,750 --> 00:27:24,620
dels recursos i la complexitat.

653
00:27:24,620 --> 00:27:28,830
>> Però permetin-me proposar que les dades ideals
estructura, el sant grial, seria

654
00:27:28,830 --> 00:27:32,200
una cosa que és constant de temps,
independentment de la quantitat de coses és

655
00:27:32,200 --> 00:27:36,940
dins d'ella, no seria increïble si un
estructura de dades retornada en respostes

656
00:27:36,940 --> 00:27:37,920
constant de temps.

657
00:27:37,920 --> 00:27:38,330
Sí

658
00:27:38,330 --> 00:27:40,110
Aquesta paraula està en la seva enorme diccionari.

659
00:27:40,110 --> 00:27:41,550
O no, aquesta paraula no és.

660
00:27:41,550 --> 00:27:43,270
O qualsevol problema.

661
00:27:43,270 --> 00:27:46,360
Bé anem a veure si no podem, almenys,
fer un pas en aquesta direcció.

662
00:27:46,360 --> 00:27:50,190
>> Permetin-me proposar una nova estructura de dades que
es pot utilitzar per a diferents coses,

663
00:27:50,190 --> 00:27:52,260
en aquest cas es diu una taula hash.

664
00:27:52,260 --> 00:27:55,590
I pel que estem realment tornar a mirar
en una matriu, en aquest cas, i

665
00:27:55,590 --> 00:28:00,550
tant arbitràriament, he dibuixat aquesta
taula hash com una matriu amb una mena de

666
00:28:00,550 --> 00:28:02,810
matriu de dues dimensions -

667
00:28:02,810 --> 00:28:05,410
o més aviat que està representat aquí com una de dues
matriu bidimensional - però això és només

668
00:28:05,410 --> 00:28:10,770
una matriu de mida 26, de manera que si ens
truqui a la taula d'arranjament, suport de taula

669
00:28:10,770 --> 00:28:12,440
zero és el rectangle a la part superior.

670
00:28:12,440 --> 00:28:15,090
Taula suport 25 és el rectangle
a la part inferior.

671
00:28:15,090 --> 00:28:18,620
I així és com jo podria dibuixar un conjunt de dades
estructura en què vull guardar

672
00:28:18,620 --> 00:28:19,790
noms de les persones.

673
00:28:19,790 --> 00:28:24,370
>> Així, per exemple, i no vaig a assenyalar a la
Tot aquí al cap, si em

674
00:28:24,370 --> 00:28:29,160
tingut aquesta sèrie, que ara vaig a
cridar a una taula hash, i això és nou

675
00:28:29,160 --> 00:28:31,360
posició zero.

676
00:28:31,360 --> 00:28:34,840
Això aquí és la ubicació
un, i així successivament.

677
00:28:34,840 --> 00:28:37,880
Afirmo que vull utilitzar aquestes dades
estructura, pel bé de la discussió,

678
00:28:37,880 --> 00:28:42,600
per emmagatzemar noms de les persones, Alice i Bob
i Charlie i altres noms.

679
00:28:42,600 --> 00:28:46,110
Així que pensar en aquest moment com l'inici
de, per exemple, un diccionari

680
00:28:46,110 --> 00:28:47,520
amb un munt de paraules.

681
00:28:47,520 --> 00:28:49,435
Ells resulten ser noms
en el nostre exemple.

682
00:28:49,435 --> 00:28:52,560
I això és molt pertinent, potser,
la implementació d'un corrector ortogràfic, ja que

683
00:28:52,560 --> 00:28:54,400
podrien, per problema plantejat 06:00.

684
00:28:54,400 --> 00:28:59,300
>> Així que si tenim una matriu de mida total de 26
pel que aquesta és la ubicació 25a

685
00:28:59,300 --> 00:29:03,390
a la part inferior, i jo sostinc que Alice és
la primera paraula en el diccionari de

686
00:29:03,390 --> 00:29:07,260
noms que voleu inserir en la memòria RAM,
en aquesta estructura de dades, on són

687
00:29:07,260 --> 00:29:12,480
instint li diu que d'Alice
nom ha d'anar en aquesta sèrie?

688
00:29:12,480 --> 00:29:13,510
>> Comptem amb 26 opcions.

689
00:29:13,510 --> 00:29:14,990
On volem posar?

690
00:29:14,990 --> 00:29:16,200
Nosaltres la volem en suport de zero, no?

691
00:29:16,200 --> 00:29:18,280
Una d'Alice, anem a trucar a aquest zero.

692
00:29:18,280 --> 00:29:20,110
I B serà un, i C serà de dos.

693
00:29:20,110 --> 00:29:22,600
Així que anem a escriure
El nom d'Alice aquí.

694
00:29:22,600 --> 00:29:24,890
Si després inserim Bob, la seva
nom anirà aquí.

695
00:29:24,890 --> 00:29:27,280
Charlie es veu aquí.

696
00:29:27,280 --> 00:29:30,500
I així successivament al llarg de
aquesta estructura de dades.

697
00:29:30,500 --> 00:29:32,090
>> Aquesta és una estructura de dades meravellosa.

698
00:29:32,090 --> 00:29:32,730
Per què?

699
00:29:32,730 --> 00:29:37,460
Bé, què és el temps d'execució de
inserir el nom d'un ésser humà en aquest

700
00:29:37,460 --> 00:29:39,850
estructura de dades en aquest moment?

701
00:29:39,850 --> 00:29:43,702
Tenint en compte que aquesta taula s'implementa,
realment, com una matriu.

702
00:29:43,702 --> 00:29:44,940
Bé, és la constant de temps.

703
00:29:44,940 --> 00:29:45,800
És la fi d'un.

704
00:29:45,800 --> 00:29:46,360
Per què?

705
00:29:46,360 --> 00:29:48,630
>> Bé, com determinar
on Alice pertany?

706
00:29:48,630 --> 00:29:51,000
Et veus en quina lletra del seu nom?

707
00:29:51,000 --> 00:29:51,490
El primer.

708
00:29:51,490 --> 00:29:54,350
I es pot arribar, si es tracta d'una cadena,
amb només mirar cadena

709
00:29:54,350 --> 00:29:55,200
suport de zero.

710
00:29:55,200 --> 00:29:57,110
Per tant el caràcter zero de la cadena.

711
00:29:57,110 --> 00:29:57,610
Això és fàcil.

712
00:29:57,610 --> 00:30:00,350
Vam fer això en la criptografia
Fa setmanes assignació.

713
00:30:00,350 --> 00:30:05,310
I després un cop heu escoltat que Alice
carta està Capital, podem restar

714
00:30:05,310 --> 00:30:08,160
de 65 o de capital A si mateix,
això ens dóna zero.

715
00:30:08,160 --> 00:30:10,940
Així que ara sabem que Alice pertany
en la posició zero.

716
00:30:10,940 --> 00:30:14,240
>> I com un punter a aquestes dades
estructura, d'algun tipus, quant de temps fa

717
00:30:14,240 --> 00:30:18,840
que em porti a trobar la ubicació
zero en una matriu?

718
00:30:18,840 --> 00:30:22,080
A només un pas, no és la constant de temps
causa de l'accés aleatori que

719
00:30:22,080 --> 00:30:23,780
proposat era una característica d'una matriu.

720
00:30:23,780 --> 00:30:28,570
Així que en resum, esbrinar el que l'índex de
del nom d'Alice és, que és, en

721
00:30:28,570 --> 00:30:32,610
aquest cas, és A, o només anem a resoldre
que a zero, on B és un i C és

722
00:30:32,610 --> 00:30:34,900
2, pensant que fos
és la constant de temps.

723
00:30:34,900 --> 00:30:38,510
Només he de mirar en la seva primera carta,
esbrinar on zero és un

724
00:30:38,510 --> 00:30:40,460
matriu és també constant de temps.

725
00:30:40,460 --> 00:30:42,140
Així que tècnicament això és
com dos passos ara.

726
00:30:42,140 --> 00:30:43,330
Però això segueix sent constant.

727
00:30:43,330 --> 00:30:46,880
Així que cridem a aquest gran O d'un, pel que hem
Alice s'insereix en aquesta taula en

728
00:30:46,880 --> 00:30:48,440
constant de temps.

729
00:30:48,440 --> 00:30:50,960
>> Però, per descomptat, estic sent
ingenu, no?

730
00:30:50,960 --> 00:30:53,240
Què passa si hi ha un Aaron a la classe?

731
00:30:53,240 --> 00:30:53,990
O Alícia?

732
00:30:53,990 --> 00:30:57,230
O qualsevol altre nom a partir d'
A. On posarem

733
00:30:57,230 --> 00:31:00,800
aquesta persona, oi?

734
00:31:00,800 --> 00:31:03,420
Vull dir, ara mateix només hi ha tres
la gent a taula, així que potser

735
00:31:03,420 --> 00:31:07,490
ha de posar Aaron en la ubicació
zero, un, dos, tres.

736
00:31:07,490 --> 00:31:09,480
>> Bé, jo podria posar una aquí.

737
00:31:09,480 --> 00:31:13,350
Però llavors, si es vol inserir en David
aquesta llista, a on va David?

738
00:31:13,350 --> 00:31:15,170
Ara el nostre sistema comença a analitzar
baix, dreta?

739
00:31:15,170 --> 00:31:19,210
Perquè ara David acaba aquí
si Aaron és en realitat aquí.

740
00:31:19,210 --> 00:31:23,060
I ara tota aquesta idea de tenir un
estructura de dades neta que ens dóna

741
00:31:23,060 --> 00:31:28,010
insercions constant de temps ja no és
constant de temps, perquè he de

742
00:31:28,010 --> 00:31:31,240
veure, oh, maleïda sigui, algú que ja és
en la ubicació d'Alice.

743
00:31:31,240 --> 00:31:35,320
>> Déjame investigar la resta d'aquestes dades
estructura, a la recerca d'un lloc per posar

744
00:31:35,320 --> 00:31:37,130
algú com el nom d'Aaron.

745
00:31:37,130 --> 00:31:39,390
I això també està començant
prendre el temps lineal.

746
00:31:39,390 --> 00:31:42,710
D'altra banda, si ara vol trobar la
Aaron en aquesta estructura de dades, i

747
00:31:42,710 --> 00:31:45,430
verificació, i el nom d'Aaron no és aquí.

748
00:31:45,430 --> 00:31:47,960
L'ideal seria que vostè acaba de dir d'Aaron
no en l'estructura de dades.

749
00:31:47,960 --> 00:31:51,530
Però si ho fa començar a fer espai per
Aaron on no hauria d'haver estat un D

750
00:31:51,530 --> 00:31:55,600
o un correu, vostè, pitjor dels casos, ha de comprovar
tota l'estructura de dades, en

751
00:31:55,600 --> 00:31:59,480
aquest cas es convertís en alguna cosa
lineal en la mida de la taula.

752
00:31:59,480 --> 00:32:00,920
>> Així bé, vaig a arreglar això.

753
00:32:00,920 --> 00:32:04,200
El problema aquí és que vaig tenir
26 elements d'aquesta matriu.

754
00:32:04,200 --> 00:32:05,000
Permetin-me canviar-lo.

755
00:32:05,000 --> 00:32:06,010
Vaya.

756
00:32:06,010 --> 00:32:10,600
Déjame canviar de manera que en lloc de ser de
talla 26 en total, compte de la part inferior

757
00:32:10,600 --> 00:32:12,720
índex es canviarà a n almenys 1.

758
00:32:12,720 --> 00:32:16,610
Si 26 és clarament massa petit per als éssers humans '
noms, perquè hi ha milers de

759
00:32:16,610 --> 00:32:20,830
noms del món, farem
en 100 o 1000 o 10000.

760
00:32:20,830 --> 00:32:22,960
Anem a assignar molt més espai.

761
00:32:22,960 --> 00:32:27,230
>> Bé, això no disminueix necessàriament
la probabilitat que no tindrem dos

762
00:32:27,230 --> 00:32:31,510
persones amb noms que comencin amb A, i
així, que anava a tractar de posar un

763
00:32:31,510 --> 00:32:33,120
noms a zero lloc encara.

764
00:32:33,120 --> 00:32:36,850
Encara van a col · lisionar, el que
vol dir que encara tenim una solució per posar

765
00:32:36,850 --> 00:32:41,020
Alice i Aaron i Alicia i altres
noms que comencin amb A qualsevol altre lloc.

766
00:32:41,020 --> 00:32:43,460
Però, quant d'un problema és això?

767
00:32:43,460 --> 00:32:46,870
Quina és la probabilitat que
tenir col · lisions en un conjunt de dades

768
00:32:46,870 --> 00:32:48,240
estructura com aquesta?

769
00:32:48,240 --> 00:32:52,570
>> Bé, deixa - tornarem
a aquesta pregunta aquí.

770
00:32:52,570 --> 00:32:55,530
I mira com podríem
resoldre primer.

771
00:32:55,530 --> 00:32:58,480
Déjame treure aquesta proposta aquí.

772
00:32:58,480 --> 00:33:02,020
El que acabem de descriure és un algorisme,
una heurística anomenada lineal

773
00:33:02,020 --> 00:33:05,030
sondeig segons el qual, si tractes d'inserir
alguna cosa aquí en aquestes dades

774
00:33:05,030 --> 00:33:08,920
estructura, que es diu una taula hash,
i no hi ha lloc allà,

775
00:33:08,920 --> 00:33:12,000
veritablement sondejar l'estructura de dades
comprovació, és aquesta disponible?

776
00:33:12,000 --> 00:33:13,430
Està aquesta disponible és aquesta disponible?

777
00:33:13,430 --> 00:33:13,980
És aquesta disponible?

778
00:33:13,980 --> 00:33:17,550
I quan per fi és, inserir el
nom que vostè pretén inicialment

779
00:33:17,550 --> 00:33:19,370
en un altre lloc en aquesta ubicació.

780
00:33:19,370 --> 00:33:23,360
Però en el pitjor dels casos, l'únic punt
podria ser la part més baixa de les dades

781
00:33:23,360 --> 00:33:25,090
estructura, el final de la sèrie.

782
00:33:25,090 --> 00:33:30,130
>> Així que intento lineal, en el pitjor dels casos,
recau en un algoritme lineal on

783
00:33:30,130 --> 00:33:34,500
Aaron, si passa a ser inserit darrera
en aquesta estructura de dades, que podria

784
00:33:34,500 --> 00:33:39,540
topar amb aquesta primera ubicació, però
després acabar la mala sort al final.

785
00:33:39,540 --> 00:33:43,940
Així que això no és una constant
temps sant grial per a nosaltres.

786
00:33:43,940 --> 00:33:47,650
Aquest enfocament dels elements d'inserció en
una estructura de dades anomenada hash

787
00:33:47,650 --> 00:33:52,050
taula no sembla ser la constant de temps
almenys no en el cas general.

788
00:33:52,050 --> 00:33:54,000
Pot delegar en alguna cosa lineal.

789
00:33:54,000 --> 00:33:56,970
>> I què si resolem col · lisions
alguna cosa diferent?

790
00:33:56,970 --> 00:34:00,740
Així que aquí està una més sofisticada
acostar-se al que és encara

791
00:34:00,740 --> 00:34:02,800
anomenada taula hash.

792
00:34:02,800 --> 00:34:05,890
I als resums, en un apart, el que
És a dir és l'índex que

793
00:34:05,890 --> 00:34:07,070
M'he referit abans.

794
00:34:07,070 --> 00:34:09,810
Per a alguna cosa hash pot ser
considerat com un verb.

795
00:34:09,810 --> 00:34:13,690
>> Així que si vostè haixix Alice és un nom,
una funció hash, per així dir-ho,

796
00:34:13,690 --> 00:34:14,710
ha de retornar un nombre.

797
00:34:14,710 --> 00:34:18,199
En aquest cas és zero si pertany al
posició zero, un, si pertany a

798
00:34:18,199 --> 00:34:20,000
ubicació un, i així successivament.

799
00:34:20,000 --> 00:34:24,360
Així que la meva funció hash fins ara ha estat
super simple, només mirant a la

800
00:34:24,360 --> 00:34:26,159
primera lletra del nom d'algú.

801
00:34:26,159 --> 00:34:29,090
No obstant això, una funció hash pren com
entrada d'algun dada, un

802
00:34:29,090 --> 00:34:30,210
cadena, un enter, el que sigui.

803
00:34:30,210 --> 00:34:32,239
I escup típicament un nombre.

804
00:34:32,239 --> 00:34:35,739
I aquest nombre és on les dades
element pertany a una estructura de dades

805
00:34:35,739 --> 00:34:37,800
coneguda aquí com una taula hash.

806
00:34:37,800 --> 00:34:41,400
>> Així que només intuïtivament, es tracta d'una
lleugerament diferent context.

807
00:34:41,400 --> 00:34:44,170
En realitat, això es refereix a un exemple
aniversari impliquen, si

808
00:34:44,170 --> 00:34:46,850
pot haver tants com
31 dies al mes.

809
00:34:46,850 --> 00:34:52,239
Però, ¿què aquesta persona decideix
fer en cas d'una col · lisió?

810
00:34:52,239 --> 00:34:55,304
Context sent ara, no és un xoc de
noms, però una col · lisió dels aniversaris,

811
00:34:55,304 --> 00:35:00,760
si dues persones tenen la mateixa data de naixement en
el 2 d'octubre, per exemple.

812
00:35:00,760 --> 00:35:02,120
>> ESTUDIANT: [inaudible].

813
00:35:02,120 --> 00:35:05,010
>> ALTAVEU 1: Sí, així que aquí tenim
l'aprofitament de les llistes enllaçades.

814
00:35:05,010 --> 00:35:07,830
Així es veu una mica diferent
que traiem abans.

815
00:35:07,830 --> 00:35:10,790
Però sembla que tenim un array
a la banda esquerra.

816
00:35:10,790 --> 00:35:13,230
Això és un índex, per no
raó en particular.

817
00:35:13,230 --> 00:35:14,630
Però segueix sent una matriu.

818
00:35:14,630 --> 00:35:16,160
És una matriu de punters.

819
00:35:16,160 --> 00:35:20,670
I cada un d'aquests elements, cadascun dels
aquests cercles o barres - la barra

820
00:35:20,670 --> 00:35:23,970
que representa null - cada un d'aquests
punters és aparentment apunten

821
00:35:23,970 --> 00:35:25,730
quina estructura de dades?

822
00:35:25,730 --> 00:35:26,890
Una llista enllaçada.

823
00:35:26,890 --> 00:35:30,530
>> Així que ara tenim la capacitat de
codificar en el nostre programa

824
00:35:30,530 --> 00:35:32,010
la mida de la taula.

825
00:35:32,010 --> 00:35:35,360
En aquest cas, sabem que mai cal
més de 31 dies en un mes.

826
00:35:35,360 --> 00:35:38,480
Tan difícil de codificar un valor com 31 es
raonable en aquest context.

827
00:35:38,480 --> 00:35:42,700
En el context dels noms, difícil de codificació
26 no és raonable que la gent

828
00:35:42,700 --> 00:35:46,340
només noms comencen amb, per exemple,
l'alfabet de l'A a la Z. participació

829
00:35:46,340 --> 00:35:50,180
>> Podem ficar a tots en què les dades
estructura, sempre que, quan arribem a

830
00:35:50,180 --> 00:35:55,330
col · lisió, no posem els noms aquí,
que en lloc de pensar en aquestes cèl · lules

831
00:35:55,330 --> 00:36:00,270
no com a propis cadenes, però com
punters a, per exemple, Alice.

832
00:36:00,270 --> 00:36:03,660
I després Alice pot tenir un altre punter
a un altre nom que comenci amb

833
00:36:03,660 --> 00:36:06,150
A. I Bob realitat va per aquí.

834
00:36:06,150 --> 00:36:10,850
>> I si hi ha un altre nom que comença
amb B, acaba aquí.

835
00:36:10,850 --> 00:36:15,070
I així cada un dels elements d'aquest
taula dos, si hem dissenyat aquest 1

836
00:36:15,070 --> 00:36:17,350
poc més intel · ligentment -

837
00:36:17,350 --> 00:36:18,125
anem -

838
00:36:18,125 --> 00:36:22,950
si hem dissenyat aquest una mica més
intel · ligentment, ara es converteix en un conjunt de dades d'adaptació

839
00:36:22,950 --> 00:36:27,720
estructura, on no hi ha límit físic
de la quantitat d'elements que es poden inserir

840
00:36:27,720 --> 00:36:30,700
en ella, perquè si vostè té
una col · lisió, això està bé.

841
00:36:30,700 --> 00:36:34,690
Només has d'anar endavant i afegir-lo al
el que vam veure fa poc era

842
00:36:34,690 --> 00:36:38,290
coneguda com una llista enllaçada.

843
00:36:38,290 --> 00:36:39,690
>> Bé, fem una pausa per un moment.

844
00:36:39,690 --> 00:36:42,570
Quina és la probabilitat d'una col · lisió
en el primer lloc?

845
00:36:42,570 --> 00:36:45,480
Bé, potser estic més pensant, potser
Jo sóc més de l'enginyeria d'aquest problema,

846
00:36:45,480 --> 00:36:46,370
perquè saps què?

847
00:36:46,370 --> 00:36:49,070
Sí, puc arribar a arbitrària
exemples de la part superior del meu cap, com

848
00:36:49,070 --> 00:36:52,870
Allison i Aaron, però en realitat,
donada una distribució uniforme dels

849
00:36:52,870 --> 00:36:56,990
entrades, és a dir algunes insercions aleatòries
en una estructura de dades, el que realment és

850
00:36:56,990 --> 00:36:58,580
la probabilitat d'una col · lisió?

851
00:36:58,580 --> 00:37:01,670
Doncs resulta que, en realitat és
molt alta.

852
00:37:01,670 --> 00:37:03,850
Permetin-me generalitzar aquest
problema és com aquest.

853
00:37:03,850 --> 00:37:08,890
>> Així que en una habitació de n CS50 estudiants, el que és
la probabilitat que almenys

854
00:37:08,890 --> 00:37:11,010
dos estudiants de l'habitació
tenir la mateixa data de naixement?

855
00:37:11,010 --> 00:37:13,346
Així que no ho. uns pocs Hund -

856
00:37:13,346 --> 00:37:16,790
200, 300 persones aquí i diversos
centenars de persones al país avui en dia.

857
00:37:16,790 --> 00:37:20,670
Així que si volia que preguntar-nos què és
la probabilitat que dues persones

858
00:37:20,670 --> 00:37:23,930
en aquesta sala que té el mateix aniversari,
podem resoldre això.

859
00:37:23,930 --> 00:37:26,250
I jo pretenc en realitat hi ha dos
les persones amb el mateix aniversari.

860
00:37:26,250 --> 00:37:29,560
>> Per exemple, algú
té aniversari avui?

861
00:37:29,560 --> 00:37:31,340
Ahir?

862
00:37:31,340 --> 00:37:32,590
Demà?

863
00:37:32,590 --> 00:37:35,980
Molt bé, així que se sent com que vaig
a haver de fer això 363 o així més

864
00:37:35,980 --> 00:37:39,500
vegades per esbrinar realment a terme
Si tenim una col · lisió.

865
00:37:39,500 --> 00:37:42,350
O podríem fer això matemàticament
en lloc de tediosament

866
00:37:42,350 --> 00:37:43,200
fent això.

867
00:37:43,200 --> 00:37:44,500
I proposar la següent.

868
00:37:44,500 --> 00:37:48,740
>> Així que proposo que podríem modelar el
probabilitat que dues persones tinguin el

869
00:37:48,740 --> 00:37:55,320
mateix dia que la probabilitat d'1
menys la probabilitat de no tenir-ne un

870
00:37:55,320 --> 00:37:56,290
el mateix aniversari.

871
00:37:56,290 --> 00:37:59,960
Així que per aconseguir això, i això és només el
forma elegant d'escriure això, per a la

872
00:37:59,960 --> 00:38:03,090
primera persona a l'habitació, ell o ella
pot tenir qualsevol de la possible

873
00:38:03,090 --> 00:38:07,370
aniversari suposant 365 dies de l'any,
amb perdó de les persones amb

874
00:38:07,370 --> 00:38:08,760
l'aniversari nombre 29 de febrer.

875
00:38:08,760 --> 00:38:13,470
>> Així que la primera persona en aquesta sala és gratis
per tenir qualsevol nombre d'aniversari

876
00:38:13,470 --> 00:38:18,280
de les 365 possibilitats perquè
farem que 365 dividit per 365,

877
00:38:18,280 --> 00:38:18,990
que és un.

878
00:38:18,990 --> 00:38:22,700
La següent persona a l'habitació, si l'objectiu
és evitar una col · lisió, només pot

879
00:38:22,700 --> 00:38:26,460
tenir el seu aniversari en forma
molts dies diferents possibles?

880
00:38:26,460 --> 00:38:27,610
364.

881
00:38:27,610 --> 00:38:31,430
Així que el segon terme d'aquesta expressió és
essencialment és fer que les matemàtiques per a nosaltres

882
00:38:31,430 --> 00:38:33,460
restant Configuració d'un dia possible.

883
00:38:33,460 --> 00:38:36,390
I a continuació, el dia següent, el dia següent, la
dia següent fins al nombre total

884
00:38:36,390 --> 00:38:38,100
de persones a l'habitació.

885
00:38:38,100 --> 00:38:41,290
>> I si considerem a continuació, què és, llavors,
la probabilitat que no totes les persones tinguin

886
00:38:41,290 --> 00:38:45,265
aniversari únics, però de nou 1 menys
que, el que tenim és una expressió

887
00:38:45,265 --> 00:38:47,810
que pot molt capritxosament
aquest aspecte.

888
00:38:47,810 --> 00:38:50,330
Però és més interessant
a veure visualment.

889
00:38:50,330 --> 00:38:55,120
Aquest és un gràfic on en l'eix x és
el nombre de persones a l'habitació, el

890
00:38:55,120 --> 00:38:56,180
nombre d'aniversari.

891
00:38:56,180 --> 00:38:59,840
A l'eix i és la probabilitat
d'una col · lisió, dues persones

892
00:38:59,840 --> 00:39:01,230
que té el mateix aniversari.

893
00:39:01,230 --> 00:39:05,020
>> I el menjar per emportar d'aquesta corba és
que tan aviat com s'arriba a rebre 40

894
00:39:05,020 --> 00:39:11,110
estudiants, que estan fent a una probabilitat del 90%
combinatorically de dos

895
00:39:11,110 --> 00:39:13,550
persones o més tenen
el mateix aniversari.

896
00:39:13,550 --> 00:39:18,600
I una vegada que arribi a agradar 58 persones és
gairebé el 100% d'una ocasió els dos

897
00:39:18,600 --> 00:39:21,310
persones a la sala van a tenir la
mateix dia, tot i que no hi ha

898
00:39:21,310 --> 00:39:26,650
365 o 366 possibles cubs i
només 58 persones a la sala.

899
00:39:26,650 --> 00:39:29,900
Només estadísticament és molt probable que
aconseguir col · lisions, que en definitiva

900
00:39:29,900 --> 00:39:31,810
motiva aquesta discussió.

901
00:39:31,810 --> 00:39:35,890
Que fins i tot si aconseguim extravagàncies, i
començar a tenir aquestes cadenes, seguim sent

902
00:39:35,890 --> 00:39:36,950
tindrà col · lisions.

903
00:39:36,950 --> 00:39:42,710
>> Així que planteja la pregunta, quin és el
cost de fer insercions i delecions

904
00:39:42,710 --> 00:39:44,850
en una estructura de dades com aquest?

905
00:39:44,850 --> 00:39:46,630
Bé, permetin-me proposar -

906
00:39:46,630 --> 00:39:51,570
i m'ho dius a mi tornar a la pantalla durant
aquí - si tenim n elements en el

907
00:39:51,570 --> 00:39:56,330
llista, pel que si estem tractant d'inserir
n elements, i tenim

908
00:39:56,330 --> 00:39:58,050
quants cubs total de?

909
00:39:58,050 --> 00:40:03,450
Diguem que 31 cubs en total
en el cas dels aniversaris.

910
00:40:03,450 --> 00:40:09,240
Quina és la longitud màxima d'un
potencialment d'aquestes cadenes?

911
00:40:09,240 --> 00:40:12,670
>> Si de nou no hi ha 31 possibles
aniversari en un mes determinat.

912
00:40:12,670 --> 00:40:14,580
I només estem aglutinació tots -

913
00:40:14,580 --> 00:40:15,580
En realitat això és un exemple ximple.

914
00:40:15,580 --> 00:40:16,960
Farem 26 al seu lloc.

915
00:40:16,960 --> 00:40:20,890
Així que si realment tenen les persones els noms
començar amb l'A a la Z, el que dóna

916
00:40:20,890 --> 00:40:22,780
som 26 possibilitats.

917
00:40:22,780 --> 00:40:25,920
I estem utilitzant una estructura de dades com
el que acabem de veure, pel que tenim

918
00:40:25,920 --> 00:40:30,210
una matriu de punters, cadascun dels quals
apunta a una llista enllaçada que l'

919
00:40:30,210 --> 00:40:32,360
primera llista és de tots
amb el nom d'Alice.

920
00:40:32,360 --> 00:40:35,770
La segona llista és tota la
nom que comencin amb A, a partir

921
00:40:35,770 --> 00:40:36,980
amb B, i així successivament.

922
00:40:36,980 --> 00:40:41,020
>> Quina és la durada probable de cadascuna de
aquestes llistes si assumim un bonic i net

923
00:40:41,020 --> 00:40:45,410
distribució dels noms de l'A a la Z
a través de l'estructura de dades de conjunt?

924
00:40:45,410 --> 00:40:50,210
No hi ha n persones en l'estructura de dades
dividit per 26, si estan ben

925
00:40:50,210 --> 00:40:52,110
distribuïts a la totalitat
estructura de dades.

926
00:40:52,110 --> 00:40:54,970
Per tant la longitud de cada un d'aquests
cadenes és n dividit per 26.

927
00:40:54,970 --> 00:40:57,380
Però en notació O gran, què és això?

928
00:40:57,380 --> 00:41:00,100

929
00:41:00,100 --> 00:41:02,440
Què és això en realitat?

930
00:41:02,440 --> 00:41:04,150
Així que no deixa de ser n, oi?

931
00:41:04,150 --> 00:41:06,620
Com hem dit en el passat,
uf que es divideix per 26.

932
00:41:06,620 --> 00:41:08,710
Sí, en realitat és més ràpid.

933
00:41:08,710 --> 00:41:12,720
No obstant això, en teoria, no és fonamentalment
tot el que més ràpid.

934
00:41:12,720 --> 00:41:16,040
>> Així que no sembla que tot el que molt
més a prop d'aquest sant grial.

935
00:41:16,040 --> 00:41:17,750
De fet, això és només el temps lineal.

936
00:41:17,750 --> 00:41:20,790
Heck, en aquest punt, per què no fem nosaltres
només ha d'utilitzar una gran llista enllaçada?

937
00:41:20,790 --> 00:41:23,510
Per què no només ha d'utilitzar una gran
matriu per emmagatzemar els noms dels

938
00:41:23,510 --> 00:41:25,010
tots a la sala?

939
00:41:25,010 --> 00:41:28,280
Bé, hi ha encara alguna cosa
convincent sobre una taula hash?

940
00:41:28,280 --> 00:41:30,810
Hi ha encara alguna cosa convincent
sobre una estructura de dades

941
00:41:30,810 --> 00:41:33,940
que s'assembla a això?

942
00:41:33,940 --> 00:41:35,182
Est.

943
00:41:35,182 --> 00:41:37,050
>> ESTUDIANT: [inaudible].

944
00:41:37,050 --> 00:41:39,840
>> ALTAVEU 1: Sí, una vegada i una altra si és només
un algorisme de temps lineal, i un

945
00:41:39,840 --> 00:41:42,780
estructura de dades de temps lineal, per què no ho faig jo
simplement emmagatzemar el nom de tots en una gran

946
00:41:42,780 --> 00:41:44,210
matriu o en una llista enllaçada gran?

947
00:41:44,210 --> 00:41:47,010
I deixar de fer CS molt més difícil
del que ha de ser?

948
00:41:47,010 --> 00:41:49,600

949
00:41:49,600 --> 00:41:53,190
Què és convincent sobre això, fins i tot
encara que em rasqui la treu?

950
00:41:53,190 --> 00:41:54,930
>> ESTUDIANT: [inaudible].

951
00:41:54,930 --> 00:41:57,040
>> ALTAVEU 1: Insercions no ho són?

952
00:41:57,040 --> 00:41:58,140
Car ja.

953
00:41:58,140 --> 00:42:03,390
Així insercions potencialment podria encara
ser constant de temps, fins i tot si les dades

954
00:42:03,390 --> 00:42:07,910
estructura són aquestes, una sèrie de
indicadors, cadascun dels quals està apuntant a

955
00:42:07,910 --> 00:42:09,550
potencialment una llista enllaçada.

956
00:42:09,550 --> 00:42:15,220
Com pots aconseguir constant
temps d'inserció dels noms?

957
00:42:15,220 --> 00:42:16,280
S'adhereixen a la part davantera, la dreta?

958
00:42:16,280 --> 00:42:19,290
>> Si sacrifiquem un objectiu de disseny de
abans, on ens volíem mantenir

959
00:42:19,290 --> 00:42:22,650
el nom de tots, per exemple, classificar,
o la totalitat dels nombres en l'escenari ordenats,

960
00:42:22,650 --> 00:42:25,020
Suposem que tenim un
llista enllaçada sense classificar.

961
00:42:25,020 --> 00:42:29,960
Només ens costa un o dos passos,
com en el cas de Ben i Brian

962
00:42:29,960 --> 00:42:32,750
abans, per inserir un element en
el principi de la llista.

963
00:42:32,750 --> 00:42:36,090
Així que si no ens preocupem de la classificació totes
dels noms que comencin amb A o la totalitat

964
00:42:36,090 --> 00:42:39,660
els noms que comencen amb B, que encara pot
aconseguir la inserció de temps constant.

965
00:42:39,660 --> 00:42:43,900
Ara, mirant a Alice o Bob o qualsevol nom
més en general segueix sent què?

966
00:42:43,900 --> 00:42:48,100
És gran O de n dividit per 26, al
cas ideal, on tothom té un aspecte uniformement

967
00:42:48,100 --> 00:42:51,190
distribuïda, on hi ha el major número d'A
ja que hi ha Z, que és probablement

968
00:42:51,190 --> 00:42:52,220
poc realista.

969
00:42:52,220 --> 00:42:53,880
Però això segueix sent lineal.

970
00:42:53,880 --> 00:42:57,120
>> Però aquí tornem al punt
de la notació asimptòtica ser

971
00:42:57,120 --> 00:42:58,600
teòricament cert.

972
00:42:58,600 --> 00:43:02,960
Però en el món real, si afirmo que
el meu programa pot fer alguna cosa 26 vegades

973
00:43:02,960 --> 00:43:06,210
més ràpid que el teu, el programa
vas a preferir l'ús de?

974
00:43:06,210 --> 00:43:09,660
Teva o la meva, que
és 26 vegades més ràpid?

975
00:43:09,660 --> 00:43:14,320
Sent realistes, la persona que és 26
vegades més ràpid, fins i tot si teòricament

976
00:43:14,320 --> 00:43:18,790
nostres algoritmes s'executen en el mateix
execució asimptòtica temps.

977
00:43:18,790 --> 00:43:20,940
>> Permetin-me proposar a una altra persona
solució en conjunt.

978
00:43:20,940 --> 00:43:24,380
I si això no bufi la seva ment,
estem fora de les estructures de dades.

979
00:43:24,380 --> 00:43:27,420
Així que això és un trienni -

980
00:43:27,420 --> 00:43:28,520
classe de nom estúpid.

981
00:43:28,520 --> 00:43:32,880
Ve de recuperacions, i la paraula
s'escriu trie, t-r-i-i, a causa d'

982
00:43:32,880 --> 00:43:34,450
recuperació de golf sona com triennis.

983
00:43:34,450 --> 00:43:36,580
Però aquesta és la història
de la paraula trie.

984
00:43:36,580 --> 00:43:40,980
>> Així que un trienni és de fet una espècie d'arbre,
i també és un joc de la paraula.

985
00:43:40,980 --> 00:43:46,330
I encara que vostè no pot veure-ho del tot
amb aquesta visualització, 1 trie és un

986
00:43:46,330 --> 00:43:50,790
arbre estructurat, com un arbre de la família amb
un avantpassat a la part superior i un munt

987
00:43:50,790 --> 00:43:54,530
dels néts i besnéts
com les fulles al fons.

988
00:43:54,530 --> 00:43:58,100
Però cada node en un trienni és una matriu.

989
00:43:58,100 --> 00:44:00,680
I està en una matriu - i anem a
simplificar en excés per un moment - és una

990
00:44:00,680 --> 00:44:04,600
matriu, en aquest cas, de mida 26, on
cada node de nou és una matriu de mida

991
00:44:04,600 --> 00:44:09,000
26, on l'element d'ordre zero en aquest
matriu representa A, i l'últim

992
00:44:09,000 --> 00:44:11,810
element en cada un d'aquests
matriu representa Z.

993
00:44:11,810 --> 00:44:15,520
>> Així que proposo, doncs, que aquestes dades
estructura, coneguda com un trienni, pot ser

994
00:44:15,520 --> 00:44:17,600
utilitzat també per emmagatzemar paraules.

995
00:44:17,600 --> 00:44:21,740
Ens vam veure fa un moment com podríem emmagatzemar
És a dir, o en aquest cas els noms, i

996
00:44:21,740 --> 00:44:25,440
Vam veure anteriorment com podem emmagatzemar números,
però si ens centrem en els noms o cadenes

997
00:44:25,440 --> 00:44:27,460
aquí, fixa't el que és interessant.

998
00:44:27,460 --> 00:44:32,210
Jo sostinc que el nom és Maxwell
a l'interior d'aquesta estructura de dades.

999
00:44:32,210 --> 00:44:33,730
On veu vostè Maxwell?

1000
00:44:33,730 --> 00:44:35,140
>> ESTUDIANT: [inaudible].

1001
00:44:35,140 --> 00:44:36,240
>> ALTAVEU 1: A l'esquerra.

1002
00:44:36,240 --> 00:44:39,910
Així que el que és interessant amb aquestes dades
estructura és en lloc d'emmagatzemar la

1003
00:44:39,910 --> 00:44:46,200
cadena M-A-X-W-E-L-L barra invertida zero, tot
contigua, el que en lloc de fer

1004
00:44:46,200 --> 00:44:46,890
està seguint.

1005
00:44:46,890 --> 00:44:50,510
Si aquest és un trie com a estructura de dades,
cada un dels nodes és de nou una matriu,

1006
00:44:50,510 --> 00:44:54,650
i desitja emmagatzemar Maxwell, primer
índex i així node de l'arrel, de manera que

1007
00:44:54,650 --> 00:44:57,810
dir-ho, el primer node,
en la posició M, la dreta, per la

1008
00:44:57,810 --> 00:44:59,160
més o menys en el centre.

1009
00:44:59,160 --> 00:45:03,740
I a partir d'aquí, se segueix una
punter a un nen nodes, per dir-ho.

1010
00:45:03,740 --> 00:45:06,150
Així doncs, en el sentit d'arbre,
vostè segueix cap avall.

1011
00:45:06,150 --> 00:45:09,030
I que et porten a un altre node
A l'esquerra, que és

1012
00:45:09,030 --> 00:45:10,540
només un altre array.

1013
00:45:10,540 --> 00:45:14,710
>> I després, si voleu emmagatzemar Maxwell,
vostè troba el punter que representa

1014
00:45:14,710 --> 00:45:16,430
A, que és aquest d'aquí.

1015
00:45:16,430 --> 00:45:17,840
Després d'anar al següent node.

1016
00:45:17,840 --> 00:45:20,100
I noti - aquesta és la raó de la foto
una mica enganyós -

1017
00:45:20,100 --> 00:45:21,990
aquest node mirada súper petit.

1018
00:45:21,990 --> 00:45:26,050
Però a la dreta d'aquest és Y i Z.
És que l'autor ha truncat la

1019
00:45:26,050 --> 00:45:27,630
foto, així que en realitat
veure les coses.

1020
00:45:27,630 --> 00:45:30,400
En cas contrari aquesta imatge
seria enormement àmplia.

1021
00:45:30,400 --> 00:45:36,180
Així que ara vostè índex en lloc X, llavors
W, A continuació, E, L i després, a continuació, L. Llavors, què

1022
00:45:36,180 --> 00:45:37,380
aquesta curiositat?

1023
00:45:37,380 --> 00:45:41,250
>> Bé, si farem servir aquest tipus de nou
assumir la forma d'emmagatzemar una cadena en un

1024
00:45:41,250 --> 00:45:44,500
estructura de dades, vostè encara ha de
essencialment marcar en les dades

1025
00:45:44,500 --> 00:45:47,250
estructura que una paraula acaba aquí.

1026
00:45:47,250 --> 00:45:50,830
En altres paraules, cada un d'aquests nodes
d'alguna manera ha de recordar que

1027
00:45:50,830 --> 00:45:53,500
realment seguit tots aquests punters
i estan deixant una mica

1028
00:45:53,500 --> 00:45:58,370
molla de pa a la part inferior d'aquest aquí
estructura per indicar M-A-X-W-E-L-L és

1029
00:45:58,370 --> 00:46:00,230
de fet, en aquesta estructura de dades.

1030
00:46:00,230 --> 00:46:02,040
>> Així que podríem fer-ho de la següent manera.

1031
00:46:02,040 --> 00:46:06,810
Cadascun dels nodes de la imatge que acaba de
serra té un, una matriu de mida 27.

1032
00:46:06,810 --> 00:46:10,550
I és ara de 27 anys, ja que en conjunt P 6,
farem realitat li donem un apòstrof,

1033
00:46:10,550 --> 00:46:13,590
perquè puguem tenir noms com O'Reilly
i altres amb apòstrofs.

1034
00:46:13,590 --> 00:46:14,820
Però mateixa idea.

1035
00:46:14,820 --> 00:46:17,710
Cadascun d'aquests elements en el
array apunta a una struct

1036
00:46:17,710 --> 00:46:19,320
node, de manera que només un node.

1037
00:46:19,320 --> 00:46:21,430
Així que això és molt reminiscent
de la nostra llista enllaçada.

1038
00:46:21,430 --> 00:46:24,550
>> I després tinc un booleà, que ho faré
truqui paraula, que només serà

1039
00:46:24,550 --> 00:46:29,120
cert si una paraula acaba en aquest
node a l'arbre.

1040
00:46:29,120 --> 00:46:32,870
Es representa efectivament la petita
triangle que vam veure fa un moment.

1041
00:46:32,870 --> 00:46:37,190
Així que si una paraula acaba en aquest node al
arbre, aquest camp paraula serà veritat,

1042
00:46:37,190 --> 00:46:41,990
que és conceptualment marcant o
estem dibuixant aquest triangle, sí que hi ha

1043
00:46:41,990 --> 00:46:44,080
és una paraula aquí.

1044
00:46:44,080 --> 00:46:45,120
>> Així que aquest és un trienni.

1045
00:46:45,120 --> 00:46:48,540
I ara la pregunta és, què
és el seu temps d'execució?

1046
00:46:48,540 --> 00:46:49,930
És gran O de n?

1047
00:46:49,930 --> 00:46:51,410
És alguna cosa més?

1048
00:46:51,410 --> 00:46:57,330
Bé, si vostè té n els noms d'aquestes dades
estructura, Maxwell és només un

1049
00:46:57,330 --> 00:47:02,330
ells, el que és el temps d'execució de
la inserció o la recerca de Maxwell?

1050
00:47:02,330 --> 00:47:06,230

1051
00:47:06,230 --> 00:47:09,050
Quin és el temps d'execució
de la inserció de Maxwell?

1052
00:47:09,050 --> 00:47:11,740
Si hi ha n altres noms
ja a taula?

1053
00:47:11,740 --> 00:47:12,507
Sí?

1054
00:47:12,507 --> 00:47:15,429
>> ESTUDIANT: [inaudible].

1055
00:47:15,429 --> 00:47:17,550
>> ALTAVEU 1: Sí, és la longitud
del nom, oi?

1056
00:47:17,550 --> 00:47:24,420
Així que M-a-x-w-e-l-l així que se sent com això
algorisme és O gran de set.

1057
00:47:24,420 --> 00:47:26,580
Bé, és clar, el nom
variarà en longitud.

1058
00:47:26,580 --> 00:47:27,380
Potser és un nom curt.

1059
00:47:27,380 --> 00:47:28,600
Potser és un nom més llarg.

1060
00:47:28,600 --> 00:47:33,390
Però el que és clau aquí és que
és un nombre constant.

1061
00:47:33,390 --> 00:47:36,810
I potser en realitat no és constant,
però déu, si essent realistes, en un

1062
00:47:36,810 --> 00:47:41,570
diccionari, és probable que hi hagi algun límit
sobre el nombre de lletres en una

1063
00:47:41,570 --> 00:47:43,820
nom de la persona en un país en particular.

1064
00:47:43,820 --> 00:47:46,940
>> I pel que podem assumir que
és un valor constant.

1065
00:47:46,940 --> 00:47:47,750
No sé el que és.

1066
00:47:47,750 --> 00:47:50,440
És probable que sigui més gran que
creiem que és.

1067
00:47:50,440 --> 00:47:52,720
Perquè sempre hi ha un racó
cas amb un nom llarg boja.

1068
00:47:52,720 --> 00:47:56,360
Així que anem a cridar k, però segueix sent un
constant presumiblement, perquè cada

1069
00:47:56,360 --> 00:48:00,190
nom en el món, almenys en una
país en particular, és que la longitud o

1070
00:48:00,190 --> 00:48:01,780
més curt, pel que és constant.

1071
00:48:01,780 --> 00:48:04,490
Però quan hem dit alguna cosa és gran
O d'un valor constant, què és això

1072
00:48:04,490 --> 00:48:07,760
realment equivalent a?

1073
00:48:07,760 --> 00:48:10,420
Aquesta és realment la mateixa cosa
dient que la constant de temps.

1074
00:48:10,420 --> 00:48:11,530
>> Ara estem una mica trampa, no?

1075
00:48:11,530 --> 00:48:15,340
Estem una mica aprofitant alguna teoria
aquí per dir que així, l'ordre de k és

1076
00:48:15,340 --> 00:48:17,450
realment només demanar un,
i és la constant de temps.

1077
00:48:17,450 --> 00:48:18,200
Però el que realment és.

1078
00:48:18,200 --> 00:48:22,550
A causa de que la idea clau aquí és que
si tenim n noms ja en aquest

1079
00:48:22,550 --> 00:48:26,010
estructura de dades, i d'inserció Maxwell,
és la quantitat de temps que ens porti a

1080
00:48:26,010 --> 00:48:29,530
inseriu Maxwell a tots els afectats
la quantitat de gent una altra

1081
00:48:29,530 --> 00:48:31,100
es troben en l'estructura de dades?

1082
00:48:31,100 --> 00:48:31,670
No sembla ser.

1083
00:48:31,670 --> 00:48:36,280
Si tingués mil milions d'més elements a aquesta
trie, i després inserir Maxwell, es

1084
00:48:36,280 --> 00:48:38,650
es veu afectat en absolut?

1085
00:48:38,650 --> 00:48:39,050
No

1086
00:48:39,050 --> 00:48:42,950
I això és a diferència de qualsevol de les dades del dia
estructures que hem vist fins ara, on

1087
00:48:42,950 --> 00:48:46,820
el temps d'execució de l'algorisme és
completament independent de la quantitat de

1088
00:48:46,820 --> 00:48:51,430
material és o no és ja
en aquesta estructura de dades.

1089
00:48:51,430 --> 00:48:54,650
>> I així, amb aquesta li produeix ara és una
oportunitat per p conjunt de sis, que

1090
00:48:54,650 --> 00:48:58,310
nou implica la implementació de la seva pròpia
corrector ortogràfic, la lectura en 150.000

1091
00:48:58,310 --> 00:49:01,050
És a dir, la millor manera d'emmagatzemar aquesta
no és necessàriament evident.

1092
00:49:01,050 --> 00:49:04,030
I encara que he aspirat a trobar
el sant grial, jo no

1093
00:49:04,030 --> 00:49:05,330
afirmen que un trienni és.

1094
00:49:05,330 --> 00:49:09,810
De fet, una taula hash pot molt bé
arribar a ser molt més eficient.

1095
00:49:09,810 --> 00:49:10,830
Però aquests són només -

1096
00:49:10,830 --> 00:49:14,620
això és només una de les decisions de disseny
vostè haurà de fer.

1097
00:49:14,620 --> 00:49:18,920
>> Però en acabar anem a prendre 50 o més
segons per fer una ullada al que està

1098
00:49:18,920 --> 00:49:22,190
amb antelació la propera setmana i més enllà que la transició
a partir d'aquesta línia d'ordres

1099
00:49:22,190 --> 00:49:26,220
món si els programes en C per coses web
base i llenguatges com PHP i

1100
00:49:26,220 --> 00:49:30,350
JavaScript i la pròpia Internet,
protocols com HTTP, que vostè ha

1101
00:49:30,350 --> 00:49:32,870
es dóna per fet des de fa anys
ara, i el més teclejat tots els

1102
00:49:32,870 --> 00:49:34,440
dia, potser, o vist.

1103
00:49:34,440 --> 00:49:37,420
I anem a començar a pelar la
capes del que és l'internet.

1104
00:49:37,420 --> 00:49:40,650
¿I quin és el codi que
subjacent a les eines actuals.

1105
00:49:40,650 --> 00:49:43,230
Així que 50 segons d'aquest teaser aquí.

1106
00:49:43,230 --> 00:49:46,570
Et dono Guerrers de la xarxa.

1107
00:49:46,570 --> 00:49:51,370
>> [REPRODUIR VIDEO]

1108
00:49:51,370 --> 00:49:56,764
>> -Ell va venir amb un missatge.

1109
00:49:56,764 --> 00:50:00,687
Amb un protocol de tots els seus.

1110
00:50:00,687 --> 00:50:13,370

1111
00:50:13,370 --> 00:50:19,780
Va arribar a un món de tallafocs cruels,
routers indiferents i perills lluny

1112
00:50:19,780 --> 00:50:22,600
pitjor que la mort.

1113
00:50:22,600 --> 00:50:23,590
És ràpid.

1114
00:50:23,590 --> 00:50:25,300
És fort.

1115
00:50:25,300 --> 00:50:27,700
És TCPIP.

1116
00:50:27,700 --> 00:50:30,420
I té la seva direcció.

1117
00:50:30,420 --> 00:50:32,920

1118
00:50:32,920 --> 00:50:34,590
Guerrers de la xarxa.

1119
00:50:34,590 --> 00:50:35,290
>> [FI REPRODUCCIÓ DE VÍDEO]

1120
00:50:35,290 --> 00:50:38,070
>> ALTAVEU 1: Així és com l'internet
es treballarà a partir de la setmana que ve.

1121
00:50:38,070 --> 00:50:40,406