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

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

3
00:00:12,250 --> 00:00:13,860
Welkom terug bij CS50.

4
00:00:13,860 --> 00:00:16,190
Dit is het begin van week 8.

5
00:00:16,190 --> 00:00:21,320
En herinner dat probleem set 5 eindigde
met een beetje een uitdaging.

6
00:00:21,320 --> 00:00:25,210
Dus de veronderstelling dat u hersteld van al uw
onderwijs Fellows en CA's foto's

7
00:00:25,210 --> 00:00:30,480
in het card.raw bestand, komt u in aanmerking
om nu al die mensen vinden, en

8
00:00:30,480 --> 00:00:34,510
een gelukkige winnaar zal naar huis lopen met een
van deze dingen, de sprong beweging

9
00:00:34,510 --> 00:00:37,450
apparaat dat u kunt gebruiken voor de definitieve
projecten, bijvoorbeeld.

10
00:00:37,450 --> 00:00:39,860
>> Dit, elk jaar, leidt tot
een beetje creepiness.

11
00:00:39,860 --> 00:00:43,480
En dus wat ik dacht dat ik zou doen is het aandeel
met u enkele van de noten die moeten

12
00:00:43,480 --> 00:00:47,370
gegaan heen en weer over
de lijst met medewerkers van laat.

13
00:00:47,370 --> 00:00:51,110
Bijvoorbeeld, gisteravond, citaat
unquote, van een van de medewerkers

14
00:00:51,110 --> 00:00:55,000
leden, "ik een student klop had net
op mijn deur om een ​​foto met mij nemen.

15
00:00:55,000 --> 00:00:59,020
Stalkers, zeg ik je. "Begon
vrij beschrijvende en dan zijn we verhuisd

16
00:00:59,020 --> 00:01:02,830
op, een uur of wat later, "ik had een
student op me te wachten na sectie

17
00:01:02,830 --> 00:01:06,080
en hij had al onze namen en foto's
op een aantal vellen papier. 'Oke.

18
00:01:06,080 --> 00:01:09,230
Zo georganiseerd, maar niet
al die griezelige nog.

19
00:01:09,230 --> 00:01:12,520
>> Dan: "Ik was buiten de stad dit weekend,
en toen ik terug kwam, was er een in

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

21
00:01:12,630 --> 00:01:16,740
slaapkamer. "[LACH]

22
00:01:16,740 --> 00:01:20,410
DAVID Malan: Volgend citaat uit een staf
lid, "een student kwam naar mijn huis op

23
00:01:20,410 --> 00:01:25,330
Somerville op 4:00 vanochtend. "Next
personeel, "Ik moet mijn hotel in San

24
00:01:25,330 --> 00:01:30,016
Francisco en een student stond te wachten
me in de lobby met drie DSLR's. "

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

26
00:01:31,510 --> 00:01:34,980
"Ik ben niet eens op het personeel dit semester,
maar een student in mijn huis ingebroken deze

27
00:01:34,980 --> 00:01:40,480
ochtend en nam de hele zaak
met Google Glass. "En dan tot slot,

28
00:01:40,480 --> 00:01:43,650
"Ten minste 12 mensen gretig waren
wachten voor mij toen ik uit mijn

29
00:01:43,650 --> 00:01:44,800
limo, en toen ik

30
00:01:44,800 --> 00:01:46,970
wakker. 'Oke.

31
00:01:46,970 --> 00:01:57,690
Dus onder de foto's, zoals u wellicht
herinneren, zijn hier deze kerel, die je

32
00:01:57,690 --> 00:02:01,850
misschien kennen als Milo Banana, die leeft
met Lauren Carvalho, ons hoofd

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

34
00:02:02,905 --> 00:02:05,170
Milo, Milo, kom hier jongen.

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
Let wel, hij draagt ​​Google Glass, dus
we zullen jullie dit allemaal zien na.

38
00:02:12,230 --> 00:02:16,190
Dus dit is Milo als je wilt
neem een ​​foto met hem daarna.

39
00:02:16,190 --> 00:02:18,240
Als je wilt om uit te kijken
naar het publiek daar.

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

41
00:02:19,430 --> 00:02:20,200
Dat is goed beeldmateriaal.

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

43
00:02:22,556 --> 00:02:23,941
Oh, doe dat niet.

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

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

46
00:02:29,470 --> 00:02:34,550
Dus een woord dan op wat ons te wachten,
want als we beginnen om de overgang,

47
00:02:34,550 --> 00:02:38,410
deze week bijzonder vanaf een
command line omgeving om PHP en

48
00:02:38,410 --> 00:02:42,720
JavaScript en SQL en HTML en CSS in
een web-based omgeving, zullen we

49
00:02:42,720 --> 00:02:44,490
uitrusten u met alle
meer kennis voor

50
00:02:44,490 --> 00:02:46,010
mogelijke afstudeeropdrachten.

51
00:02:46,010 --> 00:02:49,240
Tegen dat eind, de cursus heeft een
traditie van het houden van seminars, die

52
00:02:49,240 --> 00:02:50,950
zijn op tangentiële onderwerpen
aan de cursus.

53
00:02:50,950 --> 00:02:54,330
Zeer nauw samen met de programmering en
app ontwikkeling enzovoort, maar

54
00:02:54,330 --> 00:02:57,010
niet noodzakelijkerwijs onderzocht door
eigen syllabus van de cursus.

55
00:02:57,010 --> 00:03:00,250
>> Dus als u misschien wel interesse zou hebben in een
of meer van dit jaar de seminars,

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

57
00:03:02,530 --> 00:03:06,170
Er zijn oudere seminars
bij cs50.net/seminars.

58
00:03:06,170 --> 00:03:10,620
En op het rooster tot nu toe voor dit jaar
zijn schitterende Web Apps met Ruby on

59
00:03:10,620 --> 00:03:13,580
Rails, die een alternatief
taal PHP.

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

61
00:03:14,900 --> 00:03:18,710
Inleiding IOS, dat de
platform dat wordt gebruikt voor de iPhone en

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

63
00:03:19,850 --> 00:03:22,890
JavaScript voor Web Apps, zullen we betrekking hebben
dat, maar in dit seminar, ga je

64
00:03:22,890 --> 00:03:24,070
in meer detail.

65
00:03:24,070 --> 00:03:27,390
>> Leap Motion, dus we eigenlijk hebben enkele
van onze vrienden van Leap Motion,

66
00:03:27,390 --> 00:03:29,160
het bedrijf zelf, samen met ons.

67
00:03:29,160 --> 00:03:31,800
Morgen, in feite beoogd
een hands-on seminar, indien

68
00:03:31,800 --> 00:03:33,320
voor u van belang.

69
00:03:33,320 --> 00:03:38,770
Meteor.js, een alternatieve techniek voor
met behulp van JavaScript niet in een browser,

70
00:03:38,770 --> 00:03:39,970
maar op een server.

71
00:03:39,970 --> 00:03:42,110
Node.js, dat is heel erg
in die geest ook.

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

73
00:03:43,650 --> 00:03:46,990
Android is een zeer populaire alternatief
naar iOS en Windows Phone

74
00:03:46,990 --> 00:03:48,790
en andere mobiele platforms.

75
00:03:48,790 --> 00:03:51,180
En Web Security actieve verdediging.

76
00:03:51,180 --> 00:03:54,590
>> Dus in feite, als je zou willen
om deel te nemen in deze, laat me

77
00:03:54,590 --> 00:03:55,840
noteer deze.

78
00:03:55,840 --> 00:03:57,790
We zijn erg blij om te zeggen dat
onze vrienden bij Leap

79
00:03:57,790 --> 00:03:59,140
Beweging, dat is een startup -

80
00:03:59,140 --> 00:04:01,300
dit apparaat eigenlijk alleen maar kwam
een paar maanden geleden -

81
00:04:01,300 --> 00:04:05,960
heeft gedoneerd 30 dergelijke apparaten
de klasse voor zoveel studenten als

82
00:04:05,960 --> 00:04:08,670
u wilt de hardware lenen
naar het einde van semester en gebruiken voor

83
00:04:08,670 --> 00:04:10,390
een feitelijke afstudeerproject.

84
00:04:10,390 --> 00:04:11,890
Ze ondersteunen een aantal talen.

85
00:04:11,890 --> 00:04:16,040
Geen van hen C, geen van PHP, zodat
realiseren van een of meer van deze seminars

86
00:04:16,040 --> 00:04:16,899
zou kunnen blijken van belangstelling.

87
00:04:16,899 --> 00:04:19,730
En alle van hen zal worden gefilmd in
het geval dat u niet in staat bent

88
00:04:19,730 --> 00:04:21,380
bij te wonen in persoon.

89
00:04:21,380 --> 00:04:25,000
Het schema via aangekondigd worden
e-mail als we stollen kamers.

90
00:04:25,000 --> 00:04:28,460
>> En tot slot, als je naar
projects.cs.50.net, is een website

91
00:04:28,460 --> 00:04:31,450
We houden elk jaar dat we uitnodigen
mensen uit de gemeenschap, faculteit,

92
00:04:31,450 --> 00:04:36,420
afdelingen, medewerkers, en beide
in een buiten de CS50 aan

93
00:04:36,420 --> 00:04:37,730
voorstellen projectideeën.

94
00:04:37,730 --> 00:04:39,050
Dingen van belang om groepen studenten.

95
00:04:39,050 --> 00:04:40,600
Dingen van belang om afdelingen.

96
00:04:40,600 --> 00:04:43,990
Dus wees draaien er als je moeite hebt
met onzekerheid over wat je

97
00:04:43,990 --> 00:04:46,700
zelf zou willen aanpakken.

98
00:04:46,700 --> 00:04:51,760
>> Dus laatste keer dat we een aantoonbaar geïntroduceerd
meer complexe datastructuur dan wij hadden

99
00:04:51,760 --> 00:04:53,300
gezien in weken verleden.

100
00:04:53,300 --> 00:04:56,550
We hadden gebruik gemaakt van arrays vrij
gelukkig als nuttig als

101
00:04:56,550 --> 00:04:58,160
simplistisch datastructuur.

102
00:04:58,160 --> 00:05:00,570
Vervolgens introduceerden we deze die
Natuurlijk zijn verbonden lijsten.

103
00:05:00,570 --> 00:05:05,470
En wat was een van de motivaties voor
invoering van deze datastructuur?

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

105
00:05:06,930 --> 00:05:07,250
Wat is dat?

106
00:05:07,250 --> 00:05:08,080
>> PUBLIEK: Dynamische grootte.

107
00:05:08,080 --> 00:05:09,040
>> DAVID Malan: Dynamische grootte.

108
00:05:09,040 --> 00:05:11,890
Dus terwijl in array, moet je
weet de grootte van tevoren bij

109
00:05:11,890 --> 00:05:12,740
toewijzen u het.

110
00:05:12,740 --> 00:05:14,380
In gelinkte lijst, doe je niet
moeten weten dat.

111
00:05:14,380 --> 00:05:17,610
Je kunt gewoon malloc, of meer in het algemeen,
toewijzen van een extra

112
00:05:17,610 --> 00:05:20,720
knooppunt, om zo te zeggen, elke keer dat je
meer data wilt invoegen.

113
00:05:20,720 --> 00:05:22,670
En knooppunt heeft geen vooraf bepaalde betekenis.

114
00:05:22,670 --> 00:05:25,580
Het is gewoon een algemene term beschrijft
een soort container die we

115
00:05:25,580 --> 00:05:29,610
gebruikt in onze datastructuur te slaan
sommige post plaats, in dit

116
00:05:29,610 --> 00:05:31,750
geval toevallig gehele getallen.

117
00:05:31,750 --> 00:05:33,160
>> Maar er is altijd een afweging.

118
00:05:33,160 --> 00:05:38,070
Dus krijgen we dynamische afmetingen van de data
structuur, maar welke prijs moeten we betalen?

119
00:05:38,070 --> 00:05:40,040
Wat is het nadeel van gelinkte lijsten?

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

121
00:05:41,006 --> 00:05:41,980
>> PUBLIEK: Vereist meer geheugen.

122
00:05:41,980 --> 00:05:44,240
>> DAVID Malan: Het vergt meer
geheugen, hoe precies?

123
00:05:44,240 --> 00:05:46,440
>> PUBLIEK: [onverstaanbaar].

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

125
00:05:47,050 --> 00:05:50,460
Dus nu hebben we pointers toegang tot
extra geheugen dat we eerder

126
00:05:50,460 --> 00:05:53,040
niet nodig, omdat het voordeel
, array is natuurlijk dat

127
00:05:53,040 --> 00:05:54,860
alles is aaneengesloten, terug
aan rug aan rug, waarin

128
00:05:54,860 --> 00:05:56,380
geeft je random access.

129
00:05:56,380 --> 00:06:00,710
Want alleen door het gebruik vierkante haken
notatie, of meer technisch aanwijzer

130
00:06:00,710 --> 00:06:03,580
rekenkunde, zeer eenvoudige toevoeging,
hebt u toegang tot alle

131
00:06:03,580 --> 00:06:05,700
elementen in constante tijd.

132
00:06:05,700 --> 00:06:08,975
En in feite, dat is een soort van zinspeelde op
een andere prijs die we betalen met een

133
00:06:08,975 --> 00:06:09,760
gelinkte lijst.

134
00:06:09,760 --> 00:06:13,890
>> Wat gebeurt er met de looptijd van
zoiets als zoeken, als ik wil

135
00:06:13,890 --> 00:06:17,270
vindt u enkele waarde en de binnenkant
van een gekoppelde lijst?

136
00:06:17,270 --> 00:06:20,290
Wat doet mijn rijtijd worden?

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

138
00:06:21,560 --> 00:06:24,060
Als het wordt gesorteerd op?

139
00:06:24,060 --> 00:06:25,440
Wat als de datastructuur is gesorteerd?

140
00:06:25,440 --> 00:06:28,640
Kan ik beter dan grote doen
O van n voor zoeken?

