apostila
259 pág.

apostila

Disciplina:Algoritmos e Estrutura de Dados I542 materiais7.956 seguidores
Pré-visualização50 páginas
) ;
end;

Figura 10.60: Lendo os clientes do banco.

Os algoritmos para busca, ordenac¸a˜o e outros tipos de manipulac¸a˜o desta nova
estrutura devem levar em conta agora qual e´ o campo do registro que deve ser utilizado.
Por exemplo, se quisermos imprimir o telefone do cliente do banco cujo CPF seja
1234567899, enta˜o e´ no campo r.cpf que devemos centrar atenc¸a˜o durante a busca,
mas na hora de imprimir, deve-se exibir o campo r.fone. Vejamos um exemplo na
figura 10.61.

212 CAPI´TULO 10. ESTRUTURAS DE DADOS

procedure busca telefone (var v: bd; tam v: integer ; nome procurado: string) ;
var i : integer ;
begin

i := 1;
while ( i <= tam v) and (v[ i ] .nome<> nome procurado) do

i := i + 1;
i f i <= tam v then

writeln (’O telefone do cliente ’ ,v[ i ] .nome,’ eh o ’ ,v[ i ] . fone)
else

writeln (’Cliente nao localizado na base.’) ;
end;

Figura 10.61: Imprime o telefone do cliente que tem um certo CPF.

O campo do registro de interesse para um algoritmo normalmente e´ denominado
chave. Por exemplo, vamos tentar ordenar o banco de dados. Por qual chave devemos
fazer isto, ja´ que temos uma estrutura contendo 7 campos diferentes? Vamos conven-
cionar que a ordenac¸a˜o se dara´ pelo CPF do cliente. O algoritmo de ordenac¸a˜o pode
ser, por exemplo, o me´todo da selec¸a˜o. Mas deve-se observar que, durante as trocas,
todo o registro deve ser trocado, sob pena de misturarmos os dados dos clientes! A
figura 10.62 ilustra tal situac¸a˜o.

O ideal e´ que se implemente um procedimento para as trocas, assim o co´digo
fica encapsulado e e´ mais fa´cil dar manutenc¸a˜o. Observar tambe´m que se a chave
da ordenac¸a˜o for outra, por exemplo, o nome do cliente, deve-se implementar outra
procedure, mudando-se o co´digo na linha da comparac¸a˜o de v[i].cpf para v[i].nome.

10.3.3 Registros com vetores

Na sessa˜o anterior vimos como implementar um vetor cujos campos sa˜o registros.
Nesta sessa˜o vamos ver como implementar um registro que tem, com um dos campos,
um vetor. Para isto, vamos considerar as seguintes definic¸o˜es:

const MAX= 10000;
type vetor = array [ 1 . .MAX] of real ;

tipo vetor = record
tam: integer ;
dados : vetor ;

end;

var v: tipo vetor ;

A ideia e´ encapsular o tamanho do vetor junto com o pro´prio vetor. Isto facilita na
hora de passar paraˆmetros, entre outras coisas. Em uma figura de linguagem, e´ como
se o vetor “soubesse” seu tamanho, sem precisar passar um paraˆmetro indicando isto.

O conceito e´ simples, vamos ver pode ser feita a leitura de um vetor nesta nova
estrutuda de dados. Isto e´ apresentado na figura 10.63.

E´ importante observar o correto uso dos s´ımbolos de ponto (.) e dos colchetes,
eles teˆm que estar no lugar certo. Uma vez que, no exemplo acima, v e´ uma varia´vel

10.3. REGISTROS 213

do tipo registro, ela deve receber inicialmente um ponto para se poder acessar um
dos dois campos. Se quisermos acessar o tamanho, enta˜o a construc¸a˜o e´ v.tam. Se
quisermos acessar o vetor de reais, enta˜o a construc¸a˜o correta e´ v.dados. Ocorre que
v.dados e´ um vetor, logo, deve-se indexar com algum inteiro, por isto a construc¸a˜o
final correta e´ v.dados[i].

10.3.4 Observac¸o˜es importantes

O estudante e´ encorajado a praticar va´rios exerc´ıcios ate´ compreender bem estas
noc¸o˜es. Uma vez compreendido, na˜o havera´ dificuldades em prosseguir no estudo
de algoritmos e estruturas de dados. A maior parte das estruturas sofisticadas que
sera˜o estudadas ao longo dos pro´ximos anos de estudo sa˜o variantes das construc¸o˜es
estudadas nesta sec¸a˜o.

Nas u´ltimas aulas desta disciplina abordaremos problemas que podem ser resol-
vidos de forma elegante usando-se uma combinac¸a˜o de vetores, registros, matrizes e
tambe´m, obviamente, os tipos ba´sicos. Afinal, como estamos querendo mostrar desde
o in´ıcio do nosso estudo, a arte de se programar um computador e´ simplesmente encon-
trar as melhores estruturas de dados que, bem exploradas pelos algoritmos corretos,
levam a programas eficientes e elegantes.

