Pointers, listas ligadas e afins?

[thoga31]

Pessoal, venho-vos pedir ajuda (para variar).

Estou a bater com a cabeça nas paredes com os pointers. A teoria deles eu sei, e apontadores simples também sei. O que me está a fazer comichão aos neurónios são as coisas mais complexas como listas ligadas na prática.

Não há tutorial por esta web fora que me esclareça. Espetam com um exemplo de uma lista ligada e o texto que se segue pode-se sempre resumir a "pronto, é isto" - lamento, mas não sou o Einstein nem descendo das suas linhagens.

Alguém entendido na matéria me pode iluminar neste assunto? Luzes tenho eu a andar de volta da minha cabeça de tanto bater com a cabeça, mas elas não me iluminam a mente...

Cumprimentos.

Edited July 22, 2013 at 08:17 PM by thoga31

[nunopicado]

Ora, o Pedro e o Passarito são mais fãs de Pointers, mas cum caneco, tive 18 a listas ligadas em C, ainda me devo lembrar qualquer coisa! lol

Vejamos:

type 
  TLista=Record
    Nome:String;
    Idade:Byte;
    Next:^TLista;
  end;

A base, como já viste, é algo assim.

A explicação, é mais simples do que a prática, para variar.

Tens, em cada registo, dois campos (nome e idade) e um apontador para o proximo registo.

Sempre que o campo Next for = nil, significa que não está a apontar para lado nenhum. Logo, o registo onde estás, é o último da lista.

Se ele estiver a apontar para algum lado, significa que a lista ainda não terminou.

Para te movimentares, precisas de duas variáveis do tipo TLista.

Uma será = ao node root, e a partir daí nunca será mexida, para não perderes o fio à meada.

Outra servirá para te movimentares, e essa é a principal.

Imagina:

var
  RootNode,CurNode:^TLista;
begin
  New(RootNode);  // Crias o primeiro node. - Neste não tocas mais, apenas para leitura

  CurNode:=RootNode; // Apontas o CurNode para o primeiro.

  CurNode^.Nome:='Nuno';
  CurNode^.Idade:=35;
  CurNode^.Next:=nil;  // Não é obrigatório, visto já ser nil, mas na dúvida...

Temos neste momento uma lista com apenas um registo. O registo tem os dados de nome e idade, e o Next aponta para nada. (nil)

Agora queres adicionar mais um registo.

  new(CurNode.Next);  // Crias o novo registo
  CurNode:=CurNode^.Next;  // Movimentas-te para o novo registo

  CurNode^.Nome:='Igor';
  CurNode^.Idade:='16'; // Emenda se quiseres! 
  CurNode^.Next:=nil;

Neste momento tens dois registos.

O primeiro, que ainda está em RootNode, e o segundo que é onde está, no momento, o CurNode.

O que ainda precisas de perceber, caso não o tenhas já feito, é o seguinte:

Quando fazes CurNode:=CurNode^.Next, não estás a perder os dados, pois apenas estás a mudar a "seta" de local. Os dados continuam em memória, apenas não têm variável nenhuma que aponte para elas.

É por este motivo que o RootNode nunca se pode mexer. Se mexeres, perdes a ligação ao primeiro node, em sem ele, não tens como recuperar os dados da memória.

Se tiveres 100 registos, a partir do primeiro consegues encontrar qualquer um.

Se não tiveres o primeiro, e o CurNode estiver, por exemplo, no 50º, metade da informação já foi ao ar, pois não tens como chegar aos primeiros 49.

O que nos trás a outro assunto: libertar a memória.

Sempre que quiseres eliminar um registo, tens de libertar a memória usada, caso contrário, ainda que não uses a informação, ela fica a ocupar memória.

Imagina que queres eliminar o último registo:

  Dispose(CurNode);  // Sendo que CurNode já estava a apontar para o ultimo registo.

Isto eliminou da memória o ultimo registo.

Mas e se não for o ultimo, e sim, por exemplo, o 2º registo, numa lista de 100.

Não te basta eliminar o segundo, pois deixaria de haver ligação entre o 1º e o 3º.

