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

2
00:00:00,500 --> 00:00:11,137
[Prehrávanie hudby]

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

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

5
00:00:13,950 --> 00:00:18,560
To je týždeň päť pokračuje, a my
nejaké dobré správy a zlé správy.

6
00:00:18,560 --> 00:00:21,140
Takže dobrá správa je, že CS50
začína tento piatok.

7
00:00:21,140 --> 00:00:24,430
Ak máte záujem sa k nám pripojiť,
zamierte do obvyklej adrese tu.

8
00:00:24,430 --> 00:00:28,670
Ešte lepšia správa, nie prednáška
tento rok v pondelok 13 ..

9
00:00:28,670 --> 00:00:31,970
O niečo menej lepšie správy,
kvíz nula je budúcu stredu.

10
00:00:31,970 --> 00:00:33,840
Viac informácií môže byť
nájdete na tejto adrese tu.

11
00:00:33,840 --> 00:00:36,340
A v najbližších pár dní
budeme vypĺňať prázdne miesta

12
00:00:36,340 --> 00:00:39,234
s ohľadom na izbách
že budeme mať vyhradené.

13
00:00:39,234 --> 00:00:41,400
Lepšie správou je, že tam budem
byť preskúmanie samozrejme celej

14
00:00:41,400 --> 00:00:43,570
Zasadnutí tento rok
V pondelok vo večerných hodinách.

15
00:00:43,570 --> 00:00:46,270
Zostaňte naladení na kurze je
Internetové stránky pre umiestnenie a podrobnosti.

16
00:00:46,270 --> 00:00:49,290
Sekcie, a to aj keď sa jedná o
dovolenka, zobrazia sa aj stretnúť tiež.

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

18
00:00:50,490 --> 00:00:52,940
Najlepšie novinky, prednáška budúci piatok.

19
00:00:52,940 --> 00:00:56,220
Tak to je tradícia nám
majú podľa osnov.

20
00:00:56,220 --> 00:00:58,100
Len--, že to bude úžasné.

21
00:00:58,100 --> 00:01:02,510
Uvidíte veci, ako je
dátové štruktúry konštantné časové

22
00:01:02,510 --> 00:01:04,730
a hashovacie tabuľky a stromy a snaží sa.

23
00:01:04,730 --> 00:01:07,150
A budeme hovoriť o problémoch narodenín.

24
00:01:07,150 --> 00:01:09,440
Celá partia vecí
čaká budúci piatok.

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
Tak či onak.

28
00:01:13,190 --> 00:01:17,080
>> Takže pripomenúť, že sme boli
so zameraním na obrázku o tom, čo je

29
00:01:17,080 --> 00:01:18,980
vnútornej pamäti nášho počítača.

30
00:01:18,980 --> 00:01:22,875
Takže je pamäť RAM, alebo tam, kde programy
existuje, keď ste im beží.

31
00:01:22,875 --> 00:01:25,215
Ak dvakrát kliknete na
ikonu spustiť nejaký program,

32
00:01:25,215 --> 00:01:27,520
alebo dvakrát kliknite na
icon otvoriť niektoré súbory,

33
00:01:27,520 --> 00:01:30,430
je nabitá z vášho pevného
disk alebo jednotku SSD

34
00:01:30,430 --> 00:01:34,190
do pamäte RAM, Random Access Memory, kde
žije, kým sa nevypne napájanie,

35
00:01:34,190 --> 00:01:36,700
veko notebooku sa zavrie,
alebo ukončenia programu.

36
00:01:36,700 --> 00:01:38,960
>> Teraz, pamäť, z
ktoré pravdepodobne máte

37
00:01:38,960 --> 00:01:41,950
1 GB v týchto dňoch, 2
GB, alebo dokonca oveľa viac,

38
00:01:41,950 --> 00:01:44,420
je všeobecne stanovené
pre daný program

39
00:01:44,420 --> 00:01:47,170
v tomto druhu pravouhlého
konceptuálny model

40
00:01:47,170 --> 00:01:50,860
čím máme zásobníka v spodnej časti
a veľa ďalších vecí, na vrchole.

41
00:01:50,860 --> 00:01:53,140
Ide o to, na samom vrchole
sme videli na obrázku

42
00:01:53,140 --> 00:01:55,670
skôr, ale nikdy nehovoril o
je takzvaný texte segmentu.

43
00:01:55,670 --> 00:01:58,419
Text segment je len ozdobný spôsob, ako
hovoriť nuly a tie, ktoré

44
00:01:58,419 --> 00:02:01,150
vytvorte aktuálny skompilovaný program.

45
00:02:01,150 --> 00:02:03,910
>> Takže keď poklepete
Microsoft Word v počítači Mac alebo PC,

46
00:02:03,910 --> 00:02:08,030
alebo pri spustení bodka lomítko Mario na
Linux počítač v okne vášho terminálu,

47
00:02:08,030 --> 00:02:12,460
nuly a tie, ktoré sa skladajú
Word a Mario sú dočasne uložené

48
00:02:12,460 --> 00:02:16,610
v pamäti RAM počítača v takzvanej
Text segmentu pre konkrétny program.

49
00:02:16,610 --> 00:02:19,080
Pod tým ide inicializovaný
a neinicializovaný údaje.

50
00:02:19,080 --> 00:02:22,655
To je vec ako globálne premenné,
že sme nepoužíva veľa,

51
00:02:22,655 --> 00:02:24,910
ale občas máme
mal globálne premenné

52
00:02:24,910 --> 00:02:28,819
alebo staticky definované reťazce, ktoré
je pevný kódované slová ako "ahoj"

53
00:02:28,819 --> 00:02:31,860
ktoré nie sú prijaté od užívateľa
, Ktoré sú pevne do svojho programu.

54
00:02:31,860 --> 00:02:34,230
>> Teraz, sa v spodnej časti sme
majú takzvaný stack.

55
00:02:34,230 --> 00:02:37,665
A stack, doteraz sme boli
použitím, aké druhy účely?

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

57
00:02:39,706 --> 00:02:40,997
Čo zásobník sa používa?

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

59
00:02:41,160 --> 00:02:42,070
>> Divákov: Funkcia.

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

61
00:02:43,320 --> 00:02:44,980
V akom zmysle pre funkcie?

62
00:02:44,980 --> 00:02:48,660
>> Divákov: Pri volaní funkcie,
argumenty sú skopírované do zásobníka.

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

64
00:02:49,660 --> 00:02:52,650
Pri volaní funkcie, jej
argumenty sú skopírované do zásobníka.

65
00:02:52,650 --> 00:02:56,330
Takže nejaké X alebo Y alebo či B je
že ste prechádza do funkcie

66
00:02:56,330 --> 00:02:58,680
sú dočasne kladený na
takzvaný zásobník,

67
00:02:58,680 --> 00:03:02,000
rovnako ako jeden z Annenberg
jedáleň podnosy, a tiež veci,

68
00:03:02,000 --> 00:03:03,190
ako lokálne premenné.

69
00:03:03,190 --> 00:03:06,290
Ak váš foo funkcie alebo odkladacieho
funkcie majú lokálne premenné,

70
00:03:06,290 --> 00:03:08,602
ako je teplota, tí dvaja
skončiť na zásobníku.

71
00:03:08,602 --> 00:03:11,560
Teraz budeme moc nehovorila o
ne, ale tieto premenné prostredia

72
00:03:11,560 --> 00:03:15,690
v dolnej časti sme videli pred chvíľou, keď
Bol som futzing na klávesnici jeden deň

73
00:03:15,690 --> 00:03:20,050
a začal som prístup k veci
ako argv 100 alebo argv 1000,

74
00:03:20,050 --> 00:03:22,320
Len elements-- som zabudol
numbers-- ale, že

75
00:03:22,320 --> 00:03:24,330
nemali byť prístupné mnou.

76
00:03:24,330 --> 00:03:26,581
Začali sme vidieť niektoré
funky symboly na obrazovke.

77
00:03:26,581 --> 00:03:28,330
Boli to takzvané
premenné prostredia

78
00:03:28,330 --> 00:03:32,390
ako globálne nastavenie pre môj
programu alebo pre svoj počítač, nie

79
00:03:32,390 --> 00:03:37,090
nesúvisí s poslednou
chyba, že sme sa bavili,

80
00:03:37,090 --> 00:03:39,670
Shellshock, že to bolo
trápi pomerne málo počítačov.

81
00:03:39,670 --> 00:03:42,960
>> Teraz konečne, v dnešnej zameranie
budeme nakoniec mať na halde.

82
00:03:42,960 --> 00:03:44,864
Jedná sa o ďalší kus pamäti.

83
00:03:44,864 --> 00:03:47,030
A v podstate všetko
pamäť je isté.

84
00:03:47,030 --> 00:03:48,040
Je to rovnaký hardvér.

85
00:03:48,040 --> 00:03:49,956
Sme len trochu
liečenie rôznych klastrov

86
00:03:49,956 --> 00:03:51,460
bajtov pre rôzne účely.

87
00:03:51,460 --> 00:03:56,540
Haldy bude tiež tam, kde
premenné a pamäti, ktoré požadujete

88
00:03:56,540 --> 00:03:58,810
z operačného systému
sú dočasne uložené.

89
00:03:58,810 --> 00:04:01,890
>> Ale je to trochu problém
tu, rovnako ako obraz znamená.

90
00:04:01,890 --> 00:04:05,261
Máme druh má dva
lode sa zraziť.

91
00:04:05,261 --> 00:04:08,010
Pretože ak budete používať viac a viac
zo zásobníka, a ako vidíme dnes

92
00:04:08,010 --> 00:04:11,800
dopredu, ak budete používať viac a viac
haldy, iste zlé veci sa môže stať.

93
00:04:11,800 --> 00:04:15,054
A skutočne, môžeme vyvolať, že
úmyselne alebo neúmyselne.

94
00:04:15,054 --> 00:04:16,970
Takže Cliffhanger posledného
čas bol tento program,

95
00:04:16,970 --> 00:04:20,570
ktoré nemali slúžiť nejaký funkčný
účel iný ako ukázať

96
00:04:20,570 --> 00:04:24,750
ako ste ako zloduch môže skutočne trvať
Výhodou chýb v niečí programe

97
00:04:24,750 --> 00:04:28,460
a prevziať program alebo dokonca
Celý počítačový systém alebo server.

98
00:04:28,460 --> 00:04:31,660
Takže stačí, aby sa pozrel krátko vás
Všimnite si, že najdôležitejšie na dne

99
00:04:31,660 --> 00:04:34,510
sa v príkazovom riadku
argumenty, podľa argv.

100
00:04:34,510 --> 00:04:38,480
A to je volanie funkcie f,
v podstate bezmenná funkcia nazvaná

101
00:04:38,480 --> 00:04:40,250
f, a to odovzdaním argv [1].

102
00:04:40,250 --> 00:04:43,960
>> Takže bez ohľadu na slovo, že užívateľ zadá na
riadku za menom tohto programu,

103
00:04:43,960 --> 00:04:49,310
a potom ľubovoľná funkcia hore
top, f, sa v reťazci, AKA char *,

104
00:04:49,310 --> 00:04:51,720
ako sme začali diskutovať,
a to len nazýva "bar".

105
00:04:51,720 --> 00:04:53,310
Ale my sme to mohli nazvať čokoľvek.

106
00:04:53,310 --> 00:04:57,470
A potom prehlasuje, vnútri
f, pole znakov

107
00:04:57,470 --> 00:04:59,930
volal C-- 12 týchto znakov.

108
00:04:59,930 --> 00:05:03,580
>> Teraz, podľa príbehu, ktorý som hovoril
pred chvíľou, kedy v pamäti

109
00:05:03,580 --> 00:05:06,720
je c, alebo sú tie 12
znakov skončí?

110
00:05:06,720 --> 00:05:07,570
Len aby bolo jasno.

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

112
00:05:08,070 --> 00:05:08,590
>> Divákov: Na zásobníku.

113
00:05:08,590 --> 00:05:09,420
>> David J. Malan: Na zásobníku.

114
00:05:09,420 --> 00:05:10,720
Takže c je lokálna premenná.

115
00:05:10,720 --> 00:05:14,079
Pýtame sa na 12 znakov alebo 12 bajtov.

116
00:05:14,079 --> 00:05:16,120
Tí, ktorí sa skončí
na takzvané zásobníka.

117
00:05:16,120 --> 00:05:18,530
Teraz konečne je to iná funkcia
to je vlastne celkom užitočné,

118
00:05:18,530 --> 00:05:20,571
ale my sme naozaj použiť
to sami, strncopy.

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

120
00:05:21,550 --> 00:05:25,200
To znamená, že reťazec kópiu, ale
iba n listy, n znakov.

121
00:05:25,200 --> 00:05:31,990
Tak n znaky budú
kopírovať z baru do cca.

122
00:05:31,990 --> 00:05:32,980
A koľko?

123
00:05:32,980 --> 00:05:34,110
Dĺžka tyče.

124
00:05:34,110 --> 00:05:36,330
Takže inými slovami, že
jeden riadok, strncopy,

125
00:05:36,330 --> 00:05:39,500
bude kopírovať
účinne bar do cca.

126
00:05:39,500 --> 00:05:42,340
>> Teraz, len trochu predvídať
Ponaučenie z tohto príbehu,

127
00:05:42,340 --> 00:05:44,750
to, čo je tu potenciálne problematické?

128
00:05:44,750 --> 00:05:49,710
Aj keď sme skontrolovať dĺžku
tyče a jej odovzdanie do strncopy,

129
00:05:49,710 --> 00:05:53,145
Aký je váš gut hovoríš, je
stále zlomený o tomto programe?

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

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

132
00:05:55,220 --> 00:05:57,491
>> Divákov: Nezahŕňa
priestor pre nulový znak.

133
00:05:57,491 --> 00:05:59,990
David J. Malan: Nezahŕňa
priestor pre nulový znak.

134
00:05:59,990 --> 00:06:02,073
Potenciálne, na rozdiel od v
bežná minulá prax my ani

135
00:06:02,073 --> 00:06:04,810
mať toľko ako plus 1 na
ubytovať, že znakom null.

136
00:06:04,810 --> 00:06:06,649
Ale je to ešte horšie, než to.

137
00:06:06,649 --> 00:06:07,940
Čo iného sme nedarí robiť?

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

139
00:06:08,432 --> 00:06:09,307
>> Divákov: [nepočuteľné]

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
Sme pevne dané 12 dosť ľubovoľne.

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

144
00:06:19,497 --> 00:06:21,330
To nie je tak moc
problém, ale skutočnosť,

145
00:06:21,330 --> 00:06:25,630
že sme ani kontrolovať, či
Dĺžka tyče je menšia ako 12,

146
00:06:25,630 --> 00:06:28,530
v tom prípade to bude
bezpečné, aby to do pamäti

147
00:06:28,530 --> 00:06:30,260
volal c, že ​​sme pridelené.

148
00:06:30,260 --> 00:06:32,960
V skutočnosti, ak je ako bar
20 znakov,

149
00:06:32,960 --> 00:06:39,010
Zobrazí sa táto funkcia sa kopírovania
20 znakov z baru do C, čím sa

150
00:06:39,010 --> 00:06:41,310
pričom aspoň 8 bajtov
že by nemalo byť.

151
00:06:41,310 --> 00:06:42,690
To je dôsledok tu.

