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

2
00:00:00,500 --> 00:00:11,137
[Musik spiller]

3
00:00:11,137 --> 00:00:12,220
David J. MALAN: Okay.

4
00:00:12,220 --> 00:00:13,950
Dette er CS50.

5
00:00:13,950 --> 00:00:18,560
Det er uge fem fortsat, og vi
har nogle gode nyheder og nogle dårlige nyheder.

6
00:00:18,560 --> 00:00:21,140
Så god nyhed er, at CS50
lancerer denne fredag.

7
00:00:21,140 --> 00:00:24,430
Hvis du ønsker at slutte sig til os,
hovedet til den sædvanlige webadresse her.

8
00:00:24,430 --> 00:00:28,670
Endnu bedre nyheder, ingen foredrag
på mandag den 13..

9
00:00:28,670 --> 00:00:31,970
Lidt mindre bedre nyheder,
quiz nul er næste onsdag.

10
00:00:31,970 --> 00:00:33,840
Flere detaljer kan
findes på denne webadresse her.

11
00:00:33,840 --> 00:00:36,340
Og i løbet af de næste par dage
vi vil udfylde de tomme felter

12
00:00:36,340 --> 00:00:39,234
med hensyn til værelserne
at vi vil have reserveret.

13
00:00:39,234 --> 00:00:41,400
Bedre nyhed er, at der vil
være et kursus for hele anmeldelse

14
00:00:41,400 --> 00:00:43,570
session i det kommende
Mandag i aften.

15
00:00:43,570 --> 00:00:46,270
Hold øje med kursets
hjemmeside for placering og detaljer.

16
00:00:46,270 --> 00:00:49,290
Sektioner, selvom det er en
ferie, også vil mødes så godt.

17
00:00:49,290 --> 00:00:50,490

18
00:00:50,490 --> 00:00:52,940
Bedste nyheder, foredrag næste fredag.

19
00:00:52,940 --> 00:00:56,220
Så dette er en tradition, vi
har, som pr pensum.

20
00:00:56,220 --> 00:00:58,100
Bare-- det vil være fantastisk.

21
00:00:58,100 --> 00:01:02,510
Du vil se ting som
konstant tid datastrukturer

22
00:01:02,510 --> 00:01:04,730
og hash tabeller og træer og forsøger.

23
00:01:04,730 --> 00:01:07,150
Og vi vil tale om fødselsdag problemer.

24
00:01:07,150 --> 00:01:09,440
En hel masse ting
afventer næste fredag.

25
00:01:09,440 --> 00:01:11,212

26
00:01:11,212 --> 00:01:12,200
OK.

27
00:01:12,200 --> 00:01:13,190
Alligevel.

28
00:01:13,190 --> 00:01:17,080
>> Så minde om, at vi har været
fokus på dette billede af, hvad der er

29
00:01:17,080 --> 00:01:18,980
inde i vores computerens hukommelse.

30
00:01:18,980 --> 00:01:22,875
Så hukommelse eller RAM er, hvor programmerne
findes mens du kører dem.

31
00:01:22,875 --> 00:01:25,215
Hvis du dobbeltklikker på en
ikonet for at køre nogle program

32
00:01:25,215 --> 00:01:27,520
eller dobbeltklik på en
ikonet for at åbne nogle fil,

33
00:01:27,520 --> 00:01:30,430
den er indlæst fra din harddisk
drev eller SSD-drev

34
00:01:30,430 --> 00:01:34,190
i RAM, Random Access Memory, hvor
det lever, indtil strømmen går ud,

35
00:01:34,190 --> 00:01:36,700
den bærbare computer låget lukkes,
eller du afslutter programmet.

36
00:01:36,700 --> 00:01:38,960
>> Nu, hukommelse, af
som du sikkert har

37
00:01:38,960 --> 00:01:41,950
1 gigabyte i disse dage, 2
gigabyte, eller endda meget mere,

38
00:01:41,950 --> 00:01:44,420
er generelt fastlagt
for et givet

39
00:01:44,420 --> 00:01:47,170
i denne slags rektangulære
konceptuel model

40
00:01:47,170 --> 00:01:50,860
hvorved vi har stakken på bunden
og en masse andre ting på toppen.

41
00:01:50,860 --> 00:01:53,140
De ting øverst
vi har set på dette billede

42
00:01:53,140 --> 00:01:55,670
før men aldrig talt om
er den såkaldte tekstsegment.

43
00:01:55,670 --> 00:01:58,419
Tekst segment er bare en fancy måde
sige de nuller og ettaller, der

44
00:01:58,419 --> 00:02:01,150
komponere din faktiske kompileret program.

45
00:02:01,150 --> 00:02:03,910
>> Så når du dobbeltklikker
Microsoft Word på din Mac eller pc,

46
00:02:03,910 --> 00:02:08,030
eller når du kører prik skråstreg Mario på en
Linux-computer på dit terminalvindue,

47
00:02:08,030 --> 00:02:12,460
de nuller og ettaller, der udgør
Word eller Mario gemmes midlertidigt

48
00:02:12,460 --> 00:02:16,610
i computerens RAM i den såkaldte
tekstsegment til et bestemt program.

49
00:02:16,610 --> 00:02:19,080
Nedenfor der går initialiseret
og uden startværdi data.

50
00:02:19,080 --> 00:02:22,655
Det er ting som globale variabler,
at vi ikke har brugt mange af,

51
00:02:22,655 --> 00:02:24,910
men lejlighedsvis vi har
havde globale variabler

52
00:02:24,910 --> 00:02:28,819
eller statisk defineret strenge,
er hårdt kodet ord som "Hej"

53
00:02:28,819 --> 00:02:31,860
der er ikke taget ind fra brugeren
der er hard-kodet ind i dit program.

54
00:02:31,860 --> 00:02:34,230
>> Nu ned til bunden vi
har den såkaldte stak.

55
00:02:34,230 --> 00:02:37,665
Og stakken, hidtil, vi har været
hjælp til hvilke typer af formål?

56
00:02:37,665 --> 00:02:39,706

57
00:02:39,706 --> 00:02:40,997
Hvad er stakken blevet brugt til?

58
00:02:40,997 --> 00:02:41,160
Ja?

59
00:02:41,160 --> 00:02:42,070
>> Publikum: Funktioner.

60
00:02:42,070 --> 00:02:43,320
>> David J. MALAN: For funktioner?

61
00:02:43,320 --> 00:02:44,980
I hvilken forstand for funktioner?

62
00:02:44,980 --> 00:02:48,660
>> Publikum: Når du ringer til en funktion,
argumenter er kopieret over på stakken.

63
00:02:48,660 --> 00:02:49,660
>> David J. MALAN: Præcis.

64
00:02:49,660 --> 00:02:52,650
Når du ringer til en funktion, dens
argumenter er kopieret over på stakken.

65
00:02:52,650 --> 00:02:56,330
Så enhver X'er eller Y'er eller A'er eller BS
at du passerer ind i en funktion

66
00:02:56,330 --> 00:02:58,680
midlertidigt sat på
den såkaldte stak,

67
00:02:58,680 --> 00:03:02,000
ligesom en af ​​Annenberg
Dining Hall bakker og også ting

68
00:03:02,000 --> 00:03:03,190
ligesom lokale variable.

69
00:03:03,190 --> 00:03:06,290
Hvis din foo funktion eller din swap
funktion har lokale variabler,

70
00:03:06,290 --> 00:03:08,602
ligesom temp, de to
ender på stakken.

71
00:03:08,602 --> 00:03:11,560
Nu vil vi ikke snakke for meget om
dem, men disse miljøvariabler

72
00:03:11,560 --> 00:03:15,690
nederst oplevede vi et stykke tid siden, da
Jeg var futzing på tastaturet en dag

73
00:03:15,690 --> 00:03:20,050
og jeg begyndte at få adgang til tingene
ligesom argv 100 eller argv 1.000,

74
00:03:20,050 --> 00:03:22,320
bare elements-- jeg glemmer
den numbers-- men at

75
00:03:22,320 --> 00:03:24,330
skulle ikke tilgås af mig.

76
00:03:24,330 --> 00:03:26,581
Vi begyndte at se nogle
funky symboler på skærmen.

77
00:03:26,581 --> 00:03:28,330
Det var såkaldte
miljøvariabler

78
00:03:28,330 --> 00:03:32,390
ligesom de globale indstillinger for min
program eller til min computer, ikke

79
00:03:32,390 --> 00:03:37,090
relateret til den nylige
fejl, som vi diskuterede,

80
00:03:37,090 --> 00:03:39,670
Shellshock, der har været
plager en hel computere.

81
00:03:39,670 --> 00:03:42,960
>> Nu endelig i dagens fokus
vi vil i sidste ende være på bunke.

82
00:03:42,960 --> 00:03:44,864
Dette er en anden luns af hukommelse.

83
00:03:44,864 --> 00:03:47,030
Og fundamentalt alt dette
hukommelse er den samme ting.

84
00:03:47,030 --> 00:03:48,040
Det er den samme hardware.

85
00:03:48,040 --> 00:03:49,956
Vi er bare slags
behandle forskellige klynger

86
00:03:49,956 --> 00:03:51,460
byte til forskellige formål.

87
00:03:51,460 --> 00:03:56,540
Den bunke er også vil være der, hvor
variabler og hukommelse, som du anmoder

88
00:03:56,540 --> 00:03:58,810
fra operativsystemet
opbevares midlertidigt.

89
00:03:58,810 --> 00:04:01,890
>> Men der er lidt af et problem
her, som billedet antyder.

90
00:04:01,890 --> 00:04:05,261
Vi slags har to
skibe om at kollidere.

91
00:04:05,261 --> 00:04:08,010
Fordi som du bruger mere og mere
af stakken, og som vi ser i dag

92
00:04:08,010 --> 00:04:11,800
og fremefter, som du bruger mere og mere af det
dynge, helt sikkert dårlige ting kan ske.

93
00:04:11,800 --> 00:04:15,054
Og ja, vi kan fremkalde det
bevidst eller ubevidst.

94
00:04:15,054 --> 00:04:16,970
Så cliffhanger sidste
tidspunkt var dette program,

95
00:04:16,970 --> 00:04:20,570
som ikke tjener noget funktionelt
andet end at demonstrere formål

96
00:04:20,570 --> 00:04:24,750
hvordan du som en slem fyr rent faktisk kan tage
fordel af fejl i en andens program

97
00:04:24,750 --> 00:04:28,460
og overtage et program eller endda en
hele computeren eller server.

98
00:04:28,460 --> 00:04:31,660
Så bare at kaste et blik, du
bemærke, at hovedsagen i bunden

99
00:04:31,660 --> 00:04:34,510
tager på kommandolinjen
argumenter, som pr argv.

100
00:04:34,510 --> 00:04:38,480
Og det har et kald til en funktion f,
væsentlige en anonym funktion kaldet

101
00:04:38,480 --> 00:04:40,250
f, og den går i argv [1].

102
00:04:40,250 --> 00:04:43,960
>> Så uanset ord brugeren typer i på
prompten efter dette program navn,

103
00:04:43,960 --> 00:04:49,310
og så denne vilkårlige funktion op
top, f, tager i en streng, AKA char *,

104
00:04:49,310 --> 00:04:51,720
som vi er begyndt at diskutere,
og det bare kalder det "bar".

105
00:04:51,720 --> 00:04:53,310
Men vi kunne kalde det noget.

106
00:04:53,310 --> 00:04:57,470
Og så erklærer det, indenfor
f, et array af tegn

107
00:04:57,470 --> 00:04:59,930
kaldet C-- 12 sådanne tegn.

108
00:04:59,930 --> 00:05:03,580
>> Nu ved den historie, jeg fortalte
for et øjeblik siden, hvor i hukommelsen

109
00:05:03,580 --> 00:05:06,720
c, eller er de 12
chars ender?

110
00:05:06,720 --> 00:05:07,570
Bare for at være klar.

111
00:05:07,570 --> 00:05:08,070
Ja?

112
00:05:08,070 --> 00:05:08,590
>> Publikum: på stakken.

113
00:05:08,590 --> 00:05:09,420
>> David J. MALAN: på stakken.

114
00:05:09,420 --> 00:05:10,720
Så c er en lokal variabel.

115
00:05:10,720 --> 00:05:14,079
Vi beder om 12 tegn eller 12 byte.

116
00:05:14,079 --> 00:05:16,120
De kommer til at ende op
på den såkaldte stak.

117
00:05:16,120 --> 00:05:18,530
Nu endelig er denne anden funktion
Det er faktisk temmelig nyttigt,

118
00:05:18,530 --> 00:05:20,571
men vi har ikke rigtig brugt
det selv, strncopy.

119
00:05:20,571 --> 00:05:21,550

120
00:05:21,550 --> 00:05:25,200
Det betyder streng kopi, men
kun n bogstaver, n tegn.

121
00:05:25,200 --> 00:05:31,990
Så n tegn vil være
kopieret fra bar til ca.

122
00:05:31,990 --> 00:05:32,980
Og hvor mange?

123
00:05:32,980 --> 00:05:34,110
Længden af ​​baren.

124
00:05:34,110 --> 00:05:36,330
Så med andre ord, at
én linje, strncopy,

125
00:05:36,330 --> 00:05:39,500
kommer til at kopiere
effektivt bar i til c.

126
00:05:39,500 --> 00:05:42,340
>> Nu, bare at slags forudse
moralen i denne historie,

127
00:05:42,340 --> 00:05:44,750
hvad der er potentielt problematiske her?

128
00:05:44,750 --> 00:05:49,710
Selvom vi tjekker længden
bar og passerer det ind strncopy,

129
00:05:49,710 --> 00:05:53,145
hvad er din tarm fortæller dig er
stadig brudt om dette program?

130
00:05:53,145 --> 00:05:54,410

131
00:05:54,410 --> 00:05:55,220
Ja?

132
00:05:55,220 --> 00:05:57,491
>> Publikum: Indeholder ikke
plads til nul-karakteren.

133
00:05:57,491 --> 00:05:59,990
David J. MALAN: Indeholder ikke
plads til nul-karakteren.

134
00:05:59,990 --> 00:06:02,073
Potentielt, i modsætning til
tidligere praksis, vi ikke engang

135
00:06:02,073 --> 00:06:04,810
har så meget som et plus 1 til
rumme at null-tegn.

136
00:06:04,810 --> 00:06:06,649
Men det er endnu værre end det.

137
00:06:06,649 --> 00:06:07,940
Hvad skal vi ellers ikke at gøre?

138
00:06:07,940 --> 00:06:08,432
Ja?

139
00:06:08,432 --> 00:06:09,307
>> Publikum: [uhørligt]

140
00:06:09,307 --> 00:06:15,440

141
00:06:15,440 --> 00:06:16,440
David J. MALAN: Perfect.

142
00:06:16,440 --> 00:06:18,490
Vi har hårdt kodet 12 temmelig vilkårligt.

143
00:06:18,490 --> 00:06:19,497

144
00:06:19,497 --> 00:06:21,330
Det er ikke så meget
problem, men det faktum,

145
00:06:21,330 --> 00:06:25,630
at vi ikke selv kontrollere, om
længden af ​​linjen er mindre end 12,

146
00:06:25,630 --> 00:06:28,530
i hvilket tilfælde det vil være
sikkert at sætte det ind i hukommelsen

