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

2
00:00:00,500 --> 00:00:05,120
[MUSIK SPELA]

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

4
00:00:12,026 --> 00:00:12,900
TALARE 1: Okej.

5
00:00:12,900 --> 00:00:14,600
Alla välkomna tillbaka till avsnitt.

6
00:00:14,600 --> 00:00:18,660
Jag hoppas att ni alla är framgångsrikt
återhämtat sig från din frågesport

7
00:00:18,660 --> 00:00:19,510
från förra veckan.

8
00:00:19,510 --> 00:00:22,564
Jag vet att det är lite galet ibland.

9
00:00:22,564 --> 00:00:25,230
Som jag sa tidigare, om du är
inom standardavvikelsen,

10
00:00:25,230 --> 00:00:28,188
egentligen inte oroa dig för det, i synnerhet
för en mindre bekväm sektion.

11
00:00:28,188 --> 00:00:30,230
Det handlar om var du ska vara.

12
00:00:30,230 --> 00:00:32,850
>> Om du gjorde bra, så häftigt.

13
00:00:32,850 --> 00:00:33,650
Kudos till dig.

14
00:00:33,650 --> 00:00:36,149
Och om du känner att du behöver
lite mer hjälp,

15
00:00:36,149 --> 00:00:38,140
tveka inte att nå
ut till någon av TF: er.

16
00:00:38,140 --> 00:00:40,030
Vi är alla här för att hjälpa.

17
00:00:40,030 --> 00:00:40,960
>> Det är därför vi undervisar.

18
00:00:40,960 --> 00:00:44,550
Det är därför jag är här varje måndag för dig
killar och på kontoret timmar på torsdagar.

19
00:00:44,550 --> 00:00:48,130
Så är du välkommen att låta mig veta
om du är orolig för vad som helst

20
00:00:48,130 --> 00:00:52,450
eller om det finns något på frågesport
att du verkligen vill ta itu med.

21
00:00:52,450 --> 00:00:56,940
>> Så dagordningen för idag
allt om datastrukturer.

22
00:00:56,940 --> 00:01:01,520
Några av dessa är bara kommer att bli precis
att få dig förtrogen med dessa.

23
00:01:01,520 --> 00:01:04,870
Du kanske aldrig genomföra
dem i denna klass.

24
00:01:04,870 --> 00:01:08,690
Några av dem kommer du,
som för din speller pset.

25
00:01:08,690 --> 00:01:11,380
>> Du har ditt val
mellan hashtabeller och försök.

26
00:01:11,380 --> 00:01:13,680
Så vi kommer definitivt att gå över dem.

27
00:01:13,680 --> 00:01:18,690
Det kommer att bli definitivt mer av slag
av ett avsnitt på hög nivå i dag, men,

28
00:01:18,690 --> 00:01:22,630
eftersom det finns en hel del av dem, och om
Vi gick in på detaljer implementerings

29
00:01:22,630 --> 00:01:26,490
På alla dessa, vi skulle inte
ens få igenom länkade listor

30
00:01:26,490 --> 00:01:28,520
och kanske lite hashtabeller.

31
00:01:28,520 --> 00:01:31,200
>> Så ha tålamod med mig.

32
00:01:31,200 --> 00:01:33,530
Vi kommer inte att göra
så mycket kodning denna gång.

33
00:01:33,530 --> 00:01:36,870
Om du har några frågor om det
eller om du vill se det genomfört

34
00:01:36,870 --> 00:01:39,260
eller prova själv,
Jag rekommenderar definitivt

35
00:01:39,260 --> 00:01:44,250
kommer att study.cs50.net, vilket
har exempel på alla dessa.

36
00:01:44,250 --> 00:01:46,400
Det kommer att ha mina Powerpoints
med de anteckningar som vi

37
00:01:46,400 --> 00:01:50,860
tenderar att använda såväl som viss programmering
övningar, speciellt för saker

38
00:01:50,860 --> 00:01:55,250
som länkade listor och binära
träd stackar och köer.

39
00:01:55,250 --> 00:01:59,590
Så lite mer hög nivå, vilket
kan vara trevligt för er.

40
00:01:59,590 --> 00:02:01,320
>> Så med det, ska vi komma igång.

41
00:02:01,320 --> 00:02:03,060
Och även, yes-- frågesporter.

42
00:02:03,060 --> 00:02:06,550
Jag tror att de flesta av er som är i
min avdelning har dina frågesporter,

43
00:02:06,550 --> 00:02:12,060
men någon kommer in eller av någon anledning
inte gör det, de är här i fronten.

44
00:02:12,060 --> 00:02:12,740
>> Så länkade listor.

45
00:02:12,740 --> 00:02:15,650
Jag vet att den här typen av går
att backa innan din frågesport.

46
00:02:15,650 --> 00:02:17,940
Det var veckan innan
att vi lärt oss om detta.

47
00:02:17,940 --> 00:02:21,040
Men i detta fall, vi ska bara
gå lite mer på djupet.

48
00:02:21,040 --> 00:02:25,900
>> Så varför skulle vi välja en
lista kopplad över en array?

49
00:02:25,900 --> 00:02:27,130
Det som skiljer dem?

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

51
00:02:27,630 --> 00:02:30,464
>> PUBLIK: Du kan expandera en länkad
lista kontra en arrays fast storlek.

52
00:02:30,464 --> 00:02:31,171
TALARE 1: Rätt.

53
00:02:31,171 --> 00:02:33,970
En array har fast storlek medan en
länkad lista har en variabel storlek.

54
00:02:33,970 --> 00:02:36,970
Så om vi inte vet hur
mycket vi vill lagra,

55
00:02:36,970 --> 00:02:39,880
en länkad lista ger oss en stor
sätt att göra det eftersom vi kan bara

56
00:02:39,880 --> 00:02:43,730
lägga på en annan nod och lägg på
annan nod och lägga på en annan nod.

57
00:02:43,730 --> 00:02:45,750
Men vad som kan vara en kompromiss?

58
00:02:45,750 --> 00:02:49,521
Kommer någon ihåg avvägningen
mellan arrayer och länkade listor?

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

60
00:02:50,020 --> 00:02:51,460
>> PUBLIK: Du måste
gå igenom hela vägen

61
00:02:51,460 --> 00:02:53,738
via den länkade listan
hitta ett element i en lista.

62
00:02:53,738 --> 00:02:55,570
I en array, kan du
bara hitta ett element.

63
00:02:55,570 --> 00:02:56,278
>> TALARE 1: Rätt.

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

65
00:02:57,120 --> 00:02:58,500
>> PUBLIK: [OHÖRBAR].

66
00:02:58,500 --> 00:03:01,090
>> TALARE 1: Med matriser, vi har
vad som kallas random access.

67
00:03:01,090 --> 00:03:04,820
Innebär att om vi vill ha det
någonsin den femte punkten i en lista

68
00:03:04,820 --> 00:03:07,230
eller femte punkten i vår
array, kan vi bara ta tag i den.

69
00:03:07,230 --> 00:03:10,440
Om det är en länkad lista, vi har
att iterera igenom, eller hur?

70
00:03:10,440 --> 00:03:14,020
Så åtkomst till en del av
en array är konstant tid,

71
00:03:14,020 --> 00:03:19,530
medan med en länkad lista skulle det
sannolikt vara linjär tid eftersom kanske

72
00:03:19,530 --> 00:03:21,370
vår del är hela vägen i slutet.

73
00:03:21,370 --> 00:03:23,446
Vi måste söka igenom allt.

74
00:03:23,446 --> 00:03:25,320
Så med alla dessa uppgifter
strukturer vi kommer

75
00:03:25,320 --> 00:03:29,330
att spendera lite mer tid på,
Vad är plussidan och negativ.

76
00:03:29,330 --> 00:03:31,480
När kan vi vill
använda en över den andra?

77
00:03:31,480 --> 00:03:34,970
Och det är typ av
större sak att ta bort.

78
00:03:34,970 --> 00:03:40,140
>> Så vi har här
definitionen av en nod.

79
00:03:40,140 --> 00:03:43,040
Det är som en del i
vår länkad lista, eller hur?

80
00:03:43,040 --> 00:03:46,180
Så vi är alla bekanta
med våra typedef structs,

81
00:03:46,180 --> 00:03:47,980
som vi gick över i gransknings förra gången.

82
00:03:47,980 --> 00:03:53,180
Det var i princip bara att skapa
annan datatyp som vi kunde använda.

83
00:03:53,180 --> 00:03:57,930
>> Och i det här fallet, är det någon nod
som kommer att hålla några heltal.

84
00:03:57,930 --> 00:04:00,210
Och vad är den andra delen här?

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

86
00:04:03,192 --> 00:04:05,677
Någon?

87
00:04:05,677 --> 00:04:06,680
>> PUBLIK: [OHÖRBAR].

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

89
00:04:07,020 --> 00:04:08,400
Det är en pekare till nästa nod.

90
00:04:08,400 --> 00:04:12,610
Så detta borde egentligen vara här uppe.

91
00:04:12,610 --> 00:04:18,790
Detta är en pekare av typ
nod till nästa sak.

92
00:04:18,790 --> 00:04:22,410
Och det är vad de
omfattar vår nod.

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

94
00:04:24,060 --> 00:04:29,390
>> Okej, så med sökandet, som vi var
bara säga innan handen, om du är

95
00:04:29,390 --> 00:04:31,840
kommer att söka igenom,
du måste verkligen iterera

96
00:04:31,840 --> 00:04:33,660
via din länkad lista.

97
00:04:33,660 --> 00:04:38,530
Så om vi är ute efter numret
9, skulle vi börja på vårt huvud

98
00:04:38,530 --> 00:04:41,520
och det leder oss i början
av vår länkad lista, eller hur?

99
00:04:41,520 --> 00:04:44,600
Och vi säger, OK, gör detta
nod innehåller nummer 9?

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

101
00:04:45,690 --> 00:04:47,500
>> Okej, gå till nästa.

102
00:04:47,500 --> 00:04:48,312
Följ den.

103
00:04:48,312 --> 00:04:49,520
Innehåller den nummer 9?

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

105
00:04:50,570 --> 00:04:51,550
Följ nästa.

106
00:04:51,550 --> 00:04:55,490
>> Så vi måste verkligen iterera
genom vår länkad lista.

107
00:04:55,490 --> 00:05:00,070
Vi kan inte bara gå direkt till där 9 är.

108
00:05:00,070 --> 00:05:05,860
Och om ni verkligen vill
Hitta pseudokod uppe.

109
00:05:05,860 --> 00:05:10,420
Vi har några sökfunktion här
som tar in-- vad tar det i?

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

111
00:05:13,110 --> 00:05:14,320
Vad tycker du?

112
00:05:14,320 --> 00:05:15,960
Så lätt en.

113
00:05:15,960 --> 00:05:17,784
Vad är detta?

114
00:05:17,784 --> 00:05:18,700
PUBLIK: [OHÖRBAR].

115
00:05:18,700 --> 00:05:20,366
SPEAKER 1: Antalet vi letar efter.

116
00:05:20,366 --> 00:05:20,980
Rätt?

117
00:05:20,980 --> 00:05:22,875
Och vad skulle det motsvara?

118
00:05:22,875 --> 00:05:25,020
Det är en pekare till?

119
00:05:25,020 --> 00:05:26,000
>> Publik: En nod.

120
00:05:26,000 --> 00:05:28,980
>> TALARE 1: En nod i listan
att vi tittar på, eller hur?

121
00:05:28,980 --> 00:05:33,700
Så har vi några noder är pekare här.

122
00:05:33,700 --> 00:05:37,240
Detta är en punkt som kommer att
faktiskt iterera igenom vår lista.

123
00:05:37,240 --> 00:05:39,630
Vi sätter det lika med lista
eftersom det är bara

124
00:05:39,630 --> 00:05:44,380
att ställa in den är lika med den
start av vår länkad lista.

125
00:05:44,380 --> 00:05:50,660
>> Och även om det inte är NULL, medan
vi har fortfarande saker i vår lista,

126
00:05:50,660 --> 00:05:55,580
kontrollera om den noden har
Antalet vi söker.

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

128
00:05:57,740 --> 00:06:01,070
Annars uppdatera den, eller hur?

129
00:06:01,070 --> 00:06:04,870
>> Om det är NULL, vi avsluta vår
while-slinga och returnera false

130
00:06:04,870 --> 00:06:08,340
eftersom det innebär att vi inte har hittat den.

131
00:06:08,340 --> 00:06:11,048
Får alla människor hur det fungerar?

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 insättning, du
har tre olika sätt.

135
00:06:20,260 --> 00:06:25,250
Du kan infoga före, du kan lägga till
och du kan infoga i diverse.

136
00:06:25,250 --> 00:06:28,215
I det här fallet är vi
kommer att göra ett prefix.

137
00:06:28,215 --> 00:06:33,380
Vet någon hur de
tre fall kan skilja?

138
00:06:33,380 --> 00:06:36,920
>> Så prepend innebär att du sätter
det på framsidan av din lista.

139
00:06:36,920 --> 00:06:39,770
Så det skulle innebära att oavsett
vad din nod är, oavsett

140
00:06:39,770 --> 00:06:43,160
vad värdet är, du kommer
att rätta till det här framför, OK?

141
00:06:43,160 --> 00:06:45,160
Det kommer att bli den första
element i listan.

142
00:06:45,160 --> 00:06:49,510
>> Om du lägger det, det kommer
att gå till baksidan av din lista.

143
00:06:49,510 --> 00:06:54,010
Och sätt in i diverse innebär att du
ska sätta faktiskt till platsen

144
00:06:54,010 --> 00:06:57,700
där den håller din länkad lista sortering.

145
00:06:57,700 --> 00:07:00,810
Återigen, hur du använder
dem och när du använder

