[Música tocando] CAMILLE REKHSON: Oi, todo mundo. Bem-vindo ao questionário CS50 de zero sessão de revisão. Sou Camille. E eu vou estar indo sobre alguns tópicos com você caras hoje para ajudá-lo preparar para o quiz. Então aqui está o nosso não exaustiva lista de tópicos que você deve estar familiarizado com para o quiz. Estes foram levados diretamente a partir do programa. Eu sei que parece um monte. Mas confie em mim, você aprendeu tudo essas coisas nas últimas semanas. 

Então, nós lhe definitivamente vai ao longo de um monte deles hoje. Mas também levar algum tempo em seu própria para rever essas coisas. E se você não estavam familiarizados com que algumas dessas coisas são, certifique-se de pedir um de nós. Além disso, para a palavra oficial no questionário, vá a este link. Isso vai ter todas as informações com o quarto você precisa para ir em, dividido em ordem alfabética, e também algumas dicas sobre quais materiais você deve estar estudando, e que tipo das perguntas do questionário que você pode esperar. Então, certifique-se de verificar isso. 

Além disso, algumas dicas para quando você estão se preparando para o exame. Prática de codificação em papel. Eu sei que você me acostumei a ter a verificação de IDE para os seus erros para você, e it's-- quando você está digitando-o, é um pouco diferente do que ter para escrever as coisas. Assim, a prática de fazer alguma codificação. Alguns bons funções para praticar fazer são strlen e atoi, vendo se você pudesse escrever aqueles em seu próprio país. Estar familiarizado com os conjuntos de problemas. Na maioria dos anos há questões que dizem respeito a algum do material conjunto de problemas. Então certifique-se que você compreenda como fazer todos os conjuntos de problemas. 

Tente fazer alguns dos antigos questionários sob a restrição de tempo 75 minutos. Um monte de quizzes pode ser tipo de comprimento. Portanto, é uma boa maneira de dar -se um pouco de prática, e quanto tempo vai levá-lo, e como você deve dividir o seu tempo para se certificar você terminar tudo até o final. E também, você tem uma única página, dois lados folha de referência que você pode escrever o que quer sobre a utilização durante o quiz. Então, quando você está criando isso, que é também realmente uma ótima maneira de estudar porque você vai tipo de rever coisas como você está escrevendo. 

Assim, qualquer perguntas gerais sobre o quiz, ou como ele funciona? Sim. 

AUDIÊNCIA: Será que a lista de tópicos que apenas mostrou estar disponível para nós conectados? 

CAMILLE REKHSON: Este completo do slide show será lançado para o site. Além disso, o vídeo de revisão de hoje sessão será no site. Portanto, não se preocupe muito com escrever as coisas por toda parte. Tudo estará lá. Alguma outra pergunta? OK, então vamos começar. 

Então, uma coisa que estar familiarizado com é os diferentes tipos de dados e do tamanho que eles assumem. Isso também pode ser uma grande coisa para anote em sua folha de referência, só para ter certeza de que lembre-se tudo isso. Mas-- caracteres são assim de 1 byte. Ints são 4 bytes. Há muito, muito, que é basicamente mais espaço para um número inteiro, é de 8 bytes. Um flutuador é de 4 bytes. A dupla, que basicamente dá-lhe mais espaço para armazenar um float, é de 8 bytes. E em seguida, um ponteiro é também 8 bytes. Qualquer dúvida sobre isso? 

Então binário é outro tópico que nós temos coberto um pouco neste semestre. Então, vamos fazer alguma praticar com a conversão entre o binário e decimal. Então, alguém tem alguma idéia do que que primeiro seria? Alguém? Sim, é 42. Então, se você se lembra, cada dos lugares em binário é basicamente como 2 ao poder daquele lugar. 

Assim que o primeiro ponto é de 2 a 0 do poder. E nós temos 0 lá, então nada lá. O próximo lugar é de 2 à primeira potência. E nós temos um 1 lá, de modo que é basicamente um 2. O próximo lugar é de 2 a o segundo, que é 4. Não temos nada lá. O próximo lugar mais é de 2 a o terceiro, o que seria 8. E nós temos um lá. E nós continuar. Last-- que o mais à uma esquerda é onde nós temos 32. E assim, temos basicamente 32 plus 8 plus 2 para obter 42. Alguma pergunta? 

AUDIÊNCIA: Qual é o índice para? 

CAMILLE REKHSON: O subscrito basicamente nos diz que é binário. Portanto, há um dois lá. Se houvesse como-- na próxima um, ou quando estamos convertendo decimal para binário, há um 10 nos mostra que este número é originalmente em decimal. 

AUDIÊNCIA: Obrigado. 

CAMILLE REKHSON: Yeah. Quaisquer outras perguntas sobre esse? OK, então vamos tentar o próximo um, em seguida, decimal para binário. Assim, tendo 50 e colocando que em binário. como você faria isso? Sim. 

AUDIÊNCIA: 110.010. 

CAMILLE REKHSON: Sim. Então um-- uma maneira fácil de pensar sobre conversão de decimal para binário a-- é que muitas vezes ajuda para escrever o que os diferentes potências de 2 são. E, em seguida, passar por isso, e veja qualquer que seja a mais elevada daqueles é que você pode colocar para a número decimal sem passar por cima. 

Portanto, neste caso, um dos os poderes dos dois é de 32. Então, entra em 50 32. Mas a próxima energização seria 64, o que obviamente não se encaixa em 50. Assim, o maior que temos é a de 32. O próximo até 16. E 32 mais 16 é de apenas 48. Assim, ainda que se encaixa 50. Portanto, temos de 1 em ambos os. E, em seguida, se continuarmos indo para baixo, a única coisa que precisamos esquerda é mais 2 para obter 48-50. Então nós temos um 1 nessa posição, e um 0 na última posição. Porque não há nada em o 2 à 0 º lugar. Perguntas sobre a conversão decimal para binário? 

Então agora vamos tentar fazer alguns adição binária. Como quando você adiciona os dois para cima? Sim. 

AUDIÊNCIA: 11.100. 

CAMILLE REKHSON: Sim. Então, fazendo disso em binário é bastante o mesmo que fazê-lo em decimal. Exceto se você tiver dois ser de 1 somados, 1 mais 1 é 2, mas 2 em binário é de 1 0. Então você tem que levar a 1, e mantê- levá-lo para as colunas casal. E fora isso, basta adicionar normalmente. Qualquer dúvida sobre isso? Sim. 

AUDIÊNCIA: Desculpe, mas o que é o último lugar? Há seis números. Assim, a coluna mais à esquerda, Que valor tem isso? CAMILLE REKHSON: Nesta um fundo? AUDIÊNCIA: Na parte superior um, para 50. CAMILLE REKHSON: Para 50? Ah, então o mais à esquerda é de 32. 

AUDIÊNCIA: 32? 

CAMILLE REKHSON: Sim, por isso faria ser de 32, 16, em seguida, 8, 4, 2, 1 ou 0--. Bem, é 2 a zeroth, que é 1. Sim. Qualquer outra dúvida sobre isso? OK, então nós vamos fazer um pouco com hexadecimal. Portanto, este pode ser um pouco menos familiar, porque eu sei que nós fizemos muito mais com binário. Mas uma boa maneira de pensar em hexadecimal é para quebrar um binário número em 4 pedaços bits. Porque cada um dos 4 bits número binário é, basicamente, um dos números hexadecimais. 

Então, se temos este primeiro, temos basicamente oito 1s. Portanto, aqueles podem ser divididos up-- 

AUDIÊNCIA: 255. 

CAMILLE REKHSON: Diga isso de novo. AUDIÊNCIA: 255 em decimal, ou 0xFF em hexadecimal. CAMILLE REKHSON: Sim, ele é. Então, se você dividir-se que em dois blocos de 4 bits, temos basicamente quatro conjuntos de 1. Qual é o maximum-- basicamente, o máximo podemos obter com 4 bits de binário. E o máximo que conseguimos obter para em hexadecimal que seria uma F. Então, teríamos de dois f. Qualquer dúvida sobre isso? Sim? 

AUDIÊNCIA: Você pode repetir isso. CAMILLE REKHSON: Claro. Assim, cada um, basicamente, lugar de hexadecimal é equivalente para os 4 bits de um binário. Assim, a maneira mais fácil de fazer isso é para dividi-lo em pedaços de 4 bits. Portanto, neste caso, temos oito 1s. Então, se nós dividir os em dois blocos de 4 bits, teríamos dois conjuntos de quatro 1s. E cada um daqueles é equivalente a F. Se você acha que about-- Eu sei que nossos cérebros são tipo de fio a pensar mais através decimal, porque isso é o que estamos acostumados. Portanto, uma forma que você poderia pensar nisso como os quatro de 1 é igual a 15 em decimal. E 15 em hexadecimal é F. Então é isso uma outra maneira você pode pensar por ele. Sim. 

AUDIÊNCIA: Qual é o 0x para? 

CAMILLE REKHSON: A 0x denota que é hexadecimal. Então, nós apenas colocar isso prefixo há, normalmente. Outras perguntas sobre isso. OK, então vamos tentar ir a outra maneira então. Neste caso, have-- arrependido? AUDIÊNCIA: [inaudível]. CAMILLE REKHSON: Nós estamos indo para binário. Então, indo para o outro lado. Mas, neste caso, temos 5 e A. Então, se nós pensamos sobre isso, Se cada um dos those-- a 5 e A são o tanto vai representar um pedaço de 4 bits, como você diria 5 em binário? 

AUDIÊNCIA: 0101. 

CAMILLE REKHSON: Sim, então essa é a parte 0101. E, em seguida, como você diria A em-- 

AUDIÊNCIA: 10. CAMILLE REKHSON: Diga ele-- arrependido? AUDIÊNCIA: 10. CAMILLE REKHSON: Sim, então essa é a segunda parte dela. E então, se você colocar os dois juntos, isso é como você obter o pleno binário para o hexadecimal. Sim? 

AUDIÊNCIA: Para saber que A é 1010, você tem de memorizá-lo? Ou você pode como-- 

CAMILLE REKHSON: Então se vocę-- o differe-- assim quando você está atravessando binário, basicamente binário tem de 0 a 9 e, em seguida, A a F como os seus 16 coisas. Assim, se todo o caminho para 0 se 9-- vocę-- 9 e, em seguida, A, basicamente, se convertido em decimal, A Seria como 10, B seria como 11. E se você pensar sobre o binário 1010 é de 8 e 2, porque esses são os dois lugares que somam 10, que é exatamente o que A é equivalente a. Então, isso é uma espécie de fácil maneira de pensar sobre isso. Outras perguntas sobre hexadecimal. 

OK, então agora nós estamos indo tomar um olhar para operadores bit a bit. Assim que estes podem definitivamente chegar no quiz. Eu sei que não tem trabalhou com eles muito. Mas nós apenas estamos indo para fazer uma pequena revisão destes. Portanto, esperamos que estes serão um pouco mais familiar para você. Assim, os seis operadores bit a bit que temos aqui. E eles nos manipulam bits individuais. Assim, o operador AND é um único e comercial. Não confunda isso com oe comercial duplo, que é a lógica AND que nos permite comparar duas coisas. 

O único E é assim que pudermos manipular as coisas bit a bit. Então, isso nos dá o resultado de 1 se ambos dos argumentos que estamos comparando são o same-- ou são 1. E a barra vertical, OR, dará nos 1, se pelo menos um deles é 1. Então, basicamente exatamente o que as palavras significam. E, se os dois bits forem 1, 1 e 1 nos dá uma. Mas, com a OR, se é ou 0 1, ou 1 ou 1, em qualquer dos casos, 1 temos como sendo um deles. Então, em seguida, que seria um 1. Audiência: O que você quer dizer que diz que dá um? 

CAMILLE REKHSON: A resultado. Tipo de, como você would-- se você fez 0 e 1, o resultado de que seria 1-- ou 0 1 e com o resultado de que seria 0, desculpe. Sim, ele era uma espécie de resultado da expressão. E então, este símbolo de acento circunflexo é o XOR, ou OR exclusivo. Então isso significa que exclusivamente a uma ou exatamente um dos dois argumentos é igual a 1. E então ele iria dar-lhe um. 

A pequena linha squiggly é o operador NOT. Portanto, ao contrário do resto deles, que operam em um par de bits, o operador NÃO leva apenas um pouco, e vai lançá-lo. Então, se você give-- se você fizer NÃO 0, ele iria dar-lhe um. E se você não uma, que lhe daria 0. Sim? 

