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

2
00:00:00,500 --> 00:00:11,137
[Muziek]

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

4
00:00:12,220 --> 00:00:13,950
Dit is CS50.

5
00:00:13,950 --> 00:00:18,560
Dit is week vijf voortgezet, en we
heb goed nieuws en slecht nieuws.

6
00:00:18,560 --> 00:00:21,140
Dus goede nieuws is dat CS50
lanceert deze vrijdag.

7
00:00:21,140 --> 00:00:24,430
Als u graag om met ons mee,
hoofd naar de gebruikelijke URL hier.

8
00:00:24,430 --> 00:00:28,670
Nog beter nieuws, geen lezing
deze komende maandag de 13e.

9
00:00:28,670 --> 00:00:31,970
Iets minder beter nieuws,
quiz nul is volgende week woensdag.

10
00:00:31,970 --> 00:00:33,840
Meer informatie kan worden
vinden op deze URL hier.

11
00:00:33,840 --> 00:00:36,340
En in de komende paar dagen
we zullen invuloefeningen

12
00:00:36,340 --> 00:00:39,234
met betrekking tot de kamers
dat we hebben gereserveerd.

13
00:00:39,234 --> 00:00:41,400
Beter nieuws is dat er zal
is een cursus-brede beoordeling

14
00:00:41,400 --> 00:00:43,570
sessie aanstaande
Maandag in de avond.

15
00:00:43,570 --> 00:00:46,270
Blijf op de hoogte van de cursus
website voor de locatie en details.

16
00:00:46,270 --> 00:00:49,290
Secties, hoewel het een
vakantie, zal ook te ontmoeten.

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

18
00:00:50,490 --> 00:00:52,940
Beste nieuws, lezing volgende week vrijdag.

19
00:00:52,940 --> 00:00:56,220
Dus dit is een traditie die we
hebben, zoals in de syllabus.

20
00:00:56,220 --> 00:00:58,100
Alleen-- het gaat geweldig zijn.

21
00:00:58,100 --> 00:01:02,510
Je zult dingen zoals te zien
constante tijd datastructuren

22
00:01:02,510 --> 00:01:04,730
en hash tabellen en bomen en probeert.

23
00:01:04,730 --> 00:01:07,150
En we praten over verjaardag problemen.

24
00:01:07,150 --> 00:01:09,440
Een hele hoop dingen
wacht volgende week vrijdag.

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
Hoe dan ook.

28
00:01:13,190 --> 00:01:17,080
>> Dus herinneren dat we geweest zijn
gericht op deze foto van wat er

29
00:01:17,080 --> 00:01:18,980
binnenkant van het geheugen van onze computer.

30
00:01:18,980 --> 00:01:22,875
Dus geheugen of RAM is waar programma
bestaan ​​terwijl je ze lopen.

31
00:01:22,875 --> 00:01:25,215
Als u dubbelklikt op een
pictogram om een ​​aantal programma uit te voeren

32
00:01:25,215 --> 00:01:27,520
of dubbelklik op een
pictogram om een ​​bestand te openen,

33
00:01:27,520 --> 00:01:30,430
het is geladen vanaf de vaste
rijden of solid state drive

34
00:01:30,430 --> 00:01:34,190
in het RAM, Random Access Memory, waar
het leeft, totdat de stroom wordt uitgeschakeld,

35
00:01:34,190 --> 00:01:36,700
de laptop deksel sluit,
of je stopt het programma.

36
00:01:36,700 --> 00:01:38,960
>> Nu geheugen van
die heb je waarschijnlijk

37
00:01:38,960 --> 00:01:41,950
1 gigabyte deze dagen, 2
gigabytes, of zelfs veel meer,

38
00:01:41,950 --> 00:01:44,420
wordt algemeen ingedeeld
voor een bepaald programma

39
00:01:44,420 --> 00:01:47,170
in dit soort rechthoekige
conceptueel model

40
00:01:47,170 --> 00:01:50,860
waarbij we de stapel aan de onderkant
en een heleboel andere dingen aan de top.

41
00:01:50,860 --> 00:01:53,140
Het ding op de top
we hebben gezien op deze foto

42
00:01:53,140 --> 00:01:55,670
voordat, maar nooit over gesproken
is de zogenaamde text segment.

43
00:01:55,670 --> 00:01:58,419
Tekstsegment is gewoon een mooie manier
zeggen de nullen en enen die

44
00:01:58,419 --> 00:02:01,150
stel uw werkelijke gecompileerde programma.

45
00:02:01,150 --> 00:02:03,910
>> Dus wanneer u dubbelklikt op
Microsoft Word op uw Mac of pc,

46
00:02:03,910 --> 00:02:08,030
of wanneer u dot draaien slash Mario op een
Linux-computer op uw terminal venster,

47
00:02:08,030 --> 00:02:12,460
de nullen en enen dat componeren
Word of Mario worden tijdelijk opgeslagen

48
00:02:12,460 --> 00:02:16,610
in het RAM-geheugen van uw computer in de zogenaamde
tekstsegment voor een bepaald programma.

49
00:02:16,610 --> 00:02:19,080
Onder dat gaat geïnitialiseerd
en uninitialized gegevens.

50
00:02:19,080 --> 00:02:22,655
Dit is dingen zoals globale variabelen,
dat we niet veel van heb gebruikt,

51
00:02:22,655 --> 00:02:24,910
maar af en toe we hebben
had globale variabelen

52
00:02:24,910 --> 00:02:28,819
of statisch gedefinieerde tekenreeksen die
is hard gecodeerd woorden als "hello"

53
00:02:28,819 --> 00:02:31,860
die niet zijn opgenomen in door de gebruiker
die zijn hard-coded in uw programma.

54
00:02:31,860 --> 00:02:34,230
>> Nu, op de bodem die we
de zogenaamde stack.

55
00:02:34,230 --> 00:02:37,665
En de stapel, tot nu toe, we zijn geweest
gebruik voor wat allerlei doeleinden?

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

57
00:02:39,706 --> 00:02:40,997
Wat is de stack gebruikt voor?

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

59
00:02:41,160 --> 00:02:42,070
>> PUBLIEK: Functies.

60
00:02:42,070 --> 00:02:43,320
>> DAVID J. MALAN: Voor functies?

61
00:02:43,320 --> 00:02:44,980
In welke zin voor functies?

62
00:02:44,980 --> 00:02:48,660
>> PUBLIEK: Als u een functie aan te roepen, de
argumenten worden gekopieerd op de stapel.

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

64
00:02:49,660 --> 00:02:52,650
Wanneer u een functie aan te roepen, haar
argumenten worden gekopieerd op de stapel.

65
00:02:52,650 --> 00:02:56,330
Dus elke X of Y of A of B's
dat je voorbij in een functie

66
00:02:56,330 --> 00:02:58,680
worden tijdelijk in de
de zogenaamde stack,

67
00:02:58,680 --> 00:03:02,000
net als een van de Annenberg
eetzaal trays, en ook de dingen

68
00:03:02,000 --> 00:03:03,190
als lokale variabelen.

69
00:03:03,190 --> 00:03:06,290
Als uw foo functie of je swap
functie lokale variabelen,

70
00:03:06,290 --> 00:03:08,602
zoals temp, die twee
belanden op de stapel.

71
00:03:08,602 --> 00:03:11,560
Nu zullen we niet te veel over praten
hen, maar deze omgevingsvariabelen

72
00:03:11,560 --> 00:03:15,690
aan de onderkant hebben we een tijdje geleden, toen zag
Ik was gepruts bij het toetsenbord een dag

73
00:03:15,690 --> 00:03:20,050
en ik begon toegang dingen
zoals argv 100 of argv 1000,

74
00:03:20,050 --> 00:03:22,320
net elements-- ik vergeet
de numbers-- maar

75
00:03:22,320 --> 00:03:24,330
werden niet verondersteld te worden benaderd door mij.

76
00:03:24,330 --> 00:03:26,581
We begonnen met het zien van enkele
funky symbolen op het beeldscherm.

77
00:03:26,581 --> 00:03:28,330
Dat waren zogenaamde
omgevingsvariabelen

78
00:03:28,330 --> 00:03:32,390
zoals de algemene instellingen voor mijn
programma of voor mijn computer, niet

79
00:03:32,390 --> 00:03:37,090
los van de recente
bug die we besproken hebben,

80
00:03:37,090 --> 00:03:39,670
Shellshock, dat is al
teistert een flink aantal computers.

81
00:03:39,670 --> 00:03:42,960
>> Nu ten slotte, in de focus van vandaag
we uiteindelijk op de heap.

82
00:03:42,960 --> 00:03:44,864
Dit is een stuk geheugen.

83
00:03:44,864 --> 00:03:47,030
En fundamenteel al deze
geheugen is hetzelfde spul.

84
00:03:47,030 --> 00:03:48,040
Het is dezelfde hardware.

85
00:03:48,040 --> 00:03:49,956
We zijn gewoon een soort van
behandelen van verschillende clusters

86
00:03:49,956 --> 00:03:51,460
bytes voor verschillende doeleinden.

87
00:03:51,460 --> 00:03:56,540
De hoop wordt ook gaat worden, waar
variabelen en het geheugen die u aanvraagt

88
00:03:56,540 --> 00:03:58,810
van het besturingssysteem
tijdelijk wordt opgeslagen.

89
00:03:58,810 --> 00:04:01,890
>> Maar er is een soort van een probleem
hier, als het beeld inhoudt.

90
00:04:01,890 --> 00:04:05,261
We soort hebben twee
schepen over te botsen.

91
00:04:05,261 --> 00:04:08,010
Want als je meer en meer gebruik maken van
van de stapel, en zoals we vandaag zien

92
00:04:08,010 --> 00:04:11,800
verder, als je meer en meer van de te gebruiken
hoop, zeker slechte dingen kunnen gebeuren.

93
00:04:11,800 --> 00:04:15,054
En inderdaad, we kunnen veroorzaken dat
al dan niet opzettelijk.

94
00:04:15,054 --> 00:04:16,970
Dus de laatste cliffhanger
bedroeg dit programma,

95
00:04:16,970 --> 00:04:20,570
die geen functionele geserveerd hebben
ander doel dan om aan te tonen

96
00:04:20,570 --> 00:04:24,750
hoe je als een bad guy eigenlijk kan nemen
voordeel van bugs in programma iemands

97
00:04:24,750 --> 00:04:28,460
en de overname van een programma of zelfs een
hele computer systeem of server.

98
00:04:28,460 --> 00:04:31,660
Dus gewoon een blik te werpen in het kort, je
merken dat de belangrijkste op de bodem

99
00:04:31,660 --> 00:04:34,510
neemt in de command line
argumenten, zoals per argv.

100
00:04:34,510 --> 00:04:38,480
En het heeft een oproep naar een functie f,
wezen een naamloos functie genaamd

101
00:04:38,480 --> 00:04:40,250
f, en het is voorbij in argv [1].

102
00:04:40,250 --> 00:04:43,960
>> Dus wat het woord van de gebruiker typt in bij
de vraag achter de naam van dit programma,

103
00:04:43,960 --> 00:04:49,310
en dan is deze willekeurige functie op
top, f, neemt in een string, AKA char *,

104
00:04:49,310 --> 00:04:51,720
als we begonnen te bespreken,
en het gewoon noemt het "bar."

105
00:04:51,720 --> 00:04:53,310
Maar we konden het iets noemen.

106
00:04:53,310 --> 00:04:57,470
En dan verklaart, binnen
of f, een reeks karakters

107
00:04:57,470 --> 00:04:59,930
riep c-- 12 dergelijke tekens.

108
00:04:59,930 --> 00:05:03,580
>> Nu, door het verhaal dat ik vertelde
een moment geleden, waar in het geheugen

109
00:05:03,580 --> 00:05:06,720
is c, of zijn die 12
Chars gaat uiteindelijk?

110
00:05:06,720 --> 00:05:07,570
Even voor de duidelijkheid.

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

112
00:05:08,070 --> 00:05:08,590
>> PUBLIEK: Op de stapel.

113
00:05:08,590 --> 00:05:09,420
>> DAVID J. Malan: Op de stapel.

114
00:05:09,420 --> 00:05:10,720
Dus c een lokale variabele.

115
00:05:10,720 --> 00:05:14,079
We vragen om 12 tekens of 12 bytes.

116
00:05:14,079 --> 00:05:16,120
Die gaan uiteindelijk
op de zogenaamde stack.

117
00:05:16,120 --> 00:05:18,530
Nu eindelijk is deze andere functie
dat is eigenlijk best handig,

118
00:05:18,530 --> 00:05:20,571
maar we hebben niet echt gebruikt
het zelf, strncopy.

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

120
00:05:21,550 --> 00:05:25,200
Het betekent draad exemplaar, maar
slechts n letters, n tekens.

121
00:05:25,200 --> 00:05:31,990
Zo n tekens zal zijn
gekopieerd van de bar in de c.

122
00:05:31,990 --> 00:05:32,980
En hoeveel?

123
00:05:32,980 --> 00:05:34,110
De lengte van de bar.

124
00:05:34,110 --> 00:05:36,330
Dus met andere woorden, dat
een regel, strncopy,

125
00:05:36,330 --> 00:05:39,500
gaat kopiëren
effectief bar in te c.

126
00:05:39,500 --> 00:05:42,340
>> Nu, gewoon om soort te anticiperen
de moraal van dit verhaal,

127
00:05:42,340 --> 00:05:44,750
wat is potentieel problematisch hier?

128
00:05:44,750 --> 00:05:49,710
Ook al zijn we het controleren van de lengte
van de bar en het passeren van het in strncopy,

129
00:05:49,710 --> 00:05:53,145
wat is je darmen te vertellen is
nog steeds kapot over dit programma?

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
>> PUBLIEK: Omvat niet
ruimte voor het nul karakter.

133
00:05:57,491 --> 00:05:59,990
DAVID J. MALAN: Omvat niet
ruimte voor het nul karakter.

134
00:05:59,990 --> 00:06:02,073
Potentieel tegenstelling tot
praktijk van het verleden doen we niet eens

135
00:06:02,073 --> 00:06:04,810
hebben zo veel als een plus van 1 tot
huisvesten die null karakter.

136
00:06:04,810 --> 00:06:06,649
Maar het is nog erger dan dat.

137
00:06:06,649 --> 00:06:07,940
Wat anders zijn we niet te doen?

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

139
00:06:08,432 --> 00:06:09,307
>> PUBLIEK: [onverstaanbaar]

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
We hebben hard coded 12 vrij willekeurig.

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

144
00:06:19,497 --> 00:06:21,330
Dat is niet zozeer de
probleem, maar het feit

145
00:06:21,330 --> 00:06:25,630
dat we niet eens kijken of
de lengte van de bar is minder dan 12,

146
00:06:25,630 --> 00:06:28,530
in welk geval het gaat worden
veilig om het in het geheugen

147
00:06:28,530 --> 00:06:30,260
genaamd c die we hebben toegewezen.