147
00:06:28,530 --> 00:06:30,260
kaldet C, som vi har tildelt.

148
00:06:30,260 --> 00:06:32,960
Faktisk, hvis bar er ligesom
20 tegn lange,

149
00:06:32,960 --> 00:06:39,010
denne funktion synes at kopiere
20 tegn fra bar til C, og dermed

150
00:06:39,010 --> 00:06:41,310
at tage mindst 8 bytes
at det ikke bør være.

151
00:06:41,310 --> 00:06:42,690
Det er underforstået her.

152
00:06:42,690 --> 00:06:44,347
>> Så kort, brudte program.

153
00:06:44,347 --> 00:06:45,180
Ikke sådan en big deal.

154
00:06:45,180 --> 00:06:46,360
Måske får du en segmentering fejl.

155
00:06:46,360 --> 00:06:47,651
Vi har alle haft fejl i programmer.

156
00:06:47,651 --> 00:06:50,196
Vi har alle kunne have bugs
i programmer lige nu.

157
00:06:50,196 --> 00:06:51,320
Men hvad er konsekvenserne?

158
00:06:51,320 --> 00:06:54,390
Nå, her er en zoomet ind version af
at billede af min computers hukommelse.

159
00:06:54,390 --> 00:06:56,230
Dette er bunden af ​​min stak.

160
00:06:56,230 --> 00:06:59,644
Og ja, allernederst er, hvad der er
kaldet forælder rutine stak, fancy måde

161
00:06:59,644 --> 00:07:00,560
for at sige, det er vigtigste.

162
00:07:00,560 --> 00:07:03,772
Så hvem kaldte funktion
f, som vi taler om.

163
00:07:03,772 --> 00:07:05,230
Så er bunden af ​​stakken.

164
00:07:05,230 --> 00:07:06,640
Returadresse er noget nyt.

165
00:07:06,640 --> 00:07:08,810
Det har altid været der,
altid været i det billede.

166
00:07:08,810 --> 00:07:10,440
Vi har bare aldrig gjort opmærksom på det.

167
00:07:10,440 --> 00:07:15,290
Fordi det viser sig, den måde C værker er
at når en funktion kalder en anden,

168
00:07:15,290 --> 00:07:18,780
ikke kun gøre de argumenter, der
funktion blive skubbet på stakken,

169
00:07:18,780 --> 00:07:22,470
ikke kun gøre funktionens lokale
variabler bliver skubbet på stakken,

170
00:07:22,470 --> 00:07:26,820
noget, der hedder en returadresse
også bliver sat på stakken.

171
00:07:26,820 --> 00:07:33,330
Specifikt om de vigtigste opkald Foo, Mains
egen adresse i hukommelsen, okse noget,

172
00:07:33,330 --> 00:07:38,240
effektivt bliver sat på stakken
således at når f er færdig køre den

173
00:07:38,240 --> 00:07:43,630
ved hvor man kan hoppe tilbage til i teksten
segmentet for at fortsætte udførelsen.

174
00:07:43,630 --> 00:07:47,760
>> Så hvis vi er her begrebsmæssigt,
i hoved, så f bliver kaldt.

175
00:07:47,760 --> 00:07:50,200
Hvordan f vide, hvem
til håndbetjening tilbage?

176
00:07:50,200 --> 00:07:52,020
Nå, denne lille
brødkrumme i rødt her,

177
00:07:52,020 --> 00:07:54,978
kaldet returadresse, det bare
checks, hvad er det returadresse?

178
00:07:54,978 --> 00:07:57,039
Åh, lad mig springe tilbage til hoved her.

179
00:07:57,039 --> 00:07:59,080
Og det er en lille smule
af en oversimplificering,

180
00:07:59,080 --> 00:08:00,750
fordi de nuller og ettaller
for vigtigste er teknisk

181
00:08:00,750 --> 00:08:01,967
heroppe i tech-segmentet.

182
00:08:01,967 --> 00:08:03,800
Men det er den idé. f
bare har at vide, hvad

183
00:08:03,800 --> 00:08:06,680
hvor kontrol i sidste ende går tilbage.

184
00:08:06,680 --> 00:08:09,790
>> Men den måde computere
har længe lagt ud ting

185
00:08:09,790 --> 00:08:12,320
ligesom lokale variable og
argumenter er ligesom dette.

186
00:08:12,320 --> 00:08:17,180
Så i toppen af ​​dette billede i
blå er stakken ramme til f, så alle

187
00:08:17,180 --> 00:08:19,630
af hukommelsen, at f
specifikt er bruger.

188
00:08:19,630 --> 00:08:22,990
Så derfor bemærke, at
bar er i dette billede.

189
00:08:22,990 --> 00:08:23,980
Bar var sit argument.

190
00:08:23,980 --> 00:08:27,240
Og vi påstod, at argumenterne til
funktioner bliver skubbet på stakken.

191
00:08:27,240 --> 00:08:29,910
Og C, selvfølgelig, er
også på dette billede.

192
00:08:29,910 --> 00:08:33,520
>> Og bare for notational formål,
mærke i øverste venstre hjørne

193
00:08:33,520 --> 00:08:37,020
er, hvad der ville være c beslag 0 og
derefter lidt ned til højre

194
00:08:37,020 --> 00:08:38,220
er c beslag 11.

195
00:08:38,220 --> 00:08:41,240
Så med andre ord, kan du forestille dig
at der er et gitter af bytes

196
00:08:41,240 --> 00:08:44,380
der for det første som er
øverst til venstre, bund

197
00:08:44,380 --> 00:08:48,360
er den sidste af de 12 byte.

198
00:08:48,360 --> 00:08:49,930
>> Men nu forsøge at spole frem.

199
00:08:49,930 --> 00:08:55,580
Hvad er ved at ske, hvis vi passerer
i en streng bar, der er længere end C?

200
00:08:55,580 --> 00:08:59,130
Og vi er ikke at kontrollere, om
Det er faktisk længere end 12.

201
00:08:59,130 --> 00:09:03,146
Hvilken del af dette billede vil
bliver overskrevet af byte 0, 1, 2, 3,

202
00:09:03,146 --> 00:09:07,890
dot dot dot, 11, og derefter
dårlig, 12, 13 til 19?

203
00:09:07,890 --> 00:09:11,820
Hvad kommer til at ske her,
hvis du udlede af bestilling

204
00:09:11,820 --> 00:09:14,790
at c beslag 0 er på toppen
og c beslag 11 er slags ned

205
00:09:14,790 --> 00:09:15,812
til højre?

206
00:09:15,812 --> 00:09:16,796
Ja?

207
00:09:16,796 --> 00:09:19,260
>> PUBLIKUM: Jamen, det vil
at overskrive char * baren.

208
00:09:19,260 --> 00:09:22,260
>> David J. MALAN: Ja, det ligner
du kommer til at overskrive char * bar.

209
00:09:22,260 --> 00:09:26,245
Og værre, hvis du sender i en virkelig lang
streng, kan du endda overskrive hvad?

210
00:09:26,245 --> 00:09:27,460

211
00:09:27,460 --> 00:09:28,570
Returadressen.

212
00:09:28,570 --> 00:09:31,380
Hvilket igen, er ligesom en
brødkrumme at fortælle programmet, hvor

213
00:09:31,380 --> 00:09:34,060
at gå tilbage til når f
gøres bliver kaldt.

214
00:09:34,060 --> 00:09:37,140
>> Så hvad skurkene typisk gør
er, hvis de kommer på tværs af et program

215
00:09:37,140 --> 00:09:41,290
at de er nysgerrige om det er
udnytte, buggy på en sådan måde

216
00:09:41,290 --> 00:09:43,550
at han eller hun kan tage
fordel af denne fejl,

217
00:09:43,550 --> 00:09:45,720
generelt de ikke får
dette rigtigt første gang.

218
00:09:45,720 --> 00:09:48,590
De bare begynde at sende, for eksempel,
tilfældige strenge i dit program,

219
00:09:48,590 --> 00:09:50,260
enten på tastaturet,
eller ærligt de sandsynligvis

220
00:09:50,260 --> 00:09:52,740
skrive et lille program til bare
automatisk generere strygere,

221
00:09:52,740 --> 00:09:55,430
og begynde at slå på dit program ved
at sende masser af forskellige indgange

222
00:09:55,430 --> 00:09:56,340
ved forskellige længder.

223
00:09:56,340 --> 00:09:58,990
>> Så snart dit program går ned,
det er en fantastisk ting.

224
00:09:58,990 --> 00:10:01,020
Fordi det betyder, at han
eller hun har opdaget

225
00:10:01,020 --> 00:10:02,660
hvad der formentlig er faktisk en fejl.

226
00:10:02,660 --> 00:10:05,830
Og så de kan få mere klog
og begynde at fokusere mere snævert

227
00:10:05,830 --> 00:10:07,420
om, hvordan at udnytte denne fejl.

228
00:10:07,420 --> 00:10:11,480
Især hvad han eller hun kan
gøre er at sende, i bedste fald, hej.

229
00:10:11,480 --> 00:10:12,210
Nogen big deal.

230
00:10:12,210 --> 00:10:14,750
Det er en streng, der er tilstrækkelig kort.

231
00:10:14,750 --> 00:10:18,100
Men hvad nu, hvis han eller hun sender,
og vi vil generalisere det som,

232
00:10:18,100 --> 00:10:20,890
angreb code-- så nuller
og dem, der gør tingene

233
00:10:20,890 --> 00:10:25,150
ligesom rm-rf, der fjerner alt
fra harddisken eller sende spam

234
00:10:25,150 --> 00:10:27,000
eller anden måde at angribe maskinen?

235
00:10:27,000 --> 00:10:29,570
>> Så hvis hver af disse
bogstaverne A bare repræsenterer,

236
00:10:29,570 --> 00:10:32,380
konceptuelt, angreb, angreb,
angreb, angreb, nogle dårlige kode

237
00:10:32,380 --> 00:10:36,410
at en anden skrev, men
hvis denne person er smart nok

238
00:10:36,410 --> 00:10:40,790
til ikke kun at omfatte alle
disse rm-RFS, men også

239
00:10:40,790 --> 00:10:46,100
har hans eller hendes sidste par bytes
være et nummer, der svarer

240
00:10:46,100 --> 00:10:50,540
til adressen på hans
eller hendes eget angreb kode

241
00:10:50,540 --> 00:10:53,820
at han eller hun gik i bare
ved at give den ved prompten,

242
00:10:53,820 --> 00:10:58,760
du effektivt kan narre computeren
i at lægge mærke til, når f er færdig udførelse,

243
00:10:58,760 --> 00:11:02,400
Åh, det er tid for mig til at hoppe
tilbage til den røde returadresse.

244
00:11:02,400 --> 00:11:06,070
Men fordi han eller hun har en eller anden måde
overlappede denne returadresse

245
00:11:06,070 --> 00:11:09,602
med deres eget nummer,
og de er smart nok

246
00:11:09,602 --> 00:11:11,560
har konfigureret at
nummer til at henvise, som du

247
00:11:11,560 --> 00:11:13,740
se i super top
venstre hjørne er der,

248
00:11:13,740 --> 00:11:18,020
den faktiske adresse i computerens
hukommelse nogle af deres angreb kode,

249
00:11:18,020 --> 00:11:21,740
en slem fyr kan narre computeren
i udførelsen af ​​hans eller hendes egen kode.

250
00:11:21,740 --> 00:11:23,700
>> Og denne kode, igen, kan være alt.

251
00:11:23,700 --> 00:11:26,120
Det er generelt kaldes
shell kode, som er lige

252
00:11:26,120 --> 00:11:29,030
en måde at sige, at det ikke er
generelt noget så simpelt som RM-RF.

253
00:11:29,030 --> 00:11:32,340
Det er faktisk noget som Bash,
eller et program, der giver ham

254
00:11:32,340 --> 00:11:37,230
eller hendes programmatisk kontrol at udføre
noget andet, som de vil.

255
00:11:37,230 --> 00:11:40,210
Så kort sagt, alt dette
stammer fra den simple kendsgerning,

256
00:11:40,210 --> 00:11:44,490
at denne fejl er involveret ikke kontrol
grænserne for dit array.

257
00:11:44,490 --> 00:11:47,250
Og fordi den måde
computere arbejde er, at de

258
00:11:47,250 --> 00:11:49,430
bruge stakken fra
effektivt, begrebsmæssigt,

259
00:11:49,430 --> 00:11:54,830
bund på op, men derefter elementer
du skubber ind på stakken vokse oppefra og ned,

260
00:11:54,830 --> 00:11:56,624
dette er utroligt problematisk.

261
00:11:56,624 --> 00:11:58,290
Nu er der måder at arbejde omkring dette.

262
00:11:58,290 --> 00:12:00,800
Og helt ærligt, er der sprog
med til at løse dette.

263
00:12:00,800 --> 00:12:03,100
Java er immun for eksempel
til dette særlige spørgsmål.

264
00:12:03,100 --> 00:12:04,110
Fordi de ikke give dig fingerpeg.

265
00:12:04,110 --> 00:12:05,943
De give ikke dig
Direct Memory adresser.

266
00:12:05,943 --> 00:12:08,560
Så med denne magt, at vi har
at røre noget i hukommelsen

267
00:12:08,560 --> 00:12:11,580
vi ønsker kommer ganske vist stor risiko.

268
00:12:11,580 --> 00:12:12,430
>> Så hold øje.

269
00:12:12,430 --> 00:12:14,596
Hvis helt ærligt, i de kommende måneder
eller år at komme, når som helst

270
00:12:14,596 --> 00:12:17,740
du læse om nogle udnyttelse
af et program eller en server,

271
00:12:17,740 --> 00:12:22,370
hvis du nogensinde ser en antydning af noget
som en buffer overflow angreb,

272
00:12:22,370 --> 00:12:25,390
eller stakoverløb er en anden type
for angreb, der ligner i ånden,

273
00:12:25,390 --> 00:12:28,770
meget, som inspirerer webstedets
navnet, hvis du kender det,

274
00:12:28,770 --> 00:12:33,170
det er alle taler om lige
overfyldte størrelsen af ​​nogle tegn

275
00:12:33,170 --> 00:12:36,200
matrix eller nogle matrix mere generelt.

276
00:12:36,200 --> 00:12:38,822
Eventuelle spørgsmål, så om dette?

277
00:12:38,822 --> 00:12:39,780
Prøv ikke dette derhjemme.

278
00:12:39,780 --> 00:12:41,620

279
00:12:41,620 --> 00:12:42,300
>> Okay.

280
00:12:42,300 --> 00:12:47,270
Så malloc hidtil har været vores nye
ven i, at vi kan allokere hukommelse

281
00:12:47,270 --> 00:12:50,540
at vi ikke nødvendigvis kender i
forhånd ved, at vi ønsker, så vi ikke har

282
00:12:50,540 --> 00:12:52,920
til hårdt kode ind i vores
programnumre som 12.

283
00:12:52,920 --> 00:12:55,550
Når brugeren fortæller os, hvor meget
data, som han eller hun ønsker at indtaste,

284
00:12:55,550 --> 00:12:58,000
vi kan allokere så meget hukommelse.

285
00:12:58,000 --> 00:13:01,484
>> Så malloc det viser sig, at den
omfang, vi har brugt det,

