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

2
00:00:00,500 --> 00:00:11,137
[MUSIK SPELA]

3
00:00:11,137 --> 00:00:12,220
DAVID J. MALAN: Okej.

4
00:00:12,220 --> 00:00:13,950
Detta är CS50.

5
00:00:13,950 --> 00:00:18,560
Detta är vecka fem fortsatte, och vi
har goda nyheter och dåliga nyheter.

6
00:00:18,560 --> 00:00:21,140
Så goda nyheten är att CS50
lanserar denna fredag.

7
00:00:21,140 --> 00:00:24,430
Om du vill gå med oss,
bege dig till den vanliga webbadressen här.

8
00:00:24,430 --> 00:00:28,670
Ännu bättre nyheter, ingen föreläsning
denna kommande måndag den 13.

9
00:00:28,670 --> 00:00:31,970
Något mindre bra nyheter,
quiz noll är nästa onsdag.

10
00:00:31,970 --> 00:00:33,840
Mer detaljer kan vara
finns på webbadressen här.

11
00:00:33,840 --> 00:00:36,340
Och under de kommande två dygnen
vi kommer att fylla i tomrummen

12
00:00:36,340 --> 00:00:39,234
när det gäller rummen
att vi kommer att ha reserverat.

13
00:00:39,234 --> 00:00:41,400
Bättre nyheter är att det ska
vara en kurs omfattande översyn

14
00:00:41,400 --> 00:00:43,570
session denna kommande
Måndag på kvällen.

15
00:00:43,570 --> 00:00:46,270
Håll ögonen öppna för kursens
hemsida för plats och detaljer.

16
00:00:46,270 --> 00:00:49,290
Sektioner, även om det är en
semester, också kommer att träffas också.

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

18
00:00:50,490 --> 00:00:52,940
Bästa nyheter, föreläsa nästa fredag.

19
00:00:52,940 --> 00:00:56,220
Så det här är en tradition som vi
har, enligt kursplanen.

20
00:00:56,220 --> 00:00:58,100
Bara-- det kommer att bli fantastiskt.

21
00:00:58,100 --> 00:01:02,510
Du kommer att se saker som
konstant tidsdatastrukturer

22
00:01:02,510 --> 00:01:04,730
och hashtabeller och träd och försök.

23
00:01:04,730 --> 00:01:07,150
Och vi ska tala om födelsedagsproblem.

24
00:01:07,150 --> 00:01:09,440
En hel massa saker
inväntar nästa 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
Hur som helst.

28
00:01:13,190 --> 00:01:17,080
>> Så minns att vi har varit
med fokus på den här bilden av vad som är

29
00:01:17,080 --> 00:01:18,980
insidan av vår dators minne.

30
00:01:18,980 --> 00:01:22,875
Så minne eller RAM är där program
existerar när du kör dem.

31
00:01:22,875 --> 00:01:25,215
Om du dubbelklickar på en
ikonen för att köra några program

32
00:01:25,215 --> 00:01:27,520
eller dubbelklicka på ett
ikonen för att öppna en fil,

33
00:01:27,520 --> 00:01:30,430
det är laddat från hårda
köra bil eller SSD-enheten

34
00:01:30,430 --> 00:01:34,190
i RAM, Random Access Memory, där
den lever tills strömmen stängs av,

35
00:01:34,190 --> 00:01:36,700
den bärbara datorn locket stängs,
eller om du avslutar programmet.

36
00:01:36,700 --> 00:01:38,960
>> Nu när minnet av
som du förmodligen

37
00:01:38,960 --> 00:01:41,950
1 gigabyte i dessa dagar, 2
gigabyte, eller till och med mycket mer,

38
00:01:41,950 --> 00:01:44,420
är allmänt anges
för ett givet program

39
00:01:44,420 --> 00:01:47,170
i denna typ av rektangulära
konceptuell modell

40
00:01:47,170 --> 00:01:50,860
där vi har stapeln längst ner
och en massa andra saker på toppen.

41
00:01:50,860 --> 00:01:53,140
Saken högst upp
Vi har sett den här bilden

42
00:01:53,140 --> 00:01:55,670
innan men aldrig talat om
är den så kallade textsegment.

43
00:01:55,670 --> 00:01:58,419
Text segment är bara ett finare sätt
att säga det nollor och ettor som

44
00:01:58,419 --> 00:02:01,150
komponera din faktiska sammanställt programmet.

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

46
00:02:03,910 --> 00:02:08,030
eller när du kör dot slash Mario på en
Linux-dator på ditt terminalfönster,

47
00:02:08,030 --> 00:02:12,460
de nollor och ettor som skriver
Word eller Mario lagras tillfälligt

48
00:02:12,460 --> 00:02:16,610
i datorns RAM-minne i den så kallade
textsegment för ett speciellt program.

49
00:02:16,610 --> 00:02:19,080
Därunder går initierats
och oinitierade data.

50
00:02:19,080 --> 00:02:22,655
Det här är saker som globala variabler,
att vi inte har använt många av,

51
00:02:22,655 --> 00:02:24,910
men ibland vi har
hade globala variabler

52
00:02:24,910 --> 00:02:28,819
eller statiskt definierad strängar som
är hårdkodade ord som "hej"

53
00:02:28,819 --> 00:02:31,860
som inte tas in från användaren
som är hårdkodad i ditt program.

54
00:02:31,860 --> 00:02:34,230
>> Nu, ner på botten som vi
har den så kallade stacken.

55
00:02:34,230 --> 00:02:37,665
Och stacken, hittills, vi har varit
använder för vilka typer av ändamål?

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

57
00:02:39,706 --> 00:02:40,997
Vad stapeln använts till?

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

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

60
00:02:42,070 --> 00:02:43,320
>> DAVID J. MALAN: För funktioner?

61
00:02:43,320 --> 00:02:44,980
I vilken mening för funktioner?

62
00:02:44,980 --> 00:02:48,660
>> PUBLIK: När du ringer en funktion, den
argument kopieras till stacken.

63
00:02:48,660 --> 00:02:49,660
>> DAVID J. MALAN: Exakt.

64
00:02:49,660 --> 00:02:52,650
När du ringer en funktion, dess
argument kopieras till stacken.

65
00:02:52,650 --> 00:02:56,330
Så några X: s eller Y eller A: s eller B: s
att du passerar in i en funktion

66
00:02:56,330 --> 00:02:58,680
temporärt sätta på
den så kallade stacken,

67
00:02:58,680 --> 00:03:02,000
precis som en av Annenberg
dining hall brickor och även saker

68
00:03:02,000 --> 00:03:03,190
som lokala variabler.

69
00:03:03,190 --> 00:03:06,290
Om foo funktion eller din swap
funktionen har lokala variabler,

70
00:03:06,290 --> 00:03:08,602
som temp, dessa två
hamna på stacken.

71
00:03:08,602 --> 00:03:11,560
Nu ska vi inte prata för mycket om
dem, men dessa miljövariabler

72
00:03:11,560 --> 00:03:15,690
i botten vi såg för ett tag sedan när
Jag var futzing på tangentbordet en dag

73
00:03:15,690 --> 00:03:20,050
och jag började komma åt saker
liknande argv 100 eller argv 1000,

74
00:03:20,050 --> 00:03:22,320
bara elements-- jag glömmer
den numbers-- men att

75
00:03:22,320 --> 00:03:24,330
var inte tänkt att nås av mig.

76
00:03:24,330 --> 00:03:26,581
Vi började se lite
funky symboler på skärmen.

77
00:03:26,581 --> 00:03:28,330
De var så kallade
miljövariabler

78
00:03:28,330 --> 00:03:32,390
som globala inställningar för min
program eller till min dator, inte

79
00:03:32,390 --> 00:03:37,090
orelaterade till den nyligen
bugg som vi diskuterade,

80
00:03:37,090 --> 00:03:39,670
Shellshock, det har varit
plågar en hel del datorer.

81
00:03:39,670 --> 00:03:42,960
>> Nu slutligen i dagens fokus
vi kommer i slutändan att vara på högen.

82
00:03:42,960 --> 00:03:44,864
Detta är ytterligare en bit av minnet.

83
00:03:44,864 --> 00:03:47,030
Och i grunden allt detta
minnet är samma saker.

84
00:03:47,030 --> 00:03:48,040
Det är samma hårdvara.

85
00:03:48,040 --> 00:03:49,956
Vi är bara sorts
behandla olika kluster

86
00:03:49,956 --> 00:03:51,460
bitgrupper för olika ändamål.

87
00:03:51,460 --> 00:03:56,540
Högen kommer också vara där
variabler och minne som du begär

88
00:03:56,540 --> 00:03:58,810
från operativsystemet
lagras temporärt.

89
00:03:58,810 --> 00:04:01,890
>> Men det är lite av en problem
Här, som bilden antyder.

90
00:04:01,890 --> 00:04:05,261
Vi sorts har två
fartyg på väg att kollidera.

91
00:04:05,261 --> 00:04:08,010
För som du använder mer och mer
av stapeln, och som vi ser i dag

92
00:04:08,010 --> 00:04:11,800
framåt, eftersom du använder mer och mer av
heap, säkert dåliga saker kan hända.

93
00:04:11,800 --> 00:04:15,054
Och faktiskt, kan vi förmå att
avsiktligt eller oavsiktligt.

94
00:04:15,054 --> 00:04:16,970
Så cliffhanger sista
tiden var det här programmet,

95
00:04:16,970 --> 00:04:20,570
som inte tjänar någon funktionell
annat än att visa ändamål

96
00:04:20,570 --> 00:04:24,750
hur du som en dålig kille faktiskt kan ta
nytta av buggar i någons program

97
00:04:24,750 --> 00:04:28,460
och ta över ett program eller till och med en
hela datorsystemet eller server.

98
00:04:28,460 --> 00:04:31,660
Så bara att titta kort, du
märker att huvud i botten

99
00:04:31,660 --> 00:04:34,510
tar i kommandoraden
argument, som per argv.

100
00:04:34,510 --> 00:04:38,480
Och den har ett anrop till en funktion f,
väsentligen en namnlös funktion kallad

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

102
00:04:40,250 --> 00:04:43,960
>> Så oavsett ord användaren skriver i åtmin
prompten efter programmets namn,

103
00:04:43,960 --> 00:04:49,310
och sedan denna godtycklig funktion upp
topp, f, tar i en sträng, AKA char *,

104
00:04:49,310 --> 00:04:51,720
som vi har börjat diskutera,
och det bara kallar det "bar."

105
00:04:51,720 --> 00:04:53,310
Men vi kan kalla det vad som helst.

106
00:04:53,310 --> 00:04:57,470
Och sedan förklarar, insida
av f, en array av tecken

107
00:04:57,470 --> 00:04:59,930
kallas C-- 12 sådana tecken.

108
00:04:59,930 --> 00:05:03,580
>> Nu, genom historien jag berättade
en stund sedan, var i minnet

109
00:05:03,580 --> 00:05:06,720
är c, eller är de 12
chars kommer att hamna?

110
00:05:06,720 --> 00:05:07,570
Bara för att vara tydlig.

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

112
00:05:08,070 --> 00:05:08,590
>> Publik: På stapeln.

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

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

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

116
00:05:14,079 --> 00:05:16,120
De kommer att hamna
på den så kallade stacken.

117
00:05:16,120 --> 00:05:18,530
Nu äntligen är den här andra funktion
det är faktiskt ganska bra,

118
00:05:18,530 --> 00:05:20,571
men vi har inte riktigt använt
det själva, strncopy.

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

120
00:05:21,550 --> 00:05:25,200
Det betyder sträng kopiera, men
enbart finns N bokstäver, n tecken.

121
00:05:25,200 --> 00:05:31,990
Så n tecken blir
kopieras från bar till c.

122
00:05:31,990 --> 00:05:32,980
Och hur många?

123
00:05:32,980 --> 00:05:34,110
Längden på baren.

124
00:05:34,110 --> 00:05:36,330
Så med andra ord, att
en rad, strncopy,

125
00:05:36,330 --> 00:05:39,500
kommer att kopiera
effektivt bar in till c.

126
00:05:39,500 --> 00:05:42,340
>> Nu, bara för slags förutse
Sensmoralen i denna historia,

127
00:05:42,340 --> 00:05:44,750
vad som är potentiellt problematiskt här?

128
00:05:44,750 --> 00:05:49,710
Även om vi kollar längden
av bar och går den in strncopy,

129
00:05:49,710 --> 00:05:53,145
vad som är din gut berättar är
fortfarande trasig om det här programmet?

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

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

132
00:05:55,220 --> 00:05:57,491
>> PUBLIK: Inkluderar inte
utrymme för tomtecknet.

133
00:05:57,491 --> 00:05:59,990
DAVID J. MALAN: Inkluderar inte
utrymme för tomtecknet.

134
00:05:59,990 --> 00:06:02,073
Potentiellt, till skillnad från i
tidigare praxis gör vi inte ens

135
00:06:02,073 --> 00:06:04,810
har så mycket som en plus 1 till
rymma den nolltecken.

136
00:06:04,810 --> 00:06:06,649
Men det är ännu värre än så.

137
00:06:06,649 --> 00:06:07,940
Vad skulle vi misslyckas med att göra?

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

139
00:06:08,432 --> 00:06:09,307
>> PUBLIK: [ohörbart]

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årdkodade 12 ganska godtyckligt.

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

144
00:06:19,497 --> 00:06:21,330
Det är inte så mycket
problem, men faktum

145
00:06:21,330 --> 00:06:25,630
att vi inte ens kollar om
längden på baren är mindre än 12,

146
00:06:25,630 --> 00:06:28,530
i vilket fall det kommer att bli
säkert att sätta in det i minnet

147
00:06:28,530 --> 00:06:30,260
kallas c som vi har tilldelats.

148
00:06:30,260 --> 00:06:32,960
Faktum är att om baren är som
20 tecken långa,

149
00:06:32,960 --> 00:06:39,010
denna funktion verkar vara att kopiera
20 tecken från bar till c, och därigenom

