[Powered by Google Translate] [Passo a passo - Conjunto de Problemas 5] [Zamyla Chan - Harvard University] [Esta é CS50. - CS50.TV] 

Tudo bem. Olá, todos, e bem vindo ao Passo a passo 5. 

Pset5 é Erros de ortografia, em que vamos estar fazendo um corretor ortográfico. Corretores ortográficos são extremamente importantes. Isso já aconteceu com você? Você trabalha muito, muito acumulam em um papel para um confronto e depois ainda acabar recebendo um rade brilho muito parecido com um D ou um = D e tudo porque você é o spoiler em liverwurst a palavra baleia de largura. Sim, revisão suas pimentas é uma questão de, a impotência máxima. Este é um problema que afeta viris, os alunos viris. Me disseram uma vez pelo meu torturador grau sith que eu nunca iria entrar em um bom colega. E isso é tudo que eu sempre quis, isso é tudo que qualquer criança quer na minha idade, apenas para entrar em um bom colega. E não só qualquer colega. Não. Eu queria ir para um colega do Marfim Legal. Então, se eu não melhorar, embora seriam os meus sonhos de ir para Harvard, Jale, a prisão ou - você sabe, na prisão, Nova Jersey. Então, eu próprio tenho um corretor ortográfico. Esse é um trecho pequeno de um dos meus artistas favoritos palavra falada, Taylor Mali. De qualquer forma, como ele diz, a importância de ter um corretor ortográfico é muito importante. 

Então, bem-vindo ao Passo a passo 5, em que vamos estar falando sobre pset5: Erros de ortografia, em que nós estaremos fazendo o nosso próprio corretor ortográfico. A caixa de ferramentas para esta semana, o código de distribuição, vai ser importante olhar para só para entender as diferentes funções que seu dicionário vai ter. Na verdade, estamos indo para ter vários arquivos. C que, juntos, fazem a nossa pset. E assim olhando através de diferentes aspectos, mesmo que não estamos realmente edição um dos arquivos, speller.c, sabendo como ele funciona com relação a dictionary.c, que iremos escrever, vai ser muito importante. A especificação pset também contém uma série de informações úteis em termos de coisas que você pode assumir, regras e coisas assim, isso não deixe de ler a especificação pset cuidadosamente para dicas. E quando estiver em dúvida de uma regra ou algo assim, então sempre consultar a especificação pset ou discutir. Este pset vai dependem fortemente de ponteiros, por isso queremos ter certeza de que entendemos a diferença entre estrelas adicionar na frente do nome do ponteiro e ampersands, como para libertá-los, etc Então, ser um mestre de ponteiros vai ser muito útil neste conjunto de problemas. Nós vamos olhar para listas ligadas um pouco mais, onde temos elementos que chamamos de nós que possuem tanto um valor, bem como um apontador para o próximo nó, e assim, essencialmente, ligando elementos diferentes um após o outro. Existem algumas opções diferentes de implementar seu dicionário real. Nós vamos olhar para dois métodos principais, o que é tabelas de hash e então tenta. Em ambos os, envolvem algum tipo de noção de uma lista ligada onde têm elementos ligados um ao outro. E assim vamos olhar sobre como você pode ser capaz de operar em torno de listas ligadas, criá-las, navegar em termos de como, por exemplo, inserir um nó em que ou livre de todos os nós, bem. Em termos de nós libertadora, que é realmente importante que sempre que a memória malloc, depois nos libertar. Então, nós queremos ter certeza de que nenhum ponteiro vai unfreed, que não temos quaisquer vazamentos de memória. Nós vamos apresentar uma ferramenta chamada Valgrind que executa o programa e verifica se toda a memória que você alocou é então liberado. Seu pset só é completa quando ele funciona e tem a funcionalidade completa, mas também, Valgrind lhe diz que você não tenha encontrado qualquer vazamento de memória. Finalmente, para este pset, eu realmente quero enfatizar - Quero dizer, como de costume, eu sou definitivamente um defensor do uso de papel e caneta para seus conjuntos de problemas, mas para este, eu acho que caneta e papel vai ser especialmente importante quando você quer ser desenho setas para as coisas e entender como as coisas funcionam. Então, definitivamente tentar usar caneta e papel para desenhar as coisas antes que você comece a codificação porque ele poderia ficar um pouco confuso. 

Primeiro, vamos entrar em listas ligadas um pouco. Listas ligadas consistem de nós, onde cada nó tem um valor associado a ela, , bem como um apontador para o próximo nó após ele. Um par de coisas importantes com as listas ligadas são de que precisamos nos lembrar onde o nosso primeiro nó é, em seguida, uma vez que sabemos que o primeiro nó é, Dessa forma, podemos acessar o nó que os primeiros pontos de nó para e, em seguida, a outra depois disso e um depois disso. E então o último elemento na sua lista ligada é ponteiro que nó sempre vai apontar para NULL. Quando um nó pontos para NULL, então você sabe que você chegou ao final da lista, que esse nó é o último, que não há nada depois disso. Aqui neste esquema, você vê que as setas são os ponteiros, e a secção de azul é onde o valor é armazenado, e, em seguida, a caixa vermelha com o ponteiro para ele é ponteiro do nó apontando para o próximo nó após ele. E assim que você vê aqui, o nó D iria apontar para NULL porque é o último elemento da lista. 

Vamos ver como podemos definir uma estrutura para um nó. E já que queremos ter vários nós, isso vai se tornar um typedef struct em que nós vamos ter várias instâncias diferentes de nós. E, assim, defini-lo como um novo tipo de dados. Aqui, temos um nó typedef struct. Neste exemplo, estamos a lidar com nós inteiros, por isso temos um valor inteiro chamado e depois temos outro ponteiro, e, neste caso, é um ponteiro para um nó, por isso temos um nó struct * chamada seguinte. E então nós estamos chamando este nó coisa toda. Certifique-se de que você siga esta sintaxe. Observe que o nó está realmente acima referenciado, bem como abaixo das chaves. Então, para manter o controle de onde o meu primeiro nó está na lista vinculada, então ter um ponteiro nó chamado cabeça, e eu malloc espaço suficiente para o tamanho de um nó. Observe, no entanto, que a cabeça é realmente um ponteiro nó em oposição a um nó propriamente dito. Assim, a cabeça, na verdade, não contém qualquer valor, ele apenas aponta para o que o primeiro nó na minha lista ligada é. 

