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

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

3
00:00:12,250 --> 00:00:13,860
Bonvenon al CS50.

4
00:00:13,860 --> 00:00:16,190
Ĉi tiu estas la komenco de semajno 8.

5
00:00:16,190 --> 00:00:21,320
Kaj memoru ke problemo aro 5 finiĝis
kun iom da defio.

6
00:00:21,320 --> 00:00:25,210
Do supozante ke vi reakiris ĉiujn viajn
instruado Membroj kaj CA La fotojn

7
00:00:25,210 --> 00:00:30,480
en la card.raw dosiero, vi rajtas
nun trovos ĉiujn el tiuj homoj, kaj

8
00:00:30,480 --> 00:00:34,510
unu bonŝanca venkinto irados domo kun unu
pri tiuj aferoj, la salton movado

9
00:00:34,510 --> 00:00:37,450
aparato kiu vi povas uzi por fina
projektoj, ekzemple.

10
00:00:37,450 --> 00:00:39,860
>> Ĉi tio, ĉiu jaro, kondukas al
iom de creepiness.

11
00:00:39,860 --> 00:00:43,480
Kaj do kion mi pensis mi ŝatus fari estas kotizo
kun vi iujn el la notoj, kiuj havas

12
00:00:43,480 --> 00:00:47,370
iris tien kaj reen super
la bastonon listo de malfrue.

13
00:00:47,370 --> 00:00:51,110
Ekzemple, nur hieraŭ nokte, citaĵo
unquote, de unu el la dungitaro

14
00:00:51,110 --> 00:00:55,000
membroj, "mi ĵus havis studento frapo
sur mia pordo preni foton kun mi.

15
00:00:55,000 --> 00:00:59,020
Stalkers, mi diros al vi. "Partio
sufiĉe priskriba kaj poste ni translokiĝis

16
00:00:59,020 --> 00:01:02,830
al, eble horo poste, "mi havis
studento atendis min post sekcio

17
00:01:02,830 --> 00:01:06,080
kaj li havis ĉiujn niajn nomojn kaj fotoj
sur iu paperfoliojn. "Bone.

18
00:01:06,080 --> 00:01:09,230
Do organizitaj, sed ne
cxio, kion anime ankoraŭ.

19
00:01:09,230 --> 00:01:12,520
>> Do, "Mi estis for de la urbo ĉi tiun semajnfinon,
kaj kiam mi reiris, estis unu en

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

21
00:01:12,630 --> 00:01:16,740
dormoĉambro. "[ridado]

22
00:01:16,740 --> 00:01:20,410
DAVID Malan: Venonta citaĵo de dungitaro
membro, "studento venis al mia domo

23
00:01:20,410 --> 00:01:25,330
Somerville, je 4 GMT ĉi matene. "Sekva
bastono, "mi alvenis al mia hotelo en Sankta

24
00:01:25,330 --> 00:01:30,016
Francisko kaj studento atendis
min ĉe la premgrupo kun tri DSLRs. "

25
00:01:30,016 --> 00:01:31,510
Tipo de ĉambro.

26
00:01:31,510 --> 00:01:34,980
"Mi ne estas eĉ sur bastono tiu semestro,
sed studento penetris en mian domon

27
00:01:34,980 --> 00:01:40,480
Matene kaj gravurita la tuta afero
kun Google Pokalo. "Kaj poste laste,

28
00:01:40,480 --> 00:01:43,650
"Almenaŭ 12 homoj estis avide
atendante por mi kiam mi eliris el mia

29
00:01:43,650 --> 00:01:44,800
Ŝlimo, kaj tiam mi

30
00:01:44,800 --> 00:01:46,970
vekis. "Bone.

31
00:01:46,970 --> 00:01:57,690
Do inter la fotoj, kiel vi povas
memoras, estas tiu ulo ĉi tie, kiuj vin

32
00:01:57,690 --> 00:02:01,850
sciu, kiel Milo Banano, kiu vivas
kun Lauren Carvalho, nia kapo

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

34
00:02:02,905 --> 00:02:05,170
Milo, Milo, venu tien knabo.

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

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

37
00:02:08,650 --> 00:02:12,230
Mind vi, li estas vestita Google Pokalo, tiel
ni montros al vi cxion cxi tion poste.

38
00:02:12,230 --> 00:02:16,190
Do tiu estas Milo se vi ŝatus
preni foton kun li poste.

39
00:02:16,190 --> 00:02:18,240
Se vi ŝatus elsercxu
en la aŭdantaro.

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

41
00:02:19,430 --> 00:02:20,200
Tio estas bona materialo.

42
00:02:20,200 --> 00:02:22,556
Nu, Milo Banano.

43
00:02:22,556 --> 00:02:23,941
Ho, ne faru tion.

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

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

46
00:02:29,470 --> 00:02:34,550
Do vorto tiam kio kuŝas antaŭen,
ĉar kiel ni komencas transiro,

47
00:02:34,550 --> 00:02:38,410
tiu semajno specife, de C en
komandlinio medio por PHP kaj

48
00:02:38,410 --> 00:02:42,720
Javascript kaj SQL kaj HTML kaj CSS en
retejo bazita medio, ni estos

49
00:02:42,720 --> 00:02:44,490
ekipi vin per cxiuj
pli kono por

50
00:02:44,490 --> 00:02:46,010
potenciala fino projektoj.

51
00:02:46,010 --> 00:02:49,240
Tiucele, la kurso havas
tradicio de tenante seminarioj kiuj

52
00:02:49,240 --> 00:02:50,950
estas sur _tangential_ temoj
al la kurso.

53
00:02:50,950 --> 00:02:54,330
Tre rilataj al programado kaj al
app disvolviĝo kaj tiel plu, sed

54
00:02:54,330 --> 00:02:57,010
ne nepre esploris per
la kurso mem Syllabus.

55
00:02:57,010 --> 00:03:00,250
>> Do, se vi povus interesi en unu
aŭ pli de la ĉijara seminarioj,

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

57
00:03:02,530 --> 00:03:06,170
Estas pli malnovaj seminarioj
ĉe cs50.net/seminars.

58
00:03:06,170 --> 00:03:10,620
Kaj sur la roster tiel multe por ĉi tiu jaro
estas Amazing Retejo Apps kun Ruby on

59
00:03:10,620 --> 00:03:13,580
Rails, kiu estas alternativa
lingvo PHP.

60
00:03:13,580 --> 00:03:14,900
Komputa Lingvistiko.

61
00:03:14,900 --> 00:03:18,710
Enkonduko al IOS, kiu estas la
platformo kiu estas uzata por iPhone kaj

62
00:03:18,710 --> 00:03:19,850
iPad disvolviĝo.

63
00:03:19,850 --> 00:03:22,890
Javascript por Retejo aplikaĵoj, ni kovras
tio, sed en tiu seminario, vi iros

64
00:03:22,890 --> 00:03:24,070
pli detale.

65
00:03:24,070 --> 00:03:27,390
>> Salti Motion, do ni efektive havas iujn
el niaj amikoj el Leap Motion,

66
00:03:27,390 --> 00:03:29,160
la propra kompanio, aliĝi.

67
00:03:29,160 --> 00:03:31,800
Morgaŭ, fakte, havigi
oni batalas en seminarion, se

68
00:03:31,800 --> 00:03:33,320
interesajn por vi.

69
00:03:33,320 --> 00:03:38,770
Meteor.js, alternativa tekniko por
uzante JavaScript ne en foliumilo,

70
00:03:38,770 --> 00:03:39,970
sed sur la servilo.

71
00:03:39,970 --> 00:03:42,110
Node.js, kio estas tre multe
en tiu vejno tiel.

72
00:03:42,110 --> 00:03:43,650
Glata Android Dezajno.

73
00:03:43,650 --> 00:03:46,990
Android esti tre populara alternativo
al IOS kaj Windows Phone

74
00:03:46,990 --> 00:03:48,790
kaj aliaj telefonoj platformoj.

75
00:03:48,790 --> 00:03:51,180
Kaj Retejo Sekureco Aktiva defendo.

76
00:03:51,180 --> 00:03:54,590
>> Do fakte, se vi ŝatus
engaĝiĝi pri tio, lasu min

77
00:03:54,590 --> 00:03:55,840
fari noton pri tio.

78
00:03:55,840 --> 00:03:57,790
Ni estas tre feliĉa por diri ke
niaj amikoj Leap

79
00:03:57,790 --> 00:03:59,140
Moviĝo, kiu estas startup -

80
00:03:59,140 --> 00:04:01,300
tiu aparato vere nur venis
el kelkaj monatoj -

81
00:04:01,300 --> 00:04:05,960
favore donacis 30 tiaj aparatoj
al la klaso por tiom da studentoj, se

82
00:04:05,960 --> 00:04:08,670
Vi ŝatus pruntepreni la aparataro
al semestro fino kaj uzi ĝin por

83
00:04:08,670 --> 00:04:10,390
reala fina projekto.

84
00:04:10,390 --> 00:04:11,890
Ili apogas plurajn lingvojn.

85
00:04:11,890 --> 00:04:16,040
Neniu el ili C, neniu el ili PHP, do
realigi unu aŭ pli el tiuj seminarioj

86
00:04:16,040 --> 00:04:16,899
por elprovi de intereso.

87
00:04:16,899 --> 00:04:19,730
Kaj ĉiuj ili estos filmado en
la okazaĵo ke vi ne povas

88
00:04:19,730 --> 00:04:21,380
ĉeesti persone.

89
00:04:21,380 --> 00:04:25,000
La horaro estos anoncita per
retposxtu kiel ni solidiĝas ĉambroj.

90
00:04:25,000 --> 00:04:28,460
>> Kaj laste, se vi iros al
projects.cs.50.net, ĉi tiu estas afiŝinto

91
00:04:28,460 --> 00:04:31,450
ni subtenas ĉiun jaron ke ni inviti
uloj de la komunumo, fakultato,

92
00:04:31,450 --> 00:04:36,420
fakoj, bastono, ambaŭ
en ekster CS50 al

93
00:04:36,420 --> 00:04:37,730
proponi projekton ideoj.

94
00:04:37,730 --> 00:04:39,050
Aĵoj de intereso por studento grupoj.

95
00:04:39,050 --> 00:04:40,600
Aĵoj de intereso al fakoj.

96
00:04:40,600 --> 00:04:43,990
Do turnu tie se vi luktas
kun necerteco, kia vi

97
00:04:43,990 --> 00:04:46,700
mem ŝatus pritrakti.

98
00:04:46,700 --> 00:04:51,760
>> Do lastan fojon ni prezentis nediskuteble
pli kompleksa datumstrukturo ol ni volonte

99
00:04:51,760 --> 00:04:53,300
vidita en semajnoj pasinteco.

100
00:04:53,300 --> 00:04:56,550
Ni volonte estis uzante arrays bela
feliĉe kiel utila se

101
00:04:56,550 --> 00:04:58,160
simplista datumstrukturo.

102
00:04:58,160 --> 00:05:00,570
Tiam ni enkondukis tiujn, kiuj
kompreneble estas ligitaj listoj.

103
00:05:00,570 --> 00:05:05,470
Kaj kio estis unu el la motivoj por
enkonduki tiun datumstrukturo?

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

105
00:05:06,930 --> 00:05:07,250
Kio estas tio?

106
00:05:07,250 --> 00:05:08,080
>> Spektantaro: Dinamikaj grandeco.

107
00:05:08,080 --> 00:05:09,040
>> DAVID Malan: Dinamikaj grandeco.

108
00:05:09,040 --> 00:05:11,890
Tiel dum en tabelo, vi devas
koni lian grandecon anticipe kiam

109
00:05:11,890 --> 00:05:12,740
vi destini ĝin.

110
00:05:12,740 --> 00:05:14,380
En ligitaj listo, vi ne
devas scii tion.

111
00:05:14,380 --> 00:05:17,610
Vi povas simple malloc, aŭ pli ĝenerale,
destini plia

112
00:05:17,610 --> 00:05:20,720
nodo, por tiel diri, iam vi
volas enmeti pli da datumoj.

113
00:05:20,720 --> 00:05:22,670
Kaj nodo havas ne antaŭdeterminita signifon.

114
00:05:22,670 --> 00:05:25,580
Estas nur ĝenerala termino priskribanta
ia ujo kiu ni estas

115
00:05:25,580 --> 00:05:29,610
uzante en nia datumstrukturo stoki
iu elemento de intereso, kiu en ĉi tiu

116
00:05:29,610 --> 00:05:31,750
kazo hazarde estas entjeroj.

117
00:05:31,750 --> 00:05:33,160
>> Sed ĉiam oni tradeoff.

118
00:05:33,160 --> 00:05:38,070
Do ni ricevas dinamika grandecoj de la datumoj
strukturo, sed kion prezo ni pagas?

119
00:05:38,070 --> 00:05:40,040
Kio estas la malfacilaĵo de lertaj kunligitaj?

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

121
00:05:41,006 --> 00:05:41,980
>> Spektantaro: postulas pli da memoro.

122
00:05:41,980 --> 00:05:44,240
>> DAVID Malan: ĝi postulas pli
memoro, kiel ĝuste?

123
00:05:44,240 --> 00:05:46,440
>> Spektantaro: [inaudibles].

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

125
00:05:47,050 --> 00:05:50,460
Do nun ni montriloj tenante
plia memoro kiujn ni antaŭe

126
00:05:50,460 --> 00:05:53,040
ne bezonas, ĉar la avantaĝo
de tabelo, kompreneble, estas tio

127
00:05:53,040 --> 00:05:54,860
ĉio estas apudaj, dorso
apogi al malantaŭo, kiun

128
00:05:54,860 --> 00:05:56,380
donas hazardan aliron.

129
00:05:56,380 --> 00:06:00,710
Ĉar nur per rektaj krampo
skribmaniero, aŭ pli teknike puntero

130
00:06:00,710 --> 00:06:03,580
aritmetiko, tre simpla Krome,
vi povas aliri al iu

131
00:06:03,580 --> 00:06:05,700
elementoj en konstanta tempo.

132
00:06:05,700 --> 00:06:08,975
Kaj fakte, tio estas speco de aludas
alia prezo kiun ni pagas per

133
00:06:08,975 --> 00:06:09,760
ligitaj listo.

134
00:06:09,760 --> 00:06:13,890
>> Kio okazas al la rula tempo de
iu kiel Search, se mi volas

135
00:06:13,890 --> 00:06:17,270
trovi iun valoron kaj ene
de kunligita listo?

136
00:06:17,270 --> 00:06:20,290
Kion mia rula tempo fariĝos?

137
00:06:20,290 --> 00:06:21,560
Granda a de n.

138
00:06:21,560 --> 00:06:24,060
Se ĝi estas ordo de?

139
00:06:24,060 --> 00:06:25,440
Kio se la datumstrukturo estas ordo?