AUDIÊNCIA: Qual é a diferença entre o OR com uma linha eo OR com dois? CAMILLE REKHSON: Então o OR com duas linhas é o OR lógico. Então, isso é para comparar dois inteiros cheios, ou dois-- para ver se as coisas são iguais. Ou como fazer isso é igual a este, Ou isso é igual a este tipo de coisa. Considerando que o único bar OR, é para fazer as coisas bit a bit. Sim. 

AUDIÊNCIA: O que você quer dizer com bit a bit? 

CAMILLE REKHSON: Então, bit a bit está funcionando directamente com os bits em binário. 

AUDIÊNCIA: Oh, eu vejo. 

CAMILLE REKHSON: Sim, então trabalhando com 0 e 1.. Nós vamos fazer alguns exemplos de este depois, apenas por isso não é muito confusa. E, em seguida, os dois últimos são o deslocamento para a esquerda eo deslocamento para a direita. Quais são, basicamente, dois a menos do que sinais ou dois sinais de maior que. E eles deslocado para o bit o número dado de lugares que você lhe dá na direção. Por isso, seria ou transferi-lo para a esquerda, ou para a direita. Sim? AUDIÊNCIA: Qual é a sintaxe para execução? 

CAMILLE REKHSON: Nós estamos indo para ir através de um exemplo, em um segundo. Portanto, esperamos, que vai ajudar. Quaisquer perguntas sobre apenas o que se passa aqui, antes-- OK. Então, passando por alguns exemplos. Vamos começar com os uns e. O que teremos se fez 0 e 1? 

AUDIÊNCIA: 0. CAMILLE REKHSON: OK, e se fizéssemos um AND 1? AUDIÊNCIA: 1. CAMILLE REKHSON: Sim, o que se fizéssemos 0 OR um? AUDIÊNCIA: 1. CAMILLE REKHSON: Como cerca de 1 ou 1? AUDIÊNCIA: 1. CAMILLE REKHSON: OK, como sobre XOR 0 1? AUDIÊNCIA: 1. CAMILLE REKHSON: E um XOR 1? AUDIÊNCIA: 0. CAMILLE REKHSON: Vocês são bons. Que tal NÃO 0? 

AUDIÊNCIA: 1. CAMILLE REKHSON: E NÃO 1? AUDIÊNCIA: 0. CAMILLE REKHSON: OK, em seguida, esta última um é um pouco um com o deslocamento. Então, se nós inicialmente definido para ser x 8, e então Y é X deslocado para a esquerda 3, o que teria que nos dar? 

AUDIÊNCIA: [inaudível]. CAMILLE REKHSON: Diga isso de novo. AUDIÊNCIA: [inaudível]. CAMILLE REKHSON: Então, este realmente nos dá 64. AUDIÊNCIA: [inaudível]. CAMILLE REKHSON: Então eu sou apenas indo para escrever este aqui para cima, o que faz um pouco de sentido. Se tivermos 2 a 0, 2 a 1, 2 a 2, 2 a 3 vai ser 8. E se nós queremos mudar isso mais 3 bits para a esquerda, que seria de 2 a 4, 2 a 5, e 2 para o 6, e 2 a 6 é de 64. Será que isso faz sentido? Sim. 

Platéia: que todos os turnos de 1 e 0 do número binário para as-- 

CAMILLE REKHSON: Sim. E você não terá que se preocupar sobre a questionário sobre estes sendo negativo. Nós não vai fazer você lidar com desvios negativos de qualquer forma. Quaisquer outras perguntas sobre este? Sim. 

AUDIÊNCIA: Se ele está mudando para a direita, é qualquer coisa que qualquer coisa que wasn't-- não era originalmente parte da coisa 0? 

CAMILLE REKHSON: Sim, você faria basta adicionar 0 de sobre no original. Sim. 

AUDIÊNCIA: Então o que é que 100 deslocada para a direita três vezes? CAMILLE REKHSON: 100 deslocado para a direita, de modo que levaria todo o 1 e 0 e apenas transferi-los à direita, como muitas vezes como -lhe que se desloque para a direita. 

AUDIÊNCIA: [inaudível]? CAMILLE REKHSON: Bem, são 100-- Você está falando sobre 100 em binário, ou 100 em decimal? AUDIÊNCIA: Me desculpe, 100 em binário. 

CAMILLE REKHSON: 100 em binário, se você transferi-lo para o direita-- se deslocará para a direita uma vez, se tornaria 10. Se você transferi-lo para a direita duas vezes, ele se tornaria 001. E então se você transferi-lo novamente, você tipo de perder o pouco. Sim, isso é apenas 0. Qualquer outra dúvida sobre isso? Sim. 

AUDIÊNCIA: Então torna-se 000. 

CAMILLE REKHSON: Sim. OK, então vamos passar por um pouco de matemática ASCII. Então personagens podem essencialmente ser tratados como números inteiros com base em seus valores ASCII. Então, se nós nos sentamos int A é igual a 65, int B é igual a A + 1, int caractere C é igual a D menos 1, e caractere D é igual a 68, o que iria imprimir na parte inferior? 

Então, nós estamos imprimindo these-- abençoe vocę-- estamos imprimir todos estes como PERSONAGENS com base na porcentagem C. Então, nós estamos basicamente imprimindo o valor do caractere de todos os quatro destas variáveis. Como uma dica, 65 é o valor ASCII do capital A. Talvez que ajudou. O que? 

AUDIÊNCIA: ABCD. 

CAMILLE REKHSON: Sim, então isto deve imprimir para fora exatamente ABCD porque nós definir int A igual ao valor de A. ASCII Então, se nós imprimimos que como um caráter, nós apenas obter capital de A, A mais 1 seria um capital B em ASCII. D menos 1 seria um C maiúsculo em ASCII. E 68 é o valor ASCII de D. Questões sobre ASCII? Sim. 

AUDIÊNCIA: Então, o entre aspas A, isso muda A do ASCII? 

CAMILLE REKHSON: É isso uses-- aspas simples ao redor do count-- A faz dele um personagem. E se você está lidando com em que o número form-- Assim, quando, como neste caso, é sendo tratado como um int-- em seguida, ele lidaria com seu valor ASCII. Sim. 

AUDIÊNCIA: Você recomenda que temos uma tabela de referência ASCII? 

CAMILLE REKHSON: Eu não penso-- 

AUDIÊNCIA: Ou será que ele só estar lidando com isso? 

CAMILLE REKHSON: Eu acho que nós poderia fazê-lo com as coisas fáceis. Eu não acho que seria hurt para anotar talvez o que maiúsculo e minúsculo A são, apenas o que essas faixas estão começando com. Mas eu não acho que você precisa tomar todos o espaço para colocar uma mesa ASCII todo. Sim. 

AUDIÊNCIA: Qual é a diferença entre dizer int A e C Char, como você faz no topo? 

CAMILLE REKHSON: Então é só como isso é armazenado na memória. Mas você pode tratá-lo de qualquer maneira. Como vemos aqui, nós fazemos impressão o A como um personagem. AUDIÊNCIA: Então, isso é o mesmo que A? CAMILLE REKHSON: Yeah. Alguma outra pergunta? 

AUDIÊNCIA: Então, por cento C está dizendo imprimir um char? 

CAMILLE REKHSON: Sim. 

AUDIÊNCIA: Então mesmo se um só tem foi definido como um número inteiro, se tentar imprimir um carvão animal como um 65, ele would-- CAMILLE REKHSON: Ele iria para basicamente vai para a tabela ASCII e obtém quaisquer caracteres no gráfico ASCII para que 65. 

AUDIÊNCIA: Obrigado. 

CAMILLE REKHSON: Yeah. Sim? 

AUDIÊNCIA: Então se você fez% I,% I, % I,% I, faria apenas print-- CAMILLE REKHSON: Sim, se você fez tudo de 4% do que eu, ele iria imprimir o ASCII valores de todos os quatro destes. Alguma outra pergunta? OK, então âmbito, basicamente este ajuda-nos a determinar onde existe uma variável no seu programa. Então, nós já conversamos sobre dois diferentes tipos de escopo, globais e locais. 

Se uma variável é escopo global, o isso significa que todo o seu programa tem acesso a essa variável. E se você globalmente âmbito de uma variável, você declará-la antes de sua função principal. Então, ele é feito para a direita fora do bastão. E, em seguida, todo o seu programa pode acessá-lo. 

Se ele está com escopo apenas localmente, que variável confinado a uma região específica. Então, se você declarar dentro de um loop for, só isso for loop pode acessá-lo. Ou se você declarar dentro uma função específica, única que a função pode acessá-lo. Perguntas sobre escopo. 

OK, então a função de prototipagem. Basicamente porque C, quando ele compila, lê cima para baixo. Se você declarar uma função tarde em seu código, o compilador não sabe que esta função existe. Então, o que nós usamos são protótipos, que basicamente dizer ao compilador, esta função existir, vá olhar por isso mais tarde no código. Assim, a maneira que você faz um protótipo de função é exatamente como você começar off escrevendo uma função. Você dá o tipo de retorno, o nome da função, e então quaisquer argumentos que essa função tem. 

Então, olhar para um exemplo rápido, neste maiúsculas e nossa função que estamos usando aqui é basicamente uma função de cubo. Assim, tendo em um inteiro e retornando o cubo do referido número inteiro. Então porque temos escrito que função abaixo a função principal, e nós queremos usar o saída de isso-- ou nós quer essa função em nossa função principal, nós colocamos a caminho protótipo na parte superior do nosso programa. E então, quando nós chamamos -lo em nossa função principal, o compilador sabe que esta função está escrito mais tarde, e vai procurá-lo, e vai usá-lo corretamente. Perguntas sobre prototipagem? Sim. 

AUDIÊNCIA: Então, qual é o ponto? Eu não entendo o ponto de prototipagem. Porque não basta tê-lo lá em baixo? 

CAMILLE REKHSON: Bem, se é aqui, então quando você começa a linha de cubo x em sua função principal, o compilador não terá idéia de que a função cubo realmente existe. 

AUDIÊNCIA: Não foi possível você basta colocá-lo na frente? 

CAMILLE REKHSON: É melhor prática de codificação para colocá-lo sob a sua função principal. Então é por isso que faríamos fazer a prototipagem. Só porque, se você tinha um monte de funções, que seria muito confuso para ler através de todas essas funções antes de chegar à carne do seu programa. Sim, e você teve uma q-- 

AUDIÊNCIA: Então, está declarando a variável-se na parte superior para que você possa acessá-lo, torná-lo uma variável global? É que semelhante a este onde está declarando- lá em cima, para que ele saiba que ele vai acessá-lo mais tarde e você pode usá-lo? 

CAMILLE REKHSON: Yeah. Sim. 

AUDIÊNCIA: Deve as-- qualquer adicional funções que você criar a chave fora desta coisa, ou-- 

CAMILLE REKHSON: Sim, se você estiver criando outros principais funções no em si é o function-- por isso, se você está criando outras funções, eles deveriam estar fora. Sim? 

AUDIÊNCIA: O que há por cento D? CAMILLE REKHSON: Percentagem D é a mesma coisa como percentagem I. Refere-se a um número inteiro. Sim. 

AUDIÊNCIA: Então, o que é obra principal int? Qual era esse vazio? CAMILLE REKHSON: Vácuo diz que leva em nenhum argumento. AUDIÊNCIA: [inaudível]. CAMILLE REKHSON: Você pode falar um pouco mais alto, desculpe? AUDIÊNCIA: É, desculpe, por que você colocar para anular a primeira, e, em seguida, int entrada para o segundo? CAMILLE REKHSON: Oh, para os dois diferente-- para a função principal versus a função de cubo? Então, na função principal, usamos vazio porque não há há parâmetros que estão sendo tomadas. Considerando que, no cubo função, temos uma entrada. É por isso que se diz int, entrada, porque há argumentos de que nós somos levando-se em executar nossa função. Sim. Há umas perguntas? 

OK, e então rapidamente ponto flutuante imprecisão. Portanto, temos um número infinito de números reais. Mas há apenas uma está número finito de bits que podemos usar para exibir os números, e representá-los. Assim então vamos acabar com certa imprecisão. E os números não vão sempre que ser muito exactamente você acha que eles são quando você está lidar com ponto flutuante. Este é apenas algo de bom de saber. Perguntas sobre este assunto? Sim. 

