DAVID J. MALAN: Tudo bem. Então bem-vindo ao primeiro Postmortem CS50 para um quiz. Nós pensamos em inaugurar esta tradição este ano. E esta será uma oportunidade para percorrer o soluções para o problema. E nós vamos acelerar ou desacelerar base no interesse das pessoas aqui. 

Então, provavelmente você está aqui porque você é interessado em saber como você poderia ter ou deveria ter respondido a algumas destes problemas. Então por que não vamos dar uma olhada nesta seção em primeiro lugar? Então, ficando cordas. Isso lhe deu três versões diferentes de um programa que foi, em última análise, destina-se a obter uma seqüência de um usuário. Se é ou não fez isso era para a esquerda para que você possa determinar. 

E pedimos na Questão 0, supor que a versão 1 é compilado e executado. Por que o programa pode segfault? À primeira vista, todas as sugestões por que motivo? É. 

AUDIÊNCIA: Então, eu lembro de ter visto isso em um exemplo anterior de olhar para o char * s e vendo a digitalização dos s e vendo porque é um ponteiro, como isso afetou o que você digitalizada? É S ou o endereço de s? 

DAVID J. MALAN: OK. Boa. Assim, em última análise, a origem de qualquer problema é, presumivelmente, vai reduzir para essa variável s. E é de fato uma variável. O tipo da variável de dados é char *, o que significa que vai conter o endereço de um personagem. E é aí que reside o insight. Vai conter o endereço de um personagem ou, mais geralmente, a endereço do primeiro caractere todo um bloco de caracteres. 

Mas o problema é que s digitalização, propósito na vida, é dado um endereço e dado um código de formato, como% s, leia uma corda para o pedaço de memória nesse endereço. Mas porque não há nenhum sinal de igual antes que no primeiro ponto e vírgula linha de código, porque na verdade não alocar qualquer memória com malloc, porque isso não aconteceu realmente alocar uma matriz de uma certa dimensão, todos você está fazendo está lendo o usuário do entrada de teclado em alguns completo valor de lixo, que está na s por padrão. Assim, as probabilidades são que você vai se segfault que o endereço não só assim acontecer para ser um valor que você pode, de fato, gravar. Tão ruim não atribuir sua memória lá. 

Então, na questão 1, pedimos, supor que a versão 2 é compilado e executado. Por que este programa pode segfault? Então, este é menos buggy. E há realmente apenas uma maneira óbvia, onde você pode desencadear um segfault aqui. E esta é temática. Toda vez que estamos usando c na memória, o que você poderia fazer para induzir um segfault com a versão 2? 

AUDIÊNCIA: Se você usar essa entrada em uma cadeia que é mais do que 49 caracteres. 

DAVID J. MALAN: Exatamente. Toda vez que você ver algo fixo comprimento quando se trata de uma matriz, o seu radar deve ir fora que este poderia ser problemático se você não está verificando o limites de uma matriz. E esse é o problema aqui. Nós ainda estamos usando scanf. Nós ainda estamos usando% s, o que significa tentar para ler uma string do usuário. Isso vai ser lido em s, o que, neste ponto, é efectivamente o endereço de um bloco de memória ou equivalente. É o nome de um array de caracteres de memória. 

Mas exatamente isso, se você ler uma string isso é mais do que 49 caracteres, 49 porque você precisa de espaço para a barra invertida 0, você vai transbordar que tampão. E você pode ter sorte e ser capaz de escrever um personagem 51, 52, 53. Mas em algum ponto, o SO vai dizer, não. Este definitivamente não é a memória você está autorizado a tocar. E o programa vai segfault. 

Portanto, há, a heurística deve haver qualquer tempo você tem comprimento fixo, você tem para se certificar de que você está verificando o comprimento de tudo o que você está tentando ler nele. 

AUDIÊNCIA: Então para resolver isso, você pode tiveram uma declaração verificando realmente é o maior comprimento ou inferior a? 

DAVID J. MALAN: Absolutamente. Você só tem uma condição que diz que, se o - ou melhor, você não precisa necessariamente saber com antecedência quantos caracteres a usuário vai digitar, porque você tem ovo e da galinha. Não até que você lê-lo com scanf você pode descobrir quanto tempo é. Mas nesse ponto, já é tarde demais, porque você já leu em algum bloco de memória. Então, como um aparte, os evita biblioteca CS50 esta questão por completo, recordação usando fgetc. E ele lê um caractere de cada vez, junto, sabendo-virando dica que você Não pode transbordar um personagem se você ler um de cada vez. 

O problema é com a recordação é getstring que temos que constantemente re-size que pedaço de memória, o que é apenas uma dor. É um monte de linhas de código para fazer isso. Assim, uma outra abordagem seria a na verdade utilizar um primo, de modo dizer, de scanf. Existem variantes de um monte deles funções que realmente verificar o comprimento de quantos caracteres que você pode ler no máximo. E você pode especificar, não leia mais de 50 caracteres. De modo que seria uma outra abordagem, mas menos que acomodam de entradas maiores. 

Então pergunta 2 pergunta, suponha que a versão 3 é compilado e executado. Por que esse programa pode segfault? Então, este é realmente o mesmo responder, apesar parece um pouco amador. Estamos usando malloc, que se sente como estamos nos dando mais opções. E então nós estamos liberando que memória no final. Ainda é apenas 50 bytes de memória. Assim, poderíamos ainda tentar ler em 51, 52, 1000 bytes. Vai para segfault exatamente pelo mesmo motivo. 

Mas há outra razão. O que mais poderia malloc retorno além o endereço de um bloco de memória? Poderia retornar nulo. E porque não estamos verificando que, poderíamos estar fazendo algo estúpido por outra razão, o que é que poderíamos estar dizendo scanf, leia a entrada do usuário a partir do teclado em 0 local, AKA nulo. E que, também, será definitivamente desencadear um segfault. Assim, para o propósito do teste, teríamos ter aceitado um desses como um razão válida. Uma é idêntica. Um deles é um pouco mais sutil. 

Por fim, no que diz respeito ao programa de uso de memória, como é que a versão 2 e versão 3 diferem? Assim, por que vale a pena, vimos um oferta aparentemente infinita de possível respostas a esta. E entre as respostas das pessoas, o que nós éramos esperando, mas aceitamos outras coisas, era uma menção ao fato de que a versão 2 é utilizar a pilha de chamada. Versão 3 está usando o heap. E funcionalmente, isso realmente não fazer tudo o que muita diferença. No final do dia, ainda estamos ficando 50 bytes de memória. 

Mas isso era uma das possíveis respostas que estávamos olhando. Mas você vai ver, como você começa o seu quizzes volta do TF, que fizemos aceitar outras discussões sobre a sua usos diferentes de memória também. Mas pilha e pilha teria sido uma resposta fácil para ir com ele. Alguma pergunta? Eu dar-lhe Rob. 

ROB BOWDEN: Então problema 4. Esta é a única em que você tinha que preencher o número de bytes de todos estes tipos diferentes utilizados. Então a primeira coisa que vemos. Suponha uma arquitetura de 32 bits, como este aparelho CS50. Então, uma das coisas fundamentais sobre Arquiteturas de 32 bits, que nos diz exatamente como um grande ponteiro vai estar na arquitectura. 

Então, imediatamente, sabemos que qualquer ponteiro tipo é de 32-bits ou 4 bytes. Então, olhando para esta tabela, uma nó * é um tipo de ponteiro. Isso vai ser de 4 bytes. Nó struct *, isso é literalmente idêntica à estrela nó. E assim que vai ser de 4 bytes. String, por isso não se parece com um ponteiro ainda, mas o typedef, um string é apenas um char *, que é um tipo de ponteiro. Então, isso vai ser de 4 bytes. 

Então, esses três são os 4 bytes. Agora, nó e aluno são um pouco mais complicado. Então, olhando para nós e aluno, vemos nó como um inteiro e um ponteiro. E estudante é de dois ponteiros no interior do mesmo. Assim, pelo menos para o nosso caso aqui, a forma como que acabamos o cálculo do tamanho da esta estrutura é apenas somar tudo que está dentro da estrutura. 

Então, para nós, temos um número inteiro, que é de 4 bytes. Nós temos um ponteiro, que é de 4 bytes. E assim, um nó está acontecendo para ocupar 8 bytes. E da mesma forma para o aluno, temos um ponteiro que é 4 bytes e outro ponteiro que é 4 bytes. Então isso vai acabar sendo 8 bytes. Então nó e aluno são 8 bytes. E estes três são todos os 4 bytes. Perguntas sobre isso? Sim. 

AUDIÊNCIA: É que era um 64-bit arquitetura, que seria dobrar todos eles? 

ROB BOWDEN: Não seria dobrar todos eles. Assim, a arquitetura de 64 bits, ele, mais uma vez, mudanças que coisa fundamental que a ponteiro é agora 64 bits. É. Assim, um ponteiro é de 8 bytes. Então, esses que foram 4 bytes vão ser 8 bytes. Um estudante, que era dois ponteiros, bem, agora ele vai ser de 8 bytes, 8 bytes. Vai fazer 16 bytes. 

Mas um nó ainda é de 4 bytes. Portanto, este ponteiro vai para ser de 8 bytes. Este é 4 bytes. Assim, um nó está indo só ser de 12 bytes. Quaisquer outras perguntas sobre esse? Então o próximo, estes são os códigos de status HTTP. E você tinha que descrever as circunstâncias nos termos do qual estes puderam ser devolvido a você. um problema que eu ouvi alguns alunos tenho é que eles tentaram fazer o erros de estar no final do cliente. Então, quando nós tentamos fazer o pedido para o servidor, algo correr errado em nosso fim. Mas, geralmente, esses códigos são sendo devolvido pelo servidor. Então, nós queremos descobrir o que está acontecendo certo ou errado no servidor que faz com que essas coisas a serem devolvidos. Então, Por que um servidor retorna código de status 200? Quaisquer pensamentos? 

É. Então, alguma coisa sobre sucesso a solicitação passou. E eles são capazes de retornar tudo o que você pediu. Então, tudo estava bem. E sobre 302 encontrados? É. 

AUDIÊNCIA: O servidor estava à procura para o que você pediu. Mas não conseguiu encontrá-lo. Portanto, há um erro. 

