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

2
00:00:00,500 --> 00:00:11,137
[Muzikos grojimo]

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

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

5
00:00:13,950 --> 00:00:18,560
Tai yra penki savaitę tęsiamas, ir mes
turi gerų naujienų ir blogų naujienų.

6
00:00:18,560 --> 00:00:21,140
Taigi gera naujiena yra ta, kad CS50
pradeda šį penktadienį.

7
00:00:21,140 --> 00:00:24,430
Jei norėtumėte prisijungti prie mūsų,
galvą į įprastą URL čia.

8
00:00:24,430 --> 00:00:28,670
Dar geriau žinia, ne paskaita
tai ateina pirmadienis 13.

9
00:00:28,670 --> 00:00:31,970
Šiek tiek mažiau geresnės naujienos,
viktorina nulis kitą trečiadienį.

10
00:00:31,970 --> 00:00:33,840
Išsamesnė informacija gali būti
rasti šiuo URL čia.

11
00:00:33,840 --> 00:00:36,340
Ir per ateinančius porą dienų
mes būti užpildyti ruošiniai

12
00:00:36,340 --> 00:00:39,234
Kalbant apie kambariuose
kad turėsime saugomos.

13
00:00:39,234 --> 00:00:41,400
Geriau naujienos yra tai, kad ten bus
būti žinoma pasaulyje apžvalga

14
00:00:41,400 --> 00:00:43,570
sesijos ateinančiais
Pirmadienį vakare.

15
00:00:43,570 --> 00:00:46,270
Stay tuned į aikštyno
svetainės vietą ir duomenis.

16
00:00:46,270 --> 00:00:49,290
Skyriai, nors ji yra
atostogų, taip pat susitiks su taip pat.

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

18
00:00:50,490 --> 00:00:52,940
Geriausia naujiena, paskaita kitą penktadienį.

19
00:00:52,940 --> 00:00:56,220
Taigi tai yra tradicija, mes
turi, kaip už mokymo programas.

20
00:00:56,220 --> 00:00:58,100
Just-- tai bus nuostabu.

21
00:00:58,100 --> 00:01:02,510
Jūs matote tokius dalykus
pastovus laiko duomenų struktūros

22
00:01:02,510 --> 00:01:04,730
ir maišos lentelės ir medžiai ir bando.

23
00:01:04,730 --> 00:01:07,150
Ir mes kalbame apie gimtadienio problemų.

24
00:01:07,150 --> 00:01:09,440
Visa krūva daiktų
laukia kitą penktadienį.

25
00:01:09,440 --> 00:01:11,212

26
00:01:11,212 --> 00:01:12,200
Gerai.

27
00:01:12,200 --> 00:01:13,190
Šiaip ar taip.

28
00:01:13,190 --> 00:01:17,080
>> Taigi prisiminti, kad mes buvome
sutelkiant dėmesį į šį, kas paveikslėlyje

29
00:01:17,080 --> 00:01:18,980
viduje mūsų kompiuterio atmintyje.

30
00:01:18,980 --> 00:01:22,875
Taigi atmintis arba RAM Kai programos
egzistuoja, o jūs dirbate juos.

31
00:01:22,875 --> 00:01:25,215
Jei dukart spustelėkite
piktograma paleisti kai programa

32
00:01:25,215 --> 00:01:27,520
arba dukart spustelėkite
icon atidaryti tam tikrą failą,

33
00:01:27,520 --> 00:01:30,430
jis pakrautas iš standžiojo
vairuoti ar kietojo disko

34
00:01:30,430 --> 00:01:34,190
į RAM, Random Access Memory, kur
jis gyvena, kol galios užgęsta,

35
00:01:34,190 --> 00:01:36,700
nešiojamas dangtis užsidaro,
ar jums išeiti iš programos.

36
00:01:36,700 --> 00:01:38,960
>> Dabar, kad atmintis, iš
kuris tikriausiai turite

37
00:01:38,960 --> 00:01:41,950
1 gigabaitą šių dienų, 2
gigabaitų, arba net daug daugiau,

38
00:01:41,950 --> 00:01:44,420
paprastai išdėstyti
už tam tikrą programą

39
00:01:44,420 --> 00:01:47,170
Šiame stačiakampius rūšiuoti
koncepcinis modelis

40
00:01:47,170 --> 00:01:50,860
, kai mes turime krūvą apačioje
ir kitų daiktų krūva viršuje.

41
00:01:50,860 --> 00:01:53,140
Pačiame viršuje dalykas
mes matėme šioje nuotraukoje

42
00:01:53,140 --> 00:01:55,670
anksčiau, bet niekada kalbėjo apie
yra vadinamasis teksto daliai.

43
00:01:55,670 --> 00:01:58,419
Tekstas segmentas yra tik išgalvotas būdas
sakydamas nuliai ir tie, kurie

44
00:01:58,419 --> 00:02:01,150
kurti savo tikrąjį parengta programa.

45
00:02:01,150 --> 00:02:03,910
>> Taigi, kai jūs dukart spustelėkite
"Microsoft Word" ant jūsų Mac arba PC,

46
00:02:03,910 --> 00:02:08,030
arba kai paleidžiate dot slash Mario ant
"Linux" kompiuteris jūsų terminalo langą,

47
00:02:08,030 --> 00:02:12,460
kad nuliai ir tie, kurie sudaro
Žodis arba Mario laikinai saugomi

48
00:02:12,460 --> 00:02:16,610
į kompiuterio RAM vadinamasis
teksto segmentas tam tikrą programą.

49
00:02:16,610 --> 00:02:19,080
Žemiau kad eina inicializuoti
ir niezainicjowanymi duomenys.

50
00:02:19,080 --> 00:02:22,655
Tai stuff like globalių kintamųjų,
kad mes ne naudoti daug,

51
00:02:22,655 --> 00:02:24,910
bet kartais mes
turėjo globalių kintamųjų

52
00:02:24,910 --> 00:02:28,819
arba statiškai nustatyta eilutes, kuriose
yra sunkiai koduojami žodžius, pavyzdžiui, "labas"

53
00:02:28,819 --> 00:02:31,860
kad nėra atsižvelgiama į nuo naudotojo
kurie sunkiai koduojami į savo programą.

54
00:02:31,860 --> 00:02:34,230
>> Dabar, žemyn apačioje mes
turi vadinamąjį kamino.

55
00:02:34,230 --> 00:02:37,665
Ir kamino, iki šiol mes buvome
naudodamas Kokias tikslais?

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

57
00:02:39,706 --> 00:02:40,997
Kas kamino buvo naudojamas?

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

59
00:02:41,160 --> 00:02:42,070
>> Auditorija: funkcijos.

60
00:02:42,070 --> 00:02:43,320
>> David J. Malan: Dėl funkcijų?

61
00:02:43,320 --> 00:02:44,980
Kokia prasme funkcijas?

62
00:02:44,980 --> 00:02:48,660
>> PUBLIKA: Kai Jūs skambinate funkciją,
argumentai yra nukopijuojami ant kamino.

63
00:02:48,660 --> 00:02:49,660
>> David J. Malan: Būtent.

64
00:02:49,660 --> 00:02:52,650
Kai Jūs skambinate funkciją, jos
argumentai yra nukopijuojami ant kamino.

65
00:02:52,650 --> 00:02:56,330
Taigi bet kokie X arba Y s arba s arba B s
kad jūs artimųjų į funkciją

66
00:02:56,330 --> 00:02:58,680
laikinai įdėti
vadinamasis kamino,

67
00:02:58,680 --> 00:03:02,000
kaip vieną iš Annenberg
valgykla padėklai, taip pat dalykų,

68
00:03:02,000 --> 00:03:03,190
kaip lokalūs kintamieji.

69
00:03:03,190 --> 00:03:06,290
Jei jūsų foo funkcija arba jūsų apsikeitimo
funkcija turi lokalių kintamųjų,

70
00:03:06,290 --> 00:03:08,602
kaip temp, tie du
baigti ant kamino.

71
00:03:08,602 --> 00:03:11,560
Dabar, mes ne kalbėti per daug apie
juos, bet šie aplinkos kintamieji

72
00:03:11,560 --> 00:03:15,690
apačioje matėme, o kai prieš
Buvau futzing prie klaviatūros vieną dieną

73
00:03:15,690 --> 00:03:20,050
ir aš pradėjau susipažinimo dalykus
kaip argv 100 ar argv 1000,

74
00:03:20,050 --> 00:03:22,320
tiesiog elements-- aš pamiršiu
numbers-- bet

75
00:03:22,320 --> 00:03:24,330
nebuvo manoma, kad būti atvertas mane.

76
00:03:24,330 --> 00:03:26,581
Mes pradėjome matyti kai
funky simbolių ekrane.

77
00:03:26,581 --> 00:03:28,330
Tai buvo vadinamasis
aplinkos kintamieji

78
00:03:28,330 --> 00:03:32,390
kaip pasaulio nustatymų mano
programa ar mano kompiuteryje, o ne

79
00:03:32,390 --> 00:03:37,090
nesusijęs su neseniai
klaida, aptarėme,

80
00:03:37,090 --> 00:03:39,670
Shellshock, kad manimi buvo
kamuojančios gana keletą kompiuterių.

81
00:03:39,670 --> 00:03:42,960
>> Dabar galiausiai, šiandienos dėmesys
mes galiausiai ant krūvos.

82
00:03:42,960 --> 00:03:44,864
Tai dar viena atminties riekė.

83
00:03:44,864 --> 00:03:47,030
Ir iš esmės visa tai
atmintis pati medžiaga.

84
00:03:47,030 --> 00:03:48,040
Tai pats aparatūros.

85
00:03:48,040 --> 00:03:49,956
Užtenka tik rūšiuoti
gydant įvairias grupes

86
00:03:49,956 --> 00:03:51,460
baitų skirtingais tikslais.

87
00:03:51,460 --> 00:03:56,540
Krūva taip pat bus kur
kintamieji ir atmintis, kad prašote

88
00:03:56,540 --> 00:03:58,810
iš operacinės sistemos
laikinai saugomi.

89
00:03:58,810 --> 00:04:01,890
>> Bet ten rūšies problema
čia kaip paveikslėlį reiškia.

90
00:04:01,890 --> 00:04:05,261
Mes tarsi turime du
laivai apie susidūrimui.

91
00:04:05,261 --> 00:04:08,010
Kadangi, kaip jūs naudojate daugiau ir daugiau
iš kamino, ir, kaip matome šiandien

92
00:04:08,010 --> 00:04:11,800
pirmyn, kaip jūs naudojate daugiau ir daugiau
krūva, tikrai blogi dalykai gali atsitikti.

93
00:04:11,800 --> 00:04:15,054
Ir iš tiesų, mes galime sukelti, kad
tyčia ar netyčia.

94
00:04:15,054 --> 00:04:16,970
Taigi Cliffhanger paskutinio
laikas buvo ši programa,

95
00:04:16,970 --> 00:04:20,570
kurie netarnavo bet funkcinis
išskyrus įrodyti tikslas

96
00:04:20,570 --> 00:04:24,750
kaip jus kaip blogiukas iš tiesų gali imtis
privalumas klaidas kažkieno programos

97
00:04:24,750 --> 00:04:28,460
ir perimti programą ar net
Visa kompiuterinė sistema ar serveryje.

98
00:04:28,460 --> 00:04:31,660
Taigi tiesiog pažvelgti trumpai jums
pastebėti, kad apačioje main

99
00:04:31,660 --> 00:04:34,510
trunka komandinėje eilutėje
argumentai, kaip už argv.

100
00:04:34,510 --> 00:04:38,480
Ir ji turi ryšį su funkcija f,
iš esmės vadinamas bevardis funkcija

101
00:04:38,480 --> 00:04:40,250
f, ir tai einančios argv [1].

102
00:04:40,250 --> 00:04:43,960
>> Taigi nepriklausomai žodis vartotojas rūšys ne
greitai po šios programos pavadinimas,

103
00:04:43,960 --> 00:04:49,310
ir tada šis savavališkas funkcija iki
viršuje, f, trunka eilutę, AKA char *

104
00:04:49,310 --> 00:04:51,720
kaip mes pradėjo diskutuoti,
ir jis tiesiog vadina jį "baras".

105
00:04:51,720 --> 00:04:53,310
Tačiau mes galime jį vadinti nieko.

106
00:04:53,310 --> 00:04:57,470
Ir tada jis pareiškia, viduje
iš F, kurio simbolių masyvas

107
00:04:57,470 --> 00:04:59,930
vadinamas c-- 12 tokių simbolių.

108
00:04:59,930 --> 00:05:03,580
>> Dabar, pagal istoriją, aš sakau,
prieš momentas, kur į atmintį

109
00:05:03,580 --> 00:05:06,720
yra C, arba tie, 12
simbolių ketina baigti?

110
00:05:06,720 --> 00:05:07,570
Tiesiog kad būtų aišku.

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

112
00:05:08,070 --> 00:05:08,590
>> PUBLIKA: Ant kamino.

113
00:05:08,590 --> 00:05:09,420
>> David J. Malan: Ant kamino.

114
00:05:09,420 --> 00:05:10,720
Taigi, c yra vietos kintamąjį.

115
00:05:10,720 --> 00:05:14,079
Mes prašome 12 simbolių arba 12 baitų.

116
00:05:14,079 --> 00:05:16,120
Tie, kurie ketina baigti
apie vadinamąjį kamino.

117
00:05:16,120 --> 00:05:18,530
Dabar pagaliau tai kitas funkcijas,
kad tikrai gana naudingas,

118
00:05:18,530 --> 00:05:20,571
bet mes ne iš tikrųjų naudoti
tai patys, strncopy.

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

120
00:05:21,550 --> 00:05:25,200
Tai reiškia, string kopiją, tačiau
tik n raides, n simbolių.

121
00:05:25,200 --> 00:05:31,990
Taigi n simbolių bus
nukopijuoti iš baro į c.

122
00:05:31,990 --> 00:05:32,980
Ir kiek?

123
00:05:32,980 --> 00:05:34,110
Iš strypo ilgis.

124
00:05:34,110 --> 00:05:36,330
Taigi, kitaip tariant, kad
viena eilutė, strncopy,

125
00:05:36,330 --> 00:05:39,500
ketina kopijuoti
efektyviai uždrausti į c.

126
00:05:39,500 --> 00:05:42,340
>> Dabar, tik rūšies numatyti
Šios istorijos moralas,

127
00:05:42,340 --> 00:05:44,750
kas potencialiai problematiškas čia?

128
00:05:44,750 --> 00:05:49,710
Nors mes patikrinti ilgio
Baro ir perduoti ją į strncopy,

129
00:05:49,710 --> 00:05:53,145
Kokia jūsų žarnų pasakoja jums yra
dar suskaidytas apie šią programą?

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

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

132
00:05:55,220 --> 00:05:57,491
>> PUBLIKA: Neapima
kambarys null pobūdžio.

133
00:05:57,491 --> 00:05:59,990
David J. Malan: Neapima
kambarys null pobūdžio.

134
00:05:59,990 --> 00:06:02,073
Potencialiai, skirtingai nei
praeityje buvo taikoma praktika, mes net ne

135
00:06:02,073 --> 00:06:04,810
turi tiek, kiek pliuso nuo 1 iki
prisitaikyti, kad null charakterį.

136
00:06:04,810 --> 00:06:06,649
Bet tai dar blogiau nei tai.

137
00:06:06,649 --> 00:06:07,940
Ką dar mes nesugeba padaryti?

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

139
00:06:08,432 --> 00:06:09,307
>> PUBLIKA: [nesigirdi]

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
Mes sunkiai koduojami 12 gana savavališkai.

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

144
00:06:19,497 --> 00:06:21,330
Tai nėra tiek daug
problema, tačiau tai,

145
00:06:21,330 --> 00:06:25,630
kad mes net ne, jei tikrinant
baro ilgis yra mažesnis kaip 12,

146
00:06:25,630 --> 00:06:28,530
tokiu atveju jis bus
saugu jį į atmintį

147
00:06:28,530 --> 00:06:30,260
vadinama c, kad mes skiriama.