Para ter uma noção melhor de listas ligadas, porque é muito importante para acompanhar a certeza que você manter a cadeia, Eu gosto de pensar nisso como pessoas em uma linha de mãos dadas, onde cada pessoa está de mãos dadas com o próximo. Você não pode ver neste desenho, mas, basicamente, eles estão apontando para a próxima pessoa que está na sua cadeia. E por isso, se você quiser percorrer uma lista ligada onde essas pessoas - imagine todas essas pessoas têm valores associados a eles e também apontar para a próxima pessoa na linha - se você quiser percorrer a lista ligada, por exemplo, para editar os valores ou procurar por um valor ou algo assim, então você vai querer ter um ponteiro para a pessoa específica. Então, nós vamos ter um ponteiro de dados nó do tipo. Para este exemplo, vamos chamá-lo cursor. Outra forma comum de nomear este seria iterador ou algo parecido porque está interagindo sobre e realmente mover o nó que está apontando. Isso aqui vai ser o nosso cursor. Nosso primeiro cursor apontar para o primeiro elemento em nossa lista. E então o que nós queremos fazer é que seria basicamente ser continuar o cursor, movendo-o de lado a lado. Neste caso, queremos movê-lo para o próximo elemento da lista. Com matrizes, o que nós fazemos é apenas diria que aumentar o índice de 1. Neste caso, o que precisamos fazer é realmente encontrar o que esta pessoa pessoa atual está apontando, e que vai ser o próximo valor. Então, se o cursor é apenas um ponteiro nó, então o que nós queremos fazer é que nós queremos chegar ao valor que o cursor está apontando. Queremos chegar a esse nó e, em seguida, uma vez que estamos naquele nó, encontrar onde ele está apontando. Para chegar ao nó real que o cursor está apontando, Normalmente indicam-lo (cursor *). Que lhe daria o nó real que o cursor está apontando. E depois disso, o que nós queremos fazer é que nós queremos para acessar qualquer que seja o valor próximo do nó é. Para fazer isso, para acessar os valores dentro da estrutura, temos o operador ponto. Então seria (cursor *). Seguinte. Mas isso é um pouco confuso em termos de ter os suportes em torno do cursor *, e assim vamos substituir essa declaração inteira com cursor->. Este é um traço e um sinal maior do que, por isso tornando uma seta. cursor-> seguinte. Que realmente vai te dar o nó que os pontos cursor. Esse valor é do próximo. Então, ao invés de ter a estrela eo ponto, você está substituindo isso com uma seta. Tenha muito cuidado para se certificar de que você tentar usar essa sintaxe. 

Agora que temos o nosso cursor, se quiser acessar o valor, antes, tivemos cursor-> seguinte, mas para acessar o valor no nó que o cursor está apontando, nós simplesmente dizer node>-valor. De lá, ele é do tipo de dados o que nós definimos os valores e os nós a serem. Se ele é um nó int e cursor-> valor é apenas vai ser um inteiro. Então, podemos fazer operações em que, verificar igualdades, atribuir valores diferentes, etc Então o que você quer fazer, se você deseja mover o cursor para a próxima pessoa, você realmente mudar o valor do cursor. Desde cursor é um ponteiro nó, você alterar o endereço do ponteiro real para o endereço do próximo nó na sua lista. Este é apenas um código, onde você pode interagir. Onde eu tenho o comentário fazer alguma coisa, que é onde você está indo provavelmente para acessar o valor ou fazer alguma coisa a ver com esse nó específico. Para iniciá-lo fora, eu digo que o meu cursor inicialmente vai para apontar para o primeiro elemento na lista encadeada. E assim lá na frente, eu defini-lo como o chefe do nó. 

Como mencionei antes, libertando é realmente importante. Você quer ter certeza de que você liberar todos os elementos da lista uma vez que você terminou com ele. Quando você não precisa fazer referência a qualquer desses ponteiros mais, você quer ter certeza de que você liberar todos os ponteiros. Mas você quer ter muito cuidado aqui em que você quer evitar qualquer vazamento de memória. Se uma pessoa livre prematuramente, depois de todos os ponteiros que que os pontos de nó para vão ser perdidos. Voltando ao exemplo pessoa para torná-lo um pouco mais altas apostas, vamos ter essas pessoas, só que neste caso eles estão pairando sobre um lago com um monstro. Nós queremos ter certeza de que sempre que liberar, não perdemos e deixar de ir todos os nós antes que nós realmente os libertou. Por exemplo, se você fosse simplesmente ligar gratuitamente sobre esse cara aqui, então, ele seria libertado, mas depois todos esses caras, então, ser perdido e que iria adormecer e cair. Então, nós queremos ter certeza de que em vez disso, nós queremos manter um vínculo com o resto. Nossa cabeça ponteiro, que aponta para o primeiro elemento da lista. É como uma espécie de corda de ancoragem primeira pessoa. O que você pode querer fazer quando você liberar uma lista é ter - Se você quiser liberar o primeiro elemento primeiro, então você pode ter um ponteiro temporário que aponta para o que o primeiro elemento é. Então você tem o ponteiro temporária apontando aqui. Dessa forma, temos um porão do primeiro nó. E então, uma vez que sabemos que o primeiro nó vai ser liberada, então podemos passar esta corda, essa âncora, nossa cabeça, para realmente apontar para o que quer que o primeiro está apontando. Portanto, esta cabeça realmente aponta para o segundo elemento agora. Agora estamos autorizados a liberar o que está armazenado na temperatura, e assim podemos apagar que sem ele pôr em perigo todos os outros nós na nossa lista. Outra forma que você poderia fazer isso poderia ser cada vez que você acabou de liberar o último elemento da lista porque eles são a garantia de não ser apontado para qualquer coisa. Então, você poderia simplesmente liberar este, então livre este, em seguida, um presente gratuito. Isso definitivamente funciona, mas é um pouco mais lento, porque pela natureza das listas ligadas, não podemos simplesmente saltar imediatamente para a última. Temos de percorrer cada elemento na lista encadeada e verifique se que se está a apontar para NULL, verificar a cada vez, e, em seguida, uma vez que chegar ao fim, então livre disso. Se você fosse fazer esse processo, você seria realmente verificando aqui, verificando aqui, em seguida, verificando aqui, liberando-o, em seguida, voltar, verificando aqui, verificando aqui, liberando-o, verificando aqui, e depois libertá-la. Isso leva um pouco mais tempo. Sim. 

