DAVID Malan: Olgu. Tere tulemast tagasi CS50. See on algus 8. nädalal. Ja meenutada, et probleem set 5 lõppes koos natuke väljakutse. Seega eeldades, et sa tagasi kõik oma õpetamise stipendiaatide ja KA fotod aastal card.raw fail, teil on õigus et nüüd kõik need inimesed, ja üks õnnelik võitja kõnnime koju ühe need asjad, hüpe motion seade, mida saab kasutada lõpliku projekte, näiteks. 

Seda igal aastal viib natuke tontlikkus. Ja nii ma mõtlesin, et ma teha, on jagada teiega mõned märkused, mis on läinud edasi ja tagasi üle töötajate nimekirja lõpus. Näiteks just eelmisel õhtul, tsiteerin lõppeb, ühest töötajate kohal, "Mul oli just üliõpilane knock mu uksele pildistama minuga. Varitsejad, ma ütlen teile. "Alustasin üsna kirjeldav ja siis kolisime edasi, tund aega hiljem, "Mul oli üliõpilane ootab mind pärast jagu ja ta oli kõik meie nimed ja fotod mõned paberilehed. "Olgu. Nii organiseeritud, kuid mitte kõik, et jube veel. 

Siis: "Ma olin linnast välja sel nädalavahetusel, ja kui ma sain tagasi, seal oli üks minu magamistoas. "[naer] DAVID Malan: Järgmine tsitaat personal liige, "õpilane tuli minu maja Somerville kell 4:00 hommikul. "Next personal "Sain oma hotell San Francisco ja õpilane ootas mind fuajees kolm DSLRs. " Tüüpi kaamera. "Ma ei ole isegi töötajate see semester, kuid õpilane murdis mu majja see hommikul ja registreeritakse kogu asi Google klaas. "Ja siis lõpuks, "Vähemalt 12 inimest olid innukalt ootavad mind, kui ma välja sain limusiin, ja siis ma ärkasin. "Olgu. Nii hulgas fotod, kuna te mäletan, on see mehe siin, kes te tunneksite kui Milo Banana, kes elab Lauren Carvalho, meie peas õpetamine Fellow. Milo, Milo, tule siia poiss. Milo. Milo. Mind you, ta kannab Google Klaas, nii näitame teile, see kõik pärast. Nii et see on Milo kui soovite pildistada koos temaga hiljem. Kui soovite, et vaadata läbi kell publik olemas. OK. See on hea materjali. Noh, Milo Banana. Oh, ära tee seda. 

[Naer] 

OK. Nii sõna siis mis ootab, sest kui me hakkame üleminekust Sel nädalal konkreetsemalt alates C käsurea keskkond PHP ja JavaScript ja SQL ja HTML ja CSS veebipõhine keskkond, me oleme varustada teile kõik rohkem teadmisi võimalikke lõplikke projekte. Toward Selleks on muidugi traditsioon seminaride mis olete tangentsiaalne teemasid et muidugi. Väga palju on seotud programmitöö ja app areng ja nii edasi, kuid pruugi uurivad Loomulikult enda õppekava. 

Nii et kui sa võiksid olla huvitatud ühe või rohkem käesoleva aasta seminaride registreerida cs50.net/seminar. On vanemad seminarid kell cs50.net/seminars. Ja nimekirja seni sel aastal on hämmastav Web Apps Ruby on Rööpad, mis on alternatiiviks keele PHP. Computational Linguistics. Sissejuhatus iOS, mis on platvorm, mida kasutatakse iPhone ja iPad arengut. JavaScript Web Apps, me katame , kuid selles seminar, lähete üksikasjalikumalt. 

Hüpe Motion, nii et me tegelikult mõned Meie sõbrad hüpe Motion, ettevõte ise, meiega liituda. Homme, tegelikult anda käed-seminar, kui Teile huvi pakkuda. Meteor.js, alternatiivse tehnika kasutades JavaScript ei ole brauser, kuid server. Node.js, mis on väga palju Seega märgib samuti. Sleek Android Design. Android on väga populaarne alternatiiv iOS ja Windows Phone ja muude mobiilsete platvormide. Ja Web Security Active Defense. 

Nii et tegelikult, kui soovite osalema selles, andke teha selle teadmiseks. Oleme väga hea meel öelda, et meie sõprade hüpe Motion, mis on startup - see seade tõesti lihtsalt tuli välja paar kuud tagasi - on lahkelt annetatud 30 selliste seadmete et klassis on palju õpilasi, kui soovite laenata riistvara poole semestri lõpus ja seda kasutada tegelik lõplik projekt. Nad toetavad mitmeid keeli. Ükski neist C, ükski neist PHP, nii viia ühte või mitut neist seminarid võib osutuda huvi. Ja kõik nad on filmitud Juhul, kui Teil ei ole võimalik isiklikult kohale ilmuda. Ajakava kuulutatakse kaudu emaili me tahkuma toad. 

Ja lõpuks, kui sa lähed projects.cs.50.net on see veebileht meil säilitada igal aastal, et me kutsume inimesed ühendusest, õppejõud, osakondade töötajad, ja nii aastal väljaspool CS50 et ettepaneku projektiideid. Asjad huvi rühmades. Asjad huvi osakonnad. Nii et ärge keerake seal kui sa oled hädas määramatuse, et mida sa ise tahaks tegeleda. 

Nii eelmisel korral tutvustasime väidetavalt keerulisem andmestruktuur kui olime näinud nädalat varem. Olime kasutades massiive päris õnneks on kasulik, kui lihtsustatud andmete struktuuri. Siis kehtestati need, mis muidugi on seotud nimekirju. Ja mis oli üks põhjusi kehtestatakse käesoleva andmete struktuur? Jah? Mis see on? 

Publik: Dynamic suurus. 

DAVID Malan: Dynamic suurus. Nii et massiivi, pead tean oma suurust ette kui sa jaotada see. In seotud nimekirja, siis ei ole pead teadma, et. Sa võid malloc või üldisemalt eraldada täiendavaid sõlm, nii et rääkida, iga kord, kui soovite lisada rohkem andmeid. Ja sõlm pole etteantud tähendus. See on lihtsalt üldine termin, mis kirjeldab mingi konteiner, et me oleme kasutades meie andmestruktuur salvestada mõned punktis huvi, mis käesolevas juhul juhtub olema täisarvud. 

Aga seal on alati kompromiss. Nii saame dünaamiline suurused andmed struktuur, kuid millise hinnaga me maksma? Mis on negatiivsed ahelloendid? Jah? 

Publik: nõuab rohkem mälu. 

DAVID Malan: See nõuab rohkem mälu, kuidas täpselt? 

Publik: [kuuldamatu]. 

DAVID Malan: Täpselt. Nüüd oleme suunanäitajaks asumist lisamälu, mida me varem ei pea, sest ära massiiv, muidugi, on see, et kõik on terviklik, tagasi kuni seljad, mis annab teile muutmälu. Sest just abil nurksulg märke või rohkem tehniliselt pointer aritmeetika, väga lihtne Lisaks saate juurdepääsu mis tahes elementide konstantse ajaga. Ja tegelikult, see on omamoodi vihjab teine ​​hind, mida me maksame koos seotud nimekirja. 

