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

2
00:00:00,500 --> 00:00:11,137
[Speel van musiek]

3
00:00:11,137 --> 00:00:12,220
David J. Malan Alle regte.

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

5
00:00:13,950 --> 00:00:18,560
Dit is die vyfde week voortgesit, en ons
het 'n paar goeie nuus en slegte nuus.

6
00:00:18,560 --> 00:00:21,140
So goeie nuus is dat CS50
loods hierdie Vrydag.

7
00:00:21,140 --> 00:00:24,430
As jy wil ons aan te sluit,
kop aan die gewone URL hier.

8
00:00:24,430 --> 00:00:28,670
Die goeie nuus is geen lesing
eerskomende Maandag die 13de.

9
00:00:28,670 --> 00:00:31,970
Effens minder goeie nuus,
quiz nul is volgende Woensdag.

10
00:00:31,970 --> 00:00:33,840
Meer besonderhede kan
gevind op hierdie URL hier.

11
00:00:33,840 --> 00:00:36,340
En oor die volgende paar dae
Ons sal in die spasies te vul word

12
00:00:36,340 --> 00:00:39,234
met betrekking tot die kamers
dat ons sal gereserveer het.

13
00:00:39,234 --> 00:00:41,400
Beter nuus is dat daar sal
wees om 'n kursus-wye oorsig

14
00:00:41,400 --> 00:00:43,570
sessie eerskomende
Maandag in die aand.

15
00:00:43,570 --> 00:00:46,270
Bly ingeskakel vir die kursus se
webwerf vir die ligging en besonderhede.

16
00:00:46,270 --> 00:00:49,290
Afdelings, selfs al is dit 'n
vakansie, sal ook aan sowel.

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

18
00:00:50,490 --> 00:00:52,940
Beste nuus, lesings volgende Vrydag.

19
00:00:52,940 --> 00:00:56,220
So dit is 'n tradisie wat ons
het, soos per die leerplan.

20
00:00:56,220 --> 00:00:58,100
Just-- dit gaan wonderlik wees.

21
00:00:58,100 --> 00:01:02,510
Jy sal sien dinge soos
konstante data strukture

22
00:01:02,510 --> 00:01:04,730
en hash tabelle en bome en drieë.

23
00:01:04,730 --> 00:01:07,150
En ons sal praat oor verjaarsdag probleme.

24
00:01:07,150 --> 00:01:09,440
'N Hele klomp van die dinge
wag volgende Vrydag.

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
In elk geval.

28
00:01:13,190 --> 00:01:17,080
>> So onthou dat ons al
fokus op die foto van wat

29
00:01:17,080 --> 00:01:18,980
binnekant van ons rekenaar se geheue.

30
00:01:18,980 --> 00:01:22,875
So geheue of RAM is waar programme
bestaan ​​terwyl jy hardloop hulle.

31
00:01:22,875 --> 00:01:25,215
As jy dubbel-kliek 'n
ikoon 'n program uit te voer

32
00:01:25,215 --> 00:01:27,520
of dubbel-klik op 'n
ikoon sommige lêer oop te maak,

33
00:01:27,520 --> 00:01:30,430
dit is gelaai uit jou harde
ry of vaste toestand ry

34
00:01:30,430 --> 00:01:34,190
in die geheue, Random Access Memory, waar
dit leef totdat die krag afgaan,

35
00:01:34,190 --> 00:01:36,700
die skootrekenaardeksel sluit,
of jy sluit die program.

36
00:01:36,700 --> 00:01:38,960
>> Nou dat die geheue van
wat jy waarskynlik

37
00:01:38,960 --> 00:01:41,950
1 gigagreep hierdie dae, 2
GB, of selfs veel meer,

38
00:01:41,950 --> 00:01:44,420
is oor die algemeen uitgelê
vir 'n gegewe program

39
00:01:44,420 --> 00:01:47,170
in hierdie soort van vierkantige
konseptuele model

40
00:01:47,170 --> 00:01:50,860
waardeur ons die stapel aan die onderkant
en 'n klomp ander dinge aan die bokant.

41
00:01:50,860 --> 00:01:53,140
Die ding op die top
ons gesien het op die foto

42
00:01:53,140 --> 00:01:55,670
voor, maar nooit daaroor gepraat
is die sogenaamde teks segment.

43
00:01:55,670 --> 00:01:58,419
Teks segment is net 'n fancy manier
sê die nulle en ene wat

44
00:01:58,419 --> 00:02:01,150
komponeer jou werklike saamgestel program.

45
00:02:01,150 --> 00:02:03,910
>> So wanneer jy dubbel-kliek
Microsoft Word op jou Mac of PC,

46
00:02:03,910 --> 00:02:08,030
of wanneer jy loop dot streep Mario op 'n
Linux rekenaar by jou terminale venster,

47
00:02:08,030 --> 00:02:12,460
die nulle en ene wat komponeer
Woord of Mario tydelik gestoor

48
00:02:12,460 --> 00:02:16,610
in jou rekenaar se geheue in die sogenaamde
teks segment vir 'n bepaalde program.

49
00:02:16,610 --> 00:02:19,080
Hier wat gaan geïnisialiseer
en geïnitialiseerd data.

50
00:02:19,080 --> 00:02:22,655
Dit is dinge soos die globale veranderlikes,
dat ons nie gebruik het baie van,

51
00:02:22,655 --> 00:02:24,910
maar oor die geleentheid wat ons het
het globale veranderlikes

52
00:02:24,910 --> 00:02:28,819
of staties gedefinieer snare wat
hard gekodeer woorde soos "hallo"

53
00:02:28,819 --> 00:02:31,860
wat nie geneem uit die gebruiker
wat hard-gekodeerde in jou program.

54
00:02:31,860 --> 00:02:34,230
>> Nou, sit aan die onderkant ons
het die sogenaamde stapel.

55
00:02:34,230 --> 00:02:37,665
En die stapel, tot dusver, het ons
gebruik vir watter soort doeleindes?

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

57
00:02:39,706 --> 00:02:40,997
Wat is die stapel is gebruik?

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

59
00:02:41,160 --> 00:02:42,070
>> Publiek: funksies.

60
00:02:42,070 --> 00:02:43,320
>> David J. Malan vir funksies?

61
00:02:43,320 --> 00:02:44,980
In watter sin vir funksies?

62
00:02:44,980 --> 00:02:48,660
>> Publiek: Wanneer jy bel 'n funksie, die
argumente word op die stapel kopieer.

63
00:02:48,660 --> 00:02:49,660
>> David J. Malan Presies.

64
00:02:49,660 --> 00:02:52,650
Wanneer jy bel 'n funksie, sy
argumente word op die stapel kopieer.

65
00:02:52,650 --> 00:02:56,330
So 'n X se of Y of 'n se of B se
dat jy beweeg in 'n funksie

66
00:02:56,330 --> 00:02:58,680
tydelik op
die sogenaamde stapel,

67
00:02:58,680 --> 00:03:02,000
net soos een van die Annenberg
eetsaal bak, en ook om dinge

68
00:03:02,000 --> 00:03:03,190
soos plaaslike veranderlikes.

69
00:03:03,190 --> 00:03:06,290
As jou cat funksie of jou ruil
funksie het plaaslike veranderlikes,

70
00:03:06,290 --> 00:03:08,602
soos temp, die twee
eindig op die stapel.

71
00:03:08,602 --> 00:03:11,560
Nou sal ons nie te veel oor praat
hulle, maar hierdie omgewing veranderlikes

72
00:03:11,560 --> 00:03:15,690
aan die onderkant ons het 'n ruk gelede toe
Ek was futzing by die klawerbord een dag

73
00:03:15,690 --> 00:03:20,050
en ek het begin toegang dinge
soos argv 100 of argv 1000,

74
00:03:20,050 --> 00:03:22,320
net elements-- ek vergeet
die numbers-- maar dat

75
00:03:22,320 --> 00:03:24,330
is nie veronderstel om te verkry word deur my.

76
00:03:24,330 --> 00:03:26,581
Ons begin sien 'n paar
funky simbole op die skerm.

77
00:03:26,581 --> 00:03:28,330
Dit was die sogenaamde
omgewing veranderlikes

78
00:03:28,330 --> 00:03:32,390
soos globale instellings vir my
program of my rekenaar, wat nie

79
00:03:32,390 --> 00:03:37,090
verband hou met die onlangse
fout wat ons bespreek het,

80
00:03:37,090 --> 00:03:39,670
Shellshock, wat al
teister nogal 'n paar rekenaars.

81
00:03:39,670 --> 00:03:42,960
>> Nou laastens, in vandag se fokus
ons sal uiteindelik op die hoop.

82
00:03:42,960 --> 00:03:44,864
Dit is nog 'n stuk van die geheue.

83
00:03:44,864 --> 00:03:47,030
En fundamenteel al hierdie
geheue is dieselfde dinge.

84
00:03:47,030 --> 00:03:48,040
Dit is dieselfde hardeware.

85
00:03:48,040 --> 00:03:49,956
Ons is net soort van
behandeling verskillende groepe

86
00:03:49,956 --> 00:03:51,460
grepe vir verskillende doeleindes.

87
00:03:51,460 --> 00:03:56,540
Die hoop is ook gaan wees waar
veranderlikes en geheue wat u versoek

88
00:03:56,540 --> 00:03:58,810
van die bedryfstelsel
tydelik gestoor word.

89
00:03:58,810 --> 00:04:01,890
>> Maar daar is 'n soort van 'n probleem
hier, soos die foto impliseer.

90
00:04:01,890 --> 00:04:05,261
Ons soort van twee
skepe oor te bots.

91
00:04:05,261 --> 00:04:08,010
Omdat as jy meer en meer gebruik
van die stapel, en as ons vandag sien

92
00:04:08,010 --> 00:04:11,800
af, as jy meer en meer van die gebruik
hoop, sekerlik slegte dinge kan gebeur.

93
00:04:11,800 --> 00:04:15,054
En inderdaad, kan ons veroorsaak dat
opsetlik of per ongeluk.

94
00:04:15,054 --> 00:04:16,970
So het die fotonische lewe laaste
tyd was hierdie program

95
00:04:16,970 --> 00:04:20,570
wat nie 'n funksionele gedien het
ander doel as om te demonstreer

96
00:04:20,570 --> 00:04:24,750
hoe jy as 'n slegte man kan eintlik neem
voordeel van foute in iemand se program

97
00:04:24,750 --> 00:04:28,460
en neem oor 'n program of selfs 'n
hele rekenaarstelsel of bediener.

98
00:04:28,460 --> 00:04:31,660
So net om te blik kortliks, jy
sien dat hoof aan die onderkant

99
00:04:31,660 --> 00:04:34,510
neem in command line
argumente, soos per argv.

100
00:04:34,510 --> 00:04:38,480
En dit het 'n oproep om 'n funksie f,
wese 'n naamlose funksie genoem

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

102
00:04:40,250 --> 00:04:43,960
>> Dus, wat woord wat die gebruiker in te
die vinnige ná hierdie program se naam,

103
00:04:43,960 --> 00:04:49,310
en dan is dit arbitrêre funksie tot
top, f, neem in 'n string, AKA kar *,

104
00:04:49,310 --> 00:04:51,720
as ons begin om te bespreek,
en dit net noem dit "bar."

105
00:04:51,720 --> 00:04:53,310
Maar ons kan dit noem nie.

106
00:04:53,310 --> 00:04:57,470
En dan is dit verklaar, binne
van f, 'n verskeidenheid van die karakters

107
00:04:57,470 --> 00:04:59,930
genoem c-- 12 sulke karakters.

108
00:04:59,930 --> 00:05:03,580
>> Nou, deur die storie wat ek vertel
'n oomblik gelede, waar in die geheue

109
00:05:03,580 --> 00:05:06,720
is c, of is daardie 12
karakters gaan eindig?

110
00:05:06,720 --> 00:05:07,570
Net om duidelik te wees.

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

112
00:05:08,070 --> 00:05:08,590
>> Publiek: Op die stapel.

113
00:05:08,590 --> 00:05:09,420
>> David J. Malan op die stapel.

114
00:05:09,420 --> 00:05:10,720
So c is 'n plaaslike veranderlike.

115
00:05:10,720 --> 00:05:14,079
Ons vra vir 12 karakters of 12 grepe.

116
00:05:14,079 --> 00:05:16,120
Diegene gaan beland
op die sogenaamde stapel.

117
00:05:16,120 --> 00:05:18,530
Nou uiteindelik is hierdie ander funksie
dit is eintlik baie handig,

118
00:05:18,530 --> 00:05:20,571
maar ons het nie regtig gebruik
dit self, strncopy.

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

120
00:05:21,550 --> 00:05:25,200
Dit beteken string afskrif, maar
net n brief, N karakters.

121
00:05:25,200 --> 00:05:31,990
So n karakters sal wees
oorgeneem uit bar in c.

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

123
00:05:32,980 --> 00:05:34,110
Die lengte van die bar.

124
00:05:34,110 --> 00:05:36,330
So met ander woorde, wat
een lyn, strncopy,

125
00:05:36,330 --> 00:05:39,500
gaan kopieer
effektief kroeg in te c.

126
00:05:39,500 --> 00:05:42,340
>> Nou, net om te soort van verwag
Die moraal van hierdie storie,

127
00:05:42,340 --> 00:05:44,750
wat potensieel problematies hier?

128
00:05:44,750 --> 00:05:49,710
Selfs al het ons die beheer van die lengte
van bar en om dit in strncopy,

129
00:05:49,710 --> 00:05:53,145
Wat is jou gut vertel jou is
nog gebreek oor hierdie program?

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

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

132
00:05:55,220 --> 00:05:57,491
>> Publiek: Maak nie sluit
ruimte vir die nul karakter.

133
00:05:57,491 --> 00:05:59,990
David J. Malan Sluit nie
ruimte vir die nul karakter.

134
00:05:59,990 --> 00:06:02,073
Potensieel, in teenstelling met
in die verlede het ons dit nie doen nie, selfs

135
00:06:02,073 --> 00:06:04,810
so veel as 'n plus 1 tot
akkommodeer wat null karakter.

136
00:06:04,810 --> 00:06:06,649
Maar dit is nog erger as dit.

137
00:06:06,649 --> 00:06:07,940
Wat anders is ons versuim om te doen?

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

139
00:06:08,432 --> 00:06:09,307
>> Publiek: [onhoorbaar]

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
Ons het hard gekodeer 12 mooi arbitrêr.

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

