1
00:00:00,000 --> 00:00:10,900

2
00:00:10,900 --> 00:00:15,860
>> GARSIAKALBIS 1: Gerai, taigi tai
CS50 Tai iš penkių savaitės pabaigoje.

3
00:00:15,860 --> 00:00:19,220
Ir prisiminti, kad paskutinį kartą mes
pradėjo ieškoti mėgėjas duomenis

4
00:00:19,220 --> 00:00:22,310
struktūras, kurios pradėjo spręsti
problemos, kad pradėjo diegti

5
00:00:22,310 --> 00:00:25,640
naujų problemų, bet į šį klavišą
buvo sriegimo rūšiuoti, kad mes

6
00:00:25,640 --> 00:00:27,940
pradėjo daryti iš mazgo į mazgą.

7
00:00:27,940 --> 00:00:30,085
Taigi, tai, žinoma, yra
atskirai susijusi sąrašas.

8
00:00:30,085 --> 00:00:31,960
Ir atskirai susiję,
Aš turiu galvoje, ten tik vienas

9
00:00:31,960 --> 00:00:33,380
perverkite tarp kiekvienos iš šių mazgų.

10
00:00:33,380 --> 00:00:35,890
Pasirodo, tai galite padaryti mėgėjas
tokie dalykai kaip dvigubai, susijusių sąrašus

11
00:00:35,890 --> 00:00:38,470
kuriuo turite rodyklę
vyksta abiem kryptimis, kurios

12
00:00:38,470 --> 00:00:40,320
gali padėti su kai efektyvumą.

13
00:00:40,320 --> 00:00:42,000
Bet tai išsprendė problemą?

14
00:00:42,000 --> 00:00:43,500
Kas problema tai padarė išspręsti?

15
00:00:43,500 --> 00:00:46,620
Kodėl mums rūpi pirmadienį?

16
00:00:46,620 --> 00:00:49,820
Kodėl teoriškai, ar mes rūpinamės pirmadienį?

17
00:00:49,820 --> 00:00:50,630
Ką tai daro?

18
00:00:50,630 --> 00:00:51,950
>> Auditorija: Mes galime dinamiškai keisti ją.

19
00:00:51,950 --> 00:00:53,740
>> GARSIAKALBIS 1: Gerai, kad mes galime
dinamiškai keisti ją.

20
00:00:53,740 --> 00:00:54,710
Well done jus abu.

21
00:00:54,710 --> 00:00:57,560
Taigi galite dinamiškai keisti šį
duomenų struktūra, o masyvo,

22
00:00:57,560 --> 00:01:00,760
Prisiminkite, jūs turite žinoti šiek
priori, kiek vietos norite

23
00:01:00,760 --> 00:01:03,870
ir, jei reikia šiek tiek daugiau
Erdvė, esate rūšies nesiseka.

24
00:01:03,870 --> 00:01:05,560
Jūs turite sukurti visiškai naują masyvo.

25
00:01:05,560 --> 00:01:07,893
Jūs turite perkelti visus savo
duomenys iš vieno į kitą,

26
00:01:07,893 --> 00:01:10,600
galiausiai nemokamai seną masyvo
jei galite, ir tada tęsti.

27
00:01:10,600 --> 00:01:13,891
Kuris tiesiog jaučiasi labai brangus ir labai
neefektyvus, ir iš tiesų jis gali būti.

28
00:01:13,891 --> 00:01:14,890
Bet tai dar ne viskas gerai.

29
00:01:14,890 --> 00:01:18,180
Mes mokame kainą, kas buvo vienas
iš daugiau akivaizdžių kainas mes

30
00:01:18,180 --> 00:01:20,550
mokėti naudojant susietą sąrašą?

31
00:01:20,550 --> 00:01:22,825
>> Auditorija: Mes turime naudoti
Dvigubas erdvę kiekvienai iš jų.

32
00:01:22,825 --> 00:01:25,200
GARSIAKALBIS 1: Taip, taip, mes turime
mažiausiai du kartus, kaip daug vietos.

33
00:01:25,200 --> 00:01:27,700
Tiesą sakant, aš supratau, tai paveikslėlio
net šiek tiek klaidinantis,

34
00:01:27,700 --> 00:01:32,200
nes ant CS50 IDE šiuolaikinio daug
Kompiuteriai, rodyklė arba adresas

35
00:01:32,200 --> 00:01:33,700
iš tiesų nėra keturių baitų.

36
00:01:33,700 --> 00:01:36,090
Tai labai dažnai šių
dienų aštuoni baitai, kurie

37
00:01:36,090 --> 00:01:38,530
reiškia dugną dauguma
stačiakampiai ten tikrovės

38
00:01:38,530 --> 00:01:40,900
yra rūšies dvigubai
dideli, kaip ką aš sudarytas,

39
00:01:40,900 --> 00:01:44,409
o tai reiškia, kad jūs naudojate tris kartus
daug vietos, kaip mes galime turėti kitaip.

40
00:01:44,409 --> 00:01:46,700
Dabar tuo pačiu metu, mes
vis dar kalbame baitų, tiesa?

41
00:01:46,700 --> 00:01:49,140
Mes nebūtinai kalbame
megabaitų ar gigabaitų,

42
00:01:49,140 --> 00:01:51,000
nebent šių duomenų struktūros gauti dideli.

43
00:01:51,000 --> 00:01:54,510
>> Ir taip šiandien mes pradedame svarstyti
kaip mes galime ištirti duomenis

44
00:01:54,510 --> 00:01:57,310
efektyviau, jei į
Tai duomenys plečiasi.

45
00:01:57,310 --> 00:02:00,360
Bet pabandykime canonicalize
operacijos pirmieji

46
00:02:00,360 --> 00:02:02,460
kad jūs galite padaryti dėl šių
rūšių duomenų struktūras.

47
00:02:02,460 --> 00:02:04,790
Taigi kažkas panašaus susijęs
Sąrašas paprastai palaiko

48
00:02:04,790 --> 00:02:07,514
operacijos patinka ištrinti,
įterpti, ir ieškoti.

49
00:02:07,514 --> 00:02:08,639
Ir ką aš turiu galvoje, kad?

50
00:02:08,639 --> 00:02:11,222
Tai tiesiog reiškia, kad dažniausiai,
jei žmonės naudoja susietą sąrašą

51
00:02:11,222 --> 00:02:14,287
jie ar kas nors kitas įdiegė
funkcijas, pavyzdžiui, trinti, įterpti,

52
00:02:14,287 --> 00:02:16,120
ir paieškos, todėl jūs galite
iš tikrųjų ką nors padaryti

53
00:02:16,120 --> 00:02:18,030
naudinga su duomenų struktūra.

54
00:02:18,030 --> 00:02:20,760
Taigi leiskite priimti greitai pažvelgti
tuo, kaip mes galime įgyvendinti

55
00:02:20,760 --> 00:02:24,530
kai už susietą sąrašą kodas taip.

56
00:02:24,530 --> 00:02:27,885
>> Taigi tai yra tik keletas, C kodas,
net ne visa programa

57
00:02:27,885 --> 00:02:29,260
kad aš tikrai greitai plakta.

58
00:02:29,260 --> 00:02:32,300
Tai ne internete platinimo
kodas, nes ji nebus iš tikrųjų paleisti.

59
00:02:32,300 --> 00:02:33,790
Tačiau pastebėti Aš ką tik
su pastaba sakė,

60
00:02:33,790 --> 00:02:36,130
dot dot dot, kažkas
ten, dot dot dot, kažką ten.

61
00:02:36,130 --> 00:02:38,410
Ir tegul tik pažvelgti
ką sultingas dalys yra.

62
00:02:38,410 --> 00:02:40,790
Taigi on-line trijų,
priminti, kad tai dabar

63
00:02:40,790 --> 00:02:45,960
Mes pasiūlėme skelbiantis mazgas paskutinį
laikas, vienas iš tų stačiakampių objektus.

64
00:02:45,960 --> 00:02:48,790
Jis turi int, kad mes vadiname N,
bet mes galime ją vadina nieko,

65
00:02:48,790 --> 00:02:51,920
ir tada konstrukto mazgas žvaigždė vadinama šalia.

66
00:02:51,920 --> 00:02:55,520
Ir tiesiog, kad būtų aišku, kad antrasis
linija, on-line šešių, kas tai yra?

67
00:02:55,520 --> 00:02:57,930
Ką jis daro už mus?

68
00:02:57,930 --> 00:03:01,044
Nes ji tikrai atrodo daugiau
paslaptingas nei mūsų įprasta kintamųjų.

69
00:03:01,044 --> 00:03:02,740
>> Auditorija: Tai leidžia pereiti vieną.

70
00:03:02,740 --> 00:03:04,650
>> GARSIAKALBIS 1: Ji daro tai perkelti daugiau nei vienas.

71
00:03:04,650 --> 00:03:08,580
Ir, kad būtų tikslesni,
jis bus išsaugoti adresą

72
00:03:08,580 --> 00:03:11,582
mazgas, kad reiškia būti
semantiškai šalia jo, tiesa?

73
00:03:11,582 --> 00:03:13,540
Taigi jis nesiruošia
nebūtinai judėti nieko.

74
00:03:13,540 --> 00:03:15,290
Tai tiesiog ketiname
laikyti vertę, kuri yra

75
00:03:15,290 --> 00:03:17,170
bus adresas
kai kurių kitų mazgas,

76
00:03:17,170 --> 00:03:20,810
ir tai, kodėl mes sakė konstrukto
mazgas žvaigždė, žvaigždė, reiškiantis

77
00:03:20,810 --> 00:03:22,370
rodyklė ar adresą.

78
00:03:22,370 --> 00:03:26,390
Gerai, kad dabar, jei manome, kad turime
Šio N prieinama mums, ir tegul

79
00:03:26,390 --> 00:03:29,490
manyti, kad kažkas turi
įdėta visa krūva skaičių

80
00:03:29,490 --> 00:03:30,400
į susietą sąrašą.

81
00:03:30,400 --> 00:03:35,640
Ir tai susiję sąrašas
atkreipė dėmesį į kai kurių taško

82
00:03:35,640 --> 00:03:39,040
kintamasis vadinamas sąrašas, kurį
praėjo čia, kaip parametras,

83
00:03:39,040 --> 00:03:43,120
kaip man eiti apie linija
14 įgyvendinant paiešką?

84
00:03:43,120 --> 00:03:45,990
Kitaip tariant, jei aš įgyvendinant
funkcija, kurios tikslas gyvenime

85
00:03:45,990 --> 00:03:48,889
yra imtis int ir tada
pradžioje susietą sąrašą

86
00:03:48,889 --> 00:03:50,430
kad yra rodyklė į susietą sąrašo.

87
00:03:50,430 --> 00:03:52,992
Kaip pirmą kartą, kas aš manau Dovydą
buvo mūsų savanoris pirmadienį,

88
00:03:52,992 --> 00:03:54,700
jis buvo nukreipta į
visa susijusi sąrašas

89
00:03:54,700 --> 00:03:57,820
tai kaip nors mes artimųjų
Dovydas, kaip mūsų argumentas čia.

90
00:03:57,820 --> 00:03:59,990
Kaip mes eiti apie važiuojantiems šį sąrašą?

91
00:03:59,990 --> 00:04:04,640
Na, it turns out, kad nors
patarimų yra gana nauja, dabar pas mus,

92
00:04:04,640 --> 00:04:07,010
mes galime tai padaryti gana
tiesmukai.

93
00:04:07,010 --> 00:04:09,500
>> Aš ruošiuosi eiti į priekį ir
paskelbti laikiną kintamąjį, kad

94
00:04:09,500 --> 00:04:12,364
pagal susitarimą yra tik ketina
būti vadinamas žymeklis, arba PTR,

95
00:04:12,364 --> 00:04:14,030
bet jūs galite jį vadiname viską, ką nori.

96
00:04:14,030 --> 00:04:16,470
Ir aš ruošiuosi inicijuoti
, kad ji iš sąrašo pradžioje.

97
00:04:16,470 --> 00:04:20,050
Taigi galite rūšies galvoti apie tai,
kaip man mokytoja kitą dieną,

98
00:04:20,050 --> 00:04:23,580
rūšies nukreipta į ką nors
tarp mūsų žmonių, kaip savanorius.

99
00:04:23,580 --> 00:04:26,470
Taigi, aš laikiną kintamąjį, kad yra
tik nukreipta į tą patį,

100
00:04:26,470 --> 00:04:31,390
kad mūsų atsitiktinai pavadintas
savanoris Dovydas buvo nurodydamas.

101
00:04:31,390 --> 00:04:35,440
Dabar, kai žymeklis yra
NOT NULL, nes susigrąžinimas

102
00:04:35,440 --> 00:04:40,350
kad niekinis yra keletas specialios Sentinel vertė
atriboja į sąrašo pabaigą,

103
00:04:40,350 --> 00:04:44,280
Taigi, nors aš nesu nukreipta ne
Pirmame kaip mūsų paskutinio savanorio

104
00:04:44,280 --> 00:04:47,190
buvo eikime į priekį
ir atlikite šiuos veiksmus.

105
00:04:47,190 --> 00:04:51,820
Jei pointer-- ir dabar aš tipo nori
daryti tai, ką mes padarėme su studento

106
00:04:51,820 --> 00:04:57,410
structure-- jei žymeklis dot Kitas
equals-- o, jei žymeklis taškas N yra lygus

107
00:04:57,410 --> 00:05:02,290
lygus kintamasis N, The
argumentas, kad buvo priimtas,

108
00:05:02,290 --> 00:05:05,370
tada aš noriu eiti į priekį
ir pasakyti grąžinti tiesa.

109
00:05:05,370 --> 00:05:11,020
Aš rasiu numeris N viduje
vienas iš savo susietą sąrašą mazgų.

110
00:05:11,020 --> 00:05:13,500
Bet dot nebėra
veikia šiame kontekste,

111
00:05:13,500 --> 00:05:17,260
nes žymeklis, PTR, yra
Iš tiesų rodyklė, adresą,

112
00:05:17,260 --> 00:05:20,632
mes iš tikrųjų gali nuostabiai
naudoti pagaliau yra sintaksės gabalas

113
00:05:20,632 --> 00:05:22,590
kad markių natūra
intuityvus jausmas ir iš tikrųjų

114
00:05:22,590 --> 00:05:27,870
čia naudoti rodyklę, o tai reiškia pereiti nuo
kad adresas sveikojo skaičiaus ten.

115
00:05:27,870 --> 00:05:30,160
Taigi, tai labai panašus į
dvasia dot operatoriaus,

116
00:05:30,160 --> 00:05:33,860
bet todėl, žymeklis yra ne rodyklė
o ne pats tikrasis konstrukto,

117
00:05:33,860 --> 00:05:35,380
mes tiesiog naudokite rodyklę.

118
00:05:35,380 --> 00:05:40,620
>> Taigi, jei dabartinė mazgas, kad Aš,
laikinas kintamasis, esu nukreipta į

119
00:05:40,620 --> 00:05:43,060
Netiksli N, ką noriu daryti?

120
00:05:43,060 --> 00:05:45,910
Na, su mano savanoriais
kad mes turėjo čia kitą dieną,

121
00:05:45,910 --> 00:05:49,710
jei mano pirmasis žmogaus nėra vienas aš
nori, o gal antras žmogus nėra

122
00:05:49,710 --> 00:05:52,660
vienas aš noriu, o trečiasis, aš
reikia išlaikyti fiziškai juda.

123
00:05:52,660 --> 00:05:54,690
Kaip, kaip man žingsnis per sąrašą?

124
00:05:54,690 --> 00:05:57,470
Kai mes turėjome masyvą, jums
tiesiog patiko I plius plius.

125
00:05:57,470 --> 00:06:03,660
Bet šiuo atveju, pakanka
padaryti žymeklį, gauna, žymeklis, šalia.

126
00:06:03,660 --> 00:06:07,580
Kitaip tariant, kitą laukas
yra kaip visi liko rankose

127
00:06:07,580 --> 00:06:10,880
kad mūsų žmogaus savanoriai pirmadienį
buvo naudojant atkreipti ne kitu mazgu.

128
00:06:10,880 --> 00:06:12,890
Tai buvo kito jų kaimynai.

129
00:06:12,890 --> 00:06:17,060
>> Taigi, jei aš noriu žingsnis per šiame sąraše,
Aš negaliu tiesiog padaryti I plius plius nebėra,

130
00:06:17,060 --> 00:06:20,120
Aš vietoj turiu pasakyti
Aš, žymeklis, vyksta

131
00:06:20,120 --> 00:06:24,650
prilygti ką kitą laukas yra,
Kitas laukas, kitas laukas yra,

132
00:06:24,650 --> 00:06:28,350
Žemiau visus tuos, kurie liko rankose
kad mes turėjome scenoje nukreipta

133
00:06:28,350 --> 00:06:30,000
kai vėlesnių vertybes.

134
00:06:30,000 --> 00:06:32,590
Ir jei aš gauti per
kad visa iteracijos,

135
00:06:32,590 --> 00:06:39,330
Ir pagaliau, aš paspauskite null neturi
rasti N dar, aš tiesiog grįžti klaidinga.

136
00:06:39,330 --> 00:06:44,100
Taigi dar kartą, visi, kad mes darome čia
kaip už paveikslėlyje metu senumo,

137
00:06:44,100 --> 00:06:47,840
pradeda nurodydamas ne
pradedant iš sąrašo, matyt.

138
00:06:47,840 --> 00:06:50,970
Ir tada aš patikrinti, yra vertė
Aš ieškau lygus devynių?

139
00:06:50,970 --> 00:06:52,650
Jei taip, aš grąžina true, ir aš padaryti.

140
00:06:52,650 --> 00:06:56,450
Jei ne, aš atnaujinti savo ranką,
AKA žymeklis, atkreipti

141
00:06:56,450 --> 00:06:59,540
Kitame strėlės vietą, ir
Tada kitą strėlės vietą,

142
00:06:59,540 --> 00:07:00,480
ir kitą.

