1
00:00:00,000 --> 00:00:00,500

2
00:00:00,500 --> 00:00:05,120
[Speel van musiek]

3
00:00:05,120 --> 00:00:12,026

4
00:00:12,026 --> 00:00:12,900
Spreker 1: Alle reg.

5
00:00:12,900 --> 00:00:14,600
Almal terug na afdeling verwelkom.

6
00:00:14,600 --> 00:00:18,660
Ek hoop julle almal is suksesvol
verhaal van jou quiz

7
00:00:18,660 --> 00:00:19,510
van verlede week.

8
00:00:19,510 --> 00:00:22,564
Ek weet dit is 'n bietjie mal by tye.

9
00:00:22,564 --> 00:00:25,230
Soos ek voor sê, as jy
binne die standaard afwyking,

10
00:00:25,230 --> 00:00:28,188
nie regtig nie bekommerd daaroor, veral
vir 'n minder gemaklike afdeling.

11
00:00:28,188 --> 00:00:30,230
Dit is oor waar jy moet wees.

12
00:00:30,230 --> 00:00:32,850
>> As jy het 'n groot, dan awesome.

13
00:00:32,850 --> 00:00:33,650
Kudos aan jou.

14
00:00:33,650 --> 00:00:36,149
En as jy voel jy moet
'n bietjie meer hulp, asseblief

15
00:00:36,149 --> 00:00:38,140
voel vry om te bereik
uit enige van die TFS.

16
00:00:38,140 --> 00:00:40,030
Ons is almal hier om te help.

17
00:00:40,030 --> 00:00:40,960
>> Dit is hoekom ons leer.

18
00:00:40,960 --> 00:00:44,550
Dit is hoekom ek hier is elke Maandag vir jou
ouens en by kantoorure op Donderdae.

19
00:00:44,550 --> 00:00:48,130
So voel asseblief vry om my te laat weet
As jy bekommerd is oor enigiets

20
00:00:48,130 --> 00:00:52,450
of as daar iets op die toets
dat jy regtig wil, aan te spreek.

21
00:00:52,450 --> 00:00:56,940
>> So het die agenda vir vandag
alles oor data strukture.

22
00:00:56,940 --> 00:01:01,520
Sommige van hierdie is net gaan om net te wees
te kry wat jy vertroud met hierdie.

23
00:01:01,520 --> 00:01:04,870
Jy mag nie ooit implementeer
hulle in hierdie klas.

24
00:01:04,870 --> 00:01:08,690
Sommige van hulle sal jy,
soos vir jou speller pset.

25
00:01:08,690 --> 00:01:11,380
>> Jy sal jou keuse hê
tussen hash tabelle en drieë gedruk.

26
00:01:11,380 --> 00:01:13,680
So ons sal beslis gaan word oor diegene.

27
00:01:13,680 --> 00:01:18,690
Dit gaan beslis meer van aard te wees
van 'n hoë vlak artikel vandag, al is,

28
00:01:18,690 --> 00:01:22,630
want daar is baie van hulle, en as
ons het in die implementering besonderhede

29
00:01:22,630 --> 00:01:26,490
op al hierdie, sou ons nie
selfs deur geskakelde lyste

30
00:01:26,490 --> 00:01:28,520
en miskien 'n bietjie van 'n gemors tafels.

31
00:01:28,520 --> 00:01:31,200
>> So met my dra.

32
00:01:31,200 --> 00:01:33,530
Ons is nie van plan om te doen
soveel kodering hierdie tyd.

33
00:01:33,530 --> 00:01:36,870
As jy enige vrae het oor dit
of jy wil sien dit geïmplementeer

34
00:01:36,870 --> 00:01:39,260
of probeer om dit vir jouself,
Ek beslis aanbeveel

35
00:01:39,260 --> 00:01:44,250
gaan study.cs50.net, wat
het voorbeelde van al hierdie.

36
00:01:44,250 --> 00:01:46,400
Dit sal my kragpunte het
met die notas wat ons

37
00:01:46,400 --> 00:01:50,860
geneig is om te word, sowel as 'n paar programme
oefeninge, veral vir dinge

38
00:01:50,860 --> 00:01:55,250
soos gekoppel lyste en binêre
bome stapels en leidrade.

39
00:01:55,250 --> 00:01:59,590
So bietjie meer hoë vlak, wat
kan lekker vir julle wees.

40
00:01:59,590 --> 00:02:01,320
>> So met dit, sal ons begin.

41
00:02:01,320 --> 00:02:03,060
En ook, yes-- vasvrae.

42
00:02:03,060 --> 00:02:06,550
Ek dink die meeste van julle wat in
my artikel jou vasvrae,

43
00:02:06,550 --> 00:02:12,060
maar iemand kom of ander rede
doen nie, hulle is reg hier in die voorkant.

44
00:02:12,060 --> 00:02:12,740
>> So gekoppel lyste.

45
00:02:12,740 --> 00:02:15,650
Ek weet van hierdie soort gaan
om terug voor jou quiz.

46
00:02:15,650 --> 00:02:17,940
Dit was die week voor
dat ons geleer het oor hierdie.

47
00:02:17,940 --> 00:02:21,040
Maar in hierdie geval, sal ons net
gaan 'n bietjie meer in diepte.

48
00:02:21,040 --> 00:02:25,900
>> So hoekom kan ons kies 'n
gekoppel lys oor 'n skikking?

49
00:02:25,900 --> 00:02:27,130
Wat onderskei hulle?

50
00:02:27,130 --> 00:02:27,630
Ja?

51
00:02:27,630 --> 00:02:30,464
>> Publiek: Jy kan uit te brei 'n gekoppelde
lys teenoor 'n skikking se vaste grootte.

52
00:02:30,464 --> 00:02:31,171
Spreker 1: Right.

53
00:02:31,171 --> 00:02:33,970
'N skikking het vaste grootte, terwyl 'n
gekoppel lys het 'n veranderlike grootte.

54
00:02:33,970 --> 00:02:36,970
So, as ons nie weet hoe
veel ons wil op te slaan,

55
00:02:36,970 --> 00:02:39,880
'n geskakelde lys gee ons 'n groot
manier om dit te doen, want ons kan net

56
00:02:39,880 --> 00:02:43,730
voeg op 'n ander knoop en voeg op
'n ander knoop en voeg op 'n ander knoop.

57
00:02:43,730 --> 00:02:45,750
Maar wat kan 'n trade-off wees?

58
00:02:45,750 --> 00:02:49,521
Is daar iemand onthou die trade-off
tussen skikkings en geskakelde lyste?

59
00:02:49,521 --> 00:02:50,020
Mmhmm?

60
00:02:50,020 --> 00:02:51,460
>> Publiek: Jy moet
gaan deur al die pad

61
00:02:51,460 --> 00:02:53,738
deur die geskakelde lys
vind 'n element in 'n lys.

62
00:02:53,738 --> 00:02:55,570
In 'n skikking, kan jy
vind net 'n element.

63
00:02:55,570 --> 00:02:56,278
>> Spreker 1: Right.

64
00:02:56,278 --> 00:02:57,120
So met arrays--

65
00:02:57,120 --> 00:02:58,500
>> Publiek: [onhoorbaar].

66
00:02:58,500 --> 00:03:01,090
>> Spreker 1: Met skikkings, ons het
wat genoem ewekansige toegang.

67
00:03:01,090 --> 00:03:04,820
Beteken dat as ons wil hê wat
ooit die vyfde punt van 'n lys

68
00:03:04,820 --> 00:03:07,230
of die vyfde punt van ons
skikking, kan ons net gryp dit.

69
00:03:07,230 --> 00:03:10,440
As dit is 'n geskakelde lys, ons het
te Itereer deur, reg?

70
00:03:10,440 --> 00:03:14,020
So toegang tot 'n element in
'n skikking is konstante tyd,

71
00:03:14,020 --> 00:03:19,530
terwyl met 'n geskakelde lys sou dit
waarskynlik lineêre tyd, want miskien

72
00:03:19,530 --> 00:03:21,370
ons element is al die pad aan die einde.

73
00:03:21,370 --> 00:03:23,446
Ons het om te soek deur alles.

74
00:03:23,446 --> 00:03:25,320
So met al die data
strukture wat ons gaan

75
00:03:25,320 --> 00:03:29,330
word spandeer 'n bietjie meer tyd op,
Wat is die plus punte en negatiewe.

76
00:03:29,330 --> 00:03:31,480
Wanneer sal ons wil
Gebruik een oor die ander?

77
00:03:31,480 --> 00:03:34,970
En dit is soort van die
groter ding om weg te neem.

78
00:03:34,970 --> 00:03:40,140
>> Dus het ons hier die
definisie van 'n knoop.

79
00:03:40,140 --> 00:03:43,040
Dit is soos 'n element in
ons geskakelde lys, reg?

80
00:03:43,040 --> 00:03:46,180
So ons is almal vertroud
met ons typedef gelas,

81
00:03:46,180 --> 00:03:47,980
wat het ons oor in hersiening laaste keer.

82
00:03:47,980 --> 00:03:53,180
Dit was basies net die skep van
ander data tipe wat ons kan gebruik.

83
00:03:53,180 --> 00:03:57,930
>> En in hierdie geval, dit is 'n paar node
wat sal 'n heelgetal in hou.

84
00:03:57,930 --> 00:04:00,210
En dan wat is die tweede deel hier?

85
00:04:00,210 --> 00:04:03,192

86
00:04:03,192 --> 00:04:05,677
Iemand?

87
00:04:05,677 --> 00:04:06,680
>> Publiek: [onhoorbaar].

88
00:04:06,680 --> 00:04:07,020
>> Spreker 1: Ja.

89
00:04:07,020 --> 00:04:08,400
Dit is 'n verwysing na die volgende knoop.

90
00:04:08,400 --> 00:04:12,610
So dit moet eintlik up wees hier.

91
00:04:12,610 --> 00:04:18,790
Dit is 'n aanduiding van die tipe
knoop na die volgende ding.

92
00:04:18,790 --> 00:04:22,410
En dit is wat hulle
sluit ons node.

93
00:04:22,410 --> 00:04:24,060
Cool.

94
00:04:24,060 --> 00:04:29,390
>> Alle reg, so met 'n soektog, soos ons was
net sê voor die hand, as jy

95
00:04:29,390 --> 00:04:31,840
gaan soek deur,
jy moet eintlik Itereer

96
00:04:31,840 --> 00:04:33,660
deur jou geskakelde lys.

97
00:04:33,660 --> 00:04:38,530
So as ons kyk vir die aantal
9, sal ons begin by ons kop

98
00:04:38,530 --> 00:04:41,520
en dat wys ons aan die begin
van ons geskakelde lys, reg?

99
00:04:41,520 --> 00:04:44,600
En ons sê, OK, doen dit
knoop bevat die nommer 9?

100
00:04:44,600 --> 00:04:45,690
Geen?

101
00:04:45,690 --> 00:04:47,500
>> Alle reg, gaan na die volgende een.

102
00:04:47,500 --> 00:04:48,312
Dit volg.

103
00:04:48,312 --> 00:04:49,520
Bevat dit die nommer 9?

104
00:04:49,520 --> 00:04:50,570
No.

105
00:04:50,570 --> 00:04:51,550
Volg die volgende een.

106
00:04:51,550 --> 00:04:55,490
>> So ons moet eintlik Itereer
deur ons geskakelde lys.

107
00:04:55,490 --> 00:05:00,070
Ons kan nie net gaan direk na die plek waar 9 is.

108
00:05:00,070 --> 00:05:05,860
En as julle eintlik wil
sien 'n paar pseudo-kode daar.

109
00:05:05,860 --> 00:05:10,420
Ons het 'n paar soek funksie hier
wat neem in-- wat dit neem om in?

110
00:05:10,420 --> 00:05:13,110

111
00:05:13,110 --> 00:05:14,320
Wat dink jy?

112
00:05:14,320 --> 00:05:15,960
So maklik.

113
00:05:15,960 --> 00:05:17,784
Wat is dit?

114
00:05:17,784 --> 00:05:18,700
Publiek: [onhoorbaar].

115
00:05:18,700 --> 00:05:20,366
Spreker 1: Die getal wat ons soek.

116
00:05:20,366 --> 00:05:20,980
Reg?

117
00:05:20,980 --> 00:05:22,875
En wat sou dit ooreen?

118
00:05:22,875 --> 00:05:25,020
Dit is 'n verwysing na?

119
00:05:25,020 --> 00:05:26,000
>> GEHOOR: 'n knoop.

120
00:05:26,000 --> 00:05:28,980
>> Spreker 1: 'n knoop aan die lys
dat ons is op soek na, reg?

121
00:05:28,980 --> 00:05:33,700
So ons het 'n paar knope is wyser hier.

122
00:05:33,700 --> 00:05:37,240
Dit is 'n punt wat gaan
eintlik Itereer deur ons lys.

123
00:05:37,240 --> 00:05:39,630
Ons stel dit gelyk aan die lys
want dit is net

124
00:05:39,630 --> 00:05:44,380
om dit te stel gelyk aan die
begin van ons geskakelde lys.

125
00:05:44,380 --> 00:05:50,660
>> En terwyl dit is nie NULL, terwyl
het ons nog dinge in ons lys,

126
00:05:50,660 --> 00:05:55,580
kyk om te sien of dit knoop het
die getal wat ons soek.

127
00:05:55,580 --> 00:05:57,740
Terugkeer waar.

128
00:05:57,740 --> 00:06:01,070
Andersins, werk dit, reg?

129
00:06:01,070 --> 00:06:04,870
>> As dit is NULL, ons verlaat ons
while lus en stuur vals

130
00:06:04,870 --> 00:06:08,340
want dit beteken dat ons nog nie gevind nie.

131
00:06:08,340 --> 00:06:11,048
Nie almal kry hoe dit werk?

132
00:06:11,048 --> 00:06:11,548
OK.

133
00:06:11,548 --> 00:06:14,940

134
00:06:14,940 --> 00:06:20,260
>> So met plasing, jy
het drie verskillende maniere.

135
00:06:20,260 --> 00:06:25,250
Jy kan prefix, kan jy voeg
en jy kan voeg in verskillende soorte.

136
00:06:25,250 --> 00:06:28,215
In hierdie geval, ons is
gaan 'n plaas jou te doen.

137
00:06:28,215 --> 00:06:33,380
Is daar iemand wat weet hoe om die
drie gevalle kan verskil?

138
00:06:33,380 --> 00:06:36,920
>> So plaas jou beteken dat jy
dit aan die voorkant van jou lys.

139
00:06:36,920 --> 00:06:39,770
So dit sou beteken dat maak nie saak
wat jou node is, maak nie saak

140
00:06:39,770 --> 00:06:43,160
wat die waarde is, gaan jy
om dit te sit hier voor, OK?

141
00:06:43,160 --> 00:06:45,160
Dit gaan die eerste wees
element in jou lys.

142
00:06:45,160 --> 00:06:49,510
>> As jy dit voeg, gaan dit
om te gaan na die agterkant van jou lys.

143
00:06:49,510 --> 00:06:54,010
En voeg in verskillende soorte beteken dat jy
gaan eintlik sit in die plek

144
00:06:54,010 --> 00:06:57,700
waar dit hou jou geskakelde lys gesorteer.

