apostila
259 pág.

apostila


DisciplinaAlgoritmos e Estrutura de Dados I708 materiais7.916 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\u2dco veremos como a linguagem Pascal lida com isto.
Vetores em Pascal
Para se declarar um vetor de 200 posic¸o\u2dces 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\u2dco \u201c1..200\u201d indica que existem 200 posic¸o\u2dces controladas pela varia´vel
v. O \u201cof integer\u201d indica que cada posic¸a\u2dco e´ para se guardar um nu´mero inteiro, isto
e´, 2 bytes (dependendo da implementac¸a\u2dco).
A rigor, a linguagem Pascal permite que se reserve 200 posic¸o\u2dces de va´rias maneiras.
Basta que o intervalo \u201ca..b\u201d contenha 200 posic¸o\u2dces. Apresentamos 6 variantes dentre
as milhares poss´\u131veis:
var v: array [0. .199] of integer ;
var v: array [201..400] of integer ;
var v: array [\u2212199..0] of integer ;
var v: array [\u2212300..\u221299] of integer ;
var v: array [\u221299..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\u2dces. Em termos gerais, existe
uma restric¸a\u2dco 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\u2c6ncia
desta sec¸a\u2dco, vamos considerar a versa\u2dco que usa o intervalo de 1 a 200.
Agora, para guardar um valor qualquer, digamos 12345, na posic¸a\u2dco 98 do vetor v,
em Pascal, se usa um dos dois comandos seguintes:
v[98]:= 12345;
read(v[98]) ; (\u2217 e se digita 12345 no teclado \u2217)
128 CAPI´TULO 10. ESTRUTURAS DE DADOS
Em termos gerais, vejamos os seguintes exemplos, para fixar o conceito:
read (v[1 ]) ; (\u2217 le do teclado e armazena na primeira posicao de v \u2217)
i := 10;
v[ i+3]:= i \u2217 i ; (\u2217 armazena o quadrado de i (100) na posicao 13 de v \u2217)
write ( i , v[ i ] ) ; (\u2217 imprime o par (10, 100) na tela \u2217)
write (v[v[13 ] ] ) ; (\u2217 imprime o valor de v[100] na tela \u2217)
v[201]:= 5; (\u2217 gera erro , pois a posicao 201 nao existe em v \u2217)
v[47]:= sqrt (4) ; (\u2217 gera erro , pois sqrt retorna um real , mas v eh de inteiros \u2217)
var x: real ;
v[x]:= 10; (\u2217 gera erro , pois x eh do tipo real , deveria ser ordinal \u2217)
Note que a construc¸a\u2dco (v[v[13]]) so´ e´ poss´\u131vel pois o vetor v e´ do tipo integer. Se
fosse um vetor de reais isto na\u2dco seria poss´\u131vel (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\u2dces. Desta forma o estudante podera´, resolvendo exerc´\u131cios 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\u2dco poss´\u131vel. Quando executado,
considerando que no teclado foi digitada a seque\u2c6ncia 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\u2dco. 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\u2dces na figura acima;
10.1. VETORES 129
program lendo vetores ;
var v: array [1. .200] of real ; (\u2217 define um vetor de reais \u2217)
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\u2dco especifica onde se armazenar os valores, como o vetor v tem
200 posic¸o\u2dces, poder´\u131amos ter usado qualquer intervalo, mas normalmente se usa
um vetor a partir da posic¸a\u2dco 1, e os algoritmos na\u2dco podem deixar \u201cburacos\u201d no
vetor;
3. o uso da varia´vel auxiliar i no programa facilita muito a manipulac¸a\u2dco de vetores.
Sena\u2dco ter´\u131amos que usar comandos do tipo: read(v[1]), read(v[2]), read(v[3]),
. . . , recaindo nos problemas do in´\u131cio do curso;
4. a t´\u131tulo de exemplo, mostramos a versa\u2dco 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\u2dces 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\u131´-los na tela. Usaremos o comando for nos exemplos seguintes pois ele faci-
lita muito a redac¸a\u2dco dos programas que manipulam vetores. Os co´digos ficam mais
compactos e leg´\u131veis.
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\u2dco para o leitor poder comparar os dois co´digos e perceber
que a principal diferenc¸a entre as duas soluc¸o\u2dces e´ que, na versa\u2dco 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\u2dco sem vetores, a varia´vel x teria armazenado apenas
e ta\u2dco 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\u2dco. O resultado
e´ o mesmo, apenas a maneira de fazer difere. A figura 10.6 ilustra esta soluc¸a\u2dco.
10.1. VETORES 131
program lendo e imprimindo vetores ;
var v: array [1. .200] of real ;
i : integer ;
begin
(\u2217 este pedaco de codigo trata apenas da leitura dos dados \u2217)
for i := 1 to 10 do
read (v[ i ] ) ;
(\u2217 este outro pedaco de codigo trata apenas da impressao \u2217)
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\u2dco dos dados.
Apesar do fato deste programa funcionar, insistimos que ele merece ser escrito
seguindo as boas te´cnicas de programac¸a\u2dco. Neste sentido o uso de func¸o\u2dces e procedi-
mentos pode ser explorado para que os dois mo´dulos do programa (leitura e impressa\u2dco)
possam ficar claramente destacados de maneira independente um do outro.
O resultado final e´ o mesmo em termos de execuc¸a\u2dco 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