143
00:07:00,480 --> 00:07:03,770
Aš tiesiog pėsčiomis per šio masyvo.

144
00:07:03,770 --> 00:07:06,010
>> Taigi dar kartą, who cares?

145
00:07:06,010 --> 00:07:07,861
Kaip kas tai yra viena sudedamoji dalis?

146
00:07:07,861 --> 00:07:10,360
Na, priminti, kad mes pristatėme
iš kamino sąvoka, kuri

147
00:07:10,360 --> 00:07:15,400
yra abstraktus duomenų tipas, kiek tai
ne C dalykas, tai ne CS50 dalykas,

148
00:07:15,400 --> 00:07:19,430
tai abstrakti idėja, ši idėja
krovimas dalykų vienas ant kito

149
00:07:19,430 --> 00:07:21,820
kurios gali būti įgyvendintos
kekių skirtingais būdais.

150
00:07:21,820 --> 00:07:25,600
Ir vienas iš būdų mes pasiūlėme buvo su
masyvas, arba susietą sąrašą.

151
00:07:25,600 --> 00:07:29,570
Ir paaiškėja, kad kanoniškai A
kamino palaiko bent dvi operacijas.

152
00:07:29,570 --> 00:07:32,320
Ir Buzz žodžiai stumti, kad
stumti kažką ant kamino,

153
00:07:32,320 --> 00:07:34,770
kaip naują plokštelę į
valgykla, ar pop,

154
00:07:34,770 --> 00:07:39,000
o tai reiškia, kad pašalinti viršutinis
dėklas nuo valgomojo kamino

155
00:07:39,000 --> 00:07:41,500
salė, o po to gal kai
Kitos operacijos, taip pat.

156
00:07:41,500 --> 00:07:45,770
Taigi, kaip gali mes apibrėžti struktūrą
kad mes dabar skambina kamino?

157
00:07:45,770 --> 00:07:50,020
>> Na, mes turime visi reikiami
sintaksė mūsų žinioje C sakau,

158
00:07:50,020 --> 00:07:53,830
man tipo apibrėžimą
viduje iš kamino konstrukto,

159
00:07:53,830 --> 00:07:58,030
Aš ruošiuosi pasakyti yra masyvas, Kurių
visa krūva skaičių ir tada dydis.

160
00:07:58,030 --> 00:08:00,930
Taigi, kitaip tariant, jei aš noriu
įgyvendinti tai kodas,

161
00:08:00,930 --> 00:08:03,830
leiskite man eiti ir tiesiog rūšies
atkreipti, kas tai yra suprantama.

162
00:08:03,830 --> 00:08:06,317
Taigi, tai sako, duok mane
struktūra, kuri gavo masyvą,

163
00:08:06,317 --> 00:08:09,400
ir aš nežinau, ką talpa,
tai, matyt, kai pastovus, kad aš

164
00:08:09,400 --> 00:08:10,858
apibrėžta kitur, ir tai gerai.

165
00:08:10,858 --> 00:08:15,260
Bet manau, kad tai tik viena,
dviejų, trijų, keturių, penkių.

166
00:08:15,260 --> 00:08:16,700
Taigi talpa yra 5.

167
00:08:16,700 --> 00:08:21,730
Tai viduje elementas mano
struktūra bus vadinamas numerius.

168
00:08:21,730 --> 00:08:24,020
Ir tada man reikia vieną
kitas kintamasis, matyt,

169
00:08:24,020 --> 00:08:27,814
vadinamas dydis, kad iš pradžių aš ruošiuosi
numatyti, yra inicializuoti iki nulio.

170
00:08:27,814 --> 00:08:29,730
Jei yra nieko
kamino, dydis yra lygus nuliui,

171
00:08:29,730 --> 00:08:31,420
ir tai šiukšlių vertybes skaičiais.

172
00:08:31,420 --> 00:08:33,450
Aš neįsivaizduoju, kas yra pakuotėje yra tik dar.

173
00:08:33,450 --> 00:08:36,059
>> Taigi, jei aš noriu stumti
kažkas ant kamino,

174
00:08:36,059 --> 00:08:40,780
tarkime, aš vadinu funkcija stumti, ir
Sakau stumti 50, kaip numeris 50,

175
00:08:40,780 --> 00:08:44,090
Kur norėtumėte pasiūlyti
Aš ją nupieškite šiame masyve?

176
00:08:44,090 --> 00:08:47,124
Yra penkių skirtingų galimų atsakymų.

177
00:08:47,124 --> 00:08:48,790
Kur tu nori stumti skaičių 50?

178
00:08:48,790 --> 00:08:51,899
Jei tikslas čia, vėlgi, vadiname
funkcija stumti, pereiti į argumentą

179
00:08:51,899 --> 00:08:52,940
50, kur man jį?

180
00:08:52,940 --> 00:08:55,680

181
00:08:55,680 --> 00:08:59,052
Penki įmanomą 20% tikimybė,
atspėti teisingai.

182
00:08:59,052 --> 00:08:59,896
Taip?

183
00:08:59,896 --> 00:09:00,740
>> Auditorija: Toli dešinėje.

184
00:09:00,740 --> 00:09:01,990
>> GARSIAKALBIS 1: Toli dešinėje.

185
00:09:01,990 --> 00:09:08,359
Dabar yra 25% tikimybė,
atspėti teisingai.

186
00:09:08,359 --> 00:09:09,650
Taigi, kad iš tiesų būtų gerai.

187
00:09:09,650 --> 00:09:12,770
Pagal susitarimą, aš pasakyti masyvą,
mes paprastai prasideda kairėje,

188
00:09:12,770 --> 00:09:14,519
bet mes tikrai galėtų
pradėti dešinėje.

189
00:09:14,519 --> 00:09:17,478
Taigi spoileris čia būtų aš
tikriausiai ketina parengti jį kairėje,

190
00:09:17,478 --> 00:09:20,060
Tiesiog kaip normalus masyvo kur
Aš pradėti vyksta kairės į dešinę.

191
00:09:20,060 --> 00:09:21,780
Bet jei jūs galite apversti
aritmetinis, gerai.

192
00:09:21,780 --> 00:09:23,060
Tai tiesiog nėra tradicinis.

193
00:09:23,060 --> 00:09:24,880
Gerai, man reikia padaryti vieną
daugiau pokytis nors.

194
00:09:24,880 --> 00:09:27,710
Dabar, kad aš stumdosi kažką
ant kamino, o kas toliau?

195
00:09:27,710 --> 00:09:29,400
>> Gerai, aš turiu prieaugio dydį.

196
00:09:29,400 --> 00:09:32,600
Taigi leiskite man eiti į priekį ir tik
atnaujina, kuris buvo nulis.

197
00:09:32,600 --> 00:09:35,950
Ir vietoj dabar aš ruošiuosi
įdėti į vertės vieną.

198
00:09:35,950 --> 00:09:39,460
Ir dabar manau, aš stumti kitą
numeris ant kamino, kaip ir 51.

199
00:09:39,460 --> 00:09:42,680
Na, aš turiu padaryti vienas
pokytis, kuris yra iki dydžio du.

200
00:09:42,680 --> 00:09:46,100
Ir tada manau, aš stumti dar vieną
numeris ant kaip 61 kaminą,

201
00:09:46,100 --> 00:09:52,530
dabar man reikia atnaujinti dydį dar vienas
laiką ir gauti vertę 3 AS dydžio.

202
00:09:52,530 --> 00:09:54,690
O dabar tarkime aš vadinu pasipriešinimo.

203
00:09:54,690 --> 00:09:57,250
Dabar pop, pagal susitarimą,
nesiima argumentas.

204
00:09:57,250 --> 00:10:00,430
Su rietuvę, visa
taškas dėklas metafora

205
00:10:00,430 --> 00:10:03,450
yra ta, kad jūs neturite savo nuožiūra
eiti gauti dėklas, viskas, ką galite padaryti

206
00:10:03,450 --> 00:10:06,330
yra pop viršutinis vienas nuo
kamino, tik todėl.

207
00:10:06,330 --> 00:10:08,010
Štai, ką šis duomenų struktūra daro.

208
00:10:08,010 --> 00:10:12,250
>> Taigi, šia logika, jeigu aš
sako pop, kas ateina ne?

209
00:10:12,250 --> 00:10:13,080
Taigi 61.

210
00:10:13,080 --> 00:10:15,402
Taigi, kas iš tiesų yra kompiuteris
ketina daryti atmintyje?

211
00:10:15,402 --> 00:10:16,610
Ką mano kodas daryti?

212
00:10:16,610 --> 00:10:20,330
Ką siūlytumėte
mes pakeisti ekrane?

213
00:10:20,330 --> 00:10:23,410
Ką reikėtų keisti?

214
00:10:23,410 --> 00:10:24,960
Atsiprašome?

215
00:10:24,960 --> 00:10:26,334
Taigi, mes atsikratyti 61.

216
00:10:26,334 --> 00:10:27,500
Taigi, aš tikrai gali tai padaryti.

217
00:10:27,500 --> 00:10:28,640
Ir aš galiu atsikratyti 61.

218
00:10:28,640 --> 00:10:30,980
Ir kas tada kita
Pakeisti turi įvykti?

219
00:10:30,980 --> 00:10:33,160
Dydis tikriausiai turi grįžti į dvi dalis.

220
00:10:33,160 --> 00:10:34,210
Ir taip, kad viskas gerai.

221
00:10:34,210 --> 00:10:36,690
Bet palauk, dydį
prieš momentas buvo trys.

222
00:10:36,690 --> 00:10:38,240
Tegul tik padaryti greitai normalumas patikrinti.

223
00:10:38,240 --> 00:10:41,810
Kaip mes žinome, kad
norėjo atsikratyti 61?

224
00:10:41,810 --> 00:10:42,760
Kadangi mes Popping.

225
00:10:42,760 --> 00:10:46,450
Ir taip, aš turiu šį antrąjį objekto dydį.

226
00:10:46,450 --> 00:10:48,470
>> Palaukit, aš
galvoju grįžti į dvi savaitės

227
00:10:48,470 --> 00:10:51,660
kai mes pradėjome kalbėti apie
masyvai, jei tai buvo vieta nulis,

228
00:10:51,660 --> 00:10:55,920
tai buvo vieta viena, tai buvo vieta
du, tai yra vietą trijų, keturių,

229
00:10:55,920 --> 00:10:58,460
atrodo, kad
santykiai tarp dydis

230
00:10:58,460 --> 00:11:02,780
ir elementas, kad aš noriu pašalinti
iš masyvo, atrodo, tiesiog, ką?

231
00:11:02,780 --> 00:11:05,120
Dydis atėmus vieną.

232
00:11:05,120 --> 00:11:07,786
Ir taip tai kaip, kaip žmogui
Mes žinome 61 ateina pirmiausia.

233
00:11:07,786 --> 00:11:09,160
Kaip manimi kompiuteris ketinate žinoti?

234
00:11:09,160 --> 00:11:11,701
Kai jūsų kodas, kur jūs tikriausiai
noriu padaryti dydis minuso vieną,

235
00:11:11,701 --> 00:11:14,950
taip, trijų minus vienas yra du, ir kad
reiškia, kad mes norime atsikratyti 61.

236
00:11:14,950 --> 00:11:18,000
Ir tada mes iš tiesų gali atnaujinti
PK tokio dydžio dydis dabar

237
00:11:18,000 --> 00:11:20,300
eina nuo trijų iki tik du.

238
00:11:20,300 --> 00:11:24,520
Ir tiesiog būti pedantiškas, aš ruošiuosi
siūlyti, kad aš padariau, tiesa?

239
00:11:24,520 --> 00:11:27,660
Jūs intuityviai pasiūlė
teisingai turėčiau atsikratyti 61.

240
00:11:27,660 --> 00:11:30,700
Bet neturite I rūšies
rūšiuoti Dotarłeś atsikratyti 61?

241
00:11:30,700 --> 00:11:33,790
Aš pamiršau efektyviai
kad ji iš tikrųjų yra.

242
00:11:33,790 --> 00:11:37,680
Ir prisiminkite PSET4, jei jūs skaitėte
straipsnis apie ekspertizės, PDF

243
00:11:37,680 --> 00:11:40,780
kad mes turėjome vaikinai skaityti, ar jūs
skaityti šią savaitę PSET4.

244
00:11:40,780 --> 00:11:44,300
Prisiminkite, kad iš tikrųjų tai yra Priklauso
Visa idėja kompiuterių ekspertizės.

245
00:11:44,300 --> 00:11:47,820
Ką kompiuteris paprastai daro, yra
jis tiesiog pamiršta, kur kažkas yra,

246
00:11:47,820 --> 00:11:51,300
tačiau ji neturi eiti ir kaip
bandyti subraižyti jį arba išjungimas

247
00:11:51,300 --> 00:11:54,560
tie antgaliai su nulių ir
ar kai kurių kitų atsitiktinių modelis

248
00:11:54,560 --> 00:11:56,690
Nebent jūs patys tai daryti sąmoningai.

249
00:11:56,690 --> 00:11:58,930
Taigi jūsų intuicija
Gerai, tegul atsikratyti 61.

250
00:11:58,930 --> 00:12:00,650
Bet iš tikrųjų, mes neturime nerimauti.

251
00:12:00,650 --> 00:12:04,040
Mes tiesiog reikia pamiršti, kad
jis ten keičiant mūsų dydį.

252
00:12:04,040 --> 00:12:05,662
>> Dabar yra su šiuo kamino problema.

253
00:12:05,662 --> 00:12:07,620
Jei aš nuolat stumia dalykus
ant kamino, kas

254
00:12:07,620 --> 00:12:11,167
Akivaizdu nutiks
vos per kelias akimirkas metu?

255
00:12:11,167 --> 00:12:12,500
Mes ketiname paleisti iš kosmoso.

256
00:12:12,500 --> 00:12:13,580
Ir ką mes galime padaryti?

257
00:12:13,580 --> 00:12:14,680
Mes rūšies prisukamas.

258
00:12:14,680 --> 00:12:19,000
Šis įgyvendinimas neleidžia
mums dydį masyvo, nes naudojant

259
00:12:19,000 --> 00:12:21,240
Ši sintaksė, jei jums
prisiminkite du per savaitę,

260
00:12:21,240 --> 00:12:23,520
kai jūs paskelbė
iš masyvo dydis,

261
00:12:23,520 --> 00:12:26,780
mes nematėme mechanizmą dar kur
galite pakeisti masyvo dydį.

262
00:12:26,780 --> 00:12:29,020
Ir iš tiesų, C neturi tokios funkcijos.

263
00:12:29,020 --> 00:12:32,524
Jei sakai, kad man penkis
Nths, jiems skambinti numeriai,

264
00:12:32,524 --> 00:12:33,940
kad viskas, jūs ketinate gauti.

265
00:12:33,940 --> 00:12:38,790
Taigi mes dabar kaip ir pirmadienį, turi
gebėjimas išreikšti tirpalą

266
00:12:38,790 --> 00:12:42,480
nors mes tiesiog reikia keisti
mūsų kamino apibrėžimas

267
00:12:42,480 --> 00:12:46,840
ne būti šiek tiek sunku koduotos masyvas,
bet tik saugoti adresą.

268
00:12:46,840 --> 00:12:47,890
>> Dabar, kodėl taip yra?

269
00:12:47,890 --> 00:12:51,690
Dabar mes tiesiog turi būti patogu
faktas, kad kai mano programa veikia,

270
00:12:51,690 --> 00:12:53,730
Aš turbūt ketiname
turi paprašyti žmogaus,

271
00:12:53,730 --> 00:12:55,110
kiek numeriai norite saugoti?

272
00:12:55,110 --> 00:12:56,776
Taigi įėjimo turi ateiti iš kažkur.

273
00:12:56,776 --> 00:12:59,140
Bet kai žinau, kad
numerį, tada aš galiu tik

274
00:12:59,140 --> 00:13:02,470
panaudoti tai, ką veikti, parašęs
man atminties riekė?

275
00:13:02,470 --> 00:13:03,580
Galiu naudoti malloc.

276
00:13:03,580 --> 00:13:06,710
Ir galiu pasakyti, bet kokį skaičių
baitų noriu atgal už šias Nths.

277
00:13:06,710 --> 00:13:10,910
Ir viskas, ką turiu laikyti skaičiais
kintamasis čia viduje šio struct

278
00:13:10,910 --> 00:13:13,480
turėtų būti, ką?

279
00:13:13,480 --> 00:13:18,440
Kas iš tikrųjų eina į
numeriai pagal šį scenarijų?

280
00:13:18,440 --> 00:13:21,300
Taip, rodyklė į pirmąjį
baitas tos atminties riekė,

281
00:13:21,300 --> 00:13:24,940
arba, konkrečiau, adresas
iš pirmojo iš šių bitais.

282
00:13:24,940 --> 00:13:27,300
Nesvarbu, jei tai vienas
byte arba milijardas baitų,

283
00:13:27,300 --> 00:13:28,890
Aš tiesiog reikia rūpintis pirmas.

284
00:13:28,890 --> 00:13:31,530
Nes tai, kas malloc garantijos ir
Mano operacinė sistema garantuoja,

285
00:13:31,530 --> 00:13:34,170
yra tai, kad atminties I gabalas
gauti, tai bus greta.

286
00:13:34,170 --> 00:13:35,378
Yra nesiruošia būti tarpų.

287
00:13:35,378 --> 00:13:38,576
Taigi, jei aš paprašė 50
baitų arba 1000 baitų,

288
00:13:38,576 --> 00:13:40,450
jie visi bus
atgal atgal į nugarą.

289
00:13:40,450 --> 00:13:44,500
Ir taip ilgai, kaip aš atsimenu, kaip didelis, kaip
kiek aš paklausiau, man reikia žinoti

290
00:13:44,500 --> 00:13:46,230
pirmas toks adresas.

291
00:13:46,230 --> 00:13:48,660
>> Taigi dabar mes turime kode galimybes.

