[Música tocando] 

[REPRODUÇÃO DE VÍDEO] 

-Ele está mentindo. 

-Sobre o que? 

-Eu não sei. 

-Então, O que sabemos? 

-Isso Às 9:15, Ray Santoya estava no caixa eletrônico. -Sim. Então a questão é, o que ele estava fazendo em 09:16? 

-Shooting A nove milímetros em alguma coisa. Talvez ele viu o atirador. 

-Ou Estava trabalhando com ele. 

-Aguarde. Volte um. 

-O que você vê? 

-Trazer O rosto para cima tela cheia. 

Vidros -His. 

-Há Uma reflexão. 

-É O time de beisebol Nuevitas. Esse é o seu logotipo. 

-E Ele está falando com quem está usando aquela jaqueta. 

[FIM DE REPRODUÇÃO] 

DAVID MALAN: Tudo bem. Esta é CS50 e isso é um pouco mais de [inaudível] com a qual você está brincar com problema definir quatro. Hoje começamos a olhar um pouco mais profundamente para essas coisas chamadas ponteiros, que apesar de ser um tópico muito misterioso, verifica-se que ele vai a ser o meio através do qual nós pode começar a construir e montar programas muito mais sofisticado. Mas o que fizemos na quarta-feira passada por meio de alguns claymation primeiro. Portanto, este, recall, é Binky e usamos-lo para dar uma olhada em um programa que realmente não faz nada de interessante, mas revelou alguns problemas. Então, para começar hoje, por que não podemos andar rapidamente através de alguns destes passos, tentar destilar em termos de humanos exatamente o que está acontecendo aqui e por que isso é ruim, e, em seguida, seguir em frente e realmente começar a construir algo com esta técnica? Então, esses foram os primeiros duas linhas neste programa e em termos leigos, o que são estas duas linhas fazendo? Alguém que é razoavelmente confortável com o que está declarado na tela? Quais são essas duas linhas que fazem? Não é tudo o que diferente de uma semana, mas há algum novo símbolo especial. Sim? Ali atrás. 

AUDIÊNCIA: Declarando ponteiros? DAVID MALAN: Diga outra vez? AUDIÊNCIA: Declarando ponteiros? DAVID MALAN: Declarando e ponteiros Vamos refiná-lo um pouco mais. AUDIÊNCIA: [inaudível] endereço e, em seguida, x y. DAVID MALAN: E, em seguida, abordar. Então, especificamente o que estamos fazendo é que estamos a declarar duas variáveis. Essas variáveis, no entanto, vão para ser do tipo int estrela, que significa mais especificamente eles estão indo para armazenar o endereço de um int, respectivamente, X e Y. Agora existem quaisquer valores? Há algum endereços reais nestes duas variáveis ​​neste momento no tempo? Não. É apenas chamados valores de lixo. Se você realmente não atribuir um variável, o que estava na RAM anteriormente vai preencher com zeros e as duas dessas variáveis. Mas nós ainda não sabemos o que são e que é vai ser a chave para por que Binky perdeu a cabeça na semana passada. 

Portanto, este foi o claymation encarnação do presente em que você tem apenas duas variáveis, pequenos pedaços circulares de argila, que pode armazenar variáveis, mas quanto as setas envolvidas acima sugerem, eles não estão realmente apontando para qualquer lugar conhecido per se. Então, depois, teve esta linha, e esta era novo na semana passada, malloc para a memória atribuição, que é apenas uma maneira elegante de dizer ao sistema operacional, Linux ou Mac OS ou Windows, hey, me dê um pouco de memória, e tudo que você tem a dizer o sistema operativo é o que quando pedindo-lhe para a memória. Ele não vai se importar com o você vai fazer com ele, mas você precisa dizer ao funcionamento sistema que por meio de malloc. Sim? 

AUDIÊNCIA: Quanto? DAVID MALAN: Quanto? Quanto em bytes, e assim, este, de novo, um exemplo artificial, está apenas dizendo, dá-me o tamanho de um int. Agora, o tamanho de um int é de quatro bytes ou 32 bits. Portanto, esta é apenas uma forma de dizendo, hey, sistema operacional, dá-me quatro bytes de memória que eu posso usar a minha disposição, e, especificamente, o que faz retorno malloc com respeito para esse pedaço de quatro bytes? AUDIÊNCIA: Morada? DAVID MALAN: O endereço. O endereço desse pedaço de quatro bytes. Exatamente. E é isso o que está armazenado em última análise, em x e é por isso que nós realmente não importo com o que o número de que endereço é, se é OX1 ou ox2 ou algum endereço hexadecimal enigmática. Nós apenas cuidar pictoricamente que essa variável x é agora apontando para que o pedaço de memória. Assim, a seta representa um ponteiro, ou mais especificamente, um endereço de memória. Mas, novamente, não importa tipicamente o que esses endereços são reais. Agora, esta linha diz o que em termos leigos? Estrela x recebe 42 ponto e vírgula. O que isto significa? Você quer ir? Não arranhe seu pescoço. 

AUDIÊNCIA: O endereço de x está no 42. 

DAVID MALAN: O endereço de x é a 42. Não é bem assim. Tão perto, mas não completamente, porque não há a estrela que está prefixing este x. Por isso, precisamos de ajustar um pouco. Sim? 

AUDIÊNCIA: O valor que o ponteiro x está apontando para é de 42. DAVID MALAN: OK. O valor que o ponteiro x é apontando para, digamos, será 42, ou dito de outra forma, a estrela x diz, ir para qualquer outro endereço está em x, quer se trate de uma Oxford Rua 33 ou Oxford Street ou OX1 ou ox33, qualquer que seja que endereço numérico é, estrela x é a dereferencing de x. Então, vá para esse endereço e em seguida, colocar o número 42 lá. Assim que seria um maneira equivalente a dizer isso. Então, isso é tudo muito bem e, em seguida, que representaria a imagem como se segue, onde nós adicionamos o 42 a esse pedaço de quatro bytes na lateral direita, mas esta linha foi onde as coisas deram errado ea cabeça de Binky estalou fora neste ponto, porque coisas ruins acontecem quando você dereference valores de lixo ou você cancelar a referência inválida ponteiros, e eu digo inválido porque neste momento no história, o que está dentro de y? Qual é o valor de base y nas poucas etapas passadas? Sim? O que é isso? 

AUDIÊNCIA: Um endereço. DAVID MALAN: Um endereço. Deve ser um endereço mas tenho inicializado-lo? Então eu não tenho ainda. Então, o que é conhecido por ser aí? É apenas algum valor de lixo. Poderia ser qualquer endereço de zero a 2 bilhões se você tiver dois GB de RAM, ou zero a 4 bilhões se você tiver tem quatro gigabytes de RAM. É algum valor de lixo, mas o problema é que o sistema operacional, se ele não lhe deu que pedaço de memória especificamente que você está tentando ir, ele vai geralmente para causar o que temos visto como uma falha de segmentação. Então, na verdade, qualquer um de vocês que têm esforçou-se em problemas no horário de expediente ou em problemas que é mais geralmente com tentando descobrir uma falha de segmentação, que geralmente significa você está tocando um segmento de memória que você não deve ser. Você está tocando memória que o sistema operacional não tem permitiu-lhe tocar, se é por ir longe demais em sua matriz ou a partir de agora, se é porque você está tocando memória que é apenas algum valor de lixo. 

Assim fazendo estrela x aqui é tipo de comportamento indefinido. Você nunca deve fazê-lo porque as probabilidades são, o programa só vai falhar, porque você está dizendo, vá a este endereço e você não tem idéia de onde esse endereço realmente é. Assim, o sistema operacional é provável indo para travar o seu programa como resultado e, na verdade, isso é o que aconteceu lá para Binky. Então, finalmente, fixado Binky este problema com este. Assim que o programa em si foi falho. Mas se você espécie de avançar e executar essa linha em vez disso, y é igual x significa apenas o que quer endereço é um x, também colocá-lo em y. 

