1 00:00:00,000 --> 00:00:00,500 2 00:00:00,500 --> 00:00:05,120 [Música tocando] 3 00:00:05,120 --> 00:00:12,026 4 00:00:12,026 --> 00:00:12,900 COLUNA 1: Tudo bem. 5 00:00:12,900 --> 00:00:14,600 Todos bem-vindos de volta à seção. 6 00:00:14,600 --> 00:00:18,660 Espero que todos estão com sucesso recuperado de seu quiz 7 00:00:18,660 --> 00:00:19,510 desde a semana passada. 8 00:00:19,510 --> 00:00:22,564 Eu sei que é um pouco louco, às vezes. 9 00:00:22,564 --> 00:00:25,230 Como eu estava dizendo antes, se você estiver dentro do desvio padrão, 10 00:00:25,230 --> 00:00:28,188 realmente não se preocupe com isso, especialmente para uma secção menos confortável. 11 00:00:28,188 --> 00:00:30,230 Isso é sobre onde você deveria estar. 12 00:00:30,230 --> 00:00:32,850 >> Se você fez grande, então incrível. 13 00:00:32,850 --> 00:00:33,650 Kudos para você. 14 00:00:33,650 --> 00:00:36,149 E se você sentir que você precisa um pouco mais de ajuda, por favor 15 00:00:36,149 --> 00:00:38,140 sinta-se livre para chegar para fora a qualquer um dos FT. 16 00:00:38,140 --> 00:00:40,030 Estamos todos aqui para ajudar. 17 00:00:40,030 --> 00:00:40,960 >> É por isso que nós ensinamos. 18 00:00:40,960 --> 00:00:44,550 É por isso que eu estou aqui toda segunda-feira para você rapazes e no escritório horas às quintas-feiras. 19 00:00:44,550 --> 00:00:48,130 Então, por favor, sinta-se livre para me deixar saber se você está preocupado com nada 20 00:00:48,130 --> 00:00:52,450 ou se há alguma coisa sobre o quiz que você realmente gostaria de abordar. 21 00:00:52,450 --> 00:00:56,940 >> Assim, a agenda para hoje é tudo sobre estruturas de dados. 22 00:00:56,940 --> 00:01:01,520 Algumas delas são apenas vai ser apenas para que você obtenha familiarizados com estes. 23 00:01:01,520 --> 00:01:04,870 Você não pode sempre implementar los nesta classe. 24 00:01:04,870 --> 00:01:08,690 Alguns deles você vai, como para o seu pset ortográfico. 25 00:01:08,690 --> 00:01:11,380 >> Você vai ter a sua escolha entre tabelas hash e tentativas. 26 00:01:11,380 --> 00:01:13,680 Então, nós vamos, sem dúvida vamos sobre aqueles. 27 00:01:13,680 --> 00:01:18,690 Vai ser definitivamente mais do tipo uma secção de alto nível hoje, no entanto, 28 00:01:18,690 --> 00:01:22,630 porque há um monte deles, e se fomos para os detalhes de implementação 29 00:01:22,630 --> 00:01:26,490 em todas elas, não teríamos mesmo passar por listas ligadas 30 00:01:26,490 --> 00:01:28,520 e talvez um pouco de tabelas de hash. 31 00:01:28,520 --> 00:01:31,200 >> Então, tenha paciência comigo. 32 00:01:31,200 --> 00:01:33,530 Nós não estamos indo fazer tanto de codificação desta vez. 33 00:01:33,530 --> 00:01:36,870 Se você tiver quaisquer perguntas sobre o assunto ou você quer ver implementado 34 00:01:36,870 --> 00:01:39,260 ou experimentar por si próprio, Eu recomendo definitivamente 35 00:01:39,260 --> 00:01:44,250 indo study.cs50.net, que tem exemplos de todos estes. 36 00:01:44,250 --> 00:01:46,400 Ele vai ter meus PowerPoints com as notas que nós 37 00:01:46,400 --> 00:01:50,860 tendem a usar, bem como alguma programação exercícios, especialmente para as coisas 38 00:01:50,860 --> 00:01:55,250 como listas ligadas e binário árvores pilhas e sugestões. 39 00:01:55,250 --> 00:01:59,590 Tão pouco mais alto nível, que Pode ser bom para vocês. 40 00:01:59,590 --> 00:02:01,320 >> Então, com isso, vamos começar. 41 00:02:01,320 --> 00:02:03,060 E também, quizzes sim--. 42 00:02:03,060 --> 00:02:06,550 Acho que a maioria de vocês que estão em minha seção tem seus questionários, 43 00:02:06,550 --> 00:02:12,060 mas ninguém entra ou algum motivo você não, eles estão aqui na frente. 44 00:02:12,060 --> 00:02:12,740 >> Assim listas ligadas. 45 00:02:12,740 --> 00:02:15,650 Eu sei que este tipo de vai para trás antes de seu quiz. 46 00:02:15,650 --> 00:02:17,940 Essa foi a semana antes que aprendemos sobre isso. 47 00:02:17,940 --> 00:02:21,040 Mas, neste caso, nós vamos ir um pouco mais em profundidade. 48 00:02:21,040 --> 00:02:25,900 >> Então, por que poderíamos escolher um lista ligada através de uma matriz? 49 00:02:25,900 --> 00:02:27,130 O que os distingue? 50 00:02:27,130 --> 00:02:27,630 Sim? 51 00:02:27,630 --> 00:02:30,464 >> AUDIÊNCIA: Você pode expandir um ligado listar contra tamanho fixo de um array. 52 00:02:30,464 --> 00:02:31,171 COLUNA 1: Certo. 53 00:02:31,171 --> 00:02:33,970 Uma matriz tem tamanho fixo enquanto que uma lista ligada tem um tamanho variável. 54 00:02:33,970 --> 00:02:36,970 Então, se nós não sabemos como tanto que queremos armazenar, 55 00:02:36,970 --> 00:02:39,880 uma lista ligada nos dá uma grande maneira de fazer isso porque nós podemos apenas 56 00:02:39,880 --> 00:02:43,730 adicionar em outro nó e adicionar outro nó e adicionar em outro nó. 57 00:02:43,730 --> 00:02:45,750 Mas o que poderia ser um trade-off? 58 00:02:45,750 --> 00:02:49,521 Alguém se lembra do trade-off entre matrizes e listas ligadas? 59 00:02:49,521 --> 00:02:50,020 Mmhmm? 60 00:02:50,020 --> 00:02:51,460 >> AUDIÊNCIA: Você tem que percorrer todo o caminho 61 00:02:51,460 --> 00:02:53,738 através da lista ligada encontrar um elemento em uma lista. 62 00:02:53,738 --> 00:02:55,570 Em uma matriz, você pode apenas encontrar um elemento. 63 00:02:55,570 --> 00:02:56,278 >> COLUNA 1: Certo. 64 00:02:56,278 --> 00:02:57,120 Assim, com arrays-- 65 00:02:57,120 --> 00:02:58,500 >> AUDIÊNCIA: [inaudível]. 66 00:02:58,500 --> 00:03:01,090 >> COLUNA 1: Com matrizes, temos o que é chamado de acesso aleatório. 67 00:03:01,090 --> 00:03:04,820 Significa que, se queremos o que é já o quinto ponto de uma lista 68 00:03:04,820 --> 00:03:07,230 ou o quinto ponto da nossa array, podemos apenas agarrá-lo. 69 00:03:07,230 --> 00:03:10,440 Se é uma lista ligada, temos para percorrer, certo? 70 00:03:10,440 --> 00:03:14,020 Então acessar um elemento em uma matriz é constante de tempo, 71 00:03:14,020 --> 00:03:19,530 enquanto que com uma lista ligada que seria provavelmente será o tempo linear, porque talvez 72 00:03:19,530 --> 00:03:21,370 nosso elemento é todo o caminho no final. 73 00:03:21,370 --> 00:03:23,446 Temos que procurar através de tudo. 74 00:03:23,446 --> 00:03:25,320 Assim, com todos estes dados estruturas que vamos 75 00:03:25,320 --> 00:03:29,330 gastar um pouco mais de tempo em diante, quais são os pontos positivos e negativos. 76 00:03:29,330 --> 00:03:31,480 Quando poderia queremos usar um sobre o outro? 77 00:03:31,480 --> 00:03:34,970 E esse é o tipo de grande coisa para levar. 78 00:03:34,970 --> 00:03:40,140 >> Portanto, temos aqui a definição de um nó. 79 00:03:40,140 --> 00:03:43,040 É como um elemento nossa lista ligada, certo? 80 00:03:43,040 --> 00:03:46,180 Então, estamos todos familiarizados com as nossas estruturas typedef, 81 00:03:46,180 --> 00:03:47,980 que fomos na avaliação da última vez. 82 00:03:47,980 --> 00:03:53,180 Era basicamente apenas criar outro tipo de dados que poderíamos usar. 83 00:03:53,180 --> 00:03:57,930 >> E, neste caso, é um nó que irá realizar algum inteiro em. 84 00:03:57,930 --> 00:04:00,210 E então o que é a segunda parte aqui? 85 00:04:00,210 --> 00:04:03,192 86 00:04:03,192 --> 00:04:05,677 Qualquer um? 87 00:04:05,677 --> 00:04:06,680 >> AUDIÊNCIA: [inaudível]. 88 00:04:06,680 --> 00:04:07,020 >> COLUNA 1: Sim. 89 00:04:07,020 --> 00:04:08,400 É um ponteiro para o próximo nó. 90 00:04:08,400 --> 00:04:12,610 Portanto, este deve realmente estar aqui em cima. 91 00:04:12,610 --> 00:04:18,790 Este é um tipo de ponteiro nó para a próxima coisa. 92 00:04:18,790 --> 00:04:22,410 E isso é o que eles engloba o nosso nó. 93 00:04:22,410 --> 00:04:24,060 Legal. 94 00:04:24,060 --> 00:04:29,390 >> Tudo bem, então com a pesquisa, como estávamos apenas dizendo antes da mão, se você estiver 95 00:04:29,390 --> 00:04:31,840 vai pesquisar, você tem que realmente fazer uma iteração 96 00:04:31,840 --> 00:04:33,660 através de sua lista ligada. 97 00:04:33,660 --> 00:04:38,530 Então, se nós estamos olhando para o número 9, que iria começar na nossa cabeça 98 00:04:38,530 --> 00:04:41,520 e que nos aponta para o início da nossa lista ligada, certo? 99 00:04:41,520 --> 00:04:44,600 E nós dizemos: OK, faz isso nó conter o número 9? 100 00:04:44,600 --> 00:04:45,690 Não? 101 00:04:45,690 --> 00:04:47,500 >> Tudo bem, vá para a próxima. 102 00:04:47,500 --> 00:04:48,312 Siga-o. 103 00:04:48,312 --> 00:04:49,520 Será que ela contém o número 9? 104 00:04:49,520 --> 00:04:50,570 Não. 105 00:04:50,570 --> 00:04:51,550 Siga o próximo. 106 00:04:51,550 --> 00:04:55,490 >> Então nós temos que realmente iteração através da nossa lista ligada. 107 00:04:55,490 --> 00:05:00,070 Não podemos simplesmente ir diretamente para onde 9 é. 108 00:05:00,070 --> 00:05:05,860 E se vocês realmente querem ver alguns pseudo-código lá em cima. 109 00:05:05,860 --> 00:05:10,420 Temos alguma função de pesquisa aqui que leva em-- o que é preciso em? 110 00:05:10,420 --> 00:05:13,110 111 00:05:13,110 --> 00:05:14,320 O que você acha? 112 00:05:14,320 --> 00:05:15,960 Uma tão fácil. 113 00:05:15,960 --> 00:05:17,784 O que é isso? 114 00:05:17,784 --> 00:05:18,700 AUDIÊNCIA: [inaudível]. 115 00:05:18,700 --> 00:05:20,366 COLUNA 1: O número que estamos procurando. 116 00:05:20,366 --> 00:05:20,980 Certo? 117 00:05:20,980 --> 00:05:22,875 E o que seria isso corresponde a? 118 00:05:22,875 --> 00:05:25,020 É um ponteiro para? 119 00:05:25,020 --> 00:05:26,000 >> AUDIÊNCIA: um nó. 120 00:05:26,000 --> 00:05:28,980 >> COLUNA 1: Um nó à lista que nós estamos olhando, certo? 121 00:05:28,980 --> 00:05:33,700 Portanto, temos alguns nós são ponteiro aqui. 122 00:05:33,700 --> 00:05:37,240 Este é um ponto que vai realmente iterar nossa lista. 123 00:05:37,240 --> 00:05:39,630 Nós configurá-lo igual a listar porque isso é apenas 124 00:05:39,630 --> 00:05:44,380 fixando-a igual ao início da nossa lista ligada. 125 00:05:44,380 --> 00:05:50,660 >> E enquanto não é NULL, enquanto ainda temos coisas em nossa lista, 126 00:05:50,660 --> 00:05:55,580 verificar para ver se esse nó tem o número que estamos procurando. 127 00:05:55,580 --> 00:05:57,740 Retorna verdadeiro. 128 00:05:57,740 --> 00:06:01,070 Caso contrário, atualizá-lo, certo? 129 00:06:01,070 --> 00:06:04,870 >> Se for NULL, saímos nossa while e retornar falso 130 00:06:04,870 --> 00:06:08,340 porque isso significa que não tê-lo encontrado. 131 00:06:08,340 --> 00:06:11,048 Será que todo mundo começa como isso funciona? 132 00:06:11,048 --> 00:06:11,548 Está bem. 133 00:06:11,548 --> 00:06:14,940 134 00:06:14,940 --> 00:06:20,260 >> Assim, com a inserção, você ter três formas diferentes. 135 00:06:20,260 --> 00:06:25,250 Você pode preceder, você pode acrescentar e você pode inserir em sortidas. 136 00:06:25,250 --> 00:06:28,215 Neste caso, estamos vai fazer um preceder. 137 00:06:28,215 --> 00:06:33,380 Alguém sabe como aqueles três casos pode ser diferente? 138 00:06:33,380 --> 00:06:36,920 >> Então preceder significa que você colocar ele na frente da sua lista. 139 00:06:36,920 --> 00:06:39,770 Então, isso significa que não importa que o nó é, não importa 140 00:06:39,770 --> 00:06:43,160 qual é o valor, você vai para colocá-lo aqui na frente, OK? 141 00:06:43,160 --> 00:06:45,160 Vai ser o primeiro elemento em sua lista. 142 00:06:45,160 --> 00:06:49,510 >> Se você anexá-lo, ele vai para ir para a parte de trás de sua lista. 143 00:06:49,510 --> 00:06:54,010 E inserir em variados significa que você está vai colocar realmente no lugar 144 00:06:54,010 --> 00:06:57,700 onde ele mantém sua lista ligada ordenada. 145 00:06:57,700 --> 00:07:00,810 Mais uma vez, como você usa os e quando você usa 146 00:07:00,810 --> 00:07:02,530 eles irão variar de acordo com o seu caso. 147 00:07:02,530 --> 00:07:05,834 148 00:07:05,834 --> 00:07:07,750 Se ele não precisa ser classificado, anteposta tende 149 00:07:07,750 --> 00:07:10,460 ser o que a maioria das pessoas usar, porque você não faz 150 00:07:10,460 --> 00:07:15,680 tem que passar por toda a lista para encontrar o fim de adicioná-lo, certo? 151 00:07:15,680 --> 00:07:17,720 Você pode simplesmente colocá-lo em direito. 152 00:07:17,720 --> 00:07:21,930 >> Então, vamos passar por um inserção 1 agora. 153 00:07:21,930 --> 00:07:26,360 Então, uma coisa que eu vou recomendo neste pset 154 00:07:26,360 --> 00:07:29,820 é chamar as coisas, como sempre. 155 00:07:29,820 --> 00:07:35,130 É muito importante que você atualize os ponteiros na ordem correta 156 00:07:35,130 --> 00:07:38,620 porque se você atualizá-los um pouco fora de ordem, 157 00:07:38,620 --> 00:07:42,210 você vai acabar perda de partes da sua lista. 158 00:07:42,210 --> 00:07:49,680 >> Assim, por exemplo, neste caso, estamos contando a cabeça para apenas um ponto a 1. 159 00:07:49,680 --> 00:07:56,070 Se nós apenas fazer isso sem salvar este 1, 160 00:07:56,070 --> 00:07:58,570 nós não temos nenhuma idéia do que 1 deve apontar para agora 161 00:07:58,570 --> 00:08:02,490 porque nós perdemos o a cabeça apontada. 162 00:08:02,490 --> 00:08:05,530 Então, uma coisa para lembrar quando você está fazendo um preceder 163 00:08:05,530 --> 00:08:09,630 é salvar o que o cabeça pontos para o primeiro, 164 00:08:09,630 --> 00:08:15,210 Depois, atribua-o e atualize o que o seu novo nó deve apontar para. 165 00:08:15,210 --> 00:08:20,870 166 00:08:20,870 --> 00:08:22,560 Neste caso, esta é uma maneira de fazê-lo. 167 00:08:22,560 --> 00:08:25,440 >> Então, se tivéssemos feito isso dessa maneira onde nós apenas transferido cabeça, 168 00:08:25,440 --> 00:08:30,320 perdemos basicamente nossa lista inteira, certo? 169 00:08:30,320 --> 00:08:38,000 Uma maneira de fazer isso é ter um ponto de seguinte, e depois ter ponto cabeça para 1. 170 00:08:38,000 --> 00:08:42,650 Ou você pode fazer como o tipo de armazenamento temporário, de que falei. 171 00:08:42,650 --> 00:08:45,670 >> Mas a reatribuição seu ponteiros na ordem correta 172 00:08:45,670 --> 00:08:48,750 vai ser muito, muito importante para este pset. 173 00:08:48,750 --> 00:08:53,140 Caso contrário, você vai ter um hash mesa ou uma tentativa que só vai ser 174 00:08:53,140 --> 00:08:56,014 apenas uma parte das palavras que você quer e então you're-- mmhmm? 175 00:08:56,014 --> 00:08:58,930 AUDIÊNCIA: Qual foi o temporário coisa de armazenamento que você estava falando? 176 00:08:58,930 --> 00:09:00,305 COLUNA 1: O armazenamento temporário. 177 00:09:00,305 --> 00:09:02,760 Então, basicamente, outra maneira que você poderia fazer isso 178 00:09:02,760 --> 00:09:07,650 é armazenar o chefe de alguma coisa, como armazená-lo na variável temporária. 179 00:09:07,650 --> 00:09:11,250 Atribuí-la a um e em seguida, atualizar 1 ao ponto 180 00:09:11,250 --> 00:09:13,830 para qualquer cabeça usado para apontar para. 181 00:09:13,830 --> 00:09:16,920 Desta forma é obviamente mais elegante, porque você 182 00:09:16,920 --> 00:09:20,770 Não é necessário um valor temporário, mas apenas oferecer uma outra maneira de fazê-lo. 183 00:09:20,770 --> 00:09:23,999 184 00:09:23,999 --> 00:09:25,790 E nós realmente temos um código para esta. 185 00:09:25,790 --> 00:09:28,080 Assim, para lista ligada, nós realmente tem algum código. 186 00:09:28,080 --> 00:09:31,930 Então insira aqui, este é antecedendo. 187 00:09:31,930 --> 00:09:34,290 Portanto, este entra nele na cabeça. 188 00:09:34,290 --> 00:09:38,820 >> Então a primeira coisa, você precisa criar seu novo nó, é claro, 189 00:09:38,820 --> 00:09:40,790 e verificar se há NULL. 190 00:09:40,790 --> 00:09:43,250 Sempre bom. 191 00:09:43,250 --> 00:09:47,840 E então você precisa para atribuir os valores. 192 00:09:47,840 --> 00:09:51,260 Sempre que você cria um novo nó, você Não sei o que ele está apontando para o próximo, 193 00:09:51,260 --> 00:09:54,560 assim que você quer inicializar para NULL. 194 00:09:54,560 --> 00:09:58,760 Se ele acabar apontando para algo outra coisa, ele é transferido e está tudo bem. 195 00:09:58,760 --> 00:10:00,740 Se é a primeira coisa na lista, ele precisa 196 00:10:00,740 --> 00:10:04,270 para apontar para NULL porque isso é o fim da lista. 197 00:10:04,270 --> 00:10:12,410 >> Então para inseri-lo, vemos aqui nós está atribuindo o próximo valor do nosso nó 198 00:10:12,410 --> 00:10:17,380 para ser o cabeça, que é o que nós tivemos aqui. 199 00:10:17,380 --> 00:10:19,930 Isso é o que nós fizemos. 200 00:10:19,930 --> 00:10:25,820 E então nós estamos atribuindo cabeça para ponto ao nosso novo nó, porque lembre-se, 201 00:10:25,820 --> 00:10:31,090 é algum novo ponteiro para um nó, e isso é exatamente o que é cabeça. 202 00:10:31,090 --> 00:10:34,370 É exatamente por isso que tem esse assessor seta. 203 00:10:34,370 --> 00:10:37,030 204 00:10:37,030 --> 00:10:37,530 Legal? 205 00:10:37,530 --> 00:10:38,130 Mmhmm? 206 00:10:38,130 --> 00:10:41,100 >> AUDIÊNCIA: Será que temos que inicializar novo ao lado de NULL em primeiro lugar, 207 00:10:41,100 --> 00:10:44,240 ou podemos simplesmente inicializá-lo de cabeça? 208 00:10:44,240 --> 00:10:48,210 >> COLUNA 1: New próxima precisa de ser NULL para iniciar 209 00:10:48,210 --> 00:10:53,760 porque você não sabe onde vai ser. 210 00:10:53,760 --> 00:10:56,100 Além disso, esta é uma espécie de Assim como um paradigma. 211 00:10:56,100 --> 00:10:59,900 Você defini-lo igual a NULL apenas para fazer Certifique-se de que todas as bases estão cobertas 212 00:10:59,900 --> 00:11:04,070 antes de fazer qualquer mudança de modo que você está sempre garantido que ele vai 213 00:11:04,070 --> 00:11:08,880 estar apontando para um valor específico contra como um valor de lixo. 214 00:11:08,880 --> 00:11:12,210 Porque, sim, nós atribuímos novo ao lado automaticamente, 215 00:11:12,210 --> 00:11:15,420 mas é mais como um boas práticas para inicializar 216 00:11:15,420 --> 00:11:19,270 dessa forma e depois transferir. 217 00:11:19,270 --> 00:11:23,420 >> OK, então duplamente ligada listas agora. 218 00:11:23,420 --> 00:11:24,601 O que nós pensamos? 219 00:11:24,601 --> 00:11:26,350 O que há de diferente com duplamente ligada listas? 220 00:11:26,350 --> 00:11:30,750 221 00:11:30,750 --> 00:11:34,300 >> Assim, em nossas listas ligadas, podemos apenas mover em uma direção, certo? 222 00:11:34,300 --> 00:11:35,270 Nós só temos a seguir. 223 00:11:35,270 --> 00:11:36,760 Nós só podemos ir para a frente. 224 00:11:36,760 --> 00:11:40,300 >> Com uma lista duplamente ligada, também podemos andar para trás. 225 00:11:40,300 --> 00:11:44,810 Portanto, temos não só a número que deseja armazenar, 226 00:11:44,810 --> 00:11:50,110 temos onde ele aponta para o próximo e onde veio. 227 00:11:50,110 --> 00:11:52,865 Então, isso permite alguns melhores travessia. 228 00:11:52,865 --> 00:11:56,620 229 00:11:56,620 --> 00:12:01,240 >> Então nós duplamente vinculadas, muito semelhante, certo? 230 00:12:01,240 --> 00:12:05,000 A única diferença é que agora têm um lado e uma anterior. 231 00:12:05,000 --> 00:12:06,235 É a única diferença. 232 00:12:06,235 --> 00:12:09,570 233 00:12:09,570 --> 00:12:14,790 >> Então, se fôssemos para preceder ou append-- nós não têm qualquer código para esta aqui--se 234 00:12:14,790 --> 00:12:17,830 mas se você fosse para tentar inseri-lo, o importante 235 00:12:17,830 --> 00:12:19,980 é que você precisa fazer Certifique-se que você está atribuindo 236 00:12:19,980 --> 00:12:23,360 tanto o anterior e seu próximo ponteiro corretamente. 237 00:12:23,360 --> 00:12:29,010 Portanto, neste caso, você faria não só inicializar seguinte, 238 00:12:29,010 --> 00:12:31,820 você inicializa anterior. 239 00:12:31,820 --> 00:12:36,960 Se estamos no topo da lista, nós não só fazer a cabeça igual novo, 240 00:12:36,960 --> 00:12:41,750 mas deve ser a nossa nova anterior apontar para a cabeça, certo? 241 00:12:41,750 --> 00:12:43,380 >> Essa é a única diferença. 242 00:12:43,380 --> 00:12:47,200 E se você quiser mais prática com estes com listas ligadas, com a inserção, 243 00:12:47,200 --> 00:12:49,900 com a exclusão, com a inserção em uma lista variada, 244 00:12:49,900 --> 00:12:52,670 confira study.cs50.net. 245 00:12:52,670 --> 00:12:54,870 Há um monte de grandes exercícios. 246 00:12:54,870 --> 00:12:55,870 Eu recomendo-los. 247 00:12:55,870 --> 00:12:59,210 Eu gostaria que tivéssemos tempo para passar por eles mas há um monte de estruturas de dados 248 00:12:59,210 --> 00:13:01,530 para passar. 249 00:13:01,530 --> 00:13:02,650 >> OK, então tabelas de hash. 250 00:13:02,650 --> 00:13:07,070 Este é provavelmente o mais pouco útil para o seu pset 251 00:13:07,070 --> 00:13:11,090 aqui, porque você vai ser implementação de um destes, ou uma tentativa. 252 00:13:11,090 --> 00:13:12,200 Eu realmente gosto de tabelas de hash. 253 00:13:12,200 --> 00:13:13,110 Eles são muito legal. 254 00:13:13,110 --> 00:13:17,080 >> Então, basicamente, o que acontece é uma tabela hash 255 00:13:17,080 --> 00:13:22,050 é quando nós realmente precisamos speedy inserção, exclusão e pesquisa. 256 00:13:22,050 --> 00:13:25,010 Essas são as coisas que estamos priorizar em uma tabela hash. 257 00:13:25,010 --> 00:13:29,500 Eles podem ficar muito grande, mas, como veremos, com tentativas, 258 00:13:29,500 --> 00:13:33,040 há coisas que são muito maiores. 259 00:13:33,040 --> 00:13:38,330 >> Mas, basicamente, todo um hash tabela é uma função hash 260 00:13:38,330 --> 00:13:47,215 que lhe diz que balde para colocar cada de seus dados, cada um de seus elementos em. 261 00:13:47,215 --> 00:13:51,140 Uma maneira simples de pensar em uma tabela hash é que não é apenas baldes de coisas, 262 00:13:51,140 --> 00:13:51,770 certo? 263 00:13:51,770 --> 00:13:59,720 Então, quando você está classificando as coisas por como a primeira letra do seu nome, 264 00:13:59,720 --> 00:14:01,820 que é como uma espécie de tabela de hash. 265 00:14:01,820 --> 00:14:06,180 >> Então, se eu fosse vocês grupo é em grupos de quem quer que seu nome começa 266 00:14:06,180 --> 00:14:11,670 com um aqui, ou quem quer que o aniversário é em janeiro, fevereiro, março, 267 00:14:11,670 --> 00:14:15,220 seja qual for, que é eficaz criação de uma tabela hash. 268 00:14:15,220 --> 00:14:18,120 É só criar baldes que você classificar os elementos em 269 00:14:18,120 --> 00:14:19,520 para que você possa encontrá-los mais fácil. 270 00:14:19,520 --> 00:14:22,300 Assim, desta forma, quando eu preciso para encontrar um de vocês, 271 00:14:22,300 --> 00:14:24,680 Eu não tenho que procurar através de cada um de seus nomes. 272 00:14:24,680 --> 00:14:29,490 Eu posso ser como, oh, eu sei que Aniversário de Danielle é em-- 273 00:14:29,490 --> 00:14:30,240 AUDIÊNCIA: --April. 274 00:14:30,240 --> 00:14:30,948 COLUNA 1: abril. 275 00:14:30,948 --> 00:14:33,120 Então eu olho na minha abril balde, e com alguma sorte, 276 00:14:33,120 --> 00:14:38,270 ela vai ser a única pessoa lá dentro, e meu tempo era constante nesse sentido, 277 00:14:38,270 --> 00:14:41,230 enquanto que, se eu tenho que olhar através de um grupo inteiro de pessoas, 278 00:14:41,230 --> 00:14:43,090 que vai levar muito mais tempo. 279 00:14:43,090 --> 00:14:45,830 Então, tabelas hash são realmente apenas baldes. 280 00:14:45,830 --> 00:14:48,630 Uma maneira fácil de pensar deles. 281 00:14:48,630 --> 00:14:52,930 >> Então, uma coisa muito importante sobre uma tabela hash é uma função hash. 282 00:14:52,930 --> 00:14:58,140 Então, as coisas que eu acabei de falar sobre, como sua primeira letra de seu nome 283 00:14:58,140 --> 00:15:01,450 ou o seu mês de aniversário, estas são idéias que 284 00:15:01,450 --> 00:15:03,070 realmente se correlacionam com uma função hash. 285 00:15:03,070 --> 00:15:08,900 É apenas uma maneira de decidir qual balde você está elemento entra, OK? 286 00:15:08,900 --> 00:15:14,850 Portanto, para este pset, você pode olhar para cima praticamente qualquer função hash que deseja. 287 00:15:14,850 --> 00:15:16,030 >> Não tem que ser o seu próprio. 288 00:15:16,030 --> 00:15:21,140 Há alguns realmente fresco para fora há que fazer todos os tipos de matemática maluca. 289 00:15:21,140 --> 00:15:25,170 E se você quiser fazer o seu corretor ortográfico super rápido, 290 00:15:25,170 --> 00:15:27,620 Eu definitivamente olhar para um desses. 291 00:15:27,620 --> 00:15:32,390 >> Mas há também o são mais simples, como a computação 292 00:15:32,390 --> 00:15:39,010 a soma das palavras, como cada letra tem um número. 293 00:15:39,010 --> 00:15:39,940 Calcular a soma. 294 00:15:39,940 --> 00:15:42,230 Que determina o balde. 295 00:15:42,230 --> 00:15:45,430 Eles também têm as mais fáceis que são apenas como toda a de um aqui, 296 00:15:45,430 --> 00:15:47,050 todo o B está aqui. 297 00:15:47,050 --> 00:15:48,920 Qualquer um desses. 298 00:15:48,920 --> 00:15:55,770 >> Basicamente, ele apenas diz-lhe que índice da matriz seu elemento deve ir para. 299 00:15:55,770 --> 00:15:58,690 Basta decidir o bucket-- é tudo uma função hash é. 300 00:15:58,690 --> 00:16:04,180 Portanto, temos aqui um exemplo que é apenas a primeira letra da string 301 00:16:04,180 --> 00:16:05,900 que eu estava falando. 302 00:16:05,900 --> 00:16:11,900 >> Então você tem algum hash que é apenas o primeira letra da frase, menos um, 303 00:16:11,900 --> 00:16:16,090 que lhe dará alguns número entre 0 e 25. 304 00:16:16,090 --> 00:16:20,790 E o que você quer fazer é certifique-se de que isso representa 305 00:16:20,790 --> 00:16:24,110 o tamanho de seu hash de mesa-- quantos baldes existem. 306 00:16:24,110 --> 00:16:25,860 Com muitos destes funções de hash, eles são 307 00:16:25,860 --> 00:16:31,630 vai ser o retorno de valores que pode estar muito acima do número de depósitos 308 00:16:31,630 --> 00:16:33,610 que você realmente tem em sua tabela de hash, 309 00:16:33,610 --> 00:16:37,240 então você precisa fazer Certifique-se e mod por aqueles. 310 00:16:37,240 --> 00:16:42,190 Caso contrário, ele vai dizer, oh, ele deve estar em balde 5000 311 00:16:42,190 --> 00:16:46,040 mas você só tem 30 baldes em sua tabela hash. 312 00:16:46,040 --> 00:16:49,360 E, claro, todos nós sabemos que é vai resultar em alguns erros de loucos. 313 00:16:49,360 --> 00:16:52,870 Então certifique-se de mod pelo tamanho da tabela hash. 314 00:16:52,870 --> 00:16:58,430 315 00:16:58,430 --> 00:16:58,930 Legal. 316 00:16:58,930 --> 00:17:00,506 Assim colisões. 317 00:17:00,506 --> 00:17:02,620 Estão todos bem até agora? 318 00:17:02,620 --> 00:17:03,120 Mmhmm? 319 00:17:03,120 --> 00:17:05,900 >> AUDIÊNCIA: Por que ele retornar um valor tão grande? 320 00:17:05,900 --> 00:17:09,210 >> COLUNA 1: Dependendo do algoritmo que a sua função de hash usa. 321 00:17:09,210 --> 00:17:12,270 Alguns deles irão fazer multiplicação louco. 322 00:17:12,270 --> 00:17:16,270 E é tudo sobre a obtenção de uma distribuição uniforme, 323 00:17:16,270 --> 00:17:18,490 para que eles realmente fazer alguma coisas malucas às vezes. 324 00:17:18,490 --> 00:17:20,960 Isso é tudo. 325 00:17:20,960 --> 00:17:22,140 Algo mais? 326 00:17:22,140 --> 00:17:22,829 Está bem. 327 00:17:22,829 --> 00:17:24,480 >> Assim colisões. 328 00:17:24,480 --> 00:17:29,270 Basicamente, como eu disse anteriormente, na melhor das hipóteses, 329 00:17:29,270 --> 00:17:32,040 qualquer balde eu olhar é vai ter uma coisa, 330 00:17:32,040 --> 00:17:34,160 então eu não tenho que olhar para tudo, certo? 331 00:17:34,160 --> 00:17:37,040 Eu nem sei que ele está lá ou é Não, e isso é o que realmente queremos. 332 00:17:37,040 --> 00:17:43,960 Mas se temos dezenas de milhares de Os pontos de dados e inferior a esse número 333 00:17:43,960 --> 00:17:48,700 de baldes, nós vamos ter colisões onde eventualmente algo 334 00:17:48,700 --> 00:17:54,210 vai ter que acabar em um balde que já tem um elemento. 335 00:17:54,210 --> 00:17:57,390 >> Então a questão é, o que que vamos fazer nesse caso? 336 00:17:57,390 --> 00:17:58,480 O que vamos fazer? 337 00:17:58,480 --> 00:17:59,300 Já temos alguma coisa lá? 338 00:17:59,300 --> 00:18:00,060 Será que simplesmente jogá-lo fora? 339 00:18:00,060 --> 00:18:00,700 >> Não. 340 00:18:00,700 --> 00:18:01,980 Temos que manter os dois. 341 00:18:01,980 --> 00:18:06,400 Assim, a maneira que nós normalmente fazer isso é o quê? 342 00:18:06,400 --> 00:18:08,400 Qual é a estrutura de dados que acabamos de falar? 343 00:18:08,400 --> 00:18:09,316 AUDIÊNCIA: lista encadeada. 344 00:18:09,316 --> 00:18:10,500 COLUNA 1: Uma lista ligada. 345 00:18:10,500 --> 00:18:16,640 Então, agora, em vez de cada um destes baldes ter apenas um elemento, 346 00:18:16,640 --> 00:18:24,020 que vai conter uma lista ligada de os elementos que foram hash dentro dele. 347 00:18:24,020 --> 00:18:27,588 OK, que todos tipo de tirou essa idéia? 348 00:18:27,588 --> 00:18:30,546 Porque nós não poderíamos ter um array porque não sabemos quantas coisas 349 00:18:30,546 --> 00:18:31,730 vão estar lá. 350 00:18:31,730 --> 00:18:36,540 Uma lista ligada nos permite ter apenas o número exato que 351 00:18:36,540 --> 00:18:38,465 são misturados em que balde, né? 352 00:18:38,465 --> 00:18:42,260 353 00:18:42,260 --> 00:18:50,500 >> Então linear de sondagem é basicamente este idea-- 354 00:18:50,500 --> 00:18:52,300 é uma maneira de lidar com a colisão. 355 00:18:52,300 --> 00:18:58,010 O que você pode fazer é se, neste caso, baga foi hash em um 356 00:18:58,010 --> 00:19:01,130 e já temos algo lá, você só 357 00:19:01,130 --> 00:19:04,840 continue indo para baixo até você encontrar um slot vazio. 358 00:19:04,840 --> 00:19:06,370 Essa é uma maneira de lidar com isso. 359 00:19:06,370 --> 00:19:09,020 A outra maneira de lidar é com o que acabamos de 360 00:19:09,020 --> 00:19:12,280 called-- o ligado lista é chamado encadeamento. 361 00:19:12,280 --> 00:19:20,510 >> Então, essa idéia funciona se sua tabela hash que você pensa 362 00:19:20,510 --> 00:19:24,150 é muito maior do que seu conjunto de dados ou se você 363 00:19:24,150 --> 00:19:28,870 quero tentar minimizar o encadeamento até que seja absolutamente necessário. 364 00:19:28,870 --> 00:19:34,050 Então, uma coisa é linear sondagem, obviamente, significa 365 00:19:34,050 --> 00:19:37,290 que a sua função de hash não é tão útil 366 00:19:37,290 --> 00:19:42,200 porque você vai acabar usando sua função de hash, ficando a um ponto, 367 00:19:42,200 --> 00:19:46,400 você linear sondar até algum lugar que está disponível. 368 00:19:46,400 --> 00:19:49,670 Mas agora, naturalmente, nada outra coisa que acaba por lá, 369 00:19:49,670 --> 00:19:52,050 você vai ter que pesquisar ainda mais para baixo. 370 00:19:52,050 --> 00:19:55,650 >> E há muito mais despesa de busca que 371 00:19:55,650 --> 00:19:59,820 vai para a introdução de um elemento em sua tabela hash agora, certo? 372 00:19:59,820 --> 00:20:05,640 E agora quando você vai tentar encontrar baga de novo, você vai botar ele, 373 00:20:05,640 --> 00:20:07,742 e ele vai dizer: oh, olha no balde 1, 374 00:20:07,742 --> 00:20:09,700 e não vai ser no balde 1, então você está 375 00:20:09,700 --> 00:20:11,970 vai ter que atravessar através do restante destes. 376 00:20:11,970 --> 00:20:17,720 Então, às vezes é útil, mas na maior parte dos casos, 377 00:20:17,720 --> 00:20:22,660 vamos dizer que encadeamento é o que você quer fazer. 378 00:20:22,660 --> 00:20:25,520 >> Então nós conversamos sobre isso antes. 379 00:20:25,520 --> 00:20:27,812 Eu tenho um pouco à frente de mim. 380 00:20:27,812 --> 00:20:33,560 Mas o encadeamento é, basicamente, que cada balde em sua tabela hash 381 00:20:33,560 --> 00:20:36,120 é apenas uma lista ligada. 382 00:20:36,120 --> 00:20:39,660 >> Assim, uma outra forma, ou mais técnico forma, pensar em uma tabela hash 383 00:20:39,660 --> 00:20:44,490 é que não é apenas uma matriz de listas ligadas, que 384 00:20:44,490 --> 00:20:49,330 quando você está escrevendo seu dicionário e você está tentando carregá-lo, 385 00:20:49,330 --> 00:20:52,070 pensando nisso como uma matriz de listas ligadas 386 00:20:52,070 --> 00:20:54,390 fará com que seja muito mais fácil para que você possa inicializar. 387 00:20:54,390 --> 00:20:57,680 >> AUDIÊNCIA: Então tabela hash tem um tamanho pré-determinado, 388 00:20:57,680 --> 00:20:58,980 como um [inaudível] de baldes? 389 00:20:58,980 --> 00:20:59,220 >> COLUNA 1: Certo. 390 00:20:59,220 --> 00:21:01,655 Por isso, tem um número definido de baldes que você determine-- 391 00:21:01,655 --> 00:21:03,530 que vocês devem sinta-se livre para brincar. 392 00:21:03,530 --> 00:21:05,269 Pode ser muito legal para ver o que acontece 393 00:21:05,269 --> 00:21:06,810 como você mudar o seu número de caçambas. 394 00:21:06,810 --> 00:21:09,410 395 00:21:09,410 --> 00:21:11,510 Mas sim, ele tem um definir o número de baldes. 396 00:21:11,510 --> 00:21:15,360 O que lhe permite encaixar como muitos elementos que você precisa 397 00:21:15,360 --> 00:21:19,350 é este encadeamento separado onde você ligaram listas em cada balde. 398 00:21:19,350 --> 00:21:22,850 Isso significa que sua tabela hash será exatamente o tamanho 399 00:21:22,850 --> 00:21:25,440 que você precisa que ele seja, certo? 400 00:21:25,440 --> 00:21:27,358 Esse é o ponto de listas ligadas. 401 00:21:27,358 --> 00:21:30,850 402 00:21:30,850 --> 00:21:32,480 Legal. 403 00:21:32,480 --> 00:21:38,780 >> Por isso, todos OK lá? 404 00:21:38,780 --> 00:21:39,801 Tudo certo. 405 00:21:39,801 --> 00:21:40,300 Ah. 406 00:21:40,300 --> 00:21:41,860 O que aconteceu? 407 00:21:41,860 --> 00:21:42,960 Realmente agora. 408 00:21:42,960 --> 00:21:45,250 Acho que alguém está me matando. 409 00:21:45,250 --> 00:21:52,060 >> OK, vamos entrar em tentativas, que são um pouco louco. 410 00:21:52,060 --> 00:21:53,140 Eu gosto de tabelas de hash. 411 00:21:53,140 --> 00:21:54,460 Eu acho que eles são muito legal. 412 00:21:54,460 --> 00:21:56,710 Tries são legais também. 413 00:21:56,710 --> 00:21:59,590 >> Então, alguém se lembra o que é uma tentativa? 414 00:21:59,590 --> 00:22:01,740 Você deveria ter ido mais brevemente na palestra? 415 00:22:01,740 --> 00:22:04,570 416 00:22:04,570 --> 00:22:06,377 Você se lembra do tipo de como ele funciona? 417 00:22:06,377 --> 00:22:08,460 AUDIÊNCIA: Eu só estou balançando que se passar por isso. 418 00:22:08,460 --> 00:22:09,626 COLUNA 1: Nós não passar por isso. 419 00:22:09,626 --> 00:22:13,100 OK, nós realmente estamos indo para ir sobre ele agora é o que estamos dizendo. 420 00:22:13,100 --> 00:22:14,860 >> AUDIÊNCIA: Isso é para uma árvore de recuperação. 421 00:22:14,860 --> 00:22:15,280 >> COLUNA 1: Sim. 422 00:22:15,280 --> 00:22:16,196 É uma árvore de recuperação. 423 00:22:16,196 --> 00:22:16,960 Impressionante. 424 00:22:16,960 --> 00:22:23,610 Então, uma coisa a notar aqui é que nós está olhando para caracteres individuais 425 00:22:23,610 --> 00:22:24,480 aqui, certo? 426 00:22:24,480 --> 00:22:29,710 >> Portanto, antes com a nossa função de hash, que estavam olhando para as palavras como um todo, 427 00:22:29,710 --> 00:22:32,270 e agora estamos procurando mais para os personagens, certo? 428 00:22:32,270 --> 00:22:38,380 Portanto, temos Maxwell aqui e Mendel. 429 00:22:38,380 --> 00:22:47,840 Então, basicamente, um try-- uma maneira de pensar sobre isso é que todos os níveis aqui 430 00:22:47,840 --> 00:22:49,000 é uma matriz de letras. 431 00:22:49,000 --> 00:22:53,310 432 00:22:53,310 --> 00:22:55,790 Portanto, este é o nó raiz aqui, certo? 433 00:22:55,790 --> 00:23:01,980 Isso tem todos os personagens do alfabeto para o início de cada palavra. 434 00:23:01,980 --> 00:23:06,480 >> E o que você quer fazer é digamos, OK, nós temos alguma palavra M. 435 00:23:06,480 --> 00:23:10,590 Nós vamos olhar para Maxwell, de modo vamos para M. e M aponta para um inteiro 436 00:23:10,590 --> 00:23:14,800 uma outra matriz onde cada palavra, enquanto houver 437 00:23:14,800 --> 00:23:17,044 é uma palavra que tem um como a segunda carta, 438 00:23:17,044 --> 00:23:19,460 enquanto há uma palavra que tem B como a segunda carta, 439 00:23:19,460 --> 00:23:24,630 ele terá um ponteiro indo a alguma próxima matriz. 440 00:23:24,630 --> 00:23:29,290 >> Provavelmente não há uma palavra que MP alguma coisa, 441 00:23:29,290 --> 00:23:32,980 Assim, com a posição P no presente array, que seria apenas NULL. 442 00:23:32,980 --> 00:23:38,840 Ele diria: OK, não há nenhuma palavra que M seguido por um P, OK? 443 00:23:38,840 --> 00:23:43,100 Então, se nós pensamos sobre isso, cada uma dessas coisas menores 444 00:23:43,100 --> 00:23:47,990 é realmente um destes grandes conjuntos de A a Z. 445 00:23:47,990 --> 00:23:55,064 Então, o que pode ser uma das coisas que é uma espécie de desvantagem de uma tentativa? 446 00:23:55,064 --> 00:23:56,500 >> AUDIÊNCIA: Uma grande quantidade de memória. 447 00:23:56,500 --> 00:23:59,940 >> COLUNA 1: É uma tonelada de memória, certo? 448 00:23:59,940 --> 00:24:08,750 Cada um desses blocos aqui representa 26 espaços, 26 matriz elemento. 449 00:24:08,750 --> 00:24:13,680 Então tenta ficar incrivelmente pesada espaço. 450 00:24:13,680 --> 00:24:17,100 >> Mas eles são muito rápidos. 451 00:24:17,100 --> 00:24:22,540 Então, incrivelmente rápido, mas realmente espaço ineficiente. 452 00:24:22,540 --> 00:24:24,810 Meio que tem que descobrir qual deles você quer. 453 00:24:24,810 --> 00:24:29,470 Estes são muito legal para o seu pset, mas eles ocupam muita memória, 454 00:24:29,470 --> 00:24:30,290 para que o comércio off. 455 00:24:30,290 --> 00:24:31,480 Sim? 456 00:24:31,480 --> 00:24:34,300 >> AUDIÊNCIA: Seria possível para configurar uma tentativa e, em seguida, 457 00:24:34,300 --> 00:24:37,967 uma vez que você tem todo o dados em que você need-- 458 00:24:37,967 --> 00:24:39,550 Eu não sei se isso faria sentido. 459 00:24:39,550 --> 00:24:42,200 Eu estava me livrar de todo o Caracteres nulos, mas, em seguida, 460 00:24:42,200 --> 00:24:42,910 você não seria capaz de indexar eles-- 461 00:24:42,910 --> 00:24:43,275 >> COLUNA 1: Você ainda precisa deles. 462 00:24:43,275 --> 00:24:44,854 >> AUDIÊNCIA: - da mesma forma a cada vez. 463 00:24:44,854 --> 00:24:45,520 COLUNA 1: Sim. 464 00:24:45,520 --> 00:24:50,460 Você precisa dos caracteres nulos para deixar Você sabe se não há uma palavra lá. 465 00:24:50,460 --> 00:24:52,040 Ben se você tem algo que você quer? 466 00:24:52,040 --> 00:24:52,540 Está bem. 467 00:24:52,540 --> 00:24:54,581 Tudo bem, então vamos para ir um pouco mais 468 00:24:54,581 --> 00:24:58,920 no detalhe técnico atrás a tentar trabalhar com um exemplo. 469 00:24:58,920 --> 00:25:01,490 >> OK, então isso é a mesma coisa. 470 00:25:01,490 --> 00:25:06,290 Considerando que, em uma lista ligada, a nossa principal tipo de-- qual é a palavra que eu quero? - 471 00:25:06,290 --> 00:25:08,350 como a construção de bloco era um nó. 472 00:25:08,350 --> 00:25:12,280 Em uma tentativa, nós também temos um nó, mas é definido de forma diferente. 473 00:25:12,280 --> 00:25:17,000 >> Portanto, temos alguns que bool representa, na verdade, se uma palavra 474 00:25:17,000 --> 00:25:23,530 existe neste local, e em seguida, temos alguma variedade aqui-- ou melhor, 475 00:25:23,530 --> 00:25:27,840 este é um ponteiro para uma matriz de 27 caracteres. 476 00:25:27,840 --> 00:25:33,339 E isto é para, no presente caso, este 27-- Tenho certeza que todos vocês são como, espera, 477 00:25:33,339 --> 00:25:34,880 há 26 letras no alfabeto. 478 00:25:34,880 --> 00:25:36,010 Por que temos 27? 479 00:25:36,010 --> 00:25:37,870 >> Assim, dependendo do forma de implementar esta, 480 00:25:37,870 --> 00:25:43,240 isto é de um pset que permitiu apóstrofos. 481 00:25:43,240 --> 00:25:46,010 É por isso que o extra. 482 00:25:46,010 --> 00:25:50,500 Você também terá em algum casos o terminador nulo 483 00:25:50,500 --> 00:25:53,230 está incluída como um dos caracteres que é permitido ser, 484 00:25:53,230 --> 00:25:56,120 e é assim que eles verificam a ver se é o final da palavra. 485 00:25:56,120 --> 00:26:01,340 Se você estiver interessado, confira Vídeo de Kevin em study.cs50, 486 00:26:01,340 --> 00:26:04,790 bem como a Wikipedia tem alguns bons recursos lá. 487 00:26:04,790 --> 00:26:09,000 >> Mas vamos passar por apenas uma espécie de como você pode trabalhar através de uma tentativa 488 00:26:09,000 --> 00:26:11,010 se você está dado um. 489 00:26:11,010 --> 00:26:16,230 Portanto, temos um super simples aqui que Tem as palavras "bat" e "zoom" neles. 490 00:26:16,230 --> 00:26:18,920 E como podemos ver aqui em cima, este pequeno espaço aqui 491 00:26:18,920 --> 00:26:22,560 representa a nossa bool que diz, sim, esta é uma palavra. 492 00:26:22,560 --> 00:26:27,060 E então isso tem a nossa arrays de caracteres, certo? 493 00:26:27,060 --> 00:26:33,480 >> Então, nós estamos indo para percorrer encontrar "morcego" nessa tentativa. 494 00:26:33,480 --> 00:26:38,340 Então comece no topo, certo? 495 00:26:38,340 --> 00:26:46,290 E nós sabemos que b corresponde a o segundo índice, o segundo elemento 496 00:26:46,290 --> 00:26:47,840 Nesta matriz, porque a e b. 497 00:26:47,840 --> 00:26:51,340 Assim, cerca de um segundo. 498 00:26:51,340 --> 00:26:58,820 >> E diz, OK, legal, segue que em a próxima matriz, porque se nos lembrarmos, 499 00:26:58,820 --> 00:27:02,160 não é que cada um destes na verdade, contém o elemento. 500 00:27:02,160 --> 00:27:07,110 Cada uma destas matrizes contém um ponteiro, certo? 501 00:27:07,110 --> 00:27:10,030 É uma distinção importante a fazer. 502 00:27:10,030 --> 00:27:13,450 >> Eu sei que isso vai ser-- tentativas são realmente difícil de obter no primeiro tempo, 503 00:27:13,450 --> 00:27:15,241 por isso mesmo que este é o segunda ou terceira vez 504 00:27:15,241 --> 00:27:18,370 e ainda é o tipo de parecer difícil, 505 00:27:18,370 --> 00:27:21,199 Eu prometo que se você vai assistir o amanhã curto novamente, 506 00:27:21,199 --> 00:27:22,740 ele provavelmente vai fazer muito mais sentido. 507 00:27:22,740 --> 00:27:23,890 Demora muito para digerir. 508 00:27:23,890 --> 00:27:27,800 Eu às vezes ainda sou como, espere, o que é uma tentativa? 509 00:27:27,800 --> 00:27:29,080 Como eu uso isso? 510 00:27:29,080 --> 00:27:33,880 >> Então temos b neste caso, que é o nosso segundo índice. 511 00:27:33,880 --> 00:27:40,240 Se tivéssemos, por exemplo, c ou d ou qualquer outra carta, 512 00:27:40,240 --> 00:27:45,810 precisamos mapear que volta ao índice da nossa matriz que que corresponde a. 513 00:27:45,810 --> 00:27:56,930 Então, nós tomaríamos como rchar e nós apenas subtrair fora de um para mapeá-lo em 0-25. 514 00:27:56,930 --> 00:27:58,728 Todo mundo bom como nós mapear os nossos personagens? 515 00:27:58,728 --> 00:28:00,440 Está bem. 516 00:28:00,440 --> 00:28:05,980 >> Então vamos para o segundo e nós ver que, sim, ele não é NULL. 517 00:28:05,980 --> 00:28:07,780 Podemos passar para o próximo matriz. 518 00:28:07,780 --> 00:28:12,300 Então vamos para o próximo conjunto aqui. 519 00:28:12,300 --> 00:28:15,500 >> E nós dizemos: OK, agora nós precisa ver se um está aqui. 520 00:28:15,500 --> 00:28:18,590 É um nulo ou não é realmente seguir em frente? 521 00:28:18,590 --> 00:28:21,880 Assim, na verdade, um move encaminhar nesta matriz. 522 00:28:21,880 --> 00:28:24,570 E nós dizemos: OK, t é a nossa última carta. 523 00:28:24,570 --> 00:28:27,580 Então vamos para o t no índice. 524 00:28:27,580 --> 00:28:30,120 E, então, avançar porque não há outro. 525 00:28:30,120 --> 00:28:38,340 E isso se diz, basicamente, que, sim, ele diz que não é uma palavra aqui- 526 00:28:38,340 --> 00:28:41,750 que, se você seguir este caminho, você chegou 527 00:28:41,750 --> 00:28:43,210 em uma palavra, que sabemos que é "bat". 528 00:28:43,210 --> 00:28:43,800 Sim? 529 00:28:43,800 --> 00:28:46,770 >> AUDIÊNCIA: É normal ter que como índice 0 e, em seguida, ter uma espécie em 1 530 00:28:46,770 --> 00:28:47,660 ou para ter no final? 531 00:28:47,660 --> 00:28:48,243 >> COLUNA 1: Não. 532 00:28:48,243 --> 00:28:55,360 Portanto, se olharmos para o nosso declaração aqui, é um bool, 533 00:28:55,360 --> 00:28:59,490 por isso é seu próprio elemento em seu nó. 534 00:28:59,490 --> 00:29:03,331 Portanto, não é parte da matriz. 535 00:29:03,331 --> 00:29:03,830 Legal. 536 00:29:03,830 --> 00:29:08,370 Então, quando nós terminamos a nossa palavra e estamos nesta matriz, o que nós queremos fazer 537 00:29:08,370 --> 00:29:12,807 é fazer uma verificação para isso é uma palavra. 538 00:29:12,807 --> 00:29:14,390 E, neste caso, ele voltaria sim. 539 00:29:14,390 --> 00:29:17,220 540 00:29:17,220 --> 00:29:24,090 >> Então, nessa nota, sabemos que "zoo" - sabemos como os seres humanos que "zoo" é uma palavra, 541 00:29:24,090 --> 00:29:24,820 certo? 542 00:29:24,820 --> 00:29:28,990 Mas se tentar aqui seria dizer, não, não é. 543 00:29:28,990 --> 00:29:33,980 E diria que porque nós não designou-o como uma palavra aqui. 544 00:29:33,980 --> 00:29:40,440 Mesmo que podem atravessar através do presente matriz, 545 00:29:40,440 --> 00:29:43,890 esta tentativa diria que não, zoológico não está em seu dicionário 546 00:29:43,890 --> 00:29:47,070 porque não temos designado como tal. 547 00:29:47,070 --> 00:29:52,870 >> Assim, uma maneira de fazer isso-- Ah, desculpe, este. 548 00:29:52,870 --> 00:29:59,450 Portanto, neste caso, "zoo" não é uma palavra, mas é em nossa tentativa. 549 00:29:59,450 --> 00:30:05,690 Mas neste, dizer que quer que ele introduzir a palavra "banho", o que acontece 550 00:30:05,690 --> 00:30:08,260 é seguirmos through-- b, um t. 551 00:30:08,260 --> 00:30:11,820 Estamos nessa matriz, e vamos para procurar h. 552 00:30:11,820 --> 00:30:15,220 >> Neste caso, quando olhar para o ponteiro no h, 553 00:30:15,220 --> 00:30:17,890 ele está apontando para NULL, OK? 554 00:30:17,890 --> 00:30:20,780 Então, a menos que seja explicitamente apontando para uma outra matriz, 555 00:30:20,780 --> 00:30:25,000 você assumir que todos os ponteiros nesta matriz estão apontando para null. 556 00:30:25,000 --> 00:30:28,270 Portanto, neste caso, h está apontando como nulo por isso não podemos fazer nada, 557 00:30:28,270 --> 00:30:31,540 por isso seria também retornar falsa, "banho" não é aqui. 558 00:30:31,540 --> 00:30:34,102 559 00:30:34,102 --> 00:30:35,810 Portanto, agora estamos realmente vai passar por 560 00:30:35,810 --> 00:30:39,790 como é que nós realmente dizer que "zoo" é em nossa tentativa. 561 00:30:39,790 --> 00:30:42,920 Como é que vamos inserir "zoo" em nossa tentativa? 562 00:30:42,920 --> 00:30:47,810 Assim, da mesma maneira que começou com o nossa lista ligada, começamos na raiz. 563 00:30:47,810 --> 00:30:50,600 Quando estiver em dúvida, comece a raiz destas coisas. 564 00:30:50,600 --> 00:30:53,330 >> E vamos dizer, OK, z. 565 00:30:53,330 --> 00:30:55,650 z existe neste, e ele faz. 566 00:30:55,650 --> 00:30:58,370 Então você está se movendo para sua próxima matriz, OK? 567 00:30:58,370 --> 00:31:01,482 E então no próximo, podemos dizer, OK, se o existir? 568 00:31:01,482 --> 00:31:03,000 Ele faz. 569 00:31:03,000 --> 00:31:04,330 Este novo. 570 00:31:04,330 --> 00:31:08,670 >> E assim, em nosso próximo, temos dito, OK, "zoo" já existe aqui. 571 00:31:08,670 --> 00:31:12,440 Tudo o que precisamos fazer é definir este igual a verdade, que não é uma palavra lá. 572 00:31:12,440 --> 00:31:15,260 Se você tivesse seguido tudo até antes desse ponto, 573 00:31:15,260 --> 00:31:17,030 é uma palavra, por isso só configurá-lo igual a tal. 574 00:31:17,030 --> 00:31:17,530 Sim? 575 00:31:17,530 --> 00:31:22,550 >> AUDIÊNCIA: Então faz isso significa que "ba" é uma palavra também? 576 00:31:22,550 --> 00:31:24,120 >> COLUNA 1: Não. 577 00:31:24,120 --> 00:31:28,870 Portanto, neste caso, "ba" obteríamos aqui, diríamos que é uma palavra, 578 00:31:28,870 --> 00:31:31,590 e ele ainda seria não. 579 00:31:31,590 --> 00:31:32,822 Ok? 580 00:31:32,822 --> 00:31:33,740 Mmhmm? 581 00:31:33,740 --> 00:31:36,360 >> AUDIÊNCIA: Então, quando você é um palavra e você diz que sim, então ele 582 00:31:36,360 --> 00:31:38,380 conterá a ir para m? 583 00:31:38,380 --> 00:31:42,260 >> COLUNA 1: Então, isso tem a ver com-- você está carregando isso em. 584 00:31:42,260 --> 00:31:43,640 Você diz "zoo" é uma palavra. 585 00:31:43,640 --> 00:31:47,020 Quando você vai a check-- como, digamos que você quer dizer, 586 00:31:47,020 --> 00:31:49,400 significa "jardim zoológico" existe neste dicionário? 587 00:31:49,400 --> 00:31:54,200 Você só vai procurar "zoo" e, em seguida, verificar para ver se é uma palavra. 588 00:31:54,200 --> 00:31:57,291 Você nunca vai se mover através de m porque isso não é 589 00:31:57,291 --> 00:31:58,290 o que você está procurando. 590 00:31:58,290 --> 00:32:02,690 591 00:32:02,690 --> 00:32:08,070 >> Então, se nós realmente queria adicionar "banho" nesta tentativa, 592 00:32:08,070 --> 00:32:11,390 faríamos a mesma coisa como fizemos com "zoo" 593 00:32:11,390 --> 00:32:15,380 exceto veríamos que quando nós tentar chegar a hora, ele não existe. 594 00:32:15,380 --> 00:32:20,090 Então você pode pensar nisso como uma tentativa para adicionar um novo nó em uma lista ligada, 595 00:32:20,090 --> 00:32:27,210 de modo que seria necessário para adicionar outro uma dessas matrizes, assim. 596 00:32:27,210 --> 00:32:35,670 E então o que fazemos é apenas definir o h elemento dessa matriz apontando para isso. 597 00:32:35,670 --> 00:32:39,430 >> E então, o que gostaria de fazer aqui? 598 00:32:39,430 --> 00:32:43,110 Adicioná-lo igual a true porque é uma palavra. 599 00:32:43,110 --> 00:32:46,350 600 00:32:46,350 --> 00:32:48,150 Legal. 601 00:32:48,150 --> 00:32:48,700 Eu sei. 602 00:32:48,700 --> 00:32:51,170 Tenta não são o mais emocionante. 603 00:32:51,170 --> 00:32:54,250 Confie em mim, eu sei. 604 00:32:54,250 --> 00:32:58,040 >> Então, uma coisa a perceber com tentativas, Eu disse, eles são muito eficientes. 605 00:32:58,040 --> 00:33:00,080 Então, nós vimos eles levar até uma tonelada de espaço. 606 00:33:00,080 --> 00:33:01,370 Eles são o tipo de confundir. 607 00:33:01,370 --> 00:33:03,367 Então, por que nós nunca usá-los? 608 00:33:03,367 --> 00:33:05,450 Usamos estes porque eles são incrivelmente eficiente. 609 00:33:05,450 --> 00:33:08,130 >> Então, se você está sempre à procura uma palavra, só são 610 00:33:08,130 --> 00:33:10,450 delimitada pelo comprimento da palavra. 611 00:33:10,450 --> 00:33:15,210 Então, se você está procurando um palavra que tem um comprimento de cinco, 612 00:33:15,210 --> 00:33:20,940 você está sempre apenas vai ter que fazer, no máximo, cinco comparações, OK? 613 00:33:20,940 --> 00:33:25,780 Assim, torna-se, basicamente, uma constante. 614 00:33:25,780 --> 00:33:29,150 Como a inserção e pesquisa são basicamente constante de tempo. 615 00:33:29,150 --> 00:33:33,750 >> Então, se você pode nunca chegar algo em tempo constante, 616 00:33:33,750 --> 00:33:35,150 que é tão bom quanto ele ganha. 617 00:33:35,150 --> 00:33:37,990 Você não pode ficar melhor do que constante de tempo para essas coisas. 618 00:33:37,990 --> 00:33:43,150 Assim que é um dos enormes vantagens de tentativas. 619 00:33:43,150 --> 00:33:46,780 >> Mas é muito espaço. 620 00:33:46,780 --> 00:33:50,380 Então você meio que tem que decidir o que é mais importante para você. 621 00:33:50,380 --> 00:33:54,700 E em computadores de hoje, o espaço que uma tentativa pode levar até 622 00:33:54,700 --> 00:33:57,740 talvez não afecta que muito, mas talvez 623 00:33:57,740 --> 00:34:01,350 você está lidando com algo que tem muito, muito mais coisas, 624 00:34:01,350 --> 00:34:02,810 e uma tentativa só não é razoável. 625 00:34:02,810 --> 00:34:03,000 Sim? 626 00:34:03,000 --> 00:34:05,610 >> AUDIÊNCIA: Aguarde, então você tem 26 letras em cada um? 627 00:34:05,610 --> 00:34:07,440 >> COLUNA 1: Mmhmm. 628 00:34:07,440 --> 00:34:08,570 Sim, você tem 26. 629 00:34:08,570 --> 00:34:16,984 Você tem alguma é marcador de texto e, em seguida, você tem 26 indicadores em cada um. 630 00:34:16,984 --> 00:34:17,775 E eles estão ponto-- 631 00:34:17,775 --> 00:34:20,280 >> AUDIÊNCIA: E a cada 26 anos, que cada um deles tem 26? 632 00:34:20,280 --> 00:34:21,500 >> COLUNA 1: Sim. 633 00:34:21,500 --> 00:34:27,460 E é por isso que, como você pode ver, ele se expande rapidamente. 634 00:34:27,460 --> 00:34:28,130 Tudo certo. 635 00:34:28,130 --> 00:34:32,524 Então, nós estamos indo para entrar em árvores, o que Eu sinto que é mais fácil e, provavelmente, 636 00:34:32,524 --> 00:34:36,150 ser um pouco agradável indulto a partir de tentativas lá. 637 00:34:36,150 --> 00:34:39,620 Portanto, esperamos que a maioria de vocês vi uma árvore antes. 638 00:34:39,620 --> 00:34:41,820 Não como o bastante os de fora, que eu 639 00:34:41,820 --> 00:34:44,340 Não sei se alguém foi ao ar recentemente. 640 00:34:44,340 --> 00:34:49,230 Fui colheita da maçã neste fim de semana, e oh meu Deus, ele era lindo. 641 00:34:49,230 --> 00:34:52,250 Eu não sabia que as folhas poderia parecer que bonita. 642 00:34:52,250 --> 00:34:53,610 >> Portanto, esta é apenas uma árvore, certo? 643 00:34:53,610 --> 00:34:56,790 É só algum nó, e aponta para um monte de outros nós. 644 00:34:56,790 --> 00:34:59,570 Como você pode ver aqui, este é tipo de um tema recorrente. 645 00:34:59,570 --> 00:35:03,720 Nodes apontando para nós é uma espécie de a essência de muitas estruturas de dados. 646 00:35:03,720 --> 00:35:06,670 Depende apenas de como nós tê-los uns aos outros para apontar 647 00:35:06,670 --> 00:35:08,600 e como nós percorremos através deles e como nós 648 00:35:08,600 --> 00:35:14,500 inserir coisas que determina as suas diferentes características. 649 00:35:14,500 --> 00:35:17,600 >> Então, basta um pouco de terminologia, que eu usei antes. 650 00:35:17,600 --> 00:35:20,010 Então raiz é o que está no topo. 651 00:35:20,010 --> 00:35:21,200 É onde nós sempre começar. 652 00:35:21,200 --> 00:35:23,610 Você pode pensar nisso como a cabeça também. 653 00:35:23,610 --> 00:35:28,750 Mas, para as árvores, que tendem a se referem a ele como a raiz. 654 00:35:28,750 --> 00:35:32,820 >> Qualquer coisa no fundo aqui-- no muito, muito bottom-- 655 00:35:32,820 --> 00:35:34,500 folhas são consideradas. 656 00:35:34,500 --> 00:35:37,210 Por isso, vai junto com o coisa árvore inteira, certo? 657 00:35:37,210 --> 00:35:39,860 As folhas são nas bordas da sua árvore. 658 00:35:39,860 --> 00:35:45,820 >> E depois temos também um par de termos de falar sobre nós em relação 659 00:35:45,820 --> 00:35:46,680 uns com os outros. 660 00:35:46,680 --> 00:35:49,700 Portanto, temos pai, filhos e irmãos. 661 00:35:49,700 --> 00:35:56,260 Portanto, neste caso, é o 3 -mãe de 5, 6, e 7. 662 00:35:56,260 --> 00:36:00,370 Então, o pai é o que está um passo acima de tudo o que você está 663 00:36:00,370 --> 00:36:02,940 referindo-se, por isso só como uma árvore genealógica. 664 00:36:02,940 --> 00:36:07,090 Felizmente, isso é tudo um pouco pouco mais intuitivo do que as tentativas. 665 00:36:07,090 --> 00:36:10,970 >> Os irmãos são os que têm o mesmo pai, certo? 666 00:36:10,970 --> 00:36:13,470 Eles estão no mesmo nível aqui. 667 00:36:13,470 --> 00:36:16,960 E então, como eu estava dizendo que os filhos são apenas 668 00:36:16,960 --> 00:36:22,630 tudo o que é um degrau abaixo o nó em questão, OK? 669 00:36:22,630 --> 00:36:23,470 Legal. 670 00:36:23,470 --> 00:36:25,610 Assim, uma árvore binária. 671 00:36:25,610 --> 00:36:31,450 Alguém pode arriscar um palpite em um dos as características da árvore binária? 672 00:36:31,450 --> 00:36:32,770 >> AUDIÊNCIA: Max duas folhas. 673 00:36:32,770 --> 00:36:33,478 >> COLUNA 1: Certo. 674 00:36:33,478 --> 00:36:34,640 Assim máximo de duas folhas. 675 00:36:34,640 --> 00:36:39,730 Assim, em um presente antes, tivemos um presente que tinha três, mas de uma árvore binária, 676 00:36:39,730 --> 00:36:45,000 você tem um máximo de dois crianças por pais, certo? 677 00:36:45,000 --> 00:36:46,970 Há um outro característica interessante. 678 00:36:46,970 --> 00:36:51,550 Alguém sabe isso? 679 00:36:51,550 --> 00:36:52,620 Árvore binária. 680 00:36:52,620 --> 00:37:00,350 >> Assim, uma árvore binária terá tudo em as-- este não é sorted-- 681 00:37:00,350 --> 00:37:05,320 mas de uma árvore binária classificados, tudo à direita 682 00:37:05,320 --> 00:37:08,530 é maior do que a mãe, e tudo à esquerda 683 00:37:08,530 --> 00:37:10,035 é menor do que a mãe. 684 00:37:10,035 --> 00:37:15,690 E isso tem sido um quiz pergunta antes, então é bom saber. 685 00:37:15,690 --> 00:37:19,500 Então, a forma como definimos isso, novamente, temos um outro nó. 686 00:37:19,500 --> 00:37:21,880 Este é muito parecido com o que? 687 00:37:21,880 --> 00:37:28,336 688 00:37:28,336 --> 00:37:28,836 Duplamente 689 00:37:28,836 --> 00:37:29,320 >> Audiência: Linked listas 690 00:37:29,320 --> 00:37:31,100 >> COLUNA 1: Uma lista ligada dupla, certo? 691 00:37:31,100 --> 00:37:33,690 Então, se substituirmos este com anterior e seguinte, 692 00:37:33,690 --> 00:37:35,670 esta seria uma lista duplamente ligada. 693 00:37:35,670 --> 00:37:40,125 Mas, neste caso, nós realmente ter esquerda e direita e é isso. 694 00:37:40,125 --> 00:37:41,500 Caso contrário, é exatamente o mesmo. 695 00:37:41,500 --> 00:37:43,374 Ainda temos o elemento você está procurando, 696 00:37:43,374 --> 00:37:45,988 e você só tem dois ponteiros indo para o que vem a seguir. 697 00:37:45,988 --> 00:37:49,210 698 00:37:49,210 --> 00:37:51,870 Sim, então árvore binária de busca. 699 00:37:51,870 --> 00:37:57,665 Se notarmos, tudo no aqui é maior than-- 700 00:37:57,665 --> 00:37:59,850 ou tudo imediatamente para a direita aqui 701 00:37:59,850 --> 00:38:02,840 é maior do que, tudo aqui é inferior a. 702 00:38:02,840 --> 00:38:06,980 703 00:38:06,980 --> 00:38:14,000 >> Então, se fôssemos pesquisar, ele deve olhar muito próximo de busca binária 704 00:38:14,000 --> 00:38:14,910 aqui, certo? 705 00:38:14,910 --> 00:38:17,640 Exceto em vez de olhar na metade da matriz, 706 00:38:17,640 --> 00:38:21,720 estamos apenas olhando para a esquerda ou lado ou do lado direito da árvore. 707 00:38:21,720 --> 00:38:24,850 Então, ele fica um pouco mais simples, eu acho. 708 00:38:24,850 --> 00:38:29,300 >> Portanto, se sua raiz é NULL, obviamente, é simplesmente falso. 709 00:38:29,300 --> 00:38:33,470 E se ele está lá, obviamente, é verdade. 710 00:38:33,470 --> 00:38:35,320 Se for menor do que, buscamos a esquerda. 711 00:38:35,320 --> 00:38:37,070 Se for maior do que, buscamos a direita. 712 00:38:37,070 --> 00:38:39,890 É exatamente como busca binária, apenas uma estrutura de dados diferente 713 00:38:39,890 --> 00:38:40,600 que estamos usando. 714 00:38:40,600 --> 00:38:42,790 Em vez de uma matriz, é apenas uma árvore binária. 715 00:38:42,790 --> 00:38:45,820 716 00:38:45,820 --> 00:38:48,090 >> OK, pilhas. 717 00:38:48,090 --> 00:38:51,550 E também, parece que pode ter um pouco de tempo. 718 00:38:51,550 --> 00:38:54,460 Se fizermos isso, estou feliz de ir sobre nada disso de novo. 719 00:38:54,460 --> 00:38:56,856 OK, então empilha. 720 00:38:56,856 --> 00:39:02,695 Alguém se lembra o que stacks-- quaisquer características de uma pilha? 721 00:39:02,695 --> 00:39:05,550 722 00:39:05,550 --> 00:39:10,400 >> OK, assim que a maioria de nós, eu acho, comer no jantar halls-- 723 00:39:10,400 --> 00:39:13,100 tanto quanto nós pode não gostar de. 724 00:39:13,100 --> 00:39:16,900 Mas, obviamente, você pode pensar em uma pilha literalmente apenas como uma pilha de bandejas 725 00:39:16,900 --> 00:39:18,460 ou uma pilha de coisas. 726 00:39:18,460 --> 00:39:21,820 E o que é importante para perceber é que é 727 00:39:21,820 --> 00:39:26,850 something-- a característica que podemos chamá-lo por-- é LIFO. 728 00:39:26,850 --> 00:39:28,450 Alguém sabe o que isso significa? 729 00:39:28,450 --> 00:39:29,070 Mmhmm? 730 00:39:29,070 --> 00:39:30,650 >> AUDIÊNCIA: último a entrar, primeiro a sair. 731 00:39:30,650 --> 00:39:32,250 >> COLUNA 1: Direito, último a entrar, primeiro a sair. 732 00:39:32,250 --> 00:39:36,585 Então, se nós sabemos, se vamos empilhar as coisas se, a coisa mais fácil de agarrar off-- 733 00:39:36,585 --> 00:39:39,570 e talvez a única coisa que pode pegar off, se a nossa pilha é grande enough-- 734 00:39:39,570 --> 00:39:40,850 é aquele elemento superior. 735 00:39:40,850 --> 00:39:43,460 Então o que foi colocado em last-- como vemos aqui, 736 00:39:43,460 --> 00:39:46,370 tudo o que foi empurrado na maioria recently-- é 737 00:39:46,370 --> 00:39:51,160 vai ser o primeiro coisa que nós pop off, OK? 738 00:39:51,160 --> 00:39:56,324 >> Então o que temos aqui é outra struct typedef. 739 00:39:56,324 --> 00:39:58,740 Isto é realmente apenas como um Bater Curso de estrutura de dados, 740 00:39:58,740 --> 00:40:01,650 por isso há muito jogado em vocês. 741 00:40:01,650 --> 00:40:02,540 Eu sei. 742 00:40:02,540 --> 00:40:04,970 Então, mais uma struct. 743 00:40:04,970 --> 00:40:06,740 Yay para estruturas. 744 00:40:06,740 --> 00:40:16,660 >> E, neste caso, é um ponteiro para uma matriz que tem alguma capacidade. 745 00:40:16,660 --> 00:40:20,830 Então, isso representa a nossa pilha aqui, como nossa matriz real 746 00:40:20,830 --> 00:40:22,520 que está segurando os nossos elementos. 747 00:40:22,520 --> 00:40:24,850 E então aqui temos alguns tamanho. 748 00:40:24,850 --> 00:40:31,170 >> E geralmente, você quer manter pista de quão grande é a tua stack 749 00:40:31,170 --> 00:40:36,180 porque o que vai permitir você precisa fazer é se você sabe o tamanho, 750 00:40:36,180 --> 00:40:39,170 ele permite que você diz, OK, eu sou a capacidade? 751 00:40:39,170 --> 00:40:40,570 Posso adicionar mais alguma coisa? 752 00:40:40,570 --> 00:40:44,650 E também lhe diz onde a parte superior do seu stack 753 00:40:44,650 --> 00:40:48,180 É assim que você sabe o que você pode realmente decolar. 754 00:40:48,180 --> 00:40:51,760 E isso realmente vai ser um pouco mais claro. 755 00:40:51,760 --> 00:40:57,350 >> Assim, por impulso, uma coisa, se você nunca foram para implementar impulso, 756 00:40:57,350 --> 00:41:01,330 como eu estava dizendo, o seu pilha tem um tamanho limitado, certo? 757 00:41:01,330 --> 00:41:03,990 Nossa matriz tinha alguma capacidade. 758 00:41:03,990 --> 00:41:04,910 É uma matriz. 759 00:41:04,910 --> 00:41:08,930 É um tamanho fixo, por isso precisamos certifique-se de que não estamos colocando mais 760 00:41:08,930 --> 00:41:11,950 em nossa matriz do que nós realmente tem espaço para. 761 00:41:11,950 --> 00:41:16,900 >> Então, quando você está criando um impulso função, a primeira coisa que você faz é dizer, OK, 762 00:41:16,900 --> 00:41:18,570 eu tenho espaço na minha pilha? 763 00:41:18,570 --> 00:41:23,330 Porque se eu não fizer isso, desculpe, Eu não posso guardar o seu elemento. 764 00:41:23,330 --> 00:41:28,980 Se eu fizer isso, então você deseja armazenar -lo no topo da pilha, à direita? 765 00:41:28,980 --> 00:41:31,325 >> E é por isso que temos manter o controle do nosso tamanho. 766 00:41:31,325 --> 00:41:35,290 Se não manter o controle de nosso tamanho, não sabemos onde colocá-lo. 767 00:41:35,290 --> 00:41:39,035 Nós não sabemos quantas coisas estão em nossa matriz já. 768 00:41:39,035 --> 00:41:41,410 Como, obviamente, existem maneiras que talvez você poderia fazê-lo. 769 00:41:41,410 --> 00:41:44,610 Você pode inicializar tudo para NULL e, em seguida, verifique o mais recente NULL, 770 00:41:44,610 --> 00:41:47,950 mas uma coisa muito mais fácil é apenas quer dizer, OK, manter o controle de tamanho. 771 00:41:47,950 --> 00:41:51,840 Como eu sei que eu tenho quatro elementos na minha matriz, então a próxima coisa 772 00:41:51,840 --> 00:41:55,930 que colocar, nós somos indo para armazenar no índice 4. 773 00:41:55,930 --> 00:42:00,940 E então, é claro, isto significa que você empurrou algo com sucesso 774 00:42:00,940 --> 00:42:03,320 em seu stack, você quer aumentar o tamanho 775 00:42:03,320 --> 00:42:08,880 para que você saiba onde você está para que você pode empurrar mais coisas sobre. 776 00:42:08,880 --> 00:42:12,730 >> Então, se estamos tentando pop algo fora da pilha, 777 00:42:12,730 --> 00:42:16,072 o que poderia ser a primeira coisa que deseja verificar? 778 00:42:16,072 --> 00:42:18,030 Você está tentando tomar algo fora de sua pilha. 779 00:42:18,030 --> 00:42:21,710 780 00:42:21,710 --> 00:42:24,781 Tem certeza de que há algo em sua pilha? 781 00:42:24,781 --> 00:42:25,280 Não. 782 00:42:25,280 --> 00:42:26,894 Então, o que podemos querer verificar? 783 00:42:26,894 --> 00:42:27,810 >> AUDIÊNCIA: [inaudível]. 784 00:42:27,810 --> 00:42:29,880 COLUNA 1: Verifique o tamanho? 785 00:42:29,880 --> 00:42:31,840 Tamanho. 786 00:42:31,840 --> 00:42:38,520 Por isso, queremos verificar se nosso tamanho é maior que 0, OK? 787 00:42:38,520 --> 00:42:44,970 E se é, então nós queremos diminuir nosso tamanho por 0 e retornar isso. 788 00:42:44,970 --> 00:42:45,840 Por quê? 789 00:42:45,840 --> 00:42:49,950 >> No primeiro fomos empurrando, nós empurrou 790 00:42:49,950 --> 00:42:52,460 sobre o tamanho eo tamanho atualizado. 791 00:42:52,460 --> 00:42:57,850 Neste caso, estamos diminuindo o tamanho e depois tirá-lo, arrancando-o 792 00:42:57,850 --> 00:42:58,952 da nossa matriz. 793 00:42:58,952 --> 00:42:59,826 Por que fazemos isso? 794 00:42:59,826 --> 00:43:04,800 795 00:43:04,800 --> 00:43:11,811 Então, se eu tenho uma coisa na minha pilha, qual seria o meu tamanho em que ponto? 796 00:43:11,811 --> 00:43:13,140 1. 797 00:43:13,140 --> 00:43:15,180 >> E onde está armazenado o elemento 1? 798 00:43:15,180 --> 00:43:17,621 Em que índice? 799 00:43:17,621 --> 00:43:18,120 AUDIÊNCIA: 0. 800 00:43:18,120 --> 00:43:19,060 COLUNA 1: 0. 801 00:43:19,060 --> 00:43:22,800 Portanto, neste caso, nós sempre precisa fazer sure-- 802 00:43:22,800 --> 00:43:27,630 em vez de retornar tamanho menos 1, porque nós 803 00:43:27,630 --> 00:43:31,730 saber que o nosso elemento é vai ser armazenado a uma menor 804 00:43:31,730 --> 00:43:34,705 seja qual for o nosso tamanho é, este só cuida dele. 805 00:43:34,705 --> 00:43:36,080 É uma maneira um pouco mais elegante. 806 00:43:36,080 --> 00:43:41,220 E nós só diminuir nossa tamanho e, em seguida, retornar tamanho. 807 00:43:41,220 --> 00:43:42,330 Mmhmm? 808 00:43:42,330 --> 00:43:45,300 >> AUDIÊNCIA: Eu acho que só em geral, por que essa estrutura de dados 809 00:43:45,300 --> 00:43:47,800 ser benéfico? 810 00:43:47,800 --> 00:43:50,660 >> COLUNA 1: Depende do seu contexto. 811 00:43:50,660 --> 00:43:57,420 Assim, para algumas das teorias, se você está trabalhando com-- OK, 812 00:43:57,420 --> 00:44:02,750 deixe-me ver se há um benéfico que é benéfico para mais de fora 813 00:44:02,750 --> 00:44:05,420 de CS. 814 00:44:05,420 --> 00:44:15,780 Com pilhas, a qualquer hora que você precisa manter o controle de algo que 815 00:44:15,780 --> 00:44:20,456 é o adicionado mais recentemente é quando você vai querer usar uma pilha. 816 00:44:20,456 --> 00:44:24,770 >> E eu não posso pensar em uma boa exemplo do que agora. 817 00:44:24,770 --> 00:44:29,955 Mas sempre que a mais recente coisa é mais importante para você, 818 00:44:29,955 --> 00:44:31,705 que é quando uma pilha vai ser útil. 819 00:44:31,705 --> 00:44:35,797 820 00:44:35,797 --> 00:44:39,330 Eu estou tentando pensar se há uma boa para isso. 821 00:44:39,330 --> 00:44:43,720 Se eu pensar em um bom exemplo na próxima 20 minutos, com certeza vou te dizer. 822 00:44:43,720 --> 00:44:49,455 >> Mas no geral, se há alguma coisa, como eu disse a maioria, onde mais recente 823 00:44:49,455 --> 00:44:52,470 é o mais importante, que é onde uma pilha entra em jogo. 824 00:44:52,470 --> 00:44:58,860 Considerando as filas são uma espécie de oposto. 825 00:44:58,860 --> 00:44:59,870 E todos os cães pequenos. 826 00:44:59,870 --> 00:45:00,890 Não é esta a grande, certo? 827 00:45:00,890 --> 00:45:03,299 Eu sinto que eu deveria só tem um vídeo coelho 828 00:45:03,299 --> 00:45:05,090 à direita no meio de seção para vocês 829 00:45:05,090 --> 00:45:08,870 porque este é um corte intenso. 830 00:45:08,870 --> 00:45:10,480 >> Então uma fila. 831 00:45:10,480 --> 00:45:12,710 Basicamente, uma fila é como uma linha. 832 00:45:12,710 --> 00:45:15,780 Vocês Tenho certeza de que uso isso todos os dias, assim como em nossas salas de jantar. 833 00:45:15,780 --> 00:45:18,160 Então, nós temos que ir em e chegar em nossas bandejas, eu sou 834 00:45:18,160 --> 00:45:21,260 se você tem que esperar na fila para roubar ou obter seu alimento. 835 00:45:21,260 --> 00:45:24,650 >> Assim, a diferença aqui é que este é o FIFO. 836 00:45:24,650 --> 00:45:30,090 Então, se LIFO foi o último a entrar, primeiro fora, FIFO é o primeiro a entrar, primeiro fora. 837 00:45:30,090 --> 00:45:33,400 Portanto, este é o lugar onde tudo o que você colocar em primeiro lugar é a sua mais importante. 838 00:45:33,400 --> 00:45:35,540 Então, se você estava esperando em um linha-- pode você 839 00:45:35,540 --> 00:45:39,130 imagine se você fosse a ir buscar o novo iPhone 840 00:45:39,130 --> 00:45:42,800 e era uma pilha em que a última pessoa da fila chegou primeiro, 841 00:45:42,800 --> 00:45:44,160 as pessoas iriam matar um ao outro. 842 00:45:44,160 --> 00:45:49,800 >> Então FIFO, estamos todos muito familiarizados com no mundo real aqui, 843 00:45:49,800 --> 00:45:54,930 e tudo isso tem a ver com a verdade tipo de recriar esta linha inteira 844 00:45:54,930 --> 00:45:56,900 e filas estrutura. 845 00:45:56,900 --> 00:46:02,390 Assim, enquanto que com a pilha, temos push e pop. 846 00:46:02,390 --> 00:46:06,440 Com uma fila, temos enfileiramento e retirar da fila. 847 00:46:06,440 --> 00:46:10,910 Então enfileiramento significa, basicamente, colocá-lo na parte de trás, 848 00:46:10,910 --> 00:46:13,680 e meios dequeue tomar fora a partir da frente. 849 00:46:13,680 --> 00:46:18,680 Portanto, a nossa estrutura de dados é um pouco mais complicado. 850 00:46:18,680 --> 00:46:21,060 Temos uma segunda coisa a acompanhar. 851 00:46:21,060 --> 00:46:25,950 >> Assim, sem a cabeça, esta é exatamente uma pilha, certo? 852 00:46:25,950 --> 00:46:27,900 Esta é a mesma estrutura que uma pilha. 853 00:46:27,900 --> 00:46:32,480 A única coisa diferente agora é que tem essa cabeça, que o que você pensa 854 00:46:32,480 --> 00:46:34,272 vai acompanhar? 855 00:46:34,272 --> 00:46:35,510 >> AUDIÊNCIA: O primeiro. 856 00:46:35,510 --> 00:46:38,685 >> COLUNA 1: Direito, o primeira coisa que colocamos no. 857 00:46:38,685 --> 00:46:41,130 O chefe da nossa fila. 858 00:46:41,130 --> 00:46:42,240 Quem é o primeiro da fila. 859 00:46:42,240 --> 00:46:45,300 860 00:46:45,300 --> 00:46:49,420 Tudo bem, então se fizermos enfileiramento. 861 00:46:49,420 --> 00:46:52,720 862 00:46:52,720 --> 00:46:55,920 Mais uma vez, com qualquer de estas estruturas de dados, 863 00:46:55,920 --> 00:46:59,760 uma vez que estamos lidando com um array, precisamos verificar se temos espaço. 864 00:46:59,760 --> 00:47:03,290 >> Este é tipo de como me dizendo vocês, se você abrir um arquivo, 865 00:47:03,290 --> 00:47:04,760 você precisa verificar para null. 866 00:47:04,760 --> 00:47:08,330 Com qualquer destas pilhas e as filas, você precisa 867 00:47:08,330 --> 00:47:13,420 para ver se há espaço porque estamos lidar com uma matriz de tamanho fixo, 868 00:47:13,420 --> 00:47:16,030 como vemos aqui-- 0, 1 tudo até 5. 869 00:47:16,030 --> 00:47:20,690 Então o que fazer nesse caso é de seleção para ver se ainda temos espaço. 870 00:47:20,690 --> 00:47:23,110 É o nosso tamanho inferior a capacidade? 871 00:47:23,110 --> 00:47:28,480 >> Se assim for, é preciso armazená-lo em a cauda e nós atualizamos nosso tamanho. 872 00:47:28,480 --> 00:47:30,250 Então, o que pode ser a cauda neste caso? 873 00:47:30,250 --> 00:47:32,360 Não está explicitamente escrito para fora. 874 00:47:32,360 --> 00:47:33,380 Como podemos armazená-lo? 875 00:47:33,380 --> 00:47:34,928 Qual seria a cauda ser? 876 00:47:34,928 --> 00:47:38,600 877 00:47:38,600 --> 00:47:40,190 >> Então, vamos caminhar por este exemplo. 878 00:47:40,190 --> 00:47:44,590 Portanto, esta é uma matriz de tamanho 6, certo? 879 00:47:44,590 --> 00:47:49,220 E temos agora, nosso tamanho é 5. 880 00:47:49,220 --> 00:47:55,240 E quando nós colocá-lo em, ele vai ir para o quinto índice, certo? 881 00:47:55,240 --> 00:47:57,030 Assim armazenar pelo cauda. 882 00:47:57,030 --> 00:48:05,600 >> Outra maneira de escrever cauda seria apenas ser a nossa matriz no índice de tamanho, certo? 883 00:48:05,600 --> 00:48:07,560 Isto é de tamanho 5. 884 00:48:07,560 --> 00:48:11,490 A próxima coisa que vai entrar em cinco. 885 00:48:11,490 --> 00:48:12,296 Legal? 886 00:48:12,296 --> 00:48:13,290 Está bem. 887 00:48:13,290 --> 00:48:16,350 Ele fica um pouco mais complicado quando começamos a mexer com a cabeça. 888 00:48:16,350 --> 00:48:17,060 Sim? 889 00:48:17,060 --> 00:48:20,090 >> AUDIÊNCIA: Isso significa que nós teria declarado uma matriz que 890 00:48:20,090 --> 00:48:23,880 era de cinco elementos de comprimento e então nós estamos adicionando para ele? 891 00:48:23,880 --> 00:48:24,730 >> COLUNA 1: Não. 892 00:48:24,730 --> 00:48:27,560 Portanto, neste caso, esta é uma pilha. 893 00:48:27,560 --> 00:48:31,760 Este seria declarada como uma matriz de tamanho 6. 894 00:48:31,760 --> 00:48:37,120 E, neste caso, nós só tem um espaço à esquerda. 895 00:48:37,120 --> 00:48:42,720 >> OK, então uma coisa é neste caso, se a nossa cabeça está em 0, 896 00:48:42,720 --> 00:48:45,270 então nós apenas pode adicioná-lo em tamanho. 897 00:48:45,270 --> 00:48:51,020 Mas fica um pouco mais complicado porque, na verdade, eles 898 00:48:51,020 --> 00:48:52,840 não tem um slide para isso, então eu vou 899 00:48:52,840 --> 00:48:56,670 desenhar um porque não é tão simples, uma vez que 900 00:48:56,670 --> 00:48:59,230 começar a se livrar das coisas. 901 00:48:59,230 --> 00:49:03,920 Assim, enquanto que com uma pilha você só tem 902 00:49:03,920 --> 00:49:08,920 se preocupar com o que o tamanho é quando você está adicionando algo sobre, 903 00:49:08,920 --> 00:49:15,710 com uma fila que você também precisa fazer Certifique-se que sua cabeça está contabilizado, 904 00:49:15,710 --> 00:49:20,760 porque uma coisa legal sobre filas é que se você não estiver com sua capacidade, 905 00:49:20,760 --> 00:49:23,040 você pode realmente fazer isso enrole. 906 00:49:23,040 --> 00:49:28,810 >> OK, então um coisa-- oh, isso é terrível giz. 907 00:49:28,810 --> 00:49:31,815 Uma coisa a considerar é o caso. 908 00:49:31,815 --> 00:49:35,514 909 00:49:35,514 --> 00:49:37,140 Nós vamos apenas fazer cinco. 910 00:49:37,140 --> 00:49:41,810 OK, então nós estamos indo para dizem que a cabeça está aqui. 911 00:49:41,810 --> 00:49:46,140 Este é 0, 1, 2, 3, 4. 912 00:49:46,140 --> 00:49:54,210 >> A cabeça está lá, e por favor, tem coisas em si. 913 00:49:54,210 --> 00:49:58,340 E queremos acrescentar algo, certo? 914 00:49:58,340 --> 00:50:01,170 Então, a única coisa que precisamos sabe é que a cabeça é sempre 915 00:50:01,170 --> 00:50:05,620 vai se mover desta maneira e em seguida, volta ao início volta, OK? 916 00:50:05,620 --> 00:50:10,190 >> Portanto, esta fila tem espaço, certo? 917 00:50:10,190 --> 00:50:13,950 Ele tem espaço no início, tipo da frente deste. 918 00:50:13,950 --> 00:50:17,920 Então o que precisamos fazer é nós precisa para calcular a cauda. 919 00:50:17,920 --> 00:50:20,530 Se você sabe que seu cabeça não mudou, cauda 920 00:50:20,530 --> 00:50:24,630 é apenas a sua matriz no o índice do tamanho. 921 00:50:24,630 --> 00:50:30,000 >> Mas, na realidade, se você estiver usando uma fila, sua cabeça provavelmente está sendo atualizado. 922 00:50:30,000 --> 00:50:33,890 Então o que você precisa fazer é na verdade calcular a cauda. 923 00:50:33,890 --> 00:50:39,990 Então, o que fazemos é esta fórmula aqui, que eu vou deixar você 924 00:50:39,990 --> 00:50:42,680 vocês pensam sobre e então vamos falar sobre isso. 925 00:50:42,680 --> 00:50:49,567 926 00:50:49,567 --> 00:50:50,400 Portanto, esta é a capacidade. 927 00:50:50,400 --> 00:50:55,890 928 00:50:55,890 --> 00:50:59,660 >> Então, isso vai realmente dar-lhe uma maneira de fazê-lo. 929 00:50:59,660 --> 00:51:03,205 930 00:51:03,205 --> 00:51:04,330 Porque neste caso, o quê? 931 00:51:04,330 --> 00:51:09,205 Nossa cabeça está em 1, nosso tamanho é 4. 932 00:51:09,205 --> 00:51:11,760 933 00:51:11,760 --> 00:51:18,490 Se nós mod que por 5, obtemos 0, que é onde deve introduzir-lo. 934 00:51:18,490 --> 00:51:23,320 935 00:51:23,320 --> 00:51:26,080 >> Então, em seguida, no caso seguinte, se tivéssemos que fazer isso, 936 00:51:26,080 --> 00:51:33,390 podemos dizer, OK, vamos desenfileirá algo. 937 00:51:33,390 --> 00:51:34,390 Nós desenfileirá isso. 938 00:51:34,390 --> 00:51:37,740 Tomamos a este elemento, certo? 939 00:51:37,740 --> 00:51:47,930 >> E agora a nossa cabeça está apontando aqui, e queremos adicionar em outra coisa. 940 00:51:47,930 --> 00:51:52,470 Este é basicamente o de trás da nossa linha, certo? 941 00:51:52,470 --> 00:51:55,450 As filas podem envolver em torno da matriz. 942 00:51:55,450 --> 00:51:57,310 Essa é uma das principais diferenças. 943 00:51:57,310 --> 00:51:58,780 Pilhas, você não pode fazer isso. 944 00:51:58,780 --> 00:52:01,140 >> Com filas, você pode porque tudo o que importa 945 00:52:01,140 --> 00:52:03,940 é que você sabe o que foi adicionado mais recentemente. 946 00:52:03,940 --> 00:52:10,650 Uma vez que tudo vai ser adicionado em neste sentido para a esquerda, no caso em apreço, 947 00:52:10,650 --> 00:52:16,480 e em seguida, enrole ao redor, você pode continuar colocando em novos elementos 948 00:52:16,480 --> 00:52:18,830 na parte da frente da matriz porque não é realmente 949 00:52:18,830 --> 00:52:20,640 a frente da matriz mais. 950 00:52:20,640 --> 00:52:26,320 Você pode pensar no início do matriz como em sua cabeça realmente é. 951 00:52:26,320 --> 00:52:29,710 >> Portanto, esta fórmula é como você calcular a sua cauda. 952 00:52:29,710 --> 00:52:32,780 953 00:52:32,780 --> 00:52:35,610 Será que isso faz sentido? 954 00:52:35,610 --> 00:52:36,110 Está bem. 955 00:52:36,110 --> 00:52:39,400 956 00:52:39,400 --> 00:52:44,040 OK, dequeue, e em seguida Vocês têm 10 minutos 957 00:52:44,040 --> 00:52:48,840 para me perguntar qualquer perguntas de esclarecimento você quer, porque eu sei que é loucura. 958 00:52:48,840 --> 00:52:51,980 >> Tudo bem, então no mesmo maneira-- Eu não sei se vocês notaram, 959 00:52:51,980 --> 00:52:53,450 mas CS é tudo sobre padrões. 960 00:52:53,450 --> 00:52:57,370 As coisas são muito bonito o mesmo, apenas com pequenos ajustes. 961 00:52:57,370 --> 00:52:58,950 Então mesma coisa aqui. 962 00:52:58,950 --> 00:53:04,040 Precisamos verificar para ver se realmente têm algo em nossa fila, certo? 963 00:53:04,040 --> 00:53:05,960 Dizer, OK, é o nosso tamanho maior que 0? 964 00:53:05,960 --> 00:53:06,730 Legal. 965 00:53:06,730 --> 00:53:10,690 >> Se o fizermos, então nós nos movemos nossa cabeça, que é o que eu acabei demonstrado aqui. 966 00:53:10,690 --> 00:53:13,870 Nós atualizamos a nossa cabeça para ser mais um. 967 00:53:13,870 --> 00:53:18,390 E depois que nós diminuiremos nossa tamanho e retornar o elemento. 968 00:53:18,390 --> 00:53:21,000 969 00:53:21,000 --> 00:53:26,250 >> Há muito mais concreto código em study.cs50.net, 970 00:53:26,250 --> 00:53:29,440 e eu recomendo ir por isso, se você tiver tempo, 971 00:53:29,440 --> 00:53:30,980 mesmo que seja apenas um pseudo-código. 972 00:53:30,980 --> 00:53:35,980 E se vocês querem falar através que comigo um a um, por favor, me deixe 973 00:53:35,980 --> 00:53:37,500 sei. 974 00:53:37,500 --> 00:53:38,770 Eu ficaria feliz em. 975 00:53:38,770 --> 00:53:42,720 As estruturas de dados, se você tomar CS 124, você vai 976 00:53:42,720 --> 00:53:47,830 sabemos que as estruturas de dados ficar muito diversão e este é apenas o começo. 977 00:53:47,830 --> 00:53:50,350 >> Então, eu sei que é difícil. 978 00:53:50,350 --> 00:53:51,300 Está certo. 979 00:53:51,300 --> 00:53:52,410 Nós lutamos. 980 00:53:52,410 --> 00:53:53,630 Eu continuo a fazer. 981 00:53:53,630 --> 00:53:56,660 Então não se preocupe muito com isso. 982 00:53:56,660 --> 00:54:02,390 >> Mas isso é basicamente o seu Crash Course em estruturas de dados. 983 00:54:02,390 --> 00:54:03,400 Eu sei que é muito. 984 00:54:03,400 --> 00:54:06,860 Existe alguma coisa que nós gostaria de ir de novo? 985 00:54:06,860 --> 00:54:09,400 Qualquer coisa que quero falar através? 986 00:54:09,400 --> 00:54:10,060 Sim? 987 00:54:10,060 --> 00:54:16,525 >> AUDIÊNCIA: Para esse exemplo, de modo a cauda nova é a 0 sobre isso? 988 00:54:16,525 --> 00:54:17,150 COLUNA 1: Sim. 989 00:54:17,150 --> 00:54:18,230 AUDIÊNCIA: OK. 990 00:54:18,230 --> 00:54:24,220 Então passando, você teria um mais 4 ou- 991 00:54:24,220 --> 00:54:27,671 >> COLUNA 1: Então você estava dizendo, quando queremos ir fazer isso de novo? 992 00:54:27,671 --> 00:54:28,296 AUDIÊNCIA: Yeah. 993 00:54:28,296 --> 00:54:38,290 Então, se você estava imaginando out-- onde estão você calcular a cauda da nisso? 994 00:54:38,290 --> 00:54:44,260 >> COLUNA 1: Então a cauda foi em-- eu mudei isso. 995 00:54:44,260 --> 00:54:52,010 Assim, neste exemplo aqui, esta foi a matriz que estamos olhando, OK? 996 00:54:52,010 --> 00:54:54,670 Portanto, temos coisas em 1, 2, 3 e 4. 997 00:54:54,670 --> 00:55:05,850 Portanto, temos a nossa cabeça é igual a 1 no Neste ponto, o tamanho e a é igual a 4 998 00:55:05,850 --> 00:55:07,050 neste ponto, certo? 999 00:55:07,050 --> 00:55:08,960 >> Vocês todos concordam que é o caso? 1000 00:55:08,960 --> 00:55:14,620 Então nós fazemos a cabeça mais o tamanho, o que nos dá 5, e então nós mod por 5. 1001 00:55:14,620 --> 00:55:20,690 Recebemos 0, o que nos diz que 0 é onde está a nossa cauda, ​​onde temos espaço. 1002 00:55:20,690 --> 00:55:22,010 >> AUDIÊNCIA: O que é um cap? 1003 00:55:22,010 --> 00:55:23,520 >> COLUNA 1: A capacidade. 1004 00:55:23,520 --> 00:55:24,020 Desculpe. 1005 00:55:24,020 --> 00:55:29,640 Então esse é o tamanho de sua matriz. 1006 00:55:29,640 --> 00:55:35,210 1007 00:55:35,210 --> 00:55:36,047 Sim? 1008 00:55:36,047 --> 00:55:39,210 >> AUDIÊNCIA: [inaudível] antes retornamos o elemento? 1009 00:55:39,210 --> 00:55:46,270 >> COLUNA 1: Então, passamos a ir ou voltar do momento? 1010 00:55:46,270 --> 00:55:52,680 Então, se nós nos movemos um, diminuir o tamanho? 1011 00:55:52,680 --> 00:55:54,150 Aguente. 1012 00:55:54,150 --> 00:55:55,770 Eu definitivamente esqueceu o outro. 1013 00:55:55,770 --> 00:56:00,646 1014 00:56:00,646 --> 00:56:01,990 Não importa. 1015 00:56:01,990 --> 00:56:04,980 Não há outra fórmula. 1016 00:56:04,980 --> 00:56:09,980 Sim, você gostaria de voltar a cabeça e, em seguida, movê-lo de volta. 1017 00:56:09,980 --> 00:56:13,270 >> AUDIÊNCIA: OK, porque neste ponto, a cabeça estava em 0, 1018 00:56:13,270 --> 00:56:18,452 e depois quiser retornar índice 0 e, em seguida, fazer a cabeça 1? 1019 00:56:18,452 --> 00:56:19,870 >> COLUNA 1: Certo. 1020 00:56:19,870 --> 00:56:22,820 Eu acho que há outro tipo fórmula de como este. 1021 00:56:22,820 --> 00:56:26,970 Eu não tenho isso no topo da minha cabeça como Eu não quero dar-lhe a pessoa errada. 1022 00:56:26,970 --> 00:56:35,470 Mas eu acho que é perfeitamente válida para digamos, OK, guarde esta element-- o que quer 1023 00:56:35,470 --> 00:56:40,759 elemento de cabeça é-- diminuir sua tamanho, mover a cabeça mais, e retorno 1024 00:56:40,759 --> 00:56:41,800 o que quer que esse elemento é. 1025 00:56:41,800 --> 00:56:44,760 Isso é perfeitamente válido. 1026 00:56:44,760 --> 00:56:45,260 Está bem. 1027 00:56:45,260 --> 00:56:48,360 1028 00:56:48,360 --> 00:56:53,560 Eu sinto que isso não é como o most-- você não está 1029 00:56:53,560 --> 00:56:55,740 vai sair daqui como, sim, eu sei tentativas. 1030 00:56:55,740 --> 00:56:56,880 Eu tenho tudo. 1031 00:56:56,880 --> 00:56:57,670 Isso está ok. 1032 00:56:57,670 --> 00:57:00,200 Eu prometo. 1033 00:57:00,200 --> 00:57:05,240 Mas estruturas de dados que são algo é preciso muito tempo para se acostumar. 1034 00:57:05,240 --> 00:57:10,010 Provavelmente uma das mais difíceis coisas, eu acho que, no curso. 1035 00:57:10,010 --> 00:57:15,330 >> Por isso, definitivamente leva repetição e olhando at-- I 1036 00:57:15,330 --> 00:57:20,050 realmente não sei listas ligadas até que eu fiz demais com eles, 1037 00:57:20,050 --> 00:57:22,550 da mesma forma que eu não fiz realmente entender ponteiros 1038 00:57:22,550 --> 00:57:27,040 até que eu tive que ensiná-lo para dois anos e faço meus próprios Série de Exercícios com ele. 1039 00:57:27,040 --> 00:57:28,990 Ele tem um monte de reiteração e do tempo. 1040 00:57:28,990 --> 00:57:32,600 E, eventualmente, ele vai tipo de clique. 1041 00:57:32,600 --> 00:57:36,320 >> Mas, enquanto isso, se você tem o tipo de um elevado nível de compreensão que 1042 00:57:36,320 --> 00:57:39,321 estes fazem, seus prós e que é o que cons-- 1043 00:57:39,321 --> 00:57:41,820 nós realmente tendem a enfatizar, especialmente no curso de introdução. 1044 00:57:41,820 --> 00:57:45,511 Como, por que usaria uma tentativa através de uma matriz? 1045 00:57:45,511 --> 00:57:48,010 Como, quais são os aspectos positivos e negativos de cada um deles? 1046 00:57:48,010 --> 00:57:51,610 >> E entender os trade-offs entre cada uma destas estruturas 1047 00:57:51,610 --> 00:57:54,910 é o que é muito mais importante agora. 1048 00:57:54,910 --> 00:57:58,140 Não pode ser um louco ou duas perguntas que é 1049 00:57:58,140 --> 00:58:03,710 vai pedir-lhe para implementar impulso ou implementar pop ou enfileiramento e retirar da fila. 1050 00:58:03,710 --> 00:58:07,340 Mas, na maior parte, tendo essa maior nível de compreensão e mais 1051 00:58:07,340 --> 00:58:09,710 de uma compreensão intuitiva é mais importante do que realmente 1052 00:58:09,710 --> 00:58:11,250 ser capaz de implementá-lo. 1053 00:58:11,250 --> 00:58:14,880 >> Seria realmente maravilhoso se todos vocês podia sair e ir para implementar uma tentativa, 1054 00:58:14,880 --> 00:58:19,720 mas entendemos que não é necessariamente a coisa mais razoável agora. 1055 00:58:19,720 --> 00:58:23,370 Mas você pode em seu pset, se você quiser para, em seguida, você vai começar a prática, 1056 00:58:23,370 --> 00:58:27,200 e, em seguida, talvez você realmente entendê-la. 1057 00:58:27,200 --> 00:58:27,940 Sim? 1058 00:58:27,940 --> 00:58:30,440 >> AUDIÊNCIA: OK, então quais são que pretendia usar no pset? 1059 00:58:30,440 --> 00:58:31,916 Preciso usar um deles? 1060 00:58:31,916 --> 00:58:32,540 COLUNA 1: Sim. 1061 00:58:32,540 --> 00:58:34,199 Então você tem a sua escolha. 1062 00:58:34,199 --> 00:58:36,740 Eu acho que, neste caso, podemos falar sobre o pset um pouco 1063 00:58:36,740 --> 00:58:40,480 porque eu corri através destes. 1064 00:58:40,480 --> 00:58:47,779 Assim, no seu pset, você tem o seu escolha de tentativas ou tabelas de hash. 1065 00:58:47,779 --> 00:58:49,570 Algumas pessoas vão tentar e usar filtros de Bloom, 1066 00:58:49,570 --> 00:58:51,840 mas aqueles que tecnicamente não estão corretas. 1067 00:58:51,840 --> 00:58:55,804 Devido à sua natureza probabilística, eles dão falsos positivos, às vezes. 1068 00:58:55,804 --> 00:58:57,095 São olhar frio em, no entanto. 1069 00:58:57,095 --> 00:58:59,030 Recomendo olhar para eles, pelo menos. 1070 00:58:59,030 --> 00:59:03,260 Mas você tem a sua escolha entre uma tabela hash e uma tentativa. 1071 00:59:03,260 --> 00:59:06,660 E isso vai ser onde você carrega em seu dicionário. 1072 00:59:06,660 --> 00:59:09,230 >> E você terá que escolher sua função de hash, 1073 00:59:09,230 --> 00:59:13,420 você precisa escolher quantos baldes você tem, e vai variar. 1074 00:59:13,420 --> 00:59:17,440 Como se você tiver mais baldes, talvez ele vai correr mais rápido. 1075 00:59:17,440 --> 00:59:22,790 Mas talvez você está desperdiçando um muito espaço dessa forma, no entanto. 1076 00:59:22,790 --> 00:59:26,320 Você tem que descobrir isso. 1077 00:59:26,320 --> 00:59:27,140 Mmhmm? 1078 00:59:27,140 --> 00:59:29,875 >> AUDIÊNCIA: Você disse antes que podemos usar outras funções de hash, 1079 00:59:29,875 --> 00:59:31,750 que não temos a criar uma função hash? 1080 00:59:31,750 --> 00:59:32,666 >> COLUNA 1: Sim, certo. 1081 00:59:32,666 --> 00:59:38,150 Então, literalmente, para a sua função de hash, como o google "função hash" 1082 00:59:38,150 --> 00:59:40,770 e olhar para alguns dos mais interessantes. 1083 00:59:40,770 --> 00:59:43,250 Você não está prevista a construção suas próprias funções de hash. 1084 00:59:43,250 --> 00:59:46,100 As pessoas gastam o seu teses sobre essas coisas. 1085 00:59:46,100 --> 00:59:50,250 >> Então não se preocupe sobre a construção de seu próprio país. 1086 00:59:50,250 --> 00:59:53,350 Encontrar uma linha para começar. 1087 00:59:53,350 --> 00:59:56,120 Alguns deles você tem que manipular um pouco 1088 00:59:56,120 --> 00:59:59,430 para garantir que os tipos de retorno igualar-se e outros enfeites, assim, no início, 1089 00:59:59,430 --> 01:00:02,420 Eu recomendaria usar algo realmente fácil que talvez apenas 1090 01:00:02,420 --> 01:00:04,680 hashes na primeira letra. 1091 01:00:04,680 --> 01:00:08,760 E, em seguida, uma vez que você tem que trabalhar, incorporando uma função hash mais frio. 1092 01:00:08,760 --> 01:00:09,260 Mmhmm? 1093 01:00:09,260 --> 01:00:13,020 >> AUDIÊNCIA: Será que um tente ser ou eficiente, mas apenas mais difícil, como-- 1094 01:00:13,020 --> 01:00:15,880 >> COLUNA 1: Então uma chance, eu acho, é intuitivamente difícil de implementar 1095 01:00:15,880 --> 01:00:18,310 mas é muito rápido. 1096 01:00:18,310 --> 01:00:20,620 No entanto, ocupa mais espaço. 1097 01:00:20,620 --> 01:00:25,270 Novamente, você pode otimizar tanto dos que estão no diferentes maneiras e existem maneiras a-- 1098 01:00:25,270 --> 01:00:26,770 AUDIÊNCIA: Como estamos classificados sobre isso? 1099 01:00:26,770 --> 01:00:27,540 Será que matter-- 1100 01:00:27,540 --> 01:00:29,164 >> COLUNA 1: Então você está classificado como normal. 1101 01:00:29,164 --> 01:00:31,330 Você vai ser graduada em design. 1102 01:00:31,330 --> 01:00:36,020 Independentemente da forma como você faz, você quer ter certeza que é tão elegante como ela pode ser 1103 01:00:36,020 --> 01:00:38,610 e tão eficiente quanto possível. 1104 01:00:38,610 --> 01:00:41,950 Mas se você escolher uma tentativa ou de hash mesa, contanto que ele funciona, 1105 01:00:41,950 --> 01:00:45,350 estamos felizes com isso. 1106 01:00:45,350 --> 01:00:48,370 E se você usar algo que hashes na primeira letra, isso é bom, 1107 01:00:48,370 --> 01:00:51,410 como talvez como design-wise. 1108 01:00:51,410 --> 01:00:53,410 Também estamos atingindo o ponto neste semester-- 1109 01:00:53,410 --> 01:00:55,340 Eu não sei se você caras noticed-- se você estiver 1110 01:00:55,340 --> 01:00:58,780 graus PSet diminuir um pouco por causa do design e outros enfeites, 1111 01:00:58,780 --> 01:00:59,900 isso é perfeitamente normal. 1112 01:00:59,900 --> 01:01:02,960 Está ficando a um ponto onde sua programas estão ficando cada vez mais complicado. 1113 01:01:02,960 --> 01:01:04,830 Há mais lugares você pode melhorar. 1114 01:01:04,830 --> 01:01:06,370 >> Por isso é perfeitamente normal. 1115 01:01:06,370 --> 01:01:08,810 Não é que você está fazendo pior em seu pset. 1116 01:01:08,810 --> 01:01:11,885 É só que estamos sendo mais difícil para você agora. 1117 01:01:11,885 --> 01:01:13,732 Então, todo mundo está sentindo isso. 1118 01:01:13,732 --> 01:01:14,940 Eu só graduada todas as suas Série de Exercícios. 1119 01:01:14,940 --> 01:01:16,490 Eu sei que todo mundo está sentindo isso. 1120 01:01:16,490 --> 01:01:19,600 >> Portanto, não se preocupar com isso. 1121 01:01:19,600 --> 01:01:23,580 E se você tiver quaisquer dúvidas Série de Exercícios anteriores ou maneiras que você pode melhorar, 1122 01:01:23,580 --> 01:01:27,760 Eu tento e comentar o específico lugares, mas às vezes é tarde 1123 01:01:27,760 --> 01:01:30,840 e eu fico cansado. 1124 01:01:30,840 --> 01:01:34,885 Existem outras coisas sobre estruturas de dados? 1125 01:01:34,885 --> 01:01:37,510 Tenho certeza de que vocês realmente não quero falar mais deles, 1126 01:01:37,510 --> 01:01:42,650 mas se houver, eu estou feliz de passar por cima deles, assim como qualquer coisa 1127 01:01:42,650 --> 01:01:45,580 de palestra passado semana ou na semana passada. 1128 01:01:45,580 --> 01:01:51,580 >> Eu sei que na semana passada foi toda a revisão, de modo podemos ter pulado alguma revisão 1129 01:01:51,580 --> 01:01:54,190 da palestra. 1130 01:01:54,190 --> 01:01:58,230 Todas as outras perguntas eu posso responder? 1131 01:01:58,230 --> 01:01:59,350 OK, tudo bem. 1132 01:01:59,350 --> 01:02:02,400 Bem, vocês sair 15 minutos mais cedo. 1133 01:02:02,400 --> 01:02:08,370 >> Espero que este era semi-útil, pelo menos, e eu vou ver vocês na próxima semana, 1134 01:02:08,370 --> 01:02:12,150 ou o horário de expediente quinta-feira. 1135 01:02:12,150 --> 01:02:15,285 Há pedidos de lanches para a próxima semana, que é a coisa? 1136 01:02:15,285 --> 01:02:17,459 Porque eu esqueci de doces hoje. 1137 01:02:17,459 --> 01:02:19,750 E eu trouxe doces última semana, mas era Dia de Colombo, 1138 01:02:19,750 --> 01:02:25,400 então não eram como seis pessoas que tinha quatro sacos de doces para si. 1139 01:02:25,400 --> 01:02:28,820 Eu posso trazer Starbursts novamente se quiser. 1140 01:02:28,820 --> 01:02:29,580 Starbursts? 1141 01:02:29,580 --> 01:02:32,250 OK, parece bom. 1142 01:02:32,250 --> 01:02:35,050 Tenha um ótimo dia, pessoal. 1143 01:02:35,050 --> 01:02:39,510