141
00:06:28,640 --> 00:06:31,700
Nee, want in het ergste geval zou
zeer goed gesorteerd, maar het aantal

142
00:06:31,700 --> 00:06:32,950
u zoekt groot zou kunnen zijn.

143
00:06:32,950 --> 00:06:35,370
Het kan het nummer 100, die zijn
kan gebeuren met allemaal

144
00:06:35,370 --> 00:06:36,410
helemaal aan het einde.

145
00:06:36,410 --> 00:06:39,950
En omdat je kunt alleen toegang krijgen tot een gekoppelde
lijst in deze uitvoering door

146
00:06:39,950 --> 00:06:42,690
manier van zijn eerste knooppunt, je bent
nog een beetje pech.

147
00:06:42,690 --> 00:06:47,450
Je moet de hele zaak doorkruisen
van eerste tot de laatste om te weten

148
00:06:47,450 --> 00:06:49,150
die grote waarde, zoals 100.

149
00:06:49,150 --> 00:06:51,350
Of om te bepalen of het
er niet eens.

150
00:06:51,350 --> 00:06:55,960
>> Dus we kunnen niet doen wat algoritme in een data
structuur die er als volgt uitziet?

151
00:06:55,960 --> 00:06:59,460
We kunnen binary search niet doen, want
binary search vereist dat we hadden

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

153
00:07:00,740 --> 00:07:04,500
We konden gewoon springen van plaats tot
locatie zonder te volgen

154
00:07:04,500 --> 00:07:07,080
deze broodkruimels in de vorm
al deze pointers.

155
00:07:07,080 --> 00:07:08,300
>> Nu, hoe hebben we dit implementeren?

156
00:07:08,300 --> 00:07:12,830
Nou, als we naar het scherm hier, indien
kunnen we snel deze gegevens herimplementeren

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

158
00:07:13,440 --> 00:07:15,670
Mijn handschrift is niet zo
hier geweldig, maar we zullen proberen.

159
00:07:15,670 --> 00:07:22,030
Dus typedef struct, en wat deed ik
wil dit ding hier roepen?

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

161
00:07:22,960 --> 00:07:24,580
Dus ik zal ons begonnen.

162
00:07:24,580 --> 00:07:27,860
En nu, wat moet de binnenkant van
de gegevensstructuur die afzonderlijk

163
00:07:27,860 --> 00:07:28,430
gelinkte lijst?

164
00:07:28,430 --> 00:07:29,950
Hoeveel velden?

165
00:07:29,950 --> 00:07:30,450
>> Dus twee.

166
00:07:30,450 --> 00:07:31,570
Men is vrij eenvoudig.

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

168
00:07:33,050 --> 00:07:35,930
En we konden n wat we willen noemen,
maar het moet een int zijn als we

169
00:07:35,930 --> 00:07:37,660
uitvoering van een gekoppelde lijst voor ints.

170
00:07:37,660 --> 00:07:41,920
En nu, wat doet de tweede
veld zijn?

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

172
00:07:43,460 --> 00:07:50,570
Dus als ik het doe struct knoop *, en dan heb ik
kan dit ook wat ik wil noemen,

173
00:07:50,570 --> 00:07:53,510
maar gewoon om duidelijk te zijn Ik bel
het volgende, zoals we hebben gedaan.

174
00:07:53,510 --> 00:07:55,270
En dan zal ik mijn accolades sluiten.

175
00:07:55,270 --> 00:08:00,700
>> En nu, als de vorige keer,
Ik zet knooppunt hier beneden.

176
00:08:00,700 --> 00:08:03,830
Maar als ik dit te verklaren is als een
knooppunt, waarom heb ik moeite zo

177
00:08:03,830 --> 00:08:07,320
verbose hier in het verklaren struct
* volgende knooppunt, in tegenstelling

178
00:08:07,320 --> 00:08:09,210
om gewoon knooppunt * next?

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

180
00:08:09,904 --> 00:08:12,810
>> PUBLIEK: [onverstaanbaar].

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

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

183
00:08:14,530 --> 00:08:18,320
Omdat C neemt je echt letterlijk en
ziet alleen de definitie van knooppunt

184
00:08:18,320 --> 00:08:21,230
weg hier beneden, kun je niet
verwijzen naar het hier.

185
00:08:21,230 --> 00:08:24,760
Dus hebben we dit soort preventieve
verklaring hier, die weliswaar is

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

187
00:08:25,390 --> 00:08:27,810
Struct knooppunt, dat betekent
kunnen we nu toegang tot het

188
00:08:27,810 --> 00:08:29,760
binnenzijde van de gegevensstructuur.

189
00:08:29,760 --> 00:08:33,370
>> En als een terzijde, want dit is
steeds een beetje meer subjectieve nu,

190
00:08:33,370 --> 00:08:36,230
de ster kan hier technisch gaan,
het kan hier gaan, het kan

191
00:08:36,230 --> 00:08:37,179
gaan zelfs in het midden.

192
00:08:37,179 --> 00:08:39,890
We hebben aangenomen, in de stijl gids voor
de cursus, de conventie van zetten

193
00:08:39,890 --> 00:08:42,299
de ster naast de gegevens
type, die in dit geval,

194
00:08:42,299 --> 00:08:43,460
zou struct node.

195
00:08:43,460 --> 00:08:46,620
Maar realiseren in veel leerboeken en
keer gevonden, zou je inderdaad

196
00:08:46,620 --> 00:08:48,450
zien het aan de andere kant.

197
00:08:48,450 --> 00:08:52,200
Maar gewoon beseffen dat beide ook daadwerkelijk
werken en je moet gewoon

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

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

200
00:08:53,580 --> 00:08:55,630
Dus dat was onze verklaring
van struct knoop.

201
00:08:55,630 --> 00:08:59,430
Maar toen begonnen we meer doen
verfijnde dingen.

202
00:08:59,430 --> 00:09:03,410
Bijvoorbeeld, hebben we besloten in te voeren
iets als een hash table.

203
00:09:03,410 --> 00:09:08,160
Dus hier is een hash-tabel van grootte n,
geïndexeerd vanaf 0 in de linkerbovenhoek te n

204
00:09:08,160 --> 00:09:09,690
minus 1 linksonder.

205
00:09:09,690 --> 00:09:11,640
Dit kan een hash
tafel voor iets.

206
00:09:11,640 --> 00:09:15,340
Maar wat voor soort dingen hebben we praten
over het gebruik van een hash-tabel voor?

207
00:09:15,340 --> 00:09:18,370
Het opslaan van wat?

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

209
00:09:18,800 --> 00:09:20,870
We konden namen doen zoals
we deden vorige keer.

210
00:09:20,870 --> 00:09:22,200
En echt, kunt u iets op te slaan.

211
00:09:22,200 --> 00:09:24,640
En we zullen ook dit zien in
PHP en JavaScript.

212
00:09:24,640 --> 00:09:28,550
Een hash table is een mooi soort van Zwitserse
Zakmes die u toelaat om op te slaan

213
00:09:28,550 --> 00:09:33,690
vrijwel alles wat je wilt binnenkant van
het associëren van sleutels waarden.

214
00:09:33,690 --> 00:09:34,770
Toetsen met waarden.

215
00:09:34,770 --> 00:09:37,800
>> Nu in dit eenvoudige geval, onze
toetsen zijn gewoon nummers.

216
00:09:37,800 --> 00:09:40,380
We implementeren van een hash
tabel als een array.

217
00:09:40,380 --> 00:09:43,500
En zo de toetsen zijn 0,
1, 2, enzovoort.

218
00:09:43,500 --> 00:09:47,200
En zo zijn wij, als mens, besloot vorig
week dat je weet wat, als we

219
00:09:47,200 --> 00:09:50,410
gaat winkel namen, laten we gewoon
arbitrair, maar vrij redelijk,

220
00:09:50,410 --> 00:09:54,680
veronderstellen dat Alice, een met naam,
zal alleen worden geïndexeerd in 0.

221
00:09:54,680 --> 00:09:58,030
En Bob, een B naam, zal worden geïndexeerd
in 1, enzovoort.

222
00:09:58,030 --> 00:10:02,490
Dus we hadden een mapping tussen de ingangen,
die zijn snaren, en de hash

223
00:10:02,490 --> 00:10:04,560
plaatsen, welke getallen.

224
00:10:04,560 --> 00:10:07,740
>> Zodat proces is algemeen bekend als
een hash-functie, en je kan echt

225
00:10:07,740 --> 00:10:09,130
implementeren in code.

226
00:10:09,130 --> 00:10:12,080
Als ik wilde een hash-functie te implementeren
dat is precies wat we wel

227
00:10:12,080 --> 00:10:17,070
zojuist beschreven van de vorige keer, ik zou
verklaren een functie die neemt, als

228
00:10:17,070 --> 00:10:18,330
ingang voor bijvoorbeeld -

229
00:10:18,330 --> 00:10:22,190
en laten we dit doen op deze
scherm over hier.

230
00:10:22,190 --> 00:10:26,180
Als ik wilde implementeren van een hash
functie, zou ik zeggen

231
00:10:26,180 --> 00:10:27,410
zoiets als dit.

232
00:10:27,410 --> 00:10:29,030
>> Het gaat om een ​​int terug.

233
00:10:29,030 --> 00:10:33,600
Het gaat hash genoemd te worden, en het is
gaan als argument een om te accepteren

234
00:10:33,600 --> 00:10:38,920
snaar, of we kunnen nu meer goede,
en zeggen: char *, we noemen het s.

235
00:10:38,920 --> 00:10:43,840
En dan al deze functie te maken heeft,
uiteindelijk, wordt terug een int.

236
00:10:43,840 --> 00:10:45,990
Nu, hoe het doet dat misschien
niet zo duidelijk.

237
00:10:45,990 --> 00:10:49,510
Ik ga dit uitvoeren zonder
vormen van foutcontrole nu.

238
00:10:49,510 --> 00:10:55,740
Ik ga gewoon blindelings zeggen, terug
wat is op s beugel 0, minus,

239
00:10:55,740 --> 00:10:58,850
laten we zeggen, de hoofdstad Een puntkomma.

240
00:10:58,850 --> 00:10:59,960
>> Helemaal kapot.

241
00:10:59,960 --> 00:11:02,620
Het is niet perfect omdat
men, wat als s null is?

242
00:11:02,620 --> 00:11:04,000
Slechte dingen gaan gebeuren.

243
00:11:04,000 --> 00:11:07,940
Twee, wat als de eerste letter in dit
naam is niet een hoofdletter?

244
00:11:07,940 --> 00:11:09,860
Dat gaat niet draaien
goed uit ook.

245
00:11:09,860 --> 00:11:11,970
Het is misschien een kleine letter worden
of geen brief helemaal.

246
00:11:11,970 --> 00:11:15,520
Zo totaal ruimte voor verbetering hier,
maar dit is het basisidee.

247
00:11:15,520 --> 00:11:19,010
>> Wat we vorige week beschreven mondeling als
gewoon een proces van het in kaart brengen Alice aan

248
00:11:19,010 --> 00:11:23,360
0 en Bob 1 kan worden uitgedrukt
zeker meer formulaically als C

249
00:11:23,360 --> 00:11:24,320
functioneren hier.

250
00:11:24,320 --> 00:11:28,630
Riep opnieuw hash, neemt een string als
ingang, en dan een of andere manier iets doet

251
00:11:28,630 --> 00:11:31,020
met die ingang met een uitgang produceren.

252
00:11:31,020 --> 00:11:34,130
Niet in tegenstelling tot onze black box beschrijving
dat we lang hebben gedaan.

253
00:11:34,130 --> 00:11:36,550
Ik weet niet hoe dit zou kunnen zijn
werken onder de motorkap.

254
00:11:36,550 --> 00:11:40,120
>> Voor probleem set 6, een van de uitdagingen
is voor u om te beslissen welke

255
00:11:40,120 --> 00:11:41,920
zal uw hash-functie zijn?

256
00:11:41,920 --> 00:11:45,760
Wat gaat de binnenkant van die zwart zijn
doos, en vermoedelijk, het zal een

257
00:11:45,760 --> 00:11:50,380
wat interessanter dan deze, en
zeker meer gevoelig voor fouten

258
00:11:50,380 --> 00:11:53,180
controle dan dit
implementatie.

259
00:11:53,180 --> 00:11:54,580
>> Maar er kunnen problemen ontstaan, toch?

260
00:11:54,580 --> 00:11:57,760
Als we een datastructuur, zoals deze
men, wat is een van de problemen

261
00:11:57,760 --> 00:12:01,600
je kan lopen in de tijd als je plaatst
meer namen in de

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

263
00:12:02,880 --> 00:12:04,630
Je krijgt botsingen, toch?

264
00:12:04,630 --> 00:12:07,560
Wat als je Alice en Aäron,
twee mensen van wie de namen gebeurd

265
00:12:07,560 --> 00:12:08,190
te beginnen A?

266
00:12:08,190 --> 00:12:11,660
Dat roept de vraag op, waar u
zet de tweede dergelijke Een naam?

267
00:12:11,660 --> 00:12:15,050
>> Nou, je zou naïef zet ze gewoon
waar Bob hoort, maar dan Bob is

268
00:12:15,050 --> 00:12:17,300
soort geschroefd als je probeert te
plaatst zijn naam naast en

269
00:12:17,300 --> 00:12:18,240
er is geen plaats voor hem.

270
00:12:18,240 --> 00:12:21,400
Dus je zou Bob waar Charlie is, zet
en je kunt voorstellen dat dit zeer snel

271
00:12:21,400 --> 00:12:23,020
delegeren naar een beetje een puinhoop.

272
00:12:23,020 --> 00:12:25,600
Iets lineair in het einde, waar u
gewoon de hele zaak zoeken

273
00:12:25,600 --> 00:12:28,190
op zoek naar Alice of Bob
of Aaron of Charlie.

274
00:12:28,190 --> 00:12:33,230
>> Dus in plaats daarvan hebben we voorgesteld, in plaats van alleen
lineair peilen naar open ruimten