292
00:13:48,660 --> 00:13:51,280
Nors ji ketina imtis mumis
daugiau laiko rašyti tai padaryti,

293
00:13:51,280 --> 00:13:55,900
dabar mes galime perskirstyti tą atmintį
tiesiog laikyti kitą adresą čia

294
00:13:55,900 --> 00:13:59,060
jei norime didesnis ar net
mažesnis riekė atmintį.

295
00:13:59,060 --> 00:14:00,170
Taigi čia į kompromisą.

296
00:14:00,170 --> 00:14:01,360
Dabar mes gauname dinamiškumą.

297
00:14:01,360 --> 00:14:03,350
Mes vis dar turime
contiguousness aš teigdamas.

298
00:14:03,350 --> 00:14:05,881
Kadangi malloc duos mums
przyległa riekė atmintį.

299
00:14:05,881 --> 00:14:08,630
Bet tai ketina būti skausmo
už mus kaklo, programuotojas,

300
00:14:08,630 --> 00:14:09,770
kad iš tikrųjų kodą viršų.

301
00:14:09,770 --> 00:14:10,730
Tai tiesiog darbas.

302
00:14:10,730 --> 00:14:13,930
Mes turime kodą panašus į tai, ką buvau
beldžiasi iš vos prieš akimirką.

303
00:14:13,930 --> 00:14:16,120
Labai vykdytinas, tačiau ji priduria, sudėtingumą.

304
00:14:16,120 --> 00:14:19,520
Ir taip kūrėjas laikas, programuotojas
laikas yra dar vienas šaltinis

305
00:14:19,520 --> 00:14:22,520
kad mes gali tekti praleisti
šiek tiek laiko gauti naujų funkcijų.

306
00:14:22,520 --> 00:14:24,020
Ir tada, žinoma, yra eilė.

307
00:14:24,020 --> 00:14:26,227
Mes neisiu į tai
vienas iš daug detalių.

308
00:14:26,227 --> 00:14:27,560
Bet tai labai panašus į dvasią.

309
00:14:27,560 --> 00:14:31,220
Galėčiau įgyvendinti eilę ir
jos atitinkami veiksmai,

310
00:14:31,220 --> 00:14:35,660
Įtraukti į eilę arba dequeue, kaip pridėti arba pašalinti,
tai tik mėgėjas būdas pasakyti tai,

311
00:14:35,660 --> 00:14:38,100
Įtraukti į eilę arba dequeue, kaip nurodyta toliau.

312
00:14:38,100 --> 00:14:41,170
Aš galiu tik pats sau konstrukto
kad vėl turi numerį anketa masyvą,

313
00:14:41,170 --> 00:14:44,000
kad vėl turi dydį,,
bet kodėl aš dabar reikia

314
00:14:44,000 --> 00:14:46,940
sekti iš eilės priekyje?

315
00:14:46,940 --> 00:14:50,630
Man nereikėjo žinoti
mano kamino priekyje.

316
00:14:50,630 --> 00:14:53,570
Na, jei aš vėl dėl
queue-- tegul tiesiog sunku

317
00:14:53,570 --> 00:14:57,870
kodą ją kaip turintys kaip penkių
sveikieji čia potencialiai.

318
00:14:57,870 --> 00:15:00,940
Taigi tai yra nulis, vienas, du, tris, keturis.

319
00:15:00,940 --> 00:15:03,430
Tai bus
renkamus numerius dar kartą.

320
00:15:03,430 --> 00:15:06,940
Ir tai bus vadinamas dydis.

321
00:15:06,940 --> 00:15:10,056
>> Kodėl tai nėra pakankamas
turėti tik dydį?

322
00:15:10,056 --> 00:15:11,680
Na, tegul stumti tuos pačius numerius.

323
00:15:11,680 --> 00:15:14,220
Taigi aš pushed-- Aš enqueued arba stumiama.

324
00:15:14,220 --> 00:15:20,150
Dabar aš į eilę 50, ir tada
51, ir tada 61, ir dot dot dot.

325
00:15:20,150 --> 00:15:21,070
Taigi, kad į eilę.

326
00:15:21,070 --> 00:15:23,176
Aš enqueued 50, tada 51, tada 61.

327
00:15:23,176 --> 00:15:25,050
Ir tai atrodo identiški
prie kamino iki šiol,

328
00:15:25,050 --> 00:15:27,190
išskyrus I do reikia padaryti vieną pakeitimą.

329
00:15:27,190 --> 00:15:33,680
Man reikia atnaujinti šį dydį, todėl aš einu
nuo nulio iki vieno iki dviejų iki trijų dabar.

330
00:15:33,680 --> 00:15:35,760
Kaip man dequeue?

331
00:15:35,760 --> 00:15:36,890
Kas atsitinka su dequeue?

332
00:15:36,890 --> 00:15:41,950
Kas turėtų nukristi šį sąrašą pirmas
jei tai būtų ne Apple Store linija?

333
00:15:41,950 --> 00:15:42,780
Taigi 50.

334
00:15:42,780 --> 00:15:44,700
Taigi tai tipo sunkiau šį kartą.

335
00:15:44,700 --> 00:15:47,880
Kadangi paskutinį kartą tai buvo super
lengva tiesiog padaryti dydis minuso vieną,

336
00:15:47,880 --> 00:15:51,440
Gaunu mano masyvo pabaigos efektyviai
kur šie skaičiai yra, jis pašalina 61.

337
00:15:51,440 --> 00:15:52,920
Bet aš nenoriu pašalinti 61.

338
00:15:52,920 --> 00:15:55,030
Noriu pasinaudoti 50, kuris
ten buvo ne 5:00

339
00:15:55,030 --> 00:15:56,790
išsirikiuoti už
Naujas iPhone "ar" Papuošalą.

340
00:15:56,790 --> 00:16:01,200
Ir taip atsikratyti 50, aš
galite ne tik tai padaryti, tiesa?

341
00:16:01,200 --> 00:16:02,547
Galiu užbraukti 50.

342
00:16:02,547 --> 00:16:04,380
Bet mes tiesiog sakėme
neturi būti taip analinio

343
00:16:04,380 --> 00:16:06,330
kaip subraižyti iš arba slėpti duomenis.

344
00:16:06,330 --> 00:16:08,090
Mes galime tiesiog pamiršti, kur ji yra.

345
00:16:08,090 --> 00:16:12,330
>> Bet jei aš pakeisti mano dydis dabar
du, tai pakanka informacijos

346
00:16:12,330 --> 00:16:15,711
žinoti, kas vyksta mano eilėje?

347
00:16:15,711 --> 00:16:16,680
Ne visai.

348
00:16:16,680 --> 00:16:19,830
Kaip mano dydis yra du, o
kur veikia eilė pradėti,

349
00:16:19,830 --> 00:16:22,980
ypač jei aš vis dar turiu
tie patys numeriai atmintyje.

350
00:16:22,980 --> 00:16:24,260
50, 51, 61.

351
00:16:24,260 --> 00:16:27,090
Taigi man reikia atsiminti
dabar, kai priekinė yra.

352
00:16:27,090 --> 00:16:29,630
Ir taip, aš pasiūliau iki
ten, mes ką tik pavadino

353
00:16:29,630 --> 00:16:33,729
N-tojo priekyje, kurio pradinė
vertė turėjo ką?

354
00:16:33,729 --> 00:16:35,270
Nulis, tik sąrašo pradžia.

355
00:16:35,270 --> 00:16:40,876
Bet dabar be to, mažėjančio
dydis, mes tiesiog prieaugio priekyje.

356
00:16:40,876 --> 00:16:42,000
Dabar čia jau kita problema.

357
00:16:42,000 --> 00:16:43,030
Taigi, kai aš nuolat vyksta.

358
00:16:43,030 --> 00:16:47,520
Tarkim tai yra skaičius
pavyzdžiui, 121, 124, ir tada, Dammit,

359
00:16:47,520 --> 00:16:48,610
Aš iš kosmoso.

360
00:16:48,610 --> 00:16:50,390
Bet palauk, aš nesu.

361
00:16:50,390 --> 00:16:55,630
Taigi šiuo metu į istoriją,
manyti, kad dydis yra vienas, du,

362
00:16:55,630 --> 00:17:00,370
trijų, keturių, todėl manyti, kad
dydis yra keturių, priekinis yra vienas,

363
00:17:00,370 --> 00:17:01,621
taip, 51 yra priekyje.

364
00:17:01,621 --> 00:17:04,329
Noriu įdėti kitą numerį čia
bet, Dammit, aš iš vietos.

365
00:17:04,329 --> 00:17:06,710
Bet aš tikrai ne, tiesa?

366
00:17:06,710 --> 00:17:11,192
Kur galėčiau įdėti kai
pridėtinė vertė, kaip ir 171?

367
00:17:11,192 --> 00:17:13,400
Taip, galėčiau tiesiog rūšies
grįžti ten, tiesa?

368
00:17:13,400 --> 00:17:18,161
Ir tada užbraukti 50 arba
tiesiog perrašyti jį su 171.

369
00:17:18,161 --> 00:17:20,410
Ir jei jums įdomu, kodėl
Mūsų numeriai gavo tiek atsitiktinai,

370
00:17:20,410 --> 00:17:24,150
jie yra paprastai suprantamas kompiuterį
Mokslas kursai Harvarde po CS50.

371
00:17:24,150 --> 00:17:27,510
Bet tai buvo geras optimizavimas,
nes dabar aš ne eikvoti vietos.

372
00:17:27,510 --> 00:17:30,750
Aš vis dar turiu prisiminti
kaip didelis šis dalykas yra bendras.

373
00:17:30,750 --> 00:17:31,500
Tai penkių iš viso.

374
00:17:31,500 --> 00:17:33,375
Nes aš nenoriu
pradėti perrašymui 51.

375
00:17:33,375 --> 00:17:36,260
Taigi, dabar aš vis dar esu iš vietos,
taip, ta pati problema, kaip ir anksčiau.

376
00:17:36,260 --> 00:17:39,140
Bet jūs galite pamatyti, kaip dabar
Jūsų kodas, tikriausiai

377
00:17:39,140 --> 00:17:41,910
turi parašyti šiek tiek daugiau
sudėtingumas, kad tai įvyktų.

378
00:17:41,910 --> 00:17:44,510
Ir iš tiesų, kas operatorius
C tikriausiai leidžia

379
00:17:44,510 --> 00:17:48,110
magiškai šio tikslo, judėjimas ratu?

380
00:17:48,110 --> 00:17:50,160
Taip modulį operatorius,
procentas ženklas.

381
00:17:50,160 --> 00:17:53,160
Taigi, kas tipo kietas apie eilę,
nors mes nuolat piešimo masyvai

382
00:17:53,160 --> 00:17:56,520
nes šie kaip tiesiomis linijomis, jei jums
rūšies galvoti apie tai, kaip kreivumą

383
00:17:56,520 --> 00:18:00,341
aplink, ratu, tada tiesiog
intuityviai tai rūšies darbų psichiškai

384
00:18:00,341 --> 00:18:01,590
Manau, šiek tiek daugiau švariai.

385
00:18:01,590 --> 00:18:05,190
Jūs vis dar turi įgyvendinti
kad psichikos modelis kodą.

386
00:18:05,190 --> 00:18:07,550
Taigi ne tai, kad sunku,
galiausiai, įgyvendinti,

387
00:18:07,550 --> 00:18:12,430
bet mes vis dar prarasti size-- tiksliau,
gebėjimas keisti, nebent mes tai darome.

388
00:18:12,430 --> 00:18:15,310
>> Mes turime atsikratyti masyvo, mes
pakeisti jį su vienu rodyklė,

389
00:18:15,310 --> 00:18:20,010
ir tada kažkur mano kodas, aš turiu
Pokalbio ką veikti, kad iš tikrųjų sukurti

390
00:18:20,010 --> 00:18:23,720
masyvas vadinamas numeriai?

391
00:18:23,720 --> 00:18:26,190
Malloc ar kitu panašiu
funkcija, tiksliai.

392
00:18:26,190 --> 00:18:30,481
Bet kokie kaminai ar eilėse klausimai.

393
00:18:30,481 --> 00:18:30,980
Taip?

394
00:18:30,980 --> 00:18:33,657

395
00:18:33,657 --> 00:18:34,240
Geras klausimas.

396
00:18:34,240 --> 00:18:35,830
Kas modulį jūs naudojate čia.

397
00:18:35,830 --> 00:18:38,520
Taigi apskritai, kai naudojate
Modeliavimas, jums būtų tai padaryti

398
00:18:38,520 --> 00:18:40,620
Su dydis
Visa duomenų struktūra.

399
00:18:40,620 --> 00:18:44,120
Taigi kažkas panašaus penkių ar talpos, jei
tai pastovus, tikriausiai dalyvauja.

400
00:18:44,120 --> 00:18:47,100
Bet tik tai modulo penkių
tikriausiai nepakanka,

401
00:18:47,100 --> 00:18:51,380
nes mes turime žinoti tai mes
apvyniokite aplink čia arba čia arba čia.

402
00:18:51,380 --> 00:18:54,160
Taigi jūs tikriausiai taip pat
ketinate norite įtraukti

403
00:18:54,160 --> 00:18:57,220
iš daikto dydis, arba
priekinis kintamasis, taip pat.

404
00:18:57,220 --> 00:19:00,140
Taigi, tai tik tai gana
paprasta aritmetika išraiška,

405
00:19:00,140 --> 00:19:02,000
bet modulį būtų pagrindinis ingredientas.

406
00:19:02,000 --> 00:19:03,330
>> Taigi trumpas filmas, jei bus.

407
00:19:03,330 --> 00:19:05,780
Animacija, kad kai kurie
žmonės kitame universitete

408
00:19:05,780 --> 00:19:08,060
kartu sudėjus, kad mes
pritaikyti šią diskusiją.

409
00:19:08,060 --> 00:19:12,630
Tai reiškia, Džekas mokymosi
faktai apie eilių ir statistika.

410
00:19:12,630 --> 00:19:19,010

411
00:19:19,010 --> 00:19:21,890
>> Filmas: Kažkada,
ten buvo vaikinas pavadino Džekas.

412
00:19:21,890 --> 00:19:25,330
Kai jis atėjo į priėmimo draugų,
Džekas neturėjo įgūdis.

413
00:19:25,330 --> 00:19:28,220
Taigi Džekas ėjo pasikalbėti su
Populiariausias vaikinas jis žinojo.

414
00:19:28,220 --> 00:19:30,920
Jis nuėjo į Lou ir paklausė: Ką man daryti?

415
00:19:30,920 --> 00:19:33,400
Lu pamatė, kad jo draugas
buvo tikrai nelaimę.

416
00:19:33,400 --> 00:19:36,050
Na, jis pradėjo, tiesiog
atrodo kaip jūs apsirengęs.

417
00:19:36,050 --> 00:19:38,680
Jūs neturite jokių drabužių
su skirtingą išvaizdą?

418
00:19:38,680 --> 00:19:39,660
Taip, sakė Džekas.

419
00:19:39,660 --> 00:19:40,840
Aš tikrai daryti.

420
00:19:40,840 --> 00:19:43,320
Ateik į mano namus ir
Aš jums parodysiu jas jums.

421
00:19:43,320 --> 00:19:44,550
Taigi jie išvyko į Džekas.

422
00:19:44,550 --> 00:19:47,520
Ir Džekas parodė Lou langelį
kur jis laikė visus savo marškinėlius,

423
00:19:47,520 --> 00:19:49,260
ir jo kelnės ir jo kojines.

424
00:19:49,260 --> 00:19:52,290
Lu sako, matau, jūs turite
Visi drabužius į krūvą.

425
00:19:52,290 --> 00:19:54,870
Kodėl ne jūs dėvėti kai
Kiti kartą kurį laiką?

426
00:19:54,870 --> 00:19:58,020
>> Džekas sakė, gerai, kai aš
pašalinti drabužius ir kojines,

427
00:19:58,020 --> 00:20:00,780
Aš nuplaukite juos ir padėkite
juos į lauką.

428
00:20:00,780 --> 00:20:03,210
Tada ateina kitas
rytą ir iki aš apynių.

429
00:20:03,210 --> 00:20:06,380
Aš einu į lauką ir gauti
Mano drabužius išjungti viršuje.

430
00:20:06,380 --> 00:20:09,070
Lou greitai suprato,
Su Jack problema.

431
00:20:09,070 --> 00:20:12,080
Jis nuolat drabužiai, kompaktinių diskų,
ir knygų krūvos.

432
00:20:12,080 --> 00:20:14,420
Kai jis pasiekė
ką skaityti ar nešioti,

433
00:20:14,420 --> 00:20:17,100
jam reikia pasirinkti aukščiausios knygą ar apatinius.

434
00:20:17,100 --> 00:20:19,500
Tada, kai jis buvo padaryta, jis
būtų įdėti ją atgal.

435
00:20:19,500 --> 00:20:21,970
Atgal būtų eiti, ant kamino.

436
00:20:21,970 --> 00:20:24,460
Aš žinau, kad tirpalas,
sakė pergalingas garsiai.

437
00:20:24,460 --> 00:20:27,090
Jums reikia išmokti
pradėti naudoti eilę.

438
00:20:27,090 --> 00:20:29,870
Lou paėmė Džekas drabužius ir
pakabinti juos į spintą.

439
00:20:29,870 --> 00:20:32,710
Ir kada jis ištuštinti
dėžutė, jis tiesiog blaškoma ją.

440
00:20:32,710 --> 00:20:36,500
>> Tada jis tarė: "Dabar Jack pabaigoje
dieną, įdėti savo drabužius kairėje

441
00:20:36,500 --> 00:20:37,990
kai jūs įtraukėte juos šalin.

442
00:20:37,990 --> 00:20:41,300
Tada rytoj ryte, kai jūs
matyti saulės, gauti savo drabužius

443
00:20:41,300 --> 00:20:43,440
dešinėje, nuo linijos pabaigoje.

444
00:20:43,440 --> 00:20:44,880
Ar nematai? sakė Lu.

