1
00:00:00,000 --> 00:00:03,381
>> [Musik spiller]

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

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

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

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

6
00:00:14,380 --> 00:00:17,182
>> -Jeg ved ikke.

7
00:00:17,182 --> 00:00:19,990
>> -Så Hvad ved vi?

8
00:00:19,990 --> 00:00:23,145
>> -at På 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å spørgsmålet er, hvad
lavede han ved 9:16?

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

12
00:00:29,720 --> 00:00:31,540
Måske så han snigskytte.

13
00:00:31,540 --> 00:00:33,412
>> -Eller Arbejdede med ham.

14
00:00:33,412 --> 00:00:34,340
>> -Wait.

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

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

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

18
00:00:44,400 --> 00:00:47,805
>> -Bringe Hans ansigt op fuld skærm.

19
00:00:47,805 --> 00:00:48,680
>> -His Briller.

20
00:00:48,680 --> 00:00:50,060
>> -Der Er en refleksion.

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

22
00:01:00,455 --> 00:01:02,280
>> -Det Er den Nuevitas baseball hold.

23
00:01:02,280 --> 00:01:03,110
Det er deres logo.

24
00:01:03,110 --> 00:01:05,820
>> -Og Han taler til
hvem iført denne jakke.

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

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

27
00:01:07,628 --> 00:01:11,210
Dette er CS50 og dette er en smule mere
af [uhørligt], som du er

28
00:01:11,210 --> 00:01:12,890
dypning med problemet sæt fire.

29
00:01:12,890 --> 00:01:16,606
I dag begynder vi at se lidt mere
dybt på disse ting kaldet pointere,

30
00:01:16,606 --> 00:01:18,480
som selv om det er
en temmelig mystisk emne,

31
00:01:18,480 --> 00:01:20,813
det viser sig, at det vil
at være det middel, hvorved vi

32
00:01:20,813 --> 00:01:24,320
kan begynde at bygge og samle
meget mere sofistikerede programmer.

33
00:01:24,320 --> 00:01:28,150
Men vi gjorde det på sidste onsdag
ved hjælp af nogle claymation først.

34
00:01:28,150 --> 00:01:30,190
Så dette, tilbagekaldelse, er
Binky og vi brugte ham

35
00:01:30,190 --> 00:01:33,148
at tage et kig på et program,
ikke rigtig gøre noget interessant,

36
00:01:33,148 --> 00:01:34,950
men det gjorde afslører et par problemer.

37
00:01:34,950 --> 00:01:38,570
Så at begynde i dag, hvorfor vi ikke gå
hurtigt gennem et par af disse trin,

38
00:01:38,570 --> 00:01:41,920
forsøge at destillere i humane vilkår
præcis, hvad der foregår her

39
00:01:41,920 --> 00:01:45,410
og hvorfor det er dårligt, og derefter gå videre
og faktisk begynde at bygge noget

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

41
00:01:46,309 --> 00:01:48,350
Så disse var de første
to linjer i dette program

42
00:01:48,350 --> 00:01:51,340
og i lægmandssprog, hvad
er disse to linjer gør?

43
00:01:51,340 --> 00:01:55,600
Nogen, der er nogenlunde komfortabel
med, hvad der er angivet på skærmen?

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

45
00:01:58,340 --> 00:02:00,120
Hvad er disse to linjer gør?

46
00:02:00,120 --> 00:02:02,070
Det er ikke alt,
forskellig fra uge en,

47
00:02:02,070 --> 00:02:03,611
men der er nogle nye særlige symbol.

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

49
00:02:04,152 --> 00:02:05,628
Tilbage dertil.

50
00:02:05,628 --> 00:02:07,092
>> PUBLIKUM: Erklæring af pointers?

51
00:02:07,092 --> 00:02:08,050
DAVID MALAN: Sig igen?

52
00:02:08,050 --> 00:02:08,860
PUBLIKUM: Erklæring af pointers?

53
00:02:08,860 --> 00:02:11,776
DAVID MALAN: Erklæring af pointere og
lad os forfine det en lille smule mere.

54
00:02:11,776 --> 00:02:14,050
PUBLIKUM: [uhørligt]
adresse x- og y derefter.

55
00:02:14,050 --> 00:02:15,300
DAVID MALAN: Og så tage fat.

56
00:02:15,300 --> 00:02:18,550
Så specifikt, hvad vi laver
er vi erklærer to variabler.

57
00:02:18,550 --> 00:02:21,252
Disse variabler, selv om, vil
at være af typen int stjerne, som

58
00:02:21,252 --> 00:02:23,210
mere specifikt betyder
de kommer til at gemme

59
00:02:23,210 --> 00:02:26,450
adressen på en int,
henholdsvis x og y.

60
00:02:26,450 --> 00:02:27,660
Nu er der nogen værdier?

61
00:02:27,660 --> 00:02:32,621
Er der nogen konkrete adresser i disse
to variabler på dette tidspunkt?

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

63
00:02:33,120 --> 00:02:35,030
Det er bare såkaldt skrald værdier.

64
00:02:35,030 --> 00:02:38,120
Hvis du faktisk ikke tildele en
variabel, hvad der var i RAM

65
00:02:38,120 --> 00:02:42,224
tidligere kommer til at fylde med nuller
og dem begge af disse variabler.

66
00:02:42,224 --> 00:02:44,140
Men vi ved endnu ikke,
hvad de er, og det er

67
00:02:44,140 --> 00:02:47,060
vil være nøglen til, hvorfor Binky
tabte hovedet i sidste uge.

68
00:02:47,060 --> 00:02:49,980
>> Så dette var claymation
inkarnation af denne

69
00:02:49,980 --> 00:02:53,580
hvorved du har kun to variabler,
små cirkulære stykker af ler,

70
00:02:53,580 --> 00:02:57,330
der kan lagre variabler, men som
de pakket ind pile antyder,

71
00:02:57,330 --> 00:03:00,640
de er faktisk ikke peger
til alle steder kendt.

72
00:03:00,640 --> 00:03:03,670
Så vi havde derefter denne linje, og det
var nyt i sidste uge, malloc til hukommelse

73
00:03:03,670 --> 00:03:07,130
fordeling, som er blot en fancy måde
at fortælle operativsystemet, Linux

74
00:03:07,130 --> 00:03:09,750
eller Mac OS eller Windows,
hey, giv mig noget hukommelse,

75
00:03:09,750 --> 00:03:11,780
og alt hvad du nødt til at fortælle
operativsystemet

76
00:03:11,780 --> 00:03:14,699
er hvad når beder det for hukommelsen.

77
00:03:14,699 --> 00:03:16,990
Det kommer ikke til at pleje hvad
du kommer til at gøre med det,

78
00:03:16,990 --> 00:03:19,786
men du behøver at fortælle operativsystemet
Systemet hvad ved hjælp af malloc.

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

80
00:03:20,286 --> 00:03:21,078
>> PUBLIKUM: Hvor meget?

81
00:03:21,078 --> 00:03:21,994
DAVID MALAN: Hvor meget?

82
00:03:21,994 --> 00:03:25,280
Hvor meget i bytes, og så det igen,
en konstrueret eksempel er bare at sige,

83
00:03:25,280 --> 00:03:27,360
give mig størrelsen på en int.

84
00:03:27,360 --> 00:03:30,550
Nu, størrelsen af ​​en int
er fire byte eller 32 bit.

85
00:03:30,550 --> 00:03:32,850
Så dette er bare en måde at
sige, hey, operativsystem,

86
00:03:32,850 --> 00:03:37,290
give mig fire bytes hukommelse
at jeg kan bruge til min rådighed,

87
00:03:37,290 --> 00:03:40,560
og specifikt, hvad betyder
malloc vende tilbage med respekt

88
00:03:40,560 --> 00:03:41,795
denne bid af fire bytes?

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

90
00:03:44,110 --> 00:03:44,860
PUBLIKUM: Adresse?

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

92
00:03:45,901 --> 00:03:47,580
Adressen på den luns af fire bytes.

93
00:03:47,580 --> 00:03:48,190
Præcis.

94
00:03:48,190 --> 00:03:51,430
Og så det er, hvad der er gemt i sidste ende
i x- og det er derfor vi ikke rigtig

95
00:03:51,430 --> 00:03:55,240
pleje hvad antallet af denne
adresse er, uanset om det er OX1 eller OX2

96
00:03:55,240 --> 00:03:57,110
eller nogle kryptiske hexadecimal adresse.

97
00:03:57,110 --> 00:03:59,850
Vi har lige pleje billedligt
at denne variabel X er nu

98
00:03:59,850 --> 00:04:01,630
peger på, at bid af hukommelse.

99
00:04:01,630 --> 00:04:05,570
Så pilen repræsenterer en pegepind eller
mere specifikt en hukommelsesadresse.

100
00:04:05,570 --> 00:04:09,120
Men igen, vi typisk ikke ligeglad
hvad disse faktiske adresser er.

101
00:04:09,120 --> 00:04:11,780
Nu denne linje siger
hvad i lægmandssprog?

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

103
00:04:14,330 --> 00:04:17,390
Hvad betyder det?

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

105
00:04:18,200 --> 00:04:20,102
Undgå at ridse din hals.

106
00:04:20,102 --> 00:04:22,360
>> PUBLIKUM: Adressen på x er på 42.

107
00:04:22,360 --> 00:04:24,300
>> DAVID MALAN: Adressen på x er på 42.

108
00:04:24,300 --> 00:04:25,190
Ikke helt.

109
00:04:25,190 --> 00:04:28,485
Så tæt, men ikke helt, fordi der er
stjernen, der er forudfastsætte denne x.

110
00:04:28,485 --> 00:04:29,860
Så vi er nødt til at nappe en lille smule.

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

112
00:04:31,032 --> 00:04:36,044
>> PUBLIKUM: Den værdi, som
pointer x peger på, er 42.

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

114
00:04:36,710 --> 00:04:40,840
Den værdi, markøren x er
peger på, lad os sige, er 42,

115
00:04:40,840 --> 00:04:44,165
eller sagt på en anden måde, stjernen
x siger, gå til uanset adresse

116
00:04:44,165 --> 00:04:48,340
er i x, uanset om det er en Oxford
Street eller 33 Oxford Street

117
00:04:48,340 --> 00:04:51,850
eller OX1 eller OX33, uanset
at numerisk adresse er,

118
00:04:51,850 --> 00:04:54,380
stjerne x er dereferere af x.

119
00:04:54,380 --> 00:04:57,297
Så gå til denne adresse og
derefter sætte nummer 42 der.

120
00:04:57,297 --> 00:04:59,380
Så det ville være et
tilsvarende måde at sige det.

121
00:04:59,380 --> 00:05:01,860
Så det er alt fint og derefter
Vi ville repræsentere billedet

122
00:05:01,860 --> 00:05:05,370
som følger, hvor vi har tilføjet
42 til denne bid af fire

123
00:05:05,370 --> 00:05:09,370
bytes i højre side, men
denne linje var, hvor tingene gik galt

124
00:05:09,370 --> 00:05:11,120
og Binky hoved dukkede
ud på dette tidspunkt,

125
00:05:11,120 --> 00:05:15,290
fordi dårlige ting ske, når
du dereference skrald værdier

126
00:05:15,290 --> 00:05:18,210
eller du dereference ugyldig
pointere, og jeg siger ugyldig

127
00:05:18,210 --> 00:05:21,020
fordi der på dette tidspunkt i
historie, hvad der er inde for y?

128
00:05:21,020 --> 00:05:24,440
Hvad er værdien af ​​y baseret
på de sidste par skridt?

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

130
00:05:25,360 --> 00:05:26,115
Hvad er det?

131
00:05:26,115 --> 00:05:26,990
>> PUBLIKUM: En adresse.

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

133
00:05:28,460 --> 00:05:31,910
Det bør være en adresse
men jeg har initialiseret det?

134
00:05:31,910 --> 00:05:32,800
Så jeg har ikke endnu.

135
00:05:32,800 --> 00:05:35,430
Så hvad der er kendt for at være derinde?

136
00:05:35,430 --> 00:05:37,590
Det er blot nogle skrald værdi.

137
00:05:37,590 --> 00:05:41,500
Det kunne være en hvilken som helst adresse fra nul til
2 milliarder, hvis du har to gigs RAM,

138
00:05:41,500 --> 00:05:44,289
eller nul til 4 milliarder, hvis du har
fik fire gigabyte RAM.

139
00:05:44,289 --> 00:05:46,080
Det er nogle skrald værdi,
men problemet er

140
00:05:46,080 --> 00:05:48,200
at operativsystemet,
hvis det ikke har givet dig

141
00:05:48,200 --> 00:05:51,140
at chunk hukommelse specifikt
at du forsøger at gå til,

142
00:05:51,140 --> 00:05:54,650
Det er generelt kommer til at forårsage, hvad
vi har set som en segmentering fejl.

143
00:05:54,650 --> 00:05:57,810
Så i virkeligheden, nogen af ​​jer, der har
kæmpede på problemer på kontortid

144
00:05:57,810 --> 00:06:00,393
eller problemer, der er mere
generelt med at forsøge at finde ud af

145
00:06:00,393 --> 00:06:02,150
en segmentering fejl,
der generelt betyder

146
00:06:02,150 --> 00:06:05,017
du rører et segment af
hukommelse, som du ikke skal være.

147
00:06:05,017 --> 00:06:07,350
Du rører hukommelse,
operativsystemet har ikke

148
00:06:07,350 --> 00:06:10,450
tillod dig at røre ved, om det er
ved at gå for vidt i dit array

149
00:06:10,450 --> 00:06:12,870
eller starte nu, uanset om
det er fordi du rører

150
00:06:12,870 --> 00:06:14,780
hukommelse, der bare er en vis skrald værdi.

151
00:06:14,780 --> 00:06:18,230
>> Så laver stjerne x her er
slags udefineret adfærd.

152
00:06:18,230 --> 00:06:22,030
Du bør aldrig gøre det, fordi odds
er, er programmet bare at gå ned,

153
00:06:22,030 --> 00:06:24,050
fordi du siger,
gå til denne adresse

154
00:06:24,050 --> 00:06:27,000
og du har ingen idé om, hvor
at adressen rent faktisk er.

155
00:06:27,000 --> 00:06:30,300
Så styresystemet sandsynligvis
kommer til at gå ned dit program

156
00:06:30,300 --> 00:06:33,840
som et resultat, og ja, det er
hvad skete der for at Binky.

157
00:06:33,840 --> 00:06:37,210
Så i sidste ende, Binky fast
dette problem med dette.

158
00:06:37,210 --> 00:06:38,909
Så selve programmet var behæftet med fejl.

159
00:06:38,909 --> 00:06:41,450
Men hvis du slags gå videre
og udføre denne linje i stedet,

160
00:06:41,450 --> 00:06:45,580
y er lig med x betyder blot, hvad
adresse er en x, også sætte det i y.

161
00:06:45,580 --> 00:06:48,740
>> Og så billedligt, vi har
repræsenterede dette med to pile

162
00:06:48,740 --> 00:06:51,570
fra x og y fra peger
til det samme sted.

163
00:06:51,570 --> 00:06:55,760
Så semantisk, x er lig
til y fordi i begge disse

164
00:06:55,760 --> 00:07:00,300
gemmer den samme
adresse, ergo peger på 42,