275
00:12:33,230 --> 00:12:36,450
en plopping de namen daar, we
voorgesteld een liefhebber aanpak.

276
00:12:36,450 --> 00:12:41,740
Een hash table nog steeds uitgevoerd met een
reeks van indices, maar de data type

277
00:12:41,740 --> 00:12:44,500
deze indices waren nu pointers.

278
00:12:44,500 --> 00:12:47,360
Pointers naar wat?

279
00:12:47,360 --> 00:12:48,730
Pointers naar gelinkte lijsten.

280
00:12:48,730 --> 00:12:53,330
>> Omdat herinneren dat een gelinkte lijst is
eigenlijk gewoon een pointer naar een knooppunt, en

281
00:12:53,330 --> 00:12:57,110
het knooppunt een volgend veld, en dat knooppunt
een volgende veld, enzovoort.

282
00:12:57,110 --> 00:13:00,690
Dus je kunt nu denken van deze array op
de linkerkant van een hash tabel

283
00:13:00,690 --> 00:13:01,820
leidt tot een gekoppelde lijst.

284
00:13:01,820 --> 00:13:07,000
Het voordeel daarvan is als je een
botsing tussen Alice en Aäron,

285
00:13:07,000 --> 00:13:09,300
wat doe je dan met de
tweede dergelijke persoon?

286
00:13:09,300 --> 00:13:14,150
Sluit je er gewoon hem of haar naar de
end of zelfs het begin

287
00:13:14,150 --> 00:13:15,490
van die gelinkte lijst.

288
00:13:15,490 --> 00:13:17,340
>> En eigenlijk, laten we gewoon noodle door
dat voor slechts een seconde.

289
00:13:17,340 --> 00:13:18,640
Waar zou het meest logisch?

290
00:13:18,640 --> 00:13:22,060
Als ik Alice voegen en ze eindigt bij
de eerste plaats, dan probeer ik

291
00:13:22,060 --> 00:13:25,310
neem de naam van Aaron, en er is
uiteraard een aanrijding, moet ik

292
00:13:25,310 --> 00:13:27,400
hem in het begin
van de gelinkte lijst?

293
00:13:27,400 --> 00:13:30,944
Dat is op die eerste locatie,
of aan het einde?

294
00:13:30,944 --> 00:13:31,440
>> PUBLIEK: [onverstaanbaar].

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

296
00:13:31,990 --> 00:13:32,490
Ik hoorde begin.

297
00:13:32,490 --> 00:13:33,903
Waarom bij het begin?

298
00:13:33,903 --> 00:13:34,750
>> PUBLIEK: [onverstaanbaar].

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

300
00:13:34,940 --> 00:13:36,520
Het is alfabetisch, dus dat is leuk.

301
00:13:36,520 --> 00:13:37,330
Dat is een goede eigenschap.

302
00:13:37,330 --> 00:13:39,335
Het zal me wat tijd besparen potentieel.

303
00:13:39,335 --> 00:13:43,290
Het zal me niet laten doen binair zoeken, maar ik
zou ten minste in staat om uit te breken

304
00:13:43,290 --> 00:13:47,340
van een lus als ik realiseer, nou, ik ben weg
Vroeger waren Aaron zou in deze zijn

305
00:13:47,340 --> 00:13:48,310
gesorteerd gelinkte lijst.

306
00:13:48,310 --> 00:13:50,360
Ik heb niet om mijn tijd te verspillen op zoek
helemaal tot het einde.

307
00:13:50,360 --> 00:13:51,530
Dus dat is redelijk.

308
00:13:51,530 --> 00:13:54,710
Waarom anders zou u wilt invoegen
de botsende naam bij de

309
00:13:54,710 --> 00:13:56,660
het begin van de lijst?

310
00:13:56,660 --> 00:13:57,397
Wat is dat?

311
00:13:57,397 --> 00:13:58,680
>> PUBLIEK: [onverstaanbaar].

312
00:13:58,680 --> 00:14:00,820
>> DAVID Malan: Het kan lang duren
om naar het einde van de lijst.

313
00:14:00,820 --> 00:14:02,490
En inderdaad, langer en langer.

314
00:14:02,490 --> 00:14:04,920
Hoe meer namen je plaatst dat
beginnen met A, hoe langer dat

315
00:14:04,920 --> 00:14:06,280
keten gaat krijgen.

316
00:14:06,280 --> 00:14:07,890
Hoe langer gekoppeld
lijst gaat krijgen.

317
00:14:07,890 --> 00:14:09,420
Dus je bent eigenlijk gewoon
verspillen van uw tijd.

318
00:14:09,420 --> 00:14:14,070
Misschien bent u beter af handhaven
constante invoegtijd, big O van 1,

319
00:14:14,070 --> 00:14:18,470
door altijd de botsende naam bij zetten
het begin van de gekoppelde lijst

320
00:14:18,470 --> 00:14:21,230
en niet verontrustend zoveel
over het sorteren.

321
00:14:21,230 --> 00:14:22,600
>> Wat is het beste antwoord?

322
00:14:22,600 --> 00:14:23,320
Het is onduidelijk.

323
00:14:23,320 --> 00:14:26,140
Het soort is afhankelijk van wat de
distributie, wat de patroon is

324
00:14:26,140 --> 00:14:27,850
van de namen die u invoegt.

325
00:14:27,850 --> 00:14:29,430
Het is niet per se
een duidelijk antwoord.

326
00:14:29,430 --> 00:14:33,100
Maar hier, nogmaals, is
een ontwerp gelegenheid.

327
00:14:33,100 --> 00:14:37,220
>> Dus we bekeken toen dit ding, dat
is echt de andere grote kans

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

329
00:14:38,180 --> 00:14:41,770
En beseffen, als je nog niet hebt,
Zamyla duikt in deze beide, hash

330
00:14:41,770 --> 00:14:43,260
tabellen en probeert, in meer detail.

331
00:14:43,260 --> 00:14:45,630
En de video walkthrough is
ingebed in p-set spec.

332
00:14:45,630 --> 00:14:46,590
Dit was een Trie -

333
00:14:46,590 --> 00:14:51,670
T-R-I-E. En wat interessant was
hiervoor was dat de looptijd

334
00:14:51,670 --> 00:14:59,510
van het zoeken naar een naam, zoals Maxwell
vorige keer, was groot O van wat?

335
00:14:59,510 --> 00:15:01,040
Wat is dat?

336
00:15:01,040 --> 00:15:01,920
>> PUBLIEK: Het aantal letters.

337
00:15:01,920 --> 00:15:02,550
>> DAVID Malan: Aantal letters.

338
00:15:02,550 --> 00:15:03,210
Ik hoorde twee dingen.

339
00:15:03,210 --> 00:15:04,630
Aantal letters en constante tijd.

340
00:15:04,630 --> 00:15:05,540
Dus laten we gaan met die eerste.

341
00:15:05,540 --> 00:15:06,410
Het aantal letters.

342
00:15:06,410 --> 00:15:10,195
Nou, deze datastructuur, recall, is
als een boom, een stamboom, elk van

343
00:15:10,195 --> 00:15:12,860
waarvan de knopen bestaan ​​uit arrays.

344
00:15:12,860 --> 00:15:16,300
En die arrays zijn verwijzingen naar
andere dergelijke knooppunten of soortgelijke

345
00:15:16,300 --> 00:15:17,670
arrays in de boom.

346
00:15:17,670 --> 00:15:22,890
>> Dus als we wilden dan bepalen
of Maxwell is in hier, zou ik gaan

347
00:15:22,890 --> 00:15:26,890
naar de eerste matrix, op de top van
de boom, de zogenaamde wortel, bovenop

348
00:15:26,890 --> 00:15:30,521
de Trie, en volg de m aanwijzer,
dan is het een pointer, dan x,

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

350
00:15:31,710 --> 00:15:34,910
En dan als ik zie wat speciaal symbool,
hier aangeduid als een driehoek.

351
00:15:34,910 --> 00:15:38,480
In code ziet u stellen wij voor dat u
geïmplementeerd als een bool, gewoon zeggen ja

352
00:15:38,480 --> 00:15:40,540
of nee, een woord stopt hier.

353
00:15:40,540 --> 00:15:45,270
>> Nou, zodra we weg naar M-A-X-W-E-L-L,
voelt als zeven, misschien

354
00:15:45,270 --> 00:15:48,910
acht als we gaan nog een verleden, acht
stappen om Maxwell vinden.

355
00:15:48,910 --> 00:15:53,050
Of laten we het noemen K. Maar herinner laatste
tijd, ik betoogd dat als er

356
00:15:53,050 --> 00:15:57,540
realistisch een maximum lengte van de
woord, zoals 40-sommige-oneven tekens, een

357
00:15:57,540 --> 00:16:00,810
maximumlengte impliceert
een constante waarde.

358
00:16:00,810 --> 00:16:05,770
Dus echt, ja, het is technisch big O
van 8 of 7, of echt grote O van K. Maar

359
00:16:05,770 --> 00:16:09,420
als er een eindige pet op wat
K zou kunnen zijn, het is een constante.

360
00:16:09,420 --> 00:16:12,080
En dus is het grote O van 1 op
het einde van de dag.

361
00:16:12,080 --> 00:16:13,040
>> Niet in de echte wereld.

362
00:16:13,040 --> 00:16:15,960
Niet wanneer u daadwerkelijk beginnen met kijken
uw klok als uw programma's lopen.

363
00:16:15,960 --> 00:16:20,690
Het is absoluut gaat een beetje te zijn
langzamer dan echt constant

364
00:16:20,690 --> 00:16:21,840
tijd met een stap.

365
00:16:21,840 --> 00:16:25,540
Het gaat om zeven of acht stappen,
maar dat is veel, veel beter

366
00:16:25,540 --> 00:16:30,080
dan een algoritme zoals grote O van n die
afhankelijk van de grootte van wat in de

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

368
00:16:31,220 --> 00:16:34,970
>> Let op de kop is hier dat we kunnen invoegen
een miljoen meer namen in deze

369
00:16:34,970 --> 00:16:38,170
datastructuur, maar hoeveel meer stappen
gaat het om ons te vinden

370
00:16:38,170 --> 00:16:40,480
Maxwell in dat geval?

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

372
00:16:40,780 --> 00:16:41,820
Hij is onaangetast.

373
00:16:41,820 --> 00:16:45,480
En tot nu toe, ik denk niet dat we hebben gezien
een voorbeeld van een datastructuur of een

374
00:16:45,480 --> 00:16:48,560
algoritme dat volledig was
beïnvloed door externe

375
00:16:48,560 --> 00:16:50,040
gedrag zoals dat.

376
00:16:50,040 --> 00:16:51,160
Maar dit kan niet verbazingwekkend.

377
00:16:51,160 --> 00:16:52,900
Dit kan niet de enige oplossing zijn
de p-set

378
00:16:52,900 --> 00:16:53,570
>> En het is niet.

379
00:16:53,570 --> 00:16:55,980
Dit is niet noodzakelijkerwijs de gegevens
structuur moet je aangetrokken tot,

380
00:16:55,980 --> 00:16:58,220
want zoals hash tabellen, afweging.

381
00:16:58,220 --> 00:17:00,500
Wat is de prijs die u betaalt hier?

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

383
00:17:00,940 --> 00:17:02,890
Ik bedoel, dit is een gruwelijke
hoeveelheid geheugen.

384
00:17:02,890 --> 00:17:05,569
En je kunt niet helemaal zien hier omdat
de auteur van deze foto

385
00:17:05,569 --> 00:17:09,420
uiteraard afgeknotte Alle matrices,
en wij niet ziet veel A's en

386
00:17:09,420 --> 00:17:12,700
B en C en Q's en Y's
en Z in deze arrays.

387
00:17:12,700 --> 00:17:13,630
Maar ze zijn er.

388
00:17:13,630 --> 00:17:17,660
>> Elk van deze knooppunten een hele reeks
van ongeveer 26 of meer bytes, elk

389
00:17:17,660 --> 00:17:19,170
waarin een letter staat.

390
00:17:19,170 --> 00:17:22,920
27 in ons geval, zodat we kunnen ondersteunen
apostrof in het probleem set.

391
00:17:22,920 --> 00:17:27,030
Dus dit datastructuur is echt,
echt dicht en breed.

392
00:17:27,030 --> 00:17:30,880
En dat alleen al zou kunnen eindigen vertragen
dingen neer, of in ieder geval kost je een

393
00:17:30,880 --> 00:17:32,240
veel meer ruimte.

394
00:17:32,240 --> 00:17:34,020
Maar nogmaals, kunnen we trekken
vergelijkingen hier.

395
00:17:34,020 --> 00:17:39,190
>> Herinneren een tijdje terug, we veel bereikt
meer spannende lopende tijd in het sorteren

396
00:17:39,190 --> 00:17:42,880
wanneer we gebruik merge sort, maar de prijs
We betaalden te bereiken n log n voor samenvoegen

397
00:17:42,880 --> 00:17:46,930
sorteer vereist dat we uitgeven
meer welke bron?

398
00:17:46,930 --> 00:17:47,690
Meer ruimte.

399
00:17:47,690 --> 00:17:50,530
We hadden behoefte aan een secundaire array
kopiëren mensen in, net als

400
00:17:50,530 --> 00:17:51,620
we hebben hier op het podium.

401
00:17:51,620 --> 00:17:55,880
Dus nogmaals, geen duidelijke winnaars,
maar enkel subjectieve ontwerp

402
00:17:55,880 --> 00:17:57,710
beslissingen worden gemaakt.

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

404
00:17:58,060 --> 00:17:59,130
Dus hoe zit dit?

405
00:17:59,130 --> 00:18:02,050
Herkent iemand die D-Hall?

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

407
00:18:02,440 --> 00:18:03,170
Dus drie van ons doen.

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

409
00:18:03,750 --> 00:18:05,070
Dus dit is voor Mather's dineren.

