[Redare a muzicii] 

ROB BOWDEN: Hi. Sunt Rob. Și să această soluție afară. Deci, aici am de gând să pună în aplicare o masă generală. Vedem că nodul struct de nostru masă este de gând să arate ca aceasta. Deci, o să aibă un cuvânt char matrice de dimensiune lungime + 1. Nu uita de + 1, de la maxim cuvânt în dicționar este de 45 caractere. Și apoi vom avea nevoie de un plus caracter de zero backslash. 

Și apoi hashtable noastră î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. OK. Deci, asta e ceea ce un nod arata ca. 

Acum, aici este declarația de hashtable noastre. Se va avea 16,834 găleți. Dar acest număr nu contează cu adevărat. Și, în sfârșit, vom avea Dimensiunea globală hashtable variabilă, care va incepe la zero. Și se va urmări modul în care multe cuvinte sunt în dicționarul nostru. 

Deci, haideți să aruncăm o privire la sarcină. Observați că sarcina, returnează un bool. Te vei întoarce true dacă a fost cu succes încărcate, și false în caz contrar. Și este nevoie de un const char * 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ționar pentru lectură. Și vom avea de a face sigur că a reușit. Deci, în cazul în care 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 de a ieși din această buclă, pe care vom vedea. Deci, ține looping. 

Și acum vom malloc un singur nod. Și, desigur, avem nevoie la aer a verifica din nou. Deci, dacă mallocing nu a avut succes, atunci ne-o dorim pentru a descărca 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ă intrarea> cuvânt este char tampon cuvânt de dimensiuni Lungime de + 1 că vom stoca cuvântul inch 

Astfel fscanf este de gând să se întoarcă 1, atâta timp așa cum a fost în măsură să succes citit un cuvânt de la dosar. În cazul în care fie o eroare se întâmplă, sau noi ajunge la sfârșitul fișierului, se nu va reveni 1. În cazul în care aceasta nu se întoarce 1, suntem în cele din urmă o să iasă din această buclă în timp. Deci, vom vedea că, odată ce avem succes citit un cuvânt în intrare> cuvânt, apoi mergem la care 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, doar ne-am scos acest hash funcționeze de pe internet. Singurul lucru pe care trebuie să recunoască este că acest lucru are un const char * cuvânt. Deci, se ia 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 și vă oferă o index în Hashtable. 

Observați că suntem moding de NUM_BUCKETS, astfel ca valoarea returnată de fapt este un index în Hashtable și nu indicele de dincolo de limitele de matrice. Deci, având în vedere că funcția, vom hash cuvântul pe care am citit dicționar. Și apoi vom folosi care hash pentru a insera intrarea în Hashtable. 

Hash acum hashtable este curentul Lista legată în tabel. Și e foarte posibil că e doar NULL. Vrem să inserați intrarea nostru de la începând din această listă legat. Și astfel vom avea curent noastră punct de intrare în ceea ce Hashtable subliniază în prezent la. Și apoi vom stoca, în Hashtable la hash, intrarea curentă. Deci, aceste două linii se introduce cu succes intrarea de la începutul Lista legat la acel index în Hashtable. 

După ce am terminat cu asta, știm că am găsit un alt cuvânt în dicționar, și ne-am incrementa din nou. Așa că am continuăm să facem asta până fscanf a revenit în cele din urmă ceva non-1 la care punct amintiți-vă că avem nevoie pentru intrare gratuită. Deci, aici am malloced o intrare. Și am încercat să citesc ceva din dicționar. Și nu ne-am citit cu succes ceva din dicționar, în caz în care avem nevoie pentru a elibera intrarea că nu ne-am pus de fapt în hashtable, și în cele din urmă rupe. 

Odată ce am izbucni avem nevoie pentru a vedea, de asemenea, ne-am izbucni deoarece acolo a fost citit o eroare de la dosar? Sau ne-am izbucni pentru ca noi a ajuns la sfârșitul fișierului? Dacă a existat o eroare, atunci vrem să se întoarcă false. Deoarece sarcina nu a reușit. Și în procesul de ne-o dorim pentru a 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 din moment ce încărcate cu succes în dicționar. Și asta este pentru sarcină. Deci, acum, verifica, având în vedere un Hashtable încărcat, este de gând să arate ca aceasta. Deci, a verifica, se returnează un bool, care este va indica dacă a trecut în char * cuvânt, dacă a trecut în șir este în dicționar nostru. Deci, în cazul în care acesta este în dicționar, în cazul în care acesta este în Hashtable nostru, ne vom întoarce adevărat. Și dacă nu e, ne vom întoarce false. 