165
00:07:00,300 --> 00:07:04,910
og nu, når du siger stjerne
y, gå til adressen i y,

166
00:07:04,910 --> 00:07:06,790
dette har en interessant bivirkning.

167
00:07:06,790 --> 00:07:10,320
Så adressen i y er
samme som adressen i x.

168
00:07:10,320 --> 00:07:15,060
Så hvis du siger gå til adressen
i y og ændre værdien til 13,

169
00:07:15,060 --> 00:07:17,140
hvem der ellers er påvirket?

170
00:07:17,140 --> 00:07:21,100
X er, punkt D, så at sige,
bør blive påvirket så godt.

171
00:07:21,100 --> 00:07:24,340
>> Og ja, hvordan Nick tegnede dette billede
i claymation var præcis det.

172
00:07:24,340 --> 00:07:28,665
Selvom vi følger markøren
y, endte vi på samme sted,

173
00:07:28,665 --> 00:07:32,780
og så hvis vi var til at udskrive
ud x eller y s pointee,

174
00:07:32,780 --> 00:07:35,720
så ville vi se værdien af ​​13.

175
00:07:35,720 --> 00:07:37,927
Nu siger jeg pointee at være
overensstemmelse med videoen.

176
00:07:37,927 --> 00:07:39,760
Programmører, til min
viden, faktisk aldrig

177
00:07:39,760 --> 00:07:42,460
sige ordet pointee,
det, der er tilspidset

178
00:07:42,460 --> 00:07:44,650
på, men for konsekvens
med videoen, indser

179
00:07:44,650 --> 00:07:47,520
det er alt, der var
betød i denne situation.

180
00:07:47,520 --> 00:07:54,190
Så spørgsmål om claymation
eller henvisninger eller malloc bare endnu?

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

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

183
00:07:55,470 --> 00:07:58,560
>> Så uden yderligere
ståhej, lad os tage et kig

184
00:07:58,560 --> 00:08:00,700
på, hvor det har faktisk
været brugt i nogen tid.

185
00:08:00,700 --> 00:08:03,580
Så vi har haft denne CS50 bibliotek
der har fået alle disse funktioner.

186
00:08:03,580 --> 00:08:06,810
Vi har brugt GetInt en masse, getString,
sandsynligvis GetLongLong tidligere

187
00:08:06,810 --> 00:08:09,840
i min pset én eller deromkring, men
hvad der rent faktisk er foregået?

188
00:08:09,840 --> 00:08:12,920
Nå, lad os tage et hurtigt kig
under emhætten på et program, der

189
00:08:12,920 --> 00:08:17,017
inspirerer hvorfor vi give dig den CS50
bibliotek, og faktisk fra sidste uge,

190
00:08:17,017 --> 00:08:18,850
Vi begyndte at tage dem
uddannelse hjul off.

191
00:08:18,850 --> 00:08:21,080
Så dette er nu sorteres
en postmortem af, hvad

192
00:08:21,080 --> 00:08:23,690
har stået på
inde i CS50 bibliotek,

193
00:08:23,690 --> 00:08:27,250
selv om vi nu vil begynde at bevæge
væk fra det for de fleste programmer.

194
00:08:27,250 --> 00:08:29,460
>> Så dette er et program kaldet scanf 0.

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

196
00:08:30,510 --> 00:08:33,909
Det bare har disse linjer, men det
introducerer en funktion kaldet scanf

197
00:08:33,909 --> 00:08:36,909
at vi faktisk kommer til at se i
et øjeblik inde i CS50 bibliotek,

198
00:08:36,909 --> 00:08:38,600
omend i en lidt anderledes form.

199
00:08:38,600 --> 00:08:41,330
Så dette program på linje 16
er at erklære en variabel x.

200
00:08:41,330 --> 00:08:43,150
Så giv mig fire byte for en int.

201
00:08:43,150 --> 00:08:45,750
Det er blevet fortalt bruger,
nummer bedes, og derefter

202
00:08:45,750 --> 00:08:49,010
Dette er en interessant linje,
faktisk binder sidste uge

203
00:08:49,010 --> 00:08:49,790
og dette.

204
00:08:49,790 --> 00:08:53,230
Scanf, og derefter mærke til det tager en
string-format, ligesom printf,

205
00:08:53,230 --> 00:08:57,480
% Jeg betyder en int, og så det tager en
andet argument, der ser lidt

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

207
00:08:58,260 --> 00:09:01,880
Det er tegnet x, og til at huske,
vi så kun denne ene gang i sidste uge.

208
00:09:01,880 --> 00:09:03,465
Hvad betyder tegnet x repræsenterer?

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

210
00:09:06,210 --> 00:09:08,450
Hvad betyder tegnet gøre i C?

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

212
00:09:08,950 --> 00:09:10,024
>> PUBLIKUM: Adressen på.

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

214
00:09:11,190 --> 00:09:13,190
Så det er det modsatte
af stjernen operatøren,

215
00:09:13,190 --> 00:09:17,270
mens stjernen operatøren siger, gå til
denne adresse, den tegnet operatør

216
00:09:17,270 --> 00:09:20,280
siger, finde ud af
adresse på denne variabel,

217
00:09:20,280 --> 00:09:23,530
og så dette er nøglen, fordi
scanf formål i livet

218
00:09:23,530 --> 00:09:26,320
er at scanne brugerens
input fra tastaturet,

219
00:09:26,320 --> 00:09:29,970
afhængig af hvad han eller hun
typer, og derefter læse, at brugerens input

220
00:09:29,970 --> 00:09:32,970
i en variabel, men vi
så i de seneste to uger

221
00:09:32,970 --> 00:09:36,080
at denne swap funktionen vi
forsøgt ubesværet at gennemføre

222
00:09:36,080 --> 00:09:37,110
var blot brudt.

223
00:09:37,110 --> 00:09:42,470
Husk på, at med swap-funktion,
hvis vi bare erklærede A og B som ints,

224
00:09:42,470 --> 00:09:47,040
vi med held skifte
to variable inde i swap

225
00:09:47,040 --> 00:09:50,080
ligesom med mælken og EFT,
men så snart swap vendte tilbage,

226
00:09:50,080 --> 00:09:55,200
hvad var resultatet med hensyn
til x og y, de oprindelige værdier?

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

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

229
00:09:56,200 --> 00:09:59,754
Intet skete dengang, fordi
swaps ændrer kun dens lokale kopier,

230
00:09:59,754 --> 00:10:01,670
hvilket vil sige, alle
denne gang, når vi har

231
00:10:01,670 --> 00:10:04,010
blevet passerer argumenter
til funktioner, vi er

232
00:10:04,010 --> 00:10:05,939
blot passerer kopier af disse argumenter.

233
00:10:05,939 --> 00:10:07,980
Du kan gøre med det
hvad du vil med dem,

234
00:10:07,980 --> 00:10:10,890
men de kommer til at have nogen
effekt på de oprindelige værdier.

235
00:10:10,890 --> 00:10:13,650
Så dette er problematisk, hvis du
ønsker at have en funktion som scanf

236
00:10:13,650 --> 00:10:17,170
i livet, er hvis formål til at scanne
brugerens input fra tastaturet

237
00:10:17,170 --> 00:10:22,010
og derefter udfylde de tomme felter, så at
tale, dvs. give en variabel som x

238
00:10:22,010 --> 00:10:25,410
en værdi, fordi hvis jeg var
til bare passere x for at scanf,

239
00:10:25,410 --> 00:10:28,790
hvis du overveje logikken i sidste
uge, kan scanf gøre, hvad det vil

240
00:10:28,790 --> 00:10:33,100
med en kopi af x, men det ikke kunne
permanent ændre x medmindre vi giver

241
00:10:33,100 --> 00:10:37,120
scanf et skattekort, så at sige,
hvor x markerer stedet, hvor

242
00:10:37,120 --> 00:10:41,860
vi passerer i adressen for x, så
scanf kan gå der og faktisk forandring

243
00:10:41,860 --> 00:10:42,920
værdien af ​​x.

244
00:10:42,920 --> 00:10:45,080
Og så ja, alt
at dette program gør

245
00:10:45,080 --> 00:10:53,180
hvis jeg laver scanf 0, i min kilde
5m bibliotek, gør scanf 0,

246
00:10:53,180 --> 00:10:57,730
dot skråstreg scanf, nummer
venligst 50, tak for 50.

247
00:10:57,730 --> 00:11:01,020
>> Så det er ikke alt, interessant,
men hvad der faktisk sker

248
00:11:01,020 --> 00:11:04,820
er, at så snart jeg kalder
scanf her, værdien af ​​x

249
00:11:04,820 --> 00:11:06,410
bliver permanent ændret.

250
00:11:06,410 --> 00:11:08,335
Nu, dette synes nice og
godt, og i virkeligheden er det

251
00:11:08,335 --> 00:11:11,200
ser ud som vi ikke virkelig har brug for
det CS50 biblioteket på alle længere.

252
00:11:11,200 --> 00:11:13,960
For eksempel, lad os køre
dette endnu en gang her.

253
00:11:13,960 --> 00:11:15,750
Lad mig genåbne det for en anden.

254
00:11:15,750 --> 00:11:20,600
Lad os prøve en række venligst og
stedet for at sige 50 som før,

255
00:11:20,600 --> 00:11:22,810
lad os bare sige nej.

256
00:11:22,810 --> 00:11:24,000
OK, det er lidt underligt.

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

258
00:11:25,270 --> 00:11:28,680
Og blot nogle vrøvl her.

259
00:11:28,680 --> 00:11:31,170
Så det synes ikke at
håndtere fejlagtige situationer.

260
00:11:31,170 --> 00:11:33,620
Så vi er nødt til minimalt starten
tilføje nogle fejl-kontrol

261
00:11:33,620 --> 00:11:37,460
for at sikre, at brugeren har
skrevet i en faktiske tal som 50,

262
00:11:37,460 --> 00:11:40,720
fordi tilsyneladende skrive ord
genkendes ikke som problematisk,

263
00:11:40,720 --> 00:11:42,020
men det burde nok være.

264
00:11:42,020 --> 00:11:46,450
>> Lad os se på denne version nu, er
mit forsøg på at reimplement getString.

265
00:11:46,450 --> 00:11:48,437
Hvis scanf har alt dette
funktionalitet indbygget,

266
00:11:48,437 --> 00:11:51,270
hvorfor har vi været dypning med disse
uddannelse hjul som getString?

267
00:11:51,270 --> 00:11:55,450
Nå, her er måske min egen
simpel version af getString

268
00:11:55,450 --> 00:12:00,766
hvorved en uge siden, kunne jeg have sagt,
give mig en snor og kalder det buffer.

269
00:12:00,766 --> 00:12:03,390
I dag vil jeg begynde bare
siger char stjerne, som, tilbagekaldelse,

270
00:12:03,390 --> 00:12:04,400
det er bare synonym.

271
00:12:04,400 --> 00:12:06,629
Det ser mere skræmmende, men det er
præcis de samme ting.

272
00:12:06,629 --> 00:12:09,420
Så giv mig en variabel kaldet buffer
der kommer til at gemme en streng,

273
00:12:09,420 --> 00:12:12,780
fortælle brugeren strengen venligst,
og derefter, ligesom før,

274
00:12:12,780 --> 00:12:17,760
lad os prøve at låne denne lektion scanf
% s denne gang, og derefter sende i buffer.

275
00:12:17,760 --> 00:12:19,310
Nu en hurtig sanity check.

276
00:12:19,310 --> 00:12:22,120
Hvorfor bliver jeg siger ikke
tegnet buffer denne gang?

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

278
00:12:25,190 --> 00:12:26,625
Udlede det foregående eksempel.

279
00:12:26,625 --> 00:12:28,000
PUBLIKUM: Char stjerne er en pointer.

280
00:12:28,000 --> 00:12:29,920
DAVID MALAN: Præcis,
fordi denne gang, char

281
00:12:29,920 --> 00:12:34,080
stjerne er allerede en pegepind, en adresse,
definition af denne stjerne at være der.

282
00:12:34,080 --> 00:12:37,530
Og hvis scanf forventer en adresse,
er det tilstrækkeligt blot at passere i buffer.

283
00:12:37,530 --> 00:12:39,260
Jeg behøver ikke at sige tegnet buffer.

284
00:12:39,260 --> 00:12:42,177
For den nysgerrige, kunne du
gøre noget som dette.

285
00:12:42,177 --> 00:12:43,510
Det ville have forskellig betydning.

286
00:12:43,510 --> 00:12:47,240
Dette vil give dig en pegepind
til en pegepind, som faktisk er

287
00:12:47,240 --> 00:12:50,050
en gyldig ting i C, men for
nu, lad os holde det simpelt

288
00:12:50,050 --> 00:12:51,750
og holde historien konsekvent.

289
00:12:51,750 --> 00:12:54,100
Jeg er bare kommer til at passere i
buffer og det er korrekt.

290
00:12:54,100 --> 00:12:56,487
Problemet er dog dette.

291
00:12:56,487 --> 00:12:58,820
Lad mig gå videre og køre dette
program efter kompilere den.

292
00:12:58,820 --> 00:13:00,902
Gøre scanf 1.

293
00:13:00,902 --> 00:13:02,610
Damn det, min compiler s
fange min fejl.

294
00:13:02,610 --> 00:13:04,090
Giv mig et sekund.

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

296
00:13:05,460 --> 00:13:06,990
Lad os sige 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
Der vi går.

300
00:13:12,720 --> 00:13:14,280
Jeg har brug for det.

301
00:13:14,280 --> 00:13:16,750
CS50-ID har forskellige
konfigurationsindstillinger

302
00:13:16,750 --> 00:13:18,280
at beskytte dig mod dig selv.

303
00:13:18,280 --> 00:13:21,300
Jeg havde brug for at deaktivere dem ved
kører klang manuelt denne gang.

304
00:13:21,300 --> 00:13:22,140
Så snor venligst.

305
00:13:22,140 --> 00:13:25,560
Jeg har tænkt mig at gå videre og skrive
i min favorit hej verden.

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

307
00:13:26,490 --> 00:13:27,700
Det er ikke, hvad jeg har skrevet.

308
00:13:27,700 --> 00:13:29,690
Så det er betegnende for
noget at være forkert.

309
00:13:29,690 --> 00:13:33,920
Lad mig gå videre og skrive
i en virkelig lang snor.

310
00:13:33,920 --> 00:13:37,210
Tak for ugyldig og jeg ved ikke,
hvis jeg har tænkt mig at være i stand til at gå ned den.

311
00:13:37,210 --> 00:13:40,240
Lad os prøve lidt kopi
indsætte og se om det hjælper.

312
00:13:40,240 --> 00:13:43,290
Bare indsæt en masse af dette.

313
00:13:43,290 --> 00:13:47,310
Det er helt sikkert en større
snor end normalt.

314
00:13:47,310 --> 00:13:51,450
Lad os bare virkelig skrive det.

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

316
00:13:51,950 --> 00:13:52,650
For pokker.

317
00:13:52,650 --> 00:13:53,480
Kommando ikke fundet.

318
00:13:53,480 --> 00:13:54,550
Så det er uafhængige.

319
00:13:54,550 --> 00:13:56,440
Det er fordi jeg klistret
nogle dårlige karakterer,