AUDIÊNCIA: É este referindo- à idéia de bit de overflow que estava na palestra? Foi algo que separar? 

CAMILLE REKHSON: Eles são completamente separados, sim. OK ótimo. Pulak GOYAL: Oi, todo mundo. Meu nome é Pulak, e eu vou estar passando por cima ponteiros. OK, então vamos primeiro think memória sobre o que parece. Então, como você pode ver aqui, tomar memória e que dividi-lo em um monte de blocos. E nós fazer referência a cada bloquear por um endereço, certo? E alguém se lembra que tipo de notação que usamos para designar um endereço? 

AUDIÊNCIA: hexadecimal, 0 X. 

Pulak GOYAL: hexadecimal, certo? Assim, o 0 X significa que estamos falando sobre hexadecimal. OK, então como podemos criar ponteiros? Então, tomamos o tipo, nós colocar ele-- adicionar uma estrela a ele, e, depois, adicionar o nome da variável. Assim, os exemplos que temos visto são int estrela x, char estrela y, e z flutuar começar. Portanto, quando digo int estrela x, alguém pode me dizer o que eu estou falando sobre o tipo de lá? 

AUDIÊNCIA: A localização do disco. 

Pulak GOYAL: Desculpe, mas o quê? Pode repetir isso? AUDIÊNCIA: A localização do disco. 

Pulak GOYAL: Então actually-- então o que Eu quis dizer, é quando temos int x estrela, nós estamos dizendo é a criação de um ponteiro, e podem armazenar o endereço de um variável que é um int, certo? Assim, com o caractere y estrela, estamos criando um ponteiro que pode armazenar o endereço de uma variável que é um char. De modo que faz sentido para todos? OK legal 

OK, então com ponteiros, existem duas operações importantes que podemos fazer. Há referenciamento, e lá está dereferencing. Sim? 

AUDIÊNCIA: Você poderia ir um pouco mais lento? 

Pulak GOYAL: Claro. Sim, assim-- Sim, fazer perguntas como eu ir junto, se você-- se algo não estiver claro. Portanto, temos referenciamento e dereferencing. Então, quando você deseja obter o endereço de uma variável, em seguida, use o E comercial. Então, digamos que eu declarei int x em algum lugar. E eu quero obter o endereço de que e passá-lo, eu faria e comercial x. E quando você quiser tirar o valor associado com um ponteiro, você usa o dereference operador, que é uma estrela. 

Então, digamos que eu tinha int x estrela, e Eu tinha-o apontando para algo. Se eu quiser obter o valor do que é apontando para, gostaria apenas de fazer estrela x. Isso está limpo? Qualquer dúvida sobre isso? Sim. 

AUDIÊNCIA: Então, geralmente, você não será capaz de fazer em x e estrela X X com o mesmo. Isso está correto? Porque, se x é um variável, então você tem fazer em x para obter esse é um ponteiro. Mas, se x é um ponteiro, então você precisa para fazer estrela x para obter a variável. 

Pulak GOYAL: Sim, assim que o pergunta foi sobre quando usamos um star-- quando você usaria a estrela, e quando usamos o ampersand, e podemos usá-lo com o mesmo tipo de variável? Por isso, normalmente se você tiver, por exemplo, um int x, você iria ser maioritariamente usando o E comercial para obter o endereço desse. Porque não faz sentido de deferência em x. Considerando que, se tivéssemos int x estrela, você estaria usando a operação de remoção de referência porque não faria sentido para usar em x, nesse caso. Será que isso faz sentido? 

AUDIÊNCIA: Então você não pode e, em seguida, e um ponteiro? Pulak GOYAL: Então você tecnicamente, na verdade, pode fazer o comercial de um ponteiro. Mas isso é fora do âmbito desta classe. Para o purpose-- para suas caras ' fins, sempre que você tem ponteiros, Você quer usar o operador dereference para obter o valor associado a isso. E quando você tem regulares variáveis, como um int x, você quiser usar o E comercial operador de obter o endereço desse. ok? 

OK, então vamos olhar para ponteiros eo que acontece sob o capô. Então, a primeira coisa que eu fiz aqui é o declarado int x é igual a 5. O endereço dessa variável é 0x04, e o valor é de 5. Então, vamos ver o que acontece com a próxima linha. Então, agora nós declaramos um ponteiro. Seu endereço é 0x08, e sua valor é o endereço de x. Isso faz sentido para todos? Qualquer dúvida sobre isso? 

OK, e agora vamos ver o que acontece com a próxima linha. Assim, com esta próxima linha, temos o endereço de cópia sendo 0x10, e seu valor é 5. Portanto, a razão temos cinco é dissemos, Dereference ponteiro, que declarou uma estrela int. E assim went-- quando dereference-lo, ele disse, OK, o que está no 0x04 slot. E foi para isso. E o que x é um x0-- 0x04, e o valor é de 5. Isso faz sentido? Sim? 

AUDIÊNCIA: Porque é que o endereço da cópia apenas 4 bytes acima do ponteiro X? 

Pulak GOYAL: Sim, isso é um erro on-- 

CAMILLE REKHSON: Então, sim, lembre- isto é escrito em hexadecimal. Pulak GOYAL: Ah, sim. CAMILLE REKHSON: Então, isso é realmente 8 e, em seguida, 16 porque nós dissemos que, o ponteiro, lembre-se, em nosso IDE vai ser 8 bytes de comprimento. Pulak GOYAL: Yeah. Então, só para ficar claro, ponteiros são 8 bytes de comprimento. Um int é de 4 bytes. Assim, a razão pela qual o saltou de 0x04 para 0x08 é porque tivemos que fazer um salto de 8 bytes. E, em seguida, uma vez que for-- cópia é apenas um int, é 4 bytes, que é metade de 8 bytes. Então, nós apenas saltar para 0x10, que é dois de distância de 0x08. Alguma outra pergunta? OK, let's-- sim? 

AUDIÊNCIA: Por que não é o valor de int cópia as-- apenas por que é 5, em vez de 0x04? 

Pulak GOYAL: OK, por que é 5? OK, então quando as-- então vamos primeiro pensar sobre isso em termos de tipos. Então, eu estou dizendo int cópia é igual a estrela ponteiro. Então, qual é o tipo de ponteiro? É uma estrela int. E quando eu dereference que, o tipo torna-se um int. Então, o que nós esperamos para armazenar aqui é realmente um int. Isso faz sentido? AUDIÊNCIA: Claro, pouco. Pulak GOYAL: Então geralmente quando você pensar em termos de tipos, ele ajuda você a entender o que é o Tipo do valor que deve ir para lá. Assim, você pode geralmente descarta muitos destes erros comuns por pensar em termos de tipos. Deixe-me passar por um pouco mais de slides. E nós podemos obter perguntas em a extremidade da secção de ponteiro. OK, por isso temos um programa de buggy aqui. E assim é que alguém pode dizer anyone-- me o que está errado com este programa? Certo, então o que nós somos esperando para fazer aqui é-- o que nós queremos fazer é tomar a variável int x e vire ele-- torná-lo igual a 5 em vez de 3 e, em seguida, imprimir isso. Mas isso não está acontecendo. Alguém pode me dizer por quê? Sim? 

AUDIÊNCIA: Quando a função to_five leva x como é argumento, não é preciso x em si, mas em vez cria uma cópia, um, do mesmo. E forma em que as operações. Mas por causa disso, você não mudar o valor real de x. Desde que você é [inaudível]. 

Pulak GOYAL: Direito, direita, de modo que quando chamamos o to_five função, o que nós estamos fazendo está pensando, dá-me uma cópia do valor para essa função. Essa função, então, vai e fazer algumas manipulações. Mas uma vez que ele retorna, é agora fora do escopo da função principal aqui. E assim X ainda é, na verdade, igual a 3, e nós imprimir 3. OK, então vamos ver como isso acontece. 

OK, então não há nada declarou. Então, aqui, x é igual a 3. E agora ele é-- na posição dois, um ainda não está no escopo. E agora vamos para posicionar três, onde uma empresa assume o valor de 3. Às quatro, nós agora mudar um a 5. Mas agora, quando nós saltamos de volta para cinco, que é a declaração de impressão, um está agora fora de escopo. E X ainda é igual a 3. Será que isto faz sentido para todos? OK, então agora vamos falar sobre como podemos usar ponteiros para corrigir isso. Alguém tem alguma idéia de como nós poderia corrigir isso usando ponteiros? 

AUDIÊNCIA: Você pega em uma estrela int em vez de um int para to_five. 

Pulak GOYAL: Desculpe, você poderia falar mais alto? 

AUDIÊNCIA: Você pega em uma estrela int em vez de um int para to_five. Pulak GOYAL: OK, sim. Então, vamos pass-- em vez de passar apenas o valor, vamos passá-lo por referência. Esta nova função, certo? E assim, passando o endereço, nós pode fazer manipulações no endereço. E por isso estamos realmente, Na verdade, mudando x. Então vamos ver como isso funciona. 

OK, então, neste exemplo, fixa-lo. Nós mudamos a nossa assinatura to_five de tomar em um int estrelar em vez de apenas um int aqui. Então nós dereference este e atribuir um 5 a ele. E agora essa vontade, de fato, imprima 5. Então, vamos ver como as etapas trabalhar aqui. 

Assim, com o primeiro passo, não há nada declarou ainda. Assim, aqui, com o segundo passo, nós dissemos x é igual a 3, mas um ainda está fora do escopo. Agora na terceira linha, temos X é ainda igual a três. E agora, nós passamos em-- o que é armazenado num é agora o endereço de x. Isso faz sentido para todos, como nós temos isso? Certo, nós temos o que é como amper-- passamos por um e comercial x para a função to_five. E, em seguida, para a linha seguinte, o que nós fazemos, é que dereference um. 

E dereferenciando um, somos capazes para alterar o valor de x a partir de 3 a 5. Como x mora naquele endereço 0x12. E, em seguida, finalmente, quando nós voltar ao principal, embora este um agora está fora de âmbito, temos, de fato, mudou x. E é 5. Qualquer dúvida sobre isso? Sim? 

AUDIÊNCIA: Você pode me dizer o que o comercial era x? Eu pensei que era como E e comercial. 

Pulak GOYAL: Sim, por isso usamos o mesmo símbolo para muitas coisas diferentes. Então, aqui, quando você have-- em Neste caso, quando você tem, Eu adivinhar portanto, neste caso, quando você está lidando com ponteiros, quando você coloca o ampersand na frente de um int, uma variável int, ou um char, ou um fluxo, o que você está dizendo é, dá-me o endereço deste. Mas o que você estava pensando, quando outra pessoa você usaria comercial é, digamos, em uma instrução if. Você tem um verdadeiro, e algumas variáveis que avaliam a alguns booleano, e algumas outras variáveis que validar algumas booleana e você deseja obter o e de que. Em seguida, você usaria o comercial. COLUNA 1: Sim, por isso apenas hoje, nós temos Conversamos cerca de três diferentes usos de comercial. Temos dois ampersands, que é Pulak que acaba de descrever. Temos um e comercial, que o que é descrito Camille anteriormente, que é um e comercial. E isso é para bit a bit AND. E note que tanto o e- condicional ou, desculpe, a lógica AND bit a bit eo E, aqueles que têm dois números, certo? Foi algo ampersand algo comercial, algo algo comercial. Aqui, quando só temos comercial algo, que está dereferencing. 

Pulak GOYAL: Sim, grande questão. Sim. 

AUDIÊNCIA: Por que em linha 5a e estrelar um tornado N / A? Por que eles não apenas uma espécie de reter o mesmos valores a partir da linha anterior? 

Pulak GOYAL: Porque nós saimos a função. E então o que happens-- por isso agora estamos what-- fora do escopo dessa função, na verdade, o que acontece é aqueles são removidos da memória. Sim. 

AUDIÊNCIA: Entre 3 ou 4 estrelas a é igual a 5. Pulak GOYAL: Sim. AUDIÊNCIA: O que isso denota exatamente? Pulak GOYAL: O que significa isso? AUDIÊNCIA: É. Pulak GOYAL: Então, a pergunta era, o que é isso-- que você está fazendo on-line quando dizemos, estrela é igual a 5? Então lembre-se a estrela do operador de remoção de referência. Assim, quando um, neste caso, é um ponteiro. É uma estrela int. Então, quando nós dereference um por usando a estrela, o que estamos dizendo é, ir para tudo o que está armazenado no endereço, armazenada em um-- tão take-- modo a, agora, tem algum endereço armazenado na mesma. Vá para onde esse endereço aponta para, e agora mudar o que quer que seja para cinco. Sim. 

