1
00:00:00,000 --> 00:00:03,423
>> [MUSIK SPELA]

2
00:00:03,423 --> 00:00:05,380

3
00:00:05,380 --> 00:00:08,210
>> ANDI PENG: Välkommen till vecka 6 i avsnitt.

4
00:00:08,210 --> 00:00:11,620
Vi avvikit från vår standard
avsnitt tid tisdagen

5
00:00:11,620 --> 00:00:14,130
eftermiddag till denna härliga söndag morgon.

6
00:00:14,130 --> 00:00:17,330
Tack för alla som
anslöt sig till mig idag, men på allvar,

7
00:00:17,330 --> 00:00:18,170
en applåd.

8
00:00:18,170 --> 00:00:20,600
>> Det är en ganska stor ansträngning.

9
00:00:20,600 --> 00:00:23,600
Jag nästan inte ens göra det
i tid, men det var OK.

10
00:00:23,600 --> 00:00:27,520
Så jag vet att ni alla
har bara gjort det till frågesporten.

11
00:00:27,520 --> 00:00:30,370
Först av allt, välkommen till
den andra sidan av det.

12
00:00:30,370 --> 00:00:32,917
>> För det andra kommer vi att tala om det.

13
00:00:32,917 --> 00:00:34,000
Vi pratar om testet.

14
00:00:34,000 --> 00:00:35,700
Vi pratar om hur
du gör i klassen.

15
00:00:35,700 --> 00:00:36,550
Du kommer att bli bra.

16
00:00:36,550 --> 00:00:39,080
Jag har dina frågesporter för
dig i slutet av här,

17
00:00:39,080 --> 00:00:42,120
så om ni vill ta
En titt på det, helt bra.

18
00:00:42,120 --> 00:00:46,590
>> Så snabbt innan vi börjar, den
agenda för idag är följande.

19
00:00:46,590 --> 00:00:48,430
Som ni kan se, vi är
princip snabb bränning

20
00:00:48,430 --> 00:00:52,120
genom en hel del datastrukturer
verkligen, verkligen, verkligen snabbt.

21
00:00:52,120 --> 00:00:54,380
Så som sådant kommer det inte att vara
super interaktiv idag.

22
00:00:54,380 --> 00:00:59,620
Det ska bara vara mig slags skrika
saker som ni, och om jag förvirra dig,

23
00:00:59,620 --> 00:01:02,680
om jag går för fort, låt mig veta.

24
00:01:02,680 --> 00:01:05,200
De är bara olika data
strukturer, och som en del

25
00:01:05,200 --> 00:01:07,070
din pset för detta
kommande veckan, kommer du

26
00:01:07,070 --> 00:01:10,340
bli ombedd att genomföra en av dem,
kanske två av them-- två av dem

27
00:01:10,340 --> 00:01:12,319
i pset.

28
00:01:12,319 --> 00:01:14,610
OK, så jag ska bara
börja med några tillkännagivanden.

29
00:01:14,610 --> 00:01:19,070
Vi ska gå över stackar och köer mer i
djup än vad vi gjorde innan testet.

30
00:01:19,070 --> 00:01:20,990
Vi ska gå över kopplade
listan igen, återigen,

31
00:01:20,990 --> 00:01:23,899
mer ingående än vad
vi hade före testet.

32
00:01:23,899 --> 00:01:26,440
Och då kommer vi att tala om hash
tabeller, träd och försöker, som

33
00:01:26,440 --> 00:01:28,890
är alla ganska nödvändig för din pset.

34
00:01:28,890 --> 00:01:32,925
Och sedan ska vi gå igenom några
användbara tips för pset5.

35
00:01:32,925 --> 00:01:37,360
>> OK, så quiz 0.

36
00:01:37,360 --> 00:01:41,090
Den genomsnittliga var en 58%.

37
00:01:41,090 --> 00:01:45,370
Det var mycket låg, och så ni alla
gjorde mycket, mycket bra i enlighet

38
00:01:45,370 --> 00:01:46,510
med det.

39
00:01:46,510 --> 00:01:49,970
>> Ganska mycket, är tumregel om du är
inom en standardavvikelse från medelvärdet

40
00:01:49,970 --> 00:01:52,990
framför allt eftersom vi är i en mindre
bekväma avsnitt, du är helt bra.

41
00:01:52,990 --> 00:01:54,120
Du är på rätt spår.

42
00:01:54,120 --> 00:01:55,190
Livet är bra.

43
00:01:55,190 --> 00:01:58,952
>> Jag vet att det är skrämmande att tro att
Jag fick som en 40% på det här testet.

44
00:01:58,952 --> 00:02:00,160
Jag kommer att misslyckas den här klassen.

45
00:02:00,160 --> 00:02:02,243
Jag lovar dig, du är inte
kommer att misslyckas klassen.

46
00:02:02,243 --> 00:02:03,680
Du är helt bra.

47
00:02:03,680 --> 00:02:06,850
>> För er som fick över
medelvärdet, imponerande, imponerande,

48
00:02:06,850 --> 00:02:08,780
som, på allvar bra gjort.

49
00:02:08,780 --> 00:02:09,689
Jag har dem med mig.

50
00:02:09,689 --> 00:02:11,730
Känn dig fri att komma få dem
i slutet av avsnittet.

51
00:02:11,730 --> 00:02:14,520
Låt mig veta om du har några
frågor, frågor med dem.

52
00:02:14,520 --> 00:02:17,204
Om vi ​​lägger upp dina poäng
fel, låt oss veta.

53
00:02:17,204 --> 00:02:21,240
>> OK, så pset5, är detta ett riktigt
konstig vecka för Yale i den meningen

54
00:02:21,240 --> 00:02:24,240
att vår pset beror
Onsdag kl inklusive

55
00:02:24,240 --> 00:02:27,317
den sena dagen, så det är faktiskt
teoretiskt grund tisdag kl.

56
00:02:27,317 --> 00:02:29,150
Förmodligen ingen klar
tisdag kl.

57
00:02:29,150 --> 00:02:30,830
Det är helt bra.

58
00:02:30,830 --> 00:02:33,700
Vi kommer att ha kontorstid
ikväll samt måndag kväll.

59
00:02:33,700 --> 00:02:36,810
Och alla avsnitten här veckan kommer
faktiskt förvandlas till workshops,

60
00:02:36,810 --> 00:02:38,800
så känn dig fri att pop i
varje avsnitt som du vill,

61
00:02:38,800 --> 00:02:42,810
och de kommer att vara slags mini-pset
workshops för hjälp om det.

62
00:02:42,810 --> 00:02:45,620
Så som sådan, är detta den enda avsnitt
där vi undervisningsmaterial.

63
00:02:45,620 --> 00:02:49,220
Alla de andra delarna kommer att fokusera
uteslutande på hjälp för pset.

64
00:02:49,220 --> 00:02:50,146
Ja?

65
00:02:50,146 --> 00:02:52,000
>> PUBLIK: Var är kontorstid?

66
00:02:52,000 --> 00:02:56,120
>> ANDI PENG: Kontorstider
tonight-- oh, bra fråga.

67
00:02:56,120 --> 00:03:00,580
Jag tror kontorstid ikväll
är i kricka eller Commons.

68
00:03:00,580 --> 00:03:02,984
Om du kolla på nätet CS50
och du går till kontorstid,

69
00:03:02,984 --> 00:03:05,650
det bör finnas ett schema som
berättar om alla av dem är.

70
00:03:05,650 --> 00:03:07,954
>> Jag vet antingen ikväll
eller i morgon är kricka,

71
00:03:07,954 --> 00:03:10,120
och jag tror att vi kan ha
allmänningar för andra natten.

72
00:03:10,120 --> 00:03:11,020
Jag är inte säker.

73
00:03:11,020 --> 00:03:11,700
Bra fråga.

74
00:03:11,700 --> 00:03:14,430
Kontrollera på CS50.

75
00:03:14,430 --> 00:03:18,780
>> Cool, frågor om
schema för nästa som tre dagar?

76
00:03:18,780 --> 00:03:21,690
Jag lovar er killar som David
sagt, detta är toppen av kullen.

77
00:03:21,690 --> 00:03:23,050
Ni är nästan där.

78
00:03:23,050 --> 00:03:24,644
Bara tre dagar.

79
00:03:24,644 --> 00:03:26,310
Dit, och sedan kommer vi alla komma ner.

80
00:03:26,310 --> 00:03:28,114
Vi kommer att ha en trevlig CS-fria brytning.

81
00:03:28,114 --> 00:03:28,780
Vi ska komma tillbaka.

82
00:03:28,780 --> 00:03:30,779
Vi kommer att dyka in webb
programmering och utveckling,

83
00:03:30,779 --> 00:03:35,150
saker som är väldigt roligt jämfört
till några av de andra psets.

84
00:03:35,150 --> 00:03:37,974
Och det ska vara chill, och
Vi kommer att ha massor av kul.

85
00:03:37,974 --> 00:03:38,890
Vi kommer att ha mer godis.

86
00:03:38,890 --> 00:03:39,730
Ledsen för godis.

87
00:03:39,730 --> 00:03:40,945
Jag glömde godis.

88
00:03:40,945 --> 00:03:43,310
Det var en tuff morgon.

89
00:03:43,310 --> 00:03:46,340
Så ni är nästan där,
och jag är verkligen stolt över er.

90
00:03:46,340 --> 00:03:49,570
>> OK, så stackar.

91
00:03:49,570 --> 00:03:53,331
Vem älskade fråga om Jack
och hans kläder på frågesport?

92
00:03:53,331 --> 00:03:53,830
Ingen?

93
00:03:53,830 --> 00:03:56,500
OK, det är bra.

94
00:03:56,500 --> 00:04:00,200
>> Så i huvudsak du kan
bild Jack, den här killen här,

95
00:04:00,200 --> 00:04:03,350
gillar att ta kläder
ut ur toppen av stacken,

96
00:04:03,350 --> 00:04:05,750
och han sätter tillbaka den på
stacken efter att han har gjort.

97
00:04:05,750 --> 00:04:07,600
Så på detta sätt, han aldrig
verkar vara att få

98
00:04:07,600 --> 00:04:10,090
till botten av den
stack i hans kläder.

99
00:04:10,090 --> 00:04:12,600
Så denna typ av beskriver
den grundläggande datastrukturen

100
00:04:12,600 --> 00:04:16,610
av hur en stapel är implementerad.

101
00:04:16,610 --> 00:04:20,060
>> I huvudsak, tänk på en
stapla så en stapel av föremål

102
00:04:20,060 --> 00:04:24,900
var du lagt saker på toppen, och
då du hoppar ut dem uppifrån.

103
00:04:24,900 --> 00:04:28,600
Så LIFO är förkortningen vi gillar
att use-- sist in först ut.

104
00:04:28,600 --> 00:04:32,480
Och så sista i till toppen av den
stack är den första som kommer ut.

105
00:04:32,480 --> 00:04:34,260
Och så de två begreppen
vi vill associera

106
00:04:34,260 --> 00:04:36,190
med som kallas tryck och pop.

107
00:04:36,190 --> 00:04:39,790
När du trycker något på
stack, och du pop upp den igen.

108
00:04:39,790 --> 00:04:43,422
>> Och så jag antar att detta är typ av en
abstrakt begrepp för dig

109
00:04:43,422 --> 00:04:45,630
som vill se som en
faktiska genomförandet av detta

110
00:04:45,630 --> 00:04:46,740
i den verkliga världen.

111
00:04:46,740 --> 00:04:50,170
Hur många av er har skrivit en uppsats
kanske som en timme innan det berodde,

112
00:04:50,170 --> 00:04:54,510
och du råkat ta bort en enorm
bit av det, som av misstag?

113
00:04:54,510 --> 00:04:58,560
Och vad kontroll gör
vi använder för att sätta tillbaka den?

114
00:04:58,560 --> 00:05:00,030
Kontroll-Z, ja?

115
00:05:00,030 --> 00:05:03,640
Kontroll-Z, så antalet gånger
att Ctrl-Z har räddat mitt liv,

116
00:05:03,640 --> 00:05:08,820
har räddat min röv, varje gång
som är genomförs genom en stapel.

117
00:05:08,820 --> 00:05:13,020
>> I princip all information
det är på din Word-dokument,

118
00:05:13,020 --> 00:05:15,080
det blir knuffade och dök efter behag.

119
00:05:15,080 --> 00:05:19,460
Och så i huvudsak när du
bort någonting, pop du upp den igen.

120
00:05:19,460 --> 00:05:22,820
Och sedan om du behöver det igen, du
driva det, vilket är vad Ctrl-C gör.

121
00:05:22,820 --> 00:05:26,770
Och så verkliga världen funktion
av hur enkel datastruktur

122
00:05:26,770 --> 00:05:28,690
kan hjälpa till med din vardag.

123
00:05:28,690 --> 00:05:31,710

124
00:05:31,710 --> 00:05:40,150
>> Så en struct är det sätt som
vi faktiskt skapa en stapel.

125
00:05:40,150 --> 00:05:44,720
Vi skriver definiera struct, och sedan
vi kallar det stack i botten.

126
00:05:44,720 --> 00:05:47,440
Och inom stapeln,
vi har två parametrar

127
00:05:47,440 --> 00:05:51,580
att vi kan i huvudsak manipulera,
så vi har röding stjärnan strängar kapacitet.

128
00:05:51,580 --> 00:05:55,150
>> Allt som gör
skapar en array

129
00:05:55,150 --> 00:05:58,835
att vi kan lagra vad du vill
som vi kan avgöra dess kapacitet.

130
00:05:58,835 --> 00:06:01,990
Kapaciteten är bara max antal
objekt kan vi sätta in denna uppsättning.

131
00:06:01,990 --> 00:06:05,660
int storlek är den räknare som håller
reda på hur många objekt finns för närvarande

132
00:06:05,660 --> 00:06:07,850
i stapeln.

133
00:06:07,850 --> 00:06:11,860
Så då kan vi hålla reda på, A,
både hur stor själva stapeln är,

134
00:06:11,860 --> 00:06:14,850
och B, hur mycket av det stack
fyllde vi eftersom vi inte vill

135
00:06:14,850 --> 00:06:18,800
att svämma över vad vår kapacitet är.

136
00:06:18,800 --> 00:06:24,340
>> Så till exempel, denna härliga
Frågan var på frågesport.

137
00:06:24,340 --> 00:06:28,160
I huvudsak hur gör vi driva
på toppen av en stapel.

138
00:06:28,160 --> 00:06:28,830
Ganska enkelt.

139
00:06:28,830 --> 00:06:30,621
Om man ser på det,
Vi kommer att gå igenom det här.

140
00:06:30,621 --> 00:06:32,640
Om [OHÖRBAR] size--
kom ihåg, när du

141
00:06:32,640 --> 00:06:35,300
vill komma åt alla
parameter inom en struct,

142
00:06:35,300 --> 00:06:40,320
du gör namnet på struct.parameter.

143
00:06:40,320 --> 00:06:42,720
>> I detta fall är s
namnet på vår stack.

144
00:06:42,720 --> 00:06:46,230
Vi vill komma åt storlek
av det, så vi gör s.size.

145
00:06:46,230 --> 00:06:50,280
Så länge som storleken inte är
lika med kapacitet eller så länge

146
00:06:50,280 --> 00:06:52,940
eftersom det är mindre än kapacitet,
antingen skulle fungera här.

147
00:06:52,940 --> 00:06:57,180
>> Du vill komma åt insidan
av din stack, så s.strings,

148
00:06:57,180 --> 00:07:00,790
och du kommer att sätta det nya numret
som du vill infoga i det.

149
00:07:00,790 --> 00:07:05,030
Låt oss bara säga att vi kommer att vilja
infoga int n på stacken,

150
00:07:05,030 --> 00:07:08,905
vi kunde göra s.strings,
konsoler, är lika s.size n.

151
00:07:08,905 --> 00:07:11,030
Eftersom storleken är där vi
närvarande finns i stapeln

152
00:07:11,030 --> 00:07:14,590
Om vi ​​ska driva
det på, vi bara tillgång

153
00:07:14,590 --> 00:07:17,370
varhelst storleken är, desto
nuvarande fullhet av stapeln,

154
00:07:17,370 --> 00:07:21,729
och vi driva int n på det.

155
00:07:21,729 --> 00:07:24,770
Och sedan vill vi se till att
vi också stega storlek n,

156
00:07:24,770 --> 00:07:27,436
så att vi kan hålla reda på vi har
lagt till en extra sak till stacken.

157
00:07:27,436 --> 00:07:29,660
Nu har vi en större storlek.

158
00:07:29,660 --> 00:07:33,196
Innebär detta här vettigt att
alla, hur logiskt det fungerar?

159
00:07:33,196 --> 00:07:34,160
Det var typ av snabb.

