>> GARSIAKALBIS 1: Gerai, taigi tai CS50 Tai iš penkių savaitės pabaigoje.
Ir prisiminti, kad paskutinį kartą mes pradėjo ieškoti mėgėjas duomenis
struktūras, kurios pradėjo spręsti problemos, kad pradėjo diegti
naujų problemų, bet į šį klavišą buvo sriegimo rūšiuoti, kad mes
pradėjo daryti iš mazgo į mazgą.
Taigi, tai, žinoma, yra atskirai susijusi sąrašas.
Ir atskirai susiję, Aš turiu galvoje, ten tik vienas
perverkite tarp kiekvienos iš šių mazgų.
Pasirodo, tai galite padaryti mėgėjas tokie dalykai kaip dvigubai, susijusių sąrašus
kuriuo turite rodyklę vyksta abiem kryptimis, kurios
gali padėti su kai efektyvumą.
Bet tai išsprendė problemą?
Kas problema tai padarė išspręsti?
Kodėl mums rūpi pirmadienį?
Kodėl teoriškai, ar mes rūpinamės pirmadienį?
Ką tai daro?
>> Auditorija: Mes galime dinamiškai keisti ją.
>> GARSIAKALBIS 1: Gerai, kad mes galime dinamiškai keisti ją.
Well done jus abu.
Taigi galite dinamiškai keisti šį duomenų struktūra, o masyvo,
Prisiminkite, jūs turite žinoti šiek priori, kiek vietos norite
ir, jei reikia šiek tiek daugiau Erdvė, esate rūšies nesiseka.
Jūs turite sukurti visiškai naują masyvo.
Jūs turite perkelti visus savo duomenys iš vieno į kitą,
galiausiai nemokamai seną masyvo jei galite, ir tada tęsti.
Kuris tiesiog jaučiasi labai brangus ir labai neefektyvus, ir iš tiesų jis gali būti.
Bet tai dar ne viskas gerai.
Mes mokame kainą, kas buvo vienas iš daugiau akivaizdžių kainas mes
mokėti naudojant susietą sąrašą?
>> Auditorija: Mes turime naudoti Dvigubas erdvę kiekvienai iš jų.
GARSIAKALBIS 1: Taip, taip, mes turime mažiausiai du kartus, kaip daug vietos.
Tiesą sakant, aš supratau, tai paveikslėlio net šiek tiek klaidinantis,
nes ant CS50 IDE šiuolaikinio daug Kompiuteriai, rodyklė arba adresas
iš tiesų nėra keturių baitų.
Tai labai dažnai šių dienų aštuoni baitai, kurie
reiškia dugną dauguma stačiakampiai ten tikrovės
yra rūšies dvigubai dideli, kaip ką aš sudarytas,
o tai reiškia, kad jūs naudojate tris kartus daug vietos, kaip mes galime turėti kitaip.
Dabar tuo pačiu metu, mes vis dar kalbame baitų, tiesa?
Mes nebūtinai kalbame megabaitų ar gigabaitų,
nebent šių duomenų struktūros gauti dideli.
>> Ir taip šiandien mes pradedame svarstyti kaip mes galime ištirti duomenis
efektyviau, jei į Tai duomenys plečiasi.
Bet pabandykime canonicalize operacijos pirmieji
kad jūs galite padaryti dėl šių rūšių duomenų struktūras.
Taigi kažkas panašaus susijęs Sąrašas paprastai palaiko
operacijos patinka ištrinti, įterpti, ir ieškoti.
Ir ką aš turiu galvoje, kad?
Tai tiesiog reiškia, kad dažniausiai, jei žmonės naudoja susietą sąrašą
jie ar kas nors kitas įdiegė funkcijas, pavyzdžiui, trinti, įterpti,
ir paieškos, todėl jūs galite iš tikrųjų ką nors padaryti
naudinga su duomenų struktūra.
Taigi leiskite priimti greitai pažvelgti tuo, kaip mes galime įgyvendinti
kai už susietą sąrašą kodas taip.
>> Taigi tai yra tik keletas, C kodas, net ne visa programa
kad aš tikrai greitai plakta.
Tai ne internete platinimo kodas, nes ji nebus iš tikrųjų paleisti.
Tačiau pastebėti Aš ką tik su pastaba sakė,
dot dot dot, kažkas ten, dot dot dot, kažką ten.
Ir tegul tik pažvelgti ką sultingas dalys yra.
Taigi on-line trijų, priminti, kad tai dabar
Mes pasiūlėme skelbiantis mazgas paskutinį laikas, vienas iš tų stačiakampių objektus.
Jis turi int, kad mes vadiname N, bet mes galime ją vadina nieko,
ir tada konstrukto mazgas žvaigždė vadinama šalia.
Ir tiesiog, kad būtų aišku, kad antrasis linija, on-line šešių, kas tai yra?
Ką jis daro už mus?
Nes ji tikrai atrodo daugiau paslaptingas nei mūsų įprasta kintamųjų.
>> Auditorija: Tai leidžia pereiti vieną.
>> GARSIAKALBIS 1: Ji daro tai perkelti daugiau nei vienas.
Ir, kad būtų tikslesni, jis bus išsaugoti adresą
mazgas, kad reiškia būti semantiškai šalia jo, tiesa?
Taigi jis nesiruošia nebūtinai judėti nieko.
Tai tiesiog ketiname laikyti vertę, kuri yra
bus adresas kai kurių kitų mazgas,
ir tai, kodėl mes sakė konstrukto mazgas žvaigždė, žvaigždė, reiškiantis
rodyklė ar adresą.
Gerai, kad dabar, jei manome, kad turime Šio N prieinama mums, ir tegul
manyti, kad kažkas turi įdėta visa krūva skaičių
į susietą sąrašą.
Ir tai susiję sąrašas atkreipė dėmesį į kai kurių taško
kintamasis vadinamas sąrašas, kurį praėjo čia, kaip parametras,
kaip man eiti apie linija 14 įgyvendinant paiešką?
Kitaip tariant, jei aš įgyvendinant funkcija, kurios tikslas gyvenime
yra imtis int ir tada pradžioje susietą sąrašą
kad yra rodyklė į susietą sąrašo.
Kaip pirmą kartą, kas aš manau Dovydą buvo mūsų savanoris pirmadienį,
jis buvo nukreipta į visa susijusi sąrašas
tai kaip nors mes artimųjų Dovydas, kaip mūsų argumentas čia.
Kaip mes eiti apie važiuojantiems šį sąrašą?
Na, it turns out, kad nors patarimų yra gana nauja, dabar pas mus,
mes galime tai padaryti gana tiesmukai.
>> Aš ruošiuosi eiti į priekį ir paskelbti laikiną kintamąjį, kad
pagal susitarimą yra tik ketina būti vadinamas žymeklis, arba PTR,
bet jūs galite jį vadiname viską, ką nori.
Ir aš ruošiuosi inicijuoti , kad ji iš sąrašo pradžioje.
Taigi galite rūšies galvoti apie tai, kaip man mokytoja kitą dieną,
rūšies nukreipta į ką nors tarp mūsų žmonių, kaip savanorius.
Taigi, aš laikiną kintamąjį, kad yra tik nukreipta į tą patį,
kad mūsų atsitiktinai pavadintas savanoris Dovydas buvo nurodydamas.
Dabar, kai žymeklis yra NOT NULL, nes susigrąžinimas
kad niekinis yra keletas specialios Sentinel vertė atriboja į sąrašo pabaigą,
Taigi, nors aš nesu nukreipta ne Pirmame kaip mūsų paskutinio savanorio
buvo eikime į priekį ir atlikite šiuos veiksmus.
Jei pointer-- ir dabar aš tipo nori daryti tai, ką mes padarėme su studento
structure-- jei žymeklis dot Kitas equals-- o, jei žymeklis taškas N yra lygus
lygus kintamasis N, The argumentas, kad buvo priimtas,
tada aš noriu eiti į priekį ir pasakyti grąžinti tiesa.
Aš rasiu numeris N viduje vienas iš savo susietą sąrašą mazgų.
Bet dot nebėra veikia šiame kontekste,
nes žymeklis, PTR, yra Iš tiesų rodyklė, adresą,
mes iš tikrųjų gali nuostabiai naudoti pagaliau yra sintaksės gabalas
kad markių natūra intuityvus jausmas ir iš tikrųjų
čia naudoti rodyklę, o tai reiškia pereiti nuo kad adresas sveikojo skaičiaus ten.
Taigi, tai labai panašus į dvasia dot operatoriaus,
bet todėl, žymeklis yra ne rodyklė o ne pats tikrasis konstrukto,
mes tiesiog naudokite rodyklę.
>> Taigi, jei dabartinė mazgas, kad Aš, laikinas kintamasis, esu nukreipta į
Netiksli N, ką noriu daryti?
Na, su mano savanoriais kad mes turėjo čia kitą dieną,
jei mano pirmasis žmogaus nėra vienas aš nori, o gal antras žmogus nėra
vienas aš noriu, o trečiasis, aš reikia išlaikyti fiziškai juda.
Kaip, kaip man žingsnis per sąrašą?
Kai mes turėjome masyvą, jums tiesiog patiko I plius plius.
Bet šiuo atveju, pakanka padaryti žymeklį, gauna, žymeklis, šalia.
Kitaip tariant, kitą laukas yra kaip visi liko rankose
kad mūsų žmogaus savanoriai pirmadienį buvo naudojant atkreipti ne kitu mazgu.
Tai buvo kito jų kaimynai.
>> Taigi, jei aš noriu žingsnis per šiame sąraše, Aš negaliu tiesiog padaryti I plius plius nebėra,
Aš vietoj turiu pasakyti Aš, žymeklis, vyksta
prilygti ką kitą laukas yra, Kitas laukas, kitas laukas yra,
Žemiau visus tuos, kurie liko rankose kad mes turėjome scenoje nukreipta
kai vėlesnių vertybes.
Ir jei aš gauti per kad visa iteracijos,
Ir pagaliau, aš paspauskite null neturi rasti N dar, aš tiesiog grįžti klaidinga.
Taigi dar kartą, visi, kad mes darome čia kaip už paveikslėlyje metu senumo,
pradeda nurodydamas ne pradedant iš sąrašo, matyt.
Ir tada aš patikrinti, yra vertė Aš ieškau lygus devynių?
Jei taip, aš grąžina true, ir aš padaryti.
Jei ne, aš atnaujinti savo ranką, AKA žymeklis, atkreipti
Kitame strėlės vietą, ir Tada kitą strėlės vietą,
ir kitą.
Aš tiesiog pėsčiomis per šio masyvo.
>> Taigi dar kartą, who cares?
Kaip kas tai yra viena sudedamoji dalis?
Na, priminti, kad mes pristatėme iš kamino sąvoka, kuri
yra abstraktus duomenų tipas, kiek tai ne C dalykas, tai ne CS50 dalykas,
tai abstrakti idėja, ši idėja krovimas dalykų vienas ant kito
kurios gali būti įgyvendintos kekių skirtingais būdais.
Ir vienas iš būdų mes pasiūlėme buvo su masyvas, arba susietą sąrašą.
Ir paaiškėja, kad kanoniškai A kamino palaiko bent dvi operacijas.
Ir Buzz žodžiai stumti, kad stumti kažką ant kamino,
kaip naują plokštelę į valgykla, ar pop,
o tai reiškia, kad pašalinti viršutinis dėklas nuo valgomojo kamino
salė, o po to gal kai Kitos operacijos, taip pat.
Taigi, kaip gali mes apibrėžti struktūrą kad mes dabar skambina kamino?
>> Na, mes turime visi reikiami sintaksė mūsų žinioje C sakau,
man tipo apibrėžimą viduje iš kamino konstrukto,
Aš ruošiuosi pasakyti yra masyvas, Kurių visa krūva skaičių ir tada dydis.
Taigi, kitaip tariant, jei aš noriu įgyvendinti tai kodas,
leiskite man eiti ir tiesiog rūšies atkreipti, kas tai yra suprantama.
Taigi, tai sako, duok mane struktūra, kuri gavo masyvą,
ir aš nežinau, ką talpa, tai, matyt, kai pastovus, kad aš
apibrėžta kitur, ir tai gerai.
Bet manau, kad tai tik viena, dviejų, trijų, keturių, penkių.
Taigi talpa yra 5.
Tai viduje elementas mano struktūra bus vadinamas numerius.
Ir tada man reikia vieną kitas kintamasis, matyt,
vadinamas dydis, kad iš pradžių aš ruošiuosi numatyti, yra inicializuoti iki nulio.
Jei yra nieko kamino, dydis yra lygus nuliui,
ir tai šiukšlių vertybes skaičiais.
Aš neįsivaizduoju, kas yra pakuotėje yra tik dar.
>> Taigi, jei aš noriu stumti kažkas ant kamino,
tarkime, aš vadinu funkcija stumti, ir Sakau stumti 50, kaip numeris 50,
Kur norėtumėte pasiūlyti Aš ją nupieškite šiame masyve?
Yra penkių skirtingų galimų atsakymų.
Kur tu nori stumti skaičių 50?
Jei tikslas čia, vėlgi, vadiname funkcija stumti, pereiti į argumentą
50, kur man jį?
Penki įmanomą 20% tikimybė, atspėti teisingai.
Taip?
>> Auditorija: Toli dešinėje.
>> GARSIAKALBIS 1: Toli dešinėje.
Dabar yra 25% tikimybė, atspėti teisingai.
Taigi, kad iš tiesų būtų gerai.
Pagal susitarimą, aš pasakyti masyvą, mes paprastai prasideda kairėje,
bet mes tikrai galėtų pradėti dešinėje.
Taigi spoileris čia būtų aš tikriausiai ketina parengti jį kairėje,
Tiesiog kaip normalus masyvo kur Aš pradėti vyksta kairės į dešinę.
Bet jei jūs galite apversti aritmetinis, gerai.
Tai tiesiog nėra tradicinis.
Gerai, man reikia padaryti vieną daugiau pokytis nors.
Dabar, kad aš stumdosi kažką ant kamino, o kas toliau?
>> Gerai, aš turiu prieaugio dydį.
Taigi leiskite man eiti į priekį ir tik atnaujina, kuris buvo nulis.
Ir vietoj dabar aš ruošiuosi įdėti į vertės vieną.
Ir dabar manau, aš stumti kitą numeris ant kamino, kaip ir 51.
Na, aš turiu padaryti vienas pokytis, kuris yra iki dydžio du.
Ir tada manau, aš stumti dar vieną numeris ant kaip 61 kaminą,
dabar man reikia atnaujinti dydį dar vienas laiką ir gauti vertę 3 AS dydžio.
O dabar tarkime aš vadinu pasipriešinimo.
Dabar pop, pagal susitarimą, nesiima argumentas.
Su rietuvę, visa taškas dėklas metafora
yra ta, kad jūs neturite savo nuožiūra eiti gauti dėklas, viskas, ką galite padaryti
yra pop viršutinis vienas nuo kamino, tik todėl.
Štai, ką šis duomenų struktūra daro.
>> Taigi, šia logika, jeigu aš sako pop, kas ateina ne?
Taigi 61.
Taigi, kas iš tiesų yra kompiuteris ketina daryti atmintyje?
Ką mano kodas daryti?
Ką siūlytumėte mes pakeisti ekrane?
Ką reikėtų keisti?
Atsiprašome?
Taigi, mes atsikratyti 61.
Taigi, aš tikrai gali tai padaryti.
Ir aš galiu atsikratyti 61.
Ir kas tada kita Pakeisti turi įvykti?
Dydis tikriausiai turi grįžti į dvi dalis.
Ir taip, kad viskas gerai.
Bet palauk, dydį prieš momentas buvo trys.
Tegul tik padaryti greitai normalumas patikrinti.
Kaip mes žinome, kad norėjo atsikratyti 61?
Kadangi mes Popping.
Ir taip, aš turiu šį antrąjį objekto dydį.
>> Palaukit, aš galvoju grįžti į dvi savaitės
kai mes pradėjome kalbėti apie masyvai, jei tai buvo vieta nulis,
tai buvo vieta viena, tai buvo vieta du, tai yra vietą trijų, keturių,
atrodo, kad santykiai tarp dydis
ir elementas, kad aš noriu pašalinti iš masyvo, atrodo, tiesiog, ką?
Dydis atėmus vieną.
Ir taip tai kaip, kaip žmogui Mes žinome 61 ateina pirmiausia.
Kaip manimi kompiuteris ketinate žinoti?
Kai jūsų kodas, kur jūs tikriausiai noriu padaryti dydis minuso vieną,
taip, trijų minus vienas yra du, ir kad reiškia, kad mes norime atsikratyti 61.
Ir tada mes iš tiesų gali atnaujinti PK tokio dydžio dydis dabar
eina nuo trijų iki tik du.
Ir tiesiog būti pedantiškas, aš ruošiuosi siūlyti, kad aš padariau, tiesa?
Jūs intuityviai pasiūlė teisingai turėčiau atsikratyti 61.
Bet neturite I rūšies rūšiuoti Dotarłeś atsikratyti 61?
Aš pamiršau efektyviai kad ji iš tikrųjų yra.
Ir prisiminkite PSET4, jei jūs skaitėte straipsnis apie ekspertizės, PDF
kad mes turėjome vaikinai skaityti, ar jūs skaityti šią savaitę PSET4.
Prisiminkite, kad iš tikrųjų tai yra Priklauso Visa idėja kompiuterių ekspertizės.
Ką kompiuteris paprastai daro, yra jis tiesiog pamiršta, kur kažkas yra,
tačiau ji neturi eiti ir kaip bandyti subraižyti jį arba išjungimas
tie antgaliai su nulių ir ar kai kurių kitų atsitiktinių modelis
Nebent jūs patys tai daryti sąmoningai.
Taigi jūsų intuicija Gerai, tegul atsikratyti 61.
Bet iš tikrųjų, mes neturime nerimauti.
Mes tiesiog reikia pamiršti, kad jis ten keičiant mūsų dydį.
>> Dabar yra su šiuo kamino problema.
Jei aš nuolat stumia dalykus ant kamino, kas
Akivaizdu nutiks vos per kelias akimirkas metu?
Mes ketiname paleisti iš kosmoso.
Ir ką mes galime padaryti?
Mes rūšies prisukamas.
Šis įgyvendinimas neleidžia mums dydį masyvo, nes naudojant
Ši sintaksė, jei jums prisiminkite du per savaitę,
kai jūs paskelbė iš masyvo dydis,
mes nematėme mechanizmą dar kur galite pakeisti masyvo dydį.
Ir iš tiesų, C neturi tokios funkcijos.
Jei sakai, kad man penkis Nths, jiems skambinti numeriai,
kad viskas, jūs ketinate gauti.
Taigi mes dabar kaip ir pirmadienį, turi gebėjimas išreikšti tirpalą
nors mes tiesiog reikia keisti mūsų kamino apibrėžimas
ne būti šiek tiek sunku koduotos masyvas, bet tik saugoti adresą.
>> Dabar, kodėl taip yra?
Dabar mes tiesiog turi būti patogu faktas, kad kai mano programa veikia,
Aš turbūt ketiname turi paprašyti žmogaus,
kiek numeriai norite saugoti?
Taigi įėjimo turi ateiti iš kažkur.
Bet kai žinau, kad numerį, tada aš galiu tik
panaudoti tai, ką veikti, parašęs man atminties riekė?
Galiu naudoti malloc.
Ir galiu pasakyti, bet kokį skaičių baitų noriu atgal už šias Nths.
Ir viskas, ką turiu laikyti skaičiais kintamasis čia viduje šio struct
turėtų būti, ką?
Kas iš tikrųjų eina į numeriai pagal šį scenarijų?
Taip, rodyklė į pirmąjį baitas tos atminties riekė,
arba, konkrečiau, adresas iš pirmojo iš šių bitais.
Nesvarbu, jei tai vienas byte arba milijardas baitų,
Aš tiesiog reikia rūpintis pirmas.
Nes tai, kas malloc garantijos ir Mano operacinė sistema garantuoja,
yra tai, kad atminties I gabalas gauti, tai bus greta.
Yra nesiruošia būti tarpų.
Taigi, jei aš paprašė 50 baitų arba 1000 baitų,
jie visi bus atgal atgal į nugarą.
Ir taip ilgai, kaip aš atsimenu, kaip didelis, kaip kiek aš paklausiau, man reikia žinoti
pirmas toks adresas.
>> Taigi dabar mes turime kode galimybes.
Nors ji ketina imtis mumis daugiau laiko rašyti tai padaryti,
dabar mes galime perskirstyti tą atmintį tiesiog laikyti kitą adresą čia
jei norime didesnis ar net mažesnis riekė atmintį.
Taigi čia į kompromisą.
Dabar mes gauname dinamiškumą.
Mes vis dar turime contiguousness aš teigdamas.
Kadangi malloc duos mums przyległa riekė atmintį.
Bet tai ketina būti skausmo už mus kaklo, programuotojas,
kad iš tikrųjų kodą viršų.
Tai tiesiog darbas.
Mes turime kodą panašus į tai, ką buvau beldžiasi iš vos prieš akimirką.
Labai vykdytinas, tačiau ji priduria, sudėtingumą.
Ir taip kūrėjas laikas, programuotojas laikas yra dar vienas šaltinis
kad mes gali tekti praleisti šiek tiek laiko gauti naujų funkcijų.
Ir tada, žinoma, yra eilė.
Mes neisiu į tai vienas iš daug detalių.
Bet tai labai panašus į dvasią.
Galėčiau įgyvendinti eilę ir jos atitinkami veiksmai,
Įtraukti į eilę arba dequeue, kaip pridėti arba pašalinti, tai tik mėgėjas būdas pasakyti tai,
Įtraukti į eilę arba dequeue, kaip nurodyta toliau.
Aš galiu tik pats sau konstrukto kad vėl turi numerį anketa masyvą,
kad vėl turi dydį,, bet kodėl aš dabar reikia
sekti iš eilės priekyje?
Man nereikėjo žinoti mano kamino priekyje.
Na, jei aš vėl dėl queue-- tegul tiesiog sunku
kodą ją kaip turintys kaip penkių sveikieji čia potencialiai.
Taigi tai yra nulis, vienas, du, tris, keturis.
Tai bus renkamus numerius dar kartą.
Ir tai bus vadinamas dydis.
>> Kodėl tai nėra pakankamas turėti tik dydį?
Na, tegul stumti tuos pačius numerius.
Taigi aš pushed-- Aš enqueued arba stumiama.
Dabar aš į eilę 50, ir tada 51, ir tada 61, ir dot dot dot.
Taigi, kad į eilę.
Aš enqueued 50, tada 51, tada 61.
Ir tai atrodo identiški prie kamino iki šiol,
išskyrus I do reikia padaryti vieną pakeitimą.
Man reikia atnaujinti šį dydį, todėl aš einu nuo nulio iki vieno iki dviejų iki trijų dabar.
Kaip man dequeue?
Kas atsitinka su dequeue?
Kas turėtų nukristi šį sąrašą pirmas jei tai būtų ne Apple Store linija?
Taigi 50.
Taigi tai tipo sunkiau šį kartą.
Kadangi paskutinį kartą tai buvo super lengva tiesiog padaryti dydis minuso vieną,
Gaunu mano masyvo pabaigos efektyviai kur šie skaičiai yra, jis pašalina 61.
Bet aš nenoriu pašalinti 61.
Noriu pasinaudoti 50, kuris ten buvo ne 5:00
išsirikiuoti už Naujas iPhone "ar" Papuošalą.
Ir taip atsikratyti 50, aš galite ne tik tai padaryti, tiesa?
Galiu užbraukti 50.
Bet mes tiesiog sakėme neturi būti taip analinio
kaip subraižyti iš arba slėpti duomenis.
Mes galime tiesiog pamiršti, kur ji yra.
>> Bet jei aš pakeisti mano dydis dabar du, tai pakanka informacijos
žinoti, kas vyksta mano eilėje?
Ne visai.
Kaip mano dydis yra du, o kur veikia eilė pradėti,
ypač jei aš vis dar turiu tie patys numeriai atmintyje.
50, 51, 61.
Taigi man reikia atsiminti dabar, kai priekinė yra.
Ir taip, aš pasiūliau iki ten, mes ką tik pavadino
N-tojo priekyje, kurio pradinė vertė turėjo ką?
Nulis, tik sąrašo pradžia.
Bet dabar be to, mažėjančio dydis, mes tiesiog prieaugio priekyje.
Dabar čia jau kita problema.
Taigi, kai aš nuolat vyksta.
Tarkim tai yra skaičius pavyzdžiui, 121, 124, ir tada, Dammit,
Aš iš kosmoso.
Bet palauk, aš nesu.
Taigi šiuo metu į istoriją, manyti, kad dydis yra vienas, du,
trijų, keturių, todėl manyti, kad dydis yra keturių, priekinis yra vienas,
taip, 51 yra priekyje.
Noriu įdėti kitą numerį čia bet, Dammit, aš iš vietos.
Bet aš tikrai ne, tiesa?
Kur galėčiau įdėti kai pridėtinė vertė, kaip ir 171?
Taip, galėčiau tiesiog rūšies grįžti ten, tiesa?
Ir tada užbraukti 50 arba tiesiog perrašyti jį su 171.
Ir jei jums įdomu, kodėl Mūsų numeriai gavo tiek atsitiktinai,
jie yra paprastai suprantamas kompiuterį Mokslas kursai Harvarde po CS50.
Bet tai buvo geras optimizavimas, nes dabar aš ne eikvoti vietos.
Aš vis dar turiu prisiminti kaip didelis šis dalykas yra bendras.
Tai penkių iš viso.
Nes aš nenoriu pradėti perrašymui 51.
Taigi, dabar aš vis dar esu iš vietos, taip, ta pati problema, kaip ir anksčiau.
Bet jūs galite pamatyti, kaip dabar Jūsų kodas, tikriausiai
turi parašyti šiek tiek daugiau sudėtingumas, kad tai įvyktų.
Ir iš tiesų, kas operatorius C tikriausiai leidžia
magiškai šio tikslo, judėjimas ratu?
Taip modulį operatorius, procentas ženklas.
Taigi, kas tipo kietas apie eilę, nors mes nuolat piešimo masyvai
nes šie kaip tiesiomis linijomis, jei jums rūšies galvoti apie tai, kaip kreivumą
aplink, ratu, tada tiesiog intuityviai tai rūšies darbų psichiškai
Manau, šiek tiek daugiau švariai.
Jūs vis dar turi įgyvendinti kad psichikos modelis kodą.
Taigi ne tai, kad sunku, galiausiai, įgyvendinti,
bet mes vis dar prarasti size-- tiksliau, gebėjimas keisti, nebent mes tai darome.
>> Mes turime atsikratyti masyvo, mes pakeisti jį su vienu rodyklė,
ir tada kažkur mano kodas, aš turiu Pokalbio ką veikti, kad iš tikrųjų sukurti
masyvas vadinamas numeriai?
Malloc ar kitu panašiu funkcija, tiksliai.
Bet kokie kaminai ar eilėse klausimai.
Taip?
Geras klausimas.
Kas modulį jūs naudojate čia.
Taigi apskritai, kai naudojate Modeliavimas, jums būtų tai padaryti
Su dydis Visa duomenų struktūra.
Taigi kažkas panašaus penkių ar talpos, jei tai pastovus, tikriausiai dalyvauja.
Bet tik tai modulo penkių tikriausiai nepakanka,
nes mes turime žinoti tai mes apvyniokite aplink čia arba čia arba čia.
Taigi jūs tikriausiai taip pat ketinate norite įtraukti
iš daikto dydis, arba priekinis kintamasis, taip pat.
Taigi, tai tik tai gana paprasta aritmetika išraiška,
bet modulį būtų pagrindinis ingredientas.
>> Taigi trumpas filmas, jei bus.
Animacija, kad kai kurie žmonės kitame universitete
kartu sudėjus, kad mes pritaikyti šią diskusiją.
Tai reiškia, Džekas mokymosi faktai apie eilių ir statistika.
>> Filmas: Kažkada, ten buvo vaikinas pavadino Džekas.
Kai jis atėjo į priėmimo draugų, Džekas neturėjo įgūdis.
Taigi Džekas ėjo pasikalbėti su Populiariausias vaikinas jis žinojo.
Jis nuėjo į Lou ir paklausė: Ką man daryti?
Lu pamatė, kad jo draugas buvo tikrai nelaimę.
Na, jis pradėjo, tiesiog atrodo kaip jūs apsirengęs.
Jūs neturite jokių drabužių su skirtingą išvaizdą?
Taip, sakė Džekas.
Aš tikrai daryti.
Ateik į mano namus ir Aš jums parodysiu jas jums.
Taigi jie išvyko į Džekas.
Ir Džekas parodė Lou langelį kur jis laikė visus savo marškinėlius,
ir jo kelnės ir jo kojines.
Lu sako, matau, jūs turite Visi drabužius į krūvą.
Kodėl ne jūs dėvėti kai Kiti kartą kurį laiką?
>> Džekas sakė, gerai, kai aš pašalinti drabužius ir kojines,
Aš nuplaukite juos ir padėkite juos į lauką.
Tada ateina kitas rytą ir iki aš apynių.
Aš einu į lauką ir gauti Mano drabužius išjungti viršuje.
Lou greitai suprato, Su Jack problema.
Jis nuolat drabužiai, kompaktinių diskų, ir knygų krūvos.
Kai jis pasiekė ką skaityti ar nešioti,
jam reikia pasirinkti aukščiausios knygą ar apatinius.
Tada, kai jis buvo padaryta, jis būtų įdėti ją atgal.
Atgal būtų eiti, ant kamino.
Aš žinau, kad tirpalas, sakė pergalingas garsiai.
Jums reikia išmokti pradėti naudoti eilę.
Lou paėmė Džekas drabužius ir pakabinti juos į spintą.
Ir kada jis ištuštinti dėžutė, jis tiesiog blaškoma ją.
>> Tada jis tarė: "Dabar Jack pabaigoje dieną, įdėti savo drabužius kairėje
kai jūs įtraukėte juos šalin.
Tada rytoj ryte, kai jūs matyti saulės, gauti savo drabužius
dešinėje, nuo linijos pabaigoje.
Ar nematai? sakė Lu.
Tai bus taip malonu.
Jūs dėvėti viską vieną kartą Prieš dėvėti ką nors du kartus.
Ir su viskuo eilėse jo spinta ir lentynos,
Džekas pradėjau jausti visai tikras save.
Visi dėka Lou ir Jo nuostabius eilė.
GARSIAKALBIS 1: Gerai, tai žavinga.
Taigi, kas buvo iš tikrųjų vyksta apie po gaubtu dabar?
Kad mes turime patarimų, kad mes turime malloc,
kad mes turime galimybę sukurti gabaliukus atminties sau
dinamiškai.
Taigi tai yra paveikslėlyje prabėgomis tik kitą dieną.
Mes tikrai ne gyventi ant jo, bet šis vaizdas
vyksta jau po už savaites dangtis dabar.
Ir taip tai yra, tiesiog stačiakampis, kad mes išdarinėtos,
kompiuterio atmintyje.
O gal jūsų kompiuteryje, arba CS50 ID turi atmintį arba RAM GIGABYTE
arba du gigabaitai ar keturi.
Jis tikrai ne klausimas.
Jūsų operacinė sistema "Windows" arba "Mac OS ar Linux
iš esmės leidžia savo programą manyti, kad ji turi prieigą
į visas kompiuterio atmintis,
nors jums gali būti rodomi daug programų vienu metu.
Taigi iš tikrųjų, kad tikrai ne dirbti.
Bet tai tipo iliuzija teikiama visus savo programas.
Taigi, jei jūs turėjo du koncertai RAM, tai yra, kaip kompiuteris gali galvoti apie tai.
>> Dabar atsitiktinai, vienas iš šių daiktai, vienas iš šių atminties segmentus,
vadinamas kamino.
Ir iš tiesų bet kuriuo metu taip toli rašyti kodą
kad turite vadinamas funkcija, pavyzdžiui vamzdynui.
Prisiminkite, kad bet kuriuo metu aš Nupiešti kompiuterio atmintis,
Aš visada atkreipti rūšiuoti pusė stačiakampio čia
ir nesivargina kalbėti apie tai, kas aukščiau.
Nes kai pagrindinis yra vadinamas, aš teigti, kad jūs gaunate šį atminties rakštis
kad krinta čia.
Ir jei pagrindinis vadinama funkcija kaip apsikeitimo, gerai apsikeitimo eina čia.
Ir it turns out, kad tai kur jis baigiant.
Apie vadinamąjį kamino viduje kompiuterio atmintyje.
Šiuo metu yra dienos pabaigoje, tai tik adresus.
Tai tarsi baitas lygus nuliui, baitas vienas, baitas 2 mlrd.
Bet jeigu jūs manote apie tai kaip šio stačiakampio objektą,
visi mes darome kiekvieną kartą mes vadiname funkcija
sluoksniavimasis naują gabaliuką atmintį.
Mes teikiame šią funkciją gabaliuką iš savo atminties dirbti.
>> Ir prisiminti, kad dabar tai yra svarbu.
Nes jei mes turime kažkas panašaus apsikeitimo
ir du vietiniai kintamieji, pavyzdžiui, A ir B mes pakeisti šias vertybes iš vienos ir dviejų
iki dviejų ir vieno, prisiminti kad kai apsikeitimo grįžta,
tai kaip nors šį gabaliuką atminties yra tik dingo.
Iš tikrųjų, tai dar ten teismo ekspertizės.
Ir kažkas dar iš tikrųjų egzistuoja.
Bet konceptualiai, tai taip Nors tai visiškai dingo.
Ir taip pagrindinė nepažįsta bet darbo kad buvo padaryta toje apsikeitimo funkcija,
nebent tai tikrai praėjo tie argumentai žymeklis ar nuorodą.
Dabar esminis sprendimas į šią problemą su apsikeitimo sandoriu,
bėga dalykų pagal adresą.
Tačiau paaiškėja, taip pat tai, kas vyksta virš tos dalies
stačiakampio visa tai laikas yra dar yra daugiau atminties ten.
Ir kai jūs dinamiškai paskirstyti atmintį,
ar tai viduje GetString, kuris mes darome Jums į CS50
biblioteka, arba, jei jus vaikinai skambinti malloc ir paklausti
operacinės sistemos iš riekė atminties, jis nėra ateis iš kamino.
Jis kilęs iš kitoje vietoje jūsų kompiuterio atmintyje
Tai vadinama krūvos.
Ir tai ne koks nors kitoks.
Tai tas pats RAM.
Tai tas pats atminties.
Tai tiesiog RAM tai iki ten vietoj žemyn čia.
>> Ir taip, ką tai reiškia?
Na, jei jūsų kompiuteris turi baigtinis atminties kiekis
ir kamino auga, todėl kalbėti, o krūva, pagal
šios rodyklės, auga žemyn.
Kitaip tariant, kiekvienas laikas skambinate malloc,
jūs suteikiamas gabaliuką atminties iš aukščiau,
tada gal šiek tiek mažesnis, tada šiek tiek mažesnis, kiekvieną kartą jums skambinti malloc,
krūvos, tai naudojimas, rūšies auga,
auga arčiau ir arčiau, ką?
Kamino.
Taigi ar tai atrodo kaip gera idėja?
Aš turiu galvoje, kur ji tikrai nėra aišku, Ką dar galite daryti, jei tik
turi baigtinį kiekį atminties.
Bet tai tikrai blogai.
Šios dvi strėlės yra ant avarijos kursą vienas su kitu.
>> Ir paaiškėja, kad blogas vaikinas, žmonės, kurie yra ypač gerai su programavimo,
ir bando nulaužti į kompiuterius, gali išnaudoti šią tikrovę.
Tiesą sakant, aptarkime šiek tiek fragmentą.
Taigi tai yra pavyzdys galite skaityti apie išsamiau Vikipedijoje.
Mes jums taško straipsnis, jei įdomu.
Bet yra ataka paprastai žinomas kaip buferio, kad
gyvuoja tol, kol žmonėms turėjo galimybę manipuliuoti
kompiuterio atmintyje, ypač C. Taigi tai yra labai savavališkas programa,
bet tegul jį perskaityti iš apačios į viršų.
Pagrindinė į argc char žvaigždutėmis argv.
Taigi, tai programa, kuri trunka komandinės eilutės argumentai.
Ir visa pagrindinė neturi matyt yra skambutis funkcija, ją vadina F paprastumo.
Ir jis eina į ką?
Argv vienas.
Taigi jis eina į F kokia žodis yra tai, kad naudotojas atspausdintos
ne po eilutę Programos pavadinimas ne visiems.
Taigi, panašiai kaip Cezaris ar Vigenere, kuris jums gali prisiminti daro su argv.
>> Taigi, kas yra F?
F trunka eilutę jos vienintelis argumentas,
AKA char žvaigždė, pats dalykas, kaip eilutę.
Ir tai vadinama savavališkai bar šiame pavyzdyje.
Ir tada char C 12, tik profanas sąlygomis,
kas char c laikiklis 12 daro mus?
Kas tai daryti?
Paskirstyti atmintį, ypač 12 baitų 12 simbolių.
Būtent.
Ir tada paskutinė eilutė, išmaišyti ir Kopijuoti, jūs tikriausiai nematė.
Tai eilutė kopija funkcija, kurios tikslas gyvenime
yra nukopijuoti savo antrąjį argumentą į pirmąjį argumentą,
tačiau tik iki tam tikros tikras baitų skaičius.
Taigi trečiasis argumentas sako, kiek baitų turėtumėte nukopijuoti?
Iš juostos ilgis, kokia vartotojas įvedėte.
Ir turinys Baras, kad eilutė yra
nukopijuoti į atminties nurodė esant C
>> Taigi, šis atrodo rūšies kvailas, ir jis yra.
Tai nenatūralu pavyzdys, bet tai atstovas
iš atakų vektorius klasės, iš puola programą būdas.
Viskas yra gerai ir gerai, jei vartotojas tipai Žodžiu tai 11 simbolių
arba mažiau, plius Backslash nulis.
Ką daryti, jei vartotojas įveda į daugiau nei 11 arba 12 arba 20 arba 50 simbolių?
Kas tai programa ketinate daryti?
Potencialiai SEG kaltė. Tai vyksta aklai kopijuoti viską bare iki
į jo ilgį, kuris yra tiesiog viskas juostoje,
į adresą nurodė C. Bet C tik Preemptively skiriamas kaip 12 baitų.
Tačiau nėra papildomas patikrinimas.
Nėra jeigu sąlygomis.
Nėra klaidų tikrinimas čia.
>> Ir taip, tai ką ši programa yra ketina padaryti, tai tiesiog aklai
nukopijuoti vieną dalyką į kitą.
Ir todėl, jei mes atkreipiame tai kaip paveikslėlyje, čia
tik iš atminties rakštis.
Taigi pranešimas apačioje, mes turi vietinį kintamąjį baras.
Taip, kad žymeklis, kad ketina store-- o tos vietos argumentą, kad manimi
ketina laikyti styginių baras.
Ir tada pastebėti tik virš jo per kaminą,
nes kiekvieną kartą, jūs paprašykite Memory dėl kaminą,
jis eina truputį virš jo pavaizduotomis piktogramo-,
Atkreipkite dėmesį, kad mes turime ten 12 baitų.
Viršutiniame kairiajame vienas yra C laikiklis nulis ir apačioje dešinėje yra C laikiklis 11.
Tai tiesiog kaip kompiuteriai ketina nustatyti jį.
Taigi tiesiog intuityviai, jei juosta turi daugiau kaip 12 simbolių iš viso, įskaitant
"Backslash nulis, kur yra 12 arba C laikiklis 12 ketinate eiti?
Arba, tiksliau, kur yra 12 požymis ar 13 simbolių,
šimtoji charakteris vyksta baigti paveikslėlyje?
Aukščiau ar žemiau?
>> Teisė, nes net pati kamino auga aukštyn,
kai jūs įdėti stuff jis, ji dėl dizaino,
kelia atmintį nuo viršaus iki apačios.
Taigi, jei jūs turite daugiau nei 12 baitų, jūs ketinate pradėti perrašyti baras.
Dabar tai klaida, bet tai tikrai ne big deal.
Bet tai yra baisi, nes ten daugiau daiktų vyksta atmintyje.
Taigi čia, kaip mes galime įdėti Sveiki, būtų aiškus.
Jei aš įvedėte Hello eilutėje.
H-E-L-L-O Backslash nulis, baigiasi per tie 12 baitų, o mes super saugus.
Viskas gerai.
Bet jei aš tipo kažką ilgiau, potencialiai tai
vyksta slinkti į baro erdvėje.
Bet dar blogiau, paaiškėja iš viso to laiko,
nors mes niekada kalbėjo apie tai, kamino naudojamas kitų dalykų.
Tai ne tik vietiniai kintamieji.
>> C yra labai žemo lygio kalba.
Ir tai tarsi slapta naudoja krūvą taip pat
prisiminti kai funkcija vadinama, ką
adresas yra ankstesnio funkciją, todėl ji gali šokinėti atgal į tą funkciją.
Taigi, kai pagrindiniai skambučiai apsikeitimo tarp ką užmaunamas ant kamino
yra ne tik apsikeitimo vietinius kintamuosius, ar jos argumentai, taip pat slapta stumiama
ant kamino kaip pavaizduota raudonu gabaliuką čia
yra pagrindinė adresas fiziškai jūsų kompiuterio atmintyje,
taip, kad, kai apsikeitimo yra padaryta, kad kompiuteris žino, man reikia grįžti į pagrindinį
ir baigti vykdyti pagrindinę funkciją.
Taigi tai yra pavojinga dabar, nes jei vartotojas įveda gerai daugiau nei Sveiki,
pavyzdžiui, kad vartotojo įvesties clobbers arba perrašo tą raudoną skyrių,
logiškai, jei kompiuterio tik ketina aklai prisiimti
kad tos raudonos gabalas baitai adresas, kuriuo ji turėtų grįžti,
Ką daryti, jei priešas yra pakankamai protingas, arba laimė įdėti baitų seka
ten, kad atrodo kaip adresą, bet tai kodo adresas
kad jis ar ji nori kompiuterį vykdyti vietoj pagrindinis?
>> Kitaip tariant, jei ką vartotojas rašyti ne laiku,
yra ne tik kažkas nežalingas, kaip labas,
bet tai tikrai kodas, kuris yra lygiavertis ištrinti visus šio vartotojo failus?
Arba elektroniniu paštu savo slaptažodį mane?
Arba pradėti prisijungdami savo klavišų, tiesa?
Yra būdas, tegul numato šiandien kad jie galėtų įvesti ne tik labas
Pasaulio ar jų pavadinimas, jie iš esmės gali
praeiti kodas, nulių ir tie, kad kompiuteris
klaidų abiems kodą ir adresą.
Taigi nors ir šiek tiek abstrakčiai, jei vartotojas įveda į pakankamai rungimosi kodas
kad mes apibendrinti čia taip A. A yra ataka ar priešai.
Taigi tiesiog blogas stuff.
Mums nerūpi apie numeriai arba nuliai ar tie
Šiandien, pavyzdžiui, kad jūs galų gale perrašyti tą raudoną skyrių,
pastebėti, kad baitų seka.
O 835 Cnulis aštuoni nulis.
Ir dabar taip Vikipedijos straipsnio čia pasiūlė, jei dabar iš tikrųjų pradėti
ženklinimo jūsų kompiuterio baitų atminties, koks Vikipedijos straipsnis yra
Pasiūlymą yra tai, kas jei adresas tos viršutiniame kairiajame baitas yra 80 C 0 3508.
>> Kitaip tariant, jei blogiukas yra pakankamai protingas su savo kodą
kad iš tikrųjų įdėti numerį čia, kad atitinka kodas adresą
jis ar ji švirkščiama į kompiuterį, galite
gali apgauti kompiuterį į ką nors.
Šalinti failus, elektroninio pašto siuntimas dalykų, uostyti savo srautą,
tiesiog nieko galėtų būti įpurškiamas į kompiuterį.
Ir taip buferio ataka jos branduolys
yra tik kvailas, kvailas rankinis masyvo, kad
neturėjo patikrintas jos ribų.
Ir tai, kas yra super pavojingas ir tuo pat metu itin galingas
C yra tai, kad mes iš tikrųjų turi prieiga į bet kurią atminties.
Tai iki mūsų programuotojai, kurie rašo originalų kodą
patikrinti adyti ilgį bet masyvai, kad mes manipuliuoti.
Taigi, kad būtų aišku, kas yra pataisyti?
Jei mes įvirsta į tai kodas, aš ne tik
pakeisti baro ilgį, kas dar turėčiau būti patikrinti?
Ką dar turėčiau daryti, kad išvengti šio užpuolimo visiškai?
Aš nenoriu pasakyti, tiesiog aklai kad jums reikia nukopijuoti tiek baitų
taip pat kaip ir baro ilgis.
Noriu pasakyti, kopijuoti kaip daug baitų kaip yra baro
iki paskirta atminties arba 12 maksimaliai.
Taigi man reikia šiek tiek, jei sąlyga natūra kad daro patikrinti juostos ilgis,
bet jei jis viršija 12, mes tiesiog sunku kodą 12 kaip didžiausią galimą atstumą.
Priešingu atveju vadinamasis buferis perpildymo ataka gali atsitikti.
Esančios šių skaidres apačioje, Jei įdomu skaityti daugiau
yra tikrasis originalus straipsnis Jei norite pažvelgti.
>> Bet dabar, be kainų mokama čia buvo neefektyvumą.
Taigi, tai buvo greitai žemo lygio Apžvelkite ką
problemų gali kilti, dabar, kad mes turėti prieigą prie kompiuterio atmintyje.
Bet kita problema, mes jau suklupo pirmadienį
buvo tik neefektyvumas Susietos sąrašą.
Mes grįžti į linijinio laiko.
Mes nebeturime vientisą masyvą.
Neturime laisvą prieigą.
Mes negalime naudoti kvadratinių laikiklis notacijos.
Mes tiesiog turime naudoti, o kilpa kaip vieną parašiau prieš momentas.
Tačiau pirmadienį, mes teigė, kad mes galime slinkti atgal į efektyvumo srityje
pasiekti kažką, kad logaritminė galbūt, arba geriausia dar,
gal net kažkas, kad yra Vadinamasis pastovus laikas.
Taigi, kaip mes galime padaryti, kad naudojant šiuos naujus Įrankiai, šie adresai, šiuos patarimus,
ir sriegimo dalykų mūsų pačių?
Na, tarkime, kad čia, tai yra krūva
skaičių, kad mes norime Laikyti duomenų struktūra ir paieškos efektyviai.
Mes galime visiškai atsukti į savaitę du, mesti juos į masyvą,
ir ieškoti juos naudojant dvejetainį paiešką.
Skaldyk ir valdyk.
Ir iš tiesų parašė dvejetainis Ieškoti PSET3,
kur įgyvendino suradimas programą.
Bet žinote ką.
Yra rūšies daugiau protingas būdas tai padaryti.
Tai šiek tiek daugiau sudėtingas ir galbūt
leidžia mums pamatyti, kodėl dvejetainis Paieška yra labai daug greičiau.
Pirma, galime pristatyti medžio sąvoka.
Kuris nors iš realybė medžiai rūšies
augti kaip šis, į kompiuterį pasaulyje Mokslas jie rūšies auga žemyn
kaip šeimos medį, kur jūs turite jūsų seneliai ar proseneliai
arba Plauktiņš viršuje, patriarchas ir šeimos matriarch, tik vienas
Vadinamasis šaknis, mazgas, toliau kuri yra jo vaikai,
žemiau kurios yra jos vaikai, arba jos palikuonys apskritai.
Ir nors kabinti ne šeimos apačios
medis, Be to, kad Jauniausias šeimoje,
taip pat gali būti tiesiog bendrine vadinama medžio lapai.
>> Taigi tai yra tik krūva žodžių ir apibrėžimų
kažko vadinamas į kompiuterį medis Mokslas, panašiai kaip šeimos medį.
Bet yra mėgėjas įsikūnijimų medžių, iš kurių vienas
vadinamas dvejetainis paieškos medis.
Ir jūs galite rūšies Tease be ko šis dalykas veikia.
Na, tai dvejetainis, kokia prasme?
Kur dvejetainis iš čia?
Atsiprašome?
Tai ne tiek arba.
Tai daugiau, kad kiekvienas iš mazgų neturi daugiau nei du vaikai, kaip matome čia.
Apskritai, tree-- ir Jūsų tėvai ir seneliai
gali turėti daug vaikų arba VaikaiÄ¨iai kaip jie iš tikrųjų nori,
ir taip, pavyzdžiui, ten mes turime tris vaikai išjungti, kad dešinėje mazgas,
bet dvejetainis medis, mazgas turi nulis, vienas arba du vaikai maksimaliai.
Ir tai gražus nuosavybė, nes jei jis uždėtas dviejų,
mes ketiname būti suteikta galimybė gauti šiek tiek žurnalo bazę du
veiksmas vyksta čia galiausiai.
Taigi, mes turime kažką logaritminis.
Bet daugiau apie tai per akimirką.
Paieška medis reiškia, kad skaičiai yra išdėstytos taip, kad kairysis vaiko
vertė yra didesnė už šaknies.
Ir jo teisė vaikas didesnis nei šaknų.
Kitaip tariant, jei bet kuris iš imtis mazgai, šiuo paveikslėlyje apskritimai,
ir žiūri į savo kairę Vaikas ir jo teisė vaikas
pirmasis turėtų būti mažesnis nei, antrasis turėtų būti didesnė nei.
Taigi normalumas patikrinti 55.
Jis paliko vaiką yra 33.
Tai mažiau nei.
55, jo teisė vaikas yra 77.
Tai daugiau nei.
Ir tai rekursywny apibrėžimas.
Mes galime patikrinti kiekvieną iš tų vieną mazgai ir tas pats modelis būtų laikyti.
>> Taigi, kas yra malonu A dvejetainis paieškos medis, yra
kad vienas, mes galime ją įgyvendinti su struct, tiesiog patinka.
Ir nors mes mesti daug struktūrų jūsų,
jie šiek tiek dabar intuityvus tikiuosi.
Sintaksė yra vis dar neaiškus tikrai, Bet mazgas turinys šioje grupėje
context-- ir mes nuolat naudojant žodį mazgas,
ar tai stačiakampis ekrane arba ratu,
tai tik keletas bendrinis konteineris, šiuo atveju medžio, kaip ir viename
matėme, turime sveikąjį skaičių kiekviena iš mazgų
ir tada man reikia dviejų patarimų nukreipta į kairę vaiko ir dešinės vaikui,
atitinkamai.
Štai kaip mes galime įgyvendinti, kad į struct.
Ir kaip galėčiau ją įgyvendinti kodas?
Na, Paimkime greitai pažvelgti į šią mažą pavyzdį.
Tai nėra funkcionalus, bet aš kopijuoti ir įklijuoti tą struktūrą.
Ir jei mano funkcija dvejetainis Paieška medis vadinamas paieška,
ir tai trunka du argumentus, sveikas skaičius, N ir rodyklė
į mazgą, todėl rodyklę į medį arba rodyklė į medį šaknis,
kaip man eiti apie paieškos N?
Na, visų pirma, nes aš sprendžiant su rodyklėmis,
Aš ruošiuosi daryti normalumas patikrinti.
Jei medžių lygu lygu nuliui, yra N Šiame medyje ar ne šiame medyje?
Ji negali būti, tiesa?
Jei aš esu praeityje nulis, ten nieko nėra.
Aš taip pat tik aklai pasakyti return false.
Jei man nieko, aš tikrai negaliu rasti jokių numerį N. Taigi, ką dar galėčiau
Patikrink Dabar?
Aš ruošiuosi pasakyti gerai dar, jei N yra mažiau nei nepriklausomai yra medžio mazgas
kad aš įteikė N vertę.
Kitaip tariant, jei skaičius aš ieško, N, yra mažesnis nei mazgas
kad aš žiūriu.
Ir aš mazgas žiūriu ne vadinamas medis,
ir atšaukia iš ankstesniame pavyzdyje gauti tuo verte rodyklė,
Aš Rodyklių notacijos.
Taigi, jei N yra mažiau nei medžio rodykle N, noriu konceptualiai eiti į kairę.
Kaip aš išreikšti ieško liko?
Būti aišku, jei tai yra tas vaizdas,
ir aš buvo perduota, kad viršutinis arrow kad manimi nukreipta žemyn.
Štai mano medis žymeklis.
Aš nukreipta į medžio šaknis.
Ir aš ieškau tarkim, už numeris 44, savavališkai.
Yra 44 arba mažiau nei didesnis nei 55 Akivaizdu?
Taigi, tai mažiau nei.
Ir todėl tai jei taikoma sąlyga.
Taigi konceptualiai, ką noriu Ieškoti kito, jei aš ieškau 44?
Taip?
>> Būtent, aš noriu ieškoti kairįjį vaiką,
arba į kairę sub-tree šio paveikslėlyje.
Ir iš tiesų, tegul mane per vaizdas žemyn čia
tik už momentą, nes Aš negaliu subraižyti this out.
Jei aš pradedu čia ne 55, o Aš žinau, kad vertė 44
Aš ieškau yra kairysis, tai tipo
tiek kaip ašarojimas telefono knygą pusė arba ašarojimas medį per pusę.
Aš jau nebeturi rūpintis Visa tai pusė medžio.
Ir dar, kaip bebūtų keista, kalbant iš struktūra, tai per čia, kad dalykas
prasideda 33, tai savaime yra dvejetainis paieškos medis.
Aš pasakiau žodis rekursywny anksčiau, nes Iš tiesų, tai yra, kad duomenų struktūra
pagal apibrėžimą yra grįžtamojo.
Jums gali tekti medį, kad tai? didelis, bet kiekvienas savo vaikus viena
atstovauja medį tik šiek tiek mažesnis.
Vietoj jo yra senelis ar močiutė, dabar tai tiesiog mama
or-- aš negaliu say-- ne mama ar tėtis, kad būtų keista.
Vietoj du vaikai ten Būtų kaip brolis ir sese.
Naujos kartos šeimos medį.
Tačiau struktūriškai, tai tą pačią idėją.
Ir it turns out Turiu funkciją su kuriais galiu ieškoti dvejetainį paiešką
medis.
Jis vadinamas paieška.
Ieškoti N medžių rodyklės kairėje kitas, jei n yra didesnis, negu vertė
kad aš šiuo metu.
55 į istoriją prieš akimirką.
Turiu funkcija vadinama Paieška kad aš galiu tik
perduoti N. tai ir rekursyviai paiešką sub-tree ir tiesiog grąža
kad ir ką atsakyti.
Kita aš turiu šiek tiek galutinį bazinį scenarijų čia.
>> Kas yra galutinė atveju?
Medis yra arba niekinis.
Vertė aš arba ieškote yra mažiau nei ji arba didesnis, nei
arba lygi jai.
Ir galėčiau pasakyti lygūs lygūs, bet logiškai tai
lygiavertis tiesiog pasakyti dar čia.
Taigi tiesa yra tai, kaip rasti kažką.
Taigi, tikiuosi, tai dar įtikinamų pavyzdžių
nei kvailas sigma funkcija Mes padarėme keletą paskaitų atgal,
kur jis buvo tik kaip paprasta naudoti kilpą suskaičiuoti visus skaičius vienoje iš
kad N. čia su duomenų struktūros kad pati yra rekursyviai
apibrėžti ir rekursyviai parengtas, dabar mes turi galimybę išreikšti save, kad
kodu, kad pati yra grįžtamojo.
Taigi tai yra lygiai toks pats kodas čia.
>> Taigi, ką kitas problemas mes galime išspręsti?
Taigi greitas žingsnis nuo medžiai vos akimirką.
Štai, tarkim, Vokietijos vėliava.
Ir ten aiškiai modelis su šiuo vėliava.
Ir ten daug vėliavos pasaulyje, kad
yra taip paprasta, kaip tai kalbant jų spalvų ir raštų.
Bet manyti, kad šis yra saugomi kaip GIF arba JPEG arba Bitmap, ar ping,
bet grafinis failo formatas su kuria jūs esate susipažinę,
kai kurie iš jų mes žaisti su į PSET4.
Tai neatrodo verta saugoti juoda pikselių, juoda pikselių, juoda pikselių,
taškas, taškas, taškas, visa krūva juodi pikseliai pirmą scanline,
arba eilutė, tada visa krūva tas pats, tada visa krūva
iš tos pačios, ir tada visa krūva raudonų taškų,
raudonos taškų, raudona taškų, tada visa krūva geltonų taškų, geltona, tiesa?
>> Yra toks neefektyvumas čia.
Kaip jūs intuityviai suspausti Vokietijos vėliava
jei ją įgyvendinant kaip failą?
Kaip kokia informacija mes galime ne vargintis saugoti diske tam
sumažinti mūsų failo dydį iš, kaip megabaitas į kilobaitai, kažkas
mažesnis?
Kur slypi atleidimų Čia bus aišku?
Ką galima padaryti?
Taip?
Būtent.
Kodėl gi ne, o ne prisiminti kiekvieno pikselio spalva darn
kaip jūs darote PSET4 su bitmap failo formatu,
kodėl ne jūs tiesiog atstovauti kairiausias skiltyje taškų, pavyzdžiui,
juodų taškų krūva, krūva raudonos, ir geltonos krūva,
ir tada tiesiog kažkaip užkoduoti idėja iš Pakartokite tai 100 kartų
ar kartoti 1000 kartus?
Kur 100 ar 1000 yra tik sveikasis skaičius, todėl jūs
gali išsisukti tik su vienu numeriu vietoj šimtų ar tūkstančių
Papildomų taškų.
Ir iš tiesų, tai, kaip mes gali suspausti Vokietijos vėliava.
Bei
Dabar ką apie Prancūzijos vėliava?
Ir šiek tiek kažkokia psichikos naudotis, su kurios vėliava
gali būti suspausta daugiau diske?
Vokietijos vėliava arba prancūzų vėliava, jei mes šį požiūrį?
Vokietijos vėliava, nes ten daugiau horizontalus atleidimo.
Ir dizainas, daugelis grafinis failas formatai tiesų dirba kaip skenavimo linijas
horizontaliai.
Jie galėtų dirbti vertikaliai, tiesiog žmonija
prieš nusprendusios metų, kad mes apskritai manau dalykų eilės
iki eilės vietoj stulpelyje stulpelyje.
Taigi iš tiesų, jei buvo pažvelgti į failą
dydis Vokietijos vėliava ir prancūzų vėliava, tol, kol geba yra
tas pats, to paties pločio ir aukštis, tai vienas
čia bus didesni, nes jus turi pakartoti sau tris kartus.
Turite nurodyti mėlyna, pakartokite Būk, balta, pakartokite sau, raudona,
pakartokite sau.
Jūs galite ne tik eiti visi kelią į dešinę.
Ir kaip panaikinti, kad išvalyti suspaudimo
yra visur, jei jie yra keturi rėmai iš video-- jums
gali priminti, kad filmą arba vaizdo įrašas yra paprastai
kaip 29 arba 30 kadrų per sekundę.
Tai tarsi maža Flip Book, kur jūs tik pamatyti vaizdą, vaizdas, vaizdo, vaizdas,
vaizdas tiesiog super greitai, todėl atrodo ant ekrano aktoriai juda.
Štai kamanių apie Į viršų gėlių krūva.
Ir nors ji gali būti natūra sunku pamatyti iš pirmo žvilgsnio,
vienintelis dalykas, juda šis filmas yra bičių.
>> Kas yra kvailas apie saugoti vaizdo zdekompresowaniu?
Tai tipo iš atliekų saugoti vaizdo įrašą kaip keturias beveik identiški vaizdus,
skiriasi tik tiek, kiek, kur bičių yra.
Jūs galite išmesti pats tos informacijos
ir nepamiršti, tik, pavyzdžiui, pirmas rėmas ir paskutinis kadras,
pagrindiniai rėmai, jei jūs nors girdėjote žodį
ir tiesiog Laikyti viduryje, kai bičių yra.
Ir jūs neturite saugoti visus rožinė,
ir mėlyną, ir žalia vertės, taip pat.
Taigi tai yra tik pasakyti, kad suspaudimas yra visur.
Tai metodas, mes dažnai naudoti arba imtis už suteiktas šių dienų.
>> Bet kaip jūs suspausti tekstą?
Kaip tu apie suspaudžiant tekstą?
Na, kiekvienas iš simbolių ASCII yra vienas baitas, arba aštuonis bitus.
Ir tai rūšies kvailas, tiesa?
Kadangi jūs tikriausiai tipas A ir E ir I ir O, U daug
dažniau nei kaip W arba Q arba Z, priklausomai nuo to, kokia kalba
rašote tikrai.
Ir taip, tai kodėl mes vartojame Aštuoni bitai kiekvienam laiške,
įskaitant mažiausiai lankytinos raidės, tiesa?
Kodėl gi ne naudoti mažiau bitai super lankytinos raidės,
kaip E, ką galite atspėti pirmasis Laimės rato,
ir naudoti daugiau bitai mažiau populiarūs raidės?
Kodėl?
Nes mes tik ketina naudoti juos rečiau.
>> Na, it turns out, kad turi buvo bandoma pagaminti tai padaryti.
Ir jei jūs prisimenate iš klasės mokyklinis ar vidurinės mokyklos, Morzės kodas.
Morzės abėcėlė turi taškus ir brūkšneliai, kurie gali būti
perduodama išilgai laido garsai ar signalai kažkoks.
Bet Morzės kodas yra super švarus.
Tai tipo dvejetainis sistemos kad jūs turite taškus arba brūkšnių.
Tačiau jei matote, pavyzdžiui, du taškus.
Arba, jei jūs manote atgal į operatoriaus kas eina kaip beep, beep, beep,
pyptelėjimas, pradeda šiek tiek spragtuką , kuri perduoda signalą,
jei jus, gavėjas gauna du taškų, kokią žinią jau gavote?
Visiškai savavališkai.
>> Aš?
Aš?
Arba ką about-- ar man?
Gal tai buvo tik du E teisė?
Taigi ten ši problema iš decodability su Morzės
kodas, pagal kurį, jei asmuo siunčia jums laišką
iš tikrųjų pauzių, todėl galite rūšiuoti pamatyti ar išgirsti tarp raidžių spragas,
tai nepakanka tik siųsti srautas nulių ir,
arba taškeliai ir brūkšneliai, nes ten dviprasmiškumas.
E yra vienas taškas, tad jei matyti du taškus ar išgirsti du taškus,
gal tai du E "arba gal tai vienas I.
Taigi, mes turime sistemą, kuri siūlo pasirinkti šiek tiek daugiau protingas, kad ne.
Taigi žmogus, vardu Huffman'o metų prieš atėjo su tiksliai tai.
Taigi mes tiesiog vyksta imtis pirmo žvilgsnio
tuo, kaip medžiai Priklauso tai.
Tarkim, kad tai yra kai kvailas pranešimą norite siųsti,
sudaro tik A, B, C anketa D'S ir E ", bet yra atleidimo iš darbo daug čia.
Jis nėra skirtas būti anglų kalba.
Tai ne šifruojamas.
Tai tiesiog kvaila žinutė su daug pasikartojimų.
Taigi, jei jūs iš tikrųjų Paskaičiuoti visi A s, B-ųjų C "D's, o E", čia
dažnis.
20% laiškus A-ųjų 45% raidės
yra E ", ir trys kiti dažniai.
Mes skaičiuojamos ten rankiniu būdu ir tiesiog darė matematikos.
>> Taigi, tai Pasirodo, kad Huffman, prieš kurį laiką,
Supratau, kad, žinote, kas, jei aš pradėti statyti
medis arba miško medžių, jei norite, taip, aš galiu padaryti taip.
Aš ruošiuosi duoti mazgas kiekvienas laiškų, kad aš rūpi
ir aš ruošiuosi laikyti viduje, kad mazgas
dažniai kaip slankiojo kablelio vertė, ar galima jį naudoti N, taip pat,
bet mes tiesiog naudokite plūdę čia.
Ir algoritmas, jis pasiūlė, kad jūs
pasinaudoti šia vieno mazgo mišką medžiai, todėl itin trumpi medžiai,
ir pradėdami jungia juos su naujų grupių, naujos tėvai, jei bus.
Ir jums tai padaryti, pasirinkdamas du mažiausi dažniai vienu metu.
Taigi aš paėmė 10% ir 10%.
Sukurti naują mazgas.
Ir aš vadinu naują mazgo 20%.
>> Kuris dviejų mazgų Aš sujungti toliau?
Tai šiek tiek dviprasmiškas.
Taigi ten kai kampiniai atvejus apsvarstyti, tačiau, kad viskas gana,
Aš ruošiuosi rinktis 20% - Aš dabar ignoruoti vaikus.
Aš ruošiuosi pasirinkti 20% ir 15% ir parengti du naujus kraštus.
Ir dabar, kai du mazgai man logiškai sujungti?
Ignoruoti visus vaikus, visi anūkai, tiesiog pažvelgti šaknų
dabar.
Kuris dviejų mazgų aš kergti?
Du punktas 0,35.
Taigi leiskite man atkreipti du naujus kraštus.
Ir tada aš tik turiu vieną kairę.
Taigi čia medis.
Ir tai buvo parengtas sąmoningai ieškoti rūšies gana,
bet pastebėsite, kad kraštai turi Taip pat buvo paženklinti nulio iki vieneto.
Taigi, visi iš kairės kraštų yra nulinės savavališkai, bet nuosekliai.
Visi reikiami kraštai yra tie.
>> Ir taip, ko Hoffmanas siūloma, jei norite atstovauti B,
o ne atstovauja skaičių 66, kaip ASCII kuri yra aštuoni visą bitai,
Žinai ką, tik parduotuvėje modelis nulis, nulis, nulis,
nuliui, nes tai kelias nuo mano medžio, p Huffman anketa medis,
kad iš šaknų lapų.
Jei norite išsaugoti El, priešingai, ne
siųsti aštuonis bitus, atspindintys E. Vietoj to, siųsti ką modelio bitai?
Vienas.
Ir kas malonu apie tai kad E yra populiariausias raštas,
ir jūs, naudojant Trumpiausias kodas.
Kitas populiariausias laiškas atrodo, kad jis
buvo A. Ir taip, kiek bitų gi jis siūlo naudoti, kad?
Nulis, vienas.
>> Ir todėl, kad ji įgyvendinama kaip šio medžio, nes dabar
leiskite numatyti ten nėra dviprasmiškumo kaip Morzės
kodas, nes visi iš laiškus galite rūpi
yra iš šių kraštų pabaigoje.
Taigi, kad tik vienas taikymas medį.
Tai is-- ir aš banga mano ranka į tai, kaip jūs
gali įgyvendinti tai kaip C struktūrą.
Mes tiesiog reikia derinti simbolis, kaip char,
ir, dažnių kairę ir į dešinę.
Bet pažvelkime į du Galutiniai pavyzdžiai, kad jums
gauti pakankamai susipažinę su po nulis Viktorina į problemą nustatyti penki.
>> Taigi, yra duomenų struktūros žinomas kaip maišos lentelėje.
Ir maišos lentelė yra natūra atvėsti, kad ji turi kibirų.
Ir Tarkime, kad keturių kibirų čia tik keturi tarpų.
Štai kortų kaladė, ir čia yra klubas, kastuvas, klubas, deimantai, klubas,
Deimantai, klubas, deimantai, clubs-- todėl tai yra atsitiktinai.
Širdelės, hearts-- todėl aš bucketizing visi įėjimai čia.
Ir A maišos lentelė poreikiai pažvelgti į jūsų indėlį,
ir tada įdėti jį į tam tikrą vieta pagal tai, ką matote.
Tai algoritmas.
Ir aš naudoju super paprasta vaizdo algoritmas.
Sunkiausia dalis buvo prisiminti ką nuotraukos buvo.
Ir tada ten keturis bendrus dalykus.
>> Dabar kaminai augo, o yra sąmoningas dizainas dalykas čia.
Bet ką dar galėčiau padaryti?
Taigi iš tikrųjų čia turime krūva senų mokyklos egzaminu knygų.
Tarkime, kad krūva studentų pavadinimai yra čia.
Štai didesni maišos lentelės.
Vietoj keturių kaušų, Aš, tarkim 26.
Ir mes nenorėjome eiti skolintis 26 dalykų iš išorės [? Annenberg?], Todėl
čia penkių kad atstovauti Nuo A iki Z. Ir jei aš
pamatyti studentas, kurio vardas prasideda A Aš ruošiuosi įdėti savo arba savo viktoriną ten.
Jei kas nors pradeda su C, ten, A-- tikrųjų nenorėjo to daryti.
B eina čia.
Taigi aš turiu A ir B ir C. Ir dabar čia dar studentas.
Bet jei tai maišos lentelė įgyvendinamas su masyvo,
Aš rūšies prisukamas šiuo metu, tiesa?
I rūšies reikia įdėti šį kažkur.
>> 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.
Aš ruošiuosi įdėti jį į D. Tad pirma, turiu atsitiktinių tiesioginę prieigą
į kiekvieną studentams kibirai.
Bet dabar tai tipo atiteko į kažką linijinė,
nes jei aš noriu ieškoti kažkam kurio vardas prasideda A, aš patikrinti čia.
Bet jei tai yra ne A studentas aš ieškote,
I rūšies turite pradėti tikrinti kad kaušai, nes ką aš padariau
buvo tarsi tiesiškai zondas duomenų struktūrą.
Kvailas būdas pasakyti tiesiog ieškoti pirmo prieinamo atidarymo,
ir įdėti kaip planas B, taip sakant, arba planas, D, šiuo atveju, vertė,
toje vietoje vietoj.
Tai tik todėl, kad jei jūs gavo 26 vietas ir studentai
su vardo Q arba Z, ar kažkas panašaus kad bent jau jūs naudojate erdvę.
>> Bet mes jau matėme daugiau protingi sprendimai čia, tiesa?
Ką tu darytum vietoj jei turite susidūrimo?
Jei du žmonės turi pavadinimas A kas būtų
buvę protingesni ar daugiau intuityvus sprendimas ne tik
Eksploatacijos kur D yra turėtų būti?
Kodėl ne aš tiesiog eiti ne [? Annenberg?]
kaip malloc, kitą mazgą, jį čia, ir tada įdėti, kad studentas čia.
Taigi, kad aš iš esmės turi kai masyvą natūra,
arba gal ir daugiau elegantiškai kaip mes pradeda rodyti susietą sąrašą.
>> Ir taip maišos lentelė yra struktūra kad galėtų atrodyti tik kaip šis,
bet daugiau protingai, jūs kažką vadinama atskiras jungimo, kuriuo maišos lentelė
paprasčiausiai yra matrica, kiekvienas iš kurio sudedamosios dalys yra ne skaičius,
pati yra susijusi sąrašas.
Taigi, kad jums super greitai prieiga sprendžiant, kur maišos savo vertę.
Panašiai kaip su kortelėmis, pavyzdžiui, Aš padariau super greitus sprendimus.
Širdelės eina čia deimantai eina čia.
Tas pats čia A eina čia D eina čia B eina čia.
Taigi super greitai look-up, ir jei atsitiktų paleisti į bylos
kur jūs turite susidūrimai, du žmonės su tuo pačiu pavadinimu, gerai tada
Jums tiesiog pradėkite susiejimas juos kartu.
O gal jums išlaikyti juos surūšiuoti abėcėlės tvarka, o gal jūs neturite.
Bet bent jau dabar mes turime dinamiškumą.
Taigi, viena vertus, turime super greitai pastovus laikas, o natūra linijinio laiko
dalyvauja, jei šių susijusių sąrašus pradėsite gauti šiek tiek ilgai.
>> Taigi šis kvailas natūra, prieš kelianti pokštas metų.
Tuo CS50 hack-a-Thon, kai studentai patikrinti,
kai TF arba CA kasmet mano, kad tai juokinga taikstytis
Kaip ši ženklas, kur jis tiesiog reiškia, kad jei jūsų vardas prasideda A,
eiti šiuo keliu.
Jei prasideda jūsų vardas su B, eikite this-- Gerai,
tai juokinga gal vėliau semestrą.
Bet yra ir kitas būdas tai padaryti, per daug.
Sugrįžk, kad.
>> Taigi ten ši struktūra.
Ir tai yra mūsų paskutinis struktūra šiandien
kuri yra kažkas vadinamas Trie.
T-R-I-E, kurioje tam tikrų priežasčių yra trumpas už išimti, bet tai vadinama Trie.
Taigi Trie yra dar vienas įdomus amalgama iš šių idėjų daug.
Tai medis, kurį mes matėme anksčiau.
Tai nėra dvejetainis paieškos medis.
Tai medis bet vaikų skaičių, tačiau kiekvienas iš A TRIE vaikams
yra masyvas.
AN dydis masyvas, tarkim, 26 ar gal 27 Jei norite paremti per brūkšnelį vardai
arba kabutes Liaudies pavadinimus.
>> Ir taip, tai yra duomenų struktūra.
Ir jei jums atrodo iš viršaus į apačią, pavyzdžiui, jei jums
ieškoti viršuje mazgas ten, M, yra nukreipta į kairiausias dalykas ten,
kuris yra, tai A, X, W, E, L, L. Tai tik duomenų struktūra, kad savavališkai
yra saugoti žmonių vardus.
Ir Maksvelo yra saugomi tik po iš masyvo kelias masyvo masyvo.
Bet kas nuostabu maždaug Trie yra kad nors susietą sąrašą ir net
masyvas, geriausia, ką kada nors Dotarłeś yra linijinis laikas arba logaritminė laikas ieškote
nors paimtumėte.
Šiame duomenų struktūros TRIE, jei mano duomenų struktūra turi vieną vardą į jį
ir aš ieškau Maxwell, aš ketina jį rasti gana greitai.
Aš tiesiog ieškoti "M-A-X-W-E-L-L. Jeigu ši duomenų struktūra, priešingai,
jei N yra milijonai, jei yra milijonas vardai šios duomenų struktūros,
Maksvelo vis dar bus aptinkamą po tik M-A-X-W-E-L-L
žingsniai.
Ir David-- D-A-V-I-D žingsniai.
Kitaip tariant, statant duomenų struktūra, kad tai
gavo visų šių matricos, kurie visi patys remti laisvą prieigą,
Galiu pradėti ieškoti up people-ųjų vardas, naudojant laiko tai sumą
proporcingas ne jų skaičių dalykų į duomenų struktūrą,
kaip milijoną esamos pavadinimus.
Suma laiko užtrunka mane rasti M-A-X-W-E-L-L šioje duomenų struktūros yra
proporcingas ne su dydis duomenų struktūros,
bet vardo ilgio.
Ir realistiškai pavadinimai mes ieškome iki
niekada bus iš proto ilgai.
Gal kas nors turi 10 charakterį pavadinimas, 20 simbolių pavadinimą.
Tai tikrai baigtinis, tiesa?
Yra žemėje žmogaus, kuris turi ilgiausią galimą vardą,
bet pavadinimas yra pastovus vertė ilgis, tiesa?
Ji neturi skirtis bet prasme.
Taigi, tokiu būdu, mes su pasiekti duomenų struktūrą
kad yra pastovus laikas ieškoti-up.
Ji imasi tam tikrų veiksmų priklausomai nuo įvesties ilgio,
bet ne vardo skaičių duomenų struktūrą.
Taigi, jei mes dvigubai vardų skaičių Kitais metais iš milijardo iki dviejų milijardų,
išvada Maksvelo ketina imtis tą patį skaičių iš septynių žingsnių
jį surasti.
Ir taip mes, atrodo, pasiekė Mūsų Gralis bėgančio laiko.
>> Taigi kelių greitų pranešimų pora.
Viktorina nulis artėja.
Daugiau apie tai nuo kurso tinklalapyje per ateinančius porą dienų.
Pirmadienio lecture-- Tai šventė čia Harvardo pirmadienį.
Tai ne New Haven, todėl mes radote klasę
New Haven už paskaitą pirmadienį.
Viskas bus filmuojami ir transliuojamas, kaip įprasta,
bet tegul galų šiandien su 30 sekundžių klipą
vadinami "Deep Thoughts" iki Daven Farnham, kuris
įkvėpė pernai šeštadienį Night Live'S "Deep Thoughts"
Jack ranka, kuri dabar turėtų prasmės.
>> Filmas: Ir dabar "," Deep Mintys "pagal Daven Farnham.
Hash lentelę.
>> GARSIAKALBIS 1: Gerai, kad viskas dabar.
Mes jus pamatyti kitą savaitę.
>> Doug: Norėdami pamatyti kaip tai veikia.
Taigi leiskite pažvelgti, kad atrodo dabar.
Taigi čia mes turime nerūšiuotas masyvo.
>> IAN: Doug, galite eiti į priekį ir iš naujo paleisti tai tik vieną sekundę, prašau.
Gerai, kameros valcavimo, todėl veiksmai, kai būsite pasiruošę, Doug, gerai?
Doug: Gerai, tai kas mes turime čia yra pramaišiui su masyvo.
Ir aš spalvos visus elementus raudona rodo, kad ji yra, iš tikrųjų,
nerūšiuotus.
Taigi priminti, kad pirmas dalykas, kurį mes darome yra mes rūšiuoti kairįjį pusę masyvo.
Tada mes rūšiuoti teisę pusė masyvo.
Ir Ya-DA, J.-DA, J.-doje, mes jas sujungti kartu.
Ir mes turime visiškai rūšiuotą masyvo.
Štai kaip sujungti rūšiuoti veikia.
>> IAN: Ei, Ei, Whoa, supjaustyti, supjaustyti, supjaustyti, supjaustyti.
Doug, jūs galite ne tik Ya-DA, J.-doje, Ya-doje, jūsų kelią per merge rūšiuoti.
>> Doug: Aš ką tik padarė.
Nieko tokio.
Mes gerai eiti.
Leiskite tiesiog laikyti sukti.
Taigi bet kokiu atveju,
>> IAN: Jūs turite paaiškinti jis labiau nei tai.
Tai tiesiog nepakanka.
Doug: Ian, mes do not reikia grįžti į vieną.
Nieko tokio.
Taigi bet kokiu atveju, jei mes ir toliau su merge-- Ian, mes vidury filmavimo.
>> IAN: aš žinau.
Ir mes galime ne tik Ya-DA, J.-doje, Ya-doje, per visą procesą.
Jūs turite paaiškinti, kaip Abi šalys gauti susijungė kartu.
>> Doug: Bet mes jau ve paaiškino, kaip du sides--
>> IAN: Jūs ką tik parodė, juos šiek suliejimo masyvo.
Doug: Jie žino procesą.
Jie gerai.
Mes dingo per jį dešimt kartų.
>> IAN: Jūs tiesiog praleisti tiesiai virš jo.
Mes ketiname grįžti į vieną, jums tu negali Ya-DA, J.-da per jį.
Gerai, atgal į vieną.
>> Doug: turiu grįžti per visus skaidres?
Mano Dievas.
Tai kaip šeštą kartą, Ian.
Nieko tokio.
>> IAN: Visos dešinę.
Jūs pasiruošę?
Didysis.
Veiksmas.