148
00:06:30,260 --> 00:06:32,960
Iš tiesų, jei baras yra tarsi
20 simbolių ilgio,

149
00:06:32,960 --> 00:06:39,010
Atrodo, ši funkcija turi būti nukopijuoti
20 simbolių iš baro į c, taip

150
00:06:39,010 --> 00:06:41,310
atsižvelgiant bent 8 baitus
kad ji neturėtų būti.

151
00:06:41,310 --> 00:06:42,690
Štai potekstė čia.

152
00:06:42,690 --> 00:06:44,347
>> Taigi trumpai tariant, skaldytų programą.

153
00:06:44,347 --> 00:06:45,180
Ne toks big deal.

154
00:06:45,180 --> 00:06:46,360
Gal jums segmentavimo kaltės.

155
00:06:46,360 --> 00:06:47,651
Mes visi turėjo klaidas programose.

156
00:06:47,651 --> 00:06:50,196
Mes visi gali turėti klaidų
programose dabar.

157
00:06:50,196 --> 00:06:51,320
Bet kas problema?

158
00:06:51,320 --> 00:06:54,390
Na, čia Priartinti portalo
kad mano kompiuterio atmintyje nuotrauka.

159
00:06:54,390 --> 00:06:56,230
Tai mano kamino apačioje.

160
00:06:56,230 --> 00:06:59,644
Ir iš tiesų, pačioje apačioje yra kas
vadinamas tėvų rutina kamino, išgalvotas būdas

161
00:06:59,644 --> 00:07:00,560
pasakyti, kad pagrindinis.

162
00:07:00,560 --> 00:07:03,772
Taigi, kad kas vadinama funkcija
f, kad mes kalbame apie.

163
00:07:03,772 --> 00:07:05,230
Taigi tai iš kamino apačioje.

164
00:07:05,230 --> 00:07:06,640
Grįžti adresas yra kažkas naujo.

165
00:07:06,640 --> 00:07:08,810
Tai visada buvo ten,
visada buvo toje nuotraukoje.

166
00:07:08,810 --> 00:07:10,440
Mes tiesiog niekada atkreipė dėmesį į jį.

167
00:07:10,440 --> 00:07:15,290
Nes paaiškėja, būdas c veikia, yra
kad kai viena funkcija ragina kitas,

168
00:07:15,290 --> 00:07:18,780
ne tik tai, į argumentus, kad
funkcija gauti stumiama ant kamino,

169
00:07:18,780 --> 00:07:22,470
ne tik padaryti funkcija vietinis
kintamieji gauti stumiama ant kamino,

170
00:07:22,470 --> 00:07:26,820
kažkas vadinamas atgalinis adresas
taip pat gauna įdėti ant kamino.

171
00:07:26,820 --> 00:07:33,330
Tiksliau, jeigu pagrindinis skambučiai foo pagrindiniai s
savo adresą atmintyje, jautis, ką,

172
00:07:33,330 --> 00:07:38,240
efektyviai pasireiškia įdėti į kaminą
kad, kai f yra padaryta, kad vykdant

173
00:07:38,240 --> 00:07:43,630
žino, kur šokti atgal į tekstą
segmentas, siekiant tęsti vykdymą.

174
00:07:43,630 --> 00:07:47,760
>> Taigi, jei mes čia konceptualiai,
į Pagrindinis, tada f iškviečiamas.

175
00:07:47,760 --> 00:07:50,200
Kaip veikia f žinoti, kas
rankose kontrolės nugaros?

176
00:07:50,200 --> 00:07:52,020
Na, tai tiek
tinklalapio raudonai čia

177
00:07:52,020 --> 00:07:54,978
vadinamas atgalinis adresas, jis tiesiog
patikrinimai, kas tai yra atgalinis adresas?

178
00:07:54,978 --> 00:07:57,039
O, leiskite man šokti atgal į pagrindinį čia.

179
00:07:57,039 --> 00:07:59,080
Ir tai šiek tiek
kurio supaprastinimas,

180
00:07:59,080 --> 00:08:00,750
nes nulių ir
pagrindiniam yra techniškai

181
00:08:00,750 --> 00:08:01,967
čia į technologijų segmente.

182
00:08:01,967 --> 00:08:03,800
Bet tai idėja. f
tiesiog turi žinoti, ką

183
00:08:03,800 --> 00:08:06,680
kur kontrolė galiausiai nueina.

184
00:08:06,680 --> 00:08:09,790
>> Bet kaip kompiuterių
jau seniai išdėstyti dalykus

185
00:08:09,790 --> 00:08:12,320
kaip lokalūs kintamieji ir
argumentai yra tokia.

186
00:08:12,320 --> 00:08:17,180
Taigi šio paveikslėlio viršuje
mėlyna kamino rėmas f, todėl visi

187
00:08:17,180 --> 00:08:19,630
iš atminties, kad f
specialiai naudoja.

188
00:08:19,630 --> 00:08:22,990
Taigi atitinkamai, pastebėsite, kad
baras šiame paveikslėlyje.

189
00:08:22,990 --> 00:08:23,980
Baras buvo jo argumentas.

190
00:08:23,980 --> 00:08:27,240
Ir mes teigė, kad argumentai
funkcijos gauti stumiama ant kamino.

191
00:08:27,240 --> 00:08:29,910
Ir C, be abejo, yra
Taip pat šiame paveikslėlyje.

192
00:08:29,910 --> 00:08:33,520
>> Ir tik notacijos tikslais,
pastebėti viršutiniame kairiajame kampe

193
00:08:33,520 --> 00:08:37,020
yra tai, ką būtų c laikiklio 0 ir
tada šiek tiek žemyn į dešinę

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

195
00:08:38,220 --> 00:08:41,240
Taigi, kitaip tariant, jūs galite įsivaizduoti,
kad ten baitų tinklelis

196
00:08:41,240 --> 00:08:44,380
ten, iš kurių pirmasis yra
viršuje, kairėje, apačioje, iš kurių

197
00:08:44,380 --> 00:08:48,360
yra paskutinis iš tų 12 baitų.

198
00:08:48,360 --> 00:08:49,930
>> Bet dabar pabandykite pirmyn.

199
00:08:49,930 --> 00:08:55,580
Kas yra bręsti, jei mes pereiti
į styginių juostoje, kad ilgesnio nei c?

200
00:08:55,580 --> 00:08:59,130
Ir mes ne, jei tikrinant
tai tikrai ilgiau nei 12.

201
00:08:59,130 --> 00:09:03,146
Kuris iš šioje nuotraukoje ketina
gauti perrašyti baitų 0, 1, 2, 3,

202
00:09:03,146 --> 00:09:07,890
dot dot dot, 11, ir tada
blogai, 12, 13 per 19?

203
00:09:07,890 --> 00:09:11,820
Kas nutiks čia,
jei išvesti iš užsakymo

204
00:09:11,820 --> 00:09:14,790
kad c laikiklis 0 yra ant viršaus
ir c laikiklis 11 yra tarsi žemyn

205
00:09:14,790 --> 00:09:15,812
į dešinę?

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

207
00:09:16,796 --> 00:09:19,260
>> PUBLIKA: Na, tai vyksta
perrašyti char * juostą.

208
00:09:19,260 --> 00:09:22,260
>> David J. Malan: Taip, atrodo, kad
jūs ketinate perrašyti char * juostą.

209
00:09:22,260 --> 00:09:26,245
Ir dar blogiau, jei jūs siųsti tikrai ilgai
eilutę, galbūt net perrašyti ką?

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

211
00:09:27,460 --> 00:09:28,570
Atgalinis adresas.

212
00:09:28,570 --> 00:09:31,380
Kuris vėl yra kaip
tinklalapio pasakyti programa, kur

213
00:09:31,380 --> 00:09:34,060
grįžti į kai f
daroma vadinamas.

214
00:09:34,060 --> 00:09:37,140
>> Taigi, kas blogi vaikinai paprastai padaryti
yra, jei jie susiduria programos

215
00:09:37,140 --> 00:09:41,290
kad jie yra smalsūs, ar yra
naudoti, Buggy tokiu būdu

216
00:09:41,290 --> 00:09:43,550
kad jis arba ji gali imtis
privalumas tame klaidą,

217
00:09:43,550 --> 00:09:45,720
paprastai jie negauna
ši teisė pirmą kartą.

218
00:09:45,720 --> 00:09:48,590
Jie tiesiog pradėti siųsti, pavyzdžiui,
atsitiktinių stygos į savo programą,

219
00:09:48,590 --> 00:09:50,260
ar prie klaviatūros,
ar atvirai jie tikriausiai

220
00:09:50,260 --> 00:09:52,740
rašyti mažai programa tiesiog
automatiškai generuoti stygos,

221
00:09:52,740 --> 00:09:55,430
ir pradėti beldžiasi į jūsų programą
siunčiant daug įvairių žaliavų

222
00:09:55,430 --> 00:09:56,340
skirtingų ilgių.

223
00:09:56,340 --> 00:09:58,990
>> Kai tik jūsų programos avarijos,
tai nuostabus dalykas.

224
00:09:58,990 --> 00:10:01,020
Nes tai reiškia, kad jis
ar ji atrado

225
00:10:01,020 --> 00:10:02,660
kas tikriausiai iš tikrųjų klaida.

226
00:10:02,660 --> 00:10:05,830
Ir tada jie gali gauti daugiau protingas
ir pradėti daugiau dėmesio siaurai

227
00:10:05,830 --> 00:10:07,420
apie tai, kaip išnaudoti tą klaidą.

228
00:10:07,420 --> 00:10:11,480
Visų pirma, tai, ką jis arba ji gali
padaryti, tai atsiųsti, geriausiu atveju, labas.

229
00:10:11,480 --> 00:10:12,210
Nėra baisi.

230
00:10:12,210 --> 00:10:14,750
Tai styginių tai pakankamai trumpas.

231
00:10:14,750 --> 00:10:18,100
Bet kas, jei jis ar ji siunčia,
ir mes apibendrinti kaip,

232
00:10:18,100 --> 00:10:20,890
ataka code-- taip nuliai
ir tie, kurie daryti dalykus

233
00:10:20,890 --> 00:10:25,150
kaip rm-rf, kad pašalinti viską
iš kietojo disko arba siųsti šlamštas

234
00:10:25,150 --> 00:10:27,000
ar kažkaip pulti mašiną?

235
00:10:27,000 --> 00:10:29,570
>> Taigi, jei kiekvienas iš jų
laiškai tiesiog reiškia,

236
00:10:29,570 --> 00:10:32,380
konceptualiai, ataka, puolimas,
ataka, ataka, kai blogas kodas

237
00:10:32,380 --> 00:10:36,410
kad kažkas parašė, bet
jei tas asmuo yra pakankamai protingas,

238
00:10:36,410 --> 00:10:40,790
ne tik apima visas
tų RM-RFS, bet taip pat

239
00:10:40,790 --> 00:10:46,100
jo arba jos paskutinius kelis baitus
būti numerį, kuris atitinka

240
00:10:46,100 --> 00:10:50,540
į adreso jo
ar jos pačios ataka kodas

241
00:10:50,540 --> 00:10:53,820
kad jis ar ji praėjo tik
teikiant jį greitai,

242
00:10:53,820 --> 00:10:58,760
jūs galite efektyviai apgauti kompiuterį
į pastebiu, kai f yra daroma vykdant,

243
00:10:58,760 --> 00:11:02,400
oh, tai laikas man pereiti
atgal į raudoną atgalinį adresą.

244
00:11:02,400 --> 00:11:06,070
Bet kadangi jis ar ji turi kažkaip
sutapo, kad atgalinį adresą

245
00:11:06,070 --> 00:11:09,602
su savo numeriu,
ir jie pakankamai protingas,

246
00:11:09,602 --> 00:11:11,560
į sukonfigūravote, kad
skaičius remtis, kaip jums

247
00:11:11,560 --> 00:11:13,740
pamatyti super viršuje
kairiajame kampe ten,

248
00:11:13,740 --> 00:11:18,020
Faktinis adresas kompiuterio
atminties kai jų atakos kodą,

249
00:11:18,020 --> 00:11:21,740
blogas vaikinas gali apgauti kompiuterį
į vykdančiosios savo paties kodą.

250
00:11:21,740 --> 00:11:23,700
>> Ir tai kodas, vėlgi, gali būti bet kas.

251
00:11:23,700 --> 00:11:26,120
Tai paprastai vadinama
apvalkalas kodas, kuris yra tik

252
00:11:26,120 --> 00:11:29,030
pasakyti, kad tai ne būdas
paprastai kažkas taip paprasta, kaip rm-rf.

253
00:11:29,030 --> 00:11:32,340
Tai tikrai kažkas panašaus Bash,
arba faktinis programa, kuri suteikia jam

254
00:11:32,340 --> 00:11:37,230
ar jos programinis valdymas vykdyti
dar ką nors, kad jie nori.

255
00:11:37,230 --> 00:11:40,210
Taigi trumpai tariant, visa tai
kilęs iš paprasto fakto,

256
00:11:40,210 --> 00:11:44,490
kad ši klaida dalyvauja ne tikrinti
kad jūsų masyvo ribos.

257
00:11:44,490 --> 00:11:47,250
Ir todėl, kaip
kompiuteriai darbą yra tai, kad jie

258
00:11:47,250 --> 00:11:49,430
naudoti nuo kamino
efektyviai, konceptualiai,

259
00:11:49,430 --> 00:11:54,830
Apačia up, bet tada elementai
Paspaudus ant kamino auga iš viršaus į apačią,

260
00:11:54,830 --> 00:11:56,624
tai yra neįtikėtinai sudėtinga.

261
00:11:56,624 --> 00:11:58,290
Dabar, yra būdų, kaip išspręsti šią.

262
00:11:58,290 --> 00:12:00,800
Ir tiesą sakant, yra kalbos
, su kuria dirbti aplink tai.

263
00:12:00,800 --> 00:12:03,100
Java yra imuninės, pavyzdžiui,
šiuo konkrečiu klausimu.

264
00:12:03,100 --> 00:12:04,110
Kadangi jie neturi duoti jums patarimų.

265
00:12:04,110 --> 00:12:05,943
Jie nesuteikia jums
tiesioginės atminties adresai.

266
00:12:05,943 --> 00:12:08,560
Taigi su tokia galia, kad mes turime
liesti nieko atmintyje

267
00:12:08,560 --> 00:12:11,580
Mes norime, kad ateina, tiesa, didelė rizika.

268
00:12:11,580 --> 00:12:12,430
>> Taigi stebėkite.

269
00:12:12,430 --> 00:12:14,596
Jei atvirai, mėnesiais
ar ateinančių metų, kada

270
00:12:14,596 --> 00:12:17,740
perskaityti apie kai išnaudojimo
iš programos ar serverio,

271
00:12:17,740 --> 00:12:22,370
jei jūs kada nors pamatyti kažką užuominą
kaip buferio perpildymo atakos

272
00:12:22,370 --> 00:12:25,390
arba kamino perpildymo yra kito tipo
ataka, panaši dvasia,

273
00:12:25,390 --> 00:12:28,770
kiek įkvepia interneto svetainės
pavadinimas, jei jį žinote,

274
00:12:28,770 --> 00:12:33,170
visa tai kalbame tik apie
perpildyta su kai kurių charakterio dydį

275
00:12:33,170 --> 00:12:36,200
masyvas ar kai masyvas apskritai.

276
00:12:36,200 --> 00:12:38,822
Turite klausimų, tuomet apie tai?

277
00:12:38,822 --> 00:12:39,780
Nebandykite to namuose.

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

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

280
00:12:42,300 --> 00:12:47,270
Taigi malloc šiol buvo mūsų naujas
draugas, kad mes galime paskirstyti atmintį

281
00:12:47,270 --> 00:12:50,540
kad mes nebūtinai žinoti
iš anksto, kad mes norime, kad mes neturime

282
00:12:50,540 --> 00:12:52,920
į kietąjį kodą į mūsų
programos numerius, pavyzdžiui, 12.

283
00:12:52,920 --> 00:12:55,550
Kai vartotojas pasako kiek
duomenys, jis ar ji nori įvesti,

284
00:12:55,550 --> 00:12:58,000
mes galime malloc kad daug atminties.