Mis juhtub sõiduaega midagi Search, kui ma tahan leida mingi väärtus ja sees on seotud nimekirja? Mis minu tööaeg muutunud? Big O n. Kui see on sorteeritud? Mida teha, kui andmestruktuur on järjestatud? Kas ma saan teha paremini kui suur O n otsida? Ei, sest halvimal juhul võib see väga hästi välja sorteerida, aga number otsite võib olla suur. See võib olla number 100, mis võib juhtuda, et kõik tee lõpus. Ja kuna saad avada ainult investeerimisriskiga nimekiri selles rakendamist viis oma esimese sõlme, oled ikka omamoodi õnne. Sul on läbida kogu asja Kogu aeg, et leida et suur väärtus nagu 100. Või kas see on isegi mitte seal. 

Nii et me ei saa teha seda, mida algoritm andmed struktuur, mis näeb välja nagu see on? Me ei saa seda teha binaarne otsing, sest binaarne otsing nõutav, et meil oli muutmälu. Me võiksime lihtsalt hüpe asukoht asukoha ilma järgima need leivapuru kujul kõiki neid näitajaid. 

Nüüd, kuidas me rakendada seda? Noh, kui me läheme ekraan siin, kui saame kiiresti implementeerid neid andmeid struktuur - mu käekiri pole veel kõik, mis suur siin, aga me proovime. Nii typedef struktuure, ja mis ma tegin soovite helistada seda asja siin? Sõlme. Nii et ma saan meile hakkas. Ja nüüd, mis peab olema sees andmestruktuuri et üksikult seotud nimekirja? Kuidas paljudes valdkondades? 

Nii kaks. Üks on päris lihtne. Nii int n. Ja me võiksime kutsuda n midagi tahame, kuid see peaks olema int kui me oleme rakendamisel, mis on seotud nimekirja ints. Ja nüüd, mida teeb teine valdkonnas olema? Struct sõlme *. Nii et kui ma teen struct tipp * ja siis ma võib helistada ka see, mida tahan, vaid lihtsalt olema selge ma helistan ta järgmisena, kui me oleme seda teinud. Ja siis ma sulen looksulg. 

Ja nüüd, kui viimane kord, Panin sõlme siin. Aga kui ma olen kuulutanud on sõlme, miks ma vaeva on nii lobise siin deklareerimisel struct sõlme *, vastandina lihtsalt sõlme * edasi? Jah? 

Publik: [kuuldamatu]. 

DAVID Malan: Täpselt. Täpselt. Kuna C tegelikult viib teid sõna otseses mõttes ja vaid näeb mõiste sõlme siia alla, siis ei saa vaadake seda siin. Nii et meil on selline ennetav avaldus siin, mis on küll rohkem paljusõnaline. Struct sõlme, mis tähendab, saame seda kasutada sees andmestruktuur. 

Ja kõrvale, sest see on muutub veidi subjektiivne nüüd, star saab tehniliselt minna siin, see ei lähe siin, võib see isegi minna keskel. Me oleme vastu, stiilis juhend Loomulikult konventsioon paneb star kõrval andmed tüüp, mis antud juhul oleks struct sõlme. Aga realiseerida palju õpikuid ja online-viited, võite tõepoolest vaata seda teisel pool. Aga mõistan, et mõlemad tegelikult töö ja sa peaksid lihtsalt olema järjepidev. 

Hea küll. Nii et oli meie deklaratsioon kohta struct sõlme. Aga siis hakkasime tegema rohkem keerulisi asju. Näiteks oleme otsustanud võtta kasutusele midagi hash tabelis. Nii et siin on hash tabelis suuruse n, indekseeritud 0 peal vasakult n miinus 1 all vasakul. See võiks olla hash tabel midagi. Aga milliseid asju me räägime kuidas kasutada hash tabel? Salvestamine mis? 

Nimed. Me saaksime nimed nagu me tegime viimane kord. Ja tõesti, võite salvestada midagi. Ja me näeme seda jälle PHP ja JavaScript. Hash tabel on ilus omamoodi Šveitsi Armee nuga, mis võimaldab teil salvestada päris palju iganes sa tahad sees see, seostades võtmed väärtused. Keys väärtustega. 

Nüüd see lihtne juhtum, meie Võtmed on lihtsalt numbrid. Me rakendamisel hash tabel massiivina. Ja nii võtmed on 0, 1, 2, ja nii edasi. Ja nii meil, inimestel, otsustas viimane nädalal, et sa tead, mida, kui me oleme läheb poodi nimed, lähme lihtsalt omavoliliselt, kuid üsna mõistlikult, eeldada, et Alice, nimi, lihtsalt olla indekseeritud 0. Ja Bob, B nimi, indekseeritakse arvesse 1, ja nii edasi. Seega oli meil kaardistamise vahel sisendite mis on stringid ja räsi kohtades, kus on numbrid. 

Nii et protsess on üldiselt tuntud räsifunktsiooni ning te saate tõeliselt rakendab seda koodi. Kui ma tahtsin rakendada räsifunktsiooni mis teeb täpselt seda, mida me just kirjeldatud alates viimane kord, ma võin kuulutada funktsioon, mis võtab, kui sisend näiteks - ja teeme seda selles ekraan siin. Kui ma tahtsin rakendada hash funktsioon, ma võiks öelda, midagi sellist. 

See läheb tagasi int. See saab nimeks hash, ja see on kavatse nõustuda argumendina string, või saame olla õige nüüd, ja öelda, char *, me kutsume seda s. Ja siis kõik see funktsioon on teha, lõppkokkuvõttes on tagasi int. Nüüd, kui see, mis võiks ei ole nii selge. Ma lähen, et rakendada seda ilma moodustavad viga kontrollides kohe. Ma lihtsalt pimesi öelda, tagasi mis iganes on s sulg 0, miinus, oletame, kapitali semikooloniga. 

Täiesti katki. See ei ole täiuslik, sest üks, mis siis, kui s on null? Halvad asjad hakkavad juhtuma. Kaks, mis siis, kui esimene täht selles nimi pole suurtäht? See ei kavatse pöörduda välja ka kas. See võib olla väike täht või kirja üldse. Seega täiesti võimalik teha edusamme, kuid see on peamine idee. 

Mida me kirjeldatud eelmisel nädalal suuliselt kui lihtsalt kaardistamise protsessi Alice 0 ja Bob 1 saab väljendada kindlasti rohkem formulaically kui C toimi siin. Helistas uuesti räsi, võtab stringi sisend ja siis kuidagi ei midagi selle sisendi toota toodangut. Ei erinevalt meie musta kasti kirjeldus et me oleme kaua tehtud. Ma ei tea, kuidas see võiks olla töö all kapuuts. 

Sest probleem komplekt 6, üks väljakutseid on teil otsustada, millist on oma räsifunktsiooni olema? Mis saab olema sees, et must kast ja arvatavasti, see saab olema veidi huvitavam kui see, ja kindlasti rohkem altid viga kontroll kui selle konkreetse rakendamist. 

Kuid võib tekkida probleeme, eks ole? Kui meil on andmete struktuur, nagu see üks, mis on üks probleeme sa võid joosta rohkem aega kui sisestate rohkem nimesid hash tabel? Sa saad kokkupõrkeid, eks? Mida teha, kui teil on Alice ja Aaron, kaks inimest, kelle nimed juhtus alustada? See tekitab küsimuse, kuhu pane teine ​​selline nimi? 