148
00:06:30,260 --> 00:06:32,960
Immers, indien bar is als
20 tekens lang zijn,

149
00:06:32,960 --> 00:06:39,010
Deze functie lijkt te kopiëren
20 personages uit bar in c, waardoor

150
00:06:39,010 --> 00:06:41,310
waarbij ten minste 8 bytes
dat het niet moet.

151
00:06:41,310 --> 00:06:42,690
Dat is de implicatie hier.

152
00:06:42,690 --> 00:06:44,347
>> Dus in het kort, gebroken programma.

153
00:06:44,347 --> 00:06:45,180
Niet zo'n big deal.

154
00:06:45,180 --> 00:06:46,360
Misschien krijg je een segmentation fault.

155
00:06:46,360 --> 00:06:47,651
We hebben allemaal wel bugs in programma's.

156
00:06:47,651 --> 00:06:50,196
We hebben allemaal kunnen bugs hebben
in programma's op dit moment.

157
00:06:50,196 --> 00:06:51,320
Maar wat is de implicatie?

158
00:06:51,320 --> 00:06:54,390
Nou, hier is een ingezoomde versie van
dat beeld van het geheugen van mijn computer.

159
00:06:54,390 --> 00:06:56,230
Dit is de bodem van mijn stack.

160
00:06:56,230 --> 00:06:59,644
En inderdaad, op de bodem is wat
riep ouder routine stapel, mooie manier om

161
00:06:59,644 --> 00:07:00,560
om te zeggen dat is belangrijkste.

162
00:07:00,560 --> 00:07:03,772
Zo dat wie de functie genaamd
f dat we het over hebben.

163
00:07:03,772 --> 00:07:05,230
Dit is de bodem van de stapel.

164
00:07:05,230 --> 00:07:06,640
Retouradres is iets nieuws.

165
00:07:06,640 --> 00:07:08,810
Het is er altijd geweest,
altijd in dat beeld zijn.

166
00:07:08,810 --> 00:07:10,440
We belde nooit aandacht aan.

167
00:07:10,440 --> 00:07:15,290
Omdat blijkt hoe c werkt is
dat wanneer een functie noemt een ander,

168
00:07:15,290 --> 00:07:18,780
niet alleen de argumenten aan
functie krijgen geduwd op de stack,

169
00:07:18,780 --> 00:07:22,470
niet alleen lokaal de functie
variabelen krijgen geduwd op de stack,

170
00:07:22,470 --> 00:07:26,820
zoiets als een retouradres
Ook wordt gezet op de stapel.

171
00:07:26,820 --> 00:07:33,330
In het bijzonder, als belangrijkste oproepen foo, main's
eigen adres in het geheugen, os iets,

172
00:07:33,330 --> 00:07:38,240
effectief wordt gezet op de stapel
zodat wanneer f gebeurt uitvoeren hiervan

173
00:07:38,240 --> 00:07:43,630
weet waar om terug te springen in de tekst
segment om te kunnen blijven uitvoeren.

174
00:07:43,630 --> 00:07:47,760
>> Dus als we hier conceptueel,
in de belangrijkste, dan is f wordt aangeroepen.

175
00:07:47,760 --> 00:07:50,200
Hoe werkt f weten wie
naar handbediening terug?

176
00:07:50,200 --> 00:07:52,020
Nou, deze kleine
breadcrumb in rood hier,

177
00:07:52,020 --> 00:07:54,978
riep het retouradres, het is gewoon
cheques, wat is dat retouradres?

178
00:07:54,978 --> 00:07:57,039
Oh, laat me terug naar de hoofdpagina te springen hier.

179
00:07:57,039 --> 00:07:59,080
En dat is een beetje
van een oversimplificatie,

180
00:07:59,080 --> 00:08:00,750
omdat de nullen en enen
voor de belangrijkste zijn technisch

181
00:08:00,750 --> 00:08:01,967
hier in de tech segment.

182
00:08:01,967 --> 00:08:03,800
Maar dat is het idee. f
moet gewoon weten wat

183
00:08:03,800 --> 00:08:06,680
waar controle gaat uiteindelijk terug.

184
00:08:06,680 --> 00:08:09,790
>> Maar zoals computers
hebben lang dingen aangelegd

185
00:08:09,790 --> 00:08:12,320
als lokale variabelen en
argumenten is als dit.

186
00:08:12,320 --> 00:08:17,180
Dus in de top van deze afbeelding in
blauw is de stack frame voor f, zodat alle

187
00:08:17,180 --> 00:08:19,630
van het geheugen dat f
specifiek is gebruikt.

188
00:08:19,630 --> 00:08:22,990
Dus daarom, merken dat
bar is op deze foto.

189
00:08:22,990 --> 00:08:23,980
Bar was zijn argument.

190
00:08:23,980 --> 00:08:27,240
En wij aangevoerd dat de argumenten om
functies krijgen geduwd op de stack.

191
00:08:27,240 --> 00:08:29,910
En c, natuurlijk
ook in dit plaatje.

192
00:08:29,910 --> 00:08:33,520
>> En net voor notationeel doeleinden,
merken in de linker bovenhoek

193
00:08:33,520 --> 00:08:37,020
wordt wat zou c beugel 0 en
vervolgens iets naar beneden naar rechts

194
00:08:37,020 --> 00:08:38,220
is c beugel 11.

195
00:08:38,220 --> 00:08:41,240
Dus met andere woorden, kun je je voorstellen
dat er een raster van bytes

196
00:08:41,240 --> 00:08:44,380
daar eerste is
linksboven, onder in die

197
00:08:44,380 --> 00:08:48,360
is de laatste van de 12 bytes.

198
00:08:48,360 --> 00:08:49,930
>> Maar nu proberen om vooruit te spoelen.

199
00:08:49,930 --> 00:08:55,580
Wat er gaat gebeuren als we passeren
in een string bar dat is langer dan c?

200
00:08:55,580 --> 00:08:59,130
En we zijn niet te controleren of
Het is inderdaad langer dan 12.

201
00:08:59,130 --> 00:09:03,146
Welk deel van deze foto gaat
overschreven door bytes 0, 1, 2, 3,

202
00:09:03,146 --> 00:09:07,890
dot dot dot, 11, en vervolgens
slecht, 12, 13 tot 19?

203
00:09:07,890 --> 00:09:11,820
Wat gaat er hier gebeuren,
als je afleiden uit het bestelproces

204
00:09:11,820 --> 00:09:14,790
dat c beugel 0 is op de bovenste
en c beugel 11 is een soort van naar beneden

205
00:09:14,790 --> 00:09:15,812
rechts?

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

207
00:09:16,796 --> 00:09:19,260
>> PUBLIEK: Nou, het gaat
aan de char * bar overschrijven.

208
00:09:19,260 --> 00:09:22,260
>> DAVID J. MALAN: Ja, het lijkt erop dat
je gaat naar char * bar overschrijven.

209
00:09:22,260 --> 00:09:26,245
En nog erger, als je in een hele lange sturen
snaar, zou je zelfs overschrijven wat?

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

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

212
00:09:28,570 --> 00:09:31,380
Die weer, is net als een
breadcrumb om het programma waar vertellen

213
00:09:31,380 --> 00:09:34,060
om terug te gaan naar toen f
gebeurt wordt genoemd.

214
00:09:34,060 --> 00:09:37,140
>> Dus wat slechteriken meestal doen
is als ze over een programma komen

215
00:09:37,140 --> 00:09:41,290
dat ze zijn benieuwd of is
exploiteerbare, buggy op een zodanige wijze

216
00:09:41,290 --> 00:09:43,550
dat hij kan nemen
voordeel dat insect,

217
00:09:43,550 --> 00:09:45,720
zij over het algemeen niet krijgen
dit recht de eerste keer.

218
00:09:45,720 --> 00:09:48,590
Ze beginnen gewoon verzenden, bijvoorbeeld,
willekeurige tekenreeksen in uw programma,

219
00:09:48,590 --> 00:09:50,260
zowel op het toetsenbord,
of eerlijk gezegd waarschijnlijk dat ze

220
00:09:50,260 --> 00:09:52,740
een klein programma schrijven om gewoon
automatisch genereren van strijkers,

221
00:09:52,740 --> 00:09:55,430
en beginnen bonzen op uw programma door
verzenden in veel verschillende ingangen

222
00:09:55,430 --> 00:09:56,340
bij verschillende lengtes.

223
00:09:56,340 --> 00:09:58,990
>> Zodra je het programma crasht,
dat is een geweldig ding.

224
00:09:58,990 --> 00:10:01,020
Want het betekent dat hij
of zij heeft ontdekt

225
00:10:01,020 --> 00:10:02,660
wat waarschijnlijk inderdaad een bug.

226
00:10:02,660 --> 00:10:05,830
En dan kunnen ze slimmer krijgen
en zich te concentreren beginnen enger

227
00:10:05,830 --> 00:10:07,420
over hoe je die bug te exploiteren.

228
00:10:07,420 --> 00:10:11,480
In het bijzonder, wat hij of zij zou kunnen
doen is, in het beste geval, hello.

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

230
00:10:12,210 --> 00:10:14,750
Het is een string dat is kort genoeg.

231
00:10:14,750 --> 00:10:18,100
Maar wat als hij of zij stuurt,
en we zullen het generaliseren als,

232
00:10:18,100 --> 00:10:20,890
aanval code-- dus nullen
en degenen die dingen te doen

233
00:10:20,890 --> 00:10:25,150
zoals rm-rf, dat alles verwijderen
van de harde schijf of spam versturen

234
00:10:25,150 --> 00:10:27,000
of andere manier de machine aan te vallen?

235
00:10:27,000 --> 00:10:29,570
>> Als elk van deze
letters A gewoon vertegenwoordigt,

236
00:10:29,570 --> 00:10:32,380
conceptueel, aanval, aanval,
aanval, aanval, een aantal slechte code

237
00:10:32,380 --> 00:10:36,410
dat iemand anders geschreven, maar
als die persoon slim genoeg

238
00:10:36,410 --> 00:10:40,790
om niet alleen zijn allemaal voorzien
van deze rm-RFS, maar ook

239
00:10:40,790 --> 00:10:46,100
zijn of haar laatste paar bytes
is een nummer dat correspondeert

240
00:10:46,100 --> 00:10:50,540
het adres van zijn
of haar eigen aanval code

241
00:10:50,540 --> 00:10:53,820
dat hij of zij in net voorbij
door deze te voorzien op de prompt,

242
00:10:53,820 --> 00:10:58,760
u effectief kunt misleiden de computer
in het opmerken wanneer f wordt gedaan uitvoeren,

243
00:10:58,760 --> 00:11:02,400
oh, het is tijd voor mij om te springen
terug naar de rode retouradres.

244
00:11:02,400 --> 00:11:06,070
Maar omdat hij of zij heeft een of andere manier
overlapt dat retouradres

245
00:11:06,070 --> 00:11:09,602
met hun eigen nummer,
en ze zijn slim genoeg

246
00:11:09,602 --> 00:11:11,560
te hebben geconfigureerd dat
nummer te verwijzen, zoals u

247
00:11:11,560 --> 00:11:13,740
zien in de super top
linkerhoek er,

248
00:11:13,740 --> 00:11:18,020
het actuele adres van de computer
herinnering van sommige aanval code,

249
00:11:18,020 --> 00:11:21,740
een bad guy kan de computer te misleiden
in het uitvoeren van zijn of haar eigen code.

250
00:11:21,740 --> 00:11:23,700
>> En die code, nogmaals, kan van alles zijn.

251
00:11:23,700 --> 00:11:26,120
Het wordt over het algemeen genoemd
shell code, dat is gewoon

252
00:11:26,120 --> 00:11:29,030
een manier om te zeggen dat het niet
over het algemeen iets eenvoudigs als rm-rf.

253
00:11:29,030 --> 00:11:32,340
Het is eigenlijk zoiets als Bash,
of een echte programma geeft hem

254
00:11:32,340 --> 00:11:37,230
of haar programmatische controle uit te voeren
iets anders dat ze willen.

255
00:11:37,230 --> 00:11:40,210
Dus in het kort, dit alles
komt voort uit het simpele feit

256
00:11:40,210 --> 00:11:44,490
dat deze bug betrokken niet controleren
de grenzen van de array.

257
00:11:44,490 --> 00:11:47,250
En omdat de manier
computers werk dat zij

258
00:11:47,250 --> 00:11:49,430
Gebruik de stapel uit
effectief, conceptueel,

259
00:11:49,430 --> 00:11:54,830
bottom up op, maar dan is de elementen
u op de stapel te duwen groeien boven naar beneden,

260
00:11:54,830 --> 00:11:56,624
Dit is ongelooflijk problematisch.

261
00:11:56,624 --> 00:11:58,290
Nu, er zijn manieren om te werken rond dit.

262
00:11:58,290 --> 00:12:00,800
En eerlijk gezegd, er zijn talen
om mee te werken rond dit.

263
00:12:00,800 --> 00:12:03,100
Java immuun bijvoorbeeld
om deze specifieke kwestie.

264
00:12:03,100 --> 00:12:04,110
Omdat ze niet geven u tips.

265
00:12:04,110 --> 00:12:05,943
Ze geven je niet
directe geheugenadressen.

266
00:12:05,943 --> 00:12:08,560
Dus met deze kracht die we hebben
om iets aan te raken in het geheugen

267
00:12:08,560 --> 00:12:11,580
We willen komt, toegegeven, een groot risico.

268
00:12:11,580 --> 00:12:12,430
>> Dus houd een oogje in het zeil.

269
00:12:12,430 --> 00:12:14,596
Als, eerlijk gezegd, in de maanden
of de komende jaren, op elk moment

270
00:12:14,596 --> 00:12:17,740
je leest over enkele uitbuiting
van een programma of een server,

271
00:12:17,740 --> 00:12:22,370
als je ooit een hint van iets te zien
als een buffer overflow aanval,

272
00:12:22,370 --> 00:12:25,390
of stack overflow is een ander type
van de aanval, in dezelfde geest,

273
00:12:25,390 --> 00:12:28,770
zoveel inspireert de website
te noemen, als je het weet,

274
00:12:28,770 --> 00:12:33,170
het is allemaal over slechts
overlopen de omvang van sommige karakter

275
00:12:33,170 --> 00:12:36,200
matrix of een matrix algemeen.

276
00:12:36,200 --> 00:12:38,822
Heeft u vragen, dan, op deze?

277
00:12:38,822 --> 00:12:39,780
Probeer dit niet thuis.

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

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

280
00:12:42,300 --> 00:12:47,270
Dus malloc tot nu toe heeft onze nieuwe geweest
vriend in dat we kunnen geheugen toe te wijzen

281
00:12:47,270 --> 00:12:50,540
dat we niet per se te weten in
vooruit dat we willen, zodat we niet hebben

282
00:12:50,540 --> 00:12:52,920
hard code in onze
programmanummers zoals 12.

283
00:12:52,920 --> 00:12:55,550
Zodra de gebruiker vertelt ons hoeveel
gegevens die hij of zij wil ingang,