E assim pictoricamente, nós temos esta representada com duas setas a partir de x e de y apontador para o mesmo local. Assim semanticamente, x é igual para y, porque ambos daqueles armazenar a mesma endereço, ergo apontando para 42, e agora, quando você diz estrela y, vá para o endereço em y, este tem um efeito secundário interessante. Assim, o endereço em que y é a mesma coisa que o endereço em x. Então, se você diz que ir para o endereço em y e altere o valor para 13, Quem mais é afetado? X é, ponto D, por assim dizer, devem ser afetados também. 

E, de fato, como Nick tirei esta imagem em claymation foi exatamente isso. Mesmo que nós seguimos o ponteiro y, acabamos no mesmo lugar, e assim se estivéssemos a imprimir out x ou y de pointee, então veríamos o valor de 13. Agora, eu digo pointee ser consistente com o vídeo. Programmers, ao meu conhecimento, nunca realmente dizer a palavra pointee, o que está apontado no, mas a consistência com o vídeo, percebe isso é tudo o que era significava nessa situação. Assim dúvidas sobre claymation ou ponteiros ou apenas malloc ainda? Não? Tudo certo. 

Assim, sem mais delongas, vamos dar uma olhada para onde isso tem realmente sido utilizado durante algum tempo. Então nós tivemos esta biblioteca CS50 que tem todas essas funções. Nós usamos GetInt muito, GetString, provavelmente GetLongLong anterior Na minha PSet um ou mais, mas o que está realmente acontecendo? Bem, vamos dar uma olhada rápida por baixo do capuz com um programa que inspira por que nós damos-lhe o CS50 biblioteca, e de fato como da semana passada, que começou a tomar os rodinhas. Então, isso agora está classificada de um post-mortem do que já se arrasta dentro da biblioteca CS50, mesmo que agora vai começar a se mover longe dela para a maioria dos programas. 

Portanto, este é um programa chamado scanf 0. É super curta. Ele só tem estas linhas, mas introduz uma função chamada scanf que na verdade estamos indo para ver em um momento no interior da biblioteca CS50, embora de uma forma um pouco diferente. Portanto, este programa na linha 16 é declarar uma variável x. Então me dê quatro bytes para um int. Ele tem dito a usuário, número por favor, e, em seguida, esta é uma linha que interessante realmente une na semana passada e isso. Scanf, e, em seguida, perceber que é preciso um formato de cadeia, assim como printf, % i significa um int, e, em seguida, leva um segundo argumento que parece um pouco descolados. É ampersand x, e para recordar, nós só vi isso uma vez na semana passada. O que faz e comercial x representam? O que fazer em C e comercial? Sim? 

AUDIÊNCIA: O endereço de. DAVID MALAN: O endereço de. Portanto, é o oposto o operador de estrela, enquanto o operador estrela diz, ir para Neste endereço, o operador E comercial diz, descobrir a endereço dessa variável, e por isso esta é a chave, porque O propósito de scanf na vida é verificar o usuário de a entrada do teclado, dependendo do que ele ou ela tipos, e, em seguida, ler a entrada desse usuário em uma variável, mas nós viu nas últimas duas semanas que a referida função de comutação que nós tentou sem esforço para implementar só estava quebrado. Lembre-se que com a função swap, se nós apenas declarado A e B como ints, fizemos trocar com sucesso o duas variáveis ​​dentro de troca Assim como com o leite e JO, mas assim como swap voltou, qual foi o resultado com respeito a x e y, os valores originais? Nenhuma coisa. Sim. Nada aconteceu naquela época, porque swaps alterar apenas suas cópias locais, o que quer dizer, todos desta vez, sempre que temos foi passando argumentos às funções, estamos só de passagem cópias desses argumentos. Você pode fazer com que o que quiser com eles, mas eles vão ter nenhum efeito sobre os valores originais. Então, isso é problemático se você quero ter uma função como scanf na vida, cujo objetivo é fazer a varredura a entrada do usuário a partir do teclado e depois preencher os espaços em branco, de modo a falar, isto é, dar uma variável como x um valor, porque se eu fosse apenas para passar x para scanf, se você considerar a lógica da última semana, scanf pode fazer o que quiser com uma cópia de x, mas não podia alterar permanentemente x a menos que nós damos scanf um mapa do tesouro, por assim dizer, onde X marca o local, em que passamos o endereço de x para que scanf pode ir lá e realmente mudar o valor de x. E assim, de fato, todos que este programa faz se eu fizer scanf 0, em minha fonte Diretório 5m, fazer scanf 0, dot cortar scanf, número por favor 50, graças ao 50. 

Portanto, não é tão interessante, mas o que está de fato acontecendo é que assim que eu chamo scanf aqui, o valor de x está a ser permanentemente alterado. Agora, isso parece bom e bom, e na verdade, Parece que nós realmente não precisa a biblioteca CS50 em tudo mais. Por exemplo, vamos executar isto mais uma vez aqui. Deixe-me reabri-lo por um segundo. Vamos tentar um número por favor e em vez de dizer 50 como antes, vamos apenas dizer não. OK, isso é um pouco estranho. ESTÁ BEM. E apenas algumas bobagens aqui. Por isso, não parece lidar com situações erradas. Então, precisamos minimamente início adicionando um pouco de verificação de erros para se certificar de que o usuário tem digitado em um número real como 50, porque, aparentemente, digitando palavras não é detectada como problemática, mas provavelmente deve ser. 

Vamos olhar para esta versão agora que é minha tentativa de reimplementar GetString. Se scanf tem tudo isso funcionalidade incorporada, por que temos sido a brincar com estas rodinhas como GetString? Bem, aqui é, talvez, o meu próprio versão simples do GetString em que uma semana atrás, eu poderia ter dito, dá-me uma corda e chamá-lo de buffer. Hoje, eu vou começar apenas dizendo estrela char, que, recall, é apenas sinônimo. Parece assustador, mas é exatamente a mesma coisa. Então me dê um buffer variável chamada que está indo para armazenar uma seqüência de caracteres, dizer a string user por favor, e, em seguida, como antes, vamos tentar emprestar esta lição scanf % s neste momento e, em seguida, passar em tampão. Agora, uma verificação de sanidade rápida. Por que não estou dizendo E comercial tampão desta vez? Inferir a partir do exemplo anterior. AUDIÊNCIA: Char estrela é um ponteiro. DAVID MALAN: Exatamente, porque este tempo, char estrela já é um ponteiro, um endereço, por definição, de estar ali aquela estrela. E se scanf espera um endereço, basta apenas passar em tampão. Eu não preciso dizer tampão e comercial. Para os curiosos, você poderia fazer algo assim. Ele teria significado diferente. Isto lhe daria um ponteiro de um ponteiro, o qual é na verdade uma coisa válida em C, mas para Agora, vamos mantê-lo simples e manter a história consistente. Eu só vou passar em tampão e isso é correto. O problema, porém, é este. Deixe-me ir em frente e executar esse programa depois de compilá-lo. Faça scanf 1. Porra, meu compilador de pegando o meu erro. Dê-me um segundo. Clang. Vamos dizer que scanf-1.c. ESTÁ BEM. Aí vamos nós. Eu preciso disso. CS50 ID tem vários definições de configuração que protegem você contra você mesmo. Eu precisava desativar os de executando clang manualmente neste momento. Então cadeia por favor. Eu estou indo para ir em frente e digite no meu mundo Olá favorito. OK, null. Isso não é o que eu digitei. Por isso é indicativo de que algo está errado. Deixe-me ir em frente e digite em um tempo muito longo string. Obrigado pela nulo e eu não sei se eu vou ser capaz de lançá-lo. Vamos tentar um pouco de cópia colar e ver se isso ajuda. Basta colar um monte de presente. É definitivamente um maior cadeia do que o habitual. Vamos apenas realmente escrevê-lo. Não. Caramba. Comando não encontrado. Então, isso é não relacionado. Isso é porque eu colei alguns personagens maus, mas isso acaba não está indo trabalhar. 

