Curso de C
Ponteiros
Você está em: MarMSX >> Cursos >> C
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, ocupando o número de bytes correspondente ao tipo de dado que ela foi definida. Além disso, somos obrigados a declarar todas as variáveis que desejamos utilizar no programa antes de compilar e executar. Mas, se eu necessitar de novas variáveis, novos vetores ou vetores maiores? Isso é possível em tempo de execução do programa?
As varáveis que foram apresentadas até o presente momento são do tipo estáticas. Entretanto, as variáveis em C (e também em outras linguagens de programação) podem ser de dois tipos: estáticas e dinâmicas.
Uma variável do tipo estática é uma variável que possui um nome fixo 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.
O principal objetivo de variáveis dinâmicas é a criação ou destruição de dados na memória do computador em tempo de execução do programa, conforme a necessidade dele. Com isso, podemos criar novas variáveis e aumentar o tamanho de vetores durante a execução do programa.
Uma variável do tipo ponteiro tem como finalidade permitir a navegação pela memória do computador, lendo ou modificando dados. Nas variáveis dinâmicas, o dado é criado na memória de forma "solta", ou seja, sem necessariamente haver um nome de variável fixo para aquele dado. Dessa forma, é necessário a utilização de ponteiros para gerenciar os dados criados dinamicamente, sob pena de deixá-lo "perdido" na memória.
Em resumo, a alocação de memória cria dados dinamicamente na memória, enquanto o ponteiro é utilizado para ter acesso a esses dados e manipulá-los.
Ponteiros
Um ponteiro é uma variável que armazena um endereço de memória de um dado, para que seja possível referenciá-lo quando necessário. Além disso, ele define como interpretar o dado que está armazenado a partir daquele endereço.
Observe a ilustração abaixo:
┌─────────┬──────┐
│ Memória │ Dado │
├─────────┼──────┤
p → │ 1000H │ 05H │ i
├─────────┼──────┤
│ 1001H │ 13H │
└─────────┴──────┘
De acordo com a ilustração acima, temos:
- O dado com valor igual a &H05 está armazenado no endereço de memória igual a &H1000.
- O dado com valor igual a &H13 está armazenado na posição &H1001.
- A variável inteira de 8 bits "i" é do tipo estática e contém o valor &H05 (i=5). Assim, "i" contém o "valor_do_dado".
- A variável "p" é do tipo ponteiro e contém o valor &H1000, ou seja, "p" aponta para a posição &H1000. Assim, "p" contém o "endereco_do_dado".
Na ilustração a seguir, podemos observar como o ponteiro "p" é armanezado na memória.
┌─────────┬──────┐
│ Memória │ Dado │
├─────────┼──────┤
│ 2000H │ 00H │ p
├─────────┼──────┤
│ 2001H │ 10H │
└─────────┴──────┘
O ponteiro "p", que armazena um endereço de memória, é de 2 bits (no MSX) e contém como dado o endereço &H1000, obtido através da composição dos valores de memória &H2000 e &H2001, posições estas que variam de acordo com o funcionamento do programa.
O mapeamento completo de "p" para o dado pode ser visto na ilustração a seguir.
┌─────────┬──────┐ ┌─────────┬──────┐
│ Memória │ Dado │ │ Memória │ Dado │
├─────────┼──────┤ ├─────────┼──────┤
p │ 2000H │ 00H │------> │ 1000H │ 05H │
├─────────┼──────┤ ├─────────┼──────┤
│ 2001H │ 10H │ │ 1001H │ 13H │
└─────────┴──────┘ └─────────┴──────┘
Diferente da variável estática "i" do exemplo, que estará sempre apontada para a posição &H1000, o ponteiro "p" poderá ter seu valor alterado e passar a "apontar" para outras posições de memória. Isto nos permite "navegar" pela memória do computador. No exemplo a seguir, o ponteiro passa a apontar para a posição &H1001.
┌─────────┬──────┐
│ Memória │ Dado │
├─────────┼──────┤
│ 1000H │ 05H │ i
├─────────┼──────┤
p → │ 1001H │ 13H │
└─────────┴──────┘
Declaração do ponteiro
A declaração de uma variável do tipo estática é feita utilizando-se o tipo de dado, seguido do nome da variável. Ex:
int i;
"i" é uma variável "int" do tipo estática.
A declaração de uma variável do tipo ponteiro é feita de maneira semelhante. Devemos apenas acrescentar o sinal de asterisco "*" antes do nome da variável.
Exemplo:
int *p;
"p" é um ponteiro que referencia um dado do tipo "int".
A delcaração de um ponteiro também define o tipo de dado que ele está referenciando, ou seja, como o programa irá interpretar os dados a partir daquele endereço. Um código ASCII? Um valor inteiro? Um ponto flutuante?
Por exemplo, um ponteiro do tipo "int" referencia um valor inteiro, onde são relevantes os dois bytes consecutivos a partir do ponteiro. Um ponteiro do tipo "float" trata os dados como um número real e são relevantes os quatro próximos bytes.
int *p; float *q;
┌─────────┬──────┐ ┌─────────┬──────┐
│ Memória │ Dado │ │ Memória │ Dado │
├─────────┼──────┤ ├─────────┼──────┤
p → │ 1000H │ │ q → │ 1000H │ │
├─────────┼──────┤ ├─────────┼──────┤
│ 1001H │ │ │ 1001H │ │
└─────────┴──────┘ ├─────────┼──────┤
│ 1002H │ │
├─────────┼──────┤
│ 1003H │ │
└─────────┴──────┘
Mãos à obra !
Vejamos agora como reproduzir em C o exemplo da primeira figura da página.
#include <stdio.h>
main()
{
short int i=5;
short int *p;
p = &i;
printf("Valor de i: %d\n",i);
printf("Valor de p: %x\n",p);
}
Saída:
Valor de i: 5
Valor de p: 1000
Quando "p" é criado no programa acima, ele contém um valor aleatório de memória (nas linguagens mais modernas, é iniciado com o valor 0). Dessa forma, devemos criar uma refeerência de "p" para "i" no nosso programa.
Para podermos referenciar o endereço de memória onde a variável "i" armazena o valor 5, devemos retornar o endereço de memória de "i" e não o seu valor. Fazemos isso utilizando o operador "&" antes do nome da variável. Assim, "&i" retorna &H1000 em vez de 5.
Concluímos que os comandos abaixo:
...
printf("Valor de p: %x\n",p);
printf("Valor de &i: %x\n",&i);
...
são equivalentes e imprimirão o mesmo resultado, ou seja, 1000.
Nos C's mais antigos, quando não atribuímos qualquer valor a uma variável, o valor inicial dela é aleatório. Ex:
int i;
printf("Valor de i: %d\n",i);
Saída:
Valor de i: 28816
Com o ponteiro, acontece a mesma coisa. Ele contém um valor inicial de um endereço qualquer.
No exemplo acima, o ponteiro "p" recebeu o endereço de memória da variável "i". Se não tivéssemos feito isso, "p" estaria apontando para qualquer outra posição de memória.
É possível ler o valor do dado apontado pelo pelo ponteiro "p"?
Sim. O símbolo "*" é utilizado juntamente com o ponteiro para ler o conteúdo do endereço referenciado.
O tipo de dado lido nessa operação é aquele no qual o ponteiro foi definido. Nesse caso, ele retorna um "short int". Assim:
...
printf("Valor de i: %d\n",i);
printf("Valor de *p: %d\n",*p);
...
são equivalentes e imprimirão o mesmo resultado, ou seja, 5.
Relembrando:
- "&" recebe o endereço de memória de uma variável estática.
- "*" recebe o conteúdo da memória apontada por um ponteiro, de acordo com o tipo de dado definido para o ponteiro.
Ponteiros para tipos diferentes
Podemos referenciar outros tipos de dados diferentes do tipo do ponteiro criado, porém os dados serão interpretados como o declarado no ponteiro. Por exemplo, podemos utilizar um ponteiro do tipo char para referenciar uma variável do tipo int. Nesse caso, o ponteiro interpreta o dado como sendo char e não int.
Devemos utilizar o recurso de casting para converter tipos nesse caso. Veja o exemplo a seguir.
#include <stdio.h>
#include <stdlib.h>
main()
{
int i=4;
unsigned char *p;
p = (unsigned char *)&i; /* Casting - conversão entre tipos diferentes */
}
Graficamente:
┌─────────┬──────┐
│ Memória │ Dado │
───├─────────┼──────┤─────
│ 17CCH │ 04H │ ← p
i ├─────────┼──────┤─────
│ 17CDH │ 00H │
───├─────────┼──────┤
│ 17CEH │ │
└─────────┴──────┘
A variável "i' ocupa 2 bytes, enquanto que a variável "p" referencia 1 byte.
Este recurso é interessante para ler byte a byte o conteúdo de qualquer tipo de variável.
Deslocando os ponteiros
É possível deslocar os ponteiros na memória, utilizando-se os operadores soma "+" e subtração "-". Veja o exemplo a seguir:
short int *p, *q, *r;
q = p+2;
r = p-1;
Graficamente:
┌─────────┬──────┐
│ Memória │ Dado │
├─────────┼──────┤
│ 2345H │ │ ← r
├─────────┼──────┤
│ 2346H │ │ ← p
├─────────┼──────┤
│ 2347H │ │
├─────────┼──────┤
│ 2348H │ │ ← q
└─────────┴──────┘
A quantidade de bytes deslocada pelo ponteiro na memória depende do tipo de dados definido para ele. Veja o exemplo a seguir.
#include <stdio.h>
main()
{
int i;
float *p;
for (i=0; i<3; i++)
printf("Posição atual: %x\n", p+i);
}
Saída:
Posição atual: 3340
Posição atual: 3344
Posição atual: 3348
Uma variável do tipo float possui 4 bytes. Dessa forma, o deslocamento de um ponteiro do tipo float é de 4 em 4 bytes.
Foi visto que para a leitura de dados na memória a partir de um ponteiro, é necessário o operador "*". Quando utilizamos o deslocamento, devemos utilizar parêntesis para discriminar a operação de deslocamento do asterisco:
int *p, val;
val = *(p + deslocamento)
Vejamos porque:
- A expressão *(p+1) difere da expressão *p+1.
- A primeira obtém o conteúdo de memória apontado por "p+1".
- A segunda obtém o conteúdo de memória apontado por "p" e soma mais 1.
Veja o exemplo a seguir.
┌─────────┬──────┐
│ Memória │ Dado │
├─────────┼──────┤
│ 2345H │ 01H │ ← p
├─────────┼──────┤
│ 2346H │ 04H │
├─────────┼──────┤
│ 2347H │ 06H │
├─────────┼──────┤
│ 2348H │ 08H │
└─────────┴──────┘
Valor de *(p+1) é igual a 4
Valor de *p+1 é igual a 1 + 1 = 2
Visto isso, podemos ver o exemplo a seguir, que irá navegar pelos caracteres de uma string utilizando os operadores sobre o ponteiro.
#include <stdio.h>
#include <string.h>
main()
{
int i;
char nome[6];
unsigned char *p;
p = (unsigned char *) &nome;
strcpy(nome, "Bianca");
for (i=0; i<7; i++)
printf("%04x - %02x - %c\n", p+i, (short int) *(p+i), *(p+i));
}
Saída:
D5EF - 42 - B
D5F0 - 69 - i
D5F1 - 61 - a
D5F2 - 6E - n
D5F3 - 63 - c
D5F4 - 61 - a
D5F5 - 00 -
O ponteiro "p" recebe o endereço do primeiro caractere da string. Em seguida, a operação "p+i" vai deslocando ponteiro pela string. Observe que o valor "00" marca o fim da string.
Podemos facilitar as coisas! O deslocamento de ponteiro pode ser feito também através dos colchetes. Veja o exemplo a seguir.
#include <stdio.h>
main()
{
int v[4] = {1, 2, 3, 4};
int *p = (int *)&v, i;
for (i=0; i<4; i++)
printf("%d\n", p[i]);
}
Saída:
1
2
3
4
O conceito de ponteiro foi necessário para compreender a criação, uso e destruição de variáveis dinâmicas, que será abordado na seção seguinte.
Alocação de memória
A criação de variáveis dinâmicas é feita através da alocação dinâmica de memória. As funções malloc, calloc e realloc são utilizadas para isso, que sempre irão retornar o endereço inicial da memória onde o dado foi criado para um ponteiro.
A localização dos dados alocados é aleatória, e é feita automaticamente pelo sistema operacional em tempo de execução do programa.
Sintaxes:
ponteiro = malloc(tamanho_do_vetor * tamanho_da_variavel);
ponteiro = calloc(tamanho_do_vetor, tamanho_da_variavel);
ponteiro = realloc(ponteiro_antigo, tamanho_do_vetor * tamanho_da_variavel);
Conforme ja foi dito, a variável dinâmica não possui qualquer nome que a referencie. Assim, quando são criadas, devemos utilizar ponteiros para armazenar sua localização na memória. Exemplo:
short int *p;
p = (shot int *) malloc(1);
Nesse exemplo, uma variável com o tamanho de um byte é criada, e sua localização é armazenada no ponteiro "p" do tipo "short int".
Será chamado de "célula" o bloco consecutivo de bytes que armazena o conteúdo de um determinado tipo de variável.
É possível alocar apenas uma célula de informação, que será a variável dinâmica, ou um conjunto de células em posições contíguas de memória, que será o vetor dinâmico.
Nas listas encadeadas (mais adiante), são alocadas células individuais para compor uma lista, conforme a necessidade. Nesse caso, elas estarão em posições aleatórias de memória.
O tamanho do espaço alocado depende do produto do tamanho do dado pelo o número total de células do vetor.
tamanho_do_vetor x tamanho_da_variavel
Por exemplo, cada célula de um dado do tipo "short int" necessita de 1 byte na memória. Já o "int" necessita de 2 bytes. Assim, um vetor com 10 posições de "int" terá 10x2 ou 20 bytes alocados.
Alocação de variáveis
Assim como a variável comum, armazena somente 1 informação para um determinado tipo de dado.
Exemplo de uso do malloc para uma variável do tipo "int":
int *p;
p = (int *) malloc(2);
Aloca 2 bytes para uma variável inteira, devolvendo a referência de memória para o ponteiro "p".
Devemos utilizar a função sizeof() para calcular o tamanho de bytes a serem alocados, de acordo com o tipo de variável que desejamos utilizar. Ex:
p = (int *) malloc(sizeof(int));
Obs: é necessário fazer o casting para o tipo de ponteiro declarado. No exemplo anterior, é a expressão: "(int *)".
Graficamente:
┌─────────┬──────┐
│ Memória │ Dado │
├─────────┼──────┤
│ 153FH │ 00H │ ← p
├─────────┼──────┤
│ 1540H │ 00H │
└─────────┴──────┘
A diferença entre malloc e calloc é que calloc atribui a todos os bytes o valor igual a zero.
Já a função realloc aloca uma nova área de memória, reajustando o tamanho do vetor antigo. Ele copia os dados.
Obs: as funções malloc, calloc e realloc necessitam da biblioteca "stdlib.h" do C.
No exemplo a seguir, serão alocadas na memória duas células do tipo int, uma utilizando o malloc e outra o calloc.
#include <stdio.h>
#include <stdlib.h> /* Necessário para o malloc, calloc e realloc */
main()
{
int *p;
p = (int *) malloc(1 * sizeof(int));
printf("Valor do conteúdo de p: %d\n", *p);
printf("Posição de p: %x\n", *p);
p = (int *) calloc(1, sizeof(int));
printf("Valor do conteúdo de p: %d\n", *p);
printf("Posição de p: %x\n", *p);
}
Saída:
Valor do conteúdo de p: 0
Posição de p: 17CC
Valor do conteúdo de p: 0
Posição de p: 17D2
Cada variável dinâmica do tipo "int" ocupa 2 posições aleatórias de memória, conforme mostra a ilustração abaixo.
┌─────────┬──────┐
│ Memória │ Dado │
├─────────┼──────┤
│ 17CCH │ 00H │
├─────────┼──────┤
│ 17CDH │ 00H │
├─────────┼──────┤
│ 17CEH │ │
├─────────┼──────┤
│ 17CFH │ │
├─────────┼──────┤
│ 17D0H │ │
├─────────┼──────┤
│ 17D1H │ │
├─────────┼──────┤
│ 17D2H │ 00H │ ← p
├─────────┼──────┤
│ 17D3H │ 00H │
└─────────┴──────┘
Atenção: observe que "p" passa a apontar para outro endereço de memória e o primeiro dado ficou "perdido", ou seja, sem referência para ele. Se a posição da primeira célula alocada não for armazenada em outro ponteiro, não teremos mais como acessar esse dado.
Veja o exemplo a seguir:
int *p, *q;
p = (int *) malloc(1 * sizeof(int));
q = (int *) malloc(1 * sizeof(int));
Agora ambos os dados criados possuem referência para eles.
Para atribuir valor a um espaço alocado, deve-se utilizar o "*" junto com o ponteiro. Ex:
#include <stdio.h>
#include <stdlib.h>
main()
{
int *p;
p = (int *) malloc(1 * sizeof(int));
*p = 4;
printf("Valor do conteúdo de p: %d\n", *p);
}
Saída:
Valor do conteúdo de p: 4
Cada vez que um espaço na memória é alocado, este espaço fica reservado e indisponível para novos dados. Nesse caso, quando um certo dado não for mais utilizado, ele deverá ser removido da memória, liberando espaço.
O comando que libera espaço em memória para um recurso alocado por malloc ou calloc é o free. Ex:
free(p);
Alocação de vetores
Para alocar um vetor, basta multiplicar o tamanho da variável pelo número de elementos do vetor e passar como parâmetro para o malloc.
O programa a seguir aloca um vetor do tipo "short int" com 3 elementos. O valor retornado ao ponteiro é sempre o da primeira posição do vetor.
#include <stdio.h>
#include <stdlib.h>
main()
{
short int *p;
p = (int *) malloc (3 * sizeof(short int));
}
┌─────────┬──────┐
│ Memória │ Dado │
├─────────┼──────┤
│ 2000H │ xxx │ ← p
├─────────┼──────┤
│ 2001H │ xxx │
├─────────┼──────┤
│ 2002H │ xxx │
└─────────┴──────┘
O código em C a seguir cria um vetor de inteiros com 4 posições, insere dados e depois os imprime.
#include <stdio.h>
#include <stdlib.h>
main()
{
int i, *p;
p = (int *) malloc(4 * sizeof(int));
/* Insere dados no vetor */
for (i=0; i<4; i++)
*(p+i) = i*5;
/* Percorre o vetor lendo os dados */
for (i=0; i<4; i++)
printf("M[%d] = %d\n", i, *(p+i));
}
Saída:
M[0] = 0
M[1] = 5
M[2] = 10
M[3] = 15
Variáveis dinâmicas multidimensionais
Podemos criar matrizes e vetores em n dimensões dinamicamente. Para isso, utilizamos de um truque: criar um vetor de ponteiros para controlar vetores dinâmicos.
┌───┐
│ │ ┌───┬───┬───┬───┐
│ * │ → │ │ │ │ │ Vetor
├───┤ └───┴───┴───┴───┘
│ │ ┌───┬───┬───┬───┐
│ * │ → │ │ │ │ │ Vetor
├───┤ └───┴───┴───┴───┘
│ │ ┌───┬───┬───┬───┐
│ * │ → │ │ │ │ │ Vetor
├───┤ └───┴───┴───┴───┘
│ │ ┌───┬───┬───┬───┐
│ * │ → │ │ │ │ │ Vetor
└───┘ └───┴───┴───┴───┘
Vetor
Ponteiro
Para ilustrar o processo, vamos criar uma matriz 2x2 dinamicamente.
#include <stdio.h>
#include <stdlib.h>
main()
{
int **mat, i;
/* Cria vetor de ponteiros (controla linhas) */
mat = (int **) malloc(2 * sizeof(int*));
/* Cria 2 vetores (linhas) */
for (i=0; i<2; i++)
*(mat+i) = (int *) malloc(2 * sizeof(int));
/* Insere dados na matriz */
mat[0][0] = 1;
mat[0][1] = 2;
mat[1][0] = 3;
mat[1][1] = 4;
/* Imprime dados */
printf("Valor de 0,0: %d\n", mat[0][0]);
printf("Valor de 0,1: %d\n", mat[0][1]);
printf("Valor de 1,0: %d\n", mat[1][0]);
printf("Valor de 1,1: %d\n", mat[1][1]);
}
Saída:
Valor de 0,0: 1
Valor de 0,1: 2
Valor de 1,0: 3
Valor de 1,1: 4
O símbolo "**" denota a criação de um ponteiro para um ponteiro, ou seja, uma referência de memória que contém outra referência de memória. Isto é necessário para vetores multidimensionais.
Observe que criamos um vetor para o ponteiro "mat" do tipo (int *) e não int. Isto porque, mais uma vez, armazenamos nesse vetor endereços de memória e não valores.
Uma vez criado o vetor "mat", alocamos para cada célula desse vetor um novo vetor de int's, com o tamanho igual a 2, conforme mostra a ilustração a seguir.
┌───┐
│ │ ┌───┬───┐
│ * │ → │ │ │ Vetor
├───┤ └───┴───┘
│ │ ┌───┬───┐
│ * │ → │ │ │ Vetor
└───┘ └───┴───┘
Vetor
Ponteiro
Em vez de referenciar uma posição da matriz na forma:
*(*(mat + linha) + coluna) = valor
Utilizamos o colchete duplo [][], que é bem mais simples.
Structs como variáveis dinâmicas
Podemos também criar variáveis dinâmicas para estruturas (structs) do C, do mesmo modo que fizemos com os outros tipos de dados.
Para isso, precisamos:
- Criar a estrutura.
- Criar um ponteiro para a estrutura.
- Alocar memória para a estrutura.
Utilize a expressão a seguir para calcular o tamanho de cada "célula" da estrutura na memória.
sizeof(struct nome_da_estrutura)
A sintaxe básica é:
struct nome
{
...
} *ponteiro;
main()
{
ponteiro = (struct nome *) malloc(sizeof(struct nome));
}
Foi visto que a referência a uma variável de uma "struct" do tipo estática é feita através de um ponto ".". Por exemplo:
struct aluno
{
char nome[20];
int idade;
} alu01;
main()
{
alu01.nome = "Maria";
alu01.idade = 02;
}
No caso de um ponteiro, utiliza-se a expressão "->". Veja o exemplo a seguir.
#include <stdio.h>
#include <stdlib.h>
#include <string.h>
struct ficha
{
char nome[20];
int idade;
} *p;
void main(void)
{
p = (struct ficha *) malloc(sizeof(struct ficha));
strcpy(p->nome, "Gloria");
p->idade = 20;
printf("Nome: %s.\n", p->nome);
printf("Idade: %d anos.\n", p->idade);
}
Saída:
Nome: Gloria.
Idade: 20 anos.
Podemos criar também um array de structs? Perfeitamente. Do mesmo modo que fizemos para o int, declarando o tamanho do array. Veja o exemplo a seguir.
#include <stdio.h>
#include <stdlib.h>
#include <string.h>
struct ficha
{
char nome[20];
int idade;
} *p, *ini;
void main(void)
{
int i;
char *n;
p = (struct ficha *) malloc(4 * sizeof(struct ficha));
ini = p;
for (i=0; i<4; i++)
{
printf("Nome: ");
scanf("%s",n);
strcpy(p->nome, n);
printf("Idade: ");
scanf("%d", &p->idade);
p++;
}
printf("\n");
p = ini; /* Inicio do vetor */
for (i=0; i<4; i++)
{
printf("Registro %d:\n", i+1);
printf(" Nome: %s.\n", p->nome);
printf(" Idade: %d anos.\n", p->idade);
p++;
}
}
Saída:
Entrada de dados:
Nome: Maria
Idade: 21
Nome: Paulo
Idade: 22
Nome: Andre
Idade: 22
Nome: Catarina
Idade: 20
Resposta:
Registro 1:
Nome: Maria.
Idade: 21 anos.
Registro 2:
Nome: Paulo.
Idade: 22 anos.
Registro 3:
Nome: Andre.
Idade: 22 anos.
Registro 4:
Nome: Catarina.
Idade: 20 anos
Podemos acessar o conteúdo do vetor de structs do programa anterior utilizando os colchetes. Veja como:
...
p = ini;
for (i=0; i<4; i++)
{
printf("Registro %d:\n", i+1);
printf(" Nome: %s.\n", p[i].nome);
printf(" Idade: %d anos.\n", p[i].idade);
}
...
Listas encadeadas
Os vetores sempre alocam uma quantidade fixa de memória. Quando criamos aplicações onde os dados crescem sob demanda, como por exemplo um cadastro de clientes, às vezes o espaço alocado é insuficiente para armazenar os dados ou até mesmo muito grande. Para se adequar ao dinamismo dos dados, é necessário sempre criar um novo vetor com o tamanho necessário e copiar os dados da antiga para lá.
As listas encadeadas são uma solução para esse problema, pois permite a alocação de células de dados conforme o necessário.
Entretanto nem tudo são flores. Enquanto que no vetor os dados estão em posições contíguas na memória, nas listas encadeadas precisamos controlar a localização de cada célula criada.
Foi visto anteriormente que a alocação de memória utilizando o mesmo ponteiro faz com que o dado anterior referenciado seja "perdido". Para resolver esse problema, basta armazenar em cada célula o endereço da célula seguinte (ou até mesmo da seguinte e anterior), além é claro de armazenar o endereço da primeira célula criada.
Graficamente:
Célula 1 Célula 2 Célula N
┌───────┬─┐ ┌───────┬─┐ ┌───────┬─┐
│ │─┼──>│ │─┼──>...│ │─┼──┐
└───────┴─┘ └───────┴─┘ └───────┴─┘ ⏚
↑
inicio
Exemplo:
#include <stdio.h>
#include <stdlib.h>
struct no
{
int valor;
struct no *prox;
} *p, *q, *inicio;
main()
{
p = (struct no *) malloc(sizeof(struct no));
p->valor=0x15;
inicio = p;
q=p;
p = (struct no *) malloc(sizeof(struct no));
q->prox = p;
p->valor=0x67;
q=p;
p = (struct no *) malloc(sizeof(struct no));
q->prox = p;
p->valor=0x44;
p->prox=NULL;
}
A variável "inicio" é utilizada para armazenar o endereço da primeira célula, enquanto que a variável "q" é utilizada para armazenar o endereço da célula anterior, uma vez que é necessário indicar à esta célula o endereço da célula atual. Para isso, utiliza-se a expressão "q->prox = p".
Graficamente:
Após alocar e escrever na primeira célula:
┌─────────┬──────┐
│ Memória │ Dado │
├─────────┼──────┤
│ 1234H │ 15H │ ← p = inicio
├─────────┼──────┤
│ 1235H │ 00H │
├─────────┼──────┤
│ 1236H │ xx │
├─────────┼──────┤
│ 1237H │ xx │
└─────────┴──────┘
Após alocar e escrever a segunda célula:
┌─────────┬──────┐
│ Memória │ Dado │
├─────────┼──────┤
│ 1234H │ 67H │ ← inicio = q
├─────────┼──────┤
│ 1235H │ 00H │
├─────────┼──────┤
│ 1236H │ 10H │ Passa a ter o endereço &H1810
├─────────┼──────┤
│ 1237H │ 18H │
├─────────┼──────┤
│ ..... │ ... │
├─────────┼──────┤
│ 1810H │ 0FH │ ← p
├─────────┼──────┤
│ 1811H │ 00H │
├─────────┼──────┤
│ 1812H │ xx │
├─────────┼──────┤
│ 1813H │ xx │
└─────────┴──────┘
Após alocar e escrever a terceira célula:
┌─────────┬──────┐
│ Memória │ Dado │
├─────────┼──────┤
│ 1234H │ 67H │ ← inicio
├─────────┼──────┤
│ 1235H │ 00H │
├─────────┼──────┤
│ 1236H │ 10H │
├─────────┼──────┤
│ 1237H │ 18H │
├─────────┼──────┤
│ ..... │ ... │
├─────────┼──────┤
│ 1810H │ 0FH │ ← q
├─────────┼──────┤
│ 1811H │ 00H │
├─────────┼──────┤
│ 1812H │ 00H │ Passa a ter o endereço &H2000
├─────────┼──────┤
│ 1813H │ 20H │
├─────────┼──────┤
│ ..... │ ... │
├─────────┼──────┤
│ 2000H │ 44H │ ← p
├─────────┼──────┤
│ 2001H │ 00H │
├─────────┼──────┤
│ 2002H │ 00H │ Passa a ter o endereço 0 (NULL)
├─────────┼──────┤
│ 2003H │ 00H │
└─────────┴──────┘
A última célula é apontada para 0, ou seja, um valor nulo (NULL).
Para percorrer a lista de 3 células criadas, temos que apontar "p" para "inicio" e utilizar os endereços contidos em cada célula para encontrar a próxima.
p = inicio;
while (p!=NULL)
{
printf("Valor: %x\n", p->valor);
p = p->prox;
}
A inserção ou remoção de dados é bem simples nas listas encadeadas. Diferente dos vetores, onde às vezes é necessário deslocar os dados, aqui temos somente que criar/destruir o dado e redefinir os endereços.
Veja graficamente o processo de inserção de um elemento entre a célula 2 e 3:
Estado inicial:
Célula 1 Célula 2 Célula 3
┌───────┬─┐ ┌───────┬─┐ ┌───────┬─┐
│ │─┼──>│ │─┼──>│ │─┼──┐
└───────┴─┘ └───────┴─┘ └───────┴─┘ ⏚
Criação de um novo dado:
Célula X
┌───────┬─┐
│ │ │
└───────┴─┘
Célula 1 Célula 2 Célula 3
┌───────┬─┐ ┌───────┬─┐ ┌───────┬─┐
│ │─┼──>│ │─┼──>│ │─┼──┐
└───────┴─┘ └───────┴─┘ └───────┴─┘ ⏚
Redefinição dos apontamentos:
Célula 1 Célula 2 Célula X Célula 3
┌───────┬─┐ ┌───────┬─┐ ┌───────┬─┐ ┌───────┬─┐
│ │─┼──>│ │─┼──>│ │─┼──>│ │─┼──┐
└───────┴─┘ └───────┴─┘ └───────┴─┘ └───────┴─┘ ⏚
Veja graficamente o processo de remoção da célula X:
Estado inicial:
Célula 1 Célula 2 Célula X Célula 3
┌───────┬─┐ ┌───────┬─┐ ┌───────┬─┐ ┌───────┬─┐
│ │─┼──>│ │─┼──>│ │─┼──>│ │─┼──┐
└───────┴─┘ └───────┴─┘ └───────┴─┘ └───────┴─┘ ⏚
Removendo a célula X:
Célula 1 Célula 2 Célula 3
┌───────┬─┐ ┌───────┬─┐ ┌───────┬─┐
│ │─┼──>│ │─┼──> │ │─┼──┐
└───────┴─┘ └───────┴─┘ └───────┴─┘ ⏚
Religando:
Célula 1 Célula 2 Célula 3
┌───────┬─┐ ┌───────┬─┐ ┌───────┬─┐
│ │─┼──>│ │─┼────────────────>│ │─┼──┐
└───────┴─┘ └───────┴─┘ └───────┴─┘ ⏚
O exemplo a seguir recria a estrutura "ficha" para armazenar o nome de três pessoas.
#include <stdio.h>
#include <stdlib.h>
#include <string.h>
struct ficha
{
char nome[20];
int idade;
struct ficha *prox;
} *p, *q, *inicio;
void main(void)
{
int i;
/* Insere dados */
for (i=0; i<3; i++)
{
printf("\nFicha %d:\n",i+1);
p = (struct ficha *) malloc(sizeof(struct ficha));
printf("Nome: ");
scanf("%s", p->nome);
printf("Idade: ");
scanf("%d", &p->idade);
if (i==0)
inicio = p;
else
q->prox = p;
q=p;
if (i==2)
p->prox=NULL;
}
/* Imprime */
printf("\n\nLista de pessoas:\n\n");
p = inicio;
while (p!=NULL)
{
printf("Nome: %s\nIdade: %d\n\n", p->nome, p->idade);
p = p->prox;
}
}
Saída:
Ficha 1:
Nome: Gloria
Idade: 20
Ficha 2:
Nome: Tadeu
Idade: 31
Ficha 3:
Nome: Carla
Idade: 21
Lista de pessoas:
Nome: Gloria
Idade: 20
Nome: Tadeu
Idade: 31
Nome: Carla
Idade: 21