ROB BOWDEN: Hei. Olen Rob, ja lähdetään hash tämä ratkaisu ulos. Joten tässä me aiomme toteuttaa yleinen hash table. Näemme, että struct solmu meidän hash taulukossa on menossa näyttää tältä. Niin se tulee olla char sana taulukon koko pituus plus 1. Älä unohda 1 koska suurin sanan sanakirjasta on 45 merkkejä, ja sitten me aiomme tarvitset enää yhden merkin kenoviiva 0. 

Ja sitten meidän tiiviste 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. Niin, että mitä solmu näyttää. Nyt tässä ilmoituksessa meidän tiiviste. Se tulee olla 16384 kauhat, mutta että määrä ei ole niin väliä. Ja lopuksi, me aiomme olla globaali muuttuja hashtable_size, joka aikoo alkajaisiksi kuin 0, ja se on aio pitää kirjaa siitä, kuinka monta sanaa olivat meidän sanakirja. Selvä. 

Joten katsotaanpa katsomaan kuormalla. Niin huomaa, että kuormitus, se palauttaa bool. Palaat tosi, jos se onnistui ladattu ja vääriä toisin. Ja se vie const char * tähden sanakirja, joka on sanakirja että haluamme avata. Niin, että ensimmäinen asia aiomme tehdä. Aiomme fopen sanakirja lukeminen, ja me aiomme olla varmista, että se onnistui niin jos se palasi 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ä silmukka, joka näemme. Joten pitää kiehkura, ja nyt olemme menossa to malloc yhden solmun. Ja tietenkin, meidän täytyy virhetarkistusarvot uudelleen joten jos mallocing ei onnistunut ja 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ä maahantulo-> sana on char sana puskurin koko pituutta plus joka aiomme Säilytä sana sisään Joten fscanf aikoo palata 1 niin kauan sillä se kykeni lukemaan sana tiedoston. 

Jos jompikumpi virhe tapahtuu, tai pääsemme tiedoston loppuun, se ei palata 1 jolloin jos se ei palata 1, olemme vihdoin menossa rikkoa pois tästä kun silmukka. Näemme siis, että kun meillä on onnistuneesti lukea sanan entry-> sana, niin aiomme hash 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 hajautusfunktio Internetistä. Ainoa asia, sinun täytyy tunnustaa, on että tämä vie const char * sana, joten se vie merkkijonon tulo ja palaamassa unsigned int tuotokseksi. Niin, että kaikki hash-toiminto on, on se vie tulo, se antaa sinulle indeksinä tiiviste. Huomaa, että olemme Modaus by NUM_BUCKETS niin hash arvo palautetaan oikeastaan ​​on indeksinä tiiviste ja ei indeksoi yli rajat array. 

Joten koska hajautusfunktio, aiomme hash sana, joka luemme sanakirjasta ja sitten menemme käyttää, että on lisätä tuloa tiiviste. Nyt hashtable hash on nykyinen linkitetty lista on tiiviste, ja se on hyvin mahdollista, että on vain NULL. Haluamme lisätä meidän käännyttämiseksi Alussa tämän linkitetyn listan, ja niin aiomme olla meidän nykyisen merkinnän osoittavat johonkin tiiviste hetkellä pistettä ja sitten aiomme säilyttää hash pöytä hash Nykyisen tiedon. 

Joten nämä kaksi riviä onnistuneesti aseta merkintä alussa linkitetty lista tuohon hakemisto vuonna tiiviste. 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 lopulta palaa jotain ei 1 at missä vaiheessa muistaa, että meidän täytyy vapaa pääsy, joten tänne, me malloced maahantulon ja yritimme lukea jotain sanakirjasta. Ja emme onnistuttiin lukemaan jotain sanakirjasta, jossa tapauksessa meidän täytyy vapauttaa merkintä, että me koskaan itse laittaa tiiviste ja lopulta purkaa. 

