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

2
00:00:11,460 --> 00:00:12,250
>> DAVID MALAN: Okay.

3
00:00:12,250 --> 00:00:13,860
Velkommen tilbage til CS50.

4
00:00:13,860 --> 00:00:16,190
Dette er starten på uge 8.

5
00:00:16,190 --> 00:00:21,320
Og huske, at problemet sæt 5 sluttede
med en lille smule af en udfordring.

6
00:00:21,320 --> 00:00:25,210
Så antager du genvundet alle dine
undervisning Fellows og CA'ens fotografier

7
00:00:25,210 --> 00:00:30,480
i card.raw filen, er du berettiget
nu finde alle de mennesker, og

8
00:00:30,480 --> 00:00:34,510
en heldig vinder vil gå hjem med én
af disse ting, springet bevægelse

9
00:00:34,510 --> 00:00:37,450
enhed, som du kan bruge til endelig
projekter, for eksempel.

10
00:00:37,450 --> 00:00:39,860
>> Dette hvert år, fører til
en smule creepiness.

11
00:00:39,860 --> 00:00:43,480
Og så hvad jeg tænkte jeg ville gøre, er andelen
med dig nogle af de noter, der har

12
00:00:43,480 --> 00:00:47,370
gået frem og tilbage over
de ansatte over sent.

13
00:00:47,370 --> 00:00:51,110
For eksempel, bare aftes, citat
citat slut, fra en af ​​de ansatte

14
00:00:51,110 --> 00:00:55,000
medlemmer, "Jeg har lige haft en elev knock
på min dør for at tage et billede med mig.

15
00:00:55,000 --> 00:00:59,020
Stalkers, jeg fortælle dig. "Startede
temmelig beskrivende og vi flyttede derefter

16
00:00:59,020 --> 00:01:02,830
på, en time eller så senere "Jeg havde en
student venter på mig efter sektion

17
00:01:02,830 --> 00:01:06,080
og han havde alle vores navne og fotos
på nogle ark papir. "Okay.

18
00:01:06,080 --> 00:01:09,230
Så organiseret, men ikke
alt, utryg endnu.

19
00:01:09,230 --> 00:01:12,520
>> Så "Jeg var ude af byen denne weekend,
og da jeg kom tilbage, var der en i

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

21
00:01:12,630 --> 00:01:16,740
soveværelse. "[Latter]

22
00:01:16,740 --> 00:01:20,410
DAVID MALAN: Next citat fra et personale
medlem ", en elev kom til mit hus på

23
00:01:20,410 --> 00:01:25,330
Somerville 4 kl morges. "Next
personale, "Jeg fik til mit hotel i San

24
00:01:25,330 --> 00:01:30,016
Francisco og en studerende ventede på
mig i lobbyen med tre DSLR. "

25
00:01:30,016 --> 00:01:31,510
Type kamera.

26
00:01:31,510 --> 00:01:34,980
"Jeg er ikke engang på personale dette semester
men en studerende brød ind i mit hus, det

27
00:01:34,980 --> 00:01:40,480
morgen og indspillet det hele
med Google Glass ". Og så endelig

28
00:01:40,480 --> 00:01:43,650
"Mindst 12 mennesker var ivrigt
afventer for mig, når jeg fik ud af min

29
00:01:43,650 --> 00:01:44,800
limo, og så er jeg

30
00:01:44,800 --> 00:01:46,970
vågnede. "Okay.

31
00:01:46,970 --> 00:01:57,690
Så blandt de fotografier, som du kan
husker, er dette fyr her, hvem du

32
00:01:57,690 --> 00:02:01,850
måske kender som Milo Banana, der bor
med Lauren Carvalho, vores hoved

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

34
00:02:02,905 --> 00:02:05,170
Milo, Milo, kom her dreng.

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 dig, han iført Google Glass, så
vi vil vise dig alt dette efter.

38
00:02:12,230 --> 00:02:16,190
Så dette er Milo, hvis du gerne vil
tage et fotografi med ham bagefter.

39
00:02:16,190 --> 00:02:18,240
Hvis du gerne vil se ud
på publikum der.

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

41
00:02:19,430 --> 00:02:20,200
Det er godt optagelser.

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

43
00:02:22,556 --> 00:02:23,941
Åh, ikke gør det.

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

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

46
00:02:29,470 --> 00:02:34,550
Så et ord og derefter på, hvad der ligger forude,
fordi som vi begynder at overgangen

47
00:02:34,550 --> 00:02:38,410
denne uge specifikt fra C i en
kommandolinje miljø til PHP og

48
00:02:38,410 --> 00:02:42,720
JavaScript og SQL og HTML og CSS i
et web-baseret miljø, vil vi være

49
00:02:42,720 --> 00:02:44,490
udstyre dig med alle de
mere viden om

50
00:02:44,490 --> 00:02:46,010
potentielle endelige projekter.

51
00:02:46,010 --> 00:02:49,240
Henimod herpå, har naturligvis en
tradition for at holde seminarer,

52
00:02:49,240 --> 00:02:50,950
er på tangentielle emner
til kurset.

53
00:02:50,950 --> 00:02:54,330
Meget meget relateret til programmering og
app udvikling og så videre, men

54
00:02:54,330 --> 00:02:57,010
ikke nødvendigvis udforsket af
kursets egen pensum.

55
00:02:57,010 --> 00:03:00,250
>> Så hvis du kunne være interesseret i én
eller flere af dette års seminarer,

56
00:03:00,250 --> 00:03:02,530
registrere på cs50.net/seminar.

57
00:03:02,530 --> 00:03:06,170
Der er ældre seminarer
på cs50.net/seminars.

58
00:03:06,170 --> 00:03:10,620
Og på den vagtplan hidtil for dette år
er Amazing Web Apps med Ruby on

59
00:03:10,620 --> 00:03:13,580
Skinner, som er et alternativ
sprog PHP.

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

61
00:03:14,900 --> 00:03:18,710
Introduktion til iOS, som er
platform, der bruges til iPhone og

62
00:03:18,710 --> 00:03:19,850
IPAD udvikling.

63
00:03:19,850 --> 00:03:22,890
JavaScript for Web Apps, vil vi dække
der, men i dette seminar, vil du gå

64
00:03:22,890 --> 00:03:24,070
mere i detaljer.

65
00:03:24,070 --> 00:03:27,390
>> Leap Motion, så vi rent faktisk har nogle
af vores venner fra Leap Motion,

66
00:03:27,390 --> 00:03:29,160
virksomheden selv, slutte sig til os.

67
00:03:29,160 --> 00:03:31,800
Morgen, i virkeligheden, give
en hands-on seminar, hvis

68
00:03:31,800 --> 00:03:33,320
af interesse for dig.

69
00:03:33,320 --> 00:03:38,770
Meteor.js en alternativ teknik til
ved hjælp af JavaScript ikke i en browser,

70
00:03:38,770 --> 00:03:39,970
men på en server.

71
00:03:39,970 --> 00:03:42,110
Node.js, som er meget
i denne ånd samt.

72
00:03:42,110 --> 00:03:43,650
Sleek Android Design.

73
00:03:43,650 --> 00:03:46,990
Android er et meget populært alternativ
til iOS og Windows Phone

74
00:03:46,990 --> 00:03:48,790
og andre mobile platforme.

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

76
00:03:51,180 --> 00:03:54,590
>> Så i virkeligheden, hvis du gerne vil
at engagere sig i dette, så lad mig

77
00:03:54,590 --> 00:03:55,840
gøre opmærksom på dette.

78
00:03:55,840 --> 00:03:57,790
Vi er meget glade for at sige, at
vores venner på Leap

79
00:03:57,790 --> 00:03:59,140
Motion, hvilket er en start -

80
00:03:59,140 --> 00:04:01,300
denne enhed virkelig bare kom
ud et par måneder siden -

81
00:04:01,300 --> 00:04:05,960
har allernådigst doneret 30 sådanne anordninger
til klassen for så mange studerende, hvis

82
00:04:05,960 --> 00:04:08,670
du gerne vil låne den hardware
mod semesters ende og bruge det til

83
00:04:08,670 --> 00:04:10,390
en egentlig afsluttende projekt.

84
00:04:10,390 --> 00:04:11,890
De støtter en række sprog.

85
00:04:11,890 --> 00:04:16,040
Ingen af ​​dem C, ingen af ​​dem PHP, så
nå et eller flere af disse seminarer

86
00:04:16,040 --> 00:04:16,899
kan vise sig af interesse.

87
00:04:16,899 --> 00:04:19,730
Og alle af dem vil blive filmet i
tilfælde af at du ikke er i stand

88
00:04:19,730 --> 00:04:21,380
til at møde personligt.

89
00:04:21,380 --> 00:04:25,000
Tidsplanen blive annonceret via
e-mail som vi størkne værelser.

90
00:04:25,000 --> 00:04:28,460
>> Og endelig, hvis du går til
projects.cs.50.net, dette er en hjemmeside

91
00:04:28,460 --> 00:04:31,450
fastholder vi hvert år, at vi invitere
folk fra lokalsamfundet, fakultet,

92
00:04:31,450 --> 00:04:36,420
afdelinger, personale og både
i et udenfor CS50 til

93
00:04:36,420 --> 00:04:37,730
foreslå projektideer.

94
00:04:37,730 --> 00:04:39,050
Ting af interesse for grupper af studerende.

95
00:04:39,050 --> 00:04:40,600
Ting af interesse for afdelinger.

96
00:04:40,600 --> 00:04:43,990
Så du slå der hvis du kæmper
med usikkerhed om, hvad du

97
00:04:43,990 --> 00:04:46,700
selv ønsker at tackle.

98
00:04:46,700 --> 00:04:51,760
>> Så sidste gang vi indført et velsagtens
mere kompleks datastruktur, end vi havde

99
00:04:51,760 --> 00:04:53,300
set i uger tidligere.

100
00:04:53,300 --> 00:04:56,550
Vi havde brugt arrays pretty
lykkeligt som et nyttigt, hvis

101
00:04:56,550 --> 00:04:58,160
simplistisk datastruktur.

102
00:04:58,160 --> 00:05:00,570
Derefter introducerede vi disse, som
naturligvis er forbundet lister.

103
00:05:00,570 --> 00:05:05,470
Og hvad var en af ​​årsagerne til
indføre denne datastruktur?

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

105
00:05:06,930 --> 00:05:07,250
Hvad er det?

106
00:05:07,250 --> 00:05:08,080
>> PUBLIKUM: Dynamisk størrelse.

107
00:05:08,080 --> 00:05:09,040
>> DAVID MALAN: Dynamisk størrelse.

108
00:05:09,040 --> 00:05:11,890
Så mens der i array, skal du
kender sin størrelse på forhånd, når

109
00:05:11,890 --> 00:05:12,740
du tildele det.

110
00:05:12,740 --> 00:05:14,380
I linket liste, behøver du ikke
nødt til at vide det.

111
00:05:14,380 --> 00:05:17,610
Du kan bare malloc eller mere generelt,
afsætte yderligere

112
00:05:17,610 --> 00:05:20,720
node, så at sige, hver gang du
ønsker at indsætte flere data.

113
00:05:20,720 --> 00:05:22,670
Og node har ingen forudbestemt mening.

114
00:05:22,670 --> 00:05:25,580
Det er bare en generisk betegnelse, der beskriver
en slags container, at vi er

115
00:05:25,580 --> 00:05:29,610
hjælp i vores datastruktur til at lagre
nogle emne af interesse, som i dette

116
00:05:29,610 --> 00:05:31,750
tilfælde tilfældigvis være heltal.

117
00:05:31,750 --> 00:05:33,160
>> Men der er altid en afvejning.

118
00:05:33,160 --> 00:05:38,070
Så vi får dynamiske størrelser af data
struktur, men hvilken pris skal vi betale?

119
00:05:38,070 --> 00:05:40,040
Hvad er ulempen ved sammenkædede lister?

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

121
00:05:41,006 --> 00:05:41,980
>> PUBLIKUM: Kræver mere hukommelse.

122
00:05:41,980 --> 00:05:44,240
>> DAVID MALAN: Det kræver mere
hukommelse, præcis hvordan?

123
00:05:44,240 --> 00:05:46,440
>> PUBLIKUM: [uhørlig].

124
00:05:46,440 --> 00:05:47,050
>> DAVID MALAN: Præcis.

125
00:05:47,050 --> 00:05:50,460
Så nu har vi pointere at optage
ekstra hukommelse, som vi tidligere

126
00:05:50,460 --> 00:05:53,040
behøvede ikke, fordi fordelen
af en matrix, er naturligvis, at

127
00:05:53,040 --> 00:05:54,860
alt er op til hinanden, ryg
til tilbage til tilbage, som

128
00:05:54,860 --> 00:05:56,380
giver dig random access.

129
00:05:56,380 --> 00:06:00,710
Fordi blot ved hjælp af firkantede beslag
notation, eller mere teknisk pointer

130
00:06:00,710 --> 00:06:03,580
aritmetik, meget simpel addition,
kan du få adgang til alle

131
00:06:03,580 --> 00:06:05,700
elementer i konstant tid.

132
00:06:05,700 --> 00:06:08,975
Og faktisk er den slags antyde
anden pris, vi betaler med en

133
00:06:08,975 --> 00:06:09,760
linkede liste.

134
00:06:09,760 --> 00:06:13,890
>> Hvad sker der med køretiden for
noget som Search, hvis jeg ønsker at

135
00:06:13,890 --> 00:06:17,270
finde nogle værdi og inde
af en sammenkædet liste?

136
00:06:17,270 --> 00:06:20,290
Hvad betyder min køretid blevet?

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

138
00:06:21,560 --> 00:06:24,060
Hvis det er ordnet på?

139
00:06:24,060 --> 00:06:25,440
Hvad hvis datastrukturen er ordnet?

