JASON HIRSCHHORN: Sejam bem-vindos à Seção de Sete. Estamos na semana de sete do curso. E esta próxima quinta-feira Halloween é assim que eu sou vestido como uma abóbora. Eu não conseguia curvar e colocar em meus sapatos, então é por isso que eu sou apenas vestindo meias. Eu também não estou usando nada por baixo isso, então eu não posso tirá-lo, se é distraindo a você. Peço desculpas antecipadamente por isso. Você não precisa de imaginar o que está acontecendo. Eu estou usando cueca. Então, é tudo de bom. 

Eu tenho uma longa história sobre por que estou vestido como uma abóbora, mas eu vou guardar para mais tarde nesta seção porque eu quero começar. Nós temos um monte de coisas interessantes para ir ao longo desta semana. A maioria deles estão directamente relacionadas com esta conjunto de problemas da semana, erros de ortografia. Nós vamos estar passando por cima ligado listas e tabelas hash para toda a seção. Coloquei esta lista a cada semana, uma lista de recursos para que você possa ajudá-lo com O material deste curso. Se em uma perda ou se procurando alguma obter mais informações, confira um dos esses recursos. 

Mais uma vez, é pset6 erros ortográficos, pset desta semana. E também encoraja você, e eu incentivá-lo, usar algum outro recursos especificamente para este pset. Em particular, os três que eu tenho listado na tela - gdb, que temos sido familiarizado com e usado por um tempo agora, é vai ser muito útil nesta semana. Então eu coloquei isso aqui em cima. Mas sempre que você está trabalhando com C, você deve sempre estar usando gdb para depurar seus programas. Esta semana também Valgrind. Alguém sabe o que valgrind faz? 

AUDIÊNCIA: Ele verifica se há vazamentos de memória? 

JASON HIRSCHHORN: Valgrind verifica se há vazamentos de memória. Então, se você malloc algo em seu programa, você está pedindo para a memória. No final do seu programa, você tem livre para escrever sobre tudo o que tenho malloced para dar a memória de volta. Se você não escrever livre no final e o programa chega a uma conclusão, tudo automaticamente ser liberado. E para pequenos programas, é não um grande negócio. Mas se você está escrevendo uma longa corrida programa que não parar, necessariamente, em um par de minutos ou uma alguns segundos, em seguida, vazamentos de memória pode se tornar um grande negócio. 

Assim, para pset6, a expectativa é que você vai ter zero vazamentos de memória com seu programa. Para verificar se há vazamentos de memória, valgrind executar e ele vai dar-lhe algum bom saída permitindo que você saiba se ou nem tudo estava livre. Vamos praticar com ele mais tarde hoje, eu espero. 

Finalmente, o comando dif. Você usou algo semelhante a ele em pset5 com a ferramenta espiada. Permitiu-lhe olhar para dentro. Você também usou diff, também, por o conjunto de problemas spec. Mas, permitiu-lhe comparar dois arquivos. Você poderia comparar o arquivo de bitmap e Informações cabeçalhos de uma solução pessoal e a sua solução em pset5 se você optou por usá-lo. Dif permitirá que você fazer isso, também. Você pode comparar a resposta correta para problema desta semana para definir a sua resposta e ver se ele se alinhe ou ver em que os erros são. 

Portanto, estas são três boas ferramentas que você deve usar para esta semana, e definitivamente verificar o seu programa com estas três ferramentas antes de virar-lo dentro Mais uma vez, como já mencionado a cada semana, se você tiver algum comentário para mim - tanto positiva e construtiva - sentir-se livre para ir para o site na parte inferior do slide e introduzi-la lá. Eu realmente aprecio qualquer e todos os comentários. E se você me dar coisas específicas que Que posso fazer para melhorar ou que eu sou fazendo bem que você gostaria que eu continuar, eu levo isso a sério e realmente se esforçam para ouvir para o seu feedback. Eu não posso prometer que vou fazer tudo, porém, como vestir uma abóbora traje a cada semana. 

Então vamos passar a maior parte seção, como já referi, falando listas ligadas e tabelas de hash, que será diretamente aplicável ao conjunto de problemas esta semana. Listas encadeadas, vamos passar por cima de relativamente rapidamente, porque nós passamos um pouco mais justo tempo indo sobre ele na seção. E então vamos direto para o codificação problemas para listas ligadas. E então no final nós vamos falar sobre tabelas hash e como se aplicam a este O problema da semana definido. 

Você já viu esse código antes. Esta é uma estrutura, e que consiste em definir algo novo chamado de nó. E dentro de um nó existe um número inteiro aqui e ali é um ponteiro para outro nó. Nós já vimos isso antes. Isso foi chegando para um par de semanas agora. Ele combina os ponteiros, que temos sido trabalhar com, e estruturas, que permitem nos a combinar dois diferentes coisas em um tipo de dados. 

Há muita coisa acontecendo na tela. Mas tudo isso deve ser relativamente familiarizados com você. Na primeira linha, nós declarar um novo nó. E, em seguida, dentro desse novo nó, eu definir o inteiro em que o nó para um. Nós vemos na próxima linha que eu estou fazendo um printf comando, mas eu já esmaecidas o comando printf, porque a verdade parte importante é essa linha aqui - new_node.n. O que faz o ponto significa? 

AUDIÊNCIA: Vá para o nó e avaliar o valor n para ele. 

JASON HIRSCHHORN: Isso é exatamente correto. Dot significa acessar a parte n deste novo nó. A próxima linha faz o quê? Michael. 

AUDIÊNCIA: Cria outro nó que irá apontar para o novo nó. 

JASON HIRSCHHORN: Então não faz criar um novo nó. Ele cria um o quê? 

AUDIÊNCIA: Um ponteiro. 

Jason HIRSCHHORN: Um apontador para um nó, como indicado por este nó * aqui. Assim, cria-se um ponteiro para um nó. E qual nó ele é apontando para, Michael? 

AUDIÊNCIA: Novo nó? 

JASON HIRSCHHORN: Novo nó. E ele está apontando lá porque nós temos dado o endereço do novo nó. E agora nesta linha vemos duas maneiras diferentes de expressando a mesma coisa. E eu queria salientar a forma como estes duas coisas são o mesmo. Na primeira linha, nós desreferenciava o ponteiro. Então vamos para o nó. Isso é o que esta estrela significa. Nós já vimos isso antes com ponteiros. Ir para aquele nó. Isso é entre parênteses. E, em seguida, acessar via o operador ponto o elemento n desse nó. 

Então, que está tomando a sintaxe vimos aqui e agora usá-lo com um ponteiro. Claro, ele fica um pouco ocupado se você está escrevendo esses parênteses - que estrela e que ponto. Fica um pouco ocupado. Portanto, temos um pouco de açúcar sintático. E esta linha aqui - ptr_node-> n. Isso faz exatamente a mesma coisa. Então, essas duas linhas de código são equivalente e fará exatamente a mesma coisa. 

Mas eu queria apontar aqueles antes de ir mais longe para que possa entender que realmente esta coisa aqui é apenas açúcar sintático para dereferencing o ponteiro e, em seguida, indo para a parte n dessa estrutura. Qualquer dúvida sobre este slide? OK. 

Então vamos passar por um casal de operações que você pode fazer em listas ligadas. Uma lista ligada, recall, é uma série de nós que apontam um para o outro. E nós geralmente começam com um ponteiro chamado cabeça, em geral, que aponta para a primeira coisa na lista. Então, na primeira linha aqui, nós temos o nosso L original primeiros. Então aquela coisa que você pode pensar - este texto aqui você pode pensar em como apenas o ponteiro temos armazenados que em algum lugar pontos ao primeiro elemento. E nesta lista ligada temos quatro nós. Cada nó é uma caixa grande. A caixa maior dentro da grande caixa é a parte inteira. E então nós temos uma parte do ponteiro. 

Essas caixas não são atraídos para escala, pois quão grande é um número inteiro de bytes? Como grande agora? Quatro. E quão grande é um ponteiro? Quatro. Então, realmente, se fosse desenhar esta para escalar as duas caixas seria o mesmo tamanho. Neste caso, queremos inserir algo na lista encadeada. Assim você pode ver aqui em baixo estamos inserindo Nós cinco atravessar o lista ligada, encontrar onde cinco vai, e, em seguida, insira-o. 

Vamos quebrar esse baixo e ir um pouco mais devagar. Vou apontar para o conselho. Então, nós temos o nosso nó cinco que criamos em mallocs. Por que todos estão rindo? Brincadeirinha. OK. Então nós malloced cinco. Nós criamos este nó em outro lugar. Nós temo-lo pronto para ir. Começamos na frente nossa lista com dois. E nós queremos inserir de uma forma ordenada. 

