>> KEVIN SCHMID: Včasih, ko izgradnji Program, boste morda želeli uporabiti
struktura podatkov, znano kot slovar.
Slovar preslika ključe, ki so Ponavadi strune, vrednotam, ints,
znakov, kazalec na nekem predmetu, karkoli hočemo.
To je tako kot navadne slovarjev da karta besede skozi pojmov.
>> Slovarji nam zagotavljajo sposobnost za shranjevanje podatkov
povezana z nečim in ga poglej gor kasneje.
Torej, kako bomo dejansko izvajati slovar, recimo, oznako C, da smo lahko
uporabi v eni od naših programov?
No, obstaja veliko načinov, da smo lahko izvaja slovar.
>> Za eno, bi lahko uporabili matriko, ki smo dinamično ponovno velikosti ali bi lahko uporabili
povezani seznam, razpršena tabela ali dvojiško drevo.
Toda karkoli bomo izbrali, bi morali ne sme pozabiti na učinkovitost in
uspešnost izvajanja.
Morali bi razmišljati o algoritmu, uporabljenem vstaviti in poiskati elemente v
naša podatkovna struktura.
>> Za zdaj predpostavimo, da smo želite uporabiti strune kot ključi.
Spregovorimo o eni možnosti, struktura podatkov, ki se imenuje Trsta.
Torej, tukaj je vizualna predstavitev iz Trsta.
>> Kot slika pove, Trie je podatkovna struktura drevo z
vozlišča med seboj povezani.
Vidimo, da obstaja jasno koren vozlišče z nekaj povezav razširitvi
druga vozlišča.
Toda kaj vsako vozlišče je sestavljen iz?
Če predpostavimo, da bomo shranjevanje ključev s samo abecednih znakov,
nam ni mar za kapitalizacijo, tukaj je definicija vozlišča, ki
bo zadostovalo.
>> Objekt, katerega tip je struct vozlišče ima dva dela
imenovano podatke in otroke.
Pustili smo, podatkovni del kot komentar zamenjati z elementom
Izjava ko je struct node vključene v program C.
Del podatkov vozlišča lahko Boolova vrednost, ki označuje, ali
Ne vozlišče predstavlja zaključek A slovarju ključa ali pa bi bilo
Niz, ki predstavlja definicijo besede v slovarju.
>> Bomo uporabili smeška, ki označuje kadar so podatki prisoten v vozlišču.
Obstaja 26 elementov v našem otroci matrika, en indeks
Na črko.
Bomo videli pomen to kmalu.
>> Greva bližje pogled na korenski vozel v našem diagramu, ki nima podatkov
povezano z njo, kot kaže Odsotnost smeška v
podatkovni odsek.
Puščice razprostira od delov otroci matrike predstavljajo ne-vozlišče
kazalci na drugih vozlišč.
Na primer, puščica se razteza od Drugi element otrok
predstavlja črko B v slovarju ključ.
In v širši sliki jo označimo z B.
>> Upoštevajte, da v večjem diagram, ko smo pripravi kazalec na naslednje vozlišče, da
Ni važno, če ost izpolnjuje to drugo vozlišče.
Naš slovar vzorec vsebuje Trie dve besedi, ki in zoom.
Oglejmo si primer gledal podatke za ključ.
>> Recimo, da smo želeli poiskati ustreza vrednosti za ključne kopel.
Začeli bomo naš pogled navzgor na korenski vozel.
Potem bomo vzeli prvo črko našega Ključ, B in najti ustrezen
opaziti v naših otrok array.
Obvestilo, da obstajajo natanko 26 vložki v matriki, ena za vsako dopisom z dne
abeceda.
In bomo imeli lise predstavljajo črke abecede v redu.
>> Bomo pogled na drugo indeksa takrat, Indeks eno, za B. Na splošno, če smo
nekaj črko C smo lahko določi ustrezno mesto
V otroški niza z uporabo Izračun takole.
Lahko bi bila uporabljena večja otroke matrika, če smo želeli ponuditi look up
Tipke s širšo paleto likov, kot celotnega
Nabor znakov ASCII.
>> V tem primeru se kazalec V naši otroci paleto na
Indeks ena ni nič.
Torej bomo še naprej iskali do ključa kopeli.
Če bomo kdaj naleteli null kazalec na ustrezno mesto v otroke
Niz medtem ko prečka vozlišča, potem bomo morali reči, da smo
ni mogel najti ničesar za ta ključ.
>> Zdaj bomo vzeli drugo pismo naš ključ, in nadaljujte po
kazalci na ta način, dokler ne bomo pridete do konca našega ključa.
Če želimo priti do konca ključa brez hitting koli slepih ulic, null kazalci,
kot je primer tukaj, potem pa samo morali preveriti še eno stvar.
To je osnovni pogoj dejansko v slovarju?
>> Če je tako, bi morali najti vrednost, ter nasmejan obraz ikona v našem diagramu, kjer
beseda konča.
Če je kaj drugega shranijo podatki, potem bomo lahko vrnili.
Na primer, ključ zoo ni slovar, čeprav bi lahko imeli
dosegel konec tega ključa ne da bi kdaj hitting null kazalec, medtem ko smo
ponovitev prek Trsta.
>> Če bomo poskušali poiskati ključno kopel, Drugi indeks matrike lanskega vozlišča,
ustreza črko H, bi so potekala null kazalec.
Torej kopel je ni v slovarju.
In tako Trie je edinstven v tem, da ključi nikoli izrecno shranjeni v
struktura podatkov.
Torej, kako bomo nekaj vstavili v Trsta?
>> Oglejmo vstavite ključ zoo v našo Trsta.
Ne pozabite, da smeško na vozlišču lahko ustrezajo v kodo na preprost
Boolova vrednost, ki označuje, da je živalski vrt je v slovarju ali pa bi
ustrezajo več informacij, ki jih želijo povezati s ključno živalskem vrtu,
kot opredelitev beseda ali kaj drugega.
V nekaterih pogledih je postopek za vstavljanje Nekaj ​​v Trsta je podobna
gledal nekaj v Trsta.
>> Bomo začeli s korensko vozlišče spet, Naslednji kazalci ustreza
črke naše ključa.
Na srečo smo bili sposobni slediti kazalci vso pot, dokler ne bomo dosegli
Konec ključa.
Ker zoo je predpona besede Povečava, ki je član
slovar, mi ni treba dodeliti nobenih novih vozlišč.
>> Mi lahko spremenite vozlišče, kažejo, da Pot znakov, ki vodijo do
predstavlja ključ v našem slovarju.
Zdaj pa poskusite vstaviti Ključ KOPEL v Trsta.
Začeli bomo v korenskem vozlišču in spet sledi kazalca.
Toda v tej situaciji, smo zadeli mrtvih na koncu, preden bomo lahko prišli do
Konec ključa.
Zdaj bomo morali dodeliti nekatere nove vozlišča bodo morali dodeliti eno novo
vozlišče za vsako preostalo pismo našega ključa.
>> V tem primeru smo morali dodeliti eno novo vozlišče.
Potem bomo morali narediti indeks H reference to novo vozlišče.
Še enkrat, lahko spremenite vozlišče, kažejo, da je pot znakov
vodi k njej predstavlja Ključ v našem slovarju.
Oglejmo razlog o asimptotska kompleksnost naših postopkov za te
dve operaciji.
>> Opazili smo, da je v obeh primerih število od korakov naš algoritem je bil tvoj
sorazmerna s številom črke v besedo.
To je res.
Ko želite poiskati besedo v Trie morate le Ponovil skozi
črke enega po enega, dokler ne boste niti pridete do konca besede ali
udaril slepo ulico v Trsta.
>> In ko želite vstaviti ključ Vrednost par v Trsta uporabo
Postopek smo razpravljali, je najslabši boste imeli dodeljevanje novo vozlišče
Za vsako črko.
In bomo predpostavimo, da dodelitev je stalnica delovanja časa.
Torej, če predpostavimo, da je dolžina ključa omejen s fiksnim konstanto, tako
vstavljanje in poglej gor so konstantne čas operacije za Trsta.
>> Če ne bomo to predpostavko, da dolžina ključa je vezano na fiksni
konstanten, nato pa vstavitev in poglej gor, v najslabšem primeru, linearna
Dolžina ključa.
Opazimo, da število kosov shranjujejo V Trsta, ne vpliva na videz up
ali čas vstavitve.
To je vplivalo le s Dolžina ključa.
>> Nasprotno, dodajanje vnosov, recimo, hash tabela kaže, da bi
Prihodnost poglej gor počasnejši.
Čeprav je to morda zveni privlačno na prvi, moramo imeti v mislih, da
ugodna asimptotska kompleksnosti ne pomeni, da v praksi podatkov
Struktura je nujno ne more očitati ničesar.
Upoštevati moramo tudi, da za shranjevanje Beseda v Trsta moramo, v najslabšem
Zadeva, število vozlišč sorazmerna na dolžino besede same.
>> Poskuša ponavadi uporabljajo veliko prostora.
To je v nasprotju z znakom tabeli kjer potrebujemo le eno novo vozlišče
shranite nekaj par ključev vrednosti.
Zdaj pa spet v teoriji, velik prostor poraba ne zdi velik
obravnavati, še zlasti, ker sodobna računalniki imajo gigabajtov in
gigabajta pomnilnika.
Ampak se je izkazalo, da imamo še vedno skrbeti za spomin navada in
Organizacija zavoljo uspešnosti, saj sodobni računalniki
vzpostavili mehanizme pod hood, da se pospeši dostop do pomnilnika.
>> Vendar ti mehanizmi delujejo najbolje, ko pomnilniških dostopov so izdelani v kompaktni
regije ali območja.
In vozlišča v Trsta lahko prebivajo kjerkoli v tem kupu.
Vendar so ti kompromisi da moramo upoštevati.
>> Ne pozabite, da pri izbiri podatkov Struktura za določeno nalogo, smo
bi morali razmišljati o tem, kaj vrste Operacije podatkovna struktura mora
podpora in koliko uspešnost vsakega izmed tistih,
Operacije je za nas pomembno.
Lahko ti postopki še presegajo samo
osnovni pogled in vstavljanje.
Recimo, da smo želeli izvesti vrsto auto-popolna funkcionalnost, veliko
kot je Google iskalnik ne.
To pomeni, da vrne vse ključe in potencialno vrednote, ki
imeti določen predpono.
>> Trie je edinstveno uporabno Za to operacijo.
To je enostaven za ponovitev prek Trie za vsako značaja
predpona.
Tako kot pogledate operacijo, smo lahko sledili napotke
znak za znakom.
Potem, ko smo prispeli do konca leta predpona, bi lahko ponovitev prek
Preostali del strukture podatkov saj vsaka od ključev preko
ta točka še predpono.
>> Prav tako je težko dobiti ta vnos po abecednem vrstnem redu, saj
elementi otrok niz so urejene po abecedi.
Torej, upam, da si bom premislil dajanje poskuša poskusiti.
Jaz sem Kevin Schmid, in to je CS50.
>> Ah, to je začetek upada.
Žal mi je.
>> Stavke štiri.
Jaz sem ven.
Žal mi je.
Žal mi je za tako osebo, ki je mora urediti to zmešalo.
>> Žal mi je.
Žal mi je.
>> SPEAKER 1: Bravo.
To je bilo res dobro opravljeno.