410
00:18:05,070 --> 00:18:09,650
Ik wed dat alle eetzalen hebben
stapels trays als deze.

411
00:18:09,650 --> 00:18:11,950
En dit is eigenlijk representatief
van iets wat we hebben

412
00:18:11,950 --> 00:18:13,050
natuurlijk al gezien.

413
00:18:13,050 --> 00:18:14,850
We noemden het letterlijk een stapel.

414
00:18:14,850 --> 00:18:18,970
En de stack, in termen van uw
geheugen van de computer, is de plaats waar de gegevens gaat

415
00:18:18,970 --> 00:18:20,460
terwijl functies worden genoemd.

416
00:18:20,460 --> 00:18:23,410
>> Bijvoorbeeld, wat voor soort dingen gaan
op de stapel ten opzichte van de

417
00:18:23,410 --> 00:18:27,420
geheugen layout die we hebben besproken
in weken verleden?

418
00:18:27,420 --> 00:18:28,736
Wat is dat?

419
00:18:28,736 --> 00:18:29,670
>> PUBLIEK: Oproepen naar functies.

420
00:18:29,670 --> 00:18:30,260
>> DAVID Malan: Het spijt me.

421
00:18:30,260 --> 00:18:31,210
>> PUBLIEK: Oproepen naar functies.

422
00:18:31,210 --> 00:18:33,590
>> DAVID Malan: Gesprekken naar functies, maar
specifiek, wat er in elk van

423
00:18:33,590 --> 00:18:35,340
die frames?

424
00:18:35,340 --> 00:18:37,220
Wat voor dingen?

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

426
00:18:37,460 --> 00:18:38,500
Zodat lokale variabelen.

427
00:18:38,500 --> 00:18:43,080
Wanneer we nodig hadden een aantal lokale opslag,
als een argument, of int I, of int

428
00:18:43,080 --> 00:18:45,940
temp, of wat dan ook de lokale
variabel is, waar we zijn geweest

429
00:18:45,940 --> 00:18:47,210
zetten dat op de stapel.

430
00:18:47,210 --> 00:18:49,610
En we noemen het een stapel omdat
van die gelaagdheid idee.

431
00:18:49,610 --> 00:18:52,940
Gewoon een soort overeenkomsten met de werkelijkheid,
het begrip daarvan.

432
00:18:52,940 --> 00:18:56,650
>> Maar het blijkt dat een stapel kan ook
worden beschouwd als een gegevensstructuur, een

433
00:18:56,650 --> 00:19:00,110
alternatief voor een matrix, een alternatief
een gekoppelde lijst.

434
00:19:00,110 --> 00:19:02,770
Iets conceptueel interessanter
dat nog kan worden

435
00:19:02,770 --> 00:19:06,030
uitgevoerd met behulp van beide
dingen, maar het is een ander soort

436
00:19:06,030 --> 00:19:09,140
datastructuur ondersteunen, echt,
maar twee operaties.

437
00:19:09,140 --> 00:19:11,000
Maar u kunt toevoegen aan liefhebber
functies dan deze.

438
00:19:11,000 --> 00:19:12,180
Maar dit zijn de basics -

439
00:19:12,180 --> 00:19:13,510
push en pop.

440
00:19:13,510 --> 00:19:19,240
>> Het idee van een stack is dat als ik
hebben hier, met of zonder Annenberg

441
00:19:19,240 --> 00:19:22,880
wetende, een lade van naast de deur
met het nummer 9 op.

442
00:19:22,880 --> 00:19:23,870
Dus gewoon een int.

443
00:19:23,870 --> 00:19:26,990
En ik wil dit duwen op de data
structuur, die nog leeg is.

444
00:19:26,990 --> 00:19:28,790
Beschouw dit de bodem van de stapel.

445
00:19:28,790 --> 00:19:33,150
Ik zou dit nummer 9 te duwen op de
stapelen, en nu is het daar.

446
00:19:33,150 --> 00:19:36,040
>> Maar het interessante ding over een stapel
is dat als ik nu wil duwen

447
00:19:36,040 --> 00:19:40,210
een andere waarde, zoals 17, en ik duw
deze op de stapel, ik ga doen

448
00:19:40,210 --> 00:19:43,290
het enige intuïtieve ding, ik ben gewoon gaan
om het recht te zetten, waar wij mensen

449
00:19:43,290 --> 00:19:45,180
zou geneigd om het te zetten, op de top.

450
00:19:45,180 --> 00:19:48,850
Maar wat is interessant nu
is, hoe krijg ik om 9?

451
00:19:48,850 --> 00:19:50,670
Weet je, ik doe niet zonder enige moeite.

452
00:19:50,670 --> 00:19:54,070
>> Dus wat is er interessant aan
een stack is dat door het ontwerp,

453
00:19:54,070 --> 00:19:56,330
het is een LIFO datastructuur.

454
00:19:56,330 --> 00:19:59,680
Domme manier van het beschrijven
last in, first out.

455
00:19:59,680 --> 00:20:03,280
Dus het laatste nummer in
op dit moment was 17.

456
00:20:03,280 --> 00:20:07,540
Dus als ik iets wil knallen
van de stack, het kan alleen worden 17.

457
00:20:07,540 --> 00:20:11,890
Dus er is een verplichte volgorde van
activiteiten hier, waar het laatste item

458
00:20:11,890 --> 00:20:14,260
moet in de eerste buiten.

459
00:20:14,260 --> 00:20:16,440
Vandaar het acroniem, LIFO.

460
00:20:16,440 --> 00:20:19,160
>> Dus waarom zou dit nuttig zijn?

461
00:20:19,160 --> 00:20:22,690
Zijn hun contexten waarin je zou
wil een datastructuur als deze?

462
00:20:22,690 --> 00:20:24,810
Nou, het is zeker nuttig geweest
binnenkant van een computer.

463
00:20:24,810 --> 00:20:29,050
Dus besturingssystemen dit duidelijk te gebruiken
soort datastructuur stacks.

464
00:20:29,050 --> 00:20:32,800
We zullen ook zien hetzelfde idee
als het gaat om webpagina's.

465
00:20:32,800 --> 00:20:35,890
Dus deze week en volgende week en daarbuiten,
en als je beginnen met de uitvoering web

466
00:20:35,890 --> 00:20:39,490
pagina's in een taal genaamd HTML, kunt u
gebruikt, namelijk gegevensstructuur zoals

467
00:20:39,490 --> 00:20:42,690
Dit om te bepalen of de pagina
is correct geformatteerd.

468
00:20:42,690 --> 00:20:47,170
Want we zullen zien alle webpagina's volgen
een soort van hiërarchie, een inkeping

469
00:20:47,170 --> 00:20:52,030
die aan het eind van de dag, een
boomstructuur onder de motorkap.

470
00:20:52,030 --> 00:20:53,620
Dus meer op dat in slechts een beetje.

471
00:20:53,620 --> 00:20:56,560
>> Maar voor nu, laten we voorstellen voor een
ogenblik, hoe zouden we gaan over

472
00:20:56,560 --> 00:20:58,830
wat neerkomt op wat een stack is?

473
00:20:58,830 --> 00:21:03,370
Laat ik stel voor dat we de uitvoering van
een stapel met code zoals deze.

474
00:21:03,370 --> 00:21:07,990
Dus een stapel gaat erin om
twee dingen, een array, genaamd trays,

475
00:21:07,990 --> 00:21:09,510
alleen in overeenstemming te zijn met de demo.

476
00:21:09,510 --> 00:21:12,660
En elk van de items in die array
gaat om een ​​type int zijn.

477
00:21:12,660 --> 00:21:14,740
En de capaciteit is vermoedelijk wat?

478
00:21:14,740 --> 00:21:18,796
Want ik heb niet geschreven de
volledige definitie hier.

479
00:21:18,796 --> 00:21:21,535
>> Het is waarschijnlijk de maximale
grootte van de matrix.

480
00:21:21,535 --> 00:21:25,150
En het is waarschijnlijk verklaard als een scherpe
voorschriften op het begin van het bestand, sommige

481
00:21:25,150 --> 00:21:28,450
soort van constante zoals gesuggereerd door
de loutere kapitalisatie.

482
00:21:28,450 --> 00:21:32,250
Dus ergens capaciteit wordt gedefinieerd
zoals de maximale grootte.

483
00:21:32,250 --> 00:21:35,590
Ondertussen, in de datastructuur
bekend als een stapel zal er

484
00:21:35,590 --> 00:21:38,630
een geheel getal alleen bekend
gewoon als maat.

485
00:21:38,630 --> 00:21:43,400
>> Dus als ik deze vertegenwoordigen nu
pictorially, laten we veronderstellen dat deze

486
00:21:43,400 --> 00:21:48,070
hele zwarte doos vertegenwoordigt mijn stack.

487
00:21:48,070 --> 00:21:50,070
Binnenkant van het is twee variabelen.

488
00:21:50,070 --> 00:21:54,780
Dus ik ga naar de loting
eerste de grootte.

489
00:21:54,780 --> 00:21:57,420
En de tweede ik ga
op te stellen als een array.

490
00:21:57,420 --> 00:22:01,060
>> Maar gewoon om dingen ordelijk te houden,
normaal zou ik een array tekenen als

491
00:22:01,060 --> 00:22:04,910
dit, maar het is wel leuk
als we overeenkomen met de werkelijkheid, of

492
00:22:04,910 --> 00:22:06,230
overeenkomen met het mentale model.

493
00:22:06,230 --> 00:22:12,880
Dus laat me in plaats trekken de array
verticaal, dat is gewoon, weer,

494
00:22:12,880 --> 00:22:13,840
vertolking kunstenaar.

495
00:22:13,840 --> 00:22:16,610
Maakt niet echt uit wat het
is onder de motorkap.

496
00:22:16,610 --> 00:22:20,350
En we zullen zeggen dat, bij verstek,
capaciteit gaat worden drie.

497
00:22:20,350 --> 00:22:23,480
Dus dit zal zijn locatie 0, dit
zal plaats 1, dit zijn

498
00:22:23,480 --> 00:22:25,740
zal zijn plaats 2.

499
00:22:25,740 --> 00:22:29,330
>> Als ik omkopen met een stressbal, zou
iemand willen komen en uitvoeren van de

500
00:22:29,330 --> 00:22:30,870
boord hier voor slechts een moment?

501
00:22:30,870 --> 00:22:31,960
OK, eerst zag je hand.

502
00:22:31,960 --> 00:22:33,950
Kom maar naar boven.

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

504
00:22:36,500 --> 00:22:38,760
Dus ik denk dat het Steven.

505
00:22:38,760 --> 00:22:40,035
Kom maar naar boven.

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

507
00:22:40,770 --> 00:22:46,760
>> Maar stel nu dat we terugspoelen naar de oorspronkelijke
toestand van de wereld waar ik

508
00:22:46,760 --> 00:22:52,180
hebben net uitgeroepen tot een stapel, en het is
gaat worden van de capaciteit drie.

509
00:22:52,180 --> 00:22:54,470
Maar omvang is nog niet bepaald.

510
00:22:54,470 --> 00:22:56,100
Trays is nog niet bepaald.

511
00:22:56,100 --> 00:22:57,300
Dus eerst een paar vragen.

512
00:22:57,300 --> 00:23:01,310
En laat me je een microfoon, zodat u kunt
deelnemen actiever in deze.

513
00:23:01,310 --> 00:23:05,190
>> Dus wat is de binnenkant van omvang op dit moment
in de tijd als alles wat ik heb gedaan is

514
00:23:05,190 --> 00:23:09,340
verklaarde een stapel met
een regel code?

515
00:23:09,340 --> 00:23:10,100
>> STEVEN: Niet veel.

516
00:23:10,100 --> 00:23:12,080
>> DAVID MALAN: OK, niet veel.

517
00:23:12,080 --> 00:23:14,410
Weten we wat er binnen in omvang,
weten we wat er in zit

518
00:23:14,410 --> 00:23:16,330
van deze array hier?

519
00:23:16,330 --> 00:23:18,630
>> STEVEN: Gewoon willekeurige code, toch?

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

521
00:23:20,220 --> 00:23:23,230
>> DAVID MALAN: Ja, ik ga
noem het code, maar willekeurig -

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

523
00:23:23,820 --> 00:23:28,290
>> DAVID Malan: Dingen als willekeurig

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

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

526
00:23:29,530 --> 00:23:31,190
Dus vuilnis waarden, toch?

527
00:23:31,190 --> 00:23:33,470
Dus permutaties van 0 en 1's.

528
00:23:33,470 --> 00:23:35,920
Restanten van vorige gebruiksmogelijkheden
van dit geheugen.

529
00:23:35,920 --> 00:23:38,150
En we weten niet echt wat de waarden
zijn, zodat we ze meestal trekken

530
00:23:38,150 --> 00:23:38,930
als vraagtekens.

531
00:23:38,930 --> 00:23:41,990
>> Dus het eerste wat we vermoedelijk
gaat te willen doen hier -

532
00:23:41,990 --> 00:23:46,630
en laat me dit gebied binnen
van er een naam - trays.

533
00:23:46,630 --> 00:23:49,540
Wat moeten we vermoedelijk initialiseren
omvang om als we willen

534
00:23:49,540 --> 00:23:51,040
begint met deze stack?

535
00:23:51,040 --> 00:23:53,070
>> STEVEN: Tray is sub 3.

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

537
00:23:53,910 --> 00:23:56,710
Om duidelijk te zijn, wordt de capaciteit verklaard
elders drie.

538
00:23:56,710 --> 00:23:58,570
En dat is wat ik heb gebruikt
de matrix wijzen.

539
00:23:58,570 --> 00:24:03,535
Size gaat verwijzen naar hoeveel
trays zijn op de stack.

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

541
00:24:03,880 --> 00:24:04,460
>> DAVID Malan: Dus het moet nul zijn.

542
00:24:04,460 --> 00:24:07,760
Ga zo door, en bij elke vinger,
trek een nul in grootte.

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

544
00:24:08,440 --> 00:24:10,920
Dus nu, wat er in deze
hier, weten we niet.