285
00:12:58,000 --> 00:13:01,484
>> Taigi malloc it turns out, kad
Kiek mes jau jį naudojant,

286
00:13:01,484 --> 00:13:03,900
aiškiai paskutinį kartą, ir tada
vaikinai buvo naudojant jį

287
00:13:03,900 --> 00:13:08,160
už getstring nežinodami už
keletą savaičių, visi malloc atminties

288
00:13:08,160 --> 00:13:09,820
kilęs iš vadinamųjų krūvą.

289
00:13:09,820 --> 00:13:13,852
Ir tai, kodėl getstring, pavyzdžiui,
gali paskirstyti atmintį dinamiškai

290
00:13:13,852 --> 00:13:16,060
nežinant, ką jūs
ketina įvesti iš anksto,

291
00:13:16,060 --> 00:13:21,520
perduoti jums atgal žymiklį į tą atmintį,
ir kad atmintis vis dar tavo išlaikyti,

292
00:13:21,520 --> 00:13:24,080
net po getstring grąžą.

293
00:13:24,080 --> 00:13:27,450
Kadangi priminti juk, kad
kamino nuolat vyksta aukštyn ir žemyn,

294
00:13:27,450 --> 00:13:27,950
aukštyn ir žemyn.

295
00:13:27,950 --> 00:13:30,230
Ir kuo greičiau, kaip jis eina
žemyn, tai reiškia, kad bet kokios atminties

296
00:13:30,230 --> 00:13:33,030
ši funkcija naudojama turėtų
negali būti naudojama niekam kitam.

297
00:13:33,030 --> 00:13:34,570
Tai šiukšlių vertybes dabar.

298
00:13:34,570 --> 00:13:36,120
>> Bet krūva yra čia.

299
00:13:36,120 --> 00:13:39,360
Ir kas malonu apie malloc yra tai, kad
kai malloc paskirsto atmintį iki čia,

300
00:13:39,360 --> 00:13:42,070
tai ne įtakos, nes
didžioji dalis, kurią kamino.

301
00:13:42,070 --> 00:13:46,000
Ir taip bet funkcija gali naudotis
atmintis, buvo malloc'd,

302
00:13:46,000 --> 00:13:49,120
net panašaus getstring funkcija,
net po to, kai jis grįžo.

303
00:13:49,120 --> 00:13:51,700
>> Dabar, iš malloc Converse yra nemokama.

304
00:13:51,700 --> 00:13:53,900
Ir iš tiesų, ši taisyklė jums
reikia pradėti priimti

305
00:13:53,900 --> 00:13:58,950
yra bet, bet, bet kuriuo metu jūs naudojate malloc
turite sau naudoti nemokamai, galiausiai,

306
00:13:58,950 --> 00:14:00,280
tą pačią rodyklę.

307
00:14:00,280 --> 00:14:03,289
Visą šį laiką mes buvome raštu
Buggy, Buggy kodas, dėl daugelio priežasčių.

308
00:14:03,289 --> 00:14:05,580
Tačiau vienas iš jų buvo
naudojant CS50 biblioteką, kuri

309
00:14:05,580 --> 00:14:09,010
pati yra sąmoningai
Buggy, ji nutekėjo atminties.

310
00:14:09,010 --> 00:14:11,410
Bet koks laikas, jūs vadinamas getstring
Per pastaruosius keletą savaičių

311
00:14:11,410 --> 00:14:13,870
Mes prašome operacinės
sistema, Linux, už atmintį.

312
00:14:13,870 --> 00:14:15,780
Ir jūs niekada kartą atidavė jį atgal.

313
00:14:15,780 --> 00:14:17,730
Ir tai ne, ir
praktika, yra geras dalykas.

314
00:14:17,730 --> 00:14:20,330
>> Ir Valgrind, vienas iš
įvestos Pset 4 įrankiai

315
00:14:20,330 --> 00:14:22,900
yra visa informacija apie Jums padėti
dabar radote klaidų, pavyzdžiui, kad.

316
00:14:22,900 --> 00:14:27,060
Bet laimei Pset 4 nereikia
naudoti CS50 biblioteką ar getstring.

317
00:14:27,060 --> 00:14:31,220
Taigi bet kokie klaidų, susijusių su atminties yra
galiausiai bus jūsų pačių.

318
00:14:31,220 --> 00:14:34,060
>> Taigi malloc yra daugiau nei tiesiog
patogu šiam tikslui.

319
00:14:34,060 --> 00:14:37,420
Mes iš tikrųjų dabar gali išspręsti
iš esmės skirtingos problemos,

320
00:14:37,420 --> 00:14:41,640
ir iš esmės spręsti problemas daugiau
veiksmingai, kaip per savaitę nulis pažadą.

321
00:14:41,640 --> 00:14:44,720
Iki šiol tai yra seksualiausia
duomenų struktūra, mes turėjome.

322
00:14:44,720 --> 00:14:47,804
Ir duomenų struktūros Aš tiesiog reiškia,
iš konceptualizavimo atminties būdas

323
00:14:47,804 --> 00:14:50,720
tokiu būdu, kuris peržengia tiesiog pasakyti,
tai int, tai char.

324
00:14:50,720 --> 00:14:52,930
Mes galime pradėti klasterio dalykų kartu.

325
00:14:52,930 --> 00:14:54,460
>> Taigi masyvas atrodė taip.

326
00:14:54,460 --> 00:14:57,270
Ir tai, kas buvo raktas apie
masyvas yra tai, kad ji suteikia jums

327
00:14:57,270 --> 00:14:59,724
back-to-back gabaliukus
atmintis, iš kurių kiekvienas

328
00:14:59,724 --> 00:15:02,765
bus to paties tipo, int
int, int, int arba char, char, char,

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

330
00:15:03,330 --> 00:15:04,496
Tačiau yra keletas praradimas.

331
00:15:04,496 --> 00:15:06,570
Tai, pavyzdžiui, yra
dydžio šešių masyvo.

332
00:15:06,570 --> 00:15:10,650
Tarkime, jūs užpildyti šią masyvas su šešių
Skaičiai ir tada, dėl kokių nors priežasčių,

333
00:15:10,650 --> 00:15:13,187
Jūsų vartotojas nori suteikti
Jūs septintojo skaičius.

334
00:15:13,187 --> 00:15:14,020
Kur jūs įdėti jį?

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

336
00:15:15,490 --> 00:15:18,990
>> Kas sprendimas, jei turite
sukurta masyvą į kaminą,

337
00:15:18,990 --> 00:15:22,030
Pavyzdžiui, tik su savaitės
du žymėjimas, kurį mes pristatėme,

338
00:15:22,030 --> 00:15:23,730
iš laužtiniuose skliaustuose su numeriu viduje?

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

340
00:15:25,160 --> 00:15:27,260
Na, jūs turite šešis
Skaičiai šiose dėžėse.

341
00:15:27,260 --> 00:15:28,530
Ką jūsų instinktai būti?

342
00:15:28,530 --> 00:15:29,973
Kur gi jūs norite įdėti jį?

343
00:15:29,973 --> 00:15:30,860
>> PUBLIKA: [nesigirdi]

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

345
00:15:31,315 --> 00:15:32,380
>> PUBLIKA: Padėkite jį ant galo.

346
00:15:32,380 --> 00:15:33,796
>> David J. Malan: Padėkite jį ant galo.

347
00:15:33,796 --> 00:15:35,880
Taigi šiek tiek daugiau nei į dešinę,
už šį bloką.

348
00:15:35,880 --> 00:15:38,710
Kuris būtų malonu, bet tai
Pasirodo, jūs negalite padaryti.

349
00:15:38,710 --> 00:15:41,350
Nes jei jūs neprašė
Šio atminties riekė,

350
00:15:41,350 --> 00:15:44,490
tai gali būti sutapimas, kad šioje
yra naudojamas kitu kintamuoju

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

352
00:15:45,030 --> 00:15:49,210
Prisiminkite savaitę arba tiek, kai mes nustatyti
iš Zamyla and Davin and Gabe s pavadinimų

353
00:15:49,210 --> 00:15:49,930
atmintyje.

354
00:15:49,930 --> 00:15:51,638
Jie buvo tiesiog
atgal atgal į nugarą.

355
00:15:51,638 --> 00:15:53,550
Taigi, mes ne visada gali
pasitikėti, kad visada kas

356
00:15:53,550 --> 00:15:55,800
per čia galima man naudoti.

357
00:15:55,800 --> 00:15:56,990
>> Taigi, ką dar gali padaryti?

358
00:15:56,990 --> 00:16:00,282
Na, kai supranta jus
reikia iš dydžio septynių masyvą,

359
00:16:00,282 --> 00:16:02,490
galite tiesiog sukurti
masyvas dydžio septynių tada naudokite

360
00:16:02,490 --> 00:16:05,950
už linijos arba while cikle,
nukopijuokite jį į naują masyvą,

361
00:16:05,950 --> 00:16:09,680
ir tada kažkaip tik atsikratyti
tai masyvas arba tiesiog nustoti jį naudoti.

362
00:16:09,680 --> 00:16:12,130
Bet tai nėra labai veiksminga.

363
00:16:12,130 --> 00:16:15,340
Trumpai tariant, matricas neleiskite
Jūs dinamiškai keisti.

364
00:16:15,340 --> 00:16:17,900
>> Taigi, viena vertus, jūs gaunate
laisvosios kreipties, kuri yra nuostabi.

365
00:16:17,900 --> 00:16:20,108
Nes ji leidžia mums daryti tai, ko
kaip skaldyk ir valdyk,

366
00:16:20,108 --> 00:16:23,100
Dvejetainis paieškos, ir visa tai mes
kalbėjo apie ekrane čia.

367
00:16:23,100 --> 00:16:24,950
Bet jūs dažų save į kampą.

368
00:16:24,950 --> 00:16:27,810
Kai paspausite
Jūsų masyvo pabaigos,

369
00:16:27,810 --> 00:16:29,980
jūs turite padaryti labai
brangus eksploatavimas

370
00:16:29,980 --> 00:16:33,910
arba rašyti visa krūva kodas
dabar spręsti šią problemą.

371
00:16:33,910 --> 00:16:36,680
>> Taigi ką daryti, jei vietoj to mes turėjome
kažkas vadinamas sąrašą,

372
00:16:36,680 --> 00:16:38,820
arba susiję sąrašą visų pirma?

373
00:16:38,820 --> 00:16:41,930
Ką daryti, jei vietoj to, kad
stačiakampiai atgal atgal atgal,

374
00:16:41,930 --> 00:16:45,730
turime stačiakampiai, kad palieka mažai
tiek kraipymas kambarį tarp jų?

375
00:16:45,730 --> 00:16:49,670
Ir nors aš sudarytas šis
paveikslėlį ar pritaikyti šį paveiksliuką

376
00:16:49,670 --> 00:16:54,696
vieną iš tekstų čia grįžti į
atgal atgal labai tvarkingai, iš tikrųjų,

377
00:16:54,696 --> 00:16:56,820
vienas iš tų stačiakampių
gali būti čia atmintyje.

378
00:16:56,820 --> 00:16:58,028
Vienas iš jų gali būti čia.

379
00:16:58,028 --> 00:17:00,420
Vienas iš jų galėtų būti čia,
per čia, ir taip toliau.

380
00:17:00,420 --> 00:17:02,910
>> Bet kas, jei mes padarė,
šiuo atveju, strėlės

381
00:17:02,910 --> 00:17:05,650
kad kažkaip susieti juos
stačiakampių kartu?

382
00:17:05,650 --> 00:17:08,170
Iš tiesų, mes matėme techninis
įsikūnijimas rodykle.

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

384
00:17:09,839 --> 00:17:13,710
Ką mes naudojamas neseniai
dienų, kad po gaubtu,

385
00:17:13,710 --> 00:17:15,210
atvaizduoja rodykle?

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

387
00:17:16,290 --> 00:17:17,349
Žymeklis, tiesa?

388
00:17:17,349 --> 00:17:19,780
>> Taigi ką daryti, jei, užuot
tiesiog laikyti numerius,

389
00:17:19,780 --> 00:17:23,130
kaip 9, 17, 22, 26, 34,
Ką daryti, jei mes saugomi ne

390
00:17:23,130 --> 00:17:27,079
tik skaičius, bet žymeklis
šalia kiekvieno tokio skaičiaus?

391
00:17:27,079 --> 00:17:30,690
Taigi, kad panašiai kaip jūs sriegis
adatą per visa krūva audinio,

392
00:17:30,690 --> 00:17:32,950
kažkaip susiejimas dalykai
kartu, panašiai gali

393
00:17:32,950 --> 00:17:35,550
mes su rodyklėmis, kaip
įsikūnijęs rodyklėmis čia

394
00:17:35,550 --> 00:17:38,550
rūšies pynimo kartu
šie atskiri stačiakampiai

395
00:17:38,550 --> 00:17:41,780
efektyviai naudojant žymiklį
šalia kiekvieno numerio, kad

396
00:17:41,780 --> 00:17:46,065
atkreipia dėmesį į tam tikrą kitą skaičių, kad
atkreipia dėmesį į, savo ruožtu, kai šalia skaičius?

397
00:17:46,065 --> 00:17:47,940
Taigi, kitaip tariant,
jei mes iš tikrųjų norėjo

398
00:17:47,940 --> 00:17:49,820
įgyvendinti kažką panašaus į tai?

399
00:17:49,820 --> 00:17:53,610
Na, deja, šie stačiakampiai,
Bent jau vienas su 9, 17, 22,

400
00:17:53,610 --> 00:17:57,040
ir taip toliau, tai jau nebėra
gražūs kvadratėliai su atskirais numeriais.

401
00:17:57,040 --> 00:17:59,960
Apačioje, stačiakampio
Toliau 9, pavyzdžiui,

402
00:17:59,960 --> 00:18:04,330
atitinka tai, ką turėtų
būti žymeklis, 32 bitai.

403
00:18:04,330 --> 00:18:09,460
Dabar, aš dar nežino apie bet duomenų tipas
C, kuris suteikia jums ne tik int

404
00:18:09,460 --> 00:18:11,630
bet žymeklis apskritai.

405
00:18:11,630 --> 00:18:15,020
>> Taigi, kas yra sprendimas, jei norime
sugalvoti savo atsakymo į šį klausimą?

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

407
00:18:15,760 --> 00:18:16,640
>> PUBLIKA: [nesigirdi]

408
00:18:16,640 --> 00:18:17,360
>> David J. Malan: Kas tai?

409
00:18:17,360 --> 00:18:17,880
>> PUBLIKA: Naujoji struktūra.

410
00:18:17,880 --> 00:18:19,590
>> David J. Malan: Taip, taip, tai kodėl
ne mes sukurti naują struktūrą,

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

412
00:18:20,920 --> 00:18:25,990
Mes matėme structs anksčiau, jei trumpai,
kur mes buvo susiję su studento struktūra

413
00:18:25,990 --> 00:18:27,780
kaip tai, kas ir turėjo pavadinimą ir namą.

414
00:18:27,780 --> 00:18:31,980
Be Pset 3 Breakout naudojote visa
krūva structs-- GRect ir GOvals

415
00:18:31,980 --> 00:18:34,810
kad Stanfordo sukurta
klasteris informacija kartu.

416
00:18:34,810 --> 00:18:38,580
Taigi ką daryti, jei mes priimsime tą pačią idėją
raktiniai žodžiai "Typedef" ir "struct",

417
00:18:38,580 --> 00:18:42,890
ir tada kai studentas konkrečių dalykų,
ir vystytis į šiuos taip:

418
00:18:42,890 --> 00:18:46,210
Typedef konstrukto node-- ir mazgas yra
tik labai bendro pobūdžio informatikos

419
00:18:46,210 --> 00:18:49,980
Terminas kažko duomenų struktūros,
į duomenų struktūrą konteineris.

420
00:18:49,980 --> 00:18:53,900
Mazgas galiu reikalauti teks
int n, visiškai nesudėtingas,

421
00:18:53,900 --> 00:18:58,810
ir tada šiek tiek daugiau cryptically,
tai antra linija, konstrukto mazgas * šalia.

