[Powered by Google Translate] [Semana 6] [David J. Malan] [Harvard University] [Esta é CS50.] [CS50.TV] 

Este é CS50, e este é o início da semana 6, assim um par de novas ferramentas estão agora disponíveis para você aproveitar, o primeiro dos quais é chamado CS50 estilo. As probabilidades são, se você é como eu ou qualquer um dos companheiros de ensino, você provavelmente já viu um programa cujo estilo parece um pouco algo como isto. Talvez você começar a cortar alguns cantos, tarde da noite, ou você vai lidar com isso mais tarde, e então um TF ou CA vem mais durante o expediente. Então é difícil para nós ler. Bem, esse código é sintaticamente correta, e ele irá compilar e ele vai realmente funcionar. Mas definitivamente não é um 5 para o estilo. 

Mas agora, se vamos para este diretório aqui- e perceber que eu tenho conditions2.c- e eu corro esse novo comando, style50, nesta conditions2.c arquivo, Enter perceber que ele me informou que foi estilizado. Gedit percebeu que o arquivo foi alterado no disco, e se eu clicar em recarregar, todos os seus problemas estão agora automatizado. [Aplausos] Isso é uma das coisas que fizemos neste fim de semana. Perceber que ele é imperfeito porque há algum código que simplesmente não será capaz de estilizar perfeitamente, mas que esta é agora uma ferramenta que você pode tirar vantagem de se apenas para arrumar algumas das chaves mais errantly colocado cacheados e afins. 

Mas o mais interessante agora é CS50 Check. Com CS50 Check, você pode realmente realizar os testes de correção mesmos em seu próprio código que os companheiros de ensino são capazes de. Este é um utilitário de linha de comando que vem agora no aparelho assim que você fizer uma update50 como por pset quatro especificações, e usá-lo essencialmente como este. Você corre o check50 comando. Então você passa em um argumento de linha de comando, ou, mais geralmente conhecido como um interruptor ou uma bandeira. Geralmente, as coisas que têm hífens são chamados um interruptor a um programa de linha de comando, assim c especifica as verificações que você deseja executar. 

Os testes que você deseja executar são identificados individualmente por essa seqüência, 2012/pset4/resize. Em outras palavras, isso é apenas uma seqüência arbitrária, mas única que usamos para identificar testes 4 pset de correção. E então você especificar uma lista separada por espaço dos arquivos que você deseja carregar Verifique a CS50 para análise. Por exemplo, se eu ir para a minha solução aqui para resize.c- deixe-me abrir um maior terminal de janela e eu ir em frente e correr digamos check50-c 2012/pset4/resize, e então eu ir em frente e especificar os nomes dos arquivos, resize.c, e pressione a tecla Enter, ele comprime, ele carrega, ele verifica, e eu só falhou um monte de testes. O de vermelho no canto superior esquerdo diz que resize.c e bmp existe. Esse foi o teste. Essa foi a pergunta que nós fizemos. E é infeliz porque a resposta era falsa. O texto em branco abaixo diz esperar bmp.h de existir, e isso é simplesmente culpa minha. Eu esqueci de enviá-lo, então eu preciso fazer upload de dois arquivos, resize.c e bmp.h. Mas agora observar todos os outros testes são em amarelo porque não correr, e assim o rosto sorridente é vertical, porque ele não é nem feliz nem triste, mas temos que corrigir esse problema no vermelho antes de essas outras verificações será executado. 

Deixe-me corrigir isso. Deixe-me afastar e executar novamente essa, desta vez com bmp.h também na linha de comando, Enter, e agora, se tudo correr bem, que vai verificar e retornar um resultado de-segure a respiração- tudo verde, o que significa que eu estou indo muito bem em pset 4 até agora. Você pode ver e inferir do texto descritivo aqui exatamente o que é que testamos. Testamos primeiro é que os arquivos existem? Em seguida, testamos faz compilação resize.c? Então nós testamos não é redimensionar uma BMP 1x1 pixel quando n, o fator de redimensionamento, é 1. Agora, se você não tem idéia do que n é, você vai uma vez que você mergulhar pset 4, mas que simplesmente é uma verificação de sanidade para se certificar de que você não é o redimensionamento uma imagem em todos, se o fator de redimensionamento é 1. Se, pelo contrário, ele redimensiona um pixel 1x1 para um 1x1 pixel BMP para 2x2 corretamente quando n é 2, então de forma semelhante, formas mina em conformidade. 

Em suma, este é significado, um, pegue a travessia dos dedos fora da equação direita antes de enviar seu pset. Você saberá exatamente o que o seu TF logo saberá quando você vai sobre o envio de alguns desses conjuntos de problemas, e também a motivação pedagógica é realmente colocar a oportunidade na frente de você para que, quando você sabe a priori que não há erros em seu código e testes que não estão sendo passados, você pode colocar mais eficaz do tempo na frente para resolver esses problemas em vez de perder pontos, obter feedback de seu TF, e depois ir, "Ahh," como eu deveria ter percebido isso. Agora, pelo menos, há uma ferramenta para ajudar a encontrar isso. Ele não vai apontar onde é o erro, mas ele vai dizer o que é um sintoma da mesma. 

Agora realizar os testes não são necessariamente exaustiva. Só porque você tem uma tela cheia de verde Smiley Faces não significa que seu código é perfeito, mas isso não significa que ele passou alguns testes prescritos pela especificação. Às vezes a gente não vai liberar cheques. Por exemplo, whodunit, um dos aspectos da pset 4, é tipo de decepcionante se nós lhe damos a resposta para o que ele é, e há uma série de maneiras para revelar quem é a pessoa em que o ruído vermelho. A especificação será sempre especificar no futuro para pset em diante 5 o que verifica existir para você. Você vai perceber que há essa URL em branco no fundo. Por enquanto, esta é apenas a saída de diagnóstico. Se você visitar a URL, você vai ter um monte de loucos, mensagens enigmáticas que você está convidado a olhar através, mas é principalmente para o pessoal para que possamos diagnosticar e depurar erros em check50 si. 

Sem delongas, vamos seguir em frente de onde paramos. CS50 biblioteca tomamos para concedido por algumas semanas, mas, em seguida, na semana passada, começamos a descascar para trás uma das camadas do mesmo. Começamos colocando de lado cadeia em favor do que em vez disso? [Os alunos] Char. * Char, que tem sido um char * todo esse tempo, mas agora não temos que fingir que é um tipo string de dados real. Em vez disso, tem sido sinônimo de sorte para char *, e uma string é uma seqüência de caracteres, Então, por que será que faz sentido para representar strings como char * s? O que faz um char * representam no contexto desse conceito de uma string? Sim. >> [Estudante] O primeiro caractere. Bom, o primeiro caractere, mas não é bem o primeiro caractere. É uma [Os alunos] Endereço. Bom, o endereço do primeiro caractere. Tudo que é necessário para representar uma cadeia em memória de um computador é apenas o endereço exclusivo do seu byte primeiro. Você não tem sequer de saber quanto tempo é pois como você pode descobrir isso dinamicamente? [Estudante] comprimento String. Você pode chamar comprimento da corda, excelente, mas como funciona o comprimento da corda? O que ele faz? Sim. [Estudante] Continue indo até chegar o caractere nulo. Sim, exatamente, ele só interage com um loop for, while, qualquer que seja a partir de * até ao fim, e que o fim está representada por \ 0, o personagem chamado nulo, nulo, não deve ser confundida com nulo, o que é um ponteiro, que entrará na conversa de novo hoje. 