545
00:24:10,920 --> 00:24:12,160
Dit zijn eigenlijk gewoon vuilnis waarden.

546
00:24:12,160 --> 00:24:14,800
Dus we konden vraagtekens te tekenen, maar
laten we het bord schoon voor nu

547
00:24:14,800 --> 00:24:16,300
omdat het niet uit
wat er staat.

548
00:24:16,300 --> 00:24:19,130
We hoeven niet aan de array te initialiseren
om het even wat, want als we weten dat

549
00:24:19,130 --> 00:24:23,100
de grootte van de stapel nul is, goed, we
moet niet op zoek naar iets in

550
00:24:23,100 --> 00:24:25,590
deze array toch op
dit punt in de tijd.

551
00:24:25,590 --> 00:24:29,970
>> Dus nu stel dat ik op de
nummer 9 op de stack.

552
00:24:29,970 --> 00:24:33,750
Hoe moeten we de data structuur updaten
binnenkant van deze zwarte doos?

553
00:24:33,750 --> 00:24:35,540
Welke waarden moeten veranderen?

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

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

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

557
00:24:37,650 --> 00:24:38,770
Maat zal wat worden?

558
00:24:38,770 --> 00:24:39,580
>> STEVEN: Maat zou een te zijn.

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

560
00:24:39,870 --> 00:24:41,110
Dus maat zal worden een.

561
00:24:41,110 --> 00:24:42,540
Dus je kunt dit doen op een paar manieren.

562
00:24:42,540 --> 00:24:46,920
Laat ik u, nu uw
vinger is een gum.

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

564
00:24:47,260 --> 00:24:49,960
Dan is nu je vinger is een borstel.

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

566
00:24:50,330 --> 00:24:52,820
En nu wat er moet veranderen,
uiteraard, in de datastructuur?

567
00:24:52,820 --> 00:24:57,060
>> STEVEN: We gaan uit
bottom tot 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
Dus nog steeds niet uit wat er op het
locatie een of twee omdat ze

571
00:25:01,550 --> 00:25:04,520
vuilnis waarden, maar we moeten niet de moeite
zoek er omdat de grootte is

572
00:25:04,520 --> 00:25:07,540
ons te vertellen dat alleen het eerste element
is eigenlijk legitiem.

573
00:25:07,540 --> 00:25:10,400
Dus nu heb ik duw 17 op de lijst.

574
00:25:10,400 --> 00:25:11,830
Wat gebeurt er met deze foto?

575
00:25:11,830 --> 00:25:14,720
>> STEVEN: Dus grootte zal gaan naar twee.

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

577
00:25:15,300 --> 00:25:16,070
Je bent gum -

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

579
00:25:16,810 --> 00:25:18,026
Je bent een gum.

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

581
00:25:18,840 --> 00:25:19,720
>> DAVID Malan: Je bent een borstel.

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
En wat nog meer?

585
00:25:21,600 --> 00:25:22,600
>> STEVEN: En dan hebben we -

586
00:25:22,600 --> 00:25:22,915
>> DAVID Malan: We geduwd 17.

587
00:25:22,915 --> 00:25:24,760
>> STEVEN: Wij houden 17 op de top, dus -

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

589
00:25:25,710 --> 00:25:27,040
>> STEVEN: - zet het neer.

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

591
00:25:27,530 --> 00:25:27,940
Het wordt steeds gemakkelijk.

592
00:25:27,940 --> 00:25:29,300
Ik ben niet van plan om u te helpen deze keer.

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

594
00:25:30,510 --> 00:25:31,720
>> STEVEN: Gedaan.

595
00:25:31,720 --> 00:25:34,870
Becoming een gum.

596
00:25:34,870 --> 00:25:37,340
Ik ben steeds een borstel.

597
00:25:37,340 --> 00:25:39,340
En dan zet ik 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
Dus nog een keer.

601
00:25:41,380 --> 00:25:44,280
Ik ga nu duwen
op de stapel 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
Je bent echt gevangen me off guard.

605
00:25:52,520 --> 00:25:53,703
>> DAVID Malan: Je deed het niet
zien aankomen?

606
00:25:53,703 --> 00:25:55,930
>> STEVEN: Ik heb niet zien aankomen.

607
00:25:55,930 --> 00:25:58,756
Konden we opnieuw initiële capaciteit?

608
00:25:58,756 --> 00:25:59,790
>> DAVID Malan: Dat is een goede vraag.

609
00:25:59,790 --> 00:26:02,360
Dus we hebben soort van geschilderde onszelf
in een hoek hier.

610
00:26:02,360 --> 00:26:06,740
Er is echt geen goed uit voor Steven
omdat we deze array hebben toegewezen

611
00:26:06,740 --> 00:26:09,130
statisch, zo te zeggen, binnen
van de gegevensstructuur.

612
00:26:09,130 --> 00:26:12,170
En we hebben in wezen hard gecodeerd
het van grootte van drie.

613
00:26:12,170 --> 00:26:14,170
Dus we kunnen niet echt herverdelen het.

614
00:26:14,170 --> 00:26:20,020
>> We konden als we gingen terug in, we
geherdefinieerd trays met een pointer die zijn

615
00:26:20,020 --> 00:26:22,300
we vervolgens gebruiken malloc om de hand geheugen om.

616
00:26:22,300 --> 00:26:25,050
Want als we het geheugen van
de hoop via malloc, we

617
00:26:25,050 --> 00:26:26,430
kan dan bevrijden.

618
00:26:26,430 --> 00:26:29,630
Maar voordat het vrijmaken, konden we
herverdelen van een groter stuk van het geheugen,

619
00:26:29,630 --> 00:26:31,330
bijwerken van de wijzer, enzovoort.

620
00:26:31,330 --> 00:26:33,500
Maar voor nu, dit is echt
het beste kunnen we doen.

621
00:26:33,500 --> 00:26:36,360
Push en pop zijn vermoedelijk gaan
te hebben om een ​​fout signaal.

622
00:26:36,360 --> 00:26:40,270
>> Dus bijvoorbeeld onze implementatie
van push een bool konden terugkeren die

623
00:26:40,270 --> 00:26:42,390
eerder teruggekeerd true, true, true.

624
00:26:42,390 --> 00:26:48,390
Maar de vierde keer, het gaat hebben
valse keren, bijvoorbeeld.

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

626
00:26:48,540 --> 00:26:49,540
Zeer goed gedaan.

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

628
00:26:50,060 --> 00:26:52,160
Je hebt vandaag verdiend uw stress bal.

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

630
00:26:53,110 --> 00:26:54,382
>> STEVEN: Dank je wel.

631
00:26:54,382 --> 00:26:55,680
>> DAVID Malan: Dank je wel.

632
00:26:55,680 --> 00:26:59,740
OK, dus dit lijkt niet veel
van een stap voorwaarts, toch?

633
00:26:59,740 --> 00:27:01,410
We beschreven deze datastructuur.

634
00:27:01,410 --> 00:27:02,320
Het is al overtuigend, toch?

635
00:27:02,320 --> 00:27:03,200
Besturingssystemen bevalt.

636
00:27:03,200 --> 00:27:06,360
Blijkbaar het web kan gebruik van maken,
en andere toepassingen nog.

637
00:27:06,360 --> 00:27:10,870
Maar wat een domme beperking dat we
terug naar soort van week twee limieten

638
00:27:10,870 --> 00:27:12,880
waar we hebben vaste afmetingen arrays.

639
00:27:12,880 --> 00:27:15,010
>> Dus er zijn inderdaad een paar
manieren waarop we kunnen dit oplossen.

640
00:27:15,010 --> 00:27:18,750
We konden dynamisch toewijzen van de array,
niet door harde codering als ik heb

641
00:27:18,750 --> 00:27:22,600
hier gedaan, maar in plaats daarvan opnieuw te verklaren
dit, gewoon om duidelijk te zijn, zoals

642
00:27:22,600 --> 00:27:23,830
zoiets als dit.

643
00:27:23,830 --> 00:27:29,040
Int * trays, niet beslissen
Op nog een capaciteit.

644
00:27:29,040 --> 00:27:35,460
Maar toen ik verklaar de stapel elders
in mijn code, kon ik dan bellen malloc,

645
00:27:35,460 --> 00:27:38,250
krijgen het adres van een brok van
geheugen, en ik kon toewijzen

646
00:27:38,250 --> 00:27:39,980
dat adres te laden.

647
00:27:39,980 --> 00:27:43,340
>> En dan, want het is gewoon een brok van
geheugen, kon ik blijven vierkant gebruiken

648
00:27:43,340 --> 00:27:45,450
haakjesnotering op de gebruikelijke manier.

649
00:27:45,450 --> 00:27:49,020
Want nogmaals, er is een soort van deze
functionele equivalent arrays en

650
00:27:49,020 --> 00:27:50,820
delen van het geheugen die komen
terug van malloc.

651
00:27:50,820 --> 00:27:53,090
We kunnen een behandelen als de andere
met behulp van pointers of

652
00:27:53,090 --> 00:27:54,440
square bracket notatie.

653
00:27:54,440 --> 00:27:55,660
Dus dat is een benadering.

654
00:27:55,660 --> 00:28:00,120
>> Maar hoe anders zouden we dit implementeren
dezelfde datastructuur, mogelijk?

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

656
00:28:00,280 --> 00:28:04,530
Ik heb het gevoel dat we gewoon dit opgelost
probleem als een week geleden.

657
00:28:04,530 --> 00:28:08,860
Wat was de oplossing voor dit probleem
dat Steven tegenkwam?

658
00:28:08,860 --> 00:28:10,370
Dus gelinkte lijsten, rechts.

659
00:28:10,370 --> 00:28:13,410
>> Als het probleem is dat we schilderen
onszelf in een hoek door het toewijzen

660
00:28:13,410 --> 00:28:17,580
vooraf te weinig geheugen we
dan hebben om een ​​of andere manier omgaan met, goed,

661
00:28:17,580 --> 00:28:19,880
waarom niet gewoon vermijden dat
helemaal af te geven?

662
00:28:19,880 --> 00:28:26,170
Waarom niet gewoon verklaren trays te zijn van een
pointer naar een knooppunt, ergo een gelinkte lijst,

663
00:28:26,170 --> 00:28:30,740
en dan gewoon nieuwe knooppunten toe te wijzen
elke keer dat Steven nodig is om een ​​fit

664
00:28:30,740 --> 00:28:32,400
nummer in de gegevensstructuur.

665
00:28:32,400 --> 00:28:34,200
>> Zodat het beeld zou moeten veranderen.

666
00:28:34,200 --> 00:28:38,220
Het gaat niet zo schoon en zo
simpel als gewoon een array van drie ints.

667
00:28:38,220 --> 00:28:42,970
Nu het gaat om een ​​pointer naar een te zijn
struct, en dat struct gaat

668
00:28:42,970 --> 00:28:44,830
hebben een int en een volgende pointer.

669
00:28:44,830 --> 00:28:47,670
Het zal leiden via die pointer
aan een andere struct

670
00:28:47,670 --> 00:28:48,600
nog zo'n struct.

671
00:28:48,600 --> 00:28:50,560
Zodat het beeld zou eigenlijk
een beetje Messier.

672
00:28:50,560 --> 00:28:52,950
En we zouden hebben pijlen koppelverkoop
alles samen.

673
00:28:52,950 --> 00:28:55,280
>> Maar dat is prima, rechts, want
we hebben gezien hoe dit te doen.

674
00:28:55,280 --> 00:28:58,180
En als je eenmaal wennen
uitvoering van iets als een gekoppelde

675
00:28:58,180 --> 00:29:01,450
lijst, die je moet doen als je
kiezen om een ​​hash table implementeren met

676
00:29:01,450 --> 00:29:05,120
aparte chaining voor p-set 6, kunt u
gebruiken als een bouwsteen, of een

677
00:29:05,120 --> 00:29:08,870
ingrediënt, of in Scratch spreken, een
procedure, iets dat je, je

678
00:29:08,870 --> 00:29:12,560
gemaakt uw eigen puzzelstukje
die u vervolgens kunt hergebruiken.

679
00:29:12,560 --> 00:29:17,090
Dus afwegingen, maar mogelijke oplossingen
dat we eigenlijk eerder gezien.

680
00:29:17,090 --> 00:29:20,560
>> Dus heel vaak, dit zie je elke
jaar of twee toen Apple releases

681
00:29:20,560 --> 00:29:23,060
iets nieuws, en alle gekke mensen
line-up buiten de Apple

682
00:29:23,060 --> 00:29:27,050
slaan om hun marginale kopen
upgraden van hardware.

683
00:29:27,050 --> 00:29:30,420
Ik zeg dit, het is OK, omdat
Ik ben een van die mensen.

684
00:29:30,420 --> 00:29:35,140
Dus wat voor soort data structuur
zou dit werkelijkheid te representeren?

685
00:29:35,140 --> 00:29:36,980
>> Nou, laten we noemen het een wachtrij, een lijn.

686
00:29:36,980 --> 00:29:40,270
So British zou het meestal een bel
wachtrij toch, dus het is een mooie naam.

687
00:29:40,270 --> 00:29:44,960
En de twee operaties die een wachtrij
zullen steunen we een enqueue bellen

688
00:29:44,960 --> 00:29:48,900
werking en een dequeue operatie,
die vergelijkbaar zijn

689
00:29:48,900 --> 00:29:50,120
geest te duwen en te knallen.

690
00:29:50,120 --> 00:29:54,060
Het is gewoon soort van verschillende in
conventie, wat we roepen deze.

691
00:29:54,060 --> 00:29:57,680
Maar om iets enqueue betekent om toe te voegen
of steek hem in de datastructuur.

692
00:29:57,680 --> 00:29:59,570
Om dequeue betekent om het te verwijderen.

693
00:29:59,570 --> 00:30:05,170
Maar terwijl een stapel was een LIFO data
structuur, een wachtrij is een eerste in,

