[REPRODUCCIÓ DE MÚSICA] 

ROB Bowden: Hi. Sóc Rob. I sortirem d'aquesta solució. Així que aquí anem a posar en pràctica una taula general. Veiem que el node d'estructura de la nostra taula tindrà aquest aspecte. Així que va a tenir una paraula caràcters matriu de mida LONGITUD + 1. No us oblideu el + 1, ja que la màxima paraula al diccionari és 45 personatges. I després anem a necessitar una extra caràcter pel zero barra invertida. 

I llavors la nostra taula hash en cada cub es va a emmagatzemar un llista enllaçada de nodes. No estem fent el sondeig lineal aquí. I així, per tal de vincular la següent element en el cub, necessitem un struct node * següent. D'acord. Així que això és el que un node es sembla. 

Ara aquí és la declaració de la nostra taula hash. Va a tenir 16.834 galledes. Però aquest nombre en realitat no importa. I, finalment, tindrem la La mida de la taula hash variable global, que començarà com a zero. I es va a realitzar un seguiment de com moltes paraules són al diccionari. 

Així que donem una ullada a la càrrega. Tingueu en compte que la càrrega, retorna un bool. Es torna veritat si va ser amb èxit carregat, i false en cas contrari. I pren un char * const diccionari, que és el diccionari que volem obrir. Així que això és el primer que farem. 

Anem a fopen la diccionari per llegir. I haurem de fer segur que va succeir. Així que si és retornat NULL, llavors nosaltres no ho vam fer obrir correctament el diccionari. I hem de tornar false. Però suposant que ho va fer amb èxit obert, llavors volem llegir la diccionari. Així seguirà sonant fins que trobem alguna raó per sortir d'aquest bucle, que ja veurem. Així seguirà sonant. 

I ara anem a malloc un sol node. I per descomptat que necessitem ventilar pots tornar a intentar-ho. Així que si mallocing no va tenir èxit, a continuació, volem descarregar qualsevol node que va passar a malloc abans, tanqui la diccionari i tornar false. Però fent cas omís d'això, suposant tingut èxit, llavors volem utilitzar fscanf per llegir una sola paraula del nostre diccionari de al nostre node. Així que recordi que l'entrada> paraula és el carbó de llenya memòria intermèdia paraula de mida lenghth +1 que anem a guardar la paraula polz 

Així fscanf va a tornar 1, sempre i ja que va ser capaç d'èxit llegir una paraula de l'arxiu. Si passa, ja sigui un error, o que arribar al final de l'arxiu, es no retornarà 1. En aquest cas no retorna 1, finalment sortirem de aquest bucle while. Així que veiem que una vegada que tinguem èxit llegir una paraula en entrada> paraula, llavors anem a la paraula utilitzant la nostra funció hash. 

Fem una ullada a la funció hash. Així que vostè realment no necessita per entendre això. I en realitat ens vam aturar aquest hash funcionar des d'internet. L'única cosa que cal reconèixer és que això pren un char * paraula const. Així que ha de prendre una cadena com a entrada, i tornar un int sense signe com a sortida. Així que això és tot, una funció hash és, és pren en una entrada i li dóna una índex a la taula hash. 

Noteu que estem moding per NUM_BUCKETS, de manera que el valor retornat en realitat és un índex a la taula hash i no indexa més enllà de la límits de la matriu. Així que tenint en compte que la funció, anem per discutir la paraula que llegim la diccionari. I després farem servir el hash per inserir el entrada a la taula hash. 

Picada Ara Hashtable és el corrent llista vinculada a la taula. I és molt possible que és només NULL. Volem inserir la nostra entrada al a partir d'aquesta llista enllaçada. Així que tindrem la nostra actual punt d'entrada al que la taula hash Actualment assenyala. I després anem a emmagatzemar, a la taula hash en el hash, l'entrada actual. Així doncs, aquestes dues línies s'insereixen amb èxit l'entrada al principi de la llista enllaçada en aquest índex a la taula hash. 

Un cop hem acabat amb això, sabem que trobem una altra paraula al diccionari, i incrementem de nou. Així que seguim fent això fins fscanf finalment va tornar alguna cosa no 1 el punt recordar que hem de alliberar a l'entrada. Així que aquí tenim malloced una entrada. I tractem de llegir alguna cosa del diccionari. I no ens llegim amb èxit alguna cosa del diccionari, en aquest cas hem de alliberar l'entrada que en realitat mai posem al taula hash, i finalment trencar. 

Un cop trenquem hem de veure, bé, què ens separem perquè hi ha estava llegint un error de l'arxiu? O què ens separem perquè ens arribat al final de l'arxiu? Si hi va haver un error, a continuació, volem tornar false. Com que la càrrega no va tenir èxit. I en el procés que volem descarregar totes les paraules que llegim en, i tancar el fitxer de diccionari. 