160
00:07:34,160 --> 00:07:39,535

161
00:07:39,535 --> 00:07:42,160
PUBLIK: Kan du gå över
de s.stringss.strings [s.size] igen?

162
00:07:42,160 --> 00:07:45,808
ANDI PENG: Visst, så vad gör
s.size närvarande ge oss?

163
00:07:45,808 --> 00:07:47,440
PUBLIK: Det är den nuvarande storleken.

164
00:07:47,440 --> 00:07:50,890
ANDI PENG: Exakt, så
nuvarande index som vår storlek är,

165
00:07:50,890 --> 00:07:57,780
och så vill vi sätta nya heltal
att vi vill infoga i s.size.

166
00:07:57,780 --> 00:07:58,760
Betyder det vettigt?

167
00:07:58,760 --> 00:08:01,110
Eftersom s.strings, allt
är är namnet på uppsättningen.

168
00:08:01,110 --> 00:08:03,510
Allt som är är tillgång till
array inom vår struct,

169
00:08:03,510 --> 00:08:06,030
och så om vi vill
placera n till detta index,

170
00:08:06,030 --> 00:08:09,651
vi kan bara komma åt den
med byglar s.size.

171
00:08:09,651 --> 00:08:10,150
Häftigt.

172
00:08:10,150 --> 00:08:13,580

173
00:08:13,580 --> 00:08:18,916
>> Okej, pop, jag pseudokod ut
för er, men liknande koncept.

174
00:08:18,916 --> 00:08:19,790
Betyder det vettigt?

175
00:08:19,790 --> 00:08:22,310
Om storleken är större
än noll, då du

176
00:08:22,310 --> 00:08:25,350
vet att du vill ta något
ut eftersom om storleken är inte

177
00:08:25,350 --> 00:08:27,620
större än noll, då du
har ingenting i stapeln.

178
00:08:27,620 --> 00:08:29,840
>> Så du bara vill köra
denna kod, kan det bara

179
00:08:29,840 --> 00:08:32,320
pop om det finns något att pop.

180
00:08:32,320 --> 00:08:35,830
Så om storleken är större
än 0, vi minus storleken.

181
00:08:35,830 --> 00:08:40,020
Vi dekrementera storlek och sedan återvända
vad är inne i det eftersom

182
00:08:40,020 --> 00:08:42,710
genom att poppa, vill vi
tillgång oavsett lagras

183
00:08:42,710 --> 00:08:45,694
i index för den överst i stacken.

184
00:08:45,694 --> 00:08:46,610
Allt vettigt?

185
00:08:46,610 --> 00:08:49,693
Om jag gjorde ni skriver ut det här,
skulle ni kunna skriva ut det?

186
00:08:49,693 --> 00:08:52,029

187
00:08:52,029 --> 00:08:53,570
OK, kan ni leka med den.

188
00:08:53,570 --> 00:08:55,252
Inga bekymmer om du inte får det.

189
00:08:55,252 --> 00:08:57,460
Vi har inte tid att koda
det idag eftersom vi har

190
00:08:57,460 --> 00:08:59,959
fick en hel del av dessa strukturer
att gå igenom, men i huvudsak

191
00:08:59,959 --> 00:09:02,214
pseudokod, mycket, mycket likt att driva.

192
00:09:02,214 --> 00:09:03,380
Bara följa logiken.

193
00:09:03,380 --> 00:09:06,092
Se till att du tillgång till alla
funktioner i din struct korrekt.

194
00:09:06,092 --> 00:09:06,574
Ja?

195
00:09:06,574 --> 00:09:09,282
>> PUBLIK: Kommer dessa bilder och
Hela den här grejen upp idag-ish?

196
00:09:09,282 --> 00:09:11,586
ANDI PENG: Alltid, Japp.

197
00:09:11,586 --> 00:09:13,710
Jag ska försöka att sätta
detta upp som en timme efter.

198
00:09:13,710 --> 00:09:16,626
Jag kommer att skicka David, kommer David att försöka
sätta upp som en timme efter detta.

199
00:09:16,626 --> 00:09:20,040

200
00:09:20,040 --> 00:09:25,470
>> OK, så då vi går in i denna andra
vackra datastruktur som kallas en kö.

201
00:09:25,470 --> 00:09:30,140
Som ni kan se här, en
kö, för den brittiska bland oss,

202
00:09:30,140 --> 00:09:32,010
allt är det är en linje.

203
00:09:32,010 --> 00:09:34,680
Så till skillnad från vad
du tror att en stapel är,

204
00:09:34,680 --> 00:09:37,750
en kö är precis vad
logiskt du tycker att det är.

205
00:09:37,750 --> 00:09:41,914
Det innehas av reglerna i FIFO,
som är först in, först ut.

206
00:09:41,914 --> 00:09:43,705
Om du är den första
ett i raden, du är

207
00:09:43,705 --> 00:09:46,230
först en som
kommer ut på linjen.

208
00:09:46,230 --> 00:09:49,680
>> Så vad vi vill kalla detta
är dequeueing och enqueueing.

209
00:09:49,680 --> 00:09:52,380
Om vi ​​vill lägga till något
till vår kö, köa vi.

210
00:09:52,380 --> 00:09:55,690
Om vi ​​vill avköa, eller ta
bort något, avköa vi.

211
00:09:55,690 --> 00:10:03,350
>> Så samma sätt som vi är typ av
skapa fast storlek element som vi

212
00:10:03,350 --> 00:10:06,500
kan lagra vissa
saker, men vi kan också

213
00:10:06,500 --> 00:10:10,100
ändra där vi placerar
parametrar insidan av dem

214
00:10:10,100 --> 00:10:13,140
baserat på vilken typ av
funktionalitet vi vill.

215
00:10:13,140 --> 00:10:16,700
Så stackar, ville vi den sista
en, N att vara först ut.

216
00:10:16,700 --> 00:10:19,800
Kö är vi vill att första
in för att vara det första ut.

217
00:10:19,800 --> 00:10:22,510

218
00:10:22,510 --> 00:10:26,710
>> Så struct-typ
definiera, som ni kan se,

219
00:10:26,710 --> 00:10:29,470
Det är lite annorlunda
från vad stapeln var

220
00:10:29,470 --> 00:10:33,120
eftersom inte bara vi måste hålla
reda på var storleken för närvarande är,

221
00:10:33,120 --> 00:10:37,420
vi vill också att hålla reda på huvudet
samt där vi är idag.

222
00:10:37,420 --> 00:10:39,580
Så jag tror att det är lättare
om jag drar upp denna.

223
00:10:39,580 --> 00:10:53,270
Så låt oss föreställa oss att vi har en kö,
så låt oss säga huvudet är rätt här.

224
00:10:53,270 --> 00:10:55,811

225
00:10:55,811 --> 00:10:58,310
Chefen för linjen, låt oss
bara säga att det är för närvarande finns,

226
00:10:58,310 --> 00:11:01,809
och vi vill infoga
något i kön.

227
00:11:01,809 --> 00:11:04,350
Jag ska ringa storlek i huvudsak
är samma sak som svans,

228
00:11:04,350 --> 00:11:06,314
I slutet av vart din kö är.

229
00:11:06,314 --> 00:11:07,730
Låt oss bara säga storleken är rätt här.

230
00:11:07,730 --> 00:11:14,380

231
00:11:14,380 --> 00:11:18,400
>> Så hur gör man rimligen
infoga något i en kö?

232
00:11:18,400 --> 00:11:21,000

233
00:11:21,000 --> 00:11:24,130
Vad index vill vi placera
där vi vill infoga i.

234
00:11:24,130 --> 00:11:29,320
Om detta är början av din
kö och det är i slutet av det

235
00:11:29,320 --> 00:11:31,860
eller storleken på det, där vi
vill lägga nästa objekt?

236
00:11:31,860 --> 00:11:32,920
>> PUBLIK: [OHÖRBAR]

237
00:11:32,920 --> 00:11:35,920
ANDI PENG: Just det, du vill lägga till
det beroende på har du skrivit det.

238
00:11:35,920 --> 00:11:37,840
Antingen är tom eller som är tom.

239
00:11:37,840 --> 00:11:42,630
Så du vill lägga till det förmodligen
här eftersom om storleken är--

240
00:11:42,630 --> 00:11:50,540
om dessa är alla fulla, du vill
till den här, eller hur?

241
00:11:50,540 --> 00:11:57,150
>> Och så det är, medan mycket, mycket
enkel, inte riktigt alltid korrekt

242
00:11:57,150 --> 00:12:00,690
eftersom den huvudsakliga skillnaden
mellan en kö och en stapel

243
00:12:00,690 --> 00:12:04,350
är att kön kan
faktiskt manipuleras

244
00:12:04,350 --> 00:12:06,980
så att huvudet förändringar
beroende på var du vill

245
00:12:06,980 --> 00:12:08,650
i början av din kö för att börja.

246
00:12:08,650 --> 00:12:11,900
Och som ett resultat, din svans
kommer också att förändras.

247
00:12:11,900 --> 00:12:14,770
Och så ta en titt på
denna kod just nu.

248
00:12:14,770 --> 00:12:18,620
Som ni ombads också att
skriva ut på frågesport, enqueue.

249
00:12:18,620 --> 00:12:22,580
Kanske ska vi prata igenom varför
svaret var vad det var.

250
00:12:22,580 --> 00:12:26,790
>> Jag kunde inte riktigt passar in i denna linje på en,
men i huvudsak denna del av koden

251
00:12:26,790 --> 00:12:29,030
ska vara på en rad.

252
00:12:29,030 --> 00:12:30,140
Spendera som 30 sekunder.

253
00:12:30,140 --> 00:12:33,000
Ta en titt och se varför
detta är det sätt som det är.

254
00:12:33,000 --> 00:12:50,030

255
00:12:50,030 --> 00:12:55,420
>> Mycket, mycket liknande struct, mycket, mycket
liknande struktur som den tidigare

256
00:12:55,420 --> 00:12:58,090
stack utom kanske
en kodrad.

257
00:12:58,090 --> 00:13:01,190
Och att en kodrad
bestämmer funktionaliteten.

258
00:13:01,190 --> 00:13:03,900
Och det är verkligen skiljer
en kö från en stapel.

259
00:13:03,900 --> 00:13:18,510

260
00:13:18,510 --> 00:13:22,010
>> Någon som vill ta ett knivhugg
på att förklara varför du har

261
00:13:22,010 --> 00:13:24,980
fick denna komplicerade sak här?

262
00:13:24,980 --> 00:13:27,845
Vi ser återlämnande av vår
underbar vän modul.

263
00:13:27,845 --> 00:13:31,020
Som ni snart kommer
att känna igen i programmering,

264
00:13:31,020 --> 00:13:34,910
nästan när du behöver något
att linda runt någonting,

265
00:13:34,910 --> 00:13:36,850
modul kommer att vara ett sätt att göra det.

266
00:13:36,850 --> 00:13:40,510
Så att veta att någon som vill
att försöka förklara att kodraden?

267
00:13:40,510 --> 00:13:44,060

268
00:13:44,060 --> 00:13:47,507
Ja, alla svar är
accepterad och välkommen.

269
00:13:47,507 --> 00:13:48,840
PUBLIK: Pratar du med mig?

270
00:13:48,840 --> 00:13:49,506
ANDI PENG: Ja.

271
00:13:49,506 --> 00:13:56,200
Målgrupp: Åh, nej tyvärr.

272
00:13:56,200 --> 00:14:00,250
ANDI PENG: OK, så låt oss
gå igenom denna kod.

273
00:14:00,250 --> 00:14:03,642
Så när du försöker
lägga till något på en kö,

274
00:14:03,642 --> 00:14:08,510
i den vackra så att huvudet händer
att vara just här, är det väldigt lätt för oss

275
00:14:08,510 --> 00:14:10,960
att bara gå till slutet
infoga något, eller hur?

276
00:14:10,960 --> 00:14:14,690
Men hela poängen med en kö är
att huvudet kan faktiskt dynamiskt

277
00:14:14,690 --> 00:14:17,280
ändras beroende på var vi
vill i början av vår q att vara,

278
00:14:17,280 --> 00:14:19,880
och som sådan, svansen
kommer också att förändras.

279
00:14:19,880 --> 00:14:31,100
>> Och så föreställa sig att detta inte var den
kö, utan det var kö.

280
00:14:31,100 --> 00:14:37,900

281
00:14:37,900 --> 00:14:39,330
Låt oss säga att huvudet är rätt här.

282
00:14:39,330 --> 00:14:54,900

283
00:14:54,900 --> 00:14:56,980
Låt oss säga vår kö såg ut så här.

284
00:14:56,980 --> 00:15:00,190
Om vi ​​ville flytta där
början av raden är,

285
00:15:00,190 --> 00:15:03,400
Låt oss säga att vi skiftade huvudet
detta sätt och storlekarna här.

286
00:15:03,400 --> 00:15:07,100
>> Nu vill vi lägga till något till
denna kö, men som ni kan se,

287
00:15:07,100 --> 00:15:11,150
det är inte så enkelt som att bara
lägga till vad är efter storlek

288
00:15:11,150 --> 00:15:13,630
för då kör vi ut ur
gränserna för våra faktiska array.

289
00:15:13,630 --> 00:15:16,190
Där vi verkligen vill lägga till är här.

290
00:15:16,190 --> 00:15:18,610
Det är skönheten i en kö
är det oss, visuellt det

291
00:15:18,610 --> 00:15:22,380
ser ut linjen går så här,
men när det lagras i en datastruktur,

292
00:15:22,380 --> 00:15:29,370
de ger den som som en cykel.

293
00:15:29,370 --> 00:15:32,360
Den sveper slags runt
till framsidan på samma sätt

294
00:15:32,360 --> 00:15:34,780
att en linje kan också linda
runt beroende på vart du

295
00:15:34,780 --> 00:15:36,279
vill början av raden för att vara.

296
00:15:36,279 --> 00:15:38,630
Och så om vi tar en
titta ner här, låt oss

297
00:15:38,630 --> 00:15:40,880
säger vi ville skapa en
Funktionen kallas enqueue.

298
00:15:40,880 --> 00:15:43,980
Vi ville lägga int n till att q.

299
00:15:43,980 --> 00:15:49,250
Om q.size q-- vi kallar att våra data
structure-- om vår queue.size inte

300
00:15:49,250 --> 00:15:52,520
lika med kapaciteten eller om
det är mindre än kapacitet,

301
00:15:52,520 --> 00:15:55,120
q.strings är arrayen inom vår q.

302
00:15:55,120 --> 00:15:58,380
Vi kommer att ställa
som är lika med q.heads,

303
00:15:58,380 --> 00:16:02,730
vilket är just här, plus q.size
modul av kapaciteten, som

304
00:16:02,730 --> 00:16:04,290
linda oss tillbaka runt här.

305
00:16:04,290 --> 00:16:08,040
>> Så i det här exemplet, index
huvud är en, eller hur?

306
00:16:08,040 --> 00:16:11,480
Indexet storlek är 0, 1, 2, 3, 4.

307
00:16:11,480 --> 00:16:19,500
Så vi kan göra ett plus 4 modul
av vår kapacitet som är fem.

308
00:16:19,500 --> 00:16:20,920
Vad som ger oss?

309
00:16:20,920 --> 00:16:23,270
Vad är det index som
kommer ut av detta?

310
00:16:23,270 --> 00:16:24,080
>> PUBLIK: 0.

311
00:16:24,080 --> 00:16:27,870
>> ANDI Peng: 0, vilket
råkar vara just här,

312
00:16:27,870 --> 00:16:30,640
och så vi vill kunna
att sätta in just här.

313
00:16:30,640 --> 00:16:34,730
Och så denna ekvation här typ
på bara fungerar med alla siffror

314
00:16:34,730 --> 00:16:36,750
beroende på var din
huvud och din storlek är.

315
00:16:36,750 --> 00:16:38,541
Om du vet vad de
saker är, du vet

316
00:16:38,541 --> 00:16:43,170
precis där du vill infoga
vad är efter kön.

317
00:16:43,170 --> 00:16:44,640
Innebär det vettigt att alla?

318
00:16:44,640 --> 00:16:48,560
>> Jag vet lite av en hjärna
teaser särskilt eftersom detta

319
00:16:48,560 --> 00:16:50,512
kom i efterdyningarna av din frågesport.

320
00:16:50,512 --> 00:16:52,220
Men förhoppningsvis alla
nu kan förstå

321
00:16:52,220 --> 00:16:57,800
varför denna lösning eller detta
funktion är det sätt som det är.

322
00:16:57,800 --> 00:16:59,840
Någon lite oklart om det?

323
00:16:59,840 --> 00:17:03,471

324
00:17:03,471 --> 00:17:03,970
OK.

