>> KEVIN Schmid: Mõnikord, kui hoone programm, võite kasutada
andmestruktuur tuntud sõnastik.
Sõnastik kaardid võtmed, mis on tavaliselt stringid, et väärtused, ints,
tähemärki, kursor mõne objekti, mida iganes me tahame.
See on nagu tavaline sõnastikud et kaart sõnade kaudu mõisted.
>> Sõnaraamatud annavad meile võime salvestada teavet
seotud midagi ja otsida see üles hiljem.
Niisiis, kuidas me tegelikult ellu sõnastik, ütleme, C kood, mis meie võimuses,
kasutada ühte meie programmid?
Noh, seal on palju võimalusi, et saaksime rakendada sõnastik.
>> Ühe, võiksime kasutada massiivi, et me dünaamiliselt uuesti suurus või võiksime kasutada
seotud nimekirja, hash tabel või kahendpuu.
Aga mida me valida, et me peaksime tähelepanelikkusele tõhusust ja
täitmise rakendamise.
Peaksime mõtlema algoritmist sisestada ja otsida esemete
Meie andmete struktuuri.
>> Nüüd Oletame, et me soovite kasutada stringe võtmed.
Räägime üks võimalus, andmestruktuur nimega Prefiksipuu.
Nii et siin on visuaalne esitus kohta Prefiksipuu.
>> Nagu võib oletada, Prefiksipuu on puu andmestruktuuri
sõlmed on omavahel seotud.
Me näeme, et seal on selgelt root node mõned lingid laiendatakse
teiste keskustega.
Kuidas iga sõlm koosneb?
Kui me eeldame, et me oleme ladustamiseks võtmed ainult tähti ja
me ei hooli kapitalisatsioon siin on mõiste sõlme
piisab.
>> Objekt, mille tüüp on struct sõlm on kaks osa
nimetatakse andmete ja lastele.
Me oleme jätnud andmed osaliselt kommentaar asendada komponendi
deklaratsioon kui struct tipp on inkorporeeritud C programmi.
Andmete osa sõlm võib olla Tõeväärtuse, mis näitab, kas
ei tipule lõpetamist sõnastiku võti või võib see olla
string esindab määratlus sõna sõnastikus.
>> Me kasutame naerusuu näidata kui andmed on olemas sõlme.
Seal on 26 elementi meie lapsed massiivi üks indeks
kohta tähte.
Me näeme, kui oluline Selle kiiresti.
>> Lähme lähemale välimuse juurtipust meie diagramm, mis ei ole andmeid
sellega seotud, nagu on näidatud Kuna naerusuu sisse
andmete osa.
Nooled ulatub osad lapsed massiivi moodustavad mitte-sõlme
viiteid teistele sõlmed.
Näiteks nool ulatub teine ​​element laste
on kirjas B sõnaraamatus võti.
Ja suurem skeem me märgistavad koos B.
>> Pange tähele, et suurem skeem, kui me juhtida kursorit teise sõlme, see
Ei ole oluline, kus nooleots vastab selle teise sõlme.
Meie proovi sõnastik Prefiksipuu sisaldab kaks sõna, mis ja zoom.
Vaatame näiteks soojaks andmed võti.
>> Oletame, et me ei tahtnud, et otsida vastav väärtus võti vann.
Hakkame meie pilk üles root sõlme.
Siis võtan esitäht meie klahvi, B ja leida vastava
kohapeal meie lapsed massiivi.
Pange tähele, et seal on täpselt 26 laigud massiiv, üks iga kirja
tähestikku.
Ja me peame laigud esindama tähestiku järjekorras.
>> Me vaatame teise indeks siis, indeks ühele, B. Üldiselt, kui me
mõned tähte C me võib määrata vastava koha
aastal laste massiiv kasutades arvutus niimoodi.
Me oleks võinud kasutada rohkem lapsi massiivi kui me tahtsime pakkuda Look Up
võtmed laiemat tähtedega näiteks kogu
ASCII kooditabel.
>> Sel juhul osuti meie lapsed reaga
index üks ei ole null.
Nii me jätkame otsivad up võti vann.
Kui me kunagi tekkinud null pointer õigel kohapeal lapsed
massiivi kui me läbitakse sõlmede siis me peame ütlema, et me
ei suutnud leida midagi, et võti.
>> Nüüd võtan teist kirjas Meie peamine, ning jätkuma
suunanäitajaks sel viisil, kuni me jõuda lõpuks oma võti.
Kui jõuame lõpuks võtit lööb surnud lõpeb, null suunanäitajaks,
nagu käesoleval juhul, siis me ainult tuleb kontrollida veel ühte asja.
Kas see võti tegelikult sõnastikku?
>> Kui nii, siis peaks leidma raha, hästi naerusuu ikooni meie skeem, kus
sõna lõpus.
Kui on midagi salvestatud andmed, siis me saame selle tagasi.
Näiteks klahvi loomaaias ei sõnastik, kuigi oleksime võinud
jõudnud lõpuks see võti ilma kunagi lööb null pointer, kui me
itereerima läbi Prefiksipuu.
>> Kui üritasime otsida võti vann, eelviimane sõlme massiivi indeksi
vastab kirjas H, oleks on olnud null pointer.
Nii vannis ei ole sõnastikus.
Ja nii Prefiksipuu on ainulaadne, et võtmed ei ole kunagi selgelt salvestatud
andmestruktuur.
Niisiis, kuidas me lisada midagi arvesse Prefiksipuu?
>> Lisame võti zoo meie Prefiksipuu.
Pea meeles, et smiley nägu sõlme võiks vastama koodi lihtsa
Tõeväärtuse, mis näitab, et loomaaed on sõnastikus või see võib
vastavad rohkem teavet, et me soovivad seostavad võti loomaaias
nagu määratlus sõna või midagi muud.
Mõnes mõttes on see protsess, et sisestada midagi sisse Prefiksipuu sarnaneb
soojaks midagi Prefiksipuu.
>> Me alustame juurtipust jälle järgmisi näpunäiteid, mis vastab
tähed meie võti.
Õnneks suutsime jälgida viiteid kõik viis kuni jõudsime
lõpuks võti.
Kuna loomaaed on eesliide sõna suum, mis on liige
sõnastik, me ei pea tuleb kõik uued tipud.
>> Me võime muuta sõlme, mis näitab, et tee tähtede viib
see on peamine meie sõnastik.
Nüüd proovime sisestamist võti vann arvesse Prefiksipuu.
Me alustame kell juurtipust ja järgima vihjeid uuesti.
Aga selles olukorras, oleme tabanud surnud lõpeb enne, kui me oleme suutnud saada
lõpuks võti.
Nüüd me peame eraldama mõned uued keskusteks, peavad eraldama üks uus
sõlm iga ülejäänud kirjas meie võti.
>> Sel juhul me lihtsalt vaja eraldada üks uus sõlm.
Siis me peame H indeks viide uue sõlme.
Taas saame muuta sõlme näitavad, et tee tähtede
viib ta esindab võti meie sõnastik.
Olgem arutleda umbes asümptootiline keerukust meie metoodikad nende
kaks operatsiooni.
>> Oleme märganud, et mõlemal juhul on number samme meie algoritm selleks oli
võrdeline arv tähed märksõna.
Just nii.
Kui soovid otsida sõna Prefiksipuu sa lihtsalt vaja kinnitada, läbi
Tähtede ükshaaval kuni sa kas jõuda lõpuks sõna või
tabanud ummiktee Prefiksipuu.
>> Ja kui te soovite sisestada klahvi väärtus paar arvesse Prefiksipuu kasutades
kord me arutasime, halvimal juhul on teil eraldada uus sõlm
iga täht.
Ja me eeldame, et jaotus on pidevalt aega tööks.
Nii et kui me eeldame, et võtme pikkus on piirneb fikseeritud konstant, nii
sisestamise ja otsida on pidev aeg toimingute Prefiksipuu.
>> Kui me ei tee seda eeldusel, et võtme pikkus on piiratud fikseeritud
pidev, siis sisestamise ja otsida, halvimal juhul on lineaarne
võtme pikkus.
Pange tähele, et mitmed ladustatud aastal Prefiksipuu ei mõjuta Look Up
või sisestamise ajal.
See on ainult mõjutanud võtme pikkus.
>> Seevastu kirjete lisamise, ütleme, hash tabel kipub tegema
tulevikus otsida aeglasem.
Kuigi see võib tunduda ahvatlev alguses, Me peaksime meeles pidama, et
soodne asümptootiline keerukus ei tähendab, et tegelikkuses on andmed
struktuur on tingimata laitmatu.
Me peame silmas pidama, et salvestada sõna Prefiksipuu peame halvimal
juhul sõlmede arv võrdeline Lisa pikkus Sõna ise.
>> Püüab kalduvad kasutama palju ruumi.
See on erinevalt hash tabel, kus meil on vaja ainult üks uus sõlm
salvestada mõned põhiväärtus paari.
Nüüd jälle teoreetiliselt suur ruum tarbimine ei tundu suur
tegeleda, eriti arvestades, et kaasaegne arvutid on gigabaiti ja
gigabaiti mälu.
Aga selgub, et meil on veel muretsema mälukasutust ja
organisatsiooni huvides tulemuslikkust, kuna kaasaegseid arvuteid
mehhanismid, alla kapuuts kiirendada mälu juurdepääs.
>> Kuid need mehhanismid töötavad paremini, kui mällupöördumiste tehakse kompaktne
piirkondades või valdkondades.
Ja sõlmede Prefiksipuu võiks elada kõikjal, et hunnik.
Aga need on kompromissid et me peame arvestama.
>> Pea meeles, et valides andmed struktuuri teatud ülesanne, me
peaksid mõtlema, milliseid tegevuse andmestruktuur peab
toetus ja kui palju jõudlust iga nimetatud
toimingute küsimustes meile.
Neid toiminguid võib isegi kauem lihtsalt
põhi-look up ja sisestamist.
Oletame, et me tahtsime ellu mingi auto-complete funktsionaalsust, palju
nagu otsingumootori Google teeb.
See tähendab, et tagastada kõik võtmed ja potentsiaalselt väärtused, mis
on antud eesliide.
>> Prefiksipuu on ainulaadselt kasulik Selle operatsiooni.
See on lihtne kinnitada, läbi Prefiksipuu iga iseloomu
eesliide.
Just nagu otsida operatsiooni me võiks järgida vihjeid
tähthaaval.
Siis, kui jõuame lõpuks eesliide saaksime kinnitada, läbi
Ülejäänud osa andmestruktuur kuna ükskõik võtmed väljapoole
Siinkohal on eesliide.
>> See on ka lihtne saada selle oksjoni tähestikulises järjekorras, kuna
elemendid lapsed massiivi järjestatakse tähestikuliselt.
Loodetavasti saite aru andes püüab proovida.
Ma olen Kevin Schmid, ja see on CS50.
>> Ah, see on alles algus langus.
Vabandust.
>> Strike neli.
Ma olen välja.
Vabandust.
Vabandame tegemise isik on muuta käesoleva hulluks minna.
>> Vabandust.
Vabandust.
>> SPEAKER 1: Hästi tehtud.
See oli tõesti hästi tehtud.