b, delta : real) : real ; begin maior raiz:= (−b + sqrt(delta))/(2∗a) ; end; begin (∗ programa principal ∗) ler (a , b, c) ; (∗ garante−se que a nao eh nulo ∗) delta:= calcula delta (a , b, c) ; i f delta >= 0 then begin x1:= menor raiz (a , b, delta) ; writeln (x1) ; x2:= maior raiz (a , b, delta) ; writeln (x2) ; end else writeln (’raizes complexas’) ; end. Figura 9.11: Calculando ra´ızes de equac¸a˜o do segundo grau. 9.4. CA´LCULO DO MDC PELA DEFINIC¸A˜O 123 begin (∗ programa principal ∗) ler (a , b, c) ; (∗ garante−se que a nao eh nulo ∗) delta:= calcula delta (a , b, c) ; i f delta >= 0 then begin writeln (menor raiz (a , b, delta) , maior raiz (a , b, delta)) ; end else writeln (’raizes complexas’) ; end. Figura 9.12: Calculando ra´ızes de equac¸a˜o do segundo grau. begin (∗ programa principal ∗) ler (a , b, c) ; (∗ garante−se que a nao eh nulo ∗) writeln (menor raiz (a , b, calcula delta (a ,b, c)) , maior raiz (a , b, calcula delta (a ,b, c))) ; end. Figura 9.13: Calculando ra´ızes de equac¸a˜o do segundo grau. Terminamos aqui a primeira parte do curso, no qual as noc¸o˜es fundamentais sobre algoritmos esta˜o estabelecidas. Nos pro´ximos estudaremos as principais estruturas de dados ba´sicas para um curso introduto´rio de algoritmos. 124 CAPI´TULO 9. FUNC¸O˜ES E PROCEDIMENTOS 9.5 Exerc´ıcios 1. Fazer uma func¸a˜o em Pascal que receba como paraˆmetro dois nu´meros intei- ros na˜o nulos e retorne TRUE se um for o contra´rio do outro e FALSE em caso contra´rio. Isto e´, se os paraˆmetros forem 123 (cento e vinte e treˆs) e 321 (trezentos e vinte e um), deve-se retornar TRUE. Usar apenas operac¸o˜es sobre inteiros. 2. Fazer uma func¸a˜o em Pascal que receba como paraˆmetro um nu´mero inteiro representando um nu´mero bina´rio e retorne seu valor equivalente em decimal. Por exemplo, se a entrada for 10001, a sa´ıda deve ser 17. 3. Fazer uma func¸a˜o em Pascal que receba como paraˆmetro um nu´mero inteiro e retorne TRUE se ele for primo e FALSE em caso contra´rio. Use esta func¸a˜o para imprimir todos os nu´meros primos entre 0 e 1000. 4. Implemente func¸o˜es para seno e cosseno conforme definidos em cap´ıtulos an- teriores e use-as em uma terceira func¸a˜o que calcule a tangente. O programa principal deve imprimir os valores de tg(x) para um certo valor fornecido pelo usua´rio. 5. Implemente um procedimento para gerar mais de um milha˜o de nu´meros inteiros. Os nu´meros gerados devera˜o ser impressos em um arquivo texto. 6. Fac¸a uma func¸a˜o em Pascal que some dois nu´meros representando horas. A entrada deve ser feita da seguinte maneira: 12 52 7 13 A sa´ıda deve ser assim: 12:52 + 7:13 = 20:05 7. Fac¸a uma func¸a˜o que receba como paraˆmetros seis varia´veis DIA1, MES1 e ANO1, DIA2, MES2 e ANO2, todas do tipo integer. Considerando que cada trinca de dia, meˆs e ano representa uma data, a func¸a˜o deve retornar true se a primeira data for anterior a` segunda e false caso contra´rio. Cap´ıtulo 10 Estruturas de dados Ate´ aqui apresentamos as te´cnicas ba´sicas para construc¸a˜o de algoritmos, incluindo as noc¸o˜es de func¸o˜es e procedimentos. Podemos dizer que e´ poss´ıvel, com este conteu´do, programar uma vasta colec¸a˜o de algoritmos, inclusive alguns com alta complexidade. Contudo, o estudo geral da disciplina de “Algoritmos e Estrurutas de Dados” envolve algoritmos que trabalham dados organizados em memo´ria de maneira mais sofisticada do que as simples varia´veis ba´sicas que foram estudadas ate´ o momento. E´ algo mais ou menos parecido como manter um guarda-roupas organizado no lugar de um monte de coisas atiradas no meio do quarto de qualquer jeito. A organizac¸a˜o de dados em memo´ria permite a construc¸a˜o de algoritmos sofistica- dos e eficientes. Neste textp estudaremos treˆs estruturas de dados elementares. Sa˜o elas: • vetores (ou array unidimencional); • matrizes (ou array multidimencional); • registros. Nas sec¸o˜es seguintes explicaremos cada uma delas, sempre motivados por proble- mas que exigem seu uso ou que facilitam a implementac¸a˜o. Tambe´m veremos nos pro´ximos cap´ıtulos algumas estruturas que misturam estas treˆs. 10.1 Vetores Para motivar, vamos considerar o problema seguinte: ler uma certa quantidade de valores inteiros e os imprimir na ordem inversa da leitura. Isto e´, se os dados de entrada forem: 2, 5, 3, 4, 9, queremos imprimir na sa´ıda: 9, 4, 3, 5, 2. Este tipo de problema e´ imposs´ıvel de ser resolvido com o uso de apenas uma varia´vel pois, quando se leˆ o segundo nu´mero, ja´ se perdeu o primeiro da memo´ria. Exigiria o uso de tantas varia´veis quantos fossem os dados de entrada, mas notem que isto deve ser conhecido em tempo de compilac¸a˜o! O que faz com que simplesmente na˜o seja poss´ıvel resolver este problema para uma quantidade indefinida de valores. 125 126 CAPI´TULO 10. ESTRUTURAS DE DADOS De fato, quando se aloca, por exemplo, um nu´mero inteiro em uma varia´vel de nome a, o que ocorre e´ que o computador reserva uma posic¸a˜o de memo´ria em algum enderec¸o da RAM (conforme sabemos pelo modelo Von Neumann). Um inteiro exige (dependendo da implementac¸a˜o) 2 bytes. Mas, digamos que e´ preciso alocar espac¸o para 100 nu´meros inteiros. Sabendo que cada um deles ocupa 2 bytes, precisar´ıamos encontrar uma maneira de reservar 100 × 2 = 200 bytes e fazer com que este espac¸o de memo´ria pudesse ser acessado tambe´m por um u´nico enderec¸o, ou em outras palavras, por uma u´nica varia´vel. Os vetores sa˜o estruturas de dados que permitem o acesso a uma grande quantidade de dados em memo´ria usando-se apenas um nome de varia´vel. Esta varia´vel especial e´ declarada de tal maneira que o programador passa a ter acesso a` muitas posic¸o˜es de memo´ria, de maneira controlada. Sem ainda entrar em detalhes da linguagem Pascal, vamos tentar entender o pro- cesso. Como funciona isto em memo´ria? Seguindo no exemplo de se alocar 200 espac¸os em memo´ria para nu´meros inteiros, suponhamos que o seguinte comando faz esta alocac¸a˜o: var V: array[1. .200] of integer ; Em Pascal isto resulta na alocac¸a˜o de 200 vezes 2 bytes. Pela varia´vel V temos o controle deste espac¸o. O problema e´ como se faz para se escrever um valor qualquer neste espac¸o. Outro problema e´ onde se escreve, ja´ que temos 200 possibilidades de escolha. O simples uso da varia´vel, como esta´vamos acostumados, na˜o serve. E´ preciso uma outra informac¸a˜o adicional para se dizer em qual das 200 posic¸o˜es se quer escrever. Na verdade, a varia´vel V aponta para o in´ıcio do segmento reservado, da mesma maneira que se fazia para varia´veis ba´sicas ja´ estudadas. Para se escrever em algum lugar deste segmento, e´ preciso informar, ale´m do nome da varia´vel, uma segunda informac¸a˜o: a posic¸a˜o (ou o deslocamento) dentro do espac¸o reservado. Ora, sabemos que foram reservadas 200 posic¸o˜es, cada uma delas com espac¸o para conter um nu´mero inteiro. Se quisermos escrever na quinta posic¸a˜o, basta informar ao computador que o in´ıcio do segmento e´ dado pela varia´vel V e que, antes de se escrever, e´ preciso realizar um deslocamento de 5 posic¸o˜es, cada uma delas para um inteiro. Isto da´ um deslocamento de 10 bytes. Apo´s esta informac¸a˜o, o valor pode ser escrito. Se o desejo e´ escrever na de´cima quarta posic¸a˜o, o deslocamento deve ser de 14× 2 bytes, isto e´, 28 bytes. Para se recuperar a informac¸a˜o, por exemplo para se imprimir, ou para se fazer algum ca´lculo com estes dados, basta usar o mesmo processo: os dados sa˜o acessados pelo nome da varia´vel e pelo deslocamento. Este processo foi apresentado em muito baixo n´ıvel. Como de costume, precisamos de uma outra forma de representac¸a˜o de mais alto n´ıvel. Isto e´, cada linguagem de 10.1. VETORES 127 programac¸a˜o que implementa a noc¸a˜o de vetores tem que encontrar