325
00:17:03,970 --> 00:17:07,109

326
00:17:07,109 --> 00:17:09,970
>> Och så nu, om du
ville avköa, detta

327
00:17:09,970 --> 00:17:15,240
är där vår huvud skulle flytta
Om vi ​​skulle avköa,

328
00:17:15,240 --> 00:17:17,030
vi tar inte ut i slutet av q.

329
00:17:17,030 --> 00:17:19,130
Vi vill ta bort huvudet, eller hur?

330
00:17:19,130 --> 00:17:24,260
Så som ett resultat, är huvudet kommer att förändras,
och det är därför när du köa,

331
00:17:24,260 --> 00:17:26,800
du måste hålla reda på
där ditt huvud och din storlek

332
00:17:26,800 --> 00:17:29,450
skall kunna sätta in
i rätt läge.

333
00:17:29,450 --> 00:17:32,740
>> Och så när du avköa,
Jag Pseudokod det också.

334
00:17:32,740 --> 00:17:35,480
Känn dig fri att om du vill
att försöka koda detta.

335
00:17:35,480 --> 00:17:36,980
Du vill flytta huvudet, eller hur?

336
00:17:36,980 --> 00:17:39,320
Om jag ville avköa jag
skulle flytta huvudet över.

337
00:17:39,320 --> 00:17:40,800
Detta skulle vara huvudet.

338
00:17:40,800 --> 00:17:45,617
>> Och vår nuvarande storlek skulle
subtrahera eftersom vi inte längre

339
00:17:45,617 --> 00:17:46,950
har fyra element i arrayen.

340
00:17:46,950 --> 00:17:51,370
Vi har bara tre, och då vill vi
att återvända vad förvarades inne

341
00:17:51,370 --> 00:17:56,260
av huvudet eftersom vi vill ta detta
värde ut så mycket lik stapeln.

342
00:17:56,260 --> 00:17:58,010
Bara du tar
från en annan plats,

343
00:17:58,010 --> 00:18:01,770
och du måste överlåta din pekaren
till annan plats som följd.

344
00:18:01,770 --> 00:18:03,890
Logiskt sett alla följa?

345
00:18:03,890 --> 00:18:05,690
Bra.

346
00:18:05,690 --> 00:18:10,156
>> OK, så vi kommer att prata lite
mer på djupet om länkade listor

347
00:18:10,156 --> 00:18:13,280
eftersom de kommer att vara mycket, mycket värdefullt
för dig under denna veckas

348
00:18:13,280 --> 00:18:14,964
psets.

349
00:18:14,964 --> 00:18:17,130
Länkade listor, som ni
kan minnas, allt de är

350
00:18:17,130 --> 00:18:22,570
är noder som är noder av vissa
värden för både ett värde och en pekare

351
00:18:22,570 --> 00:18:26,290
som är kopplade till varandra
av dessa pekare.

352
00:18:26,290 --> 00:18:29,880
Och så struct om hur
Vi skapar en nod här är vi

353
00:18:29,880 --> 00:18:33,569
har int n, vilket är vad
värdet i en butik eller sträng n

354
00:18:33,569 --> 00:18:35,610
eller vad du vill
kallar det, rödingen stjärnan n.

355
00:18:35,610 --> 00:18:41,482
Struct nod stjärnan som är pekaren
som du vill ha i varje nod,

356
00:18:41,482 --> 00:18:43,690
du kommer att ha det
pekaren pekar mot nästa.

357
00:18:43,690 --> 00:18:48,207

358
00:18:48,207 --> 00:18:50,040
Du kommer att ha huvudet
av en länkad lista som är

359
00:18:50,040 --> 00:18:53,140
kommer att peka till resten av
värdena så vidare och så vidare

360
00:18:53,140 --> 00:18:55,290
tills du slutligen når slutet.

361
00:18:55,290 --> 00:18:58,040
Och detta sista noden är bara
kommer att inte ha en pekare.

362
00:18:58,040 --> 00:18:59,952
Det kommer att peka på
null, är och att när

363
00:18:59,952 --> 00:19:01,910
du vet att du har drabbats
slutet av din länkad lista

364
00:19:01,910 --> 00:19:04,076
är när din sista pekaren
pekar inte på något.

365
00:19:04,076 --> 00:19:06,670

366
00:19:06,670 --> 00:19:10,990
>> Så vi kommer att gå lite mer
djup om hur man skulle kunna

367
00:19:10,990 --> 00:19:12,400
söka i en länkad lista.

368
00:19:12,400 --> 00:19:15,460
Kom ihåg vad är några av de
nackdelarna med de länkade listor

369
00:19:15,460 --> 00:19:19,340
vers en array om sökningar.

370
00:19:19,340 --> 00:19:22,565
En array kan du binär sökning, men
varför kan du inte göra det i en länkad lista?

371
00:19:22,565 --> 00:19:26,834

372
00:19:26,834 --> 00:19:30,320
>> PUBLIK: Eftersom de är alla anslutna,
men du vet inte riktigt var

373
00:19:30,320 --> 00:19:31,330
[OHÖRBAR].

374
00:19:31,330 --> 00:19:34,600
>> ANDI PENG: Ja, precis så kom ihåg
att briljans av en matris

375
00:19:34,600 --> 00:19:37,190
var det faktum att vi hade
direktminne där

376
00:19:37,190 --> 00:19:41,580
om jag ville värdet från index
sex, jag kunde bara säga index sex,

377
00:19:41,580 --> 00:19:42,407
ge mig det värdet.

378
00:19:42,407 --> 00:19:45,240
Och det beror på matriser sorteras
i en angränsande utrymme minne

379
00:19:45,240 --> 00:19:48,020
på ett ställe, medan
typ av länkade listor

380
00:19:48,020 --> 00:19:52,820
är slumpmässigt varvas runt,
och det enda sättet du kan hitta en

381
00:19:52,820 --> 00:19:56,890
är genom en pekare som talar om
adressen där att nästa nod är.

382
00:19:56,890 --> 00:20:00,290
>> Och så som ett resultat, är det enda sättet
söka igenom en länkad lista

383
00:20:00,290 --> 00:20:01,560
är linjär sökning.

384
00:20:01,560 --> 00:20:05,890
Eftersom jag inte exakt vet var
den 12: e värdet i den länkade listan är,

385
00:20:05,890 --> 00:20:08,780
Jag måste korsa helheten
av det länkad lista en

386
00:20:08,780 --> 00:20:12,450
med en från huvudet till den första noden,
till den andra noden, till den tredje noden,

387
00:20:12,450 --> 00:20:17,690
hela vägen ner tills jag äntligen få
där noden jag letar efter är.

388
00:20:17,690 --> 00:20:22,110
Och så i denna mening, sök
på en länkad lista är alltid n.

389
00:20:22,110 --> 00:20:23,040
Det är alltid n.

390
00:20:23,040 --> 00:20:25,690
Det är alltid i linjär tid.

391
00:20:25,690 --> 00:20:28,470
>> Och så koden i vilken
vi genomföra detta, och detta

392
00:20:28,470 --> 00:20:32,620
är lite nytt för er eftersom ni
killar har inte riktigt pratat om eller någonsin

393
00:20:32,620 --> 00:20:35,000
sett pekare i hur man
söka igenom pekare,

394
00:20:35,000 --> 00:20:37,670
så vi kommer att gå igenom
detta mycket, mycket långsamt.

395
00:20:37,670 --> 00:20:40,200
Så bool ökning, höger,
Låt oss föreställa oss att vi vill ha

396
00:20:40,200 --> 00:20:42,820
för att skapa en funktion som kallas
sökning som returnerar true

397
00:20:42,820 --> 00:20:46,820
om du hittade ett värde inuti den länkade
lista, och returnerar i annat fall false.

398
00:20:46,820 --> 00:20:50,030
Nod stjärna lista är
för närvarande bara pekaren

399
00:20:50,030 --> 00:20:52,960
den första punkten i länkad lista.

400
00:20:52,960 --> 00:20:56,700
int n är det värde som du
söker efter i listan.

401
00:20:56,700 --> 00:20:58,770
>> Så nod stjärnpekaren lika listan.

402
00:20:58,770 --> 00:21:00,970
Det betyder att vi inställning
och skapa en pekare

403
00:21:00,970 --> 00:21:03,592
till det första noden inne i listan.

404
00:21:03,592 --> 00:21:04,300
Alla med mig?

405
00:21:04,300 --> 00:21:06,530
Så om vi skulle gå
tillbaka hit, skulle jag ha

406
00:21:06,530 --> 00:21:13,850
initieras en pekare som pekar på
chefen för vad denna lista är.

407
00:21:13,850 --> 00:21:18,600
>> Och när du kommer ner hit,
medan pekaren inte lika null,

408
00:21:18,600 --> 00:21:22,160
så det är den slinga, i vilken vi är
kommer att bli därefter korsa

409
00:21:22,160 --> 00:21:25,940
resten av vår lista eftersom det
händer när pekaren är lika med noll?

410
00:21:25,940 --> 00:21:27,550
Vi vet att vi have--

411
00:21:27,550 --> 00:21:28,450
>> PUBLIK: [OHÖRBAR]

412
00:21:28,450 --> 00:21:31,491
>> ANDI PENG: Exakt, så vi vet att
Vi har nått slutet av listan, eller hur?

413
00:21:31,491 --> 00:21:34,470
Om du går tillbaka hit, varje nod
skall peka till en annan nod

414
00:21:34,470 --> 00:21:36,550
och så vidare och så vidare
tills du träffar så småningom

415
00:21:36,550 --> 00:21:41,589
svansen på din länkad lista,
som har en pekare som bara

416
00:21:41,589 --> 00:21:43,130
pekar inte någon annanstans än inget.

417
00:21:43,130 --> 00:21:47,510
Och så du i princip vet att
listan är fortfarande där uppe

418
00:21:47,510 --> 00:21:50,900
tills visaren inte är lika
null eftersom när det är lika med noll,

419
00:21:50,900 --> 00:21:53,310
du vet att det inte finns något mer grejer.

420
00:21:53,310 --> 00:21:56,930
>> Så det är slingan där vi är
kommer att ha den faktiska sökt.

421
00:21:56,930 --> 00:22:01,690
Och om pointer-- ser du
den typen av pilen fungerar det?

422
00:22:01,690 --> 00:22:06,930
Så om pekaren pekar på n, om
pekaren på n är lika med lika n

423
00:22:06,930 --> 00:22:09,180
så det betyder att om
pekaren att du är

424
00:22:09,180 --> 00:22:13,420
söker efter på i slutet av varje
nod är faktiskt lika med värdet

425
00:22:13,420 --> 00:22:15,990
du letar efter, då
du vill return true.

426
00:22:15,990 --> 00:22:19,280
Så i princip, om du är på en nod som
har det värde som du letar efter,

427
00:22:19,280 --> 00:22:23,550
du vet att du har varit
kunna framgångsrikt söka.

428
00:22:23,550 --> 00:22:27,150
>> Annars, du vill ställa in
pekaren till nästa nod.

429
00:22:27,150 --> 00:22:28,850
Det är vad den linjen här gör.

430
00:22:28,850 --> 00:22:31,750
Pointer lika pekare nästa.

431
00:22:31,750 --> 00:22:33,360
Alla se hur det fungerar?

432
00:22:33,360 --> 00:22:36,580
>> Och i huvudsak du ska bara
genomlöpa hela den listan,

433
00:22:36,580 --> 00:22:41,920
återställa pekaren varje gång tills
du så småningom slog i slutet av listan.

434
00:22:41,920 --> 00:22:45,030
Och du vet att det inte finns några
fler noder att söka igenom,

435
00:22:45,030 --> 00:22:47,999
och sedan kan du returnera false
eftersom du vet att, åh, ja,

436
00:22:47,999 --> 00:22:50,540
om jag har kunnat söka
genom helheten av listan.

437
00:22:50,540 --> 00:22:54,530
Om det i detta exempel, om jag ville
att leta efter värdet på 10,

438
00:22:54,530 --> 00:22:57,250
och jag börjar i spetsen, och
Jag söker hela vägen ner,

439
00:22:57,250 --> 00:23:00,550
och jag fick så småningom till detta, vilket
en pekare som pekar på noll,

440
00:23:00,550 --> 00:23:04,415
Jag vet att, skit, jag antar att 10 inte är i
den här listan eftersom jag kunde inte hitta den.

441
00:23:04,415 --> 00:23:06,520
Och jag är i slutet av listan.

442
00:23:06,520 --> 00:23:11,040
Och i vilket fall du känner
Jag kommer att returnera false.

443
00:23:11,040 --> 00:23:12,900
>> Låt det verka i en liten bit.

444
00:23:12,900 --> 00:23:17,350
Detta kommer att vara ganska
viktigt för din pset.

445
00:23:17,350 --> 00:23:21,140
Logiken i den är mycket enkel, kanske
syntaktiskt bara genomföra det.

446
00:23:21,140 --> 00:23:23,365
Ni vill göra
Se till att du förstår.

447
00:23:23,365 --> 00:23:25,870

448
00:23:25,870 --> 00:23:27,650
Häftigt.

449
00:23:27,650 --> 00:23:32,560
>> OK, så hur vi skulle vara
infoga noder, höger,

450
00:23:32,560 --> 00:23:35,380
i en lista eftersom ihåg
vad är det som om fördelarna

451
00:23:35,380 --> 00:23:39,230
av att ha en länkad lista kontra
en matris i form av lagring?

452
00:23:39,230 --> 00:23:41,110
>> PUBLIK: Det är dynamisk,
så det är lättare att--

453
00:23:41,110 --> 00:23:43,180
>> ANDI PENG: Exakt,
så det är dynamiskt, vilket

454
00:23:43,180 --> 00:23:46,880
innebär att det kan expandera och krympa
beroende på användarens behov.

455
00:23:46,880 --> 00:23:56,570
Och så, i denna mening, vi behöver inte
att slösa onödig minnet eftersom jag

456
00:23:56,570 --> 00:24:00,850
om jag inte vet hur många värden som jag vill
att lagra, gör det inte meningsfullt för mig

457
00:24:00,850 --> 00:24:04,310
att skapa en array eftersom
om jag vill lagra 10 värden

458
00:24:04,310 --> 00:24:08,380
och jag skapa en array av 1000, det är
en hel del bortkastade minne, tilldelas.

459
00:24:08,380 --> 00:24:11,180
Det är därför vi vill använda en länkad
Listan för att kunna dynamiskt

460
00:24:11,180 --> 00:24:13,860
ändra eller krympa vår storlek.

461
00:24:13,860 --> 00:24:17,040
>> Och så det gör insättning
lite mer komplicerat.

462
00:24:17,040 --> 00:24:20,810
Eftersom vi inte slumpmässigt kan komma åt element
det sätt som vi skulle i en array.

463
00:24:20,810 --> 00:24:24,270
Om jag vill infoga ett element
in i den sjunde index,

464
00:24:24,270 --> 00:24:26,930
Jag kan bara infoga det
in i den sjunde indexet.

465
00:24:26,930 --> 00:24:30,020
På en länkad lista, gör det inte
helt fungerar lika enkelt,

466
00:24:30,020 --> 00:24:34,947
och så om vi ville infoga
den en här i den länkade listan,

467
00:24:34,947 --> 00:24:36,280
visuellt, är det mycket lätt att se.

468
00:24:36,280 --> 00:24:39,363
Vi vill bara att sätta den där,
precis i början av listan,

469
00:24:39,363 --> 00:24:40,840
direkt efter huvudet.

470
00:24:40,840 --> 00:24:44,579
>> Men det sätt på vilket vi måste överlåta
pekarna är lite invecklad

471
00:24:44,579 --> 00:24:47,620
eller logiskt, är det vettigt, men
du vill vara säker på att du har det

472
00:24:47,620 --> 00:24:50,250
helt ner på grund
det sista du vill

473
00:24:50,250 --> 00:24:52,990
är att tilldela en pekar
sätt som vi gör här.

474
00:24:52,990 --> 00:24:58,170
Om du dereference den
pekaren från topp till 1

475
00:24:58,170 --> 00:25:01,086
då helt plötsligt
resten av ditt länkad lista

476
00:25:01,086 --> 00:25:04,680
försvinner eftersom du har faktiskt inte
skapas en temporär någonting.

477
00:25:04,680 --> 00:25:06,220
Det är pekade på två.

478
00:25:06,220 --> 00:25:10,080
Om du tilldela pekaren sedan
Resten av listan är helt förlorad.

479
00:25:10,080 --> 00:25:13,310
Så du vill vara
mycket, mycket försiktig här

480
00:25:13,310 --> 00:25:17,010
att först tilldela
pekaren från vad du

481
00:25:17,010 --> 00:25:20,150
vill infoga i varhelst
du vill, och sedan

