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

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

3
00:00:12,250 --> 00:00:13,860
Dobrodošli nazaj v CS50.

4
00:00:13,860 --> 00:00:16,190
To je začetek 8. tednu.

5
00:00:16,190 --> 00:00:21,320
In opozarjajo, da problem set 5 končalo
z malo izziv.

6
00:00:21,320 --> 00:00:25,210
Torej, ob predpostavki, da izterja vse vaše
poučevanje Fellows in fotografije CA

7
00:00:25,210 --> 00:00:30,480
v datoteki card.raw, ste upravičeni
za zdaj našli vse te ljudi, in

8
00:00:30,480 --> 00:00:34,510
en srečen zmagovalec bo hodil domov z enim
od teh stvari, skok predlog

9
00:00:34,510 --> 00:00:37,450
Naprava, ki jo lahko uporabite za končno
projekti, na primer.

10
00:00:37,450 --> 00:00:39,860
>> To, vsako leto vodi
malo creepiness.

11
00:00:39,860 --> 00:00:43,480
Pa kaj sem mislil, da sem naredil, je delež
z vami nekaj opomb, ki imajo

12
00:00:43,480 --> 00:00:47,370
šli naprej in nazaj
Seznam osebja prepozno.

13
00:00:47,370 --> 00:00:51,110
Na primer, samo sinoči citatom
citata iz ene osebja

14
00:00:51,110 --> 00:00:55,000
člani, "sem imel študentsko trkanje
na moja vrata, da posnamete fotografijo z mano.

15
00:00:55,000 --> 00:00:59,020
Zalezovalci, vam povem. "Začelo
precej opisna in potem smo se preselili

16
00:00:59,020 --> 00:01:02,830
na, uro ali tako kasneje, "Imel sem
Študent me čaka po oddelku

17
00:01:02,830 --> 00:01:06,080
in je imel vse naše imena in fotografije
na nekaj listov papirja. "Vse je v redu.

18
00:01:06,080 --> 00:01:09,230
Tako organizirana, vendar ne
vse to grozljivo še ni.

19
00:01:09,230 --> 00:01:12,520
>> Potem, "sem bil iz mesta ta vikend,
in ko sem se vrnil, je bil eden od

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

21
00:01:12,630 --> 00:01:16,740
spalnica. "[SMEH]

22
00:01:16,740 --> 00:01:20,410
DAVID Malan: Naslednji citat iz osebja
član, "študent prišel v mojo hišo na

23
00:01:20,410 --> 00:01:25,330
Somerville ob 4:00 zjutraj. "Next
Osebje, "sem prišel do mojega hotela v San

24
00:01:25,330 --> 00:01:30,016
Francisco in študent je čakala
me je v preddverju s tremi dslr. "

25
00:01:30,016 --> 00:01:31,510
Vrsta fotoaparata.

26
00:01:31,510 --> 00:01:34,980
"Nisem niti za zaposlene ta semester,
ampak študent je vlomil v mojo hišo to

27
00:01:34,980 --> 00:01:40,480
zjutraj in posnel celotno stvar
z Google Glass. "In potem končno,

28
00:01:40,480 --> 00:01:43,650
"Vsaj 12 ljudi, ki so nestrpno
čaka za mene, ko sem prišel iz mojega

29
00:01:43,650 --> 00:01:44,800
limuzina, nato pa sem

30
00:01:44,800 --> 00:01:46,970
zbudil. "V redu.

31
00:01:46,970 --> 00:01:57,690
Torej med slikami, kot si lahko
spomnim, je ta človek tukaj, kdo ste

32
00:01:57,690 --> 00:02:01,850
Morda veste, kot Milo Banana, ki živi
z Lauren Carvalho, naše glave

33
00:02:01,850 --> 00:02:02,905
poučevanje člana.

34
00:02:02,905 --> 00:02:05,170
Milo, Milo, pridi sem fant.

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
Misli si, on je nosil Google steklo, tako da
vam bomo pokazali vse to potem.

38
00:02:12,230 --> 00:02:16,190
Torej, to je Milo, če bi želeli
slikati z njim kasneje.

39
00:02:16,190 --> 00:02:18,240
Če želite, da pazi
na občinstvo tam.

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

41
00:02:19,430 --> 00:02:20,200
To je dober posnetek.

42
00:02:20,200 --> 00:02:22,556
No, Milo Banana.

43
00:02:22,556 --> 00:02:23,941
Oh, ne delaj tega.

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

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

46
00:02:29,470 --> 00:02:34,550
Torej besedo, potem o tem, kaj je pred nami,
saj, kot smo začeli prehod,

47
00:02:34,550 --> 00:02:38,410
ta teden posebej od C pri
ukazni vrstici okolja v PHP, in

48
00:02:38,410 --> 00:02:42,720
JavaScript ter SQL in HTML in CSS v
okolje spleta, bomo

49
00:02:42,720 --> 00:02:44,490
vam opremljanje z vsemi
Več znanja za

50
00:02:44,490 --> 00:02:46,010
potencialnih končnih projektov.

51
00:02:46,010 --> 00:02:49,240
V ta namen so, seveda ima
tradicija seminarjev, ki

52
00:02:49,240 --> 00:02:50,950
so na dotikajo teme
v teku.

53
00:02:50,950 --> 00:02:54,330
Zelo povezana z načrtovanjem in
Razvoj app in tako naprej, vendar

54
00:02:54,330 --> 00:02:57,010
ni nujno proučiti
Tečaj lastne učni načrt.

55
00:02:57,010 --> 00:03:00,250
>> Torej, če vas bo morda zanima ena
ali več od letošnjih seminarjev,

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

57
00:03:02,530 --> 00:03:06,170
Obstajajo starejši seminarji
ob cs50.net/seminars.

58
00:03:06,170 --> 00:03:10,620
In na roster doslej za to leto
so Amazing Web Apps z Ruby na

59
00:03:10,620 --> 00:03:13,580
Tirnice, ki je alternativa
jezik za PHP.

60
00:03:13,580 --> 00:03:14,900
Computational Linguistics.

61
00:03:14,900 --> 00:03:18,710
Uvod v iOS, ki je
platforma, ki se uporabljajo za iPhone in

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

63
00:03:19,850 --> 00:03:22,890
Javascript za Web Apps bomo zajema
da, vendar v tem seminarju, boš šel

64
00:03:22,890 --> 00:03:24,070
bolj v podrobnosti.

65
00:03:24,070 --> 00:03:27,390
>> Predlog preskok, tako da bomo dejansko imeli nekaj
naših prijateljev iz Leap Motion,

66
00:03:27,390 --> 00:03:29,160
družba sama, se nam pridružite.

67
00:03:29,160 --> 00:03:31,800
Jutri, v resnici, da zagotovi
hands-on seminarju, če

68
00:03:31,800 --> 00:03:33,320
, ki vas zanimajo.

69
00:03:33,320 --> 00:03:38,770
Meteor.js, alternativna tehnika
uporabljajo JavaScript ni v brskalniku

70
00:03:38,770 --> 00:03:39,970
ampak na strežniku.

71
00:03:39,970 --> 00:03:42,110
Node.js, ki je zelo
v tej smeri, kot tudi.

72
00:03:42,110 --> 00:03:43,650
Tanko Android dizajn.

73
00:03:43,650 --> 00:03:46,990
Android pa zelo priljubljena alternativa
za iOS in Windows Phone

74
00:03:46,990 --> 00:03:48,790
in druge mobilne platforme.

75
00:03:48,790 --> 00:03:51,180
In Web Security Active Defense.

76
00:03:51,180 --> 00:03:54,590
>> Torej, v bistvu, če bi želeli
da se vključijo v to, kaj mi

77
00:03:54,590 --> 00:03:55,840
zapomnite si to.

78
00:03:55,840 --> 00:03:57,790
Zelo smo veseli, da rečemo, da
Naši prijatelji Prestopna

79
00:03:57,790 --> 00:03:59,140
Predlog, ki je ob zagonu -

80
00:03:59,140 --> 00:04:01,300
ta naprava res samo prišel
pred nekaj meseci -

81
00:04:01,300 --> 00:04:05,960
je milostno daroval 30 takih naprav
v razredu za toliko študentov, če

82
00:04:05,960 --> 00:04:08,670
bi radi, da se zadolži strojne opreme
proti koncu semestra in jo uporabite za

83
00:04:08,670 --> 00:04:10,390
Dejanski končni projekt.

84
00:04:10,390 --> 00:04:11,890
Jih podpirajo več jezikov.

85
00:04:11,890 --> 00:04:16,040
Nobena od njih C, nobena od njih PHP, tako
dosego enega ali več od teh seminarjev

86
00:04:16,040 --> 00:04:16,899
lahko izkaže interesa.

87
00:04:16,899 --> 00:04:19,730
In vse od njih bo posnet v
V primeru, da ne boste mogli

88
00:04:19,730 --> 00:04:21,380
udeležiti osebno.

89
00:04:21,380 --> 00:04:25,000
Načrt je napovedal preko
email, kot smo strdi sobe.

90
00:04:25,000 --> 00:04:28,460
>> In nenazadnje, če greš na
projects.cs.50.net, to je spletna stran

91
00:04:28,460 --> 00:04:31,450
trdimo, da je vsako leto povabimo
ljudje iz skupnosti, fakultete,

92
00:04:31,450 --> 00:04:36,420
oddelki, osebje, in obe
v zunanji CS50 do

93
00:04:36,420 --> 00:04:37,730
predlagala projektne ideje.

94
00:04:37,730 --> 00:04:39,050
Stvari, ki so v interesu študentskih skupin.

95
00:04:39,050 --> 00:04:40,600
Stvari, ki so v interesu službe.

96
00:04:40,600 --> 00:04:43,990
Torej, ne pa tam, če ste se borijo
z negotovostjo glede tega, kaj

97
00:04:43,990 --> 00:04:46,700
si želi lotiti.

98
00:04:46,700 --> 00:04:51,760
>> Torej zadnjič, ko smo uvedli verjetno
bolj zapletena struktura podatkov, kot sva

99
00:04:51,760 --> 00:04:53,300
videli v zadnjih tednih.

100
00:04:53,300 --> 00:04:56,550
Mi bi bili z uporabo nizov precej
srečno kot koristno, če

101
00:04:56,550 --> 00:04:58,160
poenostavljeno strukturo podatkov.

102
00:04:58,160 --> 00:05:00,570
Potem smo uvedli ti, ki
Seveda so povezane sezname.

103
00:05:00,570 --> 00:05:05,470
In tisto, kar je bil eden od motivov za
uveljavitvijo te podatkovne strukture?

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

105
00:05:06,930 --> 00:05:07,250
Kaj je to?

106
00:05:07,250 --> 00:05:08,080
>> PUBLIKA: Dynamic velikost.

107
00:05:08,080 --> 00:05:09,040
>> DAVID Malan: Dynamic velikost.

108
00:05:09,040 --> 00:05:11,890
Torej, medtem ko je v polju, morate
vem, njeno velikost predplačila, kadar

109
00:05:11,890 --> 00:05:12,740
jo dodeli.

110
00:05:12,740 --> 00:05:14,380
V povezano seznamu, pa ne
vedeti, da.

111
00:05:14,380 --> 00:05:17,610
Lahko samo malloc, ali bolj na splošno,
dodeli dodatna

112
00:05:17,610 --> 00:05:20,720
vozlišče, tako rekoč kadarkoli
želite vnesti več podatkov.

113
00:05:20,720 --> 00:05:22,670
In vozlišče ni vnaprej določen pomen.

114
00:05:22,670 --> 00:05:25,580
To je samo splošen izraz, ki opisuje
nekakšen posodi, ki smo

115
00:05:25,580 --> 00:05:29,610
uporabo v našem podatkovne strukture za shranjevanje
nekatere element interesa, ki v tem

116
00:05:29,610 --> 00:05:31,750
primer zgodi, da bo cela.

117
00:05:31,750 --> 00:05:33,160
>> Ampak tam je vedno kompromis.

118
00:05:33,160 --> 00:05:38,070
Tako smo dobili dinamične velikosti podatkov
strukture, ampak kakšno ceno bomo plačali?

119
00:05:38,070 --> 00:05:40,040
Kaj je slaba stran povezanih seznamov?

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

121
00:05:41,006 --> 00:05:41,980
>> PUBLIKA: zahteva več pomnilnika.

122
00:05:41,980 --> 00:05:44,240
>> DAVID Malan: To zahteva več
spomin, kako točno?

123
00:05:44,240 --> 00:05:46,440
>> PUBLIKA: [neslišno].

124
00:05:46,440 --> 00:05:47,050
>> DAVID Malan: Točno tako.

125
00:05:47,050 --> 00:05:50,460
Torej, zdaj smo kazalci prevzemu
Dodatni spomin, da smo v preteklosti

126
00:05:50,460 --> 00:05:53,040
ni potrebno, ker prednost
v matriki, seveda, da

127
00:05:53,040 --> 00:05:54,860
vse je stikata, nazaj
nazaj na hrbtu, ki

128
00:05:54,860 --> 00:05:56,380
vam naključni dostop.

129
00:05:56,380 --> 00:06:00,710
Ker samo z uporabo kvadratnega nosilec
Zapis, ali bolj tehnično kazalec

130
00:06:00,710 --> 00:06:03,580
aritmetika, zelo preprost dodatek,
lahko dostopate do katere koli

131
00:06:03,580 --> 00:06:05,700
elementi v enakem času.

132
00:06:05,700 --> 00:06:08,975
In v resnici, da je nekako namiguje na
še cena, ki smo si plačal z

133
00:06:08,975 --> 00:06:09,760
povezani seznam.

134
00:06:09,760 --> 00:06:13,890
>> Kaj se zgodi, da v času poteka
nekaj podobnega Search, če želim

135
00:06:13,890 --> 00:06:17,270
našli nekaj vrednosti in notranjost
v povezanem seznamu?

136
00:06:17,270 --> 00:06:20,290
Kaj mi teče čas postali?

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

138
00:06:21,560 --> 00:06:24,060
Če je to urejeno za?

139
00:06:24,060 --> 00:06:25,440
Kaj pa, če je struktura podatkov razporejene?

140
00:06:25,440 --> 00:06:28,640
Lahko naredim bolje kot velika
O n za iskanje?