Noh, sa võiksid naiivselt lihtsalt pane see kus Bob kuulub, kuid siis Bob on liiki kruvitud kui üritate sisestada oma nime kõrval ja Siin pole ruumi tema jaoks. Nii võite panna Bob kus Charlie on ja võite ette kujutada, see väga kiiresti läinud sisse natuke jama. Midagi lineaarne lõpuks, kui sa lihtsalt otsida kogu asi otsin Alice või Bob või Aaron või Charlie. 

Nii et selle asemel tegime ettepaneku, mitte ainult lineaarselt katsetamine avatud ruumid ja plopping nimed seal, me ettepaneku Kasvataja lähenemine. Hash tabelit rakendada ikka koos massiivi indeksid, kuid andmete tüüp need indeksid nüüd olid lähtekohtadeks. Näiturid mida? Näiturid seotud nimekirju. 

Sest meenutavad seotud nimekirja on tegelikult lihtsalt kursor sõlme, ja sõlm on järgmine väli ja et sõlm on järgmine väli ja nii edasi. Nii saab nüüd mõtlema selle massiivi vasakul servas hash tabelit viivad seotud nimekirja. Ära, mis on, kui saad kokkupõrge Alice ja Aaron, mida te teete Teine selline inimene? Sa lihtsalt lisada teda lõppu või isegi alguses Selle seotud nimekirja. 

Ja tegelikult, olgem lihtsalt makaron kaudu et just teine. Kus oleks kõige mõttekam? Kui ma sisestan Alice ja ta jõuab kell esimene asukoht, siis ma püüan sisestada Aaroni nimi, ja seal on ilmselt kokkupõrge, ma peaksin teda alguses on seotud nimekirja? See on see esimene asukoht, või lõpus? 

Publik: [kuuldamatu]. 

DAVID Malan: OK. Kuulsin hakanud. Miks alguses? 

Publik: [kuuldamatu]. 

DAVID Malan: OK. See on tähestikulises, et on tore. See on hea omadus. See säästab mind mõnda aega olla. Ta ei lase mul seda teha binaarne otsing, aga ma võiksid vähemalt suutma välja murda of loop kui ma mõistan, ma olen viis varem olid Aaron oleks see järjestatud seotud nimekirja. Ma ei pea raiska oma aega otsin kõik viis lõpuks. Nii et see mõistlik. Miks muidu võib soovite lisada kokkupõrkamise nime loetelu alguses? Mis see on? 

Publik: [kuuldamatu]. 

DAVID Malan: See võib võtta kaua aega saada nimekirja lõppu. Ja tegelikult, enam ja enam. Rohkem nimesid kui sisestate et alustada, seda pikem on kett ei hakka. Enam, et seotud nimekiri ei hakka. Nii et sa oled tõesti lihtsalt raiskad oma aega. Võibolla sa oled parem säilitada pidev sisestamise ajal suur O 1, poolt alati paneb põrgata nime algusega seotud nimekirja, ja mitte murettekitav, sest palju umbes sorteerimist. 

Milline on parim lahendus? See on selge. See liik sõltub sellest, mida jaotus on, mida struktuuris on nimed olete sisestamist. See ei ole tingimata Selge vastus. Aga siin jälle on disain võimalus. 

Nii me siis vaatasin seda asja, mis tegelikult on teine ​​suur võimalus p-set 6. Ja mõistma, kui te ei ole juba, Zamyla sukeldub mõlemad, hash tabelid ja katseid üksikasjalikumalt. Ja video läbikäiguks on varjatud p-set spec. See oli Prefiksipuu - T-R-I-E. Ja mis oli huvitav see oli, et sõiduaega otsivad nimi, nagu Maxwell Viimane kord oli suur O mida? Mis see on? 

Publik: tähtede arv. 

DAVID Malan arv tähti. Kuulsin kahte asja. Tähtede arv ja konstant korda. Lähme koos, et esimene. Tähtede arv. Noh, see andmestruktuur, mäletate, on nagu puu, sugupuu, iga kelle sõlmed koosnevad massiivid. Ja need massiivid on viiteid muud sellised sõlmede või muu selline massiivid puus. 

Nii et kui me tahame, et seejärel otsustada, kas Maxwell on siin, ma võiks minna esimese massiivi päris tippu puu, nn root tippu Prefiksipuu ja järgige m pointer, siis pointer, siis x, w, e, l, l. Ja siis, kui ma näen mõningaid erilisi sümbol, tähistatakse siin kolmnurk. In kood näete teeme ettepaneku, et sa rakendatakse bool, lihtsalt ütlen jah või ei, sõna peatub siin. 

Noh, kui oleme läinud M--X-W-E-L-L, tundub seitse, võibolla kaheksa, kui me läheme ühe minevikus, kaheksa samme, et teada Maxwell. Või ütleme K. Aga mäletate viimast aega, ma väita, et kui seal on realistlikult maksimaalne pikkus on Ühesõnaga, nagu 40-mõned-paaritu tähtedega maksimaalne pikkus tähendab püsiv väärtus. Nii et tõesti, jah, see on tehniliselt suur O 8 või 7 või tõesti suur O K. Aga kui seal on piiratud kate mida K võib olla, see on pidev. Ja nii see on suur O 1 juures Päeva lõpuks. 

Mitte reaalses maailmas. Mitte siis, kui sa tegelikult alustada vaadates oma kella oma programmi algust. See on absoluutselt läheb natuke aeglasem kui tõesti pidev aega üks samm. See saab olema seitse või kaheksa samme, kuid see on palju, palju parem kui algoritmi nagu suur O n, et sõltub suurusest, mis on sisse andmestruktuur. 

Märka pea siin saame sisestada miljonit rohkem nimesid sellesse andmete struktuuri, kuid kui palju samme see läheb meid leida Maxwell sel juhul? Ei ole. Ta on muutunud. Ja siiani, ma ei usu, et me oleme näinud näiteks andmete struktuuri või algoritm, mis oli täiesti mõjutanud välised käitumist niimoodi. Kuid see ei saa olla hämmastav. See ei saa olla ainus lahendus jaoks p-set 

Ja see ei ole. See ei pruugi andmed struktuur, mida peaks vajuma, sest nagu hash tabeleid kompromissiga. Mis on hind, mida maksate here? Mälu. Ma mõtlen, et see on jõle mälu. Ja sa ei saa päris näha siin, sest autor seda pilti ilmselt kärbitud kõik massiivid ja me ei näe palju on ja B-ja C-ja Q-ja Y ja Z on nendes massiivid. Aga nad on olemas. 

Kõik need sõlmed on terve rida mõned 26 või rohkem baite iga mis kujutab endast kirjas. 27 meie puhul nii, et me ei toeta ülakomade sisse lahendamist. Nii et see andmestruktuur on tõesti, tõesti tihe ja lai. Ja üksi sattuda aeglustub asju ette, või vähemalt maksab teile palju rohkem ruumi. Aga jälle, saame teha võrdlused siin. 

Meenuta aega tagasi, oleme saavutanud palju põnevam sõiduaega sorteerimine kui me kasutame Tarkvaraprojekteerimise, kuid hind pöörasime saavutada n log n ühendamist sort vaja, et me kulutame rohkem, mida ressurss? Rohkem ruumi. Meil oli vaja teisese massiivi kopeerida inimesi, just nagu tegime siin laval. Nii et taas, ei ole selge, võitjad, aga lihtsalt subjektiivne disain otsuseid teha. 

