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

2
00:00:03,381 --> 00:00:10,626

3
00:00:10,626 --> 00:00:11,610
>> [VIDEOAVSPELNING]

4
00:00:11,610 --> 00:00:13,640
>> -Han Ljuger.

5
00:00:13,640 --> 00:00:14,380
>> -Om vad?

6
00:00:14,380 --> 00:00:17,182
>> -Jag Vet inte.

7
00:00:17,182 --> 00:00:19,990
>> -Så Vad vet vi?

8
00:00:19,990 --> 00:00:23,145
>> -Det Vid 09:15, Ray
Santoya var på ATM.

9
00:00:23,145 --> 00:00:23,644
-Ja.

10
00:00:23,644 --> 00:00:27,030
Så frågan är, vad
gjorde han på 9:16?

11
00:00:27,030 --> 00:00:29,720
>> -Shooting 9 millimeter på något.

12
00:00:29,720 --> 00:00:31,540
Han kanske såg prickskytt.

13
00:00:31,540 --> 00:00:33,412
>> -Eller Arbetade med honom.

14
00:00:33,412 --> 00:00:34,340
>> -Vänta.

15
00:00:34,340 --> 00:00:36,200
Gå tillbaka en.

16
00:00:36,200 --> 00:00:36,975
>> -Vad ser du?

17
00:00:36,975 --> 00:00:44,400

18
00:00:44,400 --> 00:00:47,805
>> -Ta Hans ansikte upp helskärmsläge.

19
00:00:47,805 --> 00:00:48,680
>> His glasögon.

20
00:00:48,680 --> 00:00:50,060
>> -Det Finns en reflektion.

21
00:00:50,060 --> 00:01:00,455

22
00:01:00,455 --> 00:01:02,280
>> -Det Är Nuevitas basebollag.

23
00:01:02,280 --> 00:01:03,110
Det är deras logotyp.

24
00:01:03,110 --> 00:01:05,820
>> -Och Han pratar med
vem bär den där jackan.

25
00:01:05,820 --> 00:01:06,670
>> [END SPELA]

26
00:01:06,670 --> 00:01:07,628
>> DAVID MALAN: Okej.

27
00:01:07,628 --> 00:01:11,210
Detta är CS50 och det är lite mer
av [OHÖRBAR] som du är

28
00:01:11,210 --> 00:01:12,890
syssla med problem set fyra.

29
00:01:12,890 --> 00:01:16,606
Idag börjar vi titta lite mer
djupt på dessa saker som kallas pekare,

30
00:01:16,606 --> 00:01:18,480
vilket även om det är
en ganska svårbegripliga ämne,

31
00:01:18,480 --> 00:01:20,813
det visar sig att det kommer
att vara det medel genom vilket vi

32
00:01:20,813 --> 00:01:24,320
kan börja bygga och montering
mycket mer sofistikerade program.

33
00:01:24,320 --> 00:01:28,150
Men vi gjorde det på förra onsdagen
medelst någon claymation först.

34
00:01:28,150 --> 00:01:30,190
Så det här, minns, är
Binky och vi använde honom

35
00:01:30,190 --> 00:01:33,148
att ta en titt på ett program som
egentligen inte göra något intressant,

36
00:01:33,148 --> 00:01:34,950
men det gjorde avslöja några problem.

37
00:01:34,950 --> 00:01:38,570
Så för att börja idag, varför inte vi gå
snabbt igenom några av dessa steg,

38
00:01:38,570 --> 00:01:41,920
försöka destillera i mänskliga villkor
exakt vad som händer här

39
00:01:41,920 --> 00:01:45,410
och varför det är dåligt, och sedan gå vidare
och faktiskt börja bygga något

40
00:01:45,410 --> 00:01:46,309
med denna teknik?

41
00:01:46,309 --> 00:01:48,350
Så dessa var de första
två rader i detta program

42
00:01:48,350 --> 00:01:51,340
och i lekmannaspråk, vad
Dessa två linjer gör?

43
00:01:51,340 --> 00:01:55,600
Någon som är någorlunda bekväma
med vad som anges på skärmen?

44
00:01:55,600 --> 00:01:58,340

45
00:01:58,340 --> 00:02:00,120
Vilka är dessa två linjer gör?

46
00:02:00,120 --> 00:02:02,070
Det är inte alla som
skiljer sig från vecka ett,

47
00:02:02,070 --> 00:02:03,611
men det finns några nya speciell symbol.

48
00:02:03,611 --> 00:02:04,152
Yeah?

49
00:02:04,152 --> 00:02:05,628
Tillbaka dit.

50
00:02:05,628 --> 00:02:07,092
>> PUBLIK: Deklarera pekare?

51
00:02:07,092 --> 00:02:08,050
DAVID MALAN: Säg igen?

52
00:02:08,050 --> 00:02:08,860
PUBLIK: Deklarera pekare?

53
00:02:08,860 --> 00:02:11,776
DAVID MALAN: Deklarera pekare och
låt oss förfina det lite mer.

54
00:02:11,776 --> 00:02:14,050
PUBLIK: [OHÖRBAR]
adress x och sedan y.

55
00:02:14,050 --> 00:02:15,300
DAVID MALAN: Och sedan ta itu med.

56
00:02:15,300 --> 00:02:18,550
Så specifikt vad vi gör
är vi deklarerar två variabler.

57
00:02:18,550 --> 00:02:21,252
Dessa variabler, dock går
att vara av typen int stjärna, som

58
00:02:21,252 --> 00:02:23,210
mer specifikt innebär
de kommer att lagra

59
00:02:23,210 --> 00:02:26,450
adressen till en int,
respektive, x och y.

60
00:02:26,450 --> 00:02:27,660
Nu finns det några värden?

61
00:02:27,660 --> 00:02:32,621
Finns det några konkreta adresser i dessa
två variabler vid denna tidpunkt?

62
00:02:32,621 --> 00:02:33,120
Nej.

63
00:02:33,120 --> 00:02:35,030
Det är bara så kallade skräp värden.

64
00:02:35,030 --> 00:02:38,120
Om du faktiskt inte tilldela en
variabel, oavsett var i RAM

65
00:02:38,120 --> 00:02:42,224
tidigare kommer att fyllas med nollor
och ettor båda av dessa variabler.

66
00:02:42,224 --> 00:02:44,140
Men vi vet ännu inte
vad de är och det är

67
00:02:44,140 --> 00:02:47,060
kommer att vara nyckeln till varför Binky
tappat huvudet förra veckan.

68
00:02:47,060 --> 00:02:49,980
>> Så det här var claymation
inkarnationen av denna

69
00:02:49,980 --> 00:02:53,580
där du har bara två variabler,
små runda bitar av lera,

70
00:02:53,580 --> 00:02:57,330
som kan lagra variabler, men som
de insvept pilarna antyder,

71
00:02:57,330 --> 00:03:00,640
de är faktiskt inte peka
till någonstans känt i sig.

72
00:03:00,640 --> 00:03:03,670
Så då hade vi denna linje, och detta
var nya förra veckan, malloc för minne

73
00:03:03,670 --> 00:03:07,130
tilldelning, som ligger bara ett fint sätt
att tala om för operativsystemet, Linux

74
00:03:07,130 --> 00:03:09,750
eller Mac OS eller Windows,
hej, ge mig lite minne,

75
00:03:09,750 --> 00:03:11,780
och allt du behöver för att berätta
operativsystemet

76
00:03:11,780 --> 00:03:14,699
är vad när ber den för minnet.

77
00:03:14,699 --> 00:03:16,990
Det kommer inte att bry sig om vad
du kommer att göra med det,

78
00:03:16,990 --> 00:03:19,786
men du behöver tala om för operativsystemet
systemet vad genom malloc.

79
00:03:19,786 --> 00:03:20,286
Yeah?

80
00:03:20,286 --> 00:03:21,078
>> PUBLIK: Hur mycket?

81
00:03:21,078 --> 00:03:21,994
DAVID MALAN: Hur mycket?

82
00:03:21,994 --> 00:03:25,280
Hur mycket i byte, och så, denna, återigen,
en krystat exempel bara säga,

83
00:03:25,280 --> 00:03:27,360
ge mig storleken på en int.

84
00:03:27,360 --> 00:03:30,550
Nu, storleken på en int
är fyra bitgrupper eller 32 bitar.

85
00:03:30,550 --> 00:03:32,850
Så det här är bara ett sätt att
säger, hej, operativsystem,

86
00:03:32,850 --> 00:03:37,290
ge mig fyra byte minne
att jag kan använda till mitt förfogande,

87
00:03:37,290 --> 00:03:40,560
och specifikt, vad gör
malloc avkastning med respekt

88
00:03:40,560 --> 00:03:41,795
till den del av fyra byte?

89
00:03:41,795 --> 00:03:44,110

90
00:03:44,110 --> 00:03:44,860
PUBLIK: Adress?

91
00:03:44,860 --> 00:03:45,901
DAVID MALAN: Adressen.

92
00:03:45,901 --> 00:03:47,580
Adressen till den del av fyra byte.

93
00:03:47,580 --> 00:03:48,190
Exakt.

94
00:03:48,190 --> 00:03:51,430
Och så det är vad som lagras i slutändan
ix och det är därför vi inte riktigt

95
00:03:51,430 --> 00:03:55,240
bry sig om vad antalet som
adress är, oavsett om det är OX1 eller OX2

96
00:03:55,240 --> 00:03:57,110
eller några kryptiska hexadecimal adress.

97
00:03:57,110 --> 00:03:59,850
Vi bryr oss bara pictorially
att denna variabel x är nu

98
00:03:59,850 --> 00:04:01,630
pekar på att bit av minnet.

99
00:04:01,630 --> 00:04:05,570
Så att pilen representerar en pekare, eller
mer specifikt, en minnesadress.

100
00:04:05,570 --> 00:04:09,120
Men återigen, vi vanligtvis inte bryr
vad de faktiska adresser är.

101
00:04:09,120 --> 00:04:11,780
Nu, säger denna linje
vad i lekmannaspråk?

102
00:04:11,780 --> 00:04:14,330
Star x får 42 semikolon.

103
00:04:14,330 --> 00:04:17,390
Vad betyder det här?

104
00:04:17,390 --> 00:04:18,200
You wanna go?

105
00:04:18,200 --> 00:04:20,102
Repa inte halsen.

106
00:04:20,102 --> 00:04:22,360
>> PUBLIK: Adressen till x är vid 42.

107
00:04:22,360 --> 00:04:24,300
>> DAVID MALAN: Adressen till x är vid 42.

108
00:04:24,300 --> 00:04:25,190
Inte riktigt.

109
00:04:25,190 --> 00:04:28,485
Så nära, men inte riktigt, eftersom det finns
stjärnan som är prefixing denna x.

110
00:04:28,485 --> 00:04:29,860
Så vi måste justera lite.

111
00:04:29,860 --> 00:04:31,032
Yeah?

112
00:04:31,032 --> 00:04:36,044
>> Publik: Det värde som
pointer x pekar på är 42.

113
00:04:36,044 --> 00:04:36,710
DAVID MALAN: OK.

114
00:04:36,710 --> 00:04:40,840
Värdet som pekaren x är
pekar på, låt oss säga, ska vara 42,

115
00:04:40,840 --> 00:04:44,165
eller annorlunda uttryckt, stjärnan
x säger, gå till valfri adress

116
00:04:44,165 --> 00:04:48,340
är i x, oavsett om det är ett Oxford
Gata eller 33 Oxford Street

117
00:04:48,340 --> 00:04:51,850
eller OX1 eller ox33, oavsett
att numerisk adress är,

118
00:04:51,850 --> 00:04:54,380
stjärna x är Återgång för x.

119
00:04:54,380 --> 00:04:57,297
Så gå till den adressen och
då uppskattar antalet 42 där.

120
00:04:57,297 --> 00:04:59,380
Så det skulle vara en
likvärdigt sätt att säga det.

121
00:04:59,380 --> 00:05:01,860
Så det är allt bra och sedan
Vi skulle representera bilden

122
00:05:01,860 --> 00:05:05,370
på följande sätt där vi har lagt
42 till den del av fyra

123
00:05:05,370 --> 00:05:09,370
bytes på den högra sidan, men
denna linje var där saker gick snett

124
00:05:09,370 --> 00:05:11,120
och Binky huvud poppade
av vid denna punkt,

125
00:05:11,120 --> 00:05:15,290
eftersom dåliga saker hända när
du dereference sopor värden

126
00:05:15,290 --> 00:05:18,210
eller om du dereference ogiltigt
pekare, och jag säger ogiltig

127
00:05:18,210 --> 00:05:21,020
eftersom det vid denna punkt i
historia, vad som finns i y?

128
00:05:21,020 --> 00:05:24,440
Vad är värdet av y baserad
på de senaste stegen?

129
00:05:24,440 --> 00:05:25,360
Yeah?

130
00:05:25,360 --> 00:05:26,115
Vad är det?

131
00:05:26,115 --> 00:05:26,990
>> Publik: En adress.

132
00:05:26,990 --> 00:05:28,460
DAVID MALAN: En adress.

133
00:05:28,460 --> 00:05:31,910
Det bör vara en adress
men har jag initierat det?

134
00:05:31,910 --> 00:05:32,800
Så jag har inte ännu.

135
00:05:32,800 --> 00:05:35,430
Så vad som är känt för att vara där?

136
00:05:35,430 --> 00:05:37,590
Det är bara några sopor värde.

137
00:05:37,590 --> 00:05:41,500
Det kan vara vilken adress som helst från noll till
2000000000 om du har två gig RAM,

138
00:05:41,500 --> 00:05:44,289
eller noll till 4 miljarder om du har
fick fyra gigabyte RAM-minne.

139
00:05:44,289 --> 00:05:46,080
Det är en del skräp värde,
men problemet är

140
00:05:46,080 --> 00:05:48,200
att operativsystemet,
om det inte har gett dig

141
00:05:48,200 --> 00:05:51,140
att bit av minnet specifikt
att du försöker att gå till,

142
00:05:51,140 --> 00:05:54,650
det är allmänt kommer att orsaka vad
vi har sett som en segmentering fel.

143
00:05:54,650 --> 00:05:57,810
Så i själva verket, någon av er som har
kämpade på problem på kontorstid

144
00:05:57,810 --> 00:06:00,393
eller problem som är mer
i allmänhet med att försöka räkna ut

145
00:06:00,393 --> 00:06:02,150
en segmentering fel,
som i allmänhet innebär

146
00:06:02,150 --> 00:06:05,017
du rör vid en del av
minne som du inte bör vara.

147
00:06:05,017 --> 00:06:07,350
Du röra minne som
operativsystemet har inte

148
00:06:07,350 --> 00:06:10,450
tillåtit dig att röra, oavsett om det är
genom att gå för långt i din samling

149
00:06:10,450 --> 00:06:12,870
eller starta nu, om
Det är för att du vidrör

150
00:06:12,870 --> 00:06:14,780
minne som bara är några skräp värde.

151
00:06:14,780 --> 00:06:18,230
>> Så gör stjärniga x här är
sorts odefinierat beteende.

152
00:06:18,230 --> 00:06:22,030
Du ska aldrig göra det eftersom odds
är, är programmet bara kommer att krascha,

153
00:06:22,030 --> 00:06:24,050
eftersom du säger,
gå till denna adress

154
00:06:24,050 --> 00:06:27,000
och du har ingen aning om
den adressen faktiskt är.

155
00:06:27,000 --> 00:06:30,300
Så operativsystemet är sannolikt
kommer att krascha ditt program

156
00:06:30,300 --> 00:06:33,840
som ett resultat och faktiskt, det är
vad som hände där till Binky.

157
00:06:33,840 --> 00:06:37,210
Så i slutändan, Binky fast
Detta problem med detta.