Vamos tentar isso mais uma vez, porque é mais divertido se nós realmente lançá-lo. Vamos escrever isso e agora, eu sou indo para copiar uma cadeia muito longa e agora vamos ver se nós pode bater essa coisa. Repare que eu omitido espaços e novas linhas e-vírgulas e todos os personagens de funky. Enter. E agora a rede está apenas sendo lento. I pressionado Command-V muito tempo, claramente. Caramba! Comando não encontrado. 

ESTÁ BEM. Bem, o ponto é no entanto, o seguinte. Então, o que está realmente acontecendo sobre a presente declaração de tampão estrela caractere na linha 16? Então, o que estou recebendo quando eu declarar um ponteiro? Tudo o que eu estou recebendo é um valor de quatro bytes chamado de buffer, mas o que está dentro dela no momento? É apenas algum valor de lixo. Porque qualquer momento você declarar uma variável em C, é apenas algum valor de lixo, e estamos começando a viagem sobre esta realidade. Agora, quando eu digo scanf, vá a este endereço e colocar o que o usuário digita. Se o usuário digita Olá mundo, bem, onde eu gostaria de colocá-lo? Buffer é um valor de lixo. 

Então, isso é como uma espécie de seta que está apontando quem sabe onde. Talvez ele está apontando bem aqui na minha memória. E assim, quando o usuário tipos em Olá mundo, o programa tenta colocar o Olá mundo seqüência barra invertida 0 nesse pedaço de memória. Mas, com alta probabilidade, mas claramente não 100% de probabilidade, o computador vai então falhar o programa porque este não é memória que eu deveria ser permitido tocar. Assim, em breve, este programa é falho para exatamente esse motivo. Eu fundamentalmente não estou fazendo o que? Que medidas têm omiti, assim como nós omitimos com o primeiro exemplo de Binky? Sim? 

AUDIÊNCIA: alocação de memória? 

DAVID MALAN: alocação de memória. Eu realmente não tenho alocado qualquer memória para essa seqüência. Assim, podemos consertar isso em um par de formas. Um, podemos mantê-lo simples e, de fato, agora você está vai começar a ver uma indefinição das linhas entre o que uma matriz é, o que é uma string, o que é um Char estrela é, o que uma matriz de caracteres é. Aqui está um segundo exemplo envolvendo cordas e aviso tudo que eu fiz em linha 16 é, em vez de dizer tampão que vai ser um char estrela, um ponteiro para um bloco de memória, Eu vou dar muito proativamente me um buffer para 16 caracteres, e de fato, se você estiver familiarizado com o termo de tamponamento, provavelmente a partir do mundo dos vídeos, onde um buffer de vídeo é, de tamponamento, buffering. Bem, qual é a conexão aqui? Bem, interior de YouTube e dentro de players de vídeo geralmente é uma matriz que é maior do que 16. Ele pode ser uma matriz de um tamanho megabyte, talvez 10 megabytes, e para essa matriz faz seu browser baixar um monte de bytes, um grupo inteiro de megabytes de vídeo e leitor de vídeo, YouTube ou de quem quer que esteja, começa lendo os bytes de matriz que, ea qualquer momento você vê o palavra buffering, buffering, que significa que o jogador possui chegado ao fim desse array. A rede é tão lento que não tem recarregados a matriz com mais bytes e então você está fora de bits para exibir para o usuário. 

Então tampão é um termo apt aqui em que é apenas uma matriz, um pedaço de memória. E isso vai corrigi-lo pois verifica-se que você pode tratar matrizes como se eles são endereços, embora tampão é apenas um símbolo, é uma sequência de caracteres, buffer, que é útil para mim, o programador, você pode passar em torno de seu nome como se fosse um ponteiro, como se foram o endereço de um pedaço de memória para 16 caracteres. Então, isso é para dizer, eu posso passar o scanf exatamente essa palavra e agora, se eu fizer este programa, fazer scanf 2, ponto scanf barra 2, e digite Olá mundo, Enter, que tempo-- 

Hmm, o que aconteceu? Corda por favor. O que eu fiz errado? Olá, mundo, buffer. Ola mundo. Ah, eu sei o que está fazendo. ESTÁ BEM. Então está lendo-se até que o primeiro espaço. Então, vamos enganar por apenas um momento e dizer que eu só queria escrever algo realmente longa como esta é uma frase longa isso é um, dois, três, quatro, cinco, seis, sete, oito, nove, 10, 11, 12, 13, 14, 15, 16. ESTÁ BEM. Na verdade, é uma frase longa. Então, esta frase é mais de 16 caracteres e então quando eu pressione Enter, o que vai acontecer? Bem, neste caso do tampão história, eu tinha declarado para ser realmente uma matriz com 16 caracteres pronto para ir. Então, um, dois, três, quatro, cinco, seis, sete, oito, nove, 10, 11, 12, 13, 14, 15, 16. Assim, 16 caracteres, e agora, quando eu ler em algo como este é um longo sentença, o que vai acontecer é que eu vou ler em este é um longo S-E-N-A-C-N-C-E, frase. 

Portanto, esta é deliberadamente uma coisa ruim que eu continuar a escrever para além do limites da minha matriz, para além dos limites do meu tampão. Eu poderia ter sorte e do programa vai continuar a correr e não me importo, mas de um modo geral, esta vai realmente bater o meu programa, e é um bug no meu codificar o momento que eu passo para além dos limites dessa matriz, porque eu Não sei se é necessariamente vai falhar ou se eu estou indo só para ter sorte. Então, isso é problemático porque em Neste caso, ele parece funcionar e vamos tentar o destino aqui, embora o IDE parece tolerar um pouco de-- 

Aí vamos nós. Finalmente. Então, eu sou o único que pode ver isso. Então, eu só tinha um monte de diversão digitação uma frase real muito longo que certamente excedido 16 bytes, porque digitado nesta longa multi-linha louco frase, em seguida, observe o que aconteceu. O programa tentou imprimi-lo e, em seguida, tem uma falha de segmentação e falhas de segmentação é quando algo como isso acontece e o sistema operativo diz não, não pode tocar essa memória. Nós vamos matar o programa completo. 

Portanto, este parece problemático. Eu melhorei o programa pelo qual pelo menos, ter alguma memória, mas isto parece limitar o GetString função para obter cordas de algum tempo finito 16. Então, se você quer apoiar mais frases do que 16 caracteres, o que você faz? Bem, você pode aumentar o tamanho desta reserva para 32 ou que parece tipo de short. Por que não vamos apenas fazer que 1000, mas empurrar para trás. Qual é a resposta intuitivamente de apenas evitar este problema, tornando meu buffer maior, como 1.000 caracteres? Ao implementar GetString desta forma. O que é bom ou ruim aqui? Sim? Audiência: Se você ligar um monte de espaço e você não usá-lo, então você não pode redistribuir esse espaço. DAVID MALAN: Absolutamente. É um desperdício na medida em que se não o fizer realmente precisa desses 900 bytes e ainda assim você está pedindo 1.000 no total de qualquer maneira, você apenas está consumindo mais memória o computador do usuário do que você precisa, e depois de tudo, alguns você já encontrou na vida que quando você está executando muitos programas e eles estão comendo muita memória, isso pode realmente afetar o desempenho e experiência do usuário no computador. Então, esse é o tipo de uma solução preguiçoso, com certeza, e, inversamente, não é apenas um desperdício, qual é o problema ainda permanece, mesmo se eu faço o meu tampão 1000? Sim? 

