[Powered by Google Translate] [Seção 6: menos confortável] [Nate Hardison] [Harvard University] [Esta é CS50.] [CS50.TV] Tudo bem. Bem-vindo à secção 6. Esta semana, vamos estar falando sobre estruturas de dados na seção, principalmente porque o problema desta semana definir em spellr faz um monte de exploração diferente da estrutura de dados. Há um monte de maneiras diferentes você pode ir com o conjunto de problemas, E quanto mais estruturas de dados que você sabe sobre, as coisas mais legais que você pode fazer. 

Então vamos começar. Primeiro vamos falar sobre pilhas, dados da pilha e fila estruturas que nós vamos falar sobre. Pilhas e filas são realmente úteis quando começamos a falar sobre os gráficos, que nós não vamos fazer tanto de agora. Mas eles são muito bons para entender um dos grandes estruturas de dados fundamentais do CS. A descrição na especificação do conjunto de problemas, Se você puxar-lo, fala sobre pilhas como semelhante a a pilha de bandejas de refeições que você tem na lanchonete nas salas de jantar onde quando o jantar a equipe vem e coloca as bandejas de refeições para fora depois que limpa-los, eles empilhá-los um em cima do outro. E então, quando as crianças vêm para obter alimentos, eles puxam as bandejas de fora, primeiro a de cima, então o que está abaixo dela, então a um abaixo disso. Então, na verdade, a primeira bandeja que o jantar a equipe colocar para baixo é a última que é levado. O último que o jantar a equipe colocar é o primeiro que é levado para o jantar. Na especificação do conjunto de problemas, que você pode baixar, se você não tiver, falamos sobre a modelagem de um stucture dados da pilha usando este tipo de estrutura. 

Então, o que nós temos aqui, isso é semelhante ao que foi apresentado na aula, exceto em palestra que apresentou esta com ints ao contrário de char * s. Esta vai ser uma pilha que armazena o que? Daniel? O que estamos armazenando nesta pilha? [Daniel] Cordas? >> Estamos armazenar cadeias nesta pilha, exatamente. Tudo que você precisa ter para criar uma pilha é um array de uma capacidade particular, que, neste caso, capacidade vai ser em todas as tampas, pois é uma constante. E então, além da matriz, tudo o que precisamos para seguir é o tamanho atual da matriz. Uma coisa a notar aqui que é legal é a de que estamos a criar a estrutura de dados empilhada sobre uma outra estrutura, a matriz. Há diferentes maneiras de implementar pilhas. Nós não vamos fazer isso bastante ainda, mas espero que depois de fazer os problemas de lista vinculada, você vai ver como você pode facilmente implementar uma pilha em cima de uma lista ligada também. Mas, por enquanto, vamos ficar com as matrizes. Então, novamente, tudo o que precisamos é um array e só precisamos de controlar o tamanho da matriz. [Sam] Desculpe, por que é que você disse a pilha está no topo das cordas? Para mim parece que as cordas estão dentro da pilha. [Hardison] Yeah. Estamos criando, nós estamos levando a nossa matriz de estrutura de dados - essa é uma grande questão. Então a questão é por isso que, para as pessoas que estão assistindo esta linha, por que estamos dizendo que a pilha está em cima das cordas, porque aqui parece que as cordas estão dentro da pilha? O que é totalmente o caso. O que eu estava referindo-se a era que nós temos uma estrutura de dados matriz. Nós temos uma matriz de char * s, este arranjo de cordas, e vamos acrescentar a isto, a fim de criar a estrutura de dados empilhados. 

Assim, uma pilha é um pouco mais complexo do que um array. Podemos usar uma matriz para construir uma pilha. Então é aí que nós dizemos que a pilha é construída em cima de uma matriz. Da mesma forma, como eu disse anteriormente, podemos construir uma pilha em cima de uma lista ligada. Em vez de usar uma matriz para armazenar os nossos elementos, poderíamos usar uma lista ligada para manter nossos elementos e construir a pilha em torno disso. Vamos caminhar através de um par de exemplos, olhando para algum código, para ver o que está realmente acontecendo aqui. Na esquerda, eu tenho jogado para baixo o que struct pilha ficaria na memória se a capacidade de se # definido como sendo quatro. Nós temos nossos quatro elemento do array char *. Temos strings [0], strings [1], strings [2], strings [3], e, em seguida, que o espaço para o nosso passado inteiro tamanho. Será que isto faz sentido? Okay. Isto é o que acontece se o que eu faço à direita, qual será o meu código, é apenas para declarar uma estrutura, uma estrutura chamada empilhados s. Isto é o que temos. Estabelece esta pegada na memória. A primeira pergunta aqui é o que são os conteúdos desta struct pilha? Agora eles não é nada, mas eles não são absolutamente nada. São este tipo de lixo. Nós não temos idéia do que está neles. Quando declaramos s pilha, estamos apenas jogando que em cima da memória. É uma espécie de como declarar int i e não inicializa-la. Você não sabe o que está lá. Você pode ler o que está lá, mas não pode ser super útil. Uma coisa que você quer sempre se lembrar de fazer é inicializar o que precisa ser inicializado. Neste caso, nós estamos indo para inicializar o tamanho para ser zero, porque que vai passar a ser muito importante para nós. Nós poderíamos ir em frente e inicializar todos os ponteiros, todos os s * char, ser algum valor compreensível, provavelmente nulo. Mas não é totalmente necessário que façamos isso. 

Agora, as duas principais operações sobre pilhas são? Alguém se lembra da palestra que você faz com pilhas? Sim? [Stella] Empurrando e popping? >> Exatamente. Empurrando e popping são as duas principais operações sobre pilhas. E o que fazer pressão? >> Ele coloca algo para o topo da pilha, e depois leva-lo de estalo. [Hardison] Exatamente. Então, empurrando empurra algo no topo da pilha. É como o jantar a equipe colocando uma bandeja de jantar no balcão. E popping está levando uma bandeja de jantar ao lado da pilha. Vamos examinar alguns exemplos do que acontece quando empurrar as coisas para a pilha. Se fôssemos para empurrar a string 'Olá' para o nosso pilha, este é o nosso diagrama será parecido agora. Veja o que acontece? Nós empurrado para dentro do primeiro elemento de nossa matriz cordas e elevou a contagem de tamanho para ser 1. Então, se olharmos para a diferença entre os dois slides, aqui foi de 0, aqui está antes do empurrão. Aqui é depois do empurrão. Antes do envio, após a pressão. E agora temos um elemento em nossa pilha. É a string "Olá", e é isso. Tudo o resto na matriz, em nossa matriz cordas, ainda é lixo. Nós não inicializado ele. Vamos dizer que empurrar uma outra corda para o nosso pilha. Nós vamos empurrar "mundo" neste momento. Assim você pode ver "mundo" aqui vai em cima do "Olá", e a contagem de tamanho vai até 2. Agora podemos empurrar "CS50", e que vai em cima novamente. Se voltar, você pode ver como estamos empurrando as coisas em cima da pilha. E agora temos a pop. Quando apareceu alguma coisa fora da pilha, o que aconteceu? Alguém viu a diferença? É muito sutil. [Aluno] O tamanho. >> Sim, o tamanho alterado. 