146
00:07:00,810 --> 00:07:02,530
dem kommer att variera beroende på ditt ärende.

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

148
00:07:05,834 --> 00:07:07,750
Om det inte behöver
sorteras, tenderar prepend

149
00:07:07,750 --> 00:07:10,460
vara vad de flesta människor
använda eftersom du inte

150
00:07:10,460 --> 00:07:15,680
måste gå igenom hela listan
att finna i slutet för att lägga den på, eller hur?

151
00:07:15,680 --> 00:07:17,720
Du kan bara hålla det rätt in.

152
00:07:17,720 --> 00:07:21,930
>> Så vi kommer att gå igenom en
insättning 1 just nu.

153
00:07:21,930 --> 00:07:26,360
Så en sak som jag kommer att
rekommenderar den här pset

154
00:07:26,360 --> 00:07:29,820
är att dra ut saker, som alltid.

155
00:07:29,820 --> 00:07:35,130
Det är mycket viktigt att du uppdaterar
dina pekare i rätt ordning

156
00:07:35,130 --> 00:07:38,620
för om du uppdatera dem
något ur funktion,

157
00:07:38,620 --> 00:07:42,210
du kommer att hamna
förlora delar av din lista.

158
00:07:42,210 --> 00:07:49,680
>> Så till exempel i det här fallet är vi
berättar chefen att bara peka på 1.

159
00:07:49,680 --> 00:07:56,070
Om vi ​​gör just det
utan att spara detta 1,

160
00:07:56,070 --> 00:07:58,570
Vi har ingen aning om vad
1 ska peka på nu

161
00:07:58,570 --> 00:08:02,490
eftersom vi har förlorat vad
huvudet pekade.

162
00:08:02,490 --> 00:08:05,530
Så en sak att komma ihåg
När du gör en prefix

163
00:08:05,530 --> 00:08:09,630
är att rädda vad
huvud pekar på första,

164
00:08:09,630 --> 00:08:15,210
sedan dela ut det och sedan uppdatera
vad din nya noden ska peka på.

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

166
00:08:20,870 --> 00:08:22,560
I det här fallet, är detta ett sätt att göra det.

167
00:08:22,560 --> 00:08:25,440
>> Så om vi hade gjort det så här
där vi bara omplacerad huvudet,

168
00:08:25,440 --> 00:08:30,320
vi förlorar i princip vår
hela listan, eller hur?

169
00:08:30,320 --> 00:08:38,000
Ett sätt att göra det är att ha 1 poäng till
nästa, och sedan har hornspunkten till 1.

170
00:08:38,000 --> 00:08:42,650
Eller du kan göra ungefär som
tillfällig lagring, som jag talade om.

171
00:08:42,650 --> 00:08:45,670
>> Men omtilldelning din
pekare i rätt ordning

172
00:08:45,670 --> 00:08:48,750
kommer att bli mycket, mycket
viktigt att detta pset.

173
00:08:48,750 --> 00:08:53,140
Annars kommer du att få en hash
bord eller ett försök som bara kommer att bli

174
00:08:53,140 --> 00:08:56,014
endast en del av de ord som du
vill ha och sedan you're-- mmhmm?

175
00:08:56,014 --> 00:08:58,930
PUBLIK: Vad var det tillfälliga
förvarings sak du pratade om?

176
00:08:58,930 --> 00:09:00,305
SPEAKER 1: Den tillfälliga förvaringen.

177
00:09:00,305 --> 00:09:02,760
Så i princip en annan
sätt du kan göra detta

178
00:09:02,760 --> 00:09:07,650
är lagra huvudet av något, som
lagra den för temporär variabel.

179
00:09:07,650 --> 00:09:11,250
Tilldela den till 1 och
sedan uppdatera 1 till punkt

180
00:09:11,250 --> 00:09:13,830
till vad huvudet används för att peka på.

181
00:09:13,830 --> 00:09:16,920
På detta sätt är uppenbarligen
mer elegant eftersom du

182
00:09:16,920 --> 00:09:20,770
behöver inte en tillfällig värde, men
bara erbjuda ett annat sätt att göra det.

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

184
00:09:23,999 --> 00:09:25,790
Och vi faktiskt har
lite kod för detta.

185
00:09:25,790 --> 00:09:28,080
Så för länkad lista, vi
faktiskt har någon kod.

186
00:09:28,080 --> 00:09:31,930
Så sätt in här, detta är prepending.

187
00:09:31,930 --> 00:09:34,290
Så det här går den i spetsen.

188
00:09:34,290 --> 00:09:38,820
>> Så första måste du
skapa ditt nya noden, naturligtvis,

189
00:09:38,820 --> 00:09:40,790
och kontrollera NULL.

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

191
00:09:43,250 --> 00:09:47,840
Och sedan måste du tilldela värdena.

192
00:09:47,840 --> 00:09:51,260
När du skapar en ny nod, du
vet inte vad den pekar på nästa,

193
00:09:51,260 --> 00:09:54,560
så du vill initiera den till null.

194
00:09:54,560 --> 00:09:58,760
Om den gör det i slutändan pekar på något
annars, det blir omplacerad och det är bra.

195
00:09:58,760 --> 00:10:00,740
Om det är det första
i listan, behöver den

196
00:10:00,740 --> 00:10:04,270
att peka på NULL eftersom
det är slutet på listan.

197
00:10:04,270 --> 00:10:12,410
>> Så då att infoga det ser vi här vi
tilldelar nästa värdet av vår nod

198
00:10:12,410 --> 00:10:17,380
att vara vad huvudet,
vilket är vad vi hade här.

199
00:10:17,380 --> 00:10:19,930
Det är vad vi just gjorde.

200
00:10:19,930 --> 00:10:25,820
Och då kommer vi att tilldela huvud till punkt
till vår nya noden, eftersom kom ihåg,

201
00:10:25,820 --> 00:10:31,090
ny är några pekare till en nod,
och det är precis vad chefen är.

202
00:10:31,090 --> 00:10:34,370
Det är just därför vi
har denna pil åtkomst.

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
>> PUBLIK: Har vi till
initiera ny bredvid NULL först,

207
00:10:41,100 --> 00:10:44,240
eller kan vi bara initiera den till huvudet?

208
00:10:44,240 --> 00:10:48,210
>> SPEAKER 1: Ny nästa
måste vara NULL för att börja

209
00:10:48,210 --> 00:10:53,760
eftersom du inte vet
där det kommer att bli.

210
00:10:53,760 --> 00:10:56,100
Dessutom är denna typ av
precis som ett paradigm.

211
00:10:56,100 --> 00:10:59,900
Du anger det lika med NULL bara för att göra
Se till att alla dina grunder omfattas

212
00:10:59,900 --> 00:11:04,070
innan du gör något omfördelning så att
du är alltid garanterad att det kommer

213
00:11:04,070 --> 00:11:08,880
peka till ett specifikt värde
kontra som en skräp värde.

214
00:11:08,880 --> 00:11:12,210
Därför att, ja, vi tilldelar
nya nästa automatiskt

215
00:11:12,210 --> 00:11:15,420
men det är mer bara som en
god praxis att initiera den

216
00:11:15,420 --> 00:11:19,270
på det sättet och sedan tilldela.

217
00:11:19,270 --> 00:11:23,420
>> OK, så dubbelt länkade listor nu.

218
00:11:23,420 --> 00:11:24,601
Vad tycker vi?

219
00:11:24,601 --> 00:11:26,350
Vad är annorlunda med
dubbelt länkade listor?

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

221
00:11:30,750 --> 00:11:34,300
>> Så i våra länkade listor, kan vi
endast röra sig i en riktning, eller hur?

222
00:11:34,300 --> 00:11:35,270
Vi har bara nästa.

223
00:11:35,270 --> 00:11:36,760
Vi kan bara gå framåt.

224
00:11:36,760 --> 00:11:40,300
>> Med en dubbellänkad lista,
Vi kan också gå bakåt.

225
00:11:40,300 --> 00:11:44,810
Så vi har inte bara
nummer som vi vill lagra,

226
00:11:44,810 --> 00:11:50,110
Vi har då det pekar på nästa
och där vi bara kom från.

227
00:11:50,110 --> 00:11:52,865
Så detta möjliggör
vissa bättre traverse.

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

229
00:11:56,620 --> 00:12:01,240
>> Så dubbelt länkade noder,
mycket lika, eller hur?

230
00:12:01,240 --> 00:12:05,000
Enda skillnaden är nu vi
har en annan och tidigare.

231
00:12:05,000 --> 00:12:06,235
Det är den enda skillnaden.

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

233
00:12:09,570 --> 00:12:14,790
>> Så om vi skulle infoga före eller append-- vi
inte har någon kod för detta upp här--

234
00:12:14,790 --> 00:12:17,830
men om du skulle försöka
för in den, det viktiga

235
00:12:17,830 --> 00:12:19,980
är du måste göra
att du tilldelar

236
00:12:19,980 --> 00:12:23,360
både tidigare och din
nästa pekaren på rätt sätt.

237
00:12:23,360 --> 00:12:29,010
Så i detta fall, skulle du
inte bara initiera nästa,

238
00:12:29,010 --> 00:12:31,820
du initierar tidigare.

239
00:12:31,820 --> 00:12:36,960
Om vi ​​är i toppen av listan, vi
skulle inte bara göra huvudet lika nytt,

240
00:12:36,960 --> 00:12:41,750
men vår nya tidigare bör
peka på huvudet, eller hur?

241
00:12:41,750 --> 00:12:43,380
>> Det är den enda skillnaden.

242
00:12:43,380 --> 00:12:47,200
Och om du vill ha mer praktik med
dessa med länkade listor, med insättning,

243
00:12:47,200 --> 00:12:49,900
med att ta bort, med insats
i en blandad lista,

244
00:12:49,900 --> 00:12:52,670
behaga kontrollen ut study.cs50.net.

245
00:12:52,670 --> 00:12:54,870
Det finns en massa bra övningar.

246
00:12:54,870 --> 00:12:55,870
Jag rekommenderar dem.

247
00:12:55,870 --> 00:12:59,210
Jag önskar att vi hade tid att gå igenom dem
men det finns en hel del datastrukturer

248
00:12:59,210 --> 00:13:01,530
att få igenom.

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

250
00:13:02,650 --> 00:13:07,070
Detta är förmodligen den mest
användbar bit för din pset

251
00:13:07,070 --> 00:13:11,090
här eftersom du kommer att bli
genomföra en av dessa, eller ett försök.

252
00:13:11,090 --> 00:13:12,200
Jag gillar verkligen hashtabeller.

253
00:13:12,200 --> 00:13:13,110
De är ganska cool.

254
00:13:13,110 --> 00:13:17,080
>> Så i princip vad
händer är en hashtabell

255
00:13:17,080 --> 00:13:22,050
är när vi verkligen behöver snabb
insättning, radering och sökning.

256
00:13:22,050 --> 00:13:25,010
Det är dessa saker som vi är
prioritering i en hashtabell.

257
00:13:25,010 --> 00:13:29,500
De kan bli ganska stora,
men som vi ser med försök,

258
00:13:29,500 --> 00:13:33,040
Det finns saker som är mycket större.

259
00:13:33,040 --> 00:13:38,330
>> Men i grund och botten, alla en hash
tabell är en hash-funktion

260
00:13:38,330 --> 00:13:47,215
som talar om vilken hink att sätta varje
dina data, alla dina element i.

261
00:13:47,215 --> 00:13:51,140
Ett enkelt sätt att tänka på en hashtabell
är att det är bara hinkar med saker,

262
00:13:51,140 --> 00:13:51,770
rätt?

263
00:13:51,770 --> 00:13:59,720
Så när du sorterar saker med
som den första bokstaven i deras namn,

264
00:13:59,720 --> 00:14:01,820
det är ungefär som en hashtabell.

265
00:14:01,820 --> 00:14:06,180
>> Så om jag skulle grupp ni är
i grupper om vem namn börjar

266
00:14:06,180 --> 00:14:11,670
med A över här, eller vem är födelsedag
är i januari, februari, mars,

267
00:14:11,670 --> 00:14:15,220
vad som helst, är att på ett effektivt sätt
skapa en hash-tabell.

268
00:14:15,220 --> 00:14:18,120
Det är bara att skapa hinkar som
du sortera element i

269
00:14:18,120 --> 00:14:19,520
så att du kan hitta dem lättare.

270
00:14:19,520 --> 00:14:22,300
Så det här sättet när jag behöver
att hitta en av er,

271
00:14:22,300 --> 00:14:24,680
Jag behöver inte söka
genom var och en av era namn.

272
00:14:24,680 --> 00:14:29,490
Jag kan vara som, åh, jag vet att
Dani födelsedag är in--

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

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

275
00:14:30,948 --> 00:14:33,120
Så jag tittar på mitt april
hink, och med lite tur,

276
00:14:33,120 --> 00:14:38,270
hon ska vara den enda i det och
min tid var konstant i den meningen,

277
00:14:38,270 --> 00:14:41,230
medan om jag måste titta
genom en hel massa människor,

278
00:14:41,230 --> 00:14:43,090
det kommer att ta mycket längre tid.

279
00:14:43,090 --> 00:14:45,830
Så hashtabeller är egentligen bara hinkar.

280
00:14:45,830 --> 00:14:48,630
Enkelt sätt att tänka på dem.

281
00:14:48,630 --> 00:14:52,930
>> Så en mycket viktig sak om
en hash-tabell är en hashfunktion.

282
00:14:52,930 --> 00:14:58,140
Så de saker som jag just talat om, liksom
din första bokstaven i ditt förnamn

283
00:14:58,140 --> 00:15:01,450
eller din födelsedag månad,
dessa är idéer som

284
00:15:01,450 --> 00:15:03,070
verkligen korrelerar till en hashfunktion.