Então, se nós vemos dois e queremos colocar em cinco anos, o que fazemos quando vemos algo menos do que nós? O quê? Queremos inserir cinco a este lista ligada, mantendo-classificada. Vemos o número dois. Então, o que fazemos? Marcus? 

AUDIÊNCIA: Chame o ponteiro para o próximo nó. 

JASON HIRSCHHORN: E por que vamos para o próximo? 

AUDIÊNCIA: Porque é a próximo nó na lista. E só sabemos que outro local. 

JASON HIRSCHHORN: E cinco é maior do que dois, em particular. Porque queremos mantê-lo ordenado. Assim, cinco é maior do que dois. Então, vamos passar para a próxima. E agora chegamos a quatro. E o que acontece quando chegarmos a quatro? 

Cinco é maior que quatro. Por isso, manter-se ir. E agora estamos em seis. E o que vemos às seis? Sim, Carlos? 

AUDIÊNCIA: Seis é maior que cinco. 

JASON HIRSCHHORN: Seis é maior do que cinco. Então é aí que queremos inserir cinco. No entanto, tenha em mente que, se só tem um ponteiro aqui - este é o nosso ponteiro extra que é percorrendo a lista. E nós estamos apontando para seis. Perdemos a noção do que vem antes das seis. Portanto, se queremos inserir algo em esta lista mantendo-classificado, que provavelmente precisará de quantos ponteiros? 

AUDIÊNCIA: Dois. 

JASON Hirschorn: Dois. Um para acompanhar a corrente um e um para acompanhar o anterior. Esta é apenas uma lista vinculada isoladamente. Ele só vai uma direção. Se tivéssemos uma lista duplamente vinculada, onde tudo estava apontando para a coisa depois que ele ea coisa antes, então nós não precisamos fazer isso. Mas neste caso nós não queremos perder a par do que vieram antes de nós, no caso precisamos inserir cinco em algum lugar no meio. Digamos que foram inserindo nove. O que aconteceria quando chegamos a oito? 

AUDIÊNCIA: Você teria que obter esse ponto nulo. Em vez de ter ponto nulo você teria adicionar um elemento e, em seguida, têm que apontam para nove. 

JASON Hirschorn: Exatamente. Então, nós temos oito. Chegamos ao fim da lista, porque este está apontando para null. E agora, em vez de ter que apontam para nulo, temos que apontar para o nosso novo nó. E vamos definir o ponteiro na nosso novo nó como nulo. Alguém tem alguma dúvida sobre como inserir? E se eu não me importo com manter a lista ordenada? 

AUDIÊNCIA: Cole-o na início ou o fim. 

JASON Hirschorn: Cole-o na o início ou o fim. Qual deles que devemos fazer? Bobby? Por que o fim? 

AUDIÊNCIA: Como o início já está preenchido. 

JASON Hirschorn: OK. O início já está cheio. Quem quiser argumentar contra Bobby. Marcus. 

AUDIÊNCIA: Bem, você provavelmente vai querer colá-la no início, porque caso contrário, se você colocá-lo em no final você tem que percorrer a lista inteira. 

JASON Hirschorn: Exatamente. Então, se estamos pensando em tempo de execução, o tempo de execução da inserção na extremidade Seria n, o tamanho deste. Qual é a grande O tempo de execução de inserção no início? Tempo constante. Então, se você não se importa em manter algo classificado, muito melhor apenas inserir no início desta lista. E isso pode ser feito em tempo constante. 

OK. Próxima operação é encontrar, o que outros - nós formulada isso como pesquisa. Mas vamos olhar pelo lista ligada por algum objeto. Vocês têm visto o código para pesquisar antes na palestra. Mas nós meio que fez com inserir, ou pelo menos a inserção algo ordenado. Você olha através, passando nó por nó, até encontrar o número que você está procurando. O que acontece se você chegar No final da lista? Digamos que eu estou procurando nove e eu atingir o fim da lista. O que vamos fazer? 

AUDIÊNCIA: Retorno falso? 

JASON Hirschorn: Return false. Nós não encontrá-lo. Se você chegar ao final da lista e você não encontrar o número que você está procurando, não está lá. Qualquer dúvida sobre encontrar? Se isto fosse uma lista ordenada, o que seria ser diferente para nossa busca? É. 

AUDIÊNCIA: Ele iria encontrar o primeiro valor que é maior do que aquele você está procurando e em seguida, retornar false. 

JASON Hirschorn: Exatamente. Então, se é uma lista ordenada, se chegarmos a algo que é maior do que o que nós estamos procurando, nós não precisa continuar até ao fim da lista. Podemos nesse ponto return false porque nós não vamos encontrá-lo. A questão agora é, nós já conversamos sobre manter listas ligadas ordenadas, mantendo-os indiferenciados. Isso vai ser algo que você está provavelmente vai ter que pensar sobre quando o problema de codificação definir cinco, se você escolher uma tabela hash com separado abordagem de encadeamento, que falaremos mais tarde. 

Mas vale a pena manter a lista ordenada e, em seguida, ser capaz de ter talvez pesquisas mais rápidas? Ou é melhor para inserir rapidamente algo em tempo de execução constante, mas, em seguida, ter mais tempo à procura? Isso é uma troca ali mesmo que você começa a decidir o que é mais apropriado para o seu problema específico. E não é necessariamente um resposta absolutamente certa. Mas certamente é uma decisão que você começa de fazer, e provavelmente bom para defender que, digamos, um comentário ou dois por você escolheu um sobre o outro. 

Finalmente, excluindo. Nós vimos a apagar. É semelhante a procurar. Nós olhamos para o elemento. Diga que estamos tentando apagar seis. Assim, encontramos seis aqui. A única coisa que nós temos que ter certeza de que fazer é que tudo o que está apontando para seis - como vemos na etapa dois para cá - tudo o que está apontando para seis necessidades para pular seis e agora ser alterado para tudo o que está apontando para seis. Não quero nunca órfãos o resto da nossa lista por esquecer de definir que ponteiro anterior. E então, às vezes, dependendo sobre o programa, eles só excluir este nó inteiramente. Às vezes você vai querer voltar o valor que está neste nó. Então é assim que apagar obras. Qualquer dúvida sobre apagar? 

AUDIÊNCIA: Então, se você estiver indo para apagar isso, se você acabou de usar livre porque presumivelmente foi malloced? 

JASON Hirschorn: Se você quiser libertar algo que é exatamente certo e você malloced ele. Digamos que queria retornar esse valor. Poderíamos voltar seis anos e, então, livre este nó e chamada gratuita sobre ele. Ou nós provavelmente ligue grátis primeiro e depois voltar seis. 

OK. Então, vamos passar para a prática de codificação. Vamos codificar três funções. O primeiro é chamado insert_node. Então você tem o código que eu lhe enviou, e se você está vendo isso, mais tarde, você pode acessar o código em linked.c no site do CS50. Mas em linked.c, há algum código de esqueleto que já está foi escrito para você. E depois há um par de funções você precisa escrever. 

Primeiro vamos escrever insert_node. E o que faz insert_node seja insere um número inteiro. E você está dando o inteiro em uma lista encadeada. E, em particular, é preciso para manter a lista ordenada do menor ao maior. Além disso, você não quer inserir todas as duplicatas. Por fim, como você pode ver insert_node retorna um bool. Então você está suposto que o usuário saiba se ou não a inserção era sucesso, retornando verdadeiro ou falso. No final deste programa - e para esta fase não é necessário se preocupar com liberando nada. Então tudo que você está fazendo é tomar um inteiro e inseri-lo em uma lista. 

Isso é o que eu estou pedindo para você fazer agora. Mais uma vez, no linked.c, onde todos têm, é o código de esqueleto. E você deve ver para o fundo a declaração da função amostra. No entanto, antes de ir para codificá-lo em C, eu altamente incentivá-lo a ir através dos passos que temos sido praticando a cada semana. Nós já passamos por uma imagem desta. Então você deve ter algum conhecimento de como isso funciona. Mas eu gostaria de incentivá-lo a escrever alguns pseudocódigo antes de mergulhar dentro E nós vamos passar por cima de pseudocódigo como um grupo. E, em seguida, uma vez que você tenha escrito o seu pseudocódigo, e uma vez que nós escrevemos o nosso pseudocódigo como um grupo, você pode ir para codificá-lo em C. 

Como um heads-up, a função insert_node é provavelmente a mais complicada de os três que vamos escrever, porque eu adicionou algumas restrições adicionais para sua programação, em particular, que você não está indo para inserir qualquer duplicatas e que a lista deve permanecer ordenada. Portanto, este é um programa não-trivial que você precisa para codificar. E por que você não tira 06:55 minutos, apenas para se trabalhar na pseudocódigo eo código. E então, vamos começar indo como um grupo. Novamente, se você tiver alguma dúvida basta levante a mão e eu vou chegar perto. . 

