ROB Bowden: Hi. Jaz sem Rob in hašiš dajmo Ta rešitev ven. Torej, tukaj bomo izvajati splošno hash tabelo. Vidimo, da struct node našega hash miza bo izgledala takole. Tako se dogaja, da imajo char beseda array dolžine velikosti plus 1. Ne pozabite na 1, saj je največja beseda v slovarju, je 45. znakov, nato pa bomo Potrebujemo en dodaten znak za backslash 0. 

In potem naša razpršena tabela v vsakem bucket se dogaja, da shranite povezani seznam vozlišč. Ne počnemo ravno sondiranje tukaj. In tako, da se poveže na naslednji element v vedro, moramo struct vozlišče * naslednji. Torej, to je tisto vozlišče izgleda. Zdaj, tukaj je deklaracija naše razpršene tabele. To se dogaja, da imajo 16.384 vedra, vendar to število ni važno. In končno, gremo, da imajo Globalna spremenljivka hashtable_size, ki se dogaja, da začnete kot 0, in to je dogaja, da bi spremljali, koliko besed so bile v našem slovarju. Vse je v redu. 

Tako da je lahko pogled na obremenitve. Tako opazili, da je obremenitev, se vrne bool. Vam vrne true, če je bilo uspešno naložen in false sicer. In to traja char * zvezdo Slovar, ki je slovar da želimo odpreti. Tako da je prva stvar, ki bomo storili. Bomo fopen slovar za branje, in da bomo imeli se prepričajte, da je uspelo tako, če se je vrnila NULL, potem nismo Uspešno odprite slovar in moramo vrne false. 

Vendar ob predpostavki, da je to storila uspešno open, nato pa smo želeli prebrati Slovar. Tako da zanka, dokler ne bomo našli nekaj Razlog za prekinitev iz tega zanke, ki bomo videli. Tako da zanka, in zdaj gremo da malloc enotno vozlišče. In seveda, moramo k napakam pregled spet tako da če mallocing ni uspelo in želimo, da se raztovarjanje kakršne koli vozlišče, ki smo se je zgodilo z malloc prej, zaprite slovar in vrne false. 

Ampak ignoriranje, da ob predpostavki, da bomo uspelo, nato pa smo želeli uporabiti fscanf se glasi eno samo besedo iz našega slovar v naše vozlišče. Torej, ne pozabite, da vstop-> beseda je char beseda buffer dolžine plus velikost tisti, ki bomo shranite besedo prijavite Torej fscanf se bo vrnil 1, dokler kot je bilo uspešno prebrati Beseda iz spisa. 

Če katera napaka se zgodi, ali smo dosegli Konec datoteke, da ne bo vrne 1 v tem primeru, če ne vrne 1, smo na koncu bo prekinil od tega, medtem ko zanke. Tako vidimo, da ko bomo imeli uspešno prebrati besedo v vstopno-> beseda, potem pa bomo hash ta beseda uporabo našega hash funkcijo. Oglejmo si na hash funkcijo. 

Tako da ne boste res potrebujejo razumeti. In dejansko smo pravkar potegnil to hash funkcijo iz interneta. Edina stvar, morate priznati, je da to traja char * besedo, tako da je ob niz kot vložek in vračanje nepodpisan int kot proizvodnja. Tako, da je vse hash funkcija je, ali je traja v vhod, vam omogoča Indeks v hash tabelo. Opazimo, da smo modding z NUM_BUCKETS tako vrnjena vrednost hash dejansko je indeks v hash tabelo in ne indeks tistega mejá matrike. 

Torej, glede na to, hash funkcijo, gremo za razpršitev besedo, ki beremo iz slovarja, nato pa se bomo za uporabo, ki ima za vstavljanje Začetek razpršene tabele. Zdaj, Hashtable hash je trenutna povezani seznam v razpršene tabele, ter to je zelo možno, da je le NULL. Želimo, da vstavite svoj vstop na začetku tega povezani seznam, in tako bomo morali naše sedanje vnos opozarjajo na kakšen razpršene tabele trenutno opozarja na in potem bomo za shranjevanje V razpršene tabele na hašiš trenutni vpis. 

Torej ti dve vrstici uspešno vstavite Vpis na začetku povezani seznam v tem indeksu v razpršene tabele. Ko smo končali s tem, vemo, da smo našli še eno besedo slovar in smo spet prirastek. Tako smo ostali storiti, dokler fscanf končno vrne nekaj, non 1 na kateri točki se spomnite, da moramo prost vstop, tako da tukaj smo malloced Vnos in smo poskušali prebrati nekaj iz slovarja. In nismo uspešno prebrati Nekaj ​​od slovarju v katerem primeru moramo osvoboditi vnos, ki smo nikoli dejansko dana v razpršene tabele in končno prekinil. 