Hea küll. Niisiis, kuidas see on? Igaüks, kumb D-Hall? OK. Nii me kolmekesi tegema. Ema House. Nii see on Ema söögisaalis. Vean kihla, et kõik söögisaali olema korstnad plaate niimoodi. Ja see on tegelikult esindaja midagi me oleme ilmselt näinud juba. Me kutsusime seda sõna otseses mõttes pinu. Ja stack nii oma arvuti mälu, kus info läheb samas funktsioone kutsutakse. 

Näiteks milliseid asju minema stack suhtes mälupaigutuse oleme arutanud nädalates varem? Mis see on? 

Publik: Kõned funktsioone. 

DAVID Malan: Mul on kahju. 

Publik: Kõned funktsioone. 

DAVID Malan: Kõned funktsioone, kuid Täpsemalt, milline on sees iga need raamid? Milliseid asju? Jah. Nii kohalikud muutujad. Anytime me vajas kohalike ladustamine, nagu argument, või int I või int temp, või mis iganes kohalike muutuja, oleme olnud pannes, et korstnat. Ja me nimetame seda virna sest selle kihilisus idee. Just selline sobitab reaalsusega, kontseptsiooni kohta. 

Aga selgub, et stack saab ka vaadelda kui andmestruktuur, Alternatiivina massiiv, alternatiivne et seotud nimekirja. Midagi sisuliselt huvitavamaks mis saab veel rakendada, kasutades kas nende asju, aga see on teist tüüpi andmestruktuur toetamine, tõesti, ainult kaks tegevust. Aga sa võid lisada Kasvataja funktsioone kui need. Aga need on põhitõed - push ja pop. 

Ja idee stack on, et kui ma on siin, koos või ilma Annenberg teades, salv kõrvalmajas arvuga 9 peal. Nii lihtsalt int. Ja ma tahan, et lükata see peale andmed struktuur, mis praegu on tühi. Mõelge sellele põhja pinu. Ma tõstaks see number 9 peale korstnat, ja nüüd on see siin. 

Aga huvitav asi korstnat on see, et kui ma nüüd tahan suruda muu väärtus, nagu 17 ja ma push Selle peale virna, ma lähen tegema ainult intuitiivne asi, ma lihtsalt läheb pane see õige, kui meie, inimesed kalduks panna see peal. Aga mis on huvitav nüüd on, kuidas ma saan kell 9? Tead, ma ei ole ilma mõned pingutust. 

Mis on huvitav stack on, et projekteerimise, see on LIFO andmestruktuur. Rumal viis kirjeldada viimane esimene välja. Seega viimane number sel ajal oli 17. Nii et kui ma tahan pop midagi maha virna, see saab olla ainult 17. Nii et seal on kohustuslik järjekorras operatsioonide siin, kus viimane punkt aastal peab olema esimene välja. Seega akronüüm, LIFO. 

Miks võib see olla kasulik? Kas nende konteksti, milles soovite tahad andmestruktuuri nagu see on? Noh, see on kindlasti kasu olnud sees arvuti. Nii operatsioonisüsteemide selgelt seda objekti andmestruktuur korstnad. Me näeme ka sama mõte kui tegemist on veebilehtedel. Nii et see nädal ja järgmisel nädalal ja kaugemalgi ja kui hakkad rakendamise web lehekülgede keeles nimetatakse HTML, võite tegelikult kasutada andmestruktuuri nagu Selle määramiseks, kas lehekülg on õigesti vormindatud. Sest me näeme, kõik veebilehti järgima omamoodi hierarhia, taandus mis, lõpus päeval, siis puu struktuuri all kapuuts. Nii enam edasi, et vaid veidi. 

Aga nüüd, lähme ettepaneku kohta hetk, kuidas me saaksime minna esindavad mida stack on? Las ma ettepaneku, et me ellu stack koodiga niimoodi. Nii stack läheb on sees on kaks asja, array nimega plaate, lihtsalt olla kooskõlas demo. Ja iga toodet, mis massiivi saab olema tüüpi int. Ja võimsus on oletatavasti? Sest ma ei ole kirjutatud täielik määratlus siin. 

See on ilmselt suurim suurusest massiivist. Ja see on ilmselt deklareeritud terav define ülaosas faili, mõned selline pidev, kui sellele viitab Ainuüksi kapitaliseeritust. Nii kuskil maht on määratletud maksimaalne võimalik suurus. Vahepeal sees andmestruktuur tuntud stack seal olema täisarv lihtsalt teada lihtsalt suurus. 

Nii et kui ma oleks esindada seda nüüd piltlikult oletame, et see kogu must kast esindab minu stack. Toas on kaks muutujat. Ma lähen, et juhtida Esimene on suurus. Ja teine ​​ma lähen juhtida massiivina. 

Aga lihtsalt, et hoida asjad korrapärane, tavaliselt Juhin massiivi nagu , kuid see on selline kena kui me mängu reaalsus, või sobitada vaimne mudel. Nii et lubage mul vaid teha massiivi vertikaalselt, mis on vaid jällegi Kunstniku üleviimise. Ei ole tegelikult oluline, mida see on alla kapuuts. Ja me ütleme, et vaikimisi, võimsus saab olema kolm. Nii et see saab olema asukoha 0, siis on asukoht 1, see on koht 2. 

Kui ma altkäemaksu koos stressi pall, eks keegi meeldib tulla ja käivitada pardale siin hetkeks? OK, nägin oma käsi esimene. Tule üles. Hea küll. Nii et ma usun, et see on Steven. Tule üles. Hea küll. 

Aga oletame nüüd me tagasikerimiseks esialgse riik maailmas, kus ma äsja kuulutatud virna, ja see on kavatse olla läbilaskevõime kolm. Aga suurus ei ole veel kindlaks määratud. Plaate ei ole veel kindlaks määratud. Nii paar küsimust esimene. Ja lubage mul anda teile mic, nii et saate Nautida aktiivsemalt selles. 

Mis on sees suurus praegu ajal, kui ma olen teinud on deklareeritud korstnat üks rida koodi? 

Steven: Mitte palju. 

DAVID Malan: OK, ei ole palju. Kas me teame, mis seal sees on suurus, me teame, mis seal sees on Selle massiivi siin? 

Steven: Just juhusliku koodi, eks? Just - 

DAVID Malan: Jah, ma lähen nimetame seda koodi, kuid juhuslik - 

Steven: asjad. 

DAVID Malan: Asjad juhuslik 

Steven: Bits. 

DAVID Malan: Bits, eks? Nii prügi väärtused, eks? Nii permutatsiooni 0-ja 1 aasta. Jäänused eelmine tavasid Selle mälu. Ja me ei tea, mis väärtused on, et me tavaliselt juhtida neid nagu küsimärgid. 

Nii et esimene asi, mida me arvatavasti lähed tahan teha siin - ja las ma annan selle valdkonna sees seal nimi - plaate. Mida me peaksime ilmselt initsialiseerida suurus, kui tahame alustada, kasutades seda korstnat? 

Steven: Tray on sub 3. 