ROB BOWDEN: Então, o servidor foi olhando para o que você queria. Então, só de olhar aqui, 302 encontrados, ele foi capaz de encontrá-lo. 

AUDIÊNCIA: Eu sinto muito. Encontrado significa que eles fizeram encontrá-lo. Desculpe. 

ROB BOWDEN: Então 302 encontrado. O servidor é capaz de encontrar o que você queria. 

AUDIÊNCIA: Mas não é exibi-lo? 

ROB BOWDEN: A diferença entre esta 302 e 200 é que ela sabe o que você quer. Mas não é exatamente onde você queria perguntar. Assim, 302 é um redirecionamento típico. Assim que você solicitou uma página. Ele sabe, oh, eu quero para devolver-lhe isto. Mas isso é em uma URL diferente. Então, hey, você realmente quer isso. 

DAVID J. MALAN: É uma peça que disse que demos vocês um redirecionamento função que usei a função cabeçalho que, por sua vez, impresso local, cólon, e, em seguida, o URL para o qual pretender rejeitar o usuário. Mesmo que você não viu 302 explicitamente lá, que é o que o PHP magicamente inserir como o cabeçalho dizendo exatamente o que Rob disse que não - encontrado. Mas aqui em vez. 

ROB BOWDEN: OK. Assim que sobre 403 proibido? 

AUDIÊNCIA: Eu acho que é que o servidor é, basicamente, dizendo que o cliente não pode acessar a home page. 

ROB BOWDEN: Então, sim. Bem, a resposta típica que foram esperando algo como, os arquivos não são chmodded apropriadamente. Isso provavelmente é em que circunstâncias você viu. Mas há uma razão para que o cliente poderia ser em falta aqui. Na verdade, há um outro código de status - 401. Então, essas são muito semelhantes. 

401 não é autorizado. E 403 é proibido. E assim não autorizada você exclusivamente obter, se você não está logado pol Mas o login pode significar que está autorizado. Mas se você já está conectado e você ainda não tem permissão, em seguida, você também pode obter proibido. Então, se você está logado e não têm permissão, também é proibido algo que você pode começar. 

DAVID J. MALAN: E o mecanismo pelo que estes problemas são normalmente resolvido no servidor é via o comando? Chmod, se é, realmente, uma permissões emitir no arquivo ou diretório. 

ROB BOWDEN: Então 404 não encontrado. É. Portanto, ao contrário 302 onde não era exatamente onde você está pedindo, mas ele sabe o que você quer, isso, ele só tem idéia do que você quer. E você não está solicitando algo válido. 418 Eu sou um bule de chá e, em seguida, 500 servidor interno. Então, por que você pode ter isso? 

Então segfault - Na verdade, eu não sei a classificação padrão para este. Mas se o seu código PHP tinha algo de errado nisso, em teoria, poderia realmente segfault, caso em que, este 500 erro interno do servidor, algo está errado com seu servidor de configuração. Ou há um erro de sintaxe em seu código PHP. Ou algo de ruim está acontecendo. 

DAVID J. MALAN: Fizemos ver segfault entre as respostas de algumas das pessoas. E, tecnicamente, isso poderia acontecer. Mas isso seria um PHP, o programa escrito por outras pessoas, na verdade, segfaulted, que só se essas pessoas asneira e escreveu código buggy seu intérprete faria Próprio PHP segfault. Assim, mesmo que 500 é como um segfault em espírito, é quase sempre a resultado de um problema de arquivo de configuração com o seu servidor web ou, como disse Rob, um erro de sintaxe, como você não fechar uma cotação. Ou você perdeu um ponto e vírgula em algum lugar. 

AUDIÊNCIA: Assim, para o pset Shuttle, I acho que quando eu fiz isso uma vez eu cliquei no navegador, mas nada veio à tona, o que eles chamaram página branca. Mas foi por causa do código. Acho que foi JavaScript, certo? 

ROB BOWDEN: Yeah. 

AUDIÊNCIA: Será que o erro ainda subir? 

ROB BOWDEN: Então você não teria chegado este erro, porque tudo do ponto de vista do servidor web estava completamente bem. Mas você pediu index.html. Você solicitou shuttle.js e service.js. E foi capaz de retornar com sucesso a você todas essas coisas - 200. OK. É só quando o navegador tentou interpretar o código JavaScript que é como, espere, isso não é erro de JavaScript válido. Alguma outra pergunta? Tudo bem. 

DAVID J. MALAN: Então da próxima se era o número 11. E 11 foi o mais assustador para um monte de pessoas. Então, a coisa mais importante a notar aqui era que este era, de fato, sobre uma lista duplamente vinculada. Mas este não era o mesmo que o do ano passado problema lista duplamente ligada, o que não dar-lhe a ressalva de que a lista poderia, de fato, ser indiferenciados. 

Assim, o fato de que a lista foi indiferenciados eo fato de que essa palavra era sublinhado não estava destinado a transmitir que esta é realmente uma simplificação do que de outra forma teria sido um problema mais desafiador e um mais longo. Assim, um erro comum aqui foi ter colocado solução do ano passado sobre o seu um pager e depois é só copiar cegamente que para baixo como a resposta, que é o direito responder a uma pergunta diferente semelhante em espírito. Mas as sutilezas aqui foram como se segue. 

Então, um, temos um nó declarado e definido da maneira usual aqui. Em seguida, definimos lista de ser um mundial ponteiro inicializado como nulo. Então, aparentemente, há duas funções temos protótipos para aqui, inserção e remover. E então nós temos um código de exemplo aqui de fazer um monte de inserções. E, então, pedir-lhe para completar a implementação de inserção abaixo de tal uma maneira que ele insere n na lista em tempo constante, também salientou, mesmo que já está presente. 

Assim, a beleza de ser capaz de inserir na constante de tempo é que ela implica que você tem que inserir o novo nó de onde? Na parte da frente. Assim, ele elimina, felizmente, pelo menos um dos casos que costumavam exigir ainda mais linhas de código, como o fez no ano passado, e até mesmo na sala de aula quando Conversamos por esse tipo de coisa com os seres humanos e com alguns pseudo código verbal. Assim, na solução aqui, vamos pular para que apenas para ter um em visuais a tela. 

Observe que nós estamos fazendo o seguinte. E também perceber a outra simplificação foi a de que, mesmo que seja já está presente, então isso significa que, mesmo se o número já está lá, você pode cegamente inserir outro cópia do mesmo. E que, também, foi concebido para ser um simplificação, de modo que você poderia focar, na verdade, alguns dos mais parte intelectualmente interessante e não apenas alguns erro adicional verificação dado o tempo limitado. 

Assim, nesta solução de amostra, alocamos um ponteiro na mão esquerda lado aqui a um nó. Agora, percebo que ponteiro, como Rob disse, é de apenas 32 bits. E ele realmente não contêm um endereço até que você atribuir-lhe o endereço. E fazemos isso na mão direita lado via malloc. Como um bom cidadão, verificamos que malloc não é, na verdade, nula, de modo que não criar acidentalmente um segfault aqui. E cada vez que você usa malloc na vida, você deve ser a verificação de nulo, para que não você tem um bug sutil. 

Então nós inicializar que nula por atribuição de n e anterior e seguinte. E, neste caso aqui, eu inicializado anterior ao nulo, porque este novo nó vai ser o novo começando da minha lista. Portanto, não vai ser nada antes dele. E quero acrescentar, essencialmente, o lista existente para o novo nó assentada perto igual à lista em si. Mas eu não acabei ainda. Então, se a própria lista já existia, e houve pelo menos um nó já em vigor, se esta é a lista aqui e eu inserir um novo nó aqui, eu precisa ter certeza de que o meu ex-nó aponta para trás, para o meu novo nó, porque esta é, de novo, uma lista duplamente vinculada. 

Então, fazemos um teste de sanidade. Se a lista não for nulo, se já existe um ou mais nós de lá, então acrescentar que volta de referência, por assim dizer. E então a última coisa que precisamos fazer é realmente atualizar o mundial lista de variáveis-se a apontar para que o novo nó. É. 

AUDIÊNCIA: Na seta de ponteiro [Inaudível] é igual a nulo, faz isso lidar com a lista porque a lista é nulo? 

DAVID J. MALAN: Nope. Isso é simplesmente ser eu proativamente cuidadoso, em que, se esta é a minha lista original com talvez alguns mais nós por aqui e eu estou inserindo meu novo nó aqui, não vai ser nada por aqui. E eu quero capturar essa idéia definindo anterior para nulo no novo nó. E, presumivelmente, se meu código está correto e não há nenhuma outra maneira de inserir para além desta função, nós presumivelmente, mesmo que a lista já tem um ou mais nós em que, presumivelmente, o lista, o primeiro nó, teria um ponteiro anterior da própria nula. 

AUDIÊNCIA: E apenas um follow-up. A razão pela qual você coloca ponteiro próximos iguais lista é que você está fazendo com que o ponteiro antes lista em que ele está apontando para o outro, eu acho - Eu não - apenas lista? 

DAVID J. MALAN: Exatamente. E assim vamos realmente considerar dois casos aqui realmente, mesmo que o ordem, vamos considerá-los não é exactamente o mesmo que o código. Mas em um nível alto, se isso representa lista e este é um 32-bit ponteiro, o cenário mais simples é que este é nulo por padrão. E suponha que eu quero inserir o número 50 foi o primeiro número. Então, eu estou indo para ir em frente e alocar um nó, que vai conter três campos - n, anterior e seguinte. 

Eu vou colocar o número 50 aqui, porque isso vai ser n. Este será o próximo. E isso vai ser anterior. E então o que posso fazer neste caso? Bem, eu tenho apenas a linha 1 feito aqui. Pointer n fica n. Eu estou dizendo, então, anterior deve obter nulo. Então isso vai ser nulo. Então eu vou dizer a seguir vai ficar lista. 

E isso só funciona bem. Este é nulo. E assim que eu estou dizendo, o novo nó do próximo campo deve conseguir tudo o que é isso. Assim que coloca outro nulo lá. E então a última coisa Eu faço é verificar aqui. Se a lista não é igual a zero, mas é igual a zero, de modo que ignorar que completamente. E assim, tudo o que faço é fica próxima lista ponteiro, o que resulta em pictoricamente uma imagem assim. Então esse é um cenário. 