140
00:06:25,440 --> 00:06:28,640
Kan jeg gøre det bedre end store
O n til at søge?

141
00:06:28,640 --> 00:06:31,700
Nej, fordi det i værste fald kan det
meget vel blive sorteret, men antallet

142
00:06:31,700 --> 00:06:32,950
du leder efter kunne være stort.

143
00:06:32,950 --> 00:06:35,370
Det kan være nummer 100, som
kan ske at være alt

144
00:06:35,370 --> 00:06:36,410
måde ved udgangen.

145
00:06:36,410 --> 00:06:39,950
Og fordi du kun kan få adgang til en sammenkædet
listen i denne implementering af

146
00:06:39,950 --> 00:06:42,690
måde sin første node, er du
stadig slags ude af lykke.

147
00:06:42,690 --> 00:06:47,450
Du er nødt til at krydse det hele
fra først til sidst for at finde

148
00:06:47,450 --> 00:06:49,150
at store værdi som 100.

149
00:06:49,150 --> 00:06:51,350
Eller at afgøre, om det er
ikke engang der.

150
00:06:51,350 --> 00:06:55,960
>> Så vi kan ikke gøre, hvad algoritme i en data
struktur, der ligner dette?

151
00:06:55,960 --> 00:06:59,460
Vi kan ikke gøre binær søgning, fordi
binær søgning kræves, at vi havde

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

153
00:07:00,740 --> 00:07:04,500
Vi kunne bare springe fra sted til
placering uden at følge

154
00:07:04,500 --> 00:07:07,080
disse brødkrummer i form
af alle disse pejlemærker.

155
00:07:07,080 --> 00:07:08,300
>> Nu, hvordan kom vi gennemfører dette?

156
00:07:08,300 --> 00:07:12,830
Tja, hvis vi går til skærmen her, hvis
kan vi hurtigt reimplement disse data

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

158
00:07:13,440 --> 00:07:15,670
min håndskrift er ikke alt,
stor her, men vi vil forsøge.

159
00:07:15,670 --> 00:07:22,030
Så typedef struct, og hvad gjorde jeg
ønsker at kalde denne ting op her?

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

161
00:07:22,960 --> 00:07:24,580
Så jeg vil få os i gang.

162
00:07:24,580 --> 00:07:27,860
Og nu, hvad der skal være inde i
datastrukturen for denne enkeltvis

163
00:07:27,860 --> 00:07:28,430
linkede liste?

164
00:07:28,430 --> 00:07:29,950
Hvor mange felter?

165
00:07:29,950 --> 00:07:30,450
>> Så to.

166
00:07:30,450 --> 00:07:31,570
Den ene er temmelig let.

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

168
00:07:33,050 --> 00:07:35,930
Og vi kunne kalde n noget, vi ønsker,
men det skal være en int, hvis vi er

169
00:07:35,930 --> 00:07:37,660
gennemføre en linket liste til int'er.

170
00:07:37,660 --> 00:07:41,920
Og nu, hvad gør den anden
felt skal være?

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

172
00:07:43,460 --> 00:07:50,570
Så hvis jeg gør struct node *, og så er jeg
kan kalde dette også, hvad jeg vil,

173
00:07:50,570 --> 00:07:53,510
men bare for at være klar, jeg ringer
Det næste, som vi har gjort.

174
00:07:53,510 --> 00:07:55,270
Og så vil jeg lukke mine krøllede parenteser.

175
00:07:55,270 --> 00:08:00,700
>> Og nu, som sidste gang,
Jeg sætter node hernede.

176
00:08:00,700 --> 00:08:03,830
Men hvis jeg erklære dette er så en
node, hvorfor jeg gider at være så

177
00:08:03,830 --> 00:08:07,320
verbose her erklære struct
node * næste, i modsætning

178
00:08:07,320 --> 00:08:09,210
til lige node * næste?

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

180
00:08:09,904 --> 00:08:12,810
>> PUBLIKUM: [uhørlig].

181
00:08:12,810 --> 00:08:14,050
>> DAVID MALAN: Præcis.

182
00:08:14,050 --> 00:08:14,530
Præcis.

183
00:08:14,530 --> 00:08:18,320
Fordi C virkelig tager dig bogstaveligt og
kun ser definitionen af ​​node

184
00:08:18,320 --> 00:08:21,230
vej herned, du kan ikke
henvise til det heroppe.

185
00:08:21,230 --> 00:08:24,760
Så vi har denne form for forebyggende
erklæringen her, hvilket er ganske vist

186
00:08:24,760 --> 00:08:25,390
mere detaljeret.

187
00:08:25,390 --> 00:08:27,810
Struct knude, der betyder
kan vi nu få adgang til det

188
00:08:27,810 --> 00:08:29,760
indersiden af ​​datastruktur.

189
00:08:29,760 --> 00:08:33,370
>> Og som en sidebemærkning, fordi dette er
bliver lidt mere subjektive nu,

190
00:08:33,370 --> 00:08:36,230
stjernen kan teknisk gå her,
det kan gå her, det kan

191
00:08:36,230 --> 00:08:37,179
endda gå i midten.

192
00:08:37,179 --> 00:08:39,890
Vi har vedtaget, i stil guide for
kurset, konventionen om at sætte

193
00:08:39,890 --> 00:08:42,299
stjernen lige ved siden af ​​de data,
typen, som i dette tilfælde,

194
00:08:42,299 --> 00:08:43,460
ville være struct node.

195
00:08:43,460 --> 00:08:46,620
Men indse i en masse lærebøger og
online referencer, du måske faktisk

196
00:08:46,620 --> 00:08:48,450
se det på den anden side.

197
00:08:48,450 --> 00:08:52,200
Men bare indse, at begge vil faktisk
arbejde, og du bør simpelthen være

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

199
00:08:52,970 --> 00:08:53,580
>> Ok.

200
00:08:53,580 --> 00:08:55,630
Så det var vores erklæring
af struct node.

201
00:08:55,630 --> 00:08:59,430
Men så begyndte vi at gøre mere
sofistikerede ting.

202
00:08:59,430 --> 00:09:03,410
For eksempel har vi besluttet at indføre
noget som en hash tabel.

203
00:09:03,410 --> 00:09:08,160
Så her er en hash tabel med n,
indekseret fra 0 på øverste venstre hjørne til n

204
00:09:08,160 --> 00:09:09,690
minus 1 nederst til venstre.

205
00:09:09,690 --> 00:09:11,640
Dette kunne være en hash
tabel for noget.

206
00:09:11,640 --> 00:09:15,340
Men hvad slags ting gjorde vi taler
om at bruge en hash tabel for?

207
00:09:15,340 --> 00:09:18,370
Lagring hvad?

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

209
00:09:18,800 --> 00:09:20,870
Vi kunne gøre navne som
vi gjorde sidste gang.

210
00:09:20,870 --> 00:09:22,200
Og virkelig, du kan gemme noget.

211
00:09:22,200 --> 00:09:24,640
Og vi vil se det igen i
PHP og JavaScript.

212
00:09:24,640 --> 00:09:28,550
En hash tabel er en dejlig slags schweizisk
Army kniv, der giver dig mulighed for at gemme

213
00:09:28,550 --> 00:09:33,690
temmelig meget, hvad du ønsker inde i
det ved at knytte nøgler med værdier.

214
00:09:33,690 --> 00:09:34,770
Nøgler med værdier.

215
00:09:34,770 --> 00:09:37,800
>> Nu i denne simple tilfælde vores
nøgler er bare tal.

216
00:09:37,800 --> 00:09:40,380
Vi gennemføre en hash
tabel som en matrix.

217
00:09:40,380 --> 00:09:43,500
Og så tasterne er 0,
1, 2, og så videre.

218
00:09:43,500 --> 00:09:47,200
Og så vi, som mennesker, besluttede sidste
uge, at du ved, hvad, hvis vi er

219
00:09:47,200 --> 00:09:50,410
kommer til at gemme navne, lad os bare
vilkårligt, men temmelig rimeligt,

220
00:09:50,410 --> 00:09:54,680
antage, at Alice, en Et navn,
vil bare blive indekseret i 0.

221
00:09:54,680 --> 00:09:58,030
Og Bob, en B navn, vil blive indekseret
i 1, og så videre.

222
00:09:58,030 --> 00:10:02,490
Så vi havde en mapping mellem indgange,
der er strenge, og hash

223
00:10:02,490 --> 00:10:04,560
steder, der er tal.

224
00:10:04,560 --> 00:10:07,740
>> Således at processen er generelt kendt som
en hash-funktion, og du kan virkelig

225
00:10:07,740 --> 00:10:09,130
gennemføre den i koden.

226
00:10:09,130 --> 00:10:12,080
Hvis jeg ønskede at gennemføre en hash-funktion
der gør præcis, hvad vi

227
00:10:12,080 --> 00:10:17,070
netop beskrevet fra sidste gang, jeg måske
erklære en funktion, der tager som

228
00:10:17,070 --> 00:10:18,330
indgang for eksempel -

229
00:10:18,330 --> 00:10:22,190
og lad os gøre det på denne
skærmen herovre.

230
00:10:22,190 --> 00:10:26,180
Hvis jeg ønskede at gennemføre en hash
funktion, kan jeg sige

231
00:10:26,180 --> 00:10:27,410
noget som dette.

232
00:10:27,410 --> 00:10:29,030
>> Det kommer til at returnere en int.

233
00:10:29,030 --> 00:10:33,600
Det kommer til at blive kaldt hash, og det er
kommer til at acceptere som et argument et

234
00:10:33,600 --> 00:10:38,920
streng, eller vi kan være mere korrekt nu
og sige char *, vi kalder det er.

235
00:10:38,920 --> 00:10:43,840
Og så har denne funktion at gøre,
i sidste ende, er returnere en int.

236
00:10:43,840 --> 00:10:45,990
Nu, hvor det gør det måske
ikke være så klar.

237
00:10:45,990 --> 00:10:49,510
Jeg har tænkt mig at gennemføre dette uden
form for fejlkontrol lige nu.

238
00:10:49,510 --> 00:10:55,740
Jeg skal bare blindt sige, tilbage
hvad der er på s beslag 0, minus,

239
00:10:55,740 --> 00:10:58,850
lad os sige, hovedstad Et semikolon.

240
00:10:58,850 --> 00:10:59,960
>> Fuldstændig brudt.

241
00:10:59,960 --> 00:11:02,620
Det er ikke perfekt, fordi
én, hvad nu hvis s er ugyldig?

242
00:11:02,620 --> 00:11:04,000
Dårlige ting kommer til at ske.

243
00:11:04,000 --> 00:11:07,940
To, hvad nu hvis det første bogstav i denne
navn er ikke et stort bogstav?

244
00:11:07,940 --> 00:11:09,860
Det kommer ikke til at slå
godt ud enten.

245
00:11:09,860 --> 00:11:11,970
Det kan være et lille bogstav
eller ikke et bogstav overhovedet.

246
00:11:11,970 --> 00:11:15,520
Så helt plads til forbedringer her,
men dette er den grundlæggende idé.

247
00:11:15,520 --> 00:11:19,010
>> Hvad vi beskrev i sidste uge verbalt som
blot en proces kortlægning Alice til

248
00:11:19,010 --> 00:11:23,360
0 og Bob til 1. kan udtrykkes
sikkert mere formulaically som en C

249
00:11:23,360 --> 00:11:24,320
fungere her.

250
00:11:24,320 --> 00:11:28,630
Kaldes igen hash, tager en streng som
input, og så en eller anden måde gør noget

251
00:11:28,630 --> 00:11:31,020
med dette input til at producere et output.

252
00:11:31,020 --> 00:11:34,130
Ikke ulig vores sorte box beskrivelse
, som vi længe har gjort.

253
00:11:34,130 --> 00:11:36,550
Jeg ved ikke, hvordan dette kan være
arbejder under hætten.

254
00:11:36,550 --> 00:11:40,120
>> For problemet sæt 6, en af ​​udfordringerne
er for dig at beslutte, hvad

255
00:11:40,120 --> 00:11:41,920
vil dit hash-funktionen være?

256
00:11:41,920 --> 00:11:45,760
Hvad kommer til at være inde i den sorte
box, og formentlig vil det være en

257
00:11:45,760 --> 00:11:50,380
lidt mere interessant end dette, og
klart mere tilbøjelige til fejl

258
00:11:50,380 --> 00:11:53,180
kontrol end netop dette
gennemførelse.

259
00:11:53,180 --> 00:11:54,580
>> Men problemer kan opstå, right?

260
00:11:54,580 --> 00:11:57,760
Hvis vi har en datastruktur som denne
én, hvad er et af de problemer

261
00:11:57,760 --> 00:12:01,600
du kan løbe ind i, efterhånden som du indsætter
flere og flere navne i den

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

263
00:12:02,880 --> 00:12:04,630
Du får kollisioner, right?

264
00:12:04,630 --> 00:12:07,560
Hvad hvis du har Alice og Aron,
to personer, hvis navne er sket

265
00:12:07,560 --> 00:12:08,190
til at starte med A?

266
00:12:08,190 --> 00:12:11,660
Det rejser spørgsmålet, hvor du
sætte den anden sådan et navn?

267
00:12:11,660 --> 00:12:15,050
>> Nå, du måske naivt bare sætte det
hvor Bob tilhører, men så Bob er

268
00:12:15,050 --> 00:12:17,300
slags skruet hvis du forsøger at
indsætte hans navn næste og

269
00:12:17,300 --> 00:12:18,240
der er ikke plads til ham.

270
00:12:18,240 --> 00:12:21,400
Så du kan sætte Bob, hvor Charlie er,
og du kan forestille sig dette meget hurtigt

271
00:12:21,400 --> 00:12:23,020
uddelegere til lidt af en rod.

272
00:12:23,020 --> 00:12:25,600
Noget lineær i sidste ende, hvor du
bare nødt til at søge det hele

