[Música tocando] DAVID MALAN: Este é CS50. E isto é tanto o início eo end-- como literally-- quase o final de seis semanas. 

Eu pensei que eu iria partilhar um pouco de um fato divertido. Eu puxei isso a partir de um dados do semestre passado definido. Você deve se lembrar que pedimos que em cada forma conjunto p se você assistiu on-line ou se você já assistiu em pessoa. E aqui são os dados. Então, hoje foi muito previsível. Mas queríamos passar um pouco de tempo com você, no entanto. Alguém gostaria de conjecturar por que isso gráfico é tão irregular, até para baixo, para cima para baixo, de forma consistente? O que cada um dos picos e depressões representam? 

AUDIÊNCIA: [inaudível] DAVID MALAN: De fato. E mais divertidamente, Deus me livre, temos uma palestra na sexta-feira no início do semestre, isso é o que vemos acontecer. Então, hoje, nós participamos de um pouco mais sobre estruturas de dados. E, para dar-lhe mais de um sólido modelo mental para problemas em cinco, que agora está fora. Erros de ortografia, no qual, nós vamos entregar-lhe um arquivo de texto alguns 100.000 mais palavras em inglês, e você vai ter para descobrir como para carregá-los de forma inteligente em memória, na memória RAM, utilizando-se alguns dados estrutura de sua escolha. 

Agora, uma tal estrutura de dados poderia ser, mas provavelmente não deve ser, a lista ligada bastante simplista, que introduzimos última vez. E uma lista ligada tinham pelo menos uma vantagem sobre uma matriz. O que é uma vantagem de uma lista ligada, sem dúvida? 

AUDIÊNCIA: Inclusão. 

DAVID MALAN: Inclusão. O que você quer dizer com isso? 

AUDIÊNCIA: Em qualquer lugar ao longo lista [inaudível]. 

DAVID MALAN: Good. Assim, você pode inserir um elemento sempre você quer no meio da lista sem ter que embaralhar qualquer coisa, que concluiu, em nossa classificação discussões, não é necessariamente uma coisa boa, porque leva tempo para realmente se mover todos os seres humanos para a esquerda ou para a direita. E assim, com uma lista ligada, você pode apenas alocar com malloc, um novo nó, e, em seguida, atualizar um par de pointers-- dois, três operações max-- e nós somos capazes de encaixar alguém em qualquer lugar em uma lista. 

O que mais foi vantajoso cerca de uma lista ligada? Sim? 

AUDIÊNCIA: [inaudível] DAVID MALAN: Perfeito. Perfeito. É muito dinâmico. E que você não está cometendo, antecipadamente, até certo tamanho fixo pedaço de memória, como você teria para com uma matriz, o cabeça de que é que você pode alocar os nós apenas em demanda utilizando assim apenas a quantidade de espaço como você realmente precisa. Em contraste com um array, você pode acidentalmente alocar muito pouco. E depois é só ir ser uma dor no pescoço para realocar uma nova matriz maior, copiar tudo mais, liberar a matriz velha, e depois passar sobre o seu negócio. Ou pior, você pode alocar forma mais memória do que você realmente precisa, e assim você vai ter uma muito matriz escassamente povoada, por assim dizer. 

Assim, uma lista ligada dá-lhe estas vantagens de dinamismo e flexibilidade com inserções e deleções. Mas certamente deve haver um preço a pagar. De fato, um dos temas explorada no questionário de zero era um par de os trade-offs temos visto até agora. Então, o que é um preço pago ou a desvantagem de uma lista ligada? Sim. 

AUDIÊNCIA: Sem acesso aleatório. 

DAVID MALAN: Sem acesso aleatório. Mas quem se importa? De acesso aleatório não soa convincente. 

AUDIÊNCIA: [inaudível] DAVID MALAN: Exatamente. Se você quer ter um certo algorithm-- e deixe-me realmente propor pesquisa binária, em particular, que é um que usei muito bit-- se você não tem acesso aleatório, você não pode fazer isso aritmética simples de como encontrar o elemento do meio e pulando direito a ela. Você não tem que começar na primeira elemento e linearmente busca de esquerda para a direita, se você quer encontrar a média ou de qualquer outro elemento. 

AUDIÊNCIA: Provavelmente ocupa mais memória. 

DAVID MALAN: ocupa mais memória. Onde é que adicional custar vindo de na memória? 

AUDIÊNCIA: [inaudível] DAVID MALAN: Exatamente. Neste caso aqui, tivemos uma lista encadeada de números inteiros, e ainda estamos dobrando a quantidade de memória precisamos também por armazenar esses ponteiros. Agora menos de um grande negócio como suas estruturas ficam maiores e você está armazenando não um número, mas talvez um estudante ou algum outro objeto. Mas o ponto certamente permanece. E assim um certo número de operações em listas ligadas foram chamados eram grandes O linear de n--. Coisas como inserção ou busca ou exclusão no caso de um elemento Aconteceu no final da a lista se ele está classificado ou não. 

Às vezes você pode ter sorte e em limites tão baixos sobre estas operações pode também ser de tempo constante, se você estiver sempre olhando para o primeiro elemento, por exemplo. Mas, afinal, que prometeu para alcançar o Santo Graal de estruturas de dados, ou alguns destes aproximação, por meio de constante de tempo. Podemos encontrar elementos ou adicionar elementos ou remover elementos de uma lista? Veremos em breve. E verifica-se que um dos mecanismos que estamos vai começar a usar hoje, utilização anual em p definir cinco, é realmente muito familiar. Por exemplo, se este é um grupo livros de exame, cada um dos quais tem um aluno de primeira nome e último nome, e eu buscá-las a partir de no final de um exame, e todos eles são bastante muito em uma ordem aleatória, e queremos ir sobre a classificação esses exames, de modo que, uma vez classificado é apenas muito mais fácil e mais rápido para entregá-los de volta para fora para os alunos em ordem alfabética. O que seus instintos ser para uma pilha de exames como este? 