141
00:06:28,640 --> 00:06:31,700
Ne, ker v najslabšem primeru bi lahko bilo
zelo dobro rešiti, število

142
00:06:31,700 --> 00:06:32,950
iščete lahko velik.

143
00:06:32,950 --> 00:06:35,370
Morda je številka 100, ki
se lahko zgodi, da bo vse

144
00:06:35,370 --> 00:06:36,410
Tako na koncu.

145
00:06:36,410 --> 00:06:39,950
In zato, ker lahko le dostop povezano
Seznam v tem izvajanju, ki jih

146
00:06:39,950 --> 00:06:42,690
način svojega prvega vozlišča, si
Še vedno nekako od sreče.

147
00:06:42,690 --> 00:06:47,450
Moraš prečkala celotno stvar
od prve do zadnje, da bi našli

148
00:06:47,450 --> 00:06:49,150
da je velika vrednost kot 100..

149
00:06:49,150 --> 00:06:51,350
Ali ugotoviti, če je to
sploh ne obstaja.

150
00:06:51,350 --> 00:06:55,960
>> Torej ne moremo storiti kaj algoritem v podatkovnem
struktura, ki je videti takole?

151
00:06:55,960 --> 00:06:59,460
Tega ne moremo narediti binarno iskanje, saj
binarno iskanje potrebno, da smo imeli

152
00:06:59,460 --> 00:07:00,740
random access.

153
00:07:00,740 --> 00:07:04,500
Mi lahko samo preskok od lokacije do
mesto brez nadaljnje

154
00:07:04,500 --> 00:07:07,080
ti krušnih drobtin v obliki
vseh teh kazalcev.

155
00:07:07,080 --> 00:07:08,300
>> Zdaj, kako smo izvajati to?

156
00:07:08,300 --> 00:07:12,830
No, če gremo na zaslonu tukaj, če
bomo lahko hitro reimplement te podatke

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

158
00:07:13,440 --> 00:07:15,670
moj rokopis še ni vse, da je
super tukaj, ampak bomo poskušali.

159
00:07:15,670 --> 00:07:22,030
Torej typedef struct, in kaj sem
želite poklicati to stvar tukaj gor?

160
00:07:22,030 --> 00:07:22,960
Vozlišče.

161
00:07:22,960 --> 00:07:24,580
Tako da bom naju začel.

162
00:07:24,580 --> 00:07:27,860
In zdaj, kaj mora biti znotraj
Struktura podatkov za to posamezno

163
00:07:27,860 --> 00:07:28,430
povezani seznam?

164
00:07:28,430 --> 00:07:29,950
Koliko polja?

165
00:07:29,950 --> 00:07:30,450
>> Torej dva.

166
00:07:30,450 --> 00:07:31,570
Ena je zelo enostavno.

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

168
00:07:33,050 --> 00:07:35,930
In lahko rečemo n karkoli hočemo,
vendar mora biti int, če smo

169
00:07:35,930 --> 00:07:37,660
izvajanje povezan seznam za ints.

170
00:07:37,660 --> 00:07:41,920
In kaj zdaj počne drugega
polja morajo biti?

171
00:07:41,920 --> 00:07:43,460
Struct vozlišče *.

172
00:07:43,460 --> 00:07:50,570
Torej, če naredim struct vozlišče *, potem pa sem
To lahko pokličete tudi kar hočem,

173
00:07:50,570 --> 00:07:53,510
ampak samo, da je jasno, bom poklicala
je naslednji korak, saj smo počeli.

174
00:07:53,510 --> 00:07:55,270
In potem bom zaprem zavite oklepaje.

175
00:07:55,270 --> 00:08:00,700
>> In zdaj, kot zadnjič,
Sem dal vozlišče tukaj.

176
00:08:00,700 --> 00:08:03,830
Ampak, če sem to razglasitvi je kot
vozlišče, zakaj se sploh trudim, da tako

177
00:08:03,830 --> 00:08:07,320
verbose tukaj razglasitvi Struct
vozlišče * naslednji, v nasprotju

178
00:08:07,320 --> 00:08:09,210
na samo vozlišče * naslednji?

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

180
00:08:09,904 --> 00:08:12,810
>> PUBLIKA: [neslišno].

181
00:08:12,810 --> 00:08:14,050
>> DAVID Malan: Točno tako.

182
00:08:14,050 --> 00:08:14,530
Točno tako.

183
00:08:14,530 --> 00:08:18,320
Ker C res vas popelje dobesedno in
vidi le opredelitev vozlišča

184
00:08:18,320 --> 00:08:21,230
Tako sem dol, ne smeš
Če ga želite videti tukaj.

185
00:08:21,230 --> 00:08:24,760
Torej imamo te vrste preemptive
Izjava tukaj, ki je sicer

186
00:08:24,760 --> 00:08:25,390
bolj verbose.

187
00:08:25,390 --> 00:08:27,810
Struct vozlišča, kar pomeni, da
sedaj lahko dostopate do

188
00:08:27,810 --> 00:08:29,760
znotraj strukture podatkov.

189
00:08:29,760 --> 00:08:33,370
>> In stran, ker je to
postane malo bolj subjektivna zdaj,

190
00:08:33,370 --> 00:08:36,230
zvezda lahko tehnično iti tukaj,
da lahko gredo tu, lahko pa

191
00:08:36,230 --> 00:08:37,179
celo iti v sredini.

192
00:08:37,179 --> 00:08:39,890
Sprejeli smo v slogu priročnika za
Tečaj, konvencija dajanje

193
00:08:39,890 --> 00:08:42,299
zvezda tik podatkov
vrste, ki je v tem primeru

194
00:08:42,299 --> 00:08:43,460
bi struct vozlišče.

195
00:08:43,460 --> 00:08:46,620
Ampak uresničiti v veliko učbenikov in
spletne reference, boste morda celo

196
00:08:46,620 --> 00:08:48,450
ga vidimo na drugi strani.

197
00:08:48,450 --> 00:08:52,200
Ampak samo zavedati, da bo tako dejansko
delo in bi morali biti zgolj

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

199
00:08:52,970 --> 00:08:53,580
>> Vse je v redu.

200
00:08:53,580 --> 00:08:55,630
Tako da je bila naša izjava
od struct vozlišča.

201
00:08:55,630 --> 00:08:59,430
Ampak potem smo začeli delaš več
prefinjene stvari.

202
00:08:59,430 --> 00:09:03,410
Na primer, smo se odločili, da uvedejo
nekaj podobnega hash tabelo.

203
00:09:03,410 --> 00:09:08,160
Torej, tukaj je razpršena tabela velikosti n,
indeksirane od 0 na vrhu levo do n

204
00:09:08,160 --> 00:09:09,690
minus 1 na dnu levo.

205
00:09:09,690 --> 00:09:11,640
To bi lahko hash
miza za karkoli.

206
00:09:11,640 --> 00:09:15,340
Ampak kaj vrste stvari nismo govorili
o uporabi razpršene tabele za?

207
00:09:15,340 --> 00:09:18,370
Shranjevanje kaj?

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

209
00:09:18,800 --> 00:09:20,870
Mi lahko storite imena, kot so
sva zadnjič.

210
00:09:20,870 --> 00:09:22,200
In res, lahko shranite ničesar.

211
00:09:22,200 --> 00:09:24,640
In bomo to spet videli v
PHP in JavaScript.

212
00:09:24,640 --> 00:09:28,550
Razpršene tabele je lepo nekakšen švicarski
Nož, ki vam omogoča, da shranite

213
00:09:28,550 --> 00:09:33,690
precej karkoli hočeš v notranjosti
je s povezovanjem ključe z vrednostmi.

214
00:09:33,690 --> 00:09:34,770
Tipke z vrednostmi.

215
00:09:34,770 --> 00:09:37,800
>> Zdaj v tem preprostem primeru, naša
Tipke so samo številke.

216
00:09:37,800 --> 00:09:40,380
Mi izvajanje hash
miza kot niz.

217
00:09:40,380 --> 00:09:43,500
In tako so tipke 0,
1, 2, in tako naprej.

218
00:09:43,500 --> 00:09:47,200
In tako mi, kot ljudje, odločila zadnja
teden, da veš kaj, če smo

219
00:09:47,200 --> 00:09:50,410
bo trgovina imen, kaj je samo
samovoljno, ampak precej razumno,

220
00:09:50,410 --> 00:09:54,680
Predvidevam, da Alice, ime,
bo samo indeksirane v 0.

221
00:09:54,680 --> 00:09:58,030
Bob, ime B, bo indeksirana
v 1, in tako naprej.

222
00:09:58,030 --> 00:10:02,490
Tako smo imeli preslikavo med vhodi,
ki so nizi in razpršitve

223
00:10:02,490 --> 00:10:04,560
Mesta, ki so številke.

224
00:10:04,560 --> 00:10:07,740
>> Tako se ta postopek splošno znana kot
hash funkcija, in lahko resnično

225
00:10:07,740 --> 00:10:09,130
je v kodi izvajati.

226
00:10:09,130 --> 00:10:12,080
Če bi želel izvajati funkcijo razpršitve
da počne točno to, kar smo

227
00:10:12,080 --> 00:10:17,070
pravkar opisal v zadnjem času, morda sem
razglasi funkcijo, ki bo, kot je

228
00:10:17,070 --> 00:10:18,330
vhod na primer -

229
00:10:18,330 --> 00:10:22,190
in dajmo to narediti na tem
Zaslon tukaj.

230
00:10:22,190 --> 00:10:26,180
Če bi želel izvajati hašiš
funkcijo, bi lahko rekel

231
00:10:26,180 --> 00:10:27,410
kaj takega.

232
00:10:27,410 --> 00:10:29,030
>> To se dogaja, da se vrnete int.

233
00:10:29,030 --> 00:10:33,600
To se dogaja, da se imenuje hašiš, in to je
bodo sprejeti kot argument

234
00:10:33,600 --> 00:10:38,920
niz, ali smo lahko bolj pravilno zdaj,
in pravijo, char *, bomo pa s poklicati.

235
00:10:38,920 --> 00:10:43,840
In potem vse to funkcijo mora storiti,
na koncu se vrne int.

236
00:10:43,840 --> 00:10:45,990
Zdaj, kako to počne, da bi lahko
Ne bodi tako jasna.

237
00:10:45,990 --> 00:10:49,510
Jaz grem za izvajanje tega brez
Oblika preverjanja napake zdaj.

238
00:10:49,510 --> 00:10:55,740
Grem na slepo reči, vrnitev
vse, kar je v nosilcem S 0, minus,

239
00:10:55,740 --> 00:10:58,850
recimo, kapital podpičjem.

240
00:10:58,850 --> 00:10:59,960
>> Popolnoma zlomljen.

241
00:10:59,960 --> 00:11:02,620
To ni popoln, saj
eno, kaj pa če je ničen?

242
00:11:02,620 --> 00:11:04,000
Slabe stvari se bo zgodilo.

243
00:11:04,000 --> 00:11:07,940
Dva, kaj če prva črka v tem
Ime ni začetnico?

244
00:11:07,940 --> 00:11:09,860
To ne bo obrniti
iz vrtin.

245
00:11:09,860 --> 00:11:11,970
Morda bi bilo male črke
ali ne, pismo sploh.

246
00:11:11,970 --> 00:11:15,520
Torej povsem dovolj prostora za izboljšave tukaj
ampak to je osnovna ideja.

247
00:11:15,520 --> 00:11:19,010
>> Kaj smo ustno opisal zadnji teden
samo proces kartiranje Alice v

248
00:11:19,010 --> 00:11:23,360
0 in Bob 1, se lahko izrazi
Vsekakor bolj formulaically kot C

249
00:11:23,360 --> 00:11:24,320
deluje tukaj.

250
00:11:24,320 --> 00:11:28,630
Je znova poklical hašiš, je niz kot
vložek, nato pa nekako ne nekaj

251
00:11:28,630 --> 00:11:31,020
s tem input za proizvodnjo izhod.

252
00:11:31,020 --> 00:11:34,130
Ni za razliko od naše črne opis box
da smo dolgo storili.

253
00:11:34,130 --> 00:11:36,550
Ne vem, kako bi to lahko bilo
delajo pod pokrovom.

254
00:11:36,550 --> 00:11:40,120
>> Problematičnega set 6, enega izmed izzivov
je za vas, da odloči, kaj

255
00:11:40,120 --> 00:11:41,920
bo vaš hash funkcija je?

256
00:11:41,920 --> 00:11:45,760
Kaj se dogaja, da se notranjost da črna
polje, in verjetno, da bo

257
00:11:45,760 --> 00:11:50,380
malo bolj zanimivo, kot je ta, in
vsekakor bolj nagnjeni k napakam

258
00:11:50,380 --> 00:11:53,180
preverjanje, kot to predvsem
izvajanje.

259
00:11:53,180 --> 00:11:54,580
>> Vendar težave lahko nastopijo, kajne?

260
00:11:54,580 --> 00:11:57,760
Če imamo podatkovno strukturo, kot je to
ena, kar je eden od problemov

261
00:11:57,760 --> 00:12:01,600
lahko vodijo v daljšem časovnem obdobju, kot ga vstavite
več imen v

262
00:12:01,600 --> 00:12:02,880
razpršene tabele?

263
00:12:02,880 --> 00:12:04,630
Dobiš trčenja, kajne?

264
00:12:04,630 --> 00:12:07,560
Kaj pa, če imate Alice in Arona,
dve osebi, katerih imena se je zgodilo

265
00:12:07,560 --> 00:12:08,190
za začetek?

266
00:12:08,190 --> 00:12:11,660
To Zastavlja se vprašanje, kjer ste
dal drugo takšno ime?

267
00:12:11,660 --> 00:12:15,050
>> No, morda naivno pravkar dal
kjer Bob pripada, potem pa je Bob

268
00:12:15,050 --> 00:12:17,300
vrsta zajebali, če boste poskušali
vstavite svoje ime zraven in

269
00:12:17,300 --> 00:12:18,240
ni prostora za njega.

270
00:12:18,240 --> 00:12:21,400
Tako da boste morda dal Boba, kjer je Charlie,
in si lahko predstavljate to zelo hitro

271
00:12:21,400 --> 00:12:23,020
decentralizacijo v malo nered.