Având în vedere acest lucru a trecut în cuvânt, suntem merge la hash cuvântul. Acum, un lucru important să recunoaștem este că în sarcină am știut că toate Cuvintele noi 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 carcasa inferioară fiecare personaj al cuvântului. Deci, indiferent de capitalizarea de cuvânt, funcția noastră hash este revenirea același indice pentru orice capitalizare este, așa cum ar trebui a revenit pentru o complet cu litere mici versiune a cuvântului. În regulă. Acesta este indexul nostru este în Hashtable pentru acest cuvânt. 

Acum, acest lucru pentru bucla se va itera 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 intrare! = NULL. Și amintiți-vă că actualizarea indicatorul în lista de intrare noastră legată = intrare> următor. Deci, au punctul nostru de intrare curent la următorul element din lista de legat. 

Deci, pentru fiecare intrare în lista de legat, vom folosi strcasecmp. Nu e strcomp. Pentru că, încă o dată, vrem să face lucruri caz fără sensibilitate. Deci, vom folosi strcasecmp pentru a compara cuvânt care a fost trecut prin acest Funcția împotriva cuvântului care este în această intrare. În cazul în care se întoarce la zero, înseamnă că nu a fost un meci, în cazul în care dorim să return true. Am găsit cu succes cuvânt în Hashtable nostru. 

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ă hashtable nu conțin acest cuvânt. Si asta e un cec. 

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 Dimensiunea Hashtable variabilă. Deci, funcția de dimensiunea este doar de gând pentru a reveni variabilă globală. Ș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 toate găleți de masa noastră. Deci, există NUM_BUCKETS galeti. Și pentru fiecare listă legată în nostru hashtable, vom buclă peste totalitatea lista legate, eliberând fiecare element. 

Acum, avem nevoie să fim atenți. Deci, aici avem 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 cursorul următoare, deoarece odată ce l-am eliberat, memoria 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 legate liste în Hashtable. Și odată ce am terminat cu asta, ne-am descărcată complet Hashtable, și am terminat. Deci, este imposibil pentru descărcare pentru a reveni vreodată false. Și când am terminat, ne-am doar return true. 

Să-i dăm această soluție o încercare. Deci, haideți să aruncăm o privire la ceea ce noi struct nod va arata. Aici vom vedea vom avea o bool cuvânt și un nod struct * copii suport alfabet. Deci, primul lucru pe care ar putea fi întrebam, de ce este ALPHABET ed definit ca 27? Ei bine, amintiți-vă că vom avea nevoie de să fie de manipulare apostrof. Astfel că va fi un fel de caz special de-a lungul acestui program. 

Acum imi amintesc cum o trie de fapt, funcționează. Să presupunem că suntem indexarea cuvântul "pisici". Apoi, de la rădăcina de trie, ne vom uita la copii matrice, și ne vom uita la indice care corespunde literei C. Deci, care vor fi indexate 2. Deci, având în vedere că, ceea ce va ne da un nou nod. Și apoi vom lucra de la acel nod. 

Deci, având în vedere că nod, suntem încă o dată gând să se uite la matrice copii. Și ne vom uita la index zero, să corespundă A de pisică. Deci, atunci vom merge la acel nod, și având în vedere că nod vom să se uite la final este o corespunde la T. Și de a trece la acel nod, în cele din urmă, ne-am uitat complet prin cuvântul nostru "pisică". Și acum bool cuvânt ar trebui să indice dacă acest cuvânt dat este de fapt un cuvânt. 

Deci, de ce avem nevoie de acest caz special? Ei bine, ceea ce a cuvântului "catastrofă" este în dicționarul nostru, dar Cuvântul "pisica" nu este? Deci, și căutați pentru a vedea dacă cuvântul "pisică" este în dicționarul nostru, suntem de gând să se uite cu succes prin indicii C-A-T în nod regiune. Dar asta e doar pentru că catastrofă sa întâmplat pentru a crea noduri pe drum de la C-A-T, tot drumul de a sfârșitul cuvântului. Deci, bool cuvânt este folosit pentru a indica dacă această locație special indică de fapt un cuvânt. 

Bine. Deci, acum că știm ce trie este va arăta, să ne uităm la Funcția se încarce. Astfel de sarcină este de gând să se întoarcă un bool pentru dacă noi cu succes sau încărcate fără succes dicționar. Și acest lucru va fi în dicționar pe care vrem să se încarce. 

Deci, primul lucru pe care vrem să faceți este să deschideți up care dicționar pentru lectură. Și noi trebuie să ne asigurăm nu am eșua. Deci, în cazul în dicționarul nu a fost deschis cu succes, se va reveni nul, caz în care suntem O să se întoarcă false. Dar presupunând că aceasta cu succes a deschis, atunci se poate citi de fapt prin dicționar. 