482
00:25:20,150 --> 00:25:22,710
kan dereference resten av listan.

483
00:25:22,710 --> 00:25:25,250
>> Så detta gäller överallt där
du försöker sätta in.

484
00:25:25,250 --> 00:25:27,520
Om du vill infoga i
huvud, om du vill svara här,

485
00:25:27,520 --> 00:25:29,455
Om du vill infoga
slutet, ja, till slut jag

486
00:25:29,455 --> 00:25:30,910
antar att du skulle bara
har ingen visare, men du

487
00:25:30,910 --> 00:25:33,830
vill se till att du inte
förlorar resten av listan.

488
00:25:33,830 --> 00:25:36,640
Du vill alltid se till att
din nya nod pekar

489
00:25:36,640 --> 00:25:39,330
mot vad du
vill infoga i,

490
00:25:39,330 --> 00:25:42,170
och då kan du lägga till kedja på.

491
00:25:42,170 --> 00:25:43,330
Alla klart?

492
00:25:43,330 --> 00:25:45,427
>> Detta kommer att bli
en av de verkliga frågorna.

493
00:25:45,427 --> 00:25:48,010
En av de mest viktiga frågor
du kommer att ha på din pset

494
00:25:48,010 --> 00:25:51,340
är att du kommer att försöka skapa
en länkad lista och insats saker

495
00:25:51,340 --> 00:25:53,340
men sedan bara förlorar
resten av ditt länkad lista.

496
00:25:53,340 --> 00:25:54,900
Och du kommer att se ut, jag
vet inte varför detta händer?

497
00:25:54,900 --> 00:25:58,040
Och det är jobbigt att gå igenom
och sök alla dina tips.

498
00:25:58,040 --> 00:26:02,100
>> Och jag garanterar dig på denna pset,
skriva och rita dessa noder ut

499
00:26:02,100 --> 00:26:03,344
kommer att vara mycket, mycket bra.

500
00:26:03,344 --> 00:26:06,010
Så du kan helt hålla koll
av där alla dina pekare är

501
00:26:06,010 --> 00:26:08,540
vad går fel,
där alla dina noder är

502
00:26:08,540 --> 00:26:12,660
vad du behöver göra för att få åtkomst till eller
infoga eller ta bort eller någon av dem.

503
00:26:12,660 --> 00:26:14,550
Alla bra med det?

504
00:26:14,550 --> 00:26:15,050
Häftigt.

505
00:26:15,050 --> 00:26:19,300

506
00:26:19,300 --> 00:26:22,600
>> Så om vi ville titta på koden?

507
00:26:22,600 --> 00:26:24,470
Åh, jag vet inte om vi
kan se the-- OK, så

508
00:26:24,470 --> 00:26:27,940
på toppen allt är är en funktion
namngav insats där vi vill

509
00:26:27,940 --> 00:26:31,365
att sätta int n i den länkade listan.

510
00:26:31,365 --> 00:26:32,740
Vi kommer att gå igenom detta.

511
00:26:32,740 --> 00:26:34,770
Det är en hel del kod, en hel del ny syntax.

512
00:26:34,770 --> 00:26:36,220
Vi ska vara OK.

513
00:26:36,220 --> 00:26:39,120
>> Så upp på toppen, när
Vi vill skapa något

514
00:26:39,120 --> 00:26:42,380
Vad behöver vi göra, särskilt om du
vill att det ska inte lagras på stacken

515
00:26:42,380 --> 00:26:43,920
men i högen?

516
00:26:43,920 --> 00:26:45,460
Vi går till en malloc, eller hur?

517
00:26:45,460 --> 00:26:48,240
Så vi kommer att skapa en pekare.

518
00:26:48,240 --> 00:26:52,074
Nod, pekare, nya jämlikar
malloc storleken på en nod

519
00:26:52,074 --> 00:26:53,740
eftersom vi vill att noden ska skapas.

520
00:26:53,740 --> 00:26:56,720
Vi vill mängden
minne som en nod tar upp

521
00:26:56,720 --> 00:26:59,300
tilldelas för
Inrättandet av den nya noden.

522
00:26:59,300 --> 00:27:02,270
>> Och sedan ska vi kontrollera
se om nya jämlikar är lika med noll.

523
00:27:02,270 --> 00:27:03,370
Kom ihåg vad vi sa?

524
00:27:03,370 --> 00:27:06,470
Vad du malloc,
Vad måste du alltid göra?

525
00:27:06,470 --> 00:27:09,490
Du måste alltid kontrollera att se
oavsett om det är null.

526
00:27:09,490 --> 00:27:13,620
>> Till exempel, om ditt operativsystem
Systemet var helt fullt,

527
00:27:13,620 --> 00:27:17,060
om du hade ingen mer minne på
alla och du försöker malloc,

528
00:27:17,060 --> 00:27:18,410
det skulle återvända null för dig.

529
00:27:18,410 --> 00:27:21,094
Och så om du försöker använda det
när det pekar på noll,

530
00:27:21,094 --> 00:27:23,260
du inte kommer att kunna
att få tillgång till denna information.

531
00:27:23,260 --> 00:27:27,010
Och så som sådan, vi ville göra
Se till att när du mallocing,

532
00:27:27,010 --> 00:27:30,500
du alltid kontrollera att se om
att minnet du fått är null.

533
00:27:30,500 --> 00:27:33,670
Och om det inte är, då kan vi flytta
på med resten av vår kod.

534
00:27:33,670 --> 00:27:36,140
>> Så vi kommer att
initiera nya noden.

535
00:27:36,140 --> 00:27:39,050
Vi kommer att göra ett nytt n är lika med n.

536
00:27:39,050 --> 00:27:42,390
Och sedan ska vi göra
sätta nya pekaren på nya

537
00:27:42,390 --> 00:27:46,900
till null eftersom just nu gör vi inte
ha något för det att peka på.

538
00:27:46,900 --> 00:27:48,755
Vi har ingen aning om
det kommer att sätta dig,

539
00:27:48,755 --> 00:27:50,630
och sedan om vi vill
infoga det i huvudet,

540
00:27:50,630 --> 00:27:53,820
då kan vi omtilldela
pekaren till huvudet.

541
00:27:53,820 --> 00:27:58,530
Har alla följa logiken
var som händer?

542
00:27:58,530 --> 00:28:02,502
>> Allt vi gör är att skapa en ny
nod, ställa pekaren till noll,

543
00:28:02,502 --> 00:28:04,210
och sedan omfördelning
den till huvudet om vi

544
00:28:04,210 --> 00:28:06,320
vet att vi vill infoga det i spetsen.

545
00:28:06,320 --> 00:28:09,420
Och sedan huvudet kommer att
pekar mot den nya noden.

546
00:28:09,420 --> 00:28:11,060
Alla OK med det?

547
00:28:11,060 --> 00:28:12,380
>> Så det är en tvåstegsprocess.

548
00:28:12,380 --> 00:28:14,760
You got att först tilldela
vad du skapar.

549
00:28:14,760 --> 00:28:18,260
Ställ som pekare till
referens, och sedan

550
00:28:18,260 --> 00:28:21,400
kan typ av dereference
den första pekaren

551
00:28:21,400 --> 00:28:22,972
och rikta den mot den nya noden.

552
00:28:22,972 --> 00:28:25,680
Vart du vill infoga det,
denna logik kommer att hålla sant.

553
00:28:25,680 --> 00:28:27,530
>> Det är ungefär som att tilldela
temporära variabler.

554
00:28:27,530 --> 00:28:28,700
Kom ihåg att du har fått
att se till att du

555
00:28:28,700 --> 00:28:30,346
inte förlora reda på om du byter.

556
00:28:30,346 --> 00:28:33,470
Du vill vara säker på att du har en
temporär variabel den sortens håller

557
00:28:33,470 --> 00:28:35,620
reda på var det där
lagras så att du

558
00:28:35,620 --> 00:28:41,190
inte förlorar något värde i samband
som att leka med den.

559
00:28:41,190 --> 00:28:42,710
>> OK, så koden kommer att vara här.

560
00:28:42,710 --> 00:28:45,020
Ni tar en titt efter avsnitt.

561
00:28:45,020 --> 00:28:48,060
Det kommer att vara där.

562
00:28:48,060 --> 00:28:50,280
>> Så jag gissa hur gör
Detta skiljer sig om vi ville

563
00:28:50,280 --> 00:28:52,300
att infoga i mitten eller slutet?

564
00:28:52,300 --> 00:28:57,892
Finns det någon som har en idé om vad som är
pseudokod som den logiska referens

565
00:28:57,892 --> 00:29:00,350
att vi skulle ta om vi ville
att infoga den i mitten?

566
00:29:00,350 --> 00:29:03,391
Så om vi ville sätta in den på
huvud, är allt vi gör skapa en ny nod.

567
00:29:03,391 --> 00:29:06,311
Vi sätter pekaren i nämnda
ny nod till oavsett huvudet,

568
00:29:06,311 --> 00:29:08,310
och sedan vi satt huvudet
till den nya noden, eller hur?

569
00:29:08,310 --> 00:29:11,560
Om vi ​​ville sätta in den i mitten
av listan, vad skulle vi göra?

570
00:29:11,560 --> 00:29:14,108

571
00:29:14,108 --> 00:29:16,110
>> PUBLIK: Det skulle fortfarande
vara en liknande process

572
00:29:16,110 --> 00:29:19,114
som att tilldela pekaren och
sedan tilldela den pekare,

573
00:29:19,114 --> 00:29:20,530
men vi skulle behöva hitta där.

574
00:29:20,530 --> 00:29:23,560
>> ANDI PENG: Just det, så exakt
samma process förutom att du

575
00:29:23,560 --> 00:29:27,820
måste hitta exakt var du
vill den nya pekaren att gå in,

576
00:29:27,820 --> 00:29:44,790
så om jag vill infoga i
mitten av länkade list-- OK,

577
00:29:44,790 --> 00:29:46,370
låt oss säga att det är vår länkad lista.

578
00:29:46,370 --> 00:29:49,500
Om vi ​​vill infoga det här,
Vi ska skapa en ny nod.

579
00:29:49,500 --> 00:29:50,520
Vi kommer att malloc.

580
00:29:50,520 --> 00:29:52,220
Vi kommer att skapa en ny nod.

581
00:29:52,220 --> 00:29:55,940
Vi kommer att tilldela
pekare av denna nod här.

582
00:29:55,940 --> 00:29:58,335
>> Men problemet som skiljer
från där huvudet är

583
00:29:58,335 --> 00:30:00,490
är att vi visste exakt
där huvudet är.

584
00:30:00,490 --> 00:30:01,930
Det var rätt vid första, eller hur?

585
00:30:01,930 --> 00:30:04,870
Men här har vi att hålla koll
var vi sätter in det i.

586
00:30:04,870 --> 00:30:07,930
Om vi ​​sätter vår
nod här, har vi

587
00:30:07,930 --> 00:30:12,270
att se till att
en tidigare till denna nod

588
00:30:12,270 --> 00:30:14,172
är en som återtilldelar pekaren.

589
00:30:14,172 --> 00:30:16,380
Så då måste man typ av
hålla reda på två saker.

590
00:30:16,380 --> 00:30:19,420
Om du hålla reda på var detta
nod för närvarande att sätta in i.

591
00:30:19,420 --> 00:30:23,280
Du måste också hålla reda på var
föregående nod som du tittar på

592
00:30:23,280 --> 00:30:24,340
var också där.

593
00:30:24,340 --> 00:30:25,830
Alla bra med det?

594
00:30:25,830 --> 00:30:26,500
OK.

595
00:30:26,500 --> 00:30:28,000
>> Vad sägs om att sätta in i slutet?

596
00:30:28,000 --> 00:30:34,220
Om jag ville lägga till den här-- om jag ville
att lägga till en ny nod i slutet av en lista,

597
00:30:34,220 --> 00:30:37,009
Hur kan jag gå om att göra det?

598
00:30:37,009 --> 00:30:39,300
PUBLIK: Så för närvarande, den
förra ens pekade på null.

599
00:30:39,300 --> 00:30:40,960
ANDI PENG: Ja.

600
00:30:40,960 --> 00:30:43,560
Exakt så här
närvarande pekas att veta,

601
00:30:43,560 --> 00:30:46,720
och så jag antar att, i denna mening, är det
mycket lätt att lägga till i slutet av en lista.

602
00:30:46,720 --> 00:30:51,810
Allt du behöver göra är att ställa det
lika med noll och sedan boom.

603
00:30:51,810 --> 00:30:53,070
Just där, mycket lätt.

604
00:30:53,070 --> 00:30:53,960
Väldigt enkelt.

605
00:30:53,960 --> 00:30:56,430
>> Mycket lik den
huvudet, men logiskt du

606
00:30:56,430 --> 00:30:59,690
vill se till att stegen
du tar mot att göra något av detta,

607
00:30:59,690 --> 00:31:01,500
du följer med.

608
00:31:01,500 --> 00:31:04,420
Det är väldigt lätt att, i mitten
av din kod, fastna på,

609
00:31:04,420 --> 00:31:05,671
åh, jag har fått så många pekare.

610
00:31:05,671 --> 00:31:07,461
Jag vet inte var
något pekar på.

611
00:31:07,461 --> 00:31:09,170
Jag vet inte ens vilken nod jag är på.

612
00:31:09,170 --> 00:31:11,490
Vad händer?

613
00:31:11,490 --> 00:31:13,620
>> Slappna av, lugna ner, ta ett djupt andetag.

614
00:31:13,620 --> 00:31:15,530
Dra ut din länkad lista.

615
00:31:15,530 --> 00:31:18,800
Om du säger, jag vet var exakt
Jag måste sätta in detta i

616
00:31:18,800 --> 00:31:22,970
och jag vet exakt hur man ska överlåta min
pekare, mycket, mycket lättare att föreställa

617
00:31:22,970 --> 00:31:27,200
out-- mycket, mycket lättare att inte
vilse i buggar i koden.

618
00:31:27,200 --> 00:31:29,410
Alla OK med det?

619
00:31:29,410 --> 00:31:31,380
OK.

620
00:31:31,380 --> 00:31:35,120
>> Så jag antar att ett koncept som vi inte har
verkligen talade om förrän nu,

621
00:31:35,120 --> 00:31:38,131
och jag antar att du förmodligen
kommer inte att stöta mycket yet--

622
00:31:38,131 --> 00:31:40,880
det är typ av en avancerad concept--
är att vi faktiskt har en data

623
00:31:40,880 --> 00:31:43,900
struktur som kallas en dubbellänkad lista.

624
00:31:43,900 --> 00:31:46,390
Så när ni kan se,
allt vi gör är att skapa

625
00:31:46,390 --> 00:31:50,400
ett ärvärde, en extra
pekaren på vart och ett av våra noder

626
00:31:50,400 --> 00:31:52,660
som pekar också på den tidigare nod.

627
00:31:52,660 --> 00:31:58,170
Så inte nog med att vi har vår
noder pekar på nästa.

628
00:31:58,170 --> 00:32:01,430
De pekar också på tidigare.

629
00:32:01,430 --> 00:32:04,310
Jag kommer att ignorera dessa två just nu.

630
00:32:04,310 --> 00:32:06,740
>> Så då har du en kedja
som kan flytta åt båda hållen,

631
00:32:06,740 --> 00:32:09,630
och då är det lite lättare
logiskt följa.

632
00:32:09,630 --> 00:32:11,896
Som här, i stället för
hålla reda på, åh, jag

633
00:32:11,896 --> 00:32:14,520
måste veta att denna nod är
den som jag måste överlåta,

634
00:32:14,520 --> 00:32:17,532
Jag kan bara gå hit och
bara dra den föregående.

635
00:32:17,532 --> 00:32:19,490
Då vet jag exakt var
det vill säga, och sedan

636
00:32:19,490 --> 00:32:21,130
behöver inte korsa
helheten av den länkade listan.

637
00:32:21,130 --> 00:32:22,180
Det är lite lättare.

638
00:32:22,180 --> 00:32:24,960
>> Men som sådan, har du dubbelt
mängden av pekare,

639
00:32:24,960 --> 00:32:26,960
det är dubbelt så mycket minne.

640
00:32:26,960 --> 00:32:28,950
Det är en hel del tips för att hålla reda på.

641
00:32:28,950 --> 00:32:32,140
Det är lite mer komplicerat, men det är
lite mer användarvänlig beroende

642
00:32:32,140 --> 00:32:34,080
på vad du försöker åstadkomma.

643
00:32:34,080 --> 00:32:36,910
>> Så denna typ av data
struktur finns totalt,

644
00:32:36,910 --> 00:32:40,280
och strukturen för är mycket, mycket
enkel utom allt du har är,