285
00:15:03,070 --> 00:15:08,900
Det är bara ett sätt att avgöra vilken
hink du är elementet går in, OK?

286
00:15:08,900 --> 00:15:14,850
Så för denna pset, kan du slå upp
ganska mycket hash funktion du vill.

287
00:15:14,850 --> 00:15:16,030
>> Behöver inte vara din egen.

288
00:15:16,030 --> 00:15:21,140
Det finns några riktigt coola och kära ut
det som gör alla möjliga galna matte.

289
00:15:21,140 --> 00:15:25,170
Och om du vill göra din
stavningskontrollen supersnabb,

290
00:15:25,170 --> 00:15:27,620
Jag skulle definitivt
titta in i en av dem.

291
00:15:27,620 --> 00:15:32,390
>> Men det finns också de
enkla sådana, som compute

292
00:15:32,390 --> 00:15:39,010
summan av de ord, som
Varje bokstav har ett nummer.

293
00:15:39,010 --> 00:15:39,940
Beräkna summan.

294
00:15:39,940 --> 00:15:42,230
Som bestämmer skopan.

295
00:15:42,230 --> 00:15:45,430
De har också de enkla de som
är precis som alla av A: s här,

296
00:15:45,430 --> 00:15:47,050
alla B är här.

297
00:15:47,050 --> 00:15:48,920
Någon av dem.

298
00:15:48,920 --> 00:15:55,770
>> I grund och botten, bara säger det dig som
fältindex ditt element ska gå in.

299
00:15:55,770 --> 00:15:58,690
Bara beslut om bucket--
Det är allt en hashfunktion är.

300
00:15:58,690 --> 00:16:04,180
Så här har vi ett exempel som är
bara den första bokstaven i strängen

301
00:16:04,180 --> 00:16:05,900
som jag just talade om.

302
00:16:05,900 --> 00:16:11,900
>> Så du har lite hash det är bara
första bokstaven i din sträng minus A,

303
00:16:11,900 --> 00:16:16,090
vilket kommer att ge dig några
tal mellan 0 och 25.

304
00:16:16,090 --> 00:16:20,790
Och vad du vill göra är att
se till att detta är

305
00:16:20,790 --> 00:16:24,110
storleken på din hash table--
hur många hinkar finns.

306
00:16:24,110 --> 00:16:25,860
Med många av dessa
hashfunktioner, de är

307
00:16:25,860 --> 00:16:31,630
kommer att åter värden som kanske
vara långt över det antal hinkar

308
00:16:31,630 --> 00:16:33,610
att du faktiskt har
i din hashtabell,

309
00:16:33,610 --> 00:16:37,240
så du måste göra
säker och mod av dem.

310
00:16:37,240 --> 00:16:42,190
Annars kommer det att säga,
Åh, bör det vara i skopan 5000

311
00:16:42,190 --> 00:16:46,040
men du har bara 30
hinkar i din hashtabell.

312
00:16:46,040 --> 00:16:49,360
Och naturligtvis, vi vet alla att det är
kommer att resultera i några galna misstag.

313
00:16:49,360 --> 00:16:52,870
Så se till mod av
storleken på hash-tabellen.

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å kollisioner.

317
00:17:00,506 --> 00:17:02,620
Är alla bra så här långt?

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

319
00:17:03,120 --> 00:17:05,900
>> PUBLIK: Varför skulle det
returnera sådan massiv värde?

320
00:17:05,900 --> 00:17:09,210
>> TALARE 1: Beroende på algoritmen
att din hashfunktion används.

321
00:17:09,210 --> 00:17:12,270
Några av dem kommer att göra
galet multiplikation.

322
00:17:12,270 --> 00:17:16,270
Och det handlar om att få
en jämn fördelning,

323
00:17:16,270 --> 00:17:18,490
så de gör några riktigt
galna saker ibland.

324
00:17:18,490 --> 00:17:20,960
Det är allt.

325
00:17:20,960 --> 00:17:22,140
Något annat?

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

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

328
00:17:24,480 --> 00:17:29,270
I grund och botten, som jag sade tidigare,
i bästa fall,

329
00:17:29,270 --> 00:17:32,040
varje hink jag ser in är
kommer att ha en sak,

330
00:17:32,040 --> 00:17:34,160
så jag behöver inte titta på alla, eller hur?

331
00:17:34,160 --> 00:17:37,040
Jag antingen vet att det är där eller är det
inte, och det är vad vi verkligen vill.

332
00:17:37,040 --> 00:17:43,960
Men om vi har tiotusentals
datapunkter och mindre än det antal

333
00:17:43,960 --> 00:17:48,700
av skopor, vi kommer att ha
kollisioner där småningom något

334
00:17:48,700 --> 00:17:54,210
kommer att behöva hamna i en
skopa som redan har ett element.

335
00:17:54,210 --> 00:17:57,390
>> Så frågan är, vad
gör vi i så fall?

336
00:17:57,390 --> 00:17:58,480
Vad gör vi?

337
00:17:58,480 --> 00:17:59,300
Vi har redan något där?

338
00:17:59,300 --> 00:18:00,060
Får vi bara kasta ut?

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

340
00:18:00,700 --> 00:18:01,980
Vi måste hålla dem båda.

341
00:18:01,980 --> 00:18:06,400
Så det sätt som vi
brukar göra som är vad?

342
00:18:06,400 --> 00:18:08,400
Vad är datastrukturen
vi bara pratade om?

343
00:18:08,400 --> 00:18:09,316
Publik: Länkad lista.

344
00:18:09,316 --> 00:18:10,500
TALARE 1: En länkad lista.

345
00:18:10,500 --> 00:18:16,640
Så nu, istället för var och en av dessa
hinkar bara ha ett element,

346
00:18:16,640 --> 00:18:24,020
det kommer att innehålla en länkad lista med
de element som hash in i den.

347
00:18:24,020 --> 00:18:27,588
OK, gör alla slags får den idén?

348
00:18:27,588 --> 00:18:30,546
Eftersom vi inte kunde ha en array
eftersom vi inte vet hur många saker

349
00:18:30,546 --> 00:18:31,730
kommer att vara där.

350
00:18:31,730 --> 00:18:36,540
En länkad lista, tillåter oss att
bara det exakta antalet som

351
00:18:36,540 --> 00:18:38,465
är hashas i hinken, eller hur?

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

353
00:18:42,260 --> 00:18:50,500
>> Så linjär avkänningsriktningen är
i grund och botten detta idea--

354
00:18:50,500 --> 00:18:52,300
Det är ett sätt att ta itu med en kollision.

355
00:18:52,300 --> 00:18:58,010
Vad du kan göra är om, i det här
fall var berry hashed in 1

356
00:18:58,010 --> 00:19:01,130
och vi har redan
något där, du bara

357
00:19:01,130 --> 00:19:04,840
fortsätt tills
du hittar en tom plats.

358
00:19:04,840 --> 00:19:06,370
Det är ett sätt att hantera det.

359
00:19:06,370 --> 00:19:09,020
Det andra sättet att hantera
det är med vad vi just

360
00:19:09,020 --> 00:19:12,280
called-- den länkade
lista kallas chaining.

361
00:19:12,280 --> 00:19:20,510
>> Så denna idé fungerar om
ditt hashtabell du tror

362
00:19:20,510 --> 00:19:24,150
är mycket större än
dina data inställt eller om du

363
00:19:24,150 --> 00:19:28,870
vill försöka minimera kedja
tills det är absolut nödvändigt.

364
00:19:28,870 --> 00:19:34,050
Så en sak är linjär
sondering naturligtvis innebär

365
00:19:34,050 --> 00:19:37,290
att din hashfunktion
är inte riktigt lika användbar

366
00:19:37,290 --> 00:19:42,200
eftersom du kommer att sluta med
din hashfunktion, att komma till en punkt,

367
00:19:42,200 --> 00:19:46,400
Du linjär sond ner till
någon plats som är tillgänglig.

368
00:19:46,400 --> 00:19:49,670
Men nu, naturligtvis, något
annat som hamnar där,

369
00:19:49,670 --> 00:19:52,050
du kommer att behöva
söka ännu längre ner.

370
00:19:52,050 --> 00:19:55,650
>> Och det finns mycket mer
Sök kostnad som

371
00:19:55,650 --> 00:19:59,820
går in i inmatning av ett element
i hashtabell nu, eller hur?

372
00:19:59,820 --> 00:20:05,640
Och nu när du går och försöka hitta
berry igen, du kommer att hash det,

373
00:20:05,640 --> 00:20:07,742
och det kommer att säga,
åh, titta i hink 1,

374
00:20:07,742 --> 00:20:09,700
och det kommer inte att vara
i skopan 1, så du är

375
00:20:09,700 --> 00:20:11,970
kommer att behöva korsa
genom resten av dessa.

376
00:20:11,970 --> 00:20:17,720
Så det är ibland användbart,
men i de flesta fall,

377
00:20:17,720 --> 00:20:22,660
vi kommer att säga att
kedja är vad du vill göra.

378
00:20:22,660 --> 00:20:25,520
>> Så vi pratade om det här tidigare.

379
00:20:25,520 --> 00:20:27,812
Jag fick lite före mig själv.

380
00:20:27,812 --> 00:20:33,560
Men kedja är i grunden att
varje hink i din hashtabell

381
00:20:33,560 --> 00:20:36,120
är bara en länkad lista.

382
00:20:36,120 --> 00:20:39,660
>> Så ett annat sätt, eller mer teknisk
sätt att tänka på en hashtabell

383
00:20:39,660 --> 00:20:44,490
är att det är bara en array
av länkade listor, vilket

384
00:20:44,490 --> 00:20:49,330
När du skriver din ordlista
och du försöker ladda den,

385
00:20:49,330 --> 00:20:52,070
tänker på det som en
matris av länkade listor

386
00:20:52,070 --> 00:20:54,390
kommer att göra det mycket lättare
för dig att initiera.

387
00:20:54,390 --> 00:20:57,680
>> PUBLIK: Så hashtabell
har en förutbestämd storlek,

388
00:20:57,680 --> 00:20:58,980
som en [OHÖRBAR] av skopor?

389
00:20:58,980 --> 00:20:59,220
>> TALARE 1: Rätt.

390
00:20:59,220 --> 00:21:01,655
Så det finns ett visst antal
hinkar som du determine--

391
00:21:01,655 --> 00:21:03,530
som ni bör
tveka inte att leka med.

392
00:21:03,530 --> 00:21:05,269
Det kan vara ganska cool
för att se vad som händer

393
00:21:05,269 --> 00:21:06,810
när du ändrar ditt antal hinkar.

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

395
00:21:09,410 --> 00:21:11,510
Men ja, den har en
ange antal hinkar.

396
00:21:11,510 --> 00:21:15,360
Vad gör att du kan passa som
många element som du behöver

397
00:21:15,360 --> 00:21:19,350
är det separat kedja där du
har kopplat listor i varje hink.

398
00:21:19,350 --> 00:21:22,850
Det innebär att din hashtabell
kommer att vara exakt storlek

399
00:21:22,850 --> 00:21:25,440
att du behöver det vara, eller hur?

400
00:21:25,440 --> 00:21:27,358
Det är hela poängen med länkade listor.

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å alla OK där?

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

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

406
00:21:40,300 --> 00:21:41,860
Vad var det som hände?

407
00:21:41,860 --> 00:21:42,960
Verkligen nu.

408
00:21:42,960 --> 00:21:45,250
Gissa någon dödar mig.

409
00:21:45,250 --> 00:21:52,060
>> OK vi ska gå in i
försök, som är lite galen.

410
00:21:52,060 --> 00:21:53,140
Jag gillar hashtabeller.

411
00:21:53,140 --> 00:21:54,460
Jag tycker de är riktigt coola.

412
00:21:54,460 --> 00:21:56,710
Försöker är cool också.

413
00:21:56,710 --> 00:21:59,590
>> Så är det någon som kommer ihåg vad ett försök är?

414
00:21:59,590 --> 00:22:01,740
Du bör ha gått över
det kort i föreläsning?

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

416
00:22:04,570 --> 00:22:06,377
Kommer du ihåg typ hur det fungerar?

417
00:22:06,377 --> 00:22:08,460
PUBLIK: Jag bara nickar
att vi gick över den.

418
00:22:08,460 --> 00:22:09,626
TALARE 1: Vi gå över den.

419
00:22:09,626 --> 00:22:13,100
OK, vi verkligen kommer att gå
över det nu är vad vi säger.

420
00:22:13,100 --> 00:22:14,860
>> PUBLIK: Det är för en hämtning träd.

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

422
00:22:15,280 --> 00:22:16,196
Det är en hämtningsträd.

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

424
00:22:16,960 --> 00:22:23,610
Så en sak att notera här är att vi
tittar på enskilda tecken

425
00:22:23,610 --> 00:22:24,480
här, eller hur?

426
00:22:24,480 --> 00:22:29,710
>> Så innan vår hashfunktion, vi
letade på orden som helhet,

427
00:22:29,710 --> 00:22:32,270
och nu tittar vi mer
på karaktärerna, eller hur?

428
00:22:32,270 --> 00:22:38,380
Så vi har Maxwell hit och Mendel.

429
00:22:38,380 --> 00:22:47,840
Så i princip en try-- ett sätt att tänka
om detta är att varje nivå här

430
00:22:47,840 --> 00:22:49,000
är en samling av bokstäver.

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

432
00:22:53,310 --> 00:22:55,790
Så det här är din rotnoden här, eller hur?

433
00:22:55,790 --> 00:23:01,980
Detta har alla tecknen i
alfabet för starten av varje ord.

434
00:23:01,980 --> 00:23:06,480
>> Och vad du vill göra är att
säg, OK, har vi några M-ord.

