>> [Musiikki soi]
>> ROB BOWDEN: Hei.
Olen Rob.
Ja nyt tämä ratkaisu ulos.
Joten tässä me aiomme toteuttaa yleinen pöytä.
Näemme, että struct solmu meidän taulukossa on menossa näyttää tältä.
Niin se tulee olla char sana taulukon koko pituus + 1.
Älä unohda + 1, koska suurin sanan sanakirjasta on 45
merkkiä.
Ja sitten me aiomme tarvitsevat yhden ylimääräisen merkin kenoviiva nolla.
>> Ja sitten meidän hashtable kussakin kauha on menossa tallentamaan
linkitetyn listan solmuja.
Emme tee lineaarinen luotaa täällä.
Ja niin, jotta sen yhteys seuraavaan elementti ämpäri, tarvitsemme
struct solmu * seuraavaksi.
OK.
Niin, että mitä solmu näyttää.
>> Nyt tässä ilmoituksessa meidän hashtable.
Se tulee olla 16834 kauhat.
Mutta että numero ei ole oikeastaan ​​väliä.
Ja lopuksi, me aiomme olla globaali muuttuja hashtable koko, joka
aikoo alkajaisiksi kuin nolla.
Ja se tulee seurata, kuinka monet sanat ovat meidän sanakirja.
>> Joten katsotaanpa katsomaan kuormalla.
Huomaa, että kuorman, se palauttaa bool.
Palaat tosi, jos se onnistui ladattu ja vääriä toisin.
Ja se vie const char * sanakirja, joka on sanakirja
että haluamme avata.
Niin, että ensimmäinen asia aiomme tehdä.
>> Aiomme fopen sanakirja lukemiseen.
Ja me aiomme pitäisi tehdä Varmista, että se onnistui.
Joten jos se palautetaan NULL, niin emme onnistuneesti Avaa sanakirja.
Ja meidän täytyy palata vääriä.
Mutta olettaen, että se teki onnistuneesti auki, haluamme lukea
sanakirja.
Joten pitää kiehkura kunnes löydämme syytä murtautua ulos tästä silmukan,
jonka näemme.
Joten pitää kiehkura.
>> Ja nyt me aiomme malloc yhden solmun.
Ja tietysti me tarvitsemme tuuletusta tarkista uudelleen.
Joten jos mallocing ei onnistunut, niin haluamme purkaa tahansa solmuun, että me
tapahtui malloc ennen, sulje sanakirja ja palauttaa false.
Mutta unohdetaan, että vaikka oletettaisiin me onnistunut, niin haluamme käyttää fscanf
lukea sanaakaan meidän sanaston meidän solmuun.
Niin muista, että merkintä> sana on char sana puskurin koko lenghth + 1
että aiomme säilyttää sanan sisään
>> Joten fscanf tulee palata 1, niin kauan sillä se kykeni
lukea sana tiedoston.
Jos jompikumpi virhe tapahtuu, tai me päähän tiedoston, se
ei palaa 1.
Jolloin se ei palaa 1, olemme vihdoin menossa murtautua ulos
Tässä kun silmukka.
Näemme siis, että kun meillä on onnistuneesti lukea sanan
entry> sana, niin aiomme että sana käyttämällä tiivistefunktiota.
>> Katsotaanpa katsomaan hash-funktio.
Joten sinun ei todellakaan tarvitse ymmärtää tätä.
Ja oikeastaan ​​me vain veti tämän hash toimiakseen Internetistä.
Ainoa asia, sinun täytyy tunnustaa, on että tämä vie const char * sana.
Joten se vie narua tulo, ja palaamassa unsigned int tuotokseksi.
Niin, että kaikki hash-toiminto on, on se vie tulo ja antaa sinulle
indeksinä hashtable.
>> Huomaa, että olemme moding by NUM_BUCKETS, jotta palautettu arvo
itse asiassa on indeksinä hashtable ja ei indeksoi yli
rajat array.
Joten koska toiminto, aiomme hash sana, joka luemme
sanakirja.
Ja sitten me aiomme käyttää että hash lisätä
tuloa hashtable.
>> Nyt hashtable hash on nykyinen linkitetty lista taulukossa.
Ja se on hyvin mahdollista että se on vain NULL.
Haluamme lisätä meidän käännyttämiseksi Alussa tämän linkitetyn listan.
Ja niin me aiomme olla nykyiseen alkupisteestä mitä hashtable
tällä hetkellä viittaa.
Ja sitten me aiomme säilyttää, vuonna hashtable osoitteessa
hash, nykyinen tieto.
Joten nämä kaksi riviä onnistuneesti aseta merkintä alussa
linkitetty lista tuohon hakemisto vuonna hashtable.
>> Kun olemme tehneet, että me tiedämme että löysimme toinen sana
sanakirja, ja me kasvattaa uudelleen.
Joten meidän pitää tehdä, että kunnes fscanf palasi lopulta jotain ei-1
missä vaiheessa muistaa, että meidän on vapaa pääsy.
Joten täällä me malloced merkintä.
Ja yritimme lukea jotain sanakirjasta.
Ja emme onnistuttiin lukemaan jotain sanakirjasta vuonna
joka tapauksessa meidän täytyy vapauttaa merkintä että emme koskaan oikeastaan ​​panna
hashtable, ja lopulta murtaa.
>> Kun me puhkeaa meidän täytyy nähdä, hyvin, me puhkeaa, koska siellä
oli virhe luettaessa tiedostoa?
Vai rikomme pois, koska me lopussa tiedoston?
Jos oli virhe, haluamme palata vääriä.
Koska kuormitus ei onnistunut.
Ja samalla haluamme purkaa kaikki sanat, jotka luemme, ja
Sulje sanastotiedostoa.
>> Olettaen emme onnistu, sitten me vain vielä sulkea sanakirja
tiedostoon, ja lopulta palata totta, sillä me ladattu onnistuneesti sanakirja.
Ja se on siinä kuorman.
Joten nyt tarkistaa, koska ladattu hashtable, aikoo näyttää tältä.
Joten tarkista, se palauttaa bool, joka on menossa osoittamaan, onko kulunut
char * sana, onko kulunut merkkijono on meidän sanakirja.
Joten jos se on sanakirjassa, jos se on meidän hashtable,
palaamme totta.
Ja jos se ei ole, palaamme vääriä.
>> Kun otetaan huomioon tämä kulunut sana, olemme menossa hash sana.
Nyt tärkeintä tunnistaa on että kuorman tiesimme, että kaikki
sanat aiomme pieniä kirjaimia.
Mutta täällä emme ole niin varma.
Jos me katsomaan meidän hajautusfunktio, meidän hash-toiminto itse asiassa
on pienempi kotelo kunkin merkin sanan.
Joten riippumatta arvo sana, meidän hash funktio on paluu
sama indeksi jostain -arvo on, koska sillä olisi
palautetaan kokonaan pienillä kirjaimilla versio sanasta.
Okei.
Se on meidän indeksi on osaksi Hashtable sanaa.
>> Nyt tämä silmukka on menossa kerrata yli linkitetty lista
joka oli tuohon indeksi.
Joten huomaat olemme alustetaan merkintä osoittamaan, että indeksiin.
Aiomme jatkaa kun pääsy! = NULL.
Ja muista, että päivittäminen osoitin meidän linkitetty lista entry = entry> seuraavaksi.
Niin on meidän nykyinen yhteys siihen Esityslistalla on linkitetty lista.
>> Joten jokaisen merkinnän linkitetty lista, aiomme käyttää strcasecmp.
Se ei ole strcomp.
Koska jälleen kerran, haluamme tehdä asioita tapauksessa insensitively.
Joten käytämme strcasecmp vertailla sana, joka on läpäissyt tämän
toiminto sanaa vastaan joka on tämän merkinnän.
Jos se palaa nolla, se tarkoittaa, että oli ottelu, jolloin haluamme
return true.
Olemme löytäneet sana meidän hashtable.
>> Jos ei ole ottelu, niin olemme menossa silmukka uudelleen ja katsoa
seuraava merkintä.
Ja jatkamme silmukoiminen vaikka ovat merkintöjä tähän linkitetty lista.
Mitä tapahtuu, jos rikomme pois tästä silmukan?
Tämä tarkoittaa emme löytäneet merkinnän, joka Hyväksytty tämä sana, jolloin
palaamme epätosi ilmaisten, että hashtable ei sisältänyt tätä sanaa.
Ja se tarkistaa.
>> Joten katsotaanpa katsomaan koko.
Nyt koko tulee olemaan melko yksinkertainen.
Koska muistaa kuorman, jokaista sanaa löysimme meillä kasvatetaan maailmanlaajuisen
muuttuja hashtable koko.
Joten koko toiminto on juuri menossa palata globaali muuttuja.
Ja se on siinä.
>> Nyt vihdoin, meidän täytyy purkaa sanakirjassa kerran kaiken tehtyä.
Niin miten me sen teemme?
Täällä olemme silmukoiden yli kaikki ämpärillistä meidän pöytään.
Joten on NUM_BUCKETS kauhat.
Ja kunkin linkitetyn listan meidän hashtable, aiomme lenkki
kokonaisuudessaan linkitetty lista, vapauttaa jokaisen elementin.
>> Nyt meidän on oltava varovaisia.
Joten tässä meillä on väliaikainen muuttuja, joka tallennetaan osoitin seuraavaan
elementti linkitetty lista.
Ja sitten me aiomme ilmaiseksi elementin.
Meidän on oltava varmoja teemme tämän, koska meillä voi vain vapauttaa elementin
ja yritä sitten käyttää seuraavaan osoitin, koska kerran olemme vapautettu, sitä,
muisti mitätöityy.
>> Joten meidän täytyy pitää noin osoitin seuraavan osan, voimme vapauttaa
elementin, ja sitten voimme päivittää nykyinen elementti osoittamaan
seuraavan osan.
Me silmukka, kun on olemassa tekijöitä, Tässä linkitetty lista.
Teemme että kaikilla yhdistetyillä luettelot hashtable.
Ja kun olemme tehneet, että olemme kokonaan purettu hashtable, ja
olemme valmiit.
Joten se on mahdotonta purkaa koskaan palata vääriä.
Ja kun olemme tehneet, me vain palata totta.
>> Annetaanpa tämän ratkaisun yrittää.
Joten katsomaan mitä struct solmu näyttää.
Tässä näemme aiomme olla bool sana ja struct solmu * lasten
kiinnike aakkosia.
Joten ensimmäinen asia, saatat olla ihmettelevät, miksi on AAKKOSITTAIN
ed määritelty 27?
No, muistaa, että olemme menossa tarvitsevat voidaan käsittely heittomerkki.
Niin, että tulee olemaan jokseenkin erikoistapaus koko tähän ohjelmaan.
>> Nyt muista miten triellä todella toimii.
Sanotaan olemme indeksointi sana "Kissat". Sitten juuresta triestä,
olemme menossa katsomaan lapsia array, ja olemme menossa katsomaan
indeksi, joka vastaa kirjeen C. Niin että on indeksoitu 2.
Niin sillä, että tahto antaa meille uuden solmun.
Ja sitten me työskennellä, että solmu.
>> Joten koska solmu, olemme jälleen kerran menossa katsomaan lapsia array.
Ja aiomme tarkastella indeksi nolla vastaamaan kissan.
Niin sitten me aiomme mennä, että solmu, ja koska solmu aiomme
katsomaan lopussa se vastaa T. Ja siirrymme että solmuun,
Lopuksi, olemme täysin huolta kautta sana "kissa." Ja nyt bool
sana on tarkoitus ilmoittaa, onko Tämän tiettyä sanaa on oikeastaan ​​sana.
>> Joten miksi me tarvitsemme, että erikoistapaus?
No mitä sanan "katastrofi" on meidän sanakirja, mutta
sana "kissa" ei ole?
Niin ja katsomatta, jos sana "kissa" on meidän sanakirja, olemme
menossa onnistuneesti katsoa läpi indeksit C--T alueella solmussa.
Mutta se on vain siksi katastrofi tapahtui luoda solmut matkalla
C-A-T, aina sanan lopussa.
Joten bool sanaa käytetään osoittamaan, onko tässä paikassa
todella osoittaa sana.
>> Selvä.
Joten nyt me tiedämme, mitä se triestä on tulee näyttämään, katsokaamme
kuormafunktio.
Joten kuorma aio palata bool Jos me oikein tai
tuloksetta ladattu sanakirja.
Ja tämä tulee olemaan sanakirja että haluamme ladata.
>> Joten ensimmäinen asia, olemme vain avata up, joka sanakirjan lukemiseen.
Ja meidän täytyy varmistaa, emme onnistu.
Joten jos sanakirjassa ei ollut onnistuneesti avattu, se palaa
null, jolloin olemme aio palata vääriä.
Mutta olettaen, että se onnistui avattu, niin voimme todella lukea
kautta sanakirja.
>> Joten ensimmäinen asia aiomme haluat tehdä, on meillä on tämä
globaali muuttuja root.
Nyt root tulee olemaan solmu *.
Se kärkeen triestä että olemme aiotaan iteroimalla läpi.
Joten ensimmäinen asia, että olemme menossa halua tehdä, on jakaa
muisti meidän root.
Huomaa, että käytämme calloc toiminto, joka on periaatteessa sama
kuten malloc funktio, paitsi se on taattu palata jotain, joka on
täysin nollataan.
Jos siis käytetään malloc, meidän olisi käydä läpi kaikki osoittimet meidän
solmu, ja varmista, että he kaikki null.
Joten calloc tekee sen meille.
>> Nyt aivan kuten malloc, meidän täytyy tehdä Varmista, että jako oli oikeastaan
onnistunut.
Jos tämä palasi null, meidän täytyy sulkea tai sanakirja
tiedostoon ja palauttaa false.
Joten olettaen että jako on onnistunut, aiomme käyttää solmuun *
kursorin kerrata kautta triellä.
Joten meidän juuret koskaan muutu, mutta aiomme käyttää kohdistin
itse mennä solmusta toiseen.
>> Joten tässä silmukan Luemme kautta sanastotiedostoa.
Ja käytämme fgetc.
Fgetc aikoo napata yhden hahmo tiedoston.
Aiomme jatkaa tarttumalla merkkiä vaikka emme pääse
tiedoston loppuun.
>> On olemassa kaksi tapausta meidän täytyy käsitellä.
Ensimmäinen, jos merkki ei ollut uusi rivi.
Joten me tiedämme, jos se oli uusi linja, niin aiomme siirtyä uuden sanan.
Mutta jos se ei ollut uusi linja, niin Tässä haluamme selvittää
index aiomme indeksinä lapsissa array, joka
me katsoimme ennen.
>> Joten, kuten sanoin aiemmin, meidän täytyy erikoistapaus heittomerkki.
Huomaa käytämme ternäärisen operaattori täällä.
Menemme siis lukea tätä, jos merkki luemme oli
heittomerkki, niin aiomme asettaa index = "AAKKOSITTAIN" -1, joka
olla indeksi 26.
>> Else, jos se ei ollut heittomerkki, siellä aiomme asettaa indeksin
yhtä suuri kuin c -.
Joten muistakaa takaisin aiemmin p-sarjaa, c - ei aio antaa meille
aakkosjärjestyksessä C. Joten jos C on kirjain, tämä tulee
antaa meille indeksi nolla.
Kirjain B, se antaa meille indeksi 1, ja niin edelleen.
>> Joten tämä antaa meille indeksinä lasten array että haluamme.
Nyt jos tämä indeksi on tällä hetkellä null lapset, se tarkoittaa, että solmu
ei vielä ole alkaen, että polku.
Joten meidän täytyy kohdentaa solmun polun.
Sitähän me teemme täällä.
>> Joten aiomme taas käyttää calloc toiminto, jotta meidän ei tarvitse
nolla pois kaikki osoittimet.
Ja me taas täytyy tarkistaa että calloc ei epäonnistunut.
Jos calloc ei onnistu, meidän purkaa kaiken, sulkea
sanakirja, ja palauttaa false.
Niin olettaen, että se ei ole jättänyt, niin tämä luo uuden lapsen meille.
Ja sitten menemme että lapsi.
Meidän osoitin kerrata tuolle lapselle.
>> Nyt jos tämä ei null aluksi, Sitten osoitin voi vain kerrata
alas, että lapsi ei itse ottaa jakaa mitään.
Tämä on tapaus, jossa ensin tapahtui jakaa sana "kissa." Ja
se tarkoittaa, että kun menemme kohdentaa "Katastrofi", meidän ei tarvitse luoda
solmut C-A-T uudelleen.
Ne ovat jo olemassa.
>> Mikä on tämä muuta?
Tämä on sairaus, jossa C kenoviiva n, missä c on uusi rivi.
Tämä tarkoittaa, että olemme onnistuneet valmistunut sana.
Nyt mitä haluamme tehdä, kun me suorittanut sana?
Aiomme käyttää tätä sanaa alalla sisällä meidän struct solmu.
Haluamme asettaa, että totta.
Niin, joka osoittaa, että tämä solmu osoittaa onnistuneen
sana, todellinen sana.
>> Nyt asetettu, että totta.
Haluamme palauttaa meidän kohdistin pisteeseen alkuun trien uudelleen.
Ja lopuksi, kasvattaa meidän sanakirja koko, koska löysimme toisen teoksen.
Joten aiomme pitää tehdä, että lukeminen merkki merkiltä,
rakentamalla uusia solmuja meidän triessä ja jokaisen sanan sanakirjasta, kunnes
me lopulta saavuttaa C! = EOF, jossa tapauksessa meidän murtautumaan ulos tiedoston.
>> Nyt on kaksi tapausta alle jotka olisimme osuma EOF.
Ensimmäinen on, jos siellä oli virhe lukemisen tiedoston.
Joten jos oli virhe, me täytyy tehdä tyypillinen.
Purkaa kaiken, lähellä tiedosto, palauttaa false.
Olettaen ei ollut virhe, joka tarkoittaa vain me itse osui lopussa
tiedosto, jolloin suljemme tiedostoon ja palauttaa totta, sillä me
ladattu onnistuneesti sanakirja meidän trie.
>> Joten nyt Katsotaanpa tarkistaa tarkistaa.
Tarkasteltaessa toiminnanvalvonnassa, näemme että tarkastus aio palata bool.
Se palauttaa true, jos tämä sana, se on siirrellään on meidän triessä.
Se palauttaa false muuten.
Joten miten voit selvittää, tämä sana on meidän triestä?
>> Näemme tässä, että aivan kuten ennen, aiomme käyttää kohdistin kerrata
kautta trie.
Nyt olemme menossa kerrata yli koko sanan.
Joten iteroimalla yli sana olemme aiemmin, aiomme selvittää
indeksinä lapset array, joka vastaa sanaa teline I. Joten tämä
tulee näyttämään täsmälleen samalta kuin kuormitus, jossa jos sana [i]
on heittomerkki, niin haluamme käyttää indeksi "AAKKOSITTAIN" - 1.
Koska olemme päättäneet, että että on, jos aiomme säilyttää
heittomerkit.
>> Else aiomme käyttää kahta alempaa sanaa kiinnike I. Joten muistakaa, että sana voi
on mielivaltainen arvo.
Ja niin me haluamme varmistaa, että olemme käyttämällä pieniä versio asioista.
Ja vähennä siitä "" kerran taas antaa meille aakkosjärjestyksessä
asemaa tämän merkin.
Niin, että tulee olemaan meidän indeksi osaksi lasten array.
>> Ja nyt jos indeksinä lapsia matriisi on nolla, se tarkoittaa, että me
voi enää jatkaa iteroimalla alas meidän trie.
Jos näin on, tämä sana voi mahdollisesti olla meidän triessä.
Koska jos se olisi, että olisi tarkoittaa ei olisi polku
alas, että sana.
Ja et koskaan kohdata null.
Joten kohtaaminen null, palaamme vääriä.
Sanaa ei ole sanakirjassa.
Jos se ei ole tyhjä, niin olemme tulee jatkumaan iteroimalla.
>> Menemme siis siellä kohdistin huomauttaa, että erityisesti
solmu, että indeksi.
Meidän pitää tehdä, että koko koko sana, olettaen
emme koskaan lyönyt null.
Se tarkoittaa, että pystyimme saamaan läpi koko sanan ja löytää
solmu meidän yrittää.
Mutta emme ole aivan vielä valmis.
>> Emme halua vain palata totta.
Haluamme palata kursori> sana.
Koska muistan taas, on "kissa" ei meidän sanakirja, ja "katastrofi"
on, niin me onnistuneesti saamme kautta sana "kissa." Mutta osoitin
sana on väärä ja ei ole totta.
Joten palaamme kursori tarkoittava sana onko tämä solmu on todella sana.
Ja siinä se lähtöselvitykseen.
>> Joten tarkistaa koko.
Joten koko tulee olemaan melko helppoa koska muistaa kuormitus, olemme
monesko sanakirja koko jokainen sana, että törmäämme.
Joten koko on juuri menossa palata sanakirjan koko.
Ja se on siinä.
>> Joten lopuksi olemme purkaa.
Joten purkaa, aiomme käyttää rekursiivinen funktio itse tehdä kaikki
työn meille.
Joten meidän tehtävämme on menossa voidaan kutsua unloader.
Mitä unloader aiot tehdä?
Näemme tässä, että purkaimen on menossa kerrata hoitaakseen kaikki lasten
tässä solmussa.
Ja jos lapsi solmu ei ole null, niin aiomme
purkaa lapsi solmu.
>> Joten tämä on sinulle rekursiivisesti purkaa kaikki lapsemme.
Kun olemme varmoja, että kaikki lapsemme on purettu, niin me
voi vapauttaa itsemme, niin purkaa itseämme.
Tämä toimii rekursiivisesti purkaa koko triessä.
Ja sitten kun se on tehty, voimme vain palata totta.
Kevennys ei voi epäonnistua.
Me vain vapauttaa asioita.
Joten kun olemme tehneet vapauttaa kaiken, return true.
Ja se on siinä.
Nimeni on Rob.
Ja tämä oli speller.
>> [Musiikki soi]