E o que você estava perguntando sobre especificamente é uma situação como essa, onde já temos uma lista de um nó. E se eu voltar a subir no original enunciado do problema, o próximo nós vamos inserir dizer é 34, apenas para a causa da discussão. Então eu vou apenas convenientemente tirar essa aqui. Acabei malloced. Vamos supor que eu estou verificando nulo. 

Agora, eu estou indo para inicializar n ser 34. E isso vai ser n. Este será o próximo. E isso vai ser anterior. Vamos ter certeza que eu não fiz obter este para trás. Anterior vem em primeiro lugar na definição. Deixe-me corrigir isso. Este é anterior. Este é o próximo. Mesmo que estes são idênticos, vamos mantê-lo consistente. 

Anterior. Este é o próximo. Então, eu acabei de malloced minha nota, verificado para nula, atribuídos 34 no nó. Anterior fica nulo. Então isso me dá isso. Próxima lista fica. Assim, a lista é esta. Portanto, este é o mesmo agora como desenhar este seta, de modo que apontem para uma na mesma. E então eu estou verificando se a lista não é igual a nulo. E não é desta vez. Então eu vou fazer a lista anterior fica ponteiro. 

Então lista anterior fica PTR. Então, isso tem o efeito de colocar uma seta gráfica aqui. E isso está ficando um pouco ondulado, as linhas. E então, finalmente, eu atualizo listar para apontar para ponteiro. Então agora isso aponta para esse cara. E agora, vamos fazer uma rápida verificação de sanidade. 

Aqui está a lista, que é a variável global. O primeiro nó é, na verdade, 34, porque Eu estou seguindo a seta. E isso é correto porque eu quero inserir no início da lista todos os novos nós. Seu próximo campo me leva a esse cara. Se eu continuar, eu bati em seguida é nulo. Portanto, não há mais lista. Se eu acertar anterior, recebo de volta onde eu esperar. 

Assim, ainda há algumas indicações, obviamente, de manipular. Mas o fato de que lhe foi dito para fazer esta em tempo constante significa que você só têm um número finito de coisas você está autorizado a fazer. E o que é esse número? Pode ser um passo. Ele pode ser dois. Ele pode ser de 1.000 passos. Mas é finito, o que significa que você não pode ter qualquer tipo de looping em curso aqui, sem recursão, sem loops. Ele simplesmente tem que ser linhas codificadas de código que temos nesta amostra. 

Assim, o próximo problema 12 nos pediu para concluir a implementação de remover a seguir, de tal maneira que remove n da lista em tempo linear. Então você tem um pouco mais espaço de manobra agora. Você pode assumir que n, se presente na lista, estará presente não mais do que uma vez. E que também pretende ser uma base-quiz hipótese simplificadora, de modo que se você encontrar o número 50 em algum lugar na lista, você também não tem que se preocupar continuando a iteração, à procura de todos os possíveis cópia de 50, que só iria devolver em alguma minúcia em tempo limitado. 

Assim, com remoção, este foi definitivamente mais desafiador e mais código para escrever. Mas, à primeira vista, francamente, pode ser algo esmagador e como não há nenhuma maneira que você pode ter chegar a em um quiz. Mas se concentrar nas etapas individuais, Esperemos que de repente golpeá-lo de que cada um deles individualmente etapas faz sentido óbvio em retrospecto. Então, vamos dar uma olhada. 

Então, primeiro, nós inicializar ponteiro a ser em si uma lista. Porque eu quero que o tempo linear, o que significa Vou ter algum loop. E uma maneira comum de interagir sobre o nós em uma estrutura de lista ou qualquer tipo da estrutura de forma iterativa é tomar um ponteiro para a frente dos dados estrutura e depois é só começar a atualizar lo e caminhar seu caminho através da estrutura de dados. Então, eu vou fazer exatamente isso. 

Enquanto ponteiro, minha variável temporária, não é igual a zero, vamos vá em frente e confira. Será que eu tenho sorte? É o campo n no nó Atualmente estou olhando igual ao número que eu estou procurando? E se assim for, vamos fazer alguma coisa. Agora, observe esta condição se rodeia a toda seguintes linhas de código. Esta é a única coisa que me interessa - encontrar um número em questão. Portanto, não há outra coisa, o que simplifica coisas conceitualmente um pouco. 

Mas agora, eu percebi, e você pode ter só percebi isso depois de pensar através de um bit, há na verdade, dois casos aqui. Uma delas é que o nó é o início da lista, que é um pouco chato, porque isso é uma caso especial, porque você tem que lidar com essa coisa, que é a única anormalidade. Em qualquer outro lugar na lista, é a mesma coisa. Há um nó anterior e próxima nó, o nó anterior, próximo nó. Mas esse cara é um pouco especial se ele está no início. 

Portanto, se o apontador é igual a lista em si, então se eu estou no início da a lista e eu descobri n, eu preciso para fazer um par de coisas. Um, eu preciso mudar a lista apontar para o campo seguinte, 50. Então suponho que eu estou tentando para remover 34. Então esse cara tem que ir longe em apenas um momento. 

Então, eu vou dizer, a lista ponteiro fica próximo. Bem, este é ponteiro. Em seguida está apontando aqui. Então, isso está mudando esse direito flecha agora a apontar para esse cara aqui. Agora, lembre-se, nós temos uma variável temporária. Então, nós não temos nenhum nó órfão, porque eu também tenho esse cara na minha implementação de remoção. Então, agora, se a lista em si não é nulo, Eu preciso corrigir uma coisinha. 

Eu preciso agora ter certeza de que esta seta, que é previamente apontando 50-34, este tem que ir embora, porque se eu estou tentando se livrar de 34, 50 é melhor não manter qualquer tipo de referência de volta a ele como o seta sugerido. Então, eu só fiz essa linha. Então eu sou feito. Esse caso é realmente muito fácil. Decepar a cabeça da lista é relativamente simples. 

Infelizmente, não é isso bloco chato mais. Então, agora, eu tenho que considerar o caso onde há algo no meio. Mas não é terrível demais, com exceção para a sintaxe como esta. Então, se eu não estou no início da lista, eu estou em algum lugar no meio. E esta linha aqui está dizendo, início em qualquer nó que você está. Ir para a próxima área do nó anterior e apontam que no ponteiro. 

Vamos fazer isso pictoricamente. Isso estava ficando complicada. Então, se eu tenho campos anteriores aqui - vamos fazer isso - próximos campos aqui. Vou simplificar meus ponteiros vez de desenhar um monte de coisas e para trás cruzando uns aos outros. E agora, vamos apenas dizer que este é 1, 2, 3 para fins de discussão, mesmo no entanto, que não se alinha com o problema em questão. 

Então aqui vai a minha lista encadeada. Estou tentando remover dois nesta determinada versão da história. Então eu atualizei ponteiro para estar apontando para esse cara. Portanto, esta é PTR. Ele está apontando aqui. Esta lista é, que existe globalmente como antes. E ele está apontando aqui, não importa o quê. E agora, eu estou tentando remover dois. 

Então, se ponteiro está apontando aqui, estou vai seguir, aparentemente, a ponteiro anterior, o que me coloca em 1. Estou, então, vai dizer que o próximo campo, o que me traz até este caixa aqui, vai ponteiro igual seguinte. Portanto, se esse ponteiro, este é o próximo. Isso significa que esta necessidade de seta para apontar para esse cara. 

Então, o que essa linha de código tem apenas feito é um pouco disso. E agora, isso está parecendo um passo na direção certa. Nós essencialmente quer cortar 2 do meio de 1 e 3. Portanto, faz sentido que queremos rota este ponteiro em torno dele. Portanto, esta linha seguinte é verificar se ponteiro próximo não é nulo, não há de facto alguém para a direita, de 2, isso significa que nós também temos que fazer um pouco de cortar aqui. 

Então eu agora precisa seguir este ponteiro e atualizar o ponteiro anterior sobre esse cara para fazer um pouco de um resolver aqui o ponto aqui. E agora, visualmente este é bom. É um pouco confuso em que não há ninguém apontando para o 2 mais. 2 está apontando para a esquerda. E 2 está apontando para a direita. Mas ele pode fazer o que quiser, porque ele está prestes a ser libertado. E não importa o que esses valores são mais. 

O que é importante é que o restante caras estão encaminhamento acima e abaixo dele agora. E, de fato, isso é o que fazer a seguir. Nós ponteiro livre, o que significa que dizer a sistema operacional, você é bem-vindo para recuperar isso. E então, finalmente, voltamos. Else implicitamente, se ainda não voltou, temos que continuar procurando. Então ponteiro igual ponteiro próximo apenas significa mover esse cara aqui. Mova esse cara aqui. Mova esse cara aqui, se, de fato, não encontramos o número estamos procurando ainda. 

Então, francamente, parece completamente esmagadora, eu acho, em primeiro lugar vista, especialmente se você se esforçou com isso durante o teste, em seguida, ver algo como isto. E você palmadinhas nas costas. Bem, não há nenhuma maneira que eu poderia ter chegar a isso no quiz. Mas eu diria, você pode, se você quebrar lo em estes indivíduos casos e apenas atravessá-la cuidado, embora, na verdade, sob circunstâncias estressantes. 

Felizmente, a imagem feita tudo mais feliz. Você poderia chamar isso de qualquer número de maneiras. Você não tem que fazer o entrecruzamento coisa aqui. Você poderia fazê-lo com reta linhas como esta. Mas a essência deste problema, em geral, foi perceber que o imagem, no final, deve olhar um pouco algo como isso, porque constante de tempo implícito que você mantenha tocando e tocando e tocando o novos nós no início da lista. Alguma pergunta? Provavelmente o maior desafio de certamente as perguntas de codificação. 

AUDIÊNCIA: Então a lista é semelhante ao cabeça nos exemplos anteriores. 

DAVID J. MALAN: Exatamente, exatamente. Apenas um nome diferente para uma variável global. Em todo o mundo o que? 