DAVID Malan: Niisiis, OK. Et oleks selge, võimsus on välja kuulutatud mujal kui kolm. Ja see, mida ma olen kasutanud jaotada massiivi. Suurus läheb vaadake, kui palju plaate on praegu pinu. 

Steven: Zero. 

DAVID Malan: Seega peaks olema null. Nii et laske käia ja iga sõrme, juhtida null suurusega. Hea küll. Nüüd, mis on sees see siin, me ei tea. Need on tõesti lihtsalt prügi väärtused. Nii et me võime joonistada küsimärke, kuid Hoidkem pardal puhas nüüd sest see ei ole oluline mis seal on. Meil ei ole vaja initsialiseerida array midagi, sest me teame, et suurus stack on null, noh, me ei tohiks olla vaadates midagi Selle massiivi niikuinii juures ajahetkel. 

Nüüd oletame, et ma suruge number 9 peale virna. Kuidas me peaksime uuendama andmestruktuur sees see must kast? Mis väärtused on vaja muuta? 

Steven: jooksul - suurus? 

DAVID Malan: OK. Suurus peaks saama mis? 

Steven: Suurus oleks üks. 

DAVID Malan: OK. Nii suurus peaks olema üks. Nii saate teha seda paar võimalust. Annan teile, nüüd oma sõrm on kustutuskumm. Hea küll. Siis nüüd sõrm on pintsel. Hea küll. Ja nüüd, mida teised on muuta, Ilmselt andmete struktuur? 

Steven: Me läheme alates põhja kuni 9. 

DAVID Malan: 9. OK, hea. Nii ikka ei ole oluline, mis kell Asukoht üks või kaks, sest nad on prügi väärtused, kuid me ei peaks vaeva nägema otsin seal, sest suurus on ütleb meile, et ainult esimene element on tegelikult õigustatud. Nüüd ma push 17 peale nimekirja. Mis juhtub seda pilti? 

Steven: Nii suurus läheb minema kaks. 

DAVID Malan: OK. Sa oled kustutuskumm - oops. Sa oled kustutuskumm. 

Steven: Eraser. 

DAVID Malan: Sa oled pintsliga. 

Steven: Võsa. 

DAVID Malan: OK. Ja mis veel? 

Steven: Ja siis - 

DAVID Malan: nõudsime 17. 

Steven: Me jääda 17 peal, nii et - 

DAVID Malan: OK, hea. 

Steven: - tilk maha. 

DAVID Malan: Olgu. See muutub lihtne. Ma ei kavatse teid aidata seekord. Push 22. 

Steven: Valmis. Saades kustutuskumm. Olen muutumas pintsliga. Ja siis ma panen 22. 

DAVID Malan: 22. Suurepärane. Nii et üks rohkem aega. Ma nüüd sunnin peale virna 26. 

Steven: Ooh. Oh jumal. Sa tõesti püütud mind välja kaitsepiire. 

DAVID Malan: sa ei ole see peaks toimuma? 

Steven: Ma ei näinud seda tulemas. Võiks me uuesti algne maht? 

DAVID Malan: See on hea küsimus. Nii et me oleme omamoodi värvitud end nurgas siin. Seal tõesti ei ole hea välja Steven sest me oleme eraldatud selle massiivi staatiliselt, niiöelda sees andmete struktuuri. Ja me oleme sisuliselt kõva kodeeritud see olevat suurus kolm. Nii et me ei saa tõesti suunata see. 

Võiksime kui läksime tagasi, me uuesti kandikud olla pointer et me siis kasuta malloc kätte mälu. Sest kui meil on mälu hunnik kaudu malloc oleme võiks siis vabastada ta. Aga enne vabastades ta, võiksime suunata suurem patakas mälu uuendada pointer, ja nii edasi. Aga nüüd, see on tõesti Parim, mida me teha saame. Push ja pop on arvatavasti läheb et anda märku mõni viga. 

Nii näiteks meie rakendamise push võib naasta bool mis varem tagastatakse true, true, true. Aga neljandat korda, see läheb on tagasi false, näiteks. Hea küll. Väga hästi tehtud. Palju õnne. Olete teeninud oma stressi pall täna. 

[APLAUS] 

Steven: Aitäh. 

DAVID Malan: Aitäh. OK, nii see tundub olevat mitte palju on samm edasi, eks? Meil on kirjeldatud käesoleva andmete struktuuri. See on olnud veenvad, eks? Operatsioonisüsteemide nagu see. Ilmselt web saab kasutada seda, ja muid rakendusi veel. Aga mis loll piirang, et me oleme Tagasi omamoodi nädal kaks piirmäära kus meil on fikseeritud suurus massiivid. 

Seega on tõepoolest paar kuidas me võiksime lahendada. Võiksime dünaamiliselt jaotab massiivi mitte raske kodeerimine see nagu ma olen teha siin, vaid uuesti kuulutatakse see lihtsalt peab olema selge, kui midagi sellist. Int * plaate ei otsusta edasi maht veel. Aga kui ma tunnistada stack mujal minu kood, ma võiks siis kutsuda malloc, saada aadress tüki mälu, ja ma ei anna et aadressi plaate. 

Ja siis, kuna see on lihtsalt kamakas mälu, ma võiks jätkuvalt kasutada ruudu sulg märke tavalisel viisil. Kuna jällegi on omamoodi see funktsionaalne ekvivalent massiivid ja tükkideks mälu, mis tulevad tagasi malloc. Me võime ravida üks kui teine kasutades pointer aritmeetika või nurksulg märke. Nii et see on üks võimalusi. 

Aga kuidas muidu võiks me rakendada seda samade andmete struktuuri, potentsiaalselt? Õigus? Ma tunnen, et me just lahendasime selle probleem nagu nädal tagasi. Milline oli lahendus sellele probleemile et Steven sattus? Nii ahelloendid, eks. 

Kui probleem on selles, et me oleme värvimine end nurka, eraldades ette liiga vähe mälu, et meil siis on kuidagi tegeleda, noh, miks mitte lihtsalt vältida asi üldse? Miks mitte lihtsalt kuulutada kandikud olla kursor sõlme, ergo seotud nimekirja, ja siis lihtsalt eraldada uusi tippe iga kord Steven vaja sobitada number paigutatakse andmestruktuur. 

Nii pilt oleks muuta. Ta ei kavatse olla nii puhas ja lihtne kui lihtsalt massiivi kolm ints. Nüüd saab olema viit struktuure ning et struct läheb on int ja järgmise pointer. See saab viia läbi, et pointer teise sellise struct et teise sellise struktuure. Nii pilt tegelikult natuke segasemaks. Ja me oleme nooled sidumine kõik koos. 

Aga see on hea, õige, sest oleme näinud, kuidas seda teha. Ja kui sa saad mugav rakendamisel midagi seotud nimekiri, mida sa pead tegema kui sa soovi korral rakendada hash tabel eraldi Aheldamise p-set 6, saate seda kasutada ehituskivi, või koostisosa või Scratch rääkima, kord, midagi, et paned, siis loonud oma puzzle tükk mis saab siis uuesti. Nii kompromissidega, kuid võimalikke lahendusi et me oleme tegelikult näinud. 

Nii sageli, sa näed seda iga aasta või kaks, kui Apple releases midagi uut ja kõik hullud inimesed rivistama väljaspool Apple poest osta oma marginaalne uuendada riistvara. Ma ütlen seda, et see on OK, sest Ma olen üks neist inimestest. Nii et millist andmestruktuuri võib esindada see reaalsus? 