152
00:06:42,690 --> 00:06:44,347
>> Takže v skratke, rozbité programu.

153
00:06:44,347 --> 00:06:45,180
Nie je tak veľký problém.

154
00:06:45,180 --> 00:06:46,360
Možno, že máte chybu segmentácie.

155
00:06:46,360 --> 00:06:47,651
Všetci sme mali chyby v programoch.

156
00:06:47,651 --> 00:06:50,196
My všetci môžu mať chyby
programov práve teraz.

157
00:06:50,196 --> 00:06:51,320
Ale čo je dôsledok?

158
00:06:51,320 --> 00:06:54,390
No, tu je zväčšené verzie
že obraz pamäte môjho počítača.

159
00:06:54,390 --> 00:06:56,230
Jedná sa o spodnú časť môjho stacku.

160
00:06:56,230 --> 00:06:59,644
A skutočne, na samom dne je to, čo je
volal rodič rutina zásobník, ozdobný spôsob, ako

161
00:06:59,644 --> 00:07:00,560
povedať, že je to hlavné.

162
00:07:00,560 --> 00:07:03,772
Tak, že ten, kto nazýva funkcia
f, že hovoríme o.

163
00:07:03,772 --> 00:07:05,230
Tak toto je dno zásobníka.

164
00:07:05,230 --> 00:07:06,640
Spiatočná adresa je niečo nové.

165
00:07:06,640 --> 00:07:08,810
Je to vždy tam,
vždy v tomto obrázku.

166
00:07:08,810 --> 00:07:10,440
Práve sme sa nikdy obrátil pozornosť k tomu.

167
00:07:10,440 --> 00:07:15,290
Vzhľadom k tomu, že ukáže, že spôsob, akým funguje, je c
, Že keď jeden volanie funkcie druhého,

168
00:07:15,290 --> 00:07:18,780
nielen že tvrdenie, podľa ktorej
Funkcie tlačil do fronty,

169
00:07:18,780 --> 00:07:22,470
nielen že funkcia je miestna
premenné tlačil do fronty,

170
00:07:22,470 --> 00:07:26,820
niečo ako spiatočná adresa
získa tiež dať do zásobníka.

171
00:07:26,820 --> 00:07:33,330
Konkrétne, ak hlavný volá foo, hlavné je
vlastnej adresu v pamäti, vôl niečo,

172
00:07:33,330 --> 00:07:38,240
efektívne dostane dať do zásobníka
tak, že ak je f vykonáva spustením

173
00:07:38,240 --> 00:07:43,630
vie, kam skočiť späť do textu
segmentu, aby mohol pokračovať vykonávanie.

174
00:07:43,630 --> 00:07:47,760
>> Takže keď sme tu koncepčne,
V hlavnej, potom f volaná.

175
00:07:47,760 --> 00:07:50,200
Ako sa f vedieť, kto
na ručné ovládanie späť?

176
00:07:50,200 --> 00:07:52,020
No, tento malý
strúhanka v červenej tu,

177
00:07:52,020 --> 00:07:54,978
volal spiatočná adresa, to jednoducho
kontroly, čo je to spiatočná adresa?

178
00:07:54,978 --> 00:07:57,039
Oh, nechaj ma skočiť späť na hlavnú tu.

179
00:07:57,039 --> 00:07:59,080
A to je trochu
ako zjednodušujúce,

180
00:07:59,080 --> 00:08:00,750
pretože núl a jednotiek
Pre Main sú technicky

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

182
00:08:01,967 --> 00:08:03,800
Ale to je nápad. f
jednoducho musí vedieť, čo

183
00:08:03,800 --> 00:08:06,680
tam, kde konanie nakoniec sa vráti.

184
00:08:06,680 --> 00:08:09,790
>> Ale spôsob, akým počítače
už dlho stanovené veci

185
00:08:09,790 --> 00:08:12,320
ako lokálne premenné a
argumenty ako je táto.

186
00:08:12,320 --> 00:08:17,180
Takže v hornej časti obrázku v
modrá je stack frame pre f, takže všetko

187
00:08:17,180 --> 00:08:19,630
na pamäti, že f
konkrétne ich používate.

188
00:08:19,630 --> 00:08:22,990
Tak teda, všimnite si, že
Bar je na tomto obrázku.

189
00:08:22,990 --> 00:08:23,980
Bar bol jeho argument.

190
00:08:23,980 --> 00:08:27,240
A tvrdí, že argumenty
Funkcie tlačil do zásobníka.

191
00:08:27,240 --> 00:08:29,910
A c, samozrejme, je
Aj na tomto obrázku.

192
00:08:29,910 --> 00:08:33,520
>> A len pre Značky účely,
Všimnite si, v ľavom hornom rohu

193
00:08:33,520 --> 00:08:37,020
je to, čo by c držiaku 0 a
potom mierne vpravo dole

194
00:08:37,020 --> 00:08:38,220
je c držiak 11.

195
00:08:38,220 --> 00:08:41,240
Takže inými slovami, ktore si možno predstaviť
že tam je mriežka z bytov

196
00:08:41,240 --> 00:08:44,380
tam, z ktorých prvá je
vľavo hore, dole, z ktorých

197
00:08:44,380 --> 00:08:48,360
je posledná z týchto 12 bytov.

198
00:08:48,360 --> 00:08:49,930
>> Ale teraz sa snaží rýchlo vpred.

199
00:08:49,930 --> 00:08:55,580
Čo sa má stať, ak sme sa prejsť
v reťazci bare, ktorý je dlhší ako c?

200
00:08:55,580 --> 00:08:59,130
A my nie sme kontrole, či
je to naozaj dlhšie ako 12 rokov.

201
00:08:59,130 --> 00:09:03,146
Ktorá časť obrázka bude
prepísané po bajtoch 0, 1, 2, 3,

202
00:09:03,146 --> 00:09:07,890
dot dot dot, 11, a potom sa
zlý, 12, 13 až 19?

203
00:09:07,890 --> 00:09:11,820
Čo sa bude diať tu,
ak vyvodiť z objednania

204
00:09:11,820 --> 00:09:14,790
že držiak c 0 je na vrchole
c držiak 11 je trochu dole

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

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

207
00:09:16,796 --> 00:09:19,260
>> DIVÁKOV: No, to sa deje
prepísať char * bar.

208
00:09:19,260 --> 00:09:22,260
>> David J. Malan: Jo, vyzerá to, že
budete prepísať char * bar.

209
00:09:22,260 --> 00:09:26,245
A čo je horšie, ak ste poslali naozaj dlho
reťazec, môžete dokonca prepísať, čo?

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

211
00:09:27,460 --> 00:09:28,570
Spiatočná adresa.

212
00:09:28,570 --> 00:09:31,380
Čo je opäť rovnako ako
strúhanka povedať programu, kde

213
00:09:31,380 --> 00:09:34,060
sa vrátiť, keď f
sa vykonáva volaná.

214
00:09:34,060 --> 00:09:37,140
>> Takže to, čo protivníci obvykle do
je v prípade, že narazia na program

215
00:09:37,140 --> 00:09:41,290
, Že sú zvedaví, či je
využívanie, buggy takým spôsobom,

216
00:09:41,290 --> 00:09:43,550
že on alebo ona môže mať
Výhodou tejto chybe,

217
00:09:43,550 --> 00:09:45,720
väčšinou sa im nedostáva
to hneď na prvýkrát.

218
00:09:45,720 --> 00:09:48,590
Jednoducho začať vysielať, napríklad,
náhodné reťazce do svojho programu,

219
00:09:48,590 --> 00:09:50,260
či na klávesnici,
alebo povedané, že pravdepodobne

220
00:09:50,260 --> 00:09:52,740
napísať malý program, len
automaticky generovať reťazca,

221
00:09:52,740 --> 00:09:55,430
a začať búšiť na programe
odoslanie v mnohých rôznych vstupov

222
00:09:55,430 --> 00:09:56,340
v rôznych dĺžkach.

223
00:09:56,340 --> 00:09:58,990
>> Akonáhle vaše zrútenie programu,
to je úžasná vec.

224
00:09:58,990 --> 00:10:01,020
Pretože to znamená, že
alebo ona zistila,

225
00:10:01,020 --> 00:10:02,660
čo je asi naozaj chyba.

226
00:10:02,660 --> 00:10:05,830
A potom sa môžete dostať múdrejší
a začať sústrediť užšie

227
00:10:05,830 --> 00:10:07,420
o tom, ako využiť túto chybu.

228
00:10:07,420 --> 00:10:11,480
Konkrétne, čo sa on alebo ona by mohla
urobiť, je poslať, v najlepšom prípade, ahoj.

229
00:10:11,480 --> 00:10:12,210
Žiadny veľký problém.

230
00:10:12,210 --> 00:10:14,750
Je to reťazec, ktorý je dostatočne krátky.

231
00:10:14,750 --> 00:10:18,100
Ale čo keď on alebo ona pošle,
a my zovšeobecniť ako,

232
00:10:18,100 --> 00:10:20,890
Útok code-- tak nulami
a tie, ktoré sa robiť veci,

233
00:10:20,890 --> 00:10:25,150
ako rm-rf, že odstráni všetko
z pevného disku alebo rozosielanie spamu

234
00:10:25,150 --> 00:10:27,000
alebo nejako napadnúť počítač?

235
00:10:27,000 --> 00:10:29,570
>> Takže v prípade, každý z nich
písmená A práve predstavuje

236
00:10:29,570 --> 00:10:32,380
koncepčne, útok, útok,
útok, útok, nejaký zlý kód

237
00:10:32,380 --> 00:10:36,410
že niekto iný napísal, ale
ak táto osoba je dosť šikovný,

238
00:10:36,410 --> 00:10:40,790
nielen zahŕňať všetky
z tých RM-RFS, ale tiež

239
00:10:40,790 --> 00:10:46,100
mať jeho alebo jej posledný pár bajtov
je číslo, ktoré zodpovedá

240
00:10:46,100 --> 00:10:50,540
na adresu jeho
alebo jej vlastný útok kód

241
00:10:50,540 --> 00:10:53,820
že on alebo ona prešla v niekoľkých
tým, že ju na výzvu,

242
00:10:53,820 --> 00:10:58,760
môžete efektívne trik počítač
do všímať, keď je f vykonáva vykonávania,

243
00:10:58,760 --> 00:11:02,400
oh, to je čas, aby som sa skákať
späť na červenú spiatočnú adresu.

244
00:11:02,400 --> 00:11:06,070
Ale pretože on alebo ona má nejako
prekrývali, že spiatočnú adresu

245
00:11:06,070 --> 00:11:09,602
s vlastným číslom,
a oni sú dosť bystrí na to

246
00:11:09,602 --> 00:11:11,560
aby ste nakonfigurovali, že
číslo, ktoré chcete odkazovať, ako vy

247
00:11:11,560 --> 00:11:13,740
pozri v super hore
ľavá tam kútik,

248
00:11:13,740 --> 00:11:18,020
skutočná adresa počítača
Spomienka na niektoré ich útoku kódu,

249
00:11:18,020 --> 00:11:21,740
zlý človek môže oklamať počítač
k vykonaniu svojej vlastnej kód.

250
00:11:21,740 --> 00:11:23,700
>> A ten kód znova, môže to byť čokoľvek.

251
00:11:23,700 --> 00:11:26,120
To je všeobecne nazývaný
shell kód, ktorý je práve

252
00:11:26,120 --> 00:11:29,030
spôsob, ako povedať, že to nie je
všeobecne niečo tak jednoduchého ako rm-rf.

253
00:11:29,030 --> 00:11:32,340
Je to vlastne niečo ako Bash,
alebo skutočný program, ktorý mu dáva

254
00:11:32,340 --> 00:11:37,230
alebo jej programové riadenie na vykonanie
čokoľvek iného, ​​čo chcú.

255
00:11:37,230 --> 00:11:40,210
Takže v skratke, to všetko
pochádza z jednoduchej skutočnosti,

256
00:11:40,210 --> 00:11:44,490
že táto chyba sa netýkala kontrolu
hranice svojho poľa.

257
00:11:44,490 --> 00:11:47,250
A preto, že na ceste
počítače práce je to, že

258
00:11:47,250 --> 00:11:49,430
použiť zásobník z
efektívne, koncepčne,

259
00:11:49,430 --> 00:11:54,830
Spodná hore, ale potom sa prvkami
zatlačíte do zásobníka rastie zhora nadol,

260
00:11:54,830 --> 00:11:56,624
To je neuveriteľne problematické.

261
00:11:56,624 --> 00:11:58,290
Teraz existujú spôsoby, ako obísť to.

262
00:11:58,290 --> 00:12:00,800
A úprimne povedané, tam sú jazyky
s ktorou sa tento problém vyriešiť.

263
00:12:00,800 --> 00:12:03,100
Java je imúnny, napríklad,
k tejto konkrétnej otázke.

264
00:12:03,100 --> 00:12:04,110
Vzhľadom k tomu, že vám nedávajú odkazy.

265
00:12:04,110 --> 00:12:05,943
Oni vám nedávajú
priame adresy pamäte.

266
00:12:05,943 --> 00:12:08,560
Tak s týmto výkonom, že máme
na nič siahať do pamäti

267
00:12:08,560 --> 00:12:11,580
chceme, je síce veľké riziko.

268
00:12:11,580 --> 00:12:12,430
>> Takže dávať pozor.

269
00:12:12,430 --> 00:12:14,596
Ak je, úprimne povedané, v mesiacoch
alebo rokov prísť, kedykoľvek

270
00:12:14,596 --> 00:12:17,740
budete čítať o nejakom zneužívaní
programu alebo servera,

271
00:12:17,740 --> 00:12:22,370
Ak ste niekedy vidieť náznak niečoho
ako útok pretečeniu vyrovnávacej pamäti,

272
00:12:22,370 --> 00:12:25,390
alebo pretečeniu zásobníka je iný typ
útoku, podobne ako v duchu,

273
00:12:25,390 --> 00:12:28,770
rovnako ako inšpiruje webové stránky
meno, ak ho poznáte,

274
00:12:28,770 --> 00:12:33,170
je to všetko hovorí len o
pretekaniu veľkosť nejakého znaku

275
00:12:33,170 --> 00:12:36,200
poľa alebo niektoré polia všeobecnejšie.

276
00:12:36,200 --> 00:12:38,822
Akékoľvek otázky, potom, o tom myslíte?

277
00:12:38,822 --> 00:12:39,780
Neskúšajte to doma.

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

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

280
00:12:42,300 --> 00:12:47,270
Takže malloc doteraz bola naša nová
priateľ v tom, že môžeme prideliť pamäť

281
00:12:47,270 --> 00:12:50,540
že nemusí nutne vedieť,
dopredu, že chceme, aby sme nemuseli mať

282
00:12:50,540 --> 00:12:52,920
na pevný kód do našich
čísla programov, ako je 12 rokov.

283
00:12:52,920 --> 00:12:55,550
Akonáhle užívateľ nám hovorí, koľko
Dáta on alebo ona chce na vstup,

284
00:12:55,550 --> 00:12:58,000
môžeme malloc toľko pamäte.

285
00:12:58,000 --> 00:13:01,484
>> Takže malloc to dopadá, na
miery sme sa ju používať,

286
00:13:01,484 --> 00:13:03,900
výslovne naposledy, a potom
vy ste sa používať