286
00:13:01,484 --> 00:13:03,900
eksplicit sidste gang, og derefter
gutter har brugt det

287
00:13:03,900 --> 00:13:08,160
til getString ubevidst for
flere uger, alle allokere hukommelse

288
00:13:08,160 --> 00:13:09,820
kommer fra den såkaldte bunke.

289
00:13:09,820 --> 00:13:13,852
Og det er derfor getString for eksempel
kan allokere hukommelse dynamisk

290
00:13:13,852 --> 00:13:16,060
uden at vide hvad du er
kommer til at skrive i forvejen,

291
00:13:16,060 --> 00:13:21,520
hånd du tilbage en pegepind til denne hukommelse,
og at hukommelsen er stadig jeres at beholde,

292
00:13:21,520 --> 00:13:24,080
selv efter getString afkast.

293
00:13:24,080 --> 00:13:27,450
Fordi tilbagekaldelse efter alt at
stak konstant går op og ned,

294
00:13:27,450 --> 00:13:27,950
op og ned.

295
00:13:27,950 --> 00:13:30,230
Og så snart det går
ned, betyder enhver hukommelse

296
00:13:30,230 --> 00:13:33,030
denne funktion anvendes, bør
ikke bruges af andre.

297
00:13:33,030 --> 00:13:34,570
Det er skrald værdier nu.

298
00:13:34,570 --> 00:13:36,120
>> Men den bunke er heroppe.

299
00:13:36,120 --> 00:13:39,360
Og hvad er rart om malloc er, at
når malloc allokerer hukommelse op her,

300
00:13:39,360 --> 00:13:42,070
det er ikke påvirket, for
størstedelens vedkommende af stakken.

301
00:13:42,070 --> 00:13:46,000
Og så enhver funktion kan få adgang til
hukommelse, der er blevet malloc'd,

302
00:13:46,000 --> 00:13:49,120
selv af en funktion som getString,
selv efter at det er returneret.

303
00:13:49,120 --> 00:13:51,700
>> Nu det modsatte af malloc er gratis.

304
00:13:51,700 --> 00:13:53,900
Og ja, den regel, du
nødt til at begynde at vedtage

305
00:13:53,900 --> 00:13:58,950
er noget, enhver, når som helst du bruger malloc
du skal selv bruge gratis, til sidst,

306
00:13:58,950 --> 00:14:00,280
på samme pointer.

307
00:14:00,280 --> 00:14:03,289
Alt dette tidspunkt, vi har skrevet
buggy, buggy kode, af mange årsager.

308
00:14:03,289 --> 00:14:05,580
Men en af ​​der har været
anvendelse af CS50 bibliotek, som

309
00:14:05,580 --> 00:14:09,010
selv er bevidst
buggy, det lækker hukommelse.

310
00:14:09,010 --> 00:14:11,410
Hver gang du har kaldt getString
i løbet af de sidste par uger

311
00:14:11,410 --> 00:14:13,870
vi beder operativsystemet
systemet, Linux, for hukommelsen.

312
00:14:13,870 --> 00:14:15,780
Og du har aldrig en gang givet det tilbage.

313
00:14:15,780 --> 00:14:17,730
Og det er ikke i
praksis, en god ting.

314
00:14:17,730 --> 00:14:20,330
>> Og Valgrind, en af ​​de
redskaber, der er indført i Pset 4,

315
00:14:20,330 --> 00:14:22,900
handler om at hjælpe dig
nu finde fejl som.

316
00:14:22,900 --> 00:14:27,060
Men heldigvis for Pset 4 behøver du ikke
at bruge CS50 biblioteket eller getString.

317
00:14:27,060 --> 00:14:31,220
Så eventuelle fejl i forbindelse med hukommelse er
i sidste ende kommer til at være din egen.

318
00:14:31,220 --> 00:14:34,060
>> Så malloc er mere end blot
bekvemt til dette formål.

319
00:14:34,060 --> 00:14:37,420
Vi kan faktisk nu løse
fundamentalt forskellige problemer,

320
00:14:37,420 --> 00:14:41,640
og fundamentalt løse problemer mere
effektivt som ugen nul løfte.

321
00:14:41,640 --> 00:14:44,720
Indtil videre er dette den mest sexede
datastruktur, vi har haft.

322
00:14:44,720 --> 00:14:47,804
Og ved datastruktur jeg bare betyde
en måde at begrebsliggøre hukommelse

323
00:14:47,804 --> 00:14:50,720
på en måde, der går videre end bare at sige,
dette er en int, er dette et tegn.

324
00:14:50,720 --> 00:14:52,930
Vi kan begynde at klynge ting sammen.

325
00:14:52,930 --> 00:14:54,460
>> Så et array lignede dette.

326
00:14:54,460 --> 00:14:57,270
Og hvad var nøglen i omkring en
array er at det giver dig

327
00:14:57,270 --> 00:14:59,724
back-to-back bidder af
hukommelse, som hver

328
00:14:59,724 --> 00:15:02,765
vil være af samme type, int,
int, int, int, eller char, char, fjeldørred,

329
00:15:02,765 --> 00:15:03,330
char.

330
00:15:03,330 --> 00:15:04,496
Men der er nogle ulemper.

331
00:15:04,496 --> 00:15:06,570
Dette er for eksempel
et array af størrelse seks.

332
00:15:06,570 --> 00:15:10,650
Antag, at du udfylde dette array med seks
tal og derefter, uanset grunden,

333
00:15:10,650 --> 00:15:13,187
din bruger ønsker at give
du et syvende nummer.

334
00:15:13,187 --> 00:15:14,020
Hvor skal du sætte det?

335
00:15:14,020 --> 00:15:15,490

336
00:15:15,490 --> 00:15:18,990
>> Hvad er løsningen, hvis du har
skabt et array på stakken,

337
00:15:18,990 --> 00:15:22,030
for eksempel blot med uge
to notation som vi introducerede,

338
00:15:22,030 --> 00:15:23,730
af kantede parenteser med en række indeni?

339
00:15:23,730 --> 00:15:25,160

340
00:15:25,160 --> 00:15:27,260
Nå, du har fået seks
numre i disse bokse.

341
00:15:27,260 --> 00:15:28,530
Hvad ville dine instinkter være?

342
00:15:28,530 --> 00:15:29,973
Hvor ville du ønsker at sætte det?

343
00:15:29,973 --> 00:15:30,860
>> Publikum: [uhørligt]

344
00:15:30,860 --> 00:15:31,315
>> David J. MALAN: Undskyld?

345
00:15:31,315 --> 00:15:32,380
>> Publikum: Sæt det på enden.

346
00:15:32,380 --> 00:15:33,796
>> David J. MALAN: Sæt det på enden.

347
00:15:33,796 --> 00:15:35,880
Så bare over til højre,
uden for denne boks.

348
00:15:35,880 --> 00:15:38,710
Hvilket ville være rart, men det
viser sig at du ikke kan gøre det.

349
00:15:38,710 --> 00:15:41,350
Fordi hvis du ikke har bedt om
for dette stykke af hukommelse,

350
00:15:41,350 --> 00:15:44,490
det kunne være tilfældigt, at dette
bliver brugt af en anden variabel

351
00:15:44,490 --> 00:15:45,030
helt.

352
00:15:45,030 --> 00:15:49,210
Tænk tilbage en uge eller så når vi lagde
ud Zamyla og Davin og Gabe navne

353
00:15:49,210 --> 00:15:49,930
i hukommelsen.

354
00:15:49,930 --> 00:15:51,638
De var bogstaveligt
tilbage til tilbage til tilbage.

355
00:15:51,638 --> 00:15:53,550
Så vi kan ikke nødvendigvis
lid til, at hvad der nu er

356
00:15:53,550 --> 00:15:55,800
herovre er tilgængelig for mig at bruge.

357
00:15:55,800 --> 00:15:56,990
>> Så hvad ellers kan du gøre?

358
00:15:56,990 --> 00:16:00,282
Tja, når realisere dig
har brug for en bred vifte af størrelse syv,

359
00:16:00,282 --> 00:16:02,490
du bare kunne skabe en
vifte af størrelse syv derefter bruge

360
00:16:02,490 --> 00:16:05,950
en for-løkke eller en while-løkke,
kopiere det ind i det nye array,

361
00:16:05,950 --> 00:16:09,680
og så en eller anden måde bare slippe af med
dette array eller bare stoppe med at bruge det.

362
00:16:09,680 --> 00:16:12,130
Men det er ikke særlig effektiv.

363
00:16:12,130 --> 00:16:15,340
Kort sagt, arrays ikke lade
du dynamisk ændre størrelsen på.

364
00:16:15,340 --> 00:16:17,900
>> Så på den ene side får du
random access, som er forbløffende.

365
00:16:17,900 --> 00:16:20,108
Fordi det lader os gøre ting
ligesom kløft og erobring,

366
00:16:20,108 --> 00:16:23,100
binær søgning, som alle vi har
talte om på skærmen her.

367
00:16:23,100 --> 00:16:24,950
Men du male dig selv op i et hjørne.

368
00:16:24,950 --> 00:16:27,810
Så snart du rammer
slutningen af ​​din array,

369
00:16:27,810 --> 00:16:29,980
du nødt til at gøre en meget
dyr operation

370
00:16:29,980 --> 00:16:33,910
eller skrive en hel masse kode
nu beskæftige sig med dette problem.

371
00:16:33,910 --> 00:16:36,680
>> Så hvad nu hvis vi i stedet havde
noget, der hedder en liste,

372
00:16:36,680 --> 00:16:38,820
eller en linket liste i særdeleshed?

373
00:16:38,820 --> 00:16:41,930
Hvad hvis man i stedet for at have
rektangler ryg mod ryg mod ryg,

374
00:16:41,930 --> 00:16:45,730
vi har rektangler, der efterlader lidt
lidt vrikke værelse i mellem dem?

375
00:16:45,730 --> 00:16:49,670
Og selv om jeg har tegnet dette
billede eller tilpasset dette billede

376
00:16:49,670 --> 00:16:54,696
fra en af ​​teksterne her for at være tilbage til
tilbage til tilbage meget velordnet, i virkeligheden,

377
00:16:54,696 --> 00:16:56,820
en af ​​disse rektangler
kunne være heroppe i hukommelsen.

378
00:16:56,820 --> 00:16:58,028
En af dem kunne være her op.

379
00:16:58,028 --> 00:17:00,420
En af dem kunne være heroppe,
her, og så videre.

380
00:17:00,420 --> 00:17:02,910
>> Men hvad nu hvis vi trak,
i denne sag, pile

381
00:17:02,910 --> 00:17:05,650
at en eller anden måde forbinde disse
rektangler sammen?

382
00:17:05,650 --> 00:17:08,170
Faktisk har vi set en teknisk
inkarnation af en pil.

383
00:17:08,170 --> 00:17:09,839

384
00:17:09,839 --> 00:17:13,710
Hvad har vi brugt i de seneste
dage, at under hætten,

385
00:17:13,710 --> 00:17:15,210
er repræsentativ for en pil?

386
00:17:15,210 --> 00:17:16,290

387
00:17:16,290 --> 00:17:17,349
En markør, højre?

388
00:17:17,349 --> 00:17:19,780
>> Så hvad nu hvis, i stedet for
blot lagring af numre

389
00:17:19,780 --> 00:17:23,130
ligesom 9, 17, 22, 26, 34,
hvad nu hvis vi ikke gemt

390
00:17:23,130 --> 00:17:27,079
kun et nummer, men en pegepind
siden af ​​hvert sådant nummer?

391
00:17:27,079 --> 00:17:30,690
Så meget som du ville tråd en
nål gennem en hel bunke af stof,

392
00:17:30,690 --> 00:17:32,950
en eller anden måde kombinationsklausuler ting
sammen, ligeledes kan

393
00:17:32,950 --> 00:17:35,550
vi med pegepinde, som
inkarneret med pile her,

394
00:17:35,550 --> 00:17:38,550
slags flette sammen
disse individuelle rektangler

395
00:17:38,550 --> 00:17:41,780
ved effektivt ved hjælp af en pegepind
ved siden af ​​hvert nummer,

396
00:17:41,780 --> 00:17:46,065
peger på nogle næste nummer, der
peger på, til gengæld nogle næste nummer?

397
00:17:46,065 --> 00:17:47,940
Så med andre ord, hvad
hvis vi faktisk ønskede

398
00:17:47,940 --> 00:17:49,820
at gennemføre noget som dette?

399
00:17:49,820 --> 00:17:53,610
Nå desværre disse rektangler,
mindst én med 9, 17, 22,

400
00:17:53,610 --> 00:17:57,040
og så videre, er disse ikke længere
pæne firkanter med enkelte numre.

401
00:17:57,040 --> 00:17:59,960
Den nederste, rektangel
under 9, for eksempel,

402
00:17:59,960 --> 00:18:04,330
repræsenterer, hvad skal
være en pegepind, 32 bits.

403
00:18:04,330 --> 00:18:09,460
Nu er jeg endnu ikke bekendt med nogen datatype
i C, der ikke blot giver dig en int

404
00:18:09,460 --> 00:18:11,630
men en pegepind helt.

405
00:18:11,630 --> 00:18:15,020
>> Så hvad er løsningen, hvis vi vil
at opfinde vores egne svar på dette?

406
00:18:15,020 --> 00:18:15,760
Ja?

407
00:18:15,760 --> 00:18:16,640
>> Publikum: [uhørligt]

408
00:18:16,640 --> 00:18:17,360
>> David J. MALAN: Hvad er det?

409
00:18:17,360 --> 00:18:17,880
>> Publikum: Ny struktur.

410
00:18:17,880 --> 00:18:19,590
>> David J. MALAN: Ja, så hvorfor
vi ikke skabe en ny struktur,

411
00:18:19,590 --> 00:18:20,920
eller i C, en struct?

412
00:18:20,920 --> 00:18:25,990
Vi har set structs før, hvis kortvarigt,
hvor vi behandlet med en studerende struktur

413
00:18:25,990 --> 00:18:27,780
som dette, der havde et navn og et hus.

414
00:18:27,780 --> 00:18:31,980
I Pset 3 breakout du har brugt en hel
flok structs-- GRect og GOvals

415
00:18:31,980 --> 00:18:34,810
at Stanford skabt til at
klynge oplysninger sammen.

416
00:18:34,810 --> 00:18:38,580
Så hvad nu hvis vi tager den samme idé om
søgeordene "typedef" og "struct",

417
00:18:38,580 --> 00:18:42,890
og derefter nogle elev-specifikke ting,
og udvikle dette i følgende:

418
00:18:42,890 --> 00:18:46,210
typedef struct node-- og knudepunkt er
bare en meget generisk datalogi

419
00:18:46,210 --> 00:18:49,980
betegnelse for noget i en datastruktur,
en beholder i en datastruktur.

420
00:18:49,980 --> 00:18:53,900
En node Jeg hævder vil have
en int n helt ligetil,

421
00:18:53,900 --> 00:18:58,810
og så lidt mere kryptisk,
denne anden linje, struct node * næste.

422
00:18:58,810 --> 00:19:01,300
Men færre tekniske termer,
hvad er det anden linje

423
00:19:01,300 --> 00:19:02,980
kode inde i krøllede parenteser?