694
00:30:05,170 --> 00:30:06,740
first out datastructuur.

695
00:30:06,740 --> 00:30:10,050
>> Als u bent de eerste persoon in de rij,
je zal de eerste persoon om te krijgen

696
00:30:10,050 --> 00:30:12,420
uit lijn en koop uw nieuwe apparaat.

697
00:30:12,420 --> 00:30:18,070
Stel je voor hoe overstuur deze mensen zouden zijn
als Apple gebruikt in plaats van een stapel voor

698
00:30:18,070 --> 00:30:21,250
bijvoorbeeld de uitvoering picking
up van uw nieuwe speeltje.

699
00:30:21,250 --> 00:30:24,310
Dus wachtrijen zinvol, zeker, en
kunnen we denken aan allerlei

700
00:30:24,310 --> 00:30:27,480
toepassingen, vermoedelijk voor wachtrijen
vooral als je wilt eerlijkheid.

701
00:30:27,480 --> 00:30:30,040
Dus hoe kunnen we de uitvoering van deze
als een datastructuur?

702
00:30:30,040 --> 00:30:33,680
>> Nou, ik stel voor dat we misschien
moet het op deze manier doen.

703
00:30:33,680 --> 00:30:35,225
Dus ik ga nu nummers.

704
00:30:35,225 --> 00:30:38,190
Dus zullen we het simpel en niet te houden
se spreken in termen van trays.

705
00:30:38,190 --> 00:30:40,220
Gewoon nummers die mensen van gekregen.

706
00:30:40,220 --> 00:30:43,760
Capaciteit gaat, nogmaals, bevestig de
totaal aantal mensen dat kan worden in

707
00:30:43,760 --> 00:30:46,900
deze lijn, als drie of
welke andere waarde.

708
00:30:46,900 --> 00:30:50,760
>> Maar ik stel voor dat ik nodig heb om bij te houden
niet alleen de grootte van de

709
00:30:50,760 --> 00:30:52,370
wachtrij, hoeveel dingen zijn in het.

710
00:30:52,370 --> 00:30:56,310
Dus grootte is de huidige omvang, capaciteit
is de maximale grootte.

711
00:30:56,310 --> 00:30:58,540
Gewoon weer, nomenclatuur
volgens afspraak.

712
00:30:58,540 --> 00:31:03,680
Waarom moet ik een extra int binnen
van een wachtrij bij te houden van wie er in te houden

713
00:31:03,680 --> 00:31:05,365
voorkant van de lijn?

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

715
00:31:07,930 --> 00:31:10,910
Waarom moet ik dat doen in dit geval?

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

717
00:31:14,750 --> 00:31:16,190
>> Nou ja, hoe is deze foto
gaat veranderen?

718
00:31:16,190 --> 00:31:19,280
Ik kan waarschijnlijk het meest hergebruiken
van deze foto.

719
00:31:19,280 --> 00:31:21,480
Laat me gaan en wist wat hier is.

720
00:31:21,480 --> 00:31:24,580
We zullen dit een iets te geven
andere naam hier.

721
00:31:24,580 --> 00:31:28,930
Laten we te ontdoen van de 17, laten we ontdoen
van de 9, laten zich te ontdoen van de 3.

722
00:31:28,930 --> 00:31:30,410
En voegen we een ander ding.

723
00:31:30,410 --> 00:31:34,710
Ik stel voor dat ik nodig heb om bij te houden
de voorkant van de lijst, dat is gewoon

724
00:31:34,710 --> 00:31:35,570
gaat een int als goed.

725
00:31:35,570 --> 00:31:36,550
En we gaan het simpel te houden.

726
00:31:36,550 --> 00:31:37,740
Geen gekoppelde lijst voor nu.

727
00:31:37,740 --> 00:31:40,900
>> We zullen toegeven dat we gaan
bump up tegen deze limiet.

728
00:31:40,900 --> 00:31:43,720
Maar wat wil ik zien
gebeuren deze keer?

729
00:31:43,720 --> 00:31:47,240
Dus stel ik ga je gang en de eerste
persoon komt in de rij, en

730
00:31:47,240 --> 00:31:48,560
het is het getal 9.

731
00:31:48,560 --> 00:31:49,680
We hebben stress ballen.

732
00:31:49,680 --> 00:31:51,330
Kan ik steel, zeg, twee of drie personen?

733
00:31:51,330 --> 00:31:52,690
Een, twee, drie?

734
00:31:52,690 --> 00:31:53,120
Kom maar naar boven.

735
00:31:53,120 --> 00:31:56,022
Recht van voren, omdat
we maken dit een snelle.

736
00:31:56,022 --> 00:31:59,415
>> Ieder van jullie is nu gaat worden
een fan jongen in de rij bij Apple.

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

738
00:32:03,970 --> 00:32:06,210
Je zal niet worden ontvangen van Apple-hardware
aan het einde van deze wel.

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

740
00:32:06,500 --> 00:32:09,430
Dus je nummer 9 bent, ben je
nummer 17, nummer 22.

741
00:32:09,430 --> 00:32:12,130
Dit zijn willekeurige getallen, zoals
student-id's of zo.

742
00:32:12,130 --> 00:32:14,550
En in slechts een moment, laten we beginnen
om te beginnen met het toevoegen van dingen.

743
00:32:14,550 --> 00:32:16,000
En ik zal het bestuur hier deze keer draaien.

744
00:32:16,000 --> 00:32:19,570
>> Dus in dit geval, heb ik geïnitialiseerd
de voorzijde zijn -

745
00:32:19,570 --> 00:32:22,380
Ik heb eigenlijk niet echt schelen wat de
voorkant is, omdat de grootte nul.

746
00:32:22,380 --> 00:32:24,480
Dus dit kan net zo goed gewoon
wel een vraagteken.

747
00:32:24,480 --> 00:32:26,170
Dit zijn allemaal vraagtekens.

748
00:32:26,170 --> 00:32:29,880
Dus nu gaan we beginnen om daadwerkelijk wat te zien
mensen in de rij bij de winkel.

749
00:32:29,880 --> 00:32:33,320
>> Dus als nummer 9, je bent de eerste
er op 5:00, ga je gang en line-up,

750
00:32:33,320 --> 00:32:34,210
of de avond ervoor.

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

752
00:32:34,580 --> 00:32:35,940
Dus nu 9 is hier.

753
00:32:35,940 --> 00:32:37,940
Dus 9 is aan de voorzijde van de lijst.

754
00:32:37,940 --> 00:32:41,440
Dus ik ga om verder te gaan en bij te werken
de grootte van deze stroom data

755
00:32:41,440 --> 00:32:44,740
structuur niet meer zijn 0,
maar om 1.

756
00:32:44,740 --> 00:32:47,630
Ik ga 9 zetten op de
voorzijde van de lijst.

757
00:32:47,630 --> 00:32:51,020
Laat me ga je gang en schakelen het scherm
dus kunnen we aan ons voorbij zien hier.

758
00:32:51,020 --> 00:32:53,220
>> En nu wat wil ik
te zetten op de voorkant?

759
00:32:53,220 --> 00:32:56,240
Ik ga om bij te houden dat de
vooraan in de wachtrij nu

760
00:32:56,240 --> 00:32:58,570
is op locatie 0.

761
00:32:58,570 --> 00:33:00,510
Want wat is de volgende gaat gebeuren?

762
00:33:00,510 --> 00:33:03,000
Nou, stel dat ik nu enqueue
17 ook.

763
00:33:03,000 --> 00:33:04,510
Dus hop in de rij daar.

764
00:33:04,510 --> 00:33:07,060
En nogmaals, het soort deur naar de
winkel gaat om hier te zijn.

765
00:33:07,060 --> 00:33:08,700
Zo nu heb ik toegevoegd 17.

766
00:33:08,700 --> 00:33:10,810
En hoewel deze jongens blokkeren
het scherm, dat is OK,

767
00:33:10,810 --> 00:33:12,300
omdat we het hier kunnen zien up.

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

769
00:33:12,910 --> 00:33:13,810
>> PUBLIEK: We kunnen bewegen -

770
00:33:13,810 --> 00:33:14,660
>> DAVID MALAN: Nee, dat is OK.

771
00:33:14,660 --> 00:33:16,000
Het is enorm daarboven.

772
00:33:16,000 --> 00:33:18,580
Dus 17 is nu de binnenkant van de wachtrij.

773
00:33:18,580 --> 00:33:21,332
Ik moet werken die
velden nu al?

774
00:33:21,332 --> 00:33:23,210
OK, zeker grootte.

775
00:33:23,210 --> 00:33:26,430
En hoe zit het voor?

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

777
00:33:27,040 --> 00:33:30,200
Voorzijde moet niet veranderen, omdat
in tegenstelling tot een stapel, we

778
00:33:30,200 --> 00:33:31,370
willen eerlijkheid te behouden.

779
00:33:31,370 --> 00:33:35,150
Dus als 9 kwam in de eerste, willen we 9
de eerste uit de lijn zijn

780
00:33:35,150 --> 00:33:36,420
en in de winkel.

781
00:33:36,420 --> 00:33:37,220
>> In feite, laten we zien dat.

782
00:33:37,220 --> 00:33:42,235
Voordat we 22 voegen, laten we
ga je gang en dequeue 9.

783
00:33:42,235 --> 00:33:42,970
Hoe heet je ook alweer?

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

785
00:33:43,680 --> 00:33:45,440
>> DAVID Malan: Jake gaat
nu worden gedequeued.

786
00:33:45,440 --> 00:33:48,050
Zo krijg je te lopen in de winkel.

787
00:33:48,050 --> 00:33:49,880
En alsof dat de winkel
is daar.

788
00:33:49,880 --> 00:33:51,970
Dus wat nu nodig heeft - dit-dit-zegt!

789
00:33:51,970 --> 00:33:53,400
Wat moet er nu gebeuren?

790
00:33:53,400 --> 00:33:54,490
Beslissing ontwerp.

791
00:33:54,490 --> 00:33:56,825
Dus geen slechte instinct, maar -
hoe heet je ook alweer?

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

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

794
00:33:57,500 --> 00:33:58,810
Dus wat deed David?

795
00:33:58,810 --> 00:34:02,590
Hij probeerde te sorteren van de gegevens vast
structuur en beweging van zijn locatie

796
00:34:02,590 --> 00:34:04,100
in de voormalige locatie Jake's.

797
00:34:04,100 --> 00:34:06,740
En dat is prima als we bereid zijn
om dat te accepteren als een

798
00:34:06,740 --> 00:34:08,199
implementatie detail.

799
00:34:08,199 --> 00:34:11,100
Maar laten we eerst het actualiseren van de gegevens
structuur voordat we dat doen.

800
00:34:11,100 --> 00:34:14,139
Want ik ben niet aardig vinden het idee van alle
de mensen verschuiving in deze lijn.

801
00:34:14,139 --> 00:34:17,360
>> Het is geen big deal als David doet het met
een stap, maar nogmaals, denk terug aan

802
00:34:17,360 --> 00:34:20,360
toen we acht vrijwilligers op het hebt gehad
podium en we hebben gedaan, zoals het inbrengen

803
00:34:20,360 --> 00:34:22,600
sorteren, waar we moesten beginnen
bewegen iedereen.

804
00:34:22,600 --> 00:34:23,790
Dat zette duur, toch?

805
00:34:23,790 --> 00:34:28,330
Dat maakt me ineenkrimpen over grote O
van n, grote O van n kwadraat weer.

806
00:34:28,330 --> 00:34:30,650
Het is het gevoel niet meer
een ideale uitkomst.

807
00:34:30,650 --> 00:34:32,080
>> Dus laten we gewoon dit updaten.

808
00:34:32,080 --> 00:34:35,120
Zodat de grootte van de wachtrij
niet meer 2.

809
00:34:35,120 --> 00:34:37,090
Het is nu gewoon 1.

810
00:34:37,090 --> 00:34:40,360
Maar ik kan nu iets updaten
Ik heb niet eerder updaten, de

811
00:34:40,360 --> 00:34:41,130
voorzijde van de lijst.

812
00:34:41,130 --> 00:34:45,420
Ik kon alleen maar zeggen, is dat de locatie 1?

813
00:34:45,420 --> 00:34:49,770
Dus nu hebben we vuilnis waarde hier,
garbage waarde hier, en David in de

814
00:34:49,770 --> 00:34:51,469
midden van deze rotzooi.

815
00:34:51,469 --> 00:34:54,980
Maar de gegevensstructuur
nog intact.

816
00:34:54,980 --> 00:34:58,540
>> En in feite, ik weet niet eens nodig om
veranderen voormalig nummer Jake's

817
00:34:58,540 --> 00:35:00,460
9, want who cares.

818
00:35:00,460 --> 00:35:04,470
Ik heb genoeg informatie nu in de
formaat dat ik weet dat er een persoon in

819
00:35:04,470 --> 00:35:05,030
deze wachtrij.

820
00:35:05,030 --> 00:35:08,340
En ik weet dat die persoon
is op locatie 1, niet 0.

821
00:35:08,340 --> 00:35:09,760
Ik ben niet te tellen.

822
00:35:09,760 --> 00:35:11,300
Dus 1 ook.

823
00:35:11,300 --> 00:35:13,410
Zodat de data structuur is nog steeds OK.

824
00:35:13,410 --> 00:35:14,330
>> Nou, wat gebeurt er nu?

825
00:35:14,330 --> 00:35:15,010
Let's enqueue -

826
00:35:15,010 --> 00:35:15,370
wat is je naam?

827
00:35:15,370 --> 00:35:16,160
>> PUBLIEK: Callen.

828
00:35:16,160 --> 00:35:16,580
>> DAVID Malan: Callen.

829
00:35:16,580 --> 00:35:20,770
Laten we enqueue een Callen, en
22 is nu in de wachtrij.

830
00:35:20,770 --> 00:35:22,300
Dus nu wat er moet hier veranderen?

831
00:35:22,300 --> 00:35:24,380
Voorzijde is niet van plan om
veranderen, natuurlijk.

