apostila
259 pág.

apostila

Disciplina:Algoritmos e Estrutura de Dados I542 materiais7.956 seguidores
Pré-visualização50 páginas
uma maneira para
se mascarar para o programador este processo que e´ baseado em deslocamentos (ou
somas de enderec¸os).

Na pro´xima sec¸a˜o veremos como a linguagem Pascal lida com isto.

Vetores em Pascal

Para se declarar um vetor de 200 posic¸o˜es inteiras, a linguagem Pascal usa a seguinte
sintaxe (lembre-se que em outras linguagens a sintaxe pode ser diferente):

var v: array [1. .200] of integer ;

A construc¸a˜o “1..200” indica que existem 200 posic¸o˜es controladas pela varia´vel
v. O “of integer” indica que cada posic¸a˜o e´ para se guardar um nu´mero inteiro, isto
e´, 2 bytes (dependendo da implementac¸a˜o).

A rigor, a linguagem Pascal permite que se reserve 200 posic¸o˜es de va´rias maneiras.
Basta que o intervalo “a..b” contenha 200 posic¸o˜es. Apresentamos 6 variantes dentre
as milhares poss´ıveis:

var v: array [0. .199] of integer ;

var v: array [201..400] of integer ;

var v: array [−199..0] of integer ;

var v: array [−300..−99] of integer ;

var v: array [−99..100] of integer ;

const min=11, max=210;
var v: array [min. .max] of integer ;

Em todas estas variantes, o intervalo define 200 posic¸o˜es. Em termos gerais, existe
uma restric¸a˜o forte. O intervalo deve ser definido em termos de nu´meros de algum
tipo ordinal (em Pascal), isto e´, integer, logint, . . . , ate´ mesmo char. Tambe´m em
Pascal, o limite inferior deve ser menor ou igual ao limite superior. Na sequeˆncia
desta sec¸a˜o, vamos considerar a versa˜o que usa o intervalo de 1 a 200.

Agora, para guardar um valor qualquer, digamos 12345, na posic¸a˜o 98 do vetor v,
em Pascal, se usa um dos dois comandos seguintes:

v[98]:= 12345;

read(v[98]) ; (∗ e se digita 12345 no teclado ∗)

128 CAPI´TULO 10. ESTRUTURAS DE DADOS

Em termos gerais, vejamos os seguintes exemplos, para fixar o conceito:

read (v[1 ]) ; (∗ le do teclado e armazena na primeira posicao de v ∗)

i := 10;
v[ i+3]:= i ∗ i ; (∗ armazena o quadrado de i (100) na posicao 13 de v ∗)

write ( i , v[ i ] ) ; (∗ imprime o par (10, 100) na tela ∗)

write (v[v[13 ] ] ) ; (∗ imprime o valor de v[100] na tela ∗)

v[201]:= 5; (∗ gera erro , pois a posicao 201 nao existe em v ∗)

v[47]:= sqrt (4) ; (∗ gera erro , pois sqrt retorna um real , mas v eh de inteiros ∗)

var x: real ;
v[x]:= 10; (∗ gera erro , pois x eh do tipo real , deveria ser ordinal ∗)

Note que a construc¸a˜o (v[v[13]]) so´ e´ poss´ıvel pois o vetor v e´ do tipo integer. Se
fosse um vetor de reais isto na˜o seria poss´ıvel (em Pascal).

10.1.1 Primeiros problemas com vetores

Para iniciarmos nossa saga pelos algoritmos sofisticados que usam vetores, vamos
apresentar uma se´rie de problemas ja´ conhecidos para vermos como eles podem ser
resolvidos usando vetores. Aproveitaremos para fixar conceitos ja´ ensinados sobre pro-
cedimentos e func¸o˜es. Desta forma o estudante podera´, resolvendo exerc´ıcios simples,
se concentrar na novidade, isto e´, no uso de vetores.

Lendo vetores

Para resolvermos o problema apontado acima, isto e´, um programa que leia 10 nu´meros
reais e os imprima na ordem inversa da leitura, precisamos inicialmente ler os elemen-
tos do vetor. O co´digo da figura 10.1 ilustra uma soluc¸a˜o poss´ıvel. Quando executado,
considerando que no teclado foi digitada a sequeˆncia 15, 12, 27, 23, 7, 2, 0, 18, 19 e
21, teremos em memo´ria algo como ilustrado na figura seguinte:

1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 . . . 197 198 199 200
15 12 27 23 7 2 0 18 19 21 ? ? ? ? ? . . . ? ? ? ?

E´ importante, neste momento, atentar para alguns fatos:

1. este vetor tem 200 elementos, pois seu tamanho foi definido em tempo de com-
pilac¸a˜o. Como so´ foram lidos os 10 primeiros elementos, o restante do ve-
tor conte´m valores indefinidos que ja´ estavam em memo´ria quando programa
comec¸ou a executar. Isto e´ o que chamamos de lixo de memo´ria e esta´ repre-
sentado com interrogac¸o˜es na figura acima;

