ALGORITMOS E ESTRUTURAS DE DADOS I
259 pág.

ALGORITMOS E ESTRUTURAS DE DADOS I


DisciplinaAlgoritmos e Estrutura de Dados I708 materiais7.919 seguidores
Pré-visualização50 páginas
do mesmo tipo.
Para completarmos nosso estudo ba´sico de algoritmos, resta ainda introduzir a
noc¸a\u2dco de registros, que sa\u2dco estruturas heteroge\u2c6nas, isto e´, pode-se alocar va´rias posic¸o\u2dces
de memo´ria cada uma delas de um tipo potencialmente diferente.
10.3.1 Introduc¸a\u2dco aos registros
Assim como em um vetor ou em uma matriz, pode-se acessar diversas posic¸o\u2dces de
memo´ria com um u´nico nome da varia´vel, o que e´ diferente e´ que com um registro
podemos misturar diversos tipos diferentes.
Por exemplo, suponhamos que seja necessa´rio implementar um cadastro de um
cliente em um banco. Normalmente, este cadastro conte´m: nome do cliente, telefone,
enderec¸o, sexo, idade, RG e CPF. Usando-se um registro, podemos agrupar todos os
dados diferentes em uma so´ varia´vel. Por exemplo, em Pascal podemos declarar tal
varia´vel assim:
var r : record
nome: string [50 ] ;
fone : longint ;
endereco : string ;
sexo : char;
idade , rg , cpf : integer ;
end;
Cada linguagem de programac¸a\u2dco tem sua sintaxe pro´pria para a declarac¸a\u2dco e acesso
aos dados. Nos vetores e matrizes, o acesso e´ feito usando-se o nome da varia´vel e um
\u131´ndice (ou um par no caso das matrizes). Para os registros, em Pascal, usa-se o nome
da varia´vel, um ponto, e o nome do campo, que e´ escolhido pelo programador.
Por exemplo, e´ va´lido em Pascal a seguinte seque\u2c6ncia de comandos:
r .nome:= \u2019Fulano de Tal\u2019 ;
r . fone:= 32145678;
r . endereco:= \u2019Rua dos bobos, no 0\u2019 ;
r . sexo:= \u2019M\u2019 ;
r . idade:= 75;
r . rg:= 92346539;
r . cpf:= 11122233344;
Tambe´m seria va´lido ler a partir do teclado da seguinte maneira:
read (r .nome) ;
read (r . fone) ;
read (r . endereco) ;
read (r . sexo) ;
read (r . idade) ;
read (r . rg) ;
read (r . cpf) ;
210 CAPI´TULO 10. ESTRUTURAS DE DADOS
Contudo, assim como se da´ para o tipo array, para se passar um para\u2c6metro de
procedimento ou func¸a\u2dco em Pascal e´ necessa´rio antes a declarac¸a\u2dco de um novo tipo,
que poderia ser assim:
type cliente = record
nome: string [50 ] ;
fone : longint ;
endereco : string ;
sexo : char;
idade : integer ;
rg : longint ;
cpf : qword;
end;
var r : cliente ;
Na verdade a linguagem Pascal permite uma facilidade para se economizar alguma
digitac¸a\u2dco atrave´s do comando with. A figura 10.59 ilustra uma forma de se imprimir
todo o conteu´do de um registro usando-se um procedimento. O comando with pode
ser usado para leitura ou atribuic¸a\u2dco tambe´m.
procedure imprime reg (r : cliente ) ;
begin
with r do
begin
writeln (nome) ;
writeln (fone) ;
writeln (endereco) ;
writeln (sexo) ;
writeln (idade) ;
writeln (rg) ;
writeln (cpf) ;
end;
end;
Figura 10.59: Imprimindo registros.
10.3.2 Vetores de registros
O leitor pode ter observado ou pensado: um registro na\u2dco faz um arquiva\u2dco. . .
De fato, normalmente e´ mais comum ver os registros integrados a outras estrututas,
tais como vetores, matrizes ou arquivos em disco11
Considerando ainda o exemplo do cliente do banco, e´ natural imaginar que o banco
tem muitos clientes. Claro, se tiver um so´, melhor fechar as portas. Uma maneira
ainda um pouco preca´ria de se manipular muitos clientes e´ usando a estrutura de
vetores em combinac¸a\u2dco com a de registros.
A t´\u131tulo de exemplo, consideremos enta\u2dco as seguintes definic¸o\u2dces:
11O tipo file esta´ fora do escopo desta disciplina no primeiro semestre de 2009.
10.3. REGISTROS 211
const MAX= 10000;
type cliente = record
nome: string [50 ] ;
fone : longint ;
endereco : string ;
sexo : char;
idade : integer ;
rg : longint ;
cpf : qword;
end;
bd = array [ 1 . .MAX] of cliente ;
var r : cliente ;
v: bd;
tam v: integer ;
Isto e´, temos um vetor de tam v clientes!
Vamos imaginar que o banco e´ novo na prac¸a e que e´ preciso criar o banco de dados
contendo os clientes. Podemos usar o procedimento que e´ mostrado na figura 10.60.
procedure ler cl iente (var r : cliente ) ;
begin
with r do
begin
readln (nome) ;
readln (fone) ;
readln (endereco) ;
readln (sexo) ;
readln (idade) ;
readln (rg) ;
readln (cpf) ;
end;
end;
procedure carregar todos clientes (var v: bd; var tam v: integer) ;
begin
readln (tam v) ;
for i := 1 to tam v do
ler cl iente (v[ i ] ) ;
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