Nós descascado uma camada de GetInt, e depois demos uma olhada no GetString, e lembrar que essas duas funções, ou realmente, GetString, estava usando uma determinada função para realmente analisar, isto é, ler ou analisar, a entrada do usuário. E o que foi que nova função? Scanf ou sscanf. Ele realmente vem em alguns sabores diferentes. Há scanf, há sscanf, há fscanf. Por enquanto, porém, vamos focar o mais facilmente ilustrado, e deixe-me ir em frente e abrir no aparelho um arquivo como este, scanf1.c. Este é um programa super simples, mas que faz algo que nunca fizemos sem a ajuda da biblioteca CS50. Este recebe um int de um usuário. Como isso funciona? Bem, na linha 16 há, perceber que nós declaramos um int x chamado, e neste momento da história, o que é o valor de x? [Resposta do aluno inaudível] [David M.] Direito, quem sabe, algum valor lixo potencialmente, assim, em 17, nós apenas dizer que o usuário me dar um número, por favor, e passo 18 é onde fica interessante. Scanf parece emprestar uma idéia de printf em que ele usa esses códigos de formato entre aspas. D% é, naturalmente, um número decimal. Mas por que estou passando & x em vez de apenas x? O primeiro é correta. Sim. [Resposta do aluno inaudível] Exatamente, se o objetivo do programa, como o GetInt própria função, é para ter uma int do usuário que pode passar funções todas as variáveis ​​que eu quero, mas se eu não passá-los por referência ou por endereço ou por ponteiro, todos sinônimos para fins de hoje, em seguida, que a função não tem capacidade de alterar o conteúdo da variável. Isto passaria em uma cópia assim como a versão de buggy de swap que nós já conversamos sobre algumas vezes agora. 

Mas em vez disso, fazendo & x, eu estou literalmente passando o que? [Aluno] O endereço. >> O endereço de x. É como desenhar um mapa para a função chamada scanf e dizendo aqui, estas são as direcções para um bloco de memória no computador que você pode ir armazenar algum inteiro dentro Para que sscanf para fazer agora que o operador, o que parte da sintaxe é que vai ter que usar mesmo que não possa vê-lo porque alguém escreveu essa função? Em outras palavras - o que é isso? [Estudante] X ler. Não vai ser uma leitura, mas apenas em relação à x aqui. Se scanf está sendo passado o endereço de x, sintaticamente, o operador é obrigado a existir em algum lugar dentro de implementação, de modo que scanf scanf pode realmente escrever um número de 2 a esse endereço? Sim, então o *. Lembre-se de que o * é o nosso operador dereference, o que essencialmente significa ir para lá. 

Assim que tiver sido entregue um endereço, como é o caso aqui, scanf é, provavelmente, se nós realmente olhou em torno de seu código-fonte está fazendo * x ou o equivalente a realmente ir para esse endereço e colocar algum valor lá. Agora, o modo como scanf recebe a entrada do teclado, vamos agitar as mãos para fora para hoje. Basta assumir que o sistema operacional permite que sscanf para falar para o teclado do usuário, mas neste ponto agora na linha 19, quando simplesmente imprimir x, parece ser o caso scanf que colocou um int em x. Isso é exatamente como scanf funciona, e lembrar na semana passada é exatamente como GetString e GetInt e sua outra família de funções finalmente funciona, embora com ligeira variação como sscanf, o que significa digitalizar uma cadeia em vez do teclado. Mas vamos dar uma olhada em uma pequena variação desta. Em scanf2, eu realmente errou. O que está errado, e eu vou esconder o comentário que explica como muito o que está errado com este programa, a versão 2? Seja tão técnico como possível neste momento. Ele parece muito bom. É bem recuado, mas- Ok, que tal vamos podá-la para baixo para perguntas mais curtos? Linha 16. O que é linha 16 fazendo em Inglês, mas precisa técnico? Ficando um pouco estranho. Sim, Michael. [Estudante] Está apontando para a primeira letra de uma string. 

Ok, perto. Deixe-me ajustar isso um pouco. Apontando para a primeira letra de uma string, você está declarando uma variável chamada tampão que irá apontar para o primeiro endereço de uma string, ou seja, que irá apontar mais precisamente a uma char. Note que não é realmente apontando para qualquer lugar, porque não há operador de atribuição. Não há sinal de igual, então tudo o que estamos fazendo é alocação de reserva variável chamada. Ele passa a ser de 32 bits porque é um ponteiro, e o conteúdo de tampão, eventualmente, presumivelmente conterá um endereço de um char, mas por agora, o que tampão contém? Apenas alguns falso, quem sabe, algum valor de lixo, porque não explicitamente inicializado, então não devemos assumir nada. Ok, então agora é a linha 17-o que faz a linha 17 faz? Talvez que vai aquecer isso. Ela imprime uma string, certo? Ela imprime Cordas por favor. 

Linha 18 é uma espécie de familiar agora em que acabamos de ver uma variação deste mas com um código de formato diferente, por isso, em linha 18, estamos dizendo scanf aqui é o endereço de um bloco de memória. Eu quero que você tocar em uma corda, como implicado por% s, mas o problema é que não temos feito algumas coisas aqui. O que é um dos problemas? [Estudante] Está tentando dereference um ponteiro nulo. Bom, ponteiros nulos ou apenas outra maneira desconhecido. Você está entregando scanf um endereço, mas você disse há pouco que esse endereço é algum valor lixo porque nós realmente não atribuí-lo a nada, e por isso você está dizendo scanf efetivamente ir colocar uma corda aqui, mas não sei onde aqui ainda é, então nós realmente não tenho memória alocada para buffer. Além disso, o que você também não, mesmo dizendo scanf? Suponha que este era um pedaço de memória, e não era um valor de lixo, mas você ainda não está dizendo scanf algo importante. [Estudante] onde ele realmente é, o comercial. Ampersand, portanto, neste caso, está tudo bem. Porque o buffer já está declarado como um ponteiro com a peça * de sintaxe, nós não precisamos de usar e comercial porque é já um endereço, mas eu acho que ouvi-lo aqui. [Estudante] Como grande é? Bom, não estamos dizendo scanf quão grande esse buffer é, o que significa que, mesmo se fosse um tampão ponteiro, estamos dizendo scanf, colocar uma corda aqui, mas aqui pode ser de 2 bytes, que pode ser de 10 bytes, que poderia ser um megabyte. Scanf não tem idéia, e porque este é um pedaço da memória presumivelmente, não é uma seqüência ainda. É apenas uma corda uma vez que você escrever caracteres e um \ 0 para o bloco de memória. Agora é só algum pedaço de memória. Scanf não vai saber quando parar de escrever para esse endereço. 

Se você lembrar alguns exemplos no passado em que eu aleatoriamente digitados no teclado tentando estourar um buffer, e nós conversamos na sexta-feira sobre exatamente isso. Se um adversário de alguma forma, injeta em seu programa uma palavra muito maior ou frase ou então você estava esperando você pode invadida um pedaço de memória, que pode ter conseqüências ruins, como assumir todo o programa em si. Precisamos corrigir isso de alguma forma. Deixe-me afastar e ir para a versão 3 do programa. Isso é um pouco melhor. Nesta versão, notar a diferença. Na linha 16, estou novamente declarar uma variável chamada tampão, mas o que é isso agora? É uma matriz de 16 caracteres. Isso é bom, porque isso significa que eu posso agora dizer scanf aqui é um pedaço de memória real. Você quase pode pensar em matrizes como ponteiros, agora, mesmo que eles não são realmente equivalentes. Eles se comportam de maneira diferente em diferentes contextos. Mas é certamente o caso que o buffer é referência 16 caracteres contíguos porque é isso que é uma matriz e tem sido por algumas semanas agora. 

Aqui, eu estou dizendo scanf aqui está um pedaço da memória. Desta vez, é na verdade um pedaço da memória, mas porque é que este programa ainda explorável? O que há de errado ainda? Eu disse me dar 16 bytes, mas- [Aluno] O que se eles tipo em mais de 16 anos? Exatamente, e se o usuário digita 17 caracteres ou caracteres 1700? Na verdade, vamos ver se não podemos tropeçar esse erro agora. É melhor, mas não perfeito. Deixe-me ir em frente e correr fazer scanf3 para compilar este programa. Deixa-me correr scanf3, String por favor: Olá, e parece que estamos bem. Deixe-me tentar um pouco mais, Olá lá. Ok, vamos fazer Olá lá como você está hoje, Enter. Obtendo tipo de sorte aqui, vamos dizer Olá lá como você está. Droga. Ok, então tivemos sorte. Vamos ver se não podemos consertar isso. Não, isso não vai me deixar copiar. Vamos tentar de novo. Tudo bem, preparem-se. Vamos ver quanto tempo eu posso fingir foco enquanto ainda está fazendo isso. Droga. Isso é bastante apropriado, na verdade. Lá vamos nós. Ponto feito. 

