>> KEVIN SCHMID: Joskus, kun rakennus ohjelma, sinun kannattaa käyttää
tietojen rakenne tunnetaan sanakirja.
Sanakirja kartat avaimet, jotka ovat yleensä jouset, arvoihin, ints,
merkkiä, osoitin jonkin esineen, mitä haluamme.
Se on aivan kuin tavallinen sanakirjoja että kartta sanansa määritelmiä.
>> Sanakirjoja meille kyky tallentaa tietoja
liittyy jotain ja etsiä se myöhemmin.
Miten siis käytännössä soveltamaan sanakirja vaikkapa C-koodia, että voimme
käyttää yksi meidän ohjelmia?
No, on olemassa paljon tapoja, jotka voisimme toteuttaa sanakirja.
>> Yhden, voisimme käyttää array että me dynaamisesti uudelleen koko tai voisimme käyttää
linkitetty lista, tiiviste tai binääripuu.
Mutta mitä me valitsemme, meidän pitäisi olla tietoinen tehokkuuden ja
suorituskykyä täytäntöönpanoa.
Meidän pitäisi ajatella käytetty algoritmi lisätä ja etsiä kohteet
meidän tietorakenne.
>> Nyt Oletetaan, että meillä haluat käyttää merkkijonojen avaimina.
Puhutaanpa yksi mahdollisuus, data rakennetta kutsutaan triellä.
Joten tässä on visuaalisesti of trie.
>> Kuten kuvasta voi päätellä, triellä on puu datarakennetta
solmut liittyvät toisiinsa.
Näemme, että siellä on selvästi root solmu joitakin yhteyksiä ulottuu
muut solmut.
Mutta mitä kukin solmu koostuu?
Jos oletamme, että olemme tallentaa avaimet vain kirjaimia ja
emme välitä arvo, tässä on määritelmä solmu, joka
riittää.
>> Objektin, jonka tyyppi on struct solmulla on kaksi osaa
nimeltään tietojen ja lapsia.
Olemme jättäneet dataosa kommenttina korvataan osa
ilmoitusta, jos struct solmu on sisällytetty C-ohjelma.
Tieto-osa solmu voi olla Boolean arvo, joka ilmaisee, onko
ei solmu edustaa loppuun sanakirjan avaimen tai se voi olla
string edustavat määritelmän sanan sanakirjasta.
>> Käytämme hymiö kasvot osoittamaan kun data on läsnä solmussa.
On 26 elementtejä meidän lasten joukko, yksi indeksi
per kirjain.
Näemme merkitystä tämän pian.
>> Mennään lähemmin juurisolmun meidän kaaviossa, joka ei ole tietoja
liittyy siihen, kuten on esitetty Koska hymiö kasvot
tieto-osan.
Nuolet, jotka ulottuvat osista lapset array edustavat ei-solmun
viitteitä muihin solmuihin.
Esimerkiksi nuoli ulottuu toinen elementti lasten
edustaa kirjain B sanakirjasta näppäintä.
Ja suurempi kaaviossa merkitsemme sen B.
>> Huomaa, että suurempi kaaviossa, kun piirtää osoittimen toiseen solmuun, se
ei ole väliä missä nuolenkärki täyttää, että muut solmu.
Meidän näyte sanakirja triestä sisältää kaksi sanaa, jotka ja zoom.
Käydään läpi esimerkki etsii tietoja avaimen.
>> Oletetaan halusimme etsiä vastaava arvo avaimen kylpy.
Aloitamme meidän look up juurisolmusta.
Sitten otamme ensimmäisen kirjaimen meidän näppäintä, B, ja löytää vastaava
Spot lapsemme array.
Huomaa, että on olemassa täsmälleen 26 paikkoja array, yksi kutakin kirjeellä
aakkoset.
Ja meillä on paikkoja edustavat aakkosten järjestyksessä.
>> Me tarkastelemme toisen indeksin sitten indeksi yhdestä, B. Yleensä, jos me
on joitakin kirjain C me voisi määrittää vastaavan paikalla
lapsissa array laskelma näin.
Olisimme voineet käyttää isommille lapsille array jos halusimme tarjota look up
näppäimet, joilla on laajempi valikoima merkkejä, kuten koko
ASCII-merkistön.
>> Tässä tapauksessa osoitin lapsemme array at
indeksi yksi ei ole nolla.
Niin me etsimme edelleen ylös-näppäintä kylpyamme.
Jos me koskaan kohdannut nollaosoittimen oikeassa paikalla lapsia
array kun me kulki solmut, Sitten meidän täytyy sanoa, että me
ei löytänyt mitään, että avain.
>> Nyt otamme toisen kirjeellä keskeisiä, ja jatka noudattaen
viitteitä tällä tavoin, kunnes me päähän keskeisiä.
Jos me päähän avaimen ilman lyödä mitään umpikujia, null osoittimia,
kuten tässä tapauksessa, niin me vain täytyy tarkistaa yksi asia.
Onko tämä avain todella sanakirjassa?
>> Jos näin on, meidän pitäisi löytää arvo, hyvin hymiö ilme meidän kaavio, jossa
sana päättyy.
Jos on jotain muuta tallennetaan tietoa, niin voimme palauttaa sen.
Esimerkiksi avain eläintarha ei ole sanakirja, vaikka olisimme voineet
lopussa tämän keskeisen ilman koskaan lyömällä nollaosoittimen, kun me
kerrata trien läpi.
>> Jos yritimme etsiä avain kylpyamme, toiseksi viimeinen solmun taulukkoindeksin,
vastaava kirjain H, olisi ovat pitäneet nollaosoittimen.
Joten kylpy ei ole sanakirjassa.
Ja niin trien on ainutlaatuinen siinä, että avaimet ei koskaan nimenomaisesti tallennetaan
tietorakennetta.
Miten siis lisätä jotain osaksi triestä?
>> Katsotaanpa aseta avain Eläintarha meidän triellä.
Muista, että hymiö kasvot solmussa voisi vastaavat koodin yksinkertainen
Boolean joka osoittaa, että eläintarha löytyy sanakirjasta tai se voi
vastaavat enemmän tietoa, joka meillä haluavat yhdistää avaimen eläintarha,
kuten määritelmä sana tai jotain muuta.
Jollain tavalla, prosessi lisätä jotain osaksi trien on samanlainen kuin
etsii jotain triellä.
>> Aloitamme juurisolmu uudelleen, seuraavia viitteitä vastaa
kirjaimet keskeisiä.
Onneksi pystyimme seuraamaan viitteitä aina kunnes saavuimme
avaimen päätä.
Koska eläintarha on etuliite sanan zoom, joka on jäsenenä
sanakirja, meidän ei tarvitse jakaa uusia solmuja.
>> Sitä voidaan muokata solmu osoittaa, että polku merkkiä, joka johtaa
se on keskeinen meidän sanakirja.
Nyt, kokeile asettaa avain kylvystä triessä.
Aloitamme klo juurisolmu ja seuraa viitteitä uudelleen.
Mutta tässä tilanteessa, osuimme kuollut päättyä ennen pystymme päästä
avaimen päätä.
Nyt meidän täytyy jakaa joitakin uusia solmut tarvitse varata yhden uuden
solmu jokaisen jäljellä kirjeellä keskeisiä.
>> Tässä tapauksessa meidän täytyy vain jakaa yhden uuden solmun.
Sitten meidän täytyy tehdä H-indeksi viite tähän uuteen solmuun.
Jälleen kerran voimme muuttaa solmun osoittavat, että polku merkkiä
mikä se edustaa avain meidän sanakirja.
Katsotaanpa päättelemään asymptoottinen monimutkaisuus meidän menettelyt näitä
kaksi operaatiota.
>> Huomaamme, että molemmissa tapauksissa numero vaiheiden algoritmimme kesti oli
verrannollinen määrä kirjaimet avainsanan.
Aivan oikein.
Kun haluat etsiä sanan triestä sinun tarvitsee vain kerrata kautta
kirjaimet yksitellen, kunnes joko päähän sanan tai
jemmassa triessä.
>> Ja kun haluat lisätä avaimen arvopari osaksi trie käyttäen
menettelyn keskustelimme, pahimmassa tapauksessa on sinulle jaettaessa uusi solmu
jokaista kirjainta.
Ja oletamme, että jako on jatkuvasti ajan toimintaa.
Jos siis oletetaan, että avaimen pituus on jota rajoittaa kiinteä vakio, sekä
sijoittelua ja etsiä ovat vakioita aika operaatioita triellä.
>> Jos emme tee tätä oletusta, että avaimen pituus rajoittuu kiinteään
vakio, niin sijoittelua ja etsiä, pahimmassa tapauksessa, on lineaarinen
avaimen pituus.
Huomaa, että kohteiden määrää tallennettu triessä ei vaikuta look up
tai asetettiin paikoilleen.
Se on vain vaikutti avaimen pituus.
>> Sen sijaan lisätään merkintöjä, vaikkapa hash table taipumus tehdä
tulevaisuudessa etsiä hitaammin.
Vaikka tämä saattaa kuulostaa houkuttelevalta aluksi, meidän pitäisi pitää mielessä, että
suotuisa asymptoottinen monimutkaisuus ei tarkoittaa, että käytännössä data
rakenne on välttämättä arvostelun yläpuolella.
Meidän on myös otettava huomioon, että tallentaa sana triestä tarvitsemme pahimmassa
Tällöin solmujen verrannollinen pituuden sana itse.
>> Yrittää taipumus käyttää paljon tilaa.
Se on toisin kuin hash-taulukko, missä meidän tarvitsee vain yhden uuden solmun
tallentaa joitakin keskeisiä arvopari.
Nyt, jälleen teoriassa, suuri tila kulutus ei tunnu iso
käsitellä, varsinkin kun nykyaikaisen tietokoneissa on gigatavua ja
gigatavua muistia.
Mutta näyttää siltä, ​​että meillä on vielä murehtia muistin käyttöä ja
organisaatio vuoksi suorituskykyä, koska nykyiset tietokoneet
käytössä järjestelyjä alle huppu nopeuttaa muistin käyttöön.
>> Mutta nämä mekanismit toimivat parhaiten, kun muistin vierailuja tehdään kompakti
alueita tai vyöhykkeitä.
Ja solmut trien voisi sijaita missä tahansa, että kasaan.
Mutta nämä ovat kompromisseja että meidän on pohdittava.
>> Muista, että valitessaan tiedot rakenne tiettyjä tehtäviä varten, me
pitäisi ajatella siitä, millaisia toiminnan tietorakenne on
tukea ja kuinka paljon suorituskykyä kunkin tällaisen
toiminnot asioita meille.
Nämä toiminnot voivat jopa ulottua vain
perus ilme ja paikoilleen.
Oletetaan halusimme toteuttaa eräänlainen Auto-kaikki toiminnot, paljon
kuten Google-hakukone tekee.
Eli palauttaa kaikki avaimet ja mahdollisesti arvot, jotka
on annettu etuliite.
>> Triestä on ainutlaatuisen käyttökelpoinen tähän operaatioon.
Se on yksinkertaista iteroitava triestä kunkin merkin
etuliite.
Aivan kuten etsiä toimintaa, voisimme seurata viitteitä
merkki kerrallaan.
Sitten, kun tulemme lopussa etuliite, voisimme kerrata läpi
jäljellä oleva osa datarakenteen koska kaikki avaimet yli
Tässä vaiheessa on etuliite.
>> Se on myös helppo saada tietoja aakkosjärjestyksessä vuodesta
osia lasten array ovat aakkosjärjestyksessä.
Joten toivottavasti sinun harkita antaminen yrittää yrittää.
Olen Kevin Schmid, ja tämä on CS50.
>> Ah, tämä on alku lasku.
Olen pahoillani.
Anteeksi.
>> Lakko neljä.
Minä häivyn.
Anteeksi.
Sorry tehdä henkilö, joka on muokata tätä hulluksi.
>> Anteeksi.
Anteeksi.
>> SPEAKER 1: Hyvin tehty.
Se oli todella hyvin tehty.