320
00:13:56,440 --> 00:13:59,780
men dette viser sig ikke at gå på arbejde.

321
00:13:59,780 --> 00:14:03,510
>> Lad os prøve denne gang mere, fordi
det er sjovere, hvis vi rent faktisk går ned det.

322
00:14:03,510 --> 00:14:09,116
Lad os skrive dette, og nu er jeg
kommer til at kopiere en virkelig lang snor

323
00:14:09,116 --> 00:14:10,990
og lad os nu se, om vi
kan gå ned denne ting.

324
00:14:10,990 --> 00:14:14,235
Bemærk, jeg udeladt rum og
nye linjer og semikoloner

325
00:14:14,235 --> 00:14:16,035
og alle funky tegn.

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
Og nu netværkets bare at være langsom.

329
00:14:22,880 --> 00:14:27,460
Jeg holdt nede Command-V for længe, ​​tydeligt.

330
00:14:27,460 --> 00:14:28,190
For pokker!

331
00:14:28,190 --> 00:14:29,260
Kommando ikke fundet.

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

333
00:14:29,780 --> 00:14:32,240
Nå, pointen er
alligevel følgende.

334
00:14:32,240 --> 00:14:36,910
Så hvad der rent faktisk sker
på denne erklæring

335
00:14:36,910 --> 00:14:39,240
char stjerne buffer på linie 16?

336
00:14:39,240 --> 00:14:41,820
Så hvad får jeg
når jeg erklærer en pointer?

337
00:14:41,820 --> 00:14:47,440
Alt Jeg får er en fire byte værdi
kaldet buffer, men hvad der er inde i det

338
00:14:47,440 --> 00:14:49,540
i øjeblikket?

339
00:14:49,540 --> 00:14:50,930
Det er blot nogle skrald værdi.

340
00:14:50,930 --> 00:14:54,170
Fordi hver gang du erklære en variabel
i C, det er bare nogle skrald værdi,

341
00:14:54,170 --> 00:14:56,220
og vi er begyndt at
tur over denne virkelighed.

342
00:14:56,220 --> 00:14:59,720
Nu, når jeg fortæller scanf,
gå til denne adresse

343
00:14:59,720 --> 00:15:01,520
og sætte hvad brugeren typer i.

344
00:15:01,520 --> 00:15:06,400
Hvis brugeren skriver i hej
verden, ja, hvor skal jeg sætte det?

345
00:15:06,400 --> 00:15:07,750
Buffer er en skraldespand værdi.

346
00:15:07,750 --> 00:15:11,510
>> Så det er lidt ligesom en pil
der er peger hvem ved hvor.

347
00:15:11,510 --> 00:15:13,880
Måske er det at pege
lige her i min hukommelse.

348
00:15:13,880 --> 00:15:16,560
Og så når brugeren
typer i hello verden,

349
00:15:16,560 --> 00:15:22,380
programmet forsøger at sætte
snor hej verden omvendt skråstreg 0

350
00:15:22,380 --> 00:15:23,910
i denne chunk hukommelse.

351
00:15:23,910 --> 00:15:27,070
Men med stor sandsynlighed, men
tydeligvis ikke 100% sandsynlighed,

352
00:15:27,070 --> 00:15:30,440
computeren vil derefter ned
programmet, fordi det ikke er

353
00:15:30,440 --> 00:15:32,490
hukommelse, jeg skal have lov til at røre ved.

354
00:15:32,490 --> 00:15:36,330
Så kort sagt, dette program er
fejlbehæftet for netop den grund.

355
00:15:36,330 --> 00:15:38,070
Jeg fundamentalt ikke gør hvad?

356
00:15:38,070 --> 00:15:42,366
Hvilke skridt har jeg udeladt, ligesom
vi udeladt med Binky første eksempel?

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

358
00:15:42,866 --> 00:15:43,710
>> PUBLIKUM: tildeling Memory?

359
00:15:43,710 --> 00:15:45,001
>> DAVID MALAN: tildeling Hukommelse.

360
00:15:45,001 --> 00:15:48,400
Jeg har faktisk ikke allokeret
enhver hukommelse til denne streng.

361
00:15:48,400 --> 00:15:50,270
Så vi kan løse dette på et par måder.

362
00:15:50,270 --> 00:15:52,700
En, kan vi holde det simpelt
og i virkeligheden, nu er du

363
00:15:52,700 --> 00:15:55,116
vil begynde at se en sløring
af linjerne mellem, hvad

364
00:15:55,116 --> 00:15:58,520
et array er, hvad en streng er, hvad en
char stjerne er, hvad en række tegn

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

366
00:15:59,020 --> 00:16:02,450
Her er et andet eksempel
involverer strygere og varsel

367
00:16:02,450 --> 00:16:05,690
alt jeg har gjort på nettet
16 er, i stedet for at sige

368
00:16:05,690 --> 00:16:09,530
at bufferen bliver en char
stjerne, en pointer til en klump hukommelse,

369
00:16:09,530 --> 00:16:14,057
Jeg har tænkt mig at meget proaktivt at give
mig selv en buffer til 16 tegn,

370
00:16:14,057 --> 00:16:16,390
og i virkeligheden, hvis du er fortrolig
med udtrykket buffering,

371
00:16:16,390 --> 00:16:20,570
sandsynligvis fra en verden af ​​videoer,
hvor en video er buffering, buffering,

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

373
00:16:21,175 --> 00:16:22,550
Nå, hvad er forbindelsen her?

374
00:16:22,550 --> 00:16:24,960
Nå, Inde i YouTube
og inde i videoafspillere

375
00:16:24,960 --> 00:16:27,200
generelt er en matrix
der er større end 16.

376
00:16:27,200 --> 00:16:30,340
Det kan være en bred vifte af størrelse én
megabyte, måske 10 megabyte,

377
00:16:30,340 --> 00:16:34,330
og ind i den matrix gør din browser
downloade en hel masse bytes,

378
00:16:34,330 --> 00:16:37,500
en hel masse megabyte
video, og video-afspiller,

379
00:16:37,500 --> 00:16:40,930
YouTubes eller hvem er, starter
at læse bytes fra den opstilling,

380
00:16:40,930 --> 00:16:43,530
og hver gang du ser
Ordet buffering, buffering,

381
00:16:43,530 --> 00:16:46,350
det betyder at spilleren har
fået til slutningen af ​​denne array.

382
00:16:46,350 --> 00:16:50,430
Netværket er så langsom, at den ikke har
genopfyldt array med flere byte

383
00:16:50,430 --> 00:16:55,610
og så er du ude af bits
der skal vises til brugeren.

384
00:16:55,610 --> 00:16:59,430
>> Så buffer er en apt sigt her i, at
det er bare et array, en luns af hukommelse.

385
00:16:59,430 --> 00:17:02,530
Og det vil ordne det
fordi det viser sig

386
00:17:02,530 --> 00:17:07,410
at du kan behandle arrays, som om
de er adresser, selvom puffer

387
00:17:07,410 --> 00:17:10,710
er blot et symbol, er det en
sekvens af tegn, buffer,

388
00:17:10,710 --> 00:17:14,760
det er nyttigt for mig, programmøren,
du kan videregive sit navn omkring

389
00:17:14,760 --> 00:17:17,079
som om det var en
pointer, som om det

390
00:17:17,079 --> 00:17:21,000
var adressen på et stykke
hukommelse til 16 tegn.

391
00:17:21,000 --> 00:17:24,530
Så det er at sige, kan jeg videregive
den scanf præcis det ord

392
00:17:24,530 --> 00:17:30,670
og så nu, hvis jeg gør dette program,
gøre scanf 2, dot skråstreg scanf 2,

393
00:17:30,670 --> 00:17:35,386
og skriv hej verden,
Indtast, at time--

394
00:17:35,386 --> 00:17:37,590
>> Hmm, hvad skete der?

395
00:17:37,590 --> 00:17:39,340
String venligst.

396
00:17:39,340 --> 00:17:41,430
Hvad har jeg gjort forkert?

397
00:17:41,430 --> 00:17:43,800
Hello world, buffer.

398
00:17:43,800 --> 00:17:44,705
Hej Verden.

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

400
00:17:48,201 --> 00:17:49,420
Ah, jeg ved, hvad det gør.

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

402
00:17:49,920 --> 00:17:51,628
Så det er at læse op
indtil den første plads.

403
00:17:51,628 --> 00:17:55,680
Så lad os snyde for et øjeblik og
siger jeg ville bare skrive noget

404
00:17:55,680 --> 00:18:01,408
virkelig lang som dette er en lang sætning
det er en, to, tre, fire, fem,

405
00:18:01,408 --> 00:18:04,420
seks, syv, otte, ni,
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 er faktisk en lang sætning.

408
00:18:07,600 --> 00:18:10,710
Så denne sætning er
længere end 16 tegn

409
00:18:10,710 --> 00:18:13,670
og så når jeg ramte Enter,
hvad der kommer til at ske?

410
00:18:13,670 --> 00:18:16,940
Nå, i dette tilfælde af
historie, jeg havde erklæret buffer

411
00:18:16,940 --> 00:18:22,190
til faktisk at være et array
med 16 tegn klar til at gå.

412
00:18:22,190 --> 00:18:27,426
Så en, to, tre, fire, fem, seks,
syv, otte, ni, 10, 11, 12, 13, 14,

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

414
00:18:29,440 --> 00:18:34,410
Så 16 tegn, og nu, hvor jeg
læst i noget som dette er en lang

415
00:18:34,410 --> 00:18:43,950
sætning, hvad der kommer til at ske er
at jeg har tænkt mig at læse i dette er en lang

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

417
00:18:49,660 --> 00:18:52,270
>> Så det er bevidst
en dårlig ting, som jeg

418
00:18:52,270 --> 00:18:55,060
holde skrive over det
grænserne for min array,

419
00:18:55,060 --> 00:18:56,660
ud over grænserne for min buffer.

420
00:18:56,660 --> 00:19:00,100
Jeg kunne få heldige og programmet
vil holde på kører og er ligeglad,

421
00:19:00,100 --> 00:19:03,450
men generelt er dette
vil faktisk gå ned mit program,

422
00:19:03,450 --> 00:19:06,440
og det er en fejl i min
kode det øjeblik jeg træder

423
00:19:06,440 --> 00:19:08,576
ud over grænserne
af denne array, fordi jeg

424
00:19:08,576 --> 00:19:10,450
ved ikke, om det er
nødvendigvis kommer til at gå ned

425
00:19:10,450 --> 00:19:12,120
eller hvis jeg bare kommer til at få heldige.

426
00:19:12,120 --> 00:19:15,750
Så dette er problematisk, fordi i
dette tilfælde betyder det ud til at virke

427
00:19:15,750 --> 00:19:20,931
og lad os friste skæbnen her, selvom
IDE synes at tolerere en hel

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

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

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

431
00:19:23,240 --> 00:19:26,470
Så jeg er den eneste, der kan se dette.

432
00:19:26,470 --> 00:19:29,630
Så jeg har lige haft en masse sjov at skrive
ud af en virkelig lang egentlige sætning

433
00:19:29,630 --> 00:19:32,800
at det helt sikkert overskredet
16 bytes, fordi jeg

434
00:19:32,800 --> 00:19:38,050
skrevet i denne vanvittige lang multi-line
sætning, og så lægge mærke til, hvad der skete.

435
00:19:38,050 --> 00:19:41,110
Programmet forsøgte at udskrive det
og fik derefter en segmentering fejl

436
00:19:41,110 --> 00:19:44,430
og segmentering fejl er, når
noget som dette sker

437
00:19:44,430 --> 00:19:47,650
og operativsystemet siger
nej, kan ikke røre, at hukommelsen.

438
00:19:47,650 --> 00:19:49,570
Vi kommer til at dræbe
programmet helt.

439
00:19:49,570 --> 00:19:51,180
>> Så det synes problematisk.

440
00:19:51,180 --> 00:19:54,540
Jeg har forbedret programmet, hvorved
i det mindste have en del af hukommelsen,

441
00:19:54,540 --> 00:19:58,000
men dette synes at begrænse
funktionen getString til at få

442
00:19:58,000 --> 00:20:00,780
strenge af nogle endelig længde 16.

443
00:20:00,780 --> 00:20:04,200
Så hvis du ønsker at støtte længere
sætninger end 16 tegn,

444
00:20:04,200 --> 00:20:04,880
hvad laver du?

445
00:20:04,880 --> 00:20:07,970
Nå, kan du øge
størrelsen af ​​denne buffer til 32

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

447
00:20:09,190 --> 00:20:12,260
Hvorfor gør vi ikke bare gøre
det 1.000 men skubbe tilbage.

448
00:20:12,260 --> 00:20:17,100
Hvad er svaret intuitivt for
bare undgå dette problem ved at gøre

449
00:20:17,100 --> 00:20:20,660
min puffer større, ligesom 1.000 chars?

450
00:20:20,660 --> 00:20:23,470
Ved at implementere getString denne måde.

451
00:20:23,470 --> 00:20:27,130
Hvad er godt eller dårligt her?

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

453
00:20:28,033 --> 00:20:30,574
PUBLIKUM: Hvis du binde op en masse
af plads og du ikke bruger det,

454
00:20:30,574 --> 00:20:33,500
så kan du ikke omfordele rummet.

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

456
00:20:34,500 --> 00:20:38,480
Det er spild så vidt som hvis du ikke gør
faktisk har brug 900 af disse bytes

457
00:20:38,480 --> 00:20:41,057
og alligevel du beder om
1.000 i alt alligevel,

458
00:20:41,057 --> 00:20:44,140
du bare forbruge mere hukommelse på
brugerens computer, end du har brug for,

459
00:20:44,140 --> 00:20:45,740
og efter alle, nogle af
du allerede har stødt

460
00:20:45,740 --> 00:20:47,620
i livet, når du er
kører masser af programmer

461
00:20:47,620 --> 00:20:50,470
og de spiser op masser af hukommelse,
dette kan faktisk påvirke ydeevnen

462
00:20:50,470 --> 00:20:52,220
og brugerens oplevelse
på computeren.

463
00:20:52,220 --> 00:20:56,090
Så det er sådan en doven løsning,
sikker, og omvendt,

464
00:20:56,090 --> 00:21:00,140
det er ikke kun spild, hvilket problem
stadig, selv om jeg gør min buffer

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

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

467
00:21:02,600 --> 00:21:04,475
>> PUBLIKUM: Strengen er længde 1.001.

468
00:21:04,475 --> 00:21:05,350
DAVID MALAN: Præcis.

469
00:21:05,350 --> 00:21:08,280
Hvis din streng er længde 1.001,
du har nøjagtig samme problem,

470
00:21:08,280 --> 00:21:10,705
og ved mit argument, ville jeg
bare derefter gøre det 2000

471
00:21:10,705 --> 00:21:12,830
men du ikke kender i
forhånd, hvor stort det skal være,

472
00:21:12,830 --> 00:21:16,890
og dog, jeg behøver at kompilere mit program
før udlejning folk bruger og downloade

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

474
00:21:17,390 --> 00:21:21,490
Så det er præcis den slags
ting at CS50 biblioteket forsøger

475
00:21:21,490 --> 00:21:24,750
at hjælpe os med, og vi vil kun blik
på nogle af de underliggende implementering