150
00:06:39,010 --> 00:06:41,310
tar minst 8 byte
att det inte borde vara.

151
00:06:41,310 --> 00:06:42,690
Det är implikationen här.

152
00:06:42,690 --> 00:06:44,347
>> Så kort sagt, bruten programmet.

153
00:06:44,347 --> 00:06:45,180
Inte en så stor sak.

154
00:06:45,180 --> 00:06:46,360
Kanske du får en segmentering fel.

155
00:06:46,360 --> 00:06:47,651
Vi har alla haft fel i programmen.

156
00:06:47,651 --> 00:06:50,196
Vi alla kan ha fel
i program just nu.

157
00:06:50,196 --> 00:06:51,320
Men vad är innebörden?

158
00:06:51,320 --> 00:06:54,390
Tja, här är en inzoomad version av
den bild av min dators minne.

159
00:06:54,390 --> 00:06:56,230
Detta är botten av min stack.

160
00:06:56,230 --> 00:06:59,644
Och faktiskt, längst ner är det som är
kallas förälder rutin stack, finare sätt

161
00:06:59,644 --> 00:07:00,560
att säga att det är viktigaste.

162
00:07:00,560 --> 00:07:03,772
Så att den som kallas funktionen
f som vi pratar om.

163
00:07:03,772 --> 00:07:05,230
Så här är botten av stapeln.

164
00:07:05,230 --> 00:07:06,640
Returadressen är något nytt.

165
00:07:06,640 --> 00:07:08,810
Det har alltid funnits där,
alltid varit i den bilden.

166
00:07:08,810 --> 00:07:10,440
Vi kallade bara aldrig uppmärksamhet till den.

167
00:07:10,440 --> 00:07:15,290
Eftersom det blir som c fungerar är
att när ett funktionsanrop annan,

168
00:07:15,290 --> 00:07:18,780
inte bara de argument som
Funktionen får skjutas på stacken,

169
00:07:18,780 --> 00:07:22,470
inte bara funktionens lokala
variabler får skjutas på stacken,

170
00:07:22,470 --> 00:07:26,820
något som kallas en returadress
också får sätta på stacken.

171
00:07:26,820 --> 00:07:33,330
Särskilt om huvud samtal foo, huvud s
egen adress i minnet, oxe något,

172
00:07:33,330 --> 00:07:38,240
effektivt får sätta på stacken
så att när f görs verkställer det

173
00:07:38,240 --> 00:07:43,630
vet var att hoppa tillbaka i texten
segment för att fortsätta köra.

174
00:07:43,630 --> 00:07:47,760
>> Så om vi är här konceptuellt,
i main, då f anropas.

175
00:07:47,760 --> 00:07:50,200
Hur f veta vem
till handkontroll tillbaka?

176
00:07:50,200 --> 00:07:52,020
Nåväl, denna lilla
breadcrumb i rött här,

177
00:07:52,020 --> 00:07:54,978
kallas avsändaradressen, det bara
kontroller, vad är det returadress?

178
00:07:54,978 --> 00:07:57,039
Åh, låt mig gå tillbaka till huvud här.

179
00:07:57,039 --> 00:07:59,080
Och det är lite
av en grov förenkling,

180
00:07:59,080 --> 00:08:00,750
eftersom nollor och ettor
för main är tekniskt

181
00:08:00,750 --> 00:08:01,967
här uppe i tech segmentet.

182
00:08:01,967 --> 00:08:03,800
Men det är tanken. f
bara måste veta vad

183
00:08:03,800 --> 00:08:06,680
där kontrollen går till sist tillbaka.

184
00:08:06,680 --> 00:08:09,790
>> Men sättet datorer
har länge lagt ut saker

185
00:08:09,790 --> 00:08:12,320
som lokala variabler och
argumenten är så här.

186
00:08:12,320 --> 00:08:17,180
Så i den övre delen av denna bild i
blå är stackram för f, så alla

187
00:08:17,180 --> 00:08:19,630
hos minnet att f
specifikt är att använda.

188
00:08:19,630 --> 00:08:22,990
Så följaktligen märker att
bar är i denna bild.

189
00:08:22,990 --> 00:08:23,980
Bar var sin argumentation.

190
00:08:23,980 --> 00:08:27,240
Och vi hävdade att argumenten för
funktioner får skjutas på stacken.

191
00:08:27,240 --> 00:08:29,910
Och C, är naturligtvis
även i denna bild.

192
00:08:29,910 --> 00:08:33,520
>> Och bara för nota ändamål,
märke i det övre vänstra hörnet

193
00:08:33,520 --> 00:08:37,020
är vad som skulle vara c fäste 0 och
sedan något ned till höger

194
00:08:37,020 --> 00:08:38,220
är c bygel 11.

195
00:08:38,220 --> 00:08:41,240
Så med andra ord, kan du tänka dig
att det finns ett rutnät av byte

196
00:08:41,240 --> 00:08:44,380
Det första av dessa är
övre vänstra, botten som

197
00:08:44,380 --> 00:08:48,360
är det sista av dessa 12 byte.

198
00:08:48,360 --> 00:08:49,930
>> Men nu försöker spola framåt.

199
00:08:49,930 --> 00:08:55,580
Vad håller på att hända om vi passerar
i en sträng bar som är längre än c?

200
00:08:55,580 --> 00:08:59,130
Och vi ska inte kontrollera om
det är faktiskt mer än 12.

201
00:08:59,130 --> 00:09:03,146
Vilken del av den här bilden kommer att
blir över av byte 0, 1, 2, 3,

202
00:09:03,146 --> 00:09:07,890
dot dot dot, 11, och sedan
dåligt, 12, 13 till 19?

203
00:09:07,890 --> 00:09:11,820
Vad kommer att hända här,
om du dra slutsatsen beställning

204
00:09:11,820 --> 00:09:14,790
att c fäste 0 är på toppen
och c bygel 11 är typ av nedåt

205
00:09:14,790 --> 00:09:15,812
till höger?

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

207
00:09:16,796 --> 00:09:19,260
>> PUBLIK: Tja, det kommer
att skriva över char * bar.

208
00:09:19,260 --> 00:09:22,260
>> DAVID J. MALAN: Ja, det ser ut som
du kommer att skriva över char * bar.

209
00:09:22,260 --> 00:09:26,245
Och ännu värre, om du skickar in en riktigt lång
sträng, kan du även skriva vad?

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

211
00:09:27,460 --> 00:09:28,570
Avsändaradressen.

212
00:09:28,570 --> 00:09:31,380
Som återigen, är precis som ett
breadcrumb att tala om för programmet där

213
00:09:31,380 --> 00:09:34,060
att gå tillbaka till när f
sker kallas.

214
00:09:34,060 --> 00:09:37,140
>> Så vad skurkarna vanligtvis gör
är om de stöter på ett program

215
00:09:37,140 --> 00:09:41,290
att de är nyfikna om är
utnyttjas, buggy på ett sådant sätt

216
00:09:41,290 --> 00:09:43,550
att han eller hon kan ta
Fördelen med denna bugg,

217
00:09:43,550 --> 00:09:45,720
allmänhet de inte får
denna rätt första gången.

218
00:09:45,720 --> 00:09:48,590
De börjar att skicka, till exempel,
slumpmässiga strängar i ditt program,

219
00:09:48,590 --> 00:09:50,260
vare sig på tangentbordet,
eller ärligt talat de förmodligen

220
00:09:50,260 --> 00:09:52,740
skriva ett litet program för att bara
automatiskt generera strängar,

221
00:09:52,740 --> 00:09:55,430
och börja banka på ditt program genom
skicka in massor av olika ingångar

222
00:09:55,430 --> 00:09:56,340
vid olika längder.

223
00:09:56,340 --> 00:09:58,990
>> Så fort dina program kraschar,
det är en fantastisk sak.

224
00:09:58,990 --> 00:10:01,020
Eftersom det innebär att han
eller hon har upptäckt

225
00:10:01,020 --> 00:10:02,660
vad som troligen är verkligen en bugg.

226
00:10:02,660 --> 00:10:05,830
Och då kan de få mer smart
och börjar fokusera snävare

227
00:10:05,830 --> 00:10:07,420
om hur man kan utnyttja denna bugg.

228
00:10:07,420 --> 00:10:11,480
Framför allt vad han eller hon kanske
göra är att skicka, i bästa fall, hej.

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

230
00:10:12,210 --> 00:10:14,750
Det är en sträng som är tillräckligt kort.

231
00:10:14,750 --> 00:10:18,100
Men tänk om han eller hon skickar,
och vi ska generalisera det som,

232
00:10:18,100 --> 00:10:20,890
attack code-- så nollor
och de som gör saker

233
00:10:20,890 --> 00:10:25,150
som rm-rf, som tar bort allt
från hårddisken eller skicka skräppost

234
00:10:25,150 --> 00:10:27,000
eller på något sätt angripa maskinen?

235
00:10:27,000 --> 00:10:29,570
>> Så om var och en av dessa
bokstäverna A bara representerar,

236
00:10:29,570 --> 00:10:32,380
konceptuellt, attack, attack,
attack, attack, några dåliga kod

237
00:10:32,380 --> 00:10:36,410
att någon annan skrev, men
om personen är smart nog

238
00:10:36,410 --> 00:10:40,790
att inte bara omfatta alla
av dessa rm-RFS, men också

239
00:10:40,790 --> 00:10:46,100
få sina sista byte
vara ett nummer som motsvarar

240
00:10:46,100 --> 00:10:50,540
till adressen för sin
eller hennes egen attack-kod

241
00:10:50,540 --> 00:10:53,820
att han eller hon gick på bara
genom att förse den vid prompten

242
00:10:53,820 --> 00:10:58,760
du effektivt kan lura datorn
in märker när f görs verkställande,

243
00:10:58,760 --> 00:11:02,400
åh, det är dags för mig att hoppa
tillbaka till den röda returadress.

244
00:11:02,400 --> 00:11:06,070
Men för att han eller hon har på något sätt
lappade som returadress

245
00:11:06,070 --> 00:11:09,602
med sitt eget nummer,
och de är tillräckligt smarta

246
00:11:09,602 --> 00:11:11,560
ha konfigurerat att
nummer att hänvisa, som ni

247
00:11:11,560 --> 00:11:13,740
se i super toppen
vänstra hörnet där,

248
00:11:13,740 --> 00:11:18,020
den faktiska adressen i datorns
minnet av en del av sin attack-kod,

249
00:11:18,020 --> 00:11:21,740
en dålig kille kan lura datorn
till verkställande sin egen kod.

250
00:11:21,740 --> 00:11:23,700
>> Och den koden, återigen, kan vara vad som helst.

251
00:11:23,700 --> 00:11:26,120
Det är allmänt kallas
shell-kod, vilket är precis

252
00:11:26,120 --> 00:11:29,030
ett sätt att säga att det inte är
generellt något så enkelt som rm-rf.

253
00:11:29,030 --> 00:11:32,340
Det är faktiskt något som Bash,
eller en faktisk program som ger honom

254
00:11:32,340 --> 00:11:37,230
eller hennes programma för att utföra
något annat som de vill.

255
00:11:37,230 --> 00:11:40,210
Så kort sagt, allt detta
härrör från det enkla faktum

256
00:11:40,210 --> 00:11:44,490
att denna bugg inblandade inte kontrollera
gränserna för din array.

257
00:11:44,490 --> 00:11:47,250
Och eftersom det sätt
datorer fungerar är att de

258
00:11:47,250 --> 00:11:49,430
använda stapeln från
effektivt, begreppsmässigt,

259
00:11:49,430 --> 00:11:54,830
botten på upp, men då elementen
du trycker på stacken växer uppifrån och ner,

260
00:11:54,830 --> 00:11:56,624
detta är oerhört problematiskt.

261
00:11:56,624 --> 00:11:58,290
Nu finns det sätt att komma runt detta.

262
00:11:58,290 --> 00:12:00,800
Och ärligt talat, det finns språk
som man kan komma runt detta.

263
00:12:00,800 --> 00:12:03,100
Java är immun, till exempel,
till denna fråga.

264
00:12:03,100 --> 00:12:04,110
Eftersom de inte ger dig tips.

265
00:12:04,110 --> 00:12:05,943
De inte ge dig
direktminnesadresser.

266
00:12:05,943 --> 00:12:08,560
Så med denna kraft som vi har
röra någonting i minnet

267
00:12:08,560 --> 00:12:11,580
vi vill kommer visserligen stor risk.

268
00:12:11,580 --> 00:12:12,430
>> Så håll utkik.

269
00:12:12,430 --> 00:12:14,596
Om, ärligt talat, under månaderna
eller kommande år, när som helst

270
00:12:14,596 --> 00:12:17,740
du läsa om några exploatering
av ett program eller en server,

271
00:12:17,740 --> 00:12:22,370
Om du någonsin sett en antydan till något
som ett buffertspill attack,

272
00:12:22,370 --> 00:12:25,390
eller spill är en annan typ
av angrepp, i samma anda,

273
00:12:25,390 --> 00:12:28,770
mycket som inspirerar webbplatsens
namn, om du vet det,

274
00:12:28,770 --> 00:12:33,170
det är alla pratar om just
fulla storleken på vissa tecken

275
00:12:33,170 --> 00:12:36,200
array eller någon array mer generellt.

276
00:12:36,200 --> 00:12:38,822
Alla frågor, då, på det här?

277
00:12:38,822 --> 00:12:39,780
Prova inte detta hemma.

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

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

280
00:12:42,300 --> 00:12:47,270
Så malloc hittills har varit vår nya
vän i detta kan vi tilldela minne

281
00:12:47,270 --> 00:12:50,540
att vi inte nödvändigtvis vet i
avancera till att vi vill ha så att vi inte har

282
00:12:50,540 --> 00:12:52,920
till hård kod i vår
programnummer som 12.

283
00:12:52,920 --> 00:12:55,550
När användaren berättar hur mycket
uppgifter som han eller hon vill ingång,

284
00:12:55,550 --> 00:12:58,000
Vi kan malloc så mycket minne.

