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

2
00:00:00,500 --> 00:00:05,120
[MUSIC SPILLE]

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

4
00:00:12,026 --> 00:00:12,900
SPEAKER 1: All right.

5
00:00:12,900 --> 00:00:14,600
Alle velkommen tilbake til seksjonen.

6
00:00:14,600 --> 00:00:18,660
Jeg håper dere alle er vellykket
utvinnes fra din quiz

7
00:00:18,660 --> 00:00:19,510
fra forrige uke.

8
00:00:19,510 --> 00:00:22,564
Jeg vet det er litt gal til tider.

9
00:00:22,564 --> 00:00:25,230
Som jeg sa før, hvis du er
innenfor standardavviket,

10
00:00:25,230 --> 00:00:28,188
trenger egentlig ikke bekymre deg for det, spesielt
for en mindre komfortable delen.

11
00:00:28,188 --> 00:00:30,230
Det er omtrent der du skal være.

12
00:00:30,230 --> 00:00:32,850
>> Hvis du gjorde bra, så fantastisk.

13
00:00:32,850 --> 00:00:33,650
Kudos til deg.

14
00:00:33,650 --> 00:00:36,149
Og hvis du føler at du trenger
litt mer hjelp, kan du

15
00:00:36,149 --> 00:00:38,140
gjerne nå
ut til hvilken som helst av TFS.

16
00:00:38,140 --> 00:00:40,030
Vi er alle her for å hjelpe.

17
00:00:40,030 --> 00:00:40,960
>> Det er derfor vi underviser.

18
00:00:40,960 --> 00:00:44,550
Det er derfor jeg er her hver mandag for deg
gutter og på kontoret timer på torsdager.

19
00:00:44,550 --> 00:00:48,130
Så kan du gjerne gi meg beskjed
hvis du er bekymret for noe

20
00:00:48,130 --> 00:00:52,450
eller om det er noe på quiz
at du ville virkelig liker å ta opp.

21
00:00:52,450 --> 00:00:56,940
>> Så dagsorden for i dag er
alt om datastrukturer.

22
00:00:56,940 --> 00:01:01,520
Noen av disse er bare kommer til å være like
å få deg kjent med disse.

23
00:01:01,520 --> 00:01:04,870
Du kan ikke noensinne implementere
dem i denne klassen.

24
00:01:04,870 --> 00:01:08,690
Noen av dem du vil,
som for stavekontroll PSet.

25
00:01:08,690 --> 00:01:11,380
>> Du vil ha ditt valg
mellom hash tabeller og prøver.

26
00:01:11,380 --> 00:01:13,680
Så vi definitivt kommer over dem.

27
00:01:13,680 --> 00:01:18,690
Det kommer til å være definitivt mer av slag
fra et høyt nivå seksjon dag, skjønt,

28
00:01:18,690 --> 00:01:22,630
fordi det er mange av dem, og hvis
vi gikk inn i gjennomføringen detaljer

29
00:01:22,630 --> 00:01:26,490
på alle disse, ville vi ikke
selv komme gjennom lenkede lister

30
00:01:26,490 --> 00:01:28,520
og kanskje en liten bit av hash tabeller.

31
00:01:28,520 --> 00:01:31,200
>> Så bærer med meg.

32
00:01:31,200 --> 00:01:33,530
Vi kommer ikke til å gjøre
så mye som koder dette tidspunktet.

33
00:01:33,530 --> 00:01:36,870
Hvis du har noen spørsmål om det
eller du ønsker å se det implementert

34
00:01:36,870 --> 00:01:39,260
eller prøve det selv,
Jeg anbefaler

35
00:01:39,260 --> 00:01:44,250
kommer til å study.cs50.net, som
har eksempler på at alle disse.

36
00:01:44,250 --> 00:01:46,400
Det vil ha mine Powerpoints
med notatene som vi

37
00:01:46,400 --> 00:01:50,860
pleier å bruke, så vel som noen programmering
øvelser, spesielt for ting

38
00:01:50,860 --> 00:01:55,250
som lenkede lister og binære
trær stabler og pekepinner.

39
00:01:55,250 --> 00:01:59,590
Så litt mer høyt nivå, noe som
kan være fint for dere.

40
00:01:59,590 --> 00:02:01,320
>> Så med det, vil vi komme i gang.

41
00:02:01,320 --> 00:02:03,060
Og også, yes-- quizer.

42
00:02:03,060 --> 00:02:06,550
Jeg tror de fleste av dere som er i
min seksjon har dine quizzer,

43
00:02:06,550 --> 00:02:12,060
men noen kommer inn eller annen grunn
ikke gjør det, de er rett her i front.

44
00:02:12,060 --> 00:02:12,740
>> Så koblet lister.

45
00:02:12,740 --> 00:02:15,650
Jeg vet at denne typen går
å sikkerhets før quiz.

46
00:02:15,650 --> 00:02:17,940
Det var uken før
at vi har lært om dette.

47
00:02:17,940 --> 00:02:21,040
Men i dette tilfellet, vil vi bare
gå litt mer i dybden.

48
00:02:21,040 --> 00:02:25,900
>> Så hvorfor kan vi velge et
lenket liste over en rekke?

49
00:02:25,900 --> 00:02:27,130
Hva skiller dem?

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

51
00:02:27,630 --> 00:02:30,464
>> PUBLIKUM: Du kan utvide en koblet
liste versus en matrise er fast størrelse.

52
00:02:30,464 --> 00:02:31,171
SPEAKER 1: Høyre.

53
00:02:31,171 --> 00:02:33,970
En rekke har fast størrelse, mens en
lenket liste har en variabel størrelse.

54
00:02:33,970 --> 00:02:36,970
Så hvis vi ikke vet hvordan
mye vi ønsker å lagre,

55
00:02:36,970 --> 00:02:39,880
en lenket liste gir oss en god
måte å gjøre det fordi vi kan bare

56
00:02:39,880 --> 00:02:43,730
legge på en annen node og legge på
annen node og legge på en annen node.

57
00:02:43,730 --> 00:02:45,750
Men hva som kan være en trade-off?

58
00:02:45,750 --> 00:02:49,521
Er det noen som husker den trade-off
mellom arrays og koblede lister?

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

60
00:02:50,020 --> 00:02:51,460
>> PUBLIKUM: Du må
gå gjennom hele veien

61
00:02:51,460 --> 00:02:53,738
gjennom lenket liste
finne et element i en liste.

62
00:02:53,738 --> 00:02:55,570
I en matrise, kan du
bare finne et element.

63
00:02:55,570 --> 00:02:56,278
>> SPEAKER 1: Høyre.

64
00:02:56,278 --> 00:02:57,120
Så med arrays--

65
00:02:57,120 --> 00:02:58,500
>> PUBLIKUM: [uhørlig].

66
00:02:58,500 --> 00:03:01,090
>> SPEAKER 1: Med arrays, har vi
det som kalles tilfeldig tilgang.

67
00:03:01,090 --> 00:03:04,820
Betyr at hvis vi vil ha det som er
gang den femte punktet i en liste

68
00:03:04,820 --> 00:03:07,230
eller femte punktet i vår
array, kan vi bare ta tak i det.

69
00:03:07,230 --> 00:03:10,440
Hvis det er en lenket liste, har vi
å iterere gjennom, ikke sant?

70
00:03:10,440 --> 00:03:14,020
Så tilgang til et element i
en matrise er konstant tid,

71
00:03:14,020 --> 00:03:19,530
mens med en lenket liste ville det
mest sannsynlig være lineær tid fordi kanskje

72
00:03:19,530 --> 00:03:21,370
våre elementet er helt på slutten.

73
00:03:21,370 --> 00:03:23,446
Vi må søke gjennom alt.

74
00:03:23,446 --> 00:03:25,320
Så med alle disse dataene
strukturer vi skal

75
00:03:25,320 --> 00:03:29,330
til å tilbringe litt mer tid på,
hva er de positive og negative.

76
00:03:29,330 --> 00:03:31,480
Når kan vi ønsker å
bruke en over den andre?

77
00:03:31,480 --> 00:03:34,970
Og det er typen av
større ting å ta unna.

78
00:03:34,970 --> 00:03:40,140
>> Så vi har her
Definisjonen av en node.

79
00:03:40,140 --> 00:03:43,040
Det er som ett element i
vår lenket liste, ikke sant?

80
00:03:43,040 --> 00:03:46,180
Så vi er alle kjent
med våre typedef structs,

81
00:03:46,180 --> 00:03:47,980
som vi gikk over i en vurdering forrige gang.

82
00:03:47,980 --> 00:03:53,180
Det var i utgangspunktet bare skape
en annen datatype som vi kunne bruke.

83
00:03:53,180 --> 00:03:57,930
>> Og i dette tilfellet, er det noen node
som vil holde noen heltall i.

84
00:03:57,930 --> 00:04:00,210
Og så hva er den andre delen her?

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

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

87
00:04:05,677 --> 00:04:06,680
>> PUBLIKUM: [uhørlig].

88
00:04:06,680 --> 00:04:07,020
>> SPEAKER 1: Yeah.

89
00:04:07,020 --> 00:04:08,400
Det er en peker til den neste noden.

90
00:04:08,400 --> 00:04:12,610
Så dette bør faktisk være her oppe.

91
00:04:12,610 --> 00:04:18,790
Dette er en peker av typen
node til neste ting.

92
00:04:18,790 --> 00:04:22,410
Og det er det de
omfatter vår node.

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

94
00:04:24,060 --> 00:04:29,390
>> All right, så med søket, som vi var
bare si før hånd, hvis du er

95
00:04:29,390 --> 00:04:31,840
kommer til å søke gjennom,
du må faktisk iterere

96
00:04:31,840 --> 00:04:33,660
gjennom lenket liste.

97
00:04:33,660 --> 00:04:38,530
Så hvis vi ser for antall
9, ville vi starter på vårt hode

98
00:04:38,530 --> 00:04:41,520
og som peker oss i begynnelsen
av vår lenket liste, ikke sant?

99
00:04:41,520 --> 00:04:44,600
Og vi sier, OK, gjør dette
node inneholder tallet 9?

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

101
00:04:45,690 --> 00:04:47,500
>> All right, gå til den neste.

102
00:04:47,500 --> 00:04:48,312
Følge den.

103
00:04:48,312 --> 00:04:49,520
Betyr det inneholde nummer 9?

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

105
00:04:50,570 --> 00:04:51,550
Følg den neste.

106
00:04:51,550 --> 00:04:55,490
>> Så vi må faktisk iterere
gjennom vår lenket liste.

107
00:04:55,490 --> 00:05:00,070
Vi kan ikke bare gå direkte til der 9 er.

108
00:05:00,070 --> 00:05:05,860
Og hvis dere faktisk ønsker å
se noen pseudo-kode der oppe.

109
00:05:05,860 --> 00:05:10,420
Vi har noen søkefunksjonen her
som tar in-- hva tar det inn?

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

111
00:05:13,110 --> 00:05:14,320
Hva tror du?

112
00:05:14,320 --> 00:05:15,960
Så enkel en.

113
00:05:15,960 --> 00:05:17,784
Hva er dette?

114
00:05:17,784 --> 00:05:18,700
PUBLIKUM: [uhørlig].

115
00:05:18,700 --> 00:05:20,366
SPEAKER 1: Tallet vi leter etter.

116
00:05:20,366 --> 00:05:20,980
Høyre?

117
00:05:20,980 --> 00:05:22,875
Og hva ville dette tilsvare?

118
00:05:22,875 --> 00:05:25,020
Det er en peker til?

119
00:05:25,020 --> 00:05:26,000
>> PUBLIKUM: En node.

120
00:05:26,000 --> 00:05:28,980
>> SPEAKER 1: En node til liste
at vi ser på, ikke sant?

121
00:05:28,980 --> 00:05:33,700
Så vi har noen noder er pekeren her.

122
00:05:33,700 --> 00:05:37,240
Dette er et punkt som kommer til å
faktisk iterere gjennom vår liste.

123
00:05:37,240 --> 00:05:39,630
Vi setter den lik liste
fordi det er bare

124
00:05:39,630 --> 00:05:44,380
å sette den lik
start av vår lenket liste.

125
00:05:44,380 --> 00:05:50,660
>> Og mens det ikke er NULL, mens
vi har fortsatt ting i vår liste,

126
00:05:50,660 --> 00:05:55,580
sjekk for å se om det node har
antallet vi leter etter.

127
00:05:55,580 --> 00:05:57,740
Returnere true.

128
00:05:57,740 --> 00:06:01,070
Ellers oppdatere den, ikke sant?

129
00:06:01,070 --> 00:06:04,870
>> Hvis det er NULL, vi avslutter vår
mens loop og return false

130
00:06:04,870 --> 00:06:08,340
fordi det betyr at vi ikke har funnet den.

131
00:06:08,340 --> 00:06:11,048
Har alle får hvordan det fungerer?

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
>> Så med innsetting, du
har tre forskjellige måter.

135
00:06:20,260 --> 00:06:25,250
Du kan foran, du kan legge til
og du kan sette inn i assortert.

136
00:06:25,250 --> 00:06:28,215
I dette tilfellet er vi
kommer til å gjøre en foranstilt.

137
00:06:28,215 --> 00:06:33,380
Vet noen hvordan de
tre tilfeller kan avvike?

138
00:06:33,380 --> 00:06:36,920
>> Så foranstilte betyr at du setter
det på forsiden av listen.

139
00:06:36,920 --> 00:06:39,770
Slik det ville bety at uansett
hva din noden er, uansett

140
00:06:39,770 --> 00:06:43,160
hva verdien er, du kommer
for å si det rett her foran, OK?

141
00:06:43,160 --> 00:06:45,160
Det kommer til å bli den første
element i listen din.

142
00:06:45,160 --> 00:06:49,510
>> Hvis du føyer det, kommer det til
å gå til baksiden av listen.

143
00:06:49,510 --> 00:06:54,010
Og sett inn assortert betyr at du er
kommer til å sette faktisk inn i stedet

144
00:06:54,010 --> 00:06:57,700
hvor den holder lenket liste sortert.

145
00:06:57,700 --> 00:07:00,810
Igjen, hvordan du bruker
de og når du bruker

146
00:07:00,810 --> 00:07:02,530
dem vil variere avhengig av ditt tilfelle.

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