AUDIÊNCIA: Você pode dizer em termos mais simples? Alterar o endereço de um a cinco. 

Pulak GOYAL: Nós não somos mudança do endereço de um para cinco. A tem algum endereço nela, que é a endereço da variável de interesse. E assim o que estamos dizendo quando dereference é, agora queremos change-- agora estamos referenciando o interesse da variável diretamente. Será que isso faz sentido? 

COLUNA 1: Outra maneira de pensar de que é assim uma vai-- é um endereço. A estrela diz que ir para tratar e olhar para o seu valor. E agora definir o valor para 5. Por isso, diz, ir para o endereço de x, que vai ser o que está armazenado em um, e alterá-lo para 5. Pulak GOYAL: Sim? AUDIÊNCIA: Então, a posição é onde o ponteiro está indo, o endereço. Mas o valor é atribuído um valor com base no endereço. Pulak GOYAL: Yeah. Quaisquer outras perguntas sobre este? AUDIÊNCIA: Eu tenho uma pergunta. Pulak GOYAL: Sim, desculpe. AUDIÊNCIA: Então, quando você store-- assim se você está dizendo [inaudível] a. Pulak GOYAL: Sim. AUDIÊNCIA: Você tem que armazenar o x com um e comercial? Porque você não pode apenas dizer que x antes de seu int [inaudível]? Pulak GOYAL: assim-- AUDIÊNCIA: [inaudível]. Pulak GOYAL: Então é o seu question-- oh. Então a pergunta é, por que não nós-- ao to_five função, porque não podemos nós basta passar um x, certo? 

AUDIÊNCIA: Certo. 

Pulak GOYAL: OK, sim, por isso este novo vai voltar para nossa discussão sobre os tipos. Assim, a função é agora to_five esperando um tipo de int estrela. Então, qual é o tipo de x? X é apenas um int. Mas o que essa função espera é uma estrela int. Por isso, espera que uma variável tem um endereço armazenado na mesma. Então é assim que colocar o vocę-- E comercial, e por isso é como nós passamos no endereço, que é agora-- e que interpreta que como uma estrela int, sim. Ótima pergunta. Qualquer outra dúvida sobre isso? OK legal. 

OK, então agora vamos falar sobre a aritmética de ponteiro. Então, aqui, somando e subtraindo i ajusta o ponteiro por i vezes o tamanho da o tipo de bytes de ponteiro. Então, vamos olhar como que parece. Então, aqui, temos declarado int x é igual a 5. E agora nós estamos indo para declarar um ponteiro y, e passar o endereço de x lá. Portanto, temos que. Então X é armazenado a 0x04. Então agora y é igual a isso. E alguém pode me dizer o que pensam vai acontecer quando nós fazemos y mais é igual a 1? Sim? 

AUDIÊNCIA: Será que vai mudar para 0 vezes 0 8? 

Pulak GOYAL: Size, e type-- 

AUDIÊNCIA: Você está se movendo o endereço. Pulak GOYAL: Sim, sim foi--. Tão certo. Então, ele vai mudar para 0x08. E porque-- para que você usaria este fórmula, 1 vezes o tamanho do ponteiro e os ponteiros estão de size-- 

[ESTUDANTES MURMUR] 

Pulak GOYAL: Certo. 

[ESTUDANTES MURMUR] 

COLUNA 1: Então o tipo que o ponteiro aponta a-- 

Pulak GOYAL: É, sim, sim, isso é 4 bytes. 

COLUNA 1: Então ints são 4 bytes. 

Pulak Goyal: Então se tivéssemos um-- vamos dizer que declararam, eu acho, um char. O que isso-- então vamos dizer que nós x tem de char iguais a um ou algo assim. E nós tivemos o endereço do que no 0x04, o que seria y mais um é igual a fazer agora? Desculpe, o quê? 

AUDIÊNCIA: 0x05. Pulak GOYAL: 0x05, certo. Será que todo mundo vê isso? OK, e agora vamos dizer que é um float. O que aconteceria? Alguém? Então flutuadores são quantos bytes? 

AUDIÊNCIA: 4 bytes. 

Pulak GOYAL: Certo. Por isso, seria a mesma coisa que esta. Frio. OK, e agora vamos falar sobre ponteiros e matrizes. Assim que viu isto no dois conjuntos de p anteriores, onde podemos treat-- matrizes assim e ponteiros não são a mesma coisa. Mas podemos tratar matrizes como ponteiros. Então, aqui, temos essa matriz aqui, que tem três slots. No primeiro, slot-- ter um, dois e três. 

Então, se nós-- para que possamos atribuir que dizendo, temos array, dereference isso. E então, quando nós Dereference que, o que estamos realmente fazendo é referente ao mesmo slot. Então matriz estrela é igual a 1. Nós poderia- como poderia nós escrevemos o que é que-- uma maneira alternativa poderíamos escrever isso? 

AUDIÊNCIA: Array 0 igual a 1. 

Pulak GOYAL: Exatamente, que todo mundo vê isso? Assim, mesmo com aqui. Então, quando temos matriz mais 1, nós fazer-- tão even-- lembre-se que com a aritmética acabamos de falar, quando o fazemos, mais 1 ou mova-o por 4 bytes, certo. Será que todo mundo vê isso? E esse lado, quando nós Dereference que, podemos definir que a 2. E é assim que definimos o próximo bloco a 2. E assim uma forma alternativa de escrever que também seria suporte de matriz 0 suporte é igual a 1. 

AUDIÊNCIA: Você precisa dos parênteses? 

Pulak GOYAL: Sim, porque você é dereferencing toda a quantidade matriz mais um. OK, e mesma coisa para matriz mais dois. Qualquer dúvida sobre isso? Sim. AUDIÊNCIA: Então matriz é automaticamente ajustado a 0? 

Pulak GOYAL: Array é-- desculpe, o quê? 

AUDIÊNCIA: Array é 0. O endereço da matriz é apenas 0. 

Pulak GOYAL: Então, a pergunta era: é o endereço da matriz de apenas 0? Então, não, matriz tem alguns endereços. Então, quando nós dereference-lo, that's-- para que você possa pensar about-- literalmente, como um ponteiro que aponta para o início de uma matriz. Assim que tenha algum endereço. Nós não sabemos o que é. Mas quando nós dereference, sabemos esse é o início da matriz. E assim, quando nos movemos por 1, nós estamos apenas movendo em relação a onde o endereço era. Alguma outra pergunta? Sim? 

AUDIÊNCIA: Então, se você faz suporte de matriz mais 1-- Pulak GOYAL: Desculpe, I-- você poderia falar mais alto? AUDIÊNCIA: É, se você fizer suporte array [inaudível]. Assim, pois, se você colocar o pointer-- Pulak GOYAL: Desculpe, eu não posso ouvi-lo. Você pode dizê-lo mais uma vez? 

AUDIÊNCIA: Você está OK. 

Pulak GOYAL: OK, desculpe. OK legal. Any-- sim. Então, quando você vai em suporte de matriz 3-- 

Pulak GOYAL: Yeah. 

AUDIÊNCIA: --isn't há-- que não seja quatro pontos como 0, 1, 2, e 3? Por que não é int matriz 2? 

Pulak GOYAL: Não, por isso só a convenção de C é-- quando declarar a matriz, nós-- o número colocamos lá é quantos slots que queremos. Mas os índices da matriz forem realmente matriz 0, array 1, 2 e matriz. Então é só a convenção sobre como podemos declarar arrays. Sim, todas as outras perguntas? Sim. AUDIÊNCIA: Então ainda estamos falando sobre ponteiros, certo? Pulak GOYAL: Yeah. AUDIÊNCIA: Você poderia ainda fazer estrelar para matriz 0 é igual a 1? Pulak GOYAL: Não, não, assim-- OK, então a questão era possível você acabou de fazer suporte de matriz estrela zero, e, em seguida, dizer que igual a 1. Então, não, o que estamos dizendo aqui é que nós podemos penso-- podemos tratar matrizes como ponteiros. Portanto, o que estamos have-- provérbio é que temos duas maneiras agora a referência para o mesmo bloco. Então, se você tem doing-- matriz zero, do tipo de que agora é um int. E se você tomar a estrela que, você começa uma coisa inválido. Então o que estamos dizendo aqui é há duas formas alternativas para se referir ao mesmo bloco. Você pode fazer matriz suporte 0 é igual a 1. Ou você pode fazer dereference array, e tem que igual a 0. Portanto, apenas duas maneiras de fazendo a mesma coisa. Sim. 

AUDIÊNCIA: Por que não é tamanho do int 1 para adicionar a-- 

Pulak GOYAL: Tamanho de 1 int. 

AUDIÊNCIA: Porque isso é mover um fora. 

Pulak GOYAL: Porque é isso apenas a forma como funciona C. É apenas o ponteiro do caminho aritmética está definido. Vai levar o ponteiro. E então o que quer que você adicionar para ele, ele vai multiplicar isso por o tamanho de qualquer a loja ponteiro é, sim. Sim. 

AUDIÊNCIA: Então você diz que pode tratar ponteiros e matrizes do mesmo, mas que eles são diferentes. Então, o que os torna diferentes? O que não podemos fazer com um, mas não o outro? 

Pulak GOYAL: Para os fins do presente classe, eu acho it's-- o que fazer você-- 

COLUNA 1: Então, nós-- OK, então, para exemplo, se você alocar memória e você tem um ponteiro para um número inteiro, por exemplo. Se você tentou iniciar fazer aritmética de ponteiro e ir além da quantidade de memória que você alocado, você correm em erros. Sabemos com matrizes, nós dizer antes do tempo, OK, I quer allocate-- esta essencialmente diz, eu quero alocar espaço suficiente para três inteiros. E então agora podemos tratar a memória como se nós temos todos esses três números inteiros. Será que esse tipo de faz sentido? 

Pulak GOYAL: Yeah. Sim. 

AUDIÊNCIA: Então, uma estrela matriz, é que a atribuição de 1 com o índice de 0 a matriz? Pulak GOYAL: Sim. 

AUDIÊNCIA: Então, o que é após a próximas duas linhas em termos de as-- I entender que você está tentando para usar a aritmética de ponteiro aqui, mas, novamente, eu não entendo o ponteiro aritmética é. Assim, a matriz mais um, você é dizendo que você é agora vai querer falar sobre o primeiro índice para a matriz. 

Pulak GOYAL: Certo, e por isso a razão é que funciona matriz, aqui, podemos pensar como uma estrela int. E assim, quando nós ponteiro aritmética nele, lembre-se a fórmula onde tomamos as-- eu acho que quer o endereço atual é, e então, quando somamos 1 a ela, nós, na verdade, 1 multiplicar pelo tamanho a coisa que estamos manipulando. Portanto, neste caso, o tamanho de um int. E, depois, mova- transmitir por muito. 

COLUNA 1: Então fingir você tem estrela b matriz. Pulak GOYAL: OK, sim. COLUNA 1: Com a mão. Vá aqui. Pulak GOYAL: Ou eu posso só-- sim. OK Então aqui--, de modo matriz no começando, é apenas para a direita aqui. Então, quando nós dereference matriz, nós apenas referindo-se ao primeiro bloco aqui. Mas agora quando eu faço matriz mais 1, que é-- que a flecha é agora aqui. Será que isso faz sentido? Certo, porque este bloco é de tamanho int, que é de 4 bytes. E assim, o que estamos fazendo é que estamos mover esse ponteiro por mais de 4 bytes. Sempre que fazemos aritmética nele, ele vai sempre movê-lo por incrementos de 4 bytes. Porque este é como uma estrela int. Isso faz sentido? ESTÁ BEM. 

AUDIÊNCIA: Então as coisas na matriz foram 5 bytes, teremos movê-lo 5 bytes-- 

