[Música tocando] 

ROB BOWDEN: Oi Estou Rob. E imos a solución para fóra. Entón, aquí imos aplicar unha táboa xeral. Vemos que o no struct do noso mesa se ve así. Por iso, vai ter unha palabra de char matriz de tamaño Lonxitude + 1. Non esqueza do + 1, xa que o máximo palabra no dicionario é de 45 caracteres. E entón nós imos ter un adicional caracteres para o cero, barra invertida. 

E entón a nosa hashtable 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. Aceptar. Entón é iso que un nodo se parece. 

Agora aquí é a declaración da nosa hashtable. Terá 16834 baldes. Pero ese número non importa realmente. E, finalmente, imos ter o hashtable tamaño variable global, que comezará como cero. E iso vai manterse ao tanto de como moitas palabras están no noso dicionario. 

Entón, imos dar un ollo a carga. 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 * dicionario, que é o dicionario que quere abrir. Así que esta é o primeiro imos facer. 

Estamos indo ao fopen dicionario para a lectura. E nós imos ter que facer seguro de que el conseguiu. Entón, se voltou NULL, entón nós non abrir con éxito 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 ciclo, que imos ver. Polo tanto, manter looping. 

E agora nós imos malloc un único nodo. E está claro que necesitamos ao aire prema aquí. Entón, se mallocing non tivo éxito, entón 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 recorda que a entrada> palabra é o carácter tapón palabra de tamaño Lenghth + 1 que nós estamos indo para almacenar a palabra dentro 

Entón fscanf vai voltar 1, sempre como era capaz de éxito ler unha palabra desde o ficheiro. Se algún erro ocorrer, ou nós chegar ao final do arquivo, non volverá 1. No caso de que el non retorna 1, estamos finalmente vai saír do ese loop while. Así, vemos que xa que temos correctamente ler unha palabra en entry> palabra, entón nós estamos indo a que 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 ese hash funcionar a partir da Internet. O único que ten que recoñecer é que iso leva un const char * palabra. Entón, el está tomando unha cadea como entrada, e volvendo un int non asinado como saída. Entón, iso é todo unha función hash é, é leva nunha entrada e dálle unha índice para a táboa hash. 

Teña en conta que estamos moding por num_buckets, de xeito que o valor devolto en realidade, é un índice para a táboa hash e non indexa ademais do límites da matriz. Así, dado que a función, imos hash a palabra que lemos a dicionario. E entón nós imos usar que hash para introducir o entrada na táboa hash. 

Hash Agora hashtable é o actual lista ligada na táboa. E é moi posible que é só NULL. Queremos introducir a nosa entrada no inicio desta lista encadeada. E así nós imos ter a nosa actual punto de entrada ao que o hashtable actualmente apunta. E entón nós estamos indo para almacenar, no hashtable no de 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 no hashtable. 

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 volveu algo non-1 en que punto lembrar que necesitamos entrada gratuíta. Entón aquí nós malloced unha entrada. E nós tratamos ler algo desde o dicionario. E nós non ler correctamente algo do dicionario, o caso en que necesitamos liberar a entrada que nós nunca realmente poñer no hashtable, e finalmente romper. 

Así que saír necesitamos ver, así, fixemos saír porque non Foi un erro de lectura do ficheiro? Ou será que nós saír, porque nós chegou ao fin do ficheiro? Se houbo un erro, entón queremos voltar false. Porque carga non tivo éxito. E no proceso, queremos descargar todas as palabras que lemos, e pechar o ficheiro de dicionario. 

Asumindo que tivo éxito, entón nós só aínda que pechar o dicionario ficheiro e, finalmente, volver certo, xa que cargou con éxito o dicionario. E iso por carga. Entón agora comprobar, dado un hashtable cargado, se ve así. Polo tanto, asegúrese de, el retorna un bool, que é vai indicar se o pasado en char * palabra, o pasado na secuencia está no noso dicionario. Entón, se é no dicionario, se é do noso hashtable, imos voltar true. E se non é, imos voltar false. 