140
00:06:25,440 --> 00:06:28,640
Ĉu mi povas fari pli bone ol granda
Aŭ de n por serĉado?

141
00:06:28,640 --> 00:06:31,700
Ne, ĉar en la plej malbona kazo povus
tre bone esti ordo, sed la numero

142
00:06:31,700 --> 00:06:32,950
vi serĉas povus esti granda.

143
00:06:32,950 --> 00:06:35,370
Ĝi povus esti la numeron 100, kiu
povus okazi ke ĉiu

144
00:06:35,370 --> 00:06:36,410
la vojo al la fino.

145
00:06:36,410 --> 00:06:39,950
Kaj ĉar vi nur povas konsenti kunligita
lerta en tiu efektivigo de

146
00:06:39,950 --> 00:06:42,690
maniero de lia unua nodo, vi estas
ankoraŭ ia el sorton.

147
00:06:42,690 --> 00:06:47,450
Vi devas trairi la tutan aferon
de komenco ĝis fino, por trovi

148
00:06:47,450 --> 00:06:49,150
ke granda valoro kiel 100.

149
00:06:49,150 --> 00:06:51,350
Aŭ por determini se estas
eĉ ne ekzistas.

150
00:06:51,350 --> 00:06:55,960
>> Do ni ne povas fari kion algoritmo en datumoj
strukturo kiu aspektas tiel?

151
00:06:55,960 --> 00:06:59,460
Ni ne povas fari duuma serĉo, ĉar
duuma serĉo postulis ke ni havis

152
00:06:59,460 --> 00:07:00,740
hazarda aliron.

153
00:07:00,740 --> 00:07:04,500
Ni povus simple salti el situon
situo sen devi sekvi

154
00:07:04,500 --> 00:07:07,080
tiuj pano panerojn en la formo
de ĉiuj ĉi tiuj indikoj.

155
00:07:07,080 --> 00:07:08,300
>> Nun, kiamaniere ni apliki tio?

156
00:07:08,300 --> 00:07:12,830
Nu, se ni iros al la ekrano tie, se
ni povas rapide reimplement ĉi datumoj

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

158
00:07:13,440 --> 00:07:15,670
mia skribo ne estas ĉiu, kiu
grandan tie, sed ni provos.

159
00:07:15,670 --> 00:07:22,030
Do typedef struct, kaj kion faris mi
volas nomi tion ĉi tien?

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

161
00:07:22,960 --> 00:07:24,580
Do mi devos akiri ni komencis.

162
00:07:24,580 --> 00:07:27,860
Kaj nun, kio devas esti ene de
la datumstrukturo por unuope

163
00:07:27,860 --> 00:07:28,430
ligitaj listo?

164
00:07:28,430 --> 00:07:29,950
Kiom da kampoj?

165
00:07:29,950 --> 00:07:30,450
>> Do du.

166
00:07:30,450 --> 00:07:31,570
Unu estas sufiĉe facila.

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

168
00:07:33,050 --> 00:07:35,930
Kaj ni povus nomi n ion ni volas,
sed devus esti int se ni estas

169
00:07:35,930 --> 00:07:37,660
apliki kunligita listo por ints.

170
00:07:37,660 --> 00:07:41,920
Kaj nun kio faras la dua
kampo devas esti?

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

172
00:07:43,460 --> 00:07:50,570
Do, se mi faras struct nodo *, kaj tiam mi
povas nomi ankaux cxi tio, kion ajn mi volas,

173
00:07:50,570 --> 00:07:53,510
sed nur por esti klara Mi vokos
ĝi venas, kiel ni estis farante.

174
00:07:53,510 --> 00:07:55,270
Kaj poste mi fermas mian krispa krampoj.

175
00:07:55,270 --> 00:08:00,700
>> Kaj nun, kiel lasta fojo,
Mi metis nodo cxi tie.

176
00:08:00,700 --> 00:08:03,830
Sed se mi deklari cxi tiu estas kiel
nodo, kial mi tedas esti tiel

177
00:08:03,830 --> 00:08:07,320
verbose tie en deklari struct
nodo * proksima, kontraste

178
00:08:07,320 --> 00:08:09,210
al nur nodo * poste?

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

180
00:08:09,904 --> 00:08:12,810
>> Spektantaro: [inaudibles].

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

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

183
00:08:14,530 --> 00:08:18,320
Ĉar C vere prenas vin laŭvorte kaj
nur vidas la difino de vertico

184
00:08:18,320 --> 00:08:21,230
vojo cxi tie, vi ne povas
referi al ĝi ĉi tie.

185
00:08:21,230 --> 00:08:24,760
Do ni havas ĉi tiun specon de antaŭataka
deklaro tie, kiu estas Certe

186
00:08:24,760 --> 00:08:25,390
pli abundajn.

187
00:08:25,390 --> 00:08:27,810
Struct nodo, tio signifas
ni povas aliri ĝin

188
00:08:27,810 --> 00:08:29,760
ene de la datumstrukturo.

189
00:08:29,760 --> 00:08:33,370
>> Kaj kiel flanken, ĉar ĉi tiu estas
igante iom pli subjektivan nun,

190
00:08:33,370 --> 00:08:36,230
la stelo povas teknike iri tien,
ĝi povas iri ĉi tie, ĝi povas

191
00:08:36,230 --> 00:08:37,179
eĉ iri en la mezo.

192
00:08:37,179 --> 00:08:39,890
Ni adoptis, en la stilo gvidas por
la kurso, la konvencio de metante

193
00:08:39,890 --> 00:08:42,299
la stelo tuj apud la datumoj
tipo, kiu en ĉi tiu kazo,

194
00:08:42,299 --> 00:08:43,460
Estus struct nodo.

195
00:08:43,460 --> 00:08:46,620
Sed rimarki en multaj lernolibroj kaj
linio referencoj, vi povus ja

196
00:08:46,620 --> 00:08:48,450
vidi ĝin sur la alia flanko.

197
00:08:48,450 --> 00:08:52,200
Sed ĝuste rimarkas ke ambaŭ faros reale
labori kaj vi devas simple esti

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

199
00:08:52,970 --> 00:08:53,580
>> Ĉio bone.

200
00:08:53,580 --> 00:08:55,630
Por ke estis nia deklaro
de struct nodo.

201
00:08:55,630 --> 00:08:59,430
Sed tiam ni komencis fari pli
kompleksaj aĵoj.

202
00:08:59,430 --> 00:09:03,410
Ekzemple, ni decidis enkonduki
iu kiel hash tablo.

203
00:09:03,410 --> 00:09:08,160
Do jen estas hash tablo de amplekso n,
indeksitaj de 0 sur supro lasis al n

204
00:09:08,160 --> 00:09:09,690
minus 1 sur la fundo restis.

205
00:09:09,690 --> 00:09:11,640
Tio povus esti hash
tablo por nenio.

206
00:09:11,640 --> 00:09:15,340
Sed kiajn aferojn ni parolas
pri uzanta hash tablo por?

207
00:09:15,340 --> 00:09:18,370
Stoki kio?

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

209
00:09:18,800 --> 00:09:20,870
Ni povus fari nomojn kiel
ni faris lastan fojon.

210
00:09:20,870 --> 00:09:22,200
Kaj vere, vi povas stoki nenion.

211
00:09:22,200 --> 00:09:24,640
Kaj ni vidos ĉi denove en
PHP kaj en JavaScript.

212
00:09:24,640 --> 00:09:28,550
Al hash tablo estas bela speco de svisa
Poŝtranĉilo kiu permesas stoki

213
00:09:28,550 --> 00:09:33,690
preskaux kion vi volas ene de
ĝin asocii klavojn per valoroj.

214
00:09:33,690 --> 00:09:34,770
Klavoj kun valoroj.

215
00:09:34,770 --> 00:09:37,800
>> Nun en tiu simpla kazo, nia
klavoj estas nur numerojn.

216
00:09:37,800 --> 00:09:40,380
Ni aplikas kradon
tablo kiel tabelo.

217
00:09:40,380 --> 00:09:43,500
Kaj tial la klavoj estas 0,
1, 2, kaj tiel plu.

218
00:09:43,500 --> 00:09:47,200
Kaj tial ni, kiel homoj, ili decidis lastan
semajno ke vi scias kio, se ni estas

219
00:09:47,200 --> 00:09:50,410
tuj vendejo nomoj, ni nur
arbitre, sed sufiĉe prudente,

220
00:09:50,410 --> 00:09:54,680
supozi ke Alico, an A nomo,
estos nur esti indeksita en 0.

221
00:09:54,680 --> 00:09:58,030
Kaj Bob, B nomo, estos indeksita
en 1, kaj tiel plu.

222
00:09:58,030 --> 00:10:02,490
Do ni devis surĵeto inter enigoj,
kiuj estas sanaj, kaj la hash

223
00:10:02,490 --> 00:10:04,560
lokoj, kiuj estas nombroj.

224
00:10:04,560 --> 00:10:07,740
>> Do tiu procezo estas ĝenerale konata kiel
kradon funkcio, kaj vi povas vere

225
00:10:07,740 --> 00:10:09,130
apliki ĝin en kodo.

226
00:10:09,130 --> 00:10:12,080
Se mi volis apliki hash funkcio
kiu faras ĝuste kion ni

227
00:10:12,080 --> 00:10:17,070
jxus priskribita de lasta fojo, mi povus
deklari funkcio kiu prenas, kiel

228
00:10:17,070 --> 00:10:18,330
enigo ekzemple -

229
00:10:18,330 --> 00:10:22,190
kaj ni faru tion en tiu
ekrano super tie.

230
00:10:22,190 --> 00:10:26,180
Se mi volis apliki hash
funkcio, mi povus diri

231
00:10:26,180 --> 00:10:27,410
iu kiel ĉi tio.

232
00:10:27,410 --> 00:10:29,030
>> Ĝi tuj revenos al int.

233
00:10:29,030 --> 00:10:33,600
Ĝi tuj nomos hash, kaj estas
tuj akceptus kiel argumento al

234
00:10:33,600 --> 00:10:38,920
ĉeno, aŭ ni povas esti pli taŭga nun,
kaj diru char *, ni nomas ĝin s.

235
00:10:38,920 --> 00:10:43,840
Kaj tiam ĉiuj ĉi funkcio devas fari,
fine, ĝi revenas al int.

236
00:10:43,840 --> 00:10:45,990
Nun, kiel faras tion povus
ne estus tiel klara.

237
00:10:45,990 --> 00:10:49,510
Mi tuj apliki tion sen ajna
formi de eraro kontrolanta nun.

238
00:10:49,510 --> 00:10:55,740
Mi simple tuj blinde diri, revenu
kio ajn estas je s krampo 0, minus,

239
00:10:55,740 --> 00:10:58,850
diru, ĉefurbo A punktokomo.

240
00:10:58,850 --> 00:10:59,960
>> Plene rompita.

241
00:10:59,960 --> 00:11:02,620
Ĝi ne estas perfekta ĉar
unu, kio se s estas nula?

242
00:11:02,620 --> 00:11:04,000
Malbonaj aferoj okazos.

243
00:11:04,000 --> 00:11:07,940
Du, kio okazos se la unua letero en tiu
nomo ne estas majusklo?

244
00:11:07,940 --> 00:11:09,860
Tio ne tuj turni
el bone ankaŭ ne.

245
00:11:09,860 --> 00:11:11,970
Ĝi povus esti minuskla litero
aŭ ne leteron al ĉiuj.

246
00:11:11,970 --> 00:11:15,520
Do tute spaco por plibonigo tie,
sed ĉi tiu estas la baza ideo.

247
00:11:15,520 --> 00:11:19,010
>> Kion ni priskribis pasintsemajne parole kiel
nur proceso de mapado de Alico al

248
00:11:19,010 --> 00:11:23,360
0 kaj Bob al 1 povas esti esprimita
certe pli formulaically kiel C

249
00:11:23,360 --> 00:11:24,320
funkcii tie.

250
00:11:24,320 --> 00:11:28,630
Vokis denove hash, prenas ĉeno kiel
eniro, kaj poste iel faras ion

251
00:11:28,630 --> 00:11:31,020
kun tiu enigo por produkti eligo.

252
00:11:31,020 --> 00:11:34,130
Ne malkiel nia nigra skatolo priskribo
ke ni longe faris.

253
00:11:34,130 --> 00:11:36,550
Mi ne scias kiel tio povus esti
laborante sub la kapuĉo.

254
00:11:36,550 --> 00:11:40,120
>> Por problemo aro 6, unu el la defioj
estas por vi decidi kion

255
00:11:40,120 --> 00:11:41,920
via krada funkcio estas?

256
00:11:41,920 --> 00:11:45,760
Kio okazas al esti ene de tiu nigra
skatolo, kaj supozeble, ĝi devos esti

257
00:11:45,760 --> 00:11:50,380
iom pli interesa ol tio, kaj
definitive pli inklina al eraro

258
00:11:50,380 --> 00:11:53,180
kontrolanta ol tiu aparta
efektivigo.

259
00:11:53,180 --> 00:11:54,580
>> Sed problemoj povas ekesti, ĉu ne?

260
00:11:54,580 --> 00:11:57,760
Se ni havas datumstrukturo kiel ĉi
unu, kio estas unu el la problemoj

261
00:11:57,760 --> 00:12:01,600
vi povas kolizii kun la tempo kiel vi enŝovu
pli kaj pli nomoj en la

262
00:12:01,600 --> 00:12:02,880
hash tablo?

263
00:12:02,880 --> 00:12:04,630
Vi ricevas kolizioj, ĉu ne?

264
00:12:04,630 --> 00:12:07,560
Kio se vi havas Alico kaj Aaron,
du personoj kies nomoj okazis

265
00:12:07,560 --> 00:12:08,190
komenci kun A?

266
00:12:08,190 --> 00:12:11,660
Tio petegas la demando, kie vi
meti la dua tia A nomo?

267
00:12:11,660 --> 00:12:15,050
>> Nu, eble vi naive simple metu ĝin
kie Bob apartenas, sed tiam Bob estas

268
00:12:15,050 --> 00:12:17,300
speco de ŝraŭbita se vi provas
enŝovu sian nomon sekva kaj

269
00:12:17,300 --> 00:12:18,240
ne estas loko por li.

270
00:12:18,240 --> 00:12:21,400
Tiel vi povus meti Bob kie Charlie,
kaj vi povas imagi tiun tre rapide

271
00:12:21,400 --> 00:12:23,020
devolving en iom de malordo.

272
00:12:23,020 --> 00:12:25,600
Io lineara en la fino, kie vi
Nur oni devas serĉi en la tuta afero

273
00:12:25,600 --> 00:12:28,190
serĉas Alico aŭ Bob
aŭ Aaron aŭ Charlie.

