>> ROB BOWDEN: Oi
Estou Rob, e haxix Imos esta solución para fóra.
Entón, aquí imos aplicar unha táboa xeral de hash.
Vemos que o no struct do noso Hash mesa se ve así.
Por iso, vai ter unha palabra de char matriz de lonxitude do tamaño 1.
Non esqueza do 1 desde o máximo palabra no dicionario é de 45
caracteres e, a continuación, imos precisa dun personaxe extra para o
barra invertida 0.
>> E entón a nosa táboa hash en cada balde vai almacenar unha
lista ligada de nós.
Non estamos facendo lineal enquisa aquí.
E así, a fin de obrigar á seguinte elemento no balde, necesitamos un
struct node * seguinte.
Entón é iso que un nodo se parece.
Agora, aquí é a declaración da nosa táboa de hash.
Terá 16.384 baldes, pero ese número non importa realmente.
E, finalmente, imos ter o hashtable_size variable global, que
comezará como 0, e é vai manter o control de cantas palabras
estaban na nosa dicionario.
Todo ben.
>> Entón, imos dar un ollo a carga.
Entón, teña en conta que a carga, el retorna un bool.
Vostede volve verdadeiro se fose correctamente cargado e false se non.
E leva un const char * estrelas dicionario, o cal é o dicionario
que quere abrir.
Así que esta é o primeiro imos facer.
Imos fopen o dicionario para lectura, e nós imos ter
estar seguro de que conseguiu iso, se voltou NULL, entón nós non
abrir correctamente o dicionario e necesitamos voltar false.
>> Pero supoñendo que fixo correctamente aberta, así que queremos ler a
dicionario.
Polo tanto, manter looping ata que atopemos algún motivo para romper ese
lazo que imos ver.
Polo tanto, manter looping, e agora estamos indo malloc para un único nodo.
E, por suposto, necesitamos de erro de verificación de novo para se mallocing non tivo éxito
e queremos descargar calquera nodo que pasou con malloc antes, pechar o
dicionario e voltar false.
>> Pero ignorar que, asumindo que conseguiu, entón queremos usar fscanf
para ler unha soa palabra da nosa dicionario para o noso nodo.
Entón lembre que a palabra de entrada-> é o carácter tapón palabra de lonxitude plus size
que imos almacenar a palabra dentro
Entón fscanf vai voltar 1, sempre como era capaz de ler con éxito un
palabra do arquivo.
>> Se calquera erro ou chegamos a fin do ficheiro, non vai
voltar un caso en que se iso non acontecer voltar 1, estamos finalmente vai romper
fóra deste loop while.
Así, vemos que xa que temos correctamente ler unha palabra en
entry-> palabra, entón nós estamos indo ao hash esa palabra usando nosa función hash.
Imos dar un ollo a función hash.
>> Entón, o que realmente non precisa para entender iso.
E, de feito, nós só tirou este de hash función de internet.
O único que ten que recoñecer é que iso leva un const char * palabra,
el está tomando unha cadea como entrada e retornando un int non asinado como saída.
Entón, iso é todo unha función hash é, é ten en unha entrada, dálle un
índice na táboa de hash.
Teña en conta que estamos modding por num_buckets polo tanto, o valor hash retorno
en realidade, é un índice para a táboa hash e non indexa ademais do
límites da matriz.
>> Así, dado que a función de hash, imos hash a palabra que lemos
do dicionario e logo, imos usar que ten que introducir o
entrada na táboa de hash.
Agora mestura hashtable é o actual lista ligada na táboa de hash, e
é moi posible que sexa só NULL.
Queremos introducir a nosa entrada no inicio desta lista ligada, e así por
imos ter a nosa entrada actual apuntan a que a táboa hash actualmente
puntos para e logo, imos para almacenar na táboa de hash en hash
a entrada actual.
>> Entón, estas dúas liñas inserir correctamente a entrada no comezo da
lista ligada no que o índice de na táboa de hash.
Xa que estamos a facer que, sabemos que atopamos outra palabra no
dicionario e incrementar de novo.
Entón, nós continuar facendo isto ata que fscanf finalmente volve algo non 1 a
que punto lembrar que necesitamos entrada gratuíta, polo que ata aquí, nós malloced un
entrada e tentamos ler algo desde o dicionario.
E nós non ler correctamente algo do dicionario en que
caso, necesitamos liberar a entrada que nunca realmente poñer en táboa hash
e, finalmente, se romper.
>> Así que saír, necesitamos ver, así, fixemos saír porque non
Foi un erro de lectura do ficheiro, ou fixemos saír porque alcanzamos
a fin do ficheiro?
Se houbo un erro, entón queremos return false porque a carga non
éxito, e, no proceso, queremos descargar todas as palabras que lemos
e pecha o arquivo de dicionario.
Asumindo que tivo éxito, entón nós só aínda que pechar o dicionario
ficheiro e, finalmente, volver true desde nós cargou con éxito o
dicionario.
E iso por carga.
>> Entón agora comprobar, dada unha táboa hash cargado, se ve así.
Polo tanto, asegúrese de, el retorna un bool, que vai indicar a
pasou-in char * palabra, se o cadea pasada-in está no noso dicionario.
Entón, se é no dicionario, de ser o na nosa táboa hash, imos voltar
verdade, e se non é, imos voltar false.
Dada esta palabra pasou-in, estamos vai botar a palabra.
>> Agora, unha cousa importante a recoñecer é que en carga, sabiamos que todo
as palabras ían ser minúsculas, pero aquí, non ten tanta certeza.
Se derme un ollo a nosa función de hash, nosa función hash realmente
é lowercasing cada personaxe da palabra.
Polo tanto, con independencia da capitalización de palabra, a nosa función hash vai
volver o mesmo índice para calquera que sexa o capitalización é o que
retorno a unha totalmente minúsculas versión da palabra.
Todo ben.
>> Entón, este é o noso índice.
É a táboa de hash para esa palabra.
Agora, este loop vai a máis dunha lista ligada
que estaba naquel índice.
Entón, teña en conta que estamos arrincando entrada para apuntar a este índice.
Nós imos seguir mentres entrada fai non coincide NULL, e recorda que
actualizar o punteiro na nosa lista ligada entrada é igual a entrada-> seguinte, así que ten
noso punto de entrada actual ao elemento seguinte da lista ligada.
Todo ben.
>> Así, para cada entrada na lista ligada, imos usar strcasecmp.
Non é strcmp porque unha vez máis, nós queren facer as cousas caso insensible.
Entón, usamos strcasecmp comparar a palabra que foi pasado para esta función
contra a palabra que é nesa entrada.
Se voltar 0, que significa que houbo un partido, caso en que queremos
return true.
Atopamos con éxito a palabra na nosa táboa de hash.
>> Se non foi un xogo, entón estamos indo a repetir de novo e ollar para o
seguinte entrada.
E nós imos seguir looping mentres non son entradas nesta lista ligada.
Qué acontece se romper fóra deste loop for?
Isto significa que non atopou unha entrada que combinaba esta palabra, caso en que
retornamos false para indicar que o noso táboa hash non contiña esta palabra.
E iso por cheque.
Todo ben.
>> Entón, imos dar un ollo ao tamaño.
Agora, o tamaño será moi sinxelo Teña en conta que, unha vez en carga, para cada palabra
descubrimos que incrementado un mundial hashtable_size variable.
Así, a función de tamaño é só Vai voltar ese mundial
variable, e é iso.
>> Agora, por fin, hai que descargar o dicionario xa que todo está feito.
Entón, como imos facelo?
Aquí, nós estamos loop para todos baldes de nosa táboa de hash.
Polo tanto, hai num_buckets baldes.
E para cada lista ligada na nosa de hash mesa, imos varrer o
totalidade da lista ligada liberando cada elemento.
Agora, hai que ter coidado, entón aquí nós ten unha variable temporal que se
gardar o punteiro ao seguinte elemento da lista encadeada.
E entón nós estamos indo a libre o elemento actual.
>> Necesitamos estar seguro de que facemos isto dende que non pode só liberar o elemento actual
e probe acceder o seguinte punteiro desde xa que liberou-se o
memoria convértese en incorrecto.
Entón, necesitamos manter en torno a un punteiro para o seguinte elemento, entón podemos liberar o
elemento actual, e entón podemos actualizar noso elemento actual para ligar a
o seguinte elemento.
>> Imos loop while hai elementos nesta lista encadeada.
Nós imos facer isto para todas as listas ligadas en táboa hash, e xa que estamos a facer
con iso, temos completamente descargada táboa hash, e estamos a facer.
Polo tanto, é imposible que descarrega para sempre return false, e cando estea listo, nós
basta voltar certo.