145
00:06:57,700 --> 00:07:00,810
Weereens, hoe jy gebruik
diegene en wanneer jy gebruik

146
00:07:00,810 --> 00:07:02,530
sal hulle wissel, afhangende van jou saak.

147
00:07:02,530 --> 00:07:05,834

148
00:07:05,834 --> 00:07:07,750
As dit nie nodig het om te
word gesorteer, plaas geneig

149
00:07:07,750 --> 00:07:10,460
te wees wat die meeste mense
gebruik omdat jy dit nie doen nie

150
00:07:10,460 --> 00:07:15,680
het om te gaan deur die hele lys
die einde dit toe te voeg aan te vind, reg?

151
00:07:15,680 --> 00:07:17,720
Jy kan net plak dit reg.

152
00:07:17,720 --> 00:07:21,930
>> So sal ons gaan deur 'n
voeg 1 nou.

153
00:07:21,930 --> 00:07:26,360
So een ding wat ek gaan
raai op hierdie pset

154
00:07:26,360 --> 00:07:29,820
is om dinge te trek uit, soos altyd.

155
00:07:29,820 --> 00:07:35,130
Dit is baie belangrik dat jy werk
jou wenke in die korrekte volgorde

156
00:07:35,130 --> 00:07:38,620
want as jy hulle werk
effens buite orde,

157
00:07:38,620 --> 00:07:42,210
jy gaan om te eindig
verloor dele van jou lys.

158
00:07:42,210 --> 00:07:49,680
>> So byvoorbeeld, in hierdie geval, ons is
vertel die hoof net punt 1.

159
00:07:49,680 --> 00:07:56,070
As ons net dit doen
sonder om hierdie 1,

160
00:07:56,070 --> 00:07:58,570
Ons het geen idee wat
1 moet nou

161
00:07:58,570 --> 00:08:02,490
omdat ons verloor het wat
die hoof verwys na.

162
00:08:02,490 --> 00:08:05,530
So een ding om te onthou
Wanneer jy 'n plaas jou doen

163
00:08:05,530 --> 00:08:09,630
is om te red wat die
hoof punte na die eerste,

164
00:08:09,630 --> 00:08:15,210
dan toewys dit, en dan werk
wat jou nuwe node behoort te wys.

165
00:08:15,210 --> 00:08:20,870

166
00:08:20,870 --> 00:08:22,560
In hierdie geval, dit is een manier om dit te doen nie.

167
00:08:22,560 --> 00:08:25,440
>> So as ons gedoen het dit op hierdie manier
waar ons net oorgeplaas kop,

168
00:08:25,440 --> 00:08:30,320
Ons het basies ons verloor
hele lys, reg?

169
00:08:30,320 --> 00:08:38,000
Een manier om dit te doen, is 1 punt te hê
volgende, en dan het die hoof punt 1.

170
00:08:38,000 --> 00:08:42,650
Of jy kan doen soort van soos die
tydelike stoor, wat ek het gepraat oor.

171
00:08:42,650 --> 00:08:45,670
>> Maar gehou indiensneming jou
wysers in die korrekte volgorde

172
00:08:45,670 --> 00:08:48,750
gaan baie, baie wees
belangrik vir hierdie pset.

173
00:08:48,750 --> 00:08:53,140
Andersins, jy gaan 'n gemors te hê
tafel of 'n drie wat net gaan wees

174
00:08:53,140 --> 00:08:56,014
slegs 'n deel van die woorde wat jy
wil en dan you're-- Mmhmm?

175
00:08:56,014 --> 00:08:58,930
Publiek: Wat was die tydelike
stoor ding wat jy praat?

176
00:08:58,930 --> 00:09:00,305
Spreker 1: die tydelike stoor.

177
00:09:00,305 --> 00:09:02,760
So basies 'n ander
manier waarop jy dit kan doen

178
00:09:02,760 --> 00:09:07,650
is slaan die hoof van iets, soos
stoor dit die tydelike veranderlike.

179
00:09:07,650 --> 00:09:11,250
Toewys om dit te 1 en
dan werk 1 te wys

180
00:09:11,250 --> 00:09:13,830
aan alles wat kop gebruik om aan te dui.

181
00:09:13,830 --> 00:09:16,920
Hierdie manier is natuurlik
meer elegante, want jy

182
00:09:16,920 --> 00:09:20,770
nie 'n tydelike waarde het nie, maar
net die aanbied van 'n ander manier om dit te doen nie.

183
00:09:20,770 --> 00:09:23,999

184
00:09:23,999 --> 00:09:25,790
En ons werklik doen het
sommige kode vir hierdie.

185
00:09:25,790 --> 00:09:28,080
So vir gekoppelde lys ons
eintlik 'n paar kode.

186
00:09:28,080 --> 00:09:31,930
So voeg hier, is dit en tik.

187
00:09:31,930 --> 00:09:34,290
So dit gaan dit op die kop.

188
00:09:34,290 --> 00:09:38,820
>> So die eerste ding wat jy nodig het om te
skep jou nuwe node, natuurlik,

189
00:09:38,820 --> 00:09:40,790
en kyk vir NULL.

190
00:09:40,790 --> 00:09:43,250
Altyd goed.

191
00:09:43,250 --> 00:09:47,840
En dan moet jy die waardes te wys.

192
00:09:47,840 --> 00:09:51,260
Wanneer jy 'n nuwe knoop, jy
Ek weet nie wat dit is wys om die volgende,

193
00:09:51,260 --> 00:09:54,560
sodat jy wil om dit te inisialiseer te null.

194
00:09:54,560 --> 00:09:58,760
As dit nie die einde wys na iets
anders, word dit oorgeplaas en dit is goed.

195
00:09:58,760 --> 00:10:00,740
As dit is die eerste ding wat
in die lys is, is dit nodig

196
00:10:00,740 --> 00:10:04,270
om aan te dui omdat null
dit is die einde van die lys.

197
00:10:04,270 --> 00:10:12,410
>> So dan is dit te plaas, hier sien ons ons
is die toeken van die volgende waarde van ons node

198
00:10:12,410 --> 00:10:17,380
te wees wat hoof is,
en dit is wat ons hier het.

199
00:10:17,380 --> 00:10:19,930
Dit is wat ons nou net gedoen het.

200
00:10:19,930 --> 00:10:25,820
En dan is ons toeken hoof punt
ons nuwe knoop, want onthou,

201
00:10:25,820 --> 00:10:31,090
nuwe is 'n verwysing na 'n knoop,
en dit is presies wat die hoof is.

202
00:10:31,090 --> 00:10:34,370
Dit is presies die rede waarom ons
hierdie pyl accessor.

203
00:10:34,370 --> 00:10:37,030

204
00:10:37,030 --> 00:10:37,530
Cool?

205
00:10:37,530 --> 00:10:38,130
Mmhmm?

206
00:10:38,130 --> 00:10:41,100
>> Publiek: Het ons te
inisialiseer nuwe langs eerste van nul,

207
00:10:41,100 --> 00:10:44,240
of kan ons net inisialiseer aan die hoof?

208
00:10:44,240 --> 00:10:48,210
>> Spreker 1: New volgende
moet NULL te begin

209
00:10:48,210 --> 00:10:53,760
want jy weet nie
waar dit gaan wees.

210
00:10:53,760 --> 00:10:56,100
Ook, dit is soort van
net soos 'n paradigma.

211
00:10:56,100 --> 00:10:59,900
Jy stel dit gelyk aan NULL net te maak
seker dat al jou basisse word gedek

212
00:10:59,900 --> 00:11:04,070
voordat jy enige bestemming sodat
jy altyd gewaarborg dat dit sal

213
00:11:04,070 --> 00:11:08,880
word verwys na 'n spesifieke waarde
versus soos 'n gemors waarde.

214
00:11:08,880 --> 00:11:12,210
Omdat, ja, ons ken
nuwe volgende outomaties,

215
00:11:12,210 --> 00:11:15,420
maar dit is meer net soos 'n
goeie praktyk om dit te inisialiseer

216
00:11:15,420 --> 00:11:19,270
Op dié manier en dan toewys.

217
00:11:19,270 --> 00:11:23,420
>> OK, so dubbeld gekoppel lyste nou.

218
00:11:23,420 --> 00:11:24,601
Wat dink ons?

219
00:11:24,601 --> 00:11:26,350
Wat is anders met
dubbel gekoppel lyste?

220
00:11:26,350 --> 00:11:30,750

221
00:11:30,750 --> 00:11:34,300
>> So in ons geskakelde lyste, kan ons
slegs in een rigting beweeg, reg?

222
00:11:34,300 --> 00:11:35,270
Ons het net die volgende.

223
00:11:35,270 --> 00:11:36,760
Ons kan net vorentoe gaan.

224
00:11:36,760 --> 00:11:40,300
>> Met 'n dubbel gekoppel lys
Ons kan ook agteruit beweeg.

225
00:11:40,300 --> 00:11:44,810
So ons het nie net die
getal wat ons wil op te slaan,

226
00:11:44,810 --> 00:11:50,110
ons het waar dit verwys na die volgende
en waar ons net vandaan kom.

227
00:11:50,110 --> 00:11:52,865
So dit maak voorsiening vir
'n beter traversal.

228
00:11:52,865 --> 00:11:56,620

229
00:11:56,620 --> 00:12:01,240
>> So dubbel gekoppel knope,
baie soortgelyk, reg?

230
00:12:01,240 --> 00:12:05,000
Enigste verskil is nou ons
'n volgende en 'n vorige.

231
00:12:05,000 --> 00:12:06,235
Dit is die enigste verskil.

232
00:12:06,235 --> 00:12:09,570

233
00:12:09,570 --> 00:12:14,790
>> So as ons die prefix of append-- ons
nie enige kode vir die up here--

234
00:12:14,790 --> 00:12:17,830
maar as jy was om te probeer en
plaas dit, die belangrikste ding

235
00:12:17,830 --> 00:12:19,980
is wat jy nodig het om te maak
seker dat jy die toeken

236
00:12:19,980 --> 00:12:23,360
beide jou vorige en jou
volgende wyser korrek.

237
00:12:23,360 --> 00:12:29,010
So in hierdie geval, sou jy
nie net langs inisialiseer,

238
00:12:29,010 --> 00:12:31,820
jy inisialiseer vorige.

239
00:12:31,820 --> 00:12:36,960
As ons aan die hoof van die lys, ons
nie net maak kop gelyk nuwe,

240
00:12:36,960 --> 00:12:41,750
maar ons nuwe vorige indien
wys op die kop, reg?

241
00:12:41,750 --> 00:12:43,380
>> Dit is die enigste verskil.

242
00:12:43,380 --> 00:12:47,200
En as jy meer oefening wil
dit met geskakelde lyste met inbring,

243
00:12:47,200 --> 00:12:49,900
met die verwydering, met insetsel
in 'n verskeidenheid lys

244
00:12:49,900 --> 00:12:52,670
check study.cs50.net.

245
00:12:52,670 --> 00:12:54,870
Daar is 'n klomp van die groot oefeninge.

246
00:12:54,870 --> 00:12:55,870
Ek raai hulle.

247
00:12:55,870 --> 00:12:59,210
Ek wens ons tyd om te gaan deur middel van hulle het
maar daar is 'n baie data strukture

248
00:12:59,210 --> 00:13:01,530
te kry deur.

249
00:13:01,530 --> 00:13:02,650
>> OK, so hash tabelle.

250
00:13:02,650 --> 00:13:07,070
Dit is waarskynlik die mees
nuttige bietjie vir jou pset

251
00:13:07,070 --> 00:13:11,090
hier, want jy gaan wees
implementering van een van hierdie, of 'n drie.

252
00:13:11,090 --> 00:13:12,200
Ek het regtig soos hash tabelle.

253
00:13:12,200 --> 00:13:13,110
Hulle is redelik cool.

254
00:13:13,110 --> 00:13:17,080
>> So basies wat
gebeur, is 'n gemors tafel

255
00:13:17,080 --> 00:13:22,050
is wanneer ons regtig nodig spoedige
plasing, skrap, en soek.

256
00:13:22,050 --> 00:13:25,010
Dit is die dinge wat ons is
prioritiseer in 'n gemors tafel.

257
00:13:25,010 --> 00:13:29,500
Hulle kan 'n bietjie groot,
maar soos ons sal sien met drieë,

258
00:13:29,500 --> 00:13:33,040
daar is dinge wat veel groter.

259
00:13:33,040 --> 00:13:38,330
>> Maar basies, al 'n gemors
tabel is 'n hash funksie

260
00:13:38,330 --> 00:13:47,215
wat vir jou vertel wat emmer elke te sit
van jou data, elkeen van jou elemente in.

261
00:13:47,215 --> 00:13:51,140
'N eenvoudige manier om te dink van 'n hash tafel
is dat dit net emmers van dinge,

262
00:13:51,140 --> 00:13:51,770
reg?

263
00:13:51,770 --> 00:13:59,720
So wanneer jy sorteer dinge deur
soos die eerste letter van die naam,

264
00:13:59,720 --> 00:14:01,820
dit is soort van soos 'n hash tafel.

265
00:14:01,820 --> 00:14:06,180
>> So as ek by die groep julle ouens is
in groepe van wie se naam begin

266
00:14:06,180 --> 00:14:11,670
met 'n hier, of wie se verjaarsdag
is in Januarie, Februarie, Maart,

267
00:14:11,670 --> 00:14:15,220
wat ook al, dit is effektief
skep van 'n hash tafel.

268
00:14:15,220 --> 00:14:18,120
Dit is net die skep van emmers wat
jou elemente sorteer in

269
00:14:18,120 --> 00:14:19,520
sodat jy dit makliker kan vind.

270
00:14:19,520 --> 00:14:22,300
So op hierdie manier wanneer ek nodig het
een van jou te vind,

271
00:14:22,300 --> 00:14:24,680
Ek hoef nie te soek
deur elkeen van julle name.

272
00:14:24,680 --> 00:14:29,490
Ek kan wees, o, ek weet dat
Danielle se verjaarsdag is in--

273
00:14:29,490 --> 00:14:30,240
Publiek: --April.

274
00:14:30,240 --> 00:14:30,948
Spreker 1: April.

275
00:14:30,948 --> 00:14:33,120
So ek sien in my April
emmer, en met 'n bietjie geluk,

276
00:14:33,120 --> 00:14:38,270
sy die enigste een in daar sal wees en
my tyd was konstant in daardie sin,

277
00:14:38,270 --> 00:14:41,230
terwyl as ek het om te kyk
deur 'n hele klomp van die mense,

278
00:14:41,230 --> 00:14:43,090
dit gaan veel langer neem.

279
00:14:43,090 --> 00:14:45,830
So hash tabelle is regtig net emmers.

280
00:14:45,830 --> 00:14:48,630
Maklike manier om te dink van hulle.

281
00:14:48,630 --> 00:14:52,930
>> So 'n baie belangrike ding oor
'n gemors tabel is 'n hash funksie.

282
00:14:52,930 --> 00:14:58,140
So die dinge wat ek net gepraat het, soos
jou eerste letter van jou naam

283
00:14:58,140 --> 00:15:01,450
of jou verjaarsdag maand,
hierdie is idees wat

284
00:15:01,450 --> 00:15:03,070
regtig ooreen met 'n hash funksie.