148
00:07:05,834 --> 00:07:07,750
Hvis den ikke trenger å
sorteres, har en tendens til foranstilte

149
00:07:07,750 --> 00:07:10,460
å være hva folk flest
bruke fordi du ikke

150
00:07:10,460 --> 00:07:15,680
må gå gjennom hele listen
å finne slutten for å legge den på, ikke sant?

151
00:07:15,680 --> 00:07:17,720
Du kan bare stikke den rett i.

152
00:07:17,720 --> 00:07:21,930
>> Så vi vil gå gjennom en
innsetting en akkurat nå.

153
00:07:21,930 --> 00:07:26,360
Så en ting som jeg kommer til å
anbefaler på denne PSet

154
00:07:26,360 --> 00:07:29,820
er å trekke ting ut, som alltid.

155
00:07:29,820 --> 00:07:35,130
Det er veldig viktig at du oppdaterer
dine pekere i riktig rekkefølge

156
00:07:35,130 --> 00:07:38,620
fordi hvis du oppdaterer dem
litt ute av drift,

157
00:07:38,620 --> 00:07:42,210
du kommer til å ende opp
miste deler av listen din.

158
00:07:42,210 --> 00:07:49,680
>> Så for eksempel, i dette tilfellet, er vi
forteller hodet for å bare peke til 1.

159
00:07:49,680 --> 00:07:56,070
Hvis vi bare gjøre det
uten å lagre dette en,

160
00:07:56,070 --> 00:07:58,570
Vi aner ikke hva
En skal peke til nå

161
00:07:58,570 --> 00:08:02,490
fordi vi har mistet det
hodet pekte på.

162
00:08:02,490 --> 00:08:05,530
Så én ting å huske
når du gjør en foranstilt

163
00:08:05,530 --> 00:08:09,630
er å spare hva
hode peker på først,

164
00:08:09,630 --> 00:08:15,210
deretter overføre den, og deretter oppdatere
hva din nye noden skal peke til.

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

166
00:08:20,870 --> 00:08:22,560
I dette tilfellet, er dette en måte å gjøre det.

167
00:08:22,560 --> 00:08:25,440
>> Så hvis vi hadde gjort det på denne måten
der vi bare omplassert hodet,

168
00:08:25,440 --> 00:08:30,320
vi mister i utgangspunktet vår
hele listen, ikke sant?

169
00:08:30,320 --> 00:08:38,000
En måte å gjøre det på er å ha en peker til
neste, og så hodet punkt til 1.

170
00:08:38,000 --> 00:08:42,650
Eller du kan gjøre typen som
mellomlagring, som jeg snakket om.

171
00:08:42,650 --> 00:08:45,670
>> Men reassigning din
pekere i riktig rekkefølge

172
00:08:45,670 --> 00:08:48,750
kommer til å bli veldig, veldig
viktig for denne PSet.

173
00:08:48,750 --> 00:08:53,140
Ellers kommer du til å ha en hash
tabell eller en prøve som bare kommer til å være

174
00:08:53,140 --> 00:08:56,014
bare en del av ordene som du
ønsker og deretter you're-- mmhmm?

175
00:08:56,014 --> 00:08:58,930
PUBLIKUM: Hva var den midlertidige
oppbevarings ting du snakket om?

176
00:08:58,930 --> 00:09:00,305
SPEAKER 1: Den midlertidige lagring.

177
00:09:00,305 --> 00:09:02,760
Så i utgangspunktet en annen
måten du kan gjøre dette

178
00:09:02,760 --> 00:09:07,650
er lagre leder av noe, som
lagre det midlertidig variabel.

179
00:09:07,650 --> 00:09:11,250
Tilordne den til en og
deretter oppdatere en å peke

180
00:09:11,250 --> 00:09:13,830
til hvilken hodet brukes til å peke til.

181
00:09:13,830 --> 00:09:16,920
På denne måten er åpenbart
mer elegant fordi du

182
00:09:16,920 --> 00:09:20,770
ikke trenger en midlertidig verdi, men
bare tilby en annen måte å gjøre det.

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

184
00:09:23,999 --> 00:09:25,790
Og vi faktisk har
noen kode for dette.

185
00:09:25,790 --> 00:09:28,080
Så for lenket liste, vi
faktisk har noen kode.

186
00:09:28,080 --> 00:09:31,930
Så setter du inn her, dette er prepending.

187
00:09:31,930 --> 00:09:34,290
Så dette går den på hodet.

188
00:09:34,290 --> 00:09:38,820
>> Så første, må du
opprette den nye noden, selvfølgelig,

189
00:09:38,820 --> 00:09:40,790
og se etter NULL.

190
00:09:40,790 --> 00:09:43,250
Alltid godt.

191
00:09:43,250 --> 00:09:47,840
Og så må du tilordne verdiene.

192
00:09:47,840 --> 00:09:51,260
Når du oppretter en ny node, du
vet ikke hva det peker til neste,

193
00:09:51,260 --> 00:09:54,560
slik at du ønsker å initialisere den til NULL.

194
00:09:54,560 --> 00:09:58,760
Hvis det ikke ender opp som peker til noe
annet, det blir omplassert, og det er greit.

195
00:09:58,760 --> 00:10:00,740
Hvis det er det første
i listen, må det

196
00:10:00,740 --> 00:10:04,270
å peke til NULL fordi
det er slutten av listen.

197
00:10:04,270 --> 00:10:12,410
>> Så da å sette den, ser vi her vi
tilordner den neste verdien av vår node

198
00:10:12,410 --> 00:10:17,380
å være hva hodet er,
som er hva vi hadde her.

199
00:10:17,380 --> 00:10:19,930
Det er det vi nettopp gjorde.

200
00:10:19,930 --> 00:10:25,820
Og så skal vi tildele hodet til punkt
til vår nye node, fordi husk,

201
00:10:25,820 --> 00:10:31,090
nye er noen peker til en node,
og det er akkurat hva hodet er.

202
00:10:31,090 --> 00:10:34,370
Det er nettopp derfor vi
har denne pilen tilbehør.

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
>> PUBLIKUM: Må vi
initial nye neste til NULL først,

207
00:10:41,100 --> 00:10:44,240
eller kan vi bare initialisere den til hodet?

208
00:10:44,240 --> 00:10:48,210
>> SPEAKER 1: Ny neste
må være NULL å starte

209
00:10:48,210 --> 00:10:53,760
fordi du ikke vet
hvor det kommer til å bli.

210
00:10:53,760 --> 00:10:56,100
Dessuten er denne type
akkurat som et paradigme.

211
00:10:56,100 --> 00:10:59,900
Du setter den lik NULL bare for å gjøre
sikker på at alle baser er dekket

212
00:10:59,900 --> 00:11:04,070
før du gjør noe omdisponering slik at
du er alltid garantert at det vil

213
00:11:04,070 --> 00:11:08,880
peke mot en bestemt verdi
versus som en søppel verdi.

214
00:11:08,880 --> 00:11:12,210
Fordi, ja, vi tildele
nye neste automatisk,

215
00:11:12,210 --> 00:11:15,420
men det er mer akkurat som en
god praksis for å initialisere den

216
00:11:15,420 --> 00:11:19,270
på den måten, og deretter overføre.

217
00:11:19,270 --> 00:11:23,420
>> OK, så dobbelt knyttet lister nå.

218
00:11:23,420 --> 00:11:24,601
Hva tror vi?

219
00:11:24,601 --> 00:11:26,350
Hva er annerledes med
Dobbelt knyttet lister?

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

221
00:11:30,750 --> 00:11:34,300
>> Så i våre lenkede lister, kan vi
bare bevege seg i en retning, ikke sant?

222
00:11:34,300 --> 00:11:35,270
Vi har bare neste.

223
00:11:35,270 --> 00:11:36,760
Vi kan bare gå fremover.

224
00:11:36,760 --> 00:11:40,300
>> Med en dobbelt lenket liste,
Vi kan også gå bakover.

225
00:11:40,300 --> 00:11:44,810
Så vi har ikke bare
tall som vi ønsker å lagre,

226
00:11:44,810 --> 00:11:50,110
vi har der den peker til neste
og hvor vi kom fra.

227
00:11:50,110 --> 00:11:52,865
Så dette gir mulighet for
noen bedre traversering.

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

229
00:11:56,620 --> 00:12:01,240
>> Så dobbelt koblede noder,
svært like, ikke sant?

230
00:12:01,240 --> 00:12:05,000
Eneste forskjellen nå er vi
har en neste og forrige.

231
00:12:05,000 --> 00:12:06,235
Det er den eneste forskjellen.

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

233
00:12:09,570 --> 00:12:14,790
>> Så hvis vi skulle foran eller append-- vi
har ikke noen kode for dette opp her--

234
00:12:14,790 --> 00:12:17,830
men hvis du skulle prøve og
sett det, det viktigste

235
00:12:17,830 --> 00:12:19,980
er du trenger å gjøre
at du tilordner

236
00:12:19,980 --> 00:12:23,360
både den forrige og din
neste pekeren riktig.

237
00:12:23,360 --> 00:12:29,010
Så i dette tilfellet, ville du
ikke bare initial neste,

238
00:12:29,010 --> 00:12:31,820
du initial forrige.

239
00:12:31,820 --> 00:12:36,960
Hvis vi er på hodet av listen, vi
vil ikke bare gjøre hodet lik nye,

240
00:12:36,960 --> 00:12:41,750
men vår nye forrige bør
peker mot hodet, ikke sant?

241
00:12:41,750 --> 00:12:43,380
>> Det er den eneste forskjellen.

242
00:12:43,380 --> 00:12:47,200
Og hvis du vil ha mer praksis med
disse med lenkede lister, med innsetting,

243
00:12:47,200 --> 00:12:49,900
med å slette, med innlegg
inn en assortert listen,

244
00:12:49,900 --> 00:12:52,670
kan du sjekke ut study.cs50.net.

245
00:12:52,670 --> 00:12:54,870
Det er en haug med flotte øvelser.

246
00:12:54,870 --> 00:12:55,870
Jeg anbefaler dem.

247
00:12:55,870 --> 00:12:59,210
Jeg skulle ønske vi hadde tid til å gå gjennom dem
men det er mye av datastrukturer

248
00:12:59,210 --> 00:13:01,530
å komme gjennom.

249
00:13:01,530 --> 00:13:02,650
>> OK, så hash tabeller.

250
00:13:02,650 --> 00:13:07,070
Dette er sannsynligvis den mest
nyttig bit for din PSet

251
00:13:07,070 --> 00:13:11,090
her fordi du kommer til å være
implementere en av disse, eller en prøve.

252
00:13:11,090 --> 00:13:12,200
Jeg liker hash tabeller.

253
00:13:12,200 --> 00:13:13,110
De er ganske kult.

254
00:13:13,110 --> 00:13:17,080
>> Så i utgangspunktet hva
skjer er en hash table

255
00:13:17,080 --> 00:13:22,050
er når vi virkelig trenger rask
innsetting, sletting, og oppslag.

256
00:13:22,050 --> 00:13:25,010
De er de tingene som vi er
prioritering i en hash table.

257
00:13:25,010 --> 00:13:29,500
De kan bli ganske store,
men som vi skal se med prøver,

258
00:13:29,500 --> 00:13:33,040
det er ting som er mye større.

259
00:13:33,040 --> 00:13:38,330
>> Men innerst inne, alt en hash
Tabellen er en hash-funksjon

260
00:13:38,330 --> 00:13:47,215
som forteller deg hvilken bøtte å sette hver
av dine data, hver av elementene i.

261
00:13:47,215 --> 00:13:51,140
En enkel måte å tenke på en hash table
er at det er bare bøtter med ting,

262
00:13:51,140 --> 00:13:51,770
ikke sant?

263
00:13:51,770 --> 00:13:59,720
Så når du sorterer ting ved
som den første bokstaven i navnet sitt,

264
00:13:59,720 --> 00:14:01,820
det er litt som en hash table.

265
00:14:01,820 --> 00:14:06,180
>> Så hvis jeg skulle gruppen dere er
inn i grupper på hvem navn starter

266
00:14:06,180 --> 00:14:11,670
med A over her, hvem er eller bursdag
er i januar, februar, mars,

267
00:14:11,670 --> 00:14:15,220
uansett, er at effektivt
skape en hash table.

268
00:14:15,220 --> 00:14:18,120
Det er bare å lage bøtter som
du sortere elementer inn

269
00:14:18,120 --> 00:14:19,520
slik at du kan finne dem lettere.

270
00:14:19,520 --> 00:14:22,300
Så denne måten når jeg trenger
å finne en av dere,

271
00:14:22,300 --> 00:14:24,680
Jeg trenger ikke å søke
gjennom hver av navnene dine.

272
00:14:24,680 --> 00:14:29,490
Jeg kan være som, oh, jeg vet at
Danielle bursdag er in--

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

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

275
00:14:30,948 --> 00:14:33,120
Så jeg ser i min april
bøtte, og med litt hell,

276
00:14:33,120 --> 00:14:38,270
hun vil være den eneste der og
min tid var konstant i den forstand,

277
00:14:38,270 --> 00:14:41,230
mens hvis jeg må se
gjennom en hel haug med folk,

278
00:14:41,230 --> 00:14:43,090
det kommer til å ta mye lengre tid.

279
00:14:43,090 --> 00:14:45,830
Så hash tabeller er egentlig bare bøtter.

280
00:14:45,830 --> 00:14:48,630
Enkel måte å tenke på dem.

281
00:14:48,630 --> 00:14:52,930
>> Så en veldig viktig ting om
en hash table er en hash-funksjon.

282
00:14:52,930 --> 00:14:58,140
Så de tingene jeg nettopp har snakket om, som
den første bokstaven i fornavnet ditt

283
00:14:58,140 --> 00:15:01,450
eller bursdagen din måned,
disse er ideer som

284
00:15:01,450 --> 00:15:03,070
virkelig relatere til en hash-funksjon.

285
00:15:03,070 --> 00:15:08,900
Det er bare en måte å bestemme hvilke
bøtte deg er element går inn, OK?

286
00:15:08,900 --> 00:15:14,850
Så for denne PSet, kan du slå opp
stort sett alle hash-funksjon du vil.