Também geralmente fazem estes - ou eu não explicitamente dizer que você pode trabalhar com pessoas. Mas, obviamente, eu altamente incentivá-lo, se você tiver dúvidas, pedir ao vizinho sentado ao seu lado ou até mesmo trabalhar com alguém outra coisa, se você quiser. Isto não tem que ser um indivíduo atividade em silêncio. 

Vamos começar com a escrita de alguns pseudocódigo na placa. Quem pode me dar a primeira linha de pseudocódigo para este programa? Para esta função, em vez - insert_node. Alden? 

AUDIÊNCIA: Então, a primeira coisa que fiz foi criar um novo ponteiro para o nó e I inicializado ele apontando para o mesmo coisa que lista está apontando. 

JASON Hirschorn: OK. Então, você está criando um novo ponteiro à lista, não para o nó. 

AUDIÊNCIA: Certo. É. 

JASON Hirschorn: OK. E então o que é que nós queremos fazer? O que há depois? E o nó? Nós não temos um nó. Nós só temos um valor. Se queremos inserir um nó, o que nós precisa fazer antes de nós pode até mesmo pensar em inseri-lo? 

AUDIÊNCIA: Oh, desculpe. precisamos malloc espaço para um nó. 

JASON Hirschorn: Excelente. Vamos fazer - OK. Não foi possível chegar a essa altura. OK. Nós estamos indo para ir para baixo, e depois estamos usando duas colunas. Eu não posso ir que - OK. Criar um novo nó. Você pode criar um outro ponteiro para listar ou você pode simplesmente usar a lista, uma vez que existe. Você realmente não precisa fazer isso. 

Então, criamos um novo nó. Grande. Isso é o que fazer primeiro. Qual é o próximo? 

AUDIÊNCIA: Espere. Devemos criar um novo nó agora ou devemos esperar para ter certeza de que não há nenhuma duplicata do nó na lista antes de criá-lo? 

JASON Hirschorn: Boa pergunta. Vamos manter isso para depois, porque a maior parte do tempo nós vamos estar criando um novo nó. Então, vamos manter isso aqui. Mas isso é uma boa pergunta. Se nós o criamos e vemos uma duplicata, o que deve o que fazemos antes de retornar? 

AUDIÊNCIA: Liberte-lo. 

JASON Hirschorn: Yeah. Provavelmente libertá-la. OK. O que vamos fazer depois que criar um novo nó? Annie? 

AUDIÊNCIA: Colocamos o número do nó? 

JASON Hirschorn: Exatamente. Nós colocamos o número - que malloc espaço. Vou deixar que tudo como uma linha. Mas você está certo. Nós malloc espaço, e, em seguida, vamos colocar o número de polegadas Podemos até mesmo definir o ponteiro parte dele para null. Isto é exatamente correto. E então o que dizer depois disso? Nós tirei esta imagem no quadro. Então, o que fazemos? 

AUDIÊNCIA: Vamos através da lista. 

JASON Hirschorn: Vá até a lista. OK. E o que é que vamos verificar se há em cada nó. Kurt, o que nós verificamos para em cada nó? 

AUDIÊNCIA: Veja se o valor de n esse nó é maior do que o valor de n do nosso nó. 

JASON Hirschorn: OK. Eu vou fazer - sim, OK. Por isso, é n - Eu vou dizer que se o valor for maior que esse nó, então o que fazemos? 

AUDIÊNCIA: Bem, então nós inserimos a coisa certa antes disso. 

JASON Hirschorn: OK. Então, se é maior do que isso, então nós queremos inserir. Mas queremos inseri-lo logo antes porque nós também precisaria ser manter o controle e, em seguida, do que era antes. Então, insira antes. Então, nós, provavelmente, perdeu alguma coisa anteriormente. Nós provavelmente precisam ser manter a par do que está acontecendo. Mas vamos voltar lá. Então, o valor é menor do que? Kurt, o que vamos fazer se valor é menor do que? 

AUDIÊNCIA: Então você só vai manter a menos que seja o último. 

JASON Hirschorn: Eu gosto disso. Então, vá para o próximo nó. A menos que seja o último - nós provavelmente estamos verificando para que nos termos de uma condição. Mas sim, próximo nó. E isso está ficando muito baixo, por isso vamos passar aqui. Mas se - pode todo mundo vê isso? Se somos iguais, o que fazemos? Se o valor que estamos tentando inserir é igual ao valor deste nó? Sim? 

AUDIÊNCIA: [inaudível]. 

JASON Hirschorn: Yeah. Dada esta - Marcus está certo. Poderíamos ter feito talvez algo diferente. Mas dado que nós criamos, aqui devemos libertar e depois voltar. Oh boy. Está melhor? Como é isso? OK. Livre e, em seguida, o que é que vamos voltar, [inaudível]? OK. Será que estamos perdendo alguma coisa? Então para onde estamos mantendo o controle do nó anterior? 

AUDIÊNCIA: Eu acho que ele iria depois de criar um novo nó. 

JASON Hirschorn: OK. Assim, no início provavelmente vamos - sim, podemos criar um ponteiro para uma nova nó, como um ponteiro nó anterior e um ponteiro nó atual. Então, vamos inserir esse aqui. Criar atual e anterior ponteiros para os nós. Mas quando é que vamos ajustar os ponteiros? Onde é que vamos fazer isso no código? Jeff? 

AUDIÊNCIA: - condições de valor? 

JASON Hirschorn: Qual um em particular? 

AUDIÊNCIA: Eu só estou confuso. Se o valor for maior do que esse nó, não quer dizer que você quer ir para o próximo nó? 

JASON HIRSCHHORN: Então se o nosso valor é maior do que o valor deste nó. 

AUDIÊNCIA: É, então você iria querer ir mais para baixo da linha, certo? 

JASON HIRSCHHORN: Certo. Então, nós não inseri-lo aqui. Se o valor for inferior a esse nó, em seguida, vamos para o próximo nó - ou então nós inserir antes. 

AUDIÊNCIA: Espere, o que é isso nó e que é valor? 

JASON HIRSCHHORN: Boa pergunta. Valor por esta definição de função é o que está dado. Assim, o valor é o número que está dado. Então, se o valor for menor do que isso nó, precisamos de tempo para inserir. Se o valor for maior do que esse nó, vamos para o próximo nó. E de volta à pergunta original, no entanto, onde - 

AUDIÊNCIA: Se o valor é maior que esse nó. 

JASON HIRSCHHORN: E assim O que fazemos aqui? Doce. Isso é correto. Eu só vou escrever ponteiros de atualização. Mas, sim, com o atual você atualizá-lo para apontar para a próxima. Qualquer outra coisa que está faltando? Então, eu estou indo para digitar essa código em gedit. E enquanto eu fizer isso, você pode ter um mais alguns minutos para trabalhar em codificação esta em C. 

Então, eu tenho a entrada do pseudocódigo. Uma nota rápida antes de começar. Podemos não ser capazes de completamente terminar esta em todos estas três funções. Há soluções corretas para eles que eu vou enviar e-mail para vocês depois de seção, e vai ser postado em CS50.net. Então eu não incentivá-lo a ir olhar para as seções. Encorajo-vos a tentar estes em seu possuir, e depois use o da prática problemas para conferir suas respostas. Estes foram concebidos para perto relacionar-se e aderir ao que você tem que fazer no set problema. Então eu encorajo-vos a praticar este em seu próprio país e, em seguida, usar o código para verificar suas respostas. Porque eu quero passar para o hash mesas em algum ponto na seção. Por isso, não pode ficar com ele todo. Mas vamos fazer o máximo que pudermos agora. 

OK. Vamos começar. Asam, como é que vamos criar um novo nó? 

AUDIÊNCIA: Você struct *. 

JASON HIRSCHHORN: Então nós têm que aqui em cima. Oh, desculpe. Você estava dizendo struct *. 

AUDIÊNCIA: E então [? tipo?] nó ou nodo c. 

JASON HIRSCHHORN: OK. Vou chamá-lo de NEW_NODE para que possamos ficar consistente. 

AUDIÊNCIA: E você deseja definir que a cabeça, o primeiro nó. 

JASON HIRSCHHORN: OK. Então, agora esta apontando para - de modo que este não criou um novo nó ainda. Isto é apenas apontando para o primeiro nó na lista. Como faço para criar um novo nó? Se eu precisar de espaço para criar um novo nó. Malloc. E como grande? 

AUDIÊNCIA: O tamanho da estrutura. 

JASON HIRSCHHORN: O tamanho da estrutura. E o que está a struct chamado? 