O que mais você esperar para mudar? [Aluno] As cordas, também. >> Direito. As cordas também. Acontece que quando você está fazendo desta forma, porque não estamos copiando os elementos em nossa pilha, nós realmente não tem que fazer nada, podemos usar apenas o tamanho para manter o controle do número de coisas em nossa matriz para que, quando aparecer de novo, mais uma vez, apenas diminuir nosso tamanho para 1. Não há necessidade de realmente entrar e substituir nada. Tipo de funky. Acontece que nós normalmente simplesmente deixar as coisas sozinho, porque é menos trabalho para nós. Se nós não temos que voltar e substituir alguma coisa, então por que fazer isso? Assim, quando aparecer duas vezes fora da pilha, é tudo o que faz diminuir o tamanho de um par de vezes. E mais uma vez, este é apenas porque não estamos copiando as coisas em nossa pilha. Sim? Vá em frente. [Estudante, ininteligível] >> E então o que acontece quando você empurrar algo novo? Quando você empurrar algo de novo, para onde vai? Para onde ela vai, Basil? >> Em cordas [1]? >> Direito. Por que não ir para strings [3]? [Basil] Porque se esqueceu de que não havia nada em cordas [1] e [2]? [Hardison] Exatamente. Nossa pilha, essencialmente, "esqueceu" que estava segurando em nada em cordas [1] ou cordas [2], portanto, quando empurrar "woot", ele simplesmente coloca que para o elemento em cordas [1]. Há dúvidas sobre como isso funciona, em um nível básico? [Sam] Assim, este não é dinâmica, de qualquer maneira, em termos de quantidade ou em termos do tamanho da pilha? [Hardison] Exatamente. Isto é - o ponto era que esta não era uma pilha dinamicamente growning. Trata-se de uma pilha que pode conter, no máximo, quatro char * s, no máximo quatro coisas. Se fôssemos tentar empurrar uma coisa quinto, o que você acha que deve acontecer? [Estudantes, ininteligível] [Hardison] Exatamente. Há uma série de coisas que podem acontecer. Ele poderia seg falha, dependendo do que nós - exatamente como nós estavam a implementar o back-end. Ele poderia substituir. Ele poderia ter esse estouro de buffer que falamos em sala de aula. Qual seria a coisa mais óbvia que pode ser substituído se tentou empurrar uma coisa extra em nosso pilha? Então você mencionou um estouro de buffer. O que pode ser a única coisa que se escreveu mais ou pisou se transbordou acidentalmente por tentar empurrar uma coisa extra? [Daniel, ininteligível] Possível. >> Mas, inicialmente, o que pode acontecer? O que se tentou empurrar uma quarta coisa? Ele pode substituir o tamanho, pelo menos com este diagrama de memória que temos. 

Na especificação conjunto de problemas, que é o que nós vamos estar implementando hoje, o que nós queremos fazer é retornar falso. Nosso método push vai retornar um valor booleano, e esse valor booleano será verdade se o impulso sucesso e falso se não podemos empurrar mais nada, porque a pilha está cheia. Vamos examinar um pouco de que o código agora. Aqui é a nossa função push. Nossa função push para uma pilha vai ter na cadeia para colocar na pilha. Vai retornar verdadeiro se a string foi empurrado com sucesso na outra pilha e falso. Todas as sugestões sobre o que pode ser uma coisa boa primeiro a fazer aqui? [Sam] Se tamanho é igual capacidade em seguida, retornar falso? [Hardison] Bingo. Bom trabalho. Se o tamanho é a capacidade, vamos retornar falso. Não podemos colocar algo mais em nossa pilha. Caso contrário, nós queremos colocar algo no topo da pilha. O que é o "topo da pilha", inicialmente? [Daniel] Tamanho 0? Tamanho >> 0. O que é o topo da pilha depois há uma coisa na pilha? Missy, você sabe? [Missy] um. Tamanho >> é uma, exatamente. Você continuar a acrescentar ao tamanho, e cada vez que você está colocando no novo elemento no tamanho do índice na matriz. Nós podemos fazê-lo com esse tipo de one-liner, se isso faz sentido. Então, nós temos nossa matriz cordas, vamos para acessá-lo no índice tamanho, e nós apenas estamos indo para guardar nosso char * lá. Observe como não há como cópia cadeia acontecendo aqui, não alocação dinâmica de memória? E então Missy trouxe o que temos agora de fazer, porque nós temos guardado a cadeia no lugar apropriado na matriz, e ela disse que tínhamos que aumentar o tamanho de um modo que nós estamos prontos para o impulso seguinte. Assim, podemos fazer isso com s.size + +. Neste ponto, nós empurrado para a nossa matriz. Qual é a última coisa que temos que fazer? [Estudante] retornar true. Retornar >> verdade. Então é muito simples, um código muito simples. Não muito. Uma vez que você envolveu sua cabeça em torno de como a pilha funciona, isso é muito simples de implementar. 

Agora, a próxima parte deste está surgindo uma corda fora da pilha. Eu vou dar a vocês algum tempo para trabalhar nisso um pouco. É quase essencialmente o contrário do que nós fizemos aqui no empurrão. O que eu tenho feito é, na verdade - oops. Eu tenha iniciado um aparelho aqui, e no aparelho, Eu puxei o conjunto de problemas 5 especificação. Se zoom aqui, podemos ver que eu estou em cdn.cs50.net/2012/fall/psets/pset5.pdf. Vocês já baixou este código que está localizado aqui, section6.zip? Tudo bem. Se você não tiver feito isso, faça isso agora, muito rapidamente. Eu vou fazer isso na minha janela de terminal. Na verdade, eu fiz isso aqui em cima. Sim. Sim, Sam? >> Eu tenho uma pergunta sobre por que você disse s.string 's faixas de tamanho = str? O que é str? É o definido em algum lugar antes, ou - oh, no str char *? [Hardison] Sim, exatamente. Esse foi o argumento. >> Ah, ok. Desculpe. [Hardison] Nós estamos especificando a corda para empurrar dentro A outra questão que possa surgir que nós realmente não falar aqui era tomamos por certo que tivemos esta variável chamada s que estava no escopo e acessível para nós. Tomamos por certo que s foi esta struct pilha. Então, olhando para trás, este código push, você pode ver que nós estamos fazendo coisas com esta corda que foi aprovada em mas então, de repente, estamos acessando s.size, como, de onde s vem? No código que vamos olhar no arquivo seção e, em seguida, o material que você estará fazendo em seu problema se põe, fizemos nossa pilha struct uma variável global para que possamos ter acesso a ele em todas as nossas funções diferentes sem ter que manualmente passar ao redor e passá-lo por referência, fazer todo o tipo de coisa a ele. Estamos apenas enganando um pouco, se quiser, para fazer as coisas melhor. E isso é algo que estamos fazendo aqui, porque isso é para se divertir, é mais fácil. Muitas vezes, você vai ver as pessoas fazem isso, se eles têm uma grande estrutura de dados que está sendo operado dentro de seu programa. 