287
00:15:14,850 --> 00:15:16,030
>> Trenger ikke å være din egen.

288
00:15:16,030 --> 00:15:21,140
Det er noen virkelig kule seg ut
det som gjør alle slags sprø matematikk.

289
00:15:21,140 --> 00:15:25,170
Og hvis du ønsker å gjøre din
stavekontroll super rask,

290
00:15:25,170 --> 00:15:27,620
Jeg ville definitivt
ser inn i en av disse.

291
00:15:27,620 --> 00:15:32,390
>> Men det finnes også
enkle reglene, som databehandlings

292
00:15:32,390 --> 00:15:39,010
summen av ord, som
hver bokstav har en rekke.

293
00:15:39,010 --> 00:15:39,940
Beregn summen.

294
00:15:39,940 --> 00:15:42,230
Som bestemmer bøtte.

295
00:15:42,230 --> 00:15:45,430
De har også de enkle de som
er akkurat som alle A her,

296
00:15:45,430 --> 00:15:47,050
alle B her.

297
00:15:47,050 --> 00:15:48,920
Hvilken som helst av disse.

298
00:15:48,920 --> 00:15:55,770
>> I utgangspunktet, det bare forteller deg hvilke
matrise indeksere element bør gå inn.

299
00:15:55,770 --> 00:15:58,690
Bare bestemmer bucket--
det er alt en hash-funksjon er.

300
00:15:58,690 --> 00:16:04,180
Så her har vi et eksempel som er
bare den første bokstaven i strengen

301
00:16:04,180 --> 00:16:05,900
at jeg bare snakker om.

302
00:16:05,900 --> 00:16:11,900
>> Så du har litt hasj det er bare
første bokstaven i strengen minus A,

303
00:16:11,900 --> 00:16:16,090
som vil gi deg litt
tall mellom 0 og 25.

304
00:16:16,090 --> 00:16:20,790
Og hva du ønsker å gjøre er
sørge for at dette representerer

305
00:16:20,790 --> 00:16:24,110
størrelsen på hash table--
hvor mange bøtter er det.

306
00:16:24,110 --> 00:16:25,860
Med mange av disse
hash funksjoner, de er

307
00:16:25,860 --> 00:16:31,630
kommer til å være tilbake verdier som kanskje
være langt over antall bøtter

308
00:16:31,630 --> 00:16:33,610
at du faktisk har
i hash table,

309
00:16:33,610 --> 00:16:37,240
så du trenger å gjøre
sikker og mod av dem.

310
00:16:37,240 --> 00:16:42,190
Ellers kommer det til å si,
oh, bør det være i bøtte 5000

311
00:16:42,190 --> 00:16:46,040
men du har bare 30
bøtter i din hash table.

312
00:16:46,040 --> 00:16:49,360
Og selvfølgelig, vi alle vet at det er
kommer til å resultere i noen sprø feil.

313
00:16:49,360 --> 00:16:52,870
Så sørg for å mod av
størrelsen på hash table.

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
Så kollisjoner.

317
00:17:00,506 --> 00:17:02,620
Er alle bra så langt?

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

319
00:17:03,120 --> 00:17:05,900
>> PUBLIKUM: Hvorfor skulle det
returnere en slik massiv verdi?

320
00:17:05,900 --> 00:17:09,210
>> SPEAKER 1: Avhengig av algoritmen
at hash-funksjon bruker.

321
00:17:09,210 --> 00:17:12,270
Noen av dem vil gjøre
gal multiplikasjon.

322
00:17:12,270 --> 00:17:16,270
Og det handler om å få
en jevn fordeling,

323
00:17:16,270 --> 00:17:18,490
slik de gjør noen virkelig
gale ting noen ganger.

324
00:17:18,490 --> 00:17:20,960
Det er alt.

325
00:17:20,960 --> 00:17:22,140
Noe mer?

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

327
00:17:22,829 --> 00:17:24,480
>> Så kollisjoner.

328
00:17:24,480 --> 00:17:29,270
I utgangspunktet, som jeg sa tidligere,
i beste fall,

329
00:17:29,270 --> 00:17:32,040
noen bøtte jeg se nærmere på er
kommer til å ha en ting,

330
00:17:32,040 --> 00:17:34,160
så jeg trenger ikke å se i det hele tatt, ikke sant?

331
00:17:34,160 --> 00:17:37,040
Jeg enten vet det er der, eller det er
ikke, og det er det vi egentlig ønsker.

332
00:17:37,040 --> 00:17:43,960
Men hvis vi har titusenvis av
datapunkter og mindre enn det antall

333
00:17:43,960 --> 00:17:48,700
av bøtter, kommer vi til å ha
kollisjoner der til slutt noe

334
00:17:48,700 --> 00:17:54,210
er nødt til å ende opp i en
bøtte som allerede har et element.

335
00:17:54,210 --> 00:17:57,390
>> Så spørsmålet er, hva
gjør vi i så fall?

336
00:17:57,390 --> 00:17:58,480
Hva gjør vi?

337
00:17:58,480 --> 00:17:59,300
Vi har allerede noe der?

338
00:17:59,300 --> 00:18:00,060
Har vi bare kaste den ut?

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

340
00:18:00,700 --> 00:18:01,980
Vi må holde dem begge.

341
00:18:01,980 --> 00:18:06,400
Så den måten at vi
vanligvis gjør som er hva?

342
00:18:06,400 --> 00:18:08,400
Hva er datastrukturen
vi nettopp snakket om?

343
00:18:08,400 --> 00:18:09,316
PUBLIKUM: Linked-listen.

344
00:18:09,316 --> 00:18:10,500
SPEAKER 1: En lenket liste.

345
00:18:10,500 --> 00:18:16,640
Så nå, i stedet for hver av disse
bøtter bare ha ett element,

346
00:18:16,640 --> 00:18:24,020
det kommer til å inneholde en lenket liste over
de elementer som ble hashed inn i den.

347
00:18:24,020 --> 00:18:27,588
OK, gjør alle slags få den ideen?

348
00:18:27,588 --> 00:18:30,546
Fordi vi ikke kunne ha en matrise
fordi vi ikke vet hvor mange ting

349
00:18:30,546 --> 00:18:31,730
kommer til å være der.

350
00:18:31,730 --> 00:18:36,540
En lenket liste tillater oss å
ha bare det nøyaktige antallet som

351
00:18:36,540 --> 00:18:38,465
er hashet til at bøtte, ikke sant?

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

353
00:18:42,260 --> 00:18:50,500
>> Så lineær sonder er
utgangspunktet denne idea--

354
00:18:50,500 --> 00:18:52,300
det er en måte å håndtere en kollisjon.

355
00:18:52,300 --> 00:18:58,010
Det du kan gjøre er hvis, i dette
tilfelle, bær ble hashet inn en

356
00:18:58,010 --> 00:19:01,130
og vi har allerede
noe der, du bare

357
00:19:01,130 --> 00:19:04,840
holde det gående ned til
du finner en tom plass.

358
00:19:04,840 --> 00:19:06,370
Det er en måte å håndtere det.

359
00:19:06,370 --> 00:19:09,020
Den andre måten å håndtere
det er med det vi nettopp

360
00:19:09,020 --> 00:19:12,280
called-- den koblede
Listen kalles kjeding.

361
00:19:12,280 --> 00:19:20,510
>> Så denne ideen fungerer hvis
din hash table du tror

362
00:19:20,510 --> 00:19:24,150
er mye større enn
dataene satt, eller hvis du

363
00:19:24,150 --> 00:19:28,870
ønsker å prøve og minimere kjeding
før det er absolutt nødvendig.

364
00:19:28,870 --> 00:19:34,050
Så en ting er lineær
sondering åpenbart betyr

365
00:19:34,050 --> 00:19:37,290
at hash-funksjon
er ikke fullt så nyttig

366
00:19:37,290 --> 00:19:42,200
fordi du kommer til å ende opp med å bruke
din hash-funksjon, å komme til et punkt,

367
00:19:42,200 --> 00:19:46,400
du lineær sonde ned til
et sted som er tilgjengelig.

368
00:19:46,400 --> 00:19:49,670
Men nå, selvfølgelig, noe
annet som ender opp der,

369
00:19:49,670 --> 00:19:52,050
du er nødt til å
søke enda lenger nede.

370
00:19:52,050 --> 00:19:55,650
>> Og det er mye mer
Søke utgift som

371
00:19:55,650 --> 00:19:59,820
går inn å legge inn et element
i hash table nå, ikke sant?

372
00:19:59,820 --> 00:20:05,640
Og nå når du går og prøve og finne
bær igjen, du kommer til hasj det,

373
00:20:05,640 --> 00:20:07,742
og det kommer til å si,
oh, se i bøtte 1,

374
00:20:07,742 --> 00:20:09,700
og det kommer ikke til å være
i bøtte en, slik at du er

375
00:20:09,700 --> 00:20:11,970
nødt til å traversere
gjennom resten av disse.

376
00:20:11,970 --> 00:20:17,720
Så det er noen ganger nyttig,
men i de fleste tilfeller

377
00:20:17,720 --> 00:20:22,660
vi kommer til å si at
kjeding er hva du ønsker å gjøre.

378
00:20:22,660 --> 00:20:25,520
>> Så vi snakket om dette tidligere.

379
00:20:25,520 --> 00:20:27,812
Jeg fikk litt foran meg selv.

380
00:20:27,812 --> 00:20:33,560
Men kjeding er utgangspunktet at
hver bøtte i hash table

381
00:20:33,560 --> 00:20:36,120
er bare en lenket liste.

382
00:20:36,120 --> 00:20:39,660
>> Så en annen måte, eller mer teknisk
måten å tenke på en hash table

383
00:20:39,660 --> 00:20:44,490
er at det er bare en matrise
av lenkede lister, som

384
00:20:44,490 --> 00:20:49,330
når du skriver ordbok
og du prøver å laste den,

385
00:20:49,330 --> 00:20:52,070
tenker på det som en
utvalg av lenkede lister

386
00:20:52,070 --> 00:20:54,390
vil gjøre det mye lettere
for deg å initialisere.

387
00:20:54,390 --> 00:20:57,680
>> PUBLIKUM: Så hash table
har en forutbestemt størrelse,

388
00:20:57,680 --> 00:20:58,980
som en [uhørbart] bøtter?

389
00:20:58,980 --> 00:20:59,220
>> SPEAKER 1: Høyre.

390
00:20:59,220 --> 00:21:01,655
Så det har et gitt antall
bøtter som du determine--

391
00:21:01,655 --> 00:21:03,530
som dere bør
gjerne spille med.

392
00:21:03,530 --> 00:21:05,269
Det kan være ganske kult
å se hva som skjer

393
00:21:05,269 --> 00:21:06,810
som du endrer antall bøtter.

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

395
00:21:09,410 --> 00:21:11,510
Men ja, det har en
satt antall bøtter.

396
00:21:11,510 --> 00:21:15,360
Hva gjør du for å passe så
mange elementer som du trenger

397
00:21:15,360 --> 00:21:19,350
og er en egen kjeding der du
har knyttet lister i hver bøtte.

398
00:21:19,350 --> 00:21:22,850
Det betyr at hash table
vil være nøyaktig den størrelsen

399
00:21:22,850 --> 00:21:25,440
at du trenger det for å være, ikke sant?

400
00:21:25,440 --> 00:21:27,358
Det er hele poenget med lenkede lister.

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
>> Så alle OK det?

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

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

406
00:21:40,300 --> 00:21:41,860
Hva skjedde?

407
00:21:41,860 --> 00:21:42,960
Virkelig nå.

408
00:21:42,960 --> 00:21:45,250
Gjett noen dreper meg.

409
00:21:45,250 --> 00:21:52,060
>> OK vi kommer til å gå inn
prøver, som er litt gal.

410
00:21:52,060 --> 00:21:53,140
Jeg liker hash tabeller.

411
00:21:53,140 --> 00:21:54,460
Jeg tror de er veldig kult.

412
00:21:54,460 --> 00:21:56,710
Prøver er kult, også.

413
00:21:56,710 --> 00:21:59,590
>> Så er det noen som husker hva en prøve er?

414
00:21:59,590 --> 00:22:01,740
Du bør ha gått over
det kort på forelesning?

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

416
00:22:04,570 --> 00:22:06,377
Husker slags hvordan det fungerer på?

417
00:22:06,377 --> 00:22:08,460
PUBLIKUM: Jeg bare nikker
at vi gikk over den.

418
00:22:08,460 --> 00:22:09,626
SPEAKER 1: Vi går over det.

419
00:22:09,626 --> 00:22:13,100
OK, vi virkelig kommer til å gå
over det nå er hva vi sier.

420
00:22:13,100 --> 00:22:14,860
>> PUBLIKUM: Det er for en henting treet.

421
00:22:14,860 --> 00:22:15,280
>> SPEAKER 1: Yeah.

422
00:22:15,280 --> 00:22:16,196
Det er en henting treet.

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

424
00:22:16,960 --> 00:22:23,610
Så en ting å legge merke til her er at vi
ser på enkelttegn

425
00:22:23,610 --> 00:22:24,480
her, ikke sant?

426
00:22:24,480 --> 00:22:29,710
>> Så før med vår hash-funksjon, vi
var ute på ordene som helhet,

427
00:22:29,710 --> 00:22:32,270
og nå ser vi mer
på karakterene, ikke sant?

428
00:22:32,270 --> 00:22:38,380
Så vi har Maxwell over her og Mendel.

429
00:22:38,380 --> 00:22:47,840
Så i utgangspunktet en try-- en måte å tenke
om dette er at alle nivåer her

430
00:22:47,840 --> 00:22:49,000
er en rekke bokstaver.

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

432
00:22:53,310 --> 00:22:55,790
Så dette er din rotnoden her, ikke sant?

433
00:22:55,790 --> 00:23:01,980
Dette har alle tegnene i
alfabetet for starten av hvert ord.

434
00:23:01,980 --> 00:23:06,480
>> Og hva du ønsker å gjøre er
si, OK, har vi noen M ord.

435
00:23:06,480 --> 00:23:10,590
Vi kommer til å lete etter Maxwell, så
vi går til M. Og M poeng til en helhet

436
00:23:10,590 --> 00:23:14,800
andre en matrise der hver
ord, så lenge der