158
00:06:37,210 --> 00:06:38,909
Så att själva programmet var felaktig.

159
00:06:38,909 --> 00:06:41,450
Men om du typ av gå framåt
och verkställa denna linje istället,

160
00:06:41,450 --> 00:06:45,580
y är lika med x betyder bara vad
adress är ett x, också lägga den i y.

161
00:06:45,580 --> 00:06:48,740
>> Och så pictorially, vi har
representerade här med två pilar

162
00:06:48,740 --> 00:06:51,570
från x och y från pekar
till samma plats.

163
00:06:51,570 --> 00:06:55,760
Så semantiskt är x lika
till y eftersom båda dessa

164
00:06:55,760 --> 00:07:00,300
lagrar samma
adress, ergo pekar på 42,

165
00:07:00,300 --> 00:07:04,910
och nu, när du säger stjärnan
y, gå till adressen i y,

166
00:07:04,910 --> 00:07:06,790
Detta har en intressant bieffekt.

167
00:07:06,790 --> 00:07:10,320
Så adressen i y är
samma sak som adressen i x.

168
00:07:10,320 --> 00:07:15,060
Så om du säger gå till adressen
i y och ändra värdet till 13,

169
00:07:15,060 --> 00:07:17,140
vem påverkas?

170
00:07:17,140 --> 00:07:21,100
X, punkt D, så att säga,
bör påverkas också.

171
00:07:21,100 --> 00:07:24,340
>> Och faktiskt, hur Nick drog denna bild
i claymation var just detta.

172
00:07:24,340 --> 00:07:28,665
Även om vi följer pekaren
y, vi hamnade på samma plats,

173
00:07:28,665 --> 00:07:32,780
och så om vi skulle skriva ut
ut x eller y är pointee,

174
00:07:32,780 --> 00:07:35,720
då skulle vi se värdet av 13.

175
00:07:35,720 --> 00:07:37,927
Nu säger jag pointee vara
förenlig med videon.

176
00:07:37,927 --> 00:07:39,760
Programmerare, till min
kunskap, aldrig

177
00:07:39,760 --> 00:07:42,460
säga ordet pointee,
det som är spetsig

178
00:07:42,460 --> 00:07:44,650
på, men för konsekvensens
med videon, inse

179
00:07:44,650 --> 00:07:47,520
det är allt som var
menas i den situationen.

180
00:07:47,520 --> 00:07:54,190
Så några frågor om claymation
eller pekare eller malloc ännu?

181
00:07:54,190 --> 00:07:54,850
Nej?

182
00:07:54,850 --> 00:07:55,470
Okej.

183
00:07:55,470 --> 00:07:58,560
>> Så utan vidare
ADO, låt oss ta en titt

184
00:07:58,560 --> 00:08:00,700
på om detta har faktiskt
använts under en längre tid.

185
00:08:00,700 --> 00:08:03,580
Så vi har haft denna CS50 bibliotek
som har fått alla dessa funktioner.

186
00:08:03,580 --> 00:08:06,810
Vi har använt getInt en hel del, getString,
förmodligen GetLongLong tidigare

187
00:08:06,810 --> 00:08:09,840
i min PSET ett eller så, men
vad som faktiskt pågått?

188
00:08:09,840 --> 00:08:12,920
Nåväl, låt oss ta en snabb titt
under huven på ett program som

189
00:08:12,920 --> 00:08:17,017
inspirerar därför vi ger dig CS50
bibliotek, och även som i förra veckan,

190
00:08:17,017 --> 00:08:18,850
Vi började ta dem
utbildning hjul off.

191
00:08:18,850 --> 00:08:21,080
Så det här är nu sorteras
av en postmortem av vad

192
00:08:21,080 --> 00:08:23,690
har pågått
inne i CS50 biblioteket

193
00:08:23,690 --> 00:08:27,250
trots att vi nu kommer att börja röra sig
bort från det för de flesta program.

194
00:08:27,250 --> 00:08:29,460
>> Så det här är ett program som kallas scanf 0.

195
00:08:29,460 --> 00:08:30,510
Det är super kort.

196
00:08:30,510 --> 00:08:33,909
Det har bara dessa linjer, men det
introducerar en funktion kallad scanf

197
00:08:33,909 --> 00:08:36,909
att vi faktiskt kommer att se i
en stund inne i CS50 biblioteket

198
00:08:36,909 --> 00:08:38,600
om än i en något annorlunda form.

199
00:08:38,600 --> 00:08:41,330
Så det här programmet på rad 16
är att förklara en variabel x.

200
00:08:41,330 --> 00:08:43,150
Så ge mig fyra byte för en int.

201
00:08:43,150 --> 00:08:45,750
Det har varit träffande användaren,
antal snälla, och sedan

202
00:08:45,750 --> 00:08:49,010
detta är en intressant linje som
faktiskt binder samman förra veckan

203
00:08:49,010 --> 00:08:49,790
och det här.

204
00:08:49,790 --> 00:08:53,230
Scanf, och sedan märker att det tar
formatsträng, precis som printf,

205
00:08:53,230 --> 00:08:57,480
% i innebär en int, och sedan tar det en
andra argument som ser lite

206
00:08:57,480 --> 00:08:58,260
funky.

207
00:08:58,260 --> 00:09:01,880
Det är et-tecken x, och att återkalla,
Vi såg bara denna gång förra veckan.

208
00:09:01,880 --> 00:09:03,465
Vad-tecken x representerar?

209
00:09:03,465 --> 00:09:06,210

210
00:09:06,210 --> 00:09:08,450
Vad gör ampersand i C?

211
00:09:08,450 --> 00:09:08,950
Yeah?

212
00:09:08,950 --> 00:09:10,024
>> PUBLIK: Adressen till.

213
00:09:10,024 --> 00:09:11,190
DAVID MALAN: Adressen till.

214
00:09:11,190 --> 00:09:13,190
Så det är motsatsen
av stjärnan operatör,

215
00:09:13,190 --> 00:09:17,270
medan stjärnan operatören säger, gå till
denna adress, et-tecknet operatören

216
00:09:17,270 --> 00:09:20,280
säger, räkna ut
adress denna variabel,

217
00:09:20,280 --> 00:09:23,530
och så detta är nyckeln, eftersom
scanf syfte i livet

218
00:09:23,530 --> 00:09:26,320
är att skanna användarens
input från tangentbordet,

219
00:09:26,320 --> 00:09:29,970
beroende på vad han eller hon
typer och sedan läsa att användarens input

220
00:09:29,970 --> 00:09:32,970
in i en variabel, men vi
såg under de senaste två veckorna

221
00:09:32,970 --> 00:09:36,080
att denna swap funktion som vi
försökte enkelt att genomföra

222
00:09:36,080 --> 00:09:37,110
var bara bruten.

223
00:09:37,110 --> 00:09:42,470
Minns att med växlingsfunktionen,
om vi bara förklarade A och B som Ints,

224
00:09:42,470 --> 00:09:47,040
vi framgångsrikt byta
två variabler inuti swap

225
00:09:47,040 --> 00:09:50,080
precis som med mjölk och EGT,
men så snart swap tillbaka,

226
00:09:50,080 --> 00:09:55,200
vad blev resultatet när det gäller
till x och y, de ursprungliga värdena?

227
00:09:55,200 --> 00:09:55,700
Ingenting.

228
00:09:55,700 --> 00:09:56,200
Yeah.

229
00:09:56,200 --> 00:09:59,754
Ingenting hände den tiden, eftersom
swappar bara ändra sina lokala kopior,

230
00:09:59,754 --> 00:10:01,670
det vill säga, alla
den här gången, när vi har

231
00:10:01,670 --> 00:10:04,010
varit passerar argument
till funktioner, vi är

232
00:10:04,010 --> 00:10:05,939
bara passerar kopior av dessa argument.

233
00:10:05,939 --> 00:10:07,980
Du kan göra med det
vad du vill med dem,

234
00:10:07,980 --> 00:10:10,890
men de kommer att ha någon
effekt på de ursprungliga värdena.

235
00:10:10,890 --> 00:10:13,650
Så detta är problematiskt om du
vill ha en funktion som scanf

236
00:10:13,650 --> 00:10:17,170
i livet, är vars syfte är att skanna
användarens input från tangentbordet

237
00:10:17,170 --> 00:10:22,010
och sedan fylla i tomrummen, så att
tala, dvs ge en variabel som X

238
00:10:22,010 --> 00:10:25,410
ett värde, för om jag var
att bara passera x scanf,

239
00:10:25,410 --> 00:10:28,790
om du anser att logiken i sista
vecka, kan scanf göra vad det vill

240
00:10:28,790 --> 00:10:33,100
med en kopia av x, men den kunde inte
permanent ändra x om vi inte ger

241
00:10:33,100 --> 00:10:37,120
scanf en skattkarta, så att säga,
där x markerar fläcken, varvid

242
00:10:37,120 --> 00:10:41,860
vi passerar in adressen till x så att
scanf kan åka dit och faktiskt förändring

243
00:10:41,860 --> 00:10:42,920
värdet på x.

244
00:10:42,920 --> 00:10:45,080
Och så ja, alla
att detta program inte

245
00:10:45,080 --> 00:10:53,180
om jag gör scanf 0, i min källa
5m katalog, gör scanf 0,

246
00:10:53,180 --> 00:10:57,730
dot slash scanf, antal
vänligen 50, tack för 50.

247
00:10:57,730 --> 00:11:01,020
>> Så det är inte så intressant,
men vad som verkligen händer

248
00:11:01,020 --> 00:11:04,820
är att så fort som jag kallar
scanf här, värdet på x

249
00:11:04,820 --> 00:11:06,410
är permanent ändras.

250
00:11:06,410 --> 00:11:08,335
Nu verkar nice och
bra, och i själva verket, det

251
00:11:08,335 --> 00:11:11,200
verkar som om vi inte verkligen behöver
den CS50 biblioteket alls längre.

252
00:11:11,200 --> 00:11:13,960
Till exempel, låt oss köra
denna gång mer här.

253
00:11:13,960 --> 00:11:15,750
Låt mig återuppta det för en sekund.

254
00:11:15,750 --> 00:11:20,600
Låt oss prova ett antal vänligen och
istället för att säga 50 som förut,

255
00:11:20,600 --> 00:11:22,810
låt oss bara säga nej.

256
00:11:22,810 --> 00:11:24,000
OK, det är lite konstigt.

257
00:11:24,000 --> 00:11:25,270
OK.

258
00:11:25,270 --> 00:11:28,680
Och bara några dumheter här.

259
00:11:28,680 --> 00:11:31,170
Så det verkar inte
hantera felaktiga situationer.

260
00:11:31,170 --> 00:11:33,620
Så vi behöver minimalt start
att lägga till några felkontroll

261
00:11:33,620 --> 00:11:37,460
att se till att användaren har
skrev i ett verkliga antalet som 50,

262
00:11:37,460 --> 00:11:40,720
eftersom det tydligen skriva ord
inte detekteras som problematiska,

263
00:11:40,720 --> 00:11:42,020
men det förmodligen bör vara.

264
00:11:42,020 --> 00:11:46,450
>> Låt oss titta på denna version nu som är
mitt försök att reimplement getString.

265
00:11:46,450 --> 00:11:48,437
Om scanf har allt detta
funktionalitet inbyggd,

266
00:11:48,437 --> 00:11:51,270
Varför har vi syssla med dessa
utbildning hjul som getString?

267
00:11:51,270 --> 00:11:55,450
Tja, här är kanske mitt eget
enkel version av getString

268
00:11:55,450 --> 00:12:00,766
varigenom en vecka sedan, kunde jag ha sagt,
ge mig en sträng och kallar det buffert.

269
00:12:00,766 --> 00:12:03,390
Idag kommer jag att bara börja
säger röding stjärna, som minns,

270
00:12:03,390 --> 00:12:04,400
det är bara synonyma.

271
00:12:04,400 --> 00:12:06,629
Det ser skrämmande men det är
exakt samma sak.

272
00:12:06,629 --> 00:12:09,420
Så ge mig en variabel som heter buffert
som kommer att lagra en sträng,

273
00:12:09,420 --> 00:12:12,780
tala om för användaren strängen snälla,
och sedan, precis som tidigare,

274
00:12:12,780 --> 00:12:17,760
låt oss försöka låna den här lektionen scanf
% s denna gång och sedan passera i buffert.

275
00:12:17,760 --> 00:12:19,310
Nu, en snabb kontroll förstånd.

276
00:12:19,310 --> 00:12:22,120
Varför får jag inte säga
-tecken buffert den här gången?

277
00:12:22,120 --> 00:12:25,190

278
00:12:25,190 --> 00:12:26,625
Sluta från föregående exempel.

279
00:12:26,625 --> 00:12:28,000
PUBLIK: Char stjärnan är en pekare.

280
00:12:28,000 --> 00:12:29,920
DAVID MALAN: Exakt,
eftersom den här gången, röding

281
00:12:29,920 --> 00:12:34,080
stjärna är redan en pekare, en adress,
per definition av stjärnan vara där.

282
00:12:34,080 --> 00:12:37,530
Och om scanf förväntar sig en adress,
räcker det bara att passera i buffert.

283
00:12:37,530 --> 00:12:39,260
Jag behöver inte säga ampersand buffert.

284
00:12:39,260 --> 00:12:42,177
För den nyfikne, du kan
göra något sånt här.

285
00:12:42,177 --> 00:12:43,510
Det skulle ha olika innebörd.

286
00:12:43,510 --> 00:12:47,240
Detta skulle ge dig en pekare
till en pekare, som är faktiskt

287
00:12:47,240 --> 00:12:50,050
en giltig sak i C, men för
nu, låt oss hålla det enkelt

288
00:12:50,050 --> 00:12:51,750
och hålla historien konsekvent.

289
00:12:51,750 --> 00:12:54,100
Jag kommer bara att passera
buffert och det är korrekt.

290
00:12:54,100 --> 00:12:56,487
Problemet är dock redan.

291
00:12:56,487 --> 00:12:58,820
Låt mig gå vidare och köra
program efter att kompilera det.

292
00:12:58,820 --> 00:13:00,902
Gör scanf 1.

293
00:13:00,902 --> 00:13:02,610
Fan det, min kompilator
fånga mitt fel.

294
00:13:02,610 --> 00:13:04,090
Ge mig en sekund.

295
00:13:04,090 --> 00:13:05,460
Klang.

296
00:13:05,460 --> 00:13:06,990
Låt oss säga att scanf-1.c.

297
00:13:06,990 --> 00:13:10,880

298
00:13:10,880 --> 00:13:11,380
OK.

299
00:13:11,380 --> 00:13:12,720
Det går vi.

300
00:13:12,720 --> 00:13:14,280
Jag behöver det.

301
00:13:14,280 --> 00:13:16,750
CS50-ID har olika
konfigurationsinställningar

302
00:13:16,750 --> 00:13:18,280
som skyddar dig mot dig själv.

303
00:13:18,280 --> 00:13:21,300
Jag behövde för att inaktivera dem genom
kör clang manuellt den här gången.

304
00:13:21,300 --> 00:13:22,140
Så sträng snälla.

305
00:13:22,140 --> 00:13:25,560
Jag kommer att gå vidare och skriva
i min favorit hallå världen.

306
00:13:25,560 --> 00:13:26,490
OK, null.

307
00:13:26,490 --> 00:13:27,700
Det är inte vad jag skrev.

308
00:13:27,700 --> 00:13:29,690
Så det är ett tecken på
något att ha fel.

309
00:13:29,690 --> 00:13:33,920
Låt mig gå vidare och skriva
i en riktigt lång sträng.

310
00:13:33,920 --> 00:13:37,210
Tack för noll och jag vet inte
om jag kommer att kunna krascha den.