AUDIÊNCIA: A cadeia de comprimento é 1.001. DAVID MALAN: Exatamente. Se a seqüência de comprimento é 1001, você tem exatamente o mesmo problema, e pelo meu argumento, eu o faria apenas, em seguida, torná-lo 2000, mas você não sabe em avançar o quão grande ele deve ser, e ainda, eu tenho que compilar meu programa antes de deixar as pessoas usam e faça o download isto. Portanto, este é exatamente o tipo de coisas que as tentativas de biblioteca CS50 para nos ajudar com e nós só vai olhar em alguns dos implementação subjacente aqui, mas este é CS50 ponto C. Este é o arquivo que tem estado em CS50 IDE todas essas semanas que você está usando. É pré-compilados e você tem sido usá-lo automaticamente por natureza de ter o traço L bandeira CS50 com clang, mas se eu rolar para baixo através de todos estas funções, é aqui GetString, e só para lhe dar um gosto do que está acontecendo, vamos dar uma olhada rápida em a relativa complexidade. Não é um super longa função, mas não o fizemos tem que pensar muito sobre tudo como ir sobre a obtenção de cordas. 

Então aqui está o meu tampão e eu aparentemente, inicialize-o como nulo. Isto, naturalmente, é o mesma coisa como char estrela, mas eu decidi em execução da biblioteca CS50 que, se nós estamos indo para ser completamente dinâmico, Eu não sei com antecedência como grande de um usuários de cordas vão querer obter. Então eu vou começar com apenas uma cadeia vazia e eu estou indo para construir o máximo memória como eu preciso para se ajustar à string user e se eu não tenho suficiente, eu vou pedir o sistema operacional para mais memória. Eu estou indo para mover sua seqüência em um pedaço maior de memória e eu estou indo para liberar ou libertar o insuficientemente grande pedaço de memória e nós apenas estamos indo para fazer isso de forma iterativa. 

Assim, uma olhada rápida, aqui é apenas uma variável com a qual eu vou manter o controle da capacidade do meu buffer. Quantos bytes eu pode caber? Aqui está uma variável n com que eu vou continuar o controle de quantos bytes estão realmente em o tampão ou que o usuário digitou. Se você não viu isso antes, você pode especificar que uma variável como um int é não assinado, que como o nome sugere, significa que é não negativo, e por que Eu nunca quero incomodar especificando que um int não é apenas um int, mas é um int não assinado? É um int não negativo. O que o [inaudível] significa? 

AUDIÊNCIA: É descrevendo uma quantidade de memória que pode ser [inaudível]. 

DAVID MALAN: Yeah. Então, se eu disser não assinado, este é, na verdade, dando-lhe um pouco de memória extra e parece meio bobo, mas se você ter um pouco de memória adicional, que significa que você tem o dobro valores que podem representar, porque ele pode ser um 0 ou um 1. Então, por padrão, um int pode ser mais ou menos negativo de 2 bilhões de todo o caminho até positiva 2 bilhões. Essas são grandes intervalos, mas ainda é tipo de desperdício se você só se preocupam com tamanhos, que apenas intuitivamente deve ser não-negativo ou positivo ou 0, bem, então, por que você está desperdiçando 2 bilhões Os valores possíveis para números negativos se você nunca vai usá-los? Assim dizendo não assinado, agora meu int puder estar entre 0 e cerca de 4 bilhões. 

Então aqui é apenas um int C por razões não vamos entrar apenas agora como para por isso que é um int em vez de um char, mas aqui é a essência do que está acontecendo , e alguns de vocês pode ser utilizando, por exemplo, a função fgetc mesmo em PSet quatro ou após essa data, vamos vê-lo novamente no conjunto de problemas cinco, fgetc é bom porque como o nome tipo de, tipo de arcanely sugere, é uma função que recebe um personagem e assim, o que é fundamentalmente diferente sobre o que estamos fazendo em GetString é que não estamos usando scanf da mesma maneira. Estamos apenas rastejando passo-a-passo sobre tudo o que o usuário digitou em, porque sempre podemos atribuir uma char, e para que possamos sempre com segurança olhar para um caractere de cada vez, e a magia começa a acontecer aqui. Eu estou indo para rolar para baixo para meio desta função apenas para introduzir brevemente esta função. Muito como há um função malloc, há uma função realloc onde realloc permite realocar um bloco de memória e torná-la maior ou menor. Então, longa história curta e com uma onda de minha mão para hoje, sabe que o que GetString está fazendo é que é uma espécie magicamente de crescimento ou encolhendo o tampão como o utilizador tipos em sua cadeia. 

Portanto, se o usuário digita um corda curta, este código única aloca suficiente memória para se ajustar à string. Se o usuário mantém digitação como eu fiz isso de novo e de novo e novamente, bem, se o tampão do inicialmente esta grande e o programa percebe, a espere um minuto, eu estou fora do espaço, que vai dobrar o tamanho do buffer e, em seguida, o dobro do tamanho do buffer e o código que faz a duplicação, se olharmos para ele aqui, é apenas isso inteligente one-liner. Você pode não ter visto esta sintaxe antes, mas se você diz que é igual a estrela, esta é a mesma coisa que dizendo vezes capacidade para 2. Então ele simplesmente continua dobrando a capacidade do tampão e, em seguida, dizendo realloc para dar -se que muito mais memória. 

Agora, como um aparte, há são outras funções aqui que não vamos olhar para qualquer detalhe além de mostrar em GetInt, usamos GetString em GetInt. Nós verificamos que não é null, o que, recall, é o valor especial que significa algo correu mal. Estamos com falta de memória. Melhor verificar para isso. E nós devolver um valor de sentinela. Mas eu vou adiar para as observações quanto à por que e, em seguida, usar esse primo de scanf chamado sscanf e despeja que scanf sscanf, ou corda, permite que você dê uma olhada na linha que o usuário digitou no e deixá-lo analisá-lo e, essencialmente, o que eu sou fazendo aqui é que eu estou dizendo a sscanf, analisar tudo o que o usuário tem digitadas e certificar-se de% i, existe um inteiro nele, e não vamos entrar hoje exatamente porque há também um% c aqui, mas que, em poucas palavras permite nós para detectar se o usuário digitou em algo falso após o número. Então a razão que GetInt e GetString dizer-lhe para repetir, repetir, repetir é por causa de tudo que o código que nós escrevemos, é uma espécie de olhar para a entrada do usuário em certificar-se que é inteiramente numérico ou é um flutuante real valor de ponto ou semelhante, dependendo do que o valor funcionar você está usando. 

Ufa. ESTÁ BEM. Isso foi um bocado mas o ponto aqui é que a razão que tivemos as rodas de formação sobre é porque no nível mais baixo, Há apenas tantas coisas que pode dar errado que queríamos para lidar com preventivamente essas coisas certamente no primeiras semanas de classe, mas agora com PSet quatro e cinco e PSet além de você vai ver que é mais até você, mas também você é mais capaz de resolver esses tipos de problemas você mesmo. Quaisquer perguntas sobre GetString ou GetInt? Sim? 

AUDIÊNCIA: Por que você iria dobrar a capacidade do tampão em vez de apenas aumentar por isso a quantidade exacta? 

DAVID MALAN: Boa pergunta. Por que iríamos duplicar a capacidade do tampão em oposição apenas para aumentá-la por algum valor constante? Foi uma decisão design. Nós apenas decidimos que porque tende a ser um pouco caro, time-wise perguntar o sistema operativo para a memória, não o fizemos quer acabar se metendo uma situação para grandes cadeias que estávamos pedindo o sistema operacional novo e de novo e de novo e de novo em sucessão rápida para a memória. Então, nós apenas decidiu, um pouco arbitrariamente, mas esperamos razoavelmente, que, você sabe o que, vamos tentar chegar à frente de nós mesmos e manter apenas dobrando-o para que nós minimizar a quantidade de vezes temos que chamar malloc ou realloc, mas um total de julgamento chamar a ausência de saber o que os usuários podem querer digitar. Ambas as formas podem ser discutível. Indiscutivelmente bom. 