ROB BOWDEN: OK. Portanto, esta é aquela em que você tinha que escrever o parágrafo. Algumas pessoas escreveu ensaios para esta pergunta. Mas você só precisa usar esses seis termos para descrever o que acontece quando você tentar entrar em contato facebook.com. Então eu vou falar com o processo usando todos esses termos. Assim, em nosso navegador, nós digitamos facebook.com e pressione Enter. Assim, o nosso navegador vai construir uma HTTP solicitar que vai enviar através de algum processo de Facebook para Facebook para responder-nos com a HTML da sua página. 

Então, o que é o processo pelo que o pedido HTTP realmente fica para o Facebook? Então, primeiro, temos de traduzir Facebook.com. Então, só recebeu o nome Facebook.com, onde realmente faz a solicitação HTTP precisa ir? Então, precisamos traduzir Facebook.com para um endereço IP, que unicamente identifica o que a máquina que realmente pretende enviar esta solicitação para. O laptop tem um endereço IP. Tudo conectado à internet tem um endereço IP. 

Então, DNS, Domain Name System, que é o que vai lidar com a tradução do facebook.com para um endereço IP que você realmente quiser entrar em contato. Então, entramos em contato com os servidores DNS e por exemplo, o que é facebook.com? Ela diz, oh, é o endereço IP 190,212 alguma coisa, alguma coisa, alguma coisa. Tudo bem. Agora, eu sei o que a máquina Quero entrar em contato. 

Então você enviar o seu pedido HTTP sobre a máquina. Então como é que chegar a essa máquina? Bem, a solicitação vai de roteador para roteador salto. Lembre-se do exemplo em sala de aula, onde em que vimos a rota que o pacotes tomou quando tentamos para se comunicar. Vimo-lo saltar sobre o Atlântico Oceano em um ponto ou qualquer outra coisa. 

Assim, o último porto prazo. Portanto, esta é agora em seu computador. Você pode ter várias coisas atualmente comunicar com a Internet. Para que eu possa estar em execução, por exemplo, o Skype. Eu poderia ter um navegador web aberto. Eu poderia ter algo que torrenting arquivos. Então todas essas coisas são comunicando com a internet de alguma forma. 

Assim, quando o computador recebe alguns dados a partir da internet, como o faz sabe o aplicativo realmente quer os dados? Como é que sei se este particular dados é para o torrenting aplicação em oposição para o navegador web? Portanto, este é o propósito de portos em que todas estas aplicações têm afirmou uma porta no computador. Portanto, o seu navegador diz, hey, Eu estou escutando na porta 1000. E o seu programa torrenting está dizendo: Eu estou escutando na porta 3000. E Skype diz, eu estou usando a porta 4000. 

Então, quando você recebe alguns dados que pertence a uma destas aplicações, os dados é marcado com qual porta ele realmente deve ser enviada ao longo de. Portanto, este diz, oh, eu pertenço a porta 1000. Eu sei, então eu preciso transmitir a presente junto ao meu navegador. Assim, a razão é relevante aqui é que os servidores web tendem a ouvir na porta 80. Então, quando eu entrar em contato Facebook.com, eu sou comunicar com uma máquina. Mas eu preciso dizer que a porta de que máquina Quero comunicar. E os servidores web tendem a ser escutando na porta 80. 

Se eles quisessem, eles poderiam defini-lo para que ele enumera como na porta 7000. E então em um navegador web, eu poderia digitar manualmente Facebook.com: 7000 a enviar a solicitação para a porta 7000 de servidor de web do Facebook. 

DAVID J. MALAN: E, neste caso, mesmo embora não exigiu que as pessoas mencionar isso, neste caso, o porto que o pedido realmente ir para? Tente novamente. Exatamente. Sem olhar para isso, mas uma sutileza que está lá nenhum a última. 

ROB BOWDEN: Então, o HTTPS, já que é escuta especificamente para o criptografado, é na porta 4430. 

Audiência: E-mails são de 25, certo? 

DAVID J. MALAN: Saída e-mails, 25, sim. 

ROB BOWDEN: Eu nem sei mais de a - todos os mais baixos tendem a ser reservado para as coisas. Eu acho que tudo sob 1024 é reservado. 

AUDIÊNCIA: Por que você disse 3 é o número errado? 

ROB BOWDEN: Porque em um endereço IP, há quatro agrupamentos de dígitos. E eles são de 0 a 255. Então, 192.168.2.1 é um comum endereço IP da rede local. Observe todos esses são menos de 255. Então, quando eu comecei com 300, que não poderia ter sido um dos números. 

DAVID J. MALAN: Mas esse clipe bobo de - era CSI, onde tiveram um número que era muito grande para o endereço IP. 

ROB BOWDEN: Qualquer dúvida sobre isso? A próxima, mudança tão completa em tema, mas temos este array PHP para as casas da quad. E nós temos uma lista desordenada. E nós queremos imprimir cada item da lista apenas contendo o nome da casa. Portanto, temos um loop foreach. Então lembre-se, a sintaxe é foreach matriz como item na matriz. Assim, através de cada iteração do loop, casa vai assumir um dos valores dentro da matriz. 

Na primeira iteração, casa será Cabot House. Em uma iteração segundo, a casa vai ser Correio casa e assim por diante. Assim, para cada quad como casa, estamos só vai imprimir - você também poderia ter ecoado - o item da lista e, em seguida, o nome da casa e, em seguida, fechar o item da lista. As chaves são opcionais aqui. 

E então nós também disse na pergunta si mesmo, lembre-se de fechar a desordenadas lista de etiquetas. Então, precisamos sair do modo PHP a fim de fazer isso. Ou poderíamos ter ecoado a fechar tag lista não ordenada. 

DAVID J. MALAN: Também seria bem aqui ter sido a usar uma antiga escola para loop com um $ i = 0 0 e usando a contagem descobrir o comprimento do raio. Totalmente bem também, apenas um pouco prolixa. 

AUDIÊNCIA: Então, se você estava indo para [Inaudível], você faria - Eu esqueço o que o loop [inaudível] é. Você $ suporte quad i? 

DAVID J. MALAN: Exatamente. Sim, exatamente. 

ROB BOWDEN: Mais alguma coisa? 

DAVID J. MALAN: Tudo bem. Trade-offs. Assim, havia cachos de respostas possível para cada um deles. Nós estávamos realmente apenas à procura de algo convincente para um lado positivo e um lado negativo. E o número 16 pediu, validando os usuários ' do lado do cliente de entrada, como com JavaScript, em vez de no lado do servidor, como acontece com PHP. Então o que é um lado positivo de fazendo do lado do cliente? 

Bem, uma das coisas que propusemos é que você reduzir a latência, porque você não tem que se preocupar em contato com o servidor, o que pode demorar um pouco milissegundos ou até mesmo um par de segundos evitando que e apenas validando a entrada do lado do cliente dos usuários por provocando um manipulador on-apresentar e apenas a verificação, eles digite algo para o nome? Será que eles digitar algo no para o endereço de e-mail? Será que eles escolhem um dormitório de No menu drop-down? 

Você pode dar-lhes feedback instantâneo usando o computador gigahertz ou o que eles têm que é na verdade, em sua mesa. Então é só um usuário melhor experimentar normalmente. Mas uma desvantagem de fazer do lado do cliente validação, se você fizer isso sem também fazer a validação do lado do servidor é que mais ninguém saindo do CS50 sabe que você pode apenas enviar todos os dados que deseja para um servidor de qualquer número de maneiras. Francamente, na maior parte de qualquer navegador, você pode clique em torno das definições e apenas desligar o JavaScript, o que, portanto, desabilite qualquer forma de validação. 

Mas você também deve se lembrar que, mesmo que eu fiz algumas coisas misteriosas na classe usando telnet e realmente fingindo ser um navegador enviando get solicitações para um servidor. E isso certamente não é utilizando qualquer JavaScript. Isso é só me digitar comandos num teclado. Então, realmente, qualquer programador dentro suficiente conforto com a web e HTTP poderia enviar todos os dados que ele ou ela quer para um servidor sem validação. E se o seu servidor não está também a verificação, que me deram um nome, é isso realmente um endereço de email válido, não eles escolhem um dormitório, você pode acabar se inserir falso ou apenas de dados em branco em seu banco de dados, o que provavelmente não vai ser uma coisa boa se você estava supondo que ele estava lá. 

Portanto, esta é uma realidade desagradável. Mas, em geral, do lado do cliente validação é grande. Mas isso significa que o dobro do trabalho. Embora exista vários bibliotecas, bibliotecas JavaScript para exemplo, que fazer isso muito, muito menos de uma dor de cabeça. E você pode reutilizar parte do código do lado do servidor, do lado do cliente. Mas não percebem que é tipicamente trabalho adicional. É. 

AUDIÊNCIA: Então, se nós apenas disse menos seguro - 

DAVID J. MALAN: [Risos] Ugh. Aqueles são sempre o mais difícil aqueles para julgar. 

ROB BOWDEN: Isso faria foram aceites. 

DAVID J. MALAN: O quê? 

ROB BOWDEN: Eu criei este problema. Isso teria sido aceito. 

DAVID J. MALAN: Yeah. 

AUDIÊNCIA: Cool. 

ROB BOWDEN: Mas nós não aceitou para o primeiro - bem, o que estávamos procurando é algo que você não tem que comunicar com o servidor. Nós não aceitamos apenas mais rápido. 

AUDIÊNCIA: E sobre Não recarregar a página? 

ROB BOWDEN: sim. Essa foi uma resposta aceita. 

DAVID J. MALAN: Qualquer coisa onde nos sentimos que era mais provável que não provável que você sabia o que eram dizendo, que é um duro linha para desenhar algumas vezes. Usando uma lista ligada em vez de uma matriz para manter um lista de inteiros ordenada. Então, um de cabeça, muitas vezes citam com ligado listas que motivaram a sua inteira introdução foi você começa dinamismo. Elas podem crescer. Eles podem encolher. Então você não tem que saltar através de aros realmente criar mais memória com uma matriz. Ou você não tem que apenas dizer, desculpe, o usuário. A matriz é preenchida. Assim, o crescimento dinâmica da lista. A desvantagem apesar de listas ligadas? 

AUDIÊNCIA: É linear. Pesquisando em lista ligada é linear ao invés do que você log in 