Kun me puhkeaa, meidän täytyy nähdä, hyvin, me puhkeaa, koska siellä oli virhe luettaessa tiedostoa tai me puhkeaa koska pääsimme tiedoston loppuun? Jos oli virhe, niin haluamme palauttaa false, koska kuormitus ei menestyä, ja prosessi, haluamme purkaa kaikki sanat, jotka luemme ja lähellä sanastotiedostoa. Olettaen emme onnistu, sitten me vain vielä sulkea sanakirja tiedostoon, ja lopulta palata totta, sillä olemme ladattu onnistuneesti sanakirja. Ja se on siinä kuorman. 

Joten nyt tarkistaa, koska ladattu tiiviste, aikoo näyttää tältä. Joten tarkista, se palauttaa bool, joka tulee ilmoittaa, onko kulunut-in char * sana, onko läpäissyt-merkkijono on meidän sanakirja. Joten jos se on sanakirjassa, jos se on meidän tiiviste, palaamme totta, ja jos se ei ole, palaamme vääriä. Kun otetaan huomioon tämä kulunut tekstinkäsittelyohjelma, olemme menossa hash sana. 

Nyt tärkeintä tunnistaa on että kuorman, tiesimme, että kaikki sanat olivat menossa pieniä kirjaimia, mutta täällä, emme ole niin varma. Jos me katsomaan meidän hajautusfunktio, meidän hash-toiminto itse asiassa on lowercasing kunkin merkin sanan. Joten riippumatta arvo sana, meidän hash funktio on menossa palata sama indeksi jostain -arvo on, koska se olisi palautetaan kokonaan pienillä kirjaimilla versio sanasta. Selvä. 

Niin, että meidän indeksi. Se tiiviste sanaa. Nyt tämä silmukka on menossa liikaa linkitetty lista joka oli tuohon indeksi. Joten huomaat olemme alustetaan merkintä osoittamaan, että indeksiin. Aiomme jatkaa samalla merkintä ei ole yhtä NULL, ja muistaa, että päivittäminen osoitin meidän linkitetty lista entry vastaa entry-> seuraava, niin on nykyinen alkupisteestä Esityslistalla on linkitetty lista. Selvä. 

Joten jokaisen merkinnän linkitetty lista, aiomme käyttää strcasecmp. Se ei ole strcmp koska jälleen kerran, me haluavat tehdä asioita tapauksessa insensitively. Joten käytämme strcasecmp vertailla sana joka hyväksyttiin tämän toiminnon vastaan ​​sana, joka on tämä merkintä. Jos se palaa 0, se tarkoittaa, että oli ottelu, jolloin haluamme return true. Olemme löytäneet sana meidän tiiviste. 

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ä hash-taulukko ei sisällä tätä sanaa. Ja siinä se lähtöselvitykseen. Selvä. 

Joten katsotaanpa katsomaan koko. Nyt koko tulee olemaan melko yksinkertainen koska muistan kuorman, jokaista sanaa löysimme me kasvatetaan maailmanlaajuisen muuttuja hashtable_size. Joten koko toiminto on vain aio palata, että maailmanlaajuinen muuttuja, ja se on siinä. 

Nyt vihdoin, meidän täytyy purkaa sanakirjassa kerran kaiken tehtyä. Niin miten me sen teemme? Juuri täällä, me silmukoiden yli kaiken ämpärillistä meidän tiiviste. Joten on NUM_BUCKETS kauhat. Ja kunkin linkitetyn listan meidän hash pöytä, aiomme lenkki kokonaisuudessaan linkitetyn listan vapauttaa jokaisen elementin. Nyt meidän on oltava varovaisia, joten tässä me on väliaikainen muuttuja, joka on 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 sillä kun me 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 tiiviste, ja kun olemme tehneet kanssa, että olemme täysin purettu tiiviste, ja olemme valmiit. Joten se on mahdotonta kurmittamattomuuksiin koskaan palauttaa false, ja kun olemme tehneet, me vain palata totta.