Apontadores e Estruturas de Dados Dinâmicas em C

Apontadores e Estruturas de Dados Dinamicas em C

Fernando Mira da Silva

Departamento de Engenharia Electrotecnica e de Computadores

Instituto Superior Tecnico

Novembro de 2002

Resumo

O C e provavelmente a mais flexıvel das linguagens de programacao de alto-nıvel, mas ap-

resenta uma relativa complexidade sintactica. Uma das maiores dificuldades na abordagem do

C numa disciplina de introdutoria de programacao e a necessidade de introduzir os conceitos de

endereco de memoria, apontador e memoria dinamica.

Este texto foi preparado para apoioa disciplina de Introducaoa Programacao da Licenciatura

em Engenharia Electrotecnica e Computadores do Instituto Superior Tecnico. Este texto tenta

focar de modo sistematico alguns dos topicos que maiores duvidas suscita nas abordagens iniciais

da linguagem: apontadores e estruturas de dados dinamicas. Assim, embora se pressuponha o

conhecimentos dos elementos basicas da linguagem C por parte do leitor – nomeadamente, os

tipos de dados elementares e as estruturas de controlo – o textoe mantido ao nıvel elementar de

uma disciplina introdutoria de informatica.

Na apresentacao das estruturas de dados consideradas, que incluem pilhas, filas, listas e

aneis, introduz-se de forma natural a nocao de abstraccao de dados, e os princıpios essenciais

de estruturacao e modularidade baseados neste paradigma de programacao.

Para o programador experiente em C, alguns dos exemplos de codigo poderao parecer pouco

optimizados. Trata-se de uma opcao premeditada que tenta beneficiar a clareza e a simplicidade

algorıtmica, ainda que em alguns casos esta opcao possa sacrificar ligeiramente a eficiencia do

codigo apresentado. Pensamos, no entanto, que estae a opcao correcta numa abordagem intro-

dutoria da programacao.

Indice

1 Introduc ao 1

2 Apontadores 5

2.1 Motivacao para os apontadores em C . . . . . . . . . . . . . . . . . . . . . . . . 5

2.2 Modelos de memoria em C . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 5

2.3 Apontadores . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 7

2.4 Funcoes e passagem por referencia . . . . . . . . . . . . . . . . . . . . . . . . . 11

2.4.1 Passagem por referencia . . . . . . . . . . . . . . . . . . . . . . . . . . 11

2.4.2 Erros frequentes . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 16

2.5 Vectores e apontadores . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 18

2.5.1 Declaracao de vectores . . . . . . . . . . . . . . . . . . . . . . . . . . . 18

2.5.2 Aritmetica de apontadores . . . . . . . . . . . . . . . . . . . . . . . . . 22

2.5.3 Indices e apontadores . . . . . . . . . . . . . . . . . . . . . . . . . . . . 25

2.5.4 Vectores como argumentos de funcoes . . . . . . . . . . . . . . . . . . . 26

2.6 Matrizes . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 28

2.6.1 Declaracao . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 28

IV INDICE

2.6.2 Matrizes como argumento de funcoes . . . . . . . . . . . . . . . . . . . 29

2.6.3 Matrizes e vectores . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 31

2.6.4 Matrizes e apontadores . . . . . . . . . . . . . . . . . . . . . . . . . . . 34

2.7 Generalizacao para mais do que duas dimensoes . . . . . . . . . . . . . . . . . . 38

3 Vectores e memoria dinamica 41

3.1 Introducao . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 41

3.2 Vectores . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 43

3.3 “Vectores” dinamicos . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 46

3.4 Gestao da memoria dinamica . . . . . . . . . . . . . . . . . . . . . . . . . . . . 48

3.4.1 Verificacao da reserva de memoria . . . . . . . . . . . . . . . . . . . . . 48

3.4.2 Outras funcoes de gestao de memoria dinamica . . . . . . . . . . . . . . 50

3.4.3 Garbbage. . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 52

3.5 Criacao dinamica de matrizes . . . . . . . . . . . . . . . . . . . . . . . . . . . . 55

3.5.1 Introducao . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 55

3.5.2 Matrizes estaticas . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 55

3.5.3 Matrizes dinamicas . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 56

3.5.4 Vectores de apontadores e matrizes . . . . . . . . . . . . . . . . . . . . 58

4 Listas dinamicas 61

4.1 Introducao . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 61

4.2 Abstraccao de dados . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 62

INDICE V

4.3 Listas . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 63

4.4 Listas dinamicas: listar elementos . . . . . . . . . . . . . . . . . . . . . . . . . 66

4.5 Listas: pilhas . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 68

4.5.1 Introducao . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 68

4.5.2 Declaracao . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 70

4.5.3 Inicializacao . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 70

4.5.4 Sobreposicao . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 71

4.5.5 Remocao . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 72

4.5.6 Teste . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 72

4.5.7 Exemplo . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 73

4.6 Listas: filas . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 80

4.6.1 Introducao . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 80

4.6.2 Declaracao . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 80

4.6.3 Inicializacao . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 81

4.6.4 Insercao . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 82

4.6.5 Remocao . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 83

4.6.6 Teste . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 83

4.6.7 Exemplo . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 84

4.7 Listas ordenadas . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 87

4.7.1 Introducao . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 87

4.7.2 Declaracao e inicializacao . . . . . . . . . . . . . . . . . . . . . . . . . 88

VI INDICE

4.7.3 Listagem ordenada . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 89

4.7.4 Procura . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 89

4.7.5 Abstraccao de dados e metodos de teste . . . . . . . . . . . . . . . . . . 91

4.7.6 Insercao ordenada . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 92

4.7.7 Remocao . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 95

4.7.8 Exemplo . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 96

4.8 Variantes . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 107

4.8.1 Introducao . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 107

4.8.2 Listas com registo separado para a base . . . . . . . . . . . . . . . . . . 107

4.8.3 Listas duplamente ligadas . . . . . . . . . . . . . . . . . . . . . . . . . 108

4.8.4 Aneis . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 109

4.9 Anel duplo com registo separado para a base . . . . . . . . . . . . . . . . . . . . 109

4.9.1 Introducao . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 109

4.9.2 Declaracao . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 110

4.9.3 Inicializacao . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 110

4.9.4 Listagem . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 111

4.9.5 Procura . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 111

4.9.6 Insercao . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 112

4.9.7 Remocao . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 113

4.9.8 Exemplo . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 114

4.10 Listas de listas . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 121

INDICE VII

5 Conclusoes 125

Bibliografia 127

Capıtulo 1

Introduc ao

Ate ao aparecimento da linguagem C, as linguagens de alto-nıvel tinham por objectivo dis-

tanciar o programador do hardware especıfico de trabalho. Pretendia-se, deste modo, que o pro-

gramador focasse a sua actividade na solucao conceptual e algorıtmica do problema e, simultane-

amente, que o codigo final fosse independente do hardware e, como tal, facilmente portavel entre

diferentes plataformas.

Este princıpio teorico fundamental, ainda hoje correcto em muitasareas de aplicacao de soft-

ware, 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 codigo ou, em outros casos, por ser conveniente ou desejavel explorar deter-

minadas facilidades oferecidas pelas instrucoes do processador que nao estavam directamente

disponıveis na linguagem de alto-nıvel. Nestas situacoes, aunica alternativa era a programacao

directa em linguagem maquina destes blocos de codigo, opcao que implicava a revisao do software

em cada alteracao ou evolucao de hardware.

Por razoes semelhantes, quer o sistema operativo quer ferramentas de sistema como com-

piladores, gestores de ficheiros ou monitores de sistema eram consideradas aplicacoes que, por

requisitos de eficiencia do codigo, 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 corolario, estas aplicacoes eram tradicionalmente escritas total-

mente em linguagem maquina, implicando um enorme esforco de desenvolvimento e manutencao

em cada evolucao 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 INTRODUCAO

Digital PDP-10. O B era uma linguagem proxima da linguagem maquina, mas que facilitava ex-

traordinariamente a programacao 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 fa-

cilidades simples, geralmente so acessıveis em linguagem maquina, como o acesso a enderecos de

memoria e a metodos de enderecamento indirecto. De facto, os mecanismos de acesso a variaveis

e estruturas de dados previstos no B cobriam a esmagadora maioria das necessidades dos progra-

madores quando anteriormente eram obrigados a recorrera linguagem maquina. Ora estes mecan-

ismos, embora obviamente dependentes do hardware, obedeciam na sua generalidade ao modelo

de memoria 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 enderecamento

e facilidades disponıveis ao nıvel da linguagem maquina 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 nucleo do sistema operativo Unix em alto-nıvel.

Para alem da manipulacao directa de enderecos de memoria, uma das facilidades introduzida

pela linguagem C foi a incorporacao de mecanismos para gestao de memoria dinamica. O conceito

de memoria dinamica permite que um programa ajuste de modo flexıvel a dimensao da memoria

que utiliza de acordo com as suas necessidades efectivas. Por exemplo, um mesmo programa de

processamento de texto pode ocupar pouca memoria se estiver a tratar um documento de pequena

dimensao, ou ocupar um volume mais significativo no caso de um documento de maior numero de

paginas.

A invencao da linguagem C (Kernighan e Ritchie, 1978) permitiu a re-escrita de 90% do

nucleo do sistema operativo Unix em linguagem de alto-nıvel. A possibilidade de manipular

enderecos de memoria permitiu ainda a implementacao eficiente em linguagem de alto nıvel de

muitos algoritmos e estruturas de dados ate entao geralmente escritos em linguagemAssembler

(Knuth, 1973).

Neste texto apresenta-se uma introducao aos apontadores e memoria dinamica na linguagem

de programacao C. Para exemplificar estes conceitos, sao introduzidas algumas estruturas de dados

dinamicas simples, como pilhas, filas, listas e aneis. Durante a exposicao, introduz-se de forma

natural a nocao de abstraccao de dados, e os princıpios essenciais de estruturacao e modularidade

baseados neste paradigma de programacao. Deste modo, a nocao de abstraccao de dados naoe in-

troduzida formalmente num capıtulo autonomo, mas sim quando se instroduzem listas dinamicas,

altura em que o conceitoe fundamental para justificar a estrutura adoptada. Esta abordagem, em-

bora pouco convencional, deriva da nossa experiencia na docencia da disciplina de Introducao a

Programacao durante varios anos no IST, tendo beneficiado das crıticas e sugestoes de diversas

3

geracoes de alunos.

Tenta-se neste texto dar-se primaziaa clareza algorıtmica e legibilidade do codigo, ainda

que em alguns casos esta opcao possa sacrificar pontualmente a eficiencia do codigo produzido.

Considera-se, no entanto, quee esta a abordagem mais adequada numa disciplina de Introducao

a Programacao. Por outro lado, a maioria dos compiladores recentes incluem processos de

optimizacao que dispensam a utilizacao explıcita dos mecanismos de optimizacao previstos origi-

nalmente na linguagem C.

Capıtulo 2

Apontadores

2.1 Motivac ao para os apontadores em C

2.2 Modelos de mem oria em C

Embora os mecanismos de enderecamento e acessoa memoria tenham sofrido varias

evolucoes nasultimas decadas e sejam evidentemente dependentes do hardware, o C requer apenas

hipoteses muito simples relativamente ao modelo de memoria do processador.

A memoria de um computador encontra-se organizada em celulas oupalavras de memoria

individuais. Cada palavra de memoria e referenciada por um endereco e armazena um dado

conteudo. Designa-se por “numero de bits da arquitectura” o numero maximo de bits que um

processadore capaz de ler numunico acessoa memoria. Cada palavra de memoria de referencia

de um processador tem em geral um numero de bits identico ao numero de bits da arquitectura1.

Admita-se que num dado programa em C declara, entre outras as variaveisi,j,k com o tipo

int , a variavel f com o tipofloat e uma variavel d do tipo double , nao necessariamente

por esta ordem. Admita-se que apos a declaracao destas variaveis sao realizadas as seguintes

atribuicoes:

i = 2450; j = 11331; k = 113; f = 225.345; d = 22.5E+145;

1A complexidade dos modos de enderecamento dos processadores actuais conduz a que a definicao e os modelos

aqui apresentados pequem por uma simplicidade excessiva, mas sao suficientes para os objectivos propostos.

6 APONTADORES

...

......

...

...1001

1002

1003

1004

1005

1006

1007

1008

1009

Endereço

113

11331

225.345

22.5E145 (double, 64bits)

2450 i

f

d

k

j

???

???

???

Conteúdo Variável

Figura 2.1: Modelo de memoria em C (exemplo).

Um exemplo esquematico de um modelo memoria correspondente a esta configuracao encontra-se

representado na figura 2.1. Admite-se aqui que a palavra de memoria e o tipo inteiro sao repre-

sentados por 32 bits. De acordo com a figura, durante a compilacao foram atribuıdosas variaveis

i,j,k,f os enderecos 1002,1005, 1006 e 1004, respectivamente, enquanto quea variaveld foi

atribuıdo o endereco 10072 . Note-se que, com excepcao do tipodouble , cada variavel tem uma

representacao interna de 32 bits, ocupando por isso apenas um endereco de memoria. A variavel

d, de tipodouble , tem uma representacao interna de 64 bits, exigindo por isso duas palavras de

memoria: os enderecos 1007 e 1008. Na figura 2.1 encontram-se representados outras posicoes

de memoria, provavelmente ocupadas por outras variaveis, e cujo conteudo e desconhecido do

programador.

2Estritamente falando, a cada variavel local,e apenas atribuıdo um endereco relativo durante a compilacao, sendo o

endereco final fixado durante a execucao da funcao ou activacao do bloco de instrucoes em que a declaracaoe realizada.

Este tema voltara a ser abordado na seccao 3.2.

APONTADORES 7

2.3 Apontadores

Um apontador em Ce uma variavel cujo conteudo e um endereco de outra posicao de

memoria. A declaracao de variaveis do tipo apontador pode ser construıda a partir de qualquer

tipo definido anteriormente, e deve especificar o tipo de variavel referenciada pelo apontador.

A declaracao de uma variavel do tipo apontador realiza-se colocando um “*” antes do nome

da variavel. Assim, na declaracao

double *pd;int i;int *pi;float f;int j,k;double d;int m,*pi2;double *pd2,d2;

as variaveisi,j,k,m sao do tipoint , f e do tipofloat , ed,d2 sao do tipodouble . Alem

destas variaveis de tipos elementares, sao declaradas as variaveispi, pi2 do tipo apontador

para inteiro, enquanto quepd epd2 sao do tipo apontador paradouble .

Admita-se agora se realiza a seguinte sequencia de atribuicoes:

i = 2450; f = 225.345; k = 113; d = 22.5E145; m = 9800;

Apos estas instrucoes, o mapa de memoria poderia ser o representado na figura 2.2, situacao

A. Sublinhe-se que as variaveis de tipo apontador apenas contem um endereco de memoria, in-

dependentemente do tipo referenciado. Desta forma, todas as variaveis de tipo apontador tem

uma representacao igual em memoria, normalmente de dimensao identica ao do tipo inteiro (uma

palavra de memoria). Note-se que o conteudo dos apontadores, tal como o de algumas variaveis

elementares, ainda nao foi inicializado, pelo que surgem representados com??? . E importante

compreender que cada uma destas variaveis tem de facto um conteudo arbitrario, resultante da

operacao anterior do computador. Claro que estes valores, nao tido sido ainda inicializados pelo

programa, sao desconhecidos do programador, mas esta situacao nao deve ser confundida com a

“ausencia de conteudo”, erro de raciocınio frequentemente cometido por programadores principi-

antes.

As variaveis de tipo elementar podem ser inicializadas pela atribuicao directa de valores con-

stantes. A mesma tecnica pode ser utilizada para a inicializacao de apontadores, embora este

8 APONTADORES

.........

......

1001

1002

1003

1004

1005

1006

1007

1008

1009

Endereço

113

9800

225.345

22.5E145 (double, 64bits)

2450 i

f

d

k

j

pd

pi

1010

1011

1012

1013

pi2

pd2

d2

m

???

???

???

???

(double, 64bits)???

???

Conteúdo Variável

A

.........

......

1001

1002

1003

1004

1005

1006

1007

1008

1009

Endereço

9800

225.345

22.5E145

1007

1006

2450 i

f

d

k

j

pi

1010

1011

1012

1013

pi2

pd2

d2

m

???

???

???(double, 64bits)

(double, 64bits)

113

???

Conteúdo Variável

pd

B

.........

......

1001

1002

1003

1004

1005

1006

1007

1008

1009

Endereço

225.345

22.5E145

1007

1006

2450 i

f

d

k

j

pi

1010

1011

1012

1013

pi2

pd2

d2

m

(double, 64bits)

(double, 64bits)

113

???

9800

1006

1007

Conteúdo Variável

pd

???

C

.........

......

1001

1002

1003

1004

1005

1006

1007

1008

1009

Endereço

225.345

22.5E145

1007

1006

2450 i

f

d

k

j

pi

1010

1011

1012

1013

pi2

pd2

d2

m

(double, 64bits)

(double, 64bits)

113

9800

1006

1007

Conteúdo Variável

pd

22.5E145

113

D

.........

......

1001

1002

1003

1004

1005

1006

1007

1008

1009

Endereço

225.345

22.5E145

1007

1006

2450 i

f

d

k

j

pi

1010

1011

1012

1013

pi2

pd2

d2

m

(double, 64bits)

(double, 64bits)

113

Conteúdo Variável

pd

113

1012

22.5E144

1002

24500

E

.........

......

Endereço Conteúdo Variável

i1

i2

5001

5002

5003

5004

5005

5006

5007

5008

5009

5010

5011

5012

5013

pi1

pi2

pi3

k1

k2

pk1

pk2

5001

3

4

5003

5004

5006

5003

10

46

F

Figura 2.2: Mapa de memoria apos diferentes sequencias de atribuicao (explicacao no texto).

APONTADORES 9

metodo raramente seja utilizado: em geral, o programador nao sabe quais os enderecos de memoria

disponıveis no sistema, e a manipulacao directa de enderecos absolutos tem reduzidas aplicacoes

praticas.3 Assim, A inicializacao de apontadorese geralmente realizada por outros metodos, entre

os quais a utilizacao do endereco de outras variaveis ja declaradas. Este endereco pode ser obtido

em C aplicando o operador& a uma variavel. Na continuacao do exemplo anterior, admita-se que

era realizada agora a seguinte sequencia de atribuicoes:

pd = &d; pi = &k;

Apos esta fase, o mapa de memoria seria o representado na figura 2.2, situacao B, onde as

variaveispd e pi surgem agora preenchidas com os enderecos ded e k . Como seria de es-

perar, a consistencia da atribuicao exige que a variavel referenciada e o tipo do apontador sejam

compatıveis. Por exemplo, a atribuicaopd=&k e incorrecta, atendendo a quek e do tipoint e

pd esta declarada como um apontador paradouble .

A partir do momento em que os apontadores sao inicializados, o seu conteudo pode ser

copiado e atribuıdo a outras variaveis, desde que os tipos ainda sejam compatıveis. Assim, as

atribuicoes

pd2 = pd; pi2 = pi;

conduziriam apenasa copia dos enderecos guardados empd e pi parapd2 e pi2 . Apos esta

