DAVID MALAN: Tudo bem. Bem-vindo de volta ao CS50. Este é o início da semana 8. E lembrar que problema set terminou 5 com um pouco de um desafio. Então, supondo que você recuperou todo o seu Companheiros de ensino e fotografias da CA no arquivo card.raw, você é elegível agora encontrar todas essas pessoas, e um sortudo ganhador vai a pé para casa com um destas coisas, o movimento salto dispositivo que você pode usar para a final projetos, por exemplo. 

Este, a cada ano, leva a um pouco de bizarrice. E assim que eu pensei que eu iria fazer é compartilhar com você algumas das notas que têm ido para trás e para frente sobre a lista de funcionários da tarde. Por exemplo, ontem à noite, citações unquote, a partir de um dos funcionários membros ", eu só tinha uma batida estudante na minha porta para tirar uma foto comigo. Stalkers, eu lhe digo. "Começou bastante descritivo e depois nos mudamos para, uma hora mais tarde, "Eu tive um estudante esperando por mim após a seção e ele tinha todos os nossos nomes e fotos em algumas folhas de papel. "Tudo bem. Assim organizado, mas não tudo o que assustador ainda. 

Então, "Eu estava fora da cidade neste fim de semana, e quando voltei, havia um em meu quarto. "[risos] DAVID MALAN: Next citação de uma equipe membro ", disse um aluno veio à minha casa em Somerville às 4 da manhã, esta manhã. "Next pessoal, "Eu cheguei ao meu hotel em San Francisco e um aluno estava esperando por me no hall de entrada com três DSLRs. " Tipo de câmera. "Eu não estou nem na equipe neste semestre, mas um estudante invadiu a minha casa esta manhã e registrou a coisa toda com vidro Google. "E então, finalmente, "Pelo menos 12 pessoas foram avidamente aguardando para mim quando eu saí do meu limo, e então eu acordei. "Tudo bem. Assim, entre as fotografias, como você pode lembrar, são este homem aqui, que você pode saber como Milo Banana, que vive com Lauren Carvalho, a nossa cabeça ensino Fellow. Milo, Milo, vem cá menino. Milo. Milo. Lembre-se, ele está usando Google de vidro, de modo vamos mostrar tudo isso depois. Portanto, esta é Milo se você gostaria de tirar uma fotografia com ele depois. Se você gostaria de olhar para fora para o público lá. OK. Isso é bom filmagens. Bem, Milo Banana. Oh, não faça isso. 

[Risos] 

OK. Assim, uma palavra, em seguida, sobre o que está por vir, porque quando começamos a transição, esta semana especificamente, a partir de C, numa ambiente de linha de comando para PHP e JavaScript e SQL e HTML e CSS em um ambiente baseado na web, estaremos equipando-o com toda a mais conhecimento para potenciais projetos finais. Para isso, o curso tem uma tradição de realização de seminários que são sobre temas tangenciais ao curso. Muito relacionado à programação e desenvolvimento de aplicativos e assim por diante, mas não necessariamente por explorado próprio plano de estudos do curso. 

Então, se você poderia estar interessado em um ou mais de seminários deste ano, registrar em cs50.net/seminar. Existem seminários idosas em cs50.net/seminars. E no plantel, até agora, para este ano são surpreendentes Aplicativos Web com Ruby on Carris, que é uma alternativa linguagem para PHP. Linguística Computacional. Introdução à IOS, que é o plataforma que é usado para o iPhone e desenvolvimento iPad. JavaScript para Web Apps, vamos cobrir isso, mas neste seminário, você vai em mais detalhe. 

Leap Movimento, então vamos realmente ter algum dos nossos amigos da Leap Movimento, da própria empresa, se juntar a nós. Amanhã, na verdade, para fornecer um hands-on seminário, se de seu interesse. Meteor.js, uma técnica alternativa para usando JavaScript e não em um navegador, mas num servidor. Node.js., que é muito nessa veia bem. Design elegante Android. Android ser uma alternativa muito popular para iOS e Windows Phone e outras plataformas móveis. E Web Active Defense Segurança. 

Então, na verdade, se você quiser se envolver nisso, deixe-me anote isso. Estamos muito felizes em dizer que nossos amigos em Salto De movimento, que é uma inicialização - este dispositivo realmente acabou fora há alguns meses - graciosamente doaram 30 dispositivos para a classe de como muitos alunos, se gostaria de pedir o hardware para o final do semestre, e usá-lo para um projeto real final. Eles suportam várias línguas. Nenhum deles C, nenhum deles PHP, assim perceber um ou mais destes seminários pode revelar-se de interesse. E todos eles vão ser filmado em caso em que você não é capaz para comparecer em pessoa. A programação será anunciada via enviar e-mail como se solidificar quartos. 

E, por último, se você vai para projects.cs.50.net, este é um sítio mantemos a cada ano que convidamos pessoas da comunidade, professores, departamentos, funcionários e ambos em um lado de fora de CS50 para propor idéias para projetos. Coisas de interesse para grupos de estudantes. Coisas de interesse para os departamentos. Então não virar lá, se você está lutando com a incerteza quanto ao que você se gostaria de enfrentar. 

Então última vez que introduziu uma indiscutivelmente estrutura de dados mais complexa do que tínhamos visto nas últimas semanas. Nós estávamos usando matrizes bastante feliz como um útil se estrutura de dados simplista. Então, nós introduzimos estes, que naturalmente estão ligados listas. E o que foi uma das motivações para introduzindo esta estrutura de dados? Sim? O que é isso? 

AUDIÊNCIA: tamanho dinâmico. 

DAVID MALAN: tamanho dinâmico. Assim, enquanto em ordem, você tem que conhecer antecipadamente o seu tamanho quando você alocá-lo. Na lista ligada, você não tem que saber isso. Você pode apenas malloc, ou, mais geralmente, atribuir um adicional nó, por assim dizer, a qualquer momento você pretende inserir mais dados. O nodo tem nenhum significado pré-determinado. É apenas um termo genérico que descreve algum tipo de recipiente que estamos usando na nossa estrutura de dados para armazenar algum item de interesse, que neste caso acontecer de ser inteiros. 

Mas há sempre uma troca. Então, nós temos tamanhos dinâmica dos dados estrutura, mas o preço que vamos pagar? Qual é a desvantagem de listas ligadas? Sim? 

AUDIÊNCIA: Requer mais memória. 

DAVID MALAN: Exige mais memória, como exatamente? 

AUDIÊNCIA: [inaudível]. 

DAVID MALAN: Exatamente. Então, agora temos ponteiros ocupando memória adicional que anteriormente não precisa, pois a vantagem de uma matriz, é claro, é que tudo é contíguo, de volta de volta para trás, o que dá-lhe acesso aleatório. Porque apenas usando colchete notação, ou mais tecnicamente ponteiro aritmética, adição muito simples, você pode acessar qualquer elementos em tempo constante. E, de fato, esse é o tipo de insinuando outro preço que estamos pagando com um lista ligada. 