Vamos voltar para o aparelho. Será que todo mundo com sucesso obter o section6.zip? Todo mundo descompactá-lo usando section6.zip unzip? Se você vai para o diretório seção 6 - aah, em todo o lugar - e você listar o que tem aqui, você vê que você tem três diferentes arquivos. c. Você tem uma fila, um sll, que, isoladamente, é ligada lista, e uma pilha. Se você abrir stack.c, você pode ver que nós temos essa estrutura definida para nós, a estrutura exata que nós acabamos de falar nos slides. Temos a nossa variável global para a pilha, nós temos nossa função push, e depois temos a nossa função pop. Eu vou colocar o código para empurrar de volta no slide aqui, mas o que eu gostaria que vocês a fazer é, com o melhor de sua capacidade, ir e implementar a função pop. Depois de implementar, você pode compilar este com o make de pilha, e, em seguida, executar o arquivo executável pilha resultante, e que irá executar todo esse código de teste aqui em baixo que está na principal. E principal cuida de realmente fazer o push e pop chamadas e certificando-se que tudo passa bem. Também se inicializa o tamanho da pilha aqui assim você não precisa se preocupar com a inicialização isso. Você pode assumir que ele foi inicializado corretamente pelo tempo que você acessá-lo na função de pop. Isso faz sentido? Então, vamos lá. Há o código empurrão. Eu vou dar a vocês 5 ou 10 minutos. E se você tiver alguma dúvida no ínterim, enquanto você está de codificação, pergunte-lhe em voz alta. Então, se você chegar a um ponto de discórdia, é só pedir. Deixe-me saber, deixe todo mundo sabe. Trabalhe com seu vizinho também. [Daniel] Estamos apenas implementando pop agora? Apenas >> pop. Embora você pode copiar a implementação de impulso se quiser de modo que o teste irá funcionar. Porque é difícil para testar as coisas ficando em - ou, é difícil testar as coisas pulando para fora de uma pilha se não houver nada na pilha para começar. 

O que é pop suposto estar voltando? O elemento a partir do topo da pilha. É suposto obter o elemento para fora da parte superior da pilha e, em seguida, diminuir o tamanho da pilha, e agora você perdeu o elemento no topo. E então você retornar o elemento no topo. [Estudante, ininteligível] [Hardison] Então, o que acontece se você faz isso? [Estudante, ininteligível] O que acaba acontecendo é que você provavelmente está acessando ou um elemento que não foi inicializado ainda, para que o seu cálculo de onde o último elemento é desligado. Então, aqui, se você observar, no impulso, estamos acessando cordas no elemento s.size porque é um novo índice. É o novo topo da pilha. Considerando que, pop, s.size vai ser o próximo espaço, o espaço que está no topo de todos os elementos em seu stack. Assim, o elemento de nível mais alto não é s.size, mas sim, é por baixo. 

A outra coisa a fazer quando você - em pop, é que você tem que diminuir o tamanho. Se você se lembrar de volta ao nosso pequeno diagrama aqui, realmente, a única coisa que vimos acontecer quando chamado pop era que este tamanho descartado, primeiro a 2, então a 1. Então, quando empurrou um novo elemento ligado, ele iria para o local adequado. [Basil] Se o s.size é 2, então ele não iria passar para o elemento 2, e depois que você gostaria de aparecer esse elemento fora? Então, se nós fomos para - >> Então, vamos olhar para isso de novo. Se esta for a pilha neste ponto e chamamos pop, em que o índice é o elemento mais alto? [Basil] No 2, mas vai aparecer 3. >> Direito. Então é aí que nosso tamanho é 3, mas queremos colocar o elemento no índice 2. É esse tipo típico de fora por um que você tem com o zero-indexação de matrizes. Então, você quer aparecer o terceiro elemento, mas o terceiro elemento não está no índice 3. E a razão pela qual não tem que fazer isso uma menos quando estamos empurrando é porque agora, você percebe que o elemento mais alto, se fôssemos para empurrar outra coisa para a pilha, neste ponto, que gostaria de empurrá-lo no índice 3. E isso só acontece se o tamanho e os índices alinhar quando você está empurrando. 

Quem tem uma implementação da pilha de trabalho? Você tem uma pilha de trabalhar um. Você tem pop funcionando ainda? [Daniel] Sim. Acho que sim. Programa >> está funcionando e não seg falhamento, está imprimindo? Será que imprimir "sucesso" quando você o executa? Sim. Faça empilhar, executá-lo, se ele imprime "sucesso" e não vai boom, então tudo é bom. Tudo bem. Vamos passar para o aparelho muito rapidamente, e nós vamos caminhar por este. Se olharmos para o que está acontecendo aqui com pop, Daniel, que foi a primeira coisa que você fez? [Daniel] Se s.size é maior que 0. [Hardison] Okay. E por que você fez isso? [Daniel] Para se certificar de que havia algo dentro da pilha. [Hardison] Direito. Você deseja testar para ter certeza de que s.size é maior que 0; de outra forma, o que você quer que aconteça? [Daniel] return null? >> Return null, exatamente. Portanto, se s.size é maior que 0. Então, o que vamos fazer? O que vamos fazer se a pilha não está vazio? [Stella] Você diminuir o tamanho? >> Você diminuir o tamanho, tudo bem. Então, como você fez isso? >> S.size--. [Hardison] Grande. E então, o que você fez? [Stella] E então eu disse que o retorno s.string [s.size]. [Hardison] Grande. Caso contrário, você retornar nulo. Sim, Sam? [Sam] Por que não precisa ser s.size + 1? [Hardison] Plus 1? Sim >>. >> Entendi. [Sam] Eu pensei, porque você está levando um fora, então você está indo estar voltando não o que eles pediram. [Hardison] E isso foi exatamente o que estavam falando com toda esta questão de 0 índices. Então, se o zoom aqui. Se olharmos para esse cara aqui, você pode ver que, quando aparecer, estamos estourando o elemento no índice 2. 

Então, nós diminuímos nosso tamanho primeiro, depois o nosso tamanho corresponde ao nosso índice. Se não diminuir o tamanho do primeiro, então temos que fazer o tamanho -1 e decremento. Grande. Tudo bem? Qualquer dúvida sobre isso? Há uma série de maneiras diferentes para escrever isso também. Na verdade, podemos fazer algo ainda - nós podemos fazer um one-liner. Nós podemos fazer um retorno de uma linha. Assim, podemos realmente diminuir antes de retornar ao fazer isso. Então, colocar o - antes do s.size. Isso faz com que a linha realmente denso. Se a diferença entre o - s e tamanho. S.size - é que este postfix - que eles chamam de postfix, porque o - vem depois do s.size - significa que s.size é avaliada para efeitos de encontrar o índice como é atualmente, quando esta linha é executada, e depois isso - acontece após a linha é executada. Após o elemento em s.size índice é acessado. E isso não é o que queremos, porque queremos que o decremento acontecer primeiro. Othewise, vamos estar acessando a matriz, efetivamente, fora dos limites. Nós vamos estar acessando o elemento acima do que realmente deseja acessar. Sim, Sam? >> É mais rápido ou usar menos memória RAM para fazer em uma linha ou não? [Hardison] Honestamente, isso realmente depende. [Sam, ininteligível] >> Sim, depende. Você pode fazer truques compilador para obter o compilador para reconhecer que, geralmente, eu imagino. 

Então, nós mencionamos um pouco sobre essas coisas otimização do compilador que você pode fazer na compilação, e esse é o tipo de coisa que um compilador pode ser capaz de descobrir, como oh, hey, talvez eu possa fazer tudo isso em uma única operação, ao contrário de carregar a variável em tamanho a partir da RAM, decrementando-lo, guardá-lo de volta para fora, e depois colocá-lo de volta novamente para processar o resto da operação. Mas, normalmente, não, este não é o tipo de coisa que vai fazer o seu programa significativamente mais rápido. Mais alguma pergunta sobre pilhas? 