285
00:12:58,000 --> 00:13:01,484
>> Så malloc visar det sig, till
mån vi har använt det,

286
00:13:01,484 --> 00:13:03,900
uttryckligen förra gången, och sedan
ni har använt det

287
00:13:03,900 --> 00:13:08,160
för GetString omedvetet för
flera veckor, alla malloc minne

288
00:13:08,160 --> 00:13:09,820
kommer från den så kallade heap.

289
00:13:09,820 --> 00:13:13,852
Och det är därför getString, till exempel,
kan allokera minne dynamiskt

290
00:13:13,852 --> 00:13:16,060
utan att veta vad du är
kommer att skriva i förväg,

291
00:13:16,060 --> 00:13:21,520
hand du tillbaka en pekare till det minnet,
och att minnet är fortfarande din att behålla,

292
00:13:21,520 --> 00:13:24,080
även efter GetString avkastning.

293
00:13:24,080 --> 00:13:27,450
Eftersom minns ju att
stack hela tiden går upp och ner,

294
00:13:27,450 --> 00:13:27,950
upp och ner.

295
00:13:27,950 --> 00:13:30,230
Och så snart som det går
ner, betyder att varje minne

296
00:13:30,230 --> 00:13:33,030
denna funktion används bör
inte användas av någon annan.

297
00:13:33,030 --> 00:13:34,570
Det är sopor värden nu.

298
00:13:34,570 --> 00:13:36,120
>> Men högen är här uppe.

299
00:13:36,120 --> 00:13:39,360
Och vad är trevligt om malloc är att
när malloc allokerar minne upp här,

300
00:13:39,360 --> 00:13:42,070
det är inte påverkat, för
största delen av stapeln.

301
00:13:42,070 --> 00:13:46,000
Och så någon funktion kan komma åt
minne som har malloc'd,

302
00:13:46,000 --> 00:13:49,120
även av en funktion som getString,
även efter att den återlämnas.

303
00:13:49,120 --> 00:13:51,700
>> Nu är motsatsen till malloc gratis.

304
00:13:51,700 --> 00:13:53,900
Och faktiskt, den regel som du
måste börja anta

305
00:13:53,900 --> 00:13:58,950
finns någon, några, när du använder malloc
Du måste själv använda gratis, så småningom,

306
00:13:58,950 --> 00:14:00,280
på samma pekare.

307
00:14:00,280 --> 00:14:03,289
Hela denna tid har vi skrivit
barnvagn, barnvagn kod, av många skäl.

308
00:14:03,289 --> 00:14:05,580
Men en av vilka har varit
använder CS50 biblioteket, som

309
00:14:05,580 --> 00:14:09,010
själv är medvetet
buggy, läcker det minnet.

310
00:14:09,010 --> 00:14:11,410
Varje gång du har ringt getString
under de senaste veckorna

311
00:14:11,410 --> 00:14:13,870
vi ber drifts
systemet, Linux, för minnet.

312
00:14:13,870 --> 00:14:15,780
Och du har aldrig en gång gett tillbaka den.

313
00:14:15,780 --> 00:14:17,730
Och detta är inte, i
träna, en bra sak.

314
00:14:17,730 --> 00:14:20,330
>> Och Valgrind, en av
verktyg infördes Pset 4,

315
00:14:20,330 --> 00:14:22,900
handlar om att hjälpa dig
nu hitta buggar som.

316
00:14:22,900 --> 00:14:27,060
Men turligt nog för Pset 4 du inte behöver
att använda CS50 biblioteket eller getString.

317
00:14:27,060 --> 00:14:31,220
Så eventuella buggar relaterade till minnet är
i slutändan kommer att vara din egen.

318
00:14:31,220 --> 00:14:34,060
>> Så malloc är mer än bara
bekvämt för detta ändamål.

319
00:14:34,060 --> 00:14:37,420
Vi kan faktiskt nu lösa
fundamentalt olika problem,

320
00:14:37,420 --> 00:14:41,640
och i grunden lösa problem mer
effektivt som per vecka noll löfte.

321
00:14:41,640 --> 00:14:44,720
Hittills är den sexigaste
datastruktur som vi har haft.

322
00:14:44,720 --> 00:14:47,804
Och datastruktur menar jag bara
ett sätt att konceptualisering minne

323
00:14:47,804 --> 00:14:50,720
på ett sätt som går utöver att bara säga,
detta är en int, detta är en röding.

324
00:14:50,720 --> 00:14:52,930
Vi kan börja kluster saker tillsammans.

325
00:14:52,930 --> 00:14:54,460
>> Så en array såg ut så här.

326
00:14:54,460 --> 00:14:57,270
Och vad som var nyckeln i ungefär en
array är att det ger dig

327
00:14:57,270 --> 00:14:59,724
back-to-back bitar av
minne, som var och en

328
00:14:59,724 --> 00:15:02,765
kommer att vara av samma typ, int
int, int, int eller char, röding, röding,

329
00:15:02,765 --> 00:15:03,330
röding.

330
00:15:03,330 --> 00:15:04,496
Men det finns några nackdelar.

331
00:15:04,496 --> 00:15:06,570
Detta är till exempel
en matris med storleken sex.

332
00:15:06,570 --> 00:15:10,650
Anta att du fyller denna matris med sex
siffror och då, oavsett skäl,

333
00:15:10,650 --> 00:15:13,187
användar vill ge
du en sjunde nummer.

334
00:15:13,187 --> 00:15:14,020
Var placerar du den?

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

336
00:15:15,490 --> 00:15:18,990
>> Vad är lösningen om du har
skapas en array på stacken,

337
00:15:18,990 --> 00:15:22,030
till exempel, bara med den vecka
två notation som vi presenterade,

338
00:15:22,030 --> 00:15:23,730
av hakparenteser med ett nummer på insidan?

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

340
00:15:25,160 --> 00:15:27,260
Tja, du har sex
siffror i dessa rutor.

341
00:15:27,260 --> 00:15:28,530
Vad skulle dina instinkter vara?

342
00:15:28,530 --> 00:15:29,973
Var skulle du vilja sätta den?

343
00:15:29,973 --> 00:15:30,860
>> PUBLIK: [ohörbart]

344
00:15:30,860 --> 00:15:31,315
>> DAVID J. MALAN: Förlåt?

345
00:15:31,315 --> 00:15:32,380
>> PUBLIK: Sätt den på slutet.

346
00:15:32,380 --> 00:15:33,796
>> DAVID J. MALAN: Sätt den på slutet.

347
00:15:33,796 --> 00:15:35,880
Så bara över till höger,
utanför denna box.

348
00:15:35,880 --> 00:15:38,710
Vilket skulle vara trevligt, men det
visar sig att du kan inte göra det.

349
00:15:38,710 --> 00:15:41,350
För om du inte har bett
för denna bit av minne,

350
00:15:41,350 --> 00:15:44,490
det kan vara en slump att detta
används av någon annan variabel

351
00:15:44,490 --> 00:15:45,030
helt och hållet.

352
00:15:45,030 --> 00:15:49,210
Tänk tillbaka en vecka eller så när vi lade
ut Zamyla och Davin och Gabe namnger

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

354
00:15:49,930 --> 00:15:51,638
De var bokstavligen
rygg mot rygg mot rygg.

355
00:15:51,638 --> 00:15:53,550
Så vi kan inte nödvändigtvis
lita på att det som finns

356
00:15:53,550 --> 00:15:55,800
här borta är tillgänglig för mig att använda.

357
00:15:55,800 --> 00:15:56,990
>> Så vad mer kan du göra?

358
00:15:56,990 --> 00:16:00,282
Jo, en gång inse att du
behöver en matris av storlek sju,

359
00:16:00,282 --> 00:16:02,490
du kan bara skapa en
matris med storlek sju använd sedan

360
00:16:02,490 --> 00:16:05,950
en for-loop eller en while-slinga,
kopiera den till den nya arrayen,

361
00:16:05,950 --> 00:16:09,680
och sedan på något sätt bara bli av
denna array eller bara sluta använda den.

362
00:16:09,680 --> 00:16:12,130
Men det är inte särskilt effektivt.

363
00:16:12,130 --> 00:16:15,340
Kort sagt, arrayer inte låta
du dynamiskt ändra storlek.

364
00:16:15,340 --> 00:16:17,900
>> Så å ena sidan får du
random access, vilket är fantastiskt.

365
00:16:17,900 --> 00:16:20,108
Eftersom det låter oss göra saker
som söndra och härska,

366
00:16:20,108 --> 00:16:23,100
binär sökning, vilka samtliga vi har
pratade om på skärmen här.

367
00:16:23,100 --> 00:16:24,950
Men du målar själv i ett hörn.

368
00:16:24,950 --> 00:16:27,810
Så fort du träffar
i slutet av din samling,

369
00:16:27,810 --> 00:16:29,980
du måste göra en mycket
dyr operation

370
00:16:29,980 --> 00:16:33,910
eller skriva en massa kod
att nu ta itu med det problemet.

371
00:16:33,910 --> 00:16:36,680
>> Så vad händer om vi istället hade
något som kallas en lista,

372
00:16:36,680 --> 00:16:38,820
eller en lista länkad i synnerhet?

373
00:16:38,820 --> 00:16:41,930
Tänk om istället för att ha
rektanglar rygg mot rygg mot rygg,

374
00:16:41,930 --> 00:16:45,730
vi har rektanglar som lämnar lite
lite svängrum mellan dem?

375
00:16:45,730 --> 00:16:49,670
Och även om jag har dragit det här
bild eller anpassat den här bilden

376
00:16:49,670 --> 00:16:54,696
från en av de texter som här för att vara tillbaka till
rygg mot rygg mycket välordnat, i verkligheten,

377
00:16:54,696 --> 00:16:56,820
en av dessa rektanglar
kunde vara här uppe i minnet.

378
00:16:56,820 --> 00:16:58,028
En av dem kan vara här uppe.

379
00:16:58,028 --> 00:17:00,420
En av dem kan vara här uppe,
hit, och så vidare.

380
00:17:00,420 --> 00:17:02,910
>> Men tänk om vi drog,
i det här fallet, pilar

381
00:17:02,910 --> 00:17:05,650
som på något sätt koppla dessa
rektanglar tillsammans?

382
00:17:05,650 --> 00:17:08,170
I själva verket har vi sett en teknisk
inkarnation av en pil.

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

384
00:17:09,839 --> 00:17:13,710
Vad har vi använt under de senaste
dagar som, under huven,

385
00:17:13,710 --> 00:17:15,210
är representativ för en pil?

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

387
00:17:16,290 --> 00:17:17,349
En pekare, eller hur?

388
00:17:17,349 --> 00:17:19,780
>> Så vad händer om, i stället för
bara lagra numren,

389
00:17:19,780 --> 00:17:23,130
som 9, 17, 22, 26, 34,
tänk om vi lagras inte

390
00:17:23,130 --> 00:17:27,079
bara ett nummer utan en pekare
bredvid varje sådant nummer?

391
00:17:27,079 --> 00:17:30,690
Så att mycket som du skulle trä en
nål igenom en hel massa tyg,

392
00:17:30,690 --> 00:17:32,950
på något sätt knyta saker
tillsammans, på liknande sätt kan

393
00:17:32,950 --> 00:17:35,550
vi med pekare, som
förkroppsligad genom pilar här,

394
00:17:35,550 --> 00:17:38,550
slags väva samman
dessa enskilda rektanglar

395
00:17:38,550 --> 00:17:41,780
genom att effektivt att använda en pekare
bredvid varje nummer som

396
00:17:41,780 --> 00:17:46,065
pekar på något nästa nummer, som
pekar på, i sin tur, en del nästa nummer?

397
00:17:46,065 --> 00:17:47,940
Så med andra ord, vad
om vi verkligen ville

398
00:17:47,940 --> 00:17:49,820
att genomföra något sådant här?

399
00:17:49,820 --> 00:17:53,610
Väl tyvärr dessa rektanglar,
åtminstone en med 9, 17, 22,

400
00:17:53,610 --> 00:17:57,040
och så vidare, dessa är inte längre
trevliga torg med enstaka nummer.

401
00:17:57,040 --> 00:17:59,960
Botten, rektangel
Nedan 9, till exempel,

402
00:17:59,960 --> 00:18:04,330
representerar vad ska
vara en pekare, 32 bitar.

403
00:18:04,330 --> 00:18:09,460
Nu är jag ännu inte till någon datatyp
i C som inte bara ger dig en int

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

405
00:18:11,630 --> 00:18:15,020
>> Så vad är lösningen om vi vill
att uppfinna våra egna svar på detta?

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

407
00:18:15,760 --> 00:18:16,640
>> PUBLIK: [ohörbart]

408
00:18:16,640 --> 00:18:17,360
>> DAVID J. MALAN: Vad är det?

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

410
00:18:17,880 --> 00:18:19,590
>> DAVID J. MALAN: Ja, så varför
inte vi skapar en ny struktur,

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

412
00:18:20,920 --> 00:18:25,990
Vi har sett structs tidigare, om en kort stund,
där vi behandlat en elev struktur

413
00:18:25,990 --> 00:18:27,780
som denna, som hade ett namn och ett hus.

414
00:18:27,780 --> 00:18:31,980
I Pset 3 breakout du använde en hel
gäng structs-- GRect och GOvals

415
00:18:31,980 --> 00:18:34,810
att Stanford skapats för att
kluster informationen håller.

416
00:18:34,810 --> 00:18:38,580
Så vad händer om vi tar samma uppfattning om
sökorden "typedef" och "struct",

417
00:18:38,580 --> 00:18:42,890
och lite studentspecifika grejer,
och utvecklas här i följande:

418
00:18:42,890 --> 00:18:46,210
typedef struct node-- och nod är
bara en mycket generisk datavetenskap

419
00:18:46,210 --> 00:18:49,980
term för något i en datastruktur,
en behållare i en datastruktur.

420
00:18:49,980 --> 00:18:53,900
En nod Jag hävdar kommer att ha
en int n, helt enkelt,

421
00:18:53,900 --> 00:18:58,810
och sedan lite mer kryptiskt,
denna andra raden, struct nod * nästa.