144
00:06:19,497 --> 00:06:21,330
Dit is nie soseer die
probleem nie, maar die feit

145
00:06:21,330 --> 00:06:25,630
dat ons nie eens seker te maak dat
die lengte van die bar is minder as 12,

146
00:06:25,630 --> 00:06:28,530
in welke geval dit gaan wees
veilig om dit in die geheue

147
00:06:28,530 --> 00:06:30,260
genoem c dat ons toegeken is.

148
00:06:30,260 --> 00:06:32,960
Inderdaad, as bar is soos
20 karakters lank,

149
00:06:32,960 --> 00:06:39,010
hierdie funksie blyk te wees, kopieer
20 karakters van bar in c, en sodoende

150
00:06:39,010 --> 00:06:41,310
neem ten minste 8 grepe
dat dit nie moet wees nie.

151
00:06:41,310 --> 00:06:42,690
Dit is die implikasie hier.

152
00:06:42,690 --> 00:06:44,347
>> Dus, in kort, gebreekte program.

153
00:06:44,347 --> 00:06:45,180
Nie so 'n groot deal.

154
00:06:45,180 --> 00:06:46,360
Miskien het jy 'n segmentering skuld.

155
00:06:46,360 --> 00:06:47,651
Ons het almal het foute in programme.

156
00:06:47,651 --> 00:06:50,196
Ons almal kan foute het
programme nou.

157
00:06:50,196 --> 00:06:51,320
Maar wat is die implikasie?

158
00:06:51,320 --> 00:06:54,390
Wel, hier is 'n ingezoomd-in-weergawe van
die foto van my rekenaar se geheue.

159
00:06:54,390 --> 00:06:56,230
Dit is die onderkant van my stapel.

160
00:06:56,230 --> 00:06:59,644
En inderdaad, op die heel onderste is wat is
genoem ouer roetine stapel, fancy manier

161
00:06:59,644 --> 00:07:00,560
om te sê dat die belangrikste.

162
00:07:00,560 --> 00:07:03,772
Sodat elkeen wat die funksie genoem
f dat ons praat.

163
00:07:03,772 --> 00:07:05,230
So dit is die onderkant van die stapel.

164
00:07:05,230 --> 00:07:06,640
Terugkeer adres is iets nuuts.

165
00:07:06,640 --> 00:07:08,810
Dit was nog altyd daar,
altyd in die foto.

166
00:07:08,810 --> 00:07:10,440
Ons het net nooit aandag geroep om dit te.

167
00:07:10,440 --> 00:07:15,290
Omdat dit blyk uit die manier c werk is
dat wanneer een funksie noem 'n ander,

168
00:07:15,290 --> 00:07:18,780
nie net die argumente wat dit doen
funksie gestoot kry op die stapel te plaas,

169
00:07:18,780 --> 00:07:22,470
nie net die funksie se plaaslike doen
veranderlikes gestoot kry op die stapel te plaas,

170
00:07:22,470 --> 00:07:26,820
iets genaamd 'n terugkeer adres
ook kry sit op die stapel.

171
00:07:26,820 --> 00:07:33,330
Spesifiek, as hoof oproepe foo, hoof se
eie adres in die geheue, bees iets,

172
00:07:33,330 --> 00:07:38,240
effektief kry sit op die stapel
sodat wanneer f gedoen die uitvoering van dit

173
00:07:38,240 --> 00:07:43,630
weet waar om terug te spring in die teks
segment in om voort te gaan die uitvoering.

174
00:07:43,630 --> 00:07:47,760
>> So as ons hier is konseptueel,
in die belangrikste, dan is f kry genoem.

175
00:07:47,760 --> 00:07:50,200
Hoe f weet wie
om beheer terug?

176
00:07:50,200 --> 00:07:52,020
Wel, hierdie klein
bread in rooi hier

177
00:07:52,020 --> 00:07:54,978
genoem die adres, is dit net
tjeks, wat is dit terugkeer adres?

178
00:07:54,978 --> 00:07:57,039
O, laat my terug na die hoof spring hier.

179
00:07:57,039 --> 00:07:59,080
En dit is 'n bietjie
van 'n oorvereenvoudiging,

180
00:07:59,080 --> 00:08:00,750
omdat die nulle en ene
vir die hoof is tegnies

181
00:08:00,750 --> 00:08:01,967
hier in die tegnologie segment.

182
00:08:01,967 --> 00:08:03,800
Maar dit is die idee. f
het net om te weet wat

183
00:08:03,800 --> 00:08:06,680
waar beheer gaan uiteindelik terug.

184
00:08:06,680 --> 00:08:09,790
>> Maar die manier waarop rekenaars
het lank gelê dinge

185
00:08:09,790 --> 00:08:12,320
soos plaaslike veranderlikes en
argumente is soos hierdie.

186
00:08:12,320 --> 00:08:17,180
So in die top van hierdie foto in
blou is die stapel raamwerk vir f, so al

187
00:08:17,180 --> 00:08:19,630
van die geheue wat f
spesifiek is met behulp van.

188
00:08:19,630 --> 00:08:22,990
So dienooreenkomstig, sien dat
bar is in die prentjie.

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

190
00:08:23,980 --> 00:08:27,240
En ons het beweer dat argumente te
funksies gestoot kry op die stapel.

191
00:08:27,240 --> 00:08:29,910
En c, natuurlik, is
ook in hierdie foto.

192
00:08:29,910 --> 00:08:33,520
>> En net vir notasie doeleindes,
kennisgewing by die top linkerhoek

193
00:08:33,520 --> 00:08:37,020
word wat sou wees c bracket 0 en
dan effens af aan die regterkant

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

195
00:08:38,220 --> 00:08:41,240
So met ander woorde, kan jy dink
dat daar 'n rooster van grepe

196
00:08:41,240 --> 00:08:44,380
Daar, in die eerste wat
links bo, onderkant van wat

197
00:08:44,380 --> 00:08:48,360
is die laaste van die 12 grepe.

198
00:08:48,360 --> 00:08:49,930
>> Maar nou probeer om vorentoe te vinnig.

199
00:08:49,930 --> 00:08:55,580
Wat gaan gebeur as ons slaag
in 'n string bar dit is langer as c?

200
00:08:55,580 --> 00:08:59,130
En ons is nie seker te maak dat
dit is inderdaad meer as 12.

201
00:08:59,130 --> 00:09:03,146
Watter deel van hierdie prentjie gaan
kry oorskryf deur grepe 0, 1, 2, 3,

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

203
00:09:07,890 --> 00:09:11,820
Wat gaan hier gebeur nie,
As jy aflei uit die bestel

204
00:09:11,820 --> 00:09:14,790
dat c bracket 0 is op die top
en c bracket 11 is 'n soort van af

205
00:09:14,790 --> 00:09:15,812
aan die regterkant?

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

207
00:09:16,796 --> 00:09:19,260
>> Publiek: Wel, dit gaan
te vervang die kar * bar.

208
00:09:19,260 --> 00:09:22,260
>> David J. MALAN: Ja, dit lyk soos
jy gaan te vervang kar * bar.

209
00:09:22,260 --> 00:09:26,245
En nog erger, as jy stuur in 'n baie lang
string, kan jy selfs oorskryf wat?

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

211
00:09:27,460 --> 00:09:28,570
Die opbrengs adres.

212
00:09:28,570 --> 00:09:31,380
Wat weer, is net soos 'n
bread die program waar om te vertel

213
00:09:31,380 --> 00:09:34,060
om terug te gaan wanneer f
gedoen word genoem.

214
00:09:34,060 --> 00:09:37,140
>> So, wat slegte ouens tipies doen
is as hulle kom oor 'n program

215
00:09:37,140 --> 00:09:41,290
dat hulle nuuskierig of is
ontginbaar, karretjie in so 'n manier

216
00:09:41,290 --> 00:09:43,550
dat hy of sy kan neem
voordeel van die fout,

217
00:09:43,550 --> 00:09:45,720
algemeen hulle kry nie
hierdie reg die eerste keer.

218
00:09:45,720 --> 00:09:48,590
Hulle het net begin stuur, byvoorbeeld,
ewekansige snare in jou program,

219
00:09:48,590 --> 00:09:50,260
of by die klawerbord,
of eerlik hulle waarskynlik

220
00:09:50,260 --> 00:09:52,740
skryf 'n klein program om net
outomaties genereer snare,

221
00:09:52,740 --> 00:09:55,430
en begin klap op jou program deur
stuur in baie verskillende insette

222
00:09:55,430 --> 00:09:56,340
op verskillende lengtes.

223
00:09:56,340 --> 00:09:58,990
>> Sodra jou program crashes,
dit is 'n wonderlike ding.

224
00:09:58,990 --> 00:10:01,020
Want dit beteken hy
of sy ontdek

225
00:10:01,020 --> 00:10:02,660
wat is waarskynlik inderdaad 'n fout.

226
00:10:02,660 --> 00:10:05,830
En dan kan hulle meer slim
en begin meer eng fokus

227
00:10:05,830 --> 00:10:07,420
oor hoe dat die fout te ontgin.

228
00:10:07,420 --> 00:10:11,480
In die besonder, wat hy of sy mag
doen is stuur, in die beste geval, hallo.

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

230
00:10:12,210 --> 00:10:14,750
Dit is 'n string wat is genoeg kort.

231
00:10:14,750 --> 00:10:18,100
Maar wat as hy of sy stuur,
en ons sal veralgemeen dit as,

232
00:10:18,100 --> 00:10:20,890
aanval code-- so nulle
en diegene wat dinge doen

233
00:10:20,890 --> 00:10:25,150
soos rm-rf, dat alles verwyder
van die hardeskyf of stuur spam

234
00:10:25,150 --> 00:10:27,000
of een of ander manier om die masjien te val?

235
00:10:27,000 --> 00:10:29,570
>> So as elk van hierdie
letters A net verteenwoordig,

236
00:10:29,570 --> 00:10:32,380
konseptueel, aanval, aanval,
aanval, aanval, 'n paar slegte kode

237
00:10:32,380 --> 00:10:36,410
dat iemand anders geskryf het nie, maar
indien daardie persoon is slim genoeg

238
00:10:36,410 --> 00:10:40,790
om nie net al
van daardie rm-RFS nie, maar ook

239
00:10:40,790 --> 00:10:46,100
sy of haar laaste paar grepe
'n getal wat ooreenstem

240
00:10:46,100 --> 00:10:50,540
aan die adres van sy
of haar eie aanval kode

241
00:10:50,540 --> 00:10:53,820
dat hy of sy geslaag het in net
deur dit by die vinnige,

242
00:10:53,820 --> 00:10:58,760
jy kan die rekenaar effektief mislei
in die merk wanneer f gedoen uitvoering,

243
00:10:58,760 --> 00:11:02,400
O ja, dit is tyd vir my om te spring
terug na die rooi terugkeer adres.

244
00:11:02,400 --> 00:11:06,070
Maar omdat hy of sy een of ander manier
oorvleuel wat terugkeer adres

245
00:11:06,070 --> 00:11:09,602
met hul eie nommer,
en hulle is slim genoeg

246
00:11:09,602 --> 00:11:11,560
het ingestel wat
nommer te verwys, as jy

247
00:11:11,560 --> 00:11:13,740
sien in die super top
linkerhoek daar,

248
00:11:13,740 --> 00:11:18,020
die werklike adres in die rekenaar se
geheue van 'n paar van hul aanval kode,

249
00:11:18,020 --> 00:11:21,740
'n slegte man kan die rekenaar mislei
in die uitvoering van sy of haar eie kode.

250
00:11:21,740 --> 00:11:23,700
>> En dat kode, weer, kan enigiets wees.

251
00:11:23,700 --> 00:11:26,120
Dit is algemeen bekend as
dop kode, wat net

252
00:11:26,120 --> 00:11:29,030
'n manier om te sê dat dit nie
algemeen iets so eenvoudig soos rm-rf.

253
00:11:29,030 --> 00:11:32,340
Dit is eintlik iets soos Bash,
of 'n werklike program wat hom gee

254
00:11:32,340 --> 00:11:37,230
of haar programmatiese beheer uit te voer
enigiets anders wat hulle wil.

255
00:11:37,230 --> 00:11:40,210
Dus, in kort, dit alles
afgelei van die eenvoudige feit

256
00:11:40,210 --> 00:11:44,490
dat hierdie fout betrokke nie nagaan
die grense van jou skikking.

257
00:11:44,490 --> 00:11:47,250
En omdat die pad
rekenaars werk, is dat hulle

258
00:11:47,250 --> 00:11:49,430
gebruik die stapel van
effektief, konseptueel,

259
00:11:49,430 --> 00:11:54,830
onderaan, maar dan is die elemente
jy druk op die stapel groei top-down,

260
00:11:54,830 --> 00:11:56,624
dit is ongelooflik problematies.

261
00:11:56,624 --> 00:11:58,290
Nou, daar is maniere om te werk om hierdie.

262
00:11:58,290 --> 00:12:00,800
En eerlik, daar is tale
mee te werk om hierdie.

263
00:12:00,800 --> 00:12:03,100
Java is immuun, byvoorbeeld,
hierdie spesifieke kwessie.

264
00:12:03,100 --> 00:12:04,110
Omdat hulle gee jou nie wysers.

265
00:12:04,110 --> 00:12:05,943
Hulle gee jou nie
direkte geheue adresse.

266
00:12:05,943 --> 00:12:08,560
So met hierdie krag wat ons het
enigiets in die geheue aan te raak

267
00:12:08,560 --> 00:12:11,580
Ons wil kom, weliswaar 'n groot risiko.

268
00:12:11,580 --> 00:12:12,430
>> So hou 'n oog uit.

269
00:12:12,430 --> 00:12:14,596
As, eerlik, in die maande
of jare om te kom, enige tyd

270
00:12:14,596 --> 00:12:17,740
jy lees oor 'n paar uitbuiting
van 'n program of 'n bediener,

271
00:12:17,740 --> 00:12:22,370
as jy ooit sien 'n wenk van iets
soos 'n buffer oorloop aanval,

272
00:12:22,370 --> 00:12:25,390
of stapel oorloop is 'n ander soort
van die aanval, soortgelyk in die gees,

273
00:12:25,390 --> 00:12:28,770
soveel as inspireer die webwerf se
noem, as jy dit weet,

274
00:12:28,770 --> 00:12:33,170
dit is al praat net
oorstroom die grootte van 'n paar karakter

275
00:12:33,170 --> 00:12:36,200
skikking of 'n skikking meer algemeen.