sequencia, a situacao seria a representada na figura 2.2, caso C.

Uma vez estabelecido um mecanismo para preecher o conteudo de um apontador, coloca-se a

questao de como utilizar este apontador de modo a aceder aos dados apontados. Este mecanismoe

suportado no chamado sistema de enderecamento indirecto, o quale realizado em C pelo operador

* . Assim, a atribuicaoj = *pi; tem o significado “consultar o endereco guardado em pi (1006)

e, seguidamente, ler o inteiro cujo enderecoe 1006 e colocar o resultado (113) na variavelj . Deste

modo, apos as atribuicoes

j = *pi; d2 = *pd;

a situacao seria a representada na figura 2.2, caso D.

Referiu-se anteriomente que um apontadore apenas um endereco de memoria. Assim, podera

questionar-se a necessidade de distinguir um apontador para um inteiro de um apontador para um

3Embora possa ser pontualmente utilizada em programas que lidam directamente com ohardware.

10 APONTADORES

real, por exemplo. De facto, a dependencia do apontador do tipo apontado nao tem a ver com

a estrutura do apontador em si, mas sim com o facto de esta informacao ser indispensavel para

desreferenciar (aceder) correctamente o valor enderecado. Por exemplo, na expressaod2 = *pd ,

e o facto depd ser um apontador paradouble que permite ao compilador saber que o valor

referenciado ocupa nao apenas uma, mas duas palavras de memoria e qual a sua representacao. So

na posse desta informacaoe possıvel efectuar a atribuicao correcta ad2 .

Outras sequencias de atribuicao seriam possıveis. Por exemplo, apos a sequencia

pd2 = &d2; *pd2 = *pd1 / 10.0; pi2 = &i; m= *pi2 * 10;

a situacao seria a representada no caso E. Note-se que aqui o operador* foi utilizado no lado

esquerdo da atribuicao. Assim, por exemplo, a atribuicao *pd2 = *pd1 e interpretada como

ler o real cujo enderecoe especificado pelo conteudo depd1 e colocar o resultado no endereco

especificado porpd2 .

Embora ate aqui tenham sido considerados apontadores para tipos elementares, um apontador

pode tambem enderecar um outro apontador. Assim, na declaracao

int i1,i2,*pi1,**pi2,***pi3;int k1,k2,*pk1,**pk2;

enquanto quep1 e um apontador para um inteiro,p2 e um apontador para um apontador para um

inteiro ep3 e um apontador para um apontador para um apontador para um inteiro. Como seria de

esperar, a inicializacao destes apontadores realiza-se segundo as mesmas regras seguidas para os

apontadores simples, sendo apenas necessario ter em atencao, o nıvel correcto de enderecamento

indirecto multiplo. Assim, se apos a declaracao anterior, fosse executada a sequencia de instrucoes

i1 = 3; i2 = 4;pi1 = &i1; pi2 = &pi1; pi3 = &pi2;k1 = 10;pk1 = &k1; pk2 = pi2;k2 = i1 * ***pi3 + *pi1 + i2 + **pk2 * *pk1;

a situacao final poderia ser a representada na figura 2.2, caso F.

Em apontadores mutilpos a possibilidade de desreferenciar um apontador continua a ser de-

pendente do tipo apontado. Deste modo, um apontador para um inteiro e um apontador para um

apontador para um inteiro sao tipos claramente distintos e cujos conteudos nao podem ser mu-

tuamente trocados ou atribuıdos. Por outro lado, os nıveis de indireccao devem ser claramente

FUNCOES E PASSAGEM POR REFERENCIA 11

respeitados. Assim, a atribuicaoi1 = *pk2; no exemplo precedente seria incorrecta, ja quei1

e do tipo inteiro e,*pk2 e um apontador para inteiro (recorde-se que pk2e um apontador para um

apontador para um inteiro).

Comoe sabido, o valor de uma variavel nunca deve ser utilizado antes de esta ser inicializada

explicitamente pelo programa. Com efeito, no inıcio de um programa, as variaveis tem um valor

arbitrario desconhecido. Por maioria de razao, o mesmo princıpio deve ser escrupulosamente

seguido na manipulacao de apontadores. Suponha-se, por exemplo que, no inıcio de um programa,

sao incluıdas a declaracao e as instrucoes seguintes:

int *p,k;k = 4; *p = k*2;

Aqui, a segunda atribuicao especifica que o dobro dek (valor 8) deve ser colocado no endereco

especificado pelo conteudo da variavel p. No entanto, dado quep nao foi inicializada, o seu

conteudo e arbitrario. Com elevada probabilidade, o seu valor corresponde a um endereco de

memoria inexistente ou invalido. No entanto, o C nao realiza qualquer juızo de valor sobre esta

situacao e, tendo sido instruıdo para “colocar 8 no endereco indicado por p” tentara executar esta

operacao. A tentativa de escrita numa posicao de memoria invalida ou protegida conduzira ou ao

compromisso da integridade do sistema operativo se o espaco de memoria nao for conveniente-

mente protegido, comoe o caso do DOS. Se o sistema tiver um modo protegido, como o Unix ou o

Windows NT, esta situacao pode originar um erro de execucao, devido a uma violacao de memoria

detectada pelo sistema operativo. Os erros de execucao conduzema interrupcao imediata, em erro,

do programa.

Sublinhe-se que nas figuras desta seccao foram utilizados enderecos especıficos nos aponta-

dores de modo a melhor demonstrar e explicar o mecanismo de funcionamento dos mecanismos de

apontadores e indireccao em C. No entanto, na pratica, o programador nao necessita de conhecer o

valor absoluto dos apontadores, sendo suficiente a manipulacao indirecta do seu conteudo atraves

dos mecanismos de referenciacao e desreferenciacao descritos.

2.4 Func oes e passagem por refer encia

2.4.1 Passagem por refer encia

Em C, na chamada de uma funcao, os parametros formais da funcao recebem sempre uma

copia dos valores dos parametros actuais. Este mecanismo de passagem de argumentose desig-

12 APONTADORES

nadopassagem por valor(Martins, 1989) e esta subjacente a todas as chamadas de funcoes em

C. Esta situacaoe adequada se se pretender apenas que os argumentos transmitam informacao do

modulo que chama para dentro da funcao. Dado que uma funcao pode tambem retornar um valor,

este mecanismo basicoe tambem adequado quando a funcao recebe varios valores de entrada e

tem apenas um valor de saıda. Por exemplo, uma funcao que determina o maior de tres inteiros

pode ser escrita como

int maior_3(int i1,int i2, int i3){/*

* Func ao que determina o maior de tr es inteiros**/

if((i1 > i2) && (i1 > i3))return i1;

elsereturn (i2 > i3 ? i2 : i3);

}

Existem no entanto situacoes em que se pretende que uma funcao devolva mais do que um

valor. Uma situacao possıvel seria uma variante da funcao maior_3 em que se pretendesse

determinar os dois maiores valores, e nao apenas o maior. Outro caso tıpico e o de uma funcao

para trocar o valor de duas variaveis entre si. Numa primeira tentativa, poderia haver a tentacao de

escrever esta funcao 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 n umeros: ");scanf("%d %d",&a,&b);trocaMal(&a,&b);printf("a = %d, b= %d\n",a,b);


exit(0);}

No entanto, este programa nao funciona: o mecanismo de passagem por valor implica que a

funcaotroca opera correctamente sobre as variaveis locaisx ey , trocando o seu valor, mas estas

variaveis nao sao mais do que copias das variaveisa e b que, como tal, se mantem inalteradas.

Na figura 2.3 representa-se a evolucao do mapa de memoria e do conteudo das variaveis durante a

chamadaa funcaotrocaMal .

Este aparente problema pode ser resolvido pela utilizacao criteriosa de apontadores. A funcao

troca especificada anteriormente pode ser correctamente escrita como se segue:

#include <stdio.h>#include <stdlib.h>void troca(int *x,int *y){

/** Func ao que troca dois argumentos*/

int aux;aux = *x;*x = *y;*y = aux;

}int main(){

int a,b;

printf("Indique dois n umeros: ");scanf("%d %d",&a,&b);troca(&a,&b);printf("a = %d, b= %d\n",a,b);

exit(0);}

Tal como pode ser observado, a solucao adoptada consiste em passara funcao nao o valor das

variaveisa eb, mas sim os seus enderecos. Embora estes enderecos sejam passados por valor (ou

seja, a funcao recebe uma copia destes valores), o endereco permitea funcao o conhecimento da

posicao das variaveisa b em memoria e, deste modo, permite a manipulacao do seu conteudo por

meio de um enderecamento indirecto.

Um hipotetico exemplo de um mapa memoria associado ao funcionamento do programa

troca encontra-se representado na figura 2.4. Admita-se que a declaracao de variaveis no pro-

14 APONTADORES


.........

...... ...

... ... ...

Variáveis

main()do bloco

...... ...

a8

b2

2135

2136

A


.........

...... ...

... ... ...

...... ...

Variáveis

main()do bloco

Variáveis

troca()da funçao

a8

b2

2135

x

y

aux

2136

2133

2132

2131 8

2

B


.........

...... ...

... ... ...

...... ...

Variáveis

main()do bloco

Variáveis

troca()da funçao

a

b

2135

x

y

aux

2136

2133

2132

2131

8

8

2 8

2

8

2

C


.........

...... ...

... ... ...

Variáveis

main()do bloco

...... ...

a8

b2

2135

2136

D

Figura 2.3: Mapa de memoria durante as diferentes fase de execucao de um programa que utiliza

a funcao trocaMal . A - antes da chamadaa funcao, B - no inıcio de troca , C - no final de

troca , D - apos o regresso ao programa principal. O mecanismo de passagem por valor conduz

a que os valores do programa principal nao sejam alterados.



.........

...... ...

... ... ...

Variáveis

main()do bloco

...... ...

a8

b2

2135

2136

A


.........

...... ...

... ... ...

...... ...

Variáveis

main()do bloco

Variáveis

troca()da funçao

a8

b2

2135

x

y

aux

2136

2133

2132

2131 2135

2136

B


.........

...... ...

... ... ...

...... ...

Variáveis

main()do bloco

Variáveis

troca()da funçao

a

b

2135

x

y

aux

2136

2133

2132

2131 2135

2136

8

8

2 8

2

C


.........

...... ...

... ... ...

Variáveis

main()do bloco

...... ...

a

b

2135

2136

2

3

D

Figura 2.4: Mapa de memoria durante as diferentes fase de execucao do programa que utiliza a

funcaotroca . A - antes da chamadaa funcao, B - no inıcio detroca C - no final detroca , D -

apos o regresso ao programa principal. A passagem de apontadores para as variaveis do programa

principal (passagem por referencia) permite que a funcao altere as variaveis do programa principal.

16 APONTADORES

grama principal atribuiuas variaveis A e B os enderecos 2135 e 2136, e que estas foram inicial-

izadas pelo utilizador com os valores 8 e 2, respectivamente. A situacao imediatamente antes da

chamada da funcaotroca encontra-se representada em A. Durante a chamada da funcao, realiza-

se a activacao das variaveisx , y e aux , locaisa funcao, eventualmente numa zona de memoria

afastada daquela onde se encontram as variaveisa e b, sendo as duas primeiras destas variaveis

inicializadas com os enderecos dea eb (situacao B). Atraves do enderecamento indirecto atraves

das variaveisx ey , sao alterados os valores das variaveisa eb do programa principal, atingido-se

a situacao C. Apos o regresso ao programa principal, as variaveis da funcao troca sao libertadas,

atingindo-se a situacao representada em D, com as

Note-se que, estritamente falando, a passagem de argumento se deu por valor, atendendo a que

x ey sao variaveis locaisa funcao, tendo recebido apenas valores correspondentes ao endereco de

variaveis declaradas no programa principal. No entanto, neste tipo de mecanismo, diz-se tambem

que as variaveisa e b foram passadaspor referencia(Martins, 1989), atendendo a que o seu

endereco (e nao o seu conteudo) que foi passadasa funcao.

Mais genericamente, sempre quee necessario que uma funcao altere o valor de um ou mais

dos seus argumentos, este ou estes deverao ser passados por referencia, de forma a ser possıvel a

funcao modificar o valor das variaveis por um mecanismo de indireccao. E por este motivo que,

na chamada da funcaoscanf() , todas variaveis a ler sao passados por referencia, de modo a ser

possıvel a esta funcao poder ler e alterar os valores das variaveis do programa principal.

2.4.2 Erros frequentes

A tentativa de desdobramento do mecanismo de referenciacao de uma variavel quando uma

dado programa envolve varios nıveis de funcoese um erro frequente de programadores principi-

antes ou com reduzida experiencia de C. Considere-se o seguinte troco de programa, em que se

pretende que a variavelx do programa principal seja modificada na funcao func2 . Neste exem-

plo, o programador adoptou desnecessariamente uma referenciacao (calculo do seu endereco) da

variavel a modificar em cada um dos nıveis de chamada da funcao:

/*Utilizac ao incorrecta (desnecess aria)de refer encias m ultiplas.

*/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;

}

Como pode ser facilmente entendido, a referenciacao de uma variavel umaunica veze suficiente

para que este mesmo endereco possa ser sucessivamente passado entre os varios nıveis de funcoes

e ainda permitir a alteracao da variavel seja sempre possıvel. Assim, embora o programa anterior

funcione, a referenciacao de p1 na passagem defunc1 parafunc2 e inutil: o mecanismo ali

adoptado so faria sentido caso se pretendesse quefunc2 alterasse o conteudo da variavel p1 .

Comoe evidente naoe esse o caso, e o programa anterior correctamente escrito tomaria a seguinte

forma:

/*Utilizac ao correcta de uma passagempor refer encia entre v arios n ıveisde func oes.

*/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 principiantese passagem ao programa principal

ou funcao que chama a referencia de uma variavel locala funcao 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 APONTADORES

}

int main(){int x,*y;y = func1(1);x = 2 * *y;return 0;

}

Aqui, a variavel b e local a funcao func e, como tal,e criada quandofunc e activada e a

sua zona de memoria libertada quando a funcao termina. Ora o resultado da funcao func e

passada ao programa principal sob a forma do endereco deb. Quando o valor desta variavel e

lido no programa principal por meio de um enderecamento indirecto na expressaox = 2 * *y ,

a variavel b ja nao esta activa, realizando-se por isso um acesso invalido a posicao de memoria

especificada pelo endereco emy . Com elevada probabilidade, o resultado final daquela expressao

sera incorrecto.

2.5 Vectores e apontadores

2.5.1 Declarac ao de vectores

Um vector em C permite a criacao de uma estrutura com ocorrencias multiplas de uma variavel

de um mesmo tipo. Assim, a declaracao

int x[5] = {123,234,345,456,567};double y[3] = {200.0,200.1,200.2};

declara um vectorx de 5 inteiros, indexado entre 0 e 4, e um vectory de 3 reais de dupla pre-

cisao, indexado entre 0 e 2, inicializados na propria declaracao. Um possıvel mapa de memoria

correspondente a esta declaracao encontra-se representado na figura 2.5.1.

Cada elemento individual de um vector pode ser referenciado acrescentandoa frente do nome

da variavel o ındice, ou posicao que se pretende aceder, representado por um inteiro entre[] .

Para um vector comN posicoes, oındice de acesso varia entre 0 (primeira posicao) eN − 1(ultima posicao). Cada elemento dex e y corresponde a uma variavel de tipo inteiro ou double,

respectivamente. Deste modo, se se escrever,

int x[5] = {123,234,345,456,567};

VECTORES E APONTADORES 19

.........

......

1001

1002

1003

1004

1005

1006

1007

1008

1009

Endereço

1010

1011

Conteúdo Variável

x[0]

x[1]

x[2]

x[3]

x[4]

y[0]

y[1]

y[2]

123

234

345

456

789

200.0

200.1

200.2

Figura 2.5: Mapa de memoria correspondentea declaracao de dois vectores

20 APONTADORES

double y[3] = {200.0,200.1,200.2};double a;

a = y[1] + x[3];

o conteudo final dea sera o resultado da soma da segunda posicao dey com a quarta posicao de

x , ou seja 656.1.

Dado que cada elemento de um vectore uma variavel simples,e possıvel determinar o seu

endereco. 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 assima situacao representada na figura 2.5.1. Note-se que nas atribuicoes

pi = &(x[2]) e pd = &(y[1]) os parenteses poderiam ser omitidos, dado que o oper-

ador[] (ındice) tem precedencia sobre o operador& (endereco de). Assim, aquelas atribuicoes

poderiam ser escritas comopi = &x[2] epd = &y[1] .

Uma das vantagens da utilizacao de vectorese o ındice de acesso poder ser uma variavel.

Deste modo, inicializacao de um vector de 10 inteiros a 0 pode ser feita pela sequencia

#define NMAX 10int main(){

int x[NMAX];int k;

for(k = 0; k < NMAX ; k++)x[k] = 0;

/* ...*/

Uma utilizacao comum dos vectorese a utilizacao de vectores de caracteres para guardar

texto. Por exemplo a declaracao

char texto[18]="Duas palavras";


.........

......

1001

1002

1003

1004

1005

1006

1007

1008

1009

Endereço

1010

1011

Conteúdo Variável

x[0]

x[1]

x[2]

x[3]

x[4]

y[0]

y[1]

y[2]

123

234

345

456

789

200.0

200.1

200.2

1012

1013

pi

pd

1003

1008

Figura 2.6: Apontadores e vectores (explicacao no texto).

22 APONTADORES

’u’ ’a’ ’s’ ’ ’ ’p’’a’ ’l’’a’ ’v’ ’r’ ’a’ ’s’’\0’’D’

0 1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17

texto[18]

Figura 2.7: Utilizacao de vectores de caracteres para armazenar texto.

cria um vector de 18 caracteres, e inicia as suas primeiras posicoes com o textoDuas palavras.

Uma representacao grafica deste vector depois de inicializadoe apresentada na figura 2.7.

Dado que o texto pode ocupar menos espaco que a totalidade do vector, como sucede neste

caso, aultima posicao ocupada deste vectore assinalada pela colocacao na posicao seguinte

a ultima do caracter com o codigo ASCII 0, geralmente representado pela constante inteira 0

ou pelo caracter’\0’ . Note-se que estaultima representacao nao deve ser confundida com a

representacao do algarismo zero’0’ , internamente representado por 48, o codigo ASCII de 0.

2.5.2 Aritm etica de apontadores

E possıvel adicionar ou subtrair uma constante inteira de uma variavel de tipo apontador. Este

tipo de operacao so faz sentido em vectores ou estruturas de dados regulares, em que o avanco ou

recuo de um apontador conduz a um outro elemento do vector (ou estrutura de dados regulares).

E daunica e exclusiva responsabilidade do programador garantir que tais operacoes aritmeticas

se mantem dentro dos enderecos validos da estrutura de dados apontada. Assim, por exemplo, se

na sequencia do exemplo e da situacao representada na figura 2.5.1 (repetida por conveniencia na

figura 2.5.2, A) fossem executadas as instrucoes

pi = pi + 2;pd = pd - 1;

a situacao resultante seria a representada na figura 2.5.2, B.

No caso do modelo de memoria adoptado como exemplo, a operacao aritmetica sobre o apon-