DAVID J. MALAN: Exatamente. Pesquisando em uma lista ligada é linear, mesmo que seja ordenado, porque você pode apenas siga estas migalhas de pão, estes ponteiros, a partir do início da lista ao fim. Você não pode utilizar o acesso aleatório e, Assim, busca binária, mesmo que seja classificado, que você poderia fazer com um array. E há também um outro custo. É. 

AUDIÊNCIA: Memória ineficiente? 

DAVID J. MALAN: Yeah. Bem, eu não iria, necessariamente, dizer ineficiente. Mas isso não lhe custa mais memória, porque você precisa de 32 bits para cada nó para o ponteiro adicional, em menos para uma lista vinculada isoladamente. Agora, se você está armazenando apenas números inteiros e você está adicionando o ponteiro, que é na verdade, uma espécie de não-trivial. É duplicando a quantidade de memória. Mas, na realidade, se você está armazenando um lista ligada de estruturas que possam ter 8 bytes, 16 bytes, ainda mais do que isso, talvez seja menos de um custo marginal. Mas é um custo, no entanto. Assim, ou daqueles teria sido muito bem como desvantagens. 

18. Utilizando o PHP em vez de C para escrever um programa de linha de comando. Então, aqui, muitas vezes é mais rápido usar uma linguagem como PHP ou Ruby ou Python. Você acabou de abrir rapidamente um editor de texto. Você tem muito mais funções disponíveis para você. PHP tem a pia da cozinha de funções, enquanto que em C, você tem muito, muito pouco. Na verdade, a gente sabe a maneira mais difícil que você não tem tabelas de hash. Você não ligaram listas. Se você quiser aqueles, você tem que implementá-las você mesmo. 

Então, uma cabeça de PHP ou realmente qualquer linguagem interpretada é a rapidez com o qual você pode escrever código. Mas uma desvantagem, vimos isso quando eu rapidamente chicoteado até um misspeller implementação na aula usando PHP, é que o uso de uma linguagem interpretada é geralmente mais lento. E vimos que comprovadamente com um aumento no tempo de 0,3 segundos para três segundo, devido à interpretação que realmente acontece. 

Outra vantagem é que você não tem que compilar. Por isso, também acelera o desenvolvimento aliás, porque você não tem duas etapas para a execução de um programa. Você só tem um. E assim que é bastante atraente também. Usando um banco de dados SQL, em vez de um arquivo CSV para armazenar dados. Banco de dados para SQL é usado para pset7. Arquivos CSV você não usar muito. Mas você usou indiretamente em pset7 como bem, conversando com o Yahoo Finance. 

Mas CSV é como um arquivo do Excel, mas super simples, onde as colunas são apenas demarcado por vírgulas dentro de um arquivo de texto de outra forma. E usando um banco de dados SQL é um pouco mais convincente. É um lado positivo, porque você fazer as coisas como selecionar e inserir e excluir. E você tem, presumivelmente, índices que MySQL e outros bancos de dados, como Oracle, construir para você na memória, que significa que a sua escolha não é provavelmente vai ser top linear para baixo. É realmente vai ser algo como busca binária ou algo semelhante em espírito. Então, eles são geralmente mais rápido. 

Mas a desvantagem é que é apenas mais trabalho. É mais esforço. Você tem que entender bancos de dados. Você tem que configurá-lo. Você precisa de um servidor para executar esse banco de dados em. Você precisa entender como configurá-lo. Então, essas são apenas estes tipos de trade-offs. Considerando um arquivo CSV, você pode criá-lo com gedit. E você está pronto para ir. Não há nenhuma complexidade além disso. 

Usando um trie em vez de uma tabela hash com encadeamento separado para armazenar uma dicionário de palavras que lembram de pset5. Assim, um tenta de cabeça, em teoria pelo menos, é o que? Constante de tempo, pelo menos se você for hashing em cada do indivíduo letras em uma palavra, como você pode ter para pset5. Isso pode ser cinco, seis hashes hashes se há cinco ou seis letras da palavra. E isso é muito bom. E se há um limite superior sobre a forma como longo de suas palavras possam ser, que é tempo de fato assintoticamente constante. 

Considerando uma tabela hash com separado encadeamento, o problema lá com que tipo de estrutura de dados é que o desempenho de seus algoritmos normalmente depende do número de coisas já na estrutura de dados. E isso é definitivamente o caso com cadeias, em que quanto mais coisas você colocar em uma tabela hash, mais tempo os cadeias de ir, o que significa que, na pior caso, a coisa que você pode estar procurando é toda a maneira, no final de um dessas cadeias, o que efetivamente transforma em algo linear. 

Agora, na prática, é absolutamente possível ser o caso de uma tabela hash com cadeias é mais rápido do que um correspondente implementação trie. Mas isso é, por várias razões, entre que são tentativas usar um monte de memória que pode, de fato, as coisas devagar para baixo, porque você não ficar bom benefícios de uma coisa chamada cache, onde as coisas que estão juntos em memória pode ser acedida muitas vezes mais rapidamente. E às vezes você pode vir até com realmente uma boa função hash. Mesmo que você tem que perder um pouco de memória, você pode, de fato, ser capaz de encontrar as coisas rápido e não tão ruim quanto linearmente. 

Então, em suma, não havia necessariamente com qualquer um um ou mesmo dois coisas específicas que estávamos procurando. Realmente nada convincente como ascendentes e descendentes geralmente chamou nossa atenção. 

ROB BOWDEN: Então, para o lado positivo, fizemos não aceitar a sua própria "mais rápido". Você tinha a dizer algo sobre isso. Mesmo que você disse, teoricamente, mais rápido, sabíamos que tipo de entendido que é 0 a 1. E tabela hash, em teoria, Não é de 0 a 1. Mencionando nada sobre tempo de execução geralmente tem os pontos. Mas o "mais rápido", a maioria das soluções em o grande conselho que foram tentativas foram objectivamente mais lento do que as soluções que eram tabelas de hash. Assim, mais rápida em si não é realmente verdade. 

DAVID J. MALAN: Dom de dom dom. Eu sou provavelmente o único que percebe é assim que é suposto ser pronunciado, certo? 

ROB BOWDEN: Eu tinha, na verdade, não faço idéia. 

DAVID J. MALAN: Fez sentido na minha cabeça. 

ROB BOWDEN: Eu estou fazendo este. OK. Portanto, esta é aquela em que você tinha que desenhar o diagrama semelhante a você pode tenho visto nos exames anteriores. Então vamos apenas olhar para isso. Então, a partir do nó HTML, temos dois crianças, a cabeça eo corpo. Então, nós ramificar - cabeça e corpo. A cabeça tem uma tag title. Portanto, temos um título. 

Agora, a única coisa que um monte de gente esqueceu é que esses nós de texto são elementos dentro desta árvore. Então aqui nós acontecer para desenhá-los como ovais para diferenciá-los a partir destes tipos de nós. Mas note também aqui temos de topo, meio e fundo vai acabar por ser nós de texto. Então, esquecendo aqueles foi um pouco de um erro comum. 

O corpo tem três filhos - estas três divs. Então div, div, div e então o texto filhos do nó desses divs. Isso é muito bonito isso para que as perguntas. 

DAVID J. MALAN: E é interessante notar, apesar de não se debruçar sobre estes detalhes do tempo que gastamos em JavaScript, que faz o pedido, em fato, a matéria tecnicamente. Então, se a cabeça vem antes do corpo na HTML, em seguida, ele deve aparecer ao esquerda do corpo no DOM efectivo. Que o seu é, em geral, apenas FYI, uma coisa chamada ordem do documento, onde isso não importa. E se você foi a implementação de um parser, um programa que lê HTML na construção até a árvore na memória, para ser honesto, isso é provavelmente o que você intuitivamente fazer de qualquer maneira - de cima para baixo, esquerda para a direita. 

ROB BOWDEN: Perguntas sobre isso? Devo fazer o próximo? 

DAVID J. MALAN: Claro. 

ROB BOWDEN: OK. Então este é o estouro de buffer pergunta ataque. A principal coisa a reconhecer é aqui, bem, como pode um truque adversário este programa em execução código arbitrário? Então argv1, a primeira linha de comando argumento a este programa, que pode ser arbitrariamente longo. Mas aqui estamos usando memcpy para copiar argv1, que aqui é bar. Estamos passando-o como argumento. E assim ele está tomando na barra de nome. 

Então, nós estamos memcpying bar neste tampão c. Quantos bytes estamos copiando? Bem no entanto muitos bytes bar acontece a estar usando, o comprimento do argumento. Mas c é de apenas 12 bytes de largura. Então, se nós digitamos um argumento de linha de comando isso é mais do que 12 bytes, estamos vai transbordar esta determinado buffer. Agora, como pode um adversário enganar o programa em execução de código arbitrário? 

Então lembre-se que aqui principal é chamar foo. E então chamadas principais foo. Vamos desenhar isso. Portanto, temos a nossa stack. E principal tem um quadro de pilha na parte inferior. Em algum momento, as chamadas principais foo. Bem, de imediato, as chamadas principais foo. E assim foo recebe o seu próprio quadro de pilha. 

Agora, em algum momento, foo vai voltar. E foi foo retornos, o que precisamos saber em que linha de código dentro de nós principal estavam a fim de saber onde devemos continuar na principal. Podemos chamar foo de um todo monte de lugares diferentes. Como sabemos para onde voltar? Bem, precisamos guardar isso em algum lugar. 

Então, em algum lugar por aqui, nós armazenamos onde devemos voltar a uma vez foo retorna. E este é o endereço de retorno. Então, como um adversário pode tirar partido isto é o facto de que este tampão c são armazenados, vamos dizer, aqui é c. Então, nós temos 12 bytes para c. Este é c. E este é o anel pilha de foo. Portanto, se o usuário mal-intencionado entra mais bytes do que 12 ou eles entram em um comando argumento de linha que é mais do que 12 caracteres, então vamos transbordar este buffer. 

Podemos continuar. E em algum momento, vamos longe o suficiente para que nós começamos substituir este endereço de retorno. Assim, uma vez que substituir o endereço de retorno, isto significa que, quando foo retornos, estamos voltando para onde quer que o usuário mal-intencionado está dizendo a ele para por o valor que ele entrou, por qualquer caracteres que o usuário inseriu. E assim, se o usuário malicioso está sendo particularmente inteligente, ele pode ter esse voltar para algum lugar no printDef função ou em algum lugar do malloc função, em qualquer lugar arbitrário. 