445
00:20:44,880 --> 00:20:46,370
Tai bus taip malonu.

446
00:20:46,370 --> 00:20:49,770
Jūs dėvėti viską vieną kartą
Prieš dėvėti ką nors du kartus.

447
00:20:49,770 --> 00:20:52,670
Ir su viskuo eilėse
jo spinta ir lentynos,

448
00:20:52,670 --> 00:20:55,160
Džekas pradėjau jausti
visai tikras save.

449
00:20:55,160 --> 00:20:59,720
Visi dėka Lou ir
Jo nuostabius eilė.

450
00:20:59,720 --> 00:21:01,220
GARSIAKALBIS 1: Gerai, tai žavinga.

451
00:21:01,220 --> 00:21:05,920

452
00:21:05,920 --> 00:21:10,080
Taigi, kas buvo iš tikrųjų vyksta
apie po gaubtu dabar?

453
00:21:10,080 --> 00:21:12,370
Kad mes turime patarimų,
kad mes turime malloc,

454
00:21:12,370 --> 00:21:15,680
kad mes turime galimybę sukurti
gabaliukus atminties sau

455
00:21:15,680 --> 00:21:16,344
dinamiškai.

456
00:21:16,344 --> 00:21:18,510
Taigi tai yra paveikslėlyje
prabėgomis tik kitą dieną.

457
00:21:18,510 --> 00:21:21,180
Mes tikrai ne gyventi
ant jo, bet šis vaizdas

458
00:21:21,180 --> 00:21:24,180
vyksta jau po
už savaites dangtis dabar.

459
00:21:24,180 --> 00:21:27,050
Ir taip tai yra, tiesiog
stačiakampis, kad mes išdarinėtos,

460
00:21:27,050 --> 00:21:28,180
kompiuterio atmintyje.

461
00:21:28,180 --> 00:21:31,850
O gal jūsų kompiuteryje, arba CS50
ID turi atmintį arba RAM GIGABYTE

462
00:21:31,850 --> 00:21:33,050
arba du gigabaitai ar keturi.

463
00:21:33,050 --> 00:21:34,450
Jis tikrai ne klausimas.

464
00:21:34,450 --> 00:21:37,240
Jūsų operacinė sistema
"Windows" arba "Mac OS ar Linux

465
00:21:37,240 --> 00:21:41,120
iš esmės leidžia savo programą
manyti, kad ji turi prieigą

466
00:21:41,120 --> 00:21:42,982
į visas
kompiuterio atmintis,

467
00:21:42,982 --> 00:21:45,440
nors jums gali būti rodomi
daug programų vienu metu.

468
00:21:45,440 --> 00:21:46,990
Taigi iš tikrųjų, kad tikrai ne dirbti.

469
00:21:46,990 --> 00:21:49,448
Bet tai tipo iliuzija
teikiama visus savo programas.

470
00:21:49,448 --> 00:21:53,110
Taigi, jei jūs turėjo du koncertai RAM, tai
yra, kaip kompiuteris gali galvoti apie tai.

471
00:21:53,110 --> 00:21:57,110
>> Dabar atsitiktinai, vienas iš šių
daiktai, vienas iš šių atminties segmentus,

472
00:21:57,110 --> 00:21:58,350
vadinamas kamino.

473
00:21:58,350 --> 00:22:01,680
Ir iš tiesų bet kuriuo metu
taip toli rašyti kodą

474
00:22:01,680 --> 00:22:05,900
kad turite vadinamas
funkcija, pavyzdžiui vamzdynui.

475
00:22:05,900 --> 00:22:08,410
Prisiminkite, kad bet kuriuo metu aš
Nupiešti kompiuterio atmintis,

476
00:22:08,410 --> 00:22:10,640
Aš visada atkreipti rūšiuoti
pusė stačiakampio čia

477
00:22:10,640 --> 00:22:12,520
ir nesivargina kalbėti
apie tai, kas aukščiau.

478
00:22:12,520 --> 00:22:15,980
Nes kai pagrindinis yra vadinamas, aš teigti,
kad jūs gaunate šį atminties rakštis

479
00:22:15,980 --> 00:22:16,970
kad krinta čia.

480
00:22:16,970 --> 00:22:20,650
Ir jei pagrindinis vadinama funkcija
kaip apsikeitimo, gerai apsikeitimo eina čia.

481
00:22:20,650 --> 00:22:23,720
Ir it turns out, kad tai
kur jis baigiant.

482
00:22:23,720 --> 00:22:26,277
Apie vadinamąjį kamino
viduje kompiuterio atmintyje.

483
00:22:26,277 --> 00:22:28,360
Šiuo metu yra dienos pabaigoje,
tai tik adresus.

484
00:22:28,360 --> 00:22:30,680
Tai tarsi baitas lygus nuliui,
baitas vienas, baitas 2 mlrd.

485
00:22:30,680 --> 00:22:33,130
Bet jeigu jūs manote apie tai
kaip šio stačiakampio objektą,

486
00:22:33,130 --> 00:22:35,130
visi mes darome kiekvieną
kartą mes vadiname funkcija

487
00:22:35,130 --> 00:22:37,180
sluoksniavimasis naują gabaliuką atmintį.

488
00:22:37,180 --> 00:22:41,700
Mes teikiame šią funkciją gabaliuką
iš savo atminties dirbti.

489
00:22:41,700 --> 00:22:44,490
>> Ir prisiminti, kad dabar tai yra svarbu.

490
00:22:44,490 --> 00:22:46,400
Nes jei mes turime
kažkas panašaus apsikeitimo

491
00:22:46,400 --> 00:22:51,610
ir du vietiniai kintamieji, pavyzdžiui, A ir B
mes pakeisti šias vertybes iš vienos ir dviejų

492
00:22:51,610 --> 00:22:55,130
iki dviejų ir vieno, prisiminti
kad kai apsikeitimo grįžta,

493
00:22:55,130 --> 00:22:58,330
tai kaip nors šį gabaliuką
atminties yra tik dingo.

494
00:22:58,330 --> 00:23:00,080
Iš tikrųjų, tai dar
ten teismo ekspertizės.

495
00:23:00,080 --> 00:23:01,940
Ir kažkas dar iš tikrųjų egzistuoja.

496
00:23:01,940 --> 00:23:05,410
Bet konceptualiai, tai taip
Nors tai visiškai dingo.

497
00:23:05,410 --> 00:23:10,910
Ir taip pagrindinė nepažįsta bet darbo
kad buvo padaryta toje apsikeitimo funkcija,

498
00:23:10,910 --> 00:23:14,890
nebent tai tikrai praėjo tie
argumentai žymeklis ar nuorodą.

499
00:23:14,890 --> 00:23:17,790
Dabar esminis sprendimas
į šią problemą su apsikeitimo sandoriu,

500
00:23:17,790 --> 00:23:19,970
bėga dalykų pagal adresą.

501
00:23:19,970 --> 00:23:23,250
Tačiau paaiškėja, taip pat tai, kas
vyksta virš tos dalies

502
00:23:23,250 --> 00:23:26,330
stačiakampio visa tai laikas yra
dar yra daugiau atminties ten.

503
00:23:26,330 --> 00:23:28,790
Ir kai jūs dinamiškai
paskirstyti atmintį,

504
00:23:28,790 --> 00:23:32,020
ar tai viduje GetString, kuris
mes darome Jums į CS50

505
00:23:32,020 --> 00:23:34,710
biblioteka, arba, jei jus vaikinai
skambinti malloc ir paklausti

506
00:23:34,710 --> 00:23:37,950
operacinės sistemos iš riekė
atminties, jis nėra ateis iš kamino.

507
00:23:37,950 --> 00:23:40,960
Jis kilęs iš kitoje vietoje
jūsų kompiuterio atmintyje

508
00:23:40,960 --> 00:23:42,220
Tai vadinama krūvos.

509
00:23:42,220 --> 00:23:43,430
Ir tai ne koks nors kitoks.

510
00:23:43,430 --> 00:23:44,285
Tai tas pats RAM.

511
00:23:44,285 --> 00:23:45,160
Tai tas pats atminties.

512
00:23:45,160 --> 00:23:49,080
Tai tiesiog RAM tai iki
ten vietoj žemyn čia.

513
00:23:49,080 --> 00:23:50,750
>> Ir taip, ką tai reiškia?

514
00:23:50,750 --> 00:23:53,650
Na, jei jūsų kompiuteris turi
baigtinis atminties kiekis

515
00:23:53,650 --> 00:23:57,450
ir kamino auga, todėl
kalbėti, o krūva, pagal

516
00:23:57,450 --> 00:23:59,349
šios rodyklės, auga žemyn.

517
00:23:59,349 --> 00:24:01,140
Kitaip tariant, kiekvienas
laikas skambinate malloc,

518
00:24:01,140 --> 00:24:03,430
jūs suteikiamas gabaliuką
atminties iš aukščiau,

519
00:24:03,430 --> 00:24:06,630
tada gal šiek tiek mažesnis, tada šiek tiek
mažesnis, kiekvieną kartą jums skambinti malloc,

520
00:24:06,630 --> 00:24:10,100
krūvos, tai naudojimas,
rūšies auga,

521
00:24:10,100 --> 00:24:11,950
auga arčiau ir arčiau, ką?

522
00:24:11,950 --> 00:24:13,382
Kamino.

523
00:24:13,382 --> 00:24:14,840
Taigi ar tai atrodo kaip gera idėja?

524
00:24:14,840 --> 00:24:18,420

525
00:24:18,420 --> 00:24:22,140
Aš turiu galvoje, kur ji tikrai nėra aišku,
Ką dar galite daryti, jei tik

526
00:24:22,140 --> 00:24:23,910
turi baigtinį kiekį atminties.

527
00:24:23,910 --> 00:24:25,200
Bet tai tikrai blogai.

528
00:24:25,200 --> 00:24:27,920
Šios dvi strėlės yra ant
avarijos kursą vienas su kitu.

529
00:24:27,920 --> 00:24:31,930
>> Ir paaiškėja, kad blogas vaikinas, žmonės, kurie
yra ypač gerai su programavimo,

530
00:24:31,930 --> 00:24:36,140
ir bando nulaužti į kompiuterius,
gali išnaudoti šią tikrovę.

531
00:24:36,140 --> 00:24:38,290
Tiesą sakant, aptarkime
šiek tiek fragmentą.

532
00:24:38,290 --> 00:24:41,350
Taigi tai yra pavyzdys galite skaityti
apie išsamiau Vikipedijoje.

533
00:24:41,350 --> 00:24:43,100
Mes jums taško
straipsnis, jei įdomu.

534
00:24:43,100 --> 00:24:45,650
Bet yra ataka paprastai
žinomas kaip buferio, kad

535
00:24:45,650 --> 00:24:49,570
gyvuoja tol, kol žmonėms
turėjo galimybę manipuliuoti

536
00:24:49,570 --> 00:24:53,120
kompiuterio atmintyje, ypač C.
Taigi tai yra labai savavališkas programa,

537
00:24:53,120 --> 00:24:55,130
bet tegul jį perskaityti iš apačios į viršų.

538
00:24:55,130 --> 00:24:57,650
Pagrindinė į argc char žvaigždutėmis argv.

539
00:24:57,650 --> 00:24:59,830
Taigi, tai programa, kuri trunka
komandinės eilutės argumentai.

540
00:24:59,830 --> 00:25:03,620
Ir visa pagrindinė neturi matyt yra skambutis
funkcija, ją vadina F paprastumo.

541
00:25:03,620 --> 00:25:04,610
Ir jis eina į ką?

542
00:25:04,610 --> 00:25:05,490
Argv vienas.

543
00:25:05,490 --> 00:25:09,320
Taigi jis eina į F kokia
žodis yra tai, kad naudotojas atspausdintos

544
00:25:09,320 --> 00:25:11,500
ne po eilutę
Programos pavadinimas ne visiems.

545
00:25:11,500 --> 00:25:15,730
Taigi, panašiai kaip Cezaris ar Vigenere, kuris
jums gali prisiminti daro su argv.

546
00:25:15,730 --> 00:25:16,680
>> Taigi, kas yra F?

547
00:25:16,680 --> 00:25:19,760
F trunka eilutę
jos vienintelis argumentas,

548
00:25:19,760 --> 00:25:22,100
AKA char žvaigždė, pats
dalykas, kaip eilutę.

549
00:25:22,100 --> 00:25:24,920
Ir tai vadinama savavališkai
bar šiame pavyzdyje.

550
00:25:24,920 --> 00:25:27,710
Ir tada char C 12,
tik profanas sąlygomis,

551
00:25:27,710 --> 00:25:31,750
kas char c laikiklis 12 daro mus?

552
00:25:31,750 --> 00:25:33,440
Kas tai daryti?

553
00:25:33,440 --> 00:25:36,490
Paskirstyti atmintį, ypač
12 baitų 12 simbolių.

554
00:25:36,490 --> 00:25:36,990
Būtent.

555
00:25:36,990 --> 00:25:40,000
Ir tada paskutinė eilutė, išmaišyti ir
Kopijuoti, jūs tikriausiai nematė.

556
00:25:40,000 --> 00:25:43,360
Tai eilutė kopija
funkcija, kurios tikslas gyvenime

557
00:25:43,360 --> 00:25:48,160
yra nukopijuoti savo antrąjį argumentą
į pirmąjį argumentą,

558
00:25:48,160 --> 00:25:51,190
tačiau tik iki tam tikros
tikras baitų skaičius.

559
00:25:51,190 --> 00:25:53,860
Taigi trečiasis argumentas sako,
kiek baitų turėtumėte nukopijuoti?

560
00:25:53,860 --> 00:25:56,720
Iš juostos ilgis,
kokia vartotojas įvedėte.

561
00:25:56,720 --> 00:25:59,320
Ir turinys
Baras, kad eilutė yra

562
00:25:59,320 --> 00:26:02,330
nukopijuoti į atminties nurodė esant C

563
00:26:02,330 --> 00:26:04,060
>> Taigi, šis atrodo rūšies kvailas, ir jis yra.

564
00:26:04,060 --> 00:26:06,300
Tai nenatūralu pavyzdys,
bet tai atstovas

565
00:26:06,300 --> 00:26:10,100
iš atakų vektorius klasės,
iš puola programą būdas.

566
00:26:10,100 --> 00:26:15,050
Viskas yra gerai ir gerai, jei vartotojas
tipai Žodžiu tai 11 simbolių

567
00:26:15,050 --> 00:26:18,040
arba mažiau, plius Backslash nulis.

568
00:26:18,040 --> 00:26:22,830
Ką daryti, jei vartotojas įveda į daugiau nei
11 arba 12 arba 20 arba 50 simbolių?

569
00:26:22,830 --> 00:26:25,090
Kas tai programa ketinate daryti?

570
00:26:25,090 --> 00:26:29,360
Potencialiai SEG kaltė. Tai vyksta
aklai kopijuoti viską bare iki

571
00:26:29,360 --> 00:26:31,750
į jo ilgį, kuris yra
tiesiog viskas juostoje,

572
00:26:31,750 --> 00:26:36,307
į adresą nurodė C. Bet C
tik Preemptively skiriamas kaip 12 baitų.

573
00:26:36,307 --> 00:26:37,640
Tačiau nėra papildomas patikrinimas.

574
00:26:37,640 --> 00:26:38,700
Nėra jeigu sąlygomis.

575
00:26:38,700 --> 00:26:40,580
Nėra klaidų tikrinimas čia.

576
00:26:40,580 --> 00:26:43,270
>> Ir taip, tai ką ši programa yra
ketina padaryti, tai tiesiog aklai

577
00:26:43,270 --> 00:26:45,750
nukopijuoti vieną dalyką į kitą.

578
00:26:45,750 --> 00:26:47,880
Ir todėl, jei mes atkreipiame tai
kaip paveikslėlyje, čia

579
00:26:47,880 --> 00:26:49,860
tik iš atminties rakštis.

580
00:26:49,860 --> 00:26:53,470
Taigi pranešimas apačioje, mes
turi vietinį kintamąjį baras.

581
00:26:53,470 --> 00:26:57,330
Taip, kad žymeklis, kad ketina store--
o tos vietos argumentą, kad manimi

582
00:26:57,330 --> 00:26:58,672
ketina laikyti styginių baras.

583
00:26:58,672 --> 00:27:00,380
Ir tada pastebėti tik
virš jo per kaminą,

584
00:27:00,380 --> 00:27:02,505
nes kiekvieną kartą, jūs paprašykite
Memory dėl kaminą,

585
00:27:02,505 --> 00:27:04,310
jis eina truputį
virš jo pavaizduotomis piktogramo-,

586
00:27:04,310 --> 00:27:06,270
Atkreipkite dėmesį, kad mes turime ten 12 baitų.

587
00:27:06,270 --> 00:27:10,690
Viršutiniame kairiajame vienas yra C laikiklis nulis ir
apačioje dešinėje yra C laikiklis 11.

588
00:27:10,690 --> 00:27:12,870
Tai tiesiog kaip kompiuteriai
ketina nustatyti jį.

589
00:27:12,870 --> 00:27:18,300
Taigi tiesiog intuityviai, jei juosta turi daugiau
kaip 12 simbolių iš viso, įskaitant

590
00:27:18,300 --> 00:27:25,790
"Backslash nulis, kur yra
12 arba C laikiklis 12 ketinate eiti?

591
00:27:25,790 --> 00:27:28,440
Arba, tiksliau, kur yra 12
požymis ar 13 simbolių,

592
00:27:28,440 --> 00:27:30,900
šimtoji charakteris vyksta
baigti paveikslėlyje?

593
00:27:30,900 --> 00:27:33,400
Aukščiau ar žemiau?

594
00:27:33,400 --> 00:27:36,300
>> Teisė, nes net
pati kamino auga aukštyn,

595
00:27:36,300 --> 00:27:39,590
kai jūs įdėti stuff
jis, ji dėl dizaino,

596
00:27:39,590 --> 00:27:41,294
kelia atmintį nuo viršaus iki apačios.