285
00:15:03,070 --> 00:15:08,900
Dit is net 'n manier om te besluit watter
emmer jy is element gaan in, OK?

286
00:15:08,900 --> 00:15:14,850
So vir hierdie pset, kan jy kyk op
pretty much enige hash funksie wat jy wil.

287
00:15:14,850 --> 00:15:16,030
>> Hoef nie jou eie wees.

288
00:15:16,030 --> 00:15:21,140
Daar is 'n paar regtig cool kinders uit
daar wat dit doen allerhande mal wiskunde.

289
00:15:21,140 --> 00:15:25,170
En as jy wil om jou te maak
speltoetser super vinnig,

290
00:15:25,170 --> 00:15:27,620
Ek sou beslis
kyk na een van daardie.

291
00:15:27,620 --> 00:15:32,390
>> Maar daar is ook die
eenvoudige mense, soos bereken

292
00:15:32,390 --> 00:15:39,010
Die som van die woorde, soos
elke letter het 'n aantal.

293
00:15:39,010 --> 00:15:39,940
Bereken die som.

294
00:15:39,940 --> 00:15:42,230
Dit bepaal die emmer.

295
00:15:42,230 --> 00:15:45,430
Hulle het ook die maklike kinders wat
is net soos al die A's hier,

296
00:15:45,430 --> 00:15:47,050
al die B is hier.

297
00:15:47,050 --> 00:15:48,920
Enige een van daardie.

298
00:15:48,920 --> 00:15:55,770
>> Eintlik is dit net vir jou vertel wat
verskeidenheid indeks jou element moet gaan in.

299
00:15:55,770 --> 00:15:58,690
Net die besluit van die bucket--
dit is alles 'n hash funksie is.

300
00:15:58,690 --> 00:16:04,180
So hier het ons 'n voorbeeld wat
net die eerste letter van die string

301
00:16:04,180 --> 00:16:05,900
dat ek net praat.

302
00:16:05,900 --> 00:16:11,900
>> So jy het 'n paar hash dit is net die
eerste letter van jou string minus A,

303
00:16:11,900 --> 00:16:16,090
wat julle sal gee
getal tussen 0 en 25.

304
00:16:16,090 --> 00:16:20,790
En wat jy wil doen, is
seker te maak dat dit verteenwoordig

305
00:16:20,790 --> 00:16:24,110
die grootte van jou hash table--
hoeveel emmers is daar.

306
00:16:24,110 --> 00:16:25,860
Met baie van hierdie
hash funksies, hulle is

307
00:16:25,860 --> 00:16:31,630
gaan word terugkeer waardes wat kan
wees ver bo die aantal emmers

308
00:16:31,630 --> 00:16:33,610
dat jy eintlik '
in jou hash tafel,

309
00:16:33,610 --> 00:16:37,240
sodat jy nodig het om te maak
seker en mod deur diegene.

310
00:16:37,240 --> 00:16:42,190
Andersins, dit gaan om te sê,
O ja, moet dit in die emmer 5000 wees

311
00:16:42,190 --> 00:16:46,040
maar jy het net 30
emmers in jou hash tafel.

312
00:16:46,040 --> 00:16:49,360
En natuurlik, ons almal weet dit is
gaan lei tot 'n paar mal foute.

313
00:16:49,360 --> 00:16:52,870
So maak seker dat jy mod deur die
grootte van jou hash tafel.

314
00:16:52,870 --> 00:16:58,430

315
00:16:58,430 --> 00:16:58,930
Cool.

316
00:16:58,930 --> 00:17:00,506
So botsings.

317
00:17:00,506 --> 00:17:02,620
Is almal goeie so ver?

318
00:17:02,620 --> 00:17:03,120
Mmhmm?

319
00:17:03,120 --> 00:17:05,900
>> Publiek: Hoekom sou dit
terug so 'n massiewe waarde?

320
00:17:05,900 --> 00:17:09,210
>> Spreker 1: Afhangende van die algoritme
dat jou hash funksie gebruik.

321
00:17:09,210 --> 00:17:12,270
Sommige van hulle sal doen
gek vermenigvuldiging.

322
00:17:12,270 --> 00:17:16,270
En dit is alles oor die manier waarop
'n eweredige verspreiding,

323
00:17:16,270 --> 00:17:18,490
sodat hulle nie 'n paar baie
gek dinge soms.

324
00:17:18,490 --> 00:17:20,960
Dit is al.

325
00:17:20,960 --> 00:17:22,140
Enigiets anders?

326
00:17:22,140 --> 00:17:22,829
OK.

327
00:17:22,829 --> 00:17:24,480
>> So botsings.

328
00:17:24,480 --> 00:17:29,270
Basies, soos ek vroeër gesê het,
in die beste geval,

329
00:17:29,270 --> 00:17:32,040
enige emmer Ek kyk na is
gaan een ding om te hê,

330
00:17:32,040 --> 00:17:34,160
so ek het nie om te kyk na alles, reg?

331
00:17:34,160 --> 00:17:37,040
Ek weet ook dit is daar of dit is
nie, en dit is wat ons regtig wil.

332
00:17:37,040 --> 00:17:43,960
Maar as ons tienduisende
data punte en minder as dat die getal

333
00:17:43,960 --> 00:17:48,700
emmers, ons gaan te hê
botsings waar uiteindelik iets

334
00:17:48,700 --> 00:17:54,210
gaan hê om te eindig in 'n
emmer wat reeds 'n element.

335
00:17:54,210 --> 00:17:57,390
>> So die vraag is, wat
doen ons in so 'n geval?

336
00:17:57,390 --> 00:17:58,480
Wat doen ons?

337
00:17:58,480 --> 00:17:59,300
Ons het reeds iets daar te hê?

338
00:17:59,300 --> 00:18:00,060
Moenie net gooi ons dit uit?

339
00:18:00,060 --> 00:18:00,700
>> No.

340
00:18:00,700 --> 00:18:01,980
Ons het beide van hulle te hou.

341
00:18:01,980 --> 00:18:06,400
So die manier waarop ons
tipies doen is wat?

342
00:18:06,400 --> 00:18:08,400
Wat is die data struktuur
Ons het net gepraat oor?

343
00:18:08,400 --> 00:18:09,316
Publiek: Gekoppel lys.

344
00:18:09,316 --> 00:18:10,500
Spreker 1: 'n geskakelde lys.

345
00:18:10,500 --> 00:18:16,640
So nou, in plaas van elk van hierdie
emmers net met een element,

346
00:18:16,640 --> 00:18:24,020
dit gaan 'n gekoppelde lys van te bevat
die elemente wat hashed is in dit.

347
00:18:24,020 --> 00:18:27,588
OK, nie almal soort van daardie idee?

348
00:18:27,588 --> 00:18:30,546
Omdat ons nie kan het 'n verskeidenheid
want ons weet nie hoe baie dinge

349
00:18:30,546 --> 00:18:31,730
gaan wees daar.

350
00:18:31,730 --> 00:18:36,540
'N geskakelde lys ons toelaat om te
het net die presiese aantal wat

351
00:18:36,540 --> 00:18:38,465
word hashed in die emmer, reg?

352
00:18:38,465 --> 00:18:42,260

353
00:18:42,260 --> 00:18:50,500
>> So lineêre indringende is
basies hierdie idea--

354
00:18:50,500 --> 00:18:52,300
dit is een manier om te gaan met 'n botsing.

355
00:18:52,300 --> 00:18:58,010
Wat jy kan doen is as in hierdie
geval, was Berry hashed in 1

356
00:18:58,010 --> 00:19:01,130
en ons het reeds
iets daar, jy moet net

357
00:19:01,130 --> 00:19:04,840
hou totdat
vind jy 'n leë slot.

358
00:19:04,840 --> 00:19:06,370
Dit is een manier om dit te hanteer.

359
00:19:06,370 --> 00:19:09,020
Die ander manier te hanteer
dit is met wat ons nou net

360
00:19:09,020 --> 00:19:12,280
called-- die gekoppelde
lys aaneenskakeling genoem.

361
00:19:12,280 --> 00:19:20,510
>> So hierdie idee werk as
jou hash tafel wat jy dink

362
00:19:20,510 --> 00:19:24,150
is baie groter as
datastel of as jy

363
00:19:24,150 --> 00:19:28,870
wil om te probeer en verminder chaining
totdat dit absoluut noodsaaklik is.

364
00:19:28,870 --> 00:19:34,050
So een ding is lineêre
indringende natuurlik beteken

365
00:19:34,050 --> 00:19:37,290
dat jou hash funksie
is nie so nuttig

366
00:19:37,290 --> 00:19:42,200
want jy gaan om te eindig met behulp van
jou hash funksie, om na 'n punt,

367
00:19:42,200 --> 00:19:46,400
jy Lineêre ondersoek af te
'n plek wat beskikbaar is.

368
00:19:46,400 --> 00:19:49,670
Maar nou, natuurlik, enigiets
anders wat eindig daar,

369
00:19:49,670 --> 00:19:52,050
jy gaan te hê
soek nog verder af.

370
00:19:52,050 --> 00:19:55,650
>> En daar is 'n baie meer
soek koste wat

371
00:19:55,650 --> 00:19:59,820
gaan in die skryf van 'n element
in jou hash tafel nou, reg?

372
00:19:59,820 --> 00:20:05,640
En nou wanneer jy gaan en probeer en vind
Berry weer jy gaan om dit te hash,

373
00:20:05,640 --> 00:20:07,742
en dit gaan om te sê,
O, kyk in die emmer 1,

374
00:20:07,742 --> 00:20:09,700
en dit is nie van plan om
in die emmer 1, sodat jy

375
00:20:09,700 --> 00:20:11,970
gaan hê om oor te steek
deur die res van hierdie.

376
00:20:11,970 --> 00:20:17,720
So dit is soms nuttig,
maar in die meeste gevalle,

377
00:20:17,720 --> 00:20:22,660
ons gaan om te sê dat
aaneenskakeling is wat jy wil doen.

378
00:20:22,660 --> 00:20:25,520
>> So het ons gepraat oor hierdie vroeër.

379
00:20:25,520 --> 00:20:27,812
Ek het 'n bietjie voor my.

380
00:20:27,812 --> 00:20:33,560
Maar aaneenskakeling is basies dat
elke emmer in jou hash tafel

381
00:20:33,560 --> 00:20:36,120
is net 'n geskakelde lys.

382
00:20:36,120 --> 00:20:39,660
>> So 'n ander manier, of meer tegniese
manier om te dink van 'n hash tafel

383
00:20:39,660 --> 00:20:44,490
is dat dit net 'n skikking
van geskakelde lyste, wat

384
00:20:44,490 --> 00:20:49,330
wanneer jy jou woordeboek wil skryf
en jy probeer om dit te laai,

385
00:20:49,330 --> 00:20:52,070
dink aan dit as 'n
verskeidenheid van geskakelde lyste

386
00:20:52,070 --> 00:20:54,390
maak dit baie makliker
vir jou te begin.

387
00:20:54,390 --> 00:20:57,680
>> Publiek: So hash tafel
'n voorafbepaalde grootte,

388
00:20:57,680 --> 00:20:58,980
soos 'n [onhoorbaar] emmers?

389
00:20:58,980 --> 00:20:59,220
>> Spreker 1: Right.

390
00:20:59,220 --> 00:21:01,655
So het dit 'n sekere aantal
emmers dat jy determine--

391
00:21:01,655 --> 00:21:03,530
wat julle moet
voel vry om te speel met.

392
00:21:03,530 --> 00:21:05,269
Dit kan wees pretty cool
om te sien wat gebeur

393
00:21:05,269 --> 00:21:06,810
as jy jou aantal emmers verander.

394
00:21:06,810 --> 00:21:09,410

395
00:21:09,410 --> 00:21:11,510
Maar ja, dit het 'n
stel aantal emmers.

396
00:21:11,510 --> 00:21:15,360
Wat kan jy aan te pas as
baie elemente as wat jy nodig het

397
00:21:15,360 --> 00:21:19,350
is hierdie aparte aaneenskakeling waar jy
gekoppel lyste in elke emmer.

398
00:21:19,350 --> 00:21:22,850
Dit beteken dat jou hash tafel
presies die grootte

399
00:21:22,850 --> 00:21:25,440
wat jy nodig het om dit te wees, reg?

400
00:21:25,440 --> 00:21:27,358
Dit is die hele punt van geskakelde lyste.

401
00:21:27,358 --> 00:21:30,850

402
00:21:30,850 --> 00:21:32,480
Cool.

403
00:21:32,480 --> 00:21:38,780
>> Sodat almal OK daar?

404
00:21:38,780 --> 00:21:39,801
Alle regte.

405
00:21:39,801 --> 00:21:40,300
Ag.

406
00:21:40,300 --> 00:21:41,860
Wat het gebeur?

407
00:21:41,860 --> 00:21:42,960
Nou regtig.

408
00:21:42,960 --> 00:21:45,250
Raai iemand se dood vir my.

409
00:21:45,250 --> 00:21:52,060
>> OK ons gaan om te gaan in
drieë, wat is 'n bietjie mal.

410
00:21:52,060 --> 00:21:53,140
Ek hou van hash tabelle.

411
00:21:53,140 --> 00:21:54,460
Ek dink dit is regtig cool.

412
00:21:54,460 --> 00:21:56,710
Drieë is koel, ook.

413
00:21:56,710 --> 00:21:59,590
>> So nie almal onthou wat 'n drie is?

414
00:21:59,590 --> 00:22:01,740
Jy moes gegaan het oor
dit kortliks in lesing?

415
00:22:01,740 --> 00:22:04,570

416
00:22:04,570 --> 00:22:06,377
Onthou jy soort van hoe dit werk?

417
00:22:06,377 --> 00:22:08,460
Publiek: Ek is net knik
dat ons nie gaan oor dit.

418
00:22:08,460 --> 00:22:09,626
Spreker 1: Ons gaan oor dit.

419
00:22:09,626 --> 00:22:13,100
OK, ons is regtig gaan om te gaan
oor dit nou is wat ons sê.

420
00:22:13,100 --> 00:22:14,860
>> Publiek: Dit is vir 'n herwinning boom.

421
00:22:14,860 --> 00:22:15,280
>> Spreker 1: Ja.

422
00:22:15,280 --> 00:22:16,196
Dit is 'n herwinning boom.

423
00:22:16,196 --> 00:22:16,960
Awesome.

424
00:22:16,960 --> 00:22:23,610
So een ding om hier te let is dat ons
is op soek na individuele karakters

425
00:22:23,610 --> 00:22:24,480
hier, reg?

426
00:22:24,480 --> 00:22:29,710
>> So voordat ons hash funksie, ons
is op soek na die woorde as 'n geheel,

427
00:22:29,710 --> 00:22:32,270
en nou is ons meer soek
by die karakters, reg?

428
00:22:32,270 --> 00:22:38,380
So ons het Maxwell hier en Mendel.

429
00:22:38,380 --> 00:22:47,840
So basies 'n try-- 'n manier om te dink
oor hierdie is dat elke vlak hier

430
00:22:47,840 --> 00:22:49,000
is 'n skikking van die briewe.

431
00:22:49,000 --> 00:22:53,310

432
00:22:53,310 --> 00:22:55,790
So is dit jou wortel node hier, reg?

433
00:22:55,790 --> 00:23:01,980
Dit het al die karakters van die
alfabet vir die begin van elke woord.