287
00:13:03,900 --> 00:13:08,160
pre getString nevedomky pre
niekoľko týždňov, všetky pamäte malloc je

288
00:13:08,160 --> 00:13:09,820
pochádza z takzvaného haldy.

289
00:13:09,820 --> 00:13:13,852
A to je dôvod, prečo getString, napríklad,
môže alokovať pamäť dynamicky

290
00:13:13,852 --> 00:13:16,060
bez toho aby vedel, čo ste
bude písať v predstihu,

291
00:13:16,060 --> 00:13:21,520
odovzdať späť ukazovateľ na pamäti, že,
a že pamäť je stále na vás, aby,

292
00:13:21,520 --> 00:13:24,080
aj po getString vráti.

293
00:13:24,080 --> 00:13:27,450
Pretože odvolanie po tom všetkom
Zásobník je neustále ísť hore a dole,

294
00:13:27,450 --> 00:13:27,950
hore a dole.

295
00:13:27,950 --> 00:13:30,230
A akonáhle to ide
dole, to znamená, že akýkoľvek pamäť

296
00:13:30,230 --> 00:13:33,030
táto funkcia použitá,
nemal byť používaný niekým iným.

297
00:13:33,030 --> 00:13:34,570
Je to hodnoty odpadky teraz.

298
00:13:34,570 --> 00:13:36,120
>> Ale hromada je tu.

299
00:13:36,120 --> 00:13:39,360
A čo je pekné o malloc je to, že
keď malloc prideľuje pamäť tu,

300
00:13:39,360 --> 00:13:42,070
to nie je ovplyvnený, pretože
z väčšej časti tým, že v zásobníku.

301
00:13:42,070 --> 00:13:46,000
A tak nejaká funkcia prístup
pamäť, ktorá bola malloc'd,

302
00:13:46,000 --> 00:13:49,120
ani funkcie ako je getString,
aj potom, čo sa vráti.

303
00:13:49,120 --> 00:13:51,700
>> Teraz hovoriť malloc je zadarmo.

304
00:13:51,700 --> 00:13:53,900
A skutočne, na pravidlo, ktoré
treba začať prijatie

305
00:13:53,900 --> 00:13:58,950
je nejaký, niektorý, nejaký čas používať malloc
musíte sami používať zadarmo, prípadne,

306
00:13:58,950 --> 00:14:00,280
na rovnakom ukazovateli.

307
00:14:00,280 --> 00:14:03,289
Celú tú dobu sme sa písať
buggy, buggy kód, z mnohých dôvodov.

308
00:14:03,289 --> 00:14:05,580
Ale jeden z nich bol
pomocou knižnice CS50, ktoré

309
00:14:05,580 --> 00:14:09,010
sama o sebe je zámerne
buggy, to nevracia pamäť.

310
00:14:09,010 --> 00:14:11,410
Zakaždým, keď som volal getString
počas posledných niekoľkých týždňov

311
00:14:11,410 --> 00:14:13,870
pýtame sa prevádzkové
systém, Linux, pre pamäť.

312
00:14:13,870 --> 00:14:15,780
A vy ste ani raz ho dal naspäť.

313
00:14:15,780 --> 00:14:17,730
A to nie je, v
praxe, dobrá vec.

314
00:14:17,730 --> 00:14:20,330
>> A Valgrind, jeden z
nástroje zavedené v pset 4,

315
00:14:20,330 --> 00:14:22,900
je predovšetkým o ktorý vám pomôže
teraz nájsť chyby, ako že.

316
00:14:22,900 --> 00:14:27,060
Ale našťastie pre pset 4 nepotrebujete
iba v CS50 knižnicu alebo getString.

317
00:14:27,060 --> 00:14:31,220
Takže nejaké chyby spojené s pamäťou sú
nakoniec bude váš vlastný.

318
00:14:31,220 --> 00:14:34,060
>> Takže malloc je viac než len
vhodné na tento účel.

319
00:14:34,060 --> 00:14:37,420
Môžeme vlastne teraz riešiť
zásadne odlišné problémy,

320
00:14:37,420 --> 00:14:41,640
a zásadne riešiť problémy viac
efektívne, ako za týždeň nula sľubu.

321
00:14:41,640 --> 00:14:44,720
Potiaľto je to sexy
štruktúra dát sme mali.

322
00:14:44,720 --> 00:14:47,804
A dátové štruktúry som na mysli
spôsob Konceptualizácia pamäte

323
00:14:47,804 --> 00:14:50,720
spôsobom, ktorý presahuje len hovorím,
to je int, to je char.

324
00:14:50,720 --> 00:14:52,930
Môžeme začať klastra veci dohromady.

325
00:14:52,930 --> 00:14:54,460
>> Takže pole vyzeral takto.

326
00:14:54,460 --> 00:14:57,270
A čo je kľúčom k
Pole je, že vám dáva

327
00:14:57,270 --> 00:14:59,724
back-to-back kusy
pamäte, z ktorých každá

328
00:14:59,724 --> 00:15:02,765
bude rovnakého typu, int,
int, int, int alebo char, char, char,

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

330
00:15:03,330 --> 00:15:04,496
Ale je tu niekoľko tienisté stránky.

331
00:15:04,496 --> 00:15:06,570
To napríklad, je
poľa veľkosti šesť.

332
00:15:06,570 --> 00:15:10,650
Predstavte si, že vyplnenie tohto poľa sa šiestimi
čísla a potom, z akéhokoľvek dôvodu,

333
00:15:10,650 --> 00:15:13,187
Vaše užívateľské chce dať
ste sedmina číslo.

334
00:15:13,187 --> 00:15:14,020
Kde si dať?

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

336
00:15:15,490 --> 00:15:18,990
>> Aké je riešenie, ak máte
vytvoril rad na zásobníku,

337
00:15:18,990 --> 00:15:22,030
Napríklad, iba s týždeň
dve notácie, že sme uviedli,

338
00:15:22,030 --> 00:15:23,730
hranatých zátvoriek s číslom vnútri?

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

340
00:15:25,160 --> 00:15:27,260
No, máš šesť
Čísla v týchto krabiciach.

341
00:15:27,260 --> 00:15:28,530
Čo by vaše inštinkty byť?

342
00:15:28,530 --> 00:15:29,973
Kam by ste chceli dať?

343
00:15:29,973 --> 00:15:30,860
>> Divákov: [nepočuteľné]

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

345
00:15:31,315 --> 00:15:32,380
>> Divákov: Dajte ju na konci.

346
00:15:32,380 --> 00:15:33,796
>> David J. Malan: Dajte ju na konci.

347
00:15:33,796 --> 00:15:35,880
Tak len niečo málo cez doprava,
mimo tento box.

348
00:15:35,880 --> 00:15:38,710
Čo by bolo pekné, ale je to
Ukazuje sa, môžete to urobiť.

349
00:15:38,710 --> 00:15:41,350
Pretože ak ste nepožiadal
pre tento kus pamäti,

350
00:15:41,350 --> 00:15:44,490
mohlo by to byť náhodou, že tento
sa používa nejaké iné premenné

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

352
00:15:45,030 --> 00:15:49,210
Spomeňte si týždeň alebo tak, keď sme položili
z Zamyla a DAVINA a Gabe je menami

353
00:15:49,210 --> 00:15:49,930
v pamäti.

354
00:15:49,930 --> 00:15:51,638
Boli doslova
chrbtom k sebe k sebe.

355
00:15:51,638 --> 00:15:53,550
Takže nemôžeme byť nutne
verím, že čokoľvek je

356
00:15:53,550 --> 00:15:55,800
tu je k dispozícii pre mňa použitie.

357
00:15:55,800 --> 00:15:56,990
>> Takže čo iného môžete robiť?

358
00:15:56,990 --> 00:16:00,282
No, akonáhle si uvedomil, vás
Potrebujete poľa veľkosti sedem,

359
00:16:00,282 --> 00:16:02,490
môžete len vytvoriť
poľa veľkosti sedem potom použite

360
00:16:02,490 --> 00:16:05,950
cyklu for alebo while,
skopírujte ho do nového poľa,

361
00:16:05,950 --> 00:16:09,680
a potom nejako jednoducho zbaviť
Toto pole alebo jednoducho prestaňte ho používať.

362
00:16:09,680 --> 00:16:12,130
Ale to nie je príliš efektívne.

363
00:16:12,130 --> 00:16:15,340
Stručne povedané, pole nenechajte
dynamicky meniť veľkosť.

364
00:16:15,340 --> 00:16:17,900
>> Takže na jednej strane sa dostanete
náhodný prístup, čo je úžasné.

365
00:16:17,900 --> 00:16:20,108
Vzhľadom k tomu, že nám umožňuje robiť veci,
ako rozdeľ a panuj,

366
00:16:20,108 --> 00:16:23,100
binárne vyhľadávanie, všetci máme
hovoril o na obrazovke tu.

367
00:16:23,100 --> 00:16:24,950
Ale tie farby sa do kúta.

368
00:16:24,950 --> 00:16:27,810
Akonáhle stlačíte
koniec tvojho poľa,

369
00:16:27,810 --> 00:16:29,980
čo musíte urobiť veľmi
drahý prevádzku

370
00:16:29,980 --> 00:16:33,910
alebo napísať veľa kódu
aby sa vysporiadať s týmto problémom.

371
00:16:33,910 --> 00:16:36,680
>> Čo keď namiesto toho sme mali
niečo ako zoznam,

372
00:16:36,680 --> 00:16:38,820
alebo spájať zoznam sa konkrétne jedná?

373
00:16:38,820 --> 00:16:41,930
Čo keď namiesto toho, aby
obdĺžniky chrbtom k sebe k sebe,

374
00:16:41,930 --> 00:16:45,730
máme obdĺžniky, ktoré opustí malý
trochu manévrovací priestor medzi nimi?

375
00:16:45,730 --> 00:16:49,670
A aj keď som sa vyvodiť tento
obrazu alebo prispôsobiť tento obrázok

376
00:16:49,670 --> 00:16:54,696
z jedného z textov, tu sa vráti do
chrbtom k sebe veľmi usporiadane, v skutočnosti,

377
00:16:54,696 --> 00:16:56,820
jeden z týchto obdĺžnikov
by mohol byť tu v pamäti.

378
00:16:56,820 --> 00:16:58,028
Jedným z nich by mohol byť tu.

379
00:16:58,028 --> 00:17:00,420
Jedným z nich by mohla byť tu,
sem, a tak ďalej.

380
00:17:00,420 --> 00:17:02,910
>> Ale čo keď sme vychádzali,
v tomto prípade, šípky

381
00:17:02,910 --> 00:17:05,650
to nejako prepojiť ich
obdĺžniky dohromady?

382
00:17:05,650 --> 00:17:08,170
Skutočne sme videli technický
stelesnenie šípkou.

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

384
00:17:09,839 --> 00:17:13,710
Čo sme v poslednej
dni, že pod kapotou,

385
00:17:13,710 --> 00:17:15,210
vyjadrujúce šípky?

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

387
00:17:16,290 --> 00:17:17,349
Ukazovateľ, že jo?

388
00:17:17,349 --> 00:17:19,780
>> Čo keď miesto
len uloženie čísla,

389
00:17:19,780 --> 00:17:23,130
ako 9, 17, 22, 26, 34,
čo keby sme neukladá

390
00:17:23,130 --> 00:17:27,079
iba číslo, ale ukazovateľ
pri každej takejto číslo?

391
00:17:27,079 --> 00:17:30,690
Tak, že podobne ako by ste závit
ihlu cez veľa látky,

392
00:17:30,690 --> 00:17:32,950
nejako viazanie veci
spoločne, podobne môžu

393
00:17:32,950 --> 00:17:35,550
sme sa s ukazovateľmi, ako je
inkarnoval šípkami tu

394
00:17:35,550 --> 00:17:38,550
druh tkať spolu
tieto jednotlivé obdĺžniky

395
00:17:38,550 --> 00:17:41,780
tým, že účinne pomocou ukazovateľa
vedľa každého čísla, ktoré

396
00:17:41,780 --> 00:17:46,065
poukazuje na niektoré ďalšie číslo, ktoré
poukazuje na zase nejaký ďalšie číslo?

397
00:17:46,065 --> 00:17:47,940
Takže inými slovami, to, čo
Ak by sme skutočne chceli

398
00:17:47,940 --> 00:17:49,820
realizovať niečo také?

399
00:17:49,820 --> 00:17:53,610
Tak bohužiaľ, tieto obdĺžniky
Aspoň že ten s 9, 17, 22,

400
00:17:53,610 --> 00:17:57,040
a tak ďalej, to sú už
pekné námestie s jednotlivými číslami.

401
00:17:57,040 --> 00:17:59,960
Spodné, obdĺžnik
pod 9, napríklad,

402
00:17:59,960 --> 00:18:04,330
predstavuje to, čo by malo
byť ukazovateľ, 32 bitov.

403
00:18:04,330 --> 00:18:09,460
Teraz som ešte nevie akýkoľvek dátový typ
v jazyku C, ktoré vám umožnia nielen int

404
00:18:09,460 --> 00:18:11,630
ale ukazovateľ úplne.

405
00:18:11,630 --> 00:18:15,020
>> Takže aké je riešenie, ak chceme
vymyslieť vlastnú odpoveď na to?

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

407
00:18:15,760 --> 00:18:16,640
>> Divákov: [nepočuteľné]

408
00:18:16,640 --> 00:18:17,360
>> David J. Malan: Čo je to?

409
00:18:17,360 --> 00:18:17,880
>> Divákov: Nová štruktúra.

410
00:18:17,880 --> 00:18:19,590
>> David J. Malan: Jo, tak prečo
Čo keby sme vytvoriť novú štruktúru,

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

412
00:18:20,920 --> 00:18:25,990
Videli sme structs skôr, ak krátko,
kde sme sa zaoberali štruktúrou študentov

413
00:18:25,990 --> 00:18:27,780
takto, ktorý mal meno a domu.

414
00:18:27,780 --> 00:18:31,980
V pset 3 útek, ktorú ste použili celý
banda structs-- GRect a GOvals

415
00:18:31,980 --> 00:18:34,810
že Stanford vytvorený
klaster informácie dohromady.

416
00:18:34,810 --> 00:18:38,580
Tak čo, ak vezmeme rovnaký nápad
kľúčové slová "typedef" a "struct",

417
00:18:38,580 --> 00:18:42,890
a potom nejaký študent-špecifické veci,
a vyvíjať sa to do nasledujúcich:

418
00:18:42,890 --> 00:18:46,210
typedef struct node-- a uzol je
len veľmi všeobecná počítačová vedy

419
00:18:46,210 --> 00:18:49,980
termín pre niečo, čo v dátovej štruktúre,
Kontajner v dátovej štruktúre.

420
00:18:49,980 --> 00:18:53,900
Uzol Tvrdím, bude mať
int n, úplne jednoduché,

421
00:18:53,900 --> 00:18:58,810
a potom sa trochu záhadne,
Tento druhý riadok, struct uzol * ďalšie.

422
00:18:58,810 --> 00:19:01,300
Ale menej z technického hľadiska,
čo je to druhý riadok

423
00:19:01,300 --> 00:19:02,980
kódu vnútri zložených zátvoriek?

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

425
00:19:03,737 --> 00:19:04,851
>> Divákov: [nepočuteľné]