Então:

  CurNode:=RootNode;  // Posiciona-se na posição prévia ao elemento a eliminar, neste caso, RootNode.
  DelNode:=CurNode^.Next;  // Uma nova variável do mesmo tipo, DelNode, irá apontar para o elemento a eliminar.
  CurNode^.Next:=DelNode^.Next;  // Liga-se o Next do elemento prévio ao Next do elemento a eliminar, eliminando assim da lista o elemento (mas a informação ainda está em memória).

  Dispose(DelNode);  // Liberta-se a memória do elemento a eliminar.

Pedro e Passarito, falhei muito? 😛

Edited July 22, 2013 at 10:24 PM by nunopicado

[nunopicado]

Já agora, a questão dos chapéus... 🙂

Quando, ao definires a variável, usas o ^ antes do tipo, estás a dizer que essa variável será um ponteiro para esse tipo de dados.

Depois, ao usares a variavel sem chapeus, estás a referir-te ao ponteiro em si. Ou seja, quando lhe acedes, estás a aceder a um endereço de memória, não aos dados que esse endereço contem.

Para acederes aos dados de um ponteiro, tens de lhe aceder colocando o ^ no fim da variável.

Neste caso, sempre que precises aceder aos campos do Record (TLista), tens de meter o ^ no fim.

[Kline777]

Por acaso no inicio do software que fiz na empresa, chegámos ao cliente e aquilo demorava 10min a calcular... porque estavamos a passar um ficheiro txt de 100mb em linhas e a passa-las para uma memory table do delphi para fazer calculos... além de demorar a memoria do pc nao chegava e PUM! Cliente passado claro 😛

Tivemos a ideia de passar tudo para ponteiros e seleccionar os melhores momentos para libertar a memoria... parecia magia ^^ são um pesadelo para fazer debug mas tenho que admitir que ainda podem ser muito uteis.

[passarito]

Em 23/07/2013 às 00:16, nunopicado disse:

Ora, o Pedro e o Passarito são mais fãs de Pointers

Da parte que me toca, saber um pouco de ponteiros e ser fã vai uma alguma distancia. Só aprendi ponteiros bastante tarde, usei-os em casos muito especiais e muito pré-formatados. Alguns aspectos técnicos até sabem mais do eu.

Apenas uma dúvida, não sei se quando crias o 2º registo com new(CurNode.Next); o campo next do registo anterior vai ficar a apontar para o novo registo criado ou não?

Eu pessoalmente uso uma terceira variavel para fazer a actualização do campo next.

var RootNode,CurNode,AuxNode:^TLista;
...
 AuxNode:=CurNode.Next;
 new(CurNode);  // Crias o novo registo

 CurNode.Next:=AuxNode.Next; //O next do novo registo vai apontar para onde o next do registo anterior estava a apontar

{Já não necessito de o mover para o próximo registo, mas necessito dizer ao compo next do registo anterior para apontar para este registo novo}
 //CurNode:=CurNode^.Next;  // Movimentas-te para o novo registo
 AuxNode.next:=CurNode;

 CurNode^.Nome:='Igor';
 CurNode^.Idade:='16'; // Emenda se quiseres! 

Isto pode parecer um preciosismo mas se quizeres fazer uma lista ordenada tem toda a relevancia, pois podes ter de inserir um registo no meio de dois já existentes!

@thoga, há algum tempo tu colocaste um artigo meu na wiki sobre ponteiros, https://wiki.portugal-a-programar.pt/dev_geral/pascal/ponteiros/, não te entendeste?

[HappyHippyHippo]

e que tal dar uma perninha a uma outra linguagem onde ponteiros é o pão nosso de cada dia ?

https://www.portugal-a-programar.pt/topic/61312-listas-ligadas-simples-tentar-entender-o-conceito/

[passarito]

e que tal dar uma perninha a uma outra linguagem onde ponteiros é o pão nosso de cada dia ?

http://www.portugal-a-programar.pt/topic/61312-listas-ligadas-simples-tentar-entender-o-conceito/

Não tem nada de novo que o documento da Wiki não tenha.

Para iniciar tens as listas ligadas simples, as outras, são todas derivações:

Listas ligadas duplas: Os registos têm a referencia do registo imediatamente à frente e atrás;

Listas circulares (simples e duplas): Não há apontadores para nill. O útltimo registo aponta para o primeiro e, no casos das circulares duplas, o primeiro aponta para o último;