276
00:12:36,200 --> 00:12:38,822
Enige vrae, dan, op hierdie?

277
00:12:38,822 --> 00:12:39,780
Moenie probeer om dit by die huis nie.

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

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

280
00:12:42,300 --> 00:12:47,270
So malloc dusver het ons nuwe
vriend in wat ons geheue toeken

281
00:12:47,270 --> 00:12:50,540
dat ons weet nie noodwendig in
bevorder wat ons wil hê, sodat ons het nie

282
00:12:50,540 --> 00:12:52,920
om hard te kode in ons
program getalle soos 12.

283
00:12:52,920 --> 00:12:55,550
Sodra die gebruiker vertel ons hoeveel
data wat hy of sy wil invoer,

284
00:12:55,550 --> 00:12:58,000
ons kan malloc dat baie geheue.

285
00:12:58,000 --> 00:13:01,484
>> So malloc dit blyk, aan die
mate het ons dit gebruik,

286
00:13:01,484 --> 00:13:03,900
uitdruklik laaste keer, en dan
julle ouens gebruik dit

287
00:13:03,900 --> 00:13:08,160
vir getstring onwetend vir
'n paar weke, al malloc se geheue

288
00:13:08,160 --> 00:13:09,820
kom van die sogenaamde hoop.

289
00:13:09,820 --> 00:13:13,852
En dit is die rede waarom getstring, byvoorbeeld,
kan geheue dinamies ken

290
00:13:13,852 --> 00:13:16,060
sonder om te weet wat jy
gaan om te tik in advance,

291
00:13:16,060 --> 00:13:21,520
hand wat jy terug 'n wyser na daardie geheue,
en dat die geheue is nog joune te hou,

292
00:13:21,520 --> 00:13:24,080
selfs nadat getstring opbrengste.

293
00:13:24,080 --> 00:13:27,450
Omdat herroeping na alles wat die
stapel is voortdurend op en af,

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

295
00:13:27,950 --> 00:13:30,230
En so gou as wat dit gaan
af, wat beteken dat 'n geheue

296
00:13:30,230 --> 00:13:33,030
hierdie funksie moet gebruik
nie gebruik word deur enigiemand anders.

297
00:13:33,030 --> 00:13:34,570
Dit is vullis waardes nou.

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

299
00:13:36,120 --> 00:13:39,360
En wat is lekker oor malloc is dat
wanneer malloc ken geheue hier,

300
00:13:39,360 --> 00:13:42,070
dit is nie 'n impak, vir die
grootste deel, deur die stapel.

301
00:13:42,070 --> 00:13:46,000
En so 'n funksie kan toegang
geheue wat malloc'd,

302
00:13:46,000 --> 00:13:49,120
selfs deur 'n funksie soos getstring,
selfs nadat dit teruggebring word.

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

304
00:13:51,700 --> 00:13:53,900
En inderdaad, die reël wat jy
nodig het om te begin die aanneming

305
00:13:53,900 --> 00:13:58,950
enige, enige, enige tyd wat jy malloc gebruik
jy moet jouself gebruik vry, uiteindelik,

306
00:13:58,950 --> 00:14:00,280
op dieselfde wyser.

307
00:14:00,280 --> 00:14:03,289
Al hierdie tyd het ons skryf
karretjie, karretjie kode, vir baie redes.

308
00:14:03,289 --> 00:14:05,580
Maar een van wat reeds
gebruik van die CS50 biblioteek, wat

309
00:14:05,580 --> 00:14:09,010
self is doelbewus
karretjie, dit lek geheue.

310
00:14:09,010 --> 00:14:11,410
Enige tyd wat jy het getstring genoem
oor die afgelope paar weke

311
00:14:11,410 --> 00:14:13,870
ons die bedryfstelsel is te vra
stelsel, Linux, vir die geheue.

312
00:14:13,870 --> 00:14:15,780
En jy het nog nie een keer terug gegee het.

313
00:14:15,780 --> 00:14:17,730
En dit is nie, in
oefen, 'n goeie ding.

314
00:14:17,730 --> 00:14:20,330
>> En Valgrind, een van die
gereedskap wat in Pset 4,

315
00:14:20,330 --> 00:14:22,900
is alles oor jou te help
vind nou foute soos dit.

316
00:14:22,900 --> 00:14:27,060
Maar gelukkig vir Pset 4 jy hoef nie
die CS50 biblioteek of getstring te gebruik.

317
00:14:27,060 --> 00:14:31,220
So enige foute met betrekking tot die geheue is
uiteindelik gaan jou eie wees.

318
00:14:31,220 --> 00:14:34,060
>> So malloc is meer as net
gerieflik vir hierdie doel.

319
00:14:34,060 --> 00:14:37,420
Ons kan eintlik nou op te los
fundamenteel verskillende probleme,

320
00:14:37,420 --> 00:14:41,640
en fundamenteel probleme op te los meer
effektief as per week nul se belofte.

321
00:14:41,640 --> 00:14:44,720
Tot dusver is dit die mees sexy
data struktuur wat ons gehad het.

322
00:14:44,720 --> 00:14:47,804
En deur die data struktuur ek net beteken
'n manier van konseptualisering geheue

323
00:14:47,804 --> 00:14:50,720
op 'n manier wat verder gaan as net sê,
dit is 'n int, dit is 'n teken.

324
00:14:50,720 --> 00:14:52,930
Ons kan begin cluster dinge saam.

325
00:14:52,930 --> 00:14:54,460
>> So 'n skikking lyk soos hierdie.

326
00:14:54,460 --> 00:14:57,270
En wat die sleutel in ongeveer 'n was
skikking is dat dit gee jou

327
00:14:57,270 --> 00:14:59,724
rug-aan-rug stukke
geheue, wat elk

328
00:14:59,724 --> 00:15:02,765
gaan word van dieselfde soort, int,
int, int, int, of kar, kar, kar,

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

330
00:15:03,330 --> 00:15:04,496
Maar daar is 'n paar nadele.

331
00:15:04,496 --> 00:15:06,570
Dit is byvoorbeeld
'n verskeidenheid van grootte ses.

332
00:15:06,570 --> 00:15:10,650
Veronderstel jy hierdie verskeidenheid vul met ses
nommers en dan, om watter redes,

333
00:15:10,650 --> 00:15:13,187
jou gebruikers wil gee
jy 'n sewende nommer.

334
00:15:13,187 --> 00:15:14,020
Waar het jy dit doen?

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

336
00:15:15,490 --> 00:15:18,990
>> Wat is die oplossing as jy '
geskep het 'n skikking op die stapel te plaas,

337
00:15:18,990 --> 00:15:22,030
byvoorbeeld, net met die week
twee notasie wat ons lei,

338
00:15:22,030 --> 00:15:23,730
vierkante hakies met 'n aantal binne?

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

340
00:15:25,160 --> 00:15:27,260
Wel, jy het ses
getalle in hierdie bokse.

341
00:15:27,260 --> 00:15:28,530
Wat sou jou instink wees?

342
00:15:28,530 --> 00:15:29,973
Waar sal jy wil om dit te sit?

343
00:15:29,973 --> 00:15:30,860
>> Publiek: [onhoorbaar]

344
00:15:30,860 --> 00:15:31,315
>> David J. Malan Jammer?

345
00:15:31,315 --> 00:15:32,380
>> Publiek: Sit dit op die einde.

346
00:15:32,380 --> 00:15:33,796
>> David J. Malan Sit dit op die einde.

347
00:15:33,796 --> 00:15:35,880
So net meer aan die regterkant,
buite die boks.

348
00:15:35,880 --> 00:15:38,710
Watter sal lekker wees, maar dit
blyk jy kan dit nie doen nie.

349
00:15:38,710 --> 00:15:41,350
Want as jy het nie gevra
vir hierdie stuk van die geheue,

350
00:15:41,350 --> 00:15:44,490
dit kan wees deur toeval dat hierdie
gebruik word deur 'n ander veranderlike

351
00:15:44,490 --> 00:15:45,030
geheel en al.

352
00:15:45,030 --> 00:15:49,210
Dink terug 'n week of so wanneer ons gelê
uit Zamyla en Davin en Gabe se name

353
00:15:49,210 --> 00:15:49,930
in die geheue.

354
00:15:49,930 --> 00:15:51,638
Hulle was letterlik
rug aan rug aan rug.

355
00:15:51,638 --> 00:15:53,550
So kan ons nie noodwendig
vertrou dat alles se

356
00:15:53,550 --> 00:15:55,800
hier is vir my om te gebruik.

357
00:15:55,800 --> 00:15:56,990
>> So wat anders kan jy doen?

358
00:15:56,990 --> 00:16:00,282
Wel, een keer besef jy
nodig om 'n verskeidenheid van grootte sewe,

359
00:16:00,282 --> 00:16:02,490
jy kan net 'n
verskeidenheid van grootte sewe gebruik dan

360
00:16:02,490 --> 00:16:05,950
'n lus vir die of 'n while lus,
kopieer dit in die nuwe skikking,

361
00:16:05,950 --> 00:16:09,680
en dan een of ander manier net ontslae te raak van
hierdie reeks of net ophou om dit te gebruik.

362
00:16:09,680 --> 00:16:12,130
Maar dit is nie baie doeltreffend nie.

363
00:16:12,130 --> 00:16:15,340
In kort, skikkings moenie
jy dinamiese grootte.

364
00:16:15,340 --> 00:16:17,900
>> So aan die een kant jy
ewetoeganklike, wat is ongelooflik.

365
00:16:17,900 --> 00:16:20,108
Omdat dit laat ons dinge doen
soos verdeel en oorwin,

366
00:16:20,108 --> 00:16:23,100
binêre soek, al wat ons het
gepraat oor op die skerm hier.

367
00:16:23,100 --> 00:16:24,950
Maar jy jouself verf in 'n hoek.

368
00:16:24,950 --> 00:16:27,810
Sodra jy getref
die einde van jou skikking,

369
00:16:27,810 --> 00:16:29,980
jy het 'n baie te doen
duur operasie

370
00:16:29,980 --> 00:16:33,910
of skryf 'n hele klomp van die kode
nou gaan met die probleem.

371
00:16:33,910 --> 00:16:36,680
>> So, wat as plaas moes ons
iets genaamd 'n lys,

372
00:16:36,680 --> 00:16:38,820
of 'n geskakelde lys in die besonder?

373
00:16:38,820 --> 00:16:41,930
Wat as in plaas van om
reghoeke Terug op te back,

374
00:16:41,930 --> 00:16:45,730
ons het reghoeke dat 'n bietjie laat
bietjie wikkel kamer tussen hulle?

375
00:16:45,730 --> 00:16:49,670
En selfs al het ek hierdie geteken
prent of aangepas hierdie foto

376
00:16:49,670 --> 00:16:54,696
van een van die tekste hier om terug te wees
rug aan rug baie ordelike, in werklikheid,

377
00:16:54,696 --> 00:16:56,820
een van daardie reghoeke
kon hier in die geheue wees.

378
00:16:56,820 --> 00:16:58,028
Een van hulle kon hier wees.

379
00:16:58,028 --> 00:17:00,420
Een van hulle kon hier wees,
hier, en so meer.

380
00:17:00,420 --> 00:17:02,910
>> Maar wat as ons het,
in hierdie geval, pyle

381
00:17:02,910 --> 00:17:05,650
dat een of ander manier verbind hierdie
saam reghoeke?

382
00:17:05,650 --> 00:17:08,170
Inderdaad, het ons gesien dat 'n tegniese
inkarnasie van 'n pyl.

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

384
00:17:09,839 --> 00:17:13,710
Wat het ons in die afgelope
dae dat onder die enjinkap,

385
00:17:13,710 --> 00:17:15,210
verteenwoordigend is van 'n pyl?

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

387
00:17:16,290 --> 00:17:17,349
'N wyser, reg?

388
00:17:17,349 --> 00:17:19,780
>> So, wat as, in plaas van
net die stoor van die getalle,

389
00:17:19,780 --> 00:17:23,130
soos 9, 17, 22, 26, 34,
Wat gebeur as ons nie gestoor

390
00:17:23,130 --> 00:17:27,079
net 'n nommer, maar 'n wyser
langs elke sodanige nommer?

391
00:17:27,079 --> 00:17:30,690
So veel soos jy sou ryg 'n
naald deur 'n hele klomp van die stof,

392
00:17:30,690 --> 00:17:32,950
een of ander manier vasmaak dinge
saam, insgelyks kan

393
00:17:32,950 --> 00:17:35,550
ons met wysers, soos
geïnkarneer word deur pyle hier

394
00:17:35,550 --> 00:17:38,550
soort van saam te weef
hierdie individuele reghoeke

395
00:17:38,550 --> 00:17:41,780
deur effektief gebruik te maak van 'n wyser
langs elke nommer wat

396
00:17:41,780 --> 00:17:46,065
dui op 'n volgende nommer, wat
dui op sy beurt 'n volgende nommer?

397
00:17:46,065 --> 00:17:47,940
So met ander woorde, wat
As ons eintlik wou

398
00:17:47,940 --> 00:17:49,820
iets soos hierdie te implementeer?

399
00:17:49,820 --> 00:17:53,610
Wel ongelukkig hierdie reghoeke,
ten minste die een met 9, 17, 22,

400
00:17:53,610 --> 00:17:57,040
en so meer, dit is nie meer
mooi blokkies met 'n enkele nommers.

401
00:17:57,040 --> 00:17:59,960
Die onderste, reghoek
onder 9, byvoorbeeld,

402
00:17:59,960 --> 00:18:04,330
verteenwoordig wat moet
'n wyser, 32 stukkies.

403
00:18:04,330 --> 00:18:09,460
Nou, ek is nog nie bewus van enige data tipe
in C wat gee jou nie net 'n int

404
00:18:09,460 --> 00:18:11,630
maar 'n wyser heeltemal.

405
00:18:11,630 --> 00:18:15,020
>> So wat is die oplossing as ons wil
ons eie antwoord op hierdie uit te vind?

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

407
00:18:15,760 --> 00:18:16,640
>> Publiek: [onhoorbaar]

408
00:18:16,640 --> 00:18:17,360
>> David J. Malan Wat is dit?

409
00:18:17,360 --> 00:18:17,880
>> Publiek: Nuwe struktuur.

410
00:18:17,880 --> 00:18:19,590
>> David J. Malan Ja, so hoekom
het ons nie 'n nuwe struktuur,

411
00:18:19,590 --> 00:18:20,920
of in C, 'n struct?