273
00:12:25,600 --> 00:12:28,190
søger Alice eller Bob
eller Aaron eller Charlie.

274
00:12:28,190 --> 00:12:33,230
>> Så i stedet har vi foreslået, i stedet for bare
lineært sondering for åbne rum

275
00:12:33,230 --> 00:12:36,450
og plopping navne der, vi
foreslået en amatør tilgang.

276
00:12:36,450 --> 00:12:41,740
En hash tabel implementeret stadig med et
vifte af indeks, men datatype

277
00:12:41,740 --> 00:12:44,500
disse indekser nu var pointere.

278
00:12:44,500 --> 00:12:47,360
Pointere til hvad?

279
00:12:47,360 --> 00:12:48,730
Henvisninger til hægtede lister.

280
00:12:48,730 --> 00:12:53,330
>> Fordi tilbagekaldelse, at en sammenkædet liste
egentlig bare en pointer til en knude, og

281
00:12:53,330 --> 00:12:57,110
knudepunktet har en næste felt, og denne node
har en næste felt, og så videre.

282
00:12:57,110 --> 00:13:00,690
Så kan du nu tænke på dette array på
den venstre side af en hash tabel som

283
00:13:00,690 --> 00:13:01,820
fører til en sammenkædet liste.

284
00:13:01,820 --> 00:13:07,000
Den fordel, som er, hvis du får en
kollision mellem Alice og Aron,

285
00:13:07,000 --> 00:13:09,300
hvad gør du med det
anden sådanne person?

286
00:13:09,300 --> 00:13:14,150
Du skal bare vedhæfte ham eller hende til
ende, eller endog begyndelsen

287
00:13:14,150 --> 00:13:15,490
af den linkede liste.

288
00:13:15,490 --> 00:13:17,340
>> Og faktisk, lad os bare noodle gennem
at for bare et sekund.

289
00:13:17,340 --> 00:13:18,640
Hvor ville give mest mening?

290
00:13:18,640 --> 00:13:22,060
Hvis jeg indsætter Alice og hun ender på
det første sted, så jeg prøver at

291
00:13:22,060 --> 00:13:25,310
indsæt Aaron navn, og der er
naturligvis en kollision, skal jeg sætte

292
00:13:25,310 --> 00:13:27,400
ham i begyndelsen
den linkede liste?

293
00:13:27,400 --> 00:13:30,944
Det er på det første sted,
eller i slutningen?

294
00:13:30,944 --> 00:13:31,440
>> PUBLIKUM: [uhørlig].

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

296
00:13:31,990 --> 00:13:32,490
Jeg hørte begyndt.

297
00:13:32,490 --> 00:13:33,903
Hvorfor i starten?

298
00:13:33,903 --> 00:13:34,750
>> PUBLIKUM: [uhørlig].

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

300
00:13:34,940 --> 00:13:36,520
Det er alfabetisk, så det er rart.

301
00:13:36,520 --> 00:13:37,330
Det er en god egenskab.

302
00:13:37,330 --> 00:13:39,335
Det vil spare mig noget tid potentielt.

303
00:13:39,335 --> 00:13:43,290
Det vil ikke lade mig gøre binær søgning, men jeg
kunne i det mindste være i stand til at bryde ud

304
00:13:43,290 --> 00:13:47,340
af en løkke, hvis jeg indser, ja, jeg er vejen
fortiden var Aaron ville være i denne

305
00:13:47,340 --> 00:13:48,310
sorteret forbundet liste.

306
00:13:48,310 --> 00:13:50,360
Jeg behøver ikke at spilde min tid på at kigge
hele vejen til enden.

307
00:13:50,360 --> 00:13:51,530
Så det er rimeligt.

308
00:13:51,530 --> 00:13:54,710
Hvorfor ellers kan du indsætte
det kolliderende navn i

309
00:13:54,710 --> 00:13:56,660
begyndelse af listen?

310
00:13:56,660 --> 00:13:57,397
Hvad er det?

311
00:13:57,397 --> 00:13:58,680
>> PUBLIKUM: [uhørlig].

312
00:13:58,680 --> 00:14:00,820
>> DAVID MALAN: Det kan tage lang tid
for at komme til slutningen af ​​listen.

313
00:14:00,820 --> 00:14:02,490
Og i virkeligheden,. Længere og længere

314
00:14:02,490 --> 00:14:04,920
Jo flere navne, du indsætter, at
starter med A, jo længere at

315
00:14:04,920 --> 00:14:06,280
kæden kommer til at få.

316
00:14:06,280 --> 00:14:07,890
Jo længere der er forbundet
liste vil få.

317
00:14:07,890 --> 00:14:09,420
Så du er virkelig bare
spilder din tid.

318
00:14:09,420 --> 00:14:14,070
Måske er du bedre stillet opretholdelse
konstant indsættelse tid, store O i 1,

319
00:14:14,070 --> 00:14:18,470
ved altid at sætte kolliderende navnet på
begyndelsen af ​​den linkede liste,

320
00:14:18,470 --> 00:14:21,230
og ikke bekymre sig så meget
om sortering.

321
00:14:21,230 --> 00:14:22,600
>> Hvad er det bedste svar?

322
00:14:22,600 --> 00:14:23,320
Det er uklart.

323
00:14:23,320 --> 00:14:26,140
Den slags afhænger af, hvad
fordelingen er, hvad det mønster er

324
00:14:26,140 --> 00:14:27,850
af de navne, du indsætter.

325
00:14:27,850 --> 00:14:29,430
Det er ikke nødvendigvis
et indlysende svar.

326
00:14:29,430 --> 00:14:33,100
Men her til, igen, er
et design muligheder.

327
00:14:33,100 --> 00:14:37,220
>> Så vi så på denne ting, som
er virkelig den anden store mulighed

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

329
00:14:38,180 --> 00:14:41,770
Og indse, hvis du ikke allerede har,
Zamyla dykker ned begge disse, hash

330
00:14:41,770 --> 00:14:43,260
tabeller og forsøger, mere detaljeret.

331
00:14:43,260 --> 00:14:45,630
Og videogennemgang er
indlejret i p-set spec.

332
00:14:45,630 --> 00:14:46,590
Dette var en trie -

333
00:14:46,590 --> 00:14:51,670
T-R-I-E. Og hvad var interessant ved
dette var, at køretiden

334
00:14:51,670 --> 00:14:59,510
for at søge efter et navn, ligesom Maxwell
sidste gang, var store O af hvad?

335
00:14:59,510 --> 00:15:01,040
Hvad er det?

336
00:15:01,040 --> 00:15:01,920
>> PUBLIKUM: Antallet af bogstaver.

337
00:15:01,920 --> 00:15:02,550
>> DAVID MALAN: Antallet af bogstaver.

338
00:15:02,550 --> 00:15:03,210
Jeg hørte to ting.

339
00:15:03,210 --> 00:15:04,630
Antallet af breve og konstant tid.

340
00:15:04,630 --> 00:15:05,540
Så lad os gå med det første.

341
00:15:05,540 --> 00:15:06,410
Antallet af bogstaver.

342
00:15:06,410 --> 00:15:10,195
Nå, dette datastruktur, tilbagekaldelse, er
som et træ, et stamtræ, som hver

343
00:15:10,195 --> 00:15:12,860
hvis knudepunkter består af arrays.

344
00:15:12,860 --> 00:15:16,300
Og de arrays er henvisninger til
andre sådanne knudepunkter eller andre sådanne

345
00:15:16,300 --> 00:15:17,670
arrays i træet.

346
00:15:17,670 --> 00:15:22,890
>> Så hvis vi ønskede at derefter afgøre
hvorvidt Maxwell er her, kan jeg gå

347
00:15:22,890 --> 00:15:26,890
til den første array, på toppen af
træet, den såkaldte rod, top

348
00:15:26,890 --> 00:15:30,521
den trie, og følg derefter m pointer,
derefter en pegepind, så X,

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

350
00:15:31,710 --> 00:15:34,910
Og så når jeg ser nogle særlige symbol,
betegnes her som en trekant.

351
00:15:34,910 --> 00:15:38,480
I koden vil du se foreslår vi, at du
implementeret som en bool, bare at sige ja

352
00:15:38,480 --> 00:15:40,540
eller nej, et ord stopper her.

353
00:15:40,540 --> 00:15:45,270
>> Nå, når vi har gået til M-A-X-W-E-L-L,
føles som syv, måske

354
00:15:45,270 --> 00:15:48,910
otte hvis vi går en forbi den, otte
trin for at finde Maxwell.

355
00:15:48,910 --> 00:15:53,050
Eller lad os kalde det K. Men husker sidste
gang, jeg fremførte, at hvis der er

356
00:15:53,050 --> 00:15:57,540
realistisk en maksimal længde på en
word, ligesom 40-nogle-ulige antal tegn, en

357
00:15:57,540 --> 00:16:00,810
maksimale længde indebærer
en konstant værdi.

358
00:16:00,810 --> 00:16:05,770
Så virkelig, ja, det er teknisk set stort O
på 8 eller 7, eller virkelig store O i K. Men

359
00:16:05,770 --> 00:16:09,420
hvis der er en udtømmelig cap på, hvad
K kunne være, er det en konstant.

360
00:16:09,420 --> 00:16:12,080
Og så det er big O i 1 ved
slutningen af ​​dagen.

361
00:16:12,080 --> 00:16:13,040
>> Ikke i den virkelige verden.

362
00:16:13,040 --> 00:16:15,960
Ikke når du rent faktisk begynde at se
dit ur som dit program kører.

363
00:16:15,960 --> 00:16:20,690
Det er absolut kommer til at være en smule
langsommere end virkelig konstant

364
00:16:20,690 --> 00:16:21,840
tid med et trin.

365
00:16:21,840 --> 00:16:25,540
Det kommer til at være syv eller otte trin,
men stadig det er meget, meget bedre

366
00:16:25,540 --> 00:16:30,080
end en algoritme som store O n at
afhænger af størrelsen af ​​hvad der er i

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

368
00:16:31,220 --> 00:16:34,970
>> Bemærk opadrettede her er at vi kan indsætte
en million flere navne i denne

369
00:16:34,970 --> 00:16:38,170
datastruktur, men hvor mange flere trin
det kommer til at tage os med at finde

370
00:16:38,170 --> 00:16:40,480
Maxwell i denne sag?

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

372
00:16:40,780 --> 00:16:41,820
Han er upåvirket.

373
00:16:41,820 --> 00:16:45,480
Og til dato, tror jeg ikke, vi har set
et eksempel på en datastruktur eller et

374
00:16:45,480 --> 00:16:48,560
algoritme, der var helt
upåvirket af ydre

375
00:16:48,560 --> 00:16:50,040
adfærd som det.

376
00:16:50,040 --> 00:16:51,160
Men det kan ikke være fantastisk.

377
00:16:51,160 --> 00:16:52,900
Dette kan ikke være den eneste løsning
for p-sæt

378
00:16:52,900 --> 00:16:53,570
>> Og det er ikke.

379
00:16:53,570 --> 00:16:55,980
Dette er ikke nødvendigvis de data,
struktur, du skal drages til,

380
00:16:55,980 --> 00:16:58,220
fordi ligesom hash tabeller, tradeoff.

381
00:16:58,220 --> 00:17:00,500
Hvad er den pris, du betaler her?

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

383
00:17:00,940 --> 00:17:02,890
Jeg mener, dette er en grusomme
mængde hukommelse.

384
00:17:02,890 --> 00:17:05,569
Og du kan ikke helt se det her, fordi
forfatteren af ​​dette billede

385
00:17:05,569 --> 00:17:09,420
naturligvis afkortet alle arrays,
og vi er ikke at se masser af A s og

386
00:17:09,420 --> 00:17:12,700
B og C s og Q og Y'er
og Z er i disse arrays.

387
00:17:12,700 --> 00:17:13,630
Men de er der.

388
00:17:13,630 --> 00:17:17,660
>> Hver af disse knudepunkter er en hel række
af omkring 26 eller flere byte, som hver

389
00:17:17,660 --> 00:17:19,170
som repræsenterer et brev.

390
00:17:19,170 --> 00:17:22,920
27 i vores tilfælde, så vi kan understøtte
apostroffer i problemet sættet.

391
00:17:22,920 --> 00:17:27,030
Så dette datastruktur er rigtig,
virkelig tæt og bredt.

392
00:17:27,030 --> 00:17:30,880
Og det alene kan ende langsommere
ting ned, eller i det mindste koster dig en

393
00:17:30,880 --> 00:17:32,240
meget mere plads.

394
00:17:32,240 --> 00:17:34,020
Men igen, kan vi drage
sammenligninger her.

395
00:17:34,020 --> 00:17:39,190
>> Recall et stykke tid tilbage, vi opnået meget
mere spændende køretid i sortering

396
00:17:39,190 --> 00:17:42,880
når vi bruger merge slags, men prisen
Vi betalte for at opnå n log n for sammenfletningen

397
00:17:42,880 --> 00:17:46,930
sortere krævede, at vi bruger
mere, hvad ressource?

398
00:17:46,930 --> 00:17:47,690
Mere plads.

399
00:17:47,690 --> 00:17:50,530
Vi havde brug for en sekundær array til
kopiere folk ind, ligesom

400
00:17:50,530 --> 00:17:51,620
vi gjorde her på scenen.

401
00:17:51,620 --> 00:17:55,880
Så igen ingen klare vindere,
men blot subjektive design

402
00:17:55,880 --> 00:17:57,710
beslutninger, der skal foretages.

403
00:17:57,710 --> 00:17:58,060
>> Ok.

404
00:17:58,060 --> 00:17:59,130
Så hvordan omkring dette?

405
00:17:59,130 --> 00:18:02,050
Nogen genkender som D-Hall?

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

407
00:18:02,440 --> 00:18:03,170
Så tre af os gør.

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