O que acontece com o tempo de execução algo como Search, se eu quiser encontrar algum valor e no interior de uma lista ligada? O que o meu tempo de execução se tornou? Big O de n. Se for classificada para? E se a estrutura de dados é classificado? Eu posso fazer melhor do que um grande O de n para a pesquisa? Não, porque na pior das hipóteses ele pode muito bem ser classificado, mas o número você está procurando pode ser grande. Pode ser o número 100, o qual pode acontecer de ser tudo o caminho no final. E porque você só pode acessar um linked lista nesta implementação por caminho de seu primeiro nó, você está Ainda meio fora de sorte. Você tem que atravessar a coisa toda do primeiro ao último, a fim de encontrar que grande como o valor 100. Ou para determinar se é nem mesmo lá. 

Portanto, não podemos fazer o algoritmo em um conjunto de dados estrutura que se parece com isso? Nós não podemos fazer busca binária, porque busca binária necessário que tínhamos de acesso aleatório. Nós poderíamos simplesmente saltar de local para local, sem ter que seguir estas migalhas de pão na forma todas estas indicações. 

Agora, como é que vamos implementar isso? Bem, se formos para a tela aqui, se podemos reimplementar rapidamente esses dados estrutura - minha letra não é tudo o que grande aqui, mas vamos tentar. Typedef struct Então, eo que eu fiz quero chamar essa coisa aqui em cima? Node. Então, eu vou ser um bom começo. E agora, o que precisa estar dentro de a estrutura de dados para que, isoladamente lista ligada? Quantos campos? 

Assim, dois. Um deles é muito fácil. Então, int n. E poderíamos chamar n qualquer coisa que quisermos, mas deve ser um int se estamos implementação de uma lista encadeada para ints. E agora o que é que o segundo campo tem que ser? Struct node *. Então, se eu fizer struct node *, e então eu pode chamar isso também o que eu quiser, mas só para ficar claro que eu vou chamar lo ao lado, como temos vindo a fazer. E então eu vou fechar meus chaves. 

E agora, como da última vez, Eu coloquei nó aqui. Mas se eu estou declarando isso é como um nó, por que eu me incomodo de ser tão detalhado aqui na declaração struct * nó seguinte, em oposição apenas nó * next? Sim? 

AUDIÊNCIA: [inaudível]. 

DAVID MALAN: Exatamente. Exatamente. Porque C realmente leva você literalmente e vê apenas a definição de nó até aqui, você não pode consultá-lo aqui. Então nós temos esse tipo de preferência declaração aqui, que é reconhecidamente mais detalhado. Struct nó, o que significa agora podemos acessá-lo no interior da estrutura de dados. 

E, como um lado, porque isso é tornando-se um pouco mais subjetiva, agora, a estrela tecnicamente pode ir aqui, ele pode ir aqui, ele pode até mesmo ir no meio. Adotamos, no guia de estilo para o curso, a convenção de colocar a estrela ao lado dos dados tipo, que, neste caso, seria nó struct. Mas perceber em um monte de livros e referências on-line, você pode de fato vê-lo do outro lado. Mas basta perceber que ambos realmente trabalhar e você deve simplesmente ser consistente. 

Tudo bem. Então essa foi a nossa declaração de nó struct. Mas, então, começamos a fazer mais coisas sofisticadas. Por exemplo, decidimos introduzir algo como uma tabela hash. Então, aqui está uma tabela hash de tamanho n, indexados a partir de 0 no canto superior esquerdo para n menos um na parte inferior esquerda. Este poderia ser um hash mesa para nada. Mas que tipo de coisas que nós falamos sobre o uso de uma tabela hash para? Armazenar o quê? 

Nomes. Poderíamos fazer nomes como fizemos da última vez. E realmente, você pode armazenar qualquer coisa. E veremos isso de novo em PHP e JavaScript. Uma tabela é um bom tipo de suíço Canivete que permite que você armazene praticamente tudo o que quiser dentro de que associando chaves com valores. Chaves com valores. 

Agora, neste caso simples, a nossa chaves são apenas números. Estamos implementando um hash tabela como uma matriz. E para que as teclas são 0, 1, 2, e assim por diante. E assim nós, como seres humanos, decidiu última semana que você sabe que, se estamos indo para armazenar nomes, vamos arbitrariamente, mas bastante razoável, supor que Alice, um A nome só vai ser indexado em 0. E Bob, um nome de B, será indexado em 1, e assim por diante. Então, nós tivemos um mapeamento entre entradas, que são cordas, eo hash lugares, que são números. 

Assim que o processo é geralmente conhecido como uma função de hash, e você pode realmente implementá-lo em código. Se eu quisesse implementar uma função hash que faz exatamente o que nós acabamos de descrever da última vez, eu poderia declarar uma função que recebe como entrada, por exemplo - e vamos fazer isso neste tela aqui. Se eu quisesse implementar um hash função, eu poderia dizer algo como isto. 

Vai retornar um int. Vai ser chamado de hash, e é vai aceitar como argumento um string, ou podemos ser mais adequado agora, e dizer char *, vamos chamá-lo s. E então, essa função tem que fazer, em última instância, é retornar um int. Agora, como ele faz isso pode não ser tão clara. Vou implementar isso sem qualquer forma de verificação de erros no momento. Eu só vou dizer cegamente, o retorno o que estiver à s suporte 0, menos, vamos dizer, o capital Um ponto e vírgula. 

Totalmente quebrado. Não é perfeito, porque um, o que se s é nulo? Coisas ruins vão acontecer. Dois, e se a primeira letra neste nome não é uma letra maiúscula? Isso não vai virar sair bem também. Pode ser uma letra minúscula ou não uma carta a todos. Então, totalmente espaço para melhorias aqui, mas essa é a idéia básica. 

O que descreveu na semana passada como verbalmente apenas um processo de mapeamento de Alice 0 e Bob 1 pode ser expressa certamente mais formulaically como C funcionar aqui. Chamado novamente hash recebe uma string como entrada e de alguma forma faz algo com o que a entrada para produzir uma saída. Não muito diferente de nossa descrição da caixa negra que temos feito muito. Eu não sei como isso pode ser trabalhando debaixo do capô. 

Por conjunto de problemas 6, um dos desafios é para você decidir o que será a sua função hash ser? O que vai estar dentro do que o preto caixa e, presumivelmente, vai ser um pouco mais interessante do que isso, e definitivamente mais propenso a erros verificando que este particular implementação. 

Mas podem surgir problemas, certo? Se tivermos uma estrutura de dados, tal como esta um, que é um dos problemas você pode executar ao longo do tempo em que insere mais e mais nomes no tabela hash? Você começa colisões, certo? E se você tem Alice e Aaron, duas pessoas cujos nomes aconteceu começar com um? Isso levanta a questão, onde colocar o segundo como um nome? 