412
00:18:20,920 --> 00:18:25,990
Ons het gesien hoe structs voor, indien kortliks
waar ons met 'n student struktuur

413
00:18:25,990 --> 00:18:27,780
soos hierdie, wat 'n naam en 'n huis gehad het.

414
00:18:27,780 --> 00:18:31,980
In Pset 3 tempo jy 'n hele gebruik
klomp van structs-- GRect en GOvals

415
00:18:31,980 --> 00:18:34,810
dat Stanford geskep
cluster inligting saam.

416
00:18:34,810 --> 00:18:38,580
So wat as ons hierdie selfde idee van
die term "typedef" en "struct,"

417
00:18:38,580 --> 00:18:42,890
en dan 'n paar student-spesifieke dinge,
en ontwikkel dit in die volgende:

418
00:18:42,890 --> 00:18:46,210
typedef struct node-- en knoop is
net 'n baie generiese rekenaarwetenskap

419
00:18:46,210 --> 00:18:49,980
term vir iets in 'n data struktuur,
'n houer in 'n data-struktuur.

420
00:18:49,980 --> 00:18:53,900
'N knoop ek eis gaan hê
'n int n, heeltemal eenvoudig,

421
00:18:53,900 --> 00:18:58,810
en dan 'n bietjie meer kripties,
hierdie tweede lyn, struct node * volgende.

422
00:18:58,810 --> 00:19:01,300
Maar in minder tegniese terme,
Wat is die tweede lyn

423
00:19:01,300 --> 00:19:02,980
van die kode binne-in die krulhakies?

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

425
00:19:03,737 --> 00:19:04,851
>> Publiek: [onhoorbaar]

426
00:19:04,851 --> 00:19:06,600
David J. Malan 'n
wyser na 'n ander knoop.

427
00:19:06,600 --> 00:19:09,910
So weliswaar, sintaksis 'n bietjie kripties.

428
00:19:09,910 --> 00:19:13,250
Maar as jy dit letterlik gelees,
Volgende is die naam van 'n veranderlike.

429
00:19:13,250 --> 00:19:14,410
Wat is die data tipe?

430
00:19:14,410 --> 00:19:18,206
Dit is 'n bietjie verbose hierdie tyd,
maar dit is van die tipe struct node *.

431
00:19:18,206 --> 00:19:22,960
Enige tyd wat ons het gesien iets ster wat
beteken dit is 'n verwysing na die data tipe.

432
00:19:22,960 --> 00:19:26,810
So volgende is blykbaar 'n
wyser na 'n struct node.

433
00:19:26,810 --> 00:19:28,310
>> Nou, wat is 'n struct node?

434
00:19:28,310 --> 00:19:31,044
Wel, sien jy sien die
dieselfde woorde regs bo.

435
00:19:31,044 --> 00:19:33,960
En inderdaad, jy sien ook die woord
"Knoop" hier aan die onderkant links.

436
00:19:33,960 --> 00:19:35,640
En dit is eintlik net 'n gerief.

437
00:19:35,640 --> 00:19:39,930
Let daarop dat in ons student definisie
daar is die woord "student" net een keer.

438
00:19:39,930 --> 00:19:42,510
En dit is omdat 'n student
voorwerp was nie self-referensiële.

439
00:19:42,510 --> 00:19:45,340
Daar is niks binnekant van 'n student
wat moet wys na 'n ander student,

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

441
00:19:45,610 --> 00:19:47,630
Dit sou soort wees
vreemd in die werklike wêreld.

442
00:19:47,630 --> 00:19:50,880
>> Maar met 'n knoop in 'n gekoppelde
lys, ons wil hê dat 'n knoop

443
00:19:50,880 --> 00:19:53,970
te referensiële aan 'n soortgelyke voorwerp wees.

444
00:19:53,970 --> 00:19:57,900
En so neem kennis van die verandering is hier nie
net wat binne-in die krulhakies.

445
00:19:57,900 --> 00:20:00,800
Maar ons voeg die woord "knoop"
aan die bokant sowel as

446
00:20:00,800 --> 00:20:02,930
dit toe te voeg aan die onderkant
in plaas van "student."

447
00:20:02,930 --> 00:20:06,000
En dit is net 'n tegniese detail
sodat, weer, jou data struktuur

448
00:20:06,000 --> 00:20:11,380
kan self-referensiële wees, sodat 'n
knoop kan wys nog so knoop.

449
00:20:11,380 --> 00:20:13,840
>> So, wat is hierdie uiteindelik
gaan beteken vir ons?

450
00:20:13,840 --> 00:20:17,560
Wel, een van hierdie dinge binne
is die inhoud van ons node.

451
00:20:17,560 --> 00:20:19,360
Hierdie ding hier,
regs bo, is net so

452
00:20:19,360 --> 00:20:20,860
wat weer kan ons verwys na onsself.

453
00:20:20,860 --> 00:20:23,401
En dan die buitenste dinge,
selfs al knoop is 'n nuwe term,

454
00:20:23,401 --> 00:20:25,500
miskien, dit is nog steeds die
dieselfde as student en wat

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

456
00:20:27,520 --> 00:20:31,095
>> So as ons wil nou te begin
die implementering van hierdie geskakelde lys,

457
00:20:31,095 --> 00:20:33,220
hoe kan ons vertaal
iets soos hierdie te kode?

458
00:20:33,220 --> 00:20:35,350
Wel, laat ons sien net 'n
voorbeeld van 'n program wat

459
00:20:35,350 --> 00:20:36,840
eintlik gebruik van 'n geskakelde lys.

460
00:20:36,840 --> 00:20:40,870
Onder vandag se verspreiding-kode
is 'n program genaamd Lys Zero.

461
00:20:40,870 --> 00:20:44,980
En as ek loop dit Ek het 'n super
eenvoudige GUI, grafiese gebruikerskoppelvlak,

462
00:20:44,980 --> 00:20:46,460
maar dit is regtig net printf.

463
00:20:46,460 --> 00:20:50,930
En nou het ek myself 'n paar spyskaart gegee
options-- verwyder, vul, Soek,

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

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

466
00:20:52,630 --> 00:20:55,970
Dit is net 'n gemeenskaplike bedrywighede op 'n
data struktuur bekend as 'n skakel lys.

467
00:20:55,970 --> 00:20:58,409
>> Nou, verwyder gaan
verwyder 'n aantal van die lys.

468
00:20:58,409 --> 00:21:00,200
Insetsel gaan voeg
'n aantal van die lys.

469
00:21:00,200 --> 00:21:02,181
Soek gaan om te kyk
vir die aantal in die lys.

470
00:21:02,181 --> 00:21:04,930
En deurkruis is net 'n fancy manier
sê, loop deur die lys,

471
00:21:04,930 --> 00:21:06,245
druk dit uit, maar dit is dit.

472
00:21:06,245 --> 00:21:07,720
Moet dit verander nie in enige manier.

473
00:21:07,720 --> 00:21:08,570
>> So laat ons probeer om hierdie.

474
00:21:08,570 --> 00:21:10,160
Kom ons gaan voort en tik 2.

475
00:21:10,160 --> 00:21:12,710
En dan gaan ek
voeg die nommer, sê 9.

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

477
00:21:13,620 --> 00:21:17,480
En nou is my program is net
geprogrammeer om te sê, lys is nou 9.

478
00:21:17,480 --> 00:21:20,190
Nou, as ek gaan voort en
nie Voeg weer laat

479
00:21:20,190 --> 00:21:23,680
my voort te gaan en zoom uit en tik in 17.

480
00:21:23,680 --> 00:21:25,770
Nou is my lys is 9, dan is 17.

481
00:21:25,770 --> 00:21:27,750
As ek dit doen voeg weer laat slaan een.

482
00:21:27,750 --> 00:21:32,400
In plaas van 22, soos per die prentjie wat ons het
is op soek na hier, laat my voor te spring

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

484
00:21:34,630 --> 00:21:36,230
So ek gaan om te tik 26.

485
00:21:36,230 --> 00:21:37,755
Die lys is soos ek verwag.

486
00:21:37,755 --> 00:21:40,630
Maar nou, net om te sien of hierdie kode
gaan om buigsaam te wees, laat my nou

487
00:21:40,630 --> 00:21:43,520
tipe 22, waarvan ten minste
konseptueel, as ons

488
00:21:43,520 --> 00:21:46,520
Hou dit gesorteer, wat is inderdaad
gaan nou 'n ander doel te wees,

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

490
00:21:48,690 --> 00:21:50,270
So ek druk Enter.

491
00:21:50,270 --> 00:21:51,380
Inderdaad, wat werk.

492
00:21:51,380 --> 00:21:54,950
En so nou laat my plaas die
laaste, volgens die prentjie, 34.

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

494
00:21:55,450 --> 00:21:58,980
So vir nou, laat my bepaal dat
Verwyder en loop en soek nie,

495
00:21:58,980 --> 00:21:59,760
in werklikheid, werk.

496
00:21:59,760 --> 00:22:04,180
In werklikheid, as ek loop soek, laat
soek vir die nommer 22, Tik.

497
00:22:04,180 --> 00:22:05,010
Dit het bevind dat 22.

498
00:22:05,010 --> 00:22:07,580
So dit is wat hierdie
program Lys Zero doen.

499
00:22:07,580 --> 00:22:10,230
>> Maar wat eintlik gaan
op daardie implemente dit?

500
00:22:10,230 --> 00:22:14,530
Wel, die eerste wat ek mag hê, en inderdaad
Ek het 'n lêer genaamd list0.h.

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

502
00:22:16,540 --> 00:22:20,690
En iewers in daar is dit
lyn, typedef, struct node,

503
00:22:20,690 --> 00:22:24,850
dan het ek my krulhakies, int n, en
dan struct-- wat was die definisie?

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

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

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

507
00:22:29,920 --> 00:22:31,045
Dus moet ons die sterre.

508
00:22:31,045 --> 00:22:33,420
Nou tegnies kry ons in
die gewoonte van die opstel is dit hier.

509
00:22:33,420 --> 00:22:35,670
Jy kan sien en handboeke
aanlyn verwysings doen dit daar.

510
00:22:35,670 --> 00:22:36,660
Dit is funksioneel ekwivalent.

511
00:22:36,660 --> 00:22:37,980
In werklikheid, dit is 'n bietjie meer tipies.

512
00:22:37,980 --> 00:22:40,563
Maar ek sal in ooreenstemming met wat in
ons het die laaste tyd en dit doen.

513
00:22:40,563 --> 00:22:42,350
En dan laastens, ek gaan om dit te doen.

514
00:22:42,350 --> 00:22:45,550
>> So in 'n kop-lêer
iewers in list0.h

515
00:22:45,550 --> 00:22:49,200
vandag is dit struct definisie,
en miskien 'n paar ander dinge.

516
00:22:49,200 --> 00:22:52,580
Intussen is in list0c daar
gaan 'n paar dinge om te wees.

517
00:22:52,580 --> 00:22:54,740
Maar ons gaan net
begin en nie voltooi nie.

518
00:22:54,740 --> 00:22:59,690
List0.h is 'n lêer wat ek wil
in te sluit in my C-lêer.

519
00:22:59,690 --> 00:23:03,910
En dan op 'n sekere punt wat ek
gaan int te hê, hoof, tot niet.

520
00:23:03,910 --> 00:23:06,530
En dan gaan ek
het 'n paar te-doen is hier.

521
00:23:06,530 --> 00:23:10,620
Ek gaan ook 'n te hê
prototipe, soos leemte, soek, int,

522
00:23:10,620 --> 00:23:13,610
n, wie se doel in die lewe is
om te soek na 'n element.

523
00:23:13,610 --> 00:23:18,310
En dan hier Ek eis in
vandag se kode, nietig, soek, int, N,

524
00:23:18,310 --> 00:23:21,020
kommapunt maar oop krulhakies.

525
00:23:21,020 --> 00:23:25,049
En nou wil ek een of ander manier soek
vir 'n element in die lys.

526
00:23:25,049 --> 00:23:27,340
Maar ons het nie genoeg
inligting op die skerm nie.

527
00:23:27,340 --> 00:23:29,800
Ek het nie eintlik
verteenwoordig die lys self.

528
00:23:29,800 --> 00:23:33,070
So een manier waarop ons kan implementeer
'n geskakelde lys in 'n program

529
00:23:33,070 --> 00:23:37,520
is ek soort wil om iets te doen
soos verklaar gekoppel lys hier.

530
00:23:37,520 --> 00:23:40,520
Vir eenvoud, ek gaan maak
hierdie globale, selfs al in die algemeen ons

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

532
00:23:41,645 --> 00:23:43,260
Maar dit sal hierdie voorbeeld vereenvoudig.

533
00:23:43,260 --> 00:23:45,890
Dus wil ek verklaar
'n geskakelde lys hier.

534
00:23:45,890 --> 00:23:47,010
Nou, hoe kan ek dit doen?

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

536
00:23:48,810 --> 00:23:50,750
>> Hier is die foto van 'n geskakelde lys.

537
00:23:50,750 --> 00:23:53,030
En ek het nie regtig
weet op die oomblik hoe

538
00:23:53,030 --> 00:23:56,710
Ek gaan om te gaan oor verteenwoordig
so baie dinge met net een

539
00:23:56,710 --> 00:23:58,040
veranderlike in die geheue.

540
00:23:58,040 --> 00:23:59,160
Maar terug dink 'n oomblik.

541
00:23:59,160 --> 00:24:00,830
Al hierdie tyd wat ons gehad het
snare, wat ons dan

542
00:24:00,830 --> 00:24:02,913
geopenbaar skikkings te wees
karakters, wat ons dan

543
00:24:02,913 --> 00:24:05,740
geopenbaar om net 'n wyser
die eerste karakter

544
00:24:05,740 --> 00:24:08,890
in 'n verskeidenheid van die karakters
dit is null beëindig.

545
00:24:08,890 --> 00:24:13,530
So deur die logika, en met hierdie
prentjie soort loting jou gedagtes,

546
00:24:13,530 --> 00:24:17,964
Wat het ons eintlik skryf in ons
kode 'n geskakelde lys te verteenwoordig?

547
00:24:17,964 --> 00:24:21,130
Hoeveel van hierdie inligting het ons nodig
vas te vang in C-kode, sou jy sê?

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

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

550
00:24:23,154 --> 00:24:24,738
>> Publiek: Ons moet 'n verwysing na 'n knoop.

551
00:24:24,738 --> 00:24:26,237
David J. Malan 'n verwysing na 'n knoop.

