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

2
00:00:00,500 --> 00:00:11,137
[Predvajanje glasbe]

3
00:00:11,137 --> 00:00:12,220
DAVID J. Malan: Dobro.

4
00:00:12,220 --> 00:00:13,950
To je CS50.

5
00:00:13,950 --> 00:00:18,560
To je pet teden nadaljuje, in mi
dobre novice in slabe novice.

6
00:00:18,560 --> 00:00:21,140
Torej, dobra novica je, da CS50
začenja ta petek.

7
00:00:21,140 --> 00:00:24,430
Če bi radi, da se nam pridružite,
glavo na običajno URL tukaj.

8
00:00:24,430 --> 00:00:28,670
Še bolje novica, no predavanje
to prihaja ponedeljek 13..

9
00:00:28,670 --> 00:00:31,970
Nekoliko manj boljše novice,
Kviz je nič naslednjo sredo.

10
00:00:31,970 --> 00:00:33,840
Več podrobnosti lahko
najdete na tem URL tukaj.

11
00:00:33,840 --> 00:00:36,340
In v naslednjih nekaj dneh
bomo lahko izpolnite prazne

12
00:00:36,340 --> 00:00:39,234
v zvezi s prostori
da bo smo rezerviran.

13
00:00:39,234 --> 00:00:41,400
Boljša novica je, da bom
je pregled seveda vsej

14
00:00:41,400 --> 00:00:43,570
zasedanje tega prihaja
Ponedeljek zvečer.

15
00:00:43,570 --> 00:00:46,270
Ostanite z nami, da seveda je
Spletna stran za kraj in podrobnosti.

16
00:00:46,270 --> 00:00:49,290
Profili, čeprav je
praznik, se bo sestal tudi kot dobro.

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

18
00:00:50,490 --> 00:00:52,940
Najboljša novica, predavanje naslednji petek.

19
00:00:52,940 --> 00:00:56,220
Torej je to tradicija smo
imajo, glede na učni načrt.

20
00:00:56,220 --> 00:00:58,100
Samo-- se dogaja, da je neverjetno.

21
00:00:58,100 --> 00:01:02,510
Boste videli stvari, kot so
podatkovne strukture konstanten čas

22
00:01:02,510 --> 00:01:04,730
in razpršene tabele in drevesa in se trudi.

23
00:01:04,730 --> 00:01:07,150
In se bova pogovorila o problemih rojstni dan.

24
00:01:07,150 --> 00:01:09,440
Cel kup stvari
čaka naslednji petek.

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
Kakorkoli že.

28
00:01:13,190 --> 00:01:17,080
>> Tako opozarjajo, da smo bili
s poudarkom na tej sliki, kar je

29
00:01:17,080 --> 00:01:18,980
Notranjost spomin našega računalnika.

30
00:01:18,980 --> 00:01:22,875
Torej pomnilnik ali RAM je, če programi
obstaja, ko ste jim teče.

31
00:01:22,875 --> 00:01:25,215
Če dvakrat kliknete
icon teči nekaj programa

32
00:01:25,215 --> 00:01:27,520
ali dvokliknite
icon odpreti neko datoteko,

33
00:01:27,520 --> 00:01:30,430
to je natovorjen s trdega
pogon ali pogon SSD

34
00:01:30,430 --> 00:01:34,190
v RAM, Random Access Memory, kjer
živi do izpada električne energije,

35
00:01:34,190 --> 00:01:36,700
pokrov laptop zapre,
ali zaprete program.

36
00:01:36,700 --> 00:01:38,960
>> Zdaj, spomin, od
ki imate verjetno

37
00:01:38,960 --> 00:01:41,950
1 gigabajta te dni, 2
gigabajte ali celo veliko več,

38
00:01:41,950 --> 00:01:44,420
je na splošno določeno
za določen program

39
00:01:44,420 --> 00:01:47,170
V to vrsto pravokotne
konceptualni model

40
00:01:47,170 --> 00:01:50,860
pri čemer imamo kup na dnu
in kup drugih stvari na vrhu.

41
00:01:50,860 --> 00:01:53,140
Stvar na samem vrhu
smo videli na tej sliki

42
00:01:53,140 --> 00:01:55,670
prej, vendar nikoli ni govoril o
je tako imenovani besedilo segmenta.

43
00:01:55,670 --> 00:01:58,419
Segment besedilo je samo fancy način
rekel ničel in enic, ki

44
00:01:58,419 --> 00:02:01,150
sestavite vaše dejanske prevedenega programa.

45
00:02:01,150 --> 00:02:03,910
>> Torej, ko dvokliknite
Microsoft Word na vašem Mac ali PC,

46
00:02:03,910 --> 00:02:08,030
ali ko zaženete piko poševnica Mario na
Linux računalnik na vašo terminalsko okno,

47
00:02:08,030 --> 00:02:12,460
ničle in tisti, ki sestavljajo
Beseda ali Mario se začasno shranijo

48
00:02:12,460 --> 00:02:16,610
iz računalnika RAM v tako imenovani
Besedilo odsek za določen program.

49
00:02:16,610 --> 00:02:19,080
Spodaj, da gre inicializiran
in neinicializirane podatke.

50
00:02:19,080 --> 00:02:22,655
To je stvar, kot so globalne spremenljivke,
da smo ne uporablja veliko,

51
00:02:22,655 --> 00:02:24,910
ampak včasih smo jih
imela globalne spremenljivke

52
00:02:24,910 --> 00:02:28,819
ali statično opredeljena strune, ki
je težko kodirane besede, kot so "zdravo"

53
00:02:28,819 --> 00:02:31,860
da se ne sprejemajo od uporabnika
ki so težko kodirane v vaš program.

54
00:02:31,860 --> 00:02:34,230
>> Zdaj, navzdol na dnu smo
imajo ti dimnika.

55
00:02:34,230 --> 00:02:37,665
In stack, tako daleč, da smo bili
uporabi za kakšne vrste namene?

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

57
00:02:39,706 --> 00:02:40,997
Kaj je bil sveženj uporablja?

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

59
00:02:41,160 --> 00:02:42,070
>> Ciljna publika: Funkcije.

60
00:02:42,070 --> 00:02:43,320
>> DAVID J. Malan: Za funkcije?

61
00:02:43,320 --> 00:02:44,980
V kakšnem smislu za funkcije?

62
00:02:44,980 --> 00:02:48,660
>> OBČINSTVO: Ko pokličete funkcijo,
Argumenti se kopira na kupu.

63
00:02:48,660 --> 00:02:49,660
>> DAVID J. Malan: Točno tako.

64
00:02:49,660 --> 00:02:52,650
Ko pokličete funkcijo, njegova
Argumenti se kopira na kupu.

65
00:02:52,650 --> 00:02:56,330
Torej vse X ali Y ali je ali B je
da ste poteka v funkciji

66
00:02:56,330 --> 00:02:58,680
začasno dajo na
tako imenovani dimnik,

67
00:02:58,680 --> 00:03:02,000
tako kot eden od Annenberg
jedilnici pladnje, in tudi stvari,

68
00:03:02,000 --> 00:03:03,190
kot lokalne spremenljivke.

69
00:03:03,190 --> 00:03:06,290
Če je vaš foo funkcija ali vaš swap
Funkcija imajo lokalne spremenljivke,

70
00:03:06,290 --> 00:03:08,602
kot temp, ta dva
končajo na kupu.

71
00:03:08,602 --> 00:03:11,560
Zdaj, mi ne bo govoril preveč o
njih, vendar te spremenljivke okolja

72
00:03:11,560 --> 00:03:15,690
Na dnu smo videli pred časom, ko
Sem futzing na tipkovnici en dan

73
00:03:15,690 --> 00:03:20,050
in sem začel dostop do stvari
kot argv 100 ali argv 1000,

74
00:03:20,050 --> 00:03:22,320
Pravkar elements-- sem pozabil
numbers-- ampak da

75
00:03:22,320 --> 00:03:24,330
ne bi smel biti dostopni zame.

76
00:03:24,330 --> 00:03:26,581
Začeli smo videli nekaj
funky simboli na zaslonu.

77
00:03:26,581 --> 00:03:28,330
Tisti, ki so bili tako imenovani
spremenljivke okolja

78
00:03:28,330 --> 00:03:32,390
kot globalnih nastavitvah za moj
Program ali za računalnikom, ne

79
00:03:32,390 --> 00:03:37,090
povezana z nedavno
bug, da smo se pogovarjali,

80
00:03:37,090 --> 00:03:39,670
Shellshock, da je bilo
Mori kar nekaj računalnikov.

81
00:03:39,670 --> 00:03:42,960
>> Zdaj nazadnje, v današnjem poudarkom
bomo v končni fazi na kup.

82
00:03:42,960 --> 00:03:44,864
To je še en kos pomnilnika.

83
00:03:44,864 --> 00:03:47,030
In v bistvu vse to
Pomnilnik je ista stvar.

84
00:03:47,030 --> 00:03:48,040
To je enako strojno opremo.

85
00:03:48,040 --> 00:03:49,956
Mi smo nekako
zdravljenje različnih skupin

86
00:03:49,956 --> 00:03:51,460
bajtov za različne namene.

87
00:03:51,460 --> 00:03:56,540
Heap se tudi dogaja, da je tam, kjer
spremenljivke in spomin, ki ga zahtevajo

88
00:03:56,540 --> 00:03:58,810
od operacijskega sistema
začasno shranjeni.

89
00:03:58,810 --> 00:04:01,890
>> Vendar pa je nekako problem
tukaj, kot kaže slika.

90
00:04:01,890 --> 00:04:05,261
Smo nekako še dva
ladje okrog, da trčijo.

91
00:04:05,261 --> 00:04:08,010
Saj, kot ste uporabili več
kupa, in kot vidimo danes

92
00:04:08,010 --> 00:04:11,800
dalje, kot ste uporabili več in več
heap, zagotovo slabe stvari se lahko zgodi.

93
00:04:11,800 --> 00:04:15,054
In res, lahko povzroči, da
namerno ali nenamerno.

94
00:04:15,054 --> 00:04:16,970
Torej je Cliffhanger zadnji
Čas je bil ta program,

95
00:04:16,970 --> 00:04:20,570
ki ne služi katera koli funkcionalna
namen, razen za dokazovanje

96
00:04:20,570 --> 00:04:24,750
kako vam lahko kot slab človek dejansko lahko
Prednost hroščev v programu nekoga

97
00:04:24,750 --> 00:04:28,460
in prevzeti program ali celo
Celoten računalniški sistem ali strežnik.

98
00:04:28,460 --> 00:04:31,660
Torej, samo da bi pogled na kratko, ti
obvestilo, da je glavna na dnu

99
00:04:31,660 --> 00:04:34,510
sprejme v ukazni vrstici
trditve, kot na argv.

100
00:04:34,510 --> 00:04:38,480
In to je klic funkcije f,
v bistvu brez imena funkcijo imenovano

101
00:04:38,480 --> 00:04:40,250
f, in to gre v argv [1].

102
00:04:40,250 --> 00:04:43,960
>> Torej, ne glede na besedo uporabnik vnese v na
poziv po imenu tega programa,

103
00:04:43,960 --> 00:04:49,310
in potem je to samovoljno funkcija up
top, f, bo v nizu, AKA char *

104
00:04:49,310 --> 00:04:51,720
kot smo začeli, da bi razpravljali,
in to samo imenuje "bar".

105
00:04:51,720 --> 00:04:53,310
Vendar bi ga lahko imenovali nič.

106
00:04:53,310 --> 00:04:57,470
In potem izjavlja, znotraj
F, niz znakov

107
00:04:57,470 --> 00:04:59,930
imenovano C- 12 takih znakov.

108
00:04:59,930 --> 00:05:03,580
>> Zdaj, z zgodbo sem povedal
pred nekaj trenutki, kjer je v spomin

109
00:05:03,580 --> 00:05:06,720
c je, ali so tisti, ki 12
ožge bo končalo?

110
00:05:06,720 --> 00:05:07,570
Samo da bo jasno.

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

112
00:05:08,070 --> 00:05:08,590
>> OBČINSTVO: Na kupu.

113
00:05:08,590 --> 00:05:09,420
>> DAVID J. Malan: Na kupu.

114
00:05:09,420 --> 00:05:10,720
Torej je c lokalna spremenljivka.

115
00:05:10,720 --> 00:05:14,079
Mi vas prosimo, za 12 znakov ali 12 bajtov.

116
00:05:14,079 --> 00:05:16,120
Tisti, ki se bo končalo
o tako imenovanem dimnika.

117
00:05:16,120 --> 00:05:18,530
Zdaj končno je ta druga funkcija
To je pravzaprav zelo koristno,

118
00:05:18,530 --> 00:05:20,571
vendar smo v resnici ne uporablja
to sami, strncopy.

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

120
00:05:21,550 --> 00:05:25,200
To pomeni niz kopijo, vendar
samo črke n, n znakov.

121
00:05:25,200 --> 00:05:31,990
Tako bo n znakov biti
kopira iz bara v c.

122
00:05:31,990 --> 00:05:32,980
In koliko jih je?

123
00:05:32,980 --> 00:05:34,110
Dolžina bar.

124
00:05:34,110 --> 00:05:36,330
Torej, z drugimi besedami, da
ena vrstica, strncopy,

125
00:05:36,330 --> 00:05:39,500
gre za kopiranje
učinkovito bar se v c.

126
00:05:39,500 --> 00:05:42,340
>> Zdaj pa, samo da nekako predvideti
Nauk te zgodbe,

127
00:05:42,340 --> 00:05:44,750
kar je potencialno problematična tukaj?

128
00:05:44,750 --> 00:05:49,710
Čeprav smo preverjanje dolžine
droga in njegovo posredovanje v strncopy,

129
00:05:49,710 --> 00:05:53,145
kaj je tvoj gut govoriš, da si je
še vedno razdeljena glede tega programa?

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
>> OBČINSTVO: Ne vključuje
soba za null značaja.

133
00:05:57,491 --> 00:05:59,990
DAVID J. Malan: Ne vključuje
soba za null značaja.

134
00:05:59,990 --> 00:06:02,073
Potencialno razliko
preteklo prakso ne bomo niti

135
00:06:02,073 --> 00:06:04,810
Toliko kot plus 1 k
sprejme ta null značaj.

136
00:06:04,810 --> 00:06:06,649
Ampak to je še slabše kot to.

137
00:06:06,649 --> 00:06:07,940
Kaj drugega nam ne bodo storili?

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

139
00:06:08,432 --> 00:06:09,307
>> OBČINSTVO: [neslišno]

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

141
00:06:15,440 --> 00:06:16,440
DAVID J. Malan: Popolna.

142
00:06:16,440 --> 00:06:18,490
Mi smo težko kodirane 12 precej samovoljno.

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

144
00:06:19,497 --> 00:06:21,330
Da ni toliko
problem, vendar je dejstvo,

145
00:06:21,330 --> 00:06:25,630
da sva sploh ne preverja, če
dolžina vrat je manj kot 12,