Bem, você pode, ingenuamente, basta colocá-lo onde Bob pertence, mas, em seguida, Bob é tipo de ferrado se você tentar insira o seu nome ao lado e não há espaço para ele. Então você pode colocar Bob onde Charlie é, e você pode imaginar isso muito rapidamente devolvendo em um pouco de confusão. Algo linear, no final, onde você apenas tem que procurar a coisa toda à procura de Alice ou Bob ou Aaron ou Charlie. 

Então, em vez disso, propôs, em vez de apenas linearmente sondagem para espaços abertos e estatelando os nomes lá, nós propôs uma abordagem mais extravagante. Uma tabela implementada ainda com um gama de índices, mas o tipo de dados esses índices eram agora ponteiros. Ponteiros para quê? Ponteiros para listas ligadas. 

Porque lembram que uma lista ligada é na verdade, apenas um ponteiro para um nó, e o nó tem um campo seguinte, e que o nó tem um campo seguinte, e assim por diante. Então, agora você pode pensar dessa matriz em o lado esquerdo de uma tabela de Hash levando a uma lista ligada. A vantagem é que se você pegar um colisão entre Alice e Aaron, O que você faz com o segundo tal pessoa? Você acabou de ligar-lhe para o extremidade, ou mesmo o início dessa lista ligada. 

E na verdade, vamos apenas através de macarrão que por apenas um segundo. Onde faria mais sentido? Se eu inserir Alice e ela acaba em a primeira posição, então eu tento inserir o nome de Aaron, e não há obviamente uma colisão, devo colocar ele no início da lista ligada? Isso é pelo que a primeira localização, ou no final? 

AUDIÊNCIA: [inaudível]. 

DAVID MALAN: OK. Ouvi começando. Por que no início? 

AUDIÊNCIA: [inaudível]. 

DAVID MALAN: OK. É alfabética, de modo que é bom. Essa é uma boa propriedade. Ele vai me poupar algum tempo potencialmente. Ele não vai me deixar fazer busca binária, mas eu pode pelo menos ser capaz de sair de um loop, se eu perceber, bem, eu sou muito passado eram Aaron estaria nesta classificadas lista encadeada. Eu não tenho que perder meu tempo procurando todo o caminho até ao fim. Então, isso é razoável. Por que mais pode desejar inserir o nome colidindo no início da lista? O que é isso? 

AUDIÊNCIA: [inaudível]. 

DAVID MALAN: Pode levar um longo tempo a chegar ao fim da lista. E, na verdade, mais e mais. Quanto mais nomes que você insere Comece com uma, mais que cadeia vai ficar. Quanto mais tempo que ligava lista vai ficar. Então você é realmente apenas desperdiçando seu tempo. Talvez você seja melhor manter tempo de inserção constante, grande O de 1, por sempre colocando o nome de colidir em o início da lista encadeada, e não se preocupar tanto sobre a classificação. 

Qual é a melhor resposta? Não está claro. É o tipo de depende do que o a distribuição é, qual é o padrão é dos nomes que você está inserindo. Não é necessariamente uma resposta óbvia. Mas aqui, mais uma vez, é uma oportunidade de design. 

Então, em seguida, olhou para essa coisa, que é realmente a outra grande oportunidade para o p-conjunto 6. E perceber, se você não tiver já, Zamyla mergulha ambos, hash mesas e tenta, de forma mais detalhada. E o passo a passo de vídeo é incorporado em conjunto p-spec. Este foi um trie - T-R-I-E. E o que era interessante sobre isto era que o tempo de execução de procurar um nome, como Maxwell última vez, era grande O de quê? O que é isso? 

AUDIÊNCIA: O número de letras. 

DAVID MALAN: Número de letras. Ouvi duas coisas. Número de letras e de tempo constante. Então vamos com a primeira. O número de letras. Bem, esta estrutura de dados, aviso, é como uma árvore, uma árvore de família, cada um dos nós cujas são feitas de matrizes. E essas matrizes são ponteiros para outros tais nós, ou outras, tais matrizes na árvore. 

Então, se nós queríamos, então, determinar Maxwell se está aqui, eu poderia ir para a primeira matriz, no topo de a árvore, o chamado raiz, topo o trie, e então siga o ponteiro m, em seguida, a um ponteiro, então x, W, E, L, L. E então quando eu vejo algum símbolo especial, denotado aqui como um triângulo. No código você verá que nós propomos que você implementado como um bool, apenas dizendo sim ou não, a palavra pára aqui. 

Bem, uma vez que fui para a M-A-X-W-E-L-L, Parece que sete, talvez oito se formos um passado, oito passos para encontrar Maxwell. Ou vamos chamá-lo K. Mas lembre-se passado vez, argumentou que, se há realisticamente um comprimento máximo numa palavra, como alguns personagens de 40 e tantos, um comprimento máximo implica um valor constante. Então, realmente, sim, é tecnicamente grande O de 8 ou 7, ou realmente grande O de K. Mas se há um limite finito em que K pode ser, é uma constante. E por isso é grande O de 1 a no final do dia. 

Não no mundo real. Não quando você realmente começar a assistir o relógio de corrida do seu programa. É absolutamente vai ser um pouco mais lento do que verdadeiramente constante tempo com uma única etapa. Vai ser sete ou oito etapas, mas ainda é muito, muito melhor que um algoritmo como ó grande de n que depende do tamanho do que está no estrutura de dados. 

Observe a cabeça aqui é que podemos inserir mais um milhão de nomes para este estrutura de dados, mas quantos mais passos é ele que vai nos levar a encontrar Maxwell, neste caso? Nenhum. Ele é afetado. E até agora, eu não acho que nós vimos um exemplo de uma estrutura de dados ou um algoritmo que foi completamente afetado por fatores externos comportamentos como esse. Mas isso não pode ser incrível. Esta não pode ser a única solução para o p-conjunto 

E não é. Esta não é, necessariamente, os dados estrutura deve gravitar para, porque, como tabelas de hash, tradeoff. Qual é o preço que se paga aqui? Memória. Quero dizer, isso é uma atroz quantidade de memória. E você não consegue vê-lo aqui, porque o autor da imagem obviamente truncado todas as matrizes, e nós não estamos vendo muitas A e B e C e do Q e Y e Z do nestas matrizes. Mas eles estão lá. 

Cada um destes nós é uma matriz inteira de cerca de 26 ou mais bytes, cada um dos que representa uma letra. 27 em nosso caso, para que possamos apoiar apóstrofos no conjunto de problemas. Portanto, esta estrutura de dados é, na verdade, realmente densa e ampla. E isso só pode acabar retardando as coisas, ou pelo menos lhe custar uma muito mais espaço. Mas, novamente, podemos extrair comparações aqui. 

Lembre-se de um tempo atrás, nós conseguimos muito tempo de corrida mais emocionante na classificação quando usamos merge sort, mas o preço pagamos para alcançar n log n para fusão tipo exigido que nós gastamos mais que recurso? Mais espaço. Precisávamos de uma matriz secundária a copiar as pessoas para, assim como fizemos aqui no palco. Então, novamente, há claros vencedores, mas apenas projeto subjetiva decisões a serem tomadas. 