552
00:24:26,237 --> 00:24:29,320
In die besonder, wat knoop sou jou
instink wees om 'n wyser te hou?

553
00:24:29,320 --> 00:24:30,026
>> Publiek: Die eerste knoop.

554
00:24:30,026 --> 00:24:31,942
>> David J. Malan Ja,
waarskynlik net die eerste.

555
00:24:31,942 --> 00:24:34,030
En sien, die eerste
knoop is 'n ander vorm.

556
00:24:34,030 --> 00:24:37,690
Dit is net die helfte van die grootte van die struct,
want dit is inderdaad net 'n wyser.

557
00:24:37,690 --> 00:24:44,650
So wat jy wel kan doen is om te verklaar
'n geskakelde lys te wees van die tipe knoop *.

558
00:24:44,650 --> 00:24:47,780
En laat ons net noem dit die eerste
en inisialiseer te null.

559
00:24:47,780 --> 00:24:49,910
So nul, weer, is komende
in die prentjie hier.

560
00:24:49,910 --> 00:24:53,620
Nie net is nul as soos 'n spesiale
terugkeer waarde vir dinge soos getstring

561
00:24:53,620 --> 00:24:57,770
en malloc, nietig is ook die nul
wyser, die gebrek aan 'n wyser,

562
00:24:57,770 --> 00:24:58,430
as jy wil.

563
00:24:58,430 --> 00:25:00,309
Dit beteken net mooi niks is nog hier.

564
00:25:00,309 --> 00:25:02,100
Nou eers kan ek het
noem dit niks.

565
00:25:02,100 --> 00:25:04,200
Ek kon genoem het dit "lys"
of enige aantal ander dinge.

566
00:25:04,200 --> 00:25:06,960
Maar ek noem dit "die eerste" sodat
dit in lyn is met hierdie prentjie.

567
00:25:06,960 --> 00:25:10,280
So net soos 'n string verteenwoordig kan word
met die adres van sy eerste byte,

568
00:25:10,280 --> 00:25:11,280
so kan 'n geskakelde lys.

569
00:25:11,280 --> 00:25:13,480
En ons sal ander data te sien
strukture verteenwoordig word

570
00:25:13,480 --> 00:25:16,700
met net een muis,
'n 32-bit pyl wys

571
00:25:16,700 --> 00:25:18,740
op die heel eerste node in die struktuur.

572
00:25:18,740 --> 00:25:20,340
>> Maar laat ons nou verwag 'n probleem.

573
00:25:20,340 --> 00:25:23,230
As ek net onthou
in my program die adres

574
00:25:23,230 --> 00:25:27,220
van die eerste knoop, die eerste
reghoek in hierdie data struktuur,

575
00:25:27,220 --> 00:25:31,760
wat beter wees om die saak oor die
implementering van die res van my lys?

576
00:25:31,760 --> 00:25:35,820
Wat is 'n belangrike detail wat gaan
om te verseker dat dit eintlik werk?

577
00:25:35,820 --> 00:25:39,250
En deur die "eintlik werk" Ek
bedoel, baie soos 'n string,

578
00:25:39,250 --> 00:25:42,180
laat ons gaan van die eerste karakter
in Davin se naam na die tweede,

579
00:25:42,180 --> 00:25:44,755
na die derde, aan die
vierde, tot op die einde,

580
00:25:44,755 --> 00:25:47,880
Hoe weet ons wanneer ons aan die einde
van 'n geskakelde lys wat lyk soos hierdie?

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

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

583
00:25:50,660 --> 00:25:53,640
En ek het hierdie soort van soos verteenwoordig
soos 'n elektriese ingenieur mag,

584
00:25:53,640 --> 00:25:56,420
met die bietjie grou
simbool, van spesies.

585
00:25:56,420 --> 00:25:58,246
Maar dit beteken net nul in hierdie geval.

586
00:25:58,246 --> 00:26:00,370
Jy kan dit teken 'n aantal
maniere, maar hierdie skrywer

587
00:26:00,370 --> 00:26:02,800
gebeur hierdie simbool om hier te gebruik.

588
00:26:02,800 --> 00:26:06,260
>> So lank as wat ons bedrading
al hierdie nodes saam

589
00:26:06,260 --> 00:26:08,600
net onthou waar
die eerste een is, so lank

590
00:26:08,600 --> 00:26:11,760
as ons 'n spesiale simbool op
die heel laaste knoop in die lys,

591
00:26:11,760 --> 00:26:15,130
en ons sal gebruik nul, want dit is
wat ons tot ons beskikking,

592
00:26:15,130 --> 00:26:16,480
hierdie lys is voltooi.

593
00:26:16,480 --> 00:26:20,190
En selfs as ek net gee jou 'n wyser na
die eerste element, julle, die programmeerder,

594
00:26:20,190 --> 00:26:22,486
kan seker toegang tot die res van dit.

595
00:26:22,486 --> 00:26:24,360
Maar laat ons laat jou gedagtes
dwaal 'n bietjie,

596
00:26:24,360 --> 00:26:26,140
as hulle nie reeds
heel wandered-- wat is

597
00:26:26,140 --> 00:26:28,723
gaan die loop van die tyd te wees
die vind van iets in die lys?

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

599
00:26:30,450 --> 00:26:33,470
Damn dit, dit is 'n groot O van n,
wat is nie sleg nie, in regverdigheid.

600
00:26:33,470 --> 00:26:34,800
Maar dit is lineêr.

601
00:26:34,800 --> 00:26:37,980
Ons het opgegee wat funksie
van skikkings deur die verskuiwing van meer

602
00:26:37,980 --> 00:26:43,130
na hierdie foto van dinamiese
aanmekaar geweef of verbind nodes?

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

604
00:26:44,970 --> 00:26:46,687
Ons het opgegee ewekansige toegang.

605
00:26:46,687 --> 00:26:48,770
'N skikking is mooi, want
wiskundig alles

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

607
00:26:50,340 --> 00:26:52,370
Selfs al is hierdie foto
lyk mooi, en selfs

608
00:26:52,370 --> 00:26:55,830
al is dit lyk soos hierdie nodes
is mooi afstand van mekaar, in werklikheid

609
00:26:55,830 --> 00:26:56,830
hulle oral te kan wees.

610
00:26:56,830 --> 00:27:01,590
OX1, Ox50, Ox123, Ox99 hierdie
nodes kan enige plek wees.

611
00:27:01,590 --> 00:27:05,960
Omdat malloc nie ken geheue
van die hoop, maar nêrens in die hoop.

612
00:27:05,960 --> 00:27:09,080
Jy nie noodwendig weet dat dit
gaan om terug te wees om terug te rug.

613
00:27:09,080 --> 00:27:12,460
En so hierdie foto in werklikheid se
nie gaan baie van hierdie mooi.

614
00:27:12,460 --> 00:27:16,140
>> So dit gaan 'n bietjie van te neem
werk om hierdie funksie te implementeer.

615
00:27:16,140 --> 00:27:17,880
So laat implementeer soek nou.

616
00:27:17,880 --> 00:27:20,250
En ons sal sien die soort van 'n
slim manier om dit te doen.

617
00:27:20,250 --> 00:27:24,660
So as ek 'n soek funksie en
Ek kry 'n veranderlike, heelgetal n

618
00:27:24,660 --> 00:27:28,490
om te kyk, ek nodig het om te weet die
nuwe sintaksis vir die soek binne

619
00:27:28,490 --> 00:27:32,400
van 'n struktuur wat
wys na, te vind N.

620
00:27:32,400 --> 00:27:33,210
So laat ons dit doen.

621
00:27:33,210 --> 00:27:36,030
>> So eerste ek gaan om te gaan
voort en verklaar 'n knoop *.

622
00:27:36,030 --> 00:27:39,400
En ek gaan om dit te noem
wyser, net deur konvensie.

623
00:27:39,400 --> 00:27:41,710
En ek gaan om dit te inisialiseer eerste.

624
00:27:41,710 --> 00:27:43,770
En nou kan ek dit doen
in 'n aantal maniere.

625
00:27:43,770 --> 00:27:45,436
Maar ek gaan 'n gemeenskaplike benadering te neem.

626
00:27:45,436 --> 00:27:50,180
Terwyl wyser is nie gelyk aan
nul, en dit is geldig sintaksis.

627
00:27:50,180 --> 00:27:54,550
En dit beteken net die volgende doen, sodat
Solank as wat jy nie wys op niks.

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

629
00:27:55,800 --> 00:28:01,939
>> As wyser dot n, laat my terug te kom
dat, gelyk equals-- wat?

630
00:28:01,939 --> 00:28:03,105
Watter waarde is ek op soek na?

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

632
00:28:04,920 --> 00:28:06,590
Die werklike N wat in geslaag is.

633
00:28:06,590 --> 00:28:09,020
So hier is nog 'n kenmerk
van C en baie ander tale.

634
00:28:09,020 --> 00:28:13,705
Selfs al is die struktuur genoem knoop
het 'n waarde n, heeltemal wettig

635
00:28:13,705 --> 00:28:17,530
om ook 'n plaaslike argument
of veranderlike genoem n.

636
00:28:17,530 --> 00:28:20,085
Omdat selfs ons met
menslike oë kan onderskei

637
00:28:20,085 --> 00:28:22,087
dat dit n vermoedelik
verskil van die N.

638
00:28:22,087 --> 00:28:23,420
Omdat die sintaksis is anders.

639
00:28:23,420 --> 00:28:26,211
Jy het 'n kol en 'n wyser,
terwyl hierdie een het nie so 'n ding.

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

641
00:28:27,290 --> 00:28:29,120
Dit is OK om dieselfde dinge te noem.

642
00:28:29,120 --> 00:28:32,380
>> As ek jy dit doen, ek is
gaan wil om iets te doen

643
00:28:32,380 --> 00:28:35,000
soos kondig dat ons gevind n.

644
00:28:35,000 --> 00:28:37,930
En ons sal laat dit as 'n
kommentaar of pseudokode kode.

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

646
00:28:40,190 --> 00:28:47,320
doen wat ek wil doen as die huidige knoop
nie met n dat ek omgee?

647
00:28:47,320 --> 00:28:50,700
Hoe om die volgende te bereik nie?

648
00:28:50,700 --> 00:28:53,710
As my vinger op die
oomblik is PTR, en dit is

649
00:28:53,710 --> 00:28:55,920
wys op watter
eerste wys op,

650
00:28:55,920 --> 00:28:59,290
Hoe kan ek my vinger
na die volgende knoop in die kode?

651
00:28:59,290 --> 00:29:01,915
Wel, wat is die bread ons
gaan volg in hierdie geval?

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

653
00:29:03,464 --> 00:29:04,380
Publiek: [onhoorbaar].

654
00:29:04,380 --> 00:29:05,630
David J. Malan Ja, so volgende.

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

656
00:29:06,640 --> 00:29:09,824
So as ek gaan terug na my
kode hier, wel, ek is

657
00:29:09,824 --> 00:29:12,990
gaan om voort te gaan en sê wyser, wat
is net 'n tydelike variable-- dit

658
00:29:12,990 --> 00:29:15,320
'n vreemde naam, ptr, maar
dit is net soos temp--

659
00:29:15,320 --> 00:29:19,234
Ek gaan wyser te stel
gelyk aan alles wat wyser is--

660
00:29:19,234 --> 00:29:22,150
en weer, dit gaan 'n te wees
karretjie vir 'n moment-- dot volgende.

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

662
00:29:23,551 --> 00:29:26,550
Met ander woorde, ek gaan neem my
vinger wat is wys hierdie knoop

663
00:29:26,550 --> 00:29:31,247
hier en ek gaan om te sê, jy weet
wat, 'n blik op die volgende gebied

664
00:29:31,247 --> 00:29:33,330
en beweeg jou vinger
wat dit is wys.

665
00:29:33,330 --> 00:29:35,163
En dit gaan
herhaal, herhaal, herhaal.

666
00:29:35,163 --> 00:29:37,630
Maar toe het my vinger
stop om iets te doen nie?

667
00:29:37,630 --> 00:29:40,095
Sodra watter lyn van die kode skop in?

668
00:29:40,095 --> 00:29:40,970
Publiek: [onhoorbaar]

669
00:29:40,970 --> 00:29:43,060
David J. Malan As punt terwyl
wyser is nie gelyk aan null.

670
00:29:43,060 --> 00:29:44,900
Op 'n stadium my vinger se
gaan word wat dui op nul

671
00:29:44,900 --> 00:29:47,070
en ek gaan om te besef
dit is die einde van die lys.

672
00:29:47,070 --> 00:29:48,910
Nou, dit is 'n bietjie
wit leuen vir eenvoud.

673
00:29:48,910 --> 00:29:51,580
Dit blyk dat selfs al is ons
Net hierdie dot-notasie geleer

674
00:29:51,580 --> 00:29:55,220
vir strukture, wyser is nie 'n struct.

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

676
00:29:56,580 --> 00:29:58,350
Net om te wees meer nitpicky.

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

678
00:29:59,720 --> 00:30:01,360
Dit is 'n verwysing na 'n knoop.

679
00:30:01,360 --> 00:30:03,120
Dit is nie 'n knoop self.

680
00:30:03,120 --> 00:30:06,650
As ek het geen sterre hier, wyser
absolutely-- dit is 'n knoop.

681
00:30:06,650 --> 00:30:08,650
Dit is soos 'n week een
verklaring van 'n veranderlike,

682
00:30:08,650 --> 00:30:10,120
selfs al is die woord "knoop" is 'n nuwe.

683
00:30:10,120 --> 00:30:13,860
>> Maar so gou as ons 'n
ster, dit is nou 'n verwysing na 'n knoop.

684
00:30:13,860 --> 00:30:17,960
En ongelukkig kan jy nie gebruik
die dot-notasie vir 'n muis.

685
00:30:17,960 --> 00:30:21,070
Jy het die pyl te gebruik
notasie, wat opvallend,

686
00:30:21,070 --> 00:30:23,470
is die eerste keer 'n stuk
van sintaksis lyk intuïtief.

687
00:30:23,470 --> 00:30:25,245
Dit lyk letterlik soos 'n pyl.

688
00:30:25,245 --> 00:30:26,370
En so is dit 'n goeie ding.

689
00:30:26,370 --> 00:30:28,995
En hier letterlik
lyk soos 'n pyl.

690
00:30:28,995 --> 00:30:31,870
So ek dink dit is die la-- ek doen nie
dink ek oor-die pleeg here-- ek

691
00:30:31,870 --> 00:30:34,120
dink dit is die laaste nuwe stuk
van sintaksis ons gaan om te sien.