645
00:32:40,280 --> 00:32:43,850
i stället för bara en pekare till nästa,
Du har också en pekare till tidigare.

646
00:32:43,850 --> 00:32:45,940
Det är hela skillnaden var.

647
00:32:45,940 --> 00:32:47,740
Alla bra med det?

648
00:32:47,740 --> 00:32:48,240
Häftigt.

649
00:32:48,240 --> 00:32:50,940

650
00:32:50,940 --> 00:32:53,280
>> Okej, så nu är jag
att verkligen spendera förmodligen

651
00:32:53,280 --> 00:32:56,870
som 15 till 20 minuter eller huvuddelen
resten av tiden i avsnittet

652
00:32:56,870 --> 00:32:58,360
talar om hashtabeller.

653
00:32:58,360 --> 00:33:02,590
Hur många av er
har läst pset5 spec?

654
00:33:02,590 --> 00:33:03,620
Okej, bra.

655
00:33:03,620 --> 00:33:06,160
Det är högre än 50% av normalt.

656
00:33:06,160 --> 00:33:07,560
Det är ok.

657
00:33:07,560 --> 00:33:10,345
>> Så när ni kommer att se,
du utmaningen i pset5

658
00:33:10,345 --> 00:33:16,790
kommer att vara att genomföra en ordbok
där du laddar över 140.000 ord

659
00:33:16,790 --> 00:33:20,610
att vi ger dig och stavningskontroll
det mot all text.

660
00:33:20,610 --> 00:33:22,580
Vi ger dig slumpmässig
bitar av litteratur.

661
00:33:22,580 --> 00:33:23,520
Vi ger dig Odyssey.

662
00:33:23,520 --> 00:33:24,561
Vi ger dig Iliaden.

663
00:33:24,561 --> 00:33:26,350
Vi ger dig Austin Powers.

664
00:33:26,350 --> 00:33:28,220
>> Och din utmaning
kommer att vara att stavningskontroll

665
00:33:28,220 --> 00:33:31,760
varje ord i alla
av dessa ordböcker

666
00:33:31,760 --> 00:33:34,960
i huvudsak med vårt stavningskontroll.

667
00:33:34,960 --> 00:33:38,620
Och så finns det några delar
att skapa denna pset,

668
00:33:38,620 --> 00:33:41,970
först du vill vara
kan faktiskt läsa

669
00:33:41,970 --> 00:33:43,970
alla orden i din
ordbok, och sedan

670
00:33:43,970 --> 00:33:45,530
vill kunna
stavningskontroll dem alla.

671
00:33:45,530 --> 00:33:48,780
Och så som sådan, du kommer att kräva
en datastruktur som kan göra detta snabbt

672
00:33:48,780 --> 00:33:50,790
och effektivt och dynamiskt.

673
00:33:50,790 --> 00:33:52,900
>> Så jag antar att det enklaste
sätt att göra detta, du

674
00:33:52,900 --> 00:33:55,010
skulle förmodligen skapa en array, eller hur?

675
00:33:55,010 --> 00:33:58,910
Det enklaste sättet att lagring är du
kan skapa en rad 140.000 ord

676
00:33:58,910 --> 00:34:03,400
och bara placera dem alla där och
sedan korsa dem med binär sökning

677
00:34:03,400 --> 00:34:06,780
eller genom val eller inte--
ledsen som är sortering.

678
00:34:06,780 --> 00:34:10,729
Du kan sortera dem och sedan passera dem
genom binär sökning eller bara linjär sökning

679
00:34:10,729 --> 00:34:13,730
och bara sista orden, men att
tar en stor mängd minne,

680
00:34:13,730 --> 00:34:15,190
och det är inte mycket effektiv.

681
00:34:15,190 --> 00:34:18,350
>> Och så vi ska börja
talar om sätt att göra

682
00:34:18,350 --> 00:34:20,110
vår gångtid mer effektiv.

683
00:34:20,110 --> 00:34:23,190
Och vårt mål är att få
konstant tid där

684
00:34:23,190 --> 00:34:25,810
det är nästan som matriser, där
du har omedelbar tillgång till.

685
00:34:25,810 --> 00:34:28,560
Om jag ville söka efter något,
Jag vill kunna bara,

686
00:34:28,560 --> 00:34:30,810
boom, tycker att det är exakt, och dra ut den.

687
00:34:30,810 --> 00:34:34,100
Och så en struktur i vilken
vi kommer att bli mycket nära

688
00:34:34,100 --> 00:34:37,569
för att kunna få tillgång till konstant
tid, denna heliga graal

689
00:34:37,569 --> 00:34:41,370
i programmering av konstant
tid kallas en hashtabell.

690
00:34:41,370 --> 00:34:45,370
Och så David tidigare nämnts
[OHÖRBAR] lite i föredrag,

691
00:34:45,370 --> 00:34:49,100
men vi ska verkligen
dyka i djup den här veckan

692
00:34:49,100 --> 00:34:51,780
på en bit som är i fråga
hur en hashtabell fungerar.

693
00:34:51,780 --> 00:34:53,949
>> Så det sätt som en hash
bords verk, till exempel,

694
00:34:53,949 --> 00:35:00,230
om jag ville att lagra en massa ord, en
gäng ord i det engelska språket,

695
00:35:00,230 --> 00:35:02,940
Jag kunde teoretiskt sätta
banan, äpple, kiwi, mango, par,

696
00:35:02,940 --> 00:35:04,980
och cantaloupemelon allt på bara en array.

697
00:35:04,980 --> 00:35:07,044
De kunde alla passa in och bli hitta.

698
00:35:07,044 --> 00:35:09,210
Det skulle vara typ av en smärta att
söka igenom och tillgång,

699
00:35:09,210 --> 00:35:12,920
men det enklare sätt att göra detta är
att vi kan skapa faktiskt en struktur

700
00:35:12,920 --> 00:35:15,680
kallas en hashtabell där vi hash.

701
00:35:15,680 --> 00:35:19,880
Vi driver alla våra nycklar genom
en hashfunktion, en ekvation,

702
00:35:19,880 --> 00:35:22,600
som förvandlar dem alla i
någon form av ett värde

703
00:35:22,600 --> 00:35:28,740
som sedan kan vi lagrar på
huvudsak ett arrangemang av länkad lista.

704
00:35:28,740 --> 00:35:32,570
>> Och så här, om vi ville
att lagra engelska ord,

705
00:35:32,570 --> 00:35:37,250
vi kunde potentiellt bara, det gör jag inte
vet, slå alla de första bokstäverna

706
00:35:37,250 --> 00:35:39,630
in någon form av en siffra.

707
00:35:39,630 --> 00:35:43,140
Och så, till exempel, om jag ville
En vara synonymt med apple--

708
00:35:43,140 --> 00:35:47,460
eller med index på 0, och
B att vara synonymt med ett,

709
00:35:47,460 --> 00:35:51,030
vi kan ha 26 poster
som bara kan lagra

710
00:35:51,030 --> 00:35:53,610
alla bokstäver i
alfabet som vi ska börja med.

711
00:35:53,610 --> 00:35:56,130
Och då kan vi ha
äpple på index 0.

712
00:35:56,130 --> 00:35:59,160
Vi kan ha banan vid index
1, cantaloupemelon vid index 2,

713
00:35:59,160 --> 00:36:00,540
och så vidare och så vidare.

714
00:36:00,540 --> 00:36:04,460
Och så om jag ville söka
min hash bord och tillgång äpple,

715
00:36:04,460 --> 00:36:07,560
Jag vet att äpple börjar med
ett A, och jag vet exakt

716
00:36:07,560 --> 00:36:10,860
att det måste vara och hash
bord på index 0 eftersom

717
00:36:10,860 --> 00:36:13,620
av funktionen tidigare tilldelats.

718
00:36:13,620 --> 00:36:16,572
>> Så jag vet inte, vi är
en användare där programmet

719
00:36:16,572 --> 00:36:18,780
du kommer att debiteras med
arbitrarily-- inte godtyckligt,

720
00:36:18,780 --> 00:36:22,530
med att försöka tänk
tänker på goda ekvationer

721
00:36:22,530 --> 00:36:25,460
för att kunna sprida
ut alla dina värderingar

722
00:36:25,460 --> 00:36:29,370
på ett sätt som de lätt kan få tillgång till
den senare med som en ekvation

723
00:36:29,370 --> 00:36:31,130
att du själv vet.

724
00:36:31,130 --> 00:36:35,210
Så i den meningen om jag ville gå till
mango, jag vet, åh, det börjar med m.

725
00:36:35,210 --> 00:36:37,134
Det måste vara indexet för 12.

726
00:36:37,134 --> 00:36:38,800
Jag behöver inte söka igenom någonting.

727
00:36:38,800 --> 00:36:42,080
Jag vet exactly-- jag kunde bara gå till
index 12 och dra ut det.

728
00:36:42,080 --> 00:36:45,520
>> Alla tydlig på hur en
hashtabell funktion fungerar?

729
00:36:45,520 --> 00:36:48,380
Det är typ av bara en mer komplex uppsättning.

730
00:36:48,380 --> 00:36:50,010
Det är allt det är.

731
00:36:50,010 --> 00:36:51,630
OK.

732
00:36:51,630 --> 00:36:57,690
>> Så jag antar att vi stöter på
det här numret av vad

733
00:36:57,690 --> 00:37:06,390
händer om du har flera saker
som ger dig samma index?

734
00:37:06,390 --> 00:37:10,570
Så säger vår funktion, allt
gjorde var att ta den första bokstaven

735
00:37:10,570 --> 00:37:14,490
och förvandla det till en
respektive 0 till 25 index.

736
00:37:14,490 --> 00:37:17,137
Det är helt bra om
du har bara en av varje.

737
00:37:17,137 --> 00:37:18,970
Men den andra du börjar
med mer, du är

738
00:37:18,970 --> 00:37:20,910
kommer att ha vad som kallas en kollision.

739
00:37:20,910 --> 00:37:25,580
>> Så om jag försöker att infoga begrava i en hash
tabell som redan har banan på det,

740
00:37:25,580 --> 00:37:27,870
vad som kommer att hända när
du försöker infoga det?

741
00:37:27,870 --> 00:37:30,930
Dåliga saker eftersom banan
redan finns inom indexet

742
00:37:30,930 --> 00:37:33,800
som du vill lagra den i.

743
00:37:33,800 --> 00:37:35,560
Berry typ av ser ut, ah, vad ska jag göra?

744
00:37:35,560 --> 00:37:37,080
Jag vet inte vart de ska gå.

745
00:37:37,080 --> 00:37:38,410
Hur löser jag detta?

746
00:37:38,410 --> 00:37:41,150
>> Och så ni kommer slags
ser vi gör detta knepig sak

747
00:37:41,150 --> 00:37:44,810
där vi kan slags faktiskt
skapa länkad lista i våra matriser.

748
00:37:44,810 --> 00:37:46,840
Och så det enklaste sättet
att tänka på detta,

749
00:37:46,840 --> 00:37:50,830
alla hash-tabell är en
matris med länkade listor.

750
00:37:50,830 --> 00:37:55,670
Och så, i den meningen, har du
denna vackra samling av pekare,

751
00:37:55,670 --> 00:37:58,740
och därefter varje pekare i
detta värde, i detta index,

752
00:37:58,740 --> 00:38:00,740
kan faktiskt peka på andra saker.

753
00:38:00,740 --> 00:38:05,720
Och så du har alla dessa separat
kedjor som kommer bort av en stor samling.

754
00:38:05,720 --> 00:38:07,960
>> Och så här, om jag
ville infoga bär,

755
00:38:07,960 --> 00:38:11,220
Jag vet, OK, jag ska mata
det genom min hashfunktion.

756
00:38:11,220 --> 00:38:15,070
Jag ska sluta med index
1, och sedan kommer jag att kunna ha

757
00:38:15,070 --> 00:38:20,410
bara en mindre undergrupp av denna
jätte 140.000 ord ordbok.

758
00:38:20,410 --> 00:38:24,220
Och då kan jag bara titta
genom 1/26 av det.

759
00:38:24,220 --> 00:38:27,910
>> Och så då kan jag bara in
bär antingen före eller efter banan

760
00:38:27,910 --> 00:38:28,820
I det här fallet?

761
00:38:28,820 --> 00:38:29,700
Efter, eller hur?

762
00:38:29,700 --> 00:38:33,920
Och så att du kommer att vilja
infoga denna nod efter banan,

763
00:38:33,920 --> 00:38:36,667
och så du kommer att infoga
i svansen av den länkad lista.

764
00:38:36,667 --> 00:38:38,500
Jag kommer att gå tillbaka
denna föregående bild,

765
00:38:38,500 --> 00:38:40,680
så ni kan se hur
hash funktionen fungerar.

766
00:38:40,680 --> 00:38:43,980
>> Så hashfunktion är denna ekvation
att du kör typ av din input

767
00:38:43,980 --> 00:38:46,940
genom att få vad index
du vill tilldela den mot.

768
00:38:46,940 --> 00:38:51,130
Och så, i detta exempel, allt vi ville
att göra var att ta den första bokstaven,

769
00:38:51,130 --> 00:38:55,890
förvandla det till ett index, då vi
kan lagra den i vår hash funktion.

770
00:38:55,890 --> 00:39:00,160
Allt vi gör här är att vi är
omvandling av den första bokstaven.

771
00:39:00,160 --> 00:39:04,770
Så keykey [0] är bara den första bokstaven
oavsett sträng vi har,

772
00:39:04,770 --> 00:39:05,720
vi passerar.

773
00:39:05,720 --> 00:39:09,740
Vi omvandla denna till övre och
vi subtrahera med versaler A,

774
00:39:09,740 --> 00:39:11,740
så allt som gör
ger oss ett antal

775
00:39:11,740 --> 00:39:13,670
där kan vi hash våra värderingar på.

776
00:39:13,670 --> 00:39:16,550
>> Och sedan ska vi
retur hash modul STORLEK.

777
00:39:16,550 --> 00:39:19,340
Var mycket, mycket försiktig
eftersom, teoretiskt, här

778
00:39:19,340 --> 00:39:21,870
din hash-värde kan vara oändlig.

779
00:39:21,870 --> 00:39:23,660
Det kunde bara gå på och så vidare.

780
00:39:23,660 --> 00:39:26,080
Det kan vara några riktigt,
riktigt stora värde,

781
00:39:26,080 --> 00:39:29,849
men eftersom din hash tabell som
du har skapat bara har 26 index,

782
00:39:29,849 --> 00:39:31,890
du vill se till att din
modulusing så att du

783
00:39:31,890 --> 00:39:33,848
inte run-- det är samma
sak som din queue--

784
00:39:33,848 --> 00:39:36,320
så att du inte kör bort
undersidan av hashfunktion.

785
00:39:36,320 --> 00:39:39,210
>> Du vill linda den tillbaka runt
på samma sätt i [OHÖRBAR] när

786
00:39:39,210 --> 00:39:41,750
du hade som en mycket,
mycket stor bokstav, du

787
00:39:41,750 --> 00:39:43,740
ville inte det till
bara köra utanför slutet.

788
00:39:43,740 --> 00:39:46,948
Samma sak här, vill du se till att
det går inte ut i slutet genom att linda

789
00:39:46,948 --> 00:39:48,330
runt till början av tabellen.

790
00:39:48,330 --> 00:39:50,530
Så det här är bara en mycket
enkel hashfunktionen.

791
00:39:50,530 --> 00:39:56,570
Allt som gjorde var att ta den första
skrivelse av vad vår insats var

792
00:39:56,570 --> 00:40:01,660
och förvandla det till ett index som
vi kunde sätta i våra hash bord.

793
00:40:01,660 --> 00:40:05,450
>> Ja, och så som jag sade tidigare,
det sätt som vi löser kollisioner

794
00:40:05,450 --> 00:40:09,330
i vår hash tabeller har,
vad vi kallar, kedja.

795
00:40:09,330 --> 00:40:13,860
Så om du försöker infoga flera
ord som börjar med samma sak,

796
00:40:13,860 --> 00:40:16,145
du kommer att ha ett hash-värde.

797
00:40:16,145 --> 00:40:18,770
Avokado och äpple, om du har
köra det genom vår hashfunktion,

798
00:40:18,770 --> 00:40:21,450
kommer att ge dig
samma nummer, antalet 0.

799
00:40:21,450 --> 00:40:24,550
Och så sätt att lösa detta är
att vi faktiskt ganska kan länka dem

800
00:40:24,550 --> 00:40:27,010
varandra via länkade listor.

801
00:40:27,010 --> 00:40:29,600
>> Och så i denna mening,
ni kan se snäll

802
00:40:29,600 --> 00:40:32,640
av hur datastrukturer som
vi har inställningen tidigare

803
00:40:32,640 --> 00:40:35,870
som ett russin länkad lista slag
av kan komma ihop till en.