437
00:23:14,800 --> 00:23:17,044
er et ord som har A
som den andre bokstaven,

438
00:23:17,044 --> 00:23:19,460
så lenge det er et ord som
har B som det andre brevet,

439
00:23:19,460 --> 00:23:24,630
det vil ha en peker
gå til noen neste array.

440
00:23:24,630 --> 00:23:29,290
>> Det er nok ikke en
ord som MP noe,

441
00:23:29,290 --> 00:23:32,980
så på P posisjon i dette
array, ville det bare være NULL.

442
00:23:32,980 --> 00:23:38,840
Det vil si, OK, det er ingen ord
som har M etterfulgt av en P, OK?

443
00:23:38,840 --> 00:23:43,100
Så hvis vi tenker på det, hver
en av disse mindre ting

444
00:23:43,100 --> 00:23:47,990
er faktisk en av disse
store matriser fra A til Z.

445
00:23:47,990 --> 00:23:55,064
Så hva kan være en av de tingene
som er en slags ulempe med en prøve?

446
00:23:55,064 --> 00:23:56,500
>> PUBLIKUM: Mye minne.

447
00:23:56,500 --> 00:23:59,940
>> SPEAKER 1: Det er massevis av minne, ikke sant?

448
00:23:59,940 --> 00:24:08,750
Hver av disse blokkene her
representerer 26 plasser, 26 element array.

449
00:24:08,750 --> 00:24:13,680
Så prøver får utrolig plass tung.

450
00:24:13,680 --> 00:24:17,100
>> Men de er veldig fort.

451
00:24:17,100 --> 00:24:22,540
Så utrolig fort, men
virkelig plass ineffektiv.

452
00:24:22,540 --> 00:24:24,810
Slags må finne
ut hvilken du vil ha.

453
00:24:24,810 --> 00:24:29,470
Dette er skikkelig kult for din PSet,
men de tar opp mye minne,

454
00:24:29,470 --> 00:24:30,290
slik at du bytter ut.

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

456
00:24:31,480 --> 00:24:34,300
>> PUBLIKUM: Ville det være mulig
å sette opp en prøve, og deretter

457
00:24:34,300 --> 00:24:37,967
når du har all
data i det at du need--

458
00:24:37,967 --> 00:24:39,550
Jeg vet ikke om det ville være fornuftig.

459
00:24:39,550 --> 00:24:42,200
Jeg begynte å bli kvitt alle
NULL tegn, men deretter

460
00:24:42,200 --> 00:24:42,910
du ville ikke være i stand til å indeksere them--

461
00:24:42,910 --> 00:24:43,275
>> SPEAKER 1: Du fortsatt trenger dem.

462
00:24:43,275 --> 00:24:44,854
>> PUBLIKUM: - på samme måte hver gang.

463
00:24:44,854 --> 00:24:45,520
SPEAKER 1: Yeah.

464
00:24:45,520 --> 00:24:50,460
Du trenger NULL tegn til å la
vet du om det er ikke et ord der.

465
00:24:50,460 --> 00:24:52,040
Ben hadde du noe du ønsker?

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

467
00:24:52,540 --> 00:24:54,581
Greit, så vi kommer
å gå litt mer

468
00:24:54,581 --> 00:24:58,920
inn i tekniske detaljer bak
en prøve og jobbe gjennom et eksempel.

469
00:24:58,920 --> 00:25:01,490
>> OK, så dette er den samme.

470
00:25:01,490 --> 00:25:06,290
Mens det i en lenket liste, vår viktigste
slag of-- hva er ordet jeg vil? -

471
00:25:06,290 --> 00:25:08,350
som å bygge blokken var en node.

472
00:25:08,350 --> 00:25:12,280
I en prøve, har vi også en node,
men det er definert ulikt.

473
00:25:12,280 --> 00:25:17,000
>> Så vi har litt bool som
representerer enten et ord faktisk

474
00:25:17,000 --> 00:25:23,530
Det finnes på dette stedet, og deretter
vi har noen matrise her-- eller rettere sagt,

475
00:25:23,530 --> 00:25:27,840
Dette er en peker til en
utvalg av 27 tegn.

476
00:25:27,840 --> 00:25:33,339
Og dette er for, i dette tilfelle, denne
27-- Jeg er sikker på at dere alle er like, vent,

477
00:25:33,339 --> 00:25:34,880
det er 26 bokstaver i alfabetet.

478
00:25:34,880 --> 00:25:36,010
Hvorfor har vi 27?

479
00:25:36,010 --> 00:25:37,870
>> Så, avhengig av
måten du implementerer denne,

480
00:25:37,870 --> 00:25:43,240
dette er fra en PSet som
tillatt for apostrofer.

481
00:25:43,240 --> 00:25:46,010
Så det er derfor ekstra en.

482
00:25:46,010 --> 00:25:50,500
Du vil også ha i noen
tilfeller null terminator

483
00:25:50,500 --> 00:25:53,230
er inkludert som ett av
tegn på at det er tillatt å være,

484
00:25:53,230 --> 00:25:56,120
og det er hvordan de kontrollerer
se om det er på slutten av ordet.

485
00:25:56,120 --> 00:26:01,340
Hvis du er interessert, sjekk ut
Kevins video på study.cs50,

486
00:26:01,340 --> 00:26:04,790
samt Wikipedia har
noen gode ressurser der.

487
00:26:04,790 --> 00:26:09,000
>> Men vi kommer til å gå gjennom bare slags
på hvordan du kan arbeide gjennom en prøve

488
00:26:09,000 --> 00:26:11,010
hvis du får en.

489
00:26:11,010 --> 00:26:16,230
Så vi har en super enkel en her at
har ordene "bat" og "zoom" i dem.

490
00:26:16,230 --> 00:26:18,920
Og som vi ser her oppe,
denne lille plassen her

491
00:26:18,920 --> 00:26:22,560
representerer vår bool som
sier, ja, dette er et ord.

492
00:26:22,560 --> 00:26:27,060
Og så dette har vår
matriser av tegn, ikke sant?

493
00:26:27,060 --> 00:26:33,480
>> Så vi kommer til å gå gjennom
å finne "bat" i denne prøve.

494
00:26:33,480 --> 00:26:38,340
Så begynner på toppen, ikke sant?

495
00:26:38,340 --> 00:26:46,290
Og vi vet at b tilsvarer
den andre indeks, det andre elementet

496
00:26:46,290 --> 00:26:47,840
i denne matrise, fordi a og b.

497
00:26:47,840 --> 00:26:51,340
Så omtrent den andre.

498
00:26:51,340 --> 00:26:58,820
>> Og den sier, OK, kult, følger det inn
neste rekke, fordi hvis vi husker,

499
00:26:58,820 --> 00:27:02,160
det er ikke slik at hver av disse
faktisk inneholder elementet.

500
00:27:02,160 --> 00:27:07,110
Hver og en av disse matriser
inneholder en peker, ikke sant?

501
00:27:07,110 --> 00:27:10,030
Det er et viktig skille å gjøre.

502
00:27:10,030 --> 00:27:13,450
>> Jeg vet at dette kommer til å be-- prøver er
veldig vanskelig å få på første gang,

503
00:27:13,450 --> 00:27:15,241
slik at selv om dette er
andre eller tredje gang

504
00:27:15,241 --> 00:27:18,370
og det er fortsatt en slags
for å virke vanskelig,

505
00:27:18,370 --> 00:27:21,199
Jeg lover hvis du går watch
kort igjen i morgen,

506
00:27:21,199 --> 00:27:22,740
det vil sannsynligvis gjøre mye mer fornuftig.

507
00:27:22,740 --> 00:27:23,890
Det tar mye å fordøye.

508
00:27:23,890 --> 00:27:27,800
Jeg fortsatt noen ganger er
lignende, vent, hva er en prøve?

509
00:27:27,800 --> 00:27:29,080
Hvordan bruker jeg dette?

510
00:27:29,080 --> 00:27:33,880
>> Derfor har vi B i dette tilfellet
som er vår andre indeksen.

511
00:27:33,880 --> 00:27:40,240
Hvis vi hadde, sier, c eller
d eller hvilken som helst annen bokstav,

512
00:27:40,240 --> 00:27:45,810
vi trenger å kartlegge det tilbake til indeksen
av vår matrise som som svarer til.

513
00:27:45,810 --> 00:27:56,930
Så vi ville ta like rchar og vi bare
trekke ut en å kartlegge det inn 0-25.

514
00:27:56,930 --> 00:27:58,728
Alle gode hvordan vi
kartlegge vår karakter?

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

516
00:28:00,440 --> 00:28:05,980
>> Så vi går til den andre, og vi
se at, ja, det er ikke til NULL.

517
00:28:05,980 --> 00:28:07,780
Vi kan gå videre til dette neste array.

518
00:28:07,780 --> 00:28:12,300
Så vi går videre til dette neste rekke her.

519
00:28:12,300 --> 00:28:15,500
>> Og vi sier, OK, nå er vi
trenger å se om en er her.

520
00:28:15,500 --> 00:28:18,590
Er en null eller gjør det
faktisk gå videre?

521
00:28:18,590 --> 00:28:21,880
Så en faktisk flytter
fremover i denne matrisen.

522
00:28:21,880 --> 00:28:24,570
Og vi sier, OK, t er vår siste bokstav.

523
00:28:24,570 --> 00:28:27,580
Så vi går til t på indeksen.

524
00:28:27,580 --> 00:28:30,120
Og da vi beveger oss fremover
fordi det er en annen.

525
00:28:30,120 --> 00:28:38,340
Og dette sier i utgangspunktet at, ja,
det står at det er et ord her--

526
00:28:38,340 --> 00:28:41,750
at hvis du følger denne
banen, har du kommet

527
00:28:41,750 --> 00:28:43,210
på et ord, som vi vet er "bat".

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

529
00:28:43,800 --> 00:28:46,770
>> PUBLIKUM: Er det vanlig å ha det
som indeks 0 og deretter har en slags 1

530
00:28:46,770 --> 00:28:47,660
eller til å ha på slutten?

531
00:28:47,660 --> 00:28:48,243
>> SPEAKER 1: Nei.

532
00:28:48,243 --> 00:28:55,360
Så hvis vi ser tilbake på vår
erklæring her, er det en bool,

533
00:28:55,360 --> 00:28:59,490
så det er et eget element i node.

534
00:28:59,490 --> 00:29:03,331
Så det er ikke en del av tabellen.

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

536
00:29:03,830 --> 00:29:08,370
Så når vi er ferdige med ord og vi er
på denne matrisen, hva vi ønsker å gjøre

537
00:29:08,370 --> 00:29:12,807
er å gjøre en sjekk for dette er et ord.

538
00:29:12,807 --> 00:29:14,390
Og i dette tilfellet, ville det tilbake ja.

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

540
00:29:17,220 --> 00:29:24,090
>> Så på dette notatet, vet vi at "zoo" -
vi kjenner som mennesker at "zoo" er et ord,

541
00:29:24,090 --> 00:29:24,820
ikke sant?

542
00:29:24,820 --> 00:29:28,990
Men er prøve her ville
si, nei, det er ikke det.

543
00:29:28,990 --> 00:29:33,980
Og det vil si at fordi vi
har ikke utpekt det som et ord her.

544
00:29:33,980 --> 00:29:40,440
Selv om vi kan traversere
gjennom til denne matrisen,

545
00:29:40,440 --> 00:29:43,890
dette prøve vil si at, nei,
Dyrehagen er ikke i ordboken

546
00:29:43,890 --> 00:29:47,070
fordi vi ikke har
utpekt det som sådan.

547
00:29:47,070 --> 00:29:52,870
>> Så en måte å gjøre at--
oh, sorry, denne.

548
00:29:52,870 --> 00:29:59,450
Så i dette tilfellet, er ikke "zoo"
et ord, men det er i vår prøve.

549
00:29:59,450 --> 00:30:05,690
Men i denne, sier vi vil ha det
introdusere ordet "bad", hva skjer

550
00:30:05,690 --> 00:30:08,260
er vi følger through-- b, a, t.

551
00:30:08,260 --> 00:30:11,820
Vi er i denne tabellen, og
vi går for å søke etter h.

552
00:30:11,820 --> 00:30:15,220
>> I dette tilfellet, når vi
se på pekeren på h,

553
00:30:15,220 --> 00:30:17,890
den peker til NULL, OK?

554
00:30:17,890 --> 00:30:20,780
Så med mindre det er uttrykkelig
peker til en annen array,

555
00:30:20,780 --> 00:30:25,000
du antar at alle pekere
i denne matrisen peker til null.

556
00:30:25,000 --> 00:30:28,270
Slik at i dette tilfellet, er H peker
til null, slik at vi ikke kan gjøre noe,

557
00:30:28,270 --> 00:30:31,540
slik at det ville også returnere
usant, "bad" er ikke her inne.

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

559
00:30:34,102 --> 00:30:35,810
Så nå er vi faktisk
kommer til å gå gjennom

560
00:30:35,810 --> 00:30:39,790
hvordan ville vi faktisk si
at "zoo" er i våre forsøk.

561
00:30:39,790 --> 00:30:42,920
Hvordan setter vi "zoo" inn i vårt forsøk?

562
00:30:42,920 --> 00:30:47,810
Så på samme måte som vi startet med
vår lenket liste, starter vi ved roten.

563
00:30:47,810 --> 00:30:50,600
Når du er i tvil, starter på
roten av disse tingene.

564
00:30:50,600 --> 00:30:53,330
>> Og vi vil si, OK, z.

565
00:30:53,330 --> 00:30:55,650
z eksisterer i dette, og det gjør det.

566
00:30:55,650 --> 00:30:58,370
Så du går videre til
din neste array, OK?

567
00:30:58,370 --> 00:31:01,482
Og deretter på den neste,
vi sier, OK, ikke eksisterer o?

568
00:31:01,482 --> 00:31:03,000
Det gjør.

569
00:31:03,000 --> 00:31:04,330
Dette igjen.

570
00:31:04,330 --> 00:31:08,670
>> Og så på vår neste, har vi sagt,
OK, allerede eksisterer "zoo" her.

571
00:31:08,670 --> 00:31:12,440
Alt vi trenger å gjøre er å sette denne lik
til sann, at det er et ord der.

