>> ROB BOWDEN: Oi.
Estou Rob, e haxixe Vamos esta solução para fora.
Então, aqui vamos implementar uma tabela geral de hash.
Vemos que o nó struct do nosso Hash mesa vai ficar assim.
Por isso, vai ter uma palavra de char matriz de comprimento do tamanho 1.
Não se esqueça do 1 desde o máximo palavra no dicionário é de 45
caracteres e, em seguida, vamos precisa de um personagem extra para o
barra invertida 0.
>> E então a nossa tabela hash 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.
Então é isso que um nó se parece.
Agora, aqui é a declaração da nossa tabela de hash.
Vai ter 16.384 baldes, mas esse número não importa realmente.
E, finalmente, vamos ter o hashtable_size variável global, que
vai começar como 0, e é vai manter o controle de quantas palavras
estavam em nosso dicionário.
Tudo bem.
>> Então, vamos dar uma olhada em carga.
Então, 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 * estrelas dicionário, o qual é o dicionário
que deseja abrir.
Então essa é a primeira coisa vamos fazer.
Vamos fopen o dicionário para leitura, e nós vamos ter
ter certeza de que ele conseguiu isso, se ele retornou NULL, então nós não
abrir com sucesso o dicionário e 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
laço que vamos ver.
Portanto, manter looping, e agora nós estamos indo malloc para um único nó.
E, claro, precisamos de erro de verificação novamente para se mallocing não teve sucesso
e 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 palavra de entrada-> é o caractere tampão palavra de comprimento plus size
que vamos armazenar a palavra dentro
Então fscanf vai retornar 1, desde como ele era capaz de ler com sucesso um
palavra do arquivo.
>> Se qualquer um erro acontece ou chegarmos o fim do arquivo, ele não vai
retornar um caso em que se isso não acontecer retornar 1, estamos finalmente vai quebrar
fora deste loop while.
Assim, vemos que uma vez que temos com sucesso ler uma palavra em
entry-> palavra, então nós estamos indo para o hash essa 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 este de hash função 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, dá-lhe um
índice na tabela de hash.
Observe que estamos modding por num_buckets portanto, o valor hash retornado
na verdade, é um índice para a tabela hash e não indexa além do
limites da matriz.
>> Assim, dado que a função de hash, vamos hash a palavra que lemos
do dicionário e, em seguida, vamos usar que tem que inserir o
entrada na tabela de hash.
Agora, mistura hashtable é o atual lista ligada na tabela de hash, e
é muito possível que seja apenas NULL.
Queremos inserir a nossa entrada no início desta lista ligada, e assim por
vamos ter a nossa entrada atual apontam para que a tabela hash atualmente
pontos para e, em seguida, vamos para armazenar na tabela de hash em 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 na tabela de hash.
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 retorna algo não 1 a
que ponto se lembrar que nós precisamos entrada gratuita, por isso até aqui, nós malloced um
entrada e tentamos ler algo a partir do dicionário.
E nós não lido com sucesso algo do dicionário em que
caso, precisamos de libertar a entrada que nós nunca realmente colocar em tabela hash
e, finalmente, se quebrar.
>> Assim que sair, nós precisamos ver, bem, fizemos sair porque não
Foi um erro de leitura do arquivo, ou fizemos sair porque nós alcançamos
o fim do ficheiro?
Se houve um erro, então nós queremos return false porque a carga não
sucesso, e, no processo, nós queremos descarregar todas as palavras que lemos
e feche o arquivo de dicionário.
Assumindo que teve sucesso, então nós apenas ainda precisa fechar o dicionário
arquivo e, finalmente, retornar true desde nós carregou com êxito o
dicionário.
E é isso por carga.
>> Então agora verificar, dada uma tabela hash carregado, vai ficar assim.
Portanto, verifique, ele retorna um bool, que vai indicar se a
passou-in char * palavra, se o string passada-in está em nosso dicionário.
Então, se é no dicionário, se for na nossa tabela hash, vamos voltar
verdade, e se não é, vamos retornar false.
Dada esta palavra passou-in, estamos vai botar a palavra.
>> Agora, uma coisa importante a reconhecer é que em carga, sabíamos que todos
as palavras iam ser minúsculas, mas aqui, não tem tanta certeza.
Se dermos uma olhada em nossa função de hash, nossa função hash realmente
é lowercasing cada personagem da palavra.
Portanto, independentemente da capitalização de palavra, a nossa função hash vai
retornar o mesmo índice para qualquer que seja o capitalização é o que teria
retornado para uma completamente minúsculas versão da palavra.
Tudo bem.
>> Então, esse é o nosso índice.
É a tabela de hash para essa palavra.
Agora, este loop vai para mais de uma lista ligada
que estava naquele índice.
Então, observe que estamos inicializando entrada para apontar para esse índice.
Nós vamos continuar enquanto entrada faz não é igual NULL, e lembre-se que
atualizar o ponteiro na nossa lista ligada entrada é igual a entrada-> seguinte, assim que tem
nosso ponto de entrada atual para o item seguinte na lista ligada.
Tudo bem.
>> Assim, para cada entrada na lista ligada, vamos usar strcasecmp.
Não é strcmp porque mais uma vez, nós querem fazer as coisas caso insensível.
Então, nós usamos strcasecmp comparar a palavra que foi passado para esta função
contra a palavra que é nessa entrada.
Se retornar 0, que significa que houve uma partida, caso em que queremos
return true.
Encontramos com sucesso a palavra em nossa tabela de hash.
>> 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 tabela hash não continha esta palavra.
E é isso por cheque.
Tudo bem.
>> Então, vamos dar uma olhada no tamanho.
Agora, o tamanho vai ser muito simples lembre-se, uma vez em carga, para cada palavra
descobrimos que incrementado um mundial hashtable_size variável.
Assim, a função de tamanho é apenas vai retornar esse mundial
variável, e é isso.
>> Agora, finalmente, é preciso descarregar o dicionário uma vez que tudo é feito.
Então, como vamos fazer isso?
Aqui, nós estamos loop para todos baldes de nossa tabela de hash.
Portanto, há num_buckets baldes.
E para cada lista ligada em nosso de hash mesa, vamos varrer o
totalidade da lista ligada liberando cada elemento.
Agora, é preciso ter cuidado, então aqui nós tem uma variável temporária que é
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 desde uma vez que libertou-se o
memória torna-se inválido.
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.
Nós vamos fazer isso para todas as listas ligadas em tabela hash, e uma vez que estamos a fazer
com isso, temos completamente descarregada tabela hash, e estamos a fazer.
Portanto, é impossível que descarrega para sempre return false, e quando estiver pronto, nós
basta retornar verdadeiro.