>> ROB BOWDEN: Hi.
Estoy Rob, y el hash de let esta solución fuera.
Así que aquí vamos a poner en práctica una tabla hash general.
Vemos que el nodo de estructura de nuestra hachís tabla va a tener este aspecto.
Así que va a tener una palabra caracteres matriz de longitud más del tamaño 1.
No se olvide el 1, ya que la máxima palabra en el diccionario es 45
caracteres, y luego nos vamos a necesitará un personaje extra para el
barra invertida 0.
>> Y entonces nuestra tabla hash en cada cubo se va a almacenar un
lista enlazada de nodos.
No estamos haciendo el sondeo lineal aquí.
Y así, con el fin de vincular a la siguiente elemento en el cubo, necesitamos un
struct nodo * siguiente.
Así que eso es lo que un nodo se parece.
Ahora, aquí es la declaración de nuestra tabla hash.
Va a tener 16.384 cubos, pero ese número en realidad no importa.
Y, por último, vamos a tener la hashtable_size variable global, que
va a empezar como 0, y es va a realizar un seguimiento de la cantidad de palabras
estaban en nuestro diccionario.
Está bien.
>> Así que echemos un vistazo a la carga.
Así notar que la carga, devuelve un bool.
Se vuelve verdad si fue con éxito cargado y false en caso contrario.
Y se necesita un const char * estrellas diccionario, que es el diccionario
que queremos abrir.
Así que eso es lo primero que vamos a hacer.
Vamos a fopen el diccionario para lectura, y vamos a tener
para asegurarse de que tuvo éxito por lo que si se devuelve NULL, entonces no lo hicimos
abrir correctamente el diccionario y tenemos que devolver false.
>> Pero suponiendo que lo hizo con éxito abierto, entonces queremos leer la
diccionario.
Así seguirá sonando hasta que encontremos alguna razón para salir de este
bucle que ya veremos.
Así mantenemos bucle, y ahora vamos a malloc un solo nodo.
Y, por supuesto, tenemos que error de comprobación de nuevo por lo que si mallocing no tuvo éxito
y queremos descargar cualquier nodo que pasó a malloc antes, cierre la
diccionario y devolver false.
>> Pero haciendo caso omiso de eso, suponiendo tenido éxito, entonces queremos usar fscanf
para leer una sola palabra de nuestro diccionario de a nuestro nodo.
Así que recuerde que la palabra de entrada-> es el carbón de leña búfer palabra de longitud más tamaño
uno que vamos a guardar la palabra pulg
Así fscanf va a regresar 1, siempre y ya que era capaz de leer correctamente un
Palabras del archivo.
>> Si sucede, ya sea un error o se llega el final del archivo, no lo hará
devuelve 1, en cuyo caso si no lo hace devuelve 1, finalmente vamos a romper
fuera de este bucle while.
Así que vemos que una vez que tengamos éxito leer una palabra en
entrada-> palabra, entonces vamos para discutir esa palabra usando nuestra función hash.
Echemos un vistazo a la función hash.
>> Así que usted realmente no necesita para entender esto.
Y, de hecho, nos detuvimos este función hash de la Internet.
La única cosa que hay que reconocer es que esto toma un char * const palabra,
así que está teniendo una cadena como entrada y devolver un int sin signo como salida.
Así que eso es todo, una función hash es, ¿es toma en una entrada, se le da un
índice en la tabla hash.
Nótese que estamos modding por NUM_BUCKETS por lo que el valor hash devuelto
en realidad es un índice en la tabla hash y no indexa más allá de la
límites de la matriz.
>> Así que teniendo en cuenta que la función hash, vamos para discutir la palabra que leemos
del diccionario y después vamos para usar que tiene que insertar el
entrada en la tabla hash.
Ahora, el hash tabla hash es la corriente lista vinculada en la tabla hash, y
es muy posible que sea simplemente NULL.
Queremos insertar nuestra entrada en el a partir de esta lista enlazada, y así
vamos a tener nuestra entrada actual apuntar a lo que la tabla hash actualmente
puntos y luego vamos a almacenar en la tabla hash en el hash
la entrada actual.
>> Así pues, estas dos líneas se insertan con éxito la entrada al principio de la
lista enlazada en ese índice en la tabla hash.
Una vez que hemos terminado con eso, sabemos que encontramos otra palabra en el
diccionario y que se incrementan de nuevo.
Así que seguimos haciendo eso hasta fscanf finalmente regresa algo no 1 en
cuyo punto recordar que tenemos que entrada gratuita, por lo que hasta aquí, nos malloced un
entrada y tratamos de leer algo del diccionario.
Y no nos leemos con éxito algo del diccionario en el cual
caso de que necesitemos para liberar la entrada que nos En realidad nunca puesto en la tabla hash
y finalmente romperse.
>> Una vez que empezamos, tenemos que ver, bueno, qué nos separamos porque hay
estaba leyendo un error desde el archivo o qué nos separamos porque llegamos a
el final del archivo?
Si hubo un error, entonces queremos return false porque la carga no lo hizo
éxito, y en el proceso, queremos descargar todas las palabras que leemos
en y cierre el archivo de diccionario.
Asumiendo que tuvimos éxito, entonces sólo todavía tienen que cerrar el diccionario
presentar, y finalmente regresar cierto ya nos hemos cargado con éxito el
diccionario.
Y eso es todo por la carga.
>> Así que ahora comprobar, dada una tabla hash cargado, que va a tener este aspecto.
A fin de comprobar, devuelve un bool, que va a indicar si el
pasado como char * palabra, si la cadena pasada-in es en el diccionario.
Así que si está en el diccionario, si es en nuestra tabla hash, volveremos
verdad, y si no lo es, vamos a devolver false.
Dada esta palabra-pasajero en, somos ir para discutir la palabra.
>> Ahora, una cosa importante a reconocer es que en la carga, sabíamos que todos
las palabras iban a ser minúsculas, pero aquí, no estamos tan seguros.
Si echamos un vistazo a nuestra función hash, nuestra función hash realidad
está en minúscula cada personaje de la palabra.
Así que, independientemente de la capitalización de palabra, nuestra función hash se va a
devolver el mismo índice para cualquiera que sea el capitalización es, ya que tendría
regresado para una completamente en minúsculas versión de la palabra.
Está bien.
>> Así que ese es nuestro índice.
Es la tabla hash de esta palabra.
Ahora, este bucle se va a más de la lista enlazada
que era en ese índice.
Así notamos que estamos inicializando entrada para señalar a ese índice.
Vamos a seguir mientras que la entrada no no NULL de igualdad, y recordar que
actualizar el puntero en nuestra lista enlazada entrada es igual a la entrada-> siguiente, por lo que tienen
nuestro punto de entrada actual a la siguiente elemento de lista enlazada.
Está bien.
>> Así que para cada entrada de la lista enlazada, vamos a utilizar strcasecmp.
No es strcmp porque una vez más, hemos querer hacer si las cosas minúsculas.
Así que usamos strcasecmp comparar la palabra que se hizo pasar a esta función
en contra de la palabra que es en esta entrada.
Si devuelve 0, que significa que hubo un partido, en el que caso de que queramos
return true.
Nos encontramos con éxito el palabra en nuestra tabla hash.
>> Si no había un partido, entonces estamos ir a la vuelta de nuevo y mirar el
siguiente entrada.
Y continuaremos bucle mientras que hay son entradas de esta lista enlazada.
¿Qué sucede si rompemos fuera de este bucle?
Eso significa que no encontramos una entrada que emparejado esta palabra, en cuyo caso
volvemos false para indicar que nuestra tabla hash no contiene esta palabra.
Y eso es todo por cheque.
Está bien.
>> Así que echemos un vistazo a tamaño.
Ahora, el tamaño va a ser bastante simple recordar ya que en la carga, para cada palabra
nos encontramos que incrementa un mundial hashtable_size variable.
Así la función de tamaño es sólo va a devolver ese mundial
variables, y eso es todo.
>> Ahora, por fin, tenemos que descargar el diccionario una vez que todo está hecho.
Entonces, ¿cómo vamos a hacer eso?
Aquí, estamos en bucle sobre todos cubos de nuestra tabla hash.
Así que hay NUM_BUCKETS cubos.
Y para cada lista enlazada en nuestra hachís mesa, vamos a lazo sobre el
totalidad de la lista enlazada la liberación de cada elemento.
Ahora, tenemos que ser cuidadosos, así que aquí estamos tener una variable temporal que es
almacenar el puntero a la siguiente elemento de la lista enlazada.
Y luego vamos a la libre el elemento actual.
>> Tenemos que estar seguros de que hacemos esto desde que no puede simplemente liberar el elemento actual
y luego tratar de acceder a la siguiente puntero ya que una vez que liberamos a la
la memoria no es válida.
Así que tenemos que mantener en torno a un puntero a el siguiente elemento, entonces podemos liberar el
elemento actual, y entonces podemos actualizar nuestra elemento actual para apuntar a
el siguiente elemento.
>> Vamos bucle while hay elementos en esta lista enlazada.
Haremos eso en todas las listas vinculadas en la tabla hash, y una vez que hayamos terminado
con eso, que hemos descargado completamente la tabla hash, y hemos terminado.
Así que es imposible que se descarga a la vez return false, y cuando hayamos terminado, nos
simplemente devuelva true.