426
00:19:04,851 --> 00:19:06,600
David J. Malan:
ukazovateľ do iného uzla.

427
00:19:06,600 --> 00:19:09,910
Takže síce syntaxe trochu záhadné.

428
00:19:09,910 --> 00:19:13,250
Ale ak budete čítať doslova,
Ďalšia je názov premennej.

429
00:19:13,250 --> 00:19:14,410
Aký je jej dátový typ?

430
00:19:14,410 --> 00:19:18,206
Je to trochu ukecaný tentoraz,
ale to je typu struct uzol *.

431
00:19:18,206 --> 00:19:22,960
Kedykoľvek sme videli niečo hviezdu, ktorá
znamená, že je ukazovateľ na tento typ dát.

432
00:19:22,960 --> 00:19:26,810
Takže ďalší je zrejme
ukazovateľ na struct uzol.

433
00:19:26,810 --> 00:19:28,310
>> A teraz, čo je uzol struct?

434
00:19:28,310 --> 00:19:31,044
Dobre si všimnite, vidíš ty,
Rovnaké slová v pravom hornom rohu.

435
00:19:31,044 --> 00:19:33,960
A skutočne, môžete tiež vidieť slovo
"Uzol" tu dole v ľavom dolnom rohu.

436
00:19:33,960 --> 00:19:35,640
A to je vlastne len pohodlie.

437
00:19:35,640 --> 00:19:39,930
Všimnite si, že v našej definícii študenta
je tu slovo "žiak" iba raz.

438
00:19:39,930 --> 00:19:42,510
A to preto, že študent
Objekt nebol úplne evidentné.

439
00:19:42,510 --> 00:19:45,340
Nie je nič vnútri študenta
že je potrebné, aby ukazoval na iný študent,

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

441
00:19:45,610 --> 00:19:47,630
To by bolo trochu
divný v reálnom svete.

442
00:19:47,630 --> 00:19:50,880
>> Ale s uzlom v spojen
zoznam, my chceme uzol

443
00:19:50,880 --> 00:19:53,970
ako referenčná k podobným predmetom.

444
00:19:53,970 --> 00:19:57,900
A tak zistíte tu zmena nie je
len to, čo je vo vnútri zložených zátvoriek.

445
00:19:57,900 --> 00:20:00,800
Ale pridať slovo "uzol"
v hornej časti, ako aj

446
00:20:00,800 --> 00:20:02,930
pridaním na dno
namiesto "študenta."

447
00:20:02,930 --> 00:20:06,000
A to je len technický detail
tak, že, opäť Vaša dátová štruktúra

448
00:20:06,000 --> 00:20:11,380
môže byť samo-referenčná, takže
uzol môže ukazovať na iného takého uzla.

449
00:20:11,380 --> 00:20:13,840
>> Takže to, čo je v konečnom dôsledku
bude znamenať pre nás?

450
00:20:13,840 --> 00:20:17,560
No, jeden, toto dovnútra
je obsah nášho uzla.

451
00:20:17,560 --> 00:20:19,360
To, čo tu,
vpravo hore, je tak

452
00:20:19,360 --> 00:20:20,860
že opäť môžeme odkazovať na seba.

453
00:20:20,860 --> 00:20:23,401
A potom vonkajšie veci,
aj keď uzol je nový termín,

454
00:20:23,401 --> 00:20:25,500
Možno, že je to stále
rovnako ako študenti, a čo

455
00:20:25,500 --> 00:20:27,520
bol pod kapotou v SPL.

456
00:20:27,520 --> 00:20:31,095
>> Takže ak by sme sa chceli začať
vykonávanie tohto prepojeného zoznamu,

457
00:20:31,095 --> 00:20:33,220
Ako by sme mohli preložiť
niečo také sa kód?

458
00:20:33,220 --> 00:20:35,350
No, povedzme, viď
Príklad programu, ktorý

459
00:20:35,350 --> 00:20:36,840
v skutočnosti používa spájať zoznam.

460
00:20:36,840 --> 00:20:40,870
Medzi dnešné distribučné kódu
je program, nazvaný zoznam nula.

461
00:20:40,870 --> 00:20:44,980
A keď som spustiť tento som vytvoril super
jednoduché GUI, Graphical User Interface,

462
00:20:44,980 --> 00:20:46,460
ale je to naozaj len printf.

463
00:20:46,460 --> 00:20:50,930
A teraz som vzhľadom k tomu sám pár ponuku
options-- Delete, Insert, vyhľadávanie,

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

465
00:20:51,750 --> 00:20:52,630
A ukončite.

466
00:20:52,630 --> 00:20:55,970
To sú len bežné operácie
dátové štruktúry známej ako zoznam odkazov.

467
00:20:55,970 --> 00:20:58,409
>> Teraz, Delete sa chystá
Vymazanie čísla zo zoznamu.

468
00:20:58,409 --> 00:21:00,200
Vložte ide pridať
číslo v zozname.

469
00:21:00,200 --> 00:21:02,181
Vyhľadávanie bude vyzerať
na číslo v zozname.

470
00:21:02,181 --> 00:21:04,930
A traverz je len ozdobný spôsob, ako
hovoriť, prejsť zoznamu

471
00:21:04,930 --> 00:21:06,245
vytlačiť, ale to je všetko.

472
00:21:06,245 --> 00:21:07,720
Nemeňte ho žiadnym spôsobom.

473
00:21:07,720 --> 00:21:08,570
>> Takže skúsme to.

474
00:21:08,570 --> 00:21:10,160
Poďme ďalej a typ 2.

475
00:21:10,160 --> 00:21:12,710
A potom budem
vložte číslo, povedzme 9.

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

477
00:21:13,620 --> 00:21:17,480
A teraz môj program je jednoducho
naprogramovaný tak, aby povedať, zoznam je teraz deväť.

478
00:21:17,480 --> 00:21:20,190
Teraz, keď som sa do toho pustite a
Vložte si znova, nech

479
00:21:20,190 --> 00:21:23,680
ma ísť napred a oddialenie a zadajte 17.

480
00:21:23,680 --> 00:21:25,770
Teraz môj zoznam je 9, potom 17.

481
00:21:25,770 --> 00:21:27,750
Ak sa mi vložiť znova, poďme preskočiť jeden.

482
00:21:27,750 --> 00:21:32,400
Namiesto 22, podľa obrázku máme
sa pri pohľade na tú, dovoľte mi, aby som náskok

483
00:21:32,400 --> 00:21:34,630
a vložte 26 ďalšie.

484
00:21:34,630 --> 00:21:36,230
Takže budem písať 26.

485
00:21:36,230 --> 00:21:37,755
Tento zoznam je, ako som očakávať.

486
00:21:37,755 --> 00:21:40,630
Ale teraz, len aby zistil, či tento kód
bude flexibilná, dovoľte mi, aby som sa

487
00:21:40,630 --> 00:21:43,520
typ 22, ktorý aspoň
koncepčne, keď sme

488
00:21:43,520 --> 00:21:46,520
Udržať tento radené, čo je naozaj
bude ďalším cieľom práve teraz,

489
00:21:46,520 --> 00:21:48,690
by mal ísť medzi 17 a 26 rokov.

490
00:21:48,690 --> 00:21:50,270
Tak som stlačte Enter.

491
00:21:50,270 --> 00:21:51,380
V skutočnosti, to funguje.

492
00:21:51,380 --> 00:21:54,950
A tak teraz mi dovoľte vložiť
Posledný, na obrázku, 34.

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

494
00:21:55,450 --> 00:21:58,980
Takže teraz mi dovoľte stanovuje, že
Odstrániť a Traverse a hľadanie robiť,

495
00:21:58,980 --> 00:21:59,760
v skutočnosti, pracovať.

496
00:21:59,760 --> 00:22:04,180
V skutočnosti, keď sa mi spustiť vyhľadávanie, poďme
vyhľadať číslo 22, Enter.

497
00:22:04,180 --> 00:22:05,010
Bolo zistené 22.

498
00:22:05,010 --> 00:22:07,580
Takže to je to, čo tento
Program Zoznam Zero robí.

499
00:22:07,580 --> 00:22:10,230
>> Ale čo sa vlastne deje
na ktorý implementuje to?

500
00:22:10,230 --> 00:22:14,530
No, najprv by som mohol mať, a skutočne
Musím, súbor s názvom list0.h.

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

502
00:22:16,540 --> 00:22:20,690
A niekde tam je to
linka, typedef struct uzol,

503
00:22:20,690 --> 00:22:24,850
potom mám zložené zátvorky, int n, a
potom struct-- čo bolo definícia?

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

505
00:22:26,530 --> 00:22:28,545
Struct uzol ďalšie.

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

507
00:22:29,920 --> 00:22:31,045
Takže potrebujeme hviezdu.

508
00:22:31,045 --> 00:22:33,420
Teraz technicky sme sa dostali do
zvyk kreslenie tu.

509
00:22:33,420 --> 00:22:35,670
Môžete vidieť učebnice a
on-line odkazy na to tam.

510
00:22:35,670 --> 00:22:36,660
Je to funkčne ekvivalentný.

511
00:22:36,660 --> 00:22:37,980
V skutočnosti, je to trochu typické.

512
00:22:37,980 --> 00:22:40,563
Ale budem v súlade s čím
sme minule a to.

513
00:22:40,563 --> 00:22:42,350
A potom konečne, budem to robiť.

514
00:22:42,350 --> 00:22:45,550
>> Takže v hlavičkovom súbore
niekde v list0.h

515
00:22:45,550 --> 00:22:49,200
dnes je táto definícia struct,
a možno niektoré ďalšie veci.

516
00:22:49,200 --> 00:22:52,580
Zatiaľ v list0c tú
bude pár vecí.

517
00:22:52,580 --> 00:22:54,740
Ale budeme len
štart a nie dokončiť.

518
00:22:54,740 --> 00:22:59,690
List0.h je súbor chcem
zaradiť do môjho C súbor.

519
00:22:59,690 --> 00:23:03,910
A potom sa v určitom okamihu som
bude mať int, hlavné, neplatné.

520
00:23:03,910 --> 00:23:06,530
A potom budem
mať niektoré úloh je tu.

521
00:23:06,530 --> 00:23:10,620
Taky budem mať
prototyp, ako neplatné, vyhľadávanie, int,

522
00:23:10,620 --> 00:23:13,610
n, ktorých zmyslom života je
hľadať elementu.

523
00:23:13,610 --> 00:23:18,310
A potom sa tu tvrdí, v
Dnešné kód, void, hľadanie, int n,

524
00:23:18,310 --> 00:23:21,020
nie bodkočiarka, ale otvorené zložené zátvorky.

525
00:23:21,020 --> 00:23:25,049
A teraz chcem nejako vyhľadávanie
prvku v tomto zozname.

526
00:23:25,049 --> 00:23:27,340
Ale nemáme dosť
informácie na obrazovke ešte.

527
00:23:27,340 --> 00:23:29,800
Nemám vlastne
predstavovali samotný zoznam.

528
00:23:29,800 --> 00:23:33,070
Takže jeden spôsob, ako by sme mohli realizovať
spájať zoznam v programe

529
00:23:33,070 --> 00:23:37,520
je, že som trochu urobiť niečo
ako vyhlásiť, spájať zoznam tu.

530
00:23:37,520 --> 00:23:40,520
Pre jednoduchosť budem robiť
tento globálny, aj keď v Všeobecne

531
00:23:40,520 --> 00:23:41,645
nemali robiť to príliš veľa.

532
00:23:41,645 --> 00:23:43,260
Ale to bude zjednodušenie tento príklad.

533
00:23:43,260 --> 00:23:45,890
Tak som chcel deklarovať
spájať zoznam tu.

534
00:23:45,890 --> 00:23:47,010
Teraz, ako by to robil?

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

536
00:23:48,810 --> 00:23:50,750
>> Tu je obrázok prepojeného zoznamu.

537
00:23:50,750 --> 00:23:53,030
A ja naozaj nemám
vedieť, v okamihu, kedy ako

538
00:23:53,030 --> 00:23:56,710
Chystám sa ísť o zastupovanie
toľko vecí, ktoré sa len jeden

539
00:23:56,710 --> 00:23:58,040
premenná v pamäti.

540
00:23:58,040 --> 00:23:59,160
Ale spomínam na okamih.

541
00:23:59,160 --> 00:24:00,830
Celú tú dobu sme mali
reťazce, ktoré potom

542
00:24:00,830 --> 00:24:02,913
odhalil, že je pole pre
znaky, ktoré potom

543
00:24:02,913 --> 00:24:05,740
odhalený byť len ukazovateľ
na prvý znak

544
00:24:05,740 --> 00:24:08,890
v poli znakov
, Ktorý je ukončený nulovým znakom.

545
00:24:08,890 --> 00:24:13,530
Takže podľa tejto logiky, a s tým
obrázok druh siatie svoje myšlienky,

546
00:24:13,530 --> 00:24:17,964
Načo nám vlastne napísať v našej
kód predstavuje spájať zoznam?

547
00:24:17,964 --> 00:24:21,130
Koľko z týchto informácií potrebujeme
zachytiť v C kóde, povedali by ste?

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

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

550
00:24:23,154 --> 00:24:24,738
>> Divákov: Potrebujeme ukazovateľ na uzol.

551
00:24:24,738 --> 00:24:26,237
David J. Malan: ukazovateľ na uzol.

552
00:24:26,237 --> 00:24:29,320
Najmä, ktorý uzol by bol váš
inštinkty sa udržať ukazovateľ?

553
00:24:29,320 --> 00:24:30,026
>> Divákov: prvý uzol.

554
00:24:30,026 --> 00:24:31,942
>> David J. Malan: Áno,
asi len ten prvý.

555
00:24:31,942 --> 00:24:34,030
A všimnite si, prvý
Uzol je odlišný tvar.

556
00:24:34,030 --> 00:24:37,690
Je to len polovičná veľkosť struct,
pretože je to naozaj len ukazovateľ.

557
00:24:37,690 --> 00:24:44,650
Takže to, čo môžete naozaj urobiť, je vyhlásiť
spájať zoznam byť typu uzla *.

558
00:24:44,650 --> 00:24:47,780
A povedzme prvý nazvať
a inicializovať ju na hodnotu null.

559
00:24:47,780 --> 00:24:49,910
Takže null, je opäť prichádza
na obrázku tu.

560
00:24:49,910 --> 00:24:53,620
Nielen, že je null používaný ako napríklad špeciálne
Návratová hodnota pre veci, ako getString

561
00:24:53,620 --> 00:24:57,770
a malloc, null je takisto nulová
ukazovateľ, nedostatok ukazovatele,

562
00:24:57,770 --> 00:24:58,430
ak chcete.

563
00:24:58,430 --> 00:25:00,309
To jednoducho znamená, že nič, čo je ešte tu.

564
00:25:00,309 --> 00:25:02,100
Teraz prvýkrát, mohol som
volal to čokoľvek.

565
00:25:02,100 --> 00:25:04,200
Mohol som to nazval "zoznam"
alebo ľubovoľný počet ďalších vecí.

566
00:25:04,200 --> 00:25:06,960
Ale ja som volať to "prvý", takže
, Aby sa ocitol obrázku.

567
00:25:06,960 --> 00:25:10,280
Tak ako reťazec môže byť reprezentovaný
s adresou svojho prvého bytu,