274
00:12:28,190 --> 00:12:33,230
>> Do anstataŭ ni proponis, anstataŭ nur
lineare tuŝoprobado por malferma spacoj

275
00:12:33,230 --> 00:12:36,450
kaj investi la nomoj tie, ni
proponis amatoro alproksimiĝo.

276
00:12:36,450 --> 00:12:41,740
Al hash tablo implementado ankoraŭ kun
tabelo de indeksoj, sed la datumtipon de

277
00:12:41,740 --> 00:12:44,500
tiuj indeksoj nun estis montriloj.

278
00:12:44,500 --> 00:12:47,360
Pointers por kio?

279
00:12:47,360 --> 00:12:48,730
Pointers al lertaj kunligitaj.

280
00:12:48,730 --> 00:12:53,330
>> Pro memoro ke ligitaj listo estas
vere nur puntero al nodo, kaj

281
00:12:53,330 --> 00:12:57,110
la nodo havas sekva kampo, kaj tiu nodo
havas sekva kampo, kaj tiel plu.

282
00:12:57,110 --> 00:13:00,690
Do vi nun povas pensi pri tiu tabelo en
la maldekstra flanko de hash tablo kiel

283
00:13:00,690 --> 00:13:01,820
kondukante al kunligitaj listo.

284
00:13:01,820 --> 00:13:07,000
La avantaĝo de tio estas, se vi ricevas
kolizio inter Alica kaj Aaron,

285
00:13:07,000 --> 00:13:09,300
kion vi faras kun la
dua tia persono?

286
00:13:09,300 --> 00:13:14,150
Vi nur alfiksi lin aŭ ŝin al la
fino, aŭ eĉ la komenco

287
00:13:14,150 --> 00:13:15,490
de tiu ligitaj listo.

288
00:13:15,490 --> 00:13:17,340
>> Kaj efektive, ni nur vermiĉeloj tra
ke por ĝuste dua.

289
00:13:17,340 --> 00:13:18,640
Kie farus la plej senso?

290
00:13:18,640 --> 00:13:22,060
Se mi enŝovu Alice kaj ŝi finiĝos ĉe
la unua loko, tiam mi provos

291
00:13:22,060 --> 00:13:25,310
enigi la nomon de Aaron, kaj tie estas
evidente kolizio, mi devus meti

292
00:13:25,310 --> 00:13:27,400
li komence
de la ligitaj listo?

293
00:13:27,400 --> 00:13:30,944
Tio estas en tiu unua loko,
aŭ ĉe la fino?

294
00:13:30,944 --> 00:13:31,440
>> Spektantaro: [inaudibles].

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

296
00:13:31,990 --> 00:13:32,490
Mi aŭdis komenciĝis.

297
00:13:32,490 --> 00:13:33,903
Kial ĉe la komenco?

298
00:13:33,903 --> 00:13:34,750
>> Spektantaro: [inaudibles].

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

300
00:13:34,940 --> 00:13:36,520
Ĝi estas alfabeta, do tio estas agrabla.

301
00:13:36,520 --> 00:13:37,330
Tio estas bona posedaĵo.

302
00:13:37,330 --> 00:13:39,335
Ĝi helpos al mi iom tempon potenciale.

303
00:13:39,335 --> 00:13:43,290
Ne lasu min fari duuma serĉo, sed mi
povus almenaŭ povos rompi

304
00:13:43,290 --> 00:13:47,340
de ciklo se mi rimarkas, bone, mi estas maniero
estinteco estis Aaronon estus en ĉi tiu

305
00:13:47,340 --> 00:13:48,310
ordo ligillisto.

306
00:13:48,310 --> 00:13:50,360
Mi ne devas malŝpari mian tempon rigardante
tuta vojo al la fino.

307
00:13:50,360 --> 00:13:51,530
Do jen racia.

308
00:13:51,530 --> 00:13:54,710
Kial alia eble vi volas enmeti
la karamboli nomon ĉe la

309
00:13:54,710 --> 00:13:56,660
komencante de la listo?

310
00:13:56,660 --> 00:13:57,397
Kio estas tio?

311
00:13:57,397 --> 00:13:58,680
>> Spektantaro: [inaudibles].

312
00:13:58,680 --> 00:14:00,820
>> DAVID Malan: Ĝi povus fari longan tempon
alveni ĝis la fino de la listo.

313
00:14:00,820 --> 00:14:02,490
Kaj fakte, pli longa kaj pli longa.

314
00:14:02,490 --> 00:14:04,920
La pli nomoj vi enŝovu ke
komencu per A, la longaj, ke

315
00:14:04,920 --> 00:14:06,280
ĉeno tuj akiras.

316
00:14:06,280 --> 00:14:07,890
Ju pli longe ke ligitaj
listo estas tuj alvenos.

317
00:14:07,890 --> 00:14:09,420
Do vi estas vere ĝuste
malŝparas vian tempon.

318
00:14:09,420 --> 00:14:14,070
Eble vi pli bone subteni
konstanta inserción tempo, granda O de 1,

319
00:14:14,070 --> 00:14:18,470
por ĉiam meti la karamboli nomo ĉe
Komence de la ligitaj listo,

320
00:14:18,470 --> 00:14:21,230
kaj ne zorgi tiel
pri ordigado.

321
00:14:21,230 --> 00:14:22,600
>> Kio estas la plej bona respondo?

322
00:14:22,600 --> 00:14:23,320
Ĝi estas klara.

323
00:14:23,320 --> 00:14:26,140
Ĉio dependas de kion la
dissendo estas, kion la ŝablono estas

324
00:14:26,140 --> 00:14:27,850
de la nomoj vi enmeto.

325
00:14:27,850 --> 00:14:29,430
Ĝi ne estas bezone
evidenta respondo.

326
00:14:29,430 --> 00:14:33,100
Sed ĉi tie, denove, estas
dezajnon ŝancon.

327
00:14:33,100 --> 00:14:37,220
>> Do ni tiam rigardis tion, kio
estas vere la aliaj grandaj ŝancon

328
00:14:37,220 --> 00:14:38,180
por p-aro 6.

329
00:14:38,180 --> 00:14:41,770
Kaj realigi, se vi ne jam,
Zamyla mergas en ambaŭ de ĉi tiuj, hash

330
00:14:41,770 --> 00:14:43,260
tabloj kaj klopodoj, en pli detalo.

331
00:14:43,260 --> 00:14:45,630
Kaj la video walkthrough estas
enigita en p-aro spec.

332
00:14:45,630 --> 00:14:46,590
Tio estis trie -

333
00:14:46,590 --> 00:14:51,670
T-R-I-E. Kaj kio estis interesa
tio estis, ke la rula tempo

334
00:14:51,670 --> 00:14:59,510
de serĉado Mia nomo, same kiel Maxwell
lastan fojon, estis granda O de kio?

335
00:14:59,510 --> 00:15:01,040
Kio estas tio?

336
00:15:01,040 --> 00:15:01,920
>> Aŭdienco: La nombro de literoj.

337
00:15:01,920 --> 00:15:02,550
>> DAVID Malan: Nombro da literoj.

338
00:15:02,550 --> 00:15:03,210
Mi aŭdis du aĵojn.

339
00:15:03,210 --> 00:15:04,630
Nombro da leteroj kaj konstanta tempo.

340
00:15:04,630 --> 00:15:05,540
Do ni iru kun tio unue.

341
00:15:05,540 --> 00:15:06,410
La nombro de literoj.

342
00:15:06,410 --> 00:15:10,195
Nu, tiu datumstrukturo, revokon, estas
kiel arbo, familio arbo, ĉiu el

343
00:15:10,195 --> 00:15:12,860
kies verticoj estas formitaj de arrays.

344
00:15:12,860 --> 00:15:16,300
Kaj tiuj matricoj estas indikoj al
aliaj tiaj nodoj, aŭ aliaj tiaj

345
00:15:16,300 --> 00:15:17,670
arrays en la arbo.

346
00:15:17,670 --> 00:15:22,890
>> Do, se ni volis tiam determini
ĉu Maxwell estas en tie, mi povus iri

347
00:15:22,890 --> 00:15:26,890
al la unua tabelo, ĉe la plejsupro de
la arbo, la tn radiko, supro de

348
00:15:26,890 --> 00:15:30,521
la trie, kaj poste sekvi la m pointer,
tiam la puntero, tiam x,

349
00:15:30,521 --> 00:15:31,710
w, e, l, l.

350
00:15:31,710 --> 00:15:34,910
Kaj poste, kiam mi vidas iun specialan simbolon,
signifita tie kiel triangulo.

351
00:15:34,910 --> 00:15:38,480
En kodo vi vidos ni proponas ke vi
implementado kiel bool, nur diras jes

352
00:15:38,480 --> 00:15:40,540
aŭ nenio, vorto haltas tie.

353
00:15:40,540 --> 00:15:45,270
>> Nu, iam ni foriris al M-Al-X-W-E-L-L,
sentas sep, eble

354
00:15:45,270 --> 00:15:48,910
ok se ni iros unu estinteco, ok
paŝojn por trovi Maxwell.

355
00:15:48,910 --> 00:15:53,050
Aŭ ni nomas ĝin K. Sed memoru lasta
tempo, mi argumentis, ke se ekzistas

356
00:15:53,050 --> 00:15:57,540
realisme maksimumo longeco sur
vorto, kiel 40-iuj-nepara gravuloj,

357
00:15:57,540 --> 00:16:00,810
maksimuma longo implicas
konstanta valoro.

358
00:16:00,810 --> 00:16:05,770
Do vere, jes, estas teknike granda O
de 8 aŭ 7, aŭ vere granda O de K. Sed

359
00:16:05,770 --> 00:16:09,420
se estas finia ĉapo sur kio
K povus esti, ĝi estas konstanto.

360
00:16:09,420 --> 00:16:12,080
Kaj tial estas granda O de 1, je
la fino de la tago.

361
00:16:12,080 --> 00:16:13,040
>> Ne en la reala mondo.

362
00:16:13,040 --> 00:16:15,960
Ne kiam vi vere komencos rigardi
vian horloĝon kiel via programo kurado.

363
00:16:15,960 --> 00:16:20,690
Ĝi estas absolute tuj estos iom
malrapida ol vere konstanto

364
00:16:20,690 --> 00:16:21,840
tempo kun unu paŝo.

365
00:16:21,840 --> 00:16:25,540
Ĝi tuj estos sep aŭ ok ŝtupoj,
sed ankoraŭ tio estas multe, multe pli bone

366
00:16:25,540 --> 00:16:30,080
ol algoritmon kiel granda O de n kiuj
dependas de la grandeco de kio estas en la

367
00:16:30,080 --> 00:16:31,220
datumstrukturo.

368
00:16:31,220 --> 00:16:34,970
>> Rimarku la inversita jen ni povas enigi
miliono pli nomoj en tiun

369
00:16:34,970 --> 00:16:38,170
datumstrukturo, sed kiom da paŝoj
Estas ĝi tuj portos nin trovi

370
00:16:38,170 --> 00:16:40,480
Maxwell en tiu kazo?

371
00:16:40,480 --> 00:16:40,780
Neniu.

372
00:16:40,780 --> 00:16:41,820
Li estas tuŝita.

373
00:16:41,820 --> 00:16:45,480
Kaj ĝis nun, mi ne kredas ke ni vidis
ekzemplo de datumstrukturo aŭ

374
00:16:45,480 --> 00:16:48,560
algoritmo kiu estis tute
tuŝita de eksteraj

375
00:16:48,560 --> 00:16:50,040
kondutojn tiel.

376
00:16:50,040 --> 00:16:51,160
Sed ĉi tiu ne povas esti mirinda.

377
00:16:51,160 --> 00:16:52,900
Ĉi tio ne povas esti la sola solvo
por la p-aro

378
00:16:52,900 --> 00:16:53,570
>> Kaj ĝi ne estas.

379
00:16:53,570 --> 00:16:55,980
Tiu ne estas nepre la datumoj
strukturo vi devus gravitas al,

380
00:16:55,980 --> 00:16:58,220
ĉar kiel hash tabloj, tradeoff.

381
00:16:58,220 --> 00:17:00,500
Kio estas la prezo vi pagas tie?

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

383
00:17:00,940 --> 00:17:02,890
Mi volas diri, ĉi tio estas abomena
kvanto da memoro.

384
00:17:02,890 --> 00:17:05,569
Kaj vi ne povas sufiĉe vidu ĝin ĉi tie ĉar
la aŭtoro de ĉi tiu pentraĵo

385
00:17:05,569 --> 00:17:09,420
evidente senpintigita ĉiuj sensilo,
kaj ni ne vidante multajn A kaj

386
00:17:09,420 --> 00:17:12,700
B kaj C-aj kaj Q kaj Y estas
kaj Z estas en tiuj matricoj.

387
00:17:12,700 --> 00:17:13,630
Sed ili estas tie.

388
00:17:13,630 --> 00:17:17,660
>> Ĉiu de ĉi tiuj nodoj estas tuta tabelo
de iuj 26 aŭ pli da bitokoj, ĉiu el

389
00:17:17,660 --> 00:17:19,170
kiu reprezentas leteron.

390
00:17:19,170 --> 00:17:22,920
27 en nia kazo, tiel ke ni povas apogi
apostrofoj en la problemo aro.

391
00:17:22,920 --> 00:17:27,030
Do tiu datumstrukturo estas vere,
vere densa kaj larĝa.

392
00:17:27,030 --> 00:17:30,880
Kaj tio nur povus fini malrapidiĝanta
aĵoj malsupren, aŭ almenaŭ kostas vin

393
00:17:30,880 --> 00:17:32,240
multe pli da spaco.

394
00:17:32,240 --> 00:17:34,020
Sed denove, ni povas desegni
komparoj tie.

395
00:17:34,020 --> 00:17:39,190
>> Memori tempo reen, ni atingis multan
pli ekscita rula tempo en ordiga

396
00:17:39,190 --> 00:17:42,880
kiam ni uzas merge varon, sed la prezo
Ni pagis por atingi n log n por merge

397
00:17:42,880 --> 00:17:46,930
speco postulis ke ni elspezos
pli kia rimedo?

398
00:17:46,930 --> 00:17:47,690
Pli spaco.

399
00:17:47,690 --> 00:17:50,530
Ni bezonas malĉefan tabelo por
kopii popolon en, samkiel

400
00:17:50,530 --> 00:17:51,620
ni faris ĉi tie sur la scenejo.

401
00:17:51,620 --> 00:17:55,880
Do denove, ne klara gajnantoj,
sed ĝuste subjektiva dezajno

402
00:17:55,880 --> 00:17:57,710
decidojn fari.

403
00:17:57,710 --> 00:17:58,060
>> Ĉio bone.

404
00:17:58,060 --> 00:17:59,130
Do kiel pri tio?

405
00:17:59,130 --> 00:18:02,050
Ĉiu rekonas ke D-Hall?

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