409
00:18:03,750 --> 00:18:05,070
Så dette er for Mathers spisning.

410
00:18:05,070 --> 00:18:09,650
Jeg vil vædde alle de spisesale har
stakke af bakker som denne.

411
00:18:09,650 --> 00:18:11,950
Og det er faktisk repræsentativ
af noget, vi har

412
00:18:11,950 --> 00:18:13,050
naturligvis set allerede.

413
00:18:13,050 --> 00:18:14,850
Vi kaldte det bogstaveligt talt en stabel.

414
00:18:14,850 --> 00:18:18,970
Og stakken, i form af din
computerens hukommelse, er, hvor data går

415
00:18:18,970 --> 00:18:20,460
mens funktioner bliver kaldt.

416
00:18:20,460 --> 00:18:23,410
>> For eksempel går, hvad slags ting
på stakken med hensyn til

417
00:18:23,410 --> 00:18:27,420
memory layout vi har diskuteret
i uger tidligere?

418
00:18:27,420 --> 00:18:28,736
Hvad er det?

419
00:18:28,736 --> 00:18:29,670
>> PUBLIKUM: Opkald til funktioner.

420
00:18:29,670 --> 00:18:30,260
>> DAVID MALAN: Undskyld.

421
00:18:30,260 --> 00:18:31,210
>> PUBLIKUM: Opkald til funktioner.

422
00:18:31,210 --> 00:18:33,590
>> DAVID MALAN: Opkald til funktioner, men
specifikt hvad der er inde i hver af

423
00:18:33,590 --> 00:18:35,340
disse rammer?

424
00:18:35,340 --> 00:18:37,220
Hvilke ting?

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

426
00:18:37,460 --> 00:18:38,500
Så lokale variable.

427
00:18:38,500 --> 00:18:43,080
Når som helst vi havde brug for nogle lokale lagring,
som en argument eller int I eller int

428
00:18:43,080 --> 00:18:45,940
temp, eller hvad den lokale
variabel, vi har været

429
00:18:45,940 --> 00:18:47,210
sætte det på stakken.

430
00:18:47,210 --> 00:18:49,610
Og vi kalder det en stak, fordi
af denne lagdeling idé.

431
00:18:49,610 --> 00:18:52,940
Bare slags kampe op med virkeligheden,
begrebet deraf.

432
00:18:52,940 --> 00:18:56,650
>> Men det viser sig, at en stabel kan også
ses som en datastruktur, en

433
00:18:56,650 --> 00:19:00,110
alternativ til en matrix, en alternativ
til en sammenkædet liste.

434
00:19:00,110 --> 00:19:02,770
Noget begrebsmæssigt mere interessant
der kan stadig være

435
00:19:02,770 --> 00:19:06,030
gennemføres ved hjælp af en af ​​disse
ting, men det er en anden type

436
00:19:06,030 --> 00:19:09,140
datastruktur der understøtter, virkelig,
kun to operationer.

437
00:19:09,140 --> 00:19:11,000
Men du kan tilføje mere avanceret
funktioner end disse.

438
00:19:11,000 --> 00:19:12,180
Men disse er grundlæggende -

439
00:19:12,180 --> 00:19:13,510
skubbe og pop.

440
00:19:13,510 --> 00:19:19,240
>> Og ideen med en stak er, at hvis jeg
har her, med eller uden Annenberg

441
00:19:19,240 --> 00:19:22,880
vel vidende, en bakke fra næste dør
med nummeret 9 på det.

442
00:19:22,880 --> 00:19:23,870
Så bare en int.

443
00:19:23,870 --> 00:19:26,990
Og jeg ønsker at skubbe dette på de data,
struktur, som i øjeblikket er tom.

444
00:19:26,990 --> 00:19:28,790
Betragt dette bunden af ​​stakken.

445
00:19:28,790 --> 00:19:33,150
Jeg vil skubbe denne nummer 9 på
stak, og nu er det lige der.

446
00:19:33,150 --> 00:19:36,040
>> Men det interessante ved en stak
er, at hvis jeg nu ønsker at presse

447
00:19:36,040 --> 00:19:40,210
en anden værdi, ligesom 17, og jeg skubbe
dette på stakken, vil jeg gøre

448
00:19:40,210 --> 00:19:43,290
det eneste intuitive ting, jeg bare
at sige det lige der, hvor vi mennesker

449
00:19:43,290 --> 00:19:45,180
ville være tilbøjelig til at sætte det på toppen.

450
00:19:45,180 --> 00:19:48,850
Men hvad er interessant nu
er, hvordan får jeg ved 9?

451
00:19:48,850 --> 00:19:50,670
Du ved, det gør jeg ikke uden en vis indsats.

452
00:19:50,670 --> 00:19:54,070
>> Så hvad er interessant ved
en stak er, at ved design,

453
00:19:54,070 --> 00:19:56,330
det er en LIFO datastruktur.

454
00:19:56,330 --> 00:19:59,680
Silly måde at beskrive
sidste ind, først ud.

455
00:19:59,680 --> 00:20:03,280
Så det sidste nummer i
på dette tidspunkt var 17.

456
00:20:03,280 --> 00:20:07,540
Så hvis jeg ønsker at pop noget fra
af stakken, kan det kun være 17..

457
00:20:07,540 --> 00:20:11,890
Så der er en obligatorisk rækkefølge
operationer her, hvor det sidste punkt

458
00:20:11,890 --> 00:20:14,260
i har at være den første ud.

459
00:20:14,260 --> 00:20:16,440
Derfor akronym, LIFO.

460
00:20:16,440 --> 00:20:19,160
>> Så hvorfor kan det være nyttigt?

461
00:20:19,160 --> 00:20:22,690
Er deres sammenhænge, ​​hvor du ville
ønsker en datastruktur som dette?

462
00:20:22,690 --> 00:20:24,810
Nå, det helt sikkert været nyttigt
indersiden af ​​en computer.

463
00:20:24,810 --> 00:20:29,050
Så operativsystemer klart bruge dette
type datastruktur stakke.

464
00:20:29,050 --> 00:20:32,800
Vi vil også se den samme idé
når det kommer til websider.

465
00:20:32,800 --> 00:20:35,890
Så denne uge og næste uge, og ud over,
og som du begynder at gennemføre web

466
00:20:35,890 --> 00:20:39,490
sider i et sprog kaldet HTML, kan du
faktisk bruger en datastruktur som

467
00:20:39,490 --> 00:20:42,690
dette at afgøre, om side
er korrekt formateret.

468
00:20:42,690 --> 00:20:47,170
Fordi vi vil se alle websider følger
en slags hierarki, en indskæring

469
00:20:47,170 --> 00:20:52,030
der vil ved slutningen af ​​dagen, være en
træstruktur under hætten.

470
00:20:52,030 --> 00:20:53,620
Så mere om det i bare en smule.

471
00:20:53,620 --> 00:20:56,560
>> Men for nu, lad os foreslå en
øjeblik, hvordan kunne vi gå om

472
00:20:56,560 --> 00:20:58,830
repræsenterer, hvad en stak er?

473
00:20:58,830 --> 00:21:03,370
Lad mig foreslå, at vi gennemfører
en stak med kode som dette.

474
00:21:03,370 --> 00:21:07,990
Så en stak kommer til at have inde i det
to ting, en vifte, kaldet bakker,

475
00:21:07,990 --> 00:21:09,510
bare for at være i overensstemmelse med demo.

476
00:21:09,510 --> 00:21:12,660
Og hver af punkterne i denne matrix
vil være en type int.

477
00:21:12,660 --> 00:21:14,740
Og kapaciteten er formentlig hvad?

478
00:21:14,740 --> 00:21:18,796
Fordi jeg ikke har skrevet
fulde definition her.

479
00:21:18,796 --> 00:21:21,535
>> Det er nok det maksimale
størrelse af matrixen.

480
00:21:21,535 --> 00:21:25,150
Og det er nok erklæret som en skarp
defineres på toppen af ​​filen, nogle

481
00:21:25,150 --> 00:21:28,450
slags konstant som antydes af
den blotte kapitalisering.

482
00:21:28,450 --> 00:21:32,250
Så sted kapacitet er defineret
som den maksimale mulige størrelse.

483
00:21:32,250 --> 00:21:35,590
I mellemtiden, indersiden af ​​datastruktur
kendt som en stak vil der

484
00:21:35,590 --> 00:21:38,630
være et heltal bare kendt
blot som størrelse.

485
00:21:38,630 --> 00:21:43,400
>> Så hvis jeg skulle repræsentere det nu
billedligt, lad os antage, at dette

486
00:21:43,400 --> 00:21:48,070
Hele sorte boks repræsenterer mit stack.

487
00:21:48,070 --> 00:21:50,070
Inde i det er to variable.

488
00:21:50,070 --> 00:21:54,780
Så jeg har tænkt mig at tegne
første som størrelse.

489
00:21:54,780 --> 00:21:57,420
Og det andet, jeg har tænkt mig
at tegne som en matrix.

490
00:21:57,420 --> 00:22:01,060
>> Men bare for at holde tingene ordnet,
normalt ville jeg trække et array som

491
00:22:01,060 --> 00:22:04,910
dette, men det er slags nice
hvis vi matche virkeligheden, eller

492
00:22:04,910 --> 00:22:06,230
matche den mentale model.

493
00:22:06,230 --> 00:22:12,880
Så lad mig i stedet trække array
lodret, hvilket er lige, igen,

494
00:22:12,880 --> 00:22:13,840
kunstners gengivelse.

495
00:22:13,840 --> 00:22:16,610
Er faktisk ligegyldigt, hvad det
er under hætten.

496
00:22:16,610 --> 00:22:20,350
Og vi vil sige, at som standard
kapaciteten vil være tre.

497
00:22:20,350 --> 00:22:23,480
Så dette vil være placering 0, dette
vil være location 1, dette

498
00:22:23,480 --> 00:22:25,740
vil være location 2..

499
00:22:25,740 --> 00:22:29,330
>> Hvis jeg bestikke med en stress bold, ville
nogen kan lide at komme op og køre

500
00:22:29,330 --> 00:22:30,870
bord her for blot et øjeblik?

501
00:22:30,870 --> 00:22:31,960
OK, så din hånd først.

502
00:22:31,960 --> 00:22:33,950
Kom op.

503
00:22:33,950 --> 00:22:36,500
Ok.

504
00:22:36,500 --> 00:22:38,760
Så jeg tror, ​​det er Steven.

505
00:22:38,760 --> 00:22:40,035
Kom op.

506
00:22:40,035 --> 00:22:40,770
Ok.

507
00:22:40,770 --> 00:22:46,760
>> Men forestil vi nu tilbage til den oprindelige
tilstand i verden, hvor jeg

508
00:22:46,760 --> 00:22:52,180
har netop erklæret en stak, og det er
vil være kapacitet tre.

509
00:22:52,180 --> 00:22:54,470
Men størrelse er endnu ikke fastlagt.

510
00:22:54,470 --> 00:22:56,100
Bakker er endnu ikke fastlagt.

511
00:22:56,100 --> 00:22:57,300
Så et par spørgsmål først.

512
00:22:57,300 --> 00:23:01,310
Og lad mig give dig mic, så du kan
deltage mere aktivt i dette.

513
00:23:01,310 --> 00:23:05,190
>> Så hvad er inde i størrelse i dette øjeblik
i tide, hvis alt hvad jeg har gjort, er

514
00:23:05,190 --> 00:23:09,340
erklæret en stak med
én linje kode?

515
00:23:09,340 --> 00:23:10,100
>> STEVEN: Ikke meget.

516
00:23:10,100 --> 00:23:12,080
>> DAVID MALAN: OK, ikke meget.

517
00:23:12,080 --> 00:23:14,410
Ved vi, hvad der er inde i størrelse,
ved vi, hvad der er indeni

518
00:23:14,410 --> 00:23:16,330
af dette array her?

519
00:23:16,330 --> 00:23:18,630
>> STEVEN: Just tilfældig kode, right?

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

521
00:23:20,220 --> 00:23:23,230
>> DAVID MALAN: Ja, jeg går til
kalder det kode, men random -

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

523
00:23:23,820 --> 00:23:28,290
>> DAVID MALAN: Ting som tilfældig

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

525
00:23:28,870 --> 00:23:29,530
>> DAVID MALAN: Bits, right?

526
00:23:29,530 --> 00:23:31,190
Så skrald værdier? Ret

527
00:23:31,190 --> 00:23:33,470
Så permutationer af 0'er og 1'er.

528
00:23:33,470 --> 00:23:35,920
Rester af tidligere kutymer
af denne hukommelse.

529
00:23:35,920 --> 00:23:38,150
Og vi ved ikke rigtig, hvad de værdier
er, så vi typisk trække dem

530
00:23:38,150 --> 00:23:38,930
som spørgsmålstegn.

531
00:23:38,930 --> 00:23:41,990
>> Så den første ting, vi er formentlig
lyst til at gøre her -

532
00:23:41,990 --> 00:23:46,630
og lad mig give dette felt inde
af der et navn - bakker.

533
00:23:46,630 --> 00:23:49,540
Hvad skal vi formentlig initialisere
størrelse til, hvis vi ønsker at

534
00:23:49,540 --> 00:23:51,040
begynde at bruge denne stak?

535
00:23:51,040 --> 00:23:53,070
>> STEVEN: Bakke er sub 3..

536
00:23:53,070 --> 00:23:53,910
>> DAVID MALAN: Så OK.

537
00:23:53,910 --> 00:23:56,710
For at være klar, er kapaciteten erklæret
andre steder som tre.

538
00:23:56,710 --> 00:23:58,570
Og det er hvad jeg har brugt
at tildele array.

539
00:23:58,570 --> 00:24:03,535
Størrelse vil henvise til, hvor mange
bakker er i øjeblikket på stakken.

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

541
00:24:03,880 --> 00:24:04,460
>> DAVID MALAN: Så det skal være nul.