476
00:21:24,750 --> 00:21:29,790
her, men det er CS50 dot C. Denne
er den fil, der har været på CS50 IDE

477
00:21:29,790 --> 00:21:31,420
alle disse uger, som du har brugt.

478
00:21:31,420 --> 00:21:34,280
Det er på forhånd kompileret og du har
brugt det automatisk

479
00:21:34,280 --> 00:21:38,780
i kraft af at have
dash L CS50 flag med klang,

480
00:21:38,780 --> 00:21:42,300
men hvis jeg rulle ned gennem alle
disse funktioner, her er getString,

481
00:21:42,300 --> 00:21:44,636
og bare for at give dig en
forsmag på, hvad der foregår,

482
00:21:44,636 --> 00:21:46,760
lad os tage et hurtigt kig på
den relative kompleksitet.

483
00:21:46,760 --> 00:21:48,870
Det er ikke en super lang
funktion, men det gjorde vi ikke

484
00:21:48,870 --> 00:21:52,530
nødt til at tænke alt hårdt om
hvordan man kan gå om at få strenge.

485
00:21:52,530 --> 00:21:55,660
>> Så her er min buffer og jeg
tilsyneladende initialisere den til null.

486
00:21:55,660 --> 00:21:57,990
Dette er naturligvis, er
samme som char stjerne,

487
00:21:57,990 --> 00:22:00,585
men jeg besluttede i
gennemførelse af CS50 biblioteket

488
00:22:00,585 --> 00:22:02,460
at hvis vi kommer til at
være helt dynamisk,

489
00:22:02,460 --> 00:22:05,770
Jeg ved ikke, på forhånd, hvor stor en
string brugere vil ønsker at få.

490
00:22:05,770 --> 00:22:08,140
Så jeg har tænkt mig at starte
med blot en tom streng

491
00:22:08,140 --> 00:22:11,507
og jeg har tænkt mig at opbygge så meget
hukommelse som jeg har brug for at passe til brugeren strengen

492
00:22:11,507 --> 00:22:13,340
og hvis jeg ikke har
nok, jeg har tænkt mig at spørge

493
00:22:13,340 --> 00:22:15,010
Operativsystemet for mere hukommelse.

494
00:22:15,010 --> 00:22:17,510
Jeg har tænkt mig at flytte deres snor
i en større del af hukommelsen

495
00:22:17,510 --> 00:22:21,847
og jeg har tænkt mig at frigive eller befri
utilstrækkeligt stor luns af hukommelse

496
00:22:21,847 --> 00:22:23,680
og vi bare
at gøre dette iterativt.

497
00:22:23,680 --> 00:22:25,570
>> Så et hurtigt blik,
her er bare en variabel

498
00:22:25,570 --> 00:22:28,780
som jeg har tænkt mig at holde styr
af kapaciteten af ​​min buffer.

499
00:22:28,780 --> 00:22:30,071
Hvor mange bytes kan jeg passe?

500
00:22:30,071 --> 00:22:32,070
Her er en variabel n med
som jeg har tænkt mig at holde

501
00:22:32,070 --> 00:22:36,200
styr på, hvor mange bytes er faktisk i
bufferen eller at brugeren har indtastet.

502
00:22:36,200 --> 00:22:39,900
Hvis du ikke har set det før, du
kan angive, at en variabel som en int

503
00:22:39,900 --> 00:22:46,370
er usigneret, der som navnet antyder,
betyder, at det er ikke-negativ, og hvorfor ville

504
00:22:46,370 --> 00:22:50,590
Jeg nogensinde ønsker at genere angivelse
at en int er ikke bare en int,

505
00:22:50,590 --> 00:22:52,540
men det er en usigneret int?

506
00:22:52,540 --> 00:22:55,064
Det er en ikke-negativ int.

507
00:22:55,064 --> 00:22:56,355
Hvad betyder [uhørligt] betyde?

508
00:22:56,355 --> 00:22:58,910
>> PUBLIKUM: Det beskriver et beløb
hukommelse, der kan være [uhørligt].

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

510
00:22:59,660 --> 00:23:03,710
Så hvis jeg siger usigneret, det er faktisk
hvilket giver dig en smule ekstra hukommelse

511
00:23:03,710 --> 00:23:07,440
og det synes slags fjollet, men hvis du
have en smule ekstra hukommelse, som

512
00:23:07,440 --> 00:23:09,940
betyder, at du har dobbelt så mange
værdier, du kan repræsentere,

513
00:23:09,940 --> 00:23:11,570
fordi det kan være et 0 eller et 1.

514
00:23:11,570 --> 00:23:14,660
Så som standard, kan en int være nogenlunde
negativ 2 mia hele vejen

515
00:23:14,660 --> 00:23:16,030
op til positiv 2 mia.

516
00:23:16,030 --> 00:23:18,540
De er store intervaller, men
det er stadig slags spild

517
00:23:18,540 --> 00:23:21,280
hvis du kun bekymrer sig om
størrelser, som netop intuitivt

518
00:23:21,280 --> 00:23:24,620
bør være ikke-negative eller
positiv eller 0, ja så,

519
00:23:24,620 --> 00:23:28,884
hvorfor er du spilder 2 milliarder
mulige værdier for negative tal

520
00:23:28,884 --> 00:23:30,300
hvis du aldrig kommer til at bruge dem?

521
00:23:30,300 --> 00:23:35,350
Så ved at sige usigneret, nu er min int kan
være mellem 0 og ca. 4 mia.

522
00:23:35,350 --> 00:23:39,280
>> Så her er bare en int C grunde
Vi vil ikke komme ind lige nu, som

523
00:23:39,280 --> 00:23:42,280
hvorfor det er en int i stedet
af en char, men her er

524
00:23:42,280 --> 00:23:44,630
kernen i, hvad der foregår
på, og nogle af jer

525
00:23:44,630 --> 00:23:48,340
bruger måske, for eksempel den
fgetc funktion selv i pset fire

526
00:23:48,340 --> 00:23:51,580
eller senere, vil vi se det
igen i problemer sæt fem,

527
00:23:51,580 --> 00:23:55,410
fgetc er rart, fordi som navnet
slags, foreslår slags arcanely,

528
00:23:55,410 --> 00:23:57,940
Det er en funktion, som
får en karakter og så,

529
00:23:57,940 --> 00:24:00,690
hvad er fundamentalt forskellige
om, hvad vi laver i getString

530
00:24:00,690 --> 00:24:03,110
er vi ikke bruger
scanf på samme måde.

531
00:24:03,110 --> 00:24:07,550
Vi er bare snigende langs trin-for-trin
i hvad brugeren har indtastet,

532
00:24:07,550 --> 00:24:10,970
fordi vi kan altid afsætte en
char, og så kan vi altid sikkert

533
00:24:10,970 --> 00:24:15,599
se på en char ad gangen, og
magien begynder at ske her.

534
00:24:15,599 --> 00:24:17,890
Jeg har tænkt mig at rulle ned til
midten af ​​denne funktion

535
00:24:17,890 --> 00:24:20,360
lige kort for at indføre denne funktion.

536
00:24:20,360 --> 00:24:22,670
Meget gerne der er en
malloc-funktion, der er

537
00:24:22,670 --> 00:24:27,740
en realloc funktion, hvor realloc
lader dig omfordele en luns af hukommelse

538
00:24:27,740 --> 00:24:29,570
og gøre det større eller mindre.

539
00:24:29,570 --> 00:24:33,060
Så lang historie kort og med
en bølge af min hånd for i dag,

540
00:24:33,060 --> 00:24:35,620
vide, at hvad getString
gør, er det er slags

541
00:24:35,620 --> 00:24:39,720
af magisk vokser eller
krympning bufferen, når brugeren

542
00:24:39,720 --> 00:24:41,440
typer i hans eller hendes snor.

543
00:24:41,440 --> 00:24:43,962
>> Så hvis brugeren skriver en
kort snor, denne kode

544
00:24:43,962 --> 00:24:45,920
kun allokerer nok
hukommelse til at passe strengen.

545
00:24:45,920 --> 00:24:48,086
Hvis brugeren holder skrive
som jeg gjorde det igen og igen

546
00:24:48,086 --> 00:24:50,330
og igen, ja, hvis
buffer er oprindeligt dette store

547
00:24:50,330 --> 00:24:53,310
og programmet indser, at
vent et øjeblik, jeg er ude af rummet,

548
00:24:53,310 --> 00:24:55,410
det kommer til at fordoble
størrelsen af ​​bufferen

549
00:24:55,410 --> 00:24:59,110
og derefter dobbelt størrelse af bufferen
og den kode, der gør en fordobling,

550
00:24:59,110 --> 00:25:03,170
hvis vi ser på det her, det er
bare denne smarte one-liner.

551
00:25:03,170 --> 00:25:06,830
Du har måske ikke har set denne syntaks
før, men hvis du siger stjerne lig,

552
00:25:06,830 --> 00:25:10,470
dette er det samme som
siger kapacitet gange 2.

553
00:25:10,470 --> 00:25:13,390
Så det blot holder fordobling
Den pufferens

554
00:25:13,390 --> 00:25:17,480
og derefter fortæller realloc at give
selv så meget mere hukommelse.

555
00:25:17,480 --> 00:25:19,720
>> Nu, som en sidebemærkning, der
er andre funktioner i her

556
00:25:19,720 --> 00:25:23,680
at vi ikke vil se i detaljer
andet end at vise i GetInt,

557
00:25:23,680 --> 00:25:26,150
vi bruger getString i GetInt.

558
00:25:26,150 --> 00:25:28,192
Vi kontrollere, at det ikke er
null, hvilket, tilbagekaldelse,

559
00:25:28,192 --> 00:25:30,400
er særlig værdi,
betyder noget gik galt.

560
00:25:30,400 --> 00:25:31,233
Vi er ude af hukommelsen.

561
00:25:31,233 --> 00:25:32,310
Bedre kontrollere for det.

562
00:25:32,310 --> 00:25:33,710
Og vi vender tilbage en sentinel værdi.

563
00:25:33,710 --> 00:25:37,850
Men jeg vil udskyde til bemærkningerne om,
hvorfor og så bruger vi denne fætter til scanf

564
00:25:37,850 --> 00:25:42,100
kaldte sscanf og det viser sig
at sscanf, eller snor scanf,

565
00:25:42,100 --> 00:25:45,310
kan du tage et kig på den linje,
brugeren har indtastet, og lad dig

566
00:25:45,310 --> 00:25:49,610
analysere det væsentlige, og hvad jeg er
gør her, er jeg fortæller sscanf,

567
00:25:49,610 --> 00:25:54,440
analysere hvad brugeren har
skrevet i, og sørg% i,

568
00:25:54,440 --> 00:25:59,250
Der er et helt tal i det, og vi vil ikke
komme ind i dag præcis, hvorfor der er også

569
00:25:59,250 --> 00:26:03,760
en% c her, men i en nøddeskal tillader
os at opdage, hvis brugeren har indtastet

570
00:26:03,760 --> 00:26:06,050
i noget fup efter nummeret.

571
00:26:06,050 --> 00:26:11,766
Så grunden til, at GetInt og getString
fortælle dig at prøve igen, prøve igen, prøve igen

572
00:26:11,766 --> 00:26:13,640
er på grund af alle
at kode, vi har skrevet,

573
00:26:13,640 --> 00:26:17,900
Det er lidt at se på brugerens input
i at sikre det er helt numerisk

574
00:26:17,900 --> 00:26:21,700
eller det er en faktiske flydende
pointværdi eller lignende,

575
00:26:21,700 --> 00:26:24,233
afhængigt af hvilken værdi
fungere, du bruger.

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

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

578
00:26:25,710 --> 00:26:27,592
Det var en mundfuld
men pointen her er

579
00:26:27,592 --> 00:26:29,550
at årsagen til at vi havde
disse uddannelse hjul på

580
00:26:29,550 --> 00:26:32,880
er på grund på det laveste niveau,
Der er bare så mange ting,

581
00:26:32,880 --> 00:26:35,674
kan gå galt, at vi ønskede
til forebyggende håndtere

582
00:26:35,674 --> 00:26:38,090
disse ting i hvert fald i
tidligste uger af klassen,

583
00:26:38,090 --> 00:26:42,230
men nu med pset fire og pset fem og
ud over vil du se at det er mere til

584
00:26:42,230 --> 00:26:45,570
dig, men også du er bedre i stand til
løse den slags problemer

585
00:26:45,570 --> 00:26:47,180
dig selv.

586
00:26:47,180 --> 00:26:51,770
Eventuelle spørgsmål om getString eller GetInt?

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

588
00:26:52,630 --> 00:26:55,130
>> PUBLIKUM: Hvorfor ville du fordoble
Den pufferens

589
00:26:55,130 --> 00:26:57,630
snarere end blot at øge
det ved det nøjagtige beløb?

590
00:26:57,630 --> 00:26:58,100
>> DAVID MALAN: Godt spørgsmål.

591
00:26:58,100 --> 00:27:00,474
Hvorfor skulle vi fordoble kapaciteten
af bufferen i modsætning

592
00:27:00,474 --> 00:27:02,800
til bare at øge den
af nogle konstant værdi?

593
00:27:02,800 --> 00:27:03,900
Det var et design beslutning.

594
00:27:03,900 --> 00:27:08,590
Vi har lige besluttet, at fordi det har tendens til at
være lidt dyrt tidsmæssigt til at spørge

595
00:27:08,590 --> 00:27:10,440
operativsystemet
for hukommelse, vi ikke gjorde

596
00:27:10,440 --> 00:27:13,210
ønsker at ende med at få ind
en situation til store strygere

597
00:27:13,210 --> 00:27:14,960
at vi bad
OS igen og igen

598
00:27:14,960 --> 00:27:17,500
og igen og igen i
hurtigt efter hinanden til hukommelsen.

599
00:27:17,500 --> 00:27:20,387
Så vi netop besluttet, noget
vilkårligt men vi håber rimelighed,

600
00:27:20,387 --> 00:27:22,720
at du ved, hvad, lad os
forsøge at komme foran os selv

601
00:27:22,720 --> 00:27:25,520
og bare holde fordoble det, så
vi minimere mængden af ​​gange

602
00:27:25,520 --> 00:27:29,010
vi er nødt til at ringe til malloc eller
realloc, men en samlet dom

603
00:27:29,010 --> 00:27:31,820
ringe i fravær af vide
hvad brugerne måske ønsker at skrive i.

604
00:27:31,820 --> 00:27:33,600
Begge måder kan være diskutabel.

605
00:27:33,600 --> 00:27:35,430
Formentlig godt.

606
00:27:35,430 --> 00:27:39,240
>> Så lad os tage et kig på et par
andre bivirkninger af hukommelse,

607
00:27:39,240 --> 00:27:41,610
ting, der kan gå galt
og værktøjer, som du kan

608
00:27:41,610 --> 00:27:43,880
bruge til at fange den slags fejltagelser.

609
00:27:43,880 --> 00:27:47,800
Det viser sig, alle jer, selvom
check50 har ikke fortalt dig så meget,

610
00:27:47,800 --> 00:27:50,050
har skrevet buggy
-kode siden uge en,

611
00:27:50,050 --> 00:27:53,630
selv om alle check50 test er
gik, og selv hvis du og din TF

612
00:27:53,630 --> 00:27:56,010
er super overbevist om, at
din kode fungerer efter hensigten.