Ko smo izbruhnejo, moramo videti, dobro, smo izbruhnejo, ker tam je bila napaka pri branju iz datoteke, ali smo izbruhnila, ker smo dosegli Konec datoteke? Če je prišlo do napake, nato pa smo želeli vrne false, ker obremenitev ni uspeti, in v procesu, želimo razložiti vse besede, ki jih beremo v in zaprite datoteko slovarja. Ob predpostavki, da nam ni uspelo, nato pa smo pravkar še vedno morali zapreti slovar datoteko, in na koncu vrne true, saj smo uspešno naložen Slovar. In to je to za tovor. 

Torej, zdaj preveriti, saj naložen razpršena tabela, bo izgledala takole. Zato preverite, da vrne bool, ki se dogaja, da navedejo, ali opravili-in Char * besedo, ali opravili-in niz je v našem slovarju. Torej, če je v slovarju, če je v naši razpršene tabele, se bomo vrnili res, in če ni, se bomo vrnili napačen. Glede na to minilo-in beseda, smo gre za razpršitev besedo. 

Zdaj, pomembna stvar je, da priznajo da v obremenitvi, smo vedeli, da so vsi besede so bile bo malimi črkami, ampak tukaj, nismo tako prepričani. Če pogledamo našo hash funkcijo, naša hash funkcija dejansko je lowercasing vsak znak besede. Torej, ne glede na kapitalizacijo beseda, naš hash funkcija bo vrne isti indeks za karkoli kapitalizacija je, kot bi morala vrnjeni v celoti male črke različica besede. Vse je v redu. 

Tako, da je naš indeks. To je razpršena tabela za te besede. Zdaj, to zanko se dogaja da preko povezani seznam , ki je bil v tistem indeksu. Torej opazili smo inicializacija vnos poudariti, da tega indeksa. Bomo še naprej, medtem ko vnos ne ni enaka NULL, in ne pozabite, da posodabljanje kazalec v našem povezanem seznamu Vnos je enako vstopno-> naslednji, tako da imajo Naša trenutna vstopna točka za Naslednji element v povezanem seznamu. Vse je v redu. 

Torej, za vsak vpis v povezanem seznamu bomo uporabili strcasecmp. To ni strcmp, ker še enkrat, bomo želeli narediti stvari primera insensitively. Tako smo uporabili strcasecmp primerjati besedo , ki je bil sprejet na tej funkciji ob besedi, ki je v tej točki. Če se vrne 0, kar pomeni, da ni bilo ujemanje, v tem primeru želimo vrne true. Uspešno smo ugotovili beseda v našem razpršene tabele. 

Če ne bi bilo tekmo, nato pa smo spet bo zanke in pogled na next entry. In bomo še naprej loopinga medtem ko so navedbe v tej povezanem seznamu. Kaj se zgodi, če razbijemo v to zanko? To pomeni, da nismo našli vnos, ki ujema to besedo, v tem primeru vrnemo false, ki označuje, da je naš razpršene tabele ne vsebujejo to besedo. In da je za pregled. Vse je v redu. 

Tako da je lahko pogled na velikost. Zdaj, velikost se bo zelo preprosta od zapomni pri obremenitvi, za vsako besedo smo ugotovili, smo se poveča globalno spremenljivka hashtable_size. Torej funkcija znaša le vrača, da svetovna spremenljivka, in to je to. 

Zdaj končno moramo raztovoriti slovar, ko je vse končano. Torej, kako bomo to storili? Tukaj sem, da smo zanka nad vsem vedra naše razpršene tabele. Torej obstajajo NUM_BUCKETS vedra. In za vsakega povezanega seznama v naši hash miza, bomo zanko celota povezanega seznama sprostitev vsak element. Zdaj pa moramo biti previdni, tako da tukaj smo imajo začasno spremenljivko, ki je shranjevanje kazalec na naslednji element v povezanem seznamu. In potem bomo brezplačno trenutni element. 

Moramo biti prepričani, da bomo to naredili, ker smo Ne moreš sprostiti trenutni element in nato poskusite za dostop do naslednjega kazalec saj ko bomo osvobodili spomin postane neveljaven. Zato moramo ohraniti okoli kazalec Naslednji element, potem bomo lahko osvobodi Sedanji element, in potem bomo lahko posodobite Naš trenutni element, da kaže na Naslednji element. 

Bomo zanko, medtem ko obstajajo elementi V tem povezani seznam. To bomo storili za vse povezane sezname razpršene tabele, in ko sva končala S tem smo v celoti raztovoriti hash tabelo, in sva končala. Zato je nemogoče, da bi kdaj raztovarja vrne false, in ko bomo končali, smo pravkar vrnil res.