[REPRODUCCIÓN DE MÚSICA] 

ROB BOWDEN: Hi. Soy Rob. Y vamos a salir de esta solución. Así que aquí vamos a poner en práctica una tabla general. Vemos que el nodo de estructura de nuestra tabla va a tener este aspecto. Así que va a tener una palabra caracteres matriz de tamaño LONGITUD + 1. No se olvide el + 1, ya que la máxima palabra en el diccionario es 45 personajes. Y luego vamos a necesitar una extra carácter para el cero barra invertida. 

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. Aceptar. Así que eso es lo que un nodo se parece. 

Ahora aquí es la declaración de nuestra tabla hash. Va a tener 16.834 baldes. Pero ese número en realidad no importa. Y, por último, vamos a tener la El tamaño de la tabla hash variable global, que va a empezar como cero. Y se va a realizar un seguimiento de cómo muchas palabras están en el diccionario. 

Así que echemos un vistazo a la carga. Tenga en cuenta que la carga, devuelve un bool. Se vuelve verdad si fue con éxito cargado, y false en caso contrario. Y toma un char * const diccionario, que es el diccionario que queremos abrir. Así que eso es lo primero que vamos a hacer. 

Vamos a fopen la diccionario para leer. Y vamos a tener que hacer seguro de que sucedió. Así que si es devuelto NULL, entonces nosotros 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í seguirá sonando. 

Y ahora vamos a malloc un solo nodo. Y por supuesto que necesitamos ventilar puedes volver a intentarlo. Así que si mallocing no tuvo éxito, a continuación, 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 entrada> palabra es el carbón de leña búfer palabra de tamaño lenghth + 1 que vamos a guardar la palabra pulg 

Así fscanf va a regresar 1, siempre y ya que fue capaz de éxito leer una palabra del archivo. Si sucede, ya sea un error, o que llegar al final del archivo, se no devolverá 1. En cuyo caso no devuelve 1, finalmente vamos a salir de este bucle while. Así que vemos que una vez que tengamos éxito leer una palabra en entrada> palabra, entonces vamos a la palabra utilizando nuestra función hash. 

Echemos un vistazo a la función hash. Así que usted realmente no necesita para entender esto. Y en realidad nos detuvimos este hash funcionar desde internet. La única cosa que hay que reconocer es que esto toma un char * palabra const. Así que ha de tomar 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 y le da una índice en la tabla hash. 

Nótese que estamos moding por NUM_BUCKETS, de manera que el valor 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, vamos para discutir la palabra que leemos la diccionario. Y luego vamos a usar el hash para insertar el entrada en la tabla hash. 

Picadillo Ahora hashtable es la corriente lista vinculada en la tabla. Y es muy posible que es sólo NULL. Queremos insertar nuestra entrada en el a partir de esta lista enlazada. Así que vamos a tener nuestra actual punto de entrada a lo que la tabla hash Actualmente señala. 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 incrementamos de nuevo. Así que seguimos haciendo eso hasta fscanf finalmente regresó algo no 1 en cuyo punto recordar que tenemos que liberar a la entrada. Así que aquí tenemos malloced una entrada. Y tratamos de leer algo del diccionario. Y no nos leemos con éxito algo del diccionario, en cuyo caso tenemos que liberar la entrada que en realidad nunca ponemos en el tabla hash, y finalmente romper. 

Una vez que rompemos tenemos que ver, bueno, qué nos separamos porque hay estaba leyendo un error desde el archivo? ¿O qué nos separamos porque nos alcanzado el final del archivo? Si hubo un error, a continuación, queremos devolver false. Debido a que la carga no tuvo éxito. Y en el proceso que queremos descargar todas las palabras que leemos en, y cerrar el archivo de diccionario. 

Asumiendo que tuvimos éxito, entonces sólo todavía tienen que cerrar el diccionario presentar, y finalmente de vuelta verdad ya que cargó correctamente 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 es va a indicar si la pasar en char * palabra, si el pasado en la cadena está en el diccionario. Así que si está en el diccionario, si está en nuestra tabla hash, vamos a volver realidad. Y si no es así, vamos a devolver false. 