Noh, ütleme järjekorda, joon. Nii Briti kutsuksin ta tavaliselt järjekorda niikuinii, nii et see on kena nimi. Ja need kaks toimingut, mis järjekorras toetab me kutsume Lisa järjekorda töö ja dequeue operatsiooni mis on sarnased vaim push ja pop. See on lihtsalt omamoodi erinev konventsioon, mida me kutsudes neid. Aga Lisa järjekorda midagi tähendab, lisada või paigaldage see andmestruktuur. Et dequeue vahendid kustutada. Aga arvestades, et stack oli LIFO andmed struktuur, järjekord on esimene, kõigepealt välja andmestruktuur. 

Kui oled esimene inimene liin, siis esimene inimene saada kohatu ja osta uus seade. Kujutage ette, kuidas ärritunud need inimesed oleksid kui Apple asemel kasutatakse korstna jaoks Näiteks rakendada korjamine üles oma uus mänguasi. Nii järjekorrad mõtet, kindlasti, ja me ei mõtle igasuguseid rakendusi, arvatavasti, sest järjekorrad eriti kui sa tahad õiglust. Niisiis, kuidas võiks siis rakendada neid kui andmestruktuur? 

Noh, ma teen ettepaneku, et me võiksime vaja teha seda nii. Nii et ma lähen nüüd on numbrid. Nii et me hoiame see lihtne ja ei tingimata rääkida nii plaate. Just numbrid, et inimesed on saanud. Maht läheb taas määrata inimeste koguarv, mis võib olla seda joont, kui kolm või mis iganes muu väärtus. 

Aga pakun, et mul on vaja jälgida mitte ainult nende suuruse järjekorda, kuidas paljud asjad on seal. Nii suur on praegune suurus, võimsus on maksimaalne suurus. Lihtsalt jälle, nomenklatuur kokkuleppeliselt. Miks ma pean veel int sees of järjekorda jälgida, kes on sisse ees rida? Miks ma pean tegema, et see nii on? 

Noh, kuidas on see pilt muutu? Ma ilmselt uuesti kõige Selle pildi. Lubage mul minna ja kustutada, mida on siin. Me anname seda veidi teine ​​nimi siin. Olgem vabaneda 17, lähme vabaneda of 9, lähme vabaneda 3. Ja olgem lisada veel üks asi. Pakun, et mul on vaja jälgida ees nimekirja, mis on just saab olema int samuti. Ja me ei kavatse hoida lihtsa. No seotud nimekirja nüüd. 

Me tunnistama, et me ei kavatse Tõstab vastu selle piiri. Aga mida ma tahan näha juhtub sel ajal? Seega arvan, et ma minna ja esimene isik kerkib rida ja see on number 9. Meil on stress pallid. Kas ma varastama, ütleme, kaks või kolm inimest? Üks, kaks, kolm? Tule üles. Right eestpoolt, sest teeme seda ühe kiire. 

Igaühel teist on nüüd olla fan boy joone Apple. Sa ei saanud Apple riistvara lõpus see küll. Hea küll. Nii et sa oled number 9, oled number 17, number 22. Need on meelevaldne arv, nagu üliõpilane ID või tühi-tähi. Ja hetk, alustagem alustada lisades asju. Ja ma joosta juhatuse siin seekord. 

Nii et kui ma olen vormindatud ees olema - Ma tegelikult tõesti ei huvita, mida ees on, sest suurus on null. Nii et see võib ka lihtsalt olema küsimärk. Need kõik on küsimärke. Nüüd hakkame tegelikult näha mõningaid inimesed vooder üles poodi. 

Nii et kui number 9, sa oled esimene, seal juures 05:00, edasi minna ja rivistama, või õhtul. OK. Nüüd 9 on siin. Nii 9 on ees nimekirja. Nii et ma lähen edasi minna ja uuendada kui suur see praeguste andmete struktuur ei ole 0 enam vaid olla 1. Ma panen 9 juures ees nimekirja. Lubage mul minna ja vahelduvad ekraanil nii me näeme viimase meid siia. 

Ja nüüd, mida ma tahan, lauda ees? Ma lähen, et jälgida, et ees järjekorda kohe on asukoha 0. Sest see, mis järgmisena juhtub? Noh, oletame, nüüd ma Lisa järjekorda 17 samuti. Nii hop liin seal. Ja jälle omamoodi uks pood saab olema siin. Nüüd olen lisanud 17. Ja kuigi need kutid blokeerimine ekraan, see on OK, sest me näeme seda siin. Vabandust. 

Publik: me saame liikuda - 

DAVID Malan: Ei, see on OK. See on suur seal. Nii 17 on nüüd sees järjekorda. Mul on vaja uuendada, mis valdkondades nüüd küll? OK, kindlasti suurus. Ja kuidas on ees? OK, ei. Front ei tohiks muuta, sest erinevalt stack oleme tahavad säilitada õiglus. Nii et kui 9 tuli esimene, tahame 9 olla esimene välja rida ja poodi. 

Tegelikult, vaatame seda. Enne kui me sisestada 22, lähme minna ja dequeue 9. Mis su nimi oligi? 

Publik: Jake. 

DAVID Malan: Jake läheb tuleb dequeued nüüd. Nii saad kõndida poest. Ja teeselda, et kaupluse on seal. Nüüd, mida on vaja - dit-dit-dit! Mis peab juhtuma nüüd? Design otsus. Nii ei ole halb instinkt, aga - mis su nimi oligi? 

Publik: David. 

DAVID Malan: David. Mida tegi David teha? Ta püüdis omamoodi määrata andmed ning viia oma asukohta arvesse Jake endine asukoht. Ja see on hea, kui me oleme valmis nõustuda, et kui rakendamise üksikasjalikud. Aga kõigepealt, lähme andmeid värskendada struktuur, enne kui me seda teha. Sest ma ei meeldi idee kõik inimesed suunates seda joont. 

See ei ole suur asi, kui David see koos üks samm, kuid jällegi mõtlen tagasi kui meil on olnud kaheksa vabatahtlike etapis ja me oleme teinud nagu sisestamise sort, kus me pidime alustama liigub kõik ümber. See sai kallis, eks? See teeb mind roomama umbes suur O n, suur O n ruudus uuesti. See ei tunne ideaalne tulemus. 

Teeme lihtsalt uuendada seda. Nii suuruse järjekorras ei ole enam 2. Nüüd on lihtsalt 1. Aga ma ei saa nüüd uuendama midagi Ma ei uuenda enne, ees nimekirja. Ma võiks lihtsalt öelda, on see, et kohale 1? Nüüd on meil prügi väärtus siin, prügi väärtus siin, ja Taavet Keset seda prügi. Aga andmestruktuur on veel puutumata. 

Ja tegelikult, ma ei pea isegi muuta Jake endine number 9, sest kes hoolib. Mul on piisavalt teavet praegu suurus, et ma tean, et seal on üks inimene seda järjekorda. Ja ma tean, et ta on asukoht 1, mitte 0. Ma ei lugedes. Nii 1. kui ka. Nii andmete struktuur on ikka OK. 

Noh, mis järgmisena juhtub? Teeme Lisa järjekorda - Mis su nimi on? 