272
00:12:23,020 --> 00:12:25,600
Nekaj ​​linearno na koncu, kjer ste
samo treba iskati celotno stvar

273
00:12:25,600 --> 00:12:28,190
išče Alice in Bob
ali Aaron ali Charlie.

274
00:12:28,190 --> 00:12:33,230
>> Torej, namesto da smo predlagali, namesto samo
linearno sondiranje za odprte prostore

275
00:12:33,230 --> 00:12:36,450
in plopping imena Tam smo
Predlog Ljubitelj pristop.

276
00:12:36,450 --> 00:12:41,740
Hash tabela izvajajo še z
matrika indeksov, vendar podatkovni tip

277
00:12:41,740 --> 00:12:44,500
ti indeksi zdaj so bili kazalci.

278
00:12:44,500 --> 00:12:47,360
Kazalci na kaj?

279
00:12:47,360 --> 00:12:48,730
Kazalci, povezanih seznamov.

280
00:12:48,730 --> 00:12:53,330
>> Ker opozarjata, da je povezani seznam
res samo kazalec na vozlišče in

281
00:12:53,330 --> 00:12:57,110
vozlišče ima naslednje polje, in da vozlišča
Ima naslednje polje, in tako naprej.

282
00:12:57,110 --> 00:13:00,690
Tako lahko sedaj razmišljati o tem polju na
Leva stran od razpršilne tabele kot

283
00:13:00,690 --> 00:13:01,820
vodi v povezano seznamu.

284
00:13:01,820 --> 00:13:07,000
Prednost, ki je, če dobiš
trčenje med Alice in Aronu

285
00:13:07,000 --> 00:13:09,300
kaj storiti z
Druga taka oseba?

286
00:13:09,300 --> 00:13:14,150
Pravkar ste mu priložite ali ji
Konec ali celo začetek

287
00:13:14,150 --> 00:13:15,490
tega povezanega seznama.

288
00:13:15,490 --> 00:13:17,340
>> In pravzaprav, kaj je samo testenin preko
da za sekundo.

289
00:13:17,340 --> 00:13:18,640
Kjer bi bila najbolj smiselna?

290
00:13:18,640 --> 00:13:22,060
Če sem vstavil Alice in ona pristane na
prvo mesto, potem pa skušam

291
00:13:22,060 --> 00:13:25,310
vstaviti ime Aronovi, in tam
Očitno trčenje, naj dam

292
00:13:25,310 --> 00:13:27,400
ga v začetku
iz povezanega seznama?

293
00:13:27,400 --> 00:13:30,944
To je v tistem prvem mestu,
ali na koncu?

294
00:13:30,944 --> 00:13:31,440
>> PUBLIKA: [neslišno].

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

296
00:13:31,990 --> 00:13:32,490
Slišal sem, začenja.

297
00:13:32,490 --> 00:13:33,903
Zakaj na začetku?

298
00:13:33,903 --> 00:13:34,750
>> PUBLIKA: [neslišno].

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

300
00:13:34,940 --> 00:13:36,520
To je po abecedi, tako da je lepo.

301
00:13:36,520 --> 00:13:37,330
To je dobra lastnost.

302
00:13:37,330 --> 00:13:39,335
To mi bo prihranilo nekaj časa potencialno.

303
00:13:39,335 --> 00:13:43,290
To ne bo pustila narediti binarno iskanje, vendar sem
bi vsaj lahko izbruhnejo

304
00:13:43,290 --> 00:13:47,340
iz zanke, če se zavedam, no, jaz sem pot
preteklosti so Aaron bi bilo v ta

305
00:13:47,340 --> 00:13:48,310
razporejene seznam povezano.

306
00:13:48,310 --> 00:13:50,360
Nimam izgubljati svoj čas iščejo
vse do konca.

307
00:13:50,360 --> 00:13:51,530
Tako da je razumno.

308
00:13:51,530 --> 00:13:54,710
Zakaj bi si želeli, da vstavite
trka na ime

309
00:13:54,710 --> 00:13:56,660
začetek seznama?

310
00:13:56,660 --> 00:13:57,397
Kaj je to?

311
00:13:57,397 --> 00:13:58,680
>> PUBLIKA: [neslišno].

312
00:13:58,680 --> 00:14:00,820
>> DAVID Malan: To lahko traja dolgo časa
da se na koncu seznama.

313
00:14:00,820 --> 00:14:02,490
In v resnici, daljša.

314
00:14:02,490 --> 00:14:04,920
Več imen, ki jih vstavite
začnete z, več, da

315
00:14:04,920 --> 00:14:06,280
veriga bo dobil.

316
00:14:06,280 --> 00:14:07,890
Več vezana
Seznam bo dobil.

317
00:14:07,890 --> 00:14:09,420
Torej ste res samo
zapravljaš svoj čas.

318
00:14:09,420 --> 00:14:14,070
Morda ste bolje ohranja
konstantna čas vstavitve, velik O od 1,

319
00:14:14,070 --> 00:14:18,470
z vedno dajanje trka na ime
začetek povezano seznama

320
00:14:18,470 --> 00:14:21,230
in ne skrbi toliko,
o razvrščanju.

321
00:14:21,230 --> 00:14:22,600
>> Kaj je najboljši odgovor?

322
00:14:22,600 --> 00:14:23,320
To je jasno.

323
00:14:23,320 --> 00:14:26,140
Nekako je odvisno, kaj
distribucija, kaj vzorec

324
00:14:26,140 --> 00:14:27,850
imen vstavljate.

325
00:14:27,850 --> 00:14:29,430
To ni nujno
Očiten odgovor.

326
00:14:29,430 --> 00:14:33,100
Ampak tukaj, še enkrat, je
Oblikovanje priložnost.

327
00:14:33,100 --> 00:14:37,220
>> Tako smo nato pogledal na to stvar, ki
je res druga velika priložnost

328
00:14:37,220 --> 00:14:38,180
za p-set 6.

329
00:14:38,180 --> 00:14:41,770
In zavedaš, če tega še niste storili,
Zamyla potopi v oboje, zgoščevalne

330
00:14:41,770 --> 00:14:43,260
mize in poizkusih podrobneje.

331
00:14:43,260 --> 00:14:45,630
In video potopis
vgrajeni v p-set spec.

332
00:14:45,630 --> 00:14:46,590
To je Trie -

333
00:14:46,590 --> 00:14:51,670
T-R-I-E. In kaj je bilo zanimivo
to je bil, da čas teče

334
00:14:51,670 --> 00:14:59,510
o iskanju imena, kot so Maxwell
Zadnjič, ko je bil velik O česa?

335
00:14:59,510 --> 00:15:01,040
Kaj je to?

336
00:15:01,040 --> 00:15:01,920
>> PUBLIKA: število črk.

337
00:15:01,920 --> 00:15:02,550
>> DAVID Malan: Število črk.

338
00:15:02,550 --> 00:15:03,210
Slišal sem dve stvari.

339
00:15:03,210 --> 00:15:04,630
Število pisem in konstantno časa.

340
00:15:04,630 --> 00:15:05,540
Torej gremo s tem prvi.

341
00:15:05,540 --> 00:15:06,410
Število črkami.

342
00:15:06,410 --> 00:15:10,195
No, ta struktura podatkov, odpoklic, je
kot drevo, družinsko drevo, vsak od

343
00:15:10,195 --> 00:15:12,860
katerih vozlišča sestavljajo nizi.

344
00:15:12,860 --> 00:15:16,300
In ti nizi so kazalci
druga takšna vozlišča ali drugih kot

345
00:15:16,300 --> 00:15:17,670
polja v drevesu.

346
00:15:17,670 --> 00:15:22,890
>> Torej, če smo želeli ugotoviti, nato
ali je Maxwell tukaj, jaz bi šel

347
00:15:22,890 --> 00:15:26,890
do prvega niza, na sam vrh
drevo, tako imenovani root vrh

348
00:15:26,890 --> 00:15:30,521
Trie in sledite m kazalec,
Nato kazalec, potem x,

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

350
00:15:31,710 --> 00:15:34,910
In potem, ko sem videl nekaj posebnega simbola
tukaj označen kot trikotnik.

351
00:15:34,910 --> 00:15:38,480
V kodi boste videli, predlagamo, da
izvaja kot bool, samo rekel ja

352
00:15:38,480 --> 00:15:40,540
ali ne, beseda ustavi tukaj.

353
00:15:40,540 --> 00:15:45,270
>> No, ko smo šli na M-A-X-W-E-L-L,
počuti kot sedem, morda

354
00:15:45,270 --> 00:15:48,910
osem, če gremo eno mimo njega, osem
koraki, da bi našli Maxwell.

355
00:15:48,910 --> 00:15:53,050
Ali pa recimo ji K. pokličite Toda spomnimo zadnje
Tokrat sem trdil, da če obstaja

356
00:15:53,050 --> 00:15:57,540
realno največja dolžina na
beseda, kot je 40-nekaj-ak znakov,

357
00:15:57,540 --> 00:16:00,810
maksimalna dolžina pomeni
konstanta.

358
00:16:00,810 --> 00:16:05,770
Torej res, ja, to je tehnično veliki O
z dne 8. ali 7, ali res veliki O iz K. But

359
00:16:05,770 --> 00:16:09,420
če je končna kapa o tem, kaj
K lahko, da je konstantna.

360
00:16:09,420 --> 00:16:12,080
In tako je velik O od 1 v
konec dneva.

361
00:16:12,080 --> 00:16:13,040
>> Ne v resničnem svetu.

362
00:16:13,040 --> 00:16:15,960
Ne, ko ste dejansko začnete gledal
ura kot delovanje vašega programa.

363
00:16:15,960 --> 00:16:20,690
To je absolutno bo nekoliko
počasneje kot resnično konstanten

364
00:16:20,690 --> 00:16:21,840
Čas z enim korakom.

365
00:16:21,840 --> 00:16:25,540
To se dogaja, da je sedem ali osem korakov,
pa še to je veliko, veliko bolje

366
00:16:25,540 --> 00:16:30,080
kot algoritem kot veliki O n tem
je odvisna od velikosti, kaj je v

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

368
00:16:31,220 --> 00:16:34,970
>> Obvestilo glavo tu lahko vstavite
milijon imen v tem

369
00:16:34,970 --> 00:16:38,170
podatkovne strukture, ampak koliko več korakov
se dogaja, da nas bo najti

370
00:16:38,170 --> 00:16:40,480
Maxwell v tem primeru?

371
00:16:40,480 --> 00:16:40,780
Jih ni.

372
00:16:40,780 --> 00:16:41,820
On je nespremenjena.

373
00:16:41,820 --> 00:16:45,480
In do sedaj, ne verjamem, da smo videli
Primer podatkovno strukturo ali

374
00:16:45,480 --> 00:16:48,560
Algoritem, ki je bila v celoti
vpliva zunanjih

375
00:16:48,560 --> 00:16:50,040
vedenja, kot je ta.

376
00:16:50,040 --> 00:16:51,160
Ampak to ne more biti neverjetno.

377
00:16:51,160 --> 00:16:52,900
To ne more biti edina rešitev
za p-set

378
00:16:52,900 --> 00:16:53,570
>> In to ni.

379
00:16:53,570 --> 00:16:55,980
To ni nujno podatkov
Struktura morate gravitirajo,

380
00:16:55,980 --> 00:16:58,220
ker je tako kot hash tabele, kompromis.

381
00:16:58,220 --> 00:17:00,500
Kakšna je cena, ki jo plača tukaj?

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

383
00:17:00,940 --> 00:17:02,890
Mislim, da je to grozna
količino pomnilnika.

384
00:17:02,890 --> 00:17:05,569
In ne moreš kar vidim tukaj, ker
avtor te slike

385
00:17:05,569 --> 00:17:09,420
Očitno okrnjena vsi nizi,
in ne bomo videli veliko je in

386
00:17:09,420 --> 00:17:12,700
B-jev in C ter Q in Y-ov
in Z je v teh nizi.

387
00:17:12,700 --> 00:17:13,630
Ampak oni so tam.

388
00:17:13,630 --> 00:17:17,660
>> Vsaka od teh vozlišč je cela vrsta
nekaterih 26 ali več bajtov, v vsaki

389
00:17:17,660 --> 00:17:19,170
kar predstavlja pismo.

390
00:17:19,170 --> 00:17:22,920
27 v našem primeru, tako da se lahko podpre
opuščaji na problem nizu.

391
00:17:22,920 --> 00:17:27,030
Torej je to podatkovna struktura je res,
res gosto in široko.

392
00:17:27,030 --> 00:17:30,880
In da sam morda na koncu upočasnjuje
stvari navzdol, ali vsaj stanejo

393
00:17:30,880 --> 00:17:32,240
Veliko več prostora.

394
00:17:32,240 --> 00:17:34,020
Ampak spet, lahko črpamo
primerjave tukaj.

395
00:17:34,020 --> 00:17:39,190
>> Spomnimo se nekaj časa nazaj, smo dosegli veliko
bolj razburljivo tekmovanje v teku časa s sortiranjem

396
00:17:39,190 --> 00:17:42,880
ko smo uporabi zlivanjem, ampak cena
smo plačali za doseganje n log n za spajanje

397
00:17:42,880 --> 00:17:46,930
sortiranje zahteva, da smo preživeli
več kaj sredstev?

398
00:17:46,930 --> 00:17:47,690
Več prostora.

399
00:17:47,690 --> 00:17:50,530
Potrebovali smo sekundarni array
kopiranje ljudi v, tako kot

400
00:17:50,530 --> 00:17:51,620
smo tukaj na odru.

401
00:17:51,620 --> 00:17:55,880
Torej, še enkrat, ni jasnih zmagovalcev,
ampak samo subjektivna zasnova

402
00:17:55,880 --> 00:17:57,710
Odločitve je treba opraviti.

403
00:17:57,710 --> 00:17:58,060
>> Vse je v redu.

404
00:17:58,060 --> 00:17:59,130
Torej, kaj pa je to?

405
00:17:59,130 --> 00:18:02,050
Vsakdo, ki priznavajo D-Hall?

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

407
00:18:02,440 --> 00:18:03,170
Torej tri od nas.

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

409
00:18:03,750 --> 00:18:05,070
Torej, to je za jedilnico Mather je.