407
00:18:02,440 --> 00:18:03,170
Do tri el ni faras.

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

409
00:18:03,750 --> 00:18:05,070
Do tio estas por Mather la manĝejo.

410
00:18:05,070 --> 00:18:09,650
Mi vetas ĉiuj manĝoĉambroj havas
stakoj de pletoj ŝatas tion.

411
00:18:09,650 --> 00:18:11,950
Kaj jen estas vere reprezentanto
de io ni

412
00:18:11,950 --> 00:18:13,050
evidente vidis jam.

413
00:18:13,050 --> 00:18:14,850
Ni nomis ĝin laŭvorte pilo.

414
00:18:14,850 --> 00:18:18,970
Kaj la pilo, en terminoj de via
komputilo memoro, estas kie datumoj iras

415
00:18:18,970 --> 00:18:20,460
dum funkcioj estas nomata.

416
00:18:20,460 --> 00:18:23,410
>> Ekzemple, kiajn aferojn iri
sur la stako kun respekto al la

417
00:18:23,410 --> 00:18:27,420
memoro aranĝo ni diskutis
en semajnoj estinteco?

418
00:18:27,420 --> 00:18:28,736
Kio estas tio?

419
00:18:28,736 --> 00:18:29,670
>> Spektantaro: Alvokoj al funkcioj.

420
00:18:29,670 --> 00:18:30,260
>> DAVID Malan: mi bedaŭras.

421
00:18:30,260 --> 00:18:31,210
>> Spektantaro: Alvokoj al funkcioj.

422
00:18:31,210 --> 00:18:33,590
>> DAVID Malan: Alvokoj al funkcioj, sed
specife, kio estas ene de ĉiu el

423
00:18:33,590 --> 00:18:35,340
tiuj kadroj?

424
00:18:35,340 --> 00:18:37,220
Kiajn aferojn?

425
00:18:37,220 --> 00:18:37,460
Jes.

426
00:18:37,460 --> 00:18:38,500
Do lokaj variabloj.

427
00:18:38,500 --> 00:18:43,080
Anytime ni bezonis iu loka stokado,
kiel argumenton, aŭ int mi, aŭ int

428
00:18:43,080 --> 00:18:45,940
temp, aŭ kion ajn la loka
variablo, ni vizitis

429
00:18:45,940 --> 00:18:47,210
metante ke sur la stako.

430
00:18:47,210 --> 00:18:49,610
Kaj ni nomas ĝin pilo ĉar
de tiu layering ideo.

431
00:18:49,610 --> 00:18:52,940
Nur speco de alumetoj kun realo,
la koncepto de gxi.

432
00:18:52,940 --> 00:18:56,650
>> Sed ĝi rezultas ke pilo povas ankaŭ
vidiĝi kiel datumstrukturo, an

433
00:18:56,650 --> 00:19:00,110
alternativo al tabelo, alternativa
al lerta kunligita.

434
00:19:00,110 --> 00:19:02,770
Io koncepte pli interesa
kiu povas ankoraŭ esti

435
00:19:02,770 --> 00:19:06,030
implementado uzante ĉu de tiuj
aĵoj, sed estas malsama tipo de

436
00:19:06,030 --> 00:19:09,140
datumstrukturo apogante, vere,
nur du operacioj.

437
00:19:09,140 --> 00:19:11,000
Sed vi povas aldoni sur amatoro
trajtojn ol tiuj.

438
00:19:11,000 --> 00:19:12,180
Sed jen estas la fundamentojn -

439
00:19:12,180 --> 00:19:13,510
puŝi kaj pop.

440
00:19:13,510 --> 00:19:19,240
>> Kaj la ideo kun pilo estas ke se mi
jen, kun aŭ sen Annenberg

441
00:19:19,240 --> 00:19:22,880
sciante, pleto de la proksima pordo
kun la numero 9 en ĝi.

442
00:19:22,880 --> 00:19:23,870
Do nur int.

443
00:19:23,870 --> 00:19:26,990
Kaj mi volas puŝi tiun sur la datumoj
strukturon, kiu nuntempe estas malplena.

444
00:19:26,990 --> 00:19:28,790
Konsideru ĉi tiun la fundo de la pilo.

445
00:19:28,790 --> 00:19:33,150
Mi devus peli ĉi numero 9 sur la
pilo, kaj nun ĝi estas prava.

446
00:19:33,150 --> 00:19:36,040
>> Sed la interesa afero pri pilo
estas ke se mi nun volas puŝi

447
00:19:36,040 --> 00:19:40,210
iu alia valoro, kiel 17, kaj mi puŝi
ĉi sur la pilo, mi faros

448
00:19:40,210 --> 00:19:43,290
la sola intuicia afero, mi nur irante
meti ĝin ĝuste kie ni homoj

449
00:19:43,290 --> 00:19:45,180
estus inklina por meti ĝin sur pinton.

450
00:19:45,180 --> 00:19:48,850
Sed kio estas interesa nun
estas, kiel mi alveni al la 9?

451
00:19:48,850 --> 00:19:50,670
Vi scias, mi faras ne sen iuj penado.

452
00:19:50,670 --> 00:19:54,070
>> Do kio estas interesa
pilo estas ke per dezajno,

453
00:19:54,070 --> 00:19:56,330
ĝi estas LIFO datumstrukturo.

454
00:19:56,330 --> 00:19:59,680
Stulta maniero priskribi
lasta en, unua el.

455
00:19:59,680 --> 00:20:03,280
Do la lasta cifero en
en ĉi tiu epoko estis 17.

456
00:20:03,280 --> 00:20:07,540
Do se mi volas pop io ekstere
de la pilo, ĝi povas esti nur 17.

457
00:20:07,540 --> 00:20:11,890
Do tie estas deviga ordono de
operacioj tie, kie la lasta elemento

458
00:20:11,890 --> 00:20:14,260
en ĝi devas esti la unua el.

459
00:20:14,260 --> 00:20:16,440
Sekve la akronimo, LIFO.

460
00:20:16,440 --> 00:20:19,160
>> Do kial cxu tio estos utila?

461
00:20:19,160 --> 00:20:22,690
Estas iliaj kuntekstoj en kiuj vi volas
deziras datumstrukturo tiel?

462
00:20:22,690 --> 00:20:24,810
Nu, ĝi estas certe estis utilaj
ene de komputilo.

463
00:20:24,810 --> 00:20:29,050
Do mastrumaj sistemoj klare uzi ĉi
speco de datumstrukturo por piloj.

464
00:20:29,050 --> 00:20:32,800
Ni vidas ankaŭ la sama ideo
kiam temas retpaĝoj.

465
00:20:32,800 --> 00:20:35,890
Do tiu semajno kaj proksima semajno kaj preter,
kaj kiel vi komencas apliki retejo

466
00:20:35,890 --> 00:20:39,490
paĝoj en lingvo nomata HTML, vi povas
efektive uzi datumstrukturo kiel

467
00:20:39,490 --> 00:20:42,690
ĉi por determini se la paĝon
Estas ĝuste formatita.

468
00:20:42,690 --> 00:20:47,170
Ĉar ni vidos ĉiuj retpaĝoj sekvi
speco de hierarkio, la deŝovon

469
00:20:47,170 --> 00:20:52,030
kiu, fine de la tago, esti
arbo strukturo sub la kapuĉo.

470
00:20:52,030 --> 00:20:53,620
Do pli sur tiu en nur iom.

471
00:20:53,620 --> 00:20:56,560
>> Sed nuntempe, ni proponas por
momento, kiel ni povus iri

472
00:20:56,560 --> 00:20:58,830
reprezenti kion pilo estas?

473
00:20:58,830 --> 00:21:03,370
Permesu al mi proponi ke ni implemento
pilo kun kodo ŝatas tion.

474
00:21:03,370 --> 00:21:07,990
Do pilo tuj havi ene de ĝi
du aferoj, tabelo, nomita pletoj,

475
00:21:07,990 --> 00:21:09,510
nur por esti konsekvenca kun la demo.

476
00:21:09,510 --> 00:21:12,660
Kaj ĉiu el la artikoloj en tiu tabelo
tuj estos tipo int.

477
00:21:12,660 --> 00:21:14,740
Kaj kapablo estas supozeble kio?

478
00:21:14,740 --> 00:21:18,796
Ĉar mi ne skribis la
plena difino tie.

479
00:21:18,796 --> 00:21:21,535
>> Ĝi estas verŝajne la maksimuma
grandeco de la tabelo.

480
00:21:21,535 --> 00:21:25,150
Kaj ĝi estas probable deklarita kiel akra
difini ĉe la supro de la dosiero, iuj

481
00:21:25,150 --> 00:21:28,450
speco de konstanta kiel implicita de
la nura majuskloj.

482
00:21:28,450 --> 00:21:32,250
Do ie kapablo estas difinita
kiel la maksimuma ebla grandeco.

483
00:21:32,250 --> 00:21:35,590
Dume, ene de la datumstrukturo
konata kiel stako tie volo

484
00:21:35,590 --> 00:21:38,630
esti entjero nur scias
simple kiel grandeco.

485
00:21:38,630 --> 00:21:43,400
>> Do se mi estus por reprezenti tiun nun
pictóricamente, ni supozu, ke tiu

486
00:21:43,400 --> 00:21:48,070
tuta nigra skatolo reprezentas mian pilo.

487
00:21:48,070 --> 00:21:50,070
Ene de ĝi estas du variabloj.

488
00:21:50,070 --> 00:21:54,780
Do mi tuj tiri la
unue oni kiel grandeco.

489
00:21:54,780 --> 00:21:57,420
Kaj la dua mi iros
desegni tiel tablo.

490
00:21:57,420 --> 00:22:01,060
>> Sed ĝuste por subteni tion orde,
kutime mi eltirus tabelo kiel

491
00:22:01,060 --> 00:22:04,910
ĉi tio, sed estas speco de bela
se ni kongruas realaĵo, aŭ

492
00:22:04,910 --> 00:22:06,230
parigi la mensa modelo.

493
00:22:06,230 --> 00:22:12,880
Do mi anstataŭ desegni la tabelo
vertikale, kio estas justa, denove,

494
00:22:12,880 --> 00:22:13,840
artisto transdonado.

495
00:22:13,840 --> 00:22:16,610
Ne vere gravas kion
estas sub la kapuĉo.

496
00:22:16,610 --> 00:22:20,350
Kaj ni diras, ke, implicite,
kapablo tuj estos tri.

497
00:22:20,350 --> 00:22:23,480
Do tiu estos situo 0, ĉi tio
Estos situo 1, ĉi

498
00:22:23,480 --> 00:22:25,740
Estos situo 2.

499
00:22:25,740 --> 00:22:29,330
>> Se mi subaĉeti kun streso pilko, ĉu
iu ŝatus veni tien kaj ruli la

500
00:22:29,330 --> 00:22:30,870
enŝipigi tie dum nur momenta?

501
00:22:30,870 --> 00:22:31,960
Bone, mi vidis vian manon unue.

502
00:22:31,960 --> 00:22:33,950
Venu supren.

503
00:22:33,950 --> 00:22:36,500
Ĉio bone.

504
00:22:36,500 --> 00:22:38,760
Do mi opinias ke ĝi estas Steven.

505
00:22:38,760 --> 00:22:40,035
Venu supren.

506
00:22:40,035 --> 00:22:40,770
Ĉio bone.

507
00:22:40,770 --> 00:22:46,760
>> Sed supozas nun ni malantaŭenigi la komenca
stato de la mondo kie mi

508
00:22:46,760 --> 00:22:52,180
ĵus deklaris en pilo, kaj estas
tuj estos de kapablo tri.

509
00:22:52,180 --> 00:22:54,470
Sed grandeco ankoraŭ ne estis decidita.

510
00:22:54,470 --> 00:22:56,100
Pletoj ankoraŭ ne estis decidita.

511
00:22:56,100 --> 00:22:57,300
Do kelkaj demandoj unua.

512
00:22:57,300 --> 00:23:01,310
Kaj mi donos al vi mic tiel vi povas
partopreni pli aktive en ĉi tio.

513
00:23:01,310 --> 00:23:05,190
>> Do kio estas ene de amplekso en ĉi tiu momento
en la tempo kvazaŭ ĉiuj mi faris estas

514
00:23:05,190 --> 00:23:09,340
deklarita de pilo kun
unu linio de kodo?

515
00:23:09,340 --> 00:23:10,100
>> Steven: Ne tre.

516
00:23:10,100 --> 00:23:12,080
>> DAVID Malan: OK, ne multe.

517
00:23:12,080 --> 00:23:14,410
Ĉu ni scias kio estas ene de grandeco,
ni scias kio estas ene

518
00:23:14,410 --> 00:23:16,330
de tiu tabelo tie?

519
00:23:16,330 --> 00:23:18,630
>> Steven: Just hazarda kodo, ĉu ne?

520
00:23:18,630 --> 00:23:20,220
Ĝuste -

521
00:23:20,220 --> 00:23:23,230
>> DAVID Malan: Jes, mi tuj
nomas ĝin kodon, sed hazarda -

522
00:23:23,230 --> 00:23:23,820
>> Steven: Aĵoj.

523
00:23:23,820 --> 00:23:28,290
>> DAVID Malan: Aĵoj kiel hazarda

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

525
00:23:28,870 --> 00:23:29,530
>> DAVID Malan: Bitoj, ĉu ne?

526
00:23:29,530 --> 00:23:31,190
Do rubo valoroj, ĉu ne?

527
00:23:31,190 --> 00:23:33,470
Do permutoj de 0-aj kaj 1-oj.

528
00:23:33,470 --> 00:23:35,920
Restoj de antaŭa uzoj
de tiu memoro.

529
00:23:35,920 --> 00:23:38,150
Kaj ni ne vere scias kion la valoroj
estas, do ni tipe desegni ilin

530
00:23:38,150 --> 00:23:38,930
kiel demandosignojn.

531
00:23:38,930 --> 00:23:41,990
>> Do la unua horo ni supozeble
tuj volas fari ĉi tie -

532
00:23:41,990 --> 00:23:46,630
kaj mi donos al ĉi tiu kampo ene
de tie oni nomo - pletoj.

533
00:23:46,630 --> 00:23:49,540
Kion ni supozeble pravalorizi
grandeco se ni volas

534
00:23:49,540 --> 00:23:51,040
ekuzi ĉi pilo?

535
00:23:51,040 --> 00:23:53,070
>> Steven: Pleto estas sub 3.

536
00:23:53,070 --> 00:23:53,910
>> DAVID Malan: Do, OK.

537
00:23:53,910 --> 00:23:56,710
Por esti klaraj, kapablo estas deklarita
aliloke kiel tri.

538
00:23:56,710 --> 00:23:58,570
Kaj tio estas kion mi uzis
destini la tabelo.