Bem, se você é como eu, você pode ver que isso é m, então eu vou espécie de colocar isso em, se esta é a minha mesa ou o meu andar, onde Estou espalhando coisas out-- ou minha matriz realmente-- Eu poderia colocar todo o Ms lá dentro. Oh. Aqui está um A. Então eu poderia Como colocar os aqui. Oh. Aqui está outro A. Vou colocar isso aqui. Aqui está um Z. Aqui está outro M. E assim Eu poderia começar a fazer pilhas como esta. E então talvez eu iria mais tarde e tipo de muito detalhista-ly tipo as pilhas individuais. Mas o ponto é que eu ficaria na entrada que eu sou destro e eu gostaria de fazer algum calculado decisão com base nessa entrada. Se ele começa com A, colocá-lo lá. Se ele começa com Z, colocá-lo sobre lá, e tudo mais. 

Portanto, esta é uma técnica que é geralmente conhecido como hashing-- H-A-S-h-- o que geralmente significa tomar como de entrada e usando que a entrada para calcular um valor, geralmente, um número, e que número é o índice para um dispositivo de armazenamento recipiente, como uma matriz. Portanto, em outras palavras, eu poderia ter um função de hash, como eu faço na minha cabeça, que, se eu vejo alguém é nome que começa com A, Eu estou indo para mapear que a zero na minha cabeça. E se eu vejo alguém com Z, eu sou vai mapear que a 25 na minha cabeça e, em seguida, colocar isso em o último mais pilha. 

Agora, se você pensar em não meu cérebro Mas um programa C, o que os números poderiam você confiar para atingir esse mesmo resultado? Em outras palavras, se você tinha o caráter ASCII A, como é possível determinar o balde para colocá-lo? Você provavelmente não quer colocá-lo em balde de 65 anos, que Seria como lá sem uma boa razão. Onde você quer colocar um em termos de seu valor ASCII? Onde você quer fazer para o seu ASCII valor para chegar a um balde de forma mais inteligente para colocá-lo em? 

AUDIÊNCIA: Minus A. 

DAVID MALAN: Yeah. Assim, menos um ou menos especificamente 65 se é um capital A. Ou 98 se é uma minúscula a. E assim que nos permitem, muito de forma simples e muito aritmeticamente, colocar algo em um balde assim. Então não é que realmente fazemos este bem mesmo com os quizzes. 

Assim, você pode se lembrar você circulou seu Nome ensino companheiro na capa. E os nomes do TF foram organizadas estas colunas em ordem alfabética, Bem, acredite ou não, quando todos 80 mais de nós se reuniram na outra noite para grau, o último passo no nosso processo de classificação é para picar os questionários em uma grande espaço de chão no [inaudível] e estabelecer quizzes de todos para fora exatamente na ordem de seus TF de nomes na capa, pois então é muito mais fácil para nós a busca através de que o uso linear procurar ou algum tipo de inteligência para um TF para encontrar o seu ou quizzes dos seus alunos. 

Então, essa idéia de hashing que você verá é bastante poderoso é realmente muito banal e muito intuitiva, muito parecido, talvez, e dividir conquista foi na semana zero. Eu avanço rápido para a hackathon um par de anos atrás. Este foi Zamyla e um par de outros alunos saudação pessoal como eles entraram. E nós tivemos um monte de dobradura mesas lá com etiquetas de nome. E nós tínhamos as etiquetas de nome organizado com como os Como por lá eo Zs lá. E assim um dos TFs muito inteligente escreveu isso como as instruções para o dia. E na semana 12 do semestre este tudo fez sentido perfeito e todos sabia o que fazer. Mas sempre que tenho enfileirados na mesma maneira, você está implementando o mesma noção de um hash. Então, vamos formalizar-lo um pouco. Aqui é uma matriz. Ele é desenhado para ser um pouco grande apenas para descrever, visualmente, para que possamos colocar cordas em algo como isto. E essa matriz é claramente de tamanho 26 total. E a coisa é chamado mesa de forma arbitrária. Mas esta é apenas capitulação de um artista do que uma tabela hash pode ser. 

Assim, uma tabela hash agora vai ser uma estrutura de dados de nível superior. No final do dia estamos prestes a ver que você pode implementar uma tabela hash, que é muito parecido com a linha de check-in a uma hackathon muito parecido com este tabela usada para classificar os livros de exame. Mas uma tabela hash é espécie de presente de alto nível conceito que poderia usar uma matriz debaixo do capô para implementá-lo, ou pode usar uma lista de comprimento, ou mesmo talvez algumas outras estruturas de dados. E agora que é a tomada theme-- alguns destes ingredientes fundamentais como um array e este edifício bloquear agora de uma lista de comprimento e ver o que mais podemos construir em cima de quem, como ingredientes em uma receita, tornando cada vez mais resultados finais interessantes e úteis. 

Assim, com a tabela hash podemos implementá-lo na memória pictoricamente como este, mas como pode ele realmente ser codificado em cima? Bem, talvez simplesmente como é isso. Se a capacidade em todas as tampas, é apenas alguns constant-- por exemplo 26, para 26 letras do alphabet-- Eu poderia chamar de minha mesa variável, e eu poderia afirmar que eu vou colocar estrelas de char lá, ou string. Por isso, é tão simples como isso se você deseja implementar uma tabela hash. E, no entanto, isso é realmente apenas uma matriz. Mas, novamente, um hash tabela é agora o que vamos chamar um tipo abstrato de dados que é apenas uma espécie de estratificação conceitual no topo de algo mais mundano agora como um array. 

