fork download
copy 
  1. program listaligada;
  2.  
  3. (* Antigamente, penso que não era possível fazer o que fiz aqui: utilizei um
  4.    tipo de dados dentro da sua própria definição (especificamente, o campo
  5.    `next` é um apontador para o record que estamos a definir.
  6.     Era necessário fazer algo como:
  7.     
  8.        type
  9.           PNo = ^No;
  10.           No = record
  11.              ...
  12.              next: PNo;
  13.           end;
  14.    
  15.    Hoje em dia parece que não é preciso, ou então nunca foi, mas pronto, nunca
  16.    faz mal prevenir. *)
  17.  
  18. type
  19.    no = record
  20.       val: integer;
  21.       next: ^no;
  22.    end;
  23.  
  24. (* Essencial à compreensão de listas ligadas é perceber que um apontador é
  25.    apenas uma etiqueta, um número que representa um endereço de memória, e não
  26.    um objecto ou uma estrutura de dados por si só.
  27.  
  28.    Por esse motivo, os apontadores são bastante leves, pois implicam uma
  29.    alocação de 4 ou 8 bytes (32 ou 64bits).
  30.  
  31.    Nas listas ligadas, precisamos tipicamente de 3 apontadores (podemos fazer
  32.    isto com dois, mas é mais intuitivo com 3):
  33.     * head : aponta para o primeiro nó da lista)
  34.     * cur  : funciona como "cursor", ou nó actual ("current")
  35.     * last : nó actual da iteração anterior (na prática, o valor anterior de cur)
  36.  
  37.    Inicialmente, todos têm valor «nil» (representa a ausência de um endereço
  38.    válido).
  39.  
  40.    Na primeira iteração, alocamos espaço para `cur` através de new(); agora,
  41.    `cur` contém o endereço de uma estrutura `no`:
  42.  
  43.              +-----+------+
  44.     cur ---> | val | next |
  45.              +-----+------+
  46.  
  47.    No entanto, como estamos na primeira iteração, também queremos marcar este nó
  48.    como sendo a cabeça da lista. Então dizemos que `head := cur`, copiando o
  49.    endereço contido em `cur` para `head` (atenção: apenas o endereço numérico é
  50.    copiado. a memória em si, onde reside o primeiro elemento da lista, não é
  51.    duplicada). Efectivamente, `cur` e `head` apontam agora para o mesmo bloco
  52.    de memória:
  53.  
  54.                 head
  55.                   v
  56.             +-----+------+
  57.    cur ---> | val | next |
  58.             +-----+------+
  59.  
  60.    Vamos agora passar à próxima iteração. Antes disso, temos que informar que
  61.    `cur` vai deixar de ser o nó actual, para passar a ser o anterior, de forma a
  62.    conseguirmos referir-nos a ele quando estivermos na iteração seguinte.
  63.    Para isso, `last := cur`, e os 3 apontadores apontam para o mesmo elemento:
  64.  
  65.  
  66.                 head
  67.                   v
  68.             +-----+------+
  69.    cur ---> | val | next |
  70.             +-----+------+
  71.                   ^
  72.                 last
  73.  
  74.    Na iteração seguinte, fazemos novamente `new(cur)`, o que aloca novamente
  75.    memória para um novo record `no` e coloca o seu endereço em `cur`:
  76.  
  77.        head    
  78.          v
  79.    +-----+------+             +-----+------+
  80.    | val | next |    cur ---> | val | next |
  81.    +-----+------+             +-----+------+
  82.          ^
  83.        last
  84.  
  85.    Como podems ver, `head` e `last` apontam ambos para o primeiro elemento, mas
  86.    `cur` aponta para outro.
  87.    Qual o primeiro elemento da lista? Fácil, basta ver para onde `head` aponta.
  88.    Mas agora falta-nos ligar os elementos, para que seja uma verdadeira lista
  89.    ligada e não apenas um conjunto de records dispersos na memória.
  90.    Para isso, dizemos que o campo `next` do último nó da lista (apontado por
  91.    `last`) aponta para o novo nó que criámos, apontado por `cur`:
  92.  
  93.       last^.next := cur;
  94.  
  95.        head    
  96.          v
  97.    +-----+------+             +-----+------+
  98.    | val | next---\  cur ---> | val | next |
  99.    +-----+------+ |           +-----+------+
  100.          ^        |                 ^
  101.        last       \-----------------/
  102.  
  103.    Agora, basta fazermos o que fizemos anteriormente: apontar `last` para o nó
  104.    actual, de forma a podermos repetir tudo na iteração seguinte:
  105.  
  106.  
  107.        head                       last
  108.          v                          v
  109.    +-----+------+             +-----+------+
  110.    | val | next---\  cur ---> | val | next |
  111.    +-----+------+ |           +-----+------+
  112.                   |                 ^
  113.                   \-----------------/
  114.  
  115. *)
  116.  
  117. var
  118.    (* head: Cabeça da lista
  119.     * cur:  Cursor, current, nó actual
  120.     * last: Elemento da iteração anterior
  121.     *)
  122.    head, cur, last: ^no;
  123.    i: integer;
  124. begin
  125.    for i := 1 to 10 do begin
  126.       (* Alocamos memória para o nó actual *)
  127.       new(cur);
  128.       if i = 1 then
  129.          (* Se o nó for o primeiro, apontamos `head` para ele *)
  130.          head := cur
  131.       else
  132.          (* Senão, então dizemos que o `next` do anterior é o actual *)
  133.          last^.next := cur;
  134.  
  135.       cur^.val := i * i;
  136.  
  137.       (* O nó actual passa a ser o anterior da iteração seguinte *)
  138.       last := cur;
  139.    end;
  140.  
  141.    (* Apontamos o nosso "cursor" à cabeça da lista, e iteramos... *)
  142.    cur := head;
  143.    (* Enquanto o cursor for diferente de nil (enquanto apontar para nó válido *)
  144.    while (cur <> nil) do begin
  145.       (* Escrevemos o seu valor *)
  146.       writeln(cur^.val);
  147.       (* Usamos `last` como variável auxiliar *)
  148.       last := cur;
  149.       (* Avançamos o cursor para o próximo elemento *)
  150.       cur := cur^.next;
  151.       (* E libertamos a memória do anterior *)
  152.       dispose(last);
  153.    end;
  154. end.
Success #stdin #stdout 0s 232KB
comments (?)
stdin
copy 
Standard input is empty
stdout
copy 
1
4
9
16
25
36
49
64
81
100
https://ideone.com/wQBgsu
Lista ligada (Pascal)
language:
Pascal (fpc 3.0.4)
created:
10 years ago
visibility:
secret

Share or Embed source code

Discover > Sphere Engine API

The brand new service which powers Ideone!

Discover > IDE Widget

Widget for compiling and running the source code in a web browser!