542
00:24:04,460 --> 00:24:07,760
Så gå videre og med alle finger,
tegne en nul i størrelse.

543
00:24:07,760 --> 00:24:08,440
Ok.

544
00:24:08,440 --> 00:24:10,920
Så nu, hvad der er inde i dette
her ved vi ikke.

545
00:24:10,920 --> 00:24:12,160
Disse er egentlig bare skrald værdier.

546
00:24:12,160 --> 00:24:14,800
Så vi kunne trække spørgsmålstegn, men
lad os holde bestyrelsen rent for nu

547
00:24:14,800 --> 00:24:16,300
fordi det ikke betyder noget
hvad der er.

548
00:24:16,300 --> 00:24:19,130
Vi behøver ikke at initialisere array
til noget, for hvis vi ved, at

549
00:24:19,130 --> 00:24:23,100
størrelsen af ​​stakken er nul, godt, vi
bør ikke se på noget i

550
00:24:23,100 --> 00:24:25,590
dette array alligevel på
dette tidspunkt.

551
00:24:25,590 --> 00:24:29,970
>> Så nu antage, at jeg skubber
nummer 9 på stakken.

552
00:24:29,970 --> 00:24:33,750
Hvordan skal vi opdaterer datastruktur
inde i denne sorte boks?

553
00:24:33,750 --> 00:24:35,540
Hvilke værdier skal ændre?

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

555
00:24:36,200 --> 00:24:37,400
størrelsen?

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

557
00:24:37,650 --> 00:24:38,770
Størrelse bør blive det?

558
00:24:38,770 --> 00:24:39,580
>> STEVEN: Size ville være én.

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

560
00:24:39,870 --> 00:24:41,110
Så størrelse bør blive en.

561
00:24:41,110 --> 00:24:42,540
Så du kan gøre dette på et par måder.

562
00:24:42,540 --> 00:24:46,920
Lad mig give dig, nu er din
finger er et viskelæder.

563
00:24:46,920 --> 00:24:47,260
Ok.

564
00:24:47,260 --> 00:24:49,960
Så nu er din finger er en pensel.

565
00:24:49,960 --> 00:24:50,330
Ok.

566
00:24:50,330 --> 00:24:52,820
Og nu, hvad andre har at ændre,
naturligvis i datastrukturen?

567
00:24:52,820 --> 00:24:57,060
>> STEVEN: Vi går fra
bottom up til 9.

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

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

570
00:24:58,420 --> 00:25:01,550
Så stadig ikke ligegyldigt, hvad der er på
placering en eller to, fordi de er

571
00:25:01,550 --> 00:25:04,520
skrald værdier, men vi skal ikke genere
ser der, fordi størrelse er

572
00:25:04,520 --> 00:25:07,540
fortæller os, at kun det første element
er faktisk legitimt.

573
00:25:07,540 --> 00:25:10,400
Så nu jeg skubbe 17 på listen.

574
00:25:10,400 --> 00:25:11,830
Hvad sker der med billedet?

575
00:25:11,830 --> 00:25:14,720
>> STEVEN: So størrelse kommer til at gå til to.

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

577
00:25:15,300 --> 00:25:16,070
Du er viskelæder -

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

579
00:25:16,810 --> 00:25:18,026
Du er et viskelæder.

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

581
00:25:18,840 --> 00:25:19,720
>> DAVID MALAN: Du er en pensel.

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

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

584
00:25:20,920 --> 00:25:21,600
Og hvad ellers?

585
00:25:21,600 --> 00:25:22,600
>> STEVEN: Og så har vi -

586
00:25:22,600 --> 00:25:22,915
>> DAVID MALAN: Vi pressede 17..

587
00:25:22,915 --> 00:25:24,760
>> STEVEN: Vi holder 17 på toppen, så -

588
00:25:24,760 --> 00:25:25,710
>> DAVID MALAN: OK, godt.

589
00:25:25,710 --> 00:25:27,040
>> STEVEN: - drop det ned.

590
00:25:27,040 --> 00:25:27,530
>> DAVID MALAN: Okay.

591
00:25:27,530 --> 00:25:27,940
Det bliver let.

592
00:25:27,940 --> 00:25:29,300
Jeg har ikke tænkt til at hjælpe dig denne gang.

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

594
00:25:30,510 --> 00:25:31,720
>> STEVEN: Udført.

595
00:25:31,720 --> 00:25:34,870
At blive et viskelæder.

596
00:25:34,870 --> 00:25:37,340
Jeg bliver en pensel.

597
00:25:37,340 --> 00:25:39,340
Og så jeg lægger 22.

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

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

600
00:25:40,620 --> 00:25:41,380
Så en gang mere.

601
00:25:41,380 --> 00:25:44,280
Jeg vil nu til at skubbe
på stakken 26.

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

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

604
00:25:50,278 --> 00:25:52,520
Du har virkelig fangede mig ud vagt.

605
00:25:52,520 --> 00:25:53,703
>> DAVID MALAN: Du gjorde det ikke
se det komme?

606
00:25:53,703 --> 00:25:55,930
>> STEVEN: Jeg kunne ikke se det komme.

607
00:25:55,930 --> 00:25:58,756
Kunne vi re-oprindelige kapacitet?

608
00:25:58,756 --> 00:25:59,790
>> DAVID MALAN: Det er et godt spørgsmål.

609
00:25:59,790 --> 00:26:02,360
Så vi har slags malet os
i et hjørne her.

610
00:26:02,360 --> 00:26:06,740
Der er virkelig ingen god ud for Steven
fordi vi har afsat dette array

611
00:26:06,740 --> 00:26:09,130
statisk, så at sige, inde
over den datastruktur.

612
00:26:09,130 --> 00:26:12,170
Og vi har stort set hårdt kodet
det er af størrelse tre.

613
00:26:12,170 --> 00:26:14,170
Så vi kan ikke rigtig omfordele det.

614
00:26:14,170 --> 00:26:20,020
>> Vi kunne, hvis vi gik igen, vi
omdefineret bakker at være en pointer,

615
00:26:20,020 --> 00:26:22,300
vi så bruge malloc ved hånden hukommelse til.

616
00:26:22,300 --> 00:26:25,050
Fordi hvis vi fik den hukommelse,
den bunke via malloc, vi

617
00:26:25,050 --> 00:26:26,430
kunne derefter frigøre det.

618
00:26:26,430 --> 00:26:29,630
Men før at frigøre det, kunne vi
omfordele en større bid af hukommelse,

619
00:26:29,630 --> 00:26:31,330
opdatere markøren, og så videre.

620
00:26:31,330 --> 00:26:33,500
Men for nu, er det virkelig
det bedste, vi kan gøre.

621
00:26:33,500 --> 00:26:36,360
Skubbe og pop er formentlig gå
nødt til at signalere nogle fejl.

622
00:26:36,360 --> 00:26:40,270
>> Så for eksempel, implementering vores
push kunne returnere en bool, der

623
00:26:40,270 --> 00:26:42,390
tidligere returnerede sandt, sandt, sandt.

624
00:26:42,390 --> 00:26:48,390
Men fjerde gang, det kommer til at have
at returnere falsk, f.eks.

625
00:26:48,390 --> 00:26:48,540
Ok.

626
00:26:48,540 --> 00:26:49,540
Meget godt klaret.

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

628
00:26:50,060 --> 00:26:52,160
Du har fortjent din stress bold i dag.

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

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

631
00:26:54,382 --> 00:26:55,680
>> DAVID MALAN: Tak.

632
00:26:55,680 --> 00:26:59,740
OK, så dette synes ikke at være meget
et skridt fremad, right?

633
00:26:59,740 --> 00:27:01,410
Vi beskrev denne datastruktur.

634
00:27:01,410 --> 00:27:02,320
Det har været overbevisende, right?

635
00:27:02,320 --> 00:27:03,200
Operativsystemer lide det.

636
00:27:03,200 --> 00:27:06,360
Tilsyneladende nettet kan gøre brug af denne,
og andre applikationer stille.

637
00:27:06,360 --> 00:27:10,870
Men hvad en dum begrænsning, at vi er
tilbage til slags uge to grænser

638
00:27:10,870 --> 00:27:12,880
hvor vi har fast størrelse arrays.

639
00:27:12,880 --> 00:27:15,010
>> Så der er faktisk et par
måder, hvorpå vi kan løse dette.

640
00:27:15,010 --> 00:27:18,750
Vi kunne dynamisk tildele array,
ikke ved hårdt kodning det som jeg har

641
00:27:18,750 --> 00:27:22,600
gjort her, men i stedet re-erklære
dette, bare for at være klar, da

642
00:27:22,600 --> 00:27:23,830
noget som dette.

643
00:27:23,830 --> 00:27:29,040
Int * bakker ikke beslutte
på en kapacitet endnu.

644
00:27:29,040 --> 00:27:35,460
Men når jeg erklærer stakken andetsteds
i min kode, jeg kunne derefter kalde malloc,

645
00:27:35,460 --> 00:27:38,250
få adressen på en luns af
hukommelse, og jeg kunne tildele

646
00:27:38,250 --> 00:27:39,980
denne adresse til bakker.

647
00:27:39,980 --> 00:27:43,340
>> Og så, fordi det er bare en luns af
hukommelse, kunne jeg fortsætte med at bruge firkantede

648
00:27:43,340 --> 00:27:45,450
beslag notation på den sædvanlige måde.

649
00:27:45,450 --> 00:27:49,020
Fordi igen, er der er en slags dette
funktionel ækvivalent af arrays og

650
00:27:49,020 --> 00:27:50,820
bidder af hukommelse, der kommer
tilbage fra malloc.

651
00:27:50,820 --> 00:27:53,090
Vi kan behandle ene som det andet
hjælp pointer aritmetik eller

652
00:27:53,090 --> 00:27:54,440
firkantede beslag notation.

653
00:27:54,440 --> 00:27:55,660
Så det er en tilgang.

654
00:27:55,660 --> 00:28:00,120
>> Men hvordan man ellers kunne vi gennemføre denne
samme datastruktur, potentielt?

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

656
00:28:00,280 --> 00:28:04,530
Jeg føler, at vi bare løst dette
problem som for en uge siden.

657
00:28:04,530 --> 00:28:08,860
Hvad var løsningen på dette problem
at Steven løb ind?

658
00:28:08,860 --> 00:28:10,370
Så hægtede lister, til højre.

659
00:28:10,370 --> 00:28:13,410
>> Hvis problemet er, at vi maler
os op i et hjørne ved at afsætte

660
00:28:13,410 --> 00:28:17,580
i forvejen for lidt hukommelse, vi
så have en eller anden måde at beskæftige sig med, ja,

661
00:28:17,580 --> 00:28:19,880
hvorfor ikke bare undgå,
udstede i alt?

662
00:28:19,880 --> 00:28:26,170
Hvorfor ikke bare erklære bakker at være en
pointer til en node, ergo en sammenkædet liste

663
00:28:26,170 --> 00:28:30,740
og så bare tildele nye noder
hver gang Steven nødvendig for at passe en

664
00:28:30,740 --> 00:28:32,400
nummer i datastrukturen.

665
00:28:32,400 --> 00:28:34,200
>> Så ville billedet have at ændre.

666
00:28:34,200 --> 00:28:38,220
Det kommer ikke til at være så ren og som
simpelt som bare en vifte af tre ints.

667
00:28:38,220 --> 00:28:42,970
Nu er det kommer til at være en pegepind til en
struct, og at struct vil

668
00:28:42,970 --> 00:28:44,830
har en int og en næste pointer.

669
00:28:44,830 --> 00:28:47,670
Det kommer til at lede via denne pointer
til en anden sådan struct til

670
00:28:47,670 --> 00:28:48,600
en anden sådan struct.

671
00:28:48,600 --> 00:28:50,560
Så ville billedet faktisk
få en smule Messier.

672
00:28:50,560 --> 00:28:52,950
Og vi ville have pile binde
det hele sammen.

673
00:28:52,950 --> 00:28:55,280
>> Men det er fint, til højre, fordi
Vi har set, hvordan du gør dette.

674
00:28:55,280 --> 00:28:58,180
Og når du får komfortabel
gennemføre noget som en sammenkædet

675
00:28:58,180 --> 00:29:01,450
liste, som du bliver nødt til at gøre, hvis du
vælger at gennemføre en hash tabel med

676
00:29:01,450 --> 00:29:05,120
separate chaining for p-sæt 6, kan du
bruge det som en byggesten, eller

677
00:29:05,120 --> 00:29:08,870
ingrediens, eller i Scratch tale, en
procedure, noget, som du sætter, dig

678
00:29:08,870 --> 00:29:12,560
oprettet din egen brik
som du derefter kan genbruge.

679
00:29:12,560 --> 00:29:17,090
Så tradeoffs, men potentielle løsninger
at vi faktisk har set før.

680
00:29:17,090 --> 00:29:20,560
>> Så ganske ofte, kan du se det hver
år eller to, når Apple frigiver

681
00:29:20,560 --> 00:29:23,060
noget nyt, og alle de skøre mennesker
line up uden for Apple

682
00:29:23,060 --> 00:29:27,050
lagre til at købe deres marginale
opgradere på hardware.

683
00:29:27,050 --> 00:29:30,420
Jeg siger dette, er det OK, fordi
Jeg er en af ​​disse mennesker.

684
00:29:30,420 --> 00:29:35,140
Så hvad slags datastruktur
kan repræsentere denne virkelighed?

685
00:29:35,140 --> 00:29:36,980
>> Nå, lad os kalde det en kø, en linje.

686
00:29:36,980 --> 00:29:40,270
Så briterne ville kalde det typisk en
kø alligevel, så det er en nice navn.

687
00:29:40,270 --> 00:29:44,960
Og de to operationer, at en kø
støtter vi vil kalde en enqueue