410
00:18:05,070 --> 00:18:09,650
Stavim, da so vsi jedilnici imajo
skladovnice pladnjev, kot je ta.

411
00:18:09,650 --> 00:18:11,950
In to je pravzaprav predstavnik
nečesa, kar smo jih

412
00:18:11,950 --> 00:18:13,050
očitno že videli.

413
00:18:13,050 --> 00:18:14,850
Poklicali smo ga dobesedno kup.

414
00:18:14,850 --> 00:18:18,970
In kup, v smislu vašega
računalnika spomin, je, če gre podatki

415
00:18:18,970 --> 00:18:20,460
medtem ko so funkcije se imenuje.

416
00:18:20,460 --> 00:18:23,410
>> Na primer, kakšne stvari gredo
na stack v zvezi z

417
00:18:23,410 --> 00:18:27,420
Postavitev spomin smo razpravljali
V zadnjih tednih?

418
00:18:27,420 --> 00:18:28,736
Kaj je to?

419
00:18:28,736 --> 00:18:29,670
>> PUBLIKA: Klici funkcij.

420
00:18:29,670 --> 00:18:30,260
>> DAVID Malan: Žal mi je.

421
00:18:30,260 --> 00:18:31,210
>> PUBLIKA: Klici funkcij.

422
00:18:31,210 --> 00:18:33,590
>> DAVID Malan: Klici funkcij, vendar
Natančneje, katero je znotraj vsakega

423
00:18:33,590 --> 00:18:35,340
te okvirje?

424
00:18:35,340 --> 00:18:37,220
Katere vrste stvari?

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

426
00:18:37,460 --> 00:18:38,500
Tako lokalne spremenljivke.

427
00:18:38,500 --> 00:18:43,080
Kadarkoli smo potrebovali nekaj lokalno shranjevanje,
kot argument, ali int I, ali int

428
00:18:43,080 --> 00:18:45,940
temp, ali karkoli lokalnih
spremenljivka, smo bili

429
00:18:45,940 --> 00:18:47,210
dajanje da na sklad.

430
00:18:47,210 --> 00:18:49,610
In mi je kup pokličete, ker
te ideje plastenje.

431
00:18:49,610 --> 00:18:52,940
Nekako tekmah z realnostjo,
Pogodbe koncept.

432
00:18:52,940 --> 00:18:56,650
>> Vendar pa se izkaže, da sklad lahko tudi
treba obravnavati kot strukturo podatkov

433
00:18:56,650 --> 00:19:00,110
Alternativa matriko, alternativa
v povezano seznamu.

434
00:19:00,110 --> 00:19:02,770
Nekaj ​​konceptualno bolj zanimivo
da lahko še vedno

435
00:19:02,770 --> 00:19:06,030
izvaja z uporabo enega od tistih
stvari, ampak to je drugačen tip

436
00:19:06,030 --> 00:19:09,140
podatkovna struktura podpira, res,
le dve operacije.

437
00:19:09,140 --> 00:19:11,000
Lahko pa dodate na Ljubitelj
funkcij, kot ti.

438
00:19:11,000 --> 00:19:12,180
Ampak to so osnove -

439
00:19:12,180 --> 00:19:13,510
potiskanje in pop.

440
00:19:13,510 --> 00:19:19,240
>> In ideja z dimnika je, da če sem
je tu, z ali brez Annenberg

441
00:19:19,240 --> 00:19:22,880
vedoč, pladenj od soseda
s številko 9 na njem.

442
00:19:22,880 --> 00:19:23,870
Torej, samo int.

443
00:19:23,870 --> 00:19:26,990
In hočem, da potisne na podatkih
struktura, ki je trenutno prazna.

444
00:19:26,990 --> 00:19:28,790
Razmislite o tem na dnu dimnika.

445
00:19:28,790 --> 00:19:33,150
Jaz bi potisnite to številko 9 na
kup, in zdaj je tam.

446
00:19:33,150 --> 00:19:36,040
>> Ampak zanimiva stvar dimnika
je, da če bi zdaj rad potiskanje

447
00:19:36,040 --> 00:19:40,210
nekatere druge vrednosti, kot so 17 in porinem
to na kupu, bom naredil

448
00:19:40,210 --> 00:19:43,290
samo intuitivno stvar, grem
da bi ga tam, kjer smo ljudje

449
00:19:43,290 --> 00:19:45,180
bi se nagiba k temu, da dajo na vrhu.

450
00:19:45,180 --> 00:19:48,850
Ampak kaj je zanimivo zdaj
je, kako pridem ob 9h?

451
00:19:48,850 --> 00:19:50,670
Veš, jaz ne bi nekaj truda.

452
00:19:50,670 --> 00:19:54,070
>> Torej, kaj je zanimivo
stack, ki so po svoji zasnovi,

453
00:19:54,070 --> 00:19:56,330
to je podatkovna struktura LIFO.

454
00:19:56,330 --> 00:19:59,680
Neumno način opisovanja
zadnji noter, prvi ven.

455
00:19:59,680 --> 00:20:03,280
Torej, zadnja številka v
V tem času je bilo 17.

456
00:20:03,280 --> 00:20:07,540
Torej, če želim, da pop nekaj off
iz dimnika, je lahko le 17.

457
00:20:07,540 --> 00:20:11,890
Torej je obvezna red
Operacije tukaj, kjer je zadnji element

458
00:20:11,890 --> 00:20:14,260
v mora biti prva izpadla.

459
00:20:14,260 --> 00:20:16,440
Zato kratica, LIFO.

460
00:20:16,440 --> 00:20:19,160
>> Torej, zakaj bi bilo to koristno?

461
00:20:19,160 --> 00:20:22,690
So njihovi konteksti, v kateri ste jo
želijo podatkovno strukturo, kot je ta?

462
00:20:22,690 --> 00:20:24,810
No, to je gotovo koristno
notranjost računalnika.

463
00:20:24,810 --> 00:20:29,050
Torej operacijski sistemi jasno uporabljajo to
vrsta podatkovne strukture za kupe.

464
00:20:29,050 --> 00:20:32,800
Bomo videli tudi isto idejo
ko gre za spletne strani.

465
00:20:32,800 --> 00:20:35,890
Torej ta teden in naslednji teden in naprej,
in kot ste začeti izvajati spletu

466
00:20:35,890 --> 00:20:39,490
Strani v jeziku, ki se imenuje HTML, lahko
dejansko uporabljajo podatkovne strukture, kot

467
00:20:39,490 --> 00:20:42,690
to, da ugotovi, če stran
je pravilno oblikovano.

468
00:20:42,690 --> 00:20:47,170
Ker bomo videli vse spletne strani, sledite
neke vrste hierarhijo, zamik

469
00:20:47,170 --> 00:20:52,030
da bo ob koncu dneva, se
drevesna struktura pod pokrovom.

470
00:20:52,030 --> 00:20:53,620
Torej, več o tem v samo nekaj.

471
00:20:53,620 --> 00:20:56,560
>> Ampak za zdaj, kaj je predlagala za
Trenutek, kako bi lahko šel okoli

472
00:20:56,560 --> 00:20:58,830
predstavlja, kaj stack?

473
00:20:58,830 --> 00:21:03,370
Dovolite mi, da predlagam, da izvajajo
sklad s kodo, kot je ta.

474
00:21:03,370 --> 00:21:07,990
Torej sklad bo imel notri
Dve stvari, matrike, ki se imenuje pladnji,

475
00:21:07,990 --> 00:21:09,510
samo, da je v skladu z demo.

476
00:21:09,510 --> 00:21:12,660
In vsaka od postavk v tej matriki
se bo tip int.

477
00:21:12,660 --> 00:21:14,740
In zmogljivosti, je verjetno, kaj?

478
00:21:14,740 --> 00:21:18,796
Ker še nikoli nisem napisal
Celotna definicija tukaj.

479
00:21:18,796 --> 00:21:21,535
>> To je verjetno največji
velikost matrike.

480
00:21:21,535 --> 00:21:25,150
In to je verjetno deklariran kot ostra
določiti na vrhu datoteke, nekateri

481
00:21:25,150 --> 00:21:28,450
nekako konstantna kot je vsebovano v
Zgolj kapitalizacija.

482
00:21:28,450 --> 00:21:32,250
Torej nekje zmogljivost je opredeljena
kot največjo možno velikost.

483
00:21:32,250 --> 00:21:35,590
Medtem, znotraj strukture podatkov
znan kot dimnik tam bo

484
00:21:35,590 --> 00:21:38,630
je celo samo znan
preprosto kot velikosti.

485
00:21:38,630 --> 00:21:43,400
>> Torej, če bi bil jaz, da predstavlja ta sedaj
slikovno, pa domnevam, da je to

486
00:21:43,400 --> 00:21:48,070
celoti črna skrinjica predstavlja moj kup.

487
00:21:48,070 --> 00:21:50,070
Znotraj tega je dve spremenljivki.

488
00:21:50,070 --> 00:21:54,780
Torej bom pripraviti
Prva je velikost.

489
00:21:54,780 --> 00:21:57,420
In druga bom
pripraviti kot niz.

490
00:21:57,420 --> 00:22:01,060
>> Ampak samo, da se stvari urejene,
običajno bi rišem matriko kot

491
00:22:01,060 --> 00:22:04,910
to je pa res super
če ustrezajo realnosti, ali

492
00:22:04,910 --> 00:22:06,230
ujemajo z duševno model.

493
00:22:06,230 --> 00:22:12,880
Naj namesto sestaviti niz
navpično, kar je prav, še enkrat,

494
00:22:12,880 --> 00:22:13,840
umetnikova izročitev.

495
00:22:13,840 --> 00:22:16,610
Sploh ni pomembno, kakšna je
je pod pokrovom.

496
00:22:16,610 --> 00:22:20,350
In bomo rekli, da je privzeto
kapaciteta se bo tri.

497
00:22:20,350 --> 00:22:23,480
Torej bo to mesto 0, to
bo mesto 1, to

498
00:22:23,480 --> 00:22:25,740
bo lokacija 2.

499
00:22:25,740 --> 00:22:29,330
>> Če sem podkupil s stres žogo, bi
nekdo rad prišel gor in teče

500
00:22:29,330 --> 00:22:30,870
vkrcati tukaj za trenutek?

501
00:22:30,870 --> 00:22:31,960
OK, prvič videl roko.

502
00:22:31,960 --> 00:22:33,950
Pridi gor.

503
00:22:33,950 --> 00:22:36,500
Vse je v redu.

504
00:22:36,500 --> 00:22:38,760
Torej menim, da je Steven.

505
00:22:38,760 --> 00:22:40,035
Pridi gor.

506
00:22:40,035 --> 00:22:40,770
Vse je v redu.

507
00:22:40,770 --> 00:22:46,760
>> Recimo, zdaj smo nazaj na začetno
država na svetu, kjer sem

508
00:22:46,760 --> 00:22:52,180
Pravkar prijavljeni kup, in to je
bo zmogljivost tri.

509
00:22:52,180 --> 00:22:54,470
Toda velikost še ni bila ugotovljena.

510
00:22:54,470 --> 00:22:56,100
Še ni bila določena pladnji.

511
00:22:56,100 --> 00:22:57,300
Torej nekaj vprašanj prvi.

512
00:22:57,300 --> 00:23:01,310
In naj ti dam mikrofon, tako da lahko
sodelujejo bolj dejavno v tem.

513
00:23:01,310 --> 00:23:05,190
>> Torej, kaj je v velikosti v tem trenutku
V času, če je vse, kar sem naredil, je

514
00:23:05,190 --> 00:23:09,340
prijavljeni kup z
ena vrstica kode?

515
00:23:09,340 --> 00:23:10,100
>> STEVEN: Ne veliko.

516
00:23:10,100 --> 00:23:12,080
>> DAVID Malan: OK, ni veliko.

517
00:23:12,080 --> 00:23:14,410
Ali vemo, kaj je v velikosti,
Ne vemo, kaj je notri

518
00:23:14,410 --> 00:23:16,330
te matrike tukaj?

519
00:23:16,330 --> 00:23:18,630
>> STEVEN: Samo naključno kodo, kajne?

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

521
00:23:20,220 --> 00:23:23,230
>> DAVID Malan: Ja, bom
je koda poklicati, ampak naključno -

522
00:23:23,230 --> 00:23:23,820
>> STEVEN: Stvari.

523
00:23:23,820 --> 00:23:28,290
>> DAVID Malan: Stvari, kot naključno

524
00:23:28,290 --> 00:23:28,870
>> STEVEN: Biti.

525
00:23:28,870 --> 00:23:29,530
>> DAVID Malan: Biti, kajne?

526
00:23:29,530 --> 00:23:31,190
Torej smeti vrednosti, kajne?

527
00:23:31,190 --> 00:23:33,470
Torej permutacije 0 in 1 je.

528
00:23:33,470 --> 00:23:35,920
Ostanki prejšnjih običajih
to pomnilnika.

529
00:23:35,920 --> 00:23:38,150
In ne bomo zares vedeli, kaj se vrednosti
so, tako da smo ponavadi narisati

530
00:23:38,150 --> 00:23:38,930
kot vprašaji.

531
00:23:38,930 --> 00:23:41,990
>> Torej prva stvar, ki smo menda
dogaja, da želijo narediti tukaj -

532
00:23:41,990 --> 00:23:46,630
in dovolite mi, da to področje v notranjosti
od tod ime - pladnji.

533
00:23:46,630 --> 00:23:49,540
Kaj bomo predvidoma inicializacijo
velikosti, da če želimo

534
00:23:49,540 --> 00:23:51,040
začnete uporabljati to kup?

535
00:23:51,040 --> 00:23:53,070
>> STEVEN: Nik je pod 3.

536
00:23:53,070 --> 00:23:53,910
>> DAVID Malan: Torej, v redu.

537
00:23:53,910 --> 00:23:56,710
Da bo jasno, se razglasi zmogljivost
drugje kot tri.

538
00:23:56,710 --> 00:23:58,570
In to je tisto, kar sem uporabljal tudi
dodeliti niz.

539
00:23:58,570 --> 00:24:03,535
Velikost se dogaja, da se nanašajo na koliko
Pladnji so trenutno na kupu.

540
00:24:03,535 --> 00:24:03,880
>> STEVEN: Zero.