422
00:18:58,810 --> 00:19:01,300
Men i mindre tekniska termer,
vad är det andra raden

423
00:19:01,300 --> 00:19:02,980
för kod inuti klammerparentes?

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

425
00:19:03,737 --> 00:19:04,851
>> PUBLIK: [ohörbart]

426
00:19:04,851 --> 00:19:06,600
David J. MALAN: A
pekare till en annan nod.

427
00:19:06,600 --> 00:19:09,910
Så visserligen, syntax lite kryptiskt.

428
00:19:09,910 --> 00:19:13,250
Men om du läser det bokstavligen,
nästa är namnet på en variabel.

429
00:19:13,250 --> 00:19:14,410
Vad är dess datatyp?

430
00:19:14,410 --> 00:19:18,206
Det är lite mångordig den här gången,
men det är av typen struct nod *.

431
00:19:18,206 --> 00:19:22,960
Varje gång vi har sett något star, att
betyder att det är en pekare till den datatypen.

432
00:19:22,960 --> 00:19:26,810
Så nästa är uppenbarligen en
pekare till en struct nod.

433
00:19:26,810 --> 00:19:28,310
>> Nu, vad är en struct nod?

434
00:19:28,310 --> 00:19:31,044
Tja, märker du dem
Samma ord på upp till höger.

435
00:19:31,044 --> 00:19:33,960
Och faktiskt, ser du även ordet
"Nod" här nere längst ner till vänster.

436
00:19:33,960 --> 00:19:35,640
Och det är faktiskt bara en bekvämlighet.

437
00:19:35,640 --> 00:19:39,930
Notera att i vår definition elev
det är ordet "student" bara en gång.

438
00:19:39,930 --> 00:19:42,510
Och det beror på att en student
Objektet var inte självrefererande.

439
00:19:42,510 --> 00:19:45,340
Det finns inget inuti en student
som måste peka på en annan student,

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

441
00:19:45,610 --> 00:19:47,630
Det skulle vara slags
konstig i den verkliga världen.

442
00:19:47,630 --> 00:19:50,880
>> Men med en nod i en länkad
lista, vill vi ha en nod

443
00:19:50,880 --> 00:19:53,970
vara refererande till liknande syfte.

444
00:19:53,970 --> 00:19:57,900
Och så märker förändringen här är inte
precis vad som finns inuti klammerparentes.

445
00:19:57,900 --> 00:20:00,800
Men vi lägga till ordet "nod"
upptill samt

446
00:20:00,800 --> 00:20:02,930
lägga till det till botten
i stället för "student".

447
00:20:02,930 --> 00:20:06,000
Och detta är bara en teknisk detalj
så att, återigen, din datastruktur

448
00:20:06,000 --> 00:20:11,380
kan vara självrefererande, så att en
nod kan peka på en annan sådan nod.

449
00:20:11,380 --> 00:20:13,840
>> Så vad är det i slutändan
kommer att innebära för oss?

450
00:20:13,840 --> 00:20:17,560
Jo, en, det här inne
är innehållet i vår nod.

451
00:20:17,560 --> 00:20:19,360
Denna sak här uppe,
upp till höger, är bara så

452
00:20:19,360 --> 00:20:20,860
att, återigen, kan vi hänvisa till oss själva.

453
00:20:20,860 --> 00:20:23,401
Och sedan den yttersta grejer,
även om noden är en ny term,

454
00:20:23,401 --> 00:20:25,500
kanske, det är fortfarande det
samma som student och vad

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

456
00:20:27,520 --> 00:20:31,095
>> Så om vi nu ville börja
genomförande av denna länkade lista,

457
00:20:31,095 --> 00:20:33,220
Hur kan vi översätter
ungefär så här för att koda?

458
00:20:33,220 --> 00:20:35,350
Nåväl, låt oss bara ser en
exempel på ett program som

459
00:20:35,350 --> 00:20:36,840
faktiskt använder en länkad lista.

460
00:20:36,840 --> 00:20:40,870
Bland dagens distributions kod
är ett program som heter lista Zero.

461
00:20:40,870 --> 00:20:44,980
Och om jag kör detta skapade jag en super
enkelt GUI, grafiskt användargränssnitt,

462
00:20:44,980 --> 00:20:46,460
men det är egentligen bara printf.

463
00:20:46,460 --> 00:20:50,930
Och nu har jag gett mig själv ett par meny
options-- Delete, Insert, Search,

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

465
00:20:51,750 --> 00:20:52,630
Och Quit.

466
00:20:52,630 --> 00:20:55,970
Dessa är bara vanliga operationer på ett
datastruktur som kallas en länklista.

467
00:20:55,970 --> 00:20:58,409
>> Nu Radera ska
ta bort ett nummer från listan.

468
00:20:58,409 --> 00:21:00,200
Insert kommer att lägga
ett nummer i listan.

469
00:21:00,200 --> 00:21:02,181
Sök kommer att se
för nummer i listan.

470
00:21:02,181 --> 00:21:04,930
Och travers är bara ett finare sätt
att säga, gå igenom listan,

471
00:21:04,930 --> 00:21:06,245
skriva ut den, men det är det.

472
00:21:06,245 --> 00:21:07,720
Ändra inte denna på något sätt.

473
00:21:07,720 --> 00:21:08,570
>> Så låt oss prova det här.

474
00:21:08,570 --> 00:21:10,160
Låt oss gå vidare och typ 2.

475
00:21:10,160 --> 00:21:12,710
Och sedan ska jag
in nummer, säger 9.

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

477
00:21:13,620 --> 00:21:17,480
Och nu mitt program är bara
programmerad att säga, är listan nu 9.

478
00:21:17,480 --> 00:21:20,190
Nu, om jag går vidare och
inte in igen, låt

479
00:21:20,190 --> 00:21:23,680
mig gå vidare och zooma ut och skriv in 17.

480
00:21:23,680 --> 00:21:25,770
Nu är min lista är 9, därefter 17.

481
00:21:25,770 --> 00:21:27,750
Om jag sätter i gång, låt oss hoppa över en.

482
00:21:27,750 --> 00:21:32,400
I stället för 22, enligt bilden vi har
varit att titta på här, låt mig hoppa framåt

483
00:21:32,400 --> 00:21:34,630
och sätt 26 nästa.

484
00:21:34,630 --> 00:21:36,230
Så jag kommer att skriva 26.

485
00:21:36,230 --> 00:21:37,755
Listan är som jag förväntar mig.

486
00:21:37,755 --> 00:21:40,630
Men nu, bara för att se om den här koden
kommer att vara flexibla, låt mig nu

487
00:21:40,630 --> 00:21:43,520
typ 22, som åtminstone
begreppsmässigt, om vi

488
00:21:43,520 --> 00:21:46,520
hålla denna sorteras, som visserligen är
kommer att bli ytterligare ett mål just nu,

489
00:21:46,520 --> 00:21:48,690
ska gå in mellan 17 och 26.

490
00:21:48,690 --> 00:21:50,270
Så jag slog Enter.

491
00:21:50,270 --> 00:21:51,380
I själva verket fungerar det.

492
00:21:51,380 --> 00:21:54,950
Och så nu vill jag sätta in
sist, enligt bilden, 34.

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

494
00:21:55,450 --> 00:21:58,980
Så nu vill jag föreskriva att
Radera och Traverse och sökning gör,

495
00:21:58,980 --> 00:21:59,760
i själva verket fungerar.

496
00:21:59,760 --> 00:22:04,180
Faktum är att om jag kör sökning, låt oss
söka efter numret 22, Enter.

497
00:22:04,180 --> 00:22:05,010
Den hittade 22.

498
00:22:05,010 --> 00:22:07,580
Så det är vad detta
Programmet Lista Zero gör.

499
00:22:07,580 --> 00:22:10,230
>> Men vad som verkligen händer
den som implementerar detta?

500
00:22:10,230 --> 00:22:14,530
Tja, först jag kan ha, och faktiskt
Jag har en fil som heter list0.h.

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

502
00:22:16,540 --> 00:22:20,690
Och någonstans i det här
linje, typedef, struct nod,

503
00:22:20,690 --> 00:22:24,850
då jag har mina klammerparenteser, int n, och
sedan struct-- vad var definitionen?

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

505
00:22:26,530 --> 00:22:28,545
Struct nod nästa.

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

507
00:22:29,920 --> 00:22:31,045
Så vi behöver stjärnan.

508
00:22:31,045 --> 00:22:33,420
Nu tekniskt vi får in
för vana att dra upp den här.

509
00:22:33,420 --> 00:22:35,670
Du kan se läroböcker och
online-referenser gör det där.

510
00:22:35,670 --> 00:22:36,660
Det är funktionellt likvärdig.

511
00:22:36,660 --> 00:22:37,980
I själva verket är detta en lite mer typiska.

512
00:22:37,980 --> 00:22:40,563
Men jag ska vara i linje med vad
vi gjorde förra gången och gör detta.

513
00:22:40,563 --> 00:22:42,350
Och slutligen, jag ska göra det här.

514
00:22:42,350 --> 00:22:45,550
>> Så i en header-fil
någonstans i list0.h

515
00:22:45,550 --> 00:22:49,200
idag är denna struct definition,
och kanske lite annat.

516
00:22:49,200 --> 00:22:52,580
Under tiden i list0c finns
kommer att bli ett par saker.

517
00:22:52,580 --> 00:22:54,740
Men vi ska bara
start och inte avsluta detta.

518
00:22:54,740 --> 00:22:59,690
List0.h är en fil jag vill ha
att i min C-fil.

519
00:22:59,690 --> 00:23:03,910
Och sedan någon gång jag är
kommer att ha int, main, ogiltig.

520
00:23:03,910 --> 00:23:06,530
Och sedan ska jag
har en del att göra det här.

521
00:23:06,530 --> 00:23:10,620
Jag kommer även att ha en
prototyp, som ogiltig, sök, int,

522
00:23:10,620 --> 00:23:13,610
n är vars syfte i livet
att söka efter ett element.

523
00:23:13,610 --> 00:23:18,310
Och sedan ner här jag hävdar i
dagens kod, tomrum, sök, int, n,

524
00:23:18,310 --> 00:23:21,020
inget semikolon men öppna klammerparenteser.

525
00:23:21,020 --> 00:23:25,049
Och nu vill jag på något sätt söka
för ett element i den här listan.

526
00:23:25,049 --> 00:23:27,340
Men vi har inte tillräckligt
information på skärmen ännu.

527
00:23:27,340 --> 00:23:29,800
Jag har faktiskt inte
representerade själva listan.

528
00:23:29,800 --> 00:23:33,070
Så ett sätt som vi skulle kunna genomföra
en länkad lista i ett program

529
00:23:33,070 --> 00:23:37,520
är jag liksom vill göra något
som förklarar länkad lista här uppe.

530
00:23:37,520 --> 00:23:40,520
För enkelhetens skull kommer jag att göra
denna globala, även om vi i allmänhet

531
00:23:40,520 --> 00:23:41,645
borde inte göra det för mycket.

532
00:23:41,645 --> 00:23:43,260
Men det kommer att förenkla detta exempel.

533
00:23:43,260 --> 00:23:45,890
Så jag vill förklara
en länkad lista här.

534
00:23:45,890 --> 00:23:47,010
Nu, hur kan jag göra det?

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

536
00:23:48,810 --> 00:23:50,750
>> Här är bilden av en länkad lista.

537
00:23:50,750 --> 00:23:53,030
Och jag vet inte riktigt
vet just nu hur

538
00:23:53,030 --> 00:23:56,710
Jag ska gå om företräder
så många saker med bara en

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

540
00:23:58,040 --> 00:23:59,160
Men tänker tillbaka en stund.

541
00:23:59,160 --> 00:24:00,830
Hela denna tid har vi haft
strängar, som vi sedan

542
00:24:00,830 --> 00:24:02,913
visade sig vara arrayer av
tecken, som vi sedan

543
00:24:02,913 --> 00:24:05,740
visade att bara vara en pekare
till det första tecknet

544
00:24:05,740 --> 00:24:08,890
i en matris av tecken
som är null avslutas.

545
00:24:08,890 --> 00:24:13,530
Så genom denna logik, och med detta
bild slags seedning dina tankar,

546
00:24:13,530 --> 00:24:17,964
Vad behöver vi faktiskt skriver i vår
kod för att representera en länkad lista?

547
00:24:17,964 --> 00:24:21,130
Hur mycket av denna information behöver vi
att fånga i C-kod, skulle du säga?

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

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

550
00:24:23,154 --> 00:24:24,738
>> Publik: Vi behöver en pekare till en nod.

551
00:24:24,738 --> 00:24:26,237
David J. MALAN: En pekare till en nod.

552
00:24:26,237 --> 00:24:29,320
Särskilt som nod skulle ditt
instinkter vara att hålla en pekare till?

553
00:24:29,320 --> 00:24:30,026
>> Publik: Den första noden.

554
00:24:30,026 --> 00:24:31,942
>> DAVID J. MALAN: Ja,
förmodligen bara den första.

555
00:24:31,942 --> 00:24:34,030
Och märker, den första
noden är en annan form.

556
00:24:34,030 --> 00:24:37,690
Det är bara hälften så stor som den struct,
eftersom det är faktiskt bara en pekare.

557
00:24:37,690 --> 00:24:44,650
Så vad du faktiskt kan göra är att deklarera
en länkad lista att vara av typ nod *.

558
00:24:44,650 --> 00:24:47,780
Och låt oss bara kalla det först
och initiera den till null.

559
00:24:47,780 --> 00:24:49,910
Så null, återigen, är att komma
in i bilden här.

560
00:24:49,910 --> 00:24:53,620
Inte bara är null som som en speciell
returvärde för saker som getString

561
00:24:53,620 --> 00:24:57,770
och malloc är null också noll
pekare, avsaknaden av en pekare,

562
00:24:57,770 --> 00:24:58,430
om du kommer.

563
00:24:58,430 --> 00:25:00,309
Det betyder bara ingenting är ännu här.

