1 00:00:00,000 --> 00:00:11,460 2 00:00:11,460 --> 00:00:12,250 >> DAVID MALAN: Tudo bem. 3 00:00:12,250 --> 00:00:13,860 Bem-vindo de volta ao CS50. 4 00:00:13,860 --> 00:00:16,190 Este é o início da semana 8. 5 00:00:16,190 --> 00:00:21,320 E lembrar que problema set terminou 5 com um pouco de um desafio. 6 00:00:21,320 --> 00:00:25,210 Então, supondo que você recuperou todo o seu Companheiros de ensino e fotografias da CA 7 00:00:25,210 --> 00:00:30,480 no arquivo card.raw, você é elegível agora encontrar todas essas pessoas, e 8 00:00:30,480 --> 00:00:34,510 um sortudo ganhador vai a pé para casa com um destas coisas, o movimento salto 9 00:00:34,510 --> 00:00:37,450 dispositivo que você pode usar para a final projetos, por exemplo. 10 00:00:37,450 --> 00:00:39,860 >> Este, a cada ano, leva a um pouco de bizarrice. 11 00:00:39,860 --> 00:00:43,480 E assim que eu pensei que eu iria fazer é compartilhar com você algumas das notas que têm 12 00:00:43,480 --> 00:00:47,370 ido para trás e para frente sobre a lista de funcionários da tarde. 13 00:00:47,370 --> 00:00:51,110 Por exemplo, ontem à noite, citações unquote, a partir de um dos funcionários 14 00:00:51,110 --> 00:00:55,000 membros ", eu só tinha uma batida estudante na minha porta para tirar uma foto comigo. 15 00:00:55,000 --> 00:00:59,020 Stalkers, eu lhe digo. "Começou bastante descritivo e depois nos mudamos 16 00:00:59,020 --> 00:01:02,830 para, uma hora mais tarde, "Eu tive um estudante esperando por mim após a seção 17 00:01:02,830 --> 00:01:06,080 e ele tinha todos os nossos nomes e fotos em algumas folhas de papel. "Tudo bem. 18 00:01:06,080 --> 00:01:09,230 Assim organizado, mas não tudo o que assustador ainda. 19 00:01:09,230 --> 00:01:12,520 >> Então, "Eu estava fora da cidade neste fim de semana, e quando voltei, havia um em 20 00:01:12,520 --> 00:01:12,630 meu 21 00:01:12,630 --> 00:01:16,740 quarto. "[risos] 22 00:01:16,740 --> 00:01:20,410 DAVID MALAN: Next citação de uma equipe membro ", disse um aluno veio à minha casa em 23 00:01:20,410 --> 00:01:25,330 Somerville às 4 da manhã, esta manhã. "Next pessoal, "Eu cheguei ao meu hotel em San 24 00:01:25,330 --> 00:01:30,016 Francisco e um aluno estava esperando por me no hall de entrada com três DSLRs. " 25 00:01:30,016 --> 00:01:31,510 Tipo de câmera. 26 00:01:31,510 --> 00:01:34,980 "Eu não estou nem na equipe neste semestre, mas um estudante invadiu a minha casa esta 27 00:01:34,980 --> 00:01:40,480 manhã e registrou a coisa toda com vidro Google. "E então, finalmente, 28 00:01:40,480 --> 00:01:43,650 "Pelo menos 12 pessoas foram avidamente aguardando para mim quando eu saí do meu 29 00:01:43,650 --> 00:01:44,800 limo, e então eu 30 00:01:44,800 --> 00:01:46,970 acordei. "Tudo bem. 31 00:01:46,970 --> 00:01:57,690 Assim, entre as fotografias, como você pode lembrar, são este homem aqui, que você 32 00:01:57,690 --> 00:02:01,850 pode saber como Milo Banana, que vive com Lauren Carvalho, a nossa cabeça 33 00:02:01,850 --> 00:02:02,905 ensino Fellow. 34 00:02:02,905 --> 00:02:05,170 Milo, Milo, vem cá menino. 35 00:02:05,170 --> 00:02:06,320 Milo. 36 00:02:06,320 --> 00:02:08,650 Milo. 37 00:02:08,650 --> 00:02:12,230 Lembre-se, ele está usando Google de vidro, de modo vamos mostrar tudo isso depois. 38 00:02:12,230 --> 00:02:16,190 Portanto, esta é Milo se você gostaria de tirar uma fotografia com ele depois. 39 00:02:16,190 --> 00:02:18,240 Se você gostaria de olhar para fora para o público lá. 40 00:02:18,240 --> 00:02:19,430 OK. 41 00:02:19,430 --> 00:02:20,200 Isso é bom filmagens. 42 00:02:20,200 --> 00:02:22,556 Bem, Milo Banana. 43 00:02:22,556 --> 00:02:23,941 Oh, não faça isso. 44 00:02:23,941 --> 00:02:29,020 >> [Risos] 45 00:02:29,020 --> 00:02:29,470 >> OK. 46 00:02:29,470 --> 00:02:34,550 Assim, uma palavra, em seguida, sobre o que está por vir, porque quando começamos a transição, 47 00:02:34,550 --> 00:02:38,410 esta semana especificamente, a partir de C, numa ambiente de linha de comando para PHP e 48 00:02:38,410 --> 00:02:42,720 JavaScript e SQL e HTML e CSS em um ambiente baseado na web, estaremos 49 00:02:42,720 --> 00:02:44,490 equipando-o com toda a mais conhecimento para 50 00:02:44,490 --> 00:02:46,010 potenciais projetos finais. 51 00:02:46,010 --> 00:02:49,240 Para isso, o curso tem uma tradição de realização de seminários que 52 00:02:49,240 --> 00:02:50,950 são sobre temas tangenciais ao curso. 53 00:02:50,950 --> 00:02:54,330 Muito relacionado à programação e desenvolvimento de aplicativos e assim por diante, mas 54 00:02:54,330 --> 00:02:57,010 não necessariamente por explorado próprio plano de estudos do curso. 55 00:02:57,010 --> 00:03:00,250 >> Então, se você poderia estar interessado em um ou mais de seminários deste ano, 56 00:03:00,250 --> 00:03:02,530 registrar em cs50.net/seminar. 57 00:03:02,530 --> 00:03:06,170 Existem seminários idosas em cs50.net/seminars. 58 00:03:06,170 --> 00:03:10,620 E no plantel, até agora, para este ano são surpreendentes Aplicativos Web com Ruby on 59 00:03:10,620 --> 00:03:13,580 Carris, que é uma alternativa linguagem para PHP. 60 00:03:13,580 --> 00:03:14,900 Linguística Computacional. 61 00:03:14,900 --> 00:03:18,710 Introdução à IOS, que é o plataforma que é usado para o iPhone e 62 00:03:18,710 --> 00:03:19,850 desenvolvimento iPad. 63 00:03:19,850 --> 00:03:22,890 JavaScript para Web Apps, vamos cobrir isso, mas neste seminário, você vai 64 00:03:22,890 --> 00:03:24,070 em mais detalhe. 65 00:03:24,070 --> 00:03:27,390 >> Leap Movimento, então vamos realmente ter algum dos nossos amigos da Leap Movimento, 66 00:03:27,390 --> 00:03:29,160 da própria empresa, se juntar a nós. 67 00:03:29,160 --> 00:03:31,800 Amanhã, na verdade, para fornecer um hands-on seminário, se 68 00:03:31,800 --> 00:03:33,320 de seu interesse. 69 00:03:33,320 --> 00:03:38,770 Meteor.js, uma técnica alternativa para usando JavaScript e não em um navegador, 70 00:03:38,770 --> 00:03:39,970 mas num servidor. 71 00:03:39,970 --> 00:03:42,110 Node.js., que é muito nessa veia bem. 72 00:03:42,110 --> 00:03:43,650 Design elegante Android. 73 00:03:43,650 --> 00:03:46,990 Android ser uma alternativa muito popular para iOS e Windows Phone 74 00:03:46,990 --> 00:03:48,790 e outras plataformas móveis. 75 00:03:48,790 --> 00:03:51,180 E Web Active Defense Segurança. 76 00:03:51,180 --> 00:03:54,590 >> Então, na verdade, se você quiser se envolver nisso, deixe-me 77 00:03:54,590 --> 00:03:55,840 anote isso. 78 00:03:55,840 --> 00:03:57,790 Estamos muito felizes em dizer que nossos amigos em Salto 79 00:03:57,790 --> 00:03:59,140 De movimento, que é uma inicialização - 80 00:03:59,140 --> 00:04:01,300 este dispositivo realmente acabou fora há alguns meses - 81 00:04:01,300 --> 00:04:05,960 graciosamente doaram 30 dispositivos para a classe de como muitos alunos, se 82 00:04:05,960 --> 00:04:08,670 gostaria de pedir o hardware para o final do semestre, e usá-lo para 83 00:04:08,670 --> 00:04:10,390 um projeto real final. 84 00:04:10,390 --> 00:04:11,890 Eles suportam várias línguas. 85 00:04:11,890 --> 00:04:16,040 Nenhum deles C, nenhum deles PHP, assim perceber um ou mais destes seminários 86 00:04:16,040 --> 00:04:16,899 pode revelar-se de interesse. 87 00:04:16,899 --> 00:04:19,730 E todos eles vão ser filmado em caso em que você não é capaz 88 00:04:19,730 --> 00:04:21,380 para comparecer em pessoa. 89 00:04:21,380 --> 00:04:25,000 A programação será anunciada via enviar e-mail como se solidificar quartos. 90 00:04:25,000 --> 00:04:28,460 >> E, por último, se você vai para projects.cs.50.net, este é um sítio 91 00:04:28,460 --> 00:04:31,450 mantemos a cada ano que convidamos pessoas da comunidade, professores, 92 00:04:31,450 --> 00:04:36,420 departamentos, funcionários e ambos em um lado de fora de CS50 para 93 00:04:36,420 --> 00:04:37,730 propor idéias para projetos. 94 00:04:37,730 --> 00:04:39,050 Coisas de interesse para grupos de estudantes. 95 00:04:39,050 --> 00:04:40,600 Coisas de interesse para os departamentos. 96 00:04:40,600 --> 00:04:43,990 Então não virar lá, se você está lutando com a incerteza quanto ao que você 97 00:04:43,990 --> 00:04:46,700 se gostaria de enfrentar. 98 00:04:46,700 --> 00:04:51,760 >> Então última vez que introduziu uma indiscutivelmente estrutura de dados mais complexa do que tínhamos 99 00:04:51,760 --> 00:04:53,300 visto nas últimas semanas. 100 00:04:53,300 --> 00:04:56,550 Nós estávamos usando matrizes bastante feliz como um útil se 101 00:04:56,550 --> 00:04:58,160 estrutura de dados simplista. 102 00:04:58,160 --> 00:05:00,570 Então, nós introduzimos estes, que naturalmente estão ligados listas. 103 00:05:00,570 --> 00:05:05,470 E o que foi uma das motivações para introduzindo esta estrutura de dados? 104 00:05:05,470 --> 00:05:06,930 Sim? 105 00:05:06,930 --> 00:05:07,250 O que é isso? 106 00:05:07,250 --> 00:05:08,080 >> AUDIÊNCIA: tamanho dinâmico. 107 00:05:08,080 --> 00:05:09,040 >> DAVID MALAN: tamanho dinâmico. 108 00:05:09,040 --> 00:05:11,890 Assim, enquanto em ordem, você tem que conhecer antecipadamente o seu tamanho quando 109 00:05:11,890 --> 00:05:12,740 você alocá-lo. 110 00:05:12,740 --> 00:05:14,380 Na lista ligada, você não tem que saber isso. 111 00:05:14,380 --> 00:05:17,610 Você pode apenas malloc, ou, mais geralmente, atribuir um adicional 112 00:05:17,610 --> 00:05:20,720 nó, por assim dizer, a qualquer momento você pretende inserir mais dados. 113 00:05:20,720 --> 00:05:22,670 O nodo tem nenhum significado pré-determinado. 114 00:05:22,670 --> 00:05:25,580 É apenas um termo genérico que descreve algum tipo de recipiente que estamos 115 00:05:25,580 --> 00:05:29,610 usando na nossa estrutura de dados para armazenar algum item de interesse, que neste 116 00:05:29,610 --> 00:05:31,750 caso acontecer de ser inteiros. 117 00:05:31,750 --> 00:05:33,160 >> Mas há sempre uma troca. 118 00:05:33,160 --> 00:05:38,070 Então, nós temos tamanhos dinâmica dos dados estrutura, mas o preço que vamos pagar? 119 00:05:38,070 --> 00:05:40,040 Qual é a desvantagem de listas ligadas? 120 00:05:40,040 --> 00:05:41,006 Sim? 121 00:05:41,006 --> 00:05:41,980 >> AUDIÊNCIA: Requer mais memória. 122 00:05:41,980 --> 00:05:44,240 >> DAVID MALAN: Exige mais memória, como exatamente? 123 00:05:44,240 --> 00:05:46,440 >> AUDIÊNCIA: [inaudível]. 124 00:05:46,440 --> 00:05:47,050 >> DAVID MALAN: Exatamente. 125 00:05:47,050 --> 00:05:50,460 Então, agora temos ponteiros ocupando memória adicional que anteriormente 126 00:05:50,460 --> 00:05:53,040 não precisa, pois a vantagem de uma matriz, é claro, é que 127 00:05:53,040 --> 00:05:54,860 tudo é contíguo, de volta de volta para trás, o que 128 00:05:54,860 --> 00:05:56,380 dá-lhe acesso aleatório. 129 00:05:56,380 --> 00:06:00,710 Porque apenas usando colchete notação, ou mais tecnicamente ponteiro 130 00:06:00,710 --> 00:06:03,580 aritmética, adição muito simples, você pode acessar qualquer 131 00:06:03,580 --> 00:06:05,700 elementos em tempo constante. 132 00:06:05,700 --> 00:06:08,975 E, de fato, esse é o tipo de insinuando outro preço que estamos pagando com um 133 00:06:08,975 --> 00:06:09,760 lista ligada. 134 00:06:09,760 --> 00:06:13,890 >> O que acontece com o tempo de execução algo como Search, se eu quiser 135 00:06:13,890 --> 00:06:17,270 encontrar algum valor e no interior de uma lista ligada? 136 00:06:17,270 --> 00:06:20,290 O que o meu tempo de execução se tornou? 137 00:06:20,290 --> 00:06:21,560 Big O de n. 138 00:06:21,560 --> 00:06:24,060 Se for classificada para? 139 00:06:24,060 --> 00:06:25,440 E se a estrutura de dados é classificado? 140 00:06:25,440 --> 00:06:28,640 Eu posso fazer melhor do que um grande O de n para a pesquisa? 141 00:06:28,640 --> 00:06:31,700 Não, porque na pior das hipóteses ele pode muito bem ser classificado, mas o número 142 00:06:31,700 --> 00:06:32,950 você está procurando pode ser grande. 143 00:06:32,950 --> 00:06:35,370 Pode ser o número 100, o qual pode acontecer de ser tudo 144 00:06:35,370 --> 00:06:36,410 o caminho no final. 145 00:06:36,410 --> 00:06:39,950 E porque você só pode acessar um linked lista nesta implementação por 146 00:06:39,950 --> 00:06:42,690 caminho de seu primeiro nó, você está Ainda meio fora de sorte. 147 00:06:42,690 --> 00:06:47,450 Você tem que atravessar a coisa toda do primeiro ao último, a fim de encontrar 148 00:06:47,450 --> 00:06:49,150 que grande como o valor 100. 149 00:06:49,150 --> 00:06:51,350 Ou para determinar se é nem mesmo lá. 150 00:06:51,350 --> 00:06:55,960 >> Portanto, não podemos fazer o algoritmo em um conjunto de dados estrutura que se parece com isso? 151 00:06:55,960 --> 00:06:59,460 Nós não podemos fazer busca binária, porque busca binária necessário que tínhamos 152 00:06:59,460 --> 00:07:00,740 de acesso aleatório. 153 00:07:00,740 --> 00:07:04,500 Nós poderíamos simplesmente saltar de local para local, sem ter que seguir 154 00:07:04,500 --> 00:07:07,080 estas migalhas de pão na forma todas estas indicações. 155 00:07:07,080 --> 00:07:08,300 >> Agora, como é que vamos implementar isso? 156 00:07:08,300 --> 00:07:12,830 Bem, se formos para a tela aqui, se podemos reimplementar rapidamente esses dados 157 00:07:12,830 --> 00:07:13,440 estrutura - 158 00:07:13,440 --> 00:07:15,670 minha letra não é tudo o que grande aqui, mas vamos tentar. 159 00:07:15,670 --> 00:07:22,030 Typedef struct Então, eo que eu fiz quero chamar essa coisa aqui em cima? 160 00:07:22,030 --> 00:07:22,960 Node. 161 00:07:22,960 --> 00:07:24,580 Então, eu vou ser um bom começo. 162 00:07:24,580 --> 00:07:27,860 E agora, o que precisa estar dentro de a estrutura de dados para que, isoladamente 163 00:07:27,860 --> 00:07:28,430 lista ligada? 164 00:07:28,430 --> 00:07:29,950 Quantos campos? 165 00:07:29,950 --> 00:07:30,450 >> Assim, dois. 166 00:07:30,450 --> 00:07:31,570 Um deles é muito fácil. 167 00:07:31,570 --> 00:07:33,050 Então, int n. 168 00:07:33,050 --> 00:07:35,930 E poderíamos chamar n qualquer coisa que quisermos, mas deve ser um int se estamos 169 00:07:35,930 --> 00:07:37,660 implementação de uma lista encadeada para ints. 170 00:07:37,660 --> 00:07:41,920 E agora o que é que o segundo campo tem que ser? 171 00:07:41,920 --> 00:07:43,460 Struct node *. 172 00:07:43,460 --> 00:07:50,570 Então, se eu fizer struct node *, e então eu pode chamar isso também o que eu quiser, 173 00:07:50,570 --> 00:07:53,510 mas só para ficar claro que eu vou chamar lo ao lado, como temos vindo a fazer. 174 00:07:53,510 --> 00:07:55,270 E então eu vou fechar meus chaves. 175 00:07:55,270 --> 00:08:00,700 >> E agora, como da última vez, Eu coloquei nó aqui. 176 00:08:00,700 --> 00:08:03,830 Mas se eu estou declarando isso é como um nó, por que eu me incomodo de ser tão 177 00:08:03,830 --> 00:08:07,320 detalhado aqui na declaração struct * nó seguinte, em oposição 178 00:08:07,320 --> 00:08:09,210 apenas nó * next? 179 00:08:09,210 --> 00:08:09,904 Sim? 180 00:08:09,904 --> 00:08:12,810 >> AUDIÊNCIA: [inaudível]. 181 00:08:12,810 --> 00:08:14,050 >> DAVID MALAN: Exatamente. 182 00:08:14,050 --> 00:08:14,530 Exatamente. 183 00:08:14,530 --> 00:08:18,320 Porque C realmente leva você literalmente e vê apenas a definição de nó 184 00:08:18,320 --> 00:08:21,230 até aqui, você não pode consultá-lo aqui. 185 00:08:21,230 --> 00:08:24,760 Então nós temos esse tipo de preferência declaração aqui, que é reconhecidamente 186 00:08:24,760 --> 00:08:25,390 mais detalhado. 187 00:08:25,390 --> 00:08:27,810 Struct nó, o que significa agora podemos acessá-lo 188 00:08:27,810 --> 00:08:29,760 no interior da estrutura de dados. 189 00:08:29,760 --> 00:08:33,370 >> E, como um lado, porque isso é tornando-se um pouco mais subjetiva, agora, 190 00:08:33,370 --> 00:08:36,230 a estrela tecnicamente pode ir aqui, ele pode ir aqui, ele pode 191 00:08:36,230 --> 00:08:37,179 até mesmo ir no meio. 192 00:08:37,179 --> 00:08:39,890 Adotamos, no guia de estilo para o curso, a convenção de colocar 193 00:08:39,890 --> 00:08:42,299 a estrela ao lado dos dados tipo, que, neste caso, 194 00:08:42,299 --> 00:08:43,460 seria nó struct. 195 00:08:43,460 --> 00:08:46,620 Mas perceber em um monte de livros e referências on-line, você pode de fato 196 00:08:46,620 --> 00:08:48,450 vê-lo do outro lado. 197 00:08:48,450 --> 00:08:52,200 Mas basta perceber que ambos realmente trabalhar e você deve simplesmente ser 198 00:08:52,200 --> 00:08:52,970 consistente. 199 00:08:52,970 --> 00:08:53,580 >> Tudo bem. 200 00:08:53,580 --> 00:08:55,630 Então essa foi a nossa declaração de nó struct. 201 00:08:55,630 --> 00:08:59,430 Mas, então, começamos a fazer mais coisas sofisticadas. 202 00:08:59,430 --> 00:09:03,410 Por exemplo, decidimos introduzir algo como uma tabela hash. 203 00:09:03,410 --> 00:09:08,160 Então, aqui está uma tabela hash de tamanho n, indexados a partir de 0 no canto superior esquerdo para n 204 00:09:08,160 --> 00:09:09,690 menos um na parte inferior esquerda. 205 00:09:09,690 --> 00:09:11,640 Este poderia ser um hash mesa para nada. 206 00:09:11,640 --> 00:09:15,340 Mas que tipo de coisas que nós falamos sobre o uso de uma tabela hash para? 207 00:09:15,340 --> 00:09:18,370 Armazenar o quê? 208 00:09:18,370 --> 00:09:18,800 >> Nomes. 209 00:09:18,800 --> 00:09:20,870 Poderíamos fazer nomes como fizemos da última vez. 210 00:09:20,870 --> 00:09:22,200 E realmente, você pode armazenar qualquer coisa. 211 00:09:22,200 --> 00:09:24,640 E veremos isso de novo em PHP e JavaScript. 212 00:09:24,640 --> 00:09:28,550 Uma tabela é um bom tipo de suíço Canivete que permite que você armazene 213 00:09:28,550 --> 00:09:33,690 praticamente tudo o que quiser dentro de que associando chaves com valores. 214 00:09:33,690 --> 00:09:34,770 Chaves com valores. 215 00:09:34,770 --> 00:09:37,800 >> Agora, neste caso simples, a nossa chaves são apenas números. 216 00:09:37,800 --> 00:09:40,380 Estamos implementando um hash tabela como uma matriz. 217 00:09:40,380 --> 00:09:43,500 E para que as teclas são 0, 1, 2, e assim por diante. 218 00:09:43,500 --> 00:09:47,200 E assim nós, como seres humanos, decidiu última semana que você sabe que, se estamos 219 00:09:47,200 --> 00:09:50,410 indo para armazenar nomes, vamos arbitrariamente, mas bastante razoável, 220 00:09:50,410 --> 00:09:54,680 supor que Alice, um A nome só vai ser indexado em 0. 221 00:09:54,680 --> 00:09:58,030 E Bob, um nome de B, será indexado em 1, e assim por diante. 222 00:09:58,030 --> 00:10:02,490 Então, nós tivemos um mapeamento entre entradas, que são cordas, eo hash 223 00:10:02,490 --> 00:10:04,560 lugares, que são números. 224 00:10:04,560 --> 00:10:07,740 >> Assim que o processo é geralmente conhecido como uma função de hash, e você pode realmente 225 00:10:07,740 --> 00:10:09,130 implementá-lo em código. 226 00:10:09,130 --> 00:10:12,080 Se eu quisesse implementar uma função hash que faz exatamente o que nós 227 00:10:12,080 --> 00:10:17,070 acabamos de descrever da última vez, eu poderia declarar uma função que recebe como 228 00:10:17,070 --> 00:10:18,330 entrada, por exemplo - 229 00:10:18,330 --> 00:10:22,190 e vamos fazer isso neste tela aqui. 230 00:10:22,190 --> 00:10:26,180 Se eu quisesse implementar um hash função, eu poderia dizer 231 00:10:26,180 --> 00:10:27,410 algo como isto. 232 00:10:27,410 --> 00:10:29,030 >> Vai retornar um int. 233 00:10:29,030 --> 00:10:33,600 Vai ser chamado de hash, e é vai aceitar como argumento um 234 00:10:33,600 --> 00:10:38,920 string, ou podemos ser mais adequado agora, e dizer char *, vamos chamá-lo s. 235 00:10:38,920 --> 00:10:43,840 E então, essa função tem que fazer, em última instância, é retornar um int. 236 00:10:43,840 --> 00:10:45,990 Agora, como ele faz isso pode não ser tão clara. 237 00:10:45,990 --> 00:10:49,510 Vou implementar isso sem qualquer forma de verificação de erros no momento. 238 00:10:49,510 --> 00:10:55,740 Eu só vou dizer cegamente, o retorno o que estiver à s suporte 0, menos, 239 00:10:55,740 --> 00:10:58,850 vamos dizer, o capital Um ponto e vírgula. 240 00:10:58,850 --> 00:10:59,960 >> Totalmente quebrado. 241 00:10:59,960 --> 00:11:02,620 Não é perfeito, porque um, o que se s é nulo? 242 00:11:02,620 --> 00:11:04,000 Coisas ruins vão acontecer. 243 00:11:04,000 --> 00:11:07,940 Dois, e se a primeira letra neste nome não é uma letra maiúscula? 244 00:11:07,940 --> 00:11:09,860 Isso não vai virar sair bem também. 245 00:11:09,860 --> 00:11:11,970 Pode ser uma letra minúscula ou não uma carta a todos. 246 00:11:11,970 --> 00:11:15,520 Então, totalmente espaço para melhorias aqui, mas essa é a idéia básica. 247 00:11:15,520 --> 00:11:19,010 >> O que descreveu na semana passada como verbalmente apenas um processo de mapeamento de Alice 248 00:11:19,010 --> 00:11:23,360 0 e Bob 1 pode ser expressa certamente mais formulaically como C 249 00:11:23,360 --> 00:11:24,320 funcionar aqui. 250 00:11:24,320 --> 00:11:28,630 Chamado novamente hash recebe uma string como entrada e de alguma forma faz algo 251 00:11:28,630 --> 00:11:31,020 com o que a entrada para produzir uma saída. 252 00:11:31,020 --> 00:11:34,130 Não muito diferente de nossa descrição da caixa negra que temos feito muito. 253 00:11:34,130 --> 00:11:36,550 Eu não sei como isso pode ser trabalhando debaixo do capô. 254 00:11:36,550 --> 00:11:40,120 >> Por conjunto de problemas 6, um dos desafios é para você decidir o que 255 00:11:40,120 --> 00:11:41,920 será a sua função hash ser? 256 00:11:41,920 --> 00:11:45,760 O que vai estar dentro do que o preto caixa e, presumivelmente, vai ser um 257 00:11:45,760 --> 00:11:50,380 pouco mais interessante do que isso, e definitivamente mais propenso a erros 258 00:11:50,380 --> 00:11:53,180 verificando que este particular implementação. 259 00:11:53,180 --> 00:11:54,580 >> Mas podem surgir problemas, certo? 260 00:11:54,580 --> 00:11:57,760 Se tivermos uma estrutura de dados, tal como esta um, que é um dos problemas 261 00:11:57,760 --> 00:12:01,600 você pode executar ao longo do tempo em que insere mais e mais nomes no 262 00:12:01,600 --> 00:12:02,880 tabela hash? 263 00:12:02,880 --> 00:12:04,630 Você começa colisões, certo? 264 00:12:04,630 --> 00:12:07,560 E se você tem Alice e Aaron, duas pessoas cujos nomes aconteceu 265 00:12:07,560 --> 00:12:08,190 começar com um? 266 00:12:08,190 --> 00:12:11,660 Isso levanta a questão, onde colocar o segundo como um nome? 267 00:12:11,660 --> 00:12:15,050 >> Bem, você pode, ingenuamente, basta colocá-lo onde Bob pertence, mas, em seguida, Bob é 268 00:12:15,050 --> 00:12:17,300 tipo de ferrado se você tentar insira o seu nome ao lado e 269 00:12:17,300 --> 00:12:18,240 não há espaço para ele. 270 00:12:18,240 --> 00:12:21,400 Então você pode colocar Bob onde Charlie é, e você pode imaginar isso muito rapidamente 271 00:12:21,400 --> 00:12:23,020 devolvendo em um pouco de confusão. 272 00:12:23,020 --> 00:12:25,600 Algo linear, no final, onde você apenas tem que procurar a coisa toda 273 00:12:25,600 --> 00:12:28,190 à procura de Alice ou Bob ou Aaron ou Charlie. 274 00:12:28,190 --> 00:12:33,230 >> Então, em vez disso, propôs, em vez de apenas linearmente sondagem para espaços abertos 275 00:12:33,230 --> 00:12:36,450 e estatelando os nomes lá, nós propôs uma abordagem mais extravagante. 276 00:12:36,450 --> 00:12:41,740 Uma tabela implementada ainda com um gama de índices, mas o tipo de dados 277 00:12:41,740 --> 00:12:44,500 esses índices eram agora ponteiros. 278 00:12:44,500 --> 00:12:47,360 Ponteiros para quê? 279 00:12:47,360 --> 00:12:48,730 Ponteiros para listas ligadas. 280 00:12:48,730 --> 00:12:53,330 >> Porque lembram que uma lista ligada é na verdade, apenas um ponteiro para um nó, e 281 00:12:53,330 --> 00:12:57,110 o nó tem um campo seguinte, e que o nó tem um campo seguinte, e assim por diante. 282 00:12:57,110 --> 00:13:00,690 Então, agora você pode pensar dessa matriz em o lado esquerdo de uma tabela de Hash 283 00:13:00,690 --> 00:13:01,820 levando a uma lista ligada. 284 00:13:01,820 --> 00:13:07,000 A vantagem é que se você pegar um colisão entre Alice e Aaron, 285 00:13:07,000 --> 00:13:09,300 O que você faz com o segundo tal pessoa? 286 00:13:09,300 --> 00:13:14,150 Você acabou de ligar-lhe para o extremidade, ou mesmo o início 287 00:13:14,150 --> 00:13:15,490 dessa lista ligada. 288 00:13:15,490 --> 00:13:17,340 >> E na verdade, vamos apenas através de macarrão que por apenas um segundo. 289 00:13:17,340 --> 00:13:18,640 Onde faria mais sentido? 290 00:13:18,640 --> 00:13:22,060 Se eu inserir Alice e ela acaba em a primeira posição, então eu tento 291 00:13:22,060 --> 00:13:25,310 inserir o nome de Aaron, e não há obviamente uma colisão, devo colocar 292 00:13:25,310 --> 00:13:27,400 ele no início da lista ligada? 293 00:13:27,400 --> 00:13:30,944 Isso é pelo que a primeira localização, ou no final? 294 00:13:30,944 --> 00:13:31,440 >> AUDIÊNCIA: [inaudível]. 295 00:13:31,440 --> 00:13:31,990 >> DAVID MALAN: OK. 296 00:13:31,990 --> 00:13:32,490 Ouvi começando. 297 00:13:32,490 --> 00:13:33,903 Por que no início? 298 00:13:33,903 --> 00:13:34,750 >> AUDIÊNCIA: [inaudível]. 299 00:13:34,750 --> 00:13:34,940 >> DAVID MALAN: OK. 300 00:13:34,940 --> 00:13:36,520 É alfabética, de modo que é bom. 301 00:13:36,520 --> 00:13:37,330 Essa é uma boa propriedade. 302 00:13:37,330 --> 00:13:39,335 Ele vai me poupar algum tempo potencialmente. 303 00:13:39,335 --> 00:13:43,290 Ele não vai me deixar fazer busca binária, mas eu pode pelo menos ser capaz de sair 304 00:13:43,290 --> 00:13:47,340 de um loop, se eu perceber, bem, eu sou muito passado eram Aaron estaria nesta 305 00:13:47,340 --> 00:13:48,310 classificadas lista encadeada. 306 00:13:48,310 --> 00:13:50,360 Eu não tenho que perder meu tempo procurando todo o caminho até ao fim. 307 00:13:50,360 --> 00:13:51,530 Então, isso é razoável. 308 00:13:51,530 --> 00:13:54,710 Por que mais pode desejar inserir o nome colidindo no 309 00:13:54,710 --> 00:13:56,660 início da lista? 310 00:13:56,660 --> 00:13:57,397 O que é isso? 311 00:13:57,397 --> 00:13:58,680 >> AUDIÊNCIA: [inaudível]. 312 00:13:58,680 --> 00:14:00,820 >> DAVID MALAN: Pode levar um longo tempo a chegar ao fim da lista. 313 00:14:00,820 --> 00:14:02,490 E, na verdade, mais e mais. 314 00:14:02,490 --> 00:14:04,920 Quanto mais nomes que você insere Comece com uma, mais que 315 00:14:04,920 --> 00:14:06,280 cadeia vai ficar. 316 00:14:06,280 --> 00:14:07,890 Quanto mais tempo que ligava lista vai ficar. 317 00:14:07,890 --> 00:14:09,420 Então você é realmente apenas desperdiçando seu tempo. 318 00:14:09,420 --> 00:14:14,070 Talvez você seja melhor manter tempo de inserção constante, grande O de 1, 319 00:14:14,070 --> 00:14:18,470 por sempre colocando o nome de colidir em o início da lista encadeada, 320 00:14:18,470 --> 00:14:21,230 e não se preocupar tanto sobre a classificação. 321 00:14:21,230 --> 00:14:22,600 >> Qual é a melhor resposta? 322 00:14:22,600 --> 00:14:23,320 Não está claro. 323 00:14:23,320 --> 00:14:26,140 É o tipo de depende do que o a distribuição é, qual é o padrão é 324 00:14:26,140 --> 00:14:27,850 dos nomes que você está inserindo. 325 00:14:27,850 --> 00:14:29,430 Não é necessariamente uma resposta óbvia. 326 00:14:29,430 --> 00:14:33,100 Mas aqui, mais uma vez, é uma oportunidade de design. 327 00:14:33,100 --> 00:14:37,220 >> Então, em seguida, olhou para essa coisa, que é realmente a outra grande oportunidade 328 00:14:37,220 --> 00:14:38,180 para o p-conjunto 6. 329 00:14:38,180 --> 00:14:41,770 E perceber, se você não tiver já, Zamyla mergulha ambos, hash 330 00:14:41,770 --> 00:14:43,260 mesas e tenta, de forma mais detalhada. 331 00:14:43,260 --> 00:14:45,630 E o passo a passo de vídeo é incorporado em conjunto p-spec. 332 00:14:45,630 --> 00:14:46,590 Este foi um trie - 333 00:14:46,590 --> 00:14:51,670 T-R-I-E. E o que era interessante sobre isto era que o tempo de execução 334 00:14:51,670 --> 00:14:59,510 de procurar um nome, como Maxwell última vez, era grande O de quê? 335 00:14:59,510 --> 00:15:01,040 O que é isso? 336 00:15:01,040 --> 00:15:01,920 >> AUDIÊNCIA: O número de letras. 337 00:15:01,920 --> 00:15:02,550 >> DAVID MALAN: Número de letras. 338 00:15:02,550 --> 00:15:03,210 Ouvi duas coisas. 339 00:15:03,210 --> 00:15:04,630 Número de letras e de tempo constante. 340 00:15:04,630 --> 00:15:05,540 Então vamos com a primeira. 341 00:15:05,540 --> 00:15:06,410 O número de letras. 342 00:15:06,410 --> 00:15:10,195 Bem, esta estrutura de dados, aviso, é como uma árvore, uma árvore de família, cada um dos 343 00:15:10,195 --> 00:15:12,860 nós cujas são feitas de matrizes. 344 00:15:12,860 --> 00:15:16,300 E essas matrizes são ponteiros para outros tais nós, ou outras, tais 345 00:15:16,300 --> 00:15:17,670 matrizes na árvore. 346 00:15:17,670 --> 00:15:22,890 >> Então, se nós queríamos, então, determinar Maxwell se está aqui, eu poderia ir 347 00:15:22,890 --> 00:15:26,890 para a primeira matriz, no topo de a árvore, o chamado raiz, topo 348 00:15:26,890 --> 00:15:30,521 o trie, e então siga o ponteiro m, em seguida, a um ponteiro, então x, 349 00:15:30,521 --> 00:15:31,710 W, E, L, L. 350 00:15:31,710 --> 00:15:34,910 E então quando eu vejo algum símbolo especial, denotado aqui como um triângulo. 351 00:15:34,910 --> 00:15:38,480 No código você verá que nós propomos que você implementado como um bool, apenas dizendo sim 352 00:15:38,480 --> 00:15:40,540 ou não, a palavra pára aqui. 353 00:15:40,540 --> 00:15:45,270 >> Bem, uma vez que fui para a M-A-X-W-E-L-L, Parece que sete, talvez 354 00:15:45,270 --> 00:15:48,910 oito se formos um passado, oito passos para encontrar Maxwell. 355 00:15:48,910 --> 00:15:53,050 Ou vamos chamá-lo K. Mas lembre-se passado vez, argumentou que, se há 356 00:15:53,050 --> 00:15:57,540 realisticamente um comprimento máximo numa palavra, como alguns personagens de 40 e tantos, um 357 00:15:57,540 --> 00:16:00,810 comprimento máximo implica um valor constante. 358 00:16:00,810 --> 00:16:05,770 Então, realmente, sim, é tecnicamente grande O de 8 ou 7, ou realmente grande O de K. Mas 359 00:16:05,770 --> 00:16:09,420 se há um limite finito em que K pode ser, é uma constante. 360 00:16:09,420 --> 00:16:12,080 E por isso é grande O de 1 a no final do dia. 361 00:16:12,080 --> 00:16:13,040 >> Não no mundo real. 362 00:16:13,040 --> 00:16:15,960 Não quando você realmente começar a assistir o relógio de corrida do seu programa. 363 00:16:15,960 --> 00:16:20,690 É absolutamente vai ser um pouco mais lento do que verdadeiramente constante 364 00:16:20,690 --> 00:16:21,840 tempo com uma única etapa. 365 00:16:21,840 --> 00:16:25,540 Vai ser sete ou oito etapas, mas ainda é muito, muito melhor 366 00:16:25,540 --> 00:16:30,080 que um algoritmo como ó grande de n que depende do tamanho do que está no 367 00:16:30,080 --> 00:16:31,220 estrutura de dados. 368 00:16:31,220 --> 00:16:34,970 >> Observe a cabeça aqui é que podemos inserir mais um milhão de nomes para este 369 00:16:34,970 --> 00:16:38,170 estrutura de dados, mas quantos mais passos é ele que vai nos levar a encontrar 370 00:16:38,170 --> 00:16:40,480 Maxwell, neste caso? 371 00:16:40,480 --> 00:16:40,780 Nenhum. 372 00:16:40,780 --> 00:16:41,820 Ele é afetado. 373 00:16:41,820 --> 00:16:45,480 E até agora, eu não acho que nós vimos um exemplo de uma estrutura de dados ou um 374 00:16:45,480 --> 00:16:48,560 algoritmo que foi completamente afetado por fatores externos 375 00:16:48,560 --> 00:16:50,040 comportamentos como esse. 376 00:16:50,040 --> 00:16:51,160 Mas isso não pode ser incrível. 377 00:16:51,160 --> 00:16:52,900 Esta não pode ser a única solução para o p-conjunto 378 00:16:52,900 --> 00:16:53,570 >> E não é. 379 00:16:53,570 --> 00:16:55,980 Esta não é, necessariamente, os dados estrutura deve gravitar para, 380 00:16:55,980 --> 00:16:58,220 porque, como tabelas de hash, tradeoff. 381 00:16:58,220 --> 00:17:00,500 Qual é o preço que se paga aqui? 382 00:17:00,500 --> 00:17:00,940 Memória. 383 00:17:00,940 --> 00:17:02,890 Quero dizer, isso é uma atroz quantidade de memória. 384 00:17:02,890 --> 00:17:05,569 E você não consegue vê-lo aqui, porque o autor da imagem 385 00:17:05,569 --> 00:17:09,420 obviamente truncado todas as matrizes, e nós não estamos vendo muitas A e 386 00:17:09,420 --> 00:17:12,700 B e C e do Q e Y e Z do nestas matrizes. 387 00:17:12,700 --> 00:17:13,630 Mas eles estão lá. 388 00:17:13,630 --> 00:17:17,660 >> Cada um destes nós é uma matriz inteira de cerca de 26 ou mais bytes, cada um dos 389 00:17:17,660 --> 00:17:19,170 que representa uma letra. 390 00:17:19,170 --> 00:17:22,920 27 em nosso caso, para que possamos apoiar apóstrofos no conjunto de problemas. 391 00:17:22,920 --> 00:17:27,030 Portanto, esta estrutura de dados é, na verdade, realmente densa e ampla. 392 00:17:27,030 --> 00:17:30,880 E isso só pode acabar retardando as coisas, ou pelo menos lhe custar uma 393 00:17:30,880 --> 00:17:32,240 muito mais espaço. 394 00:17:32,240 --> 00:17:34,020 Mas, novamente, podemos extrair comparações aqui. 395 00:17:34,020 --> 00:17:39,190 >> Lembre-se de um tempo atrás, nós conseguimos muito tempo de corrida mais emocionante na classificação 396 00:17:39,190 --> 00:17:42,880 quando usamos merge sort, mas o preço pagamos para alcançar n log n para fusão 397 00:17:42,880 --> 00:17:46,930 tipo exigido que nós gastamos mais que recurso? 398 00:17:46,930 --> 00:17:47,690 Mais espaço. 399 00:17:47,690 --> 00:17:50,530 Precisávamos de uma matriz secundária a copiar as pessoas para, assim como 400 00:17:50,530 --> 00:17:51,620 fizemos aqui no palco. 401 00:17:51,620 --> 00:17:55,880 Então, novamente, há claros vencedores, mas apenas projeto subjetiva 402 00:17:55,880 --> 00:17:57,710 decisões a serem tomadas. 403 00:17:57,710 --> 00:17:58,060 >> Tudo bem. 404 00:17:58,060 --> 00:17:59,130 Então, que tal isso? 405 00:17:59,130 --> 00:18:02,050 Qualquer pessoa reconhecer que D-Hall? 406 00:18:02,050 --> 00:18:02,440 OK. 407 00:18:02,440 --> 00:18:03,170 Assim, três de nós. 408 00:18:03,170 --> 00:18:03,750 Mather House. 409 00:18:03,750 --> 00:18:05,070 Portanto, esta é para um jantar de Mather. 410 00:18:05,070 --> 00:18:09,650 Aposto que todas as salas de jantar têm pilhas de bandejas como este. 411 00:18:09,650 --> 00:18:11,950 E isso é realmente representativo de algo que já 412 00:18:11,950 --> 00:18:13,050 obviamente, já visto. 413 00:18:13,050 --> 00:18:14,850 Chamámos-lhe, literalmente, uma pilha. 414 00:18:14,850 --> 00:18:18,970 E a pilha, em termos da sua memória do computador, é onde os dados vão 415 00:18:18,970 --> 00:18:20,460 enquanto as funções estão sendo chamados. 416 00:18:20,460 --> 00:18:23,410 >> Por exemplo, que tipo de coisas vão na pilha com respeito ao 417 00:18:23,410 --> 00:18:27,420 layout de memória que discutimos nas últimas semanas? 418 00:18:27,420 --> 00:18:28,736 O que é isso? 419 00:18:28,736 --> 00:18:29,670 >> AUDIÊNCIA: Chamadas para funções. 420 00:18:29,670 --> 00:18:30,260 >> DAVID MALAN: Eu sinto muito. 421 00:18:30,260 --> 00:18:31,210 >> AUDIÊNCIA: Chamadas para funções. 422 00:18:31,210 --> 00:18:33,590 >> DAVID MALAN: Chamadas para funções, mas especificamente, o que está dentro de cada um 423 00:18:33,590 --> 00:18:35,340 esses quadros? 424 00:18:35,340 --> 00:18:37,220 Que tipo de coisas? 425 00:18:37,220 --> 00:18:37,460 Sim. 426 00:18:37,460 --> 00:18:38,500 Assim, as variáveis ​​locais. 427 00:18:38,500 --> 00:18:43,080 Sempre que precisávamos de algum armazenamento local, como um argumento, ou int I, ou int 428 00:18:43,080 --> 00:18:45,940 temp, ou qualquer que seja o local de variável é, temos sido 429 00:18:45,940 --> 00:18:47,210 colocando que na pilha. 430 00:18:47,210 --> 00:18:49,610 E chamamos isso de uma pilha porque dessa idéia de estratificação. 431 00:18:49,610 --> 00:18:52,940 Apenas um tipo de jogos com realidade, o conceito da mesma. 432 00:18:52,940 --> 00:18:56,650 >> Mas acontece que uma pilha pode também ser visto como uma estrutura de dados, um 433 00:18:56,650 --> 00:19:00,110 alternativa a uma matriz, uma alternativa para uma lista ligada. 434 00:19:00,110 --> 00:19:02,770 Algo conceitualmente mais interessante que pode ainda ser 435 00:19:02,770 --> 00:19:06,030 implementado usando um desses coisas, mas é um tipo diferente de 436 00:19:06,030 --> 00:19:09,140 estrutura de dados de apoio, realmente, apenas duas operações. 437 00:19:09,140 --> 00:19:11,000 Mas você pode adicionar mais sofisticado características do que estes. 438 00:19:11,000 --> 00:19:12,180 Mas estes são os princípios básicos - 439 00:19:12,180 --> 00:19:13,510 push e pop. 440 00:19:13,510 --> 00:19:19,240 >> E a idéia com uma pilha é que se eu tem aqui, com ou sem Annenberg 441 00:19:19,240 --> 00:19:22,880 saber, uma bandeja ao lado com o número 9 nele. 442 00:19:22,880 --> 00:19:23,870 Então, basta um int. 443 00:19:23,870 --> 00:19:26,990 E eu quero empurrar este para os dados estrutura, que atualmente está vazio. 444 00:19:26,990 --> 00:19:28,790 Considerar este o fundo da pilha. 445 00:19:28,790 --> 00:19:33,150 Eu levaria esse número 9 para o empilhar, e agora ele está lá. 446 00:19:33,150 --> 00:19:36,040 >> Mas a coisa interessante sobre uma pilha é que se eu agora quer empurrar 447 00:19:36,040 --> 00:19:40,210 algum outro valor, como 17 anos, e eu empurro esta na pilha, eu vou fazer 448 00:19:40,210 --> 00:19:43,290 a única coisa intuitiva, eu só vou para colocá-lo exatamente onde nós, seres humanos 449 00:19:43,290 --> 00:19:45,180 estaria inclinado a colocá-lo, no topo. 450 00:19:45,180 --> 00:19:48,850 Mas o que é interessante agora é, como faço para chegar a 9? 451 00:19:48,850 --> 00:19:50,670 Você sabe, eu não sem algum esforço. 452 00:19:50,670 --> 00:19:54,070 >> Então, o que é interessante sobre uma pilha é que, ao design, 453 00:19:54,070 --> 00:19:56,330 é uma estrutura de dados LIFO. 454 00:19:56,330 --> 00:19:59,680 Estranha maneira de descrever last in, first out. 455 00:19:59,680 --> 00:20:03,280 Assim, o último número na nesta época tinha 17 anos. 456 00:20:03,280 --> 00:20:07,540 Então, se eu quiser aparecer algo fora da pilha, que só pode ser 17. 457 00:20:07,540 --> 00:20:11,890 Portanto, há uma ordem obrigatória de operações aqui, onde o último item 458 00:20:11,890 --> 00:20:14,260 em tem que ser o primeiro a sair. 459 00:20:14,260 --> 00:20:16,440 Daí a sigla, LIFO. 460 00:20:16,440 --> 00:20:19,160 >> Então, por que isso pode ser útil? 461 00:20:19,160 --> 00:20:22,690 São os seus contextos em que você tinha quer uma estrutura de dados como este? 462 00:20:22,690 --> 00:20:24,810 Bem, isso certamente foi útil no interior de um computador. 463 00:20:24,810 --> 00:20:29,050 Então, usar sistemas operacionais claramente esta tipo de estrutura de dados para stacks. 464 00:20:29,050 --> 00:20:32,800 Veremos também a mesma idéia quando se trata de páginas da web. 465 00:20:32,800 --> 00:20:35,890 Então, esta semana e na próxima semana e além, e como você começar a implementar web 466 00:20:35,890 --> 00:20:39,490 páginas em uma linguagem chamada HTML, você pode realmente usar uma estrutura de dados como 467 00:20:39,490 --> 00:20:42,690 isto para determinar se a página é formatada corretamente. 468 00:20:42,690 --> 00:20:47,170 Porque vamos ver todas as páginas seguem uma espécie de hierarquia, um recuo 469 00:20:47,170 --> 00:20:52,030 que, no final do dia, ser um estrutura de árvore debaixo do capô. 470 00:20:52,030 --> 00:20:53,620 Assim, mais do que em apenas um bit. 471 00:20:53,620 --> 00:20:56,560 >> Mas, por agora, vamos propor um momento, como poderíamos ir sobre 472 00:20:56,560 --> 00:20:58,830 representando o que é uma pilha? 473 00:20:58,830 --> 00:21:03,370 Deixe-me propor que implementamos uma pilha com um código como este. 474 00:21:03,370 --> 00:21:07,990 Assim, uma pilha vai ter dentro dela duas coisas, uma matriz, chamados de tabuleiros, 475 00:21:07,990 --> 00:21:09,510 apenas para ser coerente com o demo. 476 00:21:09,510 --> 00:21:12,660 E cada um dos itens dessa matriz vai ser um tipo int. 477 00:21:12,660 --> 00:21:14,740 Ea capacidade é presumivelmente o quê? 478 00:21:14,740 --> 00:21:18,796 Porque eu não tenho escrito o definição completa aqui. 479 00:21:18,796 --> 00:21:21,535 >> É, provavelmente, o máximo tamanho da matriz. 480 00:21:21,535 --> 00:21:25,150 E provavelmente é declarado como um forte definir, no topo do arquivo, alguns 481 00:21:25,150 --> 00:21:28,450 tipo de constante como implícito a mera capitalização. 482 00:21:28,450 --> 00:21:32,250 Assim, a capacidade é definida algures medida que o tamanho máximo possível. 483 00:21:32,250 --> 00:21:35,590 Enquanto isso, dentro da estrutura de dados conhecida como uma pilha haverá 484 00:21:35,590 --> 00:21:38,630 ser um número inteiro apenas conhecido simplesmente como tamanho. 485 00:21:38,630 --> 00:21:43,400 >> Então, se eu fosse para representar esta empresa pictoricamente, vamos supor que este 486 00:21:43,400 --> 00:21:48,070 Toda caixa preta representa a minha stack. 487 00:21:48,070 --> 00:21:50,070 Dentro de é duas variáveis. 488 00:21:50,070 --> 00:21:54,780 Então, eu vou chamar a como uma primeira dimensão. 489 00:21:54,780 --> 00:21:57,420 E o segundo que eu vou para desenhar como uma matriz. 490 00:21:57,420 --> 00:22:01,060 >> Mas apenas para manter as coisas em ordem, normalmente eu gostaria de chamar uma matriz como 491 00:22:01,060 --> 00:22:04,910 isso, mas é uma espécie de bom se corresponde à realidade, ou 492 00:22:04,910 --> 00:22:06,230 coincidir com o modelo mental. 493 00:22:06,230 --> 00:22:12,880 Então deixe-me em vez chamar a matriz verticalmente, o que é justo, mais uma vez, 494 00:22:12,880 --> 00:22:13,840 interpretação do artista. 495 00:22:13,840 --> 00:22:16,610 Realmente não importa o que está debaixo do capô. 496 00:22:16,610 --> 00:22:20,350 E vamos dizer que, por padrão, capacidade vai ser três. 497 00:22:20,350 --> 00:22:23,480 Portanto, este será local 0, este será de localização 1, o presente 498 00:22:23,480 --> 00:22:25,740 será localização 2. 499 00:22:25,740 --> 00:22:29,330 >> Se eu subornar com uma bola de stress, seria alguém que gosta de aparecer e executar o 500 00:22:29,330 --> 00:22:30,870 embarcar aqui por um momento? 501 00:22:30,870 --> 00:22:31,960 OK, vi o seu em primeira mão. 502 00:22:31,960 --> 00:22:33,950 Vamos para cima. 503 00:22:33,950 --> 00:22:36,500 Tudo bem. 504 00:22:36,500 --> 00:22:38,760 Então, eu acredito que é Steven. 505 00:22:38,760 --> 00:22:40,035 Vamos para cima. 506 00:22:40,035 --> 00:22:40,770 Tudo bem. 507 00:22:40,770 --> 00:22:46,760 >> Mas suponha agora que voltar à inicial estado do mundo onde eu 508 00:22:46,760 --> 00:22:52,180 apenas declararam uma pilha, e é vai ter uma capacidade de três. 509 00:22:52,180 --> 00:22:54,470 Mas o tamanho ainda não foi determinada. 510 00:22:54,470 --> 00:22:56,100 Bandejas ainda não foi determinada. 511 00:22:56,100 --> 00:22:57,300 Assim, um par de perguntas em primeiro lugar. 512 00:22:57,300 --> 00:23:01,310 E deixe-me dar-lhe microfone para que você possa participar mais ativamente neste processo. 513 00:23:01,310 --> 00:23:05,190 >> Então, o que está dentro do tamanho neste momento no tempo, se tudo o que eu tenho feito é 514 00:23:05,190 --> 00:23:09,340 declarou uma pilha com uma linha de código? 515 00:23:09,340 --> 00:23:10,100 >> STEVEN: Não muito. 516 00:23:10,100 --> 00:23:12,080 >> DAVID MALAN: OK, não muito. 517 00:23:12,080 --> 00:23:14,410 Não sabemos o que está dentro do tamanho, sabemos o que está dentro 518 00:23:14,410 --> 00:23:16,330 dessa matriz aqui? 519 00:23:16,330 --> 00:23:18,630 >> STEVEN: Apenas código aleatório, certo? 520 00:23:18,630 --> 00:23:20,220 Just - 521 00:23:20,220 --> 00:23:23,230 >> DAVID MALAN: Sim, eu vou chamá-lo de código, mas aleatória - 522 00:23:23,230 --> 00:23:23,820 >> STEVEN: Coisas. 523 00:23:23,820 --> 00:23:28,290 >> DAVID MALAN: Coisas como aleatório 524 00:23:28,290 --> 00:23:28,870 >> STEVEN: Bits. 525 00:23:28,870 --> 00:23:29,530 >> DAVID MALAN: Bits, certo? 526 00:23:29,530 --> 00:23:31,190 Assim, os valores de lixo, certo? 527 00:23:31,190 --> 00:23:33,470 Então permutações de 0 e 1 do. 528 00:23:33,470 --> 00:23:35,920 Restos de usos anteriores desta memória. 529 00:23:35,920 --> 00:23:38,150 E nós realmente não sei quais são os valores são, por isso, normalmente atraí-los 530 00:23:38,150 --> 00:23:38,930 como pontos de interrogação. 531 00:23:38,930 --> 00:23:41,990 >> Então a primeira coisa que estamos presumivelmente vai querer fazer aqui - 532 00:23:41,990 --> 00:23:46,630 e deixe-me dar esse campo dentro de lá um nome - bandejas. 533 00:23:46,630 --> 00:23:49,540 O que devemos presumivelmente inicializar tamanho para se queremos 534 00:23:49,540 --> 00:23:51,040 começar a usar esta pilha? 535 00:23:51,040 --> 00:23:53,070 >> STEVEN: Bandeja é sub 3. 536 00:23:53,070 --> 00:23:53,910 >> DAVID MALAN: Então, OK. 537 00:23:53,910 --> 00:23:56,710 Para ser claro, a capacidade é declarado em outros lugares como três. 538 00:23:56,710 --> 00:23:58,570 E isso é o que eu usei para atribuir a matriz. 539 00:23:58,570 --> 00:24:03,535 Tamanho vai referir quantos bandejas são actualmente na pilha. 540 00:24:03,535 --> 00:24:03,880 >> STEVEN: Zero. 541 00:24:03,880 --> 00:24:04,460 >> DAVID MALAN: Assim deve ser zero. 542 00:24:04,460 --> 00:24:07,760 Então vá em frente, e com qualquer dedo, tirar um zero em tamanho. 543 00:24:07,760 --> 00:24:08,440 Tudo bem. 544 00:24:08,440 --> 00:24:10,920 Então, agora, o que está dentro desse aqui, nós não sabemos. 545 00:24:10,920 --> 00:24:12,160 Estes são realmente apenas valores de lixo. 546 00:24:12,160 --> 00:24:14,800 Então, nós poderíamos extrair pontos de interrogação, mas vamos manter a placa limpa, por enquanto 547 00:24:14,800 --> 00:24:16,300 porque não importa o que está lá. 548 00:24:16,300 --> 00:24:19,130 Nós não precisamos de inicializar a matriz para nada, porque, se sabemos que 549 00:24:19,130 --> 00:24:23,100 o tamanho da pilha é igual a zero, também, nós não deve estar olhando para nada em 550 00:24:23,100 --> 00:24:25,590 essa matriz de qualquer maneira em Neste ponto no tempo. 551 00:24:25,590 --> 00:24:29,970 >> Então, suponha que eu empurrar o o número 9 na pilha. 552 00:24:29,970 --> 00:24:33,750 Como devemos atualizar a estrutura de dados dentro desta caixa preta? 553 00:24:33,750 --> 00:24:35,540 Quais valores precisam mudar? 554 00:24:35,540 --> 00:24:36,200 >> STEVEN: Dentro - 555 00:24:36,200 --> 00:24:37,400 o tamanho? 556 00:24:37,400 --> 00:24:37,650 >> DAVID MALAN: OK. 557 00:24:37,650 --> 00:24:38,770 Tamanho deve tornar-se o quê? 558 00:24:38,770 --> 00:24:39,580 >> STEVEN: Size seria um. 559 00:24:39,580 --> 00:24:39,870 >> DAVID MALAN: OK. 560 00:24:39,870 --> 00:24:41,110 Assim, o tamanho que se tornam um. 561 00:24:41,110 --> 00:24:42,540 Assim, você pode fazer isso de algumas maneiras. 562 00:24:42,540 --> 00:24:46,920 Deixe-me dar-lhe, agora o seu dedo é uma borracha. 563 00:24:46,920 --> 00:24:47,260 Tudo bem. 564 00:24:47,260 --> 00:24:49,960 Então agora o seu dedo é um pincel. 565 00:24:49,960 --> 00:24:50,330 Tudo bem. 566 00:24:50,330 --> 00:24:52,820 E agora, o que mais tem que mudar, obviamente, na estrutura de dados? 567 00:24:52,820 --> 00:24:57,060 >> STEVEN: Nós vamos a partir de de baixo para cima a 9. 568 00:24:57,060 --> 00:24:57,760 >> DAVID MALAN: 9. 569 00:24:57,760 --> 00:24:58,420 OK, Good. 570 00:24:58,420 --> 00:25:01,550 Então, ainda não importa o que está em localização de um ou dois, porque eles são 571 00:25:01,550 --> 00:25:04,520 valores de lixo, mas não deve se preocupar olhando lá porque o tamanho é 572 00:25:04,520 --> 00:25:07,540 dizer-nos que só o primeiro elemento é realmente legítimo. 573 00:25:07,540 --> 00:25:10,400 Então agora eu empurrar 17 na lista. 574 00:25:10,400 --> 00:25:11,830 O que acontece com esta imagem? 575 00:25:11,830 --> 00:25:14,720 >> STEVEN: So tamanho está indo para ir a dois. 576 00:25:14,720 --> 00:25:15,300 >> DAVID MALAN: OK. 577 00:25:15,300 --> 00:25:16,070 Você está eraser - 578 00:25:16,070 --> 00:25:16,810 oops. 579 00:25:16,810 --> 00:25:18,026 Você é uma borracha. 580 00:25:18,026 --> 00:25:18,840 >> STEVEN: Eraser. 581 00:25:18,840 --> 00:25:19,720 >> DAVID MALAN: Você é um pincel. 582 00:25:19,720 --> 00:25:20,560 >> STEVEN: Brush. 583 00:25:20,560 --> 00:25:20,920 >> DAVID MALAN: OK. 584 00:25:20,920 --> 00:25:21,600 E o que mais? 585 00:25:21,600 --> 00:25:22,600 >> STEVEN: E então nós - 586 00:25:22,600 --> 00:25:22,915 >> DAVID MALAN: Nós empurramos 17. 587 00:25:22,915 --> 00:25:24,760 >> STEVEN: Nós furamos 17 em cima, por isso - 588 00:25:24,760 --> 00:25:25,710 >> DAVID MALAN: OK, muito bom. 589 00:25:25,710 --> 00:25:27,040 >> STEVEN: - deixa-lo cair. 590 00:25:27,040 --> 00:25:27,530 >> DAVID MALAN: Tudo bem. 591 00:25:27,530 --> 00:25:27,940 Está ficando mais fácil. 592 00:25:27,940 --> 00:25:29,300 Eu não estou indo para ajudá-lo neste momento. 593 00:25:29,300 --> 00:25:30,510 Empurre 22. 594 00:25:30,510 --> 00:25:31,720 >> STEVEN: Concluído. 595 00:25:31,720 --> 00:25:34,870 Tornando-se uma borracha. 596 00:25:34,870 --> 00:25:37,340 Estou me tornando um pincel. 597 00:25:37,340 --> 00:25:39,340 E então eu estou colocando 22. 598 00:25:39,340 --> 00:25:40,100 >> DAVID MALAN: 22. 599 00:25:40,100 --> 00:25:40,620 Excelente. 600 00:25:40,620 --> 00:25:41,380 Assim, mais uma vez. 601 00:25:41,380 --> 00:25:44,280 Agora estou indo para empurrar para a pilha 26. 602 00:25:44,280 --> 00:25:46,350 >> STEVEN: Ooh. 603 00:25:46,350 --> 00:25:50,278 Oh Deus. 604 00:25:50,278 --> 00:25:52,520 Você realmente me pegou desprevenido. 605 00:25:52,520 --> 00:25:53,703 >> DAVID MALAN: Você não fez ver esta vinda? 606 00:25:53,703 --> 00:25:55,930 >> STEVEN: Eu não vi isso chegando. 607 00:25:55,930 --> 00:25:58,756 Poderíamos capacidade de re-inicial? 608 00:25:58,756 --> 00:25:59,790 >> DAVID MALAN: Essa é uma boa pergunta. 609 00:25:59,790 --> 00:26:02,360 Então, nós temos uma espécie de nós mesmos pintado em um canto aqui. 610 00:26:02,360 --> 00:26:06,740 Não há realmente nada de bom fora para Steven porque nós temos alocado essa matriz 611 00:26:06,740 --> 00:26:09,130 estaticamente, por assim dizer, dentro da estrutura de dados. 612 00:26:09,130 --> 00:26:12,170 E temos essencialmente codificado que seja de tamanho três. 613 00:26:12,170 --> 00:26:14,170 Portanto, não podemos realmente realocá-lo. 614 00:26:14,170 --> 00:26:20,020 >> Poderíamos se voltamos, nós redefinido bandejas para ser um ponteiro que 615 00:26:20,020 --> 00:26:22,300 Em seguida, usamos a memória malloc mão. 616 00:26:22,300 --> 00:26:25,050 Porque, se temos a memória de o monte via malloc, nós 617 00:26:25,050 --> 00:26:26,430 então poderia livrá-lo. 618 00:26:26,430 --> 00:26:29,630 Mas, antes de liberá-lo, poderíamos realocar uma fatia maior de memória, 619 00:26:29,630 --> 00:26:31,330 actualizar o ponteiro, e assim por diante. 620 00:26:31,330 --> 00:26:33,500 Mas, por enquanto, isso é realmente o melhor que podemos fazer. 621 00:26:33,500 --> 00:26:36,360 Push e pop são provavelmente vai ter para sinalizar um erro. 622 00:26:36,360 --> 00:26:40,270 >> Assim, por exemplo, a nossa implementação de impulso poderia retornar um booleano que 623 00:26:40,270 --> 00:26:42,390 previamente retornado verdade, verdade, verdade. 624 00:26:42,390 --> 00:26:48,390 Mas, pela quarta vez, ele vai ter para retornar false, por exemplo. 625 00:26:48,390 --> 00:26:48,540 Tudo bem. 626 00:26:48,540 --> 00:26:49,540 Muito bem feito. 627 00:26:49,540 --> 00:26:50,060 Parabéns. 628 00:26:50,060 --> 00:26:52,160 Você ganhou sua bola de stress hoje. 629 00:26:52,160 --> 00:26:53,110 >> [Aplausos] 630 00:26:53,110 --> 00:26:54,382 >> STEVEN: Obrigado. 631 00:26:54,382 --> 00:26:55,680 >> DAVID MALAN: Obrigado. 632 00:26:55,680 --> 00:26:59,740 OK, então isso parece não ser muito de um passo em frente, certo? 633 00:26:59,740 --> 00:27:01,410 Nós descrevemos esta estrutura de dados. 634 00:27:01,410 --> 00:27:02,320 Tem sido interessante, certo? 635 00:27:02,320 --> 00:27:03,200 Os sistemas operacionais gostar. 636 00:27:03,200 --> 00:27:06,360 Aparentemente, a web pode fazer uso desta, e outras aplicações ainda. 637 00:27:06,360 --> 00:27:10,870 Mas o que uma limitação estúpida que estamos voltar a uma espécie de semana dois limites 638 00:27:10,870 --> 00:27:12,880 onde se fixaram tamanho arrays. 639 00:27:12,880 --> 00:27:15,010 >> Portanto, há na verdade um par de formas que poderíamos resolver isso. 640 00:27:15,010 --> 00:27:18,750 Nós poderíamos alocar dinamicamente o array, não pelo difícil codificá-lo como eu 641 00:27:18,750 --> 00:27:22,600 feito aqui, mas re-declarando isso, só para ficar claro, como 642 00:27:22,600 --> 00:27:23,830 algo como isto. 643 00:27:23,830 --> 00:27:29,040 Int * bandejas, não decidir Ainda numa capacidade. 644 00:27:29,040 --> 00:27:35,460 Mas quando eu declarar a pilha em outro lugar no meu código, eu poderia então chamar malloc, 645 00:27:35,460 --> 00:27:38,250 obter o endereço de um pedaço de memória, e eu podia atribuir 646 00:27:38,250 --> 00:27:39,980 esse endereço para bandejas. 647 00:27:39,980 --> 00:27:43,340 >> E então, porque é apenas um pedaço de memória, eu poderia continuar a usar quadrado 648 00:27:43,340 --> 00:27:45,450 a notação de suporte da maneira usual. 649 00:27:45,450 --> 00:27:49,020 Porque mais uma vez, há uma espécie de presente equivalente funcional de matrizes e 650 00:27:49,020 --> 00:27:50,820 blocos de memória que vêm volta de malloc. 651 00:27:50,820 --> 00:27:53,090 Podemos tratar um como o outro usando a aritmética de ponteiro ou 652 00:27:53,090 --> 00:27:54,440 notação de colchete. 653 00:27:54,440 --> 00:27:55,660 Então essa é uma abordagem. 654 00:27:55,660 --> 00:28:00,120 >> Mas de que outra forma poderíamos implementar esta mesma estrutura de dados, podendo? 655 00:28:00,120 --> 00:28:00,280 Certo? 656 00:28:00,280 --> 00:28:04,530 Eu sinto que nós apenas resolveu este problema como há uma semana. 657 00:28:04,530 --> 00:28:08,860 Qual foi a solução para este problema que Steven correu? 658 00:28:08,860 --> 00:28:10,370 Listas ligadas entre si, certo. 659 00:28:10,370 --> 00:28:13,410 >> Se o problema é que estamos pintando nos para um canto, alocando 660 00:28:13,410 --> 00:28:17,580 antecipadamente muito pouca memória que em seguida, ter de lidar de alguma forma com o bem, 661 00:28:17,580 --> 00:28:19,880 porque não basta evitar que emitir por completo? 662 00:28:19,880 --> 00:28:26,170 Porque não basta declarar bandejas para ser um ponteiro para um nó, ergo uma lista ligada, 663 00:28:26,170 --> 00:28:30,740 e depois simplesmente alocar novos nós cada vez que Steven necessária para atender a uma 664 00:28:30,740 --> 00:28:32,400 Número na estrutura de dados. 665 00:28:32,400 --> 00:28:34,200 >> Assim, a imagem teria que mudar. 666 00:28:34,200 --> 00:28:38,220 Não vai ser tão limpo e tão simples como um conjunto de três inteiros. 667 00:28:38,220 --> 00:28:42,970 Agora vai ser um ponteiro para um struct, e que struct vai 668 00:28:42,970 --> 00:28:44,830 ter um int e um ponteiro próximo. 669 00:28:44,830 --> 00:28:47,670 Vai levar através desse ponteiro para outra estrutura para tal 670 00:28:47,670 --> 00:28:48,600 outro tal estrutura. 671 00:28:48,600 --> 00:28:50,560 Assim, o quadro seria realmente ficar um pouco mais confusa. 672 00:28:50,560 --> 00:28:52,950 E teríamos setas amarrando tudo juntos. 673 00:28:52,950 --> 00:28:55,280 >> Mas isso é bom, certo, porque vimos como fazer isso. 674 00:28:55,280 --> 00:28:58,180 E uma vez que você se sentir confortável implementar algo como um linked 675 00:28:58,180 --> 00:29:01,450 lista, que você vai ter que fazer se você optar por implementar uma tabela hash com 676 00:29:01,450 --> 00:29:05,120 encadeamento separado para p-set 6, você pode usá-lo como um bloco de construção, ou um 677 00:29:05,120 --> 00:29:08,870 ingrediente, ou em Scratch dizer, um procedimento, algo que você colocar, você 678 00:29:08,870 --> 00:29:12,560 criou sua própria peça do puzzle , que você pode reutilizar. 679 00:29:12,560 --> 00:29:17,090 Compensações que sim, mas as possíveis soluções que temos realmente visto antes. 680 00:29:17,090 --> 00:29:20,560 >> Então, muitas vezes, você vê isso todos os ano ou dois, quando lançamentos da Apple 681 00:29:20,560 --> 00:29:23,060 algo novo, e todas as pessoas loucas linha do lado de fora da Maçã 682 00:29:23,060 --> 00:29:27,050 loja para comprar seu marginal atualizar no hardware. 683 00:29:27,050 --> 00:29:30,420 Digo isso, está tudo bem, porque Eu sou uma dessas pessoas. 684 00:29:30,420 --> 00:29:35,140 Então, que tipo de estrutura de dados pode representar essa realidade? 685 00:29:35,140 --> 00:29:36,980 >> Bem, vamos chamá-lo de uma fila, uma linha. 686 00:29:36,980 --> 00:29:40,270 So British chamaria isso tipicamente um fila de qualquer jeito, por isso é um bom nome. 687 00:29:40,270 --> 00:29:44,960 E as duas operações que a fila apoia vamos chamar a enfileirar 688 00:29:44,960 --> 00:29:48,900 operação e uma operação de remoção da fila, que são semelhantes em 689 00:29:48,900 --> 00:29:50,120 espírito de push e pop. 690 00:29:50,120 --> 00:29:54,060 É apenas uma espécie de diferente em convenção, o que estamos chamando esses. 691 00:29:54,060 --> 00:29:57,680 Mas, para enfileirar algo significa para adicionar ou inseri-lo na estrutura de dados. 692 00:29:57,680 --> 00:29:59,570 Para desenfileirar meios para removê-lo. 693 00:29:59,570 --> 00:30:05,170 Mas, enquanto uma pilha era um dos dados LIFO estrutura, uma fila é um primeiro, 694 00:30:05,170 --> 00:30:06,740 pela primeira vez a estrutura de dados. 695 00:30:06,740 --> 00:30:10,050 >> Se você é a primeira pessoa na fila, você será a primeira pessoa a chegar 696 00:30:10,050 --> 00:30:12,420 fora da linha e comprar o seu novo dispositivo. 697 00:30:12,420 --> 00:30:18,070 Imagine o quão chateado essas pessoas seria se a Apple em vez usou uma pilha, para 698 00:30:18,070 --> 00:30:21,250 exemplo, para implementar a colheita up do seu novo brinquedo. 699 00:30:21,250 --> 00:30:24,310 Então filas fazem sentido, certamente, e podemos pensar em todos os tipos de 700 00:30:24,310 --> 00:30:27,480 aplicações, presumivelmente, para filas, especialmente quando você quer justiça. 701 00:30:27,480 --> 00:30:30,040 Então, como podemos implementá-las como uma estrutura de dados? 702 00:30:30,040 --> 00:30:33,680 >> Bem, eu proponho que possamos precisa fazê-lo desta forma. 703 00:30:33,680 --> 00:30:35,225 Então, eu vou agora ter números. 704 00:30:35,225 --> 00:30:38,190 Então, vamos manter as coisas simples e não necessariamente falar em termos de bandejas. 705 00:30:38,190 --> 00:30:40,220 Apenas números que as pessoas de começado. 706 00:30:40,220 --> 00:30:43,760 Capacidade vai, mais uma vez, corrigir o número total de pessoas que podem estar em 707 00:30:43,760 --> 00:30:46,900 Nesta linha, como três ou qualquer outro valor. 708 00:30:46,900 --> 00:30:50,760 >> Mas proponho que eu preciso para manter o controle não apenas do tamanho da 709 00:30:50,760 --> 00:30:52,370 fila, quantas coisas estão na mesma. 710 00:30:52,370 --> 00:30:56,310 Assim, o tamanho é o tamanho atual, a capacidade é o tamanho máximo. 711 00:30:56,310 --> 00:30:58,540 Assim de novo, a nomenclatura por convenção. 712 00:30:58,540 --> 00:31:03,680 Por que eu preciso de um int adicional dentro de uma fila para acompanhar o que está em 713 00:31:03,680 --> 00:31:05,365 frente da linha? 714 00:31:05,365 --> 00:31:07,930 715 00:31:07,930 --> 00:31:10,910 Por que eu preciso fazer isso neste caso? 716 00:31:10,910 --> 00:31:14,750 717 00:31:14,750 --> 00:31:16,190 >> Bem, como é esta imagem vai mudar? 718 00:31:16,190 --> 00:31:19,280 Eu provavelmente pode reutilizar mais da imagem. 719 00:31:19,280 --> 00:31:21,480 Deixe-me ir em frente e apagar o que está aqui. 720 00:31:21,480 --> 00:31:24,580 Nós vamos dar a este um pouco nome diferente aqui. 721 00:31:24,580 --> 00:31:28,930 Vamos nos livrar dos 17, vamos nos livrar do 9, vamos nos livrar do 3. 722 00:31:28,930 --> 00:31:30,410 E vamos adicionar uma outra coisa. 723 00:31:30,410 --> 00:31:34,710 Proponho que eu preciso para manter o controle de a frente da lista, que é apenas 724 00:31:34,710 --> 00:31:35,570 vai ser um int bem. 725 00:31:35,570 --> 00:31:36,550 E nós vamos mantê-lo simples. 726 00:31:36,550 --> 00:31:37,740 Nenhuma lista ligada por agora. 727 00:31:37,740 --> 00:31:40,900 >> Vamos admitir que vamos bater-se contra este limite. 728 00:31:40,900 --> 00:31:43,720 Mas o que eu quero ver acontecer desta vez? 729 00:31:43,720 --> 00:31:47,240 Então, suponhamos que eu vá em frente e no primeiro pessoa vem na linha, e 730 00:31:47,240 --> 00:31:48,560 é o número 9. 731 00:31:48,560 --> 00:31:49,680 Temos bolas de stress. 732 00:31:49,680 --> 00:31:51,330 Posso roubar, digamos, duas ou três pessoas? 733 00:31:51,330 --> 00:31:52,690 Um, dois, três? 734 00:31:52,690 --> 00:31:53,120 Vamos para cima. 735 00:31:53,120 --> 00:31:56,022 Direito de frente, porque nós vamos fazer este rápida. 736 00:31:56,022 --> 00:31:59,415 >> Cada um de vocês é agora vai ser um menino fã na fila da Apple. 737 00:31:59,415 --> 00:32:03,970 738 00:32:03,970 --> 00:32:06,210 Você não vai receber o hardware da Apple no final deste embora. 739 00:32:06,210 --> 00:32:06,500 Tudo bem. 740 00:32:06,500 --> 00:32:09,430 Então, você é o número 9, você está número 17, número 22. 741 00:32:09,430 --> 00:32:12,130 Estes são números arbitrários, como IDs de estudante ou outros enfeites. 742 00:32:12,130 --> 00:32:14,550 E em apenas um momento, vamos começar para começar a adicionar as coisas. 743 00:32:14,550 --> 00:32:16,000 E eu vou correr o conselho aqui neste momento. 744 00:32:16,000 --> 00:32:19,570 >> Portanto, neste caso, eu já inicializada a frente para ser - 745 00:32:19,570 --> 00:32:22,380 Na verdade, eu realmente não me importo com o que o frente é, porque o tamanho é igual a zero. 746 00:32:22,380 --> 00:32:24,480 Portanto, este pode muito bem ser um ponto de interrogação. 747 00:32:24,480 --> 00:32:26,170 Estes são todos os pontos de interrogação. 748 00:32:26,170 --> 00:32:29,880 Então, agora nós vamos realmente começar a ver alguns pessoas fazendo fila na loja. 749 00:32:29,880 --> 00:32:33,320 >> Então, se o número 9, você é o primeiro lá 05:00, vá em frente e alinhar, 750 00:32:33,320 --> 00:32:34,210 ou na noite anterior. 751 00:32:34,210 --> 00:32:34,580 OK. 752 00:32:34,580 --> 00:32:35,940 Então agora 9 é aqui. 753 00:32:35,940 --> 00:32:37,940 Assim 9 é na frente da lista. 754 00:32:37,940 --> 00:32:41,440 Então, eu estou indo para ir em frente e atualizar o tamanho dos dados actuais 755 00:32:41,440 --> 00:32:44,740 estrutura para não ser mais 0, mas para ser 1. 756 00:32:44,740 --> 00:32:47,630 Eu vou colocar 9 na frente da lista. 757 00:32:47,630 --> 00:32:51,020 Deixe-me ir em frente e alternar a tela assim podemos ver por nós aqui. 758 00:32:51,020 --> 00:32:53,220 >> E agora o que eu quero para colocar em frente? 759 00:32:53,220 --> 00:32:56,240 Vou manter o controle que o frente da fila agora 760 00:32:56,240 --> 00:32:58,570 está na posição 0. 761 00:32:58,570 --> 00:33:00,510 Porque o que está próximo vai acontecer? 762 00:33:00,510 --> 00:33:03,000 Bem, suponho que agora eu enfileirar 17 também. 763 00:33:03,000 --> 00:33:04,510 Então hop em linha lá. 764 00:33:04,510 --> 00:33:07,060 E, novamente, o tipo de porta para o loja vai estar aqui. 765 00:33:07,060 --> 00:33:08,700 Então agora eu adicionei 17. 766 00:33:08,700 --> 00:33:10,810 E mesmo que esses caras estão bloqueando da tela, que é OK, 767 00:33:10,810 --> 00:33:12,300 porque podemos vê-lo aqui. 768 00:33:12,300 --> 00:33:12,910 Desculpe. 769 00:33:12,910 --> 00:33:13,810 >> AUDIÊNCIA: Nós podemos mudar - 770 00:33:13,810 --> 00:33:14,660 >> DAVID MALAN: Não, isso é OK. 771 00:33:14,660 --> 00:33:16,000 É enorme lá em cima. 772 00:33:16,000 --> 00:33:18,580 Assim, é agora 17 dentro da fila. 773 00:33:18,580 --> 00:33:21,332 Eu preciso atualizar o que campos agora que? 774 00:33:21,332 --> 00:33:23,210 OK, definitivamente tamanho. 775 00:33:23,210 --> 00:33:26,430 E quanto a frente? 776 00:33:26,430 --> 00:33:27,040 OK, não. 777 00:33:27,040 --> 00:33:30,200 Frente não deve mudar, porque ao contrário de uma pilha, 778 00:33:30,200 --> 00:33:31,370 quer manter a equidade. 779 00:33:31,370 --> 00:33:35,150 Então, se 9 ficou em primeiro lugar, queremos 9 para ser o primeiro a sair da linha 780 00:33:35,150 --> 00:33:36,420 e para a loja. 781 00:33:36,420 --> 00:33:37,220 >> Na verdade, vamos ver isso. 782 00:33:37,220 --> 00:33:42,235 Antes de inserir 22, vamos vá em frente e dequeue 9. 783 00:33:42,235 --> 00:33:42,970 Qual é o seu nome? 784 00:33:42,970 --> 00:33:43,680 >> AUDIÊNCIA: Jake. 785 00:33:43,680 --> 00:33:45,440 >> DAVID MALAN: Jake vai para ser será agora. 786 00:33:45,440 --> 00:33:48,050 Então você começa a entrar na loja. 787 00:33:48,050 --> 00:33:49,880 E fingir que a loja está ali. 788 00:33:49,880 --> 00:33:51,970 Então, agora o que precisa - dit-dit-dit! 789 00:33:51,970 --> 00:33:53,400 O que precisa acontecer agora? 790 00:33:53,400 --> 00:33:54,490 Decisão de projeto. 791 00:33:54,490 --> 00:33:56,825 Então, não é um mau instinto, mas - qual é o seu nome? 792 00:33:56,825 --> 00:33:57,090 >> AUDIÊNCIA: David. 793 00:33:57,090 --> 00:33:57,500 >> DAVID MALAN: David. 794 00:33:57,500 --> 00:33:58,810 Então, o que fez Davi? 795 00:33:58,810 --> 00:34:02,590 Ele estava tentando resolver de corrigir os dados estrutura e movimento a partir de sua localização 796 00:34:02,590 --> 00:34:04,100 na antiga localização do Jake. 797 00:34:04,100 --> 00:34:06,740 E isso é bom, se estamos dispostos para aceitar isso como uma 798 00:34:06,740 --> 00:34:08,199 detalhe de implementação. 799 00:34:08,199 --> 00:34:11,100 Mas, primeiro, vamos atualizar os dados estrutura antes de fazer isso. 800 00:34:11,100 --> 00:34:14,139 Porque eu não estou gostando da idéia de tudo as pessoas deslocando nesta linha. 801 00:34:14,139 --> 00:34:17,360 >> Não é grande coisa se David faz com um passo, mas, novamente, acho que volta a 802 00:34:17,360 --> 00:34:20,360 quando tivemos oito voluntários na palco e fizemos como inserção 803 00:34:20,360 --> 00:34:22,600 tipo, em que nós tivemos que começar movendo-se todos ao redor. 804 00:34:22,600 --> 00:34:23,790 Isso tem cara, certo? 805 00:34:23,790 --> 00:34:28,330 Isso faz-me encolher sobre O grande de n, grande O de n ao quadrado novamente. 806 00:34:28,330 --> 00:34:30,650 Ele não está se sentindo como um resultado ideal. 807 00:34:30,650 --> 00:34:32,080 >> Então vamos atualizar isso. 808 00:34:32,080 --> 00:34:35,120 Assim, o tamanho da fila já não é 2. 809 00:34:35,120 --> 00:34:37,090 Agora é simplesmente um. 810 00:34:37,090 --> 00:34:40,360 Mas agora eu posso atualizar algo Eu não atualizar antes, a 811 00:34:40,360 --> 00:34:41,130 frente da lista. 812 00:34:41,130 --> 00:34:45,420 Eu poderia apenas dizer, é que uma localização? 813 00:34:45,420 --> 00:34:49,770 Portanto, agora temos valor de lixo aqui, valor de lixo aqui, e David no 814 00:34:49,770 --> 00:34:51,469 meio desse lixo. 815 00:34:51,469 --> 00:34:54,980 Mas, a estrutura de dados ainda está intacto. 816 00:34:54,980 --> 00:34:58,540 >> E, na verdade, eu nem preciso mudar ex-número um do Jake 817 00:34:58,540 --> 00:35:00,460 9, porque quem se importa. 818 00:35:00,460 --> 00:35:04,470 Eu tenho bastante informação agora no tamanho que eu sei que há uma pessoa em 819 00:35:04,470 --> 00:35:05,030 essa fila. 820 00:35:05,030 --> 00:35:08,340 E eu sei que essa pessoa está na posição 1, e não 0. 821 00:35:08,340 --> 00:35:09,760 Eu não estou contando. 822 00:35:09,760 --> 00:35:11,300 Assim, um bem. 823 00:35:11,300 --> 00:35:13,410 Assim, a estrutura de dados ainda é OK. 824 00:35:13,410 --> 00:35:14,330 >> Bem, o que acontece? 825 00:35:14,330 --> 00:35:15,010 Vamos enfileirar - 826 00:35:15,010 --> 00:35:15,370 qual é o seu nome? 827 00:35:15,370 --> 00:35:16,160 >> AUDIÊNCIA: Callen. 828 00:35:16,160 --> 00:35:16,580 >> DAVID MALAN: Callen. 829 00:35:16,580 --> 00:35:20,770 Vamos enfileirar uma Callen, e 22 está agora na fila. 830 00:35:20,770 --> 00:35:22,300 Então, agora o que tem que mudar aqui? 831 00:35:22,300 --> 00:35:24,380 Frente não vai mudar, obviamente. 832 00:35:24,380 --> 00:35:27,160 Tamanho vai mudar para ser 2 novamente. 833 00:35:27,160 --> 00:35:31,590 E 22 acaba aqui, 9 ainda está presente, mas é efetivamente um 834 00:35:31,590 --> 00:35:32,600 valor de lixo agora. 835 00:35:32,600 --> 00:35:35,910 É apenas um remanescente de Jake passado. 836 00:35:35,910 --> 00:35:39,200 >> Então agora o que acontece se Eu desenfileirar David? 837 00:35:39,200 --> 00:35:41,560 Uma última operação, dequeue David. 838 00:35:41,560 --> 00:35:46,070 Poderíamos mudar, mas proponho vamos fazer tão pouco trabalho quanto possível. 839 00:35:46,070 --> 00:35:50,280 Agora, a minha estrutura de dados vai trás em tamanho de 2 para 1. 840 00:35:50,280 --> 00:35:53,730 Mas a frente da fila agora torna-se 2. 841 00:35:53,730 --> 00:35:56,640 Eu não preciso mudar esses números mas apenas, porque eles são 842 00:35:56,640 --> 00:35:58,230 apenas os valores de lixo. 843 00:35:58,230 --> 00:35:59,720 >> Mas, agora, o que acontece? 844 00:35:59,720 --> 00:36:03,280 Suponha que eu me enfileirar, 26? 845 00:36:03,280 --> 00:36:05,890 Eu sinto que eu pertenço aqui. 846 00:36:05,890 --> 00:36:06,890 Então, eu estou sendo enfileirado. 847 00:36:06,890 --> 00:36:08,760 Então eu meio que pertenço aqui. 848 00:36:08,760 --> 00:36:11,300 E mesmo que você não faz bem apreciar este visual no palco, 849 00:36:11,300 --> 00:36:15,075 porque temos muito espaço, eu deveria não estar aqui, por quê? 850 00:36:15,075 --> 00:36:16,290 >> AUDIÊNCIA: Você está fora dos limites. 851 00:36:16,290 --> 00:36:16,370 >> DAVID MALAN: Certo. 852 00:36:16,370 --> 00:36:16,940 Estou fora dos limites. 853 00:36:16,940 --> 00:36:19,330 Eu indexado além do limites desta matriz. 854 00:36:19,330 --> 00:36:23,420 Eu realmente deveria estar em um dos três localizações possíveis. 855 00:36:23,420 --> 00:36:25,150 Agora, onde é mais natural para ir? 856 00:36:25,150 --> 00:36:27,760 Proponho que alavancou uma semana um truque. 857 00:36:27,760 --> 00:36:30,150 O operador mod, porcentagem. 858 00:36:30,150 --> 00:36:36,850 Porque eu estou tecnicamente em pé na localização 3, mas eu faço 3 capacidade mod, 859 00:36:36,850 --> 00:36:40,250 para 3, um sinal de porcentagem, 3 - 860 00:36:40,250 --> 00:36:40,970 capacidade é 3. 861 00:36:40,970 --> 00:36:41,720 O que é isso? 862 00:36:41,720 --> 00:36:43,700 Qual é o resto quando você dividir 3 por 3? 863 00:36:43,700 --> 00:36:44,070 0. 864 00:36:44,070 --> 00:36:48,140 >> Assim que me põe foram Jake era, o que é realmente bom. 865 00:36:48,140 --> 00:36:50,370 Então, agora a implementação dessa coisa vai 866 00:36:50,370 --> 00:36:51,250 ser um pouco de dor de cabeça. 867 00:36:51,250 --> 00:36:53,740 É realmente apenas uma linha de dor de cabeça, de código. 868 00:36:53,740 --> 00:36:56,580 Mas pelo menos agora há lixo valor aqui, mas há dois 869 00:36:56,580 --> 00:36:57,910 ints legítimos aqui. 870 00:36:57,910 --> 00:37:04,160 E eu afirmo que agora temos feito exatamente o que precisa fazer, desde que 871 00:37:04,160 --> 00:37:08,600 podemos mudar o que Jake valor seria 26. 872 00:37:08,600 --> 00:37:12,110 >> Agora temos informação suficiente ainda para manter a integridade 873 00:37:12,110 --> 00:37:13,060 esta estrutura de dados. 874 00:37:13,060 --> 00:37:17,160 Nós ainda estamos meio fora de sorte quando nós deseja inserir quatro ou mais Total 875 00:37:17,160 --> 00:37:20,740 elementos, mas posso pelo menos fazer muito utilização eficiente da presente constante 876 00:37:20,740 --> 00:37:21,740 tempo, na verdade. 877 00:37:21,740 --> 00:37:27,150 Eu não precisa se preocupar com mudança todos, como inclinação de Davi era. 878 00:37:27,150 --> 00:37:30,816 >> Qualquer dúvida sobre pilhas, ou esta fila? 879 00:37:30,816 --> 00:37:32,184 >> AUDIÊNCIA: É a razão pela qual você precisa de tamanho para que você saiba 880 00:37:32,184 --> 00:37:34,010 onde se tem uma pessoa? 881 00:37:34,010 --> 00:37:34,770 >> DAVID MALAN: Exatamente. 882 00:37:34,770 --> 00:37:38,230 Eu preciso saber o tamanho da matriz porque eu preciso saber exatamente como 883 00:37:38,230 --> 00:37:41,940 Muitos desses valores são legítimas, e para que eu possa encontrar onde colocar 884 00:37:41,940 --> 00:37:42,800 a próxima pessoa. 885 00:37:42,800 --> 00:37:43,300 Exatamente. 886 00:37:43,300 --> 00:37:44,580 O tamanho é - 887 00:37:44,580 --> 00:37:46,360 Na verdade, nós não atualizar isso ainda. 888 00:37:46,360 --> 00:37:48,380 Eu me adicionado aos 26 anos. 889 00:37:48,380 --> 00:37:51,760 O tamanho é agora, não um, mas dois. 890 00:37:51,760 --> 00:37:57,780 Então, agora este fato me ajuda a encontrar o cabeça de lista, o que não é 0, não 891 00:37:57,780 --> 00:37:59,250 1, mas é 2. 892 00:37:59,250 --> 00:38:01,665 A parte dianteira da lista é de facto o número 22. 893 00:38:01,665 --> 00:38:05,120 Porque ele ficou em primeiro lugar, então ele deve ser autorizados a entrar na loja antes de mim, 894 00:38:05,120 --> 00:38:08,780 apesar de visualmente eu estou mais perto da loja. 895 00:38:08,780 --> 00:38:09,220 >> Tudo bem? 896 00:38:09,220 --> 00:38:12,410 Uma salva de palmas para esses caras e nós vamos deixá-los de lá. 897 00:38:12,410 --> 00:38:17,090 >> [Aplausos] 898 00:38:17,090 --> 00:38:18,150 >> DAVID MALAN: eu poderia deixar você mantenha a bandeja. 899 00:38:18,150 --> 00:38:20,760 Pudemos ver o que acontece se você quer, mas talvez não. 900 00:38:20,760 --> 00:38:21,590 Tudo bem. 901 00:38:21,590 --> 00:38:25,380 Então, o que agora é que isso nos deixa? 902 00:38:25,380 --> 00:38:28,900 Bem, deixe-me propor que há um algumas outras estruturas de dados que poderiam 903 00:38:28,900 --> 00:38:33,810 começar a adicionar ao nosso kit de ferramentas que vão realmente ser muito, muito relevante como 904 00:38:33,810 --> 00:38:35,270 nós mergulhar em coisas web. 905 00:38:35,270 --> 00:38:38,150 Que por sua vez, tem algum tipo de ligação a árvores, sob a forma de 906 00:38:38,150 --> 00:38:40,550 algo chamado DOM, documento modelo de objeto. 907 00:38:40,550 --> 00:38:42,370 Mas vamos ver mais de que em pouco tempo. 908 00:38:42,370 --> 00:38:46,260 >> Deixe-me propor que por definição chamar árvore agora o que você pode saber como 909 00:38:46,260 --> 00:38:48,820 mais de uma árvore de família, onde você ter algum antepassado na 910 00:38:48,820 --> 00:38:49,790 raizes da árvore. 911 00:38:49,790 --> 00:38:54,480 A matriarca patriarcal ou na o topo da árvore. 912 00:38:54,480 --> 00:38:56,700 Sem o seu cônjuge, neste caso. 913 00:38:56,700 --> 00:39:00,940 Mas agora temos que chamaremos crianças, que são os nós que pendem 914 00:39:00,940 --> 00:39:05,480 fora o filho esquerdo ou o direito da criança, setas como descrito aqui. 915 00:39:05,480 --> 00:39:10,490 >> Em outras palavras, uma estrutura de dados em árvore em computador, uma árvore tem zero 916 00:39:10,490 --> 00:39:11,480 ou mais nós. 917 00:39:11,480 --> 00:39:13,500 Se ele tem pelo menos um nó, que é chamado de raiz. 918 00:39:13,500 --> 00:39:15,700 É as coisas visualmente que traçamos no topo. 919 00:39:15,700 --> 00:39:20,280 E esse nó, como qualquer outro nó, pode ter zero, uma ou duas, ou três, 920 00:39:20,280 --> 00:39:23,600 ou quantos filhos o estrutura de dados suporta. 921 00:39:23,600 --> 00:39:29,150 Neste caso, a raiz, o armazenamento valor um, tem dois filhos, 2 e 3, 922 00:39:29,150 --> 00:39:33,020 assim que nós geralmente chamamos de 2 a esquerda criança e 3 a criança certa. 923 00:39:33,020 --> 00:39:36,940 >> E então, quando chegarmos a 5, 6 e 7, 6 pode ser chamado o filho do meio. 924 00:39:36,940 --> 00:39:38,940 Se você tiver quatro filhos, ele fica confuso. 925 00:39:38,940 --> 00:39:42,260 Então, pare de usar esse tipo de atalho verbalmente. 926 00:39:42,260 --> 00:39:44,580 Mas é realmente apenas uma árvore genealógica. 927 00:39:44,580 --> 00:39:48,880 E as folhas aqui são os nós que eles próprios não têm filhos. 928 00:39:48,880 --> 00:39:52,540 Eles ficam fora da parte inferior da árvore. 929 00:39:52,540 --> 00:39:56,940 >> Então, como podemos implementar uma árvore que tem apenas dois filhos maximamente? 930 00:39:56,940 --> 00:39:58,410 Vamos chamá-lo de uma árvore binária. 931 00:39:58,410 --> 00:40:00,960 Bi novamente significando dois, neste caso, como com binário. 932 00:40:00,960 --> 00:40:04,830 E, por isso, pode ter zero, uma ou os dois filhos maximamente. 933 00:40:04,830 --> 00:40:08,650 >> Vou propor que vamos implementar o nó para essa estrutura, com um int n, 934 00:40:08,650 --> 00:40:11,910 e, em seguida, dois apontadores, um chamado à esquerda, um chamado para a direita. 935 00:40:11,910 --> 00:40:14,830 Mas esses são apenas bom convenções arbitrárias. 936 00:40:14,830 --> 00:40:18,170 E o que é bom agora, especialmente se você tipo de dificuldade conceitual com 937 00:40:18,170 --> 00:40:21,300 recursão, ou pensado que não era realmente uma solução para nada, 938 00:40:21,300 --> 00:40:23,120 especialmente se você pudesse sem memória. 939 00:40:23,120 --> 00:40:26,600 Agora que estamos falando de dados estruturas e algoritmos que permitem 940 00:40:26,600 --> 00:40:31,030 nos a atravessar e manipulá-los, Acontece que a recursividade volta em 941 00:40:31,030 --> 00:40:34,240 uma muito mais atraente se não for belo caminho. 942 00:40:34,240 --> 00:40:38,670 >> Então, isso eu proponho é a implementação de uma função de pesquisa. 943 00:40:38,670 --> 00:40:39,870 Dadas duas entradas - 944 00:40:39,870 --> 00:40:41,570 por isso pense nisso como uma caixa preta. 945 00:40:41,570 --> 00:40:46,560 Dadas duas entradas, N, um int, e um ponteiro para uma árvore, um ponteiro para uma 946 00:40:46,560 --> 00:40:50,020 nó, ou realmente a raiz de uma árvore, eu alegação de que esta função pode retornar 947 00:40:50,020 --> 00:40:53,530 verdadeira ou falsa, isto valor n É dentro desta árvore. 948 00:40:53,530 --> 00:40:55,210 >> O que tem dentro dessa caixa preta? 949 00:40:55,210 --> 00:40:57,440 Bem, quatro ramos. 950 00:40:57,440 --> 00:40:58,385 O primeiro apenas verifica. 951 00:40:58,385 --> 00:41:00,490 Se a árvore é nula, basta retornar falso. 952 00:41:00,490 --> 00:41:04,580 Se não houver nenhum nó, não há n, não há nenhum número, só retornará false. 953 00:41:04,580 --> 00:41:12,330 Se, porém, n, o valor que você está procurando para, é menor do que a árvore seta ne 954 00:41:12,330 --> 00:41:15,180 só para ficar claro, o que ele quer dizer quando Eu escrevo árvore e, em seguida, a seta 955 00:41:15,180 --> 00:41:18,150 notação, n? 956 00:41:18,150 --> 00:41:18,690 Exatamente. 957 00:41:18,690 --> 00:41:21,970 Isso significa que desreferenciava ponteiro chamado árvore. 958 00:41:21,970 --> 00:41:26,750 Vá lá, e, em seguida, entrar dentro de que nó e obter o seu campo chamado n. 959 00:41:26,750 --> 00:41:30,810 E, em seguida, comparar o n real que foi passou para Pesquisa contra ele. 960 00:41:30,810 --> 00:41:35,390 >> Assim, se n for menor do que o valor n no próprio nó da árvore, assim, 961 00:41:35,390 --> 00:41:36,720 O que isso significa? 962 00:41:36,720 --> 00:41:40,690 Isso não significa nada à primeira vista. 963 00:41:40,690 --> 00:41:40,900 Certo? 964 00:41:40,900 --> 00:41:45,560 Assim como quando você tem um conjunto de valores, você pode gostar de aplicar binário 965 00:41:45,560 --> 00:41:48,290 pesquisa como uma forma de divisão e conquistar. 966 00:41:48,290 --> 00:41:51,790 Mas o pressuposto de que nós precisamos fazer para pesquisa binária para trabalhar em conjunto 967 00:41:51,790 --> 00:41:54,510 no livro de telefone e exemplos anteriores? 968 00:41:54,510 --> 00:41:55,530 >> Como ser classificados. 969 00:41:55,530 --> 00:41:59,490 Então, vamos refinar a definição de árvore aqui para não ser apenas uma árvore, que pode 970 00:41:59,490 --> 00:42:00,880 ter qualquer número de filhos. 971 00:42:00,880 --> 00:42:04,700 Não é apenas uma árvore binária, o que pode ter 0, 1 ou 2 maximamente. 972 00:42:04,700 --> 00:42:09,700 Mas, como uma árvore de busca binária, ou BST, que é apenas uma maneira elegante de dizer a 973 00:42:09,700 --> 00:42:15,430 árvore binária de tal forma que de cada nó filho esquerdo, se presente, é 974 00:42:15,430 --> 00:42:16,830 menos do que o nó. 975 00:42:16,830 --> 00:42:20,170 E criança o direito de cada nó, se estiver presente, é maior 976 00:42:20,170 --> 00:42:21,740 do que o próprio nó. 977 00:42:21,740 --> 00:42:25,200 >> Portanto, em outras palavras, se você fosse desenhar a saída da árvore, todos os números são 978 00:42:25,200 --> 00:42:30,620 cuidadosamente equilibrado como este, para que se você tem 55 como a raiz, de 33 anos pode ir 979 00:42:30,620 --> 00:42:33,090 à sua esquerda, porque é inferior a 55. 980 00:42:33,090 --> 00:42:36,430 77 pode ir para o seu direito, porque é superior a 55. 981 00:42:36,430 --> 00:42:40,750 Mas, agora, perceber, a mesma definição, é uma definição recursiva verbalmente, 982 00:42:40,750 --> 00:42:42,600 tem de pedir 33. 983 00:42:42,600 --> 00:42:47,610 33 do filho esquerdo deve ser menor do que, e direito da criança de 33, 44, deve ser 984 00:42:47,610 --> 00:42:48,580 maior do que isso. 985 00:42:48,580 --> 00:42:51,670 >> Portanto, esta é uma árvore de busca binária, e Proponho, usando um pouco de 986 00:42:51,670 --> 00:42:53,910 recursão, agora podemos encontrar n. 987 00:42:53,910 --> 00:42:59,160 Assim, se n for menor do que o valor de n, que é nó atual, eu estou indo para ir 988 00:42:59,160 --> 00:43:04,090 frente e punt, por assim dizer, e apenas devolver qualquer que seja a resposta é de 989 00:43:04,090 --> 00:43:08,470 procura de n no filho esquerdo da árvore. 990 00:43:08,470 --> 00:43:11,370 Observe mais uma vez, esta função só espera uma estrela nó, um 991 00:43:11,370 --> 00:43:12,780 ponteiro para um nó. 992 00:43:12,780 --> 00:43:17,360 Então, certamente eu só posso fazer árvore seta para a esquerda, o que levará 993 00:43:17,360 --> 00:43:18,400 me para outro nó. 994 00:43:18,400 --> 00:43:19,480 Mas o que é esse nó? 995 00:43:19,480 --> 00:43:22,820 >> Bem, de acordo com esta declaração, esquerda é apenas um ponteiro, de modo que apenas 996 00:43:22,820 --> 00:43:27,090 Significa que eu estou passando para a função de pesquisa um indicador diferente, nomeadamente 997 00:43:27,090 --> 00:43:30,750 o que representa um árvore do meu filho esquerdo. 998 00:43:30,750 --> 00:43:36,040 Portanto, neste caso, o ponteiro a 33, se esta é a nossa amostra de entrada Entretanto, se 999 00:43:36,040 --> 00:43:40,740 n é maior do que o valor de n no nó atual na árvore, então eu estou 1000 00:43:40,740 --> 00:43:43,370 indo para ir em frente e punt na outra direção e dizer, eu não 1001 00:43:43,370 --> 00:43:47,280 sabe se este valor n está na árvore, mas eu sei que se é, é a minha 1002 00:43:47,280 --> 00:43:49,090 ramo direito, por assim dizer. 1003 00:43:49,090 --> 00:43:53,120 Então deixe-me chamar recursivamente procurar, passar um n novamente, mas passando uma 1004 00:43:53,120 --> 00:43:54,580 ponteiro para o meu filho direito. 1005 00:43:54,580 --> 00:44:00,020 >> Em outras palavras, se eu estou atualmente em 55 e eu estou à procura de 99, eu sei que 99 1006 00:44:00,020 --> 00:44:04,270 é maior do que 55, então como eu rasguei o livro de telefone há semanas e nós 1007 00:44:04,270 --> 00:44:07,140 foi para a direita, da mesma forma somos nós vai dar certo aqui. 1008 00:44:07,140 --> 00:44:11,960 E eu não sei se é a minha direita criança, e não é, de 77 está lá, mas 1009 00:44:11,960 --> 00:44:13,210 Eu sei que é nessa direção. 1010 00:44:13,210 --> 00:44:18,770 Então, eu chamo de busca no meu filho direito, 77, e que a figura de pesquisa a partir 1011 00:44:18,770 --> 00:44:24,950 lá se 99 deste arbitrária exemplo é realmente lá. 1012 00:44:24,950 --> 00:44:26,900 >> Senão, o que é o caso final? 1013 00:44:26,900 --> 00:44:28,620 Se a árvore é nula é um caso. 1014 00:44:28,620 --> 00:44:31,890 Se n for menor do que a corrente do nó valor é outro caso. 1015 00:44:31,890 --> 00:44:35,120 Se n for maior do que o actual valor do nó é um terceiro caso. 1016 00:44:35,120 --> 00:44:38,250 O que é o quarto e último caso? 1017 00:44:38,250 --> 00:44:39,480 Acho que estamos fora dos casos, certo? 1018 00:44:39,480 --> 00:44:44,690 Deve ser, em que n é o nó atual que estou. 1019 00:44:44,690 --> 00:44:49,640 >> Então, se eu estou procurando 55 neste momento na história, esse ramo da 1020 00:44:49,640 --> 00:44:51,780 árvore voltaria verdade. 1021 00:44:51,780 --> 00:44:55,380 Então, o que é interessante aqui é que nós na verdade, ao contrário de semana passado, nós meio 1022 00:44:55,380 --> 00:44:56,740 de ter dois casos base. 1023 00:44:56,740 --> 00:44:58,300 E, eles não têm a ficar no topo. 1024 00:44:58,300 --> 00:45:01,390 O topo é um caso base, porque se o árvore é nulo, não há nada a fazer. 1025 00:45:01,390 --> 00:45:03,410 Basta retornar um disco codificado valor false. 1026 00:45:03,410 --> 00:45:07,400 >> O ramo inferior é uma espécie de padrão, pelo qual se tenha verificado para 1027 00:45:07,400 --> 00:45:11,550 nulo, temos verificado se ele deve ser para a esquerda, mas não deve ser, temos 1028 00:45:11,550 --> 00:45:14,640 verificado se ele deve estar certo, mas não deve ser, claramente, tem de ser 1029 00:45:14,640 --> 00:45:15,870 exatamente onde estamos. 1030 00:45:15,870 --> 00:45:16,780 Isso é um caso base. 1031 00:45:16,780 --> 00:45:19,920 Portanto, há dois casos recursivas entalado lá no meio. 1032 00:45:19,920 --> 00:45:21,630 Mas eu poderia ter escrito isto em qualquer ordem. 1033 00:45:21,630 --> 00:45:24,520 Eu apenas pensei que tipo de me pareceu natural primeiro verificar um possível erro, 1034 00:45:24,520 --> 00:45:28,340 em seguida, verifique a esquerda, em seguida, verifique bem, então supor que você está no nó 1035 00:45:28,340 --> 00:45:30,630 você está realmente procurando. 1036 00:45:30,630 --> 00:45:36,240 >> Então, por que isso pode ser útil? 1037 00:45:36,240 --> 00:45:37,910 Assim, verifica-se - 1038 00:45:37,910 --> 00:45:42,110 e deixe-me ir para um teaser aqui que está na web. 1039 00:45:42,110 --> 00:45:44,920 Nós vamos começar a utilizar não é uma linguagem de programação no início, mas a 1040 00:45:44,920 --> 00:45:46,030 linguagem de marcação. 1041 00:45:46,030 --> 00:45:48,740 A linguagem de marcação que é ser um similares em espírito à programação 1042 00:45:48,740 --> 00:45:51,715 linguagem, mas ele não lhe dá o capacidade de se expressar de forma lógica. 1043 00:45:51,715 --> 00:45:55,070 Ele só lhe dá a capacidade de expressar-se estruturalmente. 1044 00:45:55,070 --> 00:45:57,960 >> Onde você quer colocar algo na página, a página da web? 1045 00:45:57,960 --> 00:45:59,200 Qual a cor que você quer fazer isso? 1046 00:45:59,200 --> 00:46:00,950 O tamanho da fonte que você quer fazer isso? 1047 00:46:00,950 --> 00:46:02,970 Que palavras você realmente quer na página web? 1048 00:46:02,970 --> 00:46:04,060 Então essa é uma linguagem de marcação. 1049 00:46:04,060 --> 00:46:07,690 Mas, então, vamos apresentar muito rapidamente JavaScript, que é um verdadeiro 1050 00:46:07,690 --> 00:46:08,560 linguagem de programação. 1051 00:46:08,560 --> 00:46:12,530 Muito semelhante sintaticamente na aparência a C, mas vai ter algum 1052 00:46:12,530 --> 00:46:15,200 bom, mais poderoso, mais características de fácil utilização. 1053 00:46:15,200 --> 00:46:18,050 >> E uma das frustrações neste ponto no semestre é que vamos 1054 00:46:18,050 --> 00:46:22,065 em breve implementar speller em muito menos linhas de código, utilizando outras linguagens 1055 00:46:22,065 --> 00:46:25,580 que a própria C permite, mas por motivo de em breve iremos entender. 1056 00:46:25,580 --> 00:46:27,750 Este será o primeiro tal página web. 1057 00:46:27,750 --> 00:46:30,120 Será completamente abaixo do esperado, o primeiro que fazemos. 1058 00:46:30,120 --> 00:46:31,400 Ele vai simplesmente dizer: Olá mundo. 1059 00:46:31,400 --> 00:46:34,010 Mas se você nunca viu antes, este é HTML, 1060 00:46:34,010 --> 00:46:35,670 HyperText Markup Language. 1061 00:46:35,670 --> 00:46:39,310 >> Se você vai a uma determinada opção de menu em mais qualquer browser, em qualquer página web em 1062 00:46:39,310 --> 00:46:43,160 a internet, você pode ver o HTML que algumas pessoas escreveram para 1063 00:46:43,160 --> 00:46:44,400 criar essa página web. 1064 00:46:44,400 --> 00:46:47,850 E provavelmente não parece tão breve ou tão puro como este. 1065 00:46:47,850 --> 00:46:51,400 Mas vai seguir o padrão desses colchetes abertos e barras e 1066 00:46:51,400 --> 00:46:53,660 letras e números. potencialmente 1067 00:46:53,660 --> 00:46:56,770 >> Pensei em dar-lhe um teaser do que você vai ser capaz de fazer 1068 00:46:56,770 --> 00:46:57,950 depois de tomar CS50. 1069 00:46:57,950 --> 00:47:02,620 Deixe-me ir para cs.harvard.edu / roubar, página inicial nossa própria Rob Bowden. 1070 00:47:02,620 --> 00:47:06,080 Ele fez isso por nós. 1071 00:47:06,080 --> 00:47:07,490 Assim, em breve você vai ser capaz de fazer isso. 1072 00:47:07,490 --> 00:47:10,660 E também, o que você ouviu esta manhã - 1073 00:47:10,660 --> 00:47:12,480 o que você ouviu esta manhã - 1074 00:47:12,480 --> 00:47:13,780 >> [HAMSTER DANCE MUSIC] 1075 00:47:13,780 --> 00:47:15,702 >> - Você será capaz de fazer isto. 1076 00:47:15,702 --> 00:47:16,790 Que nos espera na quarta-feira. 1077 00:47:16,790 --> 00:47:17,791 Vamos vê-lo em seguida. 1078 00:47:17,791 --> 00:47:22,950 >> [HAMSTER DANCE MUSIC] 1079 00:47:22,950 --> 00:47:24,300 DAVID MALAN: Na próxima CS50 - 1080 00:47:24,300 --> 00:47:31,670