[Aluno] Seria possível fazer uma lista ligada que armazena um ponteiro de saída para o fim? Que iria ser possível. Para repetir a pergunta, é possível ter uma estrutura de lista ligada de tal forma que tem um ponteiro que aponta para o fim da lista ligada? Eu diria que é possível, e cada vez que você inserir algo em sua lista ligada você teria que atualizar esse ponteiro e coisas assim. Você teria uma cauda * nó, por exemplo. Mas quando você está implementando esse recurso, você tem que pensar no trade-offs, gosto de quantas vezes eu vou ser iteração sobre isso, quão difícil é que vai ser a de manter o controle da cauda, ​​bem como a cabeça assim como a minha iterador, e coisas assim. Será que -? >> [Estudante] Yeah. É possível, mas em termos de decisões de projeto, você tem que pesar as opções. 

Aqui está um esqueleto de código que lhe permitiria libertar cada elemento em uma lista ligada. Mais uma vez, desde que eu estou iterando uma lista ligada, eu vou querer ter algum tipo de cursor ou iterador. Estamos repetindo até que o cursor é NULL. Você não quer repetir quando o cursor é NULL porque isso significa que não há nada na lista. Então aqui eu faço um nó temporário * apontando para o que eu estou pensando é o primeiro da minha lista, e depois eu passo o meu cursor para frente e depois um livre que eu tinha no armazenamento temporário. 

Agora chegamos ao inserir em listas ligadas. Eu tenho três nós em minha lista encadeada, e vamos com o caso simples onde queremos inserir outro nó no final da nossa lista ligada. Para isso, tudo o que gostaria de fazer é que seria atravessar para encontrar onde o fim atual da lista ligada é, então qualquer nó aponta para NULL - isso é um presente - e depois dizem que, na verdade, este não vai ser o último nó; estamos, na verdade, vai ter outro. Então teríamos este ponto uma corrente de tudo o que está inserindo. Então, agora esta pessoa vermelho aqui se torna o último nó na lista ligada. E assim a característica do último nó na lista vinculada é que ela aponta para NULL. Então, o que teríamos que fazer é definir esse cara ponteiro vermelho para NULL. Lá. 

Mas o que se queria inserir um nó entre a segunda e terceira? Que não é tão simples, porque queremos ter certeza de que não deixe ir de qualquer nó na nossa lista ligada. O que nós temos que fazer é ter certeza de que nós nos ancorar a cada um. Por exemplo, vamos chamar isso de um segundo. Se você disse que o segundo aponta agora para este novo e você acabou de fazer um ponteiro lá, então, que resultaria em um cara sendo perdida porque não há qualquer ligação com ele. Em vez disso - Eu vou chamar isso de novo. Desculpe minhas habilidades artísticas. Sabemos que não podemos simplesmente ligar diretamente dois para o novo. Temos que nos certificar de que segurar a última. O que pode querer fazer é ter um ponteiro temporário para o elemento que vai ser anexado em. Então nós temos um ponteiro temporário lá. Desde que nós sabemos que este terceiro está sendo mantido, 2 pode agora ligar para a nossa nova. E se esse cara novo vermelho vai ser entre 2 e 3, então o que é ponteiro que cara vai apontar? >> [Aluno] Temp. Temp. Sim. Então próximo valor esse cara vermelha do que vai ser temporário. Quando você está inserindo em listas ligadas, vimos que podíamos facilmente adicionar algo ao fim, criando uma matriz temporária, ou se queria acrescentar algo para o meio da nossa matriz, em seguida, seria preciso um pouco mais de andar por aí. Se você quiser, por exemplo, tem uma lista ordenada vinculado, então você tem que tipo de pesar os custos e os benefícios de que porque se você quer ter um array ordenado, o que significa que toda vez que você inserir-lo, que vai demorar um pouco mais. No entanto, se você quiser, mais tarde, como veremos, nós queremos, pesquisa através de uma lista ligada, então ele pode ser mais fácil se você sabe que tudo está em ordem. Então você pode querer pesar os custos e benefícios de que. 

Outra forma de inserir em uma lista ligada é inserir no início de uma lista. Se traçarmos a nossa âncora aqui - esta é a nossa cabeça - e depois que essas pessoas ligadas a ele, e, em seguida, temos um novo nó a ser inserido no início, em seguida, o que poderia nós queremos fazer? O que seria errado com apenas dizendo que quero vincular o vermelho para o azul, porque esse é o primeiro? O que aconteceria aqui? Todos estes três se perdesse. Então nós não queremos fazer isso. Mais uma vez, nós aprendemos que temos que ter algum tipo de ponteiro temporário. Vamos optar por ter um ponto temporário para esse cara. Então, podemos ter o ponto de um azul para a temporária e, em seguida, o ponto vermelho para o azul. A razão pela qual eu estou usando o povo aqui é porque realmente queremos visualizar segurando com as pessoas e ter certeza de que temos um link para eles antes de deixar de ir a outra mão, ou algo assim. 

Agora que temos um senso de listas ligadas - como podemos criar uma lista encadeada e criar as estruturas para que consiste na definição de tipo para um nó e, em seguida, certificando-se de que temos um ponteiro para a cabeça da lista ligada - uma vez que temos isso e sabemos como atravessar uma matriz, acessar vários elementos, nós sabemos como inserir e sabemos como libertá-los, então podemos entrar em erros ortográficos. Como de costume, nós temos uma seção de perguntas que se você usou para operar com listas ligadas e estruturas diferentes, como filas e pilhas. Então, podemos mover-se em erros ortográficos. 

Erros de ortografia tem no código de distribuição um par de arquivos de importância. Primeiro notamos que temos esse Makefile aqui, que não temos realmente visto antes. Se você olhasse dentro da pasta pset5, você percebe que você tem um. Arquivo h, então você tem dois arquivos. c. O que isso faz é Makefile antes, teríamos apenas digite make e depois o nome do programa e então veríamos todos esses argumentos e bandeiras passado para o compilador. O que o Makefile faz é nos permite compilar vários arquivos de uma só vez e passar as bandeiras que nós queremos. Aqui vemos apenas há um arquivo de cabeçalho aqui. Então na verdade nós temos dois arquivos de origem. Temos speller.c e dictionary.c. Você está convidado a editar o Makefile se desejar. Observe que aqui se você digitar limpo, então o que ele faz é realmente remove qualquer coisa que é o núcleo. Se você tem uma falha de segmentação, basicamente você consegue um core dump. Portanto, este arquivo de pouco feio irá aparecer no seu diretório chamado núcleo. Você vai querer remover o para torná-lo limpo. Ele remove todos os arquivos exe e. Arquivos o. 