Então, empurrando e popping. Se vocês querem experimentar a edição de hacker, o que temos feito na edição de hacker é realmente ido e fez esta pilha crescer dinamicamente. O desafio não é principalmente aqui na função push, para descobrir como fazer essa matriz crescer como você continuar pressionando mais e mais elementos sobre a pilha. Não é realmente muito código adicional. Apenas uma chamada para - você tem de se lembrar de obter as chamadas para malloc lá corretamente, e depois descobrir quando você está indo para chamar realloc. Isso é um desafio divertido se você estiver interessado. 

Mas, por enquanto, vamos seguir em frente, e vamos falar sobre as filas. Rolar por aqui. A fila é um irmão perto da pilha. Então, na pilha, as coisas que foram colocadas em último foram as primeiras coisas a ser recuperados. Temos este último a entrar, primeiro fora, ou LIFO, ordenando. Considerando que, em fila, como seria de esperar a partir de quando você está em pé na fila, a primeira pessoa a entrar na fila, a primeira coisa a entrar na fila, é a primeira coisa que é recuperada da fila. As filas também são frequentemente utilizados quando estamos lidando com gráficos, como falamos brevemente com pilhas, e as filas também são úteis para um monte de outras coisas. Uma coisa que surge muitas vezes é tentar manter, por exemplo, uma lista ordenada de elementos. E você pode fazer isso com uma matriz. Você pode manter uma lista ordenada de coisas em uma matriz, mas onde que fica complicado é, então você sempre tem que encontrar o lugar apropriado para inserir a próxima coisa. Então se você tem uma matriz de números, de 1 a 10, e então você quer expandir isso para todos os números de 1 a 100, e você está ficando estes números de forma aleatória e tentando manter tudo classificados como você passar, você acaba tendo que fazer um monte de mudança. Com certos tipos de filas e certos tipos de estruturas de dados subjacentes, você pode realmente mantê-lo bastante simples. Você não tem que adicionar alguma coisa e, em seguida reordene a coisa toda de cada vez. Nem você tem que fazer um monte de mudança dos elementos internos ao redor. Quando olhamos para uma fila, você vê que - também em queue.c no código de seção - a estrutura que temos dado a você realmente é parecida com a estrutura que lhe deu de uma pilha. 

Há uma exceção a isso, e que uma exceção é que temos este inteiro adicional chamado a cabeça, eo chefe aqui é para manter o controle da cabeça da fila, ou o primeiro elemento na fila. Com uma pilha, fomos capazes de manter o controle do elemento que estávamos prestes a recuperar, ou a parte superior da pilha, utilizando apenas o tamanho, enquanto que com uma fila, estamos tendo que lidar com extremos opostos. Estamos tentando alinhavar as coisas em no final, mas em seguida, retornar as coisas de frente. Assim, de forma eficaz, com a cabeça, temos o índice do início da fila, e o tamanho dá-nos o índice do fim da fila para que possamos recuperar as coisas da cabeça e acrescentar coisas a cauda. Enquanto que com a pilha, estávamos sempre apenas lida com o topo da pilha. Nunca tinha a aceder ao fundo da pilha. Nós só acrescentou coisas para cima e levou as coisas fora do topo assim nós não precisamos que campo extra dentro da nossa estrutura. Isso geralmente faz sentido? Tudo bem. Sim, Charlotte? [Charlotte, ininteligível] [Hardison] Isso é uma grande questão, e que foi um que surgiu em palestra. Talvez caminhando através de alguns exemplos que ilustram por nós não queremos usar cordas [0] como chefe de fila. 

Então, imagine que temos a nossa fila, vamos chamá-lo de fila. No início, quando temos apenas instanciado-lo, quando temos apenas declarou que, não temos nada inicializado. É tudo lixo. Então, é claro que nós queremos ter certeza de que nós inicializar tanto o tamanho e os campos de cabeça para ser 0, algo razoável. Nós também pode ir em frente e nulo fora os elementos na nossa fila. E para fazer este ajuste diagrama, observe que agora a nossa fila só pode ter três elementos; enquanto que a nossa pilha poderia prender quatro, nossa fila só pode ter três. E isso é só para fazer o ajuste diagrama. A primeira coisa que acontece aqui é que colocar na fila a string "oi". E, assim como fizemos com a pilha, nada muito diferente aqui, jogamos a corda no em cordas [0] e incrementar o nosso tamanho em 1. Nós enfileirar "adeus", ele é colocado. Portanto, esta parece uma pilha para a maior parte. Nós começamos aqui, elemento novo, elemento novo, o tamanho continua a subir. O que acontece neste momento quando queremos desenfileirar alguma coisa? Quando queremos retirar da fila, que é o elemento que queremos retirar da fila? [Basil] Strings [0]. >> Zero. Exatamente, Basil. Queremos livrar-se da primeira cadeia, este, "oi". Então, qual foi a outra coisa que mudou? Observe quando apareceu algo fora da pilha, só mudou o tamanho, mas aqui, temos um par de coisas que mudam. Não só a alteração de tamanho, mas as alterações de cabeça. Isso vai de volta ao ponto de Charlotte anteriormente: Por que temos esta cabeça também? Será que faz sentido agora, Charlotte? Tipo de >>. [Hardison] Kind of? Então, o que aconteceu quando dequeued? O que fez a cabeça de fazer isso agora é interessante? [Charlotte] Ah, porque ele mudou - tudo bem. Eu vejo. Porque a cabeça - onde a cabeça está apontando para mudanças em termos de localização. Não é mais sempre a um índice zero. >> Sim, exatamente. O que aconteceu foi dequeueing se o elemento de alta foi feito e nós não têm essa cabeça campo porque estávamos sempre ligando essa string em 0 índice de o chefe da nossa fila, então nós teríamos que mudar o resto da fila de baixo. Nós teríamos que mudar o "adeus" de de cordas [1] para as cordas [0]. E cordas [2] para baixo para cordas [1]. E nós temos que fazer isso para toda a lista de elementos, toda a matriz de elementos. E quando estamos fazendo isso com uma matriz, que fica muito caro. Então, aqui, não é um grande negócio. Só temos três elementos na nossa matriz. Mas se tivéssemos uma fila de milhares de elementos ou de um milhão de elementos, e então, de repente, começamos a fazer um monte de dequeue chama a todos em um loop, as coisas estão realmente indo para desacelerar como ele muda tudo para baixo constantemente. Você sabe, mudar por 1, por uma mudança de turno, por 1, por uma mudança. Em vez disso, usamos essa cabeça, chamamos isso de um "ponteiro", apesar de que não é realmente um ponteiro em sentido estrito, não é um tipo de ponteiro. Não é um * int ou um char * ou qualquer coisa assim. Mas está apontando ou indicando o chefe da nossa fila. Sim? 