434
00:23:01,980 --> 00:23:06,480
>> En wat jy wil doen, is
sê, OK, ons het 'n paar M woord.

435
00:23:06,480 --> 00:23:10,590
Ons gaan om te kyk vir Maxwell, so
ons gaan na M. En M punte na 'n hele

436
00:23:10,590 --> 00:23:14,800
ander 'n skikking waar elke
woord, solank as wat daar

437
00:23:14,800 --> 00:23:17,044
is 'n woord wat 'n
as die tweede brief,

438
00:23:17,044 --> 00:23:19,460
so lank as wat daar is 'n woord wat
het B as die tweede brief,

439
00:23:19,460 --> 00:23:24,630
dit sal 'n wyser het
gaan 'n volgende reeks.

440
00:23:24,630 --> 00:23:29,290
>> Daar is waarskynlik nie 'n
woord wat LP iets,

441
00:23:29,290 --> 00:23:32,980
so by die P posisie in dié
skikking, sou dit net wees NULL.

442
00:23:32,980 --> 00:23:38,840
Dit sou sê, OK, daar is geen woord
wat M gevolg deur 'n P, OK?

443
00:23:38,840 --> 00:23:43,100
So as ons dink oor dit, elke
een van hierdie kleiner dinge

444
00:23:43,100 --> 00:23:47,990
is eintlik een van hierdie
groot skikkings van 'n deur Z.

445
00:23:47,990 --> 00:23:55,064
So, wat kan een van die dinge wees
dit is soort van 'n nadeel van 'n probeer?

446
00:23:55,064 --> 00:23:56,500
>> GEHOOR: 'n baie van die geheue.

447
00:23:56,500 --> 00:23:59,940
>> Spreker 1: Dit is 'n ton van die geheue, reg?

448
00:23:59,940 --> 00:24:08,750
Elkeen van hierdie blokke hier
verteenwoordig 26 ruimtes, 26 element skikking.

449
00:24:08,750 --> 00:24:13,680
So drieë kry ongelooflik ruimte swaar.

450
00:24:13,680 --> 00:24:17,100
>> Maar hulle is baie vinnig.

451
00:24:17,100 --> 00:24:22,540
So ongelooflik vinnig, maar
werklik ruimte ondoeltreffend.

452
00:24:22,540 --> 00:24:24,810
Soort het om uit te vind
uit watter een jy wil.

453
00:24:24,810 --> 00:24:29,470
Dit is werklik 'n koel vir jou pset,
maar hulle doen neem 'n baie van die geheue,

454
00:24:29,470 --> 00:24:30,290
sodat jy handel nie.

455
00:24:30,290 --> 00:24:31,480
Ja?

456
00:24:31,480 --> 00:24:34,300
>> Publiek: Sou dit moontlik wees
om 'n drie gedruk en dan

457
00:24:34,300 --> 00:24:37,967
Sodra jy al die
data in dit wat jy need--

458
00:24:37,967 --> 00:24:39,550
Ek weet nie of dit sal sin maak.

459
00:24:39,550 --> 00:24:42,200
Ek is om ontslae te raak van al die
NULL karakters, maar dan

460
00:24:42,200 --> 00:24:42,910
sou jy nie in staat wees om na die indeks them--

461
00:24:42,910 --> 00:24:43,275
>> Spreker 1: Jy moet nog steeds hulle.

462
00:24:43,275 --> 00:24:44,854
>> Publiek: - op dieselfde manier elke keer.

463
00:24:44,854 --> 00:24:45,520
Spreker 1: Ja.

464
00:24:45,520 --> 00:24:50,460
Jy moet die NULL karakters te laat
jy weet as daar nie 'n woord daar.

465
00:24:50,460 --> 00:24:52,040
Ben het jy iets wat jy wil hê?

466
00:24:52,040 --> 00:24:52,540
OK.

467
00:24:52,540 --> 00:24:54,581
Alle reg, so ons gaan
'n bietjie meer gaan

468
00:24:54,581 --> 00:24:58,920
in die tegniese detail agter
'n probeer en werk deur middel van 'n voorbeeld.

469
00:24:58,920 --> 00:25:01,490
>> OK, so dit is dieselfde ding.

470
00:25:01,490 --> 00:25:06,290
Terwyl dit in 'n geskakelde lys, ons vernaamste
soort of-- wat is die woord wat ek wil hê? -

471
00:25:06,290 --> 00:25:08,350
soos die bou blok was 'n knoop.

472
00:25:08,350 --> 00:25:12,280
In 'n drie, ons het ook 'n knoop,
maar dit is verskillend gedefinieer.

473
00:25:12,280 --> 00:25:17,000
>> So ons het 'n paar Bool wat
verteenwoordig of 'n woord eintlik

474
00:25:17,000 --> 00:25:23,530
bestaan ​​by hierdie plek, en dan
Ons het 'n paar verskeidenheid here-- of liewer,

475
00:25:23,530 --> 00:25:27,840
Dit is 'n verwysing na 'n
verskeidenheid van 27 karakters.

476
00:25:27,840 --> 00:25:33,339
En dit is vir, in hierdie geval, is hierdie
27-- Ek is seker almal van julle is soos, wag,

477
00:25:33,339 --> 00:25:34,880
daar is 26 letters in die alfabet.

478
00:25:34,880 --> 00:25:36,010
Hoekom het ons 27?

479
00:25:36,010 --> 00:25:37,870
>> So, afhangende van die
manier waarop jy die uitvoering van hierdie,

480
00:25:37,870 --> 00:25:43,240
Dit is van 'n pset wat
toegelaat vir apostrofes.

481
00:25:43,240 --> 00:25:46,010
So dit is waarom die ekstra een.

482
00:25:46,010 --> 00:25:50,500
Jy sal ook in sommige
gevalle die nul terminator

483
00:25:50,500 --> 00:25:53,230
is ingesluit as een van die
karakters dat dit toegelaat word om te wees,

484
00:25:53,230 --> 00:25:56,120
en dit is hoe hulle gaan om te
sien of dit is die einde van die woord.

485
00:25:56,120 --> 00:26:01,340
As jy belangstel, check
Kevin se video op study.cs50,

486
00:26:01,340 --> 00:26:04,790
sowel as Wikipedia het
'n paar goeie hulpbronne daar.

487
00:26:04,790 --> 00:26:09,000
>> Maar ons gaan om te gaan deur net soort
van hoe jy deur middel van 'n drie kan werk

488
00:26:09,000 --> 00:26:11,010
As jy een gegee.

489
00:26:11,010 --> 00:26:16,230
So ons het 'n super eenvoudige een hier wat
het die woorde "kolf" en "zoom" in hulle.

490
00:26:16,230 --> 00:26:18,920
En as ons sien hier,
hierdie klein ruimte hier

491
00:26:18,920 --> 00:26:22,560
verteenwoordig ons Bool wat
sê, ja, dit is 'n woord.

492
00:26:22,560 --> 00:26:27,060
En dan moet dit ons
skikkings van die karakters, reg?

493
00:26:27,060 --> 00:26:33,480
>> So gaan ons deur te gaan
vind "kolf" in hierdie drie.

494
00:26:33,480 --> 00:26:38,340
So begin by die top, reg?

495
00:26:38,340 --> 00:26:46,290
En ons weet dat b ooreenstem met
die tweede indeks, is die tweede element

496
00:26:46,290 --> 00:26:47,840
in hierdie skikking, omdat a en b.

497
00:26:47,840 --> 00:26:51,340
So ongeveer die tweede een.

498
00:26:51,340 --> 00:26:58,820
>> En dit sê, OK, koel, volg wat in
die volgende skikking, want as ons onthou,

499
00:26:58,820 --> 00:27:02,160
dit is nie dat elkeen van hierdie
eintlik bevat die element.

500
00:27:02,160 --> 00:27:07,110
Elkeen van hierdie skikkings
bevat 'n wyser, reg?

501
00:27:07,110 --> 00:27:10,030
Dit is 'n belangrike onderskeid te maak.

502
00:27:10,030 --> 00:27:13,450
>> Ek weet dit gaan be-- drieë is
werklik moeilik om te kry op die eerste keer,

503
00:27:13,450 --> 00:27:15,241
sodat selfs wanneer dit is die
tweede of derde keer

504
00:27:15,241 --> 00:27:18,370
en dit is nog steeds soort
van oënskynlike moeilik,

505
00:27:18,370 --> 00:27:21,199
Ek belowe as jy gaan kyk
die kort môre weer,

506
00:27:21,199 --> 00:27:22,740
dit sal waarskynlik 'n baie meer sin.

507
00:27:22,740 --> 00:27:23,890
Dit neem baie om te verteer.

508
00:27:23,890 --> 00:27:27,800
Ek het nog soms is
soos, wag, wat is 'n probeer?

509
00:27:27,800 --> 00:27:29,080
Hoe gebruik ek dit?

510
00:27:29,080 --> 00:27:33,880
>> So het ons in hierdie geval B sal hê,
wat is ons tweede indeks.

511
00:27:33,880 --> 00:27:40,240
As ons gehad het, sê, c of
d of enige ander brief,

512
00:27:40,240 --> 00:27:45,810
ons moet dit terug na die indeks te karteer
van ons skikking wat wat ooreenstem met.

513
00:27:45,810 --> 00:27:56,930
So ons sal neem soos rchar en ons het net
trek uit 'n dit te karteer in 0-25.

514
00:27:56,930 --> 00:27:58,728
Almal goeie hoe ons
kaart ons karakters?

515
00:27:58,728 --> 00:28:00,440
OK.

516
00:28:00,440 --> 00:28:05,980
>> So gaan ons na die tweede een, en ons
sien dat, ja, dit is nie NULL.

517
00:28:05,980 --> 00:28:07,780
Ons kan aanbeweeg na die volgende reeks.

518
00:28:07,780 --> 00:28:12,300
So gaan ons na hierdie volgende skikking hier.

519
00:28:12,300 --> 00:28:15,500
>> En ons sê, OK, nou is ons
nodig het om te kyk of 'n is hier.

520
00:28:15,500 --> 00:28:18,590
Is 'n nul of is dit
eintlik vorentoe te beweeg?

521
00:28:18,590 --> 00:28:21,880
So 'n werklikheid beweeg
vorentoe in hierdie reeks.

522
00:28:21,880 --> 00:28:24,570
En ons sê, OK, t is ons laaste brief.

523
00:28:24,570 --> 00:28:27,580
So gaan ons na die t op die indeks.

524
00:28:27,580 --> 00:28:30,120
En dan vorentoe beweeg ons
want daar is 'n ander een.

525
00:28:30,120 --> 00:28:38,340
En hierdie een sê basies dat, ja,
dit sê dat daar is 'n woord here--

526
00:28:38,340 --> 00:28:41,750
dat as jy hierdie
pad, jy het aangekom

527
00:28:41,750 --> 00:28:43,210
'n woord wat ons weet, is "kolf."

528
00:28:43,210 --> 00:28:43,800
Ja?

529
00:28:43,800 --> 00:28:46,770
>> Publiek: Is dit standaard te hê wat
as indeks 0 en dan 'n soort op 1

530
00:28:46,770 --> 00:28:47,660
of aan die einde?

531
00:28:47,660 --> 00:28:48,243
>> Spreker 1: No.

532
00:28:48,243 --> 00:28:55,360
So, as ons terugkyk na ons
verklaring hier, dit is 'n Bool,

533
00:28:55,360 --> 00:28:59,490
so dit is sy eie element in jou knoop.

534
00:28:59,490 --> 00:29:03,331
So dit is nie deel van die skikking.

535
00:29:03,331 --> 00:29:03,830
Cool.

536
00:29:03,830 --> 00:29:08,370
So wanneer ons klaar is met ons woorde en ons is
op hierdie skikking, wat ons wil doen

537
00:29:08,370 --> 00:29:12,807
is nie 'n tjek vir is dit 'n woord.

538
00:29:12,807 --> 00:29:14,390
En in hierdie geval, sou dit wel terugkeer.

539
00:29:14,390 --> 00:29:17,220

540
00:29:17,220 --> 00:29:24,090
>> So op daardie noot, ons weet dat "dieretuin" -
ons weet as mense wat "dieretuin" is 'n woord,

541
00:29:24,090 --> 00:29:24,820
reg?

542
00:29:24,820 --> 00:29:28,990
Maar probeer om hier sou
sê, nee, dit is nie.

543
00:29:28,990 --> 00:29:33,980
En dit sal sê dat omdat ons
het nie aangewys as 'n woord hier.

544
00:29:33,980 --> 00:29:40,440
Selfs al het ons kan deurkruis
deur hierdie skikking,

545
00:29:40,440 --> 00:29:43,890
hierdie drie sou sê dat, nee,
dieretuin is nie in jou woordeboek

546
00:29:43,890 --> 00:29:47,070
want ons het nie
aangewese dit so.

547
00:29:47,070 --> 00:29:52,870
>> So 'n manier om te doen that--
O, jammer, hierdie een.

548
00:29:52,870 --> 00:29:59,450
So in hierdie geval, "dieretuin" is nie
'n woord, maar dit is in ons probeer.

549
00:29:59,450 --> 00:30:05,690
Maar in hierdie een, sê ons dit wil hê
voer die woord "bad," wat gebeur

550
00:30:05,690 --> 00:30:08,260
is ons volg through-- b, a, t.

551
00:30:08,260 --> 00:30:11,820
Ons is in hierdie skikking, en
ons gaan om te soek na h.

552
00:30:11,820 --> 00:30:15,220
>> In hierdie geval, toe ons
kyk na die wyser op h,

553
00:30:15,220 --> 00:30:17,890
dit is wys om te NULL, OK?

554
00:30:17,890 --> 00:30:20,780
So tensy dit uitdruklik
verwys na 'n skikking,

555
00:30:20,780 --> 00:30:25,000
jy aanvaar dat al die verwysings
in hierdie skikking verwys na null.

556
00:30:25,000 --> 00:30:28,270
So in hierdie geval, is h wys
te null sodat ons kan niks doen nie,

557
00:30:28,270 --> 00:30:31,540
so sal dit ook terug
vals is, "bad" is nie hier nie.

558
00:30:31,540 --> 00:30:34,102

559
00:30:34,102 --> 00:30:35,810
So nou is ons eintlik
gaan om te gaan deur middel van

560
00:30:35,810 --> 00:30:39,790
hoe sou ons eintlik sê
dat "dieretuin" is in ons probeer.

561
00:30:39,790 --> 00:30:42,920
Hoe voeg ons nie "dieretuin" in ons probeer?

562
00:30:42,920 --> 00:30:47,810
So in die dieselfde manier as wat ons begin met
ons geskakelde lys, ons begin by die wortel.

563
00:30:47,810 --> 00:30:50,600
Wanneer jy twyfel, begin by
die wortel van hierdie dinge.

564
00:30:50,600 --> 00:30:53,330
>> En ons sal sê, OK, z.

565
00:30:53,330 --> 00:30:55,650
Z bestaan ​​in hierdie, en dit doen nie.

566
00:30:55,650 --> 00:30:58,370
So jy beweeg na
jou volgende skikking, OK?

567
00:30:58,370 --> 00:31:01,482
En dan op die volgende een,
ons sê, OK, nie o bestaan ​​nie?