Mas ainda mais inteligente é o que se tem o usuário retornar para a direita aqui. E então você começa a execução de estes como linhas de código. Então, nesse ponto, o usuário pode entrar o que ele quer para esta região. E ele tem o controle completo sobre o seu programa. Perguntas sobre isso? Portanto, a próxima pergunta é completa o reimplementação do foo de tal forma que ele não é mais vulnerável. 

Portanto, há um par de maneiras você poderia ter feito isso. Ainda temos c apenas sendo de comprimento 12. Você poderia ter mudado isso como parte de sua solução. Nós também adicionamos um cheque para fazer certeza de bar não era nulo. Embora você não precisa que para o crédito total. Então, nós estamos verificando o primeiro comprimento da corda de bar. Se for maior do que 12, então Não, na verdade, fazer a cópia. Então essa é uma maneira de corrigi-lo. 

Uma outra forma de fixação é, em vez de c tendo apenas ser de comprimento 12, tê-lo ser de comprimento strlen (bar). Outra maneira de fixar é realmente só retornar. Então, se você tivesse acabado de se livrar de todos isso, se você tivesse apagado tudo linhas de código, você teria chegado todo o crédito, uma vez que esta função na verdade não realizar qualquer coisa. É copiar a linha de comando argumento em algum arranjo em seu quadro de pilha local. E então a coisa está voltando. E o que for realizado está desaparecido. Assim, o retorno também foi suficiente forma de obtenção de crédito total. 

DAVID J. MALAN: Não é bem o espírito de a questão, mas aceitável por a especificação, no entanto. 

ROB BOWDEN: Perguntas sobre nada disso? A única coisa que você, pelo menos, precisava ter compilar o código. Assim, mesmo que tecnicamente você não está vulnerável se o seu código não compilar, não aceito isso. Não há dúvidas? OK. 

DAVID J. MALAN: Você quer dizer que este título? 

ROB BOWDEN: Não. 

DAVID J. MALAN: Então, em um presente, este era ou uma boa notícia ou má notícia. Este é literalmente o mesmo problema como o primeiro quiz. E é quase o mesmo problema como pset1. Mas isso foi deliberadamente simplificados para ser uma pirâmide mais simples, que pode ser resolvido com um pouco iteração mais simples. E realmente, o que se locomover em aqui não era tanto a lógica, porque provavelmente, por esta altura, você está mais confortável do que você estava em uma semana com loops ou por loops, mas realmente para provocar uma separação que você está um pouco confortável com a noção de que o PHP não é apenas sobre o que programação. Na verdade, pode ser usado como uma linguagem para escrever programas de linha de comando. 

E, de fato, é o que nós estávamos tentando de chamar a atenção. Este é um programa para a linha de comando. Então código C aqui, enquanto correta em C, não corrigir para PHP. Mas o código é realmente o mesmo. Se você comparar as soluções para Teste 0 contra o Teste 1, você verá que é quase idêntico, exceto por alguns sinais de dólar e para o ausência de um tipo de dados. Em particular, se dermos uma olhada aqui, você verá que nós iteração, neste caso, de 1 a 7. 

Poderíamos ter feito isso 0 índice. Mas, às vezes, eu acho que é apenas mentalmente mais fácil pensar sobre as coisas de 1 a 7. Se você quiser um bloco, depois dois blocos, em seguida, três, então ponto, ponto, ponto sete. Temos j sendo inicializado a 1 e, em seguida, contando com até i. E tudo aqui é de outro modo idêntica. Mas digno de nota são um par de coisas. Nós damos-lhe estas duas linhas, esta primeira um, goofily nomeado como um shebang para estrondo afiada. E isso só especifica o caminho, a pasta, em que um programa pode ser descobri que você quer usar para interpretar esse arquivo. 

E, em seguida, a linha de, depois disso, de claro, significa entrar no modo PHP. E a linha na parte inferior significa sair do modo PHP. E esta funciona, em geral, com linguagens interpretadas. É uma espécie de irritante se você escrever um programa em um arquivo chamado foo.php. E, em seguida, os utilizadores têm apenas lembre-se, OK, para executar este programa, eu tem que digitar "espaço php foo.php". Tipo de chato se nada mais. E também revela que o seu programa É escrito em PHP, que não é de todo que ilumina para o usuário. 

Assim, você pode remover os arquivos. Php completamente lembrar da aula. E você pode realmente fazer. / Foo se você chmodded lo, tornando-o executável. Então chmod a + x foo teria feito isso. E se você também adicionar a coisa toda aqui. Mas, realmente, o problema estava chegando imprimir algo como isto. No HTML, sem C-código certamente, apenas algumas PHP. Então, Milo depois voltou em 25 problema. E em 25, você recebeu o seguinte código de esqueleto, o qual era um página web muito simples. E a parte suculenta HTML-wise foi para baixo aqui, onde nós temos dentro do corpo uma forma que tem identificação única de insumos no interior do qual foi duas entradas, uma com uma idéia de nome, um com uma idéia de botão. 

O primeiro foi o tipo de texto, o segundo do tipo de envio. E, assim, deu-lhe, na verdade, mais ingredientes que você precisava, só assim vocês tinham opções com as quais para resolver este problema. Você não precisa estritamente todas estas identificações. Mas permite que você resolva isso de diferentes maneiras. E no topo, observe que o objetivo foi desencadear uma janela como esta - Olá, Milo! - de pop-up no navegador usando o super simples, se , a função de alerta não feia. E assim, em última instância, isto resume-se conceitualmente de alguma forma, escutando submissões de client-side a forma , Não o lado do servidor, de alguma forma responder a essa submissão por agarrando o valor que o usuário digitou para o campo de nome e, em seguida, exibi-la no corpo de um alerta. 

Assim, uma forma de fazer isso é com jQuery, que se parece um pouco sintaticamente desconcertante no início. Você pode fazer isso com o código DOM pura - document.getelement por ID. Mas vamos dar uma olhada nesta versão. Eu tenho um par de importantes linhas primeiro. Então, um, temos esta linha, que é idêntico ao que você pode ter visto em, creio, form2.html de classe na semana 9. E este é apenas dizer, execute o código a seguir quando o documento está pronto. Esta sendo importante apenas porque Páginas HTML são lidas de cima para baixo, da esquerda para a direita. 

E, portanto, se você tentar fazer algo em código-se aqui para alguns DOM elemento, alguns tag HTML, que é baixo aqui, você está fazendo isso muito em breve, porque este não tem sequer foi lido na memória. Então, ao dizer isso document.ready linha, estamos dizendo, aqui está um código, browser. Mas não executar este até que o todo documento está pronto, que é o DOM árvore existe em memória. Este é um pouco mais simples, se sintaticamente um pouco diferente, onde eu estou dizendo, grab o elemento HTML, cuja única identificador é insumos. Isso é o que o hash tag denota, o ID único. E então eu estou ligando. Enviar. 

So. Apresentar aqui é uma função, caso contrário, conhecido como um método, que está dentro do objeto na mão esquerda lado, há que eu não destacar. Então, se você pensar em entradas como um objeto na memória - e de fato é. É um nó em uma árvore - . Enviar meios quando este formulário com essa identificação é apresentada, execute o código a seguir. Eu não me importo o que o nome do função é que estou executando. Então, aqui eu estou usando, como antes, o que é chamada a função lambda ou um função anônima. Não é de todo intelectualmente interessante que não tem nenhum nome, o que é bom se você está apenas nunca vai chamá-lo de uma vez. E lá dentro eu realmente segurar a apresentação do formulário. A primeira vez que declarar uma variável chamado valor. E então, qual é o efeito desta realçado parte aqui, agora? O que isso faz em um alto nível para mim? 

AUDIÊNCIA: Fica o valor que o usuário não fez no HTML abaixo. Ela recebe esse ID e, em seguida, verificar que o valor do mesmo. 

DAVID J. MALAN: Exatamente. Ele agarra o nó, cujo único identificador é o nome. Começa o valor nele, o que é, presumivelmente, o que o utilizador digitado si mesmo. E então ele armazena que no variável chamada valor. Como um aparte, você também pode ter sido feito isso um pouco diferente. Totalmente aceitável, fazendo algo valor mentira var fica document.getElementById. E é por isso que é um pouco tedioso para não usar jQuery. "Nome". Valor. Então, totalmente aceitável. Diferentes maneiras de fazer isso. jQuery apenas tende a ser um pouco mais sucinto e definitivamente mais populares entre os programadores. 

Agora, eu estou fazendo um pouco de sanidade verificar, porque no problema declaração nos disse explicitamente, se o utilizador ainda não digitado seu nome, não mostram uma alertas. Mas você pode verificar que, em apenas verificando a cadeia vazia para uma entre aspas, se há nada realmente lá. Mas se não é igual, entre aspas, Eu quero chamar alertas. E a parte interessante aqui é que estamos usando o operador mais, que faz o que em JavaScript? Concatenar. Então, é como operador ponto do PHP. A mesma idéia, sintaxe um pouco diferente. E eu estou apenas criando a string que você viu na captura de tela - Olá, assim e assim. 

E então o último detalhe é o seguinte. Por que eu return false dentro desta função anônima? 

AUDIÊNCIA: Não há nenhum valor. Você colocá-lo em forma. Ele apenas diz que, se o valor não é igual em branco, em seguida, fazê-lo. Havia um vazio em que a submissão. 

DAVID J. MALAN: OK. Cuidado, porém. Não há mais ninguém aqui. E esse retorno é falso fora do, se as condições. Então esta linha destacada, retornar false, executa, não importa o quando o formulário é enviado. O que faz retornar false dentro deste manipulador de eventos, como é chamado, o evento em questão sendo submissão? 

AUDIÊNCIA: Porque só acontece uma vez. 

DAVID J. MALAN: só acontece uma vez. Não é bem assim. Sim? 

AUDIÊNCIA: Ela impede que a forma de submetendo-se o comportamento padrão, o que tornaria o recarregamento da página. 