Assumint que vam tenir èxit, llavors només encara han de tancar el diccionari presentar, i finalment de tornada veritat ja que carregar correctament el diccionari. I això és tot per la càrrega. Així que ara comprovar, donada una taula hash carregat, que tindrà aquest aspecte. Per tal de comprovar, torna un bool, que és va a indicar si la passar en char * paraula, si el passat en la cadena està al diccionari. Així que si està al diccionari, si està en la nostra taula hash, tornarem realitat. I si no és així, anem a tornar false. 

Tenint en compte això va passar en la paraula, estem anar per discutir la paraula. Ara una cosa important a reconèixer és que en la càrrega que sabíem que tota la paraules que estarem en minúscules. Però aquí no estem tan segurs. Si fem una ullada a la nostra funció hash, nostra funció hash realitat és la caixa inferior de cada personatge de la paraula. Així que, independentment de la capitalització de paraula, la nostra funció hash és el retorn el mateix índex per la qual cosa el capitalització és, ja que tindria tornat per a una completament en minúscules versió de la paraula. D'acord. Aquest és el nostre índex està en el taula hash per a aquesta paraula. 

Ara bé, aquest bucle es va a iterar sobre la llista enllaçada que era en aquest índex. Així notem que estem inicialitzant entrada per assenyalar a aquest índex. Continuarem quan! entrada = NULL. I recorda que l'actualització del punter en la nostra llista d'inscrits vinculats = entrada> següent. Així que tenim el nostre punt d'entrada actual per el següent element de la llista enllaçada. 

Així que per a cada entrada de la llista enllaçada, utilitzarem strcasecmp. No és StrComp. Perquè, una vegada més, volem fer si les coses minúscules. Així que fem servir strcasecmp comparar l' paraula que ha passat a través d'aquest funció en contra de la paraula el que hi ha en aquesta entrada. Si torna zero, que vol dir que hi va haver un partit, en el qual cas que vulguem return true. Ens trobem amb èxit el paraula en la nostra taula hash. 

Si no hi havia un partit, llavors estem anar a la volta de nou i mirar el següent entrada. I continuarem bucle mentre que hi ha són entrades d'aquesta llista enllaçada. Què passa si trenquem fora d'aquest bucle? Això vol dir que no trobem una entrada que aparellat aquesta paraula, en aquest cas tornem false per indicar que la nostra taula hash no conté aquesta paraula. I això és un xec. 

Així que donem una ullada a mida. Ara la mida serà bastant simple. Atès recordar en la càrrega, per a cada paraula trobem, hem incrementat un mundial La mida de la taula hash variable. Així que la funció de mida és només va tornar variable global. I això és tot. 

Ara, per fi, hem de descarregar el diccionari una vegada que tot està fet. Llavors, com farem això? Aquí estem bucle sobre tots els cubs de la nostra taula. Així que hi ha NUM_BUCKETS cubs. I per a cada llista enllaçada a la nostra taula hash, que anem a reproduir indefinidament la totalitat de la llista enllaçada, l'alliberament de cada element. 

Ara hem de tenir cura. Així que aquí tenim una variable temporal això és emmagatzemar el punter a la següent element de la llista enllaçada. I després anem a la lliure l'element actual. Hem d'estar segurs que fem això des que no pot simplement alliberar l'element actual i després tractar d'accedir a la següent punter, ja que una vegada que ens hem alliberat ell, la memòria no és vàlida. 

Així que hem de mantenir al voltant d'un punter a el següent element, llavors podem alliberar el element actual, i llavors podem actualitzar nostra element actual per apuntar a el següent element. Anem bucle while hi ha elements en aquesta llista enllaçada. Farem això per a tots ells vinculats llistes a la taula hash. I una vegada que haguem acabat amb això, hem completament descarregada la taula hash, i hem acabat. Així que és impossible per a descàrrega per tornar mai falsa. I quan acabem, ens simplement torni true. 

Anem a donar a aquesta solució una oportunitat. Així que donem una ullada al nostre struct node es veurà així. Aquí veiem que tindrem un bool paraula i un node d'estructura * nens ALFABET suport. Així que la primera cosa que vostè pot ser preguntant, per què és ALFABET ed defineix com 27? Bé, recordeu que nosaltres necessitarem estar manejant l'apòstrof. Així que serà una mena cas especial al llarg d'aquest programa. 

Ara recorda com 1 trie en realitat funciona. Diguem que estem indexant la paraula "Gats". Després, des de l'arrel del trienni, anem a mirar els nens matriu, i anem a mirar el índex que correspon a la lletra C. Així que serà indexada 2. Així que tenint en compte que, que la voluntat donar-nos un nou node. I després treballarem a partir d'aquest node. 

