>> ROB Bowden: Hi.
Estic Rob, i el hash de let aquesta solució fora.
Així que aquí anem a posar en pràctica una taula hash general.
Veiem que el node d'estructura de la nostra haixix taula tindrà aquest aspecte.
Així que va a tenir una paraula caràcters matriu de longitud més de la mida 1.
No us oblideu el 1, ja que la màxima paraula al diccionari és 45
caràcters, i després ens anem a necessitarà un personatge extra per al
barra invertida 0.
>> 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.
Així que això és el que un node es sembla.
Ara, aquí és la declaració de la nostra taula hash.
Va a tenir 16.384 cubs, però aquest nombre en realitat no importa.
I, finalment, tindrem la hashtable_size variable global, que
va a començar com 0, i és realitzarà un seguiment de la quantitat de paraules
estaven en el nostre diccionari.
Està bé.
>> Així que donem una ullada a la càrrega.
Així notar que la càrrega, retorna un bool.
Es torna veritat si va ser amb èxit carregat i false en cas contrari.
I es necessita un const char * estrelles diccionari, que és el diccionari
que volem obrir.
Així que això és el primer que farem.
Anem a fopen el diccionari per lectura, i tindrem
per assegurar-se que va tenir èxit pel que si es retorna NULL, llavors 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í mantenim bucle, i ara anem a malloc un sol node.
I, per descomptat, hem de error de comprovació de nou per la qual cosa si mallocing no va tenir èxit
i 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 la paraula d'entrada-> és el carbó de llenya memòria intermèdia paraula de longitud més grandària
un que anem a guardar la paraula polz
Així fscanf va a tornar 1, sempre i ja que era capaç de llegir correctament un
Paraules de l'arxiu.
>> Si passa, ja sigui un error o s'arriba al final del fitxer, no ho farà
retorna 1, en aquest cas si no ho fa retorna 1, finalment anem a trencar
fora d'aquest bucle while.
Així que veiem que una vegada que tinguem èxit llegir una paraula en
entrada-> paraula, llavors anem per discutir aquesta paraula utilitzant la nostra funció hash.
Fem una ullada a la funció hash.
>> Així que vostè realment no necessita per entendre això.
I, de fet, ens vam aturar aquest funció hash de la Internet.
L'única cosa que cal reconèixer és que això pren un char * const paraula,
així que està tenint 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, se li dóna un
índex a la taula hash.
Noteu que estem modding per NUM_BUCKETS de manera que el valor hash 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ó hash, anem per discutir la paraula que llegim
del diccionari i després anem per utilitzar que ha de inserir el
entrada a la taula hash.
Ara, el hash taula hash és el corrent llista vinculada a la taula hash, i
és molt possible que sigui simplement NULL.
Volem inserir la nostra entrada al a partir d'aquesta llista enllaçada, i així
tindrem la nostra entrada actual apuntar al que la taula hash actualment
punts i després anem a emmagatzemar a la taula hash al 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 que s'incrementen de nou.
Així que seguim fent això fins fscanf finalment torna alguna cosa no 1
el punt recordar que hem de entrada gratuïta, pel que fins aquí, ens malloced 1
entrada i tractem de llegir alguna cosa del diccionari.
I no ens llegim amb èxit alguna cosa del diccionari en el qual
cas que necessitem per alliberar l'entrada que ens En realitat mai lloc en la taula hash
i finalment trencar-se.
>> Un cop comencem, hem de veure, bé, què ens separem perquè hi ha
estava llegint un error de l'arxiu o què ens separem perquè arribem a
el final de l'arxiu?
Si hi va haver un error, llavors volem return false perquè la càrrega no ho va fer
èxit, i en el procés, volem descarregar totes les paraules que llegim
en i tanqueu el fitxer de diccionari.
Assumint que vam tenir èxit, llavors només encara han de tancar el diccionari
presentar, i finalment tornar cert ja ens hem carregat amb èxit 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 va a indicar si el
passat com char * paraula, si la cadena passada-in és al diccionari.
Així que si està al diccionari, si és en la nostra taula hash, tornarem
veritat, i si no ho és, anem a tornar false.
Donada aquesta paraula-passatger en, som anar per discutir la paraula.
>> Ara, una cosa important a reconèixer és que en la càrrega, sabíem que tots
les paraules serien minúscules, però aquí, no estem tan segurs.
Si fem una ullada a la nostra funció hash, nostra funció hash realitat
està en minúscula cada personatge de la paraula.
Així que, independentment de la capitalització de paraula, la nostra funció hash es va a
tornar el mateix índex per a qualsevol que sigui el capitalització és, ja que tindria
tornat per a una completament en minúscules versió de la paraula.
Està bé.
>> Així que aquest és el nostre índex.
És la taula hash d'aquesta paraula.
Ara, aquest bucle es va a més de la llista enllaçada
que era en aquest índex.
Així notem que estem inicialitzant entrada per assenyalar a aquest índex.
Seguirem mentre que l'entrada no no NULL d'igualtat, i recordar que
actualitzar el punter a la nostra llista enllaçada entrada és igual a l'entrada-> següent, pel que tenen
nostre punt d'entrada actual a la següent element de llista enllaçada.
Està bé.
>> Així que per a cada entrada de la llista enllaçada, utilitzarem strcasecmp.
No és strcmp perquè una vegada més, hem voler fer si les coses minúscules.
Així que fem servir strcasecmp comparar la paraula que es va fer passar a aquesta funció
en contra de la paraula que és en aquesta entrada.
Si retorna 0, que significa 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 tot per xec.
Està bé.
>> Així que donem una ullada a mida.
Ara, la mida serà bastant simple recordar ja que en la càrrega, per a cada paraula
ens trobem que s'incrementa un mundial hashtable_size variable.
Així la funció de mida és només va a tornar aquest mundial
variables, i això és tot.
>> Ara, per fi, hem de descarregar el diccionari una vegada que tot està fet.
Llavors, com farem això?
Aquí, estem en bucle sobre tots cubs de la nostra taula hash.
Així que hi ha NUM_BUCKETS cubs.
I per a cada llista enllaçada a la nostra haixix taula, anem a llaç sobre el
totalitat de la llista enllaçada l'alliberament de cada element.
Ara, hem de ser curosos, així que aquí estem tenir una variable temporal que é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 alliberem a la
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ò en totes les llistes vinculades a la taula hash, i un cop haguem acabat
amb això, que hem descarregat completament la taula hash, i hem acabat.
Així que és impossible que es descarrega alhora return false, i quan haguem acabat, ens
simplement torni true.