564
00:25:00,309 --> 00:25:02,100
Nu först, kunde jag har
kallade detta ingenting.

565
00:25:02,100 --> 00:25:04,200
Jag kunde ha kallat det "lista"
eller valfritt antal andra saker.

566
00:25:04,200 --> 00:25:06,960
Men jag kallar det "första" så att
den är i linje med den här bilden.

567
00:25:06,960 --> 00:25:10,280
Så precis som en sträng kan representeras
med adressen till sin första byte,

568
00:25:10,280 --> 00:25:11,280
så kan en länkad lista.

569
00:25:11,280 --> 00:25:13,480
Och vi får se andra data
strukturer vara representerade

570
00:25:13,480 --> 00:25:16,700
med bara en pekare,
en 32-bitars pil, som pekar

571
00:25:16,700 --> 00:25:18,740
på den allra första nod i strukturen.

572
00:25:18,740 --> 00:25:20,340
>> Men nu ska vi räknar med ett problem.

573
00:25:20,340 --> 00:25:23,230
Om jag bara minnas
i mitt program adressen

574
00:25:23,230 --> 00:25:27,220
av den första noden, den första
rektangel i denna datastruktur,

575
00:25:27,220 --> 00:25:31,760
vad hade bättre vara fallet om
Genomförandet av resten av min lista?

576
00:25:31,760 --> 00:25:35,820
Vad är en viktig detalj som händer
att se till att detta verkligen fungerar?

577
00:25:35,820 --> 00:25:39,250
Och med "faktiskt fungerar" Jag
menar, ungefär som en sträng,

578
00:25:39,250 --> 00:25:42,180
låter oss gå från det första tecknet
i Davin namn till den andra,

579
00:25:42,180 --> 00:25:44,755
till den tredje, till
fjärde, till slutet,

580
00:25:44,755 --> 00:25:47,880
Hur vet vi när vi är i slutet
av en länkad lista som ser ut så här?

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

582
00:25:50,035 --> 00:25:50,660
När det är null.

583
00:25:50,660 --> 00:25:53,640
Och jag har företrätt denna typ av som
som elingenjör makt,

584
00:25:53,640 --> 00:25:56,420
med den lilla jord
symbol, av slag.

585
00:25:56,420 --> 00:25:58,246
Men det betyder bara null i detta fall.

586
00:25:58,246 --> 00:26:00,370
Du kan rita det valfritt antal
olika sätt, men denna författare

587
00:26:00,370 --> 00:26:02,800
råkade använda denna symbol här.

588
00:26:02,800 --> 00:26:06,260
>> Så länge vi stringing
alla dessa noder tillsammans,

589
00:26:06,260 --> 00:26:08,600
bara komma ihåg var
den första är, så länge

590
00:26:08,600 --> 00:26:11,760
som vi sätter en speciell symbol på
den allra sista noden i listan,

591
00:26:11,760 --> 00:26:15,130
och vi kommer att använda null, eftersom det är
det vi har till vårt förfogande,

592
00:26:15,130 --> 00:26:16,480
listan är klar.

593
00:26:16,480 --> 00:26:20,190
Och även om jag bara ge dig en pekare till
det första elementet, dig, programmerare,

594
00:26:20,190 --> 00:26:22,486
kan säkert komma åt resten av den.

595
00:26:22,486 --> 00:26:24,360
Men låt oss låt dina sinnen
vandra lite,

596
00:26:24,360 --> 00:26:26,140
om de inte redan är
ganska wandered-- vad

597
00:26:26,140 --> 00:26:28,723
kommer att bli speltid för
hitta något i den här listan?

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

599
00:26:30,450 --> 00:26:33,470
Fan, det är stort O i n,
vilket inte är dåligt, i rättvisans namn.

600
00:26:33,470 --> 00:26:34,800
Men det är linjär.

601
00:26:34,800 --> 00:26:37,980
Vi har gett upp vilken funktion
av matriser genom att flytta mer

602
00:26:37,980 --> 00:26:43,130
mot denna bild av dynamiskt
vävs samman eller länkade noder?

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

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

605
00:26:46,687 --> 00:26:48,770
En array är trevligt eftersom
matematiskt allt

606
00:26:48,770 --> 00:26:50,340
är rygg mot rygg mot rygg mot rygg.

607
00:26:50,340 --> 00:26:52,370
Även om den här bilden
ser ganska, och till och med

608
00:26:52,370 --> 00:26:55,830
även om det ser ut som dessa noder
är snyggt åtskilda, i verkligheten

609
00:26:55,830 --> 00:26:56,830
de skulle kunna vara var som helst.

610
00:26:56,830 --> 00:27:01,590
OX1, Ox50, Ox123, Ox99, dessa
noder kan vara var som helst.

611
00:27:01,590 --> 00:27:05,960
Eftersom malloc gör tilldela minne
från högen, men någonstans i högen.

612
00:27:05,960 --> 00:27:09,080
Du behöver inte nödvändigtvis vet att det är
kommer att vara tillbaka till tillbaka till igen.

613
00:27:09,080 --> 00:27:12,460
Och så den här bilden i verkligheten är
kommer inte att vara helt denna vackra.

614
00:27:12,460 --> 00:27:16,140
>> Så det kommer att ta en bit av
arbeta för att genomföra den här funktionen.

615
00:27:16,140 --> 00:27:17,880
Så låt oss genomföra sökningen nu.

616
00:27:17,880 --> 00:27:20,250
Och vi får se lite av en
smart sätt att göra detta.

617
00:27:20,250 --> 00:27:24,660
Så om jag är en sökfunktion och
Jag får en variabel, integer n

618
00:27:24,660 --> 00:27:28,490
att leta efter, jag behöver veta
ny syntax för att titta inuti

619
00:27:28,490 --> 00:27:32,400
en struktur som är
pekade på, att hitta n.

620
00:27:32,400 --> 00:27:33,210
Så låt oss göra det här.

621
00:27:33,210 --> 00:27:36,030
>> Så först ska jag gå
framåt och förklara en nod *.

622
00:27:36,030 --> 00:27:39,400
Och jag ska kalla det
pekare, bara genom konventionen.

623
00:27:39,400 --> 00:27:41,710
Och jag kommer att initiera den till först.

624
00:27:41,710 --> 00:27:43,770
Och nu kan jag göra det här
på ett antal olika sätt.

625
00:27:43,770 --> 00:27:45,436
Men jag ska ta ett gemensamt synsätt.

626
00:27:45,436 --> 00:27:50,180
Även pekare är inte lika med
null, och det är giltigt syntax.

627
00:27:50,180 --> 00:27:54,550
Och det betyder bara göra följande, så
länge du inte pekar på någonting.

628
00:27:54,550 --> 00:27:55,800
Vad vill jag göra?

629
00:27:55,800 --> 00:28:01,939
>> Om pekaren dot n, låt mig komma tillbaka
till det, lika equals-- vad?

630
00:28:01,939 --> 00:28:03,105
Vilket värde letar jag efter?

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

632
00:28:04,920 --> 00:28:06,590
Själva n som skickades in.

633
00:28:06,590 --> 00:28:09,020
Så här är en annan funktion
C och många språk.

634
00:28:09,020 --> 00:28:13,705
Även om den struktur som kallas nod
har ett värde n, helt legitimt

635
00:28:13,705 --> 00:28:17,530
att också ha en lokal argument
eller variabel som heter n.

636
00:28:17,530 --> 00:28:20,085
Eftersom även vi, med
mänskliga ögat kan urskilja

637
00:28:20,085 --> 00:28:22,087
att denna n är förmodligen
annorlunda än den här n.

638
00:28:22,087 --> 00:28:23,420
Eftersom syntaxen är annorlunda.

639
00:28:23,420 --> 00:28:26,211
Du har en prick och en pekare,
Denna man har något sådant.

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

641
00:28:27,290 --> 00:28:29,120
Det är OK att kalla dem samma saker.

642
00:28:29,120 --> 00:28:32,380
>> Om jag hittar du här, jag är
kommer att vilja göra något

643
00:28:32,380 --> 00:28:35,000
liksom meddela att vi hittat n.

644
00:28:35,000 --> 00:28:37,930
Och vi lämnar det som en
kommentera eller pseudokoden.

645
00:28:37,930 --> 00:28:40,190
Else, och här är
intressanta delen, vilken

646
00:28:40,190 --> 00:28:47,320
vill jag göra om den aktuella noden
inte innehåller n som jag bryr mig om?

647
00:28:47,320 --> 00:28:50,700
Hur gör jag för att uppnå följande?

648
00:28:50,700 --> 00:28:53,710
Om fingret på
nu är PTR, och det är

649
00:28:53,710 --> 00:28:55,920
pekar på vad
första pekar på,

650
00:28:55,920 --> 00:28:59,290
Hur flyttar jag mitt finger
till nästa nod i kod?

651
00:28:59,290 --> 00:29:01,915
Tja, vad är länkstigen är vi
kommer att följa i det här fallet?

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

653
00:29:03,464 --> 00:29:04,380
PUBLIK: [ohörbart].

654
00:29:04,380 --> 00:29:05,630
DAVID J. MALAN: Ja, så nästa.

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

656
00:29:06,640 --> 00:29:09,824
Så om jag går tillbaka till min
koden här, ja, jag är

657
00:29:09,824 --> 00:29:12,990
kommer att gå vidare och säga pekare, vilket
är bara en tillfällig variable-- det

658
00:29:12,990 --> 00:29:15,320
ett konstigt namn, ptr, men
det är precis som temp--

659
00:29:15,320 --> 00:29:19,234
Jag kommer att ställa pekaren
lika oavsett pekaren är--

660
00:29:19,234 --> 00:29:22,150
och igen, detta kommer att bli ett
liten buggy för en moment-- punkt bredvid.

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

662
00:29:23,551 --> 00:29:26,550
Med andra ord kommer jag att ta min
finger som är riktade mot denna nod

663
00:29:26,550 --> 00:29:31,247
här och jag kommer att säga, du vet
vad, ta en titt på nästa fält

664
00:29:31,247 --> 00:29:33,330
och flytta fingret till
vad det pekar på.

665
00:29:33,330 --> 00:29:35,163
Och detta kommer att
repetera, repetera, repetera.

666
00:29:35,163 --> 00:29:37,630
Men när gör mitt finger
sluta göra något alls?

667
00:29:37,630 --> 00:29:40,095
Så snart det kodrad sparkar i?

668
00:29:40,095 --> 00:29:40,970
PUBLIK: [ohörbart]

669
00:29:40,970 --> 00:29:43,060
DAVID J. MALAN: Om punkten samtidigt
Pekaren är inte lika med noll.

670
00:29:43,060 --> 00:29:44,900
Någon gång mitt finger s
kommer att peka på null

671
00:29:44,900 --> 00:29:47,070
och jag kommer att inse
det är slutet av denna lista.

672
00:29:47,070 --> 00:29:48,910
Nu är detta en lite
vit lögn för enkelhet.

673
00:29:48,910 --> 00:29:51,580
Det visar sig att även om vi
just lärt sig detta punktnotation

674
00:29:51,580 --> 00:29:55,220
för konstruktioner, är pekaren inte en struct.

675
00:29:55,220 --> 00:29:56,580
ptr är vad?

676
00:29:56,580 --> 00:29:58,350
Bara för att vara mer nitpicky.

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

678
00:29:59,720 --> 00:30:01,360
Det är en pekare till en nod.

679
00:30:01,360 --> 00:30:03,120
Det är inte en nod i sig.

680
00:30:03,120 --> 00:30:06,650
Om jag hade ingen stjärnan här, pekare
absolutely-- det är en nod.

681
00:30:06,650 --> 00:30:08,650
Detta är som en vecka
deklaration av en variabel,

682
00:30:08,650 --> 00:30:10,120
även om ordet "nod" är ny.

683
00:30:10,120 --> 00:30:13,860
>> Men så fort vi införa en
stjärna, det är nu en pekare till en nod.

684
00:30:13,860 --> 00:30:17,960
Och tyvärr kan du inte använda
den punktnotation av en pekare.

685
00:30:17,960 --> 00:30:21,070
Du måste använda pilen
notation, som, påfallande,

686
00:30:21,070 --> 00:30:23,470
är första gången någon pjäs
av syntax ser intuitivt.

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

688
00:30:25,245 --> 00:30:26,370
Och så det är en bra sak.

689
00:30:26,370 --> 00:30:28,995
Och här nere bokstav
ser ut som en pil.

690
00:30:28,995 --> 00:30:31,870
Så jag tror det är la-- jag inte
tror jag över begå här-- I

691
00:30:31,870 --> 00:30:34,120
tror att det är det sista nya pjäs
av syntax ska vi se.

692
00:30:34,120 --> 00:30:36,500
Och tack och lov är det faktiskt
lite mer intuitivt.

693
00:30:36,500 --> 00:30:40,090
>> Nu, för er som
kanske föredrar det gamla sättet,

694
00:30:40,090 --> 00:30:42,550
Du kan fortfarande använda punktnotation.

695
00:30:42,550 --> 00:30:45,380
Men enligt måndagens
konversation, vi först

696
00:30:45,380 --> 00:30:50,530
behöver gå dit, gå till den
adress, och sedan gå in i fältet.

697
00:30:50,530 --> 00:30:51,897
Så detta är också korrekt.

698
00:30:51,897 --> 00:30:53,730
Och ärligt talat, är detta en
lite mer pedantisk.

699
00:30:53,730 --> 00:30:56,530
Du är bokstavligen säger dereference
pekaren och gå dit.

700
00:30:56,530 --> 00:30:59,320
Sedan ta tag .n, fältet kallas n.

701
00:30:59,320 --> 00:31:01,370
Men ärligt talat, vill ingen
att skriva eller läsa här.

702
00:31:01,370 --> 00:31:03,620
Och så världen uppfann
pilen notation, vilken

703
00:31:03,620 --> 00:31:06,980
är motsvarande, identiska,
det är bara syntaktisk socker.

704
00:31:06,980 --> 00:31:10,570
Så ett finare sätt att säga detta
ser bättre ut, eller ser enklare.