Então vamos dar uma olhada em um par de outros efeitos colaterais de memória, coisas que podem dar errado e ferramentas que você pode usar para capturar estes tipos de erros. Acontece tudo de você, mesmo que check50 não lhe contou como muito, têm escrito de buggy uma vez que um código de semana, mesmo se todos os testes são check50 passou, e mesmo se você e seu TF são super confiantes de que seu código funciona como previsto. Seu código foi buggy ou falho em que todos vocês, em usar a biblioteca CS50, foram fuga de memória. Você foi pedir ao sistema operacional para memória na maioria dos programas você escreveu, mas você nunca realmente dado de volta. Você chamou GetString e GetInt e GetFloat, mas com GetString, você tem nunca chamou unGetString ou dê- Voltar corda ou similar, mas nós vimos GetString que faz alocar memória por meio de malloc ou este realloc função, que é apenas muito semelhante em espírito, e ainda, temos sido pedindo o sistema operacional para memória e memória novamente e novamente mas nunca dando-lhe de volta. 

Agora, como um aparte, verifica-se que quando um programa termina, toda a memória é automaticamente liberado. Portanto, não foi um grande negócio. Ele não vai quebrar o IDE ou retardar as coisas, Mas quando os programas fazem geralmente vazar memória e eles estão correndo por um longo tempo. Se você já viu o pouco estúpido bola de praia em Mac OS ou a ampulheta no Windows, onde é uma espécie de abrandar ou pensando ou pensando ou apenas realmente começa para retardar a um rastejamento, muito possivelmente poderia ser o resultado de um vazamento de memória. Os programadores que escreveram o software que você está usando pedir ao sistema operacional para a memória cada poucos minutos, a cada hora. Mas se você estiver executando o software, mesmo que seja minimizado no seu computador por horas ou dias a fio, você pode estar pedindo mais e mais memória e nunca realmente utilizá-lo e para que o seu código pode ser, ou programas podem ser vazamento de memória, e se você começar a vazar memória, há menos memória para outros programas, e o efeito é a retardar tudo para baixo. 

Agora, este é de longe um dos os programas mais atrozes você terá oportunidades para executar em CS50, na medida como sua produção é ainda mais esotérica do que clang de ou fazer ou o todo do comando programas de linha que já executados antes, mas felizmente, incorporado em sua saída é algumas dicas úteis que super- irá ser útil quer para PSet quatro ou certamente PConfigurar cinco. Então valgrind é uma ferramenta que pode ser usado para procurar para vazamentos de memória em seu programa. É relativamente simples de executar. Você corre valgrind e, em seguida, mesmo mas é um pouco detalhado, traço verificação de vazamento traço é igual a plena e, em seguida dot corte e o nome do seu programa. Então valgrind, então, executar o seu programa e, no final do seu programa execução antes de ele sai e dá-lhe um outro pedido, que vai analisar o seu programa enquanto ele está em execução e dizer-lhe que você vazar qualquer memória e melhor ainda, se você tocar memória que não pertence a você? Não pode pegar tudo, mas é muito bom em pegar mais coisas. 

Então aqui está um exemplo de meu ter prazo este programa, tendo run valgrind, em um programa chamado memória, e eu vou para destacar as linhas que são em última análise, de interesse para nós. Portanto, há ainda mais distrações que eu tenha excluído do slide. Mas vamos ver o que este programa é capaz de nos dizer. Ele é capaz de nos dizer coisas como gravação inválido de tamanho 4. Em outras palavras, se você tocar em memória, especificamente 4 bytes de memória que você não deve ter, valgrind posso te dizer isso. Write inválido de tamanho 4. Você tocou quatro bytes que você não deve ter. Onde é que você faz isso? Esta é a beleza. Dot linha memória c 21 é onde você asneira e é por isso que é útil. Muito parecido com o GDB, pode ajudar apontá-lo ao erro real. 

Agora, este é um pouco mais detalhado, se não confuso. 40 bytes em blocos de 1 são, definitivamente, perdido no registro de perda 1 de 1. O que isso significa? Bem, isso significa apenas que você pediu 40 bytes e você nunca deu-lhe de volta. Você chamada malloc ou você chamada GetString e o sistema operativo deu-lhe 40 bytes, mas você nunca libertadas ou que a memória liberada, e para ser justo, nós nunca mostrar como para dar a volta a memória. Acontece lá fora é um super- função simples chamado livre. Recebe um argumento, a coisa você quer libertar ou dar para trás, 40 bytes, mas, aparentemente, neste programa foram perdidos na linha 20 de memória ponto c. 

Então vamos ver este programa. É super inútil. Isso só demonstra este erro particular. Então, vamos dar uma olhada. Aqui é principais e principais, observação, chamadas uma função chamada F e depois retorna. Então, nem tudo o que interessante. O que faz f fazer? Repare que eu não me incomodei com um protótipo. Eu queria manter o código o mínimo possível. Então eu coloquei f acima principal e isso é bom, certamente, para programas curtos como este. Então f não retorna nada e faz não levar nada, mas faz isso. Declara, bem como no exemplo Binky, um ponteiro chamado x que está acontecendo para armazenar o endereço de um int. Então, isso é o lado esquerdo. Em Inglês, o que é o lado direito fazendo? Alguém? O que é esta fazendo por nós? Sim? 

AUDIÊNCIA: [inaudível] vezes o tamanho de um int que é 10 vezes que [inaudível] DAVID MALAN: Boa e deixe-me resumir. Então alocar espaço suficiente para 10 inteiros ou 10, o que é do tamanho de um int, é quatro bytes, por isso 10 vezes 4 é 40, de modo que o lado direito que eu tenho realçado é dar-me 40 bytes e armazenar o endereço do primeiro byte em x. E agora, finalmente, e é aqui que este programa é buggy, o que é errado com linha 21 com base em que a lógica? O que há de errado com linha 21? Sim? AUDIÊNCIA: Você não pode índice em x [inaudível]. DAVID MALAN: Yeah. Eu não deveria índice em x como essa. Então sintaticamente, isso é OK. O que é bom é, muito parecido com você pode tratar o nome de uma matriz como se fosse um ponteiro, semelhante você pode tratar um ponteiro como se fosse uma matriz, e para que eu possa sintaticamente x suporte dizer alguma coisa, x suporte de i, mas a 10 é problemática. Por quê? 

AUDIÊNCIA: Porque não é no interior. 

DAVID MALAN: Não é dentro desse pedaço de memória. Qual é o maior valor que eu deveria estar colocando nesses colchetes? 9, de 0 a 9. Devido a indexação zero. Então, de 0 a 9 seria ótimo. Suporte 10 não é boa e mas, lembre-se, porém, cada vez Parece-me tentar fazer CS50 IDE acidente, digitando valores falsos, nem sempre cooperar, e, na verdade, muitas vezes você ter sorte só porque o sistema operacional não perceber que você nunca tão pouco passar algum pedaço de memória, porque você ficou dentro tecnicamente seu segmento, mas mais sobre isso em uma classe de sistemas operacionais, e assim por algo como isto poderia muito facilmente passar despercebido. Seu programa nunca vai falhar consistentemente, mas talvez uma vez em algum tempo. 

E então vamos tentar valgrind sobre isso, e é aqui onde vamos ficar sobrecarregado por a saída momentaneamente. Então, faça verificação de vazamento de memória valgrind é igual a memória barra ponto cheio. E aqui está o porquê eu prometo isso iria sobrecarregar. Aqui está o que valgrind, aqui está o que um programador, alguns anos- decidiu que seria uma boa idéia para a saída a aparência. Então, vamos dar sentido a isso. Então, todo o caminho na da esquerda lado sem uma boa razão é o ID do processo do programa nós apenas executado, o identificador único para o programa que nós apenas correu. Nós excluído que a partir de o slide, mas não é alguma informação útil aqui. 

