[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]