435
00:23:06,480 --> 00:23:10,590
Vi kommer att leta efter Maxwell, så
vi går till M. Och M pekar på ett helt

436
00:23:10,590 --> 00:23:14,800
andra en matris där varje
ord, så länge som det

437
00:23:14,800 --> 00:23:17,044
är ett ord som har en
som den andra bokstaven,

438
00:23:17,044 --> 00:23:19,460
så länge det finns ett ord som
har B som den andra bokstaven,

439
00:23:19,460 --> 00:23:24,630
det kommer att ha en pekare
gå till några nästa array.

440
00:23:24,630 --> 00:23:29,290
>> Det finns förmodligen inte en
ord som MP någonting,

441
00:23:29,290 --> 00:23:32,980
så i P-läget i denna
array, skulle det bara vara NULL.

442
00:23:32,980 --> 00:23:38,840
Det skulle säga, OK, finns det inget ord
som har M, följt av ett P, OK?

443
00:23:38,840 --> 00:23:43,100
Så om vi tänker på det, varje
en av dessa mindre saker

444
00:23:43,100 --> 00:23:47,990
är faktiskt en av dessa
stora matriser från A till Z.

445
00:23:47,990 --> 00:23:55,064
Så vad kan vara en av de saker
det är lite av en nackdel med ett försök?

446
00:23:55,064 --> 00:23:56,500
>> PUBLIK: En mycket minne.

447
00:23:56,500 --> 00:23:59,940
>> TALARE 1: Det finns massor av minne, eller hur?

448
00:23:59,940 --> 00:24:08,750
Var och en av dessa block här
representerar 26 platser, 26 elementgrupp.

449
00:24:08,750 --> 00:24:13,680
Så försöker få oerhört rymd tung.

450
00:24:13,680 --> 00:24:17,100
>> Men de är mycket snabba.

451
00:24:17,100 --> 00:24:22,540
Så otroligt snabbt, men
verkligen utrymmet ineffektivt.

452
00:24:22,540 --> 00:24:24,810
Typ av måste lista
ut vilken du vill.

453
00:24:24,810 --> 00:24:29,470
Dessa är riktigt coolt för din pset,
men de tar upp mycket minne,

454
00:24:29,470 --> 00:24:30,290
så du handlar av.

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

456
00:24:31,480 --> 00:24:34,300
>> PUBLIK: Skulle det vara möjligt
att upprätta ett försök och sedan

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

458
00:24:37,967 --> 00:24:39,550
Jag vet inte om det skulle vara meningsfullt.

459
00:24:39,550 --> 00:24:42,200
Jag var att bli av med alla de
NULL tecken, men sedan

460
00:24:42,200 --> 00:24:42,910
du skulle inte kunna index them--

461
00:24:42,910 --> 00:24:43,275
>> TALARE 1: Du behöver dem fortfarande.

462
00:24:43,275 --> 00:24:44,854
>> Publik: - på samma sätt varje gång.

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

464
00:24:45,520 --> 00:24:50,460
Du behöver NULL tecken för att låta
du vet om det finns inte ett ord där.

465
00:24:50,460 --> 00:24:52,040
Ben hade du något du vill?

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

467
00:24:52,540 --> 00:24:54,581
Okej, så vi kommer
att gå lite mer

468
00:24:54,581 --> 00:24:58,920
in i tekniska detaljer bakom
ett försök och arbeta igenom ett exempel.

469
00:24:58,920 --> 00:25:01,490
>> OK, så det här är samma sak.

470
00:25:01,490 --> 00:25:06,290
Medan det i en länkad lista, våran
typ of-- vad är ordet jag vill? -

471
00:25:06,290 --> 00:25:08,350
som att bygga kvarter var en nod.

472
00:25:08,350 --> 00:25:12,280
I ett försök, har vi också en nod,
men det definieras olika.

473
00:25:12,280 --> 00:25:17,000
>> Så vi har några bool som
representerar huruvida ett ord faktiskt

474
00:25:17,000 --> 00:25:23,530
existerar på den här platsen, och sedan
vi har några array här-- eller snarare,

475
00:25:23,530 --> 00:25:27,840
detta är en pekare till en
matris med 27 tecken.

476
00:25:27,840 --> 00:25:33,339
Och detta är för, i det här fallet, det här
27-- Jag är säker på att ni alla är som, vänta,

477
00:25:33,339 --> 00:25:34,880
Det finns 26 bokstäver i alfabetet.

478
00:25:34,880 --> 00:25:36,010
Varför har vi har 27?

479
00:25:36,010 --> 00:25:37,870
>> Så beroende på
hur du genomföra detta,

480
00:25:37,870 --> 00:25:43,240
Detta är från en pset som
tillåts för apostrofer.

481
00:25:43,240 --> 00:25:46,010
Så det är därför den förstnämnda.

482
00:25:46,010 --> 00:25:50,500
Du har även i vissa
fall null terminator

483
00:25:50,500 --> 00:25:53,230
ingår som en av
tecken som det är tillåtet att vara,

484
00:25:53,230 --> 00:25:56,120
och det är hur de kontrollerar
se om det är i slutet av ordet.

485
00:25:56,120 --> 00:26:01,340
Om du är intresserad, kolla in
Kevins video på study.cs50,

486
00:26:01,340 --> 00:26:04,790
samt Wikipedia har
några bra resurser där.

487
00:26:04,790 --> 00:26:09,000
>> Men vi kommer att gå igenom bara typ
på hur du kan arbeta igenom ett försök

488
00:26:09,000 --> 00:26:11,010
om du fick en.

489
00:26:11,010 --> 00:26:16,230
Så vi har en super enkel här att
har orden "bat" och "Zoom" i dem.

490
00:26:16,230 --> 00:26:18,920
Och som vi ser här uppe,
detta lilla utrymme här

491
00:26:18,920 --> 00:26:22,560
representerar vår bool som
säger, ja, detta är ett ord.

492
00:26:22,560 --> 00:26:27,060
Och då detta är vår
arrayer av tecken, eller hur?

493
00:26:27,060 --> 00:26:33,480
>> Så vi kommer att gå igenom
finna "bat" i detta försök.

494
00:26:33,480 --> 00:26:38,340
Så börjar i toppen, eller hur?

495
00:26:38,340 --> 00:26:46,290
Och vi vet att B motsvarar
det andra indexet, det andra elementet

496
00:26:46,290 --> 00:26:47,840
i denna matris, för a och b.

497
00:26:47,840 --> 00:26:51,340
Så att ungefär den andra en.

498
00:26:51,340 --> 00:26:58,820
>> Och den säger, OK, coola, följer det till
nästa array, för om vi kommer ihåg,

499
00:26:58,820 --> 00:27:02,160
Det är inte så att var och en av dessa
faktiskt innehåller elementet.

500
00:27:02,160 --> 00:27:07,110
Var och en av dessa matriser
innehåller en pekare, eller hur?

501
00:27:07,110 --> 00:27:10,030
Det är en viktig distinktion att göra.

502
00:27:10,030 --> 00:27:13,450
>> Jag vet att detta kommer att be-- försök är
verkligen svårt att komma på första gången,

503
00:27:13,450 --> 00:27:15,241
så även om detta är den
andra eller tredje gången

504
00:27:15,241 --> 00:27:18,370
och det är fortfarande snäll
att verka svårt,

505
00:27:18,370 --> 00:27:21,199
Jag lovar, om du går klockan
kort igen i morgon,

506
00:27:21,199 --> 00:27:22,740
Det kommer nog göra mycket mer känsla.

507
00:27:22,740 --> 00:27:23,890
Det krävs mycket för att smälta.

508
00:27:23,890 --> 00:27:27,800
Jag fortfarande ibland är
liknande, vänta, vad är ett försök?

509
00:27:27,800 --> 00:27:29,080
Hur använder jag detta?

510
00:27:29,080 --> 00:27:33,880
>> Så vi har b i det här fallet,
vilket är vår andra indexet.

511
00:27:33,880 --> 00:27:40,240
Om vi ​​hade, säg, c eller
d eller någon annan bokstav,

512
00:27:40,240 --> 00:27:45,810
Vi måste kartlägga det tillbaka till index
av vår matris som som motsvarar.

513
00:27:45,810 --> 00:27:56,930
Så vi skulle ta ut rchar och vi bara
subtrahera bort en för att kartlägga den till 0-25.

514
00:27:56,930 --> 00:27:58,728
Alla bra hur vi
kart våra karaktärer?

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

516
00:28:00,440 --> 00:28:05,980
>> Så vi går till den andra, och vi
se att, ja, det är inte NULL.

517
00:28:05,980 --> 00:28:07,780
Vi kan gå vidare till detta nästa samling.

518
00:28:07,780 --> 00:28:12,300
Så vi går vidare till detta nästa samling här.

519
00:28:12,300 --> 00:28:15,500
>> Och vi säger, OK, nu har vi
måste se om en är här.

520
00:28:15,500 --> 00:28:18,590
Är A null eller gör det
faktiskt gå framåt?

521
00:28:18,590 --> 00:28:21,880
Så en faktiskt rör sig
framåt i denna samling.

522
00:28:21,880 --> 00:28:24,570
Och vi säger, OK, är t vår sista bokstaven.

523
00:28:24,570 --> 00:28:27,580
Så vi går till t vid index.

524
00:28:27,580 --> 00:28:30,120
Och då kommer vi gå vidare
eftersom det finns en till.

525
00:28:30,120 --> 00:28:38,340
Och den här säger i princip att, ja,
den säger att det är ett ord här--

526
00:28:38,340 --> 00:28:41,750
att om du följer detta
väg, har du kommit

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

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

529
00:28:43,800 --> 00:28:46,770
>> PUBLIK: Är det standard att ha det
som index 0 och sedan ha en slags vid 1

530
00:28:46,770 --> 00:28:47,660
eller att ha i slutet?

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

532
00:28:48,243 --> 00:28:55,360
Så om vi ser tillbaka på vår
förklaring här, det är en bool,

533
00:28:55,360 --> 00:28:59,490
så det är en egen del i din nod.

534
00:28:59,490 --> 00:29:03,331
Så det är inte en del av matrisen.

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

536
00:29:03,830 --> 00:29:08,370
Så när vi avslutar vårt ord och vi är
vid denna array, vad vi vill göra

537
00:29:08,370 --> 00:29:12,807
är göra en kontroll för detta är ett ord.

538
00:29:12,807 --> 00:29:14,390
Och i detta fall, skulle det gå tillbaka ja.

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

540
00:29:17,220 --> 00:29:24,090
>> Så på denna anmärkning, vi vet att "zoo" -
vi känner som människor att "zoo" är ett ord,

541
00:29:24,090 --> 00:29:24,820
rätt?

542
00:29:24,820 --> 00:29:28,990
Men är prova här skulle
säga, nej, det är inte.

543
00:29:28,990 --> 00:29:33,980
Och det skulle säga att eftersom vi
har inte utsett det som ett ord här.

544
00:29:33,980 --> 00:29:40,440
Även om vi kan passera
fram till denna matris,

545
00:29:40,440 --> 00:29:43,890
Detta försök skulle säga att, nej,
Djurparken är inte i din ordlista

546
00:29:43,890 --> 00:29:47,070
för vi har inte
utsett den som sådan.

547
00:29:47,070 --> 00:29:52,870
>> Så ett sätt att göra that--
Åh, förlåt, här.

548
00:29:52,870 --> 00:29:59,450
Så i detta fall, är inte "zoo"
ett ord, men det ligger i vårt försök.

549
00:29:59,450 --> 00:30:05,690
Men i den här, säger vi vill ha det
införa ordet "bath", vad händer

550
00:30:05,690 --> 00:30:08,260
är vi följer through-- b, a, t.

551
00:30:08,260 --> 00:30:11,820
Vi är i denna matris, och
Vi går för att söka efter h.

552
00:30:11,820 --> 00:30:15,220
>> I detta fall, när vi
titta på pekaren på h,

553
00:30:15,220 --> 00:30:17,890
det pekar på NULL, OK?

554
00:30:17,890 --> 00:30:20,780
Så om det inte är uttryckligen
pekar på en annan matris,

555
00:30:20,780 --> 00:30:25,000
du antar att alla pekare
i denna array pekar på null.

556
00:30:25,000 --> 00:30:28,270
Så i detta fall, är h pekar
till null så vi kan inte göra någonting,

557
00:30:28,270 --> 00:30:31,540
så det skulle också återvända
falskt, "bad" är inte här.

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

559
00:30:34,102 --> 00:30:35,810
Så nu är vi faktiskt
kommer att gå igenom

560
00:30:35,810 --> 00:30:39,790
hur skulle vi faktiskt säga
att "zoo" är i vårt försök.

561
00:30:39,790 --> 00:30:42,920
Hur vi sätter "zoo" i vårt försök?

562
00:30:42,920 --> 00:30:47,810
Så på samma sätt som vi började med
vår länkad lista, börjar vi vid roten.

563
00:30:47,810 --> 00:30:50,600
När du är osäker börjar på
roten av dessa saker.

564
00:30:50,600 --> 00:30:53,330
>> Och vi säger, OK, z.

565
00:30:53,330 --> 00:30:55,650
z finns i detta, och det gör det.

566
00:30:55,650 --> 00:30:58,370
Så du går vidare till
nästa array, OK?

567
00:30:58,370 --> 00:31:01,482
Och sedan på nästa,
vi säger, OK, gör o existerar?

568
00:31:01,482 --> 00:31:03,000
Det gör det.

569
00:31:03,000 --> 00:31:04,330
Detta igen.

570
00:31:04,330 --> 00:31:08,670
>> Och så på vår nästa, har vi sagt,
OK, finns "zoo" redan här.

571
00:31:08,670 --> 00:31:12,440
Allt vi behöver göra är att ställa in detta lika
till true, att det finns ett ord där.