Agora, como é que nós vamos sobre a resolução de problemas? Bem, no início eu tive o luxo de ter espaço suficiente mesa aqui para que eu pudesse colocar o quizzes em qualquer lugar que eu queria. Então, como pode ir aqui. Zs pode ir aqui. Ms pode ir aqui. E então eu tive um pouco de espaço extra. Mas isso é um pouco de um direito de fraude agora, porque esta tabela, se eu realmente pensei nisso como uma matriz, é apenas vai ser de cerca de tamanho fixo. 

Então, tecnicamente, se eu puxar se questionário de outro aluno e ver, oh, esta pessoa de nome começa com um A também, Eu meio que quero colocá-lo lá. Mas assim que eu colocá-lo lá, se esta tabela de facto representa uma matriz, Eu vou estar substituindo ou sobrepor quem questionário deste aluno é. Certo? Se este é um array, só uma coisa pode ir em cada uma destas células ou elementos. E então eu meio que tenho de escolher. 

Agora antes que eu tipo de enganado e fez isso ou eu apenas uma espécie de empilhados -los por cima da outra. Mas isso não vai voar no código. Então, onde eu poderia colocar o segundo aluno cujo nome é A, se tudo o que eu tinha é este disponível espaço de tabela? E eu usei três slots e que Parece que há apenas alguns outros. O que você poderia fazer? AUDIÊNCIA: [inaudível] DAVID MALAN: Yeah. Talvez vamos mantê-lo simples. Certo? Ela não se encaixa onde eu quero colocá-lo. Então, eu vou colocá-lo tecnicamente, onde um B iria. Agora, é claro, eu estou começando a pintar-me em um canto. Se eu chegar a um estudante cujo nome é, na verdade, B, agora B vai ser movido um pouco para a frente, como pode acontecer, sim, se este é um B, agora ele tem que ir aqui. 

E por isso esta muito rapidamente poderia tornar-se problemático, mas é uma técnica que, na verdade, é referido como linear de sondagem, em que você considerar apenas o seu matriz de ser ao longo da linha. E você só tipo de sonda ou inspecionar cada elemento disponível à procura de um local disponível. E assim que você encontrar um, você largá-lo lá dentro. 

Agora, o preço a ser pago agora para esta solução é o quê? Nós temos uma matriz de tamanho fixo, e quando eu inserir nomes para ele, pelo menos inicialmente, o que é o tempo de execução de inserção para colocar os alunos quizzes nos baldes certo? Big O de quê? 

AUDIÊNCIA: n. DAVID MALAN: Eu ouvi grande O de n. Não é verdade. Mas nós vamos provocar uma separação por que em apenas um momento. O que mais poderia ser? 

AUDIÊNCIA: [inaudível] DAVID MALAN: E deixe-me fazê-lo visualmente. Então, suponhamos que esta é a letra S. 

AUDIÊNCIA: É uma. DAVID MALAN: É uma. Certo? Esta é uma matriz, que significa que temos acesso aleatório. E se pensarmos dessa como zero e isso como 25, e percebemos que, oh, aqui está a minha entrada S, Eu certamente posso converter S, um caractere ASCII, a um número correspondente entre zero e 25 e, em seguida, imediatamente colocá-lo onde ele pertence. 

Mas, claro, assim que eu chegar ao segunda pessoa cujo nome é A ou B ou C eventualmente, se eu usei o linear sondagem como a minha solução, o tempo de execução inserção no pior caso é realmente vai transformar-se em quê? E eu ouvi-lo aqui corretamente desde o início. AUDIÊNCIA: [inaudível] DAVID MALAN: Assim é, de facto, uma vez n você tem uma suficientemente grande conjunto de dados. Assim, por um lado, se a matriz é grande o suficiente e seus dados é escassa o suficiente, você obter este tempo constante bonito. Mas assim que você começar a ficando mais e mais elementos, e apenas estatisticamente que você começa mais pessoas com a letra Uma como o seu nome ou a letra B, que poderia potencialmente transformar-se em algo mais linear. Então, não é absolutamente perfeito. Então, poderíamos fazer melhor? 

Bem, o que foi o nosso solução antes quando nós quer ter mais dinamismo do que algo como uma matriz permitido? AUDIÊNCIA: [inaudível] DAVID MALAN: O que nós apresentamos? Sim. Assim, uma lista ligada. Bem, vamos ver o que um ligado lista pode fazer por nós em seu lugar. Bem, deixe-me propor que desenhar a imagem da seguinte forma. Agora este é um diferente imagem de um exemplo a partir de um texto diferente, na verdade, que é, na verdade, usando uma matriz de tamanho 31. E este autor simplesmente decidiu botar cordas não com base em nomes da pessoa, mas com base em suas datas de nascimento. Independentemente do mês, figuraram se você nasceu no primeiro dia de um mês ou o dia 31 de um mês, o autor vai botar com base nesse valor, de forma a disseminar os nomes um pouco mais do que apenas 26 pontos pode permitir. E talvez seja um pouco mais uniforme do que ir com as letras do alfabeto, porque é claro que há, provavelmente, mais pessoas no mundo com nomes que começar com uma que certamente algumas outras letras do alfabeto. Então talvez isso seja um pouco mais uniforme, assumindo uma distribuição uniforme de bebés através de um mês. 

Mas, claro, isso ainda é imperfeito. Certo? Nós estamos tendo colisões. Várias pessoas nesta estrutura de dados ainda são tendo a mesma data de nascimento, pelo menos você independentemente do mês. Mas o que o autor fez? Bem, parece que temos um array no lado da mão esquerda tirada verticalmente, mas isso é apenas interpretação de um artista. Não importa que direção você desenhar uma matriz, que ainda é um array. O que é isso uma série de aparentemente? 

