[Muzikos grojimo]
>> DAVID Malan: Tai CS50.
Ir tai yra tiek pradžia ir end-- kaip literally-- beveik pabaigoje
Šešių savaitę.
>> Aš maniau aš pasidalinti Šiek tiek įdomus faktas.
Aš iškedentas tai iki iš praėjusių semestro duomenų rinkinys.
Kaip Jūs tikriausiai žinote, kad mes prašome jus kiekvieną p Formą jei jūs stebėjo internete
arba, jei jau dalyvavo asmeniškai.
Ir čia yra duomenys.
Taigi šiandien buvo labai nuspėjamas.
Bet mes norėjome išleisti šiek tiek laiko su jumis vis.
Gal kas norėtų spėlioti, kodėl šis grafikas yra toks nelygus, aukštyn žemyn, aukštyn žemyn,
taip nuosekliai?
Ką kiekvienas smailių ir latakai atstovauti?
>> AUDITORIJA: [nesigirdi]
DAVID Malan: Iš tiesų.
Ir daugiau Įdomiai, neduok Dieve, mes manome, vieną paskaitą penktadienį
tuo semestro pradžios, kad tai, ką mes matome atsitikti.
Taigi, šiandien mes įsitraukti truputį daugiau apie duomenų struktūras.
Ir duoti jums daugiau kietas psichikos modelis problemų penkių,
kuris jau nebegalioja.
Karštieji klavišai, kuriame, mes jums ranka tekstinį failą kai 100.000
plius Angliški žodžiai, ir jūs ketinate turėti
išsiaiškinti, kaip protingai juos krauti į atmintį, į RAM, naudojant kai kuriuos duomenis
struktūra pasirinkai.
>> Dabar viena iš tokių duomenų struktūrą galima būti, bet tikriausiai neturėtų būti,
gana paprasta susijęs sąrašas, kuriuos mes pristatė paskutinį kartą.
Ir susijęs sąrašas turėjo bent vienas privalumas per masyvą.
Kas vienas privalumas susijęs sąrašas, be abejo?
>> AUDITORIJA: Insertion.
>> DAVID Malan: Insertion.
Ką visa tai reiškia?
>> AUDITORIJA: Visur kartu sąrašas [nesigirdi].
>> DAVID Malan: Geras.
Taigi jūs galite įterpti elementą, kur tai norite viduryje sąrašo
nereikia maišyti nieko, kurį mes padarė išvadą, mūsų rūšiavimą
diskusijos, nėra nebūtinai yra geras dalykas,
nes tai užima daug laiko, kad iš tikrųjų juda visų šių žmonių į kairę arba į dešinę.
Ir taip su susietą sąrašą, jūs galite tiesiog paskirstyti su malloc, naujas mazgas,
ir tada atnaujinti porą pointers-- du, trys operacijos max--
ir mes galime lošimo žmogų visur į sąrašą.
>> Ką dar buvo naudingas apie susietą sąrašą?
Taip?
>> AUDITORIJA: [nesigirdi]
DAVID Malan: Perfect.
Tobula.
Tai tikrai dinamiškas.
Ir kad jūs ne įsipareigojant, iš anksto, tam tikru fiksuoto dydžio
riekė atminties, kaip norėtumėte, kad į su masyvo, nelyginant iš kurių
yra tai, kad galite skirti mazgai tik paklausa taip naudojant tik tiek vietos,
kaip jūs iš tikrųjų reikia.
Priešingai masyvo, galite netyčia skirti per mažai.
Ir tada jis tiesiog vyksta būti kaklo skausmas
perskirstyti naują matysite, kopijuoti viskas baigėsi, nemokamai seną masyvą,
ir tada pereiti apie savo verslą.
Arba, dar blogiau, jums gali skirti kelią daugiau atminties, negu jūs iš tikrųjų reikia,
ir taip jūs ketinate turėti labai retai apgyvendintos masyvą, taip sakant.
>> Taigi susietas sąrašas suteikia jums tai privalumai dinamiškumo ir lankstumo
su intarpais ir naikinimus.
Bet tikrai turi būti sumokėta kaina.
Tiesą sakant, viena iš temų, ištirti dėl viktorinos nulis
buvo iš kompromisus pora mes matėme iki šiol.
Taigi, kas yra kaina, sumokėta arba Smukimo susietą sąrašą?
Taip.
>> AUDITORIJA: Nėra operatyvioji.
>> DAVID Malan: Nėra operatyvioji.
Bet who cares?
Operatyvioji neskamba įtikinamai.
>> AUDITORIJA: [nesigirdi]
DAVID Malan: Būtent.
Jei norite, kad tikras algorithm--
ir leiskite man iš tikrųjų pasiūlyti dvejetainis paieška visų pirma, kuris
yra vienas mes naudojo gana bit-- jei nenorite turėti laisvą prieigą,
Jūs negalite padaryti, kad paprastas aritmetines rasti kaip vidurinį elementą
ir šokinėja teisę jį.
Jūs, o ne, turi pradėti nuo pradžių elementas ir tiesiškai ieškoti iš kairės
į dešinę, jei norite rasti vidurys ar bet koks kitas elementas.
>> AUDITORIJA: Tai tikriausiai užima daugiau atminties.
>> DAVID Malan: reikia daugiau atminties.
Kur yra tas, kad papildoma kaina iš atminties?
>> AUDITORIJA: [nesigirdi]
DAVID Malan: Būtent.
Šiuo atveju čia, mes turėjome susijęs sąrašas sveikieji,
ir dar mes dvigubai atminties kiekis
mums reikia iki pat saugoti šiuos patarimus.
Dabar mažiau baisi kaip Jūsų structs gauti didesni
ir jūs saugoti ne skaičius, bet gal studentas ar kitu objektu.
Bet esmė tikrai lieka.
Ir taip iš operacijų skaičius susijusios su bendrais sąrašais buvo vadinami
buvo didelis O n-- linijinių.
Dalykų, pavyzdžiui, įterpiant ar paieškos arba išbraukta atveju elementas
atsitiko pačioje pabaigoje sąrašas, ar jis rūšiuojami ar ne.
>> Kartais jūs galite gauti pasisekė ir taip apatinės vertinimo šias operacijas
Taip pat gali būti pastovus laikas, jei esate visada žiūri į pirmąjį elementą,
pavyzdžiui.
Tačiau, galiausiai, mes pažadėjome pasiekti Gralis
Duomenų struktūrų, arba kai derinimas dalį,
būdu pastovaus laiko.
Mes galime rasti elementus arba pridėti elementų arba pašalinti elementus iš sąrašo?
Pamatysime visai netrukus.
Ir paaiškėja, kad vienas iš mechanizmų mes
ketina pradėti naudoti šiandien, metinis naudojimas psl nustatyti penki,
iš tiesų yra gana pažįstamas.
Pavyzdžiui, jei tai yra krūva iš egzamino knygų, iš kurių kiekvienas
turi studento pirmas vardas ir pavardė ant jo,
ir aš juos pasiimti iš pasibaigus egzaminui pabaigoje
ir jie visi yra gana daug atsitiktine tvarka,
ir mes norime eiti apie rūšiavimą Šie egzaminai, kad kai skirstomi
tai tik daug lengviau ir greičiau perduoti juos atgal
studentams pagal abėcėlę.
Kokie bus Jūsų instinktai būti už egzaminų, kaip šis krūva?
>> Na, jei jūs panašus į mane, jūs galite pamatyti, kad tai yra m,
todėl aš ruošiuosi tarsi pradėtas šis, jei tai yra mano stalo ar mano grindys kur
Aš skleisti dalykus out-- ar mano masyvas really--
Galėčiau įdėti visas Ms ten.
Oh.
Štai A. Taigi galėčiau įdėti As čia.
Oh.
Štai dar vienas A. Aš ruošiuosi įdėti, kad čia.
Štai Z. Štai dar vienas M. Ir taip Galėčiau pradėti uždirbti krūvas kaip šis.
Ir tada gal aš eiti vėliau ir rūšiuoti labai nitpicky-ly rūšiuoti
individualūs poliai.
Bet yra man atrodytų įėjime, kad aš ranka
ir aš norėčiau, kad kai kurie apskaičiuojami Sprendimas grindžiamas tuo įvesties.
Jei jis prasideda, padėkite jį ten.
Jei jis prasideda Z, padėkite jį ant ten, ir viskas tarp.
>> Taigi tai yra technika, kuri yra paprastai žinomas kaip hashing-- H-A-S-H-
kuris iš esmės reiškia, imant įvesties ir naudoja tą įvestį apskaičiuoti
vertė, paprastai numeris ir kad skaičius puslapis į saugojimo
konteineris, kaip masyvo.
Taigi, kitaip tariant, aš gali turėti maišos funkcija, kaip aš, mano galva,
kad jei matau kad žmogus vardas, kuris prasideda,
Aš einu į žemėlapį, kad iki nulio, mano galva.
Ir jei aš matau ką nors su Z, aš vyksta į žemėlapį, kad į 25 mano galva
ir tada įdėti, kad į paskutinis dauguma krūva.
>> Dabar, jei jūs manote apie ne mano smegenys bet C programa, ką numeriai galėtų
Jūs remtis pasiekti tą patį rezultatą?
Kitaip tariant, jei jūs turėjo ASCII simbolių A,
kaip nustatyti kas kibiras, kad pagal ją?
Jūs tikriausiai nenorite įdėti jį į kibirą 65, kuris
Būtų kaip ten be priežasties.
Kur jūs norite įdėti atsižvelgiant į jo ASCII vertės?
Kur jūs norite daryti su savo ASCII vertė sugalvoti protingesni kibirą
įdėti ją į?
>> AUDITORIJA: Minus A.
>> DAVID Malan: Taip.
Taigi minus minus specialiai 65, jei tai
kapitalas A. Arba 98, jeigu tai mažosiomis raidėmis.
Ir taip, kad leistų mums, labai paprastai ir labai aritmetiškai
įdėti kažką į panašaus kibirą.
Taigi paaiškėja, mes iš tikrųjų tai taip pat net su viktorinos.
>> Taigi jums gali prisiminti jums apibraukta jūsų Mokymo bendradarbis vardas ant viršelio.
Buvo surengta TF vardai į šias skiltis abėcėlę,
gerai, manau, tai ar ne, kai visi 80 plius mums
susirinko kitų naktį laipsnio, Paskutinis žingsnis mūsų klasifikavimo procesą
yra maišos viktorinos į big erdvė grindų ties [nesigirdi]
ir nustatyti kiekvieno asmens viktorinos iš lygiai jų TF įsakymu
pavadinimai ant viršelio, nes tada tai daug lengviau mus
ieškoti per tą tiesiniu ieškoti arba kai sumanumas natūra
už TF, norėdami surasti jo jos mokiniams "viktorinos.
>> Taigi šis nurodykite domenų idėja kad jūs pamatysite, yra
gana galinga iš tiesų yra gana banalumas ir labai intuityvus,
panašiai kaip galbūt padalinti ir valdyk buvo nulinis savaitę.
Aš pirmyn iki hackathon Prieš porą metų.
Tai buvo iš Zamyla ir pora kiti darbuotojai sveikinimo studentams
kaip jie atėjo.
Ir mes turėjome visą ryšelyje lankstymo stalai ten su vardų žymomis.
Ir mes turėjome žymos organizuotas su lyg per ten
ir ten Zs.
Ir taip vienas TFS labai gudriai rašė, kad tai instrukcijas
už dieną.
O semestro šio 12 savaitės pagaminti visiškai logiška ir visiem
žinojo, ką daryti.
Bet kuriuo metu jūs eilėje tuo pačiu būdu,
jūs įgyvendinant pats samprata maišos.
Taigi galime formalizuoti tai truputį.
Čia yra masyvas.
Jis sudarytas būti šiek tiek Platus tik vaizduoti, vizualiai,
kad mes galime įdėti stygos kažką panašaus į tai.
Ir tai masyvas Akivaizdu dydis 26 viso.
Ir dalykas yra vadinamas stalo savavališkai.
Bet tai tik menininko perdavimų kas maišos lentelės gali būti.
>> Taigi maišos lentelės dabar ruošiasi būti aukštesnio lygio duomenų struktūra.
Tuo dienos pabaigos mes pasiruošę žiūrėt kad jums
gali įgyvendinti maišos lentelę, kuri yra labai panašus į registracijos vietą eilutėje
ne hackathon panašiai kaip tai naudojamoje lentelėje rūšiavimas egzaminą knygų.
Bet maišos lentelė rūšiuoti šios aukšto lygio
koncepcija, kuri galėtų naudoti masyvą po gaubtu ją įgyvendinti,
arba ji gali naudoti ilgis sąrašą, arba net galbūt kai kurių kitų duomenų struktūros.
Ir dabar tai theme-- paėmimas kai kurios iš šių pagrindinių sudėtinių dalių
kaip masyvo ir šio pastato blokuoti dabar jų ilgio sąrašą
ir nematant kas mes galime sukurti ant tų, pavyzdžiui, sudedamųjų dalių,
į receptą, todėl vis daugiau ir daugiau įdomių ir naudingų galutiniai rezultatai.
>> Taigi su maišos lentelė mes galime ją įgyvendinti
atmintyje pavaizduotomis piktogramo-, kaip šis, bet kaip gali iš tikrųjų būti koduojami iki?
Na, gal taip tiesiog tai.
Jei TALPA visais dangteliais, yra tik kai, pavyzdžiui, 26 constant--,
už 26 raides alphabet-- Galėčiau paskambinti savo kintamas lentelę,
ir galiu teigti, kad aš ruošiuosi įdėti char žvaigždes ten, arba eilutę.
Taigi, tai taip paprasta, kaip tai, jei jūs nori įgyvendinti maišos lentelę.
Ir dar, tai tikrai tik masyvas.
Bet vėl, maišos Lentelėje yra dabar, ką mes
skambinti abstraktų duomenų tipą, kad tai tik tarsi konceptualus sluoksniavimasis viršuje
kažko daugiau kasdieniškas Dabar norėčiau masyvą.
>> Dabar, kaip mes einame apie sprendžiant problemas?
Na, anksčiau turėjau prabangą turėti pakankamai stalo erdvė čia
kad galėčiau įdėti viktorinos bet aš norėjau.
Taip gali eiti čia.
Zs gali eiti čia.
Ms gali eiti čia.
Ir tada aš turėjo tam tikrą papildomą erdvę.
Bet tai iš kodų bitų dešinėje dabar, nes šioje lentelėje, jei aš tikrai
maniau apie tai, kaip masyvo, yra tik bus kai kurių fiksuoto dydžio.
>> Techniškai, jei aš traukti iki kito studento viktorina
ir pamatyti, oi, tai asmens vardas prasideda A irgi
I rūšies norite jį ten.
Bet kaip tik aš jį ten, jei ši lentelė tikrai atstovauja masyvą,
Aš ruošiuosi būti svarbūs ar clobbering kas šio studento viktorina yra.
Teisė?
Jei tai yra masyvas, tik vienas dalykas gali eiti į kiekvieną iš šių ląstelių arba elementais.
Ir taip aš tipo turi rinktis.
>> Dabar anksčiau aš tipo apgaudinėjama ir padarė tą ar I
tiesiog rūšies sudėti jiems vienas virš kito.
Bet kad nesiruošia skristi kodą.
Taigi, kur galėčiau įdėti Antroji studentas, kurio vardas
yra, jei viskas, ką aš turėjo tai galima lentelės vietos?
Ir aš naudojamas tris lizdus ir jį atrodo ten tik keletą kitų.
Ką galėtumėte padaryti?
AUDITORIJA: [nesigirdi]
DAVID Malan: Taip.
Gal galime tiesiog laikyti jį paprasta.
Teisė?
Jis netelpa, kur aš noriu jį.
Taigi, aš ruošiuosi jį techniškai kur B būtų eiti.
Dabar, žinoma, aš pradedu dažų save į kampą.
Jei gaunu studentui kurio vardas tikrai B,
dabar B ketina perkelti šiek tiek į priekį, kaip gali nutikti, yep,
jei tai B, dabar jis turi eiti čia.
>> Ir todėl tai labai greitai gali tapti problemiškas,
bet tai technologija, kuri iš tikrųjų yra nurodytas kaip linijinis zondavimo,
kuriuo jūs tiesiog laikyti savo masyvas būti išilgai geležinkelio linijos.
Ir jūs tiesiog rūšies zondas arba apžiūrėkite kiekvieną turimą elementą
ieško prieinamo vietoje.
Ir kaip tik jūs rasite vienas, jūs palikite jį ten.
>> Dabar kaina mokama dabar Šio sprendimo yra kas?
Mes turime fiksuotą dydį masyvo, ir kai aš įdėti pavadinimus
į jį, bent jau iš pradžių, o kas chronometražas įterpimą
už išleidimą studentų pažangumą viktorinos į tinkamus kibirus?
Big O ką?
>> AUDITORIJA: n.
DAVID Malan: Girdėjau didelis O n.
Ne tiesa.
Bet mes erzinti išskyrus kodėl vos akimirką.
Ką dar gali būti?
>> AUDITORIJA: [nesigirdi]
DAVID Malan: Ir leiskite man tai padaryti vizualiai.
Taigi tarkime tai yra raidė S.
>> AUDITORIJA: Tai vienas.
DAVID Malan: Tai vienas.
Teisė?
Tai masyvas, kuris reiškia, kad turime laisvą prieigą.
Ir jei mes galvojame apie tai kaip nulio ir tai, kaip 25,
ir mes suprantame, kad, oh, čia mano indėlis S,
Aš tikrai gali konvertuoti S, ASCII simbolių,
su atitinkamu numeriu nuo nulio iki 25
ir tada iš karto padėkite jį, kur jis priklauso.
>> Bet, žinoma, kaip tik aš gauti Antrasis asmuo vardas arba B arba C
galiausiai, jei aš naudojamas linijinis zondavimo kaip mano sprendimas,
chronometražas įterpimo blogiausiu atveju
iš tikrųjų vyksta pavesti į ką?
Ir aš išgirsti čia teisingai anksti.
AUDITORIJA: [nesigirdi]
DAVID Malan: Taigi n tiesų kartą turite pakankamai didelį duomenų rinkinį.
Taigi, viena vertus, jei Jūsų masyvas yra pakankamai didelis
ir jūsų duomenys yra tik keletas pakankamai, jūs gauti šią nuostabią pastovų laiką.
Bet kaip tik jūs pradedate vis daugiau ir daugiau elementų,
ir tik statistiškai gausite daugiau žmonių su raide
Kaip jų pavadinimas arba raidė B, tai galėtų sąlygoti
išsigimti į kažką daugiau linijinių.
Taigi ne visai tobulas.
Taigi galėtume padaryti geriau?
>> Na, kas buvo mūsų sprendimas prieš kai mes
nori turėti daugiau dinamiškumo, nei kažkas panašaus masyvo leidžiama?
AUDITORIJA: [nesigirdi]
DAVID Malan: Ką mes pristatome?
Taip.
Taigi susietas sąrašas.
Na, pažiūrėkime, ką susieti sąrašas gali padaryti už mus, o ne.
Na, leiskite man pasiūlyti, kad mes atkreipti paveikslėlį taip.
Dabar tai yra kitoks Vaizdas iš pavyzdį
iš skirtingų teksto, iš tikrųjų, kad iš tikrųjų, naudojant iš dydžio 31 masyvo.
Ir tai autorius tiesiog nusprendė maišos stygos
nėra pagrįstas to asmens vardų, bet remiantis jų gimtadienių.
Nepriklausomai nuo to mėnesio, jie suprato jei jūs gimė pirmasis mėnuo
arba visą mėnesį 31., autorius pradės koduoti remiantis tos vertės,
taip išplito pavardes iš šiek tiek daugiau nei tik 26 taškus gali leisti.
Ir galbūt tai šiek tiek daugiau vienodos nei eiti su abėcėlės raidėmis,
nes, žinoma, tikriausiai daugiau žmonių pasaulyje su pavadinimais
kurie prasideda ne tikrai kai kurios kitos abėcėlės raidės.
Tai gal tai yra mažai vienodesnis, darant prielaidą,
vienodas paskirstymas kūdikių apsaugai per mėnesį.
>> Bet, žinoma, tai dar netobulas.
Teisė?
Kilo susidūrimų.
Keli žmonės tai duomenų struktūra yra vis dar
turintys tą pačią gimimo bent esate, nepriklausomai nuo mėnesio.
Bet kuo čia dėtas autorius padarė?
Na, atrodo, kad mes turime įvairių kairėje pusėje vertikaliai nubrėžtos,
bet tai tik menininko perdavimų.
Nesvarbu, kokia kryptimi jums atkreipti masyvą, ji vis dar masyvas.
Kas tai yra ir, matyt, masyvas?
>> AUDITORIJA: Susijęs sąrašas.
>> DAVID Malan: Taip.
Atrodo, kad tai masyvas susijęs sąrašą.
Taigi dar kartą, prie šio punkto rūšiuoti naudojant šias duomenų struktūras dabar
kaip ingredientų daugiau Įdomios sprendimai,
galite visiškai imtis esminis, kaip ir masyvo
ir tada imtis ko nors daugiau Įdomu kaip susijęs sąrašą
ir net juos sujungti į netgi įdomiau duomenų struktūra.
Ir iš tiesų, tai taip pat būtų vadinamas maišos lentelę,
kuriuo masyvas tikrai maišos lentelės,
bet kad maišos lentelė turi grandinės, taip sakant,
kad gali augti arba trauktis remiantis skaičius elementų norite įterpti.
>> Dabar, atitinkamai, kas veikimo laikas dabar?
Jei aš noriu įdėti ką nors kurio gimtadienis yra spalio 31,
Kur jis ar ji eiti?
Gerai.
Pačioje apačioje, kur ji sako 31.
Ir tai puikiai.
Tai buvo pastovus laiko.
Bet kas, jei mes pastebėjome, kad kas nors kurio gimtadienis, pažiūrėkime,
Spalio, lapkričio, gruodis 31?
Kur yra jis ar ji ketina eiti?
Tas pats dalykas.
Antras žingsnis, nors.
Štai pastovus nors ar ne?
Gerai.
Šiuo metu ji yra.
Tačiau bendruoju atveju, kuo daugiau žmonių mes pridėti,
probabilistically, mes ketiname gauti vis daugiau ir daugiau susidūrimų.
>> Dabar tai yra mažai geriau, nes techniškai
dabar mano grandinės gali būti blogiausiu atveju, kiek laiko?
Jei aš įdėti n žmones į tai daugiau sudėtingos duomenų struktūros, n žmonių,
blogiausiu atveju tai bus n.
Kodėl?
>> AUDITORIJA: Nes jei visi turi tą pačią gimtadienį,
jie ketina būti viena eilutė.
DAVID Malan: Perfect.
Jis gali būti šiek tiek nenatūralu, bet tikrai, blogiausiu atveju,
jei visi turi tą pačią gimtadienio, atsižvelgiant įėjimai turite,
jūs ketinate turėti masiškai ilgos grandinės.
Ir taip, gal ji yra skambinti maišos lentelę, bet tikrai tai
tiesiog masinis susijęs sąrašas su visa partija sugaišto erdvėje.
Bet apskritai, jei mes manome, kad bent gimtadieniai uniform--
ir tai tikriausiai yra ne.
Aš padaryti, kad iki.
Bet jei mes manome, už Diskutuojant
, kad jie yra, tada Teoriškai, jei tai vertikalus atstovavimas
masyvo, gerai tada tikiuosi jums ketina gauti grandines yra, jūs žinote,
grubiai tas pats ilgis, kai kiekviena tai rodo mėnesio dieną.
>> Dabar, jei yra 31 dienų per mėnesį, tai reiškia, kad mano važiavimo laikas tikrai
yra didelis O n virš 31, kurie jaučiasi geriau nei linijinių.
Bet kas buvo vienas iš mūsų įsipareigojimai porą savaičių
prieš, kai ji atėjo į išreikšdami chronometražas algoritmą?
Tiesiog pažvelgti tik aukštos užsakymo laikotarpiu.
Teisė?
31 yra tikrai naudinga.
Bet tai vis dar didelis O n.
Bet viena iš temų, Problemos nustatyti penki
bus į pripažinti, kad absoliučiai,
asimptotiškai, teoriškai tai duomenų struktūra
yra ne geriau nei tiesiog vienas masinis susijęs sąrašas.
Ir iš tiesų, o blogiausiu atveju, tai maišos lentelė gali išsigimti į tai.
>> Bet ir realiame pasaulyje, su mumis žmonės kad pačių Mac ar PC ar kas
ir veikia realiame pasaulyje Programinė įranga realiais duomenimis,
kuris algoritmas ketinate patinka?
Vienas, kad mano klasės veiksmų ar vienas, kad mano n padalytą 31 žingsnių
radote duomenų lapą arba ieškoti šiek tiek informacijos?
Aš turiu galvoje, absoliučiai 31 markių realiame pasaulyje skirtumas.
Tai 31 kartų greičiau.
Ir mes, žmonės, esame tikrai ketina vertinu.
>> Taigi realizuoti dichotomiją ten tarp tikrųjų
kalbėti apie dalykus, teoriškai ir asimptotiškai, kurie tikrai
turi vertę, kaip mes matėme, bet ir realiame pasaulyje,
jei jums rūpi tik darau žmogaus laimingas bendrųjų sąnaudų,
jums gali labai gerai norite priimti Aplinkybė, kad taip, tai yra linijinė,
bet tai 31 kartų greičiau nei linijinis gali būti.
Ir dar geriau, mes ne tik turime kažką daryti savavališkai kaip gimimo data,
galėtume išleisti šiek tiek daugiau laiko ir sumanumas
ir galvoti apie tai, ką mes galime padaryti, teikiama asmens vardas, o gal
jų gimimo sujungti tuos ingredientai išsiaiškinti kažką
kad tai tikrai daugiau vienodas ir mažiau nelygus,
taip sakant, nei šioje nuotraukoje Šiuo metu rodo, kad gali būti.
Kaip galėtume įgyvendinti šį kodą?
Na, leiskite man pasiūlyti, kad mes tiesiog pasiskolinti sintaksę mes
naudoti porą kartų iki šiol.
Ir aš ruošiuosi apibrėžti mazgas, kuris vėl
yra bendrinis terminas, tik kai konteineris tam tikrą duomenų struktūrą.
Aš ruošiuosi pasiūlyti styginių vyksta ten.
Bet mes ketiname pradėti vartoti tie mokymai ratams dabar.
>> Ne daugiau CS50 biblioteka tikrai, nebent norite, kad
jį naudoti savo galutinę Projektas, kuris yra gerai,
bet dabar mes ketiname atsitraukti užuolaidų ir sako, kad tai tik char žvaigždė.
Taigi žodžio ten bus asmens vardą atitinkama.
Ir dabar aš turiu ryšį čia į kitą mazgą
todėl, kad jie atstovauti kiekvienas mazgų
grandinėje, potencialiai Susietos sąrašą.
>> O dabar kaip man deklaruoti Pati maišos lentelės?
Kaip man deklaruoti visą šią struktūrą?
Na, tikrai, panašiai kaip aš rodyklę buvo skirta tik pirmojo elemento sąrašo
prieš panašiai galiu tik pasakyti, Aš tiesiog reikia rodykles krūva
įgyvendinti šią visa maišos lentelę.
Aš ruošiuosi masyvą vadinama lentelė maišos lentelė.
Ji ketina būti iš dydžio pajėgumo.
Štai kiek elementų galite pritaikyti jį.
Ir kiekvienas iš šių elementų šioje masyvas bus mazgas žvaigždė.
Kodėl?
Na, už šią nuotrauką, ką aš Įgyvendinant maišos lentelę kaip
efektyviai pradžia yra tik tai masyvas, kad mes nupiešiamas vertikaliai,
kiekvienas kurių kvadratų atstovauja rodyklę.
Kad tie, kurie turi nerijos per juos tik null.
Ir tie, kurie turi rodykles vyksta į dešinę
yra tikrasis rodykles į faktines mazgų, ergo įgyvendinti susijusios sąrašo pradžią.
>> Taigi čia, tada, kaip mes galime įgyvendinti maišos lentelę,
įgyvendina atskira Grupavimo.
Dabar mes galime padaryti geriau?
Visos teisės žadėjau praėjusį kartą, kad galėtume pasiekti pastovų laiką.
Ir I rūšies jums davė pastovus laikas čia,
bet tada sakė tikrai ne pastovus laikas, nes jis vis dar
priklauso nuo viso elementų skaičius
jūs įvedusi į duomenų struktūra.
Bet tarkime, mes tai padarėme.
Leiskite grįžti prie ekrano daugiau čia.
Leiskite man taip pat projektuoti tai čia, aišku, ekranas, ir tarkime, kad aš tai padariau.
Tarkime aš norėjau įdėti pavadinimą Daven į į mano duomenų struktūra.
>> Taigi noriu įterpti eilutę Daven į duomenų struktūrą.
Ką daryti, jei aš ne naudoti maišos lentelę, bet aš naudoju
kažkas, kad yra daugiau medžių, kaip kaip šeimos medį, kur
jūs turite kai šakninio viršuje ir tada mazgai ir lapai
kad eiti žemyn ir į išorę.
Tarkim, kad aš norite įterpti Daven s
į tai, kas šiuo metu tuščias sąrašas.
Aš ruošiuosi daryti taip: aš tikiu, sukursime mazgas šios šeimos
medis-kaip duomenų struktūra, kad atrodo mažai, kaip šis, iš kurių kiekvienas
stačiakampiai yra, tarkim, Dabar 26 elementų jį.
Ir kiekvienas iš ląstelių šiame masyve vyksta
atstovauti abėcėlė laišką.
>> Tiksliau, aš ruošiuosi laikyti tai, tada B, tada C, tada D,
tai vienas čia.
Taigi tai vyksta iš tikrųjų atstovauti laišką D.
Bet įterpti visi Daven s pavadinimas, man reikia padaryti šiek tiek daugiau.
Taigi, aš pirma nueiti į maišos, taip sakant.
Aš einu žiūrėti pirmą raidę į Daven s, kurios yra akivaizdžiai D,
ir aš ruošiuosi skirti mazgas, kuris atrodo
kaip this-- didelį stačiakampį didelis kad tilptų visą abėcėlę.
>> Dabar D daroma.
Dabar A. D--V-E-N yra įvartis.
Taigi, dabar, ką aš ruošiuosi padaryti tai.
Kai tik aš pradėjau D pranešimą nėra žymeklis ten.
Tai šiukšlių vertybes metu, ar galiu inicijuoti ją nuliui.
Bet leiskite man nesustoti su šis pastatas medis idėja.
Leiskite skirti dar vieną iš šių mazgai, kad turi 26 elementų į jį.
>> Ir žinote ką?
Jei tai tik atminties mazgas kad Aš sukūriau su malloc, naudojant konstrukto
kaip mes netrukus pamatysite, Aš ruošiuosi daryti this--
Aš ruošiuosi daryti rodyklę nuo dalykas, kad atstovauja D žemyn
į šią naują mazgas.
Ir dabar, pirmą kartą šalia raidė Daven pavadinimas,
V-- D--V-- aš ruošiuosi eiti į priekį ir atkreipti kito mazgo, kaip tai,
pagal kurią, "V elementai čia, kuris mes burtai instance-- oi.
Mes ne atkreipti ten.
Jis ketina eiti čia.
>> Tada mes einame manau, kad toks V.
Ir tada žemyn čia mes ketiname indekso žemyn iš V į ką mes atsižvelgsime E.
Ir tada iš čia mes ketiname eiti į vieną iš šių mazgų čia.
Ir dabar mes turime atsakyti į klausimą.
Man reikia kažkaip nurodyti, kad mes į eilutės Daven pabaigoje.
Kad galėčiau tiesiog palikite jį niekiniu.
>> Bet kas, jei mes turime Daven s vardas, pavardė, taip pat, kuris
yra, kaip mes sakė, Davenport?
Taigi ką daryti, jei Daven yra realiai substring,
kur kas ilgesnį prefiksą eilutes?
Mes negalime tiesiog nuolat pasakyti nieko nevyksta
ten, nes mes galime niekada įterpti kaip Davenport žodį
į šią duomenų struktūrą
>> Taigi, ką mes galime padaryti, o ne yra gydyti kiekvieno iš šių elementų
kaip gal turintys du elementai viduje iš jų.
Vienas iš jų yra žymeklis, iš tikrųjų, kaip aš darau.
Taigi kiekvieną iš šių dėžučių yra ne tik viena ląstelė.
Bet kas, jei top one-- Apatinė s
bus niekinis, nes nėra Davenport tik dar.
Ką daryti, jei viršutinis vienas yra keletas specialių vertės?
Ir tai bus šiek tiek Sunkutikėtis tai šis dydis.
Bet tarkime, kad tai tik varnele.
Patikrinkite.
D--V-E-N yra string Šioje duomenų struktūrą.
>> Tuo tarpu, jei aš turėjo daugiau erdvės čia aš galėčiau padaryti P-O-R-T,
ir aš galėčiau įdėti čekį mazgas kad turi raidę "T pačioje pabaigoje.
Taigi tai yra masiškai sudėtingas atrodantis duomenų struktūrą.
Ir mano rašysena tikrai nepadeda.
Bet jei aš norėjau įdėti kažką kita, apsvarstyti, ką darytume.
Jei mes norime įdėti į Dovydo, mes norime laikytis tos pačios logikos, D-A-V,
bet dabar norėčiau į kitą elementas ne iš E, bet iš I į D.
Taigi tai bus daugiau mazgų šio medžio.
Mes ketiname turėti skambučio malloc daugiau.
Bet aš nenoriu, kad pilnas netvarka šia nuotrauka.
Taigi galime vietoj pažvelgti į vieną kad buvo iš anksto suformuluota
kaip tai su ne dot, dot, dots, bet tik sutrumpintus matricas.
Tačiau kiekvienas iš mazgų Šioje medžio čia
atstovauja patį thing-- masyvas Ray dydžio 26.
>> Arba, jei norime būti tikrai teisingas dabar ką
jei kažkieno pavadinimas Apostrofs, galime
daroma prielaida, kad kiekvienas mazgas iš tikrųjų turi kaip 27 indeksų ja, o ne tik 26.
Taigi tai dabar bus duomenys struktūra vadinama trie-- T-R-i-E.
TRIE, kuris yra tariamai istoriškai protingas pavadinimas medį
kad optimizuotas paieška, kuri, žinoma,,
rašomas su I-E todėl TRIE.
Bet tai yra TRIE istorija.
>> Taigi TRIE tai medis-kaip duomenys struktūra kaip šeimos medį
kad galiausiai elgiasi kaip kad.
Ir čia yra tik dar vienas pavyzdys, visa krūva kitų žmonių vardus.
Bet klausimas dabar po ranka, kas turi
įgijome įvedant tikriausiai daugiau sudėtingas duomenų struktūra, ir vienas,
tiesą sakant, kad naudoja daug atminties.
>> Nes nors, Šiuo metu, aš tik
naudojant apie D žymeklį ir Ir V ir Es ir Ns,
Aš eikvoti daug atminties Heck.
Bet kur praleidžiu vienas šaltinis, Aš linkęs daryti įgyti atgal kitą.
Taigi, jei aš išleisti daugiau vietos, kas tikriausiai viltis?
Kad aš išleisti mažiau ką?
AUDITORIJA: Mažiau laiko.
DAVID Malan: Laikas.
Dabar kodėl gali būti?
Na, kas yra įtraukimas laikas, kalbant apie didįjį O dabar,
panašaus Daven pavadinimas arba Davenport ar David?
Na, Daven buvo penki žingsniai.
Davenport būtų devyni žingsniai, todėl būtų dar kelis žingsnius.
Davidas būtų penki žingsniai, kaip gerai.
Taigi tie konkretūs numeriai, tačiau, be abejo, nėra
viršutinė ant ilgis kažkieno vardą.
Ir iš tiesų, su šia problema rinkiniai penkių specifikacijos,
mes ketiname pasiūlyti kad tai kažkas
tai 40-kai-nelyginis simbolių.
>> Nereikėtų pamiršti, niekas neturi be galo ilgas vardas,
kuri yra pasakyti, kad iš ilgis pavadinimas ar iš eilutės ilgis būtume
turėti tam tikrą valstybinės struktūra yra neabejotinai ką?
Tai pastovus.
Teisė?
Tai gali būti didelis nuolatinis kaip 40-kažkas, bet jis yra pastovus.
Ir jis neturi priklausomybės nuo kiek kiti pavadinimai yra šioje duomenų struktūra.
Kitaip tariant, jei I norėjau dabar įterpti
Colton arba Gabriel arba Rob arba Zamyla arba Alison arba Belinda ar kitus pavadinimus
iš darbuotojų į šiuos duomenis struktūra, yra veikimo laikas
įterpti kitų pavadinimų bus ne paveikė
pagal tai, kaip ir daugelis kitų elementų duomenų jau struktūros?
Tai ne.
Teisė?
Nes mes iš tikrųjų naudoti tai daugiasluoksnis maišos lentelė.
Ir veikimo laikas bet kuris šių operacijų
priklauso ne nuo skaičiaus elementai, kurie yra duomenų struktūros
arba kad ilgainiui ketiname būti duomenų struktūros,
bet apie tai, ką konkrečiai ilgio?
>> Styginių yra įdėta, kuris tikrai daro
tai asimptotiškai pastovus LAIKĄ_ didelis O vienas.
Ir tiesą sakant, kaip tik realiame pasaulyje, tai
reiškia įterpiant Daven vardas trunka kaip penkių etapų, arba Davenport devyni
žingsniai, arba Davidas penki žingsniai.
Tai gana adyti maži rodymo laiku.
Ir, tiesą sakant, tai labai geras dalykas, ypač kai
tai nepriklauso nuo viso skaičius elementų ten.
Taigi, kaip gali mes įgyvendinti šį rūšies struktūros kodą?
Tai šiek tiek daugiau sudėtingas, bet vis tiek tai
tiesiog iš paraiškos pagrindiniai blokai.
Aš einu iš naujo mums mazgas taip:
bool vadinamas word-- ir tai būtų galima pavadinti nieko.
Bet bool atstovauja ką aš patraukė kaip varnele.
Taip.
Tai virvele pabaiga Šioje duomenų struktūrą.
>> Ir, žinoma, mazgas žvaigždė ten yra nuoroda į vaikus.
Ir, tiesą sakant, kaip tik patinka šeimos medis, jūs
būtų apsvarstyti mazgų kad kabo išjungti
iš kai kurių tėvų apačioje elementas turi būti vaikai.
Ir todėl vaikai ruošiasi būti 27 masyvas, 27. vienas
tiesiog yra už kabutes.
Mes ketiname rūšiuoti specialieji atvejai toje.
Todėl jūs galite turėti tam tikrą vardus kabutes.
Gal net brūkšnelis turėtų eiti ten, bet jūs
matyti p rinkinys 5 mes tik priežiūros apie raidžių ir kabutes.
>> Ir tada, kaip jūs atstovauti pati duomenų struktūra?
Kaip jūs atstovauti šaknis Šio TRIE, taip sakant?
Na, tiesiog norėčiau su susietą sąrašą, jūs reikia žymiklį į pirmąjį elementą.
Su TRIE tereikia vieną rodyklę į šios TRIE šaknis.
Ir iš ten galite koduoti jūsų kelią žemyn giliau ir giliau
į kiekvieno kito mazgo konstrukcijos.
Taigi tiesiog su tai gali mes, tą konstrukto.
>> Dabar Meanwhile-- Oi, klausimą.
>> AUDITORIJA: Kas bool žodis?
>> DAVID Malan: bool žodis tiesiog tai C įsikūnijimas
ką aprašiau čia, kai rėmelio
Aš pradėjau padalijant kiekvienas Array jo elementus į dvi dalis.
Vienas iš jų yra rodyklė į kitą mazgas.
Kitas turi būti kažkas panašaus į langelį
pasakyti taip, yra Žodis Daven kad baigiasi čia,
nes mes nenorime, Šiuo metu Dave.
>> Nors Dave bus teisėtas žodis, jis ne TRIE
dar.
Ir D yra ne žodis.
Ir D-nėra žodis ar vardas.
Taigi žymės rodo tik vieną kartą jums
hit tai mazgas Ankstesnis takelis simbolių
faktiškai seka, jūs įdėta.
Kad viskas bool ten daro už mus.
>> Bet kokie kiti klausimai bando?
Taip.
>> AUDITORIJA: Kas sutampa?
Ką daryti, jei turite Dave ir Daven?
DAVID Malan: Perfect.
Ką daryti, jei turite Dave ir Daven?
Taigi, jei mes įdėti, tarkim slapyvardį, už David-- Dave-- D-a-V-E?
Tai iš tikrųjų yra super paprasta.
Taigi mes tik ketina imtis keturių veiksmų.
D--V-E. Ir ką aš turiu daryti, kai aš paspauskite, kad ketvirtą mazgas?
Tik ketina patikrinti.
Mes jau gerai eiti.
Atlikta.
Keturi žingsniai.
Pastovus laikas asimptotiškai.
Ir dabar mes nurodyta, kad Dave ir Daven raišteliai Struktūros.
Taigi nėra problema.
Ir atkreipkite dėmesį, kaip buvimą iš Daven nebespėjo
imtis daugiau laiko ar mažiau laikas Dave ir atvirkščiai.
>> Taigi, ką dar mes galime padaryti dabar?
Mes naudojama ši metafora prieš iš dėklų atstovaujanti kažką.
Tačiau paaiškėja, kad kamino padėklai iš tiesų yra
demonstratyvus kitos abstrakčios duomenų type-- aukštesnio lygio duomenų struktūros
kad pabaigoje diena yra tiesiog kaip masyvo ar susietą sąrašą
ar kažkas daugiau kasdieniškas.
Bet tai įdomiau konceptualus koncepcija.
Kamino, kaip šie Dėklų čia Mather,
paprastai vadinamas tiesiog that-- kamino.
>> Ir šioje duomenų konstrukcijos tipo Jūs turite dvi operations--
turite vieną, pavadintą impulsą pridėti kažką į kaminą,
kaip pradėti kitą dėklą atgal ant kamino viršaus.
Ir tada pop, o tai reiškia, jums imtis Viršutinis dėklas off.
Bet kas svarbiausia apie šūsnis kad jis gavo šį įdomų charakteristika.
Kaip valgykloje darbuotojų yra pertvarkant padėklai kito valgio,
kas bus tiesa apie tai, kaip studentai
bendrauti su šios duomenų struktūros?
AUDITORIJA: jie ketina pop vienkartinis.
DAVID Malan: jie ketina pop vienkartinis ir, tikėkimės viršų.
Kitaip tai tiesiog rūšies kvailas pereiti visą kelią į apačią.
Teisė?
Duomenų struktūra nėra tikrai leidžia Jūs patraukti apatinį dėklą bent
lengvai.
Todėl ten tai įdomu nuosavybė į rietuvę
kad paskutinis elementas yra bus pirmasis iš.
Ir kompiuterių mokslininkai vadina tai LIFO-- trukti in, first out.
Ir jis iš tikrųjų neturi būti Įdomios programos.
Tai nebūtinai tokia akivaizdi, kaip kai kiti, tačiau jis gali, iš tikrųjų, būti naudinga,
ir ji iš tikrųjų gali būti įgyvendinta keliais skirtingais būdais pora.
>> Taigi vienas, ir tikrai, tegul man ne pasinerti į tą.
Leiskite tai padaryti vietoj.
Leiskite pažvelgti į vieną, kad beveik pačią idėją, bet tai šiek tiek teisingiau.
Teisė?
Jei esate vienas iš šių ventiliatorių berniukams arba merginos, kad tikrai patinka Apple produktus
ir jūs prabudau 03:00 išsirikiuoti tikru parduotuvėje
gauti pačią naujausią "iPhone, jūs galėjo eilę, kaip šis.
>> Dabar eilė labai sąmoningai pavadinta.
Tai linija, nes ten kai teisingumas jai.
Teisė?
Būtų rūšies čiulpti jei jūs gavo ten pirmas ne Apple Store
bet tai jūs Žemiausias dėklas, nes "Apple" darbuotojai tuomet
pop paskutinis asmuo, kuris iš tikrųjų gavo į eilutę.
Taigi kaminai ir eilėse, nors funkciškai jie Pirties same--
tai tik ši kolekcija išteklių, kad yra
augs ir shrink-- ten tai teisingumas aspektas į ją,
bent jau realiame pasaulyje, kai skrydžiai jūs naudotis
iš esmės skiriasi.
Stack-- eilė rather-- yra sakoma, kad
dvi operacijos: n eilę ir d eilėje.
Arba galite skambinti bet daug dalykų.
Bet jūs tiesiog norite fotografuoti Požiūris, kad vienas yra pridėti
ir vienas galiausiai atimant.
>> Dabar po kapotu, tiek kamino ir eilė gali būti įgyvendinta, kaip?
Mes neisime į kodą tai todėl, kad aukštesnio lygio
idėja yra tarsi labiau akivaizdu.
Aš turiu galvoje, ką žmogui daryti?
Jei aš pirmas žmogus į "Apple" Saugoti ir tai yra visą durys,
žinote, aš čia stovėti.
O kitą asmens vyksta čia stovėti.
Taigi, kas duomenų struktūra skolina pati į eilę?
>> AUDITORIJA: eilė.
DAVID Malan: Na, eilė.
Tikrai.
Ką dar?
>> AUDITORIJA: susijęs sąrašas.
>> DAVID Malan: susijęs sąrašą galite įgyvendinti.
Ir susijęs sąrašas yra gražus, nes tada jis gali augti savavališkai ilgas, palyginti
į tam tikra fiksuotą skaičių žmonių parduotuvėje.
Bet gal fiksuotas skaičius Vietų yra teisėtas.
Nes jei jie turi tik kaip 20 iPhone, pirmą dieną, o gal
jiems reikia tik jo dydis masyvo 20, tą eilę, kuri
tik pasakyti dabar, kai mes pradedame kalbėti apie šių aukštesnio lygio problemos,
galite ją įgyvendinti bet keliais būdais.
Ir ten tikriausiai tik ketina būti kompromiso erdvėje ir laike
arba tiesiog į savo kodą sudėtingumo.
>> Ką apie kamino?
Na, kamino, mes matėme per gali būti tik šie padėklai.
Ir tu gali įgyvendinti tai masyvas.
Bet tam tikru momentu, jei naudoti masyvą, kas nutiks su padėklai
Jūs bandote pribaigti?
Gerai.
Jūs tik ketina galėti eiti taip didelis.
Ir manau, kad į Mather jie realiai potinkinis toje atidarymo.
Taigi iš tikrųjų, tai beveik kaip Mather naudoja
Fiksuoto dydžio masyvas, nes galite tik
tilpti tiek daug padėklai toje atidarymo sienos žemyn žemiau žmonių kelio.
Ir taip, kad galėtų būti Sakoma, kad masyvas,
bet mes tikrai galėtų įgyvendinti, kad plačiau su susietą sąrašą.
>> Na, ką galima pasakyti apie kitą duomenų struktūros?
Leiskite atsigriebti vieną kitą vaizdinį čia.
Kažkas panašaus, kaip apie šį vieną čia?
Kodėl tai gali būti naudinga turėti ne kažkas kaip išgalvotas kaip TRIE, kuris
matėme turėjo šiuos labai didelius mazgus, kiekvienas iš kurių yra masyve?
Bet kas, jei mes darome ką nors daugiau tiesiog, kaip senosios mokyklos šeimos medį,
kiekvieno iš jų mazgai čia tiesiog saugoti numerį.
Vietoj vardo ar palikuonis tiesiog saugoti kaip šis numeris.
>> Na, žargono mes naudojame duomenų struktūros yra tiek bando
ir medžiai, kur TRIE vėlgi yra tik vienas, kurio mazgai yra matricos,
dar ką galite naudoti nuo pradinėje mokykloje
kai padarė šeimą tree-- lapai ir šaknys
Medžio ir vaikams tėvų ir jų broliai ir seserys.
Ir mes galime įgyvendinti medį, pavyzdžiui, kaip tiesiog kaip šis.
Medis, jei jį kaip mazgas, vienas šie apskritimai, kurio numeris,
jis nesiruošia turėti vienas žymeklis, bet du.
Ir kuo greičiau jūs pridedate Antrasis žymeklis, jums
iš tikrųjų gali dabar padaryti rūšiuoti iš dvimatis duomenų
struktūros atmintyje.
Panašiai kaip dvimatis masyvas, jūs galite
turėti natūra dvimačių susiję sąrašus, o tie,
kad galutinių schemas kur nėra jokių ciklų.
Tai tikrai medis su vienu senelių būdas čia ir tada
kai tėvai ir vaikai, ir vaikaičiams ir provaikaičiams.
ir kt.
>> Bet kas tikrai tvarkingas apie tai per daug, tiesiog erzinti jus su šiek tiek kodo,
priminti rekursija iš Trumpam grįžo, kuriuo
Rašydami funkciją, kuri vadina save.
Tai gražus proga įgyvendinti kažką
kaip rekursijos, nes mano, kad tai.
>> Tai medis.
Ir aš buvau šiek tiek analinis su tuo, kaip Aš įdėti skaičiais į gatvę.
Tiek daug, kad ji turi ypatingą name-- dvejetainis paieškos medis.
Dabar mes girdėjote apie dvejetainis ieškoti, bet jūs galite
dirbti atgal nuo šio dalyko pavadinimas?
Kas yra, kaip aš modelis Įterpiamas skaičiais į šio medžio?
Tai ne savavališkai.
Yra keletas modelis.
Taip.
>> AUDITORIJA: mažesnių kairėje.
>> DAVID Malan: Taip.
Mažesnių yra kairėje.
Didesnės iš jų yra dešinėje.
Toks, kad pareiškimas yra tiesa tėvų yra didesnė už jo kairiojo vaikui,
bet mažesnis negu jo dešinės vaikui.
Ir kad tik jis dar pakartotinė žodinis apibrėžimas
nes galite kreiptis, kad Ta pati logika kiekvienas mazgas
ir ji tik dugnai out, bazinį scenarijų, jei jums
bus, kai paspausite vieną iš lapai, taip sakant,
kur atostogos neturi vaikų dar.
>> Dabar, kaip gali rasti skaičių 44?
Galima būtų pradėti nuo šaknų ir pasakyti, HM.
55 yra ne 44 Taigi aš noriu eiti teisė ar aš noriu eiti į kairę?
Na, žinoma, jūs norite eiti į kairę.
Ir todėl, kaip ir telefone knyga pavyzdys dvejetainėje paieškos
plačiau.
Bet mes ją įgyvendinti Dabar šiek tiek dinamiškiau
nei masyvas gali leisti.
Ir iš tiesų, jei norite ieškoti į kodą, iš pirmo žvilgsnio, tikrai.
Atrodo, visa krūva linijų.
Bet tai gražiai paprasta.
Jei norite įdiegti funkciją vadinama paieška kurio gyvenimo tikslas
yra ieškoti vertė kaip n, sveikasis skaičius,
ir jūs išlaikė per vieną pointer-- rodyklė į šaknų mazgas,
o, tos medžio, iš kurios Jūs galite patekti visa kita,
pranešimas, kaip tiesmukai jūs galite įgyvendinti logika.
Jei medis yra niekinis, žinoma, ji nėra ten.
Tegul tik return false.
Teisė?
Jei vertus, nieko, nieko ten.
>> Kitur, jei n yra mažesnis nei medis rodyklė n-- dabar arrow n,
prisiminti įdiegėme super trumpai kitą dieną,
ir kad tik reiškia, de-nuorodą žymeklis ir pažvelgti į lauką, vadinamą n.
Taigi tai reiškia, ten ir pažvelgti į lauką, vadinamą n.
Taigi, jei n, vertė jums suteikta, yra mažiau nei į medžius sveiko skaičiaus,
kur tu nori eiti?
Į kairę.
>> Taigi pastebėsite rekursija.
Aš returning-- netiesa.
Nėra netikras.
Aš grįžti nepriklausomai atsakymą iš pokalbio su savimi, einančios
n vėl, kuris yra nereikalingas, bet tai, kas šiek tiek kitokia?
Kaip aš padaryti problemą mažesnis?
Aš einančios kaip antrą argumentas, ne iš medžio šaknis,
bet liko vaikas šioje byloje.
Taigi, aš artimųjų kairėje vaikui.
>> Tuo tarpu, jei n yra didesnis nei mazgas Aš šiuo metu ieško,
Ieškoti dešinės pusės.
Kita, jei medis yra ne niekinis, ir jei elementas ne į kairę
ir tai ne į dešinę, kas nuostabiai atvejis?
Mes iš tikrųjų nustatė, kad mazgas klausimas, ir todėl mes grąžina true.
>> Taigi mes tiesiog subraižyti paviršių dabar kai kurie iš šių duomenų struktūras.
Be problemų nustatyti penki jums ištirti jų dar toliau,
ir jums bus suteikta jūsų dizainas pasirinkimas, kaip eiti apie tai.
Ką aš norėčiau padaryti išvadą yra tik 30 antra kibinimas
kas laukia kitą savaitę ir vėliau.
>> Kaip mes begin-- laimei jums gali think-- mūsų perėjimą lėtai
iš C ir mažesnė pasaulyje lygis įgyvendinimo informacija,
į pasaulį, kuriame mes galime imtis už savaime suprantama, kad kažkas pagaliau
įgyvendinti šiuos duomenis struktūros mus
ir mes pradėsime suprasti realiame pasaulyje, priimdama įgyvendinimo
interneto programos ir svetainės apskritai
taip pat ir labai saugumas Poveikis kad mes tik
pradėjo kapstyti paviršių.
Štai kas mūsų laukia į dienų į priekį.
>> [VIDEO PLAYBACK]
>> -Jis Atėjo su žinia, su protokolu visa savo.
Jis atėjo iš žiaurus pasaulis ugniasienės, negailestinga planeta maršrutizatoriai,
ir pavojai daug blogesni nei mirtis.
Jis greitas.
Jis stiprus.
Jis TCP / IP, ir jis gavo savo adresą.
"Warriors tinkle".
[END VIDEO PLAYBACK]
DAVID Malan: kitą savaitę.
Pamatysime jums tada.
[VIDEO PLAYBACK]
-O Dabar, "Deep Thoughts" iki Daven Farnham.
-David Visada prasideda paskaitos, kurių: "Gerai."
Kodėl gi ne, "Štai sprendimas į šią savaitę, problemą, "
arba "Mes suteikiame jums visiems?"
[Atsakyti]
[END VIDEO PLAYBACK]