572
00:31:12,440 --> 00:31:15,260
Om du hade följt allt
fram till innan den punkten,

573
00:31:15,260 --> 00:31:17,030
det är ett ord, så bara
ställa in den lika med sådant.

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

575
00:31:17,530 --> 00:31:22,550
>> PUBLIK: Så då gör det
innebär att "ba" är ett ord också?

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

577
00:31:24,120 --> 00:31:28,870
Så i detta fall, "ba" vi skulle få
här, skulle vi säga är det ett ord,

578
00:31:28,870 --> 00:31:31,590
och det skulle fortfarande inte finnas något.

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
>> PUBLIK: Så när du är det en
ord och du säger ja, då är det

582
00:31:36,360 --> 00:31:38,380
kommer att innehålla för att gå till m?

583
00:31:38,380 --> 00:31:42,260
>> TALARE 1: Så det här har att göra
with-- du läser detta.

584
00:31:42,260 --> 00:31:43,640
Du säger "zoo" är ett ord.

585
00:31:43,640 --> 00:31:47,020
När du går till check--
liknande, säger du vill säga,

586
00:31:47,020 --> 00:31:49,400
existerar "zoo" i denna ordbok?

587
00:31:49,400 --> 00:31:54,200
Du kommer bara att söka efter "zoo"
och sedan kontrollera om det är ett ord.

588
00:31:54,200 --> 00:31:57,291
Du kommer aldrig att flytta
fram till m för det är inte

589
00:31:57,291 --> 00:31:58,290
vad du letar efter.

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

591
00:32:02,690 --> 00:32:08,070
>> Så om vi verkligen ville
lägg till "bath" i detta försök,

592
00:32:08,070 --> 00:32:11,390
vi skulle göra samma sak
som vi gjorde med "zoo"

593
00:32:11,390 --> 00:32:15,380
utom vi skulle se att när vi
försöka få till h, existerar det inte.

594
00:32:15,380 --> 00:32:20,090
Så du kan se det som att försöka
att lägga till en ny nod i en länkad lista,

595
00:32:20,090 --> 00:32:27,210
så vi skulle behöva lägga till ytterligare
en av dessa matriser, som så.

596
00:32:27,210 --> 00:32:35,670
Och vad vi gör är att vi bara ställa in h
element i denna array som pekar på detta.

597
00:32:35,670 --> 00:32:39,430
>> Och vad skulle vi vilja göra här?

598
00:32:39,430 --> 00:32:43,110
Lägg det lika med sant
eftersom det är ett 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
Jag vet.

602
00:32:48,700 --> 00:32:51,170
Försöker inte den mest spännande.

603
00:32:51,170 --> 00:32:54,250
Tro mig, jag vet.

604
00:32:54,250 --> 00:32:58,040
>> Så en sak att inse med försök,
Jag sa, de är mycket effektiva.

605
00:32:58,040 --> 00:33:00,080
Så vi har sett de
tar upp massor av utrymme.

606
00:33:00,080 --> 00:33:01,370
De är typ av förvirrande.

607
00:33:01,370 --> 00:33:03,367
Så varför skulle vi någonsin använda dessa?

608
00:33:03,367 --> 00:33:05,450
Vi använder dessa eftersom de är
otroligt effektiv.

609
00:33:05,450 --> 00:33:08,130
>> Så om du någonsin ser
upp ett ord, är du bara

610
00:33:08,130 --> 00:33:10,450
som begränsas av längden av ordet.

611
00:33:10,450 --> 00:33:15,210
Så om du letar efter en
ord som har längden fem,

612
00:33:15,210 --> 00:33:20,940
du alltid bara kommer att behöva
gör högst fem jämförelser, OK?

613
00:33:20,940 --> 00:33:25,780
Så det gör det i stort sett konstant.

614
00:33:25,780 --> 00:33:29,150
Liksom insättning och uppslag
är i stort sett konstant tid.

615
00:33:29,150 --> 00:33:33,750
>> Så om du någonsin kan få
något i konstant tid,

616
00:33:33,750 --> 00:33:35,150
det är så bra som det blir.

617
00:33:35,150 --> 00:33:37,990
Du kan inte få bättre än
konstant tid för dessa saker.

618
00:33:37,990 --> 00:33:43,150
Så det är en av de
stora plus i försök.

619
00:33:43,150 --> 00:33:46,780
>> Men det är en hel del utrymme.

620
00:33:46,780 --> 00:33:50,380
Så du slags måste bestämma
vad är viktigast för dig.

621
00:33:50,380 --> 00:33:54,700
Och på dagens datorer,
utrymme som ett försök kan ta upp

622
00:33:54,700 --> 00:33:57,740
kanske inte påverkar
dig så mycket, men kanske

623
00:33:57,740 --> 00:34:01,350
du arbetar med något
som har långt, långt fler saker,

624
00:34:01,350 --> 00:34:02,810
och ett försök är helt enkelt inte rimligt.

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

626
00:34:03,000 --> 00:34:05,610
>> PUBLIK: Vänta, så du har 26
bokstäver i varenda en?

627
00:34:05,610 --> 00:34:07,440
>> TALARE 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 en del är ordet markör och sedan
du har 26 pekare i var och en.

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

631
00:34:17,775 --> 00:34:20,280
>> PUBLIK: Och varje 26,
tror de har var 26?

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

633
00:34:21,500 --> 00:34:27,460
Och det är därför, som du kan
se, den expanderar ganska snabbt.

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

635
00:34:28,130 --> 00:34:32,524
Så vi kommer att få in i träd, som
Jag känner för är lättare och kommer förmodligen

636
00:34:32,524 --> 00:34:36,150
vara en trevlig liten uppskov
från försök där.

637
00:34:36,150 --> 00:34:39,620
Så förhoppningsvis de flesta av er
har sett ett träd förut.

638
00:34:39,620 --> 00:34:41,820
Inte som den vackra
de utanför, som jag

639
00:34:41,820 --> 00:34:44,340
vet inte om någon
gick utomhus nyligen.

640
00:34:44,340 --> 00:34:49,230
Jag gick apple plocka i helgen,
och Åh min Jisses, det var vackert.

641
00:34:49,230 --> 00:34:52,250
Jag visste inte blad
skulle kunna se ut som söt.

642
00:34:52,250 --> 00:34:53,610
>> Så det här är bara ett träd, eller hur?

643
00:34:53,610 --> 00:34:56,790
Det är bara några nod, och det
pekar på ett gäng andra noder.

644
00:34:56,790 --> 00:34:59,570
Som du ser här, är detta
typ av ett återkommande tema.

645
00:34:59,570 --> 00:35:03,720
Noderna pekar på noder är typ av
kärnan i många datastrukturer.

646
00:35:03,720 --> 00:35:06,670
Det beror bara på hur vi
har dem pekar på varandra

647
00:35:06,670 --> 00:35:08,600
och hur vi färdas
genom dem och hur vi

648
00:35:08,600 --> 00:35:14,500
infoga saker som avgör
deras olika egenskaper.

649
00:35:14,500 --> 00:35:17,600
>> Så bara några terminologi,
som jag har använt tidigare.

650
00:35:17,600 --> 00:35:20,010
Så rot är det som är högst upp.

651
00:35:20,010 --> 00:35:21,200
Det är där vi alltid börja.

652
00:35:21,200 --> 00:35:23,610
Du kan se det som huvudet också.

653
00:35:23,610 --> 00:35:28,750
Men för träd, tenderar vi att
hänvisa till det som roten.

654
00:35:28,750 --> 00:35:32,820
>> Någonting vid botten här--
på mycket, mycket bottom--

655
00:35:32,820 --> 00:35:34,500
ANSES blad.

656
00:35:34,500 --> 00:35:37,210
Så det går tillsammans med
hela träd sak, eller hur?

657
00:35:37,210 --> 00:35:39,860
Bladen är i kanterna av ditt träd.

658
00:35:39,860 --> 00:35:45,820
>> Och då har vi också ett par
termer för att tala om noder i förhållande

659
00:35:45,820 --> 00:35:46,680
till varandra.

660
00:35:46,680 --> 00:35:49,700
Så vi har förälder,
barn och syskon.

661
00:35:49,700 --> 00:35:56,260
Så i detta fall, är tre av
förälder till 5, 6 och 7.

662
00:35:56,260 --> 00:36:00,370
Så föräldern är det som är
ett steg över vad du är

663
00:36:00,370 --> 00:36:02,940
hänvisar till, så det är bara
som ett släktträd.

664
00:36:02,940 --> 00:36:07,090
Förhoppningsvis är detta alla lite
lite mer intuitivt än försöker.

665
00:36:07,090 --> 00:36:10,970
>> Syskon är något som har
samma förälder, eller hur?

666
00:36:10,970 --> 00:36:13,470
De är på samma nivå här.

667
00:36:13,470 --> 00:36:16,960
Och sedan, när jag var
säger, barn är bara

668
00:36:16,960 --> 00:36:22,630
vad är ett steg lägre
noden i fråga, OK?

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

670
00:36:23,470 --> 00:36:25,610
Så ett binärt träd.

671
00:36:25,610 --> 00:36:31,450
Kan någon gissa på en av
egenskaperna hos det binära trädet?

672
00:36:31,450 --> 00:36:32,770
>> Publik: Max två blad.

673
00:36:32,770 --> 00:36:33,478
>> TALARE 1: Rätt.

674
00:36:33,478 --> 00:36:34,640
Så max två blad.

675
00:36:34,640 --> 00:36:39,730
Så i det här innan, hade vi här
som hade tre, men i ett binärt träd,

676
00:36:39,730 --> 00:36:45,000
du har en max två
barn per förälder, eller hur?

677
00:36:45,000 --> 00:36:46,970
Det finns en annan
intressant egenskap.

678
00:36:46,970 --> 00:36:51,550
Är det någon som vet det?

679
00:36:51,550 --> 00:36:52,620
Binärt träd.

680
00:36:52,620 --> 00:37:00,350
>> Så ett binärt träd har allt
på the-- här är inte sorted--

681
00:37:00,350 --> 00:37:05,320
men i ett sorterat binärt träd,
allt till höger

682
00:37:05,320 --> 00:37:08,530
är större än den överordnade,
och allt till vänster

683
00:37:08,530 --> 00:37:10,035
är mindre än den överordnade.

684
00:37:10,035 --> 00:37:15,690
Och det har varit en frågesport
frågan innan, så bra att veta.

685
00:37:15,690 --> 00:37:19,500
Så hur vi definierar det,
igen, vi har en annan nod.

686
00:37:19,500 --> 00:37:21,880
Detta ser mycket liknar vad?

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

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

689
00:37:28,836 --> 00:37:29,320
>> Publik: Linked listor

690
00:37:29,320 --> 00:37:31,100
>> TALARE 1: En dubbel länkad lista, eller hur?

691
00:37:31,100 --> 00:37:33,690
Så om vi byter ut
med föregående och nästa,

692
00:37:33,690 --> 00:37:35,670
detta skulle vara en dubbellänkad lista.

693
00:37:35,670 --> 00:37:40,125
Men i det här fallet, vi faktiskt
har vänster och höger och det är det.

694
00:37:40,125 --> 00:37:41,500
Annars är det exakt samma.

695
00:37:41,500 --> 00:37:43,374
Vi har fortfarande elementet
du är ute efter,

696
00:37:43,374 --> 00:37:45,988
och du bara har två pekare
gå till vad som kommer härnäst.

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

698
00:37:49,210 --> 00:37:51,870
Ja, så binärt sökträd.

699
00:37:51,870 --> 00:37:57,665
Om vi ​​märker, allt på
här är större than--

700
00:37:57,665 --> 00:37:59,850
eller allt omedelbart
till höger här

701
00:37:59,850 --> 00:38:02,840
är större än, allt
här är mindre än.

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

703
00:38:06,980 --> 00:38:14,000
>> Så om vi skulle söka igenom, det
bör se mycket nära binär sökning

704
00:38:14,000 --> 00:38:14,910
här, eller hur?

705
00:38:14,910 --> 00:38:17,640
Utom istället för att titta
vid halv arrayen,

706
00:38:17,640 --> 00:38:21,720
vi bara titta på antingen vänster
sidan eller den högra sidan av trädet.

707
00:38:21,720 --> 00:38:24,850
Så det blir lite enklare, tror jag.

708
00:38:24,850 --> 00:38:29,300
>> Så om din rot är NULL,
uppenbarligen är det bara falskt.

709
00:38:29,300 --> 00:38:33,470
Och om den finns där, det är naturligtvis sant.

710
00:38:33,470 --> 00:38:35,320
Om det är mindre än söker vi vänster.

711
00:38:35,320 --> 00:38:37,070
Om det är större än,
vi söker rätt.

712
00:38:37,070 --> 00:38:39,890
Det är precis som binär sökning,
bara en annan datastruktur

713
00:38:39,890 --> 00:38:40,600
att vi använder.

714
00:38:40,600 --> 00:38:42,790
I stället för en matris,
det är bara ett binärt träd.

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

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

717
00:38:48,090 --> 00:38:51,550
Och dessutom ser det ut som vi
kanske har lite tid.

718
00:38:51,550 --> 00:38:54,460
Om vi ​​gör det, jag är glad att gå
över någon av detta igen.

719
00:38:54,460 --> 00:38:56,856
OK, så stackar.

720
00:38:56,856 --> 00:39:02,695
Kommer någon ihåg vad stacks--
alla kännetecken på en stapel?

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

722
00:39:05,550 --> 00:39:10,400
>> OK, så de flesta av oss, tror jag,
äta i matsalen halls--

723
00:39:10,400 --> 00:39:13,100
så mycket som vi kanske inte vill.