692
00:30:34,120 --> 00:30:36,500
En gelukkig, dit is inderdaad
'n bietjie meer intuïtief.

693
00:30:36,500 --> 00:30:40,090
>> Nou, vir dié van julle wat
mag verkies om die ou manier,

694
00:30:40,090 --> 00:30:42,550
jy kan nog steeds gebruik maak van die dot-notasie.

695
00:30:42,550 --> 00:30:45,380
Maar as per Maandag se
gesprek, ons eerste

696
00:30:45,380 --> 00:30:50,530
nodig om daar te gaan, gaan na daardie
spreek, en dan toegang tot die gebied.

697
00:30:50,530 --> 00:30:51,897
So is dit ook reg.

698
00:30:51,897 --> 00:30:53,730
En eerlik, dit is 'n
bietjie meer pedanties.

699
00:30:53,730 --> 00:30:56,530
Jy letterlik gesê dereference
die wyser en gaan daar.

700
00:30:56,530 --> 00:30:59,320
Dan gryp .n, die veld genaamd n.

701
00:30:59,320 --> 00:31:01,370
Maar eerlik, niemand wil
om te tik of lees.

702
00:31:01,370 --> 00:31:03,620
En so het die wêreld uitgevind
die pyl notasie, wat

703
00:31:03,620 --> 00:31:06,980
gelykstaande is identies,
dit is net sintaktiese suiker.

704
00:31:06,980 --> 00:31:10,570
So 'n fancy manier om te sê hierdie
lyk beter, of lyk makliker.

705
00:31:10,570 --> 00:31:12,296
>> So nou gaan ek 'n ander ding om te doen.

706
00:31:12,296 --> 00:31:15,420
Ek gaan om te sê "breek" wanneer ek het
gevind dat dit so hou ek nie op soek na dit.

707
00:31:15,420 --> 00:31:17,620
Maar dit is die kern
van 'n soek funksie.

708
00:31:17,620 --> 00:31:21,710
Maar dit is 'n baie makliker, in die
einde, om nie te wandel deur die kode.

709
00:31:21,710 --> 00:31:25,570
Dit is inderdaad die formele implementering
soek in vandag se verspreiding-kode.

710
00:31:25,570 --> 00:31:30,530
Ek waag om te sê dat die insetsel is nie
veral pret deur te loop

711
00:31:30,530 --> 00:31:33,180
visueel, of is verwyder, selfs
al aan die einde van die dag

712
00:31:33,180 --> 00:31:35,460
hulle neer te regverdig
eenvoudige heuristiek.

713
00:31:35,460 --> 00:31:36,330
>> So laat ons dit doen.

714
00:31:36,330 --> 00:31:39,250
As jy sal humor my hier, ek het
bring 'n klomp van stres balle.

715
00:31:39,250 --> 00:31:40,620
Ek het 'n klomp van die nommers.

716
00:31:40,620 --> 00:31:46,562
En kan ons net 'n paar vrywilligers
9, 17, 20, 22, 29, 34 en voor te stel?

717
00:31:46,562 --> 00:31:48,270
So in wese almal
wie's hier vandag.

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

719
00:31:50,170 --> 00:31:52,760
Dit was een, twee, drie,
vier, vyf, ses mense.

720
00:31:52,760 --> 00:31:55,740
En ek het gevra om go-- sien, geen
een in die rug verhoog hul hande.

721
00:31:55,740 --> 00:32:01,910
OK, een, twee, drie, vier,
five-- laat my laai balance-- ses.

722
00:32:01,910 --> 00:32:03,051
OK, jy ses kom op.

723
00:32:03,051 --> 00:32:04,050
Ons sal ander mense nodig het.

724
00:32:04,050 --> 00:32:05,460
Ons het ekstra stres balle.

725
00:32:05,460 --> 00:32:08,200
En as jy kan, vir
net 'n oomblik, lyn

726
00:32:08,200 --> 00:32:10,490
julle het net
soos hierdie prentjie hier.

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

728
00:32:15,200 --> 00:32:15,959
>> Alle regte.

729
00:32:15,959 --> 00:32:17,125
Kom ons kyk, wat is jou 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,
jy is nommer 9.

732
00:32:18,800 --> 00:32:19,540
Nice om jou te ontmoet.

733
00:32:19,540 --> 00:32:20,400
Hier gaan jy.

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
Nommer 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: Ek is Julia.

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

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

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

745
00:32:28,507 --> 00:32:29,340
GEHOOR: Christen.

746
00:32:29,340 --> 00:32:30,715
David J. Malan Christen, David.

747
00:32:30,715 --> 00:32:31,541
Nommer 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
Nommer 29.

752
00:32:34,880 --> 00:32:37,080
So gaan voort en kry 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
Bystand.

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
Is daar iemand het 'n merker?

760
00:32:43,682 --> 00:32:44,890
Publiek: Ek het 'n Sharpie.

761
00:32:44,890 --> 00:32:45,660
David J. Malan Jy het 'n 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 nie almal het 'n stukkie van die papier?

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

766
00:32:51,562 --> 00:32:52,270
Slaan die lesing.

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: Ons het dit.

770
00:32:56,320 --> 00:32:57,600
David J. Malan Ons het dit?

771
00:32:57,600 --> 00:32:58,577
Alle reg, dankie.

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

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

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

775
00:33:03,582 --> 00:33:04,540
Jy moet net die dag gered.

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
Alle regte.

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

781
00:33:13,360 --> 00:33:14,890
Ek gespel 29, maar OK.

782
00:33:14,890 --> 00:33:15,720
Gaan voort.

783
00:33:15,720 --> 00:33:18,114
Alle reg, sal ek gee jou
jou pen terug 'n oomblik.

784
00:33:18,114 --> 00:33:19,280
So ons het hierdie mense hier.

785
00:33:19,280 --> 00:33:20,330
Kom ons 'n ander.

786
00:33:20,330 --> 00:33:23,750
Gabe, wil jy om te speel
die eerste element hier?

787
00:33:23,750 --> 00:33:25,705
Ons sal jou nodig om te wys
op hierdie pragtige mense.

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

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

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

791
00:33:32,160 --> 00:33:33,325
Het ons iemand verloor?

792
00:33:33,325 --> 00:33:33,950
Ek het 'n 34.

793
00:33:33,950 --> 00:33:36,730
Waar did-- OK, wat wil wees 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
Alle reg, sal dit
die moeite werd om die klimaks.

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

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

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

800
00:33:43,456 --> 00:33:46,810
Alle reg, so hier is 'n
n hele klomp van knope.

801
00:33:46,810 --> 00:33:49,060
Elkeen van julle ouens verteenwoordig
een van hierdie reghoeke.

802
00:33:49,060 --> 00:33:51,930
En Gabe, die effens vreemd
Man Out, verteenwoordig die eerste.

803
00:33:51,930 --> 00:33:54,850
So sy wyser is 'n bietjie kleiner
op die skerm as almal anders.

804
00:33:54,850 --> 00:33:58,120
En in hierdie geval, elkeen van die linkerkant
hande gaan óf wys af,

805
00:33:58,120 --> 00:34:01,085
daardeur verteenwoordig nul, so
net die afwesigheid van 'n muis,

806
00:34:01,085 --> 00:34:03,210
of dit gaan word wys
by 'n knoop langs jou.

807
00:34:03,210 --> 00:34:05,440
>> So nou as jy versier
julle soos die prentjie

808
00:34:05,440 --> 00:34:07,585
hier, gaan voort en punt
na mekaar, met Gabe

809
00:34:07,585 --> 00:34:11,030
in die besonder wys op
nommer 9 in die lys te verteenwoordig.

810
00:34:11,030 --> 00:34:14,050
OK, en die getal 34, jou linkerhand
moet net wys op die vloer.

811
00:34:14,050 --> 00:34:15,750
>> OK, so dit is die geskakelde lys.

812
00:34:15,750 --> 00:34:17,580
So dit is die scenario in die vraag.

813
00:34:17,580 --> 00:34:20,210
En inderdaad, hierdie is 'n verteenwoordiger
van 'n klas van probleme

814
00:34:20,210 --> 00:34:21,929
dat jy kan probeer om op te los met 'n kode.

815
00:34:21,929 --> 00:34:25,020
Jy wil om uiteindelik voeg
'n nuwe element in die lys.

816
00:34:25,020 --> 00:34:27,494
In hierdie geval, ons gaan
probeer om die invoer van die getal 55.

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

818
00:34:28,500 --> 00:34:30,860
Maar daar gaan wees
verskillende gevalle te oorweeg.

819
00:34:30,860 --> 00:34:34,409
En inderdaad, dit gaan om een ​​te wees
van die groot-prentjie wegneemetes hier is,

820
00:34:34,409 --> 00:34:35,659
Wat is die verskillende gevalle.

821
00:34:35,659 --> 00:34:39,120
Wat is die verskil as toestande of
takke wat jou program kan hê?

822
00:34:39,120 --> 00:34:42,024
>> Wel, die nommer wat jy probeer om te
insetsel, wat ons nou weet te wees 55,

823
00:34:42,024 --> 00:34:44,650
maar as jy nie geweet het nie
vooraf, ek daresay

824
00:34:44,650 --> 00:34:47,840
val in ten minste drie
moontlike situasies.

825
00:34:47,840 --> 00:34:49,717
Waar kan 'n nuwe element?

826
00:34:49,717 --> 00:34:51,050
Publiek: En die einde of die middel.

827
00:34:51,050 --> 00:34:54,150
David J. Malan Aan die einde, in
die middel, of by die begin.

828
00:34:54,150 --> 00:34:56,650
So ek beweer daar is ten minste
drie probleme wat ons moet oplos.

829
00:34:56,650 --> 00:34:58,691
Kom ons kies wat miskien
waarskynlik die eenvoudigste

830
00:34:58,691 --> 00:35:01,090
een, waar die nuwe element
behoort aan die begin.

831
00:35:01,090 --> 00:35:04,040
So ek gaan code te hou het
soos soek, wat ek net geskryf.

832
00:35:04,040 --> 00:35:07,670
En ek gaan ptr te hê, wat
Ek sal hier verteenwoordig met my vinger,

833
00:35:07,670 --> 00:35:08,370
soos gewoonlik.

834
00:35:08,370 --> 00:35:12,430
>> En onthou, watter waarde
het ons inisialiseer ptr te?

835
00:35:12,430 --> 00:35:15,300
So ons geïnisialiseer dit aanvanklik null.

836
00:35:15,300 --> 00:35:16,410

837
00:35:16,410 --> 00:35:19,770
Maar wat het ons doen wanneer ons
is in ons soek funksie?

838
00:35:19,770 --> 00:35:20,940

839
00:35:20,940 --> 00:35:24,870
Ons stel dit gelyk aan die eerste,
wat beteken nie om dit te doen.

840
00:35:24,870 --> 00:35:25,890

841
00:35:25,890 --> 00:35:30,570
As ek ptr gelykstaande aan die eerste, wat
moet my hand werklik wys?

842
00:35:30,570 --> 00:35:31,070
Right.

843
00:35:31,070 --> 00:35:33,290
So as ek en Gabe gaan
gelyke waardes om hier te wees,

844
00:35:33,290 --> 00:35:34,760
Ons moet beide punt op nommer 9.

845
00:35:34,760 --> 00:35:36,420
>> So dit was die begin van ons storie.

846
00:35:36,420 --> 00:35:38,700
En nou is dit net 'n eenvoudige,
selfs al is die sintaksis is 'n nuwe.

847
00:35:38,700 --> 00:35:40,580
Konseptueel dit is net lineêre soek.

848
00:35:40,580 --> 00:35:42,750
55 gelyk aan 9?

849
00:35:42,750 --> 00:35:45,559
Of eerder, kom ons sê minder as 9.

850
00:35:45,559 --> 00:35:47,600
Omdat ek probeer
uit te vind waar om te sit 55.

851
00:35:47,600 --> 00:35:51,270
Minder as 9, minder as 17, minder
as 20, minder as 22, minder as 29,

852
00:35:51,270 --> 00:35:52,510
minder as 34, no.

853
00:35:52,510 --> 00:35:55,080
So nou is ons in die geval
een van minstens drie.

854
00:35:55,080 --> 00:35:59,910
>> As ek wil voeg 55 hier, wat
reëls van die kode behoefte om tereggestel te raak?

855
00:35:59,910 --> 00:36:01,890
Hoe hierdie foto van
mense nodig het om te verander?

856
00:36:01,890 --> 00:36:03,181
Wat doen ek met my linkerhand?

857
00:36:03,181 --> 00:36:04,530

858
00:36:04,530 --> 00:36:07,360
Dit moet aanvanklik nul,
want ek is aan die einde van die lys.

859
00:36:07,360 --> 00:36:09,318
En wat moet gebeur
hier met Petrus, was dit?

860
00:36:09,318 --> 00:36:10,520

861
00:36:10,520 --> 00:36:12,430
Hy is natuurlik gaan om te wys vir my.

862
00:36:12,430 --> 00:36:15,580
So ek beweer daar is ten minste twee lyne
van die kode in die voorbeeld kode van vandag

863
00:36:15,580 --> 00:36:18,570
wat gaan om dit te implementeer
scenario van die toevoeging van 55 by die stert.

864
00:36:18,570 --> 00:36:20,950
En ek kon iemand hop
en net verteenwoordig 55?

865
00:36:20,950 --> 00:36:22,200
Alle reg, jy is die nuwe 55.

866
00:36:22,200 --> 00:36:23,580

867
00:36:23,580 --> 00:36:27,054
>> So nou wat as die volgende
scenario kom saam,

868
00:36:27,054 --> 00:36:29,720
en ons wil te voeg by die
begin of die hoof van die lys?

869
00:36:29,720 --> 00:36:31,100
En wat is jou naam, nommer 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, lekker om jou te ontmoet.

873
00:36:33,585 --> 00:36:34,210
Welkom aan boord.

874
00:36:34,210 --> 00:36:36,640
So nou gaan ons
voeg, sê, die nommer 5.

875
00:36:36,640 --> 00:36:39,840
Hier is die tweede geval van die
drie ons het met voor.

876
00:36:39,840 --> 00:36:43,050
So as 5 behoort aan die begin,
Kom ons kyk hoe ons uitvind.

877
00:36:43,050 --> 00:36:46,310
Ek inisialiseer my ptr
wyser te nommer 9 weer.

878
00:36:46,310 --> 00:36:49,140
En ek besef, o, 5 minder as 9.