311
00:13:37,210 --> 00:13:40,240
Låt oss prova lite kopia
klistra och se om det hjälper.

312
00:13:40,240 --> 00:13:43,290
Bara klistra in en hel del av detta.

313
00:13:43,290 --> 00:13:47,310
Det är definitivt en större
sträng än vanligt.

314
00:13:47,310 --> 00:13:51,450
Låt oss bara verkligen skriva det.

315
00:13:51,450 --> 00:13:51,950
Nej.

316
00:13:51,950 --> 00:13:52,650
Jäklar.

317
00:13:52,650 --> 00:13:53,480
Command not found.

318
00:13:53,480 --> 00:13:54,550
Så det är orelaterade.

319
00:13:54,550 --> 00:13:56,440
Det beror på att jag klistrade
några dåliga tecken,

320
00:13:56,440 --> 00:13:59,780
men det visar sig inte kommer att fungera.

321
00:13:59,780 --> 00:14:03,510
>> Låt oss försöka detta en gång till, eftersom
Det är roligare om vi faktiskt kraschar det.

322
00:14:03,510 --> 00:14:09,116
Låt oss skriva detta och nu är jag
kommer att kopiera en riktigt lång sträng

323
00:14:09,116 --> 00:14:10,990
och nu ska vi se om vi
kan krascha den här saken.

324
00:14:10,990 --> 00:14:14,235
Märker jag utelämnade utrymmen och
nya linjer och semikolon

325
00:14:14,235 --> 00:14:16,035
och alla funky tecken.

326
00:14:16,035 --> 00:14:16,535
Enter.

327
00:14:16,535 --> 00:14:21,090

328
00:14:21,090 --> 00:14:22,880
Och nu nätverket är bara att vara långsam.

329
00:14:22,880 --> 00:14:27,460
Jag höll ner Kommando-V för länge, uppenbarligen.

330
00:14:27,460 --> 00:14:28,190
Jäklar!

331
00:14:28,190 --> 00:14:29,260
Command not found.

332
00:14:29,260 --> 00:14:29,780
>> OK.

333
00:14:29,780 --> 00:14:32,240
Tja, är poängen
ändå följande.

334
00:14:32,240 --> 00:14:36,910
Så vad som verkligen händer
på detta uttalande

335
00:14:36,910 --> 00:14:39,240
röding stjärna buffert på linjen 16?

336
00:14:39,240 --> 00:14:41,820
Så vad jag får
när jag deklarerar en pekare?

337
00:14:41,820 --> 00:14:47,440
Allt jag får är en fyra byte värde
kallas buffert, men vad som finns inuti det

338
00:14:47,440 --> 00:14:49,540
just nu?

339
00:14:49,540 --> 00:14:50,930
Det är bara några sopor värde.

340
00:14:50,930 --> 00:14:54,170
Eftersom varje gång du deklarerar en variabel
i C, är det bara några sopor värde,

341
00:14:54,170 --> 00:14:56,220
och vi börjar
resa över denna verklighet.

342
00:14:56,220 --> 00:14:59,720
Nu, när jag berättar scanf,
gå till denna adress

343
00:14:59,720 --> 00:15:01,520
och satte oavsett användaren skriver i.

344
00:15:01,520 --> 00:15:06,400
Om användaren skriver i hello
värld, ja, var kan jag uttrycka det?

345
00:15:06,400 --> 00:15:07,750
Buffert är ett skräp värde.

346
00:15:07,750 --> 00:15:11,510
>> Så det är ungefär som en pil
som är pekar vem vet var.

347
00:15:11,510 --> 00:15:13,880
Kanske det pekar
rätt här i mitt minne.

348
00:15:13,880 --> 00:15:16,560
Och så när användaren
typer i hallå världen,

349
00:15:16,560 --> 00:15:22,380
Programmet försöker sätta
sträng hello world backslash 0

350
00:15:22,380 --> 00:15:23,910
i denna bit av minne.

351
00:15:23,910 --> 00:15:27,070
Men med stor sannolikhet, men
uppenbarligen inte 100% sannolikhet,

352
00:15:27,070 --> 00:15:30,440
datorn kommer att sedan krascha
programmet eftersom detta inte är

353
00:15:30,440 --> 00:15:32,490
minne jag bör tillåtas att röra.

354
00:15:32,490 --> 00:15:36,330
Så kort sagt, är det här programmet
bristfälliga för just den anledningen.

355
00:15:36,330 --> 00:15:38,070
Jag i grunden inte gör vad?

356
00:15:38,070 --> 00:15:42,366
Vilka åtgärder har jag utelämnat, precis som
Vi utelämnade med Binky första exempel?

357
00:15:42,366 --> 00:15:42,866
Yeah?

358
00:15:42,866 --> 00:15:43,710
>> PUBLIK: Memory allocation?

359
00:15:43,710 --> 00:15:45,001
>> DAVID MALAN: Memory tilldelning.

360
00:15:45,001 --> 00:15:48,400
Jag har faktiskt inte tilldelats
något minne för den raden.

361
00:15:48,400 --> 00:15:50,270
Så vi kan fixa detta i ett par olika sätt.

362
00:15:50,270 --> 00:15:52,700
En, kan vi hålla det enkelt
och i själva verket, nu är du

363
00:15:52,700 --> 00:15:55,116
kommer att börja se en oskärpa
av linjerna mellan vad

364
00:15:55,116 --> 00:15:58,520
en array är, vad en sträng är, vad en
röding stjärna är, vad en rad tecken

365
00:15:58,520 --> 00:15:59,020
är.

366
00:15:59,020 --> 00:16:02,450
Här är ett andra exempel
involverar strängar och varsel

367
00:16:02,450 --> 00:16:05,690
allt jag har gjort på nätet
16 är, istället för att säga

368
00:16:05,690 --> 00:16:09,530
denna buffert kommer att bli en röding
stjärna, en pekare till en bit av minne,

369
00:16:09,530 --> 00:16:14,057
Jag ska mycket proaktivt ge
själv en buffert för 16 tecken,

370
00:16:14,057 --> 00:16:16,390
och i själva verket, om du är bekant
med termen buffring,

371
00:16:16,390 --> 00:16:20,570
troligen från världen av videos,
där en video är buffring, buffring,

372
00:16:20,570 --> 00:16:21,175
buffring.

373
00:16:21,175 --> 00:16:22,550
Nå, vad är kopplingen här?

374
00:16:22,550 --> 00:16:24,960
Tja, Insidan av YouTube
och insidan av videospelare

375
00:16:24,960 --> 00:16:27,200
i allmänhet är en array
som är större än 16.

376
00:16:27,200 --> 00:16:30,340
Det kan vara en rad storlek en
megabyte, kanske 10 megabyte,

377
00:16:30,340 --> 00:16:34,330
och in i den matris gör din webbläsare
ladda ner en massa byte,

378
00:16:34,330 --> 00:16:37,500
en massa megabyte
video och videospelare,

379
00:16:37,500 --> 00:16:40,930
YouTubes eller vem är, startar
läsning av byte från denna matris,

380
00:16:40,930 --> 00:16:43,530
och varje gång du ser det
ord buffring, buffring,

381
00:16:43,530 --> 00:16:46,350
som innebär att spelaren har
kommit till slutet av denna uppsättning.

382
00:16:46,350 --> 00:16:50,430
Nätet är så långsam att den inte har
fyllas arrayen med fler bytes

383
00:16:50,430 --> 00:16:55,610
och så du är ute bitar
att visa för användaren.

384
00:16:55,610 --> 00:16:59,430
>> Så buffert är en apt term här genom att
det är bara en uppsättning, en bit av minne.

385
00:16:59,430 --> 00:17:02,530
Och detta kommer att fixa det
eftersom det visar sig

386
00:17:02,530 --> 00:17:07,410
att du kan behandla matriser som om
De är adresser, även om buffert

387
00:17:07,410 --> 00:17:10,710
är bara en symbol, det är en
sekvens av tecken, buffert,

388
00:17:10,710 --> 00:17:14,760
det är nyttigt för mig, programmeraren,
du kan skicka sitt namn runt

389
00:17:14,760 --> 00:17:17,079
som om det vore en
pekare, som om det

390
00:17:17,079 --> 00:17:21,000
var adressen till en bit
minne för 16 tecken.

391
00:17:21,000 --> 00:17:24,530
Så det är att säga, kan jag passera
den scanf exakt det ordet

392
00:17:24,530 --> 00:17:30,670
och så nu, om jag gör det här programmet,
göra scanf 2, pricka snedstreck scanf 2,

393
00:17:30,670 --> 00:17:35,386
och skriv in hallå världen,
Ange att time--

394
00:17:35,386 --> 00:17:37,590
>> Hmm, vad hände?

395
00:17:37,590 --> 00:17:39,340
String vänligen.

396
00:17:39,340 --> 00:17:41,430
Vad gjorde jag för fel?

397
00:17:41,430 --> 00:17:43,800
Hej världen, buffert.

398
00:17:43,800 --> 00:17:44,705
Hej världen.

399
00:17:44,705 --> 00:17:48,201

400
00:17:48,201 --> 00:17:49,420
Ah, jag vet vad den gör.

401
00:17:49,420 --> 00:17:49,920
OK.

402
00:17:49,920 --> 00:17:51,628
Så det är att läsa upp
tills det första utrymmet.

403
00:17:51,628 --> 00:17:55,680
Så låt oss fuska för bara en stund och
säga att jag ville bara skriva något

404
00:17:55,680 --> 00:18:01,408
riktigt långt som detta är en lång mening
det är ett, två, tre, fyra, fem,

405
00:18:01,408 --> 00:18:04,420
sex, sju, åtta, nio,
10, 11, 12, 13, 14, 15, 16.

406
00:18:04,420 --> 00:18:05,300
OK.

407
00:18:05,300 --> 00:18:07,600
Det är verkligen en lång mening.

408
00:18:07,600 --> 00:18:10,710
Så här meningen är
längre än 16 tecken

409
00:18:10,710 --> 00:18:13,670
och så när jag slog in,
vad som kommer att hända?

410
00:18:13,670 --> 00:18:16,940
Jo, i detta fall av
historia, jag hade förklarat buffert

411
00:18:16,940 --> 00:18:22,190
att faktiskt vara en matris
med 16 tecken redo att gå.

412
00:18:22,190 --> 00:18:27,426
Så en, två, tre, fyra, fem, sex,
sju, åtta, nio, tio, elva, tolv, tretton, 14,

413
00:18:27,426 --> 00:18:29,440
15, 16.

414
00:18:29,440 --> 00:18:34,410
Så 16 tecken, och nu, när jag
läs i något sånt här är en lång

415
00:18:34,410 --> 00:18:43,950
mening, vad som kommer att hända är
att jag kommer att läsa i detta är en lång

416
00:18:43,950 --> 00:18:49,660
S-E-N-T-E-N-C-E, mening.

417
00:18:49,660 --> 00:18:52,270
>> Så detta är medvetet
en dålig sak som jag

418
00:18:52,270 --> 00:18:55,060
fortsätta skriva bortom
gränserna för min array,

419
00:18:55,060 --> 00:18:56,660
bortom gränserna för min buffert.

420
00:18:56,660 --> 00:19:00,100
Jag kunde ha tur och programmet
kommer att hålla på löpning och inte bryr sig,

421
00:19:00,100 --> 00:19:03,450
men generellt sett, denna
kommer verkligen krascha mitt program,

422
00:19:03,450 --> 00:19:06,440
och det är en bugg i min
koda det ögonblick jag steg

423
00:19:06,440 --> 00:19:08,576
bortom gränserna
av den matris, eftersom jag

424
00:19:08,576 --> 00:19:10,450
vet inte om det är
nödvändigtvis kommer att krascha

425
00:19:10,450 --> 00:19:12,120
eller om jag bara kommer att få tur.

426
00:19:12,120 --> 00:19:15,750
Så detta är problematiskt eftersom det i
det här fallet, det verkar fungera

427
00:19:15,750 --> 00:19:20,931
och låt oss fresta öde här, även om
IDE verkar tolerera ganska lite

428
00:19:20,931 --> 00:19:21,430
of--

429
00:19:21,430 --> 00:19:22,040
>> Det går vi.

430
00:19:22,040 --> 00:19:23,240
Slutligen.

431
00:19:23,240 --> 00:19:26,470
Så jag är den enda som kan se detta.

432
00:19:26,470 --> 00:19:29,630
Så jag hade bara en massa roligt att skriva
en riktigt lång faktiska fras

433
00:19:29,630 --> 00:19:32,800
att det verkligen överträffat
16 bytes, eftersom jag

434
00:19:32,800 --> 00:19:38,050
skrivit i denna galna lång multi-line
fras, och sedan märker vad som hände.

435
00:19:38,050 --> 00:19:41,110
Programmet försökte skriva ut det
och sedan fick en segmentering fel

436
00:19:41,110 --> 00:19:44,430
och segmente fel är när
något sådant här händer

437
00:19:44,430 --> 00:19:47,650
och operativsystemet säger
nej, kan inte röra det minnet.

438
00:19:47,650 --> 00:19:49,570
Vi kommer att döda
programmet helt och hållet.

439
00:19:49,570 --> 00:19:51,180
>> Så detta verkar problematiskt.

440
00:19:51,180 --> 00:19:54,540
Jag har förbättrat programmet vari
åtminstone ha en del minne,

441
00:19:54,540 --> 00:19:58,000
men detta förefaller begränsa
funktionen getString att få

442
00:19:58,000 --> 00:20:00,780
strängar av någon ändlig längd 16.

443
00:20:00,780 --> 00:20:04,200
Så om du vill stödja längre
meningar än 16 tecken,

444
00:20:04,200 --> 00:20:04,880
Vad gör du?

445
00:20:04,880 --> 00:20:07,970
Tja, kan du öka
Storleken på denna buffert till 32

446
00:20:07,970 --> 00:20:09,190
eller som verkar slags kort.

447
00:20:09,190 --> 00:20:12,260
Varför inte vi bara göra
det 1000 men skjuta tillbaka.

448
00:20:12,260 --> 00:20:17,100
Vad är svaret intuitivt av
bara undvika detta problem genom att göra

449
00:20:17,100 --> 00:20:20,660
min buffert större, liksom 1000 tecken?

450
00:20:20,660 --> 00:20:23,470
Genom att implementera getString detta sätt.

451
00:20:23,470 --> 00:20:27,130
Vad som är bra eller dåligt här?

452
00:20:27,130 --> 00:20:28,033
Yeah?

453
00:20:28,033 --> 00:20:30,574
PUBLIK: Om du binda upp en hel del
utrymme och du inte använder den,

454
00:20:30,574 --> 00:20:33,500
då du inte kan omfördela det utrymmet.

455
00:20:33,500 --> 00:20:34,500
DAVID MALAN: Absolut.

456
00:20:34,500 --> 00:20:38,480
Det är slöseri mån om du inte
faktiskt behöver 900 av dessa bytes

457
00:20:38,480 --> 00:20:41,057
och ändå du ber om
1000 totalt i alla fall,

458
00:20:41,057 --> 00:20:44,140
du bara förbrukar mer minne på
användarens dator än vad du behöver,

459
00:20:44,140 --> 00:20:45,740
och trots allt, en del av
Du har redan stött

460
00:20:45,740 --> 00:20:47,620
i livet att när du är
kör massor av program

461
00:20:47,620 --> 00:20:50,470
och de äter upp massor av minne,
detta kan faktiskt påverka prestanda

462
00:20:50,470 --> 00:20:52,220
och användarens upplevelse
på datorn.

463
00:20:52,220 --> 00:20:56,090
Så det är lite av en lat lösning,
säker, och omvänt,

464
00:20:56,090 --> 00:21:00,140
Det är inte bara slöseri, vilket problem
fortfarande, även om jag gör min buffert

