>> 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.
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 -