[Estudante] Como dequeue sabe apenas pop fora o que está na cabeça? [Hardison] Como dequeue saber como pop fora tudo o que está na cabeça? Direito >>, sim. >> O que ele está vendo é apenas o que a cabeça campo está definido. Assim, neste primeiro caso, se olharmos bem aqui, nossa cabeça é 0, 0 índice. >> Direito. [Hardison] Então ele só diz bem, bem, o elemento no índice 0, a seqüência de "oi", é o elemento na cabeça da nossa fila. Então, vamos para desenfileirar esse cara. E isso vai ser o elemento que é devolvido para o chamador. Sim, Saad? Assim, a cabeça >> basicamente define o - onde você está indo para indexá-lo? Isso é o começo? Sim >>. Ok >>. [Hardison] que está se tornando o novo começo para a nossa matriz. Então, quando você desenfileirar alguma coisa, tudo que você precisa fazer é acessar o elemento no índice q.head, e que será o elemento que pretende retirar da fila. Você também tem que diminuir o tamanho. Vamos ver um pouco as coisas ficam um pouco complicado com isso. Nós desenfileirar, e agora, se enfileirar novamente, onde é que vamos colocar na fila? Onde é que o próximo elemento ir na nossa fila? Dizer que queremos colocar na fila a string "CS". Em qual índice ela vai? [Os alunos] Strings [2]. >> Dois. Por 2 e não 0? [Basil] Porque agora a cabeça é 1, de modo que é como o início da lista? [Hardison] Direito. E o que indica o fim da lista? O que estávamos usando para indicar o final da nossa fila? A cabeça é o chefe da nossa fila, o início da nossa fila. O que é o fim da nossa fila? [Os alunos] Tamanho. Tamanho >>, exatamente. Assim, nossos novos elementos entrar em tamanho, e os elementos que tiramos sair na cabeça. Quando enfileirar o próximo elemento, estamos colocando-o em no tamanho. [Estudante] Antes de colocar isso em porém, tamanho era um, certo? [Hardison] Direito. Portanto, não muito em tamanho. + Tamanho, não um, mas a cabeça +. Porque nós mudou tudo pela quantidade cabeça. Então, aqui, agora temos uma fila de tamanho 1 que começa no índice 1. A cauda é índice 2. Sim? 

[Aluno] O que acontece quando você dequeue strings [0], e as cordas "slots de memória apenas se esvaziou, basicamente, ou simplesmente esquecida? [Hardison] Yeah. Neste sentido, estamos apenas esquecê-los. Se estivéssemos armazenar cópias deles para - muitas estruturas de dados, muitas vezes, armazenar as suas próprias cópias dos elementos de modo que a pessoa que gere a estrutura de dados não têm que se preocupar sobre onde todos os ponteiros estão indo. A estrutura de dados segura para tudo, segura a todas as cópias, para se certificar de que tudo persiste de forma adequada. No entanto, neste caso, estas estruturas de dados apenas, para simplificar, não estão fazendo cópias de tudo o que estamos armazenando em-los. [Estudante] Então este é um conjunto contínuo de -? Sim >>. Se olharmos para trás, o que a definição foi desta estrutura, é. É apenas uma matriz padrão, como você viu, uma matriz de char * s. Será que -? >> Sim, eu estava pensando se você eventualmente ficar sem memória, de certa forma, se você tem todos esses lugares vazios em sua matriz? [Hardison] Sim, é um bom ponto. 

Se olharmos para o que aconteceu agora, neste ponto, nós preenchemos a nossa fila, que parece. Mas nós não temos realmente cheio nossa fila porque temos uma fila que é tamanho 2, mas começa no índice 1, porque é onde nosso ponteiro cabeça. Como você estava dizendo, esse elemento em strings [0], no índice 0, não está realmente lá. Não está na nossa fila de mais. Nós apenas não se preocupou em ir e substituí-lo quando dequeued-lo. Assim, mesmo que parece que estamos sem memória, nós realmente não temos. Esse ponto está disponível para nós para usar. O comportamento adequado, se fôssemos tentar algo primeira dequeue como "bye", que seria pop bye fora. Agora a nossa fila começa no índice 2 e é de tamanho 1. E agora, se tentarmos e enfileirar algo novo, digamos, 50, 50 deve ir neste lugar no índice 0 porque ele ainda está disponível para nós. Sim, Saad? [Saad] Isso acontece automaticamente? [Hardison] Isso não acontece muito automaticamente. Você tem que fazer a matemática para fazer o trabalho, mas essencialmente o que temos feito é que acabamos enrolado. [Saad] E tudo bem se isso tem um buraco no meio dela? [Hardison] É se podemos fazer a matemática funcionar corretamente. 

E acontece que isso não é realmente difícil de fazer com o operador mod. Assim como fizemos com César e as coisas de criptografia, usando mod, podemos fazer as coisas para envolver e continuar ao redor e ao redor com nossa fila, manter esse ponteiro cabeça se movendo. Note-se que o tamanho é sempre respeitando o número de elementos, na verdade, dentro da fila. E isso é apenas o ponteiro de cabeça que mantém bicicleta passar. Se olharmos para o que aconteceu aqui, se voltar para o início, e você só vê o que acontece na cabeça quando enfileirar algo, nada aconteceu com a cabeça. Quando enfileirados outra coisa, nada aconteceu com a cabeça. Assim que dequeued algo, a cabeça vai-se por um. Nós enfileirado algo, não acontece nada na cabeça. Quando desenfileirar alguma coisa, de repente, a cabeça é incrementado. Quando enfileirar algo, não acontece nada na cabeça. 

O que aconteceria, neste ponto, se fôssemos desenfileirar algo de novo? Todos os pensamentos? O que aconteceria com a cabeça? O que deve acontecer com a cabeça se fôssemos para desenfileirar outra coisa? A cabeça agora está no índice 2, o que significa que a cabeça da fila é strings [2]. [Estudante] Que retorna 0? >> Ele deve retornar a 0. Ela deve envolver em torno de volta, exatamente. Até agora, cada vez que chamado dequeue, estamos adicionando um na cabeça, adicionar um para a cabeça, adicione uma para a cabeça, adicione uma para a cabeça. Assim que esse ponteiro cabeça fica para o último índice em nossa matriz, então temos que envolvê-la de volta ao redor para o começo, voltar a 0. [Charlotte] O que determina a capacidade da fila em uma pilha? [Hardison] Neste caso, acabamos usando sido uma constante # definido. Ok >>. [Hardison] No arquivo c real., Você pode entrar e mexer com ele um pouco e torná-lo tão grande ou tão pouco como você quer. [Charlotte] Então, quando você está tornando-se uma fila, como você faz o computador saiba como grande você quer a pilha para ser? [Hardison] Isso é uma grande questão. Há um par de maneiras. Um é apenas para defini-lo na frente e dizer que isso vai ser uma fila que tem 4 elementos ou 50 elementos ou 10.000. A outra maneira é fazer o que as pessoas estão fazendo edição de hackers e criar funções para ter sua fila crescer dinamicamente como mais coisas são adicionados dentro 