Tudo bem. Então, que tal isso? Qualquer pessoa reconhecer que D-Hall? OK. Assim, três de nós. Mather House. Portanto, esta é para um jantar de Mather. Aposto que todas as salas de jantar têm pilhas de bandejas como este. E isso é realmente representativo de algo que já obviamente, já visto. Chamámos-lhe, literalmente, uma pilha. E a pilha, em termos da sua memória do computador, é onde os dados vão enquanto as funções estão sendo chamados. 

Por exemplo, que tipo de coisas vão na pilha com respeito ao layout de memória que discutimos nas últimas semanas? O que é isso? 

AUDIÊNCIA: Chamadas para funções. 

DAVID MALAN: Eu sinto muito. 

AUDIÊNCIA: Chamadas para funções. 

DAVID MALAN: Chamadas para funções, mas especificamente, o que está dentro de cada um esses quadros? Que tipo de coisas? Sim. Assim, as variáveis ​​locais. Sempre que precisávamos de algum armazenamento local, como um argumento, ou int I, ou int temp, ou qualquer que seja o local de variável é, temos sido colocando que na pilha. E chamamos isso de uma pilha porque dessa idéia de estratificação. Apenas um tipo de jogos com realidade, o conceito da mesma. 

Mas acontece que uma pilha pode também ser visto como uma estrutura de dados, um alternativa a uma matriz, uma alternativa para uma lista ligada. Algo conceitualmente mais interessante que pode ainda ser implementado usando um desses coisas, mas é um tipo diferente de estrutura de dados de apoio, realmente, apenas duas operações. Mas você pode adicionar mais sofisticado características do que estes. Mas estes são os princípios básicos - push e pop. 

E a idéia com uma pilha é que se eu tem aqui, com ou sem Annenberg saber, uma bandeja ao lado com o número 9 nele. Então, basta um int. E eu quero empurrar este para os dados estrutura, que atualmente está vazio. Considerar este o fundo da pilha. Eu levaria esse número 9 para o empilhar, e agora ele está lá. 

Mas a coisa interessante sobre uma pilha é que se eu agora quer empurrar algum outro valor, como 17 anos, e eu empurro esta na pilha, eu vou fazer a única coisa intuitiva, eu só vou para colocá-lo exatamente onde nós, seres humanos estaria inclinado a colocá-lo, no topo. Mas o que é interessante agora é, como faço para chegar a 9? Você sabe, eu não sem algum esforço. 

Então, o que é interessante sobre uma pilha é que, ao design, é uma estrutura de dados LIFO. Estranha maneira de descrever last in, first out. Assim, o último número na nesta época tinha 17 anos. Então, se eu quiser aparecer algo fora da pilha, que só pode ser 17. Portanto, há uma ordem obrigatória de operações aqui, onde o último item em tem que ser o primeiro a sair. Daí a sigla, LIFO. 

Então, por que isso pode ser útil? São os seus contextos em que você tinha quer uma estrutura de dados como este? Bem, isso certamente foi útil no interior de um computador. Então, usar sistemas operacionais claramente esta tipo de estrutura de dados para stacks. Veremos também a mesma idéia quando se trata de páginas da web. Então, esta semana e na próxima semana e além, e como você começar a implementar web páginas em uma linguagem chamada HTML, você pode realmente usar uma estrutura de dados como isto para determinar se a página é formatada corretamente. Porque vamos ver todas as páginas seguem uma espécie de hierarquia, um recuo que, no final do dia, ser um estrutura de árvore debaixo do capô. Assim, mais do que em apenas um bit. 

Mas, por agora, vamos propor um momento, como poderíamos ir sobre representando o que é uma pilha? Deixe-me propor que implementamos uma pilha com um código como este. Assim, uma pilha vai ter dentro dela duas coisas, uma matriz, chamados de tabuleiros, apenas para ser coerente com o demo. E cada um dos itens dessa matriz vai ser um tipo int. Ea capacidade é presumivelmente o quê? Porque eu não tenho escrito o definição completa aqui. 

É, provavelmente, o máximo tamanho da matriz. E provavelmente é declarado como um forte definir, no topo do arquivo, alguns tipo de constante como implícito a mera capitalização. Assim, a capacidade é definida algures medida que o tamanho máximo possível. Enquanto isso, dentro da estrutura de dados conhecida como uma pilha haverá ser um número inteiro apenas conhecido simplesmente como tamanho. 

Então, se eu fosse para representar esta empresa pictoricamente, vamos supor que este Toda caixa preta representa a minha stack. Dentro de é duas variáveis. Então, eu vou chamar a como uma primeira dimensão. E o segundo que eu vou para desenhar como uma matriz. 

Mas apenas para manter as coisas em ordem, normalmente eu gostaria de chamar uma matriz como isso, mas é uma espécie de bom se corresponde à realidade, ou coincidir com o modelo mental. Então deixe-me em vez chamar a matriz verticalmente, o que é justo, mais uma vez, interpretação do artista. Realmente não importa o que está debaixo do capô. E vamos dizer que, por padrão, capacidade vai ser três. Portanto, este será local 0, este será de localização 1, o presente será localização 2. 

Se eu subornar com uma bola de stress, seria alguém que gosta de aparecer e executar o embarcar aqui por um momento? OK, vi o seu em primeira mão. Vamos para cima. Tudo bem. Então, eu acredito que é Steven. Vamos para cima. Tudo bem. 

Mas suponha agora que voltar à inicial estado do mundo onde eu apenas declararam uma pilha, e é vai ter uma capacidade de três. Mas o tamanho ainda não foi determinada. Bandejas ainda não foi determinada. Assim, um par de perguntas em primeiro lugar. E deixe-me dar-lhe microfone para que você possa participar mais ativamente neste processo. 

Então, o que está dentro do tamanho neste momento no tempo, se tudo o que eu tenho feito é declarou uma pilha com uma linha de código? 

STEVEN: Não muito. 

DAVID MALAN: OK, não muito. Não sabemos o que está dentro do tamanho, sabemos o que está dentro dessa matriz aqui? 

STEVEN: Apenas código aleatório, certo? Just - 

DAVID MALAN: Sim, eu vou chamá-lo de código, mas aleatória - 

STEVEN: Coisas. 

DAVID MALAN: Coisas como aleatório 

STEVEN: Bits. 

DAVID MALAN: Bits, certo? Assim, os valores de lixo, certo? Então permutações de 0 e 1 do. Restos de usos anteriores desta memória. E nós realmente não sei quais são os valores são, por isso, normalmente atraí-los como pontos de interrogação. 

Então a primeira coisa que estamos presumivelmente vai querer fazer aqui - e deixe-me dar esse campo dentro de lá um nome - bandejas. O que devemos presumivelmente inicializar tamanho para se queremos começar a usar esta pilha? 

STEVEN: Bandeja é sub 3. 

DAVID MALAN: Então, OK. Para ser claro, a capacidade é declarado em outros lugares como três. E isso é o que eu usei para atribuir a matriz. Tamanho vai referir quantos bandejas são actualmente na pilha. 