Árvores: registos com dois ponteiros, esquerda e direita (também podem ser circulares);

[nunopicado]

Passarito:

Tens razão, só o new não resolve. Tem de se criar e depois por o ponteiro a apontar para lá.

Lá está, já lá vão 17 anos desde que mexi com ponteiros e listas ligadas pela ultima vez.

[HappyHippyHippo]

Não tem nada de novo que o documento da Wiki não tenha.

continua a ler o tópico e verás um código mais simples que o apresentado na wiki (em C claro)

[passarito]

continua a ler o tópico e verás um código mais simples que o apresentado na wiki (em C claro)

Da primeira dei uma vista de olhos em ambas as páginas.

Desta segunda vez estive a analisar com mais atenção e a conclusão é que é exactamente a mesma coisa.

1. Crias o nó

2. Se a lista for ordenada, procura o local e insere o registo, se não coloca-o no fim.

3. Faz a actualização das ligações dos nós, tendo em atenção que o 1º registo é sempre um caso especial

O que é que isto tem de diferente e mais dificil do que o que tu dizes?

que passos são necessário para fazer esta acção ?

- criar o novo nó

- saber qual a posição da lista onde inserir o novo nó

- dizer ao nó criado que o nó seguinte é o nó na posição que se deseja

- dizer ao nó anterior à posição a ser inserida que o nó seguinte e o nó criado

Se achas que o C e mais fácil que o Pascal, eu acho o contrário e aí o caso muda de figura e é um "Here we go again..." mais um tópico C Vs Pascal

Eu não quereria ir por aí....

[nunopicado]

Nem vale a pena...

Ambas as formas são válidas para as linguagens a que respeitam e não adianta mais um tópico desses! 🙂

Para uns é mais fácil de uma maneira, para outros de outra, e somos todos amigos.

Agora, certo certo é que eu já não me lembrava nada disto... Tive de andar a puxar pela mona para me lembrar, e mesmo assim, falharam pontos.

Tenho de dar uma recauchutada aos meus ponteiros.

[HappyHippyHippo]

Se achas que o C e mais fácil que o Pascal, eu acho o contrário e aí o caso muda de figura e é um "Here we go again..." mais um tópico C Vs Pascal

eu nunca disse que C é mais fácil que Pascal !!!

o que disse é que o código apresentado é mais simples. queres um exemplo ?

Procedure le_insere_reg;
Begin
 New(NovoReg);
 Write('Marca do tubo: ');
 readln(NovoReg^.marca);
 Write('Tamanho: ');
 readln(NovoReg^.tamanho);
 Aux1:=Inicio;
 if (Incio=NIL) OR  (NovoReg^.marca<Aux1^.marca) then begin {1º elemento da lista se a lista está vazia, ou se marca menor que o primeiro elemento da lista}
   NovoReg^.NextPtr:=Inicio;
   Inicio:=NovoReg {NovoReg Não leva ^ porque queremos que Inicio aponte para a zona de memória onde está o NovoReg e não o seu conteúdo}
 end
 else begin   {Vamos percorrer a linha que tem inicio em Inicio e não queremos perder a referencia de memória de Inicio para o 1º registo da lista, então usa-se uma variável auxiliar atribuida anteriormente em Aux1:=Inicio;}
     While (NovoReg^.marca>=Aux1^.marca) AND (Aux1<>NIL) do begin
       RegAnterior:=Aux1; { <----------------------------------------------------------------------------------------- }
       Aux1:=Aux1^.NextPtr;
     end;
     NovoReg^.NextPtr:=Aux1;
     RegAnterior^.NextPtr:=NovoReg;
 end;
end;

o código apresentado no tópico que referenciei apresenta um algoritmo sem o uso de variáveis extras como a assinalada no código anterior

Edited July 23, 2013 at 12:09 PM by HappyHippyHippo

[pwseo]

thoga31,

Estive a escrever isto um pouco à pressa (é um exemplo ridiculamente simples), e não cheguei a explicar bem como se itera na lista para libertar os elementos da mesma. Ainda assim, espero que te esclareça um pouco:

Listas Ligadas em Pascal (ideone)

Eventualmente poderei rever isso.

