>> ROB BOWDEN: Szia.
Én Rob, és hagyja, hogy a hash e megoldás.
Tehát itt fogunk végrehajtani általános hash tábla.
Látjuk, hogy a struktúra csomópontja a hash táblázat fog kinézni, mint ez.
Ezért van, hogy a char szót tömb mérete hossza plusz 1.
Ne felejtsd el a 1, mivel a maximum szó a szótárban 45
karaktereket, majd megyünk szükség van egy extra karakter a
backslash 0-ra.
>> És akkor a hash tábla minden vödör fog tárolni a
láncolt lista csomópontok.
Nem csináljuk lineáris szondázás itt.
Így annak érdekében, hogy link a következő elem a vödör, szükségünk van egy
struct node * mellett.
Szóval, ez az, amit a csomópont néz ki.
Nos, itt van a nyilatkozat a mi hash tábla.
Úgy megy, hogy 16.384 vödör, de ez a szám nem igazán számít.
És végül, mi lesz, hogy a globális változó hashtable_size, amely
fog elindul, mint 0, és ez majd nyomon követni, hogy hány szót
volt a szótár.
Rendben van.
>> Szóval vessünk egy pillantást a terhelés.
Tehát észre, hogy terhelés, visszatér a bool.
Visszatér igaz, ha sikeresen betöltött és hamis egyébként.
És ez tart a const char * csillag szótár, amely a szótárban
hogy meg akarjuk nyitni.
Tehát ez az első dolog, fogunk csinálni.
Fogunk fopen a szótárban olvasás, és mi lesz, hogy
, hogy megbizonyosodjon arról, hogy ez sikerült, így ha visszatért NULL, akkor nem
sikeresen nyitott a szótárban , és vissza kell térnünk hamis.
>> De feltételezve, hogy nem sikerült nyitva van, akkor szeretnénk olvasni a
szótárban.
Maradjatok hurok amíg nem találunk valami ok, hogy kitörjön a jelen
hurok, amely majd meglátjuk.
Maradjatok hurok, és most megyünk malloc egy csomópont.
És persze, meg kell, hogy hiba ellenőrzése újra így ha mallocing nem sikerült
és azt akarjuk, hogy kirak olyan csomópont, hogy mi történt malloc előtt, zárja be a
szótárt, és vissza hamis.
>> De figyelmen kívül hagyva, hogy feltételezve, hogy sikerült, akkor szeretnénk használni fscanf
olvasni egy szót a szótárt a mi csomópontot.
Úgy emlékszem, hogy a belépő> szó a char szó buffer méret hossza plusz
az egyik, hogy fogunk tárolja a szó be
Tehát fscanf fog visszatérni 1. amíg mint volt sikeresen olvasni
szó a fájlból.
>> Ha bármelyik hiba történik, vagy elérjük a végén a fájl, akkor nem
1 visszaút amely esetben, ha ez nem vissza 1, mi végre fog törni
ebből a while ciklus.
Tehát azt látjuk, hogy ha már sikeresen olvasni egy szót
entry-> szó, akkor megyünk hash ez a szó a mi hash függvényt.
Vessünk egy pillantást a hash függvényt.
>> Szóval nem igazán kell megérteni ezt.
És valóban, csak húzta ezt hash függvény az interneten.
Az egyetlen dolog, amit meg kell, hogy ismerje el, hogy ez eltart egy const char * szó,
így tart a sztringet bemeneti és vissza az unsigned int a kibocsátás.
Szóval ez az egész egy hash funkció, ez vesz egy bemeneti, ez ad ön egy
index a hash tábla.
Figyeljük meg, hogy mi modding által NUM_BUCKETS így a hash visszaadott érték
valójában egy index a hash tábla és nem indexeli túl
határait a tömb.
>> Tehát mivel hash függvényt, megyünk a hash a szó, hogy olvasunk
a szótárt, és aztán megyünk használni, amely beszúrni a
belépés a hash tábla.
Most, hash tábla hash a jelenlegi láncolt lista a hash tábla, és a
ez nagyon valószínű, hogy csak NULL.
Azt szeretné szúrni a belépést a elején ez a láncolt lista, és így
mi lesz, hogy a jelenlegi bejegyzés pont, amit a hash tábla jelenleg
pontokat, majd megyünk tárolni a hash táblában a hash
Az aktuális bejegyzés.
>> Tehát ez a két vonal sikeresen be belépési elején a
láncolt lista az adott index a hash táblában.
Miután végeztünk, hogy mi tudjuk, hogy talált egy másik szót a
szótár és növedék újra.
Így csinálom, hogy amíg fscanf végül visszatér valami nem 1-es
amely pont ne feledje, hogy meg kell a belépés ingyenes, így itt, mi malloced egy
belépés és megpróbáltuk olvasni valamit a szótárban.
És nem sikerült elolvasni valamit a szótárban, amelyben
esetben fel kell szabadítanunk a bejegyzést, hogy mi soha nem tesz a hash tábla
és végül a szünet.
>> Amint kitörni, meg kell látni, nos, tudtunk kitörni, mert
Hiba olvasni a fájlt, vagy tudtunk kitörni, mert elértük
a végén a fájl?
Ha volt egy hiba, akkor szeretnénk return false mert terhelés nem
sikerül, és a folyamat, azt akarjuk, hogy kirak minden szót, amit olvas
és zárja be a szótárban fájlt.
Feltéve, hogy nem sikerül, akkor már csak továbbra is szükség van, hogy lezárja a szótárban
fájlt, és végül vissza igaz, mert már sikeresen betöltötte a
szótárban.
És ez a terhelés.
>> Tehát most ellenőrizni, mivel a terhelt hash tábla, fog kinézni.
Így ellenőrizni, visszatér a bool, amely fog annak jelzésére, hogy a
telt-in char * szó, hogy a telt-karakterlánc a mi szótárban.
Tehát, ha a szótárban, ha az a mi hash tábla, akkor vissza fog térni
igaz, és ha nem, visszatérünk hamis.
Mivel ez a telt, a szó, mi fogja hash szó.
>> Nos, egy fontos dolog, hogy ismerje el, hogy a terhelés, tudtuk, hogy az összes
a szavak lesznek kisbetűs, de itt, nem vagyunk olyan biztos.
Ha veszünk egy pillantást a hash függvény a hash függvény valójában
A lowercasing minden karakter a szó.
Tehát függetlenül attól, hogy a kapitalizációja szó, a hash funkció fog
vissza ugyanazt index bármilyen kapitalizáció olyan volna
visszatért egy teljesen kisbetűs változata a szó.
Rendben van.
>> Szóval ez az index.
Ez a hash tábla ezt a szót.
Nos, ez a for ciklus megy hogy több mint a láncolt lista
hogy abban az index.
Így észre vagyunk inicializálás bejegyzés hogy pont, hogy az index.
Megyünk tovább, amíg a bejegyzés nem nem egyenlő NULL, és ne feledje, hogy
frissítése a mutatót a láncolt lista belépés egyenlő entry-> kov, így már
a jelenlegi belépési pont a következő elem a láncolt lista.
Rendben van.
>> Tehát minden bejegyzést a láncolt lista, fogunk használni strcasecmp.
Nem strcmp mert még egyszer, mi akar csinálni a dolgokat esetben érzéketlenül.
Így használjuk strcasecmp összehasonlítani a szó amit át ezt a funkciót
ellen, a szó, hogy ebben a bejegyzést.
Ha visszatér 0, azt jelenti, hogy nem volt a meccs, ebben az esetben szeretnénk
vissza igaz.
Sikeresen megtaláltuk a szó a mi hash tábla.
>> Ha nem egyezik, akkor vagyunk fog loop újra, és nézd meg a
következő bejegyzés.
És mi is loop míg vannak bejegyzések ebben a láncolt lista.
Mi történik, ha szünet ki ez a for ciklus?
Ez azt jelenti, hogy nem találtunk olyan bejegyzést, amely párosított ezt a szót, amely esetben
visszatérünk a hamis, jelezve, hogy a hash tábla nem tartalmazza ezt a szót.
És ez a csekk.
Rendben van.
>> Szóval vessünk egy pillantást méretben.
Most, méret lesz nagyon egyszerű mivel emlékszem terhelés minden egyes szó
találtunk is növekszik a globális változó hashtable_size.
Tehát a méret funkció csak majd vissza, hogy a globális
változó, és ennyi.
>> Most végre, meg kell, hogy kirak az szótár Amint minden kész.
Szóval, hogyan fogjuk csinálni?
Itt, mi a ciklusok egész vödör a hash tábla.
Tehát vannak NUM_BUCKETS vödör.
És minden egyes láncolt lista a mi hash asztal, megyünk hurkot a
teljes egészében a láncolt lista felszabadítása minden elem.
Nos, meg kell, hogy legyen óvatos, ezért itt van egy átmeneti változó, ami
tárolja a mutatót, hogy a következő elem a láncolt lista.
És akkor mi lesz ingyenes Az aktuális elem.
>> Meg kell bizonyosodni arról, hogy ezt mivel Nem lehet csak kiszabadítani az aktuális elem
, majd próbálja meg elérni a következő mutató hiszen ha már kiszabadította azt a
memória érvénytelenné válik.
Tehát meg kell tartani körül egy mutatót A következő elem, akkor mi is szabad a
aktuális elem, és akkor frissíteni a jelenlegi elem, hogy pont
A következő elem.
>> Majd loop, míg vannak olyan elemei ebben a láncolt lista.
Majd, hogy minden csatolt listák A hash tábla, és ha kész is vagyunk
azzal, hogy most már teljesen lemerülni A hash tábla, és kész is vagyunk.
Tehát lehetetlen eltávolítja valaha return false, és amikor kész, akkor
csak vissza igaz.