572
00:31:12,440 --> 00:31:15,260
Hvis du hadde fulgt alt
opp til før det punktet,

573
00:31:15,260 --> 00:31:17,030
det er et ord, så bare
sette den lik slike.

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

575
00:31:17,530 --> 00:31:22,550
>> PUBLIKUM: Så da gjør det
mener at "ba" er et ord også?

576
00:31:22,550 --> 00:31:24,120
>> SPEAKER 1: Nei.

577
00:31:24,120 --> 00:31:28,870
Så i dette tilfellet, "ba" vi ville få
her, ville vi si det er et ord,

578
00:31:28,870 --> 00:31:31,590
og det vil fortsatt være noen.

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
>> PUBLIKUM: Så når du er det en
ord, og du sier ja, så er det

582
00:31:36,360 --> 00:31:38,380
vil inneholde for å gå til m?

583
00:31:38,380 --> 00:31:42,260
>> SPEAKER 1: Så dette har å gjøre
with-- du legger dette på.

584
00:31:42,260 --> 00:31:43,640
Du sier "zoo" er et ord.

585
00:31:43,640 --> 00:31:47,020
Når du går til check--
liker, si at du ønsker å si,

586
00:31:47,020 --> 00:31:49,400
betyr "zoo" eksisterer i dette ordbok?

587
00:31:49,400 --> 00:31:54,200
Du bare kommer til å søke etter "zoo",
og deretter sjekke for å se om det er et ord.

588
00:31:54,200 --> 00:31:57,291
Du kommer aldri til å flytte
gjennom til m, fordi det er ikke

589
00:31:57,291 --> 00:31:58,290
det du leter etter.

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

591
00:32:02,690 --> 00:32:08,070
>> Så hvis vi faktisk ønsket å
legge til "bad" i denne prøve,

592
00:32:08,070 --> 00:32:11,390
Vi ville gjøre det samme
som vi gjorde med "zoo",

593
00:32:11,390 --> 00:32:15,380
bortsett fra at vi ville se at når vi
prøve og få til h, betyr det ikke eksisterer.

594
00:32:15,380 --> 00:32:20,090
Så du kan tenke på dette som prøver
å legge til en ny node i en lenket liste,

595
00:32:20,090 --> 00:32:27,210
så vi måtte legge til en annen
en av disse matriser, som så.

596
00:32:27,210 --> 00:32:35,670
Og så det vi gjør er vi bare sette h
element i denne matrise peker til dette.

597
00:32:35,670 --> 00:32:39,430
>> Og så hva ville vi ønsker å gjøre her?

598
00:32:39,430 --> 00:32:43,110
Legg det lik sant
fordi det er et ord.

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
Jeg vet.

602
00:32:48,700 --> 00:32:51,170
Prøver er ikke den mest spennende.

603
00:32:51,170 --> 00:32:54,250
Stol på meg, jeg vet.

604
00:32:54,250 --> 00:32:58,040
>> Så én ting å realisere med forsøk,
Jeg sa, de er svært effektive.

605
00:32:58,040 --> 00:33:00,080
Så vi har sett de
ta opp massevis av plass.

606
00:33:00,080 --> 00:33:01,370
De er slags forvirrende.

607
00:33:01,370 --> 00:33:03,367
Så hvorfor skulle vi noen gang bruke disse?

608
00:33:03,367 --> 00:33:05,450
Vi bruker disse fordi de er
utrolig effektiv.

609
00:33:05,450 --> 00:33:08,130
>> Så hvis du noen gang ser
opp et ord, er du bare

610
00:33:08,130 --> 00:33:10,450
avgrenset av lengden av ordet.

611
00:33:10,450 --> 00:33:15,210
Så hvis du leter etter en
ord som er lengden av fem,

612
00:33:15,210 --> 00:33:20,940
du er bare noen gang nødt til å
gjøre på de fleste fem sammenligninger, OK?

613
00:33:20,940 --> 00:33:25,780
Så det gjør det i utgangspunktet en konstant.

614
00:33:25,780 --> 00:33:29,150
Som innsetting og oppslag
er stort sett konstant tid.

615
00:33:29,150 --> 00:33:33,750
>> Så hvis du noen gang kan få
noe i konstant tid,

616
00:33:33,750 --> 00:33:35,150
det er så godt som det blir.

617
00:33:35,150 --> 00:33:37,990
Du kan ikke bli bedre enn
konstant tid for disse tingene.

618
00:33:37,990 --> 00:33:43,150
Så det er en av
store plusser prøver.

619
00:33:43,150 --> 00:33:46,780
>> Men det er mye plass.

620
00:33:46,780 --> 00:33:50,380
Så du slags må bestemme
hva er mer viktig for deg.

621
00:33:50,380 --> 00:33:54,700
Og på dagens datamaskiner, i
plass som et forsøk kan ta opp

622
00:33:54,700 --> 00:33:57,740
kanskje ikke påvirker
deg så mye, men kanskje

623
00:33:57,740 --> 00:34:01,350
du arbeider med noe
som har langt, langt flere ting,

624
00:34:01,350 --> 00:34:02,810
og en prøve er bare ikke rimelig.

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

626
00:34:03,000 --> 00:34:05,610
>> PUBLIKUM: Vent, så du har 26
bokstaver i hver eneste en?

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

628
00:34:07,440 --> 00:34:08,570
Ja, du har 26.

629
00:34:08,570 --> 00:34:16,984
Du har noen er ordet markør, og deretter
har du 26 tips i hver eneste en.

630
00:34:16,984 --> 00:34:17,775
Og de er point--

631
00:34:17,775 --> 00:34:20,280
>> PUBLIKUM: Og hver 26,
gjør de hver har 26?

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

633
00:34:21,500 --> 00:34:27,460
Og det er derfor, som du kan
se, det utvider seg ganske raskt.

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

635
00:34:28,130 --> 00:34:32,524
Så vi kommer til å komme inn i trær, som
Jeg føler er lettere og vil trolig

636
00:34:32,524 --> 00:34:36,150
være en fin liten utsettelse
fra forsøk der.

637
00:34:36,150 --> 00:34:39,620
Så forhåpentligvis de fleste av dere
har sett et tre før.

638
00:34:39,620 --> 00:34:41,820
Ikke som den vakre
de utenfor, som jeg

639
00:34:41,820 --> 00:34:44,340
vet ikke om noen
gikk ute nylig.

640
00:34:44,340 --> 00:34:49,230
Jeg gikk apple plukke denne helgen,
og oh my gosh, det var vakkert.

641
00:34:49,230 --> 00:34:52,250
Jeg visste ikke blader
kunne se at pen.

642
00:34:52,250 --> 00:34:53,610
>> Så dette er bare et tre, ikke sant?

643
00:34:53,610 --> 00:34:56,790
Det er bare noen node, og det
peker på en haug med andre noder.

644
00:34:56,790 --> 00:34:59,570
Som du ser her, er dette
slag av en tilbakevendende tema.

645
00:34:59,570 --> 00:35:03,720
Noder peker til noder er slags
essensen av mange datastrukturer.

646
00:35:03,720 --> 00:35:06,670
Det avhenger bare av hvordan vi
få dem til å peke til hverandre

647
00:35:06,670 --> 00:35:08,600
og hvordan vi traversere
gjennom dem og hvordan vi

648
00:35:08,600 --> 00:35:14,500
sette inn ting som avgjør
deres forskjellige egenskaper.

649
00:35:14,500 --> 00:35:17,600
>> Så bare noen terminologi,
som jeg har brukt før.

650
00:35:17,600 --> 00:35:20,010
Så rot er det som er på toppen.

651
00:35:20,010 --> 00:35:21,200
det er der vi alltid starte.

652
00:35:21,200 --> 00:35:23,610
Du kan tenke på det som hodet også.

653
00:35:23,610 --> 00:35:28,750
Men for trær, har vi en tendens til å
referere til det som roten.

654
00:35:28,750 --> 00:35:32,820
>> Noe nederst her--
på veldig, veldig bottom--

655
00:35:32,820 --> 00:35:34,500
er ansett blader.

656
00:35:34,500 --> 00:35:37,210
Så det går sammen med
Hele tre ting, ikke sant?

657
00:35:37,210 --> 00:35:39,860
Bladene er på kantene av treet.

658
00:35:39,860 --> 00:35:45,820
>> Og så har vi også et par
vilkårene for å snakke om noder i forhold

659
00:35:45,820 --> 00:35:46,680
til hverandre.

660
00:35:46,680 --> 00:35:49,700
Så vi har forelder,
barn og søsken.

661
00:35:49,700 --> 00:35:56,260
Så i dette tilfellet er det tre
forelder til 5, 6 og 7.

662
00:35:56,260 --> 00:36:00,370
Så foreldrene er det som er
ett skritt over hva du er

663
00:36:00,370 --> 00:36:02,940
refererer til, så bare
som et familietre.

664
00:36:02,940 --> 00:36:07,090
Forhåpentligvis er dette alt litt
litt mer intuitivt enn prøver.

665
00:36:07,090 --> 00:36:10,970
>> Søsken er noen som har
samme overordnede, ikke sant?

666
00:36:10,970 --> 00:36:13,470
De er på samme nivå her.

667
00:36:13,470 --> 00:36:16,960
Og så, som jeg var
sier, barn er bare

668
00:36:16,960 --> 00:36:22,630
hva er ett skritt nedenfor
noden i spørsmålet, OK?

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

670
00:36:23,470 --> 00:36:25,610
Så et binært tre.

671
00:36:25,610 --> 00:36:31,450
Kan noen gjette på en av
egenskapene til den binære treet?

672
00:36:31,450 --> 00:36:32,770
>> PUBLIKUM: Maks to blader.

673
00:36:32,770 --> 00:36:33,478
>> SPEAKER 1: Høyre.

674
00:36:33,478 --> 00:36:34,640
Så maks to blader.

675
00:36:34,640 --> 00:36:39,730
Så i dette før, hadde vi denne ene
som hadde tre, men i et binært tre,

676
00:36:39,730 --> 00:36:45,000
du har en maks to
barn per forelder, ikke sant?

677
00:36:45,000 --> 00:36:46,970
Det er en annen
interessant trekk.

678
00:36:46,970 --> 00:36:51,550
Vet noen det?

679
00:36:51,550 --> 00:36:52,620
Binærtre.

680
00:36:52,620 --> 00:37:00,350
>> Så et binært tre vil ha alt
på the-- dette er ikke sorted--

681
00:37:00,350 --> 00:37:05,320
men i en sortert binært tre,
alt på høyre

682
00:37:05,320 --> 00:37:08,530
er større enn moder,
og alt på venstre

683
00:37:08,530 --> 00:37:10,035
er mindre enn moder.

684
00:37:10,035 --> 00:37:15,690
Og det har vært en quiz
spørsmålet før, så godt å vite.

685
00:37:15,690 --> 00:37:19,500
Så måten vi definerer dette,
igjen, har vi en annen node.

686
00:37:19,500 --> 00:37:21,880
Dette ser veldig likt det?

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

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

689
00:37:28,836 --> 00:37:29,320
>> Målgruppe: Linked lister

690
00:37:29,320 --> 00:37:31,100
>> SPEAKER 1: Et dobbelt lenket liste, ikke sant?

691
00:37:31,100 --> 00:37:33,690
Så hvis vi erstatte denne
med forrige og neste år,

692
00:37:33,690 --> 00:37:35,670
Dette ville være en dobbelt lenket liste.

693
00:37:35,670 --> 00:37:40,125
Men i dette tilfellet, vi faktisk
har venstre og høyre og det er det.

694
00:37:40,125 --> 00:37:41,500
Ellers er det akkurat det samme.

695
00:37:41,500 --> 00:37:43,374
Vi har fortsatt elementet
du leter etter,

696
00:37:43,374 --> 00:37:45,988
og du bare har to pekere
kommer til hva som er neste.

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

698
00:37:49,210 --> 00:37:51,870
Ja, så binært søketre.

699
00:37:51,870 --> 00:37:57,665
Hvis vi legger merke til, alt på
akkurat her er større than--

700
00:37:57,665 --> 00:37:59,850
eller alt umiddelbart
til høyre her

701
00:37:59,850 --> 00:38:02,840
er større enn, alt
her er mindre enn.

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

703
00:38:06,980 --> 00:38:14,000
>> Så hvis vi skulle søke gjennom, det
bør se svært nær binære søk

704
00:38:14,000 --> 00:38:14,910
her, ikke sant?

705
00:38:14,910 --> 00:38:17,640
Bortsett fra i stedet for å se
til halve array,

706
00:38:17,640 --> 00:38:21,720
vi bare ser på enten venstre
side eller den høyre side av treet.

707
00:38:21,720 --> 00:38:24,850
Så det blir litt enklere, tror jeg.

708
00:38:24,850 --> 00:38:29,300
>> Så hvis din rot er NULL,
tydeligvis er det bare falsk.

709
00:38:29,300 --> 00:38:33,470
Og hvis det er det, selvsagt det er sant.

710
00:38:33,470 --> 00:38:35,320
Hvis det er mindre enn, søk vi til venstre.

711
00:38:35,320 --> 00:38:37,070
Hvis det er større enn,
vi søker den rette.

712
00:38:37,070 --> 00:38:39,890
Det er akkurat som binære søk,
bare en forskjellig datastruktur

713
00:38:39,890 --> 00:38:40,600
som vi bruker.

714
00:38:40,600 --> 00:38:42,790
I stedet for en matrise,
det er bare et binært tre.

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

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

717
00:38:48,090 --> 00:38:51,550
Og også, ser det ut som vi
kan ha en liten bit av gangen.

718
00:38:51,550 --> 00:38:54,460
Hvis vi gjør det, er jeg glad for å gå
over noen av dette igjen.

719
00:38:54,460 --> 00:38:56,856
OK, stabler det.

720
00:38:56,856 --> 00:39:02,695
Er det noen som husker hva stacks--
noen kjennetegn ved en stabel?

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

722
00:39:05,550 --> 00:39:10,400
>> OK, så de fleste av oss, tror jeg,
spise i spise halls--

723
00:39:10,400 --> 00:39:13,100
så mye som vi kanskje ikke liker det.

724
00:39:13,100 --> 00:39:16,900
Men selvsagt, kan du tenke på en stabel
bokstavelig talt bare som en stabel med magasiner