284
00:12:55,550 --> 00:12:58,000
kunnen we dat veel geheugen malloc.

285
00:12:58,000 --> 00:13:01,484
>> Dus malloc zo blijkt, naar de
zover wij dat al het gebruik ervan,

286
00:13:01,484 --> 00:13:03,900
expliciet de vorige keer, en dan
Jullie zijn met behulp van het

287
00:13:03,900 --> 00:13:08,160
voor getString onbewust voor
enkele weken, het hele geheugen malloc's

288
00:13:08,160 --> 00:13:09,820
komt van de zogenaamde heap.

289
00:13:09,820 --> 00:13:13,852
En daarom getString bijvoorbeeld
dynamisch geheugen toe te wijzen

290
00:13:13,852 --> 00:13:16,060
zonder te weten wat je bent
gaan om te typen op voorhand,

291
00:13:16,060 --> 00:13:21,520
geef je terug een pointer naar dat geheugen,
en dat geheugen is nog steeds van jou te houden,

292
00:13:21,520 --> 00:13:24,080
zelfs na getString rendement.

293
00:13:24,080 --> 00:13:27,450
Omdat recall na al dat de
stack is voortdurend op en neer,

294
00:13:27,450 --> 00:13:27,950
op en neer.

295
00:13:27,950 --> 00:13:30,230
En zodra het gaat
neer, dat betekent dat alle vormen van geheugen

296
00:13:30,230 --> 00:13:33,030
deze functie gebruikt moet
niet gebruikt worden door iemand anders.

297
00:13:33,030 --> 00:13:34,570
Het is nu vuilnis waarden.

298
00:13:34,570 --> 00:13:36,120
>> Maar de hoop is hier boven.

299
00:13:36,120 --> 00:13:39,360
En wat is er leuk aan malloc is dat
wanneer malloc wijst geheugen hier,

300
00:13:39,360 --> 00:13:42,070
het is niet beïnvloed, want de
hoofdzaak door de stack.

301
00:13:42,070 --> 00:13:46,000
En dus elke functie kan toegang
geheugen dat is malloc'd,

302
00:13:46,000 --> 00:13:49,120
zelfs door een functie als getString,
zelfs nadat het is geretourneerd.

303
00:13:49,120 --> 00:13:51,700
>> Nu is het omgekeerde van malloc is gratis.

304
00:13:51,700 --> 00:13:53,900
En inderdaad, de regel die u
moeten beginnen met het goedkeuren

305
00:13:53,900 --> 00:13:58,950
is elke, elke, elke keer dat je malloc gebruiken
je moet zelf gebruik maken van gratis, uiteindelijk,

306
00:13:58,950 --> 00:14:00,280
op dezelfde pointer.

307
00:14:00,280 --> 00:14:03,289
Al die tijd hebben we het schrijven van
buggy, buggy code, om vele redenen.

308
00:14:03,289 --> 00:14:05,580
Maar een van die is
met de CS50 bibliotheek, die

309
00:14:05,580 --> 00:14:09,010
zelf bewust
buggy, het lekt geheugen.

310
00:14:09,010 --> 00:14:11,410
Elke keer dat je getString moeten bellen
de afgelopen weken

311
00:14:11,410 --> 00:14:13,870
we de operationele vragen
systeem, Linux, voor het geheugen.

312
00:14:13,870 --> 00:14:15,780
En je hebt nooit het ooit teruggegeven.

313
00:14:15,780 --> 00:14:17,730
Dit is niet in
oefenen, een goede zaak.

314
00:14:17,730 --> 00:14:20,330
>> En Valgrind, een van de
gereedschappen geïntroduceerd in Pset 4,

315
00:14:20,330 --> 00:14:22,900
is alles over u te helpen
nu vinden bugs als dat.

316
00:14:22,900 --> 00:14:27,060
Maar gelukkig voor Pset 4 je niet nodig hebt
de CS50 bibliotheek of getString gebruiken.

317
00:14:27,060 --> 00:14:31,220
Dus bugs met betrekking tot het geheugen zijn
uiteindelijk gaat om uw eigen zijn.

318
00:14:31,220 --> 00:14:34,060
>> Dus malloc is meer dan alleen
geschikt voor dit doel.

319
00:14:34,060 --> 00:14:37,420
We kunnen eigenlijk nu op te lossen
fundamenteel verschillende problemen,

320
00:14:37,420 --> 00:14:41,640
en fundamenteel problemen meer
effectief per week zero's belofte.

321
00:14:41,640 --> 00:14:44,720
Tot nu toe is dit de meest sexy
datastructuur die we hebben gehad.

322
00:14:44,720 --> 00:14:47,804
En door datastructuur ik bedoel
een manier van het conceptualiseren van het geheugen

323
00:14:47,804 --> 00:14:50,720
op een manier die verder gaat dan alleen maar te zeggen,
Dit is een int, dit is een char.

324
00:14:50,720 --> 00:14:52,930
We kunnen samen gaan cluster dingen.

325
00:14:52,930 --> 00:14:54,460
>> Dus een scala leek dit.

326
00:14:54,460 --> 00:14:57,270
En wat sleutel in ongeveer een was
array is dat het je geeft

327
00:14:57,270 --> 00:14:59,724
back-to-back brokken
geheugen, die elk

328
00:14:59,724 --> 00:15:02,765
gaat van hetzelfde type zijn, int,
int, int, int of char, char, char,

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

330
00:15:03,330 --> 00:15:04,496
Maar er zijn een paar nadelen.

331
00:15:04,496 --> 00:15:06,570
Dit is bijvoorbeeld
een array van grootte zes.

332
00:15:06,570 --> 00:15:10,650
Stel dat je deze array te vullen met zes
nummers en dan, om wat voor reden,

333
00:15:10,650 --> 00:15:13,187
je gebruiker wil geven
je een zevende nummer.

334
00:15:13,187 --> 00:15:14,020
Waar haal je het?

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

336
00:15:15,490 --> 00:15:18,990
>> Wat is de oplossing als u
creëerde een matrix op de stack,

337
00:15:18,990 --> 00:15:22,030
bijvoorbeeld alleen met de week
twee notatie die we geïntroduceerd,

338
00:15:22,030 --> 00:15:23,730
van vierkante haken met een aantal binnen?

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

340
00:15:25,160 --> 00:15:27,260
Nou, je hebt zes
nummers in deze vakken.

341
00:15:27,260 --> 00:15:28,530
Wat zou je instinct zijn?

342
00:15:28,530 --> 00:15:29,973
Waar zou je het wilt zetten?

343
00:15:29,973 --> 00:15:30,860
>> PUBLIEK: [onverstaanbaar]

344
00:15:30,860 --> 00:15:31,315
>> DAVID J. MALAN: Sorry?

345
00:15:31,315 --> 00:15:32,380
>> PUBLIEK: Zet het op het einde.

346
00:15:32,380 --> 00:15:33,796
>> DAVID J. MALAN: Zet het op het einde.

347
00:15:33,796 --> 00:15:35,880
Dus naar rechts,
buiten dit vak.

348
00:15:35,880 --> 00:15:38,710
Dat zou leuk zijn, maar het
blijkt dat je dat niet kan doen.

349
00:15:38,710 --> 00:15:41,350
Want als je niet hebt gevraagd
dit stuk geheugen,

350
00:15:41,350 --> 00:15:44,490
het zou kunnen zijn door het toeval dat deze
wordt gebruikt door een andere variabele

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

352
00:15:45,030 --> 00:15:49,210
Denk terug een week of zo toen we gelegd
uit Zamyla en Davin en Gabe's namen

353
00:15:49,210 --> 00:15:49,930
in het geheugen.

354
00:15:49,930 --> 00:15:51,638
Ze waren letterlijk
rug aan rug aan rug.

355
00:15:51,638 --> 00:15:53,550
Dat kunnen wij ook niet per se
vertrouwen dat wat de

356
00:15:53,550 --> 00:15:55,800
hier is beschikbaar voor mij om te gebruiken.

357
00:15:55,800 --> 00:15:56,990
>> Dus wat zou je doen?

358
00:15:56,990 --> 00:16:00,282
Nou, als je eenmaal het realiseren
moet een array van grootte zeven,

359
00:16:00,282 --> 00:16:02,490
kon je gewoon zorgen voor een
waaier van grootte zeven gebruik dan

360
00:16:02,490 --> 00:16:05,950
een lus of een while loop,
kopiëren naar de nieuwe matrix,

361
00:16:05,950 --> 00:16:09,680
en dan een of andere manier gewoon te ontdoen van
deze array of gewoon stoppen met het gebruik.

362
00:16:09,680 --> 00:16:12,130
Maar dat is niet bijzonder efficiënt.

363
00:16:12,130 --> 00:16:15,340
Kortom, arrays niet laten
u dynamisch wijzigen.

364
00:16:15,340 --> 00:16:17,900
>> Dus aan de ene kant krijg je
random access, die is geweldig.

365
00:16:17,900 --> 00:16:20,108
Omdat het laat ons dingen doen
als verdeel en heers,

366
00:16:20,108 --> 00:16:23,100
binary search, die we hebben
sprak over op het scherm hier.

367
00:16:23,100 --> 00:16:24,950
Maar u zelf te schilderen in een hoek.

368
00:16:24,950 --> 00:16:27,810
Zodra je raken
het einde van de array,

369
00:16:27,810 --> 00:16:29,980
je moet een zeer doen
dure operatie

370
00:16:29,980 --> 00:16:33,910
of schrijf er een hele hoop code
om nu te gaan met dat probleem.

371
00:16:33,910 --> 00:16:36,680
>> Dus wat als we in plaats daarvan hadden
zoiets als een lijst,

372
00:16:36,680 --> 00:16:38,820
of een gekoppelde lijst name?

373
00:16:38,820 --> 00:16:41,930
Wat als in plaats van het hebben van
rechthoeken back to back to back,

374
00:16:41,930 --> 00:16:45,730
we rechthoeken die iets reactie
beetje speelruimte tussen hen?

375
00:16:45,730 --> 00:16:49,670
En ook al heb ik dit getekend
foto of aangepast deze foto

376
00:16:49,670 --> 00:16:54,696
ve van de teksten hier terug te
rug aan rug zeer ordelijk, in werkelijkheid,

377
00:16:54,696 --> 00:16:56,820
een van deze rechthoeken
kan hier in het geheugen zijn.

378
00:16:56,820 --> 00:16:58,028
Een van hen kon hier te worden weergegeven.

379
00:16:58,028 --> 00:17:00,420
Een van hen kon hier up te zijn,
hier, enzovoort.

380
00:17:00,420 --> 00:17:02,910
>> Maar wat als we trokken,
in dit geval pijlen

381
00:17:02,910 --> 00:17:05,650
dat een of andere manier verwijzen deze
rechthoeken bij elkaar?

382
00:17:05,650 --> 00:17:08,170
Inderdaad, we hebben een technisch gezien
incarnatie van een pijl.

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

384
00:17:09,839 --> 00:17:13,710
Wat hebben we in de afgelopen
dagen dat, onder de motorkap,

385
00:17:13,710 --> 00:17:15,210
representeert een pijl?

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

387
00:17:16,290 --> 00:17:17,349
Een wijzer, toch?

388
00:17:17,349 --> 00:17:19,780
>> Dus wat als, in plaats van
alleen het opslaan van de nummers,

389
00:17:19,780 --> 00:17:23,130
zoals 9, 17, 22, 26, 34,
wat als we niet opgeslagen

390
00:17:23,130 --> 00:17:27,079
slechts enkele maar een pointer
naast elk dergelijk nummer?

391
00:17:27,079 --> 00:17:30,690
Zodat veel als je een zou rijgen
naald door een hele hoop stof,

392
00:17:30,690 --> 00:17:32,950
een of andere manier koppelverkoop dingen
samen, eveneens kan

393
00:17:32,950 --> 00:17:35,550
we met pointers, zoals
geïncarneerd door pijlen hier,

394
00:17:35,550 --> 00:17:38,550
soort bij elkaar te weven
deze individuele rechthoeken

395
00:17:38,550 --> 00:17:41,780
door het effectief gebruik van een pointer
naast elk nummer dat

396
00:17:41,780 --> 00:17:46,065
wijst op een aantal volgende nummer, dat
wijst op zijn beurt een volgende nummer?

397
00:17:46,065 --> 00:17:47,940
Dus in andere woorden, wat
als we eigenlijk wilden

398
00:17:47,940 --> 00:17:49,820
om iets als dit te implementeren?

399
00:17:49,820 --> 00:17:53,610
Wel Helaas deze rechthoeken,
ten minste een met 9, 17, 22,

400
00:17:53,610 --> 00:17:57,040
enzovoort, die niet langer
mooie pleinen met enkele nummers.

401
00:17:57,040 --> 00:17:59,960
De bodem, rechthoek
9 hieronder bijvoorbeeld

402
00:17:59,960 --> 00:18:04,330
vertegenwoordigt wat moet
een pointer, 32 bits.

403
00:18:04,330 --> 00:18:09,460
Nu, ik ben nog niet op de hoogte van elk type data
in C, dat geeft je niet alleen een int

404
00:18:09,460 --> 00:18:11,630
maar een pointer geheel.

405
00:18:11,630 --> 00:18:15,020
>> Dus wat is de oplossing als we willen
om ons eigen antwoord op deze uitvinden?

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

407
00:18:15,760 --> 00:18:16,640
>> PUBLIEK: [onverstaanbaar]

408
00:18:16,640 --> 00:18:17,360
>> DAVID J. MALAN: Wat is dat?

409
00:18:17,360 --> 00:18:17,880
>> PUBLIEK: Nieuwe structuur.

410
00:18:17,880 --> 00:18:19,590
>> DAVID J. MALAN: Ja, dus waarom
gaan we niet een nieuwe structuur,

411
00:18:19,590 --> 00:18:20,920
of C, een struct?

412
00:18:20,920 --> 00:18:25,990
We hebben eerder gezien structuren, zo kort,
waar we mee met een student structuur

413
00:18:25,990 --> 00:18:27,780
als deze, die een naam en een huis had.

414
00:18:27,780 --> 00:18:31,980
In Pset 3 breakout u gebruik gemaakt van een geheel
stelletje structs-- GRect en GOvals

415
00:18:31,980 --> 00:18:34,810
dat Stanford gemaakt om
cluster informatie bij elkaar.

416
00:18:34,810 --> 00:18:38,580
Dus wat als we dit zelfde idee van
de keywords "typedef" en "structuur"

417
00:18:38,580 --> 00:18:42,890
en dan nog wat student-specifieke dingen,
en evolueren deze in de volgende:

418
00:18:42,890 --> 00:18:46,210
typedef struct node-- en knooppunt
slechts een zeer generiek computer science

419
00:18:46,210 --> 00:18:49,980
term iets in een gegevensstructuur,
een houder in een gegevensstructuur.

420
00:18:49,980 --> 00:18:53,900
Een knooppunt Ik claim zal hebben
een int n, helemaal recht door zee,