Isto, embaraçando embora também seja, é também uma das fontes de grande confusão ao escrever programas que têm bugs, porque eles se manifestam só de vez em quando, às vezes. A realidade é que, mesmo se o código está completamente quebrado, ele só poderia ser completamente quebrado de vez em quando porque às vezes, essencialmente, o que acontece é o sistema operacional aloca um pouco mais de memória do que você realmente precisa, por qualquer razão, e para que ninguém mais está usando a memória logo após o seu pedaço de 16 caracteres, por isso, se você vai para 17, 18, 19, qualquer que seja, não é um negócio tão grande. Agora, o computador, mesmo que não falha nesse ponto, pode, eventualmente, usar o número de bytes de 17 ou 18 ou 19 para outra coisa, altura em que os dados que você colocar ali, ainda que excessivamente longo, vai ser substituídas potencialmente por alguma outra função. Não é necessariamente vai permanecer intacta, mas não vai necessariamente provocar uma falha seg. Mas, neste caso, eu finalmente desde caracteres suficientes que eu essencialmente ultrapassado meu segmento de memória, e pronto, o sistema operacional, disse: "Desculpe, isso não é falha de segmentação de boa qualidade." 

E vamos ver agora se o que permanece aqui no meu diretório perceber que eu tenho esse arquivo aqui, o núcleo. Note-se que esta é mais uma vez chamado de core dump. É essencialmente um arquivo que contém o conteúdo da memória de seu programa no ponto em que deixou de funcionar, e apenas para tentar um pequeno exemplo aqui, deixe-me entrar aqui e executar o gdb no scanf3 e especifique um terceiro argumento chamado de núcleo, e notar aqui que se eu listar o código, nós vamos ser capazes, como de costume com o gdb para começar a caminhar através deste programa, e eu possa executá-lo e assim que eu bater-como com o comando passo na gdb- assim que atingiu a linha de buggy potencialmente depois de digitar uma seqüência enorme, Eu vou ser capaz de realmente identificá-lo aqui. Mais sobre isso, no entanto, na seção em termos de core dumps e assim por diante, de modo que você pode realmente bisbilhotar dentro do core dump e ver em que linha o programa não você. Quaisquer perguntas, então em ponteiros e endereços? Porque hoje, nós vamos começar a tomar por certo que essas coisas existem e sabemos exatamente o que eles são. Sim. 

[Estudante] Como é que você não tem que colocar um comercial ao lado da parte- Boa pergunta. Como é que eu não tenho que colocar um comercial ao lado da matriz de caracteres como eu fiz anteriormente com a maioria dos nossos exemplos? A resposta curta é matrizes são um pouco especial. Você quase pode pensar um tampão como sendo realmente um endereço, e isso só acontece de ser o caso de que a notação de colchete é uma conveniência para que possamos entrar em suporte 0, faixa 1, faixa 2, sem ter de utilizar a notação *. Isso é um pouco de uma mentira porque as matrizes e ponteiros são, na verdade, um pouco diferente, mas que muitas vezes pode, mas nem sempre ser usados ​​indistintamente. Em suma, quando a função está esperando um ponteiro para um bloco de memória, você pode passar um endereço que foi retornado por malloc, e vamos ver malloc novamente antes de tempo, ou você pode passar-lhe o nome de uma matriz. Você não tem de fazer comercial com matrizes porque eles já estão essencialmente, como endereços. Essa é a única exceção. Os colchetes tornam especiais. 

Você poderia colocar um comercial ao lado do tampão? Não neste caso. Isso não iria funcionar porque, novamente, desta canto caso onde matrizes não são muito realmente endereços. Mas vamos talvez volte para que em pouco tempo com outros exemplos. Vamos tentar resolver um problema aqui. Temos uma estrutura de dados que temos vindo a utilizar durante algum tempo conhecida como uma matriz. O caso em questão, é o que acabamos de ter. Mas matrizes têm algum upsides e desvantagens. Matrizes são agradáveis ​​porque? O que é uma coisa que você gosta, na medida em que você gosta matrizes-sobre matrizes? O que é conveniente sobre eles? O que é interessante? Por que nós apresentá-los em primeiro lugar? Sim. [Estudante] Eles podem armazenar uma grande quantidade de dados, e você não tem que usar uma coisa toda. Você pode usar uma seção. Bom, com uma matriz você pode armazenar uma grande quantidade de dados, e você não necessariamente tem que usar tudo isso, para que você possa overallocate, o que pode ser conveniente se você não sabe de antemão quantos de algo que esperar. 

GetString é um exemplo perfeito. GetString, escrito por nós, não tem idéia de quantos chars que esperar, de modo que o fato de que podemos alocar blocos de memória contígua é bom. Matrizes também resolver um problema que vimos há algumas semanas agora onde o código começa a transformar-se em algo muito mal projetado. Lembre-se que eu criei uma estrutura estudante chamado David, e depois que foi realmente uma alternativa, porém, a ter uma variável chamada nome e outra variável chamada, eu acho, casa, e outra variável chamada ID, porque nessa história então eu queria introduzir algo mais Rob gosta no programa, então eu decidi esperar um minuto, Eu preciso mudar o nome destas variáveis. Vamos chamar de meu nome1, ID1, house1. Vamos chamar de Rob nome2, house2, ID2. Mas, então, espere um minuto, o que dizer de Tommy? Então nós tivemos três variáveis ​​mais. Nós introduzimos alguém, quatro conjuntos de variáveis. O mundo começou a ficar confuso muito rapidamente, para que introduziu estruturas, eo que é interessante sobre uma estrutura? O que faz um struct C permitem que você faça? É realmente estranho hoje. O quê? >> [Resposta do aluno inaudível] Sim, especificamente, typedef permite criar um novo tipo de dados, e estrutura, a palavra-chave struct, permite encapsular peças conceitualmente relacionados de dados juntamente e, posteriormente, chamá-los de algo como um estudante. 

Isso foi bom, porque agora podemos modelar espécie muito mais consistente conceitualmente a noção de um estudante em uma variável em vez de ter uma forma arbitrária para uma cadeia, um para um ID, e assim por diante. Matrizes são bons porque eles nos permitem começar a limpar o nosso código. Mas o que é uma desvantagem agora de uma matriz? O que você não pode fazer? Sim. [Estudante] Você tem que saber o quão grande ela é. Você tem que saber como é grande, por isso é um tipo de dor. Aqueles de vocês com experiência anterior em programação sabe que em um monte de línguas, como Java, você pode pedir um pedaço de memória, especificamente uma matriz, quão grande é você, com um comprimento de, propriedade, por assim dizer, e isso é realmente conveniente. Em C, você não pode sequer chamar strlen em uma matriz genérica porque strlen, como a palavra indica, é apenas para cordas, e você pode descobrir o comprimento de uma cadeia por causa deste convenção humana de ter um \ 0, mas um conjunto, mais genericamente, é apenas um pedaço de memória. Se é uma matriz de inteiros, não vai ser algum caractere especial no final esperando por você. Você tem que lembrar o comprimento de uma matriz. Outro ponto negativo de uma matriz elevou sua cabeça em GetString si. O que é outra desvantagem de uma matriz? Senhor, só eu e você hoje. [Resposta do aluno inaudível] >> É o quê? Ele é declarado na pilha. Ok, declarou na pilha. Por que você não gosta? [Estudante], porque ela é reutilizada. Ele fica reutilizados. Ok, se você usar uma matriz para alocar memória, você não pode, por exemplo, devolvê-lo, porque é na pilha. Ok, isso é uma desvantagem. E quanto a um outro com uma matriz? Uma vez que você afectá-lo, você é do tipo parafusado, se você precisar de mais espaço do que a matriz tem. 