597
00:27:41,294 --> 00:27:44,460
Taigi, jei jūs turite daugiau nei 12 baitų,
jūs ketinate pradėti perrašyti baras.

598
00:27:44,460 --> 00:27:47,280
Dabar tai klaida, bet tai
tikrai ne big deal.

599
00:27:47,280 --> 00:27:51,130
Bet tai yra baisi, nes ten
daugiau daiktų vyksta atmintyje.

600
00:27:51,130 --> 00:27:53,074
Taigi čia, kaip mes galime
įdėti Sveiki, būtų aiškus.

601
00:27:53,074 --> 00:27:54,490
Jei aš įvedėte Hello eilutėje.

602
00:27:54,490 --> 00:27:59,330
H-E-L-L-O Backslash nulis, baigiasi per
tie 12 baitų, o mes super saugus.

603
00:27:59,330 --> 00:28:00,330
Viskas gerai.

604
00:28:00,330 --> 00:28:03,020
Bet jei aš tipo kažką
ilgiau, potencialiai tai

605
00:28:03,020 --> 00:28:05,860
vyksta slinkti į baro erdvėje.

606
00:28:05,860 --> 00:28:08,405
Bet dar blogiau, paaiškėja
iš viso to laiko,

607
00:28:08,405 --> 00:28:11,530
nors mes niekada kalbėjo apie
tai, kamino naudojamas kitų dalykų.

608
00:28:11,530 --> 00:28:13,560
Tai ne tik vietiniai kintamieji.

609
00:28:13,560 --> 00:28:15,100
>> C yra labai žemo lygio kalba.

610
00:28:15,100 --> 00:28:17,810
Ir tai tarsi slapta
naudoja krūvą taip pat

611
00:28:17,810 --> 00:28:21,260
prisiminti kai
funkcija vadinama, ką

612
00:28:21,260 --> 00:28:26,040
adresas yra ankstesnio funkciją,
todėl ji gali šokinėti atgal į tą funkciją.

613
00:28:26,040 --> 00:28:29,980
Taigi, kai pagrindiniai skambučiai apsikeitimo tarp
ką užmaunamas ant kamino

614
00:28:29,980 --> 00:28:34,380
yra ne tik apsikeitimo vietinius kintamuosius,
ar jos argumentai, taip pat slapta stumiama

615
00:28:34,380 --> 00:28:37,510
ant kamino kaip pavaizduota
raudonu gabaliuką čia

616
00:28:37,510 --> 00:28:40,520
yra pagrindinė adresas fiziškai
jūsų kompiuterio atmintyje,

617
00:28:40,520 --> 00:28:44,180
taip, kad, kai apsikeitimo yra padaryta, kad kompiuteris
žino, man reikia grįžti į pagrindinį

618
00:28:44,180 --> 00:28:46,760
ir baigti vykdyti pagrindinę funkciją.

619
00:28:46,760 --> 00:28:51,960
Taigi tai yra pavojinga dabar, nes jei
vartotojas įveda gerai daugiau nei Sveiki,

620
00:28:51,960 --> 00:28:57,030
pavyzdžiui, kad vartotojo įvesties clobbers
arba perrašo tą raudoną skyrių,

621
00:28:57,030 --> 00:28:59,820
logiškai, jei kompiuterio
tik ketina aklai prisiimti

622
00:28:59,820 --> 00:29:03,830
kad tos raudonos gabalas baitai
adresas, kuriuo ji turėtų grįžti,

623
00:29:03,830 --> 00:29:09,020
Ką daryti, jei priešas yra pakankamai protingas, arba
laimė įdėti baitų seka

624
00:29:09,020 --> 00:29:13,450
ten, kad atrodo kaip adresą,
bet tai kodo adresas

625
00:29:13,450 --> 00:29:18,730
kad jis ar ji nori kompiuterį
vykdyti vietoj pagrindinis?

626
00:29:18,730 --> 00:29:21,670
>> Kitaip tariant, jei ką
vartotojas rašyti ne laiku,

627
00:29:21,670 --> 00:29:23,850
yra ne tik kažkas
nežalingas, kaip labas,

628
00:29:23,850 --> 00:29:28,210
bet tai tikrai kodas, kuris yra lygiavertis
ištrinti visus šio vartotojo failus?

629
00:29:28,210 --> 00:29:30,060
Arba elektroniniu paštu savo slaptažodį mane?

630
00:29:30,060 --> 00:29:31,940
Arba pradėti prisijungdami savo
klavišų, tiesa?

631
00:29:31,940 --> 00:29:34,920
Yra būdas, tegul numato šiandien
kad jie galėtų įvesti ne tik labas

632
00:29:34,920 --> 00:29:36,711
Pasaulio ar jų pavadinimas,
jie iš esmės gali

633
00:29:36,711 --> 00:29:39,570
praeiti kodas, nulių ir
tie, kad kompiuteris

634
00:29:39,570 --> 00:29:43,450
klaidų abiems kodą ir adresą.

635
00:29:43,450 --> 00:29:48,950
Taigi nors ir šiek tiek abstrakčiai, jei
vartotojas įveda į pakankamai rungimosi kodas

636
00:29:48,950 --> 00:29:52,330
kad mes apibendrinti čia taip
A. A yra ataka ar priešai.

637
00:29:52,330 --> 00:29:53,140
Taigi tiesiog blogas stuff.

638
00:29:53,140 --> 00:29:55,306
Mums nerūpi apie
numeriai arba nuliai ar tie

639
00:29:55,306 --> 00:29:59,470
Šiandien, pavyzdžiui, kad jūs galų gale
perrašyti tą raudoną skyrių,

640
00:29:59,470 --> 00:30:01,580
pastebėti, kad baitų seka.

641
00:30:01,580 --> 00:30:05,020
O 835 Cnulis aštuoni nulis.

642
00:30:05,020 --> 00:30:08,960
Ir dabar taip Vikipedijos straipsnio čia
pasiūlė, jei dabar iš tikrųjų pradėti

643
00:30:08,960 --> 00:30:12,460
ženklinimo jūsų kompiuterio baitų
atminties, koks Vikipedijos straipsnis yra

644
00:30:12,460 --> 00:30:19,060
Pasiūlymą yra tai, kas jei adresas
tos viršutiniame kairiajame baitas yra 80 C 0 3508.

645
00:30:19,060 --> 00:30:22,200
>> Kitaip tariant, jei blogiukas yra
pakankamai protingas su savo kodą

646
00:30:22,200 --> 00:30:26,650
kad iš tikrųjų įdėti numerį čia, kad
atitinka kodas adresą

647
00:30:26,650 --> 00:30:29,180
jis ar ji švirkščiama
į kompiuterį, galite

648
00:30:29,180 --> 00:30:31,050
gali apgauti kompiuterį
į ką nors.

649
00:30:31,050 --> 00:30:34,140
Šalinti failus, elektroninio pašto siuntimas
dalykų, uostyti savo srautą,

650
00:30:34,140 --> 00:30:36,710
tiesiog nieko galėtų būti
įpurškiamas į kompiuterį.

651
00:30:36,710 --> 00:30:39,220
Ir taip buferio
ataka jos branduolys

652
00:30:39,220 --> 00:30:43,530
yra tik kvailas, kvailas
rankinis masyvo, kad

653
00:30:43,530 --> 00:30:45,840
neturėjo patikrintas jos ribų.

654
00:30:45,840 --> 00:30:48,850
Ir tai, kas yra super pavojingas
ir tuo pat metu itin galingas

655
00:30:48,850 --> 00:30:52,560
C yra tai, kad mes iš tikrųjų turi
prieiga į bet kurią atminties.

656
00:30:52,560 --> 00:30:55,320
Tai iki mūsų programuotojai,
kurie rašo originalų kodą

657
00:30:55,320 --> 00:30:59,330
patikrinti adyti ilgį bet
masyvai, kad mes manipuliuoti.

658
00:30:59,330 --> 00:31:00,750
Taigi, kad būtų aišku, kas yra pataisyti?

659
00:31:00,750 --> 00:31:03,190
Jei mes įvirsta į tai
kodas, aš ne tik

660
00:31:03,190 --> 00:31:08,000
pakeisti baro ilgį, kas
dar turėčiau būti patikrinti?

661
00:31:08,000 --> 00:31:10,620
Ką dar turėčiau daryti, kad
išvengti šio užpuolimo visiškai?

662
00:31:10,620 --> 00:31:14,110
Aš nenoriu pasakyti, tiesiog aklai
kad jums reikia nukopijuoti tiek baitų

663
00:31:14,110 --> 00:31:16,140
taip pat kaip ir baro ilgis.

664
00:31:16,140 --> 00:31:18,910
Noriu pasakyti, kopijuoti kaip
daug baitų kaip yra baro

665
00:31:18,910 --> 00:31:24,090
iki paskirta
atminties arba 12 maksimaliai.

666
00:31:24,090 --> 00:31:27,450
Taigi man reikia šiek tiek, jei sąlyga natūra
kad daro patikrinti juostos ilgis,

667
00:31:27,450 --> 00:31:32,800
bet jei jis viršija 12, mes tiesiog sunku kodą
12 kaip didžiausią galimą atstumą.

668
00:31:32,800 --> 00:31:35,910
Priešingu atveju vadinamasis buferis
perpildymo ataka gali atsitikti.

669
00:31:35,910 --> 00:31:38,451
Esančios šių skaidres apačioje,
Jei įdomu skaityti daugiau

670
00:31:38,451 --> 00:31:41,200
yra tikrasis originalus straipsnis
Jei norite pažvelgti.

671
00:31:41,200 --> 00:31:44,550
>> Bet dabar, be kainų
mokama čia buvo neefektyvumą.

672
00:31:44,550 --> 00:31:46,680
Taigi, tai buvo greitai
žemo lygio Apžvelkite ką

673
00:31:46,680 --> 00:31:49,709
problemų gali kilti, dabar, kad mes
turėti prieigą prie kompiuterio atmintyje.

674
00:31:49,709 --> 00:31:51,750
Bet kita problema, mes
jau suklupo pirmadienį

675
00:31:51,750 --> 00:31:53,800
buvo tik neefektyvumas
Susietos sąrašą.

676
00:31:53,800 --> 00:31:56,019
Mes grįžti į linijinio laiko.

677
00:31:56,019 --> 00:31:57,560
Mes nebeturime vientisą masyvą.

678
00:31:57,560 --> 00:31:58,980
Neturime laisvą prieigą.

679
00:31:58,980 --> 00:32:00,710
Mes negalime naudoti kvadratinių laikiklis notacijos.

680
00:32:00,710 --> 00:32:04,590
Mes tiesiog turime naudoti, o kilpa
kaip vieną parašiau prieš momentas.

681
00:32:04,590 --> 00:32:09,740
Tačiau pirmadienį, mes teigė, kad mes galime
slinkti atgal į efektyvumo srityje

682
00:32:09,740 --> 00:32:13,040
pasiekti kažką, kad
logaritminė galbūt, arba geriausia dar,

683
00:32:13,040 --> 00:32:16,120
gal net kažkas, kad yra
Vadinamasis pastovus laikas.

684
00:32:16,120 --> 00:32:19,840
Taigi, kaip mes galime padaryti, kad naudojant šiuos naujus
Įrankiai, šie adresai, šiuos patarimus,

685
00:32:19,840 --> 00:32:22,210
ir sriegimo dalykų mūsų pačių?

686
00:32:22,210 --> 00:32:23,960
Na, tarkime, kad
čia, tai yra krūva

687
00:32:23,960 --> 00:32:27,170
skaičių, kad mes norime Laikyti
duomenų struktūra ir paieškos efektyviai.

688
00:32:27,170 --> 00:32:30,960
Mes galime visiškai atsukti į savaitę
du, mesti juos į masyvą,

689
00:32:30,960 --> 00:32:33,150
ir ieškoti juos naudojant dvejetainį paiešką.

690
00:32:33,150 --> 00:32:34,040
Skaldyk ir valdyk.

691
00:32:34,040 --> 00:32:37,720
Ir iš tiesų parašė
dvejetainis Ieškoti PSET3,

692
00:32:37,720 --> 00:32:40,100
kur įgyvendino suradimas programą.

693
00:32:40,100 --> 00:32:40,890
Bet žinote ką.

694
00:32:40,890 --> 00:32:45,060
Yra rūšies daugiau
protingas būdas tai padaryti.

695
00:32:45,060 --> 00:32:47,390
Tai šiek tiek daugiau
sudėtingas ir galbūt

696
00:32:47,390 --> 00:32:50,830
leidžia mums pamatyti, kodėl dvejetainis
Paieška yra labai daug greičiau.

697
00:32:50,830 --> 00:32:52,980
Pirma, galime pristatyti
medžio sąvoka.

698
00:32:52,980 --> 00:32:54,730
Kuris nors iš
realybė medžiai rūšies

699
00:32:54,730 --> 00:32:57,730
augti kaip šis, į kompiuterį pasaulyje
Mokslas jie rūšies auga žemyn

700
00:32:57,730 --> 00:33:00,830
kaip šeimos medį, kur jūs turite
jūsų seneliai ar proseneliai

701
00:33:00,830 --> 00:33:04,580
arba Plauktiņš viršuje, patriarchas ir
šeimos matriarch, tik vienas

702
00:33:04,580 --> 00:33:07,930
Vadinamasis šaknis, mazgas, toliau
kuri yra jo vaikai,

703
00:33:07,930 --> 00:33:11,442
žemiau kurios yra jos vaikai, arba
jos palikuonys apskritai.

704
00:33:11,442 --> 00:33:13,400
Ir nors kabinti ne
šeimos apačios

705
00:33:13,400 --> 00:33:16,070
medis, Be to, kad
Jauniausias šeimoje,

706
00:33:16,070 --> 00:33:19,520
taip pat gali būti tiesiog bendrine
vadinama medžio lapai.

707
00:33:19,520 --> 00:33:21,800
>> Taigi tai yra tik krūva
žodžių ir apibrėžimų

708
00:33:21,800 --> 00:33:25,790
kažko vadinamas į kompiuterį medis
Mokslas, panašiai kaip šeimos medį.

709
00:33:25,790 --> 00:33:28,770
Bet yra mėgėjas įsikūnijimų
medžių, iš kurių vienas

710
00:33:28,770 --> 00:33:30,780
vadinamas dvejetainis paieškos medis.

711
00:33:30,780 --> 00:33:34,380
Ir jūs galite rūšies Tease
be ko šis dalykas veikia.

712
00:33:34,380 --> 00:33:37,180
Na, tai dvejetainis, kokia prasme?

713
00:33:37,180 --> 00:33:41,455
Kur dvejetainis iš čia?

714
00:33:41,455 --> 00:33:41,955
Atsiprašome?

715
00:33:41,955 --> 00:33:45,961

716
00:33:45,961 --> 00:33:47,210
Tai ne tiek arba.

717
00:33:47,210 --> 00:33:52,000
Tai daugiau, kad kiekvienas iš mazgų neturi
daugiau nei du vaikai, kaip matome čia.

718
00:33:52,000 --> 00:33:54,990
Apskritai, tree-- ir
Jūsų tėvai ir seneliai

719
00:33:54,990 --> 00:33:57,640
gali turėti daug vaikų arba
VaikaiĨiai kaip jie iš tikrųjų nori,

720
00:33:57,640 --> 00:34:00,820
ir taip, pavyzdžiui, ten mes turime tris
vaikai išjungti, kad dešinėje mazgas,

721
00:34:00,820 --> 00:34:05,480
bet dvejetainis medis, mazgas turi
nulis, vienas arba du vaikai maksimaliai.

722
00:34:05,480 --> 00:34:08,496
Ir tai gražus nuosavybė,
nes jei jis uždėtas dviejų,

723
00:34:08,496 --> 00:34:10,620
mes ketiname būti suteikta galimybė
gauti šiek tiek žurnalo bazę du

724
00:34:10,620 --> 00:34:11,975
veiksmas vyksta čia galiausiai.

725
00:34:11,975 --> 00:34:13,350
Taigi, mes turime kažką logaritminis.

726
00:34:13,350 --> 00:34:14,558
Bet daugiau apie tai per akimirką.

727
00:34:14,558 --> 00:34:19,810
Paieška medis reiškia, kad skaičiai yra
išdėstytos taip, kad kairysis vaiko

728
00:34:19,810 --> 00:34:22,429
vertė yra didesnė už šaknies.

729
00:34:22,429 --> 00:34:26,010
Ir jo teisė vaikas
didesnis nei šaknų.

730
00:34:26,010 --> 00:34:29,290
Kitaip tariant, jei bet kuris iš imtis
mazgai, šiuo paveikslėlyje apskritimai,

731
00:34:29,290 --> 00:34:31,840
ir žiūri į savo kairę
Vaikas ir jo teisė vaikas

732
00:34:31,840 --> 00:34:34,739
pirmasis turėtų būti mažesnis nei,
antrasis turėtų būti didesnė nei.

733
00:34:34,739 --> 00:34:36,159
Taigi normalumas patikrinti 55.

734
00:34:36,159 --> 00:34:37,780
Jis paliko vaiką yra 33.

735
00:34:37,780 --> 00:34:38,620
Tai mažiau nei.

736
00:34:38,620 --> 00:34:40,929
55, jo teisė vaikas yra 77.

737
00:34:40,929 --> 00:34:41,783
Tai daugiau nei.

738
00:34:41,783 --> 00:34:43,199
Ir tai rekursywny apibrėžimas.

739
00:34:43,199 --> 00:34:46,480
Mes galime patikrinti kiekvieną iš tų vieną
mazgai ir tas pats modelis būtų laikyti.

740
00:34:46,480 --> 00:34:49,389
>> Taigi, kas yra malonu A
dvejetainis paieškos medis, yra

741
00:34:49,389 --> 00:34:52,204
kad vienas, mes galime ją įgyvendinti
su struct, tiesiog patinka.

742
00:34:52,204 --> 00:34:54,620
Ir nors mes mesti
daug struktūrų jūsų,

