COLUNA 1: Tudo bem, então estamos de volta. Bem-vindo ao CS50. Isto é o fim de semana sete. Então, lembro que da última vez, nós começamos olhando um pouco mais sofisticado estruturas de dados. Uma vez que, até agora, tudo o que tinha realmente à nossa disposição era isso, um array. Mas, antes de descartar a matriz como não tudo o que interessante, o que de fato realmente é, o que são alguns dos vantagens destes dados simples estrutura até agora? O que é que é bom? Até agora, como vimos? O que você tem? Nada. Estudante: [inaudível]. COLUNA 1: O que é isso? Estudante: [inaudível]. COLUNA 1: tamanho fixo. OK, então por que é tamanho fixo bom embora? Estudante: [inaudível]. COLUNA 1: OK, por isso é eficiente em a sensação de que você pode alocar um quantidade fixa de espaço, que espero É precisamente tanto espaço como você quiser. Assim que poderiam ser absolutamente uma vantagem. Qual é o outro lado por um conjunto? Sim? Estudante: [inaudível]. COLUNA 1: Tudo o - sorry? Estudante: [inaudível]. COLUNA 1: Todas as caixas na memória ou ao lado do outro. E isso é útil - por quê? Isso é bem verdade. Mas como podemos explorar isso verdade? Estudante: [inaudível]. COLUNA 1: Exatamente, podemos acompanhar onde tudo é apenas por saber um endereço, ou seja, o endereço do primeiro byte desse bloco de memória. Ou, no caso da cadeia, o endereço do primeiro char que string. E a partir daí, podemos encontrar o fim da string. Podemos encontrar o segundo elemento, o terceiro elemento, e assim por diante. E assim, a maneira elegante de descrever que característica é que as matrizes nos dar de acesso aleatório. Apenas usando o colchete notação e um número, você pode saltar para um elemento específico da matriz em tempo constante, O grande de uma, por assim dizer. Mas houve algumas desvantagens. O que uma matriz não fazer muito facilmente? O que é isso não é bom? Estudante: [inaudível]. COLUNA 1: O que é isso? Estudante: [inaudível]. COLUNA 1: Expansão de tamanho. Assim, as desvantagens da matriz são precisamente o oposto do que o upsides são. Então, uma das desvantagens é que é um tamanho fixo. Então você não pode realmente crescer. Você pode realocar uma fatia maior do memória e, em seguida, mover os elementos antigos na nova matriz. E, então, livre da velha matriz, para exemplo, usando malloc ou similar função chamada realloc, que realoca memória. Realloc, como um aparte, tenta dar-lhe de memória que é ao lado da matriz que você já tem. Mas isso pode mudar as coisas volta completamente. Mas, em suma, que é caro, né? Porque se você tem um bloco de memória de deste tamanho, mas você realmente quer um deste tamanho, e você quer preservar os elementos originais, você tem cerca de um processo de cópia de tempo linear que deve acontecer a partir de antiga matriz para novos. E a realidade está pedindo ao funcionamento sistema novo e de novo e novamente para grandes pedaços de memória pode começar lhe custar algum tempo também. Por isso, é tanto uma bênção e uma maldição em dissimular o fato de que essas matrizes são de tamanho fixo. Mas se introduzir algo em vez assim, o que nós chamamos um linked lista, temos alguns prós e algumas desvantagens aqui também. Assim, uma lista ligada é simplesmente um conjunto de dados estrutura composta de estruturas C neste caso, onde um struct, aviso, é apenas um recipiente para uma ou mais específico tipos de variáveis. Neste caso, o que os tipos de dados parecem estar dentro da estrutura que última vez que chamado de nó? Cada um destes rectângulos é um nó. E cada um dos retângulos menores dentro do que é um tipo de dados. Quais são os tipos que dissemos eles estavam na segunda-feira? Sim? Estudante: [inaudível]. COLUNA 1: A variável e um ponteiro, ou mais especificamente, um int, para n, e um ponteiro na parte inferior. Ambas aquelas que ser de 32 bits, em menos em um computador como este CS50 Appliance, e por isso eles são igualmente desenhada em tamanho. Então, o que estão usando o ponteiro apesar de aparentemente? Por que acrescentar esta seta agora, quando as matrizes foram tão agradável e limpo e simples? O que é o ponteiro para fazer nós em cada um desses nodos? Estudante: [inaudível]. COLUNA 1: Exatamente. Ele está dizendo a você onde a próxima é. Então, eu tipo de usar a analogia de utilizando um fio de classificar de enfiar esses nós juntos. E isso é exatamente o que estamos fazendo com ponteiros porque cada uma delas pedaços de memória pode ou não ser contígua, de costas para trás dentro de RAM, porque cada vez que você chamar malloc dizendo, dá-me o suficiente bytes para um novo nó, que poderia ficar aqui ou pode ser aqui. Pode ser aqui. Pode ser aqui. Você simplesmente não sabe. Mas o uso de ponteiros em endereços de desses nós, você pode uni-las juntos de uma forma que parece ser visualmente como a lista, mesmo se essas coisas são todos espalhados por todo o seu um ou suas duas ou seus quatro gigabytes de RAM dentro de seu próprio computador. Então, o lado negativo, então, de uma lista ligada é o quê? O que é um preço que estamos aparentemente pagando? Estudante: [inaudível]. COLUNA 1: Mais espaço, certo? Temos, neste caso, duplicando a quantidade de espaço, porque nós fomos a partir de 32 bits para cada nó, para cada int, agora de 64 bits, porque temos de manter em torno de um ponteiro bem. Você ganha mais eficiência se o seu struct é maior do que essa coisa simples. Se você realmente tem um aluno dentro de que é um par de cordas para nome e casa, talvez um número de identificação, talvez alguns outros campos completamente. Então, se você tem uma grande estrutura suficiente, talvez o custo do ponteiro está não como um grande negócio. Isto é um pouco de um caso de canto em que estamos armazenando uma simples primitivo como dentro da lista encadeada. Mas o ponto é o mesmo. Você está definitivamente gastar mais memória, mas que está recebendo flexibilidade. Porque agora se eu quiser adicionar um elemento no início da lista, Eu tenho que alocar um novo nó. E eu tenho que apenas atualizar os flechas de alguma forma por apenas movendo algumas dicas redor. Se eu quiser inserir algo na meio da lista, eu não tenho a empurrar todos para o lado como fizemos em passado semanas com os nossos voluntários que representada uma matriz. Eu só posso atribuir um novo nó e em seguida, basta apontar as setas em diferentes direções, porque não tem que permanecer no real memória de uma linha de verdade como eu desenhei aqui na tela. E então, finalmente, se você quiser inserir algo que, no final da lista, é ainda mais fácil. Esta é uma espécie de notação arbitrária, mas ponteiro de 34, dar um palpite. Qual é o valor de seu ponteiro mais provável tipo elaborado de como um velho antena escola lá? Estudante: [inaudível]. COLUNA 1: É provavelmente nulo. E, de fato, que é um autor representação do nulo. E é nulo porque é absolutamente Precisamos saber onde o fim de um linked lista é, para você continuar a seguir e seguindo e seguindo essas setas para um valor de lixo. Então nulo irá significar que não há nenhuma mais nós à direita do número 34, neste caso. Assim, propomos que podemos implementar este nó em código. E temos visto esse tipo de sintaxe antes. Typedef apenas define um novo tipo de nós, dá-nos um sinônimo como corda era para char *. Neste caso, ele vai nos dar notação abreviada para que nó struct pode ao invés de apenas ser escrita como nodo, o que é muito mais limpo. É muito menos detalhada. No interior de um nó é aparentemente um int chamado n, e, em seguida, um nó struct * o que significa exatamente o que queríamos que o setas a dizer, um ponteiro para uma outra nó do mesmo tipo de dados exatos. E eu proponho que poderia implementar um função de pesquisa como este, que a primeira vista pode parecer um pouco complexo. Mas vamos vê-lo no contexto. Deixe-me ir para o aparelho aqui. Deixe-me abrir um arquivo chamado lista de zero ponto h. E isso só contém a definição de nós só vi há pouco para esses dados tipo chamado um nó. Então nós colocamos isso em um arquivo h ponto. E como um aparte, embora esta programa que você está prestes a ver é não tudo o que complexa, é de fato convenção quando se escreve um programa para colocar as coisas como tipos de dados, para puxar constantes, às vezes, dentro de seu arquivo de cabeçalho, e não necessariamente em o arquivo C, certamente quando o seu programas ficam maiores e maiores, de modo que você sabe onde olhar tanto para documentação em alguns casos, ou para o básico como este, os definição de algum tipo. Se eu agora abrir lista de zero ponto c, observe algumas coisas. Ele inclui alguns arquivos de cabeçalho, a maioria dos de que nós já vimos antes. Ela inclui o seu próprio arquivo de cabeçalho. E como um aparte, por que é o dobro citações aqui, em oposição ao ângulo suportes na linha que Eu destacou lá? Estudante: [inaudível]. COLUNA 1: Sim isso é um arquivo local. Então, se é um arquivo local de sua preferência aqui na linha 15, por exemplo, você pode usar as aspas duplas em vez dos suportes angulares. Agora isso é bem interessante. Repare que eu tenho declarado mundial variável neste programa na linha 18 chamado pela primeira vez, a idéia é esta é Vai ser um ponteiro para o primeiro nó na minha lista ligada, e eu tenho inicializado para nulo, porque eu tenho não alocado qualquer real nós ainda. Então, isso representa, pictoricamente, o que vi há pouco na imagem como esse ponteiro no canto Lado Esquerdo. Então, agora, que o ponteiro não tem uma seta. É ao contrário, é simplesmente nulo. Mas ele representa o que será o endereço da primeira real nó na lista. Então, eu tenho implementado é uma empresa global porque, como você vai ver, tudo isso programa faz na vida é implementar uma lista ligada para mim. Agora eu tenho alguns protótipos aqui. Decidi implementar recursos como deleção, inserção, pesquisa e travessia - o último sendo apenas atravessar a lista, imprimir os seus elementos. E agora aqui está a minha rotina principal. E não vamos gastar muito tempo em estes uma vez que esta é uma espécie de, esperemos chapéu velho agora. Eu vou fazer o seguinte, enquanto o utilizador coopera. Então, eu estou indo para imprimir este menu. E eu já formatado como limpa que pude. Se o usuário digita em um, o que significa eles querem apagar alguma coisa. Se o usuário digita em dois, o que significa eles querem inserir algo. E assim sucessivamente. Vou então pedir seguida por um comando. E então eu vou usar GetInt. Portanto, este é um menuing realmente simples interface onde você só precisa digitar um mapeamento para um número desses comandos. E agora eu tenho um interruptor limpa agradável declaração de que vai ligar o que o usuário digitou dentro E se digitou um, eu vou chamar apagar e quebrar. Se digitado duas, eu vou chamar inserir e quebrar. E agora repare que eu coloquei cada destes na mesma linha. Esta é apenas uma decisão estilística. Normalmente, temos visto algo como esta. Mas eu decidi, francamente, meu programa parecia mais legível porque ele tinha apenas quatro casos para apenas listá-la assim. Uso totalmente legítimo do estilo. E eu vou fazer isso, desde que o usuário não tenha digitado zero, o que eu decidiu significará que querem parar de fumar. Então agora perceber o que eu estou vamos fazer aqui. Vou liberar a lista aparentemente. Mas mais sobre isso daqui a pouco. Vamos primeiro executar este programa. Então deixe-me fazer um terminal maior janela, ponto barra lista 0. Eu estou indo para ir em frente e coloque por tipagem dois, um número semelhante de 50, e agora você verá a lista é agora 50. E meu texto apenas rolou para cima um pouco. Então agora observe a lista contém o número 50. Vamos fazer outra inserção, tomando duas. Vamos digitar o número como um. Lista é agora um, seguido por 50. Portanto, esta é apenas uma representação textual da lista. E vamos inserir mais um número como o número 42, que é esperançosamente vai acabar no meio, porque este programa em particular os tipos que elementos, uma vez que os insere. Portanto, não temos. Super programa simples que poderia absolutamente ter usado um array, mas eu acontecer de estar usando uma lista encadeada só assim eu posso dinamicamente crescer e reduzi-lo. Então, vamos dar uma olhada para a pesquisa, se eu comando de três correr, eu quero procurar para, por exemplo, o número 43. E nada foi encontrado, aparentemente, porque voltei sem resposta. Então, vamos fazer isso de novo. Pesquisar. Vamos procurar para 50, ou melhor, procurar para 42, que tem uma bela pouco significado sutil. E eu descobri o significado da vida lá. Número 42, se você não sabe a referência, no Google. Tudo bem. Então, o que este programa feito por mim? É só me permitiu inserir assim longe e busca de elementos. Vamos avançar, então, para que a função que olhou na segunda-feira como um teaser. Então essa função, eu afirmo, as pesquisas para um elemento na lista por primeiro um, alertando o usuário e, em seguida, chamar GetInt para obter um int real que você deseja procurar. Então observe isso. Eu estou indo para criar uma variável temporária na linha 188 chamado ponteiro - PTR - poderia tê-lo chamado qualquer coisa. E é um ponteiro para um nó porque eu disse nó * lá. E estou inicializando a ser igual primeiro, para que eu efetivamente tenho o meu dedo, por assim dizer, na mesma primeiro elemento da lista. Então, se a minha mão direita é aqui PTR eu sou apontando para a mesma coisa que o primeiro está apontando. Então, agora de volta no código, o que acontece a seguir - este é um paradigma comum quando a iteração ao longo de uma estrutura como uma lista ligada. Eu vou fazer o seguinte, enquanto ponteiro não é igual a null Assim, enquanto meu dedo não está apontado em algum nulo valor, se ponteiro de seta n é igual a n. Vamos observar primeiro que n é o que o usuário digitou por GetInts chamar aqui. E ponteiro de seta n significa o quê? Bem, se nós voltar para a imagem aqui, se eu tiver um dedo apontando para aquele primeiro nó contendo nove, o seta essencialmente significa ir àquela nó e pegar o valor na posição n, neste caso, o campo de dados chamado n. Como um aparte - e nós vimos isso algumas de semanas atrás, quando alguém perguntou - esta sintaxe é novo, mas não dar-nos poderes que já não tem. Qual foi esta frase equivalente a usar notação de ponto e estrela de um casal de semanas atrás, quando puxada para trás esta camada um pouco prematuramente? Estudante: [inaudível]. COLUNA 1: Exatamente, foi estrela, e em seguida, foi estrela ponto n, com parênteses aqui, o que parece, francamente, eu acho que um monte mais enigmática de ler. Mas a estrela do ponteiro, como sempre, meios para lá. E uma vez que você está lá, que dados campo que você deseja acessar? Bem, você usar a notação de ponto para acessar um campo de dados estruturas, e eu quer especificamente n. Francamente, eu diria que este é apenas mais difícil de ler. É mais difícil se lembrar de onde que os parênteses ir, o estrela e tudo isso. Assim, o mundo adotaram algum sintática açúcar, por assim dizer. Apenas uma maneira sexy de dizer: isto é equivalente, e talvez mais intuitiva. Se o ponteiro é de fato um ponteiro, o seta significa notação ir lá e encontrar o campo neste caso chamado n. Então, se eu encontrá-lo, perceber o que eu faço. Eu simplesmente imprimir, achei por cento i, ligar o valor para que int. Eu chamo de dormir por um segundo apenas para tipo de pausa coisas na tela para dar ao utilizador um segundo para absorver o que aconteceu. E então eu quebro. Caso contrário, o que eu faço? Eu atualizar ponteiro para igual seta de ponteiro próximo. Então, só para deixar claro, isso significa ir lá, usando o meu notação old-school. Então, isso significa apenas ir para qualquer você está apontando para que, no muito primeiro caso é que eu estou apontando para a estrutura com nove nele. Então eu fui lá. E então a notação de ponto significa, obter o valor na próxima. Mas o valor, mesmo que seja elaborado como um estreito, é apenas um número. É um endereço numérico. Assim, esta linha de código, se escrito como este, o mais enigmático forma, ou assim, a pouco mais forma intuitiva, significa apenas mover a minha mão a partir do primeiro nó para o próximo, e, em seguida, o próximo, e então a seguinte, e assim por diante. Portanto, não vou me debruçar sobre o outro implementações de inserção e exclusão e transversal, os dois primeiros que são bastante envolvido. E eu acho que é muito fácil obter perdido quando fazê-lo verbalmente. Mas o que podemos fazer aqui é tentar determinar como melhor forma de fazer isso visualmente. Porque eu iria propor que se deseja inserir elementos para essa lista existente, o que tem cinco elementos - 9, 17, 22, 26 e 33 - se eu estivesse indo para implementar isso em código, eu preciso considerar como ir sobre como fazer isso. E eu gostaria de propor a dar passos de bebê segundo a qual, neste caso, quer dizer, quais são os cenários possíveis que pode encontrar em geral? Ao implementar inserção de um linked lista, isso só acontece de ser um exemplo específico de tamanho cinco. Bem, se você quiser inserir um número, como diria o número um, e manutenção da ordem classificada, onde Obviamente acontece com o número um precisa ir neste exemplo específico? Tal como no início. Mas o que é interessante lá é que Se você deseja inserir um nessa lista, o ponteiro necessidades especiais ser atualizado aparentemente? First. Então, eu diria, este é o primeiro caso que pode querer considerar um cenário que envolve a inserção no o início da lista. Vamos arrancar fora talvez uma tão fácil ou mesmo caso mais fácil, relativamente falando. Suponha que eu queira inserir o número 35 em ordem de classificação. É, obviamente, pertence lá. Então, o ponteiro obviamente vai tem que ser atualizado nesse cenário? Ponteiro de 34 tornando-se não nulo mas o endereço da estrutura contendo o número 35. Então, isso é caso dois. Então, já, eu sou uma espécie de quantização a quantidade de trabalho que tenho que fazer aqui. E, finalmente, no caso do meio é óbvio de fato, no meio, se eu quiser inserir algo como dizer 23, que vai entre os 23 e os 26, mas Agora as coisas ficam um pouco mais envolvido, porque o que ponteiros precisa ser mudado? Então, 22 obviamente precisa ser mudado porque ele não pode apontar mais de 26. Ele precisa apontar para o novo nó Eu vou ter que alocar chamando malloc ou algum equivalente. Mas, então, eu também preciso que o novo nó, 23 neste caso, que a sua ponteiro apontando para quem? 26. E aí, vai ser uma ordem das operações aqui. Porque se eu fizer isso loucamente, e eu por exemplo, no início do começo da lista, e meu objetivo é inserir 23. E eu verificar, ele pertence aqui, perto de nove? Não. Será que é aqui, ao lado de 17? Não. Será que ela pertence aqui ao lado de 22? Sim. Agora, se eu sou tolo aqui, e não pensando sobre isso, eu poderia alocar meu novo nó para 23. Posso atualizar o ponteiro da o nó chamado 22, apontando em que o novo nó. E então o que eu tenho que atualizar ponteiro do novo nó a ser? Estudante: [inaudível]. COLUNA 1: Exatamente. Apontando para 26. Mas caramba, se eu já não atualizar Ponteiro de 22 para apontar para esse cara, e agora eu tenho órfãos, o resto da lista, por assim dizer. Assim, a ordem das operações aqui vai ser importante. Para fazer isso eu poderia roubar, digamos, seis voluntários. E vamos ver se a gente não pode fazer isso visualmente em vez de código-wise. E temos alguns adorável estresse bolas para você hoje. OK, como sobre um, dois, no de volta - no final lá. três, quatro, tanto de você caras no final. E, cinco, seis. Claro. Cinco e seis. Tudo bem e nós viremos para vocês da próxima vez. Tudo bem, vamos lá para cima. Tudo bem, desde que você está aqui em primeiro lugar, gostaria de ser o único jeito no vidro Google aqui? Tudo bem, então, OK, Vidro, gravar um vídeo. OK, você está pronto para ir. Tudo bem, então se vocês podem vir aqui, eu preparei com antecedência alguns números. Tudo bem, venha até aqui. E por que não ir um pouco ainda mais dessa forma. E vamos ver, qual é o seu nome, com o vidro Google? ALUNO: Ben. COLUNA 1: Ben? OK, Ben, você vai ser o primeiro, literalmente. Por isso, vamos enviar-lhe para o final da etapa. Tudo bem, e seu nome? ALUNO: Jason. COLUNA 1: Jason, OK você vai ser o número nove. Então, se você quer seguir Ben dessa forma. ALUNO: Jill. COLUNA 1: Jill, você está indo para ser 17, que se eu tivesse feito isso mais inteligente, eu teria iniciada na outra extremidade. Você ir por esse caminho. 22. E você é? ALUNO: Mary. COLUNA 1: Mary, você vai ser 22. E o seu nome é? ALUNO: Chris. COLUNA 1: Chris, você vai ser 26. E então, finalmente. ALUNO: Diana. COLUNA 1: Diana, você vai ser 34. Então você vem aqui. Tudo bem, tão perfeito classificadas encomendar já. E vamos em frente e fazer isso para que possamos realmente - Ben você é apenas o tipo de procura fora em nada lá. OK, então vamos seguir em frente e descrever esta usando armas, bem como eu era, exatamente, o que está acontecendo. Então vá em frente e dar-vos um pé ou dois entre vós. E vá em frente e apontar com uma mão para quem você deve estar apontando para com base nesta. E se você é nula apenas apontar direto para o chão. OK, tudo bem. Portanto, agora temos uma lista ligada, e deixe-me propor que eu vou desempenhar o papel de PTR, então eu não vou incomodar levando esta ao redor. E então - alguém convenção estúpida - você pode chamar isso de qualquer coisa que você quiser - ponteiro predecessor, ponteiro pred - é apenas o apelido que demos em nosso código de exemplo para minha mão esquerda. O outro lado, que vai ser manter o controle de quem é quem no seguintes cenários. Então suponho que, em primeiro lugar, quero arrancar fora aquele primeiro exemplo de inserção de, digamos 20, na lista. Então, eu vou precisar de alguém para encarnam o número 20 para nós. Então eu preciso de alguém para malloc da platéia. Vamos para cima. Qual é o seu nome? ALUNO: Brian. COLUNA 1: Brian tudo bem, então você deve ser o nó que contém 20. Tudo bem, venha até aqui. E, obviamente, onde Brian não pertence? Assim, no meio de - na verdade, espere um minuto. Estamos fazendo isso para fora de ordem. Nós estamos fazendo isso muito mais difícil do que ele precisa estar em primeiro lugar. OK, vamos livre Brian e realloc Brian cinco. OK, então agora queremos inserir Brian como cinco. Então venha aqui ao lado Ben só por um momento. E você pode dizer presumivelmente onde essa história vai dar. Mas vamos pensar cuidadosamente sobre a ordem das operações. E é precisamente esta visuais que vai alinhar com esse código de amostra. Então, aqui eu PTR apontando inicialmente não em Ben, por si só, mas em qualquer valor que ele contém, o que neste caso é - qual é o seu nome? ALUNO: Jason. COLUNA 1: Jason, então Ben e eu somos apontando para Jason neste momento. Então agora eu tenho de determinar, onde é que Brian pertence? Então a única coisa que eu tenho acesso a agora é o item de dados n. Então eu vou dar uma olhada, é Brian menos de Jason? A resposta é verdadeira. Então, o que precisa agora de acontecer, na ordem correta? Eu preciso atualizar quantos ponteiros no total nesta história? Onde minha mão ainda está apontando para Jason, e sua mão - se você quiser colocar a mão como, de alguma forma, eu Não sei, um ponto de interrogação. OK, bom. Tudo bem, então você tem alguns candidatos. Ou Ben ou eu ou Brian ou Jason ou qualquer outra pessoa, que ponteiros precisa mudar? Quantos ao todo? OK, então dois. Meu ponteiro realmente não importa mais porque eu sou apenas temporária. Por isso, é esses dois caras, presumivelmente, Ben e Brian. Então deixe-me propor que nós atualizamos Ben, já que ele está em primeiro lugar. O primeiro elemento da lista agora vai ser Brian. Assim ponto Ben em Brian. OK, e agora? Quem fica apontada para quem? Estudante: [inaudível]. COLUNA 1: OK, então Brian tem para apontar para Jason. Mas o que eu perdi a noção do que ponteiro? Não sei onde Jason é? Estudante: [inaudível]. COLUNA 1: eu faço, desde que eu sou o ponteiro temporária. E, presumivelmente, não mudei para apontar para o novo nó. Assim, podemos simplesmente ter ponto de Brian em quem eu estou apontando. E estamos a fazer. Assim, um caso, a inserção na início da lista. Havia dois passos fundamentais. Um deles, temos que atualizar Ben, e, em seguida, nós também temos que atualizar Brian. E então eu não tem que se preocupar perambulando pelo resto da lista, porque já encontrou o seu localização, porque ele pertencia ao esquerda do primeiro elemento. Tudo bem, então bastante simples. Na verdade, parece que estamos quase fazendo isso muito complicado. Então, vamos agora arrancar fora da final da lista, e ver onde a complexidade começa. Então, se agora eu alocação da platéia. Qualquer um quer jogar 55? Tudo bem, eu vi o seu em primeira mão. Venha. Sim. Qual é o seu nome? Estudante: [inaudível]. COLUNA 1: Habata. OK, vamos lá para cima. Você vai ser o número 55. Então, você, naturalmente, pertencem no fim da lista. Então, vamos repetir a simulação comigo sendo o PTR só por um momento. Então, eu estou indo primeiro para apontar o que Ben está apontando. Nós dois estamos apontando agora em Brian. Assim, 55 não é menos do que cinco. Então eu vou me atualizar por apontando para o próximo ponteiro de Brian, que agora é, naturalmente, Jason. 55 não seja inferior a nove, de modo Vou atualizar PTR. Vou atualizar PTR. Vou atualizar PTR Eu vou atualizar PTR. E eu vou to - Hum, o que é o seu nome? ALUNO: Diana. COLUNA 1: Diana está apontando, é claro, no nulo com a mão esquerda. Então onde é que realmente Habata pertencem claramente? Para o lado esquerdo, aqui. Então, como é que eu sei para colocá-la aqui Eu acho que eu estraguei tudo. Porque o que é PTR arte neste momento? Nulo. Assim, mesmo que, visualmente, o que pudermos ver, obviamente, tudo isso caras aqui no palco. Eu não tenho mantido a par do anterior pessoa na lista. Eu não tenho um dedo apontando para fora, neste caso, o número de nó 34. Então, vamos começar esta acabado. Então, agora eu realmente preciso uma segunda variável local. E isso é o que você verá no código C amostra real, onde, como eu vou, quando eu atualizar a minha mão direita para apontar Jason, deixando, assim, Brian atrás, eu melhor começar a usar a mão esquerda para atualizar onde eu estava, para que, como eu vou através desta lista - mais sem jeito do que eu pretendia agora aqui visualmente - Vou chegar ao fim da lista. Esta mão ainda é nulo, o que é bastante inútil, excepto para indicar Sou claramente no final da lista mas agora pelo menos eu tenho essa ponteiro predecessor apontando aqui, então agora que as mãos e os ponteiros que precisa para ser atualizado? Cuja mão que você quer reconfigurar primeiro? Estudante: [inaudível]. COLUNA 1: OK, então Diana. Onde você quer apontar Ponteiro para a esquerda de Diana at? Aos 55 anos, presume-se, de modo que temos inserido lá. E onde deve 55 ponteiro ir? Para baixo, representando nulo. E minhas mãos, neste momento, não importa, porque eles eram apenas variáveis ​​temporárias. Portanto, agora estamos a fazer. Assim, a complexidade adicional ali - e não é assim tão difícil de implementar, mas precisamos de uma variável secundária para fazer certeza de que antes de eu mudar a minha direita lado, eu atualizar o valor do meu lado esquerdo lado, o ponteiro de pred, neste caso, de modo que eu tenho um ponteiro de arrasto manter o controle de onde eu estava. Agora, como um aparte, se você está pensando que isso passar, isso se sente como se fosse um pouco chato ter que manter acompanhar desta mão esquerda. Qual seria outra solução para este problema têm sido? Se você tem que redesenhar os dados estrutura que estamos falando por agora? Se este tipo de apenas se sente um pouco chato ter, tipo, dois ponteiros passando a lista, quem mais poderia ter, em um mundo ideal, mantido informações de que precisamos? Sim? Estudante: [inaudível]. COLUNA 1: Exatamente. Direito então não há realmente uma interessante germe de uma idéia. E essa idéia de um ponteiro anterior, apontando para o elemento anterior. E se eu apenas incorporada que dentro da própria lista? E isso vai ser difícil de visualizar isso sem todo o papel caindo no chão. Mas suponha que esses caras usado tanto das suas mãos para uma prévia ponteiro, e um ponteiro próximo, assim implementar o que vamos chamar um duplamente lista ligada. Isso me permitiria classificar de rewind, muito mais facilmente, sem mim, o programador, ter de manter controlar manualmente - verdadeiramente manualmente - de onde eu tinha sido anteriormente na lista. Portanto, não vamos fazer isso. Vamos mantê-lo simples, porque isso é vai ter um preço, duas vezes mais muito mais espaço para os ponteiros, se você quiser um segundo. Mas isso é de fato um comum estrutura de dados conhecida como um lista duplamente ligada. Vamos fazer o último exemplo aqui e colocar esses caras fora de sua miséria. Então malloc 20. Vamos para cima do corredor lá. Tudo bem, qual é o seu nome? Estudante: [inaudível]. COLUNA 1: Desculpe? Estudante: [inaudível]. COLUNA 1: Demeron? OK vamos lá para cima. Você deve ser 20. Você, obviamente, vai pertencer entre 17 e 22. Então deixe-me aprender a lição. Eu vou começar ponteiro apontando para Brian. E eu vou ter a minha mão esquerda apenas atualizar a Brian como eu passar para Jason, verificação faz 20 a menos do que nove? Não. É de 20 a menos de 17 anos? Não. É de 20 a menos de 22? Sim. Então, o que os ponteiros ou mãos precisa mudar onde eles estão apontando agora? Assim, podemos fazer 17 apontando para 20. Então, isso é bom. Onde queremos apontar o ponteiro agora? Aos 22 anos. E nós sabemos que 22 é, mais uma vez, graças ao meu ponteiro temporário. Então, nós estamos OK lá. Assim, devido a esta armazenagem temporária Eu mantive o controle de onde toda a gente é. E agora você pode ir para onde visualmente você pertence, e agora precisamos de 1, 2, 3, 4, 5, 6, 7, 8, 9 bolas de stress, e uma salva de palmas para esses caras, se pudéssemos. Bem feito. [Aplausos] COLUNA 1: Tudo bem. E você pode manter as peças de papel como lembranças. Tudo bem, então, confie em mim é muito mais fácil entrar por aquela com os seres humanos do que com código real. Mas o que você vai encontrar em um momento agora, é o mesmo - oh, muito obrigado. Obrigado - é que você vai descobrir que os mesmos dados estrutura, uma lista ligada, pode realmente ser utilizado como um bloco de construção de ainda mais estruturas de dados sofisticadas. E perceber também o tema aqui é que temos absolutamente introduziu mais complexidade na implementação deste algoritmo. Inserção, e se passou por isso, exclusão e consulta, é um pouco mais complicado do que Foi com uma matriz. Mas ganhar algum dinamismo. Nós temos uma estrutura de dados adaptativa. Mas, novamente, nós pagamos um preço de ter algum complexidade adicional, tanto em implementá-lo. E estamos desistido de acesso aleatório. E para ser honesto, não há um bom limpar slides posso dar-lhe que Diz aqui que é por isso que uma lista ligada é melhor do que uma matriz. E deixar por isso mesmo. Porque o tema recorrente agora, mesmo mais ainda nas próximas semanas, é que não há necessariamente uma resposta correta. É por isso que temos o eixo separado do projeto para conjuntos de problemas. Vai ser muito sensível ao contexto se você quiser usar esses dados estrutura ou aquele, e vai depende do que é importante para você em termos de recursos e complexidade. Mas deixe-me propor que os dados ideais estrutura, o santo graal, seria algo que é constante de tempo, independentemente da quantidade de material é dentro dele, não seria surpreendente se um estrutura de dados retornou respostas tempo constante. Sim. Esta palavra está na sua enorme dicionário. Ou não, esta palavra não é. Ou qualquer problema desse tipo lá. Bem, vamos ver se a gente não pode, pelo menos dar um passo em direção a isso. Deixe-me propor uma nova estrutura de dados que pode ser usado para diferentes coisas, neste caso denominada tabela hash. E por isso estamos realmente olhando para trás em uma matriz, no caso em apreço, e arbitrariamente, eu desenhei esta tabela hash como uma matriz com uma espécie de matriz bidimensional - ou melhor, ele é descrito aqui como um dois matriz dimensional - mas este é apenas uma matriz de tamanho 26, de tal modo que se chamar a tabela da matriz, suporte de mesa zero é o rectângulo no topo. Tabela suporte 25 é o retângulo na parte inferior. E é assim que eu poderia chamar um conjunto de dados estrutura em que deseja armazenar nomes de pessoas. Assim, por exemplo, e eu não vou chamar a coisa toda aqui no alto, se eu tinha essa matriz, que eu estou indo agora para chamar uma tabela hash, e este é novamente Local de zero. Esta aqui é a localização um, e assim por diante. Eu afirmo que eu quero usar esses dados estrutura, por causa da discussão, para armazenar os nomes das pessoas, Alice e Bob e Charlie e outros nomes. Então, pense nisso agora, como o início de, digamos, um dicionário com muitas palavras. Elas acontecem para ser nomes No nosso exemplo aqui. E tudo isso é muito pertinente, talvez, para implementação de um corretor ortográfico, como talvez para o problema de definir seis. Então, se temos uma matriz de tamanho total 26 de modo que este é o local 25 na parte inferior, e eu afirmo que Alice é a primeira palavra no dicionário de nomes que eu quero inserir na RAM, para essa estrutura de dados, onde estão instintos dizendo que Alice nome deve ir neste array? Temos 26 opções. Onde queremos colocá-la? Queremos que ela no suporte zero, certo? Um para Alice, vamos chamar isso de zero. E B será um, e C será de dois. Então, vamos escrever Nome aqui em cima de Alice. Se, então, inserir Bob, seu nome vai aqui. Charlie vai passar aqui. E assim por diante ao longo esta estrutura de dados. Esta é uma estrutura de dados maravilhoso. Por quê? Bem, o que é o tempo de execução inserir o nome de um humano para esta estrutura de dados agora? Dado que esta tabela é implementado, verdadeiramente, como uma matriz. Bem, é tempo constante. É fim de um. Por quê? Bem, como você determina onde Alice pertence? Você olha para qual letra do seu nome? O primeiro. E você pode chegar lá, se é uma string, apenas olhando para cadeia Suporte de zero. Assim, o caráter zeroth da cadeia. Isso é fácil. Fizemos isso no crypto semanas de atribuição atrás. E então quando você sabe que Alice A carta é a capital, podemos subtrair off 65 ou maiúsculo si, que nos dá zero. Portanto, sabemos agora que Alice pertence na posição zero. E dado um ponteiro a estes dados estrutura, de alguma sorte, o tempo faz ele me levar para encontrar a localização zero em um array? Apenas um passo, certo É hora constante devido a que o acesso aleatório proposta era uma característica de uma matriz. Assim, em breve, descobrir o que o índice do nome de Alice é, que é, em Neste caso, é A, ou vamos apenas resolver que a zero, em que B é um C e é dois, imaginando que fora É tempo constante. Eu só tenho que olhar para a sua primeira carta, descobrir onde zero é um matriz também é de tempo constante. Então, tecnicamente isso é como dois passos agora. Mas isso ainda é constante. Então, nós chamamos isso de um grande O, então nós Alice inserido nesta tabela em tempo constante. Mas, claro, eu estou sendo ingênuo aqui, certo? E se há uma Aaron na classe? Ou Alicia? Ou quaisquer outros nomes começando com A. Onde vamos colocar essa pessoa, certo? Quero dizer, agora há apenas três pessoas sobre a mesa, então talvez nós deve colocar Aaron no local zero um, dois, três. Certo, eu poderia colocar um aqui. Mas então, se tentarmos inserir David em Nesta lista, onde é que David vai? Agora o nosso sistema começa a quebrar para baixo, certo? Porque agora David acaba aqui Aaron se é realmente aqui. E agora toda essa idéia de ter um estrutura de dados limpo que nos dá inserções de tempo constantes, não está mais constante de tempo, porque eu tenho que verificar, oh, droga, alguém já está no local de Alice. Deixe-me investigar o resto dos dados estrutura, procurando um local para colocar alguém como o nome de Aaron. E assim que também está começando ter tempo linear. Além disso, se você agora quer encontrar o Aaron nesta estrutura de dados, e você verifique, eo nome de Aaron não está aqui. Idealmente, você teria apenas que dizer Arão não na estrutura de dados. Mas se você começar a fazer sala para Aaron onde deveria ter havido um D ou um E, você, o pior caso, tem que verificar Toda a estrutura de dados, em caso em que se transforma em algo linear no tamanho da tabela. Então tudo bem, eu vou corrigir isso. O problema aqui é que eu tinha 26 elementos nesta matriz. Deixe-me mudar isso. Gritos. Deixe-me mudar isso para que, em vez de ser tamanho 26 no total, observe o fundo índice vai mudar de n menos 1. Se 26 é claramente demasiado pequeno para os seres humanos ' nomes, porque há milhares de nomes do mundo, vamos fazer em 100 ou 1000 ou 10000. Vamos apenas alocar muito mais espaço. Bem, isso não significa necessariamente diminuir a probabilidade de que não terá dois pessoas com nomes que começam com A, e assim, você estava indo para tentar colocar um nomes em local ainda a zero. Eles ainda vão colidir, o que significa que ainda precisa de uma solução para colocar Alice e Arão e Alicia e outros nomes que começam com A em outro lugar. Mas como um grande problema é esse? Qual é a probabilidade de que você tem colisões em uma base de dados estrutura como esta? Bem, deixe-me - nós vamos voltar a essa pergunta aqui. E olha como poderíamos resolvê-lo pela primeira vez. Deixa-me tirar esta proposta aqui. O que acabamos de descrever é um algoritmo, uma heurística chamado linear sondagem segundo a qual, se você tentou inserir algo aqui nestes dados estrutura, o que é denominado tabela hash e não há espaço lá, você verdadeiramente sondar a estrutura de dados verificação, é esta disponível? É esta disponível é esta disponível? É esta disponível? E quando ele finalmente seja, inserir o nome que originalmente planejado em outro lugar naquele local. Mas, no pior dos casos, o único ponto pode ser a parte inferior dos dados estrutura, o fim do array. Então linear sondagem, no pior caso, transforma em um algoritmo linear em que Aaron, se ele passa a ser inserido última neste tipo de estrutura de dados, ele pode colidir com esta primeira posição, mas depois acabam por má sorte no final. Portanto, esta não é uma constante tempo santo graal para nós. Esta abordagem para a inserção de elementos uma estrutura de dados, chamado de hash tabela não parecem ser de tempo constante pelo menos, no caso geral. Ele pode transformar-se em algo linear. Então, o que se resolver conflitos um pouco diferente? Então aqui vai um mais sofisticado abordagem para o que é ainda chamada de tabela de hash. E, de hash, como um aparte, o que Quero dizer, é o índice que Me referi anteriormente. Para hash de alguma coisa pode ser pensada como um verbo. Então, se você haxixe Alice é um nome, uma função de hash, por assim dizer, deve retornar um número. Neste caso será zero se a ela pertence localização zero, um, se ela pertence a um local, e assim por diante. Assim, a minha função de hash, até agora, tem sido super simples, apenas olhando para o primeira letra do nome de alguém. Mas uma função de hash recebe como entrada de algum pedaço de dados, um string, um inteiro, qualquer que seja. E ele cospe tipicamente um número. E esse número é o local onde os dados elemento pertence a uma estrutura de dados conhecido aqui como uma tabela hash. Então, só intuitivamente, esta é uma contexto ligeiramente diferente. Isso, na verdade está se referindo a um exemplo envolvendo aniversários, quando pode haver tantos como 31 dias no mês. Mas o que essa pessoa decidir fazer em caso de uma colisão? Contexto agora a ser, não uma colisão de nomes, mas uma colisão de aniversários, se duas pessoas têm a mesma data de aniversário no o 2 º de outubro, por exemplo. Estudante: [inaudível]. COLUNA 1: Sim, então aqui nós temos a alavancagem de listas ligadas. Portanto, parece um pouco diferente do que chamou mais cedo. Mas parece que uma matriz no lado esquerdo. Esse é um índice, pois nenhuma razão particular. Mas ainda é um array. É uma matriz de ponteiros. E cada um desses elementos, cada um de esses círculos ou barras - a barra representando nula - cada uma delas ponteiros é, aparentemente, apontando para que a estrutura de dados? Uma lista ligada. Portanto, agora temos a capacidade de codificar em nosso programa o tamanho da tabela. Neste caso, sabemos que nunca há mais de 31 dias em um mês. Tão difícil codificação de um valor como 31 é razoável nesse contexto. No contexto de nomes, codificação dura 26 não é razoável que as pessoas nomes começam apenas com, por exemplo, o alfabeto de A a Z. envolvendo Podemos meter-los todos em que os dados estrutura, desde que, quando temos um colisão, não colocar os nomes aqui, que em vez de pensar essas células como não próprias cordas, mas como ponteiros para, por exemplo, Alice. E então Alice pode ter outro ponteiro para outro nome começando com A. e Bob realmente passa por aqui. E se há outro nome que começa com B, ele acaba por aqui. E assim, cada um dos elementos do presente mesa de dois, se nós projetamos este um pouco mais inteligente - Vamos lá - se nós projetamos este um pouco mais inteligentemente, torna-se agora um conjunto de dados de adaptação estrutura, onde não há limite rígido em quantos elementos você pode inserir nele porque se você tem uma colisão, isso é bom. Basta ir em frente e anexá-lo ao o que vimos um pouco atrás era conhecido como uma lista ligada. Bem, vamos fazer uma pausa por um momento. O que é que a probabilidade de uma colisão em primeiro lugar? Certo, talvez eu estou mais pensando, talvez Eu estou sobre engenharia este problema, porque você sabe o quê? Sim, eu posso chegar a arbitrária exemplos em cima da minha cabeça, como Allison e Aaron, mas, na realidade, dada uma distribuição uniforme do insumos, ou seja algumas inserções aleatórias numa estrutura de dados, o que é realmente a probabilidade de uma colisão? Bem vê, é realmente super alta. Deixe-me generalizar este este problema é como. Assim, em uma sala de n CS50 estudantes, o que é a probabilidade de que pelo menos dois alunos na sala têm a mesma data de aniversário? Portanto, não há o quê. alguns hund - 200, 300 pessoas aqui e vários centenas de pessoas em casa hoje. Então, se você queria perguntar a nós mesmos o que é a probabilidade de duas pessoas nesta sala que tem o mesmo aniversário, podemos descobrir isso. E eu afirmo na verdade, existem dois pessoas com o mesmo aniversário. Por exemplo, alguém tem aniversário hoje? Ontem? Amanhã? Tudo bem, então parece que eu vou ter que fazer isso mais ou menos 363 vezes para realmente descobrir se temos uma colisão. Ou podemos fazer isso matematicamente ao invés de tediosamente fazer isso. E propor o seguinte. Assim, proponho que poderia modelar o probabilidade de duas pessoas que têm a mesma data de aniversário como a probabilidade de um menos a probabilidade de não ter um aniversário no mesmo dia. Então, para conseguir isso, e este é apenas o fantasia maneira de escrever isso, pois o primeira pessoa na sala, ele ou ela pode ter qualquer um dos possíveis aniversários assumindo 365 dias no ano, com desculpas às pessoas com o 29 º aniversário de fevereiro. Assim, a primeira pessoa nesta sala é livre ter qualquer número de aniversários fora das 365 possibilidades para que vamos fazer que 365 dividido por 365, , que é um. A próxima pessoa na sala, se o objetivo é evitar uma colisão, só pode ter seu aniversário em como diversos dias possíveis? 364. Assim, o segundo termo da expressão é esta essencialmente, fazendo que a matemática para nós subtraindo-se fora de um dia possível. E, em seguida, no dia seguinte, no dia seguinte, o dia seguinte até ao número total de pessoas na sala. E se então considerar, qual é então a probabilidade de não ter todos aniversários únicas, mas novamente um menos que, o que temos é uma expressão que pode muito fantasiosamente semelhante a este. Mas é mais interessante olhar visualmente. Este é um gráfico em que no eixo dos x é o número de pessoas na sala, o número de aniversários. No eixo y representa a probabilidade de uma colisão, duas pessoas tendo o mesmo aniversário. E o takeaway partir desta curva é que, assim que você começa a gostar 40 estudantes, está-se a uma probabilidade de 90% combinatorically de dois ou mais pessoas que têm aniversário no mesmo dia. E uma vez que você começa a gostar de 58 pessoas é cerca de 100% de uma possibilidade os dois pessoas na sala vai ter o mesma data de aniversário, mesmo que não haja 365 ou 366 possíveis baldes e apenas 58 pessoas na sala. Apenas estatisticamente é provável que você obter colisões, o que em suma motiva esta discussão. Que, mesmo que começar a fantasia aqui, e começar a ter essas cadeias, ainda estamos vai ter colisões. Assim que levanta a questão: o que é o custo de fazer inserções e deleções em uma estrutura de dados como este? Bem, deixe-me propor - e deixe-me voltar para a tela sobre aqui - se temos n elementos no lista, por isso, se estamos tentando inserir n elementos, e nós temos quantos total de baldes? Digamos que 31 baldes totais no caso de aniversário. Qual é o comprimento máximo de um destas cadeias potencialmente? Se novamente não é possível 31 aniversários em um determinado mês. E estamos apenas a aglutinação todos - na verdade, isso é um exemplo estúpido. Vamos fazer 26 em vez. Então, se realmente tem pessoas cujos nomes começar com A a Z, dando assim nos 26 possibilidades. E nós estamos usando uma estrutura de dados como o que acabamos de ver, em que temos uma matriz de pontos, cada um dos quais aponta para uma lista ligada, onde o primeira lista é de todos com o nome de Alice. A segunda lista é cada um com o nome começar com A, começando com B, e assim por diante. Qual é a duração provável de cada um dos essas listas se assumirmos um bom limpo distribuição de nomes de A a Z através da estrutura de dados inteiro? Há n pessoas na estrutura de dados dividido por 26, se forem bem espalhados por todo o estrutura de dados. Assim, o comprimento de cada um desses cadeias é n dividido por 26. Mas na notação O grande, o que é isso? O que é isso mesmo? Então, é realmente apenas n, certo? Porque nós já disse no passado, ugh que você dividir por 26. Sim, na realidade, ela é mais rápida. Mas, em teoria, não é fundamentalmente tudo o que mais rapidamente. Portanto, não parece ser tudo o que muito mais próximo a este santo graal. Na verdade, este é apenas o tempo linear. Heck, neste ponto, por que não nós basta usar uma lista ligada enorme? Por que não usar apenas um enorme matriz para armazenar os nomes das todos na sala? Bem, ainda há algo convincente sobre uma tabela hash? Existe ainda algo atraente sobre uma estrutura de dados que se parece com isso? Este. Estudante: [inaudível]. COLUNA 1: Certo, e, novamente, se é apenas um algoritmo de tempo linear, e um estrutura de dados em tempo linear, por que não eu apenas armazenar o nome de todos em um grande matriz, ou em uma lista vinculada grande? E parar de fazer CS muito mais difícil do que precisa ser? O que é interessante sobre isso, mesmo embora eu arranhou-lo? Estudante: [inaudível]. COLUNA 1: As inserções não são? Expensive mais. Então inserções potencialmente poderia ainda ser de tempo constante, mesmo se os seus dados estrutura se parece com isso, uma série de apontadores, cada um dos quais está a apontar potencialmente uma lista encadeada. Como você poderia conseguir constante inserção vez de nomes de? Cole-o no frontal, certo? Se sacrificar um objetivo do projeto de anteriormente, onde queríamos manter o nome de todos, por exemplo, classificadas ou todos os números em fase classificados, supor que nós temos um lista ligada indiferenciados. Ele só nos custa um ou dois passos, como no caso de Ben e Brian anteriormente, para inserir um elemento em o início da lista. Então, se nós não nos importamos sobre a classificação todos dos nomes começam com um ou todos os nomes que começam com B, ainda podemos alcançar inserção constante de tempo. Agora, olhando para Alice ou Bob ou qualquer nome mais geral ainda o que é? É grande O de n dividido por 26, no caso ideal, onde todos estão uniformemente distribuído, onde há o maior número de um uma vez que existem de Z, o qual é provavelmente irrealista. Mas isso ainda é linear. Mas aqui, voltamos ao ponto de notação assintótica ser teoricamente verdade. Mas, no mundo real, se eu afirmar que meu programa pode fazer algo 26 vezes mais rápido do que o seu, cujo programa você vai preferir usar? Seu ou meu, que é 26 vezes mais rápido? Realisticamente, a pessoa de quem é 26 vezes mais rápida, ainda que teoricamente nossos algoritmos são executados na mesma assintótica tempo de corrida. Deixe-me propor uma diferente solução completamente. E se isso não explodir sua mente, estamos fora de estruturas de dados. Portanto, esta é uma trie - tipo de um nome estúpido. Ela vem de recuperações, ea palavra está escrito trie, t-r-i-e, por causa de recuperação curso soa como trie. Mas essa é a história da palavra trie. Assim, uma trie é de fato uma espécie de árvore, e também é uma brincadeira com a palavra. E mesmo que você não consegue vê-lo com esta visualização, um trie é um árvore estruturada, como uma árvore genealógica com um antepassado no topo e muito de netos e bisnetos como folhas na parte inferior. Mas cada nó em uma trie é uma matriz. E é em uma matriz - e vamos simplificar por um momento - é uma matriz, neste caso, de tamanho 26, onde cada nó é novamente uma matriz de tamanho 26, onde o elemento de ordem zero, em que Uma matriz representa, ea última em cada elemento de tal array representa Z. Assim, proponho, então, que esses dados estrutura, conhecida como uma trie, pode ser também utilizada para armazenar palavras. Vimos há pouco como poderíamos armazenar palavras, ou neste caso os nomes, e nós viu anteriormente como podemos armazenar números, mas se concentrar em nomes ou seqüências aqui, perceber o que é interessante. Eu afirmo que o nome é Maxwell dentro desta estrutura de dados. Onde você vê Maxwell? Estudante: [inaudível]. COLUNA 1: À esquerda. Então, o que é interessante com estes dados estrutura é, em vez de armazenar o corda M-A-X-W-E-L-L invertida zero, tudo contígua, o que fazer em vez está seguindo. Se esta é uma estrutura de dados como trie, cada um dos nós cujas é novamente uma matriz, e você quer armazenar Maxwell, primeiro você índice e assim nó da raiz, de modo dizer, o nó de nível superior, na posição M, certo, então aproximadamente no meio. E, em seguida, a partir daí, você seguir uma Ponteiro para uma criança nós, por assim dizer. Assim, no sentido de árvore genealógica, você segui-lo para baixo. E que levá-lo para outro nó À esquerda, que é apenas uma outra matriz. E então se você deseja armazenar Maxwell, encontrar o ponteiro que representa A, que é este aqui. Então você vai para o próximo nó. E note - é por isso que a imagem do um pouco enganador - este nó olhar super pequena. Mas para a direita deste é Y e Z. É só o autor tem truncado o imagem de modo que você realmente ver as coisas. Caso contrário, esta imagem seria muito grande. Então, agora você indexar localização X, então W, E E, em seguida, L, em seguida, L. Então qual é essa curiosidade? Bem, se estamos usando esse tipo de novo assumir a forma de armazenar uma string em um estrutura de dados, você ainda precisa essencialmente marcar nos dados estrutura que uma palavra termina aqui. Em outras palavras, cada um desses nós de alguma forma tem que se lembrar que na verdade, seguido todos estes ponteiros e estão deixando um pouco migalha de pão no fundo aqui deste estrutura para indicar M-A-X-W-E-L-L é de facto nesta estrutura de dados. Assim, poderíamos fazer isso da seguinte forma. Cada um dos nós na imagem que acabamos de tem uma serra, uma matriz de tamanho 27. E agora é 27 porque, p definir seis anos, vamos realmente dar-lhe uma apóstrofe, para que possamos ter nomes como O'Reilly e outros com apóstrofos. Mas a mesma idéia. Cada um desses elementos no pontos de matriz para uma struct nó, então apenas um nó. Então isso é muito reminiscente da nossa lista encadeada. E então eu tenho um valor booleano, que eu vou chamar palavra, que só vai ser verdadeiro se uma palavra termina neste nó da árvore. Ele representa efetivamente a pouco triângulo que vimos há pouco. Assim, se uma palavra que termina no nó no árvore, aquele campo palavra será verdadeira, que é conceitualmente a verificação off, ou estamos desenhando esse triângulo, sim, há é uma palavra aqui. Portanto, esta é uma trie. E agora a pergunta é, o que é seu tempo de execução? É grande O de n? É algo mais? Bem, se você tem n nomes nestes dados estrutura, Maxwell sendo apenas um eles, o que é o tempo de execução inserção ou encontrar Maxwell? Qual é o tempo de execução inserção de Maxwell? Se há n outros nomes já em cima da mesa? Sim? Estudante: [inaudível]. COLUNA 1: Sim, é o comprimento do nome, certo? Então M-a-x-w-e-l-l por isso se sente assim O algoritmo é grande de sete. Agora, obviamente, o nome irá variar em comprimento. Talvez seja um nome curto. Talvez seja um nome mais longo. Mas o que é importante aqui é que é um número constante. E talvez não seja realmente constante, Mas Deus, se realisticamente, em um dicionário, provavelmente há algum limite sobre o número de letras de uma o nome da pessoa em um determinado país. E assim, podemos supor que é um valor constante. Eu não sei o que é. É, provavelmente, maior do que pensamos que é. Porque há sempre algum canto caso com um nome muito louco. Então, vamos chamá-lo de k, mas é ainda um constante, presumivelmente, porque cada nome no mundo, pelo menos em um determinado país, é que o comprimento ou mais curto, por isso é constante. Mas quando dissemos algo é grande O de um valor constante, o que é isso realmente equivalente a? Essa é realmente a mesma coisa que dizer de tempo constante. Agora nós somos o tipo de fazer batota, certo? Estamos meio de alavancar alguma teoria aqui para dizer que o bem, a fim de k é realmente só encomendar de um, e é tempo constante. Mas ele realmente é. Porque o insight chave aqui é que se temos n nomes já neste estrutura de dados, e inserção Maxwell é a quantidade de tempo que nos leva a inserir Maxwell em todos os afetados por quantas outras pessoas estão dentro da estrutura de dados? Não parece ser. Se eu tivesse um bilhão de mais elementos para esta trie, e então insira Maxwell, é ele em todos os afetados? Não. E isso é diferente de qualquer um dos dados do dia estruturas que temos visto até agora, onde o tempo de execução do seu algoritmo é completamente independente de quanto material é ou não é já em que a estrutura de dados. E assim, com esta lhe proporciona agora é um oportunidade para p conjunto de seis, que será novamente envolver implementar seu próprio corretor ortográfico, a leitura em 150 mil palavras, a melhor forma de armazenar esse não é necessariamente evidente. E embora eu aspirava a encontrar o santo graal, eu não afirmam que uma trie é. Na verdade, uma tabela hash pode muito bem provar ser muito mais eficiente. Mas esses são apenas - isso é apenas uma das decisões de projeto você terá que fazer. Mas no encerramento vamos ter 50 ou mais segundos para dar uma olhada no que está frente na próxima semana e que a transição para além a partir desta linha de comando mundo, se programas em C para as coisas web base e linguagens como PHP e JavaScript e da própria internet, protocolos como HTTP, o que você tida como certa por muitos anos agora, e digitou a maioria cada dia, talvez, ou visto. E vamos começar a descascar a camadas de qual é a Internet. E qual é o código que subjacente ferramentas de hoje. Então 50 segundos este teaser aqui. Eu dar-lhe guerreiros da rede. [REPRODUÇÃO] -Ele veio com uma mensagem. Com um protocolo de todos os seus próprios. Ele veio para um mundo de firewalls cruéis routers indiferente, e os perigos longe pior que a morte. Ele é rápido. Ele é forte. Ele é TCPIP. E ele tem o seu endereço. Guerreiros da rede. [FIM REPRODUÇÃO DE VÍDEO] COLUNA 1: É assim que a internet deve trabalhar a partir da próxima semana.