146
00:06:25,630 --> 00:06:28,530
v tem primeru se bo
varno, da ga v spomin

147
00:06:28,530 --> 00:06:30,260
imenovano c, da smo dodeljen.

148
00:06:30,260 --> 00:06:32,960
Dejansko, če je bar je kot
20 znakov,

149
00:06:32,960 --> 00:06:39,010
zdi, da ta funkcija za kopiranje
20 znakov iz bara v c, s čimer

150
00:06:39,010 --> 00:06:41,310
ob vsaj 8 bajtov
da ne bi smelo biti.

151
00:06:41,310 --> 00:06:42,690
To je posledice tukaj.

152
00:06:42,690 --> 00:06:44,347
>> Torej, na kratko, zdrobljen programa.

153
00:06:44,347 --> 00:06:45,180
Ni tak big deal.

154
00:06:45,180 --> 00:06:46,360
Morda boste dobili napako segmentacije.

155
00:06:46,360 --> 00:06:47,651
Vsi smo imeli napake v programih.

156
00:06:47,651 --> 00:06:50,196
Vse, kar bi lahko žuželke
v programih, prav zdaj.

157
00:06:50,196 --> 00:06:51,320
Toda kaj je posledice?

158
00:06:51,320 --> 00:06:54,390
No, tukaj je Povečano-in verzija
da je slika spomina mojega računalnika.

159
00:06:54,390 --> 00:06:56,230
To je dno mojega dimnika.

160
00:06:56,230 --> 00:06:59,644
In res, na samem dnu je tisto, kar je
imenovano matično rutinsko stack, fancy način

161
00:06:59,644 --> 00:07:00,560
bi rekel, da je glavni.

162
00:07:00,560 --> 00:07:03,772
Tako, da kdor se imenuje funkcija
f, da govorimo o tem.

163
00:07:03,772 --> 00:07:05,230
Torej je to dno kupa.

164
00:07:05,230 --> 00:07:06,640
Povratni naslov je nekaj novega.

165
00:07:06,640 --> 00:07:08,810
To je bila vedno tam,
bila vedno na tej sliki.

166
00:07:08,810 --> 00:07:10,440
Mi samo nikoli opozoril na to.

167
00:07:10,440 --> 00:07:15,290
Ker se je izkazalo, kako c deluje, je
da ko ena funkcija zahteva drugega,

168
00:07:15,290 --> 00:07:18,780
ne le argumente, ki
Funkcija se potisne na kup,

169
00:07:18,780 --> 00:07:22,470
ne le funkcija je lokalna
spremenljivke se potisne na kup,

170
00:07:22,470 --> 00:07:26,820
nekaj, kar se imenuje povratni naslov
dobi tudi dal na kupu.

171
00:07:26,820 --> 00:07:33,330
Natančneje, če je glavna zahteva Foo, glavni je
lastni naslov v pomnilniku, ox nekaj,

172
00:07:33,330 --> 00:07:38,240
dejansko dobi dal na kupu
tako da, ko je f narejeno tako izvršitve

173
00:07:38,240 --> 00:07:43,630
ne ve, kje naj skoči nazaj v besedilu
segment, da bi še naprej izvršitve.

174
00:07:43,630 --> 00:07:47,760
>> Torej, če smo tukaj konceptualno,
V glavnem, potem dobi f klical.

175
00:07:47,760 --> 00:07:50,200
Kako f ve, kdo
za nadzor vrniti?

176
00:07:50,200 --> 00:07:52,020
No, ta mali
Orientacijska v red tukaj,

177
00:07:52,020 --> 00:07:54,978
imenuje naslov vrnitev, samo
preverjanja, kaj je to povratni naslov?

178
00:07:54,978 --> 00:07:57,039
Oh, mi skoči nazaj na glavno tukaj.

179
00:07:57,039 --> 00:07:59,080
In to je malo
njen pomen,

180
00:07:59,080 --> 00:08:00,750
ker ničel in enic
za glavno tehnično

181
00:08:00,750 --> 00:08:01,967
tu v tech segmentu.

182
00:08:01,967 --> 00:08:03,800
Ampak to je ideja. f
samo mora vedeti, kaj

183
00:08:03,800 --> 00:08:06,680
, kjer nadzor v končni fazi gre nazaj.

184
00:08:06,680 --> 00:08:09,790
>> Ampak način računalniki
že dolgo določeno stvari

185
00:08:09,790 --> 00:08:12,320
kot lokalne spremenljivke in
argumentov je, kot je ta.

186
00:08:12,320 --> 00:08:17,180
Tako da na vrhu te slike v
blue je kup okvir za f, tako da vse

187
00:08:17,180 --> 00:08:19,630
pomnilnika, da f
še posebej je s pomočjo.

188
00:08:19,630 --> 00:08:22,990
Torej zato, opazili, da se
bar je na tej sliki.

189
00:08:22,990 --> 00:08:23,980
Bar je bil njen argument.

190
00:08:23,980 --> 00:08:27,240
In mi je trdil, da so trditve, da
Funkcije se potisne na kup.

191
00:08:27,240 --> 00:08:29,910
In c, je seveda
tudi te slike.

192
00:08:29,910 --> 00:08:33,520
>> In samo za namene, simbolov,
opazili v zgornjem levem kotu

193
00:08:33,520 --> 00:08:37,020
je, kaj bi bilo c nosilec 0 in
nato rahlo navzdol v desno

194
00:08:37,020 --> 00:08:38,220
je c nosilec 11.

195
00:08:38,220 --> 00:08:41,240
Torej, z drugimi besedami, si lahko predstavljate
da je grid bajtov

196
00:08:41,240 --> 00:08:44,380
tam, od katerih prva je
zgoraj levo, katere dno

197
00:08:44,380 --> 00:08:48,360
je zadnja od teh 12 bajtov.

198
00:08:48,360 --> 00:08:49,930
>> Toda zdaj poskušajo za previjanje naprej.

199
00:08:49,930 --> 00:08:55,580
Kaj se bo zgodilo, če se peljemo
v godalni vrstici, ki je več kot c?

200
00:08:55,580 --> 00:08:59,130
In ne bomo preverjanje, če
to je res več kot 12.

201
00:08:59,130 --> 00:09:03,146
Kateri del te slike bo
se prepiše bajtov 0, 1, 2, 3,

202
00:09:03,146 --> 00:09:07,890
dot dot, 11, in nato
slab, 12, 13 do 19?

203
00:09:07,890 --> 00:09:11,820
Kaj se bo zgodilo tukaj,
Če sklepamo iz naročanje

204
00:09:11,820 --> 00:09:14,790
da c nosilec 0 je na vrhu
in c nosilec 11 je nekako navzdol

205
00:09:14,790 --> 00:09:15,812
da ali ne?

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

207
00:09:16,796 --> 00:09:19,260
>> OBČINSTVO: No, to se dogaja
prepisati char * bar.

208
00:09:19,260 --> 00:09:22,260
>> DAVID J. Malan: Ja, izgleda, da
boš prepisati Char * bar.

209
00:09:22,260 --> 00:09:26,245
In še huje, če boste poslali v res dolgo
Niz, boste morda celo prepisati kaj?

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

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

212
00:09:28,570 --> 00:09:31,380
Ki je spet, je prav tako kot
Orientacijska povedati programu, če

213
00:09:31,380 --> 00:09:34,060
, da se vrnete, ko f
poteka pozivu.

214
00:09:34,060 --> 00:09:37,140
>> Torej, kaj slabi fantje običajno storijo
je, če naletijo na programu

215
00:09:37,140 --> 00:09:41,290
da so radovedni, ali je
izkoriščati, vozičkom tako

216
00:09:41,290 --> 00:09:43,550
da je on ali ona lahko
Prednost tega hrošča,

217
00:09:43,550 --> 00:09:45,720
običajno ne dobijo
To pravico je prvič.

218
00:09:45,720 --> 00:09:48,590
Pravkar so začeli pošiljati, na primer,
naključne nize v svoj program,

219
00:09:48,590 --> 00:09:50,260
ali na tipkovnici,
ali odkrito verjetno

220
00:09:50,260 --> 00:09:52,740
napišite majhen program, da samo
samodejno ustvari strune,

221
00:09:52,740 --> 00:09:55,430
in začeti razbijati od programa, ki ga
pošilja v veliko različnih vhodov

222
00:09:55,430 --> 00:09:56,340
na različnih dolžin.

223
00:09:56,340 --> 00:09:58,990
>> Takoj, ko je vaš program zruši,
To je nekaj neverjetnega.

224
00:09:58,990 --> 00:10:01,020
Ker to pomeni, da je
ali je bila odkrita

225
00:10:01,020 --> 00:10:02,660
kar je verjetno res bug.

226
00:10:02,660 --> 00:10:05,830
In potem lahko dobite več pameten
in začeti s poudarkom ožje

227
00:10:05,830 --> 00:10:07,420
o tem, kako izkoristiti to napako.

228
00:10:07,420 --> 00:10:11,480
Še posebej, kar on ali ona morda
storiti, je poslati, v najboljšem primeru, zdravo.

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

230
00:10:12,210 --> 00:10:14,750
To je niz, ki je dovolj kratko.

231
00:10:14,750 --> 00:10:18,100
Kaj pa če je on ali ona pošlje,
in jo bomo posploševati kot,

232
00:10:18,100 --> 00:10:20,890
napad code-- tako ničel
in tisti, ki počnejo stvari

233
00:10:20,890 --> 00:10:25,150
kot rm-rf, da odstranite vse
iz trdega diska ali pošiljanje neželene elektronske pošte

234
00:10:25,150 --> 00:10:27,000
ali nekako napad stroj?

235
00:10:27,000 --> 00:10:29,570
>> Torej, če bi vsak od teh
Črke samo pomeni,

236
00:10:29,570 --> 00:10:32,380
konceptualno, napad, napad,
napad, napad, nekateri slabo kodo

237
00:10:32,380 --> 00:10:36,410
da je nekdo drug napisal, ampak
če je ta oseba dovolj pametna

238
00:10:36,410 --> 00:10:40,790
ne samo vključujejo vse
teh RM-RFS, ampak tudi

239
00:10:40,790 --> 00:10:46,100
imajo njegove zadnjih nekaj bajtov
je število, ki ustreza

240
00:10:46,100 --> 00:10:50,540
na naslov njegovega
ali sama napad koda

241
00:10:50,540 --> 00:10:53,820
da je on ali ona opravil v samo
tako, da ga na poziv,

242
00:10:53,820 --> 00:10:58,760
lahko učinkovito trik računalnik
v opazil, ko je f storiti izvršitve,

243
00:10:58,760 --> 00:11:02,400
oh, to je čas, da skočite
nazaj na rdečo povratni naslov.

244
00:11:02,400 --> 00:11:06,070
Ampak zato, ker je on ali ona je nekako
prekrivale, da povratni naslov

245
00:11:06,070 --> 00:11:09,602
s svojo lastno številko,
in oni so dovolj pametni,

246
00:11:09,602 --> 00:11:11,560
da je zasnovana tako, da
Številka sklicevati, saj vas

247
00:11:11,560 --> 00:11:13,740
glej v super top
levem kotu tam,

248
00:11:13,740 --> 00:11:18,020
dejanski naslov v računalniku
Spomin na nekaj svojih napad kodo,

249
00:11:18,020 --> 00:11:21,740
slab človek lahko trik računalnik
v izvršilni svojo lastno kodo.

250
00:11:21,740 --> 00:11:23,700
>> In to kodo, še enkrat, je lahko karkoli.

251
00:11:23,700 --> 00:11:26,120
To je na splošno imenovana
lupina koda, ki je pravkar

252
00:11:26,120 --> 00:11:29,030
način rekel, da to ni
na splošno nekaj tako enostavno, kot rm-RF.

253
00:11:29,030 --> 00:11:32,340
To je pravzaprav nekaj podobnega Bash,
ali dejansko program, ki ga daje

254
00:11:32,340 --> 00:11:37,230
ali njen programski nadzor izvajati
karkoli drugega, ki to želijo.

255
00:11:37,230 --> 00:11:40,210
Torej, na kratko, vse to
izhaja iz preprostega dejstva,

256
00:11:40,210 --> 00:11:44,490
da ta bug vpleteni ne preverja
meje vaše bivanje.

257
00:11:44,490 --> 00:11:47,250
In zato, ker je način
računalniki delo je, da se

258
00:11:47,250 --> 00:11:49,430
uporabite stack od
učinkovito, konceptualno,

259
00:11:49,430 --> 00:11:54,830
spodaj na gor, potem pa elementi
pritisneš na kupu rastejo navzdol top,

260
00:11:54,830 --> 00:11:56,624
to je zelo problematično.

261
00:11:56,624 --> 00:11:58,290
Zdaj obstajajo načini za delo okoli tega.

262
00:11:58,290 --> 00:12:00,800
In odkrito povedano, obstajajo jeziki
s katerimi obidete.

263
00:12:00,800 --> 00:12:03,100
Java je imunski, na primer,
na to vprašanje.

264
00:12:03,100 --> 00:12:04,110
Ker se vam ne dajejo napotke.

265
00:12:04,110 --> 00:12:05,943
Se vam ne dajejo
neposredne naslove spominske.

266
00:12:05,943 --> 00:12:08,560
Torej s tem moč, da imamo
dotakniti ničesar v spomin

267
00:12:08,560 --> 00:12:11,580
Želimo, da prihaja, seveda, veliko tveganje.

268
00:12:11,580 --> 00:12:12,430
>> Torej pazi.

269
00:12:12,430 --> 00:12:14,596
Če je, odkrito povedano, v prihodnjih mesecih
ali let, da pridejo, kadarkoli

270
00:12:14,596 --> 00:12:17,740
boste brali o nekem izkoriščanju
programa ali strežnika,

271
00:12:17,740 --> 00:12:22,370
če ste že kdaj videli namig nečesa
kot buffer overflow napadi,

272
00:12:22,370 --> 00:12:25,390
ali kup overflow je druga vrsta
napada, pisane v duhu,

273
00:12:25,390 --> 00:12:28,770
kar navdihuje spletne strani
ime, če ga poznate,

274
00:12:28,770 --> 00:12:33,170
je vse govoriš samo
prepolno velikosti neke značaja

275
00:12:33,170 --> 00:12:36,200
matrika ali nekaj matrika bolj na splošno.

276
00:12:36,200 --> 00:12:38,822
Vsa vprašanja, nato na to?

277
00:12:38,822 --> 00:12:39,780
Ne poskušajte tega doma.

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

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

280
00:12:42,300 --> 00:12:47,270
Torej malloc je bila doslej naša nova
prijatelj, da bomo lahko dodeliti pomnilnika

281
00:12:47,270 --> 00:12:50,540
da ne bomo nujno vedeti
napreduje, da želimo, da nimamo

282
00:12:50,540 --> 00:12:52,920
trdega kodo v našo
število programov, kot so 12.

283
00:12:52,920 --> 00:12:55,550
Ko nam uporabniku pove, koliko
Podatki on ali ona želi vhod,