568
00:25:10,280 --> 00:25:11,280
takže môže spájať zoznam.

569
00:25:11,280 --> 00:25:13,480
A uvidíme ďalšie dáta
konštrukcia je zastúpená

570
00:25:13,480 --> 00:25:16,700
iba s jedným ukazovateľom,
32-bit šípka smerujúca

571
00:25:16,700 --> 00:25:18,740
v prvom uzle v štruktúre.

572
00:25:18,740 --> 00:25:20,340
>> Ale teraz poďme predpokladať problém.

573
00:25:20,340 --> 00:25:23,230
Ak som len spomínanie
v mojom programe adresy

574
00:25:23,230 --> 00:25:27,220
z prvého uzla, najskôr
obdĺžnik v tejto dátovej štruktúre,

575
00:25:27,220 --> 00:25:31,760
čo bolo lepšie byť prípad o
Realizácia zvyšok môjho zoznamu?

576
00:25:31,760 --> 00:25:35,820
Čo je to kľúčový detail, čo sa deje
zabezpečiť, že toto skutočne funguje?

577
00:25:35,820 --> 00:25:39,250
A tým "skutočne funguje" Aj
Teda, podobne ako reťazec,

578
00:25:39,250 --> 00:25:42,180
nám umožňuje prejsť od prvého znaku
v Davin menom na druhej,

579
00:25:42,180 --> 00:25:44,755
na tretí, na
štvrtý, až do samého konca,

580
00:25:44,755 --> 00:25:47,880
ako vieme, keď sme na konci
prepojeného zoznamu, ktorý vyzerá takto?

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

582
00:25:50,035 --> 00:25:50,660
Keď je null.

583
00:25:50,660 --> 00:25:53,640
A ja som predstavoval tento druh ako
ako elektrický inžinier silou,

584
00:25:53,640 --> 00:25:56,420
s malou uzemnenie
symbol, druhov.

585
00:25:56,420 --> 00:25:58,246
Ale to len znamená, null v tomto prípade.

586
00:25:58,246 --> 00:26:00,370
Môžete nakresliť ľubovoľný počet
spôsobmi, ale tento autor

587
00:26:00,370 --> 00:26:02,800
Stalo sa tu používať tento symbol.

588
00:26:02,800 --> 00:26:06,260
>> Tak dlho, ako budeme navliekať
všetkých týchto uzlov spoločne,

589
00:26:06,260 --> 00:26:08,600
zapamätanie iba v prípade,
Prvý z nich je, tak dlho

590
00:26:08,600 --> 00:26:11,760
ako vložiť špeciálny symbol na
úplne posledný uzol v zozname,

591
00:26:11,760 --> 00:26:15,130
a budeme používať hodnotu null, pretože to je
to, čo máme k dispozícii pre nás,

592
00:26:15,130 --> 00:26:16,480
Tento zoznam je kompletný.

593
00:26:16,480 --> 00:26:20,190
A aj keď som len dať ukazovateľ na
prvý prvok, tie, programátor,

594
00:26:20,190 --> 00:26:22,486
určite prístup zvyšok.

595
00:26:22,486 --> 00:26:24,360
Ale poďme sa nechať svoju myseľ
blúdiť trochu,

596
00:26:24,360 --> 00:26:26,140
v prípade, že nie sú už
docela wandered-- čo je

597
00:26:26,140 --> 00:26:28,723
bude čas behu
nájsť niečo v tomto zozname?

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

599
00:26:30,450 --> 00:26:33,470
Sakra, je to veľké O n,
čo nie je zlé, v spravodlivosti.

600
00:26:33,470 --> 00:26:34,800
Ale je to lineárna.

601
00:26:34,800 --> 00:26:37,980
Vzdali sme to, čo funkcia
polí presunutím viac

602
00:26:37,980 --> 00:26:43,130
k tomuto obrázku dynamicky
tkané spoločne alebo prepojené uzly?

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

604
00:26:44,970 --> 00:26:46,687
Dali sme si náhodný prístup.

605
00:26:46,687 --> 00:26:48,770
Pole je pekné, pretože
matematicky všetko

606
00:26:48,770 --> 00:26:50,340
je chrbtom k sebe k sebe k sebe.

607
00:26:50,340 --> 00:26:52,370
Aj keď tento obrázok
vyzerá pekne, a dokonca aj

608
00:26:52,370 --> 00:26:55,830
aj keď to vyzerá, že tieto uzly
sú pekne od seba, v skutočnosti

609
00:26:55,830 --> 00:26:56,830
by mohli byť kdekoľvek.

610
00:26:56,830 --> 00:27:01,590
OX1, Ox50, Ox123, Ox99, títo
uzly by mohli byť kdekoľvek.

611
00:27:01,590 --> 00:27:05,960
Vzhľadom k tomu, malloc robí alokovať pamäť
z haldy, ale kdekoľvek v halde.

612
00:27:05,960 --> 00:27:09,080
Nemusíte nutne vedieť, že je
bude chrbtom k sebe k sebe.

613
00:27:09,080 --> 00:27:12,460
A tak to registrácia do reality je
to bude celkom to pekná.

614
00:27:12,460 --> 00:27:16,140
>> Takže to bude trvať trochu
pracovať na vykonávanie tejto funkcie.

615
00:27:16,140 --> 00:27:17,880
Takže poďme realizovať Hľadať.

616
00:27:17,880 --> 00:27:20,250
A uvidíme, druh
šikovný spôsob, ako to urobiť.

617
00:27:20,250 --> 00:27:24,660
Takže keď som vyhľadávacie funkcie a
Ja som vzhľadom k premennej, číslo N

618
00:27:24,660 --> 00:27:28,490
hľadať, musím vedieť,
Nová syntax hľadá vnútri

619
00:27:28,490 --> 00:27:32,400
štruktúry, ktorá je
ukázal, nájsť n.

620
00:27:32,400 --> 00:27:33,210
Tak poďme na to.

621
00:27:33,210 --> 00:27:36,030
>> Takže najprv som ísť
dopredu a vyhlásiť uzol *.

622
00:27:36,030 --> 00:27:39,400
A budem to hovoriť
ukazovateľ, len konvencií.

623
00:27:39,400 --> 00:27:41,710
A ja sa inicializovať ju ako prvý.

624
00:27:41,710 --> 00:27:43,770
A teraz môžem urobiť
v mnohých ohľadoch.

625
00:27:43,770 --> 00:27:45,436
Ale budem mať spoločný prístup.

626
00:27:45,436 --> 00:27:50,180
Kým ukazovateľ nie je rovné
null, a to je platné syntaxe.

627
00:27:50,180 --> 00:27:54,550
A to jednoducho znamená, že nasledujúci kód, takže
ak nie ste ukázal na nič.

628
00:27:54,550 --> 00:27:55,800
Čo chcete robiť?

629
00:27:55,800 --> 00:28:01,939
>> Ak sa ukazovateľ bodka n, dovoľte mi, aby som sa vrátil
k tomu, equals-- rovná čo?

630
00:28:01,939 --> 00:28:03,105
Aké hodnoty mám hľadať?

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

632
00:28:04,920 --> 00:28:06,590
Skutočná n, ktorý bol schválený v.

633
00:28:06,590 --> 00:28:09,020
Tak tu je ďalšia vlastnosť,
o C a mnohých jazykov.

634
00:28:09,020 --> 00:28:13,705
Aj keď uzol štruktúry zvané
má hodnotu n, úplne legitímne

635
00:28:13,705 --> 00:28:17,530
tiež mať miestnu argumentu
alebo premenné s názvom n.

636
00:28:17,530 --> 00:28:20,085
Pretože aj my, s
ľudské oko môže rozlíšiť

637
00:28:20,085 --> 00:28:22,087
že toto n je pravdepodobne
odlišný od tohto n.

638
00:28:22,087 --> 00:28:23,420
Vzhľadom k tomu, syntax je odlišná.

639
00:28:23,420 --> 00:28:26,211
Máš bodku a ukazovateľ,
že táto jedna nemá žiadnu takú vec.

640
00:28:26,211 --> 00:28:27,290
Takže to je v poriadku.

641
00:28:27,290 --> 00:28:29,120
To je v poriadku, aby im hovoriť rovnaké veci.

642
00:28:29,120 --> 00:28:32,380
>> Ak mám sa vám nájsť to, ja som
bude chcieť niečo urobiť

643
00:28:32,380 --> 00:28:35,000
ako oznamujeme, že sme našli n.

644
00:28:35,000 --> 00:28:37,930
A necháme to ako
komentár alebo pseudokód kód.

645
00:28:37,930 --> 00:28:40,190
Else, a tu je
Zaujímavosťou, čo

646
00:28:40,190 --> 00:28:47,320
nechcem robiť, keď aktuálneho uzla
nie obsahujúce n, že mi záleží?

647
00:28:47,320 --> 00:28:50,700
Ako môžem dosiahnuť nasledujúce?

648
00:28:50,700 --> 00:28:53,710
Ak sa môj prst na
moment je PTR, a to je

649
00:28:53,710 --> 00:28:55,920
ukázal na čokoľvek
Prvý ukazuje na,

650
00:28:55,920 --> 00:28:59,290
ako sa môžem pohnúť prstom
k ďalšiemu uzlu v kóde?

651
00:28:59,290 --> 00:29:01,915
No, čo je strúhanka sme
bude nasledovať v tomto prípade?

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

653
00:29:03,464 --> 00:29:04,380
Divákov: [nepočuteľné].

654
00:29:04,380 --> 00:29:05,630
David J. Malan: Jo, tak nabudúce.

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

656
00:29:06,640 --> 00:29:09,824
Takže keď sa vrátim k môjmu
Kód tu, naozaj, ja som

657
00:29:09,824 --> 00:29:12,990
ísť ďalej a povedať ukazovateľ, ktorý
je to len dočasné proměnná-- je to

658
00:29:12,990 --> 00:29:15,320
divný názov, ptr, ale
Je to ako temp--

659
00:29:15,320 --> 00:29:19,234
Chystám sa nastaviť ukazovateľ
rovná ktoréhokoľvek ukazovateľa je--

660
00:29:19,234 --> 00:29:22,150
a znova, to bude
malý kočík pre moment-- bodkou.

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

662
00:29:23,551 --> 00:29:26,550
Inými slovami, ja vezmem môj
prst, ktorý sa ukázal v tomto uzle

663
00:29:26,550 --> 00:29:31,247
tu a budem hovoriť, viete,
čo, pozrite sa na ďalšie pole

664
00:29:31,247 --> 00:29:33,330
a pohybom prsta
bez ohľadu na to ukazujú.

665
00:29:33,330 --> 00:29:35,163
A to bude
opakovať, opakovať, opakovať.

666
00:29:35,163 --> 00:29:37,630
Ale keď sa robí môj prst
prestať robiť vôbec nič?

667
00:29:37,630 --> 00:29:40,095
Akonáhle sa to, čo riadok kódu kopy v?

668
00:29:40,095 --> 00:29:40,970
Divákov: [nepočuteľné]

669
00:29:40,970 --> 00:29:43,060
David J. Malan: Ak je bod, zatiaľ čo
ukazovateľ nerovná null.

670
00:29:43,060 --> 00:29:44,900
Na nejakom mieste môj prst je
bude ukazovať na null

671
00:29:44,900 --> 00:29:47,070
a budem si uvedomiť,
to je koniec tohto zoznamu.

672
00:29:47,070 --> 00:29:48,910
Teraz, to je malý
lož pre jednoduchosť.

673
00:29:48,910 --> 00:29:51,580
Ukazuje sa, že aj keď sme
sa dozvedel túto tečkové notácie

674
00:29:51,580 --> 00:29:55,220
pre stavby, ukazovateľ nie je struct.

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

676
00:29:56,580 --> 00:29:58,350
Stačí, aby sa viac nitpicky.

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

678
00:29:59,720 --> 00:30:01,360
Je to ukazovateľ na uzol.

679
00:30:01,360 --> 00:30:03,120
Nie je to uzol sám.

680
00:30:03,120 --> 00:30:06,650
Keby som nemal hviezdu tu, ukazovateľ
absolutely-- je to uzol.

681
00:30:06,650 --> 00:30:08,650
To je ako týždeň jedno
deklarácia premennej,

682
00:30:08,650 --> 00:30:10,120
aj keď slovo "uzol" je nový.

683
00:30:10,120 --> 00:30:13,860
>> Ale akonáhle sme zaviedli
hviezda, to je teraz ukazovateľ na uzol.

684
00:30:13,860 --> 00:30:17,960
A bohužiaľ nemožno použiť
bodka zápis pre ukazovateľ.

685
00:30:17,960 --> 00:30:21,070
Musíte použiť šípky
zápis, ktorý, prekvapivo,

686
00:30:21,070 --> 00:30:23,470
Je to prvýkrát, kedy nejaký kus
syntax vyzerá intuitívne.

687
00:30:23,470 --> 00:30:25,245
Tento doslova vyzerá ako šíp.

688
00:30:25,245 --> 00:30:26,370
A tak to je dobrá vec.

689
00:30:26,370 --> 00:30:28,995
A tu doslova
Vyzerá ako šíp.

690
00:30:28,995 --> 00:30:31,870
Takže si myslím, že je to la-- vôbec sa mi nepáči
myslím, že som príliš spáchanie tady-- I

691
00:30:31,870 --> 00:30:34,120
si myslí, že je to posledná nový kus
syntaxe budeme vidieť.

692
00:30:34,120 --> 00:30:36,500
A vďakabohu, že je to naozaj
trochu viac intuitívne.

693
00:30:36,500 --> 00:30:40,090
>> Teraz, pre tých z vás, ktorí
by radšej postarom,

694
00:30:40,090 --> 00:30:42,550
môžete stále používať tečkové notácie.

695
00:30:42,550 --> 00:30:45,380
Ale podľa pondelňajšieho
rozhovor, najprv

696
00:30:45,380 --> 00:30:50,530
treba ísť tam, choďte na to
riešiť, a potom prístup k poľu.

697
00:30:50,530 --> 00:30:51,897
Tak to je tiež v poriadku.

698
00:30:51,897 --> 00:30:53,730
A úprimne povedané, je to
trochu pedantská.

699
00:30:53,730 --> 00:30:56,530
Tie doslova hovorí, dereferencia
ukazovateľ a tam.

700
00:30:56,530 --> 00:30:59,320
Potom si n, pole s názvom n.

701
00:30:59,320 --> 00:31:01,370
Ale úprimne povedané, nikto nechce
písať alebo čítať.

702
00:31:01,370 --> 00:31:03,620
A tak svet vynašiel
notácie šípky, ktoré

703
00:31:03,620 --> 00:31:06,980
je ekvivalentná, totožné,
je to len syntaktický cukor.

704
00:31:06,980 --> 00:31:10,570
Takže ozdobný spôsob, ako hovoriť to
vyzerá lepšie, alebo vyzerá jednoduchšie.

705
00:31:10,570 --> 00:31:12,296
>> Takže teraz budem robiť jednu vec.

706
00:31:12,296 --> 00:31:15,420
Budem hovoriť "pauzu", akonáhle som
Zistili, že je tak nemám udržať ju hľadajú.

707
00:31:15,420 --> 00:31:17,620
Ale to je podstata
vyhľadávacie funkcie.