539
00:23:58,570 --> 00:24:03,535
Grandeco tuj raporti al kiom
pletoj estas nuntempe en la pilo.

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

541
00:24:03,880 --> 00:24:04,460
>> DAVID Malan: Do ĝi devas esti nulo.

542
00:24:04,460 --> 00:24:07,760
Do iru antaŭen kaj kun iu ajn fingro
desegni nulo en grandeco.

543
00:24:07,760 --> 00:24:08,440
Ĉio bone.

544
00:24:08,440 --> 00:24:10,920
Do nun, kio estas ene de ĉi
tie, ni ne scias.

545
00:24:10,920 --> 00:24:12,160
Tio estas vere nur rubo valoroj.

546
00:24:12,160 --> 00:24:14,800
Do ni povus desegni demandosignojn, sed
ni observos la estraro pura cxar nun

547
00:24:14,800 --> 00:24:16,300
ĉar ne gravas
kio estas tie.

548
00:24:16,300 --> 00:24:19,130
Ni ne bezonas pravalorizi la tabelo
al nenio, ĉar se ni scias, ke

549
00:24:19,130 --> 00:24:23,100
la grandeco de la pilo estas nulo, nu, ni
oni ne rigardante ion en

550
00:24:23,100 --> 00:24:25,590
tiun tabelo ĉiuokaze ĉe
ĉi tiu punkto en tempo.

551
00:24:25,590 --> 00:24:29,970
>> Do nun supozas, ke mi pelas la
numero 9 sur la stako.

552
00:24:29,970 --> 00:24:33,750
Kiel do ni ĝisdatigi la datumstrukturo
ene de tiu nigra skatolo?

553
00:24:33,750 --> 00:24:35,540
Kio valoroj bezonas ŝanĝi?

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

555
00:24:36,200 --> 00:24:37,400
la grandeco?

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

557
00:24:37,650 --> 00:24:38,770
Grandeco unuiĝu kio?

558
00:24:38,770 --> 00:24:39,580
>> Steven: Grandeco estus unu.

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

560
00:24:39,870 --> 00:24:41,110
Do grandeco unuiĝu tiu.

561
00:24:41,110 --> 00:24:42,540
Do vi povas fari tion en paro manieroj.

562
00:24:42,540 --> 00:24:46,920
Lasu min donu al vi, nun via
fingro estas eraser.

563
00:24:46,920 --> 00:24:47,260
Ĉio bone.

564
00:24:47,260 --> 00:24:49,960
Tiam nun via fingro estas peniko.

565
00:24:49,960 --> 00:24:50,330
Ĉio bone.

566
00:24:50,330 --> 00:24:52,820
Kaj nun kio alia devas ŝanĝi,
evidente, en la datumstrukturo?

567
00:24:52,820 --> 00:24:57,060
>> Steven: Ni iras el
malsupro ĝis 9.

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

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

570
00:24:58,420 --> 00:25:01,550
Do ankoraŭ ne gravas kio estas ĉe
situo unu aŭ du ĉar ili estas

571
00:25:01,550 --> 00:25:04,520
rubo valoroj, sed ni ne devas ĝeni
serĉas tie ĉar grandeco estas

572
00:25:04,520 --> 00:25:07,540
diras al ni ke nur la unua ero
estas vere legitima.

573
00:25:07,540 --> 00:25:10,400
Do nun mi puŝi 17 sur la listo.

574
00:25:10,400 --> 00:25:11,830
Kio okazas al ĉi tiu bildo?

575
00:25:11,830 --> 00:25:14,720
>> Steven: Do grandeco tuj iros al du.

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

577
00:25:15,300 --> 00:25:16,070
Vi estas eraser -

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

579
00:25:16,810 --> 00:25:18,026
Vi estas eraser.

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

581
00:25:18,840 --> 00:25:19,720
>> DAVID Malan: Vi estas peniko.

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

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

584
00:25:20,920 --> 00:25:21,600
Kaj kion alian?

585
00:25:21,600 --> 00:25:22,600
>> Steven: Kaj tiam ni -

586
00:25:22,600 --> 00:25:22,915
>> DAVID Malan: Ni puŝis 17.

587
00:25:22,915 --> 00:25:24,760
>> Steven: Ni bati 17 sur supro, do -

588
00:25:24,760 --> 00:25:25,710
>> DAVID Malan: Bone, bone.

589
00:25:25,710 --> 00:25:27,040
>> Steven: - faligis ĝin malsupren.

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

591
00:25:27,530 --> 00:25:27,940
Fariĝas facila.

592
00:25:27,940 --> 00:25:29,300
Mi ne helpos al vi tiun tempon.

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

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

595
00:25:31,720 --> 00:25:34,870
Igante eraser.

596
00:25:34,870 --> 00:25:37,340
Mi ĉiufoje peniko.

597
00:25:37,340 --> 00:25:39,340
Kaj poste mi metante 22.

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

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

600
00:25:40,620 --> 00:25:41,380
Do unu pli longa tempo.

601
00:25:41,380 --> 00:25:44,280
Mi nun iras puŝi
sur la stako 26.

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

603
00:25:46,350 --> 00:25:50,278
Ho gosh.

604
00:25:50,278 --> 00:25:52,520
Vi vere kaptis min gvardio.

605
00:25:52,520 --> 00:25:53,703
>> DAVID Malan: Vi ne
vidu ĉi alveno?

606
00:25:53,703 --> 00:25:55,930
>> Steven: Mi ne vidis ĉi venas.

607
00:25:55,930 --> 00:25:58,756
Ĉu ni re-komenca kapablo?

608
00:25:58,756 --> 00:25:59,790
>> DAVID Malan: Tio estas bona demando.

609
00:25:59,790 --> 00:26:02,360
Do ni ia pentris mem
en angulo tie.

610
00:26:02,360 --> 00:26:06,740
Tie vere estas nenio bona eliris por Steven
ĉar ni destinis tiun tabelo

611
00:26:06,740 --> 00:26:09,130
statike, por tiel diri, interne
de la datumstrukturo.

612
00:26:09,130 --> 00:26:12,170
Kaj ni esence hard coded
ĝin esti de amplekso tri.

613
00:26:12,170 --> 00:26:14,170
Do ni ne povas vere reallocate ĝin.

614
00:26:14,170 --> 00:26:20,020
>> Ni povus, se ni reiris en, ni
redifinis pletoj esti puntero ke

615
00:26:20,020 --> 00:26:22,300
ni do uzu malloc al mano memoro.

616
00:26:22,300 --> 00:26:25,050
Ĉar se ni akiris la memoro de
la amaso tra malloc, ni

617
00:26:25,050 --> 00:26:26,430
povus tiam liberigi ĝin.

618
00:26:26,430 --> 00:26:29,630
Sed antaŭ ol liberigi ĝin, ni povis
reallocate pli grandan eron de memoro,

619
00:26:29,630 --> 00:26:31,330
ĝisdatigi la puntero, kaj tiel plu.

620
00:26:31,330 --> 00:26:33,500
Sed nuntempe, ĉi tio estas vere
la bona ni povas fari.

621
00:26:33,500 --> 00:26:36,360
Push kaj pop estas supozeble tuj
havi por marki iun eraron.

622
00:26:36,360 --> 00:26:40,270
>> Do ekzemple, niaj efektivigo
de puŝo povis reveni al bool kiu

623
00:26:40,270 --> 00:26:42,390
antaŭe revenis vera, vera, vera.

624
00:26:42,390 --> 00:26:48,390
Sed la kvara fojo, ĝi tuj devos
redoni malvera, ekzemple.

625
00:26:48,390 --> 00:26:48,540
Ĉio bone.

626
00:26:48,540 --> 00:26:49,540
Tre bone farita.

627
00:26:49,540 --> 00:26:50,060
Gratulojn.

628
00:26:50,060 --> 00:26:52,160
Vi gajnis via streso pilko hodiaŭ.

629
00:26:52,160 --> 00:26:53,110
>> [Aplaŭdo]

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

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

632
00:26:55,680 --> 00:26:59,740
Bone, do tio ŝajnas esti ne multe
de paŝo antaŭen, ĉu ne?

633
00:26:59,740 --> 00:27:01,410
Ni priskribis ĉi datumstrukturo.

634
00:27:01,410 --> 00:27:02,320
Jam pasis konvinka, ĉu ne?

635
00:27:02,320 --> 00:27:03,200
Mastrumaj sistemoj ŝatas ĝin.

636
00:27:03,200 --> 00:27:06,360
Ŝajne la retejo povas uzi tion,
kaj aliaj aplikoj ankoraŭ.

637
00:27:06,360 --> 00:27:10,870
Sed kia stulta limigo kiu ni estas
apogi al speco de semajno du limoj

638
00:27:10,870 --> 00:27:12,880
kie ni fiksita grandeco arrays.

639
00:27:12,880 --> 00:27:15,010
>> Do estas ja kelkaj
manieroj ni povus solvi ĉi.

640
00:27:15,010 --> 00:27:18,750
Ni povus dinamike atribui la tabelo,
ne per malmola kodigo kiel mi havas

641
00:27:18,750 --> 00:27:22,600
faris ĉi tie, sed anstataŭ re-deklarante
tiu, nur por esti klara, kiel

642
00:27:22,600 --> 00:27:23,830
iu kiel ĉi tio.

643
00:27:23,830 --> 00:27:29,040
Int * pletoj, ne decidi
sur kapablo ankoraŭ.

644
00:27:29,040 --> 00:27:35,460
Sed kiam mi deklaras la pilo aliloke
en mia kodo, mi povus tiam nomita malloc,

645
00:27:35,460 --> 00:27:38,250
atingi la adreson de eron de
memoro, kaj mi povis atribui

646
00:27:38,250 --> 00:27:39,980
ke adreso por pletoj.

647
00:27:39,980 --> 00:27:43,340
>> Kaj poste, ĉar ĝi estas nur eron de
memoro, mi povis sekvi uzi kvadratan

648
00:27:43,340 --> 00:27:45,450
krampo notacio en la kutima maniero.

649
00:27:45,450 --> 00:27:49,020
Ĉar denove, estas speco de tiu
funkcia ekvivalento de arrays kaj

650
00:27:49,020 --> 00:27:50,820
pecoj de memoro kiu venis
revenis de malloc.

651
00:27:50,820 --> 00:27:53,090
Ni povas trakti unu kiel la alia
uzante puntero aritmetiko aŭ

652
00:27:53,090 --> 00:27:54,440
kvadrata krampo skribmaniero.

653
00:27:54,440 --> 00:27:55,660
Do jen unu alproksimiĝo.

654
00:27:55,660 --> 00:28:00,120
>> Sed kiel alie povus ni apliki tiun
sama datumstrukturo, potenciale?

655
00:28:00,120 --> 00:28:00,280
Ĝuste?

656
00:28:00,280 --> 00:28:04,530
Mi sentas kiel ni ĵus solvis ĉi
problemo kiel antaŭ unu semajno.

657
00:28:04,530 --> 00:28:08,860
Kio estis la solvo al tiu problemo
ke Steven kuris en?

658
00:28:08,860 --> 00:28:10,370
Do ligitaj lertaj, dekstre.

659
00:28:10,370 --> 00:28:13,410
>> Se la problemo estas ke ni pentri
nin en angulon de atribuo

660
00:28:13,410 --> 00:28:17,580
anticipe tro malmultan memoron, ke ni
tiam devas iel pritrakti, bone,

661
00:28:17,580 --> 00:28:19,880
kial ne simple eviti tiun
elsendi aro?

662
00:28:19,880 --> 00:28:26,170
Kial ne simple deklaras pletoj esti
puntero al nodo, ergo lerta kunligita,

663
00:28:26,170 --> 00:28:30,740
kaj tiam simple malŝparas novaj nodoj
ĉiufoje Steven bezonas ĝustigi

664
00:28:30,740 --> 00:28:32,400
nombro en la datumstrukturo.

665
00:28:32,400 --> 00:28:34,200
>> Do la bildo devus ŝanĝi.

666
00:28:34,200 --> 00:28:38,220
Oni ne tuj estos tiel pura kaj kiel
simpla kiel nur tabelo de tri ints.

667
00:28:38,220 --> 00:28:42,970
Nun ĝi estas tuj estos referenco al
struct, kaj ke struct tuj

668
00:28:42,970 --> 00:28:44,830
havi _int_ kaj proksima puntero.

669
00:28:44,830 --> 00:28:47,670
Ĝi tuj konduki tra tiu puntero
al alia tia struct al

670
00:28:47,670 --> 00:28:48,600
alia tia struct.

671
00:28:48,600 --> 00:28:50,560
Do la bildo estus efektive
akiri iom Messier.

672
00:28:50,560 --> 00:28:52,950
Kaj ni volas esti sagoj ligi
ĉion kune.

673
00:28:52,950 --> 00:28:55,280
>> Sed tio estas bone, dekstra, ĉar
ni vidis kiel fari tion.

674
00:28:55,280 --> 00:28:58,180
Kaj iam vi akiras komfortan
efektivigi iun kiel kunligita

675
00:28:58,180 --> 00:29:01,450
listo, kiun vi devos fari se vi
elekti apliki kradon tablo kun

676
00:29:01,450 --> 00:29:05,120
apartan ĉeni por p-aro 6, vi povas
uzi ĝin kiel konstruaĵo bloko, aŭ

677
00:29:05,120 --> 00:29:08,870
ingredienco, aŭ en Scratch paroli, oni
proceduro, iu kiu vin meti, vi

678
00:29:08,870 --> 00:29:12,560
kreis vian propran puzlo peco
ke vi povas tiam reuzi.

679
00:29:12,560 --> 00:29:17,090
Do tradeoffs, sed eblaj solvoj
ke ni reale vidis antaŭe.

680
00:29:17,090 --> 00:29:20,560
>> Do tre ofte, vi vidas cxi tiun ĉiu
jaro aŭ du, kiam Apple ĵetoj

681
00:29:20,560 --> 00:29:23,060
iu nova, kaj ĉiuj frenezaj
laŭliniigi eksteren de la Apple

682
00:29:23,060 --> 00:29:27,050
stoki aĉeti ilian marĝenan
ĝisdatigi la aparataron.

683
00:29:27,050 --> 00:29:30,420
Mi diras tion, estas bone, ĉar
Mi estas unu el tiuj personoj.

684
00:29:30,420 --> 00:29:35,140
Do kia datumstrukturo
povus reprezenti ĉi realaĵo?

685
00:29:35,140 --> 00:29:36,980
>> Nu, ni nomas ĝin vosto, linio.

686
00:29:36,980 --> 00:29:40,270
Do britoj nomas ĝin tipe
vosto ĉiuokaze, do ĝi estas bela nomo.

687
00:29:40,270 --> 00:29:44,960
Kaj la du operacioj kiuj vosto
oni apogas ni nomas enqueue