EDIT: Peço desculpa por basicamente ter ignorado as respostas dadas antes de mim. Estava com pressa e... pronto, deu nisto. Depois irei reler o tópico e fazer as devidas alterações 🙂

Edited July 23, 2013 at 05:48 PM by pwseo

[thoga31]

Haja alguém que consiga manter o tópico dentro dos carris e dar-lhe a decência que lhe é devida... caramba! Nem para ajudar um colega que está com dificuldades em entender um assunto conseguem manter a "lucidez" no discurso. Esquecem-se do que tratava o tópico e começa o forró...

@thoga, há algum tempo tu colocaste um artigo meu na wiki sobre ponteiros, http://wiki.portugal-a-programar.pt/dev_geral:pascal:ponteiros, não te entendeste?

Não quero ofender, mas vou ser muito directo e muito sincero. O teu tutorial foi a 1ª coisa que decidi ver, e encaixa muito bem nesta descrição:

Não há tutorial por esta web fora que me esclareça. Espetam com um exemplo de uma lista ligada e o texto que se segue pode-se sempre resumir a "pronto, é isto"

Estive a escrever isto um pouco à pressa (é um exemplo ridiculamente simples), e não cheguei a explicar bem como se itera na lista para libertar os elementos da mesma. Ainda assim, espero que te esclareça um pouco:

Listas Ligadas em Pascal (ideone)

Muito obrigado, foi escrito "à pressa" mas foi precisa paciência e dedicação para fazer uma coisa tão pormenorizada. Vou ler com cuidado e se tiver alguma dúvida apito.

O mesmo para o @nunopicado, que fez ali um post todo à maneira 👍

Até já 😄

[GRSa]

Talvez o que faz com que se entenda mal este assunto é a falta de esclarecimento sobre o que guarda um ponteiro e o que se pode fazer com o conteúdo por ele armazenado.

Um ponteiro guarda simplesmente um endereço, melhor dizendo, uma referência a um local reservado na memória. Uma variável comum, qual seja, não ponteiro, não é de toda variável. No que se refere ao vínculo da variável com o espaço na memória armazenada para tal, pode-se dizer que tem natureza constante. O que varia é somente o conteúdo armazenado neste espaço. Já uma variável do género ponteiro é mais amplamente variável. Diz-se isso pelo fato de ser possível alternar o endereço da memória a ela vinculada. Estes simples conceitos devem ser concretamente assimilados.

Um exemplo da criação da lista encadeada pode ser expresso no seguinte código:

Program PercorrendoLista ;

 // Definição de um tipo para representar um nó da lista
 type TNo = record
nome  : string ; // Dado armazenado pelo nó
prox : ^TNo ; // Ponteiro p/ próximo nó
end ;

 Var
pinicio: ^TNo; // Guarda endereço 1º nó da lista
p1: ^TNo; // Auxiliar. Guarda endereço de um nó
resposta : char ; // Auxiliar. Controla repetição.

Begin
 pinicio := nil ;

 // Repetição que define os nós da lista
 repeat
new( p1 );
write( 'Entre com novo dado: ' );
readln( p1^.nome ) ;
p1^.prox := pinicio ;
pinicio := p1 ;
write( 'Novo dado(S/N)?' );
readln( resposta );
resposta := upcase( resposta );
 Until resposta = 'N' ;

 // Percorrer a lista, imprimindo seus elementos
 p1 := pinicio ;
 while( p1 <> nil ) do
 Begin
writeln( 'Nome: ' , p1^.nome );
p1 := p1^.prox ;
 End;

 // Percorrer a lista, desalocando memória para os elementos
 while( pinicio <> nil ) do
 Begin
p1 := pinicio ;
pinicio := pinicio^.prox ;
dispose( p1 );
 End;

 readln ;
End.

Este é um exemplo simples, mas bem efetivo. Pulando a parte das declarações das variáveis começa-se explicando:

Na linha 14 a variável pinicio é iniciada com nil, ou seja, aponta para nenhum local na memória, está vazia. Dentro de um loop que deseja servir para capturar seguidamente vários nomes para a lista começa-se na linha 18 algo muito importante. O procedimento NEW pura e simplesmente atribui à variável p1 o endereço de um espaço qualquer na memória preparado para receber dados aos moldes do tipo da variável p1. Após a captura do nome na linha 20, na linha 21 o campo prox da variável p1 recebe o endereço armazenado por pinicio. A variável pinicio, logo na linha 22, passa a receber o endereço antes armazenado por p1.