804
00:40:35,870 --> 00:40:38,860
Och då kan du skapa långt
effektivare datastrukturer

805
00:40:38,860 --> 00:40:43,350
som kan hantera större mängder
uppgifter, som dynamiskt ändra storlek beroende

806
00:40:43,350 --> 00:40:44,870
på dina behov.

807
00:40:44,870 --> 00:40:45,620
Alla klart?

808
00:40:45,620 --> 00:40:47,580
Alla slags klar
om vad som händer här?

809
00:40:47,580 --> 00:40:52,110
>> Om jag ville insert-- vad är en
frukt som börjar med, jag vet inte,

810
00:40:52,110 --> 00:40:54,726
B, annat än bär, banan.

811
00:40:54,726 --> 00:40:55,710
>> PUBLIK: Blackberry.

812
00:40:55,710 --> 00:40:57,910
>> ANDI PENG: Blackberry, björnbär.

813
00:40:57,910 --> 00:41:00,530
Vart tar björnbär gå hit?

814
00:41:00,530 --> 00:41:04,251
Tja, vi faktiskt inte har rett
detta ännu, men teoretiskt

815
00:41:04,251 --> 00:41:06,250
om vi ville ha detta
i alfabetisk ordning,

816
00:41:06,250 --> 00:41:07,944
där ska björnbär gå?

817
00:41:07,944 --> 00:41:09,210
>> PUBLIK: [OHÖRBAR]

818
00:41:09,210 --> 00:41:11,100
>> ANDI PENG: Exakt, efter här, eller hur?

819
00:41:11,100 --> 00:41:14,950
Men eftersom det är mycket svårt att
reorder-- Jag antar att det är upp till er.

820
00:41:14,950 --> 00:41:17,920
Ni kan helt
genomföra vad du vill.

821
00:41:17,920 --> 00:41:20,730
Ju mer effektivt sätt
att göra detta kanske

822
00:41:20,730 --> 00:41:24,570
skulle vara att sortera dina länkade
lista i alfabetisk ordning,

823
00:41:24,570 --> 00:41:26,520
och så när du är
infoga saker, du vill

824
00:41:26,520 --> 00:41:28,632
vara säker på att infoga dem
i alfabetisk ordning

825
00:41:28,632 --> 00:41:30,590
så att då när du är
försöker söka dem,

826
00:41:30,590 --> 00:41:32,410
du behöver inte korsa allt.

827
00:41:32,410 --> 00:41:35,290
Du vet exakt var
det är, och det är lättare.

828
00:41:35,290 --> 00:41:39,100
>> Men om du typ av har
saker varvas slumpmässigt,

829
00:41:39,100 --> 00:41:41,420
du fortfarande kommer att ha
att korsa det ändå.

830
00:41:41,420 --> 00:41:44,990
Och så om jag ville bara
infoga björnbär här

831
00:41:44,990 --> 00:41:47,470
och jag ville söka efter
det, jag vet, åh, björnbär

832
00:41:47,470 --> 00:41:52,012
måste börja med index 1, så jag
vet omedelbart bara söka på en.

833
00:41:52,012 --> 00:41:53,970
Och då kan jag typ av
korsa den länkade listan

834
00:41:53,970 --> 00:41:56,120
tills jag får till Blackberry,
och then-- ja?

835
00:41:56,120 --> 00:41:59,550
>> PUBLIK: Om du försöker create--
Jag antar att så här är en mycket enkel hash

836
00:41:59,550 --> 00:42:00,050
fungera.

837
00:42:00,050 --> 00:42:02,835
Och om vi ville göra
flera skikt av det liknande,

838
00:42:02,835 --> 00:42:05,870
OK, vi vill separera i
som alla bokstäver

839
00:42:05,870 --> 00:42:09,040
och sedan igen för att ha en annan uppsättning
av alfabetiska bokstäver inom det,

840
00:42:09,040 --> 00:42:11,715
lägger vi som en hash
tabell i en hash-tabell,

841
00:42:11,715 --> 00:42:13,256
eller som en funktion inom en funktion?

842
00:42:13,256 --> 00:42:14,880
Eller är that--

843
00:42:14,880 --> 00:42:17,510
>> ANDI PENG: Så din hash
function-- din hashtabell

844
00:42:17,510 --> 00:42:19,360
kan vara så stor som du vill.

845
00:42:19,360 --> 00:42:21,930
Så i den meningen, jag trodde
det var mycket lätt, mycket

846
00:42:21,930 --> 00:42:25,320
enkelt för mig att bara sortera baserat
på bokstäverna i det första ordet.

847
00:42:25,320 --> 00:42:28,690
Och så finns det bara 26 alternativ.

848
00:42:28,690 --> 00:42:32,650
Jag kan bara få 26 alternativ från
0 till 25, eftersom de endast kan

849
00:42:32,650 --> 00:42:36,510
börja från A till Z. Men om du ville
att lägga till, kanske, mer komplexitet

850
00:42:36,510 --> 00:42:39,260
eller snabbare gångtid till
hashtabell, du absolut

851
00:42:39,260 --> 00:42:40,760
kan göra alla möjliga saker.

852
00:42:40,760 --> 00:42:43,330
Du kan göra din egen
ekvation som ger dig

853
00:42:43,330 --> 00:42:48,000
mer distribution i din
ord, sedan när du söker,

854
00:42:48,000 --> 00:42:49,300
det kommer att bli snabbare.

855
00:42:49,300 --> 00:42:52,100
>> Det är helt upp till er
hur du vill genomföra det.

856
00:42:52,100 --> 00:42:55,140
Tänk på det som bara hinkar.

857
00:42:55,140 --> 00:42:57,376
Om jag ville ha
26 hinkar, jag kommer

858
00:42:57,376 --> 00:42:59,420
att sortera saker i dessa hinkar.

859
00:42:59,420 --> 00:43:02,980
Men jag kommer att ha ett gäng
saker i varje segment,

860
00:43:02,980 --> 00:43:05,890
så om du vill göra det
snabbare och effektivare,

861
00:43:05,890 --> 00:43:07,190
Låt mig få hundra hinkar.

862
00:43:07,190 --> 00:43:09,290
>> Men då måste man räkna ut ett
sätt att sortera saker så att de är

863
00:43:09,290 --> 00:43:11,040
i rätt hinken de bör vara i.

864
00:43:11,040 --> 00:43:13,331
Men sedan när du faktiskt
vill titta på hinken,

865
00:43:13,331 --> 00:43:16,410
det är mycket snabbare eftersom det finns
mindre grejer i varje hink.

866
00:43:16,410 --> 00:43:20,250
Och så, ja, det är faktiskt
tricket för er i pset5

867
00:43:20,250 --> 00:43:22,360
är att du kommer att
utmanas att bara skapa

868
00:43:22,360 --> 00:43:26,170
vad är det mest effektiva
funktionen kan du tänka dig att vara

869
00:43:26,170 --> 00:43:28,520
kunna lagra och kontrollera dessa värden.

870
00:43:28,520 --> 00:43:30,840
>> Helt upp till er
men du vill göra det,

871
00:43:30,840 --> 00:43:32,229
men det är en riktigt bra poäng.

872
00:43:32,229 --> 00:43:34,520
Att den typ av logik du
vill börja tänka på

873
00:43:34,520 --> 00:43:37,236
är, tja, varför inte jag göra fler hinkar.

874
00:43:37,236 --> 00:43:39,527
Och då måste jag söka
mindre saker, och sedan kanske jag

875
00:43:39,527 --> 00:43:41,640
har en annan hash-funktion.

876
00:43:41,640 --> 00:43:45,500
>> Ja, det finns många sätt att göra detta
pset, vissa är snabbare än andra.

877
00:43:45,500 --> 00:43:50,630
Jag är helt kommer att bara se hur
snabb var snabbaste ni kommer

878
00:43:50,630 --> 00:43:55,170
att kunna få dina funktioner ska fungera.

879
00:43:55,170 --> 00:43:58,176
OK, alla bra ut på
CHAI och hashtabeller?

880
00:43:58,176 --> 00:44:00,800
Det är faktiskt som en mycket enkel
koncept om man tänker på det.

881
00:44:00,800 --> 00:44:05,160
Allt som är är att separera vad
ingångarna är i hinkar,

882
00:44:05,160 --> 00:44:10,670
sortera dem, och sedan söka på
listor att det har samband med.

883
00:44:10,670 --> 00:44:11,852
>> Häftigt.

884
00:44:11,852 --> 00:44:18,160
Okej, nu har vi en annan sorts
av datastruktur som kallas ett träd.

885
00:44:18,160 --> 00:44:20,850
Låt oss gå vidare och tala om försök
vilka är helt olika,

886
00:44:20,850 --> 00:44:22,330
men i samma kategori.

887
00:44:22,330 --> 00:44:29,010
I grunden är allt ett träd i stället
organisera data i linjärt sätt

888
00:44:29,010 --> 00:44:32,560
att en hashtabell does-- dig
vet, det har fått en topp och en botten

889
00:44:32,560 --> 00:44:37,900
och sedan slags länka bort av det-- en
träd har en topp som ni kallar roten,

890
00:44:37,900 --> 00:44:40,220
och då har blad runt den.

891
00:44:40,220 --> 00:44:42,390
>> Och så allt du behöver här
är bara toppnoden

892
00:44:42,390 --> 00:44:45,980
som pekar på andra noder, som pekar
till flera noder, och så vidare och så vidare.

893
00:44:45,980 --> 00:44:48,130
Och så har du bara dela upp grenar.

894
00:44:48,130 --> 00:44:53,255
Det är bara ett annat sätt att organisera
uppgifter, och eftersom vi kallar det ett träd,

895
00:44:53,255 --> 00:44:56,270
ni bara-- det är bara
modelleras för att se ut som ett träd.

896
00:44:56,270 --> 00:44:57,670
Det är därför vi kallar det träd.

897
00:44:57,670 --> 00:44:59,370
>> Hashtabell ser ut som en tabell.

898
00:44:59,370 --> 00:45:01,310
Ett träd bara ser ut som ett träd.

899
00:45:01,310 --> 00:45:03,300
Allt som är en separat
sätt att organisera noder

900
00:45:03,300 --> 00:45:06,020
beroende på vilka behov du har.

901
00:45:06,020 --> 00:45:11,810
>> Så du har en rot och
så har du lämnar.

902
00:45:11,810 --> 00:45:15,380
Det sätt som vi kan särskilt
tänker på det är ett binärt träd,

903
00:45:15,380 --> 00:45:18,150
ett binärt träd är bara en
specifik typ av ett träd

904
00:45:18,150 --> 00:45:22,450
där varje nod endast punkter
att, vid max, två andra noder.

905
00:45:22,450 --> 00:45:25,434
Och så här har du distinkt
symmetri i ditt träd

906
00:45:25,434 --> 00:45:28,600
som gör det lättare att typ av ser
på vilka värden du är för då

907
00:45:28,600 --> 00:45:30,150
har alltid en vänster eller höger.

908
00:45:30,150 --> 00:45:33,150
Det finns aldrig som en vänster tredjedel från
vänster eller kvart från vänster.

909
00:45:33,150 --> 00:45:36,358
Det är bara att du har en vänster och en höger
och du kan söka någon av dessa två.

910
00:45:36,358 --> 00:45:38,980
Och så varför är detta bra?

911
00:45:38,980 --> 00:45:40,980
Det sätt som detta är
användbart är om du letar

912
00:45:40,980 --> 00:45:42,890
att söka igenom värderingar, eller hur?

913
00:45:42,890 --> 00:45:45,640
I stället för att genomföra binär
söka i ett fel matris,

914
00:45:45,640 --> 00:45:49,260
om du ville kunna sätta in noder
och ta bort noder på vilja och även

915
00:45:49,260 --> 00:45:52,185
bevara sökning
kapacitet binär sökning.

916
00:45:52,185 --> 00:45:54,560
Så på detta sätt, vi är typ av
tricking-- minns när vi

917
00:45:54,560 --> 00:45:56,530
sade länkade listor kan inte binär sökning?

918
00:45:56,530 --> 00:46:01,700
Vi slags skapar en datastruktur
att tricks som i arbets.

919
00:46:01,700 --> 00:46:05,034
>> Och så på grund länkade listor är linjära,
de länkar bara den ena efter den andra.

920
00:46:05,034 --> 00:46:06,950
Vi kan slags måste
annan typ av pekare

921
00:46:06,950 --> 00:46:09,408
som pekar på olika noder
som kan hjälpa oss med sökning.

922
00:46:09,408 --> 00:46:12,590
Och så här, om jag ville
har ett binärt sökträd,

923
00:46:12,590 --> 00:46:14,090
Jag vet att min mitten om 55.

924
00:46:14,090 --> 00:46:18,280
Jag kommer bara att skapa den
som min mitten, som min rot,

925
00:46:18,280 --> 00:46:20,770
och sedan kommer jag att ha
värden spin off av det.

926
00:46:20,770 --> 00:46:25,610
>> Så här, om jag ska söka efter
värdet 66, kan jag börja vid 55.

927
00:46:25,610 --> 00:46:27,310
Det är 66 större än 55?

928
00:46:27,310 --> 00:46:30,970
Ja det är, så jag vet att jag Mus söka
v rätt pekare av detta träd.

929
00:46:30,970 --> 00:46:32,440
Jag går till 77.

930
00:46:32,440 --> 00:46:35,367
OK, är 66 mindre än eller större än 77?

931
00:46:35,367 --> 00:46:37,950
Det är mindre än, så du vet, åh,
som måste vara den vänstra noden.

932
00:46:37,950 --> 00:46:41,410
>> Och så här vi slags bevara
alla de stora sakerna arrayer,

933
00:46:41,410 --> 00:46:44,420
så som dynamisk storleksändring
av föremål, som

934
00:46:44,420 --> 00:46:49,530
kunna sätta in och ta bort efter behag,
utan att behöva oroa sig för den fasta

935
00:46:49,530 --> 00:46:50,370
mängd utrymme.

936
00:46:50,370 --> 00:46:52,820
Vi bevarar fortfarande alla
dessa underbara saker

937
00:46:52,820 --> 00:46:57,140
samtidigt kunna bevara
log och sök tid av binär sökning

938
00:46:57,140 --> 00:47:00,450
att vi var bara tidigare
kunna få en fras.

939
00:47:00,450 --> 00:47:06,310
>> Cool datastruktur, typ av
komplicerade att genomföra, noden.

940
00:47:06,310 --> 00:47:08,311
Som ni kan se, allt
är struct av noden

941
00:47:08,311 --> 00:47:10,143
är att du har en vänster
och en höger pekare.

942
00:47:10,143 --> 00:47:11,044
Det är allt det är.

943
00:47:11,044 --> 00:47:12,960
Så i stället för att bara
med ett x eller tidigare.

944
00:47:12,960 --> 00:47:15,920
Du har en vänster eller höger, och sedan
du kan slags länka ihop dem

945
00:47:15,920 --> 00:47:16,836
men du så önskar.

946
00:47:16,836 --> 00:47:21,080

947
00:47:21,080 --> 00:47:24,270
>> OK, vi faktiskt kommer
bara ta några minuter.

948
00:47:24,270 --> 00:47:25,790
Så vi kommer att gå tillbaka hit.

949
00:47:25,790 --> 00:47:28,270
Som jag sagt tidigare,
Jag slags förklarade

950
00:47:28,270 --> 00:47:31,520
logiken bakom hur vi
skulle söka igenom detta.

951
00:47:31,520 --> 00:47:33,860
Vi ska försöka
pseudocoding ut det här för att se

952
00:47:33,860 --> 00:47:38,000
om vi slags kan tillämpa
Samma logik binär sökning

953
00:47:38,000 --> 00:47:40,055
till en annan typ av datastruktur.

954
00:47:40,055 --> 00:47:45,049
Om ni vill ta som ett par
minuter att bara tänka på detta.

955
00:47:45,049 --> 00:48:45,927

956
00:48:45,927 --> 00:48:46,925
OK.

957
00:48:46,925 --> 00:48:51,407
Okej, jag ska
faktiskt bara ge er the-- nej,

958
00:48:51,407 --> 00:48:52,990
vi pratar om pseudo först.

959
00:48:52,990 --> 00:48:56,580
Så är det någon som vill
för att ge ett hugg på vad

960
00:48:56,580 --> 00:49:02,100
det första du vill göra när
du börjat söka är?

961
00:49:02,100 --> 00:49:04,460
Om vi ​​letar efter
värdet 66, vad är

962
00:49:04,460 --> 00:49:07,940
det första vi vill göra om
Vi vill binära söka detta träd?

963
00:49:07,940 --> 00:49:10,760
>> PUBLIK: Du vill se höger
och ser till vänster och se [OHÖRBAR]