705
00:31:10,570 --> 00:31:12,296
>> Så nu ska jag göra en annan sak.

706
00:31:12,296 --> 00:31:15,420
Jag kommer att säga "paus" när jag har
fann det så jag inte fortsätta leta efter den.

707
00:31:15,420 --> 00:31:17,620
Men detta är kontentan
av en sökfunktion.

708
00:31:17,620 --> 00:31:21,710
Men det är mycket lättare, i
slut, inte att gå igenom koden.

709
00:31:21,710 --> 00:31:25,570
Detta är verkligen den formella tillämpningen
för sökning i dagens distributions kod.

710
00:31:25,570 --> 00:31:30,530
Jag vågar säga att insatsen inte
särskilt kul att gå igenom

711
00:31:30,530 --> 00:31:33,180
visuellt, inte heller är radera, även
men i slutet av dagen

712
00:31:33,180 --> 00:31:35,460
de kokar ner till ganska
enkla heuristik.

713
00:31:35,460 --> 00:31:36,330
>> Så låt oss göra det här.

714
00:31:36,330 --> 00:31:39,250
Om du kommer humor mig här, jag gjorde
ta med en massa stress bollar.

715
00:31:39,250 --> 00:31:40,620
Jag tog en massa siffror.

716
00:31:40,620 --> 00:31:46,562
Och skulle vi kunna få några frivilliga
att representera 9, 17, 20, 22, 29 och 34?

717
00:31:46,562 --> 00:31:48,270
Så i huvudsak alla
vem som är här i dag.

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

719
00:31:50,170 --> 00:31:52,760
Det var en, två, tre,
fyra, fem, sex personer.

720
00:31:52,760 --> 00:31:55,740
Och jag har blivit ombedd att go-- se, nej
en i ryggen höjer sina händer.

721
00:31:55,740 --> 00:32:01,910
OK, en, två, tre, fyra,
five-- låt mig ladda balance-- sex.

722
00:32:01,910 --> 00:32:03,051
OK, du sex kom upp.

723
00:32:03,051 --> 00:32:04,050
Vi behöver andra människor.

724
00:32:04,050 --> 00:32:05,460
Vi väckte extra stress bollar.

725
00:32:05,460 --> 00:32:08,200
Och om du kunde, för
bara ett ögonblick, linje

726
00:32:08,200 --> 00:32:10,490
er upp precis
gillar den här bilden här.

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

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

729
00:32:15,959 --> 00:32:17,125
Låt oss se, vad heter du?

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

731
00:32:17,550 --> 00:32:18,800
>> DAVID J. MALAN: Andrew,
du är nummer 9.

732
00:32:18,800 --> 00:32:19,540
Trevligt att träffas.

733
00:32:19,540 --> 00:32:20,400
Varsågod.

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

735
00:32:21,593 --> 00:32:22,176
PUBLIKEN: 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
Number 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
>> PUBLIK: Jag är Julia.

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

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

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

745
00:32:28,507 --> 00:32:29,340
PUBLIKEN: Christian.

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

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

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

749
00:32:32,040 --> 00:32:32,649
>> PUBLIKEN: 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å sätt igång och 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
Har någon en markör?

760
00:32:43,682 --> 00:32:44,890
PUBLIK: Jag har en Sharpie.

761
00:32:44,890 --> 00:32:45,660
DAVID J. MALAN: Du har 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
Och är det någon som har en bit papper?

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

766
00:32:51,562 --> 00:32:52,270
Spara föreläsningen.

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

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

769
00:32:55,362 --> 00:32:56,320
PUBLIK: Vi har det.

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

771
00:32:57,600 --> 00:32:58,577
Okej, tack.

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

773
00:33:01,380 --> 00:33:02,520
Nu kör vi.

774
00:33:02,520 --> 00:33:03,582
Var detta från dig?

775
00:33:03,582 --> 00:33:04,540
Du räddade precis på 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
Okej.

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

781
00:33:13,360 --> 00:33:14,890
Jag felstavade 29, men OK.

782
00:33:14,890 --> 00:33:15,720
Varsågod.

783
00:33:15,720 --> 00:33:18,114
Okej, jag ska ge dig
pennan tillbaka tillfälligt.

784
00:33:18,114 --> 00:33:19,280
Så vi har dessa människor här.

785
00:33:19,280 --> 00:33:20,330
Låt oss ha en annan.

786
00:33:20,330 --> 00:33:23,750
Gabe, vill du spela
det första elementet här?

787
00:33:23,750 --> 00:33:25,705
Vi behöver dig för att peka
på dessa fina folks.

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

789
00:33:26,930 --> 00:33:31,030
Så 9, 17, 20, 22, sortera
29 och sedan 34.

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

791
00:33:32,160 --> 00:33:33,325
Gjorde vi förlorar någon?

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

793
00:33:33,950 --> 00:33:36,730
Där did-- OK, vem vill vara 34?

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

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

796
00:33:39,280 --> 00:33:41,220
Okej, detta kommer att vara
väl värt klimax.

797
00:33:41,220 --> 00:33:41,550
Vad heter du?

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

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

800
00:33:43,456 --> 00:33:46,810
Okej, så här är en
massa noder.

801
00:33:46,810 --> 00:33:49,060
Var och en av er representerar
en av dessa rektanglar.

802
00:33:49,060 --> 00:33:51,930
Och Gabe, det något udda
människan ut, står först.

803
00:33:51,930 --> 00:33:54,850
Så hans pekaren är lite mindre
på skärmen än alla andra.

804
00:33:54,850 --> 00:33:58,120
Och i detta fall, var och en av vänster
händer kommer att antingen peka nedåt,

805
00:33:58,120 --> 00:34:01,085
därmed representerar null, så
bara frånvaron av en pekare,

806
00:34:01,085 --> 00:34:03,210
eller det kommer att peka
vid en nod bredvid dig.

807
00:34:03,210 --> 00:34:05,440
>> Så just nu om du pryda
er som bilden

808
00:34:05,440 --> 00:34:07,585
här, gå vidare och peka
på varandra, med Gabe

809
00:34:07,585 --> 00:34:11,030
i synnerhet pekar på
nummer 9 för att representera listan.

810
00:34:11,030 --> 00:34:14,050
OK, och nummer 34, vänster hand
ska bara peka på golvet.

811
00:34:14,050 --> 00:34:15,750
>> OK, så det här är den länkade listan.

812
00:34:15,750 --> 00:34:17,580
Så detta är scenariot i fråga.

813
00:34:17,580 --> 00:34:20,210
Och faktiskt, det här är representativt
av en klass av problem

814
00:34:20,210 --> 00:34:21,929
att du kanske försöker lösa med kod.

815
00:34:21,929 --> 00:34:25,020
Du vill slutligen infoga
ett nytt element i listan.

816
00:34:25,020 --> 00:34:27,494
I det här fallet ska vi
prova att sätta numret 55.

817
00:34:27,494 --> 00:34:28,500

818
00:34:28,500 --> 00:34:30,860
Men det kommer att bli
olika fall att tänka på.

819
00:34:30,860 --> 00:34:34,409
Och faktiskt, det här kommer att bli en
av den stora bilden hämtställen här är,

820
00:34:34,409 --> 00:34:35,659
vilka är de olika fallen.

821
00:34:35,659 --> 00:34:39,120
Vilka är de olika om villkor eller
grenar som ditt program kan ha?

822
00:34:39,120 --> 00:34:42,024
>> Tja, det nummer du försöker
Insatsen, som vi vet nu att vara 55,

823
00:34:42,024 --> 00:34:44,650
men om du inte visste
i förväg, jag daresay

824
00:34:44,650 --> 00:34:47,840
faller in i åtminstone tre
situationer.

825
00:34:47,840 --> 00:34:49,717
Där kan ett nytt element vara?

826
00:34:49,717 --> 00:34:51,050
PUBLIK: Och i slutet eller mitten.

827
00:34:51,050 --> 00:34:54,150
DAVID J. MALAN: I slutet, i
mitten, eller i början.

828
00:34:54,150 --> 00:34:56,650
Så jag hävdar att det finns åtminstone
tre problem som vi måste lösa.

829
00:34:56,650 --> 00:34:58,691
Låt oss välja vad som är kanske
utan tvekan den enklaste

830
00:34:58,691 --> 00:35:01,090
en, där det nya elementet
hör i början.

831
00:35:01,090 --> 00:35:04,040
Så jag kommer att få koden helt
som söker, som jag skrev bara.

832
00:35:04,040 --> 00:35:07,670
Och jag ska ha ptr, vilket
Jag företräder här med mitt finger,

833
00:35:07,670 --> 00:35:08,370
som vanligt.

834
00:35:08,370 --> 00:35:12,430
>> Och kom ihåg, vilket värde
vi initiera ptr till?

835
00:35:12,430 --> 00:35:15,300
Så vi initieras den till null början.

836
00:35:15,300 --> 00:35:16,410

837
00:35:16,410 --> 00:35:19,770
Men vad gjorde vi när vi
var inne vår sökfunktion?

838
00:35:19,770 --> 00:35:20,940

839
00:35:20,940 --> 00:35:24,870
Vi sätter det lika med första,
vilket inte betyder att göra detta.

840
00:35:24,870 --> 00:35:25,890

841
00:35:25,890 --> 00:35:30,570
Om jag satt ptr lika med först, vad
bör min hand verkligen pekar på?

842
00:35:30,570 --> 00:35:31,070
Rätt.

843
00:35:31,070 --> 00:35:33,290
Så om Gabe och jag kommer
att vara lika värden här,

844
00:35:33,290 --> 00:35:34,760
Vi behöver både peka på nummer 9.

845
00:35:34,760 --> 00:35:36,420
>> Så det här var början på vår historia.

846
00:35:36,420 --> 00:35:38,700
Och nu detta är bara enkelt,
även om syntaxen är ny.

847
00:35:38,700 --> 00:35:40,580
Begreppsmässigt är detta bara linjär sökning.

848
00:35:40,580 --> 00:35:42,750
Är 55 lika med 9?

849
00:35:42,750 --> 00:35:45,559
Eller snarare, låt oss säga mindre än 9.

850
00:35:45,559 --> 00:35:47,600
Därför att jag försöker
räkna ut var att sätta 55.

851
00:35:47,600 --> 00:35:51,270
Mindre än 9, mindre än 17, mindre
än 20, mindre än 22, mindre än 29,

852
00:35:51,270 --> 00:35:52,510
mindre än 34, nr.

853
00:35:52,510 --> 00:35:55,080
Så nu är vi i mål
en av åtminstone tre.

854
00:35:55,080 --> 00:35:59,910
>> Om jag vill infoga 55 hit, vad
kodrader behov av att bli avrättade?

855
00:35:59,910 --> 00:36:01,890
Hur fungerar denna bild av
människor behöver ändra?

856
00:36:01,890 --> 00:36:03,181
Vad gör jag med min vänstra hand?

857
00:36:03,181 --> 00:36:04,530

858
00:36:04,530 --> 00:36:07,360
Detta bör vara null initialt,
eftersom jag är i slutet av listan.

859
00:36:07,360 --> 00:36:09,318
Och vad som ska hända
här med Peter, var det?

860
00:36:09,318 --> 00:36:10,520

861
00:36:10,520 --> 00:36:12,430
Han uppenbarligen kommer att peka på mig.

862
00:36:12,430 --> 00:36:15,580
Så jag hävdar att det finns åtminstone två linjer
av kod i exempelkod från idag

863
00:36:15,580 --> 00:36:18,570
det kommer att genomföra detta
scenariot att lägga 55 i svansen.

864
00:36:18,570 --> 00:36:20,950
Och skulle jag ha någon hop
upp och bara representerar 55?

865
00:36:20,950 --> 00:36:22,200
Okej, du är den nya 55.

866
00:36:22,200 --> 00:36:23,580

867
00:36:23,580 --> 00:36:27,054
>> Så nu vad händer om nästa
scenario kommer tillsammans,

868
00:36:27,054 --> 00:36:29,720
och vi vill infoga i
börjar eller chefen för den här listan?

869
00:36:29,720 --> 00:36:31,100
Och vad är ditt namn, nummer 55?

870
00:36:31,100 --> 00:36:31,420
>> PUBLIKEN: Jack.

871
00:36:31,420 --> 00:36:32,295
>> David J. MALAN: Jack?

872
00:36:32,295 --> 00:36:33,585
OK, trevligt att träffas.

873
00:36:33,585 --> 00:36:34,210
Välkommen ombord.

874
00:36:34,210 --> 00:36:36,640
Så nu ska vi
sätt in, säg, antalet 5.

875
00:36:36,640 --> 00:36:39,840
Här är det andra fallet av
tre vi kom fram till tidigare.

876
00:36:39,840 --> 00:36:43,050
Så om 5 tillhör i början,
Låt oss se hur vi reda på det.

877
00:36:43,050 --> 00:36:46,310
Jag initiera min ptr
pekare till nummer 9 igen.

878
00:36:46,310 --> 00:36:49,140
Och jag insåg, åh, 5 är mindre än 9.

879
00:36:49,140 --> 00:36:50,880
Så fixa denna bild för oss.

880
00:36:50,880 --> 00:36:54,820
Vems händer, Gabe s eller Davids
eller-- vad är nummer 9 namn?

881
00:36:54,820 --> 00:36:55,740
>> PUBLIKEN: Jen.

882
00:36:55,740 --> 00:36:58,406
>> DAVID J. MALAN: Jens hands--
vilken av våra händer behöver ändra?

883
00:36:58,406 --> 00:36:58,905

884
00:36:58,905 --> 00:37:00,970
OK, så Gabe pekar på vad nu?

885
00:37:00,970 --> 00:37:01,640
På mig.

886
00:37:01,640 --> 00:37:02,750
Jag är den nya noden.

887
00:37:02,750 --> 00:37:04,870
Så jag ska bara typ av drag
här för att se det visuellt.

888
00:37:04,870 --> 00:37:06,435
Och under tiden vad ska jag påpeka det?