[Charlotte] Então, para ir com a primeira opção, o que você usa sintaxe para dizer ao programa que é o tamanho da fila? [Hardison] Ah. Então, vamos sair dessa. Eu ainda estou em stack.c aqui, então eu estou indo só para rolar até o topo aqui. Você pode ver isso aqui? Este é o # define capacidade 10. E isso é quase exatamente a mesma sintaxe que temos para fila. Exceto na fila, temos que o campo estrutura extra aqui. [Charlotte] Oh, eu pensei que a capacidade significava a capacidade para a cadeia. [Hardison] Ah. >> Isso é o comprimento máximo da palavra. >> Entendi. Sim. A capacidade aqui - que é um grande ponto. E isso é algo que é complicado porque o que temos declarado aqui é uma matriz de char * s. Uma matriz de ponteiros. Esta é uma matriz de caracteres. Este é provavelmente o que você viu quando você foi declarar seus buffers para o arquivo I / O, quando você foi criar strings manualmente na pilha. No entanto, o que temos aqui é uma matriz de char * s. Então, é uma matriz de ponteiros. Na verdade, se o zoom para fora e olharmos o que está acontecendo aqui na apresentação, você vê que os elementos reais, os dados de caracteres não é armazenada dentro da própria matriz. O que está armazenada dentro de nossa matriz aqui são ponteiros para os dados de caracteres. Okay. Então, vimos como o tamanho da fila é como com a pilha, o tamanho respeita sempre o número de elementos na fila no momento. Depois de fazer 2 enfileira, o tamanho é 2. Depois de fazer uma dequeue o tamanho agora é 1. Depois de fazer outra enqueue o tamanho está de volta a 2. Assim, o tamanho definitivamente respeita ao número de elementos na fila, e depois a cabeça apenas mantém ciclismo. Ele vai de 0-1-2, 0-1-2, 0-1-2. E toda vez que nós chamamos dequeue, o ponteiro cabeça é incrementado para o próximo índice. E se a cabeça está prestes a passar por cima, ele volta para 0. Então, com isso, podemos escrever a função dequeue. E vamos deixar a função enqueue para vocês para implementar em seu lugar. 

Quando desenfileirar um elemento de nossa fila, qual foi a primeira coisa que Daniel fez quando começou a escrever a função pop para pilhas? Deixe-me ouvir de alguém que não tenha falado ainda. Vamos ver, Saad, você se lembra o que Daniel fez o que a primeira coisa quando escreveu pop? [Saad] Não foi, foi - >> Ele testou para alguma coisa. [Saad] Se o tamanho for maior do que 0. >> Exatamente. E o que foi que o teste para? [Saad] Isso foi um teste para ver se há alguma coisa dentro da matriz. [Hardison] Yeah. Exatamente. Então você não pode aparecer qualquer coisa fora da pilha, se ele está vazio. Da mesma forma, não se pode retirar da fila qualquer coisa de uma fila se ele está vazio. Qual é a primeira coisa que devemos fazer em nossa função dequeue aqui, que você acha? [Saad] Se o tamanho for maior do que 0? Sim >>. Neste caso, eu realmente apenas testado para ver se ele é 0. Se for 0, podemos retornar nulo. Mas a lógica exatamente o mesmo. E vamos continuar com isso. Se o tamanho não é 0, onde é o elemento que queremos retirar da fila? [Saad] Na cabeça? >> Exatamente. Nós podemos apenas retirar o primeiro elemento em nossa fila acessando o elemento na cabeça. Nada louco. Depois disso, o que devemos fazer? O que tem que acontecer? Qual foi a outra coisa que falamos no dequeue? Duas coisas tem que acontecer, porque a nossa fila mudou. [Daniel] Reduzir o tamanho. >> Nós temos de reduzir o tamanho e aumentar a cabeça? Exatamente. Para aumentar a cabeça, não podemos apenas cega aumentar a cabeça, lembre-se. Não podemos apenas fazer queue.head + +. Temos também a incluir este mod pela capacidade. E por que nós mod pela capacidade, Stella? [Stella] Porque ele tem que envolver. >> Exatamente. Nós mod pela capacidade porque tem que envolver a volta a 0. Então, agora, neste momento, podemos fazer o que disse Daniel. Nós podemos diminuir o tamanho. E então podemos simplesmente retornar o elemento que estava no início da fila. Olha o tipo de gnarly em primeiro lugar. Você pode ter uma pergunta. Desculpe? 

[Sam] Por que é o primeiro no topo da fila? Onde é que isso vai? [Hardison] Vem da quarta linha do fundo. Depois que testar para ter certeza de que a nossa fila não está vazia, nós retiramos char * primeiro, retire o elemento que está sentado no índice cabeça de nossa matriz, da nossa matriz cordas >>, e chamada que primeiro? [Hardison] E chamamos isso de primeira. Sim. Só para acompanhar isso, por que você acha que nós tivemos que fazer isso? [Sam] Cada primeiro está apenas retornando q.strings [q.head]? Sim >>. >> Porque estamos fazendo isso mudança do q.head com a função mod, e não há maneira de fazer isso dentro da linha de retorno também. [Hardison] Exatamente. Você está no local. Sam está totalmente reconhecidas. A razão pela qual teve de retirar o primeiro elemento em nossa fila e armazená-lo em uma variável é porque esta linha que tinha a apenas q.head, há o operador mod lá não é algo que podemos fazer e tê-lo em vigor na cabeça sem - em uma única linha. Então, nós realmente temos que tirar o primeiro elemento, em seguida, ajuste a cabeça, ajustar o tamanho, e, em seguida, retornar o elemento que tirou. E isso é algo que vamos ver surgir mais tarde com listas ligadas, como brincar com eles. Muitas vezes, quando você está liberando ou eliminação de listas ligadas é preciso lembrar o próximo elemento, o ponteiro próximo de uma lista ligada antes de descartar o atual. Porque senão você jogar fora a informação do que resta na lista. Agora, se você vai para o seu aparelho, você abre queue.c-x fora deste. Então, se eu abrir queue.c, deixe-me zoom aqui, você vai ver que você tem um arquivo similar para o futuro. Parecidas arquivo com o que tínhamos antes com stack.c. Nós temos a nossa estrutura de fila definida apenas como vimos nos slides. 

Nós temos a nossa função enqueue que é para você fazer. E nós temos a função dequeue aqui. A função dequeue no arquivo é não implementado, mas vou colocá-lo de volta no PowerPoint para que você possa digitá-lo, se quiser. Assim, para os próximos 5 minutos ou mais, vocês trabalham em enqueue que é quase o contrário do dequeue. Você não tem que ajustar cabeça quando você está enqueueing, mas o que você tem que ajustar? Tamanho. Então, quando você enqueue, a cabeça permanece intocada, o tamanho é alterado. Mas é preciso um pouco de - você vai ter que brincar com essa mod para descobrir exatamente o que o índice do novo elemento deve ser inserido no. Então, eu vou dar a vocês um pouco, colocar desenfileirar volta no slide, e como vocês têm perguntas, gritar-los para que possamos todos falam sobre eles como um grupo. Além disso, com o tamanho que você não - quando você ajustar o tamanho, você pode sempre - você tem para modificar o tamanho de sempre? [Daniel] Não. >> Você não tem para modificar o tamanho, a direita. Como o tamanho sempre, se você está - supondo que você está administrando as coisas de forma adequada, o tamanho será sempre entre 0 e 3. Onde você tem que mod quando você está fazendo enqueue? [Estudante] Só para a cabeça. Só >> para a cabeça, exatamente. E por que você tem de mod em tudo em enqueue? Quando é uma situação em que você tem que mod? [Estudante] Se você tem coisas em espaços, como em espaços 1 e 2, e depois que você precisava para acrescentar algo a 0. [Hardison] Sim, exatamente. Então, se o ponteiro cabeça está no fim, ou se o seu tamanho, mais a sua cabeça é maior, ou melhor, vai envolver em torno da fila. 