tador inteiro tem uma correspondencia directa com a operacao realizada sobre o endereco. No

entanto, o mesmo nao sucede com o apontador paradouble , onde subtraccao de uma unidade

ao apontador corresponde na realidade a uma reducao de duas unidades no endereco fısico da

memoria.

De facto, a aritmetica de apontadores em Ce realizada de forma a que o incremento ou decre-

mento unitario corresponda a um avanco ou recuo de uma unidade num vector, independentemente

do tipo dos elementos do vector. O compilador de C garante o escalamento da constante adicionada


.........

......

1001

1002

1003

1004

1005

1006

1007

1008

1009

Endereço

1010

1011

Conteúdo Variável

x[0]

x[1]

x[2]

x[3]

x[4]

y[0]

y[1]

y[2]

123

234

345

456

789

200.0

200.1

200.2

1012

1013

pi

pd

1003

1008

A

.........

......

1001

1002

1003

1004

1005

1006

1007

1008

1009

Endereço

1010

1011

Conteúdo Variável

x[0]

x[1]

x[2]

x[3]

x[4]

y[0]

y[1]

y[2]

123

234

345

456

789

200.0

200.1

200.2

1012

1013

pi

pd

1005

1006

B

Figura 2.8: Aritmetica de apontadores (explicacao no texto).

24 APONTADORES

ou subtraıda de acordo com a dimensao do tipo apontado. Este modo de operacao garante que,

na pratica, o programador possa realizar operacoes sobre apontadores abstraindo-se do numero

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 enderecamento indirecto, qual o tipo da variavel referenciada.

A aritmetica de apontadores reforca esta necessidade, dado que o seu incremento ou decremento

exige o conhecimento da dimensao do objecto apontado.

A aritmetica de apontadores define apenas operacoes relativas de enderecos. Assim, embora

seja possıvel adicionar ou subtrair constantes de apontadores, nao faz sentido somar apontadores.

Numa analogia simples, considere-se que os enderecos sao os numeros da porta dos edifıcios de

uma dada rua: faz sentido referir “dois numeros depois do predio 174” ou “tres numeros antes do

180”, mas nao existe nenuma aplicacao em que faca sentido adicionar dois numeros de porta (174

e 180, por exemplo). No entanto, faz sentido referir “o numero de predios entre o 174 e o 180”:

de modo equivalente, tambem em C a subtraccao de apontadorese possıvel, desde que sejam do

mesmo tipo. Comoe evidente, tal como na adicao, a subtraccao de operadorese convenientemenet

escalada pela dimensao 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 */

.

Umaultima nota relativamente aos apontadores de tipovoid . O C-ANSI permite a definicao

de apontadores genericos, cujo tipoe independente do objecto apontado. Um apontadorpv deste

tipo manipula um endereco generico e pode ser simplesmente declarado por

void *pv;

e encontra utilizacao em situacoes em que se pretende que uma mesma estrutura possa enderecar

entidades ou objectos de tipos diferentes. Sempre que possıvel, este tipo de situacoes deve ser

preferencialmente abordado pela utilizacao de estruturas do tipounion . No entanto, existem

casos em que tal naoe possıvel, obrigandoa utilizacao deste tipo de apontadores.E, por exemplo,

o caso das funcoes de gestao de memoria, que trabalham com apontadores genericos (V. seccao

3.3). Note-se, no entanto, que o C nao consegue desreferenciar automaticamente um apontador


paravoid (ou seja, aceder ao conteudo apontado por). De igual modo, o desconhecimento da

dimensao do objecto apontado impede que a aritmetica de apontadores seja aplicavel a apontadores

deste tipo.

2.5.3 Indices e apontadores

Dos princıpios gerais referidos anteriormente, resulta que atribuicao do 3o elemento de um

vectorx a uma variavela pode ser realizada directamente por

a = x[2];

ou, de forma equivalente, por

a = *(&x[0] + 2);

sendo o resultado identico. Enquanto que no primeiro caso se adopta um mecanismo de

indexacao directa, no segundo caso determina-se um apontador para o primeiro elemento do

vector, incrementa-se o apontador de duas unidades para enderecar o 3o elemento e, finalmente,

aplica-se o operador “*” para realizar o enderecamento indirecto.

De facto, a segunda expressao pode ser simplificada. O C define que o endereco do primeiro

elemento de um vector pode ser obtido usando simplesmente o nome do vector, sem o operador

de indexacao (“[0]”) a frente. Ou seja, no contexto de uma expressao em C, “&x[0] ” e equiv-

alente a usar simplesmente “x ”. Por outras palavras, sex[] e um vector do tipoxpto , x e um

apontador para o tipoxpto . Assim, a expressao “ x[k] ” e sempre equivalente a “*(x k)+”. Este

facto conduz ao que designamos porregra geral de indexacao em C, que pode ser enunciada pela

equivalencia

x[k] <-> *(x + k)

Registe-se, como curiosidade, que a regra geral de indexacao conduz a que, por exemplo,

x[3] seja equivalente a3[x] . Com efeito,

x[3] <-> *(x+3) <-> *(3+x) <-> 3[x]

Claro que a utilizacao desta propriedadee geralmente proibido, nao pelo C, mas pelas normas de

boa programacao!

26 APONTADORES

2.5.4 Vectores como argumentos de func oes

Para usar um vector como argumento de uma funcao func() basta, no bloco que chama

func() , especifiar o nome da variavel que se pretende como argumento. Assim, pode fazer-se,

por exemplo,

int x[10];

/* ... */

func(x);

/* ... */

No entanto,e necessario ter em conta quex , quando usado semındice, representa apenas o

endereco da primeira posicao do vector. Como deve entao ser declarado o argumento formal

correspondente no cabecalho defunc ?

Diversas opcoes existem para realizar esta declaracao. No exemplo seguinte, a funcaoset e

utilizada para inicializar os NMAX elementos do vectora do programa principal com os inteiros

entre 1 e NMAX. Numa primeira variante, o argumento formal da funcaoe apenas a repeticao da

declaracao efectuada no programa principal. Assim,

#define NMAX 100void 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 funcao manipular um vectore suficiente conhecer o endereco do

primeiro elemento. Dentro da funcao, o modo de aceder ao k-esimo elemento do vectore sempre

adicionark ao endereco da base, independentemente da dimensao do vector. Ou seja, o parametro

formal int x[NMAX] apenas indica quex e um apontador para o primeiro elemento de um vec-

tor de inteiros. Deste modo, o C nao usa a informacao “[NMAX]” no parametro formal para aceder

a funcao. Assim, a indicacao explıcita da dimensao pode ser omitida, sendo valido escrever

void set(int x[],int n){


int k;for(k = 0; k < n; k++) x[k] = k+1;

}

Note-se que a possibilidade de omitir a dimensao resulta tambem da funcao nao necessitar de

reservar o espaco para o vector: a funcao limita-se a referenciar as celulas de memoria reservadas

no programa principal.

Na passagem de vectores como argumento o C utiliza sempre o endereco da primeira posicao,

nao existindo nenhum mecanismo previsto que permita passar a totalidade dos elementos do vec-

tor por valor. Esta limitacao, inerentea propria origem do C, tinha por base a justificacao de

que a passagem por valor de estruturas de dados de dimensao elevadae pouco eficiente, dada a

necessidade de copiar todo o seu conteudo4.

Atendendo a quea, sem inclusao doındice, especifica um apontador para primeiro elemento

do vector, uma terceira forma de declarar o argumento formale

void set(int *x,int n){int k;for(k = 0; k < n; k++) x[k] = k+1;

}

Estaultima forma sugere uma forma alternativa de escrever o corpo da funcao set . Com

efeito, para percorrer um vector basta criar um apontador, inicializa-lo com o endereco da primeira

posicao do vector e seguidamente incrementa-lo sucessivamente para acederas posicoes seguintes.

Esta tecnica pode ser ilustrada escrevendo a funcao

void set(int *x,int n){int k;for(k = 0; k < n; k++) *x++ = k+1;

}

Note-se que sendox um ponteiro cujo valor resulta de uma passagem copia do endereco dea no

programa principal,e possıvel proceder ao seu incremento na funcao de modo a percorrer todos

os elementos do vector. Aqui, a expressao *x ++ merece um comentario adicional. Em primeiro

lugar, o operador ++ tem precedencia sobre o operador* e, deste modo, o incremento opera sobre

o endereco e nao sobre a posicao de memoria em si.E este apenas o significado da precedencia,

4Na versao original do C, esta limitacao estendia-se ao tratamento de estruturas de dados criadas com a directiva

struct , mas esta limitacao foi levantada pelo C-Ansi

28 APONTADORES

o qual nao deve ser confundido com a forma de funcionamento do operador incremento enquanto

sufixo: o sufixo estabelece apenas que o conteudo de xe utilizado antes da operacao de incremento

se realizar. Ou seja,*x +=k;+ e equivalente a*x=k;x +;+.

Um outro exemplo de utilizacao desta tecnica pode ser dado escrevendo uma funcao para

contabilizar o numero de caracteres usados de umastring. Atendendo a que se sabe que oultimo

caracter esta seguido do codigo ASCII 0, esta funcao pode escrever-se

int conta(char *s){int n = 0;while(*s++ != ’\0’) n++;return n;

}

De facto, esta funcaoe equivalentea funcaostrlen , disponıvel na bibliotecastring.h .

2.6 Matrizes

2.6.1 Declarac ao

Na sua forma mais simples, a utilizacao de estruturas multidimensionais em C apenas envolve

a declaracao de uma variavel com variosındices, especificando cada um da dimensao pretendida

da estrutura. Por exemplo

float x[3][2];

declara uma estrutura bidimensional de tres por dois reais, ocupando um total de seis palavras

de memoria no modelo de memoria que temos vindo a usar como referencia. E frequente uma

estrutura bidimensional ser interpretada como uma matriz, neste exemplo de tres linhas por duas

colunas.

Nos modos de utilizacao mais simples deste tipo de estruturas, o programadador pode abstrair-

se dos detalhes de implementacao e usar a variavel bidimensional como uma matriz. Assim, a

inicializacao a zeros da estruturax pode ser efectuada por

float x[3][2];int k,j;

MATRIZES 29

.........

......

1002

1003

1004

1005

1006


1.0

2.0

3.0

4.0

5.0

6.0

1001 x[0][0]

x[0][1]

x[1][0]

x[1][1]

x[2][0]

x[2][1]

Figura 2.9: Mapa de memoria correspondentea declaracao de uma estrutura de tres por dois reais

for(k = 0 ; k < 3 ; k++)for(j = 0 ; j < 2 ; j++)

x[k][j] = 0.0;

Alternativamente, a inicializacao pode ser feita listando os valores iniciais, sendo apenas

necessario agrupar hierarquicamente as constantes de inicializacao de acordo com as dimensoes

da estrutura:

float x[3][2] = {{1.0,2.0},{3.0,4.0},{5.0,6.0}};

A disposicao em memoria desta estruturae representada esquematicamente na figura 2.9.

2.6.2 Matrizes como argumento de func oes

O facto de ser possıvel omitir a dimensao de um vector na declaracao do parametro formal de

uma funcao leva por vezes a pensar que o mesmo pode ser feito no caso de uma matriz. De facto,

a situacao naoe totalmente equivalente.

Comece-se por regressara declaracao int x[3][2] e observar a forma comoe determi-

nado o endereco de x[k][j]. Analisando a figura 2.9,e evidente que o endereco deste elementoe

obtido adicionando ao endereco do primeiro elementok*2+j . Ou seja,

30 APONTADORES

x[k][j] <-> *(&(x[0][0]) + k * 2 +j)

No caso mais generico da declaracao 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 generico de uma matriz nao basta conhecer o endereco da

primeira posicao e o os doisındices de acesso:e necessario saber tambem o numero de colunas da

matriz. Deste modo, quando uma matrize passada como argumento de uma funcao,e necessario

que esta saiba a dimensao das colunas da matriz. Por este motivo, dada a chamadaa funcao

/* ... */#define NLIN 3#define NCOL 2

/* ... */int m[NLIN][NCOL];int a;/* ... */a = soma(m);/* ... */

o parametro formal da funcao pode repetir na totalidade a declaracao 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 numero de linhas (dado que, como se mostrou, este numero naoe indispensavel

para localizar o endereco de um elemento generico 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;}

MATRIZES 31

No entanto, a omissao simultanea 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;}

naoe possıvel, gerando um erro de compilacao.

Viu-se anteriormente que se o vectorint x[NMAX] for utilizado na chamada a uma funcao,

a declaracao a adoptar nos parametros formais da funcao podia ser ouint a[]) ou int *a .

E frequente surgir a duvida see possıvel adoptar uma notacao de apontador equivalente no caso

de uma matriz. De facto sim, embora esta notacao raramente seja utilizada na pratica. No caso do

exemplo que tem vindo a ser utilizado a declaracao 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 declaracao, x e um apontador para um vector deNCOL floats . Uma explicacao mais

detalhada do significado desta invulgar declaracao pode ser encontrado na seccao 2.6.4.

2.6.3 Matrizes e vectores

Em C, uma matriz nao e mais do que umvector de vectores. Ou seja, a declaracao

int x[3][2] pode ser interpretada como “x e um vector de 3 posicoes, em que cada posicaoe

um vector de 2 posicoes”. Esta interpretacaoe tambem sugerida pela representacao 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 pratica, este facto significa que cada uma das linhas de uma matriz pode ser tratada indi-

vidualmente como um vector.

32 APONTADORES

Suponha-se, por exemplo, que dada uma matriza de dimensaoNLIN × NCOL, se pretende

escrever uma funcao que determine o maximo de cada uma das linhas da matriz e coloque o

resultado num vectory . Esta funcao 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 maximo e determinado pela

funcao 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

ondeA e uma matriz de dimensaoN ×M ex ey sao vectores de dimensaoM eN , respectiva-

mente.

Admita-se que o programa principal era escrito como

#define N 3#define M 2int 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);

}

MATRIZES 33

Atendendo a que o produto de uma matriz por um vectore um vector em que cada elemento

nao e mais do que o produto interno de cada linha da matriz com o vector operando, a funcao

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 ultima situacao em quee possıvel exemplificar a utilizacao de linhas como vectorese

o do armazenamento de varias linhas de texto. Admita-se, por exemplo, que se pretende ler uma

sequencia de linhas de texto e imprimir as mesmas linhas por ordem inversas. Tale possıvel atraves

da utilizacao de uma matriz de caracteres, utilizando cada linha como umastringconvencional:

#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 sequ encia 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 APONTADORES

}}

/* 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 utilizacao de estruturas multidimensionaise relativamente simples e intuitiva, ja o mesmo

nem sempre sucede quandoe necessario manipular apontadores relacionados com este tipo.5 O

tratamento de matrizes no Ce frequentemente fonte de alvo de duvidas. Se se perguntar a qualquer

programador de C “dada a declaracaoint x[3] , quale o tipo dex quando usado isoladamente”,

nenhum tera duvidas em afirmar que a respostae “apontador paraint ”. Experimente-se, no

entanto, a colocar a pergunta semelhante “dada a declaracao int x[3][2] , quale o tipo dex

quando usado isoladamente” e, com elevada probabilidade, nao sera obtida a mesma unanimidade

nas respostas.

Dado que, por consistencia sintactica, se tem sempre

x[k] <-> *(x + k)

entao, no caso de uma estrutura bidimensional, tera que ser

x[k][j] <-> *(x[k] + j)

e, portanto, sex[k][j] e por exemplo do tipofloat , x[k] e um apontador parafloat . Con-

sultando novamente o exemplo da figura 2.9, significa isto quex[0] corresponde a um apontador

parafloat com o valor 1001 (e portanto o endereco do primeiro elemento do vector defloats

formado pelos reais 1.0 e 2.0, enquanto quex[2] corresponde tambem a um apontador, cujo

valor e 1003 (primeiro elemento do vector defloats formado pelos reais 3.0 e 4.0).

Considere-se agora, novamente, a questao de qual o tipo dex , quando considerado isolada-

mente. Como ja se disse anteriormente em C, uma estrutura multidimensional representa sempre

5A leitura desta seccao pode ser omitida numa abordagem introdutoria da linguagem C.

MATRIZES 35

uma hierarquia de vectores simples. Ou seja,x[3][2] representa um vector de tres elementos,

em que cada ume por sua vez um vector de dois elementos. Assim,x[k] representa sempre um

vector de doisfloats . Com esta formulacao, resulta claro quex representaum apontador para

um vector de dois floats. Isto naoe mais do que a generalizacao da situacao dos vectores, em que

dada a declaracao int a[N] , se sabe quea isoladamentee um apontador para inteiro.

Assim,e natural quex semındices especifique o endereco do primeiro elemento de um vector

de tres elementos, em que cada ume um vector de doisfloats . Ou seja, no nosso exemplo,x

corresponde ao valor 1001.

Mas, afinal, qual a diferenca entre um apontador parafloat e um apontador para um vec-

tor de floats ? Por um lado, a forma de usar este tipo variavel num enderecamento indirecto

e claramente diferente. Por exemplo,x e &x[0][0] correspondem ao mesmo valor (1001 no

nosso exemplo), mas sao tipos diferentes: o primeiroe um apontador para um vector, pelo que*x

e um vector (a primeira linha dex , enquanto que*(&x[0][0]) e um float (o conteudo de

x[0][0] . No entanto,e provavelmente mais importante reter que a diferenca fundamental reside

na dimensao do objecto apontado. Considere-se novamente o exemplo que temos vindo a con-

siderar. Uma variavel do tipo apontador parafloat , cujo valor seja 1001, quando incrementada

passa a ter o valor 1002. Mas uma variavel do tipo apontador para vector de doisfloat , cujo

valor seja 1001, quando incrementada passa a ter o valor 1003 (ja que o incrementoe escalado

pela dimensao do objecto apontado).

E interessante verificar que este modeloe ounico que permite manter a consistencia sintactica

do C na equivalencia entre vectores e apontadores. Ja se disse que sendo sempre

x[k] <-> *(x + k)

entao,

x[k][j] <-> *(x[k] + j)

O que nao se disse antes, mas que tambem se verifica,e que a primeira destas regras tambem deve

ser aplicavela entidadex[k] que surge naultima expressao. Ou seja, tem-se

x[k][j] <-> *(*(x+k) + j)

o que exige por outro lado estabelecer que

36 APONTADORES

Expressao Tipo Valor Elemento daestrutura

x Apontador para vector 1001 -de doisfloats

x+1 Apontador para vector 1003 -de doisfloats

*(x+1) Apontador parafloat 1003 -*(x+2)+1 Apontador parafloat 1006 -

*(*(x+2)+1) float 6.0 x[2][1]*x Apontador parafloat 1001 -**x float 1.0 x[0][0]

*(*x+1) float 2.0 x[0][1]x[1] Apontador parafloat 1003 -

Tabela 2.1: Exemplos de tipos e valores derivados do exemplo da figura 2.9.

• Sea e um apontador para um escalar,*a e desse tipo escalar, e o valor de*a e o conteudo

do endereco especificado pora.

• Sea 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 valore identico ao dea.

Um factor que contribui frequentemente para alguma confusao deriva do facto de que, ainda

quex nao seja sintacticamente um duplo apontador parafloat , sendo

x[0][0] <-> *(*(x+0) + 0) <-> **x

verifica-se que**x e umfloat .

A consistencia destas equivalencias podem ser verificada considerando casos particulares do

exemplo que tem vindo a ser utilizado como referencia, tal como listados na tabela 2.1. O codigo

de um pequeno programa que permite validar esta tabela esta listado no apendice A.

Comoe natural,e possıvel declarar um apontador para um vector de doisfloats , sem ser

da forma implıcita que resulta da declaracao da matriz. A declaracao de uma variavely deste tipo

pode ser feita por

float (*y)[2];

Por este motivo, que quando a matrizx e passada por argumento para uma funcao func , a

MATRIZES 37

declaracao do parametro formal poder ser feita repetindo a declaracao total, omitindo a dimensao

do ındice interior, ou entao por

void func(float (*y)[2]);

tal como se referiu na seccao 2.6.2.

Dado que este tipo de declaracoese alvo frequente de confusao,e conveniente saber que existe

uma regra de leitura que ajuda a clarificar a semantica da declaracao. Com efeito,e suficiente

“seguir” as regras de precedencia, procedendoa leitura na seguinte sequencia:

float (*y)[3]

um apontador

floats

y é

para um vector de três

Sublinhe-se que, face a tudo o que ficou dito anteriormente, naoe possıvel declarar um apon-

tador para um vector sem especificar a dimensao do vector: como ja foi dito por diversas vezes,

um apontador tem que conhecer a dimensao do objecto apontado. Isto naoe possıvel sem especi-

ficar a dimensao do vector. Como corolario, um apontador para um vector de tres inteirose de

tipo distinto de um apontador para um vector para seis inteiros, nao podendo os seus conteudos

ser mutuamente atribuıdos.

Note-se que a declaracao que se acabou de referire claramente distinta de

float *y[2];

onde, devidoa ausencia de parenteses,e necessario ter em atencao a precedencia de “[]” sobre o

“*”. Neste caso,y e um vector de dois apontadores parafloat , podendo a leitura da declaracao

ser realizada pela sequencia:

y éfloat *y[3]

um vector de três apontadores

para float

A utilizacao de vectores de apontadorese abordada em maior detalhe na seccao 3.5.4.

Finalmente, refira-se que os apontadores para vectores podem ainda surgir noutros contextos:

dada a declaracao int x[10] , x e um apontador para inteiro, mas a expressao &x e do tipo

38 APONTADORES

apontador para um vector de 10 inteiros.

2.7 Generalizac ao para mais do que duas dimens oes

A generalizacao do que ficou dito para mais do que duas dimensoese directa. Considere-se,

como referencia, a declaracao da estrutura

int x[M][N][L];

1. No calculo do endereco 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 repeticao

da declaracao completa do tipo. Assim, uma declaracao 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;

}

GENERALIZACAO PARA MAIS DO QUE DUAS DIMENSOES 39

Como se mostrou anteriormente, o calculo do endereco de um elemento generico de uma es-

trutura tridimensional exige o conhecimento das duas dimensoes exteriores da estrutura (N e L no

exemplo). A generalizacao desta regra mostra que para calcular o endereco de um elemento de

uma estruturan-dimensionale necessario conhecer com rigor osn − 1 ındices exteriores da es-

trutura. Deste modo, nos argumentos formais de uma funcaoe sempre possıvel omitir a dimensao

do primeiroındice de uma estrutura multidimensional, mas nao mais do que esse. No exemplo

anterior, pode entao escrever-se

void func(int x[][N][L]){/* ... */

}

