1 00:00:00,000 --> 00:00:12,610 2 00:00:12,610 --> 00:00:12,900 >> DAVID J. MALAN: Tudo bem. 3 00:00:12,900 --> 00:00:16,790 Então bem-vindo ao primeiro Postmortem CS50 para um quiz. 4 00:00:16,790 --> 00:00:18,340 Nós pensamos em inaugurar esta tradição este ano. 5 00:00:18,340 --> 00:00:20,960 E esta será uma oportunidade para percorrer o 6 00:00:20,960 --> 00:00:22,220 soluções para o problema. 7 00:00:22,220 --> 00:00:26,160 E nós vamos acelerar ou desacelerar base no interesse das pessoas aqui. 8 00:00:26,160 --> 00:00:29,730 >> Então, provavelmente você está aqui porque você é interessado em saber como você poderia ter ou 9 00:00:29,730 --> 00:00:31,170 deveria ter respondido a algumas destes problemas. 10 00:00:31,170 --> 00:00:33,300 Então por que não vamos dar uma olhada nesta seção em primeiro lugar? 11 00:00:33,300 --> 00:00:34,450 Então, ficando cordas. 12 00:00:34,450 --> 00:00:37,600 Isso lhe deu três versões diferentes de um programa que foi, em última análise, 13 00:00:37,600 --> 00:00:39,650 destina-se a obter uma seqüência de um usuário. 14 00:00:39,650 --> 00:00:42,530 Se é ou não fez isso era para a esquerda para que você possa determinar. 15 00:00:42,530 --> 00:00:45,150 >> E pedimos na Questão 0, supor que a versão 1 é 16 00:00:45,150 --> 00:00:46,400 compilado e executado. 17 00:00:46,400 --> 00:00:48,860 Por que o programa pode segfault? 18 00:00:48,860 --> 00:00:51,150 À primeira vista, todas as sugestões por que motivo? 19 00:00:51,150 --> 00:00:54,012 20 00:00:54,012 --> 00:00:54,489 É. 21 00:00:54,489 --> 00:00:59,260 >> AUDIÊNCIA: Então, eu lembro de ter visto isso em um exemplo anterior de olhar para o 22 00:00:59,260 --> 00:01:05,506 char * s e vendo a digitalização dos s e vendo porque é um ponteiro, como 23 00:01:05,506 --> 00:01:07,971 isso afetou o que você digitalizada? 24 00:01:07,971 --> 00:01:10,940 É S ou o endereço de s? 25 00:01:10,940 --> 00:01:11,180 >> DAVID J. MALAN: OK. 26 00:01:11,180 --> 00:01:11,480 Boa. 27 00:01:11,480 --> 00:01:14,830 Assim, em última análise, a origem de qualquer problema é, presumivelmente, vai reduzir 28 00:01:14,830 --> 00:01:16,210 para essa variável s. 29 00:01:16,210 --> 00:01:17,280 E é de fato uma variável. 30 00:01:17,280 --> 00:01:19,900 O tipo da variável de dados é char *, o que significa que vai 31 00:01:19,900 --> 00:01:22,570 conter o endereço de um personagem. 32 00:01:22,570 --> 00:01:23,850 E é aí que reside o insight. 33 00:01:23,850 --> 00:01:28,330 Vai conter o endereço de um personagem ou, mais geralmente, a 34 00:01:28,330 --> 00:01:32,110 endereço do primeiro caractere todo um bloco de caracteres. 35 00:01:32,110 --> 00:01:36,680 >> Mas o problema é que s digitalização, propósito na vida, é dado um endereço e dado 36 00:01:36,680 --> 00:01:40,960 um código de formato, como% s, leia uma corda para o pedaço de 37 00:01:40,960 --> 00:01:42,330 memória nesse endereço. 38 00:01:42,330 --> 00:01:46,040 Mas porque não há nenhum sinal de igual antes que no primeiro ponto e vírgula 39 00:01:46,040 --> 00:01:49,310 linha de código, porque na verdade não alocar qualquer memória com 40 00:01:49,310 --> 00:01:53,020 malloc, porque isso não aconteceu realmente alocar uma matriz de uma certa dimensão, todos 41 00:01:53,020 --> 00:01:57,620 você está fazendo está lendo o usuário do entrada de teclado em alguns completo 42 00:01:57,620 --> 00:02:00,490 valor de lixo, que está na s por padrão. 43 00:02:00,490 --> 00:02:04,480 Assim, as probabilidades são que você vai se segfault que o endereço não só assim acontecer 44 00:02:04,480 --> 00:02:08,009 para ser um valor que você pode, de fato, gravar. 45 00:02:08,009 --> 00:02:10,889 Tão ruim não atribuir sua memória lá. 46 00:02:10,889 --> 00:02:13,150 >> Então, na questão 1, pedimos, supor que a versão 2 é 47 00:02:13,150 --> 00:02:14,230 compilado e executado. 48 00:02:14,230 --> 00:02:15,900 Por que este programa pode segfault? 49 00:02:15,900 --> 00:02:17,990 Então, este é menos buggy. 50 00:02:17,990 --> 00:02:21,470 E há realmente apenas uma maneira óbvia, onde você pode 51 00:02:21,470 --> 00:02:22,810 desencadear um segfault aqui. 52 00:02:22,810 --> 00:02:23,730 E esta é temática. 53 00:02:23,730 --> 00:02:28,180 Toda vez que estamos usando c na memória, o que você poderia fazer para induzir um segfault 54 00:02:28,180 --> 00:02:30,718 com a versão 2? 55 00:02:30,718 --> 00:02:35,560 >> AUDIÊNCIA: Se você usar essa entrada em uma cadeia que é mais do que 49 56 00:02:35,560 --> 00:02:35,975 caracteres. 57 00:02:35,975 --> 00:02:37,260 >> DAVID J. MALAN: Exatamente. 58 00:02:37,260 --> 00:02:41,420 Toda vez que você ver algo fixo comprimento quando se trata de uma matriz, o seu 59 00:02:41,420 --> 00:02:44,650 radar deve ir fora que este poderia ser problemático se você não está verificando o 60 00:02:44,650 --> 00:02:45,810 limites de uma matriz. 61 00:02:45,810 --> 00:02:46,650 E esse é o problema aqui. 62 00:02:46,650 --> 00:02:47,910 Nós ainda estamos usando scanf. 63 00:02:47,910 --> 00:02:52,200 Nós ainda estamos usando% s, o que significa tentar para ler uma string do usuário. 64 00:02:52,200 --> 00:02:56,300 Isso vai ser lido em s, o que, neste ponto, é efectivamente o 65 00:02:56,300 --> 00:02:58,570 endereço de um bloco de memória ou equivalente. 66 00:02:58,570 --> 00:03:02,080 É o nome de um array de caracteres de memória. 67 00:03:02,080 --> 00:03:07,610 >> Mas exatamente isso, se você ler uma string isso é mais do que 49 caracteres, 49 68 00:03:07,610 --> 00:03:10,440 porque você precisa de espaço para a barra invertida 0, você vai transbordar 69 00:03:10,440 --> 00:03:11,390 que tampão. 70 00:03:11,390 --> 00:03:16,410 E você pode ter sorte e ser capaz de escrever um personagem 51, 52, 53. 71 00:03:16,410 --> 00:03:18,560 Mas em algum ponto, o SO vai dizer, não. 72 00:03:18,560 --> 00:03:21,270 Este definitivamente não é a memória você está autorizado a tocar. 73 00:03:21,270 --> 00:03:23,380 E o programa vai segfault. 74 00:03:23,380 --> 00:03:26,650 >> Portanto, há, a heurística deve haver qualquer tempo você tem comprimento fixo, você tem 75 00:03:26,650 --> 00:03:30,150 para se certificar de que você está verificando o comprimento de tudo o que você está tentando 76 00:03:30,150 --> 00:03:31,090 ler nele. 77 00:03:31,090 --> 00:03:35,110 >> AUDIÊNCIA: Então para resolver isso, você pode tiveram uma declaração verificando realmente 78 00:03:35,110 --> 00:03:37,140 é o maior comprimento ou inferior a? 79 00:03:37,140 --> 00:03:37,730 >> DAVID J. MALAN: Absolutamente. 80 00:03:37,730 --> 00:03:41,706 Você só tem uma condição que diz que, se o - 81 00:03:41,706 --> 00:03:46,080 ou melhor, você não precisa necessariamente saber com antecedência quantos caracteres a 82 00:03:46,080 --> 00:03:49,060 usuário vai digitar, porque você tem ovo e da galinha. 83 00:03:49,060 --> 00:03:51,860 Não até que você lê-lo com scanf você pode descobrir quanto tempo é. 84 00:03:51,860 --> 00:03:54,500 Mas nesse ponto, já é tarde demais, porque você já leu em 85 00:03:54,500 --> 00:03:55,710 algum bloco de memória. 86 00:03:55,710 --> 00:03:59,590 Então, como um aparte, os evita biblioteca CS50 esta questão por completo, recordação 87 00:03:59,590 --> 00:04:01,060 usando fgetc. 88 00:04:01,060 --> 00:04:05,390 E ele lê um caractere de cada vez, junto, sabendo-virando dica que você 89 00:04:05,390 --> 00:04:08,060 Não pode transbordar um personagem se você ler um de cada vez. 90 00:04:08,060 --> 00:04:11,580 >> O problema é com a recordação é getstring que temos que constantemente re-size 91 00:04:11,580 --> 00:04:13,590 que pedaço de memória, o que é apenas uma dor. 92 00:04:13,590 --> 00:04:15,310 É um monte de linhas de código para fazer isso. 93 00:04:15,310 --> 00:04:18,779 Assim, uma outra abordagem seria a na verdade utilizar um primo, de modo 94 00:04:18,779 --> 00:04:19,790 dizer, de scanf. 95 00:04:19,790 --> 00:04:22,820 Existem variantes de um monte deles funções que realmente verificar o 96 00:04:22,820 --> 00:04:25,870 comprimento de quantos caracteres que você pode ler no máximo. 97 00:04:25,870 --> 00:04:29,430 E você pode especificar, não leia mais de 50 caracteres. 98 00:04:29,430 --> 00:04:34,110 De modo que seria uma outra abordagem, mas menos que acomodam de entradas maiores. 99 00:04:34,110 --> 00:04:37,040 >> Então pergunta 2 pergunta, suponha que a versão 3 é compilado e executado. 100 00:04:37,040 --> 00:04:39,960 Por que esse programa pode segfault? 101 00:04:39,960 --> 00:04:42,650 Então, este é realmente o mesmo responder, apesar 102 00:04:42,650 --> 00:04:43,590 parece um pouco amador. 103 00:04:43,590 --> 00:04:46,440 Estamos usando malloc, que se sente como estamos nos dando mais opções. 104 00:04:46,440 --> 00:04:48,030 E então nós estamos liberando que memória no final. 105 00:04:48,030 --> 00:04:49,580 Ainda é apenas 50 bytes de memória. 106 00:04:49,580 --> 00:04:53,620 Assim, poderíamos ainda tentar ler em 51, 52, 1000 bytes. 107 00:04:53,620 --> 00:04:55,830 Vai para segfault exatamente pelo mesmo motivo. 108 00:04:55,830 --> 00:04:57,530 >> Mas há outra razão. 109 00:04:57,530 --> 00:05:03,890 O que mais poderia malloc retorno além o endereço de um bloco de memória? 110 00:05:03,890 --> 00:05:04,920 Poderia retornar nulo. 111 00:05:04,920 --> 00:05:07,560 E porque não estamos verificando que, poderíamos estar fazendo algo 112 00:05:07,560 --> 00:05:11,350 estúpido por outra razão, o que é que poderíamos estar dizendo scanf, leia 113 00:05:11,350 --> 00:05:16,050 a entrada do usuário a partir do teclado em 0 local, AKA nulo. 114 00:05:16,050 --> 00:05:18,890 E que, também, será definitivamente desencadear um segfault. 115 00:05:18,890 --> 00:05:21,590 Assim, para o propósito do teste, teríamos ter aceitado um desses como um 116 00:05:21,590 --> 00:05:22,740 razão válida. 117 00:05:22,740 --> 00:05:23,420 Uma é idêntica. 118 00:05:23,420 --> 00:05:25,720 Um deles é um pouco mais sutil. 119 00:05:25,720 --> 00:05:28,975 >> Por fim, no que diz respeito ao programa de uso de memória, como é que a versão 2 e 120 00:05:28,975 --> 00:05:30,350 versão 3 diferem? 121 00:05:30,350 --> 00:05:35,070 Assim, por que vale a pena, vimos um oferta aparentemente infinita de possível 122 00:05:35,070 --> 00:05:35,770 respostas a esta. 123 00:05:35,770 --> 00:05:39,300 E entre as respostas das pessoas, o que nós éramos esperando, mas aceitamos outras 124 00:05:39,300 --> 00:05:42,250 coisas, era uma menção ao fato de que a versão 2 é utilizar 125 00:05:42,250 --> 00:05:44,560 a pilha de chamada. 126 00:05:44,560 --> 00:05:46,710 Versão 3 está usando o heap. 127 00:05:46,710 --> 00:05:50,060 E funcionalmente, isso realmente não fazer tudo o que muita diferença. 128 00:05:50,060 --> 00:05:54,040 No final do dia, ainda estamos ficando 50 bytes de memória. 129 00:05:54,040 --> 00:05:56,640 >> Mas isso era uma das possíveis respostas que estávamos olhando. 130 00:05:56,640 --> 00:05:59,730 Mas você vai ver, como você começa o seu quizzes volta do TF, que fizemos 131 00:05:59,730 --> 00:06:04,330 aceitar outras discussões sobre a sua usos diferentes de memória também. 132 00:06:04,330 --> 00:06:08,600 Mas pilha e pilha teria sido uma resposta fácil para ir com ele. 133 00:06:08,600 --> 00:06:11,150 Alguma pergunta? 134 00:06:11,150 --> 00:06:12,400 Eu dar-lhe Rob. 135 00:06:12,400 --> 00:06:18,360 136 00:06:18,360 --> 00:06:20,210 >> ROB BOWDEN: Então problema 4. 137 00:06:20,210 --> 00:06:21,985 Esta é a única em que você tinha que preencher o número de bytes de todos 138 00:06:21,985 --> 00:06:23,460 estes tipos diferentes utilizados. 139 00:06:23,460 --> 00:06:24,830 Então a primeira coisa que vemos. 140 00:06:24,830 --> 00:06:27,930 Suponha uma arquitetura de 32 bits, como este aparelho CS50. 141 00:06:27,930 --> 00:06:33,530 Então, uma das coisas fundamentais sobre Arquiteturas de 32 bits, que nos diz 142 00:06:33,530 --> 00:06:37,490 exatamente como um grande ponteiro vai estar na arquitectura. 143 00:06:37,490 --> 00:06:43,020 >> Então, imediatamente, sabemos que qualquer ponteiro tipo é de 32-bits ou 4 bytes. 144 00:06:43,020 --> 00:06:46,010 Então, olhando para esta tabela, uma nó * é um tipo de ponteiro. 145 00:06:46,010 --> 00:06:47,250 Isso vai ser de 4 bytes. 146 00:06:47,250 --> 00:06:51,640 Nó struct *, isso é literalmente idêntica à estrela nó. 147 00:06:51,640 --> 00:06:53,590 E assim que vai ser de 4 bytes. 148 00:06:53,590 --> 00:06:58,270 String, por isso não se parece com um ponteiro ainda, mas o typedef, um 149 00:06:58,270 --> 00:07:01,590 string é apenas um char *, que é um tipo de ponteiro. 150 00:07:01,590 --> 00:07:03,550 Então, isso vai ser de 4 bytes. 151 00:07:03,550 --> 00:07:06,150 >> Então, esses três são os 4 bytes. 152 00:07:06,150 --> 00:07:09,350 Agora, nó e aluno são um pouco mais complicado. 153 00:07:09,350 --> 00:07:15,160 Então, olhando para nós e aluno, vemos nó como um inteiro e um ponteiro. 154 00:07:15,160 --> 00:07:18,050 E estudante é de dois ponteiros no interior do mesmo. 155 00:07:18,050 --> 00:07:23,340 Assim, pelo menos para o nosso caso aqui, a forma como que acabamos o cálculo do tamanho da 156 00:07:23,340 --> 00:07:27,020 esta estrutura é apenas somar tudo que está dentro da estrutura. 157 00:07:27,020 --> 00:07:30,690 >> Então, para nós, temos um número inteiro, que é de 4 bytes. 158 00:07:30,690 --> 00:07:32,830 Nós temos um ponteiro, que é de 4 bytes. 159 00:07:32,830 --> 00:07:35,820 E assim, um nó está acontecendo para ocupar 8 bytes. 160 00:07:35,820 --> 00:07:39,490 E da mesma forma para o aluno, temos um ponteiro que é 4 bytes e outro 161 00:07:39,490 --> 00:07:40,770 ponteiro que é 4 bytes. 162 00:07:40,770 --> 00:07:43,180 Então isso vai acabar sendo 8 bytes. 163 00:07:43,180 --> 00:07:45,480 Então nó e aluno são 8 bytes. 164 00:07:45,480 --> 00:07:48,950 E estes três são todos os 4 bytes. 165 00:07:48,950 --> 00:07:50,240 Perguntas sobre isso? 166 00:07:50,240 --> 00:07:54,640 167 00:07:54,640 --> 00:07:54,990 Sim. 168 00:07:54,990 --> 00:07:58,413 >> AUDIÊNCIA: É que era um 64-bit arquitetura, que seria 169 00:07:58,413 --> 00:07:59,880 dobrar todos eles? 170 00:07:59,880 --> 00:08:01,790 >> ROB BOWDEN: Não seria dobrar todos eles. 171 00:08:01,790 --> 00:08:05,830 Assim, a arquitetura de 64 bits, ele, mais uma vez, mudanças que coisa fundamental que a 172 00:08:05,830 --> 00:08:08,910 ponteiro é agora 64 bits. 173 00:08:08,910 --> 00:08:09,290 É. 174 00:08:09,290 --> 00:08:10,930 Assim, um ponteiro é de 8 bytes. 175 00:08:10,930 --> 00:08:15,420 Então, esses que foram 4 bytes vão ser 8 bytes. 176 00:08:15,420 --> 00:08:18,617 Um estudante, que era dois ponteiros, bem, agora ele vai 177 00:08:18,617 --> 00:08:19,800 ser de 8 bytes, 8 bytes. 178 00:08:19,800 --> 00:08:21,980 Vai fazer 16 bytes. 179 00:08:21,980 --> 00:08:25,710 >> Mas um nó ainda é de 4 bytes. 180 00:08:25,710 --> 00:08:27,800 Portanto, este ponteiro vai para ser de 8 bytes. 181 00:08:27,800 --> 00:08:28,930 Este é 4 bytes. 182 00:08:28,930 --> 00:08:30,870 Assim, um nó está indo só ser de 12 bytes. 183 00:08:30,870 --> 00:08:36,309 184 00:08:36,309 --> 00:08:39,280 Quaisquer outras perguntas sobre esse? 185 00:08:39,280 --> 00:08:44,500 Então o próximo, estes são os códigos de status HTTP. 186 00:08:44,500 --> 00:08:48,000 E você tinha que descrever as circunstâncias nos termos do qual estes puderam 187 00:08:48,000 --> 00:08:49,810 ser devolvido a você. 188 00:08:49,810 --> 00:08:56,730 um problema que eu ouvi alguns alunos tenho é que eles tentaram fazer o 189 00:08:56,730 --> 00:08:58,950 erros de estar no final do cliente. 190 00:08:58,950 --> 00:09:02,320 Então, quando nós tentamos fazer o pedido para o servidor, algo correr 191 00:09:02,320 --> 00:09:03,820 errado em nosso fim. 192 00:09:03,820 --> 00:09:07,660 Mas, geralmente, esses códigos são sendo devolvido pelo servidor. 193 00:09:07,660 --> 00:09:11,720 Então, nós queremos descobrir o que está acontecendo certo ou errado no servidor que 194 00:09:11,720 --> 00:09:14,280 faz com que essas coisas a serem devolvidos. 195 00:09:14,280 --> 00:09:18,670 Então, Por que um servidor retorna código de status 200? 196 00:09:18,670 --> 00:09:19,920 Quaisquer pensamentos? 197 00:09:19,920 --> 00:09:23,360 198 00:09:23,360 --> 00:09:23,730 >> É. 199 00:09:23,730 --> 00:09:27,850 Então, alguma coisa sobre sucesso a solicitação passou. 200 00:09:27,850 --> 00:09:30,260 E eles são capazes de retornar tudo o que você pediu. 201 00:09:30,260 --> 00:09:32,240 Então, tudo estava bem. 202 00:09:32,240 --> 00:09:35,662 E sobre 302 encontrados? 203 00:09:35,662 --> 00:09:36,618 É. 204 00:09:36,618 --> 00:09:39,008 >> AUDIÊNCIA: O servidor estava à procura para o que você pediu. 205 00:09:39,008 --> 00:09:40,442 Mas não conseguiu encontrá-lo. 206 00:09:40,442 --> 00:09:42,850 Portanto, há um erro. 207 00:09:42,850 --> 00:09:47,720 >> ROB BOWDEN: Então, o servidor foi olhando para o que você queria. 208 00:09:47,720 --> 00:09:51,682 Então, só de olhar aqui, 302 encontrados, ele foi capaz de encontrá-lo. 209 00:09:51,682 --> 00:09:53,035 >> AUDIÊNCIA: Eu sinto muito. 210 00:09:53,035 --> 00:09:54,388 Encontrado significa que eles fizeram encontrá-lo. 211 00:09:54,388 --> 00:09:55,638 Desculpe. 212 00:09:55,638 --> 00:09:58,120 213 00:09:58,120 --> 00:10:00,160 >> ROB BOWDEN: Então 302 encontrado. 214 00:10:00,160 --> 00:10:02,350 O servidor é capaz de encontrar o que você queria. 215 00:10:02,350 --> 00:10:04,640 >> AUDIÊNCIA: Mas não é exibi-lo? 216 00:10:04,640 --> 00:10:08,180 >> ROB BOWDEN: A diferença entre esta 302 e 200 é que ela 217 00:10:08,180 --> 00:10:09,280 sabe o que você quer. 218 00:10:09,280 --> 00:10:12,000 Mas não é exatamente onde você queria perguntar. 219 00:10:12,000 --> 00:10:14,580 Assim, 302 é um redirecionamento típico. 220 00:10:14,580 --> 00:10:16,510 Assim que você solicitou uma página. 221 00:10:16,510 --> 00:10:19,590 Ele sabe, oh, eu quero para devolver-lhe isto. 222 00:10:19,590 --> 00:10:21,070 Mas isso é em uma URL diferente. 223 00:10:21,070 --> 00:10:23,534 Então, hey, você realmente quer isso. 224 00:10:23,534 --> 00:10:26,950 >> DAVID J. MALAN: É uma peça que disse que demos vocês um redirecionamento 225 00:10:26,950 --> 00:10:30,830 função que usei a função cabeçalho que, por sua vez, impresso local, 226 00:10:30,830 --> 00:10:34,110 cólon, e, em seguida, o URL para o qual pretender rejeitar o usuário. 227 00:10:34,110 --> 00:10:37,480 Mesmo que você não viu 302 explicitamente lá, que é o que o PHP 228 00:10:37,480 --> 00:10:41,550 magicamente inserir como o cabeçalho dizendo exatamente o que Rob disse que não - 229 00:10:41,550 --> 00:10:41,930 encontrado. 230 00:10:41,930 --> 00:10:43,180 Mas aqui em vez. 231 00:10:43,180 --> 00:10:45,960 232 00:10:45,960 --> 00:10:46,160 >> ROB BOWDEN: OK. 233 00:10:46,160 --> 00:10:47,630 Assim que sobre 403 proibido? 234 00:10:47,630 --> 00:10:52,240 235 00:10:52,240 --> 00:10:57,120 >> AUDIÊNCIA: Eu acho que é que o servidor é, basicamente, dizendo que o cliente 236 00:10:57,120 --> 00:10:59,970 não pode acessar a home page. 237 00:10:59,970 --> 00:11:03,260 >> ROB BOWDEN: Então, sim. 238 00:11:03,260 --> 00:11:07,670 Bem, a resposta típica que foram esperando algo como, os arquivos 239 00:11:07,670 --> 00:11:08,920 não são chmodded apropriadamente. 240 00:11:08,920 --> 00:11:11,590 Isso provavelmente é em que circunstâncias você viu. 241 00:11:11,590 --> 00:11:18,920 Mas há uma razão para que o cliente poderia ser em falta aqui. 242 00:11:18,920 --> 00:11:20,440 Na verdade, há um outro código de status - 243 00:11:20,440 --> 00:11:21,210 401. 244 00:11:21,210 --> 00:11:22,820 Então, essas são muito semelhantes. 245 00:11:22,820 --> 00:11:24,590 >> 401 não é autorizado. 246 00:11:24,590 --> 00:11:26,130 E 403 é proibido. 247 00:11:26,130 --> 00:11:31,890 E assim não autorizada você exclusivamente obter, se você não está logado pol 248 00:11:31,890 --> 00:11:34,520 Mas o login pode significar que está autorizado. 249 00:11:34,520 --> 00:11:37,930 Mas se você já está conectado e você ainda não tem permissão, em seguida, 250 00:11:37,930 --> 00:11:40,140 você também pode obter proibido. 251 00:11:40,140 --> 00:11:45,320 Então, se você está logado e não têm permissão, também é proibido 252 00:11:45,320 --> 00:11:47,164 algo que você pode começar. 253 00:11:47,164 --> 00:11:48,900 >> DAVID J. MALAN: E o mecanismo pelo que estes problemas são normalmente 254 00:11:48,900 --> 00:11:53,100 resolvido no servidor é via o comando? 255 00:11:53,100 --> 00:11:57,700 Chmod, se é, realmente, uma permissões emitir no arquivo ou diretório. 256 00:11:57,700 --> 00:11:59,220 >> ROB BOWDEN: Então 404 não encontrado. 257 00:11:59,220 --> 00:12:03,100 258 00:12:03,100 --> 00:12:03,470 É. 259 00:12:03,470 --> 00:12:10,150 Portanto, ao contrário 302 onde não era exatamente onde você está pedindo, mas ele sabe o que 260 00:12:10,150 --> 00:12:12,710 você quer, isso, ele só tem idéia do que você quer. 261 00:12:12,710 --> 00:12:15,648 E você não está solicitando algo válido. 262 00:12:15,648 --> 00:12:18,580 263 00:12:18,580 --> 00:12:22,310 418 Eu sou um bule de chá e, em seguida, 500 servidor interno. 264 00:12:22,310 --> 00:12:24,870 Então, por que você pode ter isso? 265 00:12:24,870 --> 00:12:26,120 >> Então segfault - 266 00:12:26,120 --> 00:12:28,760 267 00:12:28,760 --> 00:12:30,640 Na verdade, eu não sei a classificação padrão para este. 268 00:12:30,640 --> 00:12:34,850 Mas se o seu código PHP tinha algo de errado nisso, em teoria, poderia 269 00:12:34,850 --> 00:12:39,650 realmente segfault, caso em que, este 500 erro interno do servidor, algo 270 00:12:39,650 --> 00:12:41,400 está errado com seu servidor de configuração. 271 00:12:41,400 --> 00:12:44,320 Ou há um erro de sintaxe em seu código PHP. 272 00:12:44,320 --> 00:12:46,095 Ou algo de ruim está acontecendo. 273 00:12:46,095 --> 00:12:48,320 >> DAVID J. MALAN: Fizemos ver segfault entre as respostas de algumas das pessoas. 274 00:12:48,320 --> 00:12:49,490 E, tecnicamente, isso poderia acontecer. 275 00:12:49,490 --> 00:12:53,820 Mas isso seria um PHP, o programa escrito por outras pessoas, na verdade, 276 00:12:53,820 --> 00:12:57,790 segfaulted, que só se essas pessoas asneira e escreveu código buggy 277 00:12:57,790 --> 00:13:00,680 seu intérprete faria Próprio PHP segfault. 278 00:13:00,680 --> 00:13:06,460 Assim, mesmo que 500 é como um segfault em espírito, é quase sempre a 279 00:13:06,460 --> 00:13:10,490 resultado de um problema de arquivo de configuração com o seu servidor web ou, como disse Rob, 280 00:13:10,490 --> 00:13:13,200 um erro de sintaxe, como você não fechar uma cotação. 281 00:13:13,200 --> 00:13:16,180 Ou você perdeu um ponto e vírgula em algum lugar. 282 00:13:16,180 --> 00:13:23,677 >> AUDIÊNCIA: Assim, para o pset Shuttle, I acho que quando eu fiz isso uma vez eu cliquei no 283 00:13:23,677 --> 00:13:26,300 navegador, mas nada veio à tona, o que eles chamaram página branca. 284 00:13:26,300 --> 00:13:28,056 Mas foi por causa do código. 285 00:13:28,056 --> 00:13:29,440 Acho que foi JavaScript, certo? 286 00:13:29,440 --> 00:13:29,770 >> ROB BOWDEN: Yeah. 287 00:13:29,770 --> 00:13:31,180 >> AUDIÊNCIA: Será que o erro ainda subir? 288 00:13:31,180 --> 00:13:34,290 >> ROB BOWDEN: Então você não teria chegado este erro, porque tudo 289 00:13:34,290 --> 00:13:36,930 do ponto de vista do servidor web estava completamente bem. 290 00:13:36,930 --> 00:13:39,090 Mas você pediu index.html. 291 00:13:39,090 --> 00:13:42,000 Você solicitou shuttle.js e service.js. 292 00:13:42,000 --> 00:13:44,580 E foi capaz de retornar com sucesso a você todas essas coisas - 293 00:13:44,580 --> 00:13:44,980 200. 294 00:13:44,980 --> 00:13:45,680 OK. 295 00:13:45,680 --> 00:13:49,330 É só quando o navegador tentou interpretar o código JavaScript que 296 00:13:49,330 --> 00:13:51,370 é como, espere, isso não é erro de JavaScript válido. 297 00:13:51,370 --> 00:13:55,720 298 00:13:55,720 --> 00:13:58,210 Alguma outra pergunta? 299 00:13:58,210 --> 00:14:00,750 Tudo bem. 300 00:14:00,750 --> 00:14:04,120 >> DAVID J. MALAN: Então da próxima se era o número 11. 301 00:14:04,120 --> 00:14:07,610 E 11 foi o mais assustador para um monte de pessoas. 302 00:14:07,610 --> 00:14:14,620 303 00:14:14,620 --> 00:14:18,570 Então, a coisa mais importante a notar aqui era que este era, de fato, sobre 304 00:14:18,570 --> 00:14:19,840 uma lista duplamente vinculada. 305 00:14:19,840 --> 00:14:23,160 Mas este não era o mesmo que o do ano passado problema lista duplamente ligada, 306 00:14:23,160 --> 00:14:27,170 o que não dar-lhe a ressalva de que a lista poderia, de fato, ser indiferenciados. 307 00:14:27,170 --> 00:14:29,640 >> Assim, o fato de que a lista foi indiferenciados eo fato de que essa palavra era 308 00:14:29,640 --> 00:14:32,930 sublinhado não estava destinado a transmitir que esta é realmente uma simplificação 309 00:14:32,930 --> 00:14:35,430 do que de outra forma teria sido um problema mais desafiador 310 00:14:35,430 --> 00:14:36,600 e um mais longo. 311 00:14:36,600 --> 00:14:40,760 Assim, um erro comum aqui foi ter colocado solução do ano passado sobre o seu um 312 00:14:40,760 --> 00:14:45,580 pager e depois é só copiar cegamente que para baixo como a resposta, que é o direito 313 00:14:45,580 --> 00:14:48,520 responder a uma pergunta diferente semelhante em espírito. 314 00:14:48,520 --> 00:14:51,340 Mas as sutilezas aqui foram como se segue. 315 00:14:51,340 --> 00:14:55,200 >> Então, um, temos um nó declarado e definido da maneira usual aqui. 316 00:14:55,200 --> 00:14:59,230 Em seguida, definimos lista de ser um mundial ponteiro inicializado como nulo. 317 00:14:59,230 --> 00:15:02,150 Então, aparentemente, há duas funções temos protótipos para aqui, inserção 318 00:15:02,150 --> 00:15:03,240 e remover. 319 00:15:03,240 --> 00:15:06,600 E então nós temos um código de exemplo aqui de fazer um monte de inserções. 320 00:15:06,600 --> 00:15:09,930 E, então, pedir-lhe para completar a implementação de inserção abaixo de tal 321 00:15:09,930 --> 00:15:14,380 uma maneira que ele insere n na lista em tempo constante, também salientou, 322 00:15:14,380 --> 00:15:15,730 mesmo que já está presente. 323 00:15:15,730 --> 00:15:20,600 >> Assim, a beleza de ser capaz de inserir na constante de tempo é que ela implica 324 00:15:20,600 --> 00:15:23,060 que você tem que inserir o novo nó de onde? 325 00:15:23,060 --> 00:15:23,690 Na parte da frente. 326 00:15:23,690 --> 00:15:27,760 Assim, ele elimina, felizmente, pelo menos um dos casos que costumavam exigir 327 00:15:27,760 --> 00:15:30,520 ainda mais linhas de código, como o fez no ano passado, e até mesmo na sala de aula quando 328 00:15:30,520 --> 00:15:34,040 Conversamos por esse tipo de coisa com os seres humanos e com alguns 329 00:15:34,040 --> 00:15:35,250 pseudo código verbal. 330 00:15:35,250 --> 00:15:39,190 Assim, na solução aqui, vamos pular para que apenas para ter um em visuais 331 00:15:39,190 --> 00:15:40,480 a tela. 332 00:15:40,480 --> 00:15:42,230 >> Observe que nós estamos fazendo o seguinte. 333 00:15:42,230 --> 00:15:45,140 E também perceber a outra simplificação foi a de que, mesmo que seja 334 00:15:45,140 --> 00:15:48,280 já está presente, então isso significa que, mesmo se o número já está lá, você pode 335 00:15:48,280 --> 00:15:50,280 cegamente inserir outro cópia do mesmo. 336 00:15:50,280 --> 00:15:52,560 E que, também, foi concebido para ser um simplificação, de modo que você poderia 337 00:15:52,560 --> 00:15:54,940 focar, na verdade, alguns dos mais parte intelectualmente interessante e 338 00:15:54,940 --> 00:15:58,090 não apenas alguns erro adicional verificação dado o tempo limitado. 339 00:15:58,090 --> 00:16:02,880 >> Assim, nesta solução de amostra, alocamos um ponteiro na mão esquerda 340 00:16:02,880 --> 00:16:04,510 lado aqui a um nó. 341 00:16:04,510 --> 00:16:07,190 Agora, percebo que ponteiro, como Rob disse, é de apenas 32 bits. 342 00:16:07,190 --> 00:16:09,060 E ele realmente não contêm um endereço até que você 343 00:16:09,060 --> 00:16:09,970 atribuir-lhe o endereço. 344 00:16:09,970 --> 00:16:13,220 E fazemos isso na mão direita lado via malloc. 345 00:16:13,220 --> 00:16:16,550 Como um bom cidadão, verificamos que malloc não é, na verdade, nula, de modo que 346 00:16:16,550 --> 00:16:18,690 não criar acidentalmente um segfault aqui. 347 00:16:18,690 --> 00:16:22,840 E cada vez que você usa malloc na vida, você deve ser a verificação de nulo, para que não 348 00:16:22,840 --> 00:16:24,090 você tem um bug sutil. 349 00:16:24,090 --> 00:16:28,460 >> Então nós inicializar que nula por atribuição de n e anterior e seguinte. 350 00:16:28,460 --> 00:16:32,450 E, neste caso aqui, eu inicializado anterior ao nulo, porque este novo 351 00:16:32,450 --> 00:16:34,780 nó vai ser o novo começando da minha lista. 352 00:16:34,780 --> 00:16:37,050 Portanto, não vai ser nada antes dele. 353 00:16:37,050 --> 00:16:42,010 E quero acrescentar, essencialmente, o lista existente para o novo nó 354 00:16:42,010 --> 00:16:44,700 assentada perto igual à lista em si. 355 00:16:44,700 --> 00:16:47,120 Mas eu não acabei ainda. 356 00:16:47,120 --> 00:16:51,780 Então, se a própria lista já existia, e houve pelo menos um nó 357 00:16:51,780 --> 00:16:57,070 já em vigor, se esta é a lista aqui e eu inserir um novo nó aqui, eu 358 00:16:57,070 --> 00:17:01,840 precisa ter certeza de que o meu ex-nó aponta para trás, para o meu novo nó, 359 00:17:01,840 --> 00:17:04,260 porque esta é, de novo, uma lista duplamente vinculada. 360 00:17:04,260 --> 00:17:05,460 >> Então, fazemos um teste de sanidade. 361 00:17:05,460 --> 00:17:10,109 Se a lista não for nulo, se já existe um ou mais nós de lá, então 362 00:17:10,109 --> 00:17:12,470 acrescentar que volta de referência, por assim dizer. 363 00:17:12,470 --> 00:17:15,420 E então a última coisa que precisamos fazer é realmente atualizar o mundial 364 00:17:15,420 --> 00:17:20,329 lista de variáveis-se a apontar para que o novo nó. 365 00:17:20,329 --> 00:17:21,790 É. 366 00:17:21,790 --> 00:17:26,579 >> AUDIÊNCIA: Na seta de ponteiro [Inaudível] é igual a nulo, faz isso 367 00:17:26,579 --> 00:17:30,420 lidar com a lista porque a lista é nulo? 368 00:17:30,420 --> 00:17:30,596 >> DAVID J. MALAN: Nope. 369 00:17:30,596 --> 00:17:34,500 Isso é simplesmente ser eu proativamente cuidadoso, em que, se esta é a minha 370 00:17:34,500 --> 00:17:38,730 lista original com talvez alguns mais nós por aqui e eu estou inserindo meu 371 00:17:38,730 --> 00:17:42,380 novo nó aqui, não vai ser nada por aqui. 372 00:17:42,380 --> 00:17:44,720 E eu quero capturar essa idéia definindo anterior para 373 00:17:44,720 --> 00:17:47,740 nulo no novo nó. 374 00:17:47,740 --> 00:17:51,410 E, presumivelmente, se meu código está correto e não há nenhuma outra maneira de inserir 375 00:17:51,410 --> 00:17:54,970 para além desta função, nós presumivelmente, mesmo que a lista já tem 376 00:17:54,970 --> 00:18:00,090 um ou mais nós em que, presumivelmente, o lista, o primeiro nó, teria um 377 00:18:00,090 --> 00:18:02,750 ponteiro anterior da própria nula. 378 00:18:02,750 --> 00:18:03,550 >> AUDIÊNCIA: E apenas um follow-up. 379 00:18:03,550 --> 00:18:08,139 A razão pela qual você coloca ponteiro próximos iguais lista é que você está fazendo com que o ponteiro 380 00:18:08,139 --> 00:18:13,579 antes lista em que ele está apontando para o outro, eu acho - 381 00:18:13,579 --> 00:18:14,980 Eu não - 382 00:18:14,980 --> 00:18:15,450 apenas lista? 383 00:18:15,450 --> 00:18:16,400 >> DAVID J. MALAN: Exatamente. 384 00:18:16,400 --> 00:18:19,400 E assim vamos realmente considerar dois casos aqui realmente, mesmo que o 385 00:18:19,400 --> 00:18:22,070 ordem, vamos considerá-los não é exactamente o mesmo que o código. 386 00:18:22,070 --> 00:18:26,250 Mas em um nível alto, se isso representa lista e este é um 32-bit 387 00:18:26,250 --> 00:18:29,560 ponteiro, o cenário mais simples é que este é nulo por padrão. 388 00:18:29,560 --> 00:18:33,010 E suponha que eu quero inserir o número 50 foi o primeiro número. 389 00:18:33,010 --> 00:18:37,640 Então, eu estou indo para ir em frente e alocar um nó, que vai conter 390 00:18:37,640 --> 00:18:38,770 três campos - 391 00:18:38,770 --> 00:18:42,070 n, anterior e seguinte. 392 00:18:42,070 --> 00:18:44,580 >> Eu vou colocar o número 50 aqui, porque isso vai ser n. 393 00:18:44,580 --> 00:18:46,130 Este será o próximo. 394 00:18:46,130 --> 00:18:48,530 E isso vai ser anterior. 395 00:18:48,530 --> 00:18:50,910 E então o que posso fazer neste caso? 396 00:18:50,910 --> 00:18:53,900 Bem, eu tenho apenas a linha 1 feito aqui. 397 00:18:53,900 --> 00:18:55,400 Pointer n fica n. 398 00:18:55,400 --> 00:18:57,740 Eu estou dizendo, então, anterior deve obter nulo. 399 00:18:57,740 --> 00:18:59,470 Então isso vai ser nulo. 400 00:18:59,470 --> 00:19:01,365 Então eu vou dizer a seguir vai ficar lista. 401 00:19:01,365 --> 00:19:05,150 >> E isso só funciona bem. 402 00:19:05,150 --> 00:19:06,500 Este é nulo. 403 00:19:06,500 --> 00:19:10,620 E assim que eu estou dizendo, o novo nó do próximo campo deve conseguir tudo o que é isso. 404 00:19:10,620 --> 00:19:12,570 Assim que coloca outro nulo lá. 405 00:19:12,570 --> 00:19:14,510 E então a última coisa Eu faço é verificar aqui. 406 00:19:14,510 --> 00:19:17,870 Se a lista não é igual a zero, mas é igual a zero, de modo que ignorar que 407 00:19:17,870 --> 00:19:18,470 completamente. 408 00:19:18,470 --> 00:19:23,520 E assim, tudo o que faço é fica próxima lista ponteiro, o que resulta em pictoricamente 409 00:19:23,520 --> 00:19:25,570 uma imagem assim. 410 00:19:25,570 --> 00:19:26,620 Então esse é um cenário. 411 00:19:26,620 --> 00:19:30,490 >> E o que você estava perguntando sobre especificamente é uma situação como essa, 412 00:19:30,490 --> 00:19:33,190 onde já temos uma lista de um nó. 413 00:19:33,190 --> 00:19:36,240 E se eu voltar a subir no original enunciado do problema, o próximo nós vamos 414 00:19:36,240 --> 00:19:39,320 inserir dizer é 34, apenas para a causa da discussão. 415 00:19:39,320 --> 00:19:46,210 Então eu vou apenas convenientemente tirar essa aqui. 416 00:19:46,210 --> 00:19:47,540 Acabei malloced. 417 00:19:47,540 --> 00:19:49,310 Vamos supor que eu estou verificando nulo. 418 00:19:49,310 --> 00:19:51,870 >> Agora, eu estou indo para inicializar n ser 34. 419 00:19:51,870 --> 00:19:53,040 E isso vai ser n. 420 00:19:53,040 --> 00:19:54,670 Este será o próximo. 421 00:19:54,670 --> 00:19:57,100 E isso vai ser anterior. 422 00:19:57,100 --> 00:19:59,370 Vamos ter certeza que eu não fiz obter este para trás. 423 00:19:59,370 --> 00:20:01,110 Anterior vem em primeiro lugar na definição. 424 00:20:01,110 --> 00:20:03,070 Deixe-me corrigir isso. 425 00:20:03,070 --> 00:20:04,410 Este é anterior. 426 00:20:04,410 --> 00:20:05,780 Este é o próximo. 427 00:20:05,780 --> 00:20:08,620 Mesmo que estes são idênticos, vamos mantê-lo consistente. 428 00:20:08,620 --> 00:20:09,450 >> Anterior. 429 00:20:09,450 --> 00:20:11,030 Este é o próximo. 430 00:20:11,030 --> 00:20:16,310 Então, eu acabei de malloced minha nota, verificado para nula, atribuídos 34 no nó. 431 00:20:16,310 --> 00:20:17,570 Anterior fica nulo. 432 00:20:17,570 --> 00:20:19,480 Então isso me dá isso. 433 00:20:19,480 --> 00:20:21,010 Próxima lista fica. 434 00:20:21,010 --> 00:20:22,370 Assim, a lista é esta. 435 00:20:22,370 --> 00:20:26,520 Portanto, este é o mesmo agora como desenhar este seta, de modo que apontem para uma 436 00:20:26,520 --> 00:20:27,940 na mesma. 437 00:20:27,940 --> 00:20:30,400 E então eu estou verificando se a lista não é igual a nulo. 438 00:20:30,400 --> 00:20:31,740 E não é desta vez. 439 00:20:31,740 --> 00:20:35,580 Então eu vou fazer a lista anterior fica ponteiro. 440 00:20:35,580 --> 00:20:39,700 >> Então lista anterior fica PTR. 441 00:20:39,700 --> 00:20:44,300 Então, isso tem o efeito de colocar uma seta gráfica aqui. 442 00:20:44,300 --> 00:20:46,930 E isso está ficando um pouco ondulado, as linhas. 443 00:20:46,930 --> 00:20:50,780 E então, finalmente, eu atualizo listar para apontar para ponteiro. 444 00:20:50,780 --> 00:20:55,560 Então agora isso aponta para esse cara. 445 00:20:55,560 --> 00:20:57,170 E agora, vamos fazer uma rápida verificação de sanidade. 446 00:20:57,170 --> 00:20:59,470 >> Aqui está a lista, que é a variável global. 447 00:20:59,470 --> 00:21:02,850 O primeiro nó é, na verdade, 34, porque Eu estou seguindo a seta. 448 00:21:02,850 --> 00:21:05,210 E isso é correto porque eu quero inserir no início da lista 449 00:21:05,210 --> 00:21:06,070 todos os novos nós. 450 00:21:06,070 --> 00:21:08,860 Seu próximo campo me leva a esse cara. 451 00:21:08,860 --> 00:21:10,710 Se eu continuar, eu bati em seguida é nulo. 452 00:21:10,710 --> 00:21:11,760 Portanto, não há mais lista. 453 00:21:11,760 --> 00:21:14,460 Se eu acertar anterior, recebo de volta onde eu esperar. 454 00:21:14,460 --> 00:21:16,435 >> Assim, ainda há algumas indicações, obviamente, de manipular. 455 00:21:16,435 --> 00:21:19,870 Mas o fato de que lhe foi dito para fazer esta em tempo constante significa que você só 456 00:21:19,870 --> 00:21:22,910 têm um número finito de coisas você está autorizado a fazer. 457 00:21:22,910 --> 00:21:24,290 E o que é esse número? 458 00:21:24,290 --> 00:21:25,185 Pode ser um passo. 459 00:21:25,185 --> 00:21:25,700 Ele pode ser dois. 460 00:21:25,700 --> 00:21:26,820 Ele pode ser de 1.000 passos. 461 00:21:26,820 --> 00:21:30,500 Mas é finito, o que significa que você não pode ter qualquer tipo de looping em curso 462 00:21:30,500 --> 00:21:32,010 aqui, sem recursão, sem loops. 463 00:21:32,010 --> 00:21:37,390 Ele simplesmente tem que ser linhas codificadas de código que temos nesta amostra. 464 00:21:37,390 --> 00:21:42,330 >> Assim, o próximo problema 12 nos pediu para concluir a implementação de remover 465 00:21:42,330 --> 00:21:46,740 a seguir, de tal maneira que remove n da lista em tempo linear. 466 00:21:46,740 --> 00:21:48,740 Então você tem um pouco mais espaço de manobra agora. 467 00:21:48,740 --> 00:21:52,380 Você pode assumir que n, se presente na lista, estará presente 468 00:21:52,380 --> 00:21:53,340 não mais do que uma vez. 469 00:21:53,340 --> 00:21:56,770 E que também pretende ser uma base-quiz hipótese simplificadora, de modo 470 00:21:56,770 --> 00:21:59,780 que se você encontrar o número 50 em algum lugar na lista, você também não 471 00:21:59,780 --> 00:22:02,890 tem que se preocupar continuando a iteração, à procura de todos os possíveis 472 00:22:02,890 --> 00:22:06,990 cópia de 50, que só iria devolver em alguma minúcia em tempo limitado. 473 00:22:06,990 --> 00:22:10,460 >> Assim, com remoção, este foi definitivamente mais desafiador e mais 474 00:22:10,460 --> 00:22:11,640 código para escrever. 475 00:22:11,640 --> 00:22:14,990 Mas, à primeira vista, francamente, pode ser algo esmagador e como 476 00:22:14,990 --> 00:22:17,060 não há nenhuma maneira que você pode ter chegar a em um quiz. 477 00:22:17,060 --> 00:22:22,450 Mas se concentrar nas etapas individuais, Esperemos que de repente 478 00:22:22,450 --> 00:22:26,060 golpeá-lo de que cada um deles individualmente etapas faz sentido óbvio 479 00:22:26,060 --> 00:22:27,080 em retrospecto. 480 00:22:27,080 --> 00:22:28,200 Então, vamos dar uma olhada. 481 00:22:28,200 --> 00:22:32,570 >> Então, primeiro, nós inicializar ponteiro a ser em si uma lista. 482 00:22:32,570 --> 00:22:36,040 Porque eu quero que o tempo linear, o que significa Vou ter algum loop. 483 00:22:36,040 --> 00:22:39,730 E uma maneira comum de interagir sobre o nós em uma estrutura de lista ou qualquer tipo 484 00:22:39,730 --> 00:22:43,860 da estrutura de forma iterativa é tomar um ponteiro para a frente dos dados 485 00:22:43,860 --> 00:22:46,990 estrutura e depois é só começar a atualizar lo e caminhar seu caminho 486 00:22:46,990 --> 00:22:48,650 através da estrutura de dados. 487 00:22:48,650 --> 00:22:50,040 Então, eu vou fazer exatamente isso. 488 00:22:50,040 --> 00:22:54,260 >> Enquanto ponteiro, minha variável temporária, não é igual a zero, vamos 489 00:22:54,260 --> 00:22:55,660 vá em frente e confira. 490 00:22:55,660 --> 00:22:56,910 Será que eu tenho sorte? 491 00:22:56,910 --> 00:23:01,740 É o campo n no nó Atualmente estou olhando igual ao 492 00:23:01,740 --> 00:23:03,380 número que eu estou procurando? 493 00:23:03,380 --> 00:23:05,410 E se assim for, vamos fazer alguma coisa. 494 00:23:05,410 --> 00:23:10,020 Agora, observe esta condição se rodeia a toda 495 00:23:10,020 --> 00:23:11,520 seguintes linhas de código. 496 00:23:11,520 --> 00:23:14,610 Esta é a única coisa que me interessa - encontrar um número em questão. 497 00:23:14,610 --> 00:23:18,010 Portanto, não há outra coisa, o que simplifica coisas conceitualmente um pouco. 498 00:23:18,010 --> 00:23:22,040 >> Mas agora, eu percebi, e você pode ter só percebi isso depois de pensar 499 00:23:22,040 --> 00:23:24,720 através de um bit, há na verdade, dois casos aqui. 500 00:23:24,720 --> 00:23:28,060 Uma delas é que o nó é o início da lista, que é um 501 00:23:28,060 --> 00:23:31,040 pouco chato, porque isso é uma caso especial, porque você tem que lidar 502 00:23:31,040 --> 00:23:33,340 com essa coisa, que é a única anormalidade. 503 00:23:33,340 --> 00:23:35,720 Em qualquer outro lugar na lista, é a mesma coisa. 504 00:23:35,720 --> 00:23:38,050 Há um nó anterior e próxima nó, o nó anterior, próximo nó. 505 00:23:38,050 --> 00:23:40,940 Mas esse cara é um pouco especial se ele está no início. 506 00:23:40,940 --> 00:23:48,710 >> Portanto, se o apontador é igual a lista em si, então se eu estou no início da 507 00:23:48,710 --> 00:23:53,960 a lista e eu descobri n, eu preciso para fazer um par de coisas. 508 00:23:53,960 --> 00:23:59,230 Um, eu preciso mudar a lista apontar para o campo seguinte, 50. 509 00:23:59,230 --> 00:24:01,270 Então suponho que eu estou tentando para remover 34. 510 00:24:01,270 --> 00:24:03,560 Então esse cara tem que ir longe em apenas um momento. 511 00:24:03,560 --> 00:24:07,210 >> Então, eu vou dizer, a lista ponteiro fica próximo. 512 00:24:07,210 --> 00:24:08,570 Bem, este é ponteiro. 513 00:24:08,570 --> 00:24:10,360 Em seguida está apontando aqui. 514 00:24:10,360 --> 00:24:17,470 Então, isso está mudando esse direito flecha agora a apontar para esse cara aqui. 515 00:24:17,470 --> 00:24:19,580 Agora, lembre-se, nós temos uma variável temporária. 516 00:24:19,580 --> 00:24:23,520 Então, nós não temos nenhum nó órfão, porque eu também tenho esse cara na minha 517 00:24:23,520 --> 00:24:25,010 implementação de remoção. 518 00:24:25,010 --> 00:24:29,600 Então, agora, se a lista em si não é nulo, Eu preciso corrigir uma coisinha. 519 00:24:29,600 --> 00:24:32,690 >> Eu preciso agora ter certeza de que esta seta, que é previamente apontando 520 00:24:32,690 --> 00:24:36,830 50-34, este tem que ir embora, porque se eu estou tentando se livrar 521 00:24:36,830 --> 00:24:41,910 de 34, 50 é melhor não manter qualquer tipo de referência de volta a ele como o 522 00:24:41,910 --> 00:24:42,820 seta sugerido. 523 00:24:42,820 --> 00:24:44,820 Então, eu só fiz essa linha. 524 00:24:44,820 --> 00:24:46,520 Então eu sou feito. 525 00:24:46,520 --> 00:24:48,040 Esse caso é realmente muito fácil. 526 00:24:48,040 --> 00:24:51,010 Decepar a cabeça da lista é relativamente simples. 527 00:24:51,010 --> 00:24:52,980 >> Infelizmente, não é isso bloco chato mais. 528 00:24:52,980 --> 00:24:56,170 Então, agora, eu tenho que considerar o caso onde há algo no meio. 529 00:24:56,170 --> 00:24:59,880 Mas não é terrível demais, com exceção para a sintaxe como esta. 530 00:24:59,880 --> 00:25:03,080 Então, se eu não estou no início da lista, eu estou em algum lugar no meio. 531 00:25:03,080 --> 00:25:08,160 E esta linha aqui está dizendo, início em qualquer nó que você está. 532 00:25:08,160 --> 00:25:11,210 533 00:25:11,210 --> 00:25:18,550 Ir para a próxima área do nó anterior e apontam que no ponteiro. 534 00:25:18,550 --> 00:25:20,390 >> Vamos fazer isso pictoricamente. 535 00:25:20,390 --> 00:25:21,640 Isso estava ficando complicada. 536 00:25:21,640 --> 00:25:30,480 537 00:25:30,480 --> 00:25:37,990 Então, se eu tenho campos anteriores aqui - vamos fazer isso - próximos campos aqui. 538 00:25:37,990 --> 00:25:41,200 Vou simplificar meus ponteiros vez de desenhar um monte de 539 00:25:41,200 --> 00:25:45,710 coisas e para trás cruzando uns aos outros. 540 00:25:45,710 --> 00:25:50,870 E agora, vamos apenas dizer que este é 1, 2, 3 para fins de discussão, mesmo 541 00:25:50,870 --> 00:25:53,410 no entanto, que não se alinha com o problema em questão. 542 00:25:53,410 --> 00:25:55,900 >> Então aqui vai a minha lista encadeada. 543 00:25:55,900 --> 00:25:59,300 Estou tentando remover dois nesta determinada versão da história. 544 00:25:59,300 --> 00:26:01,960 Então eu atualizei ponteiro para estar apontando para esse cara. 545 00:26:01,960 --> 00:26:03,315 Portanto, esta é PTR. 546 00:26:03,315 --> 00:26:04,530 Ele está apontando aqui. 547 00:26:04,530 --> 00:26:07,170 Esta lista é, que existe globalmente como antes. 548 00:26:07,170 --> 00:26:09,200 E ele está apontando aqui, não importa o quê. 549 00:26:09,200 --> 00:26:10,800 E agora, eu estou tentando remover dois. 550 00:26:10,800 --> 00:26:13,850 >> Então, se ponteiro está apontando aqui, estou vai seguir, aparentemente, a 551 00:26:13,850 --> 00:26:17,110 ponteiro anterior, o que me coloca em 1. 552 00:26:17,110 --> 00:26:22,290 Estou, então, vai dizer que o próximo campo, o que me traz até este 553 00:26:22,290 --> 00:26:25,410 caixa aqui, vai ponteiro igual seguinte. 554 00:26:25,410 --> 00:26:28,400 Portanto, se esse ponteiro, este é o próximo. 555 00:26:28,400 --> 00:26:31,840 Isso significa que esta necessidade de seta para apontar para esse cara. 556 00:26:31,840 --> 00:26:35,140 >> Então, o que essa linha de código tem apenas feito é um pouco disso. 557 00:26:35,140 --> 00:26:37,500 E agora, isso está parecendo um passo na direção certa. 558 00:26:37,500 --> 00:26:41,390 Nós essencialmente quer cortar 2 do meio de 1 e 3. 559 00:26:41,390 --> 00:26:44,400 Portanto, faz sentido que queremos rota este ponteiro em torno dele. 560 00:26:44,400 --> 00:26:50,400 Portanto, esta linha seguinte é verificar se ponteiro próximo não é nulo, não há 561 00:26:50,400 --> 00:26:54,200 de facto alguém para a direita, de 2, isso significa que nós também temos que fazer 562 00:26:54,200 --> 00:26:55,850 um pouco de cortar aqui. 563 00:26:55,850 --> 00:27:00,590 >> Então eu agora precisa seguir este ponteiro e atualizar o ponteiro anterior sobre 564 00:27:00,590 --> 00:27:05,410 esse cara para fazer um pouco de um resolver aqui o ponto aqui. 565 00:27:05,410 --> 00:27:07,100 E agora, visualmente este é bom. 566 00:27:07,100 --> 00:27:11,930 É um pouco confuso em que não há ninguém apontando para o 2 mais. 567 00:27:11,930 --> 00:27:13,600 2 está apontando para a esquerda. 568 00:27:13,600 --> 00:27:14,980 E 2 está apontando para a direita. 569 00:27:14,980 --> 00:27:17,480 Mas ele pode fazer o que quiser, porque ele está prestes a ser libertado. 570 00:27:17,480 --> 00:27:19,480 E não importa o que esses valores são mais. 571 00:27:19,480 --> 00:27:23,040 >> O que é importante é que o restante caras estão encaminhamento acima 572 00:27:23,040 --> 00:27:24,280 e abaixo dele agora. 573 00:27:24,280 --> 00:27:25,810 E, de fato, isso é o que fazer a seguir. 574 00:27:25,810 --> 00:27:29,360 Nós ponteiro livre, o que significa que dizer a sistema operacional, você é bem-vindo 575 00:27:29,360 --> 00:27:30,906 para recuperar isso. 576 00:27:30,906 --> 00:27:34,900 E então, finalmente, voltamos. 577 00:27:34,900 --> 00:27:37,220 Else implicitamente, se ainda não voltou, 578 00:27:37,220 --> 00:27:38,290 temos que continuar procurando. 579 00:27:38,290 --> 00:27:41,485 Então ponteiro igual ponteiro próximo apenas significa mover esse cara aqui. 580 00:27:41,485 --> 00:27:42,600 Mova esse cara aqui. 581 00:27:42,600 --> 00:27:45,400 Mova esse cara aqui, se, de fato, não encontramos o número 582 00:27:45,400 --> 00:27:46,960 estamos procurando ainda. 583 00:27:46,960 --> 00:27:49,630 >> Então, francamente, parece completamente esmagadora, eu acho, em primeiro lugar 584 00:27:49,630 --> 00:27:52,180 vista, especialmente se você se esforçou com isso durante o teste, em seguida, ver 585 00:27:52,180 --> 00:27:52,850 algo como isto. 586 00:27:52,850 --> 00:27:55,050 E você palmadinhas nas costas. 587 00:27:55,050 --> 00:27:57,080 Bem, não há nenhuma maneira que eu poderia ter chegar a isso no quiz. 588 00:27:57,080 --> 00:28:00,470 Mas eu diria, você pode, se você quebrar lo em estes indivíduos 589 00:28:00,470 --> 00:28:04,400 casos e apenas atravessá-la cuidado, embora, na verdade, sob 590 00:28:04,400 --> 00:28:06,300 circunstâncias estressantes. 591 00:28:06,300 --> 00:28:09,470 >> Felizmente, a imagem feita tudo mais feliz. 592 00:28:09,470 --> 00:28:11,050 Você poderia chamar isso de qualquer número de maneiras. 593 00:28:11,050 --> 00:28:12,760 Você não tem que fazer o entrecruzamento coisa aqui. 594 00:28:12,760 --> 00:28:14,520 Você poderia fazê-lo com reta linhas como esta. 595 00:28:14,520 --> 00:28:18,790 Mas a essência deste problema, em geral, foi perceber que o 596 00:28:18,790 --> 00:28:22,060 imagem, no final, deve olhar um pouco algo como isso, porque 597 00:28:22,060 --> 00:28:25,030 constante de tempo implícito que você mantenha tocando e tocando e tocando o 598 00:28:25,030 --> 00:28:29,900 novos nós no início da lista. 599 00:28:29,900 --> 00:28:31,960 Alguma pergunta? 600 00:28:31,960 --> 00:28:34,565 Provavelmente o maior desafio de certamente as perguntas de codificação. 601 00:28:34,565 --> 00:28:37,690 >> AUDIÊNCIA: Então a lista é semelhante ao cabeça nos exemplos anteriores. 602 00:28:37,690 --> 00:28:39,640 >> DAVID J. MALAN: Exatamente, exatamente. 603 00:28:39,640 --> 00:28:43,130 Apenas um nome diferente para uma variável global. 604 00:28:43,130 --> 00:28:44,380 Em todo o mundo o que? 605 00:28:44,380 --> 00:28:48,880 606 00:28:48,880 --> 00:28:49,730 >> ROB BOWDEN: OK. 607 00:28:49,730 --> 00:28:52,020 Portanto, esta é aquela em que você tinha que escrever o parágrafo. 608 00:28:52,020 --> 00:28:56,060 Algumas pessoas escreveu ensaios para esta pergunta. 609 00:28:56,060 --> 00:29:00,230 Mas você só precisa usar esses seis termos para descrever o que acontece quando 610 00:29:00,230 --> 00:29:02,440 você tentar entrar em contato facebook.com. 611 00:29:02,440 --> 00:29:07,930 Então eu vou falar com o processo usando todos esses termos. 612 00:29:07,930 --> 00:29:11,290 Assim, em nosso navegador, nós digitamos facebook.com e pressione Enter. 613 00:29:11,290 --> 00:29:17,280 Assim, o nosso navegador vai construir uma HTTP solicitar que vai enviar 614 00:29:17,280 --> 00:29:22,220 através de algum processo de Facebook para Facebook para responder-nos com a 615 00:29:22,220 --> 00:29:24,450 HTML da sua página. 616 00:29:24,450 --> 00:29:28,800 >> Então, o que é o processo pelo que o pedido HTTP 617 00:29:28,800 --> 00:29:30,730 realmente fica para o Facebook? 618 00:29:30,730 --> 00:29:32,790 Então, primeiro, temos de traduzir Facebook.com. 619 00:29:32,790 --> 00:29:38,780 Então, só recebeu o nome Facebook.com, onde realmente faz a solicitação HTTP 620 00:29:38,780 --> 00:29:39,940 precisa ir? 621 00:29:39,940 --> 00:29:44,120 Então, precisamos traduzir Facebook.com para um endereço IP, que unicamente 622 00:29:44,120 --> 00:29:47,620 identifica o que a máquina que realmente pretende enviar esta solicitação para. 623 00:29:47,620 --> 00:29:49,310 O laptop tem um endereço IP. 624 00:29:49,310 --> 00:29:52,240 Tudo conectado à internet tem um endereço IP. 625 00:29:52,240 --> 00:29:59,030 >> Então, DNS, Domain Name System, que é o que vai lidar com a tradução 626 00:29:59,030 --> 00:30:03,750 do facebook.com para um endereço IP que você realmente quiser entrar em contato. 627 00:30:03,750 --> 00:30:08,075 Então, entramos em contato com os servidores DNS e por exemplo, o que é facebook.com? 628 00:30:08,075 --> 00:30:16,560 Ela diz, oh, é o endereço IP 190,212 alguma coisa, alguma coisa, alguma coisa. 629 00:30:16,560 --> 00:30:16,900 Tudo bem. 630 00:30:16,900 --> 00:30:18,850 Agora, eu sei o que a máquina Quero entrar em contato. 631 00:30:18,850 --> 00:30:22,360 >> Então você enviar o seu pedido HTTP sobre a máquina. 632 00:30:22,360 --> 00:30:24,140 Então como é que chegar a essa máquina? 633 00:30:24,140 --> 00:30:27,200 Bem, a solicitação vai de roteador para roteador salto. 634 00:30:27,200 --> 00:30:32,630 Lembre-se do exemplo em sala de aula, onde em que vimos a rota que o 635 00:30:32,630 --> 00:30:35,340 pacotes tomou quando tentamos para se comunicar. 636 00:30:35,340 --> 00:30:38,460 Vimo-lo saltar sobre o Atlântico Oceano em um ponto ou qualquer outra coisa. 637 00:30:38,460 --> 00:30:42,820 >> Assim, o último porto prazo. 638 00:30:42,820 --> 00:30:46,520 Portanto, esta é agora em seu computador. 639 00:30:46,520 --> 00:30:49,970 Você pode ter várias coisas atualmente comunicar com a Internet. 640 00:30:49,970 --> 00:30:53,730 Para que eu possa estar em execução, por exemplo, o Skype. 641 00:30:53,730 --> 00:30:55,670 Eu poderia ter um navegador web aberto. 642 00:30:55,670 --> 00:30:59,010 Eu poderia ter algo que torrenting arquivos. 643 00:30:59,010 --> 00:31:00,880 Então todas essas coisas são comunicando com a 644 00:31:00,880 --> 00:31:02,600 internet de alguma forma. 645 00:31:02,600 --> 00:31:08,070 >> Assim, quando o computador recebe alguns dados a partir da internet, como o faz 646 00:31:08,070 --> 00:31:10,130 sabe o aplicativo realmente quer os dados? 647 00:31:10,130 --> 00:31:12,610 Como é que sei se este particular dados é para o 648 00:31:12,610 --> 00:31:16,070 torrenting aplicação em oposição para o navegador web? 649 00:31:16,070 --> 00:31:20,980 Portanto, este é o propósito de portos em que todas estas aplicações têm 650 00:31:20,980 --> 00:31:22,720 afirmou uma porta no computador. 651 00:31:22,720 --> 00:31:27,580 Portanto, o seu navegador diz, hey, Eu estou escutando na porta 1000. 652 00:31:27,580 --> 00:31:32,240 E o seu programa torrenting está dizendo: Eu estou escutando na porta 3000. 653 00:31:32,240 --> 00:31:34,770 E Skype diz, eu estou usando a porta 4000. 654 00:31:34,770 --> 00:31:41,950 >> Então, quando você recebe alguns dados que pertence a uma destas aplicações, os dados 655 00:31:41,950 --> 00:31:45,510 é marcado com qual porta ele realmente deve ser enviada ao longo de. 656 00:31:45,510 --> 00:31:47,950 Portanto, este diz, oh, eu pertenço a porta 1000. 657 00:31:47,950 --> 00:31:50,950 Eu sei, então eu preciso transmitir a presente junto ao meu navegador. 658 00:31:50,950 --> 00:31:56,440 Assim, a razão é relevante aqui é que os servidores web tendem a 659 00:31:56,440 --> 00:31:58,240 ouvir na porta 80. 660 00:31:58,240 --> 00:32:02,420 Então, quando eu entrar em contato Facebook.com, eu sou comunicar com uma máquina. 661 00:32:02,420 --> 00:32:06,390 Mas eu preciso dizer que a porta de que máquina Quero comunicar. 662 00:32:06,390 --> 00:32:09,160 E os servidores web tendem a ser escutando na porta 80. 663 00:32:09,160 --> 00:32:14,010 >> Se eles quisessem, eles poderiam defini-lo para que ele enumera como na porta 7000. 664 00:32:14,010 --> 00:32:19,090 E então em um navegador web, eu poderia digitar manualmente Facebook.com: 7000 a 665 00:32:19,090 --> 00:32:24,600 enviar a solicitação para a porta 7000 de servidor de web do Facebook. 666 00:32:24,600 --> 00:32:26,820 >> DAVID J. MALAN: E, neste caso, mesmo embora não exigiu que as pessoas 667 00:32:26,820 --> 00:32:30,000 mencionar isso, neste caso, o porto que o pedido realmente ir para? 668 00:32:30,000 --> 00:32:36,630 669 00:32:36,630 --> 00:32:37,880 Tente novamente. 670 00:32:37,880 --> 00:32:42,810 671 00:32:42,810 --> 00:32:44,300 Exatamente. 672 00:32:44,300 --> 00:32:47,960 Sem olhar para isso, mas uma sutileza que está lá nenhum a última. 673 00:32:47,960 --> 00:32:51,770 >> ROB BOWDEN: Então, o HTTPS, já que é escuta especificamente para o 674 00:32:51,770 --> 00:32:55,180 criptografado, é na porta 4430. 675 00:32:55,180 --> 00:32:57,680 >> Audiência: E-mails são de 25, certo? 676 00:32:57,680 --> 00:33:00,670 >> DAVID J. MALAN: Saída e-mails, 25, sim. 677 00:33:00,670 --> 00:33:03,760 >> ROB BOWDEN: Eu nem sei mais de a - todos os mais baixos tendem a ser 678 00:33:03,760 --> 00:33:06,310 reservado para as coisas. 679 00:33:06,310 --> 00:33:09,260 Eu acho que tudo sob 1024 é reservado. 680 00:33:09,260 --> 00:33:13,450 >> AUDIÊNCIA: Por que você disse 3 é o número errado? 681 00:33:13,450 --> 00:33:18,820 >> ROB BOWDEN: Porque em um endereço IP, há quatro agrupamentos de dígitos. 682 00:33:18,820 --> 00:33:21,090 E eles são de 0 a 255. 683 00:33:21,090 --> 00:33:28,060 Então, 192.168.2.1 é um comum endereço IP da rede local. 684 00:33:28,060 --> 00:33:30,840 Observe todos esses são menos de 255. 685 00:33:30,840 --> 00:33:33,570 Então, quando eu comecei com 300, que não poderia ter 686 00:33:33,570 --> 00:33:35,210 sido um dos números. 687 00:33:35,210 --> 00:33:38,170 >> DAVID J. MALAN: Mas esse clipe bobo de - era CSI, onde tiveram um 688 00:33:38,170 --> 00:33:39,970 número que era muito grande para o endereço IP. 689 00:33:39,970 --> 00:33:42,940 690 00:33:42,940 --> 00:33:46,110 >> ROB BOWDEN: Qualquer dúvida sobre isso? 691 00:33:46,110 --> 00:33:51,710 A próxima, mudança tão completa em tema, mas temos este array PHP para 692 00:33:51,710 --> 00:33:53,270 as casas da quad. 693 00:33:53,270 --> 00:33:56,360 E nós temos uma lista desordenada. 694 00:33:56,360 --> 00:33:59,550 E nós queremos imprimir cada item da lista apenas contendo o nome da casa. 695 00:33:59,550 --> 00:34:09,090 696 00:34:09,090 --> 00:34:11,870 Portanto, temos um loop foreach. 697 00:34:11,870 --> 00:34:17,540 Então lembre-se, a sintaxe é foreach matriz como item na matriz. 698 00:34:17,540 --> 00:34:22,360 Assim, através de cada iteração do loop, casa vai assumir um dos 699 00:34:22,360 --> 00:34:24,060 valores dentro da matriz. 700 00:34:24,060 --> 00:34:26,530 >> Na primeira iteração, casa será Cabot House. 701 00:34:26,530 --> 00:34:30,370 Em uma iteração segundo, a casa vai ser Correio casa e assim por diante. 702 00:34:30,370 --> 00:34:34,370 Assim, para cada quad como casa, estamos só vai imprimir - 703 00:34:34,370 --> 00:34:37,250 você também poderia ter ecoado - 704 00:34:37,250 --> 00:34:42,199 o item da lista e, em seguida, o nome da casa e, em seguida, fechar o item da lista. 705 00:34:42,199 --> 00:34:45,210 As chaves são opcionais aqui. 706 00:34:45,210 --> 00:34:49,480 >> E então nós também disse na pergunta si mesmo, lembre-se de fechar a 707 00:34:49,480 --> 00:34:50,770 desordenadas lista de etiquetas. 708 00:34:50,770 --> 00:34:53,949 Então, precisamos sair do modo PHP a fim de fazer isso. 709 00:34:53,949 --> 00:35:00,280 Ou poderíamos ter ecoado a fechar tag lista não ordenada. 710 00:35:00,280 --> 00:35:02,380 >> DAVID J. MALAN: Também seria bem aqui ter sido a usar uma antiga escola para 711 00:35:02,380 --> 00:35:07,340 loop com um $ i = 0 0 e usando a contagem descobrir o comprimento do raio. 712 00:35:07,340 --> 00:35:09,240 Totalmente bem também, apenas um pouco prolixa. 713 00:35:09,240 --> 00:35:12,170 714 00:35:12,170 --> 00:35:14,742 >> AUDIÊNCIA: Então, se você estava indo para [Inaudível], você faria - 715 00:35:14,742 --> 00:35:16,734 Eu esqueço o que o loop [inaudível] é. 716 00:35:16,734 --> 00:35:21,380 Você $ suporte quad i? 717 00:35:21,380 --> 00:35:21,850 >> DAVID J. MALAN: Exatamente. 718 00:35:21,850 --> 00:35:23,100 Sim, exatamente. 719 00:35:23,100 --> 00:35:26,650 720 00:35:26,650 --> 00:35:27,900 >> ROB BOWDEN: Mais alguma coisa? 721 00:35:27,900 --> 00:35:31,350 722 00:35:31,350 --> 00:35:32,010 >> DAVID J. MALAN: Tudo bem. 723 00:35:32,010 --> 00:35:32,300 Trade-offs. 724 00:35:32,300 --> 00:35:38,290 Assim, havia cachos de respostas possível para cada um deles. 725 00:35:38,290 --> 00:35:40,510 Nós estávamos realmente apenas à procura de algo convincente para um lado positivo e 726 00:35:40,510 --> 00:35:41,100 um lado negativo. 727 00:35:41,100 --> 00:35:44,830 E o número 16 pediu, validando os usuários ' do lado do cliente de entrada, como com JavaScript, 728 00:35:44,830 --> 00:35:47,280 em vez de no lado do servidor, como acontece com PHP. 729 00:35:47,280 --> 00:35:49,450 Então o que é um lado positivo de fazendo do lado do cliente? 730 00:35:49,450 --> 00:35:53,780 >> Bem, uma das coisas que propusemos é que você reduzir a latência, porque você 731 00:35:53,780 --> 00:35:56,750 não tem que se preocupar em contato com o servidor, o que pode demorar um pouco 732 00:35:56,750 --> 00:36:00,390 milissegundos ou até mesmo um par de segundos evitando que e apenas 733 00:36:00,390 --> 00:36:04,670 validando a entrada do lado do cliente dos usuários por provocando um manipulador on-apresentar e 734 00:36:04,670 --> 00:36:06,650 apenas a verificação, eles digite algo para o nome? 735 00:36:06,650 --> 00:36:08,080 Será que eles digitar algo no para o endereço de e-mail? 736 00:36:08,080 --> 00:36:10,950 Será que eles escolhem um dormitório de No menu drop-down? 737 00:36:10,950 --> 00:36:14,360 >> Você pode dar-lhes feedback instantâneo usando o computador gigahertz 738 00:36:14,360 --> 00:36:16,770 ou o que eles têm que é na verdade, em sua mesa. 739 00:36:16,770 --> 00:36:19,310 Então é só um usuário melhor experimentar normalmente. 740 00:36:19,310 --> 00:36:24,460 Mas uma desvantagem de fazer do lado do cliente validação, se você fizer isso sem também 741 00:36:24,460 --> 00:36:29,860 fazer a validação do lado do servidor é que mais ninguém saindo do CS50 sabe 742 00:36:29,860 --> 00:36:33,980 que você pode apenas enviar todos os dados que deseja para um servidor de qualquer número de maneiras. 743 00:36:33,980 --> 00:36:37,030 Francamente, na maior parte de qualquer navegador, você pode clique em torno das definições e apenas 744 00:36:37,030 --> 00:36:40,110 desligar o JavaScript, o que, portanto, desabilite qualquer forma de 745 00:36:40,110 --> 00:36:41,080 validação. 746 00:36:41,080 --> 00:36:44,460 >> Mas você também deve se lembrar que, mesmo que eu fiz algumas coisas misteriosas na classe usando 747 00:36:44,460 --> 00:36:47,790 telnet e realmente fingindo ser um navegador enviando get 748 00:36:47,790 --> 00:36:49,240 solicitações para um servidor. 749 00:36:49,240 --> 00:36:51,030 E isso certamente não é utilizando qualquer JavaScript. 750 00:36:51,030 --> 00:36:53,290 Isso é só me digitar comandos num teclado. 751 00:36:53,290 --> 00:36:57,410 Então, realmente, qualquer programador dentro suficiente conforto com a web e HTTP 752 00:36:57,410 --> 00:37:01,690 poderia enviar todos os dados que ele ou ela quer para um servidor sem validação. 753 00:37:01,690 --> 00:37:05,470 E se o seu servidor não está também a verificação, que me deram um nome, é 754 00:37:05,470 --> 00:37:08,930 isso realmente um endereço de email válido, não eles escolhem um dormitório, você pode acabar 755 00:37:08,930 --> 00:37:12,800 se inserir falso ou apenas de dados em branco em seu banco de dados, o que provavelmente 756 00:37:12,800 --> 00:37:15,450 não vai ser uma coisa boa se você estava supondo que ele estava lá. 757 00:37:15,450 --> 00:37:16,770 >> Portanto, esta é uma realidade desagradável. 758 00:37:16,770 --> 00:37:19,890 Mas, em geral, do lado do cliente validação é grande. 759 00:37:19,890 --> 00:37:21,810 Mas isso significa que o dobro do trabalho. 760 00:37:21,810 --> 00:37:25,970 Embora exista vários bibliotecas, bibliotecas JavaScript para 761 00:37:25,970 --> 00:37:28,830 exemplo, que fazer isso muito, muito menos de uma dor de cabeça. 762 00:37:28,830 --> 00:37:31,940 E você pode reutilizar parte do código do lado do servidor, do lado do cliente. 763 00:37:31,940 --> 00:37:35,980 Mas não percebem que é tipicamente trabalho adicional. 764 00:37:35,980 --> 00:37:36,415 É. 765 00:37:36,415 --> 00:37:37,792 >> AUDIÊNCIA: Então, se nós apenas disse menos seguro - 766 00:37:37,792 --> 00:37:39,205 >> DAVID J. MALAN: [Risos] 767 00:37:39,205 --> 00:37:39,680 Ugh. 768 00:37:39,680 --> 00:37:43,105 Aqueles são sempre o mais difícil aqueles para julgar. 769 00:37:43,105 --> 00:37:44,480 >> ROB BOWDEN: Isso faria foram aceites. 770 00:37:44,480 --> 00:37:44,810 >> DAVID J. MALAN: O quê? 771 00:37:44,810 --> 00:37:45,810 >> ROB BOWDEN: Eu criei este problema. 772 00:37:45,810 --> 00:37:46,735 Isso teria sido aceito. 773 00:37:46,735 --> 00:37:47,220 >> DAVID J. MALAN: Yeah. 774 00:37:47,220 --> 00:37:47,830 >> AUDIÊNCIA: Cool. 775 00:37:47,830 --> 00:37:51,770 >> ROB BOWDEN: Mas nós não aceitou para o primeiro - 776 00:37:51,770 --> 00:37:53,630 bem, o que estávamos procurando é algo que você não tem que 777 00:37:53,630 --> 00:37:55,270 comunicar com o servidor. 778 00:37:55,270 --> 00:37:58,355 Nós não aceitamos apenas mais rápido. 779 00:37:58,355 --> 00:38:00,080 >> AUDIÊNCIA: E sobre Não recarregar a página? 780 00:38:00,080 --> 00:38:00,430 >> ROB BOWDEN: sim. 781 00:38:00,430 --> 00:38:03,000 Essa foi uma resposta aceita. 782 00:38:03,000 --> 00:38:06,300 >> DAVID J. MALAN: Qualquer coisa onde nos sentimos que era mais provável que não provável 783 00:38:06,300 --> 00:38:09,780 que você sabia o que eram dizendo, que é um duro 784 00:38:09,780 --> 00:38:13,500 linha para desenhar algumas vezes. 785 00:38:13,500 --> 00:38:16,000 Usando uma lista ligada em vez de uma matriz para manter um 786 00:38:16,000 --> 00:38:17,590 lista de inteiros ordenada. 787 00:38:17,590 --> 00:38:21,000 Então, um de cabeça, muitas vezes citam com ligado listas que motivaram a sua inteira 788 00:38:21,000 --> 00:38:22,370 introdução foi você começa dinamismo. 789 00:38:22,370 --> 00:38:23,030 Elas podem crescer. 790 00:38:23,030 --> 00:38:23,950 Eles podem encolher. 791 00:38:23,950 --> 00:38:27,370 Então você não tem que saltar através de aros realmente criar mais memória 792 00:38:27,370 --> 00:38:28,140 com uma matriz. 793 00:38:28,140 --> 00:38:30,310 Ou você não tem que apenas dizer, desculpe, o usuário. 794 00:38:30,310 --> 00:38:31,410 A matriz é preenchida. 795 00:38:31,410 --> 00:38:35,850 Assim, o crescimento dinâmica da lista. 796 00:38:35,850 --> 00:38:37,210 A desvantagem apesar de listas ligadas? 797 00:38:37,210 --> 00:38:40,916 798 00:38:40,916 --> 00:38:43,356 >> AUDIÊNCIA: É linear. 799 00:38:43,356 --> 00:38:45,800 Pesquisando em lista ligada é linear ao invés do que você log in 800 00:38:45,800 --> 00:38:46,360 >> DAVID J. MALAN: Exatamente. 801 00:38:46,360 --> 00:38:50,160 Pesquisando em uma lista ligada é linear, mesmo que seja ordenado, porque você pode 802 00:38:50,160 --> 00:38:53,170 apenas siga estas migalhas de pão, estes ponteiros, a partir do início da lista 803 00:38:53,170 --> 00:38:53,570 ao fim. 804 00:38:53,570 --> 00:38:57,970 Você não pode utilizar o acesso aleatório e, Assim, busca binária, mesmo que seja 805 00:38:57,970 --> 00:39:00,740 classificado, que você poderia fazer com um array. 806 00:39:00,740 --> 00:39:02,390 E há também um outro custo. 807 00:39:02,390 --> 00:39:02,966 É. 808 00:39:02,966 --> 00:39:03,800 >> AUDIÊNCIA: Memória ineficiente? 809 00:39:03,800 --> 00:39:04,130 >> DAVID J. MALAN: Yeah. 810 00:39:04,130 --> 00:39:06,940 Bem, eu não iria, necessariamente, dizer ineficiente. 811 00:39:06,940 --> 00:39:10,110 Mas isso não lhe custa mais memória, porque você precisa de 32 bits para cada 812 00:39:10,110 --> 00:39:13,400 nó para o ponteiro adicional, em menos para uma lista vinculada isoladamente. 813 00:39:13,400 --> 00:39:16,660 Agora, se você está armazenando apenas números inteiros e você está adicionando o ponteiro, que é 814 00:39:16,660 --> 00:39:17,830 na verdade, uma espécie de não-trivial. 815 00:39:17,830 --> 00:39:19,340 É duplicando a quantidade de memória. 816 00:39:19,340 --> 00:39:22,330 Mas, na realidade, se você está armazenando um lista ligada de estruturas que possam ter 817 00:39:22,330 --> 00:39:25,540 8 bytes, 16 bytes, ainda mais do que isso, talvez seja menos 818 00:39:25,540 --> 00:39:26,500 de um custo marginal. 819 00:39:26,500 --> 00:39:28,320 Mas é um custo, no entanto. 820 00:39:28,320 --> 00:39:31,880 Assim, ou daqueles teria sido muito bem como desvantagens. 821 00:39:31,880 --> 00:39:32,110 >> 18. 822 00:39:32,110 --> 00:39:36,100 Utilizando o PHP em vez de C para escrever um programa de linha de comando. 823 00:39:36,100 --> 00:39:41,890 Então, aqui, muitas vezes é mais rápido usar uma linguagem como PHP ou Ruby ou Python. 824 00:39:41,890 --> 00:39:43,700 Você acabou de abrir rapidamente um editor de texto. 825 00:39:43,700 --> 00:39:45,900 Você tem muito mais funções disponíveis para você. 826 00:39:45,900 --> 00:39:49,325 PHP tem a pia da cozinha de funções, enquanto que em C, você 827 00:39:49,325 --> 00:39:50,420 tem muito, muito pouco. 828 00:39:50,420 --> 00:39:53,820 Na verdade, a gente sabe a maneira mais difícil que você não tem tabelas de hash. 829 00:39:53,820 --> 00:39:55,000 Você não ligaram listas. 830 00:39:55,000 --> 00:39:57,470 Se você quiser aqueles, você tem que implementá-las você mesmo. 831 00:39:57,470 --> 00:40:00,950 >> Então, uma cabeça de PHP ou realmente qualquer linguagem interpretada é a rapidez 832 00:40:00,950 --> 00:40:02,920 com o qual você pode escrever código. 833 00:40:02,920 --> 00:40:06,660 Mas uma desvantagem, vimos isso quando eu rapidamente chicoteado até um misspeller 834 00:40:06,660 --> 00:40:11,780 implementação na aula usando PHP, é que o uso de uma linguagem interpretada 835 00:40:11,780 --> 00:40:13,570 é geralmente mais lento. 836 00:40:13,570 --> 00:40:18,420 E vimos que comprovadamente com um aumento no tempo de 0,3 segundos para três 837 00:40:18,420 --> 00:40:24,440 segundo, devido à interpretação que realmente acontece. 838 00:40:24,440 --> 00:40:27,060 >> Outra vantagem é que você não tem que compilar. 839 00:40:27,060 --> 00:40:30,130 Por isso, também acelera o desenvolvimento aliás, porque você não tem 840 00:40:30,130 --> 00:40:31,360 duas etapas para a execução de um programa. 841 00:40:31,360 --> 00:40:32,140 Você só tem um. 842 00:40:32,140 --> 00:40:35,260 E assim que é bastante atraente também. 843 00:40:35,260 --> 00:40:38,450 Usando um banco de dados SQL, em vez de um arquivo CSV para armazenar dados. 844 00:40:38,450 --> 00:40:40,230 Banco de dados para SQL é usado para pset7. 845 00:40:40,230 --> 00:40:42,060 Arquivos CSV você não usar muito. 846 00:40:42,060 --> 00:40:45,960 Mas você usou indiretamente em pset7 como bem, conversando com o Yahoo Finance. 847 00:40:45,960 --> 00:40:49,330 >> Mas CSV é como um arquivo do Excel, mas super simples, onde as colunas são 848 00:40:49,330 --> 00:40:54,010 apenas demarcado por vírgulas dentro de um arquivo de texto de outra forma. 849 00:40:54,010 --> 00:40:56,740 E usando um banco de dados SQL é um pouco mais convincente. 850 00:40:56,740 --> 00:41:00,060 É um lado positivo, porque você fazer as coisas como selecionar e inserir e excluir. 851 00:41:00,060 --> 00:41:03,790 E você tem, presumivelmente, índices que MySQL e outros bancos de dados, como 852 00:41:03,790 --> 00:41:07,510 Oracle, construir para você na memória, que significa que a sua escolha não é provavelmente 853 00:41:07,510 --> 00:41:09,000 vai ser top linear para baixo. 854 00:41:09,000 --> 00:41:11,300 É realmente vai ser algo como busca binária ou algo 855 00:41:11,300 --> 00:41:12,520 semelhante em espírito. 856 00:41:12,520 --> 00:41:13,930 Então, eles são geralmente mais rápido. 857 00:41:13,930 --> 00:41:16,040 >> Mas a desvantagem é que é apenas mais trabalho. 858 00:41:16,040 --> 00:41:16,730 É mais esforço. 859 00:41:16,730 --> 00:41:18,140 Você tem que entender bancos de dados. 860 00:41:18,140 --> 00:41:18,940 Você tem que configurá-lo. 861 00:41:18,940 --> 00:41:20,840 Você precisa de um servidor para executar esse banco de dados em. 862 00:41:20,840 --> 00:41:22,750 Você precisa entender como configurá-lo. 863 00:41:22,750 --> 00:41:24,930 Então, essas são apenas estes tipos de trade-offs. 864 00:41:24,930 --> 00:41:27,860 Considerando um arquivo CSV, você pode criá-lo com gedit. 865 00:41:27,860 --> 00:41:28,770 E você está pronto para ir. 866 00:41:28,770 --> 00:41:31,550 Não há nenhuma complexidade além disso. 867 00:41:31,550 --> 00:41:34,870 >> Usando um trie em vez de uma tabela hash com encadeamento separado para armazenar uma 868 00:41:34,870 --> 00:41:37,490 dicionário de palavras que lembram de pset5. 869 00:41:37,490 --> 00:41:42,480 Assim, um tenta de cabeça, em teoria pelo menos, é o que? 870 00:41:42,480 --> 00:41:46,380 Constante de tempo, pelo menos se você for hashing em cada do indivíduo 871 00:41:46,380 --> 00:41:48,990 letras em uma palavra, como você pode ter para pset5. 872 00:41:48,990 --> 00:41:52,720 Isso pode ser cinco, seis hashes hashes se há cinco ou seis 873 00:41:52,720 --> 00:41:53,900 letras da palavra. 874 00:41:53,900 --> 00:41:54,580 E isso é muito bom. 875 00:41:54,580 --> 00:41:56,910 E se há um limite superior sobre a forma como longo de suas palavras possam ser, que é 876 00:41:56,910 --> 00:41:59,320 tempo de fato assintoticamente constante. 877 00:41:59,320 --> 00:42:05,180 >> Considerando uma tabela hash com separado encadeamento, o problema lá com que 878 00:42:05,180 --> 00:42:09,070 tipo de estrutura de dados é que o desempenho de seus algoritmos normalmente 879 00:42:09,070 --> 00:42:12,700 depende do número de coisas já na estrutura de dados. 880 00:42:12,700 --> 00:42:15,660 E isso é definitivamente o caso com cadeias, em que quanto mais coisas você colocar 881 00:42:15,660 --> 00:42:18,800 em uma tabela hash, mais tempo os cadeias de ir, o que significa que, na pior 882 00:42:18,800 --> 00:42:21,960 caso, a coisa que você pode estar procurando é toda a maneira, no final de um 883 00:42:21,960 --> 00:42:26,000 dessas cadeias, o que efetivamente transforma em algo linear. 884 00:42:26,000 --> 00:42:29,450 >> Agora, na prática, é absolutamente possível ser o caso de uma tabela hash com 885 00:42:29,450 --> 00:42:32,820 cadeias é mais rápido do que um correspondente implementação trie. 886 00:42:32,820 --> 00:42:35,570 Mas isso é, por várias razões, entre que são tentativas usar um monte de 887 00:42:35,570 --> 00:42:39,240 memória que pode, de fato, as coisas devagar para baixo, porque você não ficar bom 888 00:42:39,240 --> 00:42:42,410 benefícios de uma coisa chamada cache, onde as coisas que estão juntos 889 00:42:42,410 --> 00:42:45,420 em memória pode ser acedida muitas vezes mais rapidamente. 890 00:42:45,420 --> 00:42:48,180 E às vezes você pode vir até com realmente uma boa função hash. 891 00:42:48,180 --> 00:42:51,060 Mesmo que você tem que perder um pouco de memória, você pode, de fato, ser capaz de 892 00:42:51,060 --> 00:42:54,430 encontrar as coisas rápido e não tão ruim quanto linearmente. 893 00:42:54,430 --> 00:42:58,410 >> Então, em suma, não havia necessariamente com qualquer um um ou mesmo dois 894 00:42:58,410 --> 00:43:00,050 coisas específicas que estávamos procurando. 895 00:43:00,050 --> 00:43:03,080 Realmente nada convincente como ascendentes e descendentes 896 00:43:03,080 --> 00:43:04,800 geralmente chamou nossa atenção. 897 00:43:04,800 --> 00:43:11,840 >> ROB BOWDEN: Então, para o lado positivo, fizemos não aceitar a sua própria "mais rápido". Você 898 00:43:11,840 --> 00:43:14,540 tinha a dizer algo sobre isso. 899 00:43:14,540 --> 00:43:17,910 Mesmo que você disse, teoricamente, mais rápido, sabíamos que tipo de entendido 900 00:43:17,910 --> 00:43:19,470 que é 0 a 1. 901 00:43:19,470 --> 00:43:22,820 E tabela hash, em teoria, Não é de 0 a 1. 902 00:43:22,820 --> 00:43:26,550 Mencionando nada sobre tempo de execução geralmente tem os pontos. 903 00:43:26,550 --> 00:43:32,640 Mas o "mais rápido", a maioria das soluções em o grande conselho que foram tentativas foram 904 00:43:32,640 --> 00:43:34,990 objectivamente mais lento do que as soluções que eram tabelas de hash. 905 00:43:34,990 --> 00:43:37,250 Assim, mais rápida em si não é realmente verdade. 906 00:43:37,250 --> 00:43:41,550 907 00:43:41,550 --> 00:43:44,380 >> DAVID J. MALAN: Dom de dom dom. 908 00:43:44,380 --> 00:43:46,686 Eu sou provavelmente o único que percebe é assim que é suposto 909 00:43:46,686 --> 00:43:47,500 ser pronunciado, certo? 910 00:43:47,500 --> 00:43:50,400 >> ROB BOWDEN: Eu tinha, na verdade, não faço idéia. 911 00:43:50,400 --> 00:43:51,650 >> DAVID J. MALAN: Fez sentido na minha cabeça. 912 00:43:51,650 --> 00:43:53,830 913 00:43:53,830 --> 00:43:57,580 >> ROB BOWDEN: Eu estou fazendo este. 914 00:43:57,580 --> 00:43:58,020 OK. 915 00:43:58,020 --> 00:44:04,243 Portanto, esta é aquela em que você tinha que desenhar o diagrama semelhante a você pode 916 00:44:04,243 --> 00:44:06,040 tenho visto nos exames anteriores. 917 00:44:06,040 --> 00:44:12,200 Então vamos apenas olhar para isso. 918 00:44:12,200 --> 00:44:18,170 Então, a partir do nó HTML, temos dois crianças, a cabeça eo corpo. 919 00:44:18,170 --> 00:44:20,570 Então, nós ramificar - cabeça e corpo. 920 00:44:20,570 --> 00:44:22,280 A cabeça tem uma tag title. 921 00:44:22,280 --> 00:44:23,710 Portanto, temos um título. 922 00:44:23,710 --> 00:44:28,450 >> Agora, a única coisa que um monte de gente esqueceu é que esses nós de texto são 923 00:44:28,450 --> 00:44:30,430 elementos dentro desta árvore. 924 00:44:30,430 --> 00:44:36,260 Então aqui nós acontecer para desenhá-los como ovais para diferenciá-los a partir destes 925 00:44:36,260 --> 00:44:37,380 tipos de nós. 926 00:44:37,380 --> 00:44:41,450 Mas note também aqui temos de topo, meio e fundo vai acabar por ser 927 00:44:41,450 --> 00:44:42,560 nós de texto. 928 00:44:42,560 --> 00:44:46,250 Então, esquecendo aqueles foi um pouco de um erro comum. 929 00:44:46,250 --> 00:44:48,770 >> O corpo tem três filhos - estas três divs. 930 00:44:48,770 --> 00:44:53,340 Então div, div, div e então o texto filhos do nó desses divs. 931 00:44:53,340 --> 00:44:55,900 Isso é muito bonito isso para que as perguntas. 932 00:44:55,900 --> 00:44:57,860 >> DAVID J. MALAN: E é interessante notar, apesar de não se debruçar sobre estes 933 00:44:57,860 --> 00:45:01,040 detalhes do tempo que gastamos em JavaScript, que faz o pedido, em 934 00:45:01,040 --> 00:45:02,290 fato, a matéria tecnicamente. 935 00:45:02,290 --> 00:45:06,330 Então, se a cabeça vem antes do corpo na HTML, em seguida, ele deve aparecer ao 936 00:45:06,330 --> 00:45:08,860 esquerda do corpo no DOM efectivo. 937 00:45:08,860 --> 00:45:12,265 Que o seu é, em geral, apenas FYI, uma coisa chamada ordem do documento, onde 938 00:45:12,265 --> 00:45:13,260 isso não importa. 939 00:45:13,260 --> 00:45:17,470 E se você foi a implementação de um parser, um programa que lê HTML na construção 940 00:45:17,470 --> 00:45:20,960 até a árvore na memória, para ser honesto, isso é provavelmente o que você intuitivamente 941 00:45:20,960 --> 00:45:24,720 fazer de qualquer maneira - de cima para baixo, esquerda para a direita. 942 00:45:24,720 --> 00:45:26,116 >> ROB BOWDEN: Perguntas sobre isso? 943 00:45:26,116 --> 00:45:29,080 944 00:45:29,080 --> 00:45:30,000 Devo fazer o próximo? 945 00:45:30,000 --> 00:45:32,380 >> DAVID J. MALAN: Claro. 946 00:45:32,380 --> 00:45:33,810 >> ROB BOWDEN: OK. 947 00:45:33,810 --> 00:45:39,320 Então este é o estouro de buffer pergunta ataque. 948 00:45:39,320 --> 00:45:43,740 A principal coisa a reconhecer é aqui, bem, como pode um truque adversário 949 00:45:43,740 --> 00:45:46,170 este programa em execução código arbitrário? 950 00:45:46,170 --> 00:45:51,860 Então argv1, a primeira linha de comando argumento a este programa, que pode ser 951 00:45:51,860 --> 00:45:53,920 arbitrariamente longo. 952 00:45:53,920 --> 00:45:59,160 Mas aqui estamos usando memcpy para copiar argv1, que aqui é bar. 953 00:45:59,160 --> 00:46:00,165 Estamos passando-o como argumento. 954 00:46:00,165 --> 00:46:02,050 E assim ele está tomando na barra de nome. 955 00:46:02,050 --> 00:46:08,040 >> Então, nós estamos memcpying bar neste tampão c. 956 00:46:08,040 --> 00:46:09,400 Quantos bytes estamos copiando? 957 00:46:09,400 --> 00:46:14,040 Bem no entanto muitos bytes bar acontece a estar usando, o comprimento do argumento. 958 00:46:14,040 --> 00:46:17,930 Mas c é de apenas 12 bytes de largura. 959 00:46:17,930 --> 00:46:22,280 Então, se nós digitamos um argumento de linha de comando isso é mais do que 12 bytes, estamos 960 00:46:22,280 --> 00:46:25,470 vai transbordar esta determinado buffer. 961 00:46:25,470 --> 00:46:31,000 Agora, como pode um adversário enganar o programa em execução de código arbitrário? 962 00:46:31,000 --> 00:46:34,910 >> Então lembre-se que aqui principal é chamar foo. 963 00:46:34,910 --> 00:46:37,340 E então chamadas principais foo. 964 00:46:37,340 --> 00:46:40,408 Vamos desenhar isso. 965 00:46:40,408 --> 00:46:44,720 966 00:46:44,720 --> 00:46:46,990 Portanto, temos a nossa stack. 967 00:46:46,990 --> 00:46:49,090 E principal tem um quadro de pilha na parte inferior. 968 00:46:49,090 --> 00:46:51,860 969 00:46:51,860 --> 00:46:53,250 Em algum momento, as chamadas principais foo. 970 00:46:53,250 --> 00:46:55,390 Bem, de imediato, as chamadas principais foo. 971 00:46:55,390 --> 00:46:57,130 E assim foo recebe o seu próprio quadro de pilha. 972 00:46:57,130 --> 00:46:59,650 973 00:46:59,650 --> 00:47:02,220 >> Agora, em algum momento, foo vai voltar. 974 00:47:02,220 --> 00:47:06,810 E foi foo retornos, o que precisamos saber em que linha de código dentro de nós principal 975 00:47:06,810 --> 00:47:10,610 estavam a fim de saber onde devemos continuar na principal. 976 00:47:10,610 --> 00:47:13,100 Podemos chamar foo de um todo monte de lugares diferentes. 977 00:47:13,100 --> 00:47:14,620 Como sabemos para onde voltar? 978 00:47:14,620 --> 00:47:16,460 Bem, precisamos guardar isso em algum lugar. 979 00:47:16,460 --> 00:47:23,010 >> Então, em algum lugar por aqui, nós armazenamos onde devemos voltar a uma vez 980 00:47:23,010 --> 00:47:24,070 foo retorna. 981 00:47:24,070 --> 00:47:26,350 E este é o endereço de retorno. 982 00:47:26,350 --> 00:47:30,490 Então, como um adversário pode tirar partido isto é o facto de que 983 00:47:30,490 --> 00:47:37,550 este tampão c são armazenados, vamos dizer, aqui é c. 984 00:47:37,550 --> 00:47:39,690 Então, nós temos 12 bytes para c. 985 00:47:39,690 --> 00:47:40,540 Este é c. 986 00:47:40,540 --> 00:47:43,030 E este é o anel pilha de foo. 987 00:47:43,030 --> 00:47:49,970 Portanto, se o usuário mal-intencionado entra mais bytes do que 12 ou eles entram em um comando 988 00:47:49,970 --> 00:47:54,570 argumento de linha que é mais do que 12 caracteres, então vamos 989 00:47:54,570 --> 00:47:57,540 transbordar este buffer. 990 00:47:57,540 --> 00:47:59,910 >> Podemos continuar. 991 00:47:59,910 --> 00:48:02,220 E em algum momento, vamos longe o suficiente para que nós começamos 992 00:48:02,220 --> 00:48:05,120 substituir este endereço de retorno. 993 00:48:05,120 --> 00:48:08,310 Assim, uma vez que substituir o endereço de retorno, isto significa que, quando foo 994 00:48:08,310 --> 00:48:14,220 retornos, estamos voltando para onde quer que o usuário mal-intencionado está dizendo a ele para por 995 00:48:14,220 --> 00:48:19,490 o valor que ele entrou, por qualquer caracteres que o usuário inseriu. 996 00:48:19,490 --> 00:48:24,320 E assim, se o usuário malicioso está sendo particularmente inteligente, ele pode ter esse 997 00:48:24,320 --> 00:48:29,255 voltar para algum lugar no printDef função ou em algum lugar do malloc 998 00:48:29,255 --> 00:48:31,830 função, em qualquer lugar arbitrário. 999 00:48:31,830 --> 00:48:38,420 >> Mas ainda mais inteligente é o que se tem o usuário retornar para a direita aqui. 1000 00:48:38,420 --> 00:48:41,920 E então você começa a execução de estes como linhas de código. 1001 00:48:41,920 --> 00:48:46,610 Então, nesse ponto, o usuário pode entrar o que ele quer para esta região. 1002 00:48:46,610 --> 00:48:52,210 E ele tem o controle completo sobre o seu programa. 1003 00:48:52,210 --> 00:48:53,460 Perguntas sobre isso? 1004 00:48:53,460 --> 00:48:56,380 1005 00:48:56,380 --> 00:49:00,970 Portanto, a próxima pergunta é completa o reimplementação do foo de tal forma 1006 00:49:00,970 --> 00:49:02,620 que ele não é mais vulnerável. 1007 00:49:02,620 --> 00:49:03,870 >> Portanto, há um par de maneiras você poderia ter feito isso. 1008 00:49:03,870 --> 00:49:10,900 1009 00:49:10,900 --> 00:49:13,330 Ainda temos c apenas sendo de comprimento 12. 1010 00:49:13,330 --> 00:49:16,480 Você poderia ter mudado isso como parte de sua solução. 1011 00:49:16,480 --> 00:49:18,930 Nós também adicionamos um cheque para fazer certeza de bar não era nulo. 1012 00:49:18,930 --> 00:49:24,460 Embora você não precisa que para o crédito total. 1013 00:49:24,460 --> 00:49:27,690 Então, nós estamos verificando o primeiro comprimento da corda de bar. 1014 00:49:27,690 --> 00:49:31,650 Se for maior do que 12, então Não, na verdade, fazer a cópia. 1015 00:49:31,650 --> 00:49:33,010 Então essa é uma maneira de corrigi-lo. 1016 00:49:33,010 --> 00:49:36,750 >> Uma outra forma de fixação é, em vez de c tendo apenas ser de comprimento 12, tê-lo 1017 00:49:36,750 --> 00:49:39,310 ser de comprimento strlen (bar). 1018 00:49:39,310 --> 00:49:43,370 Outra maneira de fixar é realmente só retornar. 1019 00:49:43,370 --> 00:49:46,690 Então, se você tivesse acabado de se livrar de todos isso, se você tivesse apagado tudo 1020 00:49:46,690 --> 00:49:51,830 linhas de código, você teria chegado todo o crédito, uma vez que esta função 1021 00:49:51,830 --> 00:49:54,150 na verdade não realizar qualquer coisa. 1022 00:49:54,150 --> 00:49:57,650 É copiar a linha de comando argumento em algum arranjo em 1023 00:49:57,650 --> 00:49:59,960 seu quadro de pilha local. 1024 00:49:59,960 --> 00:50:01,310 E então a coisa está voltando. 1025 00:50:01,310 --> 00:50:04,020 E o que for realizado está desaparecido. 1026 00:50:04,020 --> 00:50:09,740 Assim, o retorno também foi suficiente forma de obtenção de crédito total. 1027 00:50:09,740 --> 00:50:13,425 >> DAVID J. MALAN: Não é bem o espírito de a questão, mas aceitável por a 1028 00:50:13,425 --> 00:50:15,580 especificação, no entanto. 1029 00:50:15,580 --> 00:50:18,260 >> ROB BOWDEN: Perguntas sobre nada disso? 1030 00:50:18,260 --> 00:50:22,270 A única coisa que você, pelo menos, precisava ter compilar o código. 1031 00:50:22,270 --> 00:50:24,810 Assim, mesmo que tecnicamente você não está vulnerável se o seu código não 1032 00:50:24,810 --> 00:50:29,130 compilar, não aceito isso. 1033 00:50:29,130 --> 00:50:31,350 Não há dúvidas? 1034 00:50:31,350 --> 00:50:33,320 OK. 1035 00:50:33,320 --> 00:50:34,580 >> DAVID J. MALAN: Você quer dizer que este título? 1036 00:50:34,580 --> 00:50:37,230 >> ROB BOWDEN: Não. 1037 00:50:37,230 --> 00:50:40,470 >> DAVID J. MALAN: Então, em um presente, este era ou uma boa notícia ou má notícia. 1038 00:50:40,470 --> 00:50:43,870 Este é literalmente o mesmo problema como o primeiro quiz. 1039 00:50:43,870 --> 00:50:46,140 E é quase o mesmo problema como pset1. 1040 00:50:46,140 --> 00:50:49,980 Mas isso foi deliberadamente simplificados para ser uma pirâmide mais simples, que pode ser 1041 00:50:49,980 --> 00:50:52,330 resolvido com um pouco iteração mais simples. 1042 00:50:52,330 --> 00:50:55,680 E realmente, o que se locomover em aqui não era tanto a lógica, 1043 00:50:55,680 --> 00:50:58,100 porque provavelmente, por esta altura, você está mais confortável do que você estava 1044 00:50:58,100 --> 00:51:01,850 em uma semana com loops ou por loops, mas realmente para provocar uma separação que 1045 00:51:01,850 --> 00:51:04,790 você está um pouco confortável com a noção de que o PHP não é apenas sobre o que 1046 00:51:04,790 --> 00:51:05,290 programação. 1047 00:51:05,290 --> 00:51:07,820 Na verdade, pode ser usado como uma linguagem para escrever programas de linha de comando. 1048 00:51:07,820 --> 00:51:10,060 >> E, de fato, é o que nós estávamos tentando de chamar a atenção. 1049 00:51:10,060 --> 00:51:12,060 Este é um programa para a linha de comando. 1050 00:51:12,060 --> 00:51:16,690 Então código C aqui, enquanto correta em C, não corrigir para PHP. 1051 00:51:16,690 --> 00:51:17,940 Mas o código é realmente o mesmo. 1052 00:51:17,940 --> 00:51:21,720 Se você comparar as soluções para Teste 0 contra o Teste 1, você verá que 1053 00:51:21,720 --> 00:51:25,630 é quase idêntico, exceto por alguns sinais de dólar e para o 1054 00:51:25,630 --> 00:51:27,250 ausência de um tipo de dados. 1055 00:51:27,250 --> 00:51:31,720 Em particular, se dermos uma olhada aqui, você verá que nós iteração, neste 1056 00:51:31,720 --> 00:51:33,730 caso, de 1 a 7. 1057 00:51:33,730 --> 00:51:34,910 >> Poderíamos ter feito isso 0 índice. 1058 00:51:34,910 --> 00:51:37,320 Mas, às vezes, eu acho que é apenas mentalmente mais fácil pensar sobre as coisas 1059 00:51:37,320 --> 00:51:38,200 de 1 a 7. 1060 00:51:38,200 --> 00:51:40,300 Se você quiser um bloco, depois dois blocos, em seguida, três, então 1061 00:51:40,300 --> 00:51:41,770 ponto, ponto, ponto sete. 1062 00:51:41,770 --> 00:51:45,960 Temos j sendo inicializado a 1 e, em seguida, contando com até i. 1063 00:51:45,960 --> 00:51:48,150 E tudo aqui é de outro modo idêntica. 1064 00:51:48,150 --> 00:51:49,790 Mas digno de nota são um par de coisas. 1065 00:51:49,790 --> 00:51:53,230 Nós damos-lhe estas duas linhas, esta primeira um, goofily nomeado como um shebang 1066 00:51:53,230 --> 00:51:54,560 para estrondo afiada. 1067 00:51:54,560 --> 00:51:58,770 E isso só especifica o caminho, a pasta, em que um programa pode ser 1068 00:51:58,770 --> 00:52:02,160 descobri que você quer usar para interpretar esse arquivo. 1069 00:52:02,160 --> 00:52:04,710 >> E, em seguida, a linha de, depois disso, de claro, significa entrar no modo PHP. 1070 00:52:04,710 --> 00:52:07,740 E a linha na parte inferior significa sair do modo PHP. 1071 00:52:07,740 --> 00:52:09,740 E esta funciona, em geral, com linguagens interpretadas. 1072 00:52:09,740 --> 00:52:14,370 É uma espécie de irritante se você escrever um programa em um arquivo chamado foo.php. 1073 00:52:14,370 --> 00:52:17,320 E, em seguida, os utilizadores têm apenas lembre-se, OK, para executar este programa, eu 1074 00:52:17,320 --> 00:52:22,320 tem que digitar "espaço php foo.php". Tipo de chato se nada mais. 1075 00:52:22,320 --> 00:52:25,270 E também revela que o seu programa É escrito em PHP, que não é de todo 1076 00:52:25,270 --> 00:52:27,060 que ilumina para o usuário. 1077 00:52:27,060 --> 00:52:30,100 >> Assim, você pode remover os arquivos. Php completamente lembrar da aula. 1078 00:52:30,100 --> 00:52:35,690 E você pode realmente fazer. / Foo se você chmodded lo, tornando-o 1079 00:52:35,690 --> 00:52:36,500 executável. 1080 00:52:36,500 --> 00:52:39,630 Então chmod a + x foo teria feito isso. 1081 00:52:39,630 --> 00:52:41,460 E se você também adicionar a coisa toda aqui. 1082 00:52:41,460 --> 00:52:45,320 Mas, realmente, o problema estava chegando imprimir algo como isto. 1083 00:52:45,320 --> 00:52:51,100 No HTML, sem C-código certamente, apenas algumas PHP. 1084 00:52:51,100 --> 00:52:54,100 Então, Milo depois voltou em 25 problema. 1085 00:52:54,100 --> 00:52:58,050 E em 25, você recebeu o seguinte código de esqueleto, o qual era um 1086 00:52:58,050 --> 00:52:59,730 página web muito simples. 1087 00:52:59,730 --> 00:53:04,230 E a parte suculenta HTML-wise foi para baixo aqui, onde nós temos dentro do corpo 1088 00:53:04,230 --> 00:53:09,160 uma forma que tem identificação única de insumos no interior do qual foi duas entradas, uma 1089 00:53:09,160 --> 00:53:11,950 com uma idéia de nome, um com uma idéia de botão. 1090 00:53:11,950 --> 00:53:14,240 >> O primeiro foi o tipo de texto, o segundo do tipo de envio. 1091 00:53:14,240 --> 00:53:16,930 E, assim, deu-lhe, na verdade, mais ingredientes que você precisava, só assim 1092 00:53:16,930 --> 00:53:19,230 vocês tinham opções com as quais para resolver este problema. 1093 00:53:19,230 --> 00:53:21,130 Você não precisa estritamente todas estas identificações. 1094 00:53:21,130 --> 00:53:23,580 Mas permite que você resolva isso de diferentes maneiras. 1095 00:53:23,580 --> 00:53:27,050 E no topo, observe que o objetivo foi desencadear 1096 00:53:27,050 --> 00:53:27,960 uma janela como esta - 1097 00:53:27,960 --> 00:53:28,780 Olá, Milo! - 1098 00:53:28,780 --> 00:53:31,270 de pop-up no navegador usando o super simples, se 1099 00:53:31,270 --> 00:53:33,190 , a função de alerta não feia. 1100 00:53:33,190 --> 00:53:37,480 E assim, em última instância, isto resume-se conceitualmente de alguma forma, escutando 1101 00:53:37,480 --> 00:53:41,290 submissões de client-side a forma , Não o lado do servidor, de alguma forma 1102 00:53:41,290 --> 00:53:45,640 responder a essa submissão por agarrando o valor que o usuário digitou 1103 00:53:45,640 --> 00:53:50,120 para o campo de nome e, em seguida, exibi-la no corpo de um alerta. 1104 00:53:50,120 --> 00:53:53,460 >> Assim, uma forma de fazer isso é com jQuery, que se parece um pouco 1105 00:53:53,460 --> 00:53:56,880 sintaticamente desconcertante no início. 1106 00:53:56,880 --> 00:54:00,760 Você pode fazer isso com o código DOM pura - document.getelement por ID. 1107 00:54:00,760 --> 00:54:02,530 Mas vamos dar uma olhada nesta versão. 1108 00:54:02,530 --> 00:54:05,110 Eu tenho um par de importantes linhas primeiro. 1109 00:54:05,110 --> 00:54:09,460 Então, um, temos esta linha, que é idêntico ao que você pode ter visto 1110 00:54:09,460 --> 00:54:13,830 em, creio, form2.html de classe na semana 9. 1111 00:54:13,830 --> 00:54:16,960 E este é apenas dizer, execute o código a seguir quando 1112 00:54:16,960 --> 00:54:18,430 o documento está pronto. 1113 00:54:18,430 --> 00:54:21,770 Esta sendo importante apenas porque Páginas HTML são lidas de cima para 1114 00:54:21,770 --> 00:54:23,280 baixo, da esquerda para a direita. 1115 00:54:23,280 --> 00:54:27,910 >> E, portanto, se você tentar fazer algo em código-se aqui para alguns DOM 1116 00:54:27,910 --> 00:54:31,560 elemento, alguns tag HTML, que é baixo aqui, você está fazendo isso muito em breve, 1117 00:54:31,560 --> 00:54:34,220 porque este não tem sequer foi lido na memória. 1118 00:54:34,220 --> 00:54:37,740 Então, ao dizer isso document.ready linha, estamos dizendo, 1119 00:54:37,740 --> 00:54:39,040 aqui está um código, browser. 1120 00:54:39,040 --> 00:54:42,440 Mas não executar este até que o todo documento está pronto, que é o DOM 1121 00:54:42,440 --> 00:54:44,320 árvore existe em memória. 1122 00:54:44,320 --> 00:54:47,110 Este é um pouco mais simples, se sintaticamente um 1123 00:54:47,110 --> 00:54:51,890 pouco diferente, onde eu estou dizendo, grab o elemento HTML, cuja única 1124 00:54:51,890 --> 00:54:53,560 identificador é insumos. 1125 00:54:53,560 --> 00:54:56,220 Isso é o que o hash tag denota, o ID único. 1126 00:54:56,220 --> 00:54:58,070 E então eu estou ligando. Enviar. 1127 00:54:58,070 --> 00:55:01,660 >> So. Apresentar aqui é uma função, caso contrário, conhecido como um método, que está 1128 00:55:01,660 --> 00:55:05,850 dentro do objeto na mão esquerda lado, há que eu não destacar. 1129 00:55:05,850 --> 00:55:08,990 Então, se você pensar em entradas como um objeto na memória - e de fato é. 1130 00:55:08,990 --> 00:55:10,440 É um nó em uma árvore - 1131 00:55:10,440 --> 00:55:16,580 . Enviar meios quando este formulário com essa identificação é apresentada, execute 1132 00:55:16,580 --> 00:55:17,700 o código a seguir. 1133 00:55:17,700 --> 00:55:20,290 Eu não me importo o que o nome do função é que estou executando. 1134 00:55:20,290 --> 00:55:23,760 Então, aqui eu estou usando, como antes, o que é chamada a função lambda ou um 1135 00:55:23,760 --> 00:55:24,720 função anônima. 1136 00:55:24,720 --> 00:55:27,640 Não é de todo intelectualmente interessante que não tem nenhum nome, 1137 00:55:27,640 --> 00:55:30,220 o que é bom se você está apenas nunca vai chamá-lo de uma vez. 1138 00:55:30,220 --> 00:55:34,490 E lá dentro eu realmente segurar a apresentação do formulário. 1139 00:55:34,490 --> 00:55:36,810 A primeira vez que declarar uma variável chamado valor. 1140 00:55:36,810 --> 00:55:40,610 E então, qual é o efeito desta realçado parte aqui, agora? 1141 00:55:40,610 --> 00:55:44,755 O que isso faz em um alto nível para mim? 1142 00:55:44,755 --> 00:55:48,539 >> AUDIÊNCIA: Fica o valor que o usuário não fez no HTML abaixo. 1143 00:55:48,539 --> 00:55:50,920 Ela recebe esse ID e, em seguida, verificar que o valor do mesmo. 1144 00:55:50,920 --> 00:55:51,590 >> DAVID J. MALAN: Exatamente. 1145 00:55:51,590 --> 00:55:54,300 Ele agarra o nó, cujo único identificador é o nome. 1146 00:55:54,300 --> 00:55:56,900 Começa o valor nele, o que é, presumivelmente, o que o utilizador 1147 00:55:56,900 --> 00:55:58,190 digitado si mesmo. 1148 00:55:58,190 --> 00:56:01,020 E então ele armazena que no variável chamada valor. 1149 00:56:01,020 --> 00:56:03,720 Como um aparte, você também pode ter sido feito isso um pouco diferente. 1150 00:56:03,720 --> 00:56:09,250 Totalmente aceitável, fazendo algo valor mentira var fica 1151 00:56:09,250 --> 00:56:10,500 document.getElementById. 1152 00:56:10,500 --> 00:56:12,860 1153 00:56:12,860 --> 00:56:15,460 E é por isso que é um pouco tedioso para não usar jQuery. 1154 00:56:15,460 --> 00:56:16,710 "Nome". Valor. 1155 00:56:16,710 --> 00:56:18,330 1156 00:56:18,330 --> 00:56:19,620 Então, totalmente aceitável. 1157 00:56:19,620 --> 00:56:22,770 Diferentes maneiras de fazer isso. jQuery apenas tende a ser um pouco mais sucinto e 1158 00:56:22,770 --> 00:56:25,230 definitivamente mais populares entre os programadores. 1159 00:56:25,230 --> 00:56:27,590 >> Agora, eu estou fazendo um pouco de sanidade verificar, porque no problema 1160 00:56:27,590 --> 00:56:30,820 declaração nos disse explicitamente, se o utilizador ainda não digitado seu 1161 00:56:30,820 --> 00:56:32,580 nome, não mostram uma alertas. 1162 00:56:32,580 --> 00:56:35,390 Mas você pode verificar que, em apenas verificando a cadeia vazia para uma 1163 00:56:35,390 --> 00:56:37,850 entre aspas, se há nada realmente lá. 1164 00:56:37,850 --> 00:56:40,880 Mas se não é igual, entre aspas, Eu quero chamar alertas. 1165 00:56:40,880 --> 00:56:45,610 E a parte interessante aqui é que estamos usando o operador mais, que 1166 00:56:45,610 --> 00:56:48,130 faz o que em JavaScript? 1167 00:56:48,130 --> 00:56:48,740 Concatenar. 1168 00:56:48,740 --> 00:56:50,690 Então, é como operador ponto do PHP. 1169 00:56:50,690 --> 00:56:52,820 A mesma idéia, sintaxe um pouco diferente. 1170 00:56:52,820 --> 00:56:55,280 E eu estou apenas criando a string que você viu na captura de tela - 1171 00:56:55,280 --> 00:56:57,750 Olá, assim e assim. 1172 00:56:57,750 --> 00:56:59,200 >> E então o último detalhe é o seguinte. 1173 00:56:59,200 --> 00:57:04,970 Por que eu return false dentro desta função anônima? 1174 00:57:04,970 --> 00:57:07,420 >> AUDIÊNCIA: Não há nenhum valor. 1175 00:57:07,420 --> 00:57:09,380 Você colocá-lo em forma. 1176 00:57:09,380 --> 00:57:12,320 1177 00:57:12,320 --> 00:57:16,730 Ele apenas diz que, se o valor não é igual em branco, em seguida, fazê-lo. 1178 00:57:16,730 --> 00:57:20,040 1179 00:57:20,040 --> 00:57:20,940 Havia um vazio em que a submissão. 1180 00:57:20,940 --> 00:57:21,170 >> DAVID J. MALAN: OK. 1181 00:57:21,170 --> 00:57:21,640 Cuidado, porém. 1182 00:57:21,640 --> 00:57:22,830 Não há mais ninguém aqui. 1183 00:57:22,830 --> 00:57:25,510 E esse retorno é falso fora do, se as condições. 1184 00:57:25,510 --> 00:57:29,470 Então esta linha destacada, retornar false, executa, não importa o quando 1185 00:57:29,470 --> 00:57:32,310 o formulário é enviado. 1186 00:57:32,310 --> 00:57:36,810 O que faz retornar false dentro deste manipulador de eventos, como é chamado, 1187 00:57:36,810 --> 00:57:38,450 o evento em questão sendo submissão? 1188 00:57:38,450 --> 00:57:42,350 1189 00:57:42,350 --> 00:57:44,470 >> AUDIÊNCIA: Porque só acontece uma vez. 1190 00:57:44,470 --> 00:57:45,320 >> DAVID J. MALAN: só acontece uma vez. 1191 00:57:45,320 --> 00:57:46,821 Não é bem assim. 1192 00:57:46,821 --> 00:57:47,292 Sim? 1193 00:57:47,292 --> 00:57:50,589 >> AUDIÊNCIA: Ela impede que a forma de submetendo-se o comportamento padrão, 1194 00:57:50,589 --> 00:57:52,480 o que tornaria o recarregamento da página. 1195 00:57:52,480 --> 00:57:53,110 >> DAVID J. MALAN: Exatamente. 1196 00:57:53,110 --> 00:57:56,490 Então, eu estou sobrecarregando o prazo apresentar aqui, porque eu estou dizendo, é a forma 1197 00:57:56,490 --> 00:57:57,670 sendo submetido. 1198 00:57:57,670 --> 00:58:02,240 Mas, como você sugere, na verdade não é foi apresentado no verdadeiro caminho HTTP. 1199 00:58:02,240 --> 00:58:06,870 Ao clicar em Enviar, por causa da nossa manipulador onSubmit, estamos interceptando 1200 00:58:06,870 --> 00:58:09,040 que a submissão do formulário, por assim dizer. 1201 00:58:09,040 --> 00:58:11,290 Estamos então a fazer o nosso coisa com código JavaScript. 1202 00:58:11,290 --> 00:58:14,070 Mas eu estou voltando deliberadamente falsa, porque o que eu não quero que aconteça um 1203 00:58:14,070 --> 00:58:18,430 fração de segundo depois é para toda a forma -se a ser submetido à web 1204 00:58:18,430 --> 00:58:22,800 servidor com pares de valores-chave, alterando a URL para ser algo como 1205 00:58:22,800 --> 00:58:26,180 q = gatos ou qualquer outra coisa que fizemos, por exemplo, em sala de aula. 1206 00:58:26,180 --> 00:58:29,640 Eu não quero que isso aconteça, porque não há nenhuma escuta servidor para esta 1207 00:58:29,640 --> 00:58:30,690 formar submissão. 1208 00:58:30,690 --> 00:58:32,320 É puramente em código JavaScript. 1209 00:58:32,320 --> 00:58:35,760 E é por isso que eu não tinha sequer um atributo action no meu formulário, porque eu 1210 00:58:35,760 --> 00:58:38,870 Não pretendo que isso sempre ir para o servidor. 1211 00:58:38,870 --> 00:58:40,780 >> Então, ele está sendo submetido. 1212 00:58:40,780 --> 00:58:44,340 Mas estamos interceptando que forma submissão e impedindo que o padrão 1213 00:58:44,340 --> 00:58:47,477 comportamento, o que é na verdade percorrer todo o caminho para o servidor. 1214 00:58:47,477 --> 00:58:48,730 >> AUDIÊNCIA: Então mantê-lo do lado do cliente. 1215 00:58:48,730 --> 00:58:49,780 >> DAVID J. MALAN: Mantendo do lado do cliente dele. 1216 00:58:49,780 --> 00:58:51,030 Exatamente. 1217 00:58:51,030 --> 00:58:53,240 1218 00:58:53,240 --> 00:58:55,757 Em seguida foi a minha oh MySQL. 1219 00:58:55,757 --> 00:59:00,000 1220 00:59:00,000 --> 00:59:00,430 >> ROB BOWDEN: OK. 1221 00:59:00,430 --> 00:59:04,990 Portanto, esta primeira pergunta foi, em geral áspero para as pessoas. 1222 00:59:04,990 --> 00:59:07,270 Embora os posteriores foi melhor. 1223 00:59:07,270 --> 00:59:12,260 Então você tinha que escolher os dados corretos tipos de ambas as colunas. 1224 00:59:12,260 --> 00:59:17,750 E ambos têm alguns coisas sobre eles que 1225 00:59:17,750 --> 00:59:20,620 fazer a escolha difícil. 1226 00:59:20,620 --> 00:59:24,430 Então int não era um válido tipo de número. 1227 00:59:24,430 --> 00:59:29,410 A razão de ser de uma conta de 12 dígitos número, um int não é grande o suficiente para 1228 00:59:29,410 --> 00:59:31,070 armazenar totais dígitos. 1229 00:59:31,070 --> 00:59:36,570 Assim, uma opção válida teria sido um grande int se acontecer de você saber disso. 1230 00:59:36,570 --> 00:59:42,090 Outra opção poderia ter sido um campo de caractere de comprimento 12. 1231 00:59:42,090 --> 00:59:44,560 Assim, ou daqueles teria funcionado. 1232 00:59:44,560 --> 00:59:46,100 Int não. 1233 00:59:46,100 --> 00:59:50,170 >> Agora, o equilíbrio, acho que volta para pset7. 1234 00:59:50,170 --> 00:59:59,540 Assim, especificamente usado para decimal armazenar o valor de ações ou - 1235 00:59:59,540 --> 01:00:00,550 >> DAVID J. MALAN: Dinheiro. 1236 01:00:00,550 --> 01:00:01,060 >> ROB BOWDEN: Dinheiro. 1237 01:00:01,060 --> 01:00:05,710 Usamos decimal para armazenar a quantidade de dinheiro que o usuário possui atualmente. 1238 01:00:05,710 --> 01:00:10,950 Assim, a razão pela qual fazemos isso é porque, lembre-se, flutua. 1239 01:00:10,950 --> 01:00:12,480 Há de ponto flutuante de precisão. 1240 01:00:12,480 --> 01:00:18,200 Ele não pode precisamente armazenar o dinheiro valores como nós queremos aqui. 1241 01:00:18,200 --> 01:00:23,630 Então decimal é capaz de precisão loja algo, digamos, duas casas decimais. 1242 01:00:23,630 --> 01:00:27,630 É por isso que o equilíbrio, nós queremos que ele ser decimal e não flutuam. 1243 01:00:27,630 --> 01:00:30,230 >> DAVID J. MALAN: E também, também, embora que poderia ter sido inteligente em outro 1244 01:00:30,230 --> 01:00:32,760 contextos para pensar, talvez esta é uma oportunidade para um int. 1245 01:00:32,760 --> 01:00:34,420 Eu vou manter o controle de coisas em moedas de um centavo. 1246 01:00:34,420 --> 01:00:38,670 Porque nós explicitamente mostrou o padrão valor de ser 100.00, que 1247 01:00:38,670 --> 01:00:40,380 significa que poderia ser apenas um int. 1248 01:00:40,380 --> 01:00:45,310 E outra sutileza também com o número de foi que ele não foi feito 1249 01:00:45,310 --> 01:00:46,180 para ser uma pegadinha. 1250 01:00:46,180 --> 01:00:49,860 Mas lembre-se que um int em MySQL, como em C, pelo menos na 1251 01:00:49,860 --> 01:00:51,440 aparelho, é de 32 bits. 1252 01:00:51,440 --> 01:00:53,960 E mesmo que nós não esperamos que você saber exatamente quantos dígitos que 1253 01:00:53,960 --> 01:00:56,910 meios, me lembro que o maior número você pode representar potencialmente 1254 01:00:56,910 --> 01:01:00,710 com um número de 32 bits é mais ou menos o quê? 1255 01:01:00,710 --> 01:01:02,760 >> Qual o número que nós sempre diz? 1256 01:01:02,760 --> 01:01:04,530 2 a 32, que é o que mais ou menos? 1257 01:01:04,530 --> 01:01:07,492 1258 01:01:07,492 --> 01:01:08,780 Você não tem que saber com precisão. 1259 01:01:08,780 --> 01:01:10,580 Mas mais ou menos é útil na vida. 1260 01:01:10,580 --> 01:01:12,200 É cerca de 4 bilhões de dólares. 1261 01:01:12,200 --> 01:01:14,430 Então nós dissemos que algumas vezes. 1262 01:01:14,430 --> 01:01:16,360 Eu sei que eu já disse isso algumas vezes. 1263 01:01:16,360 --> 01:01:17,670 E é mais ou menos 4 bilhões. 1264 01:01:17,670 --> 01:01:19,710 E isso é uma boa regra de ouro para saber. 1265 01:01:19,710 --> 01:01:21,880 Se você tem 8 bits, 256 é o número mágico. 1266 01:01:21,880 --> 01:01:24,160 Se você tiver 32 bits, 4 bilhões mais ou menos. 1267 01:01:24,160 --> 01:01:27,140 Então, se você acabou de escrever 4 bilhões, você vai ver que é menos dígitos do que 1268 01:01:27,140 --> 01:01:30,970 12, o que significa que não é claramente expressividade o suficiente para capturar uma 1269 01:01:30,970 --> 01:01:34,220 Número de conta de 12 dígitos. 1270 01:01:34,220 --> 01:01:34,940 >> ROB BOWDEN: OK. 1271 01:01:34,940 --> 01:01:38,520 Então, os outros correram melhor. 1272 01:01:38,520 --> 01:01:40,900 Então suponho que o banco impõe uma mensal $ 20 1273 01:01:40,900 --> 01:01:42,400 taxa de manutenção em todas as contas. 1274 01:01:42,400 --> 01:01:45,506 Com que consulta SQL poderia o banco deduzir $ 20 a partir de cada contagem, mesmo se 1275 01:01:45,506 --> 01:01:47,520 que resulta em alguns saldos negativos? 1276 01:01:47,520 --> 01:01:50,380 Então, basicamente, há quatro principais tipos de consultas - 1277 01:01:50,380 --> 01:01:52,840 inserir, selecionar, atualizar e excluir. 1278 01:01:52,840 --> 01:01:56,080 Então, o que nós pensamos que somos vai usar aqui? 1279 01:01:56,080 --> 01:01:57,000 Atualize. 1280 01:01:57,000 --> 01:01:58,260 >> Então, vamos dar uma olhada. 1281 01:01:58,260 --> 01:02:04,290 1282 01:02:04,290 --> 01:02:05,870 Então, aqui estamos atualizando. 1283 01:02:05,870 --> 01:02:09,900 O quadro que estamos atualizando as contas? 1284 01:02:09,900 --> 01:02:11,670 Então atualizando contas. 1285 01:02:11,670 --> 01:02:15,390 E então a sintaxe diz, o que em contas estamos atualizando? 1286 01:02:15,390 --> 01:02:19,520 Bem, nós estamos estabelecendo equilíbrio igual ao valor atual de equilíbrio menos 20. 1287 01:02:19,520 --> 01:02:22,860 Então, isso vai atualizar todas as linhas de contas, subtraindo 1288 01:02:22,860 --> 01:02:26,250 20 $ a partir do equilíbrio. 1289 01:02:26,250 --> 01:02:29,260 >> DAVID J. MALAN: Um erro comum aqui, mesmo que, por vezes, perdoou-o, 1290 01:02:29,260 --> 01:02:32,990 era, na verdade, tem o código PHP aqui chamando a função de consulta ou colocar 1291 01:02:32,990 --> 01:02:35,460 aspas em torno de tudo o que não precisa estar lá. 1292 01:02:35,460 --> 01:02:39,780 >> ROB BOWDEN: Lembre-se que o MySQL é uma língua separada do PHP. 1293 01:02:39,780 --> 01:02:42,410 Temos que ser escrito MySQL em PHP. 1294 01:02:42,410 --> 01:02:46,180 E PHP é, então, enviá-lo para o servidor MySQL. 1295 01:02:46,180 --> 01:02:51,120 Mas você não precisa de PHP, a fim de comunicar com um servidor MySQL. 1296 01:02:51,120 --> 01:02:51,730 >> DAVID J. MALAN: Exatamente. 1297 01:02:51,730 --> 01:02:54,240 Portanto, não variáveis ​​com cifrões deve ser, neste contexto. 1298 01:02:54,240 --> 01:02:59,550 Ele só pode fazer toda a matemática dentro da própria base de dados. 1299 01:02:59,550 --> 01:03:00,080 >> ROB BOWDEN: OK. 1300 01:03:00,080 --> 01:03:01,300 Então a próxima. 1301 01:03:01,300 --> 01:03:02,731 É este o próximo? 1302 01:03:02,731 --> 01:03:03,210 É. 1303 01:03:03,210 --> 01:03:06,570 Assim, com o que poderia consulta SQL do banco recuperar os números de contas de sua 1304 01:03:06,570 --> 01:03:09,300 clientes mais ricos, aqueles com contrapesos maiores do que 1000? 1305 01:03:09,300 --> 01:03:13,280 Assim que um dos quatro tipos principais vamos querer aqui? 1306 01:03:13,280 --> 01:03:14,430 Selecione. 1307 01:03:14,430 --> 01:03:16,650 Por isso, queremos selecionar. 1308 01:03:16,650 --> 01:03:17,610 O que nós queremos para selecionar? 1309 01:03:17,610 --> 01:03:19,380 Qual coluna que queremos selecionar? 1310 01:03:19,380 --> 01:03:20,970 Vamos especificamente deseja para selecionar um número. 1311 01:03:20,970 --> 01:03:23,910 Mas se você disse que estrela, nós também aceitou isso. 1312 01:03:23,910 --> 01:03:25,820 >> Então, escolha o número a partir do que mesa? 1313 01:03:25,820 --> 01:03:26,640 Contas. 1314 01:03:26,640 --> 01:03:28,370 E então a condição que queremos? 1315 01:03:28,370 --> 01:03:30,140 Onde equilíbrio maior que 1.000. 1316 01:03:30,140 --> 01:03:31,720 Também aceito maior ou igual. 1317 01:03:31,720 --> 01:03:35,230 1318 01:03:35,230 --> 01:03:36,190 Último. 1319 01:03:36,190 --> 01:03:42,940 Com que consulta SQL poderia o banco próximo, ou seja, apagar todas as contas que 1320 01:03:42,940 --> 01:03:44,480 tem um saldo de US $ 0? 1321 01:03:44,480 --> 01:03:47,620 Então, qual dos quatro somos nós vai querer usar? 1322 01:03:47,620 --> 01:03:48,320 Excluir. 1323 01:03:48,320 --> 01:03:50,180 Assim, a sintaxe para isso? 1324 01:03:50,180 --> 01:03:51,890 Excluir o quadro? 1325 01:03:51,890 --> 01:03:53,550 Contas. 1326 01:03:53,550 --> 01:03:55,790 E, em seguida, a condição na qual que deseja excluir - 1327 01:03:55,790 --> 01:03:57,280 onde o equilíbrio é igual a zero. 1328 01:03:57,280 --> 01:04:03,050 Então, excluir todas as linhas de contas onde o saldo é zero. 1329 01:04:03,050 --> 01:04:04,300 Perguntas sobre qualquer um desses? 1330 01:04:04,300 --> 01:04:08,840 1331 01:04:08,840 --> 01:04:10,260 Quer fila? 1332 01:04:10,260 --> 01:04:11,200 >> DAVID J. MALAN: guia Fila. 1333 01:04:11,200 --> 01:04:17,110 Então, em um presente, que lhe deu um pouco estrutura familiar que explorou uma 1334 01:04:17,110 --> 01:04:20,450 bit em sala de aula ao lado de estruturas, que foi uma dados 1335 01:04:20,450 --> 01:04:21,910 estrutura relacionada em espírito. 1336 01:04:21,910 --> 01:04:24,670 A diferença, embora com uma fila é que tivemos que lembrar de alguma forma que 1337 01:04:24,670 --> 01:04:27,900 estava na frente da fila, em grande parte para que pudéssemos fazer mais 1338 01:04:27,900 --> 01:04:30,530 utilização eficiente da memória, pelo menos se estivéssemos usando um array. 1339 01:04:30,530 --> 01:04:35,460 >> Porque recall, se temos uma matriz, se, por exemplo, esta é a frente 1340 01:04:35,460 --> 01:04:38,470 fila, se eu entrar na fila aqui, e então alguém entra na fila 1341 01:04:38,470 --> 01:04:42,710 atrás de mim, atrás de mim, atrás de mim, e uma pessoa sai de linha, você 1342 01:04:42,710 --> 01:04:45,930 poderia, como já vimos alguns dos nossos humano voluntários em sala de aula, têm todos 1343 01:04:45,930 --> 01:04:47,100 mudar esta maneira. 1344 01:04:47,100 --> 01:04:50,880 Mas, em geral, depois de ter todos fazer algo não é o melhor uso do tempo 1345 01:04:50,880 --> 01:04:54,600 em um programa, porque isso significa que o seu algoritmo está sendo executado no que 1346 01:04:54,600 --> 01:04:56,520 tempo de execução assintótica? 1347 01:04:56,520 --> 01:04:57,420 É linear. 1348 01:04:57,420 --> 01:04:59,600 >> E eu sinto que esse é o tipo de estúpido. 1349 01:04:59,600 --> 01:05:02,890 Se a próxima pessoa da fila é o próximo pessoa que deveria ir para o 1350 01:05:02,890 --> 01:05:04,660 loja, eles não têm para mover em conjunto. 1351 01:05:04,660 --> 01:05:08,200 Apenas deixe que a pessoa ser arranquei quando chegar a hora, por exemplo. 1352 01:05:08,200 --> 01:05:09,870 Assim, podemos economizar um pouco de tempo lá. 1353 01:05:09,870 --> 01:05:14,840 E assim, para fazer isso, porém, que os meios que o chefe de fila ou o 1354 01:05:14,840 --> 01:05:18,060 frente da fila vai progressivamente se mover mais e mais 1355 01:05:18,060 --> 01:05:23,340 na matriz e, eventualmente, pode realmente envolver em torno de se estamos usando um 1356 01:05:23,340 --> 01:05:25,790 matriz para armazenar as pessoas nesta fila. 1357 01:05:25,790 --> 01:05:28,390 Então você quase pode pensar no matriz como uma dados circular 1358 01:05:28,390 --> 01:05:29,880 estrutura nesse sentido. 1359 01:05:29,880 --> 01:05:33,970 >> Então, de alguma forma você tem que manter o controle do tamanho dele ou realmente o fim de tudo 1360 01:05:33,970 --> 01:05:36,250 e, em seguida, onde o início do que é. 1361 01:05:36,250 --> 01:05:39,490 Assim, propomos que você declarar um tal fila, a chamada 1362 01:05:39,490 --> 01:05:41,330 ele q, apenas uma letra. 1363 01:05:41,330 --> 01:05:44,570 Em seguida, propomos que a frente seja inicializado para zero, e que o tamanho 1364 01:05:44,570 --> 01:05:45,470 ser inicializado para zero. 1365 01:05:45,470 --> 01:05:47,770 >> Então, agora, não há nada dentro dessa fila. 1366 01:05:47,770 --> 01:05:50,910 E pedimos-lhe para completar a implementação de enfileiramento abaixo em 1367 01:05:50,910 --> 01:05:55,250 tal modo que a função adiciona n à a fim de q e, em seguida, devolve verdadeiro. 1368 01:05:55,250 --> 01:05:58,690 Mas se q é completa ou negativa, o função deve retornar false vez. 1369 01:05:58,690 --> 01:06:01,060 E deu-lhe um par de suposições. 1370 01:06:01,060 --> 01:06:04,320 Mas eles não são realmente funcionais relevante, existe apenas que bool, 1371 01:06:04,320 --> 01:06:06,690 porque, tecnicamente, bool não existem em C, a menos que você inclua um 1372 01:06:06,690 --> 01:06:07,310 determinado arquivo de cabeçalho. 1373 01:06:07,310 --> 01:06:09,350 Assim que acabou de se certificar de que não foram este é um truque 1374 01:06:09,350 --> 01:06:10,940 questão tipo de coisa. 1375 01:06:10,940 --> 01:06:16,280 >> Então, enfileiramento, propusemos na amostra As soluções para aplicação como se segue. 1376 01:06:16,280 --> 01:06:20,420 Um, nós primeiro verificar a facilidade, os frutos baixo pendurado. 1377 01:06:20,420 --> 01:06:23,820 Se a fila estiver cheia ou o número que você está tentando inserir é menor 1378 01:06:23,820 --> 01:06:26,380 do que zero, o que dissemos no especificação do problema deve 1379 01:06:26,380 --> 01:06:30,320 não ser permitido, porque nós só queremos valores não negativos, então você deve 1380 01:06:30,320 --> 01:06:31,640 apenas return false imediatamente. 1381 01:06:31,640 --> 01:06:33,820 Assim, alguns relativamente fácil verificação de erros. 1382 01:06:33,820 --> 01:06:38,720 Se que você deseja adicionar que real número, você tinha que fazer um pouco de 1383 01:06:38,720 --> 01:06:39,440 pensando aqui. 1384 01:06:39,440 --> 01:06:41,330 E é aí que é um pouco chato mentalmente, porque você tem que 1385 01:06:41,330 --> 01:06:43,000 descobrir como lidar com a envolvente. 1386 01:06:43,000 --> 01:06:46,870 >> Mas o germe da idéia aqui é de interesse para nós é que a envolvente 1387 01:06:46,870 --> 01:06:51,480 muitas vezes implica aritmética modular e o operador mod, o lado por cento, 1388 01:06:51,480 --> 01:06:55,140 onde você pode ir de um valor maior de volta para zero e, em seguida, um e dois e 1389 01:06:55,140 --> 01:06:58,650 três e, em seguida, de volta ao redor de zero, um e dois e três, e assim por diante 1390 01:06:58,650 --> 01:06:59,380 uma e outra vez. 1391 01:06:59,380 --> 01:07:02,880 Assim, a maneira propomos fazer isso é que queremos índice para a 1392 01:07:02,880 --> 01:07:05,850 array chamado números onde nossos inteiros mentir. 1393 01:07:05,850 --> 01:07:10,740 Mas para chegar lá, primeiro quero fazer seja qual for o tamanho da fila é mas 1394 01:07:10,740 --> 01:07:14,080 em seguida, adicione a isso qualquer que seja a frente da lista é. 1395 01:07:14,080 --> 01:07:17,880 E o efeito que é colocar-nos em a posição certa na fila e 1396 01:07:17,880 --> 01:07:20,970 Não suponha que a primeira pessoa na linha é, no início, que ele ou 1397 01:07:20,970 --> 01:07:24,130 ela absolutamente poderia ser se nós Também foram mudando todos. 1398 01:07:24,130 --> 01:07:26,710 Mas estamos apenas a criação de trabalho para nós mesmos, se nós tomamos 1399 01:07:26,710 --> 01:07:27,800 esse caminho particular. 1400 01:07:27,800 --> 01:07:29,330 >> Assim, podemos mantê-lo relativamente simples. 1401 01:07:29,330 --> 01:07:32,180 Nós temos que lembrar que nós só adicionado um int para a fila. 1402 01:07:32,180 --> 01:07:35,850 E então nós apenas retornar true. 1403 01:07:35,850 --> 01:07:38,560 Enquanto isso, em dequeue, pedimos que você faça o seguinte. 1404 01:07:38,560 --> 01:07:42,260 Implementá-lo de tal forma que removida da fila, ou seja, remove e retorna, 1405 01:07:42,260 --> 01:07:44,190 int na frente da fila. 1406 01:07:44,190 --> 01:07:46,410 Para remover o int, basta esquecê-lo. 1407 01:07:46,410 --> 01:07:47,650 Você não precisa substituir a sua parte. 1408 01:07:47,650 --> 01:07:48,820 Então, ainda é realmente lá. 1409 01:07:48,820 --> 01:07:51,930 Assim como os dados de um disco rígido, estamos apenas ignorando o fato de 1410 01:07:51,930 --> 01:07:52,970 que agora é lá. 1411 01:07:52,970 --> 01:07:55,520 E se q está vazia, devemos em vez retornar negativo 1. 1412 01:07:55,520 --> 01:07:56,750 Então, este se sente arbitrária. 1413 01:07:56,750 --> 01:08:01,640 Por que retornar negativo 1 em vez de falso? 1414 01:08:01,640 --> 01:08:02,620 É. 1415 01:08:02,620 --> 01:08:05,070 >> AUDIÊNCIA: Q está armazenando valores positivos. 1416 01:08:05,070 --> 01:08:10,950 Desde que você só armazenar valores positivos no q, negativo é um erro. 1417 01:08:10,950 --> 01:08:11,510 >> DAVID J. MALAN: OK, é verdade. 1418 01:08:11,510 --> 01:08:14,850 Então porque nós só estamos armazenando positivo valores ou zero, então não há problema em 1419 01:08:14,850 --> 01:08:18,050 retornar um valor negativo como uma sentinela valor, um símbolo especial. 1420 01:08:18,050 --> 01:08:21,630 Mas você está reescrevendo a história lá, porque a razão estamos apenas 1421 01:08:21,630 --> 01:08:25,890 retornando valores não negativos é porque queremos 1422 01:08:25,890 --> 01:08:27,670 tem um valor de sentinela. 1423 01:08:27,670 --> 01:08:32,617 Então, mais especificamente, porque não basta return false em caso de erro? 1424 01:08:32,617 --> 01:08:33,099 É. 1425 01:08:33,099 --> 01:08:35,510 >> AUDIÊNCIA: Você falhou para retornar um inteiro. 1426 01:08:35,510 --> 01:08:36,630 >> DAVID J. MALAN: Exatamente. 1427 01:08:36,630 --> 01:08:38,569 E é aí que fica C muito constrangedor. 1428 01:08:38,569 --> 01:08:40,590 Se você está dizendo que você está indo para retornar um int, você tem 1429 01:08:40,590 --> 01:08:41,279 para retornar um int. 1430 01:08:41,279 --> 01:08:43,689 Você não pode começar a fantasia e começar a retornar um booleano ou um float ou um 1431 01:08:43,689 --> 01:08:45,040 corda ou algo parecido. 1432 01:08:45,040 --> 01:08:49,370 Agora, entretanto, JavaScript e PHP e algumas outras línguas pode, de fato, 1433 01:08:49,370 --> 01:08:51,310 você retornar diferente tipos de valores. 1434 01:08:51,310 --> 01:08:54,819 E isso pode ser realmente útil, onde você poderia retornar ints positivas, zeros, 1435 01:08:54,819 --> 01:08:59,439 ints negativos ou falso ou nulo mesmo para significar erro. 1436 01:08:59,439 --> 01:09:01,890 Mas não temos que versatilidade em C. 1437 01:09:01,890 --> 01:09:04,569 >> Assim, com dequeue, o que propor a fazer é - 1438 01:09:04,569 --> 01:09:07,350 1439 01:09:07,350 --> 01:09:09,830 >> ROB BOWDEN: Você pode retornar false. 1440 01:09:09,830 --> 01:09:13,189 É só que falsa é de hash definir falso para zero. 1441 01:09:13,189 --> 01:09:16,000 Então, se você retornar false, você está retornando zero. 1442 01:09:16,000 --> 01:09:25,470 E zero é uma coisa válida na nossa fila, enquanto que um negativo não é se 1443 01:09:25,470 --> 01:09:27,000 falsa passou a ser negativo 1. 1444 01:09:27,000 --> 01:09:29,972 Mas você não deve mesmo precisa saber disso. 1445 01:09:29,972 --> 01:09:32,399 >> DAVID J. MALAN: Isso é por isso que eu não disse isso. 1446 01:09:32,399 --> 01:09:36,450 >> ROB BOWDEN: Mas não era verdade que você não pode retornar false. 1447 01:09:36,450 --> 01:09:37,700 >> DAVID J. MALAN: Claro. 1448 01:09:37,700 --> 01:09:40,920 1449 01:09:40,920 --> 01:09:44,240 Então dequeue, observe que aceitamos invalidar como seu argumento. 1450 01:09:44,240 --> 01:09:45,479 E isso é porque não somos passar nada dentro 1451 01:09:45,479 --> 01:09:48,359 Nós apenas queremos remover o elemento na parte da frente da fila. 1452 01:09:48,359 --> 01:09:49,819 Então, como podemos fazer sobre isso? 1453 01:09:49,819 --> 01:09:51,290 Bem, primeiro, vamos fazer isso verificação de sanidade rápida. 1454 01:09:51,290 --> 01:09:53,350 Se o tamanho da fila é de 0, não há nenhum trabalho a ser feito. 1455 01:09:53,350 --> 01:09:54,210 Retorno negativo 1. 1456 01:09:54,210 --> 01:09:54,800 Concluído. 1457 01:09:54,800 --> 01:09:56,340 Então, isso é algumas linhas de meu programa. 1458 01:09:56,340 --> 01:09:58,180 Assim, apenas quatro linhas permanecem. 1459 01:09:58,180 --> 01:10:01,310 >> Então, aqui eu decidir diminuir o tamanho. 1460 01:10:01,310 --> 01:10:04,620 E diminuindo o tamanho eficaz significa que eu estou esquecendo 1461 01:10:04,620 --> 01:10:06,010 algo está lá. 1462 01:10:06,010 --> 01:10:09,910 Mas também tenho de atualizar onde a frente são os números. 1463 01:10:09,910 --> 01:10:11,620 Então, para fazer isso, eu preciso fazer duas coisas. 1464 01:10:11,620 --> 01:10:16,390 Eu primeiro preciso lembrar que o número está na frente da fila, 1465 01:10:16,390 --> 01:10:17,860 porque eu preciso voltar aquela coisa. 1466 01:10:17,860 --> 01:10:20,910 Então eu não quero esquecer acidentalmente sobre ele e, em seguida, substituí-lo. 1467 01:10:20,910 --> 01:10:22,840 Eu só vou lembrar de um int. 1468 01:10:22,840 --> 01:10:27,310 >> E agora, eu quero atualizar q.front ser q.front 1. 1469 01:10:27,310 --> 01:10:30,070 Portanto, se esta foi a primeira pessoa em linha, agora, eu quero fazer mais 1 para 1470 01:10:30,070 --> 01:10:31,930 apontar para a próxima pessoa na fila. 1471 01:10:31,930 --> 01:10:33,420 Mas eu tenho que lidar com isso envolvente. 1472 01:10:33,420 --> 01:10:37,270 E se a capacidade é uma constante global, que vai permitir-me para certificar-se 1473 01:10:37,270 --> 01:10:41,140 como eu apontar para a última pessoa em linha, a operação do módulo irá trazer 1474 01:10:41,140 --> 01:10:43,840 me de volta a zero no frente da fila. 1475 01:10:43,840 --> 01:10:46,050 E que manipula a envolvente aqui. 1476 01:10:46,050 --> 01:10:48,950 E então eu proceder para retornar n. 1477 01:10:48,950 --> 01:10:51,530 >> Agora, a rigor, não o fiz tem que declarar n. 1478 01:10:51,530 --> 01:10:53,880 Eu não tenho que agarrá-lo e armazená-lo temporariamente, porque o valor é 1479 01:10:53,880 --> 01:10:54,740 ainda está lá. 1480 01:10:54,740 --> 01:10:57,490 Então, eu poderia apenas fazer a aritmética direita para retornar o ex-chefe 1481 01:10:57,490 --> 01:10:58,450 da fila. 1482 01:10:58,450 --> 01:11:01,850 Mas eu senti que este era mais clara para realmente pegar o int, colocá-lo 1483 01:11:01,850 --> 01:11:04,320 em n, e depois voltar que por uma questão de clareza, mas 1484 01:11:04,320 --> 01:11:05,735 não estritamente necessário. 1485 01:11:05,735 --> 01:11:09,313 1486 01:11:09,313 --> 01:11:12,130 Psst. 1487 01:11:12,130 --> 01:11:13,410 Eles são todos pronunciável na minha cabeça. 1488 01:11:13,410 --> 01:11:15,940 1489 01:11:15,940 --> 01:11:19,110 >> ROB BOWDEN: Então, primeira pergunta é o problema de árvore binária. 1490 01:11:19,110 --> 01:11:22,140 Então, primeira pergunta é, nós somos dado a esses números. 1491 01:11:22,140 --> 01:11:27,160 E queremos inseri-los de alguma forma em destes nós de modo a que ele é um 1492 01:11:27,160 --> 01:11:30,110 válido árvore de busca binária. 1493 01:11:30,110 --> 01:11:36,260 Então a única coisa a lembrar sobre árvores de busca binária é que ele não é 1494 01:11:36,260 --> 01:11:39,800 só que a coisa para a esquerda é menor e a coisa a 1495 01:11:39,800 --> 01:11:41,120 o direito é maior. 1496 01:11:41,120 --> 01:11:44,580 Ele precisa ser que toda a árvore para esquerda é menor, e toda a árvore 1497 01:11:44,580 --> 01:11:45,740 à direita é maior. 1498 01:11:45,740 --> 01:11:55,260 >> Então, se eu colocar 34 aqui no topo, e depois Eu coloquei 20 aqui, então isso é válido para que 1499 01:11:55,260 --> 01:11:56,970 agora, porque 34 por aqui. 1500 01:11:56,970 --> 01:11:57,920 20 vai para a esquerda. 1501 01:11:57,920 --> 01:11:58,950 Então, isso é menos. 1502 01:11:58,950 --> 01:12:03,640 Mas eu não posso então colocar 59 aqui, porque embora 59 está à direita, de 20, 1503 01:12:03,640 --> 01:12:06,140 ele ainda está à esquerda do 34. 1504 01:12:06,140 --> 01:12:10,760 Assim, com essa restrição em mente, o maneira mais fácil de resolver este provavelmente 1505 01:12:10,760 --> 01:12:14,330 problema é apenas uma espécie destes números - 1506 01:12:14,330 --> 01:12:18,720 então 20, 34, 36, 52, 59, 106. 1507 01:12:18,720 --> 01:12:21,640 E, em seguida, insira-os da esquerda para a direita. 1508 01:12:21,640 --> 01:12:23,390 >> Então 20 vai aqui. 1509 01:12:23,390 --> 01:12:24,630 34 vai aqui. 1510 01:12:24,630 --> 01:12:25,830 36 vai aqui. 1511 01:12:25,830 --> 01:12:29,360 52, 59, 106. 1512 01:12:29,360 --> 01:12:34,730 E você também pode ter descoberto com alguns ligar e perceber, 1513 01:12:34,730 --> 01:12:38,830 Oh, espere, eu não tenho números suficientes para preencher esta em mais aqui. 1514 01:12:38,830 --> 01:12:42,170 Então eu preciso que meu reshift rota nota vai ser. 1515 01:12:42,170 --> 01:12:47,490 Mas note que em três finais, se você lê da esquerda para a direita, é no 1516 01:12:47,490 --> 01:12:48,740 ordem crescente. 1517 01:12:48,740 --> 01:12:52,150 1518 01:12:52,150 --> 01:12:56,540 >> Então, agora, queremos declarar que a struct vai ser para o 1519 01:12:56,540 --> 01:12:58,300 nós nesta árvore. 1520 01:12:58,300 --> 01:13:02,720 Então o que precisamos em uma árvore binária? 1521 01:13:02,720 --> 01:13:05,830 Portanto, temos um valor de tipo int, de modo algum valor int. 1522 01:13:05,830 --> 01:13:07,220 Eu não sei o que chamamos -o na solução - 1523 01:13:07,220 --> 01:13:08,500 int n. 1524 01:13:08,500 --> 01:13:13,570 Precisamos de um ponteiro para o filho esquerdo e um ponteiro para o filho direito. 1525 01:13:13,570 --> 01:13:17,540 Então ele vai ficar assim. 1526 01:13:17,540 --> 01:13:20,510 E vai realmente olhar antes quando é que o duplamente vinculada 1527 01:13:20,510 --> 01:13:25,090 lista coisas, então aviso - 1528 01:13:25,090 --> 01:13:27,860 Eu vou ter que percorrer todo o caminho de volta para o problema 11. 1529 01:13:27,860 --> 01:13:30,980 1530 01:13:30,980 --> 01:13:36,390 >> Então, observe que parece idêntica a esta, exceto que só acontecerá a chamar estes 1531 01:13:36,390 --> 01:13:38,590 nomes diferentes. 1532 01:13:38,590 --> 01:13:41,440 Nós ainda temos um número inteiro valor e dois ponteiros. 1533 01:13:41,440 --> 01:13:44,850 É só que, em vez de tratar a ponteiros como apontar para a próxima coisa 1534 01:13:44,850 --> 01:13:47,955 e do anterior, estamos tratando os ponteiros para apontar para um filho esquerdo 1535 01:13:47,955 --> 01:13:49,205 e filho direito. 1536 01:13:49,205 --> 01:13:57,372 1537 01:13:57,372 --> 01:13:57,860 OK. 1538 01:13:57,860 --> 01:13:59,650 Então, esse é o nosso nó struct. 1539 01:13:59,650 --> 01:14:03,920 E agora, a única função que precisamos implementar para isso é transversal, que 1540 01:14:03,920 --> 01:14:08,320 queremos passar por cima da árvore, a impressão os valores da árvore de ordem. 1541 01:14:08,320 --> 01:14:15,241 >> Então, olhando aqui, gostaríamos de imprimir a 20, 34, 36, 52, 59 e 106. 1542 01:14:15,241 --> 01:14:17,970 Como é que vamos conseguir isso? 1543 01:14:17,970 --> 01:14:18,890 Portanto, é bastante similar. 1544 01:14:18,890 --> 01:14:22,910 Se você viu no exame passado o problema que você queria imprimir 1545 01:14:22,910 --> 01:14:25,940 toda a árvore com vírgulas entre tudo, era, na verdade, até mesmo 1546 01:14:25,940 --> 01:14:27,320 mais fácil do que isso. 1547 01:14:27,320 --> 01:14:30,950 Então aqui está a solução. 1548 01:14:30,950 --> 01:14:33,110 Isto era significativamente mais fácil se você fez isso de forma recursiva. 1549 01:14:33,110 --> 01:14:36,650 Eu não sei se alguém tentou para fazê-lo de forma iterativa. 1550 01:14:36,650 --> 01:14:38,340 >> Mas, primeiro, temos o nosso caso base. 1551 01:14:38,340 --> 01:14:39,660 E se a raiz é nulo? 1552 01:14:39,660 --> 01:14:40,610 Então, nós apenas estamos indo para retornar. 1553 01:14:40,610 --> 01:14:42,300 Nós não queremos para imprimir qualquer coisa. 1554 01:14:42,300 --> 01:14:45,940 Else vamos atravessar recursivamente para baixo. 1555 01:14:45,940 --> 01:14:48,140 Imprima toda a subárvore esquerda. 1556 01:14:48,140 --> 01:14:51,440 Então imprimir tudo menos que o meu valor atual. 1557 01:14:51,440 --> 01:14:53,930 E então eu vou me imprimir. 1558 01:14:53,930 --> 01:14:57,310 E então eu estou indo para a minha recursão toda subárvore direita, então tudo 1559 01:14:57,310 --> 01:14:58,810 maior do que o meu valor. 1560 01:14:58,810 --> 01:15:03,870 E isso vai imprimir tudo em ordem. 1561 01:15:03,870 --> 01:15:05,860 Perguntas sobre como isso realmente realiza isso? 1562 01:15:05,860 --> 01:15:09,892 1563 01:15:09,892 --> 01:15:12,545 >> AUDIÊNCIA: Eu tenho uma pergunta no [inaudível]. 1564 01:15:12,545 --> 01:15:15,090 1565 01:15:15,090 --> 01:15:23,550 >> ROB BOWDEN: Portanto, uma forma de se aproximar qualquer problema recursivo é só pensar 1566 01:15:23,550 --> 01:15:26,275 sobre ele gostar de você tem que pensar sobre todos os casos de canto. 1567 01:15:26,275 --> 01:15:32,150 1568 01:15:32,150 --> 01:15:38,110 Por isso, considero que queremos imprimir esta árvore inteira. 1569 01:15:38,110 --> 01:15:42,030 Então, todos nós estamos indo focalizar em é este nó específico - 1570 01:15:42,030 --> 01:15:43,740 36. 1571 01:15:43,740 --> 01:15:47,420 As chamadas recursivas, nós fingimos aqueles apenas trabalhar. 1572 01:15:47,420 --> 01:15:54,000 Então, aqui, esta chamada recursiva para transversal, que, sem sequer pensar 1573 01:15:54,000 --> 01:15:58,640 sobre isso, apenas atravessando a esquerda três, imagine que já imprime 20 1574 01:15:58,640 --> 01:16:00,730 e 34 para nós. 1575 01:16:00,730 --> 01:16:03,350 E então, quando finalmente, de forma recursiva chamar travessia sobre o 1576 01:16:03,350 --> 01:16:07,890 direita, que irá imprimir corretamente 52, 59, e 106 para nós. 1577 01:16:07,890 --> 01:16:13,620 >> Assim, dado que esta pode imprimir 20, 34, e o outro pode imprimir 52, 59, 108, 1578 01:16:13,620 --> 01:16:17,180 tudo o que precisamos para ser capaz de fazer é imprimir nós mesmos, no meio disso. 1579 01:16:17,180 --> 01:16:21,250 Então imprima tudo antes de nós. 1580 01:16:21,250 --> 01:16:27,710 Imprimir a nós mesmos, de modo a impressão nó atual 36, printf regular, e, em seguida, 1581 01:16:27,710 --> 01:16:31,170 imprimir tudo atrás de nós. 1582 01:16:31,170 --> 01:16:32,730 >> DAVID J. MALAN: Este é o lugar onde a recursão fica muito bonito. 1583 01:16:32,730 --> 01:16:36,270 É este salto incrível de fé, onde você faz um pouquinho de trabalho. 1584 01:16:36,270 --> 01:16:38,460 E então você deixar alguém mais fazer o resto. 1585 01:16:38,460 --> 01:16:40,180 E que outra pessoa é, ironicamente, você. 1586 01:16:40,180 --> 01:16:44,260 1587 01:16:44,260 --> 01:16:48,360 Então, por graves brownie pontos, se se desloca para cima sobre as questões - 1588 01:16:48,360 --> 01:16:50,530 >> ROB BOWDEN: Nas perguntas? 1589 01:16:50,530 --> 01:16:53,490 >> DAVID J. MALAN: E um pouco para baixo para os números, alguém sabe onde 1590 01:16:53,490 --> 01:16:55,190 esses números vêm? 1591 01:16:55,190 --> 01:16:56,610 >> ROB BOWDEN: Eu tenho literalmente nenhuma idéia. 1592 01:16:56,610 --> 01:16:59,794 >> DAVID J. MALAN: Eles aparecem durante todo o teste. 1593 01:16:59,794 --> 01:17:01,150 >> AUDIÊNCIA: São eles os mesmos números? 1594 01:17:01,150 --> 01:17:01,910 >> DAVID J. MALAN: Esses números. 1595 01:17:01,910 --> 01:17:03,260 Um pouco de ovo de Páscoa. 1596 01:17:03,260 --> 01:17:08,100 Portanto, para aqueles de vocês assistindo on-line em casa, se você pode nos dizer por e-mail para 1597 01:17:08,100 --> 01:17:12,680 heads@CS50.net que o significado estes números são repetidos seis 1598 01:17:12,680 --> 01:17:18,560 todo Teste 1, vamos lavá-lo com incrível atenção na final 1599 01:17:18,560 --> 01:17:21,610 palestra e uma bola de stress. 1600 01:17:21,610 --> 01:17:25,460 1601 01:17:25,460 --> 01:17:27,790 Nice, sutil. 1602 01:17:27,790 --> 01:17:29,570 >> ROB Bowden: Qualquer últimas perguntas sobre qualquer coisa sobre o teste? 1603 01:17:29,570 --> 01:17:32,608