AUDIÊNCIA: lista encadeada. 

DAVID MALAN: Yeah. Parece que é uma matriz de lista ligada. Então, novamente, a este ponto de tipo de usar essas estruturas de dados agora como ingredientes a mais soluções interessantes, você pode perfeitamente ter um fundamentais, como uma matriz, e em seguida, tomar algo mais interessante como uma lista ligada e até mesmo combiná-los em um mesmo estrutura de dados mais interessante. E, de fato, isso também seria ser chamado de uma tabela hash, pelo que a matriz é realmente a tabela hash, mas que tem tabela hash correntes, por assim dizer, que pode crescer ou psiquiatra com base no número de elementos que você deseja inserir. 

Agora, nesse sentido, o que é o tempo de execução agora? Se eu quiser inserir alguém cujo aniversário é 31 de outubro de onde é que ele ou ela vai? Tudo certo. Na parte inferior, onde ele diz que 31. E isso é perfeito. Esse foi o tempo constante. Mas o que se encontrar alguém cujo aniversário é, vamos ver, Outubro, novembro, 31 de dezembro? Onde é que ele ou ela vai? Mesma coisa. Duas etapas embora. Isso é constante, embora, não é? Tudo certo. No momento em que ela é. Mas, no caso geral, quanto mais as pessoas que agregam, probabilisticamente, vamos para obter mais e mais colisões. 

Agora isso é um pouco melhor, porque tecnicamente Agora minhas correntes poderiam estar em o pior caso quanto tempo? Se eu inserir n pessoas para este mais estrutura de dados sofisticado, n pessoas, na pior das hipóteses ele vai ser n. Por quê? 

AUDIÊNCIA: Porque se todo mundo tem o mesmo aniversário, eles estão indo para ser uma linha. DAVID MALAN: Perfeito. Ele pode ser um pouco artificial, mas realmente, no pior caso, se todo mundo tem o mesmo aniversário, dadas as entradas que você tem, você vai ter um maciçamente cadeia longa. E assim, você poderia chamá-lo de um Hash Table, mas realmente é apenas uma enorme lista ligada um monte de espaço desperdiçado. Mas, em geral, se assumirmos que pelo menos, os aniversários são uniform-- e provavelmente não é. Eu estou fazendo isso. Mas se assumirmos, por a causa da discussão que eles são, então, em teoria, se esta é a representação verticais da matriz, bem, então espero que você está vai ficar cadeias que são, você sabe, aproximadamente o mesmo comprimento, onde cada um dos deles representa um dia do mês. 

Agora, se há 31 dias no mês, isso significa que o meu tempo de corrida realmente é grande O de n mais de 31, que sente melhor do que linear. Mas o que era um de nossos compromissos de algumas semanas há sempre que se tratava de expressar o tempo de execução de um algoritmo? Basta apenas olhar para o termo de ordem superior. Certo? 31 é definitivamente útil. Mas isso ainda é grande O de n. Mas um dos temas do conjunto de problemas de cinco vai ser a reconhecer que absolutamente, assintoticamente, teoricamente esta estrutura de dados não é melhor do que apenas uma lista ligada maciça. E, de fato, no pior dos casos, este tabela hash pode transformar-se em que. 

Mas no mundo real, com nós seres humanos que os próprios Macs ou PCs ou o que quer e estão em execução no mundo real software em dados do mundo real, algoritmo que você vai preferir? Aquele que toma medidas finais ou à que leva n dividido por 31 passos para encontrar alguma peça de dados ou para procurar alguma informação? Quero dizer, absolutamente as 31 marcas uma diferença no mundo real. É 31 vezes mais rápido. E nós, seres humanos são, certamente, vai apreciar isso. 

Assim, perceber a dicotomia na verdade existe entre falando sobre coisas teoricamente e assintoticamente que definitivamente tem valor como vimos, mas no mundo real, se você se preocupa apenas fazendo o feliz humano para as entradas gerais, você pode muito bem querer aceitar o facto de que, sim, isto é linear, mas é 31 vezes mais rápido que pode ser linear. E melhor ainda, nós não apenas temos que fazer algo arbitrário como a data de nascimento, poderíamos passar um pouco mais tempo e inteligência e pensar sobre o que poderíamos fazer, dado o nome de uma pessoa e talvez sua data de nascimento para combinar os ingredientes para descobrir algo que é verdadeiramente mais uniforme e menos irregular, por assim dizer do que esta imagem atualmente sugere que poderia ser. Como podemos implementar isso no código? Bem, deixe-me propor que apenas pedir algum sintaxe temos utilizado um par de vezes até agora. E eu estou indo para definir um nó, que novamente é um termo genérico para apenas alguns recipiente para alguma estrutura de dados. Vou propor que uma seqüência que vai lá dentro. Mas vamos começar a tomar aquelas rodinhas fora agora. 

Não há mais biblioteca CS50 realmente, a menos que você quiser usá-lo para o seu final, projeto, que é bom, mas agora estamos indo para puxar a cortina e dizer que é apenas uma estrela de char. Assim, a palavra não vai ser o nome da pessoa em questão. E agora eu tenho um link aqui para o próximo nó para que estes representam cada um dos nós na cadeia, potencialmente, de uma lista ligada. 