708
00:31:17,620 --> 00:31:21,710
Ale je to oveľa jednoduchšie, v
koniec, a nie prejsť kód.

709
00:31:21,710 --> 00:31:25,570
To je skutočne formálna realizácia
hľadanie v dnešnej distribúcie kóde.

710
00:31:25,570 --> 00:31:30,530
Trúfam si povedať, že vložka nie je
obzvlášť zábavné prejsť

711
00:31:30,530 --> 00:31:33,180
vizuálne, ani ich mazať, a to aj
aj keď na konci dňa

712
00:31:33,180 --> 00:31:35,460
sa redukuje na pomerne
jednoduché heuristiky.

713
00:31:35,460 --> 00:31:36,330
>> Tak poďme na to.

714
00:31:36,330 --> 00:31:39,250
Ak budete humor ma tu, som
prináša veľa stresu gule.

715
00:31:39,250 --> 00:31:40,620
Priniesol som veľa čísel.

716
00:31:40,620 --> 00:31:46,562
A mohli by sme získať len niekoľko dobrovoľníkov
reprezentovať 9, 17, 20, 22, 29, a 34?

717
00:31:46,562 --> 00:31:48,270
Takže v podstate každý
kto je tu dnes.

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

719
00:31:50,170 --> 00:31:52,760
To bol jeden, dva, tri,
štyri, päť, šesť ľudí.

720
00:31:52,760 --> 00:31:55,740
A ja som bol požiadaný, aby jít-- vidieť, no
jeden na zadnej strane zvyšuje svoje ruky.

721
00:31:55,740 --> 00:32:01,910
OK, jeden, dva, tri, štyri,
five-- dovoľte mi načíta balance-- šesť.

722
00:32:01,910 --> 00:32:03,051
OK, šesť poď hore.

723
00:32:03,051 --> 00:32:04,050
Budeme potrebovať ďalších ľudí.

724
00:32:04,050 --> 00:32:05,460
Priniesli sme ďalšie stres gule.

725
00:32:05,460 --> 00:32:08,200
A ak by ste mohol, pre
len na chvíľu, linka

726
00:32:08,200 --> 00:32:10,490
Sami si jednoducho
páči tento obrázok tu.

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

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

729
00:32:15,959 --> 00:32:17,125
Poďme sa pozrieť, Ako sa voláte?

730
00:32:17,125 --> 00:32:17,550
>> DIVÁKOV: Andrew.

731
00:32:17,550 --> 00:32:18,800
>> David J. Malan: Andrew,
ste číslo 9.

732
00:32:18,800 --> 00:32:19,540
Teší ma.

733
00:32:19,540 --> 00:32:20,400
Tu to máš.

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

735
00:32:21,593 --> 00:32:22,176
DIVÁKOV: Len.

736
00:32:22,176 --> 00:32:22,662
David J. Malan: Len.

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

738
00:32:23,162 --> 00:32:23,765
Číslo 17.

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

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

741
00:32:25,450 --> 00:32:26,400
>> Divákov: Som Julia.

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

743
00:32:26,980 --> 00:32:27,545
Číslo 20.

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

745
00:32:28,507 --> 00:32:29,340
DIVÁKOV: Christian.

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

747
00:32:30,715 --> 00:32:31,541
Číslo 22.

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

749
00:32:32,040 --> 00:32:32,649
>> DIVÁKOV: JP.

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

751
00:32:33,440 --> 00:32:34,880
Číslo 29.

752
00:32:34,880 --> 00:32:37,080
Takže choďte do toho a dostať v-- Uh oh.

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

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

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

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

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

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

759
00:32:42,390 --> 00:32:43,682
Má niekto značku?

760
00:32:43,682 --> 00:32:44,890
Divákov: Mám Sharpie.

761
00:32:44,890 --> 00:32:45,660
David J. Malan: Máš 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
A má niekto kus papiera?

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

766
00:32:51,562 --> 00:32:52,270
Uložiť prednášku.

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

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

769
00:32:55,362 --> 00:32:56,320
Divákov: Máme to.

770
00:32:56,320 --> 00:32:57,600
David J. Malan: Máme to?

771
00:32:57,600 --> 00:32:58,577
Dobre, ďakujem.

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

773
00:33:01,380 --> 00:33:02,520
Ideme na to.

774
00:33:02,520 --> 00:33:03,582
Bolo to od vás?

775
00:33:03,582 --> 00:33:04,540
Práve ste zachránil deň.

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

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

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

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

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

781
00:33:13,360 --> 00:33:14,890
Aj chybne 29, ale OK.

782
00:33:14,890 --> 00:33:15,720
Len do toho.

783
00:33:15,720 --> 00:33:18,114
Dobre, dám vám
pero späť na okamih.

784
00:33:18,114 --> 00:33:19,280
Takže máme týchto ľudí tu.

785
00:33:19,280 --> 00:33:20,330
Poďme sa jeden druhého.

786
00:33:20,330 --> 00:33:23,750
Gabe, chceš hrať
prvý prvok tu?

787
00:33:23,750 --> 00:33:25,705
Musíme vás upozorniť
v týchto jemných ľudí.

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

789
00:33:26,930 --> 00:33:31,030
Takže 9, 17, 20, 22, triediť
z 29, a potom 34.

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

791
00:33:32,160 --> 00:33:33,325
Sme stratili niekoho?

792
00:33:33,325 --> 00:33:33,950
Mám 34.

793
00:33:33,950 --> 00:33:36,730
Kde udělal-- OK, kto chce byť 34?

794
00:33:36,730 --> 00:33:37,605
OK, poď hore, 34.

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

796
00:33:39,280 --> 00:33:41,220
Tak jo, to bude
stojí za vyvrcholenie.

797
00:33:41,220 --> 00:33:41,550
Ako sa voláte?

798
00:33:41,550 --> 00:33:42,040
>> DIVÁKOV: Peter.

799
00:33:42,040 --> 00:33:43,456
>> David J. Malan: Peter, poď hore.

800
00:33:43,456 --> 00:33:46,810
Dobre, takže tu je
Celá partia uzlov.

801
00:33:46,810 --> 00:33:49,060
Každý z vás predstavuje
jeden z týchto obdĺžnikov.

802
00:33:49,060 --> 00:33:51,930
A Gabe, trochu zvláštne
človek sa predstavuje ako prvý.

803
00:33:51,930 --> 00:33:54,850
Takže jeho ukazovateľ je o niečo menšia
na obrazovke, než všetci ostatní.

804
00:33:54,850 --> 00:33:58,120
A v tomto prípade, každý po ľavej strane
ruky, bude buď smerovať nadol,

805
00:33:58,120 --> 00:34:01,085
v dôsledku čoho sa null, tak
len absencia ukazovateľa,

806
00:34:01,085 --> 00:34:03,210
alebo to bude ukazovať
v uzle vedľa vás.

807
00:34:03,210 --> 00:34:05,440
>> Takže teraz, keď sa zdobia
sami ako na obrázku

808
00:34:05,440 --> 00:34:07,585
tú, choďte do toho a bod
na seba, s Gabe

809
00:34:07,585 --> 00:34:11,030
najmä ukazuje na
číslo 9 reprezentovať zoznam.

810
00:34:11,030 --> 00:34:14,050
OK, a číslo 34, vaša ľavá ruka
by mala byť len ukázal na podlahu.

811
00:34:14,050 --> 00:34:15,750
>> OK, takže to je previazaný zoznam.

812
00:34:15,750 --> 00:34:17,580
Tak toto je scenár v pochybnosť.

813
00:34:17,580 --> 00:34:20,210
A skutočne, to je reprezentatívna
triedy problémov

814
00:34:20,210 --> 00:34:21,929
, Že by sa mohli pokúsiť riešiť s kódom.

815
00:34:21,929 --> 00:34:25,020
Ak chcete nakoniec vložiť
nový prvok do zoznamu.

816
00:34:25,020 --> 00:34:27,494
V tomto prípade budeme
skúste vložiť číslo 55.

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

818
00:34:28,500 --> 00:34:30,860
Ale tam to bude
rôzne prípady, aby zvážila.

819
00:34:30,860 --> 00:34:34,409
A skutočne, to bude jeden
z big-obraz takeaways tu, je,

820
00:34:34,409 --> 00:34:35,659
Aké sú rôzne prípady.

821
00:34:35,659 --> 00:34:39,120
Aké sú rôzne, ak podmienky, alebo
vetvy, ktoré váš program mohol mať?

822
00:34:39,120 --> 00:34:42,024
>> No, číslo sa snažíte
vložka, ktorá dnes už vieme, že je 55,

823
00:34:42,024 --> 00:34:44,650
ale ak ste nevedeli,
v predstihu, trúfam si tvrdiť,

824
00:34:44,650 --> 00:34:47,840
spadá do najmenej troch
možné situácie.

825
00:34:47,840 --> 00:34:49,717
Tam, kde by mohol byť nový prvok?

826
00:34:49,717 --> 00:34:51,050
Divákov: A koniec alebo stred.

827
00:34:51,050 --> 00:34:54,150
David J. Malan: Na konci, v
strednej, alebo na začiatku.

828
00:34:54,150 --> 00:34:56,650
Tak som sa tvrdí, že je aspoň
tri problémy musíme riešiť.

829
00:34:56,650 --> 00:34:58,691
Poďme si vybrať, čo je potrebné
pravdepodobne najjednoduchšie

830
00:34:58,691 --> 00:35:01,090
jeden, kde nový prvok
patrí na začiatku.

831
00:35:01,090 --> 00:35:04,040
Takže budem mať kód úplne
ako je vyhľadávanie, ktoré som napísal.

832
00:35:04,040 --> 00:35:07,670
A ja budem mať ptr, ktoré
Budem reprezentovať tu s mojím prstom,

833
00:35:07,670 --> 00:35:08,370
ako obvykle.

834
00:35:08,370 --> 00:35:12,430
>> A pamätajte si, akú hodnotu
sme inicializovať ptr na?

835
00:35:12,430 --> 00:35:15,300
Tak sme sa inicializuje ju spočiatku null.

836
00:35:15,300 --> 00:35:16,410

837
00:35:16,410 --> 00:35:19,770
Ale to, čo sme urobili, akonáhle sme
boli v našej funkciu vyhľadávania?

838
00:35:19,770 --> 00:35:20,940

839
00:35:20,940 --> 00:35:24,870
Vydali sme sa rovná prvej,
čo neznamená, že robí.

840
00:35:24,870 --> 00:35:25,890

841
00:35:25,890 --> 00:35:30,570
Ak mám nastaviť prvý ptr rovno, čo
by moja ruka naozaj ukazuje na?

842
00:35:30,570 --> 00:35:31,070
Presne tak.

843
00:35:31,070 --> 00:35:33,290
Takže ak Gabe a ja sa chystáte
byť rovnaké hodnoty tu

844
00:35:33,290 --> 00:35:34,760
Potrebujeme ako bodu číslo 9.

845
00:35:34,760 --> 00:35:36,420
>> Tak toto bol začiatok nášho príbehu.

846
00:35:36,420 --> 00:35:38,700
A teraz je to len jednoduchý,
aj keď syntax je nové.

847
00:35:38,700 --> 00:35:40,580
Koncepčne je to len lineárne hľadanie.

848
00:35:40,580 --> 00:35:42,750
Je 55 rovná 9?

849
00:35:42,750 --> 00:35:45,559
Alebo skôr, povedzme, menej ako 9.

850
00:35:45,559 --> 00:35:47,600
Pretože sa snažím
prísť na to, kam umiestniť 55.

851
00:35:47,600 --> 00:35:51,270
Menej ako 9, menej ako 17, menej
ako 20, menej ako 22, menej ako 29,

852
00:35:51,270 --> 00:35:52,510
menej ako 34, nie.

853
00:35:52,510 --> 00:35:55,080
Takže teraz sme v prípade
jeden z najmenej troch.

854
00:35:55,080 --> 00:35:59,910
>> Ak chcem vložiť 55 sem, čo
riadky kódu potrebné sa dostať popravený?

855
00:35:59,910 --> 00:36:01,890
Ako to obrázok
ľudia potrebujú zmeniť?

856
00:36:01,890 --> 00:36:03,181
Čo mám robiť s mojou ľavú ruku?

857
00:36:03,181 --> 00:36:04,530

858
00:36:04,530 --> 00:36:07,360
To by malo byť null spočiatku,
preto, že som na konci zoznamu.

859
00:36:07,360 --> 00:36:09,318
A čo by sa stalo,
tu s Petrom, že?

860
00:36:09,318 --> 00:36:10,520

861
00:36:10,520 --> 00:36:12,430
Očividne bude ukazovať na mňa.

862
00:36:12,430 --> 00:36:15,580
Takže tvrdím, že je to najmenej dva riadky
kódu v ukážkovom kóde odo dneška

863
00:36:15,580 --> 00:36:18,570
že to bude na vykonanie tohto
Scenár pridanie 55 na chvoste.

864
00:36:18,570 --> 00:36:20,950
A mohol by som mať niekoho hop
a práve predstavuje 55?

865
00:36:20,950 --> 00:36:22,200
Dobre, že ste nový 55.

866
00:36:22,200 --> 00:36:23,580

867
00:36:23,580 --> 00:36:27,054
>> Takže teraz, čo keď ďalšie
scenár príde,

868
00:36:27,054 --> 00:36:29,720
a chceme vložiť na
na začiatku alebo na čele tohto zoznamu?

869
00:36:29,720 --> 00:36:31,100
A aké je vaše meno, číslo 55?

870
00:36:31,100 --> 00:36:31,420
>> DIVÁKOV: Jack.

871
00:36:31,420 --> 00:36:32,295
>> David J. Malan: Jack?

872
00:36:32,295 --> 00:36:33,585
OK, rád ťa spoznávam.

873
00:36:33,585 --> 00:36:34,210
Vitajte na palube.

874
00:36:34,210 --> 00:36:36,640
Takže teraz budeme
vložiť, povedzme, číslo 5.

875
00:36:36,640 --> 00:36:39,840
Tu je druhý prípad
tri sme prišli s pred.

876
00:36:39,840 --> 00:36:43,050
Takže v prípade, 5 patrí na začiatku,
poďme sa pozrieť, ako sme zistili, že von.

877
00:36:43,050 --> 00:36:46,310
Aj inicializovať svoj ptr
ukazovateľ opäť číslo 9.

878
00:36:46,310 --> 00:36:49,140
A uvedomil som si, oh, 5 je menšia ako 9.

879
00:36:49,140 --> 00:36:50,880
Takže opraviť tento obrázok pre nás.

880
00:36:50,880 --> 00:36:54,820
Čí ruky, Gabe či Davida
nebo--, čo je číslo deväť meno?

881
00:36:54,820 --> 00:36:55,740
>> DIVÁKOV: Len.

882
00:36:55,740 --> 00:36:58,406
>> David J. Malan: Jenin hands--
ktoré v našich rukách je potrebné zmeniť?

883
00:36:58,406 --> 00:36:58,905

884
00:36:58,905 --> 00:37:00,970
OK, takže Gabe poukazuje na to, čo teraz?

885
00:37:00,970 --> 00:37:01,640
Na mňa.

886
00:37:01,640 --> 00:37:02,750
Som nový uzol.

887
00:37:02,750 --> 00:37:04,870
Tak som si len trochu pohybu
tu vidieť vizuálne.