Então, nós introduzimos, malloc recall, que nos deu a capacidade de alocar dinamicamente a memória. Mas o que se tentou um mundo completamente diferente? O que se queria resolver alguns desses problemas por isso, em vez minha caneta-dorme aqui- o que se queria essencialmente em vez de criar um mundo que já não é assim? Trata-se de uma matriz, e, é claro, este tipo de deterioração, uma vez que atingiu o fim da matriz, e agora não tem mais espaço para outro inteiro ou outro personagem. E se nós meio que preventivamente dizer bem, por que não vamos relaxar esta exigência de que todos esses pedaços de memória ser contíguo volta para trás, e por que não, quando eu preciso de um int ou um char, me dê espaço para um deles? E quando eu precisar de outro, dá-me um outro espaço, e quando eu precisar de outro, dá-me um outro espaço. A vantagem de que agora é que, se alguém leva a memória por aqui, não é grande coisa. Vou levar este pedaço adicional de memória aqui e depois este. 

Agora, o único problema aqui é que esta quase se sente como eu tenho todo um conjunto de variáveis ​​diferentes. Isso sente-se como cinco diferentes variáveis ​​potencialmente. Mas o que se roubar uma idéia de cordas em que, de alguma maneira vincular essas coisas juntas conceitualmente, e que se eu fizesse isso? Esta é a minha flecha muito mal desenhado. Mas suponha que cada um desses pedaços de memória apontou para o outro, e esse cara, que não tem nenhum irmão à sua direita, não tem nenhuma seta tal. Este é de fato o que é chamado de uma lista ligada. Esta é uma nova estrutura de dados que nos permite alocar um bloco de memória, depois outra, depois outra, depois outra, a qualquer hora que queremos durante um programa, e lembre-se que todos eles são de alguma forma relacionados por, literalmente, encadeando-os, e nós fizemos isso pictoricamente aqui com uma seta. Mas no código, o que seria o mecanismo através do qual você pudesse de alguma forma se conectar, quase como Scratch, um pedaço de um outro pedaço? Nós poderíamos usar um ponteiro, certo? Porque realmente a seta que vai da praça superior esquerdo, esse cara aqui a esta, poderia conter dentro da praça não apenas alguns ints, não apenas alguns char, mas o que se eu realmente alocada um pouco de espaço extra para que agora, cada um dos meus pedaços de memória, mesmo que isso vai me custar, agora parece um pouco mais rectangular em que um dos blocos de memória é utilizado para um número, assim como o número 1, e, em seguida, se este tipo armazena o número 2, este pedaço de outra memória é usada para uma seta, ou mais concretamente, um ponteiro. E suponha que eu armazenar o número 3 por aqui, enquanto eu uso isso para apontar para esse cara, e agora esse cara, vamos supor que eu só quero esses três pedaços de memória. Eu vou desenhar uma linha por isso, indicando nulo. Não há personagem adicional. 

Na verdade, esta é a forma como nós podemos ir sobre a implementação de algo que é chamado de uma lista ligada. Uma lista ligada é uma nova estrutura de dados, e é um trampolim para a muito amador estruturas de dados que começam a resolver problemas ao longo das linhas de Facebook tipo de problemas e problemas do tipo Google onde você tem enormes conjuntos de dados, e já não corta para armazenar tudo de forma contígua e usar algo como busca linear ou mesmo algo como pesquisa binária. Você quer mesmo melhores tempos de execução. De fato, um dos objetivos primordiais vamos falar mais tarde esta semana ou na próxima é um algoritmo cujo tempo de corrida é constante. Em outras palavras, tem sempre a mesma quantidade de tempo, não importa como é grande a entrada, e que seria de fato interessante, até mais do que algo logarítmica. O que é isso na tela aqui? Cada um dos retângulos é exatamente o que eu desenhei a mão. Mas a coisa toda a maneira à esquerda é uma variável especial. Vai ser um ponteiro único porque a única pegadinha com uma lista ligada, como essas coisas são chamados, é que você tem para se agarrar a uma final da lista de relacionados. 

Assim como com uma corda, você tem que saber o endereço do primeiro caractere. Mesma coisa para listas ligadas. Você tem que saber o endereço do primeiro pedaço de memória porque de lá, você pode chegar a qualquer um outro. Desvantagem. Qual o preço que estamos pagando por essa versatilidade de ter um dinamicamente estrutura de dados de tamanho considerável que se alguma vez precisar de mais memória, tudo bem, simplesmente alocar mais um pedaço e desenhar um ponteiro de da antiga para a nova cauda da lista? Sim. [Estudante] É preciso espaço de cerca de duas vezes mais. Ele ocupa um espaço duas vezes maior, de modo que é definitivamente uma desvantagem, e temos visto isso troca antes entre tempo e espaço e flexibilidade onde por agora, não precisamos de 32 bits para cada um desses números. Nós realmente precisamos de 64, 32 para o número e 32 para o ponteiro. Mas, ei, eu tenho 2 gigabytes de memória RAM. Adicionando mais 32 bits aqui e aqui não parece que de um grande negócio. Mas para grandes conjuntos de dados, definitivamente acrescenta-se, literalmente, o dobro. O que é outra desvantagem agora, ou o que é que vamos característica desistir, se representar listas de coisas com uma lista ligada e não uma matriz? [Estudante] Você não pode atravessá-lo para trás. Você não pode atravessá-lo para trás, então você é do tipo parafusado, se você está andando da esquerda para a direita, com um loop ou um loop while e então você percebe, "Oh, eu quero voltar para o início da lista." Você não pode porque estes ponteiros só ir da esquerda para a direita, como as setas indicam. 

Agora, você poderia lembrar o início da lista, com uma outra variável, mas isso é uma complexidade para manter em mente. Uma matriz, não importa o quão longe você vá, você sempre pode fazer menos, menos, menos, menos e voltar de onde você veio. O que é outra desvantagem aqui? Sim. [Pergunta estudante inaudível] Você poderia, então você realmente acabou de propor uma estrutura de dados chamado de lista duplamente ligada, e, na verdade, você gostaria de acrescentar outro ponteiro para cada um desses rectângulos que vai outra direcção, ao contrário do que é que agora você pode atravessar para o outro, a desvantagem de que agora você está usando três vezes mais memória do que costumávamos e também aumentar a complexidade em termos de código que você tem que escrever para acertar. Mas todos estes são talvez compensações razoáveis, se a reversão é mais importante. Sim. [Estudante] Você também não pode ter uma lista 2D vinculado. Bom, você não pode realmente ter uma lista 2D ligados. Você poderia. Não é tão fácil como uma matriz. Como um array, você faz suporte aberto, suporte fechada, suporte aberto, fechado suporte, e você terá uma estrutura 2-dimensional. Você poderia implementar uma lista de 2-dimensional ligados Se você adicionar, como você propôs-um ponteiro terceiro a cada uma dessas coisas, e se você pensar em uma outra lista que vem em você estilo 3D da tela para todos nós, que é apenas uma outra corrente de algum tipo. Nós poderíamos fazer isso, mas não é tão simples como escrever suporte aberto, colchete. Sim. [Pergunta estudante inaudível] Bom, então isso é um retrocesso real. 

Esses algoritmos que temos pined mais, como oh, busca binária, você pode pesquisar uma matriz de números na placa ou um livro de telefone muito mais rapidamente se utilizar dividir e conquistar e um algoritmo de busca binária, mas busca binária necessários dois pressupostos. Um, que os dados foram classificados. Agora, nós podemos manter este presumivelmente classificados, talvez por isso não é uma preocupação, mas de busca binária também assumiu que você teve acesso aleatório à lista de números, e uma matriz permite que você tenha acesso aleatório, e de acesso aleatório, Quero dizer, se você está dado uma matriz, quanto tempo leva para você para chegar ao suporte de 0? Uma operação, basta usar [0] e você está aí. Quantos passos que é preciso para chegar ao local 10? Um passo, é só ir para [10] e você está lá. Por outro lado, como você começa para o número inteiro 10 em uma lista ligada? Você tem que começar no início, porque você só está lembrando o início de uma lista ligada, como uma string está sendo lembrado pelo endereço de seu primeiro char, e ao descobrir que int 10 ou que o caráter 10 em uma seqüência, você tem que procurar a coisa toda. 