724
00:39:13,100 --> 00:39:16,900
Men självklart kan du komma på en stapel
bokstavligen bara som en stapel av brickor

725
00:39:16,900 --> 00:39:18,460
eller en stapel av saker.

726
00:39:18,460 --> 00:39:21,820
Och vad som är viktigt
att inse är att det är

727
00:39:21,820 --> 00:39:26,850
something-- den karaktäristiska
som vi kallar det by-- är LIFO.

728
00:39:26,850 --> 00:39:28,450
Vet någon vad det står för?

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

730
00:39:29,070 --> 00:39:30,650
>> PUBLIK: Sist in, först ut.

731
00:39:30,650 --> 00:39:32,250
>> TALARE 1: Rätt, sist in, först ut.

732
00:39:32,250 --> 00:39:36,585
Så om vi vet, om vi stapla saker
upp till det lättaste greppa off--

733
00:39:36,585 --> 00:39:39,570
och kanske det enda vi kan ta
av om vår stack är stor enough--

734
00:39:39,570 --> 00:39:40,850
är att toppelementet.

735
00:39:40,850 --> 00:39:43,460
Så vad lades på
last-- som vi ser här,

736
00:39:43,460 --> 00:39:46,370
oavsett sköts
på mest recently-- är

737
00:39:46,370 --> 00:39:51,160
kommer att bli den första
sak som vi lossna, OK?

738
00:39:51,160 --> 00:39:56,324
>> Så vad vi har här är
annan typedef struct.

739
00:39:56,324 --> 00:39:58,740
Detta är verkligen precis som en
snabbkurs i datastrukturen,

740
00:39:58,740 --> 00:40:01,650
så det finns en hel del kastas på er.

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

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

743
00:40:04,970 --> 00:40:06,740
Yay för strukturer.

744
00:40:06,740 --> 00:40:16,660
>> Och i det här fallet, det är en del pekare
till en matris som har en viss kapacitet.

745
00:40:16,660 --> 00:40:20,830
Så detta är vår stack
Här, liksom våra faktiska array

746
00:40:20,830 --> 00:40:22,520
som är hållande våra element.

747
00:40:22,520 --> 00:40:24,850
Och så här har vi några storlek.

748
00:40:24,850 --> 00:40:31,170
>> Och typiskt, vill du behålla
reda på hur stor din stack är

749
00:40:31,170 --> 00:40:36,180
eftersom det som det kommer att göra det möjligt
dig att göra är om du vet storleken,

750
00:40:36,180 --> 00:40:39,170
Det gör att du kan säga,
OK, jag är på kapacitet?

751
00:40:39,170 --> 00:40:40,570
Kan jag lägga till något mer?

752
00:40:40,570 --> 00:40:44,650
Och det berättar också
där toppen av din stack

753
00:40:44,650 --> 00:40:48,180
är så att du vet vad du
kan faktiskt ta av.

754
00:40:48,180 --> 00:40:51,760
Och det är faktiskt kommer att
vara lite mer tydlig här.

755
00:40:51,760 --> 00:40:57,350
>> Så för push, en sak, om du
någonsin skulle genomföra skjuta,

756
00:40:57,350 --> 00:41:01,330
som jag säger bara, din
stack har en begränsad storlek, eller hur?

757
00:41:01,330 --> 00:41:03,990
Vår samling hade viss kapacitet.

758
00:41:03,990 --> 00:41:04,910
Det är en matris.

759
00:41:04,910 --> 00:41:08,930
Det är en fast storlek, så vi måste
se till att vi inte är att sätta mer

760
00:41:08,930 --> 00:41:11,950
in i vårt utbud än vi
faktiskt har plats för.

761
00:41:11,950 --> 00:41:16,900
>> Så när du skapar en push
funktion, det första du gör är att säga, OK,

762
00:41:16,900 --> 00:41:18,570
har jag utrymme i min stack?

763
00:41:18,570 --> 00:41:23,330
För om jag inte gör det, ledsen,
Jag kan inte lagra ditt element.

764
00:41:23,330 --> 00:41:28,980
Om jag gör det, då du vill spara
det högst upp i stacken, eller hur?

765
00:41:28,980 --> 00:41:31,325
>> Och det är därför vi har
att hålla reda på vår storlek.

766
00:41:31,325 --> 00:41:35,290
Om vi ​​inte hålla reda på vår storlek,
vi vet inte var de ska uttrycka det.

767
00:41:35,290 --> 00:41:39,035
Vi vet inte hur många saker
är i vår array redan.

768
00:41:39,035 --> 00:41:41,410
Som uppenbarligen finns det sätt
att kanske du kunde göra det.

769
00:41:41,410 --> 00:41:44,610
Du kan initiera allt till NULL
och sedan söka efter den senaste NULL,

770
00:41:44,610 --> 00:41:47,950
men en mycket enklare sak är bara
säga, OK, hålla reda på storlek.

771
00:41:47,950 --> 00:41:51,840
Som jag vet att jag har fyra element
i min samling, så nästa sak

772
00:41:51,840 --> 00:41:55,930
att vi sätter på, vi är
kommer att lagra åtmin index 4.

773
00:41:55,930 --> 00:42:00,940
Och sedan, naturligtvis, innebär detta att
du lyckas har drivit något

774
00:42:00,940 --> 00:42:03,320
på din stack, du
vill öka storleken

775
00:42:03,320 --> 00:42:08,880
så att du vet var du är så
att du kan skjuta fler saker på.

776
00:42:08,880 --> 00:42:12,730
>> Så om vi försöker pop
något utanför stacken,

777
00:42:12,730 --> 00:42:16,072
vad som kan vara det första
att vi vill kontrollera?

778
00:42:16,072 --> 00:42:18,030
Du försöker ta
något av din stack.

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

780
00:42:21,710 --> 00:42:24,781
Är du säker på att det finns
något i din stack?

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

782
00:42:25,280 --> 00:42:26,894
Så vad kan vi vill kontrollera?

783
00:42:26,894 --> 00:42:27,810
>> PUBLIK: [OHÖRBAR].

784
00:42:27,810 --> 00:42:29,880
SPEAKER 1: Kontrollera om storleken?

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

786
00:42:31,840 --> 00:42:38,520
Så vi vill kontrollera om
vår storlek är större än 0, OK?

787
00:42:38,520 --> 00:42:44,970
Och om det är så vi vill minska
vår storlek med 0 och returnera det.

788
00:42:44,970 --> 00:42:45,840
Varför?

789
00:42:45,840 --> 00:42:49,950
>> I det första en var vi
skjuta, vi drivit det

790
00:42:49,950 --> 00:42:52,460
på storlek och uppdateras sedan storlek.

791
00:42:52,460 --> 00:42:57,850
I det här fallet, vi nedräkna storlek
och sedan ta bort det, plocka det

792
00:42:57,850 --> 00:42:58,952
från vår samling.

793
00:42:58,952 --> 00:42:59,826
Varför skulle vi göra det?

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

795
00:43:04,800 --> 00:43:11,811
Så om jag har en sak på min stack,
vad som skulle vara min storlek på den punkten?

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

797
00:43:13,140 --> 00:43:15,180
>> Och där elementet 1 lagras?

798
00:43:15,180 --> 00:43:17,621
Vid vilken index?

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

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

801
00:43:19,060 --> 00:43:22,800
Så i detta fall, vi
alltid måste göra sure--

802
00:43:22,800 --> 00:43:27,630
stället för att återvända
storlek minus 1, eftersom vi

803
00:43:27,630 --> 00:43:31,730
vet att vårt inslag är
kommer att förvaras i en mindre

804
00:43:31,730 --> 00:43:34,705
oavsett vår storlek är, detta
bara tar hand om det.

805
00:43:34,705 --> 00:43:36,080
Det är en något mer elegant sätt.

806
00:43:36,080 --> 00:43:41,220
Och vi stega bara vår
storlek och sedan återvända storlek.

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

808
00:43:42,330 --> 00:43:45,300
>> PUBLIK: Jag antar att bara i allmänhet,
varför skulle denna datastruktur

809
00:43:45,300 --> 00:43:47,800
vara till nytta?

810
00:43:47,800 --> 00:43:50,660
>> TALARE 1: Det beror på din bakgrund.

811
00:43:50,660 --> 00:43:57,420
Så för en del av den teori,
om du arbetar with-- OK,

812
00:43:57,420 --> 00:44:02,750
Låt mig se om det finns en positiv man
som gynnar mer än utanför

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

814
00:44:05,420 --> 00:44:15,780
Med stackar, helst du behöver
att hålla reda på något som

815
00:44:15,780 --> 00:44:20,456
Den senast tillagda är när
du kommer att vilja använda en stack.

816
00:44:20,456 --> 00:44:24,770
>> Och jag kan inte tänka mig en bra
exempel på det just nu.

817
00:44:24,770 --> 00:44:29,955
Men när den senaste
sak är viktigast för dig,

818
00:44:29,955 --> 00:44:31,705
det är då en stapel
kommer att vara till nytta.

819
00:44:31,705 --> 00:44:35,797

820
00:44:35,797 --> 00:44:39,330
Jag försöker tänka om
det finns en god man för detta.

821
00:44:39,330 --> 00:44:43,720
Om jag tänker på ett gott exempel i nästa
20 minuter, kommer jag definitivt att berätta.

822
00:44:43,720 --> 00:44:49,455
>> Men totalt sett, om det finns något,
som sagt mest, där senaste

823
00:44:49,455 --> 00:44:52,470
är det viktigaste, det är
där en stapel kommer in.

824
00:44:52,470 --> 00:44:58,860
Medan köerna är typ av det motsatta.

825
00:44:58,860 --> 00:44:59,870
Och alla de små hundarna.

826
00:44:59,870 --> 00:45:00,890
Är inte detta stora, eller hur?

827
00:45:00,890 --> 00:45:03,299
Jag känner att jag borde
bara ha en kanin video

828
00:45:03,299 --> 00:45:05,090
rätt i mitten av
avsnitt för er

829
00:45:05,090 --> 00:45:08,870
eftersom detta är en intensiv sektion.

830
00:45:08,870 --> 00:45:10,480
>> Så en kö.

831
00:45:10,480 --> 00:45:12,710
I grund och botten en kö är som en linje.

832
00:45:12,710 --> 00:45:15,780
Ni killar jag är säker på att använda detta varje dag,
precis som i våra matsalar.

833
00:45:15,780 --> 00:45:18,160
Så vi måste gå in
och få våra brickor, jag är

834
00:45:18,160 --> 00:45:21,260
att du har att vänta i rad
att svepa eller få din mat.

835
00:45:21,260 --> 00:45:24,650
>> Så skillnaden här
är att detta är FIFO.

836
00:45:24,650 --> 00:45:30,090
Så om LIFO senast var i första
ut, är FIFO först in, först ut.

837
00:45:30,090 --> 00:45:33,400
Så det är här vad du sätter
På första är din viktigaste.

838
00:45:33,400 --> 00:45:35,540
Så om du väntade
i en line-- kan du

839
00:45:35,540 --> 00:45:39,130
tänk om du gick till
gå och hämta den nya iPhone

840
00:45:39,130 --> 00:45:42,800
och det var en stack där
sista personen i kön fick det första,

841
00:45:42,800 --> 00:45:44,160
människor skulle döda varandra.

842
00:45:44,160 --> 00:45:49,800
>> Så FIFO, vi är alla väl förtrogna
med i den verkliga världen här,

843
00:45:49,800 --> 00:45:54,930
och det hela har att göra med faktiskt
slags återskapa hela denna linje

844
00:45:54,930 --> 00:45:56,900
och köande struktur.

845
00:45:56,900 --> 00:46:02,390
Så medan med stapeln,
Vi har tryck och pop.

846
00:46:02,390 --> 00:46:06,440
Med en kö, vi har
enqueue och dequeue.

847
00:46:06,440 --> 00:46:10,910
Så enqueue princip innebär
lägga den på ryggen,

848
00:46:10,910 --> 00:46:13,680
och dequeue medel ta
bort från framsidan.

849
00:46:13,680 --> 00:46:18,680
Så vår datastruktur är en
lite mer komplicerat.

850
00:46:18,680 --> 00:46:21,060
Vi har en andra sak att hålla reda på.

851
00:46:21,060 --> 00:46:25,950
>> Så utan huvud, detta
är exakt en bunt, eller hur?

852
00:46:25,950 --> 00:46:27,900
Detta är samma struktur som en stapel.

853
00:46:27,900 --> 00:46:32,480
Det enda som skiljer nu är att vi
har detta huvud, vilket vad tror du

854
00:46:32,480 --> 00:46:34,272
kommer att hålla reda på?

855
00:46:34,272 --> 00:46:35,510
>> Publik: Det första en.

856
00:46:35,510 --> 00:46:38,685
>> TALARE 1: Rätt, det
första som vi lägger in.

857
00:46:38,685 --> 00:46:41,130
Chefen för vår kö.

858
00:46:41,130 --> 00:46:42,240
Den som är först i kön.

859
00:46:42,240 --> 00:46:45,300

860
00:46:45,300 --> 00:46:49,420
Okej, så om vi gör enqueue.

861
00:46:49,420 --> 00:46:52,720

862
00:46:52,720 --> 00:46:55,920
Återigen, med någon av
dessa datastrukturer,

863
00:46:55,920 --> 00:46:59,760
eftersom vi har att göra med en array,
Vi måste kontrollera om vi har utrymme.

864
00:46:59,760 --> 00:47:03,290
>> Det är ungefär som jag berättar
ni, om du öppnar en fil,

865
00:47:03,290 --> 00:47:04,760
du måste kontrollera för null.

866
00:47:04,760 --> 00:47:08,330
Med någon av dessa staplar
och köer, behöver du

867
00:47:08,330 --> 00:47:13,420
för att se om det finns utrymme för att vi är
att göra med en storlek array fast,