DAVID J. MALAN: Exatamente. Então, eu estou sobrecarregando o prazo apresentar aqui, porque eu estou dizendo, é a forma sendo submetido. Mas, como você sugere, na verdade não é foi apresentado no verdadeiro caminho HTTP. Ao clicar em Enviar, por causa da nossa manipulador onSubmit, estamos interceptando que a submissão do formulário, por assim dizer. Estamos então a fazer o nosso coisa com código JavaScript. Mas eu estou voltando deliberadamente falsa, porque o que eu não quero que aconteça um fração de segundo depois é para toda a forma -se a ser submetido à web servidor com pares de valores-chave, alterando a URL para ser algo como q = gatos ou qualquer outra coisa que fizemos, por exemplo, em sala de aula. Eu não quero que isso aconteça, porque não há nenhuma escuta servidor para esta formar submissão. É puramente em código JavaScript. E é por isso que eu não tinha sequer um atributo action no meu formulário, porque eu Não pretendo que isso sempre ir para o servidor. 

Então, ele está sendo submetido. Mas estamos interceptando que forma submissão e impedindo que o padrão comportamento, o que é na verdade percorrer todo o caminho para o servidor. 

AUDIÊNCIA: Então mantê-lo do lado do cliente. 

DAVID J. MALAN: Mantendo do lado do cliente dele. Exatamente. Em seguida foi a minha oh MySQL. 

ROB BOWDEN: OK. Portanto, esta primeira pergunta foi, em geral áspero para as pessoas. Embora os posteriores foi melhor. Então você tinha que escolher os dados corretos tipos de ambas as colunas. E ambos têm alguns coisas sobre eles que fazer a escolha difícil. Então int não era um válido tipo de número. A razão de ser de uma conta de 12 dígitos número, um int não é grande o suficiente para armazenar totais dígitos. Assim, uma opção válida teria sido um grande int se acontecer de você saber disso. Outra opção poderia ter sido um campo de caractere de comprimento 12. Assim, ou daqueles teria funcionado. Int não. 

Agora, o equilíbrio, acho que volta para pset7. Assim, especificamente usado para decimal armazenar o valor de ações ou - 

DAVID J. MALAN: Dinheiro. 

ROB BOWDEN: Dinheiro. Usamos decimal para armazenar a quantidade de dinheiro que o usuário possui atualmente. Assim, a razão pela qual fazemos isso é porque, lembre-se, flutua. Há de ponto flutuante de precisão. Ele não pode precisamente armazenar o dinheiro valores como nós queremos aqui. Então decimal é capaz de precisão loja algo, digamos, duas casas decimais. É por isso que o equilíbrio, nós queremos que ele ser decimal e não flutuam. 

DAVID J. MALAN: E também, também, embora que poderia ter sido inteligente em outro contextos para pensar, talvez esta é uma oportunidade para um int. Eu vou manter o controle de coisas em moedas de um centavo. Porque nós explicitamente mostrou o padrão valor de ser 100.00, que significa que poderia ser apenas um int. E outra sutileza também com o número de foi que ele não foi feito para ser uma pegadinha. Mas lembre-se que um int em MySQL, como em C, pelo menos na aparelho, é de 32 bits. E mesmo que nós não esperamos que você saber exatamente quantos dígitos que meios, me lembro que o maior número você pode representar potencialmente com um número de 32 bits é mais ou menos o quê? 

Qual o número que nós sempre diz? 2 a 32, que é o que mais ou menos? Você não tem que saber com precisão. Mas mais ou menos é útil na vida. É cerca de 4 bilhões de dólares. Então nós dissemos que algumas vezes. Eu sei que eu já disse isso algumas vezes. E é mais ou menos 4 bilhões. E isso é uma boa regra de ouro para saber. Se você tem 8 bits, 256 é o número mágico. Se você tiver 32 bits, 4 bilhões mais ou menos. Então, se você acabou de escrever 4 bilhões, você vai ver que é menos dígitos do que 12, o que significa que não é claramente expressividade o suficiente para capturar uma Número de conta de 12 dígitos. 

ROB BOWDEN: OK. Então, os outros correram melhor. Então suponho que o banco impõe uma mensal $ 20 taxa de manutenção em todas as contas. Com que consulta SQL poderia o banco deduzir $ 20 a partir de cada contagem, mesmo se que resulta em alguns saldos negativos? Então, basicamente, há quatro principais tipos de consultas - inserir, selecionar, atualizar e excluir. Então, o que nós pensamos que somos vai usar aqui? Atualize. 

Então, vamos dar uma olhada. Então, aqui estamos atualizando. O quadro que estamos atualizando as contas? Então atualizando contas. E então a sintaxe diz, o que em contas estamos atualizando? Bem, nós estamos estabelecendo equilíbrio igual ao valor atual de equilíbrio menos 20. Então, isso vai atualizar todas as linhas de contas, subtraindo 20 $ a partir do equilíbrio. 

DAVID J. MALAN: Um erro comum aqui, mesmo que, por vezes, perdoou-o, era, na verdade, tem o código PHP aqui chamando a função de consulta ou colocar aspas em torno de tudo o que não precisa estar lá. 

ROB BOWDEN: Lembre-se que o MySQL é uma língua separada do PHP. Temos que ser escrito MySQL em PHP. E PHP é, então, enviá-lo para o servidor MySQL. Mas você não precisa de PHP, a fim de comunicar com um servidor MySQL. 

DAVID J. MALAN: Exatamente. Portanto, não variáveis ​​com cifrões deve ser, neste contexto. Ele só pode fazer toda a matemática dentro da própria base de dados. 

ROB BOWDEN: OK. Então a próxima. É este o próximo? É. Assim, com o que poderia consulta SQL do banco recuperar os números de contas de sua clientes mais ricos, aqueles com contrapesos maiores do que 1000? Assim que um dos quatro tipos principais vamos querer aqui? Selecione. Por isso, queremos selecionar. O que nós queremos para selecionar? Qual coluna que queremos selecionar? Vamos especificamente deseja para selecionar um número. Mas se você disse que estrela, nós também aceitou isso. 

Então, escolha o número a partir do que mesa? Contas. E então a condição que queremos? Onde equilíbrio maior que 1.000. Também aceito maior ou igual. Último. Com que consulta SQL poderia o banco próximo, ou seja, apagar todas as contas que tem um saldo de US $ 0? Então, qual dos quatro somos nós vai querer usar? Excluir. Assim, a sintaxe para isso? Excluir o quadro? Contas. E, em seguida, a condição na qual que deseja excluir - onde o equilíbrio é igual a zero. Então, excluir todas as linhas de contas onde o saldo é zero. Perguntas sobre qualquer um desses? Quer fila? 

DAVID J. MALAN: guia Fila. Então, em um presente, que lhe deu um pouco estrutura familiar que explorou uma bit em sala de aula ao lado de estruturas, que foi uma dados estrutura relacionada em espírito. A diferença, embora com uma fila é que tivemos que lembrar de alguma forma que estava na frente da fila, em grande parte para que pudéssemos fazer mais utilização eficiente da memória, pelo menos se estivéssemos usando um array. 

Porque recall, se temos uma matriz, se, por exemplo, esta é a frente fila, se eu entrar na fila aqui, e então alguém entra na fila atrás de mim, atrás de mim, atrás de mim, e uma pessoa sai de linha, você poderia, como já vimos alguns dos nossos humano voluntários em sala de aula, têm todos mudar esta maneira. Mas, em geral, depois de ter todos fazer algo não é o melhor uso do tempo em um programa, porque isso significa que o seu algoritmo está sendo executado no que tempo de execução assintótica? É linear. 

E eu sinto que esse é o tipo de estúpido. Se a próxima pessoa da fila é o próximo pessoa que deveria ir para o loja, eles não têm para mover em conjunto. Apenas deixe que a pessoa ser arranquei quando chegar a hora, por exemplo. Assim, podemos economizar um pouco de tempo lá. E assim, para fazer isso, porém, que os meios que o chefe de fila ou o frente da fila vai progressivamente se mover mais e mais na matriz e, eventualmente, pode realmente envolver em torno de se estamos usando um matriz para armazenar as pessoas nesta fila. Então você quase pode pensar no matriz como uma dados circular estrutura nesse sentido. 

Então, de alguma forma você tem que manter o controle do tamanho dele ou realmente o fim de tudo e, em seguida, onde o início do que é. Assim, propomos que você declarar um tal fila, a chamada ele q, apenas uma letra. Em seguida, propomos que a frente seja inicializado para zero, e que o tamanho ser inicializado para zero. 

Então, agora, não há nada dentro dessa fila. E pedimos-lhe para completar a implementação de enfileiramento abaixo em tal modo que a função adiciona n à a fim de q e, em seguida, devolve verdadeiro. Mas se q é completa ou negativa, o função deve retornar false vez. E deu-lhe um par de suposições. Mas eles não são realmente funcionais relevante, existe apenas que bool, porque, tecnicamente, bool não existem em C, a menos que você inclua um determinado arquivo de cabeçalho. Assim que acabou de se certificar de que não foram este é um truque questão tipo de coisa. 

Então, enfileiramento, propusemos na amostra As soluções para aplicação como se segue. Um, nós primeiro verificar a facilidade, os frutos baixo pendurado. Se a fila estiver cheia ou o número que você está tentando inserir é menor do que zero, o que dissemos no especificação do problema deve não ser permitido, porque nós só queremos valores não negativos, então você deve apenas return false imediatamente. Assim, alguns relativamente fácil verificação de erros. Se que você deseja adicionar que real número, você tinha que fazer um pouco de pensando aqui. E é aí que é um pouco chato mentalmente, porque você tem que descobrir como lidar com a envolvente. 

Mas o germe da idéia aqui é de interesse para nós é que a envolvente muitas vezes implica aritmética modular e o operador mod, o lado por cento, onde você pode ir de um valor maior de volta para zero e, em seguida, um e dois e três e, em seguida, de volta ao redor de zero, um e dois e três, e assim por diante uma e outra vez. Assim, a maneira propomos fazer isso é que queremos índice para a array chamado números onde nossos inteiros mentir. Mas para chegar lá, primeiro quero fazer seja qual for o tamanho da fila é mas em seguida, adicione a isso qualquer que seja a frente da lista é. E o efeito que é colocar-nos em a posição certa na fila e Não suponha que a primeira pessoa na linha é, no início, que ele ou ela absolutamente poderia ser se nós Também foram mudando todos. Mas estamos apenas a criação de trabalho para nós mesmos, se nós tomamos esse caminho particular. 