421
00:18:53,900 --> 00:18:58,810
en dan een beetje meer cryptisch,
deze tweede lijn, struct knoop * volgende.

422
00:18:58,810 --> 00:19:01,300
Maar in minder technische termen,
wat dat tweede regel

423
00:19:01,300 --> 00:19:02,980
van code binnen de accolades?

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

425
00:19:03,737 --> 00:19:04,851
>> PUBLIEK: [onverstaanbaar]

426
00:19:04,851 --> 00:19:06,600
DAVID J. MALAN: A
pointer naar een ander knooppunt.

427
00:19:06,600 --> 00:19:09,910
Dus inderdaad, de syntax een beetje cryptisch.

428
00:19:09,910 --> 00:19:13,250
Maar als je het letterlijk leest,
naast de naam van een variabele.

429
00:19:13,250 --> 00:19:14,410
Wat is het gegevenstype?

430
00:19:14,410 --> 00:19:18,206
Het is een beetje verbose deze tijd,
maar het is van het type struct knoop *.

431
00:19:18,206 --> 00:19:22,960
Elke keer dat we iets ster gezien, dat
betekent dat het een pointer naar dat soort gegevens.

432
00:19:22,960 --> 00:19:26,810
Dus de volgende is blijkbaar een
pointer naar een struct knoop.

433
00:19:26,810 --> 00:19:28,310
>> Nu, wat is een struct knoop?

434
00:19:28,310 --> 00:19:31,044
Nou, let zie je die
Dezelfde woorden rechtsboven.

435
00:19:31,044 --> 00:19:33,960
En inderdaad, je ziet ook het woord
"Knooppunt" hier beneden in de linkerbenedenhoek.

436
00:19:33,960 --> 00:19:35,640
En dit is eigenlijk gewoon een gemak.

437
00:19:35,640 --> 00:19:39,930
Merk op dat in onze student definitie
daar is het woord "student" slechts een keer.

438
00:19:39,930 --> 00:19:42,510
En dat komt omdat een student
object was niet zichzelf verwijst.

439
00:19:42,510 --> 00:19:45,340
Er is niets binnenkant van een student
dat moet verwijzen naar een andere student,

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

441
00:19:45,610 --> 00:19:47,630
Dat zou een soort van zijn
raar in de echte wereld.

442
00:19:47,630 --> 00:19:50,880
>> Maar met een knooppunt in een gekoppelde
lijst, we willen wel een knooppunt

443
00:19:50,880 --> 00:19:53,970
te zijn referentiële een soortgelijk voorwerp.

444
00:19:53,970 --> 00:19:57,900
En zo ziet de verandering is hier niet
gewoon wat er binnen de accolades.

445
00:19:57,900 --> 00:20:00,800
Maar wij voegen het woord "knooppunt"
boven en

446
00:20:00,800 --> 00:20:02,930
toe te voegen aan de bodem
in plaats van "student."

447
00:20:02,930 --> 00:20:06,000
En dit is slechts een technisch detail
zo dat, nogmaals, je datastructuur

448
00:20:06,000 --> 00:20:11,380
kan zelf-referentiële, zodat een
knooppunt kan wijzen aan een andere knoop.

449
00:20:11,380 --> 00:20:13,840
>> Dus wat is dit uiteindelijk
gaat betekenen voor ons?

450
00:20:13,840 --> 00:20:17,560
Nou ja, een, dit spul binnen
is de inhoud van onze knooppunt.

451
00:20:17,560 --> 00:20:19,360
Dit ding hier,
rechtsboven, is gewoon zo

452
00:20:19,360 --> 00:20:20,860
dat, opnieuw, kunnen we verwijzen naar onszelf.

453
00:20:20,860 --> 00:20:23,401
En dan de buitenste spul,
ook al is het knooppunt is een nieuwe term,

454
00:20:23,401 --> 00:20:25,500
misschien, het is nog steeds de
hetzelfde als student en wat

455
00:20:25,500 --> 00:20:27,520
was onder de motorkap in de SPL.

456
00:20:27,520 --> 00:20:31,095
>> Dus als we wilden nu beginnen
uitvoering van deze gelinkte lijst,

457
00:20:31,095 --> 00:20:33,220
hoe kunnen we vertalen
iets als dit te coderen?

458
00:20:33,220 --> 00:20:35,350
Nou, laten we zien enkel een
voorbeeld van een programma dat

459
00:20:35,350 --> 00:20:36,840
eigenlijk maakt gebruik van een gelinkte lijst.

460
00:20:36,840 --> 00:20:40,870
Onder de huidige verdeelsleutel
is een programma genaamd Lijst Nul.

461
00:20:40,870 --> 00:20:44,980
En als ik dit run heb ik een super
eenvoudige GUI, Graphical User Interface,

462
00:20:44,980 --> 00:20:46,460
maar het is echt gewoon printf.

463
00:20:46,460 --> 00:20:50,930
En nu heb ik mezelf een paar menu gegeven
options-- Delete, Insert, Zoeken,

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

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

466
00:20:52,630 --> 00:20:55,970
Dit zijn slechts gemeenschappelijke operaties op een
datastructuur die bekend staat als een link lijst.

467
00:20:55,970 --> 00:20:58,409
>> Nu, Verwijderen gaat
een nummer uit de lijst te verwijderen.

468
00:20:58,409 --> 00:21:00,200
Invoegen gaat voegen
een nummer aan de lijst.

469
00:21:00,200 --> 00:21:02,181
Zoeken is gaan kijken
voor nummer in de lijst.

470
00:21:02,181 --> 00:21:04,930
En traverse is gewoon een mooie manier
van te zeggen, loop door de lijst,

471
00:21:04,930 --> 00:21:06,245
print het uit, maar dat is het.

472
00:21:06,245 --> 00:21:07,720
Doe het niet veranderen in any way.

473
00:21:07,720 --> 00:21:08,570
>> Dus laten we dit proberen.

474
00:21:08,570 --> 00:21:10,160
Laten we verder gaan en type 2.

475
00:21:10,160 --> 00:21:12,710
En dan ga ik
nummer, zeggen 9.

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

477
00:21:13,620 --> 00:21:17,480
En nu mijn programma is gewoon
geprogrammeerd zeggen lijst is nu 9.

478
00:21:17,480 --> 00:21:20,190
Nu, als ik ga je gang en
denk opnieuw invoegen, laat

479
00:21:20,190 --> 00:21:23,680
mij ga je gang en uit te zoomen en typ in 17.

480
00:21:23,680 --> 00:21:25,770
Nu is mijn lijst is 9, dan 17.

481
00:21:25,770 --> 00:21:27,750
Als ik weer in te voegen, laten we slaan een.

482
00:21:27,750 --> 00:21:32,400
In plaats van 22, zoals in de foto we hebben
gekeken naar hier, laat me springen vooruit

483
00:21:32,400 --> 00:21:34,630
en plaats 26 volgende.

484
00:21:34,630 --> 00:21:36,230
Dus ik ga om te typen 26.

485
00:21:36,230 --> 00:21:37,755
De lijst is als ik verwacht.

486
00:21:37,755 --> 00:21:40,630
Maar nu, alleen maar om te zien of deze code
gaat om flexibel te zijn, laat me nu

487
00:21:40,630 --> 00:21:43,520
type 22, dat ten minste
conceptueel, als we

488
00:21:43,520 --> 00:21:46,520
Het houden van dit opgelost, dat is inderdaad
gaat nog een doelpunt op dit moment zijn,

489
00:21:46,520 --> 00:21:48,690
moet gaan tussen de 17 en 26.

490
00:21:48,690 --> 00:21:50,270
Dus ik druk op Enter.

491
00:21:50,270 --> 00:21:51,380
Inderdaad, dat werkt.

492
00:21:51,380 --> 00:21:54,950
En dus nu laat ik steek de
laatste, per de foto, 34.

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

494
00:21:55,450 --> 00:21:58,980
Dus voor nu laat ik bepalen dat
Verwijderen en Traverse en zoeken te doen,

495
00:21:58,980 --> 00:21:59,760
in feite werken.

496
00:21:59,760 --> 00:22:04,180
In feite, als ik lopen zoeken, laten we
zoeken naar het nummer 22, Enter.

497
00:22:04,180 --> 00:22:05,010
Het vond 22.

498
00:22:05,010 --> 00:22:07,580
Dus dat is wat dit
programma Lijst Nul doet.

499
00:22:07,580 --> 00:22:10,230
>> Maar wat er werkelijk gaande is
Op dat implementeert dit?

500
00:22:10,230 --> 00:22:14,530
Nou, ten eerste ik zou kunnen hebben, en inderdaad
Ik heb wel een bestand genaamd list0.h.

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

502
00:22:16,540 --> 00:22:20,690
En ergens is er dit
lijn, typedef, struct knoop,

503
00:22:20,690 --> 00:22:24,850
dan heb ik mijn accolades, int n, en
dan struct-- wat was de definitie?

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

505
00:22:26,530 --> 00:22:28,545
Struct knooppunt volgende.

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

507
00:22:29,920 --> 00:22:31,045
Dus moeten we de ster.

508
00:22:31,045 --> 00:22:33,420
Nu technisch gezien komen we in
de gewoonte om hier tekenen het.

509
00:22:33,420 --> 00:22:35,670
Je zou leerboeken zien en
keer gevonden doe het daar.

510
00:22:35,670 --> 00:22:36,660
Het is functioneel equivalent.

511
00:22:36,660 --> 00:22:37,980
In feite is dit wat typischer.

512
00:22:37,980 --> 00:22:40,563
Maar ik zal in overeenstemming met wat zijn
we hebben de laatste tijd en doe dit.

513
00:22:40,563 --> 00:22:42,350
En dan tot slot, ik ga dit doen.

514
00:22:42,350 --> 00:22:45,550
>> Dus in een header file
ergens, in list0.h

515
00:22:45,550 --> 00:22:49,200
vandaag de dag is dit struct definitie,
en misschien nog enkele andere dingen.

516
00:22:49,200 --> 00:22:52,580
Ondertussen in list0c er
gaan een paar dingen zijn.

517
00:22:52,580 --> 00:22:54,740
Maar we gaan gewoon
starten en deze niet af te maken.

518
00:22:54,740 --> 00:22:59,690
List0.h is een bestand dat ik wil
op te nemen in mijn C-bestand.

519
00:22:59,690 --> 00:23:03,910
En dan op een gegeven moment ben ik
gaat int hebben, belangrijkste, ongeldig maken.

520
00:23:03,910 --> 00:23:06,530
En dan ga ik
hebben een aantal te-doen is hier.

521
00:23:06,530 --> 00:23:10,620
Ik ga ook een hebben
prototype, zoals leegte, zoeken, int,

522
00:23:10,620 --> 00:23:13,610
n, waarvan het doel in het leven is
om te zoeken naar een element.

523
00:23:13,610 --> 00:23:18,310
En dan hier beneden Ik claim in
de huidige code, leegte, zoeken, int, n,

524
00:23:18,310 --> 00:23:21,020
geen komma, maar open accolades.

525
00:23:21,020 --> 00:23:25,049
En nu wil ik een of andere manier te zoeken
Een element in deze lijst.

526
00:23:25,049 --> 00:23:27,340
Maar we hebben niet genoeg
informatie op het scherm nog niet.

527
00:23:27,340 --> 00:23:29,800
Ik heb eigenlijk niet
vertegenwoordigde de lijst zelf.

528
00:23:29,800 --> 00:23:33,070
Dus een manier waarop we kunnen implementeren
een gekoppelde lijst een programma

529
00:23:33,070 --> 00:23:37,520
is wil ik soort van om iets te doen
zoals verklaren gelinkte lijst hierboven.

530
00:23:37,520 --> 00:23:40,520
Voor de eenvoud ga ik maken
deze wereldwijde, hoewel in het algemeen hebben we

531
00:23:40,520 --> 00:23:41,645
moet dit niet te veel doen.

532
00:23:41,645 --> 00:23:43,260
Maar dit voorbeeld vereenvoudigd.

533
00:23:43,260 --> 00:23:45,890
Dus ik wil verklaren
een gekoppelde hier om de lijst up.

534
00:23:45,890 --> 00:23:47,010
Nu, hoe kan ik dat doen?

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

536
00:23:48,810 --> 00:23:50,750
>> Hier is de foto van een gelinkte lijst.

537
00:23:50,750 --> 00:23:53,030
En ik niet echt
momenteel weten hoe

538
00:23:53,030 --> 00:23:56,710
Ik ga om te gaan over wat neerkomt
zo veel dingen met slechts een

539
00:23:56,710 --> 00:23:58,040
variabele in het geheugen.

540
00:23:58,040 --> 00:23:59,160
Maar denk terug een moment.

541
00:23:59,160 --> 00:24:00,830
Al die tijd die we hebben gehad
strings, die we vervolgens

542
00:24:00,830 --> 00:24:02,913
geopenbaard aan arrays zijn van
personages, die we vervolgens

543
00:24:02,913 --> 00:24:05,740
geopenbaard aan slechts een pointer
om het eerste teken

544
00:24:05,740 --> 00:24:08,890
in een array karakters
dat is beëindigd met null.

545
00:24:08,890 --> 00:24:13,530
Dus tegen die logica en daardoor
foto soort van zaaien je gedachten,

546
00:24:13,530 --> 00:24:17,964
wat moeten we eigenlijk schrijven in ons
code om een ​​gekoppelde lijst vertegenwoordigen?

547
00:24:17,964 --> 00:24:21,130
Hoeveel van deze informatie hebben we nodig
vast te leggen in de C-code, zou je dan zeggen?

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
>> PUBLIEK: We hebben een pointer naar een knooppunt.

551
00:24:24,738 --> 00:24:26,237
DAVID J. MALAN: Een pointer naar een knooppunt.

552
00:24:26,237 --> 00:24:29,320
Vooral dat knooppunt zou je
instincten zijn om een ​​pointer te houden?

553
00:24:29,320 --> 00:24:30,026
>> Publiek: Het eerste knooppunt.

554
00:24:30,026 --> 00:24:31,942
>> DAVID J. MALAN: Ja,
waarschijnlijk gewoon de eerste.

555
00:24:31,942 --> 00:24:34,030
En merk op, de eerste
knooppunt een andere vorm.

556
00:24:34,030 --> 00:24:37,690
Het is slechts de helft van de grootte van de structuur,
omdat het immers maar een pointer.

557
00:24:37,690 --> 00:24:44,650
Dus wat je wel kunt doen is te verklaren
een gelinkte lijst te zijn van het type knooppunt *.

558
00:24:44,650 --> 00:24:47,780
En laten we eerst het noemen
en initialiseren op nul.

559
00:24:47,780 --> 00:24:49,910
Dus null, nogmaals, is komen
in de foto hier.

560
00:24:49,910 --> 00:24:53,620
Niet alleen wordt null gebruikt als als een speciale
return waarde voor dingen als getString