688
00:29:44,960 --> 00:29:48,900
drift og en dequeue drift,
som er ens i

689
00:29:48,900 --> 00:29:50,120
ånd at skubbe og pop.

690
00:29:50,120 --> 00:29:54,060
Det er bare slags anderledes i
konvention, hvad vi kalder dem.

691
00:29:54,060 --> 00:29:57,680
Men at enqueue noget betyder at tilføje
eller sæt den til datastruktur.

692
00:29:57,680 --> 00:29:59,570
At dequeue betyder at fjerne det.

693
00:29:59,570 --> 00:30:05,170
Men hvor en stak var en LIFO data
struktur, en kø er en først ind,

694
00:30:05,170 --> 00:30:06,740
først ud datastruktur.

695
00:30:06,740 --> 00:30:10,050
>> Hvis du er den første person i rækken,
du vil være den første person til at få

696
00:30:10,050 --> 00:30:12,420
ude af trit og købe din nye enhed.

697
00:30:12,420 --> 00:30:18,070
Forestil dig, hvor ked af disse mennesker ville være
hvis Apple i stedet brugt en stak, for

698
00:30:18,070 --> 00:30:21,250
Eksempelvis at gennemføre plukning
up af dit nye legetøj.

699
00:30:21,250 --> 00:30:24,310
Så køer mening, i hvert fald, og
Vi kan tænke på alle mulige

700
00:30:24,310 --> 00:30:27,480
applikationer, formentlig for køer,
især når du ønsker retfærdighed.

701
00:30:27,480 --> 00:30:30,040
Så hvordan kan vi implementere disse
som en datastruktur?

702
00:30:30,040 --> 00:30:33,680
>> Nå, jeg foreslår, at vi måske
nødt til at gøre det på denne måde.

703
00:30:33,680 --> 00:30:35,225
Så jeg har tænkt mig at nu har numre.

704
00:30:35,225 --> 00:30:38,190
Så vi vil holde det simpelt og ikke
nødvendigvis tale i form af bakker.

705
00:30:38,190 --> 00:30:40,220
Bare tal, at folk i fået.

706
00:30:40,220 --> 00:30:43,760
Kapacitet vil, igen, fastsætte
samlede antal personer, der kan være i

707
00:30:43,760 --> 00:30:46,900
denne linje, da tre eller
enhver anden værdi.

708
00:30:46,900 --> 00:30:50,760
>> Men jeg foreslår, at jeg har brug for at holde styr
ikke blot af størrelsen af

709
00:30:50,760 --> 00:30:52,370
kø, hvor mange ting er i det.

710
00:30:52,370 --> 00:30:56,310
Så størrelse er den aktuelle størrelse, kapacitet
er den maksimale størrelse.

711
00:30:56,310 --> 00:30:58,540
Lige igen, nomenklatur
efter sædvane.

712
00:30:58,540 --> 00:31:03,680
Hvorfor har jeg brug for en ekstra int inde
af en kø for at holde styr på, hvem der er i

713
00:31:03,680 --> 00:31:05,365
forsiden af ​​den linje?

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

715
00:31:07,930 --> 00:31:10,910
Hvorfor skal jeg nødt til at gøre det i dette tilfælde?

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

717
00:31:14,750 --> 00:31:16,190
>> Nå, hvordan er dette billede
kommer til at ændre sig?

718
00:31:16,190 --> 00:31:19,280
Jeg kan sandsynligvis genbruge mest
af dette billede.

719
00:31:19,280 --> 00:31:21,480
Lad mig gå videre og slette, hvad der er her.

720
00:31:21,480 --> 00:31:24,580
Vi vil give det en anelse
andet navn heroppe.

721
00:31:24,580 --> 00:31:28,930
Lad os slippe af de 17, lad os slippe
af 9, lad os slippe af med den 3..

722
00:31:28,930 --> 00:31:30,410
Og lad os tilføje en anden ting.

723
00:31:30,410 --> 00:31:34,710
Jeg foreslår, at jeg har brug for at holde styr på
den forreste del af listen, hvilket er lige

724
00:31:34,710 --> 00:31:35,570
vil være en int så godt.

725
00:31:35,570 --> 00:31:36,550
Og vi kommer til at holde det simpelt.

726
00:31:36,550 --> 00:31:37,740
Ingen linkede liste for nu.

727
00:31:37,740 --> 00:31:40,900
>> Vi vil indrømme, at vi kommer til at
bump op mod denne grænse.

728
00:31:40,900 --> 00:31:43,720
Men hvad jeg ønsker at se
ske denne gang?

729
00:31:43,720 --> 00:31:47,240
Så formoder jeg gå videre og den første
person kommer op på linje, og

730
00:31:47,240 --> 00:31:48,560
det er nummer 9.

731
00:31:48,560 --> 00:31:49,680
Vi har stress bolde.

732
00:31:49,680 --> 00:31:51,330
Kan jeg stjæle, siger, to eller tre personer?

733
00:31:51,330 --> 00:31:52,690
En, to, tre?

734
00:31:52,690 --> 00:31:53,120
Kom op.

735
00:31:53,120 --> 00:31:56,022
Lige forfra, fordi
vil vi gøre dette til en hurtig.

736
00:31:56,022 --> 00:31:59,415
>> Hver af jer er nu kommer til at være
en fan dreng i kø ved Apple.

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

738
00:32:03,970 --> 00:32:06,210
Du vil ikke modtage Apple-hardware
i slutningen af ​​dette selv.

739
00:32:06,210 --> 00:32:06,500
Ok.

740
00:32:06,500 --> 00:32:09,430
Så du er nummer 9, er du
nummer 17, nummer 22..

741
00:32:09,430 --> 00:32:12,130
Disse er vilkårlige numre, ligesom
studerende id'er eller whatnot.

742
00:32:12,130 --> 00:32:14,550
Og på bare et øjeblik, så lad os begynde
at begynde at tilføje ting.

743
00:32:14,550 --> 00:32:16,000
Og jeg vil køre i bestyrelsen her i denne tid.

744
00:32:16,000 --> 00:32:19,570
>> Så i dette tilfælde, har jeg initialiseret
fronten for at være -

745
00:32:19,570 --> 00:32:22,380
Jeg faktisk ikke rigtig pleje hvad
front er, fordi størrelsen er nul.

746
00:32:22,380 --> 00:32:24,480
Så dette kan lige så godt bare
være et spørgsmålstegn.

747
00:32:24,480 --> 00:32:26,170
Disse er alle spørgsmålstegn.

748
00:32:26,170 --> 00:32:29,880
Så nu vil vi begynde at rent faktisk se nogle
mennesker foring op i butikken.

749
00:32:29,880 --> 00:32:33,320
>> Så hvis nummer 9, er du den første
der på 5:00, gå videre og stille op,

750
00:32:33,320 --> 00:32:34,210
eller natten før.

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

752
00:32:34,580 --> 00:32:35,940
Så nu 9 er her.

753
00:32:35,940 --> 00:32:37,940
Så 9 er i den forreste del af listen.

754
00:32:37,940 --> 00:32:41,440
Så jeg har tænkt mig at gå videre og opdatere
størrelsen af ​​denne aktuelle data

755
00:32:41,440 --> 00:32:44,740
struktur ikke være 0 længere,
men at være 1.

756
00:32:44,740 --> 00:32:47,630
Jeg har tænkt mig at sætte 9 ved
foran listen.

757
00:32:47,630 --> 00:32:51,020
Lad mig gå videre og skifte skærmen
så vi kan se forbi os her.

758
00:32:51,020 --> 00:32:53,220
>> Og nu, hvad vil jeg have
til at sætte foran?

759
00:32:53,220 --> 00:32:56,240
Jeg har tænkt mig at holde styr at
forrest i køen lige nu

760
00:32:56,240 --> 00:32:58,570
er ved placeringen 0.

761
00:32:58,570 --> 00:33:00,510
Fordi det næste kommer til at ske?

762
00:33:00,510 --> 00:33:03,000
Nå, formoder jeg nu enqueue
17 så godt.

763
00:33:03,000 --> 00:33:04,510
Så hop på linje der.

764
00:33:04,510 --> 00:33:07,060
Og igen, den slags dør til
butik kommer til at være her.

765
00:33:07,060 --> 00:33:08,700
Så nu har jeg tilføjet 17.

766
00:33:08,700 --> 00:33:10,810
Og selv om disse fyre blokerer
skærmen, det er OK,

767
00:33:10,810 --> 00:33:12,300
fordi vi kan se det heroppe.

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

769
00:33:12,910 --> 00:33:13,810
>> PUBLIKUM: Vi kan flytte -

770
00:33:13,810 --> 00:33:14,660
>> DAVID MALAN: Nej, det er OK.

771
00:33:14,660 --> 00:33:16,000
Det er enorme deroppe.

772
00:33:16,000 --> 00:33:18,580
Så 17 er nu inde i køen.

773
00:33:18,580 --> 00:33:21,332
Jeg har brug for at opdatere hvilke
felter nu selv?

774
00:33:21,332 --> 00:33:23,210
OK, absolut størrelse.

775
00:33:23,210 --> 00:33:26,430
Og hvad med fronten?

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

777
00:33:27,040 --> 00:33:30,200
Foran bør ikke ændre, fordi
i modsætning til en stak, vi

778
00:33:30,200 --> 00:33:31,370
ønsker at opretholde retfærdighed.

779
00:33:31,370 --> 00:33:35,150
Så hvis 9 kom i første omgang ønsker vi 9
at være den første ud af linjen

780
00:33:35,150 --> 00:33:36,420
og ind i butikken.

781
00:33:36,420 --> 00:33:37,220
>> Faktisk, lad os se.

782
00:33:37,220 --> 00:33:42,235
Før vi indsætter 22, lad os
gå videre og dequeue 9..

783
00:33:42,235 --> 00:33:42,970
Hvad er dit navn igen?

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

785
00:33:43,680 --> 00:33:45,440
>> DAVID MALAN: Jake går
skal dequeued nu.

786
00:33:45,440 --> 00:33:48,050
Så får du at gå ind i butikken.

787
00:33:48,050 --> 00:33:49,880
Og foregive, at butikken
er derovre.

788
00:33:49,880 --> 00:33:51,970
Så nu, hvad har brug for - dit-dit-dit!

789
00:33:51,970 --> 00:33:53,400
Hvad skal der ske nu?

790
00:33:53,400 --> 00:33:54,490
Design beslutning.

791
00:33:54,490 --> 00:33:56,825
Så ikke en dårlig instinkt, men -
hvad er dit navn igen?

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

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

794
00:33:57,500 --> 00:33:58,810
Så hvad gjorde David gøre?

795
00:33:58,810 --> 00:34:02,590
Han prøvede at sortere i fastsætte data
struktur og flytte fra sin placering

796
00:34:02,590 --> 00:34:04,100
i Jakes tidligere placering.

797
00:34:04,100 --> 00:34:06,740
Og det er fint, hvis vi er villige
at acceptere, at som en

798
00:34:06,740 --> 00:34:08,199
gennemførelse detalje.

799
00:34:08,199 --> 00:34:11,100
Men først, lad os opdatere data
struktur, før vi gør det.

800
00:34:11,100 --> 00:34:14,139
Fordi jeg ikke kunne lide tanken om alle
de mennesker, flytte i denne linje.

801
00:34:14,139 --> 00:34:17,360
>> Det er ikke nogen big deal, hvis David gør det med
et skridt, men igen, tænke tilbage på

802
00:34:17,360 --> 00:34:20,360
når vi har haft otte frivillige på
fase, og vi har gjort ligesom indsættelse

803
00:34:20,360 --> 00:34:22,600
sortere, hvor vi havde til at starte
flytte alle omkring.

804
00:34:22,600 --> 00:34:23,790
Det fik dyrt, right?

805
00:34:23,790 --> 00:34:28,330
Det gør mig krybe om store O
n, kvadreret store O n igen.

806
00:34:28,330 --> 00:34:30,650
Det er ikke at føle sig som
en ideel resultat.

807
00:34:30,650 --> 00:34:32,080
>> Så lad os bare opdatere denne.

808
00:34:32,080 --> 00:34:35,120
Så størrelsen af ​​køen
er ikke længere 2..

809
00:34:35,120 --> 00:34:37,090
Det er nu blot 1.

810
00:34:37,090 --> 00:34:40,360
Men jeg kan nu opdatere noget
Jeg har ikke opdateret før,

811
00:34:40,360 --> 00:34:41,130
foran listen.

812
00:34:41,130 --> 00:34:45,420
Jeg kunne bare sige, er, at location 1?

813
00:34:45,420 --> 00:34:49,770
Så nu har vi skrald værdi her,
skrald værdi her, og David i

814
00:34:49,770 --> 00:34:51,469
midten af ​​dette affald.

815
00:34:51,469 --> 00:34:54,980
Men datastrukturen
er stadig intakt.

816
00:34:54,980 --> 00:34:58,540
>> Og i virkeligheden, behøver jeg ikke engang behøver at
ændre Jakes tidligere nummer

817
00:34:58,540 --> 00:35:00,460
9, fordi der bekymrer.

818
00:35:00,460 --> 00:35:04,470
Jeg har nok information nu er i
størrelse, som jeg ved, der er én person i

819
00:35:04,470 --> 00:35:05,030
denne kø.

820
00:35:05,030 --> 00:35:08,340
Og jeg ved, at denne person
er location 1, ikke 0.

821
00:35:08,340 --> 00:35:09,760
Jeg er ikke tælle.

822
00:35:09,760 --> 00:35:11,300
Så 1 samt.

823
00:35:11,300 --> 00:35:13,410
Så datastrukturen er stadig OK.

824
00:35:13,410 --> 00:35:14,330
>> Nå, hvad sker der nu?

825
00:35:14,330 --> 00:35:15,010
Lad os enqueue -

826
00:35:15,010 --> 00:35:15,370
hvad er dit navn?

