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.