Pulak GOYAL: Certo, então, se tivéssemos uma estrela char, nós movê-lo por apenas 1 byte. Assim, no caso do carvão animal estrelas, seria apenas mova-o por um. AUDIÊNCIA: Para obter o seguinte você precisa de uma estrela. Pulak GOYAL: Yeah, yeah, faz isso faz sentido? COLUNA 1: Nós podemos conversar mais sobre isso mais tarde. Pulak GOYAL: Sim, sim, com certeza. OK legal. Vamos passar para a próxima seção. COLUNA 1: Oh, OK legal. Sim esse sou eu. Tudo bem, impressionante. OK, legal, então agora estamos em um pouco mais informações gerais sobre a memória. Além disso, eu aprecio o fato de que eles estavam indo muito rapidamente. É um monte de material para obter por meio de uma hora e meia. Mas se existem tópicos que você quer ir mais aprofundada, nós vamos ter o horário de expediente da semana onde você pode conversar com a gente um a um. Ou você poderia apenas vir para cima no acabar e vamos conversar sobre as coisas. E como sempre, sinta- livre para fazer perguntas. Fantástica. Então aqui está a nossa imagem de memória que que vimos nos palestra de um bilhão de vezes. E nós sabemos que esta pilha cresce acima da parte inferior ea pilha cresce para baixo. E qual é a diferença entre as coisas que mantemos na pilha e as coisas que mantemos na pilha? Alguém jogar alguma coisa lá fora. Sim. 

AUDIÊNCIA: É empilhar para as coisas que são apenas variáveis ​​impermanentes que nós somos apenas declarando usando determinadas funções? COLUNA 1: bonito, sim. Então qualquer momento, onde, vamos dizer que estamos em uma função, e nós apenas temos algumas variáveis ​​locais. Aqueles vão acabar na pilha. Se, em vez disso, nós chamamos malloc e realmente alocar memória, que sempre vem do heap. Então, sim legal? 

E para lembrar que qualquer memória que você alocar usando malloc, que vai acabar na pilha. E se você esquecer de -lo livre, o computador de não vai saber que você está feito com ele. Por isso, só vai pendurar lá fora na memória. E você é, essencialmente, vazando que a memória. Você está perdendo isso. Porque você nunca disse ao computador, hey Eu sou feito usando-o, sinta-se livre para usar, colocar outras coisas lá. Frio. Todas as perguntas lá? Sim. 

AUDIÊNCIA: Então, que tipo de memória é pilha? Alimentos não dinâmica, delegado? O que você chama isso? 

COLUNA 1: Claro, para que você possa pense nisso como variáveis ​​locais. Chamadas reais para funções está indo para empilhar. Algo mais? Sim? AUDIÊNCIA: Como você livre a memória que você adicionou ao as-- COLUNA 1: Claro, por isso, quando você alocar memória na pilha, você chama malloc. E assim, em seguida, que lhe dá uma volta ponteiro para algum endereço na memória. Então, dizer que você chamou esse ponteiro, certo? Então, você acabou de dizer ponteiro livre. E que libera a memória. Frio. Outras perguntas? Sim. 

AUDIÊNCIA: O que faz alocada dinamicamente significa? 

COLUNA 1: dinamicamente alocado significa, no âmbito do seu programa. Então, quando você chamar malloc em no meio do seu programa, no início do programa, não há nenhuma memória alocada. E como o computador passo através desse código, ele vai alocar a memória. Então é isso que queremos dizer com dinamicamente. Boa pergunta. Sim? AUDIÊNCIA: Quando você define uma matriz com os colchetes, faz isso ainda [inaudível]? COLUNA 1: Essa é uma boa pergunta. Eu acho que quando você alocar uma matriz, ele realmente coloca na pilha. Eu não sou positivo sobre que, por isso, não citar-me. 

COLUNA 2: Eu acho que sim ele-- coloca-o na pilha. 

COLUNA 1: Coloca-o na pilha. OK, legal, confirmada. Outras perguntas? Sim? 

AUDIÊNCIA: Quando você delegar malloc, não o computador automaticamente alocar memória para suas variáveis? COLUNA 1: Sim, para suas variáveis ​​locais, ele coloca automaticamente memória na pilha. AUDIÊNCIA: Então, qual é o ponto de usar malloc? COLUNA 1: Qual é o ponto de usar malloc? Então, nós vimos um grupo de exemplos, como, por exemplo, usando swap, onde queremos que o âmbito de aplicação a variável a ser algo além de apenas a sua chamada de função. E nós queremos algo que podemos passar ao redor e que podemos acessar de diferentes lugares. É aí que nós queremos colocar memória no heap. Assim que todos esses diferentes funções podem acessá-lo. 

AUDIÊNCIA: Você só pode explicar isso? 

COLUNA 1: Então, uma opção para que o é-- pergunta era: podemos simplesmente allocate-- desculpe, podemos declarar uma variável global, essencialmente. Essa é uma opção. Mas com um monte desses, aqueles tendem a ficar realmente confuso. E nós geralmente pensamos de que o design tão ruim. Sim. Cool, quaisquer outras perguntas? Fantástica. OK, seguindo em frente. Portanto, este é, na verdade, como podemos alocar memória. Nós conversamos sobre isso um pouco. Usamos essa função chamada malloc. E você diga a ele quantos bytes em memória, então quantos bytes na pilha, você quer. E está indo para retornar o endereço, portanto, um ponteiro para, uma parte da memória que está alocado para você. Assim, o tipo vai ser estrela vazio. Vai ser um ponteiro para o que você decidir colocar lá. Toda vez que você chamá- malloc, já dissemos você tem que libertá-lo assim que nós não tem vazamentos de memória. 

Qual é a outra coisa que você absolutamente tem que fazer todos os vez que você chamar malloc? OK, você tem que libertá-la. Qual é a outra coisa? Verifique para null, bonito. Então, sim, é certo lá em cima no tabuleiro. Se você tentar alocar memória e você não tem memória esquerda, o computador vai dizer, Eu não tenho nada para lhe dar. E dá-lhe de volta nulo. Perguntas sobre isso? Sim. 

AUDIÊNCIA: Por que você nunca quer declarar um ponteiro com um tipo específico quando a estrela vazio pode lidar com todos os tipos de ponteiro de qualquer maneira? COLUNA 1: Boa pergunta. Por que dizemos int estrela ao contrário de anular estrela quando a estrela vazio pode lidar com tudo? Então, nós não quero nunca explicitamente converter ponteiros. É apenas uma prática ruim. Mas vamos falar sobre int estrelas assim como uma compreensão de, este é um ponteiro para um inteiro. 

AUDIÊNCIA: OK. 

COLUNA 1: Sim, e permite você manipule os valores nele como números inteiros. 

AUDIÊNCIA: Oh, OK. E estrela vazio não iria deixá-lo fazer isso? 

COLUNA 1: Depende do contexto Sim, então não se preocupe não se preocupe demais sobre o tipo de lá. Só sei que, em geral, malloc retorna um ponteiro para alguma coisa. Boa pergunta. 

AUDIÊNCIA: Por que você multiplicar -lo 10 vezes? [INAUDÍVEL]. 

COLUNA 1: Claro, então eu estava apenas fazendo exemplo aleatório aqui onde Eu queria alocar suficiente espaço para armazenar 10 inteiros. Apenas uma escolha aleatória. Sim. Sim, o que há? 

AUDIÊNCIA: O que você faz Quer dizer, verificando null? Você quer verificar o ponteiro para nulo ou o malloc? COLUNA 1: Sim, exatamente. Portanto, a pergunta era, o que que queremos dizer por cheque por null? Queremos a-- a qualquer momento que chamamos de malloc e nós estamos devolvido um ponteiro, queremos dizer, é ponteiro igual a nulo? Então, literalmente PTR. PTR é igual a nulo. Sim. AUDIÊNCIA: Então, eu era uma espécie de querer saber, se você inicializar o ponteiro para malloc, faz ele aponta para o início do malloc? Porque se é uma array-- COLUNA 1: Isso é uma grande questão. Sim, se você chamar malloc, o ponteiro que ele-- digamos, então aqui nós alocamos 10 bytes de memória. Então, eu sinto muito, o suficiente espaço para 10 inteiros, nós estamos indo para obter o endereço de que a primeira peça de memória. Esta é uma boa pergunta. Sim. 

AUDIÊNCIA: Ao alocar 10 inteiros generalizadas, você poderia realmente usar isso ponteiro como quase como-- como um array de inteiros? COLUNA 1: Sim, você também pode usá-lo como um array de inteiros? Sim, exatamente, isso é o que Pulak apenas mostrei on-- um casal desliza atrás, onde se diz, OK, este é realmente apenas um tipo de-- nós pode pensar nisso como um array de 10 inteiros. Ele só acontece de ser no heap. AUDIÊNCIA: Mas você não podia acesso com notação colchete? COLUNA 1: Você realmente pode acessar com notação colchete, sim. Você pode tratá-los da mesma. Sim. 

AUDIÊNCIA: Por que ponteiro nunca ser nulo? 

COLUNA 1: Por que ponteiro nunca ser nulo? Se você irá utilizar-se todos a memória do heap. Se o seu programa é comer-se, comendo, comendo memória, e não há nada de esquerda, em seguida, malloc vai dizer-- se você diz, Eu quero mais de 100 bytes, ele vai quer dizer, eu não tenho 100 bytes. Aqui é nulo. Isso significa que, eu falhei. Sim. 

AUDIÊNCIA: Nesse caso, nulo não é nada, certo? 

COLUNA 1: Sim, na medida em que caso, nulo é nada. Você não tem endereço. Não há memória. Tudo bem, seguir em frente. OK, vamos falar muito rapidamente cerca de estouro de buffer. Quando pode nos deparamos com estouro de buffer? Vamos dizer que nós temos um-- alocar um bloco de memória, e nós estamos indo para escrever a seqüência de caracteres no. E vamos dizer, OK, eu estou indo para alocar espaço suficiente para seis caracteres. E eu vou pedir o usuário para algumas entradas. E as entradas do usuário, por exemplo, Olá. E isso se encaixa perfeitamente bem porque temos espaço para todos os personagens da Olá, eo caractere de terminação nulo. Muito espaço, não há problema. 

Mas o que se dê a oportunidade para um usuário mal para usar nosso programa, e ele digita não seis caracteres, ou não cinco personagens, mas um milhão. Eles mantêm digitação e digitação, e digitação, o que vai acontecer? Bem, nós só dar o enough-- computador ou desculpe, nós só deu essa seqüência espaço suficiente para 5 caracteres. Então, vamos obter algo como este, onde a pessoa má que é digitando entrada pode substituir o tamanho da memória intermédia, e pode ir realmente passado a quantidade que é originalmente alocado. E então o que você pode fazer, a coisa realmente mal que você pode fazer, é substituir o endereço de retorno. Que basicamente significa você pode tipo de levar controlo do comportamento do programa. Então, em um nível muito alto buffer overflow é quando você alocar uma certa quantidade de memória. E então vocę-- isso porque você é tendo a entrada do usuário ou algo como isso-- você ultrapassar os limites do que você originalmente alocado e começar a bagunçar o seu programa. Sim? 

AUDIÊNCIA: Por que não faria isso apenas retornar uma falha de segmentação? 

COLUNA 1: Por que não faria isso retornar uma falha de segmentação? Poderia. Às vezes, o compilador ou durante um de seu tempo de execução está realmente indo para verificar se. Se certas coisas acontecem, e este é o tipo de nível inferior, então você precisa saber. Mas se você não projetar estes sistemas, adequadamente então você tem a chance de não captura-lo e apenas permitindo que o computador do take-- pessoa mal para controlar seu computador. Sim. 

AUDIÊNCIA: [inaudível]? COLUNA 1: Claro. Oh, quando eu digo buffer, Eu só quero dizer o quantidade de memória que você tenha alocado. Então aqui eu disse, oh, nós temos alocado seis char-- espaço suficiente para seis caracteres. E eu só chamar que meu tampão onde eu poderia escrever informações. Sim. Qualquer outra dúvida sobre isso? Sim. 

AUDIÊNCIA: Como você parar com isso? Como você parar com isso? COLUNA 1: Awesome questão. Como você parar com isso? Como você evitar estouro de buffer? Bem, uma maneira de fazer isso é algo como GetString, onde estamos constantemente a aumentar a quantidade de memória que alocamos se o usuário inserir uma grande quantidade de texto. Outro a coisa é, se você só quer seis personagens, fazer uma verificação rápida. Diga apenas a entrada de seis caracteres. Sim. Então, digamos que você era trabalhando on-- vamos para ir para o material na web um pouco mais tarde no course-- mas vamos dizer que você está trabalhando em uma forma, você faria apenas limitar o quanto poderia entregues. Sim. 