E agora como faço para declarar própria tabela de hash? Como faço para declarar toda esta estrutura? Bem, realmente, muito parecido com que eu usei um ponteiro para apenas o primeiro elemento de uma lista antes, da mesma forma eu posso apenas dizer Eu só preciso de um monte de ponteiros para implementar essa tabela hash todo. Eu vou ter um array chamada de tabela para a tabela hash. Vai ser de capacidade tamanho. É assim que muitos elementos podem caber nele. E cada um desses elementos neste matriz vai ser uma estrela nó. Por quê? Bem, por esta imagem, o que eu sou implementar a tabela de hash como notadamente no início é apenas essa matriz que temos desenhado na vertical, cada um de cujos quadrados representa um ponteiro. Que aqueles que têm barras através deles são apenas nulo. E os que têm setas que vão para a direita são ponteiros reais para nós reais, ergo o início de uma lista ligada. 

Então, aqui, então, é como podemos implementar uma tabela hash que implementa o encadeamento separado. Agora podemos fazer melhor? Tudo bem que prometi da última vez que poderíamos conseguir tempo constante. E eu meio que lhe deu constante de tempo aqui, mas depois não disse realmente constante de tempo porque ainda é dependente do total número de elementos você está introduzindo em a estrutura de dados. Mas suponha que nós fizemos isso. Deixe-me voltar para a tela aqui. Permitam-me também projetar esta aqui em cima, claro da tela, e suponho que eu fiz isso. Suponha que eu queria inserir o nome Daven em em minha estrutura de dados. 

Então, eu quero inserir uma string Daven na estrutura de dados. E se eu não usar um Hash Table, mas eu uso algo que é mais do tipo árvore como uma árvore genealógica, onde você tem alguma raiz no nós e folhas superiores e, em seguida, que ir para baixo e para fora. Suponhamos, então, que eu deseja inserir Daven de em que é atualmente uma lista vazia. Eu vou fazer o seguinte: Eu sou vai criar um nó desta família árvore-como estrutura de dados que parece um pouco parecido com isso, cada uma das quais retângulos tem, digamos, para agora 26 elementos nele. E cada uma das células nesta matriz vai para representar a letra de um alfabeto. 

Especificamente, eu estou indo para o tratamento este é A, então B, então C, então D, este aqui. Então, isso vai efetivamente representar a letra D. Mas para inserir todos Daven de nome eu preciso fazer um pouco mais. Então, eu estou indo primeiro para mistura, por assim dizer. Vou olhar para a primeira letra em Daven do que é, obviamente, uma D, e eu estou indo para alocar um nó que parece como isto-- um grande retângulo grande o suficiente para caber todo o alfabeto. 

Agora D é feito. Agora A. D-A-V-E-N é o objetivo. Então agora o que eu vou fazer é esta. Assim que eu comecei a notificação D não há nenhum ponteiro lá. É valores de lixo, no momento, ou eu poderia inicializar a null. Mas deixe-me continuar com esta ideia de construir uma árvore. Deixe-me alocar mais um desses nodos que contém 26 elementos nele. 

E você sabe o quê? Se este é apenas um nó na memória que Eu criei com malloc, usando uma struct como veremos em breve, Eu vou fazer isso- Vou desenhar uma seta de a coisa que representasse D para baixo para este novo nó. E agora, pela primeira vez o seguinte carta em nome de Daven, V-- D-A-V-- eu vou ir em frente e desenhar outro nó como este, pelo que, os elementos de V, que aqui vamos chamar de gritos instance--. Não vamos tirar lá. Vai aqui. 

Então nós vamos consideram que este é V. E então aqui vamos índice para baixo de V para o que vamos considerar E. E então a partir daqui vamos vá ter um desses nós aqui. E agora nós temos uma pergunta para responder. Eu preciso de alguma forma indicam que estamos no fim da cadeia Daven. Então, eu poderia deixá-lo nulo. 

Mas o que se tem de Daven nome completo também, que é, como já dissemos, Davenport? Então, o que se é Daven realmente uma substring, um prefixo de uma seqüência muito mais tempo? Não podemos simplesmente permanentemente dizer nada vai para ir lá, porque podíamos nunca insira uma palavra como Davenport para esta estrutura de dados 

Então, o que nós poderíamos fazer é em vez tratar cada um desses elementos Tendo como talvez dois elementos dentro deles. Um deles é um ponteiro, de fato, como eu venho fazendo. Assim, cada uma destas caixas não é apenas um celular. Mas e se o topo um-- do um fundo vai ser nulo, porque não há Davenport ainda. E se o topo é algum valor especial? E isso vai ser um pouco difícil desenhá-la deste tamanho. Mas acho que é apenas uma marca de verificação. Confira. D-A-V-E-N é uma seqüência nesta estrutura de dados. 

Enquanto isso, se eu tivesse mais espaço aqui, eu poderia fazer P-O-R-T, e eu poderia colocar o check-in o nó que tem a letra T no final. Portanto, este é um massivamente estrutura de dados de aparência complexa. E a minha letra certamente não ajuda. Mas se eu queria inserir algo outra coisa, considere o que faríamos. Se quiséssemos colocar David na, nós seguem a mesma lógica, D-A-V, mas agora eu apontaria na próxima elemento não a partir de E, mas a partir de I a D. Portanto, não vai ser mais nós nesta árvore. Nós vamos ter chamada malloc mais. Mas eu não quero fazer uma bagunça completa da imagem. Então, vamos olhar para uma vez que foi pré-formulados assim com não ponto, ponto, pontos, mas apenas matrizes abreviados. Mas cada um dos nós nesta árvore-se aqui representa o mesmo coisa-- uma série de Ray tamanho 26. 

Ou, se quisermos ser realmente bom agora, o que se o nome de alguém como um apóstrofo, vamos supor que cada nó tem realmente como 27 índices em que, não apenas 26. Então, isso agora vai ser um dos dados uma estrutura chamada trie-- T-R-I-E. Uma trie, que supostamente é historicamente um nome inteligente para uma árvore otimizado para de recuperação, o que, naturalmente, é soletrado com um I-E por isso é trie. Mas essa é a história da trie. 