424
00:19:02,980 --> 00:19:03,737
Ja?

425
00:19:03,737 --> 00:19:04,851
>> Publikum: [uhørligt]

426
00:19:04,851 --> 00:19:06,600
David J. MALAN: A
pointer til en anden node.

427
00:19:06,600 --> 00:19:09,910
Så ganske vist syntaks lidt kryptisk.

428
00:19:09,910 --> 00:19:13,250
Men hvis du læser det bogstaveligt,
næste er navnet på en variabel.

429
00:19:13,250 --> 00:19:14,410
Hvad er dens datatype?

430
00:19:14,410 --> 00:19:18,206
Det er en lidt vidtløftig denne gang,
men det er af typen struct node *.

431
00:19:18,206 --> 00:19:22,960
Enhver tid vi har set noget stjerne, at
betyder, at det er en pointer til denne datatype.

432
00:19:22,960 --> 00:19:26,810
Så næste er tilsyneladende en
pointer til en struct node.

433
00:19:26,810 --> 00:19:28,310
>> Nu, hvad er en struct node?

434
00:19:28,310 --> 00:19:31,044
Nå, mærke, at du ser dem
samme ord øverst til højre.

435
00:19:31,044 --> 00:19:33,960
Og ja, se dig også ordet
"Knude" hernede nederst til venstre.

436
00:19:33,960 --> 00:19:35,640
Og det er faktisk bare en bekvemmelighed.

437
00:19:35,640 --> 00:19:39,930
Bemærk, at i vores studerende definition
der er ordet "studerende" kun én gang.

438
00:19:39,930 --> 00:19:42,510
Og det er fordi en elev
Formålet var ikke selvrefererende.

439
00:19:42,510 --> 00:19:45,340
Der er ikke noget inde i en elev
der skal pege på en anden elev,

440
00:19:45,340 --> 00:19:45,610
persay.

441
00:19:45,610 --> 00:19:47,630
Det ville være slags
underlige i den virkelige verden.

442
00:19:47,630 --> 00:19:50,880
>> Men med en knude i en forbundet
liste, vi ønsker en knude

443
00:19:50,880 --> 00:19:53,970
være referentiel en lignende genstand.

444
00:19:53,970 --> 00:19:57,900
Og så mærke til ændringen her er ikke
bare hvad der er indeni de krøllede parenteser.

445
00:19:57,900 --> 00:20:00,800
Men vi tilføje ordet "knude"
foroven samt

446
00:20:00,800 --> 00:20:02,930
tilføje det til bunden
i stedet for "studerende".

447
00:20:02,930 --> 00:20:06,000
Og dette er kun en teknisk detalje
så, igen, din datastruktur

448
00:20:06,000 --> 00:20:11,380
kan være selvrefererende, således at en
knude kan pege på en anden sådan node.

449
00:20:11,380 --> 00:20:13,840
>> Så hvad er dette i sidste ende
kommer til at betyde for os?

450
00:20:13,840 --> 00:20:17,560
Tja, en, denne ting inde
er indholdet af vores knudepunkt.

451
00:20:17,560 --> 00:20:19,360
Denne ting op her,
øverst til højre, er bare så

452
00:20:19,360 --> 00:20:20,860
det igen, kan vi henvise til os.

453
00:20:20,860 --> 00:20:23,401
Og så den yderste ting,
selvom noden, er et nyt begreb,

454
00:20:23,401 --> 00:20:25,500
måske, det er stadig den
samme som studerende, og hvad

455
00:20:25,500 --> 00:20:27,520
var under emhætten i SPL.

456
00:20:27,520 --> 00:20:31,095
>> Så hvis vi nu ønskede at starte
gennemførelsen af ​​denne linkede liste,

457
00:20:31,095 --> 00:20:33,220
hvordan kan vi omsætte
noget som dette til at kode?

458
00:20:33,220 --> 00:20:35,350
Nå, lad os bare se en
eksempel på et program, der

459
00:20:35,350 --> 00:20:36,840
rent faktisk bruger en linket liste.

460
00:20:36,840 --> 00:20:40,870
Blandt dagens uddeling kode
er et program kaldet List Zero.

461
00:20:40,870 --> 00:20:44,980
Og hvis jeg køre dette skabte jeg en super
simpel GUI, Grafisk brugergrænseflade,

462
00:20:44,980 --> 00:20:46,460
men det er egentlig bare printf.

463
00:20:46,460 --> 00:20:50,930
Og nu har jeg givet mig selv et par menu
options-- Slet, Indsæt, Søg,

464
00:20:50,930 --> 00:20:51,750
og Traverse.

465
00:20:51,750 --> 00:20:52,630
Og Afslut.

466
00:20:52,630 --> 00:20:55,970
Disse er blot almindelige operationer på en
datastruktur kendt som et link liste.

467
00:20:55,970 --> 00:20:58,409
>> Nu Slet vil
slette et nummer fra listen.

468
00:20:58,409 --> 00:21:00,200
Indsæt kommer til at tilføje
et nummer til listen.

469
00:21:00,200 --> 00:21:02,181
Søg kommer til at se
efter nummer på listen.

470
00:21:02,181 --> 00:21:04,930
Og travers er bare en fancy måde
sige, gå gennem listen,

471
00:21:04,930 --> 00:21:06,245
printe den ud, men det er det.

472
00:21:06,245 --> 00:21:07,720
Du må ikke ændre det på nogen måde.

473
00:21:07,720 --> 00:21:08,570
>> Så lad os prøve dette.

474
00:21:08,570 --> 00:21:10,160
Lad os gå videre og type 2.

475
00:21:10,160 --> 00:21:12,710
Og så jeg har tænkt mig at
indsætte antal, siger 9.

476
00:21:12,710 --> 00:21:13,620
Enter.

477
00:21:13,620 --> 00:21:17,480
Og nu er mit program er bare
programmeret til at sige, listen er nu 9.

478
00:21:17,480 --> 00:21:20,190
Nu, hvis jeg gå videre og
gør Indsæt igen, lad

479
00:21:20,190 --> 00:21:23,680
mig gå videre og zoome ud og skriv 17.

480
00:21:23,680 --> 00:21:25,770
Min liste er nu 9, derefter 17.

481
00:21:25,770 --> 00:21:27,750
Hvis jeg gør indsætte igen, lad os springe en.

482
00:21:27,750 --> 00:21:32,400
I stedet for 22, som pr det billede, vi har
været at se på her, lad mig springe frem

483
00:21:32,400 --> 00:21:34,630
og indsæt 26 næste.

484
00:21:34,630 --> 00:21:36,230
Så jeg har tænkt mig at skrive 26.

485
00:21:36,230 --> 00:21:37,755
Listen er som jeg forventer.

486
00:21:37,755 --> 00:21:40,630
Men nu, bare for at se, om denne kode
kommer til at være fleksibel, så lad mig nu

487
00:21:40,630 --> 00:21:43,520
typen 22, som i det mindste
begrebsmæssigt, hvis vi er

488
00:21:43,520 --> 00:21:46,520
Holde dette sorteret, som faktisk
kommer til at være endnu et mål lige nu,

489
00:21:46,520 --> 00:21:48,690
skal gå i mellem 17 og 26.

490
00:21:48,690 --> 00:21:50,270
Så jeg trykker på Enter.

491
00:21:50,270 --> 00:21:51,380
Ja, det virker.

492
00:21:51,380 --> 00:21:54,950
Og så lad mig indsætte
sidste pr billedet 34.

493
00:21:54,950 --> 00:21:55,450
>> Okay.

494
00:21:55,450 --> 00:21:58,980
Så for nu lad mig fastsætte, at
Slet og Traverse og Search gør,

495
00:21:58,980 --> 00:21:59,760
faktisk fungerer.

496
00:21:59,760 --> 00:22:04,180
I virkeligheden, hvis jeg løber Søg, lad os
søg efter nummer 22, Enter.

497
00:22:04,180 --> 00:22:05,010
Det fandt 22.

498
00:22:05,010 --> 00:22:07,580
Så det er, hvad denne
Program List Zero gør.

499
00:22:07,580 --> 00:22:10,230
>> Men hvad der rent faktisk sker
om der implementerer dette?

500
00:22:10,230 --> 00:22:14,530
Nå, først jeg måtte have, og faktisk
Jeg har en fil kaldet list0.h.

501
00:22:14,530 --> 00:22:16,540

502
00:22:16,540 --> 00:22:20,690
Og et eller andet sted i der er denne
linje, typedef, struct node

503
00:22:20,690 --> 00:22:24,850
så har jeg mine krøllede parenteser, int n, og
så struct-- hvad var definitionen?

504
00:22:24,850 --> 00:22:26,530

505
00:22:26,530 --> 00:22:28,545
Struct node næste.

506
00:22:28,545 --> 00:22:29,920

507
00:22:29,920 --> 00:22:31,045
Så vi har brug for stjernen.

508
00:22:31,045 --> 00:22:33,420
Nu teknisk vi kommer ind
for vane at trække det her.

509
00:22:33,420 --> 00:22:35,670
Du vil måske se lærebøger og
online referencer gør det der.

510
00:22:35,670 --> 00:22:36,660
Det er funktionelt ækvivalente.

511
00:22:36,660 --> 00:22:37,980
I virkeligheden er det lidt mere typisk.

512
00:22:37,980 --> 00:22:40,563
Men jeg vil være i overensstemmelse med, hvad
vi gjorde sidste gang og gøre dette.

513
00:22:40,563 --> 00:22:42,350
Og så til sidst, jeg har tænkt mig at gøre dette.

514
00:22:42,350 --> 00:22:45,550
>> Så i en header fil
et eller andet sted i list0.h

515
00:22:45,550 --> 00:22:49,200
dag er denne struct definition
og måske nogle andre ting.

516
00:22:49,200 --> 00:22:52,580
I mellemtiden i list0c der
kommer til at være et par ting.

517
00:22:52,580 --> 00:22:54,740
Men vi vil bare
start og ikke afslutte dette.

518
00:22:54,740 --> 00:22:59,690
List0.h er en fil jeg vil
at medtage i min C-fil.

519
00:22:59,690 --> 00:23:03,910
Og så på et tidspunkt er jeg
kommer til at have int, main, ugyldig.

520
00:23:03,910 --> 00:23:06,530
Og så jeg har tænkt mig at
har nogle gøremål er her.

521
00:23:06,530 --> 00:23:10,620
Jeg vil også have en
prototype, ligesom tomrum, søg, int,

522
00:23:10,620 --> 00:23:13,610
n, hvis formål i livet er
at søge efter et element.

523
00:23:13,610 --> 00:23:18,310
Og så hernede Jeg hævder i
dagens kode, ugyldig, søg, int, n,

524
00:23:18,310 --> 00:23:21,020
ingen semikolon men åbne krøllede parenteser.

525
00:23:21,020 --> 00:23:25,049
Og nu vil jeg en eller anden måde søge
til et element på denne liste.

526
00:23:25,049 --> 00:23:27,340
Men vi har ikke nok
på skærmen endnu.

527
00:23:27,340 --> 00:23:29,800
Jeg har faktisk ikke
repræsenteret selve listen.

528
00:23:29,800 --> 00:23:33,070
Så en måde, vi kunne gennemføre
en sammenkædet liste i et program

529
00:23:33,070 --> 00:23:37,520
er jeg slags ønsker at gøre noget
ligesom erklærer linket liste op her.

530
00:23:37,520 --> 00:23:40,520
For overskuelighedens skyld vil jeg gøre
denne globale, selvom vi generelt

531
00:23:40,520 --> 00:23:41,645
bør ikke gøre det for meget.

532
00:23:41,645 --> 00:23:43,260
Men det vil forenkle dette eksempel.

533
00:23:43,260 --> 00:23:45,890
Så jeg vil gerne erklære
en linket liste op her.

534
00:23:45,890 --> 00:23:47,010
Nu, hvordan kan jeg gøre det?

535
00:23:47,010 --> 00:23:48,810

536
00:23:48,810 --> 00:23:50,750
>> Her er billedet af en linket liste.

537
00:23:50,750 --> 00:23:53,030
Og det gør jeg ikke rigtig
ved i det øjeblik, hvor

538
00:23:53,030 --> 00:23:56,710
Jeg har tænkt mig at gå om repræsentere
så mange ting med blot én

539
00:23:56,710 --> 00:23:58,040
variabel i hukommelsen.

540
00:23:58,040 --> 00:23:59,160
Men tænk tilbage et øjeblik.

541
00:23:59,160 --> 00:24:00,830
Alt dette tidspunkt, vi har haft
strenge, som vi derefter

542
00:24:00,830 --> 00:24:02,913
viser sig at være arrays af
tegn, som vi derefter

543
00:24:02,913 --> 00:24:05,740
åbenbaret til bare at være en pegepind
til det første tegn

544
00:24:05,740 --> 00:24:08,890
i et array af tegn
der er nul afsluttes.

545
00:24:08,890 --> 00:24:13,530
Så ved denne logik, og med denne
billede slags såning dine tanker,

546
00:24:13,530 --> 00:24:17,964
hvad behøver vi faktisk skrive i vores
kode til at repræsentere en linket liste?

547
00:24:17,964 --> 00:24:21,130
Hvor meget af denne information har vi brug
at fange i C-kode, ville du sige?

548
00:24:21,130 --> 00:24:22,654

549
00:24:22,654 --> 00:24:23,154
Ja?

550
00:24:23,154 --> 00:24:24,738
>> PUBLIKUM: Vi har brug for en pointer til en node.

551
00:24:24,738 --> 00:24:26,237
David J. MALAN: En markør til et knudepunkt.

552
00:24:26,237 --> 00:24:29,320
Især som knudepunkt ville din
instinkter være at holde en pointer til?

553
00:24:29,320 --> 00:24:30,026
>> PUBLIKUM: Den første node.

554
00:24:30,026 --> 00:24:31,942
>> David J. MALAN: Ja,
sandsynligvis bare den første.

555
00:24:31,942 --> 00:24:34,030
Og bemærk, det første
knudepunkt er en anden form.

556
00:24:34,030 --> 00:24:37,690
Det er kun halvdelen af ​​struct,
fordi det er faktisk kun en pegepind.

557
00:24:37,690 --> 00:24:44,650
Så hvad du rent faktisk kan gøre, er erklære
en sammenkædet liste at være af typen node *.

558
00:24:44,650 --> 00:24:47,780
Og lad os bare kalde det først
og initialisere den til null.

559
00:24:47,780 --> 00:24:49,910
Så nul igen, er på vej
ind i billedet her.

560
00:24:49,910 --> 00:24:53,620
Ikke alene er nul bruges som som en særlig
returværdi for ting som getString

561
00:24:53,620 --> 00:24:57,770
og malloc, null er også nul
pointer, manglen på en pointer,

562
00:24:57,770 --> 00:24:58,430
hvis du vil.

563
00:24:58,430 --> 00:25:00,309
Det betyder bare, intet er endnu her.

564
00:25:00,309 --> 00:25:02,100
Nu først, jeg kunne have
kaldte dette noget.

565
00:25:02,100 --> 00:25:04,200
Jeg kunne have kaldt det "liste"
eller en række andre ting.

566
00:25:04,200 --> 00:25:06,960
Men jeg kalder det "første", således at
det flugter med dette billede.

