1 00:00:00,000 --> 00:00:00,500 2 00:00:00,500 --> 00:00:11,137 [MÚSICA DE JOGO] 3 00:00:11,137 --> 00:00:12,220 DAVID J. MALAN: Tudo bem. 4 00:00:12,220 --> 00:00:13,950 Este é CS50. 5 00:00:13,950 --> 00:00:18,560 Esta é semana de cinco continuou, e nós tenho uma boa notícia e uma má notícia. 6 00:00:18,560 --> 00:00:21,140 Então boa notícia é que CS50 lança nesta sexta-feira. 7 00:00:21,140 --> 00:00:24,430 Se você gostaria de se juntar a nós, cabeça para o URL de costume aqui. 8 00:00:24,430 --> 00:00:28,670 Uma notícia ainda melhor, nenhuma palestra próxima segunda-feira dia 13. 9 00:00:28,670 --> 00:00:31,970 Pouco menos melhor notícia, questionário zero é próxima quarta-feira. 10 00:00:31,970 --> 00:00:33,840 Mais detalhes podem ser encontrados neste URL aqui. 11 00:00:33,840 --> 00:00:36,340 E ao longo dos próximos dois dias estaremos preenchendo os espaços em branco 12 00:00:36,340 --> 00:00:39,234 no que diz respeito aos quartos que teremos reservados. 13 00:00:39,234 --> 00:00:41,400 Melhor notícia é que não vou ser uma revisão de todo o curso 14 00:00:41,400 --> 00:00:43,570 sessão no próximo Segunda-feira à noite. 15 00:00:43,570 --> 00:00:46,270 Fique atento para o curso de Site para localização e detalhes. 16 00:00:46,270 --> 00:00:49,290 Seções, embora seja um férias, também vai atender bem. 17 00:00:49,290 --> 00:00:50,490 18 00:00:50,490 --> 00:00:52,940 Melhor notícia, palestra na próxima sexta. 19 00:00:52,940 --> 00:00:56,220 Portanto, esta é uma tradição que têm, de acordo com o conteúdo programático. 20 00:00:56,220 --> 00:00:58,100 Apenas-- que vai ser incrível. 21 00:00:58,100 --> 00:01:02,510 Você vai ver coisas como estruturas de dados de tempo constante 22 00:01:02,510 --> 00:01:04,730 e tabelas de hash e árvores e tentativas. 23 00:01:04,730 --> 00:01:07,150 E vamos falar sobre os problemas de aniversário. 24 00:01:07,150 --> 00:01:09,440 Um monte de coisas aguarda próxima sexta-feira. 25 00:01:09,440 --> 00:01:11,212 26 00:01:11,212 --> 00:01:12,200 Está bem. 27 00:01:12,200 --> 00:01:13,190 De qualquer forma. 28 00:01:13,190 --> 00:01:17,080 >> Então lembro que fomos focando esta imagem do que está 29 00:01:17,080 --> 00:01:18,980 dentro da memória do nosso computador. 30 00:01:18,980 --> 00:01:22,875 Assim, a memória ou a memória RAM é onde os programas existir enquanto você está executando-os. 31 00:01:22,875 --> 00:01:25,215 Se você clicar duas vezes um ícone para executar algum programa 32 00:01:25,215 --> 00:01:27,520 ou clique duas vezes em um ícone para abrir algum arquivo, 33 00:01:27,520 --> 00:01:30,430 ele é carregado a partir do disco rígido ou unidade de estado sólido 34 00:01:30,430 --> 00:01:34,190 na RAM, Random Access Memory, onde ele vive até se desligar, 35 00:01:34,190 --> 00:01:36,700 a tampa fecha portátil, ou sair do programa. 36 00:01:36,700 --> 00:01:38,960 >> Agora que a memória, de que você provavelmente tem 37 00:01:38,960 --> 00:01:41,950 1 gigabyte nos dias de hoje, 2 gigabytes, ou mesmo muito mais, 38 00:01:41,950 --> 00:01:44,420 geralmente é colocado para fora para um determinado programa 39 00:01:44,420 --> 00:01:47,170 neste tipo de rectangular modelo conceitual 40 00:01:47,170 --> 00:01:50,860 pelo qual temos a pilha na parte inferior e um monte de outras coisas no topo. 41 00:01:50,860 --> 00:01:53,140 A coisa no topo temos visto nesta imagem 42 00:01:53,140 --> 00:01:55,670 antes, mas nunca conversamos sobre é o chamado segmento de texto. 43 00:01:55,670 --> 00:01:58,419 Segmento de texto é apenas uma maneira elegante de dizer os zeros e uns que 44 00:01:58,419 --> 00:02:01,150 compor seu programa compilado real. 45 00:02:01,150 --> 00:02:03,910 >> Então, quando você clica duas vezes Microsoft Word no seu Mac ou PC, 46 00:02:03,910 --> 00:02:08,030 ou ao executar o ponto barra Mario em um Computador Linux em sua janela de terminal, 47 00:02:08,030 --> 00:02:12,460 os zeros e uns que compõem Word ou Mario são armazenados temporariamente 48 00:02:12,460 --> 00:02:16,610 na memória RAM do seu computador na chamada segmento de texto para um programa particular. 49 00:02:16,610 --> 00:02:19,080 Abaixo disso vai inicializado e dados não inicializado. 50 00:02:19,080 --> 00:02:22,655 Este é o material como variáveis ​​globais, que não usei muitos, 51 00:02:22,655 --> 00:02:24,910 mas de vez em quando temos tinha variáveis ​​globais 52 00:02:24,910 --> 00:02:28,819 ou estaticamente cordas definido que é codificado palavras como "Olá" 53 00:02:28,819 --> 00:02:31,860 que não são levados em do utilizador que são codificados em seu programa. 54 00:02:31,860 --> 00:02:34,230 >> Agora, para baixo na parte inferior nós ter a pilha de chamada. 55 00:02:34,230 --> 00:02:37,665 E a pilha, até agora, temos sido usando para que tipos de efeitos? 56 00:02:37,665 --> 00:02:39,706 57 00:02:39,706 --> 00:02:40,997 O que a pilha foi utilizado? 58 00:02:40,997 --> 00:02:41,160 Sim? 59 00:02:41,160 --> 00:02:42,070 >> Audiência: Funções. 60 00:02:42,070 --> 00:02:43,320 >> DAVID J. MALAN: Para funções? 61 00:02:43,320 --> 00:02:44,980 Em que sentido para as funções? 62 00:02:44,980 --> 00:02:48,660 >> AUDIÊNCIA: Quando você chamar uma função, o argumentos são copiados para a pilha. 63 00:02:48,660 --> 00:02:49,660 >> DAVID J. MALAN: Exatamente. 64 00:02:49,660 --> 00:02:52,650 Quando você chama uma função, a argumentos são copiados para a pilha. 65 00:02:52,650 --> 00:02:56,330 Assim, qualquer Xs ou Y do ou de um ou de B que você está passando para uma função 66 00:02:56,330 --> 00:02:58,680 são temporariamente colocados em a pilha assim chamado, 67 00:02:58,680 --> 00:03:02,000 apenas como um dos Annenberg bandejas salão de jantar, e também as coisas 68 00:03:02,000 --> 00:03:03,190 como variáveis ​​locais. 69 00:03:03,190 --> 00:03:06,290 Se a sua função foo ou sua troca função de ter variáveis ​​locais, 70 00:03:06,290 --> 00:03:08,602 como temperatura, esses dois acabar na pilha. 71 00:03:08,602 --> 00:03:11,560 Agora, não vamos falar muito sobre eles, mas essas variáveis ​​de ambiente 72 00:03:11,560 --> 00:03:15,690 na parte inferior que vimos há um tempo atrás, quando Eu estava mexendo no teclado um dia 73 00:03:15,690 --> 00:03:20,050 e eu comecei a acessar coisas argv como 100 ou argv 1000, 74 00:03:20,050 --> 00:03:22,320 apenas elements-- eu esqueço Números de a, mas que 75 00:03:22,320 --> 00:03:24,330 Não era para ser acessado por mim. 76 00:03:24,330 --> 00:03:26,581 Começamos a ver alguns símbolos funk na tela. 77 00:03:26,581 --> 00:03:28,330 Aqueles eram chamados variáveis ​​de ambiente 78 00:03:28,330 --> 00:03:32,390 como configurações globais para o meu programa ou para o meu computador, não 79 00:03:32,390 --> 00:03:37,090 sem relação com a recente bug que discutimos, 80 00:03:37,090 --> 00:03:39,670 Shellshock, que tem sido assola muito poucos computadores. 81 00:03:39,670 --> 00:03:42,960 >> Agora, por último, em foco de hoje que em última análise vai ser na pilha. 82 00:03:42,960 --> 00:03:44,864 Este é mais um pedaço de memória. 83 00:03:44,864 --> 00:03:47,030 E tudo isto fundamentalmente memória é a mesma coisa. 84 00:03:47,030 --> 00:03:48,040 É o mesmo hardware. 85 00:03:48,040 --> 00:03:49,956 Nós somos apenas uma espécie de tratamento de diferentes grupos 86 00:03:49,956 --> 00:03:51,460 de bytes para diferentes fins. 87 00:03:51,460 --> 00:03:56,540 A pilha também vai ser onde variáveis ​​e memória que você solicitar 88 00:03:56,540 --> 00:03:58,810 a partir do sistema operativo é temporariamente armazenado. 89 00:03:58,810 --> 00:04:01,890 >> Mas há um tipo de problema aqui, como a foto indica. 90 00:04:01,890 --> 00:04:05,261 Nós meio que temos dois navios prestes a colidir. 91 00:04:05,261 --> 00:04:08,010 Porque, como você usa cada vez mais da pilha, e como vemos hoje 92 00:04:08,010 --> 00:04:11,800 para a frente, como você usa cada vez mais a pilha, com certeza as coisas ruins podem acontecer. 93 00:04:11,800 --> 00:04:15,054 E, de fato, podemos induzir que intencionalmente ou não. 94 00:04:15,054 --> 00:04:16,970 Assim, o suspense última tempo era esse programa, 95 00:04:16,970 --> 00:04:20,570 que não servem qualquer funcional outro propósito além de demonstrar 96 00:04:20,570 --> 00:04:24,750 como você como um cara mau pode realmente ter vantagem de bugs no programa de alguém 97 00:04:24,750 --> 00:04:28,460 e assumir um programa ou até mesmo um sistema de computador ou servidor de todo. 98 00:04:28,460 --> 00:04:31,660 Então, só para olhar brevemente, você notar que o principal na parte inferior 99 00:04:31,660 --> 00:04:34,510 toma em linha de comando argumentos, como por argv. 100 00:04:34,510 --> 00:04:38,480 E tem uma chamada para uma função f, essencialmente uma função de chamada sem nome 101 00:04:38,480 --> 00:04:40,250 f, e ele está passando em argv [1]. 102 00:04:40,250 --> 00:04:43,960 >> Então, qualquer palavra que o usuário digita em pelo a solicitação após o nome deste programa, 103 00:04:43,960 --> 00:04:49,310 e então esta função arbitrária up top, f, leva em uma corda, AKA char *, 104 00:04:49,310 --> 00:04:51,720 como começamos a discutir, e ele simplesmente chama de "bar". 105 00:04:51,720 --> 00:04:53,310 Mas poderíamos chamá-lo de nada. 106 00:04:53,310 --> 00:04:57,470 E então ele declara, dentro de f, uma série de caracteres 107 00:04:57,470 --> 00:04:59,930 chamado C-- 12 desses personagens. 108 00:04:59,930 --> 00:05:03,580 >> Agora, pela história que eu estava dizendo um momento atrás, onde na memória 109 00:05:03,580 --> 00:05:06,720 c é, ou são aqueles 12 PERSONAGENS vai acabar? 110 00:05:06,720 --> 00:05:07,570 Só para ficar claro. 111 00:05:07,570 --> 00:05:08,070 Sim? 112 00:05:08,070 --> 00:05:08,590 >> AUDIÊNCIA: Na pilha. 113 00:05:08,590 --> 00:05:09,420 >> DAVID J. MALAN: Na pilha. 114 00:05:09,420 --> 00:05:10,720 Assim, c é uma variável local. 115 00:05:10,720 --> 00:05:14,079 Estamos pedindo para 12 caracteres ou 12 bytes. 116 00:05:14,079 --> 00:05:16,120 Aqueles vão acabar na pilha de chamada. 117 00:05:16,120 --> 00:05:18,530 Agora, finalmente, é esta outra função que é realmente muito útil, 118 00:05:18,530 --> 00:05:20,571 mas não usei muito nós mesmos, strncopy. 119 00:05:20,571 --> 00:05:21,550 120 00:05:21,550 --> 00:05:25,200 Significa cópia corda, mas só n letras, n caracteres. 121 00:05:25,200 --> 00:05:31,990 Então n caracteres será copiado de bar em c. 122 00:05:31,990 --> 00:05:32,980 E quantos? 123 00:05:32,980 --> 00:05:34,110 O comprimento da barra. 124 00:05:34,110 --> 00:05:36,330 Assim, em outras palavras, que uma linha, strncopy, 125 00:05:36,330 --> 00:05:39,500 vai copiar efetivamente bar no c. 126 00:05:39,500 --> 00:05:42,340 >> Agora, apenas a espécie de antecipar A moral desta história, 127 00:05:42,340 --> 00:05:44,750 o que é potencialmente problemático aqui? 128 00:05:44,750 --> 00:05:49,710 Mesmo que estamos verificando o comprimento de bar e passá-la em strncopy, 129 00:05:49,710 --> 00:05:53,145 o que é seu intestino dizendo é ainda quebrado sobre este programa? 130 00:05:53,145 --> 00:05:54,410 131 00:05:54,410 --> 00:05:55,220 Sim? 132 00:05:55,220 --> 00:05:57,491 >> AUDIÊNCIA: Não inclui espaço para o caractere nulo. 133 00:05:57,491 --> 00:05:59,990 DAVID J. MALAN: Não inclui espaço para o caractere nulo. 134 00:05:59,990 --> 00:06:02,073 Potencialmente, ao contrário de as práticas do passado que nem sequer 135 00:06:02,073 --> 00:06:04,810 tem tanto como uma vantagem de 1 a acomodar esse caractere nulo. 136 00:06:04,810 --> 00:06:06,649 Mas é ainda pior do que isso. 137 00:06:06,649 --> 00:06:07,940 O que mais estamos deixando de fazer? 138 00:06:07,940 --> 00:06:08,432 Sim? 139 00:06:08,432 --> 00:06:09,307 >> AUDIÊNCIA: [inaudível] 140 00:06:09,307 --> 00:06:15,440 141 00:06:15,440 --> 00:06:16,440 DAVID J. MALAN: Perfeito. 142 00:06:16,440 --> 00:06:18,490 Nós codificado 12 muito arbitrariamente. 143 00:06:18,490 --> 00:06:19,497 144 00:06:19,497 --> 00:06:21,330 Isso não é tanto a problema, mas o facto 145 00:06:21,330 --> 00:06:25,630 que não estamos ainda verificando se o comprimento da barra é menos do que 12, 146 00:06:25,630 --> 00:06:28,530 caso em que vai ser seguro para colocá-lo na memória 147 00:06:28,530 --> 00:06:30,260 chamada c que temos alocado. 148 00:06:30,260 --> 00:06:32,960 Com efeito, se a barra é assim 20 caracteres, 149 00:06:32,960 --> 00:06:39,010 esta função parece estar copiando 20 personagens de bar em c, assim, 150 00:06:39,010 --> 00:06:41,310 tendo, pelo menos, 8 bytes que não devem ser. 151 00:06:41,310 --> 00:06:42,690 Essa é a implicação aqui. 152 00:06:42,690 --> 00:06:44,347 >> Assim, no programa curto, quebrado. 153 00:06:44,347 --> 00:06:45,180 Não como um grande negócio. 154 00:06:45,180 --> 00:06:46,360 Talvez você começa uma falha de segmentação. 155 00:06:46,360 --> 00:06:47,651 Todos nós já tivemos erros nos programas. 156 00:06:47,651 --> 00:06:50,196 Todos nós pode ter erros em programas de agora. 157 00:06:50,196 --> 00:06:51,320 Mas qual é a implicação? 158 00:06:51,320 --> 00:06:54,390 Bem, aqui está uma versão ampliada-in de que imagem de memória do meu computador. 159 00:06:54,390 --> 00:06:56,230 Este é o fundo do meu stack. 160 00:06:56,230 --> 00:06:59,644 E, de fato, bem no fundo é o que é chamado pilha rotina pai, maneira extravagante 161 00:06:59,644 --> 00:07:00,560 de dizer que é principal. 162 00:07:00,560 --> 00:07:03,772 Assim que quem chamou a função f que estamos falando. 163 00:07:03,772 --> 00:07:05,230 Assim, este é o fundo da pilha. 164 00:07:05,230 --> 00:07:06,640 Endereço de retorno é algo novo. 165 00:07:06,640 --> 00:07:08,810 Ele sempre esteve lá, sempre estive nessa imagem. 166 00:07:08,810 --> 00:07:10,440 Nós apenas nunca chamou atenção para ele. 167 00:07:10,440 --> 00:07:15,290 Porque acontece o caminho c funciona é que quando uma função chama outra, 168 00:07:15,290 --> 00:07:18,780 não só os argumentos para que função são empurrados para a pilha, 169 00:07:18,780 --> 00:07:22,470 não só local de função variáveis ​​são empurrados para a pilha, 170 00:07:22,470 --> 00:07:26,820 algo chamado um endereço de retorno também é colocado na pilha. 171 00:07:26,820 --> 00:07:33,330 Especificamente, se as chamadas principais Foo, principais do próprio endereço na memória, algo boi, 172 00:07:33,330 --> 00:07:38,240 efetivamente é colocado na pilha de modo que, quando f é feito de executá-lo 173 00:07:38,240 --> 00:07:43,630 sabe onde pular de volta no texto segmento, a fim de continuar a execução. 174 00:07:43,630 --> 00:07:47,760 >> Então, se estamos aqui, conceitualmente, na principal, então f é chamada. 175 00:07:47,760 --> 00:07:50,200 Como f saber quem para controle de mão de volta? 176 00:07:50,200 --> 00:07:52,020 Bem, este pequeno breadcrumb em vermelho aqui, 177 00:07:52,020 --> 00:07:54,978 chamado o endereço de retorno, ele só cheques, o que é que o endereço de retorno? 178 00:07:54,978 --> 00:07:57,039 Oh, deixe-me saltar de volta para principal aqui. 179 00:07:57,039 --> 00:07:59,080 E isso é um pouco de uma simplificação, 180 00:07:59,080 --> 00:08:00,750 porque os zeros e uns para principal são tecnicamente 181 00:08:00,750 --> 00:08:01,967 aqui em cima no segmento de tecnologia. 182 00:08:01,967 --> 00:08:03,800 Mas essa é a idéia. f só tem que saber o que 183 00:08:03,800 --> 00:08:06,680 em última análise, em que o controlo de volta. 184 00:08:06,680 --> 00:08:09,790 >> Mas a forma como os computadores Há muito tempo estabelecidas as coisas 185 00:08:09,790 --> 00:08:12,320 como variáveis ​​locais e argumentos é assim. 186 00:08:12,320 --> 00:08:17,180 Assim, no topo da imagem em azul é o quadro de pilha para f, então tudo 187 00:08:17,180 --> 00:08:19,630 da memória que f especificamente é utilizado. 188 00:08:19,630 --> 00:08:22,990 Então, nesse sentido, perceber que bar é neste quadro. 189 00:08:22,990 --> 00:08:23,980 Bar era seu argumento. 190 00:08:23,980 --> 00:08:27,240 E defendeu que os argumentos para funções são empurrados para a pilha. 191 00:08:27,240 --> 00:08:29,910 E c, é claro, é Também nesta foto. 192 00:08:29,910 --> 00:08:33,520 >> E apenas para fins de notação, notar no canto superior esquerdo 193 00:08:33,520 --> 00:08:37,020 é o que seria c suporte 0 e então ligeiramente para baixo à direita 194 00:08:37,020 --> 00:08:38,220 é c suporte 11. 195 00:08:38,220 --> 00:08:41,240 Portanto, em outras palavras, você pode imaginar que há uma grade de bytes 196 00:08:41,240 --> 00:08:44,380 há, em primeiro lugar, que é superior esquerdo, inferior do que 197 00:08:44,380 --> 00:08:48,360 é o último dos 12 bytes. 198 00:08:48,360 --> 00:08:49,930 >> Mas agora tentar avançar. 199 00:08:49,930 --> 00:08:55,580 O que está para acontecer se passarmos em um bar de cadeia que é mais do que c? 200 00:08:55,580 --> 00:08:59,130 E não estamos verificando se é de fato maior do que 12. 201 00:08:59,130 --> 00:09:03,146 Qual parte da imagem vai se substituído por bytes 0, 1, 2, 3, 202 00:09:03,146 --> 00:09:07,890 dot dot dot, 11, e, em seguida, ruim, 12, 13 a 19? 203 00:09:07,890 --> 00:09:11,820 O que vai acontecer aqui, se inferir a partir da ordenação 204 00:09:11,820 --> 00:09:14,790 que c 0 suporte está no topo e c suporte 11 é uma espécie de baixo 205 00:09:14,790 --> 00:09:15,812 à direita? 206 00:09:15,812 --> 00:09:16,796 Sim? 207 00:09:16,796 --> 00:09:19,260 >> AUDIÊNCIA: Bem, ele vai para substituir o bar char *. 208 00:09:19,260 --> 00:09:22,260 >> DAVID J. MALAN: Sim, parece que você está indo para substituir carvão bar *. 209 00:09:22,260 --> 00:09:26,245 E pior, se você enviar em um tempo muito longo string, você pode até substituir o que? 210 00:09:26,245 --> 00:09:27,460 211 00:09:27,460 --> 00:09:28,570 O endereço de retorno. 212 00:09:28,570 --> 00:09:31,380 Que mais uma vez, é como um breadcrumb para dizer ao programa onde 213 00:09:31,380 --> 00:09:34,060 voltar para quando f é feito de ser chamado. 214 00:09:34,060 --> 00:09:37,140 >> Então, o que bandidos costumam fazer é se deparar com um programa 215 00:09:37,140 --> 00:09:41,290 que eles são curiosos se é explorável, carrinho, de tal maneira 216 00:09:41,290 --> 00:09:43,550 que ele ou ela pode tomar vantagem desse bug, 217 00:09:43,550 --> 00:09:45,720 geralmente eles não recebem este direito pela primeira vez. 218 00:09:45,720 --> 00:09:48,590 Eles só começar a enviar, por exemplo, seqüências aleatórias em seu programa, 219 00:09:48,590 --> 00:09:50,260 se no teclado, ou, francamente eles provavelmente 220 00:09:50,260 --> 00:09:52,740 escrever um pequeno programa para apenas gerar automaticamente cordas, 221 00:09:52,740 --> 00:09:55,430 e começar a bater em seu programa o envio de lotes de entradas diferentes 222 00:09:55,430 --> 00:09:56,340 em diferentes comprimentos. 223 00:09:56,340 --> 00:09:58,990 >> Assim que suas falhas do programa, isso é uma coisa incrível. 224 00:09:58,990 --> 00:10:01,020 Porque isso significa que ele ou ela descobriu 225 00:10:01,020 --> 00:10:02,660 o que provavelmente é de fato um bug. 226 00:10:02,660 --> 00:10:05,830 E então eles podem ficar mais inteligente e começar a se concentrar mais estreitamente 227 00:10:05,830 --> 00:10:07,420 sobre a forma de explorar esse bug. 228 00:10:07,420 --> 00:10:11,480 Em particular, o que ele ou ela pode fazer é enviar, no melhor dos casos, Olá. 229 00:10:11,480 --> 00:10:12,210 Não é grande coisa. 230 00:10:12,210 --> 00:10:14,750 É uma cadeia que é suficientemente curto. 231 00:10:14,750 --> 00:10:18,100 Mas e se ele ou ela envia, e vamos generalizar-lo como, 232 00:10:18,100 --> 00:10:20,890 ataque code-- tão zeros e os que fazem as coisas 233 00:10:20,890 --> 00:10:25,150 rm-rf como, que retire tudo a partir do disco rígido ou enviar spam 234 00:10:25,150 --> 00:10:27,000 ou de alguma forma a atacar máquina? 235 00:10:27,000 --> 00:10:29,570 >> Por isso, se cada uma delas letras A apenas representa, 236 00:10:29,570 --> 00:10:32,380 conceitualmente, ataque, ataque, ataque, ataque, um código ruim 237 00:10:32,380 --> 00:10:36,410 que alguém escreveu, mas se essa pessoa é inteligente o suficiente 238 00:10:36,410 --> 00:10:40,790 não apenas para incluir todos desses rm-rfs, mas também 239 00:10:40,790 --> 00:10:46,100 que os seus últimos bytes ser um número que corresponde 240 00:10:46,100 --> 00:10:50,540 para o endereço do seu ou seu próprio código de ataque 241 00:10:50,540 --> 00:10:53,820 que ele ou ela passou em apenas , fornecendo-lhe no prompt, 242 00:10:53,820 --> 00:10:58,760 você pode efetivamente enganar o computador para perceber quando f é feito em execução, 243 00:10:58,760 --> 00:11:02,400 oh, é hora de eu saltar de volta para o endereço do remetente vermelha. 244 00:11:02,400 --> 00:11:06,070 Mas porque ele ou ela tem de alguma forma sobrepostas que o endereço de retorno 245 00:11:06,070 --> 00:11:09,602 com o seu próprio número, e eles são inteligentes o suficiente 246 00:11:09,602 --> 00:11:11,560 ter configurado que número para se referir, como você 247 00:11:11,560 --> 00:11:13,740 ver no super top canto esquerdo lá, 248 00:11:13,740 --> 00:11:18,020 o endereço real no computador de memória de algum do seu código de ataque, 249 00:11:18,020 --> 00:11:21,740 um bandido pode enganar o computador para executar o seu próprio código. 250 00:11:21,740 --> 00:11:23,700 >> E esse código, mais uma vez, pode ser qualquer coisa. 251 00:11:23,700 --> 00:11:26,120 É geralmente chamado código shell, que é apenas 252 00:11:26,120 --> 00:11:29,030 uma forma de dizer que não é geralmente algo tão simples como rm-rf. 253 00:11:29,030 --> 00:11:32,340 É realmente algo como Bash, ou um programa real que lhe dá 254 00:11:32,340 --> 00:11:37,230 ou seu controle programático para executar qualquer outra coisa que eles querem. 255 00:11:37,230 --> 00:11:40,210 Então, em suma, tudo isso deriva do simples fato 256 00:11:40,210 --> 00:11:44,490 que este bug não envolveu a verificação os limites de sua matriz. 257 00:11:44,490 --> 00:11:47,250 E porque o caminho computadores de trabalho é que eles 258 00:11:47,250 --> 00:11:49,430 utilizar a pilha efetivamente, conceitualmente, 259 00:11:49,430 --> 00:11:54,830 inferior em cima, mas, em seguida, os elementos você empurrar para a pilha crescer de cima para baixo, 260 00:11:54,830 --> 00:11:56,624 isso é extremamente problemático. 261 00:11:56,624 --> 00:11:58,290 Agora, existem maneiras de contornar isso. 262 00:11:58,290 --> 00:12:00,800 E, francamente, há línguas com a qual trabalhar em torno deste. 263 00:12:00,800 --> 00:12:03,100 Java é imune, por exemplo, a esta questão particular. 264 00:12:03,100 --> 00:12:04,110 Porque não dar-lhe indicações. 265 00:12:04,110 --> 00:12:05,943 Eles não dão a você endereços de memória diretas. 266 00:12:05,943 --> 00:12:08,560 Assim, com este poder que temos tocar em nada na memória 267 00:12:08,560 --> 00:12:11,580 que queremos vem, na verdade, um grande risco. 268 00:12:11,580 --> 00:12:12,430 >> Portanto, manter um olho para fora. 269 00:12:12,430 --> 00:12:14,596 Se, francamente, nos meses ou anos, a qualquer hora 270 00:12:14,596 --> 00:12:17,740 você ler sobre alguma exploração de um programa ou de um servidor, 271 00:12:17,740 --> 00:12:22,370 se você já viu um toque de algo como um ataque de estouro de buffer, 272 00:12:22,370 --> 00:12:25,390 ou estouro de pilha é um outro tipo de ataque, semelhante em espírito, 273 00:12:25,390 --> 00:12:28,770 tanto quanto inspira o site da nome, se você sabe disso, 274 00:12:28,770 --> 00:12:33,170 tudo está falando apenas transbordando o tamanho de algum personagem 275 00:12:33,170 --> 00:12:36,200 matriz ou matriz algum modo mais geral. 276 00:12:36,200 --> 00:12:38,822 Todas as perguntas, então, sobre este assunto? 277 00:12:38,822 --> 00:12:39,780 Não tente fazer isso em casa. 278 00:12:39,780 --> 00:12:41,620 279 00:12:41,620 --> 00:12:42,300 >> Tudo certo. 280 00:12:42,300 --> 00:12:47,270 Então malloc, até agora, tem sido o nosso novo amigo em que podemos alocar memória 281 00:12:47,270 --> 00:12:50,540 que não sabem necessariamente em avançar que queremos de modo que não temos 282 00:12:50,540 --> 00:12:52,920 código rígido em nossa Os números de programas como 12. 283 00:12:52,920 --> 00:12:55,550 Uma vez que o usuário nos diz o quanto dados que ele ou ela quer de entrada, 284 00:12:55,550 --> 00:12:58,000 podemos malloc que muita memória. 285 00:12:58,000 --> 00:13:01,484 >> Então malloc se vê, ao medida em que temos vindo a utilizar, 286 00:13:01,484 --> 00:13:03,900 explicitamente última vez, e em seguida, vocês têm usado 287 00:13:03,900 --> 00:13:08,160 para GetString sem saber para várias semanas, todos da memória do malloc 288 00:13:08,160 --> 00:13:09,820 vem o chamado montão. 289 00:13:09,820 --> 00:13:13,852 E é por isso getString, por exemplo, pode alocar memória dinamicamente 290 00:13:13,852 --> 00:13:16,060 sem saber o que você está vai digitar com antecedência, 291 00:13:16,060 --> 00:13:21,520 entregá-lo de volta um ponteiro para a memória, e que a memória ainda é seu para manter, 292 00:13:21,520 --> 00:13:24,080 mesmo depois getString retorna. 293 00:13:24,080 --> 00:13:27,450 Como recordação depois de tudo que o pilha está constantemente indo para cima e para baixo, 294 00:13:27,450 --> 00:13:27,950 cima e para baixo. 295 00:13:27,950 --> 00:13:30,230 E assim que ele vai para baixo, isso significa que qualquer memória 296 00:13:30,230 --> 00:13:33,030 Esta função deve não ser usado por qualquer pessoa. 297 00:13:33,030 --> 00:13:34,570 É valores de lixo agora. 298 00:13:34,570 --> 00:13:36,120 >> Mas a pilha está aqui em cima. 299 00:13:36,120 --> 00:13:39,360 E o que é agradável sobre malloc é que quando malloc aloca memória até aqui, 300 00:13:39,360 --> 00:13:42,070 não é afetado, pois o maior parte dos casos, por a pilha. 301 00:13:42,070 --> 00:13:46,000 E assim qualquer função pode acessar memória que tenha sido malloc'd, 302 00:13:46,000 --> 00:13:49,120 até mesmo por uma função como getString, mesmo depois de ser devolvidos. 303 00:13:49,120 --> 00:13:51,700 >> Agora, o inverso do malloc é gratuito. 304 00:13:51,700 --> 00:13:53,900 E, de fato, a regra que precisa começar a adoptar 305 00:13:53,900 --> 00:13:58,950 é qualquer, qualquer, qualquer hora que você usar malloc você deve usar-se livre, eventualmente, 306 00:13:58,950 --> 00:14:00,280 no mesmo ponteiro. 307 00:14:00,280 --> 00:14:03,289 Todo esse tempo que temos vindo a escrever bugs, código de buggy, por muitas razões. 308 00:14:03,289 --> 00:14:05,580 Mas um dos quais tem sido usando a biblioteca de CS50, que 309 00:14:05,580 --> 00:14:09,010 em si é deliberadamente Buggy, que vazamentos de memória. 310 00:14:09,010 --> 00:14:11,410 Toda vez que você chamou getString ao longo das últimas semanas 311 00:14:11,410 --> 00:14:13,870 estamos pedindo a operação sistema, Linux, para a memória. 312 00:14:13,870 --> 00:14:15,780 E você nunca já dado de volta. 313 00:14:15,780 --> 00:14:17,730 E isso não é, em praticar, uma coisa boa. 314 00:14:17,730 --> 00:14:20,330 >> E Valgrind, um dos ferramentas introduzidas no Pset 4, 315 00:14:20,330 --> 00:14:22,900 é tudo a ajudar você agora encontrar erros como esse. 316 00:14:22,900 --> 00:14:27,060 Mas, felizmente para Pset 4 você não precisa para usar a biblioteca CS50 ou getString. 317 00:14:27,060 --> 00:14:31,220 Assim, todos os erros relacionados à memória são em última análise, vai ser o seu próprio. 318 00:14:31,220 --> 00:14:34,060 >> Então malloc é mais do que apenas conveniente para este propósito. 319 00:14:34,060 --> 00:14:37,420 Na verdade, podemos agora resolver fundamentalmente diferentes problemas, 320 00:14:37,420 --> 00:14:41,640 e, fundamentalmente, resolver problemas mais eficazmente como promessa por semana zeros. 321 00:14:41,640 --> 00:14:44,720 Até agora, esta é a mais sexy estrutura de dados que tivemos. 322 00:14:44,720 --> 00:14:47,804 E por estrutura de dados Eu só quero dizer uma forma de memória conceituar 323 00:14:47,804 --> 00:14:50,720 de uma forma que vai além de apenas dizer: este é um inteiro, este é um caracter. 324 00:14:50,720 --> 00:14:52,930 Podemos começar com as coisas de cluster juntos. 325 00:14:52,930 --> 00:14:54,460 >> Assim, um conjunto parecido com este. 326 00:14:54,460 --> 00:14:57,270 E o que foi fundamental em cerca de uma matriz é que lhe dá 327 00:14:57,270 --> 00:14:59,724 back-to-back pedaços de memória, cada uma das quais 328 00:14:59,724 --> 00:15:02,765 vai ser do mesmo tipo, int int, int, int ou char, char, char, 329 00:15:02,765 --> 00:15:03,330 car. 330 00:15:03,330 --> 00:15:04,496 Mas há algumas desvantagens. 331 00:15:04,496 --> 00:15:06,570 Este, por exemplo, é uma matriz de tamanho seis. 332 00:15:06,570 --> 00:15:10,650 Suponha que você preencha essa matriz com seis números e, em seguida, por qualquer motivo, 333 00:15:10,650 --> 00:15:13,187 o usuário quer dar você um sétimo número. 334 00:15:13,187 --> 00:15:14,020 Onde você colocou? 335 00:15:14,020 --> 00:15:15,490 336 00:15:15,490 --> 00:15:18,990 >> Qual é a solução se você tiver criada uma matriz sobre a pilha, 337 00:15:18,990 --> 00:15:22,030 por exemplo, apenas com a semana dois notação que introduzimos, 338 00:15:22,030 --> 00:15:23,730 de colchetes com um número dentro? 339 00:15:23,730 --> 00:15:25,160 340 00:15:25,160 --> 00:15:27,260 Bem, você tem seis números nessas caixas. 341 00:15:27,260 --> 00:15:28,530 O que seus instintos ser? 342 00:15:28,530 --> 00:15:29,973 Onde você deseja colocá-lo? 343 00:15:29,973 --> 00:15:30,860 >> AUDIÊNCIA: [inaudível] 344 00:15:30,860 --> 00:15:31,315 >> DAVID J. MALAN: Desculpe? 345 00:15:31,315 --> 00:15:32,380 >> AUDIÊNCIA: Coloque-o no final. 346 00:15:32,380 --> 00:15:33,796 >> DAVID J. MALAN: Coloque-o no final. 347 00:15:33,796 --> 00:15:35,880 Então, só para a direita, fora da caixa. 348 00:15:35,880 --> 00:15:38,710 O que seria bom, mas Acontece que você não pode fazer isso. 349 00:15:38,710 --> 00:15:41,350 Porque se você não pediu para este pedaço de memória, 350 00:15:41,350 --> 00:15:44,490 poderia ser por acaso que este está a ser usado por outra variável 351 00:15:44,490 --> 00:15:45,030 completamente. 352 00:15:45,030 --> 00:15:49,210 Pense de volta uma semana ou assim quando nós colocamos os nomes de Zamyla e Davin e Gabe 353 00:15:49,210 --> 00:15:49,930 na memória. 354 00:15:49,930 --> 00:15:51,638 Eles estavam literalmente back to back to back. 355 00:15:51,638 --> 00:15:53,550 Portanto, não podemos necessariamente confiar que tudo de 356 00:15:53,550 --> 00:15:55,800 aqui está disponível para eu usar. 357 00:15:55,800 --> 00:15:56,990 >> Então o que mais você pode fazer? 358 00:15:56,990 --> 00:16:00,282 Bem, uma vez que você perceber precisa de uma matriz de tamanho sete, 359 00:16:00,282 --> 00:16:02,490 você pode simplesmente criar um matriz de tamanho sete então usar 360 00:16:02,490 --> 00:16:05,950 um loop ou um loop while, copiá-lo para a nova matriz, 361 00:16:05,950 --> 00:16:09,680 e, em seguida, de alguma forma, se livrar de essa matriz ou simplesmente parar de usá-lo. 362 00:16:09,680 --> 00:16:12,130 Mas isso não é particularmente eficiente. 363 00:16:12,130 --> 00:16:15,340 Em suma, as matrizes não deixe redimensionar dinamicamente. 364 00:16:15,340 --> 00:16:17,900 >> Assim, por um lado, obtém de acesso aleatório, que é incrível. 365 00:16:17,900 --> 00:16:20,108 Porque nos permite fazer coisas como dividir e conquistar, 366 00:16:20,108 --> 00:16:23,100 pesquisa binária, todos os quais temos falou na tela aqui. 367 00:16:23,100 --> 00:16:24,950 Mas você pintar sozinho em um canto. 368 00:16:24,950 --> 00:16:27,810 Assim que você acertar o fim de sua matriz, 369 00:16:27,810 --> 00:16:29,980 você tem que fazer uma muito operação dispendiosa 370 00:16:29,980 --> 00:16:33,910 ou escrever um monte de código agora lidar com esse problema. 371 00:16:33,910 --> 00:16:36,680 >> Então, o que se em vez tivemos algo chamado uma lista, 372 00:16:36,680 --> 00:16:38,820 ou uma lista ligada em particular? 373 00:16:38,820 --> 00:16:41,930 E se em vez de ter retângulos volta para trás para trás, 374 00:16:41,930 --> 00:16:45,730 temos retângulos que deixam um pouco pouco espaço de manobra entre eles? 375 00:16:45,730 --> 00:16:49,670 E mesmo que eu desenhei este foto ou adaptado esta imagem 376 00:16:49,670 --> 00:16:54,696 a partir de um dos textos aqui para voltar ao volta para trás muito ordenada, na realidade, 377 00:16:54,696 --> 00:16:56,820 um desses rectângulos poderia estar aqui na memória. 378 00:16:56,820 --> 00:16:58,028 Um deles poderia ser até aqui. 379 00:16:58,028 --> 00:17:00,420 Um deles poderia ser até aqui, aqui, e assim por diante. 380 00:17:00,420 --> 00:17:02,910 >> Mas o que se chamou, neste caso, setas 381 00:17:02,910 --> 00:17:05,650 que de alguma forma vincular estes retângulos juntos? 382 00:17:05,650 --> 00:17:08,170 Na verdade, temos visto um técnico encarnação de uma seta. 383 00:17:08,170 --> 00:17:09,839 384 00:17:09,839 --> 00:17:13,710 O que temos usado nos últimos anos dias que, debaixo do capô, 385 00:17:13,710 --> 00:17:15,210 é representativa de uma seta? 386 00:17:15,210 --> 00:17:16,290 387 00:17:16,290 --> 00:17:17,349 Um ponteiro, certo? 388 00:17:17,349 --> 00:17:19,780 >> Então, o que se, em vez de apenas armazenar os números, 389 00:17:19,780 --> 00:17:23,130 como 9, 17, 22, 26, 34, E se nós não armazenados 390 00:17:23,130 --> 00:17:27,079 apenas um número, mas um apontador ao lado de cada número tal? 391 00:17:27,079 --> 00:17:30,690 Então, que assim como você enfiar uma agulha através de um monte de tecido, 392 00:17:30,690 --> 00:17:32,950 coisas de alguma forma de subordinação em conjunto, de modo semelhante pode 393 00:17:32,950 --> 00:17:35,550 nós com ponteiros, como encarnado por setas aqui, 394 00:17:35,550 --> 00:17:38,550 tipo de tecer desses retângulos individuais 395 00:17:38,550 --> 00:17:41,780 por efetivamente usando um ponteiro ao lado de cada número que 396 00:17:41,780 --> 00:17:46,065 aponta para algum número seguinte, que indica, por sua vez, alguns próximo número? 397 00:17:46,065 --> 00:17:47,940 Portanto, em outras palavras, o que se realmente queria 398 00:17:47,940 --> 00:17:49,820 para implementar algo parecido com isto? 399 00:17:49,820 --> 00:17:53,610 Bem, infelizmente, esses retângulos, , pelo menos, um com 9, 17, 22, 400 00:17:53,610 --> 00:17:57,040 e assim por diante, estes não são mais praças agradáveis ​​com números individuais. 401 00:17:57,040 --> 00:17:59,960 O fundo, retângulo abaixo de 9, por exemplo, 402 00:17:59,960 --> 00:18:04,330 representa o que deve ser um ponteiro, 32 bits. 403 00:18:04,330 --> 00:18:09,460 Agora, eu ainda não estou ciente de qualquer tipo de dados em C que lhe dá não só um int 404 00:18:09,460 --> 00:18:11,630 mas um apontador completamente. 405 00:18:11,630 --> 00:18:15,020 >> Então, qual é a solução, se quisermos inventar a nossa própria resposta para isso? 406 00:18:15,020 --> 00:18:15,760 Sim? 407 00:18:15,760 --> 00:18:16,640 >> AUDIÊNCIA: [inaudível] 408 00:18:16,640 --> 00:18:17,360 >> DAVID J. MALAN: O que é isso? 409 00:18:17,360 --> 00:18:17,880 >> AUDIÊNCIA: Nova estrutura. 410 00:18:17,880 --> 00:18:19,590 >> DAVID J. MALAN: Sim, então por que Não podemos criar uma nova estrutura, 411 00:18:19,590 --> 00:18:20,920 ou em C, um struct? 412 00:18:20,920 --> 00:18:25,990 Vimos estruturas antes, se brevemente, onde lidamos com uma estrutura de estudante 413 00:18:25,990 --> 00:18:27,780 como este, que tinha um nome e uma casa. 414 00:18:27,780 --> 00:18:31,980 Em Pset 3 fuga você usou um todo bando de GRect structs-- e GOvals 415 00:18:31,980 --> 00:18:34,810 Stanford que criou a informações de cluster juntos. 416 00:18:34,810 --> 00:18:38,580 Então, o que se tomarmos essa mesma idéia de as palavras-chave "typedef" e "struct" 417 00:18:38,580 --> 00:18:42,890 e, em seguida, algumas coisas específicas do aluno, e evoluir esta no seguinte: 418 00:18:42,890 --> 00:18:46,210 typedef struct node-- e nó é apenas uma ciência da computação muito genérico 419 00:18:46,210 --> 00:18:49,980 prazo para algo em uma estrutura de dados, um recipiente, de uma estrutura de dados. 420 00:18:49,980 --> 00:18:53,900 Um nó Eu reivindico vai ter um int n, totalmente simples, 421 00:18:53,900 --> 00:18:58,810 e, em seguida, um pouco mais enigmaticamente, Nesta segunda linha, nó struct * próximo. 422 00:18:58,810 --> 00:19:01,300 Mas, em termos menos técnicos, o que é que a segunda linha 423 00:19:01,300 --> 00:19:02,980 de código dentro das chaves? 424 00:19:02,980 --> 00:19:03,737 Sim? 425 00:19:03,737 --> 00:19:04,851 >> AUDIÊNCIA: [inaudível] 426 00:19:04,851 --> 00:19:06,600 David J. MALAN: Um ponteiro para outro nó. 427 00:19:06,600 --> 00:19:09,910 Então, na verdade, sintaxe um pouco enigmática. 428 00:19:09,910 --> 00:19:13,250 Mas se você lê-lo, literalmente, em seguida é o nome de uma variável. 429 00:19:13,250 --> 00:19:14,410 Qual é seu tipo de dados? 430 00:19:14,410 --> 00:19:18,206 É um pouco prolixo, desta vez, mas é do tipo de nó struct *. 431 00:19:18,206 --> 00:19:22,960 Qualquer vez que vimos algo estrela, que significa que é um ponteiro para esse tipo de dados. 432 00:19:22,960 --> 00:19:26,810 Então, da próxima é, aparentemente, um ponteiro para um nó de struct. 433 00:19:26,810 --> 00:19:28,310 >> Agora, o que é um nó struct? 434 00:19:28,310 --> 00:19:31,044 Bem, observe que você vê aqueles mesmas palavras no canto superior direito. 435 00:19:31,044 --> 00:19:33,960 E, de fato, você também verá a palavra "Nó" aqui em baixo no canto inferior esquerdo. 436 00:19:33,960 --> 00:19:35,640 E isso é realmente apenas uma conveniência. 437 00:19:35,640 --> 00:19:39,930 Observe que em nossa definição de estudante há a palavra "aluno" apenas uma vez. 438 00:19:39,930 --> 00:19:42,510 E isso é porque um aluno objeto não era auto-referencial. 439 00:19:42,510 --> 00:19:45,340 Não há nada dentro de um estudante que precisa apontar para um outro estudante, 440 00:19:45,340 --> 00:19:45,610 persay. 441 00:19:45,610 --> 00:19:47,630 Isso seria uma espécie de estranho no mundo real. 442 00:19:47,630 --> 00:19:50,880 >> Mas, com um nó em uma ligada lista, nós queremos um nó 443 00:19:50,880 --> 00:19:53,970 para ser referencial para um objeto semelhante. 444 00:19:53,970 --> 00:19:57,900 E assim perceber a mudança aqui não é apenas o que está dentro das chaves. 445 00:19:57,900 --> 00:20:00,800 Mas adicionar a palavra "nó" , na parte superior, bem como 446 00:20:00,800 --> 00:20:02,930 adicionando-o ao fundo em vez de "aluno". 447 00:20:02,930 --> 00:20:06,000 E este é apenas um detalhe técnico de modo a que, novamente, a sua estrutura de dados 448 00:20:06,000 --> 00:20:11,380 pode ser auto-referencial, de modo que a nó pode apontar para um outro tal nó. 449 00:20:11,380 --> 00:20:13,840 >> Então o que é isso, em última instância vai significar para nós? 450 00:20:13,840 --> 00:20:17,560 Bem, um, este material dentro é o conteúdo do nosso nó. 451 00:20:17,560 --> 00:20:19,360 Esta coisa aqui em cima, superior direito, é tão 452 00:20:19,360 --> 00:20:20,860 que, mais uma vez, podemos nos referir a nós mesmos. 453 00:20:20,860 --> 00:20:23,401 E então as coisas mais externa, embora nó é um novo termo 454 00:20:23,401 --> 00:20:25,500 talvez, ainda o é mesmo como estudante e que 455 00:20:25,500 --> 00:20:27,520 estava debaixo do capô em SPL. 456 00:20:27,520 --> 00:20:31,095 >> Então, se nós agora queria começar implementação desta lista ligada, 457 00:20:31,095 --> 00:20:33,220 como podemos traduzir algo como isto para codificar? 458 00:20:33,220 --> 00:20:35,350 Bem, vamos ver uma exemplo de um programa que 459 00:20:35,350 --> 00:20:36,840 na verdade, usa uma lista ligada. 460 00:20:36,840 --> 00:20:40,870 Entre código de distribuição de hoje é um programa chamado Lista Zero. 461 00:20:40,870 --> 00:20:44,980 E se eu executar este eu criei um super GUI simples, Interface gráfica do utilizador, 462 00:20:44,980 --> 00:20:46,460 mas é realmente apenas printf. 463 00:20:46,460 --> 00:20:50,930 E agora que eu me dei algumas cardápio opções-- DELETE, INSERT, Pesquisa, 464 00:20:50,930 --> 00:20:51,750 e Traverse. 465 00:20:51,750 --> 00:20:52,630 E Sair. 466 00:20:52,630 --> 00:20:55,970 Estes são apenas operações comuns em um estrutura de dados conhecida como lista de link. 467 00:20:55,970 --> 00:20:58,409 >> Agora, Excluir vai excluir um número da lista. 468 00:20:58,409 --> 00:21:00,200 Inserir vai adicionar um número à lista. 469 00:21:00,200 --> 00:21:02,181 Pesquisa vai olhar para o número da lista. 470 00:21:02,181 --> 00:21:04,930 E travessia é apenas uma maneira elegante de dizer, percorrer a lista, 471 00:21:04,930 --> 00:21:06,245 imprimi-lo, mas é isso. 472 00:21:06,245 --> 00:21:07,720 Não alterá-lo de qualquer forma. 473 00:21:07,720 --> 00:21:08,570 >> Então, vamos tentar isso. 474 00:21:08,570 --> 00:21:10,160 Vamos em frente e digite 2. 475 00:21:10,160 --> 00:21:12,710 E então eu vou inserir o número, dizem 9. 476 00:21:12,710 --> 00:21:13,620 Enter. 477 00:21:13,620 --> 00:21:17,480 E agora o meu programa é apenas programado para dizer lista é agora 9. 478 00:21:17,480 --> 00:21:20,190 Agora, se eu ir em frente e que inserir novamente, vamos 479 00:21:20,190 --> 00:21:23,680 me ir em frente e diminuir o zoom e digite 17. 480 00:21:23,680 --> 00:21:25,770 Agora, a minha lista é 9, então com 17 anos. 481 00:21:25,770 --> 00:21:27,750 Se eu fizer inserir novamente, vamos pular um. 482 00:21:27,750 --> 00:21:32,400 Em vez de 22, de acordo com a imagem que tenho estado a olhar para aqui, deixe-me passar à frente 483 00:21:32,400 --> 00:21:34,630 e inserir 26 próximo. 484 00:21:34,630 --> 00:21:36,230 Então eu vou para digitar 26. 485 00:21:36,230 --> 00:21:37,755 A lista é como eu esperava. 486 00:21:37,755 --> 00:21:40,630 Mas agora, só para ver se esse código vai ser flexível, deixe-me agora 487 00:21:40,630 --> 00:21:43,520 Tipo 22, o qual, pelo menos conceitualmente, se tivermos 488 00:21:43,520 --> 00:21:46,520 Tendo isso resolvido, o que é de fato vai ser um outro objetivo, agora, 489 00:21:46,520 --> 00:21:48,690 deve ir entre 17 e 26. 490 00:21:48,690 --> 00:21:50,270 Então eu pressione Enter. 491 00:21:50,270 --> 00:21:51,380 Na verdade, isso funciona. 492 00:21:51,380 --> 00:21:54,950 E agora deixe-me inserir o passado, por a imagem, 34. 493 00:21:54,950 --> 00:21:55,450 >> Tudo certo. 494 00:21:55,450 --> 00:21:58,980 Então, por agora, deixe-me estipulam que Excluir e Traverse e Pesquisa fazer, 495 00:21:58,980 --> 00:21:59,760 de fato, trabalhar. 496 00:21:59,760 --> 00:22:04,180 Na verdade, se eu executar pesquisa, vamos procure o número 22, Enter. 497 00:22:04,180 --> 00:22:05,010 Constatou-se 22. 498 00:22:05,010 --> 00:22:07,580 Então é isso que este Programa Lista Zero faz. 499 00:22:07,580 --> 00:22:10,230 >> Mas o que realmente está acontecendo em que implementa isso? 500 00:22:10,230 --> 00:22:14,530 Bem, primeiro eu poderia ter, e de fato Eu tenho um arquivo chamado list0.h. 501 00:22:14,530 --> 00:22:16,540 502 00:22:16,540 --> 00:22:20,690 E em algum lugar existe essa line, typedef, nó struct, 503 00:22:20,690 --> 00:22:24,850 então eu tenho as minhas chaves, int n, e então struct-- qual era a definição? 504 00:22:24,850 --> 00:22:26,530 505 00:22:26,530 --> 00:22:28,545 Nó struct seguinte. 506 00:22:28,545 --> 00:22:29,920 507 00:22:29,920 --> 00:22:31,045 Por isso, precisamos da estrela. 508 00:22:31,045 --> 00:22:33,420 Agora, tecnicamente, entrar em o hábito de desenhar-lo aqui. 509 00:22:33,420 --> 00:22:35,670 Você pode ver livros didáticos e referências on-line fazê-lo lá. 510 00:22:35,670 --> 00:22:36,660 É funcionalmente equivalente. 511 00:22:36,660 --> 00:22:37,980 Na verdade, isso é um pouco mais típico. 512 00:22:37,980 --> 00:22:40,563 Mas eu vou ser coerente com o que fizemos da última vez e fazer isso. 513 00:22:40,563 --> 00:22:42,350 E então, finalmente, eu vou fazer isso. 514 00:22:42,350 --> 00:22:45,550 >> Assim, em um arquivo de cabeçalho em algum lugar, em list0.h 515 00:22:45,550 --> 00:22:49,200 hoje é esta definição struct, e talvez algumas outras coisas. 516 00:22:49,200 --> 00:22:52,580 Enquanto isso, na list0c há Vai ser algumas coisas. 517 00:22:52,580 --> 00:22:54,740 Mas vamos apenas começar e não terminar isso. 518 00:22:54,740 --> 00:22:59,690 List0.h é um arquivo que eu quero para incluir no meu arquivo C. 519 00:22:59,690 --> 00:23:03,910 E então, em algum momento eu sou vai ter int, principal, anular. 520 00:23:03,910 --> 00:23:06,530 E então eu vou tem algum de afazeres está aqui. 521 00:23:06,530 --> 00:23:10,620 Eu também vou ter um protótipo, como vazio, busca, int, 522 00:23:10,620 --> 00:23:13,610 n, cujo propósito na vida é para procurar um elemento. 523 00:23:13,610 --> 00:23:18,310 E então aqui eu afirmo em código de hoje, vazio, busca, int, n, 524 00:23:18,310 --> 00:23:21,020 nenhum ponto e vírgula, mas chaves abertas. 525 00:23:21,020 --> 00:23:25,049 E agora eu quero procurar alguma forma para um elemento na lista. 526 00:23:25,049 --> 00:23:27,340 Mas não temos o suficiente informação sobre a tela ainda. 527 00:23:27,340 --> 00:23:29,800 Eu não tenho, na verdade, representava a própria lista. 528 00:23:29,800 --> 00:23:33,070 Portanto, uma forma que pudéssemos implementar uma lista ligada de um programa 529 00:23:33,070 --> 00:23:37,520 é que eu meio que quero fazer algo como declarar lista ligada aqui. 530 00:23:37,520 --> 00:23:40,520 Para simplificar, eu vou fazer este global, mesmo que em geral nós 531 00:23:40,520 --> 00:23:41,645 não deve fazer isso demais. 532 00:23:41,645 --> 00:23:43,260 Mas vai simplificar este exemplo. 533 00:23:43,260 --> 00:23:45,890 Então, eu quero declarar uma lista ligada aqui. 534 00:23:45,890 --> 00:23:47,010 Agora, como eu poderia fazer isso? 535 00:23:47,010 --> 00:23:48,810 536 00:23:48,810 --> 00:23:50,750 >> Aqui está a foto de uma lista encadeada. 537 00:23:50,750 --> 00:23:53,030 E eu realmente não saber no momento como 538 00:23:53,030 --> 00:23:56,710 Eu estou indo para ir sobre a representação tantas coisas com apenas um 539 00:23:56,710 --> 00:23:58,040 variável na memória. 540 00:23:58,040 --> 00:23:59,160 Mas acho que volta um momento. 541 00:23:59,160 --> 00:24:00,830 Todo esse tempo que tivemos cordas, que depois 542 00:24:00,830 --> 00:24:02,913 revelou-se matrizes de caracteres, que depois 543 00:24:02,913 --> 00:24:05,740 revelou ser apenas um ponteiro para o primeiro carácter 544 00:24:05,740 --> 00:24:08,890 em um array de caracteres que tem um terminador nulo. 545 00:24:08,890 --> 00:24:13,530 Então, por essa lógica, e com isso tipo de imagem de semear seus pensamentos, 546 00:24:13,530 --> 00:24:17,964 Para que precisamos realmente escrever na nossa código para representar uma lista ligada? 547 00:24:17,964 --> 00:24:21,130 Como muitas dessas informações que precisamos para capturar em código C, você diria? 548 00:24:21,130 --> 00:24:22,654 549 00:24:22,654 --> 00:24:23,154 Sim? 550 00:24:23,154 --> 00:24:24,738 >> AUDIÊNCIA: Precisamos de um ponteiro para um nó. 551 00:24:24,738 --> 00:24:26,237 DAVID J. MALAN: Um ponteiro para um nó. 552 00:24:26,237 --> 00:24:29,320 Em particular, o que seria o seu nó instintos ser para manter um ponteiro para? 553 00:24:29,320 --> 00:24:30,026 >> AUDIÊNCIAS: O primeiro nó. 554 00:24:30,026 --> 00:24:31,942 >> DAVID J. MALAN: Sim, provavelmente apenas o primeiro. 555 00:24:31,942 --> 00:24:34,030 E note, o primeiro nó é uma forma diferente. 556 00:24:34,030 --> 00:24:37,690 É apenas a metade do tamanho da estrutura, porque é na verdade apenas um ponteiro. 557 00:24:37,690 --> 00:24:44,650 Então, o que você pode realmente fazer é declarar uma lista ligada para ser do tipo nó *. 558 00:24:44,650 --> 00:24:47,780 E vamos chamá-lo de primeira e inicialize-o como nulo. 559 00:24:47,780 --> 00:24:49,910 Então, null, mais uma vez, está chegando em cena aqui. 560 00:24:49,910 --> 00:24:53,620 Não só é nulo usado como como um especial valor de retorno para coisas como getString 561 00:24:53,620 --> 00:24:57,770 e malloc, nulo é também o zero ponteiro, a falta de um ponteiro, 562 00:24:57,770 --> 00:24:58,430 se você quiser. 563 00:24:58,430 --> 00:25:00,309 Significa apenas que nada está ainda aqui. 564 00:25:00,309 --> 00:25:02,100 Agora em primeiro lugar, eu poderia ter chamou isso de nada. 565 00:25:02,100 --> 00:25:04,200 Eu poderia tê-lo chamado "lista" ou qualquer número de outras coisas. 566 00:25:04,200 --> 00:25:06,960 Mas eu estou chamando-o de "primeiro" para que se alinha com esta imagem. 567 00:25:06,960 --> 00:25:10,280 Assim como uma corda pode ser representado com o endereço do seu primeiro byte 568 00:25:10,280 --> 00:25:11,280 pode assim uma lista ligada. 569 00:25:11,280 --> 00:25:13,480 E vamos ver outros dados estruturas ser representado 570 00:25:13,480 --> 00:25:16,700 com apenas um ponteiro, uma flecha de 32 bits, que aponta 571 00:25:16,700 --> 00:25:18,740 o primeiro nó na estrutura. 572 00:25:18,740 --> 00:25:20,340 >> Mas agora vamos antecipar um problema. 573 00:25:20,340 --> 00:25:23,230 Se eu só estou lembrando no meu programa o endereço 574 00:25:23,230 --> 00:25:27,220 do primeiro nó, o primeiro retângulo nesta estrutura de dados, 575 00:25:27,220 --> 00:25:31,760 o melhor que seja o caso sobre a implementação do resto da minha lista? 576 00:25:31,760 --> 00:25:35,820 O que é um detalhe chave que está acontecendo para garantir isso realmente funciona? 577 00:25:35,820 --> 00:25:39,250 E por "realmente funciona" Eu Quer dizer, muito parecido com uma corda, 578 00:25:39,250 --> 00:25:42,180 permite-nos ir a partir do primeiro caractere em nome do Davin para o segundo, 579 00:25:42,180 --> 00:25:44,755 para o terceiro, o quarto, até o fim, 580 00:25:44,755 --> 00:25:47,880 como sabemos quando estamos no final de uma lista encadeada que se parece com isso? 581 00:25:47,880 --> 00:25:50,035 582 00:25:50,035 --> 00:25:50,660 Quando é nulo. 583 00:25:50,660 --> 00:25:53,640 E eu tenho representado este tipo de como como uma força engenheiro elétrico, 584 00:25:53,640 --> 00:25:56,420 com o pouco de terra símbolo, das sortes. 585 00:25:56,420 --> 00:25:58,246 Mas isso apenas significa nulo neste caso. 586 00:25:58,246 --> 00:26:00,370 Você pode desenhar qualquer número de maneiras, mas o mesmo autor 587 00:26:00,370 --> 00:26:02,800 passou a utilizar este símbolo aqui. 588 00:26:02,800 --> 00:26:06,260 >> Enquanto nós estamos amarrando todos estes nodos juntos, 589 00:26:06,260 --> 00:26:08,600 só lembrando que a primeira é, desde 590 00:26:08,600 --> 00:26:11,760 como colocar um símbolo especial no o último nó na lista, 591 00:26:11,760 --> 00:26:15,130 e usaremos nulo, porque isso é o que temos à nossa disposição, 592 00:26:15,130 --> 00:26:16,480 esta lista está completa. 593 00:26:16,480 --> 00:26:20,190 E mesmo se eu apenas dar-lhe um ponteiro para o primeiro elemento, que, o programador, 594 00:26:20,190 --> 00:26:22,486 certamente pode acessar o resto. 595 00:26:22,486 --> 00:26:24,360 Mas vamos deixar suas mentes vagar um pouco, 596 00:26:24,360 --> 00:26:26,140 se eles não estão já bastante wandered-- o que é 597 00:26:26,140 --> 00:26:28,723 vai ser o tempo de execução encontrar alguma coisa nessa lista? 598 00:26:28,723 --> 00:26:30,450 599 00:26:30,450 --> 00:26:33,470 Porra, é grande O de n, que não é ruim, na justiça. 600 00:26:33,470 --> 00:26:34,800 Mas é linear. 601 00:26:34,800 --> 00:26:37,980 Temos dado o recurso de matrizes movendo mais 602 00:26:37,980 --> 00:26:43,130 para esse quadro de forma dinâmica entrelaçados ou nós ligados? 603 00:26:43,130 --> 00:26:44,970 604 00:26:44,970 --> 00:26:46,687 Nós desistimos de acesso aleatório. 605 00:26:46,687 --> 00:26:48,770 Uma matriz é bom porque matematicamente tudo 606 00:26:48,770 --> 00:26:50,340 está de volta para fazer a volta para trás. 607 00:26:50,340 --> 00:26:52,370 Mesmo que esta imagem parece muito, e mesmo 608 00:26:52,370 --> 00:26:55,830 mas parece que esses nós são bem espaçados entre si, na realidade 609 00:26:55,830 --> 00:26:56,830 eles poderiam estar em qualquer lugar. 610 00:26:56,830 --> 00:27:01,590 OX 1, Ox50, Ox123, Ox99, estes nós poderia estar em qualquer lugar. 611 00:27:01,590 --> 00:27:05,960 Porque malloc aloca memória da pilha, mas em qualquer lugar do heap. 612 00:27:05,960 --> 00:27:09,080 Você não necessariamente sabe que é vai ser back to back to back. 613 00:27:09,080 --> 00:27:12,460 E assim esta imagem em realidade não vai ser muito esta bonita. 614 00:27:12,460 --> 00:27:16,140 >> Então, ele vai levar um pouco de trabalhar para implementar essa função. 615 00:27:16,140 --> 00:27:17,880 Então, vamos implementar a pesquisa agora. 616 00:27:17,880 --> 00:27:20,250 E nós vamos ver uma espécie de maneira inteligente de fazer isso. 617 00:27:20,250 --> 00:27:24,660 Então, se eu sou uma função de pesquisa e Eu sou dado uma variável, inteiro n 618 00:27:24,660 --> 00:27:28,490 procurar, eu preciso saber o nova sintaxe para olhar para dentro 619 00:27:28,490 --> 00:27:32,400 de uma estrutura que está apontou, para encontrar n. 620 00:27:32,400 --> 00:27:33,210 Então, vamos fazer isso. 621 00:27:33,210 --> 00:27:36,030 >> Então, primeiro eu vou frente e declarar um nó *. 622 00:27:36,030 --> 00:27:39,400 E eu vou chamá-lo ponteiro, apenas por convenção. 623 00:27:39,400 --> 00:27:41,710 E eu estou indo para inicializar a primeira. 624 00:27:41,710 --> 00:27:43,770 E agora eu posso fazer isso em um número de maneiras. 625 00:27:43,770 --> 00:27:45,436 Mas eu vou ter uma abordagem comum. 626 00:27:45,436 --> 00:27:50,180 Enquanto apontador não é igual null, e isso é válido sintaxe. 627 00:27:50,180 --> 00:27:54,550 E isso significa apenas fazer o seguinte, de modo Contanto que você não está apontando para o nada. 628 00:27:54,550 --> 00:27:55,800 O que eu quero fazer? 629 00:27:55,800 --> 00:28:01,939 >> Se ponteiro ponto n, deixe-me voltar para que, equals-- iguala o quê? 630 00:28:01,939 --> 00:28:03,105 Qual o valor que eu estou procurando? 631 00:28:03,105 --> 00:28:04,920 632 00:28:04,920 --> 00:28:06,590 O n real que foi passado. 633 00:28:06,590 --> 00:28:09,020 Então aqui está uma outra característica de C e muitas línguas. 634 00:28:09,020 --> 00:28:13,705 Embora a estrutura chamada nó tem um valor de n, totalmente legítimo 635 00:28:13,705 --> 00:28:17,530 também ter um argumento locais ou variável chamada n. 636 00:28:17,530 --> 00:28:20,085 Porque mesmo que, com Os olhos humanos, pode-se distinguir 637 00:28:20,085 --> 00:28:22,087 que esta n é presumivelmente diferente deste n. 638 00:28:22,087 --> 00:28:23,420 Porque a sintaxe é diferente. 639 00:28:23,420 --> 00:28:26,211 Você tem um ponto e um ponteiro, enquanto este não tem tal coisa. 640 00:28:26,211 --> 00:28:27,290 Então, isso é OK. 641 00:28:27,290 --> 00:28:29,120 Isso é OK para chamar-lhes as mesmas coisas. 642 00:28:29,120 --> 00:28:32,380 >> Se eu não encontrar isso, eu sou vai querer fazer alguma coisa 643 00:28:32,380 --> 00:28:35,000 como anunciar que encontramos n. 644 00:28:35,000 --> 00:28:37,930 E nós vamos deixar isso como um comentar ou código de pseudocódigo. 645 00:28:37,930 --> 00:28:40,190 Outra coisa, e aqui está o parte interessante, o que 646 00:28:40,190 --> 00:28:47,320 eu gostaria de fazer se o nó atual não se contendo n que eu me importo com? 647 00:28:47,320 --> 00:28:50,700 Como faço para conseguir o seguinte? 648 00:28:50,700 --> 00:28:53,710 Se o meu dedo no momento é PTR, e é 649 00:28:53,710 --> 00:28:55,920 apontando para o que quer que primeiro está apontando, 650 00:28:55,920 --> 00:28:59,290 Como faço para mover meu dedo para o nó seguinte código? 651 00:28:59,290 --> 00:29:01,915 Bem, qual é a trilha que estamos vai seguir neste caso? 652 00:29:01,915 --> 00:29:03,464 653 00:29:03,464 --> 00:29:04,380 AUDIÊNCIA: [inaudível]. 654 00:29:04,380 --> 00:29:05,630 DAVID J. MALAN: Sim, por isso a seguir. 655 00:29:05,630 --> 00:29:06,640 656 00:29:06,640 --> 00:29:09,824 Então, se eu voltar para o meu código aqui, na verdade, eu sou 657 00:29:09,824 --> 00:29:12,990 indo para ir em frente e dizer ponteiro, que é apenas um variable-- temporária é 658 00:29:12,990 --> 00:29:15,320 um nome estranho, ptr, mas é como temp-- 659 00:29:15,320 --> 00:29:19,234 Vou configurar o ponteiro igual a qualquer ponteiro é-- 660 00:29:19,234 --> 00:29:22,150 e mais uma vez, isso vai ser um buggy pouco para um ponto moment-- seguinte. 661 00:29:22,150 --> 00:29:23,551 662 00:29:23,551 --> 00:29:26,550 Em outras palavras, eu vou tomar o meu dedo que está apontando para este nó 663 00:29:26,550 --> 00:29:31,247 aqui e eu vou dizer, você sabe o que, dê uma olhada no próximo campo 664 00:29:31,247 --> 00:29:33,330 e mover o dedo para seja o que está apontando. 665 00:29:33,330 --> 00:29:35,163 E isso vai repetir, repetir, repetir. 666 00:29:35,163 --> 00:29:37,630 Mas quando o meu dedo deixar de fazer alguma coisa? 667 00:29:37,630 --> 00:29:40,095 Tão logo que linha de código em chutes? 668 00:29:40,095 --> 00:29:40,970 AUDIÊNCIA: [inaudível] 669 00:29:40,970 --> 00:29:43,060 DAVID J. MALAN: Se o ponto enquanto ponteiro não é igual a null. 670 00:29:43,060 --> 00:29:44,900 Em algum momento o meu dedo do vai estar apontando para nulo 671 00:29:44,900 --> 00:29:47,070 e eu estou indo para perceber isso é o fim da lista. 672 00:29:47,070 --> 00:29:48,910 Agora, este é um pouco mentirinha para simplificar. 673 00:29:48,910 --> 00:29:51,580 Acontece que, embora acabou de aprender esta notação de ponto 674 00:29:51,580 --> 00:29:55,220 para estruturas, o ponteiro não é um struct. 675 00:29:55,220 --> 00:29:56,580 ptr é o quê? 676 00:29:56,580 --> 00:29:58,350 Apenas para ser mais detalhista. 677 00:29:58,350 --> 00:29:59,720 678 00:29:59,720 --> 00:30:01,360 É um ponteiro para um nó. 679 00:30:01,360 --> 00:30:03,120 Não é um nó em si. 680 00:30:03,120 --> 00:30:06,650 Se eu não tinha nenhuma estrela aqui, ponteiro absolutely-- é um nó. 681 00:30:06,650 --> 00:30:08,650 Isto é como uma semana declaração de uma variável, 682 00:30:08,650 --> 00:30:10,120 embora a palavra "nó" é novo. 683 00:30:10,120 --> 00:30:13,860 >> Mas assim que introduzir um estrela, agora é um ponteiro para um nó. 684 00:30:13,860 --> 00:30:17,960 E, infelizmente, você não pode usar a notação de ponto para um ponteiro. 685 00:30:17,960 --> 00:30:21,070 Você tem que usar a seta notação, o que, surpreendentemente, 686 00:30:21,070 --> 00:30:23,470 é a primeira vez que um pedaço de sintaxe parece intuitiva. 687 00:30:23,470 --> 00:30:25,245 Isso literalmente parece uma flecha. 688 00:30:25,245 --> 00:30:26,370 E isso é uma coisa boa. 689 00:30:26,370 --> 00:30:28,995 E aqui embaixo, literalmente parece uma flecha. 690 00:30:28,995 --> 00:30:31,870 Então, eu acho que é a la-- eu não acho que estou over-cometer aqui-- I 691 00:30:31,870 --> 00:30:34,120 acho que é a última peça nova de sintaxe, vamos ver. 692 00:30:34,120 --> 00:30:36,500 E, felizmente, é de fato um pouco mais intuitivo. 693 00:30:36,500 --> 00:30:40,090 >> Agora, para aqueles de vocês que pode preferir a velha forma, 694 00:30:40,090 --> 00:30:42,550 Você ainda pode usar a notação de ponto. 695 00:30:42,550 --> 00:30:45,380 Mas como por segunda-feira de conversa, primeiro 696 00:30:45,380 --> 00:30:50,530 precisa ir lá, ir para esse abordar, em seguida, acessar o campo. 697 00:30:50,530 --> 00:30:51,897 Então, isso também é correto. 698 00:30:51,897 --> 00:30:53,730 E, francamente, este é um pouco mais pedante. 699 00:30:53,730 --> 00:30:56,530 Você está literalmente dizendo, desreferenciava o ponteiro e ir para lá. 700 00:30:56,530 --> 00:30:59,320 Em seguida, pegue .n, o campo chamado n. 701 00:30:59,320 --> 00:31:01,370 Mas, francamente, ninguém quer para escrever ou ler isto. 702 00:31:01,370 --> 00:31:03,620 E assim o mundo inventado a notação de seta, que 703 00:31:03,620 --> 00:31:06,980 é equivalente, idêntica, é apenas um açúcar sintático. 704 00:31:06,980 --> 00:31:10,570 Assim, uma maneira elegante de dizer isso parece melhor, ou parece mais simples. 705 00:31:10,570 --> 00:31:12,296 >> Então, agora eu vou fazer outra coisa. 706 00:31:12,296 --> 00:31:15,420 Eu vou dizer "quebrar" uma vez que eu achei tão eu não continuar olhando para ele. 707 00:31:15,420 --> 00:31:17,620 Mas esta é a essência de uma função de pesquisa. 708 00:31:17,620 --> 00:31:21,710 Mas é muito mais fácil, no final, não andar através do código. 709 00:31:21,710 --> 00:31:25,570 Este é de facto a implementação formal de pesquisa em código de distribuição de hoje. 710 00:31:25,570 --> 00:31:30,530 Ouso dizer que inserir não é particularmente diversão a pé 711 00:31:30,530 --> 00:31:33,180 visualmente, nem apagar, mesmo no entanto, no final do dia 712 00:31:33,180 --> 00:31:35,460 eles se resumem a bastante heurísticas simples. 713 00:31:35,460 --> 00:31:36,330 >> Então, vamos fazer isso. 714 00:31:36,330 --> 00:31:39,250 Se você vai humor me aqui, eu fiz trazer um monte de bolas de stress. 715 00:31:39,250 --> 00:31:40,620 Eu trouxe um monte de números. 716 00:31:40,620 --> 00:31:46,562 E poderíamos obter apenas alguns voluntários para representar a 9, 17, 20, 22, 29, e 34? 717 00:31:46,562 --> 00:31:48,270 Então, basicamente todos quem está aqui hoje. 718 00:31:48,270 --> 00:31:50,170 719 00:31:50,170 --> 00:31:52,760 Isso foi um, dois, três, quatro, cinco, seis pessoas. 720 00:31:52,760 --> 00:31:55,740 E eu fui convidado a vai-- ver, não uma na parte de trás levanta as mãos. 721 00:31:55,740 --> 00:32:01,910 OK, um, dois, três, quatro, cinco-- deixe-me carregar balance-- seis. 722 00:32:01,910 --> 00:32:03,051 OK, você seis suba. 723 00:32:03,051 --> 00:32:04,050 Vamos precisar de outras pessoas. 724 00:32:04,050 --> 00:32:05,460 Trouxemos stress bolas extras. 725 00:32:05,460 --> 00:32:08,200 E se você poderia, por apenas um momento, a linha 726 00:32:08,200 --> 00:32:10,490 -vos apenas como esta foto aqui. 727 00:32:10,490 --> 00:32:15,200 728 00:32:15,200 --> 00:32:15,959 >> Tudo certo. 729 00:32:15,959 --> 00:32:17,125 Vamos ver, qual é o seu nome? 730 00:32:17,125 --> 00:32:17,550 >> AUDIÊNCIA: Andrew. 731 00:32:17,550 --> 00:32:18,800 >> DAVID J. MALAN: Andrew, você é o número 9. 732 00:32:18,800 --> 00:32:19,540 Prazer em conhecê-lo. 733 00:32:19,540 --> 00:32:20,400 Aqui você vai. 734 00:32:20,400 --> 00:32:21,593 735 00:32:21,593 --> 00:32:22,176 AUDIÊNCIA: Jen. 736 00:32:22,176 --> 00:32:22,662 DAVID J. MALAN: Jen. 737 00:32:22,662 --> 00:32:23,162 David. 738 00:32:23,162 --> 00:32:23,765 Número 17. 739 00:32:23,765 --> 00:32:24,950 740 00:32:24,950 --> 00:32:25,450 Sim? 741 00:32:25,450 --> 00:32:26,400 >> AUDIÊNCIA: Eu sou Julia. 742 00:32:26,400 --> 00:32:26,980 >> DAVID J. MALAN: Julia, David. 743 00:32:26,980 --> 00:32:27,545 Número 20. 744 00:32:27,545 --> 00:32:28,507 745 00:32:28,507 --> 00:32:29,340 AUDIÊNCIA: Christian. 746 00:32:29,340 --> 00:32:30,715 DAVID J. MALAN: Christian, David. 747 00:32:30,715 --> 00:32:31,541 Número 22. 748 00:32:31,541 --> 00:32:32,040 E? 749 00:32:32,040 --> 00:32:32,649 >> AUDIÊNCIA: JP. 750 00:32:32,649 --> 00:32:33,440 DAVID J. MALAN: JP. 751 00:32:33,440 --> 00:32:34,880 Número 29. 752 00:32:34,880 --> 00:32:37,080 Então vá em frente e obter em-- Uh oh. 753 00:32:37,080 --> 00:32:38,486 754 00:32:38,486 --> 00:32:38,985 Uh oh. 755 00:32:38,985 --> 00:32:39,650 756 00:32:39,650 --> 00:32:40,150 Espera. 757 00:32:40,150 --> 00:32:41,360 758 00:32:41,360 --> 00:32:42,390 20. 759 00:32:42,390 --> 00:32:43,682 Alguém tem um marcador? 760 00:32:43,682 --> 00:32:44,890 AUDIÊNCIA: Eu tenho uma Sharpie. 761 00:32:44,890 --> 00:32:45,660 DAVID J. MALAN: Você tem um Sharpie? 762 00:32:45,660 --> 00:32:46,159 Está bem. 763 00:32:46,159 --> 00:32:47,577 764 00:32:47,577 --> 00:32:49,160 E alguém tem um pedaço de papel? 765 00:32:49,160 --> 00:32:51,562 766 00:32:51,562 --> 00:32:52,270 Salve a palestra. 767 00:32:52,270 --> 00:32:53,810 768 00:32:53,810 --> 00:32:55,362 Venha. 769 00:32:55,362 --> 00:32:56,320 AUDIÊNCIA: Nós temos isso. 770 00:32:56,320 --> 00:32:57,600 DAVID J. MALAN: Temos isso? 771 00:32:57,600 --> 00:32:58,577 Tudo bem, obrigado. 772 00:32:58,577 --> 00:33:01,380 773 00:33:01,380 --> 00:33:02,520 Aqui vamos nós. 774 00:33:02,520 --> 00:33:03,582 Foi isso de você? 775 00:33:03,582 --> 00:33:04,540 Você acabou de salvar o dia. 776 00:33:04,540 --> 00:33:05,670 777 00:33:05,670 --> 00:33:07,220 Então, 29. 778 00:33:07,220 --> 00:33:10,510 779 00:33:10,510 --> 00:33:11,110 Tudo certo. 780 00:33:11,110 --> 00:33:13,360 781 00:33:13,360 --> 00:33:14,890 Eu mal escrito 29, mas OK. 782 00:33:14,890 --> 00:33:15,720 Continue. 783 00:33:15,720 --> 00:33:18,114 Tudo bem, eu vou te dar a caneta de volta momentaneamente. 784 00:33:18,114 --> 00:33:19,280 Então, temos essas pessoas aqui. 785 00:33:19,280 --> 00:33:20,330 Vamos ter um outro. 786 00:33:20,330 --> 00:33:23,750 Gabe, você quer jogar o primeiro elemento aqui? 787 00:33:23,750 --> 00:33:25,705 Vamos precisar de você para apontar a essas pessoas finas. 788 00:33:25,705 --> 00:33:26,930 789 00:33:26,930 --> 00:33:31,030 Então, 9, 17, 20, 22, espécie de 29, e depois 34. 790 00:33:31,030 --> 00:33:32,160 791 00:33:32,160 --> 00:33:33,325 Será que vamos perder alguém? 792 00:33:33,325 --> 00:33:33,950 Eu tenho um 34. 793 00:33:33,950 --> 00:33:36,730 Onde fez-- OK, quem quer ser 34? 794 00:33:36,730 --> 00:33:37,605 OK, vamos lá para cima, 34. 795 00:33:37,605 --> 00:33:39,280 796 00:33:39,280 --> 00:33:41,220 Tudo bem, este será valeu a pena o clímax. 797 00:33:41,220 --> 00:33:41,550 Qual o seu nome? 798 00:33:41,550 --> 00:33:42,040 >> AUDIÊNCIA: Peter. 799 00:33:42,040 --> 00:33:43,456 >> DAVID J. MALAN: Peter, vamos lá para cima. 800 00:33:43,456 --> 00:33:46,810 Tudo bem, então aqui está um grupo inteiro de nós. 801 00:33:46,810 --> 00:33:49,060 Cada um de vocês representa um desses retângulos. 802 00:33:49,060 --> 00:33:51,930 E Gabe, a um pouco estranho homem para fora, representa o primeiro. 803 00:33:51,930 --> 00:33:54,850 Assim, seu ponteiro é um pouco menor na tela do que todos os outros. 804 00:33:54,850 --> 00:33:58,120 E, neste caso, cada um sua esquerda mãos vai ou apontar para baixo, 805 00:33:58,120 --> 00:34:01,085 representando, assim, nulo, de modo apenas na ausência de um ponteiro, 806 00:34:01,085 --> 00:34:03,210 ou ele vai estar apontando em um nó ao lado de você. 807 00:34:03,210 --> 00:34:05,440 >> Então, agora, se você enfeitar vós semelhantes a imagem 808 00:34:05,440 --> 00:34:07,585 aqui, vá em frente e ponto um para o outro, com Gabe 809 00:34:07,585 --> 00:34:11,030 em particular, que aponta no o número 9 para representar a lista. 810 00:34:11,030 --> 00:34:14,050 OK, eo número 34, sua mão esquerda deve apenas estar apontando para o chão. 811 00:34:14,050 --> 00:34:15,750 >> OK, então esta é a lista encadeada. 812 00:34:15,750 --> 00:34:17,580 Portanto, este é o cenário em questão. 813 00:34:17,580 --> 00:34:20,210 E, de fato, este é representante de uma classe de problemas 814 00:34:20,210 --> 00:34:21,929 que você pode tentar resolver com o código. 815 00:34:21,929 --> 00:34:25,020 Você deseja inserir em última instância um novo elemento na lista. 816 00:34:25,020 --> 00:34:27,494 Neste caso, vamos tente inserir o número 55. 817 00:34:27,494 --> 00:34:28,500 818 00:34:28,500 --> 00:34:30,860 Mas não vai ser casos diferentes a considerar. 819 00:34:30,860 --> 00:34:34,409 E, de fato, este vai ser um do grande-retrato takeaways aqui, é, 820 00:34:34,409 --> 00:34:35,659 quais são os diferentes casos. 821 00:34:35,659 --> 00:34:39,120 Quais são os diferentes se as condições ou ramos que o programa possa ter? 822 00:34:39,120 --> 00:34:42,024 >> Bem, o número que você está tentando inserção, que sabemos agora para ser 55, 823 00:34:42,024 --> 00:34:44,650 mas se você não sabia com antecedência, eu diria 824 00:34:44,650 --> 00:34:47,840 cai, pelo menos, três situações possíveis. 825 00:34:47,840 --> 00:34:49,717 Onde pode um elemento novo ser? 826 00:34:49,717 --> 00:34:51,050 AUDIÊNCIA: E o fim ou meio. 827 00:34:51,050 --> 00:34:54,150 David J. MALAN: No final, em no meio, ou no início. 828 00:34:54,150 --> 00:34:56,650 Então, eu afirmo que há pelo menos três problemas que precisamos resolver. 829 00:34:56,650 --> 00:34:58,691 Vamos escolher o que é, talvez, sem dúvida o mais simples 830 00:34:58,691 --> 00:35:01,090 um, em que o novo elemento pertence no início. 831 00:35:01,090 --> 00:35:04,040 Então, eu vou ter bastante código como pesquisar, o que eu acabei de escrever. 832 00:35:04,040 --> 00:35:07,670 E eu vou ter ptr, que Eu vou representar aqui com o meu dedo, 833 00:35:07,670 --> 00:35:08,370 como de costume. 834 00:35:08,370 --> 00:35:12,430 >> E lembre-se, o valor fizemos inicializar ptr para? 835 00:35:12,430 --> 00:35:15,300 Por isso, ele inicializado como nulo inicialmente. 836 00:35:15,300 --> 00:35:16,410 837 00:35:16,410 --> 00:35:19,770 Mas então o que nós fizemos, uma vez que estavam dentro da nossa função de pesquisa? 838 00:35:19,770 --> 00:35:20,940 839 00:35:20,940 --> 00:35:24,870 Nós configurá-lo igual ao primeiro, o que não significa fazer isso. 840 00:35:24,870 --> 00:35:25,890 841 00:35:25,890 --> 00:35:30,570 Se eu definir ptr igual ao primeiro, o que deve ser realmente a minha mão apontando? 842 00:35:30,570 --> 00:35:31,070 Certo. 843 00:35:31,070 --> 00:35:33,290 Então, se Gabe e eu vamos ser valores iguais aqui, 844 00:35:33,290 --> 00:35:34,760 precisamos tanto do ponto no número 9. 845 00:35:34,760 --> 00:35:36,420 >> Portanto, este foi o início de nossa história. 846 00:35:36,420 --> 00:35:38,700 E agora este é apenas simples, mesmo que a sintaxe é novo. 847 00:35:38,700 --> 00:35:40,580 Conceitualmente, esta é apenas a pesquisa linear. 848 00:35:40,580 --> 00:35:42,750 É 55 igual a 9? 849 00:35:42,750 --> 00:35:45,559 Ou melhor, vamos dizer menos do que 9. 850 00:35:45,559 --> 00:35:47,600 Porque eu estou tentando descobrir onde colocar 55. 851 00:35:47,600 --> 00:35:51,270 Menos de 9, menos de 17, menos de 20, menos de 22, menos de 29, 852 00:35:51,270 --> 00:35:52,510 menos do que 34, n. 853 00:35:52,510 --> 00:35:55,080 Portanto, agora estamos em caso um de pelo menos três. 854 00:35:55,080 --> 00:35:59,910 >> Se eu quiser inserir 55 para cá, o que linhas de código necessidade de ter executado? 855 00:35:59,910 --> 00:36:01,890 Como é que esse quadro de os seres humanos precisam mudar? 856 00:36:01,890 --> 00:36:03,181 O que eu faço com a mão esquerda? 857 00:36:03,181 --> 00:36:04,530 858 00:36:04,530 --> 00:36:07,360 Isto deve ser inicialmente nula, porque eu estou no fim da lista. 859 00:36:07,360 --> 00:36:09,318 E o que deve acontecer aqui com Peter, foi? 860 00:36:09,318 --> 00:36:10,520 861 00:36:10,520 --> 00:36:12,430 Ele está, obviamente, vai apontar para mim. 862 00:36:12,430 --> 00:36:15,580 Então, eu afirmo que há pelo menos duas linhas de código no código de exemplo a partir de hoje 863 00:36:15,580 --> 00:36:18,570 que vai implementar este cenário de adição de 55 na cauda. 864 00:36:18,570 --> 00:36:20,950 E eu poderia ter alguém hop e representam apenas 55? 865 00:36:20,950 --> 00:36:22,200 Tudo bem, você é o novo 55. 866 00:36:22,200 --> 00:36:23,580 867 00:36:23,580 --> 00:36:27,054 >> Então, agora que se o próximo cenário vem junto, 868 00:36:27,054 --> 00:36:29,720 e queremos inserir no início ou a cabeça de lista? 869 00:36:29,720 --> 00:36:31,100 E qual é o seu nome, o número 55? 870 00:36:31,100 --> 00:36:31,420 >> AUDIÊNCIA: Jack. 871 00:36:31,420 --> 00:36:32,295 >> DAVID J. MALAN: Jack? 872 00:36:32,295 --> 00:36:33,585 OK, prazer em conhecê-lo. 873 00:36:33,585 --> 00:36:34,210 Bem-vindo a bordo. 874 00:36:34,210 --> 00:36:36,640 Então agora nós vamos inserir, por exemplo, o número 5. 875 00:36:36,640 --> 00:36:39,840 Este é o segundo caso do três nós viemos com antes. 876 00:36:39,840 --> 00:36:43,050 Assim, se pertence 5 no início, vamos ver como podemos descobrir isso. 877 00:36:43,050 --> 00:36:46,310 Eu inicializar o meu ptr ponteiro para o 9 novamente. 878 00:36:46,310 --> 00:36:49,140 E eu percebi, oh, 5 é inferior a 9. 879 00:36:49,140 --> 00:36:50,880 Então corrigir esta imagem para nós. 880 00:36:50,880 --> 00:36:54,820 Cujas mãos, Gabe ou David de ou-- qual é o nome do número 9? 881 00:36:54,820 --> 00:36:55,740 >> AUDIÊNCIA: Jen. 882 00:36:55,740 --> 00:36:58,406 >> DAVID J. MALAN: hands-- de Jen que de nossas mãos precisa mudar? 883 00:36:58,406 --> 00:36:58,905 884 00:36:58,905 --> 00:37:00,970 OK, então Gabe aponta para o que agora? 885 00:37:00,970 --> 00:37:01,640 Para mim. 886 00:37:01,640 --> 00:37:02,750 Eu sou o novo nó. 887 00:37:02,750 --> 00:37:04,870 Então eu vou tipo de movimento aqui para vê-lo visualmente. 888 00:37:04,870 --> 00:37:06,435 E enquanto isso o que eu apontar isso? 889 00:37:06,435 --> 00:37:07,910 890 00:37:07,910 --> 00:37:09,020 Ainda assim, onde eu estou apontando. 891 00:37:09,020 --> 00:37:10,000 Então é isso. 892 00:37:10,000 --> 00:37:13,717 Então, só realmente uma linha de correções de código esta questão em particular, ao que parece. 893 00:37:13,717 --> 00:37:14,800 Tudo bem, então isso é bom. 894 00:37:14,800 --> 00:37:17,580 E alguém pode ser um marcador para 5? 895 00:37:17,580 --> 00:37:18,080 Vamos lá para cima. 896 00:37:18,080 --> 00:37:20,270 897 00:37:20,270 --> 00:37:21,320 Nós vamos tirar você da próxima vez. 898 00:37:21,320 --> 00:37:24,280 >> Tudo bem, então agora-- e Como um aparte, os nomes 899 00:37:24,280 --> 00:37:28,510 Eu não estou fazendo menção explícita de direito agora, ponteiro pred, ponteiro antecessor 900 00:37:28,510 --> 00:37:31,260 e novo ponteiro, que é apenas os nomes dado 901 00:37:31,260 --> 00:37:35,280 no código de exemplo para os ponteiros ou minhas mãos que é tipo de apontar ao redor. 902 00:37:35,280 --> 00:37:36,060 Qual o seu nome? 903 00:37:36,060 --> 00:37:36,700 >> AUDIÊNCIA: Christine. 904 00:37:36,700 --> 00:37:37,100 >> DAVID J. MALAN: Christine. 905 00:37:37,100 --> 00:37:38,090 Bem-vindo a bordo. 906 00:37:38,090 --> 00:37:42,180 Tudo bem, então vamos considerar agora um cenário um pouco mais chato, 907 00:37:42,180 --> 00:37:46,350 pelo qual eu quero inserir algo como 26 para isso. 908 00:37:46,350 --> 00:37:47,090 20? 909 00:37:47,090 --> 00:37:47,590 O quê? 910 00:37:47,590 --> 00:37:50,510 Estes é-- coisa boa que temos esta caneta. 911 00:37:50,510 --> 00:37:51,955 Tudo bem, 20. 912 00:37:51,955 --> 00:37:53,640 913 00:37:53,640 --> 00:37:57,570 Se alguém pudesse ter outra peça de papel pronto, apenas em caso-- tudo bem. 914 00:37:57,570 --> 00:37:58,370 Oh, interessante. 915 00:37:58,370 --> 00:37:59,760 916 00:37:59,760 --> 00:38:02,390 Bem, este é um exemplo de um bug palestra. 917 00:38:02,390 --> 00:38:03,894 OK então, qual é o seu nome? 918 00:38:03,894 --> 00:38:04,560 AUDIÊNCIA: Julia. 919 00:38:04,560 --> 00:38:07,559 DAVID J. MALAN: Julia, você pode pop para fora e fingir que nunca foram lá? 920 00:38:07,559 --> 00:38:09,040 OK, isso nunca aconteceu. 921 00:38:09,040 --> 00:38:09,680 Obrigado. 922 00:38:09,680 --> 00:38:12,180 Então, suponha que queremos inserir Julia para esta lista ligada. 923 00:38:12,180 --> 00:38:13,780 Ela é o número 20. 924 00:38:13,780 --> 00:38:15,530 E, claro, ela é vai pertencer ao 925 00:38:15,530 --> 00:38:17,521 begin-- não apontam para nada ainda. 926 00:38:17,521 --> 00:38:20,020 Então sua mão pode ser tipo de baixo valor nulo ou algum lixo. 927 00:38:20,020 --> 00:38:21,210 Vamos contar a história rápida. 928 00:38:21,210 --> 00:38:22,980 Eu estou apontando para o número 5 desta vez. 929 00:38:22,980 --> 00:38:23,880 Então eu verifico 9. 930 00:38:23,880 --> 00:38:25,130 Então eu verifico 17. 931 00:38:25,130 --> 00:38:26,247 Então eu verifico 22. 932 00:38:26,247 --> 00:38:27,650 933 00:38:27,650 --> 00:38:32,485 E eu percebo, ooh, Julia precisa ir antes de 22. 934 00:38:32,485 --> 00:38:33,580 935 00:38:33,580 --> 00:38:34,660 Então, o que precisa acontecer? 936 00:38:34,660 --> 00:38:35,786 937 00:38:35,786 --> 00:38:36,910 Cujas mãos precisa mudar? 938 00:38:36,910 --> 00:38:38,360 Julia, minha, ou-- Qual é o seu nome? 939 00:38:38,360 --> 00:38:39,230 >> AUDIÊNCIA: Christian. 940 00:38:39,230 --> 00:38:40,060 >> DAVID J. MALAN: Christian ou? 941 00:38:40,060 --> 00:38:40,560 >> AUDIÊNCIA: Andy. 942 00:38:40,560 --> 00:38:40,905 >> DAVID J. MALAN: Andy. 943 00:38:40,905 --> 00:38:41,654 Christian ou Andy? 944 00:38:41,654 --> 00:38:44,280 945 00:38:44,280 --> 00:38:45,690 Andy precisa apontar? 946 00:38:45,690 --> 00:38:46,780 947 00:38:46,780 --> 00:38:47,341 Julia. 948 00:38:47,341 --> 00:38:47,840 Tudo certo. 949 00:38:47,840 --> 00:38:48,960 Então, Andy, você quer apontar para Julia? 950 00:38:48,960 --> 00:38:50,120 Mas espere um minuto. 951 00:38:50,120 --> 00:38:53,260 Na história, até agora, Eu sou o tipo de uma 952 00:38:53,260 --> 00:38:56,800 em carga, no sentido de que ponteiro é a coisa que é 953 00:38:56,800 --> 00:38:57,850 movendo-se através da lista. 954 00:38:57,850 --> 00:39:00,800 Podemos ter um nome para Andy, mas não há nenhuma variável chamada Andy. 955 00:39:00,800 --> 00:39:04,320 A única outra variável que temos é primeiro, que está representado por Gabe. 956 00:39:04,320 --> 00:39:07,690 >> Portanto, este é, na verdade, porque assim agora não tenho necessidade disso. 957 00:39:07,690 --> 00:39:10,846 Mas agora na tela existe falar novamente do ponteiro pred. 958 00:39:10,846 --> 00:39:11,970 Então deixe-me ser mais explícita. 959 00:39:11,970 --> 00:39:14,820 Se esta é ponteiro, eu tinha melhor ficar um pouco mais inteligente 960 00:39:14,820 --> 00:39:15,950 sobre minha iteração. 961 00:39:15,950 --> 00:39:19,580 Se você não se importa de passar por aqui novamente, que aponta aqui, que aponta aqui. 962 00:39:19,580 --> 00:39:22,500 Mas deixe-me ter um ponteiro pred, ponteiro antecessor, que é 963 00:39:22,500 --> 00:39:24,740 tipo de apontar para o elemento que eu estava apenas no. 964 00:39:24,740 --> 00:39:27,330 Então, quando eu ir para lá, agora minha esquerda atualizações manuais. 965 00:39:27,330 --> 00:39:29,370 Quando vou aqui minhas atualizações mão esquerda. 966 00:39:29,370 --> 00:39:33,090 E agora eu tenho não só um ponteiro para o elemento que vai atrás de Julia, 967 00:39:33,090 --> 00:39:36,300 Eu ainda tenho um ponteiro para Andy, o elemento antes. 968 00:39:36,300 --> 00:39:39,430 Então, você tem acesso, essencialmente, farinha de rosca, se quiser, 969 00:39:39,430 --> 00:39:41,500 para todas as indicações necessárias. 970 00:39:41,500 --> 00:39:43,710 >> Então, se eu estou apontando para Andy e eu também estou apontando 971 00:39:43,710 --> 00:39:47,105 na cristã, cujas mãos agora deve ser apontado em outro lugar? 972 00:39:47,105 --> 00:39:48,770 973 00:39:48,770 --> 00:39:51,960 Então Andy agora pode apontar para Julia. 974 00:39:51,960 --> 00:39:54,460 Julia agora pode apontar para Christian. 975 00:39:54,460 --> 00:39:56,950 Porque ela pode copiar a minha ponteiro do lado direito. 976 00:39:56,950 --> 00:40:00,044 E que efetivamente coloca você de volta a este lugar aqui. 977 00:40:00,044 --> 00:40:02,460 Assim, em breve, mesmo que isso está nos levando espécie de sempre 978 00:40:02,460 --> 00:40:04,510 realmente atualizar um lista ligada, perceber 979 00:40:04,510 --> 00:40:06,580 que as operações são relativamente simples. 980 00:40:06,580 --> 00:40:10,030 É de um, dois, três linhas de código no final. 981 00:40:10,030 --> 00:40:12,780 Mas envolto em torno daqueles linhas de código presumivelmente 982 00:40:12,780 --> 00:40:16,350 é um pouco de lógica que efetivamente faz a pergunta: onde estamos? 983 00:40:16,350 --> 00:40:18,970 Estamos no início, no meio, ou o fim? 984 00:40:18,970 --> 00:40:21,890 >> Agora, certamente há alguma outra operações que possam implementar. 985 00:40:21,890 --> 00:40:24,880 E essas fotos aqui apenas retratam o que nós fizemos com os seres humanos. 986 00:40:24,880 --> 00:40:26,080 E quanto a remoção? 987 00:40:26,080 --> 00:40:30,650 Se eu quiser, por exemplo, remover o número 34 ou 55, 988 00:40:30,650 --> 00:40:34,680 Eu poderia ter o mesmo tipo de código, mas eu vou precisar de um ou dois passos. 989 00:40:34,680 --> 00:40:36,110 Porque o que há de novo? 990 00:40:36,110 --> 00:40:40,460 Se eu remover alguém no final, como número 55 e depois 34, 991 00:40:40,460 --> 00:40:42,995 o que também tem de mudar como eu faço isso? 992 00:40:42,995 --> 00:40:44,870 Eu tenho que não evict-- Qual é o seu nome? 993 00:40:44,870 --> 00:40:45,380 >> AUDIÊNCIA: Jack. 994 00:40:45,380 --> 00:40:46,255 >> DAVID J. MALAN: Jack. 995 00:40:46,255 --> 00:40:49,770 Eu tenho não só evict-- livre Jack, tão literalmente ligar gratuitamente Jack, ou pelo menos 996 00:40:49,770 --> 00:40:53,530 o ponteiro lá também, mas agora o que precisa mudar com Peter? 997 00:40:53,530 --> 00:40:55,510 Sua mão melhor começar a apontar para baixo. 998 00:40:55,510 --> 00:40:59,300 Porque assim que eu chamo livre em Jack, se de Pedro ainda apontando para Jack 999 00:40:59,300 --> 00:41:02,530 e, portanto, eu continuo percorrendo a lista e acesso este ponteiro, 1000 00:41:02,530 --> 00:41:05,650 que é quando o nosso velho amigo segmentação falha pode realmente chutar. 1001 00:41:05,650 --> 00:41:07,860 Porque nós temos dado o memória de volta para Jack. 1002 00:41:07,860 --> 00:41:10,760 >> Você pode ficar lá desajeitadamente por apenas um momento. 1003 00:41:10,760 --> 00:41:13,410 Porque nós temos apenas um par operações finais a considerar. 1004 00:41:13,410 --> 00:41:15,600 Removendo o cabeça de lista, ou o beginning-- e este do 1005 00:41:15,600 --> 00:41:16,349 um pouco chato. 1006 00:41:16,349 --> 00:41:19,640 Porque nós temos que saber que Gabe é uma espécie de especial neste programa. 1007 00:41:19,640 --> 00:41:21,440 Porque, na verdade, ele tem seu próprio ponteiro. 1008 00:41:21,440 --> 00:41:24,860 Ele não está apenas a ser apontada para, como é quase todo mundo aqui. 1009 00:41:24,860 --> 00:41:28,112 >> Assim, quando a cabeça da lista é removida, cujas mãos precisa mudar agora? 1010 00:41:28,112 --> 00:41:29,070 Qual é o seu nome? 1011 00:41:29,070 --> 00:41:29,450 >> AUDIÊNCIA: Christine. 1012 00:41:29,450 --> 00:41:31,408 >> DAVID J. MALAN: Eu sou terrível em nomes, aparentemente. 1013 00:41:31,408 --> 00:41:34,011 Então Christine e Gabe, cujas mãos precisa mudar 1014 00:41:34,011 --> 00:41:36,510 quando tentamos remover Christine, número 5, a partir da imagem? 1015 00:41:36,510 --> 00:41:37,550 1016 00:41:37,550 --> 00:41:38,820 OK, então vamos fazer Gabe. 1017 00:41:38,820 --> 00:41:40,950 Gabe vai apontar, presumivelmente, no número 9. 1018 00:41:40,950 --> 00:41:42,230 1019 00:41:42,230 --> 00:41:44,642 Mas o que deve acontecer no próximo? 1020 00:41:44,642 --> 00:41:46,600 AUDIÊNCIA: Christine deveria ser nulo [inaudível]. 1021 00:41:46,600 --> 00:41:50,244 DAVID J. MALAN: OK, nós devemos provavelmente make-- eu ouvi "nulo" em algum lugar. 1022 00:41:50,244 --> 00:41:51,410 AUDIÊNCIA: Null e libertá-la. 1023 00:41:51,410 --> 00:41:51,855 DAVID J. MALAN: null o que? 1024 00:41:51,855 --> 00:41:53,074 AUDIÊNCIA: Null e libertá-la. 1025 00:41:53,074 --> 00:41:54,490 DAVID J. MALAN: Null e libertá-la. 1026 00:41:54,490 --> 00:41:55,422 Então isso é muito fácil. 1027 00:41:55,422 --> 00:41:58,380 E é perfeito que você agora é espécie de pé, não pertencer. 1028 00:41:58,380 --> 00:42:00,430 Porque você foi dissociado da lista. 1029 00:42:00,430 --> 00:42:02,820 Você tem sido eficaz órfãos a partir da lista. 1030 00:42:02,820 --> 00:42:07,770 E assim seria melhor ligar gratuitamente agora Christine dar essa memória de volta. 1031 00:42:07,770 --> 00:42:10,240 Caso contrário, cada vez que apagar um nó da lista 1032 00:42:10,240 --> 00:42:14,230 fôssemos fazer a lista mais curto, mas não realmente a diminuir 1033 00:42:14,230 --> 00:42:15,096 o tamanho da memória. 1034 00:42:15,096 --> 00:42:17,720 E assim se continuar a acrescentar e acrescentando, acrescentando coisas para a lista, 1035 00:42:17,720 --> 00:42:19,280 meu computador pode ficar mais lento e mais lento e mais lento, 1036 00:42:19,280 --> 00:42:21,740 porque eu estou ficando sem memória, mesmo que eu não sou realmente 1037 00:42:21,740 --> 00:42:25,580 usando bytes de Christine de memória mais. 1038 00:42:25,580 --> 00:42:28,500 >> Então, no final, há outra cenários, de remoção course-- 1039 00:42:28,500 --> 00:42:30,640 no meio, a remoção no final, como vimos. 1040 00:42:30,640 --> 00:42:32,348 Mas o mais interessante desafio agora é 1041 00:42:32,348 --> 00:42:34,770 vai ser a considerar exatamente que o tempo de execução é. 1042 00:42:34,770 --> 00:42:36,640 Assim, não só você pode manter sua pedaços de papel, se, Gabe, 1043 00:42:36,640 --> 00:42:38,640 você não se importaria de dar todos uma bola anti-stress. 1044 00:42:38,640 --> 00:42:42,100 Muito obrigado à nossa lista ligada de voluntários aqui, se pudesse. 1045 00:42:42,100 --> 00:42:45,320 >> [Aplausos] 1046 00:42:45,320 --> 00:42:46,700 >> DAVID J. MALAN: Tudo bem. 1047 00:42:46,700 --> 00:42:51,110 Assim, um par de analítica perguntas, então, se eu pudesse. 1048 00:42:51,110 --> 00:42:59,670 Nós já vimos isso antes de notação, O grande e omega, limites superiores 1049 00:42:59,670 --> 00:43:02,520 e limites mais baixos no tempo de funcionamento de um algoritmo. 1050 00:43:02,520 --> 00:43:04,950 Então, vamos considerar apenas um par de perguntas. 1051 00:43:04,950 --> 00:43:07,090 >> Um deles, e nós dissemos que antes, o que é o funcionamento 1052 00:43:07,090 --> 00:43:10,647 tempo de busca por um lista em termos de grande O? 1053 00:43:10,647 --> 00:43:13,480 O que é um limite superior sobre o funcionamento tempo de busca de uma lista ligada 1054 00:43:13,480 --> 00:43:16,340 como implementado pelos nossos voluntários aqui? 1055 00:43:16,340 --> 00:43:17,820 É grande O de n, linear. 1056 00:43:17,820 --> 00:43:20,630 Porque, na pior das hipóteses, o elemento, como 55, 1057 00:43:20,630 --> 00:43:23,830 que pode estar procurando pode ser onde Jack era, todo o caminho no final. 1058 00:43:23,830 --> 00:43:28,250 E, infelizmente, ao contrário de um array não podemos começar a fantasia neste momento. 1059 00:43:28,250 --> 00:43:31,820 Apesar de todos os nossos seres humanos eram classificadas a partir de pequenos elementos, 5, 1060 00:43:31,820 --> 00:43:35,900 todo o caminho até o elemento de maior, 55, que geralmente é uma coisa boa. 1061 00:43:35,900 --> 00:43:38,815 Mas o que faz essa suposição já não nos permitem fazer? 1062 00:43:38,815 --> 00:43:39,775 1063 00:43:39,775 --> 00:43:40,650 AUDIÊNCIA: [inaudível] 1064 00:43:40,650 --> 00:43:40,920 DAVID J. MALAN: Diga de novo? 1065 00:43:40,920 --> 00:43:41,800 AUDIÊNCIA: acesso aleatório. 1066 00:43:41,800 --> 00:43:43,049 DAVID J. MALAN: acesso aleatório. 1067 00:43:43,049 --> 00:43:46,330 E por sua vez, isso significa que não podemos mais usar zeros fraco, intuição, 1068 00:43:46,330 --> 00:43:49,365 e evidência de utilização de binário pesquisar e dividir e conquistar. 1069 00:43:49,365 --> 00:43:51,240 Porque, embora nós os seres humanos poderiam, obviamente, 1070 00:43:51,240 --> 00:43:54,610 ver que Andy ou Christian foram mais ou menos no meio da lista, 1071 00:43:54,610 --> 00:43:57,670 só sabemos que como um computador por desnatação à lista 1072 00:43:57,670 --> 00:43:59,029 desde o início. 1073 00:43:59,029 --> 00:44:00,570 Então, nós temos que desistiu de acesso aleatório. 1074 00:44:00,570 --> 00:44:04,380 >> Tão grande O de n agora é o superior obrigado em nosso tempo de busca. 1075 00:44:04,380 --> 00:44:07,920 E sobre ômega de nossa busca? 1076 00:44:07,920 --> 00:44:11,535 Qual é o limite inferior na busca para algum número nesta lista? 1077 00:44:11,535 --> 00:44:12,410 AUDIÊNCIA: [inaudível] 1078 00:44:12,410 --> 00:44:13,040 DAVID J. MALAN: Diga de novo? 1079 00:44:13,040 --> 00:44:13,420 AUDIÊNCIA: One. 1080 00:44:13,420 --> 00:44:13,800 DAVID J. MALAN: One. 1081 00:44:13,800 --> 00:44:14,760 Tempo tão constante. 1082 00:44:14,760 --> 00:44:17,020 No melhor dos casos, é Christine de facto, no início da lista. 1083 00:44:17,020 --> 00:44:19,020 E nós estamos procurando número 5, de modo que a encontrou. 1084 00:44:19,020 --> 00:44:19,787 Portanto, não é grande coisa. 1085 00:44:19,787 --> 00:44:22,370 Mas ela tem que estar no início da lista, neste caso. 1086 00:44:22,370 --> 00:44:23,745 Que tal algo como excluir? 1087 00:44:23,745 --> 00:44:24,717 1088 00:44:24,717 --> 00:44:26,300 E se você quiser excluir um elemento? 1089 00:44:26,300 --> 00:44:29,200 Qual é o limite superior e limite inferior sobre a eliminação de algo a partir de um ligado 1090 00:44:29,200 --> 00:44:29,699 lista? 1091 00:44:29,699 --> 00:44:35,195 1092 00:44:35,195 --> 00:44:36,070 AUDIÊNCIA: [inaudível] 1093 00:44:36,070 --> 00:44:36,420 DAVID J. MALAN: Diga de novo? 1094 00:44:36,420 --> 00:44:37,067 AUDIÊNCIA: n. 1095 00:44:37,067 --> 00:44:38,900 David J. MALAN: n é na verdade, o limite superior. 1096 00:44:38,900 --> 00:44:41,700 Porque, no pior caso tentamos excluir Jack, como acabamos de fazer. 1097 00:44:41,700 --> 00:44:43,050 Ele é todo o caminho no final. 1098 00:44:43,050 --> 00:44:45,419 Leva-nos para sempre, ou n passos para encontrá-lo. 1099 00:44:45,419 --> 00:44:46,460 Então, isso é um limite superior. 1100 00:44:46,460 --> 00:44:47,430 Isso é linear, com certeza. 1101 00:44:47,430 --> 00:44:50,970 E o melhor caso de tempo de execução, ou os limites inferiores na melhor das hipóteses 1102 00:44:50,970 --> 00:44:51,975 haveria tempo constante. 1103 00:44:51,975 --> 00:44:54,600 Porque talvez a gente tente apagar Christine, e nós apenas ter sorte 1104 00:44:54,600 --> 00:44:55,558 ela está no começo. 1105 00:44:55,558 --> 00:44:56,350 Agora, espere um minuto. 1106 00:44:56,350 --> 00:44:59,370 Gabe também estava no início, e nós também tivemos que atualizar Gabe. 1107 00:44:59,370 --> 00:45:01,150 Para que não foi apenas um passo. 1108 00:45:01,150 --> 00:45:04,210 Então é isso, já constante tempo, no melhor dos casos, 1109 00:45:04,210 --> 00:45:06,345 para remover o elemento mais pequeno? 1110 00:45:06,345 --> 00:45:07,360 1111 00:45:07,360 --> 00:45:10,960 É, ainda que possa ser de dois, três, ou até 100 linhas de código, 1112 00:45:10,960 --> 00:45:14,000 se é o mesmo número de linhas, não em algum loop, 1113 00:45:14,000 --> 00:45:16,577 e independente do tamanho da lista, com certeza. 1114 00:45:16,577 --> 00:45:18,660 Excluindo o elemento no o início da lista, 1115 00:45:18,660 --> 00:45:21,940 mesmo que tenhamos de lidar com Gabe, ainda é tempo constante. 1116 00:45:21,940 --> 00:45:24,220 >> Portanto, este parece ser um enorme passo para trás. 1117 00:45:24,220 --> 00:45:27,000 E o que é um desperdício de tempo Se, em uma semana e na semana 1118 00:45:27,000 --> 00:45:30,250 zero, tivemos não só código pseudocódigo mas o código real 1119 00:45:30,250 --> 00:45:35,780 para implementar algo que é log base de n, ou registro, em vez disso, de n, base 2, 1120 00:45:35,780 --> 00:45:37,150 em termos de seu tempo de execução. 1121 00:45:37,150 --> 00:45:40,710 Então, por que diabos seria queremos começar usando algo como uma lista ligada? 1122 00:45:40,710 --> 00:45:41,517 Sim. 1123 00:45:41,517 --> 00:45:44,022 >> AUDIÊNCIA: Então, você pode adicionar elementos para a matriz. 1124 00:45:44,022 --> 00:45:46,230 DAVID J. MALAN: Então você pode adicionar elementos à matriz. 1125 00:45:46,230 --> 00:45:47,550 E isso também é temática. 1126 00:45:47,550 --> 00:45:49,740 E vamos continuar a ver este, este trade-off, muito 1127 00:45:49,740 --> 00:45:51,573 como já vimos um trade-off com merge sort. 1128 00:45:51,573 --> 00:45:54,606 Nós realmente poderia acelerar pesquisar ou classificar, em vez disso, 1129 00:45:54,606 --> 00:45:57,480 se passar um pouco mais de espaço e tem um pedaço de uma memória adicional 1130 00:45:57,480 --> 00:45:58,760 ou uma matriz para merge sort. 1131 00:45:58,760 --> 00:46:01,270 Mas nós gastamos mais espaço, mas economizar tempo. 1132 00:46:01,270 --> 00:46:04,820 Neste caso, estamos dando-se tempo, mas estamos 1133 00:46:04,820 --> 00:46:08,170 ganhando flexibilidade, dinamismo, se quiserem, 1134 00:46:08,170 --> 00:46:10,280 que é sem dúvida uma característica positiva. 1135 00:46:10,280 --> 00:46:11,520 >> Nós também estamos gastando espaço. 1136 00:46:11,520 --> 00:46:13,710 Em que sentido é um ligado listar mais caro 1137 00:46:13,710 --> 00:46:15,700 em termos de espaço de uma matriz? 1138 00:46:15,700 --> 00:46:18,379 1139 00:46:18,379 --> 00:46:19,920 Onde está o espaço extra vem? 1140 00:46:19,920 --> 00:46:20,460 Sim? 1141 00:46:20,460 --> 00:46:21,800 >> AUDIÊNCIA: ponteiro [inaudível]. 1142 00:46:21,800 --> 00:46:23,310 >> DAVID J. MALAN: Sim, nós também tem o ponteiro. 1143 00:46:23,310 --> 00:46:25,560 Então, isso é chato minorly em que não sou mais 1144 00:46:25,560 --> 00:46:27,780 Eu armazenar apenas um int representar um int. 1145 00:46:27,780 --> 00:46:30,990 Eu sou armazenar um int e um apontador, que é também de 32 bits. 1146 00:46:30,990 --> 00:46:33,470 Então, eu estou literalmente dobrando a quantidade de espaço envolvido. 1147 00:46:33,470 --> 00:46:36,040 Então isso é um trade-off, mas que é, no caso de int. 1148 00:46:36,040 --> 00:46:39,580 Suponha que você não está armazenando int, mas suponho que cada um desses retângulos 1149 00:46:39,580 --> 00:46:43,290 ou cada um desses seres humanos estava representando uma palavra, uma palavra em Inglês que 1150 00:46:43,290 --> 00:46:46,430 pode ser de cinco caracteres, 10 caracteres, talvez até mais. 1151 00:46:46,430 --> 00:46:49,940 Em seguida, adicionando apenas 32 mais bits pode ser menos de um grande negócio. 1152 00:46:49,940 --> 00:46:52,160 >> O que se cada um dos estudantes na manifestação 1153 00:46:52,160 --> 00:46:55,107 foram literalmente estruturas estudantis que têm nomes e casas e talvez 1154 00:46:55,107 --> 00:46:57,065 números de telefone e Twitter lida e semelhantes. 1155 00:46:57,065 --> 00:46:59,564 Assim, todos os campos que começamos falando no outro dia, 1156 00:46:59,564 --> 00:47:02,410 muito menos de um grande negócio, nossos nós ficam mais interessantes 1157 00:47:02,410 --> 00:47:05,972 e grande para gastar, eh, um adicional ponteiro só para conectá-los. 1158 00:47:05,972 --> 00:47:07,180 Mas, na verdade, é um trade-off. 1159 00:47:07,180 --> 00:47:09,560 E, de fato, o código é mais complexa, como você vai 1160 00:47:09,560 --> 00:47:11,770 ver ao percorre que o exemplo particular. 1161 00:47:11,770 --> 00:47:14,302 Mas o que se havia algum santo graal aqui. 1162 00:47:14,302 --> 00:47:17,010 E se nós não dar um passo para trás, mas um grande passo para a frente 1163 00:47:17,010 --> 00:47:19,180 e implementar um conjunto de dados estrutura através do qual se 1164 00:47:19,180 --> 00:47:22,870 pode encontrar elementos como Jack ou Christine ou quaisquer outros elementos 1165 00:47:22,870 --> 00:47:25,870 nessa matriz em verdadeiro tempo constante? 1166 00:47:25,870 --> 00:47:26,920 A busca é constante. 1167 00:47:26,920 --> 00:47:28,320 Excluir é constante. 1168 00:47:28,320 --> 00:47:29,570 Insert é constante. 1169 00:47:29,570 --> 00:47:32,260 Todas estas operações são constantes. 1170 00:47:32,260 --> 00:47:33,750 Isso seria o nosso santo graal. 1171 00:47:33,750 --> 00:47:36,690 E é aí que nós vai pegar na próxima vez. 1172 00:47:36,690 --> 00:47:38,600 Vejo vocês depois. 1173 00:47:38,600 --> 00:47:39,371