Assim, podemos mantê-lo relativamente simples. Nós temos que lembrar que nós só adicionado um int para a fila. E então nós apenas retornar true. Enquanto isso, em dequeue, pedimos que você faça o seguinte. Implementá-lo de tal forma que removida da fila, ou seja, remove e retorna, int na frente da fila. Para remover o int, basta esquecê-lo. Você não precisa substituir a sua parte. Então, ainda é realmente lá. Assim como os dados de um disco rígido, estamos apenas ignorando o fato de que agora é lá. E se q está vazia, devemos em vez retornar negativo 1. Então, este se sente arbitrária. Por que retornar negativo 1 em vez de falso? É. 

AUDIÊNCIA: Q está armazenando valores positivos. Desde que você só armazenar valores positivos no q, negativo é um erro. 

DAVID J. MALAN: OK, é verdade. Então porque nós só estamos armazenando positivo valores ou zero, então não há problema em retornar um valor negativo como uma sentinela valor, um símbolo especial. Mas você está reescrevendo a história lá, porque a razão estamos apenas retornando valores não negativos é porque queremos tem um valor de sentinela. Então, mais especificamente, porque não basta return false em caso de erro? É. 

AUDIÊNCIA: Você falhou para retornar um inteiro. 

DAVID J. MALAN: Exatamente. E é aí que fica C muito constrangedor. Se você está dizendo que você está indo para retornar um int, você tem para retornar um int. Você não pode começar a fantasia e começar a retornar um booleano ou um float ou um corda ou algo parecido. Agora, entretanto, JavaScript e PHP e algumas outras línguas pode, de fato, você retornar diferente tipos de valores. E isso pode ser realmente útil, onde você poderia retornar ints positivas, zeros, ints negativos ou falso ou nulo mesmo para significar erro. Mas não temos que versatilidade em C. 

Assim, com dequeue, o que propor a fazer é - 

ROB BOWDEN: Você pode retornar false. É só que falsa é de hash definir falso para zero. Então, se você retornar false, você está retornando zero. E zero é uma coisa válida na nossa fila, enquanto que um negativo não é se falsa passou a ser negativo 1. Mas você não deve mesmo precisa saber disso. 

DAVID J. MALAN: Isso é por isso que eu não disse isso. 

ROB BOWDEN: Mas não era verdade que você não pode retornar false. 

DAVID J. MALAN: Claro. Então dequeue, observe que aceitamos invalidar como seu argumento. E isso é porque não somos passar nada dentro Nós apenas queremos remover o elemento na parte da frente da fila. Então, como podemos fazer sobre isso? Bem, primeiro, vamos fazer isso verificação de sanidade rápida. Se o tamanho da fila é de 0, não há nenhum trabalho a ser feito. Retorno negativo 1. Concluído. Então, isso é algumas linhas de meu programa. Assim, apenas quatro linhas permanecem. 

Então, aqui eu decidir diminuir o tamanho. E diminuindo o tamanho eficaz significa que eu estou esquecendo algo está lá. Mas também tenho de atualizar onde a frente são os números. Então, para fazer isso, eu preciso fazer duas coisas. Eu primeiro preciso lembrar que o número está na frente da fila, porque eu preciso voltar aquela coisa. Então eu não quero esquecer acidentalmente sobre ele e, em seguida, substituí-lo. Eu só vou lembrar de um int. 

E agora, eu quero atualizar q.front ser q.front 1. Portanto, se esta foi a primeira pessoa em linha, agora, eu quero fazer mais 1 para apontar para a próxima pessoa na fila. Mas eu tenho que lidar com isso envolvente. E se a capacidade é uma constante global, que vai permitir-me para certificar-se como eu apontar para a última pessoa em linha, a operação do módulo irá trazer me de volta a zero no frente da fila. E que manipula a envolvente aqui. E então eu proceder para retornar n. 

Agora, a rigor, não o fiz tem que declarar n. Eu não tenho que agarrá-lo e armazená-lo temporariamente, porque o valor é ainda está lá. Então, eu poderia apenas fazer a aritmética direita para retornar o ex-chefe da fila. Mas eu senti que este era mais clara para realmente pegar o int, colocá-lo em n, e depois voltar que por uma questão de clareza, mas não estritamente necessário. Psst. Eles são todos pronunciável na minha cabeça. 

ROB BOWDEN: Então, primeira pergunta é o problema de árvore binária. Então, primeira pergunta é, nós somos dado a esses números. E queremos inseri-los de alguma forma em destes nós de modo a que ele é um válido árvore de busca binária. Então a única coisa a lembrar sobre árvores de busca binária é que ele não é só que a coisa para a esquerda é menor e a coisa a o direito é maior. Ele precisa ser que toda a árvore para esquerda é menor, e toda a árvore à direita é maior. 

Então, se eu colocar 34 aqui no topo, e depois Eu coloquei 20 aqui, então isso é válido para que agora, porque 34 por aqui. 20 vai para a esquerda. Então, isso é menos. Mas eu não posso então colocar 59 aqui, porque embora 59 está à direita, de 20, ele ainda está à esquerda do 34. Assim, com essa restrição em mente, o maneira mais fácil de resolver este provavelmente problema é apenas uma espécie destes números - então 20, 34, 36, 52, 59, 106. E, em seguida, insira-os da esquerda para a direita. 

Então 20 vai aqui. 34 vai aqui. 36 vai aqui. 52, 59, 106. E você também pode ter descoberto com alguns ligar e perceber, Oh, espere, eu não tenho números suficientes para preencher esta em mais aqui. Então eu preciso que meu reshift rota nota vai ser. Mas note que em três finais, se você lê da esquerda para a direita, é no ordem crescente. 

Então, agora, queremos declarar que a struct vai ser para o nós nesta árvore. Então o que precisamos em uma árvore binária? Portanto, temos um valor de tipo int, de modo algum valor int. Eu não sei o que chamamos -o na solução - int n. Precisamos de um ponteiro para o filho esquerdo e um ponteiro para o filho direito. Então ele vai ficar assim. E vai realmente olhar antes quando é que o duplamente vinculada lista coisas, então aviso - Eu vou ter que percorrer todo o caminho de volta para o problema 11. 

Então, observe que parece idêntica a esta, exceto que só acontecerá a chamar estes nomes diferentes. Nós ainda temos um número inteiro valor e dois ponteiros. É só que, em vez de tratar a ponteiros como apontar para a próxima coisa e do anterior, estamos tratando os ponteiros para apontar para um filho esquerdo e filho direito. OK. Então, esse é o nosso nó struct. E agora, a única função que precisamos implementar para isso é transversal, que queremos passar por cima da árvore, a impressão os valores da árvore de ordem. 

Então, olhando aqui, gostaríamos de imprimir a 20, 34, 36, 52, 59 e 106. Como é que vamos conseguir isso? Portanto, é bastante similar. Se você viu no exame passado o problema que você queria imprimir toda a árvore com vírgulas entre tudo, era, na verdade, até mesmo mais fácil do que isso. Então aqui está a solução. Isto era significativamente mais fácil se você fez isso de forma recursiva. Eu não sei se alguém tentou para fazê-lo de forma iterativa. 

Mas, primeiro, temos o nosso caso base. E se a raiz é nulo? Então, nós apenas estamos indo para retornar. Nós não queremos para imprimir qualquer coisa. Else vamos atravessar recursivamente para baixo. Imprima toda a subárvore esquerda. Então imprimir tudo menos que o meu valor atual. E então eu vou me imprimir. E então eu estou indo para a minha recursão toda subárvore direita, então tudo maior do que o meu valor. E isso vai imprimir tudo em ordem. Perguntas sobre como isso realmente realiza isso? 

AUDIÊNCIA: Eu tenho uma pergunta no [inaudível]. 

ROB BOWDEN: Portanto, uma forma de se aproximar qualquer problema recursivo é só pensar sobre ele gostar de você tem que pensar sobre todos os casos de canto. Por isso, considero que queremos imprimir esta árvore inteira. Então, todos nós estamos indo focalizar em é este nó específico - 36. As chamadas recursivas, nós fingimos aqueles apenas trabalhar. Então, aqui, esta chamada recursiva para transversal, que, sem sequer pensar sobre isso, apenas atravessando a esquerda três, imagine que já imprime 20 e 34 para nós. E então, quando finalmente, de forma recursiva chamar travessia sobre o direita, que irá imprimir corretamente 52, 59, e 106 para nós. 

Assim, dado que esta pode imprimir 20, 34, e o outro pode imprimir 52, 59, 108, tudo o que precisamos para ser capaz de fazer é imprimir nós mesmos, no meio disso. Então imprima tudo antes de nós. Imprimir a nós mesmos, de modo a impressão nó atual 36, printf regular, e, em seguida, imprimir tudo atrás de nós. 

DAVID J. MALAN: Este é o lugar onde a recursão fica muito bonito. É este salto incrível de fé, onde você faz um pouquinho de trabalho. E então você deixar alguém mais fazer o resto. E que outra pessoa é, ironicamente, você. Então, por graves brownie pontos, se se desloca para cima sobre as questões - 

ROB BOWDEN: Nas perguntas? 

DAVID J. MALAN: E um pouco para baixo para os números, alguém sabe onde esses números vêm? 

ROB BOWDEN: Eu tenho literalmente nenhuma idéia. 

DAVID J. MALAN: Eles aparecem durante todo o teste. 

AUDIÊNCIA: São eles os mesmos números? 

DAVID J. MALAN: Esses números. Um pouco de ovo de Páscoa. Portanto, para aqueles de vocês assistindo on-line em casa, se você pode nos dizer por e-mail para heads@CS50.net que o significado estes números são repetidos seis todo Teste 1, vamos lavá-lo com incrível atenção na final palestra e uma bola de stress. Nice, sutil. 

ROB Bowden: Qualquer últimas perguntas sobre qualquer coisa sobre o teste?