AUDIÊNCIA: Nó? 

JASON HIRSCHHORN: Node. Então malloc (sizeof (node)); dá-nos espaço. E é nessa linha - uma coisa é incorreta nesta linha. É NEW_NODE um ponteiro para um struct? Esse é um nome genérico. O que é - nó, exatamente. É um nó *. E o que vamos fazer logo após nós malloc algo, Asan? Qual é a primeira coisa que fazemos? E se não funcionar? 

AUDIÊNCIA: Oh, verificar se ele aponta para o nó? 

JASON HIRSCHHORN: Exatamente. Então, se você é igual a NEW_NODE iguais nulo, o que vamos fazer? Isso retorna um bool, essa função. Exatamente. Parece bom. Alguma coisa a acrescentar aí? Nós vamos adicionar coisas no final. Mas que até agora parece ser bom. Criar indicadores atuais e anteriores. Michael, como eu faço isso? 

AUDIÊNCIA: Você teria para fazer um nó *. Você teria que fazer um não para NEW_NODE mas para o nós já temos. 

JASON HIRSCHHORN: OK. Assim, o nó atual em que estamos. Vou ligar para que curr. Tudo bem. Nós decidimos que queremos manter dois, porque precisamos saber o que está à sua frente. O que eles são inicializados para? 

AUDIÊNCIA: O seu valor em nossa lista. 

JASON HIRSCHHORN: Então, qual é o primeira coisa em nossa lista? Ou como é que sabemos onde o início da nossa lista é? 

AUDIÊNCIA: Não é passado para a função? 

JASON HIRSCHHORN: Certo. Ela foi aprovada em aqui. Então, se ele é passado para a função, o início da lista, o que devemos definir corrente igual? 

AUDIÊNCIA: List. 

JASON HIRSCHHORN: List. Isto é exatamente correto. Agora que tem o endereço de o início da nossa lista. E o que dizer anterior? 

AUDIÊNCIA: Lista menos um? 

JASON HIRSCHHORN: Há nada antes dele. Então o que podemos fazer para significar nada? 

AUDIÊNCIA: Null. 

JASON HIRSCHHORN: Yeah. Isso soa como uma boa idéia. Perfeito. Obrigado. Vá até a lista. Constantino, quanto tempo é que vamos para percorrer a lista? 

AUDIÊNCIA: até chegarmos nulo. 

JASON HIRSCHHORN: OK. Portanto, se, ao mesmo tempo, por loop. O que estamos fazendo? 

AUDIÊNCIA: Talvez um loop? 

JASON HIRSCHHORN: Vamos fazer um loop for. OK. 

AUDIÊNCIA: E dizemos para - até que o ponteiro atual não é igual a nulo. 

JASON HIRSCHHORN: Então, se sabemos que o condição, como podemos escrever um loop baseado fora dessa condição. Que tipo de laço que devemos usar? 

AUDIÊNCIA: While. 

JASON HIRSCHHORN: Yeah. Isso faz mais sentido com base fora do que você disse. Se nós apenas quer ir para nós seria só sei que coisa, não faria sentido de fazer um loop while. Embora atual não é igual a zero, se o valor for inferior a esse nó. Akshar, dá-me dessa linha. 

AUDIÊNCIA: Se a corrente-> n n menor que o valor. Ou reverter isso. Mudar esse suporte. 

JASON HIRSCHHORN: Desculpe. 

AUDIÊNCIA: Alterar o suporte. 

JASON HIRSCHHORN: Então, se é maior do que o valor. Porque isso é confuso com o comentário acima, eu vou fazer isso. Mas sim. Se o nosso valor é menor do que isso nó, o que vamos fazer? Oh. Tenho-o aqui. Inserir antes. OK. Como fazemos isso? 

AUDIÊNCIA: É-me ainda? 

JASON HIRSCHHORN: Yeah. 

AUDIÊNCIA: You - NEW_NODE-> seguinte. 

JASON HIRSCHHORN: Então, qual é que vai ser igual? 

AUDIÊNCIA: Vai igual atual. 

JASON HIRSCHHORN: Exatamente. E assim o outro - o que mais precisamos para atualizar? 

AUDIÊNCIA: Verifique se passado é igual a nulo. 

JASON HIRSCHHORN: se prev - por isso, se prev igual nulo. 

AUDIÊNCIA: Isso significa que ele vai para se tornar a cabeça. 

JASON HIRSCHHORN: Isso significa que tornou-se a cabeça. Então o que fazemos? 

AUDIÊNCIA: Fazemos cabeça é igual NEW_NODE. 

JASON HIRSCHHORN: Cabeça é igual NEW_NODE. E por cabeça aqui, não lista? 

AUDIÊNCIA: Porque a cabeça é uma organização global variável, que é o ponto de partida. 

JASON HIRSCHHORN: Sweet. OK. E - 

AUDIÊNCIA: Então você mais prev-> próximo é igual NEW_NODE. E então você retornar true. 

JASON HIRSCHHORN: Onde montamos final NEW_NODE? 

AUDIÊNCIA: eu - Eu definir que no início. 

JASON HIRSCHHORN: Então o que linha? 

AUDIÊNCIA: Após a instrução if verificando se ele é conhecido. 

JASON HIRSCHHORN: Aqui? 

AUDIÊNCIA: Eu faria NEW_NODE-> n igual valor. 

JASON HIRSCHHORN: Parece bom. Provavelmente faz sentido - nós não precisa saber o que estamos na lista porque estamos lidando apenas com uma lista. Assim, uma declaração de função melhor para isto é só para se livrar dessa inteiramente e apenas inserir um valor na cabeça. Nós nem sequer precisa de saber que lista que está dentro Mas vou mantê-la por agora e então alterá-lo após a atualização os slides e código. Assim que parece ser bom para agora. Se o valor - que pode fazer isso online? Se - o que fazemos aqui, Noah. 

AUDIÊNCIA: Se o valor é maior que curr-> n - 

JASON HIRSCHHORN: Como fazer vamos para o próximo nó? 

AUDIÊNCIA: Curr-> n é igual a NEW_NODE. 

JASON HIRSCHHORN: Então n é que parte da estrutura? O inteiro. E NEW_NODE é um apontador para um nó. Então, o que parte do curr devemos atualizar? Se não for n, então o que é a outra parte? Noé, que é a outra parte. 

AUDIÊNCIA: Oh, ao lado. 

JASON HIRSCHHORN: Next, exatamente. Exatamente. Em seguida é a certa. E o que mais precisamos para atualizar, Noah? 

AUDIÊNCIA: Os ponteiros. 

JASON HIRSCHHORN: Então atualizamos atual. 

AUDIÊNCIA: Prev-> seguinte. 

JASON HIRSCHHORN: Yeah. OK, vamos fazer uma pausa. Quem pode nos ajudar aqui? Manu, o que devemos fazer? 

AUDIÊNCIA: Você tem que definir ele igual a curr-> seguinte. Mas fazer isso antes da linha anterior. 

JASON HIRSCHHORN: OK. Mais alguma coisa? Akshar. 

AUDIÊNCIA: Eu não acho que você é destina-se a alterar curr-> seguinte. Eu acho que você está destinado a fazer iguais curr curr-> ao lado de ir para o próximo nó. 

JASON HIRSCHHORN: So sorry, onde? Em qual linha? Esta linha? 

AUDIÊNCIA: Yeah. Faça curr igual curr-> seguinte. 

JASON HIRSCHHORN: Então, isso é correto porque a corrente é uma ponteiro para um nó. E nós queremos que ele aponta para o próximo nó do que está recebendo atualmente apontado. Curr si tem um lado. Mas, se fôssemos atualizar curr.next, nós seria atualizar a nota real em si, não onde esta ponteiro estava apontando. E sobre esta linha, no entanto. Avi? 

AUDIÊNCIA: Prev-> next igual curr. 

JASON HIRSCHHORN: Então, novamente, se prev é um ponteiro para um nó, prev-> próximo é o ponteiro efectiva no nó. Portanto, esta seria a atualização de um ponteiro em um nó para curr. Nós não queremos para atualizar um apontador num nó. Queremos atualizar anterior. Então, como vamos fazer isso? 

AUDIÊNCIA: Seria apenas prev. 

JASON HIRSCHHORN: Certo. Ant é um apontador para um nó. Agora, estamos mudando-o para um novo ponteiro para um nó. OK Vamos descer. Finalmente, esta última condição. Jeff, o que fazemos aqui? 

AUDIÊNCIA: Se o valor é igual a curr-> n. 

JASON HIRSCHHORN: Desculpe. Oh meu Deus. O quê? Valor == curr-> n. O que vamos fazer? 

AUDIÊNCIA: Você iria libertar o nosso NEW_NODE, e então você retornar false. 