613
00:27:56,010 --> 00:27:59,190
Din kode er blevet buggy eller
fejlbehæftet i, at alle jer,

614
00:27:59,190 --> 00:28:02,540
i at bruge CS50 bibliotek,
er blevet utæt hukommelse.

615
00:28:02,540 --> 00:28:06,040
Du er blevet anmodet operativsystem
til hukommelse i de fleste programmer

616
00:28:06,040 --> 00:28:08,850
du har skrevet, men du har
faktisk aldrig givet det tilbage.

617
00:28:08,850 --> 00:28:12,110
Du har kaldt getString
og GetInt og GetFloat,

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

619
00:28:15,270 --> 00:28:19,890
String Tilbage eller lignende, men vi har set
at getString gør allokere hukommelse

620
00:28:19,890 --> 00:28:22,810
i form af malloc eller dette
funktion realloc, som er lige

621
00:28:22,810 --> 00:28:25,670
meget ens i ånden,
og alligevel har vi været

622
00:28:25,670 --> 00:28:28,629
beder operativsystemet for
hukommelse og hukommelse igen og igen

623
00:28:28,629 --> 00:28:29,670
men aldrig give det tilbage.

624
00:28:29,670 --> 00:28:33,550
>> Nu, da en side, viser det sig, at
når et program afsluttes, alt hukommelse

625
00:28:33,550 --> 00:28:34,870
automatisk frigøres.

626
00:28:34,870 --> 00:28:36,150
Så det er ikke været et enormt meget.

627
00:28:36,150 --> 00:28:38,590
Det kommer ikke til at bryde
IDE eller langsomme ting ned,

628
00:28:38,590 --> 00:28:40,670
men når programmer gør
generelt lække hukommelse

629
00:28:40,670 --> 00:28:42,170
og de kører i lang tid.

630
00:28:42,170 --> 00:28:45,640
Hvis du nogensinde har set den dumme lille
badebold i Mac OS eller timeglas

631
00:28:45,640 --> 00:28:51,160
på Windows, hvor det er slags
bremse eller tænker eller tænker

632
00:28:51,160 --> 00:28:53,770
eller bare virkelig begynder
at bremse til en gennemgang,

633
00:28:53,770 --> 00:28:56,960
det meget muligvis kunne være
resultatet af en hukommelsesfejl.

634
00:28:56,960 --> 00:28:59,970
Programmørerne, der skrev
den software, du bruger

635
00:28:59,970 --> 00:29:03,570
spørge operativsystemet for hukommelse
hvert par minutter, hver time.

636
00:29:03,570 --> 00:29:05,570
Men hvis du kører
software, selv om det er

637
00:29:05,570 --> 00:29:08,680
minimeres i din computer
i timer eller dagevis,

638
00:29:08,680 --> 00:29:11,980
kan du spørge om mere og mere
hukommelse og faktisk aldrig bruger det

639
00:29:11,980 --> 00:29:15,180
og så din kode kan være, eller
programmer kan være utæt hukommelse,

640
00:29:15,180 --> 00:29:18,350
og hvis du begynder at lække hukommelse,
der er mindre hukommelse til andre programmer,

641
00:29:18,350 --> 00:29:21,220
og virkningen er at
bremse alt ned.

642
00:29:21,220 --> 00:29:23,600
>> Nu, dette er langt en af
de mest grusomme programmer

643
00:29:23,600 --> 00:29:26,350
vil du have mulighed
at køre i CS50 omfang

644
00:29:26,350 --> 00:29:31,650
som dens output er endnu mere esoteriske end
klang s eller gøre os eller nogen af ​​kommandoen

645
00:29:31,650 --> 00:29:35,930
line programmer, vi har kørt før, men
heldigvis, indlejret i sin produktion

646
00:29:35,930 --> 00:29:39,810
er nogle super nyttige tips, der
vil være nyttig enten til pset fire

647
00:29:39,810 --> 00:29:41,510
eller i hvert fald POpret fem.

648
00:29:41,510 --> 00:29:44,250
Så Valgrind er et værktøj
der kan bruges til at se

649
00:29:44,250 --> 00:29:46,930
for memory leaks i dit program.

650
00:29:46,930 --> 00:29:48,570
Det er relativt enkelt at køre.

651
00:29:48,570 --> 00:29:51,420
Du kører Valgrind og da, selv
selvom det er lidt detaljeret,

652
00:29:51,420 --> 00:29:54,440
dash bindestreg lækage kontrol
lig fuld, og derefter dot

653
00:29:54,440 --> 00:29:56,320
skråstreg og navnet på dit program.

654
00:29:56,320 --> 00:30:00,010
Så Valgrind vil derefter køre dit program
og til allersidst af dit program

655
00:30:00,010 --> 00:30:02,240
kører før det afsluttes og
giver dig en anden prompt,

656
00:30:02,240 --> 00:30:04,980
det kommer til at analysere din
program, mens den er kørt

657
00:30:04,980 --> 00:30:07,740
og fortælle dig har du lække
enhver hukommelse og bedre endnu,

658
00:30:07,740 --> 00:30:10,610
har du rører hukommelse,
ikke tilhører dig?

659
00:30:10,610 --> 00:30:13,700
Det kan ikke fange alt, men det er
temmelig god til at fange de fleste ting.

660
00:30:13,700 --> 00:30:19,700
>> Så her er et eksempel på min har kørt
dette program, som har kørt Valgrind,

661
00:30:19,700 --> 00:30:21,470
på et program kaldet
hukommelse, og jeg har tænkt mig

662
00:30:21,470 --> 00:30:24,730
at fremhæve de linjer, der er
i sidste ende af interesse for os.

663
00:30:24,730 --> 00:30:27,690
Så der er endnu flere distraktioner
at jeg har slettet fra slide.

664
00:30:27,690 --> 00:30:30,930
Men lad os bare se, hvad dette
Programmet er i stand til at fortælle os.

665
00:30:30,930 --> 00:30:34,800
Det er i stand til at fortælle os ting
ligesom ugyldig skrive størrelse 4.

666
00:30:34,800 --> 00:30:38,020
Med andre ord, hvis du rører hukommelsen,
specielt 4 bytes hukommelse

667
00:30:38,020 --> 00:30:40,350
at du ikke skal have,
Valgrind kan fortælle dig det.

668
00:30:40,350 --> 00:30:41,660
Ugyldig skrive størrelse 4.

669
00:30:41,660 --> 00:30:43,640
Du rørte fire bytes
at du ikke skal have.

670
00:30:43,640 --> 00:30:44,840
Hvor har du det?

671
00:30:44,840 --> 00:30:45,900
Det er den skønhed.

672
00:30:45,900 --> 00:30:50,000
Hukommelse prik c linje 21 er, hvor du
skruet op, og det er derfor, det er nyttigt.

673
00:30:50,000 --> 00:30:53,410
Meget gerne GDB, kan det hjælpe
pege dig på det faktiske fejl.

674
00:30:53,410 --> 00:30:57,170
>> Nu, dette ene er lidt mere
verbose, hvis ikke forvirrende.

675
00:30:57,170 --> 00:31:01,307
40 bytes i 1 blokke er absolut
tabt i tab post 1 af 1.

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

677
00:31:02,140 --> 00:31:05,920
Tja, det betyder bare, du bad om
40 bytes og du aldrig gav det tilbage.

678
00:31:05,920 --> 00:31:08,930
Du kaldte malloc eller du kaldte
GetString og operativsystemet

679
00:31:08,930 --> 00:31:12,450
gav dig 40 bytes, men du aldrig
befriet eller frigjort, at hukommelsen,

680
00:31:12,450 --> 00:31:15,400
og for at være fair, har vi aldrig vise
dig, hvordan du give tilbage hukommelse.

681
00:31:15,400 --> 00:31:17,910
Viser sig der er en super
simpel funktion kaldes fri.

682
00:31:17,910 --> 00:31:21,170
Tager et argument, de ting
du ønsker at frigøre eller give tilbage,

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

684
00:31:23,430 --> 00:31:27,300
er gået tabt på linje
20 hukommelse dot c.

685
00:31:27,300 --> 00:31:28,650
>> Så lad os se dette program.

686
00:31:28,650 --> 00:31:31,020
Det er super ubrugelig.

687
00:31:31,020 --> 00:31:33,980
Det viser kun
denne særlige fejl.

688
00:31:33,980 --> 00:31:34,920
Så lad os tage et kig.

689
00:31:34,920 --> 00:31:39,920
Her er de vigtigste og vigtigste, skilte, opkald
en funktion kaldet f og derefter vender tilbage.

690
00:31:39,920 --> 00:31:41,550
Så ikke alt, interessant.

691
00:31:41,550 --> 00:31:42,664
Hvad betyder f gøre?

692
00:31:42,664 --> 00:31:44,330
Bemærk, at jeg ikke gider med en prototype.

693
00:31:44,330 --> 00:31:46,520
Jeg ønskede at holde koden
så minimale som muligt.

694
00:31:46,520 --> 00:31:49,530
Så jeg sætter f over hoved- og
det er fint, i hvert fald,

695
00:31:49,530 --> 00:31:51,500
til korte programmer som dette.

696
00:31:51,500 --> 00:31:56,910
Så f returnerer ikke noget og gør
ikke tage noget, men det gør gøre dette.

697
00:31:56,910 --> 00:31:59,620
Det erklærer, ligesom
i Binky eksempel

698
00:31:59,620 --> 00:32:02,682
en pointer kaldet x, der kommer
at gemme adressen på en int.

699
00:32:02,682 --> 00:32:03,890
Så det er den venstre side.

700
00:32:03,890 --> 00:32:07,230
På engelsk, hvad der er den
højre side gør?

701
00:32:07,230 --> 00:32:09,770
Nogen?

702
00:32:09,770 --> 00:32:13,665
Hvad er det gør for os?

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

704
00:32:14,651 --> 00:32:16,623
>> PUBLIKUM: [uhørligt]
gange større en int

705
00:32:16,623 --> 00:32:19,175
hvilket er 10 gange, at [uhørligt]

706
00:32:19,175 --> 00:32:20,800
DAVID MALAN: God og lad mig opsummere.

707
00:32:20,800 --> 00:32:25,480
Så afsætte nok plads til 10 heltal
eller 10, hvad er på størrelse med en int,

708
00:32:25,480 --> 00:32:29,340
Det er fire bytes, så 10 gange 4 er
40, således at højre side, som jeg har

709
00:32:29,340 --> 00:32:33,930
fremhævede, er at give mig 40 bytes og
gemme adressen på den første byte

710
00:32:33,930 --> 00:32:34,940
ind på x.

711
00:32:34,940 --> 00:32:38,380
Og nu endelig og her er hvor
dette program er buggy, hvad er

712
00:32:38,380 --> 00:32:41,540
galt med linje 21, baseret på denne logik?

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

714
00:32:45,197 --> 00:32:46,280
Hvad er der galt med linje 21?

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

716
00:32:46,780 --> 00:32:49,550
PUBLIKUM: Du kan ikke
indeks i x [uhørligt].

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

718
00:32:50,300 --> 00:32:52,270
Jeg skal ikke indeks i x som.

719
00:32:52,270 --> 00:32:53,850
Så syntaktisk, det er OK.

720
00:32:53,850 --> 00:32:56,990
Hvad er rart er, ligesom du
kan behandle navnet på et array

721
00:32:56,990 --> 00:33:01,080
som om det er en pegepind, tilsvarende
kan du behandle en pegepind, som om det er

722
00:33:01,080 --> 00:33:06,425
et array, og så jeg kan syntaktisk
sige x beslag noget, x beslag i,

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

724
00:33:07,800 --> 00:33:09,096
Hvorfor?

725
00:33:09,096 --> 00:33:10,910
>> PUBLIKUM: Fordi det er ikke inde.

726
00:33:10,910 --> 00:33:12,390
>> DAVID MALAN: Det er ikke
indeni, luns af hukommelse.

727
00:33:12,390 --> 00:33:15,306
Hvad er den største værdi, jeg skulle
være at sætte i disse firkantede parenteser?

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

729
00:33:16,870 --> 00:33:18,160
På grund af nul indeksering.

730
00:33:18,160 --> 00:33:20,190
Så 0 til 9 ville være fint.

731
00:33:20,190 --> 00:33:23,960
Konsollen 10 er ikke god og
men, husker dog, hver gang

732
00:33:23,960 --> 00:33:27,017
Jeg synes at forsøge at gøre CS50 IDE
nedbrud ved at skrive i falske værdier,

733
00:33:27,017 --> 00:33:29,100
det ikke altid samarbejder,
og ja, du ofte

734
00:33:29,100 --> 00:33:31,460
heldig bare fordi
operativsystem ikke

735
00:33:31,460 --> 00:33:35,467
bemærke, at du nogensinde så lidt
videregive nogle luns af hukommelse,

736
00:33:35,467 --> 00:33:38,300
fordi du holdt sig inden teknisk
dit segment, men mere om det

737
00:33:38,300 --> 00:33:40,940
i et operativsystemer klasse,
og så noget som dette

738
00:33:40,940 --> 00:33:43,000
kunne meget nemt gå uopdaget.

739
00:33:43,000 --> 00:33:48,120
Dit program er aldrig vil gå ned
konsekvent, men måske en gang i et stykke tid.

740
00:33:48,120 --> 00:33:50,610
>> Og så lad os prøve Valgrind
om dette, og her er

741
00:33:50,610 --> 00:33:52,870
hvor vi får overvældet
af udgangen øjeblik.

742
00:33:52,870 --> 00:34:00,810
Så gør hukommelse Valgrind lækage kontrol
lig fuld dot skråstreg hukommelse.

743
00:34:00,810 --> 00:34:03,040
Og her er hvorfor lover jeg
dette ville overvælde.

744
00:34:03,040 --> 00:34:05,700
Her er hvad Valgrind, her er hvad
en programmør, nogle år siden-

745
00:34:05,700 --> 00:34:08,469
besluttet, at det ville være en god idé
for output til at ligne.

746
00:34:08,469 --> 00:34:09,750
Så lad os få mening ud af dette.

747
00:34:09,750 --> 00:34:13,120
Så hele vejen til venstre hånd
side uden god grund

748
00:34:13,120 --> 00:34:16,620
er den proces ID af programmet
vi bare køre, den entydige identifikator

749
00:34:16,620 --> 00:34:18,030
for det program, vi lige kørte.

750
00:34:18,030 --> 00:34:19,738
Vi udgår fra at
dias, men der

751
00:34:19,738 --> 00:34:22,190
er nogle nyttige oplysninger i her.

752
00:34:22,190 --> 00:34:24,684
>> Lad os rulle op til toppen.

753
00:34:24,684 --> 00:34:25,600
Her er, hvor vi begyndte.

754
00:34:25,600 --> 00:34:27,040
Så det er ikke så meget output.

755
00:34:27,040 --> 00:34:30,429
Her er det ugyldigt skrive
størrelse 4 på linie 21.

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

757
00:34:31,760 --> 00:34:34,500
Linie 21 var præcis
dette, og det giver mening

758
00:34:34,500 --> 00:34:37,290
at jeg er i gyldigt
skrive 4 byte, fordi jeg er

759
00:34:37,290 --> 00:34:40,389
forsøger at sætte denne heltal,
som kunne være noget,