879
00:36:49,140 --> 00:36:50,880
So los hierdie foto vir ons.

880
00:36:50,880 --> 00:36:54,820
Wie se hande, Gabe se of David se
or-- wat is nommer 9 se 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 se hands--
wat van ons hande nodig om te verander?

883
00:36:58,406 --> 00:36:58,905

884
00:36:58,905 --> 00:37:00,970
OK, so Gabe wys na wat nou?

885
00:37:00,970 --> 00:37:01,640
Op my.

886
00:37:01,640 --> 00:37:02,750
Ek is die nuwe node.

887
00:37:02,750 --> 00:37:04,870
So sal ek net soort van beweging
hier is dit visueel sien.

888
00:37:04,870 --> 00:37:06,435
En intussen wat ek wys dit?

889
00:37:06,435 --> 00:37:07,910

890
00:37:07,910 --> 00:37:09,020
Steeds waar ek wys.

891
00:37:09,020 --> 00:37:10,000
So dit is dit.

892
00:37:10,000 --> 00:37:13,717
So net regtig een lyn van kode fixes
hierdie spesifieke probleem, sou dit lyk.

893
00:37:13,717 --> 00:37:14,800
Alle reg, sodat dit is goed.

894
00:37:14,800 --> 00:37:17,580
En kan iemand 'n plekhouer vir 5?

895
00:37:17,580 --> 00:37:18,080
Kom op.

896
00:37:18,080 --> 00:37:20,270

897
00:37:20,270 --> 00:37:21,320
Ons kry jy die volgende keer.

898
00:37:21,320 --> 00:37:24,280
>> Alle reg, sodat now-- en
As 'n eenkant, die name

899
00:37:24,280 --> 00:37:28,510
Ek is nie die maak melding van reg
nou, pred wyser, voorganger wyser

900
00:37:28,510 --> 00:37:31,260
en nuwe wyser, wat
net die name gegee

901
00:37:31,260 --> 00:37:35,280
in die voorbeeld kode aan die wysers of
my hande dit is soort van wys rond.

902
00:37:35,280 --> 00:37:36,060
Wat is jou 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
Alle reg, so laat ons nou kyk
'n Bietjie meer irriterende scenario,

907
00:37:42,180 --> 00:37:46,350
waardeur ek wil voeg
iets soos 26 in hierdie.

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
Hierdie are-- goeie ding ons het hierdie pen.

911
00:37:50,510 --> 00:37:51,955
Alle reg, 20.

912
00:37:51,955 --> 00:37:53,640

913
00:37:53,640 --> 00:37:57,570
As iemand kan nog 'n stukkie van kry
papier gereed, net in case-- alles reg.

914
00:37:57,570 --> 00:37:58,370
O, interessant.

915
00:37:58,370 --> 00:37:59,760

916
00:37:59,760 --> 00:38:02,390
Wel, dit is 'n voorbeeld
van 'n lesing fout.

917
00:38:02,390 --> 00:38:03,894
OK so wat is jou naam nou weer?

918
00:38:03,894 --> 00:38:04,560
Publiek: Julia.

919
00:38:04,560 --> 00:38:07,559
David J. Malan Julia, kan jy pop
uit en maak asof jy was nooit daar?

920
00:38:07,559 --> 00:38:09,040
OK, dit het nooit gebeur nie.

921
00:38:09,040 --> 00:38:09,680
Dankie.

922
00:38:09,680 --> 00:38:12,180
So dink ons ​​wil voeg
Julia in hierdie verband lys.

923
00:38:12,180 --> 00:38:13,780
Sy is die nommer 20.

924
00:38:13,780 --> 00:38:15,530
En natuurlik is sy
gaan om te behoort aan die

925
00:38:15,530 --> 00:38:17,521
begin-- nie wys nie enigiets nie.

926
00:38:17,521 --> 00:38:20,020
So jou hand kan soort wees
down nul of 'n gemors waarde.

927
00:38:20,020 --> 00:38:21,210
Kom ons vertel die vinnige storie.

928
00:38:21,210 --> 00:38:22,980
Ek wys op nommer 5 hierdie tyd.

929
00:38:22,980 --> 00:38:23,880
Dan kyk ek 9.

930
00:38:23,880 --> 00:38:25,130
Dan gaan ek 17.

931
00:38:25,130 --> 00:38:26,247
Dan gaan ek 22.

932
00:38:26,247 --> 00:38:27,650

933
00:38:27,650 --> 00:38:32,485
En ek besef, ooh, Julia
behoeftes om te gaan voor 22.

934
00:38:32,485 --> 00:38:33,580

935
00:38:33,580 --> 00:38:34,660
So wat moet gebeur?

936
00:38:34,660 --> 00:38:35,786

937
00:38:35,786 --> 00:38:36,910
Wie se hande nodig om te verander?

938
00:38:36,910 --> 00:38:38,360
Julia se, myne, or--
Wat is jou naam nou weer?

939
00:38:38,360 --> 00:38:39,230
>> GEHOOR: Christen.

940
00:38:39,230 --> 00:38:40,060
>> David J. Malan Christelike 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
Christen of Andy?

944
00:38:41,654 --> 00:38:44,280

945
00:38:44,280 --> 00:38:45,690
Andy nodig om te wys 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
Alle regte.

949
00:38:47,840 --> 00:38:48,960
So Andy, wil jy om te wys op Julia?

950
00:38:48,960 --> 00:38:50,120
Maar wag 'n minuut.

951
00:38:50,120 --> 00:38:53,260
In die storie tot dusver
Ek is die soort van 'n

952
00:38:53,260 --> 00:38:56,800
in beheer is, in die sin dat
wyser is die ding wat

953
00:38:56,800 --> 00:38:57,850
beweeg deur die lys.

954
00:38:57,850 --> 00:39:00,800
Ons kan 'n naam vir Andy, maar
daar is geen veranderlike genoem Andy.

955
00:39:00,800 --> 00:39:04,320
Die enigste ander veranderlike ons het, is
eerste, wie verteenwoordig deur Gabe.

956
00:39:04,320 --> 00:39:07,690
>> So dit is eintlik die rede waarom so
dusver het ons nie nodig nie.

957
00:39:07,690 --> 00:39:10,846
Maar nou op die skerm is daar
noem weer van pred wyser.

958
00:39:10,846 --> 00:39:11,970
So laat my meer duidelik.

959
00:39:11,970 --> 00:39:14,820
As dit is wyser, ek het 'n beter
'n bietjie meer intelligent

960
00:39:14,820 --> 00:39:15,950
oor my iterasie.

961
00:39:15,950 --> 00:39:19,580
As jy nie omgee nie my gaan hier deur
weer, wys hier, wys hier.

962
00:39:19,580 --> 00:39:22,500
Maar laat my 'n pred wyser,
voorganger wyser, wat

963
00:39:22,500 --> 00:39:24,740
soort wat dui op die
element Ek was net op.

964
00:39:24,740 --> 00:39:27,330
So toe ek hier gaan, nou
my linkerhand updates.

965
00:39:27,330 --> 00:39:29,370
Wanneer ek gaan hier my linkerhand updates.

966
00:39:29,370 --> 00:39:33,090
En nou, ek het nie net 'n verwysing na
die element wat gaan na Julia,

967
00:39:33,090 --> 00:39:36,300
Ek het nog 'n verwysing na
Andy, die element voor.

968
00:39:36,300 --> 00:39:39,430
So jy toegang het, in wese,
broodkrummels, as jy wil,

969
00:39:39,430 --> 00:39:41,500
om al die nodige verwysings.

970
00:39:41,500 --> 00:39:43,710
>> So as ek wys op
Ek en Andy is ook daarop

971
00:39:43,710 --> 00:39:47,105
op Christelike, wie se hande
moet nou elders wys?

972
00:39:47,105 --> 00:39:48,770

973
00:39:48,770 --> 00:39:51,960
So Andy kan nou wys op Julia.

974
00:39:51,960 --> 00:39:54,460
Julia kan nou wys op Christelike.

975
00:39:54,460 --> 00:39:56,950
Omdat sy kan kopieer my
regterhand se wyser.

976
00:39:56,950 --> 00:40:00,044
En dit effektief jy sit
terug na hierdie plek hier.

977
00:40:00,044 --> 00:40:02,460
Dus, in kort, selfs al is dit
neem ons soort ewig

978
00:40:02,460 --> 00:40:04,510
om werklik te werk 'n
gekoppel lys, besef

979
00:40:04,510 --> 00:40:06,580
dat die bedrywighede
is relatief eenvoudig.

980
00:40:06,580 --> 00:40:10,030
Dit is van een, twee, drie
reëls van die kode uiteindelik.

981
00:40:10,030 --> 00:40:12,780
Maar toegedraai rondom dié
reëls van die kode vermoedelik

982
00:40:12,780 --> 00:40:16,350
is 'n bietjie van die logika wat effektief
vra die vraag, waar is ons?

983
00:40:16,350 --> 00:40:18,970
Is ons aan die begin,
die middel, of die einde?

984
00:40:18,970 --> 00:40:21,890
>> Nou, daar is beslis 'n paar ander
bedrywighede wat ons kan implementeer.

985
00:40:21,890 --> 00:40:24,880
En hierdie foto's hier net uitbeeld
wat ons nou net gedoen het met die mens.

986
00:40:24,880 --> 00:40:26,080
Wat van die verwydering?

987
00:40:26,080 --> 00:40:30,650
As ek wil, byvoorbeeld,
verwyder die nommer 34 of 55,

988
00:40:30,650 --> 00:40:34,680
Ek kan dieselfde soort kode het,
maar ek gaan een of twee stappe nodig.

989
00:40:34,680 --> 00:40:36,110
Want wat is nuut?

990
00:40:36,110 --> 00:40:40,460
As ek verwyder iemand aan die einde,
soos nommer 55 en dan 34,

991
00:40:40,460 --> 00:40:42,995
wat ook moet verander as ek dit doen?

992
00:40:42,995 --> 00:40:44,870
Ek moet nie evict--
Wat is jou naam nou weer?

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
Ek moet nie net evict-- gratis Jack,
so letterlik bel gratis Jack, of ten minste

996
00:40:49,770 --> 00:40:53,530
die wyser daar ook, maar nou
wat nodig is om te verander met Peter?

997
00:40:53,530 --> 00:40:55,510
Sy hand beter begin wys het.

998
00:40:55,510 --> 00:40:59,300
Omdat so gou as ek bel gratis op
Jack, as Peter se steeds wys na Jack

999
00:40:59,300 --> 00:41:02,530
en ek dus hou dwars
die lys en toegang tot hierdie wyser,

1000
00:41:02,530 --> 00:41:05,650
Dis toe dat ons ou vriend segmentering
fout kan eintlik skop.

1001
00:41:05,650 --> 00:41:07,860
Want ons het die lig van die
geheue terug na Jack.

1002
00:41:07,860 --> 00:41:10,760
>> Jy kan daar bly
ongemaklik vir net 'n oomblik.

1003
00:41:10,760 --> 00:41:13,410
Want ons het net 'n paar
finale bedrywighede te oorweeg.

1004
00:41:13,410 --> 00:41:15,600
Die verwydering van die hoof van die lys,
of die beginning-- en hierdie een se

1005
00:41:15,600 --> 00:41:16,349
'n bietjie irriterend.

1006
00:41:16,349 --> 00:41:19,640
Want ons het om te weet dat Gabe
is 'n soort van spesiale in hierdie program.

1007
00:41:19,640 --> 00:41:21,440
Omdat inderdaad, hy het sy eie wyser.

1008
00:41:21,440 --> 00:41:24,860
Hy is nie net om daarop te,
soos byna almal anders hier.

1009
00:41:24,860 --> 00:41:28,112
>> En toe die hoof van die lys is
verwyder, wie se hande moet nou verander?

1010
00:41:28,112 --> 00:41:29,070
Wat is jou naam nou weer?

1011
00:41:29,070 --> 00:41:29,450
>> Publiek: Christine.

1012
00:41:29,450 --> 00:41:31,408
>> David J. MALAN: Ek is verskriklik
by name, blykbaar.

1013
00:41:31,408 --> 00:41:34,011
So Christine en Gabe,
wie se hande nodig om te verander

1014
00:41:34,011 --> 00:41:36,510
wanneer ons probeer Christine te verwyder,
nommer 5, van die prentjie?

1015
00:41:36,510 --> 00:41:37,550

1016
00:41:37,550 --> 00:41:38,820
OK, so kom ons doen Gabe.

1017
00:41:38,820 --> 00:41:40,950
Gabe gaan wys,
vermoedelik, op nommer 9.

1018
00:41:40,950 --> 00:41:42,230

1019
00:41:42,230 --> 00:41:44,642
Maar wat volgende moet gebeur?

1020
00:41:44,642 --> 00:41:46,600
Publiek: Christine moet
nul [onhoorbaar].

1021
00:41:46,600 --> 00:41:50,244
David J. Malan OK, moet ons waarskynlik
make-- Ek het gehoor "null" iewers.

1022
00:41:50,244 --> 00:41:51,410
Publiek: Null en gratis 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 gratis haar.

1025
00:41:53,074 --> 00:41:54,490
David J. Malan Null en gratis haar.

1026
00:41:54,490 --> 00:41:55,422
So dit is baie maklik.

1027
00:41:55,422 --> 00:41:58,380
En dit is ideaal dat jy nou soort
van wat daar staan, nie deel uitmaak.

1028
00:41:58,380 --> 00:42:00,430
Omdat jy het al
ontkoppelde uit die lys.

1029
00:42:00,430 --> 00:42:02,820
Jy het effektief is
weeskinders uit die lys.

1030
00:42:02,820 --> 00:42:07,770
En so het ons het 'n beter roep nou gratis op
Christine dat die geheue terug te gee.

1031
00:42:07,770 --> 00:42:10,240
Anders elke keer as ons
verwyder 'n knoop van die lys

1032
00:42:10,240 --> 00:42:14,230
ons kan maak die lys
korter, maar nie eintlik afneem

1033
00:42:14,230 --> 00:42:15,096
die grootte in die geheue.

1034
00:42:15,096 --> 00:42:17,720
En so, as ons hou toe te voeg en
toe te voeg, om dinge op die lys,

1035
00:42:17,720 --> 00:42:19,280
my rekenaar kan kry stadiger
en stadiger en stadiger,

1036
00:42:19,280 --> 00:42:21,740
want ek is besig om van die
geheue, selfs al is ek nie eintlik