JASON HIRSCHHORN: Isto é o que temos escrito até agora. Alguém tem alguma coisa a acrescentar antes de fazer? OK. Vamos tentar. Controle poderá chegar ao final de uma função não-vazio. Avi, o que está acontecendo? 

AUDIÊNCIA: Você deve colocar retorno verdadeiro fora do loop while? 

JASON HIRSCHHORN: Eu não sei. Você me quer? 

AUDIÊNCIA: Não importa. Não. 

JASON HIRSCHHORN: Akshar? 

AUDIÊNCIA: Eu acho que você quis colocar retorno falso no final do loop while. 

JASON HIRSCHHORN: Então, onde você quer que ele vá? 

AUDIÊNCIA: Como fora do loop while. Então, se você sair do loop while que meios que você já chegou ao fim e nada aconteceu. 

JASON HIRSCHHORN: OK. Então, o que fazemos aqui? 

AUDIÊNCIA: Você retorna falso lá também. 

JASON HIRSCHHORN: Oh, nós fazê-lo em ambos os lugares? 

AUDIÊNCIA: Yeah. 

JASON HIRSCHHORN: OK. Vamos? Oh meu Deus. Sinto muito. Peço desculpas para a tela. É uma espécie de surtando sobre nós. Então, escolha uma opção. Zero, por código, sai do programa. Um insere algo. Vamos inserir três. A inserção não foi bem sucedida. Vou imprimir. Eu não tenho nada. OK. Talvez tenha sido apenas um acaso. Insira um. Não bem sucedida. OK. Vamos percorrer GDB muito rapidamente para verificar o que está acontecendo. 

Lembre-gdb. / O nome do seu programa nos deixa em GDB. Isso é um monte de lidar? O piscar? Provavelmente. Feche os olhos e tomar alguma profundidade respirações se você ficar cansado de olhar para ele. Estou em GDB. Qual é a primeira coisa que eu faço em GDB? Temos que descobrir o que está acontecendo aqui. Vamos ver. Temos seis minutos para a figura o que está acontecendo. Quebre principal. E então o que eu faço? Carlos? Execute. OK. Vamos escolher uma opção. E o que fazer N? Avançar. É. 

AUDIÊNCIA: Você não mencionou - você não disse que a cabeça, que era inicializado com nulo no início. Mas eu pensei que você disse que estava bem. 

JASON HIRSCHHORN: Vamos - vamos olhar em GDB, e depois vamos voltar. Mas parece que você já tem algumas idéias sobre o que está acontecendo. Por isso, queremos inserir algo. OK. Temos inserir. Por favor insira um int. Nós vamos inserir três. E então eu estou nessa linha. Como faço para ir iniciar a depuração função da inserção conhecido? Oh meu Deus. Isso é um monte. É que pirando muito? 

AUDIÊNCIA: Ah, ele morreu. 

JASON HIRSCHHORN: Eu só puxou-o para fora. OK. 

AUDIÊNCIA: Talvez seja o a outra extremidade do fio. 

JASON HIRSCHHORN: Uau. Assim, a linha de fundo - o que você disse? 

AUDIÊNCIA: Eu disse a ironia de técnico dificuldades nesta classe. 

JASON HIRSCHHORN: Eu sei. Se eu tivesse o controle sobre essa parte. [Inaudível] Isso soa muito bem. Por que vocês não começar a pensar sobre o que poderíamos ter feito de errado, e vamos estar de volta em 90 segundos. 

Avica, eu vou perguntar a você como ir insert_node dentro de depurá-lo. Então é aqui que deixamos para trás. Como faço para entrar insert_node, Avica, para examinar o que está acontecendo? O comando GDB? Pausa não me levaria para dentro. A Marquise sabe? 

AUDIÊNCIA: O quê? 

JASON HIRSCHHORN: Qual comando GDB Eu uso para ir dentro dessa função? 

AUDIÊNCIA: Step? 

JASON HIRSCHHORN: Step via S. Isso me leva para dentro. OK. NEW_NODE mallocing algum espaço. Isso tudo parece que vai. Vamos examinar NEW_NODE. Ele tem algum endereço de memória. Vamos verificar - isso é tudo correto. Então, tudo aqui parece estar funcionando corretamente. 

AUDIÊNCIA: Qual é a diferença entre P e exibição? 

JASON HIRSCHHORN: P está para impressão. E assim que você está perguntando o que é o diferença entre isso e isso? Nesse caso, nada. Mas geralmente há algumas diferenças. E você deve olhar no manual do GDB. Mas neste caso, nada. Nós tendemos a usar impressão, porém, porque nós não precisamos de fazer muito mais do que imprimir um único valor. 

OK. Portanto, estamos na linha 80 do nosso código, configuração nó * curr igual a lista. Vamos imprimir curr. Ele é igual a lista. Doce. Espere. Ele é igual a alguma coisa. Isso não parece certo. Lá vamos nós. É porque em GDB, certo, se é a linha que você está nele não foi executado ainda. Então, você precisa realmente digitar próximo para executar a linha antes de ver seus resultados. Então aqui estamos nós. Nós apenas executou esta linha, anterior é igual a nulo. Então, novamente, se imprimir anterior não vamos ver nada estranho. Mas se nós realmente executar que linha, então vamos ver que a referida linha de trabalhado. 

Portanto, temos curr. Essas são boas. Certo? Agora estamos nessa linha aqui. Enquanto curr não é igual a nulo. Bem, o que faz curr iguais? Nós só vimos ele igualou nulo. Imprimimos-lo. Vou imprimi-lo novamente. Assim é que, enquanto laço vai executar? 

AUDIÊNCIA: Não. 

JASON HIRSCHHORN: Então, quando eu digitei que linha, você vê que pulou todo o caminho até o fundo, retornar false. E então nós estamos indo para retornar false e voltar para o nosso programa e eventualmente, imprimir, como vimos, a inserção não foi bem sucedida. Então, alguém tem alguma idéia sobre o que o que precisamos fazer para corrigir isso? Vou esperar até que eu veja um par de mãos levantadas. Nós não executar este. Tenha em mente, este foi o primeiro coisa que estávamos fazendo. Eu não vou fazer um casal. Eu vou fazer alguns. Porque um casal significa dois. Eu vou esperar por mais de dois. 

A primeira inserção, curr, por padrão é igual a nulo. E este laço só executa curr se não é nulo. Então, como posso resolver isso? Eu vejo três mãos. Eu vou esperar por mais de três. Marcus, o que você acha? 

AUDIÊNCIA: Bem, se você precisar dele para executar mais de uma vez, você só alterá-lo para um loop do-while. 

JASON HIRSCHHORN: OK. Será que isso resolve o nosso problema, então? 

AUDIÊNCIA: Neste caso, não por causa de o facto de que a lista está vazia. Então provavelmente você só precisa adicionar uma declaração de que se o loop em seguida, tem de estar na extremidade da da lista, em que ponto você pode apenas inseri-lo. 

JASON HIRSCHHORN: Eu gosto disso. Isso faz sentido. Se o circuito sai - porque ele vai retornar false aqui. Então, se o loop, então estamos em No final da lista, ou talvez o início de uma lista, se não há nada no , o que é o mesmo que o fim. Então, agora queremos inserir alguma coisa aqui. Então, como parece que o código, Marcus? 

AUDIÊNCIA: Se você já tem o nó malloced, você poderia simplesmente dizer NEW_NODE-> next igual a nulo porque tem que ser no final. Ou NEW_NODE-> next igual a nulo. 

JASON HIRSCHHORN: OK. Desculpe. NEW_NODE-> next igual a nulo porque estamos no final. Isso não colocá-lo dentro Como é que vamos colocá-lo na lista? Certo. Isso é só configurá-lo igual a. Não como nós, na verdade, colocá-lo na lista? O que está apontando para o fim da lista? 

AUDIÊNCIA: Head. 

JASON HIRSCHHORN: Desculpe? 

AUDIÊNCIA: Cabeça está apontando para o fim da lista. 

JASON HIRSCHHORN: Se não há nada em a lista, a cabeça está apontando para a fim da lista. Então, que vai trabalhar para a primeira inserção. E se há um par coisas na lista? Do que nós não queremos para definir cabeça igual NEW_NODE. O que queremos fazer lá? Sim? Provavelmente anterior. Será que funciona? Lembre-se que é apenas anterior um ponteiro para um nó. E anterior é uma variável local. Portanto, esta linha vai definir uma variável local, anterior, igual ou apontando para este novo nó. Isso realmente não vai colocá-lo na nossa lista, no entanto. Como é que vamos colocá-lo em nossa lista? Akchar? 

AUDIÊNCIA: Eu acho que você fazer current-> seguinte. 