422
00:18:58,810 --> 00:19:01,300
Tačiau mažiau techninių terminų,
kas tai yra antroji linija

423
00:19:01,300 --> 00:19:02,980
kodo viduje klamrami?

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

425
00:19:03,737 --> 00:19:04,851
>> PUBLIKA: [nesigirdi]

426
00:19:04,851 --> 00:19:06,600
David J. Malan:
žymiklį į kitą mazgą.

427
00:19:06,600 --> 00:19:09,910
Taigi reikia pripažinti, sintaksės tiek paslaptingas.

428
00:19:09,910 --> 00:19:13,250
Bet jei jūs jį skaityti pažodžiui,
šalia yra kintamojo vardas.

429
00:19:13,250 --> 00:19:14,410
Kas yra jo duomenų tipas?

430
00:19:14,410 --> 00:19:18,206
Tai šiek tiek kalbantys, šį kartą,
bet tai tipo struct mazgas *.

431
00:19:18,206 --> 00:19:22,960
Bet koks laikas, mes matėme kažką žvaigždė, kad
reiškia, kad jis žymiklį į tą duomenų tipą.

432
00:19:22,960 --> 00:19:26,810
Taigi, kitą, matyt,
Rodyklė į struct mazgas.

433
00:19:26,810 --> 00:19:28,310
>> Dabar, kas yra konstrukto mazgas?

434
00:19:28,310 --> 00:19:31,044
Na, pastebėsite, pamatysite tuos,
tie patys žodžiai viršuje dešinėje.

435
00:19:31,044 --> 00:19:33,960
Ir iš tiesų, jūs taip pat pamatysite žodį
"Mazgas" žemyn čia, apačioje, kairėje.

436
00:19:33,960 --> 00:19:35,640
Ir iš tikrųjų tai yra tik patogumo.

437
00:19:35,640 --> 00:19:39,930
Atkreipkite dėmesį, kad mūsų studentų apibrėžimo
ten žodis "studentas" tik vieną kartą.

438
00:19:39,930 --> 00:19:42,510
Ir tai todėl, kad studentas
objektas buvo ne subjektyviais kriterijais.

439
00:19:42,510 --> 00:19:45,340
Nėra nieko viduje studentas
kad reikia atkreipti dėmesį į kitą studentas,

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

441
00:19:45,610 --> 00:19:47,630
Tai būtų tarsi
keista realiame pasaulyje.

442
00:19:47,630 --> 00:19:50,880
>> Bet su per mazgas susieti
sąrašas, mes norime mazgas

443
00:19:50,880 --> 00:19:53,970
būti Godbijīgs panašiu daiktu.

444
00:19:53,970 --> 00:19:57,900
Ir taip pastebėsite čia kaita nėra
tik tai, kas viduje garbanotas petnešomis.

445
00:19:57,900 --> 00:20:00,800
Bet mes pridėti žodį "mazgas"
viršuje, taip pat

446
00:20:00,800 --> 00:20:02,930
pridedant jį į apačią
vietoj "studentas".

447
00:20:02,930 --> 00:20:06,000
Ir tai yra tik techninė detalė
taip, kad vėl, jūsų duomenų struktūra

448
00:20:06,000 --> 00:20:11,380
gali tik savimi, kad
mazgas gali nurodyti kitas toks mazgas.

449
00:20:11,380 --> 00:20:13,840
>> Taigi, kas tai yra galiausiai
ketina reikšti mus?

450
00:20:13,840 --> 00:20:17,560
Na, vienas, ši medžiaga viduje
yra mūsų mazgas turinys.

451
00:20:17,560 --> 00:20:19,360
Šis dalykas čia,
viršuje dešinėje, yra tik tiek

452
00:20:19,360 --> 00:20:20,860
kad, vėlgi, galime kreiptis į save.

453
00:20:20,860 --> 00:20:23,401
Ir tada atokiausiuose dalykų,
nors mazgas yra naujas terminas,

454
00:20:23,401 --> 00:20:25,500
tai, kad jis vis dar
pats, kaip studentų ir ką

455
00:20:25,500 --> 00:20:27,520
buvo po į SPL gaubtu.

456
00:20:27,520 --> 00:20:31,095
>> Taigi, jei mes dabar norėjau pradėti
Įgyvendinant šią susietą sąrašą,

457
00:20:31,095 --> 00:20:33,220
kaip gali mes verčiame
kažkas panašaus į tai kodas?

458
00:20:33,220 --> 00:20:35,350
Na, tegul tik pamatyti
pavyzdys programos,

459
00:20:35,350 --> 00:20:36,840
faktiškai naudoja susietą sąrašą.

460
00:20:36,840 --> 00:20:40,870
Tarp šiandienos platinimo kodą
yra programa, vadinama Sąrašas nulis.

461
00:20:40,870 --> 00:20:44,980
Ir jei aš paleisti tai aš sukūriau super
paprastas GUI, Graphical User Interface,

462
00:20:44,980 --> 00:20:46,460
bet tai tikrai tik printf.

463
00:20:46,460 --> 00:20:50,930
Ir dabar aš jau davė sau keletą meniu
options-- Ištrinti, Įterpti, Paieška,

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

465
00:20:51,750 --> 00:20:52,630
Ir Baigti.

466
00:20:52,630 --> 00:20:55,970
Tai yra tik bendros operacijos
duomenų struktūra vadinama nuoroda, sąrašą.

467
00:20:55,970 --> 00:20:58,409
>> Dabar Ištrinti ketina
ištrinti iš sąrašo numerį.

468
00:20:58,409 --> 00:21:00,200
Įdėkite ketina pridėti
skaičius į sąrašą.

469
00:21:00,200 --> 00:21:02,181
Paieška atrodys
už numerį sąraše.

470
00:21:02,181 --> 00:21:04,930
Ir ėjimas yra tik išgalvotas būdas
sakydamas, vaikščioti per sąrašą,

471
00:21:04,930 --> 00:21:06,245
atspausdinti jį, bet viskas.

472
00:21:06,245 --> 00:21:07,720
Negalima pakeisti jį bet kokiu būdu.

473
00:21:07,720 --> 00:21:08,570
>> Taigi pabandykime tai.

474
00:21:08,570 --> 00:21:10,160
Vykime į priekį ir 2 tipo.

475
00:21:10,160 --> 00:21:12,710
Ir tada aš ruošiuosi
įterpti numerį, pasakyti 9.

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

477
00:21:13,620 --> 00:21:17,480
Ir dabar mano programa yra tik
užprogramuotas pasakyti, sąrašas dabar yra 9.

478
00:21:17,480 --> 00:21:20,190
Dabar, jei aš einu į priekį ir
do Įdėkite vėl, leiskite

479
00:21:20,190 --> 00:21:23,680
man eiti į priekį ir nutolinti ir įveskite 17.

480
00:21:23,680 --> 00:21:25,770
Dabar mano sąraše yra 9, o po to 17.

481
00:21:25,770 --> 00:21:27,750
Jei aš įdėti vėl praleiskime vieną.

482
00:21:27,750 --> 00:21:32,400
Vietoj 22, kaip už paveikslėlyje mes
ieškau ne čia, leiskite man šokti į priekį

483
00:21:32,400 --> 00:21:34,630
ir įdėkite 26 sekantis.

484
00:21:34,630 --> 00:21:36,230
Taigi, aš ruošiuosi 26 tipo.

485
00:21:36,230 --> 00:21:37,755
Sąrašas, kaip aš tikėtis.

486
00:21:37,755 --> 00:21:40,630
Bet dabar, tik pamatyti, jei šio kodekso
bus lankstus, leiskite man dabar

487
00:21:40,630 --> 00:21:43,520
22 tipas, kuris bent
konceptualiai, jei mes

488
00:21:43,520 --> 00:21:46,520
Tęsdami šią rūšiuojamos, kuris yra iš tikrųjų
bus dar vienas tikslas dabar,

489
00:21:46,520 --> 00:21:48,690
turėtų eiti tarp 17 ir 26.

490
00:21:48,690 --> 00:21:50,270
Taigi, aš paspauskite Enter.

491
00:21:50,270 --> 00:21:51,380
Iš tiesų, tai veikia.

492
00:21:51,380 --> 00:21:54,950
Ir todėl dabar leiskite man įdėti
paskutinis, už nuotrauką, 34.

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

494
00:21:55,450 --> 00:21:58,980
Taigi dabar leiskite man nustatyta, kad
Ištrinti ir Travers ir paieška padaryti,

495
00:21:58,980 --> 00:21:59,760
iš tiesų, dirbti.

496
00:21:59,760 --> 00:22:04,180
Iš tiesų, jei aš paleisti paiešką, tegul
ieškoti skaičiaus 22, Enter.

497
00:22:04,180 --> 00:22:05,010
Jis nustatė 22.

498
00:22:05,010 --> 00:22:07,580
Taigi, kad yra tai, kas tai
programa Sąrašas nulis daro.

499
00:22:07,580 --> 00:22:10,230
>> Bet ką iš tikrųjų vyksta
apie tai įgyvendina tai?

500
00:22:10,230 --> 00:22:14,530
Na, visų pirma aš gali turėti ir iš tiesų
Aš turiu, failas, vadinamas list0.h.

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

502
00:22:16,540 --> 00:22:20,690
Ir kažkur ten tai
linija, Typedef, konstrukto mazgas,

503
00:22:20,690 --> 00:22:24,850
tada turiu garbanotas petnešos, int n, ir
tada struct-- kas apibrėžimas?

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

505
00:22:26,530 --> 00:22:28,545
Kapitalo struktūra mazgas šalia.

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

507
00:22:29,920 --> 00:22:31,045
Taigi, mes turime žvaigždė.

508
00:22:31,045 --> 00:22:33,420
Dabar techniškai mes į
piešimo čia įprotis.

509
00:22:33,420 --> 00:22:35,670
Jūs galite pamatyti vadovėlius ir
Prisijungę nuorodos daryti ten.

510
00:22:35,670 --> 00:22:36,660
Tai funkciškai lygiavertės.

511
00:22:36,660 --> 00:22:37,980
Tiesą sakant, tai yra šiek tiek daugiau tipiškas.

512
00:22:37,980 --> 00:22:40,563
Bet aš būsiu atitinka tai, ką
mes padarėme paskutinį kartą ir tai padaryti.

513
00:22:40,563 --> 00:22:42,350
Ir tada galiausiai, aš ruošiuosi tai padaryti.

514
00:22:42,350 --> 00:22:45,550
>> Taigi antraštės failą
kažkur į list0.h

515
00:22:45,550 --> 00:22:49,200
šiandien tai konstrukto apibrėžimą,
o gal kai kurių kitų dalykų.

516
00:22:49,200 --> 00:22:52,580
Tuo tarpu list0c ten
bus keletas dalykų.

517
00:22:52,580 --> 00:22:54,740
Tačiau mes ketiname tik
pradėti, o ne užbaigti tai.

518
00:22:54,740 --> 00:22:59,690
List0.h yra failas Noriu
įtraukti į mano C failą.

519
00:22:59,690 --> 00:23:03,910
Ir tada tam tikru momentu aš
teks int, pagrindinis, negalioja.

520
00:23:03,910 --> 00:23:06,530
Ir tada aš ruošiuosi
turi keletą darbų čia.

521
00:23:06,530 --> 00:23:10,620
Aš taip pat teks
prototipas, kaip tuščia, paiešką, int,

522
00:23:10,620 --> 00:23:13,610
N, kurio gyvenimo tikslas yra
ieškoti elemento.

523
00:23:13,610 --> 00:23:18,310
Ir tada žemyn čia galiu reikalauti iš
Šiandienos kodas, negaliojančiu, ieškoti, int n,

524
00:23:18,310 --> 00:23:21,020
ne kabliataškis, bet atviros garbanotieji petnešų.

525
00:23:21,020 --> 00:23:25,049
Ir dabar aš noriu kažkaip ieškoti
už šio sąrašo elementas.

526
00:23:25,049 --> 00:23:27,340
Tačiau mes neturime pakankamai
informacija ekrane dar.

527
00:23:27,340 --> 00:23:29,800
Turiu ne iš tikrųjų
atstovavo pats sąrašas.

528
00:23:29,800 --> 00:23:33,070
Taigi vienas iš būdų mes galime įgyvendinti
susiję sąrašas programą

529
00:23:33,070 --> 00:23:37,520
yra I rūšies nori kažką daryti
kaip Pareiškiu susiję sąrašą čia.

530
00:23:37,520 --> 00:23:40,520
Kad būtų paprasčiau, aš ruošiuosi padaryti
tai pasaulinė, nors apskritai mes

531
00:23:40,520 --> 00:23:41,645
neturėtų daryti tai per daug.

532
00:23:41,645 --> 00:23:43,260
Bet tai bus supaprastinti šį pavyzdį.

533
00:23:43,260 --> 00:23:45,890
Taigi noriu paskelbti
susiję sąrašas čia.

534
00:23:45,890 --> 00:23:47,010
Dabar, kaip galėčiau tai padaryti?

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

536
00:23:48,810 --> 00:23:50,750
>> Štai iš susietą sąrašo nuotraukos.

537
00:23:50,750 --> 00:23:53,030
Ir aš tikrai ne
žinoti metu how

538
00:23:53,030 --> 00:23:56,710
Aš ruošiuosi eiti apie atstovaujantis
tiek daug dalykų, tik su vienu

539
00:23:56,710 --> 00:23:58,040
kintamasis atmintyje.

540
00:23:58,040 --> 00:23:59,160
Bet prisiminkite akimirką.

541
00:23:59,160 --> 00:24:00,830
Visą šį laiką mes turėjome
stygos, kurį mes tada

542
00:24:00,830 --> 00:24:02,913
atskleidė, kad matricos
simbolių, kuriuos mes tada

543
00:24:02,913 --> 00:24:05,740
atskleidė tiesiog rodyklė
į pirmąjį požymį

544
00:24:05,740 --> 00:24:08,890
į simbolių masyvas
Štai null nutrauktas.

545
00:24:08,890 --> 00:24:13,530
Taigi, šia logika, ir su šiuo
nuotrauka rūšies sėti savo mintis,

546
00:24:13,530 --> 00:24:17,964
ką mums reikia iš tikrųjų parašyti mūsų
kodas atstovauti susietą sąrašą?

547
00:24:17,964 --> 00:24:21,130
Kiek šios informacijos mums reikia,
užfiksuoti C kodą, galėtumėte pasakyti?

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

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

550
00:24:23,154 --> 00:24:24,738
>> PUBLIKA: Mums reikia žymiklį į mazgą.

551
00:24:24,738 --> 00:24:26,237
David J. Malan: Rodyklė į mazgą.

552
00:24:26,237 --> 00:24:29,320
Visų pirma, kuris mazgas norėtų jūsų
instinktai būti išlaikyti žymiklį?

553
00:24:29,320 --> 00:24:30,026
>> PUBLIKA: pirmasis mazgas.

554
00:24:30,026 --> 00:24:31,942
>> David J. Malan: Taip,
tikriausiai tik pirmą kartą.

555
00:24:31,942 --> 00:24:34,030
Ir atkreipkite dėmesį, pirmiausia
mazgas yra skirtingos formos.

556
00:24:34,030 --> 00:24:37,690
Tai tik pusė iš struct dydis,
nes tai iš tiesų tik žymeklis.

557
00:24:37,690 --> 00:24:44,650
Taigi, ką jūs iš tiesų gali padaryti, tai paskelbti
susijęs sąrašas, kad būtų tipo mazgas *.

558
00:24:44,650 --> 00:24:47,780
Ir tegul tiesiog vadina jį pirmą kartą
inicijuoti ir ją null.

559
00:24:47,780 --> 00:24:49,910
Taigi null, vėlgi, yra dar
į nuotrauką čia.

560
00:24:49,910 --> 00:24:53,620
Ne tik null naudojamas kaip kaip speciali
Grąžina reikšmę dalykų, pavyzdžiui, getstring

561
00:24:53,620 --> 00:24:57,770
ir malloc, niekinis, taip pat nulis
žymeklis, iš rodyklės stoka,

562
00:24:57,770 --> 00:24:58,430
jei bus.