STEVEN: Zero. 

DAVID MALAN: Assim deve ser zero. Então vá em frente, e com qualquer dedo, tirar um zero em tamanho. Tudo bem. Então, agora, o que está dentro desse aqui, nós não sabemos. Estes são realmente apenas valores de lixo. Então, nós poderíamos extrair pontos de interrogação, mas vamos manter a placa limpa, por enquanto porque não importa o que está lá. Nós não precisamos de inicializar a matriz para nada, porque, se sabemos que o tamanho da pilha é igual a zero, também, nós não deve estar olhando para nada em essa matriz de qualquer maneira em Neste ponto no tempo. 

Então, suponha que eu empurrar o o número 9 na pilha. Como devemos atualizar a estrutura de dados dentro desta caixa preta? Quais valores precisam mudar? 

STEVEN: Dentro - o tamanho? 

DAVID MALAN: OK. Tamanho deve tornar-se o quê? 

STEVEN: Size seria um. 

DAVID MALAN: OK. Assim, o tamanho que se tornam um. Assim, você pode fazer isso de algumas maneiras. Deixe-me dar-lhe, agora o seu dedo é uma borracha. Tudo bem. Então agora o seu dedo é um pincel. Tudo bem. E agora, o que mais tem que mudar, obviamente, na estrutura de dados? 

STEVEN: Nós vamos a partir de de baixo para cima a 9. 

DAVID MALAN: 9. OK, Good. Então, ainda não importa o que está em localização de um ou dois, porque eles são valores de lixo, mas não deve se preocupar olhando lá porque o tamanho é dizer-nos que só o primeiro elemento é realmente legítimo. Então agora eu empurrar 17 na lista. O que acontece com esta imagem? 

STEVEN: So tamanho está indo para ir a dois. 

DAVID MALAN: OK. Você está eraser - oops. Você é uma borracha. 

STEVEN: Eraser. 

DAVID MALAN: Você é um pincel. 

STEVEN: Brush. 

DAVID MALAN: OK. E o que mais? 

STEVEN: E então nós - 

DAVID MALAN: Nós empurramos 17. 

STEVEN: Nós furamos 17 em cima, por isso - 

DAVID MALAN: OK, muito bom. 

STEVEN: - deixa-lo cair. 

DAVID MALAN: Tudo bem. Está ficando mais fácil. Eu não estou indo para ajudá-lo neste momento. Empurre 22. 

STEVEN: Concluído. Tornando-se uma borracha. Estou me tornando um pincel. E então eu estou colocando 22. 

DAVID MALAN: 22. Excelente. Assim, mais uma vez. Agora estou indo para empurrar para a pilha 26. 

STEVEN: Ooh. Oh Deus. Você realmente me pegou desprevenido. 

DAVID MALAN: Você não fez ver esta vinda? 

STEVEN: Eu não vi isso chegando. Poderíamos capacidade de re-inicial? 

DAVID MALAN: Essa é uma boa pergunta. Então, nós temos uma espécie de nós mesmos pintado em um canto aqui. Não há realmente nada de bom fora para Steven porque nós temos alocado essa matriz estaticamente, por assim dizer, dentro da estrutura de dados. E temos essencialmente codificado que seja de tamanho três. Portanto, não podemos realmente realocá-lo. 

Poderíamos se voltamos, nós redefinido bandejas para ser um ponteiro que Em seguida, usamos a memória malloc mão. Porque, se temos a memória de o monte via malloc, nós então poderia livrá-lo. Mas, antes de liberá-lo, poderíamos realocar uma fatia maior de memória, actualizar o ponteiro, e assim por diante. Mas, por enquanto, isso é realmente o melhor que podemos fazer. Push e pop são provavelmente vai ter para sinalizar um erro. 

Assim, por exemplo, a nossa implementação de impulso poderia retornar um booleano que previamente retornado verdade, verdade, verdade. Mas, pela quarta vez, ele vai ter para retornar false, por exemplo. Tudo bem. Muito bem feito. Parabéns. Você ganhou sua bola de stress hoje. 

[Aplausos] 

STEVEN: Obrigado. 

DAVID MALAN: Obrigado. OK, então isso parece não ser muito de um passo em frente, certo? Nós descrevemos esta estrutura de dados. Tem sido interessante, certo? Os sistemas operacionais gostar. Aparentemente, a web pode fazer uso desta, e outras aplicações ainda. Mas o que uma limitação estúpida que estamos voltar a uma espécie de semana dois limites onde se fixaram tamanho arrays. 

Portanto, há na verdade um par de formas que poderíamos resolver isso. Nós poderíamos alocar dinamicamente o array, não pelo difícil codificá-lo como eu feito aqui, mas re-declarando isso, só para ficar claro, como algo como isto. Int * bandejas, não decidir Ainda numa capacidade. Mas quando eu declarar a pilha em outro lugar no meu código, eu poderia então chamar malloc, obter o endereço de um pedaço de memória, e eu podia atribuir esse endereço para bandejas. 

E então, porque é apenas um pedaço de memória, eu poderia continuar a usar quadrado a notação de suporte da maneira usual. Porque mais uma vez, há uma espécie de presente equivalente funcional de matrizes e blocos de memória que vêm volta de malloc. Podemos tratar um como o outro usando a aritmética de ponteiro ou notação de colchete. Então essa é uma abordagem. 

Mas de que outra forma poderíamos implementar esta mesma estrutura de dados, podendo? Certo? Eu sinto que nós apenas resolveu este problema como há uma semana. Qual foi a solução para este problema que Steven correu? Listas ligadas entre si, certo. 

Se o problema é que estamos pintando nos para um canto, alocando antecipadamente muito pouca memória que em seguida, ter de lidar de alguma forma com o bem, porque não basta evitar que emitir por completo? Porque não basta declarar bandejas para ser um ponteiro para um nó, ergo uma lista ligada, e depois simplesmente alocar novos nós cada vez que Steven necessária para atender a uma Número na estrutura de dados. 

Assim, a imagem teria que mudar. Não vai ser tão limpo e tão simples como um conjunto de três inteiros. Agora vai ser um ponteiro para um struct, e que struct vai ter um int e um ponteiro próximo. Vai levar através desse ponteiro para outra estrutura para tal outro tal estrutura. Assim, o quadro seria realmente ficar um pouco mais confusa. E teríamos setas amarrando tudo juntos. 

Mas isso é bom, certo, porque vimos como fazer isso. E uma vez que você se sentir confortável implementar algo como um linked lista, que você vai ter que fazer se você optar por implementar uma tabela hash com encadeamento separado para p-set 6, você pode usá-lo como um bloco de construção, ou um ingrediente, ou em Scratch dizer, um procedimento, algo que você colocar, você criou sua própria peça do puzzle , que você pode reutilizar. Compensações que sim, mas as possíveis soluções que temos realmente visto antes. 