284
00:12:55,550 --> 00:12:58,000
lahko malloc, da je veliko pomnilnika.

285
00:12:58,000 --> 00:13:01,484
>> Torej malloc se izkaže, da
Koliko smo se ga uporablja,

286
00:13:01,484 --> 00:13:03,900
izrecno zadnji čas, nato pa
fantje so ga s pomočjo

287
00:13:03,900 --> 00:13:08,160
za getstring nevede za
nekaj tednov, vse pomnilnika malloc je

288
00:13:08,160 --> 00:13:09,820
prihaja iz tako imenovanega kup.

289
00:13:09,820 --> 00:13:13,852
In zato getstring, na primer,
mogoče dodeliti pomnilnika dinamično

290
00:13:13,852 --> 00:13:16,060
ne da bi vedel, kaj ste
dogaja, da tip vnaprej,

291
00:13:16,060 --> 00:13:21,520
ti pa vrnejo kazalec na ta spomin,
in da je spomin še vedno obdržite,

292
00:13:21,520 --> 00:13:24,080
tudi po getstring donose.

293
00:13:24,080 --> 00:13:27,450
Ker odpoklic po vsem tem
Snop se nenehno dogaja gor in dol,

294
00:13:27,450 --> 00:13:27,950
gor in dol.

295
00:13:27,950 --> 00:13:30,230
In takoj, ko gre
določa, da je katera koli pomnilnika

296
00:13:30,230 --> 00:13:33,030
Ta funkcija se uporablja, naj
ne bo nihče drug uporablja.

297
00:13:33,030 --> 00:13:34,570
To je nerazumljivo vrednote zdaj.

298
00:13:34,570 --> 00:13:36,120
>> Ampak kup je tu.

299
00:13:36,120 --> 00:13:39,360
In kaj je lepo o malloc je, da
ko malloc dodeljuje pomnilnik tu gor,

300
00:13:39,360 --> 00:13:42,070
to ni vplivalo na
večina del, ki jih je kupu.

301
00:13:42,070 --> 00:13:46,000
In tako se lahko vsaka funkcija dostop
pomnilnika, ki je bil malloc'd,

302
00:13:46,000 --> 00:13:49,120
tudi s funkcijo kot getstring,
tudi potem, ko se je vrnil.

303
00:13:49,120 --> 00:13:51,700
>> Zdaj, nasprotno od funkcije malloc je brezplačna.

304
00:13:51,700 --> 00:13:53,900
In res, ti pravilo
morali začeti o sprejetju

305
00:13:53,900 --> 00:13:58,950
je vsak, vsak, kadarkoli boste uporabili malloc
morate sami uporabljate brezplačno, na koncu,

306
00:13:58,950 --> 00:14:00,280
na isti kazalec.

307
00:14:00,280 --> 00:14:03,289
Ves ta čas smo bili pisno
buggy, buggy kodo, zaradi mnogih razlogov.

308
00:14:03,289 --> 00:14:05,580
Vendar pa je eden, ki je
uporabo knjižnice CS50, ki

309
00:14:05,580 --> 00:14:09,010
sam je namerno
buggy, pušča spomin.

310
00:14:09,010 --> 00:14:11,410
Vsakič, ko sem poklical getstring
v zadnjih nekaj tednih

311
00:14:11,410 --> 00:14:13,870
smo asking poslovanja
sistem Linux, za spomin.

312
00:14:13,870 --> 00:14:15,780
In nikoli, ko ga dal nazaj.

313
00:14:15,780 --> 00:14:17,730
In to ni v
praksa, dobra stvar.

314
00:14:17,730 --> 00:14:20,330
>> In Valgrind, ena
orodja, uvedene v pset 4,

315
00:14:20,330 --> 00:14:22,900
je vse o vam bomo pomagali
Zdaj našli hrošče, kot je ta.

316
00:14:22,900 --> 00:14:27,060
Toda na srečo pset 4, vam ni treba
uporabiti knjižnico CS50 ali getstring.

317
00:14:27,060 --> 00:14:31,220
Torej, vse napake, povezane s spominom so
na koncu bo svoje.

318
00:14:31,220 --> 00:14:34,060
>> Torej malloc je več kot le
primeren za ta namen.

319
00:14:34,060 --> 00:14:37,420
Mi lahko dejansko zdaj rešiti
bistveno različne težave,

320
00:14:37,420 --> 00:14:41,640
in temeljito reševanje problemov več
učinkovito kot na obljubo Tedensko ZERO.

321
00:14:41,640 --> 00:14:44,720
Doslej je to najbolj seksi
podatkovne strukture smo imeli.

322
00:14:44,720 --> 00:14:47,804
In podatkovne strukture I pomeni samo
način konceptualizaciji pomnilnika

323
00:14:47,804 --> 00:14:50,720
na način, ki presega samo rekel,
to je int, je to znak.

324
00:14:50,720 --> 00:14:52,930
Lahko začnemo kasetnih stvari skupaj.

325
00:14:52,930 --> 00:14:54,460
>> Torej matrika videti takole.

326
00:14:54,460 --> 00:14:57,270
In kaj je bilo ključnega pomena pri približno
Niz je, da vam daje

327
00:14:57,270 --> 00:14:59,724
back-to-back kosi
spomin, od katerih je vsak

328
00:14:59,724 --> 00:15:02,765
se bo istega tipa, int
int, int, int ali char, char, char,

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

330
00:15:03,330 --> 00:15:04,496
Toda obstaja nekaj slabosti.

331
00:15:04,496 --> 00:15:06,570
Ta primer je
matrika velikosti šest.

332
00:15:06,570 --> 00:15:10,650
Recimo, da se zapolni ta niz s šestimi
številke in nato, zaradi kakršnega koli razloga,

333
00:15:10,650 --> 00:15:13,187
vaš uporabnik želi, da bi
vam sedmi številko.

334
00:15:13,187 --> 00:15:14,020
Kje si ga dal?

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

336
00:15:15,490 --> 00:15:18,990
>> Kaj je rešitev, če imate
ustvaril niz na sklad,

337
00:15:18,990 --> 00:15:22,030
na primer, samo z tedna
dva zapisa, da bomo uvedli,

338
00:15:22,030 --> 00:15:23,730
kvadratnih oklepajih s številnimi znotraj?

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

340
00:15:25,160 --> 00:15:27,260
No, imaš šest
Številke v teh poljih.

341
00:15:27,260 --> 00:15:28,530
Kaj bi svojim instinktom bilo?

342
00:15:28,530 --> 00:15:29,973
Kje bi si želeli, da bi ga?

343
00:15:29,973 --> 00:15:30,860
>> OBČINSTVO: [neslišno]

344
00:15:30,860 --> 00:15:31,315
>> DAVID J. Malan: Oprostite?

345
00:15:31,315 --> 00:15:32,380
>> OBČINSTVO: Daj ga na koncu.

346
00:15:32,380 --> 00:15:33,796
>> DAVID J. Malan: Daj na koncu.

347
00:15:33,796 --> 00:15:35,880
Torej nekaj več kot na desni,
izven tega prostora.

348
00:15:35,880 --> 00:15:38,710
Kar bi bilo lepo, vendar pa
Izkazalo se je, da ne morem storiti.

349
00:15:38,710 --> 00:15:41,350
Ker če si ne prosi
Za ta kos pomnilnika,

350
00:15:41,350 --> 00:15:44,490
da bi se lahko po naključju to to
se nekatere druge spremenljivke uporablja

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

352
00:15:45,030 --> 00:15:49,210
Pomisli nazaj teden ali dva, ko smo jih
out Zamyla and Davin and Gabe je imen

353
00:15:49,210 --> 00:15:49,930
v pomnilniku.

354
00:15:49,930 --> 00:15:51,638
Bili so dobesedno
back to back to back.

355
00:15:51,638 --> 00:15:53,550
Torej, ne moremo nujno
Verjamemo, da Karkoli

356
00:15:53,550 --> 00:15:55,800
tukaj je na voljo za mene za uporabo.

357
00:15:55,800 --> 00:15:56,990
>> Torej, kaj še lahko naredil?

358
00:15:56,990 --> 00:16:00,282
No, ko ti zavedali
Potrebujemo paleto velikosti sedem,

359
00:16:00,282 --> 00:16:02,490
si lahko samo ustvariti
array velikosti sedem nato uporabite

360
00:16:02,490 --> 00:16:05,950
zanke for ali while zanko,
kopirajte v novo paleto,

361
00:16:05,950 --> 00:16:09,680
in potem nekako le znebiti
Ta matrika ali samo prenehate uporabljati.

362
00:16:09,680 --> 00:16:12,130
Ampak to ni posebej učinkovita.

363
00:16:12,130 --> 00:16:15,340
Skratka, nizi, ne pustite
ti dinamično spreminjanje velikosti.

364
00:16:15,340 --> 00:16:17,900
>> Torej, na eni strani dobiš
random access, kar je neverjetno.

365
00:16:17,900 --> 00:16:20,108
Zato, ker nam omogoča delati stvari
kot so deli in vladaj,

366
00:16:20,108 --> 00:16:23,100
binarno iskanje, kar smo jih
govorili na zaslonu tukaj.

367
00:16:23,100 --> 00:16:24,950
Ampak ti si slikal v kotu.

368
00:16:24,950 --> 00:16:27,810
Takoj, ko ste zadeli
konec tvoje matrike,

369
00:16:27,810 --> 00:16:29,980
moraš narediti zelo
draga operacija

370
00:16:29,980 --> 00:16:33,910
ali pisati cel kup kode
Do zdaj se ukvarjajo s tem problemom.

371
00:16:33,910 --> 00:16:36,680
>> Pa kaj, če namesto tega smo imeli
nekaj, kar se imenuje seznam,

372
00:16:36,680 --> 00:16:38,820
ali povezani seznam zlasti?

373
00:16:38,820 --> 00:16:41,930
Kaj pa, če namesto da
pravokotniki back to back to back,

374
00:16:41,930 --> 00:16:45,730
imamo pravokotnike, ki puščajo malo
malo Vrckanje prostora med njimi?

375
00:16:45,730 --> 00:16:49,670
In čeprav sem to pripraviti
slika ali prilagoditi to sliko

376
00:16:49,670 --> 00:16:54,696
iz ene od besedil tukaj nazaj na
back to back zelo urejeno, v resnici,

377
00:16:54,696 --> 00:16:56,820
eden od teh pravokotnikov
bi lahko tukaj v spomin.

378
00:16:56,820 --> 00:16:58,028
Eden od njih bi lahko tu gor.

379
00:16:58,028 --> 00:17:00,420
Eden od njih je lahko tukaj,
tukaj, in tako naprej.

380
00:17:00,420 --> 00:17:02,910
>> Toda kaj, če smo opozorili,
v tem primeru, puščice

381
00:17:02,910 --> 00:17:05,650
da nekako povezati ti
pravokotnikov skupaj?

382
00:17:05,650 --> 00:17:08,170
Dejansko smo videli tehnična
inkarnacija puščico.

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

384
00:17:09,839 --> 00:17:13,710
Kaj smo uporabili v nedavnem
dni, da se pod pokrovom motorja,

385
00:17:13,710 --> 00:17:15,210
je predstavnik puščico?

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

387
00:17:16,290 --> 00:17:17,349
Kazalec, kajne?

388
00:17:17,349 --> 00:17:19,780
>> Pa kaj, če namesto
Samo shranjevanje številk,

389
00:17:19,780 --> 00:17:23,130
kot 9, 17, 22, 26, 34,
Kaj pa, če mi ne shranijo

390
00:17:23,130 --> 00:17:27,079
Samo število ampak kazalec
ob vsakem takem številu?

391
00:17:27,079 --> 00:17:30,690
Tako, da je veliko, kot bi navoj
iglo skozi cel kup materiala,

392
00:17:30,690 --> 00:17:32,950
nekako vezanje stvari
skupaj, podobno lahko

393
00:17:32,950 --> 00:17:35,550
smo s kazalci, kot so
inkarnirali s puščicami tukaj,

394
00:17:35,550 --> 00:17:38,550
vrste pletejo
Ti posamezni pravokotniki

395
00:17:38,550 --> 00:17:41,780
z učinkovito uporabo kazalec
poleg vsakega številko, da

396
00:17:41,780 --> 00:17:46,065
opozarja na nekaterih naslednjo številko, da
poudarja, da v zameno nekaj naslednja številka?

397
00:17:46,065 --> 00:17:47,940
Torej, z drugimi besedami, kaj
če bi dejansko želeli

398
00:17:47,940 --> 00:17:49,820
izvesti kaj takega?

399
00:17:49,820 --> 00:17:53,610
No, na žalost, ti pravokotniki,
Vsaj ena z 9, 17, 22,

400
00:17:53,610 --> 00:17:57,040
in tako naprej, to ni več
lepo trgi z ločenima številkami.

401
00:17:57,040 --> 00:17:59,960
Dno, pravokotnik
pod 9, na primer,

402
00:17:59,960 --> 00:18:04,330
predstavlja to, kar bi morala
je kazalec, 32 bitov.

403
00:18:04,330 --> 00:18:09,460
Zdaj, jaz še nisem seznanjen z nobenimi podatkovni tip
v C-ju, ki vam omogoča ne samo int

404
00:18:09,460 --> 00:18:11,630
vendar je kazalec v celoti.

405
00:18:11,630 --> 00:18:15,020
>> Torej, kaj je rešitev, če želimo
izumiti lastne odgovor na to?

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

407
00:18:15,760 --> 00:18:16,640
>> OBČINSTVO: [neslišno]

408
00:18:16,640 --> 00:18:17,360
>> DAVID J. Malan: Kaj je to?

409
00:18:17,360 --> 00:18:17,880
>> OBČINSTVO: Nova struktura.

410
00:18:17,880 --> 00:18:19,590
>> DAVID J. Malan: Ja, zakaj
ne bomo zgradili novo strukturo,

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

412
00:18:20,920 --> 00:18:25,990
Videli smo konstruktov prej, če za kratek čas,
kjer smo se ukvarjali s strukturo študentov

413
00:18:25,990 --> 00:18:27,780
kot je ta, ki je imel ime in hišo.

414
00:18:27,780 --> 00:18:31,980
V pset 3 zlom ste uporabili celoten
kup structs-- GRect in GOvals

415
00:18:31,980 --> 00:18:34,810
da Stanford ustvarjena za
cluster informacije skupaj.

416
00:18:34,810 --> 00:18:38,580
Pa kaj, če bomo to isto idejo
ključne besede "typedef" in "struct,"

417
00:18:38,580 --> 00:18:42,890
in potem nekaj študent specifične stvari,
in razvijajo to v naslednje:

418
00:18:42,890 --> 00:18:46,210
typedef struct node-- in vozlišča
samo zelo generično računalništvo

419
00:18:46,210 --> 00:18:49,980
izraz za nekaj, kar v strukturi podatkov,
vsebnik v podatkovno strukturo.

420
00:18:49,980 --> 00:18:53,900
Vozlišče Trdim, se dogaja, da imajo
int n, povsem enostavna,