AUDIÊNCIA: puxa GetString memória de pilha, certo? Apenas para clarificar? COLUNA 1: Mais uma vez? AUDIÊNCIA: Será que GetString tomar a memória da pilha? COLUNA 1: Acredito Getm-- get int tem memória do heap porque chama alloc. AUDIÊNCIA: Oh. ESTÁ BEM. COLUNA 1: Sim, malloc e realloc. Outras perguntas? Sim. 

AUDIÊNCIA: Então por definir o tamanho da memória intermédia, você impedir que alguém ser capaz de injetar código que pode deslizar passando a [inaudível]. 

COLUNA 1: Então, por definição o tamanho da memória intermédia, você disse, OK aqui está como quantidade de memória que podemos usar. Se você permitir que o usuário para escrever sobre ele, então você vai ter problemas. Faz sentido. Fantástica. Vamos seguir em frente. Tudo certo. Falando de erros, aqui estão algumas mensagens de erro comuns que poderia ter aparecido enquanto você estava codificação, trabalhando em seus conjuntos de problemas. Boa chance de que um dos estes mostra-se no questionário se nos últimos anos são qualquer indicação. Assim, as respostas são do tipo aqui em cima no tabuleiro. Mas sinta-se livre para gritar um pouco mais. 

Porque pode acontecer uma falha de segmentação? Por que você pode ter uma falha de segmentação quando você estiver executando o seu programa? 

AUDIÊNCIA: [inaudível]. 

COLUNA 1: Boa. Sim, se tentarmos acesso memória que não é dado a nós. Se excluir a referência um ponteiro nulo. Por exemplo, se nós chamamos malloc, e se esqueça de verificar se é nulo, e nós apenas tentar usá-lo, o computador de vai dar-nos uma falha de segmentação. Boa. E sobre implícita declaração de função? O que isso significa? AUDIÊNCIA: Você está tentando usar um função que você não tenha definido. COLUNA 1: Boa. Você está tentando usar uma função que você não tenha definido. Assim que poderia ser uma de duas coisas. Talvez fosse como o exemplo Camille mostrei anteriormente. E você tem uma função principal que chama algo chamado cubo. E vamos dizer que você esqueceu para escrever este protótipo. Você se esqueceu de dizer, hey computador, Eu tenho essa função chamada cube. Você vai vê-lo mais tarde. Vamos dizer que você esqueceu de escrever o protótipo, você pode obter este erro. Outra coisa é, digamos você tentou usar printf, e se esqueceu de incluir a biblioteca padrão, em seguida, ele vai dizer implícita declaração de função. E por último mas não menos importante, identificador não declarado. Sim. 

AUDIÊNCIA: Você tem um escopo problema. Como talvez você está tentando chamar uma variável local que é em um tipo diferente de área. COLUNA 1: Ótimo, então se você tem uma variável que não está no escopo, e você está tentando usá-lo, você vai ficar em apuros. E apenas em termos mais gerais, digamos você tentar usar x, com cada vez dizendo int x é igual a 5, então você está vai ter problemas. Desculpe-me, perguntas sobre isso? Awesome, chugging direita junto. 

OK, recursão, por isso vamos might-- see-- eu perdi meu sch-- oh aqui vamos nós, apenas se certificar de que estamos mais ou menos dentro do cronograma. Tudo bem, legal. OK, recursão, a idéia geral de recursividade, uma função recursiva é uma função que chama a si mesmo. OK, então é isso que eu quer dizer com um conceito de programa pelo qual uma função se chama. Qual seria o que é um some-- boa razão para usar recursão? Quando ele pode ser útil? Ou o que é um programa que realmente presta-se a recursão? 

AUDIÊNCIA: Pesquisa binária. 

COLUNA 1: Pesquisa binária presta-se a recursividade, porque você tem esse problema que você pode quebrar em pedaços menores, e executar continuamente o mesmo algoritmo nele. Isto leva a, em muitos casos, mais código elegante que é mais preciso. Nós apenas são o exemplo de busca binária. Outro exemplo é o merge sort. Às vezes, quando você pensa em um algoritmo, como fatorial, ele só se sente recursiva, certo? Porque nós sabemos que o fatorial de 5 é um fatorial 5 4 vezes. E assim, quando você configura um problema Dessa forma, ele só se sente recursiva. Assim que seria um ótima maneira de escrevê-lo. Perguntas? Sim. 

AUDIÊNCIA: O que é um caso base? 

COLUNA 1: Oh, que é um caso base? Eu disse, não se esqueça para incluir um caso base. Vamos dizer que estávamos escrevendo uma função fatorial, e nós estávamos fazendo fatorial de 5. E nós sabemos que um fatorial de 5 é 5 vezes um fatorial de 4, blah, blah, blah, blah. Como é que vamos saber quando parar? Como sabemos que nós realmente tem um número? Porque se nós continuou chamando fatorial, então nós nunca obter uma resposta, certo? Então, quando é que vamos saber como parar no exemplo fatorial. Qualquer um, sim. 

AUDIÊNCIA: Quando o fatorial 1 é 1. COLUNA 1: Boa. Então, nós sabemos. Podemos tomar como certo que Fatorial 1 é igual a 1. Então, se chegarmos ao ponto em que estamos chamando fatorial em 1, vá em frente e retornar 1. E esse é o seu caso base. Porque nós sabemos que uma vez que atingiram, e nós sempre vai bater isso, vamos never-- nós não só vai manter para sempre. Quaisquer outras perguntas sobre recursão? Sim. 

AUDIÊNCIA: Então, quando você retornar 1, ele apenas automaticamente vai parar o programa, certo? 

COLUNA 1: Sim isso, quando você chamada de retorno 1, se-- digamos, digamos fatorial de 2 chamadas fatorial de 1, fatorial de 1 só vai devolver um. E agora fatorial de 2 vai dizer OK, 2 vezes 1 é 2, e retornar essa resposta. Sim. 

AUDIÊNCIA: Não temos que nos preocupar sobre o escopo de recursão quando você entra em um algoritmo? 

COLUNA 1: Ah, sim. Sim, você tem que se preocupar âmbito no contexto da recorrência. Assim, apenas as variáveis ​​definidas em que prazo da função vão ser útil. Sim boa pergunta. Tudo bem, vamos continuar se movendo. Porque nós temos um monte de Material para passar. Mas como eu disse, sinta-se livre para bater-se o horário de expediente, ou nós após o fato. 

Este é apenas um slide realmente rápido. Nós aprendemos muito sobre busca e uma triagem. Por favor por favor por favor, estas secções estão on-line, Eu acredito em cs50.net/quizzes. Então vá tomar esta tabela e colocá-lo em sua folha de avaliação, porque haverá uma pergunta sobre este assunto. Por favor, não entendi errado. Apenas muito rapidamente, o que significa que este gráfico, é ele fala sobre o grande, o que sabemos para ser o limite superior de um algoritmos tempo de execução. E nós temos omega, que é vai ser o limite inferior de um tempo de execução de algoritmos. ok? 

AUDIÊNCIA: [inaudível]. 

COLUNA 1: Sim, o que é a última coisa? O que é teta? É nós-- se nós estamos indo só para se preocupam nesta classe, no caso onde o nosso limite superior e nossa limite inferior são os mesmos. Sim, essa é a única vez é vai vir para cima nesta classe. OK, eu vou continuar. Se você não tiver tomado a sua imagem, Eu prometo estes serão online. 

OK, impressionante, estruturas. Por que nós queremos estruturas? O que é um motivo útil podemos querer estruturas. Alguém grita alguma coisa. Bem, vamos olhar para o exemplo no tabuleiro. Vamos dizer que estamos lidando com todos esses estudantes. Se nós estamos fazendo um programa para CS50, há como 800 pessoas. Precisamos write-- vamos precisa lidar com um monte de informações sobre os alunos. Seria bom se poderíamos tipo de grupo isto-- toda a informação de que tem a ver com um aluno em particular em um tipo de dados. Mas sabemos que não há dados escreva chamado, estudante, certo? Nós temos um número inteiro, temos um flutuador, temos uma corda, ou uma estrela char, mas não temos, um estudante. 

Então o que podemos fazer é realmente tipo de definir nossa própria estrutura, chamá-lo de estudante, e podemos associar alguns diferentes campos com que struct. Portanto, neste caso, vamos dizer que temos um estudante. E as coisas que nós nos importamos sobre são o número de identificação de estudante e nome do aluno. E agora podemos associar esse ID e este nome com um determinado aluno. Então, vamos ver alguns exemplos. 

OK, então aqui eu digo: OK, vamos dizer que nós queremos fazer uma estudante. Eu o chamo de um estudante. E o seu número de identificação, em Neste caso, podemos acessar apenas fazendo o nome do estudante pontilham o campo que deseja acessar. Então isso vai ser apenas estudante 1 ponto ID, e nós configurá-lo igual a 1. Porque lembre-se, dissemos que ID vai ser um inteiro. E de forma muito semelhante, podemos dizer, este nome do aluno vai ser Davin, por exemplo. Assim, podemos campo basta acessar de uma estrutura utilizando este ponto. Perguntas sobre isso? Sim. 

AUDIÊNCIA: Existe alguma maneira para proteger suas variáveis? Existe alguma maneira de proteger variáveis sejam acessadas externamente? 

COLUNA 1: Há alguma maneira para proteger suas variáveis sejam acessadas externamente? Não no âmbito do CS50. Outras perguntas? Sim. 

AUDIÊNCIA: Qual é typedef struct? O que cada componente significa? COLUNA 1: Ah, o que é typedef struct? O que faz cada componente significar desse cara? 

AUDIÊNCIA: É. 

COLUNA 1: OK, legal. Portanto, este diz, hey computador, I quer criar uma nova estrutura. E eu estou indo para definir uma definição para ele, de modo que eu poderia usá-lo como se fosse um tipo em todo o meu programa. OK, então eu quero definir uma estrutura. E eu estou indo agora para ser capaz de usá-lo como um tipo. E seu nome é estudante. E aqui estão os seus campos. 

AUDIÊNCIA: Então é isso typedef struct [inaudível]? COLUNA 1: Se você quer ser capaz de usar este struct todo o seu programa, e na maioria dos casos em que CS50 fazer, temos de dizer Tipo Def. E que permite utilizar a mesma maneira que nós usamos como int ou float. O computador será sempre sabe o que é. Sim. 

AUDIÊNCIA: Podemos escrever esta no arquivo de cabeçalho? 

COLUNA 1: Oh, desculpe. Será que escrever isso no arquivo de cabeçalho? Você poderia escrever isso no topo de sua programa, no topo do seu programa c. Sim, isso seria o mais lugar razoável para ele. Ali atrás. AUDIÊNCIA: Mesma pergunta, portanto, antes principal? COLUNA 1: Certo, você precisa que isso seja em algum lugar que todos possam acessá-lo. Portanto, antes de principal no seu caso, sim. AUDIÊNCIA: Existe uma diferença entre colocando estudante na parte superior e na parte inferior? COLUNA 1: Ah, há uma diferença entre colocar estudante no topo ou no fundo? Let-- salvar essa pergunta, e quando chegarmos a listas ligadas, vamos ver que, OK? Então agarrar a isso por um segundo. A última coisa que eu quero mencionar aqui, é, em vez de ter uma estrutura, temos um ponteiro para uma estrutura, nós podemos mudar nossa notação para ser um pouco melhor. 

Podemos dizer, vamos dizer que temos um Ponteiro para um estudante em vez de apenas um estudante. Se queremos que o acesso a um campo, em vez de fazendo, bem ir cancelar o ponteiro, e, em seguida, acessar o nome do campo. Esta notação parece um pouco desarrumado com a estrela neste ponto. Totalmente correto, mas uma espécie de maneira mais limpa de fazê-lo, é apenas dizer o nome seta ponteiro. E que realmente combina dereferencing e acessar em um belo símbolo. Perguntas sobre isso? 

AUDIÊNCIA: Basta dizer que mais uma vez. 

COLUNA 1: Dizer que mais uma vez. 

AUDIÊNCIA: Exatamente o que você acabou de dizer. COLUNA 1: Claro, exatamente o que eu disse. Se temos um ponteiro para um estudante em vez do próprio estudante, nós can-- uma maneira que podemos acessar o campo é excluir a referência e, em seguida Nome de acesso. Outra forma, mais agradável nós pode fazê-lo, que é apenas um pouco de açúcar sintático, é apenas para fazer ponteiro nome seta. E que vai combinar o dereferencing eo acesso. Sim, muito legal. Tudo certo. 