Claro que todas as outras variantes em que exista consistencia sintactica entre os argumentos

formais e actuais do procedimento sao validas. Assim, pelas mesmas razoes ja detalhadas na

seccao 2.6.4,

void func(int (*x)[N][L]){/* ... */

}

e uma alternativa sintacticamente correcta neste caso.

Capıtulo 3

Vectores e mem oria din amica

3.1 Introduc ao

Ate ao aparecimento da linguagem C, a maioria das linguagens de alto nıvel exigia um dimen-

sionamento rıgido das variaveis envolvidas. Por outras palavras, a quantidade maxima de memoria

necessaria durante a execucao do programa deveria ser definida na altura de compilacao do pro-

grama. Sempre que os requisitos de memoria ultrapassavam o limite fixado durante a execucao

do programa, este deveria gerar um erro. A solucao nestes casos era recompilar o programa au-

mentando a dimensao das variaveis, solucao so possıvel se o utilizador tivesse acesso e dominasse

os detalhes do codigo fonte. Por exemplo, um programa destinadoa simulacao de um circuito

electronico poderia ser obrigado a definir no codigo fonte o numero maximo de componentes

do circuito. Caso este numero fosse ultrapassado, o programa deveria gerar um erro, porque a

memoria reservada durante a compilacao tinha sido ultrapassada. A alternativa nestas situacoes

era a reservaa partida de uma dimensao de memoria suficiente para acomodar circuitos de di-

mensao elevada, mas tal traduzia-se obviamente num consumo excessivo de memoria sempre que

o programa fosse utilizado para simular circuitos de dimensao reduzida. Em alguns casos, os pro-

gramas recorriama utilizacao de ficheiros para guardar informacao temporaria, mas esta solucao

implicava geralmente uma complexidade algorıtmica acrescida.

Tal como o nome indica, os sistemas de memoria dinamica permitem gerir de forma dinamica

os requisitos de memoria de um dado programa durante a sua execucao. Por exemplo, no caso

do sistema de simulacao referido anteriormente, o programa pode, no inıcio da execucao, deter-

minar a dimensao do circuito a simular e so nessa altura reservar a memoria necessaria. Com

esta metodologia, o programa pode minimizar a quantidade de memoria reservada e, deste modo,

permitir que o sistema operativo optimize a distribuicao de memoria pelos varios programas que

42 VECTORES E MEMORIA DINAMICA

se encontram simultaneamente em execucao. No entanto, ate ao aparecimento do C este tipo

de mecanismos, caso estivessem disponıveis no sistema operativo, eram apenas acessıveis em

linguagem maquina ouAssembler, mais uma vez pela necessidade de manipular directamente

enderecos de memoria.

Apesar da flexibilidade oferecida, a gestao directa da memoria dinamica exige algumas

precaucoes suplementares durante o desenvolvimento do codigo. Por este motivo, muitas lingua-

gens de programacao de alto-nıvel mais recentes (Lisp, Java, Scheme, Python, Perl, Mathematica,

entre outras) efectuam a gestao automatica da memoria dinamica, permitindo assim que o pro-

gramador se concentre na implementacao algorıtmica e nos modelos de dados associados, sem se

preocupar explicitamente com os problemas de dimensionamento de variaveis ou os volumes de

memoria necessarios para armazenamento de dados.

Neste contexto, podera perguntar-se quais as vantagens de programar em C ou porquee que

o C ainda mantem a popularidade em tantasareas de aplicacao. Ha diversas respostas para esta

questao:

• A gestao directa da memoria dinamica permite normalmente a construcao de programas

com maior eficiencia 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, micro-

controladores, etc) apenas disporem de compiladores para a linguagem C, a qual se encontra

mais proximo da linguagem maquina do que linguagens conceptualmente mais elaboradas.

Por este motivo, o C ainda se reveste hoje de uma importancia crucial em diversasareas da

Engenharia Electrotecnica, nomeadamente em aplicacoes que implicam o recurso a micro-

controladores especializados.

• Dada a sua proximidade com o hardware1, a maioria dos sistemas operativos actualmente

existentes sao ainda hoje programados na linguagem C.

• A maioria dos compiladores de linguagens de alto nıvel, incluindo o proprio C, sao actual-

mente escritos e desenvolvidos em C. Ou seja, nesta perspectiva, o Ce hoje uma linguagem

indispensavel a geracao da maioria das outras linguagens, constituindo, neste sentido, a

“linguagem das linguagens”.

1O C e frequentemente designado na gıria como umAssemblerde alto nıvel, apesar do evidente paradoxo contido

nesta designacao.

VECTORES 43

3.2 Vectores

Em C, um vectore uma coleccao com um numero bem definido de elementos do mesmo tipo.

Ao encontrar a declaracao de um vector num programa, o compilador reserva automaticamente

espaco em memoria para todos os seus elementos. Por razoes de clareza e de boa pratica de

programacao, estas constantes sao normalmente declaradas de forma simbolica atraves de uma

directivadefine , mas a dimensao continua obviamente a ser uma constante:

#define DIM_MAX 100#define DIM_MAX_STRING 200

int x[DIM_MAX];char s[DIM_MAX_STRING];

Por outras palavras, a necessidade de saberquantamemoria e necessaria para o vector que se

pretende utilizar implica que a dimensao deste vector seja uma constante, cujo valor ja conhecido

durante a compilacao do programa.

Comoe sabido, as variaveis locais a uma funcao tem um tempo de vida limitadoa execucao

da funcao2. O espaco para estas variaveise reservado na chamada zona da pilha (stack), uma

regiao de memoria dedicada pelo programa para armazenar variaveis locais e que normalmentee

ocupada por ordem inversa. Por outras palavras, sao usados primeiros os enderecos mais elevados

e vao sendo sucessivamente ocupados os enderecos inferioresa medida que sao reservadas mais

variaveis locais. Dada a forma como se realiza esta ocupacao de memoria, o limite inferior da

regiao da pilhae geralmente designada portopo da pilha. Neste sentido, quando uma funcao

e chamada, o espaco para as variaveis locaise reservado no topo da pilha, que assim decresce.

Quando uma funcao termina, todas as variaveis locais sao libertadas e o topo da pilha aumenta

novamente. Assim, por exemplo, dada a declaracao