868
00:47:13,420 --> 00:47:16,030
som vi ser här-- 0, 1 alla upp till 5.

869
00:47:16,030 --> 00:47:20,690
Så vad vi gör i så fall är kontrollen
för att se om vi fortfarande har utrymme.

870
00:47:20,690 --> 00:47:23,110
Är vår storlek mindre än kapaciteten?

871
00:47:23,110 --> 00:47:28,480
>> Om så är fallet, måste vi lagra den på
svansen och vi uppdaterar vår storlek.

872
00:47:28,480 --> 00:47:30,250
Så vad kan svansen vara i det här fallet?

873
00:47:30,250 --> 00:47:32,360
Det är inte tydligt utskrivet.

874
00:47:32,360 --> 00:47:33,380
Hur skulle vi förvara det?

875
00:47:33,380 --> 00:47:34,928
Vad skulle svansen vara?

876
00:47:34,928 --> 00:47:38,600

877
00:47:38,600 --> 00:47:40,190
>> Så låt oss gå igenom det här exemplet.

878
00:47:40,190 --> 00:47:44,590
Så detta är en matris med storlek 6, eller hur?

879
00:47:44,590 --> 00:47:49,220
Och vi har just nu är 5 vår storlek.

880
00:47:49,220 --> 00:47:55,240
Och när vi lägger den i, det kommer
att gå in i den femte index, eller hur?

881
00:47:55,240 --> 00:47:57,030
Så spara på svansen.

882
00:47:57,030 --> 00:48:05,600
>> Ett annat sätt att skriva svans skulle bara
vara vår samling vid index av storlek, eller hur?

883
00:48:05,600 --> 00:48:07,560
Detta är storlek 5.

884
00:48:07,560 --> 00:48:11,490
Nästa sak kommer att gå in i 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
Det blir lite mer komplicerat
när vi börjar jävlas med huvudet.

888
00:48:16,350 --> 00:48:17,060
Ja?

889
00:48:17,060 --> 00:48:20,090
>> PUBLIK: Betyder det att vi
skulle ha förklarat en array som

890
00:48:20,090 --> 00:48:23,880
var fem elementen lång och
då vi lägger in den?

891
00:48:23,880 --> 00:48:24,730
>> SPEAKER 1: Nej.

892
00:48:24,730 --> 00:48:27,560
Så i detta fall, är detta en stapel.

893
00:48:27,560 --> 00:48:31,760
Detta skulle förklaras
som en array av storlek 6.

894
00:48:31,760 --> 00:48:37,120
Och i det här fallet, vi
bara har en plats kvar.

895
00:48:37,120 --> 00:48:42,720
>> OK, så en sak är i detta
fall, om huvudet är vid 0,

896
00:48:42,720 --> 00:48:45,270
då vi bara kan lägga till den i storlek.

897
00:48:45,270 --> 00:48:51,020
Men det blir lite svårare
eftersom det faktiskt, de

898
00:48:51,020 --> 00:48:52,840
har inte en slid
för detta, så jag kommer

899
00:48:52,840 --> 00:48:56,670
att dra en eftersom det inte är
riktigt så enkelt när du

900
00:48:56,670 --> 00:48:59,230
börja att bli av med saker.

901
00:48:59,230 --> 00:49:03,920
Så medan med en stack
du alltid bara har

902
00:49:03,920 --> 00:49:08,920
oroa sig för vad storleken är
När du lägger till något på,

903
00:49:08,920 --> 00:49:15,710
med en kö som du också måste göra
Se till att ditt huvud redovisas,

904
00:49:15,710 --> 00:49:20,760
eftersom en cool sak om köer
är att om du inte är på kapacitet,

905
00:49:20,760 --> 00:49:23,040
du faktiskt kan göra det linda runt.

906
00:49:23,040 --> 00:49:28,810
>> OK, så en thing-- oh,
Detta är fruktansvärt krita.

907
00:49:28,810 --> 00:49:31,815
En sak att tänka på är fallet.

908
00:49:31,815 --> 00:49:35,514

909
00:49:35,514 --> 00:49:37,140
Vi ska bara göra fem.

910
00:49:37,140 --> 00:49:41,810
OK, så vi kommer att
säger chefen är här.

911
00:49:41,810 --> 00:49:46,140
Detta är 0, 1, 2, 3, 4.

912
00:49:46,140 --> 00:49:54,210
>> Huvudet är där, och
vänligen ha saker i dem.

913
00:49:54,210 --> 00:49:58,340
Och vi vill lägga till något i, eller hur?

914
00:49:58,340 --> 00:50:01,170
Så det som vi måste
vet är att huvudet är alltid

915
00:50:01,170 --> 00:50:05,620
kommer att flytta på detta sätt och
sedan slinga tillbaka runt, OK?

916
00:50:05,620 --> 00:50:10,190
>> Så denna kö har plats, eller hur?

917
00:50:10,190 --> 00:50:13,950
Den har plats i början,
typ av motsatsen till detta.

918
00:50:13,950 --> 00:50:17,920
Så vad vi behöver göra är att vi
behöva beräkna svansen.

919
00:50:17,920 --> 00:50:20,530
Om du vet att din
huvudet har inte flyttat, svans

920
00:50:20,530 --> 00:50:24,630
är bara din samling på
index för den storleken.

921
00:50:24,630 --> 00:50:30,000
>> Men i verkligheten, om du använder en kö,
huvudet är antagligen uppdateras.

922
00:50:30,000 --> 00:50:33,890
Så vad du behöver göra är
faktiskt räkna svansen.

923
00:50:33,890 --> 00:50:39,990
Så vad vi gör är denna formel
här, som jag kommer att låta dig

924
00:50:39,990 --> 00:50:42,680
killar tycker om, och
då vi ska prata om det.

925
00:50:42,680 --> 00:50:49,567

926
00:50:49,567 --> 00:50:50,400
Så det här är kapacitet.

927
00:50:50,400 --> 00:50:55,890

928
00:50:55,890 --> 00:50:59,660
>> Så detta kommer faktiskt
ge dig ett sätt att göra det.

929
00:50:59,660 --> 00:51:03,205

930
00:51:03,205 --> 00:51:04,330
För i så fall vad?

931
00:51:04,330 --> 00:51:09,205
Vår huvud är på 1, är vår storlek 4.

932
00:51:09,205 --> 00:51:11,760

933
00:51:11,760 --> 00:51:18,490
Om vi ​​mod att med 5, får vi 0,
som är där vi ska mata in den.

934
00:51:18,490 --> 00:51:23,320

935
00:51:23,320 --> 00:51:26,080
>> Så sedan i nästa fall,
om vi skulle göra det,

936
00:51:26,080 --> 00:51:33,390
vi säger, OK, låt oss avköa något.

937
00:51:33,390 --> 00:51:34,390
Vi avköa detta.

938
00:51:34,390 --> 00:51:37,740
Vi tar ut detta element, eller hur?

939
00:51:37,740 --> 00:51:47,930
>> Och nu vårt huvud pekar här,
och vi vill lägga in en annan sak.

940
00:51:47,930 --> 00:51:52,470
Detta är i princip
baksidan av vår linje, eller hur?

941
00:51:52,470 --> 00:51:55,450
Köer kan linda runt arrayen.

942
00:51:55,450 --> 00:51:57,310
Det är en av de viktigaste skillnaderna.

943
00:51:57,310 --> 00:51:58,780
Stacks, du kan inte göra det här.

944
00:51:58,780 --> 00:52:01,140
>> Med köer, kan du
eftersom allt som betyder något

945
00:52:01,140 --> 00:52:03,940
är att du vet vad
senast var lagt.

946
00:52:03,940 --> 00:52:10,650
Eftersom allt kommer att läggas till i
denna riktning åt vänster, i detta fall,

947
00:52:10,650 --> 00:52:16,480
och sedan linda runt, kan du
fortsätta att sätta in nya element

948
00:52:16,480 --> 00:52:18,830
på framsidan av matrisen
eftersom det inte är riktigt

949
00:52:18,830 --> 00:52:20,640
framsidan av matrisen längre.

950
00:52:20,640 --> 00:52:26,320
Du kan tänka på i början av
array som var huvudet faktiskt är.

951
00:52:26,320 --> 00:52:29,710
>> Så denna formel är hur
du beräknar din svans.

952
00:52:29,710 --> 00:52:32,780

953
00:52:32,780 --> 00:52:35,610
Är det vettigt?

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, och sedan
ni har 10 minuter

957
00:52:44,040 --> 00:52:48,840
att ställa några klargörande frågor mig
du vill, för jag vet att det är galet.

958
00:52:48,840 --> 00:52:51,980
>> Okej, så i samma way--
Jag vet inte om ni har märkt,

959
00:52:51,980 --> 00:52:53,450
men CS handlar om mönster.

960
00:52:53,450 --> 00:52:57,370
Saker och ting är ganska mycket
Samma, bara med små tweaks.

961
00:52:57,370 --> 00:52:58,950
Så samma sak här.

962
00:52:58,950 --> 00:53:04,040
Vi måste kontrollera för att se om vi faktiskt
har något i vår kö, eller hur?

963
00:53:04,040 --> 00:53:05,960
Säg, OK, är vår storlek större än 0?

964
00:53:05,960 --> 00:53:06,730
Cool.

965
00:53:06,730 --> 00:53:10,690
>> Om vi ​​gör det kommer vi flytta vårt huvud, vilket
är vad jag just visat här.

966
00:53:10,690 --> 00:53:13,870
Vi uppdaterar våra huvuden för att vara en till.

967
00:53:13,870 --> 00:53:18,390
Och då är vi dekrementera vår
storlek och returnera elementet.

968
00:53:18,390 --> 00:53:21,000

969
00:53:21,000 --> 00:53:26,250
>> Det finns mycket mer konkret
kod på study.cs50.net,

970
00:53:26,250 --> 00:53:29,440
och jag rekommenderar starkt kommer
igenom det om du har tid,

971
00:53:29,440 --> 00:53:30,980
även om det bara är en pseudo-kod.

972
00:53:30,980 --> 00:53:35,980
Och om ni vill prata igenom
att med mig en på en, låt mig

973
00:53:35,980 --> 00:53:37,500
vet.

974
00:53:37,500 --> 00:53:38,770
Jag skulle gärna.

975
00:53:38,770 --> 00:53:42,720
Datastrukturer, om
du tar CS 124, du ska

976
00:53:42,720 --> 00:53:47,830
vet att datastrukturer blir mycket
roligt och det är bara början.

977
00:53:47,830 --> 00:53:50,350
>> Så jag vet att det är svårt.

978
00:53:50,350 --> 00:53:51,300
Det är OK.

979
00:53:51,300 --> 00:53:52,410
Vi kämpar.

980
00:53:52,410 --> 00:53:53,630
Jag gör fortfarande.

981
00:53:53,630 --> 00:53:56,660
Så oroa dig inte för mycket om det.

982
00:53:56,660 --> 00:54:02,390
>> Men det är i grunden din
snabbkurs i datastrukturer.

983
00:54:02,390 --> 00:54:03,400
Jag vet att det är en hel del.

984
00:54:03,400 --> 00:54:06,860
Finns det något som vi
skulle vilja gå igen?

985
00:54:06,860 --> 00:54:09,400
Allt vi vill prata igenom?

986
00:54:09,400 --> 00:54:10,060
Ja?

987
00:54:10,060 --> 00:54:16,525
>> Publik: För detta exempel, så
den nya svansen är vid 0 över det?

988
00:54:16,525 --> 00:54:17,150
TALARE 1: Ja.

989
00:54:17,150 --> 00:54:18,230
PUBLIK: OK.

990
00:54:18,230 --> 00:54:24,220
Så då går igenom,
du skulle ha 1 plus 4 eller--

991
00:54:24,220 --> 00:54:27,671
>> TALARE 1: Så du sa,
när vi vill gå göra det igen?

992
00:54:27,671 --> 00:54:28,296
PUBLIK: Ja.

993
00:54:28,296 --> 00:54:38,290
Så om du räkna out-- var är
du beräkna svansen mellan i det?

994
00:54:38,290 --> 00:54:44,260
>> TALARE 1: Så svansen
var in-- Jag ändrade detta.

995
00:54:44,260 --> 00:54:52,010
Så i det här exemplet här, var detta
arrayen vi tittar på, OK?

996
00:54:52,010 --> 00:54:54,670
Så vi har saker i en, två, tre och fyra.

997
00:54:54,670 --> 00:55:05,850
Så vi har vårt huvud är lika med 1 vid
denna punkt, och är lika med 4 vår storlek

998
00:55:05,850 --> 00:55:07,050
vid denna punkt, eller hur?

999
00:55:07,050 --> 00:55:08,960
>> Ni är alla överens om så är fallet?

1000
00:55:08,960 --> 00:55:14,620
Så vi gör huvudet plus storlek, vilket
ger oss 5 och sedan mod vi med 5.

1001
00:55:14,620 --> 00:55:20,690
Vi får 0, vilket säger oss att 0 är
var är vår svans, där vi har utrymme.

1002
00:55:20,690 --> 00:55:22,010
>> PUBLIK: Vad är ett tak?

1003
00:55:22,010 --> 00:55:23,520
>> TALARE 1: Kapaciteten.

1004
00:55:23,520 --> 00:55:24,020
Ursäkta.

1005
00:55:24,020 --> 00:55:29,640
Så det är storleken på din 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
>> PUBLIK: [OHÖRBAR] innan
vi tillbaka elementet?

1009
00:55:39,210 --> 00:55:46,270
>> TALARE 1: Så vi flyttar
huvudet eller returnera ögonblicket?

1010
00:55:46,270 --> 00:55:52,680
Så om vi flyttar en, dekrementera storlek?