541
00:24:03,880 --> 00:24:04,460
>> DAVID Malan: Torej bi bilo nič.

542
00:24:04,460 --> 00:24:07,760
Tako da gredo naprej in z vsakim prstom,
narisati nič v velikosti.

543
00:24:07,760 --> 00:24:08,440
Vse je v redu.

544
00:24:08,440 --> 00:24:10,920
Torej, zdaj, kaj je notri tega
tukaj, ne vemo.

545
00:24:10,920 --> 00:24:12,160
To so res samo smeti vrednosti.

546
00:24:12,160 --> 00:24:14,800
Torej bi lahko potegnemo vprałaje, vendar
Pustimo svet čisto za zdaj

547
00:24:14,800 --> 00:24:16,300
saj ni važno
kaj je tam.

548
00:24:16,300 --> 00:24:19,130
Mi ne potrebujemo za inicializacijo niz
z ničemer, kajti če vemo, da

549
00:24:19,130 --> 00:24:23,100
velikost svežnju nič, dobro smo
se ne sme gledaš kaj v

550
00:24:23,100 --> 00:24:25,590
To polje je na vsak način
ta trenutek.

551
00:24:25,590 --> 00:24:29,970
>> Torej sedaj Predvidevam, da bom pritisnil
številka 9 na kupu.

552
00:24:29,970 --> 00:24:33,750
Kako bi morali posodobiti podatkovno strukturo
notranjost te črne škatle?

553
00:24:33,750 --> 00:24:35,540
Katere vrednote je treba spremeniti?

554
00:24:35,540 --> 00:24:36,200
>> STEVEN: V -

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

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

557
00:24:37,650 --> 00:24:38,770
Velikost morala postati kaj?

558
00:24:38,770 --> 00:24:39,580
>> STEVEN: Velikost bi bila ena.

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

560
00:24:39,870 --> 00:24:41,110
Tako da bi postali ena velikost.

561
00:24:41,110 --> 00:24:42,540
Torej, lahko to storite v nekaj načinov.

562
00:24:42,540 --> 00:24:46,920
Naj ti dam, zdaj si
Prst je radirka.

563
00:24:46,920 --> 00:24:47,260
Vse je v redu.

564
00:24:47,260 --> 00:24:49,960
Potem je zdaj vaš prst je čopič.

565
00:24:49,960 --> 00:24:50,330
Vse je v redu.

566
00:24:50,330 --> 00:24:52,820
In sedaj, kaj se mora spremeniti,
Očitno je, da strukture podatkov?

567
00:24:52,820 --> 00:24:57,060
>> STEVEN: Gremo od
spodaj do 9.

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

569
00:24:57,760 --> 00:24:58,420
V redu, dobro.

570
00:24:58,420 --> 00:25:01,550
Torej še vedno ni važno, kaj je na
lokaciji enega ali dva, ker so

571
00:25:01,550 --> 00:25:04,520
Smetarska vrednosti, vendar ne smemo ukvarjati
si tam, ker velikost je

572
00:25:04,520 --> 00:25:07,540
nam povedali, da je samo prvi element
je dejansko legitimno.

573
00:25:07,540 --> 00:25:10,400
Torej, zdaj bom pritisnil 17 na seznamu.

574
00:25:10,400 --> 00:25:11,830
Kaj se zgodi s to sliko?

575
00:25:11,830 --> 00:25:14,720
>> STEVEN: Torej, velikost pa je šla na dva.

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

577
00:25:15,300 --> 00:25:16,070
Ste radirka -

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

579
00:25:16,810 --> 00:25:18,026
Ste radirko.

580
00:25:18,026 --> 00:25:18,840
>> STEVEN: radirka.

581
00:25:18,840 --> 00:25:19,720
>> DAVID Malan: Ti si krtačo.

582
00:25:19,720 --> 00:25:20,560
>> STEVEN: Čopič.

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

584
00:25:20,920 --> 00:25:21,600
In kaj še?

585
00:25:21,600 --> 00:25:22,600
>> STEVEN: In potem -

586
00:25:22,600 --> 00:25:22,915
>> DAVID Malan: Zavzeli smo se 17.

587
00:25:22,915 --> 00:25:24,760
>> STEVEN: Držimo 17 na vrhu, tako da -

588
00:25:24,760 --> 00:25:25,710
>> DAVID Malan: V redu, dobro.

589
00:25:25,710 --> 00:25:27,040
>> STEVEN: - ga spustite navzdol.

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

591
00:25:27,530 --> 00:25:27,940
To je vse enostavno.

592
00:25:27,940 --> 00:25:29,300
Ne bom vam pomagala ta čas.

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

594
00:25:30,510 --> 00:25:31,720
>> STEVEN: Končano.

595
00:25:31,720 --> 00:25:34,870
Postati radirko.

596
00:25:34,870 --> 00:25:37,340
Jaz sem postal krtačo.

597
00:25:37,340 --> 00:25:39,340
In potem sem dajanje 22.

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

599
00:25:40,100 --> 00:25:40,620
Odlično.

600
00:25:40,620 --> 00:25:41,380
Torej, še enkrat.

601
00:25:41,380 --> 00:25:44,280
Zdaj sem bom za potiskanje
na kupu 26.

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

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

604
00:25:50,278 --> 00:25:52,520
Res si me preseneti.

605
00:25:52,520 --> 00:25:53,703
>> DAVID Malan: Nisi
videli prihajati?

606
00:25:53,703 --> 00:25:55,930
>> STEVEN: Nisem videl tega prihaja.

607
00:25:55,930 --> 00:25:58,756
Bi lahko ponovno začetna zmogljivost?

608
00:25:58,756 --> 00:25:59,790
>> DAVID Malan: To je dobro vprašanje.

609
00:25:59,790 --> 00:26:02,360
Torej smo nekako naslikal sebe
v kotu tukaj.

610
00:26:02,360 --> 00:26:06,740
Res ni dober ven Stevenom
ker smo dodeljen ta niz

611
00:26:06,740 --> 00:26:09,130
statično, tako rekoč, v notranjosti
podatkovne strukture.

612
00:26:09,130 --> 00:26:12,170
In smo v bistvu težko kodirane
, da je velikost tri.

613
00:26:12,170 --> 00:26:14,170
Torej, ne moremo zares prerazporediti.

614
00:26:14,170 --> 00:26:20,020
>> Lahko bi, če bi šli nazaj, smo
na novo pladnji, da je kazalec, ki

615
00:26:20,020 --> 00:26:22,300
smo nato malloc za ročno spomin.

616
00:26:22,300 --> 00:26:25,050
Ker če imamo spomin iz
kup prek funkcije malloc smo

617
00:26:25,050 --> 00:26:26,430
bi ga rešil.

618
00:26:26,430 --> 00:26:29,630
Toda preden je osvoboditev, smo lahko
prerazporediti večji kos pomnilnika,

619
00:26:29,630 --> 00:26:31,330
posodabljanje kazalca, in tako naprej.

620
00:26:31,330 --> 00:26:33,500
Toda za zdaj je to res
najboljše, kar lahko naredimo.

621
00:26:33,500 --> 00:26:36,360
Push in pop sta verjetno bo
da so za signaliziranje nekatere napake.

622
00:26:36,360 --> 00:26:40,270
>> Tako, na primer, naša izvedba
za lahko potisni vrne bool ki

623
00:26:40,270 --> 00:26:42,390
prej vrnil res, res, res.

624
00:26:42,390 --> 00:26:48,390
Ampak četrti čas, da se dogaja, da imajo
vrne false, npr.

625
00:26:48,390 --> 00:26:48,540
Vse je v redu.

626
00:26:48,540 --> 00:26:49,540
Zelo dobro opravljeno.

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

628
00:26:50,060 --> 00:26:52,160
Ste zaslužili svoj stres žogo danes.

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

630
00:26:53,110 --> 00:26:54,382
>> STEVEN: Hvala.

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

632
00:26:55,680 --> 00:26:59,740
OK, tako da se zdi, da ni veliko
za korak naprej, a ne?

633
00:26:59,740 --> 00:27:01,410
Opisali smo to strukturo podatkov.

634
00:27:01,410 --> 00:27:02,320
To je bil prepričljiv, kajne?

635
00:27:02,320 --> 00:27:03,200
Operacijski sistemi všeč.

636
00:27:03,200 --> 00:27:06,360
Očitno lahko spletni uporabi tega
in druge aplikacije še vedno.

637
00:27:06,360 --> 00:27:10,870
Ampak kaj neumnega omejitev, ki smo
nazaj na neke v tednu dvema skrajnostma

638
00:27:10,870 --> 00:27:12,880
kjer smo določena zaporedja velikosti.

639
00:27:12,880 --> 00:27:15,010
>> Torej so dejansko nekaj
načini, kako bi lahko rešili to.

640
00:27:15,010 --> 00:27:18,750
Mi lahko dinamično dodeli niz,
ni jih težko kodiranje, kot sem

641
00:27:18,750 --> 00:27:22,600
narediti tukaj, ampak ponovno izjavlja
to, samo, da bo jasno, kot je

642
00:27:22,600 --> 00:27:23,830
kaj takega.

643
00:27:23,830 --> 00:27:29,040
Int * pladnji, ne odločajo
o zmogljivosti še ni.

644
00:27:29,040 --> 00:27:35,460
Toda, ko sem razglasila Sveženj drugje
v mojem kodo, sem lahko potem pokličete malloc,

645
00:27:35,460 --> 00:27:38,250
dobite naslov na kos
spomin, in sem lahko dodeli

646
00:27:38,250 --> 00:27:39,980
da je naslov na pladnjih.

647
00:27:39,980 --> 00:27:43,340
>> In potem, ker je samo kos
spomin, sem lahko še naprej uporabljajo kvadrat

648
00:27:43,340 --> 00:27:45,450
Nosilec zapis na običajen način.

649
00:27:45,450 --> 00:27:49,020
Ker še enkrat, tam je nekako to
funkcionalni ekvivalent nizi in

650
00:27:49,020 --> 00:27:50,820
kose pomnilnika, ki prihajajo
nazaj od funkcije malloc.

651
00:27:50,820 --> 00:27:53,090
Mi lahko privoščite eno kot drugo
uporabo kazalca aritmetično ali

652
00:27:53,090 --> 00:27:54,440
oglati oklepaj zapis.

653
00:27:54,440 --> 00:27:55,660
Tako da je en pristop.

654
00:27:55,660 --> 00:28:00,120
>> Ampak kako pa bi lahko izvajanje tega
enako strukturo podatkov, morda?

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

656
00:28:00,280 --> 00:28:04,530
Počutim se, kot smo pravkar rešili to
problem kot pred tednom dni.

657
00:28:04,530 --> 00:28:08,860
Kaj je rešitev za ta problem
da Steven naletela?

658
00:28:08,860 --> 00:28:10,370
Torej povezani seznam, prav.

659
00:28:10,370 --> 00:28:13,410
>> Če problem je, da smo slikarstva
sami v kotu z dodelitvijo

660
00:28:13,410 --> 00:28:17,580
vnaprej premalo pomnilnika, ki smo
Nato so se nekako ukvarjajo z, no,

661
00:28:17,580 --> 00:28:19,880
zakaj ne samo, da bi se izognili
izda skupaj?

662
00:28:19,880 --> 00:28:26,170
Zakaj ne razglasi pladnji za
kazalec na vozlišče, ergo povezan seznam,

663
00:28:26,170 --> 00:28:30,740
in nato preprosto dodelijo nove vozlišč
vsakič Steven potrebno, da se prilega

664
00:28:30,740 --> 00:28:32,400
število v podatkovno strukturo.

665
00:28:32,400 --> 00:28:34,200
>> Tako da bi slika morala spremeniti.

666
00:28:34,200 --> 00:28:38,220
To ne bo tako čista in kot
enostavno, kot le niz treh ints.

667
00:28:38,220 --> 00:28:42,970
Zdaj se dogaja, da se kazalec
struct, in da struct bo

668
00:28:42,970 --> 00:28:44,830
imajo int in naslednjo kazalec.

669
00:28:44,830 --> 00:28:47,670
To bo vodilo preko tega kazalca
drugi taki struct, da

670
00:28:47,670 --> 00:28:48,600
še ena taka struct.

671
00:28:48,600 --> 00:28:50,560
Torej slika bi dejansko
dobili malo Messier.

672
00:28:50,560 --> 00:28:52,950
In mi bi bili puščice vezavo
vse skupaj.

673
00:28:52,950 --> 00:28:55,280
>> Ampak to je v redu, kajne, saj
smo videli, kako to storiti.

674
00:28:55,280 --> 00:28:58,180
In ko boste dobili udobno
izvedbenih nekaj podobnega povezano

675
00:28:58,180 --> 00:29:01,450
Seznam, ki jih boste morali narediti, če
odločijo za izvajanje razpršene tabele s

676
00:29:01,450 --> 00:29:05,120
Veriženje za p-set 6, lahko
jo uporabite kot gradnik, ali

677
00:29:05,120 --> 00:29:08,870
sestavina ali nič rekoč
Postopek, nekaj, kar si dal, vas

678
00:29:08,870 --> 00:29:12,560
ustvarili svoj kos sestavljanke
da lahko potem znova.

679
00:29:12,560 --> 00:29:17,090
Torej kompromisi, vendar potencialne rešitve
da smo dejansko videli.

680
00:29:17,090 --> 00:29:20,560
>> Tako pogosto, vidiš to vsak
leto ali dve, ko Apple za javnost

681
00:29:20,560 --> 00:29:23,060
nekaj novega, in vsi nori ljudje
line up zunaj Apple

682
00:29:23,060 --> 00:29:27,050
shranite za nakup njihovega obrobnega
nadgraditi na strojni opremi.

683
00:29:27,050 --> 00:29:30,420
Jaz pravim, da je v redu, ker
Jaz sem eden tistih ljudi.

684
00:29:30,420 --> 00:29:35,140
Torej, kakšne podatkovne strukture
lahko predstavlja to realnost?

685
00:29:35,140 --> 00:29:36,980
>> No, pa je čakalna vrsta, linija pokličite.

686
00:29:36,980 --> 00:29:40,270
Torej bi Britanci poimenovali po navadi
Čakalna vrsta nekako, tako da je lepo ime.