214 CAPI´TULO 10. ESTRUTURAS DE DADOS

procedure ordena por cpf (var v: bd; n: integer) ;
var i , j , pos menor: integer ;

aux: cliente ;

begin
for i := 1 to n−1 do
begin

(∗ acha o menor elemento a partir de i ∗)
pos menor:= i ;
for j:= i+1 to n do

if v[ j ] . cpf < v[pos menor ] . cpf then
pos menor:= j ;

(∗ troca ∗)
with aux do
begin

nome:= v[pos menos ] .nome;
fone:= v[pos menor ] . fone ;
endereco:= v[pos menor ] . endereco ;
sexo:= v[pos menor ] . sexo ;
idade:= v[pos menor ] . idade ;
rg:= v[pos menor ] . rg ;
cpf:= v[pos menor ] . cpf ;

end;

with v[pos menor] do
begin

nome:= v[ i ] .nome;
fone:= v[ i ] . fone ;
endereco:= v[ i ] . endereco ;
sexo:= v[ i ] . sexo ;
idade:= v[ i ] . idade ;
rg:= v[ i ] . rg ;
cpf:= v[ i ] . cpf ;

end;

with v[ i ] do
begin

nome:= aux.nome;
fone:= aux.nome;
endereco:= aux.nome;
sexo:= aux.nome;
idade:= aux.nome;
rg:= aux.nome;
cpf:= aux. cpf ;

end;

Figura 10.62: Ordena pelo CPF.

10.3. REGISTROS 215

procedure ler vetor (var v: tipo vetor) ;
var i : integer ;

begin
readln (v.tam) ;
for i := 1 to v.tam do

readln (v.dados [ i ] )
end;

Figura 10.63: Lendo vetores implementados em registros.

216 CAPI´TULO 10. ESTRUTURAS DE DADOS

10.3.5 Exerc´ıcios

1. Latitude e longitude sa˜o especificados em graus, (o), minutos (’), segundos (”),
e direc¸a˜o (N, S, L, O). Por exemplo, a cidade A fica na latitude 22o17’34”N e
longitude 53o41’9”O.

Defina um tipo em Pascal cujo nome seja localizacao, e que seja constituido
de longitude e latitude, ambas do tipo coordenadas. Para isto voce tera´ que
definir o tipo coordenadas como sendo constituido de grau, minutos, segundos
e direcao.

2. Declare um vetor onde cada elemento e´ um registro com os campos: nome,
DDD, telefone, CPF, Idade.

3. Considerando o vetor na˜o ordenado, encontrar e imprimir o nome do cliente
mais jovem. Fac¸a um procedimento para isto

4. Ordenar por ordem de nome. Fac¸a um procedimento para isto.

5. Dado um CPF, localizar se o nome esta´ no vetor e imprimir todos os dados.
Fac¸a um procedimento para isto.

6. Fac¸a um procedimento que receba por valor paraˆmetros para nome, DDD, tele-
fone, CPF, Idade e o insira no vetor (que ja´ esta´ ordenado) em ordem alfabe´tica.
Na˜o vale usar um vetor auxiliar. Retornar por refereˆncia o vetor alterado

7. Considere o arquivo de uma empresa (chamado de “func.dat” – um arquivo de
registros) contendo para cada funciona´rio seu nu´mero, seu n´ıvel salarial e seu de-
partamento. Como a administrac¸a˜o desta empresa e´ feita a n´ıvel departamental
e´ importante que no arquivo os funciona´rios de cada um dos departamentos este-
jam relacionados entre si e ordenados sequencialmente pelo seu nu´mero. Como
sa˜o frequentes as mudanc¸as interdepartamentais no quadro de funciona´rios, na˜o
e´ conveniente reestruturar o arquivo a cada uma destas mudanc¸as. Desta ma-
neira, o arquivo poderia ser organizado da seguinte forma:

linha numFunc nivel departamento proximo

0 123 7 1 5

1 8765 12 1 -1

2 9210 4 2 -1

3 2628 4 3 6

4 5571 8 2 -1

5 652 1 1 9

6 7943 1 3 -1

7 671 5 3 12

8 1956 11 2 11

9 1398 6 1 10

10 3356 3 1 1

11 4050 2 2 4

12 2468 9 3 3

10.3. REGISTROS 217

Em um segundo arquivo (chamado “depto.dat” – um arquivo de registros) temos
as seguintes informac¸o˜es:

codDepto nomeDepto inicio

1 vendas 0

2 contabilidade 8

3 estoque 7

4 entrega 2

Assim, o primeiro funciona´rio do departamento de vendas e´ o registro 0 do
arquivo de funciona´rios e os demais funciona´rios do mesmo departamento sa˜o
obtidos seguindo o campo proximo. Ou seja, os funciona´rios do departamento
de vendas sa˜o os funciona´rios nos registros: 0, 5, 9, 10 e 1. Os funciona´rios do
departamento de contabilidade sa˜o os funciona´rios nos registros: 8, 11 e 4.

Escreva um programa