>> 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?