Então, vamos falar sobre a outra questão. Vamos pular para nós, que nós estamos indo para usar em listas ligadas em apenas um segundo. Então aqui, você notará que há é o nó palavra tanto na parte inferior, e no topo. Antes, quando estávamos definindo estudante, nós apenas tivemos estudante na parte inferior. Nós não temos estudante no topo. Alguém sabe por que isso pode ser? Qual é a diferença? Sim. AUDIÊNCIA: Então você usa nó é a definição de nó, por isso é uma coisa recursiva? COLUNA 1: Boa. Sim, precisamos de nossos para nós tem ponteiro para outros nodos. Então, uma vez que usamos este tipo antes que seja realmente definida, precisamos colocá-lo no topo apenas para que ele saiba o que é. AUDIÊNCIA: Então nós ainda precisar dele no fundo? COLUNA 1: Sim. AUDIÊNCIA: Então, sempre na parte inferior. COLUNA 1: Sempre na parte inferior. Então, todos vocês vão tê-lo na parte inferior. Alguma outra pergunta? Tudo bem, então vamos realmente falar sobre listas ligadas muito rapidamente. Então listas ligadas é-- nós usá-los em vez de matrizes em alguns casos, porque sabemos que as matrizes são um comprimento fixo, ao passo que listas ligadas podemos crescer e encolher como nós queremos. Portanto, este é um exemplo do que uma lista ligada pode parecer. O que precisamos ver é o cabeça da lista. Então, onde a lista começa. E então ele nó, cada nó subseqüente, é responsável por conhecer onde o próximo nó é. Portanto, neste caso, o nó que armazena 1 é responsável por saber onde 3 é. A pessoa que armazena 3 é responsável por saber em que 9 é. E 9 não tem mais ninguém para apontar para. É o fim da lista, por isso só diz nulo. ok? 

AUDIÊNCIA: Qual é o ponto disso? 

COLUNA 1: Qual é o ponto disso? 

AUDIÊNCIA: É. COLUNA 1: Porque, vamos dizer que temos alguns dados. E nós não sabemos exatamente como quantidade de dados que queremos antes do tempo. Assim, com uma matriz, vamos dizer onde nós quer contar as pessoas na primeira linha. As chances são de que não vai mudar. Nós podemos apenas dizer, OK, I quer uma matriz de tamanho seis. Mas se queremos algo que vai mudar. 

Por exemplo, digamos que eu estava tentando manter o controle dos alunos como eles vêm para o quarto para a sessão de avaliação. Eu não tenho nenhuma idéia de como muitos de vocês as pessoas estão indo para aparecer. Então, eu poderia querer uma estrutura de dados que eu possa expandir e encolher. Porque talvez alguém vai embora, talvez, alguém vai vir. E assim, a qualquer tempo, pode adicionar ou remover os nós. Cool, grande questão. Sim. 

Audiência: Se você pode usar algo como GetString que mantém permitindo-lhe obter mais dados como você precisar dele, por que você precisa disso também? 

COLUNA 1: Por que você utilizar a lista quando ligado você pode usar algo como GetString? Esta é uma boa pergunta. Lembre-se que um dos Get-- as quedas de GetString é que nós não fizemos um muito bom trabalho de libertar a memória, e nós introduzimos um grupo de vazamentos de memória em seu programa? Você poderia dar um estaticamente matriz de tamanho e manter o seu cultivo. Mas você teria que encontrar novos lugares na memória. Seria apenas um monte de sobrecarga. 

Uma das coisas agradáveis ​​sobre ligada listas em oposição a matrizes, é matrizes estão todos na mesma localização na memória. Tem que ser contínua pedaços de memória. Considerando que as listas ligadas, 2 e 3 de Maio ser totalmente em locais diferentes. Como 2 é aqui, e 3 é aqui. E, enquanto eles têm uma ponteiro para um outro, está tudo bem. Sabemos que podemos encontrá-los. Pergunta lá? 

AUDIÊNCIA: GetString é uma função na biblioteca CS50, certo? Não existe em programas reais. 

COLUNA 1: Correto. Certo, isso é outra coisa. Se não existir GetString fora do contexto de CS50. Sim. 

AUDIÊNCIA: O mesmo acontece com o fato de que dois poderiam ser muito longe, faz que o impacto da eficiência do acessar os elementos na lista? COLUNA 1: Isso é uma grande questão. A pergunta era, não é impacto a eficiência de acesso esses diferentes elementos na lista. Na verdade sim. Porque nós sabemos se-- vamos dizer que nós queremos acessar o segundo elemento da matriz, que sabemos podemos apenas fazer uma matriz de suporte, direito. Ele sempre vai ser o mesmo local. Mas, se queremos chegar a esse 3, não podemos apenas dizer, ir buscar que 3. Nós temos que dizer, OK, começam em o início da lista, e agora nós temos realmente para percorrer até que encontrar o número que estamos interessados. 

Portanto, neste caso, dizemos, OK esta é a primeira série. Então, basicamente, que é índice 0. Agora temos que encontrar o segundo número. Isso é índice 1. Assim que realmente está acontecendo a-- apenas acessando, vai levar tempo N. Cool, grande e velho N. Sim. 

AUDIÊNCIA: Quais são cada uma das listas? Eles são cada matrizes, ou o quê? COLUNA 1: Isso é uma grande questão. Quais são cada um dos estruturas que eu tirar? Eles são nós. Assim, cada um desses pequenos estrutura tem duas partes. Tem um número inteiro que possui. Isso é os dados reais que ele está segurando. Esse é o tipo de parte útil. E, isso é o que faz com que seja uma lista encadeada, que tem um apontador para o próximo nó. Impressionante questão. Tudo bem, então vamos olhar muito rapidamente olhar para alguns exemplos do que poderíamos fazer com listas ligadas. 

Então, um exemplo é muito rápido, suponha que queremos fazer uma pesquisa. Que tipo de pesquisa não pode fazemos em listas ligadas? 

AUDIÊNCIA: Binary. 

COLUNA 1: Binário. Por que não podemos usar a pesquisa binária? 

AUDIÊNCIA: [inaudível]. COLUNA 1: Certo, porque com binário busca, tivemos que contar com o fato de que poderíamos simplesmente pular para a matriz, em qualquer ponto. Poderíamos apenas dizer, ir para o elemento do meio. Com aqui, como dissemos um pouco mais cedo, não podemos simplesmente saltar para o elemento do meio. A fim de encontrar qualquer elemento, que, na verdade, tem que caminhar por toda a nossa lista. 

Então, se nós queríamos fazer uma pesquisa, o melhor que podemos fazer é apenas uma busca linear. Começamos na cabeça, nós check-- vamos dizer que nós somos procurando 9-- começamos na cabeça. Nós dizemos, é esta 9? Não. É este 9? Não. É este 9? Sim, nós encontramos. OK, isso é tudo isso. Aqui está um pouco de pseudo-código. Vou deixar isso para você caras a produzir mais em seu próprio país, só porque nós estamos correndo um pouco curto no tempo. 

Vamos falar sobre a inserção. Nós vimos uma demonstração muito legal de isso em palestra em que disse: OK, temos esta lista vinculada onde todo mundo está apontando para um outro, e alguém surge no palco. Como podemos inserir esse pessoa em nossa lista ligada? Bem, uma maneira errada de fazer, o que Eu acho que é o que vimos em primeiro lugar, é quando a pessoa frente automaticamente apontou para a nova pessoa. E então nós meio que abandonado o segunda metade da lista, certo? Porque nós não sabemos onde é na memória anymore. Então, para ter muito cuidado com o ordem na qual inserimos as coisas. 

Então, aqui, vamos dizer que queremos colocar um na frente da nossa lista. Primeiro, temos um ponto na element-- segundo ou o elemento que contém 1. Então, fazemos isso, só assim nós não estamos vai perder o segundo semestre. E agora, podemos ter ponto de cabeça para 1. Então, novamente, este é apenas como super alto nível. Isto é como nós iria inserir um nó. Temos um monte de pseudo-código aqui-- sorry, Eu não sei por que eu sou chamando-o de pseudo-código. É código real. Você pode ir check-out mais tarde. 

Tudo bem, vamos muito quickly-- mais perguntas em listas ligadas antes de eu mover-se em um par de outros dados estruturas em nossos últimos 10 minutos. 

AUDIÊNCIA: Precisamos agora como escrevê-lo em um teste? 

COLUNA 1: Será que precisamos de saber como a-- 

AUDIÊNCIA: Escreva-o em um teste. 

COLUNA 1: Precisamos a-- você deve estar preparado para escrever, inserir, remover e procurar listas ligadas no teste. Isso é algo que nós poderia esperar que você faça. Basta ir sobre ele. Se você tiver quaisquer perguntas sobre a código, atirar o seu TF um e-mail, vir para o horário de expediente. Ainda há muito tempo para estudar, para não se preocupar. Tudo bem, qualquer outro perguntas sobre listas ligadas? Sim. 

AUDIÊNCIA: Então, se você não usar o ponteiro para ir para o outro à direita antes de usar o ponteiro para a da esquerda, que é o equivalente de exclusão tudo correto? COLUNA 1: Yeah. AUDIÊNCIA: [inaudível]. COLUNA 1: Certo, já que não podemos obtê-lo, é realmente ainda pior. Não só porque não sabemos onde ele está, não podemos mais usá-lo, mas nós não somos we've-- libertando a memória mais. Portanto, é apenas rondando e não ser útil, porque não podemos encontrá-lo. Sim, questão legal. 

Tudo bem, vamos falar sobre pilhas. Vimos stacks muito rapidamente. Eles são os primeiros na última estruturas de dados para fora. Então pensamos nas pilhas em Annenberg bandejas de onde nós empilhar as coisas em cima. E se você estiver indo para vir buscar uma bandeja, você é sempre vai levar a um no topo, que é a mais recently-- que é a coisa que mais recentemente colocado no topo da pilha. Assim, você pode tipo de pensar neste tipo de visual quando você está pensando stacks. E então, temos algo estalou fora do topo da pilha. 

Se é-- oh, e as palavras que nós usar quando estamos falando sobre estes dados estruturas é geralmente, se colocar algo na pilha, dizemos que estamos empurrando-o na pilha. E se tomarmos algo fora da pilha, dizemos que estamos estalando para fora da pilha. Se você estiver indo para implementar um stack-- que eu definitivamente recomendamos que você tente out-- você é vai querer acompanhar, digamos que você está usando uma matriz. Eu sei que na palestra falamos sobre o uso de ambas as matrizes ou listas ligadas para implementar uma pilha. Se você estiver usando uma array, você precisa keep-- desculpa me-- precisamos manter o controle de o tamanho e a capacidade. Assim, o número máximo que a nossa pilha pode conter. Perguntas sobre pilhas? 

AUDIÊNCIA: Qual é a diferença entre tamanho e capacidade? COLUNA 1: A diferença entre tamanho e capacidade, pergunta incrível. Então, vamos dizer que estamos utilizando uma matriz, e nós alocar espaço suficiente para 10 inteiros. E começamos a encher isso. E nós levar as coisas por diante, e nós pop coisas fora. Queremos manter o controle do máximo número que pode segurar, que é a capacidade. E queremos manter o controle da número atual que temos, que é o tamanho. Boa pergunta. Qualquer outra coisa em pilhas? Tudo bem, vamos falar cerca de surpresa, as filas. 

Ao contrário de pilhas, que são pela primeira vez na última fora, estes são first in, first out. Portanto, este é como-- pensar de uma linha. Pense em fila no Apple Loja para obter qualquer produto. E a primeira pessoa na linha deve ser a primeira pessoa que ajudou. Então a primeira coisa que é empurrado é esta a primeira coisa que estalou. Frio? Muito similarly-- Oh, as palavras que nós usamos em vez de empurrar e pop-- que eu usei apenas, Estou sorry-- é que dizemos, se estamos colocando algo em a fila, dizemos enfileirado-lo. Se nós estamos tomando algo fora a fila, dizemos que dequeued. Isto. Posso estar pronunciando as errado, mas você começa a idéia. E então, novamente, assim como pilhas, se estamos implementando isso como matriz, temos de manter o controle da tamanho, a capacidade, ea cabeça. O que quero dizer com a cabeça? Por que precisamos para manter faixa da cabeça? 