Teniendo en cuenta esto pasó en la palabra, estamos ir para discutir la palabra. Ahora una cosa importante a reconocer es que en la carga que sabíamos que toda la palabras que vamos a estar en minúsculas. Pero aquí no estamos tan seguros. Si echamos un vistazo a nuestra función hash, nuestra función hash realidad es la caja inferior de cada personaje de la palabra. Así que, independientemente de la capitalización de palabra, nuestra función hash es el retorno el mismo índice para lo que el capitalización es, ya que tendría regresado para una completamente en minúsculas versión de la palabra. De acuerdo. Ese es nuestro índice está en el tabla hash para esta palabra. 

Ahora bien, este bucle se va a iterar sobre la lista enlazada que era en ese índice. Así notamos que estamos inicializando entrada para señalar a ese índice. Vamos a continuar cuando! entrada = NULL. Y recuerda que la actualización del puntero en nuestra lista de inscritos vinculados = entrada> siguiente. Así que tenemos nuestro punto de entrada actual para el siguiente elemento de la lista enlazada. 

Así que para cada entrada de la lista enlazada, vamos a utilizar strcasecmp. No es StrComp. Porque, una vez más, queremos hacer si las cosas minúsculas. Así que usamos strcasecmp comparar la palabra que se ha pasado a través de este función en contra de la palabra lo que hay en esta entrada. Si devuelve cero, 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 un cheque. 

Así que echemos un vistazo a tamaño. Ahora el tamaño va a ser bastante simple. Dado que recordar en la carga, para cada palabra encontramos, hemos incrementado un mundial El tamaño de la tabla hash variable. Así que la función de tamaño es sólo va volver variable global. 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 bucle sobre todos los cubos de nuestra mesa. Así que hay NUM_BUCKETS cubos. Y para cada lista enlazada en nuestra tabla hash, que vamos a reproducir indefinidamente la totalidad de la lista enlazada, la liberación de cada elemento. 

Ahora tenemos que tener cuidado. Así que aquí tenemos una variable temporal eso 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 nos hemos liberado él, 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 para todos ellos vinculados listas en la tabla hash. Y una vez que hayamos terminado con eso, hemos completamente descargada la tabla hash, y hemos terminado. Así que es imposible para descarga para volver jamás falsa. Y cuando terminemos, nos simplemente devuelva true. 

Vamos a dar a esta solución una oportunidad. Así que echemos un vistazo a lo nuestro struct nodo se verá así. Aquí vemos que vamos a tener un bool palabra y un nodo de estructura * niños ALFABETO soporte. Así que la primera cosa que usted puede ser preguntándose, ¿por qué es ALFABETO ed define como 27? Bueno, recuerde que nosotros vamos a necesitar estar manejando el apóstrofe. Así que va a ser algo así como un caso especial lo largo de este programa. 

Ahora recuerda cómo un trie en realidad funciona. Digamos que estamos indexando la palabra "gatos". Luego, desde la raíz del trie, vamos a mirar a los niños matriz, y vamos a mirar el índice que corresponde a la letra C. Así que será indexada 2. Así que teniendo en cuenta que, que la voluntad darnos un nuevo nodo. Y luego vamos a trabajar a partir de ese nodo. 

Así que teniendo en cuenta que el nodo, estamos una vez más va a mirar la matriz niños. Y vamos a buscar en el índice cero para corresponder a la A en el gato. Así que vamos a ir a ese nodo, y dado que el nodo que vamos para mirar la final es una corresponde T. Y de pasar a ese nodo, por último, nos hemos mirado por completo a través de nuestra palabra "gato". Y ahora bool palabra se supone que indica si esta palabra dada es en realidad una palabra. 

Entonces, ¿por qué necesitamos ese caso especial? Pues lo de la palabra "catástrofe" es en el diccionario, pero el palabra "gato" no lo es? Así y mirando para ver si la palabra "gato" está en el diccionario, estamos va a parecer con éxito a través los índices de C-A-T en nodo región. Pero eso es sólo porque la catástrofe sucedido para crear nodos en el camino a partir de C-A-T, todo el camino a el final de la palabra. Así bool palabra se utiliza para indicar si este lugar en particular indica, en realidad una palabra. 

Está bien. Así que ahora que sabemos lo que es trie va a parecer, echemos un vistazo a la función de la carga. Así que la carga va a devolver un bool Porque si estamos con éxito o sin éxito cargado el diccionario. Y esto va a ser el diccionario que queremos cargar. 