10.1. VETORES 129

program lendo vetores ;
var v: array [1. .200] of real ; (∗ define um vetor de reais ∗)

i : integer ;

begin
i := 1;
while i <= 10 do
begin

read (v[ i ] ) ;
i := i + 1;

end;
end.

Figura 10.1: Lendo elementos e colocando no vetor.

2. o enunciado na˜o especifica onde se armazenar os valores, como o vetor v tem
200 posic¸o˜es, poder´ıamos ter usado qualquer intervalo, mas normalmente se usa
um vetor a partir da posic¸a˜o 1, e os algoritmos na˜o podem deixar “buracos” no
vetor;

3. o uso da varia´vel auxiliar i no programa facilita muito a manipulac¸a˜o de vetores.
Sena˜o ter´ıamos que usar comandos do tipo: read(v[1]), read(v[2]), read(v[3]),
. . . , recaindo nos problemas do in´ıcio do curso;

4. a t´ıtulo de exemplo, mostramos a versa˜o deste programa usando os comando
repeat e for. Os trechos de co´digo duas figuras 10.2 e 10.3, abaixo, ilustram
estas duas variantes.

begin
for i := 1 to 10 do

read (v[ i ] ) ;
end.

Figura 10.2: Lendo elementos e colocando no vetor, usando for.

begin
i := 1;
repeat

read (v[ i ] ) ;
i := i + 1;

until i > 10;
end.

Figura 10.3: Lendo elementos e colocando no vetor, usando repeat.

Uma vez que se leu o vetor, pode-se agora manipular os dados da maneira ne-
cessa´ria para se resolver o problema desejado. Nas sec¸o˜es seguintes vamos exemplificar
usando diversos algoritmos ja´ conhecidos.

130 CAPI´TULO 10. ESTRUTURAS DE DADOS

Imprimindo vetores

O programa ilustrado na figura 10.4 mostra como ler 10 nu´meros reais do teclado e
imprimı´-los na tela. Usaremos o comando for nos exemplos seguintes pois ele faci-
lita muito a redac¸a˜o dos programas que manipulam vetores. Os co´digos ficam mais
compactos e leg´ıveis.

program lendo e imprimindo vetores ;
var v: array [1. .200] of real ;

i : integer ;

begin
for i := 1 to 10 do
begin

read (v[ i ] ) ;
writeln (v[ i ] ) ;

end;
end.

Figura 10.4: Lendo e imprimindo.

E´ importante observar que este programa poderia ter sido resolvido sem o uso de
vetores, como mostrado na figura 10.5.

program lendo e imprimindo vetores ;
var x: real ; i : integer ;

begin
for i := 1 to 10 do
begin

read (x) ;
writeln (x) ;

end;
end.

Figura 10.5: Lendo e imprimindo.

Mostramos esta versa˜o para o leitor poder comparar os dois co´digos e perceber
que a principal diferenc¸a entre as duas soluc¸o˜es e´ que, na versa˜o com vetores, todos
os nu´meros lidos do teclado continuam em memo´ria apo´s a leitura do u´ltimo nu´mero
digitado, enquanto que na versa˜o sem vetores, a varia´vel x teria armazenado apenas
e ta˜o somente o u´ltimo nu´mero lido.

Uma outra maneira de escrever co´digo para resolver o mesmo problema e´ separar o
programa em duas partes: uma para a leitura e a outra para a impressa˜o. O resultado
e´ o mesmo, apenas a maneira de fazer difere. A figura 10.6 ilustra esta soluc¸a˜o.

10.1. VETORES 131

program lendo e imprimindo vetores ;
var v: array [1. .200] of real ;

i : integer ;

begin
(∗ este pedaco de codigo trata apenas da leitura dos dados ∗)
for i := 1 to 10 do

read (v[ i ] ) ;

(∗ este outro pedaco de codigo trata apenas da impressao ∗)
for i := 1 to 10 do

writeln (v[ i ] ) ;
end.

Figura 10.6: Lendo e imprimindo.

O co´digo apresenta uma certa modularidade, pois pode ser facilmente visualizado
como contendo uma parte que se ocupa da leitura dos dados separada da outra parte
que se ocupa da impressa˜o dos dados.

Apesar do fato deste programa funcionar, insistimos que ele merece ser escrito
seguindo as boas te´cnicas de programac¸a˜o. Neste sentido o uso de func¸o˜es e procedi-
mentos pode ser explorado para que os dois mo´dulos do programa (leitura e impressa˜o)
possam ficar claramente destacados de maneira independente um do outro.

O resultado final e´ o mesmo em termos de execuc¸a˜o do programa e de seu resul-
tado final na tela, exibido para quem executa o programa. Por outro lado, para o
programador, o co´digo e´ mais elegante. Por