725
00:39:16,900 --> 00:39:18,460
eller en stabel av ting.

726
00:39:18,460 --> 00:39:21,820
Og det som er viktig
å innse er at det er

727
00:39:21,820 --> 00:39:26,850
something-- den karakteristiske
som vi kaller det by-- er LIFO.

728
00:39:26,850 --> 00:39:28,450
Vet noen hva det står for?

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

730
00:39:29,070 --> 00:39:30,650
>> PUBLIKUM: sist inn, først ut.

731
00:39:30,650 --> 00:39:32,250
>> SPEAKER 1: Høyre, sist inn, først ut.

732
00:39:32,250 --> 00:39:36,585
Så hvis vi vet, hvis vi stable ting
opp, til den enkleste ting ta off--

733
00:39:36,585 --> 00:39:39,570
og kanskje det eneste vi kan hente
av hvis stacken er stor enough--

734
00:39:39,570 --> 00:39:40,850
er at øverste element.

735
00:39:40,850 --> 00:39:43,460
Så uansett hva ble satt på
last-- som vi ser her,

736
00:39:43,460 --> 00:39:46,370
hva ble presset
på de fleste recently-- er

737
00:39:46,370 --> 00:39:51,160
kommer til å bli den første
ting som vi pop off, OK?

738
00:39:51,160 --> 00:39:56,324
>> Så det vi har her er
annen typedef struct.

739
00:39:56,324 --> 00:39:58,740
Dette er egentlig bare som en
lynkurs i datastrukturen,

740
00:39:58,740 --> 00:40:01,650
så det er mye kastet på dere.

741
00:40:01,650 --> 00:40:02,540
Jeg vet.

742
00:40:02,540 --> 00:40:04,970
Så enda en struct.

743
00:40:04,970 --> 00:40:06,740
Yay for strukturer.

744
00:40:06,740 --> 00:40:16,660
>> Og i dette tilfellet, er det noen peker
til en matrise som har en viss kapasitet.

745
00:40:16,660 --> 00:40:20,830
Så dette representerer vår stack
her, som vår faktiske matrise

746
00:40:20,830 --> 00:40:22,520
som holder våre elementer.

747
00:40:22,520 --> 00:40:24,850
Og så her har vi en viss størrelse.

748
00:40:24,850 --> 00:40:31,170
>> Og vanligvis, vil du holde
styr på hvor stor stabel din er

749
00:40:31,170 --> 00:40:36,180
fordi hva det kommer til å tillate
deg å gjøre er hvis du vet størrelsen,

750
00:40:36,180 --> 00:40:39,170
det tillater deg å si,
OK, jeg er på kapasitet?

751
00:40:39,170 --> 00:40:40,570
Kan jeg legge til noe mer?

752
00:40:40,570 --> 00:40:44,650
Og det forteller deg også
der toppen av stabelen din

753
00:40:44,650 --> 00:40:48,180
er slik at du vet hva du
faktisk kan ta av.

754
00:40:48,180 --> 00:40:51,760
Og det er faktisk kommer til å
være litt mer tydelig her.

755
00:40:51,760 --> 00:40:57,350
>> Så for push, en ting, hvis du
var stadig å implementere push,

756
00:40:57,350 --> 00:41:01,330
som jeg bare sa, din
stack har en begrenset størrelse, ikke sant?

757
00:41:01,330 --> 00:41:03,990
Vårt utvalg hadde en viss kapasitet.

758
00:41:03,990 --> 00:41:04,910
Det er en matrise.

759
00:41:04,910 --> 00:41:08,930
Det er en fast størrelse, så vi trenger å
sørge for at vi ikke setter mer

760
00:41:08,930 --> 00:41:11,950
inn i vårt utvalg enn vi
faktisk har plass til.

761
00:41:11,950 --> 00:41:16,900
>> Så når du oppretter en push
funksjon, første du gjør er å si, OK,

762
00:41:16,900 --> 00:41:18,570
har jeg plass i bunken min?

763
00:41:18,570 --> 00:41:23,330
Fordi hvis jeg ikke gjør det, beklager,
Jeg kan ikke lagre ditt element.

764
00:41:23,330 --> 00:41:28,980
Hvis jeg gjør det, så du vil lagre
den på toppen av bunken, ikke sant?

765
00:41:28,980 --> 00:41:31,325
>> Og dette er grunnen til at vi har
å holde orden på vår størrelse.

766
00:41:31,325 --> 00:41:35,290
Hvis vi ikke holder orden på vår størrelse,
vi vet ikke hvor du skal plassere den.

767
00:41:35,290 --> 00:41:39,035
Vi vet ikke hvor mange ting
er i vårt utvalg allerede.

768
00:41:39,035 --> 00:41:41,410
Som åpenbart finnes det måter
at kanskje du kunne gjøre det.

769
00:41:41,410 --> 00:41:44,610
Du kan initialisere alt til NULL
og deretter se etter den nyeste NULL,

770
00:41:44,610 --> 00:41:47,950
men en mye enklere ting er bare
å si, OK, holde styr på størrelse.

771
00:41:47,950 --> 00:41:51,840
Som jeg vet at jeg har fire elementer
i mitt utvalg, slik at den neste tingen

772
00:41:51,840 --> 00:41:55,930
at vi satt på, vi er
skal lagre på index 4.

773
00:41:55,930 --> 00:42:00,940
Og så, betyr selvfølgelig dette at
du har lastet skjøvet noe

774
00:42:00,940 --> 00:42:03,320
på stabelen din, du
ønsker å øke størrelsen

775
00:42:03,320 --> 00:42:08,880
slik at du vet hvor du er så
at du kan skyve flere ting på.

776
00:42:08,880 --> 00:42:12,730
>> Så hvis vi prøver å pop
noe av stabelen,

777
00:42:12,730 --> 00:42:16,072
hva som kan være det første
at vi ønsker å se etter?

778
00:42:16,072 --> 00:42:18,030
Du prøver å ta
noe av stabelen din.

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

780
00:42:21,710 --> 00:42:24,781
Er du sikker på at det er
noe i bunken din?

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

782
00:42:25,280 --> 00:42:26,894
Så hva kan vi ønsker å sjekke?

783
00:42:26,894 --> 00:42:27,810
>> PUBLIKUM: [uhørlig].

784
00:42:27,810 --> 00:42:29,880
SPEAKER 1: Sjekk for størrelsen?

785
00:42:29,880 --> 00:42:31,840
Størrelse.

786
00:42:31,840 --> 00:42:38,520
Så vi ønsker å sjekke for å se om
vår størrelse er større enn 0, OK?

787
00:42:38,520 --> 00:42:44,970
Og hvis det er, så vi ønsker å redusere
vår størrelse med 0 og returnere det.

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

789
00:42:45,840 --> 00:42:49,950
>> I det første ble en vi
skyve, dyttet den vi

790
00:42:49,950 --> 00:42:52,460
på størrelse og deretter oppdateres størrelse.

791
00:42:52,460 --> 00:42:57,850
I dette tilfellet er vi minske størrelsen
og deretter ta den av, plukker det

792
00:42:57,850 --> 00:42:58,952
fra vår array.

793
00:42:58,952 --> 00:42:59,826
Hvorfor kan vi gjøre det?

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

795
00:43:04,800 --> 00:43:11,811
Så hvis jeg har en ting på min stabel,
hva ville være min størrelse på det tidspunktet?

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

797
00:43:13,140 --> 00:43:15,180
>> Og hvor er elementet en lagret?

798
00:43:15,180 --> 00:43:17,621
På hvilken indeks?

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

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

801
00:43:19,060 --> 00:43:22,800
Så i dette tilfelle vi
alltid trenger å gjøre sure--

802
00:43:22,800 --> 00:43:27,630
stedet for å returnere
størrelse minus 1, fordi vi

803
00:43:27,630 --> 00:43:31,730
vet at våre elementet er
kommer til å bli lagret på en mindre

804
00:43:31,730 --> 00:43:34,705
hva vår størrelse er dette
bare tar vare på den.

805
00:43:34,705 --> 00:43:36,080
Det er en litt mer elegant måte.

806
00:43:36,080 --> 00:43:41,220
Og vi bare minske vår
størrelse og deretter returnere størrelse.

807
00:43:41,220 --> 00:43:42,330
Mmhmm?

808
00:43:42,330 --> 00:43:45,300
>> PUBLIKUM: Jeg antar bare generelt,
Hvorfor skulle dette datastruktur

809
00:43:45,300 --> 00:43:47,800
være gunstig?

810
00:43:47,800 --> 00:43:50,660
>> SPEAKER 1: Det avhenger av konteksten.

811
00:43:50,660 --> 00:43:57,420
Så for noen av teorien,
hvis du arbeider with-- OK,

812
00:43:57,420 --> 00:44:02,750
la meg se om det er en gunstig ett
som er fordelaktig til mer enn utenfor

813
00:44:02,750 --> 00:44:05,420
av CS.

814
00:44:05,420 --> 00:44:15,780
Med stabler, helst du trenger
å holde styr på noe som

815
00:44:15,780 --> 00:44:20,456
er den mest nylig lagt til er når
du kommer til å ønske å bruke en stabel.

816
00:44:20,456 --> 00:44:24,770
>> Og jeg kan ikke tenke på en god
eksempel på det akkurat nå.

817
00:44:24,770 --> 00:44:29,955
Men når den siste
ting er viktigst for deg,

818
00:44:29,955 --> 00:44:31,705
det er da en stabel
kommer til å være nyttig.

819
00:44:31,705 --> 00:44:35,797

820
00:44:35,797 --> 00:44:39,330
Jeg prøver å tenke hvis
det er en god en for dette.

821
00:44:39,330 --> 00:44:43,720
Hvis jeg tenker på et godt eksempel i neste
20 minutter, vil jeg definitivt si deg.

822
00:44:43,720 --> 00:44:49,455
>> Men alt i alt, hvis det er noe,
som jeg sa de fleste, der siste

823
00:44:49,455 --> 00:44:52,470
er viktigst, det er
der en stabel kommer inn i bildet.

824
00:44:52,470 --> 00:44:58,860
Mens køene er slags motsatt.

825
00:44:58,860 --> 00:44:59,870
Og alle de små hundene.

826
00:44:59,870 --> 00:45:00,890
Er ikke dette bra, ikke sant?

827
00:45:00,890 --> 00:45:03,299
Jeg føler at jeg burde
bare har en kanin video

828
00:45:03,299 --> 00:45:05,090
rett i midten av
seksjon for dere

829
00:45:05,090 --> 00:45:08,870
fordi dette er en intens delen.

830
00:45:08,870 --> 00:45:10,480
>> Så en kø.

831
00:45:10,480 --> 00:45:12,710
I utgangspunktet er en kø som en linje.

832
00:45:12,710 --> 00:45:15,780
Dere Jeg er sikker bruk dette hver dag,
akkurat som i våre spisesaler.

833
00:45:15,780 --> 00:45:18,160
Så vi må gå i
og få våre skuffer, jeg er

834
00:45:18,160 --> 00:45:21,260
at du må vente i kø
å sveipe eller få mat.

835
00:45:21,260 --> 00:45:24,650
>> Så forskjellen her
er at dette er FIFO.

836
00:45:24,650 --> 00:45:30,090
Så hvis LIFO ble sist inn, først
ut, er FIFO først inn, først ut.

837
00:45:30,090 --> 00:45:33,400
Så det er her hva du putter
på først er din viktigste.

838
00:45:33,400 --> 00:45:35,540
Så hvis du har ventet
i en line-- kan du

839
00:45:35,540 --> 00:45:39,130
tenk hvis du gikk til
gå få den nye iPhone

840
00:45:39,130 --> 00:45:42,800
og det var en stabel der
siste personen i kø fikk det først,

841
00:45:42,800 --> 00:45:44,160
folk ville drepe hverandre.

842
00:45:44,160 --> 00:45:49,800
>> Så FIFO, vi er alle veldig kjent
med i den virkelige verden her,

843
00:45:49,800 --> 00:45:54,930
og det hele har å gjøre med faktisk
slags gjenskape hele denne linjen

844
00:45:54,930 --> 00:45:56,900
og kø struktur.

845
00:45:56,900 --> 00:46:02,390
Så mens med stabelen,
vi har push og pop.

846
00:46:02,390 --> 00:46:06,440
Med en kø, har vi
enqueue og dequeue.

847
00:46:06,440 --> 00:46:10,910
Så enqueue utgangspunktet betyr
sette den inn på baksiden,

848
00:46:10,910 --> 00:46:13,680
og dequeue del ta
ut fra forsiden.

849
00:46:13,680 --> 00:46:18,680
Så vår datastruktur er en
litt mer komplisert.

850
00:46:18,680 --> 00:46:21,060
Vi har en annen ting å holde styr på.

851
00:46:21,060 --> 00:46:25,950
>> Så uten hode, denne
er akkurat en stabel, ikke sant?

852
00:46:25,950 --> 00:46:27,900
Dette er den samme struktur som en stabel.

853
00:46:27,900 --> 00:46:32,480
Det eneste annerledes nå er vi
har dette hodet, som hva tror du

854
00:46:32,480 --> 00:46:34,272
kommer til å holde styr på?

855
00:46:34,272 --> 00:46:35,510
>> PUBLIKUM: Den første.

856
00:46:35,510 --> 00:46:38,685
>> SPEAKER 1: Høyre, den
første at vi satt i.

857
00:46:38,685 --> 00:46:41,130
Lederen for vår køen.

858
00:46:41,130 --> 00:46:42,240
Den som er først i køen.

859
00:46:42,240 --> 00:46:45,300

860
00:46:45,300 --> 00:46:49,420
All right, så hvis vi gjør enqueue.

861
00:46:49,420 --> 00:46:52,720

862
00:46:52,720 --> 00:46:55,920
Igjen, med hvilken som helst av
Disse datastrukturer,

863
00:46:55,920 --> 00:46:59,760
siden vi har å gjøre med en matrise,
vi trenger å sjekke om vi har plass.

864
00:46:59,760 --> 00:47:03,290
>> Dette er typen som meg forteller
dere, hvis du åpner en fil,

865
00:47:03,290 --> 00:47:04,760
du må sjekke for null.