Así que lo primero que tenemos que hacer es abrir hasta ese diccionario para leer. Y tenemos que asegurarnos nosotros no fallamos. Así que si el diccionario no era abierto con éxito, devolverá nulo, en cuyo caso estamos va a devolver false. Pero suponiendo que éxito abierto, entonces podemos realmente leer a través del diccionario. 

Así que lo primero que vamos a queremos hacer es que tenemos esta raíz variable global. Ahora raíz va a ser un nodo *. Es la cima de nuestra trie que estamos va a recorrer en iteración. Así que lo primero que vamos a querer hacer es asignar memoria para nuestra raíz. Nótese que estamos usando la calloc función, que es básicamente la misma como la función malloc, excepto que es garantizado para devolver algo que es completamente llevado a cero. Así que si usamos malloc, necesitaríamos pasar por todos los punteros en nuestra nodo, y asegúrese de que son todos nulos. Así calloc lo hará por nosotros. 

Ahora como malloc, tenemos que hacer Asegúrese de que la asignación fue en realidad exitosa. Si esto devuelve null, entonces tenga que cerrar o diccionario presentar y devolver false. Así que asumiendo que la asignación se éxito, vamos a utilizar un nodo * cursor para recorrer nuestra trie. Así que nuestras raíces nunca va a cambiar, pero vamos a usar el cursor para en realidad ir de un nodo a otro. 

Así que en este bucle que estamos leyendo a través del archivo de diccionario. Y estamos usando fgetc. Fgetc va a agarrar un solo carácter del archivo. Vamos a continuar con el acaparamiento caracteres, mientras que no llegan hasta la final del archivo. 

Hay dos casos que tenemos que manejar. El primero, si el carácter no era una nueva línea. Así que sabemos que si era una nueva línea, a continuación, estamos a punto de pasar a una nueva palabra. Pero suponiendo que no era una nueva línea, a continuación, aquí queremos averiguar el Índice vamos a índice en en la matriz de los niños que mirábamos antes. 

Así que, como he dicho antes, tenemos que caso especial el apóstrofe. Nótese que estamos usando el ternario operador de aquí. Así que vamos a leer esto, ya que si el carácter se lee en una era apóstrofe, a continuación, vamos a establecer index = "alfabeto" -1, que se ser el índice 26. 

Si no, si no fuera un apóstrofe, no vamos a establecer el índice igual a c - a. Así que recuerde volver de previamente p-series, c - a que nos va a dar la posición alfabética de C. Así que si C es la letra A, esto se darnos el índice cero. Porque la letra B, se le dará nos el índice 1, y así sucesivamente. 

Así que esto nos da el índice en la hijos matriz que queremos. Ahora bien, si este índice es actualmente nula en los niños, que significa que un nodo no existe en la actualidad de ese camino. Así que tenemos que asignar un nodo para ese camino. Eso es lo que vamos a hacer aquí. 

Así que vamos a utilizar de nuevo el calloc función, por lo que no tiene que cero todos los punteros. Y de nuevo tenemos que comprobar que calloc no falló. Si calloc dejó, entonces necesitamos para descargar todo, cerrar nuestra diccionario, y devolver false. Así que suponiendo que no falló, entonces esto creará un nuevo hijo para nosotros. Y luego vamos a ir a ese niño. Nuestro cursor iterará a ese niño. 

Ahora bien, si esto no era nulo, para empezar, a continuación, el cursor sólo se puede repetir a ese niño sin llegar a tener que asignar nada. Este es el caso en el que primero pasó asignar la palabra "gato". Y eso significa que cuando vamos a asignar "Catástrofe", que no es necesario para crear nodos para C-A-T de nuevo. Ya existen. 

¿Qué es este sitio? Esta es la condición en la que C era barra invertida n, donde c es una nueva línea. Esto significa que tenemos éxito completado una palabra. Ahora, ¿qué es lo que queremos hacer cuando completado con éxito una palabra? Vamos a utilizar este campo la palabra dentro de nuestro nodo estructura. Queremos establecer que en true. Así que indica que este nodo indica un éxito palabra, una palabra real. 

Ahora establezca que en true. Queremos restablecer nuestra cursor hasta el punto al comienzo del trie de nuevo. Y, por último, incrementar nuestro diccionario tamaño, ya que nos encontramos otra obra. Así que vamos a seguir haciendo eso, lectura de carácter por carácter, la construcción de nuevos nodos en nuestro trie y para cada palabra en el diccionario, hasta finalmente alcanzamos C! = EOF, en el que caso salimos de el archivo. 