832
00:35:24,380 --> 00:35:27,160
Grootte gaat veranderen om weer 2.

833
00:35:27,160 --> 00:35:31,590
En 22 eindigt hier, 9 is nog steeds aanwezig,
maar het is in feite een

834
00:35:31,590 --> 00:35:32,600
garbage waarde nu.

835
00:35:32,600 --> 00:35:35,910
Het is gewoon een overblijfsel van Jake verleden.

836
00:35:35,910 --> 00:35:39,200
>> Dus nu wat gebeurt er als
Ik dequeue David?

837
00:35:39,200 --> 00:35:41,560
Een laatste operatie, dequeue David.

838
00:35:41,560 --> 00:35:46,070
We kunnen verschuiven, maar ik stel voor laten we
doe zo weinig mogelijk werk.

839
00:35:46,070 --> 00:35:50,280
Nu is mijn datastructuur gaat
terug in grootte van 2 naar 1.

840
00:35:50,280 --> 00:35:53,730
Maar de voorkant van de wachtrij
Nu wordt 2.

841
00:35:53,730 --> 00:35:56,640
Ik hoef niet naar deze nummers te veranderen
gewoon nog niet, omdat ze

842
00:35:56,640 --> 00:35:58,230
gewoon huisvuil waarden.

843
00:35:58,230 --> 00:35:59,720
>> Maar nu wat gebeurt er?

844
00:35:59,720 --> 00:36:03,280
Stel dat ik enqueue mezelf, 26?

845
00:36:03,280 --> 00:36:05,890
Ik voel me alsof ik behoor dan hier.

846
00:36:05,890 --> 00:36:06,890
Dus ik word enqueued.

847
00:36:06,890 --> 00:36:08,760
Dus ik soort behoor hier.

848
00:36:08,760 --> 00:36:11,300
En ook al heb je niet helemaal
waardeer dit visueel op het podium,

849
00:36:11,300 --> 00:36:15,075
want we hebben genoeg ruimte, zou ik
hier niet staan, waarom?

850
00:36:15,075 --> 00:36:16,290
>> PUBLIEK: Je bent out of bounds.

851
00:36:16,290 --> 00:36:16,370
>> DAVID Malan: Right.

852
00:36:16,370 --> 00:36:16,940
Ik ben out of bounds.

853
00:36:16,940 --> 00:36:19,330
Ik heb geïndexeerd buiten de
grenzen van deze array.

854
00:36:19,330 --> 00:36:23,420
Ik moet echt in een van de
drie mogelijke locaties.

855
00:36:23,420 --> 00:36:25,150
Nu, waar is het meest natuurlijke om te gaan?

856
00:36:25,150 --> 00:36:27,760
Ik stel voor dat we leveraged
een week een truc.

857
00:36:27,760 --> 00:36:30,150
De mod operator, percentage.

858
00:36:30,150 --> 00:36:36,850
Want ik ben technisch staan ​​aan
locatie 3, maar ik doe 3 mod capaciteit,

859
00:36:36,850 --> 00:36:40,250
dus 3, een procent teken, 3 -

860
00:36:40,250 --> 00:36:40,970
capaciteit is 3.

861
00:36:40,970 --> 00:36:41,720
Wat is dat?

862
00:36:41,720 --> 00:36:43,700
Wat is de rest als
verdeel je 3 bij 3?

863
00:36:43,700 --> 00:36:44,070
0.

864
00:36:44,070 --> 00:36:48,140
>> Zodat ik zet waren Jake was,
dat is eigenlijk goed.

865
00:36:48,140 --> 00:36:50,370
Dus nu de uitvoering
van dit ding gaat

866
00:36:50,370 --> 00:36:51,250
wel een beetje hoofdpijn.

867
00:36:51,250 --> 00:36:53,740
Het is eigenlijk gewoon een regel
van hoofdpijn, van de code.

868
00:36:53,740 --> 00:36:56,580
Maar in ieder geval nu is er vuilnis
waarde hier, maar er is twee

869
00:36:56,580 --> 00:36:57,910
legitieme ints hier.

870
00:36:57,910 --> 00:37:04,160
En ik beweer dat nu hebben we gedaan
precies wat we nodig hebben om zo lang doen

871
00:37:04,160 --> 00:37:08,600
we veranderen wat Jake's
waarde moest worden 26.

872
00:37:08,600 --> 00:37:12,110
>> We hebben nu voldoende informatie nog
de integriteit

873
00:37:12,110 --> 00:37:13,060
deze gegevensstructuur.

874
00:37:13,060 --> 00:37:17,160
We zijn nog steeds soort van geluk toen we
willen vier of meer totale voegen

875
00:37:17,160 --> 00:37:20,740
elementen, maar ik kan in ieder geval mooi te maken
efficiënt gebruik van deze constante

876
00:37:20,740 --> 00:37:21,740
tijd, in feite.

877
00:37:21,740 --> 00:37:27,150
Ik heb geen zorgen te maken over het verschuiven
iedereen, zoals neiging Davids was.

878
00:37:27,150 --> 00:37:30,816
>> Heeft u vragen over stapels,
of deze wachtrij?

879
00:37:30,816 --> 00:37:32,184
>> PUBLIEK: Is de reden waarom
je nodig hebt grootte, zodat u weet

880
00:37:32,184 --> 00:37:34,010
waar om een ​​persoon te hebben?

881
00:37:34,010 --> 00:37:34,770
>> DAVID Malan: Precies.

882
00:37:34,770 --> 00:37:38,230
Ik moet de grootte van de matrix weten
want ik moet precies weten hoe

883
00:37:38,230 --> 00:37:41,940
veel van deze waarden zijn legitiem,
en zodat ik kan vinden waar te zetten

884
00:37:41,940 --> 00:37:42,800
de volgende persoon.

885
00:37:42,800 --> 00:37:43,300
Precies.

886
00:37:43,300 --> 00:37:44,580
De grootte is -

887
00:37:44,580 --> 00:37:46,360
eigenlijk, we hebben dit nog niet updaten.

888
00:37:46,360 --> 00:37:48,380
Ikzelf toegevoegd op 26.

889
00:37:48,380 --> 00:37:51,760
De grootte is nu niet 1 maar 2.

890
00:37:51,760 --> 00:37:57,780
Dus nu dit inderdaad helpt mij vinden de
van de lijst, die niet 0 is, niet

891
00:37:57,780 --> 00:37:59,250
1, maar 2.

892
00:37:59,250 --> 00:38:01,665
De voorzijde van de lijst
inderdaad nummer 22.

893
00:38:01,665 --> 00:38:05,120
Want hij kwam in de eerste, dus hij moet
in de winkel worden toegestaan ​​voor mij,

894
00:38:05,120 --> 00:38:08,780
hoewel visueel sta ik
dichter naar de winkel.

895
00:38:08,780 --> 00:38:09,220
>> Oke?

896
00:38:09,220 --> 00:38:12,410
Een applaus voor deze jongens
en we zullen ze laten uit daar.

897
00:38:12,410 --> 00:38:17,090
>> [Applaus]

898
00:38:17,090 --> 00:38:18,150
>> DAVID Malan: ik kon laten
u de lade te houden.

899
00:38:18,150 --> 00:38:20,760
We konden zien wat er gebeurt als
je wilt, maar misschien ook niet.

900
00:38:20,760 --> 00:38:21,590
Oke.

901
00:38:21,590 --> 00:38:25,380
Dus wat nu betekent dat ons verlaten?

902
00:38:25,380 --> 00:38:28,900
Nou, laat me voorstellen dat er een
enkele andere datastructuren we konden

903
00:38:28,900 --> 00:38:33,810
beginnen met het toevoegen aan onze tool kit die zal
eigenlijk heel, heel relevant als

904
00:38:33,810 --> 00:38:35,270
We duiken in web-dingen.

905
00:38:35,270 --> 00:38:38,150
Die opnieuw, heeft een soort verbinding
om bomen in de vorm van

906
00:38:38,150 --> 00:38:40,550
iets genaamd DOM, document
object model.

907
00:38:40,550 --> 00:38:42,370
Maar we zullen meer van zien
dat duurde niet lang.

908
00:38:42,370 --> 00:38:46,260
>> Laat me definitionally stel voor dat we
nu wat je zou kunnen kennen als noemen boom

909
00:38:46,260 --> 00:38:48,820
meer van een stamboom, waar u
wat voorouder op

910
00:38:48,820 --> 00:38:49,790
wortels van de boom.

911
00:38:49,790 --> 00:38:54,480
Een patriarchale of een matriarch op
de top van de boom.

912
00:38:54,480 --> 00:38:56,700
Zonder hun echtgenoot, in dit geval.

913
00:38:56,700 --> 00:39:00,940
Maar we hebben nu wat we noemen
kinderen, die knooppunten die hangen

914
00:39:00,940 --> 00:39:05,480
uit de linker kind of rechts kind,
pijlen zoals hier afgebeeld.

915
00:39:05,480 --> 00:39:10,490
>> Met andere woorden, in een boom datastructuur
in computer, een boom zero

916
00:39:10,490 --> 00:39:11,480
of meer knooppunten.

917
00:39:11,480 --> 00:39:13,500
Indien ten minste een knooppunt
dat heet de wortel.

918
00:39:13,500 --> 00:39:15,700
Het zijn de dingen die visueel
trekken we aan de top.

919
00:39:15,700 --> 00:39:20,280
En dat knooppunt, net als elk ander knooppunt, kan
hebben nul, een, of twee, of drie,

920
00:39:20,280 --> 00:39:23,600
of hoeveel kinderen de
gegevensstructuur ondersteunt.

921
00:39:23,600 --> 00:39:29,150
In dit geval, de wortel, de opslag
waarde een, twee kinderen, 2 en 3,

922
00:39:29,150 --> 00:39:33,020
zodat we over het algemeen noemen 2 links
kind en 3 het juiste kind.

923
00:39:33,020 --> 00:39:36,940
>> En toen we naar beneden naar 5, 6, en
7, 6 kan de middelste kind genoemd.

924
00:39:36,940 --> 00:39:38,940
Als je vier kinderen,
het wordt verwarrend.

925
00:39:38,940 --> 00:39:42,260
Dus we stoppen met dat soort
van snelkoppeling verbaal.

926
00:39:42,260 --> 00:39:44,580
Maar het is eigenlijk gewoon een stamboom.

927
00:39:44,580 --> 00:39:48,880
En de bladeren hier zijn de knooppunten die
hebben zelf geen kinderen.

928
00:39:48,880 --> 00:39:52,540
Ze hangen af ​​van de onderkant van de boom.

929
00:39:52,540 --> 00:39:56,940
>> Dus hoe kunnen we de uitvoering van een boom die
heeft slechts twee kinderen maximaal?

930
00:39:56,940 --> 00:39:58,410
We noemen het een binaire boom.

931
00:39:58,410 --> 00:40:00,960
Bi opnieuw betekenis twee, in dit
geval, net als met binaire.

932
00:40:00,960 --> 00:40:04,830
En dus het kan hebben nul, een,
of twee kinderen maximaal.

933
00:40:04,830 --> 00:40:08,650
>> Ik stel voor dat we de uitvoering van het knooppunt
voor die structuur met een int n,

934
00:40:08,650 --> 00:40:11,910
en dan twee wijzers, een zogenaamde
links, een zogenaamde rechts.

935
00:40:11,910 --> 00:40:14,830
Maar die zijn gewoon leuk
willekeurige conventies.

936
00:40:14,830 --> 00:40:18,170
En wat is er nu leuk, vooral als u
soort worstelde conceptueel met

937
00:40:18,170 --> 00:40:21,300
recursie, of dacht dat het niet was
echt een oplossing voor alles,

938
00:40:21,300 --> 00:40:23,120
vooral als je kon
opraken van het geheugen.

939
00:40:23,120 --> 00:40:26,600
Nu praten we over gegevens
structuren en algoritmen die het mogelijk maken

940
00:40:26,600 --> 00:40:31,030
ons te doorkruisen en te manipuleren,
blijkt dat recursie komt terug in

941
00:40:31,030 --> 00:40:34,240
een veel meer dwingende
zoniet mooie manier.

942
00:40:34,240 --> 00:40:38,670
>> Dus dit stel ik voor de implementatie
van een Search-functie.

943
00:40:38,670 --> 00:40:39,870
Gegeven twee ingangen -

944
00:40:39,870 --> 00:40:41,570
dus denk aan dit als een zwarte doos.

945
00:40:41,570 --> 00:40:46,560
Gegeven twee ingangen, n, int, en
pointer naar een boom, een pointer naar een

946
00:40:46,560 --> 00:40:50,020
knooppunt, of eigenlijk de wortel van een boom, ik
bewering dat deze functie kan terugkeren

947
00:40:50,020 --> 00:40:53,530
waar of onwaar, dat waarde n
is de binnenkant van deze boom.

948
00:40:53,530 --> 00:40:55,210
>> Wat is de binnenkant van deze zwarte doos?

949
00:40:55,210 --> 00:40:57,440
Nou ja, vier vestigingen.

950
00:40:57,440 --> 00:40:58,385
Het eerste net controleert.

951
00:40:58,385 --> 00:41:00,490
Als boom is null, net return false.

952
00:41:00,490 --> 00:41:04,580
Als er geen knooppunt, is er geen n,
er is geen nummer, maar return false.

953
00:41:04,580 --> 00:41:12,330
Indien wel, n, de waarde die u op zoek bent
voor, minder dan boom arrow n en

954
00:41:12,330 --> 00:41:15,180
alleen maar om duidelijk te zijn, wat betekent het als
Ik schrijf boom en vervolgens op de pijl

955
00:41:15,180 --> 00:41:18,150
notatie, n?

956
00:41:18,150 --> 00:41:18,690
Precies.

957
00:41:18,690 --> 00:41:21,970
Het betekent dat dereferentie
pointer genaamd boom.

958
00:41:21,970 --> 00:41:26,750
Ga daar heen, en dan krijg binnenkant van die
knooppunt en krijg zijn gebied genaamd n.