Novamente, não estamos resolvendo todos os nossos problemas. Estamos introduzindo novos, mas realmente depende do que você está tentando projetar para. Em termos de aplicação do presente, podemos pedir uma idéia de que a estrutura do aluno. A sintaxe é muito semelhante, só que agora, a idéia é um pouco mais abstrato de casa e nome e ID. Mas proponho que nós poderíamos ter uma estrutura de dados em C que é chamado de nó, como a última palavra sobre o slide sugere, dentro de um nó, e um nó é apenas um contêiner genérico em ciência da computação. Geralmente é desenhada como um círculo ou um quadrado ou retângulo, como temos feito. E nesta estrutura de dados, que tem um int, n, de modo que é o número que eu quiser armazenar. Mas o que é essa segunda linha, struct node * próximo? Por que isso é correto, ou qual o papel que este jogo coisa, mesmo que seja um pouco enigmática, à primeira vista? Sim. [Resposta do aluno inaudível] Exatamente, por isso o tipo * do espólio que é um ponteiro de algum tipo. O nome deste ponteiro é arbitrariamente seguinte, mas poderíamos ter chamado qualquer coisa que queremos, mas o que faz este ponto ponteiro para? [Estudante] Outro nó. >> Exatamente, ele aponta para outro nó tal. 

Agora, isso é uma espécie de curiosidade de C. Lembre-se que C é lido por um top compilador para baixo, da esquerda para a direita, que significa que se-isso é um pouco diferente do que fizemos com o aluno. Quando definimos um estudante, que se não colocar uma palavra lá. Ele apenas disse typedef. Então nós tivemos int id nome, corda, corda casa, e, em seguida, na parte inferior do estudante da estrutura. Esta declaração é um pouco diferente, porque, novamente, o compilador C é um pouco idiota. Ele só vai ler de cima para baixo, assim que se atinge a linha 2 aqui onde próxima está declarada e vê Oh, aqui está uma variável chamada seguinte. É um ponteiro para um nó de estrutura. O compilador vai perceber o que é um nó de estrutura? Eu nunca ouvi falar dessa coisa antes, porque o nó palavra não poderiam aparecer até o fundo, para que haja esta redundância. Você tem que dizer nó struct aqui, o que você pode encurtar mais tarde graças a typedef aqui, mas isso é porque estamos referenciando a estrutura em si no interior da estrutura. Essa é a única pegadinha aí. 

Alguns problemas interessantes vão surgir. Temos uma lista de números. Como vamos inserir nele? Como é que vamos busca-lo? Como podemos excluir isso? Especialmente agora que temos de gerir todos esses ponteiros. Você pensou ponteiros eram uma espécie de alucinante quando você tinha um deles apenas tentando ler um int para ele. Agora, temos de manipular o valor de uma lista inteira. Por que não vamos tomar o nosso intervalo de 5 minutos aqui, e então nós vamos trazer algumas pessoas até ao palco para fazer exatamente isso. 

C é muito mais divertido quando é encenado. Quem iria literalmente gostaria de ser o primeiro? Ok, vamos lá para cima. Você está em primeiro lugar. Quem gostaria de ser o 9? Ok, 9. Como cerca de 9? 17? A panelinha aqui. 22 e 26 em que a linha da frente. E então, que tal alguém ali sendo apontada. Está 34. Ok, de 34 anos, vem para cima. Primeiro está ali. Ok, todos os quatro de vocês. E quem foi que disse para 9? Quem é o nosso 9? Quem realmente quer ser 9? Tudo bem, vamos lá, ser 9. Aqui vamos nós. 34, nós vamos encontrá-lo por lá. A primeira parte é fazer-vos olhar como aquele. 26, 22, 17, bom. Se você pode estar ao lado, porque estamos indo para malloc você em um momento. 

Bom, muito bom. Ok, excelente, por isso vamos pedir um par de perguntas aqui. E, na verdade, qual é o seu nome? >> Anita. Anita, tudo bem, venha até aqui. Anita vai nos ajudar a resolver um tipo de pergunta bastante simples, em primeiro lugar, que é como você encontrar ou não um valor está na lista? Agora, observe que o primeiro, representado aqui por Lucas, é um pouco diferente, e por isso seu pedaço de papel é deliberadamente de lado porque não é tão alto e não toma-se como muitos bits, embora tecnicamente ele tem o mesmo tamanho de papel apenas rodado. Mas ele é um pouco diferente, já que ele tem apenas 32 bits para um ponteiro, e todos esses caras são de 64 bits, metade dos quais é o número, metade dos quais é um ponteiro. Mas o ponteiro não é retratado, por isso, se vocês pudessem um pouco sem jeito use a mão esquerda para apontar para a pessoa ao seu lado. E você é o número 34. Qual é o seu nome? Ari. Ari, portanto, na verdade, manter o papel em sua mão direita, ea mão esquerda vai direto para baixo. Você declara nulo à esquerda. 

Agora o nosso retrato humano é muito consistente. Isto é, na verdade, como os ponteiros trabalhar. E se você pode amassar um pouco dessa forma que eu não estou no seu caminho. Anita aqui, encontrar-me o número 22, mas assumir uma restrição de não seres humanos segurando pedaços de papel, mas esta é uma lista, e você só tem Lucas para começar porque ele é, literalmente, o primeiro ponteiro. Suponha que você mesmo é um ponteiro, e para que você também tem a capacidade de apontar algo. Por que você não começar por apontar exatamente o que Lucas está apontando? Bom, deixe-me e aprovar isso aqui. Apenas por uma questão de discussão, deixe-me puxar para cima uma página em branco aqui. Como se escreve o seu nome? >> Anita. Ok, Anita. Digamos nó * anita = lucas. Bem, não devemos chamá-lo de Lucas. Devemos chamá-lo primeiro. Por que isso é de fato consistente com a realidade aqui? Um, primeiro já existe. Primeiro foi alocado em algum lugar, presumivelmente, aqui em cima. * Primeiro nó, e que tem sido atribuída uma lista de alguma forma. Eu não sei como isso aconteceu. Isso aconteceu antes da aula começar. Esta lista ligada de seres humanos foi criado. E agora, neste momento da história, tudo isso é ir no Facebook, aparentemente, mais tarde, neste ponto da história, Anita foi inicializada para ser igual ao primeiro, o que não significa que os pontos de Anita em Lucas. Em vez disso, ela aponta para o que ele aponta para pois o mesmo endereço que está dentro de 32 bits - Lucas 1, 2, 3 - é agora também dentro de 32 Anita bits - 1, 2, 3. 

Agora, encontrar 22. Como você vai fazer sobre isso? O que é que o ponto? >> Para o que for. Aponte para o que quer, então vá em frente e agir para fora o melhor que puder aqui. Bom, bom, e agora você está apontando-o que é o seu nome, com 22? Ramon. >> Ramon, então Ramon está segurando 22. Você já fez um cheque. O Ramon == 22, e se assim for, por exemplo, podemos voltar verdade. Deixe-me, enquanto esses caras ficar aqui um pouco sem jeito, deixe-me fazer algo rapidamente, como bool encontrar. Eu estou indo para ir em frente e dizer (lista * nó, int n). Eu estarei de volta com vocês. Eu só tenho que escrever algum código. E agora eu estou indo para ir em frente e fazer isso, nó * anita = lista. E eu estou indo para ir em frente e dizer ao mesmo tempo (Anita! = NULL). 

A metáfora aqui está ficando um pouco esticado, mas enquanto (Anita! = NULL), o que eu quero fazer? Eu preciso de alguma forma de referenciar o inteiro que Anita está apontando. No passado, quando se tinham estruturas, o que é um nó, usamos a notação de ponto, e gostaríamos de dizer algo como anita.n, mas o problema aqui é que Anita não é uma estrutura em si. O que ela é? Ela é um ponteiro, por isso mesmo, se quisermos usar esta notação de ponto e este vai olhar deliberadamente um pouco enigmática- temos que fazer alguma coisa, como ir para a mão esquerda o que Anita está apontando para e em seguida, obter o campo chamado n. Anita é um ponteiro, mas o que é * Anita? O que você acha quando você vai para o que Anita está apontando? A estrutura, um nó, e um nó de recordação, tem um campo chamado n porque tem, lembre-se, estes dois campos, próximos e n, que vimos há pouco aqui. 