567
00:25:06,960 --> 00:25:10,280
Så ligesom en streng kan være repræsenteret
med adressen på sin første byte,

568
00:25:10,280 --> 00:25:11,280
så kan en linket liste.

569
00:25:11,280 --> 00:25:13,480
Og vi vil se andre data
strukturer repræsenteres

570
00:25:13,480 --> 00:25:16,700
med blot en pegepind,
en 32-bit pil, der peger

571
00:25:16,700 --> 00:25:18,740
i det første knudepunkt i strukturen.

572
00:25:18,740 --> 00:25:20,340
>> Men lad os nu forventer et problem.

573
00:25:20,340 --> 00:25:23,230
Hvis jeg kun huske
i mit program adressen

574
00:25:23,230 --> 00:25:27,220
af det første knudepunkt, det første
rektangel i denne datastruktur,

575
00:25:27,220 --> 00:25:31,760
hvad havde bedre være tilfældet om
gennemførelse af resten af ​​min liste?

576
00:25:31,760 --> 00:25:35,820
Hvad er en afgørende detalje, der kommer
at sikre, at dette rent faktisk virker?

577
00:25:35,820 --> 00:25:39,250
Og med "rent faktisk virker:" Jeg
betyde, meget gerne en streng,

578
00:25:39,250 --> 00:25:42,180
lader os gå fra det første tegn
i Davin navn til den anden,

579
00:25:42,180 --> 00:25:44,755
til den tredje til
fjerde, til den bitre ende,

580
00:25:44,755 --> 00:25:47,880
hvordan kan vi vide, når vi er i slutningen
af en sammenkædet liste, der ligner dette?

581
00:25:47,880 --> 00:25:50,035

582
00:25:50,035 --> 00:25:50,660
Når det er nul.

583
00:25:50,660 --> 00:25:53,640
Og jeg har repræsenteret denne slags som
ligesom en elektrisk ingeniør kraft,

584
00:25:53,640 --> 00:25:56,420
med den lille jordforbindelse
symbol slags.

585
00:25:56,420 --> 00:25:58,246
Men det betyder bare nul i dette tilfælde.

586
00:25:58,246 --> 00:26:00,370
Du kan tegne det et vilkårligt antal
måder, men denne forfatter

587
00:26:00,370 --> 00:26:02,800
skete for at bruge dette symbol her.

588
00:26:02,800 --> 00:26:06,260
>> Så længe vi snor
alle disse knudepunkter sammen,

589
00:26:06,260 --> 00:26:08,600
kun huske hvor
den første er, så længe

590
00:26:08,600 --> 00:26:11,760
som vi sætter et særligt symbol på
den allersidste knude i listen,

591
00:26:11,760 --> 00:26:15,130
og vi vil bruge null, fordi det er
hvad vi har til rådighed for os,

592
00:26:15,130 --> 00:26:16,480
denne liste er færdig.

593
00:26:16,480 --> 00:26:20,190
Og selv om jeg kun give dig en pegepind til
det første element, du som programmør,

594
00:26:20,190 --> 00:26:22,486
kan sikkert adgang til resten af ​​det.

595
00:26:22,486 --> 00:26:24,360
Men lad os lade jeres sind
vandre en lille smule,

596
00:26:24,360 --> 00:26:26,140
hvis de allerede er ikke
helt wandered-- hvad er

597
00:26:26,140 --> 00:26:28,723
vil være køretiden for
finde noget på denne liste?

598
00:26:28,723 --> 00:26:30,450

599
00:26:30,450 --> 00:26:33,470
Damn det, det er store O af n,
hvilket ikke er dårligt, i retfærdighed.

600
00:26:33,470 --> 00:26:34,800
Men det er lineær.

601
00:26:34,800 --> 00:26:37,980
Vi har givet op, hvad funktionen
arrays ved at flytte flere

602
00:26:37,980 --> 00:26:43,130
mod dette billede af dynamisk
vævet sammen eller er knyttet knuder?

603
00:26:43,130 --> 00:26:44,970

604
00:26:44,970 --> 00:26:46,687
Vi har givet op random access.

605
00:26:46,687 --> 00:26:48,770
Et array er rart, fordi
matematisk alt

606
00:26:48,770 --> 00:26:50,340
er tilbage til tilbage til tilbage til tilbage.

607
00:26:50,340 --> 00:26:52,370
Selvom dette billede
ser temmelig, og selv

608
00:26:52,370 --> 00:26:55,830
selvom det ser ud som disse knudepunkter
er pænt fordelt fra hinanden, i virkeligheden

609
00:26:55,830 --> 00:26:56,830
de kunne være hvor som helst.

610
00:26:56,830 --> 00:27:01,590
OX1, Ox50, Ox123, Ox99 disse
knudepunkter kunne være overalt.

611
00:27:01,590 --> 00:27:05,960
Fordi malloc ikke tildele hukommelse
fra den bunke, men overalt i bunke.

612
00:27:05,960 --> 00:27:09,080
Du behøver ikke nødvendigvis vide, at det er
vil være tilbage til tilbage til tilbage.

613
00:27:09,080 --> 00:27:12,460
Og så dette billede i virkelighedens
ikke kommer til at være helt denne smukke.

614
00:27:12,460 --> 00:27:16,140
>> Så det kommer til at tage lidt af
arbejde for at gennemføre denne funktion.

615
00:27:16,140 --> 00:27:17,880
Så lad os gennemføre søgning nu.

616
00:27:17,880 --> 00:27:20,250
Og vi vil se sådan en
smart måde at gøre dette.

617
00:27:20,250 --> 00:27:24,660
Så hvis jeg er en søgefunktion og
Jeg får en variabel tal n

618
00:27:24,660 --> 00:27:28,490
at kigge efter, jeg har brug for at kende
ny syntaks for at kigge indenfor

619
00:27:28,490 --> 00:27:32,400
af en struktur, der er
pegede på, for at finde n.

620
00:27:32,400 --> 00:27:33,210
Så lad os gøre dette.

621
00:27:33,210 --> 00:27:36,030
>> Så først vil jeg tænkt mig at gå
videre og erklære en node *.

622
00:27:36,030 --> 00:27:39,400
Og jeg har tænkt mig at kalde det
pointer, blot ved konvention.

623
00:27:39,400 --> 00:27:41,710
Og jeg har tænkt mig at initialisere den til først.

624
00:27:41,710 --> 00:27:43,770
Og nu kan jeg gøre dette
på en række måder.

625
00:27:43,770 --> 00:27:45,436
Men jeg har tænkt mig at tage en fælles tilgang.

626
00:27:45,436 --> 00:27:50,180
Mens markøren er ikke lig med
null, og det er gyldig syntaks.

627
00:27:50,180 --> 00:27:54,550
Og det betyder blot gøre følgende, så
længe du ikke peger på ingenting.

628
00:27:54,550 --> 00:27:55,800
Hvad ønsker jeg at gøre?

629
00:27:55,800 --> 00:28:01,939
>> Hvis pointer prik n, lad mig komme tilbage
til at equals-- lig hvad?

630
00:28:01,939 --> 00:28:03,105
Hvilken værdi jeg leder efter?

631
00:28:03,105 --> 00:28:04,920

632
00:28:04,920 --> 00:28:06,590
Selve n, der blev vedtaget i.

633
00:28:06,590 --> 00:28:09,020
Så her er en anden funktion
C og mange sprog.

634
00:28:09,020 --> 00:28:13,705
Selvom struktur kaldet node
har en værdi n helt legitimt

635
00:28:13,705 --> 00:28:17,530
også have en lokal argument
eller variabel kaldet n.

636
00:28:17,530 --> 00:28:20,085
Fordi vi selv med
menneskers øjne kan skelne

637
00:28:20,085 --> 00:28:22,087
at n er formentlig
forskellig fra denne n.

638
00:28:22,087 --> 00:28:23,420
Fordi syntaksen er anderledes.

639
00:28:23,420 --> 00:28:26,211
Du har fået en prik og en pegepind,
denne ene har noget sådant.

640
00:28:26,211 --> 00:28:27,290
Så det er OK.

641
00:28:27,290 --> 00:28:29,120
Det er OK at kalde dem de samme ting.

642
00:28:29,120 --> 00:28:32,380
>> Hvis jeg finder du dette, er jeg
lyst til at gøre noget

643
00:28:32,380 --> 00:28:35,000
ligesom meddele, at vi har fundet n.

644
00:28:35,000 --> 00:28:37,930
Og vi vil overlade som en
kommentere eller pseudokode kode.

645
00:28:37,930 --> 00:28:40,190
Else, og her er den
interessant del, hvad

646
00:28:40,190 --> 00:28:47,320
ønsker jeg at gøre, hvis den aktuelle node
ikke indeholdende N, som jeg bryder mig om?

647
00:28:47,320 --> 00:28:50,700
Hvordan kan jeg opnå følgende?

648
00:28:50,700 --> 00:28:53,710
Hvis min finger på
øjeblik er PTR, og det er

649
00:28:53,710 --> 00:28:55,920
peger på uanset
først peger på,

650
00:28:55,920 --> 00:28:59,290
Hvordan flytter jeg min finger
til den næste node i koden?

651
00:28:59,290 --> 00:29:01,915
Nå, hvad er brødkrumme, vi er
kommer til at følge i denne sag?

652
00:29:01,915 --> 00:29:03,464

653
00:29:03,464 --> 00:29:04,380
Publikum: [uhørligt].

654
00:29:04,380 --> 00:29:05,630
David J. MALAN: Ja, så næste.

655
00:29:05,630 --> 00:29:06,640

656
00:29:06,640 --> 00:29:09,824
Så hvis jeg gå tilbage til mit
kode her, ja, jeg er

657
00:29:09,824 --> 00:29:12,990
kommer til at gå videre og sige pointer, som
er blot en midlertidig variable-- det er

658
00:29:12,990 --> 00:29:15,320
en underlig navn, PTR, men
det er ligesom temp--

659
00:29:15,320 --> 00:29:19,234
Jeg har tænkt mig at sætte markøren
svarende til, hvad markøren er--

660
00:29:19,234 --> 00:29:22,150
og igen, dette vil være en
lille buggy for en moment-- prik næste.

661
00:29:22,150 --> 00:29:23,551

662
00:29:23,551 --> 00:29:26,550
Med andre ord, vil jeg tage min
finger, som peger på denne knude

663
00:29:26,550 --> 00:29:31,247
her, og jeg har tænkt mig at sige, du ved
hvad, tage et kig på det næste felt

664
00:29:31,247 --> 00:29:33,330
og flytte din finger til
hvad det peger på.

665
00:29:33,330 --> 00:29:35,163
Og det kommer til at
gentag, gentag, gentag.

666
00:29:35,163 --> 00:29:37,630
Men når gør min finger
stoppe med at gøre noget som helst?

667
00:29:37,630 --> 00:29:40,095
Så snart hvad linje kode spark i?

668
00:29:40,095 --> 00:29:40,970
Publikum: [uhørligt]

669
00:29:40,970 --> 00:29:43,060
David J. MALAN: Hvis punkt, mens
pointer er ikke lig med nul.

670
00:29:43,060 --> 00:29:44,900
På et tidspunkt min finger
vil være at pege på nul

671
00:29:44,900 --> 00:29:47,070
og jeg har tænkt mig at indse
det er slutningen af ​​denne liste.

672
00:29:47,070 --> 00:29:48,910
Nu, dette er en smule
hvid løgn om enkelhed.

673
00:29:48,910 --> 00:29:51,580
Det viser sig, at selv om vi
lige lært denne dot notation

674
00:29:51,580 --> 00:29:55,220
af strukturer, pointer er ikke en struct.

675
00:29:55,220 --> 00:29:56,580
PTR er hvad?

676
00:29:56,580 --> 00:29:58,350
Bare for at være mere nitpicky.

677
00:29:58,350 --> 00:29:59,720

678
00:29:59,720 --> 00:30:01,360
Det er en pointer til en node.

679
00:30:01,360 --> 00:30:03,120
Det er ikke en knude selv.

680
00:30:03,120 --> 00:30:06,650
Hvis jeg havde ingen stjerne her, pegepind
absolutely-- det er et knudepunkt.

681
00:30:06,650 --> 00:30:08,650
Dette er ligesom uge én
erklæring af en variabel,

682
00:30:08,650 --> 00:30:10,120
Selv om ordet "node" er nyt.

683
00:30:10,120 --> 00:30:13,860
>> Men så snart vi indføre en
stjerne, er det nu en pointer til en node.

684
00:30:13,860 --> 00:30:17,960
Og desværre kan du ikke bruge
dot notation for en pointer.

685
00:30:17,960 --> 00:30:21,070
Du er nødt til at bruge pilen
notation, som mere slående,

686
00:30:21,070 --> 00:30:23,470
er første gang et stykke
af syntaks ser intuitiv.

687
00:30:23,470 --> 00:30:25,245
Det ser bogstaveligt talt som en pil.

688
00:30:25,245 --> 00:30:26,370
Og så det er en god ting.

689
00:30:26,370 --> 00:30:28,995
Og hernede bogstaveligt
ligner en pil.

690
00:30:28,995 --> 00:30:31,870
Så jeg tror, ​​det er den la-- jeg ikke
tror, ​​jeg over-begå her-- jeg

691
00:30:31,870 --> 00:30:34,120
tror, ​​det er det sidste nye stykke
af syntaks, vi kommer til at se.

692
00:30:34,120 --> 00:30:36,500
Og heldigvis, det er faktisk
lidt mere intuitiv.

693
00:30:36,500 --> 00:30:40,090
>> Nu, for dem af jer der
måske foretrækker den gamle måde,

694
00:30:40,090 --> 00:30:42,550
du kan stadig bruge dot notation.

695
00:30:42,550 --> 00:30:45,380
Men som pr mandagens
samtale, vi først

696
00:30:45,380 --> 00:30:50,530
nødt til at gå der, gå til at
adresse og derefter få adgang til området.

697
00:30:50,530 --> 00:30:51,897
Så dette er også korrekt.

698
00:30:51,897 --> 00:30:53,730
Og helt ærligt, det er en
lidt mere pedantisk.

699
00:30:53,730 --> 00:30:56,530
Du er bogstaveligt talt sige, dereference
markøren og derned.

700
00:30:56,530 --> 00:30:59,320
Så fat .n, feltet kaldet n.

701
00:30:59,320 --> 00:31:01,370
Men helt ærligt, ingen ønsker
at skrive eller læse dette.

702
00:31:01,370 --> 00:31:03,620
Og så verden opfundet
pilen notation, som

703
00:31:03,620 --> 00:31:06,980
er tilsvarende, identiske,
det er bare syntaktisk sukker.

704
00:31:06,980 --> 00:31:10,570
Så en fancy måde at sige dette
ser bedre ud, eller ser enklere.

705
00:31:10,570 --> 00:31:12,296
>> Så nu har jeg tænkt mig at gøre en anden ting.

706
00:31:12,296 --> 00:31:15,420
Jeg har tænkt mig at sige "pause" når jeg har
fundet det så jeg ikke holde udkig efter det.

707
00:31:15,420 --> 00:31:17,620
Men dette er kernen
af en søgefunktion.

708
00:31:17,620 --> 00:31:21,710
Men det er meget nemmere, i
ende, ikke at gå gennem koden.