563
00:24:58,430 --> 00:25:00,309
Tai tiesiog reiškia, nieko dar čia.

564
00:25:00,309 --> 00:25:02,100
Dabar pirmą kartą, aš galėtų jau
pavadino tai nieko.

565
00:25:02,100 --> 00:25:04,200
Galėjau jį pavadino "sąrašas"
arba bet kitų dalykų skaičius.

566
00:25:04,200 --> 00:25:06,960
Bet aš pavadino jį "pirmas", kad
IT linijos su šiame paveikslėlyje.

567
00:25:06,960 --> 00:25:10,280
Taigi kaip eilutę gali būti atstovaujama
su savo pirmojo baito adresas,

568
00:25:10,280 --> 00:25:11,280
todėl gali susieti sąrašas.

569
00:25:11,280 --> 00:25:13,480
Ir mes pamatyti kitus duomenis
struktūros atstovauja

570
00:25:13,480 --> 00:25:16,700
tik su vienu rodykle,
32 bitų rodyklė, nukreipta

571
00:25:16,700 --> 00:25:18,740
tuo pat pirmojo mazgo struktūrą.

572
00:25:18,740 --> 00:25:20,340
>> Bet dabar tegul numatyti problemų.

573
00:25:20,340 --> 00:25:23,230
Jei aš tik prisiminti
mano programos adreso

574
00:25:23,230 --> 00:25:27,220
pirmojo mazgo, pirmasis
Stačiakampis šios duomenų struktūros,

575
00:25:27,220 --> 00:25:31,760
kas turėjo būti geriau apie bylą
įgyvendinimas mano sąrašo poilsio?

576
00:25:31,760 --> 00:25:35,820
Kas yra raktas detalė, kuri vyksta
Siekiant užtikrinti tai tikrai veikia?

577
00:25:35,820 --> 00:25:39,250
Ir "iš tiesų veikia" Aš
reiškia, panašiai kaip eilutę,

578
00:25:39,250 --> 00:25:42,180
leidžia mums pereiti nuo pirmojo pobūdžio
į Davin vardo į antrąjį,

579
00:25:42,180 --> 00:25:44,755
į trečia,
ketvirta, iki galo,

580
00:25:44,755 --> 00:25:47,880
kaip mes žinome, kai mes pabaigoje
Susietos sąrašą, kuris atrodo taip?

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

582
00:25:50,035 --> 00:25:50,660
Kai jis tuščias.

583
00:25:50,660 --> 00:25:53,640
Ir aš atstovavo šį kaip rūšiuoti
kaip elektromechanikas jėgomis,

584
00:25:53,640 --> 00:25:56,420
su mažai įžeminimo
simbolis, dvasia.

585
00:25:56,420 --> 00:25:58,246
Bet tai tik reiškia, kad niekinis ir šiuo atveju.

586
00:25:58,246 --> 00:26:00,370
Galite piešti tai bet koks skaičius
būdų, bet šis autorius

587
00:26:00,370 --> 00:26:02,800
čia nutiko naudoti šį simbolį.

588
00:26:02,800 --> 00:26:06,260
>> Kol mes apjuostame
visų šių mazgų kartu,

589
00:26:06,260 --> 00:26:08,600
tik prisiminti, kur
Pirmasis yra, kol

590
00:26:08,600 --> 00:26:11,760
kaip mes įdėti specialų simbolį
labai paskutinis mazgas sąraše,

591
00:26:11,760 --> 00:26:15,130
ir mes naudosime null, nes tai
ką mes turime mums prieinama,

592
00:26:15,130 --> 00:26:16,480
šis sąrašas yra išsamus.

593
00:26:16,480 --> 00:26:20,190
Ir net jei tik aš jums žymeklį į
Pirmasis elementas, jūs, programuotojas,

594
00:26:20,190 --> 00:26:22,486
tikrai gali prieiti prie jo pailsėti.

595
00:26:22,486 --> 00:26:24,360
Bet leiskim savo protus
Brody truputį,

596
00:26:24,360 --> 00:26:26,140
jei jie nėra jau
gana wandered-- kas

597
00:26:26,140 --> 00:26:28,723
bus rodomi laikas
rasti nieko šiame sąraše?

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

599
00:26:30,450 --> 00:26:33,470
Velnias ji, tai didelis O n,
kuris nėra blogai, tiesą sakant.

600
00:26:33,470 --> 00:26:34,800
Bet tai yra linijinė.

601
00:26:34,800 --> 00:26:37,980
Prašėme tai, ką funkcija
iš matricos juda daugiau

602
00:26:37,980 --> 00:26:43,130
link šio dinamiškai paveikslėlyje
austi kartu ar susiję mazgai?

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

604
00:26:44,970 --> 00:26:46,687
Mes atsisakė laisvą prieigą.

605
00:26:46,687 --> 00:26:48,770
Masyvas yra gražus, nes
matematiškai viskas

606
00:26:48,770 --> 00:26:50,340
atgal atgal atgal į nugarą.

607
00:26:50,340 --> 00:26:52,370
Nors šioje nuotraukoje
atrodo gana ir net

608
00:26:52,370 --> 00:26:55,830
nors atrodo, kad šiais mazgais
gražiai išdėstyti vienas nuo kito, iš tikrųjų

609
00:26:55,830 --> 00:26:56,830
jie gali būti bet kur.

610
00:26:56,830 --> 00:27:01,590
OX1, Ox50, Ox123, Ox99, tai
mazgai gali būti bet kur.

611
00:27:01,590 --> 00:27:05,960
Kadangi malloc daro paskirstyti atmintį
iš krūvos, tačiau bet kurioje krūvą.

612
00:27:05,960 --> 00:27:09,080
Jūs nebūtinai žino, kad tai
bus grįžti atgal į nugarą.

613
00:27:09,080 --> 00:27:12,460
Ir taip šis vaizdas į tikrovės
nesiruošia būti gana tai gana.

614
00:27:12,460 --> 00:27:16,140
>> Taigi ji ketina imtis šiek tiek
dirbti siekiant įgyvendinti šią funkciją.

615
00:27:16,140 --> 00:27:17,880
Taigi leiskite įgyvendinti paiešką dabar.

616
00:27:17,880 --> 00:27:20,250
Ir mes pamatysime rūšies
protingas būdas tai padaryti.

617
00:27:20,250 --> 00:27:24,660
Taigi, jei aš esu paieškos funkcija ir
Aš davė kintančiais sveikasis skaičius n

618
00:27:24,660 --> 00:27:28,490
ieškoti, reikia žinoti
nauja sintaksė ieškote viduje

619
00:27:28,490 --> 00:27:32,400
statinio ŠTAI
nurodė, kad, norint rasti n.

620
00:27:32,400 --> 00:27:33,210
Taigi leiskite tai padaryti.

621
00:27:33,210 --> 00:27:36,030
>> Taigi, pirmiausia aš ruošiuosi eiti
į priekį ir paskelbti mazgas *.

622
00:27:36,030 --> 00:27:39,400
Ir aš ruošiuosi jį vadiname
žymeklis, tik pagal susitarimą.

623
00:27:39,400 --> 00:27:41,710
Ir aš ruošiuosi inicijuoti ją pirmą kartą.

624
00:27:41,710 --> 00:27:43,770
Ir dabar aš galiu tai padaryti
į įvairiais būdais.

625
00:27:43,770 --> 00:27:45,436
Bet aš ruošiuosi laikytis vienodo požiūrio.

626
00:27:45,436 --> 00:27:50,180
Nors žymeklis nėra lygūs
null, ir tai galioja sintaksė.

627
00:27:50,180 --> 00:27:54,550
Ir tai tiesiog reiškia, atlikite šiuos veiksmus, kad
Tol, kol jūs nesate nukreipta į nieką.

628
00:27:54,550 --> 00:27:55,800
Ką norite daryti?

629
00:27:55,800 --> 00:28:01,939
>> Jei žymeklis taškas n, leiskite man grįžti
į tą, equals-- lygi, ką?

630
00:28:01,939 --> 00:28:03,105
Kokią vertę aš ko ieškote?

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

632
00:28:04,920 --> 00:28:06,590
Tikrasis n, kuris buvo priimtas.

633
00:28:06,590 --> 00:28:09,020
Taigi čia yra kita funkcija
C ir daug kalbų.

634
00:28:09,020 --> 00:28:13,705
Nors struktūros vadinamas mazgu
turi vertę n, visiškai teisėtas

635
00:28:13,705 --> 00:28:17,530
taip pat turėti vietos argumentą
arba kintamas vadinamas n.

636
00:28:17,530 --> 00:28:20,085
Nes net mes, su
žmogaus akis gali atskirti

637
00:28:20,085 --> 00:28:22,087
kad tai n yra turbūt
skiriasi nuo šio n.

638
00:28:22,087 --> 00:28:23,420
Kadangi sintaksė skiriasi.

639
00:28:23,420 --> 00:28:26,211
Jūs turite dot ir rodyklę,
kadangi šis vieną neturi tokio dalyko.

640
00:28:26,211 --> 00:28:27,290
Taigi, tai yra gerai.

641
00:28:27,290 --> 00:28:29,120
Tai gerai, kad juos vadina tuos pačius dalykus.

642
00:28:29,120 --> 00:28:32,380
>> Jei aš jums rasti tai, aš tikiu,
ketinate nori kažką daryti

643
00:28:32,380 --> 00:28:35,000
kaip pranešti, kad mes nustatėme, n.

644
00:28:35,000 --> 00:28:37,930
Ir mes palikti, kad
komentarą arba Pseudocode kodas.

645
00:28:37,930 --> 00:28:40,190
Kita, ir čia
įdomiausia dalis, tai, ką

646
00:28:40,190 --> 00:28:47,320
aš noriu daryti, jei dabartinės mazgo
yra turintis ne n, kad man rūpi?

647
00:28:47,320 --> 00:28:50,700
Kaip man pasiekti šių sričių?

648
00:28:50,700 --> 00:28:53,710
Jei mano pirštas ne
momentas yra PTR, ir tai

649
00:28:53,710 --> 00:28:55,920
nukreipta į ką
Pirmasis yra nukreipta ne,

650
00:28:55,920 --> 00:28:59,290
kaip man perkelti mano pirštą
į kitą mazgas kodą?

651
00:28:59,290 --> 00:29:01,915
Na, kas tinklalapio mes
ketina vadovautis šioje byloje?

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

653
00:29:03,464 --> 00:29:04,380
PUBLIKA: [nesigirdi].

654
00:29:04,380 --> 00:29:05,630
David J. Malan: Taip, todėl kitą.

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

656
00:29:06,640 --> 00:29:09,824
Taigi, jei aš einu atgal į savo
kodas čia, tiesą sakant, aš

657
00:29:09,824 --> 00:29:12,990
ketina eiti į priekį ir pasakyti žymeklį, kuris
yra tik laikinas variable-- tai

658
00:29:12,990 --> 00:29:15,320
Keistas vardas, PTR, bet
tai tiesiog kaip temp--

659
00:29:15,320 --> 00:29:19,234
Aš ruošiuosi nustatyti žymeklį
lygios kokios rodyklės is--

660
00:29:19,234 --> 00:29:22,150
ir vėl, tai bus
tiek Buggy už moment-- tašku kitą.

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

662
00:29:23,551 --> 00:29:26,550
Kitaip tariant, aš ruošiuosi pasiimti savo
pirštu, kad manimi nukreipta į šio mazgo

663
00:29:26,550 --> 00:29:31,247
čia, ir aš ruošiuosi pasakyti, žinote,
ką, pažvelgti į kitą lauką išvaizdą

664
00:29:31,247 --> 00:29:33,330
ir judinkite pirštą
kokia ji nukreipta ne.

665
00:29:33,330 --> 00:29:35,163
Ir tai vyksta
kartoju, kartoju, pakartokite.

666
00:29:35,163 --> 00:29:37,630
Bet kai daro savo pirštą
nustoti daryti ką nors ne visi?

667
00:29:37,630 --> 00:29:40,095
Kaip tik tai, ką linija kodų smūgių į?

668
00:29:40,095 --> 00:29:40,970
PUBLIKA: [nesigirdi]

669
00:29:40,970 --> 00:29:43,060
David J. Malan: Jei taškas, o
žymeklis nėra lygus nuliui.

670
00:29:43,060 --> 00:29:44,900
Tam tikru momentu mano piršto
bus nukreipta į null

671
00:29:44,900 --> 00:29:47,070
ir aš ruošiuosi suvokti
tai šio sąrašo pabaigoje.

672
00:29:47,070 --> 00:29:48,910
Dabar, tai yra šiek tiek
baltas melas paprastumo.

673
00:29:48,910 --> 00:29:51,580
Pasirodo, kad nors mes
ką tik sužinojau šį dot žymėjimą

674
00:29:51,580 --> 00:29:55,220
struktūroms, žymeklis nėra konstrukto.

675
00:29:55,220 --> 00:29:56,580
PTR yra kas?

676
00:29:56,580 --> 00:29:58,350
Tiesiog daugiau nitpicky.

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

678
00:29:59,720 --> 00:30:01,360
Tai rodyklė mazgas.

679
00:30:01,360 --> 00:30:03,120
Tai nėra pats mazgas.

680
00:30:03,120 --> 00:30:06,650
Jeigu aš neturėjo žvaigždę čia, žymeklis
absolutely-- tai mazgas.

681
00:30:06,650 --> 00:30:08,650
Tai kaip savaitę vienu
deklaracija kintamojo,

682
00:30:08,650 --> 00:30:10,120
nors žodis "mazgas" yra nauja.

683
00:30:10,120 --> 00:30:13,860
>> Bet kaip tik mes pristatome
žvaigždė, tai dabar žymiklį į mazgą.

684
00:30:13,860 --> 00:30:17,960
Ir, deja, jūs negalite naudoti
dot notacijos už rodykle.

685
00:30:17,960 --> 00:30:21,070
Jūs turite naudoti rodyklę
žymėjimas, kuris, stulbinamai,

686
00:30:21,070 --> 00:30:23,470
yra pirmas kartas, bet gabalas
sintaksė atrodo intuityvus.

687
00:30:23,470 --> 00:30:25,245
Tai tiesiog atrodo kaip strėlė.

688
00:30:25,245 --> 00:30:26,370
Ir taip, kad tai geras dalykas.

689
00:30:26,370 --> 00:30:28,995
Ir žemyn čia pažodžiui
atrodo kaip strėlė.

690
00:30:28,995 --> 00:30:31,870
Taigi, aš manau, kad tai la-- aš ne
manau, kad aš per įsipareigojant here-- aš

691
00:30:31,870 --> 00:30:34,120
manau, kad tai paskutinis naujasis kūrinys
Sintaksės mes ketiname pamatyti.

692
00:30:34,120 --> 00:30:36,500
Ir laimei, tai iš tiesų
šiek tiek daugiau intuityvus.

693
00:30:36,500 --> 00:30:40,090
>> Dabar, tiems iš jūsų, kurie
norėti senas būdas,

694
00:30:40,090 --> 00:30:42,550
Jūs vis dar galite naudoti taškinę notacijos.

695
00:30:42,550 --> 00:30:45,380
Bet kaip už pirmadienį
pokalbis, mes pirmiausia

696
00:30:45,380 --> 00:30:50,530
reikia eiti ten, eikite į, kad
spręsti, o tada prisijungti prie lauką.

697
00:30:50,530 --> 00:30:51,897
Taigi tai taip pat teisinga.

698
00:30:51,897 --> 00:30:53,730
Ir tiesą sakant, tai yra
šiek tiek daugiau pedantiškas.

699
00:30:53,730 --> 00:30:56,530
Jūs tiesiog sakydamas, dereference
žymeklis ir ten.

700
00:30:56,530 --> 00:30:59,320
Tada patraukti .n, laukas vadinamas n.

701
00:30:59,320 --> 00:31:01,370
Bet tiesą sakant, niekas nenori
tipo ar skaityti.

702
00:31:01,370 --> 00:31:03,620
Ir taip pasaulis išrado
rodyklė žymėjimas, kuris

703
00:31:03,620 --> 00:31:06,980
yra lygiavertis, vienodi,
tai tik sintaksinė cukrus.