Para realmente imitar isso no código, nós poderíamos fazer isso e dizer se ((* anita). n == n), o n que eu estou procurando. Observe que a função foi aprovada no número que me interessa. Então eu posso ir em frente e fazer algo como verdadeiro retorno. Outra coisa, se esse não é o caso, o que eu quero fazer? Como eu traduzo para codificar o que Anita fez intuitivamente andando através da lista? O que devo fazer aqui para simular Anita dar esse passo para a esquerda, que passo para a esquerda? [Resposta do aluno inaudível] >> O que é isso? [Resposta do aluno inaudível] Bom, não é uma idéia ruim, mas no passado, quando fizemos isso, fizemos anita + + porque que gostaria de acrescentar o número 1 para Anita, que normalmente apontar para a próxima pessoa, como Ramon, ou a pessoa próxima a ele, ou a pessoa próxima a ele para baixo da linha. Mas isso não é muito bom aqui, porque o que essa coisa parece na memória? Não é isso. Nós temos que desativar isso. Parece que este na memória, e mesmo que eu tenha desenhado 1 e 2 e 3 próximos um do outro, se realmente simular este-Vocês podem, ainda apontando para as mesmas pessoas, alguns de vocês podem dar um passo atrás aleatória, alguns de vocês um passo aleatório para a frente? 

Esta confusão é ainda uma lista ligada, mas esses caras poderiam estar em qualquer lugar na memória, assim anita + + não vai funcionar por que? O que está em local anita + +? Quem sabe. É algum outro valor que só acontece a ser interposta entre todos esses nós por acaso, porque não estamos usando uma matriz. Nós alocado a cada um destes nós individualmente. Ok, se vocês podem limpar-se de volta. Deixe-me propor que, em vez de anita + +, que em vez fazer anita fica- bem, por que não vamos para o que quer que Anita está apontando e depois fazer. próximo? Em outras palavras, vamos para Ramon, que está segurando o número 22, e depois. seguinte é como se Anita seria copiar o seu ponteiro mão esquerda. Mas ela não quis ir mais longe do que Ramon porque encontramos 22. Mas isso seria a idéia. Agora, isso é uma bagunça horrível. Honestamente, ninguém vai lembrar esta sintaxe, e assim, felizmente, na verdade é um pouco deliberada-oh, você não realmente ver o que eu escrevi. Isso seria mais convincente se pudesse. Voila! 

Por trás das cenas, eu estava resolvendo o problema dessa forma. Anita, para dar esse passo para a esquerda, em primeiro lugar, nós ir para o endereço que Anita está apontando para e onde ela vai encontrar não só n, que verifiquei apenas para efeitos de comparação, mas você também vai encontrar próximo - neste caso, Mão esquerda Ramon, apontando para o próximo nó na lista. Mas esta é a bagunça horrível a que me referi anteriormente, mas acontece C nos permite simplificar isso. Em vez de escrever (* anita), podemos ao invés de apenas escrever anita-> n, e é exatamente a mesma coisa funcionalmente, mas é muito mais intuitivo, e é muito mais consistente com a imagem que temos vindo a desenhar todo esse tempo usando as setas. 

Por fim, o que nós precisamos fazer no final deste programa? Há uma linha de código restante. Devolver o que? Falso, porque se passar todo o loop while e Anita é, de fato, nulo, isso significa que ela percorreu todo o caminho para o fim da lista onde ela estava apontando-o que é o seu nome? Ari mão esquerda. >> Ari, que é nulo. Anita agora é nulo, e eu perceber que você está de pé aqui sem jeito no limbo porque eu estou saindo em um monólogo aqui, mas vamos envolvê-lo novamente em apenas um momento. Anita é nulo nesse ponto da história, de modo que o loop while termina, e nós temos que retornar falso, porque se ela tem todo o caminho para ponteiro nulo de Ari então não havia número que ela procurou na lista. Podemos limpar isso também, mas essa é uma implementação muito boa, então de uma função de passagem, uma função para encontrar uma lista ligada. É ainda busca linear, mas não é tão simples como um ponteiro + + ou + + uma variável i porque agora não podemos adivinhar em que cada um destes nós se encontram na memória. Temos que, literalmente, seguir a trilha de migalhas de pão ou, mais especificamente, ponteiros, para começar a partir de um nó para outro. 

Agora vamos tentar outro. Anita, você quer voltar para cá? Por que não vamos em frente e alocar uma outra pessoa da platéia? Malloc qual é o seu nome? >> Rebecca. Rebecca. Rebecca foi malloced da platéia, e ela é agora armazenar o número 55. E o objetivo em mãos agora é para Anita para inserir Rebecca na lista ligada aqui em seu lugar apropriado. Venha aqui por um momento. Eu tenho feito algo assim. Eu fiz * nó. E qual é o seu nome? Rebecca. >> Rebecca, tudo bem. Rebecca fica malloc (sizeof (nó)). Assim como nós alocamos coisas como estudantes e outros enfeites no passado, temos o tamanho do nó, de modo agora Rebecca está apontando para o que? Rebecca tem dois campos dentro dela, um dos quais é 55. Vamos fazer o que, rebecca-> = 55. Mas, então, rebecca-> seguinte deve ser-como agora, a mão dela é uma espécie de, quem sabe? Ele está apontando para algum valor de lixo, então por que não fazer para uma boa medida que pelo menos fazer isso para que a mão esquerda está agora ao seu lado. Agora Anita, levá-lo a partir daqui. Você tem Rebecca tendo sido atribuídos. Vá em frente e descobrir onde devemos colocar Rebecca. Bom, muito bom. Ok, bom, e agora nós precisamos de você para fornecer um pouco de direção, de modo que você alcançou Ari. Sua mão esquerda é nulo, mas Rebecca pertence claramente à direita, então como é que nós temos que alterar esta lista ligada a fim de inserir Rebecca no local apropriado? Se você pode, literalmente, mover as mãos das pessoas de esquerda em torno de como necessário, nós vamos resolver o problema dessa forma. Ok, bom, e, entretanto, a mão esquerda de Rebecca já está ao seu lado. 

Isso foi muito fácil. Vamos tentar alocar-estamos quase pronto, 20. Ok, vamos lá para cima. 20 foi atribuído, então deixe-me ir em frente e dizer novamente aqui nós acabamos de fazer saad * nó. Temos malloc (sizeof (nó)). Em seguida, fazer a mesma sintaxe exata como fizemos antes de 20, e eu vou fazer = NULL seguinte, e agora cabe a Anita você inserir na lista ligada, se você poderia desempenhar esse papel exato. Executar. Ok, bom. Agora pense com cuidado antes de você começar a se mover a mão esquerda ao redor. Você tem, de longe, o papel mais difícil hoje. Cuja mão deve ser movido em primeiro lugar? Ok, espere, eu estou ouvindo algumas n º. Se algumas pessoas se educadamente gostaria de ajudar a resolver uma situação embaraçosa aqui. Cuja mão esquerda deve ser atualizado primeiro, talvez? Sim. [Estudante] Saad. Ok, Saad, por que, então? [Resposta do aluno inaudível] Bom, porque se mover-qual é o seu nome? >> Marshall. Marshall, se mover sua mão primeiro para baixo a nulo, agora temos literalmente órfãos quatro pessoas na lista porque ele era a única coisa apontando para Ramon e todos para a esquerda, de modo que a atualização primeiro ponteiro era ruim. Vamos desfazer isso. Bom, e agora vá em frente e passar a mão apropriado esquerda apontando para Ramon. Isso sente-se um pouco redundante. Agora há duas pessoas apontando para Ramon, mas isso é bom porque agora que outra forma é que vamos atualizar a lista? O que por outro lado tem de se mover? Excelente, agora temos perdido a memória? Não, tudo bem, vamos ver se não podemos quebrar esta mais uma vez. 

