Apontadores e Estruturas de Dados Dinâmicas em C
Fernando Mira da Silva
Departamento de Engenharia Electrotécnica e de Computadores
Instituto Superior Técnico
Novembro de 2002
Resumo
O C é provavelmente a mais flexı́vel das linguagens de programação de alto-nı́vel, mas apresenta uma relativa complexidade sintáctica. Uma das maiores dificuldades na abordagem do
C numa disciplina de introdutória de programação é a necessidade de introduzir os conceitos de
endereço de memória, apontador e memória dinâmica.
Este texto foi preparado para apoio à disciplina de Introdução à Programação da Licenciatura
em Engenharia Electrotécnica e Computadores do Instituto Superior Técnico. Este texto tenta
focar de modo sistemático alguns dos tópicos que maiores dúvidas suscita nas abordagens iniciais
da linguagem: apontadores e estruturas de dados dinâmicas. Assim, embora se pressuponha o
conhecimentos dos elementos básicas da linguagem C por parte do leitor – nomeadamente, os
tipos de dados elementares e as estruturas de controlo – o texto é mantido ao nı́vel elementar de
uma disciplina introdutória de informática.
Na apresentação das estruturas de dados consideradas, que incluem pilhas, filas, listas e
anéis, introduz-se de forma natural a noção de abstracção de dados, e os princı́pios essenciais
de estruturação e modularidade baseados neste paradigma de programação.
Para o programador experiente em C, alguns dos exemplos de código poderão parecer pouco
optimizados. Trata-se de uma opção premeditada que tenta beneficiar a clareza e a simplicidade
algorı́tmica, ainda que em alguns casos esta opção possa sacrificar ligeiramente a eficiência do
código apresentado. Pensamos, no entanto, que esta é a opção correcta numa abordagem introdutória da programação.
Índice
1 Introdução
1
2 Apontadores
5
2.1
Motivação para os apontadores em C . . . . . . . . . . . . . . . . . . . . . . . .
5
2.2
Modelos de memória em C . . . . . . . . . . . . . . . . . . . . . . . . . . . . .
5
2.3
Apontadores . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .
7
2.4
Funções e passagem por referência . . . . . . . . . . . . . . . . . . . . . . . . .
11
2.4.1
Passagem por referência . . . . . . . . . . . . . . . . . . . . . . . . . .
11
2.4.2
Erros frequentes . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .
16
Vectores e apontadores . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .
18
2.5.1
Declaração de vectores . . . . . . . . . . . . . . . . . . . . . . . . . . .
18
2.5.2
Aritmética de apontadores . . . . . . . . . . . . . . . . . . . . . . . . .
22
2.5.3
Índices e apontadores . . . . . . . . . . . . . . . . . . . . . . . . . . . .
25
2.5.4
Vectores como argumentos de funções . . . . . . . . . . . . . . . . . . .
26
Matrizes . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .
28
2.6.1
28
2.5
2.6
Declaração . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .
IV
ÍNDICE
2.7
3
Matrizes como argumento de funções . . . . . . . . . . . . . . . . . . .
29
2.6.3
Matrizes e vectores . . . . . . . . . . . . . . . . . . . . . . . . . . . . .
31
2.6.4
Matrizes e apontadores . . . . . . . . . . . . . . . . . . . . . . . . . . .
34
Generalização para mais do que duas dimensões . . . . . . . . . . . . . . . . . .
38
Vectores e memória dinâmica
41
3.1
Introdução . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .
41
3.2
Vectores . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .
43
3.3
“Vectores” dinâmicos . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .
46
3.4
Gestão da memória dinâmica . . . . . . . . . . . . . . . . . . . . . . . . . . . .
48
3.4.1
Verificação da reserva de memória . . . . . . . . . . . . . . . . . . . . .
48
3.4.2
Outras funções de gestão de memória dinâmica . . . . . . . . . . . . . .
50
3.4.3
Garbbage . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .
52
Criação dinâmica de matrizes . . . . . . . . . . . . . . . . . . . . . . . . . . . .
55
3.5.1
Introdução . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .
55
3.5.2
Matrizes estáticas . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .
55
3.5.3
Matrizes dinâmicas . . . . . . . . . . . . . . . . . . . . . . . . . . . . .
56
3.5.4
Vectores de apontadores e matrizes . . . . . . . . . . . . . . . . . . . .
58
3.5
4
2.6.2
Listas dinâmicas
61
4.1
Introdução . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .
61
4.2
Abstracção de dados . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .
62
ÍNDICE
4.3
Listas . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .
63
4.4
Listas dinâmicas: listar elementos . . . . . . . . . . . . . . . . . . . . . . . . .
66
4.5
Listas: pilhas . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .
68
4.5.1
Introdução . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .
68
4.5.2
Declaração . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .
70
4.5.3
Inicialização . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .
70
4.5.4
Sobreposição . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .
71
4.5.5
Remoção . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .
72
4.5.6
Teste . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .
72
4.5.7
Exemplo . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .
73
Listas: filas . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .
80
4.6.1
Introdução . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .
80
4.6.2
Declaração . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .
80
4.6.3
Inicialização . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .
81
4.6.4
Inserção . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .
82
4.6.5
Remoção . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .
83
4.6.6
Teste . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .
83
4.6.7
Exemplo . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .
84
Listas ordenadas . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .
87
4.7.1
Introdução . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .
87
4.7.2
Declaração e inicialização . . . . . . . . . . . . . . . . . . . . . . . . .
88
4.6
4.7
V
VI
ÍNDICE
4.8
4.9
4.7.3
Listagem ordenada . . . . . . . . . . . . . . . . . . . . . . . . . . . . .
89
4.7.4
Procura . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .
89
4.7.5
Abstracção de dados e métodos de teste . . . . . . . . . . . . . . . . . .
91
4.7.6
Inserção ordenada . . . . . . . . . . . . . . . . . . . . . . . . . . . . .
92
4.7.7
Remoção . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .
95
4.7.8
Exemplo . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .
96
Variantes . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 107
4.8.1
Introdução . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 107
4.8.2
Listas com registo separado para a base . . . . . . . . . . . . . . . . . . 107
4.8.3
Listas duplamente ligadas . . . . . . . . . . . . . . . . . . . . . . . . . 108
4.8.4
Aneis . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 109
Anel duplo com registo separado para a base . . . . . . . . . . . . . . . . . . . . 109
4.9.1
Introdução . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 109
4.9.2
Declaração . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 110
4.9.3
Inicialização . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 110
4.9.4
Listagem . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 111
4.9.5
Procura . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 111
4.9.6
Inserção . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 112
4.9.7
Remoção . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 113
4.9.8
Exemplo . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 114
4.10 Listas de listas . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 121
ÍNDICE
5
Conclusões
Bibliografia
125
127
VII
Capı́tulo 1
Introdução
Até ao aparecimento da linguagem C, as linguagens de alto-nı́vel tinham por objectivo distanciar o programador do hardware especı́fico de trabalho. Pretendia-se, deste modo, que o programador focasse a sua actividade na solução conceptual e algorı́tmica do problema e, simultaneamente, que o código final fosse independente do hardware e, como tal, facilmente portável entre
diferentes plataformas.
Este princı́pio teórico fundamental, ainda hoje correcto em muitas áreas de aplicação de software, conduzia no entanto a problemas diversos sempre que o programador, por qualquer motivo,
necessitava de explorar determinadas regularidades das estruturas de dados de modo a optimizar
zonas crı́ticas do código ou, em outros casos, por ser conveniente ou desejável explorar determinadas facilidades oferecidas pelas instruções do processador que não estavam directamente
disponı́veis na linguagem de alto-nı́vel. Nestas situações, a única alternativa era a programação
directa em linguagem máquina destes blocos de código, opção que implicava a revisão do software
em cada alteração ou evolução de hardware.
Por razões semelhantes, quer o sistema operativo quer ferramentas de sistema como compiladores, gestores de ficheiros ou monitores de sistema eram consideradas aplicações que, por
requisitos de eficiência do código, eram incompatı́veis com linguagens de alto-nı́vel. O mesmo
sucedia com todos os programas que necessitavam, de alguma forma, de controlar directamente
dispositivos de hardware. Como corolário, estas aplicações eram tradicionalmente escritas totalmente em linguagem máquina, implicando um enorme esforço de desenvolvimento e manutenção
em cada evolução do hardware.
Quando Ken Thompson iniciou a escrita do sistema operativo Unix (Ritchie e Thmompson,
1974), desenvolveu uma linguagem, designada B, que funcionava no hardware de um computador
2 I NTRODUÇ ÃO
Digital PDP-10. O B era uma linguagem próxima da linguagem máquina, mas que facilitava extraordinariamente a programação de baixo-nı́vel. O B adoptava algumas estruturas decisionais e
ciclos comuns a linguagens de alto-nı́vel e, simultaneamente, disponibilizava um conjunto de facilidades simples, geralmente só acessı́veis em linguagem máquina, como o acesso a endereços de
memória e a métodos de endereçamento indirecto. De facto, os mecanismos de acesso a variáveis
e estruturas de dados previstos no B cobriam a esmagadora maioria das necessidades dos programadores quando anteriormente eram obrigados a recorrer à linguagem máquina. Ora estes mecanismos, embora obviamente dependentes do hardware, obedeciam na sua generalidade ao modelo
de memória previsto na arquitectura de Von Neuman, o qual, nos seus princı́pios essenciais, está na
base da maioria das plataformas computacionais desde os anos 50 até aos nossos dias. Foi assim
surgiu a ideia da possibilidade de desenvolvimento de uma linguagem de alto nı́vel, independente
do hardware, que permitisse simultaneamente um acesso flexı́vel aos modos de endereçamento
e facilidades disponı́veis ao nı́vel da linguagem máquina da maioria dos processadores. É assim
que, em 1983, é inventada a linguagem C (Kernighan e Ritchie, 1978), a qual permitiu a re-escrita
de 90% do núcleo do sistema operativo Unix em alto-nı́vel.
Para além da manipulação directa de endereços de memória, uma das facilidades introduzida
pela linguagem C foi a incorporação de mecanismos para gestão de memória dinâmica. O conceito
de memória dinâmica permite que um programa ajuste de modo flexı́vel a dimensão da memória
que utiliza de acordo com as suas necessidades efectivas. Por exemplo, um mesmo programa de
processamento de texto pode ocupar pouca memória se estiver a tratar um documento de pequena
dimensão, ou ocupar um volume mais significativo no caso de um documento de maior número de
páginas.
A invenção da linguagem C (Kernighan e Ritchie, 1978) permitiu a re-escrita de 90% do
núcleo do sistema operativo Unix em linguagem de alto-nı́vel. A possibilidade de manipular
endereços de memória permitiu ainda a implementação eficiente em linguagem de alto nı́vel de
muitos algoritmos e estruturas de dados até então geralmente escritos em linguagem Assembler
(Knuth, 1973).
Neste texto apresenta-se uma introdução aos apontadores e memória dinâmica na linguagem
de programação C. Para exemplificar estes conceitos, são introduzidas algumas estruturas de dados
dinâmicas simples, como pilhas, filas, listas e aneis. Durante a exposição, introduz-se de forma
natural a noção de abstracção de dados, e os princı́pios essenciais de estruturação e modularidade
baseados neste paradigma de programação. Deste modo, a noção de abstracção de dados não é introduzida formalmente num capı́tulo autónomo, mas sim quando se instroduzem listas dinâmicas,
altura em que o conceito é fundamental para justificar a estrutura adoptada. Esta abordagem, embora pouco convencional, deriva da nossa experiência na docência da disciplina de Introdução à
Programação durante vários anos no IST, tendo beneficiado das crı́ticas e sugestões de diversas
3
gerações de alunos.
Tenta-se neste texto dar-se primazia à clareza algorı́tmica e legibilidade do código, ainda
que em alguns casos esta opção possa sacrificar pontualmente a eficiência do código produzido.
Considera-se, no entanto, que é esta a abordagem mais adequada numa disciplina de Introdução
à Programação. Por outro lado, a maioria dos compiladores recentes incluem processos de
optimização que dispensam a utilização explı́cita dos mecanismos de optimização previstos originalmente na linguagem C.
Capı́tulo 2
Apontadores
2.1
Motivação para os apontadores em C
2.2
Modelos de memória em C
Embora os mecanismos de endereçamento e acesso à memória tenham sofrido várias
evoluções nas últimas décadas e sejam evidentemente dependentes do hardware, o C requer apenas
hipóteses muito simples relativamente ao modelo de memória do processador.
A memória de um computador encontra-se organizada em células ou palavras de memória
individuais. Cada palavra de memória é referenciada por um endereço e armazena um dado
conteúdo. Designa-se por “número de bits da arquitectura” o número máximo de bits que um
processador é capaz de ler num único acesso à memória. Cada palavra de memória de referência
de um processador tem em geral um número de bits idêntico ao número de bits da arquitectura1 .
Admita-se que num dado programa em C declara, entre outras as variáveis i,j,k com o tipo
int, a variável f com o tipo float e uma variável d do tipo double, não necessariamente
por esta ordem. Admita-se que após a declaração destas variáveis são realizadas as seguintes
atribuições:
i = 2450; j = 11331; k = 113; f = 225.345; d = 22.5E+145;
1
A complexidade dos modos de endereçamento dos processadores actuais conduz a que a definição e os modelos
aqui apresentados pequem por uma simplicidade excessiva, mas são suficientes para os objectivos propostos.
6 A PONTADORES
Endereço
..
.
Conteúdo
Variável
..
.
..
.
1001
???
1002
2450
1003
???
1004
225.345
f
1005
11331
j
1006
113
k
1007
22.5E145
1008
(double, 64bits)
1009
???
..
.
i
d
..
.
Figura 2.1: Modelo de memória em C (exemplo).
Um exemplo esquemático de um modelo memória correspondente a esta configuração encontra-se
representado na figura 2.1. Admite-se aqui que a palavra de memória e o tipo inteiro são representados por 32 bits. De acordo com a figura, durante a compilação foram atribuı́dos às variáveis
i,j,k,f os endereços 1002,1005, 1006 e 1004, respectivamente, enquanto que à variável d foi
atribuı́do o endereço 10072 . Note-se que, com excepção do tipo double, cada variável tem uma
representação interna de 32 bits, ocupando por isso apenas um endereço de memória. A variável
d, de tipo double, tem uma representação interna de 64 bits, exigindo por isso duas palavras de
memória: os endereços 1007 e 1008. Na figura 2.1 encontram-se representados outras posições
de memória, provavelmente ocupadas por outras variáveis, e cujo conteúdo é desconhecido do
programador.
2
Estritamente falando, a cada variável local, é apenas atribuı́do um endereço relativo durante a compilação, sendo o
endereço final fixado durante a execução da função ou activação do bloco de instruções em que a declaração é realizada.
Este tema voltará a ser abordado na secção 3.2.
A PONTADORES 7
2.3
Apontadores
Um apontador em C é uma variável cujo conteúdo é um endereço de outra posição de
memória. A declaração de variáveis do tipo apontador pode ser construı́da a partir de qualquer
tipo definido anteriormente, e deve especificar o tipo de variável referenciada pelo apontador.
A declaração de uma variável do tipo apontador realiza-se colocando um “*” antes do nome
da variável. Assim, na declaração
double *pd;
int
i;
int
*pi;
float
f;
int
j,k;
double d;
int
m,*pi2;
double *pd2,d2;
as variáveis i,j,k,m são do tipo int, f é do tipo float, e d,d2 são do tipo double. Além
destas variáveis de tipos elementares, são declaradas as variáveis pi, pi2 do tipo apontador
para inteiro, enquanto que pd e pd2 são do tipo apontador para double.
Admita-se agora se realiza a seguinte sequência de atribuições:
i = 2450; f = 225.345; k = 113; d = 22.5E145; m = 9800;
Após estas instruções, o mapa de memória poderia ser o representado na figura 2.2, situação
A. Sublinhe-se que as variáveis de tipo apontador apenas contêm um endereço de memória, independentemente do tipo referenciado. Desta forma, todas as variáveis de tipo apontador têm
uma representação igual em memória, normalmente de dimensão idêntica ao do tipo inteiro (uma
palavra de memória). Note-se que o conteúdo dos apontadores, tal como o de algumas variáveis
elementares, ainda não foi inicializado, pelo que surgem representados com ???. É importante
compreender que cada uma destas variáveis tem de facto um conteúdo arbitrário, resultante da
operação anterior do computador. Claro que estes valores, não tido sido ainda inicializados pelo
programa, são desconhecidos do programador, mas esta situação não deve ser confundida com a
“ausência de conteúdo”, erro de raciocı́nio frequentemente cometido por programadores principiantes.
As variáveis de tipo elementar podem ser inicializadas pela atribuição directa de valores constantes. A mesma técnica pode ser utilizada para a inicialização de apontadores, embora este
8 A PONTADORES
Endereço
..
.
Conteúdo
Variável
..
.
..
.
Endereço
..
.
Conteúdo
Variável
..
.
..
.
Endereço
..
.
Conteúdo
Variável
..
.
..
.
pd
1001
1007
pd
1001
1007
pd
i
1002
2450
i
1002
2450
i
pi
1003
1006
pi
1003
1006
pi
225.345
f
1004
225.345
f
1004
225.345
f
1005
???
j
1005
???
j
1005
???
j
1006
113
k
1006
113
k
1006
113
k
d
1007
d
1007
1001
???
1002
2450
1003
???
1004
1007
22.5E145
1008
(double, 64bits)
1009
9800
1010
1011
1012
m
1009
9800
m
???
pi2
1010
1006
pi2
???
pd2
1011
1007
pd2
d2
1012
???
d2
m
1009
9800
???
pi2
1010
???
pd2
1011
d2
1012
(double, 64bits)
1013
..
.
..
.
..
.
A
..
.
1008
1008
???
Conteúdo
???
(double, 64bits)
1013
..
.
..
.
Variável
Endereço
..
.
Conteúdo
Variável
..
.
..
.
(double, 64bits)
..
.
C
B
..
.
..
.
d
22.5E145
(double, 64bits)
(double, 64bits)
1013
Endereço
22.5E145
Endereço
..
.
Conteúdo
Variável
..
.
..
.
1001
1007
pd
1001
1007
pd
5001
3
i1
1002
2450
i
1002
2450
i
5002
4
i2
1003
1006
pi
1003
1006
pi
5003
5001
pi1
5004
5003
pi2
1004
225.345
f
1005
113
j
1005
113
j
5005
5004
pi3
1006
113
k
1006
113
k
5006
10
k1
d
1007
d
5007
46
k2
5008
5006
pk1
5003
pk2
1007
22.5E145
1008
(double, 64bits)
1009
9800
1010
1011
1012
1013
..
.
1004
225.345
f
22.5E145
1008
(double, 64bits)
m
1009
24500
m
5009
1006
pi2
1010
1002
pi2
5010
1007
pd2
1011
1012
pd2
5011
d2
1012
d2
5012
22.5E145
(double, 64bits)
..
.
D
1013
..
.
22.5E144
(double, 64bits)
..
.
E
5013
..
.
..
.
F
Figura 2.2: Mapa de memória após diferentes sequências de atribuição (explicação no texto).
A PONTADORES 9
método raramente seja utilizado: em geral, o programador não sabe quais os endereços de memória
disponı́veis no sistema, e a manipulação directa de endereços absolutos tem reduzidas aplicações
práticas.3 Assim, A inicialização de apontadores é geralmente realizada por outros métodos, entre
os quais a utilização do endereço de outras variáveis já declaradas. Este endereço pode ser obtido
em C aplicando o operador & a uma variável. Na continuação do exemplo anterior, admita-se que
era realizada agora a seguinte sequência de atribuições:
pd = &d; pi = &k;
Após esta fase, o mapa de memória seria o representado na figura 2.2, situação B, onde as
variáveis pd e pi surgem agora preenchidas com os endereços de d e k. Como seria de esperar, a consistência da atribuição exige que a variável referenciada e o tipo do apontador sejam
compatı́veis. Por exemplo, a atribuição pd=&k é incorrecta, atendendo a que k é do tipo int e
pd está declarada como um apontador para double.
A partir do momento em que os apontadores são inicializados, o seu conteúdo pode ser
copiado e atribuı́do a outras variáveis, desde que os tipos ainda sejam compatı́veis. Assim, as
atribuições
pd2 = pd; pi2 = pi;
conduziriam apenas à cópia dos endereços guardados em pd e pi para pd2 e pi2. Após esta
sequência, a situação seria a representada na figura 2.2, caso C.
Uma vez estabelecido um mecanismo para preecher o conteúdo de um apontador, coloca-se a
questão de como utilizar este apontador de modo a aceder aos dados apontados. Este mecanismo é
suportado no chamado sistema de endereçamento indirecto, o qual é realizado em C pelo operador
*. Assim, a atribuição j = *pi; tem o significado “consultar o endereço guardado em pi (1006)
e, seguidamente, ler o inteiro cujo endereço é 1006 e colocar o resultado (113) na variável j. Deste
modo, após as atribuições
j = *pi; d2 = *pd;
a situação seria a representada na figura 2.2, caso D.
Referiu-se anteriomente que um apontador é apenas um endereço de memória. Assim, poderá
questionar-se a necessidade de distinguir um apontador para um inteiro de um apontador para um
3
Embora possa ser pontualmente utilizada em programas que lidam directamente com o hardware.
10 A PONTADORES
real, por exemplo. De facto, a dependência do apontador do tipo apontado não tem a ver com
a estrutura do apontador em si, mas sim com o facto de esta informação ser indispensável para
desreferenciar (aceder) correctamente o valor endereçado. Por exemplo, na expressão d2 = *pd,
é o facto de pd ser um apontador para double que permite ao compilador saber que o valor
referenciado ocupa não apenas uma, mas duas palavras de memória e qual a sua representação. Só
na posse desta informação é possı́vel efectuar a atribuição correcta a d2.
Outras sequências de atribuição seriam possı́veis. Por exemplo, após a sequência
pd2 = &d2; *pd2 = *pd1 / 10.0; pi2 = &i; m= *pi2 * 10;
a situação seria a representada no caso E. Note-se que aqui o operador * foi utilizado no lado
esquerdo da atribuição. Assim, por exemplo, a atribuição *pd2 = *pd1 é interpretada como
ler o real cujo endereço é especificado pelo conteúdo de pd1 e colocar o resultado no endereço
especificado por pd2.
Embora até aqui tenham sido considerados apontadores para tipos elementares, um apontador
pode também endereçar um outro apontador. Assim, na declaração
int i1,i2,*pi1,**pi2,***pi3;
int k1,k2,*pk1,**pk2;
enquanto que p1 é um apontador para um inteiro, p2 é um apontador para um apontador para um
inteiro e p3 é um apontador para um apontador para um apontador para um inteiro. Como seria de
esperar, a inicialização destes apontadores realiza-se segundo as mesmas regras seguidas para os
apontadores simples, sendo apenas necessário ter em atenção, o nı́vel correcto de endereçamento
indirecto múltiplo. Assim, se após a declaração anterior, fosse executada a sequência de instruções
i1 = 3; i2 = 4;
pi1 = &i1; pi2 = &pi1; pi3 = &pi2;
k1 = 10;
pk1 = &k1; pk2 = pi2;
k2 = i1 * ***pi3 + *pi1 + i2 + **pk2 * *pk1;
a situação final poderia ser a representada na figura 2.2, caso F.
Em apontadores mútilpos a possibilidade de desreferenciar um apontador continua a ser dependente do tipo apontado. Deste modo, um apontador para um inteiro e um apontador para um
apontador para um inteiro são tipos claramente distintos e cujos conteúdos não podem ser mutuamente trocados ou atribuı́dos. Por outro lado, os nı́veis de indirecção devem ser claramente
F UNÇ ÕES E PASSAGEM POR REFER ÊNCIA 11
respeitados. Assim, a atribuição i1 = *pk2; no exemplo precedente seria incorrecta, já que i1
é do tipo inteiro e, *pk2 é um apontador para inteiro (recorde-se que pk2 é um apontador para um
apontador para um inteiro).
Como é sabido, o valor de uma variável nunca deve ser utilizado antes de esta ser inicializada
explicitamente pelo programa. Com efeito, no inı́cio de um programa, as variáveis têm um valor
arbitrário desconhecido. Por maioria de razão, o mesmo princı́pio deve ser escrupulosamente
seguido na manipulação de apontadores. Suponha-se, por exemplo que, no inı́cio de um programa,
são incluı́das a declaração e as instruções seguintes:
int *p,k;
k = 4; *p = k*2;
Aqui, a segunda atribuição especifica que o dobro de k (valor 8) deve ser colocado no endereço
especificado pelo conteúdo da variável p. No entanto, dado que p não foi inicializada, o seu
conteúdo é arbitrário. Com elevada probabilidade, o seu valor corresponde a um endereço de
memória inexistente ou inválido. No entanto, o C não realiza qualquer juı́zo de valor sobre esta
situação e, tendo sido instruı́do para “colocar 8 no endereço indicado por p” tentará executar esta
operação. A tentativa de escrita numa posição de memória inválida ou protegida conduzirá ou ao
compromisso da integridade do sistema operativo se o espaço de memória não for convenientemente protegido, como é o caso do DOS. Se o sistema tiver um modo protegido, como o Unix ou o
Windows NT, esta situação pode originar um erro de execução, devido a uma violação de memória
detectada pelo sistema operativo. Os erros de execução conduzem à interrupção imediata, em erro,
do programa.
Sublinhe-se que nas figuras desta secção foram utilizados endereços especı́ficos nos apontadores de modo a melhor demonstrar e explicar o mecanismo de funcionamento dos mecanismos de
apontadores e indirecção em C. No entanto, na prática, o programador não necessita de conhecer o
valor absoluto dos apontadores, sendo suficiente a manipulação indirecta do seu conteúdo através
dos mecanismos de referenciação e desreferenciação descritos.
2.4
2.4.1
Funções e passagem por referência
Passagem por referência
Em C, na chamada de uma função, os parâmetros formais da função recebem sempre uma
cópia dos valores dos parâmetros actuais. Este mecanismo de passagem de argumentos é desig-
12 A PONTADORES
nado passagem por valor (Martins, 1989) e está subjacente a todas as chamadas de funções em
C. Esta situação é adequada se se pretender apenas que os argumentos transmitam informação do
módulo que chama para dentro da função. Dado que uma função pode também retornar um valor,
este mecanismo básico é também adequado quando a função recebe vários valores de entrada e
tem apenas um valor de saı́da. Por exemplo, uma função que determina o maior de três inteiros
pode ser escrita como
int maior_3(int i1,int i2, int i3){
/*
* Função que determina o maior de três inteiros
*
*/
if((i1 > i2) && (i1 > i3))
return i1;
else
return (i2 > i3 ? i2 : i3);
}
Existem no entanto situações em que se pretende que uma função devolva mais do que um
valor. Uma situação possı́vel seria uma variante da função maior_3 em que se pretendesse
determinar os dois maiores valores, e não apenas o maior. Outro caso tı́pico é o de uma função
para trocar o valor de duas variáveis entre si. Numa primeira tentativa, poderia haver a tentação de
escrever esta função como
#include <stdio.h>
#include <stdlib.h>
void trocaMal(int x,int y){
/*
* ERRADO
*/
int aux;
aux = x;
x
= y;
y
= aux;
}
int main(){
int a,b;
printf("Indique dois números: ");
scanf("%d %d",&a,&b);
trocaMal(&a,&b);
printf("a = %d, b= %d\n",a,b);
F UNÇ ÕES E PASSAGEM POR REFER ÊNCIA 13
exit(0);
}
No entanto, este programa não funciona: o mecanismo de passagem por valor implica que a
função troca opera correctamente sobre as variáveis locais x e y, trocando o seu valor, mas estas
variáveis não são mais do que cópias das variáveis a e b que, como tal, se mantêm inalteradas.
Na figura 2.3 representa-se a evolução do mapa de memória e do conteúdo das variáveis durante a
chamada à função trocaMal.
Este aparente problema pode ser resolvido pela utilização criteriosa de apontadores. A função
troca especificada anteriormente pode ser correctamente escrita como se segue:
#include <stdio.h>
#include <stdlib.h>
void troca(int *x,int *y){
/*
* Função que troca dois argumentos
*/
int aux;
aux = *x;
*x = *y;
*y = aux;
}
int main(){
int a,b;
printf("Indique dois números: ");
scanf("%d %d",&a,&b);
troca(&a,&b);
printf("a = %d, b= %d\n",a,b);
exit(0);
}
Tal como pode ser observado, a solução adoptada consiste em passar à função não o valor das
variáveis a e b, mas sim os seus endereços. Embora estes endereços sejam passados por valor (ou
seja, a função recebe uma cópia destes valores), o endereço permite à função o conhecimento da
posição das variáveis a b em memória e, deste modo, permite a manipulação do seu conteúdo por
meio de um endereçamento indirecto.
Um hipotético exemplo de um mapa memória associado ao funcionamento do programa
troca encontra-se representado na figura 2.4. Admita-se que a declaração de variáveis no pro-
14 A PONTADORES
Endereço
Conteúdo
..
.
..
.
..
.
..
.
..
.
..
.
..
.
..
.
..
.
Variáveis 2135
do bloco
main()
2136
..
.
Variável
8
a
2
b
..
.
..
.
Endereço
..
.
..
.
2131
Variáveis
da funçao 2132
troca()
2133
Variável
..
.
2
8
x
8
2
y
8
aux
..
.
..
.
..
.
..
.
..
.
..
.
Variáveis 2135
do bloco
main()
2136
..
.
..
.
C
Variável
..
.
8
2
x
y
aux
..
.
..
.
..
.
..
.
..
.
..
.
Variáveis 2135
do bloco
main()
2136
..
.
8
a
2
b
..
.
..
.
B
Conteúdo
..
.
..
.
2131
Variáveis
da funçao 2132
troca()
2133
A
Endereço
Conteúdo
8
a
2
b
..
.
Endereço
Conteúdo
Variável
..
.
..
.
..
.
..
.
..
.
..
.
..
.
..
.
..
.
Variáveis 2135
do bloco
main()
2136
..
.
..
.
8
a
2
b
..
.
D
Figura 2.3: Mapa de memória durante as diferentes fase de execução de um programa que utiliza
a função trocaMal. A - antes da chamada à função, B - no inı́cio de troca, C - no final de
troca, D - após o regresso ao programa principal. O mecanismo de passagem por valor conduz
a que os valores do programa principal não sejam alterados.
F UNÇ ÕES E PASSAGEM POR REFER ÊNCIA 15
Endereço
Conteúdo
..
.
..
.
..
.
..
.
..
.
..
.
..
.
..
.
..
.
Variáveis 2135
do bloco
main()
2136
..
.
Variável
8
a
2
b
..
.
..
.
Endereço
..
.
..
.
2131
Variáveis
da funçao 2132
troca()
2133
Variável
..
.
2135
2136
8
y
aux
..
.
..
.
..
.
..
.
..
.
..
.
2
8
a
8
2
b
..
.
C
..
.
2135
2136
x
y
aux
..
.
..
.
..
.
..
.
..
.
..
.
Variáveis 2135
do bloco
main()
2136
..
.
8
a
2
b
..
.
..
.
Endereço
Conteúdo
Variável
..
.
..
.
..
.
..
.
..
.
..
.
..
.
..
.
..
.
x
..
.
Variáveis 2135
do bloco
main()
2136
Variável
B
Conteúdo
..
.
..
.
2131
Variáveis
da funçao 2132
troca()
2133
A
Endereço
Conteúdo
..
.
Variáveis 2135
do bloco
main()
2136
..
.
..
.
2
a
3
b
..
.
D
Figura 2.4: Mapa de memória durante as diferentes fase de execução do programa que utiliza a
função troca. A - antes da chamada à função, B - no inı́cio de troca C - no final de troca, D após o regresso ao programa principal. A passagem de apontadores para as variáveis do programa
principal (passagem por referência) permite que a função altere as variáveis do programa principal.
16 A PONTADORES
grama principal atribuiu às variáveis A e B os endereços 2135 e 2136, e que estas foram inicializadas pelo utilizador com os valores 8 e 2, respectivamente. A situação imediatamente antes da
chamada da função troca encontra-se representada em A. Durante a chamada da função, realizase a activação das variáveis x, y e aux, locais à função, eventualmente numa zona de memória
afastada daquela onde se encontram as variáveis a e b, sendo as duas primeiras destas variáveis
inicializadas com os endereços de a e b (situação B). Através do endereçamento indirecto através
das variáveis x e y, são alterados os valores das variáveis a e b do programa principal, atingido-se
a situação C. Após o regresso ao programa principal, as variáveis da função troca são libertadas,
atingindo-se a situação representada em D, com as
Note-se que, estritamente falando, a passagem de argumento se deu por valor, atendendo a que
x e y são variáveis locais à função, tendo recebido apenas valores correspondentes ao endereço de
variáveis declaradas no programa principal. No entanto, neste tipo de mecanismo, diz-se também
que as variáveis a e b foram passadas por referência(Martins, 1989), atendendo a que o seu
endereço (e não o seu conteúdo) que foi passadas à função.
Mais genericamente, sempre que é necessário que uma função altere o valor de um ou mais
dos seus argumentos, este ou estes deverão ser passados por referência, de forma a ser possı́vel à
função modificar o valor das variáveis por um mecanismo de indirecção. É por este motivo que,
na chamada da função scanf(), todas variáveis a ler são passados por referência, de modo a ser
possı́vel a esta função poder ler e alterar os valores das variáveis do programa principal.
2.4.2
Erros frequentes
A tentativa de desdobramento do mecanismo de referenciação de uma variável quando uma
dado programa envolve vários nı́veis de funções é um erro frequente de programadores principiantes ou com reduzida experiência de C. Considere-se o seguinte troço de programa, em que se
pretende que a variável x do programa principal seja modificada na função func2. Neste exemplo, o programador adoptou desnecessariamente uma referenciação (cálculo do seu endereço) da
variável a modificar em cada um dos nı́veis de chamada da função:
/*
Utilização incorrecta (desnecessária)
de referências múltiplas.
*/
void func2(int **p2,int b2){
**p2 = -b2 * b2;
}
void func1(int *p1,int b1){
b1 = b1 + 1;
F UNÇ ÕES E PASSAGEM POR REFER ÊNCIA 17
func2(&p1,b1);
}
int main(){
int x;
func1(&x,5);
return 0;
}
Como pode ser facilmente entendido, a referenciação de uma variável uma única vez é suficiente
para que este mesmo endereço possa ser sucessivamente passado entre os vários nı́veis de funções
e ainda permitir a alteração da variável seja sempre possı́vel. Assim, embora o programa anterior
funcione, a referenciação de p1 na passagem de func1 para func2 é inútil: o mecanismo ali
adoptado só faria sentido caso se pretendesse que func2 alterasse o conteúdo da variável p1.
Como é evidente não é esse o caso, e o programa anterior correctamente escrito tomaria a seguinte
forma:
/*
Utilização correcta de uma passagem
por referência entre vários nı́veis
de funções.
*/
void func2(int *p2,int b2){
*p2 = -b2 * b2;
}
void func1(int *p1,int b1){
b1 = b1 + 1;
func2(p1,b1);
}
int main(){
int x;
func1(&x,5);
return 0;
}
Um outro erro frequente em programadores principiantes é passagem ao programa principal
ou função que chama a referência de uma variável local à função evocada. Este tipo de erro pode
ser esquematizado pelo seguinte programa:
int *func(int a){
int b,*c;
b = 2 * a;
c = &b;
return c;
18 A PONTADORES
}
int main(){
int x,*y;
y = func1(1);
x = 2 * *y;
return 0;
}
Aqui, a variável b é local à função func e, como tal, é criada quando func é activada e a
sua zona de memória libertada quando a função termina. Ora o resultado da função func é
passada ao programa principal sob a forma do endereço de b. Quando o valor desta variável é
lido no programa principal por meio de um endereçamento indirecto na expressão x = 2 * *y,
a variável b já não está activa, realizando-se por isso um acesso inválido à posição de memória
especificada pelo endereço em y. Com elevada probabilidade, o resultado final daquela expressão
será incorrecto.
2.5
2.5.1
Vectores e apontadores
Declaração de vectores
Um vector em C permite a criação de uma estrutura com ocorrências múltiplas de uma variável
de um mesmo tipo. Assim, a declaração
int
x[5] = {123,234,345,456,567};
double y[3] = {200.0,200.1,200.2};
declara um vector x de 5 inteiros, indexado entre 0 e 4, e um vector y de 3 reais de dupla precisão, indexado entre 0 e 2, inicializados na própria declaração. Um possı́vel mapa de memória
correspondente a esta declaração encontra-se representado na figura 2.5.1.
Cada elemento individual de um vector pode ser referenciado acrescentando à frente do nome
da variável o ı́ndice, ou posição que se pretende aceder, representado por um inteiro entre [].
Para um vector com N posições, o ı́ndice de acesso varia entre 0 (primeira posição) e N − 1
(última posição). Cada elemento de x e y corresponde a uma variável de tipo inteiro ou double,
respectivamente. Deste modo, se se escrever,
int
x[5] = {123,234,345,456,567};
V ECTORES E APONTADORES 19
Endereço
..
.
Conteúdo
Variável
..
.
..
.
1001
123
x[0]
1002
234
x[1]
1003
345
x[2]
1004
456
x[3]
1005
789
x[4]
1006
200.0
y[0]
1007
1008
y[1]
200.1
1009
1010
1011
..
.
y[2]
200.2
..
.
Figura 2.5: Mapa de memória correspondente à declaração de dois vectores
20 A PONTADORES
double y[3] = {200.0,200.1,200.2};
double a;
a = y[1] + x[3];
o conteúdo final de a será o resultado da soma da segunda posição de y com a quarta posição de
x, ou seja 656.1.
Dado que cada elemento de um vector é uma variável simples, é possı́vel determinar o seu
endereço. Assim, é possı́vel fazer
int
x[5] = {123,234,345,456,567};
double y[3] = {200.0,200.1,200.2};
int
*pi; double *pd;
pi = &(x[2]);
pd = &(y[1]);
conduzindo-se assim à situação representada na figura 2.5.1. Note-se que nas atribuições
pi = &(x[2]) e pd = &(y[1]) os parenteses poderiam ser omitidos, dado que o operador [] (ı́ndice) tem precedência sobre o operador & (endereço de). Assim, aquelas atribuições
poderiam ser escritas como pi = &x[2] e pd = &y[1].
Uma das vantagens da utilização de vectores é o ı́ndice de acesso poder ser uma variável.
Deste modo, inicialização de um vector de 10 inteiros a 0 pode ser feita pela sequência
#define NMAX 10
int main(){
int x[NMAX];
int k;
for(k = 0; k < NMAX ; k++)
x[k] = 0;
/* ...*/
Uma utilização comum dos vectores é a utilização de vectores de caracteres para guardar
texto. Por exemplo a declaração
char texto[18]="Duas palavras";
V ECTORES E APONTADORES 21
Endereço
..
.
Conteúdo
Variável
..
.
..
.
1001
123
x[0]
1002
234
x[1]
1003
345
x[2]
1004
456
x[3]
1005
789
x[4]
1006
200.0
y[0]
1007
1008
y[1]
200.1
1009
1010
y[2]
200.2
1011
1012
1003
pi
1013
1008
pd
..
.
..
.
Figura 2.6: Apontadores e vectores (explicação no texto).
22 A PONTADORES
0
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
texto[18] ’D’ ’u’ ’a’ ’s’ ’ ’ ’p’ ’a’ ’l’ ’a’ ’v’ ’r’ ’a’ ’s’’\0’
Figura 2.7: Utilização de vectores de caracteres para armazenar texto.
cria um vector de 18 caracteres, e inicia as suas primeiras posições com o texto Duas palavras.
Uma representação gráfica deste vector depois de inicializado é apresentada na figura 2.7.
Dado que o texto pode ocupar menos espaço que a totalidade do vector, como sucede neste
caso, a última posição ocupada deste vector é assinalada pela colocação na posição seguinte
à última do caracter com o código ASCII 0, geralmente representado pela constante inteira 0
ou pelo caracter ’\0’. Note-se que esta última representação não deve ser confundida com a
representação do algarismo zero ’0’, internamente representado por 48, o código ASCII de 0.
2.5.2
Aritmética de apontadores
É possı́vel adicionar ou subtrair uma constante inteira de uma variável de tipo apontador. Este
tipo de operação só faz sentido em vectores ou estruturas de dados regulares, em que o avanço ou
recuo de um apontador conduz a um outro elemento do vector (ou estrutura de dados regulares).
É da única e exclusiva responsabilidade do programador garantir que tais operações aritméticas
se mantêm dentro dos endereços válidos da estrutura de dados apontada. Assim, por exemplo, se
na sequência do exemplo e da situação representada na figura 2.5.1 (repetida por conveniência na
figura 2.5.2, A) fossem executadas as instruções
pi = pi + 2;
pd = pd - 1;
a situação resultante seria a representada na figura 2.5.2, B.
No caso do modelo de memória adoptado como exemplo, a operação aritmética sobre o apontador inteiro tem uma correspondência directa com a operação realizada sobre o endereço. No
entanto, o mesmo não sucede com o apontador para double, onde subtracção de uma unidade
ao apontador corresponde na realidade a uma redução de duas unidades no endereço fı́sico da
memória.
De facto, a aritmética de apontadores em C é realizada de forma a que o incremento ou decremento unitário corresponda a um avanço ou recuo de uma unidade num vector, independentemente
do tipo dos elementos do vector. O compilador de C garante o escalamento da constante adicionada
V ECTORES E APONTADORES 23
Endereço
..
.
Conteúdo
Variável
..
.
..
.
Endereço
..
.
Conteúdo
Variável
..
.
..
.
1001
123
x[0]
1001
123
x[0]
1002
234
x[1]
1002
234
x[1]
1003
345
x[2]
1003
345
x[2]
1004
456
x[3]
1004
456
x[3]
1005
789
x[4]
1005
789
x[4]
y[0]
1006
1006
200.0
1007
1008
y[0]
1007
y[1]
200.1
1009
1010
200.0
1008
y[1]
200.1
1009
y[2]
200.2
1011
1010
y[2]
200.2
1011
1012
1003
pi
1012
1005
pi
1013
1008
pd
1013
1006
pd
..
.
..
.
A
..
.
..
.
B
Figura 2.8: Aritmética de apontadores (explicação no texto).
24 A PONTADORES
ou subtraı́da de acordo com a dimensão do tipo apontado. Este modo de operação garante que,
na prática, o programador possa realizar operações sobre apontadores abstraindo-se do número
efectivo de bytes do elemento apontado.
Já anteriormente se mencionou que em C o tipo do apontador depende do objecto apontado, de
modo a ser possı́vel determinar, num endereçamento indirecto, qual o tipo da variável referenciada.
A aritmética de apontadores reforça esta necessidade, dado que o seu incremento ou decremento
exige o conhecimento da dimensão do objecto apontado.
A aritmética de apontadores define apenas operações relativas de endereços. Assim, embora
seja possı́vel adicionar ou subtrair constantes de apontadores, não faz sentido somar apontadores.
Numa analogia simples, considere-se que os endereços são os números da porta dos edifı́cios de
uma dada rua: faz sentido referir “dois números depois do prédio 174” ou “três números antes do
180”, mas não existe nenuma aplicação em que faça sentido adicionar dois números de porta (174
e 180, por exemplo). No entanto, faz sentido referir “o número de prédios entre o 174 e o 180”:
de modo equivalente, também em C a subtracção de apontadores é possı́vel, desde que sejam do
mesmo tipo. Como é evidente, tal como na adição, a subtracção de operadores é convenientemenet
escalada pela dimensão do objecto apontado:
int
x[5] = {123,234,345,456,567};
double y[3] = {200.0,200.1,200.2};
int
*pi1,*pi2; double *pd1,*pd2;
int
di,dd;
pi1 = &x[2]; pi2 = &x[0]; di = pi1 - pi2; /* di <- 2 */
pd1 = &y[1]; pd2 = &y[3]; dd = pd1 - pd2; /* dd <- -1 */
.
Uma última nota relativamente aos apontadores de tipo void. O C-ANSI permite a definição
de apontadores genéricos, cujo tipo é independente do objecto apontado. Um apontador pv deste
tipo manipula um endereço genérico e pode ser simplesmente declarado por
void *pv;
e encontra utilização em situações em que se pretende que uma mesma estrutura possa endereçar
entidades ou objectos de tipos diferentes. Sempre que possı́vel, este tipo de situações deve ser
preferencialmente abordado pela utilização de estruturas do tipo union. No entanto, existem
casos em que tal não é possı́vel, obrigando à utilização deste tipo de apontadores. É, por exemplo,
o caso das funções de gestão de memória, que trabalham com apontadores genéricos (V. secção
3.3). Note-se, no entanto, que o C não consegue desreferenciar automaticamente um apontador
V ECTORES E APONTADORES 25
para void (ou seja, aceder ao conteúdo apontado por). De igual modo, o desconhecimento da
dimensão do objecto apontado impede que a aritmética de apontadores seja aplicável a apontadores
deste tipo.
2.5.3
Índices e apontadores
Dos princı́pios gerais referidos anteriormente, resulta que atribuição do 3o elemento de um
vector x a uma variável a pode ser realizada directamente por
a = x[2];
ou, de forma equivalente, por
a = *(&x[0] + 2);
sendo o resultado idêntico. Enquanto que no primeiro caso se adopta um mecanismo de
indexação directa, no segundo caso determina-se um apontador para o primeiro elemento do
vector, incrementa-se o apontador de duas unidades para endereçar o 3o elemento e, finalmente,
aplica-se o operador “*” para realizar o endereçamento indirecto.
De facto, a segunda expressão pode ser simplificada. O C define que o endereço do primeiro
elemento de um vector pode ser obtido usando simplesmente o nome do vector, sem o operador
de indexação (“[0]”) à frente. Ou seja, no contexto de uma expressão em C, “ &x[0]” é equivalente a usar simplesmente “ x”. Por outras palavras, se x[] é um vector do tipo xpto, x é um
apontador para o tipo xpto. Assim, a expressão “ x[k]” é sempre equivalente a “ *(xk)+”. Este
facto conduz ao que designamos por regra geral de indexação em C, que pode ser enunciada pela
equivalência
x[k] <-> *(x + k)
Registe-se, como curiosidade, que a regra geral de indexação conduz a que, por exemplo,
x[3] seja equivalente a 3[x]. Com efeito,
x[3] <-> *(x+3) <-> *(3+x) <-> 3[x]
Claro que a utilização desta propriedade é geralmente proibido, não pelo C, mas pelas normas de
boa programação!
26 A PONTADORES
2.5.4
Vectores como argumentos de funções
Para usar um vector como argumento de uma função func() basta, no bloco que chama
func(), especifiar o nome da variável que se pretende como argumento. Assim, pode fazer-se,
por exemplo,
int x[10];
/* ... */
func(x);
/* ... */
No entanto, é necessário ter em conta que x, quando usado sem ı́ndice, representa apenas o
endereço da primeira posição do vector. Como deve então ser declarado o argumento formal
correspondente no cabeçalho de func?
Diversas opções existem para realizar esta declaração. No exemplo seguinte, a função set é
utilizada para inicializar os NMAX elementos do vector a do programa principal com os inteiros
entre 1 e NMAX. Numa primeira variante, o argumento formal da função é apenas a repetição da
declaração efectuada no programa principal. Assim,
#define NMAX 100
void set(int x[NMAX],int n){
int k;
for(k = 0; k < n; k++) x[k] = k+1;
}
int main(){
int a[NMAX];
set(a,NMAX);
/* ... */
}
Note-se que para uma função manipular um vector é suficiente conhecer o endereço do
primeiro elemento. Dentro da função, o modo de aceder ao k-ésimo elemento do vector é sempre
adicionar k ao endereço da base, independentemente da dimensão do vector. Ou seja, o parâmetro
formal int x[NMAX] apenas indica que x é um apontador para o primeiro elemento de um vector de inteiros. Deste modo, o C não usa a informação “[NMAX]” no parâmetro formal para aceder
à função. Assim, a indicação explı́cita da dimensão pode ser omitida, sendo válido escrever
void set(int x[],int n){
V ECTORES E APONTADORES 27
int k;
for(k = 0; k < n; k++) x[k] = k+1;
}
Note-se que a possibilidade de omitir a dimensão resulta também da função não necessitar de
reservar o espaço para o vector: a função limita-se a referenciar as células de memória reservadas
no programa principal.
Na passagem de vectores como argumento o C utiliza sempre o endereço da primeira posição,
não existindo nenhum mecanismo previsto que permita passar a totalidade dos elementos do vector por valor. Esta limitação, inerente à própria origem do C, tinha por base a justificação de
que a passagem por valor de estruturas de dados de dimensão elevada é pouco eficiente, dada a
necessidade de copiar todo o seu conteúdo4 .
Atendendo a que a, sem inclusão do ı́ndice, especifica um apontador para primeiro elemento
do vector, uma terceira forma de declarar o argumento formal é
void set(int *x,int n){
int k;
for(k = 0; k < n; k++) x[k] = k+1;
}
Esta última forma sugere uma forma alternativa de escrever o corpo da função set. Com
efeito, para percorrer um vector basta criar um apontador, inicializá-lo com o endereço da primeira
posição do vector e seguidamente incrementá-lo sucessivamente para aceder às posições seguintes.
Esta técnica pode ser ilustrada escrevendo a função
void set(int *x,int n){
int k;
for(k = 0; k < n; k++) *x++ = k+1;
}
Note-se que sendo x um ponteiro cujo valor resulta de uma passagem cópia do endereço de a no
programa principal, é possı́vel proceder ao seu incremento na função de modo a percorrer todos
os elementos do vector. Aqui, a expressão *x++ merece um comentário adicional. Em primeiro
lugar, o operador ++ tem precedência sobre o operador * e, deste modo, o incremento opera sobre
o endereço e não sobre a posição de memória em si. É este apenas o significado da precedência,
4
Na versão original do C, esta limitação estendia-se ao tratamento de estruturas de dados criadas com a directiva
struct, mas esta limitação foi levantada pelo C-Ansi
28 A PONTADORES
o qual não deve ser confundido com a forma de funcionamento do operador incremento enquanto
sufixo: o sufixo estabelece apenas que o conteúdo de x é utilizado antes da operação de incremento
se realizar. Ou seja, *x+=k;+ é equivalente a *x=k;x+;+.
Um outro exemplo de utilização desta técnica pode ser dado escrevendo uma função para
contabilizar o número de caracteres usados de uma string. Atendendo a que se sabe que o último
caracter está seguido do código ASCII 0, esta função pode escrever-se
int conta(char *s){
int n = 0;
while(*s++ != ’\0’) n++;
return n;
}
De facto, esta função é equivalente á função strlen, disponı́vel na biblioteca string.h.
2.6
2.6.1
Matrizes
Declaração
Na sua forma mais simples, a utilização de estruturas multidimensionais em C apenas envolve
a declaração de uma variável com vários ı́ndices, especificando cada um da dimensão pretendida
da estrutura. Por exemplo
float x[3][2];
declara uma estrutura bidimensional de três por dois reais, ocupando um total de seis palavras
de memória no modelo de memória que temos vindo a usar como referência. É frequente uma
estrutura bidimensional ser interpretada como uma matriz, neste exemplo de três linhas por duas
colunas.
Nos modos de utilização mais simples deste tipo de estruturas, o programadador pode abstrairse dos detalhes de implementação e usar a variável bidimensional como uma matriz. Assim, a
inicialização a zeros da estrutura x pode ser efectuada por
float x[3][2];
int k,j;
M ATRIZES 29
Endereço
..
.
Conteúdo
Variável
..
.
..
.
1001
1.0
x[0][0]
1002
2.0
x[0][1]
1003
3.0
x[1][0]
1004
4.0
x[1][1]
1005
5.0
x[2][0]
1006
6.0
x[2][1]
..
.
..
.
Figura 2.9: Mapa de memória correspondente à declaração de uma estrutura de três por dois reais
for(k = 0 ; k < 3 ; k++)
for(j = 0 ; j < 2 ; j++)
x[k][j] = 0.0;
Alternativamente, a inicialização pode ser feita listando os valores iniciais, sendo apenas
necessário agrupar hierarquicamente as constantes de inicialização de acordo com as dimensões
da estrutura:
float x[3][2] = {{1.0,2.0},{3.0,4.0},
{5.0,6.0}};
A disposição em memória desta estrutura é representada esquematicamente na figura 2.9.
2.6.2
Matrizes como argumento de funções
O facto de ser possı́vel omitir a dimensão de um vector na declaração do parâmetro formal de
uma função leva por vezes a pensar que o mesmo pode ser feito no caso de uma matriz. De facto,
a situação não é totalmente equivalente.
Comece-se por regressar à declaração int x[3][2] e observar a forma como é determinado o endereço de x[k][j]. Analisando a figura 2.9, é evidente que o endereço deste elemento é
obtido adicionando ao endereço do primeiro elemento k*2+j. Ou seja,
30 A PONTADORES
x[k][j]
<->
*(&(x[0][0]) + k * 2 +j)
No caso mais genérico da declaração ter a forma <tipo> x[N][M] ter-se-á ainda
x[k][j]
<->
*(&(x[0][0]) + k * M +j)
Ou seja, para aceder a um elemento genérico de uma matriz não basta conhecer o endereço da
primeira posição e o os dois ı́ndices de acesso: é necessário saber também o número de colunas da
matriz. Deste modo, quando uma matriz é passada como argumento de uma função, é necessário
que esta saiba a dimensão das colunas da matriz. Por este motivo, dada a chamada à função
/* ... */
#define NLIN 3
#define NCOL 2
/* ... */
int m[NLIN][NCOL];
int a;
/* ... */
a = soma(m);
/* ... */
o parâmetro formal da função pode repetir na totalidade a declaração da matriz, como em
float norma(float x[NLIN][NCOL]){
int s = 0,k,j;
for(k = 0; k < NLIN ; k++)
for(j = 0; j < NCOL ; j++)
s += x[k][j];
return s;
}
ou pode omitir o número de linhas (dado que, como se mostrou, este número não é indispensável
para localizar o endereço de um elemento genérico da matriz), como em
float norma(float x[][NCOL]){
int s = 0,k,j;
for(k = 0; k < NLIN ; k++)
for(j = 0; j < NCOL ; j++)
s += x[k][j];
return s;
}
M ATRIZES 31
No entanto, a omissão simultânea de ambos os ı́ndices como em
float norma(float x[][]){ /* ERRADO */
int s = 0,k,j;
for(k = 0; k < NLIN ; k++)
for(j = 0; j < NCOL ; j++)
s += x[k][j];
return s;
}
não é possı́vel, gerando um erro de compilação.
Viu-se anteriormente que se o vector int x[NMAX] for utilizado na chamada a uma função,
a declaração a adoptar nos parâmetros formais da função podia ser ou int a[]) ou int *a.
É frequente surgir a dúvida se é possı́vel adoptar uma notação de apontador equivalente no caso
de uma matriz. De facto sim, embora esta notação raramente seja utilizada na prática. No caso do
exemplo que tem vindo a ser utilizado a declaração possı́vel seria
float norma(float (*x)[NCOL]){
int s = 0,k,j;
for(k = 0; k < NLIN ; k++)
for(j = 0; j < NCOL ; j++)
s += x[k][j];
return s;
}
Nesta declaração, x é um apontador para um vector de NCOL floats. Uma explicação mais
detalhada do significado desta invulgar declaração pode ser encontrado na secção 2.6.4.
2.6.3
Matrizes e vectores
Em C, uma matriz não é mais do que um vector de vectores. Ou seja, a declaração
int x[3][2] pode ser interpretada como “ x é um vector de 3 posições, em que cada posição é
um vector de 2 posições”. Esta interpretação é também sugerida pela representação que se adoptou
na figura 2.9. Por outras palavras, x[0], x[1] e x[2] representam vectores de dois elementos
constituı́dos respectivamente por {1.0 , 2.0}, {2.0 , 3.0}, e {4.0 , 5.0}.
Na prática, este facto significa que cada uma das linhas de uma matriz pode ser tratada individualmente como um vector.
32 A PONTADORES
Suponha-se, por exemplo, que dada uma matriz a de dimensão NLIN × NCOL, se pretende
escrever uma função que determine o máximo de cada uma das linhas da matriz e coloque o
resultado num vector y. Esta função pode ser escrita como
void maxMat(float y[],float a[][NCOL]){
int k;
for(k = 0; k < NLIN ; k++)
y[k] = maxVec(a[k],NCOL);
}
onde cada linha foi tratada individualmente como um vector, cujo máximo é determinado pela
função vectorial
float maxVec(float v[],int n){
float m;
int k;
m = v[0];
for(k = 1; k < n; k++)
m = (v[k] > m ? v[k] : m);
return m;
}
De igual forma, considere-se que se pretende calcular o produto matricial
y = Ax
onde A é uma matriz de dimensão N × M e x e y são vectores de dimensão M e N , respectivamente.
Admita-se que o programa principal era escrito como
#define N 3
#define M 2
int main(){
float A[N][M] = {{1,2},{3,4},{5,6}};
float x[M] = {10,20};
float y[N];
int k;
matVecProd(y,A,x);
for(k = 0; k < N ; k++)
printf("%f\n",y[k]);
exit(0);
}
M ATRIZES 33
Atendendo a que o produto de uma matriz por um vector é um vector em que cada elemento
não é mais do que o produto interno de cada linha da matriz com o vector operando, a função
prodMatVec poderia ser escrita como
void matVecProd(float y[],float A[][M],float x[]){
int k;
for(k = 0; k < N ; k++)
y[k] = prodInt(A[k],x,M);
}
com o produto interno definido por
float prodInt(float a[],float b[],int n){
float s = 0.0;
int k;
for(k = 0; k < n; k++)
s += a[k] * b[k];
return s;
}
Uma última situação em que é possı́vel exemplificar a utilização de linhas como vectores é
o do armazenamento de várias linhas de texto. Admita-se, por exemplo, que se pretende ler uma
sequência de linhas de texto e imprimir as mesmas linhas por ordem inversas. Tal é possı́vel através
da utilização de uma matriz de caracteres, utilizando cada linha como uma string convencional:
#include <stdio.h>
#include <stdlib.h>
#include <string.h>
#define NUM_LINHAS 5
#define DIM_LINHA 40
int main(){
char texto[NUM_LINHAS][DIM_LINHA];
int k;
/* Leitura */
printf("Escreva uma sequência de %d linhas:\n",NUM_LINHAS);
for(k = 0;k < NUM_LINHAS; k++){
fgets(texto[k],DIM_LINHA,stdin);
if(texto[k][strlen(texto[k])-1] != ’\n’){
printf("Erro: linha demasiado comprida.\n");
exit(1);
34 A PONTADORES
}
}
/* Escrita */
printf("\nLinhas por ordem inversa:\n");
for(k = NUM_LINHAS-1;k >= 0; k--)
printf("%s",texto[k]);
exit(0);
}
2.6.4
Matrizes e apontadores
Se a utilização de estruturas multidimensionais é relativamente simples e intuitiva, já o mesmo
nem sempre sucede quando é necessário manipular apontadores relacionados com este tipo. 5 O
tratamento de matrizes no C é frequentemente fonte de alvo de dúvidas. Se se perguntar a qualquer
programador de C “dada a declaração int x[3], qual é o tipo de x quando usado isoladamente”,
nenhum terá dúvidas em afirmar que a resposta é “apontador para int”. Experimente-se, no
entanto, a colocar a pergunta semelhante “dada a declaração int x[3][2], qual é o tipo de x
quando usado isoladamente” e, com elevada probabilidade, não será obtida a mesma unanimidade
nas respostas.
Dado que, por consistência sintáctica, se tem sempre
x[k] <-> *(x + k)
então, no caso de uma estrutura bidimensional, terá que ser
x[k][j] <-> *(x[k] + j)
e, portanto, se x[k][j] é por exemplo do tipo float, x[k] é um apontador para float. Consultando novamente o exemplo da figura 2.9, significa isto que x[0] corresponde a um apontador
para float com o valor 1001 (e portanto o endereço do primeiro elemento do vector de floats
formado pelos reais 1.0 e 2.0, enquanto que x[2] corresponde também a um apontador, cujo
valor é 1003 (primeiro elemento do vector de floats formado pelos reais 3.0 e 4.0).
Considere-se agora, novamente, a questão de qual o tipo de x, quando considerado isoladamente. Como já se disse anteriormente em C, uma estrutura multidimensional representa sempre
5
A leitura desta secção pode ser omitida numa abordagem introdutória da linguagem C.
M ATRIZES 35
uma hierarquia de vectores simples. Ou seja, x[3][2] representa um vector de três elementos,
em que cada um é por sua vez um vector de dois elementos. Assim, x[k] representa sempre um
vector de dois floats. Com esta formulação, resulta claro que x representa um apontador para
um vector de dois floats. Isto não é mais do que a generalização da situação dos vectores, em que
dada a declaração int a[N], se sabe que a isoladamente é um apontador para inteiro.
Assim, é natural que x sem ı́ndices especifique o endereço do primeiro elemento de um vector
de três elementos, em que cada um é um vector de dois floats. Ou seja, no nosso exemplo, x
corresponde ao valor 1001.
Mas, afinal, qual a diferença entre um apontador para float e um apontador para um vector de floats? Por um lado, a forma de usar este tipo variável num endereçamento indirecto
é claramente diferente. Por exemplo, x e &x[0][0] correspondem ao mesmo valor (1001 no
nosso exemplo), mas são tipos diferentes: o primeiro é um apontador para um vector, pelo que *x
é um vector (a primeira linha de x, enquanto que *(&x[0][0]) é um float (o conteúdo de
x[0][0]. No entanto, é provavelmente mais importante reter que a diferença fundamental reside
na dimensão do objecto apontado. Considere-se novamente o exemplo que temos vindo a considerar. Uma variável do tipo apontador para float, cujo valor seja 1001, quando incrementada
passa a ter o valor 1002. Mas uma variável do tipo apontador para vector de dois float, cujo
valor seja 1001, quando incrementada passa a ter o valor 1003 (já que o incremento é escalado
pela dimensão do objecto apontado).
É interessante verificar que este modelo é o único que permite manter a consistência sintáctica
do C na equivalência entre vectores e apontadores. Já se disse que sendo sempre
x[k] <-> *(x + k)
então,
x[k][j] <-> *(x[k] + j)
O que não se disse antes, mas que também se verifica, é que a primeira destas regras também deve
ser aplicável à entidade x[k] que surge na última expressão. Ou seja, tem-se
x[k][j] <-> *(*(x+k) + j)
o que exige por outro lado estabelecer que
36 A PONTADORES
Expressão
Tipo
Valor
x
Apontador para vector
de dois floats
Apontador para vector
de dois floats
Apontador para float
Apontador para float
float
Apontador para float
float
float
Apontador para float
1001
Elemento da
estrutura
-
1003
-
1003
1006
6.0
1001
1.0
2.0
1003
x[2][1]
x[0][0]
x[0][1]
-
x+1
*(x+1)
*(x+2)+1
*(*(x+2)+1)
*x
**x
*(*x+1)
x[1]
Tabela 2.1: Exemplos de tipos e valores derivados do exemplo da figura 2.9.
• Se a é um apontador para um escalar, *a é desse tipo escalar, e o valor de *a é o conteúdo
do endereço especificado por a.
• Se a é um apontador para um vector de elementos de um dado tipo, *a é um apontador para
um elemento do tipo constituinte, e o seu valor é idêntico ao de a.
Um factor que contribui frequentemente para alguma confusão deriva do facto de que, ainda
que x não seja sintacticamente um duplo apontador para float, sendo
x[0][0] <-> *(*(x+0) + 0) <-> **x
verifica-se que **x é um float.
A consistência destas equivalências podem ser verificada considerando casos particulares do
exemplo que tem vindo a ser utilizado como referência, tal como listados na tabela 2.1. O código
de um pequeno programa que permite validar esta tabela está listado no apêndice A.
Como é natural, é possı́vel declarar um apontador para um vector de dois floats, sem ser
da forma implı́cita que resulta da declaração da matriz. A declaração de uma variável y deste tipo
pode ser feita por
float (*y)[2];
Por este motivo, que quando a matriz x é passada por argumento para uma função func, a
M ATRIZES 37
declaração do parâmetro formal poder ser feita repetindo a declaração total, omitindo a dimensão
do ı́ndice interior, ou então por
void func(float (*y)[2]);
tal como se referiu na secção 2.6.2.
Dado que este tipo de declarações é alvo frequente de confusão, é conveniente saber que existe
uma regra de leitura que ajuda a clarificar a semântica da declaração. Com efeito, é suficiente
“seguir” as regras de precedência, procedendo à leitura na seguinte sequência:
float (*y)[3]
yé
um apontador
para um vector de três
floats
Sublinhe-se que, face a tudo o que ficou dito anteriormente, não é possı́vel declarar um apontador para um vector sem especificar a dimensão do vector: como já foi dito por diversas vezes,
um apontador tem que conhecer a dimensão do objecto apontado. Isto não é possı́vel sem especificar a dimensão do vector. Como corolário, um apontador para um vector de três inteiros é de
tipo distinto de um apontador para um vector para seis inteiros, não podendo os seus conteúdos
ser mutuamente atribuı́dos.
Note-se que a declaração que se acabou de referir é claramente distinta de
float *y[2];
onde, devido à ausência de parenteses, é necessário ter em atenção a precedência de “[]” sobre o
“*”. Neste caso, y é um vector de dois apontadores para float, podendo a leitura da declaração
ser realizada pela sequência:
float *y[3]
yé
um vector de três
apontadores
para float
A utilização de vectores de apontadores é abordada em maior detalhe na secção 3.5.4.
Finalmente, refira-se que os apontadores para vectores podem ainda surgir noutros contextos:
dada a declaração int x[10], x é um apontador para inteiro, mas a expressão &x é do tipo
38 A PONTADORES
apontador para um vector de 10 inteiros.
2.7
Generalização para mais do que duas dimensões
A generalização do que ficou dito para mais do que duas dimensões é directa. Considere-se,
como referência, a declaração da estrutura
int x[M][N][L];
1. No cálculo do endereço de qualquer elemento da estrutura tem-se a igualdade:
&(x[m][n][l]) == (&x[0][0][0]) + m * (N*L) + n * L + l
2. x[k][j] é um apontador para inteiro.
3. x[k] é um apontador para um vector de L inteiros.
4. x é um apontador para uma matriz de N×L inteiros.
5. Em geral,
x[m][n][l] == *(*(*(x+m)+n)+l)
A passagem de uma estrutura multidimensional como argumento pode ser feita pela repetição
da declaração completa do tipo. Assim, uma declaração possı́vel é
#define M ...
#define N ...
#define L ...
void func(int x[M][N][L]){
/* ... */
}
int main(){
int x[M][N][L];
/*...*/
func(x);
/*...*/
return 0;
}
G ENERALIZAÇ ÃO PARA MAIS DO QUE DUAS DIMENS ÕES 39
Como se mostrou anteriormente, o cálculo do endereço de um elemento genérico de uma estrutura tridimensional exige o conhecimento das duas dimensões exteriores da estrutura (N e L no
exemplo). A generalização desta regra mostra que para calcular o endereço de um elemento de
uma estrutura n-dimensional é necessário conhecer com rigor os n − 1 ı́ndices exteriores da estrutura. Deste modo, nos argumentos formais de uma função é sempre possı́vel omitir a dimensão
do primeiro ı́ndice de uma estrutura multidimensional, mas não mais do que esse. No exemplo
anterior, pode então escrever-se
void func(int x[][N][L]){
/* ... */
}
Claro que todas as outras variantes em que exista consistência sintáctica entre os argumentos
formais e actuais do procedimento são válidas. Assim, pelas mesmas razões já detalhadas na
secção 2.6.4,
void func(int (*x)[N][L]){
/* ... */
}
é uma alternativa sintacticamente correcta neste caso.
Capı́tulo 3
Vectores e memória dinâmica
3.1
Introdução
Até ao aparecimento da linguagem C, a maioria das linguagens de alto nı́vel exigia um dimensionamento rı́gido das variáveis envolvidas. Por outras palavras, a quantidade máxima de memória
necessária durante a execução do programa deveria ser definida na altura de compilação do programa. Sempre que os requisitos de memória ultrapassavam o limite fixado durante a execução
do programa, este deveria gerar um erro. A solução nestes casos era recompilar o programa aumentando a dimensão das variáveis, solução só possı́vel se o utilizador tivesse acesso e dominasse
os detalhes do código fonte. Por exemplo, um programa destinado à simulação de um circuito
electrónico poderia ser obrigado a definir no código fonte o número máximo de componentes
do circuito. Caso este número fosse ultrapassado, o programa deveria gerar um erro, porque a
memória reservada durante a compilação tinha sido ultrapassada. A alternativa nestas situações
era a reserva à partida de uma dimensão de memória suficiente para acomodar circuitos de dimensão elevada, mas tal traduzia-se obviamente num consumo excessivo de memória sempre que
o programa fosse utilizado para simular circuitos de dimensão reduzida. Em alguns casos, os programas recorriam à utilização de ficheiros para guardar informação temporária, mas esta solução
implicava geralmente uma complexidade algorı́tmica acrescida.
Tal como o nome indica, os sistemas de memória dinâmica permitem gerir de forma dinâmica
os requisitos de memória de um dado programa durante a sua execução. Por exemplo, no caso
do sistema de simulação referido anteriormente, o programa pode, no inı́cio da execução, determinar a dimensão do circuito a simular e só nessa altura reservar a memória necessária. Com
esta metodologia, o programa pode minimizar a quantidade de memória reservada e, deste modo,
permitir que o sistema operativo optimize a distribuição de memória pelos vários programas que
42 V ECTORES E MEM ÓRIA DIN ÂMICA
se encontram simultaneamente em execução. No entanto, até ao aparecimento do C este tipo
de mecanismos, caso estivessem disponı́veis no sistema operativo, eram apenas acessı́veis em
linguagem máquina ou Assembler, mais uma vez pela necessidade de manipular directamente
endereços de memória.
Apesar da flexibilidade oferecida, a gestão directa da memória dinâmica exige algumas
precauções suplementares durante o desenvolvimento do código. Por este motivo, muitas linguagens de programação de alto-nı́vel mais recentes (Lisp, Java, Scheme, Python, Perl, Mathematica,
entre outras) efectuam a gestão automática da memória dinâmica, permitindo assim que o programador se concentre na implementação algorı́tmica e nos modelos de dados associados, sem se
preocupar explicitamente com os problemas de dimensionamento de variáveis ou os volumes de
memória necessários para armazenamento de dados.
Neste contexto, poderá perguntar-se quais as vantagens de programar em C ou porque é que
o C ainda mantém a popularidade em tantas áreas de aplicação. Há diversas respostas para esta
questão:
• A gestão directa da memória dinâmica permite normalmente a construção de programas
com maior eficiência e com menores recursos computacionais.
• Dada a evidente complexidade dos compiladores de linguagens mais elaboradas, é frequente
microprocessadores e controladores especializados (processadores digitais de sinal, microcontroladores, etc) apenas disporem de compiladores para a linguagem C, a qual se encontra
mais próximo da linguagem máquina do que linguagens conceptualmente mais elaboradas.
Por este motivo, o C ainda se reveste hoje de uma importância crucial em diversas áreas da
Engenharia Electrotécnica, nomeadamente em aplicações que implicam o recurso a microcontroladores especializados.
• Dada a sua proximidade com o hardware1 , a maioria dos sistemas operativos actualmente
existentes são ainda hoje programados na linguagem C.
• A maioria dos compiladores de linguagens de alto nı́vel, incluindo o próprio C, são actualmente escritos e desenvolvidos em C. Ou seja, nesta perspectiva, o C é hoje uma linguagem
indispensável à geração da maioria das outras linguagens, constituindo, neste sentido, a
“linguagem das linguagens”.
1
O C é frequentemente designado na gı́ria como um Assembler de alto nı́vel, apesar do evidente paradoxo contido
nesta designação.
V ECTORES 43
3.2
Vectores
Em C, um vector é uma colecção com um número bem definido de elementos do mesmo tipo.
Ao encontrar a declaração de um vector num programa, o compilador reserva automaticamente
espaço em memória para todos os seus elementos. Por razões de clareza e de boa prática de
programação, estas constantes são normalmente declaradas de forma simbólica através de uma
directiva define, mas a dimensão continua obviamente a ser uma constante:
#define DIM_MAX 100
#define DIM_MAX_STRING 200
int
char
x[DIM_MAX];
s[DIM_MAX_STRING];
Por outras palavras, a necessidade de saber quanta memória é necessária para o vector que se
pretende utilizar implica que a dimensão deste vector seja uma constante, cujo valor já conhecido
durante a compilação do programa.
Como é sabido, as variáveis locais a uma função têm um tempo de vida limitado à execução
da função2 . O espaço para estas variáveis é reservado na chamada zona da pilha (stack), uma
região de memória dedicada pelo programa para armazenar variáveis locais e que normalmente é
ocupada por ordem inversa. Por outras palavras, são usados primeiros os endereços mais elevados
e vão sendo sucessivamente ocupados os endereços inferiores à medida que são reservadas mais
variáveis locais. Dada a forma como se realiza esta ocupação de memória, o limite inferior da
região da pilha é geralmente designada por topo da pilha. Neste sentido, quando uma função
é chamada, o espaço para as variáveis locais é reservado no topo da pilha, que assim decresce.
Quando uma função termina, todas as variáveis locais são libertadas e o topo da pilha aumenta
novamente. Assim, por exemplo, dada a declaração
int function(int z){
int a;
int x[5];
int b;
/* ... */
a chamada da função func poderia dar origem a uma evolução do preenchimento da memória da
forma como se representa na figura 3.1.
2
Excepto se a sua declaração for precedido do atributo static, mas este só é usado em circunstâncias excepcionais.
44 V ECTORES E MEM ÓRIA DIN ÂMICA
Endereço
..
.
Conteúdo
Variável
..
.
..
.
Endereço
..
.
Conteúdo
Variável
..
.
..
.
1001
1001
topo da pilha
1002
1002
b
1003
1003
x[0]
1004
1004
x[1]
1005
1005
x[2]
1006
1006
x[3]
1007
1007
a
1008
1008
z
1009
1009
...
..
.
..
.
topo da pilha
A
..
.
..
.
B
Figura 3.1: Mapa de memória antes e após a chamada à função func (A) e mapa de memória
durante a execução da função (B).
A necessidade da dimensão dos vectores ser conhecida na altura da compilação conduz à
impossibilidade de declarações do tipo
int function(int n){
int x[n]; /* MAL: n é uma variável, e o seu valor é desconhecido
na altura da compilação */
/* ... */
Como é evidente, os elementos de um vector podem não ser escalares simples como no exemplo anterior. Os elementos de um vector podem ser estruturas de dados, como por exemplo
em
#define MAX_NOME
200
#define MAX_ALUNOS 500
typedef struct _tipoAluno {
int numero;
char nome[MAX_NOME];
} tipoAluno;
V ECTORES 45
int main(){
tipoAluno alunos[MAX_ALUNOS];
/* ... */
ou mesmo outro vector. Com efeito, na declaração
int mat[10][5]
a matriz mat, do ponto de vista interno do C, não é mais do que um vector de 10 elementos, em
que cada elemento é por sua vez um vector de 5 inteiro (V. secção 2.6.3).
A necessidade de definir de forma rı́gida a dimensão dos vectores na altura da compilação
obriga frequentemente ao estabelecimento de um compromisso entre a dimensão máxima e a
eficiência do programa em termos da memória utilizada. Uma solução possı́vel é utilizar um
majorante dos valores “tı́picos”. Considere-se novamente um sistema para simulação de circuitos
electrónicos. Se os sistemas que se pretende simular têm em média 1000 componentes, poderse-ia utilizar um valor de 2000 ou 5000 para dimensionar o vector de componentes. No entanto,
a utilização de um valor máximo elevado pode conduzir a situações frequentes de desperdı́cio
de memória, com o programa a reservar à partida volumes de memória muito superiores aos
necessários, enquanto que um valor reduzido deste parâmetro pode limitar seriamente a dimensão
dos problemas a abordar. Por outro lado, é por vezes difı́cil encontrar parâmetros razoáveis para
definir “valor médio”. Em determinadas aplicações, 50 componentes pode ser um valor razoável,
noutras 10,000 pode ser um valor reduzido. Para agravar a situação, a dimensão de memória que
é razoável reservar à partida depende da memória fı́sica disponı́vel no sistema em que se está a
trabalhar: sistemas com 8MB ou 8GB de memória conduzem obviamente a situações distintas.
Não se pretende com esta análise colocar de parte todas as utilizações de vectores convencionais com dimensão fixa. Frequentemente, esta é uma solução mais que razoável. Por exemplo,
uma linha de texto numa consola de texto tem em geral cerca de 80 caracteres, pelo que a definição
de um valor máximo para o comprimento de uma linha de 160 ou 200 caracteres é um valor que
pode ser razoável e que não é excessivo na maioria das aplicações. No entanto, em situações
em que o número de elementos pode variar significativamente, é desejável que a memória seja
reservada à medida das necessidades.
46 V ECTORES E MEM ÓRIA DIN ÂMICA
3.3
“Vectores” dinâmicos
Uma forma de ultrapassar a dificuldade criada pelo dimensionamento de vectores é a reserva
de blocos de memória só ser realizada durante a execução do programa. Considere-se novamente
o simulador de circuitos electrónicos. A ideia essencial é iniciar o programa com um volume de
memória mı́nimo, determinar qual o número de componentes do sistema a simular e só depois
deste passo reservar espaço para manipular o número de componentes pretendido.
Recorde-se que ao declarar um vector
int x[MAX_DIM]
a utilização do nome do vector sem especificar o ı́ndice é equivalente ao endereço do ı́ndice 0 do
vector. Por outras palavras, a utilização no programa de x é equivalente a &x[0].Decorre também
daqui a regra geral de indexação em C:
x[k] <-> *(x + k)
equivalência que é universal em C.
A utilização de um bloco de memória criado dinamicamente e que pode ser utilizado com
mecanismos de acesso idênticos aos de um vector pode ser realizado declarando uma variável
de tipo de apontador e solicitando ao sistema operativo a reserva de um bloco de memória da
dimensão pretendida. O pedido de reserva de memória ao sistema operativo é efectuado através
de um conjunto de funções declaradas no ficheiro stdlib.h. Uma das funções utilizáveis para
este efeito tem como protótipo
void *calloc(size_t nmemb, size_t size);
A função calloc reserva um bloco de memória contı́gua com espaço suficiente para armazenar
nmemb elementos de dimensão size cada, devolvendo o endereço (apontador) para a primeira
posição do bloco. size_t é o tipo utilizado para especificação de dimensões numéricas em várias
funções do C e a sua implementação pode ser dependente do sistema operativo, mas corresponde
geralmente a um inteiro sem sinal. O tipo de retorno, void*, corresponde a um endereço genérico
de memória. o que permite que a função seja utilizada independentemente do tipo especı́fico do
apontador que se pretende inicializar. A função retorna um apontador para o primeiro endereço de
“V ECTORES ” DIN ÂMICOS 47
uma região de memória livre da dimensão solicitada. Caso esta reserva não seja possı́vel, a função
retorna NULL, para indicar que a reserva não foi efectuada.
Considere-se, como exemplo, um programa para cálculo da média e variância de N valores
reais indicados pelo programador. Em vez de utilizar um vector de dimensão fixa, é possı́vel
utilizar apenas um apontador para um real e um programa com a seguinte estrutura:
/* Ficheiro: media.c
Conteúdo: Programa para cálculo da média e variânicia
Autor:
Fernando M. Silva, IST ([email protected])
História : 2001/06/01 - Criação
*/
#include <stdio.h>
#include <stdlib.h>
int main(){
int n;
/* Número de valores */
float *f; /* Apontador para o primeiro valor */
float soma,media,variancia;
int k;
printf("Indique quantos valores pretende utilizar: ");
scanf("%d",&n);
f = (float*) calloc(n,sizeof(float));
/* reserva de memória
para um bloco de n
reais */
if(f == NULL){
/* Teste da reserva de memória */
fprintf(stderr,"Erro na reserva de memória\n");
exit(1);
}
/* A partir deste ponto, f pode ser tratado como um
vector de n posições */
for( k = 0 ; k < n ; k++){
printf("Indique o valor ı́ndice %d : ",k);
scanf("%f",&f[k]);
}
soma = 0.0;
for( k = 0 ; k < n ; k++)
soma += f[k];
media = soma / n;
/* cálculo da média */
soma = 0.0;
48 V ECTORES E MEM ÓRIA DIN ÂMICA
for( k = 0 ; k < n ; k++)
soma += (f[k] - media) * (f[k] - media);
variancia = soma / n;
/* cálculo da var. */
printf("Média = %5.2f, var = %5.2f\n",
media, variancia);
free(f);
exit(0);
}
Na chamada à função calloc(), dois aspectos devem ser considerados. Em primeiro lugar o operador sizeof() é um operador intrı́nseco do C que devolve a dimensão (geralmente em bytes)
do tipo ou variável indicado no argumento. Por outro lado, à esquerda da função calloc() foi
acrescentada e expressão (float*). Esta expressão funciona como um operador de cast, obrigando à conversão do apontador genérico devolvido pela função calloc para um apontador para
real. Em geral, na operação de cast é indicado o tipo do apontador que se encontra do lado esquerdo da atribuição. Embora este cast não seja obrigatório, é geralmente utilizado na linguagem
C como uma garantia adicional da consistência das atribuições.
Após a reserva dinâmica de memória, o apontador f pode ser tratado como um vector convencional. Como é evidente, o ı́ndice não deve ultrapassar a posição n − 1, dado que para valores
superiores se estaria a aceder a posições de memória inválidas.
Enquanto que as variáveis locais são criadas na zona da pilha, toda a memória reservada
dinamicamente é geralmente criada numa região independente de memória designada por heap
(molhe). Admita-se, no caso do programa para cálculo das médias e variâncias, que o valor de n
especificado pelo utilizador era 4. Uma possı́vel representação do mapa de memória antes e após
a chamada da função calloc encontra-se representado na figura 3.2.
3.4
Gestão da memória dinâmica
3.4.1
Verificação da reserva de memória
Como já se referiu, ao efectuar uma reserva dinâmica de memória é essencial testar se os recursos solicitados foram ou não disponibilizados pelo sistema. Com efeito, a reserva de memória
pode ser mal sucedida por falta de recursos disponı́veis no sistema. Este teste teste e deve ser sempre efectuado testando o apontador devolvido pela função calloc(). Quando existe um erro,
a função devolve o endereço 0 de memória, o qual é representado simbolicamente pela constante
G EST ÃO DA MEM ÓRIA DIN ÂMICA 49
Zona da pilha (var. locais)
Endereço
..
.
Conteúdo
Zona do heap (var. dinamicas)
Variável
Endereço
..
.
..
.
..
.
...
1001
k
2102
1003
variancia
2103
1004
media
2104
1005
soma
2105
1006
f
2106
n
2107
...
2108
4
1008
1009
..
.
Variável
..
.
..
.
...
2101
1002
1007
Conteúdo
topo
...
2109
..
.
..
.
..
.
A
Zona da pilha (var. locais)
Endereço
..
.
Conteúdo
..
.
Zona do heap (var. dinamicas)
Variável
Endereço
..
.
..
.
...
1001
Conteúdo
Variável
..
.
..
.
...
2101
1002
k
2102
*f
1003
variancia
2103
*(f+1) <−> f[1]
1004
media
2104
*(f+2) <−> f[2]
1005
soma
2105
*(f+3) <−> f[3]
f
2106
n
2107
...
2108
1006
1007
2102
4
1008
1009
..
.
<−>f[0]
topo
...
2109
..
.
..
.
..
.
B
Figura 3.2: Mapa de memória antes da reserva de memória (A) e após a reserva de memória. (B).
50 V ECTORES E MEM ÓRIA DIN ÂMICA
NULL (definida em stdio.h). Se o endereço devolvido tiver qualquer outro valor, a reserva de
memória foi bem sucedida, e o programa pode continuar a sua execução normal.
3.4.2
Outras funções de gestão de memória dinâmica
Função free()
Enquanto que a função calloc() efectua uma reserva dinâmica de memória, a função
free(p) liberta o bloco de memória apontado por p. Como seria de esperar, esta função só
tem significado se o apontador p foi obtido por uma função prévia de reserva de memória, como
a função calloc() descrita anteriormente.
De um modo geral, é boa prática de programação libertar toda a memória reservada pelo
programa sempre que esta deixa de ser necessária. Isto sucede frequentemente pela necessidade
de libertar memória que só foi necessária temporariamente pelo programa.
Note-se que sempre que o programa termina toda a memória reservada é automaticamente libertada. Deste modo, a libertação explı́cita da memória reservada durante a execução do programa
não é estritamente obrigatória antes de sair do programa através da função exit() ou da directiva return no bloco main(). Apesar deste facto, alguns autores consideram que, por razões
de consistência e arrumação do código, o programa deve proceder à libertação de toda a memória
reservada antes de ser concluı́do. É este o procedimento adoptado no programa para cálculo da
variância, onde a função free() é chamada antes do programa terminar.
Função malloc()
A função malloc() tem por protótipo
void *malloc(size_t total_size);
onde total_size representa a dimensão total da memória a reservar, expressa em bytes. A
função malloc() é muito semelhante à função calloc() A forma calloc(n,d) pode ser
simplesmente substituı́da por malloc(n*d). A única diferença formal entre as duas funções é
que enquanto a função calloc() devolve um bloco de memória inicializado com zero em todas
as posições, a função malloc() não efectua explicitamente esta inicialização.
G EST ÃO DA MEM ÓRIA DIN ÂMICA 51
Função realloc()
A função realloc() pode ser utilizada sempre que é necessário modificar a dimensão de
um bloco de memória dinâmica reservado anteriormente. O protótipo da função é
void *realloc(void *old_ptr,size_t total_new_size);
onde old_ptr é o apontador para o bloco de memória reservado anteriormente, enquanto que
total_new_size é a dimensão total que se pretende agora para o mesmo bloco. A função
retorna um apontador para o bloco de memória redimensionado. Note-se que o segundo argumento
tem um significado semelhante ao da função malloc.
Suponha-se, por exemplo, que no inı́cio de um programa tinha sido reservado um bloco de
memória para a n inteiros:
int main(){
int *x,n;
/* Obtenção do valor de n ... */
x = (int*) calloc(n,sizeof(int));
mas que, mais tarde, se verificou a necessidade de acrescentar 1000 posições a este bloco de
memória. Este resultado pode ser obtido fazendo
x = (int*) realloc(x,(n+1000)*sizeof(int));
O funcionamento exacto da função realloc() depende das disponibilidades de memória
existentes. Suponha-se, para assentar ideias, que inicialmente se tinha n=2000, e que o valor de x
resultante da função calloc era 10000 (figura 3.3, A). Deste modo o bloco de memória reservado
inicialmente estendia-se do endereço 10000 ao endereço 11999. Quando mais tarde é chamada a
função realloc duas situações podem ocorrer. Se os endereços de memória entre 12000 e 12999
estiverem livres, o bloco de memória é prolongado, sem mudança de sı́tio, pelo que o valor de x
permanece inalterado (figura 3.3, B). No entanto, se algum endereço entre 12000 e 12999 estiver
ocupado (figura 3.3, C), é necessário deslocar todo o bloco de memória para uma nova região.
Neste caso, o novo bloco de memória pode ser mapeado, por exemplo, entre os endereços 12500
e 15499 (figura 3.3, D), retornando a função realloc o novo endereço da primeira posição de
memória (12500). Como complemento, a função realloc trata de copiar automaticamente todo
52 V ECTORES E MEM ÓRIA DIN ÂMICA
o conteúdo guardado nos endereços 10000 a 11999 para os endereços 12500 a 14499 e liberta as
posições de memória iniciais.
3.4.3
Garbbage
Como referido anteriormente, o espaço de memória para as variáveis locais é reservado na
zona de memória da pilha quando uma função é chamada, sendo automaticamente libertado (e
com ele as variáveis locais) quando a função termina.
Ao contrário das variáveis locais, a memória dinâmica é criada e libertada sob controlo do
programa, através das chamadas às funções calloc(), malloc() e free().
Em programas complexos, é frequente um programa reservar blocos de memória que, por
erro do programador ou pela própria estrutura do programa, não são libertados mas para os quais
se perdem todos os apontadores disponı́veis. Neste caso, o bloco de memória dinâmica é reservado, mas deixa de ser acessı́vel porque se perderam todos os apontadores que indicavam a sua
localização em memória. Estes blocos de memória reservados mas cuja localização se perdeu são
geralmente designados por “garbbage” (lixo).
Considere-se, por exemplo, o seguinte, programa:
void func(){
int *x,y;
y = 3;
x = (int*) calloc(y,sizeof(int));
/* ... Utilização de x, free()
não chamado...
*/
}
void main()
int a,b;
func();
/* O Bloco reservado em func deixou de ser
usado, mas deixou de estar inacessı́vel */
Um mapa de memória ilustrativo desta situação está representado na figura 3.4.
G EST ÃO DA MEM ÓRIA DIN ÂMICA 53
Zona da pilha (var. locais)
Zona da pilha (var. locais)
Endereço
Conteúdo
..
.
Variável
Endereço
..
.
..
.
2000
1003
10000
Conteúdo
..
.
...
1001
1002
10000
n
10001
11999
1006
12000
1007
12001
...
..
.
...
Endereço
..
.
Conteúdo
Variável
Endereço
..
.
..
.
1001
2000
..
.
1003
10000
1765
1005
n
1008
12003
1009
..
.
..
.
...
12999
..
.
Endereço
..
.
...
1001
1002
Conteúdo
..
.
2000
1003
10000
Conteúdo
..
.
10000
666
10001
−300
x
1004
2000
1003
12500
..
.
..
.
n
..
.
...
10001
−300
..
.
11999
1005
1009
1006
12000
1007
12001
11111111
12002
−555555
...
1009
..
.
C
12001
11111111
12002
−555555
...
Memoria
libertada
..
.
..
.
Memoria ocupada
por outras var. dinamicas
12500
666
12501
−300
..
.
14599
..
.
12003
..
.
1765
...
12000
1008
..
.
Variável
..
.
..
.
666
x
1004
1765
Conteúdo
10000
Variável
1007
11999
..
.
Endereço
...
1002
..
.
1005
1008
Zona do heap (var. dinamicas)
Variável
1006
n
..
.
B
Zona do heap (var. dinamicas)
..
.
1765
..
.
1001
..
.
...
12000
..
.
..
.
Variável
..
.
..
.
Zona da pilha (var. locais)
..
.
−300
1007
Endereço
Conteúdo
666
10001
11999
A
Endereço
10000
1006
12002
Variável
..
.
x
1004
Memoria livre
..
.
Zona da pilha (var. locais)
Conteúdo
..
.
...
1002
−300
1005
1009
..
.
666
x
1008
Variável
..
.
1004
..
.
Zona do heap (var. dinamicas)
Zona do heap (var. dinamicas)
..
.
Memoria
"realocada"
..
.
..
.
D
Figura 3.3: Mapa de memória após a chamada à função calloc() (A) e após a função
realloc() (B), se existir espaço disponı́vel nos endereços contı́guos. Em (C) e (D) representase a situação correspondente no caso em que a memória dinâmica imediatamente a seguir ao bloco
reservado está ocupada, sendo necessário deslocar todo o bloco para outra zona de memória. Neste
caso, o apontador retornado pela função é diferente do inicial.
54 V ECTORES E MEM ÓRIA DIN ÂMICA
Zona da pilha (var. locais)
Endereço
..
.
Conteúdo
Zona do heap (var. dinamicas)
Variável
Endereço
..
.
..
.
..
.
...
1001
Conteúdo
Zona da pilha (var. locais)
Variável
Endereço
..
.
..
.
..
.
...
2101
Conteúdo
Zona do heap (var. dinamicas)
Variável
..
.
..
.
..
.
...
1001
2102
1003
2103
1003
1004
2104
1004
2105
1005
1006
b
2106
1007
a
2107
topo
1006
b
2106
1007
a
2107
1008
2108
1009
2109
..
.
..
.
..
.
1002
...
2102
..
.
...
2102
x[0]
2103
x[1]
y
2104
x[2]
2105
2108
1009
2109
..
.
Variável
..
.
x
1008
..
.
Conteúdo
2101
topo
1002
1005
topo
Endereço
..
.
..
.
A
topo
...
..
.
B
Zona da pilha (var. locais)
Endereço
..
.
Conteúdo
Zona do heap (var. dinamicas)
Variável
Endereço
..
.
..
.
..
.
...
1001
Conteúdo
Variável
..
.
..
.
...
2101
1002
2102
x[0]
1003
2103
x[1]
1004
2104
x[2]
1005
topo
2105
1006
b
2106
1007
a
2107
1008
2108
1009
2109
..
.
..
.
..
.
topo
...
..
.
C
Figura 3.4: Criação de “garbbage” (lixo). Mapa de memória (exemplo do texto): (A) antes da
chamada à função func, (B) no final da função func e (C) após retorno ao programa principal. De notar que em (C) a memória dinâmica ficou reservada, mas que se perderam todas as
referências que permitiam o acesso a esta zona de memória.
C RIAÇ ÃO DIN ÂMICA DE MATRIZES 55
3.5
3.5.1
Criação dinâmica de matrizes
Introdução
A criação e utilização de estruturas dinâmicas em C que possam ter um acesso equivalente
a uma matriz é simples. No entanto, a compreensão detalhada de como funcionam este tipo de
estruturas nem sempre é claro.
De modo a simplificar a exposição, começar-se-á por apresentar na secção 3.5.2 um resumo do
modo de declaração e de acesso de matrizes estáticas. Seguidamente, na secção 3.5.3, descreve-se
uma metodologia simples para criar dinamicamente vectores de apontadores com um comportamento equivalente ao de uma matriz. Seguidamente, na secção 3.5.4 serão discutidas as diferenças
e semelhanças entre matrizes e vectores de apontadores, de modo a evidenciar as diferenças entre
as estruturas dinâmicas criadas e as matrizes nativas do C.
3.5.2
Matrizes estáticas
Conforme já se viu na secção 2.6.1, a utilização de estruturas multidimensionais em C apenas exige a declaração de uma variável com vários ı́ndices, especificando cada um da dimensão
pretendida da estrutura. Por exemplo
float x[3][2];
declara uma estrutura bidimensional de dois por três reais, ocupando um total de seis palavras
de memória no modelo de memória que temos vindo a assumir como referência. É frequente
uma estrutura bidimensional ser interpretada como uma matriz, neste exemplo de duas linhas por
três colunas. A inicialização de uma matriz pode ser efectuada durante a execução do programa
ou listando os valores iniciais, sendo apenas necessário fazer um agrupamento hierárquico das
constantes de inicialização de acordo com as dimensões da estrutura:
float x[3][2] = {{1.0,2.0},{3.0,4.0},
{5.0,6.0}};
Como se mostrou anteriormente, a arrumação em memória desta estrutura encontra-se representada esquematicamente na figura 2.9.
56 V ECTORES E MEM ÓRIA DIN ÂMICA
3.5.3
Matrizes dinâmicas
Admita-se que num dado programa se pretende substituir a sequência
#define N ...
#define M ...
...
int x[N][M];
por uma estrutura dinâmica com um mecanismo de acesso equivalente, mas em que os limites n e
m são variáveis cujo valor só é conhecido durante a execução do programa.
A solução para este problema é substituir a estrutura x por um vector dinâmico de apontadores
para inteiros, em que cada posição é por sua vez inicializada com um vector dinâmico. Considerese, por exemplo, que se pretende criar uma matriz de n por m. O código para este efeito é dado
por
int main{
int k;
int n,m;
int **x;
/* Inicialização de n e m */
x = (int**) calloc(n,sizeof(int*));
if(x == NULL){
printf("Erro na reserva de memória\n");
exit(1);
}
for(k = 0; k < n ; k++){
x[k] = (int*) calloc(m,sizeof(int));
if(x == NULL){
printf("Erro na reserva de memória\n");
exit(1);
}
}
Por exemplo, se se pretender criar uma matriz de 4 por 2 e inicializá-la com um valores inteiros
em que a classe das dezenas corresponde à linha e a classe dos algarismos às unidades, poder-se-ia
fazer
C RIAÇ ÃO DIN ÂMICA DE MATRIZES 57
int main{
int k,j;
int n,m;
int **x;
n = 4; m = 3;
x = (int**) calloc(n,sizeof(int*));
if(x == NULL){
printf("Erro na reserva de memória\n");
exit(1);
}
for(k = 0; k < n ; k++){
x[k] = (int*) calloc(m,sizeof(int));
if(x == NULL){
printf("Erro na reserva de memória\n");
exit(1);
}
}
for(k = 0; k < n ; k++)
for(j = 0; j < m ; j++)
x[k][j] = 10 * k + j;
O resultado da execução deste bloco de código seria o que se mostra na figura 3.5.
Este exemplo indica que a solução geral para simular a criação dinâmica de matrizes é declarar
um duplo apontador para o tipo pretendido dos elementos da matriz e, seguidamente, reservar
dinâmicamente um vector de apontadores e criar dinamicamente os vectores correspondentes a
cada linha.
Como é evidente, neste exemplo x é um duplo apontador para inteiro. Deste modo, se pretender usar esta “matriz dinâmica” como argumento de uma função fazer-se, no bloco que chama,
func(x,n,m,/* Outros argumentos */);
enquanto que o cabeçalho de func deverá ser
void func(int **x,int n,int m,/* Outros argumentos */);
58 V ECTORES E MEM ÓRIA DIN ÂMICA
Zona da pilha
Zona do heap
Endereço
Conteúdo
Variável
..
.
..
.
..
.
1543
2001
..
.
..
.
x
..
.
Endereço
..
.
Conteúdo
Variável
..
.
..
.
2001
2006
x[0]
2002
2009
x[1]
2003
2012
x[2]
2004
2015
x[3]
..
.
..
.
..
.
Endereço
Conteúdo
Variável
2006
0
x[0][0]
2007
1
x[0][1]
2009
10
x[1][0]
2010
11
x[1][1]
2012
20
x[2][0]
2013
21
x[2][1]
2015
30
x[3][0]
2016
31
x[3][1]
Figura 3.5: Criação dinâmica de matrizes por meio de um vector de apontadores. Os endereços
indicados são apenas ilustrativos.
Esta solução é tão frequente na prática que, por analogia, muitos programadores (mesmo
experientes) de C pensam que, dada a declaração tipo x[N][M], x sem qualquer ı́ndice corresponde a um duplo apontador para tipo. Como se mostrou na secção 2.6.4, esta suposição não
corresponde à realidade: nesta situação, x é um apontador para um vector de elementos de tipo.
3.5.4
Vectores de apontadores e matrizes
Considere-se a declaração
int *x[4];
Recordando que os [] têm precedência sobre o operador *, e seguindo a regra de interpretação
semântica da declaração apresentada na secção 2.6.4, resulta que x é um vector de 4 apontadores
para inteiros. Ou seja, em termos de modelo de memória, encontramos uma representação como a
indicada na figura 3.6, situação A. Um ponto importante a sublinhar é que esta declaração apenas
reserva memória para quatro apontadores. Esta situação é frequentemente mal interpretada pelo
facto de, sendo x[k] uma apontador para um inteiro, então *x[k] e *(x[k]+j) também são
do tipo inteiro. Mas, devido às equivalências sintácticas de endereçamento em C, tem-se
C RIAÇ ÃO DIN ÂMICA DE MATRIZES 59
Endereço
Conteúdo
Variável
..
.
..
.
..
.
1001
???
x[0]
1002
???
x[1]
1003
???
x[2]
1004
???
x[3]
..
.
..
.
..
.
A
Endereço
..
.
Conteúdo
Variável
Endereço
..
.
2001
1
x[0][0]
2002
2
x[0][1]
2005
3
x[1][0]
2006
4
x[1][1]
2010
5
x[2][0]
2011
6
x[2][1]
2013
7
x[3][0]
2014
8
x[3][1]
..
.
1001
2001
x[0]
1002
2005
x[1]
1003
2010
x[2]
1004
2013
x[3]
..
.
..
.
..
.
Conteúdo
Variável
B
Figura 3.6: Vectores de apontadores: A - Antes de inicializado, B- após a inicialização.
60 V ECTORES E MEM ÓRIA DIN ÂMICA
*x[k]
<-> x[k][0]
*(x[k]+j) <-> x[k][j]
e, portanto, x[k][j] é um inteiro. O que conduz, por vezes, ao raciocı́nio errado de que um
vector de apontadores pode ser utilizado indiscriminadamente como se de uma matriz se tratasse.
Ora, de facto, tal só é possı́vel se os elementos de x tiverem sido convenientemente inicializados
de modo a endereçarem a base de um vector de inteiros. Isto, só por si, não é realizado pela
declaração int *x[4], que se limita a declarar um vector de apontadores e a reservar 4 palavras
de memória para este efeito. Nesta declaração, não é reservada memória para qualquer inteiro.
Claro que, se o utilizador o pretender, é fácil inicializar as posições de memória do vector
de apontadores reservando memória dinâmica de modo a armazenar os inteiros pretendido. Admitindo que se pretende que o vector de apontadores anteriores sirva de base a uma estrutura
de endereçamento equivalente a uma matriz de 4 por 2, esta inicialização pode ser feita pela
sequência
int k,j;
int *x[4];
for(k = 0; k < 4; k++)
x[k] = (int*) calloc(2,sizeof(int));
for(k = 0; k < 4; k++)
for(j = 0; j < 2; j++)
x[k][j] = k*2 + j + 1;
onde, além da reserva das posições de memória para os vectores inteiros, se procedeu à sua
inicialização. A situação final pode ser representada pelo modelo da figura 3.6, situação B.
Em sı́ntese, é conveniente reter que, apesar da manipulação de matrizes e de vectores de
apontadores seja sintacticamente semelhante, os mecanismos de reserva de memória são claramente distintos. No caso da matriz int x[4][2], a própria declaração reserva automaticamente espaço para oito inteiros, os quais podem ser acedidos pelas regras habituais. No caso da
declaração de um vector de apontadores, como por exemplo int *x[4], apenas é efectuada a
reserva de quatro apontadores. A sua utilização requer a prévia inicialização de cada um dos seus
elementos com um endereço válido de um bloco de memória, o qual pode ser obtido a partir de
um vector já declarado ou, como no exemplo aqui usado, pela reserva de um bloco de memória
dinâmica através da função calloc().
Capı́tulo 4
Listas dinâmicas
4.1
Introdução
Como se viu anteriormente, a utilização de vectores em C apresenta a desvantagem de exigir o
conhecimento à partida da dimensão máxima do vector. Em muitas situações, a utilização de vectores dinâmicos, como descrito na secção 3.3, é uma solução eficiente. No entanto, em situações
em que a quantidade de memória dinâmica necessária varia frequentemente durante a execução do
programa, a utilização de vectores dinâmicos revela-se frequentemente pouco eficaz.
Considere-se, por exemplo, um gestor de uma central telefónica que necessita de reservar
dinamicamente memória para cada chamada estabelecida (onde é armazenada toda a informação
sobre a ligação, como por exemplo os números de origem e destino, tempo de ligação, etc,) e
libertar essa mesma memória quando a chamada é terminada. Dado que o número de ligações
activas varia frequentemente ao longo do dia, uma solução baseada num vector dinâmico exigiria o seu redimensionamento frequente. Em particular, sempre que não fosse possı́vel encontrar
memória livre imediatamente a seguir ao fim do vector, seria necessário deslocar todo o vector (v.
função realloc, secção 3.4.2) para uma nova zona de memória, e a cópia exaustiva de todo o
seu conteúdo para a nova posição de memória. Este mecanismo, além de pouco eficiente, poderia
inviabilizar o funcionamento em tempo real do sistema, dado que uma percentagem significativa
do tempo disponı́vel seria dispendido na gestão da memória usada pelo vector.
Quando se pretende armazenar entidades individuais de memória que possam ser criadas e
libertadas individualmente com uma certa frequência, é normalmente mais adequado utilizar estruturas de dados criadas dinâmicas e organizadas em listas.
62 L ISTAS DIN ÂMICAS
4.2
Abstracção de dados
Neste capı́tulo descrevem-se listas dinâmicas como uma forma de armazenar ou organizar
informação. Esta organização é, obviamente, independente do tipo de informação que se pretende
armazenar. Esta situação é semelhante à da construção de um armário com gavetas: a estrutura
do móvel é independente do conteúdo que se irá arrumar nas gavetas. Esta independência entre
móvel e conteúdo garante a generalidade do móvel, no sentido em que este será adaptável a várias
situações.
De modo semelhante, ao desenhar um programa é importante que as suas componentes sejam
o mais independentes possı́veis, de forma a manterem a generalidade. Tanto quanto possı́vel, é
desejável que um bloco de código desenvolvido para o programa A seja reutilizável no programa
B ou, pelo menos, que tal seja possı́vel sem alterações ou com alterações mı́nimas.
Uma forma de atingir este objectivo é, ao desenhar o programa, adoptar uma metodologia
designada por abstracção de dados(Martins, 1989). Esta metodologia baseia-se na definição e
distinção clara dos vários tipos de dados utilizados pelo programa (ou, seguindo o exemplo anterior, distinguir tanto quanto possı́vel o móvel do conteúdo das gavetas). Segundo esta metodologia,
cada tipo de dados deve ter manipulado apenas por um conjunto de funções especı́ficas, designadas
métodos, conhecedoras dos detalhes internos do tipo de dados associado. Todos os outros blocos
do programa têm apenas que conhecer as propriedades abstractas ou genéricas deste tipo. A
manipulação do tipo só são acessı́veis de outros blocos de programa através dos métodos disponibilizados pelo tipo de dados.
Esta metodologia de programação garante que, caso seja necessário alterar os detalhes internos de um determinado tipo, apenas é necessário alterar os métodos correspondentes a esse tipo.
Dado que todos os blocos de programas onde este tipo de dados é utilizado apenas acedem a ele
através dos métodos disponı́veis, requerendo apenas o conhecimento das suas propriedades gerais
(ou abstractas), é possı́vel minimizar ou eliminar totalmente as alterações necessárias aos outros blocos de programa. Deste modo, a metodologia de abstracção de dados contribui para uma
relativa estanquecidade e independência dos diversos módulos constituintes.
Neste capı́tulo, utilizar-se-á nos diversos exemplos uma metodologia estrita de abstracção de
dados, chamando-se a atenção caso a caso para aspectos especı́ficos da implementação.
L ISTAS 63
Zona da pilha (var. locais)
Variável
Conteúdo
..
.
base
Zona do heap (var. dinamicas)
Conteúdo
..
.
dados
(pos 1)
dados
(pos 2)
dados
(pos 3)
dados
(pos 4)
NULL
Figura 4.1: Lista dinâmica. Todos os elementos são criados dinamicamente na zona de heap,
sendo suficiente uma variável local de tipo apontador (variável base, nas figura) para poder aceder
a todos os elementos da lista.
4.3
Listas
Uma lista dinâmica não é mais do que uma colecção de estruturas de dados, criadas dinamicamente, em que cada elemento dispõe de um apontador para o elemento seguinte (figura 4.1). Cada
elemento da lista é constituı́do por uma zona de armazenamento de dados e de um apontador para
o próximo elemento. Para ser possı́vel identificar o fim da lista, no apontador do último elemento
é colocado o valor NULL.
Para criar uma lista é necessário definir um tipo de dados e criar uma variável local (normalmente designada base ou raiz. Admita-se, por exemplo, que se pretendia que cada elemento da
lista guardasse uma string com um nome e um número inteiro. A criação de uma lista de elementos
deste tipo exigiria uma declaração de tipos e de variáveis como se segue:
#define MAX_NOME 200
64 L ISTAS DIN ÂMICAS
typedef struct _tipoDados {
char nome[MAX_NOME];
int num;
} _tipoDados;
typedef struct _tipoLista{
tipoDados dados;
struct _tipoLista *seg;
} tipoLista;
int main(){
tipoLista *base;
/* ... */
Note-se que na definição do apontador seguinte, é necessário utilizar a construção
struct _tipoLista *seg e não tipoLista *seg. De facto, apesar de serem duas formas aparentemente semelhantes, a forma
typedef struct _tipoLista{
tipoDados dados;
tipoLista *seg; /* DECLARAÇÂO INVÁLIDA */
} tipoLista;
é inválida porque tipoLista só é conhecido no final da declaração, e não pode ser utilizado
antes de completamente especificado.
Uma das vantagens deste tipo de estruturas é que cada um dos seus elementos pode ser reservado e libertado individualmente, sem afectar os restantes elementos (exigindo apenas ajustar um
ou dois apontadores, de forma a garantir a consistência do conjunto). Adicionalmente, a ordem
dos elementos da lista é apenas definida pela organização dos apontadores. Deste modo, se for
necessário introduzir um elemento entre dois já existentes, não é necessário deslocar todos os elementos de uma posição, como sucederia num vector. Basta de facto reservar espaço para um
elemento adicional e deslocar todos os outros elementos de uma posição. Na figura 4.2 apresentase um exemplo em que se ilustra esta independência entre endereços de memória e sequência da
lista, e confere a esta uma flexibilidade superior à de um vector.
Dada esta independência entre endereços de memória e sequência, é frequente adoptar-se
representações gráficas simplificadas para as listas, como a se mostra na figura 4.3. A cruz no
último elemento corresponde a uma representação simbólica abreviada para o valor NULL.
L ISTAS 65
Zona da pilha (var. locais)
Variável
Conteúdo
..
.
base
Zona do heap (var. dinamicas)
Conteúdo
..
.
dados
(pos 2)
dados
(pos 1)
dados
(pos 4)
NULL
dados
(pos 3)
Figura 4.2: Lista dinâmica. A sequência dos elementos da lista é apenas definida pelos apontadores
de cada elemento, independentemente do endereço de memória ocupado.
base
Figura 4.3: Lista dinâmica. Representação simplificada
66 L ISTAS DIN ÂMICAS
Apesar das vantagens já referidas de uma lista, é necessário ter em atenção que o programa só
dispõe de uma variável para aceder a toda a lista, e que esta tem que ser percorrida elemento a elemento até se atingir a posição pretendida. Num vector, dado que todos as posições são adjacentes,
para aceder a qualquer posição basta saber o endereço do primeiro elemento e o número de ordem
(ı́ndice) do elemento que se pretende aceder para ser possı́vel calcular o endereço do elemento que
se pretende. Ou seja, a flexibilidade acrescida da lista em termos de organização de memória é
conseguida à custa do tempo de acesso aos seus elementos.
4.4
Listas dinâmicas: listar elementos
Uma operação particularmente simples sobre uma lista, mas ilustrativa do mecanismos de
acesso geralmente adoptados, é a listagem de todos os seus elementos. Considere-se, por exemplo,
que se pretende listar no terminal o conteúdo de todos os números e nomes da lista do exemplo da
secção 4.3. Uma solução para este efeito seria a sequência de código seguinte:
#define MAX_NOME 200
typedef struct _tipoDados {
char nome[MAX_NOME];
int num;
} tipoDados;
typedef struct _tipoLista{
tipoDados dados;
struct _tipoLista *seg;
} tipoLista;
void escreveDados(tipoDados dados){
printf("Num = %5d Nome = %s\n",dados.num, dados.nome);
}
void lista(tipoLista *base){
tipoLista *aux; /* Apontador que percorre a lista */
aux = base;
/* Incializa com o primeiro elemento
while(aux != NULL){ /* Enquanto não se atingir o final...
escreveDados(aux -> dados); /* Escreve o conteúdo
aux = aux -> seg; /* Avança para a próxima posição
}
}
int main(){
*/
*/
*/
*/
L ISTAS DIN ÂMICAS :
LISTAR ELEMENTOS
tipoLista *base;
/* Neste ponto, o apontador base e os restantes
elementos da lista são, de alguma forma,
inicializados */
/* Listagem do conteÚdo */
lista(base);
O princı́pio essencial da operação de listagem está incluı́da na função lista e é muito simples. Inicializa-se um apontador aux para o inı́cio da lista. Seguidamente, enquanto este apontador for diferente de NULL (ou seja, não atingir o fim da lista), o apontador é sucessivamente
avançado para o elemento seguinte.
Note-se como se adoptou neste bloco de código a metodologia de abstracção de dados. Existe neste exemplo uma separação funcional de tarefas entre as diversas entidades que participam o programa. A função lista manipula unicamente a estrutura de dados que suporta a
lista, percorrendo todos os seus elementos até ao fim da lista. No entanto, quando é necessário
escrever o conteúdo de cada nó no terminal, esta tarefa é delegada a uma função especı́fica (
escreveDados), responsável pela manipulação e processamento dos detalhes especı́ficos de
variáveis do tipo tipoDados. Neste sentido, tipoDados é, para a lista, um tipo abstracto
genérico, cuja representação interna ela desconhece, e da qual só tem que conhecer uma propriedade muito genérica: uma variável deste tipo pode de alguma forma ser escrita no terminal,
havendo um método competente para o fazer.
Uma forma alternativa da função listar frequentemente utilizada passa pela utilização de um
ciclo for em vez do ciclo while:
void lista(tipoLista *base){
tipoLista *aux; /* Apont. que percorre */
/* a lista.
*/
for(aux = base ; aux != NULL; aux = aux -> seg)
escreveDados(aux -> dados);
}
67
68 L ISTAS DIN ÂMICAS
4.5
4.5.1
Listas: pilhas
Introdução
As listas têm habitualmente uma estrutura e organização em memória semelhante à apresentada na figura 4.1. No entanto, os mecanismos de acesso à lista são variáveis e, no seu conjunto,
podem permitir que a lista realize apenas um subconjunto de tarefas bem determinadas.
Em teoria da computação, uma pilha (ou stack, na lietratura anglo-saxónica) é um sistema
que armazena dados de forma sequencial e que permite a sua leitura por ordem inversa da escrita.
A designação pilha vem da semelhança funcional com uma pilha comum. Admita-se que se
dispõe de um conjunto de palavras que se pretende armazenar. Considere-se ainda que o sistema
de armazenamento disponı́vel é um conjunto de pratos, sendo cada palavra manuscrita no fundo
do prato. À medida que as palavras vão sendo comunicadas ao sistema de armazenamento, são
escritas no fundo de um prato e este é colocado numa pilha. A leitura posterior das palavras
registadas é feita desempilhando pratos sucessivamente e lendo o valor registado em cada um.
Como é óbvio, a leitura ocorre por ordem inversa da escrita.
Uma pilha é frequentemente designada por uma estrutura LIFO, acrónimo derivado da expressão Last In First Out. A operação de armazenamento na pilha é geralmente designada de
operação de push, enquanto que a leitura é designada de pop.
As pilhas têm uma utilização frequente em informática sempre que se pretende inverter uma
sequência de dados. Embora a relação não seja óbvia, pode indicar-se, por exemplo, que o cálculo
de uma expressão aritmética em que vários operadores têm nı́veis de precedência diferentes é
realizada acumulando numa pilha resultados intermédios.
Considere-se, por exemplo, que se pretende inverter os caracteres da palavra Luı́s. A forma
como uma pilha pode contribuir para este resultado está graficamente sugerido na figura 4.4.
Uma pilha pode ser realizada em C através de uma lista dinâmica ligada. A colocação de
um novo elemento no topo da pilha corresponde a criar um novo elemento para a lista e inseri-lo
junto à base. De forma correspondente, a operação de remoção e leitura corresponde a retirar o
elemento da base, ficando esta a apontar para o elemento seguinte (v. figura 4.5)
L ISTAS :
L
L
u
í
s
s
s
s
í
í
í
í
u
u
u
u
u
u
L
L
L
L
L
L
Entrada (push)
(sobreposição)
í
u
PILHAS
L
L
Saida (pop)
(remoção)
Figura 4.4: Inversão de uma sequência de caracteres por meio de uma pilha.
base
’u’
’L’
’í’
Figura 4.5: Realização de uma pilha por uma lista ligada. No exemplo, considera-se uma pilha de
caracteres e a inserção do caracter ’ı́’ no topo da pilha. A tracejado indica-se a ligação existente
antes da inserção, a cheio após a inserção. A operação de remoção corresponde à realização
do mecanismo inverso (reposição da ligação a tracejado e libertação do elemento de memória
correspondente ao ’ı́’).
69
70 L ISTAS DIN ÂMICAS
4.5.2
Declaração
Tal como qualquer lista, a realização de uma pilha implica a declaração de um tipo de suporte
da lista e a utilização de uma variável para a base da pilha. A declaração da pilha pode ser feita,
por exemplo, pela declaração
typedef struct _tipoPilha {
tipoDados dados;
struct _tipoPilha *seg;
} tipoPilha;
onde se admite que tipoDados já foi definido e caracteriza o tipo de informação registada em
cada posição da pilha.
A utilização da pilha implica que no programa principal, ou no bloco de código onde se
pretende utilizar a pilha, seja declarada uma variável de tipo apontador para tipoPilha que
registe a base da pilha. Ou seja, será necessário dispor de uma variável declarada, por exemplo,
por
tipoPilha *pilha;
4.5.3
Inicialização
A primeira operação necessária para utilizar a pilha é inicializá-la ou criá-la. Uma pilha vazia
deve ter a sua base apontada para NULL. Embora seja possı́vel realizar directamente uma atribuição
à variável pilha, tratando-se de um detalhe interno de manipulação do tipo tipoPilha, esta
inicialização deverá ser delegada numa função especı́fica. Deste modo, para respeitar a metodologia de abstracção de dados, deve declarar-se uma pequena função
tipoPilha *inicializa(){
return NULL;
}
e utilizar-se esta função sempre que seja necessário inicializar a pilha:
pilha = inicializa();
L ISTAS :
4.5.4
PILHAS
Sobreposição
A operação de sobreposição exige a seguinte sequência de operações:
• Reserva de memória dinâmica para armazenar um novo elemento.
• Cópia dos dados para o elemento criado.
• Inserção do novo elemento na base da pilha.
Para a criação da memória dinâmica, é conveniente criar uma função novoNo() que cria
espaço para um novo nó, verificando a simultaneamente a existência de erros na reserva de
memória. Esta função pode ser definida como
tipoPilha *novoNo(tipoDados x){
tipoPilha *novo = calloc(1,sizeof(tipoPilha));
if(novo == NULL)
Erro("Erro na reserva de memória");
novo -> dados = x;
novo -> seg = NULL;
return novo;
}
onde Erro() é uma função genérica simples que imprime uma mensagem de erro e termina o
programa (ver secção 4.5.7).
A operação de inserção no topo da pilha exige a realização das operações representadas na
figura 4.5. Estas podem ser realizada pela seguinte função:
tipoPilha *sobrepoe(tipoPilha *pilha,tipoDados x){
tipoPilha *novo;
novo = novoNo(x);
novo -> seg = pilha;
return novo;
}
Esta função, após a criação do novo elemento, limita-se a colocar o apontador seg a apontar para o elemento que anteriormente se encontrava no topo, e indicar à base que o novo topo
corresponde ao novo elemento inserido.
71
72 L ISTAS DIN ÂMICAS
Note-se que esta função aceita como argumento o apontador original para o inı́cio da lista
(topo da pilha) e devolve a nova base alterada.
4.5.5
Remoção
A operação de remoção da pilha é acompanhada da leitura. Tal como anteriormente a função
recebe o apontador para a base da lista e devolve a base alterada. Dado que a remoção é acompanhada de leitura, a função recebe um segundo apontador, passado por referência, que deve ser
usado para guardar o valor do elemento removido. Uma função possı́vel para a realização desta
operação é
tipoPilha *retira(tipoPilha *pilha,tipoDados *x){
tipoPilha *aux;
if(pilhaVazia(pilha))
Erro("remoção de uma pilha vazia");
*x = pilha -> dados;
aux = pilha -> seg;
free(pilha);
return aux;
}
A operação de remoção é precedida de um teste para verificação de pilha vazia, para garantia
de integridade da memória (v. secção 4.5.6). Note-se que após a leitura da pilha, o bloco de
memória utilizado é libertado pela função free().
4.5.6
Teste
Antes de ser tentada a remoção de um elemento da pilha, é conveniente testar se a pilha se
encontra vazia. Numa primeira abordagem, poder-se-ia ser tentado a testar, sempre que necessário,
se o apontador da base se encontra com o valor NULL. Esta realização, ainda que correcta, violaria
o princı́pio essencial de abstracção de dados que temos vindo a respeitar: a caracterização como
vazia de uma pilha é um detalhe interno do tipoPilha, e como tal deve ser delegado numa
função especı́fica, de tipo booleano. Deste modo, poderia fazer-se
int pilhaVazia(tipoPilha *pilha){
return (pilha == NULL);
}
L ISTAS :
PILHAS
Esta função retorna 1 se a pilha estiver vazia, e 0 em caso contrário.
4.5.7
Exemplo
Suponha-se que se pretende implementar um sistema de inversão de caracteres baseado na
pilha definida anteriormente. Uma das vantagens de utilizar uma pilha para este efeito consiste
no facto de não ser necessário definir à partida a dimensão máxima da cadeia de caracteres: o
programa efectua a reserva e libertação de memória à medida das necessidades do programa.
Neste caso, tipoDados é realizado por um simples caracter. Para respeitar e exemplificar
o princı́pio de abstracção, iremos escrever os métodos especı́ficos de leitura e escrita deste tipo.
De modo a explorar de forma eficaz a independência dos diversos tipos de dados, os métodos
correspondentes a cada tipo devem ser declarados em ficheiros separados. Deste modo, os métodos
de acesso a tipoDados são agrupados num ficheiro dados.c. Os protótipos correspondentes
são declarados no ficheiro dados.h.
Ficheiro dados.h
/*
* Ficheiro: dados.h
* Autor:
Fernando M. Silva
* Data:
7/11/2002
* Conteúdo:
*
Ficheiro com declaração de tipos e
*
protótipos dos métodos para manipulação
*
de um tipoDados, concretizados aqui
*
por um tipo caracter simples.
*/
#ifndef _DADOS_H
#define _DADOS_H
#include <stdio.h>
#include <stdlib.h>
typedef char tipoDados;
/* Métodos de acesso a tipo dados */
int
leDados(tipoDados *x);
void
escreveDados(tipoDados x);
#endif /* _DADOS_H */
73
74 L ISTAS DIN ÂMICAS
Ficheiro dados.c
/*
*
*
*
*
*
*
*
*/
Ficheiro: dados.c
Autor:
Fernando M. Silva
Data:
12/11/2002
Conteúdo:
Métodos para manipulação de um
tipoDados, concretizado por um
caracter simples.
#include "dados.h"
int leDados(tipoDados *x){
/*
Lê um caracter. Devolve 1 se ler um ’\n’ */
*x = getchar();
if(*x == ’\n’)
return 1;
else
return 0;
}
void escreveDados(tipoDados x){
putchar(x);
}
De igual modo, a metodologia de abstracção de dados implementada sugere que todos
os métodos de acesso a tipoPilha sejam agrupados num ficheiro pilha.c, ficando as
declarações e protótipos correspondentes acessı́veis num ficheiro pilha.h.
Deste modo, ter-se-ia
Ficheiro pilha.h
/*
*
*
*
*
*
*
Ficheiro: pilha.h
Autor:
Fernando M. Silva
Data:
7/11/2000
Conteúdo:
Ficheiro com declaração de tipos e
protótipos dos métodos para manipulação
L ISTAS :
*
de uma pilha simples de elementos genéricos
*
de "tipoDados".
*/
#ifndef _PILHA_H
#define _PILHA_H
#include "dados.h"
typedef struct _tipoPilha {
tipoDados dados;
struct _tipoPilha *seg;
} tipoPilha;
/* Protótipos das funções */
tipoPilha *inicializa(void);
tipoPilha *sobrepoe(tipoPilha *pilha,tipoDados x);
tipoPilha *retira(tipoPilha *pilha,tipoDados *x);
int
pilhaVazia(tipoPilha *pilha);
#endif /* _PILHA_H */
Ficheiro pilha.c
/*
* Ficheiro: pilha.c
* Autor:
Fernando M. Silva
* Data:
1/12/2000
* Conteúdo:
*
Métodos para manipulação de uma pilha suportada
*
numa estrutura dinâmica ligada
*/
#include "pilha.h"
#include "util.h"
tipoPilha *novoNo(tipoDados x){
/*
* Cria um novo nó para a pilha
*/
tipoPilha *novo = calloc(1,sizeof(tipoPilha));
if(novo == NULL)
Erro("Erro na reserva de memória");
novo -> dados = x;
novo -> seg = NULL;
return novo;
PILHAS
75
76 L ISTAS DIN ÂMICAS
}
tipoPilha *inicializa(){
/*
* Cria uma nova pilha
* Retorna:
*
Pilha inicializada
*/
return NULL;
}
int pilhaVazia(tipoPilha *pilha){
/*
* Verifica o estado da pilha
* Argumentos:
*
pilha - Apontador para a base da pilha
* Retorna:
*
1 se a pilha estiver vazia
*
0 em caso contrário
*/
return (pilha == NULL);
}
tipoPilha *sobrepoe(tipoPilha *pilha,tipoDados x){
/*
* Adiciona um elemento à pilha
* Argumentos:
*
pilha - Apontador para a base da pilha
*
x
- dados a inserir
* Retorna:
*
Pilha modificada
*/
tipoPilha *novo;
novo = novoNo(x);
novo -> seg = pilha;
return novo;
}
tipoPilha *retira(tipoPilha *pilha,tipoDados *x){
/*
* Retira um elemento da pilha
* Argumentos:
*
pilha - Apontador para a base da pilha
*
x
- Apontador para variável que
*
retorna o valor lido da pilha
* Retorna:
*
Pilha modificada
L ISTAS :
PILHAS
*/
tipoPilha *aux;
if(pilhaVazia(pilha))
Erro("remoção de uma pilha vazia");
*x = pilha -> dados;
aux = pilha -> seg;
free(pilha);
return aux;
}
A função genérica de erro Erro() pode ser declarada num módulo genérico util.c, onde
são agrupadas funções utilitárias genéricas (neste exemplo, Erro() é única). O protótipos correspondente deve ser declarado num módulo util.h.
Ficheiro util.h
/*
* Ficheiro: util.h
* Autor:
Fernando M. Silva
* Data:
7/11/2002
* Conteúdo:
*
Ficheiro com declaração de funções e
*
protótipos genéricos
*/
#ifndef _UTIL_H
#define _UTIL_H
void Erro(char *msgErro);
#endif /* _UTIL_H */
Ficheiro util.c
/*
*
*
*
*
*
*/
Ficheiro:
Autor:
Data:
Conteúdo:
Funções
util.c
Fernando M. Silva
1/11/2002
genéricas
77
78 L ISTAS DIN ÂMICAS
#include <stdio.h>
#include <stdlib.h>
#include "util.h"
void Erro(char *msgErro){
/*
* Termina o programa, escrevendo uma mensagem
* de erro
*/
fprintf(stderr, "Erro: %s\n",msgErro);
exit(1);
}
Considere-se, por último, o programa principal. Este limita-se a inicializar a pilha e a efectuar
a leitura de um sequência de dados, acumulando-os sucessivamente na pilha. A leitura é efectuada
até que a função leDados() (método de tipoDados) identifique uma mudança de linha na
entrada. Seguidamente, os dados são sucessivamente removidos (desempilhados) e escritos no
dispositivo de saı́da, até que a pilha esteja vazia. Deste modo, ter-se-ia:
Ficheiro main.c
/*
* Ficheiro: main.c
* Autor:
Fernando M. Silva
* Data:
7/11/2000
* Conteúdo:
*
Programa principal simples para teste
*
de uma pilha, usada para inversão de
*
uma cadeia de caracteres
*/
#include <stdio.h>
#include <stdlib.h>
#include "pilha.h"
int main(){
tipoPilha *pilha;
tipoDados x;
pilha = inicializa();
printf("Introduza uma sequência de caracteres:\n");
while(!leDados(&x)){
pilha = sobrepoe(pilha,x);
}
L ISTAS :
PILHAS
printf("Sequência invertida:\n");
while(!pilhaVazia(pilha)){
pilha = retira(pilha,&x);
escreveDados(x);
}
printf("\n");
exit(0);
}
A compilação automática de todos os módulos pode ser realizada por meio do utilitário make.
A Makefile correspondente poderia ser escrita como
#
# Ficheiro: Makefile
# Autor:
Fernando M. Silva
# Data:
7/11/2000
# Conteúdo:
#
Makefile para teste de estruturas dinâmicas
#
#
A variável CFLAGS especifica as flags usadas
#
por omissão nas regras de compilação
#
#
A variável SOURCES, que define os ficheiro
#
fonte em C, só e usada para permitir a
#
evocação do utilitário "makedepend" (pelo
#
comando ’make depend’), de modo a actualizar
#
automaticamente as dependências dos ficheiros
#
.o nos ficheiros .h
#
#
A variável OBJECTS define o conjunto dos
#
ficheiros objectos
#
CFLAGS=-g -Wall -ansi -pedantic
SOURCES=main.c pilha.c dados.c util.c
OBJECTS=main.o pilha.o dados.o util.o
#
# Comando de linkagem dos executáveis
#
teste: $(OBJECTS)
gcc -o $@ $(OBJECTS)
#
# A regra ’make depend’ efectua uma actualização da
# makefile, actualizando as listas de dependências dos
79
80 L ISTAS DIN ÂMICAS
# ficheiros .o em .c
#
#
depend::
makedepend $(SOURCES)
#
# Regra clean: ’make clean’ apaga todos os ficheiros
# reconstruı́veis do disco
#
clean::
rm -f *.o a.out *˜ core teste *.bak
# DO NOT DELETE
4.6
4.6.1
Listas: filas
Introdução
Referiu-se anteriormente que uma pilha correspondia a uma estrutura LIFO (Last In, First
Out). De forma semelhante, podemos descrever uma fila como um sistema FIFO (First In, First
Out). O exemplo corrente de funcionamento de uma fila é a vulgar fila de espera. Cada novo
elemento armazenado é colocado no final da fila, enquanto que cada elemento retirado é obtido do
inı́cio da fila (figura 4.6, A).
Uma fila pode ser realizada por meio de uma lista ligada, relativamente à qual são mantidos
não um, mas dois apontadores: um para a base ou inı́cio, por onde são retirados os elementos, e
outro para o fim ou último elemento da lista, que facilita a inserção de novos elementos na lista.1
4.6.2
Declaração
De forma a que seja possı́vel manipular uma única variável do tipoFila, esta é realizada
por uma estrutura de dados que agrupa os dois apontadores, inı́cio e fim. Deste modo, a declaração
da fila pode ser realizada por
1
De facto, o apontador para a base seria suficiente para realizar a fila; no entanto, cada operação de inserção exigiria
percorrer a totalidade da fila para realizar a inserção no final, método que seria pouco eficiente.
L ISTAS :
fim
’L’
’u’
FILAS
’í’
inicio
A
fim
’L’
’u’
’í’
’s’
’í’
’s’
inicio
B
fim
’L’
’u’
inicio
C
Figura 4.6: Realização de uma fila de caracteres com uma lista ligada. A - Estrutura da fila, B Fila em A após a inserção do caracter ’s’ (a tracejado, as ligações eliminadas), C - Fila em B após
a leitura de um caracter (’L’).
typedef struct _tipoLista {
tipoDados dados;
struct _tipoLista *seg;
} tipoLista;
typedef struct _tipoFila {
tipoLista *fim;
tipoLista *inicio;
} tipoFila;
4.6.3
Inicialização
A inicialização da fila vazia corresponde simplesmente a colocar a NULL os dois apontadores
da fila. Deste modo, a inicialização da fila pode ser realizada simplesmente por
void inicializa(tipoFila *fila){
fila -> inicio = NULL;
fila -> fim
= NULL;
}
Note-se que na chamada à função o argumento deve ser efectuada por referência (passando o
endereço da variável tipoFila) de modo a que a variável seja alterável pela função.
81
82 L ISTAS DIN ÂMICAS
4.6.4
Inserção
A inserção de novos elementos corresponde à colocação de elementos no final da fila, tal como
representado graficamente na figura 4.6, caso B.
Tal como no caso da pilha, para a criação da memória dinâmica, é conveniente criar uma
função auxiliar novoNo().
tipoLista *novoNo(tipoDados x){
tipoLista *novo = calloc(1,sizeof(tipoFila));
if(novo == NULL)
Erro("Erro na reserva de memória");
novo -> dados = x;
novo -> seg = NULL;
return novo;
}
A função de inserção propriamente dita pode ser realizada por
void adiciona(tipoFila *fila,tipoDados x){
tipoLista *novo;
novo = novoNo(x);
novo -> dados = x;
if(fila -> fim != NULL){
fila -> fim -> seg = novo;
}
else{
fila -> inicio = novo;
}
fila -> fim = novo;
}
Nesta função é necessário considerar o caso particular em que a fila está vazia e em que,
como tal, o apontador fim está a NULL. Neste caso particular, ambos os apontadores ( inicio
e fim) devem ser colocados ser inicializados com o endereço do novo elemento inserido. No
caso habitual (lista não vazia), basta adicionar o novo elemento ao último da lista e modificar o
apontador fim.
L ISTAS :
4.6.5
FILAS
Remoção
A inserção de novos elementos corresponde à eliminação de elementos presentes no final da
fila, tal como representado graficamente na figura 4.6, caso C.
Esta função pode ser realizada por
void retira(tipoFila *fila,tipoDados *x){
tipoLista *aux;
if(filaVazia(fila))
Erro("Remoção de uma fila vazia");
*x = fila -> inicio -> dados;
aux = fila -> inicio;
fila -> inicio = fila -> inicio -> seg;
if(fila -> inicio == NULL)
fila -> fim = NULL;
free(aux);
}
A função de retira tem também uma estrutura simples. Tal como na função de inserção, é
necessário considerar o caso particular em que a lista tem apenas um elemento, situação em que o
apontador fim deve ser colocado a NULL depois da remoção.
Tal como no caso da pilha, é testada a condição de pilha vazia antes de efectuar a remoção
(ver secção 4.6.6).
4.6.6
Teste
Para manipulação da lista é indispensável dispor de uma função para testar se a fila se encontra
vazia. Para este teste basta verificar qualquer um dos apontadores se encontra a NULL. Este teste
pode ser efectuado pelo código
int filaVazia(tipoFila *fila){
return (fila -> inicio == NULL);
}
83
84 L ISTAS DIN ÂMICAS
4.6.7
Exemplo
Para uma maior semelhança com o exemplo da pilha, utiliza-se também neste exemplo o caso
de uma fila de caracteres. Como seria de esperar, a fila não realiza neste caso uma inversão, mas
apenas um armazenamento temporário da informação, permitindo a sua reprodução pela mesma
ordem de entrada.
Tal como no exemplo da pilha, o código foi distribuı́do por três ficheiros: main.c, fila.c
e dados.c, tendo para os dois últimos sido desenvolvido um ficheiro de protótipos associado.
Dada a semelhança com o exemplo da pilha, apresentam-se aqui apenas o conteúdo
dos vários ficheiros, sem outros comentários. Omite-se aqui o conteúdo dos ficheiros
dados.h, dados.c, util.h e util.c por serem obviamente idênticos aos anteriores.
Ficheiro fila.h
/*
* Ficheiro: fila.h
* Autor:
Fernando M. Silva
* Data:
7/11/2002
* Conteúdo:
*
Ficheiro com declaração de tipos e
*
protótipos dos métodos para manipulação
*
de uma fila simples de elementos genéricos
*
de "tipoDados".
*/
#ifndef _FILA_H
#define _FILA_H
#include "dados.h"
typedef struct _tipoLista {
tipoDados dados;
struct _tipoLista *seg;
} tipoLista;
typedef struct _tipoFila {
tipoLista *fim;
tipoLista *inicio;
} tipoFila;
/* Protótipos das funções */
L ISTAS :
void
void
void
int
inicializa(tipoFila *fila);
adiciona(tipoFila *fila,tipoDados x);
retira(tipoFila *fila,tipoDados *x);
filaVazia(tipoFila *fila);
#endif /* _FILA_H */
Ficheiro fila.c
/*
* Ficheiro: fila.c
* Autor:
Fernando M. Silva
* Data:
1/11/2002
* Conteúdo:
*
Métodos para manipulação de uma fila suportada
*
numa estrutura dinâmica ligada
*/
#include "fila.h"
#include "util.h"
tipoLista *novoNo(tipoDados x){
/*
* Cria um novo nó para a fila
*/
tipoLista *novo = calloc(1,sizeof(tipoFila));
if(novo == NULL)
Erro("Erro na reserva de memória");
novo -> dados = x;
novo -> seg = NULL;
return novo;
}
void inicializa(tipoFila *fila){
/*
* Inicializa uma nova fila
*/
fila -> inicio = NULL;
fila -> fim
= NULL;
}
int filaVazia(tipoFila *fila){
/*
* Verifica o estado da fila
* Argumentos:
FILAS
85
86 L ISTAS DIN ÂMICAS
*
fila - Apontador para a base da fila
* Retorna:
*
1 se a fila estiver vazia
*
0 em caso contrário
*/
return (fila -> inicio == NULL);
}
void adiciona(tipoFila *fila,tipoDados x){
/*
* Adiciona um elemento à fila
* Argumentos:
*
fila - Apontador para a fila
*
x
- dados a inserir
*/
tipoLista *novo;
novo = novoNo(x);
if(fila -> fim != NULL){
fila -> fim -> seg = novo;
}
else{
fila -> inicio = novo;
}
fila -> fim = novo;
}
void retira(tipoFila *fila,tipoDados *x){
/*
* Retira um elemento fila
* Argumentos:
*
fila - Apontador para a fila
*
x
- Apontador para variável que
*
retorna o valor lido da fila
*/
tipoLista *aux;
if(filaVazia(fila))
Erro("Remoção de uma fila vazia");
*x = fila -> inicio -> dados;
aux = fila -> inicio;
fila -> inicio = fila -> inicio -> seg;
if(fila -> inicio == NULL)
fila -> fim = NULL;
free(aux);
}
L ISTAS ORDENADAS 87
Ficheiro main.c
/*
* Ficheiro: main.c
* Autor:
Fernando M. Silva
* Data:
7/11/2000
* Conteúdo:
*
Programa principal simples para teste
*
de uma fila.
*/
#include <stdio.h>
#include <stdlib.h>
#include "fila.h"
int main(){
tipoFila fila;
tipoDados x;
inicializa(&fila);
printf("Introduza uma sequência de caracteres:\n");
while(!leDados(&x)){
adiciona(&fila,x);
}
printf("Sequência lida:\n");
while(!filaVazia(&fila)){
retira(&fila,&x);
escreveDados(x);
}
printf("\n");
exit(0);
}
4.7
4.7.1
Listas ordenadas
Introdução
Um vector pode ser ordenado segundo uma qualquer relação de ordem utilizando um algoritmo apropriado(Knuth, 1973) (selection sort, bubble-sort, quicksort ou qualquer outro). Embora
estes algoritmos estejam bem estudados e sejam frequentemente necessários, todos eles requerem
um esforço computacional significativo. É possı́vel provar que a quantidade de trabalho necessária
para esta tarefa não é apenas proporcional ao número de elementos a ordenar: a complexidade da
88 L ISTAS DIN ÂMICAS
tarefa aumenta significativamente mais que a dimensão do vector. Para compreender melhor a
quantidade de trabalho exigido, podemos comparar esta situação ao de arrumar alfabeticamente
uma biblioteca a partir de uma situação desorganizada. Se arrumar uma biblioteca com 5,000
livros demorar um dia, arrumar uma biblioteca com 10,000 livros não demorará apenas dois dias,
mas sim três ou quatro, já que cada tı́tulo individual terá que ser alfabeticamente comparado com
um número muito maior de outros livros.
No caso de uma biblioteca, se se pretender evitar a tarefa hercúlea de ordenar todos os livros,
o melhor é mantê-la sempre ordenada. Desta forma, cada novo livro adicionado terá apenas que
ser colocado no local certo, tarefa obviamente muito mais rápida.
Em C, quando os elementos a ordenar se encontram armazenados num vector, o método anterior corresponde basicamente a encontrar o local de inserção, deslocar todos os elementos posteriores de uma posição, e inserir o elemento na posição assim aberta. Embora o algoritmo seja
simples, a tarefa de deslocar todos os elementos de uma posição é computacionalmente pesada,
sobretudo quando a inserção se efectua nas posições iniciais. O paralelo que podemos encontrar
no exemplo da biblioteca é o de uma estante repleta de livros, excepto na última prateleira. A
introdução ordenada de um novo tı́tulo na primeira prateleira exige deslocar todos os tı́tulos de
uma posição. Dado que só existe espaço disponı́vel na última prateleira, este processo pode exigir
de facto movimentar livros em todas as prateleiras da estante.
As listas dinâmicas oferecem uma forma simples de criar e manter eficientemente uma
colecção de objectos ordenados. Ao contrário do vector, em que todas as posições se encontram em endereços de memória contı́guos, a ordem dos elementos da lista não depende do seu
endereço de memória, mas apenas da ordem definida pela sequência de apontadores, tal como já
se mostrou 4.2.
As operações necessárias para a manipulação e manutenção de uma lista ordenada são
generalizações relativamente simples dos casos da pilha e da fila. Algumas destas operações,
como criar a lista ou listar os seus elementos, já foram apresentadas anteriormente. Apenas algumas das operações descritas seguidamente, como a inserção, procura e remoção no meio da lista
são de facto totalmente novas.
4.7.2
Declaração e inicialização
A declaração e inicialização de uma lista segue os passos já vistos para o caso da pilha. A
declaração da lista pode ser realizada por
typedef struct _tipoLista {
L ISTAS ORDENADAS 89
tipoDados dados;
struct _tipoLista *seg;
} tipoLista;
onde, tal como nos exemplos anteriores, tipoDados é um tipo abstracto que define a informação
armazenada em cada elemento.
De igual modo, a inicialização da lista corresponde apenas à inicialização do apontador a
NULL, por meio da função de inicialização
tipoLista *inicializa(){
return NULL;
}
4.7.3
Listagem ordenada
A listagem ordenada corresponde apenas a uma listagem convencional do conteúdo. Deste
modo, a listagem pode ser feita por
void listar(tipoLista *base ){
tipoLista *aux = base;
while(aux){
printf(" -> ");
escreveDados(aux -> dados);
printf("\n");
aux = aux -> seg;
}
}
4.7.4
Procura
A procura é um procedimento relativamente simples. Basta percorrer a lista até encontrar o
elemento que se procura, e retornar um apontador para o respectivo elemento. Convenciona-se
que a função de procura deve retornar NULL caso o elemento a procurar não exista.
Para assentar ideias, admita-se temporariamente que se está a lidar com uma lista de inteiros.
Deste modo, presume-se que se definiu previamente
typedef int tipoDados;
90 L ISTAS DIN ÂMICAS
Neste caso, a função de procura pode ser realizada por
tipoLista *procura(tipoLista *base,tipoDados x){
tipoLista *aux;
aux = base;
while((aux!=NULL) &&
aux = aux -> seg;
return aux;
aux -> dados != x)
}
A função anterior, embora funcione, apresenta o inconveniente de não explorar o facto da lista
estar ordenada. Por exemplo, no caso de uma lista ordenada de inteiros onde estejam todos os
valores pares entre 10 e 10000, se se procurar o número 15 será necessário ir até ao fim da lista
para concluir que o número não está presente. Como é óbvio, esta conclusão poderia ter sido tirada
muito mais cedo, logo que fosse atingido o número 16 na lista.
Deste modo, uma versão mais optimizada da função de procura pode ser escrita como
tipoLista *procuraOrdenado(tipoLista *base,tipoDados x){
tipoLista *aux = base;
while((aux!=NULL) && (aux -> dados<x))
aux = aux -> seg;
if((aux != NULL) && (aux -> dados == x))
return aux;
else
return NULL;
}
Neste caso, a lista é percorrida enquanto o elemento a procurar for inferior à posição actual
da lista. Quando o ciclo é interrompido, é testado se se se atingiu o fim da lista ou se se encontrou
o elemento procurado.
Nesta função, vale a pena considerar a estrutura do teste
if((aux != NULL) &&
...
}
(aux -> dados
== x)){
e verificar a forma como se toma partido do modo como o C avalia expressões lógicas. Repare-se
que o segundo operando da disjunção ( aux -> dados == x) só pode ser avaliado se aux
L ISTAS ORDENADAS 91
for diferente de NULL, já que de outra forma se poderia estar a gerar uma violação de memória
(tentativa de acesso através do endereço 0, o que se encontra fora do controlo do programador).
No entanto, o C garante que realiza a avaliação de expressões lógicas da esquerda para a direita e
que interrompe a sua avaliação assim que for possı́vel determinar univocamente o resultado final.
Neste exemplo, se aux for NULL, o primeiro operando da conjunção lógica ’&&’ é falso, o que
implica que o resultado global da expressão também o é. Assim, não sendo necessário o cálculo
do segundo operando, não há o risco de se produzir a violação de memória decorrente do acesso
através de um apontador NULL.
Refira-se, por último, que num problema prático podem coexistir várias funções de procura,
consoante o que se pretende encontrar. Por exemplo, se os elementos de uma lista são estruturas
que incluem, por exemplo, um número e um nome, podem ser escritas duas funções de procura,
uma para o número e outra para o nome. Claro que se a lista estiver ordenada por números, a
busca pelo número poderá ser optimizada (procura só até encontrar um elemento de número igual
ou superior ao procurado), mas a busca pelo nome terá obviamente que ser exaustiva se o nome
não existir, já que só no final da lista será possı́vel ter a certeza de que determinado nome não faz
parte da lista.
4.7.5
Abstracção de dados e métodos de teste
Nas duas funções de procura anteriores admitiu-se que o tipoDados era um inteiro. Esta
hipótese permitiu utilizar os operadores relacionais == e < de uma forma intuitiva.
No caso mais geral em que tipoDados é um tipo abstracto genérico esta comparação
não pode ser realizada directamente pelos operadores relacionais. Para demonstrar este facto,
considere-se que tipoDados corresponde a uma estrutura com um número e um nome de um
aluno. Neste caso, não faz sentido usar o operador relacional < para comparar dois alunos a e
b. De facto, o C desconhece o que se pretende comparar: é o nome dos alunos a e b ou os seus
números?
Para contornar esta dificuldade, seria possı́vel utilizar o operador ’.’ (membro de estrutura)
e aceder directamente ao campo numérico, utilizando o operador < para a comparação, ou aceder
ao campo com o nome e utilizar a função strcmp() de forma adequada. No entanto, qualquer
destas soluções estaria a violar o princı́pio de abstracção de dados, já que os métodos de procura
da lista, para quem tipoDados deveria ser um tipo abstracto genérico, estariam a aceder directamente a detalhes internos do tipo.
A forma de resolver esta questão é as funções procura delegarem o processo de comparação
92 L ISTAS DIN ÂMICAS
em métodos (funções) especı́ficos internos de tipoDados, responsáveis pela implementação dos
detalhes práticos da comparação. Deste modo, admitindo que foram associados ao tipo abstracto
tipoDados um método com protótipo
int menor(tipoDados a,tipoDados b);
que devolve 1 se a for de algum modo anterior a b e 0 em caso contrário (as funções da lista não
precisam de conhecer os detalhes desta comparação) e um outro
int igual(tipoDados a,tipoDados b);
que devolve 1 se a for igual b segundo um dado critério e 0 em caso contrário.
Deste modo, uma solução mais geral da função de procura ordenada deveria ser escrita como
tipoLista *procuraOrdenado(tipoLista *base,tipoDados x){
tipoLista *aux = base;
while((aux!=NULL) && menor(aux -> dados,x))
aux = aux -> seg;
if((aux != NULL) && igual(aux -> dados ,x))
return aux;
else
return NULL;
}
Alternativamente, é frequente unificar todos os métodos de comparação numa única função
que devolve -1, 0 ou 1 consoante o primeiro elemento é anterior, igual ou posterior ao segundo. É
esta solução que é adoptada na função strcmp() para comparação de strings.
4.7.6
Inserção ordenada
Para realizar uma inserção ordenada é suficiente percorrer a lista até encontrar um elemento
que seja superior ao que se pretende inserir. O novo elemento deverá ser colocado antes deste.
Apesar desta metodologia simples, a inserção ordenada requer algumas considerações suplementares. Um dos pontos a ter em conta é que para posicionar o novo elemento antes do que foi
identificado é necessário alterar o apontador do elemento que se encontra antes deste. Ou seja, ao
L ISTAS ORDENADAS 93
antes
depois
5
novo
10
7
Figura 4.7: Inserção entre dois elementos da lista. O apontador antes não aponta para o elemento
anterior da lista, mas sim para o campo apontador seg desse elemento.
percorrer a lista, é necessário manter uma referência não apenas para o elemento da lista que está
a ser comparado (elemento actual) mas também para o seu predecessor (elemento anterior).
De modo a melhor compreender esta operação, é conveniente começar por desenvolver uma
função auxiliar de inserção em que se admite que a posição de inserção já foi determinada e, como
tal, que já existem referências para o apontador do elemento anterior e para o elemento actual
(v. figura 4.7). Designaremos estas variáveis de referência por antes e depois. Neste caso o
código desta função pode ser escrito
void insere(tipoLista **antes, tipoDados x, tipoLista *depois){
tipoLista *novo = novoNo(x);
*antes = novo;
novo -> seg = depois;
}
onde a função novoNo() é semelhantes às anteriores
tipoLista *novoNo(tipoDados x){
tipoLista *novo = calloc(1,sizeof(tipoLista));
if(novo == NULL)
Erro("Erro na reserva de memória");
novo -> dados = x;
novo -> seg = NULL;
return novo;
}
Uma vez definida esta função, a inserção ordenada apenas tem que ter em conta alguns casos
particulares, nomeadamente a inserção numa fila vazia ou a inserção antes do inı́cio. Nos outros
94 L ISTAS DIN ÂMICAS
casos, basta percorrer a lista com um apontador act, e manter presente que se deve manter um
apontador ant para o elemento anterior. A função insereOrdenado() pode então ser escrita
tipoLista *insereOrdenado(tipoLista *base,tipoDados x){
tipoLista *act,*ant;
if(base == NULL){
insere(&base,x,NULL); /* Lista vazia */
}
else if(menor(x,base -> dados)){
insere(&base,x,base); /* Insere *antes* da base */
}
else{
ant = base; act = base -> seg;
while((act != NULL) && (menor(act -> dados,x))){
ant = act; act = act -> seg;
}
insere(&(ant -> seg),x,act);
}
return base;
}
Esta função recebe como um dos argumentos o valor da base e devolve o valor desta depois
da inserção. A base retornada é idêntica à base inicial, excepto quando a inserção é feita no inı́cio
da lista.
O par de funções insere() e insereOrdenado() foi escrita de modo a sublinhar os
diversos aspectos necessários à inserção numa lista. No entanto, o C permite escrever uma função
de inserção ordenada de modo muito mais compacto:
tipoLista *insereOrdenado(tipoLista *base,tipoDados x){
tipoLista *aux = base, *novo = novoNo(x);
if(aux == NULL || menor(x,aux -> dados)) {
novo -> seg = base;
return novo;
}
aux = base;
while( aux -> seg!= NULL && menor(aux -> seg -> dados,x))
aux = aux -> seg;
novo -> seg = aux -> seg;
aux -> seg = novo;
return base;
L ISTAS ORDENADAS 95
reg
1
4
9
Figura 4.8: Remoção. O apontador reg referencia o campo seg do registo anterior da lista.
}
Aqui, o primeiro if abrange simultaneamente a inserção numa lista vazia e antes do primeiro
elemento. Seguidamente, o ciclo while percorre a lista, mantendo apenas um apontador (equivalente ao apontador ant do exemploanterior).
4.7.7
Remoção
Tal como a inserção, a remoção pode ser simplificada se for escrita uma função auxiliar
libertaReg que é executada quando já é conhecido o local de remoção. Esta função (v. figura
4.8) pode ser escrita
tipoLista *libertaReg(tipoLista *reg){
tipoLista *aux;
aux = reg;
reg = reg -> seg;
free(aux);
return reg;
}
Seguidamente, é necessário escrever uma função que procure o o elemento a apagar e chame
a função anterior. Esta função é dada por
tipoLista *apaga(tipoLista *base,tipoDados x){
tipoLista *aux;
aux = base;
if(base != NULL){
if(igual(base -> dados,x)){
base = libertaReg(base);
}
else{
96 L ISTAS DIN ÂMICAS
aux = base;
while((aux -> seg != NULL) &&
(menor(aux -> seg -> dados,x)))
aux = aux -> seg;
if((aux -> seg != NULL) &&
igual(aux -> seg -> dados,x))
aux -> seg = libertaReg(aux -> seg);
}
}
return base;
}
4.7.8
Exemplo
Como exemplo, apresenta-se aqui o código completo de um programa que manipula uma
lista ordenada de racionais. O tipo racional é representado por dois inteiros, que descrevem o seu
numerador e o denominador. O programa aceita uma sequência de racionais. Um racional positivo
é inserido na lista, enquanto que um racional negativo provoca uma tentativa de remoção do seu
simétrico, caso este exista (ou seja, a indicação de − 35 provoca a remoção do racional 53 ).
Omite-se aqui a listagem dos ficheiros util.h e util.c, idênticos ao introduzido no exemplo da pilha (v. secção 4.5.7).
Ficheiro dados.h
/*
*
*
*
*
*
*
*
*
*
*
*
#
*/
Ficheiro: lista.h
Autor:
Fernando M. Silva
Data:
7/11/2000
Conteúdo:
Definição do tipo genérico
"tipoDados" usado nos exemplos de
estruturas de dados dinâmicas.
Para fins de exemplo, "tipoDados"
é realizado por uma fracção inteira,
a qual e’ especificada por um numerador
e um denominador
#ifndef _DADOS_H
L ISTAS ORDENADAS 97
#define _DADOS_H
#include <stdio.h>
typedef struct{
int numerador;
int denominador;
} tipoDados;
void
tipoDados
float
int
int
int
int
tipoDados
#endif
escreveDados(tipoDados x);
leDados(char mensagem[]);
valor(tipoDados x);
igual(tipoDados x,tipoDados y);
menor(tipoDados x,tipoDados y);
numerador(tipoDados x);
denominador(tipoDados x);
simetrico(tipoDados x);
Ficheiro dados.c
/*
*
*
*
*
*
*
*
*
*
*
*/
Ficheiro: dados .c
Autor:
Fernando M. Silva
Data:
1/12/2000
Conteúdo:
Métodos de acesso exemplificativos
da definição de um tipo abstracto "tipoDados"
Neste exemplo, "tipoDados" implementa um numero
racional, especificado por um numerador e um
denominador
#include "dados.h"
#define DIM_LINE 100
tipoDados leDados(char mensagem[]){
/*
* Escreve a mensagem passada por argumento, lê um racional e
* valida a entrada
* Argumento:
*
mensagem - mensagem a escrever
* Retorna:
*
racional lido
98 L ISTAS DIN ÂMICAS
*/
char line[DIM_LINE];
tipoDados x;
int ni;
do{
printf("%s\n",mensagem);
fgets(line,DIM_LINE,stdin);
ni=sscanf(line,"%d %d",&x.numerador,&x.denominador);
if(ni !=2){
printf("Erro na leitura\n");
}
else{
if(x.denominador == 0)
printf("Racional inválido\n");
}
}while((ni != 2) || (x.denominador == 0));
return x;
}
void
escreveDados(tipoDados x){
/*
* Escreve x em stdout, no formato
* numerador / denominador
* Argumento:
*
x - valor a escrever
*/
printf("%d/%d",x.numerador,x.denominador);
}
float
valor(tipoDados x){
/*
* Retorna um real com o valor (aproximado) do racional x
* Argumento:
*
x - racional
* Retorna
*
valor aproximado de x
*/
return (float) x.numerador / (float) x.denominador;
}
int
menor(tipoDados x,tipoDados y){
/*
* Retorna 1 caso o racional x seja menor que y
* Argumentos:
*
x,y - racionais a comparar
* Retorna
L ISTAS ORDENADAS 99
*
1 se x < y
*
0 em caso contrário
*/
if(x.denominador * y.denominador > 0)
return x.numerador * y.denominador < y.numerador * x.denominador;
else
return x.numerador * y.denominador > y.numerador * x.denominador;
}
int
igual(tipoDados x,tipoDados y){
/*
* Retorna 1 caso o racional x seja igual a y
* Argumentos:
*
x,y - racionais a comparar
* Retorna
*
1 se x = y
*
0 em caso contrário
*/
return x.numerador * y.denominador == x.denominador * y.numerador;
}
int
numerador(tipoDados x){
/*
* Retorna o numerador do racional x
* Argumento:
*
x - racional
* Retorna
*
numerador de x
*/
return x.numerador;
}
int
denominador(tipoDados x){
/*
* Retorna o denominador do racional x
* Argumento:
*
x - racional
* Retorna
*
denominador de x
*/
return x.denominador;
}
tipoDados simetrico(tipoDados x){
/*
* Retorna o simétrico do racional x
* Argumento:
100 L ISTAS DIN ÂMICAS
*
x - racional
* Retorna
*
simétrico de x
*/
tipoDados aux;
aux.numerador
= -x.numerador;
aux.denominador = x.denominador;
return aux;
}
Ficheiro lista.h
/*
* Ficheiro: lista.h
* Autor:
Fernando M. Silva
* Data:
7/11/2000
* Conteúdo:
*
Ficheiro com declaração de tipos e
*
protótipos dos métodos para manipulação
*
de uma lista dinâmica simples
*
*/
#ifndef _LISTA_H
#define _LISTA_H
#include <stdio.h>
#include <stdlib.h>
/*
* Tipo dos dados da lista
*/
#include "dados.h"
/*
* Definição de tipoLista
*/
typedef struct _tipoLista {
tipoDados dados;
struct _tipoLista *seg;
} tipoLista;
/*
* Protótipos dos métodos de acesso
*/
L ISTAS ORDENADAS 101
/* Inicialização */
tipoLista *inicializa(void);
/*
* Procura x na lista iniciada por base, retornando um apontador
* para o registo que contem este valor (ou NULL se não existe)
*/
tipoLista *procura(tipoLista *base,tipoDados x);
tipoLista *procuraOrdenado(tipoLista *base,tipoDados x);
/*
* Insere x antes do registo "depois" e modificando o apontador "antes".
*/
void insere(tipoLista **antes, tipoDados x, tipoLista *depois);
/*
* Insere x na lista ordenada iniciada por base
* Devolve a base, eventualmente alterada
*/
tipoLista *insereOrdenado(tipoLista *base,tipoDados x);
/*
* Lista todos os elementos da estrutura.
*/
void listar(tipoLista *base);
/*
* Liberta da lista o elemento especificado por reg
*/
tipoLista *libertaReg(tipoLista *reg);
/*
* Apaga da lista o registo que contém x
* Retorna a base, eventualmente alterada
*/
tipoLista *apaga(tipoLista *base,tipoDados x);
#endif
Ficheiro lista.c
/*
*
*
*
Ficheiro: lista.c
Autor:
Fernando M. Silva
Data:
7/11/2000
102 L ISTAS DIN ÂMICAS
* Conteúdo:
*
Métodos para manipulação
*
de uma lista dinâmica
*
simples (ordenada)
*
*/
/*
* Inclui ficheiro com tipo e protótipos
*/
#include "lista.h"
#include "util.h"
tipoLista *novoNo(tipoDados x){
/*
* Cria um novo nó da lista
*/
tipoLista *novo = calloc(1,sizeof(tipoLista));
if(novo == NULL)
Erro("Erro na reserva de memória");
novo -> dados = x;
novo -> seg = NULL;
return novo;
}
tipoLista *inicializa(){
/*
* Cria uma nova lista
* Retorna:
*
lista inicializada
*/
return NULL;
}
tipoLista *procura(tipoLista *base,tipoDados x){
/*
* Procura um elemento na lista iniciada por base
* Argumentos:
*
base - apontador para a base da lista
*
x
- elemento a procurar
* Retorna
*
apontador para x (ou NULL caso nao encontre)
*/
tipoLista *aux = base;
while((aux!=NULL) && !igual(aux -> dados,x))
aux = aux -> seg;
return aux;
L ISTAS ORDENADAS 103
}
tipoLista *procuraOrdenado(tipoLista *base,tipoDados x){
/*
* Idêntico ao anterior, mas optimizado para listas
* ordenadas
* Argumentos:
*
base - apontador para a base da lista
*
x
- elemento a procurar
* Retorna
*
apontador para x (ou NULL caso nao encontre)
*/
tipoLista *aux = base;
while((aux!=NULL) && menor(aux -> dados,x))
aux = aux -> seg;
if((aux != NULL) && igual(aux -> dados ,x))
return aux;
else
return NULL;
}
void insere(tipoLista **antes, tipoDados x, tipoLista *depois){
/*
* Insere x entre dois registos
* Argumentos:
*
antes - predecessor na lista
*
x
- elemento a inserir
*
depois - elemento seguinte a x
*/
tipoLista *novo = novoNo(x);
*antes = novo;
novo -> seg = depois;
}
tipoLista *insereOrdenado(tipoLista *base,tipoDados x){
/*
* Insere x na lista ordenada
* Argumentos:
*
base - apontador para a base da lista
*
x
- elemento a procurar
* Retorna
*
base, eventualmente alterada
*/
tipoLista *act,*ant;
if(base == NULL){
insere(&base,x,NULL); /* Lista vazia */
104 L ISTAS DIN ÂMICAS
}
else if(menor(x,base -> dados)){
insere(&base,x,base); /* Insere *antes* da base */
}
else{
ant = base; act = base -> seg;
while((act != NULL) &&
(menor(act -> dados,x))){
/*
* Procura local de inserção
*/
ant = act; act = act -> seg;
}
insere(&(ant -> seg),x,act);
}
return base;
}
void listar(tipoLista *base ){
/*
* Lista todos os elementos
* Argumentos:
*
base - apontador para a base da lista
*/
while(base){
printf(" -> ");
escreveDados(base -> dados);
printf("\n");
base = base -> seg;
}
}
tipoLista *libertaReg(tipoLista *reg){
/*
* Remove da lista o elemento apontado por reg e
* liberta a memória associada.
* Argumentos:
*
reg - apontador para a variável da lista que
*
aponta para o registo a libertar
* Retorna - novo valor do apontandor
*/
tipoLista *aux;
aux = reg;
reg = reg -> seg;
free(aux);
return reg;
}
L ISTAS ORDENADAS 105
tipoLista *apaga(tipoLista *base,tipoDados x){
/*
* Apaga da lista o registo que contém x
* Argumentos:
*
base - apontador para a base da lista
*
x
- elemento a eliminar
* Retorna
*
base, eventualmente alterada
*/
tipoLista *aux;
aux = base;
if(base != NULL){
if(igual(base -> dados,x)){
base = libertaReg(base);
}
else{
aux = base;
while((aux -> seg != NULL) &&
(menor(aux -> seg -> dados,x)))
aux = aux -> seg;
if((aux -> seg != NULL) &&
igual(aux -> seg -> dados,x))
aux -> seg = libertaReg(aux -> seg);
}
}
return base;
}
Ficheiro main.c
/*
*
*
*
*
*
*
*
*
*
*
*
*
Ficheiro: main.c
Autor:
Fernando M. Silva
Data:
7/11/2000
Conteúdo:
Programa principal simples para teste
de estruturas dinâmicas ligadas.
Neste teste, os dados armazenados na lista
são fracções inteiras, implementadas
por um tipo abstracto "tipoDados".
Assim:
1. A especificação de um racional positivo,
106 L ISTAS DIN ÂMICAS
*
acrescenta o racional à lista
*
2. A introdução de um racional negativo,
*
especifica que deve ser apagada o seu
*
simétrico da lista
*
3. Com a entrada de um racional com valor 0,
*
termina o programa
*
*/
#include <stdio.h>
#include <stdlib.h>
#include "lista.h"
int main(){
tipoLista *base;
tipoDados x;
base = inicializa();
printf(" Programa para teste de uma lista "
"ordenada de racionais:\n");
printf("
- A introdução de um racional positivo "
"conduz à sua\n"
"
inserção ordenada na lista.\n");
printf("
- A introdução de um racional "
"negativo procura o seu\n"
"
simétrico na lista e, "
"caso exista, remove-o.\n");
x = leDados("\nIndique o numerador e denominador "
"de um racional:\n"
"(dois inteiros na mesma linha)");
while(numerador(x) != 0) {
if(valor(x) > 0){
base = insereOrdenado(base,x);
}
else{
x = simetrico(x);
if(procuraOrdenado(base,x) == NULL){
printf(" ************ Erro: elemento de "
"valor idêntico a ");
escreveDados(x);
printf(" não encontrado na lista\n");
}
else{
base = apaga(base,x);
}
}
printf("\nConteúdo actual da lista:\n");
VARIANTES 107
base
1
4
9
Figura 4.9: Lista de inteiros com registo separado para a base. Nesta figura, a lista tem apenas três
elementos efectivos (1, 4 e 9), sendo o primeiro registo utilizado apenas para o suporte da base da
lista.
listar(base);
x = leDados("\nIndique o numerador "
"e denominador de um racional:\n"
"(dois inteiros na mesma linha)");
}
printf("\n Racional com valor 0: fim do programa\n");
exit(0);
}
4.8
Variantes
4.8.1
Introdução
Embora a estrutura fundamental das listas dinâmicas seja no essencial a que se viu anteriormente, existem diversas variantes que têm como objectivo simplificar os mecanismos de acesso
ou ajustar a lista a objectivos especı́ficos.
4.8.2
Listas com registo separado para a base
Conforme se viu anteriormente, a manipulação de listas ordenadas exige que a base da lista
seja tratada como um caso particular. Uma forma de evitar estes testes adicionais é manter permanentemente um registo mudo no inı́cio da lista (registo separado para a base) que, embora não
seja utilizado de facto, permite simplificar o acesso aos restantes elementos. Adicionalmente, este
tipo de estrutura (v. figura 4.9 tem a vantagem do apontador para a base não ser modificado depois
da criação da lista.
As funções de manipulação da lista são no essencial semelhantes às da lista ordenada simples.
Embora sem listar aqui todas as funções de acesso, referem-se algumas das que são modificadas
pela existência de um registo permanente na base.
A inicialização da lista corresponde neste caso à criação do registo da base. Deste modo, a
108 L ISTAS DIN ÂMICAS
fim
1
5
8
9
inicio
Figura 4.10: Lista dupla de inteiros.
função de inicialização é dada por
Por outro lado, a função de inserção ordenada pode ser simplificada. Admitindo a utilização
da mesma função insere() já apresentado para a lista simples, a inserção pode ser feita por
onde se pode constatar a ausência do teste particular à base que se realiza na lista ordenada simples.
4.8.3
Listas duplamente ligadas
Um dos inconvenientes das listas simplesmente ligadas é serem unidireccionais. Por outras
palavras, ao aceder a um dado elemento da lista é fácil aceder ao elemento seguinte, mas o acesso
ao elemento anterior não é possı́vel.
Para evitar este inconveniente é possı́vel desenvolver uma lista duplamente ligada, em que
cada elemento dispõe de dois apontadores, um para o elemento seguinte e outro para o anterior.
Adicionalmente, tal como no caso da fila, o acesso à lista é geralmente mantido por dois apontadores, um para o inı́cio e outro para o fim da lista (v. figura 4.10). A declaração de uma lista
duplamente ligada pode ser realizada simplesmente por
typedef struct _tipoRegDupla{
tipoDados dados;
struct _tipoRegDupla *seg,*ant;
} tipoRegDupla;
typedef struct _tipoDupla{
tipoRegDupla inicio;
tipoRegDupla fim;
} tipoDupla;
A NEL DUPLO COM REGISTO SEPARADO PARA A BASE 109
base
1
4
4
9
Figura 4.11: Lista em anel de inteiros. O último elemento aponta para o primeiro
base
5
8
9
Figura 4.12: Anel duplo com registo separado para a base.
4.8.4
Aneis
Numa lista simplesmente ligada, o último da elemento da lista é identificado pelo facto do
apontador para o elemento seguinte ser NULL. Uma alternativa é colocar o último elemento da
lista a apontar para a base (v. figura 4.11). A manipulação de uma estrutura deste tipo é muito
semelhante à de uma lista simples, substituindo-se apenas parte das comparações com o valor
NULL por comparações com o apontador da base.
Uma lista em anel apresenta a vantagem do último elemento apontar para o primeiro, o que
pode ser conveniente em aplicações em que seja necessário percorrer os elementos da lista de uma
forma cı́clica.
4.9
4.9.1
Anel duplo com registo separado para a base
Introdução
Um anel duplo com registo separado para a base é uma estrutura dinâmica que combina as
diversas variantes abordadas anteriormente: registo separado para a base, ligação em anel e registos com apontadores bidireccionais (figura 4.12). Embora este tipo estrutura possa sugerir uma
manipulação à partida mais complexa, verifica-se na prática o inverso: a exploração correcta desta
estrutura origina, de modo geral, código mais simples.
110 L ISTAS DIN ÂMICAS
base
Figura 4.13: Anel vazio após a criação.
4.9.2
Declaração
A declaração de um anel é feita da forma habitual. Ou seja,
typedef struct _tipoAnel {
tipoDados dados;
struct _tipoAnel *seg,*ant;
} tipoAnel;
4.9.3
Inicialização
A inicialização de um anel corresponde à criação de um registo para a base e ao fecho em anel
das suas ligações (figura 4.13). Esta inicialização pode ser feita por
tipoAnel *inicializa(){
tipoAnel *aux;
tipoDados regMudo;
aux = novoNo(regMudo);
aux -> seg = aux -> ant = aux;
return aux;
}
A função novoNo(), semelhante às anteriores, pode ser definida como
tipoAnel *novoNo(tipoDados x){
tipoAnel *novo = calloc(1,sizeof(tipoAnel));
if(novo == NULL)
Erro("Erro na reserva de memória");
novo -> dados = x;
A NEL DUPLO COM REGISTO SEPARADO PARA A BASE 111
novo -> seg = novo -> ant = NULL;
return novo;
}
4.9.4
Listagem
A listagem de um anel pode ser feita por ordem directa ou inversa. Deste modo, podem ser
desenvolvidas duas funções para este efeito, de estrutura muito semelhante:
/*
Listagem directa
void listar(tipoAnel *base ){
tipoAnel *aux;
*/
aux = base -> seg;
while(aux != base){
printf(" -> ");
escreveDados(aux -> dados);
printf("\n");
aux = aux -> seg;
}
}
/*
Listagem inversa
*/
void listarInv(tipoAnel *base ){
tipoAnel *aux;
aux = base -> ant;
while(aux != base){
printf(" -> ");
escreveDados(aux -> dados);
printf("\n");
aux = aux -> ant;
}
}
Repare-se que em qualquer das duas funções o inı́cio da listagem se efectua no elemento a seguir
à base (de modo a saltar o registo da base), enquanto que na condição de manutenção no ciclo se
testa o regresso à base.
4.9.5
Procura
A função de procura é semelhante à de uma lista ordenada, omitindo o elemento inicial:
112 L ISTAS DIN ÂMICAS
tipoAnel *procuraOrdenado(tipoAnel *base,tipoDados x){
tipoAnel *aux;
base -> dados = x;
aux = base -> seg;
while(menor(aux -> dados,x))
aux = aux -> seg;
if((aux != base) && (igual(aux -> dados,x)))
return aux;
else
return NULL;
}
Repare-se que, para simplificar a condição do ciclo, se iniciou o registo da base com o próprio
valor do elemento a procurar. Este artifı́cio garante que, mesmo que o elemento de procura não
se encontre no anel, a procura é interrompida quando se atinge a base. Claro que, deste modo,
é preciso testar à saı́da do ciclo se a interrupção se verificou por ter encontrado o local real de
interrupção e o elemento de procura, ou por se ter encontrado o elemento artificialmente colocado
na base. Neste último caso deverá retornar-se o apontador NULL.
4.9.6
Inserção
No caso de inserção ordenada no anel, é particularmente útil utilizar uma função só para a
inserção do registo, admitindo que já se conhece o local de inserção, e desenvolver posteriormente
a função de procura o local de inserção.
A primeira destas funções pode ser definida como
void insere(tipoAnel *depois,tipoDados x){
tipoAnel *novo = novoNo(x);
novo -> seg = depois;
/* (1) */
novo -> ant = depois -> ant;
/* (2) */
depois -> ant = novo;
/* (3) */
novo -> ant -> seg = novo;
/* (4) */
}
Apesar da aparente complexidade da função, a sua realização corresponde apenas à realização
das ligações necessárias pela ordem correcta. Na figura 4.14 detalha-se este processo de inserção
no caso de um anel de inteiros, identificando-se a correspondência entre as ligação e as instruções
da listagem.
A NEL DUPLO COM REGISTO SEPARADO PARA A BASE 113
depois
1
8
(2)
(4)
novo
(1)
(3)
3
Figura 4.14: Inserção num anel. Os números entre () correspondem às atribuições da listagem
apresentada no texto.
Repare-se que, dado que a lista é dupla, é suficiente o apontador para o elemento seguinte para
estabelecer todas as ligações.
A função de inserção propriamente dita realiza apenas a pesquisa do local de inserção. De
forma semelhante ao já efectuado no caso da função de procura, é possı́vel colocar uma cópia
do elemento a inserir no registo da base para permitir que o caso particular de inserção no final
da lista não tem que ser tratado como um caso particular. Deste modo, o código da função fica
particularmente simples:
void insereOrdenado(tipoAnel *base,tipoDados x){
tipoAnel *act;
base -> dados = x;
act = base -> seg;
while(menor(act -> dados,x))
act = act -> seg;
insere(act,x);
}
4.9.7
Remoção
A operação de remoção pode ser realizada por duas funções complementares. A primeira
(removeReg()) é utilizada após a identificação do registo a eliminar e é responsável pela
libertação da memória ocupada e reconstrução das ligações. A segunda (apaga()) que corresponde à função a utilizar externamente, procura o registo a eliminar e, caso o identifique, chama
114 L ISTAS DIN ÂMICAS
a primeira.
void removeReg(tipoAnel *reg){
reg -> seg -> ant = reg -> ant;
reg -> ant -> seg = reg -> seg;
free(reg);
}
void apaga(tipoAnel *base,tipoDados x){
tipoAnel *aux;
base -> dados = x;
aux = base -> seg;
while(menor(aux -> dados,x))
aux = aux -> seg;
if((aux != base) && igual(aux -> dados,x))
removeReg(aux);
}
4.9.8
Exemplo
Utiliza-se neste caso o mesmo exemplo de listagem de racionais já apresentado anteriormente.
Neste caso, omite-se a listagem dos métodos do tipo tipoDados, e os ficheiros util.c e
util.h, obviamente idêntico ao anterior.
Ficheiro anel.h
/*
* Ficheiro: anel.h
* Autor:
Fernando M. Silva
* Data:
7/11/2000
* Conteúdo:
*
Ficheiro com declaração de tipos e
*
protótipos dos métodos para manipulação
*
de um anel com registo seoparado
*
para a base
*
*/
#ifndef _ANEL_H
#define _ANEL_H
#include <stdio.h>
A NEL DUPLO COM REGISTO SEPARADO PARA A BASE 115
#include <stdlib.h>
/*
* Tipo dos dados da lista
*/
#include "dados.h"
/*
* Definição de tipoAnel
*/
typedef struct _tipoAnel {
tipoDados dados;
struct _tipoAnel *seg,*ant;
} tipoAnel;
/*
* Protótipos dos métodos de acesso
*/
/* Inicialização */
tipoAnel *inicializa(void);
/*
* Procura x na lista iniciada por base, retornando um apontador
* para o registo que contem este valor (ou NULL se não existe)
*/
tipoAnel *procura(tipoAnel *base,tipoDados x);
tipoAnel *procuraOrdenado(tipoAnel *base,tipoDados x);
/*
* Insere x antes do registo "depois"
*/
void insere(tipoAnel *depois,tipoDados x);
/*
* Insere x na lista ordenada iniciada por base
*/
void insereOrdenado(tipoAnel *base,tipoDados x);
/*
* Lista todos os elementos da estrutura.
*/
void listar(tipoAnel *base);
void listarInv(tipoAnel *base);
/*
*
Remove da lista o elemento apontado por reg
116 L ISTAS DIN ÂMICAS
*/
void libertaReg(tipoAnel *reg);
/*
* Apaga da lista o registo que contém x
*/
void apaga(tipoAnel *base,tipoDados x);
#endif
Ficheiro anel.c
/*
*
*
*
*
*
*
*
*
*/
Ficheiro: anel.c
Autor:
Fernando M. Silva
Data:
7/11/2000
Conteúdo:
Métodos para manipulação
de um anel com registo separado
para a base.
/*
* Inclui ficheiro com tipo e protótipos
*/
#include "anel.h"
#include "util.h"
tipoAnel *novoNo(tipoDados x){
/*
* Cria um novo nó da lista
*/
tipoAnel *novo = calloc(1,sizeof(tipoAnel));
if(novo == NULL)
Erro("Erro na reserva de memória");
novo -> dados = x;
novo -> seg = novo -> ant = NULL;
return novo;
}
/* Inicialização. O anel vazio é constituı́da pelo
* registo da base.
*/
tipoAnel *inicializa(){
A NEL DUPLO COM REGISTO SEPARADO PARA A BASE 117
tipoAnel *aux;
tipoDados regMudo;
aux = novoNo(regMudo);
aux -> seg = aux -> ant = aux;
return aux;
}
/*
* Procura x no anel iniciada por base, retornando um apontador
* para o registo que contem este valor (ou NULL se não existe)
*
* Este procedimento realiza uma busca exaustiva em todo o anel
*/
tipoAnel *procura(tipoAnel *base,tipoDados x){
tipoAnel *aux;
base -> dados = x;
aux = base -> seg;
while(!igual(aux -> dados,x))
aux = aux -> seg;
return (aux == base ? NULL : aux);
}
/*
* Idêntico ao anterior, mas optimizado para aneis
* ordenadas (a procura para logo que seja atingido
* um elemento igual ou SUPERIOR a x).
*/
tipoAnel *procuraOrdenado(tipoAnel *base,tipoDados x){
tipoAnel *aux;
base -> dados = x;
aux = base -> seg;
while(menor(aux -> dados,x))
aux = aux -> seg;
if((aux != base) && (igual(aux -> dados,x)))
return aux;
else
return NULL;
}
/*
* Insere x antes do registo "depois"
*/
void insere(tipoAnel *depois,tipoDados x){
tipoAnel *novo = novoNo(x);
118 L ISTAS DIN ÂMICAS
novo -> seg = depois;
novo -> ant = depois -> ant;
depois -> ant = novo;
novo -> ant -> seg = novo;
}
/*
* Insere x no anel ordenada iniciada por base
*/
void insereOrdenado(tipoAnel *base,tipoDados x){
tipoAnel *act;
base -> dados = x;
act = base -> seg;
while(menor(act -> dados,x)){
/*
* Procura local de inserção
*/
act = act -> seg;
}
insere(act,x);
}
/*
* Lista todos os elementos da estrutura.
*/
void listar(tipoAnel *base ){
tipoAnel *aux;
aux = base -> seg;
while(aux != base){
printf(" -> ");
escreveDados(aux -> dados);
printf("\n");
aux = aux -> seg;
}
}
/*
* Lista todos os elementos da estrutura
* por ordem inversa.
*/
void listarInv(tipoAnel *base ){
tipoAnel *aux;
aux = base -> ant;
while(aux != base){
printf(" -> ");
escreveDados(aux -> dados);
A NEL DUPLO COM REGISTO SEPARADO PARA A BASE 119
printf("\n");
aux = aux -> ant;
}
}
/*
* Remove do anel o elemento apontado por reg
* e liberta a memória associada.
*/
void libertaReg(tipoAnel *reg){
reg -> seg -> ant = reg -> ant;
reg -> ant -> seg = reg -> seg;
free(reg);
}
/*
* Apaga do anel o registo que contém x
* Retorna a base, eventualmente alterada
*/
void apaga(tipoAnel *base,tipoDados x){
tipoAnel *aux;
base -> dados = x;
aux = base -> seg;
while(menor(aux -> dados,x))
aux = aux -> seg;
if((aux != base) && igual(aux -> dados,x))
libertaReg(aux);
}
Ficheiro main.c
/*
*
*
*
*
*
*
*
*
*
*
*
*
Ficheiro: main.c
Autor:
Fernando M. Silva
Data:
7/11/2000
Conteúdo:
Programa principal simples para teste
de estruturas dinâmicas ligadas.
Neste teste, os dados armazenados na lista
são fracções inteiras, implementadas
por um tipo abstracto "tipoDados".
Assim:
1. A especificação de um racional positivo,
120 L ISTAS DIN ÂMICAS
*
acrescenta o racional à lista
*
2. A introdução de um racional negativo,
*
especifica que deve ser apagada o seu
*
simétrico da lista
*
3. Com a entrada de um racional com valor 0,
*
termina o programa
*
*/
#include <stdio.h>
#include <stdlib.h>
#include "anel.h"
int main(){
tipoAnel *base;
tipoDados x;
base = inicializa();
printf(" Programa para teste de uma lista ordenada de racionais:\n");
printf("
- A introdução de um racional positivo conduz à sua\n"
"
inserção ordenada na lista.\n");
printf("
- A introdução de um racional negativo procura o seu\n"
"
simétrico na lista e, caso exista, remove-o.\n");
x = leDados("\nIndique o numerador e denominador de um racional:\n"
"(dois inteiros na mesma linha)");
while(numerador(x) != 0) {
if(valor(x) > 0){
insereOrdenado(base,x);
}
else{
x = simetrico(x);
if(procuraOrdenado(base,x) == NULL){
printf(" ************ Erro: elemento de valor idêntico a ");
escreveDados(x);
printf(" não encontrado na lista\n");
}
else{
apaga(base,x);
}
}
printf("\nConteúdo actual do anel (ordem crescente):\n");
listar(base);
printf("\nConteúdo por ordem inversa:\n");
listarInv(base);
x = leDados("\nIndique o numerador e denominador de um racional:\n"
"(dois inteiros na mesma linha)");
}
L ISTAS DE LISTAS 121
base
Figura 4.15: Lista de listas.
printf("\n Racional com valor 0: fim do programa\n");
exit(0);
}
4.10
Listas de listas
É frequente a implementação de uma dada aplicação requerer a utilização hierárquica de diversas listas. Por exemplo, um sistema de arquivo de documentos pode basear-se numa lista de
categorias, em que cada categoria tem associada, por sua vez, uma lista de documentos dessa categoria. Eventualmente, cada um destes documentos pode ainda ter associado uma lista especı́fica,
como uma lista das datas em que o documento foi alterado e as alterações fundamentais de cada
vez. Uma representação simbólica de uma lista de listas está representada na figura 4.15.
Uma lista de listas (ou um anel de anéis) nada tem de particular do ponto de vista de
programação. Cada lista por si só ú uma estrutura do tipo apontado anteriormente. No entanto,
é necessário ter em atenção que a lista e as suas sublistas têm tipos diferentes e, de acordo com
o modelo que temos vindo a desenvolver, cada uma delas precisará de um método especı́fico de
acesso. Por outras palavras, será necessário manter duas funções de listagem, duas funções de
inserção, etc, dado que cada tipo de lista exige um método especı́fico2 .
A declaração de uma lista de lista pode ser efectuada pelo código
typedef struct _tipoSubLista {
/*
2
De facto, esta duplicação de código pode ser evitada escrevendo código baseado em apontadores genéricos do tipo
void*. Esta possibilidade não será, por agora, abordada
122 L ISTAS DIN ÂMICAS
tipoDadosSubLista descreve todos os
atributos de cada elemento de uma
sublista
*/
tipoDadosSubLista dadosSubLista;
struct _tipoSubLista *seg;
} tipoSubLista;
typedef struct _tipoDadosLista{
/*
declaração dos campos necessários
a cada elemento da lista
principal
int ...
char ...
*/
tipoSubLista *baseSub;
} tipoDadosLista;
typedef struct _tipoListaDeListas{
tipoDadosLista dados;
struct _tipoListaDeListas *seg;
} tipoListaDeListas;
Note-se que se adoptou aqui quatro tipos abstractos distintos: o tipo tipoDadosSubLista,
que suporta os dados de cada sublista, o tipo tipoSubLista, que suporta as sublistas, o tipo
tipoDadosLista que suporta o tipo de dados da lista principal e, finalmente, o tipoListaDeListas, que suporta a lista principal.
A manipulação da lista faz-se pela combinação das funções (métodos) desenvolvidos para
cada tipo de objecto. Admita-se, por exemplo, que no programa principal foi declarada uma lista
de listas
tipoListaDeListas *base;
que foi de alguma forma inicializada. Suponha-se agora que é necessário inserir uma variável
x de tipoDados na sublista suportada no elemento da lista principal que tem o valor y. O código
para este efeito seria:
tipoListaDeListas *base,*aux;
tipoDadosSubLista x;
tipoDadosLista
y;
L ISTAS DE LISTAS 123
/*
inicialização da lista e dos valores x e y
...
*/
aux = procuraOrdenadoListaDeListas(base,y);
if(aux == NULL)
fprintf(stderr,"Erro: valor não encontrado na lista principal");
else
insereDados(aux -> dados,x);
/*
...
*/
A função insereDados é nova neste contexto, e deverá ser um método especı́fico de
tipoDadosLista. A sua estrutura é muito simples, e a sua existência deve-se apenas à necessidade de manter uma realização correcta da abstracção de dados. Esta função seria
void insereDados(tipoDadosLista dados,tipoDadosSubLista x){
insereDadosSubLista(dados.baseSub,x);
}
sendo a função insereDadosSubLista uma função convencional de inserção.
Capı́tulo 5
Conclusões
O C é provavelmente a mais flexı́vel das linguagens de programação de alto-nı́vel, mas apresenta uma relativa complexidade sintáctica. Uma das maiores dificuldades na abordagem do
C numa disciplina introdutória de programação é a necessidade de introduzir os conceitos de
endereço de memória, apontador e memória dinâmica.
Neste texto introduziu-se a noção de apontador e discutiu-se o problema da manipulação de
estruturas de dados dinâmicas em C. Apesar da introdução de diversas estruturas de dados, o
primeiro objectivo deste texto foi, sobretudo, o de tentar explicar os mecanismos essenciais de
manipulação de apontadores e gestão de memória dinâmica em C, utilizando-se algumas estruturas
de dados simples para exemplificar estes mecanismos. O aprofundamento destes temas tem o seu
seguimento natural numa disciplina especı́fica de Algoritmos e Estruturas de Dados, ou em textos
especı́ficos de algoritmia, como (Sedgwick, 1990; Cormen e outros, 1990; Knuth, 1973).
Bibliografia
Cormen, T. H., Leiserson, C. E., e Rivest, R. L. (1990). Introduction to Algorithms. MIT
Press/McGraw-Hill.
Kernighan, B. e Ritchie, D. (1978). The C Programming Language. Prentice-Hall.
Knuth, D. E. (1973). Fundamental Algorithms, volume 1 of The Art of Computer Programming,
section 1.2, páginas 10–119. Addison-Wesley, Reading, Massachusetts, second edition.
Martins, J. P. (1989). Introduction to Computer Science Using Pascal. Wadsworth Publishing Co.,
Belmont, California.
Ritchie, D. e Thmompson, K. (1974). The unix time sharing system. Commun ACM, páginas
365–375.
Sedgwick (1990). Algorithms in C. Addison Wesley.
B IBLIOGRAFIA 129
Apêndice A
Programa de teste que valida a consistência das atribuições da tabela 2.1, apresentada na
secção 2.6.4. Note-se que o facto de o programa compilar sem erros garante a consistência dos
tipos nas atribuições realizadas.
Nos processadores da famı́lia Intel, cada endereço de memória especifica apenas um byte,
apesar de, nos processadores 486 e seguintes, cada operação de acesso à memória se realizar em
palavras de 4 bytes (32 bits). De forma a obter-se valores equivalentes ao do modelo de memória
usado nos exemplos, realiza-se uma divisão por quatro e ajusta-se o endereço escrito no monitor
de forma a que o elemento x[0][0] surja com o valor 1001.
#include <stdio.h>
float x[3][2] = {{1.0,2.0},{3.0,4.0},
{5.0,6.0}};
void escreveEndereco(int n){
n = (n - (int) x)/4 + 1001;
printf("endereco = %d\n",n);
}
int main(){
float (*pv3)[2];
float *pf;
float f;
}
pv3 = x;
pv3 = x + 1;
escreveEndereco((int) pv3);
escreveEndereco((int)pv3);
pf = *(x+1);
pf = *(x+2)+1;
f = *(*(x+2)+1);
escreveEndereco((int)pf);
escreveEndereco((int)pf);
printf("%4.1f\n",f);
pf = *x;
escreveEndereco((int)pf);
f = **x;
f = *(*x+1);
printf("%4.1f\n",f);
printf("%4.1f\n",f);
pf = x[1];
return 0;
escreveEndereco((int)pf);