[Música tocando] ROB BOWDEN: Oi. Estou Rob. E vamos a solução para fora. Então, aqui vamos implementar uma tabela geral. Vemos que o nó struct do nosso mesa vai ficar assim. Por isso, vai ter uma palavra de char matriz de tamanho COMPRIMENTO + 1. Não se esqueça do + 1, já que o máximo palavra no dicionário é de 45 caracteres. E então nós vamos precisar de um adicional caracteres para o zero, barra invertida. E então nossa hashtable em cada balde vai armazenar uma lista ligada de nós. Nós não estamos fazendo linear sondagem aqui. E assim, a fim de vincular a próxima elemento no balde, precisamos de um struct node * seguinte. OK. Então é isso que um nó se parece. Agora aqui é a declaração da nossa hashtable. Vai ter 16834 baldes. Mas esse número não importa realmente. E, finalmente, vamos ter o hashtable tamanho variável global, que vai começar como zero. E isso vai se manter a par de como muitas palavras estão em nosso dicionário. Então, vamos dar uma olhada em carga. Observe que a carga, ele retorna um bool. Você retorna verdadeiro se fosse com sucesso carregado e false caso contrário. E leva um const char * dicionário, que é o dicionário que deseja abrir. Então essa é a primeira coisa vamos fazer. Nós estamos indo para o fopen dicionário para a leitura. E nós vamos ter que fazer certeza de que ele conseguiu. Então, se ele retornou NULL, então nós não abrir com êxito o dicionário. E nós precisamos retornar false. Mas supondo que ele fez com sucesso aberta, então nós queremos ler a dicionário. Portanto, manter looping até que encontremos algum motivo para romper esse ciclo, que vamos ver. Portanto, manter looping. E agora nós vamos malloc um único nó. E é claro que precisamos para o ar clique aqui. Então, se mallocing não teve sucesso, então queremos descarregar qualquer nó que aconteceu com malloc antes, fechar o dicionário e retornar false. Mas ignorar que, assumindo que conseguiu, então nós queremos usar fscanf para ler uma única palavra do nosso dicionário para o nosso nó. Então lembre-se que a entrada> palavra é o caractere tampão palavra de tamanho Lenghth + 1 que nós estamos indo para armazenar a palavra dentro Então fscanf vai retornar 1, contanto como era capaz de sucesso ler uma palavra a partir do arquivo. Se algum erro acontecer, ou nós chegar ao final do arquivo, ele não retornará 1. No caso em que ele não retorna 1, estamos finalmente vai sair do esse loop while. Assim, vemos que uma vez que temos com sucesso ler uma palavra em entry> palavra, então nós estamos indo para que palavra usando nossa função hash. Vamos dar uma olhada a função hash. Então, você realmente não precisa para entender isso. E, na verdade, nós apenas puxou esse hash funcionar a partir da internet. A única coisa que você precisa reconhecer é que isso leva um const char * palavra. Então, ele está tomando uma string como entrada, e retornando um int não assinado como saída. Então, isso é tudo uma função hash é, é leva em uma entrada e dá-lhe uma índice para a tabela hash. Observe que estamos moding por num_buckets, de modo que o valor devolvido na verdade, é um índice para a tabela hash e não indexa além do limites da matriz. Assim, dado que a função, vamos hash a palavra que lemos a dicionário. E então nós vamos usar que hash para inserir o entrada na tabela hash. Hash Agora hashtable é o atual lista ligada na tabela. E é muito possível que é apenas NULL. Queremos inserir a nossa entrada no início desta lista encadeada. E assim nós vamos ter a nossa atual ponto de entrada para o que o hashtable atualmente aponta. E então nós estamos indo para armazenar, no hashtable no de hash, a entrada atual. Então, essas duas linhas inserir com sucesso a entrada no começo da lista ligada em que o índice de no hashtable. Uma vez que estamos a fazer com que, nós sabemos que encontramos uma outra palavra no dicionário, e incrementar novamente. Então, nós continuar fazendo isso até que fscanf finalmente voltou algo não-1 em que ponto se lembrar que precisamos entrada gratuita. Então aqui nós malloced uma entrada. E nós tentamos ler algo a partir do dicionário. E nós não lido com sucesso algo do dicionário, no caso em que precisamos de libertar a entrada que nós nunca realmente colocar no hashtable, e finalmente quebrar. Assim que sair nós precisamos ver, bem, fizemos sair porque não Foi um erro de leitura do arquivo? Ou será que nós sair, porque nós chegou ao fim do arquivo? Se houve um erro, então queremos retornar false. Porque carga não teve êxito. E no processo, queremos descarregar todas as palavras que lemos, e fechar o arquivo de dicionário. Assumindo que teve sucesso, então nós apenas ainda precisa fechar o dicionário arquivo e, finalmente, retornar verdadeiro, uma vez que carregou com êxito o dicionário. E é isso por carga. Então agora verificar, dado um hashtable carregado, vai ficar assim. Portanto, verifique, ele retorna um bool, que é vai indicar se o passado em char * palavra, se o passado na seqüência está no nosso dicionário. Então, se é no dicionário, se é do nosso hashtable, vamos retornar true. E se não for, vamos retornar false. Dada esta aprovada em palavra, estamos vai botar a palavra. Agora uma coisa importante a reconhecer é que na carga sabíamos que toda a palavras que vamos estar em minúsculas. Mas aqui não tem tanta certeza. Se dermos uma olhada em nossa função de hash, nossa função hash realmente é mais baixa cobertura de cada personagem da palavra. Portanto, independentemente da capitalização de palavra, a nossa função de hash é o retorno o mesmo índice por qualquer que seja o capitalização é, como ele teria retornado para uma completamente minúsculas versão da palavra. Tudo bem. Esse é o nosso índice é no Hashtable para esta palavra. Agora, este loop vai iterar sobre a lista ligada que estava naquele índice. Então, observe que estamos inicializando entrada para apontar para esse índice. Nós vamos continuar enquanto entrada! = NULL. E lembre-se que a atualização do ponteiro em nossa entrada ligada list = entry> seguinte. Então temos o nosso ponto de entrada corrente para o próximo item na lista encadeada. Assim, para cada entrada na lista ligada, vamos usar strcasecmp. Não é SeqComp. Porque, mais uma vez, nós queremos fazer as coisas caso insensível. Então, nós usamos strcasecmp comparar a palavra que foi passado através desta função contra a palavra que é nessa entrada. Se ela retorna zero, que significa que houve uma partida, caso em que queremos return true. Encontramos com sucesso a palavra em nossa hashtable. Se não foi um jogo, então estamos indo para repetir novamente e olhar para o próxima entrada. E nós vamos continuar looping enquanto não são entradas nesta lista ligada. O que acontece se quebrar fora deste loop for? Isso significa que não encontrou uma entrada que combinava esta palavra, caso em que retornamos false para indicar que o nosso hashtable não continha esta palavra. E isso é um cheque. Então, vamos dar uma olhada no tamanho. Agora o tamanho vai ser muito simples. Uma vez que se lembrar em carga, para cada palavra encontramos, temos incrementado um mundial tamanho variável hashtable. Assim, a função de tamanho é só ir para voltar variável global. E é isso. Agora, finalmente, é preciso descarregar o dicionário uma vez que tudo é feito. Então, como vamos fazer isso? Aqui estamos loop sobre todos os baldes de nossa mesa. Portanto, há num_buckets baldes. E para cada lista ligada em nosso hashtable, vamos varrer a totalidade da lista encadeada, liberando cada elemento. Agora, precisamos ter cuidado. Então aqui nós temos uma variável temporária que tem de armazenar o ponteiro para o próximo elemento na lista encadeada. E então nós estamos indo para livre o elemento atual. Precisamos ter certeza de que fazemos isso desde que não pode apenas liberar o elemento atual e tente acessar o próximo ponteiro, pois, uma vez que já libertou-o, a memória se torna inválida. Então, precisamos manter em torno de um ponteiro para o próximo elemento, então podemos liberar o elemento atual, e então nós podemos atualizar nosso elemento atual para apontar para o próximo elemento. Vamos loop while há elementos nesta lista encadeada. Vamos fazer isso para todos ligados listas na tabela hash. E uma vez que estamos a fazer com que, nós temos completamente descarregada a hashtable, e estamos a fazer. Portanto, é impossível para descarregar para sempre retornar false. E quando estiver pronto, nós basta retornar verdadeiro. Vamos dar a esta solução uma tentativa. Então, vamos dar uma olhada no que o nosso nó struct será semelhante. Aqui vemos que vamos ter um bool palavra e um nó struct * crianças ALFABETO suporte. Então a primeira coisa que você pode ser perguntando, por que é ALFABETO ed definido como 27? Bem, lembre-se que nós vamos precisar estar lidando com o apóstrofo. Então isso vai ser um pouco de um caso especial durante todo este programa. Agora lembre-se como um trie realmente funciona. Digamos que estamos indexando a palavra "gatos". Em seguida, a partir da raiz de trie, vamos olhar para as crianças array, e vamos olhar para o índice que corresponde à letra C. Assim que será indexado 2. Então, uma vez que, que a vontade dá-nos um novo nó. E então nós vamos trabalhar a partir desse nó. Assim, dado que nós, que estamos mais uma vez vai olhar para a matriz filhos. E nós estamos indo olhar índice zero corresponder ao A no gato. Então nós estamos indo para ir para esse nó, e dado que nós vamos de olhar para o final, é uma corresponde para T. E passar para esse nó, finalmente, temos completamente olhou através da nossa palavra "gato". E agora bool palavra é suposto indicar se esta palavra dada é na verdade uma palavra. Então, por que precisamos nesse caso especial? Bem, o que a palavra "catástrofe" está no nosso dicionário, mas o palavra "gato" não é? Assim, e olhando para ver se a palavra "gato" está no nosso dicionário, estamos vai olhar com sucesso através os índices de C-A-T na região do nó. Mas isso é só porque catástrofe aconteceu para criar nós no caminho a partir de C-A-T, todo o caminho até o fim da palavra. Então bool palavra é usada para indicar se este local especial realmente indica uma palavra. Tudo bem. Portanto, agora que sabemos o que é trie indo olhar como, vamos olhar para o carregar função. Assim, a carga vai retornar um booleano para saber se com sucesso ou sem sucesso carregado no dicionário. E este vai ser o dicionário que deseja carregar. Então a primeira coisa que estamos a fazer é abrir até que dicionário para a leitura. E nós temos que ter certeza de nós não falhar. Portanto, se o dicionário não era aberto com sucesso, ele retornará nula, caso em que estamos vai retornar false. Mas, supondo que com sucesso abriu, então podemos realmente ler através do dicionário. Então a primeira coisa que vamos quero fazer é que temos esta raiz variável global. Agora raiz vai ser um nó *. É o topo da nossa trie que estamos vai ser iterar. Então a primeira coisa que vamos querer fazer é alocar memória para a nossa raiz. Observe que estamos usando a calloc função, a qual é basicamente a mesma como a função malloc, exceto que é garantido para retornar algo que é completamente zerado. Então, se nós usamos malloc, precisaríamos passar por todos os ponteiros em nossa nó, e certifique-se de que eles são todos nulos. Então calloc vai fazer isso por nós. Agora apenas como malloc, precisamos fazer Certifique-se que a dotação era de fato bem sucedida. Se este retornou nulo, então nós precisa fechar ou dicionário arquivo e retornar false. Assim, supondo que a alocação foi bem sucedida, vamos usar um nó * cursor para percorrer o nosso trie. Então nossas raízes nunca vai mudar, mas vamos usar o cursor para realmente ir de nó em nó. Portanto, neste loop for que estamos lendo através do arquivo de dicionário. E nós estamos usando fgetc. Fgetc vai pegar um único personagem a partir do arquivo. Nós vamos continuar agarrando caracteres enquanto não atingem o final do arquivo. Há dois casos que temos de lidar. O primeiro, quando o carácter Não foi uma nova linha. Então, nós sabemos se foi uma nova linha, em seguida, estamos prestes a passar para uma nova palavra. Mas supondo que ele não era uma nova linha, em seguida, aqui nós queremos descobrir a índice vamos índice em na matriz crianças que nós olhamos antes. Então, como eu disse antes, nós precisamos caso especial o apóstrofo. Observe que estamos usando o ternário operador aqui. Então, vamos ler isso como, se o personagem que lemos na era apóstrofo, então vamos definir index = "ALFABETO" -1, que será ser o índice 26. Outra coisa, se não fosse um apóstrofo, não vamos definir o índice igual a c - a. Então lembre-se de volta a partir anteriormente p-sets, c - uma vai nos dar o posição alfabética de C. Portanto, se C é a letra A, este será dá-nos o índice zero. Para a letra B, ele vai te dar us o índice 1, e assim por diante. Então, isso nos dá o índice para a variedade crianças que nós queremos. Agora, se esse índice é actualmente nulo na as crianças, o que significa que um nó não existe actualmente desse caminho. Então, precisamos alocar um nó para esse caminho. Isso é o que nós vamos fazer aqui. Então vamos usar novamente o calloc função, de modo que não temos a zerar todos os ponteiros. E mais uma vez precisa verificar calloc que não falhou. Se calloc deixou, então precisamos para descarregar tudo, fechar o nosso dicionário, e retornar false. Assim, supondo que ele não falhou, então isso irá criar um novo filho para nós. E, em seguida, iremos para aquela criança. Nossa cursor irá iterar para baixo para aquela criança. Agora, se isso não foi nula, para começar, em seguida, o cursor pode simplesmente iterar até aquela criança sem realmente ter de alocar qualquer coisa. Este é o caso em que aconteceu pela primeira vez alocar a palavra "gato". E isso significa que quando vamos para alocar "Catástrofe", que não precisa criar nós para C-A-T novamente. Eles já existem. O que é essa pessoa? Esta é a condição em que c é barra invertida n, onde c é uma nova linha. Isso significa que nós temos com sucesso completou uma palavra. Agora, o que nós queremos fazer quando concluiu com êxito uma palavra? Vamos usar este campo palavra dentro do nosso nó struct. Queremos definir que a verdade. Assim que indica que este nó indica um sucesso palavra, uma palavra real. Agora defina que a verdade. Queremos redefinir a nossa cursor para o ponto para o início de trie novamente. E, finalmente, aumentar nosso dicionário tamanho, uma vez que encontramos um outro trabalho. Então, nós vamos continuar fazendo isso, a leitura em caractere por caractere, construção de novos nós na nossa trie e para cada palavra no dicionário, até finalmente chegar a C! = EOF, em que caso, sair do arquivo. Agora, existem dois casos sob que poderíamos ter atingido EOF. A primeira é se houve um erro a leitura do arquivo. Então, se houve um erro, nós precisa fazer o típico. Descarregar tudo, perto o arquivo, retornar false. Assumindo que não houve um erro, que significa apenas que nós realmente bater o fim do o arquivo, caso em que, vamos fechar o arquivo e retornar true, uma vez que dicionário carregado com êxito em nosso trie. Então agora vamos verificar cheque. Olhando para a função de verificação, vemos o cheque vai retornar um booleano. Ele retorna true se esta palavra, que é sendo passado está em nosso trie. Ele retorna false caso contrário. Então, como você determinar se esta palavra é em nossa trie? Vemos aqui que, como antes, vamos usar cursor para iterar através do nosso trie. Agora, aqui vamos fazer uma iteração ao longo de toda a nossa palavra. Então iteração sobre a palavra que estamos passado, vamos determinar a índice para a matriz que as crianças corresponde à palavra suporte I. Portanto, este vai parecer exatamente como de carga, onde se palavra [i] é um apóstrofo, então nós queremos usar index "alfabeto" - 1. Porque foi determinado que a referida é o lugar onde nós estamos indo para armazenar apóstrofos. Else vamos usar dois inferiores palavra suporte I. Então lembre-se que a palavra pode tem capitalização arbitrária. E por isso queremos ter certeza de que estamos usando uma versão minúscula das coisas. E, em seguida, subtrair de que 'a' para uma vez novamente nos dar a alfabética posição desse personagem. Então isso vai ser o nosso índice para a matriz de crianças. E agora, se esse índice para as crianças matriz é nulo, isso significa que não pode mais continuar a iteração para baixo a nossa trie. Se for esse o caso, esta palavra não pode possivelmente estar na nossa trie. Desde que fosse, que seria significa que haveria um caminho para baixo para essa palavra. E você nunca iria encontrar nulo. Assim, encontrando nulo, nós retornar false. A palavra não está no dicionário. Se não fosse nulo, então estamos vai continuar a iteração. Então, vamos lá fora cursor de salientar que a especial nó nesse índice. Nós continuar fazendo isso ao longo a palavra inteira, assumindo nós nunca bateu nulo. Isso significa que fomos capazes de passar toda a palavra e encontrar um nó na nossa tentativa. Mas nós não estamos completamente feito ainda. Nós não queremos apenas retornar true. Queremos voltar cursor> palavra. Desde lembrar mais uma vez, é o "gato" não é em nosso dicionário, e "catástrofe" é, então vamos com sucesso obtemos através da palavra "gato". Mas cursor palavra será falso e não é verdade. Então voltamos palavra cursor para indicar se este nó é realmente uma palavra. E é isso por cheque. Então, vamos verificar o tamanho. Assim, o tamanho vai ser muito fácil uma vez que, lembre-se da carga, nós somos incrementando tamanho do dicionário para cada palavra que encontramos. Assim, o tamanho é só ir a retornar tamanho do dicionário. E é isso. Então, por fim, temos descarregar. Então, descarregar, vamos usar um função recursiva para realmente fazer tudo do trabalho para nós. Portanto, a nossa função vai ser chamado de descarga. O que está descarregador vai fazer? Vemos aqui que descarregador vai iterar sobre todas as crianças em este nó particular. E se o nó filho não é nulo, então vamos descarregar o nó filho. Portanto, este é você recursivamente descarregar todos os nossos filhos. Uma vez que temos a certeza de que todos os nossos filhos tenham sido descarregadas, então nós pode libertar-nos, por isso, nós descarregar. Isto irá trabalhar de forma recursiva descarregar toda a trie. E, em seguida, uma vez que é feito, podemos simplesmente retornar true. Unload não pode falhar. Nós apenas estamos liberando coisas. Assim, uma vez que estamos a fazer liberando tudo, retornar true. E é isso. Meu nome é Rob. E esta foi speller. [Música tocando]