866
00:47:04,760 --> 00:47:08,330
Med noen av disse stabler
og køer, må du

867
00:47:08,330 --> 00:47:13,420
for å se om det er plass fordi vi er
arbeider med en fast størrelse array,

868
00:47:13,420 --> 00:47:16,030
som vi ser her-- 0, 1 helt opp til 5.

869
00:47:16,030 --> 00:47:20,690
Så det vi gjør i dette tilfellet er sjekk
for å se om vi fortsatt har plass.

870
00:47:20,690 --> 00:47:23,110
Er vår størrelse mindre enn kapasiteten?

871
00:47:23,110 --> 00:47:28,480
>> I så fall må vi lagre den på
halen og vi oppdaterer vår størrelse.

872
00:47:28,480 --> 00:47:30,250
Så hva kan halen være i dette tilfellet?

873
00:47:30,250 --> 00:47:32,360
Det er ikke eksplisitt skrevet ut.

874
00:47:32,360 --> 00:47:33,380
Hvordan ville vi lagre det?

875
00:47:33,380 --> 00:47:34,928
Hva ville halen være?

876
00:47:34,928 --> 00:47:38,600

877
00:47:38,600 --> 00:47:40,190
>> Så la oss gå gjennom dette eksemplet.

878
00:47:40,190 --> 00:47:44,590
Så dette er en matrise av størrelse 6, ikke sant?

879
00:47:44,590 --> 00:47:49,220
Og vi har akkurat nå, er vår størrelse 5.

880
00:47:49,220 --> 00:47:55,240
Og når vi setter det i, det kommer
å gå inn i den femte indeksen, ikke sant?

881
00:47:55,240 --> 00:47:57,030
Så lagre på halen.

882
00:47:57,030 --> 00:48:05,600
>> En annen måte å skrive halen ville bare
være vårt utvalg på indeks for størrelsen, ikke sant?

883
00:48:05,600 --> 00:48:07,560
Dette er størrelse 5.

884
00:48:07,560 --> 00:48:11,490
Neste ting kommer til å gå inn i fem.

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
Det blir litt mer komplisert
når vi begynner å rote med hodet.

888
00:48:16,350 --> 00:48:17,060
Ja?

889
00:48:17,060 --> 00:48:20,090
>> PUBLIKUM: Betyr det at vi
ville ha erklært en matrise som

890
00:48:20,090 --> 00:48:23,880
var fem elementer lang og
da vi legger på det?

891
00:48:23,880 --> 00:48:24,730
>> SPEAKER 1: Nei.

892
00:48:24,730 --> 00:48:27,560
Så i dette tilfelle, er dette en stabel.

893
00:48:27,560 --> 00:48:31,760
Dette ville bli erklært
som en matrise av størrelse 6.

894
00:48:31,760 --> 00:48:37,120
Og i dette tilfellet, vi
har bare én plass til venstre.

895
00:48:37,120 --> 00:48:42,720
>> OK, så en ting er i dette
tilfelle, hvis hodet er på 0,

896
00:48:42,720 --> 00:48:45,270
da vi bare kan legge den på størrelse.

897
00:48:45,270 --> 00:48:51,020
Men det blir litt mer komplisert
fordi faktisk, de

898
00:48:51,020 --> 00:48:52,840
ikke har et lysbilde
for dette, så jeg kommer

899
00:48:52,840 --> 00:48:56,670
å trekke en fordi det ikke er
fullt så enkelt når du

900
00:48:56,670 --> 00:48:59,230
begynne å bli kvitt ting.

901
00:48:59,230 --> 00:49:03,920
Så mens med en stabel
du bare trenger

902
00:49:03,920 --> 00:49:08,920
å bekymre deg for hva størrelsen er
når du legger noe på,

903
00:49:08,920 --> 00:49:15,710
med en kø må du også gjøre
sikker på at hodet ditt er regnskapsført,

904
00:49:15,710 --> 00:49:20,760
fordi en kul ting om køer
er at hvis du ikke er på kapasitet,

905
00:49:20,760 --> 00:49:23,040
du kan faktisk gjøre det brytes rundt.

906
00:49:23,040 --> 00:49:28,810
>> OK, så en thing-- oh,
Dette er forferdelig kritt.

907
00:49:28,810 --> 00:49:31,815
En ting å vurdere er tilfelle.

908
00:49:31,815 --> 00:49:35,514

909
00:49:35,514 --> 00:49:37,140
Vi vil bare gjøre fem.

910
00:49:37,140 --> 00:49:41,810
OK, så vi kommer til å
si hodet er her.

911
00:49:41,810 --> 00:49:46,140
Dette er 0, 1, 2, 3, 4.

912
00:49:46,140 --> 00:49:54,210
>> Hodet er der, og
Vennligst ha ting i dem.

913
00:49:54,210 --> 00:49:58,340
Og vi ønsker å legge noe i, ikke sant?

914
00:49:58,340 --> 00:50:01,170
Så ting som vi trenger for å
vet er at hodet er alltid

915
00:50:01,170 --> 00:50:05,620
kommer til å flytte denne måten og
deretter sløyfe tilbake rundt, OK?

916
00:50:05,620 --> 00:50:10,190
>> Så denne køen har plass, ikke sant?

917
00:50:10,190 --> 00:50:13,950
Den har plass i begynnelsen,
slag av det motsatte av dette.

918
00:50:13,950 --> 00:50:17,920
Så det vi trenger å gjøre, er vi
trenger å beregne halen.

919
00:50:17,920 --> 00:50:20,530
Hvis du vet at din
hodet har ikke flyttet, hale

920
00:50:20,530 --> 00:50:24,630
er bare din matrise på
indeksen av størrelsen.

921
00:50:24,630 --> 00:50:30,000
>> Men i virkeligheten, hvis du bruker en kø,
hodet er trolig blir oppdatert.

922
00:50:30,000 --> 00:50:33,890
Så hva du trenger å gjøre er
faktisk beregne halen.

923
00:50:33,890 --> 00:50:39,990
Så det vi gjør er denne formelen
her, som jeg kommer til å la deg

924
00:50:39,990 --> 00:50:42,680
gutta tenke på, og
så får vi snakke om det.

925
00:50:42,680 --> 00:50:49,567

926
00:50:49,567 --> 00:50:50,400
Så dette er kapasiteten.

927
00:50:50,400 --> 00:50:55,890

928
00:50:55,890 --> 00:50:59,660
>> Så dette vil faktisk
gi deg en måte å gjøre det.

929
00:50:59,660 --> 00:51:03,205

930
00:51:03,205 --> 00:51:04,330
Fordi i dette tilfelle, hva?

931
00:51:04,330 --> 00:51:09,205
Vårt hovedkontor er på 1, er vår størrelse fire.

932
00:51:09,205 --> 00:51:11,760

933
00:51:11,760 --> 00:51:18,490
Hvis vi mod som med 5, får vi 0,
som er der vi skal legge den inn.

934
00:51:18,490 --> 00:51:23,320

935
00:51:23,320 --> 00:51:26,080
>> Så deretter i det neste tilfelle,
hvis vi skulle gjøre dette,

936
00:51:26,080 --> 00:51:33,390
vi sier, OK, la oss dequeue noe.

937
00:51:33,390 --> 00:51:34,390
Vi dequeue dette.

938
00:51:34,390 --> 00:51:37,740
Vi tar ut dette elementet, ikke sant?

939
00:51:37,740 --> 00:51:47,930
>> Og nå vårt hode peker her,
og vi ønsker å legge inn en annen ting.

940
00:51:47,930 --> 00:51:52,470
Dette er i utgangspunktet
iden av vår linje, ikke sant?

941
00:51:52,470 --> 00:51:55,450
Køer kan vikle rundt array.

942
00:51:55,450 --> 00:51:57,310
Det er en av de viktigste forskjellene.

943
00:51:57,310 --> 00:51:58,780
Stabler, kan du ikke gjøre dette.

944
00:51:58,780 --> 00:52:01,140
>> Med køer, kan du
fordi alt som teller

945
00:52:01,140 --> 00:52:03,940
er at du vet hva
ble lagt til sist.

946
00:52:03,940 --> 00:52:10,650
Siden alt kommer til å bli lagt i
denne venstrerettet retning, i dette tilfellet,

947
00:52:10,650 --> 00:52:16,480
og deretter vikle rundt, kan du
fortsette å sette inn nye elementer

948
00:52:16,480 --> 00:52:18,830
på forsiden av rekken
fordi det er egentlig ikke

949
00:52:18,830 --> 00:52:20,640
forsiden av rekken lenger.

950
00:52:20,640 --> 00:52:26,320
Du kan tenke på begynnelsen av
matrise som hvor hodet ditt faktisk er.

951
00:52:26,320 --> 00:52:29,710
>> Så denne formelen er hvordan
du beregne din halen.

952
00:52:29,710 --> 00:52:32,780

953
00:52:32,780 --> 00:52:35,610
Betyr det fornuftig?

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, og deretter
dere har 10 minutter

957
00:52:44,040 --> 00:52:48,840
å stille meg oppklarende spørsmål
du vil, fordi jeg vet det er sprøtt.

958
00:52:48,840 --> 00:52:51,980
>> Greit, så i samme måte--
Jeg vet ikke om dere lagt merke til,

959
00:52:51,980 --> 00:52:53,450
men CS handler om mønstre.

960
00:52:53,450 --> 00:52:57,370
Ting er ganske mye det
samme, bare med små tilpasninger.

961
00:52:57,370 --> 00:52:58,950
Så samme her.

962
00:52:58,950 --> 00:53:04,040
Vi må sjekke for å se om vi faktisk
har noe i vår kø, ikke sant?

963
00:53:04,040 --> 00:53:05,960
Sier, OK, er vår størrelse større enn 0?

964
00:53:05,960 --> 00:53:06,730
Cool.

965
00:53:06,730 --> 00:53:10,690
>> Hvis vi gjør det, så flytter vi vårt hode, som
er hva jeg nettopp demonstrert her.

966
00:53:10,690 --> 00:53:13,870
Vi oppdaterer vårt hode til å være en mer.

967
00:53:13,870 --> 00:53:18,390
Og da vi minske vår
størrelse og tilbake i elementet.

968
00:53:18,390 --> 00:53:21,000

969
00:53:21,000 --> 00:53:26,250
>> Det er mye mer konkret
kode på study.cs50.net,

970
00:53:26,250 --> 00:53:29,440
og jeg anbefaler å gå
gjennom det hvis du har tid,

971
00:53:29,440 --> 00:53:30,980
selv om det bare er en pseudo-kode.

972
00:53:30,980 --> 00:53:35,980
Og hvis dere ønsker å snakke gjennom
at med meg en på en, kan du gi meg

973
00:53:35,980 --> 00:53:37,500
vet.

974
00:53:37,500 --> 00:53:38,770
Jeg vil gjerne.

975
00:53:38,770 --> 00:53:42,720
Datastrukturer, hvis
du tar CS 124, vil du

976
00:53:42,720 --> 00:53:47,830
vet at datastrukturer får veldig
moro, og dette er bare begynnelsen.

977
00:53:47,830 --> 00:53:50,350
>> Så jeg vet det er vanskelig.

978
00:53:50,350 --> 00:53:51,300
Det er OK.

979
00:53:51,300 --> 00:53:52,410
Vi sliter.

980
00:53:52,410 --> 00:53:53,630
Jeg gjør det fortsatt.

981
00:53:53,630 --> 00:53:56,660
Så ikke bekymre deg for mye om det.

982
00:53:56,660 --> 00:54:02,390
>> Men det er i utgangspunktet din
lynkurs i datastrukturer.

983
00:54:02,390 --> 00:54:03,400
Jeg vet det er mye.

984
00:54:03,400 --> 00:54:06,860
Er det noe som vi
ønsker å gå over igjen?

985
00:54:06,860 --> 00:54:09,400
Noe vi ønsker å snakke gjennom?

986
00:54:09,400 --> 00:54:10,060
Ja?

987
00:54:10,060 --> 00:54:16,525
>> PUBLIKUM: For det eksempelet, så
den nye halen er på 0 over det?

988
00:54:16,525 --> 00:54:17,150
SPEAKER 1: Ja.

989
00:54:17,150 --> 00:54:18,230
PUBLIKUM: OK.

990
00:54:18,230 --> 00:54:24,220
Så da går gjennom,
du ville ha en pluss 4 or--

991
00:54:24,220 --> 00:54:27,671
>> SPEAKER 1: Så du sa,
når vi ønsker å gå gjøre dette igjen?

992
00:54:27,671 --> 00:54:28,296
PUBLIKUM: Yeah.

993
00:54:28,296 --> 00:54:38,290
Så hvis du skulle finne out-- hvor er
du beregne halen fra i det?

994
00:54:38,290 --> 00:54:44,260
>> SPEAKER 1: Så halen
var in-- Jeg endret dette.

995
00:54:44,260 --> 00:54:52,010
Så i dette eksempelet her, dette var
matrisen vi ser på, OK?

996
00:54:52,010 --> 00:54:54,670
Så vi har ting i 1, 2, 3 og 4.

997
00:54:54,670 --> 00:55:05,850
Så vi har vårt hode er lik 1 på
dette punktet, og er lik 4 vår størrelse

998
00:55:05,850 --> 00:55:07,050
på dette punktet, ikke sant?

999
00:55:07,050 --> 00:55:08,960
>> Du er alle enige om det er tilfelle?

1000
00:55:08,960 --> 00:55:14,620
Så vi gjør hodet pluss størrelse, som
gir oss fem, og da vi mod med 5.

1001
00:55:14,620 --> 00:55:20,690
Vi får 0, som forteller oss at 0 er
hvor er vår hale, hvor vi har plass.

1002
00:55:20,690 --> 00:55:22,010
>> PUBLIKUM: Hva er en cap?

1003
00:55:22,010 --> 00:55:23,520
>> SPEAKER 1: Kapasiteten.

1004
00:55:23,520 --> 00:55:24,020
Unnskyld.

1005
00:55:24,020 --> 00:55:29,640
Så det er størrelsen på array.

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
>> PUBLIKUM: [uhørlig] før
vi tilbake elementet?

1009
00:55:39,210 --> 00:55:46,270
>> SPEAKER 1: Så vi flytter
hodet eller returnere øyeblikket?