688
00:29:44,960 --> 00:29:48,900
operacion kaj dequeue operacio,
kiuj estas similaj en

689
00:29:48,900 --> 00:29:50,120
spirito puŝi kaj pop.

690
00:29:50,120 --> 00:29:54,060
Estas nur speco de malsama en
konvencio, kion ni nomas tiujn.

691
00:29:54,060 --> 00:29:57,680
Sed por enqueue ion signifas aldoni
aŭ enmeti ĝin al la datumstrukturo.

692
00:29:57,680 --> 00:29:59,570
Por dequeue signifas forigi ĝin.

693
00:29:59,570 --> 00:30:05,170
Sed dum pilo estis LIFO datumoj
strukturo, vosto estas unua en,

694
00:30:05,170 --> 00:30:06,740
unua el datumstrukturo.

695
00:30:06,740 --> 00:30:10,050
>> Se vi estas la unua persono en linio,
Vi estos la unua persono akiri

696
00:30:10,050 --> 00:30:12,420
el linio kaj aĉeti via nova aparato.

697
00:30:12,420 --> 00:30:18,070
Imagu kiel renversita tiuj homoj estus
se Apple anstataŭ uzi pilo, por

698
00:30:18,070 --> 00:30:21,250
Ekzemple, por apliki la pluki
supren de via nova ludilo.

699
00:30:21,250 --> 00:30:24,310
Do vostoj sencon, certe, kaj
ni povas pensi pri ĉiaj

700
00:30:24,310 --> 00:30:27,480
aplikoj, supozeble, por vostoj,
precipe kiam oni volas justeco.

701
00:30:27,480 --> 00:30:30,040
Do kiel eble ni apliki tiujn
kiel datumstrukturo?

702
00:30:30,040 --> 00:30:33,680
>> Nu, mi proponas ke ni
bezonas fari ĝin tiamaniere.

703
00:30:33,680 --> 00:30:35,225
Do mi tuj nun havas numerojn.

704
00:30:35,225 --> 00:30:38,190
Do ni devos konservi ĝin simpla kaj ne
nepre parolas en terminoj de pletoj.

705
00:30:38,190 --> 00:30:40,220
Nur nombroj, ke homoj de alveninta.

706
00:30:40,220 --> 00:30:43,760
Kapablo tuj, denove, ripari la
totala nombro de homoj kiuj povas esti en

707
00:30:43,760 --> 00:30:46,900
ĉi tiu linio, kiel tri aŭ
ajn alia valoro.

708
00:30:46,900 --> 00:30:50,760
>> Sed mi proponas ke mi bezonas konservi trako
ne nur de la grandeco de la

709
00:30:50,760 --> 00:30:52,370
vosto, kiom da aferoj estas en ĝi.

710
00:30:52,370 --> 00:30:56,310
Do grandeco estas la aktuala grandeco, kapablo
estas la maksimuma grandeco.

711
00:30:56,310 --> 00:30:58,540
Nur denove, nomenklaturo
per konvencio.

712
00:30:58,540 --> 00:31:03,680
Kial mi bezonas plian int ene
de vosto al sekvigi kiuj estas en

713
00:31:03,680 --> 00:31:05,365
antaŭ la linio?

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

715
00:31:07,930 --> 00:31:10,910
Kial mi devas fari ke en tiu kazo?

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

717
00:31:14,750 --> 00:31:16,190
>> Nu, kial ĉi tiu bildo
tuj ŝanĝos?

718
00:31:16,190 --> 00:31:19,280
Mi versxajne povas reuzi plej
de ĉi tiu pentraĵo.

719
00:31:19,280 --> 00:31:21,480
Lasu min antaŭeniri kaj viŝi kio estas tie.

720
00:31:21,480 --> 00:31:24,580
Ni donos al tiu iomete
malsama nomo ĝis ĉi tie.

721
00:31:24,580 --> 00:31:28,930
Ni forigi la 17, ni liveri
de la 9, ni liveris de la 3.

722
00:31:28,930 --> 00:31:30,410
Kaj ni aldonu unu alia afero.

723
00:31:30,410 --> 00:31:34,710
Mi proponas, ke mi devas sekvigi
la fronto de la listo, kiu estas ĝuste

724
00:31:34,710 --> 00:31:35,570
tuj estos int tiel.

725
00:31:35,570 --> 00:31:36,550
Kaj ni tuj teni ĝin simpla.

726
00:31:36,550 --> 00:31:37,740
Neniu ligitaj listo por nun.

727
00:31:37,740 --> 00:31:40,900
>> Ni agnoskas, ke ni tuj
bump kontraux cxi tiun limon.

728
00:31:40,900 --> 00:31:43,720
Sed kion mi volas vidi
okazi cxi tiun tempon?

729
00:31:43,720 --> 00:31:47,240
Do supozas ke mi iru antaŭen kaj la unua
persono venas supren en linio, kaj

730
00:31:47,240 --> 00:31:48,560
ĝi estas la numero 9.

731
00:31:48,560 --> 00:31:49,680
Ni ja havas streson pilkojn.

732
00:31:49,680 --> 00:31:51,330
Ĉu mi povas sxteli, diru, du aŭ tri personoj?

733
00:31:51,330 --> 00:31:52,690
Unu, du, tri?

734
00:31:52,690 --> 00:31:53,120
Venu supren.

735
00:31:53,120 --> 00:31:56,022
Rajto de la fronto, ĉar
ni faros ĉi tiu rapida.

736
00:31:56,022 --> 00:31:59,415
>> Ĉiu el vi nun tuj estos
fano knabo en linio de Apple.

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

738
00:32:03,970 --> 00:32:06,210
Vi ne povas ricevi Apple aparataro
fine de tiu though.

739
00:32:06,210 --> 00:32:06,500
Ĉio bone.

740
00:32:06,500 --> 00:32:09,430
Do vi estas numero 9, vi estas
numero 17, numero 22.

741
00:32:09,430 --> 00:32:12,130
Ĉi tiuj estas arbitraj nombroj, kiel
studento IDs aŭ whatnot.

742
00:32:12,130 --> 00:32:14,550
Kaj en nur momente, ni komencu
komenci aldoni aferojn.

743
00:32:14,550 --> 00:32:16,000
Mi kuros la estraro tie ĉi tempo.

744
00:32:16,000 --> 00:32:19,570
>> Do, en tiu kazo, mi inicializado
la fronto por esti -

745
00:32:19,570 --> 00:32:22,380
Mi fakte ne vere gravas kion la
antaŭaĵo estas tio, ke la grandeco estas nulo.

746
00:32:22,380 --> 00:32:24,480
Do tio povus tiel simple
esti demandosigno.

747
00:32:24,480 --> 00:32:26,170
Ĉi tiuj estas ĉiuj demandosignojn.

748
00:32:26,170 --> 00:32:29,880
Do nun ni komencas reale vidi iun
homoj kiuj kovras ĉe la vendejo.

749
00:32:29,880 --> 00:32:33,320
>> Do se numero 9, vi estas la unua
tie ĉe 5 AM, antaŭeniri kaj vicigas,

750
00:32:33,320 --> 00:32:34,210
aŭ la antaŭa nokto.

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

752
00:32:34,580 --> 00:32:35,940
Do nun 9 estas ĉi tie.

753
00:32:35,940 --> 00:32:37,940
Do 9 estas en la fronto de la listo.

754
00:32:37,940 --> 00:32:41,440
Do mi tuj iros antaŭen kaj ĝisdatigi
la grandeco de tiu fluo datumoj

755
00:32:41,440 --> 00:32:44,740
strukturo por ne esti 0 plu,
sed al esti 1.

756
00:32:44,740 --> 00:32:47,630
Mi tuj metos 9, je la
Fronte al la listo.

757
00:32:47,630 --> 00:32:51,020
Lasu min antaŭeniri kaj ebligi la ekrano
tiel ni povas vidi pasintajn nin ĉi tie.

758
00:32:51,020 --> 00:32:53,220
>> Kaj nun kion mi volas
meti al antaŭa?

759
00:32:53,220 --> 00:32:56,240
Mi tuj sekvigi ke la
Fronte al la vosto nun

760
00:32:56,240 --> 00:32:58,570
estas je situo 0.

761
00:32:58,570 --> 00:33:00,510
Pro kio sekva okazos?

762
00:33:00,510 --> 00:33:03,000
Nu, supozu nun mi enqueue
17 tiel.

763
00:33:03,000 --> 00:33:04,510
Do hop en linio tie.

764
00:33:04,510 --> 00:33:07,060
Kaj denove, la speco de pordo al la
vendejo tuj estos tie.

765
00:33:07,060 --> 00:33:08,700
Do nun mi aldonis 17.

766
00:33:08,700 --> 00:33:10,810
Kaj eĉ se tiuj infanoj blokas
la ekrano, tio estas OK,

767
00:33:10,810 --> 00:33:12,300
ĉar ni povas vidi ĝin tie.

768
00:33:12,300 --> 00:33:12,910
Pardonon.

769
00:33:12,910 --> 00:33:13,810
>> Spektantaro: Ni povas movi -

770
00:33:13,810 --> 00:33:14,660
>> DAVID Malan: Ne, tio estas okej.

771
00:33:14,660 --> 00:33:16,000
Ĝi estas grandega tie supre.

772
00:33:16,000 --> 00:33:18,580
Do 17 estas nun ene de la vico.

773
00:33:18,580 --> 00:33:21,332
Mi bezonas ĝisdatigi kiu
kampoj nun kvankam?

774
00:33:21,332 --> 00:33:23,210
OK, definitive grandeco.

775
00:33:23,210 --> 00:33:26,430
Kaj kion pri antaŭa?

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

777
00:33:27,040 --> 00:33:30,200
Fronto ne devus ŝanĝi, ĉar
kontraste de pilo, ni

778
00:33:30,200 --> 00:33:31,370
volas subteni justeco.

779
00:33:31,370 --> 00:33:35,150
Do se 9 venis unue, ni volas 9
esti la unua el la linio

780
00:33:35,150 --> 00:33:36,420
kaj en la vendejo.

781
00:33:36,420 --> 00:33:37,220
>> Fakte, vidu tion.

782
00:33:37,220 --> 00:33:42,235
Antaŭ ni enŝovu 22, ni
antaŭeniri kaj dequeue 9.

783
00:33:42,235 --> 00:33:42,970
Kio estas via nomo denove?

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

785
00:33:43,680 --> 00:33:45,440
>> DAVID Malan: Jake tuj
esti dequeued nun.

786
00:33:45,440 --> 00:33:48,050
Do vi ricevas marŝi en la vendejo.

787
00:33:48,050 --> 00:33:49,880
Kaj ŝajnigi ke la vendejo
estas tie.

788
00:33:49,880 --> 00:33:51,970
Do nun kio bezonas - dit-dit-dit!

789
00:33:51,970 --> 00:33:53,400
Kio devas okazi nun?

790
00:33:53,400 --> 00:33:54,490
Dezajno decido.

791
00:33:54,490 --> 00:33:56,825
Do ne estas malbona instinkto, sed -
kio estas via nomo denove?

792
00:33:56,825 --> 00:33:57,090
>> Spektantaro: Davido.

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

794
00:33:57,500 --> 00:33:58,810
Do kio, David fari?

795
00:33:58,810 --> 00:34:02,590
Li provis ordigi de ripari la datumoj
strukturo kaj movigxas de sia loko

796
00:34:02,590 --> 00:34:04,100
en Jake La eksa loko.

797
00:34:04,100 --> 00:34:06,740
Kaj tio estas bone se ni pretas
akcepti ke kiel

798
00:34:06,740 --> 00:34:08,199
efektivigo detalo.

799
00:34:08,199 --> 00:34:11,100
Sed unue, ni ĝisdatigis la datumoj
strukturo antaŭ ol ni faras tion.

800
00:34:11,100 --> 00:34:14,139
Ĉar mi ne placxis al mi la ideo de ĉiuj
la popolo sxangxigxantaj en ĉi tiu linio.

801
00:34:14,139 --> 00:34:17,360
>> Ne estas granda interkonsento se Davido faras ĝin per
unu paŝo, sed denove, opinias reen al

802
00:34:17,360 --> 00:34:20,360
kiam ni havis ok volontuloj en la
scenejo kaj ni faris kiel inserción

803
00:34:20,360 --> 00:34:22,600
varon, kie ni devis komenci
movi ĉiuj ĉirkaŭe.

804
00:34:22,600 --> 00:34:23,790
Kiu alvenis multekosta, ĉu ne?

805
00:34:23,790 --> 00:34:28,330
Tio igas min cringe pri granda O
de n, granda O de n akordita denove.

806
00:34:28,330 --> 00:34:30,650
Tio ne sentante kiel
idealan rezulton.

807
00:34:30,650 --> 00:34:32,080
>> Do ni simple ĝisdatigi ĉi.

808
00:34:32,080 --> 00:34:35,120
Do la grandeco de la vosto
ne plu estas 2.

809
00:34:35,120 --> 00:34:37,090
Ĝi estas nun simple 1.

810
00:34:37,090 --> 00:34:40,360
Sed mi povas nun ĝisdatigi ion
Mi ne ĝisdatigis antaŭe, la

811
00:34:40,360 --> 00:34:41,130
Fronte al la listo.

812
00:34:41,130 --> 00:34:45,420
Mi povis nur diri, estas ke situo 1?

813
00:34:45,420 --> 00:34:49,770
Do nun ni havas rubo valoro ĉi tie,
rubo valoro ĉi tie, kaj Davidon en la

814
00:34:49,770 --> 00:34:51,469
Meze de ĉi tiu rubo.

815
00:34:51,469 --> 00:34:54,980
Sed la datumstrukturo
ankoraŭ estas sendifekta.

816
00:34:54,980 --> 00:34:58,540
>> Kaj fakte, mi eĉ ne bezonas
ŝanĝi Jake iama nombro

817
00:34:58,540 --> 00:35:00,460
9, ĉar kiu zorgas.

818
00:35:00,460 --> 00:35:04,470
Mi havas sufiĉe informo nun en la
grandeco, ke mi scias ke ekzistas unu persono en

819
00:35:04,470 --> 00:35:05,030
tiu vosto.

820
00:35:05,030 --> 00:35:08,340
Kaj mi scias, ke tiu persono
estas en loko 1, ne 0.

821
00:35:08,340 --> 00:35:09,760
Mi ne rakonti.

822
00:35:09,760 --> 00:35:11,300
Do 1 kiel bone.

823
00:35:11,300 --> 00:35:13,410
Do la datumstrukturo ankoraŭ OK.

824
00:35:13,410 --> 00:35:14,330
>> Nu, kio okazas nun?

825
00:35:14,330 --> 00:35:15,010
Ni enqueue -

826
00:35:15,010 --> 00:35:15,370
kio estas via nomo?