561
00:24:53,620 --> 00:24:57,770
en malloc, null is ook de nul
pointer, het ontbreken van een pointer,

562
00:24:57,770 --> 00:24:58,430
als je wil.

563
00:24:58,430 --> 00:25:00,309
Het betekent gewoon dat er niets is nog hier.

564
00:25:00,309 --> 00:25:02,100
Nu eerst, ik had kunnen
noemde dit alles.

565
00:25:02,100 --> 00:25:04,200
Ik kon het hebben genoemd "lijst"
of een aantal andere zaken.

566
00:25:04,200 --> 00:25:06,960
Maar ik doe het bellen "eerste", zodat
deze lijn staat met deze foto.

567
00:25:06,960 --> 00:25:10,280
Dus net als een string kan worden weergegeven
met het adres van de eerste byte,

568
00:25:10,280 --> 00:25:11,280
zo kan een gelinkte lijst.

569
00:25:11,280 --> 00:25:13,480
En we zullen zien andere data
structuren worden vertegenwoordigd

570
00:25:13,480 --> 00:25:16,700
met slechts een wijzer,
een 32-bits pijl, wijzend

571
00:25:16,700 --> 00:25:18,740
op het eerste knooppunt in de structuur.

572
00:25:18,740 --> 00:25:20,340
>> Maar laten we nu anticiperen op een probleem.

573
00:25:20,340 --> 00:25:23,230
Als ik alleen herinneren
in mijn programma het adres

574
00:25:23,230 --> 00:25:27,220
van het eerste knooppunt, de eerste
rechthoek in deze datastructuur,

575
00:25:27,220 --> 00:25:31,760
wat had beter de zaak over de te
uitvoering van de rest van mijn lijst?

576
00:25:31,760 --> 00:25:35,820
Wat is een belangrijk detail dat gaat
te zorgen dat dit echt werkt?

577
00:25:35,820 --> 00:25:39,250
En met "echt werkt" Ik
betekenen, zoals een koord,

578
00:25:39,250 --> 00:25:42,180
laat ons gaan van het eerste teken
in Davin's naam aan de tweede,

579
00:25:42,180 --> 00:25:44,755
de derde, de
vierde, aan het einde,

580
00:25:44,755 --> 00:25:47,880
hoe weten we wanneer we aan het eind
van een gelinkte lijst die er zo uitziet?

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

582
00:25:50,035 --> 00:25:50,660
Wanneer het is null.

583
00:25:50,660 --> 00:25:53,640
En ik heb dit soort als vertegenwoordigd
zoals een elektrisch ingenieur macht,

584
00:25:53,640 --> 00:25:56,420
met de kleine aarding
symbool, van soorten.

585
00:25:56,420 --> 00:25:58,246
Maar dat betekent nul in dit geval.

586
00:25:58,246 --> 00:26:00,370
U kunt het tekenen elk nummer
manieren, maar deze auteur

587
00:26:00,370 --> 00:26:02,800
is er gebeurd met dit symbool gebruiken hier.

588
00:26:02,800 --> 00:26:06,260
>> Zolang we rijgen
al deze knooppunten samen,

589
00:26:06,260 --> 00:26:08,600
alleen herinneren waar
de eerste is, zolang

590
00:26:08,600 --> 00:26:11,760
als we een speciaal symbool op
het laatste knooppunt in de lijst,

591
00:26:11,760 --> 00:26:15,130
en we zullen gebruiken null, want dat is
wat we tot onze beschikking,

592
00:26:15,130 --> 00:26:16,480
deze lijst compleet is.

593
00:26:16,480 --> 00:26:20,190
En al is het maar ik geef je een pointer naar
het eerste element, u, de programmeur,

594
00:26:20,190 --> 00:26:22,486
zeker in de rest ervan.

595
00:26:22,486 --> 00:26:24,360
Maar laten we laat uw gedachten
dwalen een beetje,

596
00:26:24,360 --> 00:26:26,140
als ze niet al
heel wandered-- wat is

597
00:26:26,140 --> 00:26:28,723
naar de looptijd zijn van
iets in deze lijst vinden?

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

599
00:26:30,450 --> 00:26:33,470
Verdomme, het is big O van n,
dat is niet slecht, in alle eerlijkheid.

600
00:26:33,470 --> 00:26:34,800
Maar het is lineair.

601
00:26:34,800 --> 00:26:37,980
We hebben op wat functie gegeven
arrays door meer te bewegen

602
00:26:37,980 --> 00:26:43,130
in de richting van deze foto van dynamisch
verweven en verbonden knopen?

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

604
00:26:44,970 --> 00:26:46,687
We hebben opgegeven random access.

605
00:26:46,687 --> 00:26:48,770
Een array is leuk omdat
mathematisch alles

606
00:26:48,770 --> 00:26:50,340
is rug aan rug aan rug aan rug.

607
00:26:50,340 --> 00:26:52,370
Hoewel deze foto
ziet er mooi, en zelfs

608
00:26:52,370 --> 00:26:55,830
maar het lijkt erop dat deze knooppunten
zijn mooi afstand van elkaar, in werkelijkheid

609
00:26:55,830 --> 00:26:56,830
ze kan overal zijn.

610
00:26:56,830 --> 00:27:01,590
OX1, Ox50, Ox123, Ox99, deze
knooppunten kan overal zijn.

611
00:27:01,590 --> 00:27:05,960
Omdat malloc doet geheugen toewijzen
van de hoop, maar overal in de heap.

612
00:27:05,960 --> 00:27:09,080
Je hoeft niet per se weten dat het
ga terug naar back to back.

613
00:27:09,080 --> 00:27:12,460
En dus is deze foto in werkelijkheid is
niet van plan heel dit mooi zijn.

614
00:27:12,460 --> 00:27:16,140
>> Dus het gaat om een ​​beetje van te nemen
werken om deze functie uit te voeren.

615
00:27:16,140 --> 00:27:17,880
Dus laten we zoekopdracht uit te voeren nu.

616
00:27:17,880 --> 00:27:20,250
En we zien wel een soort van een
slimme manier om dit te doen.

617
00:27:20,250 --> 00:27:24,660
Dus als ik een zoekfunctie en
Ik kreeg een variabele, integer n

618
00:27:24,660 --> 00:27:28,490
te zoeken, ik moet het weten
nieuwe syntax voor het kijken van binnen

619
00:27:28,490 --> 00:27:32,400
of een structuur die
wees aan n vinden.

620
00:27:32,400 --> 00:27:33,210
Dus laten we dit doen.

621
00:27:33,210 --> 00:27:36,030
>> Dus eerst ga ik om te gaan
vooruit en verklaren een knooppunt *.

622
00:27:36,030 --> 00:27:39,400
En ik ga het ook noemen
wijzer, gewoon volgens afspraak.

623
00:27:39,400 --> 00:27:41,710
En ik ga het initialiseren naar eerste.

624
00:27:41,710 --> 00:27:43,770
En nu kan ik dit doen
in een aantal manieren.

625
00:27:43,770 --> 00:27:45,436
Maar ik ga naar een gemeenschappelijke aanpak.

626
00:27:45,436 --> 00:27:50,180
Hoewel pointer is niet gelijk
null, en dat is geldig syntax.

627
00:27:50,180 --> 00:27:54,550
En het betekent gewoon het volgende doen, dus
Zolang je niet te wijzen op niets.

628
00:27:54,550 --> 00:27:55,800
Wat wil ik doen?

629
00:27:55,800 --> 00:28:01,939
>> Als wijzer dot n, laat me terug te komen
om dat, gelijk aan equals-- wat?

630
00:28:01,939 --> 00:28:03,105
Welke waarde moet ik naar zoeken?

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

632
00:28:04,920 --> 00:28:06,590
De werkelijke n dat werd aangenomen in.

633
00:28:06,590 --> 00:28:09,020
Dus hier is een andere functie
van C en vele talen.

634
00:28:09,020 --> 00:28:13,705
Hoewel de structuur die knooppunt
n heeft een waarde, volledig gewettigd

635
00:28:13,705 --> 00:28:17,530
ook een lokaal argument
of variabele genoemd n.

636
00:28:17,530 --> 00:28:20,085
Want ook wij, met
menselijk oog kan onderscheiden

637
00:28:20,085 --> 00:28:22,087
dat dit n vermoedelijk
verschillend van deze n.

638
00:28:22,087 --> 00:28:23,420
Omdat de syntax is anders.

639
00:28:23,420 --> 00:28:26,211
Je hebt een punt en een pointer gekregen,
terwijl deze heeft niet zoiets.

640
00:28:26,211 --> 00:28:27,290
Dus dit is OK.

641
00:28:27,290 --> 00:28:29,120
Dat is OK ze dezelfde dingen te noemen.

642
00:28:29,120 --> 00:28:32,380
>> Als ik u dit vinden, ben ik
gaat te willen om iets te doen

643
00:28:32,380 --> 00:28:35,000
zoals aankondigen dat we gevonden n.

644
00:28:35,000 --> 00:28:37,930
En we laten dat als een
reageren of pseudo-code.

645
00:28:37,930 --> 00:28:40,190
Anders, en hier is de
interessante deel, wat

646
00:28:40,190 --> 00:28:47,320
doen wat ik wil doen als het huidige knooppunt
is niet met n dat ik de zorg over?

647
00:28:47,320 --> 00:28:50,700
Hoe krijg ik het volgende te bereiken?

648
00:28:50,700 --> 00:28:53,710
Als mijn vinger naar de
Momenteel is PTR, en het is

649
00:28:53,710 --> 00:28:55,920
wijzend op wat
eerste wijst op,

650
00:28:55,920 --> 00:28:59,290
hoe kan ik mijn vinger bewegen
naar de volgende knoop in code?

651
00:28:59,290 --> 00:29:01,915
Nou ja, wat is de breadcrumb we
zal volgen in dit geval?

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

653
00:29:03,464 --> 00:29:04,380
PUBLIEK: [onverstaanbaar].

654
00:29:04,380 --> 00:29:05,630
DAVID J. MALAN: Ja, dus naast.

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

656
00:29:06,640 --> 00:29:09,824
Dus als ik ga terug naar mijn
code hier, inderdaad, ik ben

657
00:29:09,824 --> 00:29:12,990
ga je gang gaan en zeggen wijzer, die
is slechts een tijdelijke variable-- het is

658
00:29:12,990 --> 00:29:15,320
een rare naam, ptr, maar
het is net als temp--

659
00:29:15,320 --> 00:29:19,234
Ik ga aanwijzer instellen
gelijk aan wat wijzer is--

660
00:29:19,234 --> 00:29:22,150
en nogmaals, dit gaat om een ​​te zijn
kleine buggy voor een moment-- stip.

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

662
00:29:23,551 --> 00:29:26,550
Met andere woorden, ga ik neem mijn
vinger die is te wijzen op dit knooppunt

663
00:29:26,550 --> 00:29:31,247
hier en ik ga zeggen, weet je
wat, neem een ​​kijkje op het volgende veld

664
00:29:31,247 --> 00:29:33,330
en beweeg uw vinger naar
wat het ook is wijzend op.

665
00:29:33,330 --> 00:29:35,163
En dit gaat
herhalen, herhalen, herhalen.

666
00:29:35,163 --> 00:29:37,630
Maar wanneer komt mijn vinger
stop helemaal niets doen?

667
00:29:37,630 --> 00:29:40,095
Zodra welke regel code kicks in?

668
00:29:40,095 --> 00:29:40,970
PUBLIEK: [onverstaanbaar]

669
00:29:40,970 --> 00:29:43,060
DAVID J. MALAN: Als punt terwijl
pointer is niet gelijk aan nul.

670
00:29:43,060 --> 00:29:44,900
Op een gegeven moment mijn vinger's
gaat worden wijzend op null

671
00:29:44,900 --> 00:29:47,070
en ik ga om te beseffen
dat is het einde van deze lijst.

672
00:29:47,070 --> 00:29:48,910
Nu is dit een beetje
leugentje om bestwil voor eenvoud.

673
00:29:48,910 --> 00:29:51,580
Het blijkt dat, hoewel we
net geleerd dit dot notatie

674
00:29:51,580 --> 00:29:55,220
voor structuren, wijzer is geen structuur.

675
00:29:55,220 --> 00:29:56,580
ptr is wat?

676
00:29:56,580 --> 00:29:58,350
Gewoon om meer nitpicky zijn.

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

678
00:29:59,720 --> 00:30:01,360
Het is een pointer naar een knooppunt.

679
00:30:01,360 --> 00:30:03,120
Het is niet een node zelf.

680
00:30:03,120 --> 00:30:06,650
Als ik had geen ster hier, wijzer
absolutely-- het is een knooppunt.

681
00:30:06,650 --> 00:30:08,650
Dit is net als een week
verklaring van een variabele,

682
00:30:08,650 --> 00:30:10,120
hoewel het woord "knooppunt" is nieuw.

683
00:30:10,120 --> 00:30:13,860
>> Maar zodra we de invoering van een
ster, het is nu een pointer naar een knooppunt.

684
00:30:13,860 --> 00:30:17,960
En helaas kan je niet gebruiken
de puntnotatie een pointer.

685
00:30:17,960 --> 00:30:21,070
Je moet de pijl te gebruiken
notatie, die opvallend,

686
00:30:21,070 --> 00:30:23,470
is de eerste keer dat een stuk
van syntax ziet er intuïtief.

687
00:30:23,470 --> 00:30:25,245
Dit ziet er letterlijk als een pijl.

688
00:30:25,245 --> 00:30:26,370
En dus dat is een goede zaak.

689
00:30:26,370 --> 00:30:28,995
En hier beneden letterlijk
ziet eruit als een pijl.

690
00:30:28,995 --> 00:30:31,870
Dus ik denk dat dat de la-- ik niet
denk dat ik over-plegen hier-- I

691
00:30:31,870 --> 00:30:34,120
denk dat dat de laatste nieuwe stuk
van syntax we zullen gaan zien.

692
00:30:34,120 --> 00:30:36,500
En gelukkig, het is inderdaad
wat intuïtiever.

693
00:30:36,500 --> 00:30:40,090
>> Nu, voor degenen onder u die
zou de oude manier wilt,

694
00:30:40,090 --> 00:30:42,550
kunt u nog steeds gebruik maken van de dot-notatie.

695
00:30:42,550 --> 00:30:45,380
Maar als per maandag
gesprek, we eerst

696
00:30:45,380 --> 00:30:50,530
nodig hebt om er naartoe te gaan, naar die
aan te pakken, en vervolgens toegang tot het gebied.

697
00:30:50,530 --> 00:30:51,897
Dus dit is ook correct.

698
00:30:51,897 --> 00:30:53,730
En eerlijk gezegd, dit is een
beetje pedant.

699
00:30:53,730 --> 00:30:56,530
Je bent letterlijk zeggen, dereferentie
de wijzer en ga daar.

700
00:30:56,530 --> 00:30:59,320
Grijp dan .n, het veld met de naam n.

701
00:30:59,320 --> 00:31:01,370
Maar eerlijk gezegd, niemand wil
te typen of te lezen dit.