889
00:37:06,435 --> 00:37:07,910

890
00:37:07,910 --> 00:37:09,020
Fortfarande där jag pekar.

891
00:37:09,020 --> 00:37:10,000
Så det är det.

892
00:37:10,000 --> 00:37:13,717
Så bara egentligen en rad kod fixar
denna fråga verkar det.

893
00:37:13,717 --> 00:37:14,800
Okej, så det är bra.

894
00:37:14,800 --> 00:37:17,580
Och kan någon vara en platshållare för 5?

895
00:37:17,580 --> 00:37:18,080
Kom upp.

896
00:37:18,080 --> 00:37:20,270

897
00:37:20,270 --> 00:37:21,320
Vi ska ta dig nästa gång.

898
00:37:21,320 --> 00:37:24,280
>> Okej, så nu-- och
Inom parentes namnen

899
00:37:24,280 --> 00:37:28,510
Jag gör inte nämns uttryckligen rätten
Nu, pred pekare, föregångare pekare

900
00:37:28,510 --> 00:37:31,260
och nya pekare, det är
bara namnen ges

901
00:37:31,260 --> 00:37:35,280
i exempelkod till pekare eller
mina händer den typen är av pekar runt.

902
00:37:35,280 --> 00:37:36,060
Vad heter du?

903
00:37:36,060 --> 00:37:36,700
>> PUBLIKEN: Christine.

904
00:37:36,700 --> 00:37:37,100
>> DAVID J. MALAN: Christine.

905
00:37:37,100 --> 00:37:38,090
Välkommen ombord.

906
00:37:38,090 --> 00:37:42,180
Okej, så låt oss betrakta nu
en något mer irriterande scenario,

907
00:37:42,180 --> 00:37:46,350
varvid jag vill infoga
ungefär 26 in i detta.

908
00:37:46,350 --> 00:37:47,090
20?

909
00:37:47,090 --> 00:37:47,590
Vad?

910
00:37:47,590 --> 00:37:50,510
Dessa är-- bra vi har denna penna.

911
00:37:50,510 --> 00:37:51,955
Okej, 20.

912
00:37:51,955 --> 00:37:53,640

913
00:37:53,640 --> 00:37:57,570
Om någon kunde få en annan bit av
papper redo, bara i case-- okej.

914
00:37:57,570 --> 00:37:58,370
Åh, intressant.

915
00:37:58,370 --> 00:37:59,760

916
00:37:59,760 --> 00:38:02,390
Ja detta är ett exempel
av en föreläsning bugg.

917
00:38:02,390 --> 00:38:03,894
OK så vad är ditt namn igen?

918
00:38:03,894 --> 00:38:04,560
PUBLIKEN: Julia.

919
00:38:04,560 --> 00:38:07,559
DAVID J. MALAN: Julia, kan du pop
ut och låtsas att du var aldrig där?

920
00:38:07,559 --> 00:38:09,040
OK, detta hände aldrig.

921
00:38:09,040 --> 00:38:09,680
Tack.

922
00:38:09,680 --> 00:38:12,180
Så antar att vi vill sätta in
Julia in i denna länkad lista.

923
00:38:12,180 --> 00:38:13,780
Hon är nummer 20.

924
00:38:13,780 --> 00:38:15,530
Och naturligtvis är hon
kommer att tillhöra vid

925
00:38:15,530 --> 00:38:17,521
begin-- inte peka på något ännu.

926
00:38:17,521 --> 00:38:20,020
Så din hand kan typ av vara
ned null eller några sopor värde.

927
00:38:20,020 --> 00:38:21,210
Låt oss berätta snabb historia.

928
00:38:21,210 --> 00:38:22,980
Jag pekar på nummer 5 den här gången.

929
00:38:22,980 --> 00:38:23,880
Sedan kollar jag 9.

930
00:38:23,880 --> 00:38:25,130
Sedan kollar jag 17.

931
00:38:25,130 --> 00:38:26,247
Sedan kollar jag 22.

932
00:38:26,247 --> 00:38:27,650

933
00:38:27,650 --> 00:38:32,485
Och jag inser, ooh, Julia
måste gå före den 22.

934
00:38:32,485 --> 00:38:33,580

935
00:38:33,580 --> 00:38:34,660
Så vad måste hända?

936
00:38:34,660 --> 00:38:35,786

937
00:38:35,786 --> 00:38:36,910
Vems händer behöver ändra?

938
00:38:36,910 --> 00:38:38,360
Julias, gruva, eller--
vad heter du nu igen?

939
00:38:38,360 --> 00:38:39,230
>> PUBLIKEN: Christian.

940
00:38:39,230 --> 00:38:40,060
>> DAVID J. MALAN: kristen eller?

941
00:38:40,060 --> 00:38:40,560
>> PUBLIKEN: 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 behöver peka 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
Okej.

949
00:38:47,840 --> 00:38:48,960
Så Andy, vill du peka på Julia?

950
00:38:48,960 --> 00:38:50,120
Men vänta lite.

951
00:38:50,120 --> 00:38:53,260
I berättelsen så här långt,
Jag är den typ av man

952
00:38:53,260 --> 00:38:56,800
i laddning, i den meningen att
pekaren är det som är

953
00:38:56,800 --> 00:38:57,850
flytta genom listan.

954
00:38:57,850 --> 00:39:00,800
Vi kan ha ett namn för Andy, men
det finns ingen variabel som heter Andy.

955
00:39:00,800 --> 00:39:04,320
Den enda andra variabeln vi har är
först, vem som representeras av Gabe.

956
00:39:04,320 --> 00:39:07,690
>> Så det här är faktiskt varför alltså
länge har vi inte behövt det.

957
00:39:07,690 --> 00:39:10,846
Men nu på skärmen finns
nämna igen om Pred pekare.

958
00:39:10,846 --> 00:39:11,970
Så låt mig vara tydligare.

959
00:39:11,970 --> 00:39:14,820
Om detta är pekare, jag hade bättre
få lite smartare

960
00:39:14,820 --> 00:39:15,950
om min iteration.

961
00:39:15,950 --> 00:39:19,580
Om du inte har något emot mig gå igenom här
igen, pekar här, pekar här.

962
00:39:19,580 --> 00:39:22,500
Men låt mig få ett Pred pekare,
föregångare pekare, det är

963
00:39:22,500 --> 00:39:24,740
slags pekar på
elementet Jag var bara på.

964
00:39:24,740 --> 00:39:27,330
Så när jag går här, nu
min vänstra hand uppdateringar.

965
00:39:27,330 --> 00:39:29,370
När jag går här min vänstra hand uppdateringar.

966
00:39:29,370 --> 00:39:33,090
Och nu har jag inte bara en pekare till
det element som går efter Julia,

967
00:39:33,090 --> 00:39:36,300
Jag har fortfarande en pekare till
Andy, elementet innan.

968
00:39:36,300 --> 00:39:39,430
Så du har tillgång till, i huvudsak,
ströbröd, om ni så vill,

969
00:39:39,430 --> 00:39:41,500
till alla de erforderliga pekare.

970
00:39:41,500 --> 00:39:43,710
>> Så om jag pekar på
Andy och jag också peka

971
00:39:43,710 --> 00:39:47,105
på Christian, vars händer
bör nu pekade på annat håll?

972
00:39:47,105 --> 00:39:48,770

973
00:39:48,770 --> 00:39:51,960
Så Andy kan nu peka på Julia.

974
00:39:51,960 --> 00:39:54,460
Julia kan nu peka på Christian.

975
00:39:54,460 --> 00:39:56,950
Eftersom hon kan kopiera min
högra pekare.

976
00:39:56,950 --> 00:40:00,044
Och som effektivt sätter dig
tillbaka till denna plats här.

977
00:40:00,044 --> 00:40:02,460
Så kort sagt, även om detta
tar oss slags evigt

978
00:40:02,460 --> 00:40:04,510
att faktiskt uppdatera en
lista kopplad, inser

979
00:40:04,510 --> 00:40:06,580
att verksamheten
är relativt enkla.

980
00:40:06,580 --> 00:40:10,030
Den är av en, två, tre
kodrader i sista hand.

981
00:40:10,030 --> 00:40:12,780
Men lindade runt dem
kodrader förmodligen

982
00:40:12,780 --> 00:40:16,350
är lite av logik som effektivt
ställer frågan, var är vi?

983
00:40:16,350 --> 00:40:18,970
Är vi i början,
mitten eller slutet?

984
00:40:18,970 --> 00:40:21,890
>> Nu, det finns säkert någon annan
verksamhet som vi skulle kunna genomföra.

985
00:40:21,890 --> 00:40:24,880
Och dessa bilder här skildrar precis
vad vi gjorde precis med människor.

986
00:40:24,880 --> 00:40:26,080
Hur är borttagning?

987
00:40:26,080 --> 00:40:30,650
Om jag vill, till exempel,
bort numret 34 eller 55,

988
00:40:30,650 --> 00:40:34,680
Jag kan ha samma typ av kod,
men jag kommer att behöva ett eller två steg.

989
00:40:34,680 --> 00:40:36,110
För vad är nytt?

990
00:40:36,110 --> 00:40:40,460
Om jag tar bort någon på slutet,
liknande antal 55 och sedan 34,

991
00:40:40,460 --> 00:40:42,995
vad också måste förändras som jag gör det?

992
00:40:42,995 --> 00:40:44,870
Jag måste inte evict--
vad heter du nu igen?

993
00:40:44,870 --> 00:40:45,380
>> PUBLIKEN: Jack.

994
00:40:45,380 --> 00:40:46,255
>> DAVID J. MALAN: Jack.

995
00:40:46,255 --> 00:40:49,770
Jag måste inte bara evict-- gratis Jack,
så bokstav ringa gratis Jack, eller åtminstone

996
00:40:49,770 --> 00:40:53,530
pekaren där också, men nu
vad som behöver förändras med Peter?

997
00:40:53,530 --> 00:40:55,510
Hans hand bättre start pekar nedåt.

998
00:40:55,510 --> 00:40:59,300
Därför att så fort jag ringer gratis
Jack, om Peters fortfarande pekar på Jack

999
00:40:59,300 --> 00:41:02,530
och jag håller därför traversera
listan och tillgång denna pekare,

1000
00:41:02,530 --> 00:41:05,650
det är då vår gamle vän segmente
fel kan faktiskt sparka in.

1001
00:41:05,650 --> 00:41:07,860
Eftersom vi har gett
minnes tillbaka till Jack.

1002
00:41:07,860 --> 00:41:10,760
>> Du kan stanna där
tafatt för bara ett ögonblick.

1003
00:41:10,760 --> 00:41:13,410
Eftersom vi har bara ett par
slutgiltiga åtgärder att överväga.

1004
00:41:13,410 --> 00:41:15,600
Ta bort huvudet av listan,
eller beginning-- och den här är

1005
00:41:15,600 --> 00:41:16,349
lite irriterande.

1006
00:41:16,349 --> 00:41:19,640
Eftersom vi måste veta att Gabe
är typ av speciell i detta program.

1007
00:41:19,640 --> 00:41:21,440
Därför att ja, har han sin egen pekare.

1008
00:41:21,440 --> 00:41:24,860
Han inte bara vara riktad mot,
som är nästan alla andra här.

1009
00:41:24,860 --> 00:41:28,112
>> Så när chefen för listan är
avlägsnats, vars händer behöver ändra nu?

1010
00:41:28,112 --> 00:41:29,070
Vad heter du nu igen?

1011
00:41:29,070 --> 00:41:29,450
>> PUBLIKEN: Christine.

1012
00:41:29,450 --> 00:41:31,408
>> DAVID J. MALAN: Jag är hemskt
vid namn, tydligen.

1013
00:41:31,408 --> 00:41:34,011
Så Christine och Gabe,
vars händer måste ändra

1014
00:41:34,011 --> 00:41:36,510
när vi försöker ta bort Christine,
nummer fem, från bilden?

1015
00:41:36,510 --> 00:41:37,550

1016
00:41:37,550 --> 00:41:38,820
OK, så låt oss göra Gabe.

1017
00:41:38,820 --> 00:41:40,950
Gabe kommer att peka,
förmodligen, på nummer 9.

1018
00:41:40,950 --> 00:41:42,230

1019
00:41:42,230 --> 00:41:44,642
Men vad nästa ska hända?

1020
00:41:44,642 --> 00:41:46,600
PUBLIK: Christine bör
vara null [ohörbart].

1021
00:41:46,600 --> 00:41:50,244
DAVID J. MALAN: OK, vi borde nog
märke-- Jag hörde "null" någonstans.

1022
00:41:50,244 --> 00:41:51,410
PUBLIK: Null och fri henne.

1023
00:41:51,410 --> 00:41:51,855
DAVID J. MALAN: null vad?

1024
00:41:51,855 --> 00:41:53,074
PUBLIK: Null och fri henne.

1025
00:41:53,074 --> 00:41:54,490
DAVID J. MALAN: Null och fri henne.

1026
00:41:54,490 --> 00:41:55,422
Så detta är mycket enkelt.

1027
00:41:55,422 --> 00:41:58,380
Och det är perfekt att du är nu sorterar
av att stå där, som inte tillhör.

1028
00:41:58,380 --> 00:42:00,430
Därför att du har varit
frikopplat från listan.

1029
00:42:00,430 --> 00:42:02,820
Du har på ett effektivt sätt varit
föräldralösa från listan.

1030
00:42:02,820 --> 00:42:07,770
Och så vi hade bättre ringa gratis nu
Christine för att ge det minnet tillbaka.

1031
00:42:07,770 --> 00:42:10,240
Annars varje gång vi
ta bort en nod från listan

1032
00:42:10,240 --> 00:42:14,230
vi kanske göra listan
kortare, men faktiskt inte minskar

1033
00:42:14,230 --> 00:42:15,096
storleken på minnet.

1034
00:42:15,096 --> 00:42:17,720
Och så om vi fortsätter att lägga till och
lägga till, lägga till saker till listan,

1035
00:42:17,720 --> 00:42:19,280
min dator kan få långsammare
och långsammare och långsammare,