465
00:21:00,140 --> 00:21:02,100
1000?

466
00:21:02,100 --> 00:21:02,600
Yeah?

467
00:21:02,600 --> 00:21:04,475
>> PUBLIK: Strängen är längden 1001.

468
00:21:04,475 --> 00:21:05,350
DAVID MALAN: Exakt.

469
00:21:05,350 --> 00:21:08,280
Om din sträng är längd 1001,
du har exakt samma problem,

470
00:21:08,280 --> 00:21:10,705
och genom min argumentation, skulle jag
just då göra det 2000,

471
00:21:10,705 --> 00:21:12,830
men du vet inte in
förväg hur stor den ska vara,

472
00:21:12,830 --> 00:21:16,890
och ändå, måste jag kompilera mitt program
innan du låter människor använder och nedladdning

473
00:21:16,890 --> 00:21:17,390
Det.

474
00:21:17,390 --> 00:21:21,490
Så det här är precis den typ av
saker som de CS50 biblioteket försöker

475
00:21:21,490 --> 00:21:24,750
att hjälpa oss med och vi ska bara blick
på några av de underliggande genomförandet

476
00:21:24,750 --> 00:21:29,790
här, men detta är CS50 dot C. Denna
är den filen som har varit på CS50 IDE

477
00:21:29,790 --> 00:21:31,420
alla dessa veckor som du har använt.

478
00:21:31,420 --> 00:21:34,280
Det är förkompilerade och du har
använt det automatiskt

479
00:21:34,280 --> 00:21:38,780
som på grund av att ha
dash L CS50 flagga med klang,

480
00:21:38,780 --> 00:21:42,300
men om jag bläddra ner genom alla
dessa funktioner, här är getString,

481
00:21:42,300 --> 00:21:44,636
och bara för att ge dig en
smakprov på vad som händer,

482
00:21:44,636 --> 00:21:46,760
låt oss ta en snabb titt på
den relativa komplexiteten.

483
00:21:46,760 --> 00:21:48,870
Det är inte en super lång
funktion, men vi gjorde inte

484
00:21:48,870 --> 00:21:52,530
måste tänka alla hårt om
hur man ska gå om att få strängar.

485
00:21:52,530 --> 00:21:55,660
>> Så här är min buffert och jag
tydligen initiera den till noll.

486
00:21:55,660 --> 00:21:57,990
Detta, naturligtvis, är den
Samma sak som röding stjärna,

487
00:21:57,990 --> 00:22:00,585
men jag bestämde mig i
genomförandet av CS50 biblioteket

488
00:22:00,585 --> 00:22:02,460
att om vi ska
vara helt dynamisk,

489
00:22:02,460 --> 00:22:05,770
Jag vet inte i förväg hur stor av en
sträng användare kommer att vilja få.

490
00:22:05,770 --> 00:22:08,140
Så jag kommer att börja
med bara en tom sträng

491
00:22:08,140 --> 00:22:11,507
och jag kommer att bygga upp så mycket
minne som jag behöver för att passa användaren strängen

492
00:22:11,507 --> 00:22:13,340
och om jag inte har
nog, kommer jag att be

493
00:22:13,340 --> 00:22:15,010
operativsystemet för mer minne.

494
00:22:15,010 --> 00:22:17,510
Jag kommer att flytta sin sträng
till en större bit av minne

495
00:22:17,510 --> 00:22:21,847
och jag kommer att frigöra eller befria
otillräckligt stor del av minnet

496
00:22:21,847 --> 00:22:23,680
och vi ska bara
att göra detta iterativt.

497
00:22:23,680 --> 00:22:25,570
>> Så en snabb blick,
här är bara en variabel

498
00:22:25,570 --> 00:22:28,780
som jag kommer att hålla koll
av kapaciteten i min buffert.

499
00:22:28,780 --> 00:22:30,071
Hur många bytes kan jag passar?

500
00:22:30,071 --> 00:22:32,070
Här är en variabel n med
som jag kommer att hålla

501
00:22:32,070 --> 00:22:36,200
koll på hur många bytes är faktiskt i
bufferten eller att användaren har skrivit.

502
00:22:36,200 --> 00:22:39,900
Om du inte har sett det här förut, du
kan ange att en variabel som ett int

503
00:22:39,900 --> 00:22:46,370
är osignerad, vilket som namnet antyder,
innebär att det är icke-negativt, och varför skulle

504
00:22:46,370 --> 00:22:50,590
Jag någonsin vill bry specificerar
att en int är inte bara en int,

505
00:22:50,590 --> 00:22:52,540
men det är en osignerad int?

506
00:22:52,540 --> 00:22:55,064
Det är ett icke-negativt int.

507
00:22:55,064 --> 00:22:56,355
Vad gör [OHÖRBAR] detta?

508
00:22:56,355 --> 00:22:58,910
>> PUBLIK: Det beskriver ett belopp
av minne som kan vara [OHÖRBAR].

509
00:22:58,910 --> 00:22:59,660
>> DAVID MALAN: Ja.

510
00:22:59,660 --> 00:23:03,710
Så om jag säger osignerade, är detta faktiskt
ger dig en bit av extra minne

511
00:23:03,710 --> 00:23:07,440
och det verkar slags dumt, men om du
har en bit av extra minne, att

512
00:23:07,440 --> 00:23:09,940
innebär att du har dubbelt så många
värden du kan representera,

513
00:23:09,940 --> 00:23:11,570
eftersom det kan vara en 0 eller en 1.

514
00:23:11,570 --> 00:23:14,660
Så som standard, kan en int vara ungefär
negativa 2000000000 hela vägen

515
00:23:14,660 --> 00:23:16,030
upp till positiv 2 miljarder.

516
00:23:16,030 --> 00:23:18,540
De är stora intervall, men
det är fortfarande slags slöseri

517
00:23:18,540 --> 00:23:21,280
om du bara bryr sig om
storlekar som just intuitivt

518
00:23:21,280 --> 00:23:24,620
bör vara icke-negativa eller
positivt eller 0, ja då,

519
00:23:24,620 --> 00:23:28,884
varför är du slösar 2000000000
möjliga värden för negativa tal

520
00:23:28,884 --> 00:23:30,300
om du aldrig kommer att använda dem?

521
00:23:30,300 --> 00:23:35,350
Så genom att säga osignerade, nu min int kan
vara mellan 0 och cirka 4 miljarder.

522
00:23:35,350 --> 00:23:39,280
>> Så här är bara en int C skäl
vi kommer inte att komma in just nu som

523
00:23:39,280 --> 00:23:42,280
varför det är en int i stället
av en röding, men här är

524
00:23:42,280 --> 00:23:44,630
kontentan av vad som händer
på, och några av er

525
00:23:44,630 --> 00:23:48,340
kanske använder, till exempel, den
fgetc funktion även i PSET fyra

526
00:23:48,340 --> 00:23:51,580
eller senare, vi får se det
igen i problemet set fem,

527
00:23:51,580 --> 00:23:55,410
fgetc är trevligt eftersom som namnet
sorts föreslår slags arcanely,

528
00:23:55,410 --> 00:23:57,940
Det är en funktion som
får en karaktär och så,

529
00:23:57,940 --> 00:24:00,690
vad är fundamentalt annorlunda
om vad vi gör i getString

530
00:24:00,690 --> 00:24:03,110
är att vi inte använder
scanf på samma sätt.

531
00:24:03,110 --> 00:24:07,550
Vi är bara kryper längs steg-för-steg
över vad användaren har skrivit in,

532
00:24:07,550 --> 00:24:10,970
eftersom vi kan alltid tilldela en
röding, och så kan vi alltid säkert

533
00:24:10,970 --> 00:24:15,599
titta på en röding i taget, och
magin börjar hända här.

534
00:24:15,599 --> 00:24:17,890
Jag kommer att rulla ner till
mitt i denna funktion

535
00:24:17,890 --> 00:24:20,360
bara för att presentera kortfattat denna funktion.

536
00:24:20,360 --> 00:24:22,670
Ungefär som det finns en
malloc funktion, det finns

537
00:24:22,670 --> 00:24:27,740
en realloc funktion där realloc
låter dig omfördela en del av minne

538
00:24:27,740 --> 00:24:29,570
och gör det större eller mindre.

539
00:24:29,570 --> 00:24:33,060
Så lång historia kort och med
en våg av min hand för idag,

540
00:24:33,060 --> 00:24:35,620
vet att det som getString
gör är det är typ

541
00:24:35,620 --> 00:24:39,720
av magiskt växer eller
krympande bufferten som användaren

542
00:24:39,720 --> 00:24:41,440
typer i hans eller hennes sträng.

543
00:24:41,440 --> 00:24:43,962
>> Så om användaren skriver ett
kort sträng, denna kod

544
00:24:43,962 --> 00:24:45,920
endast allokerar tillräckligt
minne för att passa strängen.

545
00:24:45,920 --> 00:24:48,086
Om användaren håller skriva
som jag gjorde det igen och igen

546
00:24:48,086 --> 00:24:50,330
och igen, väl, om
buffertens början denna stora

547
00:24:50,330 --> 00:24:53,310
och programmet inser, att
vänta en minut, jag är ute i rymden,

548
00:24:53,310 --> 00:24:55,410
det kommer att fördubbla
storleken på bufferten

549
00:24:55,410 --> 00:24:59,110
och sedan fördubbla storleken på bufferten
koden som gör fördubbling,

550
00:24:59,110 --> 00:25:03,170
Om vi ​​tittar på det här, det är
just detta smarta one-liner.

551
00:25:03,170 --> 00:25:06,830
Du kanske inte har sett denna syntax
innan, men om du säger stjärnan är lika,

552
00:25:06,830 --> 00:25:10,470
Detta är samma sak som
säga kapacitets gånger 2.

553
00:25:10,470 --> 00:25:13,390
Så det blir bara en fördubbling
kapaciteten av bufferten

554
00:25:13,390 --> 00:25:17,480
och sedan träffande realloc att ge
sig om att mycket mer minne.

555
00:25:17,480 --> 00:25:19,720
>> Nu, som en sidoreplik, det
är andra funktioner i här

556
00:25:19,720 --> 00:25:23,680
att vi inte kommer att undersöka detalj
annat än att visa i getInt,

557
00:25:23,680 --> 00:25:26,150
vi använder getString i getInt.

558
00:25:26,150 --> 00:25:28,192
Vi kontrollerar att det inte är
null, som minns,

559
00:25:28,192 --> 00:25:30,400
är det särskilt värde som
betyder något gick fel.

560
00:25:30,400 --> 00:25:31,233
Vi är slut på minne.

561
00:25:31,233 --> 00:25:32,310
Bättre kontrollera det.

562
00:25:32,310 --> 00:25:33,710
Och vi återvänder en vaktpost värde.

563
00:25:33,710 --> 00:25:37,850
Men jag ska skjuta till kommentarerna beträffande
varför och sedan använder vi denna kusin scanf

564
00:25:37,850 --> 00:25:42,100
kallas sscanf och det visar sig
att sscanf eller sträng scanf,

565
00:25:42,100 --> 00:25:45,310
låter dig ta en titt på den linje som
användaren har skrivit in och låt dig

566
00:25:45,310 --> 00:25:49,610
analysera det i huvudsak och vad jag
gör här är jag säger sscanf,

567
00:25:49,610 --> 00:25:54,440
analysera vad användaren har
skrivs in och se till att% i,

568
00:25:54,440 --> 00:25:59,250
Det är ett heltal i det, och vi kommer inte
komma in i dag exakt varför det finns också

569
00:25:59,250 --> 00:26:03,760
en% c här, men att det i ett nötskal tillåter
oss att detektera om användaren har matat in

570
00:26:03,760 --> 00:26:06,050
i något falska efter numret.

571
00:26:06,050 --> 00:26:11,766
Så anledningen till att getInt och getString
berätta för dig att försöka igen, försöka igen, försök igen

572
00:26:11,766 --> 00:26:13,640
är på grund av alla
den koden vi har skrivit,

573
00:26:13,640 --> 00:26:17,900
det är typ att titta på användarens input
i att se till att det är helt numerisk

574
00:26:17,900 --> 00:26:21,700
eller det är en verklig flytande
punktvärde eller liknande,

575
00:26:21,700 --> 00:26:24,233
beroende på vilket värde
fungera du använder.

576
00:26:24,233 --> 00:26:25,060
>> Whew.

577
00:26:25,060 --> 00:26:25,710
OK.

578
00:26:25,710 --> 00:26:27,592
Det var en munsbit
men poängen här är

579
00:26:27,592 --> 00:26:29,550
att anledningen till att vi hade
dessa stödhjulen på

580
00:26:29,550 --> 00:26:32,880
beror på den lägsta nivån,
Det finns bara så många saker som

581
00:26:32,880 --> 00:26:35,674
kan gå fel att vi ville ha
att preemptively hantera

582
00:26:35,674 --> 00:26:38,090
dessa saker säkerligen i
tidigaste veckor för klassen

583
00:26:38,090 --> 00:26:42,230
men nu med PSET fyra och PSET fem och
bortom ser du att det är mer åt

584
00:26:42,230 --> 00:26:45,570
dig men också du är mer kapabel
att lösa dessa typer av problem

585
00:26:45,570 --> 00:26:47,180
själv.

586
00:26:47,180 --> 00:26:51,770
Har du frågor om getString eller getInt?

587
00:26:51,770 --> 00:26:52,630
Yeah?

588
00:26:52,630 --> 00:26:55,130
>> PUBLIK: Varför skulle du dubbla
kapaciteten av bufferten

589
00:26:55,130 --> 00:26:57,630
snarare än att bara öka
det genom det exakta beloppet?

590
00:26:57,630 --> 00:26:58,100
>> DAVID MALAN: Bra fråga.

591
00:26:58,100 --> 00:27:00,474
Varför skulle vi fördubbla kapaciteten
av bufferten i motsats

592
00:27:00,474 --> 00:27:02,800
att bara utöka
av någon konstant värde?

593
00:27:02,800 --> 00:27:03,900
Det var ett beslut design.

594
00:27:03,900 --> 00:27:08,590
Vi har just beslutat att eftersom det tenderar att
vara lite dyrt tidsmässigt att fråga

595
00:27:08,590 --> 00:27:10,440
operativsystemet
för minne, gjorde vi inte

596
00:27:10,440 --> 00:27:13,210
vill sluta få in
en situation för stora strängar

597
00:27:13,210 --> 00:27:14,960
att vi bad
OS och om igen

598
00:27:14,960 --> 00:27:17,500
och om och om igen i
snabb följd för minnet.

599
00:27:17,500 --> 00:27:20,387
Så vi just beslutat, något
godtyckligt men vi hoppas rimligen,

600
00:27:20,387 --> 00:27:22,720
att du vet vad, låt oss
försöka få framför oss

601
00:27:22,720 --> 00:27:25,520
och bara hålla fördubbling det så att
vi minimera mängden gånger

602
00:27:25,520 --> 00:27:29,010
Vi måste ringa malloc eller
realloc, men en total bedömning

603
00:27:29,010 --> 00:27:31,820
ring i avsaknad av att veta
vad användarna kanske vill skriva in.

604
00:27:31,820 --> 00:27:33,600
Båda sätten kan vara diskutabelt.

605
00:27:33,600 --> 00:27:35,430
Förmodligen bra.

606
00:27:35,430 --> 00:27:39,240
>> Så låt oss ta en titt på ett par
andra biverkningar av minne,

607
00:27:39,240 --> 00:27:41,610
saker som kan gå fel
och verktyg som du kan

608
00:27:41,610 --> 00:27:43,880
använda för att fånga dessa typer av misstag.

609
00:27:43,880 --> 00:27:47,800
Det visar sig er alla, även om
check50 har inte sagt så mycket,