704
00:31:06,980 --> 00:31:10,570
Taigi išgalvotas būdas pasakyti tai
atrodo geriau, arba atrodo paprastesnis.

705
00:31:10,570 --> 00:31:12,296
>> Taigi, dabar aš ruošiuosi daryti vieną kitą dalyką.

706
00:31:12,296 --> 00:31:15,420
Aš ruošiuosi pasakyti "pertrauką", kai aš
radau, kad aš ne nuolat ieško už jį.

707
00:31:15,420 --> 00:31:17,620
Bet tai esmė
iš paieškos funkcija.

708
00:31:17,620 --> 00:31:21,710
Bet tai daug lengviau, ir
pabaigos, o ne vaikščioti per kodą.

709
00:31:21,710 --> 00:31:25,570
Tai iš tiesų oficialus įgyvendinimas
Paieškos šiandienos platinimo kodas.

710
00:31:25,570 --> 00:31:30,530
Drįstu pasakyti, kad įterpti nėra
ypač smagu pasivaikščioti

711
00:31:30,530 --> 00:31:33,180
vizualiai, nei trinti, net
nors ne dienos pabaigoje

712
00:31:33,180 --> 00:31:35,460
jie skliautais į gana
paprasti euristika.

713
00:31:35,460 --> 00:31:36,330
>> Taigi leiskite tai padaryti.

714
00:31:36,330 --> 00:31:39,250
Jei jūs humoras man čia, aš
pareikšti streso kamuoliukus krūva.

715
00:31:39,250 --> 00:31:40,620
Aš išvedžiau numerių krūva.

716
00:31:40,620 --> 00:31:46,562
Ir mes galėtume gauti tik keletą savanorių
atstovauti 9, 17, 20, 22, 29 ir 34?

717
00:31:46,562 --> 00:31:48,270
Taigi, iš esmės visi
kas čia šiandien.

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

719
00:31:50,170 --> 00:31:52,760
Tai buvo vienas, du, trys,
keturių, penkių, šešių žmonių.

720
00:31:52,760 --> 00:31:55,740
Ir aš buvo paprašyta go-- pamatyti, ne
vienas gale kelia savo rankas.

721
00:31:55,740 --> 00:32:01,910
Gerai, vienas, du, trys, keturi
five-- leiskite įkelti balance-- šešis.

722
00:32:01,910 --> 00:32:03,051
Gerai, jūs šešių ateiti iki.

723
00:32:03,051 --> 00:32:04,050
Mums reikia kitų žmonių.

724
00:32:04,050 --> 00:32:05,460
Mes atnešė papildomų streso kamuolius.

725
00:32:05,460 --> 00:32:08,200
Ir jei galėtų,
tiesiog akimirka, linija

726
00:32:08,200 --> 00:32:10,490
patys sukuria tik
kaip pavaizduota šiame paveikslėlyje čia.

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

728
00:32:15,200 --> 00:32:15,959
>> Viskas gerai.

729
00:32:15,959 --> 00:32:17,125
Pažiūrėkime, koks tavo vardas?

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

731
00:32:17,550 --> 00:32:18,800
>> David J. Malan: Andriejus,
Jūs esate numeris 9.

732
00:32:18,800 --> 00:32:19,540
Nice to meet you.

733
00:32:19,540 --> 00:32:20,400
Čia jūs einate.

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

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

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

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

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

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

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

741
00:32:25,450 --> 00:32:26,400
>> PUBLIKA: Aš Julija.

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

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

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

745
00:32:28,507 --> 00:32:29,340
PUBLIKA: krikščionis.

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

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

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

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

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

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

752
00:32:34,880 --> 00:32:37,080
Taigi pirmyn ir gauti in-- Uh oh.

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

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

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

756
00:32:39,650 --> 00:32:40,150
Budėjimo.

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
Ar kas nors turite žymeklį?

760
00:32:43,682 --> 00:32:44,890
PUBLIKA: Aš turiu Sharpie.

761
00:32:44,890 --> 00:32:45,660
David J. Malan: Tu turi Sharpie?

762
00:32:45,660 --> 00:32:46,159
Gerai.

763
00:32:46,159 --> 00:32:47,577

764
00:32:47,577 --> 00:32:49,160
Ir ar kas nors turi popierėlį?

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

766
00:32:51,562 --> 00:32:52,270
Išsaugoti paskaitą.

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

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

769
00:32:55,362 --> 00:32:56,320
PUBLIKA: Mes gavo jį.

770
00:32:56,320 --> 00:32:57,600
David J. Malan: Mes jį gavo?

771
00:32:57,600 --> 00:32:58,577
Gerai, ačiū.

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

773
00:33:01,380 --> 00:33:02,520
Here we go.

774
00:33:02,520 --> 00:33:03,582
Ar tai buvo pas jus?

775
00:33:03,582 --> 00:33:04,540
Jūs tiesiog išgelbėjo dieną.

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

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

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

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

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

781
00:33:13,360 --> 00:33:14,890
Aš klaidomis 29, bet gerai.

782
00:33:14,890 --> 00:33:15,720
Eiti į priekį.

783
00:33:15,720 --> 00:33:18,114
Gerai, aš duosiu jums
švirkštimo atgal trumpam.

784
00:33:18,114 --> 00:33:19,280
Taigi, mes turime šie žmonės čia.

785
00:33:19,280 --> 00:33:20,330
Leiskite turėti vieną kitą.

786
00:33:20,330 --> 00:33:23,750
Gabe, tu nori žaisti
Pirmasis elementas čia?

787
00:33:23,750 --> 00:33:25,705
Mes turime jums atkreipti
Šiuose smulkių žmonės.

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

789
00:33:26,930 --> 00:33:31,030
Taigi 9, 17, 20, 22, tarsi
29, ir tada 34.

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

791
00:33:32,160 --> 00:33:33,325
Ar mes prarasti ką nors?

792
00:33:33,325 --> 00:33:33,950
Aš turiu 34.

793
00:33:33,950 --> 00:33:36,730
Kur did-- Gerai, kas nori būti 34?

794
00:33:36,730 --> 00:33:37,605
Gerai, nagi iki 34.

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

796
00:33:39,280 --> 00:33:41,220
Gerai, tai bus
verta kulminacija.

797
00:33:41,220 --> 00:33:41,550
Koks tavo vardas?

798
00:33:41,550 --> 00:33:42,040
>> PUBLIKA: Petras.

799
00:33:42,040 --> 00:33:43,456
>> David J. Malan: Petras, nagi iki.

800
00:33:43,456 --> 00:33:46,810
Gerai, kad čia
visa krūva mazgų.

801
00:33:46,810 --> 00:33:49,060
Kiekvienas iš jūsų vaikinai yra
vienas iš šių stačiakampių.

802
00:33:49,060 --> 00:33:51,930
Ir Gabe, šiek tiek keista,
žmogus iš, atstovauja pirmasis.

803
00:33:51,930 --> 00:33:54,850
Taigi jo žymeklis tiek mažesnis
ant nei visi kiti ekrane.

804
00:33:54,850 --> 00:33:58,120
Ir šiuo atveju kiekviena kaire
rankos ketina arba atkreipti žemyn,

805
00:33:58,120 --> 00:34:01,085
taip atstovaujanti nuliui, todėl
tik iš rodyklės nebuvimas,

806
00:34:01,085 --> 00:34:03,210
ar ji bus nukreipta
ne mazgas šalia jūsų.

807
00:34:03,210 --> 00:34:05,440
>> Taigi dabar, jei jūs puošia
patys, kaip paveikslėlyje

808
00:34:05,440 --> 00:34:07,585
čia, eikite į priekį ir taškas
vienas į kitą, su Gabe

809
00:34:07,585 --> 00:34:11,030
ypač nukreipta į
numeris 9 atstovauti sąrašą.

810
00:34:11,030 --> 00:34:14,050
Gerai, numeris 34, jūsų kairė ranka
tiesiog reikia būti nukreipta į grindis.

811
00:34:14,050 --> 00:34:15,750
>> Gerai, kad tai yra susiję sąrašas.

812
00:34:15,750 --> 00:34:17,580
Taigi tai yra tas scenarijus.

813
00:34:17,580 --> 00:34:20,210
Ir iš tiesų, tai yra atstovas
iš problemų klasei

814
00:34:20,210 --> 00:34:21,929
kad jūs galite pabandyti išspręsti su kodu.

815
00:34:21,929 --> 00:34:25,020
Jūs norite, kad galiausiai įterpti
naujas elementas į sąrašą.

816
00:34:25,020 --> 00:34:27,494
Tokiu atveju, mes ketiname
pabandykite įdėti skaičių 55.

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

818
00:34:28,500 --> 00:34:30,860
Bet ten bus
skirtingus atvejus apsvarstyti.

819
00:34:30,860 --> 00:34:34,409
Ir iš tiesų, tai bus vienas
iš didelis-picture takeaways čia yra,

820
00:34:34,409 --> 00:34:35,659
kas yra skirtingų atvejų.

821
00:34:35,659 --> 00:34:39,120
Kas yra, jei sąlygomis arba skirtingi
filialai, kad jūsų programa gali turėti?

822
00:34:39,120 --> 00:34:42,024
>> Na, numeris, kurį bandote
įterpti, kurį mes dabar žinome, kad 55,

823
00:34:42,024 --> 00:34:44,650
bet jei jūs nežinote,
iš anksto, aš Manyti

824
00:34:44,650 --> 00:34:47,840
patenka į mažiausiai trijų
galimi atvejai.

825
00:34:47,840 --> 00:34:49,717
Jeigu naujasis elementas gali būti?

826
00:34:49,717 --> 00:34:51,050
PUBLIKA: Ir pabaigoje ar viduryje.

827
00:34:51,050 --> 00:34:54,150
David J. Malan: Tuo tikslu,
viduryje ar pradžioje.

828
00:34:54,150 --> 00:34:56,650
Taigi galiu reikalauti ten bent
trys problemos turime spręsti.

829
00:34:56,650 --> 00:34:58,691
Leiskite pasirinkti tai, kas galbūt
be abejo, paprasčiausias

830
00:34:58,691 --> 00:35:01,090
vienas, kur naująjį elementą
priklauso pradžioje.

831
00:35:01,090 --> 00:35:04,040
Taigi, aš ruošiuosi kodą gana
kaip ieškoti, kurį aš ką tik parašė.

832
00:35:04,040 --> 00:35:07,670
Ir aš ruošiuosi PTR, kuris
Aš atstovauti čia su mano pirštu,

833
00:35:07,670 --> 00:35:08,370
kaip įprasta.

834
00:35:08,370 --> 00:35:12,430
>> Ir atminkite, kas vertė
Ar mes inicijuoti PTR prie?

835
00:35:12,430 --> 00:35:15,300
Taigi, mes inicializuoti jį null pradžių.

836
00:35:15,300 --> 00:35:16,410

837
00:35:16,410 --> 00:35:19,770
Bet tada ką gi mes darome, kai mes
buvo viduje mūsų paieškos funkcija?

838
00:35:19,770 --> 00:35:20,940

839
00:35:20,940 --> 00:35:24,870
Mes nustatėme, kad lygi pirma,
tačiau tai nereiškia, tai daryti.

840
00:35:24,870 --> 00:35:25,890

841
00:35:25,890 --> 00:35:30,570
Jei aš nustatyti PTR lygią, pirma, ką
turėtų mano ranka tikrai nukreipta į?

842
00:35:30,570 --> 00:35:31,070
Teisė.

843
00:35:31,070 --> 00:35:33,290
Taigi, jei Gabe ir aš ketinate
būti lygios vertės čia

844
00:35:33,290 --> 00:35:34,760
turime tiek taško numeris 9.

845
00:35:34,760 --> 00:35:36,420
>> Taigi, tai buvo mūsų istorijos pradžia.

846
00:35:36,420 --> 00:35:38,700
O dabar tai tik paprasta,
nors sintaksė yra nauja.

847
00:35:38,700 --> 00:35:40,580
Konceptualiai tai tik linijinis paieška.

848
00:35:40,580 --> 00:35:42,750
Ar 55 lygi 9?

849
00:35:42,750 --> 00:35:45,559
Arba, o, tarkime, mažiau nei 9.

850
00:35:45,559 --> 00:35:47,600
Nes aš bandau
išsiaiškinti, kur dėti 55.

851
00:35:47,600 --> 00:35:51,270
Mažiau nei 9, yra mažesnis kaip 17, mažiau
kaip 20 ir mažiau kaip 22 ir mažiau kaip 29,

852
00:35:51,270 --> 00:35:52,510
mažesnis kaip 34, Nr.

853
00:35:52,510 --> 00:35:55,080
Taigi dabar mes atveju
viena iš mažiausiai trijų.

854
00:35:55,080 --> 00:35:59,910
>> Jei aš noriu įterpti 55 per čia, ką
kodo eilutes reikia gauti įvykdytas?

855
00:35:59,910 --> 00:36:01,890
Kaip veikia šį paveikslėlį
žmonės turi keisti?

856
00:36:01,890 --> 00:36:03,181
Ką man daryti su savo kaire ranka?

857
00:36:03,181 --> 00:36:04,530

858
00:36:04,530 --> 00:36:07,360
Tai turėtų būti niekinis pradžių,
nes aš ne sąrašo pabaigoje.

859
00:36:07,360 --> 00:36:09,318
Ir kas turėtų atsitikti,
čia su Petru, tai buvo?

860
00:36:09,318 --> 00:36:10,520

861
00:36:10,520 --> 00:36:12,430
Jis akivaizdžiai ketina atkreipti dėmesį į mane.

862
00:36:12,430 --> 00:36:15,580
Taigi galiu reikalauti ten bent dvi eilutės
kodo mėginio kodą iš šiandien

863
00:36:15,580 --> 00:36:18,570
kad ketina įgyvendinti šį
scenarijus pridedant 55 ne uodega.

864
00:36:18,570 --> 00:36:20,950
Ir aš galėčiau ką nors hop
aukštyn ir tik atstovauti 55?

865
00:36:20,950 --> 00:36:22,200
Gerai, jūs esate nauja 55.

866
00:36:22,200 --> 00:36:23,580

867
00:36:23,580 --> 00:36:27,054
>> Taigi dabar ką daryti, jei šalia
scenarijus ateina kartu,

868
00:36:27,054 --> 00:36:29,720
ir mes norime įterpti ne
pradedant arba šio sąrašo galva?

869
00:36:29,720 --> 00:36:31,100
Ir koks tavo vardas, numeris 55?

870
00:36:31,100 --> 00:36:31,420
>> PUBLIKA: Džekas.

871
00:36:31,420 --> 00:36:32,295
>> David J. Malan: Jack?

872
00:36:32,295 --> 00:36:33,585
Gerai, nice to meet you.

873
00:36:33,585 --> 00:36:34,210
Sveiki atvykę į laivą.

874
00:36:34,210 --> 00:36:36,640
Taigi dabar mes ketiname
įdėti, tarkim, skaičius 5.

875
00:36:36,640 --> 00:36:39,840
Štai antras atvejis
trijų mes atėjo su anksčiau.

876
00:36:39,840 --> 00:36:43,050
Taigi, jei 5 priklauso pradžioje,
pažiūrėkime, kaip mes matome, kad iš.

877
00:36:43,050 --> 00:36:46,310
Aš inicijuoti savo PTR
rodyklė numeris 9 kartą.

878
00:36:46,310 --> 00:36:49,140
Ir aš supratau, oi, 5 yra mažesnis kaip 9.

879
00:36:49,140 --> 00:36:50,880
Taigi nustatyti šią nuotrauką mums.

880
00:36:50,880 --> 00:36:54,820
Kieno rankos, Gabe s ar Dovydo
or-- kas numeris 9 vardas?

881
00:36:54,820 --> 00:36:55,740
>> PUBLIKA: Jen.

882
00:36:55,740 --> 00:36:58,406
>> David J. Malan: Jen hands--
kuris iš mūsų rankų reikia pakeisti?

883
00:36:58,406 --> 00:36:58,905

884
00:36:58,905 --> 00:37:00,970
Gerai, kad Gabe nurodo ne tai, ką dabar?

885
00:37:00,970 --> 00:37:01,640
Tuo mane.