Mallocing uma última vez, o número 5. Em todo o caminho de volta, venha para baixo. É muito emocionante. [Aplausos] Qual é o seu nome? >> Ron. Ron, ok, você está malloced como número 5. Acabamos de executado o código que é quase idêntico a estes com apenas um nome diferente. Excelente. Agora, Anita, boa sorte inserir o número 5 na lista agora. Bom, e? Excelente, de modo que este é realmente o terceiro de três casos no total. Primeiro tivemos alguém no final, Rebecca. Então, teve alguém no meio. Agora temos alguém no início, e, neste exemplo, agora teve que atualizar Lucas pela primeira vez porque o primeiro elemento na lista agora tem que apontar para um novo nó, que, por sua vez, está a apontar no número de nó 9. 

Esta foi uma demonstração extremamente estranho, eu tenho certeza, assim um grande aplauso para esses caras se pudesse. Bem feito. Isto é tudo. Você pode manter seus pedaços de papel como um pouco de memória. Acontece que fazer isso no código não é tão simples como mover as mãos em torno de e apontando ponteiros em coisas diferentes. Mas perceber que quando chega a hora de implementar algo como uma lista ligada ou uma variante do que se você se concentrar em realmente esses fundamentos básicos, os problemas de mordida de tamanho que eu tenho que descobrir, é esta mão ou este lado, perceber que o que é outra forma de um programa bastante complexo pode, de fato, ser reduzida a blocos de construção bastante simples como este. 

Vamos levar as coisas para uma direção mais sofisticado ainda. Temos agora a noção de lista ligada. Temos também, graças à sugestão lá atrás-uma lista duplamente ligada, que parece ser quase a mesma, mas agora temos dois ponteiros dentro da estrutura em vez de uma, e provavelmente poderíamos chamar os ponteiros anterior e próximo ou para a esquerda ou para a direita, mas nós, de fato, precisa de dois deles. O código seria um pouco mais complicado. Anita teria que fazer mais trabalho aqui no palco. Mas certamente poderíamos implementar esse tipo de estrutura. Em termos de tempo de funcionamento, no entanto, o que seria o tempo de execução por Anita de encontrar um n número em uma lista ligada agora? O ainda grande de n, então não é melhor do que a busca linear. Nós não podemos fazer busca binária, embora, mais uma vez. Por que isso acontece? Você não pode pular. Mesmo que ver, obviamente, todos os seres humanos no palco, e Anita poderia ter eyeballed e disse: "Aqui está a meio da lista", ela não saberia que, se fosse um programa de computador porque a única coisa que tinha de agarrar-se no início do cenário era Lucas, que foi o primeiro ponteiro. Ela teria necessariamente que seguir estes links, contando o seu caminho até que encontrou cerca de meio a, e mesmo assim, ela não vai saber quando ela atingiu o meio a menos que ela vai todo o caminho até o fim para descobrir quantos são, depois volta atrás, e que também seria difícil, a menos que você teve uma lista duplamente ligada de algum tipo. 

Resolução de alguns problemas hoje, mas a introdução de outros. E sobre uma estrutura de dados completamente diferente? Esta é uma fotografia das bandejas em Mather House, e, neste caso, temos uma estrutura de dados que temos também uma espécie de já falando. Nós conversamos sobre uma pilha no contexto da memória, e que é uma espécie de deliberadamente chamado porque uma pilha nos termos de memória é efetivamente uma estrutura de dados que tem mais e mais coisas em camadas em cima dele. Mas o mais interessante sobre uma pilha, como é o caso na realidade, é que ele é um tipo especial de estrutura de dados. É uma estrutura de dados em que o primeiro elemento é o último elemento para fora. Se você é a primeira bandeja para ser colocado na pilha, você vai ser, infelizmente, a bandeja último a ser retirado da pilha, e isso não é necessariamente uma coisa boa. Por outro lado, você pode pensar sobre ele o caminho inverso, o último é o primeiro a sair. 

Agora, se os cenários vêm à mente que ter uma pilha estrutura de dados, onde você tem que a propriedade do último, em primeiro lugar, é realmente atraente? Isso é uma coisa boa? É que uma coisa ruim? É definitivamente uma coisa ruim se as bandejas não eram todos iguais e todos eles eram diferentes cores especiais ou outros enfeites, ea cor que você quer é todo o caminho na parte inferior. É claro, você não pode conseguir que sem grande esforço. Você tem que começar a partir do topo e trabalhar sua maneira para baixo. Da mesma forma, se você fosse um desses meninos de fãs que espera a noite toda tentando obter um iPhone e alinha em um lugar como este? Não seria bom se a loja da Apple foram uma estrutura de dados de pilha? Yay? Não? Só é bom para as pessoas que aparecem no último minuto possível e depois se arranquei a fila. E, na verdade, o fato de que eu estava tão inclinado a dizer fila é realmente consistente com o que nós chamaríamos este tipo de estrutura de dados, um na realidade onde a ordem não importa, e deseja que o primeiro em ser o primeiro a sair mesmo que apenas por uma questão de equidade humana. Vamos chamar geral de que uma estrutura de dados fila. 

Acontece que além de listas ligadas, podemos começar a usar essas mesmas idéias básicas e começar a criar novos tipos e diferentes de soluções para os problemas. Por exemplo, no caso de uma pilha, que pode representar uma pilha usando uma estrutura de dados como este, eu gostaria de propor. Neste caso, eu tenho declarado um struct, e eu já disse dentro desta estrutura é uma matriz de números e, em seguida, um tamanho variável chamada, e eu vou chamar essa coisa de uma pilha. Agora, por que isso realmente funciona? No caso de uma pilha, poderia desenhar essa eficácia no ecrã como uma matriz. Aqui é a minha pilha. Esses são os meus números. E nós vamos chamar-lhes como este, este, este, este, este. E então eu tenho algum membro de outros dados aqui, que é chamado de tamanho, de modo que este é o tamanho, e isto é números, e coletivamente, o iPad todo aqui representa uma estrutura de pilha. Agora, por padrão, o tamanho presumivelmente tem que ser inicializado a 0, e que está dentro da matriz de números inicialmente quando eu alocar uma matriz? Lixo. Quem sabe? E isso realmente não importa. Não importa se é 1, 2, 3, 4, 5, de forma completamente aleatória pela má sorte armazenados em minha estrutura, porque desde que eu sei que o tamanho da pilha é 0, então eu sei que programaticamente, não olhe para qualquer um dos elementos do array. Não importa o que está lá. Não olhe para eles, como seria a implicação de um tamanho de 0. 

Mas suponha que agora eu vá em frente e inserir algo na pilha. Quero inserir o número 5, então eu coloquei o número 5 aqui, e então o que eu coloco aqui? Agora eu realmente colocar para baixo 1 para o tamanho, e agora, a pilha é de tamanho 1. E se eu ir em frente e inserir o número, digamos, 7 próximo? Isso, então, é atualizado a 2, e depois vamos fazer 9, e então esta é atualizado a 3. Mas a característica interessante agora desta pilha é que Eu tenho que remover elemento que se eu quiser pop algo fora da pilha, por assim dizer? 9 seria a primeira coisa a ir. Como a imagem deve mudar se eu quiser aparecer um elemento da pilha, Muito parecido com uma bandeja na Mather? Sim. >> [Estudante] tamanho definido para 2. Exatamente, tudo que eu faço é definir o tamanho para 2, eo que eu faço com a matriz? Eu não tenho que fazer nada. Eu poderia, apenas para ser anal, coloque um 0 lá ou a -1 ou algo para significar que este não é um valor legal, mas não importa porque Eu posso gravar fora do conjunto em si quanto tempo é para que eu saiba só olhar para os dois primeiros elementos desta matriz. Agora, se eu for e adicionar o número de 8 a essa matriz, como é que o quadro mude em seguida? Isto torna-se 8, e isto torna-se 3. Estou cortando alguns cantos aqui. Agora temos 5, 7, 8, e estamos de volta a um tamanho de 3. Isso é muito simples de implementar, mas quando é que vamos lamentar esta decisão design? Quando as coisas começam a ir muito, muito errado? Sim. [Resposta do aluno inaudível] Quando você quiser voltar e pegar o primeiro elemento que você colocar dentro 