702
00:31:01,370 --> 00:31:03,620
En zo de wereld uitgevonden
de pijl notatie die

703
00:31:03,620 --> 00:31:06,980
gelijk, identiek,
het is gewoon syntactische suiker.

704
00:31:06,980 --> 00:31:10,570
Dus een mooie manier om dit te zeggen
ziet er beter uit, of ziet er eenvoudiger.

705
00:31:10,570 --> 00:31:12,296
>> Dus nu ga ik een ander ding te doen.

706
00:31:12,296 --> 00:31:15,420
Ik ga zeggen "break" zodra ik heb
vond het zo ik niet blijven kijken naar het.

707
00:31:15,420 --> 00:31:17,620
Maar dit is de kern
van een zoekfunctie.

708
00:31:17,620 --> 00:31:21,710
Maar het is een stuk makkelijker, in de
einde, niet te lopen door de code.

709
00:31:21,710 --> 00:31:25,570
Dit is inderdaad de formele implementatie
van de zoekopdracht in de huidige verdeelsleutel.

710
00:31:25,570 --> 00:31:30,530
Ik durf te zeggen dat de insert is niet
bijzonder leuk om te lopen door

711
00:31:30,530 --> 00:31:33,180
visueel, noch is te verwijderen, zelfs
maar aan het eind van de dag

712
00:31:33,180 --> 00:31:35,460
ze neer op tamelijk
eenvoudige heuristiek.

713
00:31:35,460 --> 00:31:36,330
>> Dus laten we dit doen.

714
00:31:36,330 --> 00:31:39,250
Als u zult humor me hier, ik deed
brengen een heleboel stress ballen.

715
00:31:39,250 --> 00:31:40,620
Ik bracht een heleboel getallen.

716
00:31:40,620 --> 00:31:46,562
En konden we slechts een paar vrijwilligers
te vertegenwoordigen 9, 17, 20, 22, 29 en 34?

717
00:31:46,562 --> 00:31:48,270
Dus in wezen iedereen
wie we hier vandaag.

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

719
00:31:50,170 --> 00:31:52,760
Dat was een, twee, drie,
vier, vijf, zes personen.

720
00:31:52,760 --> 00:31:55,740
En ik ben gevraagd om gaan-- zien, geen
een aan de achterkant verhoogt hun handen.

721
00:31:55,740 --> 00:32:01,910
OK, een, twee, drie, vier,
five-- laat me laden balance-- zes.

722
00:32:01,910 --> 00:32:03,051
OK, je zes komen op maximaal.

723
00:32:03,051 --> 00:32:04,050
We zullen andere mensen nodig.

724
00:32:04,050 --> 00:32:05,460
We brachten extra stress ballen.

725
00:32:05,460 --> 00:32:08,200
En als je zou kunnen, voor
slechts een moment, lijn

726
00:32:08,200 --> 00:32:10,490
jezelf omhoog enkel
graag deze foto hier.

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

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

729
00:32:15,959 --> 00:32:17,125
Laten we eens kijken, wat is uw naam?

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

731
00:32:17,550 --> 00:32:18,800
>> DAVID J. MALAN: Andrew,
je bent nummer 9.

732
00:32:18,800 --> 00:32:19,540
Leuk je te ontmoeten.

733
00:32:19,540 --> 00:32:20,400
Hier ga je.

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

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

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

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

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

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

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

741
00:32:25,450 --> 00:32:26,400
>> Publiek: Ik ben Julia.

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

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

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

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

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

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

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

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

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

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

752
00:32:34,880 --> 00:32:37,080
Dus ga je gang en krijg 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
Heeft iemand een marker?

760
00:32:43,682 --> 00:32:44,890
PUBLIEK: Ik heb een Sharpie.

761
00:32:44,890 --> 00:32:45,660
DAVID J. MALAN: Je hebt een 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
En heeft iemand een stuk papier?

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

766
00:32:51,562 --> 00:32:52,270
Sla de lezing.

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

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

769
00:32:55,362 --> 00:32:56,320
PUBLIEK: We hebben het.

770
00:32:56,320 --> 00:32:57,600
DAVID J. MALAN: We got it?

771
00:32:57,600 --> 00:32:58,577
Oke, dank je wel.

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

773
00:33:01,380 --> 00:33:02,520
Hier gaan we.

774
00:33:02,520 --> 00:33:03,582
Was dit van u?

775
00:33:03,582 --> 00:33:04,540
Je redde net de dag.

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

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

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

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

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

781
00:33:13,360 --> 00:33:14,890
Ik verkeerd gespeld 29, maar OK.

782
00:33:14,890 --> 00:33:15,720
Ga je gang.

783
00:33:15,720 --> 00:33:18,114
Oke, ik geef je
je pen even terug.

784
00:33:18,114 --> 00:33:19,280
Dus hebben we deze mensen hier.

785
00:33:19,280 --> 00:33:20,330
Laten we eens een andere.

786
00:33:20,330 --> 00:33:23,750
Gabe, wil je spelen
het eerste element hier?

787
00:33:23,750 --> 00:33:25,705
We zullen je nodig hebt om te wijzen
bij deze fijne mensen.

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

789
00:33:26,930 --> 00:33:31,030
Dus 9, 17, 20, 22, sorteren
van 29, en dan 34.

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

791
00:33:32,160 --> 00:33:33,325
Hebben we iemand verliezen?

792
00:33:33,325 --> 00:33:33,950
Ik heb wel een 34.

793
00:33:33,950 --> 00:33:36,730
Waar did-- OK, wie wil zijn 34?

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

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

796
00:33:39,280 --> 00:33:41,220
Oke, dit zal
de moeite waard om de climax.

797
00:33:41,220 --> 00:33:41,550
Wat is je naam?

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

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

800
00:33:43,456 --> 00:33:46,810
Oke, dus hier is een
hele hoop van knooppunten.

801
00:33:46,810 --> 00:33:49,060
Ieder van jullie is
een van deze rechthoeken.

802
00:33:49,060 --> 00:33:51,930
En Gabe, het enigszins vreemd
man uit, vertegenwoordigt eerste.

803
00:33:51,930 --> 00:33:54,850
Dus zijn pointer is een beetje kleiner
op het scherm dan iedereen anders.

804
00:33:54,850 --> 00:33:58,120
En in dit geval, elk van uw linkerhand
handen gaat ofwel naar beneden wijzen,

805
00:33:58,120 --> 00:34:01,085
waardoor die null, dus
maar het ontbreken van een pointer,

806
00:34:01,085 --> 00:34:03,210
of het gaat om te wijzen
op een knooppunt naast je.

807
00:34:03,210 --> 00:34:05,440
>> Dus nu als je sieren
jezelf als het beeld

808
00:34:05,440 --> 00:34:07,585
hier, ga je gang en punt
naar elkaar, met Gabe

809
00:34:07,585 --> 00:34:11,030
in het bijzonder richten op
nummer 9 naar de lijst vertegenwoordigen.

810
00:34:11,030 --> 00:34:14,050
OK, en nummer 34, je linkerhand
moet gewoon worden wijzend op de vloer.

811
00:34:14,050 --> 00:34:15,750
>> OK, dus dit is de gelinkte lijst.

812
00:34:15,750 --> 00:34:17,580
Dit is het scenario betrokken.

813
00:34:17,580 --> 00:34:20,210
En inderdaad, dit is representatief
een categorie problemen

814
00:34:20,210 --> 00:34:21,929
dat je zou kunnen proberen op te lossen met een code.

815
00:34:21,929 --> 00:34:25,020
Je wilt uiteindelijk voegen
Een nieuw element in de lijst.

816
00:34:25,020 --> 00:34:27,494
In dit geval gaan we
probeer het plaatsen van de nummer 55.

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

818
00:34:28,500 --> 00:34:30,860
Maar er gaat worden
verschillende gevallen te overwegen.

819
00:34:30,860 --> 00:34:34,409
En inderdaad, dit gaat om een ​​te zijn
van de big-picture afhaalrestaurants hier is,

820
00:34:34,409 --> 00:34:35,659
wat zijn de verschillende gevallen.

821
00:34:35,659 --> 00:34:39,120
Wat zijn de verschillende als voorwaarden of
takken die het programma zou kunnen hebben?

822
00:34:39,120 --> 00:34:42,024
>> Nou, het nummer dat u probeert te
insert, waarvan we nu weten zijn 55,

823
00:34:42,024 --> 00:34:44,650
maar als je het niet wist
van tevoren, ik durf te zeggen

824
00:34:44,650 --> 00:34:47,840
valt in ten minste drie
situaties.

825
00:34:47,840 --> 00:34:49,717
Waar zou een nieuw element zijn?

826
00:34:49,717 --> 00:34:51,050
PUBLIEK: En het einde of in het midden.

827
00:34:51,050 --> 00:34:54,150
DAVID J. MALAN: Aan het einde in
het midden of aan het begin.

828
00:34:54,150 --> 00:34:56,650
Dus ik beweren dat er op zijn minst
drie problemen die we moeten oplossen.

829
00:34:56,650 --> 00:34:58,691
Laten we kiezen wat het misschien
misschien wel de eenvoudigste

830
00:34:58,691 --> 00:35:01,090
men, wanneer het nieuwe element
behoort bij het begin.

831
00:35:01,090 --> 00:35:04,040
Dus ik ga naar code vrij hebben
zoals zoeken, wat ik net schreef.

832
00:35:04,040 --> 00:35:07,670
En ik ga PTR hebben, die
Ik zal hier vertegenwoordig met mijn vinger,

833
00:35:07,670 --> 00:35:08,370
zoals gewoonlijk.

834
00:35:08,370 --> 00:35:12,430
>> En vergeet niet, welke waarde
hebben we initialiseren ptr naar?

835
00:35:12,430 --> 00:35:15,300
Dus we geïnitialiseerd is om in eerste instantie null.

836
00:35:15,300 --> 00:35:16,410

837
00:35:16,410 --> 00:35:19,770
Maar wat hebben we gedaan toen we
binnen waren onze zoekfunctie?

838
00:35:19,770 --> 00:35:20,940

839
00:35:20,940 --> 00:35:24,870
We stellen het gelijk aan de eerste,
wat niet betekent dat dit te doen.

840
00:35:24,870 --> 00:35:25,890

841
00:35:25,890 --> 00:35:30,570
Als ik ptr gelijk aan de eerste, wat
moet mijn hand echt te wijzen op?

842
00:35:30,570 --> 00:35:31,070
Rechts.

843
00:35:31,070 --> 00:35:33,290
Dus als Gabe en ik gaan
gelijke waarden hier zijn,

844
00:35:33,290 --> 00:35:34,760
we nodig hebben om zowel punt op nummer 9.

845
00:35:34,760 --> 00:35:36,420
>> Dus dit was het begin van ons verhaal.

846
00:35:36,420 --> 00:35:38,700
En nu dit is gewoon rechttoe rechtaan,
ook al is de syntax is nieuw.

847
00:35:38,700 --> 00:35:40,580
Conceptueel is dit gewoon lineair zoeken.

848
00:35:40,580 --> 00:35:42,750
55 is gelijk aan 9?

849
00:35:42,750 --> 00:35:45,559
Of liever gezegd, laten we minder dan 9 zeggen.

850
00:35:45,559 --> 00:35:47,600
Want ik ben op zoek naar
achterhalen waar te 55 zetten.

851
00:35:47,600 --> 00:35:51,270
Minder dan 9, minder dan 17, minder
dan 20, minder dan 22, minder dan 29,

852
00:35:51,270 --> 00:35:52,510
minder dan 34, nee.

853
00:35:52,510 --> 00:35:55,080
Dus nu zijn we in het geval
een van ten minste drie.

854
00:35:55,080 --> 00:35:59,910
>> Als ik hier wil invoegen 55 over, wat
regels code nodig om geëxecuteerd?

855
00:35:59,910 --> 00:36:01,890
Hoe werkt deze foto van
mensen moeten veranderen?

856
00:36:01,890 --> 00:36:03,181
Wat doe ik met mijn linkerhand?

857
00:36:03,181 --> 00:36:04,530

858
00:36:04,530 --> 00:36:07,360
Dit moet in eerste instantie nul zijn,
want ik ben aan het einde van de lijst.

859
00:36:07,360 --> 00:36:09,318
En wat er moet gebeuren
hier samen met Peter, was het?

860
00:36:09,318 --> 00:36:10,520

861
00:36:10,520 --> 00:36:12,430
Hij is duidelijk gaat wijzen naar mij.

862
00:36:12,430 --> 00:36:15,580
Dus ik beweer dat er ten minste twee lijnen
van code in de voorbeeldcode van vandaag

863
00:36:15,580 --> 00:36:18,570
dat gaat om dit te implementeren
scenario van het toevoegen van 55 aan de staart.

864
00:36:18,570 --> 00:36:20,950
En mag ik iemand hop
up en slechts 55 voor?

865
00:36:20,950 --> 00:36:22,200
Oke, jij bent de nieuwe 55.

866
00:36:22,200 --> 00:36:23,580

867
00:36:23,580 --> 00:36:27,054
>> Dus wat nu als de volgende
scenario komt langs,

868
00:36:27,054 --> 00:36:29,720
en we willen voegen aan de
begin of het hoofd van deze lijst?

869
00:36:29,720 --> 00:36:31,100
En wat is je naam, nummer 55?

870
00:36:31,100 --> 00:36:31,420
>> PUBLIEK: Jack.

871
00:36:31,420 --> 00:36:32,295
>> DAVID J. MALAN: Jack?

872
00:36:32,295 --> 00:36:33,585
OK, leuk je te ontmoeten.

873
00:36:33,585 --> 00:36:34,210
Welkom aan boord.

874
00:36:34,210 --> 00:36:36,640
Dus nu gaan we naar
invoegen, bijvoorbeeld het getal 5.

875
00:36:36,640 --> 00:36:39,840
Hier is het tweede geval van de
drie kwamen we met voorheen.

876
00:36:39,840 --> 00:36:43,050
Dus als 5 behoort bij het begin,
laten we eens kijken hoe we dat te weten komen.

877
00:36:43,050 --> 00:36:46,310
Ik initialiseren mijn ptr
pointer naar nummer 9 weer.

878
00:36:46,310 --> 00:36:49,140
En ik realiseerde me, oh, 5 minder dan 9.

879
00:36:49,140 --> 00:36:50,880
Dus fix dit beeld voor ons.

880
00:36:50,880 --> 00:36:54,820
Wiens handen, Gabe's of David's
of-- wat is nummer 9 van de naam?

881
00:36:54,820 --> 00:36:55,740
>> PUBLIEK: Jen.

882
00:36:55,740 --> 00:36:58,406
>> DAVID J. MALAN: Jen's hands--
die van onze handen moeten veranderen?

883
00:36:58,406 --> 00:36:58,905

884
00:36:58,905 --> 00:37:00,970
OK, dus Gabe wijst naar wat nu?

885
00:37:00,970 --> 00:37:01,640
Bij mij.