Vamos dar uma olhada em dictionary.h. Este diz que ela declara a funcionalidade de um dicionário. Temos um comprimento máximo para qualquer palavra no dicionário. Dizemos que esta vai ser a palavra mais longa possível. É de comprimento 45. Então, nós não vamos ter todas as palavras que excedem esse comprimento. Aqui só temos os protótipos de função. Não temos a implementação real porque é isso que vamos fazer para este pset. Mas o que isso faz é já que estamos lidando com arquivos maiores aqui e funcionalidade em uma escala maior, é útil ter um. arquivo h para que outra pessoa lendo ou usando seu código pode entender o que está acontecendo. E talvez eles querem implementar tenta se você fez tabelas de hash ou vice-versa. Então eles dizem que minha função de carga, a implementação real vai ser diferente, mas este protótipo não vai mudar. Aqui nós verificar, que retorna verdadeiro se uma determinada palavra está no dicionário. Então, temos de carga, que basicamente leva em um arquivo de dicionário e carrega-lo em alguma estrutura de dados. Temos tamanho, que, quando chamado, retorna o tamanho de seu dicionário, quantas palavras são armazenados, e descarregar, o que libera toda a memória que você pode ter tomado ao mesmo tempo que seu dicionário. 

Vamos dar uma olhada em dictionary.c. Vemos que é muito parecido com dictionary.h, só que agora ele só tem todas essas TODOs nele. E assim que é o seu trabalho. Eventualmente, você vai ser o preenchimento de speller.c com todo este código. Dictionary.c, quando executado, não é realmente vai fazer alguma coisa, por isso olhar para speller.c para ver a implementação real do corretor ortográfico. Mesmo que você não vai ser a edição qualquer código, é importante ler, entender quando é chamado de carga, quando eu estou chamando de verificação, só para entender, mapeá-lo para fora, ver como a função funciona. Vemos que ele está verificando o uso correto. Essencialmente, quando alguém corre speller, isso indica que é opcional para eles para passar em um arquivo de dicionário, porque lá vai ser um arquivo de dicionário padrão. E então eles têm que passar o texto a ser verificado feitiço. rusage ofertas com o tempo, porque uma parte deste pset que vamos tratar mais tarde é não só obter um funcionamento corretor ortográfico trabalhando mas realmente conseguir que ele seja rápido. E assim, então, que é onde rusage vai vir dentro Aqui, vemos a primeira chamada para um de nossos arquivos dictionary.c, que é carga. Carga retorna true ou false - true em caso de sucesso, falso em caso de falha. Então, se o dicionário não foi colocado corretamente, então o speller.c irá retornar 1 e saia. Mas se ele faz a carga corretamente, então ele vai continuar. Continuamos, e vemos algum arquivo I / O aqui, onde vai ser lidar com a abertura do arquivo de texto. Aqui, o que isso faz é feitiço verifica cada palavra no texto. Então, o que está fazendo speller.c aqui está interagindo sobre cada uma das palavras no arquivo de texto e, em seguida, verificando-los no dicionário. Aqui, temos um Boolean incorreta que vai ver se a verificação retorna verdadeiro ou não. Se a palavra é, na verdade, no dicionário, então cheque retornará true. Isso significa que a palavra não está incorreto. Então incorreta seria falsa, e é por isso que temos o estrondo lá, a indicação. Nós manter em curso, e em seguida, ele mantém o controle de quantas palavras com erros ortográficos existem no arquivo. Ele continua e fecha o arquivo. Então, aqui, ele informa quantas palavras com erros ortográficos que você teve. Ele calcula a quantidade de tempo que levou para carregar o dicionário, quanto tempo demorou para verificá-lo, quanto tempo levou para calcular o tamanho, que, como nós vamos continuar, deve ser muito pequena, e depois de quanto tempo que levou para descarregar o dicionário. Aqui em cima, vemos a chamada para descarregar aqui. Se verificar tamanho aqui, então vemos que aqui é a chamada para o tamanho em que determina o tamanho do dicionário. Impressionante. 

Nossa tarefa para este pset é implementar carga, o que vai carregar o dicionário estrutura de dados - o que você escolher, seja ele uma tabela hash ou uma tentativa - com palavras do arquivo de dicionário. Então você tem tamanho, que irá retornar o número de palavras no dicionário. E se você implementar carga de uma forma inteligente, então o tamanho deve ser muito fácil. Então você verificar, que irá verificar se uma palavra está no dicionário. Então speller.c passa em uma corda, e então você tem que verificar se string que está contido dentro de seu dicionário. Observe que geralmente temos dicionários padrão, mas neste pset, basicamente, qualquer dicionário transmitido em qualquer língua. Portanto, não podemos apenas supor que a palavra THE está dentro. O FOOBAR palavra pode ser definida em um dicionário certo que passamos dentro E então temos descarregar, o que libera o dicionário da memória. 

Primeiro, eu gostaria de ir sobre o método de tabela hash sobre como podemos implementar todas essas quatro funções, e então eu vou passar por cima do método tenta, como podemos implementar essas quatro funções, e na conversa final sobre algumas dicas gerais quando você está fazendo o pset e também como você pode ser capaz de usar Valgrind para verificar se há vazamentos de memória. 