JASON HIRSCHHORN: OK. curr-> seguinte. Então, novamente, a única razão que nós estamos para baixo aqui é, o que faz de corrente igual? 

AUDIÊNCIA: Igual nulo. 

JASON HIRSCHHORN: E então o que acontece se o fizermos null-> next? O que vai ficar? Nós vamos ter uma falha de segmentação. 

AUDIÊNCIA: Do curr igual nulo. 

JASON HIRSCHHORN: Isso é a mesma coisa como prev, no entanto, porque não há uma variável local que estamos definindo igual a este novo nó. Vamos voltar à nossa imagem de inserir algo. Digamos que está inserindo no final da lista, por isso aqui. Nós temos um ponteiro atual que é apontando para nulo e um ponto anterior que está apontando para 8. Então o que precisamos atualizar, Avi? 

AUDIÊNCIA: Anterior-> next? 

JASON HIRSCHHORN: Anterior-> próximo é o que queremos atualizar porque isso vai realmente inseri-lo no No final da lista. Nós ainda temos um bug, no entanto, que vamos correr em. O que é isso bug? Sim? 

AUDIÊNCIA: Vai voltar falsa neste caso? 

JASON HIRSCHHORN: Ah, é é vai retornar false. Mas há um outro bug. Então, vamos precisar para colocar em return true. 

AUDIÊNCIA: O anterior ainda igual nula no topo da lista de? 

JASON HIRSCHHORN: ainda Então anterior é igual a nulo no início. Então, como podemos superar isso? Sim? 

AUDIÊNCIA: Eu acho que você pode fazer uma verificação antes do loop while para ver se é uma lista vazia. 

JASON HIRSCHHORN: OK. Então vamos aqui. Faça uma verificação. Se - 

AUDIÊNCIA: Então, se a cabeça é igual é igual a nulo. 

JASON HIRSCHHORN: Se a cabeça é igual é igual a null - que vai nos dizer se é uma lista vazia. 

AUDIÊNCIA: E então você fazer a cabeça é igual a novo. 

JASON HIRSCHHORN: Cabeça é igual NEW_NODE? E o que mais precisamos fazer? 

AUDIÊNCIA: E então você retornar true. 

JASON HIRSCHHORN: Não é bem assim. Estamos perdendo uma etapa. 

AUDIÊNCIA: NEW_NODE próximo tem que apontar para null. 

JASON HIRSCHHORN: Exatamente, Alden. E então podemos retornar true. OK. Mas ainda é uma boa idéia para fazer as coisas no final da lista, direita? Tudo bem. Nós ainda pode realmente começar para o fim da lista. Então é esse código bem se estamos no fim da lista e há alguns coisas na lista? Certo? Porque ainda temos a idéia de Marcus. Podemos sair deste ciclo, porque estamos no fim da lista. Portanto, nós queremos ainda este código aqui em baixo? 

AUDIÊNCIA: sim. 

JASON HIRSCHHORN: Yeah. E o que nós precisamos mudar isso? Verdadeiro. Será que um bom som a todos até agora? Alguém tem alguma - Avi, você tem algo a acrescentar? 

AUDIÊNCIA: Não. 

JASON HIRSCHHORN: OK. Então, nós fizemos algumas mudanças. Nós fizemos essa verificação antes de nós entrou para uma lista vazia. Então, nós temos tido o cuidado de uma lista vazia. E aqui nós tomamos o cuidado de inserir algo no fim da lista. Então, parece que essa tomada loop while conta das coisas no meio, em algum lugar da lista, se houver são coisas na lista. 

OK. Vamos executar este programa novamente. Não bem sucedida. 

AUDIÊNCIA: Você não fazê-lo. 

JASON HIRSCHHORN: Oh, Eu não fiz isso. Bom ponto, Michael. Vamos adicionar um make ligados. Linha 87 há um erro. Linha 87. Alden, esta foi a linha que você me deu. O que há de errado? 

AUDIÊNCIA: Tem que ser como nulo. 

JASON HIRSCHHORN: Excelente. Exatamente. Deve ser nulo. Vamos fazer de novo. Compilar. OK. Vamos inserir três. A inserção foi bem-sucedida. Vamos imprimi-lo. Oh, se pudéssemos verificar. Mas nós não fizemos a imprimir função ainda. Vamos entrar outra coisa. O que devemos entrar? 

AUDIÊNCIA: Sete. 

JASON HIRSCHHORN: Seven? 

AUDIÊNCIA: sim. 

JASON HIRSCHHORN: Temos uma falha seg. Então, nós temos um, mas nós claramente não pode ficar dois. É 05:07. Assim nós poderíamos depurar este por três minutos. Mas eu vou deixar-nos aqui e seguir em frente para hash tabelas. Mas, novamente, as respostas para este código Vou enviar e-mail para você daqui a pouco. Estamos muito próximos a ele. Eu altamente incentivá-lo a descobrir o que está acontecendo aqui e corrigi-lo. Então, eu vou enviar e-mail que você este código como bem além da solução - provavelmente, a solução mais tarde. Primeiro este código. 

A outra coisa que eu quero fazer antes de nós acabamento é que não liberaram nada. Então, eu quero mostrar o que valgrind parece. Se corrermos limites valgrind em nosso programa,. / ligada. Novamente, de acordo com esta corrediça, nós deve executar valgrind com algum tipo de opção, neste caso - Check-vazamento = full. Então vamos escrever valgrind - Check-vazamento = full. Portanto, este será executado valgrind em nosso programa. E agora o programa realmente funciona. Então, vamos executá-lo apenas como antes, colocar algo dentro Eu vou colocar em três. Isso funciona. Eu não estou indo para tentar colocar em alguma coisa outra coisa, porque nós vamos obter um falso seg nesse caso. Então, eu só vou sair. 

E agora você vê aqui vazar e resumo heap. Estas são as coisas boas que você queira dar uma olhada. Assim, o resumo pilha - diz, em uso na saída - oito bytes em um bloco. Esse bloco é o nó que malloced. Michael, você disse antes de um nó é de oito picadas porque tem o número inteiro eo ponteiro. Então, esse é o nosso nó. E então ele diz que nós usamos malloc sete vezes e que libertou algo seis vezes. Mas nós nunca chamado de livre, então eu não tenho idéia do que isso está falando. 

Mas basta dizer que, quando o seu corridas do programa, malloc está sendo chamado em alguns outros lugares que nós não precisa se preocupar. Então malloc provavelmente foi chamado em alguns lugares. Não precisa se preocupar onde. Mas isso é realmente nós. Esta primeira linha é a gente. Deixamos esse bloco. E você pode ver que aqui no resumo vazamento. Ainda alcançável - oito bytes em um bloco. Isso significa que a memória - que vazaram essa memória. Definitivamente perdida - algo é perdido para sempre. Geralmente, você não vai ver nada lá. Ainda acessível é geralmente onde você vai ver as coisas, onde você vai querer olhar para ver o que o código que deveria ter libertado, mas você se esqueceu de libertar. 

E então, se este não foi o caso, se fizemos tudo livre, podemos verificar isso. Vamos executar o programa não colocar em qualquer coisa. Você vai ver aqui em baixo em uso na saída - zero bytes de zero de blocos. Isso significa que não tinha mais nada quando este programa saiu. Então, antes de virar pset6, execute valgrind e certifique-se que você não tem qualquer vazamentos de memória em seu programa. Se você tiver alguma dúvida com valgrind, fique à vontade para chegar. Mas isto é como você usá-lo. Muito simples - veja se você ter em uso na saída - quaisquer bytes em todos os blocos. 

Então nós estávamos trabalhando no nó de inserção. Eu tinha duas outras funções aqui - imprimir nós e nós livres. Novamente, essas são funções que são vai ser bom para você praticar porque eles vão ajudá-lo não apenas com estes exercícios de amostra, mas também sobre o conjunto de problemas. Eles mapeiam em bem de perto para as coisas você vai ter que fazer no conjunto de problemas. Mas eu quero ter certeza tocamos em tudo. E tabelas de hash também são cruciais para o que estamos fazendo na seção deste semana - ou no conjunto problema. 

Então, nós estamos indo para terminar a seção falando de tabelas de hash. Se você notar que fiz um mesinha hash. Isso não é o que nós estamos falando sobre, no entanto. Estamos falando de um diferente tipo de tabelas de hash. E em seu núcleo, uma tabela hash nada mais é do que uma disposição mais uma função hash. Vamos falar um pouco só para certificar-se de todo mundo entende o que é um função hash é. E eu estou te dizendo agora que é nada mais do que duas coisas - uma matriz e uma função de hash. E aqui estão os passos através de que esta opera. 