886
00:37:01,640 --> 00:37:02,750
Ik ben het nieuwe knooppunt.

887
00:37:02,750 --> 00:37:04,870
Dus ik zal gewoon een soort van verhuizing
hier om het visueel te zien.

888
00:37:04,870 --> 00:37:06,435
En ondertussen wat doe ik dat punt?

889
00:37:06,435 --> 00:37:07,910

890
00:37:07,910 --> 00:37:09,020
Nog steeds waar ik wijzen.

891
00:37:09,020 --> 00:37:10,000
Dus dat is het.

892
00:37:10,000 --> 00:37:13,717
Dus gewoon echt een regel code fixes
deze specifieke kwestie, lijkt het.

893
00:37:13,717 --> 00:37:14,800
Oke, dus dat is goed.

894
00:37:14,800 --> 00:37:17,580
En kan iemand zijn placeholder voor 5?

895
00:37:17,580 --> 00:37:18,080
Kom maar naar boven.

896
00:37:18,080 --> 00:37:20,270

897
00:37:20,270 --> 00:37:21,320
We halen je de volgende keer.

898
00:37:21,320 --> 00:37:24,280
>> Oke, dus nu-- en
als een terzijde, de namen

899
00:37:24,280 --> 00:37:28,510
Ik ben niet het maken expliciet melding van het recht
nu, pred wijzer, voorganger wijzer

900
00:37:28,510 --> 00:37:31,260
en pointer, dat
alleen de namen van

901
00:37:31,260 --> 00:37:35,280
in de voorbeeldcode om de pointers of
mijn handen dat soort is te wijzen rond.

902
00:37:35,280 --> 00:37:36,060
Wat is je naam?

903
00:37:36,060 --> 00:37:36,700
>> PUBLIEK: Christine.

904
00:37:36,700 --> 00:37:37,100
>> DAVID J. MALAN: Christine.

905
00:37:37,100 --> 00:37:38,090
Welkom aan boord.

906
00:37:38,090 --> 00:37:42,180
Oke, dus laten we eens kijken nu
een iets vervelend scenario

907
00:37:42,180 --> 00:37:46,350
waarbij ik wil invoegen
zoiets 26 in deze.

908
00:37:46,350 --> 00:37:47,090
20?

909
00:37:47,090 --> 00:37:47,590
Wat?

910
00:37:47,590 --> 00:37:50,510
Deze zijn-- goed dat we hebben deze pen.

911
00:37:50,510 --> 00:37:51,955
Goed, 20.

912
00:37:51,955 --> 00:37:53,640

913
00:37:53,640 --> 00:37:57,570
Als iemand een ander stuk van kon krijgen
papier klaar, net op geval-- goed.

914
00:37:57,570 --> 00:37:58,370
Oh, interessant.

915
00:37:58,370 --> 00:37:59,760

916
00:37:59,760 --> 00:38:02,390
Nou, dit is een voorbeeld
van een lezing bug.

917
00:38:02,390 --> 00:38:03,894
OK dus wat heet je ook alweer?

918
00:38:03,894 --> 00:38:04,560
PUBLIEK: Julia.

919
00:38:04,560 --> 00:38:07,559
DAVID J. MALAN: Julia, kunt u pop
uit en doen alsof je er nooit?

920
00:38:07,559 --> 00:38:09,040
OK, dit is nooit gebeurd.

921
00:38:09,040 --> 00:38:09,680
Dank je wel.

922
00:38:09,680 --> 00:38:12,180
Dus stel dat we willen invoegen
Julia in deze gelinkte lijst.

923
00:38:12,180 --> 00:38:13,780
Zij is het getal 20.

924
00:38:13,780 --> 00:38:15,530
En natuurlijk is ze
naar behoren bij de

925
00:38:15,530 --> 00:38:17,521
begin-- nog niets aan te wijzen.

926
00:38:17,521 --> 00:38:20,020
Dus je hand kan soort zijn
beneden nul of een garbage waarde.

927
00:38:20,020 --> 00:38:21,210
Laten we zeggen de snelle verhaal.

928
00:38:21,210 --> 00:38:22,980
Ik wees naar nummer 5 dit keer.

929
00:38:22,980 --> 00:38:23,880
Dan check ik 9.

930
00:38:23,880 --> 00:38:25,130
Dan check ik 17.

931
00:38:25,130 --> 00:38:26,247
Dan check ik 22.

932
00:38:26,247 --> 00:38:27,650

933
00:38:27,650 --> 00:38:32,485
En ik realiseer me, ooh, Julia
moet gaan voor 22.

934
00:38:32,485 --> 00:38:33,580

935
00:38:33,580 --> 00:38:34,660
Dus wat moet er gebeuren?

936
00:38:34,660 --> 00:38:35,786

937
00:38:35,786 --> 00:38:36,910
Moeten wiens handen om te veranderen?

938
00:38:36,910 --> 00:38:38,360
Julia's, de mijne, of--
hoe heet je ook alweer?

939
00:38:38,360 --> 00:38:39,230
>> PUBLIEK: Christian.

940
00:38:39,230 --> 00:38:40,060
>> DAVID J. MALAN: christen of?

941
00:38:40,060 --> 00:38:40,560
>> PUBLIEK: Andy.

942
00:38:40,560 --> 00:38:40,905
>> DAVID J. MALAN: Andy.

943
00:38:40,905 --> 00:38:41,654
Christelijke of Andy?

944
00:38:41,654 --> 00:38:44,280

945
00:38:44,280 --> 00:38:45,690
Moet Andy te wijzen op?

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
Oke.

949
00:38:47,840 --> 00:38:48,960
Dus Andy, wil je wijzen op Julia?

950
00:38:48,960 --> 00:38:50,120
Maar wacht eens even.

951
00:38:50,120 --> 00:38:53,260
In het verhaal tot nu toe,
Ik ben het soort van een

952
00:38:53,260 --> 00:38:56,800
de leiding, in de zin dat
pointer is het ding dat is

953
00:38:56,800 --> 00:38:57,850
bewegen door de lijst.

954
00:38:57,850 --> 00:39:00,800
We zouden een naam voor Andy, maar
er is geen variabele genaamd Andy.

955
00:39:00,800 --> 00:39:04,320
De enige andere variabele die we hebben is
eerste, wie vertegenwoordigd door Gabe.

956
00:39:04,320 --> 00:39:07,690
>> Dus dit is eigenlijk daarom aldus
toe hebben we dit niet nodig is.

957
00:39:07,690 --> 00:39:10,846
Maar nu op het scherm is er
opnieuw te vermelden van pred pointer.

958
00:39:10,846 --> 00:39:11,970
Dus laat me explicieter.

959
00:39:11,970 --> 00:39:14,820
Als dit is wijzer, ik had beter
een beetje intelligenter

960
00:39:14,820 --> 00:39:15,950
over mijn iteratie.

961
00:39:15,950 --> 00:39:19,580
Als je het niet erg vindt dat ik het gaan door hier
weer, hier richten, hier wijzend.

962
00:39:19,580 --> 00:39:22,500
Maar laat me een pred wijzer,
voorganger wijzer, dat is

963
00:39:22,500 --> 00:39:24,740
soort te wijzen op de
element Ik was gewoon op.

964
00:39:24,740 --> 00:39:27,330
Dus als ik ga hier nu
mijn linkerhand updates.

965
00:39:27,330 --> 00:39:29,370
Als ik ga hier mijn linkerhand updates.

966
00:39:29,370 --> 00:39:33,090
En nu heb ik niet alleen een verwijzing naar
het element dat gaat na Julia,

967
00:39:33,090 --> 00:39:36,300
Ik heb nog een pointer naar
Andy, het element voor.

968
00:39:36,300 --> 00:39:39,430
Zodat u toegang hebt, in wezen,
paneermeel, als je wil,

969
00:39:39,430 --> 00:39:41,500
om alle vereiste pointers.

970
00:39:41,500 --> 00:39:43,710
>> Dus als ik wijzend op
Andy en ik ben ook wijzen

971
00:39:43,710 --> 00:39:47,105
bij Christian, wiens handen
moet nu elders worden opgemerkt?

972
00:39:47,105 --> 00:39:48,770

973
00:39:48,770 --> 00:39:51,960
Dus Andy kunnen nu wijzen op Julia.

974
00:39:51,960 --> 00:39:54,460
Julia kan nu wijzen op Christian.

975
00:39:54,460 --> 00:39:56,950
Omdat ze kan kopiëren mijn
pointer rechterhand.

976
00:39:56,950 --> 00:40:00,044
En dat effectief u zet
terug naar deze plek hier.

977
00:40:00,044 --> 00:40:02,460
Dus in het kort, ook al is dit
is een soort die ons van eeuwigheid

978
00:40:02,460 --> 00:40:04,510
daadwerkelijk werken een
gelinkte lijst, realiseren

979
00:40:04,510 --> 00:40:06,580
dat de operaties
zijn relatief eenvoudig.

980
00:40:06,580 --> 00:40:10,030
Het is een, twee, drie
regels code uiteindelijk.

981
00:40:10,030 --> 00:40:12,780
Maar rond deze
regels code vermoedelijk

982
00:40:12,780 --> 00:40:16,350
is een beetje logica die effectief
stelt de vraag, waar zijn we?

983
00:40:16,350 --> 00:40:18,970
Zijn we aan het begin,
het midden of het einde?

984
00:40:18,970 --> 00:40:21,890
>> Nu zijn er zeker enkele andere
operaties die we kunnen implementeren.

985
00:40:21,890 --> 00:40:24,880
En deze foto's hier gewoon verbeelden
wat we net gedaan met mensen.

986
00:40:24,880 --> 00:40:26,080
Hoe zit het met het verwijderen?

987
00:40:26,080 --> 00:40:30,650
Als ik wil bijvoorbeeld
verwijder het nummer 34 of 55,

988
00:40:30,650 --> 00:40:34,680
Ik zou dezelfde soort code zijn,
maar ik ga naar een of twee stappen nodig.

989
00:40:34,680 --> 00:40:36,110
Want wat is er nieuw?

990
00:40:36,110 --> 00:40:40,460
Als ik iemand te verwijderen aan het einde,
als nummer 55 en 34,

991
00:40:40,460 --> 00:40:42,995
wat moet ook veranderen als ik dat doe?

992
00:40:42,995 --> 00:40:44,870
Ik moet niet evict--
hoe heet je ook alweer?

993
00:40:44,870 --> 00:40:45,380
>> PUBLIEK: Jack.

994
00:40:45,380 --> 00:40:46,255
>> DAVID J. MALAN: Jack.

995
00:40:46,255 --> 00:40:49,770
Ik moet niet alleen evict-- vrij Jack,
dus letterlijk gratis bellen Jack, of op zijn minst

996
00:40:49,770 --> 00:40:53,530
de aanwijzer er ook, maar nu
wat er moet veranderen met Peter?

997
00:40:53,530 --> 00:40:55,510
Zijn hand beter beginnen naar beneden.

998
00:40:55,510 --> 00:40:59,300
Want zodra ik gratis bellen op
Jack, als Peter's nog steeds wijzend op Jack

999
00:40:59,300 --> 00:41:02,530
en ik dan ook blijven doorkruisen
de lijst en toegang tot deze wijzer,

1000
00:41:02,530 --> 00:41:05,650
dat is wanneer onze oude vriend segmentatie
fout zou eigenlijk schoppen.

1001
00:41:05,650 --> 00:41:07,860
Omdat we hebben gezien de
geheugen terug naar Jack.

1002
00:41:07,860 --> 00:41:10,760
>> Je kunt er overnachten
onhandig voor slechts een moment.

1003
00:41:10,760 --> 00:41:13,410
Want we hebben slechts een paar
laatste operaties te overwegen.

1004
00:41:13,410 --> 00:41:15,600
Het verwijderen van de kop van de lijst,
of de beginning-- en deze is

1005
00:41:15,600 --> 00:41:16,349
een beetje vervelend.

1006
00:41:16,349 --> 00:41:19,640
Want we moeten weten dat Gabe
is een beetje speciaal in dit programma.

1007
00:41:19,640 --> 00:41:21,440
Want inderdaad, hij heeft zijn eigen pointer.

1008
00:41:21,440 --> 00:41:24,860
Hij is niet alleen hun gewezen wordt,
zoals bijna iedereen hier.

1009
00:41:24,860 --> 00:41:28,112
>> Dus wanneer het hoofd van de lijst
verwijderd, wier handen moeten nu veranderen?

1010
00:41:28,112 --> 00:41:29,070
Wat heet je ook alweer?

1011
00:41:29,070 --> 00:41:29,450
>> PUBLIEK: Christine.

1012
00:41:29,450 --> 00:41:31,408
>> DAVID J. MALAN: Ik ben vreselijk
op namen, blijkbaar.

1013
00:41:31,408 --> 00:41:34,011
Dus Christine en Gabe,
wiens handen moeten veranderen

1014
00:41:34,011 --> 00:41:36,510
wanneer we proberen om Christine te verwijderen,
nummer 5, van de foto?

1015
00:41:36,510 --> 00:41:37,550

1016
00:41:37,550 --> 00:41:38,820
OK, dus laten we het doen Gabe.

1017
00:41:38,820 --> 00:41:40,950
Gabe gaat wijzen,
vermoedelijk, op nummer 9.

1018
00:41:40,950 --> 00:41:42,230

1019
00:41:42,230 --> 00:41:44,642
Maar wat er nu moet gebeuren?

1020
00:41:44,642 --> 00:41:46,600
PUBLIEK: Christine moet
null [onverstaanbaar].

1021
00:41:46,600 --> 00:41:50,244
DAVID J. MALAN: OK, moeten we waarschijnlijk
make-- Ik hoorde "null" ergens.

1022
00:41:50,244 --> 00:41:51,410
PUBLIEK: Null en vrij haar.

1023
00:41:51,410 --> 00:41:51,855
DAVID J. MALAN: NULL wat?

1024
00:41:51,855 --> 00:41:53,074
PUBLIEK: Null en vrij haar.

1025
00:41:53,074 --> 00:41:54,490
DAVID J. MALAN: Null en vrij haar.

1026
00:41:54,490 --> 00:41:55,422
Dus dit is zeer eenvoudig.

1027
00:41:55,422 --> 00:41:58,380
En het is perfect dat je nu een soort
van daar staan, die niet behoren.

1028
00:41:58,380 --> 00:42:00,430
Want je bent geweest
losgekoppeld van de lijst.

1029
00:42:00,430 --> 00:42:02,820
Je hebt effectief geweest
weeskinderen uit de lijst.

1030
00:42:02,820 --> 00:42:07,770
En dus hadden we het beter noemen nu gratis op
Christine aan dat het geheugen terug te geven.

1031
00:42:07,770 --> 00:42:10,240
Anders elke keer als we
verwijderen uit de lijst een knooppunt

1032
00:42:10,240 --> 00:42:14,230
we zouden kunnen maken van de lijst
korter, maar niet echt afnemende