Així que tenint en compte que el node, estem un cop més va a mirar la matriu nens. I anem a buscar en l'índex zero per correspondre a la A en el gat. Així que anirem a aquest node, i atès que el node que anem per mirar la final és una correspon T. I de passar a aquest node, finalment, ens hem mirat del tot mitjançant la nostra paraula "gat". I ara bool paraula se suposa que indica si aquesta paraula donada és en realitat una paraula. 

Llavors, per què necessitem aquest cas especial? Doncs el de la paraula "catàstrofe" és al diccionari, però el paraula "gat" no ho és? Així i mirant per veure si la paraula "gat" és al diccionari, estem va a semblar amb èxit a través els índexs de C-A-T a node regió. Però això és només perquè la catàstrofe succeït per crear nodes en el camí a partir de C-A-T, tot el camí a al final de la paraula. Així bool paraula s'utilitza per indicar si aquest lloc en particular indica, en realitat una paraula. 

Està bé. Així que ara que sabem el que és trienni va a semblar, donem una ullada a la funció de la càrrega. Així que la càrrega va a tornar un bool Perquè si estem amb èxit o sense èxit carregat el diccionari. I això serà el diccionari que volem carregar. 

Així que el primer que hem de fer és obrir fins a aquest diccionari per llegir. I hem d'assegurar nosaltres no fallem. Així que si el diccionari no era obert amb èxit, tornarà nul, en aquest cas estem tornarà false. Però suposant que èxit obert, llavors podem realment llegir a través del diccionari. 

Així que el primer que anem a volem fer és que tenim aquesta arrel variable global. Ara arrel serà un node *. És el cim de la nostra trie que estem va a recórrer en iteració. Així que el primer que anem a voler fer és assignar memòria per a la nostra arrel. Noteu que estem fent servir la calloc funció, que és bàsicament la mateixa com la funció malloc, excepte que és garantit per tornar una cosa que és completament portat a zero. Així que si fem servir malloc, necessitaríem passar per tots els punters en la nostra node, i assegureu-vos que són tots nuls. Així calloc ho farà per nosaltres. 

Ara com malloc, hem de fer Assegureu-vos que l'assignació va ser en realitat reeixida. Si això retorna null, llavors hagi de tancar o diccionari presentar i tornar false. Així que assumint que l'assignació es èxit, utilitzarem un node * cursor per recórrer la nostra trienni. Així que les nostres arrels mai canviarà, però farem servir el cursor per en realitat anar d'un node a un altre. 

Així que en aquest bucle que estem llegint amb el fitxer de diccionari. I estem usant fgetc. Fgetc va a agafar un sol caràcter de l'arxiu. Anem a continuar amb l'acaparament caràcters, mentre que no arriben fins a la final de l'arxiu. 

Hi ha dos casos que hem de manejar. El primer, si el caràcter no era una nova línia. Així que sabem que si era una nova línia, a continuació, estem a punt de passar a una nova paraula. Però suposant que no era una nova línia, a continuació, aquí volem esbrinar el Índex anem a índex en en la matriu dels nens que miràvem abans. 

Així que, com he dit abans, hem de cas especial l'apòstrof. Noteu que estem usant el ternari operador d'aquí. Així que anem a llegir això, ja que si el caràcter es llegeix en una era apòstrof, a continuació, establirem index = "alfabet" -1, que ser l'índex 26. 

Si no, si no fos un apòstrof, no establirem l'índex igual a c - a. Així que recordi tornar de prèviament p-sèries, c - a què ens donarà la posició alfabètica de C. Així que si C és la lletra A, això es donar-nos l'índex zero. Perquè la lletra B, se li donarà ens l'índex 1, i així successivament. 

Així que això ens dóna l'índex a la fills matriu que volem. Ara bé, si aquest índex és actualment nul · la en els nens, que significa que un node no existeix en l'actualitat d'aquest camí. Així que hem d'assignar un node per aquest camí. Això és el que farem aquí. 

Així que utilitzarem de nou el calloc funció, pel que no ha de zero tots els punters. I de nou hem de comprovar que calloc no va fallar. Si calloc va deixar, llavors necessitem per descarregar tot, tancar la nostra diccionari, i tornar false. Així que suposant que no va fallar, llavors això crearà un nou fill per a nosaltres. I després anirem a aquest nen. El nostre cursor iterará a aquest nen. 

Ara bé, si això no era nul, per començar, a continuació, el cursor només es pot repetir a aquest nen sense arribar a haver de assignar res. Aquest és el cas en què primer va passar assignar la paraula "gat". I això vol dir que quan anem a assignar "Catàstrofe", que no és necessari per crear nodes per a C-A-T de nou. Ja existeixen. 