959
00:41:26,750 --> 00:41:30,810
En dan vergelijken met de werkelijke n dat was
overgegaan in Zoeken tegen.

960
00:41:30,810 --> 00:41:35,390
>> Als n kleiner is dan de waarde n
in de boom node zelf, goed,

961
00:41:35,390 --> 00:41:36,720
Wat betekent dat?

962
00:41:36,720 --> 00:41:40,690
Dat betekent dat er niets op het eerste gezicht.

963
00:41:40,690 --> 00:41:40,900
Rechts?

964
00:41:40,900 --> 00:41:45,560
Net als wanneer je een array van
waarden, zou u willen binaire toepassing

965
00:41:45,560 --> 00:41:48,290
zoeken als een vorm van verdeel
en heers.

966
00:41:48,290 --> 00:41:51,790
Maar wat aanname hebben we moeten ervoor
voor binaire zoeken om te werken op alle

967
00:41:51,790 --> 00:41:54,510
in het telefoonboek en
eerdere voorbeelden?

968
00:41:54,510 --> 00:41:55,530
>> Hoe te sorteren.

969
00:41:55,530 --> 00:41:59,490
Dus laten we het verfijnen van de definitie van de boom
hier niet om gewoon een boom, die kan worden

970
00:41:59,490 --> 00:42:00,880
hebben een aantal van de kinderen.

971
00:42:00,880 --> 00:42:04,700
Niet alleen een binaire boom, dat kan
hebben 0, 1, of 2 maximaal.

972
00:42:04,700 --> 00:42:09,700
Maar als een binaire zoekboom, of BST,
dat is gewoon een mooie manier om te zeggen een

973
00:42:09,700 --> 00:42:15,430
binaire boom zodat elk knooppunt
linker kind, indien aanwezig, is

974
00:42:15,430 --> 00:42:16,830
minder dan het knooppunt.

975
00:42:16,830 --> 00:42:20,170
En elke knoop heeft gelijk kind,
indien aanwezig, groter

976
00:42:20,170 --> 00:42:21,740
dan het knooppunt zelf.

977
00:42:21,740 --> 00:42:25,200
>> Dus met andere woorden, als je om te tekenen
de boom uit, alle getallen

978
00:42:25,200 --> 00:42:30,620
zorgvuldig afgewogen als deze, zodat als
heb je 55 als de wortel, kan 33 gaan

979
00:42:30,620 --> 00:42:33,090
links daarvan omdat hij minder dan 55.

980
00:42:33,090 --> 00:42:36,430
77 kan naar haar recht, omdat
is groter dan 55.

981
00:42:36,430 --> 00:42:40,750
Maar let nu op, dezelfde definitie,
het is een recursieve definitie verbaal,

982
00:42:40,750 --> 00:42:42,600
heeft te gelden voor 33.

983
00:42:42,600 --> 00:42:47,610
33's linker kind moet lager zijn dan het zijn,
en 33's rechts kind, 44, moet zijn

984
00:42:47,610 --> 00:42:48,580
groter dan.

985
00:42:48,580 --> 00:42:51,670
>> Dus dit is een binaire zoekboom, en
Ik stel voor, met behulp van een beetje

986
00:42:51,670 --> 00:42:53,910
recursie, kunnen we nu vinden n.

987
00:42:53,910 --> 00:42:59,160
Als n kleiner is dan de waarde die n
huidige knooppunt, ik ga om te gaan

988
00:42:59,160 --> 00:43:04,090
gang en trap, om zo te zeggen, en gewoon
terug wat het antwoord is van

989
00:43:04,090 --> 00:43:08,470
zoeken naar de n
linker kind boom.

990
00:43:08,470 --> 00:43:11,370
Let nog eens op, deze functie alleen
verwacht een knooppunt ster, een

991
00:43:11,370 --> 00:43:12,780
pointer naar een knooppunt.

992
00:43:12,780 --> 00:43:17,360
Dus zeker kan ik gewoon doen boom
pijl naar links, wat zal leiden

993
00:43:17,360 --> 00:43:18,400
me naar een ander knooppunt.

994
00:43:18,400 --> 00:43:19,480
Maar wat is dat knooppunt?

995
00:43:19,480 --> 00:43:22,820
>> Nou, volgens deze verklaring,
links is slechts een pointer, zodat alleen

996
00:43:22,820 --> 00:43:27,090
betekent dat ik overgaan naar de zoekfunctie
een andere aanwijzer, namelijk

997
00:43:27,090 --> 00:43:30,750
degene die vertegenwoordigt
boom mijn linker kind.

998
00:43:30,750 --> 00:43:36,040
Dus in dit geval de aanwijzer 33, indien
dit is onze steekproef ingang Ondertussen, als

999
00:43:36,040 --> 00:43:40,740
n is groter dan de waarde n aan de
huidige knooppunt in de boom, dan ben ik

1000
00:43:40,740 --> 00:43:43,370
ga je gang en de trap te gaan in de andere
richting en gewoon zeggen, ik doe niet

1001
00:43:43,370 --> 00:43:47,280
weten of deze waarde n in de structuur,
maar ik weet dat als het is, het is in mijn

1002
00:43:47,280 --> 00:43:49,090
rechts tak, zo te zeggen.

1003
00:43:49,090 --> 00:43:53,120
Dus laat me call recursief zoeken,
het passeren van een n weer, maar passeren in een

1004
00:43:53,120 --> 00:43:54,580
pointer naar mijn rechter kind.

1005
00:43:54,580 --> 00:44:00,020
>> Met andere woorden, als ik op dit moment op 55
en ik ben op zoek naar 99, ik weet dat 99

1006
00:44:00,020 --> 00:44:04,270
groter is dan 55, dus net als ik scheurde
het telefoonboek weken geleden en we

1007
00:44:04,270 --> 00:44:07,140
ging rechts, eveneens zijn wij
ga hier gaan.

1008
00:44:07,140 --> 00:44:11,960
En ik weet niet of het aan mijn rechter
kind, en het is niet, 77 is er, maar

1009
00:44:11,960 --> 00:44:13,210
Ik weet dat het in die richting.

1010
00:44:13,210 --> 00:44:18,770
Dus bel ik zoek op mijn rechter kind,
77, en laat zoeken figuur uit

1011
00:44:18,770 --> 00:44:24,950
daar als 99 in deze arbitraire
Zo is er eigenlijk.

1012
00:44:24,950 --> 00:44:26,900
>> Anders, wat is het laatste geval is?

1013
00:44:26,900 --> 00:44:28,620
Als boom is null is een geval.

1014
00:44:28,620 --> 00:44:31,890
Als n kleiner is dan het huidige knooppunt
waarde ander geval.

1015
00:44:31,890 --> 00:44:35,120
Als n groter is dan de huidige
node waarde is een derde geval.

1016
00:44:35,120 --> 00:44:38,250
Wat is de vierde en laatste geval?

1017
00:44:38,250 --> 00:44:39,480
Ik denk dat we uit gevallen, toch?

1018
00:44:39,480 --> 00:44:44,690
Het moet dat n in de
huidige knooppunt dat ik op.

1019
00:44:44,690 --> 00:44:49,640
>> Dus als ik ben op zoek naar 55 op dit punt
in het verhaal, die tak van de

1020
00:44:49,640 --> 00:44:51,780
boom zou return true.

1021
00:44:51,780 --> 00:44:55,380
Dus wat is interessant hier is dat we
eigenlijk, in tegenstelling tot de weken voorbij, we soort

1022
00:44:55,380 --> 00:44:56,740
van twee base gevallen.

1023
00:44:56,740 --> 00:44:58,300
En ze hoeven niet te
worden alle aan de top.

1024
00:44:58,300 --> 00:45:01,390
De top is een referentiemodel want als de
boom is null, er is niets te doen.

1025
00:45:01,390 --> 00:45:03,410
Net terug van een hard gecodeerde
waarde false.

1026
00:45:03,410 --> 00:45:07,400
>> De onderste tak is een soort van de
standaard, waarbij als wij hebben gecontroleerd

1027
00:45:07,400 --> 00:45:11,550
null, hebben we gekeken of het zou moeten zijn
vertrokken, maar het moet niet, we hebben

1028
00:45:11,550 --> 00:45:14,640
gecontroleerd of het recht mag, maar
moet niet duidelijk het moet

1029
00:45:14,640 --> 00:45:15,870
precies waar we zijn.

1030
00:45:15,870 --> 00:45:16,780
Dat is een base case.

1031
00:45:16,780 --> 00:45:19,920
Dus er is twee recursieve gevallen
daar ingeklemd in het midden.

1032
00:45:19,920 --> 00:45:21,630
Maar ik zou hebben geschreven
dit in willekeurige volgorde.

1033
00:45:21,630 --> 00:45:24,520
Ik dacht dat het soort voelde natuurlijke
eerst controleren voor een mogelijke fout,

1034
00:45:24,520 --> 00:45:28,340
controleer dan linksaf, check dan rechts, dan
gaan ervan uit dat je op het knooppunt

1035
00:45:28,340 --> 00:45:30,630
je bent eigenlijk op zoek naar.

1036
00:45:30,630 --> 00:45:36,240
>> Dus waarom zou dit nuttig zijn?

1037
00:45:36,240 --> 00:45:37,910
Zo blijkt het -

1038
00:45:37,910 --> 00:45:42,110
en laat me springen naar een teaser
hier is dat in het web.

1039
00:45:42,110 --> 00:45:44,920
We gaan aan de slag met geen
programmeertaal op het eerste, maar een

1040
00:45:44,920 --> 00:45:46,030
opmaaktaal.

1041
00:45:46,030 --> 00:45:48,740
Een opmaaktaal zijnde een die
in dezelfde geest te programmeren

1042
00:45:48,740 --> 00:45:51,715
taal, maar het niet geven u de
vermogen om jezelf te uiten logisch.

1043
00:45:51,715 --> 00:45:55,070
Het geeft alleen de mogelijkheid om
structureel te uiten jezelf.

1044
00:45:55,070 --> 00:45:57,960
>> Waar wil je iets zetten
op de pagina, de webpagina?

1045
00:45:57,960 --> 00:45:59,200
Welke kleur wil je het maken?

1046
00:45:59,200 --> 00:46:00,950
Welke lettergrootte wil je het maken?

1047
00:46:00,950 --> 00:46:02,970
Welke woorden heb je eigenlijk
wil op de webpagina?

1048
00:46:02,970 --> 00:46:04,060
Dus dat is een opmaaktaal.

1049
00:46:04,060 --> 00:46:07,690
Maar dan zullen we heel snel invoeren
JavaScript, dat is een volwaardige

1050
00:46:07,690 --> 00:46:08,560
programmeertaal.

1051
00:46:08,560 --> 00:46:12,530
Zeer vergelijkbaar syntactisch in uiterlijk
naar C, maar het zal wat hebben

1052
00:46:12,530 --> 00:46:15,200
nice, krachtiger,
gebruiksvriendelijke functies.

1053
00:46:15,200 --> 00:46:18,050
>> En een van de frustraties bij deze
punt in het semester is dat we zullen

1054
00:46:18,050 --> 00:46:22,065
snel te implementeren speller in veel minder
coderegels gebruik van andere talen

1055
00:46:22,065 --> 00:46:25,580
dan C zelf maakt, maar voor de rede's
we zullen snel begrijpen.

1056
00:46:25,580 --> 00:46:27,750
Dit zal de eerste dergelijke webpagina.

1057
00:46:27,750 --> 00:46:30,120
Het zal volledig underwhelming,
de eerste die we maken.

1058
00:46:30,120 --> 00:46:31,400
Het wil alleen maar zeggen, hello wereld.

1059
00:46:31,400 --> 00:46:34,010
Maar als je nog nooit hebt gezien
eerder is HTML,

1060
00:46:34,010 --> 00:46:35,670
HyperText Markup Language.

1061
00:46:35,670 --> 00:46:39,310
>> Als je naar een bepaalde menu-optie in
vrijwel elke browser, op een webpagina op

1062
00:46:39,310 --> 00:46:43,160
het internet, kunt u de HTML-
dat sommige mensen schreven aan

1063
00:46:43,160 --> 00:46:44,400
creëren die webpagina.

1064
00:46:44,400 --> 00:46:47,850
En het waarschijnlijk niet uitzien als
korte of zo netjes als dit.

1065
00:46:47,850 --> 00:46:51,400
Maar het zal het patroon van deze te volgen
geopend beugels en schuine strepen en

1066
00:46:51,400 --> 00:46:53,660
letters en cijfers mogelijk.

1067
00:46:53,660 --> 00:46:56,770
>> Ik dacht, ik geef je een teaser
van wat je zult kunnen doen

1068
00:46:56,770 --> 00:46:57,950
na het nemen van CS50.

1069
00:46:57,950 --> 00:47:02,620
Laat me gaan naar cs.harvard.edu / rob,
onze eigen Rob Bowden's homepage.

1070
00:47:02,620 --> 00:47:06,080
Hij maakte deze voor ons.

1071
00:47:06,080 --> 00:47:07,490
Dus je zult snel in staat om dat te doen.

1072
00:47:07,490 --> 00:47:10,660
En ook, wat je gehoord
vanmorgen -

1073
00:47:10,660 --> 00:47:12,480
wat je hoorde vanmorgen -

1074
00:47:12,480 --> 00:47:13,780
>> [HAMSTER DANCE MUSIC]

1075
00:47:13,780 --> 00:47:15,702
>> - U zult in staat zijn om dit te maken.

1076
00:47:15,702 --> 00:47:16,790
Dat wacht ons op woensdag.

1077
00:47:16,790 --> 00:47:17,791
Wij zullen u dan zien.

1078
00:47:17,791 --> 00:47:22,950
>> [HAMSTER DANCE MUSIC]

1079
00:47:22,950 --> 00:47:24,300
DAVID Malan: Bij de volgende CS50 -

1080
00:47:24,300 --> 00:47:31,670