Passo a passo de um exemplo de execução do código. Inserção de cinco nomes à lista:

1º Loop:

Linha 18: p1 recebe o endereço ADRESS01*;

Linha 20: Insere-se o nome ‘fulanoA’;

Linha 21: p1^.prox recebe o endereço nil;

Linha 22: pinicio recebe o endereço ADRESS01* que aponta para o espaço na memória que agora armazena o nome ‘fulanoA’ e o endereço nil;

2º Loop:

Linha 18: p1 recebe o endereço ADRESS02*;

Linha 20: Insere-se o nome ‘fulanoB’;

Linha 21: p1^.prox recebe o endereço ADRESS01;

Linha 22: pinicio recebe o endereço ADRESS02* que aponta para o espaço na memória que agora armazena o nome ‘fulanoB’ e o endereço ADRESS01;

3º Loop:

Linha 18: p1 recebe o endereço ADRESS03*;

Linha 20: Insere-se o nome ‘fulanoC’;

Linha 21: p1^.prox recebe o endereço ADRESS02;

Linha 22: pinicio recebe o endereço ADRESS03* que aponta para o espaço na memória que agora armazena o nome ‘fulanoC’ e o endereço ADRESS02;

4º Loop:

Linha 18: p1 recebe o endereço ADRESS04*;

Linha 20: Insere-se o nome ‘fulanoD’;

Linha 21: p1^.prox recebe o endereço ADRESS03;

Linha 22: pinicio recebe o endereço ADRESS04* que aponta para o espaço na memória que agora armazena o nome ‘fulanoD’ e o endereço ADRESS03;

5º Loop:

Linha 18: p1 recebe o endereço ADRESS05*;

Linha 20: Insere-se o nome ‘fulanoE’;

Linha 21: p1^.prox recebe o endereço ADRESS04;

Linha 22: pinicio recebe o endereço ADRESS05* que aponta para o espaço na memória que agora armazena o nome ‘fulanoE’ e o endereço ADRESS04;

E é isso gente. Relevem se fui pouco técnico ou pouco acadêmico, o objetivo é que o conceito seja facilmente entendido. Lembre-se que a minha escrita pode parecer um pouco diferente para vocês por ser brasileiro. 👍

[thoga31]

Estive a ler com atenção o código do @pwseo, depois de encher a pança 😄 , e finalmente estou a começar a entender a história e o porquê das atribuições que são feitas. Mil obrigados, @pwseo. Finalmente alguém me conseguiu clarificar o mistério das cinco chagas 😛

Portanto, se não me enganei a dissecar o código do @GRSa com base nos meus novos entendimentos, ele implementou uma stack enquanto o @pwseo implementou essencialmente uma queue.

@GRSa, acabei por não ler o texto pormenorizado pois achei-o confuso. Preferi tentar esquematizar o teu código e, se não me enganei, fizeste uma lista LIFO.

Corrijam-me se me enganei 😄

(estou a tentar perceber isto só com cabeça, papel e caneta, não me meti a compilar nenhum código para o testar - um assunto difícil terá de ser entendido à força bruta xD)

Edited July 23, 2013 at 08:42 PM by thoga31

[GRSa]

Portanto, se não me enganei a dissecar o código do @GRSa com base nos meus novos entendimentos, ele implementou uma stack enquanto o @pwseo implementou essencialmente uma queue.

@GRSa, acabei por não ler o texto pormenorizado pois achei-o confuso. Preferi tentar esquematizar o teu código e, se não me enganei, fizeste uma lista LIFO.

Sim, tratei de um exemplo que aborda o conceito de pilha (stack), uma lista linear (LIFO). Que pena que você achou o texto confuso. Em que parte exatamente? Achei a minha explicação bastante razoável. Sei que você criou este tópico mais para animar um debate sobre o assunto. Você sabe disso e muito mais.

Edited July 23, 2013 at 09:03 PM by GRSa

[thoga31]

Não, por acaso criei o tópico mesmo para aprender algo que não sabia - apontadores e suas aplicações 😄