687
00:29:40,270 --> 00:29:44,960
In dve operaciji, da čakalne vrste
podpirali bomo klic enqueue

688
00:29:44,960 --> 00:29:48,900
Delovanje in dequeue delovanje,
ki so podobne

689
00:29:48,900 --> 00:29:50,120
duh push in pop.

690
00:29:50,120 --> 00:29:54,060
To je nekako drugačna
Konvencija, kaj kličeš ti.

691
00:29:54,060 --> 00:29:57,680
Ampak enqueue kaj pomeni, da dodate
ali vstaviti za podatkovno strukturo.

692
00:29:57,680 --> 00:29:59,570
Da dequeue pomeni, da ga odstranite.

693
00:29:59,570 --> 00:30:05,170
Toda medtem ko je bil kup podatkov LIFO
struktura, čakalna vrsta je prvi,

694
00:30:05,170 --> 00:30:06,740
Prvi od strukture podatkov.

695
00:30:06,740 --> 00:30:10,050
>> Če ste prva oseba, ki je v skladu,
da bo prva oseba, da bi dobili

696
00:30:10,050 --> 00:30:12,420
iz linije in kupite novo napravo.

697
00:30:12,420 --> 00:30:18,070
Predstavljajte si, kako razburjen bi ti ljudje
če Apple namesto dimnika, za

698
00:30:18,070 --> 00:30:21,250
na primer, za izvajanje picking
up vaše nove igrače.

699
00:30:21,250 --> 00:30:24,310
Torej čakalne vrste smisla, vsekakor, in
lahko razmišljamo o vseh mogočih

700
00:30:24,310 --> 00:30:27,480
aplikacije, verjetno, za čakalne vrste,
še posebej, če hočeš pravičnost.

701
00:30:27,480 --> 00:30:30,040
Torej, kako bi lahko izvajanje teh
kot podatkovne strukture?

702
00:30:30,040 --> 00:30:33,680
>> No, jaz predlagam, da bi lahko
morajo to storiti v to smer.

703
00:30:33,680 --> 00:30:35,225
Torej bom zdaj številk.

704
00:30:35,225 --> 00:30:38,190
Tako da bomo naj bo enostavno in ne
nujno govori v smislu pladnje.

705
00:30:38,190 --> 00:30:40,220
Samo številke, ki ljudje gotten.

706
00:30:40,220 --> 00:30:43,760
Kapaciteta se bo, še enkrat, določi
Skupno število oseb, ki so lahko v

707
00:30:43,760 --> 00:30:46,900
ta vrstica, kot tri ali
koli druga vrednost.

708
00:30:46,900 --> 00:30:50,760
>> Ampak jaz predlagam, da moram slediti
ne le velikosti

709
00:30:50,760 --> 00:30:52,370
Čakalna vrsta, koliko so stvari v njem.

710
00:30:52,370 --> 00:30:56,310
Torej velikost je sedanja velikost, zmogljivost
je največja velikost.

711
00:30:56,310 --> 00:30:58,540
Samo enkrat, nomenklatura
po dogovoru.

712
00:30:58,540 --> 00:31:03,680
Zakaj potrebujemo dodatno int znotraj
o vrsti slediti, kdo je v

713
00:31:03,680 --> 00:31:05,365
sprednji strani linije?

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

715
00:31:07,930 --> 00:31:10,910
Zakaj moram to narediti v tem primeru?

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

717
00:31:14,750 --> 00:31:16,190
>> No, kako je to slika
se bo spremenilo?

718
00:31:16,190 --> 00:31:19,280
Verjetno lahko ponovno najbolj
te slike.

719
00:31:19,280 --> 00:31:21,480
Dovolite mi, da gredo naprej in izbrisati, kaj je tukaj.

720
00:31:21,480 --> 00:31:24,580
Mi bomo to lahko nekoliko
drugačno ime tu gor.

721
00:31:24,580 --> 00:31:28,930
Znebimo od 17, znebimo
od 9, dajmo se znebite 3.

722
00:31:28,930 --> 00:31:30,410
In dodajmo še eno stvar.

723
00:31:30,410 --> 00:31:34,710
Predlagam, da moram slediti
sprednja stran, ki je prav

724
00:31:34,710 --> 00:31:35,570
bo int tudi.

725
00:31:35,570 --> 00:31:36,550
In bomo keep it simple.

726
00:31:36,550 --> 00:31:37,740
Ne povezani seznam za zdaj.

727
00:31:37,740 --> 00:31:40,900
>> Bomo priznati, da bomo
Naleteli proti tej meji.

728
00:31:40,900 --> 00:31:43,720
Ampak, kaj hočem videti
zgodilo tokrat?

729
00:31:43,720 --> 00:31:47,240
Tako, da sem šel naprej in prvi
oseba, ki prihaja v liniji, in

730
00:31:47,240 --> 00:31:48,560
to je številka 9.

731
00:31:48,560 --> 00:31:49,680
Imamo stres kroglice.

732
00:31:49,680 --> 00:31:51,330
Lahko kradem, recimo, dveh ali treh ljudi?

733
00:31:51,330 --> 00:31:52,690
Ena, dva, tri?

734
00:31:52,690 --> 00:31:53,120
Pridi gor.

735
00:31:53,120 --> 00:31:56,022
Desno od spredaj, ker
bomo, da je to eden hitro.

736
00:31:56,022 --> 00:31:59,415
>> Vsak od vas se sedaj dogaja, da se
ventilator fant v vrsti na Apple.

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

738
00:32:03,970 --> 00:32:06,210
Ne boste prejemali Apple strojne opreme
Na koncu tega, čeprav.

739
00:32:06,210 --> 00:32:06,500
Vse je v redu.

740
00:32:06,500 --> 00:32:09,430
Torej ste številko 9, si
Številka 17, številka 22.

741
00:32:09,430 --> 00:32:12,130
To so poljubne številke, kot
študent ID-ji ali drugih malenkosti.

742
00:32:12,130 --> 00:32:14,550
In čez nekaj trenutkov, začnimo
za začetek dodajanja stvari.

743
00:32:14,550 --> 00:32:16,000
In bom teči krovu tukaj ta čas.

744
00:32:16,000 --> 00:32:19,570
>> Torej, v tem primeru, sem inicializiran
spredaj, da -

745
00:32:19,570 --> 00:32:22,380
Pravzaprav sploh ne zanima, kaj
spredaj je, saj znaša nič.

746
00:32:22,380 --> 00:32:24,480
Torej je to lahko tudi samo
biti vprašaj.

747
00:32:24,480 --> 00:32:26,170
To so vsi vprašljiva.

748
00:32:26,170 --> 00:32:29,880
Torej, zdaj bomo začeli dejansko videli nekaj
ljudje podloga v trgovini.

749
00:32:29,880 --> 00:32:33,320
>> Torej, če številka 9, ti si prvi
tam ob 5:00, pojdi naprej in line up,

750
00:32:33,320 --> 00:32:34,210
ali večer prej.

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

752
00:32:34,580 --> 00:32:35,940
Torej, zdaj 9 je tukaj.

753
00:32:35,940 --> 00:32:37,940
Torej 9 na sprednjem seznama.

754
00:32:37,940 --> 00:32:41,440
Tako da sem šel naprej in posodobiti
Velikost tekočih podatkov

755
00:32:41,440 --> 00:32:44,740
strukture, da ne bo več 0,
ampak na 1.

756
00:32:44,740 --> 00:32:47,630
Bom dal na 9.
sprednja stran.

757
00:32:47,630 --> 00:32:51,020
Dovolite mi, da gredo naprej in preklopite zaslon
Tako lahko vidimo, mimo nas tukaj.

758
00:32:51,020 --> 00:32:53,220
>> In zdaj kaj hočem
dati na sprednji strani?

759
00:32:53,220 --> 00:32:56,240
Grem slediti, da
sprednji vrsti zdaj

760
00:32:56,240 --> 00:32:58,570
je na mestu 0..

761
00:32:58,570 --> 00:33:00,510
Ker, kaj se bo zgodilo naslednje?

762
00:33:00,510 --> 00:33:03,000
No, recimo, zdaj sem enqueue
17 kot tudi.

763
00:33:03,000 --> 00:33:04,510
Torej hop v skladu tam.

764
00:33:04,510 --> 00:33:07,060
In spet, nekako vratih
Trgovina je, da bo tu.

765
00:33:07,060 --> 00:33:08,700
Torej, zdaj sem dodal 17.

766
00:33:08,700 --> 00:33:10,810
In čeprav so ti fantje blokiranje
zaslon, da je v redu,

767
00:33:10,810 --> 00:33:12,300
saj ga lahko vidite tukaj gor.

768
00:33:12,300 --> 00:33:12,910
Žal mi je.

769
00:33:12,910 --> 00:33:13,810
>> PUBLIKA: Mi lahko premikate -

770
00:33:13,810 --> 00:33:14,660
>> DAVID Malan: Ne, to je v redu.

771
00:33:14,660 --> 00:33:16,000
To je velik tam gor.

772
00:33:16,000 --> 00:33:18,580
Torej 17 je sedaj znotraj vrste.

773
00:33:18,580 --> 00:33:21,332
Moram posodobiti, ki
Polja sedaj, čeprav?

774
00:33:21,332 --> 00:33:23,210
OK, vsekakor velikost.

775
00:33:23,210 --> 00:33:26,430
Kaj pa spredaj?

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

777
00:33:27,040 --> 00:33:30,200
Spredaj se ne sme spremeniti, ker
za razliko od dimnika, smo

778
00:33:30,200 --> 00:33:31,370
želijo ohraniti pravičnost.

779
00:33:31,370 --> 00:33:35,150
Torej, če 9 prišel prvi, želimo 9
da je treba najprej iz vrste

780
00:33:35,150 --> 00:33:36,420
in v trgovini.

781
00:33:36,420 --> 00:33:37,220
>> Dejstvo je, da vidimo, da je.

782
00:33:37,220 --> 00:33:42,235
Preden smo vstaviti 22, dajmo
iti naprej in dequeue 9.

783
00:33:42,235 --> 00:33:42,970
Kaj ti je že ime?

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

785
00:33:43,680 --> 00:33:45,440
>> DAVID Malan: Jake se dogaja
se dequeued zdaj.

786
00:33:45,440 --> 00:33:48,050
Tako da boste dobili, da hodi v trgovino.

787
00:33:48,050 --> 00:33:49,880
In se pretvarjamo, da trgovina
je tam.

788
00:33:49,880 --> 00:33:51,970
Torej, kaj zdaj potrebuje - dit-dit-dit!

789
00:33:51,970 --> 00:33:53,400
Kaj se mora zgoditi zdaj?

790
00:33:53,400 --> 00:33:54,490
Odločitev oblikovanje.

791
00:33:54,490 --> 00:33:56,825
Torej ni slab nagon, ampak -
Kako ti je ime?

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

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

794
00:33:57,500 --> 00:33:58,810
Torej, kaj je David storil?

795
00:33:58,810 --> 00:34:02,590
Poskušal je nekako popraviti podatke
struktura in premik od svojega mesta

796
00:34:02,590 --> 00:34:04,100
v Jakov nekdanji lokaciji.

797
00:34:04,100 --> 00:34:06,740
In to je v redu, če smo pripravljeni
sprejeti dejstvo, da so

798
00:34:06,740 --> 00:34:08,199
podrobno izvajanje.

799
00:34:08,199 --> 00:34:11,100
Ampak najprej, kaj je posodobiti podatke
strukturo, preden to storimo.

800
00:34:11,100 --> 00:34:14,139
Ker nisem všeč zamisel, da vse
ljudje premikajo v tej vrstici.

801
00:34:14,139 --> 00:34:17,360
>> To ni nič takega, če je David to počne z
en korak, vendar še enkrat, mislim nazaj

802
00:34:17,360 --> 00:34:20,360
ko smo imeli osem prostovoljcev na
oder in smo naredili tako kot vstavljanje

803
00:34:20,360 --> 00:34:22,600
razvrščanje, kjer smo morali začeti
gibljejo vse okoli.

804
00:34:22,600 --> 00:34:23,790
Da imam drago, kajne?

805
00:34:23,790 --> 00:34:28,330
To me klečeplastvo o velikem O
n, big O n znova na kvadrat.

806
00:34:28,330 --> 00:34:30,650
To ni občutek, kot
idealen rezultat.

807
00:34:30,650 --> 00:34:32,080
>> Zato naj samo posodobiti to.

808
00:34:32,080 --> 00:34:35,120
Torej velikost čakalne vrste
ni več 2.

809
00:34:35,120 --> 00:34:37,090
To je zdaj samo 1.

810
00:34:37,090 --> 00:34:40,360
Ampak jaz lahko sedaj posodobite nekaj
Nisem posodobiti prej,

811
00:34:40,360 --> 00:34:41,130
sprednja stran.

812
00:34:41,130 --> 00:34:45,420
Jaz lahko samo povem, je, da je lokacija 1?

813
00:34:45,420 --> 00:34:49,770
Torej, zdaj imamo smeti vrednosti tukaj
Smetarsko vrednost tukaj, in David v

814
00:34:49,770 --> 00:34:51,469
Sredi te smeti.

815
00:34:51,469 --> 00:34:54,980
Ampak struktura podatkov
je nedotaknjena.

816
00:34:54,980 --> 00:34:58,540
>> In v resnici sploh ne potrebujete
spremenite Jaku nekdanjo številko

817
00:34:58,540 --> 00:35:00,460
9, ker koga briga.

818
00:35:00,460 --> 00:35:04,470
Nimam dovolj informacij, je zdaj v
velikost, da vem, da je ena oseba v

819
00:35:04,470 --> 00:35:05,030
To čakalne vrste.

820
00:35:05,030 --> 00:35:08,340
In vem, da je ta oseba
je na lokaciji 1, ne 0.

821
00:35:08,340 --> 00:35:09,760
Jaz se ne upošteva.

822
00:35:09,760 --> 00:35:11,300
Torej 1, kot tudi.

823
00:35:11,300 --> 00:35:13,410
Torej podatkovna struktura je še vedno v redu.

824
00:35:13,410 --> 00:35:14,330
>> No, kaj se zgodi potem?

825
00:35:14,330 --> 00:35:15,010
Debatni enqueue -