Publik: Callen. 

DAVID Malan: Callen. Olgem Lisa järjekorda Callen ja 22 on nüüd järjekorras. Nüüd mis peab muutuma here? Front ei kavatse muuta, ilmselt. Suurus on muutu olema 2 uuesti. Ja 22 jõuab siia, 9 on endiselt olemas, aga see on tegelikult prügi raha nüüd. See on lihtsalt jäänuk Jake minevikust. 

Nüüd mis juhtub, kui Ma dequeue David? Üks viimase operatsiooni dequeue David. Me võiks liikuda, kuid pakun olgem teha nii vähe tööd kui võimalik. Nüüd minu andmestruktuur läheb tagasi suurus 2-1. Aga ees järjekorras nüüd saab 2. Mul ei ole vaja muuta need numbrid lihtsalt veel, sest nad on lihtsalt prügi väärtused. 

Aga nüüd, mis juhtub? Oletame I Lisa järjekorda ise, 26? Ma tunnen, et ma kuulun siia. Nii et ma olen seda enqueued. Nii et ma mingi kuulu siia. Ja kuigi sa ei ole päris hindan seda visuaalselt laval, sest meil on piisavalt ruumi, et ma peaksin ei seisaks siin, siis miks? 

Publik: Sa oled audis. 

DAVID Malan: Õigus. Ma olen audis. Olen indekseeritud kaugemale piire see massiiv. Ma tõesti peaks olema üks kolm võimalikku asukohta. Nüüd, kus on kõige loomulikum minna? Teen ettepaneku võimendatud nädal üks trikk. Mod operaatori protsent. Sest ma tehniliselt seisvat asukoht 3, aga ma 3 mod võimsus, nii 3 protsenti märk, 3 - võimsus on 3. Mis see on? Mis on ülejäänud kui sa jagad 3 3? 0. 

Nii et paneb mind olid Jake oli, mis on tegelikult hea. Nüüd rakendamise see asi läheb olla natuke peavalu. See on tõesti lihtsalt üks rida peavalu, koodi. Aga vähemalt nüüd on prügi väärtus siin, kuid seal on kaks õigustatud ints siin. Ja ma väita, et nüüd me oleme teinud täpselt, mida me peame tegema nii kaua, kui me muuta seda, mis Jake väärtus pidi olema 26. 

Nüüd on meil piisavalt informatsiooni veel säilitada terviklikkuse Selliste andmete struktuuri. Me oleme ikka veel sellist õnne, kui me soovite lisada neli või rohkem kokku elemente, kuid võin vähemalt teha päris tõhus kasutamine see pidev aeg, tegelikult. Ma ei pea muretsema, suunates igaüks, kui Taaveti kalle oli. 

Kõik küsimused on korstnad, või see järjekord? 

Publik: on põhjus, miks pead suurus, et sa tead kus on inimene? 

DAVID Malan: Täpselt. Ma pean teadma, suurusest massiivist sest mul on vaja teada, kuidas täpselt paljud need väärtused on õigustatud, ja nii, et ma ei leia, kuhu panna järgmisele inimesele. Täpselt. Suurus - tegelikult, me ei uuenda seda veel. Lisasin ennast kell 26. Suurus on nüüd, mitte 1, vaid 2. Nüüd see tõesti aitab mul leida eesotsas nimekirja, mis ei ole 0, ei 1, kuid on 2. Ees nimekiri on tõesti number 22. Kuna ta tuli esimene, nii et ta peaks lubatakse poodi enne mind, kuigi visuaalselt Ma seisan lähemale poest. 

Olgu? Aplausi need kutid ja me anname neid välja sealt. 

[APLAUS] 

DAVID Malan: ma võiks lasta hoiate salve. Võiksime vaadata, mis juhtub siis, kui sa tahad, aga võib-olla mitte. Hea küll. Mis siis nüüd ei, mis jätavad meid? Noh, las ma ettepaneku, et seal on mõned muud andmestruktuurid võiksime alustada lisades meie tööriistakomplekt, mis tegelikult olla üsna, üsna oluline, sest me sukelduda web kraam. Mis jällegi on mingi seos et puude kujul midagi, mida nimetatakse DOM, dokument objekti mudeli. Aga me näeme rohkem et enne pikk. 

Lubage mul pakkuda definitionally et me kutsuvad puu nüüd, mida sa võiksid teada, kui rohkem sugupuu, kuhu mõned esivanem juures puu juurtele. Patriarhaalne või matriarh juures väga tipus. Ilma oma abikaasa, käesoleval juhul. Aga meil on nüüd see, mida me kutsume lapsed, kes on sõlmed, et riputada ära vasaku lapse või paremale laps, nooled on kujutatud siin. 

Teisisõnu, on puu andmestruktuur arvuti, puu on null või rohkem tippe. Kui see on vähemalt üks sõlm, seda nimetatakse root. On asju visuaalselt, et juhime ülaosas. Ja et sõlm, nagu mis tahes muu sõlme, saab on null, üks või kaks või kolm, või siiski palju lapsi andmestruktuur toetab. Sel juhul root, säilitades väärtus üks, on kaks last, 2 ja 3, nii me tavaliselt nimetame 2 vasakul laps ja 3 õigus laps. 

Ja siis, kui me alla 5, 6, ja 7, 6 võib nimetada keskel laps. Kui teil on neli last, ta saab segane. Nii et me lõpetada selline otsetee suuliselt. Aga see on tõesti ainult sugupuu. Ja lehed on siin sõlmede et ise ei ole lapsi. Nad riputada off põhja puu. 

Niisiis, kuidas võiks siis rakendada puu on ainult kaks last maksimaalselt? Me nimetame seda kahendpuu. Bi jälle tähendab kaks sellega juhul, nagu binaarse. Ja nii see võib olla null, üks, või kaks last maksimaalselt. 

Ma ettepaneku, et me rakendada sõlme selle struktuuri int n, ja siis kaks suunanäitajaks, üks nn vasakule, üks nn õige. Aga need on vaid kena suvalise konventsioonidega. Ja mis kena nüüd, eriti kui teil liiki võidelnud kontseptuaalselt koos rekursioon, või arvatakse, et see ei olnud tõesti lahendus midagi, eriti kui sa saaksid otsa mälu. Nüüd, kui me räägime andmed struktuure ja algoritme, mis võimaldavad meil läbida ja manipuleerida neid, Selgub, et rekursioon tuleb tagasi palju ahvatlevamaks kui mitte ilus viis. 

Nii et see pakun on rakendamise of Search funktsiooni. Arvestades kahe sisendi - seega mõtle seda kui musta kasti. Arvestades kahe sisendi, n, int, ja kursor puu pointer sõlme, või tõesti puu juurt, I väide, et seda funktsiooni saab tagasi õige või vale, et väärtus n on sees seda puud. 

Mis seal sees on selle musta kasti? Noh, neli haru. Esimene lihtsalt kontrollib. Kui puu on null, siis tagastab false. Kui seal ei ole sõlme, pole n, pole number, vaid tagastab false. Kui aga n, väärtus, mida otsid eest, on vähem kui puu nool n ja lihtsalt olla kindel, mida see tähendab, kui Ma kirjutan puu ja siis nool märke, n? Täpselt. See tähendab dereference et pointer nimega puu. Minge sinna ja siis saad sisse selle sõlm ja saada oma ala nimetatakse n. Ja siis võrrelda tegelikke n, mis oli läks Otsi selle vastu. 

