Algoritmos e Estruturas de Dados (2024/2025)

Anexo 1

Revisão dos apontadores em C. As seis situações práticas em que se usam apontadores em C.

Apontadores em C

Introdução: Variáveis e apontadores

Os programas processam dados armazenados na memória do computador. O mecanismo mais simples que permite aceder e usar essa memória são as variáveis. Cada variável tem um nome e um tipo e representa um pedaço da memória do computador onde podem ser guardados valores desse tipo.

Exemplo de definição duma variável inteira:

int i;

Através da utilização de variáveis, é possível ir muito longe na escrita de programas em C. Muitos programas podem ser escritos usando apenas variáveis destas.

Mas há algumas situações em que o uso de variáveis não é suficiente e é necessário usar mecanismo mais flexível de manipulação da memória:

Trata-se do mecanismo dos apontadores!

Conceitos básicos sobre apontadores

Portanto os apontadores constituem um segundo mecanismo de acesso à memória:

Em vez de se usar um nome para identificar um pedaço da memória, usa-se diretamente o endereço dessa zona de memória para a identificar e chama-se a esse endereço um apontador. Diz-se que o apontador aponta para uma determinada zona de memória.

Os apontadores são valores especiais que podem ser guardados em variáveis de tipo apontador.

Em C há tipos específicos para representar apontadores. O tipo dos apontadores que apontam para valores de tipo T escreve-se:

T *

Para exemplificar, eis a definição duma variável de tipo apontador para inteiro:

int *pt;

Em C, há duas operações principais para manipular apontadores: o operador & permite obter um apontador para uma variável qualquer, assim:

&Variável

e o operador * permite aceder ao valor apontado por um apontador, assim:

*Apontador

Vejamos um exemplo. Abaixo, define-se uma variável inteira normal v. A seguir define-se uma variável de tipo apontador para inteiros x e fazemo-la apontar para a variável v. Depois, usamos o apontador para colocar o valor 42 na zona de memória apontada por x.

int v = 0;
int *x = &v;
*x = 42

A seguinte figura, ilustra a situação após a atribuição do valor 42 a *x.

Repare que a variável v pode ser acedida de duas formas: (1) usando o nome v; (2) usando a expressão *x.

Para perceber melhor as possibilidades dos apontadores vamos definir agora um segundo apontador, y a fazê-lo também apontar para a variável v:

int *y = x;

Obtém-se a seguinte situação:

Agora o conteúdo da variável v pode ser acedido de três formas diferentes: (1) usando o nome v; (2) usando a expressão *x; (3) usando a expressão *y.

O operador & chama-se operador endereço. O operador * chama-se operador de desreferenciação.

Repare na seguinte curiosa equivalência, que é válida em C para qualquer variável v:

*&v == v

Falta ainda falar da constante predefinida de tipo apontador NULL. Garante-se que este apontador constante não aponta para sítio nenhum. O NULL ser atribuído a qualquer variável de tipo apontador, por exemplo assim:

int *z = NULL;

Neste caso serve para registar que a variável z não está a apontar para sítio nenhum, de momento.

O apontador NULL também pode ser usado em testes, assim:

if (z == NULL) ...

O apontador NULL não pode ser desreferenciado, pois não aponta para sítio nenhum.

Apontadores para registos

O seguinte tipo registo permite representar datas:

typedef struct {
    int day, month, year;
} Date;

Vamos definir agora uma variável de tipo Date e coloquemos um apontador de tipo Date * a apontar para ela:

Date d = {25, 12, 2008};
Date *p = &d;

Para aceder, através do apontador, ao ano da data d, podemos escrever:

(*p).year

Mas a utilização de apontadores para registos em C é tão frequente, que foi criada uma notação mais compacta e sugestiva para fazer isso: o operador ->.

A seguinte expressão é equivalente à anterior:

p->year

Compatibilidade entre apontadores

Em C, tipos de apontadores que apontem para valores de tipos diferentes são incompatíveis entre si.

Com uma exceção: o tipo especial void * é compatível com todos os tipos de operadores.

int *pti;
double *ptd;
void *v;

pti = ptd;             /* Errado */
pti = (int *)ptd;      /* Válido por causa do cast */

v = ptd;               /* Válido porque se trata de void * */
pti = v;               /* Válido porque se trata de void * */

Utilidade dos apontadores

Os exemplos anteriores são interessantes, mas não mostram ainda as situações práticas em que a utilização de apontadores é essencial na linguagem C.

As situações práticas em que se usam apontadores em C são numerosas. Em AED, quase todas essas situações de uso de apontadores vão aparecer:

Implementação de parâmetros de saída nas funções.
Manipulação de vetores.
Manipulação de memória a baixo nível.
Criação de variáveis dinâmicas.
Implementação de estruturas de dados genéricas usando void *.
Implementação de tipos abstratos de dados (TADs).

1 - Apontadores: Implementação de parâmetros de saída nas funções

Vamos tentar programar uma função para trocar o valor de duas variáveis inteiras, x e y. Este é um exemplo que ilustra a necessidade de suportar parâmetros de saída na linguagem C.

Esta primeira tentativa não funciona:

void swap(int a, int b)   /* Não funciona!!!! */
{
    int temp = a;
    a = b;
    b = temp;
}

A chamada de swap(x,y) não muda nada, porque os parâmetros das funções são implementados usando variáveis locais, inicializadas com cópias dos valores passados. A função swap faz a troca das cópias locais, mas não troca o conteúdo das variáveis originais. Diz-se que os parâmetros a e b são parâmetros de entrada, porque eles permitem apenas transferir dados de fora para dentro da função.

Para resolver este problema, temos de usar apontadores. A função swap vai aceder às variáveis originais através de apontadores para efetuar a troca. Fica assim:

void swap(int *a, int *b)   /* Funciona!!!! */
{
    int temp = *a;
    *a = *b;
    *b = temp;
}

Agora a chamada escreve-se swap(&x,&y) e a troca é realmente efetuada. Diz-se que os parâmetros a e b são parâmetros de saída, porque eles permitem passar dados de dentro para fora da função.

Ficámos a saber que há duas maneiras de fazer uma função produzir dados para o seu exterior:

Através do resultado.
Através de parâmetros de saída (usando apontadores).

O seguinte exemplo mostra uma função com dois resultados, sendo os resultados implementados usando parâmetros de saída. A função faz o seguinte: dado um vetor de reais e o respetivo comprimento, a função calcula o máximo e o mínimo do vetor, ao mesmo tempo:

void maxMin(double v[], int n, double *max, double *min) /* precondição: n > 0 */
{
    double lmax = v[0];
    double lmin = v[0];
    int i;
    for( i = 1 ; i < n ; i++ ) {
        if (v[i] > lmax) lmax = v[i];
        if (v[i] < lmin) lmin = v[i];
    }
    *max = lmax;    // passsagem dos resultados para o exterior
    *min = lmin;    // passsagem dos resultados para o exterior
}

Exemplo de chamada:

double vect[] = {1.0, 2.9, 34.6, 44.2,  0.01};
double max, min;
maxMin(vect, 5, &max, &min);

Atenção: Algumas funções de biblioteca também usam parâmetros de saída. Por exemplo, a função de biblioteca scanf. Veja um exemplo de utilização:

int i;
double r;
char c;
scanf("%d %lf %c", &i, &r, &c);

2 - Apontadores: Manipulação de vetores e relação entre vetores e apontadores

Em C o nome duma variável de tipo vetor representa um apontador constante para a primeira componente do vetor guardado na variável.

Considere o seguinte vetor

int sequencia[100];

Para aceder ao primeiro elemento do vetor, normalmente escrevemos:

sequencia[0]

Mas também podemos escrever o que está a seguir, pois o significado é exatamente o mesmo.

*sequencia

Em AED, normalmente acedemos aos elementos dos vetores normais usando a primeira notação, por ser a mais simples. Faremos o mesmo com vetores criados dinamicamente através do malloc.

3 - Apontadores: Manipulação de memória a baixo nível

Tem a ver com a possibilidade de interpretar os bytes de qualquer zona de memória da forma que nos convier, mas não explicamos aqui o mecanismo.

Nas situações mais sofisticadas, até é possível fazer programas introspetivos que analizam a sua própria memória, por exemplo a pilha de execução, para tirar conclusões. Há programas anti-virus que usam este mecanismo.

Esta forma de usar os apontadores não é relevante para AED.

4 - Apontadores: Criação de variáveis dinâmicas

Até agora temos usado apontadores que apontam para variáveis normais, previamente declaradas no código do programa. Agora vai surgir uma novidade.

Em C, além das variáveis normais, declaradas no código do programa, também é possível criar novas variáveis em tempo de execução - as chavadas variáveis dinâmicas. Mas, se é assim, quando se cria uma variável dinâmica, qual será o nome dessa variável? Na verdade ela não tem nome e por isso, precisa de ser manipulada através dum apontador.

Usa-se a função de biblioteca malloc para criar variáveis dinâmicas. Eis o cabeçalho desta função, tal como está definido no módulo stdlib:

void *malloc(size_t size);

Exemplo de utilização:

#include <stdlib.h> 