Vamos rolar até o topo. Aqui é onde começamos. Portanto, não é tanto assim de saída. Aqui está o que write inválido 4 de tamanho na linha 21. Bem, o que era linha 21? Linha 21 foi exatamente este e faz sentido que eu estou no validamente escrito 4 bytes, porque eu sou tentando colocar este número inteiro, o que poderia ser qualquer coisa, isso só acontece de ser zero, mas eu estou tentando para colocá-lo em um local que não pertence a mim. Além disso, aqui em baixo, 40 bytes em um blocos são definitivamente perdidos em ficha 1. Isso porque quando eu chamar malloc aqui, eu nunca realmente liberar a memória. 

Então, como podemos corrigir isso? Deixe-me ir em frente e ser um pouco mais seguro e fazer 9 lá e me deixe aqui livre x. Esta é a nova função para hoje. Se eu agora executar novamente fazer corte de ponto de memória, vamos executar valgrind nele novamente, maximizar minha janela e pressione Enter. Agora, é bom. Eles enterram a boa notícia em todo este processo de saída. Todos os blocos heap eram livres. Vamos voltar ao que o heap é, mas não há fugas são possíveis. Portanto, este é apenas mais um ferramenta para o seu kit de ferramentas com o qual você pode começar a agora encontrar erros como esse. 

Mas vamos ver o que mais pode dar errado aqui. Transição Vamos agora realmente resolver um problema. Como um aparte, se isso vai aliviar um pouco de confusão ou tensão, isto agora é engraçado. Sim. Isso é muito bom. Porque ponteiros são endereços e endereços são, em geral, por convenção escrito com hexadecimal. Ha, ha, isso é engraçado agora. De qualquer forma, por isso vamos agora realmente resolver um problema. Isto tem sido super, super baixo-nível, até agora, e nós podemos realmente fazer útil coisas com esses detalhes de baixo nível. 

Então, nós introduzimos algumas semanas atrás, a noção de uma matriz. Uma matriz foi bom porque é difícil de limpar o nosso código porque se quiséssemos escrever uma programa com vários alunos ou vários nomes e casas e dormitórios e faculdades e tudo isso, poderíamos armazenar tudo mais limpa dentro de uma matriz. Mas propor uma desvantagem de uma matriz, até agora. Mesmo se você não sofri it yourself em um programa, apenas instintivamente, o que é uma coisa ruim sobre uma matriz, talvez? Ouço alguns murmúrios. AUDIÊNCIA: É difícil para alterar o tamanho. DAVID MALAN: É difícil para alterar o tamanho. Você não pode mudar o tamanho de uma matriz, de facto, por si só em C. Você pode alocar outro array, mover tudo, desde o antigo para o novo, e agora ter algum espaço extra, mas não é como um linguagem como Java ou Python ou qualquer número de outros línguas com que alguns de vocês pode estar familiarizado onde você pode simplesmente continuar adicionando coisas saciedade ao fim de uma matriz. Quando você tem uma série de tamanho 6, que é o seu tamanho, e tão parecido com a idéia anterior tendo um tampão de um determinado tamanho, você tem que adivinhar fora do portão qual é o tamanho que você quer que ele seja? Se você adivinhar muito grande, você está perdendo espaço. Se você adivinhar muito pequeno, você Não é possível armazenar os dados, pelo menos, sem muito trabalho. 

Então, hoje, graças aos ponteiros, nós podemos começar a costurar o nosso próprio costume estruturas de dados, e em verdade, aqui é algo que parece um pouco mais enigmática, à primeira vista, mas isso é o que nós vamos chamar um ligado lista, e seu tipo de nome resume isto. É uma lista de números, ou em Neste caso, uma lista de números, mas pode ser uma lista de tudo, mas ela ligados entre si por meio de setas, e apenas dar um palpite com qual técnica vamos ser capazes para unir, tipo de como pipoca com um fio, uma ligada listas retângulos aqui? Seus números? O que é o recurso de linguagem subjacente? 

AUDIÊNCIA: Um ponteiro. 

DAVID MALAN: Um ponteiro. Então cada um desses setas representa aqui um ponteiro ou apenas um endereço. Portanto, em outras palavras, se eu quiser para armazenar uma lista de números, Eu não posso simplesmente armazená-lo se eu quiser a capacidade para aumentar e diminuir minha estrutura de dados em uma matriz. Então eu preciso ter um pouco mais sofisticação, de notar que esta tipo de imagem sugere que, se você só tem pequenos tópicos ligar tudo em conjunto, provavelmente não é tão difícil de fazer espaço entre dois destes rectângulos ou dois desses nós, como vamos começar chamando-os, coloque em um novo nó, e depois com uma nova linha, apenas abandonar os três nós juntos, a primeira, a última, e por um que você acabou de inserir no meio. 

E, de fato uma lista ligada, ao contrário de uma matriz, é dinâmico. Ela pode crescer e pode encolher e você não faz tem que saber ou se importar com antecedência como quantidade de dados que você vai estar armazenando, mas acontece que nós temos que ser um pouco cuidadoso sobre como implementar isso. Então, primeiro vamos considerar como vamos implementar um destes pequenos retângulos. É fácil de implementar um int. Você acabou de dizer int n e, em seguida, você obtém 4 bytes para um int, mas como faço para obter um int, chamá-lo de n, e, em seguida, um ponteiro, vamos chamá-lo em seguida. Poderíamos chamar essas coisas qualquer coisa que quisermos mas eu preciso de uma estrutura de dados personalizado. Sim? 

AUDIÊNCIA: Ampersand [inaudível]. 

DAVID MALAN: Então e comercial, vamos utilizar para obter o endereço de um nó potencialmente. Mas precisamos de outro O recurso de C em ordem para me dar a capacidade de criar este retângulo costume, este costume variável se você, na memória. AUDIÊNCIA: Uma struct. DAVID MALAN: Uma struct. Lembre-se da última semana, introduzimos struct, esta palavra-chave relativamente simples que nos permite fazer coisas como esta. C não veio com um conjunto de dados estrutura chamada estudante. Ele vem com int e bóia e carvão animal e tal, mas ele não vem com o aluno, mas podemos criar um tipo de dados do aluno, uma estrutura estudante, com esta sintaxe Aqui. E você vai ver isso de novo e de novo. Então não se preocupe com memorizar as palavras-chave, mas a palavra-chave que é importante é apenas o fato de que nós dissemos struct e, em seguida, nós o chamamos de estudante e no interior do aluno era um nome e uma casa ou um dormitório ou similares. 

E agora, hoje, vamos propor isso. Eu adicionei algumas palavras, mas se eu quiser para implementar este retângulo que é tem tanto um int e um ponteiro, você sabe, eu sou vai declarar uma estrutura chamado nó. Eu também sou, dentro dele, vai dizer que um nó, rectângulo, tem um int e vamos chamá-lo e n ele tem um ponteiro próximo. E isso é um pouco detalhado, mas se você pensar sobre isso, as setas que estavam na imagem um momento atrás são de que tipo de dados? Quando cada um desses setas apontando está a que tipo de estrutura de dados? Não é apenas que aponta para um int per se. Ele está apontando para o coisa toda rectangular e que coisa retangular, nós dissemos, é chamado de nó. E então nós meio que tem que recursivamente definir esta tais que um nó, digamos, irá conter um int chamado n e um ponteiro chamado seguinte e no tipo de estrutura de dados para o qual que os pontos de ponteiro é, aparentemente, vai ser nó struct. 

Portanto, este é irritantemente verboso e apenas para ser pedante, a razão pela qual nós não podemos apenas dizer isto, que, francamente, parece muito mais legível, é porque lembre-se que C ler as coisas de cima para baixo, da esquerda para a direita. Não é até chegarmos a ponto e vírgula que a palavra-chave nó realmente existe. Portanto, se queremos ter esse tipo de referência cíclico dentro dos dados estrutura, nós temos que fazer isso, onde dizemos nó struct na parte superior, que dá-nos uma mais maneira de descrever este coisa, então dentro dizemos nó struct, e depois na última linha podemos dizer, tudo bem, C, a propósito, basta ligar para todo este maldito coisa que um nó e parar usando a palavra-chave struct completamente. Portanto, esta é apenas uma espécie de sintática truque que finalmente nos permite criar algo que se parece exatamente com isso. 