886
00:37:01,640 --> 00:37:02,750
Esu naujas mazgas.

887
00:37:02,750 --> 00:37:04,870
Taigi aš tiesiog rūšies perkelti
Čia matyti vizualiai.

888
00:37:04,870 --> 00:37:06,435
Ir tuo tarpu ką man atkreipti, kad?

889
00:37:06,435 --> 00:37:07,910

890
00:37:07,910 --> 00:37:09,020
Vis kur aš nukreipta.

891
00:37:09,020 --> 00:37:10,000
Taigi, kad viskas.

892
00:37:10,000 --> 00:37:13,717
Taigi tiesiog tikrai viena eilutė kodo pataisymai
šis konkretus klausimas, atrodo.

893
00:37:13,717 --> 00:37:14,800
Gerai, kad tai gerai.

894
00:37:14,800 --> 00:37:17,580
Ir gali kas nors būti dėl 5 vietos rezervavimo ženklas?

895
00:37:17,580 --> 00:37:18,080
Nagi iki.

896
00:37:18,080 --> 00:37:20,270

897
00:37:20,270 --> 00:37:21,320
Mes jums kitą kartą.

898
00:37:21,320 --> 00:37:24,280
>> Gerai, kad now-- ir
kaip panaikinti, pavadinimų

899
00:37:24,280 --> 00:37:28,510
Aš ne padaryti aiškų paminėti teisės
dabar pred žymeklis, žymeklis pirmtakas

900
00:37:28,510 --> 00:37:31,260
ir naujos žymeklis, tai
tik pavadinimai suteikta

901
00:37:31,260 --> 00:37:35,280
mėginio kodą į rodyklės arba
mano rankos, kad manimi rūšies nukreipta aplink.

902
00:37:35,280 --> 00:37:36,060
Koks tavo vardas?

903
00:37:36,060 --> 00:37:36,700
>> PUBLIKA: Christine.

904
00:37:36,700 --> 00:37:37,100
>> David J. Malan Christine.

905
00:37:37,100 --> 00:37:38,090
Sveiki atvykę į laivą.

906
00:37:38,090 --> 00:37:42,180
Visos teisės, todėl aptarkime dabar
šiek tiek labiau erzina scenarijus,

907
00:37:42,180 --> 00:37:46,350
, kuriuo noriu įterpti
kažkas panašaus į 26 į tai.

908
00:37:46,350 --> 00:37:47,090
20?

909
00:37:47,090 --> 00:37:47,590
Ką?

910
00:37:47,590 --> 00:37:50,510
Tai are-- geras dalykas, mes turime šį rašiklį.

911
00:37:50,510 --> 00:37:51,955
Visos teisės 20.

912
00:37:51,955 --> 00:37:53,640

913
00:37:53,640 --> 00:37:57,570
Jei kas nors galėtų gauti kitą gabalas
popieriaus pasiruošę, tik case-- viskas gerai.

914
00:37:57,570 --> 00:37:58,370
O, įdomu.

915
00:37:58,370 --> 00:37:59,760

916
00:37:59,760 --> 00:38:02,390
Na tai pavyzdys
iš paskaitų klaidą.

917
00:38:02,390 --> 00:38:03,894
Gerai, kad tai, kas tavo vardas?

918
00:38:03,894 --> 00:38:04,560
PUBLIKA: Julija.

919
00:38:04,560 --> 00:38:07,559
David J. Malan: Julija, jūs galite pop
iš ir apsimesti, jūs niekada nebuvo ten?

920
00:38:07,559 --> 00:38:09,040
Gerai, tai niekada neįvyko.

921
00:38:09,040 --> 00:38:09,680
Ačiū.

922
00:38:09,680 --> 00:38:12,180
Taigi tarkime, kad mes norime įterpti
Julija į šią susietą sąrašą.

923
00:38:12,180 --> 00:38:13,780
Ji yra skaičius 20.

924
00:38:13,780 --> 00:38:15,530
Ir, žinoma, ji
ketina priklausyti ne

925
00:38:15,530 --> 00:38:17,521
begin-- nenukreipkite į ką nors dar.

926
00:38:17,521 --> 00:38:20,020
Taigi jūsų ranka gali rūšies būti
žemyn null arba kai šiukšlių vertė.

927
00:38:20,020 --> 00:38:21,210
Leiskite papasakoti greitai istoriją.

928
00:38:21,210 --> 00:38:22,980
Aš nukreipta į 5 numeriu šį kartą.

929
00:38:22,980 --> 00:38:23,880
Tada aš patikrinti 9.

930
00:38:23,880 --> 00:38:25,130
Tada aš patikrinti 17.

931
00:38:25,130 --> 00:38:26,247
Tada aš patikrinti 22.

932
00:38:26,247 --> 00:38:27,650

933
00:38:27,650 --> 00:38:32,485
Ir aš suprantu,, ooh, Julia
turi eiti prieš 22.

934
00:38:32,485 --> 00:38:33,580

935
00:38:33,580 --> 00:38:34,660
Taigi, kas turi įvykti?

936
00:38:34,660 --> 00:38:35,786

937
00:38:35,786 --> 00:38:36,910
Kieno rankos reikia pakeisti?

938
00:38:36,910 --> 00:38:38,360
Julija, mano, or--
koks tavo vardas dar kartą?

939
00:38:38,360 --> 00:38:39,230
>> PUBLIKA: krikščionis.

940
00:38:39,230 --> 00:38:40,060
>> David J. Malan: Christian arba?

941
00:38:40,060 --> 00:38:40,560
>> PUBLIKA: Andy.

942
00:38:40,560 --> 00:38:40,905
>> David J. Malan Andy.

943
00:38:40,905 --> 00:38:41,654
Krikščionių ar Andy?

944
00:38:41,654 --> 00:38:44,280

945
00:38:44,280 --> 00:38:45,690
Andy reikia atkreipti dėmesį į?

946
00:38:45,690 --> 00:38:46,780

947
00:38:46,780 --> 00:38:47,341
Julija.

948
00:38:47,341 --> 00:38:47,840
Viskas gerai.

949
00:38:47,840 --> 00:38:48,960
Taigi Andy norite atkreipti dėmesį į Julia?

950
00:38:48,960 --> 00:38:50,120
Bet palauk.

951
00:38:50,120 --> 00:38:53,260
Į istoriją iki šiol,
Aš vienokį

952
00:38:53,260 --> 00:38:56,800
atsakingas, ta prasme, kad
žymeklis yra dalykas, kad

953
00:38:56,800 --> 00:38:57,850
juda per sąrašą.

954
00:38:57,850 --> 00:39:00,800
Mes gali turėti Andy vardą, bet
ten ne kintamasis vadinamas Andy.

955
00:39:00,800 --> 00:39:04,320
Vienintelis kitas kintamasis mes turime, yra
pirma, kas atstovauja Gabe.

956
00:39:04,320 --> 00:39:07,690
>> Taigi iš tikrųjų tai yra, kodėl taip
šiol mes nereikia tai.

957
00:39:07,690 --> 00:39:10,846
Bet dabar ekrane yra
paminėti vėl pred rodyklė.

958
00:39:10,846 --> 00:39:11,970
Taigi leiskite man būti aiškesnis.

959
00:39:11,970 --> 00:39:14,820
Jei tai yra žymeklis, turėjau geriau
gauti šiek tiek daugiau protingas

960
00:39:14,820 --> 00:39:15,950
apie mano iteracijos.

961
00:39:15,950 --> 00:39:19,580
Jei jūs neprieštaraujate, mano išgyvena čia
vėl, nurodydama čia, rodydamas čia.

962
00:39:19,580 --> 00:39:22,500
Bet leiskite man turėti pred žymeklį,
pirmtakas žymeklis, tai

963
00:39:22,500 --> 00:39:24,740
rūšies nukreipta į
elementas buvau tiesiog ne.

964
00:39:24,740 --> 00:39:27,330
Taigi, kai aš einu čia, dabar
mano kairė ranka atnaujinimai.

965
00:39:27,330 --> 00:39:29,370
Kai aš einu čia mano kairė ranka atnaujinimus.

966
00:39:29,370 --> 00:39:33,090
Ir dabar turiu ne tik žymiklį į
elementas, kuris eina po Julija

967
00:39:33,090 --> 00:39:36,300
Aš vis dar turiu žymiklį į
Andy, elementas anksčiau.

968
00:39:36,300 --> 00:39:39,430
Taigi, jūs turite prieigą, iš esmės,
džiūvėsėliai, jei norite,

969
00:39:39,430 --> 00:39:41,500
visiems būtinų patarimų.

970
00:39:41,500 --> 00:39:43,710
>> Taigi, jei aš nukreipta į
Andy ir aš taip pat nukreipta

971
00:39:43,710 --> 00:39:47,105
ne krikščionis, kurio rankos
dabar reikėtų pažymėti kitur?

972
00:39:47,105 --> 00:39:48,770

973
00:39:48,770 --> 00:39:51,960
Taigi Andy dabar gali nurodyti ne Julija.

974
00:39:51,960 --> 00:39:54,460
Julija, dabar gali būti nukreiptas krikščionis.

975
00:39:54,460 --> 00:39:56,950
Nes ji gali nukopijuoti mano
dešinė yra žymeklis.

976
00:39:56,950 --> 00:40:00,044
Ir, kad būtų veiksmingai suteikia jums
atgal į šitą vietą čia.

977
00:40:00,044 --> 00:40:02,460
Taigi trumpai tariant, nors tai
veda mus rūšies amžinai

978
00:40:02,460 --> 00:40:04,510
faktiškai atnaujinti
susiję sąrašą, reikia suprasti,

979
00:40:04,510 --> 00:40:06,580
kad operacijos
yra gana paprasta.

980
00:40:06,580 --> 00:40:10,030
Tai vienas, du, trys
eilučių kodo galiausiai.

981
00:40:10,030 --> 00:40:12,780
Bet apvyniotas aplink tie
eilučių kodo greičiausiai tai

982
00:40:12,780 --> 00:40:16,350
yra logikos tiek, kad būtų veiksmingai
klausia, kur mes esame?

983
00:40:16,350 --> 00:40:18,970
Ar mes iš pradžių,
viduryje arba pabaigoje?

984
00:40:18,970 --> 00:40:21,890
>> Dabar yra žinoma, kai kurie kiti
operacijos, mes galime įgyvendinti.

985
00:40:21,890 --> 00:40:24,880
Ir šios nuotraukos čia tik vaizduoja
ką tik padarė su žmonėmis.

986
00:40:24,880 --> 00:40:26,080
Ką apie pašalinimo?

987
00:40:26,080 --> 00:40:30,650
Jei aš noriu, pavyzdžiui,
pašalinti numerį 34 arba 55,

988
00:40:30,650 --> 00:40:34,680
Aš gali turėti tos pačios rūšies kodas,
bet aš ruošiuosi reikia vieną ar du žingsnius.

989
00:40:34,680 --> 00:40:36,110
Nes tai, kas naujo?

990
00:40:36,110 --> 00:40:40,460
Jei aš pašalinti ką nors pabaigoje,
kaip skaičius 55 ir tada 34,

991
00:40:40,460 --> 00:40:42,995
kas taip pat turi keistis, nes aš tai darau?

992
00:40:42,995 --> 00:40:44,870
Turiu ne evict--
koks tavo vardas dar kartą?

993
00:40:44,870 --> 00:40:45,380
>> PUBLIKA: Džekas.

994
00:40:45,380 --> 00:40:46,255
>> David J. Malan: Džekas.

995
00:40:46,255 --> 00:40:49,770
Turiu ne tik evict-- nemokamai Jack
taip tiesiog skambinti nemokamai Jack, arba bent jau

996
00:40:49,770 --> 00:40:53,530
ten žymeklis taip pat, bet dabar
ką reikia keisti su Petru?

997
00:40:53,530 --> 00:40:55,510
Jo ranka geriau pradėti nukreipta žemyn.

998
00:40:55,510 --> 00:40:59,300
Nes kaip tik aš skambinti nemokamai
Džekas, jei Petro dar nukreipta į Jack

999
00:40:59,300 --> 00:41:02,530
ir aš, todėl išlaikyti važiuojantiems
sąrašas ir galimybė tai žymeklis,

1000
00:41:02,530 --> 00:41:05,650
kad, kai mūsų senas draugas segmentavimas
kaltės iš tiesų gali mesti į.

1001
00:41:05,650 --> 00:41:07,860
Kadangi mes jau davė
atminties atgal į Jack.

1002
00:41:07,860 --> 00:41:10,760
>> Galite likti čia
nerangiai tik už akimirką.

1003
00:41:10,760 --> 00:41:13,410
Kadangi mes turime tik pora
baigiamosios operacijos apsvarstyti.

1004
00:41:13,410 --> 00:41:15,600
Pašalinus sąraše galvą,
arba beginning-- ir tai vienas s

1005
00:41:15,600 --> 00:41:16,349
šiek tiek erzina.

1006
00:41:16,349 --> 00:41:19,640
Kadangi mes turime žinoti, kad Gabe
rūšies specialius šios programos.

1007
00:41:19,640 --> 00:41:21,440
Nes iš tiesų, jis turi savo žymeklį.

1008
00:41:21,440 --> 00:41:24,860
Jis ne tik yra nurodė,
kaip beveik visi kiti čia.

1009
00:41:24,860 --> 00:41:28,112
>> Taigi, kai sąrašo galva
pašalinti, kurios rankos reikia keisti dabar?

1010
00:41:28,112 --> 00:41:29,070
Koks tavo vardas dar kartą?

1011
00:41:29,070 --> 00:41:29,450
>> PUBLIKA: Christine.

1012
00:41:29,450 --> 00:41:31,408
>> David J. Malan: Aš baisu
ne pavadinimus, matyt.

1013
00:41:31,408 --> 00:41:34,011
Taigi Christine ir Gabe,
kieno rankas reikia pakeisti

1014
00:41:34,011 --> 00:41:36,510
kai mes bandome pašalinti Christine,
skaičius 5, nuo paveikslėlyje?

1015
00:41:36,510 --> 00:41:37,550

1016
00:41:37,550 --> 00:41:38,820
Gerai, kad galime padaryti Gabe.

1017
00:41:38,820 --> 00:41:40,950
Gabe vyksta į tašką,
matyt, numeriu 9.

1018
00:41:40,950 --> 00:41:42,230

1019
00:41:42,230 --> 00:41:44,642
Bet ką kitą turėtų atsitikti?

1020
00:41:44,642 --> 00:41:46,600
PUBLIKA: Christine turėtų
yra niekinis [nesigirdi].

1021
00:41:46,600 --> 00:41:50,244
David J. Malan: Gerai, mes tikriausiai turėtų
make-- išgirdau "nulis" kažkur.

1022
00:41:50,244 --> 00:41:51,410
PUBLIKA: Null ir be jos.

1023
00:41:51,410 --> 00:41:51,855
David J. Malan: NULL ką?

1024
00:41:51,855 --> 00:41:53,074
PUBLIKA: Null ir be jos.

1025
00:41:53,074 --> 00:41:54,490
David J. Malan: Null ir be jos.

1026
00:41:54,490 --> 00:41:55,422
Taigi, tai yra labai lengva.

1027
00:41:55,422 --> 00:41:58,380
Ir tai puikus, kad jūs dabar tarsi
Nuolatinių ten, nepriklausančios.

1028
00:41:58,380 --> 00:42:00,430
Kadangi jūs buvote
atsietas nuo sąrašo.

1029
00:42:00,430 --> 00:42:02,820
Jūs efektyviai buvo
našlaičiai iš sąrašo.

1030
00:42:02,820 --> 00:42:07,770
Ir todėl mes turėjome geriau skambinti nemokamai dabar
Christine duoti tą atmintį atgal.

1031
00:42:07,770 --> 00:42:10,240
Priešingu atveju, kiekvieną kartą mes
trinti mazgas iš sąrašo

1032
00:42:10,240 --> 00:42:14,230
mes galime būti padaryti sąrašą
trumpesnis, bet ne iš tikrųjų mažėja

1033
00:42:14,230 --> 00:42:15,096
atminties dydis.