Então, muitas vezes, você vê isso todos os ano ou dois, quando lançamentos da Apple algo novo, e todas as pessoas loucas linha do lado de fora da Maçã loja para comprar seu marginal atualizar no hardware. Digo isso, está tudo bem, porque Eu sou uma dessas pessoas. Então, que tipo de estrutura de dados pode representar essa realidade? 

Bem, vamos chamá-lo de uma fila, uma linha. So British chamaria isso tipicamente um fila de qualquer jeito, por isso é um bom nome. E as duas operações que a fila apoia vamos chamar a enfileirar operação e uma operação de remoção da fila, que são semelhantes em espírito de push e pop. É apenas uma espécie de diferente em convenção, o que estamos chamando esses. Mas, para enfileirar algo significa para adicionar ou inseri-lo na estrutura de dados. Para desenfileirar meios para removê-lo. Mas, enquanto uma pilha era um dos dados LIFO estrutura, uma fila é um primeiro, pela primeira vez a estrutura de dados. 

Se você é a primeira pessoa na fila, você será a primeira pessoa a chegar fora da linha e comprar o seu novo dispositivo. Imagine o quão chateado essas pessoas seria se a Apple em vez usou uma pilha, para exemplo, para implementar a colheita up do seu novo brinquedo. Então filas fazem sentido, certamente, e podemos pensar em todos os tipos de aplicações, presumivelmente, para filas, especialmente quando você quer justiça. Então, como podemos implementá-las como uma estrutura de dados? 

Bem, eu proponho que possamos precisa fazê-lo desta forma. Então, eu vou agora ter números. Então, vamos manter as coisas simples e não necessariamente falar em termos de bandejas. Apenas números que as pessoas de começado. Capacidade vai, mais uma vez, corrigir o número total de pessoas que podem estar em Nesta linha, como três ou qualquer outro valor. 

Mas proponho que eu preciso para manter o controle não apenas do tamanho da fila, quantas coisas estão na mesma. Assim, o tamanho é o tamanho atual, a capacidade é o tamanho máximo. Assim de novo, a nomenclatura por convenção. Por que eu preciso de um int adicional dentro de uma fila para acompanhar o que está em frente da linha? Por que eu preciso fazer isso neste caso? 

Bem, como é esta imagem vai mudar? Eu provavelmente pode reutilizar mais da imagem. Deixe-me ir em frente e apagar o que está aqui. Nós vamos dar a este um pouco nome diferente aqui. Vamos nos livrar dos 17, vamos nos livrar do 9, vamos nos livrar do 3. E vamos adicionar uma outra coisa. Proponho que eu preciso para manter o controle de a frente da lista, que é apenas vai ser um int bem. E nós vamos mantê-lo simples. Nenhuma lista ligada por agora. 

Vamos admitir que vamos bater-se contra este limite. Mas o que eu quero ver acontecer desta vez? Então, suponhamos que eu vá em frente e no primeiro pessoa vem na linha, e é o número 9. Temos bolas de stress. Posso roubar, digamos, duas ou três pessoas? Um, dois, três? Vamos para cima. Direito de frente, porque nós vamos fazer este rápida. 

Cada um de vocês é agora vai ser um menino fã na fila da Apple. Você não vai receber o hardware da Apple no final deste embora. Tudo bem. Então, você é o número 9, você está número 17, número 22. Estes são números arbitrários, como IDs de estudante ou outros enfeites. E em apenas um momento, vamos começar para começar a adicionar as coisas. E eu vou correr o conselho aqui neste momento. 

Portanto, neste caso, eu já inicializada a frente para ser - Na verdade, eu realmente não me importo com o que o frente é, porque o tamanho é igual a zero. Portanto, este pode muito bem ser um ponto de interrogação. Estes são todos os pontos de interrogação. Então, agora nós vamos realmente começar a ver alguns pessoas fazendo fila na loja. 

Então, se o número 9, você é o primeiro lá 05:00, vá em frente e alinhar, ou na noite anterior. OK. Então agora 9 é aqui. Assim 9 é na frente da lista. Então, eu estou indo para ir em frente e atualizar o tamanho dos dados actuais estrutura para não ser mais 0, mas para ser 1. Eu vou colocar 9 na frente da lista. Deixe-me ir em frente e alternar a tela assim podemos ver por nós aqui. 

E agora o que eu quero para colocar em frente? Vou manter o controle que o frente da fila agora está na posição 0. Porque o que está próximo vai acontecer? Bem, suponho que agora eu enfileirar 17 também. Então hop em linha lá. E, novamente, o tipo de porta para o loja vai estar aqui. Então agora eu adicionei 17. E mesmo que esses caras estão bloqueando da tela, que é OK, porque podemos vê-lo aqui. Desculpe. 

AUDIÊNCIA: Nós podemos mudar - 

DAVID MALAN: Não, isso é OK. É enorme lá em cima. Assim, é agora 17 dentro da fila. Eu preciso atualizar o que campos agora que? OK, definitivamente tamanho. E quanto a frente? OK, não. Frente não deve mudar, porque ao contrário de uma pilha, quer manter a equidade. Então, se 9 ficou em primeiro lugar, queremos 9 para ser o primeiro a sair da linha e para a loja. 

Na verdade, vamos ver isso. Antes de inserir 22, vamos vá em frente e dequeue 9. Qual é o seu nome? 

AUDIÊNCIA: Jake. 

DAVID MALAN: Jake vai para ser será agora. Então você começa a entrar na loja. E fingir que a loja está ali. Então, agora o que precisa - dit-dit-dit! O que precisa acontecer agora? Decisão de projeto. Então, não é um mau instinto, mas - qual é o seu nome? 

AUDIÊNCIA: David. 

DAVID MALAN: David. Então, o que fez Davi? Ele estava tentando resolver de corrigir os dados estrutura e movimento a partir de sua localização na antiga localização do Jake. E isso é bom, se estamos dispostos para aceitar isso como uma detalhe de implementação. Mas, primeiro, vamos atualizar os dados estrutura antes de fazer isso. Porque eu não estou gostando da idéia de tudo as pessoas deslocando nesta linha. 

Não é grande coisa se David faz com um passo, mas, novamente, acho que volta a quando tivemos oito voluntários na palco e fizemos como inserção tipo, em que nós tivemos que começar movendo-se todos ao redor. Isso tem cara, certo? Isso faz-me encolher sobre O grande de n, grande O de n ao quadrado novamente. Ele não está se sentindo como um resultado ideal. 

Então vamos atualizar isso. Assim, o tamanho da fila já não é 2. Agora é simplesmente um. Mas agora eu posso atualizar algo Eu não atualizar antes, a frente da lista. Eu poderia apenas dizer, é que uma localização? Portanto, agora temos valor de lixo aqui, valor de lixo aqui, e David no meio desse lixo. Mas, a estrutura de dados ainda está intacto. 

