>> KEVIN SCHMID: Kartais, kai pastatas programa, galite naudoti
duomenų struktūra vadinama žodyną.
Žodynas žemėlapiai raktai, kurie yra paprastai stygos, vertybėms, ints,
simbolių, rodyklė į tam tikrą objektą, ką norime.
Tai tiesiog kaip paprasti žodynai kad žemėlapis žodžiai per apibrėžimus.
>> Žodynai pateikti Galimybė saugoti informaciją
susijęs su kažkuo ir surasti jį vėliau.
Taigi, kaip mes iš tikrųjų įgyvendinti žodynas, tarkim, C kodas, kad mes galime
naudoti vieną iš mūsų programų?
Na, yra daug būdų, kad galėtume įgyvendinti žodyną.
>> Už vieną, mes galime naudoti masyvą, kad mes dinamiškai naujo dydžio ar mes galime naudoti
susijęs sąrašas, maišos lentelė arba dvejetainis medis.
Bet ką mes pasirinkti, turėtume prisimindama efektyvumo ir
vykdymą, įgyvendinti.
Turėtume galvoti apie algoritmas įterpti ir ieškoti elementus į
mūsų duomenų struktūra.
>> Nes dabar, tarkime, kad mes norite naudoti eilutes kaip raktus.
Pakalbėkime apie viena galimybė, duomenų struktūra vadinama TRIE.
Taigi čia yra vaizdinis iš TRIE.
>> Kaip paveikslas rodo, A TRIE yra medžio duomenų struktūra,
mazgai sujungti.
Mes matome, kad yra aiškiai šaknis mazgas su kai kurios nuorodos išplečiantis
kiti mazgai.
Bet ką kiekvienas mazgas sudaro?
Jei mes manome, kad mes saugoti raktus su tik raides ir
mes nerūpi kapitalizacija, čia iš mazgo, apibrėžimas
pakaks.
>> Daiktas, kurio tipas yra struct mazgas susideda iš dviejų dalių
vadinamas duomenis ir vaikus.
Mes palikome duomenų dalį kaip komentarą bus pakeistas komponento
deklaracija kai struct mazgas įtraukti į C programa.
Duomenų dalis mazgas gali būti Būlio vertė nurodoma, ar
ne mazgas reiškia užbaigimą iš žodyno rakto arba ji gali būti
ženklų atstovams apibrėžimą žodžio žodyne.
>> Mes naudosime smiley veido nurodyti kai duomenys yra pateikti mazgas.
Yra 26 elementų mūsų vaikai masyvas, vienas puslapis
už raidė.
Pamatysime reikšmę tai greitai.
>> Leiskite gauti arčiau šaknų mazgas mūsų diagramą, kurioje nėra duomenų
susijęs su juo, kaip nurodyta nebuvimas smiley veido
duomenų dalis.
Rodyklės nusidriekę iš dalių vaikai masyvo atstovauti ne-mazgas
rodykles į kitus mazgus.
Pavyzdžiui, rodyklė tęsiasi nuo Antrasis elementas vaikams
atstovauja raidę B žodyne klavišą.
Ir didesnių schema mes ženklina ją su B
>> Atkreipkite dėmesį, kad didesnių schema, kai mes atkreipti žymeklį į kitą mazgą, jis
Nesvarbu, kur Antgaliai atitinka tą kitą mazgą.
Mūsų pavyzdys žodynas trie yra du žodžiai, kad ir priartinimas.
Leiskite eiti per pavyzdys žiūrint duomenis rakto.
>> Tarkime, mes norime ieškoti atitinkančią vertę raktų vonia.
Mes pradėsime mūsų ieškoti šakninio mazgo.
Tada mes priimsime pirmąją raidę mūsų raktas, B ir rasti atitinkamas
vietoje mūsų vaikų masyvo.
Atkreipkite dėmesį, kad yra lygiai 26 taškus masyve, po vieną kiekvienam laiške
abėcėlė.
Ir mes turime dėmės atstovauti abėcėlės raidžių tvarka.
>> Mes pažvelgti į antrąjį indeksą tada, vienas puslapis, skirtas B. Apskritai, jei mes
turėti tam tikrą raidė C mes galėtų nustatyti atitinkamą vietą
į vaikų masyvas naudojant kaip tai apskaičiuoti.
Galėjome naudojo didesnius vaikus masyvas jei norime pasiūlyti pažvelgti į
raktai su įvairesnių simbolių, pavyzdžiui, visą
ASCII simbolių rinkinys.
>> Tokiu atveju, žymeklis mūsų vaikų masyvo
vienas puslapis nėra lygus nuliui.
Taigi mes ir toliau ieškome iki rakto pirtis.
Jeigu mes kada nors susidūrė null rodyklė tinkamu vietoje vaikais
masyvas, o mes vedama mazgus, tada mes turime pasakyti, kad mes
negalėjo rasti nieko už tą raktą.
>> Dabar, mes priimsime antrą raidę mūsų pagrindinis, ir toliau taip
rodykles Tokiu būdu, kol mes pasiekti, kad mūsų raktas pabaigos.
Jei mes pasiekti rakto galą be hitting bet aklavietes, null patarimų,
kaip yra šiuo atveju, tada mes tik turi patikrinti dar vieną dalyką.
Ar tai raktas tikrųjų žodyne?
>> Jei taip, mes turime rasti vertę, taip pat smiley veido piktograma mūsų diagramą, kurioje
žodis baigiasi.
Jei yra kažkas saugomi duomenys, tada mes galime jį grąžinti.
Pavyzdžiui, pagrindinis zoologijos nėra žodynas, nors galėtume turėti
pasiekė šio rakto galą niekada pradeda null rodyklę, o mes
pakartoti per TRIE.
>> Jei mes bandėme ieškoti rakto pirtis, antrasis praėjusių mazgas masyvo indeksas,
atitinkanti raidė H, būtų surengė null rodyklę.
Taigi pirtis nėra žodyne.
Ir taip trie yra unikali tuo, kad raktus niekada aiškiai saugomi
duomenų struktūra.
Taigi, kaip mes įterpti kažką į TRIE?
>> Leiskite įdėti raktą Zoo į mūsų TRIE.
Atminkite, kad smiley veido ne mazgas gali atitikti kodą į paprastas
Būlio vertė rodo, kad zoologijos sode yra žodyne arba ji gali
atitinka daugiau informacijos, kad mums norite susieti su pagrindine zoologijos sode,
kaip ir apibrėžiant žodis ar kažkas.
Tam tikrais būdais, procesas įterpti kažkas į TRIE yra panašus į
žiūrint ką nors per TRIE.
>> Pradėsime nuo šaknų mazgas vėl, Šie patarimų, atitinkantis
Mūsų raktas raidės.
Laimei, mums pavyko laikytis patarimų visą kelią, kol pasiekė
rakto galas.
Kadangi zoologijos sodas yra žodžio priešdėlis priartinimas, kuris yra narys
žodyną, mes nereikia skirti jokių naujų mazgų.
>> Mes gali keisti mazgas rodo, kad simbolių pirmaujančių į kelias
ji yra mūsų žodyne klavišą.
Dabar pabandykime įterpiant raktas PIRTIS į TRIE.
Pradėsime nuo šakninio mazgo ir vėl vykdykite nurodymus.
Bet šioje situacijoje, mes paspauskite miręs pabaigą, kol mes galėsime gauti
pabaigos klavišą.
Dabar, mes turime skirti keletą naujų mazgai turės skirti vienas naujas
mazgas kiekvienas likęs laiškas mūsų raktą.
>> Tokiu atveju, mes tiesiog reikia skirti vieną naują mazgą.
Tada mes turime padaryti H puslapis nuoroda šią naują mazgas.
Dar kartą, mes galime pakeisti mazgas rodo, kad simbolių kelias
todėl jai atstovauja raktas į mūsų žodyną.
Leiskite samprotauti apie asimptotinis sudėtingumas mūsų procedūras jie
dvi operacijos.
>> Pastebime, kad abiem atvejais skaičius iš žingsnius mūsų algoritmas paėmė buvo
proporcingas skaičius raidės raktinį žodį.
Tai tiesa.
Jei norite ieškoti žodį trie tereikia pakartoti per
raidės po vieną, kol jums arba pasiekti žodžio pabaigoje arba
pasiekė aklavietę į TRIE.
>> Ir kai jūs norite įterpti mygtuką vertė pora į TRIE naudojant
procedūra aptarėme, blogiausiu atveju bus jums skiriant naują mazgas
už kiekvieną laišką.
Ir mes manyti, kad paskirstymas yra pastovus laikas operacija.
Taigi, jei mes manome, kad rakto ilgis yra apriboti nustatytą konstantą, tiek
intarpas ir ieškoti yra pastovus laiko operacijose TRIE.
>> Jei mes ne pateikti šią prielaidą, kad rakto ilgis yra apribota fiksuoto
pastovus, tada įkišimo ir ieškoti, blogiausiu atveju yra tiesinis
ilgis klavišą.
Atkreipkite dėmesį, kad laikyti daiktų skaičius į TRIE neturi įtakos ieškoti
ar įterpimo laikas.
Tai įtakos tik ilgis klavišą.
>> Priešingai, pridedant įrašus, tarkim, maišos lentelė yra linkęs padaryti
ateitis ieškoti lėčiau.
Nors tai gali atrodyti patrauklus, pirmiausia, turėtume nepamiršti, kad
palankus asimptotinis sudėtingumas nėra reiškia, kad praktikoje duomenis
struktūra yra neišvengiamai nepriekaištingas.
Mes taip pat turime manyti, kad laikyti žodis į TRIE turime, blogiausiu
atveju, mazgų skaičius proporcingas su žodžiu pati ilgio.
>> Tries linkę naudoti daug vietos.
Štai priešingai maišos lentelės kur mes tik reikia vieną naują mazgą
laikyti kai kurių pagrindinių vertės porą.
Dabar vėl teoriškai, didelė erdvė vartojimas neatrodo kaip didelė
spręsti, ypač turint omenyje, kad modernios kompiuteriai turi gigabaitų ir
gigabaitų atminties.
Tačiau paaiškėja, kad mes vis dar turime nerimauti atminties ir
organizacija vardan efektyvumą, nes šiuolaikiniai kompiuteriai
turėti mechanizmus, pagal dangtis pagreitinti atminties galimybes.
>> Tačiau šie mechanizmai veikia geriausiai, kai atminties užklausų gaminami kompaktiškas
regionuose ar teritorijose.
Ir tam TRIE mazgus gali gyventi bet tos krūvos.
Tačiau tai yra kompromisai kad mes turime apsvarstyti.
>> Atminkite, kad, renkantis duomenis struktūrą tam tikrą užduotį, mes
reikia galvoti apie tai, kas rūšių operacijos duomenų struktūra turi
parama ir kiek veiklos vienas iš tų,
operacijos yra svarbi mums.
Šios operacijos gali net peržengia tiesiog
Pagrindinė ieškoti ir įterpimas.
Tarkime, mes norime įgyvendinti natūra auto-pilnas funkcionalumas, daug
kaip "Google" paieškos sistema veikia.
Tai yra, grąžinti visus raktus ir potencialiai vertybės
turėti tam tikrą priedėlį.
>> Trie vienareikšmiškai naudinga šiai operacijai.
Tai paprasta pakartoti per kiekvieno charakterio trie
prefiksas.
Tiesiog kaip ieškoti operacijos galėtume sekti nurodymus
požymis pobūdžio.
Tada, kai mes atvykti į pabaigos priešdėlis, galime pakartoti per
Likusi duomenų struktūros nes bet raktus po
šis punktas turi priešdėlį.
>> Tai taip pat lengva gauti šį įrašą abėcėlės tvarka nuo
elementai vaikų masyvo yra rikiuojami pagal abėcėlę.
Taigi tikiuosi jums apsvarstyti davimas bando pabandyti.
Aš Kevin Schmid, ir tai yra CS50.
>> Ak, tai pradžia iš nuosmukio.
Aš atsiprašau.
Atsiprašau.
>> Strike keturis.
Aš iš.
Atsiprašau.
Atsiprašome už tai, kad asmuo, kuris turi redaguoti šį išprotėti.
>> Atsiprašau.
Atsiprašau.
>> GARSIAKALBIS 1: Well done.
Tai buvo tikrai gerai padaryta.