int *a = malloc(10 * sizeof(int));  /* cria variável dinâmica; neste caso um vetor dinâmico com 10 inteiros */
a[3] = 10;                          /* altera a célula de índice 3 do vetor dinâmico */

A função malloc retorna a constante NULL no caso de não haver mais memória disponível.

Para libertar a memória ocupada por uma variável dinâmica que deixou de ser precisa, usa-se a operação:

void free(void *ptr);

Existe ainda um outra função muito útil, que permite mudar o tamanho duma variável dinâmica:

void realloc(void *ptr, int newSize);

Interessa criar variáveis dinâmicas principalmente nas seguintes situações:

Para criar vetor dinâmicos, isto é vetores cujo tamanho só pode ser determinado depois do programa começar a correr.
Para construir estruturas de dados dinâmicas, e.g. listas ligadas e árvores, cujos elementos constituintes vão sendo criados à medidas das necessidades.

5 - Apontadores: Implementação de estruturas de dados genéricas usando `void *`

Em AED vão ocorrer muitas situações em que precisamos de criar estruturas de dados genéricas, capazes de armazenar objetos de tipo qualquer.

A implementação duma estrutura de dados genérica envolve o uso de apontadores de tipo void *. O que se guarda numa estruturas de dados genéricas são apontadores para objetos, e não os objetos propriamente ditos. É a única forma de obter independencia do tipo dos objetos.

Ainda é cedo para dar mostrar a implementação duma estrutura de dados genérica. Como alternativa, mostra-se um exemplo de função genérica que aceita argumentos de vários tipos.

A seguinte função troca os conteúdos de duas variáveis de qualquer tipo. Os parâmetros da função são de tipo void *. Note que, neste caso, precisamos de saber o tamanho dos valores do tipo que estiver em causa.

#include <string.h>

void swap(void *a, void *b, int n) {
    char aux[n];
    memcpy(aux, a, n);
    memcpy(a, b, n);
    memcpy(b, aux, n);
}

O seguinte programa de teste chama a função genérica com variáveis de tipo int e de tipo double.

int testA(void) {
    int x = 5, y = 6;
    printf("%d %d\n", x, y);
    swap(&x, &y, sizeof(int));
    printf("%d %d\n", x, y);
    return 0;
}

int testB(void) {
    double x = 2.22, y = 3.33;
    printf("%lf %lf\n", x, y);
    swap(&x, &y, sizeof(double));
    printf("%lf %lf\n", x, y);
    return 0;
}

int main(void) {
    testA();
    testB();
    return 0;
}

6 - Apontadores: Definição de tipos abstratos de dados (TADs)

O conceito de tipo abstrato de dados (TAD) é o conceito central de AED.

Um tipo abstrato de dados oculta a representação interna dos seus valores. O tipo diz-se abstrato porque abstrai a representação interna dos seus valores. "Abstrair" significa "ignorar deliberadamente".

É muito importante implementar TADs, por diversas razões que são estudadas em Engenharia de Software e que veremos mais tarde.

Felizmente, a linguagem C oferece um mecanismo para implementar tipos abstratos. Esse mecanismo também recorre ao uso de apontadores.

Vamos exemplificar com um TAD Aluno. Queremos alcançar algo de exigente: por um lado, o nome do tipo "Aluno" tem de ser público, pelo outro lado não podemos divulgar a representação dos objetos de tipo Aluno.

Faz-se assim: Escondemos a representação dos alunos dentro do ficheiro "Aluno.c".

struct Aluno {
    int numero;          // Numero do aluno
    double p;            // Nota do projeto
    double t1, t2;       // Notas testes
};

Desta forma, o ficheiro "Aluno.c" fica com acesso à representação e pode implementar todas as operações sobre alunos. Mais nenhum módulo fica com acesso à representação, porque em C nunca se incluem ficheiros ".c".

Mas, como é que as outras partes do sistema têm acesso nome de tipo Aluno, por exemplo para definir variáveis?

A solução consiste em colocar, no ficheiro "Aluno.h", a seguinte definição pública:

typedef struct Aluno *Aluno;

Publicamente, fica-se a saber que o Aluno é um tipo apontador para o tipo registo "struct Aluno". E não se divulgam os campos de "struct Aluno". O facto desta definição ser considerada válida é um pequeno milagre na linguagem C. O C permite definir tipos apontador para tipos incompletos. No ficheiro "Aluno.h", o tipo "struct Aluno" é um tipo incompleto porque não conhecemos os campos dele.

Iremos definir os nossos TADs usando este mecanismo. Ficamos muito satisfeitos por ter à nossa disposição um mecanismo eficaz para ocultação de informação! Mas, note que há um pequeno preço a pagar: vamos ter de manipular todos os nossos objetos através de apontadores.