E, na verdade, eu nem preciso mudar ex-número um do Jake 9, porque quem se importa. Eu tenho bastante informação agora no tamanho que eu sei que há uma pessoa em essa fila. E eu sei que essa pessoa está na posição 1, e não 0. Eu não estou contando. Assim, um bem. Assim, a estrutura de dados ainda é OK. 

Bem, o que acontece? Vamos enfileirar - qual é o seu nome? 

AUDIÊNCIA: Callen. 

DAVID MALAN: Callen. Vamos enfileirar uma Callen, e 22 está agora na fila. Então, agora o que tem que mudar aqui? Frente não vai mudar, obviamente. Tamanho vai mudar para ser 2 novamente. E 22 acaba aqui, 9 ainda está presente, mas é efetivamente um valor de lixo agora. É apenas um remanescente de Jake passado. 

Então agora o que acontece se Eu desenfileirar David? Uma última operação, dequeue David. Poderíamos mudar, mas proponho vamos fazer tão pouco trabalho quanto possível. Agora, a minha estrutura de dados vai trás em tamanho de 2 para 1. Mas a frente da fila agora torna-se 2. Eu não preciso mudar esses números mas apenas, porque eles são apenas os valores de lixo. 

Mas, agora, o que acontece? Suponha que eu me enfileirar, 26? Eu sinto que eu pertenço aqui. Então, eu estou sendo enfileirado. Então eu meio que pertenço aqui. E mesmo que você não faz bem apreciar este visual no palco, porque temos muito espaço, eu deveria não estar aqui, por quê? 

AUDIÊNCIA: Você está fora dos limites. 

DAVID MALAN: Certo. Estou fora dos limites. Eu indexado além do limites desta matriz. Eu realmente deveria estar em um dos três localizações possíveis. Agora, onde é mais natural para ir? Proponho que alavancou uma semana um truque. O operador mod, porcentagem. Porque eu estou tecnicamente em pé na localização 3, mas eu faço 3 capacidade mod, para 3, um sinal de porcentagem, 3 - capacidade é 3. O que é isso? Qual é o resto quando você dividir 3 por 3? 0. 

Assim que me põe foram Jake era, o que é realmente bom. Então, agora a implementação dessa coisa vai ser um pouco de dor de cabeça. É realmente apenas uma linha de dor de cabeça, de código. Mas pelo menos agora há lixo valor aqui, mas há dois ints legítimos aqui. E eu afirmo que agora temos feito exatamente o que precisa fazer, desde que podemos mudar o que Jake valor seria 26. 

Agora temos informação suficiente ainda para manter a integridade esta estrutura de dados. Nós ainda estamos meio fora de sorte quando nós deseja inserir quatro ou mais Total elementos, mas posso pelo menos fazer muito utilização eficiente da presente constante tempo, na verdade. Eu não precisa se preocupar com mudança todos, como inclinação de Davi era. 

Qualquer dúvida sobre pilhas, ou esta fila? 

AUDIÊNCIA: É a razão pela qual você precisa de tamanho para que você saiba onde se tem uma pessoa? 

DAVID MALAN: Exatamente. Eu preciso saber o tamanho da matriz porque eu preciso saber exatamente como Muitos desses valores são legítimas, e para que eu possa encontrar onde colocar a próxima pessoa. Exatamente. O tamanho é - Na verdade, nós não atualizar isso ainda. Eu me adicionado aos 26 anos. O tamanho é agora, não um, mas dois. Então, agora este fato me ajuda a encontrar o cabeça de lista, o que não é 0, não 1, mas é 2. A parte dianteira da lista é de facto o número 22. Porque ele ficou em primeiro lugar, então ele deve ser autorizados a entrar na loja antes de mim, apesar de visualmente eu estou mais perto da loja. 

Tudo bem? Uma salva de palmas para esses caras e nós vamos deixá-los de lá. 

[Aplausos] 

DAVID MALAN: eu poderia deixar você mantenha a bandeja. Pudemos ver o que acontece se você quer, mas talvez não. Tudo bem. Então, o que agora é que isso nos deixa? Bem, deixe-me propor que há um algumas outras estruturas de dados que poderiam começar a adicionar ao nosso kit de ferramentas que vão realmente ser muito, muito relevante como nós mergulhar em coisas web. Que por sua vez, tem algum tipo de ligação a árvores, sob a forma de algo chamado DOM, documento modelo de objeto. Mas vamos ver mais de que em pouco tempo. 

Deixe-me propor que por definição chamar árvore agora o que você pode saber como mais de uma árvore de família, onde você ter algum antepassado na raizes da árvore. A matriarca patriarcal ou na o topo da árvore. Sem o seu cônjuge, neste caso. Mas agora temos que chamaremos crianças, que são os nós que pendem fora o filho esquerdo ou o direito da criança, setas como descrito aqui. 

Em outras palavras, uma estrutura de dados em árvore em computador, uma árvore tem zero ou mais nós. Se ele tem pelo menos um nó, que é chamado de raiz. É as coisas visualmente que traçamos no topo. E esse nó, como qualquer outro nó, pode ter zero, uma ou duas, ou três, ou quantos filhos o estrutura de dados suporta. Neste caso, a raiz, o armazenamento valor um, tem dois filhos, 2 e 3, assim que nós geralmente chamamos de 2 a esquerda criança e 3 a criança certa. 

E então, quando chegarmos a 5, 6 e 7, 6 pode ser chamado o filho do meio. Se você tiver quatro filhos, ele fica confuso. Então, pare de usar esse tipo de atalho verbalmente. Mas é realmente apenas uma árvore genealógica. E as folhas aqui são os nós que eles próprios não têm filhos. Eles ficam fora da parte inferior da árvore. 

Então, como podemos implementar uma árvore que tem apenas dois filhos maximamente? Vamos chamá-lo de uma árvore binária. Bi novamente significando dois, neste caso, como com binário. E, por isso, pode ter zero, uma ou os dois filhos maximamente. 

Vou propor que vamos implementar o nó para essa estrutura, com um int n, e, em seguida, dois apontadores, um chamado à esquerda, um chamado para a direita. Mas esses são apenas bom convenções arbitrárias. E o que é bom agora, especialmente se você tipo de dificuldade conceitual com recursão, ou pensado que não era realmente uma solução para nada, especialmente se você pudesse sem memória. Agora que estamos falando de dados estruturas e algoritmos que permitem nos a atravessar e manipulá-los, Acontece que a recursividade volta em uma muito mais atraente se não for belo caminho. 

Então, isso eu proponho é a implementação de uma função de pesquisa. Dadas duas entradas - por isso pense nisso como uma caixa preta. Dadas duas entradas, N, um int, e um ponteiro para uma árvore, um ponteiro para uma nó, ou realmente a raiz de uma árvore, eu alegação de que esta função pode retornar verdadeira ou falsa, isto valor n É dentro desta árvore. 