827
00:35:15,370 --> 00:35:16,160
>> Spektantaro: Callen.

828
00:35:16,160 --> 00:35:16,580
>> DAVID Malan: Callen.

829
00:35:16,580 --> 00:35:20,770
Ni enqueue a Callen, kaj
22 estas nun en la vico.

830
00:35:20,770 --> 00:35:22,300
Do nun kio devas ŝanĝi ĉi tie?

831
00:35:22,300 --> 00:35:24,380
Fronto ne tuj
ŝanĝi, evidente.

832
00:35:24,380 --> 00:35:27,160
Grandeco tuj ŝanĝos esti 2 denove.

833
00:35:27,160 --> 00:35:31,590
Kaj 22 finas ĉi tie, 9 estas ankoraŭ aktuala,
sed estas efektive

834
00:35:31,590 --> 00:35:32,600
rubo valoro nun.

835
00:35:32,600 --> 00:35:35,910
Estas nur la restintoj de Jake pasinteco.

836
00:35:35,910 --> 00:35:39,200
>> Do nun kio okazas se
Mi dequeue David?

837
00:35:39,200 --> 00:35:41,560
Unu lasta operacio, dequeue Davido.

838
00:35:41,560 --> 00:35:46,070
Ni povis ŝanĝi, sed mi proponas Atendu
fari tiel malmulta laboro kiel ebla.

839
00:35:46,070 --> 00:35:50,280
Nun mia datumstrukturo iras
apogi en grandeco de 2 al 1.

840
00:35:50,280 --> 00:35:53,730
Sed la fronto de la vosto
nun iĝas 2.

841
00:35:53,730 --> 00:35:56,640
Mi ne bezonas ŝanĝi tiuj numeroj
nur ankoraŭ, ĉar ili estas

842
00:35:56,640 --> 00:35:58,230
nur rubo valoroj.

843
00:35:58,230 --> 00:35:59,720
>> Sed nun kio okazas?

844
00:35:59,720 --> 00:36:03,280
Supozu mi enqueue mem, 26?

845
00:36:03,280 --> 00:36:05,890
Mi sentas ke mi apartenas ĉi tien.

846
00:36:05,890 --> 00:36:06,890
Do mi esti enqueued.

847
00:36:06,890 --> 00:36:08,760
Do mi specon de aparteni ĉi tie.

848
00:36:08,760 --> 00:36:11,300
Kaj eĉ se vi ne sufiĉe
estimi ĉi vide sur la scenejo,

849
00:36:11,300 --> 00:36:15,075
ĉar ni havas multe da ĉambro, mi devus
ne staras tie, kial?

850
00:36:15,075 --> 00:36:16,290
>> Spektantaro: Vi estas ekster limojn.

851
00:36:16,290 --> 00:36:16,370
>> DAVID Malan: Ĝuste.

852
00:36:16,370 --> 00:36:16,940
Mi estas el limojn.

853
00:36:16,940 --> 00:36:19,330
Mi indeksita preter la
limoj de tiu tabelo.

854
00:36:19,330 --> 00:36:23,420
Mi vere devus esti en unu el la
tri eblaj lokoj.

855
00:36:23,420 --> 00:36:25,150
Nun, kie estas plej natura iri?

856
00:36:25,150 --> 00:36:27,760
Mi proponas ke ni leveraged
semajno unu artifiko.

857
00:36:27,760 --> 00:36:30,150
La mod operatoro, procento.

858
00:36:30,150 --> 00:36:36,850
Ĉar mi teknike staris
situo 3, sed mi faras 3 _mod_ kapablo,

859
00:36:36,850 --> 00:36:40,250
tial 3, procento signo, 3 -

860
00:36:40,250 --> 00:36:40,970
kapablo estas 3.

861
00:36:40,970 --> 00:36:41,720
Kio estas tio?

862
00:36:41,720 --> 00:36:43,700
Kio estas la resto kiam
vi dividas 3 por 3?

863
00:36:43,700 --> 00:36:44,070
0.

864
00:36:44,070 --> 00:36:48,140
>> Do kiu metas min estis Jake estis,
kiu estas vere bona.

865
00:36:48,140 --> 00:36:50,370
Do nun la efektivigo
de tiu afero tuj

866
00:36:50,370 --> 00:36:51,250
esti iom pri kapdoloro.

867
00:36:51,250 --> 00:36:53,740
Estas vere nur unu linio
de kapdoloro, de kodo.

868
00:36:53,740 --> 00:36:56,580
Sed almenaŭ nun tie estas rubo
valoron tie, sed ekzistas du

869
00:36:56,580 --> 00:36:57,910
legitima ints tie.

870
00:36:57,910 --> 00:37:04,160
Kaj mi asertas ke nun ni faris
ĝuste kion ni bezonas por fari tiel longe kiel

871
00:37:04,160 --> 00:37:08,600
ni ŝanĝas kion Jake la
valoro devis esti 26.

872
00:37:08,600 --> 00:37:12,110
>> Ni nun havas sufiĉe informo ankoraŭ
subteni la integrecon

873
00:37:12,110 --> 00:37:13,060
de tiu datumstrukturo.

874
00:37:13,060 --> 00:37:17,160
Ni estas ankoraŭ ia el sorton, kiam ni
volas enmeti kvar aŭ pli entute

875
00:37:17,160 --> 00:37:20,740
elementoj, sed mi povas almenaŭ fari belan
efika uzo de ĉi tiu konstanto

876
00:37:20,740 --> 00:37:21,740
tempo, fakte.

877
00:37:21,740 --> 00:37:27,150
Mi ne devas maltrankviligi sxangxigxantaj
ĉiuj, kiel David deklivo estis.

878
00:37:27,150 --> 00:37:30,816
>> Ajna demandojn sur piloj,
aŭ ĉi vosto?

879
00:37:30,816 --> 00:37:32,184
>> Spektantaro: Ĉu la kialo kial
vi bezonas grandeco por vi scias

880
00:37:32,184 --> 00:37:34,010
kie havi persono?

881
00:37:34,010 --> 00:37:34,770
>> DAVID Malan: Ĝuste.

882
00:37:34,770 --> 00:37:38,230
Mi bezonas scii la grandecon de la tabelo
ĉar mi bezonas scii precize kiel

883
00:37:38,230 --> 00:37:41,940
multaj de ĉi tiuj valoroj estas legitima,
kaj por ke mi povas trovi kie meti

884
00:37:41,940 --> 00:37:42,800
la sekvanta persono.

885
00:37:42,800 --> 00:37:43,300
Ekzakte.

886
00:37:43,300 --> 00:37:44,580
La grandeco estas -

887
00:37:44,580 --> 00:37:46,360
fakte, ni ne ĝisdatigis ĉi ankoraŭ.

888
00:37:46,360 --> 00:37:48,380
Mi aldonis min je 26.

889
00:37:48,380 --> 00:37:51,760
La grandeco estas nun, ne 1, sed 2.

890
00:37:51,760 --> 00:37:57,780
Do nun tio ja helpas min trovi la
estro de la listo, kiu estas ne 0, ne

891
00:37:57,780 --> 00:37:59,250
1, sed estas 2.

892
00:37:59,250 --> 00:38:01,665
La fronto de la listo
estas ja la numero 22.

893
00:38:01,665 --> 00:38:05,120
Ĉar li venis en la komenco, do li devus
esti permesita en la vendejo antaŭ mi,

894
00:38:05,120 --> 00:38:08,780
kvankam vide Mi staras
pli proksime al la vendejo.

895
00:38:08,780 --> 00:38:09,220
>> Ĉio bone?

896
00:38:09,220 --> 00:38:12,410
Ronda de aplaŭdo por tiuj infanoj
kaj ni lasu ilin el tie.

897
00:38:12,410 --> 00:38:17,090
>> [Aplaŭdo]

898
00:38:17,090 --> 00:38:18,150
>> DAVID Malan: Mi povus lasu
vi observos la pleto.

899
00:38:18,150 --> 00:38:20,760
Ni povis vidi kio okazas se
vi volas, sed eble ne.

900
00:38:20,760 --> 00:38:21,590
Ĉio bone.

901
00:38:21,590 --> 00:38:25,380
Do kio nun faras kiuj lasas al ni?

902
00:38:25,380 --> 00:38:28,900
Nu, mi proponas ke tie estas
kelkaj aliaj datumstrukturoj ni povis

903
00:38:28,900 --> 00:38:33,810
eku aldoni al nia ilo kit kiu volo
reale esti sufiĉe, sufiĉe grava kiel

904
00:38:33,810 --> 00:38:35,270
ni plonĝi en retejo aĵoj.

905
00:38:35,270 --> 00:38:38,150
Kiu denove, ĝi havas ian rilaton
trees en la formo de

906
00:38:38,150 --> 00:38:40,550
iu nomita DOM, dokumento
objekto modelo.

907
00:38:40,550 --> 00:38:42,370
Sed ni vidos pli
ke antaŭ longe.

908
00:38:42,370 --> 00:38:46,260
>> Permesu al mi proponi definitionally ke ni
voki arbo nun kio vi eble scias kiel

909
00:38:46,260 --> 00:38:48,820
pli de familio arbo, kie vi
havi iu praulo en la

910
00:38:48,820 --> 00:38:49,790
radikoj de la arbo.

911
00:38:49,790 --> 00:38:54,480
Al patriarkaj aŭ matriarca ĉe
la plejsupro de la arbo.

912
00:38:54,480 --> 00:38:56,700
Sen lia edzino, en tiu kazo.

913
00:38:56,700 --> 00:39:00,940
Sed ni havas nun kion ni nomas
infanoj, kiuj estas nodoj kiuj pendas

914
00:39:00,940 --> 00:39:05,480
ekstere la maldekstra infano aŭ la dekstra infano,
sagoj kiel reprezentita tie.

915
00:39:05,480 --> 00:39:10,490
>> En aliaj vortoj, en arba datumstrukturo
en komputilo, arbo havas nula

916
00:39:10,490 --> 00:39:11,480
aŭ pli nodoj.

917
00:39:11,480 --> 00:39:13,500
Se ĝi havas almenaŭ unu nodo,
kiuj nomiĝas la radiko.

918
00:39:13,500 --> 00:39:15,700
Ĝi estas la aĵoj vide ke
ni desegni ĉe la supro.

919
00:39:15,700 --> 00:39:20,280
Kaj tiu nodo, kiel ĉiu alia nodo, ĉu
havas nulo, unu, aŭ du, aŭ tri,

920
00:39:20,280 --> 00:39:23,600
aŭ tamen multaj infanoj la
datumstrukturo elportas.

921
00:39:23,600 --> 00:39:29,150
En tiu kazo, la radiko, stoki la
valoro, ĝi havas du filojn, 2 kaj 3,

922
00:39:29,150 --> 00:39:33,020
do ni ĝenerale nomas 2 maldekstren
infano kaj 3 la dekstra infano.

923
00:39:33,020 --> 00:39:36,940
>> Kaj poste kiam ni atingos suben ĝis 5, 6, kaj
7, 6 povus nomi la mezo infano.

924
00:39:36,940 --> 00:39:38,940
Se vi havas kvar infanojn,
metas konfuza.

925
00:39:38,940 --> 00:39:42,260
Do ni ĉesi uzi tian
de ŝparvojo parole.

926
00:39:42,260 --> 00:39:44,580
Sed estas vere nur familio arbo.

927
00:39:44,580 --> 00:39:48,880
Kaj la folioj tie estas la nodoj kiuj
mem ne havas infanoj.

928
00:39:48,880 --> 00:39:52,540
Ili pendas sur la malsupro de la arbo.

929
00:39:52,540 --> 00:39:56,940
>> Do kiel eble ni apliki arbo kiu
havas nur du infanoj maksimume?

930
00:39:56,940 --> 00:39:58,410
Ni nomas ĝin duuma arbo.

931
00:39:58,410 --> 00:40:00,960
Bi denove signifas du, en tiu
kazo, kiel kun binara.

932
00:40:00,960 --> 00:40:04,830
Kaj tial ĝi povas havi nulo, unu,
aŭ du infanoj maksimume.

933
00:40:04,830 --> 00:40:08,650
>> Mi proponas ke ni havas la nodo
por tiu strukturo kun int n,

934
00:40:08,650 --> 00:40:11,910
kaj tiam du montriloj, oni nomas
lasis, oni nomas prava.

935
00:40:11,910 --> 00:40:14,830
Sed tiuj estas nur bela
arbitrajn konvenciojn.

936
00:40:14,830 --> 00:40:18,170
Kaj kio estas bela nun, speciale se vi
speco de baraktis koncepte kun

937
00:40:18,170 --> 00:40:21,300
rekursio, aŭ pensis ke ne estis
vere solvon por nenion,

938
00:40:21,300 --> 00:40:23,120
precipe se vi povus
kuru el memoro.

939
00:40:23,120 --> 00:40:26,600
Nun, kiam ni parolas pri datumoj
strukturoj kaj algoritmoj kiuj permesas

940
00:40:26,600 --> 00:40:31,030
ni trairi kaj manipuli ilin,
rezultas ke rekursio revenas en

941
00:40:31,030 --> 00:40:34,240
multe pli konvinka
se ne bela vojo.

942
00:40:34,240 --> 00:40:38,670
>> Do tio mi proponas estas la efektivigo
de Serĉu funkcio.

943
00:40:38,670 --> 00:40:39,870
Donita du enigoj -

944
00:40:39,870 --> 00:40:41,570
tiel pensas pri ĉi tion kiel nigran skatolon.

945
00:40:41,570 --> 00:40:46,560
Donita du eniroj, n, an int, kaj
puntero al arbo, puntero al

946
00:40:46,560 --> 00:40:50,020
nodo, aŭ vere la radiko de arbo, mi
aserto, ke tiu funkcio povas reveni

947
00:40:50,020 --> 00:40:53,530
vera aŭ malvera, ke valoro n
estas ene de ĉi arbo.

948
00:40:53,530 --> 00:40:55,210
>> Kio estas ene de la nigra skatolo?

949
00:40:55,210 --> 00:40:57,440
Nu, kvar branĉoj.

950
00:40:57,440 --> 00:40:58,385
La unua nur kontrolas.

951
00:40:58,385 --> 00:41:00,490
Se arbo estas nula, nur redoni malvera.

952
00:41:00,490 --> 00:41:04,580
Se ne estas nodo, ne estas n,
ne estas nombro, nur redoni malvera.

953
00:41:04,580 --> 00:41:12,330
Se tamen, n, la valoro kiun vi sercxas
por, estas malpli ol arbo sago n, kaj

954
00:41:12,330 --> 00:41:15,180
nur por esti klara, kion tio signifas kiam
Mi skribas arbo kaj poste la sago

955
00:41:15,180 --> 00:41:18,150
notacio, n?