Então, se nós agora podemos assumir implementar essa coisa em C, como é que nós, na verdade, iniciar atravessando este? Bem, na verdade, tudo o que temos a fazer é iteração da esquerda para a direita e apenas tipo de inserir os nós ou excluir nós ou procurar coisas onde quisermos, mas para fazer isso, vamos em frente e fazer as coisas um pouco mais real, porque isso tem sido super-baixo nível até agora. Será que alguém literalmente gostaria de ser o primeiro? ESTÁ BEM. Vamos lá para cima. Qual o seu nome? 

DAVID: David. DAVID MALAN: David. Bom te conhecer. Eu também. Tudo certo. E precisamos de um número 9. Não é tão bom como o primeiro, talvez. OK, número 9. Um número 17, por favor. Deixe-me voltar um pouco mais longe. Number 22, por favor, e e quanto a mais para trás se eu posso ver nenhuma mão com toda a luz ou não. Alguém está sendo ofereceu ali. Você quer chegar? Seu antebraço é forçado a subir. OK, 17. 22. 26 está vindo para baixo. Será que ninguém gosta de forcefully-- Vamos lá para cima. Um voluntário real. 

Então, muito rapidamente, se vocês poderiam organizar -se apenas como os nós na tela. Obrigado. E você vai ser 26. Todas as introduções certas e rápidas. Então, eu estou David e você também? DAVID: David. DAVID MALAN: E você é? JAKE: Jake. SUE: Sue. ALEX: Alex. RAPHAEL: Raphael. TAYLOR: Taylor. DAVID MALAN: Taylor. Excelente. Então, esses são nossos voluntários para hoje e ir em frente e mudar um pouco dessa forma, e apenas ir em frente e manter segurando seus números como você é ou o seu primeiro sinal e com a mão esquerda, vá em frente e apenas implementar essas flechas, apenas de modo que a mão esquerda é, literalmente, apontando para o que você deve apontar na, e dar-se algum espaço para que podemos ver visualmente os braços, na verdade, apontando, e você pode apenas apontar tipo de para o chão está bem. 

Portanto, temos aqui uma lista ligada de um, dois, três, quatro, cinco nódulos inicialmente, e perceber que temos este especial ponteiro no início quem é chave, porque temos de manter o controle de toda a lista de comprimento de alguma forma. Esses caras, mesmo que sejam deixadas para a direita, volta para trás na memória, na verdade, eles podem estar em qualquer lugar na memória do computador. Então, esses caras poderiam ser em pé em qualquer lugar na fase e isso é bom, contanto que eles são na verdade, apontando para o outro, mas para manter as coisas limpo e simples, nós vamos apenas desenhá-los esquerda para direita este, mas pode haver lacunas maciças entre esses nós. 

Agora, se eu quero realmente inserir alguns novo valor, vamos em frente e fazer isso. Nós temos uma oportunidade agora para escolher outro nó. Digamos que vamos começar com mallocing 55. Será que alguém poderia me importo de ser malloc? OK, vamos lá para cima. Qual o seu nome? RAINBOW: Arco-íris. DAVID MALAN: Arco-íris? Tudo certo. Malloc do arco-íris. Vamos lá para cima. Portanto, agora temos de nos perguntar algorithmically onde podemos colocar 55. Então, todos nós sabemos, obviamente, onde ela provavelmente pertence, se nós estamos tentando para manter este classificado e se vocês poderiam tomar uma um passo para trás para que não caia o palco, que seria ótimo. Então, na verdade, Arco-Íris, começar de novo aqui comigo, porque nós, como o computador pode agora só vê uma variável de cada vez. Assim, se este é o primeiro nó. Observe que ele não é um nó, ele é apenas um ponteiro, e é por isso que ele está desenhado para ser apenas o tamanho de um ponteiro, não um desses rectângulos completos. Então, nós estamos indo para verificar em cada iteração é de 55 a menos de 9? Não. É de 55 a menos de 17? Não. Menos de 22? Menos de 26? Menos de 34? E agora, obviamente, Íris pertence no final. Então, para ser claro, eo que era o seu nome, Taylor? 

TAYLOR: Taylor. DAVID MALAN: Então entre Taylor mão esquerda e as mãos do arco-íris aqui, cuja mão precisa apontar para o que em Para inserir 55 nesta lista? O que precisamos fazer? Sim? 

AUDIÊNCIA: a mão de Taylor precisa apontar esquerda. 

DAVID MALAN: Exatamente. Então, a inserção de um nó para o fim da lista é muito simples, porque Taylor apenas tem a ponto, ao invés de para o chão ou vamos chamá-lo nulo, nulo é uma espécie de ausência de um ponteiro ou uma especial ponteiro zero, você está vai apontar com sua esquerda mão no arco-íris e, em seguida, Arco-Íris, Onde deve a sua esquerda mão, provavelmente, apontar? Baixa. Não é bom se sua mão é uma espécie de apontar fora aqui ou qualquer tipo de que maneira. Isso seria considerado um valor de lixo, mas se ela aponta para algum valor conhecido, vamos chamá-lo de zero ou nulo, que é OK porque temos um termo neste e sabemos que a lista agora está completa. 

Então, o que é outra caso relativamente simples? Poderíamos malloc 5? Vamos lá para cima. Qual o seu nome? TIFFANY: Tiffany. DAVID MALAN: me desculpe? TIFFANY: Tiffany. DAVID MALAN: Tiffany. Tudo certo. Tiffany foi malloced com o valor 5. Vamos lá para cima. Este é relativamente fácil demais, mas vamos considerar a ordem das operações agora. Foi muito fácil com Taylor no final. Número 5 é, naturalmente, menos do que 9, e por isso temos David, dispomos de Tiffany, e qual era o seu nome? 

JAKE: Jake. 

DAVID MALAN: Jake. Tiffany, Jake, e David. Cuja mão deve ser atualizado primeiro? O que você quer fazer aqui? Há um par de maneiras possíveis, mas há também uma ou mais formas erradas. 

AUDIÊNCIA: Comece com mais à esquerda. 

DAVID MALAN: Comece com o mais à esquerda. Quem é o mais à esquerda aqui, então? AUDIÊNCIA: First. 

DAVID MALAN: OK. Então comece com o primeiro e onde você quer atualizar mãos de David para ser? AUDIÊNCIA: Rumo a 5. DAVID MALAN: OK. Então David, ponto em cinco ou Tiffany aqui, e agora? 

AUDIÊNCIA: Tiffany aponta para o 9? DAVID MALAN: Perfeito, exceto de Binky cabeça apenas uma espécie de caiu, certo? Porque o que há de errado com esta imagem, literalmente? AUDIÊNCIA: Nada está apontando. DAVID MALAN: Nada é apontando para Jake agora. Temos literalmente órfão 9 e 17, e nós temos literalmente vazou tudo isso de memória, porque, atualizar a mão de David em primeiro lugar, que é bem, na medida em que é corretamente apontando para Tiffany agora, mas se ninguém tinha o clarividência de apontar para Jake, então nós perdemos o totalidade dessa lista. Então, vamos desfazer. Então isso foi uma coisa boa para tropeçar mas vamos corrigir agora. O que devemos fazer primeiro em vez disso? Sim? 

AUDIÊNCIA: Tiffany deve apontar para o 9? DAVID MALAN: Eu não posso chegar tão perto de você. Quem deve apontar para o 9? 

AUDIÊNCIA: Tiffany. 