O que tem dentro dessa caixa preta? Bem, quatro ramos. O primeiro apenas verifica. Se a árvore é nula, basta retornar falso. Se não houver nenhum nó, não há n, não há nenhum número, só retornará false. Se, porém, n, o valor que você está procurando para, é menor do que a árvore seta ne só para ficar claro, o que ele quer dizer quando Eu escrevo árvore e, em seguida, a seta notação, n? Exatamente. Isso significa que desreferenciava ponteiro chamado árvore. Vá lá, e, em seguida, entrar dentro de que nó e obter o seu campo chamado n. E, em seguida, comparar o n real que foi passou para Pesquisa contra ele. 

Assim, se n for menor do que o valor n no próprio nó da árvore, assim, O que isso significa? Isso não significa nada à primeira vista. Certo? Assim como quando você tem um conjunto de valores, você pode gostar de aplicar binário pesquisa como uma forma de divisão e conquistar. Mas o pressuposto de que nós precisamos fazer para pesquisa binária para trabalhar em conjunto no livro de telefone e exemplos anteriores? 

Como ser classificados. Então, vamos refinar a definição de árvore aqui para não ser apenas uma árvore, que pode ter qualquer número de filhos. Não é apenas uma árvore binária, o que pode ter 0, 1 ou 2 maximamente. Mas, como uma árvore de busca binária, ou BST, que é apenas uma maneira elegante de dizer a árvore binária de tal forma que de cada nó filho esquerdo, se presente, é menos do que o nó. E criança o direito de cada nó, se estiver presente, é maior do que o próprio nó. 

Portanto, em outras palavras, se você fosse desenhar a saída da árvore, todos os números são cuidadosamente equilibrado como este, para que se você tem 55 como a raiz, de 33 anos pode ir à sua esquerda, porque é inferior a 55. 77 pode ir para o seu direito, porque é superior a 55. Mas, agora, perceber, a mesma definição, é uma definição recursiva verbalmente, tem de pedir 33. 33 do filho esquerdo deve ser menor do que, e direito da criança de 33, 44, deve ser maior do que isso. 

Portanto, esta é uma árvore de busca binária, e Proponho, usando um pouco de recursão, agora podemos encontrar n. Assim, se n for menor do que o valor de n, que é nó atual, eu estou indo para ir frente e punt, por assim dizer, e apenas devolver qualquer que seja a resposta é de procura de n no filho esquerdo da árvore. Observe mais uma vez, esta função só espera uma estrela nó, um ponteiro para um nó. Então, certamente eu só posso fazer árvore seta para a esquerda, o que levará me para outro nó. Mas o que é esse nó? 

Bem, de acordo com esta declaração, esquerda é apenas um ponteiro, de modo que apenas Significa que eu estou passando para a função de pesquisa um indicador diferente, nomeadamente o que representa um árvore do meu filho esquerdo. Portanto, neste caso, o ponteiro a 33, se esta é a nossa amostra de entrada Entretanto, se n é maior do que o valor de n no nó atual na árvore, então eu estou indo para ir em frente e punt na outra direção e dizer, eu não sabe se este valor n está na árvore, mas eu sei que se é, é a minha ramo direito, por assim dizer. Então deixe-me chamar recursivamente procurar, passar um n novamente, mas passando uma ponteiro para o meu filho direito. 

Em outras palavras, se eu estou atualmente em 55 e eu estou à procura de 99, eu sei que 99 é maior do que 55, então como eu rasguei o livro de telefone há semanas e nós foi para a direita, da mesma forma somos nós vai dar certo aqui. E eu não sei se é a minha direita criança, e não é, de 77 está lá, mas Eu sei que é nessa direção. Então, eu chamo de busca no meu filho direito, 77, e que a figura de pesquisa a partir lá se 99 deste arbitrária exemplo é realmente lá. 

Senão, o que é o caso final? Se a árvore é nula é um caso. Se n for menor do que a corrente do nó valor é outro caso. Se n for maior do que o actual valor do nó é um terceiro caso. O que é o quarto e último caso? Acho que estamos fora dos casos, certo? Deve ser, em que n é o nó atual que estou. 

Então, se eu estou procurando 55 neste momento na história, esse ramo da árvore voltaria verdade. Então, o que é interessante aqui é que nós na verdade, ao contrário de semana passado, nós meio de ter dois casos base. E, eles não têm a ficar no topo. O topo é um caso base, porque se o árvore é nulo, não há nada a fazer. Basta retornar um disco codificado valor false. 

O ramo inferior é uma espécie de padrão, pelo qual se tenha verificado para nulo, temos verificado se ele deve ser para a esquerda, mas não deve ser, temos verificado se ele deve estar certo, mas não deve ser, claramente, tem de ser exatamente onde estamos. Isso é um caso base. Portanto, há dois casos recursivas entalado lá no meio. Mas eu poderia ter escrito isto em qualquer ordem. Eu apenas pensei que tipo de me pareceu natural primeiro verificar um possível erro, em seguida, verifique a esquerda, em seguida, verifique bem, então supor que você está no nó você está realmente procurando. 

Então, por que isso pode ser útil? Assim, verifica-se - e deixe-me ir para um teaser aqui que está na web. Nós vamos começar a utilizar não é uma linguagem de programação no início, mas a linguagem de marcação. A linguagem de marcação que é ser um similares em espírito à programação linguagem, mas ele não lhe dá o capacidade de se expressar de forma lógica. Ele só lhe dá a capacidade de expressar-se estruturalmente. 

Onde você quer colocar algo na página, a página da web? Qual a cor que você quer fazer isso? O tamanho da fonte que você quer fazer isso? Que palavras você realmente quer na página web? Então essa é uma linguagem de marcação. Mas, então, vamos apresentar muito rapidamente JavaScript, que é um verdadeiro linguagem de programação. Muito semelhante sintaticamente na aparência a C, mas vai ter algum bom, mais poderoso, mais características de fácil utilização. 

E uma das frustrações neste ponto no semestre é que vamos em breve implementar speller em muito menos linhas de código, utilizando outras linguagens que a própria C permite, mas por motivo de em breve iremos entender. Este será o primeiro tal página web. Será completamente abaixo do esperado, o primeiro que fazemos. Ele vai simplesmente dizer: Olá mundo. Mas se você nunca viu antes, este é HTML, HyperText Markup Language. 

Se você vai a uma determinada opção de menu em mais qualquer browser, em qualquer página web em a internet, você pode ver o HTML que algumas pessoas escreveram para criar essa página web. E provavelmente não parece tão breve ou tão puro como este. Mas vai seguir o padrão desses colchetes abertos e barras e letras e números. potencialmente 

Pensei em dar-lhe um teaser do que você vai ser capaz de fazer depois de tomar CS50. Deixe-me ir para cs.harvard.edu / roubar, página inicial nossa própria Rob Bowden. Ele fez isso por nós. Assim, em breve você vai ser capaz de fazer isso. E também, o que você ouviu esta manhã - o que você ouviu esta manhã - 

[HAMSTER DANCE MUSIC] 

- Você será capaz de fazer isto. Que nos espera na quarta-feira. Vamos vê-lo em seguida. 

[HAMSTER DANCE MUSIC] DAVID MALAN: Na próxima CS50 -