568
00:31:01,482 --> 00:31:03,000
Dit doen nie.

569
00:31:03,000 --> 00:31:04,330
Dit het weer eens.

570
00:31:04,330 --> 00:31:08,670
>> En so op ons volgende een, het ons gesê:
OK, "dieretuin" bestaan ​​reeds hier.

571
00:31:08,670 --> 00:31:12,440
Al wat ons moet doen, is ingestel om hierdie gelyke
waar, dat daar is 'n woord daar.

572
00:31:12,440 --> 00:31:15,260
As jy alles gevolg het
tot voor daardie punt,

573
00:31:15,260 --> 00:31:17,030
dit is 'n woord, sodat net
stel dit gelyk aan sulke.

574
00:31:17,030 --> 00:31:17,530
Ja?

575
00:31:17,530 --> 00:31:22,550
>> Publiek: doen dit dan
beteken dat "ba" is 'n woord ook?

576
00:31:22,550 --> 00:31:24,120
>> Spreker 1: No.

577
00:31:24,120 --> 00:31:28,870
So in hierdie geval, "ba" Ons sou kry
hier, sal ons sê, is dit 'n woord,

578
00:31:28,870 --> 00:31:31,590
en dit sou nog steeds nie.

579
00:31:31,590 --> 00:31:32,822
OK?

580
00:31:32,822 --> 00:31:33,740
Mmhmm?

581
00:31:33,740 --> 00:31:36,360
>> Publiek: So as jy is om dit 'n
woord en jy sê ja, dan is dit

582
00:31:36,360 --> 00:31:38,380
sal bevat om te gaan na m?

583
00:31:38,380 --> 00:31:42,260
>> Spreker 1: So dit het te doen
with-- jy laai dit in.

584
00:31:42,260 --> 00:31:43,640
Jy sê: "dieretuin" is 'n woord.

585
00:31:43,640 --> 00:31:47,020
Wanneer jy na check--
soos, sê wat jy wil sê,

586
00:31:47,020 --> 00:31:49,400
beteken "dieretuin" bestaan ​​in hierdie woordeboek?

587
00:31:49,400 --> 00:31:54,200
Jy net gaan soek vir "dieretuin"
en dan kyk om te sien of dit is 'n woord.

588
00:31:54,200 --> 00:31:57,291
Jy gaan nooit te beweeg
deur na m, want dit is nie

589
00:31:57,291 --> 00:31:58,290
wat jy soek.

590
00:31:58,290 --> 00:32:02,690

591
00:32:02,690 --> 00:32:08,070
>> So as ons eintlik wou
voeg "bad" in hierdie drie,

592
00:32:08,070 --> 00:32:11,390
sou ons dieselfde ding doen
as ons gedoen het met "dieretuin"

593
00:32:11,390 --> 00:32:15,380
behalwe ons sien dat wanneer ons
probeer en kry om te h, beteken dit nie bestaan ​​nie.

594
00:32:15,380 --> 00:32:20,090
So jy kan dink van hierdie as om
'n nuwe node by te voeg in 'n geskakelde lys,

595
00:32:20,090 --> 00:32:27,210
sodat ons sal moet 'n ander te voeg
een van hierdie skikkings, soos so.

596
00:32:27,210 --> 00:32:35,670
En dan wat ons doen, is ons net soos die h
element van hierdie reeks verwys na hierdie.

597
00:32:35,670 --> 00:32:39,430
>> En dan wat sou ons hier wil doen?

598
00:32:39,430 --> 00:32:43,110
Voeg dit gelyk aan ware
want dit is 'n woord.

599
00:32:43,110 --> 00:32:46,350

600
00:32:46,350 --> 00:32:48,150
Cool.

601
00:32:48,150 --> 00:32:48,700
Ek weet nie.

602
00:32:48,700 --> 00:32:51,170
Drieë is nie die mees opwindende.

603
00:32:51,170 --> 00:32:54,250
Glo my, ek weet.

604
00:32:54,250 --> 00:32:58,040
>> So een ding om te besef met drieë,
Ek het gesê, hulle is baie effektief.

605
00:32:58,040 --> 00:33:00,080
So het ons hulle gesien
neem 'n ton van die ruimte.

606
00:33:00,080 --> 00:33:01,370
Hulle is soort van verwarrend.

607
00:33:01,370 --> 00:33:03,367
So hoekom sou ons ooit gebruik?

608
00:33:03,367 --> 00:33:05,450
Ons gebruik hierdie, want hulle is
ongelooflik doeltreffend.

609
00:33:05,450 --> 00:33:08,130
>> So as jy ooit op soek
'n woord, is jy net

610
00:33:08,130 --> 00:33:10,450
begrens deur die lengte van die woord.

611
00:33:10,450 --> 00:33:15,210
So as jy op soek is na 'n
woord wat 'n lengte van vyf,

612
00:33:15,210 --> 00:33:20,940
jy net ooit gaan hê
maak op die meeste vyf vergelykings, OK?

613
00:33:20,940 --> 00:33:25,780
So dit maak dit eintlik 'n konstante.

614
00:33:25,780 --> 00:33:29,150
Soos inplanting en soek
is basies konstante tyd.

615
00:33:29,150 --> 00:33:33,750
>> So as jy ooit kan kry
iets in konstante tyd,

616
00:33:33,750 --> 00:33:35,150
dit is so goed soos dit kry.

617
00:33:35,150 --> 00:33:37,990
Jy kan nie beter as kry
konstante tyd vir hierdie dinge.

618
00:33:37,990 --> 00:33:43,150
So dit is een van die
groot pluspunte van die drieë.

619
00:33:43,150 --> 00:33:46,780
>> Maar dit is 'n baie ruimte.

620
00:33:46,780 --> 00:33:50,380
So jy soort van moet besluit
Wat is meer belangrik vir jou.

621
00:33:50,380 --> 00:33:54,700
En op vandag se rekenaars, die
ruimte wat 'n drie kan tot

622
00:33:54,700 --> 00:33:57,740
Miskien raak nie
julle het, maar miskien

623
00:33:57,740 --> 00:34:01,350
jy te doen het met iets
wat ver, ver meer dinge,

624
00:34:01,350 --> 00:34:02,810
en 'n drie is net nie redelik.

625
00:34:02,810 --> 00:34:03,000
Ja?

626
00:34:03,000 --> 00:34:05,610
>> Publiek: Wag, sodat jy het 26
letters in elke enkele een?

627
00:34:05,610 --> 00:34:07,440
>> Spreker 1: Mmhmm.

628
00:34:07,440 --> 00:34:08,570
Ja, jy het 26.

629
00:34:08,570 --> 00:34:16,984
Jy het 'n paar is woord merker en dan
jy het 26 wenke in elke een.

630
00:34:16,984 --> 00:34:17,775
En hulle point--

631
00:34:17,775 --> 00:34:20,280
>> Publiek: En elke 26,
hulle het elkeen 26?

632
00:34:20,280 --> 00:34:21,500
>> Spreker 1: Ja.

633
00:34:21,500 --> 00:34:27,460
En dit is hoekom, as jy kan
sien, dit uit redelik vinnig.

634
00:34:27,460 --> 00:34:28,130
Alle regte.

635
00:34:28,130 --> 00:34:32,524
So ons gaan om te kry in die bome, wat
Ek voel is makliker en sal waarskynlik

636
00:34:32,524 --> 00:34:36,150
'n mooi klein uitstel
uit drieë daar.

637
00:34:36,150 --> 00:34:39,620
So hopelik die meeste van julle
het 'n boom gesien het.

638
00:34:39,620 --> 00:34:41,820
Nie soos die mooi
kinders buite, wat ek

639
00:34:41,820 --> 00:34:44,340
Ek weet nie of iemand
het onlangs in die buitelug.

640
00:34:44,340 --> 00:34:49,230
Ek het appel pluk hierdie naweek,
en oh my gosh, dit was pragtig.

641
00:34:49,230 --> 00:34:52,250
Ek het nie blare weet
kon kyk wat mooi.

642
00:34:52,250 --> 00:34:53,610
>> So dit is net 'n boom, reg?

643
00:34:53,610 --> 00:34:56,790
Dit is net 'n paar knoop, en dit
dui op 'n klomp van die ander nodes.

644
00:34:56,790 --> 00:34:59,570
As jy hier sien, is dit
soort van 'n herhalende tema.

645
00:34:59,570 --> 00:35:03,720
Knope wat verwys na nodes is 'n soort van
die essensie van baie data strukture.

646
00:35:03,720 --> 00:35:06,670
Dit hang net af hoe ons
het hulle na mekaar

647
00:35:06,670 --> 00:35:08,600
en hoe ons deurkruis
deur hulle en hoe ons

648
00:35:08,600 --> 00:35:14,500
voeg dinge wat bepaal
hul verskillende eienskappe.

649
00:35:14,500 --> 00:35:17,600
>> So net 'n paar terme,
wat ek voorheen gebruik het.

650
00:35:17,600 --> 00:35:20,010
So wortel is alles wat by die heel boonste.

651
00:35:20,010 --> 00:35:21,200
dit is waar ons altyd begin.

652
00:35:21,200 --> 00:35:23,610
Jy kan dink dat dit as die hoof ook.

653
00:35:23,610 --> 00:35:28,750
Maar vir bome, is ons geneig om te
verwys na dit as die wortel.

654
00:35:28,750 --> 00:35:32,820
>> Enigiets aan die onderkant here--
by die baie, baie bottom--

655
00:35:32,820 --> 00:35:34,500
is van mening blare.

656
00:35:34,500 --> 00:35:37,210
So dit gaan saam met die
hele boom ding, reg?

657
00:35:37,210 --> 00:35:39,860
Blare is op die rand van jou boom.

658
00:35:39,860 --> 00:35:45,820
>> En dan het ons ook 'n paar
terme te praat oor knope in verhouding

659
00:35:45,820 --> 00:35:46,680
aan mekaar.

660
00:35:46,680 --> 00:35:49,700
So het ons 'n ouer,
kinders, en broers en susters.

661
00:35:49,700 --> 00:35:56,260
So in hierdie geval, 3 is die
ouer van 5, 6 en 7.

662
00:35:56,260 --> 00:36:00,370
So het die ouer wat ookal
een stap bo alles wat jy is

663
00:36:00,370 --> 00:36:02,940
verwys na, sodat net
soos 'n stamboom.

664
00:36:02,940 --> 00:36:07,090
Hopelik is dit al 'n bietjie
bietjie meer intuïtief as die drieë.

665
00:36:07,090 --> 00:36:10,970
>> Broers en susters enige wat
dieselfde ouer, reg?

666
00:36:10,970 --> 00:36:13,470
Hulle is op dieselfde vlak hier.

667
00:36:13,470 --> 00:36:16,960
En dan, soos ek was
sê, kinders is net

668
00:36:16,960 --> 00:36:22,630
wat is 'n stap onder
die knoop in die vraag, OK?

669
00:36:22,630 --> 00:36:23,470
Cool.

670
00:36:23,470 --> 00:36:25,610
So 'n binêre boom.

671
00:36:25,610 --> 00:36:31,450
Kan iemand 'n raaiskoot waag op een van
die eienskappe van die tweeledige boom?

672
00:36:31,450 --> 00:36:32,770
>> Publiek: Max twee blare.

673
00:36:32,770 --> 00:36:33,478
>> Spreker 1: Right.

674
00:36:33,478 --> 00:36:34,640
So maksimum van twee blare.

675
00:36:34,640 --> 00:36:39,730
So in hierdie een voor, ons het hierdie een
dat drie, maar in 'n binêre boom,

676
00:36:39,730 --> 00:36:45,000
jy het 'n maksimum van twee
kinders per ouer, reg?

677
00:36:45,000 --> 00:36:46,970
Daar is nog 'n
interessante kenmerk.

678
00:36:46,970 --> 00:36:51,550
Is daar iemand wat weet dat?

679
00:36:51,550 --> 00:36:52,620
Binêre boom.

680
00:36:52,620 --> 00:37:00,350
>> So 'n binêre boom sal alles hê
op the-- hierdie een is nie sorted--

681
00:37:00,350 --> 00:37:05,320
maar in 'n gesorteer binêre boom,
alles op die regte

682
00:37:05,320 --> 00:37:08,530
groter is as die ouer,
en alles aan die linkerkant

683
00:37:08,530 --> 00:37:10,035
minder is as die ouer.

684
00:37:10,035 --> 00:37:15,690
En wat is 'n toets
vraag voor, so goed om te weet.

685
00:37:15,690 --> 00:37:19,500
So die manier waarop ons definieer dit,
Weereens, ons het nog 'n knoop.

686
00:37:19,500 --> 00:37:21,880
Dit lyk baie soortgelyk aan wat?

687
00:37:21,880 --> 00:37:28,336

688
00:37:28,336 --> 00:37:28,836
Dubbel

689
00:37:28,836 --> 00:37:29,320
>> Publiek: Gekoppel lyste

690
00:37:29,320 --> 00:37:31,100
>> Spreker 1: 'n dubbel gekoppel lys, reg?

691
00:37:31,100 --> 00:37:33,690
So as ons die plek van hierdie
met vorige en die volgende,

692
00:37:33,690 --> 00:37:35,670
dit sou 'n dubbel gekoppel lys wees.

693
00:37:35,670 --> 00:37:40,125
Maar in hierdie geval, het ons eintlik
het links en regs en dit is dit.

694
00:37:40,125 --> 00:37:41,500
Andersins, is dit presies dieselfde.

695
00:37:41,500 --> 00:37:43,374
Ons het nog steeds die element
jy soek,

696
00:37:43,374 --> 00:37:45,988
en jy moet net twee wysers
gaan net die volgende.

697
00:37:45,988 --> 00:37:49,210

698
00:37:49,210 --> 00:37:51,870
Ja, so binêre soek boom.

699
00:37:51,870 --> 00:37:57,665
As ons sien, alles op die
hier is groter than--

700
00:37:57,665 --> 00:37:59,850
of alles onmiddellik
aan die regterkant hier

701
00:37:59,850 --> 00:38:02,840
is groter as alles
hier is minder as.

702
00:38:02,840 --> 00:38:06,980

703
00:38:06,980 --> 00:38:14,000
>> So as ons om te soek deur dit
moet kyk baie naby aan binêre soek

704
00:38:14,000 --> 00:38:14,910
hier, reg?

705
00:38:14,910 --> 00:38:17,640
Behalwe in plaas van om te kyk
teen die helfte van die skikking,

706
00:38:17,640 --> 00:38:21,720
Ons is net op soek na die linker
kant of die regterkant van die boom.

707
00:38:21,720 --> 00:38:24,850
So raak dit 'n bietjie makliker, dink ek.

708
00:38:24,850 --> 00:38:29,300
>> So as jou wortel is NULL,
natuurlik is dit net vals.

709
00:38:29,300 --> 00:38:33,470
En as dit is daar, natuurlik, dit is waar.

710
00:38:33,470 --> 00:38:35,320
As dit is minder as ons soek die linkerkant.

711
00:38:35,320 --> 00:38:37,070
As dit is groter as,
Ons soek die reg.

712
00:38:37,070 --> 00:38:39,890
Dit is presies soos binêre soek,
net 'n ander datastruktuur

713
00:38:39,890 --> 00:38:40,600
wat ons gebruik.