956
00:41:18,150 --> 00:41:18,690
Ekzakte.

957
00:41:18,690 --> 00:41:21,970
Ĝi signifas ke dereference
pointer nomata arbo.

958
00:41:21,970 --> 00:41:26,750
Iru tie, kaj poste ene de tiu
nodo kaj akiri lia kampo nomata n.

959
00:41:26,750 --> 00:41:30,810
Kaj poste kompari la aktualan n kiu estis
pasis al Serĉu kontraux gxi.

960
00:41:30,810 --> 00:41:35,390
>> Do se n estas malpli ol, la n valoro
en la arbo nodo mem, nu,

961
00:41:35,390 --> 00:41:36,720
kion tio signifas?

962
00:41:36,720 --> 00:41:40,690
Tio signifas nenion al unua vido.

963
00:41:40,690 --> 00:41:40,900
Ĝuste?

964
00:41:40,900 --> 00:41:45,560
Ĝuste kiel kiam vi havas aron da
valoroj, vi eble ŝatus apliki duuma

965
00:41:45,560 --> 00:41:48,290
serĉi kiel formo de divido
kaj venki.

966
00:41:48,290 --> 00:41:51,790
Sed kion supozo ni bezonas por fari
por duuma serĉo por labori en la tuta

967
00:41:51,790 --> 00:41:54,510
en la telefono libron kaj
antaŭaj ekzemploj?

968
00:41:54,510 --> 00:41:55,530
>> Kiel estu ordigita.

969
00:41:55,530 --> 00:41:59,490
Do ni rafini la difino de arbo
tie ne esti simple arbo, kiu povas

970
00:41:59,490 --> 00:42:00,880
havi ajnan numeron de infanoj.

971
00:42:00,880 --> 00:42:04,700
Ne nur duuma arbo, kiu povas
havi 0, 1, aŭ 2 maksimume.

972
00:42:04,700 --> 00:42:09,700
Sed kiel duuma serĉarbo, aŭ BST,
kiu estas nur imago maniero diri al

973
00:42:09,700 --> 00:42:15,430
duuma arbo tia, ke ĉiu nodo
maldekstra infano, se ĝi ĉeestas, estas

974
00:42:15,430 --> 00:42:16,830
malpli ol la nodo.

975
00:42:16,830 --> 00:42:20,170
Kaj cxiu nodo la dekstra infano,
se ĉeestas, estas pli granda

976
00:42:20,170 --> 00:42:21,740
ol la nodo mem.

977
00:42:21,740 --> 00:42:25,200
>> Do, en aliaj vortoj, se vi estus desegni
la arbo ekstere, ĉiuj de la nombroj estas

978
00:42:25,200 --> 00:42:30,620
atente balancis kiel ĉi tiel ke se
vi havas 55 kiel la radiko, 33 povas iri

979
00:42:30,620 --> 00:42:33,090
al lia maldekstra ĉar ĝi estas malpli ol 55.

980
00:42:33,090 --> 00:42:36,430
77 povas iri al lia dekstra ĉar
ĝi estas pli granda ol 55.

981
00:42:36,430 --> 00:42:40,750
Sed nun rimarkas, la sama difino,
ĝi estas rekursia difino parole,

982
00:42:40,750 --> 00:42:42,600
devas peti 33.

983
00:42:42,600 --> 00:42:47,610
33 la maldekstra infano devas esti malpli ol ĝi,
kaj 33 la dekstra infano, 44, devas esti

984
00:42:47,610 --> 00:42:48,580
pli granda ol ĝi.

985
00:42:48,580 --> 00:42:51,670
>> Do tiu estas duuma serĉo arbo, kaj
Mi proponas, uzante iomete da

986
00:42:51,670 --> 00:42:53,910
rekursio, ni povas nun trovi n.

987
00:42:53,910 --> 00:42:59,160
Do se n estas malpli ol la valoro n tio
nuna nodo, mi tuj iros

988
00:42:59,160 --> 00:43:04,090
antaŭeniris kaj liberigas, por tiel diri, kaj ĝuste
revenu ajn la respondo estas de

989
00:43:04,090 --> 00:43:08,470
serĉante n sur la
arbo maldekstra infano.

990
00:43:08,470 --> 00:43:11,370
Rimarku denove, ĉi tiu funkcio nur
atendas nodo stelo,

991
00:43:11,370 --> 00:43:12,780
puntero al nodo.

992
00:43:12,780 --> 00:43:17,360
Do certe mi povas nur faru arbo
sago maldekstren, kio kondukos

993
00:43:17,360 --> 00:43:18,400
mi al alia nodo.

994
00:43:18,400 --> 00:43:19,480
Sed kio estas tiu nodo?

995
00:43:19,480 --> 00:43:22,820
>> Nu, laŭ ĉi tiu deklaro,
maldekstra estas nur referenco, tiel ke nur

996
00:43:22,820 --> 00:43:27,090
signifas Mi pasante al la serĉo funkcio
malsama pointer, nome

997
00:43:27,090 --> 00:43:30,750
kiu reprezentas
mia maldekstra infano arbo.

998
00:43:30,750 --> 00:43:36,040
Do, en tiu kazo, la puntero al 33, se
tio estas nia specimeno enigo Dume, se

999
00:43:36,040 --> 00:43:40,740
n estas pli granda ol la valoro n je la
nuna nodo en la arbo, tiam mi estas

1000
00:43:40,740 --> 00:43:43,370
tuj iros antaŭen kaj liberigas en la alia
direkto kaj nur diru, mi ne

1001
00:43:43,370 --> 00:43:47,280
scii se tiu valoro n estas en la arbo,
sed mi scias se ĝi estas, ĝi estas sube mia

1002
00:43:47,280 --> 00:43:49,090
dekstra branĉo, por tiel diri.

1003
00:43:49,090 --> 00:43:53,120
Do lasu min vokas: rekursie esplori,
pasante n denove, sed pasante en

1004
00:43:53,120 --> 00:43:54,580
puntero al mia dekstra infano.

1005
00:43:54,580 --> 00:44:00,020
>> En aliaj vortoj, se mi estas aktuale ĉe 55
kaj Mi serĉas 99 Mi scias, ke 99

1006
00:44:00,020 --> 00:44:04,270
estas pli granda ol 55, do ĝuste kiel mi disŝiris
la telefono libro semajnoj kaj ni

1007
00:44:04,270 --> 00:44:07,140
iris dekstren, simile ni estas
tuj iros ĉi tie.

1008
00:44:07,140 --> 00:44:11,960
Kaj mi ne scias se ĝi estas ĉe mia dekstra
infano, kaj ĝi ne estas, 77 estas tie, sed

1009
00:44:11,960 --> 00:44:13,210
Mi scias ke estas en tiu direkto.

1010
00:44:13,210 --> 00:44:18,770
Do mi nomas serĉu per mia dekstra infano,
77, kaj lasu serĉo figuro el

1011
00:44:18,770 --> 00:44:24,950
tie se 99 en tiu arbitra
Ekzemplo estas efektive tie.

1012
00:44:24,950 --> 00:44:26,900
>> Alie, kio estas la fina kazo?

1013
00:44:26,900 --> 00:44:28,620
Se arbo estas nula estas unu kazo.

1014
00:44:28,620 --> 00:44:31,890
Se n estas malpli ol la aktuala nodo
valoro estas alia kazo.

1015
00:44:31,890 --> 00:44:35,120
Se n estas pli granda ol la aktuala
nodo valoro estas tria kazo.

1016
00:44:35,120 --> 00:44:38,250
Kio estas la kvara kaj lasta kazo?

1017
00:44:38,250 --> 00:44:39,480
Mi kredas ke ni estas el kazoj, ĉu ne?

1018
00:44:39,480 --> 00:44:44,690
Devas esti ke n estas en la
nuna nodo ke mi estas sur.

1019
00:44:44,690 --> 00:44:49,640
>> Do se mi sercxas 55 je ĉi tiu punkto
en la rakonto, tiu branĉo de la

1020
00:44:49,640 --> 00:44:51,780
arbo revenus vera.

1021
00:44:51,780 --> 00:44:55,380
Do kio estas interesa estas, ke ni
fakte, kontraste semajnoj pasis, ni speco

1022
00:44:55,380 --> 00:44:56,740
de havi du bazo kazoj.

1023
00:44:56,740 --> 00:44:58,300
Kaj oni ne devas
estu ĉiuj ĉe la supro.

1024
00:44:58,300 --> 00:45:01,390
La supro estas bazo kazo ĉar se la
arbo estas nula, estas nenio por fari.

1025
00:45:01,390 --> 00:45:03,410
Nur reveni malmola kodita
valoro de falsaj.

1026
00:45:03,410 --> 00:45:07,400
>> La fundo branĉo estas varo de la
implicite, per kiu, se ni kontrolis por

1027
00:45:07,400 --> 00:45:11,550
nula, ni kontrolis se ĝi devus esti
forlasis, sed gxi ne, ni

1028
00:45:11,550 --> 00:45:14,640
kontrolis se ĝi devus esti bone, sed
ne devus esti, klare ĝi devas esti

1029
00:45:14,640 --> 00:45:15,870
ĝuste kie ni estas.

1030
00:45:15,870 --> 00:45:16,780
Tio estas baza kazo.

1031
00:45:16,780 --> 00:45:19,920
Do ekzistas du rekursiaj kazoj
sandwiched tie en la mezo.

1032
00:45:19,920 --> 00:45:21,630
Sed mi povus esti skribita
tiu en ajna ordo.

1033
00:45:21,630 --> 00:45:24,520
Mi nur pensis ke speco de sentis natura
unue kontroli por ebla eraro,

1034
00:45:24,520 --> 00:45:28,340
tiam kontrolu restis, tiam kontrolu pravas, tiam
supozu ke vi estas en la nodo

1035
00:45:28,340 --> 00:45:30,630
vi fakte serĉas.

1036
00:45:30,630 --> 00:45:36,240
>> Do kial cxu tio estos utila?

1037
00:45:36,240 --> 00:45:37,910
Do rezultas -

1038
00:45:37,910 --> 00:45:42,110
kaj mi saltas al teaser
tie estas en la TTT.

1039
00:45:42,110 --> 00:45:44,920
Ni tuj ekuzi ne
plani lingvon unue, sed

1040
00:45:44,920 --> 00:45:46,030
markado lingvo.

1041
00:45:46,030 --> 00:45:48,740
Al HTML lingvon estante unu tio estas
simila en spirito programado

1042
00:45:48,740 --> 00:45:51,715
lingvo, sed ĝi ne donas al vi la
kapablo esprimi sin logike.

1043
00:45:51,715 --> 00:45:55,070
Ĝi nur donas al vi la kapablon
esprimi sin strukture.

1044
00:45:55,070 --> 00:45:57,960
>> Kie vi volas meti ion
en la paĝo, la retpaĝo?

1045
00:45:57,960 --> 00:45:59,200
Kian koloron vi volas fari ĝin?

1046
00:45:59,200 --> 00:46:00,950
Kio tiparo vi volas fari ĝin?

1047
00:46:00,950 --> 00:46:02,970
Kio vortoj ĉu vi vere
volas en la retpaĝo?

1048
00:46:02,970 --> 00:46:04,060
Do tio estas markado lingvo.

1049
00:46:04,060 --> 00:46:07,690
Sed tiam ni devos tre rapide enkonduki
Javascript, kiu estas plene disvolviĝinta

1050
00:46:07,690 --> 00:46:08,560
programado lingvo.

1051
00:46:08,560 --> 00:46:12,530
Tre simila sintakse laŭ aspekto
al C, sed havos iujn

1052
00:46:12,530 --> 00:46:15,200
bela, pli potenca, pli
uzanto amika karakterizaĵoj.

1053
00:46:15,200 --> 00:46:18,050
>> Kaj unu el la frustroj en ĉi
punkto en la semestro estas ke ni instruos vin

1054
00:46:18,050 --> 00:46:22,065
frue apliki Speller en multe malpli da
linioj de kodo uzante aliajn lingvojn

1055
00:46:22,065 --> 00:46:25,580
ol C mem permesas, sed por kialo estas
ni baldaŭ komprenis.

1056
00:46:25,580 --> 00:46:27,750
Tiu estos la unua tia retpaĝo.

1057
00:46:27,750 --> 00:46:30,120
Ĝi estos tute underwhelming,
la unua ni faras.

1058
00:46:30,120 --> 00:46:31,400
Ĝi simple diri, saluton mondo.

1059
00:46:31,400 --> 00:46:34,010
Sed se vi neniam vidis ĝin
antaŭe, tio estas HTML,

1060
00:46:34,010 --> 00:46:35,670
Hiperteksto Markup Language.

1061
00:46:35,670 --> 00:46:39,310
>> Se vi iras al iu menuo opcion en
plej ajna retumilo, en ajna retpaĝo sur

1062
00:46:39,310 --> 00:46:43,160
interreto, vi povos vidi la HTML
ke iu homo skribis al

1063
00:46:43,160 --> 00:46:44,400
krei tiun ĉi paĝon.

1064
00:46:44,400 --> 00:46:47,850
Kaj probable ne aspektas kiel
mallonga aŭ neta kiel ĉi tio.

1065
00:46:47,850 --> 00:46:51,400
Sed ĝi sekvos la modelon de ĉi tiuj
malfermita krampoj kaj slashes kaj

1066
00:46:51,400 --> 00:46:53,660
literoj kaj potenciale nombroj.

1067
00:46:53,660 --> 00:46:56,770
>> Mi pensis, ke mi volas doni al vi teaser
kion vi povos fari

1068
00:46:56,770 --> 00:46:57,950
post preni CS50.

1069
00:46:57,950 --> 00:47:02,620
Permesu al mi iri al cs.harvard.edu / ŝteli,
nia propra Rob Bowden la hejmpaĝo.

1070
00:47:02,620 --> 00:47:06,080
Li faris tion por ni.

1071
00:47:06,080 --> 00:47:07,490
Do vi baldaux povos fari tion.

1072
00:47:07,490 --> 00:47:10,660
Kaj ankaŭ, kion vi aŭdis
ĉi-matene -

1073
00:47:10,660 --> 00:47:12,480
kion vi auxdis tiun matenon -

1074
00:47:12,480 --> 00:47:13,780
>> [Hamstro DANCU MUZIKO]

1075
00:47:13,780 --> 00:47:15,702
>> - You'll povos fari tion.

1076
00:47:15,702 --> 00:47:16,790
Ke atendas nin je merkredo.

1077
00:47:16,790 --> 00:47:17,791
Ni vidos vin tiam.

1078
00:47:17,791 --> 00:47:22,950
>> [Hamstro DANCU MUZIKO]

1079
00:47:22,950 --> 00:47:24,300
DAVID Malan: Je la sekvanta CS50 -

1080
00:47:24,300 --> 00:47:31,670