760
00:34:40,389 --> 00:34:42,370
det bare sker for at være
nul, men jeg prøver

761
00:34:42,370 --> 00:34:44,940
at sætte det på et sted
der ikke tilhører mig.

762
00:34:44,940 --> 00:34:50,900
Desuden, hernede, 40 bytes i én
blokke er afgjort tabt på rekordtid 1.

763
00:34:50,900 --> 00:34:56,500
Det er fordi når jeg kalder malloc
her, jeg faktisk aldrig frigøre hukommelse.

764
00:34:56,500 --> 00:34:58,140
>> Så hvordan kan vi løse dette?

765
00:34:58,140 --> 00:35:02,970
Lad mig gå videre og være lidt mere sikker
og gøre 9 der og lad mig her gratis på x.

766
00:35:02,970 --> 00:35:04,820
Dette er den nye funktion til dag.

767
00:35:04,820 --> 00:35:11,520
Hvis jeg nu køres igen gøre hukommelse dot skråstreg,
Lad os køre Valgrind på det igen,

768
00:35:11,520 --> 00:35:14,990
maksimere mit vindue og tryk Enter.

769
00:35:14,990 --> 00:35:16,900
Nu er det godt.

770
00:35:16,900 --> 00:35:19,590
De begrave de gode nyheder
i alt af denne produktion.

771
00:35:19,590 --> 00:35:20,810
Alle dynge blokke var frie.

772
00:35:20,810 --> 00:35:23,604
Vi vil komme tilbage til, hvad den bunke
er, men ingen lækager er mulige.

773
00:35:23,604 --> 00:35:25,520
Så dette er blot en anden
værktøj til din værktøjskasse

774
00:35:25,520 --> 00:35:30,220
som du kan begynde at
find nu fejl som dette.

775
00:35:30,220 --> 00:35:34,532
>> Men lad os se, hvad
mere kan gå galt her.

776
00:35:34,532 --> 00:35:38,890
Lad os overgang nu
faktisk at løse et problem.

777
00:35:38,890 --> 00:35:42,440
Som en sidebemærkning, hvis det vil aflaste en
lille smule forvirring eller spændinger,

778
00:35:42,440 --> 00:35:43,430
dette er nu sjovt.

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

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

781
00:35:46,900 --> 00:35:49,040
Det er temmelig godt.

782
00:35:49,040 --> 00:35:50,890
Fordi pointere er
adresser og adresser

783
00:35:50,890 --> 00:35:53,098
er generelt konventionelt
skrevet med hexadecimal.

784
00:35:53,098 --> 00:35:54,650
Ha, ha, det er sjovt nu.

785
00:35:54,650 --> 00:35:58,390
Under alle omstændigheder, så lad os nu
faktisk løse et problem.

786
00:35:58,390 --> 00:36:00,840
Det har været super,
Super lavt niveau hidtil,

787
00:36:00,840 --> 00:36:03,950
og vi kan faktisk gøre nyttig
ting med disse lavt niveau detaljer.

788
00:36:03,950 --> 00:36:06,710
>> Så vi introducerede et par uger
siden begrebet et array.

789
00:36:06,710 --> 00:36:09,177
Et array var rart, fordi
det er svært at rydde op vores kode

790
00:36:09,177 --> 00:36:11,760
for hvis vi ønskede at skrive en
program med flere studerende

791
00:36:11,760 --> 00:36:15,270
eller flere navne og huse, og
sovesale og gymnasier og alt dette,

792
00:36:15,270 --> 00:36:19,430
vi kunne gemme alt mere
rent inde i et array.

793
00:36:19,430 --> 00:36:23,039
Men foreslå én nedadrettede
af et array hidtil.

794
00:36:23,039 --> 00:36:26,080
Selv hvis du ikke har lidt det selv
i et program, bare instinktivt,

795
00:36:26,080 --> 00:36:30,870
hvad er en dårlig ting
om et array, måske?

796
00:36:30,870 --> 00:36:32,337
Jeg hører nogle mumler.

797
00:36:32,337 --> 00:36:34,170
PUBLIKUM: Det er svært
at ændre størrelsen.

798
00:36:34,170 --> 00:36:36,128
DAVID MALAN: Det er svært
at ændre størrelsen.

799
00:36:36,128 --> 00:36:38,660
Du kan ikke ændre størrelsen
af et array, i virkeligheden, i sig selv

800
00:36:38,660 --> 00:36:43,040
i C. Du kan tildele et andet array,
flytte alt fra den gamle

801
00:36:43,040 --> 00:36:45,380
ind i det nye, og nu
har nogle ekstra plads,

802
00:36:45,380 --> 00:36:47,469
men det er ikke som en
sprog som Java eller Python

803
00:36:47,469 --> 00:36:49,760
eller en række andre
sprog med hvilket nogle af jer

804
00:36:49,760 --> 00:36:52,070
kunne være bekendt, hvor man
kan bare holde tilføje ting

805
00:36:52,070 --> 00:36:53,930
til bevidstløshed til enden af ​​et array.

806
00:36:53,930 --> 00:36:57,880
Når du har en bred vifte af
størrelse 6, som er dets størrelse,

807
00:36:57,880 --> 00:37:01,970
og så meget lide tanken tidligere
har en buffer med en vis størrelse,

808
00:37:01,970 --> 00:37:05,940
du nødt til at gætte ud af porten
hvilken størrelse vil du have det til at være?

809
00:37:05,940 --> 00:37:07,880
Hvis du gætter for stor,
du spilder plads.

810
00:37:07,880 --> 00:37:10,950
Hvis du gætter for lille, du
kan ikke gemme disse data, i det mindste

811
00:37:10,950 --> 00:37:12,940
uden en masse mere arbejde.

812
00:37:12,940 --> 00:37:18,180
>> Så i dag, takket være pointere, vi kan
begynde at sy sammen vores egne brugerdefinerede

813
00:37:18,180 --> 00:37:20,989
datastrukturer, og
Faktisk her er noget

814
00:37:20,989 --> 00:37:23,030
der ser lidt mere
kryptiske ved første øjekast,

815
00:37:23,030 --> 00:37:26,440
men det er det, vi vil kalde en sammenkædet
listen, og dens navn slags sammenfatter

816
00:37:26,440 --> 00:37:26,940
det.

817
00:37:26,940 --> 00:37:29,550
Det er en liste over numre, eller i
dette tilfælde en liste over numre,

818
00:37:29,550 --> 00:37:33,480
men det kunne være en liste over noget, men
det er bundet sammen ved hjælp af pile,

819
00:37:33,480 --> 00:37:36,380
og bare tage et gæt
med hvilken teknik

820
00:37:36,380 --> 00:37:38,310
vil vi være i stand til
at sy sammen,

821
00:37:38,310 --> 00:37:42,540
lidt ligesom popcorn med en tråd,
en sammenkædet lister rektangler her?

822
00:37:42,540 --> 00:37:43,936
Dens tal?

823
00:37:43,936 --> 00:37:45,560
Hvad er den underliggende sprog funktion?

824
00:37:45,560 --> 00:37:46,350
>> PUBLIKUM: En pointer.

825
00:37:46,350 --> 00:37:47,308
>> DAVID MALAN: En pointer.

826
00:37:47,308 --> 00:37:51,700
Så hver af disse pile repræsenterer her
en pointer eller blot en adresse.

827
00:37:51,700 --> 00:37:54,590
Så med andre ord, hvis jeg vil
at lagre en liste over numre,

828
00:37:54,590 --> 00:37:59,040
Jeg kan ikke bare gemme det, hvis jeg vil
evnen til at vokse og skrumpe

829
00:37:59,040 --> 00:38:00,990
min datastruktur i et array.

830
00:38:00,990 --> 00:38:03,000
Så jeg har brug for at have en lille
mere sofistikerede,

831
00:38:03,000 --> 00:38:05,720
men bemærker, at dette
Billedet viser slags

832
00:38:05,720 --> 00:38:08,650
at hvis du lige har fået små tråde
forbinde det hele sammen,

833
00:38:08,650 --> 00:38:13,100
sandsynligvis er ikke så svært at gøre plads
mellem to af disse rektangler

834
00:38:13,100 --> 00:38:16,750
eller to af disse knudepunkter, da vi starter
kalde dem, sat i en ny knude,

835
00:38:16,750 --> 00:38:19,547
og derefter med nogle nye tråd, bare
grøft tre knudepunkter sammen,

836
00:38:19,547 --> 00:38:22,880
den første, den sidste og den
at du bare indsat i midten.

837
00:38:22,880 --> 00:38:26,000
>> Og faktisk en sammenkædet liste,
I modsætning til en array, er dynamisk.

838
00:38:26,000 --> 00:38:27,840
Det kan vokse og det kan
skrumpe, og du ikke gør

839
00:38:27,840 --> 00:38:32,434
nødt til at vide eller pleje på forhånd, hvordan
meget data du vil være opbevaring,

840
00:38:32,434 --> 00:38:35,600
men det viser sig, vi er nødt til at være lidt
forsigtig med, hvordan man gennemfører dette.

841
00:38:35,600 --> 00:38:39,070
Så lad os først overveje, hvordan vi gennemfører
en af ​​disse små rektangler.

842
00:38:39,070 --> 00:38:40,690
Det er nemt at implementere en int.

843
00:38:40,690 --> 00:38:44,000
Du skal bare sige int n og derefter
du får 4 bytes for en int,

844
00:38:44,000 --> 00:38:49,089
men hvordan får jeg en int, kalder det n,
og derefter en pegepind, lad os kalde det næste.

845
00:38:49,089 --> 00:38:50,880
Vi kunne kalde disse
ting noget, vi ønsker

846
00:38:50,880 --> 00:38:53,590
men jeg har brug for en brugerdefineret datastruktur.

847
00:38:53,590 --> 00:38:54,257
Ja?

848
00:38:54,257 --> 00:38:57,020
>> PUBLIKUM: Ampersand [uhørligt].

849
00:38:57,020 --> 00:39:00,940
>> DAVID MALAN: Så tegnet vi vil bruge til
få adressen på en node potentielt.

850
00:39:00,940 --> 00:39:02,740
Men vi har brug for en anden
træk ved C for

851
00:39:02,740 --> 00:39:06,700
at give mig mulighed for at oprette
denne skik rektangel, denne skik

852
00:39:06,700 --> 00:39:08,919
variabel hvis du vil, i hukommelsen.

853
00:39:08,919 --> 00:39:09,710
PUBLIKUM: En struct.

854
00:39:09,710 --> 00:39:10,626
DAVID MALAN: A struct.

855
00:39:10,626 --> 00:39:14,310
Husker fra sidste uge, vi introducerede
struct, denne relativt simple nøgleord

856
00:39:14,310 --> 00:39:16,254
der lader os gøre ting som dette.

857
00:39:16,254 --> 00:39:18,420
C kom ikke med en data
struktur kaldet elev.

858
00:39:18,420 --> 00:39:22,190
Den leveres med int og float og fjeldørred og
sådan, men det kommer ikke med studerende,

859
00:39:22,190 --> 00:39:26,750
men vi kan skabe en studerende datatype,
en studerende struktur med denne syntaks

860
00:39:26,750 --> 00:39:27,250
her.

861
00:39:27,250 --> 00:39:28,350
Og du vil se det igen og igen.

862
00:39:28,350 --> 00:39:30,426
Så du skal ikke bekymre dig om
huske de søgeord,

863
00:39:30,426 --> 00:39:33,300
men det søgeord, der er vigtigt, er
bare det faktum, at vi sagde struct

864
00:39:33,300 --> 00:39:37,590
og så vi kaldte det studerende og inde
af de studerende var et navn og et hus

865
00:39:37,590 --> 00:39:39,390
eller et kollegieværelse eller lignende.

866
00:39:39,390 --> 00:39:41,980
>> Og så nu i dag, lad os foreslå dette.

867
00:39:41,980 --> 00:39:45,240
Jeg har tilføjet et par ord, men hvis jeg ønsker
at gennemføre denne rektangel, der er

868
00:39:45,240 --> 00:39:48,440
fik begge en int og
pointer, ved du hvad, jeg er

869
00:39:48,440 --> 00:39:51,540
kommer til at erklære en struct kaldet node.

870
00:39:51,540 --> 00:39:55,630
Jeg er også, inde i den, vil sige
at en node, dette rektangel, har en int

871
00:39:55,630 --> 00:39:59,730
og vi vil kalde det n og
det har en næste pointer.

872
00:39:59,730 --> 00:40:02,540
Og det er lidt detaljeret,
men hvis du tænker over det,

873
00:40:02,540 --> 00:40:07,300
pilene, der var i billedet
et øjeblik siden, er af, hvad datatype?

874
00:40:07,300 --> 00:40:12,330
Hvor hver af disse pile peger
til hvilken type af datastruktur?

875
00:40:12,330 --> 00:40:14,332
Det er ikke peger blot på en int per se.

876
00:40:14,332 --> 00:40:16,165
Det peger på
Hele rektangulære ting

877
00:40:16,165 --> 00:40:18,720
og at rektangulære ting,
vi sagde, kaldes en knude.

878
00:40:18,720 --> 00:40:21,720
Og så vi slags nødt til at
rekursivt definere dette sådant

879
00:40:21,720 --> 00:40:26,270
at en node, skal vi sige,
vil indeholde en int kaldes n

880
00:40:26,270 --> 00:40:31,070
og en pointer kaldet næste og
type datastruktur, som

881
00:40:31,070 --> 00:40:35,770
at pointer punkter er tilsyneladende
vil være struct node.

882
00:40:35,770 --> 00:40:41,550
>> Så dette er irriterende detaljeret
og bare for at være pedantisk,

883
00:40:41,550 --> 00:40:44,100
grunden til, at vi ikke kan
blot sige dette, som ærligt talt

884
00:40:44,100 --> 00:40:46,860
ser meget mere læsbar,
er fordi tilbagekaldelse, at C læse

885
00:40:46,860 --> 00:40:48,710
ting top til bund, venstre til højre.

886
00:40:48,710 --> 00:40:54,120
Det er ikke, indtil vi får den semikolon
at søgeordet node rent faktisk eksisterer.

887
00:40:54,120 --> 00:40:57,980
Så hvis vi ønsker at have denne form for
cyklisk henvisning indersiden af ​​data

888
00:40:57,980 --> 00:41:02,120
struktur, vi er nødt til at gøre dette, hvor
vi siger struct node foroven, som

889
00:41:02,120 --> 00:41:06,770
giver os en længere måde at beskrive dette
ting, så inde vi siger struct node,

890
00:41:06,770 --> 00:41:09,560
og derefter i allersidste linje
vi siger, okay, C, ved den måde,

891
00:41:09,560 --> 00:41:12,060
bare kalde hele denne forbandede
ting en node og stoppe

892
00:41:12,060 --> 00:41:14,360
bruge søgeordet struct helt.

893
00:41:14,360 --> 00:41:18,030
Så dette er bare en slags syntaktisk
trick, der i sidste ende lader os skabe

894
00:41:18,030 --> 00:41:21,370
noget, der ser ud præcis som dette.

895
00:41:21,370 --> 00:41:25,010
>> Så hvis vi antager nu vi kan
gennemføre denne ting i C,

896
00:41:25,010 --> 00:41:28,040
hvordan gør vi faktisk
begynde kørsel denne?