Vamos para o método de tabela hash. Uma tabela consiste de uma lista de baldes. Cada valor, cada palavra, está a ir em um desses baldes. Uma tabela idealmente distribui todos esses valores que você está passando em e em seguida preenche-los no balde de modo que cada balde tem cerca de um igual número de valores na mesma. A estrutura de uma tabela hash, temos uma série de listas ligadas. O que fazemos é quando passamos em um valor, nós verificamos que esse valor deveria pertencer, balde que ela pertence, e depois colocá-lo na lista ligada associada a esse balde. Aqui, o que eu tenho é uma função hash. É uma tabela int hash. Assim, para o primeiro balde, quaisquer inteiros abaixo de 10 ir para o primeiro balde. Quaisquer números inteiros acima de 10, mas abaixo de 20 ir para o segundo, e, em seguida, assim por diante e assim por diante. Para mim, cada segmento é representar esses números. No entanto, dizer que eu estava a passar em 50, por exemplo. Afigura-se como se os três primeiros contêm uma série de 10 números. Mas eu quero deixar o meu tabela hash para tomar qualquer tipo de inteiros, então eu teria que filtrar todos os números acima de 30 no balde passado. E assim, então, que resultaria em uma espécie de tabela hash desequilibrada. Para reiterar, uma tabela hash é apenas uma matriz de caçambas onde cada balde é uma lista ligada. E assim, para determinar onde cada valor vai, que ele vai para balde, você vai querer o que é chamado de função hash que assume um valor e, em seguida, diz que este valor corresponde a um balde certo. Então, lá em cima, neste exemplo, a minha função hash levou cada valor. É verificado se foi inferior a 10. Se fosse, seria colocá-lo no primeiro balde. Ele verifica se é menor que 20, coloca-o no segundo, se verdadeira, verifica se é menor que 30, e em seguida, coloca-o no terceiro balde, e depois de tudo só cai no balde quarto. Assim, sempre que você tem um valor, função seu hash vai colocar o valor dentro do balde apropriado. A função hash, basicamente, precisa saber quantos baldes que você tem. Seu tamanho da tabela, o número de depósitos que você tem, que vai ser um número fixo que é com você, para você decidir, mas vai ser um número fixo. Portanto, sua função hash vai estar contando com isso para determinar qual balde de cada chave vai para de tal forma que é uniformemente distribuída. Similar à nossa implementação de listas ligadas, agora cada nó na tabela de hash é realmente vai ter um char tipo. Portanto, temos uma matriz de char chamado palavra e, em seguida, outro ponteiro para o próximo nó, o que faz sentido, porque vai ser uma lista ligada. Lembre-se de quando tinha ligado listas, fiz um * nó chamado cabeça que estava apontando para o primeiro nó na lista vinculada. Mas para a nossa tabela hash, porque temos várias listas ligadas, o que nós queremos é que nós queremos que a nossa tabela de hash para ser como, "O que é um balde?" Um balde é apenas uma lista de ponteiros de nós, e assim cada elemento no balde na realidade aponta para sua lista vinculado correspondente. Para voltar a este esquema, você vê que os baldes em si são as setas, não nós reais. Uma propriedade essencial de funções hash é que eles são determinísticos. Isso significa que sempre que você hash o número 2, ele deve retornar sempre o mesmo balde. Cada valor único que vai para a função hash, se repetida, tem de obter o mesmo índice. Portanto, sua função hash retorna o índice da matriz quando esse valor pertence. Como mencionei antes, o número de depósitos é fixo, e para que o seu índice que você voltar tem que ser menor do que o número de caçambas mas maior que 0. A razão pela qual nós temos funções de hash em vez de apenas uma única lista vinculada ou uma única matriz é que nós queremos ser capaz de saltar para uma determinada seção mais facilmente se sabemos que a característica de um valor - em vez de ter que procurar no dicionário todo, ser capaz de saltar para uma determinada seção do mesmo. Sua função hash deve ter em conta que, idealmente, cada balde tem aproximadamente o mesmo número de teclas. Como a tabela hash é uma série de listas ligadas, em seguida, as listas ligadas próprios vão ter mais de um nó. No exemplo anterior, dois números diferentes, mesmo que elas não sejam iguais, quando desordenado, voltaria o mesmo índice. Então, quando você está lidando com as palavras, uma palavra quando hash seria o mesmo valor hash como outra palavra. Isso é o que chamamos de uma colisão, quando temos um nó que, quando hash, a lista ligada a esse balde não está vazio. A técnica que chamamos há linear sondagem, onde você vai para a lista de ligações e, em seguida, descobrir onde você deseja inserir o nó porque você tem uma colisão. Você pode ver que pode haver um trade-off aqui, certo? Se você tem uma tabela muito pequena hash, um número muito pequeno de baldes, então você vai ter um monte de colisões. Mas, então, se você fizer uma tabela hash muito grande, você está indo provavelmente para minimizar as colisões, mas vai ser uma grande estrutura de dados. Não vai ser trade-offs com isso. Então, quando você está fazendo a sua pset, tente brincar entre talvez fazer uma pequena tabela hash mas então sabendo que ele vai demorar um pouco mais para atravessar os diferentes elementos dessas listas ligadas. 

O que carga vai fazer é iterar sobre cada palavra no dicionário. Ele passa um ponteiro para o arquivo de dicionário. Então, você vai aproveitar o arquivo E / S funções que dominam em pset4 e iterar sobre cada palavra no dicionário. Você quer que todas as palavras do dicionário para se tornar um novo nó, e você vai colocar cada um desses nós dentro de sua estrutura de dados dicionário. Sempre que você começa uma nova palavra, você sabe que ele vai se tornar um nó. Então você pode ir imediatamente e malloc um ponteiro nó para cada palavra nova que você tem. Aqui eu estou chamando meu new_node ponteiro nó e estou mallocing o que? O tamanho de um nó. Então, para ler a seqüência real de um arquivo, porque o dicionário é armazenado por uma palavra e, em seguida, uma nova linha, o que pode tirar vantagem de é a função fscanf, qual é o arquivo de dicionário que estamos passada, por isso verifica o arquivo para uma string e lugares que cadeia no último argumento. Se você se lembrar de volta para uma das palestras, quando nós fomos e tipo de descascadas as camadas de volta na biblioteca CS50, vimos uma implementação de fscanf lá. Para voltar ao fscanf, temos o arquivo que estamos lendo, estamos à procura de uma cadeia em que o arquivo, e depois vamos colocá-lo em aqui eu tenho new_node-> palavra porque new_node é um ponteiro nó, não um nó real. Então eu estou dizendo new_node, eu quero ir para o nó que ele está apontando para e depois atribuir o valor à palavra. Queremos então tomar a palavra e inseri-lo na tabela de hash. Perceba que fizemos new_node um ponteiro nó porque nós vamos querer saber o que o endereço do nó é quando inseri-lo no porque a estrutura dos nós próprios, da estrutura, é que eles têm um apontador para um novo nó. Então qual é o endereço do nó que vai apontar? Esse endereço vai ser new_node. Isso faz sentido, porque estamos fazendo um new_node * nó em oposição a um nó? Okay. Temos uma palavra. Esse valor é new_node-> palavra. Que contém a palavra do dicionário que deseja introduzir. Então, o que nós queremos fazer é que nós queremos chamar a nossa função hash sobre essa seqüência porque a nossa função hash leva em uma seqüência e depois nos devolve um número inteiro, onde esse inteiro é o índice onde hashtable em que o índice representa que balde. Queremos levar esse índice e, em seguida, ir para o índice da tabela hash e depois usar essa lista ligada para inserir o nó no new_node. Lembre-se que, contudo, você decidir inserir o nó, se é no meio se você quiser resolver isso ou no início ou no final, apenas a certeza de que o seu último nó sempre aponta para NULL porque essa é a única maneira que sabemos onde o último elemento da nossa lista ligada é. 

