>> 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.