Dada esta aprobada en palabra, estamos vai botar a palabra. Agora unha cousa importante a recoñecer é que na carga sabiamos que todo o palabras que imos estar en minúsculas. Pero aquí non ten tanta certeza. Se derme un ollo a nosa función de hash, nosa función hash realmente é máis baixa cobertura de cada personaxe da palabra. Polo tanto, con independencia da capitalización de palabra, a nosa función de hash é o retorno o mesmo índice por calquera que sexa o capitalización é, como el retorno a unha totalmente minúsculas versión da palabra. Todo ben. Ese é o noso índice é o Hashtable a esta palabra. 

Agora, este loop vai iterado sobre a 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! = NULL. E lembre que a actualización do punteiro na nosa entrada ligada list = entry> seguinte. Entón temos o noso punto de entrada cadea para o seguinte elemento da lista encadeada. 

Así, para cada entrada na lista ligada, imos usar strcasecmp. Non é SeqComp. Porque, unha vez máis, queremos facer as cousas caso insensible. Entón, usamos strcasecmp comparar a palabra que foi pasado a través desta función contra a palabra que é nesa entrada. Se volve cero, é dicir que houbo un partido, caso en que queremos return true. Atopamos con éxito a palabra na nosa hashtable. 

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 hashtable non contiña esta palabra. E iso é un cheque. 

Entón, imos dar un ollo ao tamaño. Agora o tamaño será moi sinxelo. Xa que lembrar en carga, para cada palabra atopamos, temos incrementado un mundial tamaño variable hashtable. Así, a función de tamaño é só ir para volver variable global. E é iso. 

Agora, por fin, hai que descargar o dicionario xa que todo está feito. Entón, como imos facelo? Aquí estamos loop sobre todo baldes de nosa mesa. Polo tanto, hai num_buckets baldes. E para cada lista ligada na nosa hashtable, imos varrer a totalidade da lista encadeada, liberando cada elemento. 

Agora, necesitamos ter coidado. Entón aquí temos unha variable temporal que ten de almacenar 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, pois, unha vez que xa liberou-o, a memoria se fai válida. 

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. Imos facelo para todos conectados listas na táboa hash. E xa que estamos a facer que, temos completamente descargada a hashtable, e estamos a facer. Polo tanto, é imposible para descargar para sempre voltar false. E cando estea listo, nós basta voltar certo. 

Imos dar a esta solución un intento. Entón, imos dar un ollo ao que o noso nó struct será semellante. Aquí vemos que imos ter un bool palabra e un nó struct * nenos Alfabeto soporte. Entón o primeiro que pode ser pregunta, por que é alfabeto ed axusta 27? Ben, lembre que nós imos ter estar lidando co apóstrofo. Entón iso vai ser un pouco de un caso especial durante todo este programa. 

Agora lembre-se como un trie realmente funciona. Digamos que estamos indexando a palabra "Gatos". A continuación, a partir da raíz de trie, imos ollar para os nenos array, e imos ollar para o índice que corresponde á letra C. Así que será indexado 2. Entón, xa que, que a vontade ofrécenos un novo nodo. E entón nós imos traballar a partir dese nodo. 

Así, dado que nós, que estamos unha vez máis vai mirar para a matriz fillos. E nós estamos indo ollar índice cero corresponden ao A o gato. Entón nós estamos indo a ir a este nodo, e dado que imos mirar para o final, é unha corresponde para T. E pasar a este nodo, finalmente, temos totalmente mirou a través da nosa palabra "gato". E agora bool palabra se quere indicar se esta palabra dada é en realidade unha palabra. 

Entón, por que necesitamos nese caso especial? Ben, o que a palabra "catástrofe" está no noso dicionario, pero o palabra "gato" non é? Así, e mirando a ver se a palabra "gato" está no noso dicionario, estamos vai mirar con éxito a través os índices de C-A-T na rexión do nodo. Pero isto é só porque catástrofe pasou para crear nós no camiño desde C-A-T, todo o camiño ata o fin da palabra. Entón bool palabra é usada para indicar se este lugar especial realmente indica unha palabra. 

Todo ben. Polo tanto, agora que sabemos o que é trie indo ollar como, imos ollar para o Cargando función. Así, a carga vai voltar un booleano para saber se correctamente ou sen éxito cargado no dicionario. E este será o dicionario que quere cargar. 