888
00:37:04,870 --> 00:37:06,435
A medzitým čo som zdôrazniť, že?

889
00:37:06,435 --> 00:37:07,910

890
00:37:07,910 --> 00:37:09,020
Napriek tomu, kde som ukázal.

891
00:37:09,020 --> 00:37:10,000
Tak takto to je.

892
00:37:10,000 --> 00:37:13,717
Takže naozaj len jeden riadok kódu opravy
tento konkrétny problém, by sa mohlo zdať.

893
00:37:13,717 --> 00:37:14,800
Dobre, takže to je dobré.

894
00:37:14,800 --> 00:37:17,580
A môže niekto byť zástupný symbol pre 5?

895
00:37:17,580 --> 00:37:18,080
Poď hore.

896
00:37:18,080 --> 00:37:20,270

897
00:37:20,270 --> 00:37:21,320
Budeme vám nabudúce.

898
00:37:21,320 --> 00:37:24,280
>> Dobre, takže teď-- a
Mimochodom, názvy

899
00:37:24,280 --> 00:37:28,510
Nebudem robiť explicitné zmienku o práve
Teraz, pred ukazovateľ, predchodca ukazovateľ

900
00:37:28,510 --> 00:37:31,260
a nový ukazovateľ, ktorý je
vzhľadom k tomu len mená

901
00:37:31,260 --> 00:37:35,280
v ukážkovom kóde na ukazovateli alebo
ruky, že to trochu polohovacie okolo.

902
00:37:35,280 --> 00:37:36,060
Ako sa voláte?

903
00:37:36,060 --> 00:37:36,700
>> DIVÁKOV: Christine.

904
00:37:36,700 --> 00:37:37,100
>> David J. Malan: Christine.

905
00:37:37,100 --> 00:37:38,090
Vitajte na palube.

906
00:37:38,090 --> 00:37:42,180
Dobre, takže uvažujme teraz
trochu nepríjemné scenár,

907
00:37:42,180 --> 00:37:46,350
čím Chcem vložiť
niečo ako 26 do toho.

908
00:37:46,350 --> 00:37:47,090
20?

909
00:37:47,090 --> 00:37:47,590
Čo je?

910
00:37:47,590 --> 00:37:50,510
Tieto jsou-- dobrú vec máme toto pero.

911
00:37:50,510 --> 00:37:51,955
V poriadku, 20.

912
00:37:51,955 --> 00:37:53,640

913
00:37:53,640 --> 00:37:57,570
Ak sa niekto mohol dostať ešte kúsok
papier pripravený, len case-- v poriadku.

914
00:37:57,570 --> 00:37:58,370
Oh, zaujímavé.

915
00:37:58,370 --> 00:37:59,760

916
00:37:59,760 --> 00:38:02,390
No to je príklad
prednáškového chyby.

917
00:38:02,390 --> 00:38:03,894
OK, takže to, čo sa voláš?

918
00:38:03,894 --> 00:38:04,560
DIVÁKOV: Julia.

919
00:38:04,560 --> 00:38:07,559
David J. Malan: Julia, môžete pop
, A predstierať, že si nikdy nebol?

920
00:38:07,559 --> 00:38:09,040
OK, to sa nikdy nestalo.

921
00:38:09,040 --> 00:38:09,680
Ďakujem vám.

922
00:38:09,680 --> 00:38:12,180
Takže predpokladám, že chceme vložiť
Julia do tohto prepojeného zoznamu.

923
00:38:12,180 --> 00:38:13,780
Je číslo 20.

924
00:38:13,780 --> 00:38:15,530
A samozrejme, že je
bude patriť k

925
00:38:15,530 --> 00:38:17,521
begin-- neukazujú na nič zatiaľ.

926
00:38:17,521 --> 00:38:20,020
Takže vaša ruka môže byť trochu
dole null alebo nejaké odpadky hodnotu.

927
00:38:20,020 --> 00:38:21,210
Poďme povedať, rýchly príbeh.

928
00:38:21,210 --> 00:38:22,980
Som ukázal na číslo 5 tejto dobe.

929
00:38:22,980 --> 00:38:23,880
Potom som skontrolovať 9.

930
00:38:23,880 --> 00:38:25,130
Potom som skontrolovať 17.

931
00:38:25,130 --> 00:38:26,247
Potom som skontrolovať 22.

932
00:38:26,247 --> 00:38:27,650

933
00:38:27,650 --> 00:38:32,485
A ja si uvedomujem, ooh, Julia
musí ísť pred 22.

934
00:38:32,485 --> 00:38:33,580

935
00:38:33,580 --> 00:38:34,660
Takže to, čo sa musí stať?

936
00:38:34,660 --> 00:38:35,786

937
00:38:35,786 --> 00:38:36,910
Čí ruky je potrebné zmeniť?

938
00:38:36,910 --> 00:38:38,360
Julie, moje, nebo--
čo sa voláš?

939
00:38:38,360 --> 00:38:39,230
>> DIVÁKOV: Christian.

940
00:38:39,230 --> 00:38:40,060
>> David J. Malan: Christian, alebo?

941
00:38:40,060 --> 00:38:40,560
>> DIVÁKOV: Andy.

942
00:38:40,560 --> 00:38:40,905
>> David J. Malan: Andy.

943
00:38:40,905 --> 00:38:41,654
Christian, alebo Andy?

944
00:38:41,654 --> 00:38:44,280

945
00:38:44,280 --> 00:38:45,690
Andy je potrebné poukázať 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 poriadku.

949
00:38:47,840 --> 00:38:48,960
Tak Andy, chceš ukázať na Julia?

950
00:38:48,960 --> 00:38:50,120
Ale počkajte chvíľku.

951
00:38:50,120 --> 00:38:53,260
V príbehu tak ďaleko,
Ja som tak nejako jedno

952
00:38:53,260 --> 00:38:56,800
na starosti, v tom zmysle, že
ukazovateľ je vec, ktorá je

953
00:38:56,800 --> 00:38:57,850
pohybujúce sa v zozname.

954
00:38:57,850 --> 00:39:00,800
Mohli by sme mať názov pre Andyho, ale
nie je premenná s názvom Andy.

955
00:39:00,800 --> 00:39:04,320
Iba iné premenné máme, je
Prvý, kto zastupuje Gabe.

956
00:39:04,320 --> 00:39:07,690
>> Takže to je vlastne dôvod, prečo sa tak
Zatiaľ sme to potrebovali to.

957
00:39:07,690 --> 00:39:10,846
Ale teraz na obrazovke je
znovu zmieniť o pred ukazovatele.

958
00:39:10,846 --> 00:39:11,970
Tak nechaj ma byť konkrétnejší.

959
00:39:11,970 --> 00:39:14,820
Ak je to ukazovateľ, mal som lepší
trochu inteligentnejšie

960
00:39:14,820 --> 00:39:15,950
o mojom iteráciu.

961
00:39:15,950 --> 00:39:19,580
Ak vám nevadí, že môj prechádza tu
opäť ukázal tu, ukazuje tu.

962
00:39:19,580 --> 00:39:22,500
Ale dovoľte mi mať pred ukazovateľ,
predchodca ukazovateľ, ktorý je

963
00:39:22,500 --> 00:39:24,740
druh ukazuje na
element som bola na.

964
00:39:24,740 --> 00:39:27,330
Takže keď idem tu a teraz
Moja ľavá ruka aktualizácie.

965
00:39:27,330 --> 00:39:29,370
Keď idem tu moja ľavá aktualizácie ručne.

966
00:39:29,370 --> 00:39:33,090
A teraz mám nielen ukazovateľ
prvok, ktorý ide po Julii,

967
00:39:33,090 --> 00:39:36,300
Stále mám ukazovateľ
Andy, prvok pred.

968
00:39:36,300 --> 00:39:39,430
Takže budete mať prístup, v podstate,
strúhanka, ak chcete,

969
00:39:39,430 --> 00:39:41,500
na všetkých potrebných ukazovateľov.

970
00:39:41,500 --> 00:39:43,710
>> Takže keď som ukázal na
Andy a ja som tiež ukázal

971
00:39:43,710 --> 00:39:47,105
u kresťana, ktorého ruky
by teraz mala byť zdôraznené inde?

972
00:39:47,105 --> 00:39:48,770

973
00:39:48,770 --> 00:39:51,960
Takže Andy teraz možno poukázať na Júliu.

974
00:39:51,960 --> 00:39:54,460
Julia sa teraz poukázať na Christiana.

975
00:39:54,460 --> 00:39:56,950
Vzhľadom k tomu, že môžete kopírovať moje
pravá ruka je ukazovateľ.

976
00:39:56,950 --> 00:40:00,044
A to vám účinne prenáša
späť na toto miesto tu.

977
00:40:00,044 --> 00:40:02,460
Takže stručne povedané, aj keď toto
nás berie druh navždy

978
00:40:02,460 --> 00:40:04,510
skutočne aktualizovať
spájať zoznam, realizovať

979
00:40:04,510 --> 00:40:06,580
že operácia
sú relatívne jednoduché.

980
00:40:06,580 --> 00:40:10,030
Je to z jedného, ​​dva, tri
riadkov kódu nakoniec.

981
00:40:10,030 --> 00:40:12,780
Ale omotal okolo tých
riadkov kódu pravdepodobne

982
00:40:12,780 --> 00:40:16,350
je trochu logiky, ktorá účinne
kladie otázku, kde to sme?

983
00:40:16,350 --> 00:40:18,970
Sme na začiatku,
stredná, alebo koniec?

984
00:40:18,970 --> 00:40:21,890
>> Teraz, tam sú určite iné
operácie môžeme realizovať.

985
00:40:21,890 --> 00:40:24,880
A tieto fotky tu len opísať
to, čo sme práve robili s ľuďmi.

986
00:40:24,880 --> 00:40:26,080
Čo je odstránenie?

987
00:40:26,080 --> 00:40:30,650
Ak chcem, napríklad,
odstrániť číslo 34 alebo 55,

988
00:40:30,650 --> 00:40:34,680
Možno mám rovnaký druh kódu,
ale budem potrebovať jeden alebo dva kroky.

989
00:40:34,680 --> 00:40:36,110
Vzhľadom k tomu, čo je nové?

990
00:40:36,110 --> 00:40:40,460
Ak mám odstrániť niekoho, kto na konci,
ako číslo 55 a 34,

991
00:40:40,460 --> 00:40:42,995
čo má tiež zmeniť, ako to urobiť?

992
00:40:42,995 --> 00:40:44,870
Musím sa evict--
čo sa voláš?

993
00:40:44,870 --> 00:40:45,380
>> DIVÁKOV: Jack.

994
00:40:45,380 --> 00:40:46,255
>> David J. Malan: Jack.

995
00:40:46,255 --> 00:40:49,770
Musím nielen evict-- zadarmo Jack,
tak doslova Volajte zadarmo Jack, alebo aspoň

996
00:40:49,770 --> 00:40:53,530
tam ukazovateľ taky, ale teraz
to, čo sa musí zmeniť s Petrom?

997
00:40:53,530 --> 00:40:55,510
Jeho ruka lepší štart smerom nadol.

998
00:40:55,510 --> 00:40:59,300
Pretože akonáhle som volať zadarmo na
Jacku, či Peter je stále ukazuje na Jacka

999
00:40:59,300 --> 00:41:02,530
a preto, aby kríženie
Zoznam a prístup tohto ukazovateľa,

1000
00:41:02,530 --> 00:41:05,650
to je, keď náš starý priateľ segmentácie
Porucha môže skutočne kopať do.

1001
00:41:05,650 --> 00:41:07,860
Vzhľadom k tomu, že sme vzhľadom na
pamäť späť na Jacka.

1002
00:41:07,860 --> 00:41:10,760
>> Môžete tam zostať
nešikovne len na chvíľu.

1003
00:41:10,760 --> 00:41:13,410
Pretože máme len pár
finálne operácie, aby zvážila.

1004
00:41:13,410 --> 00:41:15,600
Odstránenie hlavy zoznamu,
alebo beginning-- a ten je

1005
00:41:15,600 --> 00:41:16,349
trochu nepríjemné.

1006
00:41:16,349 --> 00:41:19,640
Vzhľadom k tomu, musíme vedieť, že Gabe
je tak trochu zvláštne v tomto programe.

1007
00:41:19,640 --> 00:41:21,440
Pretože v skutočnosti, má vlastný ukazovateľ.

1008
00:41:21,440 --> 00:41:24,860
On nie je len sa ukázal na,
rovnako ako takmer všetci ostatní tu.

1009
00:41:24,860 --> 00:41:28,112
>> Takže keď v čele zoznamu je
odstránená, ktorého ruky je potrebné zmeniť práve teraz?

1010
00:41:28,112 --> 00:41:29,070
Ako sa voláš?

1011
00:41:29,070 --> 00:41:29,450
>> DIVÁKOV: Christine.

1012
00:41:29,450 --> 00:41:31,408
>> David J. Malan: Som hrozný
na mená, zrejme.

1013
00:41:31,408 --> 00:41:34,011
Takže Christine a Gabe,
ktorého ruke je potrebné zmeniť

1014
00:41:34,011 --> 00:41:36,510
kedy sa snažíme odstrániť Christine,
číslo 5, z obrázku?

1015
00:41:36,510 --> 00:41:37,550

1016
00:41:37,550 --> 00:41:38,820
OK, tak sa poďme robiť Gabe.

1017
00:41:38,820 --> 00:41:40,950
Gabe sa deje na bod,
Možno predpokladať, že u čísla 9.

1018
00:41:40,950 --> 00:41:42,230

1019
00:41:42,230 --> 00:41:44,642
Ale čo ďalšie by sa malo stať?

1020
00:41:44,642 --> 00:41:46,600
Divákov: Christine by
byť null [nepočuteľné].

1021
00:41:46,600 --> 00:41:50,244
David J. Malan: OK, mali by sme asi
make-- Počul som, "null" niekde inde.

1022
00:41:50,244 --> 00:41:51,410
Divákov: Null a oslobodiť ju.

1023
00:41:51,410 --> 00:41:51,855
David J. Malan: Null čo?

1024
00:41:51,855 --> 00:41:53,074
Divákov: Null a oslobodiť ju.

1025
00:41:53,074 --> 00:41:54,490
David J. Malan: Null a oslobodiť ju.

1026
00:41:54,490 --> 00:41:55,422
Takže je to veľmi jednoduché.

1027
00:41:55,422 --> 00:41:58,380
A je to perfektné, že si teraz nejako
zo tam stál, ktorá nepatrí.

1028
00:41:58,380 --> 00:42:00,430
Vzhľadom k tomu, že ste bol
oddelená od zoznamu.

1029
00:42:00,430 --> 00:42:02,820
Vy ste skutočne boli
osirel zo zoznamu.

1030
00:42:02,820 --> 00:42:07,770
A tak sme mali lepšie volať zadarmo teraz
Christine, aby tú spomienku späť.

1031
00:42:07,770 --> 00:42:10,240
Inak zakaždým, keď
odstrániť uzol zo zoznamu

1032
00:42:10,240 --> 00:42:14,230
by sme mohli byť robiť zoznam
kratšie, ale nie v skutočnosti znižuje

1033
00:42:14,230 --> 00:42:15,096
veľkosť v pamäti.