int function(int z){

int a;

int x[5];

int b;

/* ... */

a chamada da funcao funcpoderia dar origem a uma evolucao do preenchimento da memoria da

forma como se representa na figura 3.1.

2Excepto se a sua declaracao for precedido do atributostatic , mas este so e usado em circunstancias excepcionais.


...

......

...

...1001

1002

1003

1004

1005

1006

1007

1008

1009


topo da pilha

A

...

......

...

...

x[0]

x[1]

x[2]

x[3]

1001

1002

1003

1004

1005

1006

1007

1008

1009


...

b

a

z

topo da pilha

B

Figura 3.1: Mapa de memoria antes e apos a chamadaa funcao func (A) e mapa de memoria

durante a execucao da funcao (B).

A necessidade da dimensao dos vectores ser conhecida na altura da compilacao conduza

impossibilidade de declaracoes do tipo

int function(int n){

int x[n]; /* MAL: n e uma vari avel, e o seu valor e desconhecido

na altura da compilac ao */

/* ... */

Comoe evidente, os elementos de um vector podem nao ser escalares simples como no ex-

emplo 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;

VECTORES 45

int main(){tipoAluno alunos[MAX_ALUNOS];/* ... */

ou mesmo outro vector. Com efeito, na declaracao

int mat[10][5]

a matrizmat , do ponto de vista interno do C, naoe mais do que um vector de 10 elementos, em

que cada elementoe por sua vez um vector de 5 inteiro (V. seccao 2.6.3).

A necessidade de definir de forma rıgida a dimensao dos vectores na altura da compilacao

obriga frequentemente ao estabelecimento de um compromisso entre a dimensao maxima e a

eficiencia do programa em termos da memoria utilizada. Uma solucao possıvel e utilizar um

majorante dos valores “tıpicos”. Considere-se novamente um sistema para simulacao de circuitos

electronicos. Se os sistemas que se pretende simular tem em media 1000 componentes, poder-

se-ia utilizar um valor de 2000 ou 5000 para dimensionar o vector de componentes. No entanto,

a utilizacao de um valor maximo elevado pode conduzir a situacoes frequentes de desperdıcio

de memoria, com o programa a reservara partida volumes de memoria muito superiores aos

necessarios, enquanto que um valor reduzido deste parametro pode limitar seriamente a dimensao

dos problemas a abordar. Por outro lado,e por vezes difıcil encontrar parametros razoaveis para

definir “valor medio”. Em determinadas aplicacoes, 50 componentes pode ser um valor razoavel,

noutras 10,000 pode ser um valor reduzido. Para agravar a situacao, a dimensao de memoria que

e razoavel reservara partida depende da memoria fısica disponıvel no sistema em que se esta a

trabalhar: sistemas com 8MB ou 8GB de memoria conduzem obviamente a situacoes distintas.

Nao se pretende com esta analise colocar de parte todas as utilizacoes de vectores conven-

cionais com dimensao fixa. Frequentemente, estae uma solucao mais que razoavel. Por exemplo,

uma linha de texto numa consola de texto tem em geral cerca de 80 caracteres, pelo que a definicao

de um valor maximo para o comprimento de uma linha de 160 ou 200 caracterese um valor que

pode ser razoavel e que nao e excessivo na maioria das aplicacoes. No entanto, em situacoes

em que o numero de elementos pode variar significativamente,e desejavel que a memoria seja

reservadaa medida das necessidades.


3.3 “Vectores” din amicos

Uma forma de ultrapassar a dificuldade criada pelo dimensionamento de vectorese a reserva

de blocos de memoria so ser realizada durante a execucao do programa. Considere-se novamente

o simulador de circuitos electronicos. A ideia essenciale iniciar o programa com um volume de

memoria mınimo, determinar qual o numero de componentes do sistema a simular e so depois

deste passo reservar espaco para manipular o numero de componentes pretendido.

Recorde-se que ao declarar um vector

int x[MAX_DIM]

a utilizacao do nome do vector sem especificar oındicee equivalente ao endereco doındice 0 do

vector. Por outras palavras, a utilizacao no programa dex e equivalente a&x[0] .Decorre tambem

daqui a regra geral de indexacao em C:

x[k] <-> *(x + k)

equivalencia quee universal em C.

A utilizacao de um bloco de memoria criado dinamicamente e que pode ser utilizado com

mecanismos de acesso identicos aos de um vector pode ser realizado declarando uma variavel

de tipo de apontador e solicitando ao sistema operativo a reserva de um bloco de memoria da

dimensao pretendida. O pedido de reserva de memoria ao sistema operativoe efectuado atraves

de um conjunto de funcoes declaradas no ficheirostdlib.h . Uma das funcoes utilizaveis para

este efeito tem como prototipo

void *calloc(size_t nmemb, size_t size);

A funcaocalloc reserva um bloco de memoria contıgua com espaco suficiente para armazenar

nmembelementos de dimensao size cada, devolvendo o endereco (apontador) para a primeira

posicao do bloco.size_t e o tipo utilizado para especificacao de dimensoes numericas em varias

funcoes do C e a sua implementacao pode ser dependente do sistema operativo, mas corresponde

geralmente a um inteiro sem sinal. O tipo de retorno,void* , corresponde a um endereco generico

de memoria. o que permite que a funcao seja utilizada independentemente do tipo especıfico do

apontador que se pretende inicializar. A funcao retorna um apontador para o primeiro endereco de

“V ECTORES” DINAMICOS 47

uma regiao de memoria livre da dimensao solicitada. Caso esta reserva nao seja possıvel, a funcao

retornaNULL, para indicar que a reserva nao foi efectuada.

Considere-se, como exemplo, um programa para calculo da media e variancia deN valores

reais indicados pelo programador. Em vez de utilizar um vector de dimensao fixa, e possıvel

utilizar apenas um apontador para um real e um programa com a seguinte estrutura:

/* Ficheiro: media.cConte udo: Programa para c alculo da m edia e vari aniciaAutor: Fernando M. Silva, IST ([email protected])Hist oria : 2001/06/01 - Criac ao

*/#include <stdio.h>#include <stdlib.h>

int main(){int n; /* N umero 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 mem oriapara um bloco de nreais */

if(f == NULL){ /* Teste da reserva de mem oria */fprintf(stderr,"Erro na reserva de mem oria\n");exit(1);

}/* A partir deste ponto, f pode ser tratado como um

vector de n posic oes */

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; /* c alculo da m edia */

soma = 0.0;


for( k = 0 ; k < n ; k++)soma += (f[k] - media) * (f[k] - media);

variancia = soma / n; /* c alculo da var. */

printf("M edia = %5.2f, var = %5.2f\n",media, variancia);

free(f);exit(0);

}

Na chamadaa funcaocalloc() , dois aspectos devem ser considerados. Em primeiro lugar o op-

eradorsizeof() e um operador intrınseco do C que devolve a dimensao (geralmente em bytes)

do tipo ou variavel indicado no argumento. Por outro lado,a esquerda da funcaocalloc() foi

acrescentada e expressao(float*) . Esta expressao funciona como um operador decast, obrig-

andoa conversao do apontador generico devolvido pela funcaocalloc para um apontador para

real. Em geral, na operacao decast e indicado o tipo do apontador que se encontra do lado es-

querdo da atribuicao. Embora estecastnao seja obrigatorio, e geralmente utilizado na linguagem

C como uma garantia adicional da consistencia das atribuicoes.

Apos a reserva dinamica de memoria, o apontadorf pode ser tratado como um vector con-

vencional. Comoe evidente, oındice nao deve ultrapassar a posicaon− 1, dado que para valores

superiores se estaria a aceder a posicoes de memoria invalidas.

Enquanto que as variaveis locais sao criadas na zona da pilha, toda a memoria reservada

dinamicamentee geralmente criada numa regiao independente de memoria designada porheap

(molhe). Admita-se, no caso do programa para calculo das medias e variancias, que o valor den

especificado pelo utilizador era4. Uma possıvel representacao do mapa de memoria antes e apos

a chamada da funcaocalloc encontra-se representado na figura 3.2.

3.4 Gest ao da mem oria din amica

3.4.1 Verificac ao da reserva de mem oria

Como ja se referiu, ao efectuar uma reserva dinamica de memoria e essencial testar se os re-

cursos solicitados foram ou nao disponibilizados pelo sistema. Com efeito, a reserva de memoria

pode ser mal sucedida por falta de recursos disponıveis no sistema. Este teste teste e deve ser sem-

pre efectuado testando o apontador devolvido pela funcao calloc() . Quando existe um erro,

a funcao devolve o endereco 0 de memoria, o quale representado simbolicamente pela constante

GESTAO DA MEM ORIA DINAMICA 49

...

......

...

...

...

......

...

...

topo


...

...

2101

2102

2103

2104

2105

2106

2107

2108

2109

1001

1002

1003

1004

1005

1006

1007

1008

1009


...

k

Zona da pilha (var. locais)

variancia

media

soma

f

...

n

heap

4

Zona do (var. dinamicas)

A

...

......

...

...

...

......

...

...

f[0]

f[1]

f[2]

f[3]

*f <−>

*(f+1) <−>

*(f+2) <−>

*(f+3) <−>


...

...

2101

2102

2103

2104

2105

2106

2107

2108

2109

1001

1002

1003

1004

1005

1006

1007

1008

1009


...

k


variancia

media

soma

f

...

n

heap

2102

4

Zona do (var. dinamicas)

topo

B

Figura 3.2: Mapa de memoria antes da reserva de memoria (A) e apos a reserva de memoria. (B).


NULL (definida emstdio.h ). Se o endereco devolvido tiver qualquer outro valor, a reserva de

memoria foi bem sucedida, e o programa pode continuar a sua execucao normal.

3.4.2 Outras func oes de gest ao de mem oria din amica

Func ao free()

Enquanto que a funcao calloc() efectua uma reserva dinamica de memoria, a funcao

free(p) liberta o bloco de memoria apontado porp. Como seria de esperar, esta funcao so

tem significado se o apontadorp foi obtido por uma funcao previa de reserva de memoria, como

a funcaocalloc() descrita anteriormente.

De um modo geral,e boa pratica de programacao libertar toda a memoria reservada pelo

programa sempre que esta deixa de ser necessaria. Isto sucede frequentemente pela necessidade

de libertar memoria que so foi necessaria temporariamente pelo programa.

Note-se que sempre que o programa termina toda a memoria reservadae automaticamente lib-

ertada. Deste modo, a libertacao explıcita da memoria reservada durante a execucao do programa

naoe estritamente obrigatoria antes de sair do programa atraves da funcaoexit() ou da direc-

tiva return no blocomain() . Apesar deste facto, alguns autores consideram que, por razoes

de consistencia e arrumacao do codigo, o programa deve procedera libertacao de toda a memoria

reservada antes de ser concluıdo. E este o procedimento adoptado no programa para calculo da

variancia, onde a funcaofree() e chamada antes do programa terminar.

Func ao malloc()

A funcaomalloc() tem por prototipo

void *malloc(size_t total_size);

ondetotal_size representa a dimensao total da memoria a reservar, expressa em bytes. A

funcaomalloc() e muito semelhantea funcaocalloc() A forma calloc(n,d) pode ser

simplesmente substituıda pormalloc(n*d) . A unica diferenca formal entre as duas funcoese

que enquanto a funcaocalloc() devolve um bloco de memoria inicializado com zero em todas

as posicoes, a funcaomalloc() nao efectua explicitamente esta inicializacao.


Func ao realloc()

A funcao realloc() pode ser utilizada sempre quee necessario modificar a dimensao de

um bloco de memoria dinamica reservado anteriormente. O prototipo da funcaoe

void *realloc(void *old_ptr,size_t total_new_size);

ondeold_ptr e o apontador para o bloco de memoria reservado anteriormente, enquanto que

total_new_size e a dimensao total que se pretende agora para o mesmo bloco. A funcao

retorna um apontador para o bloco de memoria redimensionado. Note-se que o segundo argumento

tem um significado semelhante ao da funcaomalloc .

Suponha-se, por exemplo, que no inıcio de um programa tinha sido reservado um bloco de

memoria para an inteiros:

int main(){

int *x,n;

/* Obtenc ao do valor de n ... */

x = (int*) calloc(n,sizeof(int));

mas que, mais tarde, se verificou a necessidade de acrescentar 1000 posicoes a este bloco de

memoria. Este resultado pode ser obtido fazendo

x = (int*) realloc(x,(n+1000)*sizeof(int));

O funcionamento exacto da funcao realloc() depende das disponibilidades de memoria

existentes. Suponha-se, para assentar ideias, que inicialmente se tinhan=2000 , e que o valor dex

resultante da funcaocalloc era 10000 (figura 3.3, A). Deste modo o bloco de memoria reservado

inicialmente estendia-se do endereco 10000 ao endereco 11999. Quando mais tardee chamada a

funcao realloc duas situacoes podem ocorrer. Se os enderecos de memoria entre 12000 e 12999

estiverem livres, o bloco de memoria e prolongado, sem mudanca de sıtio, pelo que o valor dex

permanece inalterado (figura 3.3, B). No entanto, se algum endereco entre 12000 e 12999 estiver

ocupado (figura 3.3, C),e necessario deslocar todo o bloco de memoria para uma nova regiao.

Neste caso, o novo bloco de memoria pode ser mapeado, por exemplo, entre os enderecos 12500

e 15499 (figura 3.3, D), retornando a funcao realloc o novo endereco da primeira posicao de

memoria (12500). Como complemento, a funcaorealloc trata de copiar automaticamente todo


o conteudo guardado nos enderecos 10000 a 11999 para os enderecos 12500 a 14499 e liberta as

posicoes de memoria iniciais.

3.4.3 Garbbage

Como referido anteriormente, o espaco de memoria para as variaveis locaise reservado na

zona de memoria da pilha quando uma funcao e chamada, sendo automaticamente libertado (e

com ele as variaveis locais) quando a funcao termina.

Ao contrario das variaveis locais, a memoria dinamicae criada e libertada sob controlo do

programa, atraves das chamadasas funcoescalloc() , malloc() e free() .

Em programas complexos,e frequente um programa reservar blocos de memoria que, por

erro do programador ou pela propria estrutura do programa, nao sao libertados mas para os quais

se perdem todos os apontadores disponıveis. Neste caso, o bloco de memoria dinamicae reser-

vado, mas deixa de ser acessıvel porque se perderam todos os apontadores que indicavam a sua

localizacao em memoria. Estes blocos de memoria reservados mas cuja localizacao se perdeu sao

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 ao de x, free()

nao 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 memoria ilustrativo desta situacao esta representado na figura 3.4.


...

...


...1001

1002

1003

1004

1005

1006

1007

1008

1009


...


...

heapZona do (var. dinamicas)

n

x

10000

10001

.......

...... ...... ......

10000

2000 −300

..

11999

12000

12001

12002

1765

12003

Memoria livre

666

A

...

11999

12000

1765

...

...


...1001

1002

1003

1004

1005

1006

1007

1008

1009


...


...


n

x

10000

10001

.........

...... ...... ......

10000

2000 −300

12999

666

B

...

...


...1001

1002

1003

1004

1005

1006

1007

1008

1009


...


...


n

x

10000

10001

.......

...... ...... ......

10000

2000 −300

..

11999

12000

12001

12002

1765

12003

−555555

11111111 Memoria ocupadapor outras var. dinamicas

666

C

...

libertadaMemoria

... .. .

−300

666

... .. .

11999

12000

12001

12002

1765

−555555

11111111

...

...


...1001

1002

1003

1004

1005

1006

1007

1008

1009


...


...


n

x

10000

10001

...

...... ...... ......

2000

666

−300

12500

12501

14599

"realocada"Memoria

12500

D

Figura 3.3: Mapa de memoria apos a chamadaa funcao calloc() (A) e apos a funcao

realloc() (B), se existir espaco disponıvel nos enderecos contıguos. Em (C) e (D) representa-

se a situacao correspondente no caso em que a memoria dinamica imediatamente a seguir ao bloco

reservado esta ocupada, sendo necessario deslocar todo o bloco para outra zona de memoria. Neste

caso, o apontador retornado pela funcaoe diferente do inicial.


...

......

...

...

...

......

...

...

topo

topo


...

...

2101

2102

2103

2104

2105

2106

2107

2108

2109

1001

1002

1003

1004

1005

1006

1007

1008

1009


...

Zona da pilha (var. locais) heapZona do (var. dinamicas)

b

a

A

...

......

...

...

...

......

...

...

topo

topo


...

...

2101

2102

2103

2104

2105

2106

2107

2108

2109

1001

1002

1003

1004

1005

1006

1007

1008

1009


...


b

a

y

x2102

x[0]

x[1]

x[2]

B

...

......

...

...

...

......

...

...

topotopo


...

...

2101

2102

2103

2104

2105

2106

2107

2108

2109

1001

1002

1003

1004

1005

1006

1007

1008

1009


...


b

a

x[0]

x[1]

x[2]

C

Figura 3.4: Criacao de “garbbage” (lixo). Mapa de memoria (exemplo do texto): (A) antes da

chamadaa funcao func , (B) no final da funcao func e (C) apos retorno ao programa princi-

pal. De notar que em (C) a memoria dinamica ficou reservada, mas que se perderam todas as

referencias que permitiam o acesso a esta zona de memoria.

CRIACAO DINAMICA DE MATRIZES 55

3.5 Criac ao din amica de matrizes

3.5.1 Introduc ao

A criacao e utilizacao de estruturas dinamicas em C que possam ter um acesso equivalente

a uma matrize simples. No entanto, a compreensao detalhada de como funcionam este tipo de

estruturas nem sempree claro.

De modo a simplificar a exposicao, comecar-se-a por apresentar na seccao 3.5.2 um resumo do

modo de declaracao e de acesso de matrizes estaticas. Seguidamente, na seccao 3.5.3, descreve-se

uma metodologia simples para criar dinamicamente vectores de apontadores com um comporta-

mento equivalente ao de uma matriz. Seguidamente, na seccao 3.5.4 serao discutidas as diferencas

e semelhancas entre matrizes e vectores de apontadores, de modo a evidenciar as diferencas entre

as estruturas dinamicas criadas e as matrizes nativas do C.

3.5.2 Matrizes est aticas

Conforme ja se viu na seccao 2.6.1, a utilizacao de estruturas multidimensionais em C ape-

nas exige a declaracao de uma variavel com variosındices, especificando cada um da dimensao

pretendida da estrutura. Por exemplo

float x[3][2];

declara uma estrutura bidimensional de dois por tres reais, ocupando um total de seis palavras

de memoria no modelo de memoria que temos vindo a assumir como referencia. E frequente

uma estrutura bidimensional ser interpretada como uma matriz, neste exemplo de duas linhas por

tres colunas. A inicializacao de uma matriz pode ser efectuada durante a execucao do programa

ou listando os valores iniciais, sendo apenas necessario fazer um agrupamento hierarquico das

constantes de inicializacao de acordo com as dimensoes da estrutura:

float x[3][2] = {{1.0,2.0},{3.0,4.0},{5.0,6.0}};

Como se mostrou anteriormente, a arrumacao em memoria desta estrutura encontra-se repre-

sentada esquematicamente na figura 2.9.


3.5.3 Matrizes din amicas

Admita-se que num dado programa se pretende substituir a sequencia

#define N ...

#define M ...

...

int x[N][M];

por uma estrutura dinamica com um mecanismo de acesso equivalente, mas em que os limitesn e

msao variaveis cujo valor so e conhecido durante a execucao do programa.

A solucao para este problemae substituir a estruturax por um vector dinamico de apontadores

para inteiros, em que cada posicaoe por sua vez inicializada com um vector dinamico. Considere-

se, por exemplo, que se pretende criar uma matriz den por m. O codigo para este efeitoe dado

por

int main{int k;int n,m;int **x;

/* Inicializac ao de n e m */

x = (int**) calloc(n,sizeof(int*));if(x == NULL){

printf("Erro na reserva de mem oria\n");exit(1);

}

for(k = 0; k < n ; k++){x[k] = (int*) calloc(m,sizeof(int));if(x == NULL){


}}

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 correspondea linha e a classe dos algarismosas unidades, poder-se-ia

fazer


int main{int k,j;int n,m;int **x;

n = 4; m = 3;

x = (int**) calloc(n,sizeof(int*));if(x == NULL){


}

for(k = 0; k < n ; k++){x[k] = (int*) calloc(m,sizeof(int));if(x == NULL){


}}

for(k = 0; k < n ; k++)for(j = 0; j < m ; j++)

x[k][j] = 10 * k + j;

O resultado da execucao deste bloco de codigo seria o que se mostra na figura 3.5.

Este exemplo indica que a solucao geral para simular a criacao dinamica de matrizese declarar

um duplo apontador para o tipo pretendido dos elementos da matriz e, seguidamente, reservar

dinamicamente um vector de apontadores e criar dinamicamente os vectores correspondentes a

cada linha.

Comoe evidente, neste exemplox e um duplo apontador para inteiro. Deste modo, se pre-

tender usar esta “matriz dinamica” como argumento de uma funcao fazer-se, no bloco que chama,

func(x,n,m,/* Outros argumentos */);

enquanto que o cabecalho defunc devera ser

void func(int **x,int n,int m,/* Outros argumentos */);


...... ...

x1543 2001

... ... ...

......

... ... ...

...

Endereço Conteúdo Variável Endereço Conteúdo VariávelEndereço Conteúdo Variável

Zona da pilha Zona do heap

2003

x[0]

x[1]

x[2]

x[3]

x[0][1]

x[0][0]

x[1][0]

x[1][1]

x[2][1]

x[2][0]

x[3][0]

x[3][1]

2001

2002

2004

2006

2007

2009

2010

2012

2013

2015

2016

2006

2009

2012

201511

0

1

10

20

21

30

31

Figura 3.5: Criacao dinamica de matrizes por meio de um vector de apontadores. Os enderecos

indicados sao apenas ilustrativos.

Esta solucao e tao frequente na pratica que, por analogia, muitos programadores (mesmo

experientes) de C pensam que, dada a declaracaotipo x[N][M] , x sem qualquerındice corre-

sponde a um duplo apontador paratipo . Como se mostrou na seccao 2.6.4, esta suposicao nao

correspondea realidade: nesta situacao,x e um apontador para um vector de elementos detipo .

3.5.4 Vectores de apontadores e matrizes

Considere-se a declaracao

int *x[4];

Recordando que os[] tem precedencia sobre o operador* , e seguindo a regra de interpretacao

semantica da declaracao apresentada na seccao 2.6.4, resulta quex e um vector de 4 apontadores

para inteiros. Ou seja, em termos de modelo de memoria, encontramos uma representacao como a

indicada na figura 3.6, situacao A. Um ponto importante a sublinhare que esta declaracao apenas

reserva memoria para quatro apontadores. Esta situacao e frequentemente mal interpretada pelo

facto de, sendox[k] uma apontador para um inteiro, entao*x[k] e *(x[k]+j) tambem sao

do tipo inteiro. Mas, devidoas equivalencias sintacticas de enderecamento em C, tem-se


...... ...

...... ...

1001

1002

1003

1004

Endereço

???

Conteúdo Variável

x[0]

x[1]

x[2]

x[3]

???

???

???

A

...... ...

...... ...

1001

1002

1003

1004

x[0]

x[1]

x[2]

x[3]

2001

2002

2005

2006

2010

2011

2013

2014

2001

2005

2010

2013

x[0][1]

x[0][0]

x[1][0]

x[1][1]

x[2][1]

x[2][0]

x[3][0]

x[3][1]

Endereço Conteúdo Variável Endereço Conteúdo Variável

1

2

3

4

5

6

7

8

B

Figura 3.6: Vectores de apontadores: A - Antes de inicializado, B- apos a inicializacao.


*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 dex tiverem sido convenientemente inicializados

de modo a enderecarem a base de um vector de inteiros. Isto, so por si, nao e realizado pela

declaracaoint *x[4] , que se limita a declarar um vector de apontadores e a reservar 4 palavras

de memoria para este efeito. Nesta declaracao, naoe reservada memoria para qualquer inteiro.

Claro que, se o utilizador o pretender,e facil inicializar as posicoes de memoria do vector

de apontadores reservando memoria dinamica de modo a armazenar os inteiros pretendido. Ad-

mitindo que se pretende que o vector de apontadores anteriores sirva de base a uma estrutura

de enderecamento equivalente a uma matriz de 4 por 2, esta inicializacao pode ser feita pela

sequencia

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, alem da reserva das posicoes de memoria para os vectores inteiros, se procedeua sua

inicializacao. A situacao final pode ser representada pelo modelo da figura 3.6, situacao B.

Em sıntese,e conveniente reter que, apesar da manipulacao de matrizes e de vectores de

apontadores seja sintacticamente semelhante, os mecanismos de reserva de memoria sao clara-

mente distintos. No caso da matrizint x[4][2] , a propria declaracao reserva automatica-

mente espaco para oito inteiros, os quais podem ser acedidos pelas regras habituais. No caso da

declaracao de um vector de apontadores, como por exemploint *x[4] , apenase efectuada a

reserva de quatro apontadores. A sua utilizacao requer a previa inicializacao de cada um dos seus

elementos com um endereco valido de um bloco de memoria, o qual pode ser obtido a partir de

um vector ja declarado ou, como no exemplo aqui usado, pela reserva de um bloco de memoria

dinamica atraves da funcaocalloc() .

Capıtulo 4

Listas din amicas

4.1 Introduc ao

Como se viu anteriormente, a utilizacao de vectores em C apresenta a desvantagem de exigir o

conhecimentoa partida da dimensao maxima do vector. Em muitas situacoes, a utilizacao devec-

tores dinamicos, como descrito na seccao 3.3,e uma solucao eficiente. No entanto, em situacoes

em que a quantidade de memoria dinamica necessaria varia frequentemente durante a execucao do

programa, a utilizacao de vectores dinamicos revela-se frequentemente pouco eficaz.

Considere-se, por exemplo, um gestor de uma central telefonica que necessita de reservar

dinamicamente memoria para cada chamada estabelecida (ondee armazenada toda a informacao

sobre a ligacao, como por exemplo os numeros de origem e destino, tempo de ligacao, etc,) e

libertar essa mesma memoria quando a chamadae terminada. Dado que o numero de ligacoes

activas varia frequentemente ao longo do dia, uma solucao baseada num vector dinamico exi-

giria o seu redimensionamento frequente. Em particular, sempre que nao fosse possıvel encontrar

memoria livre imediatamente a seguir ao fim do vector, seria necessario deslocar todo o vector (v.

funcao realloc , seccao 3.4.2) para uma nova zona de memoria, e a copia exaustiva de todo o

seu conteudo para a nova posicao de memoria. Este mecanismo, alem de pouco eficiente, poderia

inviabilizar o funcionamento em tempo real do sistema, dado que uma percentagem significativa

do tempo disponıvel seria dispendido na gestao da memoria usada pelo vector.

Quando se pretende armazenar entidades individuais de memoria que possam ser criadas e

libertadas individualmente com uma certa frequencia,e normalmente mais adequado utilizar es-

truturas de dados criadas dinamicas e organizadas emlistas.

62 LISTAS DINAMICAS

4.2 Abstracc ao de dados

Neste capıtulo descrevem-se listas dinamicas como uma forma de armazenar ou organizar

informacao. Esta organizacaoe, obviamente, independente do tipo de informacao que se pretende

armazenar. Esta situacao e semelhantea da construcao de um armario com gavetas: a estrutura

do movel e independente do conteudo que se ira arrumar nas gavetas. Esta independencia entre

movel e conteudo garante ageneralidadedo movel, no sentido em que este sera adaptavel a varias

situacoes.

De modo semelhante, ao desenhar um programae importante que as suas componentes sejam

o mais independentes possıveis, de forma a manterem a generalidade. Tanto quanto possıvel, e

desejavel que um bloco de codigo desenvolvido para o programa A seja reutilizavel no programa

B ou, pelo menos, que tal seja possıvel sem alteracoes ou com alteracoes mınimas.

Uma forma de atingir este objectivoe, ao desenhar o programa, adoptar uma metodologia

designada porabstraccao de dados(Martins, 1989). Esta metodologia baseia-se na definicao e

distincao clara dos varios tipos de dados utilizados pelo programa (ou, seguindo o exemplo ante-

rior, distinguir tanto quanto possıvel o movel do conteudo das gavetas). Segundo esta metodologia,

cada tipo de dados deve ter manipulado apenas por um conjunto de funcoes especıficas, designadas

metodos, conhecedoras dos detalhes internos do tipo de dados associado. Todos os outros blocos

do programa tem apenas que conhecer aspropriedades abstractasou genericas deste tipo. A

manipulacao do tipo so sao acessıveis de outros blocos de programa atraves dosmetodosdisponi-

bilizados pelo tipo de dados.

Esta metodologia de programacao garante que, caso seja necessario alterar os detalhes inter-

nos de um determinado tipo, apenase necessario alterar os metodos correspondentes a esse tipo.

Dado que todos os blocos de programas onde este tipo de dadose utilizado apenas acedem a ele

atraves dos metodos disponıveis, requerendo apenas o conhecimento das suas propriedades gerais

(ou abstractas), e possıvel minimizar ou eliminar totalmente as alteracoes necessarias aos out-

ros blocos de programa. Deste modo, a metodologia de abstraccao de dados contribui para uma

relativa estanquecidade e independencia dos diversos modulos constituintes.

Neste capıtulo, utilizar-se-a nos diversos exemplos uma metodologia estrita de abstraccao de

dados, chamando-se a atencao caso a caso para aspectos especıficos da implementacao.

L ISTAS 63

......

dados

(pos 1)

dados

(pos 2)

dados

(pos 3)

dados

(pos 4)

ConteúdoConteúdo


NULL

Variável


base

Figura 4.1: Lista dinamica. Todos os elementos sao criados dinamicamente na zona deheap,

sendo suficiente uma variavel local de tipo apontador (variavelbase, nas figura) para poder aceder

a todos os elementos da lista.

4.3 Listas

Uma lista dinamica naoe mais do que uma coleccao de estruturas de dados, criadas dinamica-

mente, em que cada elemento dispoe de um apontador para o elemento seguinte (figura 4.1). Cada

elemento da listae constituıdo por uma zona de armazenamento de dados e de um apontador para

o proximo elemento. Para ser possıvel identificar o fim da lista, no apontador doultimo elemento

e colocado o valorNULL.

Para criar uma listae necessario definir um tipo de dados e criar uma variavel local (normal-

mente designadabaseou raiz. Admita-se, por exemplo, que se pretendia que cada elemento da

lista guardasse uma string com um nome e um numero inteiro. A criacao de uma lista de elementos

deste tipo exigiria uma declaracao de tipos e de variaveis como se segue:

#define MAX_NOME 200

64 LISTAS DINAMICAS

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 definicao do apontador seguinte,e necessario utilizar a construcao

struct _tipoLista *seg e nao tipoLista *seg . De facto, apesar de serem duas for-

mas aparentemente semelhantes, a forma

typedef struct _tipoLista{tipoDados dados;tipoLista *seg; /* DECLARAC AO INVALIDA */

} tipoLista;

e invalida porquetipoLista so e conhecido no final da declaracao, e nao pode ser utilizado

antes de completamente especificado.

Uma das vantagens deste tipo de estruturase que cada um dos seus elementos pode ser reser-

vado e libertado individualmente, sem afectar os restantes elementos (exigindo apenas ajustar um

ou dois apontadores, de forma a garantir a consistencia do conjunto). Adicionalmente, a ordem

dos elementos da listae apenas definida pela organizacao dos apontadores. Deste modo, se for

necessario introduzir um elemento entre dois ja existentes, naoe necessario deslocar todos os el-

ementos de uma posicao, como sucederia num vector. Basta de facto reservar espaco para um

elemento adicional e deslocar todos os outros elementos de uma posicao. Na figura 4.2 apresenta-

se um exemplo em que se ilustra esta independencia entre enderecos de memoria e sequencia da

lista, e confere a esta uma flexibilidade superiora de um vector.

Dada esta independencia entre enderecos de memoria e sequencia, e frequente adoptar-se

representacoes graficas simplificadas para as listas, como a se mostra na figura 4.3. A cruz no

ultimo elemento corresponde a uma representacao simbolica abreviada para o valorNULL.

L ISTAS 65

......

dados

(pos 1)

dados

(pos 2)

dados

(pos 3)

dados

(pos 4)

ConteúdoConteúdo


Variável


base

NULL

Figura 4.2: Lista dinamica. A sequencia dos elementos da listae apenas definida pelos apontadores

de cada elemento, independentemente do endereco de memoria ocupado.

base

Figura 4.3: Lista dinamica. Representacao simplificada

66 LISTAS DINAMICAS

Apesar das vantagens ja referidas de uma lista,e necessario ter em atencao que o programa so

dispoe de uma variavel para aceder a toda a lista, e que esta tem que ser percorrida elemento a ele-

mento ate se atingir a posicao pretendida. Num vector, dado que todos as posicoes sao adjacentes,

para aceder a qualquer posicao basta saber o endereco do primeiro elemento e o numero de ordem

(ındice) do elemento que se pretende aceder para ser possıvel calcular o endereco do elemento que

se pretende. Ou seja, a flexibilidade acrescida da lista em termos de organizacao de memoria e

conseguidaa custa do tempo de acesso aos seus elementos.

4.4 Listas din amicas: listar elementos

Uma operacao 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 conteudo de todos os numeros e nomes da lista do exemplo da

seccao 4.3. Uma solucao para este efeito seria a sequencia de codigo 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 n ao se atingir o final... */

escreveDados(aux -> dados); /* Escreve o conte udo */aux = aux -> seg; /* Avanca para a pr oxima posic ao */

}}int main(){

L ISTAS DINAMICAS : LISTAR ELEMENTOS 67

tipoLista *base;

/* Neste ponto, o apontador base e os restanteselementos da lista s ao, de alguma forma,inicializados */

/* Listagem do conte Udo */

lista(base);

O princıpio essencial da operacao de listagem esta incluıda na funcao lista e e muito sim-

ples. Inicializa-se um apontadoraux para o inıcio da lista. Seguidamente, enquanto este apon-

tador for diferente deNULL (ou seja, nao atingir o fim da lista), o apontadore sucessivamente

avancado para o elemento seguinte.

Note-se como se adoptou neste bloco de codigo a metodologia de abstraccao de dados. Ex-

iste neste exemplo uma separacao funcional de tarefas entre as diversas entidades que partici-

pam o programa. A funcao lista manipula unicamente a estrutura de dados que suporta a

lista, percorrendo todos os seus elementos ate ao fim da lista. No entanto, quandoe necessario

escrevero conteudo de cada no no terminal, esta tarefae delegada a uma funcao especıfica (

escreveDados ), responsavel pela manipulacao e processamento dos detalhes especıficos de

variaveis do tipotipoDados . Neste sentido,tipoDados e, para a lista, um tipo abstracto

generico, cuja representacao interna ela desconhece, e da qual so tem que conhecer uma pro-

priedade muito generica: uma variavel deste tipo pode de alguma forma ser escrita no terminal,

havendo um metodo competente para o fazer.

Uma forma alternativa da funcao listar frequentemente utilizada passa pela utilizacao de um

ciclo for em vez do ciclowhile :

void lista(tipoLista *base){tipoLista *aux; /* Apont. que percorre */

/* a lista. */for(aux = base ; aux != NULL; aux = aux -> seg)

escreveDados(aux -> dados);}

68 LISTAS DINAMICAS

4.5 Listas: pilhas

4.5.1 Introduc ao

As listas tem habitualmente uma estrutura e organizacao em memoria semelhantea apresen-

tada na figura 4.1. No entanto, os mecanismos de acessoa lista sao variaveis e, no seu conjunto,

podem permitir que a lista realize apenas um subconjunto de tarefas bem determinadas.

Em teoria da computacao, umapilha (ou stack, na lietratura anglo-saxonica) e um sistema

que armazena dados de forma sequencial e que permite a sua leitura por ordem inversa da escrita.

A designacao pilha vem da semelhanca funcional com uma pilha comum. Admita-se que se

dispoe de um conjunto de palavras que se pretende armazenar. Considere-se ainda que o sistema

dearmazenamentodisponıvel e um conjunto de pratos, sendo cada palavra manuscrita no fundo

do prato. A medida que as palavras vao sendo comunicadas ao sistema de armazenamento, sao

escritas no fundo de um prato e estee colocado numa pilha. A leitura posterior das palavras

registadase feita desempilhando pratos sucessivamente e lendo o valor registado em cada um.

Comoe obvio, a leitura ocorre por ordem inversa da escrita.

Uma pilhae frequentemente designada por uma estrutura LIFO, acronimo derivado da ex-

pressao Last In First Out. A operacao de armazenamento na pilhae geralmente designada de

operacao depush, enquanto que a leiturae designada depop.

As pilhas tem uma utilizacao frequente em informatica sempre que se pretende inverter uma

sequencia de dados. Embora a relacao nao sejaobvia, pode indicar-se, por exemplo, que o calculo

de uma expressao aritmetica em que varios operadores tem nıveis de precedencia diferentese

realizada acumulando numa pilha resultados intermedios.

Considere-se, por exemplo, que se pretende inverter os caracteres da palavraLuı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 atraves de uma lista dinamica ligada. A colocacao 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 operacao de remocao e leitura corresponde a retirar o

elemento da base, ficando esta a apontar para o elemento seguinte (v. figura 4.5)

L ISTAS: PILHAS 69

L

u

L L

u

L

(remoção)

s u Lu s

(sobreposição)Entrada (push) Saida (pop)

L íí

L

u

s

L

u

L

u

s

L

u

í í í í

Figura 4.4: Inversao de uma sequencia de caracteres por meio de uma pilha.

base ’L’’u’

’í’

Figura 4.5: Realizacao de uma pilha por uma lista ligada. No exemplo, considera-se uma pilha de

caracteres e a insercao do caracter ’ı’ no topo da pilha. A tracejado indica-se a ligacao existente

antes da insercao, a cheio apos a insercao. A operacao de remocao correspondea realizacao

do mecanismo inverso (reposicao da ligacao a tracejado e libertacao do elemento de memoria

correspondente ao ’ı’).

70 LISTAS DINAMICAS

4.5.2 Declarac ao

Tal como qualquer lista, a realizacao de uma pilha implica a declaracao de um tipo de suporte

da lista e a utilizacao de uma variavel para a base da pilha. A declaracao da pilha pode ser feita,

por exemplo, pela declaracao

typedef struct _tipoPilha {tipoDados dados;struct _tipoPilha *seg;

} tipoPilha;

onde se admite quetipoDados ja foi definido e caracteriza o tipo de informacao registada em

cada posicao da pilha.

A utilizacao da pilha implica que no programa principal, ou no bloco de codigo onde se

pretende utilizar a pilha, seja declarada uma variavel de tipo apontador paratipoPilha que

registe a base da pilha. Ou seja, sera necessario dispor de uma variavel declarada, por exemplo,

por

tipoPilha *pilha;

4.5.3 Inicializac ao

A primeira operacao necessaria para utilizar a pilhae inicializa-la ou cria-la. Uma pilha vazia

deve ter a sua base apontada paraNULL. Embora seja possıvel realizar directamente uma atribuicao

a variavel pilha, tratando-se de um detalhe interno de manipulacao do tipotipoPilha , esta

inicializacao devera ser delegada numa funcao especıfica. Deste modo, para respeitar a metodolo-

gia de abstraccao de dados, deve declarar-se uma pequena funcao

tipoPilha *inicializa(){return NULL;

}

e utilizar-se esta funcao sempre que seja necessario inicializar a pilha:

pilha = inicializa();

L ISTAS: PILHAS 71

4.5.4 Sobreposic ao

A operacao de sobreposicao exige a seguinte sequencia de operacoes:

• Reserva de memoria dinamica para armazenar um novo elemento.

• Copia dos dados para o elemento criado.

• Insercao do novo elemento na base da pilha.

Para a criacao da memoria dinamica,e conveniente criar uma funcao novoNo() que cria

espaco para um novo no, verificando a simultaneamente a existencia de erros na reserva de

memoria. Esta funcao pode ser definida como

tipoPilha *novoNo(tipoDados x){tipoPilha *novo = calloc(1,sizeof(tipoPilha));

if(novo == NULL)Erro("Erro na reserva de mem oria");

novo -> dados = x;novo -> seg = NULL;return novo;

}

ondeErro() e uma funcao generica simples que imprime uma mensagem de erro e termina o

programa (ver seccao 4.5.7).

A operacao de insercao no topo da pilha exige a realizacao das operacoes representadas na

figura 4.5. Estas podem ser realizada pela seguinte funcao:

tipoPilha *sobrepoe(tipoPilha *pilha,tipoDados x){tipoPilha *novo;

novo = novoNo(x);novo -> seg = pilha;return novo;

}

Esta funcao, apos a criacao do novo elemento, limita-se a colocar o apontadorseg a apon-

tar para o elemento que anteriormente se encontrava no topo, e indicara base que o novo topo

corresponde ao novo elemento inserido.

72 LISTAS DINAMICAS

Note-se que esta funcao 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 ao

A operacao de remocao da pilhae acompanhada da leitura. Tal como anteriormente a funcao

recebe o apontador para a base da lista e devolve a base alterada. Dado que a remocao e acom-

panhada de leitura, a funcao recebe um segundo apontador, passado por referencia, que deve ser

usado para guardar o valor do elemento removido. Uma funcao possıvel para a realizacao desta

operacaoe

tipoPilha *retira(tipoPilha *pilha,tipoDados *x){tipoPilha *aux;

if(pilhaVazia(pilha))Erro("remoc ao de uma pilha vazia");

*x = pilha -> dados;aux = pilha -> seg;free(pilha);return aux;

}

A operacao de remocaoe precedida de um teste para verificacao de pilha vazia, para garantia

de integridade da memoria (v. seccao 4.5.6). Note-se que apos a leitura da pilha, o bloco de

memoria utilizadoe libertado pela funcaofree() .

4.5.6 Teste

Antes de ser tentada a remocao 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 necessario,

se o apontador da base se encontra com o valorNULL. Esta realizacao, ainda que correcta, violaria

o princıpio essencial de abstraccao de dados que temos vindo a respeitar: a caracterizacao como

vazia de uma pilhae um detalhe interno dotipoPilha , e como tal deve ser delegado numa

funcao especıfica, de tipo booleano. Deste modo, poderia fazer-se

int pilhaVazia(tipoPilha *pilha){return (pilha == NULL);

}

L ISTAS: PILHAS 73

Esta funcao retorna 1 se a pilha estiver vazia, e 0 em caso contrario.

4.5.7 Exemplo

Suponha-se que se pretende implementar um sistema de inversao de caracteres baseado na

pilha definida anteriormente. Uma das vantagens de utilizar uma pilha para este efeito consiste

no facto de nao ser necessario definir a partida a dimensao maxima da cadeia de caracteres: o

programa efectua a reserva e libertacao de memoria a medida das necessidades do programa.

Neste caso,tipoDados e realizado por um simples caracter. Para respeitar e exemplificar

o princıpio de abstraccao, iremos escrever os metodos especıficos de leitura e escrita deste tipo.

De modo a explorar de forma eficaz a independencia dos diversos tipos de dados, os metodos

correspondentes a cada tipo devem ser declarados em ficheiros separados. Deste modo, os metodos

de acesso atipoDados sao agrupados num ficheirodados.c . Os prototipos correspondentes

sao declarados no ficheirodados.h .

Ficheiro dados.h

/** Ficheiro: dados.h* Autor: Fernando M. Silva* Data: 7/11/2002* Conte udo:* Ficheiro com declarac ao de tipos e* prot otipos dos m etodos para manipulac ao* 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;

/* M etodos de acesso a tipo dados */int leDados(tipoDados *x);void escreveDados(tipoDados x);#endif /* _DADOS_H */

74 LISTAS DINAMICAS

Ficheiro dados.c

/** Ficheiro: dados.c* Autor: Fernando M. Silva* Data: 12/11/2002* Conte udo:* Metodos para manipulac ao 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 abstraccao de dados implementada sugere que todos

os metodos de acesso atipoPilha sejam agrupados num ficheiropilha.c , ficando as

declaracoes e prototipos correspondentes acessıveis num ficheiropilha.h .

Deste modo, ter-se-ia

Ficheiro pilha.h

/** Ficheiro: pilha.h* Autor: Fernando M. Silva* Data: 7/11/2000* Conte udo:* Ficheiro com declarac ao de tipos e* prot otipos dos m etodos para manipulac ao

L ISTAS: PILHAS 75

* de uma pilha simples de elementos gen ericos* de "tipoDados".*/

#ifndef _PILHA_H#define _PILHA_H

#include "dados.h"

typedef struct _tipoPilha {tipoDados dados;struct _tipoPilha *seg;

} tipoPilha;

/* Prot otipos das func oes */

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* Conte udo:* Metodos para manipulac ao de uma pilha suportada* numa estrutura din amica ligada*/

#include "pilha.h"#include "util.h"

tipoPilha *novoNo(tipoDados x){/*

* Cria um novo n o para a pilha*/

tipoPilha *novo = calloc(1,sizeof(tipoPilha));if(novo == NULL)

Erro("Erro na reserva de mem oria");novo -> dados = x;novo -> seg = NULL;return novo;

76 LISTAS DINAMICAS

}

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 contr ario*/

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 vari avel que* retorna o valor lido da pilha* Retorna:* Pilha modificada

L ISTAS: PILHAS 77

*/tipoPilha *aux;if(pilhaVazia(pilha))

Erro("remoc ao de uma pilha vazia");

*x = pilha -> dados;aux = pilha -> seg;free(pilha);return aux;

}

A funcao generica de erroErro() pode ser declarada num modulo genericoutil.c , onde

sao agrupadas funcoes utilitarias genericas (neste exemplo,Erro() e unica). O prototipos corre-

spondente deve ser declarado num moduloutil.h .

Ficheiro util.h

/** Ficheiro: util.h* Autor: Fernando M. Silva* Data: 7/11/2002* Conte udo:* Ficheiro com declarac ao de func oes e* prot otipos gen ericos*/

#ifndef _UTIL_H#define _UTIL_H

void Erro(char *msgErro);

#endif /* _UTIL_H */

Ficheiro util.c

/** Ficheiro: util.c* Autor: Fernando M. Silva* Data: 1/11/2002* Conte udo:* Func oes gen ericas*/

78 LISTAS DINAMICAS

#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, porultimo, o programa principal. Este limita-se a inicializar a pilha e a efectuar

a leitura de um sequencia de dados, acumulando-os sucessivamente na pilha. A leiturae efectuada

ate que a funcao leDados() (metodo detipoDados ) identifique uma mudanca de linha na

entrada. Seguidamente, os dados sao 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* Conte udo:* Programa principal simples para teste* de uma pilha, usada para invers ao 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 sequ encia de caracteres:\n");while(!leDados(&x)){

pilha = sobrepoe(pilha,x);}

L ISTAS: PILHAS 79

printf("Sequ encia invertida:\n");while(!pilhaVazia(pilha)){

pilha = retira(pilha,&x);escreveDados(x);

}printf("\n");exit(0);

}

A compilacao automatica de todos os modulos pode ser realizada por meio do utilitariomake.

A Makefile correspondente poderia ser escrita como

## Ficheiro: Makefile# Autor: Fernando M. Silva# Data: 7/11/2000# Conte udo:# Makefile para teste de estruturas din amicas## A vari avel CFLAGS especifica as flags usadas# por omiss ao nas regras de compilac ao## A vari avel SOURCES, que define os ficheiro# fonte em C, s o e usada para permitir a# evocac ao do utilit ario "makedepend" (pelo# comando ’make depend’), de modo a actualizar# automaticamente as depend encias dos ficheiros# .o nos ficheiros .h## A vari avel OBJECTS define o conjunto dos# ficheiros objectos#CFLAGS=-g -Wall -ansi -pedanticSOURCES=main.c pilha.c dados.c util.cOBJECTS=main.o pilha.o dados.o util.o## Comando de linkagem dos execut aveis#teste: $(OBJECTS)

gcc -o $@ $(OBJECTS)

## A regra ’make depend’ efectua uma actualizac ao da# makefile, actualizando as listas de depend encias dos

80 LISTAS DINAMICAS

# 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 Listas: filas

4.6.1 Introduc ao

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 filae a vulgar fila de espera. Cada novo

elemento armazenadoe colocado no final da fila, enquanto que cada elemento retiradoe obtido do

inıcio da fila (figura 4.6, A).

Uma fila pode ser realizada por meio de uma lista ligada, relativamentea qual sao mantidos

nao um, mas dois apontadores: um para a base ou inıcio, por onde sao retirados os elementos, e

outro para o fim ouultimo elemento da lista, que facilita a insercao de novos elementos na lista.1

4.6.2 Declarac ao

De forma a que seja possıvel manipular umaunica variavel dotipoFila , estae realizada

por uma estrutura de dados que agrupa os dois apontadores, inıcio e fim. Deste modo, a declaracao

da fila pode ser realizada por

1De facto, o apontador para a base seria suficiente para realizar a fila; no entanto, cada operacao de insercao exigiria

percorrer a totalidade da fila para realizar a insercao no final, metodo que seria pouco eficiente.

L ISTAS: FILAS 81

’L’ ’u’ ’í’fim

inicio

A’L’ ’u’ ’s’fim

inicio

’í’

B

’L’ ’u’ ’s’fim

inicio

’í’

C

Figura 4.6: Realizacao de uma fila de caracteres com uma lista ligada. A - Estrutura da fila, B -

Fila em A apos a insercao do caracter ’s’ (a tracejado, as ligacoes eliminadas), C - Fila em B apos

a leitura de um caracter (’L’).

typedef struct _tipoLista {tipoDados dados;struct _tipoLista *seg;

} tipoLista;

typedef struct _tipoFila {tipoLista *fim;tipoLista *inicio;

} tipoFila;


A inicializacao da fila vazia corresponde simplesmente a colocar a NULL os dois apontadores

da fila. Deste modo, a inicializacao da fila pode ser realizada simplesmente por

void inicializa(tipoFila *fila){fila -> inicio = NULL;fila -> fim = NULL;

}

Note-se que na chamadaa funcao o argumento deve ser efectuada por referencia (passando o

endereco da variaveltipoFila ) de modo a que a variavel seja alteravel pela funcao.

82 LISTAS DINAMICAS

4.6.4 Inserc ao

A insercao de novos elementos correspondea colocacao de elementos no final da fila, tal como

representado graficamente na figura 4.6, caso B.

Tal como no caso da pilha, para a criacao da memoria dinamica,e conveniente criar uma

funcao auxiliarnovoNo() .

tipoLista *novoNo(tipoDados x){tipoLista *novo = calloc(1,sizeof(tipoFila));


novo -> dados = x;novo -> seg = NULL;return novo;

}

A funcao de insercao 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 funcao e necessario considerar o caso particular em que a fila esta vazia e em que,

como tal, o apontadorfim esta aNULL. Neste caso particular, ambos os apontadores (inicio

e fim ) devem ser colocados ser inicializados com o endereco do novo elemento inserido. No

caso habitual (lista nao vazia), basta adicionar o novo elemento aoultimo da lista e modificar o

apontadorfim .

L ISTAS: FILAS 83

4.6.5 Remoc ao

A insercao de novos elementos correspondea eliminacao de elementos presentes no final da

fila, tal como representado graficamente na figura 4.6, caso C.

Esta funcao pode ser realizada por

void retira(tipoFila *fila,tipoDados *x){tipoLista *aux;

if(filaVazia(fila))Erro("Remoc ao 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 funcao deretira tem tambem uma estrutura simples. Tal como na funcao de insercao,e

necessario considerar o caso particular em que a lista tem apenas um elemento, situacao em que o

apontadorfim deve ser colocado aNULLdepois da remocao.

Tal como no caso da pilha,e testada a condicao de pilha vazia antes de efectuar a remocao

(ver seccao 4.6.6).

4.6.6 Teste

Para manipulacao da listae indispensavel dispor de uma funcao para testar se a fila se encontra

vazia. Para este teste basta verificar qualquer um dos apontadores se encontra aNULL. Este teste

pode ser efectuado pelo codigo

int filaVazia(tipoFila *fila){return (fila -> inicio == NULL);

}

84 LISTAS DINAMICAS

4.6.7 Exemplo

Para uma maior semelhanca com o exemplo da pilha, utiliza-se tambem neste exemplo o caso

de uma fila de caracteres. Como seria de esperar, a fila nao realiza neste caso uma inversao, mas

apenas um armazenamento temporario da informacao, permitindo a sua reproducao pela mesma

ordem de entrada.

Tal como no exemplo da pilha, o codigo foi distribuıdo por tres ficheiros:main.c , fila.c

edados.c , tendo para os doisultimos sido desenvolvido um ficheiro de prototipos associado.

Dada a semelhanca com o exemplo da pilha, apresentam-se aqui apenas o conteudo

dos varios ficheiros, sem outros comentarios. Omite-se aqui o conteudo dos ficheiros

dados.h, dados.c, util.h eutil.c por serem obviamente identicos aos anteriores.

Ficheiro fila.h

/** Ficheiro: fila.h* Autor: Fernando M. Silva* Data: 7/11/2002* Conte udo:* Ficheiro com declarac ao de tipos e* prot otipos dos m etodos para manipulac ao* de uma fila simples de elementos gen ericos* de "tipoDados".*/

#ifndef _FILA_H#define _FILA_H

#include "dados.h"


} tipoLista;

typedef struct _tipoFila {tipoLista *fim;tipoLista *inicio;

} tipoFila;

/* Prot otipos das func oes */

L ISTAS: FILAS 85

void inicializa(tipoFila *fila);void adiciona(tipoFila *fila,tipoDados x);void retira(tipoFila *fila,tipoDados *x);int filaVazia(tipoFila *fila);

#endif /* _FILA_H */

Ficheiro fila.c

/** Ficheiro: fila.c* Autor: Fernando M. Silva* Data: 1/11/2002* Conte udo:* Metodos para manipulac ao de uma fila suportada* numa estrutura din amica ligada*/

#include "fila.h"#include "util.h"

tipoLista *novoNo(tipoDados x){/*

* Cria um novo n o para a fila*/

tipoLista *novo = calloc(1,sizeof(tipoFila));if(novo == NULL)


}

void inicializa(tipoFila *fila){/*

* Inicializa uma nova fila*/

fila -> inicio = NULL;fila -> fim = NULL;

}

int filaVazia(tipoFila *fila){/*

* Verifica o estado da fila* Argumentos:

86 LISTAS DINAMICAS

* fila - Apontador para a base da fila* Retorna:* 1 se a fila estiver vazia* 0 em caso contr ario*/

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 vari avel que* retorna o valor lido da fila*/

tipoLista *aux;if(filaVazia(fila))

Erro("Remoc ao 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* Conte udo:* 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 sequ encia de caracteres:\n");while(!leDados(&x)){

adiciona(&fila,x);}printf("Sequ encia lida:\n");while(!filaVazia(&fila)){

retira(&fila,&x);escreveDados(x);

}printf("\n");exit(0);

}

4.7 Listas ordenadas

4.7.1 Introduc ao

Um vector pode ser ordenado segundo uma qualquer relacao de ordem utilizando um algo-

ritmo apropriado(Knuth, 1973) (selection sort, bubble-sort, quicksortou qualquer outro). Embora

estes algoritmos estejam bem estudados e sejam frequentemente necessarios, todos eles requerem

um esforco computacional significativo.E possıvel provar que a quantidade de trabalho necessaria

para esta tarefa naoe apenas proporcional ao numero de elementos a ordenar: a complexidade da

88 LISTAS DINAMICAS

tarefa aumenta significativamente mais que a dimensao do vector. Para compreender melhor a

quantidade de trabalho exigido, podemos comparar esta situacao ao de arrumar alfabeticamente

uma biblioteca a partir de uma situacao desorganizada. Se arrumar uma biblioteca com 5,000

livros demorar um dia, arrumar uma biblioteca com 10,000 livros nao demorara apenas dois dias,

mas sim tres ou quatro, ja que cada tıtulo individual tera que ser alfabeticamente comparado com

um numero muito maior de outros livros.

No caso de uma biblioteca, se se pretender evitar a tarefa herculea de ordenar todos os livros,

o melhore mante-la sempre ordenada. Desta forma, cada novo livro adicionado tera apenas que

ser colocado no local certo, tarefa obviamente muito mais rapida.

Em C, quando os elementos a ordenar se encontram armazenados num vector, o metodo an-

terior corresponde basicamente a encontrar o local de insercao, deslocar todos os elementos pos-

teriores de uma posicao, e inserir o elemento na posicao assim aberta. Embora o algoritmo seja

simples, a tarefa de deslocar todos os elementos de uma posicao e computacionalmente pesada,

sobretudo quando a insercao se efectua nas posicoes iniciais. O paralelo que podemos encontrar

no exemplo da bibliotecae o de uma estante repleta de livros, excepto naultima prateleira. A

introducao ordenada de um novo tıtulo na primeira prateleira exige deslocar todos os tıtulos de

uma posicao. Dado que so existe espaco disponıvel naultima prateleira, este processo pode exigir

de facto movimentar livros em todas as prateleiras da estante.

As listas dinamicas oferecem uma forma simples de criar e manter eficientemente uma

coleccao de objectos ordenados. Ao contrario do vector, em que todas as posicoes se encon-

tram em enderecos de memoria contıguos, a ordem dos elementos da lista nao depende do seu

endereco de memoria, mas apenas da ordem definida pela sequencia de apontadores, tal como ja

se mostrou 4.2.

As operacoes necessarias para a manipulacao e manutencao de uma lista ordenada sao

generalizacoes relativamente simples dos casos da pilha e da fila. Algumas destas operacoes,

como criar a lista ou listar os seus elementos, ja foram apresentadas anteriormente. Apenas algu-

mas das operacoes descritas seguidamente, como a insercao, procura e remocao no meio da lista

sao de facto totalmente novas.

4.7.2 Declarac ao e inicializac ao

A declaracao e inicializacao de uma lista segue os passos ja vistos para o caso da pilha. A

declaracao da lista pode ser realizada por

typedef struct _tipoLista {


tipoDados dados;struct _tipoLista *seg;

} tipoLista;

onde, tal como nos exemplos anteriores,tipoDados e um tipo abstracto que define a informacao

armazenada em cada elemento.

De igual modo, a inicializacao da lista corresponde apenasa inicializacao do apontador a

NULL, por meio da funcao de inicializacao

tipoLista *inicializa(){return NULL;

}

4.7.3 Listagem ordenada

A listagem ordenada corresponde apenas a uma listagem convencional do conteudo. 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 procurae 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 funcao de procura deve retornarNULLcaso o elemento a procurar nao 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 LISTAS DINAMICAS

Neste caso, a funcao de procura pode ser realizada por

tipoLista *procura(tipoLista *base,tipoDados x){tipoLista *aux;

aux = base;while((aux!=NULL) && aux -> dados != x)

aux = aux -> seg;return aux;

}

A funcao anterior, embora funcione, apresenta o inconveniente de nao 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 numero 15 sera necessario ir ate ao fim da lista

para concluir que o numero nao esta presente. Comoeobvio, esta conclusao poderia ter sido tirada

muito mais cedo, logo que fosse atingido o numero 16 na lista.

Deste modo, uma versao mais optimizada da funcao 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;

elsereturn NULL;

}

Neste caso, a listae percorrida enquanto o elemento a procurar for inferiora posicao actual

da lista. Quando o cicloe interrompido,e testado se se se atingiu o fim da lista ou se se encontrou

o elemento procurado.

Nesta funcao, 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 expressoes logicas. Repare-se

que o segundo operando da disjuncao ( aux -> dados == x ) so pode ser avaliado seaux


for diferente deNULL, ja que de outra forma se poderia estar a gerar uma violacao de memoria

(tentativa de acesso atraves do endereco 0, o que se encontra fora do controlo do programador).

No entanto, o C garante que realiza a avaliacao de expressoes logicas da esquerda para a direita e

que interrompe a sua avaliacao assim que for possıvel determinar univocamente o resultado final.

Neste exemplo, seaux for NULL, o primeiro operando da conjuncao logica ’&&’ e falso, o que

implica que o resultado global da expressao tambem oe. Assim, nao sendo necessario o calculo

do segundo operando, nao ha o risco de se produzir a violacao de memoria decorrente do acesso

atraves de um apontadorNULL.

Refira-se, porultimo, que num problema pratico podem coexistir varias funcoes de procura,

consoante o que se pretende encontrar. Por exemplo, se os elementos de uma lista sao estruturas

que incluem, por exemplo, um numero e um nome, podem ser escritas duas funcoes de procura,

uma para o numero e outra para o nome. Claro que se a lista estiver ordenada por numeros, a

busca pelo numero podera ser optimizada (procura so ate encontrar um elemento de numero igual

ou superior ao procurado), mas a busca pelo nome tera obviamente que ser exaustiva se o nome

nao existir, ja que so no final da lista sera possıvel ter a certeza de que determinado nome nao faz

parte da lista.

4.7.5 Abstracc ao de dados e m etodos de teste

Nas duas funcoes de procura anteriores admitiu-se que otipoDados era um inteiro. Esta

hipotese permitiu utilizar os operadores relacionais== e< de uma forma intuitiva.

No caso mais geral em quetipoDados e um tipo abstracto generico esta comparacao

nao pode ser realizada directamente pelos operadores relacionais. Para demonstrar este facto,

considere-se quetipoDados corresponde a uma estrutura com um numero e um nome de um

aluno. Neste caso, nao faz sentido usar o operador relacional< para comparar dois alunosa e

b. De facto, o C desconhece o que se pretende comparar:e o nome dos alunosa e b ou os seus

numeros?

Para contornar esta dificuldade, seria possıvel utilizar o operador’.’ (membro de estrutura)

e aceder directamente ao campo numerico, utilizando o operador< para a comparacao, ou aceder

ao campo com o nome e utilizar a funcaostrcmp() de forma adequada. No entanto, qualquer

destas solucoes estaria a violar o princıpio de abstraccao de dados, ja que os metodos de procura

da lista, para quemtipoDados deveria ser um tipo abstracto generico, estariam a aceder direc-

tamente a detalhes internos do tipo.

A forma de resolver esta questaoe as funcoesprocura delegarem o processo de comparacao

92 LISTAS DINAMICAS

em metodos (funcoes) especıficos internos detipoDados , responsaveis pela implementacao dos

detalhes praticos da comparacao. Deste modo, admitindo que foram associados ao tipo abstracto

tipoDados um metodo com prototipo

int menor(tipoDados a,tipoDados b);

que devolve 1 sea for de algum modo anterior ab e 0 em caso contrario (as funcoes da lista nao

precisam de conhecer os detalhes desta comparacao) e um outro

int igual(tipoDados a,tipoDados b);

que devolve 1 sea for igual b segundo um dado criterio e 0 em caso contrario.

Deste modo, uma solucao mais geral da funcao 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;

elsereturn NULL;

}

Alternativamente,e frequente unificar todos os metodos de comparacao numaunica funcao

que devolve -1, 0 ou 1 consoante o primeiro elementoe anterior, igual ou posterior ao segundo.E

esta solucao quee adoptada na funcaostrcmp() para comparacao destrings .

4.7.6 Inserc ao ordenada

Para realizar uma insercao ordenadae 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 insercao ordenada requer algumas consideracoes suple-

mentares. Um dos pontos a ter em contae que para posicionar o novo elemento antes do que foi

identificadoe necessario alterar o apontador do elemento que se encontra antes deste. Ou seja, ao


105

7

antes depois

novo

Figura 4.7: Insercao entre dois elementos da lista. O apontadorantes nao aponta para o elemento

anterior da lista, mas sim para o campo apontadorseg desse elemento.

percorrer a lista,e necessario manter uma referencia nao apenas para o elemento da lista que esta

a ser comparado (elemento actual) mas tambem para o seu predecessor (elemento anterior).

De modo a melhor compreender esta operacao, e conveniente comecar por desenvolver uma

funcao auxiliar de insercao em que se admite que a posicao de insercao ja foi determinada e, como

tal, que ja existem referencias para o apontador do elemento anterior e para o elemento actual

(v. figura 4.7). Designaremos estas variaveis de referencia porantes e depois . Neste caso o

codigo desta funcao pode ser escrito

void insere(tipoLista **antes, tipoDados x, tipoLista *depois){tipoLista *novo = novoNo(x);

*antes = novo;novo -> seg = depois;

}

onde a funcaonovoNo() e semelhantesas anteriores

tipoLista *novoNo(tipoDados x){tipoLista *novo = calloc(1,sizeof(tipoLista));if(novo == NULL)


}

Uma vez definida esta funcao, a insercao ordenada apenas tem que ter em conta alguns casos

particulares, nomeadamente a insercao numa fila vazia ou a insercao antes do inıcio. Nos outros

94 LISTAS DINAMICAS

casos, basta percorrer a lista com um apontadoract , e manter presente que se deve manter um

apontadorant para o elemento anterior. A funcaoinsereOrdenado() pode entao 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 funcao recebe como um dos argumentos o valor da base e devolve o valor desta depois

da insercao. A base retornadae identicaa base inicial, excepto quando a insercaoe feita no inıcio

da lista.

O par de funcoesinsere() e insereOrdenado() foi escrita de modo a sublinhar os

diversos aspectos necessariosa insercao numa lista. No entanto, o C permite escrever uma funcao

de insercao 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;


reg

941

Figura 4.8: Remocao. O apontadorreg referencia o camposeg do registo anterior da lista.

}

Aqui, o primeiroif abrange simultaneamente a insercao numa lista vazia e antes do primeiro

elemento. Seguidamente, o ciclowhile percorre a lista, mantendo apenas um apontador (equiv-

alente ao apontadorant do exemploanterior).

4.7.7 Remoc ao

Tal como a insercao, a remocao pode ser simplificada se for escrita uma funcao auxiliar

libertaReg quee executada quando ja e conhecido o local de remocao. Esta funcao (v. figura

4.8) pode ser escrita

tipoLista *libertaReg(tipoLista *reg){tipoLista *aux;

aux = reg;reg = reg -> seg;free(aux);return reg;

}

Seguidamente,e necessario escrever uma funcao que procure o o elemento a apagar e chame

a funcao anterior. Esta funcaoe 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 LISTAS DINAMICAS

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 codigo completo de um programa que manipula uma

lista ordenada de racionais. O tipo racionale representado por dois inteiros, que descrevem o seu

numerador e o denominador. O programa aceita uma sequencia de racionais. Um racional positivo

e inserido na lista, enquanto que um racional negativo provoca uma tentativa de remocao do seu

simetrico, caso este exista (ou seja, a indicacao de−35 provoca a remocao do racional35 ).

Omite-se aqui a listagem dos ficheirosutil.h e util.c , identicos ao introduzido no ex-

emplo da pilha (v. seccao 4.5.7).

Ficheiro dados.h

/** Ficheiro: lista.h* Autor: Fernando M. Silva* Data: 7/11/2000* Conte udo:* Definic ao do tipo gen erico* "tipoDados" usado nos exemplos de* estruturas de dados din amicas.** Para fins de exemplo, "tipoDados"* e realizado por uma fracc ao inteira,* a qual e’ especificada por um numerador# e um denominador*/

#ifndef _DADOS_H


#define _DADOS_H

#include <stdio.h>

typedef struct{int numerador;int denominador;

} tipoDados;

void escreveDados(tipoDados x);tipoDados leDados(char mensagem[]);float valor(tipoDados x);int igual(tipoDados x,tipoDados y);int menor(tipoDados x,tipoDados y);int numerador(tipoDados x);int denominador(tipoDados x);tipoDados simetrico(tipoDados x);#endif

Ficheiro dados.c

/** Ficheiro: dados .c* Autor: Fernando M. Silva* Data: 1/12/2000* Conte udo:* Metodos de acesso exemplificativos* da definic ao 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 100tipoDados leDados(char mensagem[]){

/** Escreve a mensagem passada por argumento, l e um racional e* valida a entrada* Argumento:* mensagem - mensagem a escrever* Retorna:* racional lido

98 LISTAS DINAMICAS

*/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 inv alido\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


* 1 se x < y* 0 em caso contr ario*/

if(x.denominador * y.denominador > 0)return x.numerador * y.denominador < y.numerador * x.denominador;

elsereturn 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 contr ario*/

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 sim etrico do racional x* Argumento:

100 LISTAS DINAMICAS

* x - racional* Retorna* sim etrico 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* Conte udo:* Ficheiro com declarac ao de tipos e* prot otipos dos m etodos para manipulac ao* de uma lista din amica simples**/

#ifndef _LISTA_H#define _LISTA_H

#include <stdio.h>#include <stdlib.h>

/** Tipo dos dados da lista*/

#include "dados.h"

/** Definic ao de tipoLista*/


} tipoLista;

