[MÚSICA DE JOGO]
DAVID J. MALAN: Tudo bem.
Este é CS50.
Esta é semana de cinco continuou, e nós tenho uma boa notícia e uma má notícia.
Então boa notícia é que CS50 lança nesta sexta-feira.
Se você gostaria de se juntar a nós, cabeça para o URL de costume aqui.
Uma notícia ainda melhor, nenhuma palestra próxima segunda-feira dia 13.
Pouco menos melhor notícia, questionário zero é próxima quarta-feira.
Mais detalhes podem ser encontrados neste URL aqui.
E ao longo dos próximos dois dias estaremos preenchendo os espaços em branco
no que diz respeito aos quartos que teremos reservados.
Melhor notícia é que não vou ser uma revisão de todo o curso
sessão no próximo Segunda-feira à noite.
Fique atento para o curso de Site para localização e detalhes.
Seções, embora seja um férias, também vai atender bem.
Melhor notícia, palestra na próxima sexta.
Portanto, esta é uma tradição que têm, de acordo com o conteúdo programático.
Apenas-- que vai ser incrível.
Você vai ver coisas como estruturas de dados de tempo constante
e tabelas de hash e árvores e tentativas.
E vamos falar sobre os problemas de aniversário.
Um monte de coisas aguarda próxima sexta-feira.
Está bem.
De qualquer forma.
>> Então lembro que fomos focando esta imagem do que está
dentro da memória do nosso computador.
Assim, a memória ou a memória RAM é onde os programas existir enquanto você está executando-os.
Se você clicar duas vezes um ícone para executar algum programa
ou clique duas vezes em um ícone para abrir algum arquivo,
ele é carregado a partir do disco rígido ou unidade de estado sólido
na RAM, Random Access Memory, onde ele vive até se desligar,
a tampa fecha portátil, ou sair do programa.
>> Agora que a memória, de que você provavelmente tem
1 gigabyte nos dias de hoje, 2 gigabytes, ou mesmo muito mais,
geralmente é colocado para fora para um determinado programa
neste tipo de rectangular modelo conceitual
pelo qual temos a pilha na parte inferior e um monte de outras coisas no topo.
A coisa no topo temos visto nesta imagem
antes, mas nunca conversamos sobre é o chamado segmento de texto.
Segmento de texto é apenas uma maneira elegante de dizer os zeros e uns que
compor seu programa compilado real.
>> Então, quando você clica duas vezes Microsoft Word no seu Mac ou PC,
ou ao executar o ponto barra Mario em um Computador Linux em sua janela de terminal,
os zeros e uns que compõem Word ou Mario são armazenados temporariamente
na memória RAM do seu computador na chamada segmento de texto para um programa particular.
Abaixo disso vai inicializado e dados não inicializado.
Este é o material como variáveis ​​globais, que não usei muitos,
mas de vez em quando temos tinha variáveis ​​globais
ou estaticamente cordas definido que é codificado palavras como "Olá"
que não são levados em do utilizador que são codificados em seu programa.
>> Agora, para baixo na parte inferior nós ter a pilha de chamada.
E a pilha, até agora, temos sido usando para que tipos de efeitos?
O que a pilha foi utilizado?
Sim?
>> Audiência: Funções.
>> DAVID J. MALAN: Para funções?
Em que sentido para as funções?
>> AUDIÊNCIA: Quando você chamar uma função, o argumentos são copiados para a pilha.
>> DAVID J. MALAN: Exatamente.
Quando você chama uma função, a argumentos são copiados para a pilha.
Assim, qualquer Xs ou Y do ou de um ou de B que você está passando para uma função
são temporariamente colocados em a pilha assim chamado,
apenas como um dos Annenberg bandejas salão de jantar, e também as coisas
como variáveis ​​locais.
Se a sua função foo ou sua troca função de ter variáveis ​​locais,
como temperatura, esses dois acabar na pilha.
Agora, não vamos falar muito sobre eles, mas essas variáveis ​​de ambiente
na parte inferior que vimos há um tempo atrás, quando Eu estava mexendo no teclado um dia
e eu comecei a acessar coisas argv como 100 ou argv 1000,
apenas elements-- eu esqueço Números de a, mas que
Não era para ser acessado por mim.
Começamos a ver alguns símbolos funk na tela.
Aqueles eram chamados variáveis ​​de ambiente
como configurações globais para o meu programa ou para o meu computador, não
sem relação com a recente bug que discutimos,
Shellshock, que tem sido assola muito poucos computadores.
>> Agora, por último, em foco de hoje que em última análise vai ser na pilha.
Este é mais um pedaço de memória.
E tudo isto fundamentalmente memória é a mesma coisa.
É o mesmo hardware.
Nós somos apenas uma espécie de tratamento de diferentes grupos
de bytes para diferentes fins.
A pilha também vai ser onde variáveis ​​e memória que você solicitar
a partir do sistema operativo é temporariamente armazenado.
>> Mas há um tipo de problema aqui, como a foto indica.
Nós meio que temos dois navios prestes a colidir.
Porque, como você usa cada vez mais da pilha, e como vemos hoje
para a frente, como você usa cada vez mais a pilha, com certeza as coisas ruins podem acontecer.
E, de fato, podemos induzir que intencionalmente ou não.
Assim, o suspense última tempo era esse programa,
que não servem qualquer funcional outro propósito além de demonstrar
como você como um cara mau pode realmente ter vantagem de bugs no programa de alguém
e assumir um programa ou até mesmo um sistema de computador ou servidor de todo.
Então, só para olhar brevemente, você notar que o principal na parte inferior
toma em linha de comando argumentos, como por argv.
E tem uma chamada para uma função f, essencialmente uma função de chamada sem nome
f, e ele está passando em argv [1].
>> Então, qualquer palavra que o usuário digita em pelo a solicitação após o nome deste programa,
e então esta função arbitrária up top, f, leva em uma corda, AKA char *,
como começamos a discutir, e ele simplesmente chama de "bar".
Mas poderíamos chamá-lo de nada.
E então ele declara, dentro de f, uma série de caracteres
chamado C-- 12 desses personagens.
>> Agora, pela história que eu estava dizendo um momento atrás, onde na memória
c é, ou são aqueles 12 PERSONAGENS vai acabar?
Só para ficar claro.
Sim?
>> AUDIÊNCIA: Na pilha.
>> DAVID J. MALAN: Na pilha.
Assim, c é uma variável local.
Estamos pedindo para 12 caracteres ou 12 bytes.
Aqueles vão acabar na pilha de chamada.
Agora, finalmente, é esta outra função que é realmente muito útil,
mas não usei muito nós mesmos, strncopy.
Significa cópia corda, mas só n letras, n caracteres.
Então n caracteres será copiado de bar em c.
E quantos?
O comprimento da barra.
Assim, em outras palavras, que uma linha, strncopy,
vai copiar efetivamente bar no c.
>> Agora, apenas a espécie de antecipar A moral desta história,
o que é potencialmente problemático aqui?
Mesmo que estamos verificando o comprimento de bar e passá-la em strncopy,
o que é seu intestino dizendo é ainda quebrado sobre este programa?
Sim?
>> AUDIÊNCIA: Não inclui espaço para o caractere nulo.
DAVID J. MALAN: Não inclui espaço para o caractere nulo.
Potencialmente, ao contrário de as práticas do passado que nem sequer
tem tanto como uma vantagem de 1 a acomodar esse caractere nulo.
Mas é ainda pior do que isso.
O que mais estamos deixando de fazer?
Sim?
>> AUDIÊNCIA: [inaudível]
DAVID J. MALAN: Perfeito.
Nós codificado 12 muito arbitrariamente.
Isso não é tanto a problema, mas o facto
que não estamos ainda verificando se o comprimento da barra é menos do que 12,
caso em que vai ser seguro para colocá-lo na memória
chamada c que temos alocado.
Com efeito, se a barra é assim 20 caracteres,
esta função parece estar copiando 20 personagens de bar em c, assim,
tendo, pelo menos, 8 bytes que não devem ser.
Essa é a implicação aqui.
>> Assim, no programa curto, quebrado.
Não como um grande negócio.
Talvez você começa uma falha de segmentação.
Todos nós já tivemos erros nos programas.
Todos nós pode ter erros em programas de agora.
Mas qual é a implicação?
Bem, aqui está uma versão ampliada-in de que imagem de memória do meu computador.
Este é o fundo do meu stack.
E, de fato, bem no fundo é o que é chamado pilha rotina pai, maneira extravagante
de dizer que é principal.
Assim que quem chamou a função f que estamos falando.
Assim, este é o fundo da pilha.
Endereço de retorno é algo novo.
Ele sempre esteve lá, sempre estive nessa imagem.
Nós apenas nunca chamou atenção para ele.
Porque acontece o caminho c funciona é que quando uma função chama outra,
não só os argumentos para que função são empurrados para a pilha,
não só local de função variáveis ​​são empurrados para a pilha,
algo chamado um endereço de retorno também é colocado na pilha.
Especificamente, se as chamadas principais Foo, principais do próprio endereço na memória, algo boi,
efetivamente é colocado na pilha de modo que, quando f é feito de executá-lo
sabe onde pular de volta no texto segmento, a fim de continuar a execução.
>> Então, se estamos aqui, conceitualmente, na principal, então f é chamada.
Como f saber quem para controle de mão de volta?
Bem, este pequeno breadcrumb em vermelho aqui,
chamado o endereço de retorno, ele só cheques, o que é que o endereço de retorno?
Oh, deixe-me saltar de volta para principal aqui.
E isso é um pouco de uma simplificação,
porque os zeros e uns para principal são tecnicamente
aqui em cima no segmento de tecnologia.
Mas essa é a idéia. f só tem que saber o que
em última análise, em que o controlo de volta.
>> Mas a forma como os computadores Há muito tempo estabelecidas as coisas
como variáveis ​​locais e argumentos é assim.
Assim, no topo da imagem em azul é o quadro de pilha para f, então tudo
da memória que f especificamente é utilizado.
Então, nesse sentido, perceber que bar é neste quadro.
Bar era seu argumento.
E defendeu que os argumentos para funções são empurrados para a pilha.
E c, é claro, é Também nesta foto.
>> E apenas para fins de notação, notar no canto superior esquerdo
é o que seria c suporte 0 e então ligeiramente para baixo à direita
é c suporte 11.
Portanto, em outras palavras, você pode imaginar que há uma grade de bytes
há, em primeiro lugar, que é superior esquerdo, inferior do que
é o último dos 12 bytes.
>> Mas agora tentar avançar.
O que está para acontecer se passarmos em um bar de cadeia que é mais do que c?
E não estamos verificando se é de fato maior do que 12.
Qual parte da imagem vai se substituído por bytes 0, 1, 2, 3,
dot dot dot, 11, e, em seguida, ruim, 12, 13 a 19?
O que vai acontecer aqui, se inferir a partir da ordenação
que c 0 suporte está no topo e c suporte 11 é uma espécie de baixo
à direita?
Sim?
>> AUDIÊNCIA: Bem, ele vai para substituir o bar char *.
>> DAVID J. MALAN: Sim, parece que você está indo para substituir carvão bar *.
E pior, se você enviar em um tempo muito longo string, você pode até substituir o que?
O endereço de retorno.
Que mais uma vez, é como um breadcrumb para dizer ao programa onde
voltar para quando f é feito de ser chamado.
>> Então, o que bandidos costumam fazer é se deparar com um programa
que eles são curiosos se é explorável, carrinho, de tal maneira
que ele ou ela pode tomar vantagem desse bug,
geralmente eles não recebem este direito pela primeira vez.
Eles só começar a enviar, por exemplo, seqüências aleatórias em seu programa,
se no teclado, ou, francamente eles provavelmente
escrever um pequeno programa para apenas gerar automaticamente cordas,
e começar a bater em seu programa o envio de lotes de entradas diferentes
em diferentes comprimentos.
>> Assim que suas falhas do programa, isso é uma coisa incrível.
Porque isso significa que ele ou ela descobriu
o que provavelmente é de fato um bug.
E então eles podem ficar mais inteligente e começar a se concentrar mais estreitamente
sobre a forma de explorar esse bug.
Em particular, o que ele ou ela pode fazer é enviar, no melhor dos casos, Olá.
Não é grande coisa.
É uma cadeia que é suficientemente curto.
Mas e se ele ou ela envia, e vamos generalizar-lo como,
ataque code-- tão zeros e os que fazem as coisas
rm-rf como, que retire tudo a partir do disco rígido ou enviar spam
ou de alguma forma a atacar máquina?
>> Por isso, se cada uma delas letras A apenas representa,
conceitualmente, ataque, ataque, ataque, ataque, um código ruim
que alguém escreveu, mas se essa pessoa é inteligente o suficiente
não apenas para incluir todos desses rm-rfs, mas também
que os seus últimos bytes ser um número que corresponde
para o endereço do seu ou seu próprio código de ataque
que ele ou ela passou em apenas , fornecendo-lhe no prompt,
você pode efetivamente enganar o computador para perceber quando f é feito em execução,
oh, é hora de eu saltar de volta para o endereço do remetente vermelha.
Mas porque ele ou ela tem de alguma forma sobrepostas que o endereço de retorno
com o seu próprio número, e eles são inteligentes o suficiente
ter configurado que número para se referir, como você
ver no super top canto esquerdo lá,
o endereço real no computador de memória de algum do seu código de ataque,
um bandido pode enganar o computador para executar o seu próprio código.
>> E esse código, mais uma vez, pode ser qualquer coisa.
É geralmente chamado código shell, que é apenas
uma forma de dizer que não é geralmente algo tão simples como rm-rf.
É realmente algo como Bash, ou um programa real que lhe dá
ou seu controle programático para executar qualquer outra coisa que eles querem.
Então, em suma, tudo isso deriva do simples fato
que este bug não envolveu a verificação os limites de sua matriz.
E porque o caminho computadores de trabalho é que eles
utilizar a pilha efetivamente, conceitualmente,
inferior em cima, mas, em seguida, os elementos você empurrar para a pilha crescer de cima para baixo,
isso é extremamente problemático.
Agora, existem maneiras de contornar isso.
E, francamente, há línguas com a qual trabalhar em torno deste.
Java é imune, por exemplo, a esta questão particular.
Porque não dar-lhe indicações.
Eles não dão a você endereços de memória diretas.
Assim, com este poder que temos tocar em nada na memória
que queremos vem, na verdade, um grande risco.
>> Portanto, manter um olho para fora.
Se, francamente, nos meses ou anos, a qualquer hora
você ler sobre alguma exploração de um programa ou de um servidor,
se você já viu um toque de algo como um ataque de estouro de buffer,
ou estouro de pilha é um outro tipo de ataque, semelhante em espírito,
tanto quanto inspira o site da nome, se você sabe disso,
tudo está falando apenas transbordando o tamanho de algum personagem
matriz ou matriz algum modo mais geral.
Todas as perguntas, então, sobre este assunto?
Não tente fazer isso em casa.
>> Tudo certo.
Então malloc, até agora, tem sido o nosso novo amigo em que podemos alocar memória
que não sabem necessariamente em avançar que queremos de modo que não temos
código rígido em nossa Os números de programas como 12.
Uma vez que o usuário nos diz o quanto dados que ele ou ela quer de entrada,
podemos malloc que muita memória.
>> Então malloc se vê, ao medida em que temos vindo a utilizar,
explicitamente última vez, e em seguida, vocês têm usado
para GetString sem saber para várias semanas, todos da memória do malloc
vem o chamado montão.
E é por isso getString, por exemplo, pode alocar memória dinamicamente
sem saber o que você está vai digitar com antecedência,
entregá-lo de volta um ponteiro para a memória, e que a memória ainda é seu para manter,
mesmo depois getString retorna.
Como recordação depois de tudo que o pilha está constantemente indo para cima e para baixo,
cima e para baixo.
E assim que ele vai para baixo, isso significa que qualquer memória
Esta função deve não ser usado por qualquer pessoa.
É valores de lixo agora.
>> Mas a pilha está aqui em cima.
E o que é agradável sobre malloc é que quando malloc aloca memória até aqui,
não é afetado, pois o maior parte dos casos, por a pilha.
E assim qualquer função pode acessar memória que tenha sido malloc'd,
até mesmo por uma função como getString, mesmo depois de ser devolvidos.
>> Agora, o inverso do malloc é gratuito.
E, de fato, a regra que precisa começar a adoptar
é qualquer, qualquer, qualquer hora que você usar malloc você deve usar-se livre, eventualmente,
no mesmo ponteiro.
Todo esse tempo que temos vindo a escrever bugs, código de buggy, por muitas razões.
Mas um dos quais tem sido usando a biblioteca de CS50, que
em si é deliberadamente Buggy, que vazamentos de memória.
Toda vez que você chamou getString ao longo das últimas semanas
estamos pedindo a operação sistema, Linux, para a memória.
E você nunca já dado de volta.
E isso não é, em praticar, uma coisa boa.
>> E Valgrind, um dos ferramentas introduzidas no Pset 4,
é tudo a ajudar você agora encontrar erros como esse.
Mas, felizmente para Pset 4 você não precisa para usar a biblioteca CS50 ou getString.
Assim, todos os erros relacionados à memória são em última análise, vai ser o seu próprio.
>> Então malloc é mais do que apenas conveniente para este propósito.
Na verdade, podemos agora resolver fundamentalmente diferentes problemas,
e, fundamentalmente, resolver problemas mais eficazmente como promessa por semana zeros.
Até agora, esta é a mais sexy estrutura de dados que tivemos.
E por estrutura de dados Eu só quero dizer uma forma de memória conceituar
de uma forma que vai além de apenas dizer: este é um inteiro, este é um caracter.
Podemos começar com as coisas de cluster juntos.
>> Assim, um conjunto parecido com este.
E o que foi fundamental em cerca de uma matriz é que lhe dá
back-to-back pedaços de memória, cada uma das quais
vai ser do mesmo tipo, int int, int, int ou char, char, char,
car.
Mas há algumas desvantagens.
Este, por exemplo, é uma matriz de tamanho seis.
Suponha que você preencha essa matriz com seis números e, em seguida, por qualquer motivo,
o usuário quer dar você um sétimo número.
Onde você colocou?
>> Qual é a solução se você tiver criada uma matriz sobre a pilha,
por exemplo, apenas com a semana dois notação que introduzimos,
de colchetes com um número dentro?
Bem, você tem seis números nessas caixas.
O que seus instintos ser?
Onde você deseja colocá-lo?
>> AUDIÊNCIA: [inaudível]
>> DAVID J. MALAN: Desculpe?
>> AUDIÊNCIA: Coloque-o no final.
>> DAVID J. MALAN: Coloque-o no final.
Então, só para a direita, fora da caixa.
O que seria bom, mas Acontece que você não pode fazer isso.
Porque se você não pediu para este pedaço de memória,
poderia ser por acaso que este está a ser usado por outra variável
completamente.
Pense de volta uma semana ou assim quando nós colocamos os nomes de Zamyla e Davin e Gabe
na memória.
Eles estavam literalmente back to back to back.
Portanto, não podemos necessariamente confiar que tudo de
aqui está disponível para eu usar.
>> Então o que mais você pode fazer?
Bem, uma vez que você perceber precisa de uma matriz de tamanho sete,
você pode simplesmente criar um matriz de tamanho sete então usar
um loop ou um loop while, copiá-lo para a nova matriz,
e, em seguida, de alguma forma, se livrar de essa matriz ou simplesmente parar de usá-lo.
Mas isso não é particularmente eficiente.
Em suma, as matrizes não deixe redimensionar dinamicamente.
>> Assim, por um lado, obtém de acesso aleatório, que é incrível.
Porque nos permite fazer coisas como dividir e conquistar,
pesquisa binária, todos os quais temos falou na tela aqui.
Mas você pintar sozinho em um canto.
Assim que você acertar o fim de sua matriz,
você tem que fazer uma muito operação dispendiosa
ou escrever um monte de código agora lidar com esse problema.
>> Então, o que se em vez tivemos algo chamado uma lista,
ou uma lista ligada em particular?
E se em vez de ter retângulos volta para trás para trás,
temos retângulos que deixam um pouco pouco espaço de manobra entre eles?
E mesmo que eu desenhei este foto ou adaptado esta imagem
a partir de um dos textos aqui para voltar ao volta para trás muito ordenada, na realidade,
um desses rectângulos poderia estar aqui na memória.
Um deles poderia ser até aqui.
Um deles poderia ser até aqui, aqui, e assim por diante.
>> Mas o que se chamou, neste caso, setas
que de alguma forma vincular estes retângulos juntos?
Na verdade, temos visto um técnico encarnação de uma seta.
O que temos usado nos últimos anos dias que, debaixo do capô,
é representativa de uma seta?
Um ponteiro, certo?
>> Então, o que se, em vez de apenas armazenar os números,
como 9, 17, 22, 26, 34, E se nós não armazenados
apenas um número, mas um apontador ao lado de cada número tal?
Então, que assim como você enfiar uma agulha através de um monte de tecido,
coisas de alguma forma de subordinação em conjunto, de modo semelhante pode
nós com ponteiros, como encarnado por setas aqui,
tipo de tecer desses retângulos individuais
por efetivamente usando um ponteiro ao lado de cada número que
aponta para algum número seguinte, que indica, por sua vez, alguns próximo número?
Portanto, em outras palavras, o que se realmente queria
para implementar algo parecido com isto?
Bem, infelizmente, esses retângulos, , pelo menos, um com 9, 17, 22,
e assim por diante, estes não são mais praças agradáveis ​​com números individuais.
O fundo, retângulo abaixo de 9, por exemplo,
representa o que deve ser um ponteiro, 32 bits.
Agora, eu ainda não estou ciente de qualquer tipo de dados em C que lhe dá não só um int
mas um apontador completamente.
>> Então, qual é a solução, se quisermos inventar a nossa própria resposta para isso?
Sim?
>> AUDIÊNCIA: [inaudível]
>> DAVID J. MALAN: O que é isso?
>> AUDIÊNCIA: Nova estrutura.
>> DAVID J. MALAN: Sim, então por que Não podemos criar uma nova estrutura,
ou em C, um struct?
Vimos estruturas antes, se brevemente, onde lidamos com uma estrutura de estudante
como este, que tinha um nome e uma casa.
Em Pset 3 fuga você usou um todo bando de GRect structs-- e GOvals
Stanford que criou a informações de cluster juntos.
Então, o que se tomarmos essa mesma idéia de as palavras-chave "typedef" e "struct"
e, em seguida, algumas coisas específicas do aluno, e evoluir esta no seguinte:
typedef struct node-- e nó é apenas uma ciência da computação muito genérico
prazo para algo em uma estrutura de dados, um recipiente, de uma estrutura de dados.
Um nó Eu reivindico vai ter um int n, totalmente simples,
e, em seguida, um pouco mais enigmaticamente, Nesta segunda linha, nó struct * próximo.
Mas, em termos menos técnicos, o que é que a segunda linha
de código dentro das chaves?
Sim?
>> AUDIÊNCIA: [inaudível]
David J. MALAN: Um ponteiro para outro nó.
Então, na verdade, sintaxe um pouco enigmática.
Mas se você lê-lo, literalmente, em seguida é o nome de uma variável.
Qual é seu tipo de dados?
É um pouco prolixo, desta vez, mas é do tipo de nó struct *.
Qualquer vez que vimos algo estrela, que significa que é um ponteiro para esse tipo de dados.
Então, da próxima é, aparentemente, um ponteiro para um nó de struct.
>> Agora, o que é um nó struct?
Bem, observe que você vê aqueles mesmas palavras no canto superior direito.
E, de fato, você também verá a palavra "Nó" aqui em baixo no canto inferior esquerdo.
E isso é realmente apenas uma conveniência.
Observe que em nossa definição de estudante há a palavra "aluno" apenas uma vez.
E isso é porque um aluno objeto não era auto-referencial.
Não há nada dentro de um estudante que precisa apontar para um outro estudante,
persay.
Isso seria uma espécie de estranho no mundo real.
>> Mas, com um nó em uma ligada lista, nós queremos um nó
para ser referencial para um objeto semelhante.
E assim perceber a mudança aqui não é apenas o que está dentro das chaves.
Mas adicionar a palavra "nó" , na parte superior, bem como
adicionando-o ao fundo em vez de "aluno".
E este é apenas um detalhe técnico de modo a que, novamente, a sua estrutura de dados
pode ser auto-referencial, de modo que a nó pode apontar para um outro tal nó.
>> Então o que é isso, em última instância vai significar para nós?
Bem, um, este material dentro é o conteúdo do nosso nó.
Esta coisa aqui em cima, superior direito, é tão
que, mais uma vez, podemos nos referir a nós mesmos.
E então as coisas mais externa, embora nó é um novo termo
talvez, ainda o é mesmo como estudante e que
estava debaixo do capô em SPL.
>> Então, se nós agora queria começar implementação desta lista ligada,
como podemos traduzir algo como isto para codificar?
Bem, vamos ver uma exemplo de um programa que
na verdade, usa uma lista ligada.
Entre código de distribuição de hoje é um programa chamado Lista Zero.
E se eu executar este eu criei um super GUI simples, Interface gráfica do utilizador,
mas é realmente apenas printf.
E agora que eu me dei algumas cardápio opções-- DELETE, INSERT, Pesquisa,
e Traverse.
E Sair.
Estes são apenas operações comuns em um estrutura de dados conhecida como lista de link.
>> Agora, Excluir vai excluir um número da lista.
Inserir vai adicionar um número à lista.
Pesquisa vai olhar para o número da lista.
E travessia é apenas uma maneira elegante de dizer, percorrer a lista,
imprimi-lo, mas é isso.
Não alterá-lo de qualquer forma.
>> Então, vamos tentar isso.
Vamos em frente e digite 2.
E então eu vou inserir o número, dizem 9.
Enter.
E agora o meu programa é apenas programado para dizer lista é agora 9.
Agora, se eu ir em frente e que inserir novamente, vamos
me ir em frente e diminuir o zoom e digite 17.
Agora, a minha lista é 9, então com 17 anos.
Se eu fizer inserir novamente, vamos pular um.
Em vez de 22, de acordo com a imagem que tenho estado a olhar para aqui, deixe-me passar à frente
e inserir 26 próximo.
Então eu vou para digitar 26.
A lista é como eu esperava.
Mas agora, só para ver se esse código vai ser flexível, deixe-me agora
Tipo 22, o qual, pelo menos conceitualmente, se tivermos
Tendo isso resolvido, o que é de fato vai ser um outro objetivo, agora,
deve ir entre 17 e 26.
Então eu pressione Enter.
Na verdade, isso funciona.
E agora deixe-me inserir o passado, por a imagem, 34.
>> Tudo certo.
Então, por agora, deixe-me estipulam que Excluir e Traverse e Pesquisa fazer,
de fato, trabalhar.
Na verdade, se eu executar pesquisa, vamos procure o número 22, Enter.
Constatou-se 22.
Então é isso que este Programa Lista Zero faz.
>> Mas o que realmente está acontecendo em que implementa isso?
Bem, primeiro eu poderia ter, e de fato Eu tenho um arquivo chamado list0.h.
E em algum lugar existe essa line, typedef, nó struct,
então eu tenho as minhas chaves, int n, e então struct-- qual era a definição?
Nó struct seguinte.
Por isso, precisamos da estrela.
Agora, tecnicamente, entrar em o hábito de desenhar-lo aqui.
Você pode ver livros didáticos e referências on-line fazê-lo lá.
É funcionalmente equivalente.
Na verdade, isso é um pouco mais típico.
Mas eu vou ser coerente com o que fizemos da última vez e fazer isso.
E então, finalmente, eu vou fazer isso.
>> Assim, em um arquivo de cabeçalho em algum lugar, em list0.h
hoje é esta definição struct, e talvez algumas outras coisas.
Enquanto isso, na list0c há Vai ser algumas coisas.
Mas vamos apenas começar e não terminar isso.
List0.h é um arquivo que eu quero para incluir no meu arquivo C.
E então, em algum momento eu sou vai ter int, principal, anular.
E então eu vou tem algum de afazeres está aqui.
Eu também vou ter um protótipo, como vazio, busca, int,
n, cujo propósito na vida é para procurar um elemento.
E então aqui eu afirmo em código de hoje, vazio, busca, int, n,
nenhum ponto e vírgula, mas chaves abertas.
E agora eu quero procurar alguma forma para um elemento na lista.
Mas não temos o suficiente informação sobre a tela ainda.
Eu não tenho, na verdade, representava a própria lista.
Portanto, uma forma que pudéssemos implementar uma lista ligada de um programa
é que eu meio que quero fazer algo como declarar lista ligada aqui.
Para simplificar, eu vou fazer este global, mesmo que em geral nós
não deve fazer isso demais.
Mas vai simplificar este exemplo.
Então, eu quero declarar uma lista ligada aqui.
Agora, como eu poderia fazer isso?
>> Aqui está a foto de uma lista encadeada.
E eu realmente não saber no momento como
Eu estou indo para ir sobre a representação tantas coisas com apenas um
variável na memória.
Mas acho que volta um momento.
Todo esse tempo que tivemos cordas, que depois
revelou-se matrizes de caracteres, que depois
revelou ser apenas um ponteiro para o primeiro carácter
em um array de caracteres que tem um terminador nulo.
Então, por essa lógica, e com isso tipo de imagem de semear seus pensamentos,
Para que precisamos realmente escrever na nossa código para representar uma lista ligada?
Como muitas dessas informações que precisamos para capturar em código C, você diria?
Sim?
>> AUDIÊNCIA: Precisamos de um ponteiro para um nó.
DAVID J. MALAN: Um ponteiro para um nó.
Em particular, o que seria o seu nó instintos ser para manter um ponteiro para?
>> AUDIÊNCIAS: O primeiro nó.
>> DAVID J. MALAN: Sim, provavelmente apenas o primeiro.
E note, o primeiro nó é uma forma diferente.
É apenas a metade do tamanho da estrutura, porque é na verdade apenas um ponteiro.
Então, o que você pode realmente fazer é declarar uma lista ligada para ser do tipo nó *.
E vamos chamá-lo de primeira e inicialize-o como nulo.
Então, null, mais uma vez, está chegando em cena aqui.
Não só é nulo usado como como um especial valor de retorno para coisas como getString
e malloc, nulo é também o zero ponteiro, a falta de um ponteiro,
se você quiser.
Significa apenas que nada está ainda aqui.
Agora em primeiro lugar, eu poderia ter chamou isso de nada.
Eu poderia tê-lo chamado "lista" ou qualquer número de outras coisas.
Mas eu estou chamando-o de "primeiro" para que se alinha com esta imagem.
Assim como uma corda pode ser representado com o endereço do seu primeiro byte
pode assim uma lista ligada.
E vamos ver outros dados estruturas ser representado
com apenas um ponteiro, uma flecha de 32 bits, que aponta
o primeiro nó na estrutura.
>> Mas agora vamos antecipar um problema.
Se eu só estou lembrando no meu programa o endereço
do primeiro nó, o primeiro retângulo nesta estrutura de dados,
o melhor que seja o caso sobre a implementação do resto da minha lista?
O que é um detalhe chave que está acontecendo para garantir isso realmente funciona?
E por "realmente funciona" Eu Quer dizer, muito parecido com uma corda,
permite-nos ir a partir do primeiro caractere em nome do Davin para o segundo,
para o terceiro, o quarto, até o fim,
como sabemos quando estamos no final de uma lista encadeada que se parece com isso?
Quando é nulo.
E eu tenho representado este tipo de como como uma força engenheiro elétrico,
com o pouco de terra símbolo, das sortes.
Mas isso apenas significa nulo neste caso.
Você pode desenhar qualquer número de maneiras, mas o mesmo autor
passou a utilizar este símbolo aqui.
>> Enquanto nós estamos amarrando todos estes nodos juntos,
só lembrando que a primeira é, desde
como colocar um símbolo especial no o último nó na lista,
e usaremos nulo, porque isso é o que temos à nossa disposição,
esta lista está completa.
E mesmo se eu apenas dar-lhe um ponteiro para o primeiro elemento, que, o programador,
certamente pode acessar o resto.
Mas vamos deixar suas mentes vagar um pouco,
se eles não estão já bastante wandered-- o que é
vai ser o tempo de execução encontrar alguma coisa nessa lista?
Porra, é grande O de n, que não é ruim, na justiça.
Mas é linear.
Temos dado o recurso de matrizes movendo mais
para esse quadro de forma dinâmica entrelaçados ou nós ligados?
Nós desistimos de acesso aleatório.
Uma matriz é bom porque matematicamente tudo
está de volta para fazer a volta para trás.
Mesmo que esta imagem parece muito, e mesmo
mas parece que esses nós são bem espaçados entre si, na realidade
eles poderiam estar em qualquer lugar.
OX 1, Ox50, Ox123, Ox99, estes nós poderia estar em qualquer lugar.
Porque malloc aloca memória da pilha, mas em qualquer lugar do heap.
Você não necessariamente sabe que é vai ser back to back to back.
E assim esta imagem em realidade não vai ser muito esta bonita.
>> Então, ele vai levar um pouco de trabalhar para implementar essa função.
Então, vamos implementar a pesquisa agora.
E nós vamos ver uma espécie de maneira inteligente de fazer isso.
Então, se eu sou uma função de pesquisa e Eu sou dado uma variável, inteiro n
procurar, eu preciso saber o nova sintaxe para olhar para dentro
de uma estrutura que está apontou, para encontrar n.
Então, vamos fazer isso.
>> Então, primeiro eu vou frente e declarar um nó *.
E eu vou chamá-lo ponteiro, apenas por convenção.
E eu estou indo para inicializar a primeira.
E agora eu posso fazer isso em um número de maneiras.
Mas eu vou ter uma abordagem comum.
Enquanto apontador não é igual null, e isso é válido sintaxe.
E isso significa apenas fazer o seguinte, de modo Contanto que você não está apontando para o nada.
O que eu quero fazer?
>> Se ponteiro ponto n, deixe-me voltar para que, equals-- iguala o quê?
Qual o valor que eu estou procurando?
O n real que foi passado.
Então aqui está uma outra característica de C e muitas línguas.
Embora a estrutura chamada nó tem um valor de n, totalmente legítimo
também ter um argumento locais ou variável chamada n.
Porque mesmo que, com Os olhos humanos, pode-se distinguir
que esta n é presumivelmente diferente deste n.
Porque a sintaxe é diferente.
Você tem um ponto e um ponteiro, enquanto este não tem tal coisa.
Então, isso é OK.
Isso é OK para chamar-lhes as mesmas coisas.
>> Se eu não encontrar isso, eu sou vai querer fazer alguma coisa
como anunciar que encontramos n.
E nós vamos deixar isso como um comentar ou código de pseudocódigo.
Outra coisa, e aqui está o parte interessante, o que
eu gostaria de fazer se o nó atual não se contendo n que eu me importo com?
Como faço para conseguir o seguinte?
Se o meu dedo no momento é PTR, e é
apontando para o que quer que primeiro está apontando,
Como faço para mover meu dedo para o nó seguinte código?
Bem, qual é a trilha que estamos vai seguir neste caso?
AUDIÊNCIA: [inaudível].
DAVID J. MALAN: Sim, por isso a seguir.
Então, se eu voltar para o meu código aqui, na verdade, eu sou
indo para ir em frente e dizer ponteiro, que é apenas um variable-- temporária é
um nome estranho, ptr, mas é como temp--
Vou configurar o ponteiro igual a qualquer ponteiro é--
e mais uma vez, isso vai ser um buggy pouco para um ponto moment-- seguinte.
Em outras palavras, eu vou tomar o meu dedo que está apontando para este nó
aqui e eu vou dizer, você sabe o que, dê uma olhada no próximo campo
e mover o dedo para seja o que está apontando.
E isso vai repetir, repetir, repetir.
Mas quando o meu dedo deixar de fazer alguma coisa?
Tão logo que linha de código em chutes?
AUDIÊNCIA: [inaudível]
DAVID J. MALAN: Se o ponto enquanto ponteiro não é igual a null.
Em algum momento o meu dedo do vai estar apontando para nulo
e eu estou indo para perceber isso é o fim da lista.
Agora, este é um pouco mentirinha para simplificar.
Acontece que, embora acabou de aprender esta notação de ponto
para estruturas, o ponteiro não é um struct.
ptr é o quê?
Apenas para ser mais detalhista.
É um ponteiro para um nó.
Não é um nó em si.
Se eu não tinha nenhuma estrela aqui, ponteiro absolutely-- é um nó.
Isto é como uma semana declaração de uma variável,
embora a palavra "nó" é novo.
>> Mas assim que introduzir um estrela, agora é um ponteiro para um nó.
E, infelizmente, você não pode usar a notação de ponto para um ponteiro.
Você tem que usar a seta notação, o que, surpreendentemente,
é a primeira vez que um pedaço de sintaxe parece intuitiva.
Isso literalmente parece uma flecha.
E isso é uma coisa boa.
E aqui embaixo, literalmente parece uma flecha.
Então, eu acho que é a la-- eu não acho que estou over-cometer aqui-- I
acho que é a última peça nova de sintaxe, vamos ver.
E, felizmente, é de fato um pouco mais intuitivo.
>> Agora, para aqueles de vocês que pode preferir a velha forma,
Você ainda pode usar a notação de ponto.
Mas como por segunda-feira de conversa, primeiro
precisa ir lá, ir para esse abordar, em seguida, acessar o campo.
Então, isso também é correto.
E, francamente, este é um pouco mais pedante.
Você está literalmente dizendo, desreferenciava o ponteiro e ir para lá.
Em seguida, pegue .n, o campo chamado n.
Mas, francamente, ninguém quer para escrever ou ler isto.
E assim o mundo inventado a notação de seta, que
é equivalente, idêntica, é apenas um açúcar sintático.
Assim, uma maneira elegante de dizer isso parece melhor, ou parece mais simples.
>> Então, agora eu vou fazer outra coisa.
Eu vou dizer "quebrar" uma vez que eu achei tão eu não continuar olhando para ele.
Mas esta é a essência de uma função de pesquisa.
Mas é muito mais fácil, no final, não andar através do código.
Este é de facto a implementação formal de pesquisa em código de distribuição de hoje.
Ouso dizer que inserir não é particularmente diversão a pé
visualmente, nem apagar, mesmo no entanto, no final do dia
eles se resumem a bastante heurísticas simples.
>> Então, vamos fazer isso.
Se você vai humor me aqui, eu fiz trazer um monte de bolas de stress.
Eu trouxe um monte de números.
E poderíamos obter apenas alguns voluntários para representar a 9, 17, 20, 22, 29, e 34?
Então, basicamente todos quem está aqui hoje.
Isso foi um, dois, três, quatro, cinco, seis pessoas.
E eu fui convidado a vai-- ver, não uma na parte de trás levanta as mãos.
OK, um, dois, três, quatro, cinco-- deixe-me carregar balance-- seis.
OK, você seis suba.
Vamos precisar de outras pessoas.
Trouxemos stress bolas extras.
E se você poderia, por apenas um momento, a linha
-vos apenas como esta foto aqui.
>> Tudo certo.
Vamos ver, qual é o seu nome?
>> AUDIÊNCIA: Andrew.
>> DAVID J. MALAN: Andrew, você é o número 9.
Prazer em conhecê-lo.
Aqui você vai.
AUDIÊNCIA: Jen.
DAVID J. MALAN: Jen.
David.
Número 17.
Sim?
>> AUDIÊNCIA: Eu sou Julia.
>> DAVID J. MALAN: Julia, David.
Número 20.
AUDIÊNCIA: Christian.
DAVID J. MALAN: Christian, David.
Número 22.
E?
>> AUDIÊNCIA: JP.
DAVID J. MALAN: JP.
Número 29.
Então vá em frente e obter em-- Uh oh.
Uh oh.
Espera.
20.
Alguém tem um marcador?
AUDIÊNCIA: Eu tenho uma Sharpie.
DAVID J. MALAN: Você tem um Sharpie?
Está bem.
E alguém tem um pedaço de papel?
Salve a palestra.
Venha.
AUDIÊNCIA: Nós temos isso.
DAVID J. MALAN: Temos isso?
Tudo bem, obrigado.
Aqui vamos nós.
Foi isso de você?
Você acabou de salvar o dia.
Então, 29.
Tudo certo.
Eu mal escrito 29, mas OK.
Continue.
Tudo bem, eu vou te dar a caneta de volta momentaneamente.
Então, temos essas pessoas aqui.
Vamos ter um outro.
Gabe, você quer jogar o primeiro elemento aqui?
Vamos precisar de você para apontar a essas pessoas finas.
Então, 9, 17, 20, 22, espécie de 29, e depois 34.
Será que vamos perder alguém?
Eu tenho um 34.
Onde fez-- OK, quem quer ser 34?
OK, vamos lá para cima, 34.
Tudo bem, este será valeu a pena o clímax.
Qual o seu nome?
>> AUDIÊNCIA: Peter.
>> DAVID J. MALAN: Peter, vamos lá para cima.
Tudo bem, então aqui está um grupo inteiro de nós.
Cada um de vocês representa um desses retângulos.
E Gabe, a um pouco estranho homem para fora, representa o primeiro.
Assim, seu ponteiro é um pouco menor na tela do que todos os outros.
E, neste caso, cada um sua esquerda mãos vai ou apontar para baixo,
representando, assim, nulo, de modo apenas na ausência de um ponteiro,
ou ele vai estar apontando em um nó ao lado de você.
>> Então, agora, se você enfeitar vós semelhantes a imagem
aqui, vá em frente e ponto um para o outro, com Gabe
em particular, que aponta no o número 9 para representar a lista.
OK, eo número 34, sua mão esquerda deve apenas estar apontando para o chão.
>> OK, então esta é a lista encadeada.
Portanto, este é o cenário em questão.
E, de fato, este é representante de uma classe de problemas
que você pode tentar resolver com o código.
Você deseja inserir em última instância um novo elemento na lista.
Neste caso, vamos tente inserir o número 55.
Mas não vai ser casos diferentes a considerar.
E, de fato, este vai ser um do grande-retrato takeaways aqui, é,
quais são os diferentes casos.
Quais são os diferentes se as condições ou ramos que o programa possa ter?
>> Bem, o número que você está tentando inserção, que sabemos agora para ser 55,
mas se você não sabia com antecedência, eu diria
cai, pelo menos, três situações possíveis.
Onde pode um elemento novo ser?
AUDIÊNCIA: E o fim ou meio.
David J. MALAN: No final, em no meio, ou no início.
Então, eu afirmo que há pelo menos três problemas que precisamos resolver.
Vamos escolher o que é, talvez, sem dúvida o mais simples
um, em que o novo elemento pertence no início.
Então, eu vou ter bastante código como pesquisar, o que eu acabei de escrever.
E eu vou ter ptr, que Eu vou representar aqui com o meu dedo,
como de costume.
>> E lembre-se, o valor fizemos inicializar ptr para?
Por isso, ele inicializado como nulo inicialmente.
Mas então o que nós fizemos, uma vez que estavam dentro da nossa função de pesquisa?
Nós configurá-lo igual ao primeiro, o que não significa fazer isso.
Se eu definir ptr igual ao primeiro, o que deve ser realmente a minha mão apontando?
Certo.
Então, se Gabe e eu vamos ser valores iguais aqui,
precisamos tanto do ponto no número 9.
>> Portanto, este foi o início de nossa história.
E agora este é apenas simples, mesmo que a sintaxe é novo.
Conceitualmente, esta é apenas a pesquisa linear.
É 55 igual a 9?
Ou melhor, vamos dizer menos do que 9.
Porque eu estou tentando descobrir onde colocar 55.
Menos de 9, menos de 17, menos de 20, menos de 22, menos de 29,
menos do que 34, n.
Portanto, agora estamos em caso um de pelo menos três.
>> Se eu quiser inserir 55 para cá, o que linhas de código necessidade de ter executado?
Como é que esse quadro de os seres humanos precisam mudar?
O que eu faço com a mão esquerda?
Isto deve ser inicialmente nula, porque eu estou no fim da lista.
E o que deve acontecer aqui com Peter, foi?
Ele está, obviamente, vai apontar para mim.
Então, eu afirmo que há pelo menos duas linhas de código no código de exemplo a partir de hoje
que vai implementar este cenário de adição de 55 na cauda.
E eu poderia ter alguém hop e representam apenas 55?
Tudo bem, você é o novo 55.
>> Então, agora que se o próximo cenário vem junto,
e queremos inserir no início ou a cabeça de lista?
E qual é o seu nome, o número 55?
>> AUDIÊNCIA: Jack.
>> DAVID J. MALAN: Jack?
OK, prazer em conhecê-lo.
Bem-vindo a bordo.
Então agora nós vamos inserir, por exemplo, o número 5.
Este é o segundo caso do três nós viemos com antes.
Assim, se pertence 5 no início, vamos ver como podemos descobrir isso.
Eu inicializar o meu ptr ponteiro para o 9 novamente.
E eu percebi, oh, 5 é inferior a 9.
Então corrigir esta imagem para nós.
Cujas mãos, Gabe ou David de ou-- qual é o nome do número 9?
>> AUDIÊNCIA: Jen.
>> DAVID J. MALAN: hands-- de Jen que de nossas mãos precisa mudar?
OK, então Gabe aponta para o que agora?
Para mim.
Eu sou o novo nó.
Então eu vou tipo de movimento aqui para vê-lo visualmente.
E enquanto isso o que eu apontar isso?
Ainda assim, onde eu estou apontando.
Então é isso.
Então, só realmente uma linha de correções de código esta questão em particular, ao que parece.
Tudo bem, então isso é bom.
E alguém pode ser um marcador para 5?
Vamos lá para cima.
Nós vamos tirar você da próxima vez.
>> Tudo bem, então agora-- e Como um aparte, os nomes
Eu não estou fazendo menção explícita de direito agora, ponteiro pred, ponteiro antecessor
e novo ponteiro, que é apenas os nomes dado
no código de exemplo para os ponteiros ou minhas mãos que é tipo de apontar ao redor.
Qual o seu nome?
>> AUDIÊNCIA: Christine.
>> DAVID J. MALAN: Christine.
Bem-vindo a bordo.
Tudo bem, então vamos considerar agora um cenário um pouco mais chato,
pelo qual eu quero inserir algo como 26 para isso.
20?
O quê?
Estes é-- coisa boa que temos esta caneta.
Tudo bem, 20.
Se alguém pudesse ter outra peça de papel pronto, apenas em caso-- tudo bem.
Oh, interessante.
Bem, este é um exemplo de um bug palestra.
OK então, qual é o seu nome?
AUDIÊNCIA: Julia.
DAVID J. MALAN: Julia, você pode pop para fora e fingir que nunca foram lá?
OK, isso nunca aconteceu.
Obrigado.
Então, suponha que queremos inserir Julia para esta lista ligada.
Ela é o número 20.
E, claro, ela é vai pertencer ao
begin-- não apontam para nada ainda.
Então sua mão pode ser tipo de baixo valor nulo ou algum lixo.
Vamos contar a história rápida.
Eu estou apontando para o número 5 desta vez.
Então eu verifico 9.
Então eu verifico 17.
Então eu verifico 22.
E eu percebo, ooh, Julia precisa ir antes de 22.
Então, o que precisa acontecer?
Cujas mãos precisa mudar?
Julia, minha, ou-- Qual é o seu nome?
>> AUDIÊNCIA: Christian.
>> DAVID J. MALAN: Christian ou?
>> AUDIÊNCIA: Andy.
>> DAVID J. MALAN: Andy.
Christian ou Andy?
Andy precisa apontar?
Julia.
Tudo certo.
Então, Andy, você quer apontar para Julia?
Mas espere um minuto.
Na história, até agora, Eu sou o tipo de uma
em carga, no sentido de que ponteiro é a coisa que é
movendo-se através da lista.
Podemos ter um nome para Andy, mas não há nenhuma variável chamada Andy.
A única outra variável que temos é primeiro, que está representado por Gabe.
>> Portanto, este é, na verdade, porque assim agora não tenho necessidade disso.
Mas agora na tela existe falar novamente do ponteiro pred.
Então deixe-me ser mais explícita.
Se esta é ponteiro, eu tinha melhor ficar um pouco mais inteligente
sobre minha iteração.
Se você não se importa de passar por aqui novamente, que aponta aqui, que aponta aqui.
Mas deixe-me ter um ponteiro pred, ponteiro antecessor, que é
tipo de apontar para o elemento que eu estava apenas no.
Então, quando eu ir para lá, agora minha esquerda atualizações manuais.
Quando vou aqui minhas atualizações mão esquerda.
E agora eu tenho não só um ponteiro para o elemento que vai atrás de Julia,
Eu ainda tenho um ponteiro para Andy, o elemento antes.
Então, você tem acesso, essencialmente, farinha de rosca, se quiser,
para todas as indicações necessárias.
>> Então, se eu estou apontando para Andy e eu também estou apontando
na cristã, cujas mãos agora deve ser apontado em outro lugar?
Então Andy agora pode apontar para Julia.
Julia agora pode apontar para Christian.
Porque ela pode copiar a minha ponteiro do lado direito.
E que efetivamente coloca você de volta a este lugar aqui.
Assim, em breve, mesmo que isso está nos levando espécie de sempre
realmente atualizar um lista ligada, perceber
que as operações são relativamente simples.
É de um, dois, três linhas de código no final.
Mas envolto em torno daqueles linhas de código presumivelmente
é um pouco de lógica que efetivamente faz a pergunta: onde estamos?
Estamos no início, no meio, ou o fim?
>> Agora, certamente há alguma outra operações que possam implementar.
E essas fotos aqui apenas retratam o que nós fizemos com os seres humanos.
E quanto a remoção?
Se eu quiser, por exemplo, remover o número 34 ou 55,
Eu poderia ter o mesmo tipo de código, mas eu vou precisar de um ou dois passos.
Porque o que há de novo?
Se eu remover alguém no final, como número 55 e depois 34,
o que também tem de mudar como eu faço isso?
Eu tenho que não evict-- Qual é o seu nome?
>> AUDIÊNCIA: Jack.
>> DAVID J. MALAN: Jack.
Eu tenho não só evict-- livre Jack, tão literalmente ligar gratuitamente Jack, ou pelo menos
o ponteiro lá também, mas agora o que precisa mudar com Peter?
Sua mão melhor começar a apontar para baixo.
Porque assim que eu chamo livre em Jack, se de Pedro ainda apontando para Jack
e, portanto, eu continuo percorrendo a lista e acesso este ponteiro,
que é quando o nosso velho amigo segmentação falha pode realmente chutar.
Porque nós temos dado o memória de volta para Jack.
>> Você pode ficar lá desajeitadamente por apenas um momento.
Porque nós temos apenas um par operações finais a considerar.
Removendo o cabeça de lista, ou o beginning-- e este do
um pouco chato.
Porque nós temos que saber que Gabe é uma espécie de especial neste programa.
Porque, na verdade, ele tem seu próprio ponteiro.
Ele não está apenas a ser apontada para, como é quase todo mundo aqui.
>> Assim, quando a cabeça da lista é removida, cujas mãos precisa mudar agora?
Qual é o seu nome?
>> AUDIÊNCIA: Christine.
>> DAVID J. MALAN: Eu sou terrível em nomes, aparentemente.
Então Christine e Gabe, cujas mãos precisa mudar
quando tentamos remover Christine, número 5, a partir da imagem?
OK, então vamos fazer Gabe.
Gabe vai apontar, presumivelmente, no número 9.
Mas o que deve acontecer no próximo?
AUDIÊNCIA: Christine deveria ser nulo [inaudível].
DAVID J. MALAN: OK, nós devemos provavelmente make-- eu ouvi "nulo" em algum lugar.
AUDIÊNCIA: Null e libertá-la.
DAVID J. MALAN: null o que?
AUDIÊNCIA: Null e libertá-la.
DAVID J. MALAN: Null e libertá-la.
Então isso é muito fácil.
E é perfeito que você agora é espécie de pé, não pertencer.
Porque você foi dissociado da lista.
Você tem sido eficaz órfãos a partir da lista.
E assim seria melhor ligar gratuitamente agora Christine dar essa memória de volta.
Caso contrário, cada vez que apagar um nó da lista
fôssemos fazer a lista mais curto, mas não realmente a diminuir
o tamanho da memória.
E assim se continuar a acrescentar e acrescentando, acrescentando coisas para a lista,
meu computador pode ficar mais lento e mais lento e mais lento,
porque eu estou ficando sem memória, mesmo que eu não sou realmente
usando bytes de Christine de memória mais.
>> Então, no final, há outra cenários, de remoção course--
no meio, a remoção no final, como vimos.
Mas o mais interessante desafio agora é
vai ser a considerar exatamente que o tempo de execução é.
Assim, não só você pode manter sua pedaços de papel, se, Gabe,
você não se importaria de dar todos uma bola anti-stress.
Muito obrigado à nossa lista ligada de voluntários aqui, se pudesse.
>> [Aplausos]
>> DAVID J. MALAN: Tudo bem.
Assim, um par de analítica perguntas, então, se eu pudesse.
Nós já vimos isso antes de notação, O grande e omega, limites superiores
e limites mais baixos no tempo de funcionamento de um algoritmo.
Então, vamos considerar apenas um par de perguntas.
>> Um deles, e nós dissemos que antes, o que é o funcionamento
tempo de busca por um lista em termos de grande O?
O que é um limite superior sobre o funcionamento tempo de busca de uma lista ligada
como implementado pelos nossos voluntários aqui?
É grande O de n, linear.
Porque, na pior das hipóteses, o elemento, como 55,
que pode estar procurando pode ser onde Jack era, todo o caminho no final.
E, infelizmente, ao contrário de um array não podemos começar a fantasia neste momento.
Apesar de todos os nossos seres humanos eram classificadas a partir de pequenos elementos, 5,
todo o caminho até o elemento de maior, 55, que geralmente é uma coisa boa.
Mas o que faz essa suposição já não nos permitem fazer?
AUDIÊNCIA: [inaudível]
DAVID J. MALAN: Diga de novo?
AUDIÊNCIA: acesso aleatório.
DAVID J. MALAN: acesso aleatório.
E por sua vez, isso significa que não podemos mais usar zeros fraco, intuição,
e evidência de utilização de binário pesquisar e dividir e conquistar.
Porque, embora nós os seres humanos poderiam, obviamente,
ver que Andy ou Christian foram mais ou menos no meio da lista,
só sabemos que como um computador por desnatação à lista
desde o início.
Então, nós temos que desistiu de acesso aleatório.
>> Tão grande O de n agora é o superior obrigado em nosso tempo de busca.
E sobre ômega de nossa busca?
Qual é o limite inferior na busca para algum número nesta lista?
AUDIÊNCIA: [inaudível]
DAVID J. MALAN: Diga de novo?
AUDIÊNCIA: One.
DAVID J. MALAN: One.
Tempo tão constante.
No melhor dos casos, é Christine de facto, no início da lista.
E nós estamos procurando número 5, de modo que a encontrou.
Portanto, não é grande coisa.
Mas ela tem que estar no início da lista, neste caso.
Que tal algo como excluir?
E se você quiser excluir um elemento?
Qual é o limite superior e limite inferior sobre a eliminação de algo a partir de um ligado
lista?
AUDIÊNCIA: [inaudível]
DAVID J. MALAN: Diga de novo?
AUDIÊNCIA: n.
David J. MALAN: n é na verdade, o limite superior.
Porque, no pior caso tentamos excluir Jack, como acabamos de fazer.
Ele é todo o caminho no final.
Leva-nos para sempre, ou n passos para encontrá-lo.
Então, isso é um limite superior.
Isso é linear, com certeza.
E o melhor caso de tempo de execução, ou os limites inferiores na melhor das hipóteses
haveria tempo constante.
Porque talvez a gente tente apagar Christine, e nós apenas ter sorte
ela está no começo.
Agora, espere um minuto.
Gabe também estava no início, e nós também tivemos que atualizar Gabe.
Para que não foi apenas um passo.
Então é isso, já constante tempo, no melhor dos casos,
para remover o elemento mais pequeno?
É, ainda que possa ser de dois, três, ou até 100 linhas de código,
se é o mesmo número de linhas, não em algum loop,
e independente do tamanho da lista, com certeza.
Excluindo o elemento no o início da lista,
mesmo que tenhamos de lidar com Gabe, ainda é tempo constante.
>> Portanto, este parece ser um enorme passo para trás.
E o que é um desperdício de tempo Se, em uma semana e na semana
zero, tivemos não só código pseudocódigo mas o código real
para implementar algo que é log base de n, ou registro, em vez disso, de n, base 2,
em termos de seu tempo de execução.
Então, por que diabos seria queremos começar usando algo como uma lista ligada?
Sim.
>> AUDIÊNCIA: Então, você pode adicionar elementos para a matriz.
DAVID J. MALAN: Então você pode adicionar elementos à matriz.
E isso também é temática.
E vamos continuar a ver este, este trade-off, muito
como já vimos um trade-off com merge sort.
Nós realmente poderia acelerar pesquisar ou classificar, em vez disso,
se passar um pouco mais de espaço e tem um pedaço de uma memória adicional
ou uma matriz para merge sort.
Mas nós gastamos mais espaço, mas economizar tempo.
Neste caso, estamos dando-se tempo, mas estamos
ganhando flexibilidade, dinamismo, se quiserem,
que é sem dúvida uma característica positiva.
>> Nós também estamos gastando espaço.
Em que sentido é um ligado listar mais caro
em termos de espaço de uma matriz?
Onde está o espaço extra vem?
Sim?
>> AUDIÊNCIA: ponteiro [inaudível].
>> DAVID J. MALAN: Sim, nós também tem o ponteiro.
Então, isso é chato minorly em que não sou mais
Eu armazenar apenas um int representar um int.
Eu sou armazenar um int e um apontador, que é também de 32 bits.
Então, eu estou literalmente dobrando a quantidade de espaço envolvido.
Então isso é um trade-off, mas que é, no caso de int.
Suponha que você não está armazenando int, mas suponho que cada um desses retângulos
ou cada um desses seres humanos estava representando uma palavra, uma palavra em Inglês que
pode ser de cinco caracteres, 10 caracteres, talvez até mais.
Em seguida, adicionando apenas 32 mais bits pode ser menos de um grande negócio.
>> O que se cada um dos estudantes na manifestação
foram literalmente estruturas estudantis que têm nomes e casas e talvez
números de telefone e Twitter lida e semelhantes.
Assim, todos os campos que começamos falando no outro dia,
muito menos de um grande negócio, nossos nós ficam mais interessantes
e grande para gastar, eh, um adicional ponteiro só para conectá-los.
Mas, na verdade, é um trade-off.
E, de fato, o código é mais complexa, como você vai
ver ao percorre que o exemplo particular.
Mas o que se havia algum santo graal aqui.
E se nós não dar um passo para trás, mas um grande passo para a frente
e implementar um conjunto de dados estrutura através do qual se
pode encontrar elementos como Jack ou Christine ou quaisquer outros elementos
nessa matriz em verdadeiro tempo constante?
A busca é constante.
Excluir é constante.
Insert é constante.
Todas estas operações são constantes.
Isso seria o nosso santo graal.
E é aí que nós vai pegar na próxima vez.
Vejo vocês depois.