Todo o texto referente aos 5 loop's torna-se algo confuso. Prefiro diagramas, e nesse aspecto o @pwseo foi exímio. Dissequei o teu código à unha, portanto. Percebi, por fim, que estava perante uma lista LIFO (aka stack).

Eu implemento stacks sem apontadores, mas as queues são um caso mais bicudo em que é mais eficiente usar listas ligadas (mais eficiente ou, talvez, menos pesado para a memória - para queues grandes e com constante push e pop eu gasto muita memória, e parte dela para nada a certo ponto).

[passarito]

Em 23/07/2013 às 18:55, thoga31 disse:

Haja alguém que consiga manter o tópico dentro dos carris e dar-lhe a decência que lhe é devida... caramba! Nem para ajudar um colega que está com dificuldades em entender um assunto conseguem manter a "lucidez" no discurso. Esquecem-se do que tratava o tópico e começa o forró...

Por muito que me custou ficar calado, foi por esse motivo que não respondi a HappyHippyHippo. O tópico iria passar a ser mais 1 C Vs Pascal e eu não quiz alimentar isso!

Em 23/07/2013 às 18:55, thoga31 disse:

passarito, em 23 de Julho de 2013 - 10:40, disse:

@thoga, há algum tempo tu colocaste um artigo meu na wiki sobre ponteiros, http://wiki.portugal-a-programar.pt/dev_geral:pascal:ponteiros, não te entendeste?

Não quero ofender, mas vou ser muito directo e muito sincero. O teu tutorial foi a 1ª coisa que decidi ver, e encaixa muito bem nesta descrição:

thoga31, em 22 de Julho de 2013 - 21:16, disse:

Não há tutorial por esta web fora que me esclareça. Espetam com um exemplo de uma lista ligada e o texto que se segue pode-se sempre resumir a "pronto, é isto"

Quando perguntei, "não te entendeste?", não era com um intuito agressivo, antes pelo contrário, seria para me dizeres o que não estavas a entender para eu, se soubesse, te puder ajudar.

Quanto ao "Não quero ofender", seria preciso muito mais do que isso, no entanto fiquei surpreso, quando fiz o post que colocaste na Wiki, disse para se sentirem livres para alterarem/corrigirem o texto se assim o entendessem, pois a clareza da minha escrita nem sempre é a melhor.

Para mim, onde os ponteiros fazem mais sentido é nas listas (lifo, fifo, ordenadas, etc.) e árvores, e que cada registo criado é alocado na memória e que podes ter uma variável que te dá a informação alocada nesse local da memória. Podem ter outras finalidades que de repente desconheço mas nada como falar nelas.

Mas ok, aceito as tuas criticas.

[thoga31]

Quanto ao tópico em si e o seu rumo parcial, já disse tudo o que tinha a dizer. Cada um entenda como quiser. Adiante.

Eu sei que não perguntaste com intuito agressivo, da mesma forma que eu também não tive esse intuito, como creio que te apercebeste. Apenas fui sincero.

Quanto ao tutorial, na altura tinhas recebido boas críticas pelo que coloquei na Wiki. Não sendo um entendido no assunto e como não o estudei na altura, limitei-me a fazer o que seria natural - seguir as opiniões de quem sabia.

Agora dediquei-me ao assunto, e senti que a explicação das listas estava escassa ou pobre.

Isto tudo depende de quem está a ler as coisas. Há quem ache que o meu tutorial está fantástico, mas também já recebi críticas com outros pareceres. No que diz respeito a apontadores, parecia que tinha um qualquer bloqueio natural para o assunto (leia-se a aplicação prática de apontadores, a sua teoria sempre a soube bem) e precisei de uma explicação mais pormenorizada, explicando passo-a-passo e de forma não menos simples o porquê de cada atribuição feita.

Se vires o teu tutorial, tu apresentas a teoria dos apontadores (até aí tudo ok) mas depois fazes uma mera aplicação em listas ligadas (e aí eu perdi-me).

O que importa é que já entendi e houve interesse por parte de algumas pessoas em me transmitir o conhecimento (algumas no sentido de não serem muitas, isto não foi nenhuma romaria ao santuário). Tenham sido elas ou não aqueles que conseguiram arranjar uma forma de eu entender, o que me interessa é que houve interesse por parte dessas pessoas. 😉