>> 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.
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 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.