Se o tamanho é um inteiro que representa o número de palavras em um dicionário, em seguida, uma forma de fazer isto é a de que, sempre que o tamanho é chamado passamos por cada elemento em nossa tabela hash e em seguida, percorrer cada lista ligada dentro da tabela hash e, então, calcular o comprimento de que, aumentando a nossa 1 contador em 1. Mas cada vez que o tamanho é chamado, que vai levar um longo tempo porque vamos ser linearmente sondando cada única lista vinculada. Em vez disso, ele vai ser muito mais fácil se você manter o controle de quantas palavras são passados ​​dentro Então se você incluir um contador dentro de sua função de carga que as atualizações, conforme necessário, em seguida, contador, se você defini-lo como uma variável global, serão capazes de ser acedidos pelo tamanho. Então, o que tamanho poderia simplesmente fazer é em uma linha, basta retornar o valor do contador, o tamanho do dicionário, que você já tratadas na carga. Isso é o que eu quis dizer quando disse que se você implementar carga de uma forma útil, então o tamanho vai ser muito fácil. 

Então, agora temos de verificar. Agora estamos lidando com palavras do arquivo de texto de entrada, e assim vamos estar verificando se todas essas palavras de entrada são, na verdade, no dicionário ou não. Semelhante a Scramble, queremos permitir a insensibilidade caso. Você quer ter certeza de que todas as palavras passada, apesar de serem caso misto, quando chamado com comparação string, são equivalentes. As palavras nos arquivos de texto dicionário são, na verdade, todas as letras minúsculas. Outra coisa é que você pode assumir que cada palavra passada, cada corda, vai ser tanto alfabética ou conter apóstrofos. Apóstrofos vão ser palavras válidas em nosso dicionário. Então se você tem uma palavra com apóstrofo S, que é uma palavra real legítimo em seu dicionário que vai ser um dos nós na tabela hash. Verifique se opera com a palavra existe, então ele tem que estar em nossa tabela de hash. Se a palavra está no dicionário, então todas as palavras do dicionário estão na tabela hash, então vamos olhar para esta palavra na tabela hash. Nós sabemos que desde que implementamos nosso função hash de tal modo que cada palavra única é sempre hash para o mesmo valor, então nós sabemos que, em vez de pesquisar através de nossa mesa inteira toda hash, nós podemos realmente encontrar a lista ligada que essa palavra deve pertencer. Se fosse no dicionário, então seria nesse balde. O que podemos fazer, se a palavra é o nome de nossa string passada, Nós podemos apenas hash que palavra e olhar para a lista ligada no valor de hashtable [hash (palavra)]. De lá, o que podemos fazer é que temos um subconjunto menor de nós para procurar por esta palavra, e para que possamos atravessar a lista ligada, usando um exemplo de mais cedo no passo a passo, e depois chamar string compare com a palavra onde quer que o cursor está apontando, essa palavra, e ver se os comparar. Dependendo da maneira que você organizar a sua função hash, se for ordenado, você pode ser capaz de voltar um pouco mais cedo falsa, mas se é indiferenciados, então você quer continuar percorrendo através de sua lista ligada até encontrar o último elemento da lista. E se você ainda não encontrou a palavra pelo tempo que você chegou ao fim da lista ligada, que significa que a sua palavra não existe no dicionário, e assim que a palavra é inválido, e verificação deve retornar falso. 

Agora vamos para descarregar, onde queremos libertar todos os nós que temos malloc'd, tão livre de todos os nós dentro de nossa tabela de hash. Nós vamos querer iterar sobre todas as listas ligadas e livres de todos os nós que. Se você olhar acima no passo a passo para o exemplo em que liberar uma lista ligada, então você vai querer repetir esse processo para cada elemento na tabela hash. E eu vou passar por cima deste para o final da explicação, mas Valgrind é uma ferramenta onde você pode ver se você adequadamente libertado cada nó que você malloc'd ou qualquer outra coisa que você malloc'd, qualquer outro ponteiro. Então, isso é tabelas de hash, onde temos um número finito de baldes e uma função hash, que terá um valor e depois atribuir o valor para um balde certo. 

Agora chegamos ao tentativas. Tenta tipo de olhar como este, e eu também vou tirar um exemplo. Basicamente, você tem toda uma série de cartas de potenciais, e então, sempre que você está construindo uma palavra, essa carta pode ser ligado por um dicionário para uma vasta gama de possibilidades. Algumas palavras começam com C, mas em seguida, continuar com A, mas outros continuam com O, por exemplo. Um trie é uma maneira de visualizar todas as combinações possíveis dessas palavras. Uma trie vai acompanhar a seqüência de letras que compõem as palavras, ramificando-se, quando necessário, quando uma letra pode ser seguido por um múltiplo de cartas, e no final de cada ponto indicam se a palavra é válido ou não porque se você está soletrando a palavra MAT, MA Eu não acho que é uma palavra válida, mas é MAT. E assim, em seu trie, isso indicaria que depois de MAT que na verdade é uma palavra válida. Cada nó na nossa trie está realmente indo para conter uma matriz de ponteiros de nós, e nós vamos ter, especificamente, 27 dos ponteiros do nó, um para cada letra do alfabeto, assim como o carácter apóstrofo. Cada elemento na matriz é em si que irá apontar para outro nó. Então, se esse nó é NULL, se não há nada depois disso, então sabemos que não há outras cartas em que a seqüência de palavras. Mas se esse nó não é NULL, o que significa que existem mais cartas em que seqüência de letras. E depois disso, cada nó indica se é o último caractere de uma palavra ou não. 