709
00:31:21,710 --> 00:31:25,570
Dette er faktisk den formelle gennemførelse
af søgning i dagens uddeling kode.

710
00:31:25,570 --> 00:31:30,530
Jeg tør sige, at indsatsen ikke er
særligt sjovt at gå igennem

711
00:31:30,530 --> 00:31:33,180
visuelt, er heller ikke slette, selv
men ved slutningen af ​​dagen

712
00:31:33,180 --> 00:31:35,460
de koges ned til nogenlunde
simple heuristik.

713
00:31:35,460 --> 00:31:36,330
>> Så lad os gøre dette.

714
00:31:36,330 --> 00:31:39,250
Hvis du vil humor mig her, jeg gjorde
bringe en masse stress bolde.

715
00:31:39,250 --> 00:31:40,620
Jeg bragte en masse tal.

716
00:31:40,620 --> 00:31:46,562
Og kunne vi få et par frivillige
at repræsentere 9, 17, 20, 22, 29, og 34?

717
00:31:46,562 --> 00:31:48,270
Så det væsentlige alle
hvem der er her i dag.

718
00:31:48,270 --> 00:31:50,170

719
00:31:50,170 --> 00:31:52,760
Det var en, to, tre,
fire, fem, seks personer.

720
00:31:52,760 --> 00:31:55,740
Og jeg er blevet bedt om at go-- se, nej
en i ryggen hæver deres hænder.

721
00:31:55,740 --> 00:32:01,910
OK, en, to, tre, fire,
five-- lad mig indlæse balance-- seks.

722
00:32:01,910 --> 00:32:03,051
OK, du seks kom op.

723
00:32:03,051 --> 00:32:04,050
Vi har brug for andre mennesker.

724
00:32:04,050 --> 00:32:05,460
Vi bragte ekstra stress bolde.

725
00:32:05,460 --> 00:32:08,200
Og hvis du kunne, for
bare et øjeblik, linje

726
00:32:08,200 --> 00:32:10,490
jer op lige
ligesom dette billede her.

727
00:32:10,490 --> 00:32:15,200

728
00:32:15,200 --> 00:32:15,959
>> Okay.

729
00:32:15,959 --> 00:32:17,125
Lad os se, hvad er dit navn?

730
00:32:17,125 --> 00:32:17,550
>> Publikum: Andrew.

731
00:32:17,550 --> 00:32:18,800
>> David J. MALAN: Andrew,
du er nummer 9.

732
00:32:18,800 --> 00:32:19,540
Rart at møde dig.

733
00:32:19,540 --> 00:32:20,400
Værsgo.

734
00:32:20,400 --> 00:32:21,593

735
00:32:21,593 --> 00:32:22,176
Publikum: Jen.

736
00:32:22,176 --> 00:32:22,662
David J. MALAN: Jen.

737
00:32:22,662 --> 00:32:23,162
David.

738
00:32:23,162 --> 00:32:23,765
Nummer 17.

739
00:32:23,765 --> 00:32:24,950

740
00:32:24,950 --> 00:32:25,450
Ja?

741
00:32:25,450 --> 00:32:26,400
>> PUBLIKUM: Jeg er Julia.

742
00:32:26,400 --> 00:32:26,980
>> David J. MALAN: Julia, David.

743
00:32:26,980 --> 00:32:27,545
Nummer 20.

744
00:32:27,545 --> 00:32:28,507

745
00:32:28,507 --> 00:32:29,340
Publikum: kristen.

746
00:32:29,340 --> 00:32:30,715
David J. MALAN Christian, David.

747
00:32:30,715 --> 00:32:31,541
Nummer 22.

748
00:32:31,541 --> 00:32:32,040
Og?

749
00:32:32,040 --> 00:32:32,649
>> Publikum: JP.

750
00:32:32,649 --> 00:32:33,440
David J. MALAN: JP.

751
00:32:33,440 --> 00:32:34,880
Number 29.

752
00:32:34,880 --> 00:32:37,080
Så gå videre og få in-- Uh oh.

753
00:32:37,080 --> 00:32:38,486

754
00:32:38,486 --> 00:32:38,985
Uh oh.

755
00:32:38,985 --> 00:32:39,650

756
00:32:39,650 --> 00:32:40,150
Standby.

757
00:32:40,150 --> 00:32:41,360

758
00:32:41,360 --> 00:32:42,390
20.

759
00:32:42,390 --> 00:32:43,682
Er der nogen der har en markør?

760
00:32:43,682 --> 00:32:44,890
Publikum: Jeg har en Sharpie.

761
00:32:44,890 --> 00:32:45,660
David J. MALAN: Har du en Sharpie?

762
00:32:45,660 --> 00:32:46,159
OK.

763
00:32:46,159 --> 00:32:47,577

764
00:32:47,577 --> 00:32:49,160
Og nogen der har et stykke papir?

765
00:32:49,160 --> 00:32:51,562

766
00:32:51,562 --> 00:32:52,270
Gem forelæsningen.

767
00:32:52,270 --> 00:32:53,810

768
00:32:53,810 --> 00:32:55,362
Kom.

769
00:32:55,362 --> 00:32:56,320
PUBLIKUM: Vi har fået det.

770
00:32:56,320 --> 00:32:57,600
David J. MALAN: Vi fik det?

771
00:32:57,600 --> 00:32:58,577
Okay, tak.

772
00:32:58,577 --> 00:33:01,380

773
00:33:01,380 --> 00:33:02,520
Her går vi.

774
00:33:02,520 --> 00:33:03,582
Var det fra dig?

775
00:33:03,582 --> 00:33:04,540
Du har lige reddet dagen.

776
00:33:04,540 --> 00:33:05,670

777
00:33:05,670 --> 00:33:07,220
Så 29.

778
00:33:07,220 --> 00:33:10,510

779
00:33:10,510 --> 00:33:11,110
Okay.

780
00:33:11,110 --> 00:33:13,360

781
00:33:13,360 --> 00:33:14,890
Jeg stavede 29, men OK.

782
00:33:14,890 --> 00:33:15,720
Værsgo.

783
00:33:15,720 --> 00:33:18,114
Okay, vil jeg give dig
pennen tilbage et øjeblik.

784
00:33:18,114 --> 00:33:19,280
Så vi har disse folk her.

785
00:33:19,280 --> 00:33:20,330
Lad os få en anden.

786
00:33:20,330 --> 00:33:23,750
Gabe, du ønsker at spille
det første element her?

787
00:33:23,750 --> 00:33:25,705
Vi har brug for dig til at pege
på disse fine folk.

788
00:33:25,705 --> 00:33:26,930

789
00:33:26,930 --> 00:33:31,030
Så 9, 17, 20, 22, sortere
af 29, og derefter 34.

790
00:33:31,030 --> 00:33:32,160

791
00:33:32,160 --> 00:33:33,325
Har vi mister nogen?

792
00:33:33,325 --> 00:33:33,950
Jeg har en 34.

793
00:33:33,950 --> 00:33:36,730
Hvor did-- OK, der ønsker at være 34?

794
00:33:36,730 --> 00:33:37,605
OK, kom op, 34.

795
00:33:37,605 --> 00:33:39,280

796
00:33:39,280 --> 00:33:41,220
Okay, vil dette være
værd at klimaks.

797
00:33:41,220 --> 00:33:41,550
Hvad er dit navn?

798
00:33:41,550 --> 00:33:42,040
>> Publikum: Peter.

799
00:33:42,040 --> 00:33:43,456
>> David J. MALAN: Peter, kom op.

800
00:33:43,456 --> 00:33:46,810
Okay, så her er en
hel masse noder.

801
00:33:46,810 --> 00:33:49,060
Hver af jer repræsenterer
en af ​​disse rektangler.

802
00:33:49,060 --> 00:33:51,930
Og Gabe, det lidt underligt
Menneske, repræsenterer først.

803
00:33:51,930 --> 00:33:54,850
Så hans pointer er lidt mindre
på skærmen end alle andre.

804
00:33:54,850 --> 00:33:58,120
Og i dette tilfælde, hver af din venstre
hænder vil enten pege ned,

805
00:33:58,120 --> 00:34:01,085
derved repræsenterer nul, så
blot fravær af en pointer,

806
00:34:01,085 --> 00:34:03,210
eller det kommer til at pege
ved et knudepunkt ved siden af ​​dig.

807
00:34:03,210 --> 00:34:05,440
>> Så lige nu, hvis du pryder
jer som på billedet

808
00:34:05,440 --> 00:34:07,585
her, gå videre og punkt
på hinanden, med Gabe

809
00:34:07,585 --> 00:34:11,030
navnlig peger på
nummer 9 til at repræsentere listen.

810
00:34:11,030 --> 00:34:14,050
OK, og nummer 34, venstre hånd
blot skal pege på gulvet.

811
00:34:14,050 --> 00:34:15,750
>> OK, så dette er den linkede liste.

812
00:34:15,750 --> 00:34:17,580
Så dette er det pågældende scenario.

813
00:34:17,580 --> 00:34:20,210
Og ja, det er repræsentativt
af en klasse af problemer

814
00:34:20,210 --> 00:34:21,929
at du måske forsøge at løse med kode.

815
00:34:21,929 --> 00:34:25,020
Du ønsker at i sidste ende indsætte
et nyt element i listen.

816
00:34:25,020 --> 00:34:27,494
I dette tilfælde vil vi
prøve at indsætte nummer 55.

817
00:34:27,494 --> 00:34:28,500

818
00:34:28,500 --> 00:34:30,860
Men der vil være
forskellige sager at overveje.

819
00:34:30,860 --> 00:34:34,409
Og ja, dette vil være en
af de store-billede grillbarer her, er,

820
00:34:34,409 --> 00:34:35,659
hvad er de forskellige sager.

821
00:34:35,659 --> 00:34:39,120
Hvad er anderledes, hvis betingelser eller
grene at dit program kan have?

822
00:34:39,120 --> 00:34:42,024
>> Nå, det nummer, du forsøger at
indsats, som vi ved nu at være 55,

823
00:34:42,024 --> 00:34:44,650
men hvis du ikke kender
i forvejen, jeg daresay

824
00:34:44,650 --> 00:34:47,840
falder i mindst tre
mulige situationer.

825
00:34:47,840 --> 00:34:49,717
Hvor kan et nyt element være?

826
00:34:49,717 --> 00:34:51,050
Publikum: Og enden eller midten.

827
00:34:51,050 --> 00:34:54,150
David J. MALAN: I slutningen, i
midten, eller i begyndelsen.

828
00:34:54,150 --> 00:34:56,650
Så jeg hævder, at der er mindst
tre problemer, vi er nødt til at løse.

829
00:34:56,650 --> 00:34:58,691
Lad os vælge, hvad der er måske
nok den enkleste

830
00:34:58,691 --> 00:35:01,090
en, når det nye element
hører i begyndelsen.

831
00:35:01,090 --> 00:35:04,040
Så jeg har tænkt mig at få koden helt
ligesom at søge, som jeg lige har skrevet.

832
00:35:04,040 --> 00:35:07,670
Og jeg har tænkt mig at have ptr, som
Jeg repræsenterer her med min finger,

833
00:35:07,670 --> 00:35:08,370
som sædvanlig.

834
00:35:08,370 --> 00:35:12,430
>> Og husk, hvilken værdi
vi initialisere ptr til?

835
00:35:12,430 --> 00:35:15,300
Så vi initialiseret det til null i første omgang.

836
00:35:15,300 --> 00:35:16,410

837
00:35:16,410 --> 00:35:19,770
Men hvad gjorde vi gøre, når vi
var inde i vores søgefunktionen?

838
00:35:19,770 --> 00:35:20,940

839
00:35:20,940 --> 00:35:24,870
Vi sætter det lig med det første,
hvilket ikke betyder, at gøre dette.

840
00:35:24,870 --> 00:35:25,890

841
00:35:25,890 --> 00:35:30,570
Hvis jeg sat ptr lig først, hvad
skal min hånd virkelig peger på?

842
00:35:30,570 --> 00:35:31,070
Højre.

843
00:35:31,070 --> 00:35:33,290
Så hvis Gabe og jeg går
at være lige store værdier her,

844
00:35:33,290 --> 00:35:34,760
er vi nødt til både punkt nummer 9.

845
00:35:34,760 --> 00:35:36,420
>> Så dette var begyndelsen af ​​vores historie.

846
00:35:36,420 --> 00:35:38,700
Og nu er det bare ligetil,
selvom syntaksen er ny.

847
00:35:38,700 --> 00:35:40,580
Begrebsmæssigt er det bare lineær søgning.

848
00:35:40,580 --> 00:35:42,750
Er 55 svarende til 9?

849
00:35:42,750 --> 00:35:45,559
Eller rettere, lad os sige mindre end 9.

850
00:35:45,559 --> 00:35:47,600
Fordi jeg forsøger at
regne ud, hvor at sætte 55.

851
00:35:47,600 --> 00:35:51,270
Mindre end 9, er mindre end 17 mindre
end 20, mindre end 22, er mindre end 29,

852
00:35:51,270 --> 00:35:52,510
mindre end 34, no.

853
00:35:52,510 --> 00:35:55,080
Så nu er vi i tilfælde
en af ​​mindst tre.

854
00:35:55,080 --> 00:35:59,910
>> Hvis jeg ønsker at indsætte 55 herovre, hvad
kodelinjer behov for at få udført?

855
00:35:59,910 --> 00:36:01,890
Hvordan dette billede af
mennesker har brug for at ændre?

856
00:36:01,890 --> 00:36:03,181
Hvad gør jeg med min venstre hånd?

857
00:36:03,181 --> 00:36:04,530

858
00:36:04,530 --> 00:36:07,360
Dette bør være nul i første omgang,
fordi jeg er i slutningen af ​​listen.

859
00:36:07,360 --> 00:36:09,318
Og hvad der skal ske
her med Peter, var det?

860
00:36:09,318 --> 00:36:10,520

861
00:36:10,520 --> 00:36:12,430
Han er naturligvis vil pege på mig.

862
00:36:12,430 --> 00:36:15,580
Så jeg hævder, at der er mindst to linjer
kode i prøven koden fra i dag

863
00:36:15,580 --> 00:36:18,570
det kommer til at gennemføre denne
scenario tilsætte 55 ved halen.

864
00:36:18,570 --> 00:36:20,950
Og kunne jeg have nogen hop
op og bare repræsenterer 55?

865
00:36:20,950 --> 00:36:22,200
Okay, du er den nye 55.

866
00:36:22,200 --> 00:36:23,580

867
00:36:23,580 --> 00:36:27,054
>> Så nu, hvad hvis det næste
scenarie kommer sammen,

868
00:36:27,054 --> 00:36:29,720
og vi ønsker at indsætte på
begynder eller lederen af ​​denne liste?

869
00:36:29,720 --> 00:36:31,100
Og hvad er dit navn, nummer 55?

870
00:36:31,100 --> 00:36:31,420
>> Publikum: Jack.

871
00:36:31,420 --> 00:36:32,295
>> David J. MALAN: Jack?

872
00:36:32,295 --> 00:36:33,585
OK, rart at møde dig.

873
00:36:33,585 --> 00:36:34,210
Velkommen ombord.

874
00:36:34,210 --> 00:36:36,640
Så nu vil vi
indsætte, siger, nummer 5.