743
00:34:54,620 --> 00:34:56,560
jie šiek tiek
dabar intuityvus tikiuosi.

744
00:34:56,560 --> 00:35:00,570
Sintaksė yra vis dar neaiškus tikrai,
Bet mazgas turinys šioje grupėje

745
00:35:00,570 --> 00:35:02,786
context-- ir mes nuolat
naudojant žodį mazgas,

746
00:35:02,786 --> 00:35:04,910
ar tai stačiakampis
ekrane arba ratu,

747
00:35:04,910 --> 00:35:08,970
tai tik keletas bendrinis konteineris,
šiuo atveju medžio, kaip ir viename

748
00:35:08,970 --> 00:35:11,780
matėme, turime sveikąjį skaičių
kiekviena iš mazgų

749
00:35:11,780 --> 00:35:15,460
ir tada man reikia dviejų patarimų nukreipta
į kairę vaiko ir dešinės vaikui,

750
00:35:15,460 --> 00:35:16,590
atitinkamai.

751
00:35:16,590 --> 00:35:20,730
Štai kaip mes galime
įgyvendinti, kad į struct.

752
00:35:20,730 --> 00:35:22,315
Ir kaip galėčiau ją įgyvendinti kodas?

753
00:35:22,315 --> 00:35:26,730
Na, Paimkime greitai
pažvelgti į šią mažą pavyzdį.

754
00:35:26,730 --> 00:35:29,820
Tai nėra funkcionalus, bet aš
kopijuoti ir įklijuoti tą struktūrą.

755
00:35:29,820 --> 00:35:33,510
Ir jei mano funkcija dvejetainis
Paieška medis vadinamas paieška,

756
00:35:33,510 --> 00:35:36,980
ir tai trunka du argumentus,
sveikas skaičius, N ir rodyklė

757
00:35:36,980 --> 00:35:41,400
į mazgą, todėl rodyklę į medį
arba rodyklė į medį šaknis,

758
00:35:41,400 --> 00:35:43,482
kaip man eiti apie paieškos N?

759
00:35:43,482 --> 00:35:45,440
Na, visų pirma, nes aš
sprendžiant su rodyklėmis,

760
00:35:45,440 --> 00:35:46,750
Aš ruošiuosi daryti normalumas patikrinti.

761
00:35:46,750 --> 00:35:54,279
Jei medžių lygu lygu nuliui, yra N
Šiame medyje ar ne šiame medyje?

762
00:35:54,279 --> 00:35:55,070
Ji negali būti, tiesa?

763
00:35:55,070 --> 00:35:56,870
Jei aš esu praeityje nulis,
ten nieko nėra.

764
00:35:56,870 --> 00:35:59,230
Aš taip pat tik
aklai pasakyti return false.

765
00:35:59,230 --> 00:36:04,050
Jei man nieko, aš tikrai negaliu
rasti jokių numerį N. Taigi, ką dar galėčiau

766
00:36:04,050 --> 00:36:04,750
Patikrink Dabar?

767
00:36:04,750 --> 00:36:12,830
Aš ruošiuosi pasakyti gerai dar, jei N yra
mažiau nei nepriklausomai yra medžio mazgas

768
00:36:12,830 --> 00:36:16,300
kad aš įteikė N vertę.

769
00:36:16,300 --> 00:36:20,270
Kitaip tariant, jei skaičius aš
ieško, N, yra mažesnis nei mazgas

770
00:36:20,270 --> 00:36:21,340
kad aš žiūriu.

771
00:36:21,340 --> 00:36:23,190
Ir aš mazgas žiūriu
ne vadinamas medis,

772
00:36:23,190 --> 00:36:26,370
ir atšaukia iš ankstesniame pavyzdyje
gauti tuo verte rodyklė,

773
00:36:26,370 --> 00:36:28,310
Aš Rodyklių notacijos.

774
00:36:28,310 --> 00:36:35,960
Taigi, jei N yra mažiau nei medžio rodykle
N, noriu konceptualiai eiti į kairę.

775
00:36:35,960 --> 00:36:38,590
Kaip aš išreikšti ieško liko?

776
00:36:38,590 --> 00:36:41,560
Būti aišku, jei tai yra
tas vaizdas,

777
00:36:41,560 --> 00:36:44,612
ir aš buvo perduota, kad viršutinis
arrow kad manimi nukreipta žemyn.

778
00:36:44,612 --> 00:36:45,570
Štai mano medis žymeklis.

779
00:36:45,570 --> 00:36:48,060
Aš nukreipta į medžio šaknis.

780
00:36:48,060 --> 00:36:52,100
Ir aš ieškau tarkim, už
numeris 44, savavališkai.

781
00:36:52,100 --> 00:36:55,300
Yra 44 arba mažiau nei
didesnis nei 55 Akivaizdu?

782
00:36:55,300 --> 00:36:56,360
Taigi, tai mažiau nei.

783
00:36:56,360 --> 00:36:58,760
Ir todėl tai jei taikoma sąlyga.

784
00:36:58,760 --> 00:37:03,981
Taigi konceptualiai, ką noriu
Ieškoti kito, jei aš ieškau 44?

785
00:37:03,981 --> 00:37:04,480
Taip?

786
00:37:04,480 --> 00:37:08,310

787
00:37:08,310 --> 00:37:11,100
>> Būtent, aš noriu
ieškoti kairįjį vaiką,

788
00:37:11,100 --> 00:37:12,789
arba į kairę sub-tree šio paveikslėlyje.

789
00:37:12,789 --> 00:37:14,830
Ir iš tiesų, tegul mane per
vaizdas žemyn čia

790
00:37:14,830 --> 00:37:17,770
tik už momentą, nes
Aš negaliu subraižyti this out.

791
00:37:17,770 --> 00:37:21,150
Jei aš pradedu čia ne 55, o
Aš žinau, kad vertė 44

792
00:37:21,150 --> 00:37:23,180
Aš ieškau yra
kairysis, tai tipo

793
00:37:23,180 --> 00:37:26,010
tiek kaip ašarojimas telefono knygą
pusė arba ašarojimas medį per pusę.

794
00:37:26,010 --> 00:37:29,660
Aš jau nebeturi rūpintis
Visa tai pusė medžio.

795
00:37:29,660 --> 00:37:33,270
Ir dar, kaip bebūtų keista, kalbant iš
struktūra, tai per čia, kad dalykas

796
00:37:33,270 --> 00:37:36,682
prasideda 33, tai savaime
yra dvejetainis paieškos medis.

797
00:37:36,682 --> 00:37:39,890
Aš pasakiau žodis rekursywny anksčiau, nes
Iš tiesų, tai yra, kad duomenų struktūra

798
00:37:39,890 --> 00:37:41,707
pagal apibrėžimą yra grįžtamojo.

799
00:37:41,707 --> 00:37:44,540
Jums gali tekti medį, kad tai?
didelis, bet kiekvienas savo vaikus viena

800
00:37:44,540 --> 00:37:46,870
atstovauja medį tik šiek tiek mažesnis.

801
00:37:46,870 --> 00:37:50,910
Vietoj jo yra senelis
ar močiutė, dabar tai tiesiog mama

802
00:37:50,910 --> 00:37:54,300
or-- aš negaliu say-- ne mama
ar tėtis, kad būtų keista.

803
00:37:54,300 --> 00:37:59,000
Vietoj du vaikai ten
Būtų kaip brolis ir sese.

804
00:37:59,000 --> 00:38:01,120
Naujos kartos šeimos medį.

805
00:38:01,120 --> 00:38:02,900
Tačiau struktūriškai, tai tą pačią idėją.

806
00:38:02,900 --> 00:38:06,790
Ir it turns out Turiu funkciją
su kuriais galiu ieškoti dvejetainį paiešką

807
00:38:06,790 --> 00:38:07,290
medis.

808
00:38:07,290 --> 00:38:08,680
Jis vadinamas paieška.

809
00:38:08,680 --> 00:38:17,870
Ieškoti N medžių rodyklės kairėje
kitas, jei n yra didesnis, negu vertė

810
00:38:17,870 --> 00:38:18,870
kad aš šiuo metu.

811
00:38:18,870 --> 00:38:20,800
55 į istoriją prieš akimirką.

812
00:38:20,800 --> 00:38:23,780
Turiu funkcija vadinama
Paieška kad aš galiu tik

813
00:38:23,780 --> 00:38:29,660
perduoti N. tai ir rekursyviai paiešką
sub-tree ir tiesiog grąža

814
00:38:29,660 --> 00:38:30,620
kad ir ką atsakyti.

815
00:38:30,620 --> 00:38:33,530
Kita aš turiu šiek tiek galutinį bazinį scenarijų čia.

816
00:38:33,530 --> 00:38:35,310
>> Kas yra galutinė atveju?

817
00:38:35,310 --> 00:38:36,570
Medis yra arba niekinis.

818
00:38:36,570 --> 00:38:39,980
Vertė aš arba ieškote yra
mažiau nei ji arba didesnis, nei

819
00:38:39,980 --> 00:38:42,610
arba lygi jai.

820
00:38:42,610 --> 00:38:44,750
Ir galėčiau pasakyti lygūs
lygūs, bet logiškai tai

821
00:38:44,750 --> 00:38:46,500
lygiavertis tiesiog pasakyti dar čia.

822
00:38:46,500 --> 00:38:49,150
Taigi tiesa yra tai, kaip rasti kažką.

823
00:38:49,150 --> 00:38:51,710
Taigi, tikiuosi, tai
dar įtikinamų pavyzdžių

824
00:38:51,710 --> 00:38:54,900
nei kvailas sigma funkcija
Mes padarėme keletą paskaitų atgal,

825
00:38:54,900 --> 00:38:58,360
kur jis buvo tik kaip paprasta naudoti kilpą
suskaičiuoti visus skaičius vienoje iš

826
00:38:58,360 --> 00:39:02,390
kad N. čia su duomenų struktūros
kad pati yra rekursyviai

827
00:39:02,390 --> 00:39:07,050
apibrėžti ir rekursyviai parengtas, dabar mes
turi galimybę išreikšti save, kad

828
00:39:07,050 --> 00:39:09,780
kodu, kad pati yra grįžtamojo.

829
00:39:09,780 --> 00:39:12,580
Taigi tai yra lygiai toks pats kodas čia.

830
00:39:12,580 --> 00:39:14,400
>> Taigi, ką kitas problemas mes galime išspręsti?

831
00:39:14,400 --> 00:39:18,160
Taigi greitas žingsnis nuo
medžiai vos akimirką.

832
00:39:18,160 --> 00:39:20,130
Štai, tarkim, Vokietijos vėliava.

833
00:39:20,130 --> 00:39:22,020
Ir ten aiškiai
modelis su šiuo vėliava.

834
00:39:22,020 --> 00:39:23,811
Ir ten daug
vėliavos pasaulyje, kad

835
00:39:23,811 --> 00:39:27,560
yra taip paprasta, kaip tai kalbant
jų spalvų ir raštų.

836
00:39:27,560 --> 00:39:31,930
Bet manyti, kad šis yra saugomi kaip
GIF arba JPEG arba Bitmap, ar ping,

837
00:39:31,930 --> 00:39:34,240
bet grafinis failo formatas
su kuria jūs esate susipažinę,

838
00:39:34,240 --> 00:39:36,460
kai kurie iš jų mes
žaisti su į PSET4.

839
00:39:36,460 --> 00:39:41,550
Tai neatrodo verta saugoti
juoda pikselių, juoda pikselių, juoda pikselių,

840
00:39:41,550 --> 00:39:44,790
taškas, taškas, taškas, visa krūva
juodi pikseliai pirmą scanline,

841
00:39:44,790 --> 00:39:47,430
arba eilutė, tada visa krūva
tas pats, tada visa krūva

842
00:39:47,430 --> 00:39:49,530
iš tos pačios, ir tada
visa krūva raudonų taškų,

843
00:39:49,530 --> 00:39:53,020
raudonos taškų, raudona taškų, tada visa
krūva geltonų taškų, geltona, tiesa?

844
00:39:53,020 --> 00:39:55,050
>> Yra toks neefektyvumas čia.

845
00:39:55,050 --> 00:39:59,040
Kaip jūs intuityviai
suspausti Vokietijos vėliava

846
00:39:59,040 --> 00:40:01,320
jei ją įgyvendinant kaip failą?

847
00:40:01,320 --> 00:40:04,940
Kaip kokia informacija mes galime ne
vargintis saugoti diske tam

848
00:40:04,940 --> 00:40:08,040
sumažinti mūsų failo dydį iš, kaip
megabaitas į kilobaitai, kažkas

849
00:40:08,040 --> 00:40:09,430
mažesnis?

850
00:40:09,430 --> 00:40:13,130
Kur slypi atleidimų
Čia bus aišku?

851
00:40:13,130 --> 00:40:13,880
Ką galima padaryti?

852
00:40:13,880 --> 00:40:14,380
Taip?

853
00:40:14,380 --> 00:40:21,380

854
00:40:21,380 --> 00:40:21,970
Būtent.

855
00:40:21,970 --> 00:40:24,550
Kodėl gi ne, o ne prisiminti
kiekvieno pikselio spalva darn

856
00:40:24,550 --> 00:40:28,200
kaip jūs darote PSET4
su bitmap failo formatu,

857
00:40:28,200 --> 00:40:32,060
kodėl ne jūs tiesiog atstovauti
kairiausias skiltyje taškų, pavyzdžiui,

858
00:40:32,060 --> 00:40:35,370
juodų taškų krūva, krūva
raudonos, ir geltonos krūva,

859
00:40:35,370 --> 00:40:39,210
ir tada tiesiog kažkaip užkoduoti
idėja iš Pakartokite tai 100 kartų

860
00:40:39,210 --> 00:40:41,020
ar kartoti 1000 kartus?

861
00:40:41,020 --> 00:40:43,430
Kur 100 ar 1000 yra
tik sveikasis skaičius, todėl jūs

862
00:40:43,430 --> 00:40:47,290
gali išsisukti tik su vienu numeriu
vietoj šimtų ar tūkstančių

863
00:40:47,290 --> 00:40:48,270
Papildomų taškų.

864
00:40:48,270 --> 00:40:50,990
Ir iš tiesų, tai, kaip mes
gali suspausti Vokietijos vėliava.

865
00:40:50,990 --> 00:40:51,490
Bei

866
00:40:51,490 --> 00:40:53,470
Dabar ką apie Prancūzijos vėliava?

867
00:40:53,470 --> 00:40:58,930
Ir šiek tiek kažkokia
psichikos naudotis, su kurios vėliava

868
00:40:58,930 --> 00:41:01,040
gali būti suspausta daugiau diske?

869
00:41:01,040 --> 00:41:05,720
Vokietijos vėliava arba prancūzų
vėliava, jei mes šį požiūrį?

870
00:41:05,720 --> 00:41:08,490
Vokietijos vėliava, nes ten
daugiau horizontalus atleidimo.

871
00:41:08,490 --> 00:41:12,190
Ir dizainas, daugelis grafinis failas
formatai tiesų dirba kaip skenavimo linijas

872
00:41:12,190 --> 00:41:12,830
horizontaliai.

873
00:41:12,830 --> 00:41:14,674
Jie galėtų dirbti
vertikaliai, tiesiog žmonija

874
00:41:14,674 --> 00:41:17,090
prieš nusprendusios metų, kad mes
apskritai manau dalykų eilės

875
00:41:17,090 --> 00:41:18,880
iki eilės vietoj stulpelyje stulpelyje.

876
00:41:18,880 --> 00:41:20,820
Taigi iš tiesų, jei buvo
pažvelgti į failą

877
00:41:20,820 --> 00:41:24,670
dydis Vokietijos vėliava ir prancūzų
vėliava, tol, kol geba yra

878
00:41:24,670 --> 00:41:27,530
tas pats, to paties pločio
ir aukštis, tai vienas

879
00:41:27,530 --> 00:41:31,580
čia bus didesni, nes jus
turi pakartoti sau tris kartus.

880
00:41:31,580 --> 00:41:35,570
Turite nurodyti mėlyna, pakartokite
Būk, balta, pakartokite sau, raudona,

881
00:41:35,570 --> 00:41:36,740
pakartokite sau.

882
00:41:36,740 --> 00:41:39,000
Jūs galite ne tik eiti visi
kelią į dešinę.

883
00:41:39,000 --> 00:41:41,200
Ir kaip panaikinti, kad
išvalyti suspaudimo

884
00:41:41,200 --> 00:41:43,910
yra visur, jei jie yra
keturi rėmai iš video-- jums

885
00:41:43,910 --> 00:41:45,890
gali priminti, kad filmą
arba vaizdo įrašas yra paprastai

886
00:41:45,890 --> 00:41:47,286
kaip 29 arba 30 kadrų per sekundę.

887
00:41:47,286 --> 00:41:50,410
Tai tarsi maža Flip Book, kur jūs
tik pamatyti vaizdą, vaizdas, vaizdo, vaizdas,

888
00:41:50,410 --> 00:41:54,410
vaizdas tiesiog super greitai, todėl atrodo
ant ekrano aktoriai juda.

889
00:41:54,410 --> 00:41:57,130
Štai kamanių apie
Į viršų gėlių krūva.

890
00:41:57,130 --> 00:41:59,790
Ir nors ji gali būti natūra
sunku pamatyti iš pirmo žvilgsnio,

891
00:41:59,790 --> 00:42:04,020
vienintelis dalykas, juda
šis filmas yra bičių.

892
00:42:04,020 --> 00:42:06,880
>> Kas yra kvailas apie saugoti
vaizdo zdekompresowaniu?

893
00:42:06,880 --> 00:42:11,420
Tai tipo iš atliekų saugoti vaizdo įrašą
kaip keturias beveik identiški vaizdus,

894
00:42:11,420 --> 00:42:13,670
skiriasi tik tiek, kiek, kur bičių yra.

895
00:42:13,670 --> 00:42:16,280
Jūs galite išmesti pats
tos informacijos