Què és aquest lloc? Aquesta és la condició en la que C era barra invertida n, on c és una línia. Això vol dir que tenim èxit completat una paraula. Ara, què és el que volem fer quan completat amb èxit una paraula? Utilitzarem aquest camp la paraula dins del nostre node estructura. Volem establir que en true. Així que indica que aquest node indica un èxit paraula, una paraula real. 

Ara estableixi que en true. Volem restablir la nostra cursor fins al punt al començament del trienni de nou. I, finalment, incrementar el nostre diccionari mida, ja que ens trobem una altra obra. Així que seguirem fent això, lectura de caràcter per caràcter, la construcció de nous nodes en el nostre trienni i per a cada paraula al diccionari, fins finalment arribem C! = EOF, en el qual cas sortim de l'arxiu. 

Ara hi ha dos casos sota que podríem haver colpejat EOF. La primera és si hi va haver un error llegir el fitxer. Així que si hi va haver un error, haurà de fer el típic. Descarregueu tot, prop arxiu, torna falsa. Suposant que no era un error, que simplement vol dir que realment va colpejar el final de l'arxiu, en aquest cas, es tanca el presentar i tornar true ja que diccionari carregat correctament en la nostra trie. 

Així que ara anem a veure xec. Quant a la funció de comprovació, veiem El registre d'entrada es va a tornar un bool. Retorna true si aquesta paraula que és que passa és en la nostra trienni. Retorna false en cas contrari. Llavors, com determinar si aquesta paraula és en la nostra triennis? 

Veiem aquí que, igual que abans, farem servir el cursor per iterar a través del nostre trie. Ara aquí repetirem llarg de tota la nostra paraula. Així iteració en la paraula que estem passat, anem a determinar la índex en la matriu els nens que correspon a la paraula suport I. Així que aquest serà exactament com de càrrega, en la qual si la paraula [i] és un apòstrof, llavors volem utilitzar l'índex "alfabet" - 1. Com que es va determinar que aquesta és on anem a emmagatzemar apòstrofs. 

Else utilitzarem dues paraules més baixa suport I. Així que recorda aquesta paraula pot tenir la capitalització arbitrària. I pel que volem assegurar-nos que estem usant una versió en minúscules de les coses. I després restar que 'a' alhora de nou ens dóna la alfabètic posició d'aquest caràcter. Així que serà el nostre índex en la matriu dels nens. 

I ara si aquest índex en els nens matriu és nul, això significa que ja no pot continuar la iteració baixar la trie. Si aquest és el cas, aquesta paraula no pot possiblement estar en la nostra Trie. Atès que si ho fos, que ho faria significa no hi hauria un camí a aquesta paraula. I mai es trobaria nul. Així que trobar nul, tornem falsa. La paraula no és al diccionari. Si no fos nul, llavors estem continuarà la iteració. 

Així que anem per aquí cursor per apuntar a aquesta particular node en aquest índex. Nosaltres seguim fent que al llarg la paraula completa, suposant mai colpegem nul. Això vol dir que hem estat capaços d'obtenir a través d' tota la paraula i trobar un node en el nostre intent. Però no hem acabat encara. 

No volem simplement tornar true. Volem tornar cursor> paraula. Atès que recordar una vegada més, és "gat" no és al diccionari, i "catàstrofe" És, llavors tindrem èxit que obtenim a través de la paraula "gat". Però cursor paraula serà falsa i no és cert. Així que tornem cursor paraula per indicar si aquest node és en realitat una paraula. I això és tot per xec. 

Així que anem a veure la mida. Així que la mida serà bastant fàcil ja que, recorda en la càrrega, estem incrementant la mida del diccionari per cada paraula que ens trobem. Així que la mida és només va a tornar la mida del diccionari. I això és tot. 

Així, finalment, hem descarregar. Així que es baixa, anem a utilitzar una funció recursiva per fer realitat tots part del treball per nosaltres. Així que la nostra funció va a ser cridats descarregador. Què està descarregador farem? Veiem aquí que descarregador va a iterar sobre tots els infants en aquest node particular. I si el node fill no és null, llavors anem a descarregar el node secundari. 

Així que aquest és el teu cas de forma recursiva descarregui tots els nostres nens. Quan estiguem segurs que tots els nostres nens s'han descarregat, llavors pot alliberar a nosaltres mateixos, així descarregar nosaltres mateixos. Això funciona de manera recursiva descarregar tot el trienni. I un cop fet això, només podem tornar true. Unload no pot fallar. Només estem alliberant coses. Així que un cop haguem acabat alliberant tot, tornar true. I això és tot. El meu nom és Rob. I això va ser corrector ortogràfic. 

[REPRODUCCIÓ DE MÚSICA]