1011
00:55:52,680 --> 00:55:54,150
Håll ut.

1012
00:55:54,150 --> 00:55:55,770
Jag glömde definitivt en annan.

1013
00:55:55,770 --> 00:56:00,646

1014
00:56:00,646 --> 00:56:01,990
Glöm det.

1015
00:56:01,990 --> 00:56:04,980
Det finns inte en annan formel.

1016
00:56:04,980 --> 00:56:09,980
Ja, skulle du vilja återvända
huvudet och sedan flytta tillbaka den.

1017
00:56:09,980 --> 00:56:13,270
>> PUBLIK: OK, eftersom det vid denna
punkt, var huvudet vid 0,

1018
00:56:13,270 --> 00:56:18,452
och sedan vill återvända
index 0 och sedan göra huvud 1?

1019
00:56:18,452 --> 00:56:19,870
>> TALARE 1: Rätt.

1020
00:56:19,870 --> 00:56:22,820
Jag tror det finns en annan
formel ungefär som det här.

1021
00:56:22,820 --> 00:56:26,970
Jag har inte det på toppen mitt huvud som
Jag vill inte ge dig fel.

1022
00:56:26,970 --> 00:56:35,470
Men jag tror att det är helt korrekt att
säg, OK, lagra denna element-- oavsett

1023
00:56:35,470 --> 00:56:40,759
huvudets del är-- dekrementera din
storlek, flytta huvudet över och retur

1024
00:56:40,759 --> 00:56:41,800
oavsett vad det elementet är.

1025
00:56:41,800 --> 00:56:44,760
Det är helt giltiga.

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
Jag tycker detta är inte
som den most-- du inte

1029
00:56:53,560 --> 00:56:55,740
kommer att gå ut härifrån
liksom, ja, jag vet försök.

1030
00:56:55,740 --> 00:56:56,880
Jag fick det hela.

1031
00:56:56,880 --> 00:56:57,670
Det är OK.

1032
00:56:57,670 --> 00:57:00,200
Jag lovar.

1033
00:57:00,200 --> 00:57:05,240
Men datastrukturer är något som
Det tar mycket tid att vänja sig.

1034
00:57:05,240 --> 00:57:10,010
Förmodligen en av de svåraste
saker, tror jag, i kursen.

1035
00:57:10,010 --> 00:57:15,330
>> Så det definitivt tar
repetition och ser at-- jag

1036
00:57:15,330 --> 00:57:20,050
visste inte riktigt länkade listor
tills jag gjorde alldeles för mycket med dem,

1037
00:57:20,050 --> 00:57:22,550
på samma sätt som jag inte
verkligen förstår pekare

1038
00:57:22,550 --> 00:57:27,040
tills jag har haft att lära ut det för två
år och göra mina egna psets med det.

1039
00:57:27,040 --> 00:57:28,990
Det tar mycket upprepning och tid.

1040
00:57:28,990 --> 00:57:32,600
Och så småningom kommer det slags klicka.

1041
00:57:32,600 --> 00:57:36,320
>> Men under tiden, om du har typ
av en hög nivå förståelse av vad

1042
00:57:36,320 --> 00:57:39,321
dessa gör, deras för-
och cons-- vilket är vad

1043
00:57:39,321 --> 00:57:41,820
vi verkligen tenderar att betona,
speciellt i intro kursen.

1044
00:57:41,820 --> 00:57:45,511
Liksom, varför skulle vi använder
ett försök under en array?

1045
00:57:45,511 --> 00:57:48,010
Liksom, vad är positiva
och negativ av var och en av dem?

1046
00:57:48,010 --> 00:57:51,610
>> Och förstå avvägningar
mellan var och en av dessa strukturer

1047
00:57:51,610 --> 00:57:54,910
är det som är mycket viktigare just nu.

1048
00:57:54,910 --> 00:57:58,140
Det kan finnas en galen
fråga eller två som är

1049
00:57:58,140 --> 00:58:03,710
kommer att be er att genomföra skjuta eller
genomföra pop eller enqueue och dequeue.

1050
00:58:03,710 --> 00:58:07,340
Men för det mesta, har det
högre förståelse nivå och mer

1051
00:58:07,340 --> 00:58:09,710
av ett intuitivt grepp är
viktigare än faktiskt

1052
00:58:09,710 --> 00:58:11,250
att kunna genomföra det.

1053
00:58:11,250 --> 00:58:14,880
>> Det skulle vara riktigt häftigt om er alla
kunde gå ut och gå att genomföra ett försök,

1054
00:58:14,880 --> 00:58:19,720
men vi förstår att det är inte nödvändigtvis
det mest rimliga sak just nu.

1055
00:58:19,720 --> 00:58:23,370
Men du kan i ditt pset, om du vill
till, och sedan får du praktik,

1056
00:58:23,370 --> 00:58:27,200
och då kanske du kommer
verkligen förstå det.

1057
00:58:27,200 --> 00:58:27,940
Ja?

1058
00:58:27,940 --> 00:58:30,440
>> PUBLIK: OK, så vilka som är
Vi menade att användas i pset?

1059
00:58:30,440 --> 00:58:31,916
Behöver jag använda en av dem?

1060
00:58:31,916 --> 00:58:32,540
TALARE 1: Ja.

1061
00:58:32,540 --> 00:58:34,199
Så du har ditt val.

1062
00:58:34,199 --> 00:58:36,740
Jag antar att i det här fallet, kan vi
tala om pset lite

1063
00:58:36,740 --> 00:58:40,480
eftersom jag sprang genom dessa.

1064
00:58:40,480 --> 00:58:47,779
Så i ditt pset, har du din
Valet av försök eller hashtabeller.

1065
00:58:47,779 --> 00:58:49,570
Vissa människor kommer att försöka
och använda standard filter,

1066
00:58:49,570 --> 00:58:51,840
men de är inte tekniskt korrekt.

1067
00:58:51,840 --> 00:58:55,804
På grund av deras probabilistisk natur,
de ger falska positiva ibland.

1068
00:58:55,804 --> 00:58:57,095
De är coolt utseende till, dock.

1069
00:58:57,095 --> 00:58:59,030
Rekommendera ute
på dem åtminstone.

1070
00:58:59,030 --> 00:59:03,260
Men du har ditt val
mellan en hashtabell och ett försök.

1071
00:59:03,260 --> 00:59:06,660
Och det kommer att bli när
du laddar i din ordlista.

1072
00:59:06,660 --> 00:59:09,230
>> Och du måste välja
din hashfunktion,

1073
00:59:09,230 --> 00:59:13,420
måste du välja hur många
skopor du har, och den kommer att variera.

1074
00:59:13,420 --> 00:59:17,440
Som om du har fler hinkar,
kanske det kommer att springa snabbare.

1075
00:59:17,440 --> 00:59:22,790
Men kanske du slösar bort en
mycket utrymme på det sättet, men.

1076
00:59:22,790 --> 00:59:26,320
Du måste räkna ut det.

1077
00:59:26,320 --> 00:59:27,140
Mmhmm?

1078
00:59:27,140 --> 00:59:29,875
>> PUBLIK: Du sa förut att
vi kan använda andra hashfunktioner,

1079
00:59:29,875 --> 00:59:31,750
att vi inte behöver
skapa en hashfunktion?

1080
00:59:31,750 --> 00:59:32,666
>> TALARE 1: Ja, just det.

1081
00:59:32,666 --> 00:59:38,150
Så bokstavligen för din hashfunktion,
som google "hashfunktion"

1082
00:59:38,150 --> 00:59:40,770
och leta efter några häftiga sådana.

1083
00:59:40,770 --> 00:59:43,250
Du förväntas inte bygga
egna hashfunktioner.

1084
00:59:43,250 --> 00:59:46,100
Människor tillbringar sin
teser om dessa saker.

1085
00:59:46,100 --> 00:59:50,250
>> Så oroa dig inte om att bygga din egen.

1086
00:59:50,250 --> 00:59:53,350
Hitta en på nätet till att börja med.

1087
00:59:53,350 --> 00:59:56,120
Några av dem måste du
manipulera lite

1088
00:59:56,120 --> 00:59:59,430
att se till att typer retur matcha upp
och allt, så i början,

1089
00:59:59,430 --> 01:00:02,420
Jag skulle rekommendera att använda något
verkligen lätt att kanske bara

1090
01:00:02,420 --> 01:00:04,680
hashar på den första bokstaven.

1091
01:00:04,680 --> 01:00:08,760
Och sedan när du har att arbeta,
införliva en kylare hashfunktion.

1092
01:00:08,760 --> 01:00:09,260
Mmhmm?

1093
01:00:09,260 --> 01:00:13,020
>> PUBLIK: Skulle ett försök att vara eller
effektivt men bara svårare att, like--

1094
01:00:13,020 --> 01:00:15,880
>> TALARE 1: Så ett försök, tror jag,
är intuitivt svårt att genomföra

1095
01:00:15,880 --> 01:00:18,310
men är mycket snabb.

1096
01:00:18,310 --> 01:00:20,620
Dock tar upp mer utrymme.

1097
01:00:20,620 --> 01:00:25,270
Återigen kan man optimera både av dem som
olika sätt och det finns sätt att--

1098
01:00:25,270 --> 01:00:26,770
PUBLIK: Hur ska vi graderad på detta?

1099
01:00:26,770 --> 01:00:27,540
Är det matter--

1100
01:00:27,540 --> 01:00:29,164
>> TALARE 1: Så du graderade normalt sätt.

1101
01:00:29,164 --> 01:00:31,330
Du kommer att graderas på design.

1102
01:00:31,330 --> 01:00:36,020
Vilket sätt du gör, du vill
se till att det är lika elegant som det kan vara

1103
01:00:36,020 --> 01:00:38,610
och så effektivt som det kan vara.

1104
01:00:38,610 --> 01:00:41,950
Men om du väljer ett försök eller hash
bord, så länge det fungerar,

1105
01:00:41,950 --> 01:00:45,350
vi är nöjda med.

1106
01:00:45,350 --> 01:00:48,370
Och om du använder något som hashar
på den första bokstaven, det är bra,

1107
01:00:48,370 --> 01:00:51,410
som kanske gillar designmässigt.

1108
01:00:51,410 --> 01:00:53,410
Vi är också når
punkt i detta semester--

1109
01:00:53,410 --> 01:00:55,340
Jag vet inte om du
killar noticed-- om du är

1110
01:00:55,340 --> 01:00:58,780
pset kvaliteter minskar lite
på grund av design och allt,

1111
01:00:58,780 --> 01:00:59,900
det är väl bra.

1112
01:00:59,900 --> 01:01:02,960
Det börjar bli till en punkt där din
program blir mer komplicerat.

1113
01:01:02,960 --> 01:01:04,830
Det finns fler platser
du kan förbättra.

1114
01:01:04,830 --> 01:01:06,370
>> Så det är helt normalt.

1115
01:01:06,370 --> 01:01:08,810
Det är inte så att du är
göra värre på pset.

1116
01:01:08,810 --> 01:01:11,885
Det är bara vi vara hårdare på dig nu.

1117
01:01:11,885 --> 01:01:13,732
Så alla är känsla det.

1118
01:01:13,732 --> 01:01:14,940
Jag graderade bara alla dina psets.

1119
01:01:14,940 --> 01:01:16,490
Jag vet att alla känner det.

1120
01:01:16,490 --> 01:01:19,600
>> Så var inte orolig för det.

1121
01:01:19,600 --> 01:01:23,580
Och om du har några frågor om
tidigare psets eller sätt du kan förbättra,

1122
01:01:23,580 --> 01:01:27,760
Jag försöker och kommentera den specifika
ställen, men ibland är det för sent

1123
01:01:27,760 --> 01:01:30,840
och jag blir trött.

1124
01:01:30,840 --> 01:01:34,885
Finns det några andra saker
om datastrukturer?

1125
01:01:34,885 --> 01:01:37,510
Jag är säker på att ni inte riktigt
vill prata om dem längre,

1126
01:01:37,510 --> 01:01:42,650
men om det finns, jag är glad att
gå över dem, liksom allt

1127
01:01:42,650 --> 01:01:45,580
från föreläsning detta tidigare
veckan eller förra veckan.

1128
01:01:45,580 --> 01:01:51,580
>> Jag vet att förra veckan var allt recension, så
vi kan ha hoppat över någon recension

1129
01:01:51,580 --> 01:01:54,190
från föreläsning.

1130
01:01:54,190 --> 01:01:58,230
Alla andra frågor som jag kan svara?

1131
01:01:58,230 --> 01:01:59,350
OK, okej.

1132
01:01:59,350 --> 01:02:02,400
Nåväl, ni får ut 15 minuter för tidigt.

1133
01:02:02,400 --> 01:02:08,370
>> Jag hoppas att detta var halv hjälp åtminstone,
och jag kommer att se er nästa vecka,

1134
01:02:08,370 --> 01:02:12,150
eller torsdag kontorstid.

1135
01:02:12,150 --> 01:02:15,285
Finns det begär för mellanmål
för nästa vecka, det är grejen?

1136
01:02:15,285 --> 01:02:17,459
Eftersom jag glömde godis idag.

1137
01:02:17,459 --> 01:02:19,750
Och jag tog godis sist
vecka, men det var Columbus Day,

1138
01:02:19,750 --> 01:02:25,400
så det var som sex personer som
hade fyra påsar med godis till sig själva.

1139
01:02:25,400 --> 01:02:28,820
Jag kan ta med Starbursts
igen om du vill.

1140
01:02:28,820 --> 01:02:29,580
Starbursts?

1141
01:02:29,580 --> 01:02:32,250
OK, låter bra.

1142
01:02:32,250 --> 01:02:35,050
Ha en bra dag, grabbar.

1143
01:02:35,050 --> 01:02:39,510