/** Prot otipos dos m etodos de acesso*/


/* Inicializac ao */tipoLista *inicializa(void);

/** Procura x na lista iniciada por base, retornando um apontador* para o registo que contem este valor (ou NULL se n ao 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 cont em 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


* Conte udo:* Metodos para manipulac ao* de uma lista din amica* simples (ordenada)**/

/** Inclui ficheiro com tipo e prot otipos*/

#include "lista.h"#include "util.h"

tipoLista *novoNo(tipoDados x){/*

* Cria um novo n o da lista*/

tipoLista *novo = calloc(1,sizeof(tipoLista));if(novo == NULL)


}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;


}

tipoLista *procuraOrdenado(tipoLista *base,tipoDados x){/*

* Id entico 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 */


}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 ao*/

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 mem oria associada.* Argumentos:* reg - apontador para a vari avel 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;

}


tipoLista *apaga(tipoLista *base,tipoDados x){/*

* Apaga da lista o registo que cont em 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* Conte udo:* Programa principal simples para teste* de estruturas din amicas ligadas.** Neste teste, os dados armazenados na lista* s ao fracc oes inteiras, implementadas* por um tipo abstracto "tipoDados".* Assim:* 1. A especificac ao de um racional positivo,


* acrescenta o racional a lista* 2. A introduc ao de um racional negativo,* especifica que deve ser apagada o seu* sim etrico 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 ao de um racional positivo "

"conduz a sua\n"" inserc ao ordenada na lista.\n");

printf(" - A introduc ao de um racional ""negativo procura o seu\n"

" sim etrico 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 id entico a ");

escreveDados(x);printf(" n ao encontrado na lista\n");

}else{

base = apaga(base,x);}

}printf("\nConte udo actual da lista:\n");

VARIANTES 107

��

��

941base

Figura 4.9: Lista de inteiros com registo separado para a base. Nesta figura, a lista tem apenas tres

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 ao

Embora a estrutura fundamental das listas dinamicas seja no essencial a que se viu anterior-

mente, existem diversas variantes que tem 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 manipulacao de listas ordenadas exige que a base da lista

seja tratada como um caso particular. Uma forma de evitar estes testes adicionaise manter per-

manentemente um registo mudo no inıcio da lista (registo separado para a base) que, embora nao

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 nao ser modificado depois

da criacao da lista.

As funcoes de manipulacao da lista sao no essencial semelhantesas da lista ordenada simples.

Embora sem listar aqui todas as funcoes de acesso, referem-se algumas das que sao modificadas

pela existencia de um registo permanente na base.

A inicializacao da lista corresponde neste casoa criacao do registo da base. Deste modo, a


fim

inicio

8 951

Figura 4.10: Lista dupla de inteiros.

funcao de inicializacaoe dada por

Por outro lado, a funcao de insercao ordenada pode ser simplificada. Admitindo a utilizacao

da mesma funcao insere() ja apresentado para a lista simples, a insercao pode ser feita por

onde se pode constatar a ausencia do teste particulara base que se realiza na lista ordenada simples.

4.8.3 Listas duplamente ligadas

Um dos inconvenientes das listas simplesmente ligadase serem unidireccionais. Por outras

palavras, ao aceder a um dado elemento da listae facil aceder ao elemento seguinte, mas o acesso

ao elemento anterior naoe possıvel.

Para evitar este inconvenientee possıvel desenvolver umalista duplamente ligada, em que

cada elemento dispoe de dois apontadores, um para o elemento seguinte e outro para o anterior.

Adicionalmente, tal como no caso da fila, o acessoa listae geralmente mantido por dois apon-

tadores, um para o inıcio e outro para o fim da lista (v. figura 4.10). A declaracao 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;

ANEL DUPLO COM REGISTO SEPARADO PARA A BASE 109

base

941 4

Figura 4.11: Lista em anel de inteiros. Oultimo elemento aponta para o primeiro

��

8 95

base

Figura 4.12: Anel duplo com registo separado para a base.

4.8.4 Aneis

Numa lista simplesmente ligada, oultimo da elemento da listae identificado pelo facto do

apontador para o elemento seguinte serNULL. Uma alternativae colocar oultimo elemento da

lista a apontar para a base (v. figura 4.11). A manipulacao de uma estrutura deste tipoe muito

semelhantea de uma lista simples, substituindo-se apenas parte das comparacoes com o valor

NULLpor comparacoes com o apontador da base.

Uma lista em anel apresenta a vantagem doultimo elemento apontar para o primeiro, o que

pode ser conveniente em aplicacoes em que seja necessario percorrer os elementos da lista de uma

forma cıclica.

4.9 Anel duplo com registo separado para a base

4.9.1 Introduc ao

Um anel duplo com registo separado para a basee uma estrutura dinamica que combina as

diversas variantes abordadas anteriormente: registo separado para a base, ligacao em anel e reg-

istos com apontadores bidireccionais (figura 4.12). Embora este tipo estrutura possa sugerir uma

manipulacaoa partida mais complexa, verifica-se na pratica o inverso: a exploracao correcta desta

estrutura origina, de modo geral, codigo mais simples.


��

base

Figura 4.13: Anel vazio apos a criacao.

4.9.2 Declarac ao

A declaracao de um anele feita da forma habitual. Ou seja,

typedef struct _tipoAnel {tipoDados dados;struct _tipoAnel *seg,*ant;

} tipoAnel;


A inicializacao de um anel correspondea criacao de um registo para a base e ao fecho em anel

das suas ligacoes (figura 4.13). Esta inicializacao pode ser feita por

tipoAnel *inicializa(){tipoAnel *aux;tipoDados regMudo;

aux = novoNo(regMudo);aux -> seg = aux -> ant = aux;return aux;

}

A funcaonovoNo() , semelhanteas anteriores, pode ser definida como

tipoAnel *novoNo(tipoDados x){tipoAnel *novo = calloc(1,sizeof(tipoAnel));


novo -> dados = x;


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 funcoes para este efeito, de estrutura muito semelhante:

/* Listagem directa */void listar(tipoAnel *base ){

tipoAnel *aux;

aux = base -> seg;while(aux != base){


}}/* 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 funcoes o inıcio da listagem se efectua no elemento a seguir

a base (de modo a saltar o registo da base), enquanto que na condicao de manutencao no ciclo se

testa o regressoa base.

4.9.5 Procura

A funcao de procurae semelhantea de uma lista ordenada, omitindo o elemento inicial:


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;

elsereturn NULL;

}

Repare-se que, para simplificar a condicao do ciclo, se iniciou o registo da base com o proprio

valor do elemento a procurar. Este artifıcio garante que, mesmo que o elemento de procura nao

se encontre no anel, a procurae interrompida quando se atinge a base. Claro que, deste modo,

e preciso testara saıda do ciclo se a interrupcao se verificou por ter encontrado o local real de

interrupcao e o elemento de procura, ou por se ter encontrado o elemento artificialmente colocado

na base. Nesteultimo caso devera retornar-se o apontadorNULL.

4.9.6 Inserc ao

No caso de insercao ordenada no anel,e particularmenteutil utilizar uma funcao so para a

insercao do registo, admitindo que ja se conhece o local de insercao, e desenvolver posteriormente

a funcao de procura o local de insercao.

A primeira destas funcoes 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 funcao, a sua realizacao corresponde apenasa realizacao

das ligacoes necessarias pela ordem correcta. Na figura 4.14 detalha-se este processo de insercao

no caso de um anel de inteiros, identificando-se a correspondencia entre as ligacao e as instrucoes

da listagem.


depois

1 8

novo

(1)(2) (3)(4)

3

Figura 4.14: Insercao num anel. Os numeros entre () correspondemas atribuicoes da listagem

apresentada no texto.

Repare-se que, dado que a listae dupla,e suficiente o apontador para o elemento seguinte para

estabelecer todas as ligacoes.

A funcao de insercao propriamente dita realiza apenas a pesquisa do local de insercao. De

forma semelhante ao ja efectuado no caso da funcao de procura,e possıvel colocar uma copia

do elemento a inserir no registo da base para permitir que o caso particular de insercao no final

da lista nao tem que ser tratado como um caso particular. Deste modo, o codigo da funcao 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 ao

A operacao de remocao pode ser realizada por duas funcoes complementares. A primeira

(removeReg() ) e utilizada apos a identificacao do registo a eliminar ee responsavel pela

libertacao da memoria ocupada e reconstrucao das ligacoes. A segunda (apaga() ) que corre-

spondea funcao a utilizar externamente, procura o registo a eliminar e, caso o identifique, chama


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 metodos do tipotipoDados , e os ficheirosutil.c e

util.h , obviamente identico ao anterior.

Ficheiro anel.h

/** Ficheiro: anel.h* Autor: Fernando M. Silva* Data: 7/11/2000* Conte udo:* Ficheiro com declarac ao de tipos e* prot otipos dos m etodos para manipulac ao* de um anel com registo seoparado* para a base**/

#ifndef _ANEL_H#define _ANEL_H

#include <stdio.h>


#include <stdlib.h>

/** Tipo dos dados da lista*/

#include "dados.h"

/** Definic ao de tipoAnel*/

typedef struct _tipoAnel {tipoDados dados;struct _tipoAnel *seg,*ant;

} tipoAnel;

/** Prot otipos dos m etodos de acesso*/

/* Inicializac ao */tipoAnel *inicializa(void);

/** Procura x na lista iniciada por base, retornando um apontador* para o registo que contem este valor (ou NULL se n ao 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);


void listar(tipoAnel *base);void listarInv(tipoAnel *base);

/** Remove da lista o elemento apontado por reg


*/void libertaReg(tipoAnel *reg);

/** Apaga da lista o registo que cont em x*/

void apaga(tipoAnel *base,tipoDados x);

#endif

Ficheiro anel.c

/** Ficheiro: anel.c* Autor: Fernando M. Silva* Data: 7/11/2000* Conte udo:* Metodos para manipulac ao* de um anel com registo separado* para a base.**/

/** Inclui ficheiro com tipo e prot otipos*/

#include "anel.h"#include "util.h"

tipoAnel *novoNo(tipoDados x){/*

* Cria um novo n o da lista*/

tipoAnel *novo = calloc(1,sizeof(tipoAnel));if(novo == NULL)

Erro("Erro na reserva de mem oria");novo -> dados = x;novo -> seg = novo -> ant = NULL;return novo;

}

/* Inicializac ao. O anel vazio e constitu ıda pelo* registo da base.*/

tipoAnel *inicializa(){


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 n ao 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);}