Então, nessa situação que nós temos aqui em cima no slide agora, se eu quiser colocar na fila alguma coisa agora, queremos algo enfileirar no índice 0. Então, se você olhar para onde o 50 vai, e eu chamo enqueue 50, vai lá no fundo. Ele vai em 0 índice. Ele substitui o 'oi' que já foi retirado da fila. [Daniel] Não tome o cuidado de que em dequeue já? Por que fazer qualquer coisa com a cabeça em enqueue? [Hardison] Ah, então você não está modificando a cabeça, me desculpe. Mas você tem que usar o operador mod quando você está acessando o elemento que você quer colocar na fila quando você está acessando o próximo elemento na sua fila. [Basil] Eu não fiz isso, e eu tenho "sucesso" por lá. [Daniel] Oh, eu entendo o que você está dizendo. [Hardison] Então você didn't - você fez no q.size? [Basil] Yeah. Eu só mudou de lado, eu não fiz nada com a cabeça. [Hardison] Você realmente não tem que repor a cabeça para ser qualquer coisa, mas quando você índice na matriz cordas, você realmente tem que ir em frente e calcular onde o próximo elemento é, withe porque a pilha, o elemento seguinte na sua pilha sempre foi no índice correspondente ao tamanho. Se olharmos para trás até à nossa função push pilha, podemos sempre plunk em nosso novo elemento à direita no tamanho do índice. Considerando que, com a fila, não podemos fazer isso porque, se estamos nesta situação, se enfileirado 50 cadeia de nosso novo iria bem no strings [1] que não queremos fazer. Queremos ter a nova cadeia ir no índice 0. 

Alguém - sim? [Estudante] Eu tenho uma pergunta, mas não é realmente relacionados. O que significa quando alguém apenas chama algo como ponteiro pred? O que é que o nome curto para? Eu sei que é apenas um nome. [Hardison] ponteiro Pred? Vamos ver. Em que contexto? [Aluno] Foi para a inserção. Posso pedir-lhe mais tarde, se você quiser porque realmente não é relacionado, mas eu só - [Hardison] Do código de David inserção de aula? Podemos puxar isso e falar sobre isso. Vamos falar sobre isso a seguir, uma vez que temos de listas ligadas. 

Então, vamos muito rápido olhar para o que a função enqueue parece. Qual foi a primeira coisa que as pessoas tentaram fazer em sua linha enqueue? Para esta fila? Semelhante ao que você fez para a pilha de empurrar. O que você fez, Stella? [Stella, ininteligível] [Hardison] Exatamente. If (q.size CAPACIDADE ==) - Eu preciso colocar o meu aparelho no lugar certo - retornar falso. Zoom em um pouco. Okay. Agora, qual é a próxima coisa que temos que fazer? Assim como com a pilha, e inserida no lugar certo. E assim o que era o lugar certo para inserir essa? Com a pilha era o tamanho do índice, com isso, não é bem assim. [Daniel] Eu tenho q.head--ou - q.strings >>? >> Sim. q.strings [q.head + q.size mod CAPACIDADE]? [Hardison] Nós provavelmente deseja colocar parênteses em torno deste de modo que nós estamos começando a precedência apropriada e de modo que é cleart a todos. E definir que igual? >> Para str? >> Para str. Grande. E agora o que é a última coisa que temos de fazer? Assim como fizemos na pilha. >> Incrementar o tamanho? >> Incrementar o tamanho. Boom. E então, uma vez que o código inicial só retornou falso por padrão, nós queremos mudar isso para true se tudo passa e tudo vai bem. Tudo bem. Isso é um monte de informações para seção. Nós não somos muito mais. Nós queremos falar muito rapidamente sobre isoladamente ligados listas. Vou colocar isto para que possamos voltar a ele mais tarde. Mas vamos voltar para a nossa apresentação para apenas mais alguns slides. Então enqueue é TODO, agora temos feito isso. 

Agora vamos dar uma olhada isoladamente ligados listas. Nós conversamos sobre isso mais um pouco na palestra. Como muitos de vocês viu a demo onde tivemos pessoas desajeitadamente apontando para outros números e cada uma exploração? >> Eu estava nessa. >> O que vocês acham? Fiz isso, espero que desmistificar estes um pouco? Com uma lista, verifica-se que lidar com esse tipo que nós vamos chamar um nó. Considerando que, com a fila ea pilha que tínhamos estruturas que nós chamamos de fila na pilha, tivemos esses nova fila em tipos de pilha, aqui uma lista realmente é feita apenas de um monte de nós. Da mesma forma que as cordas são apenas um monte de chars todos alinhados ao lado do outro. Uma lista ligada é apenas um nó e outro nó e outro nó e outro nó. E, em vez de esmagar todos os nós e armazená-los em conjunto de forma contígua todos ao lado uns dos outros na memória, ter este ponteiro próximo nos permite armazenar os nós onde quer que, de forma aleatória. E, em seguida, o tipo de fio de todos eles em conjunto para o ponto de um para o outro. 

E o que era a grande vantagem que esta teve sobre uma matriz? Sobre tudo o armazenamento de forma contígua apenas preso ao lado do outro? Você se lembra? Sim? >> Alocação de memória dinâmica? >> Alocação de memória dinâmica em que sentido? [Estudante] Em que você pode continuar fazendo-o maior e você não tem que mover o conjunto inteiro? [Hardison] Exatamente. Assim, com uma matriz, quando você quer colocar um novo elemento para o meio, você tem que mudar tudo para o espaço. E como falamos com a fila, é por isso que manter o ponteiro cabeça, de modo que não estamos constantemente mudando as coisas. Porque isso fica caro, se você tem uma grande matriz e você está constantemente fazendo essas inserções aleatórias. Considerando que, com uma lista, tudo que você tem a fazer é jogá-lo em um novo nó, ajustar os ponteiros, e está feito. O que suga sobre isso? Afora o fato de que não é tão fácil de trabalhar como uma matriz? Sim? [Daniel] Bem, eu acho que é muito mais difícil de acessar um elemento específico na lista ligada? [Hardison] Você não pode simplesmente pular de um elemento arbitrário no meio da lista de relacionados. Como é que você tem que fazer isso em vez disso? >> Você tem que percorrer a coisa toda. [Hardison] Yeah. Você tem que passar por um de cada vez, uma de cada vez. É uma enorme - é uma dor. Qual é a outra - não há outra queda para isso. [Basil] Você não pode ir para a frente e para trás? Você tem que ir uma direção? [Hardison] Yeah. Então, como vamos resolver isso, às vezes? [Basil] duplamente vinculada listas? >> Exatamente. Há listas duplamente ligadas. Há também - muito? 

[Sam] É o mesmo que usar a coisa que pred - Acabei de me lembrar, não é isso que a coisa é para pred? Não é que entre dupla e individualmente? Olhar [Hardison] Vamos para o que exatamente ele estava fazendo. Então, vamos lá. Aqui está a lista de códigos. Aqui temos predptr, aqui. É isso o que você estava falando? Portanto, este foi - ele está liberando uma lista e ele está tentando armazenar um ponteiro para ele. Este não é o dobro, vinculada isoladamente-listas. Podemos falar mais sobre isso mais tarde uma vez que este está falando sobre a liberação da lista e eu quero mostrar algumas outras coisas primeiro. mas é só - é lembrar o valor de ptr [Estudante] Ah, é ponteiro precedente? Sim >>. Para que possamos então incrementar ptr-se antes que, então, livre predptr que é. Porque nós não podemos ptr livre e depois chamar ptr = ptr vem, certo? Isso seria ruim. Então vamos ver, de volta para esse cara. 