826
00:35:15,010 --> 00:35:15,370
Kako ti je ime?

827
00:35:15,370 --> 00:35:16,160
>> PUBLIKA: Callen.

828
00:35:16,160 --> 00:35:16,580
>> DAVID Malan: Callen.

829
00:35:16,580 --> 00:35:20,770
Oglejmo enqueue je Callen, in
22 je zdaj na vrsti.

830
00:35:20,770 --> 00:35:22,300
Torej, zdaj, kaj je tu spremenilo?

831
00:35:22,300 --> 00:35:24,380
Spredaj je ne bo
spremeniti, seveda.

832
00:35:24,380 --> 00:35:27,160
Velikost se bo spremenilo, da je 2. znova.

833
00:35:27,160 --> 00:35:31,590
In 22 konča tukaj, 9 je še vedno prisotna,
ampak to je dejansko

834
00:35:31,590 --> 00:35:32,600
Smetarsko vrednost zdaj.

835
00:35:32,600 --> 00:35:35,910
To je samo ostanek Jake preteklosti.

836
00:35:35,910 --> 00:35:39,200
>> Torej, zdaj, kaj se zgodi, če
Jaz dequeue Davida?

837
00:35:39,200 --> 00:35:41,560
Še zadnja operacija, dequeue David.

838
00:35:41,560 --> 00:35:46,070
Mi lahko premika, ampak jaz predlagam lets '
storite tako malo dela, kot je mogoče.

839
00:35:46,070 --> 00:35:50,280
Zdaj moja struktura podatkov gre
nazaj v velikosti 2-1.

840
00:35:50,280 --> 00:35:53,730
Ampak sprednji vrsti
zdaj postane 2.

841
00:35:53,730 --> 00:35:56,640
Ni mi treba spremeniti te številke
samo še, ker oni

842
00:35:56,640 --> 00:35:58,230
le smeti vrednosti.

843
00:35:58,230 --> 00:35:59,720
>> Toda zdaj, kaj se zgodi?

844
00:35:59,720 --> 00:36:03,280
Recimo, da sem enqueue sam, 26?

845
00:36:03,280 --> 00:36:05,890
Počutim se, kot da spadam sem.

846
00:36:05,890 --> 00:36:06,890
Torej sem se enqueued.

847
00:36:06,890 --> 00:36:08,760
Tako sem nekako spadam sem.

848
00:36:08,760 --> 00:36:11,300
In čeprav ti niso čisto
cenim to vidno na odru,

849
00:36:11,300 --> 00:36:15,075
ker imamo dovolj prostora, da bi moral
ne bi stal tukaj, zakaj?

850
00:36:15,075 --> 00:36:16,290
>> PUBLIKA: Ti si izven igrišča.

851
00:36:16,290 --> 00:36:16,370
>> DAVID Malan: Right.

852
00:36:16,370 --> 00:36:16,940
Sem izven igrišča.

853
00:36:16,940 --> 00:36:19,330
Sem indeksira preko
mejá te matrike.

854
00:36:19,330 --> 00:36:23,420
Res bi morala biti v eni od
tri možne lokacije.

855
00:36:23,420 --> 00:36:25,150
Zdaj, ko je najbolj naravna iti?

856
00:36:25,150 --> 00:36:27,760
Predlagam, da vzvodom
teden en trik.

857
00:36:27,760 --> 00:36:30,150
Operater mod, odstotek.

858
00:36:30,150 --> 00:36:36,850
Ker sem tehnično znašal
mesto 3, ampak jaz 3 mod zmogljivosti,

859
00:36:36,850 --> 00:36:40,250
tako 3, znak za odstotek, 3 -

860
00:36:40,250 --> 00:36:40,970
kapaciteta je 3.

861
00:36:40,970 --> 00:36:41,720
Kaj je to?

862
00:36:41,720 --> 00:36:43,700
Kaj je ostalo pri
si delimo 3 za 3?

863
00:36:43,700 --> 00:36:44,070
0.

864
00:36:44,070 --> 00:36:48,140
>> Tako, da me postavi so bili Jake je bil,
kar je pravzaprav dobro.

865
00:36:48,140 --> 00:36:50,370
Torej, zdaj je izvajanje
to stvar, ki se dogaja, da

866
00:36:50,370 --> 00:36:51,250
biti malo glavobol.

867
00:36:51,250 --> 00:36:53,740
To je res samo ena vrstica
glavobola, kode.

868
00:36:53,740 --> 00:36:56,580
Ampak zdaj vsaj obstaja smeti
Vrednost tu, vendar pa je dva

869
00:36:56,580 --> 00:36:57,910
zakonite ints tukaj.

870
00:36:57,910 --> 00:37:04,160
In trdim, da zdaj smo storili
kaj moramo tako dolgo, dokler ne

871
00:37:04,160 --> 00:37:08,600
smo spremenili, kaj Jake
vrednost naj bi bila 26.

872
00:37:08,600 --> 00:37:12,110
>> Zdaj imamo dovolj podatkov, še
da se ohrani celovitost

873
00:37:12,110 --> 00:37:13,060
te strukture podatkov.

874
00:37:13,060 --> 00:37:17,160
Še vedno smo nekako od sreče, ko smo
želite vstaviti štiri ali več skupaj

875
00:37:17,160 --> 00:37:20,740
Elementi, ampak lahko bi vsaj precej
učinkovita uporaba ta konstanta

876
00:37:20,740 --> 00:37:21,740
čas, v resnici.

877
00:37:21,740 --> 00:37:27,150
Nimam skrbeti za prestavljanje
vsakdo, kot naklona Davidove bil.

878
00:37:27,150 --> 00:37:30,816
>> Vsa vprašanja o skladih,
ali je ta vrsta?

879
00:37:30,816 --> 00:37:32,184
>> PUBLIKA: Je razlog, zakaj
morate velikosti, tako da boste vedeli,

880
00:37:32,184 --> 00:37:34,010
kjer je imela oseba?

881
00:37:34,010 --> 00:37:34,770
>> DAVID Malan: Točno tako.

882
00:37:34,770 --> 00:37:38,230
Moram vedeti, velikost matrike
ker moram, kako natančno vedeti

883
00:37:38,230 --> 00:37:41,940
mnogi od teh vrednosti so legitimne,
in da najdem, kam

884
00:37:41,940 --> 00:37:42,800
Naslednja oseba.

885
00:37:42,800 --> 00:37:43,300
Točno tako.

886
00:37:43,300 --> 00:37:44,580
Velikost je -

887
00:37:44,580 --> 00:37:46,360
pravzaprav nismo posodobili to še ni.

888
00:37:46,360 --> 00:37:48,380
Sam sem dodal na 26 let.

889
00:37:48,380 --> 00:37:51,760
Velikost je sedaj, ne 1, vendar 2.

890
00:37:51,760 --> 00:37:57,780
Torej, zdaj je to res mi pomaga najti
glava seznama, ki ni 0, ne

891
00:37:57,780 --> 00:37:59,250
1, vendar pa je 2.

892
00:37:59,250 --> 00:38:01,665
Sprednja stran
je dejansko število 22.

893
00:38:01,665 --> 00:38:05,120
Ker je prišel v prvo, zato je treba
dovoljeno v trgovini pred menoj,

894
00:38:05,120 --> 00:38:08,780
čeprav vizualno stojim
bližje trgovini.

895
00:38:08,780 --> 00:38:09,220
>> Vse v redu?

896
00:38:09,220 --> 00:38:12,410
Aplavz za te fante
in jih bom pustil ven.

897
00:38:12,410 --> 00:38:17,090
>> [APLAVZ]

898
00:38:17,090 --> 00:38:18,150
>> DAVID Malan: Jaz bi pustil
boste obdržali pladenj.

899
00:38:18,150 --> 00:38:20,760
Smo lahko videli, kaj se zgodi, če
hočeš, pa morda ne.

900
00:38:20,760 --> 00:38:21,590
Vse je v redu.

901
00:38:21,590 --> 00:38:25,380
Torej, kaj zdaj pa nam preostane?

902
00:38:25,380 --> 00:38:28,900
No, naj predlagajo, da obstaja
Nekaj ​​drugih podatkovne strukture smo lahko

903
00:38:28,900 --> 00:38:33,810
začnete tako, da naše orodje kit, ki bo
dejansko zelo, zelo pomembno, saj je

904
00:38:33,810 --> 00:38:35,270
smo se potopite v spletnem stvari.

905
00:38:35,270 --> 00:38:38,150
Ki je spet, ima nekakšno povezavo
drevesom v obliki

906
00:38:38,150 --> 00:38:40,550
nekaj, kar se imenuje DOM, dokument
objektni model.

907
00:38:40,550 --> 00:38:42,370
Ampak bomo videli več
da je pred dolgo.

908
00:38:42,370 --> 00:38:46,260
>> Dovolite mi, da predlagam definitionally, da smo
pokličite drevo zdaj kaj znate, kot

909
00:38:46,260 --> 00:38:48,820
bolj družinsko drevo, kjer si
nekaj prednika na

910
00:38:48,820 --> 00:38:49,790
Korenine drevesa.

911
00:38:49,790 --> 00:38:54,480
Patriarhalna ali Matriarchs na
samem vrhu drevesa.

912
00:38:54,480 --> 00:38:56,700
Brez njihovega zakonca, v tem primeru.

913
00:38:56,700 --> 00:39:00,940
Vendar imamo zdaj, kaj bomo klic
otroci, ki so vozlišča, ki visi

914
00:39:00,940 --> 00:39:05,480
off levi otroka ali desno otroka,
puščice, kot je prikazano tukaj.

915
00:39:05,480 --> 00:39:10,490
>> Z drugimi besedami, v podatkovno strukturo drevo
v računalniku, drevo ima ničlo

916
00:39:10,490 --> 00:39:11,480
ali več vozlišč.

917
00:39:11,480 --> 00:39:13,500
Če ima vsaj eno vozlišča
ki se imenuje koren.

918
00:39:13,500 --> 00:39:15,700
To so stvari, ki vizualno
potegnemo na vrhu.

919
00:39:15,700 --> 00:39:20,280
In to vozlišče, kot katera koli druga vozlišča, lahko
imeli nič, ena ali dve ali tri,

920
00:39:20,280 --> 00:39:23,600
ali glede na število otrok
Struktura podatkov podpira.

921
00:39:23,600 --> 00:39:29,150
V tem primeru je koren, shranjevanje
vrednost ena, ima dva otroka, 2 in 3,

922
00:39:29,150 --> 00:39:33,020
Tako smo na splošno imenujemo 2 levo
otrok in 3 pravico otrok.

923
00:39:33,020 --> 00:39:36,940
>> Potem, ko smo dobili do 5, 6, in
7, 6 bi lahko imenovali srednji otrok.

924
00:39:36,940 --> 00:39:38,940
Če imate štiri otroke,
postane zmedeno.

925
00:39:38,940 --> 00:39:42,260
Zato smo prenehali uporabljati to vrsto
za bližnjico verbalno.

926
00:39:42,260 --> 00:39:44,580
Ampak to je res samo družinsko drevo.

927
00:39:44,580 --> 00:39:48,880
In listi tukaj so vozlišča, ki
sami nimajo otrok.

928
00:39:48,880 --> 00:39:52,540
So visi off dno drevesa.

929
00:39:52,540 --> 00:39:56,940
>> Torej, kako bi lahko izvajala drevo, ki
Ima le dva otroka, maksimalno?

930
00:39:56,940 --> 00:39:58,410
Mi bomo to binarno drevo klic.

931
00:39:58,410 --> 00:40:00,960
Bi spet pomeni dve, v tem
tako, kot je z binarno.

932
00:40:00,960 --> 00:40:04,830
Tako ima lahko nič, ena,
ali dva otroka najvišja.

933
00:40:04,830 --> 00:40:08,650
>> Bom predlagam, da izvajajo vozlišče
Za te strukture z int n,

934
00:40:08,650 --> 00:40:11,910
in potem dva kazalci, ena se imenuje
levo, ena imenovana pravica.

935
00:40:11,910 --> 00:40:14,830
Ampak to so samo lepo
samovoljne konvencij.

936
00:40:14,830 --> 00:40:18,170
In kaj je lepo zdaj, še posebej, če
vrsta boril s konceptualno

937
00:40:18,170 --> 00:40:21,300
rekurzija, ali misli, da ni bilo
res rešitev za vse,

938
00:40:21,300 --> 00:40:23,120
še posebej, če bi lahko
zmanjka pomnilnika.

939
00:40:23,120 --> 00:40:26,600
Zdaj, ko govorimo o podatkih
strukture in algoritmi, ki omogočajo

940
00:40:26,600 --> 00:40:31,030
nam prečkanje in manipulirati z njimi,
Izkazalo se je, da je rekurzija vrne v

941
00:40:31,030 --> 00:40:34,240
veliko bolj prepričljiv
če ne lep način.

942
00:40:34,240 --> 00:40:38,670
>> Torej, to predlagam, je izvajanje
za funkcijo iskanje.

943
00:40:38,670 --> 00:40:39,870
Glede na to, dva vhoda -

944
00:40:39,870 --> 00:40:41,570
tako da mislim, da je to črno škatlo.

945
00:40:41,570 --> 00:40:46,560
Glede na to, dva vhoda, n, int, in
kazalec na drevo, kazalec

946
00:40:46,560 --> 00:40:50,020
vozlišče, ali res koren drevesa, sem
Trditev, da je to funkcija vrne

947
00:40:50,020 --> 00:40:53,530
resnična ali neresnična, da je vrednost n
je znotraj tega drevesa.

948
00:40:53,530 --> 00:40:55,210
>> Kaj je v te črne skrinjice?

949
00:40:55,210 --> 00:40:57,440
No, štiri podružnice.

950
00:40:57,440 --> 00:40:58,385
Prvi pravkar preverja.

951
00:40:58,385 --> 00:41:00,490
Če drevo je nična, samo vrne false.

952
00:41:00,490 --> 00:41:04,580
Če ni vozel, ni n
ni več, samo vrne false.

953
00:41:04,580 --> 00:41:12,330
Če temu, n, vrednost iščete
, da je manj kot drevo puščice n, in

954
00:41:12,330 --> 00:41:15,180
samo, da bo jasno, kaj pomeni, ko
Pišem drevo in nato puščico