1036
00:42:19,280 --> 00:42:21,740
eftersom jag kör ut ur
minne, även om jag inte faktiskt

1037
00:42:21,740 --> 00:42:25,580
med Christine s bytes
minne längre.

1038
00:42:25,580 --> 00:42:28,500
>> Så i slutändan finns det andra
scenarier, av course-- borttagning

1039
00:42:28,500 --> 00:42:30,640
i mitten, borttagning
i slutet, som vi såg.

1040
00:42:30,640 --> 00:42:32,348
Men mer intressant
Utmaningen nu är

1041
00:42:32,348 --> 00:42:34,770
kommer att vara att överväga exakt
vad gångtid är.

1042
00:42:34,770 --> 00:42:36,640
Så kan du inte bara hålla din
bitar av papper, om, Gabe,

1043
00:42:36,640 --> 00:42:38,640
du inte skulle ha något emot att ge
alla en stress boll.

1044
00:42:38,640 --> 00:42:42,100
Tack så mycket till vår länkad lista
volontärer här, om du kunde.

1045
00:42:42,100 --> 00:42:45,320
>> [Applåder]

1046
00:42:45,320 --> 00:42:46,700
>> DAVID J. MALAN: Okej.

1047
00:42:46,700 --> 00:42:51,110
Så ett par analytisk
frågor då, om jag kunde.

1048
00:42:51,110 --> 00:42:59,670
Vi har sett denna notation tidigare,
stort O och omega, övre gränser

1049
00:42:59,670 --> 00:43:02,520
och undre gränser för den
gångtid viss algoritm.

1050
00:43:02,520 --> 00:43:04,950
Så låt oss betrakta bara
ett par frågor.

1051
00:43:04,950 --> 00:43:07,090
>> Ett, och vi sa att det
tidigare, vad är igång

1052
00:43:07,090 --> 00:43:10,647
tiden för sökandet efter en
lista när det gäller stora O?

1053
00:43:10,647 --> 00:43:13,480
Vad är en övre gräns för driften
tiden för att söka en länkad lista

1054
00:43:13,480 --> 00:43:16,340
som genomförs av våra volontärer här?

1055
00:43:16,340 --> 00:43:17,820
Det är stora O n, linjärt.

1056
00:43:17,820 --> 00:43:20,630
Därför att i det värsta fallet,
elementet, liksom 55,

1057
00:43:20,630 --> 00:43:23,830
Vi kanske letar efter kan vara där
Jack var, hela vägen i slutet.

1058
00:43:23,830 --> 00:43:28,250
Och tyvärr, till skillnad från en array
Vi kan inte få lust den här gången.

1059
00:43:28,250 --> 00:43:31,820
Även om alla våra människan var
sorterade från små element, fem,

1060
00:43:31,820 --> 00:43:35,900
hela vägen upp till den större element,
55, det är oftast en bra sak.

1061
00:43:35,900 --> 00:43:38,815
Men vad gör det antagandet
inte längre tillåta oss att göra?

1062
00:43:38,815 --> 00:43:39,775

1063
00:43:39,775 --> 00:43:40,650
PUBLIK: [ohörbart]

1064
00:43:40,650 --> 00:43:40,920
DAVID J. MALAN: Säg igen?

1065
00:43:40,920 --> 00:43:41,800
PUBLIK: Random access.

1066
00:43:41,800 --> 00:43:43,049
DAVID J. MALAN: Random access.

1067
00:43:43,049 --> 00:43:46,330
Och i sin tur det betyder att vi kan inte
längre använder svaga nollor, intuition,

1068
00:43:46,330 --> 00:43:49,365
och självklarhet att använda binära
Sök och söndra och härska.

1069
00:43:49,365 --> 00:43:51,240
För även om vi
människor skulle naturligtvis

1070
00:43:51,240 --> 00:43:54,610
se att Andy och Christian var
ungefär i mitten av listan,

1071
00:43:54,610 --> 00:43:57,670
Vi vet bara att som en
dator genom att skumma listan

1072
00:43:57,670 --> 00:43:59,029
från början.

1073
00:43:59,029 --> 00:44:00,570
Så vi har gett upp att random access.

1074
00:44:00,570 --> 00:44:04,380
>> Så stor o n är nu den övre
bundet på vår söktid.

1075
00:44:04,380 --> 00:44:07,920
Hur är omega i sökandet?

1076
00:44:07,920 --> 00:44:11,535
Vad är den undre gränsen för att söka
för vissa nummer i den här listan?

1077
00:44:11,535 --> 00:44:12,410
PUBLIK: [ohörbart]

1078
00:44:12,410 --> 00:44:13,040
DAVID J. MALAN: Säg igen?

1079
00:44:13,040 --> 00:44:13,420
PUBLIKEN: 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 bästa fall är Christine
faktiskt i början av listan.

1083
00:44:17,020 --> 00:44:19,020
Och vi letar efter
nummer fem, så vi hittade henne.

1084
00:44:19,020 --> 00:44:19,787
Så ingen big deal.

1085
00:44:19,787 --> 00:44:22,370
Men hon har fått vara på
början av listan i detta fall.

1086
00:44:22,370 --> 00:44:23,745
Hur är det något liknande Delete?

1087
00:44:23,745 --> 00:44:24,717

1088
00:44:24,717 --> 00:44:26,300
Vad händer om du vill ta bort ett element?

1089
00:44:26,300 --> 00:44:29,200
Vad är den övre gränsen och den lägre
om radering något från en länkad

1090
00:44:29,200 --> 00:44:29,699
listan?

1091
00:44:29,699 --> 00:44:35,195

1092
00:44:35,195 --> 00:44:36,070
PUBLIK: [ohörbart]

1093
00:44:36,070 --> 00:44:36,420
DAVID J. MALAN: Säg igen?

1094
00:44:36,420 --> 00:44:37,067
PUBLIKEN: n.

1095
00:44:37,067 --> 00:44:38,900
DAVID J. MALAN: n är
faktiskt den övre gränsen.

1096
00:44:38,900 --> 00:44:41,700
Eftersom i värsta fall försöker vi
ta bort Jack, som vi just gjorde.

1097
00:44:41,700 --> 00:44:43,050
Han är hela vägen i slutet.

1098
00:44:43,050 --> 00:44:45,419
Tar oss för alltid, eller
n steg för att hitta honom.

1099
00:44:45,419 --> 00:44:46,460
Så det är en övre gräns.

1100
00:44:46,460 --> 00:44:47,430
Det är linjärt, visst.

1101
00:44:47,430 --> 00:44:50,970
Och bästa fall gångtid, eller
de nedre gränserna i bästa fall

1102
00:44:50,970 --> 00:44:51,975
skulle vara konstant tid.

1103
00:44:51,975 --> 00:44:54,600
Eftersom vi kanske försöker ta bort
Christine och vi bara har tur

1104
00:44:54,600 --> 00:44:55,558
hon är i början.

1105
00:44:55,558 --> 00:44:56,350
Vänta lite nu.

1106
00:44:56,350 --> 00:44:59,370
Gabe var även i början,
och vi hade också uppdatera Gabe.

1107
00:44:59,370 --> 00:45:01,150
Så det var inte bara ett steg.

1108
00:45:01,150 --> 00:45:04,210
Så är det verkligen konstant
tid, i bästa fall,

1109
00:45:04,210 --> 00:45:06,345
för att ta bort det minsta elementet?

1110
00:45:06,345 --> 00:45:07,360

1111
00:45:07,360 --> 00:45:10,960
Det är, även om det kan vara två,
tre, eller till och med 100 rader kod,

1112
00:45:10,960 --> 00:45:14,000
om det är lika många
linjer, inte i någon slinga,

1113
00:45:14,000 --> 00:45:16,577
och oberoende av storleken
av listan, absolut.

1114
00:45:16,577 --> 00:45:18,660
Radera elementet vid
början av listan,

1115
00:45:18,660 --> 00:45:21,940
även om vi måste ta itu med
Gabe, är fortfarande konstant tid.

1116
00:45:21,940 --> 00:45:24,220
>> Så detta verkar vara en
massiva steg bakåt.

1117
00:45:24,220 --> 00:45:27,000
Och vad ett slöseri med tid
om, i vecka ett och vecka

1118
00:45:27,000 --> 00:45:30,250
noll hade vi inte bara
pseudokod kod men faktiska koden

1119
00:45:30,250 --> 00:45:35,780
att genomföra något som är log
bas n, eller logga snarare n, bas 2,

1120
00:45:35,780 --> 00:45:37,150
i termer av dess gångtid.

1121
00:45:37,150 --> 00:45:40,710
Så varför i helsike skulle vi vilja börja
med hjälp av något som en länkad lista?

1122
00:45:40,710 --> 00:45:41,517
Yeah.

1123
00:45:41,517 --> 00:45:44,022
>> PUBLIK: Så du kan lägga till
element till arrayen.

1124
00:45:44,022 --> 00:45:46,230
DAVID J. MALAN: Så du kan
lägga till element till arrayen.

1125
00:45:46,230 --> 00:45:47,550
Och detta är för tematisk.

1126
00:45:47,550 --> 00:45:49,740
Och vi kommer att fortsätta att se
detta, denna avvägning, mycket

1127
00:45:49,740 --> 00:45:51,573
som vi har sett en
avvägning med merge sort.

1128
00:45:51,573 --> 00:45:54,606
Vi kunde verkligen påskynda
sök eller sortering, snarare

1129
00:45:54,606 --> 00:45:57,480
Om vi ​​tillbringar lite mer utrymme och
har ytterligare en bit av ett minne

1130
00:45:57,480 --> 00:45:58,760
eller ett system för sammanslagnings slag.

1131
00:45:58,760 --> 00:46:01,270
Men vi spenderar mer
utrymme, men vi sparar tid.

1132
00:46:01,270 --> 00:46:04,820
I det här fallet är vi
ge upp tid men vi är

1133
00:46:04,820 --> 00:46:08,170
få flexibilitet,
dynamik, om man så vill,

1134
00:46:08,170 --> 00:46:10,280
vilket är utan tvekan ett positivt inslag.

1135
00:46:10,280 --> 00:46:11,520
>> Vi är också spendera utrymme.

1136
00:46:11,520 --> 00:46:13,710
I vilken mening är en länkad
listan dyrare

1137
00:46:13,710 --> 00:46:15,700
vad gäller utrymme än en array?

1138
00:46:15,700 --> 00:46:18,379

1139
00:46:18,379 --> 00:46:19,920
Var är det extra utrymmet kommer från?

1140
00:46:19,920 --> 00:46:20,460
Yeah?

1141
00:46:20,460 --> 00:46:21,800
>> PUBLIK: [ohörbart] pekare.

1142
00:46:21,800 --> 00:46:23,310
>> DAVID J. MALAN: Ja, vi
har också pekaren.

1143
00:46:23,310 --> 00:46:25,560
Så detta är minorly irriterande
i som inte längre är

1144
00:46:25,560 --> 00:46:27,780
Jag lagrar bara en int
att representera en int.

1145
00:46:27,780 --> 00:46:30,990
Jag lagrar en int och en
pekare, som också är 32 bitar.

1146
00:46:30,990 --> 00:46:33,470
Så jag bokstavligen fördubblas
mängden utrymme inblandade.

1147
00:46:33,470 --> 00:46:36,040
Så det är en kompromiss, men
det är i fallet med int.

1148
00:46:36,040 --> 00:46:39,580
Anta att du inte lagrar int,
men antar att alla dessa rektanglar

1149
00:46:39,580 --> 00:46:43,290
eller var och en av dessa människor representerade
ett ord, ett engelskt ord som

1150
00:46:43,290 --> 00:46:46,430
kanske fem tecken, 10
tecken, kanske ännu mer.

1151
00:46:46,430 --> 00:46:49,940
Sedan lägga bara 32 fler bitar
kan vara mindre av en stor sak.

1152
00:46:49,940 --> 00:46:52,160
>> Tänk om var och en av eleverna
i demonstrationen

1153
00:46:52,160 --> 00:46:55,107
var bokstavligen elev structs som
har namn och hus och kanske

1154
00:46:55,107 --> 00:46:57,065
telefonnummer och Twitter
handtag och liknande.

1155
00:46:57,065 --> 00:46:59,564
Så alla fält vi började
talar om häromdagen,

1156
00:46:59,564 --> 00:47:02,410
mycket mindre av en stor sak som
våra noder blir mer intressant

1157
00:47:02,410 --> 00:47:05,972
och stora att spendera, eh, en extra
pekaren bara för att koppla ihop dem.

1158
00:47:05,972 --> 00:47:07,180
Men ja, det är en kompromiss.

1159
00:47:07,180 --> 00:47:09,560
Och faktiskt, är koden
mer komplex, eftersom du kommer

1160
00:47:09,560 --> 00:47:11,770
se genom att skumma igenom
som särskilt exempel.

1161
00:47:11,770 --> 00:47:14,302
Men tänk om det fanns
några heliga graal här.

1162
00:47:14,302 --> 00:47:17,010
Vad händer om vi inte tar ett steg
bakåt men ett stort steg framåt

1163
00:47:17,010 --> 00:47:19,180
och genomföra en data
struktur via vilken vi

1164
00:47:19,180 --> 00:47:22,870
kan hitta element som Jack eller
Christine eller andra element

1165
00:47:22,870 --> 00:47:25,870
i denna samling i sann konstant tid?

1166
00:47:25,870 --> 00:47:26,920
Sök är konstant.

1167
00:47:26,920 --> 00:47:28,320
Radera är konstant.

1168
00:47:28,320 --> 00:47:29,570
Insert är konstant.

1169
00:47:29,570 --> 00:47:32,260
Alla dessa verksamheter är konstanta.

1170
00:47:32,260 --> 00:47:33,750
Det skulle vara vår heliga graal.

1171
00:47:33,750 --> 00:47:36,690
Och det är där vi
kommer att plocka upp nästa gång.

1172
00:47:36,690 --> 00:47:38,600
Ser du sedan.

1173
00:47:38,600 --> 00:47:39,371