896
00:42:16,280 --> 00:42:20,190
ir nepamiršti, tik, pavyzdžiui,
pirmas rėmas ir paskutinis kadras,

897
00:42:20,190 --> 00:42:22,180
pagrindiniai rėmai, jei jūs
nors girdėjote žodį

898
00:42:22,180 --> 00:42:24,337
ir tiesiog Laikyti
viduryje, kai bičių yra.

899
00:42:24,337 --> 00:42:26,170
Ir jūs neturite
saugoti visus rožinė,

900
00:42:26,170 --> 00:42:28,330
ir mėlyną, ir
žalia vertės, taip pat.

901
00:42:28,330 --> 00:42:31,200
Taigi tai yra tik pasakyti, kad
suspaudimas yra visur.

902
00:42:31,200 --> 00:42:34,900
Tai metodas, mes dažnai naudoti
arba imtis už suteiktas šių dienų.

903
00:42:34,900 --> 00:42:38,750
>> Bet kaip jūs suspausti tekstą?

904
00:42:38,750 --> 00:42:40,450
Kaip tu apie suspaudžiant tekstą?

905
00:42:40,450 --> 00:42:45,410
Na, kiekvienas iš simbolių
ASCII yra vienas baitas, arba aštuonis bitus.

906
00:42:45,410 --> 00:42:47,360
Ir tai rūšies kvailas, tiesa?

907
00:42:47,360 --> 00:42:51,160
Kadangi jūs tikriausiai tipas A
ir E ir I ir O, U daug

908
00:42:51,160 --> 00:42:55,270
dažniau nei kaip W arba Q arba Z,
priklausomai nuo to, kokia kalba

909
00:42:55,270 --> 00:42:56,610
rašote tikrai.

910
00:42:56,610 --> 00:42:59,600
Ir taip, tai kodėl mes vartojame
Aštuoni bitai kiekvienam laiške,

911
00:42:59,600 --> 00:43:02,040
įskaitant mažiausiai
lankytinos raidės, tiesa?

912
00:43:02,040 --> 00:43:05,300
Kodėl gi ne naudoti mažiau bitai
super lankytinos raidės,

913
00:43:05,300 --> 00:43:07,760
kaip E, ką galite atspėti
pirmasis Laimės rato,

914
00:43:07,760 --> 00:43:10,450
ir naudoti daugiau bitai
mažiau populiarūs raidės?

915
00:43:10,450 --> 00:43:10,950
Kodėl?

916
00:43:10,950 --> 00:43:13,130
Nes mes tik ketina
naudoti juos rečiau.

917
00:43:13,130 --> 00:43:15,838
>> Na, it turns out, kad turi
buvo bandoma pagaminti tai padaryti.

918
00:43:15,838 --> 00:43:18,630
Ir jei jūs prisimenate iš klasės
mokyklinis ar vidurinės mokyklos, Morzės kodas.

919
00:43:18,630 --> 00:43:20,400
Morzės abėcėlė turi taškus
ir brūkšneliai, kurie gali būti

920
00:43:20,400 --> 00:43:24,270
perduodama išilgai laido
garsai ar signalai kažkoks.

921
00:43:24,270 --> 00:43:25,930
Bet Morzės kodas yra super švarus.

922
00:43:25,930 --> 00:43:29,010
Tai tipo dvejetainis sistemos
kad jūs turite taškus arba brūkšnių.

923
00:43:29,010 --> 00:43:30,977
Tačiau jei matote, pavyzdžiui, du taškus.

924
00:43:30,977 --> 00:43:33,810
Arba, jei jūs manote atgal į operatoriaus
kas eina kaip beep, beep, beep,

925
00:43:33,810 --> 00:43:36,760
pyptelėjimas, pradeda šiek tiek spragtuką
, kuri perduoda signalą,

926
00:43:36,760 --> 00:43:40,360
jei jus, gavėjas gauna du
taškų, kokią žinią jau gavote?

927
00:43:40,360 --> 00:43:43,490
Visiškai savavališkai.

928
00:43:43,490 --> 00:43:44,450
>> Aš?

929
00:43:44,450 --> 00:43:45,060
Aš?

930
00:43:45,060 --> 00:43:47,500
Arba ką about-- ar man?

931
00:43:47,500 --> 00:43:49,570
Gal tai buvo tik du E teisė?

932
00:43:49,570 --> 00:43:52,480
Taigi ten ši problema
iš decodability su Morzės

933
00:43:52,480 --> 00:43:54,890
kodas, pagal kurį, jei
asmuo siunčia jums laišką

934
00:43:54,890 --> 00:43:59,510
iš tikrųjų pauzių, todėl galite rūšiuoti
pamatyti ar išgirsti tarp raidžių spragas,

935
00:43:59,510 --> 00:44:02,990
tai nepakanka tik
siųsti srautas nulių ir,

936
00:44:02,990 --> 00:44:05,610
arba taškeliai ir brūkšneliai,
nes ten dviprasmiškumas.

937
00:44:05,610 --> 00:44:08,640
E yra vienas taškas, tad jei
matyti du taškus ar išgirsti du taškus,

938
00:44:08,640 --> 00:44:11,254
gal tai du E "arba gal tai vienas I.

939
00:44:11,254 --> 00:44:13,670
Taigi, mes turime sistemą, kuri siūlo pasirinkti
šiek tiek daugiau protingas, kad ne.

940
00:44:13,670 --> 00:44:16,851
Taigi žmogus, vardu Huffman'o metų
prieš atėjo su tiksliai tai.

941
00:44:16,851 --> 00:44:18,600
Taigi mes tiesiog vyksta
imtis pirmo žvilgsnio

942
00:44:18,600 --> 00:44:20,114
tuo, kaip medžiai Priklauso tai.

943
00:44:20,114 --> 00:44:22,530
Tarkim, kad tai yra kai
kvailas pranešimą norite siųsti,

944
00:44:22,530 --> 00:44:26,342
sudaro tik A, B, C anketa D'S ir E ",
bet yra atleidimo iš darbo daug čia.

945
00:44:26,342 --> 00:44:27,550
Jis nėra skirtas būti anglų kalba.

946
00:44:27,550 --> 00:44:28,341
Tai ne šifruojamas.

947
00:44:28,341 --> 00:44:30,540
Tai tiesiog kvaila žinutė
su daug pasikartojimų.

948
00:44:30,540 --> 00:44:34,010
Taigi, jei jūs iš tikrųjų Paskaičiuoti visi
A s, B-ųjų C "D's, o E", čia

949
00:44:34,010 --> 00:44:34,890
dažnis.

950
00:44:34,890 --> 00:44:37,800
20% laiškus
A-ųjų 45% raidės

951
00:44:37,800 --> 00:44:39,660
yra E ", ir trys kiti dažniai.

952
00:44:39,660 --> 00:44:41,960
Mes skaičiuojamos ten rankiniu būdu
ir tiesiog darė matematikos.

953
00:44:41,960 --> 00:44:44,579
>> Taigi, tai Pasirodo, kad
Huffman, prieš kurį laiką,

954
00:44:44,579 --> 00:44:46,620
Supratau, kad, žinote,
kas, jei aš pradėti statyti

955
00:44:46,620 --> 00:44:51,172
medis arba miško medžių, jei norite,
taip, aš galiu padaryti taip.

956
00:44:51,172 --> 00:44:53,880
Aš ruošiuosi duoti mazgas kiekvienas
laiškų, kad aš rūpi

957
00:44:53,880 --> 00:44:55,530
ir aš ruošiuosi laikyti
viduje, kad mazgas

958
00:44:55,530 --> 00:44:58,610
dažniai kaip slankiojo kablelio
vertė, ar galima jį naudoti N, taip pat,

959
00:44:58,610 --> 00:45:00,210
bet mes tiesiog naudokite plūdę čia.

960
00:45:00,210 --> 00:45:03,100
Ir algoritmas,
jis pasiūlė, kad jūs

961
00:45:03,100 --> 00:45:07,210
pasinaudoti šia vieno mazgo mišką
medžiai, todėl itin trumpi medžiai,

962
00:45:07,210 --> 00:45:11,920
ir pradėdami jungia juos su
naujų grupių, naujos tėvai, jei bus.

963
00:45:11,920 --> 00:45:16,150
Ir jums tai padaryti, pasirinkdamas
du mažiausi dažniai vienu metu.

964
00:45:16,150 --> 00:45:18,110
Taigi aš paėmė 10% ir 10%.

965
00:45:18,110 --> 00:45:19,090
Sukurti naują mazgas.

966
00:45:19,090 --> 00:45:20,910
Ir aš vadinu naują mazgo 20%.

967
00:45:20,910 --> 00:45:22,750
>> Kuris dviejų mazgų Aš sujungti toliau?

968
00:45:22,750 --> 00:45:23,810
Tai šiek tiek dviprasmiškas.

969
00:45:23,810 --> 00:45:26,643
Taigi ten kai kampiniai atvejus
apsvarstyti, tačiau, kad viskas gana,

970
00:45:26,643 --> 00:45:29,300
Aš ruošiuosi rinktis 20% -
Aš dabar ignoruoti vaikus.

971
00:45:29,300 --> 00:45:33,640
Aš ruošiuosi pasirinkti 20% ir
15% ir parengti du naujus kraštus.

972
00:45:33,640 --> 00:45:35,624
Ir dabar, kai du mazgai
man logiškai sujungti?

973
00:45:35,624 --> 00:45:38,540
Ignoruoti visus vaikus, visi
anūkai, tiesiog pažvelgti šaknų

974
00:45:38,540 --> 00:45:39,070
dabar.

975
00:45:39,070 --> 00:45:42,220
Kuris dviejų mazgų aš kergti?

976
00:45:42,220 --> 00:45:44,530
Du punktas 0,35.

977
00:45:44,530 --> 00:45:45,890
Taigi leiskite man atkreipti du naujus kraštus.

978
00:45:45,890 --> 00:45:47,570
Ir tada aš tik turiu vieną kairę.

979
00:45:47,570 --> 00:45:48,650
Taigi čia medis.

980
00:45:48,650 --> 00:45:51,160
Ir tai buvo parengtas sąmoningai
ieškoti rūšies gana,

981
00:45:51,160 --> 00:45:55,870
bet pastebėsite, kad kraštai turi
Taip pat buvo paženklinti nulio iki vieneto.

982
00:45:55,870 --> 00:45:59,510
Taigi, visi iš kairės kraštų yra nulinės
savavališkai, bet nuosekliai.

983
00:45:59,510 --> 00:46:01,170
Visi reikiami kraštai yra tie.

984
00:46:01,170 --> 00:46:05,070
>> Ir taip, ko Hoffmanas siūloma,
jei norite atstovauti B,

985
00:46:05,070 --> 00:46:10,080
o ne atstovauja skaičių 66, kaip
ASCII kuri yra aštuoni visą bitai,

986
00:46:10,080 --> 00:46:13,360
Žinai ką, tik parduotuvėje
modelis nulis, nulis, nulis,

987
00:46:13,360 --> 00:46:17,030
nuliui, nes tai kelias
nuo mano medžio, p Huffman anketa medis,

988
00:46:17,030 --> 00:46:18,600
kad iš šaknų lapų.

989
00:46:18,600 --> 00:46:20,970
Jei norite išsaugoti
El, priešingai, ne

990
00:46:20,970 --> 00:46:26,290
siųsti aštuonis bitus, atspindintys E.
Vietoj to, siųsti ką modelio bitai?

991
00:46:26,290 --> 00:46:26,890
Vienas.

992
00:46:26,890 --> 00:46:30,410
Ir kas malonu apie tai
kad E yra populiariausias raštas,

993
00:46:30,410 --> 00:46:32,340
ir jūs, naudojant
Trumpiausias kodas.

994
00:46:32,340 --> 00:46:34,090
Kitas populiariausias
laiškas atrodo, kad jis

995
00:46:34,090 --> 00:46:37,380
buvo A. Ir taip, kiek bitų
gi jis siūlo naudoti, kad?

996
00:46:37,380 --> 00:46:38,270
Nulis, vienas.

997
00:46:38,270 --> 00:46:41,060
>> Ir todėl, kad ji įgyvendinama
kaip šio medžio, nes dabar

998
00:46:41,060 --> 00:46:43,350
leiskite numatyti ten
nėra dviprasmiškumo kaip Morzės

999
00:46:43,350 --> 00:46:46,090
kodas, nes visi iš
laiškus galite rūpi

1000
00:46:46,090 --> 00:46:48,780
yra iš šių kraštų pabaigoje.

1001
00:46:48,780 --> 00:46:50,580
Taigi, kad tik vienas
taikymas medį.

1002
00:46:50,580 --> 00:46:52,538
Tai is-- ir aš banga
mano ranka į tai, kaip jūs

1003
00:46:52,538 --> 00:46:55,570
gali įgyvendinti tai kaip C struktūrą.

1004
00:46:55,570 --> 00:46:58,260
Mes tiesiog reikia derinti
simbolis, kaip char,

1005
00:46:58,260 --> 00:46:59,910
ir, dažnių kairę ir į dešinę.

1006
00:46:59,910 --> 00:47:02,510
Bet pažvelkime į du
Galutiniai pavyzdžiai, kad jums

1007
00:47:02,510 --> 00:47:06,070
gauti pakankamai susipažinę su po
nulis Viktorina į problemą nustatyti penki.

1008
00:47:06,070 --> 00:47:09,210
>> Taigi, yra duomenų struktūros
žinomas kaip maišos lentelėje.

1009
00:47:09,210 --> 00:47:12,247
Ir maišos lentelė yra natūra
atvėsti, kad ji turi kibirų.

1010
00:47:12,247 --> 00:47:14,830
Ir Tarkime, kad keturių kibirų
čia tik keturi tarpų.

1011
00:47:14,830 --> 00:47:20,830
Štai kortų kaladė, ir čia yra
klubas, kastuvas, klubas, deimantai, klubas,

1012
00:47:20,830 --> 00:47:25,960
Deimantai, klubas, deimantai,
clubs-- todėl tai yra atsitiktinai.

1013
00:47:25,960 --> 00:47:30,330
Širdelės, hearts-- todėl aš
bucketizing visi įėjimai čia.

1014
00:47:30,330 --> 00:47:32,430
Ir A maišos lentelė poreikiai
pažvelgti į jūsų indėlį,

1015
00:47:32,430 --> 00:47:34,850
ir tada įdėti jį į tam tikrą
vieta pagal tai, ką matote.

1016
00:47:34,850 --> 00:47:35,600
Tai algoritmas.

1017
00:47:35,600 --> 00:47:37,980
Ir aš naudoju super
paprasta vaizdo algoritmas.

1018
00:47:37,980 --> 00:47:40,030
Sunkiausia dalis buvo
prisiminti ką nuotraukos buvo.

1019
00:47:40,030 --> 00:47:41,590
Ir tada ten keturis bendrus dalykus.

1020
00:47:41,590 --> 00:47:45,440
>> Dabar kaminai augo, o
yra sąmoningas dizainas dalykas čia.

1021
00:47:45,440 --> 00:47:46,540
Bet ką dar galėčiau padaryti?

1022
00:47:46,540 --> 00:47:49,080
Taigi iš tikrųjų čia turime
krūva senų mokyklos egzaminu knygų.

1023
00:47:49,080 --> 00:47:51,240
Tarkime, kad krūva
studentų pavadinimai yra čia.

1024
00:47:51,240 --> 00:47:52,570
Štai didesni maišos lentelės.

1025
00:47:52,570 --> 00:47:54,867
Vietoj keturių kaušų,
Aš, tarkim 26.

1026
00:47:54,867 --> 00:47:57,950
Ir mes nenorėjome eiti skolintis 26
dalykų iš išorės [? Annenberg?], Todėl

1027
00:47:57,950 --> 00:48:00,289
čia penkių kad atstovauti
Nuo A iki Z. Ir jei aš

1028
00:48:00,289 --> 00:48:03,580
pamatyti studentas, kurio vardas prasideda A
Aš ruošiuosi įdėti savo arba savo viktoriną ten.

1029
00:48:03,580 --> 00:48:08,850
Jei kas nors pradeda su C, ten,
A-- tikrųjų nenorėjo to daryti.

1030
00:48:08,850 --> 00:48:10,060
B eina čia.

1031
00:48:10,060 --> 00:48:13,390
Taigi aš turiu A ir B ir C. Ir
dabar čia dar studentas.

1032
00:48:13,390 --> 00:48:16,212
Bet jei tai maišos lentelė
įgyvendinamas su masyvo,

1033
00:48:16,212 --> 00:48:17,920
Aš rūšies prisukamas
šiuo metu, tiesa?

1034
00:48:17,920 --> 00:48:19,510
I rūšies reikia įdėti šį kažkur.

1035
00:48:19,510 --> 00:48:24,380
>> Taigi vienas būdas aš galiu išspręsti šią problemą yra visi
teisė, yra užimtas, B yra užimtas, C yra užimtas.

1036
00:48:24,380 --> 00:48:28,880
Aš ruošiuosi įdėti jį į D. Tad
pirma, turiu atsitiktinių tiesioginę prieigą

1037
00:48:28,880 --> 00:48:31,064
į kiekvieną studentams kibirai.

1038
00:48:31,064 --> 00:48:33,230
Bet dabar tai tipo atiteko
į kažką linijinė,

1039
00:48:33,230 --> 00:48:36,750
nes jei aš noriu ieškoti kažkam
kurio vardas prasideda A, aš patikrinti čia.

1040
00:48:36,750 --> 00:48:38,854
Bet jei tai yra ne A
studentas aš ieškote,

1041
00:48:38,854 --> 00:48:41,520
I rūšies turite pradėti tikrinti
kad kaušai, nes ką aš padariau

1042
00:48:41,520 --> 00:48:44,530
buvo tarsi tiesiškai
zondas duomenų struktūrą.

1043
00:48:44,530 --> 00:48:47,710
Kvailas būdas pasakyti tiesiog ieškoti
pirmo prieinamo atidarymo,