1033
00:42:14,230 --> 00:42:15,096
de grootte van het geheugen.

1034
00:42:15,096 --> 00:42:17,720
En dus als we blijven toevoegen en
voegen, dingen toe te voegen aan de lijst,

1035
00:42:17,720 --> 00:42:19,280
mijn computer kan langzamer
en trager en trager,

1036
00:42:19,280 --> 00:42:21,740
want ik ben bijna geen
geheugen, zelfs als ik niet eigenlijk

1037
00:42:21,740 --> 00:42:25,580
met Christine's bytes
geheugen meer.

1038
00:42:25,580 --> 00:42:28,500
>> Dus uiteindelijk zijn er andere
scenario's, van course-- verwijderen

1039
00:42:28,500 --> 00:42:30,640
in het midden, het verwijderen
op het einde, zoals we zagen.

1040
00:42:30,640 --> 00:42:32,348
Maar de meest interessante
uitdaging is nu

1041
00:42:32,348 --> 00:42:34,770
zal zijn precies verhelpen
wat de looptijd is.

1042
00:42:34,770 --> 00:42:36,640
Dus niet alleen kan je je
stukjes papier, indien, Gabe,

1043
00:42:36,640 --> 00:42:38,640
zou je niet willen geven
iedereen een stressbal.

1044
00:42:38,640 --> 00:42:42,100
Dank je wel aan onze gelinkte lijst
vrijwilligers hier, als je kon.

1045
00:42:42,100 --> 00:42:45,320
>> [Applaus]

1046
00:42:45,320 --> 00:42:46,700
>> DAVID J. MALAN: Oke.

1047
00:42:46,700 --> 00:42:51,110
Dus een paar analytische
vragen dan, als ik kon.

1048
00:42:51,110 --> 00:42:59,670
We hebben deze notatie eerder gezien,
big O en omega, bovengrenzen

1049
00:42:59,670 --> 00:43:02,520
en ondergrenzen van de
looptijd van een algoritme.

1050
00:43:02,520 --> 00:43:04,950
Dus laten we eens gewoon
een paar vragen.

1051
00:43:04,950 --> 00:43:07,090
>> Een, en we zeiden dat het
voor, wat is de running

1052
00:43:07,090 --> 00:43:10,647
tijd van zoeken naar een
lijst in termen van grote O?

1053
00:43:10,647 --> 00:43:13,480
Wat is een bovengrens voor de lopende
tijd van zoeken een gekoppelde lijst

1054
00:43:13,480 --> 00:43:16,340
zoals uitgevoerd door onze vrijwilligers hier?

1055
00:43:16,340 --> 00:43:17,820
Het is groot O van n, lineair.

1056
00:43:17,820 --> 00:43:20,630
Omdat in het ergste geval,
het element, zoals 55,

1057
00:43:20,630 --> 00:43:23,830
we misschien op zoek naar misschien wel waar
Jack, helemaal aan het einde.

1058
00:43:23,830 --> 00:43:28,250
En helaas, anders dan een matrix
kunnen we niet chique deze tijd.

1059
00:43:28,250 --> 00:43:31,820
Hoewel al onze mensen waren
gesorteerd van kleine elementen, 5,

1060
00:43:31,820 --> 00:43:35,900
helemaal tot aan de grotere element,
55, dat is meestal een goede zaak.

1061
00:43:35,900 --> 00:43:38,815
Maar wat betekent dat de veronderstelling
niet meer kunnen we doen?

1062
00:43:38,815 --> 00:43:39,775

1063
00:43:39,775 --> 00:43:40,650
PUBLIEK: [onverstaanbaar]

1064
00:43:40,650 --> 00:43:40,920
DAVID J. MALAN: weer zeggen?

1065
00:43:40,920 --> 00:43:41,800
PUBLIEK: 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
En op zijn beurt dat betekent dat we kunnen geen
gebruik meer maken van zwakke nullen, intuïtie,

1068
00:43:46,330 --> 00:43:49,365
en het evidente karakter van het gebruik van binaire
zoeken en verdeel en heers.

1069
00:43:49,365 --> 00:43:51,240
Want hoewel we
mensen kunnen natuurlijk

1070
00:43:51,240 --> 00:43:54,610
zien dat Andy of christelijk waren
ongeveer in het midden van de lijst,

1071
00:43:54,610 --> 00:43:57,670
we weten alleen dat als een
computer door het afromen van de lijst

1072
00:43:57,670 --> 00:43:59,029
vanaf het allereerste begin.

1073
00:43:59,029 --> 00:44:00,570
Dus we hebben opgegeven dat random access.

1074
00:44:00,570 --> 00:44:04,380
>> Zo groot O van n is nu de bovenste
gebonden op onze zoektijd.

1075
00:44:04,380 --> 00:44:07,920
Hoe zit het met omega van ons zoeken?

1076
00:44:07,920 --> 00:44:11,535
Wat is de ondergrens op te zoeken
gedurende een aantal in dit overzicht?

1077
00:44:11,535 --> 00:44:12,410
PUBLIEK: [onverstaanbaar]

1078
00:44:12,410 --> 00:44:13,040
DAVID J. MALAN: weer zeggen?

1079
00:44:13,040 --> 00:44:13,420
PUBLIEK: One.

1080
00:44:13,420 --> 00:44:13,800
DAVID J. MALAN: One.

1081
00:44:13,800 --> 00:44:14,760
Dus constante tijd.

1082
00:44:14,760 --> 00:44:17,020
In het beste geval, Christine is
immers aan het begin van de lijst.

1083
00:44:17,020 --> 00:44:19,020
En we zijn op zoek naar
nummer 5, dus hebben we haar gevonden.

1084
00:44:19,020 --> 00:44:19,787
Dus geen big deal.

1085
00:44:19,787 --> 00:44:22,370
Maar ze heeft om in de
begin van de lijst in dit geval.

1086
00:44:22,370 --> 00:44:23,745
Hoe zit het met iets als Delete?

1087
00:44:23,745 --> 00:44:24,717

1088
00:44:24,717 --> 00:44:26,300
Wat als u een element wilt verwijderen?

1089
00:44:26,300 --> 00:44:29,200
Wat is de bovengrens en ondergrens
op iets uit een gekoppeld te verwijderen

1090
00:44:29,200 --> 00:44:29,699
lijst?

1091
00:44:29,699 --> 00:44:35,195

1092
00:44:35,195 --> 00:44:36,070
PUBLIEK: [onverstaanbaar]

1093
00:44:36,070 --> 00:44:36,420
DAVID J. MALAN: weer zeggen?

1094
00:44:36,420 --> 00:44:37,067
PUBLIEK: n.

1095
00:44:37,067 --> 00:44:38,900
DAVID J. MALAN: n is
inderdaad de bovengrens.

1096
00:44:38,900 --> 00:44:41,700
Want in het ergste geval proberen we
Jack verwijderen, zoals we net gedaan.

1097
00:44:41,700 --> 00:44:43,050
Hij is helemaal aan het eind.

1098
00:44:43,050 --> 00:44:45,419
Neemt ons altijd, of
n stappen om hem te vinden.

1099
00:44:45,419 --> 00:44:46,460
Dus dat is een bovengrens.

1100
00:44:46,460 --> 00:44:47,430
Dat is lineair, zeker.

1101
00:44:47,430 --> 00:44:50,970
En het beste geval looptijd, of
de ondergrens in het beste geval

1102
00:44:50,970 --> 00:44:51,975
zou constante tijd.

1103
00:44:51,975 --> 00:44:54,600
Want misschien proberen we om te verwijderen
Christine, en we krijgen gewoon geluk

1104
00:44:54,600 --> 00:44:55,558
ze is in het begin.

1105
00:44:55,558 --> 00:44:56,350
Wacht eens even.

1106
00:44:56,350 --> 00:44:59,370
Gabe was aan het begin,
en we moesten ook Gabe updaten.

1107
00:44:59,370 --> 00:45:01,150
Dus dat was niet zomaar een stap.

1108
00:45:01,150 --> 00:45:04,210
Dus is het inderdaad constant
tijd, in het beste geval,

1109
00:45:04,210 --> 00:45:06,345
om het kleinste element te verwijderen?

1110
00:45:06,345 --> 00:45:07,360

1111
00:45:07,360 --> 00:45:10,960
Het is, hoewel het misschien twee,
drie of zelfs 100 regels code,

1112
00:45:10,960 --> 00:45:14,000
als het hetzelfde aantal
lijnen, niet in een lus,

1113
00:45:14,000 --> 00:45:16,577
en onafhankelijk van de grootte
van de lijst, absoluut.

1114
00:45:16,577 --> 00:45:18,660
Het element bij het verwijderen
het begin van de lijst

1115
00:45:18,660 --> 00:45:21,940
zelfs als we te maken hebben met
Gabe, blijft constant tijd.

1116
00:45:21,940 --> 00:45:24,220
>> Dus dit lijkt een
enorme stap achteruit.

1117
00:45:24,220 --> 00:45:27,000
En wat een verspilling van tijd
indien, in week een en week

1118
00:45:27,000 --> 00:45:30,250
nul hadden we niet alleen
pseudocode code maar de werkelijke code

1119
00:45:30,250 --> 00:45:35,780
naar iets dat log implementeren
base n, of meld u, in plaats van n, basis 2,

1120
00:45:35,780 --> 00:45:37,150
qua looptijd.

1121
00:45:37,150 --> 00:45:40,710
Dus waarom de heck zouden we willen beginnen
met behulp van iets als een gelinkte lijst?

1122
00:45:40,710 --> 00:45:41,517
Yeah.

1123
00:45:41,517 --> 00:45:44,022
>> PUBLIEK: Dus u kunt toevoegen
elementen aan de array.

1124
00:45:44,022 --> 00:45:46,230
DAVID J. MALAN: Dus je kan
elementen aan de array voegen.

1125
00:45:46,230 --> 00:45:47,550
En ook dit is thematisch.

1126
00:45:47,550 --> 00:45:49,740
En we zullen blijven zien
deze, deze trade-off, veel

1127
00:45:49,740 --> 00:45:51,573
zoals we hebben gezien een
trade-off met merge sort.

1128
00:45:51,573 --> 00:45:54,606
We konden echt versnellen
zoeken of sorteren, liever,

1129
00:45:54,606 --> 00:45:57,480
Als we besteden een beetje meer ruimte en
hebben een extra stuk van een herinnering

1130
00:45:57,480 --> 00:45:58,760
of een array voor merge sort.

1131
00:45:58,760 --> 00:46:01,270
Maar we besteden meer
ruimte, maar we tijd besparen.

1132
00:46:01,270 --> 00:46:04,820
In dit geval zijn we
het opgeven van de tijd, maar we zijn

1133
00:46:04,820 --> 00:46:08,170
verkrijgen flexibiliteit
dynamiek als je wil,

1134
00:46:08,170 --> 00:46:10,280
dat is misschien wel een positief punt.

1135
00:46:10,280 --> 00:46:11,520
>> We zijn ook de besteding van de ruimte.

1136
00:46:11,520 --> 00:46:13,710
In welke zin is een gekoppelde
lijst duurder

1137
00:46:13,710 --> 00:46:15,700
in termen van ruimte dan een array?

1138
00:46:15,700 --> 00:46:18,379

1139
00:46:18,379 --> 00:46:19,920
Waar is de extra ruimte vandaan?

1140
00:46:19,920 --> 00:46:20,460
Yeah?

1141
00:46:20,460 --> 00:46:21,800
>> PUBLIEK: [onverstaanbaar] wijzer.

1142
00:46:21,800 --> 00:46:23,310
>> DAVID J. MALAN: Ja, we
hebben ook de pointer.

1143
00:46:23,310 --> 00:46:25,560
Dus dit is minorly vervelend
dat niet meer am

1144
00:46:25,560 --> 00:46:27,780
Ik opbergen gewoon een int
naar een int te vertegenwoordigen.

1145
00:46:27,780 --> 00:46:30,990
Ik ben het opslaan van een int en een
pointer, die ook 32 bits.

1146
00:46:30,990 --> 00:46:33,470
Dus ik ben letterlijk verdubbelen
de hoeveelheid ruimte betrokken.

1147
00:46:33,470 --> 00:46:36,040
Dus dat is een trade-off, maar
dat is in het geval van int.

1148
00:46:36,040 --> 00:46:39,580
Stel dat je niet opslaan van int,
maar stel dat elk van deze rechthoeken

1149
00:46:39,580 --> 00:46:43,290
of elk van deze mensen vertegenwoordigde
een woord, een Engels woord dat

1150
00:46:43,290 --> 00:46:46,430
misschien vijf tekens, 10
personages, misschien zelfs meer.

1151
00:46:46,430 --> 00:46:49,940
Dan het toevoegen van slechts 32 meer bits
misschien minder van een big deal te zijn.

1152
00:46:49,940 --> 00:46:52,160
>> Wat als elk van de studenten
in de demonstratie

1153
00:46:52,160 --> 00:46:55,107
waren letterlijk student structuren die
hebben namen en huizen en misschien

1154
00:46:55,107 --> 00:46:57,065
telefoonnummers en Twitter
handgrepen en dergelijke.

1155
00:46:57,065 --> 00:46:59,564
Dus alle velden we begonnen
praten over de andere dag,

1156
00:46:59,564 --> 00:47:02,410
veel minder een big deal als
onze knooppunten krijgen interessanter

1157
00:47:02,410 --> 00:47:05,972
en groot te brengen, eh, een extra
wijzer alleen om ze met elkaar te verbinden.

1158
00:47:05,972 --> 00:47:07,180
Maar inderdaad, het is een trade-off.

1159
00:47:07,180 --> 00:47:09,560
En inderdaad, de code is
complexer, zoals u zult

1160
00:47:09,560 --> 00:47:11,770
zie door het afromen door middel van
die specifieke voorbeeld.

1161
00:47:11,770 --> 00:47:14,302
Maar wat als er
sommige heilige graal hier.

1162
00:47:14,302 --> 00:47:17,010
Wat als we niet een stap te zetten
achteruit maar een grote stap voorwaarts

1163
00:47:17,010 --> 00:47:19,180
en implementeren van een data
structuur via welke we

1164
00:47:19,180 --> 00:47:22,870
kunnen elementen zoals Jack of zoek
Christine of andere elementen

1165
00:47:22,870 --> 00:47:25,870
in deze array in ware constante tijd?

1166
00:47:25,870 --> 00:47:26,920
Search is een constante.

1167
00:47:26,920 --> 00:47:28,320
Delete is constant.

1168
00:47:28,320 --> 00:47:29,570
Insert is constant.

1169
00:47:29,570 --> 00:47:32,260
Al deze activiteiten zijn constant.

1170
00:47:32,260 --> 00:47:33,750
Dat zou onze heilige graal zijn.

1171
00:47:33,750 --> 00:47:36,690
En dat is waar we
pikt de volgende keer.

1172
00:47:36,690 --> 00:47:38,600
Zie je dan.

1173
00:47:38,600 --> 00:47:39,371