610
00:27:47,800 --> 00:27:50,050
har skrivit buggy
kod eftersom vecka ett,

611
00:27:50,050 --> 00:27:53,630
även om alla check50 tester är
passerat, och även om du och din TF

612
00:27:53,630 --> 00:27:56,010
är super säkra på att
koden fungerar som det är tänkt.

613
00:27:56,010 --> 00:27:59,190
Koden har buggy eller
brister på att ni alla,

614
00:27:59,190 --> 00:28:02,540
vid användning av CS50 biblioteket
har läcker minne.

615
00:28:02,540 --> 00:28:06,040
Du har begärt att operativsystemet
för minne i de flesta program

616
00:28:06,040 --> 00:28:08,850
du har skrivit, men du har
aldrig gett det tillbaka.

617
00:28:08,850 --> 00:28:12,110
Du har kallat getString
och getInt och getFloat,

618
00:28:12,110 --> 00:28:15,270
men med getString, du har
aldrig kallas unGetString eller Ge

619
00:28:15,270 --> 00:28:19,890
String Bakåt eller liknande, men vi har sett
att getString inte allokera minne

620
00:28:19,890 --> 00:28:22,810
genom malloc eller detta
funktions realloc, som är bara

621
00:28:22,810 --> 00:28:25,670
mycket i samma anda,
och ändå har vi varit

622
00:28:25,670 --> 00:28:28,629
frågar operativsystemet för
minne och minne och om igen

623
00:28:28,629 --> 00:28:29,670
men aldrig ge det tillbaka.

624
00:28:29,670 --> 00:28:33,550
>> Nu, som en sidoreplik, visar det sig att
när ett program avslutas, allt minne

625
00:28:33,550 --> 00:28:34,870
automatiskt befrias.

626
00:28:34,870 --> 00:28:36,150
Så det har inte varit en stor affär.

627
00:28:36,150 --> 00:28:38,590
Det kommer inte att bryta
IDE eller sakta ner saker,

628
00:28:38,590 --> 00:28:40,670
men när programmen gör
läcker generellt minne

629
00:28:40,670 --> 00:28:42,170
och de kör under en lång tid.

630
00:28:42,170 --> 00:28:45,640
Om du någonsin har sett dumma lilla
badboll i Mac OS eller timglaset

631
00:28:45,640 --> 00:28:51,160
Windows där det är typ av
bromsa eller tänker eller tänkande

632
00:28:51,160 --> 00:28:53,770
eller bara verkligen börjar
att sakta till en genomsökning,

633
00:28:53,770 --> 00:28:56,960
det mycket skulle kunna vara
resultatet av en minnesläcka.

634
00:28:56,960 --> 00:28:59,970
Programmerarna som skrev
programvaran du använder

635
00:28:59,970 --> 00:29:03,570
be operativsystem för minne
med några minuters mellanrum, varje timme.

636
00:29:03,570 --> 00:29:05,570
Men om du kör
mjukvara, även om det är

637
00:29:05,570 --> 00:29:08,680
minimeras i din dator
timmar eller dagar i sträck,

638
00:29:08,680 --> 00:29:11,980
du kanske att begära mer och mer
minne och aldrig faktiskt använder det

639
00:29:11,980 --> 00:29:15,180
och så din kod kan vara, eller
program kan läcka minne,

640
00:29:15,180 --> 00:29:18,350
och om du börjar läcka minne,
det finns mindre minne för andra program,

641
00:29:18,350 --> 00:29:21,220
och effekten är att
sakta ned allt.

642
00:29:21,220 --> 00:29:23,600
>> Nu är detta absolut en av
de mest avskyvärda programmen

643
00:29:23,600 --> 00:29:26,350
du kommer att ha möjligheter
att köra i CS50 mån

644
00:29:26,350 --> 00:29:31,650
som dess utgång är ännu mer esoteriska än
klang: s eller göra eller någon av kommandot

645
00:29:31,650 --> 00:29:35,930
linje program vi har körs innan men
tack och lov, inbäddat i sin produktion

646
00:29:35,930 --> 00:29:39,810
är några super användbara tips som
kommer att vara användbart antingen för PSET fyra

647
00:29:39,810 --> 00:29:41,510
eller säkert PInstallera fem.

648
00:29:41,510 --> 00:29:44,250
Så valgrind är ett verktyg
som kan användas för att leta

649
00:29:44,250 --> 00:29:46,930
för minnesläckor i ditt program.

650
00:29:46,930 --> 00:29:48,570
Det är relativt enkelt att köra.

651
00:29:48,570 --> 00:29:51,420
Du kör valgrind och då, även
även om det är lite mångordig,

652
00:29:51,420 --> 00:29:54,440
streck streck läckagekontroll
lika fullt, och sedan dot

653
00:29:54,440 --> 00:29:56,320
snedstreck och namnet på ditt program.

654
00:29:56,320 --> 00:30:00,010
Så valgrind kommer sedan köra ditt program
och i slutet av ditt program

655
00:30:00,010 --> 00:30:02,240
kör innan det avslutas och
ger dig en annan snabb,

656
00:30:02,240 --> 00:30:04,980
det kommer att analysera din
program samtidigt som det har varit igång

657
00:30:04,980 --> 00:30:07,740
och berätta gjorde du läcker
något minne och ännu bättre,

658
00:30:07,740 --> 00:30:10,610
har du trycker minne som
inte tillhörde dig?

659
00:30:10,610 --> 00:30:13,700
Det kan inte fånga allt, men det är
ganska bra på att fånga det mesta.

660
00:30:13,700 --> 00:30:19,700
>> Så här är ett exempel på min har körts
detta program har körts valgrind,

661
00:30:19,700 --> 00:30:21,470
om ett program som kallas
minne, och jag kommer

662
00:30:21,470 --> 00:30:24,730
att lyfta fram de linjer som är
i slutändan av intresse för oss.

663
00:30:24,730 --> 00:30:27,690
Så det finns ännu fler distraktioner
att jag har tagit bort från bilden.

664
00:30:27,690 --> 00:30:30,930
Men låt oss bara se vad detta
Programmet är i stånd att berätta.

665
00:30:30,930 --> 00:30:34,800
Det är kapabel att berätta saker
som ogiltiga skrivning av storlek 4.

666
00:30:34,800 --> 00:30:38,020
Med andra ord, om du rör minnet,
specifikt 4 byte minne

667
00:30:38,020 --> 00:30:40,350
att du inte ska ha,
valgrind kan berätta för er att.

668
00:30:40,350 --> 00:30:41,660
Ogiltig skrivning av storlek 4.

669
00:30:41,660 --> 00:30:43,640
Du berörde fyra byte
att du inte ska ha.

670
00:30:43,640 --> 00:30:44,840
Var gjorde du det?

671
00:30:44,840 --> 00:30:45,900
Detta är skönheten.

672
00:30:45,900 --> 00:30:50,000
Minnes dot c linje 21 är där du
skruvas upp och det är därför det är bra.

673
00:30:50,000 --> 00:30:53,410
Ungefär som GDB, kan det hjälpa
pekar du på själva felet.

674
00:30:53,410 --> 00:30:57,170
>> Nu är det här en lite mer
verbose, om inte förvirrande.

675
00:30:57,170 --> 00:31:01,307
40 byte i 1 block är definitivt
förlorade i förlust rekord 1 av 1.

676
00:31:01,307 --> 00:31:02,140
Vad betyder det?

677
00:31:02,140 --> 00:31:05,920
Tja, det betyder bara att du bad om
40 bytes och du aldrig gav det tillbaka.

678
00:31:05,920 --> 00:31:08,930
Du ringde malloc eller så kallade
GetString och operativsystemet

679
00:31:08,930 --> 00:31:12,450
gav dig 40 bytes, men du aldrig
frigörs eller utsläppt att minnet,

680
00:31:12,450 --> 00:31:15,400
och för att vara rättvis, har vi aldrig visa
hur du ge tillbaka minnet.

681
00:31:15,400 --> 00:31:17,910
Det visade sig att det finns en super
enkel funktion kallade fria.

682
00:31:17,910 --> 00:31:21,170
Tar ett argument, saken
du vill frigöra eller ge tillbaka,

683
00:31:21,170 --> 00:31:23,430
men 40 bytes, tydligen,
i detta program

684
00:31:23,430 --> 00:31:27,300
har förlorat på rad
20 av minnet dot c.

685
00:31:27,300 --> 00:31:28,650
>> Så låt oss se det här programmet.

686
00:31:28,650 --> 00:31:31,020
Det är super värdelös.

687
00:31:31,020 --> 00:31:33,980
Det visar bara
denna speciella fel.

688
00:31:33,980 --> 00:31:34,920
Så låt oss ta en titt.

689
00:31:34,920 --> 00:31:39,920
Här är huvud och huvud, meddelande, samtal
en funktion som kallas f och sedan tillbaka.

690
00:31:39,920 --> 00:31:41,550
Så inte så intressant.

691
00:31:41,550 --> 00:31:42,664
Vad f göra?

692
00:31:42,664 --> 00:31:44,330
Märker jag inte brydde sig med en prototyp.

693
00:31:44,330 --> 00:31:46,520
Jag ville hålla koden
så liten som möjligt.

694
00:31:46,520 --> 00:31:49,530
Så jag satte f över huvud- och
det är bra, säkert,

695
00:31:49,530 --> 00:31:51,500
för korta program som detta.

696
00:31:51,500 --> 00:31:56,910
Så f inte tillbaka något och gör
inte ta något, men det gör det.

697
00:31:56,910 --> 00:31:59,620
Den förklarar, ungefär som
i Binky exempel

698
00:31:59,620 --> 00:32:02,682
en pekare som heter x som händer
att lagra adressen för en int.

699
00:32:02,682 --> 00:32:03,890
Så det är den vänstra sidan.

700
00:32:03,890 --> 00:32:07,230
På engelska, vad är det
höger sida gör?

701
00:32:07,230 --> 00:32:09,770
Någon?

702
00:32:09,770 --> 00:32:13,665
Vad är detta gör för oss?

703
00:32:13,665 --> 00:32:14,651
Yeah?

704
00:32:14,651 --> 00:32:16,623
>> PUBLIK: [OHÖRBAR]
gånger större än en int

705
00:32:16,623 --> 00:32:19,175
vilket är 10 gånger högre än [OHÖRBAR]

706
00:32:19,175 --> 00:32:20,800
DAVID MALAN: Bra och låt mig sammanfatta.

707
00:32:20,800 --> 00:32:25,480
Så allokera tillräckligt med utrymme för 10 heltal
eller 10, vad är storleken på en int,

708
00:32:25,480 --> 00:32:29,340
Det är fyra byte, så 10 gånger 4 är
40, så att höger sida som jag har

709
00:32:29,340 --> 00:32:33,930
markerade är ge mig 40 byte och
lagra adressen hos den första bitgruppen

710
00:32:33,930 --> 00:32:34,940
in x.

711
00:32:34,940 --> 00:32:38,380
Och nu slutligen, och här är där
detta program är buggig, vad är

712
00:32:38,380 --> 00:32:41,540
fel med linje 21 baserat på denna logik?

713
00:32:41,540 --> 00:32:45,197

714
00:32:45,197 --> 00:32:46,280
Vad är det för fel med linje 21?

715
00:32:46,280 --> 00:32:46,780
Yeah?

716
00:32:46,780 --> 00:32:49,550
PUBLIK: Du kan inte
index till x [OHÖRBAR].

717
00:32:49,550 --> 00:32:50,300
DAVID MALAN: Ja.

718
00:32:50,300 --> 00:32:52,270
Jag borde inte index till x så.

719
00:32:52,270 --> 00:32:53,850
Så syntaktiskt, det är OK.

720
00:32:53,850 --> 00:32:56,990
Vad är trevligt är mycket som du
kan behandla namnet på en matris

721
00:32:56,990 --> 00:33:01,080
som om det är en pekare, på samma sätt
kan du behandla en pekare som om det är

722
00:33:01,080 --> 00:33:06,425
en matris, och så jag kan syntaktiskt
säger x fäste något, x fäste i,

723
00:33:06,425 --> 00:33:07,800
men 10 är problematisk.

724
00:33:07,800 --> 00:33:09,096
Varför?

725
00:33:09,096 --> 00:33:10,910
>> PUBLIK: Eftersom det är inte inne.

726
00:33:10,910 --> 00:33:12,390
>> DAVID MALAN: Det är inte
inuti den del av minnet.

727
00:33:12,390 --> 00:33:15,306
Vad är det största värdet jag skulle
att lägga i dessa hakparenteser?

728
00:33:15,306 --> 00:33:16,870
9, 0 till 9.

729
00:33:16,870 --> 00:33:18,160
På grund av noll indexering.

730
00:33:18,160 --> 00:33:20,190
Så 0 till 9 skulle vara bra.

731
00:33:20,190 --> 00:33:23,960
Konsol 10 är inte bra och
men minns dock, varje gång

732
00:33:23,960 --> 00:33:27,017
Jag verkar försöka göra CS50 IDE
krasch genom att skriva in falska värden,

733
00:33:27,017 --> 00:33:29,100
det är inte alltid samarbeta,
och faktiskt, du ofta

734
00:33:29,100 --> 00:33:31,460
tur bara för att
operativsystem inte

735
00:33:31,460 --> 00:33:35,467
märker att du aldrig så lite
passera någon bit av minnet,

736
00:33:35,467 --> 00:33:38,300
eftersom du bott inom tekniskt
din segment, men mer om det

737
00:33:38,300 --> 00:33:40,940
i ett operativsystem klass,
och så ungefär så här

738
00:33:40,940 --> 00:33:43,000
kan mycket lätt gå oupptäckt.

739
00:33:43,000 --> 00:33:48,120
Ditt program kommer aldrig att krascha
konsekvent men kanske en gång i ett tag.

740
00:33:48,120 --> 00:33:50,610
>> Och så låt oss försöka valgrind
på detta, och här är

741
00:33:50,610 --> 00:33:52,870
där vi får överväldigad
av utsignalen momentant.

742
00:33:52,870 --> 00:34:00,810
Så gör minnes valgrind läckagekontroll
lika fullt prick snedstreck minne.

743
00:34:00,810 --> 00:34:03,040
Och här är varför jag lovar
Detta skulle överväldiga.

744
00:34:03,040 --> 00:34:05,700
Här är vad valgrind, här är vad
en programmerare, några år sedan-

745
00:34:05,700 --> 00:34:08,469
beslutade att det skulle vara en bra idé
för utgången att se ut.

746
00:34:08,469 --> 00:34:09,750
Så låt oss att förstå detta.

747
00:34:09,750 --> 00:34:13,120
Så hela vägen till vänster
sida utan goda skäl

748
00:34:13,120 --> 00:34:16,620
är process-ID för programmet
vi bara köra, unik identifierare

749
00:34:16,620 --> 00:34:18,030
för det program som vi bara sprang.

750
00:34:18,030 --> 00:34:19,738
Vi utgår det från
bilden, men det

751
00:34:19,738 --> 00:34:22,190
är användbar information här.

752
00:34:22,190 --> 00:34:24,684
>> Låt oss bläddra upp till den absoluta toppen.

753
00:34:24,684 --> 00:34:25,600
Här är där vi började.

754
00:34:25,600 --> 00:34:27,040
Så det är inte så mycket utgång.

755
00:34:27,040 --> 00:34:30,429
Här är det ogiltiga skriv
storlek 4 på rad 21.

756
00:34:30,429 --> 00:34:31,760
Nå, vad var ledningen 21?

757
00:34:31,760 --> 00:34:34,500
Linje 21 var exakt
detta och det är vettigt

758
00:34:34,500 --> 00:34:37,290
att jag är i giltigt
skriver 4 byte eftersom jag är

759
00:34:37,290 --> 00:34:40,389
försöker sätta detta heltal,
vilket kan vara allt,