Não é a nossa matriz. Não é nossa função. Em particular, as funções de hash precisa fazer um par de coisas com isso. Eu vou falar especificamente sobre este conjunto de problemas. Ele provavelmente vai tomar em um string. E o que é que vai voltar? Que tipo de dados? Alden? Sua função hash retornar? Um inteiro. Então é isso que o hash tabela consiste em - uma mesa em forma de leque e uma função de hash. Como ele funciona? Ele funciona em três etapas. Nós dar-lhe uma chave. Neste caso, nós vamos dar-lhe uma corda. Chamamos a função hash por uma etapa na chave e temos um valor. 

Especificamente, vamos dizer obtemos um número inteiro. Esse número inteiro, não são muito específicos limites para o número inteiro que pode ser. Neste exemplo, a matriz é de tamanho três. Então, o que os números podem ser inteiro. Qual é o intervalo de valores válidos para que inteiro, o tipo de retorno desse de hash função? Zero, um e dois. O ponto de partida da função hash é descobrir o lugar na matriz onde a nossa chave está indo. Há apenas três possíveis lugares aqui - zero, um ou dois. Portanto, esta função melhor retorno zero, um ou dois. Alguns indice válido neste array. 

E, em seguida, dependendo de onde ele retorna, você pode ver que há disposição aberto entre parênteses o valor. Isso é onde colocamos a chave. Por isso, jogar a abóbora, sairmos zero. No conjunto do suporte 0, colocamos abóbora. Nós jogamos em gatos, saímos um. Nós colocamos em um gato. Colocamos em aranha. Saímos duas. Colocamos aranha em suporte disposição dois. Seria tão bom se funcionou assim. Mas, infelizmente, como veremos, é um pouco mais complicado. 

Antes de chegar lá, todas as perguntas sobre o básico set-up de uma tabela hash? Esta é uma imagem de exactamente o que chamou a bordo. Mas desde que o desenhou no quadro, eu Não vou entrar em-lo ainda mais. Essencialmente chaves, a caixa preta mágica - ou, neste caso, a caixa azul - de um função hash coloca-los em baldes. E, neste exemplo, estamos não colocar o nome. Estamos colocando o telefone associado número do nome no balde. Mas você poderia muito bem apenas colocar o nome no balde. 

Este é apenas um retrato do que traçamos no tabuleiro. Temos potenciais armadilhas, no entanto. E há dois em particular slides que eu quero passar por cima. O primeiro é sobre uma função hash. Então eu fiz a pergunta, o que faz uma boa função hash? Dou duas respostas. A primeira é que não é determinista. No contexto das funções hash, o que isso significa? Sim? 

AUDIÊNCIA: Pode encontrar o índice em tempo constante? 

JASON HIRSCHHORN: Isso não é o que ela significa. Mas isso é um bom palpite. Alguém mais tem um palpite para que isso significa? Que uma boa função de hash é determinista? Annie? 

AUDIÊNCIA: É uma chave só pode ser mapeado a um lugar na tabela de hash. 

JASON HIRSCHHORN: Isso é exatamente correto. Toda vez que você colocar na abóbora, ele sempre retorna zero. Se você colocar em abóbora e sua mistura função retorna zero, mas tem um probabilidade de voltar algo outra coisa maior que zero - talvez por isso, às vezes, pode retornar um ou duas vezes - que não é uma boa função hash. Você está absolutamente certo. Sua função hash deve retornar o mesmo número inteiro exacto, neste caso, para a mesma seqüência exata. 

Talvez ele retorna o mesmo número inteiro exato para a mesma seqüência exata independentemente da capitalização. Mas, nesse caso, ainda é determinista, porque várias coisas são mapeados para o mesmo valor. Isso é bom. Enquanto existe apenas um saída para uma dada entrada. 

OK. A segunda coisa é que ele retorna índices válidos. Trouxemos-se que antes. Esta função hash - oh boy - uma função de hash deve retornar índices válidos. Então diga - vamos voltar a este exemplo. Minha função hash conta até as letras da palavra. Essa é a função hash. E retorna esse número inteiro. Então, se eu tenho a palavra A, é vai voltar um. E vai colocar um aqui. E se eu colocar a palavra morcego? Vai voltar três. Onde o morcego ir? 

Não serve. Mas ele precisa ir a algum lugar. Esta é a minha tabela hash afinal de contas, e tudo precisa ir a algum lugar. Então, para onde deve ir morcego? Quaisquer pensamentos? Adivinha? Bons palpites? 

AUDIÊNCIA: Zero. 

JASON HIRSCHHORN: Porque a zero? 

AUDIÊNCIA: Porque três módulo três é igual a zero? 

JASON HIRSCHHORN: Three módulo de três é igual a zero. Isso é um grande palpite, e isso é correto. Portanto, neste caso deveria provavelmente ir a zero. Assim, uma boa maneira de garantir que esse hash função só retorna índices válidos é modulo para isto por o tamanho da tabela. Se você quer que este modulo retornos três, você está sempre indo para obter algo entre zero, um e dois. E se isso sempre retorna sete, e você sempre modulo por três, você está sempre vai ficar a mesma coisa. 

Então, ainda é determinística se você modulo. Mas isso vai garantir que você nunca conseguir alguma coisa - uma indústria inválido. Geralmente, esse módulo deve acontecer dentro de sua função de hash. Assim você não precisa se preocupar com isso. Você só pode garantir que este é um indice válido. Qualquer dúvida sobre este armadilha potencial? 

OK. E lá vamos nós. Próxima armadilha potencial, e este é um dos grandes. E se duas chaves mapa para o mesmo valor de? Portanto, há duas maneiras de lidar com isso. O primeiro é chamado linear sondagem, o que eu sou não vai passar por cima. Mas você deve estar familiarizado com a forma que funciona e o que é. 

A segunda eu vou passar por cima porque esta é a única que muitos pessoas provavelmente vai acabar decidindo para usar em seu conjunto de problemas. Claro, você não precisa. Mas, para o conjunto de problemas, muitas pessoas tendem a optar por criar uma tabela hash com encadeamento separado para implementar seu dicionário. Então, nós estamos indo ir sobre o que isso significa para criar uma tabela hash com encadeamento separado. 

Então eu coloquei na abóbora. Ele retorna zero. E eu coloquei abóbora aqui. Então eu coloquei em - o que é outra coisa Halloween-temático? 

AUDIÊNCIA: Candy. 

JASON HIRSCHHORN: doces! Isso é um grande homem. Eu coloquei em doces, e doces também me dá zero. O que eu faço? Alguma ideia? Porque você toda a sorte de conhecer o encadeamento separado é. Então, alguma idéia do que fazer? É. 

AUDIÊNCIA: Colocar a corda na verdade, na tabela de hash. 

JASON HIRSCHHORN: Então nós vamos desenhar a boa idéia por aqui. OK. 

AUDIÊNCIA: Tenha o hashtable [Inaudível] o ponteiro que aponta para o início de uma lista. E então, abóbora ser o primeiro valor nessa lista ligada e doces ser o segundo valor nessa lista encadeada. 

JASON HIRSCHHORN: OK. Marcus, que foi excelente. Eu vou quebrar esse baixo. Marcus diz não substituir abóbora. Isso seria ruim. Não coloque doces em outro lugar. Vamos colocá-los a zero. Mas estamos indo para lidar com colocá-los em zero por criação de uma lista de zero. E vamos criar uma lista de tudo o que mapeada para zero. E a melhor maneira que aprendemos a criar uma lista que pode aumentar e diminuir dinamicamente não está dentro outra matriz. Portanto, não um array multi-dimensional. Mas apenas criar uma lista ligada. 

Então, o que ele propôs - Eu estou indo para obter um novo - é criar uma matriz com ponteiros, uma matriz de ponteiros. OK. Qualquer idéia ou sugestão que o tipo desta ponteiros deve ser? Marcus? 

AUDIÊNCIA: Ponteiros para - 

JASON HIRSCHHORN: Porque você disse uma lista ligada, por isso - 

AUDIÊNCIA: ponteiros do nó? 

JASON HIRSCHHORN: ponteiros nó. Se as coisas em nossa ligado lista são os nós, então eles deve ser ponteiros do nó. E o que eles igual inicialmente? 

AUDIÊNCIA: Null. 

JASON HIRSCHHORN: Null. Portanto, não é a nossa coisa vazia. Abóbora retorna zero. O que vamos fazer? Caminhe comigo através dela? Na verdade, Marcus já me deu. Alguém me atravessá-la. O que fazemos quando - este é muito parecido com o que nós estávamos fazendo. Avi. 

AUDIÊNCIA: Eu vou dar um palpite. Então, quando você começa doces. 

JASON HIRSCHHORN: Yeah. Bem, nós temos de abóbora. Vamos buscar o nosso primeiro. Temos abóbora. 