Vamos para um exemplo de uma trie. Primeiro eu tenho espaço para 27 nós nesta matriz. Se eu tiver a palavra BAR - Se eu tiver a BAR palavra e eu quero inserir em que, a primeira letra é B, então se minha trie é vazio, B é a segunda letra do alfabeto, então eu vou escolher para colocar esta aqui neste índice. Eu vou ter B aqui. B vai ser um nó que aponta para outra matriz de todos os possíveis caracteres que pode seguir após a letra B. Neste caso, eu estou lidando com a barra de palavra, de modo que A irá aqui. Depois de A, eu tenho a letra R, de forma seguida, um pontos agora para a sua própria combinação, e R estarei aqui. BAR é uma palavra completa, então eu vou ter ponto R para outro nó que diz que essa palavra é válido. Esse nó é também vai ter um conjunto de nós, mas aqueles podem ser NULL. Mas, basicamente, ele pode continuar assim. Isso vai se tornar um pouco mais claro quando vamos a um exemplo diferente, por isso tenha paciência comigo lá. Agora temos BAR dentro do nosso dicionário. Agora dizer que temos o BAZ palavra. Começamos com B, e já temos B como uma das cartas que estão em nosso dicionário. Isso é seguido com A. Temos um já. Mas, então, em vez disso, temos seguinte Z. Então, em seguida, um elemento em nossa matriz vai ser Z, e assim, então, que um vai apontar para outro fim válido da palavra. Assim, vemos que quando continuamos a B e depois A, há duas opções diferentes atualmente em nosso dicionário de palavras que começam com B e A. Dizer que queria inserir o FOOBAR palavra. Então, gostaríamos de fazer uma entrada em F. F é um nó que aponta para uma matriz inteira. O que iria encontrar, vá para O, O, em seguida, liga para uma lista inteira. Teríamos B e, em seguida, continuar, teríamos A e depois R. Então atravessa foobar todo o caminho até FOOBAR é uma palavra correta. E assim, então isso seria uma palavra válida. Agora dizer que a nossa próxima palavra no dicionário é realmente a palavra FOO. Diríamos F. O que se segue F? Na verdade, eu já tenho um espaço para O, então eu vou continuar. Eu não preciso de fazer um novo. Continuar. FOO é uma palavra válida neste dicionário, então eu vou para indicar que isso é válido. Se eu parar meu seqüência lá, que seria correto. Mas se continuamos a nossa seqüência de FOO até B e só tinha foob, foob não é uma palavra, e isso não é indicado como um válido. Em uma trie, você tem cada nó indicando se é uma palavra válida ou não, e, em seguida, cada nó também tem uma matriz de 27 ponteiros do nó que aponte para nós próprios. 

Aqui está uma forma de como você pode querer definir isso. No entanto, tal como no exemplo da tabela hash, onde tinha a cabeça * nó para indicar o início de nossa lista ligada, nós também vamos querer alguma forma de saber onde o início de nossa trie é. Alguns chamam as pessoas tenta árvores, e é aí que vem da raiz. Então, nós queremos a raiz da nossa árvore para ter certeza de que vamos ficar aterrado para onde o nosso trie é. Nós já meio que fui mais a maneira como você poderia pensar sobre o carregamento de cada palavra no dicionário. Essencialmente, para cada palavra que você vai querer para percorrer o trie e sabendo que cada elemento em que as crianças - que chamou de crianças neste caso - corresponde a uma letra diferente, você vai querer verificar esses valores em que o índice particular, que corresponde à letra. Então, pensando todo o caminho de volta para César e Vigenère, sabendo que cada carta que você pode tipo de mapa para um índice alfabético, definitivamente de A a Z vai ser muito fácil de mapear para uma letra alfabética, mas, infelizmente, as apóstrofes são também um caráter aceito em palavras. Eu nem tenho certeza do que o valor ASCII é, assim para que, se você quiser encontrar um índice de decidir se você quer que ele seja o primeiro ou um ou o último, você vai ter que fazer um teste codificado para que e depois colocar isso no índice 26, por exemplo. Então você está verificando o valor em crianças [i] onde [i] corresponde a qualquer carta que você está. Se isso é NULL, o que significa que não há atualmente nenhuma carta possíveis decorrente de que a seqüência anterior, de modo que você vai querer malloc e fazer um novo nó e têm que as crianças [i] ponto para ele de modo que você criar - quando inserido uma carta para o rectângulo - tornando as crianças não-NULL e ponto em que novo nó. Mas se isso não é NULL, como no nosso exemplo do FOO quando já tinha FOOBAR, continuamos, e não estamos sempre fazendo um novo nó, mas sim apenas a criação is_word para true no fim da palavra. 

Portanto, assim como antes, porque aqui você está lidando com cada letra de cada vez, que vai ser mais fácil para você para o tamanho, em vez de ter de calcular e passar por toda a árvore e calcular quantos filhos eu tenho e, em seguida, ramificando-se, lembrando-se quantos estão do lado esquerdo e do lado direito e coisas assim, vai ser muito mais fácil para você se você só manter o controle de quantas palavras você está adicionando em quando você está lidando com a carga. E então que o tamanho do caminho pode retornar apenas uma variável global do tamanho. 

Agora chegamos a verificar. Mesmos padrões de antes, onde queremos permitir a insensibilidade caso. Como assim, vamos supor que as cordas são apenas caracteres alfabéticos ou os apóstrofos porque as crianças é uma matriz de 27 de comprimento, assim todas as letras do alfabeto mais o apóstrofo. Para verificar o que você vai querer fazer é que você vai querer começar na raiz porque a raiz irá apontar para uma matriz que contém todas as letras possíveis a partir de uma palavra. Você vai começar por aí, e então você vai verificar é este valor NULL ou não, porque se o valor é NULL, o que significa que o dicionário não tem quaisquer valores que contêm a carta em que a ordem particular. Se é nulo, então isso significa que a palavra é grafada imediatamente. Mas se não é NULL, então você pode continuar, dizer que a primeira letra é uma carta possível primeiro em uma palavra, então agora eu quero verificar se a segunda letra, essa sequência, está dentro do meu dicionário. Então você está indo para ir para o índice de crianças do primeiro nó e verificar se essa segunda carta existe. Então você repetir esse processo para verificar se que a seqüência é válido ou não dentro de seu trie. Sempre que as crianças nó no índice aponta para NULL, você sabe que a seqüência não existe, mas se você chegar ao final da palavra que você digitou, então você quer verificar agora que eu completei essa seqüência e descobriu que dentro do meu trie, que é uma palavra válida ou não? E então você quer verificar se, e é aí que se você encontrou essa sequência, então você quer verificar se essa palavra é válido ou não porque lembro que no caso anterior que eu desenhei, onde tivemos foob, que era uma seqüência válida que encontramos, mas não era uma palavra real válido em si. 