421
00:18:53,900 --> 00:18:58,810
nato pa malo bolj cryptically,
ta druga vrstica struct vozlišče * naslednji.

422
00:18:58,810 --> 00:19:01,300
Toda v manj strokovnih izrazov,
kaj je to druga vrstica

423
00:19:01,300 --> 00:19:02,980
kode notranjosti zavitimi oklepaji?

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

425
00:19:03,737 --> 00:19:04,851
>> OBČINSTVO: [neslišno]

426
00:19:04,851 --> 00:19:06,600
DAVID J. Malan:
kazalec na drugo vozlišče.

427
00:19:06,600 --> 00:19:09,910
Torej res, skladnje malo skrivnosten.

428
00:19:09,910 --> 00:19:13,250
Ampak, če ste prebrali dobesedno,
Naslednja je ime spremenljivke.

429
00:19:13,250 --> 00:19:14,410
Kakšna je njegova vrsta podatkov?

430
00:19:14,410 --> 00:19:18,206
To je malce verbose tokrat,
ampak to je tipa struct vozlišče *.

431
00:19:18,206 --> 00:19:22,960
Vsakič, ko smo videli nekaj zvezdo, ki
pomeni, da je kazalec za to vrsto podatkov.

432
00:19:22,960 --> 00:19:26,810
Torej, naslednjič, je očitno
kazalec na struct vozlišče.

433
00:19:26,810 --> 00:19:28,310
>> Zdaj, kaj je struct vozlišče?

434
00:19:28,310 --> 00:19:31,044
No, opazil vidite tiste
iste besede v zgornjem desnem kotu.

435
00:19:31,044 --> 00:19:33,960
In res, boste videli tudi besedo
"Node" tukaj na spodnji levi strani.

436
00:19:33,960 --> 00:19:35,640
In to je pravzaprav samo udobje.

437
00:19:35,640 --> 00:19:39,930
Opazimo, da v naši definiciji študentski
tam je beseda "študent" samo enkrat.

438
00:19:39,930 --> 00:19:42,510
In to zato, ker študent
objekt ni bil sama nase.

439
00:19:42,510 --> 00:19:45,340
Nič ni notri študenta
da je treba opozoriti na drug študent,

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

441
00:19:45,610 --> 00:19:47,630
To bi bilo nekako
čudno v resničnem svetu.

442
00:19:47,630 --> 00:19:50,880
>> Toda s vozlišče v povezan
seznam, bomo želeli vozlišče

443
00:19:50,880 --> 00:19:53,970
da se referenčni s podobnim ciljem.

444
00:19:53,970 --> 00:19:57,900
In tako opazite spremembo tukaj ni
samo tisto, kar je znotraj zavitimi oklepaji.

445
00:19:57,900 --> 00:20:00,800
Vendar pa smo dodali besedo "node"
na vrhu kot tudi

446
00:20:00,800 --> 00:20:02,930
dodajanjem na dnu
namesto "študenta".

447
00:20:02,930 --> 00:20:06,000
In to je samo tehnična podrobnost
tako da, še enkrat, vaš struktura podatkov

448
00:20:06,000 --> 00:20:11,380
lahko sama nase, tako da
vozlišče lahko kažejo na drugo takšno vozlišče.

449
00:20:11,380 --> 00:20:13,840
>> Torej, kaj je to na koncu
bo to pomenilo za nas?

450
00:20:13,840 --> 00:20:17,560
No, ena, te stvari v notranjosti
je vsebina našega vozlišča.

451
00:20:17,560 --> 00:20:19,360
Ta stvar tu gor,
zgoraj desno, samo zato, da

452
00:20:19,360 --> 00:20:20,860
da spet lahko govorimo sebi.

453
00:20:20,860 --> 00:20:23,401
In potem najbolj oddaljene stvari,
čeprav vozlišče je nov izraz

454
00:20:23,401 --> 00:20:25,500
morda je še vedno
Enako kot študent in kaj

455
00:20:25,500 --> 00:20:27,520
je pod pokrovom v SPL.

456
00:20:27,520 --> 00:20:31,095
>> Torej, če smo zdaj želeli začeti
izvajanje te povezani seznam,

457
00:20:31,095 --> 00:20:33,220
kako bi lahko prevedli
kaj takega kodo?

458
00:20:33,220 --> 00:20:35,350
No, pa sem videl samo
Primer programa, ki

459
00:20:35,350 --> 00:20:36,840
dejansko uporablja povezani seznam.

460
00:20:36,840 --> 00:20:40,870
Med današnjim distribucijskega kodo
je program, imenovan Seznam Zero.

461
00:20:40,870 --> 00:20:44,980
In če sem teči to sem ustvaril super
preprost GUI, grafični uporabniški vmesnik,

462
00:20:44,980 --> 00:20:46,460
ampak to je res samo printf.

463
00:20:46,460 --> 00:20:50,930
In zdaj sem sam dal nekaj meni
options-- Delete, Insert, iskanje,

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

465
00:20:51,750 --> 00:20:52,630
In Končaj.

466
00:20:52,630 --> 00:20:55,970
To so le skupne operacije na
podatkovna struktura znana kot seznam povezav.

467
00:20:55,970 --> 00:20:58,409
>> Zdaj, Delete bo
Številko zbrišete s seznama.

468
00:20:58,409 --> 00:21:00,200
Vstavi se dogaja, da dodate
številka na seznamu.

469
00:21:00,200 --> 00:21:02,181
Iskanje se bo izgledalo
za številko na seznamu.

470
00:21:02,181 --> 00:21:04,930
In premikanja je samo fancy način
rekel, sprehod po seznamu,

471
00:21:04,930 --> 00:21:06,245
natisnete, ampak to je to.

472
00:21:06,245 --> 00:21:07,720
Ne spreminjajo na kakršen koli način.

473
00:21:07,720 --> 00:21:08,570
>> Torej poskusimo to.

474
00:21:08,570 --> 00:21:10,160
Pojdimo naprej in tip 2.

475
00:21:10,160 --> 00:21:12,710
In potem bom
vstavite številko, pravijo 9.

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

477
00:21:13,620 --> 00:21:17,480
In zdaj moj program je le
programirana reči, seznam je zdaj 9.

478
00:21:17,480 --> 00:21:20,190
Zdaj pa, če grem naprej in
pa spet vstavite, naj

479
00:21:20,190 --> 00:21:23,680
grem naprej in pomanjšanje in tip v 17.

480
00:21:23,680 --> 00:21:25,770
Sedaj je moj seznam, je 9, potem 17.

481
00:21:25,770 --> 00:21:27,750
Če bi še enkrat vstaviti, pa preskočite enega.

482
00:21:27,750 --> 00:21:32,400
Namesto, da bi 22, kot je na sliki smo jih
gledal sem, naj skoči naprej

483
00:21:32,400 --> 00:21:34,630
in vstavite 26 naprej.

484
00:21:34,630 --> 00:21:36,230
Torej bom tip 26.

485
00:21:36,230 --> 00:21:37,755
Seznam je kot pričakujem.

486
00:21:37,755 --> 00:21:40,630
Toda zdaj, samo da vidim, če to kodo
se bo fleksibilna, pusti me zdaj

487
00:21:40,630 --> 00:21:43,520
tip 22, ki je vsaj
konceptualno, če smo

488
00:21:43,520 --> 00:21:46,520
Ohranitev te razporejene, ki je dejansko
bo še en cilj, prav zdaj,

489
00:21:46,520 --> 00:21:48,690
bi morala iti v med 17. in 26..

490
00:21:48,690 --> 00:21:50,270
Zato sem zadeti nastopiti.

491
00:21:50,270 --> 00:21:51,380
Dejansko, da deluje.

492
00:21:51,380 --> 00:21:54,950
In zdaj mi vstavite
nazadnje, na sliki, 34.

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

494
00:21:55,450 --> 00:21:58,980
Za zdaj naj določi, da
Brisanje in Traverse in iskanje storiti,

495
00:21:58,980 --> 00:21:59,760
v resnici deluje.

496
00:21:59,760 --> 00:22:04,180
V bistvu, če ne bom teči iskanje, dajva
poiščete številko 22, Enter.

497
00:22:04,180 --> 00:22:05,010
22 je mogoče najti.

498
00:22:05,010 --> 00:22:07,580
Torej, to je tisto, kar ta
Program Seznam Zero počne.

499
00:22:07,580 --> 00:22:10,230
>> Toda kaj se dejansko dogaja
o, ki izvaja to?

500
00:22:10,230 --> 00:22:14,530
No, najprej bi morali, in dejansko
Imam, datoteka z imenom list0.h.

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

502
00:22:16,540 --> 00:22:20,690
In nekje je to
linija, typedef struct vozlišče,

503
00:22:20,690 --> 00:22:24,850
potem imam zavitimi oklepaji, int n, in
potem struct-- kaj je definicija?

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

505
00:22:26,530 --> 00:22:28,545
Struct vozlišče naslednji.

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

507
00:22:29,920 --> 00:22:31,045
Zato moramo zvezdo.

508
00:22:31,045 --> 00:22:33,420
Sedaj tehnično smo prišli v
Navada je risba tukaj.

509
00:22:33,420 --> 00:22:35,670
Lahko vidite učbenikov in
Spletne reference to storite tam.

510
00:22:35,670 --> 00:22:36,660
To je funkcionalno enakovredna.

511
00:22:36,660 --> 00:22:37,980
V bistvu, to je malo bolj tipično.

512
00:22:37,980 --> 00:22:40,563
Ampak bom biti skladni s kakšnimi
sva zadnjič in to.

513
00:22:40,563 --> 00:22:42,350
In potem na koncu, bom to naredil.

514
00:22:42,350 --> 00:22:45,550
>> Torej v glavi datoteke
nekje v list0.h

515
00:22:45,550 --> 00:22:49,200
Danes je ta opredelitev struct,
in morda nekatere druge stvari.

516
00:22:49,200 --> 00:22:52,580
Medtem v list0c tam
bo še nekaj stvari.

517
00:22:52,580 --> 00:22:54,740
Ampak bomo samo
začeti in ne končati to.

518
00:22:54,740 --> 00:22:59,690
List0.h je datoteka želim
v mojem C datoteko vključiti.

519
00:22:59,690 --> 00:23:03,910
In potem na neki točki sem
dogaja, da imajo int, glavno, nična.

520
00:23:03,910 --> 00:23:06,530
In potem bom
imajo nekaj opravkov je tukaj.

521
00:23:06,530 --> 00:23:10,620
Jaz sem tudi dogaja, da imajo
Prototip, kot nična, iskanje, int,

522
00:23:10,620 --> 00:23:13,610
n, katerih namen v življenju je
za iskanje elementa.

523
00:23:13,610 --> 00:23:18,310
In potem tukaj Trdim v
današnja koda, nična, iskanje, int, n,

524
00:23:18,310 --> 00:23:21,020
no podpičje vendar odprta zavitimi oklepaji.

525
00:23:21,020 --> 00:23:25,049
In zdaj bi rad nekako iskanje
za element v tem seznamu.

526
00:23:25,049 --> 00:23:27,340
Vendar nimamo dovolj
Informacije na zaslonu še.

527
00:23:27,340 --> 00:23:29,800
Imam dejansko ni
predstavljal seznam sam.

528
00:23:29,800 --> 00:23:33,070
Torej en način, da bi lahko izvajala
povezani seznam v programu

529
00:23:33,070 --> 00:23:37,520
je nekako želijo narediti nekaj
kot izjavljam povezani seznam tukaj.

530
00:23:37,520 --> 00:23:40,520
Zaradi enostavnosti, bom, da bi
ta globalni, čeprav Na splošno

531
00:23:40,520 --> 00:23:41,645
ne bi smeli početi to preveč.

532
00:23:41,645 --> 00:23:43,260
Vendar bo poenostavil ta primer.

533
00:23:43,260 --> 00:23:45,890
Torej, želim, da razglasi
povezani seznam tukaj.

534
00:23:45,890 --> 00:23:47,010
Zdaj, kako lahko to storim?

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

536
00:23:48,810 --> 00:23:50,750
>> Tukaj je slika povezanega seznama.

537
00:23:50,750 --> 00:23:53,030
In jaz res ne
vem trenutno kako

538
00:23:53,030 --> 00:23:56,710
Jaz grem pa predstavlja
Toliko stvari z enim samim

539
00:23:56,710 --> 00:23:58,040
spremenljivka v pomnilniku.

540
00:23:58,040 --> 00:23:59,160
Vendar pomislite za trenutek.

541
00:23:59,160 --> 00:24:00,830
Ves ta čas smo imeli
strune, ki smo jih nato

542
00:24:00,830 --> 00:24:02,913
je pokazala, da so nizi
Znaki, ki jih nato

543
00:24:02,913 --> 00:24:05,740
je pokazala, da samo se pointer
na prvi znak

544
00:24:05,740 --> 00:24:08,890
v niz znakov
da je null zaključi.

545
00:24:08,890 --> 00:24:13,530
Torej s to logiko, in s tem
picture vrsta sejanje svoje misli,

546
00:24:13,530 --> 00:24:17,964
kaj potrebujejo smo pravzaprav napisali v našem
koda za zastopanje povezani seznam?

547
00:24:17,964 --> 00:24:21,130
Koliko te informacije potrebujemo
ujeti v C kodo, bi rekli?

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
>> OBČINSTVO: Potrebujemo kazalec na vozlišče.

551
00:24:24,738 --> 00:24:26,237
DAVID J. Malan: kazalec na vozlišče.

552
00:24:26,237 --> 00:24:29,320
Še posebej, ki node bi bil vaš
instinkt je, da kazalec?

553
00:24:29,320 --> 00:24:30,026
>> OBČINSTVO: prvo vozlišče.

554
00:24:30,026 --> 00:24:31,942
>> DAVID J. Malan: Ja,
Verjetno je samo prvi.

555
00:24:31,942 --> 00:24:34,030
In opazil, prvi
vozlišče je drugačna oblika.

556
00:24:34,030 --> 00:24:37,690
To je samo polovica velikost struct,
ker je res samo kazalec.

557
00:24:37,690 --> 00:24:44,650
Torej, kaj lahko v resnici storiti, je razglasila
povezani seznam, da bi tipa vozlišča *.

558
00:24:44,650 --> 00:24:47,780
In kaj je to šele prvi klic
in ga inicializirati na nič.

559
00:24:47,780 --> 00:24:49,910
Torej null, še enkrat, je prišel
v sliko tukaj.

560
00:24:49,910 --> 00:24:53,620
Ne samo, da je nična uporablja kot kot posebna
vrne vrednost za stvari, kot getstring

561
00:24:53,620 --> 00:24:57,770
in malloc, null tudi nič
kazalec, pomanjkanje kazalcem,

562
00:24:57,770 --> 00:24:58,430
če hočete.

563
00:24:58,430 --> 00:25:00,309
To samo pomeni nič, je še tukaj.