714
00:38:40,600 --> 00:38:42,790
In plaas van 'n skikking,
dit is net 'n binêre boom.

715
00:38:42,790 --> 00:38:45,820

716
00:38:45,820 --> 00:38:48,090
>> OK, stapels.

717
00:38:48,090 --> 00:38:51,550
En ook, dit lyk asof ons
dalk 'n bietjie van die tyd.

718
00:38:51,550 --> 00:38:54,460
As ons dit doen, ek is gelukkig om te gaan
oor enige van hierdie weer.

719
00:38:54,460 --> 00:38:56,856
OK, so stapels.

720
00:38:56,856 --> 00:39:02,695
Is daar iemand onthou wat stacks--
enige eienskappe van 'n stapel?

721
00:39:02,695 --> 00:39:05,550

722
00:39:05,550 --> 00:39:10,400
>> OK, so die meeste van ons, dink ek,
eet in die eetkamer halls--

723
00:39:10,400 --> 00:39:13,100
soveel as wat ons mag nie graag.

724
00:39:13,100 --> 00:39:16,900
Maar natuurlik, kan jy dink van 'n stapel
letterlik net so 'n stapel van bak

725
00:39:16,900 --> 00:39:18,460
of 'n stapel van dinge.

726
00:39:18,460 --> 00:39:21,820
En wat is belangrik
om te besef is dat dit

727
00:39:21,820 --> 00:39:26,850
something-- die kenmerkende
dat ons noem dit deur- is LIFO.

728
00:39:26,850 --> 00:39:28,450
Is daar iemand wat weet wat dit staan ​​vir?

729
00:39:28,450 --> 00:39:29,070
Mmhmm?

730
00:39:29,070 --> 00:39:30,650
>> Publiek: Laaste in, eerste uit.

731
00:39:30,650 --> 00:39:32,250
>> Spreker 1: Right, die laaste in, eerste uit.

732
00:39:32,250 --> 00:39:36,585
So as ons weet, as ons stapel dinge
up, die maklikste ding om te gryp off--

733
00:39:36,585 --> 00:39:39,570
en miskien die enigste ding wat ons kan gryp
af as ons stapel is 'n groot enough--

734
00:39:39,570 --> 00:39:40,850
is dat top element.

735
00:39:40,850 --> 00:39:43,460
Dus, wat is op
last-- soos ons hier sien,

736
00:39:43,460 --> 00:39:46,370
alles is gedruk
op die meeste recently-- is

737
00:39:46,370 --> 00:39:51,160
gaan na die eerste wees
ding wat ons pop af, OK?

738
00:39:51,160 --> 00:39:56,324
>> So wat ons hier het is '
'n ander typedef struct.

739
00:39:56,324 --> 00:39:58,740
Dit is regtig net graag 'n
crash kursus in die data struktuur,

740
00:39:58,740 --> 00:40:01,650
so daar is 'n baie gegooi by julle.

741
00:40:01,650 --> 00:40:02,540
Ek weet nie.

742
00:40:02,540 --> 00:40:04,970
So nog 'n struct.

743
00:40:04,970 --> 00:40:06,740
Yay vir strukture.

744
00:40:06,740 --> 00:40:16,660
>> En in hierdie geval, dit is 'n paar wyser
om 'n skikking wat 'n kapasiteit.

745
00:40:16,660 --> 00:40:20,830
Sodat hierdie verteenwoordig ons stapel
hier, soos ons werklike verskeidenheid

746
00:40:20,830 --> 00:40:22,520
dit is hou ons elemente.

747
00:40:22,520 --> 00:40:24,850
En dan is hier ons het 'n paar groot.

748
00:40:24,850 --> 00:40:31,170
>> En tipies, wat jy wil hou
spoor van hoe groot jou stapel

749
00:40:31,170 --> 00:40:36,180
want hoe dit gaan te laat
jy moet doen is as jy weet wat die grootte,

750
00:40:36,180 --> 00:40:39,170
dit laat jou te sê,
OK, ek by kapasiteit?

751
00:40:39,170 --> 00:40:40,570
Kan ek iets byvoeg?

752
00:40:40,570 --> 00:40:44,650
En dit ook vertel
waar die top van jou stapel

753
00:40:44,650 --> 00:40:48,180
so jy weet wat jy
eintlik kan opstyg.

754
00:40:48,180 --> 00:40:51,760
En dit is eintlik gaan
'n bietjie meer duidelik.

755
00:40:51,760 --> 00:40:57,350
>> So vir stoot, een ding, as jy
ooit druk te implementeer,

756
00:40:57,350 --> 00:41:01,330
as ek net sê, jou
stapel het 'n beperkte grootte, reg?

757
00:41:01,330 --> 00:41:03,990
Ons verskeidenheid het 'n paar kapasiteit.

758
00:41:03,990 --> 00:41:04,910
Dit is 'n skikking.

759
00:41:04,910 --> 00:41:08,930
Dit is 'n vaste grootte, sodat ons nodig het om te
seker te maak dat ons nie meer om

760
00:41:08,930 --> 00:41:11,950
in ons verskeidenheid as wat ons
eintlik ruimte vir.

761
00:41:11,950 --> 00:41:16,900
>> So wanneer jy skep 'n druk
funksie, die eerste ding wat jy doen is om te sê, OK,

762
00:41:16,900 --> 00:41:18,570
ek het ruimte in my stapel?

763
00:41:18,570 --> 00:41:23,330
Want as ek dit nie doen nie, jammer,
Ek kan nie slaan jou element.

764
00:41:23,330 --> 00:41:28,980
As ek dit doen, dan is jy wil op te slaan
dit aan die bokant van die stapel, reg?

765
00:41:28,980 --> 00:41:31,325
>> En dit is hoekom ons
spoor van ons grootte te hou.

766
00:41:31,325 --> 00:41:35,290
As ons nie tred hou van ons grootte nie,
Ons weet nie waar om dit te sit.

767
00:41:35,290 --> 00:41:39,035
Ons weet nie hoe baie dinge
in ons verskeidenheid reeds.

768
00:41:39,035 --> 00:41:41,410
Soos duidelik daar is maniere
dat miskien jy kan dit doen.

769
00:41:41,410 --> 00:41:44,610
Jy kan alles inisialiseer te null
en dan gaan vir die jongste NULL,

770
00:41:44,610 --> 00:41:47,950
maar 'n baie makliker ding is net
om te sê, OK, hou van grootte.

771
00:41:47,950 --> 00:41:51,840
Soos ek weet ek het vier elemente
in my skikking, so die volgende ding

772
00:41:51,840 --> 00:41:55,930
wat ons aan, ons is
gaan om te slaan op indeks 4.

773
00:41:55,930 --> 00:42:00,940
En dan, natuurlik, beteken dit dat
jy het suksesvol gestoot iets

774
00:42:00,940 --> 00:42:03,320
op jou stapel, jy
wil die grootte te verhoog

775
00:42:03,320 --> 00:42:08,880
sodat jy weet waar jy is so
dat jy meer dinge kan druk op.

776
00:42:08,880 --> 00:42:12,730
>> So as ons probeer om te pop
iets uit die stapel,

777
00:42:12,730 --> 00:42:16,072
wat dalk die eerste ding wees
wat ons wil om te kyk vir?

778
00:42:16,072 --> 00:42:18,030
Jy probeer om te neem
iets uit jou stapel.

779
00:42:18,030 --> 00:42:21,710

780
00:42:21,710 --> 00:42:24,781
Is jy seker daar is
iets in jou stapel?

781
00:42:24,781 --> 00:42:25,280
No.

782
00:42:25,280 --> 00:42:26,894
So, wat sou ons wil om te kyk?

783
00:42:26,894 --> 00:42:27,810
>> Publiek: [onhoorbaar].

784
00:42:27,810 --> 00:42:29,880
Spreker 1: Check vir die grootte?

785
00:42:29,880 --> 00:42:31,840
Grootte.

786
00:42:31,840 --> 00:42:38,520
So ons wil om te kyk om te sien of
ons grootte is groter as 0, OK?

787
00:42:38,520 --> 00:42:44,970
En as dit is, dan wil ons te verminder
ons grootte deur 0 en terugkeer nie.

788
00:42:44,970 --> 00:42:45,840
Hoekom?

789
00:42:45,840 --> 00:42:49,950
>> In die eerste een wat ons was
stoot, ons stoot dit

790
00:42:49,950 --> 00:42:52,460
op die grootte en dan opgedateer grootte.

791
00:42:52,460 --> 00:42:57,850
In hierdie geval, ons decrementing grootte
en dan neem dit af, pluk dit

792
00:42:57,850 --> 00:42:58,952
van ons verskeidenheid.

793
00:42:58,952 --> 00:42:59,826
Hoekom kan ons dit doen?

794
00:42:59,826 --> 00:43:04,800

795
00:43:04,800 --> 00:43:11,811
So as ek een ding op my stapel,
Wat sou my grootte op daardie punt wees?

796
00:43:11,811 --> 00:43:13,140
1.

797
00:43:13,140 --> 00:43:15,180
>> En waar is element 1 gestoor?

798
00:43:15,180 --> 00:43:17,621
Op watter indeks?

799
00:43:17,621 --> 00:43:18,120
Publiek: 0.

800
00:43:18,120 --> 00:43:19,060
Spreker 1: 0.

801
00:43:19,060 --> 00:43:22,800
So in hierdie geval, ons
altyd nodig om te maak sure--

802
00:43:22,800 --> 00:43:27,630
in plaas van die terugkeer
grootte minus 1, want ons

803
00:43:27,630 --> 00:43:31,730
weet dat ons element is
gaan op 1 minder geberg word

804
00:43:31,730 --> 00:43:34,705
alles wat ons grootte is, is hierdie
net sorg nie.

805
00:43:34,705 --> 00:43:36,080
Dit is 'n bietjie meer elegante manier.

806
00:43:36,080 --> 00:43:41,220
En ons het net decrement ons
grootte en dan terug grootte.

807
00:43:41,220 --> 00:43:42,330
Mmhmm?

808
00:43:42,330 --> 00:43:45,300
>> Publiek: Ek dink net in die algemeen,
hoekom sou hierdie data struktuur

809
00:43:45,300 --> 00:43:47,800
voordelig wees?

810
00:43:47,800 --> 00:43:50,660
>> Spreker 1: Dit hang af van jou konteks.

811
00:43:50,660 --> 00:43:57,420
So vir 'n paar van die teorie,
As jy werk with-- OK,

812
00:43:57,420 --> 00:44:02,750
Laat my sien of daar is 'n voordelige een
wat voordelig is vir meer as buite

813
00:44:02,750 --> 00:44:05,420
CS.

814
00:44:05,420 --> 00:44:15,780
Met stapels, enige tyd wat jy nodig het
spoor van iets te hou wat

815
00:44:15,780 --> 00:44:20,456
is die mees onlangs bygevoeg is wanneer
jy gaan om te wil 'n stapel te gebruik.

816
00:44:20,456 --> 00:44:24,770
>> En ek kan nie dink aan 'n goeie
voorbeeld van wat nou.

817
00:44:24,770 --> 00:44:29,955
Maar wanneer die mees onlangse
ding is vir jou die belangrikste,

818
00:44:29,955 --> 00:44:31,705
dit is wanneer 'n stapel
gaan nuttig te wees.

819
00:44:31,705 --> 00:44:35,797

820
00:44:35,797 --> 00:44:39,330
Ek probeer om te dink as
daar is 'n goeie een vir hierdie.

821
00:44:39,330 --> 00:44:43,720
As ek dink aan 'n goeie voorbeeld in die volgende
20 minute, ek sal beslis vir jou sê.

822
00:44:43,720 --> 00:44:49,455
>> Maar algehele, as daar enigiets is,
soos ek gesê het die meeste, waar die meeste onlangse

823
00:44:49,455 --> 00:44:52,470
is baie belangrik, dis
waar 'n stapel kom in die spel.

824
00:44:52,470 --> 00:44:58,860
Terwyl toue is soort van die teenoorgestelde.

825
00:44:58,860 --> 00:44:59,870
En al die klein honde.

826
00:44:59,870 --> 00:45:00,890
Is dit nie die groot, reg?

827
00:45:00,890 --> 00:45:03,299
Ek voel soos ek moet
net 'n bunny video

828
00:45:03,299 --> 00:45:05,090
reg in die middel van die
artikel vir julle

829
00:45:05,090 --> 00:45:08,870
want dit is 'n intense afdeling.

830
00:45:08,870 --> 00:45:10,480
>> So 'n tou.

831
00:45:10,480 --> 00:45:12,710
Basies 'n tou is soos 'n lyn.

832
00:45:12,710 --> 00:45:15,780
Julle ek is seker gebruik hierdie alledaagse,
net soos in ons eetsale.

833
00:45:15,780 --> 00:45:18,160
So ons het om te gaan in
en kry ons bak, ek is

834
00:45:18,160 --> 00:45:21,260
seker jy het om te wag in lyn
te krap of kry jou kos.

835
00:45:21,260 --> 00:45:24,650
>> So het die verskil hier
is dat dit EIEU.

836
00:45:24,650 --> 00:45:30,090
So as LIFO was laaste in, eerste
uit EIEU is die eerste in, eerste uit.

837
00:45:30,090 --> 00:45:33,400
So dit is waar wat jy sit
op die eerste is jou belangrikste.

838
00:45:33,400 --> 00:45:35,540
So, as jy wag
in 'n line-- kan jy

839
00:45:35,540 --> 00:45:39,130
dink as jy na
gaan kry die nuwe iPhone

840
00:45:39,130 --> 00:45:42,800
en dit was 'n stapel waar die
laaste persoon in lyn het dit die eerste keer,

841
00:45:42,800 --> 00:45:44,160
mense sal mekaar doodmaak.

842
00:45:44,160 --> 00:45:49,800
>> So EIEU, ons is almal baie bekend
in die werklike wêreld hier,

843
00:45:49,800 --> 00:45:54,930
en dit alles het te doen met eintlik
soort herskep hierdie hele lyn

844
00:45:54,930 --> 00:45:56,900
en toustaan ​​struktuur.

845
00:45:56,900 --> 00:46:02,390
So terwyl met die stapel,
Ons het druk en pop.

846
00:46:02,390 --> 00:46:06,440
Met 'n tou, ons het
enqueue en dequeue.

847
00:46:06,440 --> 00:46:10,910
So enqueue beteken basies
sit dit op die rug,

848
00:46:10,910 --> 00:46:13,680
en dequeue middel neem
af van die voorkant.

849
00:46:13,680 --> 00:46:18,680
So ons data struktuur is 'n
bietjie meer ingewikkeld.

850
00:46:18,680 --> 00:46:21,060
Ons het 'n tweede ding om tred te hou.

851
00:46:21,060 --> 00:46:25,950
>> So sonder die kop, hierdie
is presies 'n stapel, reg?

852
00:46:25,950 --> 00:46:27,900
Dit is dieselfde struktuur as 'n stapel.

853
00:46:27,900 --> 00:46:32,480
Die enigste ding wat anders is, is ons nou
het die hoof, wat doen wat jy dink

854
00:46:32,480 --> 00:46:34,272
gaan om tred te hou?

855
00:46:34,272 --> 00:46:35,510
>> Publiek: Die eerste een.