Assim, uma trie é esses dados em árvore estrutura como uma árvore genealógica que em última análise se comporta assim. E aqui é apenas mais um exemplo de uma todo monte de nomes de outras pessoas. Mas a questão agora na mão é o que tem ganhamos através da introdução de um indiscutivelmente mais estrutura de dados complicado, e um, francamente, que utiliza uma grande quantidade de memória. 

Porque mesmo que, no momento, eu só estou usando ponteiro D e A e V e Es e Ns, Eu estou perdendo um pedaço de muita memória. Mas onde eu passar um recurso, Eu tendo a não ganhar de volta um outro. Então, se eu estou gastando mais espaço, o que é, provavelmente, a esperança? Que eu estou gastando menos com o que? AUDIÊNCIA: Menos tempo. DAVID MALAN: Time. Agora, por que pode ser isso? Bem, o que é a inserção tempo, em termos de grande ó agora, de um nome como Daven ou Davenport ou David? Bem, Daven era de cinco etapas. Davenport seria nove etapas, por isso seria mais alguns passos. David seria cinco passos bem. Portanto, estas são de concreto números, mas certamente há um limite superior sobre o comprimento do nome de alguém. E, de fato, no problema conjuntos de cinco especificação, vamos propor que é algo que é de 40 caracteres e tantos. 

Realisticamente, ninguém tem um nome infinitamente longo, o que quer dizer que o comprimento de um nome ou o comprimento de uma string que pode ter certeza de que o estado de estrutura é sem dúvida o que? É constante. Certo? Pode ser uma grande constante como 40 e poucos anos, mas é constante. E isso não tem nenhuma dependência de quantos outros nomes estão nesta estrutura de dados. Em outras palavras, se I queria agora inserir Colton ou Gabriel ou Rob ou Zamyla ou Alison ou Belinda ou quaisquer outros nomes da equipe em dados estrutura, é o tempo de execução de inserir outros nomes vai ser em tudo impactaram pela forma como muitos outros elementos são na estrutura de dados já? Não é. Certo? Porque nós estamos efetivamente usando esta tabela hash de multi-camada. E o tempo de execução de qualquer destas operações não é dependente do número de elementos que se encontram na estrutura de dados ou que são, eventualmente, indo estar na estrutura de dados, mas no comprimento do que especificamente? 

A seqüência de estar inserido, o que faz este assintoticamente constante tempo-- grande O de um. E, francamente, só em o mundo real, este significa inserir o nome de Daven leva como cinco etapas, ou Davenport nove etapas, ou David cinco etapas. Isso é muito danado pequenos tempos de execução. E, de fato, isso é muito coisa boa, especialmente quando não é dependente do total número de elementos de lá. Então, como podemos implementar esta tipo de estrutura em código? É um pouco mais complexo, mas ainda é apenas uma aplicação de blocos de construção básicos. Eu estou indo para redefinir nos nó como se segue: booleano chamado word-- e esta poderia ser chamado de qualquer coisa. Mas o representa boleano o que eu desenhei como uma marca de verificação. Sim. Esta é a extremidade de uma corda nesta estrutura de dados. 

E, claro, a estrela nó não está se referindo a crianças. E, de fato, assim como uma árvore de família, você consideraria os nós que são pendurado da parte inferior de alguns dos pais elemento a ser crianças. E assim as crianças vai ser uma matriz de 27, a uma 27th sendo apenas para apóstrofo. Nós estamos indo para classificar de caso especial que. Então você pode ter certeza nomes com apóstrofo. Talvez até hífen deve vá lá, mas você ver em conjunto p 5 só cuidado sobre letras e apóstrofos. 

E então como é que você representa a própria estrutura de dados? Como você representar a raiz desta trie, por assim dizer? Bem, assim como com uma lista ligada, você precisa de um ponteiro para o primeiro elemento. Com uma trie você só precisa de um ponteiro para a raiz desta trie. E a partir daí você pode botar o seu caminho cada vez mais fundo para todos os outros nós na estrutura. Então simplesmente com esta lata nós representamos que struct. 

Agora Meanwhile-- Oh, pergunta. 

AUDIÊNCIA: Qual é palavra bool? 

DAVID MALAN: palavra Bool é apenas nesta encarnação C do que eu descrevi nessa caixa aqui, quando Comecei dividindo cada um dos elementos em duas peças da matriz. Um deles é um ponteiro para o próximo nó. A outra tem que ser algo como uma caixa de seleção dizer que sim, há uma Daven palavra que termina aqui, porque não queremos, no momento, Dave. 

Mesmo que Dave vai ser um palavra legítima, ele não está no trie Ainda. E D não é uma palavra. E D-A não é uma palavra ou um nome. Assim, a marca de verificação indica apenas uma vez você atingir esse nó é o trajetória anterior de personagens na verdade, uma seqüência de caracteres que você inseriu. Então, isso é tudo o bool não está fazendo por nós. 

Quaisquer outras perguntas sobre tentativas? Sim. 

AUDIÊNCIA: Qual é a sobreposição? E se você tem um Dave e um Daven? DAVID MALAN: Perfeito. E se você tem um Dave e um Daven? Então, se nós inserimos, digamos, um apelido, para David-- Dave-- D-A-V-E? Esta é realmente super simples. Então nós só vamos levar quatro etapas. D-A-V-E. E o que eu tenho que fazer, uma vez que eu bati quarta nó? Basta ir verificar. Já está pronto para ir. Feito. Quatro passos. Constante de tempo assintoticamente. E agora que já indicaram que tanto Dave e Daven são strings na estrutura. Então, não é um problema. E observe como a presença Daven de não torná-lo levar mais tempo ou menos tempo para Dave e vice-versa. 