564
00:25:00,309 --> 00:25:02,100
Zdaj prvič, lahko imam
imenujemo to karkoli.

565
00:25:02,100 --> 00:25:04,200
Lahko bi ga imenovali "seznam"
ali poljubno število drugih stvari.

566
00:25:04,200 --> 00:25:06,960
Ampak jaz sem jo kliče "prvi", tako da
it uravna s te slike.

567
00:25:06,960 --> 00:25:10,280
Torej samo kot niz lahko predstavljal
z naslovom prvi bajt,

568
00:25:10,280 --> 00:25:11,280
Tako lahko povezani seznam.

569
00:25:11,280 --> 00:25:13,480
In bomo videli druge podatke
strukture zastopa

570
00:25:13,480 --> 00:25:16,700
z enim samim kazalnikom,
32-bit puščica, ki kaže

571
00:25:16,700 --> 00:25:18,740
na zelo prvo vozlišče v strukturi.

572
00:25:18,740 --> 00:25:20,340
>> Ampak zdaj pa pričakujemo težave.

573
00:25:20,340 --> 00:25:23,230
Če sem le spomnimo
v mojem programu naslov

574
00:25:23,230 --> 00:25:27,220
prvega vozla, prvi
pravokotnik, v to strukturo podatkov,

575
00:25:27,220 --> 00:25:31,760
Kaj je bolje, da se primer o
Izvajanje preostanek svojega seznama?

576
00:25:31,760 --> 00:25:35,820
Kaj je ključna podrobnost, ki se dogaja
da bi to zagotovili dejansko deluje?

577
00:25:35,820 --> 00:25:39,250
In "dejansko deluje" I
pomeni, podobno kot niz,

578
00:25:39,250 --> 00:25:42,180
upamo, nam gredo od prvega znaka
v imenu Davin k drugi,

579
00:25:42,180 --> 00:25:44,755
da tretjič,
četrtič, do samega konca,

580
00:25:44,755 --> 00:25:47,880
Kako vemo, kdaj smo na koncu
iz povezanega seznama, ki izgleda takole?

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

582
00:25:50,035 --> 00:25:50,660
Ko je nična.

583
00:25:50,660 --> 00:25:53,640
In sem predstavljal te vrste, kot je
kot električni inženir moči,

584
00:25:53,640 --> 00:25:56,420
z malo ozemljitev
simbol, z menoj.

585
00:25:56,420 --> 00:25:58,246
Ampak to samo pomeni, null, v tem primeru.

586
00:25:58,246 --> 00:26:00,370
Lahko ga izdela poljubno število
načinov, vendar je ta avtor

587
00:26:00,370 --> 00:26:02,800
se je zgodilo, da uporabite ta simbol tukaj.

588
00:26:02,800 --> 00:26:06,260
>> Tako dolgo, dokler bomo zavezovanja
vseh teh vozlišč skupaj,

589
00:26:06,260 --> 00:26:08,600
Samo spomnimo, kjer
Prvi je, tako dolgo

590
00:26:08,600 --> 00:26:11,760
kot smo dali poseben simbol na
Zelo zadnji vozel v seznamu,

591
00:26:11,760 --> 00:26:15,130
in bomo uporabili null, ker je to
kar imamo na voljo, da nas,

592
00:26:15,130 --> 00:26:16,480
ta seznam je popolna.

593
00:26:16,480 --> 00:26:20,190
In tudi, če le ti dam kazalec na
Prvi element, ti, programer,

594
00:26:20,190 --> 00:26:22,486
zagotovo lahko dostopate še ostalo.

595
00:26:22,486 --> 00:26:24,360
Vendar pa naj vaše misli
sprehaja malo,

596
00:26:24,360 --> 00:26:26,140
če niso že
precej wandered-- kaj

597
00:26:26,140 --> 00:26:28,723
bo čas teče
najti ničesar na tem seznamu?

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

599
00:26:30,450 --> 00:26:33,470
Prekleto, to je velik O n,
kar ni slabo, v pravičnosti.

600
00:26:33,470 --> 00:26:34,800
Vendar je linearna.

601
00:26:34,800 --> 00:26:37,980
Smo dali gor, kaj funkcija
nizi, ki jih premika več

602
00:26:37,980 --> 00:26:43,130
k te slike dinamično
tkani skupaj ali povezana vozlišča?

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

604
00:26:44,970 --> 00:26:46,687
Mi obupal naključni dostop.

605
00:26:46,687 --> 00:26:48,770
Niz je lepo, ker
matematično vse

606
00:26:48,770 --> 00:26:50,340
je back to back to back to back.

607
00:26:50,340 --> 00:26:52,370
Čeprav te slike
zgleda lepa, in še

608
00:26:52,370 --> 00:26:55,830
čeprav izgleda, da teh vozlišč
so lepo razmaknjene, v resnici

609
00:26:55,830 --> 00:26:56,830
so lahko kjerkoli.

610
00:26:56,830 --> 00:27:01,590
OX1, Ox50, Ox123, Ox99, ti
vozlišča je lahko kjerkoli.

611
00:27:01,590 --> 00:27:05,960
Ker malloc ne dodeliti pomnilnika
iz kup, ampak kjerkoli na kup.

612
00:27:05,960 --> 00:27:09,080
Saj ni nujno, da veš, da je
dogaja, da se vrnem nazaj na hrbet.

613
00:27:09,080 --> 00:27:12,460
In zato je ta slika v resnici je
ne bo čisto ta lepa.

614
00:27:12,460 --> 00:27:16,140
>> Tako da bo trajalo nekaj
prizadevala za izvajanje te funkcije.

615
00:27:16,140 --> 00:27:17,880
Torej, kaj je sedaj izvaja iskanje.

616
00:27:17,880 --> 00:27:20,250
In bomo videli, vrste
pameten način za to.

617
00:27:20,250 --> 00:27:24,660
Torej, če sem funkcijo iskanja in
Jaz sem dal spremenljivo, celo število n

618
00:27:24,660 --> 00:27:28,490
iskati, moram vedeti
Nova skladnja za iskanje znotraj

619
00:27:28,490 --> 00:27:32,400
strukture, ki je
poudaril, da bi našli n.

620
00:27:32,400 --> 00:27:33,210
Torej, kaj je to.

621
00:27:33,210 --> 00:27:36,030
>> Torej, najprej bom šel
naprej in razglasi vozlišče *.

622
00:27:36,030 --> 00:27:39,400
In bom, da ga pokličete
kazalec, samo po dogovoru.

623
00:27:39,400 --> 00:27:41,710
In bom inicializacijo najprej.

624
00:27:41,710 --> 00:27:43,770
In zdaj lahko to storite
na številne načine.

625
00:27:43,770 --> 00:27:45,436
Ampak grem, da bi skupen pristop.

626
00:27:45,436 --> 00:27:50,180
Čeprav kazalec ni enaka
null, in da je veljavna skladnja.

627
00:27:50,180 --> 00:27:54,550
In to samo pomeni, da naredite naslednje, da
Dokler ti ne kaže na nič.

628
00:27:54,550 --> 00:27:55,800
Kaj hočem storiti?

629
00:27:55,800 --> 00:28:01,939
>> Če kazalec dot n, mi vrni
tistemu, equals-- enaka kaj?

630
00:28:01,939 --> 00:28:03,105
Kakšno vrednost iščem?

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

632
00:28:04,920 --> 00:28:06,590
Dejanska n, ki je bil sprejet leta.

633
00:28:06,590 --> 00:28:09,020
Torej, tukaj je še ena značilnost
o C in številnih jezikih.

634
00:28:09,020 --> 00:28:13,705
Čeprav strukture imenujemo vozlišča
ima n vrednost, povsem legitimno

635
00:28:13,705 --> 00:28:17,530
da ima tudi lokalno argument
ali spremenljivo imenuje n.

636
00:28:17,530 --> 00:28:20,085
Ker tudi mi z
človeške oči, se lahko razlikuje

637
00:28:20,085 --> 00:28:22,087
da ta n je verjetno
razlikuje od tega n.

638
00:28:22,087 --> 00:28:23,420
Ker sintaksa je drugačna.

639
00:28:23,420 --> 00:28:26,211
Imaš piko in kazalec,
ker tole je nič takšnega.

640
00:28:26,211 --> 00:28:27,290
Torej je to v redu.

641
00:28:27,290 --> 00:28:29,120
To je v redu, da jih pokličete iste stvari.

642
00:28:29,120 --> 00:28:32,380
>> Če bi se vam zdi to, da sem
dogaja, da želijo narediti nekaj

643
00:28:32,380 --> 00:28:35,000
podobno sporočamo, da smo našli n.

644
00:28:35,000 --> 00:28:37,930
In bomo pustite, da kot
komentar ali psevdokoda kodo.

645
00:28:37,930 --> 00:28:40,190
Drugega, in tukaj je
Zanimiv del tega, kar

646
00:28:40,190 --> 00:28:47,320
narediti, kar želim storiti, če trenutnim vozliščem
ne vsebuje n, da me skrbi?

647
00:28:47,320 --> 00:28:50,700
Kako doseči naslednje?

648
00:28:50,700 --> 00:28:53,710
Če je moj prst na
Trenutek je PTR, in to je

649
00:28:53,710 --> 00:28:55,920
kaže na karkoli
Prva je gledala,

650
00:28:55,920 --> 00:28:59,290
kako premakniti prst
na naslednje vozlišče v kodi?

651
00:28:59,290 --> 00:29:01,915
No, kaj je Orientacijska smo
bo sledila v tem primeru?

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

653
00:29:03,464 --> 00:29:04,380
OBČINSTVO: [neslišno].

654
00:29:04,380 --> 00:29:05,630
DAVID J. Malan: Ja, tako naprej.

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

656
00:29:06,640 --> 00:29:09,824
Torej, če se vrnem na moj
Koda tukaj, res, da sem

657
00:29:09,824 --> 00:29:12,990
dogaja, da gredo naprej in reči kazalec, ki
je le začasna variable-- je

658
00:29:12,990 --> 00:29:15,320
čudno ime, ptr, vendar
to je tako kot temp--

659
00:29:15,320 --> 00:29:19,234
Grem, da nastavite kazalec
enako kakršni koli kazalec je--

660
00:29:19,234 --> 00:29:22,150
in spet, to se bo
malo buggy za moment-- piko naslednjo.

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

662
00:29:23,551 --> 00:29:26,550
Z drugimi besedami, bom vzamem
prst, ki se kaže v tem vozlišču

663
00:29:26,550 --> 00:29:31,247
tu in bom rekel, veste,
kaj, si oglejte naslednje polje

664
00:29:31,247 --> 00:29:33,330
in premaknite prst
karkoli že je obrnjena.

665
00:29:33,330 --> 00:29:35,163
In to se dogaja, da
ponavljam, ponavljam, ponavljanje.

666
00:29:35,163 --> 00:29:37,630
Ampak ko pa moj prst
stop počne karkoli?

667
00:29:37,630 --> 00:29:40,095
Takoj, ko je kakšna vrstica kode brce v?

668
00:29:40,095 --> 00:29:40,970
OBČINSTVO: [neslišno]

669
00:29:40,970 --> 00:29:43,060
DAVID J. Malan: Če je točka, ko
kazalec ni enaka null.

670
00:29:43,060 --> 00:29:44,900
Na neki točki Prst imam
dogaja, da se kaže na null

671
00:29:44,900 --> 00:29:47,070
in bom za uresničitev
da je konec tega seznama.

672
00:29:47,070 --> 00:29:48,910
Zdaj, to je malo
bela laž zaradi enostavnosti.

673
00:29:48,910 --> 00:29:51,580
Izkazalo se je, da kljub temu, da
Pravkar se naučili to dot zapis

674
00:29:51,580 --> 00:29:55,220
struktur, kazalec ni struct.

675
00:29:55,220 --> 00:29:56,580
ptr je kaj?

676
00:29:56,580 --> 00:29:58,350
Samo, da se bolj nitpicky.

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

678
00:29:59,720 --> 00:30:01,360
To je kazalec na vozlišče.

679
00:30:01,360 --> 00:30:03,120
To ni vozel sama.

680
00:30:03,120 --> 00:30:06,650
Če sem imel zvezdo tukaj, kazalec
absolutely-- je vozlišče.

681
00:30:06,650 --> 00:30:08,650
To je kot en teden
Deklaracija spremenljivke,

682
00:30:08,650 --> 00:30:10,120
čeprav beseda "vozlišče" je nova.

683
00:30:10,120 --> 00:30:13,860
>> Toda takoj, ko bomo uvedli
zvezda, to je sedaj kazalec na vozlišče.

684
00:30:13,860 --> 00:30:17,960
In žal ne morete uporabljati
dot zapis za kazalec.

685
00:30:17,960 --> 00:30:21,070
Boste morali uporabiti puščico
zapis, ki je, presenetljivo,

686
00:30:21,070 --> 00:30:23,470
je prvič kateremkoli kos
sintakse zgleda intuitivno.

687
00:30:23,470 --> 00:30:25,245
To dobesedno videti kot puščica.

688
00:30:25,245 --> 00:30:26,370
In tako, da je dobra stvar.

689
00:30:26,370 --> 00:30:28,995
In tukaj dobesedno
Izgleda kot puščica.

690
00:30:28,995 --> 00:30:31,870
Zato mislim, da je la-- ne vem
Mislim, da sem pretirano stori tu-- I

691
00:30:31,870 --> 00:30:34,120
mislim, da je to zadnja nov kos
sintakse bomo videli.

692
00:30:34,120 --> 00:30:36,500
In na srečo, to je res
Malo bolj intuitivno.

693
00:30:36,500 --> 00:30:40,090
>> Zdaj, za tiste, ki ste
bi raje staro pot,

694
00:30:40,090 --> 00:30:42,550
lahko še vedno uporabljate dot zapis.

695
00:30:42,550 --> 00:30:45,380
Vendar pa je na ponedeljek-ih
pogovor, smo najprej

696
00:30:45,380 --> 00:30:50,530
treba iti tja, pojdi na to
obravnavo in dostop do zelenice.

697
00:30:50,530 --> 00:30:51,897
Torej, to je tudi pravilno.

698
00:30:51,897 --> 00:30:53,730
In odkrito povedano, to je
malo bolj občutljiv.

699
00:30:53,730 --> 00:30:56,530
Ti si dobesedno rekel, dereference
kazalec in tja.

700
00:30:56,530 --> 00:30:59,320
Potem zgrabi .N, polje se imenuje n.

701
00:30:59,320 --> 00:31:01,370
Vendar odkrito povedano, nihče ne želi
tipkati ali brati.

702
00:31:01,370 --> 00:31:03,620
In tako svet izumil
arrow zapis, ki

703
00:31:03,620 --> 00:31:06,980
je enaka, enaki,
to je samo skladenjska sladkor.

704
00:31:06,980 --> 00:31:10,570
Tako fancy način rekel to
izgleda bolje, ali pa je videti preprostejša.

705
00:31:10,570 --> 00:31:12,296
>> Torej, zdaj bom naredil še eno stvar.