Deci, primul lucru pe care am de gând să Vreau să faceți este să avem această rădăcină variabilă globală. Acum rădăcină va fi un nod *. Este partea de sus a trie nostru că suntem va fi iterarea prin intermediul. Deci, primul lucru pe care vom să vrea să faceți este să aloce memorie de radacina noastra. Observați că suntem folosind calloc funcție, care este în esență același ca funcția malloc, cu excepția e garantat pentru a reveni ceva care este complet adus la zero. Deci, dacă am folosit malloc, ne-ar trebui să du-te prin toate indicii în nostru nod, și asigurați-vă că toate acestea sunt nule. Astfel calloc va face asta pentru noi. 

Acum, la fel ca malloc, avem nevoie pentru a face vă că alocarea a fost de fapt succes. În cazul în care acest lucru sa întors null, atunci ne-am nevoie pentru a închide sau dicționar fișier și a reveni false. Deci, presupunând că alocarea a fost de succes, vom folosi un nod * cursorul pentru a itera prin trie nostru. Deci, rădăcinile noastre nu se va schimba, dar am de gând să folosească cursorul pentru a de fapt, du-te de la nod la nod. 

Deci, în această buclă pentru citim prin fișierul dicționar. Și folosim fgetc. Fgetc este de gând să apuca un singur personaj din dosar. Vom continua hapsân caractere în timp ce noi nu ajung la sfârșitul fișierului. 

Există două cazuri pe care trebuie să se ocupe. Primul, dacă caracterul Nu a fost o nouă linie. Deci, noi știm dacă a fost o noua linie, apoi suntem pe cale de a trece la un nou cuvânt. Dar presupunând că nu a fost o linie nouă, apoi aici ne-am dori să dau seama de index vom index în în matrice copii care ne-am uitat la mai înainte. 

Deci, cum am spus mai înainte, trebuie să ne caz special apostrof. Observați suntem folosind ternar operator de aici. Așa că am de gând să citesc acest lucru ca, în cazul în care caracterul am citit într-o a fost apostrof, atunci vom stabili index = "alfabet" -1, care va fie indexul 26. 

Altfel, în cazul în care acesta nu a fost un apostrof, acolo vom stabili indicele egal cu c - un. Deci, amintiți-vă înapoi de la anterior p-seturi, c - o este de gând să ne dea Poziția alfabetică a C. Deci, dacă C este litera A, acest lucru va ne da index zero. Pentru litera B, se va da ne indicele 1, și așa mai departe. 

Deci, acest lucru ne dă indicele în copii matrice pe care ne-o dorim. Acum, în cazul în care acest indice este în prezent nul în copiii, care înseamnă că un nod nu există în prezent de la această cale. Deci, avem nevoie de a aloca un nod pentru această cale. Asta e ceea ce vom face aici. 

Așa că am de gând să folosească din nou calloc funcție, astfel încât să nu trebuie să zero, toate indicii. Și din nou avem nevoie pentru a verifica că calloc nu a eșuat. Dacă calloc a eșua, atunci avem nevoie de pentru a descărca totul, închideți nostru dicționar, și să se întoarcă false. Deci, presupunând că nu reușesc, atunci acest lucru va crea un nou copil pentru noi. Și apoi vom merge la acel copil. Cursor nostru va repeta până la acel copil. 

Acum, în cazul în care acest lucru nu a fost nul pentru a începe cu, atunci cursorul se poate repeta doar până la care copilul fără de fapt, a trebui să aloce nimic. Acesta este cazul în care ne-am sa întâmplat în primul rând aloca cuvântul "pisică". Și asta înseamnă că, atunci când vom merge să aloce "Catastrofă," nu avem nevoie pentru a crea noduri pentru C-A-T din nou. Acestea există deja. 

Ce este acest altceva? Aceasta este condiția în care c este backslash n, unde c este o noua linie. Acest lucru înseamnă că avem succes finalizat un cuvânt. Acum, ce vrem să facem atunci când ne-am finalizat cu succes un cuvânt? Vom folosi acest domeniu cuvânt interiorul nod noastre struct. Vrem să stabilească care la true. Deci, care indică faptul că acest nod indică un succes cuvânt, un cuvânt real. 

Acum stabilit că, pentru a adevărat. Vrem să resetați cursorul nostru la punct la începutul trie din nou. Și, în sfârșit, incrementa dicționarul nostru dimensiune, deoarece am găsit un alt lucru. Deci, vom continua să faci asta, lectură în caracter cu caracter, construirea de noi noduri în trie noastră și pentru fiecare cuvânt în dicționar, până vom ajunge în cele din urmă C! = EOF, în care caz ne-am iesi din dosar. 