856
00:46:35,510 --> 00:46:38,685
>> Spreker 1: Right, die
eerste ding wat ons in.

857
00:46:38,685 --> 00:46:41,130
Die hoof van ons ry.

858
00:46:41,130 --> 00:46:42,240
Wie is die eerste in die lyn.

859
00:46:42,240 --> 00:46:45,300

860
00:46:45,300 --> 00:46:49,420
Alle reg, so as ons dit doen enqueue.

861
00:46:49,420 --> 00:46:52,720

862
00:46:52,720 --> 00:46:55,920
Weer, met enige van
hierdie data strukture,

863
00:46:55,920 --> 00:46:59,760
omdat ons te doen het met 'n skikking,
ons nodig het om te kyk of ons 'n ruimte.

864
00:46:59,760 --> 00:47:03,290
>> Dit is soort van soos vir my vertel
julle ouens, as jy 'n lêer oop te maak,

865
00:47:03,290 --> 00:47:04,760
wat jy nodig het om te kyk vir nul.

866
00:47:04,760 --> 00:47:08,330
Met enige van hierdie stapels
en toue, moet jy

867
00:47:08,330 --> 00:47:13,420
om te sien of daar is ruimte, want ons is
doen met 'n vaste grootte skikking,

868
00:47:13,420 --> 00:47:16,030
soos ons sien here-- 0, 1 al tot 5.

869
00:47:16,030 --> 00:47:20,690
So wat ons doen in daardie geval is tjek
om te sien of ons nog plek.

870
00:47:20,690 --> 00:47:23,110
Is ons grootte minder as kapasiteit?

871
00:47:23,110 --> 00:47:28,480
>> As dit so is, moet ons dit op te slaan op
die stert en ons grootte werk.

872
00:47:28,480 --> 00:47:30,250
So wat kan die stert wees in hierdie geval?

873
00:47:30,250 --> 00:47:32,360
Dit is nie duidelik uitgeskryf.

874
00:47:32,360 --> 00:47:33,380
Hoe sal ons dit stoor?

875
00:47:33,380 --> 00:47:34,928
Wat sou die stert wees?

876
00:47:34,928 --> 00:47:38,600

877
00:47:38,600 --> 00:47:40,190
>> So laat loop deur middel van hierdie voorbeeld.

878
00:47:40,190 --> 00:47:44,590
So, dit is 'n verskeidenheid van grootte 6, reg?

879
00:47:44,590 --> 00:47:49,220
En ons het op die oomblik, ons grootte is 5.

880
00:47:49,220 --> 00:47:55,240
En wanneer ons dit in, dit gaan
om te gaan in die vyfde indeks, reg?

881
00:47:55,240 --> 00:47:57,030
So slaan op die stert.

882
00:47:57,030 --> 00:48:05,600
>> Nog 'n manier stert te skryf wil net
wees ons opgestel by indeks van grootte, reg?

883
00:48:05,600 --> 00:48:07,560
Dit is die grootte 5.

884
00:48:07,560 --> 00:48:11,490
Volgende ding wat gaan om te gaan in 5.

885
00:48:11,490 --> 00:48:12,296
Cool?

886
00:48:12,296 --> 00:48:13,290
OK.

887
00:48:13,290 --> 00:48:16,350
Dit raak 'n bietjie meer ingewikkeld
wanneer ons begin geknoei met die kop.

888
00:48:16,350 --> 00:48:17,060
Ja?

889
00:48:17,060 --> 00:48:20,090
>> Publiek: Beteken dit dat ons
sou 'n skikking verklaar het dat

890
00:48:20,090 --> 00:48:23,880
was vyf elemente lang en
dan is ons voeg op dit?

891
00:48:23,880 --> 00:48:24,730
>> Spreker 1: No.

892
00:48:24,730 --> 00:48:27,560
So in hierdie geval, dit is 'n stapel.

893
00:48:27,560 --> 00:48:31,760
Dit sou verklaar word
as 'n verskeidenheid van grootte 6.

894
00:48:31,760 --> 00:48:37,120
En in hierdie geval, ons
net een spasie links.

895
00:48:37,120 --> 00:48:42,720
>> OK, so een ding is in hierdie
geval, as ons kop is by 0,

896
00:48:42,720 --> 00:48:45,270
dan moet ons net dit kan byvoeg by grootte.

897
00:48:45,270 --> 00:48:51,020
Maar dit raak 'n bietjie moeiliker
want eintlik, het hulle

898
00:48:51,020 --> 00:48:52,840
het nie 'n skyfie
vir hierdie, so ek gaan

899
00:48:52,840 --> 00:48:56,670
een te trek, want dit is nie
heeltemal so eenvoudig as jy

900
00:48:56,670 --> 00:48:59,230
begin om ontslae te raak van die dinge.

901
00:48:59,230 --> 00:49:03,920
So terwyl met 'n stapel
jy net ooit

902
00:49:03,920 --> 00:49:08,920
bekommerd te wees oor wat die grootte is
wanneer jy iets toe te voeg aan,

903
00:49:08,920 --> 00:49:15,710
met 'n tou moet jy ook te maak
seker dat jou kop is verantwoordelik vir,

904
00:49:15,710 --> 00:49:20,760
omdat 'n cool ding oor toue
is dat as jy nie by die kapasiteit,

905
00:49:20,760 --> 00:49:23,040
jy kan eintlik maak dit draai om.

906
00:49:23,040 --> 00:49:28,810
>> OK, so een thing-- O,
dit is verskriklik kryt.

907
00:49:28,810 --> 00:49:31,815
Een ding om te oorweeg is die geval nie.

908
00:49:31,815 --> 00:49:35,514

909
00:49:35,514 --> 00:49:37,140
Ons sal net doen vyf.

910
00:49:37,140 --> 00:49:41,810
OK, so ons gaan
sê die hoof is hier.

911
00:49:41,810 --> 00:49:46,140
Dit is 0, 1, 2, 3, 4.

912
00:49:46,140 --> 00:49:54,210
>> Die hoof is daar, en
asseblief dinge in hulle.

913
00:49:54,210 --> 00:49:58,340
En ons wil iets in te voeg, reg?

914
00:49:58,340 --> 00:50:01,170
So die ding wat ons nodig het om te
weet, is dat die kop is altyd

915
00:50:01,170 --> 00:50:05,620
gaan op hierdie manier te beweeg en
dan loop terug rond, OK?

916
00:50:05,620 --> 00:50:10,190
>> So hierdie tou het ruimte, reg?

917
00:50:10,190 --> 00:50:13,950
Dit het ruimte in die begin,
soort van die teenoorgestelde hiervan.

918
00:50:13,950 --> 00:50:17,920
So wat ons moet doen is om ons
moet die stert te bereken.

919
00:50:17,920 --> 00:50:20,530
As jy weet dat jou
hoof het nie beweeg nie, stert

920
00:50:20,530 --> 00:50:24,630
is net jou opgestel by
Die indeks van die grootte.

921
00:50:24,630 --> 00:50:30,000
>> Maar in werklikheid, as jy met 'n tou,
jou kop is waarskynlik opgedateer.

922
00:50:30,000 --> 00:50:33,890
So, wat jy hoef te doen is
eintlik bereken die stert.

923
00:50:33,890 --> 00:50:39,990
So wat ons doen is om hierdie formule
hier, wat ek gaan om jou te laat

924
00:50:39,990 --> 00:50:42,680
ouens dink oor, en
dan sal ons daaroor praat.

925
00:50:42,680 --> 00:50:49,567

926
00:50:49,567 --> 00:50:50,400
So is dit kapasiteit.

927
00:50:50,400 --> 00:50:55,890

928
00:50:55,890 --> 00:50:59,660
>> So dit sal eintlik
gee jou 'n manier om dit te doen nie.

929
00:50:59,660 --> 00:51:03,205

930
00:51:03,205 --> 00:51:04,330
Want in hierdie geval, wat?

931
00:51:04,330 --> 00:51:09,205
Ons hoof is op 1, ons grootte is 4.

932
00:51:09,205 --> 00:51:11,760

933
00:51:11,760 --> 00:51:18,490
As ons mod wat deur 5, kry ons 0,
en dit is waar ons moet invoer nie.

934
00:51:18,490 --> 00:51:23,320

935
00:51:23,320 --> 00:51:26,080
>> So dan in die volgende geval,
As ons dit doen,

936
00:51:26,080 --> 00:51:33,390
ons sê, OK, laat ons dequeue iets.

937
00:51:33,390 --> 00:51:34,390
Ons dequeue hierdie.

938
00:51:34,390 --> 00:51:37,740
Ons neem hierdie element, reg?

939
00:51:37,740 --> 00:51:47,930
>> En nou is ons kop is hier wys,
en ons wil by te voeg in 'n ander ding.

940
00:51:47,930 --> 00:51:52,470
Dit is basies die
agterkant van ons lyn, reg?

941
00:51:52,470 --> 00:51:55,450
Toue kan draai om die skikking.

942
00:51:55,450 --> 00:51:57,310
Dit is een van die belangrikste verskille.

943
00:51:57,310 --> 00:51:58,780
Stapels, kan jy dit nie doen nie.

944
00:51:58,780 --> 00:52:01,140
>> Met toue, kan jy
want al wat saak maak

945
00:52:01,140 --> 00:52:03,940
is dat jy weet wat
mees onlangs bygevoeg.

946
00:52:03,940 --> 00:52:10,650
Want alles gaan in gevoeg word
hierdie linkswaartse rigting, in hierdie geval,

947
00:52:10,650 --> 00:52:16,480
en dan draai rond, kan jy
voortgaan om in die nuwe elemente

948
00:52:16,480 --> 00:52:18,830
aan die voorkant van die skikking
want dit is nie regtig

949
00:52:18,830 --> 00:52:20,640
die voorkant van die skikking nie.

950
00:52:20,640 --> 00:52:26,320
Jy kan dink van die begin van die
skikking as waar jou kop eintlik is.

951
00:52:26,320 --> 00:52:29,710
>> So hierdie formule is hoe
jy bereken jou stert.

952
00:52:29,710 --> 00:52:32,780

953
00:52:32,780 --> 00:52:35,610
Doen wat sin maak?

954
00:52:35,610 --> 00:52:36,110
OK.

955
00:52:36,110 --> 00:52:39,400

956
00:52:39,400 --> 00:52:44,040
OK, dequeue, en dan
julle ouens het 10 minute

957
00:52:44,040 --> 00:52:48,840
my enige verduidelik vrae te vra
wat jy wil, want ek weet dit is gek.

958
00:52:48,840 --> 00:52:51,980
>> Alle reg, sodat in dieselfde way--
Ek weet nie of julle opgemerk,

959
00:52:51,980 --> 00:52:53,450
maar CS is al oor die patrone.

960
00:52:53,450 --> 00:52:57,370
Dinge is pretty much die
dieselfde, net met 'n klein tweaked.

961
00:52:57,370 --> 00:52:58,950
So dieselfde ding hier.

962
00:52:58,950 --> 00:53:04,040
Ons moet kyk na as ons eintlik sien
iets in ons ry, reg?

963
00:53:04,040 --> 00:53:05,960
Sê, OK, is ons grootte groter as 0?

964
00:53:05,960 --> 00:53:06,730
Cool.

965
00:53:06,730 --> 00:53:10,690
>> As ons dit doen, dan beweeg ons ons kop, wat
is wat ek net hier gedemonstreer.

966
00:53:10,690 --> 00:53:13,870
Ons werk ons ​​hoof een te wees.

967
00:53:13,870 --> 00:53:18,390
En dan het ons decrement ons
grootte en die standaard van die element.

968
00:53:18,390 --> 00:53:21,000

969
00:53:21,000 --> 00:53:26,250
>> Daar is baie meer konkrete
kode op study.cs50.net,

970
00:53:26,250 --> 00:53:29,440
en ek raai gaan
deur dit as jy tyd het,

971
00:53:29,440 --> 00:53:30,980
selfs al is dit net 'n pseudo-kode.

972
00:53:30,980 --> 00:53:35,980
En as julle wil praat deur
wat met my een op een, laat my asseblief

973
00:53:35,980 --> 00:53:37,500
weet.

974
00:53:37,500 --> 00:53:38,770
Ek sal bly wees om te wees.

975
00:53:38,770 --> 00:53:42,720
Data strukture, indien
jy CS 124, sal jy

976
00:53:42,720 --> 00:53:47,830
weet dat data strukture kry baie
pret en dit is net die begin.

977
00:53:47,830 --> 00:53:50,350
>> So ek weet dit is moeilik.

978
00:53:50,350 --> 00:53:51,300
Dit is OK.

979
00:53:51,300 --> 00:53:52,410
Ons sukkel.

980
00:53:52,410 --> 00:53:53,630
Ek nog steeds doen.

981
00:53:53,630 --> 00:53:56,660
So te veel bekommerd wees nie oor dit.

982
00:53:56,660 --> 00:54:02,390
>> Maar dit is basies jou
crash kursus in die data strukture.

983
00:54:02,390 --> 00:54:03,400
Ek weet dit is 'n baie.

984
00:54:03,400 --> 00:54:06,860
Is daar enigiets wat ons
wil om te gaan oor weer?

985
00:54:06,860 --> 00:54:09,400
Enigiets wat ons wil om te praat deur middel van?

986
00:54:09,400 --> 00:54:10,060
Ja?

987
00:54:10,060 --> 00:54:16,525
>> Publiek: Vir daardie voorbeeld, so
die nuwe stert is by 0 oor dit?

988
00:54:16,525 --> 00:54:17,150
Spreker 1: Ja.

989
00:54:17,150 --> 00:54:18,230
Publiek: OK.

990
00:54:18,230 --> 00:54:24,220
So dan gaan deur,
jy wil hê 1 plus 4 or--

991
00:54:24,220 --> 00:54:27,671
>> Spreker 1: So jy sê,
wanneer ons wil gaan doen dit weer?

992
00:54:27,671 --> 00:54:28,296
Publiek: Ja.

993
00:54:28,296 --> 00:54:38,290
So, as jy besyfering out-- waar is
jy die berekening van die stert van daardie?

994
00:54:38,290 --> 00:54:44,260
>> Spreker 1: So het die stert
was in-- Ek verander nie.

995
00:54:44,260 --> 00:54:52,010
So in hierdie voorbeeld hier, dit was
die skikking ons kyk na, OK?

996
00:54:52,010 --> 00:54:54,670
Dus het ons dinge in 1, 2, 3 en 4.

997
00:54:54,670 --> 00:55:05,850
So het ons ons kop is gelyk aan 1 by
hierdie punt, en ons grootte is gelyk aan 4

998
00:55:05,850 --> 00:55:07,050
Op hierdie punt, reg?

999
00:55:07,050 --> 00:55:08,960
>> Julle almal is dit eens dat dit die geval is?

1000
00:55:08,960 --> 00:55:14,620
So ons doen om die kop, plus die grootte, wat
gee ons 5, en dan moet ons mod deur 5.

1001
00:55:14,620 --> 00:55:20,690
Ons kry 0, wat vertel ons dat 0 is
waar is ons stert, waar ons die ruimte.

1002
00:55:20,690 --> 00:55:22,010
>> Publiek: Wat is 'n pet?

1003
00:55:22,010 --> 00:55:23,520
>> Spreker 1: Die kapasiteit.

1004
00:55:23,520 --> 00:55:24,020
Jammer.