875
00:36:36,640 --> 00:36:39,840
Her er det andet tilfælde af
tre vi kom op med før.

876
00:36:39,840 --> 00:36:43,050
Så hvis 5 hører i starten,
lad os se, hvordan vi finder ud af det.

877
00:36:43,050 --> 00:36:46,310
Jeg initialisere min ptr
pointer til nummer 9 igen.

878
00:36:46,310 --> 00:36:49,140
Og jeg indså, åh, 5 er mindre end 9.

879
00:36:49,140 --> 00:36:50,880
Så løse dette billede til os.

880
00:36:50,880 --> 00:36:54,820
Hvis hænder, Gabe eller Davids
eller-- hvad er nummer 9 navn?

881
00:36:54,820 --> 00:36:55,740
>> Publikum: Jen.

882
00:36:55,740 --> 00:36:58,406
>> David J. MALAN: Jens hands--
hvilke af vores hænder nødt til at ændre?

883
00:36:58,406 --> 00:36:58,905

884
00:36:58,905 --> 00:37:00,970
OK, så Gabe peger på, hvad nu?

885
00:37:00,970 --> 00:37:01,640
På mig.

886
00:37:01,640 --> 00:37:02,750
Jeg er den nye node.

887
00:37:02,750 --> 00:37:04,870
Så jeg vil bare slags træk
her for at se det visuelt.

888
00:37:04,870 --> 00:37:06,435
Og i mellemtiden hvad gør jeg pege det?

889
00:37:06,435 --> 00:37:07,910

890
00:37:07,910 --> 00:37:09,020
Stadig hvor jeg peger.

891
00:37:09,020 --> 00:37:10,000
Så det er det.

892
00:37:10,000 --> 00:37:13,717
Så bare virkelig én linje kode rettelser
dette særlige spørgsmål, synes det.

893
00:37:13,717 --> 00:37:14,800
Okay, så det er godt.

894
00:37:14,800 --> 00:37:17,580
Og kan nogen være en pladsholder for 5?

895
00:37:17,580 --> 00:37:18,080
Kom op.

896
00:37:18,080 --> 00:37:20,270

897
00:37:20,270 --> 00:37:21,320
Vi får dig næste gang.

898
00:37:21,320 --> 00:37:24,280
>> Okay, så nu-- og
Som en sidebemærkning navne

899
00:37:24,280 --> 00:37:28,510
Jeg gør ikke udtrykkeligt nævner retten
nu, Gæt pointer, forgænger pointer

900
00:37:28,510 --> 00:37:31,260
og nye pointer, det er
blot navnene givet

901
00:37:31,260 --> 00:37:35,280
i prøven kode til pegepinde eller
mine hænder der er slags peger rundt.

902
00:37:35,280 --> 00:37:36,060
Hvad er dit navn?

903
00:37:36,060 --> 00:37:36,700
>> Publikum: Christine.

904
00:37:36,700 --> 00:37:37,100
>> David J. MALAN: Christine.

905
00:37:37,100 --> 00:37:38,090
Velkommen ombord.

906
00:37:38,090 --> 00:37:42,180
Okay, så lad os overveje nu
en lidt mere irriterende scenario

907
00:37:42,180 --> 00:37:46,350
hvorved jeg ønsker at indsætte
noget lignende 26 i dette.

908
00:37:46,350 --> 00:37:47,090
20?

909
00:37:47,090 --> 00:37:47,590
Hvad?

910
00:37:47,590 --> 00:37:50,510
Disse are-- god ting vi har denne pen.

911
00:37:50,510 --> 00:37:51,955
Okay, 20.

912
00:37:51,955 --> 00:37:53,640

913
00:37:53,640 --> 00:37:57,570
Hvis nogen kunne få et andet stykke
papir klar, bare i case-- okay.

914
00:37:57,570 --> 00:37:58,370
Åh, interessant.

915
00:37:58,370 --> 00:37:59,760

916
00:37:59,760 --> 00:38:02,390
Nå dette er et eksempel
af et foredrag bug.

917
00:38:02,390 --> 00:38:03,894
OK, så hvad er dit navn igen?

918
00:38:03,894 --> 00:38:04,560
Publikum: Julia.

919
00:38:04,560 --> 00:38:07,559
David J. MALAN: Julia, kan du pop
ud og foregive du var aldrig der?

920
00:38:07,559 --> 00:38:09,040
OK, det aldrig sket.

921
00:38:09,040 --> 00:38:09,680
Tak.

922
00:38:09,680 --> 00:38:12,180
Så formoder, at vi vil indsætte
Julia i denne forbundet liste.

923
00:38:12,180 --> 00:38:13,780
Hun er tallet 20.

924
00:38:13,780 --> 00:38:15,530
Og selvfølgelig er hun
kommer til at høre til den

925
00:38:15,530 --> 00:38:17,521
begin-- ikke pege på noget endnu.

926
00:38:17,521 --> 00:38:20,020
Så din hånd kan slags være
ned nul eller nogle skrald værdi.

927
00:38:20,020 --> 00:38:21,210
Lad os fortælle hurtig historie.

928
00:38:21,210 --> 00:38:22,980
Jeg peger på nummer 5 denne gang.

929
00:38:22,980 --> 00:38:23,880
Så tjek jeg 9.

930
00:38:23,880 --> 00:38:25,130
Så tjek jeg 17.

931
00:38:25,130 --> 00:38:26,247
Så tjek jeg 22.

932
00:38:26,247 --> 00:38:27,650

933
00:38:27,650 --> 00:38:32,485
Og jeg indser, ooh, Julia
nødt til at gå, før 22.

934
00:38:32,485 --> 00:38:33,580

935
00:38:33,580 --> 00:38:34,660
Så hvad skal der ske?

936
00:38:34,660 --> 00:38:35,786

937
00:38:35,786 --> 00:38:36,910
Hvis hænder nødt til at ændre?

938
00:38:36,910 --> 00:38:38,360
Julias, mine, eller--
hvad er dit navn igen?

939
00:38:38,360 --> 00:38:39,230
>> Publikum: kristen.

940
00:38:39,230 --> 00:38:40,060
>> David J. MALAN Christian eller?

941
00:38:40,060 --> 00:38:40,560
>> Publikum: Andy.

942
00:38:40,560 --> 00:38:40,905
>> David J. MALAN: Andy.

943
00:38:40,905 --> 00:38:41,654
Kristen eller Andy?

944
00:38:41,654 --> 00:38:44,280

945
00:38:44,280 --> 00:38:45,690
Andy har brug for at pege på?

946
00:38:45,690 --> 00:38:46,780

947
00:38:46,780 --> 00:38:47,341
Julia.

948
00:38:47,341 --> 00:38:47,840
Okay.

949
00:38:47,840 --> 00:38:48,960
Så Andy, vil du pege på Julia?

950
00:38:48,960 --> 00:38:50,120
Men vent et øjeblik.

951
00:38:50,120 --> 00:38:53,260
I historien hidtil,
Jeg er den slags en

952
00:38:53,260 --> 00:38:56,800
i ladning, i den forstand, at
pointer er den ting, der er

953
00:38:56,800 --> 00:38:57,850
bevæger sig gennem listen.

954
00:38:57,850 --> 00:39:00,800
Vi har måske et navn til Andy, men
der er ingen variabel kaldet Andy.

955
00:39:00,800 --> 00:39:04,320
Den eneste anden variabel vi har, er
første, der har repræsenteret af Gabe.

956
00:39:04,320 --> 00:39:07,690
>> Så dette er faktisk grunden således
langt har vi ikke behov for dette.

957
00:39:07,690 --> 00:39:10,846
Men nu på skærmen er der
nævne igen af ​​Pred pointer.

958
00:39:10,846 --> 00:39:11,970
Så lad mig være mere præcis.

959
00:39:11,970 --> 00:39:14,820
Hvis dette er pointer, jeg havde bedre
få lidt mere intelligent

960
00:39:14,820 --> 00:39:15,950
om min iteration.

961
00:39:15,950 --> 00:39:19,580
Hvis du ikke har noget imod min går igennem her
igen, peger her, peger her.

962
00:39:19,580 --> 00:39:22,500
Men lad mig få en Pred pointer,
forgænger pointer, der er

963
00:39:22,500 --> 00:39:24,740
slags peger på
element Jeg var lige ved.

964
00:39:24,740 --> 00:39:27,330
Så når jeg går her, nu
min venstre hånd opdateringer.

965
00:39:27,330 --> 00:39:29,370
Når jeg går her min venstre hånd opdateringer.

966
00:39:29,370 --> 00:39:33,090
Og nu har jeg ikke blot en pegepind til
det element, der går efter Julia,

967
00:39:33,090 --> 00:39:36,300
Jeg har stadig en pointer til
Andy, elementet før.

968
00:39:36,300 --> 00:39:39,430
Så du har adgang til, i det væsentlige,
rasp, hvis du vil,

969
00:39:39,430 --> 00:39:41,500
til alle de nødvendige pointere.

970
00:39:41,500 --> 00:39:43,710
>> Så hvis jeg peger på
Andy og jeg også pege

971
00:39:43,710 --> 00:39:47,105
på Christian, hvis hænder
bør nu påpeges andetsteds?

972
00:39:47,105 --> 00:39:48,770

973
00:39:48,770 --> 00:39:51,960
Så Andy kan nu pege på Julia.

974
00:39:51,960 --> 00:39:54,460
Julia kan nu pege på Christian.

975
00:39:54,460 --> 00:39:56,950
Fordi hun kan kopiere min
højre hånds pointer.

976
00:39:56,950 --> 00:40:00,044
Og der effektivt sætter dig
tilbage til dette sted her.

977
00:40:00,044 --> 00:40:02,460
Så kort, selvom det
tager os slags evigt

978
00:40:02,460 --> 00:40:04,510
faktisk opdatere en
linkede liste, indser

979
00:40:04,510 --> 00:40:06,580
at operationerne
er relativt enkle.

980
00:40:06,580 --> 00:40:10,030
Det er af en, to, tre
linjer kode i sidste ende.

981
00:40:10,030 --> 00:40:12,780
Men svøbt omkring dem
linjer kode formentlig

982
00:40:12,780 --> 00:40:16,350
er en smule logik, der effektivt
spørger, hvor er vi?

983
00:40:16,350 --> 00:40:18,970
Er vi ved begyndelsen,
midten, eller enden?

984
00:40:18,970 --> 00:40:21,890
>> Nu er der sikkert nogle andre
operationer, vi kunne gennemføre.

985
00:40:21,890 --> 00:40:24,880
Og disse billeder her bare skildrer
hvad vi lige gjorde med mennesker.

986
00:40:24,880 --> 00:40:26,080
Hvad om fjernelse?

987
00:40:26,080 --> 00:40:30,650
Hvis jeg vil, for eksempel,
fjerne nummer 34 eller 55,

988
00:40:30,650 --> 00:40:34,680
Jeg kunne have den samme slags kode,
men jeg har tænkt mig at brug et eller to trin.

989
00:40:34,680 --> 00:40:36,110
For hvad er nyt?

990
00:40:36,110 --> 00:40:40,460
Hvis jeg fjerner nogen i slutningen,
som nummer 55 og derefter 34

991
00:40:40,460 --> 00:40:42,995
hvad også har til at ændre, som jeg gør det?

992
00:40:42,995 --> 00:40:44,870
Jeg er nødt til ikke evict--
hvad er dit navn igen?

993
00:40:44,870 --> 00:40:45,380
>> Publikum: Jack.

994
00:40:45,380 --> 00:40:46,255
>> David J. MALAN: Jack.

995
00:40:46,255 --> 00:40:49,770
Jeg er nødt til ikke kun evict-- gratis Jack,
så bogstaveligt ringe gratis Jack, eller i det mindste

996
00:40:49,770 --> 00:40:53,530
markøren der også, men nu
hvad der skal ændres med Peter?

997
00:40:53,530 --> 00:40:55,510
Hans hånd bedre start pegende nedad.

998
00:40:55,510 --> 00:40:59,300
Fordi så snart jeg ringe gratis på
Jack, hvis Peters stadig peger på Jack

999
00:40:59,300 --> 00:41:02,530
og derfor vil jeg holde gennemkører
listen over og adgang denne pointer,

1000
00:41:02,530 --> 00:41:05,650
det er når vores gamle segmentering ven
fejl kan faktisk sparke.

1001
00:41:05,650 --> 00:41:07,860
Fordi vi har givet den
hukommelse tilbage til Jack.

1002
00:41:07,860 --> 00:41:10,760
>> Du kan bo der
akavet for bare et øjeblik.

1003
00:41:10,760 --> 00:41:13,410
Fordi vi har bare et par
slutoperationerne at overveje.

1004
00:41:13,410 --> 00:41:15,600
Afskedigelse af lederen af ​​listen,
eller beginning-- og denne ene er

1005
00:41:15,600 --> 00:41:16,349
lidt irriterende.

1006
00:41:16,349 --> 00:41:19,640
Fordi vi er nødt til at vide, at Gabe
er en slags særligt i dette program.

1007
00:41:19,640 --> 00:41:21,440
Fordi ja, han har sin egen pointer.

1008
00:41:21,440 --> 00:41:24,860
Han er ikke bare at blive peget på,
som er næsten alle andre her.

1009
00:41:24,860 --> 00:41:28,112
>> Så når hovedet af listen er
fjernet, hvis hænder nødt til at ændre nu?

1010
00:41:28,112 --> 00:41:29,070
Hvad er dit navn igen?

1011
00:41:29,070 --> 00:41:29,450
>> Publikum: Christine.

1012
00:41:29,450 --> 00:41:31,408
>> David J. MALAN: Jeg er forfærdelig
på navne, tilsyneladende.

1013
00:41:31,408 --> 00:41:34,011
Så Christine og Gabe,
hvis hænder nødt til at ændre

1014
00:41:34,011 --> 00:41:36,510
når vi forsøger at fjerne Christine,
nummer 5, fra billedet?

1015
00:41:36,510 --> 00:41:37,550

1016
00:41:37,550 --> 00:41:38,820
OK, så lad os gøre Gabe.

1017
00:41:38,820 --> 00:41:40,950
Gabe kommer til at pege,
formodentlig på nummer 9.

1018
00:41:40,950 --> 00:41:42,230

1019
00:41:42,230 --> 00:41:44,642
Men hvad næste der skal ske?

1020
00:41:44,642 --> 00:41:46,600
Publikum: Christine burde
være nul [uhørligt].

1021
00:41:46,600 --> 00:41:50,244
David J. MALAN: OK, bør man nok
make-- Jeg hørte "nul" et eller andet sted.

1022
00:41:50,244 --> 00:41:51,410
Publikum: Null og fri hende.

1023
00:41:51,410 --> 00:41:51,855
David J. MALAN: Null hvad?

1024
00:41:51,855 --> 00:41:53,074
Publikum: Null og fri hende.

1025
00:41:53,074 --> 00:41:54,490
David J. MALAN: Null og fri hende.

1026
00:41:54,490 --> 00:41:55,422
Så det er meget let.

1027
00:41:55,422 --> 00:41:58,380
Og det er perfekt, at du nu sortere
af stående der, der ikke tilhører.

1028
00:41:58,380 --> 00:42:00,430
Fordi du har været
afkoblet fra listen.

