>> ROB BOWDEN: Hi.
Sunt Rob, și hash Să această soluție afară.
Deci, aici am de gând să pună în aplicare un tabel hash general.
Vedem că nodul struct de hash noastre masă este de gând să arate ca aceasta.
Deci, o să aibă un cuvânt char matrice de lungime dimensiune plus 1.
Nu uita de 1 la maxim cuvânt în dicționar este de 45
caractere, iar apoi vom au nevoie de un caracter suplimentar pentru
backslash 0.
>> Și apoi masa noastră hash în fiecare găleată se va stoca un
Lista legate de noduri.
Noi nu facem liniar sondare aici.
Și astfel, în scopul de a lega la alta Element în găleată, avem nevoie de un
struct nod * viitor.
Deci, asta e ceea ce un nod arata ca.
Acum, aici este declarația de masa noastră hash.
Se va avea 16.384 de găleți, dar că numărul nu contează cu adevărat.
Și, în sfârșit, vom avea hashtable_size global variabilă, care
este de gând să încep ca 0, și este merge pentru a urmări cât de multe cuvinte
au fost, în dicționarul nostru.
Bine.
>> Deci, haideți să aruncăm o privire la sarcină.
Astfel observa că sarcina, returnează un bool.
Te vei întoarce true dacă a fost cu succes încărcat și false în caz contrar.
Și este nevoie de un const char * stele dicționar, care este dicționarul
pe care ne-o dorim pentru a deschide.
Deci, asta e primul lucru am de gând să faci.
Vom fopen dicționarul de lectură, și vom avea
pentru a vă asigura că a reușit, deci, dacă ea sa întors NULL, atunci nu am
deschide cu succes în dicționar și avem nevoie pentru a reveni false.
>> Dar presupunând că a făcut-o cu succes deschis, apoi ne-o dorim pentru a citi
dicționar.
Deci, ține looping până când vom găsi unele motiv pentru a iesi din aceasta
buclă pe care vom vedea.
Deci, ține looping, iar acum vom merge la malloc un singur nod.
Și, desigur, avem nevoie pentru a eroare de verificare din nou, așa că, dacă mallocing nu a reușit
și vrem să descarce orice nod pe care le sa întâmplat cu malloc înainte, închideți
dicționar și a reveni false.
>> Dar ignorând că, ne-am presupunând a reușit, atunci vrem sa folosim fscanf
pentru a citi un singur cuvânt de la noastră dictionar în nodul nostru.
Deci, amintiți-vă că cuvântul de intrare-> este char tampon cuvânt de lungime dimensiune plus
una care vom stoca cuvântul inch
Astfel fscanf este de gând să se întoarcă 1, atâta timp așa cum a fost capabil să citească un succes
cuvânt de la dosar.
>> În cazul în care fie o eroare se întâmplă sau vom ajunge la sfârșitul fișierului, nu va
reveni 1, caz în care în caz contrar întoarcă 1, vom în cele din urmă va rupe
din această buclă în timp.
Deci, vom vedea că, odată ce avem succes citit un cuvânt în
intrare-> cuvânt, atunci vom hash acest cuvânt utilizând funcția noastră hash.
Să aruncăm o privire la funcția de distribuire.
>> Deci, nu aveți cu adevărat nevoie să înțeleagă acest lucru.
Și, de fapt, ne-am scos acest Funcția hash de pe internet.
Singurul lucru pe care trebuie să recunoască este că acest lucru are un const char * cuvânt,
așa că, luând un șir ca intrare și revenind un int nesemnate ca ieșire.
Deci, asta e tot o funcție hash este, este ia într-o intrare, vă oferă o
index în tabelul hash.
Observați că suntem modding de NUM_BUCKETS astfel încât valoarea hash a revenit
de fapt este un index în tabelul hash și nu indicele de dincolo de
limitele de matrice.
>> Deci, având în vedere că funcția hash, vom hash cuvântul pe care am citit
din dicționar și apoi vom merge să utilizeze care are pentru a insera
intrare în tabelul hash.
Acum, hash Hashtable este curentul Lista legată în tabelul hash, și
este foarte posibil că este doar NULL.
Vrem să inserați intrarea nostru de la începând din această listă legată, și așa
vom avea intrarea noastră actuală punctul de ce tabelul hash în prezent
puncte pentru a și apoi vom stoca în tabelul hash la hash
intrarea curentă.
>> Deci, aceste două linii se introduce cu succes intrarea de la începutul
Lista legat la acel index în tabelul hash.
După ce am terminat cu asta, știm că am găsit un alt cuvânt în
dicționar și am incrementa din nou.
Așa că am continuăm să facem asta până fscanf se întoarce în cele din urmă ceva non 1 la
care punct amintiți-vă că trebuie să intrare liberă, așa că aici, noi malloced o
intrare și am încercat să citesc ceva din dicționar.
Și nu ne-am citit cu succes ceva din dicționar, în care
caz, avem nevoie pentru a elibera intrarea pe care le nu pune de fapt în tabelul hash
și, în final rupe.
>> Odată ce am izbucni, avem nevoie pentru a vedea, de asemenea, ne-am izbucni deoarece acolo
a fost citit o eroare de fișier, sau ne-am izbucni că am ajuns
sfârșitul fișierului?
Dacă a existat o eroare, atunci vrem să return false pentru că sarcina nu a făcut
reuși, și în acest proces, vrem să descărca toate cuvintele pe care le-am citit
în și închideți fișierul dicționar.
Presupunând că am reușit, atunci ne-am încă mai trebuie să închidă în dicționar
dosar, și în cele din urmă a reveni adevărat, deoarece ne-am încărcat cu succes
dicționar.
Și asta este pentru sarcină.
>> Deci, acum, verifica, având în vedere un tabel hash încărcat, este de gând să arate ca aceasta.
Deci, a verifica, se returnează un bool, care se va indica dacă
a trecut-in char * cuvânt, indiferent dacă șir a trecut-in este în dicționar nostru.
Deci, în cazul în care acesta este în dicționar, dacă este în masa noastră hash, ne vom întoarce
adevărat, și dacă nu e, ne vom întoarce false.
Având în vedere acest cuvânt a trecut-in, suntem merge la hash cuvântul.
>> Acum, un lucru important să recunoaștem este că în sarcină, am știut că toate
cuvintele au fost de gând să fie litere mici, dar aici, nu suntem așa de sigur.
Dacă ne uităm la funcția noastră hash, Funcția noastră hash de fapt
este lowercasing fiecare personaj al cuvântului.
Deci, indiferent de capitalizarea de cuvânt, funcția noastră hash se va
returneze același indice pentru orice capitalizare este ca aceasta ar avea
a revenit pentru o complet cu litere mici versiune a cuvântului.
Bine.
>> Deci, asta e indexul nostru.
Este tabelul hash pentru acest cuvânt.
Acum, acest lucru pentru bucla se întâmplă la peste lista de legătura
care a fost la acel index.
Deci observa suntem inițializarea intrare pentru a indica faptul că index.
Vom continua în timp ce intrarea nu Nu NULL egal, și amintiți-vă că
actualizarea indicatorul în lista noastră legată de intrare este egal cu intrare-> următor, așa că au
punctul nostru de intrare curent la următorul element în listă legat.
Bine.
>> Deci, pentru fiecare intrare în lista de legat, vom folosi strcasecmp.
Nu strcmp pentru că, încă o dată, ne-am vrei sa faci lucruri caz fără sensibilitate.
Deci, vom folosi strcasecmp pentru a compara cuvântul care a fost trecut la această funcție
împotriva cuvântul care este în această intrare.
În cazul în care se întoarce 0, înseamnă că nu a fost un meci, în cazul în care dorim să
return true.
Am găsit cu succes cuvânt în masa noastră hash.
>> Dacă nu a fost un meci, atunci suntem merge la bucla din nou si uita-te la
intrare următor.
Și vom continua looping în timp ce acolo sunt intrări în această listă legat.
Ce se întâmplă dacă am rupe din aceasta pentru buclă?
Asta înseamnă că nu am găsit o intrare care potrivit acest cuvânt, în care caz
ne întoarcem false pentru a indica faptul că noastră tabel hash nu conțin acest cuvânt.
Și asta este pentru verificare.
Bine.
>> Deci, haideți să aruncăm o privire la dimensiune.
Acum, dimensiunea va fi destul de simplu amintiți-vă, deoarece în sarcină, pentru fiecare cuvânt
am găsit am incrementat un global hashtable_size variabilă.
Deci, funcția de dimensiunea este doar O să se întoarcă că la nivel mondial
variabilă, și asta e tot.
>> Acum, în cele din urmă, avem nevoie pentru a descărca dicționar dată totul sa terminat.
Deci, cum vom face asta?
Chiar aici, suntem looping peste tot găleți de masa noastră hash.
Deci, există NUM_BUCKETS galeti.
Și pentru fiecare listă legată în hash nostru masă, vom bucla peste
întregime din lista de legătura eliberând fiecare element.
Acum, trebuie să fim atenți, așa că aici am au o variabilă temporar care este
stocarea indicatorul la alta element din lista de legătura.
Și apoi vom liber elementul curent.
>> Avem nevoie pentru a fi sigur că vom face acest lucru, deoarece ne-am nu se poate elibera doar elementul curent
și apoi încercați să accesați indicatorul următor deoarece odată ce l-am eliberat
memorie devine invalid.
Deci, avem nevoie pentru a menține în jurul valorii de un pointer la elementul următor, atunci ne putem elibera
element de curent, și apoi putem actualiza elementul nostru curent de a indica
elementul următor.
>> Vom buclă în timp ce există elemente în această listă legat.
Vom face acest lucru pentru toate listele legate în tabelul hash, și o dată am terminat
cu care, am descărcată complet tabelul hash, și am terminat.
Deci, este imposibil pentru descarcă de tot return false, și când am terminat, ne-am
doar return true.