Curso de Pascal
Ponteiros
Você está em: MarMSX >> Cursos >> Pascal
1. Variáveis dinâmicas
Foi visto até aqui, que as variáveis armazenam dados na memória e esses dados podem ser de diversos tipos. Elas localizam-se em uma área separada do código executável, onde cada variável é um bloco de memória contendo o dado em si.
As varáveis que foram apresentadas até o presente momento são do tipo estáticas. Entretanto, elas podem ser de dois tipos: estáticas ou dinâmicas.
Uma variável do tipo estática é uma variável que possui um nome que a referencia, é criada em tempo de compilação e esta está sempre no mesmo lugar da memória. Já a variável do tipo dinâmica não possui um nome associado a ela e é criada/destruída em tempo de execução do programa.
Por que variáveis dinâmicas?
Quando criamos aplicações onde não temos como prever a quantidade de dados armazenados na memória, como por exemplo um cadastro de clientes, podemos subestimar ou superestimar o espaço de memória utilizado para armazenar os dados através do uso de vetores ou matrizes. Além disso, não cabe ao usuário modificar o programa de forma a adaptar às mudanças, até mesmo porque isso nem sempre é possível, pois ele na maioria das vezes conta somente com o código executável da aplicação.
As variáveis dinâmicas permitem o uso inteligente da memória, quando passamos a utilizar a quantidade necessária de dados, uma vez que os dados são criados ou destruídos na memória conforme a demanda.
A segunda parte desse capítulo irá abordar a criação de listas dinâmicas. Nessa parte, vamos entender como as variáveis dinâmicas são criadas e referenciadas.
Definição de ponteiro
Uma vez que a variável dinâmica não possui um nome associado a ela, ela é referenciada por outro tipo de variável: o ponteiro. O objetivo de um ponteiro é armazenar um endereço de memória que indica a localização de um dado criado dinamicamente.
A representação de um ponteiro em Pascal é o sinal de circunflexo "^".
Declaração de um ponteiro:
var nome_ponteiro : ^tipo_de_dado;
Por exemplo, a criação de um ponteiro do tipo integer é:
var p : ^integer;
A criação de variáveis dinâmicas
A criação de um variável dinâmica é feita através da alocação de memória, isto é, a reserva de um espaço de memória para ela armazenar dados. Nesse processo, além de reservar um espaço de memória para a variável dinâmica, o endereço do primeiro byte da área reservada é retornado para um ponteiro.
O comando new(ponteiro) é o responsável pela alocação de memória. O espaço reservado depende do tipo de dado do ponteiro utilizado no comando new(). Exemplo:
var p : ^integer;
begin
new(p);
end.
O comando new(p) reserva 2 bytes (tamanho do integer) na memória e retorna para "p" o endereço da área reservada. Veja o diagrama a seguir.
┌─────────┬──────┐
│ Memória │ Dado │
├─────────┼──────┤
│ xxxx │ xx │ Programa
├─────────┼──────┤
+-> │ 2F3EH │ xx │ Heap
| ├─────────┼──────┤ (variáveis dinâmicas)
| │ 2F3FH │ xx │
| ├─────────┼──────┤
| │ ..... │ .. │
| ├─────────┼──────┤
+- p │ D230H │ 3EH │ Área de dados
├─────────┼──────┤ (variáveis estáticas)
│ D231H │ 2FH │
└─────────┴──────┘
O ponteiro "p" é criado na área de dados e contém o endereço do espaço criado dinamicamente (&H2F3E). Observe que no endereço reservado há um valor de dado aleatório. Isso se assemelha à criação de uma variável estática, que enquanto não tiver um valor atribuído a ela, terá uma valor aleatório (também chamado de lixo).
Assim como qualquer variável, o ponteiro recém criado também possui um valor (referência a endereço) aleatório. Convém-se atribuir inicialmente o endereço de ponteiro igual a 0, através a da palavra reservada NIL. Isso significa que o ponteiro NÃO aponta para qualquer variável dinâmica.
O programa a seguir testa se o ponteiro "p" está ou não referenciando uma variável dinâmica.
var p : ^integer;
procedure testa_ptr;
begin
if p = nil then
writeln('Ponteiro nulo.')
else
writeln('Ponteiro referenciado.');
end;
begin
p := nil;
testa_ptr;
new(p);
testa_ptr;
end.
Saída:
Ponteiro nulo.
Ponteiro referenciado.
Leitura / escrita de dados em variáveis dinâmicas
Após criar uma variável dinâmica na memória, podemos acessar esse espaço de forma a inserir ou ler os dados contidos nele. O acesso à região de memória reservada é realizado através de um ponteiro.
A sintaxe para o acesso é:
ponteiro^
No exemplo a seguir, vamos alocar um espaço em memória e inserir o valor 4 nele.
var p : ^integer;
begin
new(p);
p^ := 4;
end.
O diagrama a seguir ilustra o funcionamento do programa.
┌─────────┬──────┐
│ Memória │ Dado │
├─────────┼──────┤
│ xxxx │ xx │ Programa
├─────────┼──────┤
+-> │ 2F3EH │ 04 │ Heap
| ├─────────┼──────┤ (variáveis dinâmicas)
| │ 2F3FH │ 00 │
| ├─────────┼──────┤
| │ ..... │ .. │
| ├─────────┼──────┤
+- p │ D230H │ 3EH │ Área de dados
├─────────┼──────┤ (variáveis estáticas)
│ D231H │ 2FH │
└─────────┴──────┘
Podemos ler o conteúdo armazenado dinamicamente. Veja o exemplo a seguir.
var p : ^integer;
begin
new(p);
p^ := 4;
writeln('Valor em p: ', p^);
end.
Saída:
Valor em p: 4
Obtendo o endereço de variáveis estáticas ou ponteiros
Podemos também obter o endereço no qual uma variável estática ou um ponteiro está localizado, através do função addr(). Veja o programa a seguir.
var i : integer;
p : ^integer;
begin
writeln('Endereco da variavel i: ', addr(i));
writeln('Endereco do ponteiro p: ', addr(p));
end.
Saída:
Endereco da variavel i: -11720
Endereco do ponteiro p: -11722
Que equivalem aos valores em hexadecimal &HD238 e &HD236, respectivamente.
┌─────────┬──────┐
│ Memória │ Dado │
├─────────┼──────┤
│ xxxx │ xx │ Programa
├─────────┼──────┤
│ xxxxx │ xx │ Heap
├─────────┼──────┤ (variáveis dinâmicas)
│ ..... │ .. │
├─────────┼──────┤
p │ D236H │ xx │ Área de dados
├─────────┼──────┤ (variáveis estáticas)
│ D237H │ xx │
├─────────┼──────┤
i │ D238H │ xx │
├─────────┼──────┤
│ D239H │ xx │
└─────────┴──────┘
Obs: o comando addr() retorna um ponteiro (e não um valor) no Free Pascal do PC.
Atribuindo um endereço a um ponteiro
O comando prt() converte um valor inteiro de endereço de memória para um ponteiro. Veja o exemplo a seguir.
var i, e : integer;
p : ^integer;
begin
i := 5;
e := addr(i);
p := ptr(e);
writeln('Endereço da variavel i: ', e);
writeln('Valor de endereço apontado por p: ', p^);
end.
Saída:
Endereço da variável i: -11720
Valor de endereço apontado por p: 5
┌─────────┬──────┐
│ Memória │ Dado │
├─────────┼──────┤
│ xxxx │ xx │ Programa
├─────────┼──────┤
│ xxxxx │ xx │ Heap
├─────────┼──────┤ (variáveis dinâmicas)
│ ..... │ .. │
├─────────┼──────┤
+-- p │ D234H │ 38H │ Área de dados
| ├─────────┼──────┤ (variáveis estáticas)
| │ D235H │ D2H │
| ├─────────┼──────┤
| e │ D236H │ 38H │
| ├─────────┼──────┤
| │ D237H │ D2H │
| ├─────────┼──────┤
+-> i │ D238H │ 05H │
├─────────┼──────┤
│ D231H │ 00H │
└─────────┴──────┘
Lendo o endereço contido em um ponteiro
O comando ord() lê o endereço armazenado em um ponteiro "p". Veja o exemplo a seguir.
var i : integer;
p : ^integer;
begin
p := ptr(addr(i)); { p aponta para i }
writeln('Endereco de i: ', addr(i));
writeln('Endereco apontado por p: ', ord(p));
end.
Saída:
Endereço de i: -11720
Endereço apontado por p: -11720
Lendo ponteiros de tipos diferentes
Podemos também utilizar um ponteiro de um determinado tipo para apontar para uma variável de outro tipo.
No programa a seguir, desejamos ler o conteúdo de memória de uma variável estática do tipo "integer" byte a byte. Para isso, será utilizado um ponteiro do tipo "byte".
var n, i, e : integer;
p : ^byte;
begin
n := 10;
e := addr(n);
writeln('Valores dos bytes armazenados na memoria para a variavel n:');
for i:=0 to 1 do
begin
p := ptr(e);
writeln('Posicao ', i, ' - ', p^);
e:= e + 1;
end;
end.
Saída:
Valores dos bytes armazenados na memoria para a variavel n:
Posicao 0 - 10
Posicao 1 - 0
O conteúdo da variável "n" em memória é: 10 00 (sistema little endian, onde a ordem dos números de 16 bits são invertidos na memória. Assim, o normal fica 00 10).
O programa a seguir analisa o conteúdo de memória onde a variável do tipo string[10] armazena os dados.
var i, e : integer;
p : ^byte;
nome : string[10];
begin
nome := 'Poliana';
e := addr(nome);
writeln('Valores dos bytes armazenados na memoria para a variavel num:');
for i:=0 to 9 do
begin
p := ptr(e);
write('Posicao ', i, ' - ', p^, ' - ');
if (p^ > 13) then writeln(chr(p^)) else writeln;
e := e + 1;
end;
end.
Saída:
Posicao 0 - 7 -
Posicao 1 - 80 - P
Posicao 2 - 111 - o
Posicao 3 - 108 - l
Posicao 4 - 105 - i
Posicao 5 - 97 - a
Posicao 6 - 110 - n
Posicao 7 - 97 - a
Posicao 8 - 0 -
Posicao 9 - 0 -
Notas:
- Ao lado do valor de cada byte, está o código ASCII correspondente.
- Repare na posição 0 de memória: ela contém o comprimento da string, que é 7.
- O conteúdo de string não utilizado é marcado com o valor 0 (endereços 8 e 9).
O comando em Pascal "length(string)" retorna o comprimento de uma string. Ele conta somente os caracteres válidos, ignorando a parte valorada como 0. Ex:
tam := length(nome);
Referência perdida
Como podemos dar o comando new() para alocar memória várias vezes, temos que tomar cuidado com o seguinte problema: ao ser dado um novo comando new(), uma nova área de memória é alocada, o endereço do ponteiro p é alterado e o endereço anterior é perdido. Veja o exemplo a seguir.
var p : ^integer;
begin
new(p);
Endereço: | 2F32 2F33 2F34 2F35 2F36 ... |
Dado : | xxxx xxxx xxxx xxxx xxxx ... |
p
p^ := 3;
Endereço: | 2F32 2F33 2F34 2F35 2F36 ... |
Dado : | 03 00 xxxx xxxx xxxx ... |
p
new(p);
Endereço: | 2F32 2F33 2F34 2F35 2F36 ... |
Dado : | 03 00 xxxx xxxx xxxx ... |
p
end.
Conforme pode ser observado no diagrama anterior, quando damos o segundo comando "new", a referência ao endereço &H2F32 é perdida, uma vez que o ponteiro "p" passa a apontar para o endereço &H2F34. Se desássemos recuperar o primeiro dado armazenado, não teríamos mais acesso a ele.
Para resolver essa situação, devemos criar uma outra variável do tipo "ponteiro" para armazenar o primeiro endereço.
var : p, q : ^integer;
begin
new(p);
q := p; { Salva endereço }
new(p);
end.
Assim teríamos:
Endereço: | 2F32 2F33 2F34 2F35 2F36 ... |
Dado : | 03 00 xxxx xxxx xxxx ... |
q p
Desalocando a memória
O mecanismo de variáveis dinâmicas permite desalocar memória, ou seja, liberar espaço que não será mais utilizado. Dessa forma, podemos dispor de mais espaço de memória para o uso.
O comando dispose() libera a memória alocada por new(), ou seja, libera o espaço de memória apontado pelo ponteiro "p". Exemplo:
var : p : ^integer;
begin
new(p);
dispose(p); { Descarta posição de memória atual }
end.
Diagrama:
new(p);
Endereço: | 2F32 2F33 2F34 2F35 2F36 ... |
Dado : | xxxx xxxx xxxx xxxx xxxx ... |
p
dispose(p);
Endereço: | 2F32 2F33 2F34 2F35 2F36 ... |
Dado : | xxxx xxxx xxxx xxxx xxxx ... |
Ponteiros como parâmetros de funções e procedimentos
Não é possível declarar diretamente uma variável do tipo ponteiro na lista de parâmetros de uma função/procedimento. Ex:
procedure recebe_ptr(p : ^integer);
Ao compilarmos o código acima, geraria um erro.
Entretanto, é possível passar ponteiros como parâmetro. Para isso, deve-se criar um tipo de variável ponteiro. Ex:
type PInt = ^integer;
procedure recebe_ptr(p : PInt);
Podemos reescrever o programa da seção de alocação de memória, de forma a receber qualquer ponteiro.
type PInt = ^integer;
var p, q : PInt;
procedure testa_ptr(p : PInt);
begin
if p = nil then
writeln('Ponteiro nulo.')
else
writeln('Ponteiro referenciado.');
end;
begin
p := nil;
q := nil;
testa_ptr(p);
new(p);
testa_ptr(p);
testa_ptr(q);
end.
Saída:
Ponteiro nulo.
Ponteiro referenciado.
Ponteiro nulo.
Criação de listas dinâmicas - introdução
Conforme observado nesses últimos exemplos, uma variável dinâmica é capaz de alocar e desalocar diversos espaços na memória, diferentemente da variável estática, que somente aloca o seu espaço. Esses recursos da variável dinâmica são úteis para a criação de listas dinâmicas. Veja o exemplo a seguir.
var p : ^integer;
i : integer;
begin
for i:=1 to 4 do
begin
new(p);
end;
end.
O programa acima irá reservar quatro áreas na memória do tamanho de "integer", que ser utilizado para armazenar quatro números (lista).
+---+ +---+ +---+ +---+
| | | | | | | |
| | | | | | | |
+---+ +---+ +---+ +---+
↑
p
Os espaços reservados em memória são representadas pelas caixinhas, e a ordem de introdução é da esquerda para a direita.
Visto que o programa criou quatro "variáveis" do tipo inteiro, cada uma delas é um elemento de uma lista. Entretanto, observa-se que a lista criada possui elementos não referenciados (ou perdidos na memória). Assim, não podemos acessar todos os elementos, mas somente o último elemento, que é referenciado pelo ponteiro "p".
O truque para contornar esse problema é adicionar a cada elmento da lista um ponteiro, referenciando o próximo elemento.
Na seção seguinte, veremos como criar e gerenciar listas dinâmicas.
2. Listas Encadeadas (ou Dinâmicas)
Foi apresentado até agora uma maneira de armazenar múltiplos dados - em uma lista estática ou vetor. As principais características de um vetor são:
- A lista possui tamanho fixo.
- Os elementos estão dispostos na memória em posições contíguas.
- O acesso a cada item da lista é de maneira direta.
- A inserção ou remoção de itens da lista pode acarretar em deslocamento nos itens restantes.
Existe também a possibilidade de criar uma lista dinâmica, chamada também de lista encadeada. As principais características de uma lista encadeada são:
- A lista possui tamanho variável.
- Os elementos estão dispostos na memória em posições dispersas.
- É necessário conhecer a posição de cada elemento na memória.
- Para acessar cada item da lista, deve-se percorrer a lista até atingir a posição desejada.
- A inserção ou remoção de itens da lista é direta e não afeta os demais itens.
Uma lista do tipo encadeada cria seus elementos um a um, conforme a necessidade. Além disso, cada elemento é criado em uma posição aleatória na memória. Assim, torna-se necessário registrar de alguma forma a localização de cada item da lista.
No caso dos vetores, é necessário somente conhecer a localização do inicio da lista, pois os dados estão localizados de forma sequencial. No caso da lista encadeada, a solução adotada para registrar a localização dos elementos da lista é adicionar a cada elemento o endereço do elemento subjacente.
0 1 2 3 4
┌──┬──┬──┬──┬──┐
Vetor │ │ │ │ │ │ Localização de v[2] = e+2
└──┴──┴──┴──┴──┘
e
┌──┐ ┌──┐ ┌──┐ ┌──┐
Lista │ │ │ │ │ │ │ │
└──┘-->└──┘-->└──┘-->└──┘--x
Como teremos que armazenar dois tipos de dado diferentes em cada elemento da lista encadeada, teremos que criar um novo tipo para isso.
Supondo um lista encadeada de inteiros, fazemos:
type
elemento = record
valor : integer;
prox : ^elemento; { Erro }
end;
O código acima não funciona, pois é necessário criar um tipo para referenciar o elemento.
Assim, temos:
type
p_elemento = ^elemento;
elemento = record
valor : integer;
prox : p_elemento;
end;
A estrutura criada fica:
Elemento
┌────────┐
│ Valor │
│ │
├────────┤
│ prox │
└────────┘
No capítulo de tipos, vimos uma variável composta chamada varficha, que é uma ficha que armazena dados. Vimos também que esta variável podia ser armazenada em um vetor. Agora, vamos criar uma lista encadeada do tipo "ficha", para ilustrar o funcionamento de listas dinâmicas.
Os passos necessários são:
- Criar tipo "ficha".
- Criar tipo ponteiro para ficha.
- Criar variável do tipo ponteiro para ficha.
- Criar uma ficha na memória.
- Guardamos o endereço dela.
- Criamos uma nova ficha.
- Apontar o elemento atual para o anterior.
Passos 1 e 2: criar tipo "ficha" e criar tipo ponteiro para ficha.
type
p_varficha = ^varficha; { ponteiro para varficha }
varficha = record
nome : string[40];
idade : integer;
peso : real;
prox : p_varficha;
end;
Passo 3: criar variável do tipo ponteiro para ficha.
var p, q : p_varficha;
Nota: p_varficha somente define um tipo, ou seja, não armazena qualquer valor. Dessa forma, temos que criar variáveis para armazenar o endereço de cada elemento a ser criado pelo comando new.
Passo 4: criar uma ficha na memória.
new(p);
Passo 5: guardar o endereço da ficha criada.
q := p;
Passo 6: criar uma nova ficha na memória.
new(p);
Passo 7: apontar o elemento atual para o anterior.
p^.prox := q;
Abaixo é ilustrada a seqüência de criação na memória, a partir do passo 4.
Observa-se que a lista criada é uma lista invertida, onde os "últimos serão os primeiros".
Os elementos de um tipo são acessados da seguinte forma:
variavel.elemento
No capítulo anterior, criamos a variável estática "ficha" e o acesso a cada elemento era feito da seguinte maneira:
var ficha : varficha;
ficha.nome
ficha.idade
ficha.peso;
No caso da variável criada dinamicamente, utilizamos o ponteiro que a referencia para acessar os elementos. Exemplo:
var p : ^varficha;
p^.nome;
p^.idade;
p^.peso;
No exemplo anterior, o ponteiro "p" referencia a primeira ficha criada, enquanto que o ponteiro "q" referencia a segunda. Assim, podemos acessar qualquer uma das fichas.
Visto isso, podemos inverter a lista, fazendo com que o primeiro elemento referencie o segundo.
Substituir no passo 7 a linha:
p^.prox := q;
por
q^.prox := p;
Com isso, o sentido das setas na ilustração é invertido.
Caso o segundo elemento da lista seja o último, devemos sinalizar isso, fazendo com que ele aponte para "NIL".
p^.prox := nil;
Dessa forma, quando percorrermos a lista e encontrarmos um elemento apontando para "NIL", sabemos que se trata do último elemento.
LISTAS SIMPLESMENTE ENCADEADAS
São listas em que cada elemento contém referência somente a um elemento subjacente.
LISTAS DUPLAMENTE ENCADEADAS
São listas que cada elemento contém o endereço do elemento subjacente anterior e posterior.
Vejamos agora um exemplo completo de criação de listas encadeadas.
type
p_varficha = ^varficha;
varficha = record
nome : string[40];
idade : integer;
peso : real;
prox : p_varficha;
end;
var p,q : p_varficha;
i : integer;
begin
q := nil;
for i:=1 to 10 do
begin
new(p);
write('Nome: ');
readln(p^.nome);
write('Idade: ');
readln(p^.idade);
write('Peso: ');
readln(p^.peso);
if (q=nil) then
p^.prox:=nil
else
p^.prox:=q;
q:=p;
end;
end.
Este programa cria uma lista simplesmente encadeada com 10 fichas. A primeira ficha aponta para NIL, a segunda para a primeira, e assim por diante.
Se desejarmos uma lista duplamente encadeada, fazemos:
type
p_varficha = ^varficha;
varficha = record
nome : string[40];
idade : integer;
peso : real;
prox : p_varficha;
ant : p_varficha; { novo }
end;
var p,q : p_varficha;
i : integer;
begin
q:=nil;
for i:=1 to 10 do
begin
new(p);
write('Nome: ');
readln(p^.nome);
write('Idade: ');
readln(p^.idade);
write('Peso: ');
readln(p^.peso);
if (q=nil) then
p^.prox:=nil
else
begin { novo }
p^.prox:=q;
q^.ant:=p; { novo }
end; { novo }
q:=p;
if (i=10) then { novo }
p^.ant:=nil; { novo - Última ficha criada }
end;
end.
Vamos ver no esquema abaixo, o que a dupla associação faz:
Obs: conforme dito anteriormente, o número de elementos aqui é livre (até onde a memória permitir, é claro!). Observe no programa anterior que, cada elemento é criado dinamicamente (função new).
REMOÇÃO DE ELEMENTOS
É possível remover elmentos da lista. Para apagar um elemento, utiliza-se a função dispose(ponteiro).
Aqui está a simplicidade em relação aos vetores. Em vez de deslocar os elementos na lista, basta indicar aos elementos anterior e posterior ao elemento atual que será removido os novos endereços.
Passos para remover um elemento na posição i:
- Indicar ao elemento da posição i-1 o novo endereço de próximo, que é i+1, em vez de i.
- Indicar ao elemento da posição i+1 o novo endereço de anterior, que é i-1, em vez de i.
- Apagar o elemento na posição i.
Procedimento para remover um elemento:
procedure remove_no(p : p_varficha);
var ant, prox : p_varficha;
begin
ant := p^.ant;
prox := p^.prox;
ant^.prox := prox;
prox^.ant := ant;
dispose(p);
end;
Obs: É necessário fazer a verificação se um elemento é o primeiro ou o último da lista. Assim, o código fica:
procedure remove_no(p : p_varficha);
var ant, prox : p_varficha;
begin
ant := p^.ant;
prox := p^.prox;
if (ant <> nil) then ant^.prox := prox;
if (prox <> nil) prox^.ant := ant;
dispose(p);
end;
A seguir um programa completo que exibe a lista completa e também remove um elemento da lista.
type
p_varficha = ^varficha;
varficha = record
nome : string[40];
idade : integer;
peso : real;
prox : p_varficha;
ant : p_varficha;
end;
var p, q, prim : p_varficha;
i, tam_lista : integer;
procedure lista_nos;
var i : integer;
pos : p_varficha;
begin
pos := prim;
for i:=1 to tam_lista do
begin
writeln('Pessoa ', i);
writeln(' Nome: ', pos^.nome);
writeln(' Idade: ', pos^.idade);
writeln(' Peso: ', pos^.peso:3:2);
writeln;
pos := pos^.prox;
end;
end;
procedure remove_no(p : p_varficha);
var ant, prox : p_varficha;
begin
ant := p^.ant;
prox := p^.prox;
if (ant <> nil) then ant^.prox := prox;
if (prox <> nil) then prox^.ant := ant;
dispose(p);
tam_lista := tam_lista - 1;
end;
begin
q:=nil;
for i:=1 to 3 do
begin
new(p);
write('Nome: ');
readln(p^.nome);
write('Idade: ');
readln(p^.idade);
write('Peso: ');
readln(p^.peso);
if (q=nil) then
p^.prox:=nil
else
begin
p^.prox:=q;
q^.ant:=p;
end;
q:=p;
if (i=10) then
p^.ant:=nil;
end;
prim := p;
tam_lista := 3;
lista_nos;
remove_no(prim^.prox); { remove o segundo elemento }
lista_nos;
end.
Saída:
Nome: Pedro
Idade: 21
Peso: 68
Nome: Fatima
Idade: 23
Peso: 55
Nome: Gilda
Idade: 22
Peso: 56
Pessoa 1
Nome: Gilda
Idade: 22
Peso: 56.00
Pessoa 2
Nome: Fatima
Idade: 23
Peso: 55.00
Pessoa 3
Nome: Pedro
Idade: 21
Peso: 68.00
Pessoa 1
Nome: Gilda
Idade: 22
Peso: 56.00
Pessoa 2
Nome: Pedro
Idade: 21
Peso: 68.00
INSERÇÃO DE ELEMENTOS
Para inserir um novo elemento no vetor, o procedimento é similar ao da remoção. Note que não existe posição fixa em uma lista encadeada. Por exemplo, para inserir um novo elemento entre a posição 2 e 3, deve-se fazer:
- Criar o elmento novo: new(p).
- Indicar ao ponteiro de próximo do elemento 2 o endereço desse novo elemento.
- Indicar ao ponteiro de anterior do elemento 3 o endereço desse novo elemento.
- Notificar ao elemento novo os elementos anteriores e posteriores.
Graficamente:
O código de inserção é o seguinte:
procedure insere_no(p : p_varficha);
var ant, q : p_varficha;
begin
ant := p^.ant;
q := cria_no;
if (ant <> nil) then ant^.prox := q;
p^.ant := q;
if (ant <> nil) then q^.ant := ant else q^.ant := nil;
q^.prox := p;
tam_lista := tam_lista + 1;
end;
Vamos incorporar essas mudanças ao código de remoção apresentado.
Na execução, foram inseridos 3 nomes (Pedro, Fatima e Gilda), removida a Fatima e acrescentado o Paulo entre o primeiro e o segundo elemento.
type
p_varficha = ^varficha;
varficha = record
nome : string[40];
idade : integer;
peso : real;
prox : p_varficha;
ant : p_varficha;
end;
var p, q, prim : p_varficha;
i, tam_lista : integer;
procedure lista_nos;
var i : integer;
pos : p_varficha;
begin
pos := prim;
for i:=1 to tam_lista do
begin
writeln('Pessoa ', i);
writeln(' Nome: ', pos^.nome);
writeln(' Idade: ', pos^.idade);
writeln(' Peso: ', pos^.peso:3:2);
writeln;
pos := pos^.prox;
end;
end;
function cria_no : p_varficha;
var p : p_varficha;
begin
new(p);
write('Nome: ');
readln(p^.nome);
write('Idade: ');
readln(p^.idade);
write('Peso: ');
readln(p^.peso);
cria_no := p;
end;
procedure remove_no(p : p_varficha);
var ant, prox : p_varficha;
begin
ant := p^.ant;
prox := p^.prox;
if (ant <> nil) then ant^.prox := prox;
if (prox <> nil) then prox^.ant := ant;
dispose(p);
tam_lista := tam_lista - 1;
end;
procedure insere_no(p : p_varficha);
var ant, q : p_varficha;
begin
ant := p^.ant;
q := cria_no;
if (ant <> nil) then ant^.prox := q;
p^.ant := q;
if (ant <> nil) then q^.ant := ant else q^.ant := nil;
q^.prox := p;
tam_lista := tam_lista + 1;
end;
begin
q:=nil;
for i:=1 to 3 do
begin
p := cria_no;
if (q=nil) then
p^.prox:=nil
else
begin
p^.prox:=q;
q^.ant:=p;
end;
q:=p;
if (i=10) then
p^.ant:=nil;
end;
prim := p;
tam_lista := 3;
writeln;
writeln('Lista de nomes:');
lista_nos;
writeln('Remove um elemento:');
remove_no(prim^.prox);
writeln('Lista de nomes:');
lista_nos;
writeln('Insere novo elemento:');
insere_no(prim^.prox);
writeln;
writeln('Lista de nomes:');
lista_nos;
end.
Saída:
Nome: Pedro
Idade: 21
Peso: 68
Nome: Fatima
Idade: 23
Peso: 55
Nome: Gilda
Idade: 22
Peso: 56
Lista de nomes:
Pessoa 1
Nome: Gilda
Idade: 22
Peso: 56.00
Pessoa 2
Nome: Fatima
Idade: 23
Peso: 55.00
Pessoa 3
Nome: Pedro
Idade: 21
Peso: 68.00
Remove um elemento:
Lista de nomes:
Pessoa 1
Nome: Gilda
Idade: 22
Peso: 56.00
Pessoa 2
Nome: Pedro
Idade: 21
Peso: 68.00
Insere novo elemento:
Nome: Paulo
Idade: 20
Peso: 64
Lista de nomes:
Pessoa 1
Nome: Gilda
Idade: 22
Peso: 56.00
Pessoa 2
Nome: Paulo
Idade: 20
Peso: 64.00
Pessoa 3
Nome: Pedro
Idade: 21
Peso: 68.00