1029
00:42:00,430 --> 00:42:02,820
Du har faktisk været
forældreløse fra listen.

1030
00:42:02,820 --> 00:42:07,770
Og så må vi hellere kalde gratis nu på
Christine at give denne hukommelse tilbage.

1031
00:42:07,770 --> 00:42:10,240
Ellers hver gang vi
slette en node fra listen

1032
00:42:10,240 --> 00:42:14,230
vi måske gøre listen
kortere, men ikke faktisk faldende

1033
00:42:14,230 --> 00:42:15,096
størrelse i hukommelsen.

1034
00:42:15,096 --> 00:42:17,720
Og så hvis vi holde tilføje og
tilføjer, tilføjer ting til listen,

1035
00:42:17,720 --> 00:42:19,280
min computer kan få langsommere
og langsommere og langsommere,

1036
00:42:19,280 --> 00:42:21,740
fordi jeg kører ud af
hukommelse, selv om jeg faktisk ikke

1037
00:42:21,740 --> 00:42:25,580
hjælp Christines bytes
hukommelse længere.

1038
00:42:25,580 --> 00:42:28,500
>> Så i sidste ende er der andre
scenarier, af course-- fjernelse

1039
00:42:28,500 --> 00:42:30,640
i midten, fjernelse
i slutningen, som vi så.

1040
00:42:30,640 --> 00:42:32,348
Men mere interessant
Udfordringen er nu

1041
00:42:32,348 --> 00:42:34,770
vil være at overveje præcis
hvad køretiden er.

1042
00:42:34,770 --> 00:42:36,640
Så ikke alene kan du holde din
stykker papir, hvis Gabe,

1043
00:42:36,640 --> 00:42:38,640
du ville ikke have noget imod at give
alle en stress bold.

1044
00:42:38,640 --> 00:42:42,100
Tak så meget til vores linkede liste
frivillige her, hvis du kunne.

1045
00:42:42,100 --> 00:42:45,320
>> [Applaus]

1046
00:42:45,320 --> 00:42:46,700
>> David J. MALAN: Okay.

1047
00:42:46,700 --> 00:42:51,110
Så et par analytisk
spørgsmål så, hvis jeg kunne.

1048
00:42:51,110 --> 00:42:59,670
Vi har set denne notation før,
store O og omega, øvre grænser

1049
00:42:59,670 --> 00:43:02,520
og nedre grænser på
køretid nogle algoritme.

1050
00:43:02,520 --> 00:43:04,950
Så lad os overveje bare
et par spørgsmål.

1051
00:43:04,950 --> 00:43:07,090
>> En, og vi sagde det
før, hvad er kørende

1052
00:43:07,090 --> 00:43:10,647
tid søgen efter en
liste i form af store O?

1053
00:43:10,647 --> 00:43:13,480
Hvad er en øvre grænse på driften
tid på at søge en linket liste

1054
00:43:13,480 --> 00:43:16,340
som gennemført ved vores frivillige her?

1055
00:43:16,340 --> 00:43:17,820
Det er stort O n, lineær.

1056
00:43:17,820 --> 00:43:20,630
Fordi i værste fald,
elementet, ligesom 55,

1057
00:43:20,630 --> 00:43:23,830
vi måske være på udkig efter kan være, hvor
Jack var, hele vejen i slutningen.

1058
00:43:23,830 --> 00:43:28,250
Og desværre, i modsætning til et array
vi kan ikke få lyst denne gang.

1059
00:43:28,250 --> 00:43:31,820
Selvom alle vores mennesker var
sorteret fra små elementer, 5,

1060
00:43:31,820 --> 00:43:35,900
hele vejen op til det større element
55, det er normalt en god ting.

1061
00:43:35,900 --> 00:43:38,815
Men hvad betyder denne antagelse
ikke længere tillade os at gøre?

1062
00:43:38,815 --> 00:43:39,775

1063
00:43:39,775 --> 00:43:40,650
Publikum: [uhørligt]

1064
00:43:40,650 --> 00:43:40,920
David J. MALAN: Sig det igen?

1065
00:43:40,920 --> 00:43:41,800
PUBLIKUM: Tilfældig adgang.

1066
00:43:41,800 --> 00:43:43,049
David J. MALAN: Tilfældig adgang.

1067
00:43:43,049 --> 00:43:46,330
Og til gengæld, der betyder, at vi ikke kan gøre
længere bruge svag nuller, intuition,

1068
00:43:46,330 --> 00:43:49,365
og nærliggende at bruge binær
søg og del og hersk.

1069
00:43:49,365 --> 00:43:51,240
For selvom vi
mennesker kunne naturligvis

1070
00:43:51,240 --> 00:43:54,610
se, at Andy eller Christian var
omtrent i midten af ​​listen,

1071
00:43:54,610 --> 00:43:57,670
Vi ved kun, at som et
computer ved at skumme liste

1072
00:43:57,670 --> 00:43:59,029
fra begyndelsen.

1073
00:43:59,029 --> 00:44:00,570
Så vi har givet op at random access.

1074
00:44:00,570 --> 00:44:04,380
>> Så stor O n nu er den øvre
bundet på vores søgen tid.

1075
00:44:04,380 --> 00:44:07,920
Hvad med omega i vores søgen?

1076
00:44:07,920 --> 00:44:11,535
Hvad er den nedre grænse på at søge
for nogle tal på denne liste?

1077
00:44:11,535 --> 00:44:12,410
Publikum: [uhørligt]

1078
00:44:12,410 --> 00:44:13,040
David J. MALAN: Sig det igen?

1079
00:44:13,040 --> 00:44:13,420
Publikum: One.

1080
00:44:13,420 --> 00:44:13,800
David J. MALAN: One.

1081
00:44:13,800 --> 00:44:14,760
Så konstant tid.

1082
00:44:14,760 --> 00:44:17,020
I bedste fald, Christine er
faktisk i begyndelsen af ​​listen.

1083
00:44:17,020 --> 00:44:19,020
Og vi leder efter
nummer 5, så vi fandt hende.

1084
00:44:19,020 --> 00:44:19,787
Så nogen big deal.

1085
00:44:19,787 --> 00:44:22,370
Men hun er nødt til at være på
starten af ​​listen i denne sag.

1086
00:44:22,370 --> 00:44:23,745
Hvad med noget lignende Delete?

1087
00:44:23,745 --> 00:44:24,717

1088
00:44:24,717 --> 00:44:26,300
Hvad hvis du ønsker at slette et element?

1089
00:44:26,300 --> 00:44:29,200
Hvad er den øvre grænse og nedre grænse
om sletning af noget fra en sammenkædet

1090
00:44:29,200 --> 00:44:29,699
liste?

1091
00:44:29,699 --> 00:44:35,195

1092
00:44:35,195 --> 00:44:36,070
Publikum: [uhørligt]

1093
00:44:36,070 --> 00:44:36,420
David J. MALAN: Sig det igen?

1094
00:44:36,420 --> 00:44:37,067
PUBLIKUM: n.

1095
00:44:37,067 --> 00:44:38,900
David J. MALAN: n er
faktisk den øvre grænse.

1096
00:44:38,900 --> 00:44:41,700
Fordi der i værste fald forsøger vi
at slette Jack, ligesom vi lige gjorde.

1097
00:44:41,700 --> 00:44:43,050
Han er hele vejen i slutningen.

1098
00:44:43,050 --> 00:44:45,419
Tager os for evigt, eller
n trin for at finde ham.

1099
00:44:45,419 --> 00:44:46,460
Så det er en øvre grænse.

1100
00:44:46,460 --> 00:44:47,430
Det er lineær, helt sikkert.

1101
00:44:47,430 --> 00:44:50,970
Og den bedste sag køretid, eller
de nedre grænser i bedste fald

1102
00:44:50,970 --> 00:44:51,975
ville være konstant tid.

1103
00:44:51,975 --> 00:44:54,600
Fordi vi måske forsøger at slette
Christine og vi bare få heldige

1104
00:44:54,600 --> 00:44:55,558
hun er i begyndelsen.

1105
00:44:55,558 --> 00:44:56,350
Vent nu lige lidt.

1106
00:44:56,350 --> 00:44:59,370
Gabe var også i starten,
og vi havde også til at opdatere Gabe.

1107
00:44:59,370 --> 00:45:01,150
Så det var ikke kun et skridt.

1108
00:45:01,150 --> 00:45:04,210
Så er det faktisk konstant
tid, i bedste fald,

1109
00:45:04,210 --> 00:45:06,345
at fjerne det mindste element?

1110
00:45:06,345 --> 00:45:07,360

1111
00:45:07,360 --> 00:45:10,960
Det er, selv om det kan være to,
tre, eller endda 100 linjer kode,

1112
00:45:10,960 --> 00:45:14,000
hvis det er det samme antal
linjer, ikke i nogen løkke,

1113
00:45:14,000 --> 00:45:16,577
og uafhængigt af størrelsen
af listen, absolut.

1114
00:45:16,577 --> 00:45:18,660
Sletning elementet på
begyndelsen af ​​listen,

1115
00:45:18,660 --> 00:45:21,940
selv om vi har at gøre med
Gabe er stadig konstant tid.

1116
00:45:21,940 --> 00:45:24,220
>> Så dette virker som en
massiv tilbageskridt.

1117
00:45:24,220 --> 00:45:27,000
Og sikke et spild af tid
hvis i uge én og uge

1118
00:45:27,000 --> 00:45:30,250
nul havde vi ikke kun
pseudokode kode, men den faktiske kode

1119
00:45:30,250 --> 00:45:35,780
at gennemføre noget, der er log
basen n, eller log snarere af n, bunden 2,

1120
00:45:35,780 --> 00:45:37,150
i form af sin køretid.

1121
00:45:37,150 --> 00:45:40,710
Så hvorfor dælen skulle vi ønsker at starte
ved hjælp af noget som en sammenkædet liste?

1122
00:45:40,710 --> 00:45:41,517
Ja.

1123
00:45:41,517 --> 00:45:44,022
>> PUBLIKUM: Så du kan tilføje
elementer til arrayet.

1124
00:45:44,022 --> 00:45:46,230
David J. MALAN: Så du kan
tilføje elementer til arrayet.

1125
00:45:46,230 --> 00:45:47,550
Og det er også tematisk.

1126
00:45:47,550 --> 00:45:49,740
Og vi vil fortsætte med at se
dette afvejning, meget

1127
00:45:49,740 --> 00:45:51,573
ligesom vi har set en
trade-off med fusionere slags.

1128
00:45:51,573 --> 00:45:54,606
Vi kunne virkelig fremskynde
søgning eller sortering snarere

1129
00:45:54,606 --> 00:45:57,480
hvis vi bruger lidt mere plads og
have en ekstra bid af en hukommelse

1130
00:45:57,480 --> 00:45:58,760
eller et array til sammenfletning slags.

1131
00:45:58,760 --> 00:46:01,270
Men vi bruger mere
plads, men vi sparer tid.

1132
00:46:01,270 --> 00:46:04,820
I dette tilfælde er vi
opgiver tid, men vi er

1133
00:46:04,820 --> 00:46:08,170
opnå fleksibilitet,
dynamik hvis du vil,

1134
00:46:08,170 --> 00:46:10,280
som nok er et positivt træk.

1135
00:46:10,280 --> 00:46:11,520
>> Vi er også at bruge rummet.

1136
00:46:11,520 --> 00:46:13,710
I hvilken forstand er en sammenkædet
liste dyrere

1137
00:46:13,710 --> 00:46:15,700
i form af plads end et array?

1138
00:46:15,700 --> 00:46:18,379

1139
00:46:18,379 --> 00:46:19,920
Hvor er den ekstra plads, der kommer fra?

1140
00:46:19,920 --> 00:46:20,460
Ja?

1141
00:46:20,460 --> 00:46:21,800
>> Publikum: [uhørligt] pointer.

1142
00:46:21,800 --> 00:46:23,310
>> David J. MALAN: Ja, vi
har også markøren.

1143
00:46:23,310 --> 00:46:25,560
Så dette er minorly irriterende
i, at der ikke længere er

1144
00:46:25,560 --> 00:46:27,780
Jeg lagring bare en int
at repræsentere en int.

1145
00:46:27,780 --> 00:46:30,990
Jeg gemmer en int og en
pointer, som også er 32 bit.

1146
00:46:30,990 --> 00:46:33,470
Så jeg bogstaveligt talt fordobling
mængden af ​​plads involveret.

1147
00:46:33,470 --> 00:46:36,040
Så det er et trade-off, men
det er i tilfælde af int.

1148
00:46:36,040 --> 00:46:39,580
Antag, at du ikke opbevare int,
men formoder hver af disse rektangler

1149
00:46:39,580 --> 00:46:43,290
eller hver af disse mennesker repræsenterede
et ord, et engelsk ord, der

1150
00:46:43,290 --> 00:46:46,430
kan bestå af fem karakterer, 10
tegn, måske endda mere.

1151
00:46:46,430 --> 00:46:49,940
Derefter tilføje blot 32 flere bits
kan være mindre af en big deal.

1152
00:46:49,940 --> 00:46:52,160
>> Hvad nu, hvis hver af de studerende
i demonstrationen

1153
00:46:52,160 --> 00:46:55,107
var bogstaveligt studerende structs der
har navne og huse og måske

1154
00:46:55,107 --> 00:46:57,065
telefonnumre og Twitter
håndtag og lignende.

1155
00:46:57,065 --> 00:46:59,564
Så alle felterne vi startede
taler om den anden dag,

1156
00:46:59,564 --> 00:47:02,410
meget mindre af en big deal som
vores knudepunkter får mere interessant

1157
00:47:02,410 --> 00:47:05,972
og store til at bruge, hvad, en ekstra
pointer bare at linke dem sammen.

1158
00:47:05,972 --> 00:47:07,180
Men ja, det er et trade-off.

1159
00:47:07,180 --> 00:47:09,560
Og ja, koden er
mere komplekse, som du vil

1160
00:47:09,560 --> 00:47:11,770
se ved at skimme igennem
det pågældende eksempel.

1161
00:47:11,770 --> 00:47:14,302
Men hvad nu hvis der var
nogle hellige gral her.

1162
00:47:14,302 --> 00:47:17,010
Hvad hvis vi ikke tage et skridt
baglæns, men et kæmpeskridt fremad

1163
00:47:17,010 --> 00:47:19,180
og gennemføre en data-
struktur via hvilken vi

1164
00:47:19,180 --> 00:47:22,870
kan finde elementer som Jack eller
Christine eller andre elementer

1165
00:47:22,870 --> 00:47:25,870
i dette array i sand konstant tid?

1166
00:47:25,870 --> 00:47:26,920
Søgning er konstant.

1167
00:47:26,920 --> 00:47:28,320
Slet er konstant.

1168
00:47:28,320 --> 00:47:29,570
Indsæt er konstant.

1169
00:47:29,570 --> 00:47:32,260
Alle disse operationer er konstant.

1170
00:47:32,260 --> 00:47:33,750
Det ville være vores hellige gral.

1171
00:47:33,750 --> 00:47:36,690
Og det er, hvor vi
vil afhente næste gang.

1172
00:47:36,690 --> 00:47:38,600
Se dig derefter.

1173
00:47:38,600 --> 00:47:39,371