Entón o primeiro que estamos a facer é abrir ata que dicionario para a lectura. E nós temos que estar seguro de non falla. Polo tanto, se o dicionario non era aberto correctamente, el volverá nula, caso en que estamos Vai voltar false. Pero, supoñendo que correctamente abriu, entón podemos realmente ler a través do dicionario. 

Entón o primeiro que imos quero facer é que temos esta raíz variable global. Agora raíz será un nodo *. É o principio da nosa trie que estamos será iterado. Entón o primeiro que imos querer facer é reservar memoria para a nosa raíz. Teña en conta que estamos a usar a calloc función, a cal é basicamente o mesmo como a función malloc, agás que se garantido para voltar algo que é totalmente zerado. Entón, se usamos malloc, necesitariamos pasar por todos os punteiros na nosa no, e asegúrese de que son todos nulos. Entón calloc vai facelo por nós. 

Agora só como malloc, necesitamos facer Asegúrese de que a dotación era de feito exitosa. Se este regresou nulo, entón nós Debe pechar ou dicionario arquivo e voltar false. Así, supoñendo que a distribución se exitosa, imos usar un nodo * cursor percorrer o noso trie. Entón nosas raíces nunca vai cambiar, pero imos usar o cursor realmente ir de nó en nó. 

Polo tanto, neste loop for que estamos lendo a través do arquivo de dicionario. E nós estamos usando fgetc. Fgetc vai pegar un único personaxe a partir do ficheiro. Nós imos seguir agarrando caracteres mentres non acadan o final do arquivo. 

Hai dous casos que debemos tratar. A primeira, cando o carácter Non foi unha nova liña. Entón, nós sabemos si foi unha nova liña, a continuación, estamos a piques de pasar a unha nova palabra. Pero supoñendo que el non era unha nova liña, a continuación, aquí queremos descubrir a índice imos índice en na matriz nenos que nós miramos antes. 

Entón, como dixen antes, necesitamos caso especial o apóstrofo. Teña en conta que estamos a usar o ternário operador aquí. Entón, imos ler isto como, o personaxe que lemos na era apóstrofo, entón imos definir index = "alfabeto" -1, que será ser o índice 26. 

Outra cousa, se non fose un apóstrofo, non imos establecer o índice igual a c - a. Entón lembre-se de volta a partir anteriormente p-sets, c - unha vai dar o posición alfabética de C. Polo tanto, se C é a letra A, este será ofrécenos o índice cero. Para a letra B, que vai che dar us o índice 1, e así por diante. 

Entón, iso dános o índice para a variedade nenos que queremos. Agora, se ese contido é actualmente nulo na os nenos, o que significa que un nó Non existe actualmente dese camiño. Entón, necesitamos reservar un nodo a este camiño. Iso é o que imos facer aquí. 

Entón imos utilizar de novo o calloc función, de xeito que non ten por Restablecer todos os punteiros. E unha vez máis que comprobar calloc que non fallou. Se calloc deixou, entón necesitamos para descargar todo, pechar o noso dicionario, e voltar false. Así, supoñendo que non fallou, entón iso pode crear un novo fillo para nós. E, a continuación, iremos para aquela neno. Nosa cursor ha iterado abaixo para aquela neno. 

Agora, se iso non foi nula, para comezar, a continuación, o cursor pode simplemente iterado ata aquela neno sen realmente ter que reservar calquera cousa. Este é o caso en que pasou por primeira vez reservar a palabra "gato". E isto significa que cando imos para reservar "Catástrofe", que non precisa crear nós para C-A-T novo. Xa existen. 

Que é esa persoa? Esta é a condición na que c é barra invertida n, onde c é unha nova liña. Isto significa que temos correctamente completou unha palabra. Agora, o que queremos facer cando rematou con éxito unha palabra? Imos usar este campo palabra dentro do noso nodo struct. Queremos establecer que a verdade. Así que indica que este nodo indica un éxito palabra, unha palabra real. 