827
00:35:15,370 --> 00:35:16,160
>> PUBLIKUM: Callen.

828
00:35:16,160 --> 00:35:16,580
>> DAVID MALAN: Callen.

829
00:35:16,580 --> 00:35:20,770
Lad os enqueue en Callen, og
22 er nu i køen.

830
00:35:20,770 --> 00:35:22,300
Så nu, hvad skal ændres her?

831
00:35:22,300 --> 00:35:24,380
Front ikke kommer til at
ændre, naturligvis.

832
00:35:24,380 --> 00:35:27,160
Størrelse kommer til at ændre til at være 2 igen.

833
00:35:27,160 --> 00:35:31,590
Og 22 ender her, 9 er stadig til stede,
men det er effektivt en

834
00:35:31,590 --> 00:35:32,600
skrald værdi nu.

835
00:35:32,600 --> 00:35:35,910
Det er bare en rest af Jake fortid.

836
00:35:35,910 --> 00:35:39,200
>> Så nu, hvad sker der, hvis
Jeg dequeue David?

837
00:35:39,200 --> 00:35:41,560
En sidste operation, dequeue David.

838
00:35:41,560 --> 00:35:46,070
Vi kunne flytte, men jeg foreslår lad os
gøre så lidt arbejde som muligt.

839
00:35:46,070 --> 00:35:50,280
Nu er min datastruktur går
tilbage i størrelse 2-1.

840
00:35:50,280 --> 00:35:53,730
Men forrest i køen
bliver nu 2..

841
00:35:53,730 --> 00:35:56,640
Jeg har ikke brug for at ændre disse numre
bare endnu, fordi de er

842
00:35:56,640 --> 00:35:58,230
bare skrald værdier.

843
00:35:58,230 --> 00:35:59,720
>> Men nu hvad sker der?

844
00:35:59,720 --> 00:36:03,280
Antag jeg enqueue mig selv, 26?

845
00:36:03,280 --> 00:36:05,890
Jeg føler, at jeg hører herovre.

846
00:36:05,890 --> 00:36:06,890
Så jeg bliver enqueued.

847
00:36:06,890 --> 00:36:08,760
Så jeg slags hører til her.

848
00:36:08,760 --> 00:36:11,300
Og selvom du ikke helt
værdsætte denne visuelt på scenen,

849
00:36:11,300 --> 00:36:15,075
fordi vi har masser af plads, jeg skulle
ikke stå her, hvorfor?

850
00:36:15,075 --> 00:36:16,290
>> PUBLIKUM: Du er out of bounds.

851
00:36:16,290 --> 00:36:16,370
>> DAVID MALAN: Right.

852
00:36:16,370 --> 00:36:16,940
Jeg er ude af bounds.

853
00:36:16,940 --> 00:36:19,330
Jeg har indekseret over det
grænserne for dette array.

854
00:36:19,330 --> 00:36:23,420
Jeg burde være i en af ​​de
tre mulige placeringer.

855
00:36:23,420 --> 00:36:25,150
Nu hvor der er mest naturligt at gå?

856
00:36:25,150 --> 00:36:27,760
Jeg foreslår, vi gearede
en uge en trick.

857
00:36:27,760 --> 00:36:30,150
The Mod operatør procentdel.

858
00:36:30,150 --> 00:36:36,850
Fordi jeg teknisk set er stående på
location 3, men jeg gør 3 mod kapacitet,

859
00:36:36,850 --> 00:36:40,250
så 3 et procenttegn, 3 -

860
00:36:40,250 --> 00:36:40,970
kapacitet er 3..

861
00:36:40,970 --> 00:36:41,720
Hvad er det?

862
00:36:41,720 --> 00:36:43,700
Hvad er resten, når
du opdele 3 af 3?

863
00:36:43,700 --> 00:36:44,070
0.

864
00:36:44,070 --> 00:36:48,140
>> Så det sætter mig var Jake var,
der er faktisk godt.

865
00:36:48,140 --> 00:36:50,370
Så nu gennemførelsen
af denne ting kommer til at

866
00:36:50,370 --> 00:36:51,250
være lidt af en hovedpine.

867
00:36:51,250 --> 00:36:53,740
Det er egentlig bare en linje
hovedpine, kode.

868
00:36:53,740 --> 00:36:56,580
Men i det mindste nu er der skrald
værdi her, men der er to

869
00:36:56,580 --> 00:36:57,910
legitime ints her.

870
00:36:57,910 --> 00:37:04,160
Og jeg hævder, at nu har vi gjort
præcis, hvad vi skal gøre, så længe

871
00:37:04,160 --> 00:37:08,600
vi ændre, hvad Jakes
værdi var at være 26.

872
00:37:08,600 --> 00:37:12,110
>> Vi har nu oplysninger nok stadig
at opretholde integriteten

873
00:37:12,110 --> 00:37:13,060
af denne datastruktur.

874
00:37:13,060 --> 00:37:17,160
Vi er stadig slags ude af lykke, når vi
ønsker at indsætte fire eller flere samlede

875
00:37:17,160 --> 00:37:20,740
elementer, men jeg kan i det mindste gøre pretty
effektiv udnyttelse af denne konstante

876
00:37:20,740 --> 00:37:21,740
tid, i virkeligheden.

877
00:37:21,740 --> 00:37:27,150
Jeg behøver ikke at bekymre dig om at flytte
alle, da Davids hældning var.

878
00:37:27,150 --> 00:37:30,816
>> Eventuelle spørgsmål vedrørende stakke,
eller denne kø?

879
00:37:30,816 --> 00:37:32,184
>> TILHØRERNE: Er grunden
du har brug for størrelse, så du kender

880
00:37:32,184 --> 00:37:34,010
hvor at have en person?

881
00:37:34,010 --> 00:37:34,770
>> DAVID MALAN: Præcis.

882
00:37:34,770 --> 00:37:38,230
Jeg har brug for at kende størrelsen af ​​array
fordi jeg har brug for at vide præcis, hvordan

883
00:37:38,230 --> 00:37:41,940
mange af disse værdier er legitime,
og så jeg kan finde, hvor at sætte

884
00:37:41,940 --> 00:37:42,800
den næste person.

885
00:37:42,800 --> 00:37:43,300
Præcis.

886
00:37:43,300 --> 00:37:44,580
Størrelsen er -

887
00:37:44,580 --> 00:37:46,360
faktisk, vi ikke opdatere denne endnu.

888
00:37:46,360 --> 00:37:48,380
Jeg tilføjede mig på 26..

889
00:37:48,380 --> 00:37:51,760
Størrelsen er nu, ikke 1, men 2.

890
00:37:51,760 --> 00:37:57,780
Så nu er dette faktisk hjælper mig med at finde
leder af listen, der ikke er 0, ikke

891
00:37:57,780 --> 00:37:59,250
1, men er 2.

892
00:37:59,250 --> 00:38:01,665
Den forreste del af listen
er faktisk nummer 22.

893
00:38:01,665 --> 00:38:05,120
Fordi han kom i først, så bør han
være tilladt ind i butikken før mig,

894
00:38:05,120 --> 00:38:08,780
selvom visuelt jeg står
tættere til butikken.

895
00:38:08,780 --> 00:38:09,220
>> Okay?

896
00:38:09,220 --> 00:38:12,410
En runde af bifald for disse fyre
og vi vil lade dem ud derfra.

897
00:38:12,410 --> 00:38:17,090
>> [Applaus]

898
00:38:17,090 --> 00:38:18,150
>> DAVID MALAN: jeg kunne lade
du holder bakken.

899
00:38:18,150 --> 00:38:20,760
Vi kunne se, hvad der sker, hvis
du vil, men måske ikke.

900
00:38:20,760 --> 00:38:21,590
Ok.

901
00:38:21,590 --> 00:38:25,380
Så hvad nu, står vi?

902
00:38:25,380 --> 00:38:28,900
Nå, lad mig foreslå, at der er en
få andre datastrukturer, vi kunne

903
00:38:28,900 --> 00:38:33,810
begynde at tilføje til vores værktøjskasse, der vil
faktisk være helt, helt relevant som

904
00:38:33,810 --> 00:38:35,270
vi dykke ned i web stuff.

905
00:38:35,270 --> 00:38:38,150
Hvilket igen har en vis form for forbindelse
til træer i form af

906
00:38:38,150 --> 00:38:40,550
noget, der hedder DOM, dokument
objekt model.

907
00:38:40,550 --> 00:38:42,370
Men vi vil se mere af
at inden længe.

908
00:38:42,370 --> 00:38:46,260
>> Lad mig foreslå definitionally at vi
kalde træet nu, hvad du måske kender som

909
00:38:46,260 --> 00:38:48,820
mere af en familie træ, hvor man
har nogle forfader ved

910
00:38:48,820 --> 00:38:49,790
rødder af træet.

911
00:38:49,790 --> 00:38:54,480
En patriarkalsk eller matriark på
toppen af ​​træet.

912
00:38:54,480 --> 00:38:56,700
Uden deres ægtefælle. I dette tilfælde

913
00:38:56,700 --> 00:39:00,940
Men nu har vi, hvad vi vil kalde
børn, som er knuder, der hænger

914
00:39:00,940 --> 00:39:05,480
off venstre barn eller højre barn,
pile, som afbildet her.

915
00:39:05,480 --> 00:39:10,490
>> Med andre ord, i et træ datastruktur
i computer har et træ nul

916
00:39:10,490 --> 00:39:11,480
eller flere knuder.

917
00:39:11,480 --> 00:39:13,500
Hvis det har mindst en knude,
der hedder root.

918
00:39:13,500 --> 00:39:15,700
Det er de ting, visuelt at
vi trækker på toppen.

919
00:39:15,700 --> 00:39:20,280
Og denne node, som enhver anden knude, kan
have nul, én eller to, eller tre,

920
00:39:20,280 --> 00:39:23,600
eller hvor mange børn de
datastruktur understøtter.

921
00:39:23,600 --> 00:39:29,150
I dette tilfælde, roden opbevaring af
værdi en, har to børn, 2 og 3,

922
00:39:29,150 --> 00:39:33,020
så vi generelt kalder 2 venstre
barn og 3 højre barn.

923
00:39:33,020 --> 00:39:36,940
>> Og så når vi kommer ned til 5, 6 og
7, 6 kunne kaldes den midterste barn.

924
00:39:36,940 --> 00:39:38,940
Hvis du har fire børn,
det bliver forvirrende.

925
00:39:38,940 --> 00:39:42,260
Så vi stoppe med at bruge den slags
genvej verbalt.

926
00:39:42,260 --> 00:39:44,580
Men det er egentlig bare et stamtræ.

927
00:39:44,580 --> 00:39:48,880
Og bladene her er de noder,
selv har ingen børn.

928
00:39:48,880 --> 00:39:52,540
De hænger ned fra bunden af ​​træet.

929
00:39:52,540 --> 00:39:56,940
>> Så hvordan kan vi implementere et træ,
har kun to børn maximalt?

930
00:39:56,940 --> 00:39:58,410
Vi kalder det et binært træ.

931
00:39:58,410 --> 00:40:00,960
Bi igen betyder to, i dette
tilfælde gerne med binær.

932
00:40:00,960 --> 00:40:04,830
Og så kan det have nul, et,
eller to børn maksimalt.

933
00:40:04,830 --> 00:40:08,650
>> Jeg vil foreslå, at vi gennemfører node
for denne struktur med en int n,

934
00:40:08,650 --> 00:40:11,910
og derefter to pointere, den ene kaldte
venstre, der hedder rigtigt.

935
00:40:11,910 --> 00:40:14,830
Men de er bare nice
vilkårlige konventioner.

936
00:40:14,830 --> 00:40:18,170
Og hvad er rart nu, især hvis du
slags kæmpet konceptuelt med

937
00:40:18,170 --> 00:40:21,300
rekursion eller troede, at det ikke var
virkelig en løsning på noget som helst,

938
00:40:21,300 --> 00:40:23,120
især hvis du kunne
løber tør for hukommelse.

939
00:40:23,120 --> 00:40:26,600
Nu, hvor vi taler om data
strukturer og algoritmer, der tillader

940
00:40:26,600 --> 00:40:31,030
os at krydse og manipulere dem,
viser sig, at rekursion kommer tilbage i

941
00:40:31,030 --> 00:40:34,240
en langt mere overbevisende
hvis ikke smuk måde.

942
00:40:34,240 --> 00:40:38,670
>> Så dette jeg foreslår, er gennemførelsen
en søgefunktion.

943
00:40:38,670 --> 00:40:39,870
Da to indgange -

944
00:40:39,870 --> 00:40:41,570
så tænk på det som en sort boks.

945
00:40:41,570 --> 00:40:46,560
Da to indgange, n, en int og en
pointer til et træ, en pointer til en

946
00:40:46,560 --> 00:40:50,020
node, eller virkelig roden af ​​et træ, jeg
påstand om, at denne funktion kan returnere

947
00:40:50,020 --> 00:40:53,530
sandt eller falsk, at værdien n
er inde i dette træ.

948
00:40:53,530 --> 00:40:55,210
>> Hvad er inde i denne sorte boks?

949
00:40:55,210 --> 00:40:57,440
Nå, fire filialer.

950
00:40:57,440 --> 00:40:58,385
Den første lige tjekker.

951
00:40:58,385 --> 00:41:00,490
Hvis træet er null, bare returnere falsk.

952
00:41:00,490 --> 00:41:04,580
Hvis der ikke er nogen node, er der ingen n,
der er ingen tal, bare returnere falsk.

953
00:41:04,580 --> 00:41:12,330
Hvis selv, n, den værdi, du leder efter
til mindre end træ pil n er, og

954
00:41:12,330 --> 00:41:15,180
bare for at være klar, hvad betyder det, når
Jeg skriver træet og derefter pilen