760
00:34:40,389 --> 00:34:42,370
Det råkar bara vara
noll, men jag försöker

761
00:34:42,370 --> 00:34:44,940
för att uttrycka det på ett ställe
som inte tillhör mig.

762
00:34:44,940 --> 00:34:50,900
Dessutom, här nere, 40 byte i en
block definitivt förlorade på rekordtid 1.

763
00:34:50,900 --> 00:34:56,500
Det beror på när jag ringer malloc
här, jag faktiskt aldrig frigöra minnet.

764
00:34:56,500 --> 00:34:58,140
>> Så hur kan vi fixa det här?

765
00:34:58,140 --> 00:35:02,970
Låt mig gå vidare och vara lite säkrare
och gör 9 där och låt mig här fri x.

766
00:35:02,970 --> 00:35:04,820
Detta är den nya funktionen för idag.

767
00:35:04,820 --> 00:35:11,520
Om jag nu köra göra minnes dot snedstreck,
låt oss köra valgrind på det igen,

768
00:35:11,520 --> 00:35:14,990
maximera mitt fönster och tryck på Retur.

769
00:35:14,990 --> 00:35:16,900
Nu är det bra.

770
00:35:16,900 --> 00:35:19,590
De begrava de goda nyheterna
i allt detta utgång.

771
00:35:19,590 --> 00:35:20,810
Alla heap block var gratis.

772
00:35:20,810 --> 00:35:23,604
Vi ska återkomma till vad högen
är, men inga läckage kan inträffa.

773
00:35:23,604 --> 00:35:25,520
Så det här är bara en annan
verktyg för din verktygslåda

774
00:35:25,520 --> 00:35:30,220
med vilken du kan börja
hitta nu fel som.

775
00:35:30,220 --> 00:35:34,532
>> Men låt oss se vad
mer kan gå fel här.

776
00:35:34,532 --> 00:35:38,890
Låt oss övergång nu
faktiskt lösa ett problem.

777
00:35:38,890 --> 00:35:42,440
Som en sidoreplik, om detta kommer att befria en
lite förvirring eller spänning,

778
00:35:42,440 --> 00:35:43,430
detta är nu roligt.

779
00:35:43,430 --> 00:35:46,400

780
00:35:46,400 --> 00:35:46,900
Yeah.

781
00:35:46,900 --> 00:35:49,040
Det är ganska bra.

782
00:35:49,040 --> 00:35:50,890
Eftersom pekare är
adresser och adresser

783
00:35:50,890 --> 00:35:53,098
är i allmänhet av konvention
skriven med hexadecimal.

784
00:35:53,098 --> 00:35:54,650
Ha, är ha denna roliga nu.

785
00:35:54,650 --> 00:35:58,390
Hur som helst, så låt oss nu
faktiskt lösa ett problem.

786
00:35:58,390 --> 00:36:00,840
Detta har varit super,
super låg-nivå hittills,

787
00:36:00,840 --> 00:36:03,950
och vi kan faktiskt göra nytta
saker med dessa uppgifter på låg nivå.

788
00:36:03,950 --> 00:36:06,710
>> Så vi introducerade några veckor
sedan begreppet en array.

789
00:36:06,710 --> 00:36:09,177
En array var trevligt eftersom
det är svårt att städa upp vår kod

790
00:36:09,177 --> 00:36:11,760
eftersom om vi ville skriva en
program med flera elever

791
00:36:11,760 --> 00:36:15,270
eller flera namn och hus och
sovsalar och högskolor och allt detta,

792
00:36:15,270 --> 00:36:19,430
vi kunde lagra allt mer
rent insidan av en matris.

793
00:36:19,430 --> 00:36:23,039
Men föreslå en nackdel
av en array hittills.

794
00:36:23,039 --> 00:36:26,080
Även om du inte har lidit det själv
i ett program, bara instinktivt,

795
00:36:26,080 --> 00:36:30,870
vad är en dålig sak
om en array, kanske?

796
00:36:30,870 --> 00:36:32,337
Jag hör några mummel.

797
00:36:32,337 --> 00:36:34,170
PUBLIK: Det är svårt
för att ändra storlek.

798
00:36:34,170 --> 00:36:36,128
DAVID MALAN: Det är svårt
för att ändra storlek.

799
00:36:36,128 --> 00:36:38,660
Du kan inte ändra storlek
av en array, i själva verket, i och för sig

800
00:36:38,660 --> 00:36:43,040
i C. Du kan tilldela en annan array,
flytta allt från gamla

801
00:36:43,040 --> 00:36:45,380
i det nya, och nu
ha lite extra utrymme,

802
00:36:45,380 --> 00:36:47,469
men det är inte som en
språk som Java eller Python

803
00:36:47,469 --> 00:36:49,760
eller valfritt antal andra
språk med vilket en del av er

804
00:36:49,760 --> 00:36:52,070
kan känna när du
kan bara fortsätta att lägga till saker

805
00:36:52,070 --> 00:36:53,930
till leda till slutet av en array.

806
00:36:53,930 --> 00:36:57,880
När du har en rad
storlek 6, som är dess storlek,

807
00:36:57,880 --> 00:37:01,970
och så mycket som idén tidigare
med en buffert av en viss storlek,

808
00:37:01,970 --> 00:37:05,940
du måste gissa ut ur porten
Vilken storlek vill du att det ska vara?

809
00:37:05,940 --> 00:37:07,880
Om du gissar för stort,
du slösar utrymme.

810
00:37:07,880 --> 00:37:10,950
Om du gissar för liten, du
kan inte lagra dessa uppgifter, åtminstone

811
00:37:10,950 --> 00:37:12,940
utan en mycket mer arbete.

812
00:37:12,940 --> 00:37:18,180
>> Så idag, tack vare pekare, vi kan
börja sy ihop våra egna

813
00:37:18,180 --> 00:37:20,989
datastrukturer, och
Faktum är att här är något

814
00:37:20,989 --> 00:37:23,030
som ser lite mer
kryptiskt vid första anblicken,

815
00:37:23,030 --> 00:37:26,440
men detta är vad vi kallar en länkad
lista, och dess namn slags sammanfattar

816
00:37:26,440 --> 00:37:26,940
Det.

817
00:37:26,940 --> 00:37:29,550
Det är en lista med tal, eller
det här fallet, en lista med tal,

818
00:37:29,550 --> 00:37:33,480
men det kan vara en lista över vad som helst, men
det är sammanlänkade med hjälp av pilar,

819
00:37:33,480 --> 00:37:36,380
och bara ta en gissning
med vilken teknik

820
00:37:36,380 --> 00:37:38,310
kommer vi att kunna
att sy ihop,

821
00:37:38,310 --> 00:37:42,540
ungefär som popcorn med en tråd,
en länkad listor rektanglar här?

822
00:37:42,540 --> 00:37:43,936
Dess siffror?

823
00:37:43,936 --> 00:37:45,560
Vad är det underliggande språket funktionen?

824
00:37:45,560 --> 00:37:46,350
>> Publik: En pekare.

825
00:37:46,350 --> 00:37:47,308
>> DAVID MALAN: En pekare.

826
00:37:47,308 --> 00:37:51,700
Så var och en av dessa pilar här representerar
en pekare eller bara en adress.

827
00:37:51,700 --> 00:37:54,590
Så med andra ord, om jag vill
att lagra en lista med tal,

828
00:37:54,590 --> 00:37:59,040
Jag kan inte bara lagra den om jag vill
förmågan att växa och krympa

829
00:37:59,040 --> 00:38:00,990
min datastruktur i en array.

830
00:38:00,990 --> 00:38:03,000
Så jag måste ha lite
mer sofistikerade,

831
00:38:03,000 --> 00:38:05,720
men märker att detta
bild slags antyder

832
00:38:05,720 --> 00:38:08,650
att om du bara har små trådar
ansluter allt tillsammans,

833
00:38:08,650 --> 00:38:13,100
förmodligen är inte så svårt att göra utrymme
i mellan två av dessa rektanglar

834
00:38:13,100 --> 00:38:16,750
eller två av dessa noder, som vi kommer att börja
kalla dem, sätta i en ny nod,

835
00:38:16,750 --> 00:38:19,547
och sedan med några nya tråd, bara
dike tre noder tillsammans,

836
00:38:19,547 --> 00:38:22,880
den första en, den sista, och en
att du bara infogas i mitten.

837
00:38:22,880 --> 00:38:26,000
>> Och faktiskt en länkad lista,
till skillnad från en array, är dynamisk.

838
00:38:26,000 --> 00:38:27,840
Den kan växa och det kan
krympa och du inte

839
00:38:27,840 --> 00:38:32,434
måste veta eller vård i förväg hur
mycket data du kommer att lagra,

840
00:38:32,434 --> 00:38:35,600
men det visar sig att vi måste vara lite
försiktiga med hur att genomföra detta.

841
00:38:35,600 --> 00:38:39,070
Så låt oss först fundera över hur vi genomför
en av dessa små rektanglar.

842
00:38:39,070 --> 00:38:40,690
Det är lätt att genomföra en int.

843
00:38:40,690 --> 00:38:44,000
Du säger bara int n och sedan
du får 4 byte för en int,

844
00:38:44,000 --> 00:38:49,089
men hur får jag en int, kalla det n,
och sedan en pekare, låt oss kalla det nästa.

845
00:38:49,089 --> 00:38:50,880
Vi skulle kunna kalla dessa
saker vad vi vill

846
00:38:50,880 --> 00:38:53,590
men jag behöver en egen datastruktur.

847
00:38:53,590 --> 00:38:54,257
Yeah?

848
00:38:54,257 --> 00:38:57,020
>> PUBLIK: Ampersand [OHÖRBAR].

849
00:38:57,020 --> 00:39:00,940
>> DAVID MALAN: Så ampersand vi använder för att
få adressen för en nod potentiellt.

850
00:39:00,940 --> 00:39:02,740
Men vi behöver en annan
funktion i C i syfte

851
00:39:02,740 --> 00:39:06,700
att ge mig möjlighet att skapa
denna sed rektangel, denna sed

852
00:39:06,700 --> 00:39:08,919
variabel om ni så vill, i minnet.

853
00:39:08,919 --> 00:39:09,710
PUBLIK: En struct.

854
00:39:09,710 --> 00:39:10,626
DAVID MALAN: En struct.

855
00:39:10,626 --> 00:39:14,310
Minns från förra veckan införde vi
struct, denna relativt enkla sökord

856
00:39:14,310 --> 00:39:16,254
som låter oss göra sånt här.

857
00:39:16,254 --> 00:39:18,420
C kom inte med en data
struktur som kallas elev.

858
00:39:18,420 --> 00:39:22,190
Den levereras med int och float och röding och
sådan, men det kommer inte med elev,

859
00:39:22,190 --> 00:39:26,750
men vi kan skapa en typ elev uppgifter,
en student struktur, med denna syntax

860
00:39:26,750 --> 00:39:27,250
här.

861
00:39:27,250 --> 00:39:28,350
Och du kommer att se det här igen och igen.

862
00:39:28,350 --> 00:39:30,426
Så du behöver inte oroa dig
memorera sökord,

863
00:39:30,426 --> 00:39:33,300
men det sökord som är viktigt är
bara det faktum att vi sade struct

864
00:39:33,300 --> 00:39:37,590
och sedan vi kallade den studerande och inne
av studenterna var ett namn och ett hus

865
00:39:37,590 --> 00:39:39,390
eller en student eller liknande.

866
00:39:39,390 --> 00:39:41,980
>> Och så nu idag, låt oss föreslå detta.

867
00:39:41,980 --> 00:39:45,240
Jag har lagt till några ord, men om jag vill
att genomföra denna rektangel som är

868
00:39:45,240 --> 00:39:48,440
fick både en int och en
pekare, vet du vad, jag är

869
00:39:48,440 --> 00:39:51,540
kommer att deklarera en struct som kallas nod.

870
00:39:51,540 --> 00:39:55,630
Jag är också, inne i det, kommer att säga
att en nod, denna rektangel har en int

871
00:39:55,630 --> 00:39:59,730
och vi kallar det n och
den har en nästa pekare.

872
00:39:59,730 --> 00:40:02,540
Och detta är lite mångordig,
men om man tänker på det,

873
00:40:02,540 --> 00:40:07,300
pilarna som fanns i bilden
en stund sedan är vad datatyp?

874
00:40:07,300 --> 00:40:12,330
Om var och en av dessa pilar pekar
vilken typ av datastruktur?

875
00:40:12,330 --> 00:40:14,332
Det är inte pekar bara en int i sig.

876
00:40:14,332 --> 00:40:16,165
Det pekar på
hela rektangulär sak

877
00:40:16,165 --> 00:40:18,720
och att rektangulära sak,
vi sade, kallas en nod.

878
00:40:18,720 --> 00:40:21,720
Och så vi slags måste
rekursivt definiera detta en sådan

879
00:40:21,720 --> 00:40:26,270
att en nod, ska vi säga,
kommer att innehålla en int kallas n

880
00:40:26,270 --> 00:40:31,070
och en pekare som heter nästa och
typ av datastruktur, till vilken

881
00:40:31,070 --> 00:40:35,770
att pekaren poäng är uppenbarligen
kommer att bli struct nod.

882
00:40:35,770 --> 00:40:41,550
>> Så detta är irriterande mångordig
och bara vara pedantisk,

883
00:40:41,550 --> 00:40:44,100
anledningen till att vi inte kan
bara säga detta, som uppriktigt sagt

884
00:40:44,100 --> 00:40:46,860
ser mycket mer lättläst,
beror återkallande att C läsa

885
00:40:46,860 --> 00:40:48,710
saker uppifrån och ned, från vänster till höger.

886
00:40:48,710 --> 00:40:54,120
Det är inte förrän vi får semikolon
att sökordet noden faktiskt existerar.

887
00:40:54,120 --> 00:40:57,980
Så om vi vill ha denna typ av
cyklisk referens insidan av uppgifter

888
00:40:57,980 --> 00:41:02,120
struktur, vi måste göra detta, där
vi säger struct nod vid topp, som

889
00:41:02,120 --> 00:41:06,770
ger oss en längre sätt att beskriva detta
sak, sedan inuti vi säger struct nod,

890
00:41:06,770 --> 00:41:09,560
och sedan i sista raden
vi säger, okej, C, förresten,

891
00:41:09,560 --> 00:41:12,060
bara kalla hela denna jävla
sak en nod och stoppa

892
00:41:12,060 --> 00:41:14,360
med hjälp av nyckelordet struct helt och hållet.

893
00:41:14,360 --> 00:41:18,030
Så det här är bara en slags syntaktisk
trick som i slutändan låter oss skapa

894
00:41:18,030 --> 00:41:21,370
något som ser ut precis som detta.

895
00:41:21,370 --> 00:41:25,010
>> Så om vi antar nu att vi kan
genomföra den här saken i C,

896
00:41:25,010 --> 00:41:28,040
hur gör vi faktiskt
börja traversera denna?

897
00:41:28,040 --> 00:41:32,360
Tja, i själva verket är allt vi har att göra
iterera från vänster till höger och bara

898
00:41:32,360 --> 00:41:35,960
typ av infoga noder eller ta bort noder
eller söka efter saker var vi vill,

899
00:41:35,960 --> 00:41:39,560
men för att göra detta, låt oss gå vidare och göra
saker lite mer verklig eftersom detta

900
00:41:39,560 --> 00:41:42,560
har varit super låg nivå hittills.

901
00:41:42,560 --> 00:41:45,700
Skulle någon bokstavligen vilja vara först?

902
00:41:45,700 --> 00:41:46,200
OK.

903
00:41:46,200 --> 00:41:47,092
Kom upp.

904
00:41:47,092 --> 00:41:47,800
Vad heter du?