Ahora hay dos casos bajo que podríamos haber golpeado EOF. La primera es si hubo un error leer el archivo. Así que si hubo un error, deberá hacer lo típico. Descargue todo, cerca archivo, vuelve falsa. Suponiendo que no era un error, que simplemente significa que realmente golpeó el final de el archivo, en cuyo caso, se cierra el presentar y devolver true ya que diccionario cargado correctamente en nuestra trie. 

Así que ahora vamos a ver cheque. En cuanto a la función de comprobación, vemos El registro de entrada se va a devolver un bool. Devuelve true si esta palabra que es que se pasa es en nuestra trie. Devuelve false en caso contrario. Entonces, ¿cómo determinar si esta palabra es en nuestra trie? 

Vemos aquí que, al igual que antes, vamos a usar el cursor para iterar a través de nuestro trie. Ahora aquí vamos a repetir lo largo de toda nuestra palabra. Así iteración en la palabra que estamos pasado, vamos a determinar la índice en la matriz los niños que corresponde a la palabra soporte I. Así que este va a ser exactamente como de carga, en la que si la palabra [i] es un apóstrofe, entonces queremos utilizar el índice "alfabeto" - 1. Debido a que se determinó que esa es donde vamos a almacenar apóstrofes. 

Else vamos a utilizar dos palabras más baja soporte I. Así que recuerda esa palabra puede tener la capitalización arbitraria. Y por lo que queremos asegurarnos de que estamos usando una versión en minúsculas de las cosas. Y luego restar de que 'a' a la vez de nuevo nos da la alfabético posición de ese carácter. Así que va a ser nuestro índice en la matriz de los niños. 

Y ahora si ese índice en los niños matriz es nulo, eso significa que ya no puede continuar la iteración bajar la trie. Si ese es el caso, esta palabra no puede posiblemente estar en nuestra Trie. Dado que si lo fuera, que lo haría significa no habría un camino a esa palabra. Y nunca se encontraría nulo. Así que encontrar nulo, volvemos falsa. La palabra no está en el diccionario. Si no fuera nulo, entonces estamos va a continuar la iteración. 

Así que vamos por ahí cursor para apuntar a esa particular nodo en ese índice. Nosotros seguimos haciendo que a lo largo la palabra completa, suponiendo nunca golpeamos nulo. Eso significa que hemos sido capaces de obtener a través de toda la palabra y encontrar un nodo en nuestro intento. Pero no hemos terminado todavía. 

No queremos simplemente devolver true. Queremos volver cursor> palabra. Dado que recordar una vez más, es "gato" no es en el diccionario, y "catástrofe" ¿Es, entonces tendremos éxito que obtenemos a través de la palabra "gato". Pero cursor palabra será falsa y no es cierto. Así que volvemos cursor palabra para indicar si este nodo es en realidad una palabra. Y eso es todo por cheque. 

Así que vamos a ver el tamaño. Así que el tamaño va a ser bastante fácil ya que, recuerda en la carga, estamos incrementando el tamaño del diccionario para cada palabra que nos encontramos. Así que el tamaño es sólo va a devolver el tamaño del diccionario. Y eso es todo. 

Así, por último, hemos descargar. Así que descarga, vamos a utilizar una función recursiva para hacer realidad todos parte del trabajo por nosotros. Así que nuestra función va a ser llamados descargador. ¿Qué está descargador vamos a hacer? Vemos aquí que descargador va a iterar sobre todos los niños en este nodo particular. Y si el nodo hijo no es null, entonces vamos a descargar el nodo secundario. 

Así que éste es tu caso de forma recursiva descargue todos nuestros niños. Una vez que estemos seguros de que todos nuestros niños se han descargado, entonces puede liberar a nosotros mismos, así descargar nosotros mismos. Esto funciona de forma recursiva descargar todo el trie. Y una vez hecho esto, sólo podemos devolver true. Unload no puede fallar. Sólo estamos liberando cosas. Así que una vez que hayamos terminado liberando todo, devolver true. Y eso es todo. Mi nombre es Rob. Y esto fue corrector ortográfico. 

[REPRODUCCIÓN DE MÚSICA]