Da mesma forma, para descarregar nas tentativas que você quer para descarregar todos os nós em sua trie. Desculpe. Similares às tabelas de hash onde descarregar em nós libertados todos os nós, nas tentativas também queremos libertar todos os nós. Descarregar realmente mais fácil trabalhar de baixo para cima porque estes são essencialmente ligados listas. Então, nós queremos ter certeza de que temos para todos os valores e livre de todos los explicitamente. O que você vai querer fazer se você está trabalhando com uma trie é viajar para o fundo e nó do livre menor possível primeiro e depois ir-se a todos os filhos e, então, livre de todos aqueles, ir para cima e, então, livre, etc Tipo de como lidar com a camada de fundo do primeiro trie e depois vai lá em cima depois de ter libertado tudo. Este é um bom exemplo de que a função recursiva pode vir a calhar. Uma vez que você libertou a camada inferior da trie, então você chama descarregar sobre o resto, certificando-se de que você liberar todos os mini - Você pode tipo de visualizá-lo como tentativas mini. Então, você tem a sua raiz aqui. Estou simplificando, então eu não tenho que tirar 26 deles. Então você tem isso, e em seguida, estes representam sequências de palavras onde todos estes pequenos círculos são letras que são seqüências válidas de letras. Vamos continuar um pouco mais. O que você vai querer fazer é livre o fundo aqui e então livre este e, em seguida, um presente livre no fundo antes de libertar o topo aqui porque se você algo livre no segundo nível aqui, então você realmente iria perder este valor aqui. É por isso que é importante na descarga de um trie para se certificar de que você liberar o fundo primeiro. O que você pode querer fazer é dizer para cada nó Quero descarregar todas as crianças. 

Agora que já sabemos descarregar para o método de tabela hash, bem como o método trie, vamos querer olhar para Valgrind. Valgrind você corre com os seguintes comandos. Você tem valgrind-v. Você está verificando todos os vazamentos quando você executar speller dado este determinado texto speller porque precisa levar em um arquivo de texto. Então Valgrind irá executar o seu programa, dizer quantos bytes você alocado, quantos bytes você libertou, e ele vai lhe dizer se você libertou apenas o suficiente ou se você não livre suficiente, ou, às vezes você pode até mesmo sobre-livre, como um nó livre que já foi libertado e assim ele irá retornar erros. Se você usar Valgrind, ele vai te dar algumas mensagens indicando se você libertou ou menos do que o suficiente, apenas o suficiente, ou mais vezes o suficiente. 

Uma parte deste pset, é opcional para desafiar o Big Board. Mas quando estamos lidando com essas estruturas de dados É divertido ver o quão rapidamente e quão eficiente suas estruturas de dados poderia ser. Será que o seu resultado função hash em um monte de colisões? Ou é o seu tamanho de dados realmente grande? Leva muito tempo para atravessar? No registo de speller, ele exibe quanto tempo você usa para carregar, para verificar, para conduzir, tamanho e para descarregar, e assim aqueles são postados no O Big Board, onde você pode competir contra os seus colegas e alguns membros da equipe para ver quem tem o mais rápido corretor ortográfico. Uma coisa que eu gostaria de observar sobre as tabelas de hash é que há algumas funções muito simples de hash que poderíamos pensar. Por exemplo, você tem 26 baldes, e assim cada balde corresponde à primeira letra de uma palavra, mas isso vai resultar em uma tabela de hash muito desequilibrada porque existem palavras muito menos que começam com X do que começar com M, por exemplo. Uma maneira de fazer speller é se você deseja obter todas as funcionalidades outra para baixo, depois é só usar uma simples função hash para ser capaz de obter o seu código em execução e depois voltar e alterar o tamanho de sua tabela de hash e definição. Há uma série de recursos na internet para funções de hash, e assim para este pset que estão autorizados a pesquisar funções hash na internet para algumas dicas e inspiração, desde que você tenha certeza de citar onde você tem que partir. Você está convidado a olhar e interpretar alguma função hash que você encontrar na Internet. Voltar a isso, você pode ser capaz de ver se alguém usou uma trie se a sua implementação é mais rápido do que sua tabela hash ou não. Você pode enviar para o Conselho Big várias vezes. Ela irá gravar sua entrada mais recente. Então talvez você mudar de função hash e, em seguida, perceber que na verdade é muito mais rápido ou muito mais lento do que antes. Isso é um pouco de uma forma divertida. Há sempre um ou dois membros da equipe que tentam fazer o dicionário mais lento possível, de modo que é sempre divertido de se olhar. 

O uso para o pset é executar speller com um dicionário opcional e, em seguida, um arquivo de texto obrigatória. Por padrão, quando você executar speller com apenas um arquivo de texto e não especificar um dicionário, ele vai usar o arquivo de texto dicionário, a uma grande na pasta cs50/pset5/dictionaries. Que um tem mais de 100.000 palavras. Eles também têm um pequeno dicionário, que tem palavras consideravelmente menos CS50 que fez para você. No entanto, você pode muito facilmente apenas fazer o seu próprio dicionário se você só quer estar trabalhando em pequenos exemplos - por exemplo, se você quiser usar o gdb e você sabe os valores específicos que você quer que seu tabela de hash para mapear a. Então você só pode fazer o seu próprio arquivo de texto apenas com bar, baz, FOO, e FOOBAR, fazer isso em um arquivo de texto, separar aqueles cada um com uma linha, e, em seguida, fazer o seu próprio arquivo de texto que literalmente só contém talvez uma ou duas palavras para que você saiba exatamente o que a saída deve ser. Alguns dos arquivos de texto mostra que a Big Board quando você executar desafio irá verificar são Guerra e Paz e um romance de Jane Austen, ou algo assim. Então, quando você está começando, é muito mais fácil de fazer seus próprios arquivos de texto que contêm apenas um par de palavras ou talvez 10 de modo que você pode prever o que o resultado deve ser e depois verificar se contra isso, então mais um exemplo controlado. E assim já que estamos lidando com a previsão e desenhar as coisas, outra vez eu quero te encorajar a usar papel e caneta porque ele realmente vai ajudá-lo com um presente - desenhar as setas, como a tabela hash ou como seu trie olha, quando você está liberando algo onde as setas estão indo, você está segurando o suficiente, você vê todos os links desaparecendo e caindo no abismo da memória vazada. Então, por favor, por favor, tente desenhar as coisas mesmo antes de chegar a escrever código para baixo. Desenhe as coisas para que você entenda como as coisas estão indo para o trabalho porque então eu garanto que você vai correr em confusões menos ponteiro lá. 

Tudo bem. Quero desejar-lhe o melhor da sorte com este pset. É provavelmente o mais difícil. Portanto, tente começar cedo, desenhar as coisas, desenhar as coisas, e boa sorte. Este foi Walkthrough 5. 

[CS50.TV]