Agora estableza que a verdade. Queremos redefinir a nosa cursor ao punto para o inicio de trie novo. E, finalmente, aumentar o noso dicionario tamaño, xa que atopamos outro traballo. Entón, nós imos seguir facendo iso, a lectura en carácter por carácter, construción de novos nós na nosa trie e para cada palabra no dicionario, ata finalmente chegar a C! = fin de ficheiro no que caso, saír do arquivo. 

Agora, hai dous casos baixo que poderiamos atinxir EOF. O primeiro é se houbo un erro a lectura do ficheiro. Entón, se houbo un erro, nós que facer o típico. Descargar todo, preto o ficheiro, voltar false. Asumindo que non houbo un erro, que significa só que realmente bater o fin do o ficheiro, caso en que, imos pechar o arquivo e volver true, xa que dicionario cargado con éxito na nosa trie. 

Entón agora imos comprobar cheque. Mirando para a función de comprobación, vemos o cheque vai voltar un booleano. El retorna true se esta palabra, que é sendo pasado está no noso trie. El retorna false caso contrario. Entón, como determinar se esta palabra é na nosa trie? 

Vemos aquí que, como antes, imos usar cursor iterado a través da nosa trie. Agora, aquí imos facer unha iteración ao longo de toda a nosa palabra. Entón iteración sobre a palabra que estamos pasado imos determinar a índice para a matriz que os nenos corresponde á palabra soporte I. Polo tanto, este vai parecer exactamente como de carga, onde se palabra [i] é un apóstrofo, entón queremos usar index "alfabeto" - 1. Porque foi determinado que a referida é o lugar onde nós estamos indo para almacenar apóstrofos. 

Else imos usar dous inferiores palabra soporte I. Entón lembre que a palabra pode ten capitalización arbitraria. E por iso queremos estar seguro de que estamos usando unha versión minúscula das cousas. E, a continuación, restar de que 'a' para unha vez novo dar a alfabética posición dese personaxe. Entón iso vai ser o noso índice para a matriz de nenos. 

E agora, se este índice para os nenos matriz é nulo, isto significa que non pode seguir iteración abaixo a nosa trie. En tal caso, esta palabra non pode posiblemente estar na nosa trie. Sempre que fose, que sería quere dicir que habería un camiño abaixo para esa palabra. E nunca ía atopar nulo. Así, atopando nulo, nós voltar false. A palabra non está no dicionario. Se non fose nulo, entón estamos seguirá a iteración. 

Entón, imos por aí cursor salientar que a especial nó nese índice. Nós continuar facendo iso ao longo a palabra, asumindo nunca bateu nulo. Isto significa que fomos capaces de pasar toda a palabra e atopar un nó na nosa intento. Pero nós non estamos totalmente feito aínda. 

Non queremos só retornar true. Queremos volver cursor> palabra. Desde lembrar unha vez máis, é o "gato" non é na nosa dicionario, e "catástrofe" é, entón imos correctamente obtemos a través da palabra "gato". Pero cursor palabra será falso e non é verdade. Entón volvemos palabra cursor indicar se este nodo é realmente unha palabra. E iso por cheque. 

Entón, imos comprobar o tamaño. Así, o tamaño será moi fácil xa que, lembre-se da carga, somos incrementando tamaño do dicionario para cada palabra que atopamos. Así, o tamaño é só ir a voltar tamaño do dicionario. E é iso. 

Entón, por fin, temos descargar. Entón, descargar, imos utilizar un función recursiva para realmente facer todo do traballo para nós. Polo tanto, a nosa función vai ser chamado descarga. O que está Descarregador vai facer? Vemos aquí que Descarregador vai iterado sobre todos os nenos en este nodo particular. E se o nodo fillo non é nulo, entón imos descargar o no fillo. 

Polo tanto, este é vostede recursivamente descargar todos os nosos fillos. Unha vez que temos a certeza de que todos os nosos fillos fosen descargados, entón nós pode liberar-nos, por iso, nós descargar. Isto ha traballar de forma recursiva descargar toda a trie. E, a continuación, unha vez que está feito, podemos simplemente voltar true. Unload non pode fallar. Nós só estamos liberando cousas. Así, unha vez que estamos a facer liberando todo, volver true. E é iso. O meu nome é Rob. E esta foi Speller. 

[Música tocando]