905
00:41:47,800 --> 00:41:48,499
>> David: David.

906
00:41:48,499 --> 00:41:49,290
DAVID MALAN: David.

907
00:41:49,290 --> 00:41:49,998
Trevligt att träffas.

908
00:41:49,998 --> 00:41:50,960
Jag med.

909
00:41:50,960 --> 00:41:52,450
Okej.

910
00:41:52,450 --> 00:41:53,990
Och vi behöver ett nummer 9.

911
00:41:53,990 --> 00:41:55,240
Inte lika bra som första, kanske.

912
00:41:55,240 --> 00:41:56,430
OK, nummer 9.

913
00:41:56,430 --> 00:41:59,667
Ett antal 17, tack.

914
00:41:59,667 --> 00:42:01,000
Låt mig gå tillbaka lite längre.

915
00:42:01,000 --> 00:42:03,980
Number 22, snälla, och
vad sägs om längre tillbaka

916
00:42:03,980 --> 00:42:06,344
Om jag kan se alla händer
med allt det ljus eller ingen.

917
00:42:06,344 --> 00:42:08,010
Någon som frivilligt direkt.

918
00:42:08,010 --> 00:42:08,968
Vill du komma upp?

919
00:42:08,968 --> 00:42:10,450
Din underarm med kraft går upp.

920
00:42:10,450 --> 00:42:12,340
OK, 17.

921
00:42:12,340 --> 00:42:13,690
22.

922
00:42:13,690 --> 00:42:15,120
26 kommer ner.

923
00:42:15,120 --> 00:42:18,450
Skulle någon annan vilja
forcefully-- Kom upp.

924
00:42:18,450 --> 00:42:21,030
En verklig volontär.

925
00:42:21,030 --> 00:42:23,330
>> Så mycket snabbt, om
ni kunde ordna

926
00:42:23,330 --> 00:42:26,550
er precis som
noderna på skärmen.

927
00:42:26,550 --> 00:42:27,510
Tack.

928
00:42:27,510 --> 00:42:29,234
Och du kommer att bli 26.

929
00:42:29,234 --> 00:42:30,650
Okej och snabba introduktioner.

930
00:42:30,650 --> 00:42:32,139
Så jag är David och du är också?

931
00:42:32,139 --> 00:42:32,680
David: David.

932
00:42:32,680 --> 00:42:33,721
DAVID MALAN: Och du är?

933
00:42:33,721 --> 00:42:34,229
JAKE: Jake.

934
00:42:34,229 --> 00:42:34,729
SUE: Sue.

935
00:42:34,729 --> 00:42:35,229
ALEX: Alex.

936
00:42:35,229 --> 00:42:36,475
RAPHAEL: Raphael.

937
00:42:36,475 --> 00:42:37,100
TAYLOR: Taylor.

938
00:42:37,100 --> 00:42:37,466
DAVID MALAN: Taylor.

939
00:42:37,466 --> 00:42:37,590
Utmärkt.

940
00:42:37,590 --> 00:42:39,810
Så dessa är våra volontärer
för idag och gå vidare

941
00:42:39,810 --> 00:42:43,090
och flytta lite på det sättet,
och bara gå vidare och hålla

942
00:42:43,090 --> 00:42:47,024
hålla dina siffror som du är eller din
första tecknet och med vänster hand,

943
00:42:47,024 --> 00:42:48,940
gå vidare och bara genomföra
dessa pilar, precis

944
00:42:48,940 --> 00:42:51,360
så att din vänstra hand är bokstavligen
pekar på vad du ska peka

945
00:42:51,360 --> 00:42:54,610
på, och ge dig själv lite utrymme så att
vi kan visuellt se dina armar faktiskt

946
00:42:54,610 --> 00:42:58,120
pekar, och du kan bara peka
typ av på botten är bra.

947
00:42:58,120 --> 00:43:03,040
>> Så här har vi en länkad lista med en,
två, tre, fyra, fem noder i början,

948
00:43:03,040 --> 00:43:05,860
och märker att vi har denna speciella
pekaren i början som är

949
00:43:05,860 --> 00:43:09,770
nyckel eftersom vi måste hålla koll
listan hela längden på något sätt.

950
00:43:09,770 --> 00:43:13,590
Dessa killar, även om de är kvar
till höger, rygg mot rygg i minnet,

951
00:43:13,590 --> 00:43:15,950
de faktiskt kan vara var som helst
i datorns minne.

952
00:43:15,950 --> 00:43:18,240
Så dessa killar kan vara
står någonstans på scenen

953
00:43:18,240 --> 00:43:20,960
och det är bra, så länge de är
faktiskt pekar på varandra,

954
00:43:20,960 --> 00:43:22,770
men att hålla saker
ren och enkel, vi ska

955
00:43:22,770 --> 00:43:25,728
bara dra dem från vänster till höger som
detta, men det kan finnas stora luckor

956
00:43:25,728 --> 00:43:26,790
i mellan dessa noder.

957
00:43:26,790 --> 00:43:30,710
>> Nu, om jag vill faktiskt sätta några
nytt värde, låt oss gå vidare och göra det.

958
00:43:30,710 --> 00:43:33,720
Vi har en möjlighet nu
att välja en annan nod.

959
00:43:33,720 --> 00:43:39,820
Säg låt oss börja med mallocing 55.

960
00:43:39,820 --> 00:43:41,320
Skulle någon emot att malloc?

961
00:43:41,320 --> 00:43:42,280
OK, kom upp.

962
00:43:42,280 --> 00:43:42,992
Vad heter du?

963
00:43:42,992 --> 00:43:43,700
RAINBOW: Rainbow.

964
00:43:43,700 --> 00:43:44,050
DAVID MALAN: Rainbow?

965
00:43:44,050 --> 00:43:44,810
Okej.

966
00:43:44,810 --> 00:43:46,600
Malloc Rainbow.

967
00:43:46,600 --> 00:43:47,450
Kom upp.

968
00:43:47,450 --> 00:43:51,610
Så nu måste vi fråga oss
algoritm där vi kan sätta 55.

969
00:43:51,610 --> 00:43:53,610
Så vi alla vet,
naturligtvis, där hon förmodligen

970
00:43:53,610 --> 00:43:55,401
hör om vi försöker
att hålla denna sorteras

971
00:43:55,401 --> 00:43:58,299
och om ni kunde ta en
ett steg tillbaka så att vi inte faller bort

972
00:43:58,299 --> 00:43:59,590
scenen, det skulle vara bra.

973
00:43:59,590 --> 00:44:01,420
Så egentligen, Rainbow,
börja om här med mig,

974
00:44:01,420 --> 00:44:04,200
eftersom vi som datorn nu kan
bara se en variabel i taget.

975
00:44:04,200 --> 00:44:05,190
Så om detta är den första noden.

976
00:44:05,190 --> 00:44:07,160
Lägg märke till att han inte är en nod,
Han är bara en pekare,

977
00:44:07,160 --> 00:44:10,270
och det är därför han dras till vara
bara storleken på en pekare, inte

978
00:44:10,270 --> 00:44:11,780
en av de fullständiga rektanglar.

979
00:44:11,780 --> 00:44:16,650
Så vi kommer att kontrollera vid varje
iteration är 55 mindre än 9?

980
00:44:16,650 --> 00:44:17,150
Nej.

981
00:44:17,150 --> 00:44:19,060
Är 55 mindre än 17?

982
00:44:19,060 --> 00:44:19,720
Nej.

983
00:44:19,720 --> 00:44:20,800
Mindre än 22?

984
00:44:20,800 --> 00:44:22,020
Mindre än 26?

985
00:44:22,020 --> 00:44:23,390
Mindre än 34?

986
00:44:23,390 --> 00:44:25,890
Och så nu, självklart
Rainbow hör i slutet.

987
00:44:25,890 --> 00:44:27,270
Så för att vara tydlig, och vad
var ditt namn, Taylor?

988
00:44:27,270 --> 00:44:27,895
>> TAYLOR: Taylor.

989
00:44:27,895 --> 00:44:32,510
DAVID MALAN: Så bland Taylors
vänster hand och Rainbow händer här,

990
00:44:32,510 --> 00:44:38,324
vars hand måste peka på det som i
För att sätta in 55 i listan?

991
00:44:38,324 --> 00:44:39,240
Vad behöver vi göra?

992
00:44:39,240 --> 00:44:39,700
Yeah?

993
00:44:39,700 --> 00:44:41,140
>> Publik: Taylors handen
måste peka åt vänster.

994
00:44:41,140 --> 00:44:41,680
>> DAVID MALAN: Exakt.

995
00:44:41,680 --> 00:44:43,800
Så du sätter en nod
i slutet av listan

996
00:44:43,800 --> 00:44:47,140
är ganska enkelt eftersom Taylor bara
måste peka, i stället för på marken

997
00:44:47,140 --> 00:44:49,640
eller ska vi kalla det noll,
null är typ av frånvaron

998
00:44:49,640 --> 00:44:51,640
av en pekare eller en speciell
noll pekare, du är

999
00:44:51,640 --> 00:44:53,740
kommer att peka med vänster
handen på Rainbow och sedan Rainbow,

1000
00:44:53,740 --> 00:44:55,910
där ska din vänstra
handen förmodligen peka?

1001
00:44:55,910 --> 00:44:56,570
Ner.

1002
00:44:56,570 --> 00:45:00,140
Det är inte bra om hennes hand är typ
pekar ut här eller typ av någon

1003
00:45:00,140 --> 00:45:00,640
vilken väg.

1004
00:45:00,640 --> 00:45:02,407
Det skulle anses
en soptunna värde,

1005
00:45:02,407 --> 00:45:04,240
men om hon pekar på
några kända värdet, vi ska

1006
00:45:04,240 --> 00:45:07,360
kalla det noll eller noll, det är OK
eftersom vi har en löptid på detta

1007
00:45:07,360 --> 00:45:09,390
och vi vet att listan är klar.

1008
00:45:09,390 --> 00:45:11,550
>> Så vad är en annan
relativt enkelt fall?

1009
00:45:11,550 --> 00:45:13,125
Kan vi malloc 5?

1010
00:45:13,125 --> 00:45:14,010
Kom upp.

1011
00:45:14,010 --> 00:45:14,782
Vad heter du?

1012
00:45:14,782 --> 00:45:15,490
Tiffany: Tiffany.

1013
00:45:15,490 --> 00:45:16,000
DAVID MALAN: Jag är ledsen?

1014
00:45:16,000 --> 00:45:16,470
Tiffany: Tiffany.

1015
00:45:16,470 --> 00:45:16,880
DAVID MALAN: Tiffany.

1016
00:45:16,880 --> 00:45:17,110
Okej.

1017
00:45:17,110 --> 00:45:19,071
Tiffany har malloced
med värdet 5.

1018
00:45:19,071 --> 00:45:19,570
Kom upp.

1019
00:45:19,570 --> 00:45:23,820
Detta är relativt lätt också, men
låt oss betrakta order av verksamheten nu.

1020
00:45:23,820 --> 00:45:25,820
Det var ganska lätt
med Taylor i slutet.

1021
00:45:25,820 --> 00:45:30,302
Nummer 5 är naturligtvis mindre än 9,
och så vi har David, vi har Tiffany,

1022
00:45:30,302 --> 00:45:31,260
och vad var ditt namn?

1023
00:45:31,260 --> 00:45:31,680
>> JAKE: Jake.

1024
00:45:31,680 --> 00:45:32,470
>> DAVID MALAN: Jake.

1025
00:45:32,470 --> 00:45:34,300
Tiffany, Jake, och David.

1026
00:45:34,300 --> 00:45:36,580
Vars hand bör uppdateras först?

1027
00:45:36,580 --> 00:45:39,260

1028
00:45:39,260 --> 00:45:40,590
Vad vill du göra här?

1029
00:45:40,590 --> 00:45:45,244
Det finns ett par olika sätt, men
det finns också en eller flera fel sätt.

1030
00:45:45,244 --> 00:45:46,620
>> PUBLIK: Börja med längst till vänster.

1031
00:45:46,620 --> 00:45:47,800
>> DAVID MALAN: Börja med längst till vänster.

1032
00:45:47,800 --> 00:45:49,008
Vem är längst till vänster här då?

1033
00:45:49,008 --> 00:45:49,700
PUBLIK: First.

1034
00:45:49,700 --> 00:45:50,366
>> DAVID MALAN: OK.

1035
00:45:50,366 --> 00:45:53,781
Så börja med först och där gör du
vill uppdatera Davids händer att vara?

1036
00:45:53,781 --> 00:45:54,780
PUBLIK: Mot 5.

1037
00:45:54,780 --> 00:45:55,446
DAVID MALAN: OK.

1038
00:45:55,446 --> 00:45:59,026
Så David, peka på fem
eller Tiffany här och nu?

1039
00:45:59,026 --> 00:46:01,072
>> PUBLIK: Tiffany pekar på 9?

1040
00:46:01,072 --> 00:46:04,030
DAVID MALAN: Perfekt, utom Binky s
chef bara typ av föll, eller hur?

1041
00:46:04,030 --> 00:46:06,820
För vad är det för fel med
den här bilden bokstavligen?

1042
00:46:06,820 --> 00:46:08,070
PUBLIK: Ingenting pekar.

1043
00:46:08,070 --> 00:46:09,945
DAVID MALAN: Ingenting är
pekar på Jake nu.

1044
00:46:09,945 --> 00:46:13,360
Vi har bokstavligen föräldralösa 9
och 17, och vi har bokstavligen

1045
00:46:13,360 --> 00:46:18,450
läckt ut av detta minne, eftersom de genom
uppdatering Davids hand först, det är

1046
00:46:18,450 --> 00:46:21,660
bra eftersom den är korrekt
pekar på Tiffany nu,

1047
00:46:21,660 --> 00:46:25,410
men om ingen hade
framsyntheten att peka på Jake,

1048
00:46:25,410 --> 00:46:27,490
då vi har förlorat
helheten av denna förteckning.

1049
00:46:27,490 --> 00:46:28,200
Så låt oss ångra.

1050
00:46:28,200 --> 00:46:30,950
Så det var en bra sak att
snubbla över men låt oss korrigera nu.

1051
00:46:30,950 --> 00:46:33,624
Vad ska vi göra först i stället?

1052
00:46:33,624 --> 00:46:34,124
Yeah?

1053
00:46:34,124 --> 00:46:35,791
>> PUBLIK: Tiffany bör peka på 9?

1054
00:46:35,791 --> 00:46:37,582
DAVID MALAN: Jag kan inte
få det nära dig.

1055
00:46:37,582 --> 00:46:38,720
Vem ska peka på 9?

1056
00:46:38,720 --> 00:46:39,220
>> PUBLIK: Tiffany.

1057
00:46:39,220 --> 00:46:39,390
>> DAVID MALAN: Okej.

1058
00:46:39,390 --> 00:46:41,200
Så Tiffany bör första punkten på 9.

1059
00:46:41,200 --> 00:46:43,550
Så Tiffany bör ta
på en identisk värde

1060
00:46:43,550 --> 00:46:45,820
David, som verkar
redundant för en stund,

1061
00:46:45,820 --> 00:46:48,820
men det är bra för nu, andra
steg, kan vi uppdatera David hand

1062
00:46:48,820 --> 00:46:52,680
att peka på Tiffany, och sedan om
vi bara typ av ren upp saker

1063
00:46:52,680 --> 00:46:55,740
som om det är typ av vårlikt,
nu som är en korrekt isättning.

1064
00:46:55,740 --> 00:46:56,700
Så utmärkt.

1065
00:46:56,700 --> 00:46:57,970
Så nu är vi nästan där.

1066
00:46:57,970 --> 00:47:01,075
Låt oss sätta en slutlig
värde som värdet 20.