Então o que mais nós podemos fazer? Nós usamos esta metáfora antes bandejas de representar algo. Mas verifica-se que a pilha de tabuleiros é realmente demonstrativo de outro abstrato de dados type-- uma estrutura de dados de nível superior que, no final do dia é apenas como uma matriz ou uma lista ligada ou algo mais mundano. Mas é uma mais interessante conceito conceitual. Uma pilha, como estes Bandejas aqui em Mather, são geralmente chamados apenas que-- uma pilha. 

E, neste tipo de estrutura de dados você tem duas operations-- você tem um chamado de impulso para adicionando algo para a pilha, como colocar outra bandeja trás sobre o topo da pilha. E em seguida, pop, o que significa que tomar o mais alto para fora da bandeja. Mas o que é importante sobre uma pilha é que ele tem essa característica curiosa. Como a equipe de sala de jantar são rearranjar as bandejas para a próxima refeição, o que vai ser verdade sobre como os alunos interagir com essa estrutura de dados? AUDIÊNCIA: Eles estão indo estalar um fora. DAVID MALAN: Eles vão estalar um fora, espero que o topo. Caso contrário, é apenas uma espécie de estúpida para percorrer todo o caminho até o fundo. Certo? A estrutura de dados realmente não permite você pegar a bandeja inferior, pelo menos, facilmente. Então há esse curioso propriedade de uma pilha que o último item é vai ser o primeiro a sair. E os cientistas da computação chamam este LIFO-- último a entrar, primeiro a sair. E ele realmente tem aplicações interessantes. Não é necessariamente tão óbvio como alguns outros, mas pode, de fato, ser útil, e pode, de facto, ser implementado em um par de maneiras diferentes. 

Então, um, e na verdade, vamos me não para mergulhar nisso. Vamos fazer isso em seu lugar. Vamos olhar para um que é quase o mesma idéia, mas é um pouco mais justo. Certo? Se você é um desses meninos fãs ou meninas que realmente gosta de produtos da Apple e você acordou às 3h00 para alinhar em alguma loja para obter o mais recente iPhone, você poderia ter fila como este. 

Agora a fila é muito deliberadamente nomeado. É uma linha porque não há alguma justiça a ele. Certo? Seria uma espécie de sugado se você tiver chegou primeiro na Apple Store mas você é efetivamente o bottommost bandeja porque os funcionários da Apple, em seguida, estalar a última pessoa que realmente tem na linha. Então, pilhas e filas, embora funcionalmente eles são tipo do same-- é só esta coleção de recursos que é vai crescer e shrink-- existe este aspecto justiça a ele, pelo menos, no mundo real, onde as operações se exercita são fundamentalmente diferentes. Um stack-- uma fila rather-- é dito ter duas operações: fila de n e d fila. Ou você pode chamá-los uma série de coisas. Mas você só quer capturar a noção de que uma é a adição de e uma última análise, é subtraindo. 

Agora sob o capô, tanto a pilha e uma fila poderia ser implementado como? Não vamos entrar no código de porque o nível mais elevado idéia é uma espécie de mais evidente. Quero dizer, o que os humanos fazem? Se eu sou a primeira pessoa no Apple Armazenar e esta é a porta da frente, você sabe, eu vou ficar aqui. E a próxima pessoa vai ficar aqui. E a próxima pessoa vai ficar aqui. Então, o que estrutura de dados presta-se a uma fila? 

AUDIÊNCIA: A fila. DAVID MALAN: Bem, uma fila. Claro. O que mais? 

AUDIÊNCIA: Uma lista ligada. 

DAVID MALAN: um ligado lista que poderia implementar. E uma lista ligada é bom porque depois ele pode crescer arbitrariamente longa em oposição para ter um número fixo de pessoas na loja. Mas talvez um número fixo de lugares é legítimo. Porque se eles só têm como 20 iPhones no primeiro dia, talvez eles só precisam de uma matriz de tamanho 20 para representar essa fila, que é só para dizer agora, uma vez que começar a falar sobre esses problemas de nível superior, você pode implementá-lo em qualquer número de maneiras. E não há, provavelmente, só vai ser um trade off no espaço e no tempo ou apenas em sua própria complexidade do código. 

Que tal uma pilha? Bem, uma pilha, temos visto também poderia ser apenas estas bandejas. E você poderia implementar esta uma matriz. Mas em algum momento, se você usar uma matriz, o que vai acontecer com as bandejas você está tentando colocar para baixo? Tudo certo. Você só vai ser capaz de ir tão alto. E eu acho que eles estão em Mather na verdade, em que a abertura do recesso. Então, na verdade, é quase como Mather está usando uma matriz de tamanho fixo, porque só você pode caber tantas bandejas em que a abertura de a parede abaixo joelhos das pessoas. E, de modo que pode ser Diz-se que uma matriz, mas nós certamente poderia implementar essa de modo mais geral, com uma lista ligada. 

Bem, o que dizer de uma outra estrutura de dados? Deixe-me puxar para cima um outro visuais aqui. Algo como que tal essa aqui? Por que ele pode ser útil para não ter algo tão extravagante como uma trie, que vimos que tinha esses nós muito largas, cada um dos quais está em uma matriz? Mas o que se fazer algo mais simplesmente, como uma árvore genealógica da velha escola, cada um de cujos nós aqui é apenas armazenar um número. Em vez de um nome ou um descendente é apenas armazenar um número como este. 