/** Id entico 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;

elsereturn NULL;

}

/** Insere x antes do registo "depois"*/

void insere(tipoAnel *depois,tipoDados x){tipoAnel *novo = novoNo(x);


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 ao*/

act = act -> seg;}insere(act,x);

}


void listar(tipoAnel *base ){tipoAnel *aux;aux = base -> seg;while(aux != base){


}}

/** 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);


printf("\n");aux = aux -> ant;

}}

/** Remove do anel o elemento apontado por reg* e liberta a mem oria associada.*/

void libertaReg(tipoAnel *reg){reg -> seg -> ant = reg -> ant;reg -> ant -> seg = reg -> seg;free(reg);

}

/** Apaga do anel o registo que cont em 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* Conte udo:* Programa principal simples para teste* de estruturas din amicas ligadas.** Neste teste, os dados armazenados na lista* s ao fracc oes inteiras, implementadas* por um tipo abstracto "tipoDados".* Assim:* 1. A especificac ao de um racional positivo,


* acrescenta o racional a lista* 2. A introduc ao de um racional negativo,* especifica que deve ser apagada o seu* sim etrico 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 ao de um racional positivo conduz a sua\n"

" inserc ao ordenada na lista.\n");printf(" - A introduc ao de um racional negativo procura o seu\n"

" sim etrico 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 id entico a ");escreveDados(x);printf(" n ao encontrado na lista\n");

}else{

apaga(base,x);}

}printf("\nConte udo actual do anel (ordem crescente):\n");listar(base);printf("\nConte udo 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 implementacao de uma dada aplicacao requerer a utilizacao hierarquica de di-

versas 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 cat-

egoria. 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 alteracoes fundamentais de cada

vez. Uma representacao simbolica de uma lista de listas esta representada na figura 4.15.

Uma lista de listas (ou um anel de aneis) nada tem de particular do ponto de vista de

programacao. Cada lista por si so u uma estrutura do tipo apontado anteriormente. No entanto,

e necessario ter em atencao que a lista e as suas sublistas tem tipos diferentes e, de acordo com

o modelo que temos vindo a desenvolver, cada uma delas precisara de um metodo especıfico de

acesso. Por outras palavras, sera necessario manter duas funcoes de listagem, duas funcoes de

insercao, etc, dado que cada tipo de lista exige um metodo especıfico2.

A declaracao de uma lista de lista pode ser efectuada pelo codigo

typedef struct _tipoSubLista {/*

2De facto, esta duplicacao de codigo pode ser evitada escrevendo codigo baseado em apontadores genericos do tipo

void* . Esta possibilidade nao sera, por agora, abordada


tipoDadosSubLista descreve todos osatributos de cada elemento de umasublista

*/tipoDadosSubLista dadosSubLista;struct _tipoSubLista *seg;

} tipoSubLista;

