[Powered by Google Translate] Na programação, muitas vezes precisamos representar listas de valores,
como os nomes dos alunos em uma seção
ou os seus resultados no último teste.
>> Na linguagem C, declarado matrizes podem ser utilizadas
para armazenar listas.
É fácil enumerar os elementos de uma lista
armazenados em uma matriz, e se você precisa acessar
ou modificar o elemento da lista om
por algum índice arbitrário I,
que pode ser feito em tempo constante,
mas as matrizes apresentam desvantagens, também.
>> Quando nós declará-los, somos obrigados a dizer
na frente como eles são grandes,
isto é, quantos elementos que podem armazenar
e qual o tamanho destes elementos são, que é determinada pelo tipo.
Por exemplo, int arr (10)
pode armazenar 10 itens
que são do tamanho de um int.
>> Nós não podemos mudar o tamanho de uma matriz após a declaração.
Nós temos que fazer uma nova matriz se deseja armazenar mais elementos.
A razão dessa limitação existe é que o nosso
programa armazena todo o conjunto
como um pedaço contíguo de memória.
Dizer que este é o buffer onde se armazenados em nossa matriz.
Pode haver outras variáveis
localizado ao lado da matriz
na memória, por isso não podemos
apenas fazer a matriz maior.
>> Às vezes, nós gostaríamos de trocar de velocidade a matriz de acesso rápido de dados
para um pouco mais de flexibilidade.
Digite a lista ligada, uma outra estrutura de dados básica
você não pode ser tão familiarizado.
A um nível elevado,
uma lista ligada armazena os dados numa sequência de nodos
que estão ligados uns aos outros com links,
portanto, "lista ligada." o nome
Como veremos, esta diferença no projeto
conduz a diferentes vantagens e desvantagens
de uma matriz.
>> Aqui está um código C para uma lista muito simples ligada de inteiros.
Você pode ver que temos representado cada nó
na lista como uma estrutura que contém duas coisas,
um inteiro para armazenar chamado 'Val'
e um link para o próximo nó na lista
que representamos como um ponteiro chamado 'próximo'.
Dessa forma, é possível acompanhar toda a lista
com apenas um único ponteiro para o nó 1,
e então podemos seguir os ponteiros próximos
para o nó 2,
para o nó 3,
ao nó 4,
e assim por diante, até chegar ao fim da lista.
>> Você pode ser capaz de ver uma vantagem isso tem
sobre a estrutura de array estático - com uma lista ligada,
não precisamos de um grande pedaço de memória completamente.
O nó 1 da lista poderia viver neste lugar na memória,
eo nó 2 poderia ser todo o caminho até aqui.
Podemos chegar a todos os nós, não importa onde eles estão na memória,
porque a partir do nó 1, o ponteiro próximo de cada nó
nos diz exatamente onde ir.
>> Além disso, não temos que dizer na frente
como uma grande lista encadeada será a nossa forma de fazer com arrays estáticos,
uma vez que podemos continuar a adicionar nós a uma lista
enquanto não há espaço em algum lugar na memória para novos nós.
Portanto, listas ligadas são fáceis de redimensionar dinamicamente.
Dizer, mais tarde no programa, precisamos adicionar mais nós
em nossa lista.
Para inserir um novo nó em nossa lista em tempo real,
tudo o que temos a fazer é alocar a memória para esse nó,
plop no valor de dados,
e depois colocá-lo onde quiser, ajustando os ponteiros apropriados.
>> Por exemplo, se quiséssemos colocar um nó no meio
os nós 2 e 3 da lista,
não teríamos para mover os nós 2 ou 3 em tudo.
Dizer que estamos inserindo este nó vermelho.
Tudo que temos a fazer é definir ponteiro próximo do novo nó de
para apontar para o nó 3
e, em seguida, religar ponteiro próximo nó 2 do
para apontar para o novo nó.
Assim, podemos redimensionar nossas listas na mosca
desde o nosso computador não dependem de indexação,
mas sim na ligação entre o uso de ponteiros para armazená-los.
>> Listas No entanto, uma desvantagem do ligadas
é que, ao contrário de uma matriz estática,
o computador não pode simplesmente pular para o meio da lista.
Desde que o computador tem que visitar cada nó na lista ligada
para chegar ao próximo,
que vai levar mais tempo para encontrar um nó específico
do que seria em um array.
Para percorrer a lista inteira leva um tempo proporcional
para o comprimento da lista,
ou O (n) em notação assintótica.
Em média, atingindo qualquer nó
também leva um tempo proporcional a n.
>> Agora, vamos realmente escrever um código
que trabalha com listas ligadas.
Vamos dizer que queremos uma lista ligada de inteiros.
Podemos representar um nó na nossa lista novamente
como uma estrutura com dois campos,
um valor inteiro chamado 'Val'
e um ponteiro próximo para o próximo nó da lista.
Bem, parece bastante simples.
>> Vamos dizer que queremos escrever uma função
que percorre a lista e imprime o
valor armazenado no último nó da lista.
Bem, isso significa que teremos que percorrer todos os nós da lista
para encontrar a última, mas desde que não está adicionando
ou apagar nada, não queremos mudar
a estrutura interna dos ponteiros seguintes na lista.
>> Então, vamos precisar de um ponteiro especificamente para passagem
que chamaremos de "rastreador".
Vai rastejar através de todos os elementos da lista
seguindo a cadeia de ponteiros próximos.
Tudo o que temos armazenado é um ponteiro para o nó 1,
ou "cabeça" da lista.
Pontos de cabeça para o nó 1.
É o tipo de ponteiro a nó.
>> Para obter o nó 1 real na lista,
temos que dereference esse ponteiro,
mas antes que possamos cancelar a referência de que, é preciso verificar
se o ponteiro é nulo primeiro.
Se for nulo, a lista está vazia,
e devemos imprimir uma mensagem que, porque a lista é vazia,
não há último nó.
Mas, vamos dizer que a lista não é vazia.
Se não é, então devemos rastrear toda a lista
até chegarmos ao último nó da lista,
e como podemos saber se nós estamos olhando para o último nó na lista?
>> Bem, se ponteiro próxima de um nó é nulo,
sabemos que estamos no final
desde o último ponteiro seguinte teria nenhum nó seguinte na lista para apontar.
É uma boa prática para manter sempre ponteiro próximo do nó passado inicializado como nulo
ter uma propriedade padronizada que nos alerta quando chegamos ao fim da lista.
>> Então, se rastreador → seguinte é nulo,
lembre-se que a sintaxe flecha é um atalho para dereferencing
um ponteiro para uma estrutura, em seguida, acessar
seu próximo campo equivalente ao incómodo:
(* Rastreador). Seguinte.
Uma vez que tenhamos encontrado o último nó,
queremos imprimir rastreador → val,
o valor do nó actual
que sabemos que é a última.
Caso contrário, se nós não estamos ainda no último nó na lista,
temos que seguir em frente para o próximo nó na lista
e verificar se esse é o último.
Para fazer isso, basta fazer o nosso ponteiro rastreador
para apontar para o próximo valor do nó atual,
isto é, o nó seguinte na lista.
Isto é feito ajustando
rastreador = rastreador → seguinte.
Em seguida, repetimos este processo, com um laço, por exemplo,
até encontrar o último nó.
Assim, por exemplo, se rastreador estava apontando para a cabeça,
vamos definir rastreador para apontar para rastreador → seguinte,
que é o mesmo que o próximo campo do nó 1.
Então, agora o nosso rastreador está apontando para o nó 2,
e, de novo, repetir este com um ciclo,
até que tenhamos encontrado o último nó, isto é,
onde ponteiro próximo do nó está a apontar para null.
E aí temos que,
nós encontramos o último nó na lista, e para imprimir o seu valor,
é só usar rastreador → val.
>> O deslocamento não é tão ruim, mas o que sobre a inserção?
Vamos dizer que nós queremos inserir um inteiro na posição 4
em uma lista de inteiros.
Que se encontra entre os nós de corrente 3 e 4.
Mais uma vez, temos que percorrer a lista apenas para
chegar ao elemento terceiro, aquele que está inserindo depois.
Então, criamos um ponteiro rastreador novamente para percorrer a lista,
verificar se o nosso ponteiro cabeça é nulo,
e se não é, aponta nosso ponteiro rastreador no nó de cabeça.
Então, estamos no primeiro elemento.
Nós temos que ir para a frente dois elementos mais antes que possamos inserir,
por isso podemos usar um loop
int i = 1; i <3, i + +
e em cada iteração do loop,
avançar nosso ponteiro rastreador frente por um nó
verificando se o campo próximo do nó atual é nulo,
e se não é, mover nosso ponteiro rastreador para o próximo nó
definindo-o igual ao ponteiro próximo do nó atual.
Assim, desde que o nosso circuito para fazer isso, diz
duas vezes,
chegamos ao nó 3,
e uma vez que nosso ponteiro rastreador atingiu o nó após
que queremos inserir o nosso inteiro novo,
como é que nós realmente a inserção?
>> Bem, o nosso novo inteiro tem de ser inserida na lista
como parte de sua estrutura próprio nó,
uma vez que esta é realmente uma seqüência de nós.
Então, vamos fazer um novo ponteiro para o nó
chamado "new_node '
e configurá-lo para apontar para a memória que agora alocar
sobre a pilha para o próprio nó,
ea quantidade de memória que precisamos alocar?
Assim, o tamanho de um nó,
e queremos definir seu campo val para o número inteiro que deseja inserir.
Vamos dizer, 6.
Agora, o nó contém o nosso valor inteiro.
É também uma boa prática para inicializar próximo campo o novo nó de
para apontar para null,
mas e agora?
>> Temos que mudar a estrutura interna da lista
e os ponteiros próximos contida existente da lista
Nós 3 e 4.
Uma vez que os ponteiros próximos determinar a ordem da lista,
E já que estamos inserindo nosso novo nó
para a direita no meio da lista,
pode ser um pouco complicado.
Isto porque, lembre-se, o nosso computador
só sabe a localização de nós na lista
por causa dos ponteiros próximos armazenados nos nós anteriores.
Então, se alguma vez perdeu a noção de qualquer um destes locais,
dizer alterando um dos ponteiros próximos em nossa lista,
por exemplo, dizer que mudou
campo seguinte o nó 3 é
para apontar para algum nó aqui.
Nós estaríamos fora de sorte, porque não faria
tem alguma idéia de onde encontrar o resto da lista,
e isso é, obviamente, muito ruim.
Então, nós temos que ter muito cuidado sobre a ordem
em que manipular os ponteiros próximas durante a inserção.
>> Então, para simplificar, vamos dizer que
nossos primeiros quatro nós
são denominados A, B, C, e D, com as setas que representam a cadeia de ponteiros
que ligam os nós.
Então, precisamos inserir nosso novo nó
entre os nós C e D.
É fundamental fazê-lo na ordem certa, e eu vou mostrar-lhe porquê.
>> Vamos olhar para a maneira errada de fazer isso primeiro.
Ei, sabemos que o novo nó tem que vir logo depois C,
então vamos definir ponteiro próximo do C
para apontar para new_node.
Tudo bem, parece tudo bem, só temos que terminar agora por
fazendo ponto o novo nó do ponteiro ao lado de D,
mas espera, como podemos fazer isso?
A única coisa que poderia nos dizer onde era D,
o ponteiro próximo foi previamente armazenado em C,
mas nós apenas reescreveu que o ponteiro
para apontar para o novo nó,
assim já não temos qualquer pista onde D é na memória,
e nós perdemos o resto da lista.
Não é bom em tudo.
>> Então, como vamos fazer isso certo?
Primeiro, apontar ponteiro seguinte, o novo nó no D.
Agora, os ponteiros tanto o novo nó e C do próximo
estão apontando para o mesmo nó, D,
mas isso é bom.
Agora podemos apontar ponteiro próximo do C no novo nó.
Então, nós fizemos isso sem perder quaisquer dados.
No código, C é o nó actual
que a travessia ponteiro rastreador está apontando,
e D é representada pelo nó apontado pelo campo seguinte do nó actual,
ou rastreador → seguinte.
Então, primeiro definir ponteiro seguinte, o novo nó
para apontar para rastreador → seguinte,
da mesma forma que disse ponteiro próxima new_node deveria
apontar para D na figura.
Então, podemos definir ponteiro próximo do nó atual
para nosso novo nó,
assim como nós teve de esperar até o ponto C para new_node no desenho.
Agora tudo está em ordem, e não perdemos
o controle de todos os dados, e fomos capazes de apenas
furar o nosso novo nó no meio da lista
sem reconstruir a coisa toda ou até mesmo deslocando todos os elementos
do jeito que teria que ter com uma matriz de comprimento fixo.
>> Então, listas ligadas são um básico, mas importante, estrutura de dados dinâmica
que têm vantagens e desvantagens
em comparação com as matrizes e outras estruturas de dados,
e, como é frequentemente o caso em ciência da computação,
é importante saber quando usar cada ferramenta,
para que você possa escolher a ferramenta certa para o trabalho certo.
>> Para mais prática, tente escrever funções para
excluir nós de uma lista ligada -
lembre-se de ter cuidado com a ordem em que você reorganizar
os ponteiros próximos para garantir que você não perca um pedaço de sua lista -
ou uma função para contar os nós em uma lista ligada,
ou um divertimento, para inverter a ordem de todos os nós em uma lista ligada.
>> Meu nome é Jackson Steinkamp, ​​este é CS50.