955
00:41:15,180 --> 00:41:18,150
notation, n?

956
00:41:18,150 --> 00:41:18,690
Præcis.

957
00:41:18,690 --> 00:41:21,970
Det betyder dereference at
pointer kaldet træ.

958
00:41:21,970 --> 00:41:26,750
Derned, og derefter komme ind i denne
node og få sit felt kaldet n.

959
00:41:26,750 --> 00:41:30,810
Og derefter sammenligne den faktiske n, der var
gået ind Søg imod det.

960
00:41:30,810 --> 00:41:35,390
>> Så hvis n er mindre end værdien n
i træet node selv, godt

961
00:41:35,390 --> 00:41:36,720
hvad betyder det?

962
00:41:36,720 --> 00:41:40,690
Det betyder ikke noget ved første øjekast.

963
00:41:40,690 --> 00:41:40,900
Right?

964
00:41:40,900 --> 00:41:45,560
Ligesom når du har en bred vifte af
værdier, kan du lide at anvende binære

965
00:41:45,560 --> 00:41:48,290
søge som en form for kløft
og erobre.

966
00:41:48,290 --> 00:41:51,790
Men hvad antagelse vi nødt til at gøre
for binær søgning for at arbejde på alle

967
00:41:51,790 --> 00:41:54,510
i telefonbogen og
tidligere eksempler?

968
00:41:54,510 --> 00:41:55,530
>> Hvordan skal sorteres.

969
00:41:55,530 --> 00:41:59,490
Så lad os forfine definitionen af ​​træet
her ikke at være bare et træ, der kan

970
00:41:59,490 --> 00:42:00,880
have et vilkårligt antal børn.

971
00:42:00,880 --> 00:42:04,700
Ikke bare et binært træ, som kan
har 0, 1 eller 2 maksimalt.

972
00:42:04,700 --> 00:42:09,700
Men som en binær søgning træ eller BST,
der er bare en fancy måde at sige en

973
00:42:09,700 --> 00:42:15,430
binært træ, således at hver node
venstre barn, hvis det nuværende er

974
00:42:15,430 --> 00:42:16,830
mindre end knudepunktet.

975
00:42:16,830 --> 00:42:20,170
Og hver node ret barn,
hvis tilstede, er større

976
00:42:20,170 --> 00:42:21,740
end knudepunktet selv.

977
00:42:21,740 --> 00:42:25,200
>> Så med andre ord, hvis du skulle tegne
træet ud, alle numrene er

978
00:42:25,200 --> 00:42:30,620
omhyggeligt afbalanceret som dette, så hvis
du har 55 som roden, kan 33 gå

979
00:42:30,620 --> 00:42:33,090
til venstre, fordi det er mindre end 55 år.

980
00:42:33,090 --> 00:42:36,430
77 kan gå til sin ret, fordi
den er større end 55 år.

981
00:42:36,430 --> 00:42:40,750
Men nu mærke, samme definition,
Det er en rekursiv definition verbalt,

982
00:42:40,750 --> 00:42:42,600
skal ansøge om 33.

983
00:42:42,600 --> 00:42:47,610
33 venstre barn skal være mindre end det,
og 33 ret barn, 44, skal være

984
00:42:47,610 --> 00:42:48,580
større end det.

985
00:42:48,580 --> 00:42:51,670
>> Så dette er en binær søgning træ, og
Jeg foreslår, at bruge en lille smule af

986
00:42:51,670 --> 00:42:53,910
rekursion, kan vi nu finde n..

987
00:42:53,910 --> 00:42:59,160
Så hvis n er mindre end den værdi, n, der er
nuværende node, jeg kommer til at gå

988
00:42:59,160 --> 00:43:04,090
fremad og punt, så at sige, og bare
tilbage uanset svar er

989
00:43:04,090 --> 00:43:08,470
søger efter n på
tree venstre barn.

990
00:43:08,470 --> 00:43:11,370
Bemærk igen, denne funktion bare
forventer en node stjerne, en

991
00:43:11,370 --> 00:43:12,780
pointer til et knudepunkt.

992
00:43:12,780 --> 00:43:17,360
Så vel kan jeg bare gøre træet
pil venstre, som vil føre

993
00:43:17,360 --> 00:43:18,400
mig til en anden node.

994
00:43:18,400 --> 00:43:19,480
Men hvad er det node?

995
00:43:19,480 --> 00:43:22,820
>> Tja, ifølge denne erklæring
venstre er blot en pegepind, så bare

996
00:43:22,820 --> 00:43:27,090
betyder jeg passerer til søgefunktionen
en anden pointer, nemlig

997
00:43:27,090 --> 00:43:30,750
den, som repræsenterer
min venstre barns træ.

998
00:43:30,750 --> 00:43:36,040
Så i dette tilfælde, at markøren 33, hvis
dette er vores prøve input mellemtiden, hvis

999
00:43:36,040 --> 00:43:40,740
n er større end værdien N ved
nuværende node i træet, så er jeg

1000
00:43:40,740 --> 00:43:43,370
kommer til at gå videre og punt i det andet
retning og bare sige, jeg ikke

1001
00:43:43,370 --> 00:43:47,280
vide, om denne værdi n er i træet,
men jeg ved, om det er, det er ned af min

1002
00:43:47,280 --> 00:43:49,090
højre gren, så at sige.

1003
00:43:49,090 --> 00:43:53,120
Så lad mig kalde rekursivt søge,
passerer en n igen, men passerer i en

1004
00:43:53,120 --> 00:43:54,580
pointer til min højre barn.

1005
00:43:54,580 --> 00:44:00,020
>> Med andre ord, ved hvis jeg er i øjeblikket 55
og jeg leder for 99, jeg ved, at 99

1006
00:44:00,020 --> 00:44:04,270
er større end 55, så ligesom jeg rev
i telefonbogen uger siden, og vi

1007
00:44:04,270 --> 00:44:07,140
gik ret, på samme måde er vi
kommer til at gå lige her.

1008
00:44:07,140 --> 00:44:11,960
Og jeg ved ikke, om det er ved min højre
barn, og det er ikke, 77 er der, men

1009
00:44:11,960 --> 00:44:13,210
Jeg ved, det er i den retning.

1010
00:44:13,210 --> 00:44:18,770
Så jeg kalder søgning på min højre barn,
77 og lad søgningen tal ud fra

1011
00:44:18,770 --> 00:44:24,950
der, hvis 99 i denne vilkårlige
eksempel er faktisk der.

1012
00:44:24,950 --> 00:44:26,900
>> Else, hvad er det sidste tilfældet?

1013
00:44:26,900 --> 00:44:28,620
Hvis træet er null er én sag.

1014
00:44:28,620 --> 00:44:31,890
Hvis n er mindre end den aktuelle node
værdien er en anden sag.

1015
00:44:31,890 --> 00:44:35,120
Hvis n er større end den aktuelle
node værdi er et tredje tilfælde.

1016
00:44:35,120 --> 00:44:38,250
Hvad er den fjerde og sidste sag?

1017
00:44:38,250 --> 00:44:39,480
Jeg tror, ​​vi er ude af sager, right?

1018
00:44:39,480 --> 00:44:44,690
Det må være n er i
aktuelle node at jeg er på.

1019
00:44:44,690 --> 00:44:49,640
>> Så hvis jeg søger efter 55 på dette punkt
i historien, gren, den

1020
00:44:49,640 --> 00:44:51,780
træ ville returnere sandt.

1021
00:44:51,780 --> 00:44:55,380
Så hvad er interessant her, er, at vi
faktisk, i modsætning uger tidligere, vi slags

1022
00:44:55,380 --> 00:44:56,740
af har to base tilfælde.

1023
00:44:56,740 --> 00:44:58,300
Og de behøver ikke at
være alle på toppen.

1024
00:44:58,300 --> 00:45:01,390
Den øverste er en base tilfældet, fordi hvis
træ er null, er der intet at gøre.

1025
00:45:01,390 --> 00:45:03,410
Bare returnere en hård kodet
værdi af falsk.

1026
00:45:03,410 --> 00:45:07,400
>> Den nederste gren er en slags
standard, hvor hvis vi har kontrolleret for

1027
00:45:07,400 --> 00:45:11,550
null, vi har tjekket om det skulle være
venstre, men det bør ikke være, vi har

1028
00:45:11,550 --> 00:45:14,640
kontrolleres, hvis det skulle være rigtigt, men det
bør ikke være det helt klart må være

1029
00:45:14,640 --> 00:45:15,870
lige der, hvor vi er.

1030
00:45:15,870 --> 00:45:16,780
Det er en base case.

1031
00:45:16,780 --> 00:45:19,920
Så der er to rekursive tilfælde
klemt der i midten.

1032
00:45:19,920 --> 00:45:21,630
Men jeg kunne have skrevet
dette i vilkårlig rækkefølge.

1033
00:45:21,630 --> 00:45:24,520
Jeg syntes bare det følte slags naturlig
først kontrollere, om en eventuel fejl,

1034
00:45:24,520 --> 00:45:28,340
så tjek venstre, så tjek lige, så
antage, at du er på node

1035
00:45:28,340 --> 00:45:30,630
du faktisk leder efter.

1036
00:45:30,630 --> 00:45:36,240
>> Så hvorfor kan det være nyttigt?

1037
00:45:36,240 --> 00:45:37,910
Så det viser sig -

1038
00:45:37,910 --> 00:45:42,110
og lad mig springe til en teaser
her, at der er i nettet.

1039
00:45:42,110 --> 00:45:44,920
Vi kommer til at begynde at bruge ikke
programmeringssprog i starten, men en

1040
00:45:44,920 --> 00:45:46,030
kodesprog.

1041
00:45:46,030 --> 00:45:48,740
Et markup sprog er en, der er
samme ånd til programmering

1042
00:45:48,740 --> 00:45:51,715
sprog, men det gør ikke give dig den
evne til at udtrykke dig logisk.

1043
00:45:51,715 --> 00:45:55,070
Det giver dig kun mulighed for at
udtrykke dig strukturelt.

1044
00:45:55,070 --> 00:45:57,960
>> Hvor vil du sætte noget
på siden,? websiden

1045
00:45:57,960 --> 00:45:59,200
Hvilken farve vil du gøre det?

1046
00:45:59,200 --> 00:46:00,950
Hvilken skriftstørrelse vil du gøre det?

1047
00:46:00,950 --> 00:46:02,970
Hvilke ord vil du faktisk
ønsker på websiden?

1048
00:46:02,970 --> 00:46:04,060
Så det er et kodesprog.

1049
00:46:04,060 --> 00:46:07,690
Men så vil vi meget hurtigt indfører
JavaScript, som er et fuldgyldigt

1050
00:46:07,690 --> 00:46:08,560
programmeringssprog.

1051
00:46:08,560 --> 00:46:12,530
Meget lig syntaktisk i udseende
til C, men det vil have nogle

1052
00:46:12,530 --> 00:46:15,200
nice, mere kraftfuld, mere
brugervenlige funktioner.

1053
00:46:15,200 --> 00:46:18,050
>> Og en af ​​de frustrationer på dette
punkt i semesteret er, at vi vil

1054
00:46:18,050 --> 00:46:22,065
snart gennemføre speller i langt færre
linjer kode ved hjælp af andre sprog

1055
00:46:22,065 --> 00:46:25,580
end C selv tillader det, men for fornuftens
Vi vil snart forstå.

1056
00:46:25,580 --> 00:46:27,750
Dette vil være den første webside.

1057
00:46:27,750 --> 00:46:30,120
Det vil være helt underwhelming,
det første vi gør.

1058
00:46:30,120 --> 00:46:31,400
Det vil blot sige, hej verden.

1059
00:46:31,400 --> 00:46:34,010
Men hvis du aldrig har set det
før, det er HTML,

1060
00:46:34,010 --> 00:46:35,670
HyperText Markup Language.

1061
00:46:35,670 --> 00:46:39,310
>> Hvis du går til en bestemt menupunkt i
de fleste enhver browser på enhver webside på

1062
00:46:39,310 --> 00:46:43,160
internettet, kan du se HTML
at nogle mennesker skrev til

1063
00:46:43,160 --> 00:46:44,400
skabe den webside.

1064
00:46:44,400 --> 00:46:47,850
Og det sandsynligvis ikke ser ud som
kortfattet eller så pæn som dette.

1065
00:46:47,850 --> 00:46:51,400
Men det vil følge det mønster af disse
åbne parenteser og skråstreger og

1066
00:46:51,400 --> 00:46:53,660
bogstaver og potentielt tal.

1067
00:46:53,660 --> 00:46:56,770
>> Jeg troede, jeg ville give dig en teaser
af, hvad du vil være i stand til at gøre

1068
00:46:56,770 --> 00:46:57,950
efter at have taget CS50.

1069
00:46:57,950 --> 00:47:02,620
Lad mig gå til cs.harvard.edu / Rob,
vores egen Rob Bowden hjemmeside.

1070
00:47:02,620 --> 00:47:06,080
Han gjorde dette for os.

1071
00:47:06,080 --> 00:47:07,490
Så du vil snart være i stand til at gøre det.

1072
00:47:07,490 --> 00:47:10,660
Og også, hvad du har hørt
morges -

1073
00:47:10,660 --> 00:47:12,480
hvad du hørte i morges -

1074
00:47:12,480 --> 00:47:13,780
>> [HAMSTER DANCE MUSIC]

1075
00:47:13,780 --> 00:47:15,702
>> - Du kunne gøre dette.

1076
00:47:15,702 --> 00:47:16,790
Der venter os på onsdag.

1077
00:47:16,790 --> 00:47:17,791
Vi vil se dig derefter.

1078
00:47:17,791 --> 00:47:22,950
>> [HAMSTER DANCE MUSIC]

1079
00:47:22,950 --> 00:47:24,300
DAVID MALAN: På det næste CS50 -

1080
00:47:24,300 --> 00:47:31,670