1034
00:42:15,096 --> 00:42:17,720
A tak, ak budeme držať pridávanie a
pridávať, pridávať veci do zoznamu,

1035
00:42:17,720 --> 00:42:19,280
Môj počítač sa môže dostať pomalší
a pomalší a pomalší,

1036
00:42:19,280 --> 00:42:21,740
pretože bežím z
pamäť, aj keď nie som v skutočnosti

1037
00:42:21,740 --> 00:42:25,580
pomocou Christine bajtov
pamäti ešte.

1038
00:42:25,580 --> 00:42:28,500
>> Takže na konci sú iné
scenáre, z course-- odstránenie

1039
00:42:28,500 --> 00:42:30,640
v stredu, odstránenie
Na konci, ako sme videli.

1040
00:42:30,640 --> 00:42:32,348
Ale ešte zaujímavejšie
Teraz je

1041
00:42:32,348 --> 00:42:34,770
bude uvažovať presne
čo je doba chodu je.

1042
00:42:34,770 --> 00:42:36,640
Takže nielen môžete nechať
kúsky papiera, v prípade, Gabe,

1043
00:42:36,640 --> 00:42:38,640
by vám nevadilo dať
každý stres loptičku.

1044
00:42:38,640 --> 00:42:42,100
Ďakujem moc nášho prepojeného zoznamu
dobrovoľníkov tu, keby si mohol.

1045
00:42:42,100 --> 00:42:45,320
>> [APPLAUSE]

1046
00:42:45,320 --> 00:42:46,700
>> David J. Malan: Dobre.

1047
00:42:46,700 --> 00:42:51,110
Takže pár analytické
otázok, potom, keby som mohol.

1048
00:42:51,110 --> 00:42:59,670
Sme videl tento zápis,
veľké O a omega, horná hranica

1049
00:42:59,670 --> 00:43:02,520
a dolná hranica na
doba chodu nejakého algoritmu.

1050
00:43:02,520 --> 00:43:04,950
Takže uvažujme len
pár otázok.

1051
00:43:04,950 --> 00:43:07,090
>> Raz, a to povedal, že sme
predtým, čo je beh

1052
00:43:07,090 --> 00:43:10,647
Doba hľadania
zoznam, pokiaľ ide o veľké O?

1053
00:43:10,647 --> 00:43:13,480
Čo je to horná hranica na prevádzku
Doba hľadania spájať zoznam

1054
00:43:13,480 --> 00:43:16,340
ako realizovať naše dobrovoľníkmi tu?

1055
00:43:16,340 --> 00:43:17,820
Je to veľký O n, lineárne.

1056
00:43:17,820 --> 00:43:20,630
Vzhľadom k tomu, v najhoršom prípade,
prvok, ako je 55,

1057
00:43:20,630 --> 00:43:23,830
môžeme hľadať, kde by mohla byť
Jack, úplne na konci.

1058
00:43:23,830 --> 00:43:28,250
A bohužiaľ, na rozdiel od mnohých
nemôžeme dostať chuť tentoraz.

1059
00:43:28,250 --> 00:43:31,820
Aj napriek tomu, že všetci naši ľudia boli
radené od malých prvkov, 5,

1060
00:43:31,820 --> 00:43:35,900
celú cestu až do väčšieho prvku,
55, je to zvyčajne dobrá vec.

1061
00:43:35,900 --> 00:43:38,815
Ale to, čo robí tento predpoklad
už nám umožňujú robiť?

1062
00:43:38,815 --> 00:43:39,775

1063
00:43:39,775 --> 00:43:40,650
Divákov: [nepočuteľné]

1064
00:43:40,650 --> 00:43:40,920
David J. Malan: znova, povedz?

1065
00:43:40,920 --> 00:43:41,800
Divákov: Random prístup.

1066
00:43:41,800 --> 00:43:43,049
David J. Malan: s náhodným prístupom.

1067
00:43:43,049 --> 00:43:46,330
A zase to znamená, že môžeme bez
ďalej používať slabý nuly, intuície,

1068
00:43:46,330 --> 00:43:49,365
a samozrejmosť použitie binárne
vyhľadávanie a rozdeľ a panuj.

1069
00:43:49,365 --> 00:43:51,240
Vzhľadom k tomu, aj keď sme
ľudia mohli samozrejme

1070
00:43:51,240 --> 00:43:54,610
vidieť, že Andy a Christian boli
zhruba v polovici zoznamu,

1071
00:43:54,610 --> 00:43:57,670
Vieme len, že ako
Počítač zbieraním na zoznam

1072
00:43:57,670 --> 00:43:59,029
od samého začiatku.

1073
00:43:59,029 --> 00:44:00,570
Tak sme sa vzdali, že náhodný prístup.

1074
00:44:00,570 --> 00:44:04,380
>> Tak veľký O n je teraz horný
viazané na nášho vyhľadávacieho času.

1075
00:44:04,380 --> 00:44:07,920
Čo omega nášho vyhľadávania?

1076
00:44:07,920 --> 00:44:11,535
Čo je dolná hranica na vyhľadávanie
pre nejaké číslo v tomto zozname?

1077
00:44:11,535 --> 00:44:12,410
Divákov: [nepočuteľné]

1078
00:44:12,410 --> 00:44:13,040
David J. Malan: znova, povedz?

1079
00:44:13,040 --> 00:44:13,420
DIVÁKOV: One.

1080
00:44:13,420 --> 00:44:13,800
David J. Malan: One.

1081
00:44:13,800 --> 00:44:14,760
Takže časová konštanta.

1082
00:44:14,760 --> 00:44:17,020
V najlepšom prípade, Christine
naozaj na začiatku zoznamu.

1083
00:44:17,020 --> 00:44:19,020
A my hľadáme
číslo 5, takže sme ju našli.

1084
00:44:19,020 --> 00:44:19,787
Takže žiadny veľký problém.

1085
00:44:19,787 --> 00:44:22,370
Ale to musí byť na
začiatku zoznamu v tomto prípade.

1086
00:44:22,370 --> 00:44:23,745
Čo asi niečo ako Delete?

1087
00:44:23,745 --> 00:44:24,717

1088
00:44:24,717 --> 00:44:26,300
Čo keď chcete zmazať prvok?

1089
00:44:26,300 --> 00:44:29,200
Čo je horná hranica a dolná hranica
o zmazanie niečo z spojená

1090
00:44:29,200 --> 00:44:29,699
Zoznam?

1091
00:44:29,699 --> 00:44:35,195

1092
00:44:35,195 --> 00:44:36,070
Divákov: [nepočuteľné]

1093
00:44:36,070 --> 00:44:36,420
David J. Malan: znova, povedz?

1094
00:44:36,420 --> 00:44:37,067
DIVÁKOV: n.

1095
00:44:37,067 --> 00:44:38,900
David J. Malan: n je
naozaj horná hranica.

1096
00:44:38,900 --> 00:44:41,700
Vzhľadom k tomu, v najhoršom prípade sa snažíme
odstrániť Jacka, ako sme to urobil.

1097
00:44:41,700 --> 00:44:43,050
Je to úplne na konci.

1098
00:44:43,050 --> 00:44:45,419
Nám trvá celú večnosť, alebo
n kroky, aby ho našli.

1099
00:44:45,419 --> 00:44:46,460
Tak to je horná hranica.

1100
00:44:46,460 --> 00:44:47,430
To je lineárna, iste.

1101
00:44:47,430 --> 00:44:50,970
A v najlepšom prípade doba chodu alebo
dolná hranica v najlepšom prípade

1102
00:44:50,970 --> 00:44:51,975
by byť konštantný čas.

1103
00:44:51,975 --> 00:44:54,600
Vzhľadom k tomu, že by sme sa snaží odstrániť
Christine, a my len mať šťastie

1104
00:44:54,600 --> 00:44:55,558
ona je na začiatku.

1105
00:44:55,558 --> 00:44:56,350
Teraz počkajte chvíľku.

1106
00:44:56,350 --> 00:44:59,370
Gabe bol tiež na začiatku,
a tiež sme museli aktualizovať Gabe.

1107
00:44:59,370 --> 00:45:01,150
Takže to nebol len jeden krok.

1108
00:45:01,150 --> 00:45:04,210
Tak to je naozaj konštantná
Doba, v najlepšom prípade,

1109
00:45:04,210 --> 00:45:06,345
na odstránenie najmenší prvok?

1110
00:45:06,345 --> 00:45:07,360

1111
00:45:07,360 --> 00:45:10,960
To znamená, že aj keď to môže byť dve,
tri, alebo dokonca sto riadkov kódu,

1112
00:45:10,960 --> 00:45:14,000
či je to rovnaký počet
linky, nie v nejakej slučke,

1113
00:45:14,000 --> 00:45:16,577
a nezávisí od veľkosti
zoznamu, absolútne.

1114
00:45:16,577 --> 00:45:18,660
Odstránenie prvku na
začiatok zoznamu,

1115
00:45:18,660 --> 00:45:21,940
aj keď máme čo do činenia s
Gabe, je stále konštantný čas.

1116
00:45:21,940 --> 00:45:24,220
>> Takže to vyzerá,
masívny krok späť.

1117
00:45:24,220 --> 00:45:27,000
A čo je strata času
v prípade, v jednom týždni a týždeň

1118
00:45:27,000 --> 00:45:30,250
nula sme mali nielen
pseudokód kód, ale skutočný kód

1119
00:45:30,250 --> 00:45:35,780
realizovať niečo, čo denník
base n, alebo prihláste skôr n, základ 2,

1120
00:45:35,780 --> 00:45:37,150
pokiaľ ide o jeho prevádzke.

1121
00:45:37,150 --> 00:45:40,710
Tak prečo sakra by sme chceli začať
používať niečo ako prepojeného zoznamu?

1122
00:45:40,710 --> 00:45:41,517
Jo.

1123
00:45:41,517 --> 00:45:44,022
>> Divákov: Takže môžete pridať
prvky do poľa.

1124
00:45:44,022 --> 00:45:46,230
David J. Malan :, takže môžete
pridať prvky do poľa.

1125
00:45:46,230 --> 00:45:47,550
Aj to je tematická.

1126
00:45:47,550 --> 00:45:49,740
A budeme aj naďalej vidieť
by tento trade-off, veľa

1127
00:45:49,740 --> 00:45:51,573
ako sme videli,
trade-off s zlučovacie druhu.

1128
00:45:51,573 --> 00:45:54,606
Naozaj by sa urýchliť
vyhľadávania alebo triedenia, skôr

1129
00:45:54,606 --> 00:45:57,480
ak by sme stráviť trochu viac priestoru a
majú ďalší kus pamäte

1130
00:45:57,480 --> 00:45:58,760
alebo pole pre zlúčenie druhu.

1131
00:45:58,760 --> 00:46:01,270
Ale trávime viac
priestor, ale šetrí čas.

1132
00:46:01,270 --> 00:46:04,820
V tomto prípade sme
vzdať sa času, ale my sme

1133
00:46:04,820 --> 00:46:08,170
získanie flexibility,
dynamika ak chcete,

1134
00:46:08,170 --> 00:46:10,280
čo je pravdepodobne pozitívnu vlastnosť.

1135
00:46:10,280 --> 00:46:11,520
>> Sme tiež výdavky priestor.

1136
00:46:11,520 --> 00:46:13,710
V akom zmysle je spojený
Zoznam drahšie

1137
00:46:13,710 --> 00:46:15,700
z hľadiska priestoru, než pole?

1138
00:46:15,700 --> 00:46:18,379

1139
00:46:18,379 --> 00:46:19,920
Ak je priestor navyše prichádza?

1140
00:46:19,920 --> 00:46:20,460
Jo?

1141
00:46:20,460 --> 00:46:21,800
>> Divákov: [nepočuteľné] ukazovateľ.

1142
00:46:21,800 --> 00:46:23,310
>> David J. Malan: Jo, to sme
majú tiež ukazovateľ.

1143
00:46:23,310 --> 00:46:25,560
Tak toto je minorly nepríjemné
v tom, že už som

1144
00:46:25,560 --> 00:46:27,780
Aj ukladanie len int
reprezentovať int.

1145
00:46:27,780 --> 00:46:30,990
Som uloženie int a A
ukazovateľ, ktorý je tiež 32 bitov.

1146
00:46:30,990 --> 00:46:33,470
Takže som doslova zdvojnásobí
množstvo priestoru podieľať.

1147
00:46:33,470 --> 00:46:36,040
Takže je to kompromis, ale
to je v prípade int.

1148
00:46:36,040 --> 00:46:39,580
Predpokladajme, že si nie ste ukladanie int,
ale predpokladám, že každý z týchto obdĺžnikov

1149
00:46:39,580 --> 00:46:43,290
alebo každý z týchto ľudí bola predstavujúce
slovo, anglické slovo, ktoré

1150
00:46:43,290 --> 00:46:46,430
môže mať päť znakov, 10
postavy, možno aj viac.

1151
00:46:46,430 --> 00:46:49,940
Potom sa pridá len 32 viac bitov
môže byť menej veľký problém.

1152
00:46:49,940 --> 00:46:52,160
>> Čo keď každý zo študentov
na demonštráciu

1153
00:46:52,160 --> 00:46:55,107
doslova študentské structs že
majú mená a domy a možno

1154
00:46:55,107 --> 00:46:57,065
telefónne čísla a Twitter
spracováva a podobne.

1155
00:46:57,065 --> 00:46:59,564
Takže všetky polia sme začali
hovorí o iný deň,

1156
00:46:59,564 --> 00:47:02,410
oveľa menej veľký problém, ako
naše uzly dostať oveľa zaujímavejšie

1157
00:47:02,410 --> 00:47:05,972
a veľké minúť, čo, ďalšie
ukazovateľ len ich prepojenie.

1158
00:47:05,972 --> 00:47:07,180
Ale naozaj, je to kompromis.

1159
00:47:07,180 --> 00:47:09,560
A skutočne, je kód
zložitejšie, ako budete

1160
00:47:09,560 --> 00:47:11,770
viď zbieraním prostredníctvom
že konkrétny príklad.

1161
00:47:11,770 --> 00:47:14,302
Ale čo v prípade, že boli
nejaký svätý grál tu.

1162
00:47:14,302 --> 00:47:17,010
Čo keď nebudeme brať krok
dozadu, ale masívny krok vpred

1163
00:47:17,010 --> 00:47:19,180
a implementáciu dát
Štruktúra cez ktorú

1164
00:47:19,180 --> 00:47:22,870
môžete nájsť prvky, ako je Jack, alebo
Christine alebo akékoľvek iné prvky

1165
00:47:22,870 --> 00:47:25,870
v tomto poli v pravom konštantnom čase?

1166
00:47:25,870 --> 00:47:26,920
Vyhľadávanie je konštantná.

1167
00:47:26,920 --> 00:47:28,320
Odstrániť je konštantná.

1168
00:47:28,320 --> 00:47:29,570
Vložte je konštantná.

1169
00:47:29,570 --> 00:47:32,260
Všetky tieto operácie sú konštantné.

1170
00:47:32,260 --> 00:47:33,750
To by nám svätý grál.

1171
00:47:33,750 --> 00:47:36,690
A to je miesto, kde sme sa
zdvihne nabudúce.

1172
00:47:36,690 --> 00:47:38,600
Uvidíme sa potom.

1173
00:47:38,600 --> 00:47:39,371