Estruturas e ponteiros
Como vimos em aulas anteriores, podemos declarar uma variável cujo tipo é uma estrutura:
typedef struct ponto {
double x;
double y;
} Ponto
Ponto centro;Podemos manipular essa variável:
centro.x = 12.3; centro.y = 5.2;
E podemos também declarar um ponteiro para estruturas desse tipo e colocá-lo a apontar para a variável anterior:
Ponto *pcentro = ¢ro;
Neste caso, para manipular a estrutura, podemos utilizar o que vimos na última aula:
(*pcentro).x = 12.3; (*pcentro).y = 5.2;
No entanto, dada a frequência com que em C utilizamos este tipo de acesso, existe um operador específico que simplifica a sintaxe, o operador ->. Portanto, podemos manipular a estrutura de forma equivalente da seguinte forma:
pcentro->x = 12.3; pcentro->y = 5.2;
Notar que a declaração de um ponteiro, em particular de um ponteiro para uma estrutura, não aloca memória. Se quisermos alocar memória de forma explícita podemos fazer o seguinte:
Ponto *pcentro; pcentro = (Ponto*) malloc(sizeof(Ponto));
Estruturas e funções
As funções podem receber e retornar estruturas:
Ponto adicionaPonto(Ponto p1, Ponto p2) {
Ponto res;
res.x = p1.x + p2.x;
res.y = p1.y + p2.y;
return res;
}Notar no entanto que função retorna cópia da estrutura, neste caso da estrutura res. A passagem é também feita por valor, ou seja, por cópia dos argumentos. Portanto, tal como vimos em aulas anteriores, a chamada adicionaPonto(pa, pb) não altera os valores das estruturas pa e pb passadas como parâmetro (apenas são modificadas as estruturas cópia que existem apenas no contexto dentro da função).
A questão é se o facto de as estruturas serem passadas por valor pode trazer problemas de eficiência. De facto a passagem de estruturas grandes como parâmetros é ineficiente, uma vez que é necessário efectuar cópia de todos os campos. Por essa razão, utilizam-se normalmente ponteiros para estruturas e, portanto, a passagem passa a ser por referência.
No exemplo anterior podemos ter então:
void adicionaPonto(Ponto *p1, Ponto *p2, Ponto *res) {
res->x = p1->x + p2->x;
res->y = p1->y + p2->y;
}Notar que neste caso podemos alterar o conteúdo dos argumentos, o que acontece de facto com o argumento res.
Podemos também reservar memória para uma estrutura que será utilizada fora da função. Por exemplo, podemos reservar memória com o malloc e retornar o ponteiro para a memória alocada:
Ponto *adicionaPonto(Ponto *p1, Ponto *p2) {
Ponto *res;
res = (Ponto *) malloc(sizeof(Ponto));
res->x = p1->x + p2->x;
res->y = p1->y + p2->y;
return res;
}NOTA IMPORTANTE: Em geral, para cada malloc realizado num programa, tem de existir um free! Um memory leak ocorre sempre que "perdemos" o endereço de memória de uma alocação e, uma vez perdido o endereço, não podemos utilizar a memória alocada e também não a podemos libertar.
Exemplo de uma fuga de memória, um erro a evitar:
void printSOMA(Ponto *p1, Ponto *p2) {
Ponto *res;
res = (Ponto *) malloc(sizeof(Ponto));
res->x = p1->x + p2->x;
res->y = p1->y + p2->y;
printf("(%d, %d)\n",res->x,res->y);
}Notar que, sempre que a função printSOMA for invocada, irá ocorrer uma fuga de memória relativa à alocação de memória e, enquanto o programam não terminar, essas fugas de memória serão acumuladas levando no limite à exaustão da memória disponível para o programa.
Podemos corrigir este erro adicionando um free para libertar a memória quando já não for necessária:
void printSOMA(Ponto *p1, Ponto *p2) {
Ponto *res;
res = (Ponto *) malloc(sizeof(Ponto));
res->x = p1->x + p2->x;
res->y = p1->y + p2->y;
printf("(%d, %d)\n",res->x,res->y);
free (res);
}OUTRA NOTA IMPORTANTE: Ainda que, tal como vimos, um vector seja passado por referência enquanto parâmetro de uma função, o mesmo não é verdade se o vector estiver encapsulado dentro de uma estrutura! Consideremos o seguinte exemplo:
#include <stdio.h>
#include <stdlib.h>
typedef struct {
int a[10];
} sa;
void xpto(sa s)
{
s.a[9] = -1;
}
int main()
{
sa x, y;
int i;
for (i = 0; i < 10; i++)
x.a[i] = i;
y = x;
xpto(x);
for (i = 0; i < 10; i++)
printf("%d %d\n", x.a[i], y.a[i]);
return EXIT_SUCCESS;
}Ao compilar e executar temos:
[aplf@darkstar ~]$ gcc -Wall -ansi -pedantic test02.c [aplf@darkstar ~]$ ./a.out 0 0 1 1 2 2 3 3 4 4 5 5 6 6 7 7 8 8 9 9 [aplf@darkstar ~]$
Ou seja, a expressão y = x copia o conteúdo do vector, o que não acontece se fizermos uma atribuição entre dois vectores! Segundo, x é passado por valor à função xpto, incluindo o vector, uma vez que depois de invocada a função xpto, os valores de x.a continuam inalterados! Portanto, devemos ter bastante cuidado quando passamos estruturas por valor, podemos estar implicitamente a copiar grandes quantidades de memória.
Estruturas auto-referenciadas
As tabelas, ou vectores, permitem representar colecções de elementos, sejam estes inteiros, reais, caracteres, estruturas, ponteiros ou até mesmo outros vectores. Os elementos são guardados em posições consecutivas de memória e o programador é responsável por respeitar os limites.
As tabelas podem ser de dimensão fixa ou podem ser alocadas dinamicamente:
#define N 100 int tab1[N]; int *tab2 = (int *) malloc(N*sizeof(int));
Existem várias formas de aceder aos elementos numa tabela, por exemplo:
x = tab2[i]; y = *(tab2+i);
Ainda que as tabelas sejam fáceis de manipular e permitam aceder facilmente ao n-ésimo elemento, têm algumas desvantagens:
- o tamanho é limitado, sendo necessário realocar e copiar todos os elementos se for necessário aumentar a dimensão;
- pode levar ao desperdício de memória se existirem menos elementos a guardar do que a dimensão disponível na tabela.
Vamos ver ultrapassar algumas destas desvantagens através da implementação de listas ligadas, que na prática são lista de estruturas que se referenciam entre si, ou seja, estruturas auto-referenciadas.
As estruturas auto-referenciadas têm pelo menos um campo que é um ponteiro para outra estrutura do mesmo tipo:
typedef struct ponto {
double x;
double y;
struct ponto *origem;
} Ponto;As estruturas auto-referenciadas irão permitir-nos criar estruturas de dados dinâmicas utilizando ponteiros, como por exemplo listas (simplesmente e duplamente ligadas) e árvores.
Lista simplesmente ligada
Vamos definir um conjunto de nós em que cada nó contém:
- informação útil (valor a guardar, por exemplo);
- ponteiro para o próximo nó.
typedef int Item;
/*
* +----+ +----+ +----+
* head -->| 10 | | 8 | | 15 |
* +----+ +----+ +----+
* | -+-->| -+-->| -+--> NULL
* +----+ +----+ +----+
* node node node
*/
struct node {
Item valor;
struct node *next;
};Vantagens:
- tamanho ilimitado (limite na memória disponível na máquina);
- alocação de memória apenas para os elementos que queremos representar;
- inserção e remoção simples.
Desvantagens:
- mais difícil o acesso ao n-ésimo elemento.
Inserção
/* x * +----+ +----+ +----+ * head -->| 10 | | 8 | | 15 | * +----+ +----+ +----+ * | -+-->| -+--X-->| -+--> NULL * +----+ +--+-+ +----+ * | ^ * | +----+ | * | | 21 | | * | +----+ | * +->| -+--+ * +----+ * t */ t->next = x->next; x->next = t;
Remoção
/* x t * +----+ +----+ +----+ * head -->| 10 | | 8 | | 15 | * +----+ +----+ +----+ * | -+-X->| -+-->| -+--> NULL * +--+-+ +----+ +----+ * | ^ * | | * +-----------------+ */ t = x->next; x->next = t->next; free(t);
Lista duplamente ligada
Vamos definir um conjunto de nós em que cada nó contém:
- informação útil (valor a guardar, por exemplo);
- ponteiro para o próximo nó;
- ponteiro para o nó anterior.
typedef int Item;
/*
* +----+ +----+ +----+
* head -->| 10 | | 8 | | 15 |
* +----+ +----+ +----+
* | -+-->| -+-->| -+--> NULL
* +----+ +----+ +----+
* NULL<--+- -+<--+- |<--+- |
* +----+ +----+ +----+
* node node node
*/
struct node {
Item valor;
struct node *next, *prev;
};typedef
É usual utilizar typedef na manipulação de estruturas auto-referenciadas:
struct node{
int value;
struct node *next;
};
typedef struct node Node;
typedef struct node* Node_ptr;Conversão de tipos e estruturas
Existem algumas situações em que é útil a conversão de tipos, ou typecasting, entre estruturas. No entanto, no caso das estruturas, existem algum detalhes importantes para além do que vimos na Aula 05.
Na maior parte das arquitecturas, quando acedemos a um tipo primitivo, e.g., um inteiro, o seu valor tem de estar alinhado na memória. Ou seja, se um tipo for representado com 4 bytes, a localização na memória tem de começar num endereço que é um múltiplo de 4. Ainda que em algumas arquitecturas a memória possa não estar alinhada, isso não é desejável uma vez que implica uma perda de performance. Por esta razão, a maior parte dos compiladores alinham a memória por omissão. Em particular as implementações típicas da função malloc retornam endereços que são múltiplos de 2*sizeof(size_t), ou seja de 8 ou 16 dependendo se estamos a falar de uma arquitectura de 32 ou 64 bits, respectivamente.
Neste cenário, em que os campos de uma estrutura são alinhados na memória, temos que a estrutura
struct ex1 {
char c;
int i;
};ocupa 8 bytes na memória, e não 5 bytes como seria de esperar. É também importante ter em conta que os compiladores em geral não reorganizam a estrutura para empacotar os campos. Por exemplo, se tivermos as seguintes estruturas,
struct ex2 {
char c;
int i;
char d;
int j;
};
struct ex3 {
char c;
char d;
int i;
int j;
};temos que a primeira tem 16 bytes de tamanho, enquanto que a segunda tem 12 bytes de tamanho. No caso da segunda, temos 2 bytes ocupados pelos char, dois bytes desperdiçados, e 8 bytes para os dois int. O facto de as estruturas estarem alinhadas desta forma é particularmente relevante quando as mesmas são utilizadas em vectores, caso em que se não estivesses alinhadas desta forma, ainda que a alocação de memória tenha o comportamento descrito acima, existiriam campos das estruturas nos vectores que não estariam alinhadas.
A forma como os campos das estruturas são alinhados na memória tem implicações na conversão de tipos de estruturas. Suponhamos que temos o seguinte código:
#include <stdio.h>
#include <stdlib.h>
struct ex4 {
unsigned short x;
int y;
};
struct ex5 {
char a[4];
int y;
};
int main()
{
struct ex4 * ptr;
struct ex5 * pts;
printf("%ld\n", sizeof(struct ex4));
printf("%ld\n", sizeof(struct ex5));
ptr = malloc(sizeof(struct ex4));
ptr->x = 0x2a20;
ptr->y = -10034;
pts = (struct ex5 *) ptr;
printf("[%x,%x,%x,%x] %d\n", pts->a[0], pts->a[1], pts->a[2], pts->a[3], pts->y);
return EXIT_SUCCESS;
}Ao compilar e executar obtemos:
[aplf@darkstar ~]$ gcc -Wall -ansi -pedantic test04.c [aplf@darkstar ~]$ ./a.out 8 8 [20,2a,0,0] -10034 [aplf@darkstar ~]$
Notar que ambas as estruturas têm o mesmo tamanho e que tivemos em conta a correspondência entre os bytes de ambas as estruturas na conversão de tipos pts = (struct ex5 *) ptr.
De facto, desde que tenhamos em mente o alinhamento da memória e que os tipos são apenas informação para o compilador, pois na realidade temos apenas sequências bytes na memória, podemos fazer outras coisas como:
#include <stdio.h>
#include <stdlib.h>
#define LEN 16
struct list {
size_t n;
char a[1];
};
int main()
{
struct list * ptr;
int i;
printf("%ld\n", sizeof(struct list));
ptr = malloc(sizeof(struct list) + LEN - sizeof(size_t));
ptr->n = 0;
for (i = 0; i < LEN; i++) {
ptr->n ++;
ptr->a[i] = 'a' + i;
}
for (i = 0; i < ptr->n; i++)
printf("%c\n", ptr->a[i]);
free(ptr);
return EXIT_SUCCESS;
}Se compilarmos e executarmos com o valgrind, obtemos:
[aplf@darkstar bitbucket]$ gcc -Wall -ansi -pedantic test05.c [aplf@darkstar bitbucket]$ valgrind ./a.out ==24622== Memcheck, a memory error detector ==24622== Copyright (C) 2002-2012, and GNU GPL'd, by Julian Seward et al. ==24622== Using Valgrind-3.8.1 and LibVEX; rerun with -h for copyright info ==24622== Command: ./a.out ==24622== 16 a b c d e f g h i j k l m n o p ==24622== ==24622== HEAP SUMMARY: ==24622== in use at exit: 0 bytes in 0 blocks ==24622== total heap usage: 1 allocs, 1 frees, 24 bytes allocated ==24622== ==24622== All heap blocks were freed -- no leaks are possible ==24622== ==24622== For counts of detected and suppressed errors, rerun with: -v ==24622== ERROR SUMMARY: 0 errors from 0 contexts (suppressed: 2 from 2) [aplf@darkstar bitbucket]$
Porque é que obtemos este output? E porque que é que este código funciona?