1034
00:42:15,096 --> 00:42:17,720
Ir taip, jei mes nuolat pridedant ir
pridurdamas, kad pridedant dalykų sąrašą,

1035
00:42:17,720 --> 00:42:19,280
mano kompiuteris gali gauti lėčiau
ir lėčiau ir lėčiau,

1036
00:42:19,280 --> 00:42:21,740
nes aš senka
atminties, net jei aš ne iš tikrųjų

1037
00:42:21,740 --> 00:42:25,580
naudojant Christine baitų
atminties nebėra.

1038
00:42:25,580 --> 00:42:28,500
>> Taigi, galų gale, yra ir kitų
scenarijai, kurių course-- šalinimas

1039
00:42:28,500 --> 00:42:30,640
viduryje, šalinimas
pabaigoje, kaip mes matėme.

1040
00:42:30,640 --> 00:42:32,348
Bet įdomiau
Dabar iškilęs uždavinys yra

1041
00:42:32,348 --> 00:42:34,770
bus apsvarstyti tiksliai
ką veikia laikas yra.

1042
00:42:34,770 --> 00:42:36,640
Taigi ne tik jūs galite išsaugoti savo
popieriaus lapų, jei Gabe,

1043
00:42:36,640 --> 00:42:38,640
jūs neprieštaraujate suteikiant
kiekvienas stresas kamuoliukas.

1044
00:42:38,640 --> 00:42:42,100
Labai ačiū mūsų susietą sąrašą
Savanorių čia, jei galėtų.

1045
00:42:42,100 --> 00:42:45,320
>> [Plojimai]

1046
00:42:45,320 --> 00:42:46,700
>> David J. Malan: Gerai.

1047
00:42:46,700 --> 00:42:51,110
Taigi iš analitinė pora
klausimai Tada, jei galėčiau.

1048
00:42:51,110 --> 00:42:59,670
Mes matėme šį žymėjimą anksčiau,
didelis O ir omega, viršutinių ribų

1049
00:42:59,670 --> 00:43:02,520
ir apatinė ribos dėl
važiavimo laikas kai kurių algoritmas.

1050
00:43:02,520 --> 00:43:04,950
Taigi aptarkime tik
klausimų pora.

1051
00:43:04,950 --> 00:43:07,090
>> Vienas iš jų, ir mes jį sakė
prieš, o kas veikia

1052
00:43:07,090 --> 00:43:10,647
laikas ieškoti
sąrašas pagal stambiojo O?

1053
00:43:10,647 --> 00:43:13,480
Kas viršutinė riba nuo važiavimo
laikas ieškoti susietą sąrašą

1054
00:43:13,480 --> 00:43:16,340
kaip įgyvendinamos mūsų savanoriai čia?

1055
00:43:16,340 --> 00:43:17,820
Tai didelis O n, linijinė.

1056
00:43:17,820 --> 00:43:20,630
Nes blogiausiu atveju,
elementas, kaip ir 55,

1057
00:43:20,630 --> 00:43:23,830
mes galime būti ieškote gali būti ten, kur
Džekas buvo visa pabaigoje būdas.

1058
00:43:23,830 --> 00:43:28,250
Ir, deja, skirtingai nuo masyvo
mes negalime gauti išgalvotas šį kartą.

1059
00:43:28,250 --> 00:43:31,820
Nors visi mūsų žmonėms buvo
rūšiuoti nuo mažų elementų, 5,

1060
00:43:31,820 --> 00:43:35,900
visą kelią iki didesnio elemento,
55, tai paprastai yra geras dalykas.

1061
00:43:35,900 --> 00:43:38,815
Bet ką daro šią prielaidą
nebėra leidžia mums daryti?

1062
00:43:38,815 --> 00:43:39,775

1063
00:43:39,775 --> 00:43:40,650
PUBLIKA: [nesigirdi]

1064
00:43:40,650 --> 00:43:40,920
David J. Malan: Pasakykite naujo?

1065
00:43:40,920 --> 00:43:41,800
PUBLIKA: Laisvosios kreipties.

1066
00:43:41,800 --> 00:43:43,049
David J. Malan: Laisvosios kreipties.

1067
00:43:43,049 --> 00:43:46,330
Ir, savo ruožtu tai reiškia, kad mes galime ne
ilgiau naudoti silpną nuliai, intuicija,

1068
00:43:46,330 --> 00:43:49,365
ir akivaizdumas naudojant dvejetainę
ieškoti ir padalinti ir užkariauti.

1069
00:43:49,365 --> 00:43:51,240
Nes nors mes
žmonės gali akivaizdžiai

1070
00:43:51,240 --> 00:43:54,610
matyti, kad Andy ir krikščionių buvo
maždaug viduryje sąrašo

1071
00:43:54,610 --> 00:43:57,670
mes tik žinome, kad
kompiuteris nugriebus sąrašą

1072
00:43:57,670 --> 00:43:59,029
nuo pat pradžių.

1073
00:43:59,029 --> 00:44:00,570
Taigi mes atsisakė tą laisvą prieigą.

1074
00:44:00,570 --> 00:44:04,380
>> Taigi didelis O n metu yra viršutinis
laikytis mūsų paieškos laiką.

1075
00:44:04,380 --> 00:44:07,920
Ką apie omega mūsų paieškos?

1076
00:44:07,920 --> 00:44:11,535
Kas apatinė ant paieškos
dėl tam tikrų į šį sąrašą skaičius?

1077
00:44:11,535 --> 00:44:12,410
PUBLIKA: [nesigirdi]

1078
00:44:12,410 --> 00:44:13,040
David J. Malan: Pasakykite naujo?

1079
00:44:13,040 --> 00:44:13,420
PUBLIKA: Vienas.

1080
00:44:13,420 --> 00:44:13,800
David J. Malan: Vienas.

1081
00:44:13,800 --> 00:44:14,760
Taigi pastovus laikas.

1082
00:44:14,760 --> 00:44:17,020
Geriausiu atveju, Christine
tikrai ne sąrašo pradžioje.

1083
00:44:17,020 --> 00:44:19,020
Ir mes ieškome
skaičius 5, todėl mes radome ją.

1084
00:44:19,020 --> 00:44:19,787
Taigi ne big deal.

1085
00:44:19,787 --> 00:44:22,370
Bet ji turiu būti ne
pradžioje šioje byloje, sąrašą.

1086
00:44:22,370 --> 00:44:23,745
Ką apie kažką panašaus Delete?

1087
00:44:23,745 --> 00:44:24,717

1088
00:44:24,717 --> 00:44:26,300
Ką daryti, jei norite ištrinti elementą?

1089
00:44:26,300 --> 00:44:29,200
Kas viršutinė ir apatinė
ant išbraukiant kažką iš susijęs

1090
00:44:29,200 --> 00:44:29,699
sąrašą?

1091
00:44:29,699 --> 00:44:35,195

1092
00:44:35,195 --> 00:44:36,070
PUBLIKA: [nesigirdi]

1093
00:44:36,070 --> 00:44:36,420
David J. Malan: Pasakykite naujo?

1094
00:44:36,420 --> 00:44:37,067
PUBLIKA: n.

1095
00:44:37,067 --> 00:44:38,900
David J. Malan: n
Iš tiesų viršutinė riba.

1096
00:44:38,900 --> 00:44:41,700
Nes blogiausiu atveju, mes stengiamės
ištrinti Jack, kaip mes ką tik padarė.

1097
00:44:41,700 --> 00:44:43,050
Jis visa pabaigoje būdas.

1098
00:44:43,050 --> 00:44:45,419
Priima su mumis amžinai, arba
n žingsnių jį surasti.

1099
00:44:45,419 --> 00:44:46,460
Štai viršutinė riba.

1100
00:44:46,460 --> 00:44:47,430
Štai linijinė, tikrai.

1101
00:44:47,430 --> 00:44:50,970
Ir geriausias atvejis bėgančio laiko, arba
žemesnės ribos geriausiu atveju

1102
00:44:50,970 --> 00:44:51,975
būtų pastovus laikas.

1103
00:44:51,975 --> 00:44:54,600
Nes gal mes stengiamės ištrinti
Christine, ir mes tiesiog gauti pasisekė

1104
00:44:54,600 --> 00:44:55,558
ji pradžioje.

1105
00:44:55,558 --> 00:44:56,350
Dabar palauk.

1106
00:44:56,350 --> 00:44:59,370
Gabe taip pat buvo pradžioje,
ir mes taip pat turėjo atnaujinti Gabe.

1107
00:44:59,370 --> 00:45:01,150
Taigi, tai buvo ne tik vienas žingsnis.

1108
00:45:01,150 --> 00:45:04,210
Taigi tai iš tiesų nuolat
laikas, geriausiu atveju,

1109
00:45:04,210 --> 00:45:06,345
pašalinti mažiausias elementas?

1110
00:45:06,345 --> 00:45:07,360

1111
00:45:07,360 --> 00:45:10,960
Tai, nors tai gali būti du,
trys, ar net 100 eilučių kodo,

1112
00:45:10,960 --> 00:45:14,000
jei jis pats skaičius
linijos, o ne kai kilpa,

1113
00:45:14,000 --> 00:45:16,577
ir nepriklauso nuo dydžio
sąrašo, absoliučiai.

1114
00:45:16,577 --> 00:45:18,660
Trynimas esant elementą
Sąrašo pradžioje,

1115
00:45:18,660 --> 00:45:21,940
net jei mes turime elgtis su
Gabe vis dar pastovus laikas.

1116
00:45:21,940 --> 00:45:24,220
>> Taigi tai atrodo
masinis žingsnis atgal.

1117
00:45:24,220 --> 00:45:27,000
Ir ką laiko švaistymas
, jeigu per savaitę vieną ir savaitę

1118
00:45:27,000 --> 00:45:30,250
nulis mes turėjome ne tik
Pseudocode kodas, tačiau tikrasis kodas

1119
00:45:30,250 --> 00:45:35,780
įgyvendinti kažką, kad žurnalas
bazė n arba prisijunkite, o, n, pagrindas 2,

1120
00:45:35,780 --> 00:45:37,150
atsižvelgiant į jos veikimo laiką.

1121
00:45:37,150 --> 00:45:40,710
Taigi, kodėl gi būtų mes norime pradėti
naudojant kažką panašaus į susietą sąrašą?

1122
00:45:40,710 --> 00:45:41,517
Taip.

1123
00:45:41,517 --> 00:45:44,022
>> PUBLIKA: Taigi jūs galite pridėti
elementai masyvo.

1124
00:45:44,022 --> 00:45:46,230
David J. Malan: Taigi jūs galite
pridėti elementus į masyvą.

1125
00:45:46,230 --> 00:45:47,550
Ir tai taip pat yra teminis.

1126
00:45:47,550 --> 00:45:49,740
Ir mes toliau matyti
tai šis kompromisas, daug

1127
00:45:49,740 --> 00:45:51,573
kaip mes matėme
kompromisą su merge rūšiuoti.

1128
00:45:51,573 --> 00:45:54,606
Mes tikrai gali paspartinti
ieškoti arba rūšiavimą, o,

1129
00:45:54,606 --> 00:45:57,480
jei mes praleisti šiek tiek daugiau vietos ir
turėti papildomą riekė atminties

1130
00:45:57,480 --> 00:45:58,760
arba už merge rūšiuoti masyvo.

1131
00:45:58,760 --> 00:46:01,270
Bet mes praleidžiame daugiau
erdvė, bet mes sutaupyti laiko.

1132
00:46:01,270 --> 00:46:04,820
Tokiu atveju, mes
mesti laiką, bet mes

1133
00:46:04,820 --> 00:46:08,170
įgyti lankstumo,
dinamiškumas, jei bus,

1134
00:46:08,170 --> 00:46:10,280
kuris yra neabejotinai teigiamas bruožas.

1135
00:46:10,280 --> 00:46:11,520
>> Mes taip pat išleidžia erdvę.

1136
00:46:11,520 --> 00:46:13,710
Kokia prasme yra susijęs
sąrašą brangesnis

1137
00:46:13,710 --> 00:46:15,700
erdvės požiūriu nei masyvo?

1138
00:46:15,700 --> 00:46:18,379

1139
00:46:18,379 --> 00:46:19,920
Kur yra papildomos vietos tiekiamos iš?

1140
00:46:19,920 --> 00:46:20,460
Taip?

1141
00:46:20,460 --> 00:46:21,800
>> PUBLIKA: [nesigirdi] žymeklis.

1142
00:46:21,800 --> 00:46:23,310
>> David J. Malan: Taip, mes
taip pat turi rodyklę.

1143
00:46:23,310 --> 00:46:25,560
Taigi tai yra minorly erzina
tuo, kad nebėra esu

1144
00:46:25,560 --> 00:46:27,780
Aš saugoti tik int
atstovauti int.

1145
00:46:27,780 --> 00:46:30,990
Aš saugoti int ir A
žymeklis, kuris taip pat yra 32 bitai.

1146
00:46:30,990 --> 00:46:33,470
Taigi, aš tiesiog dvigubai
Tarpas dalyvauja.

1147
00:46:33,470 --> 00:46:36,040
Štai kompromisą, tačiau
tai į int atveju.

1148
00:46:36,040 --> 00:46:39,580
Tarkime, kad jūs ne saugoti int,
bet manau, kad kiekvienas iš šių stačiakampių

1149
00:46:39,580 --> 00:46:43,290
ar kiekvienas iš šių žmonių buvo atstovaujanti
žodis, anglų kalbos žodis, kad

1150
00:46:43,290 --> 00:46:46,430
gali būti penkių simbolių, 10
simbolių, o gal net daugiau.

1151
00:46:46,430 --> 00:46:49,940
Tada pridedant tik 32 bitai daugiau
gali būti mažiau baisi.

1152
00:46:49,940 --> 00:46:52,160
>> Ką daryti, jei kiekvienas iš mokinių
į demonstraciją

1153
00:46:52,160 --> 00:46:55,107
buvo pažodžiui studentų structs kad
turi vardus ir namus, o gal ir

1154
00:46:55,107 --> 00:46:57,065
telefono numerius ir "Twitter"
rankenos ir pan.

1155
00:46:57,065 --> 00:46:59,564
Taigi visus laukus mes pradėjome
kalbame apie kitą dieną,

1156
00:46:59,564 --> 00:47:02,410
daug mažiau baisi kaip
mūsų mazgai gauti įdomiau

1157
00:47:02,410 --> 00:47:05,972
ir didelis praleisti, eh, papildomas
žymeklis tiesiog susieti juos kartu.

1158
00:47:05,972 --> 00:47:07,180
Bet iš tikrųjų, tai kompromisas.

1159
00:47:07,180 --> 00:47:09,560
Ir iš tiesų, kodas yra
sudėtingesnė, nes jūs

1160
00:47:09,560 --> 00:47:11,770
matyti nugriebus per
kad visų pirma pavyzdys.

1161
00:47:11,770 --> 00:47:14,302
Bet kas, jei ten buvo
kai Gralis čia.

1162
00:47:14,302 --> 00:47:17,010
Ką daryti, jei mes neturime žengti žingsnį
atgal bet masinis žingsnis į priekį

1163
00:47:17,010 --> 00:47:19,180
ir įgyvendinti duomenų
struktūra, per kurią mes

1164
00:47:19,180 --> 00:47:22,870
rasite elementų, tokių kaip Jack arba
Christine arba visi kiti elementai,

1165
00:47:22,870 --> 00:47:25,870
šiame masyve tiesa nuolat laiku?

1166
00:47:25,870 --> 00:47:26,920
Paieška yra pastovus.

1167
00:47:26,920 --> 00:47:28,320
Ištrinti yra pastovus.

1168
00:47:28,320 --> 00:47:29,570
Įdėkite yra pastovus.

1169
00:47:29,570 --> 00:47:32,260
Visi šių operacijų yra pastovus.

1170
00:47:32,260 --> 00:47:33,750
Tai būtų mūsų Gralis.

1171
00:47:33,750 --> 00:47:36,690
Ir tai yra, kai mes
pasiimti kitą kartą.

1172
00:47:36,690 --> 00:47:38,600
Pasimatysime vėliau.

1173
00:47:38,600 --> 00:47:39,371