apostila
259 pág.

apostila


DisciplinaAlgoritmos e Estrutura de Dados I674 materiais7.931 seguidores
Pré-visualização50 páginas
) ;
end;
Figura 10.60: Lendo os clientes do banco.
Os algoritmos para busca, ordenac¸a\u2dco e outros tipos de manipulac¸a\u2dco 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\u2dco e´ no campo r.cpf que devemos centrar atenc¸a\u2dco 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 (\u2019O telefone do cliente \u2019 ,v[ i ] .nome,\u2019 eh o \u2019 ,v[ i ] . fone)
else
writeln (\u2019Cliente nao localizado na base.\u2019) ;
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\u2dco se dara´ pelo CPF do cliente. O algoritmo de ordenac¸a\u2dco pode
ser, por exemplo, o me´todo da selec¸a\u2dco. 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\u2dco.
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\u2dco. Observar tambe´m que se a chave
da ordenac¸a\u2dco for outra, por exemplo, o nome do cliente, deve-se implementar outra
procedure, mudando-se o co´digo na linha da comparac¸a\u2dco de v[i].cpf para v[i].nome.
10.3.3 Registros com vetores
Na sessa\u2dco anterior vimos como implementar um vetor cujos campos sa\u2dco registros.
Nesta sessa\u2dco vamos ver como implementar um registro que tem, com um dos campos,
um vetor. Para isto, vamos considerar as seguintes definic¸o\u2dces:
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\u2c6metros, entre outras coisas. Em uma figura de linguagem, e´ como
se o vetor \u201csoubesse\u201d seu tamanho, sem precisar passar um para\u2c6metro 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´\u131mbolos de ponto (.) e dos colchetes,
eles te\u2c6m 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\u2dco a construc¸a\u2dco e´ v.tam. Se
quisermos acessar o vetor de reais, enta\u2dco a construc¸a\u2dco correta e´ v.dados. Ocorre que
v.dados e´ um vetor, logo, deve-se indexar com algum inteiro, por isto a construc¸a\u2dco
final correta e´ v.dados[i].
10.3.4 Observac¸o\u2dces importantes
O estudante e´ encorajado a praticar va´rios exerc´\u131cios ate´ compreender bem estas
noc¸o\u2dces. Uma vez compreendido, na\u2dco havera´ dificuldades em prosseguir no estudo
de algoritmos e estruturas de dados. A maior parte das estruturas sofisticadas que
sera\u2dco estudadas ao longo dos pro´ximos anos de estudo sa\u2dco variantes das construc¸o\u2dces
estudadas nesta sec¸a\u2dco.
Nas u´ltimas aulas desta disciplina abordaremos problemas que podem ser resol-
vidos de forma elegante usando-se uma combinac¸a\u2dco de vetores, registros, matrizes e
tambe´m, obviamente, os tipos ba´sicos. Afinal, como estamos querendo mostrar desde
o in´\u131cio 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\u22121 do
begin
(\u2217 acha o menor elemento a partir de i \u2217)
pos menor:= i ;
for j:= i+1 to n do
if v[ j ] . cpf < v[pos menor ] . cpf then
pos menor:= j ;
(\u2217 troca \u2217)
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´\u131cios
1. Latitude e longitude sa\u2dco especificados em graus, (o), minutos (\u2019), segundos (\u201d),
e direc¸a\u2dco (N, S, L, O). Por exemplo, a cidade A fica na latitude 22o17\u201934\u201dN e
longitude 53o41\u20199\u201dO.
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\u2dco 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\u2c6metros para nome, DDD, tele-
fone, CPF, Idade e o insira no vetor (que ja´ esta´ ordenado) em ordem alfabe´tica.
Na\u2dco vale usar um vetor auxiliar. Retornar por refere\u2c6ncia o vetor alterado
7. Considere o arquivo de uma empresa (chamado de \u201cfunc.dat\u201d \u2013 um arquivo de
registros) contendo para cada funciona´rio seu nu´mero, seu n´\u131vel salarial e seu de-
partamento. Como a administrac¸a\u2dco desta empresa e´ feita a n´\u131vel 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\u2dco frequentes as mudanc¸as interdepartamentais no quadro de funciona´rios, na\u2dco
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 \u201cdepto.dat\u201d \u2013 um arquivo de registros) temos
as seguintes informac¸o\u2dces:
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\u2dco
obtidos seguindo o campo proximo. Ou seja, os funciona´rios do departamento
de vendas sa\u2dco os funciona´rios nos registros: 0, 5, 9, 10 e 1. Os funciona´rios do
departamento de contabilidade sa\u2dco os funciona´rios nos registros: 8, 11 e 4.
Escreva um programa