1067
00:47:01,075 --> 00:47:03,010
Om vi ​​kunde malloc en slutlig volontär?

1068
00:47:03,010 --> 00:47:04,140
Kom upp.

1069
00:47:04,140 --> 00:47:06,224
Så här är lite mer besvärlig.

1070
00:47:06,224 --> 00:47:08,390
Men egentligen, koden är vi
skrift, om än verbalt,

1071
00:47:08,390 --> 00:47:10,610
är precis som att ha ett gäng
av om förhållandena nu, eller hur?

1072
00:47:10,610 --> 00:47:12,318
Vi hade en beskaffenhet
kontrollera om det hör

1073
00:47:12,318 --> 00:47:13,840
i slutet, kanske början.

1074
00:47:13,840 --> 00:47:15,940
Vi behöver någon form av slinga för att
hitta plats i mitten.

1075
00:47:15,940 --> 00:47:17,400
Så låt oss göra det med vad heter du?

1076
00:47:17,400 --> 00:47:17,700
>> ERIC: Eric.

1077
00:47:17,700 --> 00:47:18,340
>> DAVID MALAN: Eric?

1078
00:47:18,340 --> 00:47:18,660
Eric.

1079
00:47:18,660 --> 00:47:19,368
Trevligt att träffas.

1080
00:47:19,368 --> 00:47:20,490
Så vi har 20.

1081
00:47:20,490 --> 00:47:21,220
Mindre än fem?

1082
00:47:21,220 --> 00:47:21,530
Nej.

1083
00:47:21,530 --> 00:47:22,160
Mindre än nio?

1084
00:47:22,160 --> 00:47:22,410
Nej.

1085
00:47:22,410 --> 00:47:23,050
Mindre än 17?

1086
00:47:23,050 --> 00:47:23,550
Nej.

1087
00:47:23,550 --> 00:47:23,740
OK.

1088
00:47:23,740 --> 00:47:25,701
Han hör hemma här och
ditt namn igen är?

1089
00:47:25,701 --> 00:47:26,200
SUE: Sue.

1090
00:47:26,200 --> 00:47:26,880
DAVID MALAN: Sue.

1091
00:47:26,880 --> 00:47:27,379
ALEX: Alex.

1092
00:47:27,379 --> 00:47:28,790
DAVID MALAN: Sue, Alex, och?

1093
00:47:28,790 --> 00:47:29,290
ERIC: Eric.

1094
00:47:29,290 --> 00:47:30,120
DAVID MALAN: Eric.

1095
00:47:30,120 --> 00:47:32,140
Vars händer måste uppdateras först?

1096
00:47:32,140 --> 00:47:32,930
>> PUBLIK: Eric.

1097
00:47:32,930 --> 00:47:33,429
OK.

1098
00:47:33,429 --> 00:47:35,200
Så Eric bör peka på där?

1099
00:47:35,200 --> 00:47:35,930
Vid 22.

1100
00:47:35,930 --> 00:47:36,430
God.

1101
00:47:36,430 --> 00:47:38,180
Och nu vad händer nu?

1102
00:47:38,180 --> 00:47:40,800
Sue kan peka på Eric
och nu, om ni bara

1103
00:47:40,800 --> 00:47:44,077
göra vissa rum, vilket är bra
visuellt, nu har vi gjort insättningen.

1104
00:47:44,077 --> 00:47:47,160
Så låt oss nu behandla ett ärende, men
Tack så mycket för våra volontärer.

1105
00:47:47,160 --> 00:47:48,090
Väldigt bra gjort.

1106
00:47:48,090 --> 00:47:50,831
Du kan behålla dem, om du vill.

1107
00:47:50,831 --> 00:47:54,140
Och vi har en härlig avskedsgåva om
du skulle varje vilja ta en stressboll.

1108
00:47:54,140 --> 00:47:56,030
Låt mig bara passera ner det.

1109
00:47:56,030 --> 00:47:58,430
Så vad är takeaway av detta?

1110
00:47:58,430 --> 00:48:02,430
Detta verkar vara fantastiskt
mån vi har nu

1111
00:48:02,430 --> 00:48:06,360
introducerade ett alternativ till en
matris som inte är så begränsad

1112
00:48:06,360 --> 00:48:07,780
till en matris av någon fast storlek.

1113
00:48:07,780 --> 00:48:09,380
De kan växa dynamiskt.

1114
00:48:09,380 --> 00:48:13,220
>> Men mycket som vi har sett i veckor
förflutna, vi aldrig få något gratis,

1115
00:48:13,220 --> 00:48:15,740
som säkerligen finns det en avvägning här.

1116
00:48:15,740 --> 00:48:18,890
Så med en uppåtsidan av en länkad
listan, är denna dynamik?

1117
00:48:18,890 --> 00:48:21,590
Denna förmåga att växa och uppriktigt sagt,
Vi kunde ha gjort delete

1118
00:48:21,590 --> 00:48:23,570
och vi kunde krympa efter behov.

1119
00:48:23,570 --> 00:48:24,710
Vilket pris betalar vi?

1120
00:48:24,710 --> 00:48:28,510

1121
00:48:28,510 --> 00:48:30,340
Dubbelt så mycket utrymme, i första hand.

1122
00:48:30,340 --> 00:48:34,010
Om du tittar på bilden, inte längre
jag lagra en lista av heltal.

1123
00:48:34,010 --> 00:48:36,740
Jag lagrar en lista över
heltal plus pekare.

1124
00:48:36,740 --> 00:48:38,240
Så jag fördubbla mängden utrymme.

1125
00:48:38,240 --> 00:48:40,740
Nu kanske det är inte en sådan
en big deal 4 bytes, 8 byte,

1126
00:48:40,740 --> 00:48:43,160
men det kan säkert lägga
för stora datamängder.

1127
00:48:43,160 --> 00:48:45,570
Vad är en annan nackdel?

1128
00:48:45,570 --> 00:48:46,070
Yeah?

1129
00:48:46,070 --> 00:48:48,010
>> PUBLIK: Vi måste
korsa dem en i taget.

1130
00:48:48,010 --> 00:48:48,760
DAVID MALAN: Ja.

1131
00:48:48,760 --> 00:48:50,260
Vi måste korsa dem en i taget.

1132
00:48:50,260 --> 00:48:53,860
Vet du vad, vi gav upp denna super
praktisk funktion av hakparentes

1133
00:48:53,860 --> 00:48:57,240
notation, mer korrekt
känd som random access,

1134
00:48:57,240 --> 00:48:59,280
där vi bara kan hoppa
till ett enskilt element

1135
00:48:59,280 --> 00:49:01,470
men nu om jag fortfarande hade
mina volontärer här,

1136
00:49:01,470 --> 00:49:04,660
om jag ville hitta
nummer 22, jag kan inte bara

1137
00:49:04,660 --> 00:49:06,620
hoppa till konsolen något något.

1138
00:49:06,620 --> 00:49:10,530
Jag måste se över listan, mycket
som våra Söka exempel linjärt,

1139
00:49:10,530 --> 00:49:12,260
att hitta numret 22.

1140
00:49:12,260 --> 00:49:14,340
Så vi tycks ha betalat ett pris där.

1141
00:49:14,340 --> 00:49:16,430
Men vi kan ändå
lösa andra problem.

1142
00:49:16,430 --> 00:49:18,587
>> I själva verket, låt mig presentera
bara ett par bilder.

1143
00:49:18,587 --> 00:49:20,920
Så om du har varit ner till
Mathers Dining Hall nyligen,

1144
00:49:20,920 --> 00:49:23,320
du ihåg att deras
staplar av tråg som denna,

1145
00:49:23,320 --> 00:49:26,300
vi lånat dessa från
Annenberg innan klassen.

1146
00:49:26,300 --> 00:49:28,930
Så här stapeln av brickor, dock,
är representativ faktiskt

1147
00:49:28,930 --> 00:49:30,860
av en datavetenskap datastruktur.

1148
00:49:30,860 --> 00:49:32,910
Det finns en datastruktur
i datavetenskap

1149
00:49:32,910 --> 00:49:38,010
känd som en stapel som mycket snyggt
lämpar sig för just denna visuella.

1150
00:49:38,010 --> 00:49:41,380
Så om vart och ett av dessa fack är inte en
fack men som ett nummer och jag ville

1151
00:49:41,380 --> 00:49:45,010
att lagra siffror, jag
skulle kunna sätta en här nere,

1152
00:49:45,010 --> 00:49:48,320
och jag kunde sätta en annan här nere,
och fortsätter att stapla siffror

1153
00:49:48,320 --> 00:49:53,180
ovanpå varandra, och vad som är
potentiellt användbart om detta

1154
00:49:53,180 --> 00:49:55,450
är att det är underförstått
av denna datastruktur?

1155
00:49:55,450 --> 00:49:58,045
Vilka nummer kan jag dra ut
först lämpligast?

1156
00:49:58,045 --> 00:50:00,640

1157
00:50:00,640 --> 00:50:03,030
Den senast ett sätta på det.

1158
00:50:03,030 --> 00:50:06,430
>> Så det här är vad vi skulle kalla in
datavetenskap en LIFO datastruktur.

1159
00:50:06,430 --> 00:50:08,070
Sist in, först ut.

1160
00:50:08,070 --> 00:50:10,800
Och vi får se snart varför
som kan vara användbara, men för nu,

1161
00:50:10,800 --> 00:50:12,200
bara betrakta fastigheten.

1162
00:50:12,200 --> 00:50:15,158
Och det är typ av dum om du tror
om hur matsalen gör det.

1163
00:50:15,158 --> 00:50:17,910
Varje gång de rena fack och
sätta de färskaste som på toppen,

1164
00:50:17,910 --> 00:50:22,160
du kan ha en tidigare ren
men så småningom mycket smutsiga och dammiga

1165
00:50:22,160 --> 00:50:24,360
fack längst ner
om du aldrig faktiskt

1166
00:50:24,360 --> 00:50:26,820
gå till botten av det
stack, eftersom du bara

1167
00:50:26,820 --> 00:50:29,380
hålla sätta nya och
de rena ovanpå det.

1168
00:50:29,380 --> 00:50:31,840
Samma sak kan hända
i en stormarknad också.

1169
00:50:31,840 --> 00:50:35,450
Om du har en monter
av mjölk och varje gång CVS

1170
00:50:35,450 --> 00:50:37,610
eller vem blir mer mjölk,
du bara shove mjölk

1171
00:50:37,610 --> 00:50:39,880
du redan har på baksidan och
du sätter de nya framsidan,

1172
00:50:39,880 --> 00:50:43,088
du kommer att ha några ganska otäck
mjölk i slutet av datastrukturen,

1173
00:50:43,088 --> 00:50:46,390
eftersom det alltid är i botten eller
ekvivalent det är alltid längst bak.

1174
00:50:46,390 --> 00:50:50,407
>> Men det finns ett annat sätt att tänka på
rada upp data och till exempel, detta.

1175
00:50:50,407 --> 00:50:53,490
Om du är en av dem som gillar
att rada upp utanför Apples butiker

1176
00:50:53,490 --> 00:50:55,610
när en ny produkt kommer
ut, är du förmodligen

1177
00:50:55,610 --> 00:50:58,780
inte använder en bunt uppgifter
struktur eftersom du

1178
00:50:58,780 --> 00:51:03,070
skulle stöta bort alla andra som är
kö för att köpa några nya leksak.

1179
00:51:03,070 --> 00:51:06,610
Snarare är du antagligen att använda
vilken typ av datastruktur

1180
00:51:06,610 --> 00:51:10,050
eller vilken typ av system
i den verkliga världen?

1181
00:51:10,050 --> 00:51:13,493
Förhoppningsvis är det en linje, eller mer
korrekt eller mer brittisk-liknande, en kö.

1182
00:51:13,493 --> 00:51:17,700
Och det visar sig en kö är också en
datastruktur i datavetenskap,

1183
00:51:17,700 --> 00:51:19,700
men en kö har en mycket
annan egenskap.

1184
00:51:19,700 --> 00:51:20,820
Det är inte LIFO.

1185
00:51:20,820 --> 00:51:21,990
Sist in, först ut.

1186
00:51:21,990 --> 00:51:22,800
Gud förbjude.

1187
00:51:22,800 --> 00:51:24,280
Det är i stället FIFO.

1188
00:51:24,280 --> 00:51:26,110
Först in först ut.

1189
00:51:26,110 --> 00:51:27,970
Och det är en bra sak
för rättvisa skull

1190
00:51:27,970 --> 00:51:30,428
säkert när du foder
upp super tidigt på morgonen.

1191
00:51:30,428 --> 00:51:33,400
Om du får det första, du
vill komma ut först också.

1192
00:51:33,400 --> 00:51:35,880
>> Och så alla dessa uppgifter
strukturer, köer och travar

1193
00:51:35,880 --> 00:51:39,220
och klasar av andra, visar sig att du
kan tänka på detta som bara en array.

1194
00:51:39,220 --> 00:51:41,820
Detta är en array, kanske
en fast storlek 4, men det skulle

1195
00:51:41,820 --> 00:51:44,990
vara typ av trevligt om vi bara kunde stapla
brickor nästan oändligt högt om vi

1196
00:51:44,990 --> 00:51:46,780
ha så många brickor eller siffror.

1197
00:51:46,780 --> 00:51:48,840
Så kanske vi vill
använder en länkad lista här,

1198
00:51:48,840 --> 00:51:51,800
men en kompromiss kommer att vara
potentiellt att vi behöver mer minne,

1199
00:51:51,800 --> 00:51:55,930
tar lite mer tid, men vi
begränsar inte höjden på stapeln,

1200
00:51:55,930 --> 00:51:59,550
ungefär som Mather: s monter
kan begränsa storleken på stapeln,

1201
00:51:59,550 --> 00:52:03,117
och så dessa är designbeslut eller
alternativ för oss i slutändan.

1202
00:52:03,117 --> 00:52:04,950
Så med dessa uppgifter
strukturer, har vi börjat

1203
00:52:04,950 --> 00:52:09,360
se nya övre gränser potentiellt
på det som tidigare var supersnabb

1204
00:52:09,360 --> 00:52:11,260
och där vi lämnar
ledig idag och där

1205
00:52:11,260 --> 00:52:13,200
vi hoppas att få
är på onsdag, vi ska

1206
00:52:13,200 --> 00:52:15,740
börja titta på en data
struktur som låter oss söka

1207
00:52:15,740 --> 00:52:18,260
genom uppgifter i logg sluttid igen.

1208
00:52:18,260 --> 00:52:21,470
Och vi såg det, minns vecka noll
och en med binär sökning eller dela

1209
00:52:21,470 --> 00:52:22,180
och erövra.

1210
00:52:22,180 --> 00:52:26,240
Det kommer tillbaka och ännu bättre,
den heliga graal för denna onsdag

1211
00:52:26,240 --> 00:52:29,510
kommer att vara att komma med
datastruktur som löper riktigt

1212
00:52:29,510 --> 00:52:32,070
eller teoretiskt i
konstant tid, varigenom

1213
00:52:32,070 --> 00:52:34,760
det spelar ingen roll hur många
miljoner eller miljarder saker

1214
00:52:34,760 --> 00:52:38,470
Vi har i datastrukturen, kommer det
ta oss konstant tid, kanske ett steg

1215
00:52:38,470 --> 00:52:41,387
eller två steg eller 10 steg,
men konstant antal steg

1216
00:52:41,387 --> 00:52:42,970
att söka igenom den datastruktur.

1217
00:52:42,970 --> 00:52:46,300
Det verkligen kommer att vara den heliga graal
men mer om det på onsdag.

1218
00:52:46,300 --> 00:52:49,045
Se ya då.

1219
00:52:49,045 --> 00:52:53,704
>> [MUSIK SPELA]

1220
00:52:53,704 --> 00:56:08,448