typedef struct _tipoDadosLista{/*

declarac ao dos campos necess ariosa cada elemento da listaprincipalint ...char ...

*/tipoSubLista *baseSub;

} tipoDadosLista;

typedef struct _tipoListaDeListas{tipoDadosLista dados;struct _tipoListaDeListas *seg;

} tipoListaDeListas;

Note-se que se adoptou aqui quatro tipos abstractos distintos: o tipotipoDadosSubLista ,

que suporta os dados de cada sublista, o tipotipoSubLista , que suporta as sublistas, o tipo

tipoDadosLista que suporta o tipo de dados da lista principal e, finalmente, o tipoListaDeLis-

tas, que suporta a lista principal.

A manipulacao da lista faz-se pela combinacao das funcoes (metodos) 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 quee necessario inserir uma variavel

x detipoDados na sublista suportada no elemento da lista principal que tem o valory. O codigo

para este efeito seria:

tipoListaDeListas *base,*aux;tipoDadosSubLista x;tipoDadosLista y;

L ISTAS DE LISTAS 123

/*inicializac ao da lista e dos valores x e y

...

*/aux = procuraOrdenadoListaDeListas(base,y);if(aux == NULL)

fprintf(stderr,"Erro: valor n ao encontrado na lista principal");else

insereDados(aux -> dados,x);/*

...*/

A funcao insereDadose nova neste contexto, e devera ser um metodo especıfico de

tipoDadosLista . A sua estruturae muito simples, e a sua existencia deve-se apenasa ne-

cessidade de manter uma realizacao correcta da abstraccao de dados. Esta funcao seria

void insereDados(tipoDadosLista dados,tipoDadosSubLista x){insereDadosSubLista(dados.baseSub,x);

}

sendo a funcao insereDadosSubLista uma funcao convencional de insercao.

Capıtulo 5

Conclus oes

O C e provavelmente a mais flexıvel das linguagens de programacao de alto-nıvel, mas ap-

resenta uma relativa complexidade sintactica. Uma das maiores dificuldades na abordagem do

C numa disciplina introdutoria de programacao e a necessidade de introduzir os conceitos de

endereco de memoria, apontador e memoria dinamica.

Neste texto introduziu-se a nocao de apontador e discutiu-se o problema da manipulacao de

estruturas de dados dinamicas em C. Apesar da introducao de diversas estruturas de dados, o

primeiro objectivo deste texto foi, sobretudo, o de tentar explicar os mecanismos essenciais de

manipulacao de apontadores e gestao de memoria dinamica 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 ofThe Art of Computer Programming,

section 1.2, paginas 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, paginas

365–375.

Sedgwick (1990).Algorithms in C. Addison Wesley.

BIBLIOGRAFIA 129

Apendice A

Programa de teste que valida a consistencia das atribuicoes da tabela 2.1, apresentada na

seccao 2.6.4. Note-se que o facto de o programa compilar sem erros garante a consistencia dos

tipos nas atribuicoes realizadas.

Nos processadores da famılia Intel, cada endereco de memoria especifica apenas um byte,

apesar de, nos processadores 486 e seguintes, cada operacao de acessoa memoria se realizar em

palavras de 4 bytes (32 bits). De forma a obter-se valores equivalentes ao do modelo de memoria

usado nos exemplos, realiza-se uma divisao por quatro e ajusta-se o endereco escrito no monitor

de forma a que o elementox[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; escreveEndereco((int) pv3);pv3 = x + 1; escreveEndereco((int)pv3);

pf = *(x+1); escreveEndereco((int)pf);pf = *(x+2)+1; escreveEndereco((int)pf);f = *(*(x+2)+1); printf("%4.1f\n",f);

pf = *x; escreveEndereco((int)pf);

f = **x; printf("%4.1f\n",f);f = *(*x+1); printf("%4.1f\n",f);

pf = x[1]; escreveEndereco((int)pf);return 0;

}

Documents

Apontadores e Estruturas de Dados Dinâmicas em C