706
00:31:12,296 --> 00:31:15,420
Bom rekel "odmor", ko imam
ugotovila, da tudi jaz ne vodijo iskal.

707
00:31:15,420 --> 00:31:17,620
Toda to je bistvo
za funkcijo iskanja.

708
00:31:17,620 --> 00:31:21,710
Ampak to je veliko lažje, v
konec, da ne bo sprehod skozi kodo.

709
00:31:21,710 --> 00:31:25,570
To je dejansko formalno izvajanje
iskanja v današnji distribucije kode.

710
00:31:25,570 --> 00:31:30,530
Upam si reči, da vložek ni
še posebej zabavno, da sprehod skozi

711
00:31:30,530 --> 00:31:33,180
vizualno, niti izbrisati, čeprav
čeprav na koncu dneva

712
00:31:33,180 --> 00:31:35,460
se omejijo na dokaj
preprosti tolči.

713
00:31:35,460 --> 00:31:36,330
>> Torej, kaj je to.

714
00:31:36,330 --> 00:31:39,250
Če boste humor me tukaj sem
prinašajo kup stresnih žogic.

715
00:31:39,250 --> 00:31:40,620
Prinesel sem kup številk.

716
00:31:40,620 --> 00:31:46,562
In bi lahko dobili le nekaj prostovoljcev
da predstavljajo 9, 17, 20, 22, 29, in 34?

717
00:31:46,562 --> 00:31:48,270
Torej v bistvu vsak
, ki je danes tu.

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

719
00:31:50,170 --> 00:31:52,760
To je ena, dva, tri,
štiri, pet, šest ljudi.

720
00:31:52,760 --> 00:31:55,740
In sem prosil, da tam-- videli, no
eden v hrbet postavlja svoje roke.

721
00:31:55,740 --> 00:32:01,910
OK, ena, dva, tri, štiri,
five-- mi preračunavanja balance-- šest.

722
00:32:01,910 --> 00:32:03,051
OK, ti šest pridi gor.

723
00:32:03,051 --> 00:32:04,050
Potrebovali bomo tudi druge ljudi.

724
00:32:04,050 --> 00:32:05,460
Smo prinesli dodatne stresne žogice.

725
00:32:05,460 --> 00:32:08,200
In če bi lahko, za
Samo trenutek, vrstica

726
00:32:08,200 --> 00:32:10,490
sami gor samo
kot te slike tukaj.

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

728
00:32:15,200 --> 00:32:15,959
>> V redu.

729
00:32:15,959 --> 00:32:17,125
Poglejmo, kako ti je ime?

730
00:32:17,125 --> 00:32:17,550
>> OBČINSTVO: Andrew.

731
00:32:17,550 --> 00:32:18,800
>> DAVID J. Malan: Andrew,
ste številka 9.

732
00:32:18,800 --> 00:32:19,540
Lepo, da sva se spoznala.

733
00:32:19,540 --> 00:32:20,400
Tukaj imaš.

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

735
00:32:21,593 --> 00:32:22,176
OBČINSTVO: 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
Številka 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
>> OBČINSTVO: Jaz sem Julia.

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

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

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

745
00:32:28,507 --> 00:32:29,340
OBČINSTVO: Christian.

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

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

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

749
00:32:32,040 --> 00:32:32,649
>> OBČINSTVO: JP.

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

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

752
00:32:34,880 --> 00:32:37,080
Torej, pojdi naprej in se noter-- 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
Pripravljenosti.

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
Ima kdo marker?

760
00:32:43,682 --> 00:32:44,890
OBČINSTVO: Imam Sharpie.

761
00:32:44,890 --> 00:32:45,660
DAVID J. Malan: Imaš 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
In ali ima kdo kos papirja?

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

766
00:32:51,562 --> 00:32:52,270
Shranite predavanje.

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

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

769
00:32:55,362 --> 00:32:56,320
OBČINSTVO: Smo jo dobili.

770
00:32:56,320 --> 00:32:57,600
DAVID J. Malan: Imamo ga?

771
00:32:57,600 --> 00:32:58,577
V redu, hvala.

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

773
00:33:01,380 --> 00:33:02,520
Gremo.

774
00:33:02,520 --> 00:33:03,582
Je bilo to pri vas?

775
00:33:03,582 --> 00:33:04,540
Pravkar ste rešili dan.

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

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

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

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

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

781
00:33:13,360 --> 00:33:14,890
Napačno sem 29, ampak OK.

782
00:33:14,890 --> 00:33:15,720
Pojdi naprej.

783
00:33:15,720 --> 00:33:18,114
Vredu, dam ti
pero nazaj za trenutek.

784
00:33:18,114 --> 00:33:19,280
Torej imamo ti ljudje tukaj.

785
00:33:19,280 --> 00:33:20,330
Dajva še eno drugo.

786
00:33:20,330 --> 00:33:23,750
Gabe, hočeš igrati
Prvi element tu?

787
00:33:23,750 --> 00:33:25,705
Vam bomo potrebovali točko
V teh drobnih ljudi.

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

789
00:33:26,930 --> 00:33:31,030
Torej, 9, 17, 20, 22, sortiranje
od 29, in nato 34.

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

791
00:33:32,160 --> 00:33:33,325
Ali smo izgubili nekoga?

792
00:33:33,325 --> 00:33:33,950
Imam 34.

793
00:33:33,950 --> 00:33:36,730
Kje did-- OK, kdo želi biti 34?

794
00:33:36,730 --> 00:33:37,605
OK, pridi gor, 34.

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

796
00:33:39,280 --> 00:33:41,220
V redu, to bo
vredno vrhunec.

797
00:33:41,220 --> 00:33:41,550
Kako ti je ime?

798
00:33:41,550 --> 00:33:42,040
>> OBČINSTVO: Peter.

799
00:33:42,040 --> 00:33:43,456
>> DAVID J. Malan: Peter, pridi gor.

800
00:33:43,456 --> 00:33:46,810
Vse v redu, tako da tukaj je
Cel kup vozlišč.

801
00:33:46,810 --> 00:33:49,060
Vsak od vas predstavlja
eden od teh pravokotnikov.

802
00:33:49,060 --> 00:33:51,930
In Gabe, nekoliko nenavadno
človek ven, predstavlja prvi.

803
00:33:51,930 --> 00:33:54,850
Torej je njegov kazalec je malo manjši
na zaslonu, kot vsi ostali.

804
00:33:54,850 --> 00:33:58,120
In v tem primeru se vsak od vaš levi
Roke se dogaja, da bodisi točko navzdol,

805
00:33:58,120 --> 00:34:01,085
kar predstavlja null, tako
le odsotnost kazalcem,

806
00:34:01,085 --> 00:34:03,210
ali pa se dogaja, da se kaže
na vozlišču poleg sebe.

807
00:34:03,210 --> 00:34:05,440
>> Torej, zdaj, če ga krasijo
sami, kot na sliki

808
00:34:05,440 --> 00:34:07,585
Tukaj, pojdi naprej in točka
drug na drugega, z Gabe

809
00:34:07,585 --> 00:34:11,030
zlasti kaže na
številka 9, ki zastopa seznam.

810
00:34:11,030 --> 00:34:14,050
OK, in številko 34, levo roko
Morala bi biti obrnjena v tla.

811
00:34:14,050 --> 00:34:15,750
>> OK, tako da je to povezano seznam.

812
00:34:15,750 --> 00:34:17,580
Torej je ta scenarij v vprašanju.

813
00:34:17,580 --> 00:34:20,210
In res, to je reprezentativna
za razred problemov

814
00:34:20,210 --> 00:34:21,929
da lahko poskusite rešiti s kodo.

815
00:34:21,929 --> 00:34:25,020
Hočeš, da na koncu vstaviti
nov element v seznamu.

816
00:34:25,020 --> 00:34:27,494
V tem primeru bomo
poskusite vstaviti številko 55.

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

818
00:34:28,500 --> 00:34:30,860
Vendar pa se dogaja, da se
različni primeri, da razmisli.

819
00:34:30,860 --> 00:34:34,409
In res, to se dogaja, da je eden
od big-picture takeaways tukaj, je,

820
00:34:34,409 --> 00:34:35,659
kaj so različni primeri.

821
00:34:35,659 --> 00:34:39,120
Kakšne so drugačni, če pogoji, ali
veje, ki lahko imajo vaš program?

822
00:34:39,120 --> 00:34:42,024
>> No, število, ki ga poskušate
Vložek, ki je zdaj vemo, da je 55,

823
00:34:42,024 --> 00:34:44,650
ampak, če niste vedeli,
vnaprej, upam si reči,

824
00:34:44,650 --> 00:34:47,840
spada v vsaj treh
možne situacije.

825
00:34:47,840 --> 00:34:49,717
Kjer bi lahko nov element je?

826
00:34:49,717 --> 00:34:51,050
OBČINSTVO: In konec ali srednje.

827
00:34:51,050 --> 00:34:54,150
DAVID J. Malan: Na koncu, v
srednji ali na začetku.

828
00:34:54,150 --> 00:34:56,650
Torej trdim, da je vsaj
tri probleme moramo rešiti.

829
00:34:56,650 --> 00:34:58,691
Dajmo izbrati, kaj je mogoče
verjetno najpreprostejši

830
00:34:58,691 --> 00:35:01,090
ena, kjer je novi element
spada na začetku.

831
00:35:01,090 --> 00:35:04,040
Torej bom imel kodo precej
kot je iskanje, ki sem napisal.

832
00:35:04,040 --> 00:35:07,670
In jaz bom imel ptr, ki
Jaz bom tu predstavljajo s prstom,

833
00:35:07,670 --> 00:35:08,370
kot ponavadi.

834
00:35:08,370 --> 00:35:12,430
>> In zapomni si, kakšno vrednost
smo inicializacijo ptr za?

835
00:35:12,430 --> 00:35:15,300
Zato smo ga inicializiran na začetku null.

836
00:35:15,300 --> 00:35:16,410

837
00:35:16,410 --> 00:35:19,770
Ampak potem, kaj smo storili, ko smo
so znotraj naše iskalno funkcijo?

838
00:35:19,770 --> 00:35:20,940

839
00:35:20,940 --> 00:35:24,870
Mi je pa enaka prvi,
ki ne pomeni to.

840
00:35:24,870 --> 00:35:25,890

841
00:35:25,890 --> 00:35:30,570
Če sem iz PTR, ki je enaka prvi, kaj
naj bi moja roka res gledala?

842
00:35:30,570 --> 00:35:31,070
Prav.

843
00:35:31,070 --> 00:35:33,290
Torej, če Gabe greva
biti enake vrednosti tukaj

844
00:35:33,290 --> 00:35:34,760
moramo tako točko na številko 9.

845
00:35:34,760 --> 00:35:36,420
>> Tako da je bil to začetek naše zgodbe.

846
00:35:36,420 --> 00:35:38,700
In zdaj je to le preprosta,
čeprav sintaksa je nova.

847
00:35:38,700 --> 00:35:40,580
Konceptualno je to samo linearno iskanje.

848
00:35:40,580 --> 00:35:42,750
Je enak 55 do 9?

849
00:35:42,750 --> 00:35:45,559
Ali pa, recimo, manj kot 9.

850
00:35:45,559 --> 00:35:47,600
Ker skušam
ugotoviti, kje postaviti 55.

851
00:35:47,600 --> 00:35:51,270
Manj kot 9, manj kot 17 in manj
kot 20, manjša od 22, manjša od 29,

852
00:35:51,270 --> 00:35:52,510
manj kot 34, št.

853
00:35:52,510 --> 00:35:55,080
Torej, zdaj smo v primeru
eden od najmanj treh.

854
00:35:55,080 --> 00:35:59,910
>> Če želim vstaviti 55 nad tu, kaj
vrstic kode potrebi se bodo izvajali?

855
00:35:59,910 --> 00:36:01,890
Kako to sliko
ljudje morali spremeniti?

856
00:36:01,890 --> 00:36:03,181
Kaj naj naredim z mojo levo roko?

857
00:36:03,181 --> 00:36:04,530

858
00:36:04,530 --> 00:36:07,360
To bi moralo biti null začetku,
zato, ker sem na koncu seznama.

859
00:36:07,360 --> 00:36:09,318
In kaj naj bi se zgodilo
tukaj s Petrom, je bilo to?

860
00:36:09,318 --> 00:36:10,520

861
00:36:10,520 --> 00:36:12,430
Očitno mu je šlo, da kaže na mene.

862
00:36:12,430 --> 00:36:15,580
Torej trdim, da je vsaj dve vrstici
kode v kodo vzorca in danes

863
00:36:15,580 --> 00:36:18,570
da bo za izvajanje tega
Scenarij dodal 55 na repu.

864
00:36:18,570 --> 00:36:20,950
In lahko dobim nekoga hop
in samo predstavljajo 55?

865
00:36:20,950 --> 00:36:22,200
V redu, vi ste nov 55.

866
00:36:22,200 --> 00:36:23,580

867
00:36:23,580 --> 00:36:27,054
>> In kaj zdaj, če je naslednji
Scenarij prihaja skupaj,

868
00:36:27,054 --> 00:36:29,720
in želimo, da vstavite na
začnejo ali vodja tega seznama?

869
00:36:29,720 --> 00:36:31,100
In kako ti je ime, številka 55?

870
00:36:31,100 --> 00:36:31,420
>> OBČINSTVO: Jack.

871
00:36:31,420 --> 00:36:32,295
>> DAVID J. Malan: Jack?

872
00:36:32,295 --> 00:36:33,585
OK, lepo, da sva se spoznala.

873
00:36:33,585 --> 00:36:34,210
Dobrodošli na krovu.

874
00:36:34,210 --> 00:36:36,640
Torej, zdaj bomo
vstavite, recimo, število 5.

875
00:36:36,640 --> 00:36:39,840
Tukaj je drugi primer
trije smo prišli do prej.

876
00:36:39,840 --> 00:36:43,050
Torej, če 5 spada na začetku,
Poglejmo, kako se to ugotovi.

877
00:36:43,050 --> 00:36:46,310
I inicializacijo moje ptr
kazalec na številko 9 znova.

878
00:36:46,310 --> 00:36:49,140
In sem spoznal, oh, 5 je manj kot 9.

879
00:36:49,140 --> 00:36:50,880
Torej popraviti to sliko za nas.

880
00:36:50,880 --> 00:36:54,820
Katerih roke, Gabe ali David je
ali-- kaj je številka 9 je ime?

881
00:36:54,820 --> 00:36:55,740
>> OBČINSTVO: Jen.

882
00:36:55,740 --> 00:36:58,406
>> DAVID J. Malan: Jen hands--
kateri od naših rokah morali spremeniti?

883
00:36:58,406 --> 00:36:58,905

884
00:36:58,905 --> 00:37:00,970
OK, tako da Gabe opozarja na kaj pa zdaj?

885
00:37:00,970 --> 00:37:01,640
Vame.

886
00:37:01,640 --> 00:37:02,750
Sem nova vozlišča.