1005
00:55:24,020 --> 00:55:29,640
So dit is die grootte van jou skikking.

1006
00:55:29,640 --> 00:55:35,210

1007
00:55:35,210 --> 00:55:36,047
Ja?

1008
00:55:36,047 --> 00:55:39,210
>> Publiek: [onhoorbaar] voor
ons terugkeer van die element?

1009
00:55:39,210 --> 00:55:46,270
>> Spreker 1: So beweeg ons die
kop of die standaard van die oomblik?

1010
00:55:46,270 --> 00:55:52,680
So as ons beweeg een, decrement die grootte?

1011
00:55:52,680 --> 00:55:54,150
Hou op.

1012
00:55:54,150 --> 00:55:55,770
Ek het beslis vergeet 'n ander.

1013
00:55:55,770 --> 00:56:00,646

1014
00:56:00,646 --> 00:56:01,990
Toemaar.

1015
00:56:01,990 --> 00:56:04,980
Daar is nie 'n ander formule.

1016
00:56:04,980 --> 00:56:09,980
Ja, sou jy wil om terug te keer
die kop en dan beweeg dit terug.

1017
00:56:09,980 --> 00:56:13,270
>> Publiek: OK, want op hierdie
punt, die hoof was by 0,

1018
00:56:13,270 --> 00:56:18,452
en dan wat jy wil om terug te keer
indeks 0 en dan maak kop 1?

1019
00:56:18,452 --> 00:56:19,870
>> Spreker 1: Right.

1020
00:56:19,870 --> 00:56:22,820
Ek dink daar is 'n ander
formule soort van soos hierdie.

1021
00:56:22,820 --> 00:56:26,970
Ek het dit nie op die top van my kop
Ek wil nie hê jy moet die verkeerde een.

1022
00:56:26,970 --> 00:56:35,470
Maar ek dink dit is heeltemal geldig
sê, OK, slaan hierdie element-- wat

1023
00:56:35,470 --> 00:56:40,759
hoof se element is-- Trek jou
grootte, beweeg jou kop oor en terugkeer

1024
00:56:40,759 --> 00:56:41,800
wat dit ook al element is.

1025
00:56:41,800 --> 00:56:44,760
Dit is volkome geldig.

1026
00:56:44,760 --> 00:56:45,260
OK.

1027
00:56:45,260 --> 00:56:48,360

1028
00:56:48,360 --> 00:56:53,560
Ek voel soos hierdie is nie
soos die most-- jy nie

1029
00:56:53,560 --> 00:56:55,740
gaan hier uit te loop
soos, ja, ek weet drieë gedruk.

1030
00:56:55,740 --> 00:56:56,880
Ek het dit alles.

1031
00:56:56,880 --> 00:56:57,670
Dit is OK.

1032
00:56:57,670 --> 00:57:00,200
Ek belowe.

1033
00:57:00,200 --> 00:57:05,240
Maar data strukture is iets wat
dit neem baie tyd om gewoond te raak aan.

1034
00:57:05,240 --> 00:57:10,010
Waarskynlik een van die moeilikste
dinge, dink ek, in die kursus.

1035
00:57:10,010 --> 00:57:15,330
>> So dit is beslis neem
herhaling en soek at-- ek

1036
00:57:15,330 --> 00:57:20,050
het nie regtig weet gekoppel lyste
totdat ek het te veel met hulle,

1037
00:57:20,050 --> 00:57:22,550
in dieselfde manier as wat ek gedoen het nie
regtig verstaan ​​wysers

1038
00:57:22,550 --> 00:57:27,040
totdat ek het dit vir twee tot leer
jaar en doen my eie psets met dit.

1039
00:57:27,040 --> 00:57:28,990
Dit neem 'n baie van die herhaling en tyd.

1040
00:57:28,990 --> 00:57:32,600
En uiteindelik, sal dit soort klik.

1041
00:57:32,600 --> 00:57:36,320
>> Maar in die tussentyd, as jy 'n soort
van 'n hoë vlak van begrip van wat

1042
00:57:36,320 --> 00:57:39,321
doen dit, hul voor-
en cons-- is wat

1043
00:57:39,321 --> 00:57:41,820
ons regtig is geneig om te beklemtoon,
veral in die intro kursus.

1044
00:57:41,820 --> 00:57:45,511
Soos, hoekom sou ons gebruik
'n probeer om oor 'n skikking?

1045
00:57:45,511 --> 00:57:48,010
Soos wat die positiewe
en negatiewe van elkeen van daardie?

1046
00:57:48,010 --> 00:57:51,610
>> En die begrip van die trade-offs
tussen elk van hierdie strukture

1047
00:57:51,610 --> 00:57:54,910
is wat is baie meer belangrik nou.

1048
00:57:54,910 --> 00:57:58,140
Daar kan 'n gek wees
vraag of twee wat

1049
00:57:58,140 --> 00:58:03,710
gaan jou vra druk te implementeer of
implementeer pop of enqueue en dequeue.

1050
00:58:03,710 --> 00:58:07,340
Maar vir die grootste deel, met wat
hoër vlak van begrip en meer

1051
00:58:07,340 --> 00:58:09,710
van 'n intuïtiewe begrip is
meer belangrik as eintlik

1052
00:58:09,710 --> 00:58:11,250
in staat is om dit te implementeer.

1053
00:58:11,250 --> 00:58:14,880
>> Dit sou regtig awesome as almal van julle
kon uitgaan en gaan implementeer 'n drie,

1054
00:58:14,880 --> 00:58:19,720
Maar ons verstaan ​​dit is nie noodwendig
die mees redelike ding nou.

1055
00:58:19,720 --> 00:58:23,370
Maar jy kan in jou pset, as jy wil
te, en dan sal jy die praktyk kry,

1056
00:58:23,370 --> 00:58:27,200
en dan miskien sal jy
regtig verstaan ​​nie.

1057
00:58:27,200 --> 00:58:27,940
Ja?

1058
00:58:27,940 --> 00:58:30,440
>> Publiek: OK, so watter is
ons bedoel is om te gebruik in die pset?

1059
00:58:30,440 --> 00:58:31,916
Het ek nie een van hulle te gebruik?

1060
00:58:31,916 --> 00:58:32,540
Spreker 1: Ja.

1061
00:58:32,540 --> 00:58:34,199
So jy het jou keuse.

1062
00:58:34,199 --> 00:58:36,740
Ek dink in hierdie geval, kan ons
praat oor die pset 'n bietjie

1063
00:58:36,740 --> 00:58:40,480
want ek het deur middel van hierdie.

1064
00:58:40,480 --> 00:58:47,779
So in jou pset, moet jy jou
keuse van drieë of hash tabelle.

1065
00:58:47,779 --> 00:58:49,570
Sommige mense sal probeer
en gebruik bloei filters,

1066
00:58:49,570 --> 00:58:51,840
maar diegene tegnies nie korrek is nie.

1067
00:58:51,840 --> 00:58:55,804
As gevolg van hul probabilistiese natuur,
hulle gee vals positiewes soms.

1068
00:58:55,804 --> 00:58:57,095
Hulle is cool kyk na, al is.

1069
00:58:57,095 --> 00:58:59,030
Raai soek
by hulle ten minste.

1070
00:58:59,030 --> 00:59:03,260
Maar jy moet jou keuse
tussen 'n hash tafel en 'n drie gedruk.

1071
00:59:03,260 --> 00:59:06,660
En wat gaan om te wees waar
jy laai in jou woordeboek.

1072
00:59:06,660 --> 00:59:09,230
>> En jy sal nodig het om te kies
jou hash funksie,

1073
00:59:09,230 --> 00:59:13,420
wat jy nodig het om van te kies hoeveel
emmers wat jy het, en dit sal wissel.

1074
00:59:13,420 --> 00:59:17,440
Soos as jy meer emmers,
miskien sal dit vinniger te hardloop.

1075
00:59:17,440 --> 00:59:22,790
Maar miskien is jy mors
baie ruimte op die manier, al is.

1076
00:59:22,790 --> 00:59:26,320
Jy het dit om uit te vind.

1077
00:59:26,320 --> 00:59:27,140
Mmhmm?

1078
00:59:27,140 --> 00:59:29,875
>> Publiek: Jy het gesê voor daardie
ons kan gebruik om ander hash funksies,

1079
00:59:29,875 --> 00:59:31,750
dat ons nie hoef te
'n hash funksie?

1080
00:59:31,750 --> 00:59:32,666
>> Spreker 1: Ja, reg.

1081
00:59:32,666 --> 00:59:38,150
So letterlik vir jou hash funksie,
soos Google "hash funksie"

1082
00:59:38,150 --> 00:59:40,770
en kyk vir 'n paar koel kinders.

1083
00:59:40,770 --> 00:59:43,250
Jy is nie verwag om te bou
jou eie hash funksies.

1084
00:59:43,250 --> 00:59:46,100
Mense spandeer hul
verhandelings op hierdie dinge.

1085
00:59:46,100 --> 00:59:50,250
>> So moenie bekommerd wees oor die bou van jou eie.

1086
00:59:50,250 --> 00:59:53,350
Vind 'n aanlyn te begin.

1087
00:59:53,350 --> 00:59:56,120
Sommige van hulle wat jy hoef te
'n bietjie te manipuleer

1088
00:59:56,120 --> 00:59:59,430
om seker te maak terugkeer tipes ooreen
en noem maar op, so in die begin,

1089
00:59:59,430 --> 01:00:02,420
Ek sou raai die gebruik iets
baie maklik dat ons dalk net

1090
01:00:02,420 --> 01:00:04,680
hashes op die eerste brief.

1091
01:00:04,680 --> 01:00:08,760
En dan wanneer jy dit werk,
waarin 'n koeler hash funksie.

1092
01:00:08,760 --> 01:00:09,260
Mmhmm?

1093
01:00:09,260 --> 01:00:13,020
>> Publiek: Sou 'n probeer wees of
doeltreffende, maar net harder te, like--

1094
01:00:13,020 --> 01:00:15,880
>> Spreker 1: So 'n drie, dink ek,
is intuïtief moeilik om te implementeer

1095
01:00:15,880 --> 01:00:18,310
maar is baie vinnig.

1096
01:00:18,310 --> 01:00:20,620
Maar neem meer ruimte.

1097
01:00:20,620 --> 01:00:25,270
Weereens, kan jy optimaliseer beide van diegene in
verskillende maniere en daar is maniere aan-

1098
01:00:25,270 --> 01:00:26,770
Publiek: Hoe is ons gegradeer op dit?

1099
01:00:26,770 --> 01:00:27,540
Is dit matter--

1100
01:00:27,540 --> 01:00:29,164
>> Spreker 1: So jy gegradeer normale manier.

1101
01:00:29,164 --> 01:00:31,330
Jy gaan gegradeer op die ontwerp.

1102
01:00:31,330 --> 01:00:36,020
Ongeag hoe jy dit doen, jy wil
maak seker dit is so elegant soos dit kan wees

1103
01:00:36,020 --> 01:00:38,610
en so doeltreffend as wat dit kan wees.

1104
01:00:38,610 --> 01:00:41,950
Maar as jy kies om 'n drie of hash
tafel, so lank as dit werk,

1105
01:00:41,950 --> 01:00:45,350
ons is gelukkig met dit.

1106
01:00:45,350 --> 01:00:48,370
En as jy iets gebruik wat hashes
op die eerste brief, dit is goed,

1107
01:00:48,370 --> 01:00:51,410
soos miskien soos ontwerp-wyse.

1108
01:00:51,410 --> 01:00:53,410
Ons is ook die bereiking van die
punt in hierdie semester--

1109
01:00:53,410 --> 01:00:55,340
Ek weet nie of jy
ouens noticed-- as jy

1110
01:00:55,340 --> 01:00:58,780
pset grade weier om 'n bietjie
as gevolg van die ontwerp en noem maar op,

1111
01:00:58,780 --> 01:00:59,900
dit is heeltemal fyn.

1112
01:00:59,900 --> 01:01:02,960
Dit is steeds op 'n punt waar jou
programme kry meer ingewikkeld.

1113
01:01:02,960 --> 01:01:04,830
Daar is meer plekke
jy kan verbeter op.

1114
01:01:04,830 --> 01:01:06,370
>> So dit is heeltemal normaal.

1115
01:01:06,370 --> 01:01:08,810
Dit is nie dat jy
doen erger op jou pset.

1116
01:01:08,810 --> 01:01:11,885
Dit is net ons om harder op jou nou.

1117
01:01:11,885 --> 01:01:13,732
Sodat almal die gevoel nie.

1118
01:01:13,732 --> 01:01:14,940
Ek het net gegradeer al jou psets.

1119
01:01:14,940 --> 01:01:16,490
Ek weet almal voel dit.

1120
01:01:16,490 --> 01:01:19,600
>> So moenie bekommerd wees oor dit wees nie.

1121
01:01:19,600 --> 01:01:23,580
En indien u enige vrae oor
voor psets of maniere waarop jy kan verbeter,

1122
01:01:23,580 --> 01:01:27,760
Ek probeer en kommentaar van die spesifieke
plekke, maar soms is dit laat

1123
01:01:27,760 --> 01:01:30,840
en ek moeg.

1124
01:01:30,840 --> 01:01:34,885
Is daar enige ander dinge
oor datastrukture?

1125
01:01:34,885 --> 01:01:37,510
Ek is seker dat julle nie regtig
wil om te praat oor hulle nie,

1126
01:01:37,510 --> 01:01:42,650
maar as daar is, ek is bly om te
gaan oor hulle, sowel as enigiets

1127
01:01:42,650 --> 01:01:45,580
vanaf lesing die afgelope
week of verlede week.

1128
01:01:45,580 --> 01:01:51,580
>> Ek weet verlede week was al hersiening, so
ons kan oor 'n paar hersiening oorgeslaan het

1129
01:01:51,580 --> 01:01:54,190
van lesing.

1130
01:01:54,190 --> 01:01:58,230
Enige ander vrae wat ek kan antwoord?

1131
01:01:58,230 --> 01:01:59,350
OK, alles reg.

1132
01:01:59,350 --> 01:02:02,400
Wel, jy ouens kry 15 minute vroeg.

1133
01:02:02,400 --> 01:02:08,370
>> Ek hoop dit was semi-nuttig ten minste,
en ek sal sien julle volgende week,

1134
01:02:08,370 --> 01:02:12,150
of Donderdag kantoorure.

1135
01:02:12,150 --> 01:02:15,285
Is daar versoeke vir snacks
vir volgende week, is dit die ding?

1136
01:02:15,285 --> 01:02:17,459
Omdat ek vandag lekkergoed vergeet.

1137
01:02:17,459 --> 01:02:19,750
En ek het lekkergoed laaste
week, maar dit was Columbus Day,

1138
01:02:19,750 --> 01:02:25,400
so daar was soos ses mense wat
het vier sakke van snoep vir hulself.

1139
01:02:25,400 --> 01:02:28,820
Ek kan bring Starbursts
weer as jy wil.

1140
01:02:28,820 --> 01:02:29,580
Starbursts?

1141
01:02:29,580 --> 01:02:32,250
OK, klink goed.

1142
01:02:32,250 --> 01:02:35,050
Het jy 'n groot dag, ouens.

1143
01:02:35,050 --> 01:02:39,510