1010
00:55:46,270 --> 00:55:52,680
Så hvis vi flytter en, minske størrelsen?

1011
00:55:52,680 --> 00:55:54,150
Hold på.

1012
00:55:54,150 --> 00:55:55,770
Jeg definitivt glemte en annen.

1013
00:55:55,770 --> 00:56:00,646

1014
00:56:00,646 --> 00:56:01,990
Never mind.

1015
00:56:01,990 --> 00:56:04,980
Det er ikke en annen formel.

1016
00:56:04,980 --> 00:56:09,980
Ja, vil du ønsker å returnere
hodet og deretter flytte den tilbake.

1017
00:56:09,980 --> 00:56:13,270
>> PUBLIKUM: OK, fordi på dette
punkt, var hodet på 0,

1018
00:56:13,270 --> 00:56:18,452
og deretter du ønsker å returnere
indeks 0 og deretter lage head 1?

1019
00:56:18,452 --> 00:56:19,870
>> SPEAKER 1: Høyre.

1020
00:56:19,870 --> 00:56:22,820
Jeg tror det er en annen
formel typen som dette.

1021
00:56:22,820 --> 00:56:26,970
Jeg har ikke den på toppen hodet mitt som
Jeg ønsker ikke å gi deg feil en.

1022
00:56:26,970 --> 00:56:35,470
Men jeg tror det er helt gyldig til
si, OK, lagre denne element-- uansett

1023
00:56:35,470 --> 00:56:40,759
hodets element er-- minske din
størrelse, bevege hodet over, og avkastningen

1024
00:56:40,759 --> 00:56:41,800
uansett hva det elementet er.

1025
00:56:41,800 --> 00:56:44,760
Det er helt gyldig.

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
Jeg føler at dette ikke er
som most-- du ikke

1029
00:56:53,560 --> 00:56:55,740
kommer til å gå ut herfra
som, ja, jeg vet prøver.

1030
00:56:55,740 --> 00:56:56,880
Jeg fikk det hele.

1031
00:56:56,880 --> 00:56:57,670
Det er OK.

1032
00:56:57,670 --> 00:57:00,200
Jeg lover.

1033
00:57:00,200 --> 00:57:05,240
Men datastrukturer er noe som
det tar mye tid å venne seg til.

1034
00:57:05,240 --> 00:57:10,010
Sannsynligvis en av de vanskeligste
ting, tror jeg, i løpet.

1035
00:57:10,010 --> 00:57:15,330
>> Så det tar definitivt
repetisjon og ser at-- jeg

1036
00:57:15,330 --> 00:57:20,050
gjorde egentlig ikke vet lenkede lister
før jeg gjorde altfor mye med dem,

1037
00:57:20,050 --> 00:57:22,550
på samme måte som gjorde ikke jeg
virkelig forstå pekere

1038
00:57:22,550 --> 00:57:27,040
før jeg har måtte lære det for to
år og gjøre mine egne psets med det.

1039
00:57:27,040 --> 00:57:28,990
Det tar mye gjentakelse og tid.

1040
00:57:28,990 --> 00:57:32,600
Og til slutt, vil det slags klikk.

1041
00:57:32,600 --> 00:57:36,320
>> Men i mellomtiden, hvis du har en slags
fra et høyt nivå forståelse av hva

1042
00:57:36,320 --> 00:57:39,321
disse gjør, deres fordeler
og cons-- som er hva

1043
00:57:39,321 --> 00:57:41,820
vi virkelig har en tendens til å understreke,
spesielt i intro kurs.

1044
00:57:41,820 --> 00:57:45,511
Liker, hvorfor skulle vi bruke
en prøve over en array?

1045
00:57:45,511 --> 00:57:48,010
Liker, hva er de positive
og negativer på hver av dem?

1046
00:57:48,010 --> 00:57:51,610
>> Og forstå avveiningene
mellom hver av disse strukturene

1047
00:57:51,610 --> 00:57:54,910
er det som er mye viktigere akkurat nå.

1048
00:57:54,910 --> 00:57:58,140
Det kan være en gal
spørsmål eller to som er

1049
00:57:58,140 --> 00:58:03,710
kommer til å be deg om å implementere skyve eller
implementere pop eller enqueue og dequeue.

1050
00:58:03,710 --> 00:58:07,340
Men for det meste, som har som
høyere nivå forståelse og mer

1051
00:58:07,340 --> 00:58:09,710
av en intuitiv forståelse er
viktigere enn faktisk

1052
00:58:09,710 --> 00:58:11,250
å være i stand til å gjennomføre det.

1053
00:58:11,250 --> 00:58:14,880
>> Det ville være virkelig fantastisk hvis alle dere
kunne gå ut og gå gjennomføre en prøve,

1054
00:58:14,880 --> 00:58:19,720
men vi forstår det er ikke nødvendigvis
den mest fornuftige tingen akkurat nå.

1055
00:58:19,720 --> 00:58:23,370
Men du kan i PSet, hvis du vil
til, og da vil du få praksis

1056
00:58:23,370 --> 00:58:27,200
og så kanskje du vil
virkelig forstå det.

1057
00:58:27,200 --> 00:58:27,940
Ja?

1058
00:58:27,940 --> 00:58:30,440
>> PUBLIKUM: OK, så hvilke som er
vi ment å bruke i PSet?

1059
00:58:30,440 --> 00:58:31,916
Trenger jeg å bruke en av dem?

1060
00:58:31,916 --> 00:58:32,540
SPEAKER 1: Ja.

1061
00:58:32,540 --> 00:58:34,199
Så du har ditt valg.

1062
00:58:34,199 --> 00:58:36,740
Jeg antar i dette tilfellet, kan vi
snakke om PSet litt

1063
00:58:36,740 --> 00:58:40,480
fordi jeg kjørte gjennom disse.

1064
00:58:40,480 --> 00:58:47,779
Så i din PSet, har du din
Valget av prøver eller hash tabeller.

1065
00:58:47,779 --> 00:58:49,570
Noen mennesker vil prøve
og bruke blomst filtre,

1066
00:58:49,570 --> 00:58:51,840
men de teknisk sett ikke er riktige.

1067
00:58:51,840 --> 00:58:55,804
På grunn av deres natur probabilistisk,
de gir falske positiver noen ganger.

1068
00:58:55,804 --> 00:58:57,095
De er kule titt inn, though.

1069
00:58:57,095 --> 00:58:59,030
Anbefale ser
på dem minst.

1070
00:58:59,030 --> 00:59:03,260
Men du har ditt valg
mellom en hash-tabell og en prøve.

1071
00:59:03,260 --> 00:59:06,660
Og det kommer til å være der
du legger i ordboken.

1072
00:59:06,660 --> 00:59:09,230
>> Og du må velge
din hash-funksjon,

1073
00:59:09,230 --> 00:59:13,420
må du velge hvor mange
skuffer du har, og det vil variere.

1074
00:59:13,420 --> 00:59:17,440
Som hvis du har flere bøtter,
kanskje det vil kjøre fortere.

1075
00:59:17,440 --> 00:59:22,790
Men kanskje du kaster bort en
mye plass på den måten, skjønt.

1076
00:59:22,790 --> 00:59:26,320
Du må finne ut av det.

1077
00:59:26,320 --> 00:59:27,140
Mmhmm?

1078
00:59:27,140 --> 00:59:29,875
>> PUBLIKUM: Du sa tidligere at
vi kan bruke andre hash funksjoner,

1079
00:59:29,875 --> 00:59:31,750
at vi ikke trenger å
opprette en hash-funksjon?

1080
00:59:31,750 --> 00:59:32,666
>> SPEAKER 1: Ja, ikke sant.

1081
00:59:32,666 --> 00:59:38,150
Så bokstavelig talt for din hash-funksjon,
som google "hash-funksjon"

1082
00:59:38,150 --> 00:59:40,770
og ser etter noen kule de.

1083
00:59:40,770 --> 00:59:43,250
Du er ikke forventet å bygge
dine egne hash funksjoner.

1084
00:59:43,250 --> 00:59:46,100
Folk bruker deres
teser om disse tingene.

1085
00:59:46,100 --> 00:59:50,250
>> Så ikke bekymre deg om å bygge din egen.

1086
00:59:50,250 --> 00:59:53,350
Finn en på nettet til å begynne med.

1087
00:59:53,350 --> 00:59:56,120
Noen av dem må du
manipulere litt

1088
00:59:56,120 --> 00:59:59,430
å sørge for at returtyper matche opp
og whatnot, så i begynnelsen,

1089
00:59:59,430 --> 01:00:02,420
Jeg vil anbefale å bruke noe
veldig lett at kanskje bare

1090
01:00:02,420 --> 01:00:04,680
hashes på den første bokstaven.

1091
01:00:04,680 --> 01:00:08,760
Og så når du har det arbeidende,
innlemme et kjøligere hash-funksjon.

1092
01:00:08,760 --> 01:00:09,260
Mmhmm?

1093
01:00:09,260 --> 01:00:13,020
>> PUBLIKUM: Ville en prøve være eller
effektive, men bare vanskeligere å, like--

1094
01:00:13,020 --> 01:00:15,880
>> SPEAKER 1: Så en prøve, tror jeg,
er intuitivt vanskelig å implementere

1095
01:00:15,880 --> 01:00:18,310
men er veldig rask.

1096
01:00:18,310 --> 01:00:20,620
Men tar mer plass.

1097
01:00:20,620 --> 01:00:25,270
Igjen, kan du optimalisere både av de i
forskjellige måter og det finnes måter to--

1098
01:00:25,270 --> 01:00:26,770
PUBLIKUM: Hvordan skal vi gradert på dette?

1099
01:00:26,770 --> 01:00:27,540
Betyr det matter--

1100
01:00:27,540 --> 01:00:29,164
>> SPEAKER 1: Så du gradert vanlig måte.

1101
01:00:29,164 --> 01:00:31,330
Du kommer til å bli gradert på design.

1102
01:00:31,330 --> 01:00:36,020
Uansett hvordan du gjør det, vil du
sørge for at det er like elegant som det kan være

1103
01:00:36,020 --> 01:00:38,610
og så effektiv som det kan være.

1104
01:00:38,610 --> 01:00:41,950
Men hvis du velger en prøve eller hash
bord, så lenge det virker,

1105
01:00:41,950 --> 01:00:45,350
Vi er fornøyd med det.

1106
01:00:45,350 --> 01:00:48,370
Og hvis du bruker noe som hashes
på den første bokstaven, er det helt greit,

1107
01:00:48,370 --> 01:00:51,410
som kanskje liker design-messig.

1108
01:00:51,410 --> 01:00:53,410
Vi er også nå
punkt i denne semester--

1109
01:00:53,410 --> 01:00:55,340
Jeg vet ikke om du
Gutta noticed-- hvis du er

1110
01:00:55,340 --> 01:00:58,780
PSet karakterer avta litt
på grunn av design og whatnot,

1111
01:00:58,780 --> 01:00:59,900
det er helt greit.

1112
01:00:59,900 --> 01:01:02,960
Det er å få til et punkt hvor din
programmer blir mer komplisert.

1113
01:01:02,960 --> 01:01:04,830
Det er flere steder
du kan bli bedre på.

1114
01:01:04,830 --> 01:01:06,370
>> Så det er helt normalt.

1115
01:01:06,370 --> 01:01:08,810
Det er ikke det at du er
gjør verre på PSet.

1116
01:01:08,810 --> 01:01:11,885
Det er bare vi blir hardere på deg nå.

1117
01:01:11,885 --> 01:01:13,732
Så alle som føler det.

1118
01:01:13,732 --> 01:01:14,940
Jeg bare gradert alle dine psets.

1119
01:01:14,940 --> 01:01:16,490
Jeg vet at alle føler det.

1120
01:01:16,490 --> 01:01:19,600
>> Så ikke vær bekymret for det.

1121
01:01:19,600 --> 01:01:23,580
Og hvis du har noen spørsmål om
tidligere psets eller måter du kan forbedre,

1122
01:01:23,580 --> 01:01:27,760
Jeg prøver og kommentere den spesifikke
steder, men noen ganger er det for sent

1123
01:01:27,760 --> 01:01:30,840
og jeg blir lei.

1124
01:01:30,840 --> 01:01:34,885
Er det noen andre ting
om datastrukturer?

1125
01:01:34,885 --> 01:01:37,510
Jeg er sikker på at dere egentlig ikke
ønsker å snakke om dem lenger,

1126
01:01:37,510 --> 01:01:42,650
men hvis det er, er jeg glad for å
gå over dem, samt noe

1127
01:01:42,650 --> 01:01:45,580
fra forelesning denne siste
uke eller forrige uke.

1128
01:01:45,580 --> 01:01:51,580
>> Jeg vet at forrige uke var all anmeldelse, så
vi kan ha hoppet over noen gjennomgang

1129
01:01:51,580 --> 01:01:54,190
fra forelesning.

1130
01:01:54,190 --> 01:01:58,230
Eventuelle andre spørsmål kan jeg svare?

1131
01:01:58,230 --> 01:01:59,350
OK, greit.

1132
01:01:59,350 --> 01:02:02,400
Vel, dere får ut 15 minutter for tidlig.

1133
01:02:02,400 --> 01:02:08,370
>> Jeg håper dette var semi-nyttig i det minste,
og jeg vil se dere neste uke,

1134
01:02:08,370 --> 01:02:12,150
eller torsdag kontortid.

1135
01:02:12,150 --> 01:02:15,285
Er det forespørsler om snacks
for neste uke, det er tingen?

1136
01:02:15,285 --> 01:02:17,459
Fordi jeg glemte godteri i dag.

1137
01:02:17,459 --> 01:02:19,750
Og jeg tok godteri sist
uke, men det var Columbus Day,

1138
01:02:19,750 --> 01:02:25,400
så det var som seks personer som
hadde fire poser med godteri til seg selv.

1139
01:02:25,400 --> 01:02:28,820
Jeg kan bringe Starbursts
igjen hvis du vil.

1140
01:02:28,820 --> 01:02:29,580
Starbursts?

1141
01:02:29,580 --> 01:02:32,250
OK, høres bra ut.

1142
01:02:32,250 --> 01:02:35,050
Ha en flott dag, folkens.

1143
01:02:35,050 --> 01:02:39,510