Bem, o jargão que usamos em estruturas de dados é duas tentativas e árvores, onde uma trie, novamente, é apenas uma cujos nós são matrizes, ainda é o que você pode usar da escola de classe quando você fez uma família tree-- folhas e da raiz da árvore e crianças do pais e irmãos dos mesmos. E poderíamos implementar uma árvore, por exemplo, como simplesmente como este. Uma árvore, como se um nó, um dos estes círculos que contém um número, ele não vai ter um ponteiro, mas dois. E assim que você adicionar um segundo ponteiro, você agora pode realmente fazer tipo de dados bi-dimensional estruturas em memória. Muito parecido com um bidimensional array, você pode ter tipo de bi-dimensional listas ligadas, mas os que seguem um padrão onde não há ciclos. É verdadeiramente uma árvore com uma maneira avô aqui e depois para cima alguns pais e filhos e netos e bisnetos. e assim por diante. 

Mas o que é realmente interessante sobre isso também, só para provocá-lo com um pouco de código, recordação de recursão algum tempo atrás, em que você escrever uma função que chama a si mesmo. Esta é uma bela oportunidade para implementar algo como recursão, porque considerar isso. 

Esta é uma árvore. E eu tenho sido um pouco anal com a forma como Eu coloquei os números inteiros para a rua. Tanto é assim que ele tem uma especial nome-- uma árvore de busca binária. Agora nós já ouviu falar de binário procurar, mas você pode trabalhar para trás a partir do nome desta coisa? Qual é o padrão de como eu inseridos os números inteiros para esta árvore? Não é arbitrária. Há algum padrão. Sim. 

AUDIÊNCIA: Os menores de esquerda. 

DAVID MALAN: Yeah. Os menores estão à esquerda. As maiores são na direita. De tal forma que uma afirmação verdadeira é uma pai é maior do que o seu filho esquerdo, mas menos do que o seu filho direito. E só isso é mesmo um definição verbal recursiva porque você pode aplicar esse mesma lógica para cada nó E só bottoms para fora, um caso base, se você vontade, quando você bate um dos as folhas, por assim dizer, onde uma licença não tem filhos ainda. 

Agora, como você pode encontrar o número 44? Você poderia começar na raiz e dizer, hm. 55 não é 44 Então eu quero ir direito ou eu quero ir para a esquerda? Bem, obviamente você quer ir esquerdo. E assim é como o telefone exemplo livro em busca binária de modo mais geral. Mas estamos implementá-lo agora um pouco mais dinâmica do que uma matriz pode permitir. E, na verdade, se você quiser olhar no código, à primeira vista, com certeza. Parece que um monte de linhas. Mas é bem simples. Se você quiser implementar uma função chamada pesquisa cujo propósito na vida é a busca de um valor como n, um inteiro, e que você passou em um pointer-- um apontador para o nó das raízes, ao contrário, de que árvore da qual você pode acessar tudo o mais, observe como diretamente você pode implementar a lógica. Se árvore é nulo, obviamente ele não está lá. Vamos apenas retornar falso. Certo? Se você entregá-lo nada, não há nada lá. 

Logo, se n é inferior a árvore seta n-- agora arrow n, lembrar que introduzimos Super brevemente no outro dia, e que apenas significa de-referência a ponteiro e olhar para o campo chamado n. Então isso significa ir lá e olhar para o campo chamado n. Então, se n, o valor que se recebe, é menos em que o valor do inteiro árvores, onde você quer ir? Para a esquerda. 

Então, observe a recursividade. Estou returning-- não é verdade. Não falsa. Estou voltando qualquer que seja a resposta é a partir de uma chamada para mim, passando um n de novo, o que é redundante, mas o que é um pouco diferente agora? Como eu estou fazendo o problema menor? Eu estou passando como o segundo argumento, não a raiz da árvore, mas o filho esquerdo neste caso. Então, eu estou passando o filho esquerdo. 

Por outro lado, se n for maior do que o nó Atualmente estou olhando, Eu procuro o lado direito. Outra coisa, se a árvore não é nulo, e Se o elemento não está à esquerda e não é para a direita, o que é maravilhosamente o caso? Nós realmente encontramos o nó em pergunta, e assim voltamos verdade. 

Então, nós apenas arranhamos a superfície agora algumas dessas estruturas de dados. No conjunto de problemas de cinco você vai explorar estes ainda mais longe, e você será dado o seu projeto escolha de como ir sobre isso. O que eu gostaria de concluir sobre é apenas um segundo teaser 30 do que nos espera na próxima semana e além. 

Como nós begin-- felizmente você pode penso-- nossa transição lenta do mundo da C e menor detalhes de implementação nível, para um mundo em que podemos tomar para certo que alguém tem, finalmente, implementado estes dados estruturas para nós, e vamos começar a entender o mundo real significa de implementação programas baseados na web e sites mais geralmente e também a própria segurança implicações que nós só começaram a arranhar a superfície do. Aqui está o que nos espera nos dias que virão. 

[REPRODUÇÃO DE VÍDEO] 

-Ele Veio com uma mensagem, com um protocolo de todos os seus próprios. Ele veio para um mundo de cruel firewalls, roteadores indiferente, e perigos muito piores do que a morte. Ele é rápido. Ele é forte. Ele é o TCP / IP, e ele tem o seu endereço. "Guerreiros da rede." [FIM REPRODUÇÃO DE VÍDEO] DAVID MALAN: Na próxima semana. Vamos vê-lo em seguida. [REPRODUÇÃO DE VÍDEO] -E Agora, "Pensamentos Profundos" por Daven Farnham. -David Começa sempre palestras com: "Tudo bem." Por que não, "Aqui está a solução ao conjunto de problemas desta semana " ou "Estamos dando a todos vocês um A?" [Risos] [FIM REPRODUÇÃO DE VÍDEO]