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