AUDIÊNCIA: Porque é aí que o início de sua lista é. COLUNA 1: Sim, basicamente a cabeça é onde o início de nossa fila é. Porque nós sabemos, ao contrário de pilhas, which-- Eu estou indo para tentar enfrentar este maneira-- sabemos que ela sempre vai encolher desta forma e crescer dessa maneira. Filas, as pessoas vêm para o final e deixar desde o início, por isso temos de manter o controle de onde o início é. Isso é o que eu quero dizer por que precisamos manter o controle de onde está a cabeça. Frio? Tudo certo. Oito minutos, casal mais tópicos, podemos fazê-lo. 

Tudo mesa à direita, hash. Nós conversamos muito brevemente sobre tabelas de hash. Para o teste, você só precisa compreendê-los a um nível elevado. A idéia básica é que você tem esses dados. E nós queremos acessá-lo no tempo que é mais rápido do que algo como um ligado Lista. Porque nós dissemos, se fôssemos pesquisar através de uma lista ligada, que poderia levar tempo N. Mesmo acessando pode tomar N vez em uma lista vinculada. As tabelas de hash nos dar uma maneira que pudermos acessar mais rapidamente as coisas, e mais procurar rapidamente as coisas, sem tendo as restrições de um array onde se fixaram tamanho. 

Então pensamos em uma estrutura de dados onde, onde vamos colocá-la na estrutura de dados é dependente desta função hash mágico. Portanto, neste caso, o hash mágico função é apenas tomando uma palavra, verificando que a primeira letra é, e em seguida, apenas classificando-o em ordem alfabética. Portanto, essencialmente colocá-los em diferentes baldes. Quando vemos banana, nós dizemos, OK, vamos colocar no balde B. Quando vemos a Apple, vamos colocá-lo na Um balde. Se víssemos damasco, vamos colocar no Um balde. ok? 

Então suponho que eu estava procurando for-- I Não sei, o que é outra fruta? Suponha que eu estava à procura de laranja. Onde devo procurar? No balde O. Sim, há apenas um lugar que a laranja pode ser, OK? Então eu disse anteriormente que acontece se-- bem eu disse anteriormente, vamos dizer que vamos colocar apricot em-- mas eu realmente abordar o fato de que, oh não, se eu fosse para colocar em baga, é vai entrar em conflito com banana. Onde vamos colocá-la se houver já algo em nossa mesa? Bem, nós temos algumas opções. 

Opção número um é linear sondagem, o que significa, basicamente, digamos que eu quero tentar colocar baga, e vejo, oh não, bananas já está lá, Eu apenas dizer OK, deixe- me olhar para o próximo ponto disponível. Então eu desço, eu digo, oh, não há nada no balde D. Eu realmente não posso pensar de todas as frutas que começam com a letra D, então eu só vou colocar baga lá. Durian. OK, portanto, uma vez que há nada lá ainda, Eu poderia muito bem usar apenas esse ponto. Qual é a desvantagem de que? 

AUDIÊNCIA: É fora de ordem. 

COLUNA 1: Desculpe? AUDIÊNCIA: É fora de ordem. 

COLUNA 1: É out-- bem, nós pode acabar com coisas que não são em-- armazenado em baldes na maneira que esperamos que eles sejam. Então, se nós procura para baga, antes dissemos, oh podemos olhar em um balde. Ele só podia estar em um balde. Mas agora, na verdade, poderia ser em todos os baldes, certo? 

OK, aqui está uma outra opção, chaining-- separado que é a idéia de que nós estamos indo usar um pouco mais tarde na P jogo 5. Ao invés de apenas ter um espaço em cada balde, por que não temos cada balde ser um ponteiro para uma lista vinculada? Quando dizemos, OK, há um balde por tudo o que começa com A. E não só vai ser um ligado lista de frutas que começam com A. Então, se temos um novo fruto, digamos nós get-- nós abacate, temos maçã, vamos dizer que temos de damasco, como é que nós colocamos na lista? Bem, nós iríamos para balde 0, e gostaríamos basta inseri-lo em nossa lista gostava, Simples assim. 

Agora eu continuo dizendo balde. Nós poderíamos implementar este em um número de maneiras. Uma maneira típica que esta tipo de imagem sugere, é talvez ter uma matriz de ponteiros para listas ligadas. Essa é uma maneira que pudermos implementar uma tabela hash. AUDIÊNCIA: Você precisa de outro lista porque banana e berry estão fora de ordem? COLUNA 1: Será que você need-- ah, você preciso de outra lista, porque a banana e bagas estão fora de ordem? Neste caso, a nossa função hash, que nos diz onde colocar as coisas não se preocupa com a segunda letra. Ele não se preocupa com alfabetizar, ele só se preocupa com a primeira letra. Questão? 

AUDIÊNCIA: Qual é a definição de que função, eo que ele se parece? COLUNA 1: Ah, bom. OK, por isso, não precisa preocupar muito para este quiz. Então, eu não coloquei nos slides. Nós vamos ser introduzido a ele para definir P 5. Mas, basicamente, ele diz que, dado um novo elemento, onde devo colocá-lo? Ou, digamos que eu estou procurando um elemento, onde poderia estar? Sim, grande questão. 

OK, muito rapidamente, árvores e tentativas. Assim, uma árvore é apenas qualquer tipo de estrutura de dados organizado. E vamos ver um monte de fotos que fará com que este super clara. E uma trie, que vimos em sala de aula, é um tipo muito especial de árvore que funciona essencialmente como uma tabela hash multi-nível. É super legal. Nós vamos vê-lo em apenas um segundo. Tudo bem, então vamos falar sobre árvores em primeiro lugar. Portanto, esta é realmente exemplo típico de uma árvore, onde temos alguma hierarquia. Você vê que um está em o topo, certo? E eu posso dizer porque não há topo claramente uma ordenação porque têm essas setas indo para baixo. De modo que, a coisa no topo, Eu chamo isso de o nó raiz. Então, um é o nó raiz. E as coisas na parte inferior, que nada saindo eles, I dizer que estes são os nós de folha. Assim 8,9 5, 6, 7, OK. E, geralmente, o que terminologia posso dizer é que é uma mãe de três. Então, é a coisa que vem um nível acima dela, e aponta para ele. E 3 é uma criança. É a coisa que 1 aponta para. Questão? 

AUDIÊNCIA: Você pode voltar para o slide anterior, por favor? 

COLUNA 1: Posso voltar para o slide anterior? Certo. Perguntas sobre este assunto? Ou você só queria olhar para ele? AUDIÊNCIA: Eu só não passar por isso. 

COLUNA 1: OK, legal, sim. Estes serão on-line por isso não se preocupar em obter cada palavra. E no interesse da tempo, eu estou indo para ir. É que OK? Fantástica. OK legal. Então vamos falar sobre um kind-- muito específicas por isso temos estes geral estrutura de árvores, que é apenas qualquer coisa que nos permite a espécie de coisas Ranking hierarquicamente. 

Árvores binárias são coisas onde cada nó tem no máximo duas crianças. ok? E eu disse, OK, de modo que parece para se encaixam nessa descrição. Eu disse nó, não uma árvore de busca binária. O que é uma árvore de busca binária? É classificada. Então você sabe que em uma árvore de busca binária, tudo para o tudo tree-- para os nódulos esquerda é menor, e tudo para o nós direita é maior. Então isso não é uma árvore de busca binária. Esta é apenas uma árvore binária. Portanto, temos grande categoria de árvores, categoria ligeiramente menor de árvores binárias, busca por A-- árvores de busca binária. Frio? Tudo certo. 

E agora, mais divertido de tudo, nós temos as nossas tentativas. Vocês viram este quadro numa palestra? Sim, ele deve olhar super familiar. Vejamos como podemos realmente implementar isso. Ou, na verdade, vamos ver, isso mesmo vir acima? Não. Tudo bem, nós nem sequer têm a se preocupar com essas coisas de baixo nível. Teremos tempo de sobra para abordar, em seguida, definir P 5. Mas, por agora, apenas muito alto nível, nós sabemos que este é o que parece. Nós o descrevemos como tipo de uma tabela hash multi-nível where-- o que faz esta loja? Este armazena os nomes de cientistas que podemos realmente procure por apenas uma espécie de sequência do diferentes tabelas de hash para baixo, tudo bem? 

E o objectivo da presente é, em teoria, eles fornecem tempo constante olhar para cima. Então, se eu quiser verificar que, por exemplo, quem é someone-- Mandel que é neste trie, eu poderia muito rapidamente em linear-- Sinto muito, em constante de tempo, descobrir se é ou não é no trie. Mas um golpe, é olhar para o quão grande é este. Nós não estamos mesmo que armazenar quantidade de dados, e é enorme. Então, um grande golpe é que ele usa uma grande quantidade de memória. Sim. 

AUDIÊNCIA: Por que fornecem constante de tempo, exatamente? 

COLUNA 1: Mais uma vez? 

AUDIÊNCIA: Qual é a intuição por que ele fornece constante de tempo? 

COLUNA 1: Excelente pergunta. Por que ele oferece constante de tempo? Então o que podemos fazer é, vamos dizer que nós estamos procurando Mandel. Sabemos que queremos começar no primeiro nível em M. Sabemos que queremos segui-lo para E. Portanto, isso é dar um passo, dois passos, certo? Nós segui-lo para N. nós segui-lo para D. Nós segui-lo para E. nós segui-lo para L. E, em seguida, a próxima coisa que verifique says-- este delta diz Sim, isso é em nossa mesa. Essa é uma palavra. Essa é uma entrada válida no nosso trie. Então você está dizendo, OK, que deu sete passos. Mas se nós adicionamos mais como um zilhão cientistas a esta estrutura de dados, nós não teria que verificar um zilhão de coisas mais. Estamos sempre apenas vai ter que tomar sete etapas, o comprimento da pessoa de nome. 

Então, nós gostamos de pensar de tempo de execução como, suponhamos nós aumentamos o tamanho da nossa estrutura de dados, quanto mais tempo é ele que vai tomar? Neste caso, se somarmos um bando mais cientistas, isso não importa. Ele ainda vai demorar a mesma quantidade de tempo. É tempo constante. Sim. 

AUDIÊNCIA: Como você não conhece para fazer a varredura sobre os outros números? COLUNA 1: Como faço para saber como a-- AUDIÊNCIA: Gosto de como você sabe que você ir reta de M para E e não de M a A? COLUNA 1: Oh, com certeza. Porque eu sabia que eu era procurando a palavra Mandel, e eu só sei que é M-E. Então isso-- sim, vá em frente. AUDIÊNCIA: Será que você não tem de olhar para as outras letras no resto da [inaudível]? 

COLUNA 1: Ah, não tenho olhar para as-- OK, ótimo. Esta é uma grande pergunta. Depende de como implementá-lo. Se nós implementá-lo como apenas como uma série de matrizes onde sabemos que E é sempre na posição 0, Eu não sei, o que quer índice número está. Sim, nós podemos apenas fazer constante tempo, fazer, fazer, fazer, fazer. Frio. Pergunta lá? 

AUDIÊNCIA: É tempo constante a mesma coisa que em tempo real? COLUNA 1: É tempo constante a mesma coisa é em tempo real? Eu não sou realmente certo tempo real é. AUDIÊNCIA: Como aquele tempo literalmente progride segundo por segundo em vez de ser uma variável independente. 

COLUNA 1: Ah, sim, você pode pensar nisso dessa forma. Em outras palavras, não é dependente sobre o tamanho da estrutura de dados. Essa é uma maneira de pensar sobre isso. Alguma outra pergunta? Talvez na primeira vez em história, que terminou no tempo. Se você tiver alguma dúvida, sinta- livre para vir pedir-nos, vá para a seção, fale com o seu TFs, escritório horas são 08:00 e 08:30 às 11:00 na segunda-feira e terça-feira, por isso, é um pouco de tempo diferente, então certifique-se notar que. Sim. 

AUDIÊNCIA: Será que precisamos de saber coisas como argumentos de linha de comando, ls traço, traço o que quer? 

COLUNA 1: Linha de comando argumentos e comandos do Linux, sim, você precisa saber quem. Very-- é como o tipo de nível material nós tratados na secção 0, tanto quanto comandos Linux movimento. 

AUDIÊNCIA: São as horas em Annenberg? COLUNA 1: Horas de escritório, eu não sou inteiramente certo onde eles estão. Mas você pode verificar o website, e ele vai dizer.