964
00:49:10,760 --> 00:49:11,230
större antal.

965
00:49:11,230 --> 00:49:12,271
>> ANDI PENG: Ja, exakt.

966
00:49:12,271 --> 00:49:15,350
Så du kommer att titta på din rot.

967
00:49:15,350 --> 00:49:18,180
Det finns massor av sätt du kan ringa
det, dina överordnade nod folk säger.

968
00:49:18,180 --> 00:49:21,317
Jag vilja säga rot eftersom
det är som roten av trädet.

969
00:49:21,317 --> 00:49:23,400
Du kommer att titta på
din rotnod, och du är

970
00:49:23,400 --> 00:49:26,940
kommer att se är 66 större
än eller mindre än 55.

971
00:49:26,940 --> 00:49:30,360
Och om det är större än väl, är det
större än där vi vill se?

972
00:49:30,360 --> 00:49:32,000
Var vill vi söker nu, eller hur?

973
00:49:32,000 --> 00:49:34,340
Vi vill söka
högra halvan av detta träd.

974
00:49:34,340 --> 00:49:38,390
>> Så vi har, enkelt, en
pekare som pekar till höger.

975
00:49:38,390 --> 00:49:44,325
Och så då kan vi ställa
vår nya roten att vara 77.

976
00:49:44,325 --> 00:49:46,450
Vi kan bara gå dit
pekaren pekar.

977
00:49:46,450 --> 00:49:49,100
Tja, åh, här vi börjar
vid 77, och vi kan bara

978
00:49:49,100 --> 00:49:51,172
göra detta rekursivt igen och igen.

979
00:49:51,172 --> 00:49:52,880
På detta sätt, du snäll
av en funktion.

980
00:49:52,880 --> 00:49:57,430
Du har ett sätt att söka som du
kan bara upprepa om och om och om igen,

981
00:49:57,430 --> 00:50:02,720
beroende på var du vill se
tills du så småningom kommer till värdet

982
00:50:02,720 --> 00:50:04,730
att du söker efter.

983
00:50:04,730 --> 00:50:05,230
Vettigt?

984
00:50:05,230 --> 00:50:07,800
>> Jag ska visa dig de faktiska
kod, och det är en hel del kod.

985
00:50:07,800 --> 00:50:08,674
Du behöver inte freak out.

986
00:50:08,674 --> 00:50:09,910
Vi kommer att prata igenom det.

987
00:50:09,910 --> 00:50:13,410

988
00:50:13,410 --> 00:50:14,020
>> Faktiskt nej.

989
00:50:14,020 --> 00:50:15,061
Det var bara pseudokod.

990
00:50:15,061 --> 00:50:17,860
OK, det var bara pseudo,
vilket är lite komplicerat,

991
00:50:17,860 --> 00:50:19,751
men det är helt bra.

992
00:50:19,751 --> 00:50:21,000
Alla följer med här?

993
00:50:21,000 --> 00:50:24,260
Om roten är null, retur
falskt eftersom det innebär

994
00:50:24,260 --> 00:50:26,850
du behöver inte ens har något där.

995
00:50:26,850 --> 00:50:31,376
>> Om root n är värdet, så om det
råkar vara den du tittar på,

996
00:50:31,376 --> 00:50:34,000
då du kommer att återvända sant
eftersom du vet att du hittat den.

997
00:50:34,000 --> 00:50:36,250
Men om värdet är mindre
än roten av n, är du

998
00:50:36,250 --> 00:50:38,332
kommer att söka den vänstra
barn eller vänster blad,

999
00:50:38,332 --> 00:50:39,540
vad du vill kalla det.

1000
00:50:39,540 --> 00:50:41,750
Och om värdet är större än roten,
du kommer att söka rätt trädet,

1001
00:50:41,750 --> 00:50:44,610
sedan bara köra funktionen
genom sökningen igen.

1002
00:50:44,610 --> 00:50:48,037
>> Och om roten är null, att denna
innebär att du har nått slutet?

1003
00:50:48,037 --> 00:50:50,120
Det innebär att du inte har någon
mer mer blad att söka,

1004
00:50:50,120 --> 00:50:52,230
då vet du, åh, jag
antar att det är inte här

1005
00:50:52,230 --> 00:50:55,063
eftersom när jag har tittat igenom
det hela och det är inte här,

1006
00:50:55,063 --> 00:50:56,930
det bara inte kan vara här.

1007
00:50:56,930 --> 00:50:58,350
>> Innebär det vettigt att alla?

1008
00:50:58,350 --> 00:51:03,230
Så det är som binär sökning bevara
funktionerna i länkade listor.

1009
00:51:03,230 --> 00:51:09,200
Cool, och så den andra typen
datastruktur ni

1010
00:51:09,200 --> 00:51:13,180
kan försöka genomföra på pset,
du bara måste välja en metod.

1011
00:51:13,180 --> 00:51:19,430
Men kanske en alternativ metod för att
hashtabellen är vad vi kallar en trie.

1012
00:51:19,430 --> 00:51:24,080
>> Allt en trie är en
specifik typ av träd som

1013
00:51:24,080 --> 00:51:28,600
har värden som går till andra värden.

1014
00:51:28,600 --> 00:51:31,450
Så istället för att ha en binär
träd i den meningen att endast en

1015
00:51:31,450 --> 00:51:35,940
sak kan peka på två, kan du ha
en sak peka på många, många saker.

1016
00:51:35,940 --> 00:51:39,450
Du har i huvudsak arrayer
insida som du lagrar

1017
00:51:39,450 --> 00:51:41,790
pekare som pekar på andra matriser.

1018
00:51:41,790 --> 00:51:45,210

1019
00:51:45,210 --> 00:51:49,460
>> Så noden om hur vi
skulle definiera en trie

1020
00:51:49,460 --> 00:51:52,590
är att vi vill ha en
Boolean, c ord, eller hur?

1021
00:51:52,590 --> 00:51:54,920
Så noden är Boolean
som sant eller falskt,

1022
00:51:54,920 --> 00:51:58,490
först och främst i spetsen för
att array, är det ett ord?

1023
00:51:58,490 --> 00:52:03,620
För det andra vill du ha tips
till vad resten av dem är.

1024
00:52:03,620 --> 00:52:07,470
En lite komplicerat, lite abstrakt, men
Jag kommer att förklara vad det alla medel.

1025
00:52:07,470 --> 00:52:13,800
>> Så här, i toppen, om man
har en matris förklarade redan,

1026
00:52:13,800 --> 00:52:17,040
en nod där du har en Boolean
värdet som är lagrat vid den främre

1027
00:52:17,040 --> 00:52:19,490
som berättar är det ett ord?

1028
00:52:19,490 --> 00:52:20,520
Är detta inte ett ord?

1029
00:52:20,520 --> 00:52:23,240
Och sedan har du
resten av ditt array som

1030
00:52:23,240 --> 00:52:26,040
faktiskt lagrar alla
möjligheterna för vad det kunde vara.

1031
00:52:26,040 --> 00:52:28,660
Så, till exempel, som
upptill du har

1032
00:52:28,660 --> 00:52:32,140
den första som säger sant eller
falskt, ja eller nej, det är ett ord.

1033
00:52:32,140 --> 00:52:38,130
>> Och då har du 0 till 26
de bokstäver som du kan lagra.

1034
00:52:38,130 --> 00:52:42,790
Om jag ville söka här
för bat, jag går till toppen

1035
00:52:42,790 --> 00:52:49,200
och jag ser för B. Jag tycker B i mitt
array, och så jag vet, OK, är B ett ord?

1036
00:52:49,200 --> 00:52:53,010
B är inte ett ord, så på så sätt
Jag måste fortsätta söka.

1037
00:52:53,010 --> 00:52:56,410
Jag går från B, och jag ser till
pekare som B pekar mot

1038
00:52:56,410 --> 00:53:00,900
och jag ser en annan uppsättning av information,
samma struktur som vi hade tidigare.

1039
00:53:00,900 --> 00:53:05,240
>> Och här-- oh, nästa
brev i [OHÖRBAR] är A.

1040
00:53:05,240 --> 00:53:07,210
Så vi ser i den arrayen.

1041
00:53:07,210 --> 00:53:10,860
Vi finner det åttonde värde,
och sedan ser vi att se, oh,

1042
00:53:10,860 --> 00:53:12,840
hey, det är ett ord, är B-A ett ord?

1043
00:53:12,840 --> 00:53:13,807
Det är inte ett ord.

1044
00:53:13,807 --> 00:53:14,890
Vi måste fortsätta leta.

1045
00:53:14,890 --> 00:53:17,850
>> Och så då ser vi till där
pekaren över A-punkter,

1046
00:53:17,850 --> 00:53:21,130
och den pekar på ett annat sätt i
som vi har mer värde lagras.

1047
00:53:21,130 --> 00:53:24,150
Och slutligen, vi får
B-A-T, som är ett ord.

1048
00:53:24,150 --> 00:53:25,970
Och så nästa gång
du ser, du kommer

1049
00:53:25,970 --> 00:53:30,850
att ha den kontroll av, ja,
Detta Boolean funktion är sant.

1050
00:53:30,850 --> 00:53:35,450
Och så i den mening vi är typ
att ha ett träd med arrayer.

1051
00:53:35,450 --> 00:53:39,890
>> Så då kan du typ av sökning nedåt.

1052
00:53:39,890 --> 00:53:43,650
Snarare än hashing en funktion och
tilldelning av värden av länkad lista,

1053
00:53:43,650 --> 00:53:49,190
du kan bara genomföra en
trie som söker downwords.

1054
00:53:49,190 --> 00:53:50,850
Riktigt, riktigt komplicerat grejer.

1055
00:53:50,850 --> 00:53:54,060
Inte lätt att tänka på att jag är som
spotta så många datastrukturer ut

1056
00:53:54,060 --> 00:53:58,710
på dig, men gör alla slags
förstå hur logiken i detta fungerar?

1057
00:53:58,710 --> 00:54:01,920
>> OK bra.

1058
00:54:01,920 --> 00:54:05,600
Så B-A-T, och sedan
du kommer att söka.

1059
00:54:05,600 --> 00:54:07,940
Nästa gång du ska
att se, oh, hey, det är sant,

1060
00:54:07,940 --> 00:54:09,273
därför vet jag att detta måste vara ett ord.

1061
00:54:09,273 --> 00:54:12,030

1062
00:54:12,030 --> 00:54:13,770
>> Samma sak för zoo.

1063
00:54:13,770 --> 00:54:17,960
Så här är det just nu, om vi
ville söka zoo, just nu,

1064
00:54:17,960 --> 00:54:20,780
närvarande zoo är inte en
ord i vår ordlista

1065
00:54:20,780 --> 00:54:25,300
eftersom, som ni kan se,
första plats som vi har en Boolean

1066
00:54:25,300 --> 00:54:28,590
return true är i slutet av zoom.

1067
00:54:28,590 --> 00:54:30,430
Vi har Z-O-O-M.

1068
00:54:30,430 --> 00:54:33,900
>> Och så här, vi egentligen inte har
ordet, zoo, i vår ordlista

1069
00:54:33,900 --> 00:54:36,070
eftersom den här kryssrutan inte är markerad.

1070
00:54:36,070 --> 00:54:39,540
Så att datorn inte
vet att zoo är ett ord

1071
00:54:39,540 --> 00:54:42,430
eftersom det sätt som vi har
lagras det, bara en zoom här

1072
00:54:42,430 --> 00:54:44,920
faktiskt har ett logiskt värde
som har stängts sant.

1073
00:54:44,920 --> 00:54:49,380
Så om vi vill infoga
ord, zoo, i vår ordlista,

1074
00:54:49,380 --> 00:54:51,770
hur skulle vi gå om att göra det?

1075
00:54:51,770 --> 00:54:55,960
Vad har vi att göra för att se till att vår
dator vet att Z-O-O är ett ord

1076
00:54:55,960 --> 00:54:58,130
och inte det första ordet är Z-O-O-M?

1077
00:54:58,130 --> 00:54:59,360
>> PUBLIK: [OHÖRBAR]

1078
00:54:59,360 --> 00:55:01,450
>> ANDI PENG: Exakt, vi
vill se till att detta

1079
00:55:01,450 --> 00:55:07,890
Här är det logiskt värde
prickas av att det är sant.

1080
00:55:07,890 --> 00:55:13,297
Z-O-O, då vi kommer att kontrollera att,
så vi vet exakt, hej, är djurparken ett ord.

1081
00:55:13,297 --> 00:55:15,380
Jag kommer att tala om
dator att det är ett ord så

1082
00:55:15,380 --> 00:55:18,000
att när datorn kontroller
den vet att zoo är ett ord.

1083
00:55:18,000 --> 00:55:21,269
>> Eftersom ihåg alla dessa uppgifter
strukturer, är det väldigt lätt för oss

1084
00:55:21,269 --> 00:55:22,310
att säga, oh, det bat ett ord.

1085
00:55:22,310 --> 00:55:22,851
Zoo är ett ord.

1086
00:55:22,851 --> 00:55:23,611
Zoom är ett ord.

1087
00:55:23,611 --> 00:55:25,860
Men när du bygger det,
datorn har ingen aning.

1088
00:55:25,860 --> 00:55:28,619
>> Så du måste berätta det exakt
vid vilken tidpunkt är det ett ord?

1089
00:55:28,619 --> 00:55:29,910
Vid vilken tidpunkt är det inte ett ord?

1090
00:55:29,910 --> 00:55:31,784
Och vid vilken tidpunkt jag
behöver söka saker,

1091
00:55:31,784 --> 00:55:34,000
och vid vilken tidpunkt behöver jag gå nästa?

1092
00:55:34,000 --> 00:55:37,010
Alla borta från det?

1093
00:55:37,010 --> 00:55:39,540
Häftigt.

1094
00:55:39,540 --> 00:55:42,530
>> Och så då kommer
problemet med hur skulle vi

1095
00:55:42,530 --> 00:55:45,560
gå om hur du sätter något
det är faktiskt inte det?

1096
00:55:45,560 --> 00:55:49,090
Så låt oss bara säga att vi vill infoga
ordet, bad, i vår trie.

1097
00:55:49,090 --> 00:55:53,589
Som ni kan se som för närvarande
allt vi har nu är B-A-T,

1098
00:55:53,589 --> 00:55:55,630
och denna nya datastruktur
Det hade en pint som

1099
00:55:55,630 --> 00:55:59,740
pekade på null eftersom vi antar
att, åh, det finns inga ord efter B-A-T,

1100
00:55:59,740 --> 00:56:02,530
varför vi måste hålla
ha saker efter att T.

1101
00:56:02,530 --> 00:56:06,581
>> Men problemet uppstår om vi gör du
vill ha ett ord som kommer efter

1102
00:56:06,581 --> 00:56:07,080
T s.

1103
00:56:07,080 --> 00:56:09,500
Om du har bad, du är
kommer att ha en H-rätt.

1104
00:56:09,500 --> 00:56:13,290
Och så hur vi ska göra det är
vi kommer att skapa en separat nod.

1105
00:56:13,290 --> 00:56:16,840
Vi är inte tilldela det belopp
minne för denna nya uppsättning,

1106
00:56:16,840 --> 00:56:20,720
och vi kommer att tilldela pekare.

1107
00:56:20,720 --> 00:56:22,947
>> Vi kommer att tilldela
H, Först av allt, detta null,

1108
00:56:22,947 --> 00:56:24,030
vi kommer att bli av.

1109
00:56:24,030 --> 00:56:26,590
Vi kommer att ha
H-punkten nedåt.

1110
00:56:26,590 --> 00:56:30,600
Om vi ​​ser en H, vi vill ha det
att gå till någon annanstans.

1111
00:56:30,600 --> 00:56:33,910
>> Här inne kan vi sedan bocka av ja.

1112
00:56:33,910 --> 00:56:38,170
Om vi ​​träffar en H efter T, åh,
då vet vi att detta är ett ord.

1113
00:56:38,170 --> 00:56:41,110
Boolean kommer att return true.

1114
00:56:41,110 --> 00:56:42,950
Alla klar över hur det hände?

1115
00:56:42,950 --> 00:56:45,110
OK.

1116
00:56:45,110 --> 00:56:47,214
>> Så i huvudsak alla
dessa datastrukturer

1117
00:56:47,214 --> 00:56:50,130
att vi har gått över i dag, jag har
gått över dem verkligen, verkligen snabbt

1118
00:56:50,130 --> 00:56:52,192
och inte i för mycket
detalj, och det är OK.

1119
00:56:52,192 --> 00:56:53,900
När du börjar messing
med det, kommer du att

1120
00:56:53,900 --> 00:56:55,733
hålla reda på var
alla pekare är,