Acum, există două cazuri în conformitate cu pe care ne-am fi lovit EOF. Primul este dacă a existat o eroare citirea din fișierul. Deci, dacă a fost o eroare, ne-am au nevoie pentru a face tipic. Descărca totul, aproape fișierul, intoarce false. Presupunând că nu a fost o eroare, care înseamnă doar ne-am lovit de fapt la sfârșitul anului dosar, în care caz, am închide fișier și a reveni adevărat din moment ce dicționar încărcat cu succes în trie nostru. 

Deci, acum, haideți să verificați de verificare. Privind la funcția de verificare, vom vedea care verificare este de gând să se întoarcă un bool. Acesta returneaza true daca acest cuvânt care este fiind trecut este în trie nostru. Returnează false în caz contrar. Deci, cum te determina dacă acest cuvânt este în trie nostru? 

Vedem aici că, la fel ca înainte, vom folosi cursorul pentru a repeta prin trie nostru. Acum, aici vom repeta peste întreaga noastră cuvânt. Astfel iterarea peste cuvântul suntem trecut, vom stabili index în matrice copii care corespunde cuvânt suport I. Deci, acest este de gând să arate exact ca sarcină, în cazul în care în cazul în care cuvântul [i] este un apostrof, atunci ne-o dorim de a utiliza indicele de "alfabet" - 1. Pentru că am stabilit că este în cazul în care vom stoca apostroful. 

Altfel vom folosi două cuvinte mai mici Suport I. Deci, amintiți-vă că Word poate au capitalizare arbitrar. Și așa vrem să ne asigurăm că suntem folosind o versiune cu litere mici de lucruri. Și apoi scade de la care "a" la o dată din nou ne da ordinea alfabetică poziție de care caracter. Astfel că va fi indexul nostru în matrice copii. 

Și acum, dacă că indicele în copii matrice este nulă, înseamnă că ne-am nu mai poate continua iterarea jos trie nostru. Dacă acesta este cazul, acest cuvânt nu poate fi, eventual, în trie nostru. Deoarece dacă ar fi, care ar Adică nu ar fi o cale până la acest cuvânt. Și nu te-ar întâlni nul. Așa se confruntă cu null, ne întoarcem false. În care cuvântul nu este în dicționar. În cazul în care nu au fost nule, atunci suntem O să iterarea continua. 

Deci mergem acolo cursor pentru a indica faptul că special nod la acel index. Noi continua să faci asta de-a lungul întregul cuvânt, presupunând nu am lovit nul. Asta înseamnă că noi am fost capabil de a obține prin intermediul întregul cuvânt și găsi un nod în try nostru. Dar nu suntem destul de terminat încă. 

Noi nu vrem să se întoarcă doar adevărat. Vrem să se întoarcă cursorul> cuvânt. Din moment ce ne amintim din nou, este "pisica" nu este în dicționarul nostru, și "catastrofă" este, atunci ne vom lua cu succes prin cuvântul "pisică". Dar cursor Cuvântul va fi fals și nu este adevărat. Deci, ne întoarcem cuvânt cursor pentru a indica dacă acest nod este de fapt un cuvânt. Și asta este pentru verificare. 

Deci, haideți să verificați dimensiunea. Deci, dimensiunea va fi destul de ușor din moment ce, amintiți-vă în sarcină, suntem incrementarea dimensiune dicționar pentru fiecare cuvânt pe care le întâlnim. Deci, dimensiunea este doar de gând să reveni dimensiune dicționar. Și asta e tot. 

Deci, în cele din urmă ne-am descărca. Deci descărca, vom folosi un Funcția recursive a face de fapt tot de lucru pentru noi. Deci, funcția noastră va fi numit pe descărcător. Ce este descărcător de gând să faci? Vedem aici că descărcător se va itera peste toți copiii la acest nod special. Și dacă nodul copil nu este null, atunci vom descărca nodul copil. 

Deci, aceasta este de ai descărca recursiv toate de copiii noștri. Odată ce suntem siguri că toți copiii noștri au fost descărcate, apoi ne-am ne putem elibera, așa descărca noi. Aceasta va funcționa recursiv descarce întreaga trie. Și apoi, o dată ce a făcut, ne putem întoarce pur și simplu adevărată. În gol nu poate da greș. Noi doar eliberarea lucruri. Deci, odată ce am terminat eliberarea totul, return true. Și asta e tot. Numele meu este Rob. Și acest lucru a fost speller. 

[Redare a muzicii]