DAVID MALAN: Tudo bem. Então Tiffany deve primeiro ponto no 9. Então Tiffany deve tomar em um valor idêntico para David, que parece redundante, por um momento, mas isso é bom porque agora, segundo passo, podemos atualizar a mão de David para apontar para Tiffany, e então se Nós meio que limpar as coisas como se este é o tipo de primavera-like, agora que é uma inserção correcta. Assim excelente. Portanto, agora estamos quase lá. Vamos inserir um final, valor como o valor 20. Se pudéssemos malloc um voluntário final? Vamos lá para cima. Então, este é um pouco mais complicado. Mas, realmente, o código estamos escrever, ainda que verbalmente, é como ter um monte se as condições de agora, certo? Tivemos uma condição verificando se ele pertence no final, talvez o início. Nós precisamos de algum tipo de loop para encontrar o ponto no meio. Então vamos fazer isso com o que é seu nome? 

ERIC: Eric. 

DAVID MALAN: Eric? Eric. Bom te conhecer. Portanto, temos 20. Menos de cinco? Não. Menos de nove? Não. Menos de 17? Não. ESTÁ BEM. Ele pertence aqui e seus nomes são novamente? SUE: Sue. DAVID MALAN: Sue. ALEX: Alex. DAVID MALAN: Sue, Alex, e? ERIC: Eric. DAVID MALAN: Eric. Cujas mãos precisa ficar atualizado em primeiro lugar? 

AUDIÊNCIA: Eric. ESTÁ BEM. Então Eric deve apontar para onde? Aos 22 anos. Boa. E agora o que é o próximo? Sue pode, então, apontar para Eric e agora, se vocês apenas fazer algum espaço, o que é bom visualmente, agora que temos feito a inserção. Então, vamos agora considerar uma pergunta, mas muito obrigado para os nossos voluntários. Muito bem feito. Você pode manter esses, se você gosta. E nós temos um belo presente de despedida se você cada gostaria de ter uma bola de stress. Deixe-me apenas passar isso para baixo. Então, qual é o takeaway deste? Este parece ser incrível na medida em que temos agora Apresentar uma alternativa para uma matriz que não é tão confinado para uma matriz de algum tamanho fixo. Elas podem crescer de forma dinâmica. 

Mas muito como temos visto em semanas passado, nós nunca conseguir nada de graça, como certamente há um trade-off aqui. Assim, com um upside de um ligado lista, é esse dinamismo? Esta capacidade de crescer e, francamente, que poderíamos ter feito de exclusão e poderíamos encolher conforme necessário. Qual o preço que estamos pagando? Duas vezes mais espaço, em primeiro lugar. Se você olhar para a foto, não mais Eu sou armazenar uma lista de inteiros. Eu estou armazenando uma lista de inteiros mais ponteiros. Então, eu estou dobrando a quantidade de espaço. Agora, talvez isso não seja tão um grande negócio 4 bytes, 8 bytes, mas certamente poderia adicionar -se para grandes conjuntos de dados. O que é outra desvantagem? Sim? 

AUDIÊNCIA: Nós temos que atravessá-los um por um. DAVID MALAN: Yeah. Nós temos que atravessá-los um por um. Você sabe o que, que deram este super recurso conveniente de colchete notação, mais propriamente conhecido como acesso aleatório, onde podemos simplesmente pular a um elemento individual mas agora se eu ainda tinha meus voluntários aqui, se eu queria encontrar o número 22, eu não posso apenas saltar para suporte algo algo. Eu tenho que olhar sobre a lista, muito como nossos exemplos de pesquisa de forma linear, para encontrar o número 22. Então, nós parecem ter pago um preço lá. Mas a gente pode, no entanto, resolver outros problemas. 

Na verdade, deixe-me apresentar apenas um par de elementos visuais. Então, se você foi para baixo para Mather do Refeitório recentemente, você deve se lembrar que a sua pilhas de bandejas como este, nós emprestamos estes a partir de Annenberg antes da aula. Portanto, esta pilha de bandejas, porém, na verdade, é representativa de uma estrutura de dados informática. Existe uma estrutura de dados em ciência da computação conhecida como uma pilha que muito bem presta-se a exatamente esse visual. Por isso, se cada uma destas bandejas não é um bandeja, mas como um número e eu queria para armazenar números, eu poderia colocar um aqui em baixo, e eu poderia colocar outro aqui em baixo, e continuar empilhamento números em cima do outro, e que está potencialmente útil sobre esta é que o que é a implicação desta estrutura de dados? Que número posso retirar primeiro o mais convenientemente? O mais recentemente, um posto lá. 

Então é isso que nós chamaríamos em ciência da computação uma estrutura de dados LIFO. Último a entrar, primeiro a sair. E vamos ver em breve por que que pode ser útil, mas, por agora, basta considerar o imóvel. E é uma espécie de idiota se você acha sobre como o salão de jantar faz. Toda vez que eles bandejas limpas e colocar os mais frescos no topo, você poderia ter uma limpo anteriormente mas, eventualmente, muito sujo e empoeirado bandeja na parte inferior se você nunca realmente chegar ao fundo da referida pilha, porque você só manter colocando o novo e os limpos em cima dela. A mesma coisa pode acontecer num supermercado também. Se você tem um caso de exibição de leite e cada vez CVS ou quem recebe mais leite, você apenas empurrar os leites você já tem a parte de trás e você colocar os novos na frente, você vai ter alguns bastante desagradável leite no final da estrutura de dados, porque é sempre na parte inferior ou equivalentemente é sempre na parte de trás. 

Mas há outra maneira de pensar sobre alinhando dados e por exemplo, isso. Se você é uma daquelas pessoas que gosta a linha de fora de lojas da Apple quando um novo produto vem fora, você provavelmente está Não usando uma pilha de dados estrutura porque você alienaria todos os outros que é fazendo fila para comprar algum brinquedo novo. Em vez disso, você provavelmente está usando que tipo de estrutura de dados ou que tipo de sistema no mundo real? Esperemos que seja uma linha, ou mais corretamente ou mais britânico-like, uma fila. E verifica-se uma fila é também um estrutura de dados em ciência da computação, mas uma fila tem uma muito propriedade diferente. Não é LIFO. Último a entrar, primeiro a sair. Deus me livre. É, em vez FIFO. Primeiro a entrar, primeiro a sair. E isso é uma coisa boa de justiça amor ' certamente quando você está alinhando super início da manhã. Se você chegar lá primeiro, você quer sair primeiro também. 

E assim todos estes dados estruturas, filas e pilhas e cachos de outros, acaba por você pode pensar nisso como apenas uma matriz. Esta é uma matriz, talvez um tamanho fixo 4, mas tinha ser uma espécie de bom se pudéssemos simplesmente amontoar bandejas quase infinitamente alto se têm que muitas bandejas ou números. Então, talvez nós queremos usar uma lista ligada aqui, mas o trade-off vai ser potencialmente que precisamos de mais memória, leva um pouco mais de tempo, mas nós não limitar a altura da pilha, bem como vitrine de Mather pode limitar o tamanho da pilha, e assim que estas são decisões de projeto ou opções disponíveis para nós em última instância. Assim, com estes dados estruturas, nós começamos vendo novos limites superiores potencialmente sobre o que anteriormente foi super rápido e onde vamos deixá fora hoje e onde vamos esperar para chegar a é na quarta-feira, nós vamos começar a olhar para um conjunto de dados estrutura que nos permite pesquisar através de dados em log tempo final novamente. E vimos que, lembre-se, na semana de zero e um com busca binária ou dividir e conquistar. Está vindo de volta e melhor ainda, o Santo Graal para nesta quarta-feira será a de chegar com o estrutura de dados que corre verdadeiramente ou em teoricamente constante de tempo, por meio de que não importa quantas milhões ou bilhões de coisas temos na estrutura de dados, ele será levar-nos tempo constante, talvez um passo ou dois passos ou 10 passos, mas números de passos constantes para procurar por essa estrutura de dados. Que de fato será o santo graal mas mais sobre isso na quarta-feira. See ya então. 

[Música tocando]