>> COLUNA 1: Vamos dar 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 Word e um nó estrela Struct
Crianças entre parênteses alfabeto.
Então a primeira coisa que você pode estar se perguntando: por isso é de hash alfabeto definido como 27?
Bem, lembre-se que nós vamos precisar estar lidando com o apóstrofo, de modo
que vai ser um pouco de um especial caso ao longo deste programa.
>> OK, agora, lembre-se como um Trie realmente funciona.
Digamos que estamos indexando a palavra gatos, em seguida, a partir da raiz do nosso Trie,
vamos olhar para as Crianças array, e vamos olhar para o
índice que corresponde à letra C. Para que seria índice dois.
Assim, dado que, que nos dará um novo nó, e depois vamos
trabalhar a partir desse nó.
>> Assim, dado que nós, que estamos mais uma vez vai olhar para a matriz Crianças,
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
olhar para o índice que corresponde para T. E passar para esse nó,
finalmente, temos completamente olhou através do nosso gato palavra, e agora Bool
Palavra deve indicar se esta palavra dada é na verdade uma palavra.
>> Então, por que precisamos nesse caso especial?
Bem, e se a catástrofe palavra está no nosso dicionário, mas
a palavra gato não é?
Assim, em olhando para ver se a palavra gato é em nosso dicionário, vamos
olhar com sucesso através dos índices C-A-T e chegar a um nó, mas isso é
só porque catástrofe aconteceu criar nós no caminho de C-A-T todos
o caminho para o fim da palavra.
Então Bool Word é usado indicar se este local especial, na verdade,
indica uma palavra.
>> Tudo bem, então agora que sabemos o que é um Trie está indo olhar como, vamos olhar
na função de carga.
Assim carga vai retornar um Bool para saber se com sucesso ou
dicionário e, sem sucesso, carregado este vai ser o dicionário
que deseja carregar.
Então a primeira coisa que vamos fazer é abrir até que dicionário para a leitura.
Temos que ter certeza de que não falhou, por isso, se o dicionário não foi
aberto com sucesso, ele retornará Não, nesse caso, vamos
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, a raiz vai ser uma estrela 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, assim como Malloc, precisamos fazer Certifique-se que a alocação é realmente
bem sucedida.
Se este retornou nulo, então nós precisa fechar nosso dicionário
arquivo e retornar False.
Assim, supondo que a alocação foi bem sucedida, vamos usar um nó
estrelar Cursor para repetir através do nosso Trie.
Portanto, a nossa raiz nunca vai mudar, mas nós vamos usar para Cursor
realmente ir de nó em nó.
>> Tudo bem, então neste loop, estamos leitura através do arquivo de dicionário,
e nós estamos usando a fgetc.
Então fgetc vai pegar um único personagem a partir do arquivo.
Nós vamos continuar agarrando caracteres enquanto não atingem o
final do arquivo, por isso há dois casos que precisamos lidar.
O primeiro, quando o carácter não era um nova linha, por isso sabemos se era um novo
linha, então estamos prestes a passar para uma nova palavra.
Mas supondo que ele não era uma nova linha, em seguida, aqui, 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 operador ternário aqui, então vamos ler
isso como se o personagem lemos em foi um apóstrofo, então vamos
definir índice igual ao alfabeto menos 1, que será o índice de 26.
Outra coisa, se não fosse um apóstrofo, em seguida, vamos definir o índice
igual a c, menos um.
Então lembre-se de volta a partir de conjuntos p anteriores, c menos uma vai nos dar o
posição alfabética de c, por isso, se c é a letra A, esta vontade
dá-nos o índice zero.
Para a letra B, que daria us o índice 1, e assim por diante.
>> Então, isso nos dá o índice para a Crianças matriz que nós queremos.
Agora, se esse índice é actualmente nulo na a matriz Crianças, isso significa que
um nó não existe atualmente de esse caminho, por isso precisamos de atribuir um
nó para esse caminho.
Isso é o que fazemos aqui.
Então, vamos, mais uma vez, use o calloc função de modo que não temos
para zerar todos os ponteiros, e nós, de novo, precisa verificar se calloc
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 fosse nulo, 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, não precisa criar
nós para C-A-T novamente.
Eles já existem.
>> OK, então 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 isso como True, de modo que indica que este nó indica uma
palavra sucesso uma palavra real.
Agora, definir que para True.
Queremos redefinir a nossa cursor para o ponto para o início do Trie novamente.
E, finalmente, aumentar nosso dicionário tamanho desde que encontramos outra palavra.
>> Tudo bem, então vamos continuar fazendo que, lendo em caráter de
personagem, construção de novos nós na nossa Trie e para cada palavra na
dicionário, até que, finalmente, chegar c é igual a EOF, caso em que, se quebrar
fora do arquivo.
Agora, há dois casos em que poderíamos ter atingido EOF.
A primeira é se houve um erro a leitura do arquivo, por isso, se houve
um erro, o que precisamos fazer o típico descarregar tudo, fechar 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
carregados com sucesso o dicionário em nosso Trie.
>> Tudo bem, então agora vamos confira Cheque.
Olhando para a função de verificação, vemos Verifique que vai retornar um Bool.
Ele retorna True se esta palavra, que é sendo passado está em nosso Trie.
Ele retorna false caso contrário.
>> Então, como é que vamos determinar se esta palavra é em nossa Trie?
Vemos aqui que, como antes, vamos usar cursor para iterar
através do nosso Trie.
Agora, aqui, nós vamos fazer uma iteração ao longo de toda a nossa palavra.
Então iteração sobre a palavra que estamos passou, vamos determinar a
índice para a matriz Crianças que corresponde à palavra suporte i.
Então, isso vai parecer exatamente como Carga, onde se suporte palavra i é um
apóstrofo, então nós queremos usar o índice alfabeto menos 1 por julgarmos
que é para onde estamos indo para armazenar apóstrofo.
>> Else vamos usar tolower suporte palavra i.
Então lembre-se que a palavra pode ter arbitrária capitalização, e por isso
quer ter a certeza que estamos usando uma versão minúscula das coisas.
E, em seguida, subtrair que minúsculas ao, mais uma vez, dá-nos a
posição alfabética desse personagem.
Então isso vai ser o nosso índice na matriz 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 no nosso Trie, uma vez que se ele
foram, isso significaria que haveria uma caminho até essa palavra, e se fosse
nunca encontrar nulo.
Assim, encontrando nulo, voltamos False.
A palavra não está no dicionário.
Se não fosse nulo, então vamos continuar iterando, por isso estamos indo
para atualizar o nosso cursor para apontar para que determinado nó nesse índice.
>> Então, nós continuar fazendo isso ao longo a palavra inteira.
Assumindo que nunca bateu nulo, isso significa fomos capazes de passar por todo o
mundo e encontrar um nó na nossa Trie, mas não estamos completamente feito ainda.
Nós não queremos apenas retornar True.
Queremos voltar palavra erro cursor uma vez que, lembre-se, novamente, se gato não é
em nosso dicionário e catástrofe é, então vamos obter sucesso através de
o gato palavra, mas a palavra cursor 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 Size.
Então Tamanho vai ser muito fácil uma vez que, lembre-se de carga, estamos
incrementando tamanho do dicionário para cada palavra que encontramos.
Então Tamanho é só ir para retornar tamanho do dicionário, e é isso.
>> Tudo bem, então, por último, temos Unload.
Então Unload, vamos usar um função recursiva para realmente fazer tudo
do trabalho por nós, para a nossa função vai ser chamado Descarregador.
O que está Unloader vai fazer?
Vemos aqui que Unloader vai iterar sobre todas as crianças em
este nó particular, e se a criança nó não for nulo, então vamos
descarregar o nó filho.
>> Então, isso vai de forma recursiva descarregar todas as nossas crianças.
Uma vez que temos a certeza de que todos os nossos filhos tenham sido descarregadas, então nós
pode libertar-nos, por isso, descarregar a nós mesmos.
Então, isso vai recursivamente descarregar o todo Trie, e então uma vez que é
feito, podemos simplesmente retornar True.
Unload não pode falhar, estamos apenas liberando as coisas.
Assim, uma vez que estamos a fazer liberando tudo, retornar True.
E é isso.
Meu nome é Rob, e este foi [inaudível].