A outra coisa ruim sobre listas é que, enquanto que com uma matriz temos apenas todos os elementos próprios empilhadas lado a lado, Aqui também temos introduzido este ponteiro. Portanto, há um pedaço adicional de memória que estamos tendo de usar para cada elemento que nós estamos guardando em nossa lista. Nós temos flexibilidade, mas tem um custo. Ele vem com esse tempo, custo e ele vem com esse custo de memória também. Tempo, no sentido de que agora temos de passar por cada elemento na matriz para encontrar o índice de 10, ou que teria sido índice 10 em uma matriz. 

Só muito rapidamente, quando diagrama de fora destas listas, normalmente temos para a cabeça da lista ou o primeiro ponteiro da lista e note que este é um ponteiro verdade. É apenas 4 bytes. Não é um nó em si. Então você vê que ele não tem valor int nele, nenhum ponteiro próxima nele. É literalmente apenas um ponteiro. Vai apontar para algo que é uma estrutura de nó real. [Sam] Um ponteiro chamado nó? >> Este é - não. Este é um ponteiro para algo do tipo de nó. É um ponteiro para uma estrutura de nó. >> Ah, ok. Diagrama sobre o código, esquerda à direita. Podemos defini-lo como nulo, o que é uma boa maneira de começar. Quando você diagrama, você quer escrevê-lo como nulo ou você colocar uma linha através dele assim. 

Uma das maneiras mais fáceis de trabalhar com listas, e pedimos que tanto prepend e anexar para ver as diferenças entre os dois, prepending mas é definitivamente mais fácil. Quando você precede, este é o lugar onde você - quando você prepend (7), você vai criar a estrutura do nó e você definir primeiro a apontar para ele, porque agora, já que ele prefixado, ele vai estar no início da lista. Se prepend (3), que cria um outro nó, mas agora 3 vem antes do 7. Então estamos essencialmente empurrando as coisas para a nossa lista. Agora, você pode ver que prepend, às vezes as pessoas chamam de empurrar, porque você está empurrando um novo elemento em sua lista. Também é fácil de apagar na frente de uma lista. Então, as pessoas, muitas vezes chamada de pop. E dessa maneira, você pode emular uma pilha usando uma lista ligada. Gritos. Desculpe, agora estamos entrando em acréscimo. Então aqui nós prefixado (7), agora nós prepend (3). Se prefixado algo mais para esta lista, se prefixado (4), então temos 4 e depois 3 e depois 7. Então nós poderia pop e remover 4, remove 3, remova 7. Muitas vezes, a forma mais intuitiva de pensar sobre isso é com acréscimo. Então eu diagramado para fora o que seria parecido com acrescentar aqui. Aqui, anexado (7) não parece ser diferente porque há apenas um elemento na lista. E anexando (3) coloca-lo no final. Talvez você pode ver agora o truque com append é que desde que nós só sabemos onde o início da lista é, para anexar a uma lista que você tem que andar todo o caminho através da lista para chegar ao fim, parar, em seguida, construir o nó e tudo dólar baixo. Ligue todas as coisas para cima. Assim, com prepend, como acabamos rasgou esta muito rapidamente, quando você precede a uma lista, é bastante simples. 

Você faz o seu novo nó, envolvem algum alocação dinâmica de memória. Então aqui nós estamos fazendo um struct nó usando malloc. Então malloc estamos usando porque isso vai reservar memória para nós para mais tarde porque nós não queremos isso - nós queremos essa memória a persistir por um longo tempo. E nós temos um ponteiro para o espaço na memória que nós apenas alocado. Usamos tamanho de nó, não somar os campos. Nós não gerar manualmente o número de bytes, em vez disso, use sizeof para que saibamos que estamos recebendo um número adequado de bytes. Temos certeza de que o nosso para testar chamada malloc conseguiu. Isso é algo que você quer fazer em geral. Em máquinas modernas, a falta de memória não é algo que é fácil a menos que você está a atribuição de uma tonelada de coisas e fazer uma lista enorme, mas se você está construindo coisas para, digamos, como um iPhone ou um Android, você tem recursos limitados de memória, especialmente se você está fazendo algo intenso. Portanto, é bom para entrar em prática. 

Repare que eu usei algumas funções diferentes aqui que você já viu que são uma espécie de novo. Então fprintf é como printf exceto seu primeiro argumento é o fluxo para o qual você deseja imprimir. Neste caso, queremos imprimir para a cadeia de erro padrão que é diferente do padrão outstream. Por padrão, ele mostra-se no mesmo lugar. Ela também imprime ao terminal, mas você pode - usando os comandos que você aprendeu sobre as técnicas de redirecionamento, que você aprendeu na vídeo de Tommy por conjunto de problemas 4, você pode direcioná-lo para diferentes áreas e, depois, sair, aqui, sai do seu programa. É essencialmente como voltar da principal, exceto que nós usamos, porque aqui saída de retorno não vai fazer nada. Nós não estamos no principal, para retorno não sair do programa como nós queremos. Então, nós usamos a função de saída e dar-lhe um código de erro. Então, aqui vamos definir campo o novo nó de valor, o seu campo i igual a i, e então conectá-lo. Montamos ponteiro seguinte, o novo nó para que ele aponte para o primeiro, e depois na primeira vai agora apontar para o novo nó. Estas primeiras linhas de código, estamos realmente construindo o novo nó. Nem as duas últimas linhas desta função, mas os primeiros. Você pode realmente sair em uma função, em uma função auxiliar. Que muitas vezes é o que eu faço é, eu retirá-lo em uma função, Eu chamo-lhe algo como nó de construção, e que mantém a função prepend muito pequena, com apenas 3 linhas de então. Eu faço uma chamada para o meu função do nó de construção, e então eu tudo fio para cima. 

A última coisa que eu quero te mostrar, e eu vou deixar você fazer append e tudo o que em seu próprio país, é como iterar sobre uma lista. Há um monte de maneiras diferentes de abordar uma lista. Neste caso, vamos encontrar o comprimento de uma lista. Então, vamos começar com comprimento = 0. Isto é muito semelhante à escrita strlen para uma cadeia. Isso é o que eu quero mostrar para você, este laço for bem aqui. Parece meio funk, não é o habitual int i = 0, i <qualquer que seja, i + +. Em vez disso, está a inicializar a variável n ser o início da lista. E então, quando a nossa variável iterator não é nulo, nós continuar. Isto porque, por convenção, o fim da nossa lista será nulo. E, em seguida, para incrementar, em vez de fazer + +, o equivalente lista ligada de + + é n = n-> seguinte. 

Eu vou deixar você preencher as lacunas aqui porque estamos fora do tempo. Mas manter isso em mente como você trabalhar em Série de Exercícios seus spellr. Listas ligadas, se você está implementando uma tabela hash, vai certamente ser muito útil. E, tendo esta expressão para looping sobre as coisas vão tornar a vida muito mais fácil, eu espero. Qualquer dúvida, rapidamente? [Sam] Será que você enviar o sll concluído e sc? [Hardison] Yeah. Eu vou enviar lâminas concluídas e pilha sll concluído e queue.cs. [CS50.TV]