AUDIÊNCIA: OK. Abóbora retorna zero. Então você colocá-lo nisso. Ou, na verdade, você colocá-lo na lista encadeada. 

JASON HIRSCHHORN: Como é que nós colocá-lo na lista ligada? 

AUDIÊNCIA: Oh, a sintaxe real? 

JASON HIRSCHHORN: Basta andar - dizer mais. O que vamos fazer? 

AUDIÊNCIA: Você acabou de inserir ele como o primeiro nó. 

JASON HIRSCHHORN: OK. Então, nós temos o nosso nó, abóbora. E agora como faço para inseri-lo? 

AUDIÊNCIA: Você atribui lo para o ponteiro. 

JASON HIRSCHHORN: Qual ponteiro? 

AUDIÊNCIA: O ponteiro no zero. 

JASON HIRSCHHORN: Então, onde faz esse ponto? 

AUDIÊNCIA: Para nulo agora. 

JASON HIRSCHHORN: Bem, ele está apontando para null. Mas eu estou colocando em abóbora. Então, onde ele deve apontar? 

AUDIÊNCIA: Para abóbora. 

JASON HIRSCHHORN: Para abóbora. Exatamente. Então, isso aponta para abóbora. E onde é que este ponteiro no ponto de abóbora? Para 

AUDIÊNCIA: Null. 

JASON HIRSCHHORN: Para nulo. Exatamente. Então, nós apenas inserido algo na lista encadeada. Nós só escrevi este código para fazer isso. Quase que quase conseguiu completamente rachado. Agora vamos inserir doces. Nosso doces também vai para zero. Então, o que vamos fazer com doces? 

AUDIÊNCIA: Depende se ou Não estamos tentando resolver isso. 

JASON HIRSCHHORN: Isso é exatamente correto. Depende se ou não Estamos tentando resolver isso. Vamos supor que nós não estamos indo para classificá-lo. 

AUDIÊNCIA: Bem, então, como discutimos antes, é mais simples apenas para colocá-lo logo no início para que o ponteiro de zero pontos a doces. 

JASON HIRSCHHORN: OK. Espere um pouco. Deixe-me criar doces aqui. Portanto, este ponteiro - 

AUDIÊNCIA: Sim, deve agora estar apontando para doces. Então, o ponteiro da ponto doce para abóbora. 

JASON HIRSCHHORN: Assim? E dizer que tem outro coisa para mapear a zero? 

AUDIÊNCIA: Bem, você só fazer a mesma coisa? 

JASON HIRSCHHORN: Faça a mesma coisa. Portanto, neste caso, se não o fizermos quer mantê-lo ordenados soa bastante simples. Tomamos o ponteiro no indice dada pela nossa função hash. Temos que apontam para o nosso novo nó. E então, o que quer que estava apontando previamente - neste caso, nulo, no segundo caso abóbora - que, seja o que está apontando para anteriormente, adicionar para o próximo de o nosso novo nó. Estamos inserindo algo no início. Na verdade, este é muito mais simples do que tentando manter a lista ordenada. Mas, novamente, a pesquisa será mais complicado aqui. Nós sempre vamos ter que ir até o fim. 

OK. Qualquer dúvida sobre o encadeamento separado? Como isso funciona? Por favor, pergunte-los agora. Eu realmente quero ter a certeza que tudo entender isso antes de cabeça para fora. 

AUDIÊNCIA: Por que você coloque a abóbora e doces na mesma parte da tabela de hash? 

JASON HIRSCHHORN: Boa pergunta. Por que colocá-los na mesma parte da tabela de hash? Bem, neste caso, a nossa função de hash retorna zero para ambos. Então, eles precisam ir ao indice de zero porque é onde nós estamos indo procurá-los se alguma vez quer procurá-los. Mais uma vez, com uma abordagem linear sondagem nós não iria colocá-los a zero. Mas, na abordagem da cadeia separada, vamos colocá-los a zero e, em seguida, criar uma lista fora de zero. 

E nós não queremos substituir abóbora simplesmente por isso, porque então nós assumir que abóbora foi nunca inserido. Se nós apenas manter uma coisa na local que seria ruim. Então, não haveria possibilidade de nós nunca - se alguma vez teve uma duplicata, então nós seria apenas apagar o nosso valor inicial. Então é por isso que fazemos esta abordagem. Ou é por isso que nós escolhemos - mas novamente, escolheu a abordagem de encadeamento separado, que existem muitas outras abordagens pode-se escolher. Isso responde a sua pergunta? 

OK. Carlos. Sondagem Linear envolveria - se encontramos uma colisão em zero, nós ficaria no próximo ponto para ver se era aberto e colocá-lo lá. E então nós olhamos na próxima esporte e ver se estava aberto e colocá-lo lá. Assim, encontramos o seguinte disponível local aberto e colocá-lo lá. Alguma outra pergunta? Sim, Avi. 

AUDIÊNCIA: No seguimento disso, o que você quer dizer com próximo ponto? Na tabela de hash ou em uma lista vinculada. 

JASON HIRSCHHORN: Para linear programação, há listas ligadas. O próximo ponto na tabela de hash. 

AUDIÊNCIA: OK. Assim, a tabela hash seria inicializado para a dimensão - como o número de strings que você estava inserindo? 

JASON HIRSCHHORN: Você faria quer que seja realmente grande. Sim. Aqui está uma imagem do que nós acabou de desenhar no quadro. Mais uma vez, temos uma colisão bem aqui. em 152. E você vai ver que criamos uma lista ligada fora dele. Mais uma vez, a tabela hash encadeamento separado abordagem não é o que você tem que tomar para definir problemas seis, mas é um que um monte de estudantes tendem a tomar. Então, com essa nota, vamos falar brevemente antes de cabeça para fora sobre o problema seis, e então eu vou compartilhar uma história com você. Temos três minutos. 

Problema definir seis. Você tem quatro funções - carga, verificar o tamanho eo descarregamento. Carga - bem, estamos indo sobre a carga agora. Traçamos carga na placa. E nós nem sequer começou a codificação de um monte de inserção em uma lista encadeada. Assim, a carga não é muito mais do que o que acabamos fazendo. 

Check é quando você tem algo carregado. É o mesmo processo como este. As mesmas duas primeiras partes onde você joga algo na função de hash e obter o seu valor. Mas agora não vamos inseri-lo. Agora nós estamos olhando para ele. Tenho código de exemplo escrito por encontrar algo em uma lista encadeada. Encorajo-vos a praticar isso. Mas intuitivamente encontrar algo é bastante semelhante ao da inserção de alguma coisa. Na verdade, fez um desenho de encontrar algo em uma lista encadeada, movendo-se completamente até que você chegou ao final. E se você chegou ao final e não podia encontrá-lo, então ele não está lá. Então, isso é cheque, essencialmente. 

Em seguida é o tamanho. Vamos pular tamanho. Finalmente você descarregar. Unload é uma que não têm atraído na placa ou codificados ainda. Mas eu encorajá-lo a tentar codificá-lo em nossa amostra exemplo lista encadeada. Mas descarregar intuitivamente é semelhante ao livre - ou eu quero dizer é semelhante para verificar. Exceto agora cada vez que você vai através, você não está simplesmente verificando a veja se você tem o seu valor lá. Mas você está tomando esse nó e libertando-o, essencialmente. Isso é o que descarregar lhe pede para fazer. Tudo grátis você malloced. Então, você está passando por toda a lista mais uma vez, passando por todo o hash mesa novamente. Desta vez, não marque para ver o que está lá. Apenas libertar o que está lá. 

E, finalmente, o tamanho. Tamanho deve ser implementada. Se você não implementar o tamanho - Vou dizer assim. Se você não implementar o tamanho exatamente uma linha de código, incluindo a voltar declaração, você é fazendo tamanho incorretamente. Portanto, verifique se o tamanho, para o projeto completo pontos, você está fazendo isso em exatamente um linha de código, incluindo a instrução de retorno. 

E não arrumar ainda, Akchar. Castor Eager. Eu queria agradecer a vocês para vir a seção. Tenha um Feliz Dia das Bruxas. Este é meu traje. Eu vou estar vestindo esta quinta-feira se eu vê-lo em horário de expediente. E se você está curioso para saber um pouco mais fundo quanto a este traje, sentir livre para verificar a seção 2011 para uma história sobre isso que eu sou vestindo a fantasia de abóbora. E é uma história triste. Portanto, verifique se você tem alguns tecidos próximos. Mas por que, se você tem alguma perguntas que eu vou ficar por aqui fora depois de seção. Boa sorte em conjunto de problemas seis. E como sempre, se você tiver qualquer perguntas, deixe-me saber.