1037
00:42:21,740 --> 00:42:25,580
gebruik Christine se grepe
geheue nie.

1038
00:42:25,580 --> 00:42:28,500
>> So op die ou end is daar ander
scenario's, van course-- verwydering

1039
00:42:28,500 --> 00:42:30,640
in die middel, verwydering
aan die einde, soos ons gesien het.

1040
00:42:30,640 --> 00:42:32,348
Maar die meer interessant
uitdaging is nou

1041
00:42:32,348 --> 00:42:34,770
gaan wees om presies te oorweeg
wat die loop van die tyd is.

1042
00:42:34,770 --> 00:42:36,640
So nie net kan jy jou
stukkies papier, indien, Gabe,

1043
00:42:36,640 --> 00:42:38,640
jy sal nie omgee om
almal 'n stress bal.

1044
00:42:38,640 --> 00:42:42,100
Baie dankie aan ons gekoppel lys
vrywilligers hier, as jy kon.

1045
00:42:42,100 --> 00:42:45,320
>> [Applous]

1046
00:42:45,320 --> 00:42:46,700
>> David J. Malan Alle regte.

1047
00:42:46,700 --> 00:42:51,110
So 'n paar van die analitiese
vrae dan, as ek kon.

1048
00:42:51,110 --> 00:42:59,670
Ons het gesien dat hierdie notasie voor,
groot O en omega, bogrense

1049
00:42:59,670 --> 00:43:02,520
en laer perke op die
loop van die tyd van 'n paar algoritme.

1050
00:43:02,520 --> 00:43:04,950
So laat ons kyk net
'n paar vrae.

1051
00:43:04,950 --> 00:43:07,090
>> Een, en ons het gesê dit
voor, wat is die loop

1052
00:43:07,090 --> 00:43:10,647
tyd van soeke na 'n
lys in terme van die groot O?

1053
00:43:10,647 --> 00:43:13,480
Wat is 'n bogrens op die lopende
tyd van soek na 'n geskakelde lys

1054
00:43:13,480 --> 00:43:16,340
soos toegepas deur ons vrywilligers hier?

1055
00:43:16,340 --> 00:43:17,820
Dit is groot O van n, lineêr.

1056
00:43:17,820 --> 00:43:20,630
Want in die ergste geval,
die element, soos 55,

1057
00:43:20,630 --> 00:43:23,830
ons dalk op soek na mag wees waar
Jack was, al die pad aan die einde.

1058
00:43:23,830 --> 00:43:28,250
En ongelukkig, in teenstelling met 'n verskeidenheid
ons kan nie fancy hierdie tyd.

1059
00:43:28,250 --> 00:43:31,820
Selfs al is almal van ons mense was
gesorteer van die klein elemente, 5,

1060
00:43:31,820 --> 00:43:35,900
al die pad tot by die groter element,
55, dit is gewoonlik 'n goeie ding.

1061
00:43:35,900 --> 00:43:38,815
Maar wat beteken dat die aanname
nie langer toelaat dat ons te doen?

1062
00:43:38,815 --> 00:43:39,775

1063
00:43:39,775 --> 00:43:40,650
Publiek: [onhoorbaar]

1064
00:43:40,650 --> 00:43:40,920
David J. Malan weer sê?

1065
00:43:40,920 --> 00:43:41,800
Publiek: Random toegang.

1066
00:43:41,800 --> 00:43:43,049
David J. Malan Random toegang.

1067
00:43:43,049 --> 00:43:46,330
En op sy beurt beteken dit dat ons nie
meer gebruik swak nulle, intuïsie,

1068
00:43:46,330 --> 00:43:49,365
en vanselfsprekendheid van die gebruik van binêre
soek en te verdeel en oorwin.

1069
00:43:49,365 --> 00:43:51,240
Want selfs al is ons
mens kon duidelik

1070
00:43:51,240 --> 00:43:54,610
sien dat Andy of Christian was
ongeveer in die middel van die lys,

1071
00:43:54,610 --> 00:43:57,670
Ons weet net dat as 'n
rekenaar deur skimming die lys

1072
00:43:57,670 --> 00:43:59,029
van die begin af.

1073
00:43:59,029 --> 00:44:00,570
So ons het opgegee dat ewekansige toegang.

1074
00:44:00,570 --> 00:44:04,380
>> So groot O van N is nou die boonste
gebind op ons soek tyd.

1075
00:44:04,380 --> 00:44:07,920
Wat van omega van ons soek?

1076
00:44:07,920 --> 00:44:11,535
Wat is die ondergrens op soek
vir 'n paar nommer in die lys?

1077
00:44:11,535 --> 00:44:12,410
Publiek: [onhoorbaar]

1078
00:44:12,410 --> 00:44:13,040
David J. Malan weer sê?

1079
00:44:13,040 --> 00:44:13,420
Publiek: Een.

1080
00:44:13,420 --> 00:44:13,800
David J. Malan Een.

1081
00:44:13,800 --> 00:44:14,760
So konstante tyd.

1082
00:44:14,760 --> 00:44:17,020
In die beste geval, Christine is
inderdaad aan die begin van die lys.

1083
00:44:17,020 --> 00:44:19,020
En ons is op soek na
nommer 5, so ons het haar.

1084
00:44:19,020 --> 00:44:19,787
So geen groot deal.

1085
00:44:19,787 --> 00:44:22,370
Maar sy het om te wees by die
begin van die lys in hierdie geval.

1086
00:44:22,370 --> 00:44:23,745
Wat van iets soos Verwyder?

1087
00:44:23,745 --> 00:44:24,717

1088
00:44:24,717 --> 00:44:26,300
Wat gebeur as jy 'n element te verwyder?

1089
00:44:26,300 --> 00:44:29,200
Wat is die bogrens en ondergrens
op die verwydering van iets uit 'n gekoppelde

1090
00:44:29,200 --> 00:44:29,699
lys?

1091
00:44:29,699 --> 00:44:35,195

1092
00:44:35,195 --> 00:44:36,070
Publiek: [onhoorbaar]

1093
00:44:36,070 --> 00:44:36,420
David J. Malan weer sê?

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 die bogrens.

1096
00:44:38,900 --> 00:44:41,700
Want in die ergste geval ons probeer
Jack te verwyder, soos ons nou net gedoen het.

1097
00:44:41,700 --> 00:44:43,050
Hy is al die pad aan die einde.

1098
00:44:43,050 --> 00:44:45,419
Neem ons vir ewig, of
N stappe om hom te vind.

1099
00:44:45,419 --> 00:44:46,460
So dit is 'n bogrens.

1100
00:44:46,460 --> 00:44:47,430
Dit is lineêre, seker nie.

1101
00:44:47,430 --> 00:44:50,970
En die beste geval loop van tyd, of
die onderste grense in die beste geval

1102
00:44:50,970 --> 00:44:51,975
sou konstante tyd.

1103
00:44:51,975 --> 00:44:54,600
Omdat ons dalk probeer om te verwyder
Christine, en ons het net kry gelukkig

1104
00:44:54,600 --> 00:44:55,558
Sy is aan die begin.

1105
00:44:55,558 --> 00:44:56,350
Wag nou 'n minuut.

1106
00:44:56,350 --> 00:44:59,370
Gabe was ook aan die begin,
en ons het ook te werk Gabe.

1107
00:44:59,370 --> 00:45:01,150
So dit was nie net 'n stap.

1108
00:45:01,150 --> 00:45:04,210
So is dit inderdaad konstante
tyd, in die beste geval,

1109
00:45:04,210 --> 00:45:06,345
die kleinste element te verwyder?

1110
00:45:06,345 --> 00:45:07,360

1111
00:45:07,360 --> 00:45:10,960
Dit is, selfs al is dit dalk twee,
drie, of selfs 100 reëls van die kode,

1112
00:45:10,960 --> 00:45:14,000
As dit is dieselfde aantal
lyne, nie in 'n paar lus,

1113
00:45:14,000 --> 00:45:16,577
en onafhanklik van die grootte
van die lys, absoluut.

1114
00:45:16,577 --> 00:45:18,660
Die verwydering van die element by
die begin van die lys,

1115
00:45:18,660 --> 00:45:21,940
selfs as ons te doen het met
Gabe, is steeds konstant tyd.

1116
00:45:21,940 --> 00:45:24,220
>> So dit lyk soos 'n
groot stap agteruit.

1117
00:45:24,220 --> 00:45:27,000
En wat 'n vermorsing van tyd
As in week een en week

1118
00:45:27,000 --> 00:45:30,250
zero ons het nie net
pseudokode kode, maar die werklike kode

1119
00:45:30,250 --> 00:45:35,780
iets wat log te implementeer
basis N, of teken, maar eerder van N, basis 2,

1120
00:45:35,780 --> 00:45:37,150
in terme van sy lopende tyd.

1121
00:45:37,150 --> 00:45:40,710
So hoekom die klink sou ons wil begin
die gebruik van iets soos 'n geskakelde lys?

1122
00:45:40,710 --> 00:45:41,517
Ja.

1123
00:45:41,517 --> 00:45:44,022
>> Publiek: So jy kan byvoeg
elemente in die skikking.

1124
00:45:44,022 --> 00:45:46,230
David J. Malan So kan jy
voeg elemente in die skikking.

1125
00:45:46,230 --> 00:45:47,550
En dit is ook tematiese.

1126
00:45:47,550 --> 00:45:49,740
En ons sal voortgaan om te sien
dit is hierdie kompromis, baie

1127
00:45:49,740 --> 00:45:51,573
soos ons gesien het 'n
trade-off met merge soort.

1128
00:45:51,573 --> 00:45:54,606
Ons kan regtig bespoedig
soek of te sorteer, eerder

1129
00:45:54,606 --> 00:45:57,480
As ons spandeer 'n bietjie meer ruimte en
'n bykomende stuk van 'n geheue

1130
00:45:57,480 --> 00:45:58,760
of 'n skikking merge soort.

1131
00:45:58,760 --> 00:46:01,270
Maar ons meer bestee
ruimte, maar ons tyd te bespaar.

1132
00:46:01,270 --> 00:46:04,820
In hierdie geval, ons is
gee tyd, maar ons is

1133
00:46:04,820 --> 00:46:08,170
besig om buigsaamheid,
dinamika as jy wil,

1134
00:46:08,170 --> 00:46:10,280
wat waarskynlik 'n positiewe kenmerk.

1135
00:46:10,280 --> 00:46:11,520
>> Ons is ook die besteding van die ruimte.

1136
00:46:11,520 --> 00:46:13,710
In watter sin is 'n gekoppelde
lys duurder

1137
00:46:13,710 --> 00:46:15,700
in terme van ruimte as 'n skikking?

1138
00:46:15,700 --> 00:46:18,379

1139
00:46:18,379 --> 00:46:19,920
Waar is die ekstra ruimte vandaan?

1140
00:46:19,920 --> 00:46:20,460
Ja?

1141
00:46:20,460 --> 00:46:21,800
>> Publiek: [onhoorbaar] wyser.

1142
00:46:21,800 --> 00:46:23,310
>> David J. Malan Ja, ons
ook die wyser.

1143
00:46:23,310 --> 00:46:25,560
So dit is minorly irriterende
in wat nie meer is

1144
00:46:25,560 --> 00:46:27,780
Ek stoor net 'n int
'n int te verteenwoordig.

1145
00:46:27,780 --> 00:46:30,990
Ek stoor 'n int en 'n
wyser, wat ook 32 stukkies.

1146
00:46:30,990 --> 00:46:33,470
So ek letterlik verdubbel
die bedrag van die ruimte wat betrokke is.

1147
00:46:33,470 --> 00:46:36,040
So dit is 'n trade-off nie, maar
dit is in die geval van int.

1148
00:46:36,040 --> 00:46:39,580
Veronderstel dat jy nie stoor int,
maar veronderstel elkeen van hierdie reghoeke

1149
00:46:39,580 --> 00:46:43,290
of elk van hierdie mense was verteenwoordig
'n woord, 'n Engelse woord wat

1150
00:46:43,290 --> 00:46:46,430
dalk vyf karakters, 10
karakters, miskien selfs meer.

1151
00:46:46,430 --> 00:46:49,940
Dan voeg net 32 ​​meer stukkies
dalk minder van 'n groot deal.

1152
00:46:49,940 --> 00:46:52,160
>> Wat gebeur as elkeen van die studente
in die demonstrasie

1153
00:46:52,160 --> 00:46:55,107
was letterlik student structs wat
het name en huise en miskien

1154
00:46:55,107 --> 00:46:57,065
telefoonnommers en Twitter
hanteer en dies meer.

1155
00:46:57,065 --> 00:46:59,564
So al die velde het ons begin
praat oor die ander dag,

1156
00:46:59,564 --> 00:47:02,410
veel minder van 'n groot deal as
ons nodes kry meer interessant

1157
00:47:02,410 --> 00:47:05,972
en groot te spandeer, eh, 'n bykomende
wyser net om hulle te skakel.

1158
00:47:05,972 --> 00:47:07,180
Maar inderdaad, dit is 'n trade-off.

1159
00:47:07,180 --> 00:47:09,560
En inderdaad, die kode
meer kompleks, soos jy sal

1160
00:47:09,560 --> 00:47:11,770
sien deur skimming deur
daardie spesifieke voorbeeld.

1161
00:47:11,770 --> 00:47:14,302
Maar wat as daar
sommige heilige graal hier.

1162
00:47:14,302 --> 00:47:17,010
Wat as ons nie 'n stap te neem nie
agtertoe, maar 'n groot stap vorentoe

1163
00:47:17,010 --> 00:47:19,180
en implementering van 'n data
struktuur via wat ons

1164
00:47:19,180 --> 00:47:22,870
elemente soos Jack of kan vind
Christine of enige ander elemente

1165
00:47:22,870 --> 00:47:25,870
in hierdie verskeidenheid in ware konstante tyd?

1166
00:47:25,870 --> 00:47:26,920
Soek konstant.

1167
00:47:26,920 --> 00:47:28,320
Verwyder konstant.

1168
00:47:28,320 --> 00:47:29,570
Insetsel is konstant.

1169
00:47:29,570 --> 00:47:32,260
Al hierdie bedrywighede is konstant.

1170
00:47:32,260 --> 00:47:33,750
Dit sou ons heilige graal wees.

1171
00:47:33,750 --> 00:47:36,690
En dit is waar ons
sal haal die volgende keer.

1172
00:47:36,690 --> 00:47:38,600
Sien jy dan.

1173
00:47:38,600 --> 00:47:39,371