1121
00:56:55,733 --> 00:56:58,060
vad som händer i din
datastrukturer, et cetera.

1122
00:56:58,060 --> 00:56:59,810
De kommer att vara till stor nytta,
och det är upp till dig

1123
00:56:59,810 --> 00:57:03,890
killar att helt räkna ut hur
du vill genomföra saker.

1124
00:57:03,890 --> 00:57:07,650
>> Och så pset4 av 5-- oh, det är fel.

1125
00:57:07,650 --> 00:57:10,140
Pset5 är felstavningar.

1126
00:57:10,140 --> 00:57:13,710
Som jag sade tidigare, du kommer att, en gång
igen, ladda ner källkoden från oss.

1127
00:57:13,710 --> 00:57:16,210
Det kommer att finnas tre huvud
saker du ska ladda ner.

1128
00:57:16,210 --> 00:57:18,470
Du kommer att ladda ner ordböcker,
kers, och texter.

1129
00:57:18,470 --> 00:57:21,660
>> Alla dessa saker är är
antingen lexikon av ord

1130
00:57:21,660 --> 00:57:25,190
att vi vill att du ska kolla
eller test av uppgifter

1131
00:57:25,190 --> 00:57:26,930
att vi vill att du ska stavningskontroll.

1132
00:57:26,930 --> 00:57:29,670
Och så ordböcker
Vi ger dig går

1133
00:57:29,670 --> 00:57:34,870
för att ge dig de faktiska ord som vi vill
du kan lagra något på ett sätt som är

1134
00:57:34,870 --> 00:57:36,530
effektivare än en array.

1135
00:57:36,530 --> 00:57:38,470
Och då texterna är
kommer att bli vad vi är

1136
00:57:38,470 --> 00:57:43,900
ber dig att stava kontrollera att
alla orden finns riktiga ord.

1137
00:57:43,900 --> 00:57:47,970
>> Och så de tre block av
program som vi ska ger dig

1138
00:57:47,970 --> 00:57:51,130
kallas dictionary.c,
dictionary.h och speller.c.

1139
00:57:51,130 --> 00:57:56,500
Och så alla dictionary.c gör är
vad du blir ombedd att genomföra.

1140
00:57:56,500 --> 00:57:57,880
Den laddar ord.

1141
00:57:57,880 --> 00:58:02,000
Det stava kontroller dem, och det gör säkert
att allt sitter ordentligt.

1142
00:58:02,000 --> 00:58:05,180
>> diction.h är bara ett bibliotek fil
som förklarar alla dessa funktioner.

1143
00:58:05,180 --> 00:58:07,650
Och speller.c, kommer vi att ge dig.

1144
00:58:07,650 --> 00:58:09,290
Du behöver inte ändra något av det.

1145
00:58:09,290 --> 00:58:14,290
Alla speller.c gör är att ta det,
laster det, kontrollerar hastigheten för den,

1146
00:58:14,290 --> 00:58:19,190
testar riktmärket som hur
snabbt du kan göra saker.

1147
00:58:19,190 --> 00:58:20,410
>> Det är en speller.

1148
00:58:20,410 --> 00:58:23,920
Bara inte bråka med den, men göra
att du förstår vad den gör.

1149
00:58:23,920 --> 00:58:28,090
Vi använder en funktion som kallas getrusage som
testar prestanda för din spell

1150
00:58:28,090 --> 00:58:28,590
checker.

1151
00:58:28,590 --> 00:58:32,200
Allt det gör är i grunden testa
tid av allt i din ordlista,

1152
00:58:32,200 --> 00:58:33,680
så se till att du förstår det.

1153
00:58:33,680 --> 00:58:36,660
Var noga med att inte bråka med det eller
annars saker och ting inte kommer att köras.

1154
00:58:36,660 --> 00:58:39,740

1155
00:58:39,740 --> 00:58:44,170
>> Och huvuddelen av denna utmaning är för
ni verkligen ändra dictionary.c.

1156
00:58:44,170 --> 00:58:48,526
Vi kommer att ge dig
140.000 ord i ordlistan.

1157
00:58:48,526 --> 00:58:50,900
Vi kommer att ge dig en text
fil som har dessa ord,

1158
00:58:50,900 --> 00:58:54,840
och vi vill att du ska kunna organisera
dem i en hash-tabell eller en trie

1159
00:58:54,840 --> 00:58:58,140
eftersom när vi ber dig att stava
check-- tänk om du är spell

1160
00:58:58,140 --> 00:59:00,690
kontroll som Homeros Odysséen.

1161
00:59:00,690 --> 00:59:03,010
Det är så här stor, stor test.

1162
00:59:03,010 --> 00:59:05,190
>> Tänk om varje enskild
ord du var tvungen att titta

1163
00:59:05,190 --> 00:59:08,100
genom en rad 140.000 värden.

1164
00:59:08,100 --> 00:59:10,350
Det skulle ta evigheter
för din maskin att köra.

1165
00:59:10,350 --> 00:59:14,490
Det är därför vi vill organisera vår
data till effektivare datastrukturer

1166
00:59:14,490 --> 00:59:17,270
såsom en hashtabell eller en trie.

1167
00:59:17,270 --> 00:59:20,700
Och då ni kan snäll
av när du söker åtkomst

1168
00:59:20,700 --> 00:59:22,570
saker lättare och snabbare.

1169
00:59:22,570 --> 00:59:24,934
>> Och så var noga med att lösa kollisioner.

1170
00:59:24,934 --> 00:59:27,350
Du kommer att få ett gäng
ord av att börja med A.

1171
00:59:27,350 --> 00:59:29,957
Du kommer att få en massa ord
som börjar med B. Upp till dig

1172
00:59:29,957 --> 00:59:31,290
killar hur du vill lösa det.

1173
00:59:31,290 --> 00:59:34,144
Kanske det finns mer
effektiv hash-funktion

1174
00:59:34,144 --> 00:59:36,810
än bara den första bokstaven i
något, och så det är upp till dig

1175
00:59:36,810 --> 00:59:38,190
killar att sorts göra vad du vill.

1176
00:59:38,190 --> 00:59:40,148
>> Kanske du vill lägga till
alla bokstäver tillsammans.

1177
00:59:40,148 --> 00:59:43,410
Kanske du vill gärna göra konstiga saker
att redovisa antalet bokstäver,

1178
00:59:43,410 --> 00:59:43,970
vad som helst.

1179
00:59:43,970 --> 00:59:45,386
Upp till er hur ni vill göra.

1180
00:59:45,386 --> 00:59:49,262
Om du vill göra en hash-tabell, om du
vill prova en trie, helt upp till dig.

1181
00:59:49,262 --> 00:59:52,470
Jag varnar dig i förväg att de
Trie är typiskt lite svårare

1182
00:59:52,470 --> 00:59:54,520
bara för att det finns en hel del
fler tips för att hålla reda på.

1183
00:59:54,520 --> 00:59:55,645
Men helt upp till er.

1184
00:59:55,645 --> 00:59:58,742
Det är betydligt mer effektivt
i de flesta fall.

1185
00:59:58,742 --> 01:00:01,450
Du vill verkligen kunna hålla
koll på alla dina tips.

1186
01:00:01,450 --> 01:00:03,850
Liksom gör samma sak
som jag gjorde här.

1187
01:00:03,850 --> 01:00:06,871
När du försöker infoga
värden i en hashtabell eller ta bort,

1188
01:00:06,871 --> 01:00:08,620
se till att du är
verkligen hålla reda

1189
01:00:08,620 --> 01:00:11,860
där allt beror på
det är verkligen lätt för om jag

1190
01:00:11,860 --> 01:00:14,727
försöker infoga som ordet, andy.

1191
01:00:14,727 --> 01:00:16,810
Låt oss bara säga att det är en
riktigt ord, ord, andy,

1192
01:00:16,810 --> 01:00:19,640
till en gigantisk lista över A-ord.

1193
01:00:19,640 --> 01:00:22,450
>> Om jag råkar bara överlåta
en pekare fel, oops,

1194
01:00:22,450 --> 01:00:24,940
Det går helhet
resten av mitt länkad lista.

1195
01:00:24,940 --> 01:00:26,897
Nu är det enda ord jag
har är andy, och nu

1196
01:00:26,897 --> 01:00:29,230
alla de andra orden i
ordbok har gått förlorade.

1197
01:00:29,230 --> 01:00:31,370
Och så du vill vara säker på att du
hålla reda på alla dina pekare

1198
01:00:31,370 --> 01:00:33,661
eller annat du kommer att få
stora problem i koden.

1199
01:00:33,661 --> 01:00:35,840
Dra saker noggrant steg för steg.

1200
01:00:35,840 --> 01:00:37,870
Det gör det mycket lättare att tänka på.

1201
01:00:37,870 --> 01:00:40,910
>> Och slutligen, vill du kunna
testa dina prestationer i ditt program

1202
01:00:40,910 --> 01:00:41,618
på den stora tavlan.

1203
01:00:41,618 --> 01:00:43,710
Om ni tar en
titta på CS50 just nu,

1204
01:00:43,710 --> 01:00:45,210
vi har vad som kallas den stora styrelsen.

1205
01:00:45,210 --> 01:00:50,200
Det är matchprotokollet av de snabbast
Stavningskontrollen gånger över hela CS50

1206
01:00:50,200 --> 01:00:55,720
just nu, jag tror att toppen som 10
gånger jag tror att åtta av dem är personal.

1207
01:00:55,720 --> 01:00:57,960
Vi vill verkligen att ni ska slå oss.

1208
01:00:57,960 --> 01:01:00,870
>> Alla av oss försökte genomföra
den snabbaste koden som möjligt.

1209
01:01:00,870 --> 01:01:04,880
Vi vill att ni försöka utmana
oss och genomföra snabbare än alla oss

1210
01:01:04,880 --> 01:01:05,550
Kan.

1211
01:01:05,550 --> 01:01:07,970
Och så detta är verkligen
den första gången som vi är

1212
01:01:07,970 --> 01:01:12,680
frågar ni att göra en pset som
du kan göra riktigt i vilken metod

1213
01:01:12,680 --> 01:01:13,760
du vill.

1214
01:01:13,760 --> 01:01:17,730
>> Jag säger alltid, det är mer besläktad
till en verklig lösning, eller hur?

1215
01:01:17,730 --> 01:01:19,550
Jag säger, hej, jag vill att du gör det här.

1216
01:01:19,550 --> 01:01:21,380
Bygg ett program som gör detta för mig.

1217
01:01:21,380 --> 01:01:22,630
Gör det hur du vill.

1218
01:01:22,630 --> 01:01:24,271
Jag vet bara att jag vill snabbt.

1219
01:01:24,271 --> 01:01:25,770
Det är din utmaning för denna vecka.

1220
01:01:25,770 --> 01:01:27,531
Ni kommer vi
för att ge dig en uppgift.

1221
01:01:27,531 --> 01:01:29,030
Vi kommer att ge dig en utmaning.

1222
01:01:29,030 --> 01:01:31,559
Och sedan är det upp till er
att helt bara räkna ut

1223
01:01:31,559 --> 01:01:34,100
vad är det snabbaste och mest
effektivt sätt att genomföra detta.

1224
01:01:34,100 --> 01:01:34,600
Ja?

1225
01:01:34,600 --> 01:01:37,476
>> PUBLIK: Är vi får om
ville att forska snabbare sätt

1226
01:01:37,476 --> 01:01:40,821
att göra hashtabeller nätet, kan vi göra
det och citera någon annans kod?

1227
01:01:40,821 --> 01:01:42,070
ANDI PENG: Ja, helt bra.

1228
01:01:42,070 --> 01:01:44,320
Så om ni läsa
spec, det finns en rad

1229
01:01:44,320 --> 01:01:48,310
i spec som säger ni
är helt gratis att forska hash

1230
01:01:48,310 --> 01:01:51,070
funktioner på vad är några
av de snabbare hashfunktioner

1231
01:01:51,070 --> 01:01:54,720
att köra saker genom så
länge du citerar denna kod.

1232
01:01:54,720 --> 01:01:57,220
Så en del människor har redan
räknat ut snabbt sätt

1233
01:01:57,220 --> 01:02:00,250
att göra stavningskontroller, snabb
sätt att lagra information.

1234
01:02:00,250 --> 01:02:02,750
Helt upp till er om ni
vill bara ta det, eller hur?

1235
01:02:02,750 --> 01:02:04,045
Se till att du citerar.

1236
01:02:04,045 --> 01:02:06,170
Utmaningen här verkligen
att vi försöker testa

1237
01:02:06,170 --> 01:02:09,750
är att se till att du vet
din väg runt pekare.

1238
01:02:09,750 --> 01:02:12,700
Så långt du genomföra
den faktiska hashfunktionen

1239
01:02:12,700 --> 01:02:15,070
och komma med liknande
matten att göra det,

1240
01:02:15,070 --> 01:02:17,570
ni kan forska vad
metoder på nätet ni vill.

1241
01:02:17,570 --> 01:02:17,996
Ja?

1242
01:02:17,996 --> 01:02:19,700
>> PUBLIK: Kan vi bara nämna
genom att använda [OHÖRBAR]?

1243
01:02:19,700 --> 01:02:20,120
>> ANDI PENG: Ja.

1244
01:02:20,120 --> 01:02:22,328
Du kan bara i din kommentar
Du kan citera som, oh,

1245
01:02:22,328 --> 01:02:26,127
tas från yadaen, bla,
bla, hashfunktion.

1246
01:02:26,127 --> 01:02:27,210
Någon som har några frågor?

1247
01:02:27,210 --> 01:02:29,694
Vi faktiskt breezed
genom sektion idag.

1248
01:02:29,694 --> 01:02:31,610
Jag kommer att vara här uppe till
svara på frågor samt.

1249
01:02:31,610 --> 01:02:36,570
>> Dessutom, som jag sa, kontor
timmar ikväll och i morgon.

1250
01:02:36,570 --> 01:02:40,307
Spec denna vecka är faktiskt
super lätt och super kort för att läsa.

1251
01:02:40,307 --> 01:02:43,140
Jag skulle föreslå att ta en titt, bara
läsa igenom hela det.

1252
01:02:43,140 --> 01:02:45,730
>> Och Zamyla faktiskt leder dig
genom var och en av funktionerna

1253
01:02:45,730 --> 01:02:49,796
du behöver för att genomföra, och därför är det
mycket, mycket tydligt hur man gör allt.

1254
01:02:49,796 --> 01:02:51,920
Bara för att se till att du är
hålla reda på pekare.

1255
01:02:51,920 --> 01:02:53,650
Detta är en mycket utmanande pset.

1256
01:02:53,650 --> 01:02:56,744
>> Det är inte utmanande, eftersom liknande,
oh, begreppen är så mycket mer

1257
01:02:56,744 --> 01:02:59,160
svårt, eller om du måste lära
så mycket nytt syntax vägen

1258
01:02:59,160 --> 01:03:00,650
som du gjorde för den sista pset.

1259
01:03:00,650 --> 01:03:03,320
Denna pset är svårt eftersom
det finns så många pekare,

1260
01:03:03,320 --> 01:03:06,980
och då är det väldigt lätt att åter
du har en bugg i koden inte kunna

1261
01:03:06,980 --> 01:03:08,315
ta reda på var att fel är.

1262
01:03:08,315 --> 01:03:13,200
>> Och så komplett och fullkomlig tro på dig
killar att kunna slå vår [OHÖRBAR]

1263
01:03:13,200 --> 01:03:13,700
stavningar.

1264
01:03:13,700 --> 01:03:16,640
Jag har faktiskt inte någon skriftlig gruva
ännu, men jag kommer att skriva min.

1265
01:03:16,640 --> 01:03:19,070
Så medan du skriver
yours, kommer jag att skriva min.

1266
01:03:19,070 --> 01:03:21,070
Jag ska försöka göra
gruvan snabbare än din.

1267
01:03:21,070 --> 01:03:23,940
Vi får se vem som har den snabbaste.

1268
01:03:23,940 --> 01:03:27,340
>> Och ja, jag kommer att se alla
ni här på tisdag.

1269
01:03:27,340 --> 01:03:29,510
Jag kommer att köra ett slag som en pset verkstad.

1270
01:03:29,510 --> 01:03:32,640
Alla avsnitt här
vecka är PSET workshops,

1271
01:03:32,640 --> 01:03:36,690
så ni har massor av möjligheter
för att få hjälp, öppettider som alltid,

1272
01:03:36,690 --> 01:03:41,330
och jag ser verkligen fram emot
läsa alla dina killar "kod.

1273
01:03:41,330 --> 01:03:44,160
Jag har frågesporter upp här om du
killar vill komma och hämta dem.

1274
01:03:44,160 --> 01:03:45,880
Det var allt.

1275
01:03:45,880 --> 01:03:48,180