897
00:41:28,040 --> 00:41:32,360
Tja, i virkeligheden, alt, hvad vi skal gøre, er
gentage fra venstre mod højre og lige

898
00:41:32,360 --> 00:41:35,960
slags indsætte knudepunkter eller slette knudepunkter
eller søge efter ting, hvor vi vil,

899
00:41:35,960 --> 00:41:39,560
men for at gøre dette, så lad os gå videre og gøre
tingene lidt mere reel, fordi dette

900
00:41:39,560 --> 00:41:42,560
har været super lavt niveau hidtil.

901
00:41:42,560 --> 00:41:45,700
Ville nogen bogstaveligt gerne være først?

902
00:41:45,700 --> 00:41:46,200
OK.

903
00:41:46,200 --> 00:41:47,092
Kom op.

904
00:41:47,092 --> 00:41:47,800
Hvad er dit navn?

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
Dejligt at møde dig.

908
00:41:49,998 --> 00:41:50,960
Også mig.

909
00:41:50,960 --> 00:41:52,450
Okay.

910
00:41:52,450 --> 00:41:53,990
Og vi har brug for et nummer 9.

911
00:41:53,990 --> 00:41:55,240
Ikke så god som første, måske.

912
00:41:55,240 --> 00:41:56,430
OK, nummer 9.

913
00:41:56,430 --> 00:41:59,667
En række 17, tak.

914
00:41:59,667 --> 00:42:01,000
Lad mig gå tilbage lidt længere.

915
00:42:01,000 --> 00:42:03,980
Nummer 22, skal du, og
hvad med længere tilbage

916
00:42:03,980 --> 00:42:06,344
hvis jeg kan se nogen hænder
med alt lys eller ingen.

917
00:42:06,344 --> 00:42:08,010
Nogen der bliver meldte lige der.

918
00:42:08,010 --> 00:42:08,968
Har du lyst til at komme op?

919
00:42:08,968 --> 00:42:10,450
Din underarm er magt går op.

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 ned.

923
00:42:15,120 --> 00:42:18,450
Vil nogen anden gerne
forcefully-- Kom op.

924
00:42:18,450 --> 00:42:21,030
En egentlig frivillig.

925
00:42:21,030 --> 00:42:23,330
>> Så meget hurtigt, hvis
du fyre kunne arrangere

926
00:42:23,330 --> 00:42:26,550
jer ligesom
knudepunkterne på skærmen.

927
00:42:26,550 --> 00:42:27,510
Tak.

928
00:42:27,510 --> 00:42:29,234
Og du vil være 26.

929
00:42:29,234 --> 00:42:30,650
Alle rigtige og hurtige introduktioner.

930
00:42:30,650 --> 00:42:32,139
Så jeg er David, og du er også?

931
00:42:32,139 --> 00:42:32,680
David: David.

932
00:42:32,680 --> 00:42:33,721
DAVID MALAN: Og du er?

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
Fremragende.

940
00:42:37,590 --> 00:42:39,810
Så dette er vores frivillige
for i dag og gå videre

941
00:42:39,810 --> 00:42:43,090
og skift lidt på den måde,
og bare gå videre og holde

942
00:42:43,090 --> 00:42:47,024
holde dine numre, som du er, eller din
første tegn og bruge din venstre hånd,

943
00:42:47,024 --> 00:42:48,940
gå videre og bare gennemføre
disse pile, bare

944
00:42:48,940 --> 00:42:51,360
så din venstre hånd er bogstaveligt talt
peger på, hvad du skal pege

945
00:42:51,360 --> 00:42:54,610
på, og giv dig selv nogle rum, så
vi kan visuelt se dine arme faktisk

946
00:42:54,610 --> 00:42:58,120
peger, og du kan bare pege
slags på jorden er fint.

947
00:42:58,120 --> 00:43:03,040
>> Så her har vi en sammenkædet liste med en,
to, tre, fire, fem knudepunkter i første omgang,

948
00:43:03,040 --> 00:43:05,860
og læg mærke til at vi har denne særlige
pointer i begyndelsen, der er

949
00:43:05,860 --> 00:43:09,770
nøglen, fordi vi er nødt til at holde styr
af hele længden listen eller anden måde.

950
00:43:09,770 --> 00:43:13,590
Disse fyre, selvom de er forladt
mod højre, ryg mod ryg i hukommelsen,

951
00:43:13,590 --> 00:43:15,950
de rent faktisk kan være hvor som helst
i computerens hukommelse.

952
00:43:15,950 --> 00:43:18,240
Så disse fyre kunne være
stående overalt på scenen

953
00:43:18,240 --> 00:43:20,960
og det er fint, så længe de er
faktisk peger på hinanden,

954
00:43:20,960 --> 00:43:22,770
men at holde tingene
ren og enkel, vi får

955
00:43:22,770 --> 00:43:25,728
bare trække dem venstre til højre som
dette, men der kunne være massive huller

956
00:43:25,728 --> 00:43:26,790
mellem disse knudepunkter.

957
00:43:26,790 --> 00:43:30,710
>> Nu, hvis jeg ønsker at faktisk indsætte nogle
ny værdi, lad os gå videre og gøre dette.

958
00:43:30,710 --> 00:43:33,720
Vi har en mulighed nu
at vælge en anden node.

959
00:43:33,720 --> 00:43:39,820
Sig lad os starte med mallocing 55.

960
00:43:39,820 --> 00:43:41,320
Ville nogen noget imod at være malloc?

961
00:43:41,320 --> 00:43:42,280
OK, kom op.

962
00:43:42,280 --> 00:43:42,992
Hvad er dit navn?

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
Okay.

966
00:43:44,810 --> 00:43:46,600
Malloc Rainbow.

967
00:43:46,600 --> 00:43:47,450
Kom op.

968
00:43:47,450 --> 00:43:51,610
Så nu er vi nødt til at spørge os selv
algoritmisk hvor vi kan sætte 55.

969
00:43:51,610 --> 00:43:53,610
Så alle os vide,
naturligvis, hvor hun sandsynligvis

970
00:43:53,610 --> 00:43:55,401
hører, hvis vi prøver
at holde denne sorteres

971
00:43:55,401 --> 00:43:58,299
og hvis du fyre kunne tage en
skridt tilbage, så vi ikke falder af

972
00:43:58,299 --> 00:43:59,590
scenen, ville det være fantastisk.

973
00:43:59,590 --> 00:44:01,420
Så faktisk, Rainbow,
starte forfra her hos mig,

974
00:44:01,420 --> 00:44:04,200
fordi vi som computeren nu kan
kun se én variabel ad gangen.

975
00:44:04,200 --> 00:44:05,190
Så hvis dette er det første knudepunkt.

976
00:44:05,190 --> 00:44:07,160
Bemærk, han er ikke en knude,
han er bare en pointer,

977
00:44:07,160 --> 00:44:10,270
og det er derfor han er draget til at være
kun størrelsen af ​​en pegepind, ikke

978
00:44:10,270 --> 00:44:11,780
en af ​​de fulde rektangler.

979
00:44:11,780 --> 00:44:16,650
Så vi kommer til at kontrollere på hvert
iteration er 55 mindre end 9?

980
00:44:16,650 --> 00:44:17,150
Nej.

981
00:44:17,150 --> 00:44:19,060
Er 55 mindre end 17?

982
00:44:19,060 --> 00:44:19,720
Nej.

983
00:44:19,720 --> 00:44:20,800
Mindre end 22?

984
00:44:20,800 --> 00:44:22,020
Mindre end 26?

985
00:44:22,020 --> 00:44:23,390
Mindre end 34?

986
00:44:23,390 --> 00:44:25,890
Og så nu, naturligvis
Rainbow hører i slutningen.

987
00:44:25,890 --> 00:44:27,270
Så for at være klar, og hvad
var dit navn, Taylor?

988
00:44:27,270 --> 00:44:27,895
>> TAYLOR: Taylor.

989
00:44:27,895 --> 00:44:32,510
DAVID MALAN: Så blandt Taylors
venstre hånd og Rainbow hænder her,

990
00:44:32,510 --> 00:44:38,324
hvis hånd har brug for at pege på, hvad der i
For at indsætte 55 i denne liste?

991
00:44:38,324 --> 00:44:39,240
Hvad skal vi gøre?

992
00:44:39,240 --> 00:44:39,700
Ja?

993
00:44:39,700 --> 00:44:41,140
>> PUBLIKUM: Taylors hånd
nødt til at pege til venstre.

994
00:44:41,140 --> 00:44:41,680
>> DAVID MALAN: Præcis.

995
00:44:41,680 --> 00:44:43,800
Så indsætter en node
ind i enden af ​​listen

996
00:44:43,800 --> 00:44:47,140
er ret enkel, fordi Taylor bare
skal pege i stedet for på jorden

997
00:44:47,140 --> 00:44:49,640
eller vi vil kalde det null,
null er sortering af fraværet

998
00:44:49,640 --> 00:44:51,640
af en pegepind eller en speciel
nul pointer, du er

999
00:44:51,640 --> 00:44:53,740
kommer til at pege med venstre
hånd på Rainbow og derefter Rainbow,

1000
00:44:53,740 --> 00:44:55,910
Hvor skal din venstre
hånd formentlig pege?

1001
00:44:55,910 --> 00:44:56,570
Ned.

1002
00:44:56,570 --> 00:45:00,140
Det er ikke godt, hvis hendes hånd er sortering
at pege off her eller slags enhver

1003
00:45:00,140 --> 00:45:00,640
hvilken vej.

1004
00:45:00,640 --> 00:45:02,407
Det ville blive betragtet
en skraldespand værdi,

1005
00:45:02,407 --> 00:45:04,240
men hvis hun peger på
nogle kendte værdi, vi får

1006
00:45:04,240 --> 00:45:07,360
kalder det nul eller nul, det er OK
fordi vi har et begreb i denne

1007
00:45:07,360 --> 00:45:09,390
og vi ved listen er nu færdig.

1008
00:45:09,390 --> 00:45:11,550
>> Så hvad er en anden
forholdsvis enkel sag?

1009
00:45:11,550 --> 00:45:13,125
Kunne vi malloc 5?

1010
00:45:13,125 --> 00:45:14,010
Kom op.

1011
00:45:14,010 --> 00:45:14,782
Hvad er dit navn?

1012
00:45:14,782 --> 00:45:15,490
Tiffany: Tiffany.

1013
00:45:15,490 --> 00:45:16,000
DAVID MALAN: Jeg er ked af?

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
Okay.

1017
00:45:17,110 --> 00:45:19,071
Tiffany er blevet malloced
med værdien 5.

1018
00:45:19,071 --> 00:45:19,570
Kom op.

1019
00:45:19,570 --> 00:45:23,820
Denne ene er forholdsvis let også, men
lad os overveje rækkefølgen af ​​operationer nu.

1020
00:45:23,820 --> 00:45:25,820
Det var temmelig let
med Taylor i slutningen.

1021
00:45:25,820 --> 00:45:30,302
Nummer 5 er naturligvis mindre end 9,
og så har vi David, vi har Tiffany,

1022
00:45:30,302 --> 00:45:31,260
og hvad var dit navn?

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, og David.

1026
00:45:34,300 --> 00:45:36,580
Hvis hånd bør opdateres først?

1027
00:45:36,580 --> 00:45:39,260

1028
00:45:39,260 --> 00:45:40,590
Hvad vil du gøre her?

1029
00:45:40,590 --> 00:45:45,244
Der er et par mulige måder, men
der er også en eller flere forkerte måder.

1030
00:45:45,244 --> 00:45:46,620
>> PUBLIKUM: Start med længst til venstre.

1031
00:45:46,620 --> 00:45:47,800
>> DAVID MALAN: Start med den længst til venstre.

1032
00:45:47,800 --> 00:45:49,008
Hvem er den længst til venstre her så?

1033
00:45:49,008 --> 00:45:49,700
PUBLIKUM: Først.

1034
00:45:49,700 --> 00:45:50,366
>> DAVID MALAN: OK.

1035
00:45:50,366 --> 00:45:53,781
Så start med først og hvor har du
vil opdatere Davids hænder til at være?

1036
00:45:53,781 --> 00:45:54,780
PUBLIKUM: Mod 5.

1037
00:45:54,780 --> 00:45:55,446
DAVID MALAN: OK.

1038
00:45:55,446 --> 00:45:59,026
Så David, punkt fem
eller Tiffany her, og nu?

1039
00:45:59,026 --> 00:46:01,072
>> PUBLIKUM: Tiffany peger på 9?

1040
00:46:01,072 --> 00:46:04,030
DAVID MALAN: Perfekt, undtagen Binky s
leder bare lidt faldt, ikke?

1041
00:46:04,030 --> 00:46:06,820
For hvad er der galt med
dette billede bogstaveligt?

1042
00:46:06,820 --> 00:46:08,070
PUBLIKUM: Ingenting peger.

1043
00:46:08,070 --> 00:46:09,945
DAVID MALAN: Intet er
peger på Jake nu.

1044
00:46:09,945 --> 00:46:13,360
Vi har bogstaveligt forældreløse 9
og 17, og vi har bogstaveligt talt

1045
00:46:13,360 --> 00:46:18,450
lækket hele denne hukommelse, fordi ved
opdatering Davids hånd først, det er

1046
00:46:18,450 --> 00:46:21,660
fint så vidt som det er korrekt
peger på Tiffany nu,

1047
00:46:21,660 --> 00:46:25,410
men hvis ingen havde
fremsyn til at pege på Jake,

1048
00:46:25,410 --> 00:46:27,490
så har vi mistet
helhed af denne liste.

1049
00:46:27,490 --> 00:46:28,200
Så lad os fortryde.

1050
00:46:28,200 --> 00:46:30,950
Så det var en god ting at
tur over men lad os rette nu.

1051
00:46:30,950 --> 00:46:33,624
Hvad skal vi gøre først i stedet?

1052
00:46:33,624 --> 00:46:34,124
Ja?

1053
00:46:34,124 --> 00:46:35,791
>> PUBLIKUM: Tiffany skal pege på 9?

1054
00:46:35,791 --> 00:46:37,582
DAVID MALAN: Jeg kan ikke
få det tæt på dig.

1055
00:46:37,582 --> 00:46:38,720
Hvem skal pege på 9?

1056
00:46:38,720 --> 00:46:39,220
>> PUBLIKUM: Tiffany.

1057
00:46:39,220 --> 00:46:39,390
>> DAVID MALAN: Okay.

1058
00:46:39,390 --> 00:46:41,200
Så Tiffany bør første punkt på 9.

1059
00:46:41,200 --> 00:46:43,550
Så Tiffany bør tage
på en identisk værdi

1060
00:46:43,550 --> 00:46:45,820
til David, som synes
overflødige for et øjeblik,

1061
00:46:45,820 --> 00:46:48,820
men det er fint, fordi nu, andet
skridt, kan vi opdatere Davids hånd

1062
00:46:48,820 --> 00:46:52,680
at pege på Tiffany, og derefter, hvis
vi lige slags ren tingene op

1063
00:46:52,680 --> 00:46:55,740
som om dette er slags forår-lignende,
nu det er en korrekt isætning.

1064
00:46:55,740 --> 00:46:56,700
Så fremragende.

1065
00:46:56,700 --> 00:46:57,970
Så nu er vi der næsten.