955
00:41:15,180 --> 00:41:18,150
zapis, n?

956
00:41:18,150 --> 00:41:18,690
Točno tako.

957
00:41:18,690 --> 00:41:21,970
To pomeni, da ciljne datoteke
Kazalec se imenuje drevo.

958
00:41:21,970 --> 00:41:26,750
Pojdi tja, nato pa dobil v notranjosti, ki
vozlišče in dobila polje z imenom n.

959
00:41:26,750 --> 00:41:30,810
In nato primerjati dejansko n, da je
prešla v Search proti njej.

960
00:41:30,810 --> 00:41:35,390
>> Torej, če je n manjša od vrednosti n
V drevesu samega vozlišča, dobro,

961
00:41:35,390 --> 00:41:36,720
Kaj to pomeni?

962
00:41:36,720 --> 00:41:40,690
To ne pomeni nič, na prvi pogled.

963
00:41:40,690 --> 00:41:40,900
Kajne?

964
00:41:40,900 --> 00:41:45,560
Tako kot če imate niz
Vrednosti, boste morda želeli uporabiti binarno

965
00:41:45,560 --> 00:41:48,290
iskanje kot obliko razkoraka
in vladaj.

966
00:41:48,290 --> 00:41:51,790
Ampak kaj predpostavka pa moramo narediti
za binarno iskanje za delo na vseh

967
00:41:51,790 --> 00:41:54,510
v imeniku in
prejšnji primeri?

968
00:41:54,510 --> 00:41:55,530
>> Kako se urejeno.

969
00:41:55,530 --> 00:41:59,490
Torej, kaj je natančnejše opredelitve drevesa
Tu ni prav drevo, ki lahko

970
00:41:59,490 --> 00:42:00,880
ima poljubno število otrok.

971
00:42:00,880 --> 00:42:04,700
Ne samo binarno drevo, ki lahko
ima 0, 1, 2 ali maksimalno.

972
00:42:04,700 --> 00:42:09,700
Ampak kot dvojiškega drevesa, ali BST,
ki je samo fancy način rekel

973
00:42:09,700 --> 00:42:15,430
binarno drevo, tako da vsako vozlišče je
levo otrok, če je prisoten, je

974
00:42:15,430 --> 00:42:16,830
manj kot vozlišče.

975
00:42:16,830 --> 00:42:20,170
Vsako vozlišče in pravica otrok,
če je prisoten, je večja

976
00:42:20,170 --> 00:42:21,740
kot vozlišče sama.

977
00:42:21,740 --> 00:42:25,200
>> Torej, z drugimi besedami, če ste bili, da pripravijo
drevo ven, vse številke so

978
00:42:25,200 --> 00:42:30,620
skrbno uravnotežene, tako da, če
imate 55 kot root, 33 more iti

979
00:42:30,620 --> 00:42:33,090
na njegovi levi, ker je manj kot 55 let.

980
00:42:33,090 --> 00:42:36,430
77 se lahko obrnejo na svoje pravice, ker
to je več kot 55 let.

981
00:42:36,430 --> 00:42:40,750
Toda zdaj opazil, enako opredelitev,
to je rekurzivna definicija verbalno,

982
00:42:40,750 --> 00:42:42,600
zaprositi za 33.

983
00:42:42,600 --> 00:42:47,610
33 na levi Otrok mora biti manjša od njega,
in 33 pravica otrok, 44, mora biti

984
00:42:47,610 --> 00:42:48,580
večja od njega.

985
00:42:48,580 --> 00:42:51,670
>> Torej je to binarno iskalno drevo, in
I predlaga uporabo malo

986
00:42:51,670 --> 00:42:53,910
rekurzija, bomo lahko sedaj najdete n.

987
00:42:53,910 --> 00:42:59,160
Torej, če je n manj kot vrednost n, ki je
trenutno vozlišče, jaz grem

988
00:42:59,160 --> 00:43:04,090
naprej in punt, tako rekoč, in samo
vrne kar je odgovor na

989
00:43:04,090 --> 00:43:08,470
iskanje n o
levo otrok drevesa.

990
00:43:08,470 --> 00:43:11,370
Spet opazili, ta funkcija samo
pričakuje, da bo vozlišče Zvezda,

991
00:43:11,370 --> 00:43:12,780
kazalec na vozlišče.

992
00:43:12,780 --> 00:43:17,360
Torej, zagotovo sem lahko samo naredi drevo
puščica levo, ki bo vodila

993
00:43:17,360 --> 00:43:18,400
mi drugo vozlišče.

994
00:43:18,400 --> 00:43:19,480
Ampak kaj je to vozlišče?

995
00:43:19,480 --> 00:43:22,820
>> No, glede na to izjavo,
levo je samo kazalec, tako da le

996
00:43:22,820 --> 00:43:27,090
pomeni, da sem prehod na funkcijo iskanja
drugačen kazalec, in sicer

997
00:43:27,090 --> 00:43:30,750
tista, ki predstavlja
Moja leva otroka drevo.

998
00:43:30,750 --> 00:43:36,040
Torej v tem primeru kazalec 33, če
to je naš vložek vzorec Medtem, če

999
00:43:36,040 --> 00:43:40,740
n je večja od vrednosti n na
trenutno vozlišče v drevesu, potem pa sem

1000
00:43:40,740 --> 00:43:43,370
dogaja, da gredo naprej in punt v drugo
Smer in samo reči, jaz ne

1001
00:43:43,370 --> 00:43:47,280
ve, če ta vrednost je n v drevesu
vem pa, če je to, to je moja dol

1002
00:43:47,280 --> 00:43:49,090
Pravica podružnica, tako rekoč.

1003
00:43:49,090 --> 00:43:53,120
Torej, naj me pokliče rekurzivno iskanje,
spet spustimo n, vendar gre v

1004
00:43:53,120 --> 00:43:54,580
kazalec na moji desni otroka.

1005
00:43:54,580 --> 00:44:00,020
>> Z drugimi besedami, če sem trenutno na 55
in iščem 99, vem, da je 99

1006
00:44:00,020 --> 00:44:04,270
je več kot 55 let, tako kot sem strgal
tedni imenika nazaj in mi

1007
00:44:04,270 --> 00:44:07,140
šel desno, podobno smo
šli tukaj.

1008
00:44:07,140 --> 00:44:11,960
In ne vem, če je na moji desni
otrok, in to ne, 77 je tam, ampak

1009
00:44:11,960 --> 00:44:13,210
Vem, da je v tej smeri.

1010
00:44:13,210 --> 00:44:18,770
Zato sem poklical iskanje na moji desni otroka
77, in pustite iskanje razbrati iz

1011
00:44:18,770 --> 00:44:24,950
pa če je 99 v tem samovoljno
Primer je dejansko tam.

1012
00:44:24,950 --> 00:44:26,900
>> Else, kaj je končni primeru?

1013
00:44:26,900 --> 00:44:28,620
Če drevo je nična, je en primer.

1014
00:44:28,620 --> 00:44:31,890
Če je n manj kot tok vozlišča
vrednost je še en primer.

1015
00:44:31,890 --> 00:44:35,120
Če je n večji od toka
vrednost vozlišča je tretji primer.

1016
00:44:35,120 --> 00:44:38,250
Kaj je četrti in zadnji primer?

1017
00:44:38,250 --> 00:44:39,480
Mislim, da smo iz primerov, kajne?

1018
00:44:39,480 --> 00:44:44,690
Zato mora biti, da je n v
trenutno vozlišče, da sem naprej.

1019
00:44:44,690 --> 00:44:49,640
>> Torej, če sem iskal 55 let na tej točki
v zgodbi, ki veje

1020
00:44:49,640 --> 00:44:51,780
Drevo bi spet res.

1021
00:44:51,780 --> 00:44:55,380
Torej, kaj je zanimivo, je, da smo
pravzaprav, za razliko od preteklih tednih smo nekako

1022
00:44:55,380 --> 00:44:56,740
za dve bazne primerov.

1023
00:44:56,740 --> 00:44:58,300
In ti ne bi bilo treba
Vse bo na vrhu.

1024
00:44:58,300 --> 00:45:01,390
Vrhu je osnovna ker če
Drevo je nična, ni nič narediti.

1025
00:45:01,390 --> 00:45:03,410
Pravkar vrnil težko kodirane
vrednost false.

1026
00:45:03,410 --> 00:45:07,400
>> Spodnji veja je nekako
privzeto, pri čemer se, če smo preveriti

1027
00:45:07,400 --> 00:45:11,550
null, smo preverili, če je treba
levo, vendar to ne bi smelo biti, ki smo jih

1028
00:45:11,550 --> 00:45:14,640
preveri, če bi bilo prav, vendar
ne sme biti jasno, da mora biti

1029
00:45:14,640 --> 00:45:15,870
tam, kjer smo.

1030
00:45:15,870 --> 00:45:16,780
To je osnovni primer.

1031
00:45:16,780 --> 00:45:19,920
Torej je dve rekurzivni primeri
je stisnjena v sredini.

1032
00:45:19,920 --> 00:45:21,630
Vendar bi jaz napisal
to v poljubnem vrstnem redu.

1033
00:45:21,630 --> 00:45:24,520
Mislil sem, da je nekako zdelo naravno
najprej preverite morebitne napake,

1034
00:45:24,520 --> 00:45:28,340
nato pa preverite v levo, nato pa preverite desno, nato
Predvidevam, da ste na vozlišču

1035
00:45:28,340 --> 00:45:30,630
ste dejansko iščejo.

1036
00:45:30,630 --> 00:45:36,240
>> Torej, zakaj bi bilo to koristno?

1037
00:45:36,240 --> 00:45:37,910
Tako se izkaže -

1038
00:45:37,910 --> 00:45:42,110
in mi skočil na teaser
tu se je v spletu.

1039
00:45:42,110 --> 00:45:44,920
Bomo začeli uporabljati ne
programski jezik na prvi, ampak

1040
00:45:44,920 --> 00:45:46,030
označevalni jezik.

1041
00:45:46,030 --> 00:45:48,740
Pa tista, ki je označevalni jezik
pisane v duhu programiranja

1042
00:45:48,740 --> 00:45:51,715
jezika, vendar pa ne dam
sposobnost, da sami logično izraziti.

1043
00:45:51,715 --> 00:45:55,070
To samo vam daje možnost, da
izraziti sebe strukturno.

1044
00:45:55,070 --> 00:45:57,960
>> Kam želite dati nekaj
na strani, spletna stran?

1045
00:45:57,960 --> 00:45:59,200
Kakšno barvo želite, da bi ga?

1046
00:45:59,200 --> 00:46:00,950
Kaj velikost pisave hočeš narediti to?

1047
00:46:00,950 --> 00:46:02,970
Kaj besede, kajne dejansko
želim na spletni strani?

1048
00:46:02,970 --> 00:46:04,060
Tako da je označevalni jezik.

1049
00:46:04,060 --> 00:46:07,690
Ampak potem bomo zelo hitro uvesti
JavaScript, ki je polnopravni

1050
00:46:07,690 --> 00:46:08,560
programskega jezika.

1051
00:46:08,560 --> 00:46:12,530
Zelo podobno skladenjsko po videzu
do C, vendar pa boste morali nekaj

1052
00:46:12,530 --> 00:46:15,200
lepo, močnejši, bolj
uporabniku prijazne funkcije.

1053
00:46:15,200 --> 00:46:18,050
>> In ena od frustracij na to
točka v semestru je, da bomo

1054
00:46:18,050 --> 00:46:22,065
Kmalu izvajati Speller v veliko manj
vrstic kode, ki uporabljajo druge jezike

1055
00:46:22,065 --> 00:46:25,580
kot C sama po sebi dovoljuje, vendar razlog je
bomo kmalu razumeli.

1056
00:46:25,580 --> 00:46:27,750
To bo prva tovrstna spletna stran.

1057
00:46:27,750 --> 00:46:30,120
To bo popolnoma underwhelming,
Prva naredimo.

1058
00:46:30,120 --> 00:46:31,400
To bo preprosto reči, zdravo svet.

1059
00:46:31,400 --> 00:46:34,010
Ampak, če še nikoli niste videli
prej, to je HTML

1060
00:46:34,010 --> 00:46:35,670
HyperText Markup Language.

1061
00:46:35,670 --> 00:46:39,310
>> Če greš v neke menija v
Najbolj koli brskalnik, na kateri koli spletni strani na

1062
00:46:39,310 --> 00:46:43,160
internet, lahko vidite HTML
da nekateri ljudje pisal

1063
00:46:43,160 --> 00:46:44,400
ustvariti to spletno stran.

1064
00:46:44,400 --> 00:46:47,850
In verjetno ne izgleda kot
kratek ali kot lepo, kot je ta.

1065
00:46:47,850 --> 00:46:51,400
Vendar pa bo sledila vzorcu teh
odprte konzole in poševnice in

1066
00:46:51,400 --> 00:46:53,660
črke in potencialno številke.

1067
00:46:53,660 --> 00:46:56,770
>> Mislila sem, da vam teaser
o tem, kaj boste mogli storiti

1068
00:46:56,770 --> 00:46:57,950
po zaužitju CS50.

1069
00:46:57,950 --> 00:47:02,620
Naj grem na cs.harvard.edu / rob,
naše lastne Rob Bowden je domača stran.

1070
00:47:02,620 --> 00:47:06,080
On to je za nas.

1071
00:47:06,080 --> 00:47:07,490
Tako da boste kmalu lahko storim.

1072
00:47:07,490 --> 00:47:10,660
In tudi, kaj ste slišali
Zjutraj -

1073
00:47:10,660 --> 00:47:12,480
kaj ste slišali danes zjutraj -

1074
00:47:12,480 --> 00:47:13,780
>> [HAMSTER DANCE MUSIC]

1075
00:47:13,780 --> 00:47:15,702
>> - Boš lahko, da je to.

1076
00:47:15,702 --> 00:47:16,790
To nas čaka v sredo.

1077
00:47:16,790 --> 00:47:17,791
Vam bomo videli potem.

1078
00:47:17,791 --> 00:47:22,950
>> [HAMSTER DANCE MUSIC]

1079
00:47:22,950 --> 00:47:24,300
DAVID Malan: Na naslednjem CS50 -

1080
00:47:24,300 --> 00:47:31,670