887
00:37:02,750 --> 00:37:04,870
Torej bom nekako premakniti
tukaj videti vizualno.

888
00:37:04,870 --> 00:37:06,435
In medtem kaj moram poudariti, da je?

889
00:37:06,435 --> 00:37:07,910

890
00:37:07,910 --> 00:37:09,020
Še vedno, ko sem obrnjena.

891
00:37:09,020 --> 00:37:10,000
Torej, to je to.

892
00:37:10,000 --> 00:37:13,717
Torej, samo res ena vrstica kode popravkov
to posebno vprašanje, se zdi.

893
00:37:13,717 --> 00:37:14,800
V redu, to je dobro.

894
00:37:14,800 --> 00:37:17,580
In lahko nekdo ograda za 5?

895
00:37:17,580 --> 00:37:18,080
Pridi gor.

896
00:37:18,080 --> 00:37:20,270

897
00:37:20,270 --> 00:37:21,320
Vam bom naslednjič.

898
00:37:21,320 --> 00:37:24,280
>> V redu, tako sedaj-- in
Naj omenim, da imeni

899
00:37:24,280 --> 00:37:28,510
Jaz ne bi izrecno omenja pravice
Zdaj, PRED kazalec, predhodnik pointer

900
00:37:28,510 --> 00:37:31,260
in nov kazalec, da je
saj le imena

901
00:37:31,260 --> 00:37:35,280
v kodeksu vzorca na kazalcev ali
moje roke, ki je nekako obrnjena naokoli.

902
00:37:35,280 --> 00:37:36,060
Kako ti je ime?

903
00:37:36,060 --> 00:37:36,700
>> OBČINSTVO: Christine.

904
00:37:36,700 --> 00:37:37,100
>> DAVID J. Malan: Christine.

905
00:37:37,100 --> 00:37:38,090
Dobrodošli na krovu.

906
00:37:38,090 --> 00:37:42,180
V redu, kaj menijo, da je sedaj
nekoliko bolj siten scenarij,

907
00:37:42,180 --> 00:37:46,350
pri čemer želim vstaviti
nekaj podobnega kot 26. v to.

908
00:37:46,350 --> 00:37:47,090
20?

909
00:37:47,090 --> 00:37:47,590
Kaj?

910
00:37:47,590 --> 00:37:50,510
To si-- dobra stvar imamo to pisalo.

911
00:37:50,510 --> 00:37:51,955
V redu, 20.

912
00:37:51,955 --> 00:37:53,640

913
00:37:53,640 --> 00:37:57,570
Če bi nekdo dobil en kos
papir pripravljen, samo v case-- vse v redu.

914
00:37:57,570 --> 00:37:58,370
Oh, zanimivo.

915
00:37:58,370 --> 00:37:59,760

916
00:37:59,760 --> 00:38:02,390
No to je primer
predavanja hrošča.

917
00:38:02,390 --> 00:38:03,894
OK kaj je že ime?

918
00:38:03,894 --> 00:38:04,560
OBČINSTVO: Julia.

919
00:38:04,560 --> 00:38:07,559
DAVID J. Malan: Julia, se lahko pop
ven in se pretvarjati, da si nikoli ni tam?

920
00:38:07,559 --> 00:38:09,040
OK, to se ni nikoli zgodilo.

921
00:38:09,040 --> 00:38:09,680
Hvala.

922
00:38:09,680 --> 00:38:12,180
Torej domnevam, želimo vstaviti
Julia v tem povezanega seznama.

923
00:38:12,180 --> 00:38:13,780
Ona je številka 20.

924
00:38:13,780 --> 00:38:15,530
In seveda, da je
dogaja, da sodijo v

925
00:38:15,530 --> 00:38:17,521
begin-- ne kažejo na kaj še.

926
00:38:17,521 --> 00:38:20,020
Torej tvoja roka lahko nekako biti
navzdol null ali nekaj smeti vrednost.

927
00:38:20,020 --> 00:38:21,210
Povejmo hitro zgodbo.

928
00:38:21,210 --> 00:38:22,980
Jaz sem gledala številko 5 tokrat.

929
00:38:22,980 --> 00:38:23,880
Potem sem preveriti, 9.

930
00:38:23,880 --> 00:38:25,130
Potem sem preveriti 17.

931
00:38:25,130 --> 00:38:26,247
Potem sem preveriti 22.

932
00:38:26,247 --> 00:38:27,650

933
00:38:27,650 --> 00:38:32,485
In se zavedam, ooh, Julia
mora iti pred 22.

934
00:38:32,485 --> 00:38:33,580

935
00:38:33,580 --> 00:38:34,660
Torej, kaj se mora zgoditi?

936
00:38:34,660 --> 00:38:35,786

937
00:38:35,786 --> 00:38:36,910
Čigar roke je treba spremeniti?

938
00:38:36,910 --> 00:38:38,360
Julia, rudnik, ali--
kaj je že ime?

939
00:38:38,360 --> 00:38:39,230
>> OBČINSTVO: Christian.

940
00:38:39,230 --> 00:38:40,060
>> DAVID J. Malan: Christian ali?

941
00:38:40,060 --> 00:38:40,560
>> OBČINSTVO: Andy.

942
00:38:40,560 --> 00:38:40,905
>> DAVID J. Malan: Andy.

943
00:38:40,905 --> 00:38:41,654
Christian ali Andy?

944
00:38:41,654 --> 00:38:44,280

945
00:38:44,280 --> 00:38:45,690
Andy je treba opozoriti na?

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
V redu.

949
00:38:47,840 --> 00:38:48,960
Torej, Andy, hočeš opozoriti na Julia?

950
00:38:48,960 --> 00:38:50,120
Toda počakaj malo.

951
00:38:50,120 --> 00:38:53,260
V doslej zgodbe
Jaz sem nekako ene

952
00:38:53,260 --> 00:38:56,800
zadolžen, v tem smislu, da
kazalec je stvar, ki je

953
00:38:56,800 --> 00:38:57,850
premikanje po seznamu.

954
00:38:57,850 --> 00:39:00,800
Morda bomo imeli ime Andy, vendar
ni spremenljivka se imenuje Andy.

955
00:39:00,800 --> 00:39:04,320
Edina druga spremenljivka imamo, je
Prvi, ki je zastopal Gabe.

956
00:39:04,320 --> 00:39:07,690
>> Torej, to je pravzaprav, zakaj tako
daleč smo ni to potrebno.

957
00:39:07,690 --> 00:39:10,846
Toda zdaj na zaslonu je
omeniš of PRED kazalca.

958
00:39:10,846 --> 00:39:11,970
Torej, kaj mi je bolj jasno.

959
00:39:11,970 --> 00:39:14,820
Če je to kazalec, da je bolje,
malo bolj inteligenten

960
00:39:14,820 --> 00:39:15,950
o mojem ponovitev.

961
00:39:15,950 --> 00:39:19,580
Če vas ne moti, moj gre tu skozi
spet kaže tu, kaže tukaj.

962
00:39:19,580 --> 00:39:22,500
Ampak naj imajo PRED kazalec,
Predhodnik kazalec, da je

963
00:39:22,500 --> 00:39:24,740
nekako kaže na
element Ravnokar sem bil.

964
00:39:24,740 --> 00:39:27,330
Torej, ko sem šel tu, zdaj
Moja leva posodobitve ročno.

965
00:39:27,330 --> 00:39:29,370
Ko sem šel tu moja leva posodobitve roko.

966
00:39:29,370 --> 00:39:33,090
In zdaj imam ne samo kazalec
element, ki gre po Juliji,

967
00:39:33,090 --> 00:39:36,300
Še vedno imam kazalec
Andy, element prej.

968
00:39:36,300 --> 00:39:39,430
Tako imate dostop, v bistvu,
drobtine, če hočete,

969
00:39:39,430 --> 00:39:41,500
do vseh potrebnih kazalcev.

970
00:39:41,500 --> 00:39:43,710
>> Torej, če sem gledala
Andy in jaz sem tudi obrnjena

971
00:39:43,710 --> 00:39:47,105
na krščanske, katere roke
Sedaj je treba poudariti drugje?

972
00:39:47,105 --> 00:39:48,770

973
00:39:48,770 --> 00:39:51,960
Torej, Andy lahko sedaj opozarjajo na Julijo.

974
00:39:51,960 --> 00:39:54,460
Julia zdaj lahko kazali na krščansko.

975
00:39:54,460 --> 00:39:56,950
Ker je mogoče kopirati moj
Desna roka je kazalec.

976
00:39:56,950 --> 00:40:00,044
In da je dejansko vas postavi
nazaj v ta kraj tu.

977
00:40:00,044 --> 00:40:02,460
Torej, na kratko, čeprav je to
se nam pri tem nekako večno

978
00:40:02,460 --> 00:40:04,510
dejansko posodobiti
povezani seznam, zavedati

979
00:40:04,510 --> 00:40:06,580
da poslovanje
relativno enostavno.

980
00:40:06,580 --> 00:40:10,030
To je eden, dva, tri
vrstic kode na koncu.

981
00:40:10,030 --> 00:40:12,780
Ampak ovije okrog tistih,
vrstic kode predvidoma

982
00:40:12,780 --> 00:40:16,350
je malo logike, ki učinkovito
zastavlja vprašanje, kje smo?

983
00:40:16,350 --> 00:40:18,970
Smo na začetku,
srednji ali konec?

984
00:40:18,970 --> 00:40:21,890
>> Zdaj, gotovo obstajajo nekatere druge
Operacije mi lahko izvajajo.

985
00:40:21,890 --> 00:40:24,880
In te slike tukaj samo opisujejo
kaj sva naredila z ljudmi.

986
00:40:24,880 --> 00:40:26,080
Kaj pa odstranitev?

987
00:40:26,080 --> 00:40:30,650
Če želim, da, na primer,
odstraniti številko 34 ali 55,

988
00:40:30,650 --> 00:40:34,680
Jaz bi imela enake kode,
ampak bom potreboval enega ali dva koraka.

989
00:40:34,680 --> 00:40:36,110
Ker, kaj je novega?

990
00:40:36,110 --> 00:40:40,460
Če sem odstraniti nekoga na koncu,
kot številko 55 in nato 34,

991
00:40:40,460 --> 00:40:42,995
kaj spremeniti tudi, kot sem to storil?

992
00:40:42,995 --> 00:40:44,870
Moram ne evict--
kaj je že ime?

993
00:40:44,870 --> 00:40:45,380
>> OBČINSTVO: Jack.

994
00:40:45,380 --> 00:40:46,255
>> DAVID J. Malan: Jack.

995
00:40:46,255 --> 00:40:49,770
Moram le evict-- brezplačno Jack,
tako dobesedno pokličite brezplačno Jack, ali vsaj

996
00:40:49,770 --> 00:40:53,530
kazalec tam, ampak zdaj
kaj je treba spremeniti s Petrom?

997
00:40:53,530 --> 00:40:55,510
Njegova roka je bolje začeti navzdol.

998
00:40:55,510 --> 00:40:59,300
Zato, ker takoj, ko sem poklical brezplačno
Jack, če Peter je še vedno gledala Jack

999
00:40:59,300 --> 00:41:02,530
in zato vodi prečkajo
seznam in dostop kazalec this,

1000
00:41:02,530 --> 00:41:05,650
da je, ko naš stari prijatelj segmentacija
Napaka bi lahko dejansko brcnil.

1001
00:41:05,650 --> 00:41:07,860
Ker smo zaradi
spomin nazaj k Jacku.

1002
00:41:07,860 --> 00:41:10,760
>> Lahko ostaneš tam
nerodno le za trenutek.

1003
00:41:10,760 --> 00:41:13,410
Ker imamo le nekaj
končni postopki, da razmisli.

1004
00:41:13,410 --> 00:41:15,600
Odstranjevanje glav seznama,
ali beginning-- in ta je

1005
00:41:15,600 --> 00:41:16,349
malo siten.

1006
00:41:16,349 --> 00:41:19,640
Ker moramo vedeti, da Gabe
je nekako poseben v tem programu.

1007
00:41:19,640 --> 00:41:21,440
Saj res, on ima svoj kazalec.

1008
00:41:21,440 --> 00:41:24,860
On ni samo pa opozoril na,
kot je že skoraj vsi ostali tukaj.

1009
00:41:24,860 --> 00:41:28,112
>> Torej, ko je glava seznama
odstraniti, katerih roke je treba zdaj spremeniti?

1010
00:41:28,112 --> 00:41:29,070
Kaj je že ime?

1011
00:41:29,070 --> 00:41:29,450
>> OBČINSTVO: Christine.

1012
00:41:29,450 --> 00:41:31,408
>> DAVID J. Malan: Jaz sem grozna
na imena, očitno.

1013
00:41:31,408 --> 00:41:34,011
Torej, Christine in Gabe,
čigar roke je treba spremeniti

1014
00:41:34,011 --> 00:41:36,510
ko smo poskušali odstraniti Christine,
številka 5, iz slike?

1015
00:41:36,510 --> 00:41:37,550

1016
00:41:37,550 --> 00:41:38,820
OK, tako da naredimo Gabe.

1017
00:41:38,820 --> 00:41:40,950
Gabe se dogaja s točko,
domnevno, na številki 9.

1018
00:41:40,950 --> 00:41:42,230

1019
00:41:42,230 --> 00:41:44,642
Toda kaj naj bi se zgodilo naslednjič?

1020
00:41:44,642 --> 00:41:46,600
OBČINSTVO: Christine smeli
je ničen [neslišno].

1021
00:41:46,600 --> 00:41:50,244
DAVID J. Malan: OK, če bi mi verjetno
make-- sem slišal "null" nekje.

1022
00:41:50,244 --> 00:41:51,410
OBČINSTVO: Null in brez nje.

1023
00:41:51,410 --> 00:41:51,855
DAVID J. Malan: NULL kaj?

1024
00:41:51,855 --> 00:41:53,074
OBČINSTVO: Null in brez nje.

1025
00:41:53,074 --> 00:41:54,490
DAVID J. Malan: Null in brez nje.

1026
00:41:54,490 --> 00:41:55,422
Torej, to je zelo enostavno.

1027
00:41:55,422 --> 00:41:58,380
In je kot nalašč, da si zdaj nekako
ki stoji tam, ne pripada.

1028
00:41:58,380 --> 00:42:00,430
Zato, ker ste bili
ločena od seznama.

1029
00:42:00,430 --> 00:42:02,820
Učinkovito ste bili
sirota iz seznama.

1030
00:42:02,820 --> 00:42:07,770
In tako smo poklicali brezplačno zdaj
Christine, da bi ta spomin nazaj.

1031
00:42:07,770 --> 00:42:10,240
V nasprotnem primeru vsakič, ko
odstrani vozlišče iz seznama

1032
00:42:10,240 --> 00:42:14,230
bomo lahko izdelavo seznama
krajši, vendar dejansko ne zmanjšuje

1033
00:42:14,230 --> 00:42:15,096
velikost v pomnilniku.