1066
00:46:57,970 --> 00:47:01,075
Lad os indsætte en sidste
værdi som værdien 20.

1067
00:47:01,075 --> 00:47:03,010
Hvis vi kunne malloc et sidste volontør?

1068
00:47:03,010 --> 00:47:04,140
Kom op.

1069
00:47:04,140 --> 00:47:06,224
Så denne ene er lidt mere tricky.

1070
00:47:06,224 --> 00:47:08,390
Men virkelig, koden er vi
skrivning, omend verbalt,

1071
00:47:08,390 --> 00:47:10,610
er lige som at have en flok
af hvis betingelserne nu, ikke?

1072
00:47:10,610 --> 00:47:12,318
Vi havde en tilstand
kontrollere, om det tilhører

1073
00:47:12,318 --> 00:47:13,840
ved udgangen, måske begyndelsen.

1074
00:47:13,840 --> 00:47:15,940
Vi har brug for en form for løkke til
finde det punkt i midten.

1075
00:47:15,940 --> 00:47:17,400
Så lad os gøre det med, hvad er dit navn?

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
Dejligt at møde dig.

1080
00:47:19,368 --> 00:47:20,490
Så vi har 20.

1081
00:47:20,490 --> 00:47:21,220
Mindre end fem?

1082
00:47:21,220 --> 00:47:21,530
Nej.

1083
00:47:21,530 --> 00:47:22,160
Mindre end ni?

1084
00:47:22,160 --> 00:47:22,410
Nej.

1085
00:47:22,410 --> 00:47:23,050
Mindre end 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ører til her og
jeres navne igen er?

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, og?

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
Hvis hænder har brug for at få opdateret først?

1096
00:47:32,140 --> 00:47:32,930
>> PUBLIKUM: Eric.

1097
00:47:32,930 --> 00:47:33,429
OK.

1098
00:47:33,429 --> 00:47:35,200
Så Erics skal pege på, hvor?

1099
00:47:35,200 --> 00:47:35,930
Ved 22.

1100
00:47:35,930 --> 00:47:36,430
Godt.

1101
00:47:36,430 --> 00:47:38,180
Og nu, hvad det næste?

1102
00:47:38,180 --> 00:47:40,800
Sue kan derefter pege på Eric
og nu, hvis du fyre bare

1103
00:47:40,800 --> 00:47:44,077
gøre nogle rum, som er fint
visuelt, nu vi har gjort indsættelsen.

1104
00:47:44,077 --> 00:47:47,160
Så lad os nu overveje et spørgsmål, men
tak så meget for vores frivillige.

1105
00:47:47,160 --> 00:47:48,090
Meget godt klaret.

1106
00:47:48,090 --> 00:47:50,831
Du kan holde dem, hvis du vil.

1107
00:47:50,831 --> 00:47:54,140
Og vi har en dejlig afsked gave, hvis
du gerne hver gerne tage en stress bold.

1108
00:47:54,140 --> 00:47:56,030
Lad mig blot videregive dette ned.

1109
00:47:56,030 --> 00:47:58,430
Så hvad er takeaway dette?

1110
00:47:58,430 --> 00:48:02,430
Dette synes at være fantastisk
for så vidt vi har nu

1111
00:48:02,430 --> 00:48:06,360
indført et alternativ til en
array, der ikke er så begrænset

1112
00:48:06,360 --> 00:48:07,780
til en matrix af en eller anden fast størrelse.

1113
00:48:07,780 --> 00:48:09,380
De kan vokse dynamisk.

1114
00:48:09,380 --> 00:48:13,220
>> Men meget ligesom vi har set i uger
fortiden, vi aldrig få noget gratis,

1115
00:48:13,220 --> 00:48:15,740
ligesom mon der ikke er en afvejning her.

1116
00:48:15,740 --> 00:48:18,890
Så med en upside på en sammenkædet
liste, er denne dynamik?

1117
00:48:18,890 --> 00:48:21,590
Denne evne til at vokse og helt ærligt,
vi kunne have gjort sletning

1118
00:48:21,590 --> 00:48:23,570
og vi kunne skrumpe efter behov.

1119
00:48:23,570 --> 00:48:24,710
Hvilken pris betaler vi?

1120
00:48:24,710 --> 00:48:28,510

1121
00:48:28,510 --> 00:48:30,340
Dobbelt så meget plads, først og fremmest.

1122
00:48:30,340 --> 00:48:34,010
Hvis du ser på billedet, der ikke længere
er jeg lagring af en liste af heltal.

1123
00:48:34,010 --> 00:48:36,740
Jeg lagring af en liste over
heltal plus pointere.

1124
00:48:36,740 --> 00:48:38,240
Så jeg fordoble mængden af ​​plads.

1125
00:48:38,240 --> 00:48:40,740
Nu, måske det er ikke sådan
en big deal 4 byte, 8 byte,

1126
00:48:40,740 --> 00:48:43,160
men det kunne sikkert tilføje
op til store datasæt.

1127
00:48:43,160 --> 00:48:45,570
Hvad er en anden ulempe?

1128
00:48:45,570 --> 00:48:46,070
Ja?

1129
00:48:46,070 --> 00:48:48,010
>> PUBLIKUM: Vi er nødt til
krydse dem én efter én.

1130
00:48:48,010 --> 00:48:48,760
DAVID MALAN: Ja.

1131
00:48:48,760 --> 00:48:50,260
Vi er nødt til at krydse dem én efter én.

1132
00:48:50,260 --> 00:48:53,860
Ved du hvad, vi gav op denne super
praktisk funktion af firkantede beslag

1133
00:48:53,860 --> 00:48:57,240
notation, mere korrekt
kendt som random access,

1134
00:48:57,240 --> 00:48:59,280
hvor vi bare kan hoppe
til et enkelt element

1135
00:48:59,280 --> 00:49:01,470
men nu, hvis jeg stadig havde
mine frivillige her,

1136
00:49:01,470 --> 00:49:04,660
hvis jeg ønskede at finde den
nummer 22, jeg kan ikke bare

1137
00:49:04,660 --> 00:49:06,620
springe til konsollen noget noget.

1138
00:49:06,620 --> 00:49:10,530
Jeg er nødt til at kigge over listen, meget
ligesom vores søge eksempler lineært,

1139
00:49:10,530 --> 00:49:12,260
at finde nummeret 22.

1140
00:49:12,260 --> 00:49:14,340
Så vi synes at have betalt en pris der.

1141
00:49:14,340 --> 00:49:16,430
Men vi kan alligevel
løse andre problemer.

1142
00:49:16,430 --> 00:49:18,587
>> Faktisk, lad mig introducere
blot et par visuals.

1143
00:49:18,587 --> 00:49:20,920
Så hvis du har været ned til
Mathers Dining Hall for nylig,

1144
00:49:20,920 --> 00:49:23,320
vil du huske, at deres
stakke af bakker som denne,

1145
00:49:23,320 --> 00:49:26,300
vi lånt disse fra
Annenberg før klassen.

1146
00:49:26,300 --> 00:49:28,930
Så denne stablen af ​​bakker, men
repræsenterer faktisk

1147
00:49:28,930 --> 00:49:30,860
af en computer science datastruktur.

1148
00:49:30,860 --> 00:49:32,910
Der er en datastruktur
i datalogi

1149
00:49:32,910 --> 00:49:38,010
kendt som en stak, som meget pænt
egner sig til netop denne visuelle.

1150
00:49:38,010 --> 00:49:41,380
Så hvis hver af disse bakker er ikke en
bakke men ligesom et nummer og jeg ønskede

1151
00:49:41,380 --> 00:49:45,010
at lagre numre, I
kunne sætte en hernede,

1152
00:49:45,010 --> 00:49:48,320
og jeg kunne sætte en anden hernede,
og fortsætte stabling numre

1153
00:49:48,320 --> 00:49:53,180
oven på hinanden, og hvad der er
potentielt nyttigt om dette

1154
00:49:53,180 --> 00:49:55,450
er, at hvad er konsekvenserne
af denne datastruktur?

1155
00:49:55,450 --> 00:49:58,045
Hvilket nummer kan jeg trække sig ud
første mest hensigtsmæssigt?

1156
00:49:58,045 --> 00:50:00,640

1157
00:50:00,640 --> 00:50:03,030
Den senest én sat på der.

1158
00:50:03,030 --> 00:50:06,430
>> Så dette er, hvad vi ville kalde i
datalogi en LIFO datastruktur.

1159
00:50:06,430 --> 00:50:08,070
Sidste ind, først ud.

1160
00:50:08,070 --> 00:50:10,800
Og vi vil se inden længe, ​​hvorfor
som kan være nyttige, men for nu,

1161
00:50:10,800 --> 00:50:12,200
lige overveje ejendommen.

1162
00:50:12,200 --> 00:50:15,158
Og det er lidt dum, hvis du tror
om, hvordan den spisesal gør det.

1163
00:50:15,158 --> 00:50:17,910
Hver gang de rene bakker og
sætte de friskeste dem på toppen,

1164
00:50:17,910 --> 00:50:22,160
du kunne have en tidligere rent
men til sidst meget beskidt og støvede

1165
00:50:22,160 --> 00:50:24,360
bakke i bunden
hvis du aldrig faktisk

1166
00:50:24,360 --> 00:50:26,820
komme til bunden af ​​denne
stak, fordi du bare

1167
00:50:26,820 --> 00:50:29,380
holde lægge det nye og
ren dem oven på den.

1168
00:50:29,380 --> 00:50:31,840
Det samme kan ske
i et supermarked også.

1169
00:50:31,840 --> 00:50:35,450
Hvis du har en montre
mælk og hver gang CVS

1170
00:50:35,450 --> 00:50:37,610
eller hvem får mere mælk,
du bare puffe de mælk

1171
00:50:37,610 --> 00:50:39,880
du allerede har til bagsiden og
du sætte de nye op foran,

1172
00:50:39,880 --> 00:50:43,088
du kommer til at have nogle temmelig ubehagelig
mælk ved udgangen af ​​den datastruktur,

1173
00:50:43,088 --> 00:50:46,390
fordi det er altid i bunden eller
ækvivalent det er altid på bagsiden.

1174
00:50:46,390 --> 00:50:50,407
>> Men der er en anden måde at tænke på
foring op data og for eksempel, dette.

1175
00:50:50,407 --> 00:50:53,490
Hvis du er en af ​​de mennesker, der kan lide
at line op uden for Apple butikker

1176
00:50:53,490 --> 00:50:55,610
når et nyt produkt kommer
ud, er du sandsynligvis

1177
00:50:55,610 --> 00:50:58,780
ikke bruger en stak af data
struktur, fordi du

1178
00:50:58,780 --> 00:51:03,070
ville fremmedgøre alle andre, der er
kø for at købe nogle nye legetøj.

1179
00:51:03,070 --> 00:51:06,610
Snarere, er du sandsynligvis bruge
hvilken slags datastruktur

1180
00:51:06,610 --> 00:51:10,050
eller hvilken form for systemet
i den virkelige verden?

1181
00:51:10,050 --> 00:51:13,493
Forhåbentlig er det en linje, eller mere
korrekt, eller mere britisk-lignende, en kø.

1182
00:51:13,493 --> 00:51:17,700
Og det viser sig en kø er også en
datastruktur i datalogi,

1183
00:51:17,700 --> 00:51:19,700
men en kø har en meget
anden egenskab.

1184
00:51:19,700 --> 00:51:20,820
Det er ikke LIFO.

1185
00:51:20,820 --> 00:51:21,990
Sidste ind, først ud.

1186
00:51:21,990 --> 00:51:22,800
Gud forbyde.

1187
00:51:22,800 --> 00:51:24,280
Det er i stedet FIFO.

1188
00:51:24,280 --> 00:51:26,110
Først ind, først ud.

1189
00:51:26,110 --> 00:51:27,970
Og det er en god ting
for retfærdighed 'skyld

1190
00:51:27,970 --> 00:51:30,428
sikkert, når du foring
op super tidligt om morgenen.

1191
00:51:30,428 --> 00:51:33,400
Hvis du får der først, du
ønsker at komme ud først så godt.

1192
00:51:33,400 --> 00:51:35,880
>> Og så alle disse data
strukturer, køer og stakke

1193
00:51:35,880 --> 00:51:39,220
og klaser af andre, viser sig du
kan tænke på det som bare et array.

1194
00:51:39,220 --> 00:51:41,820
Dette er en matrix, måske
en fast størrelse 4, men det ville

1195
00:51:41,820 --> 00:51:44,990
være slags rart, hvis vi bare kunne hobe
bakker næsten uendeligt høje, hvis vi

1196
00:51:44,990 --> 00:51:46,780
have så mange bakker eller tal.

1197
00:51:46,780 --> 00:51:48,840
Så måske vil vi
bruge en sammenkædet liste her,

1198
00:51:48,840 --> 00:51:51,800
men trade-off vil være
potentielt at vi har brug for mere hukommelse,

1199
00:51:51,800 --> 00:51:55,930
tager lidt mere tid, men vi
begrænser ikke højden af ​​stablen,

1200
00:51:55,930 --> 00:51:59,550
meget gerne Mathers montre
kan begrænse størrelsen af ​​stakken,

1201
00:51:59,550 --> 00:52:03,117
og så disse er designbeslutninger eller
muligheder til rådighed for os i sidste ende.

1202
00:52:03,117 --> 00:52:04,950
Så med disse data
strukturer, vi har i gang

1203
00:52:04,950 --> 00:52:09,360
se nye øvre grænser potentielt
om, hvad der tidligere var super hurtig

1204
00:52:09,360 --> 00:52:11,260
og hvor vi vil forlade
off dag, og hvor

1205
00:52:11,260 --> 00:52:13,200
vi håber at komme til
er på onsdag, vi får

1206
00:52:13,200 --> 00:52:15,740
begynde at se på en data
struktur, der lader os søge

1207
00:52:15,740 --> 00:52:18,260
gennem data i log sluttidspunkt igen.

1208
00:52:18,260 --> 00:52:21,470
Og vi så, at, husker, i uge nul
og en med binær søgning eller kløft

1209
00:52:21,470 --> 00:52:22,180
og erobre.

1210
00:52:22,180 --> 00:52:26,240
Det kommer tilbage og bedre endnu,
den hellige gral for denne onsdag

1211
00:52:26,240 --> 00:52:29,510
vil være at komme op med den
datastruktur, der kører virkelig

1212
00:52:29,510 --> 00:52:32,070
eller teoretisk i
konstant tid, hvorved

1213
00:52:32,070 --> 00:52:34,760
det er ligegyldigt, hvor mange
millioner eller milliarder af ting

1214
00:52:34,760 --> 00:52:38,470
vi har i datastruktur, vil det
tage os konstant tid, måske et skridt

1215
00:52:38,470 --> 00:52:41,387
eller to trin eller 10 trin,
men konstante antal trin

1216
00:52:41,387 --> 00:52:42,970
at søge gennem den datastruktur.

1217
00:52:42,970 --> 00:52:46,300
Det rent faktisk vil være den hellige gral
men mere om det på onsdag.

1218
00:52:46,300 --> 00:52:49,045
Se ya derefter.

1219
00:52:49,045 --> 00:52:53,704
>> [Musik spiller]

1220
00:52:53,704 --> 00:56:08,448