1044
00:48:47,710 --> 00:48:51,850
ir įdėti kaip planas B, taip sakant,
arba planas, D, šiuo atveju, vertė,

1045
00:48:51,850 --> 00:48:53,340
toje vietoje vietoj.

1046
00:48:53,340 --> 00:48:56,470
Tai tik todėl, kad jei jūs
gavo 26 vietas ir studentai

1047
00:48:56,470 --> 00:49:00,600
su vardo Q arba Z, ar kažkas panašaus
kad bent jau jūs naudojate erdvę.

1048
00:49:00,600 --> 00:49:03,140
>> Bet mes jau matėme daugiau
protingi sprendimai čia, tiesa?

1049
00:49:03,140 --> 00:49:04,870
Ką tu darytum vietoj
jei turite susidūrimo?

1050
00:49:04,870 --> 00:49:06,670
Jei du žmonės turi
pavadinimas A kas būtų

1051
00:49:06,670 --> 00:49:09,160
buvę protingesni ar daugiau
intuityvus sprendimas ne tik

1052
00:49:09,160 --> 00:49:12,840
Eksploatacijos kur D yra turėtų būti?

1053
00:49:12,840 --> 00:49:14,810
Kodėl ne aš tiesiog eiti
ne [? Annenberg?]

1054
00:49:14,810 --> 00:49:19,960
kaip malloc, kitą mazgą, jį
čia, ir tada įdėti, kad studentas čia.

1055
00:49:19,960 --> 00:49:22,120
Taigi, kad aš iš esmės turi
kai masyvą natūra,

1056
00:49:22,120 --> 00:49:25,590
arba gal ir daugiau elegantiškai kaip mes
pradeda rodyti susietą sąrašą.

1057
00:49:25,590 --> 00:49:29,520
>> Ir taip maišos lentelė yra struktūra
kad galėtų atrodyti tik kaip šis,

1058
00:49:29,520 --> 00:49:33,900
bet daugiau protingai, jūs kažką vadinama
atskiras jungimo, kuriuo maišos lentelė

1059
00:49:33,900 --> 00:49:38,340
paprasčiausiai yra matrica, kiekvienas iš
kurio sudedamosios dalys yra ne skaičius,

1060
00:49:38,340 --> 00:49:40,470
pati yra susijusi sąrašas.

1061
00:49:40,470 --> 00:49:45,080
Taigi, kad jums super greitai prieiga
sprendžiant, kur maišos savo vertę.

1062
00:49:45,080 --> 00:49:48,059
Panašiai kaip su kortelėmis, pavyzdžiui,
Aš padariau super greitus sprendimus.

1063
00:49:48,059 --> 00:49:49,600
Širdelės eina čia deimantai eina čia.

1064
00:49:49,600 --> 00:49:52,180
Tas pats čia A eina čia
D eina čia B eina čia.

1065
00:49:52,180 --> 00:49:55,740
Taigi super greitai look-up, ir jei
atsitiktų paleisti į bylos

1066
00:49:55,740 --> 00:49:59,429
kur jūs turite susidūrimai, du
žmonės su tuo pačiu pavadinimu, gerai tada

1067
00:49:59,429 --> 00:50:00,970
Jums tiesiog pradėkite susiejimas juos kartu.

1068
00:50:00,970 --> 00:50:03,900
O gal jums išlaikyti juos surūšiuoti
abėcėlės tvarka, o gal jūs neturite.

1069
00:50:03,900 --> 00:50:05,900
Bet bent jau dabar mes turime dinamiškumą.

1070
00:50:05,900 --> 00:50:10,250
Taigi, viena vertus, turime super greitai
pastovus laikas, o natūra linijinio laiko

1071
00:50:10,250 --> 00:50:14,110
dalyvauja, jei šių susijusių sąrašus
pradėsite gauti šiek tiek ilgai.

1072
00:50:14,110 --> 00:50:16,880
>> Taigi šis kvailas natūra,
prieš kelianti pokštas metų.

1073
00:50:16,880 --> 00:50:19,590
Tuo CS50 hack-a-Thon,
kai studentai patikrinti,

1074
00:50:19,590 --> 00:50:22,040
kai TF arba CA kasmet
mano, kad tai juokinga taikstytis

1075
00:50:22,040 --> 00:50:27,772
Kaip ši ženklas, kur jis tiesiog
reiškia, kad jei jūsų vardas prasideda A,

1076
00:50:27,772 --> 00:50:28,870
eiti šiuo keliu.

1077
00:50:28,870 --> 00:50:31,110
Jei prasideda jūsų vardas
su B, eikite this-- Gerai,

1078
00:50:31,110 --> 00:50:33,290
tai juokinga gal vėliau semestrą.

1079
00:50:33,290 --> 00:50:36,420
Bet yra ir kitas
būdas tai padaryti, per daug.

1080
00:50:36,420 --> 00:50:37,410
Sugrįžk, kad.

1081
00:50:37,410 --> 00:50:38,600
>> Taigi ten ši struktūra.

1082
00:50:38,600 --> 00:50:40,420
Ir tai yra mūsų paskutinis
struktūra šiandien

1083
00:50:40,420 --> 00:50:42,400
kuri yra kažkas vadinamas Trie.

1084
00:50:42,400 --> 00:50:47,140
T-R-I-E, kurioje tam tikrų priežasčių yra trumpas
už išimti, bet tai vadinama Trie.

1085
00:50:47,140 --> 00:50:51,389
Taigi Trie yra dar vienas įdomus
amalgama iš šių idėjų daug.

1086
00:50:51,389 --> 00:50:52,930
Tai medis, kurį mes matėme anksčiau.

1087
00:50:52,930 --> 00:50:54,180
Tai nėra dvejetainis paieškos medis.

1088
00:50:54,180 --> 00:50:58,410
Tai medis bet vaikų skaičių,
tačiau kiekvienas iš A TRIE vaikams

1089
00:50:58,410 --> 00:51:00,090
yra masyvas.

1090
00:51:00,090 --> 00:51:04,790
AN dydis masyvas, tarkim, 26 ar gal 27
Jei norite paremti per brūkšnelį vardai

1091
00:51:04,790 --> 00:51:06,790
arba kabutes Liaudies pavadinimus.

1092
00:51:06,790 --> 00:51:08,280
>> Ir taip, tai yra duomenų struktūra.

1093
00:51:08,280 --> 00:51:10,290
Ir jei jums atrodo iš viršaus
į apačią, pavyzdžiui, jei jums

1094
00:51:10,290 --> 00:51:13,710
ieškoti viršuje mazgas ten, M, yra
nukreipta į kairiausias dalykas ten,

1095
00:51:13,710 --> 00:51:17,665
kuris yra, tai A, X, W, E, L, L. Tai
tik duomenų struktūra, kad savavališkai

1096
00:51:17,665 --> 00:51:19,120
yra saugoti žmonių vardus.

1097
00:51:19,120 --> 00:51:25,720
Ir Maksvelo yra saugomi tik po
iš masyvo kelias masyvo masyvo.

1098
00:51:25,720 --> 00:51:30,050
Bet kas nuostabu maždaug Trie yra
kad nors susietą sąrašą ir net

1099
00:51:30,050 --> 00:51:34,520
masyvas, geriausia, ką kada nors Dotarłeś yra
linijinis laikas arba logaritminė laikas ieškote

1100
00:51:34,520 --> 00:51:35,600
nors paimtumėte.

1101
00:51:35,600 --> 00:51:40,530
Šiame duomenų struktūros TRIE, jei
mano duomenų struktūra turi vieną vardą į jį

1102
00:51:40,530 --> 00:51:43,720
ir aš ieškau Maxwell, aš
ketina jį rasti gana greitai.

1103
00:51:43,720 --> 00:51:47,910
Aš tiesiog ieškoti "M-A-X-W-E-L-L. Jeigu
ši duomenų struktūra, priešingai,

1104
00:51:47,910 --> 00:51:51,830
jei N yra milijonai, jei yra
milijonas vardai šios duomenų struktūros,

1105
00:51:51,830 --> 00:51:57,100
Maksvelo vis dar bus
aptinkamą po tik M-A-X-W-E-L-L

1106
00:51:57,100 --> 00:51:58,090
žingsniai.

1107
00:51:58,090 --> 00:52:01,276
Ir David-- D-A-V-I-D žingsniai.

1108
00:52:01,276 --> 00:52:03,400
Kitaip tariant, statant
duomenų struktūra, kad tai

1109
00:52:03,400 --> 00:52:07,240
gavo visų šių matricos, kurie visi
patys remti laisvą prieigą,

1110
00:52:07,240 --> 00:52:11,090
Galiu pradėti ieškoti up people-ųjų
vardas, naudojant laiko tai sumą

1111
00:52:11,090 --> 00:52:14,340
proporcingas ne jų skaičių
dalykų į duomenų struktūrą,

1112
00:52:14,340 --> 00:52:16,330
kaip milijoną esamos pavadinimus.

1113
00:52:16,330 --> 00:52:20,135
Suma laiko užtrunka mane rasti
M-A-X-W-E-L-L šioje duomenų struktūros yra

1114
00:52:20,135 --> 00:52:22,260
proporcingas ne su
dydis duomenų struktūros,

1115
00:52:22,260 --> 00:52:25,930
bet vardo ilgio.

1116
00:52:25,930 --> 00:52:28,440
Ir realistiškai
pavadinimai mes ieškome iki

1117
00:52:28,440 --> 00:52:29,970
niekada bus iš proto ilgai.

1118
00:52:29,970 --> 00:52:32,600
Gal kas nors turi 10 charakterį
pavadinimas, 20 simbolių pavadinimą.

1119
00:52:32,600 --> 00:52:33,900
Tai tikrai baigtinis, tiesa?

1120
00:52:33,900 --> 00:52:37,110
Yra žemėje žmogaus, kuris
turi ilgiausią galimą vardą,

1121
00:52:37,110 --> 00:52:39,920
bet pavadinimas yra pastovus
vertė ilgis, tiesa?

1122
00:52:39,920 --> 00:52:41,980
Ji neturi skirtis bet prasme.

1123
00:52:41,980 --> 00:52:45,090
Taigi, tokiu būdu, mes su
pasiekti duomenų struktūrą

1124
00:52:45,090 --> 00:52:47,800
kad yra pastovus laikas ieškoti-up.

1125
00:52:47,800 --> 00:52:50,670
Ji imasi tam tikrų veiksmų
priklausomai nuo įvesties ilgio,

1126
00:52:50,670 --> 00:52:54,250
bet ne vardo skaičių
duomenų struktūrą.

1127
00:52:54,250 --> 00:52:58,700
Taigi, jei mes dvigubai vardų skaičių
Kitais metais iš milijardo iki dviejų milijardų,

1128
00:52:58,700 --> 00:53:03,720
išvada Maksvelo ketina imtis
tą patį skaičių iš septynių žingsnių

1129
00:53:03,720 --> 00:53:04,650
jį surasti.

1130
00:53:04,650 --> 00:53:08,810
Ir taip mes, atrodo, pasiekė
Mūsų Gralis bėgančio laiko.

1131
00:53:08,810 --> 00:53:10,860
>> Taigi kelių greitų pranešimų pora.

1132
00:53:10,860 --> 00:53:11,850
Viktorina nulis artėja.

1133
00:53:11,850 --> 00:53:14,600
Daugiau apie tai nuo kurso tinklalapyje
per ateinančius porą dienų.

1134
00:53:14,600 --> 00:53:17,120
Pirmadienio lecture-- Tai šventė
čia Harvardo pirmadienį.

1135
00:53:17,120 --> 00:53:18,850
Tai ne New Haven,
todėl mes radote klasę

1136
00:53:18,850 --> 00:53:20,310
New Haven už paskaitą pirmadienį.

1137
00:53:20,310 --> 00:53:22,550
Viskas bus filmuojami
ir transliuojamas, kaip įprasta,

1138
00:53:22,550 --> 00:53:24,900
bet tegul galų šiandien
su 30 sekundžių klipą

1139
00:53:24,900 --> 00:53:26,910
vadinami "Deep Thoughts"
iki Daven Farnham, kuris

1140
00:53:26,910 --> 00:53:30,850
įkvėpė pernai šeštadienį
Night Live'S "Deep Thoughts"

1141
00:53:30,850 --> 00:53:35,700
Jack ranka, kuri
dabar turėtų prasmės.

1142
00:53:35,700 --> 00:53:38,810
>> Filmas: Ir dabar "," Deep
Mintys "pagal Daven Farnham.

1143
00:53:38,810 --> 00:53:42,100

1144
00:53:42,100 --> 00:53:42,870
Hash lentelę.

1145
00:53:42,870 --> 00:53:45,940

1146
00:53:45,940 --> 00:53:47,660
>> GARSIAKALBIS 1: Gerai, kad viskas dabar.

1147
00:53:47,660 --> 00:53:48,805
Mes jus pamatyti kitą savaitę.

1148
00:53:48,805 --> 00:53:55,380

1149
00:53:55,380 --> 00:53:56,680
>> Doug: Norėdami pamatyti kaip tai veikia.

1150
00:53:56,680 --> 00:53:58,304
Taigi leiskite pažvelgti, kad atrodo dabar.

1151
00:53:58,304 --> 00:53:59,890
Taigi čia mes turime nerūšiuotas masyvo.

1152
00:53:59,890 --> 00:54:04,860
>> IAN: Doug, galite eiti į priekį ir iš naujo paleisti
tai tik vieną sekundę, prašau.

1153
00:54:04,860 --> 00:54:08,562
Gerai, kameros valcavimo, todėl
veiksmai, kai būsite pasiruošę, Doug, gerai?

1154
00:54:08,562 --> 00:54:11,020
Doug: Gerai, tai kas mes
turime čia yra pramaišiui su masyvo.

1155
00:54:11,020 --> 00:54:13,960
Ir aš spalvos visus elementus
raudona rodo, kad ji yra, iš tikrųjų,

1156
00:54:13,960 --> 00:54:14,460
nerūšiuotus.

1157
00:54:14,460 --> 00:54:17,960
Taigi priminti, kad pirmas dalykas, kurį mes darome
yra mes rūšiuoti kairįjį pusę masyvo.

1158
00:54:17,960 --> 00:54:20,630
Tada mes rūšiuoti teisę
pusė masyvo.

1159
00:54:20,630 --> 00:54:22,830
Ir Ya-DA, J.-DA, J.-doje,
mes jas sujungti kartu.

1160
00:54:22,830 --> 00:54:24,520
Ir mes turime visiškai rūšiuotą masyvo.

1161
00:54:24,520 --> 00:54:25,360
Štai kaip sujungti rūšiuoti veikia.

1162
00:54:25,360 --> 00:54:27,109
>> IAN: Ei, Ei, Whoa,
supjaustyti, supjaustyti, supjaustyti, supjaustyti.

1163
00:54:27,109 --> 00:54:30,130
Doug, jūs galite ne tik Ya-DA, J.-doje,
Ya-doje, jūsų kelią per merge rūšiuoti.

1164
00:54:30,130 --> 00:54:31,970
>> Doug: Aš ką tik padarė.

1165
00:54:31,970 --> 00:54:32,832
Nieko tokio.

1166
00:54:32,832 --> 00:54:33,540
Mes gerai eiti.

1167
00:54:33,540 --> 00:54:34,760
Leiskite tiesiog laikyti sukti.

1168
00:54:34,760 --> 00:54:35,380
Taigi bet kokiu atveju,

1169
00:54:35,380 --> 00:54:37,800
>> IAN: Jūs turite paaiškinti
jis labiau nei tai.

1170
00:54:37,800 --> 00:54:39,999
Tai tiesiog nepakanka.

1171
00:54:39,999 --> 00:54:41,790
Doug: Ian, mes do not
reikia grįžti į vieną.

1172
00:54:41,790 --> 00:54:42,350
Nieko tokio.

1173
00:54:42,350 --> 00:54:45,690
Taigi bet kokiu atveju, jei mes ir toliau su merge--
Ian, mes vidury filmavimo.

1174
00:54:45,690 --> 00:54:46,612
>> IAN: aš žinau.

1175
00:54:46,612 --> 00:54:49,320
Ir mes galime ne tik Ya-DA, J.-doje,
Ya-doje, per visą procesą.

1176
00:54:49,320 --> 00:54:52,200
Jūs turite paaiškinti, kaip
Abi šalys gauti susijungė kartu.

1177
00:54:52,200 --> 00:54:53,570
>> Doug: Bet mes jau ve
paaiškino, kaip du sides--

1178
00:54:53,570 --> 00:54:55,321
>> IAN: Jūs ką tik parodė,
juos šiek suliejimo masyvo.

1179
00:54:55,321 --> 00:54:56,486
Doug: Jie žino procesą.

1180
00:54:56,486 --> 00:54:57,172
Jie gerai.

1181
00:54:57,172 --> 00:54:58,380
Mes dingo per jį dešimt kartų.

1182
00:54:58,380 --> 00:55:00,330
>> IAN: Jūs tiesiog praleisti tiesiai virš jo.

1183
00:55:00,330 --> 00:55:03,360
Mes ketiname grįžti į vieną, jums
tu negali Ya-DA, J.-da per jį.

1184
00:55:03,360 --> 00:55:05,480
Gerai, atgal į vieną.

1185
00:55:05,480 --> 00:55:07,833
>> Doug: turiu grįžti
per visus skaidres?

1186
00:55:07,833 --> 00:55:08,332
Mano Dievas.

1187
00:55:08,332 --> 00:55:11,008

1188
00:55:11,008 --> 00:55:13,004
Tai kaip šeštą kartą, Ian.

1189
00:55:13,004 --> 00:55:13,940
Nieko tokio.

1190
00:55:13,940 --> 00:55:15,200
>> IAN: Visos dešinę.

1191
00:55:15,200 --> 00:55:16,590
Jūs pasiruošę?

1192
00:55:16,590 --> 00:55:17,400
Didysis.

1193
00:55:17,400 --> 00:55:18,950
Veiksmas.