1034
00:42:15,096 --> 00:42:17,720
In tako, če se držimo dodajanje in
dodajanje, dodajanje stvari na seznamu,

1035
00:42:17,720 --> 00:42:19,280
moj računalnik morda dobili počasnejši
in počasneje in počasneje,

1036
00:42:19,280 --> 00:42:21,740
ker sem zmanjkuje
spomin, čeprav v resnici nisem

1037
00:42:21,740 --> 00:42:25,580
uporabo Christine je bajta
spomina več.

1038
00:42:25,580 --> 00:42:28,500
>> Torej, na koncu pa se drugi
scenariji, iz course-- odstranitev

1039
00:42:28,500 --> 00:42:30,640
v sredini, odstranjevanje
na koncu, kot smo videli.

1040
00:42:30,640 --> 00:42:32,348
Ampak bolj zanimivo
Zdaj je izziv

1041
00:42:32,348 --> 00:42:34,770
bo natančno preuči
kaj čas teče, je.

1042
00:42:34,770 --> 00:42:36,640
Torej ne samo, da lahko obdržite vaše
Lističe, če Gabe,

1043
00:42:36,640 --> 00:42:38,640
vas ne bi motilo, dajanje
vsi stres žogo.

1044
00:42:38,640 --> 00:42:42,100
Najlepša hvala za naše povezani seznam
prostovoljcev tukaj, če bi lahko.

1045
00:42:42,100 --> 00:42:45,320
>> [APLAVZ]

1046
00:42:45,320 --> 00:42:46,700
>> DAVID J. Malan: Dobro.

1047
00:42:46,700 --> 00:42:51,110
Torej nekaj analitično
vprašanja, nato pa, če sem lahko.

1048
00:42:51,110 --> 00:42:59,670
Videli smo ta zapis pred,
big O in omega, zgornje meje

1049
00:42:59,670 --> 00:43:02,520
in spodnja meja za
čas nekaj algoritem teče.

1050
00:43:02,520 --> 00:43:04,950
Torej, kaj menijo, da samo
nekaj vprašanj.

1051
00:43:04,950 --> 00:43:07,090
>> One, in mi je rekel,
pred tem, kaj je tek

1052
00:43:07,090 --> 00:43:10,647
čas iskanja
Seznam v smislu velikega O?

1053
00:43:10,647 --> 00:43:13,480
Kaj je zgornja meja za vožnjo
Čas iskanjem povezani seznam

1054
00:43:13,480 --> 00:43:16,340
kot naši prostovoljci izvajajo tu?

1055
00:43:16,340 --> 00:43:17,820
To je velik O n, linearna.

1056
00:43:17,820 --> 00:43:20,630
Ker v najslabšem primeru,
elementa, kot so 55,

1057
00:43:20,630 --> 00:43:23,830
bomo lahko iskali morda kje
Jack je bilo vse tako na koncu.

1058
00:43:23,830 --> 00:43:28,250
In na žalost, za razliko od matrike
ne moremo dobiti fancy tokrat.

1059
00:43:28,250 --> 00:43:31,820
Čeprav so bile vse naše ljudi
razporejene od majhnih elementov, 5,

1060
00:43:31,820 --> 00:43:35,900
vse tja do večjega elementa
55, to je navadno dobra stvar.

1061
00:43:35,900 --> 00:43:38,815
Ampak kaj to domnevo
ne nam omogočajo, da naredim?

1062
00:43:38,815 --> 00:43:39,775

1063
00:43:39,775 --> 00:43:40,650
OBČINSTVO: [neslišno]

1064
00:43:40,650 --> 00:43:40,920
DAVID J. Malan: Ponovi?

1065
00:43:40,920 --> 00:43:41,800
OBČINSTVO: Random dostop.

1066
00:43:41,800 --> 00:43:43,049
DAVID J. Malan: Random dostop.

1067
00:43:43,049 --> 00:43:46,330
In posledično to pomeni, da ne moremo
več uporabljati šibek ničel intuicijo,

1068
00:43:46,330 --> 00:43:49,365
in očitnost dvojiškem
iskanje in razdeli in vladaj.

1069
00:43:49,365 --> 00:43:51,240
Ker čeprav smo
Ljudje bi očitno

1070
00:43:51,240 --> 00:43:54,610
vidim, da so Andy ali Christian
približno na sredini seznama,

1071
00:43:54,610 --> 00:43:57,670
vemo le, da je, kot je
Računalnik s posnemanjem s seznama

1072
00:43:57,670 --> 00:43:59,029
od samega začetka.

1073
00:43:59,029 --> 00:44:00,570
Tako da smo obupali, da naključni dostop.

1074
00:44:00,570 --> 00:44:04,380
>> Tako velik O n zdaj je zgornja
vezan na naše iskalno času.

1075
00:44:04,380 --> 00:44:07,920
Kaj pa omega naše iskanje?

1076
00:44:07,920 --> 00:44:11,535
Kaj je spodnja meja za iskanje
za nekaj več na tem seznamu?

1077
00:44:11,535 --> 00:44:12,410
OBČINSTVO: [neslišno]

1078
00:44:12,410 --> 00:44:13,040
DAVID J. Malan: Ponovi?

1079
00:44:13,040 --> 00:44:13,420
OBČINSTVO: One.

1080
00:44:13,420 --> 00:44:13,800
DAVID J. Malan: One.

1081
00:44:13,800 --> 00:44:14,760
Tako konstanten čas.

1082
00:44:14,760 --> 00:44:17,020
V najboljšem primeru, Christine je
dejansko na začetku seznama.

1083
00:44:17,020 --> 00:44:19,020
In iščemo
številka 5, tako da smo jo našli.

1084
00:44:19,020 --> 00:44:19,787
Torej ni nič takega.

1085
00:44:19,787 --> 00:44:22,370
Ampak ona ima, da je na
začetek seznama v tem primeru.

1086
00:44:22,370 --> 00:44:23,745
Kaj pa nekaj takega kot Delete?

1087
00:44:23,745 --> 00:44:24,717

1088
00:44:24,717 --> 00:44:26,300
Kaj pa, če želite izbrisati element?

1089
00:44:26,300 --> 00:44:29,200
Kaj je zgornja meja in spodnja meja
o izbrisu nekaj iz povezane

1090
00:44:29,200 --> 00:44:29,699
seznam?

1091
00:44:29,699 --> 00:44:35,195

1092
00:44:35,195 --> 00:44:36,070
OBČINSTVO: [neslišno]

1093
00:44:36,070 --> 00:44:36,420
DAVID J. Malan: Ponovi?

1094
00:44:36,420 --> 00:44:37,067
OBČINSTVO: n.

1095
00:44:37,067 --> 00:44:38,900
DAVID J. Malan: n
res zgornja meja.

1096
00:44:38,900 --> 00:44:41,700
Ker v najslabšem primeru bomo poskušali
izbrisati Jack, kot smo pravkar storil.

1097
00:44:41,700 --> 00:44:43,050
On je vse tako na koncu.

1098
00:44:43,050 --> 00:44:45,419
Nas traja večno, ali
n korakov, da bi ga našli.

1099
00:44:45,419 --> 00:44:46,460
Tako, da je zgornja meja.

1100
00:44:46,460 --> 00:44:47,430
To je linearna, seveda.

1101
00:44:47,430 --> 00:44:50,970
In najboljši primer čas teče, ali
spodnje meje v najboljšem primeru

1102
00:44:50,970 --> 00:44:51,975
bi bil konstanten čas.

1103
00:44:51,975 --> 00:44:54,600
Mogoče zato, ker smo poskušali izbrisati
Christine, in smo samo srečo

1104
00:44:54,600 --> 00:44:55,558
ona je na začetku.

1105
00:44:55,558 --> 00:44:56,350
Počakajte malo.

1106
00:44:56,350 --> 00:44:59,370
Gabe je tudi na začetku,
in smo tudi imeli za posodobitev Gabe.

1107
00:44:59,370 --> 00:45:01,150
Tako, da ni bil le en korak.

1108
00:45:01,150 --> 00:45:04,210
Torej je res konstantna
čas, v najboljšem primeru,

1109
00:45:04,210 --> 00:45:06,345
odstraniti najmanjši element?

1110
00:45:06,345 --> 00:45:07,360

1111
00:45:07,360 --> 00:45:10,960
To je, čeprav bi bilo morda dva,
tri ali celo 100 vrstic kode,

1112
00:45:10,960 --> 00:45:14,000
Če je enako število
linije, ne v neki zanki,

1113
00:45:14,000 --> 00:45:16,577
in neodvisna od velikosti
seznama, absolutno.

1114
00:45:16,577 --> 00:45:18,660
Brisanje elementa na
začetek seznama

1115
00:45:18,660 --> 00:45:21,940
tudi če imamo opraviti z
Gabe, je še vedno čas konstantna.

1116
00:45:21,940 --> 00:45:24,220
>> Torej, to se zdi, kot
ogromen korak nazaj.

1117
00:45:24,220 --> 00:45:27,000
In kaj zapravljanje časa
če je, v enem tednu in teden

1118
00:45:27,000 --> 00:45:30,250
zero smo imeli ne samo
psevdokoda code ampak dejanska koda

1119
00:45:30,250 --> 00:45:35,780
izvesti nekaj, kar je dnevnik
baza n, ali se prijavite, ne, n, baza 2,

1120
00:45:35,780 --> 00:45:37,150
v smislu svojega časa teče.

1121
00:45:37,150 --> 00:45:40,710
Torej, zakaj bi vraga želimo začeti
uporabo nekaj podobnega povezanega seznama?

1122
00:45:40,710 --> 00:45:41,517
Ja.

1123
00:45:41,517 --> 00:45:44,022
>> OBČINSTVO: Torej, lahko dodate
elementi v matriki.

1124
00:45:44,022 --> 00:45:46,230
DAVID J. Malan: Torej lahko
dodate elemente matrike.

1125
00:45:46,230 --> 00:45:47,550
In tudi to je tematsko.

1126
00:45:47,550 --> 00:45:49,740
In bomo še videli
to je to trade-off, kar je precej

1127
00:45:49,740 --> 00:45:51,573
kot smo videli
trade-off z zlivanjem.

1128
00:45:51,573 --> 00:45:54,606
Mi bi res lahko pospeši
iskanje in sortiranje, ne,

1129
00:45:54,606 --> 00:45:57,480
če bomo porabili malo več prostora in
imajo dodatno kos pomnilnika

1130
00:45:57,480 --> 00:45:58,760
ali niz za urejanje z zlivanjem.

1131
00:45:58,760 --> 00:46:01,270
Vendar smo porabili več
prostor, vendar smo prihranili čas.

1132
00:46:01,270 --> 00:46:04,820
V tem primeru smo
obupal čas, vendar smo

1133
00:46:04,820 --> 00:46:08,170
pridobivanje fleksibilnost,
dinamičnost, če hočete,

1134
00:46:08,170 --> 00:46:10,280
ki je nedvomno pozitivna lastnost.

1135
00:46:10,280 --> 00:46:11,520
>> Mi smo tudi porabo prostora.

1136
00:46:11,520 --> 00:46:13,710
V kakšnem smislu je povezano
seznam dražji

1137
00:46:13,710 --> 00:46:15,700
v prostorskem smislu, kot array?

1138
00:46:15,700 --> 00:46:18,379

1139
00:46:18,379 --> 00:46:19,920
Kjer je dodaten prostor, ki prihaja iz?

1140
00:46:19,920 --> 00:46:20,460
Ja?

1141
00:46:20,460 --> 00:46:21,800
>> OBČINSTVO: [neslišno] kazalec.

1142
00:46:21,800 --> 00:46:23,310
>> DAVID J. Malan: Ja,
tudi kazalec.

1143
00:46:23,310 --> 00:46:25,560
Torej je to minorly nadležno
s tem, da ni več am

1144
00:46:25,560 --> 00:46:27,780
I shranjevanje le int
za zastopanje int.

1145
00:46:27,780 --> 00:46:30,990
Jaz shranjevanje int in A
kazalec, ki je prav tako 32 bitov.

1146
00:46:30,990 --> 00:46:33,470
Tako da sem dobesedno podvojili
Količina prostora je izbral.

1147
00:46:33,470 --> 00:46:36,040
Torej, to je trade-off, vendar
da je v primeru notr.

1148
00:46:36,040 --> 00:46:39,580
Predvidevam, da niste shranjevanje int,
ampak domnevam, vsaka od teh pravokotnikov

1149
00:46:39,580 --> 00:46:43,290
ali vsak od teh ljudi je predstavlja
beseda, angleška beseda, ki

1150
00:46:43,290 --> 00:46:46,430
morda pet znakov, 10
znakov, morda celo več.

1151
00:46:46,430 --> 00:46:49,940
Nato dodal le 32 več bitov
morda manj velik posel.

1152
00:46:49,940 --> 00:46:52,160
>> Kaj pa, če je vsak od učencev
pri predstavitvi

1153
00:46:52,160 --> 00:46:55,107
dobesedno študentske konstruktov, ki
imajo imena in hiše in morda

1154
00:46:55,107 --> 00:46:57,065
telefonske številke in Twitter
ročaji in podobno.

1155
00:46:57,065 --> 00:46:59,564
Torej vsa polja smo začeli
Govorimo o drugi dan,

1156
00:46:59,564 --> 00:47:02,410
mnogo manj velik posel kot
naša vozlišča dobili bolj zanimivo

1157
00:47:02,410 --> 00:47:05,972
in velika, da preživijo, eh, dodatna
kazalec samo, da jih povezati.

1158
00:47:05,972 --> 00:47:07,180
Ampak res, to je trade-off.

1159
00:47:07,180 --> 00:47:09,560
In res, koda
bolj zapletena, kot boste

1160
00:47:09,560 --> 00:47:11,770
glej s posnemanjem s
da posamezen primer.

1161
00:47:11,770 --> 00:47:14,302
Toda kaj, če ne bi bilo
nekateri sveti gral tukaj.

1162
00:47:14,302 --> 00:47:17,010
Kaj pa, če ne bomo naredili korak
nazaj, ampak ogromen korak naprej

1163
00:47:17,010 --> 00:47:19,180
in izvajati podatkov
Struktura po katerem

1164
00:47:19,180 --> 00:47:22,870
mogoče najti elemente, kot so Jack ali
Christine ali katere koli druge elemente

1165
00:47:22,870 --> 00:47:25,870
v tem polju v pravem času konstantno?

1166
00:47:25,870 --> 00:47:26,920
Iskanje je konstantna.

1167
00:47:26,920 --> 00:47:28,320
Izbriši konstantna.

1168
00:47:28,320 --> 00:47:29,570
Vstavi se konstantna.

1169
00:47:29,570 --> 00:47:32,260
Vse te operacije so stalnica.

1170
00:47:32,260 --> 00:47:33,750
Da bi naš sveti gral.

1171
00:47:33,750 --> 00:47:36,690
In to je, če smo
bo dvignil naslednjič.

1172
00:47:36,690 --> 00:47:38,600
Se vidiva potem.

1173
00:47:38,600 --> 00:47:39,371