Nii et kui n on väiksem n väärtus puus tipu ennast hästi, Mida see tähendab? See tähendab, et midagi esimesel pilgul. Õigus? Just nagu siis, kui sul on array väärtused, et teile soovida kohaldada binaarne otsida nii vormis lõhe ja vallutada. Aga milline oletus ei peame jaoks binaarne otsing tööd üldse aastal telefoniraamatust ja varasemaid näiteid? 

Kuidas sorteerida. Niisiis olgem täpsustada mõiste puu siin ei oleks lihtsalt puu, mis võib mingit laste arvu. Mitte ainult kahendpuu, mis võib on 0, 1 või 2 maksimaalselt. Aga kui Kahendotsingupuu või BST mis on lihtsalt fancy viis öelda kahendpuu nii, et iga sõlme vasak laps, kui seda esineb, on vähem kui sõlme. Ja iga sõlme õigust lapse kui seda esineb, on suurem kui sõlm ise. 

Nii teisisõnu, kui sa olid juhtida puu välja kõik numbrid on hoolikalt tasakaalustada niimoodi, et kui teil on 55 root, 33 minna oma vasakule, sest see on vähem kui 55. 77 võib minna selle õige, sest see on suurem kui 55. Aga nüüd teate, sama määratlust, see on rekursiivne definitsioon verbaalselt, taotlema 33. 33 vasak laps peab olema väiksem kui see, ja 33 õigus laps, 44, peab olema suurem kui see. 

Nii et see on Kahendotsingupuu ja Pakun, kasutades natuke rekursioon, saame nüüd leida n. Nii et kui n on väiksem kui väärtus n, mis on aktiivse sõlme, ma lähen käia ja punt niiöelda, ja lihtsalt tagasi iganes vastus on otsides n kohta puu vasakule laps. Teade jälle see funktsioon lihtsalt loodab sõlme star, kursor sõlme. Seega kindlasti ma ei saa lihtsalt teha puu nool vasakule, mis viib mind teise sõlme. Aga mis on see, et sõlm? 

Noh, vastavalt käesoleva deklaratsiooniga, Vasakul on lihtsalt kursor, nii et lihtsalt tähendab, et ma panen selle otsingu funktsiooni erinevad pointer, nimelt üks, mis tähistab mu vasak lapse puu. Nii et sel juhul kursorit 33, kui see on meie proovi sisend Vahepeal kui n on suurem kui väärtus n aasta aktiivse sõlme puu, siis ma olen läheb minna ja punt teistes suunas ja lihtsalt öelda, ma ei tea, kas see väärtus n on puus, kuid ma tean, et see on, see on ette minu õige haru, nii rääkida. Nii et lubage mul kõne rekursiivselt otsida, kulgeb n uuesti, kuid kulgeb kursor minu õigus laps. 

Teisisõnu, kui ma olen praegu 55 ja ma otsin 99, ma tean, et 99 on suurem kui 55, nii nagu ma rebis telefoniraamatust nädalat tagasi ja me läks otse, samamoodi on meil lähen siin. Ja ma ei tea, kas see on minu õigus laps, ja see ei ole, 77 on olemas, kuid Ma tean, et see on selles suunas. Nii et ma kutsun otsing minu õige laps, 77, ja lase otsing joonis välja seal kui 99 selles meelevaldne Näiteks on tegelikult olemas. 

Else, mis on viimane juhtum? Kui puu on null on ühel juhul. Kui n on väiksem kui praegune sõlme väärtus on teise puhul. Kui n on suurem kui praegune node väärtus on olemas ka kolmas. Mis on neljas ja viimane juhtum? Arvan, et oleme välja juhul, eks? See peab olema, et n on aktiivse sõlme, et ma olen. 

Nii et kui ma olen otsivad 55 selles punktis lugu, et filiaal puu Jõutakse tõsi. Mis on huvitav on see, et me tegelikult erinevalt nädalat varem, oleme lahke kohta on kaks baasi juhtudel. Ja nad ei pea olema kõik ülaosas. Top on aluspõhimõtted, sest kui Puu on null, pole midagi teha. Lihtsalt tagasi kõva kodeeritud väärtuse false. 

Alumine haru on omamoodi default, kusjuures kui oleme kontrollinud null, me kontrollida, kas see peaks olema jäänud, kuid see ei peaks olema, oleme kontrollida, kas see peaks olema õige, kuid see ei tohiks olla, kindlasti peab see olema õigus, kus me oleme. See on tugipunkt. Nii et seal on kaks rekursiivne juhtudel asuvast seal keskel. Aga ma oleks kirjutanud see mis tahes järjekorras. Ma lihtsalt arvasin, et see omamoodi tunda loomulik kõigepealt kontrollida võimalik viga, siis vaadake vasakule, siis vaadake paremale, seejärel eeldada, et sa oled sõlme sa oled tegelikult otsivad. 

Miks võib see olla kasulik? Nii selgub - ja andke mulle hüpata teaser siin see on veebis. Me läheme hakata ei programmeerimiskeel alguses, kuid märgistuskeel. Märgistuskeel on üks, mis on sarnase sisuga programmeerimine keel, kuid see ei anna teile suutlikkus väljendada ennast loogiliselt. See ainult annab teile võime ennast väljendada struktuuriga. 

Kui sa tahad lisada midagi lehel veebilehele? Mis värvi sa tahad teha? Mida kirjasuuruse sa tahad teha? Mis sõnu sa tegelikult tahan veebilehelt? Nii et märgistuskeel. Aga siis me väga kiiresti kasutusele JavaScript, mis on täieõiguslik programmeerimiskeelt. Väga sarnane süntaktiliselt välimusega Lisa C, kuid see saab olema mõned kena, võimsam, rohkem kasutajasõbralikud omadused. 

Ja üks pettumusi selles mõtet semester on see, et paneme kiiresti rakendada veerija palju vähem rida koodi kasutades teistes keeltes kui C ise lubab, kuid põhjus on me varsti aru. See on esimene selline veebileht. See on täiesti underwhelming, Esimene teeme. See lihtsalt tähendab, tere. Aga kui sa oled kunagi näinud seda enne, see on HTML, Hypertext Markup Language. 

Kui te lähete teatud menüü valik Kõige iga brauseriga, mis tahes veebilehe internet, näete HTML et mõned inimesed kirjutasid luua, et veebilehel. Ja see ilmselt ei ole nii lühike või kui puhas nagu see. Aga ta jälgib muster neist lahtised sulud ja kaldkriipsud ja kirjad ja potentsiaalselt numbrid. 

Ma arvasin, et sulle teaser mida saate teha pärast pildistamist CS50. Lubage mul minna cs.harvard.edu / Rob, meie enda Rob Bowden kodulehelt. Ta tegi seda meie eest. Nii saate kohe võimalik teha. Ja ka see, mida te olete kuulnud täna hommikul - mida te olete kuulnud täna hommikul - 

[HAMSTER TANTSUMUUSIKAT] 

- You'Ll teha seda. See ootab meid kolmapäeval. Näeme siis. 

[HAMSTER TANTSUMUUSIKAT] DAVID Malan: Järgmisel CS50 -