Acontece aqui, mesmo que uma pilha é uma matriz debaixo do capô, essas estruturas de dados que já começou a falar sobre geralmente também são conhecidos como abstratos estruturas de dados pelo qual como elas são implementadas é completamente fora de questão. Uma estrutura de dados como uma pilha é suposto adicionar suporte operações como impulso, que empurra uma bandeja para a pilha, e pop, que remove um elemento da pilha, e é isso. Se você tivesse que baixar código de outra pessoa que já implementadas esta coisa chamada uma pilha, essa pessoa teria escrito apenas duas funções para você, push e pop, cujo único propósito na vida seria fazer exatamente isso. Você ou ele ou a ela que implementou o programa teria sido inteiramente um para decidir como implementar a semântica de empurrar e aparecendo debaixo do capô ou a funcionalidade de empurrar e popping. E eu fiz uma decisão um tanto míope aqui através da implementação de minha pilha com esta estrutura de dados simples por quê? Quando é que esta pausa estrutura de dados? Em que ponto eu tenho que retornar um erro quando o usuário chama push, por exemplo? [Estudante] Se não há mais espaço. Exatamente, se há não mais espaço, se eu excedeu a capacidade, que é todo em maiúsculas, porque sugere que é algum tipo de constante global. Bem, então eu só vou ter que dizer: "Desculpe, eu não posso empurrar um outro valor na pilha ", bem como em Mather. 

Em algum momento, eles vão bater a parte de cima do gabinete que pouco. Não há mais espaço ou capacidade da pilha, altura em que há algum tipo de erro. Eles têm que colocar o elemento em outro lugar, a bandeja em outro lugar, ou em lugar nenhum. Agora, com uma fila, podemos implementá-lo um pouco diferente. Uma fila é um pouco diferente, em que, sob o capô, ele pode ser implementado como uma matriz, mas por que, neste caso, estou propondo ter também um elemento de cabeça que representa a cabeça de lista, a frente da lista, a primeira pessoa da fila na loja da Apple, além de tamanho? Por que eu preciso de uma peça adicional de dados aqui? Pense de volta para o que os números é se eu desenhei como se segue. Suponhamos que esta é agora uma fila, em vez de uma pilha, a diferença ser-assim como a fila de armazenamento da Apple é justo. A primeira pessoa na linha no início da lista, o número 5, neste caso, ele ou ela vai ser deixado na primeira loja. Vamos fazer isso. Suponha-se que este é o estado da minha fila neste momento no tempo, e agora a loja da Apple abre ea primeira pessoa, número 5, é conduzido para a loja. Como faço para mudar o quadro, agora que eu de-fila a primeira pessoa na parte da frente da linha? O que é isso? >> [Estudante] Alterar a fila. Mudar a cabeça, de modo 5 desaparece. Na realidade, é como se, a melhor forma de fazer isso? Na realidade, é como se esse cara desaparece. Qual seria o número 7 fazer em uma loja real? Eles iriam dar um grande passo para a frente. 

Mas o que temos vindo a apreciar quando se trata de matrizes e mover as coisas? Isso é um desperdício do seu tempo, certo? Por que você tem que ser tão anal como ter a primeira pessoa no início da linha de fisicamente o início do bloco de memória? Isso é completamente desnecessário. Por quê? O que eu poderia apenas lembrar em vez disso? >> [Resposta do aluno inaudível] Exatamente, eu poderia apenas lembrar com esta cabeça adicional membro de dados que agora o cabeça da lista já não é 0, o que foi um momento atrás. Agora é realmente o número 1. Desta forma, recebo uma otimização leve. Só porque eu tenho de-fila alguém de linha no início da linha na loja da Apple não significa que todo mundo tem que mudar, que recall é uma operação linear. Eu posso passar o tempo ao invés única constante e, em seguida, obter uma resposta muito mais rápida. Mas o preço que eu estou pagando é o que ganhar esse adicional de desempenho e não ter que mudar todos? Sim. >> [Resposta do aluno inaudível] Pode adicionar mais pessoas, bem, o problema é ortogonal ao fato de que nós não estamos mudando as pessoas ao redor. É ainda uma matriz, para se vamos ou não mudar todos ou não- oh, eu vejo o que você quer dizer, tudo bem. Na verdade, eu concordo com o que você está dizendo em que é quase como se nós nunca estamos indo agora para usar o início desta matriz mais porque se eu remover 5, então eu remover 7. Mas eu só colocar as pessoas para a direita. 

Parece que eu estou perdendo espaço e, finalmente, minha fila se desintegra em nada, portanto, pode apenas ter envolvente pessoas, e podemos pensar dessa matriz realmente como uma espécie de estrutura circular, mas usamos o operador em C para fazer esse tipo de envolvente? [Resposta do aluno inaudível] >> O operador módulo. Seria um pouco chato para pensar em como você faz a envolvente, mas poderia fazê-lo, e nós poderíamos começar a colocar as pessoas no que costumava ser a frente da linha, mas lembre-se com esta variável cabeça que a cabeça de uma linha realmente é. E se, em vez disso, nosso objetivo, em última análise, no entanto, era para procurar números, como fizemos aqui no palco com Anita, mas nós realmente queremos o melhor de todos os mundos? Nós queremos mais do que sofisticação matriz permite que porque queremos que a capacidade de crescer de forma dinâmica a estrutura de dados. Mas nós não queremos ter que recorrer a algo que nós indicamos na primeira conferência não era um algoritmo ótimo, o de busca linear. Acontece que você pode, de fato, alcançar ou pelo menos perto de tempo constante, em que alguém como Anita, se ela configura a estrutura de dados não ser uma lista ligada, a não ser uma pilha, a não ser uma fila, pode, na verdade, chegar a uma estrutura de dados que lhe permite olhar para as coisas, mesmo palavras, não apenas em números, o que nós chamamos de tempo constante. 

E, de fato, olhando para frente, uma das Série de Exercícios nesta classe é quase sempre a implementação de um corretor ortográfico, em que nós damos-lhe algumas palavras novamente 150.000 ingleses eo objetivo é carregar os para a memória e rapidamente ser capaz de responder às perguntas do formulário é esta palavra soletrada corretamente? E seria realmente chupar se você tivesse que percorrer todos os 150 mil palavras para responder a isso. Mas, na verdade, nós vamos ver que nós podemos fazê-lo em tempo muito, muito rápido. E vai envolver algo implementação chamada tabela hash, e mesmo que à primeira vista essa coisa chamada uma tabela hash vai vamos alcançar esses super-rápidos tempos de resposta, verifica-se que há, de facto, um problema. Quando chega a hora de implementar esta coisa chamada de novo, eu estou fazendo isso de novo. Eu sou o único aqui. Quando chega a hora de implementar essa coisa chamada uma tabela hash, nós vamos ter que tomar uma decisão. Qual deve ser essa coisa realmente ser? E quando começamos a inserção de números para esta tabela hash, como é que vamos para armazená-los de tal forma que pode levá-los de volta o mais rápido que chegamos los? Mas vamos ver antes de tempo que esta questão de Quando o aniversário de todos está na classe será bastante pertinente. Acontece que nesta sala, temos algumas centenas de pessoas, assim as chances de que dois de nós têm a mesma data de aniversário é provavelmente bastante elevado. E se houvesse apenas 40 de nós nesta sala? Quais são as chances de duas pessoas que têm a mesma data de aniversário? [Os alunos] Mais de 50%. Sim, mais de 50%. Na verdade, eu ainda trouxe um gráfico. Acontece, e isso é realmente apenas um sneak preview- se há apenas 58 de nós nesta sala, a probabilidade de dois de nós ter a mesma data de aniversário é extremamente alta, quase 100%, e que vai causar um monte de dor para nós na quarta-feira. 

Com isso dito, vamos adiar aqui. Vemo-nos na quarta-feira. [Aplausos] [CS50.TV]