Grátis
259 pág.

Denunciar
Pré-visualização | Página 28 de 50
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