Algoritmos e Estruturas de Dados I – Arquivos

Algoritmos e Estruturas de Dados I – Arquivos

Profa. Mercedes Gonzales Márquez

ArquivosArquivos

Armazenamento de grandes quantidades de informação por um grande período de tempo. Exemplos:

A companhia telefónica precisa guardar informações sobre seus assinantes.

Informações armazenadas na Receita Federal sobre os contribuintes.

ArquivosArquivos

Arquivo é um conjunto de registros armazenados em um dispositivo de memória secundária.

Registro é um conjunto de unidades de informação logicamente relacionadas. Cada unidade de informação constitui um campo do registro.

Exemplo Arquivo de biblioteca : Cada livro é catalogado por meio de um registro, e o conjunto de registros corresponde ao acervo de livros da biblioteca.

ArquivosArquivos Ficha catalográfica (Registro)

Conjunto de fichas catalográficas (arquivo)

Código do livro:___________________________________Título:___________________________________________Autor:___________________________________________Assuntos:________________________________________Editora:________________________Ano:______________




ArquivosArquivos

(a) Definição do registro que compõe o arquivo(b) Definição do tipo construído arquivo(c) Declaração de variáveis (de registro,de arquivo,outras)

Definição do tipo construído arquivo:Tipo <identif_arquivo> = arquivo composto de tipo

<identif_registro> Declaração de variável composta do tipo arquivo definidoTipo-arquivo : nome_variável

ArquivosArquivosExemplo biblioteca

Definição do registro que compõe o arquivoTipo livro = registrointeiro: codigo,anoliteral: titulo,autor,assunto,editorafim registro

Definição do arquivoTipo arqlivro=arquivo composto de livro

Declaração de variáveislivro:ficha variável de registroarqlivro:biblos variável de arquivo

ArquivosArquivos Exemplo2: Fichário dos associados de um clube que

utiliza a seguinte ficha de cadastro.

tipo socio=registroliteral: nome,datanasc,naturalidade,nacionalidade,endereço,bairro,cidade,estado,dataadesãointeiro:RG,CPF,Fone,nrodependlógico:sexofim registrotipo arqsocio=arquivo composto de sociosocio:regsocioarqsocio:clube

Nome:_______________________________________________________RG:_________CPF:_________________Sexo:__Masculino __FemininoData Nascimento:_______Naturalidade:_______Nacionalidade_________Endereço:_________________________Bairro:_____________________Cidade:____________________Estado:____________Fone:___________Data Adesão:________________No dependentes:___________________

ArquivosArquivos Manipulação:

Diante de um arquivo de livros por exemplo podemos ter apenas dois tipos de atitudes:

(a) No caso de ser um leitor: procura a informação sobre a localização de certo livro através das fichas que registram o acervo.

(b) No caso de ser funcionário (da biblioteca): manipulação de diferentes formas como inserir, modificar e remover alguma informação sobre algum livro.

ArquivosArquivos Algoritmos básicos para consulta e/ou manipulação de

alguma informação no arquivo

Consultar Arquivo1. Abrir gaveta do arquivo2. Achar ficha procurada3. Copiar informações da ficha4.Fechar gaveta do arquivo

Acrescentar dados1. Abrir gaveta do arquivo2. Achar posição de inserção3. Guardar ficha nova4.Fechar gaveta do arquivo

Modificar dados1. Abrir gaveta do arquivo2. Achar ficha procurada3. Alterar os dados da ficha4.Fechar gaveta do arquivo

Eliminar dados1. Abrir gaveta do arquivo2. Achar a ficha procurada3. Retirar a ficha do arquivo4.Fechar gaveta do arquivo

ArquivosArquivos

Exercício:Dado o arquivo CADASTRO com registros com os campos NOME,SEXO,COR-DE-OLHOS,ALTURA, PESO E DATA-DE-NASCIMENTO, separá-los em dois arquivos: um chamado HOMENS, com registros cujo campo SEXO apresente o valor 1 (sexo masculino), e outro chamado MULHERES, com registros cujo campo SEXO seja igual a 2. Os registros dos novos arquivos deverão possuir os seguintes campos: NOME, COR-DE-OLHOS, ALTURA, PESO E DATA-DE-NASCIMENTO.

(1) Defina os tipos registro chamados regcad1 e regcad2; e os tipos arquivo arqcad1 e arqcad2 e as variáveis necessárias.(2) Faça o algoritmo que complete a tarefa solicitada.

Arquivos- operações básicasArquivos- operações básicasAbrindo um arquivo: Não podemos obter uma informação contida em um arquivo sem antes abri-lo. Isto é feito pelo comandoAbra (Identif_arquivo)onde: Identif_arquivo representa o identificador da variável arquivo previamente definida.Exemplo: abra(biblos)

Fechando um arquivo:Não é recomendável manter um arquivo aberto depois de usá-lo, pois isso deixaria seu conteúdo exposto a agentes externos. Para fechar os arquivos após sua utilização usamos:Fecha(Identif_arquivo)Exemplo: fecha(biblos)

ArquivosArquivos

Copiando um registro de arquivo: Um arquivo não deve ser consumido (no sentido de

retirar informação dele) e sim consultado. Para tal, é necessário copiar o conteúdo que nos interessa em algum lugar. Usa-se o comando

copie (identif_arquivo, identif_registro)identif_arquivo: Representa o identificador de variável

arquivo previamente definidaidentif_registro: Representa o identificador de variável

registro de formato igual àquele que compõe o arquivo.Exemplocopie(biblos,ficha)

ArquivosArquivosGuardando um registro: Para guardar um registro no arquivo é necessário que este tenha a mesma estruturação de campos que os registros já armazenados. Usa-se o comando,guarde(identif_arquivo,identif_registro)Exemplo:guarde(biblos,ficha)Guarda-se a informação do registro para a posição atual do arquivo.

Eliminando um registro: Para eliminação de informações indesejadas usamoselimine(id_arquivo)Exemplo: elimine(biblos)Elimina-se o registro na posição corrente do arquivo.

ArquivosArquivos Organização de arquivos:

Seqüencial Direta

Organização Sequencial Registros armazenados contiguamente, um após o

outro. Para acessar um registro específico precisamos

obedecer a sua ordem de gravação, o que significa percorrer todos os registros que o antecedem.

A tarefa de acesso é auxiliada pelos comandos Avance Fda (fim de arquivo)

ArquivosArquivos

avance(identif_arquivo)Esse comando coloca o arquivo na posição

consecutiva ou seja, no próximo registro. Se utilizado repetidas vezes permite percorrer o arquivo passando por uma série consecutiva de registros.

Fda (identif_arquivo)Esse comando retorna verdadeiro quando a posição

atual é o fim do arquivo e falso, caso contrário.

ArquivosArquivos Exercício:Faça um algoritmo que guarde um novo telefone em

um arquivo sequencial (Inserção)algoritmo<inserção_telefone>tipo pessoa : registroliteral:nomeinteiro:fonefim registrotipo pessoal=arquivo composto de pessoapessoa:auxpessoal:agendaInicioabra(agenda)repita avance(agenda)até fda(agenda)leia (aux.nome,aux.fone)guarda(agenda,aux)fecha(agenda)fim

ArquivosArquivos Observações:

Sempre que o comando abra é executado, a posição corrente do arquivo é o primeiro registro.

O comando guarda armazena o registro na posição corrente do arquivo que, no exemplo, é a última posição.

Vejamos o caso de uma consulta no mesmo arquivo Como não se conhece a posição da informação

procurada no arquivo, vasculha-se o arquivo partir do início. Se o final de arquivo for alcançado e a informação não for encontrada, conclui-se que esta não existe.

ArquivosArquivosalgoritmo<consulta_telefone>tipo pessoa : registroliteral:nomeinteiro:fonefim registrotipo pessoal=arquivo composto de pessoapessoa:auxpessoal:agendaliteral:nome_procuradoInicioabra(agenda)leia (nome_procurado)repita copie(agenda,aux) avance(agenda)até (aux.nome=nome_procurado) ou (fda(agenda))se (aux.nome=nome_procurado) então

escreva (aux.fone)senão escreva(“telefone não registrado”)fecha(agenda)fim

ArquivosArquivos

Observações: Não deve-se, apenas, avançar pelos registros para

verificar a coincidência do campo nome, é preciso copiar para um registro auxiliar cada um dos registros armazenados.

Exercício: Utilizando o tipo de arquivo arqLivro já apresentado, elabore um algoritmo que permita ao leitor obter uma relação de livros que a biblioteca dispõe sobre determinado assunto.

ArquivosArquivos

• Suponhamos que alguém já cadastrado mude o telefone, temos então que localizar seu registro correspondente, copiar seu conteúdo a um registro auxiliar e então alterar o campo fone.

• Depois basta gravar as informações atualizadas na mesma posição em que se encontrava antes, ou seja, gravar o registro atualizado “por cima” do antigo.

• Vejamos o caso de uma alteração de dados no mesmo arquivo

ArquivosArquivosalgoritmo<modifica_telefone>

tipo pessoa : registro

literal:nome

inteiro:fone

fim registro

tipo pessoal=arquivo composto de pessoa

pessoa:aux

pessoal:agenda

literal:nome_procurado

inteiro:novofone

Inicio

abra(agenda)

leia (nome_procurado)

copie(agenda,aux)

enquanto (aux.nome<>nomeprocurado

e não(fda(agenda))) faça

avance(agenda)

copie (agenda,aux)

fim enquanto

se (aux.nome=nome_procurado) então escreva (aux.fone) escreva (“Novo telefone”) leia (novofone) aux.fone←novofone guarde(agenda,aux)senão escreva(“telefone não registrado”)Fim se

fecha(agenda)Fim


Tomar cuidado de não avançar a posição corrente depois de ter encontrado o registro, pois devemos, após da atualização, de regravá-lo na mesma posição.

É conveniente apresentar para o usuário as informações que vão ser modificadas.

Vejamos o caso de uma eliminação de registro no mesmo arquivo Se quisermos excluir algum telefone arquivado devemos

primeiro localizar o registro para então eliminá-lo após uma confirmação.

ArquivosArquivosalgoritmo<elimina_telefone>


literal:nome

inteiro:fone

fim registro


pessoa:aux

pessoal:agenda

literal:nome_procurado,confirmacao

Inicio

Abra (agenda)

Leia (nome_procurado)

Copie (agenda,aux)

Enquanto (aux.nome<>nome_procurado e não (fda(agenda)) faça

Avance (agenda)

Copie (agenda,aux)

Fim enquanto

se (aux.nome=nome_procurado) então escreva (aux.nome,aux.fone)

escreva (“Confirma exclusão (S/N)?”) leia (confirmacao) se (confirmacao=”S”) então elimine(agenda)senão escreva(“telefone não registrado”)Fim sefecha(agenda)fim


Tomar cuidado de não avançar a posição corrente depois de ter encontrado o registro, pois será o registro da posição corrente que será eliminado.

É conveniente solicitar uma confirmação da exclusão para evitar perdas irreparáveis.

Exercício2: Utilizando o tipo de arquivo arqLivro já apresentado, elabore um algoritmo destinado ao usuário de categoria funcionário para possibilitar qualquer espécie de manipulação dos dados apartir de um código do livro (inserção, consulta, modificação, eliminação). Faça um menú de opções.

ArquivosArquivos

Exercício3: Uma instituição de pesquisa recolheu amostras em três regiões. Cada amostra constitui um registro com os seguintes componentes: sexo, idade, salário, estado civil, número de dependentes, valor do patrimônio, quantidade de calorias absorvidas por dia, grau de instrução. Em cada região, os dados foram armazenados em um arquivo sequencial, sendo os registros colocados em ordem crescente de idade. Escrever um algoritmo que intercale estes arquivos de modo que o arquivo resultante permaneça ordenado.

ArquivosArquivosalgoritmo<intercala_registros>


literal:sexo

inteiro:idade,nrodep,valorp,grau

real: salário

fim registro


pessoa:aux1,aux2,aux3

pessoal:regiao1,regiao2,regiao3,saida

inteiro:menoridade,narquivo

Inicio

Abra (regiao1)

Copie (regiao1,aux1)

Abra (regiao2)


Abra (regiao3)


Enquanto (!fda(regiao1) ou !fda(regiao2)

ou !fda(regiao3)) faça

menoridade<- 9999

se (aux1.idade<menoridade e !fda(regiao1)

menoridade<-aux1.idade

narquivo<-1

fim se

se ...

se (narquivo=1) então

guarde (aux1,saida)

avance(regiao1)

copie(regiao1,aux1)

avance(saida)

senão

ArquivosArquivos

Exercício4: A seção de controle de produção de uma fábrica mantém um arquivo de registros de produção por máquinas. Cada registro contém o número da máquina e o número de peças produzidas em um dia. Supondo que a fábrica possua três máquinas, escreva um algoritmo que separe o arquivo em três outros arquivos, um para cada máquina.

ArquivosArquivos Organização Direta

– Também chamada de acesso aleatório.– Vá diretamente ao registro desejado usando uma chave:– O computador não precisa ler todos os registros anteriores. Ou

seja, através do campo podemos determinar o lugar onde o registro está guardado, podendo acessá-lo de forma instantânea sem nos preocupar com seus antecessores.

– Um algoritmo de randomização (hashing) é usado para determinar o endereço de uma chave específica.

– A chave deve ser única pois nunca podemos armazenar dois registros diferentes em uma mesma localização.

– Exemplo: Um professor deseja armazenar o nome do aluno e suas quatro notas (bimestrais), então usa como chave o código de chamada do aluno (o qual é único).

ArquivosArquivos Algoritmo de Randomização (Hashing)Aplica uma fórmula matemática à chave para determinar o endereço de determinado registro. Ocorre colisão quando o algoritmo de randomização produz o mesmo endereço em disco para duas chaves diferentes.

ArquivosArquivos

ArquivosArquivos Para que a posição corrente do arquivo passe a ser a

indicada pela chave usamos o comandoposicione (IdArquivo, CHAVE)onde:IdArquivo:Representa o identificador de variável de arquivo

previamente definida.CHAVE: é um inteiro que indica a posição corrente desejada.

ArquivosArquivos Exercício:Faça um algoritmo que guarde um novo aluno em um arquivo

de organização direta (Inserção)

algoritmo<inserção_aluno>

tipo aluno : registro

literal:nome

inteiro:numero

inteiro:Nota[4]

fim registro

tipo sala=arquivo composto de aluno

aluno:aux

sala:diario

inteiro:i

Inicio

abra(diario)

repita

leia (aux.numero)

se (aux.numero>0) então

leia (aux.nome)

Para i de 1 até 4 repita

leia (aux.Nota[i])

Fim para

posicione (diario, aux.numero)

guarde (diario,aux)

fim se

até (aux.numero=0)

fecha(diario)

Fim

ArquivosArquivos Consultando registros em forma direta

algoritmo<consulta_aluno>tipo aluno : registroliteral:nomeinteiro:numerointeiro:Nota[4]fim registrotipo sala=arquivo composto de alunoaluno:auxsala:diariointeiro:numeroaluno

Início

abra(diario)

leia (numeroaluno)

posicione (diario, numero.aluno)

copie(diario,aux)

escreva(aux.nome,”possui notas”,aux.Nota[1],

aux.Nota[2], aux.Nota[3],aux.Nota[4])

fecha(diario)Fim

Observe que não foi necessário fazer a pesquisa por todos os registros do arquivo já

que o registro desejado pode ser acessado diretamente, ou seja, sem precisar que

nenhum outro registro fosse acessado.

ArquivosArquivos Alteração no arquivo de acesso

diretoalgoritmo<altera_aluno>tipo aluno : registroliteral:nomeinteiro:numerointeiro:Nota[4]fim registrotipo sala=arquivo composto de alunoaluno:auxsala:diariointeiro:numeroaluno,qualnotareal:nota

Início

abra(diario)

leia (numeroaluno,qualnota)

posicione (diario, numeroaluno)

copie(diario,aux)

se (qualnota=1) então

nota←aux.Nota[1]

senão


nota←aux.Nota[2]

senão


nota←aux.Nota[3]

senão se(qualnota=4) então

nota←aux.Nota[4]

escreva(aux.nome,”possui nota”,qualnota,”=”,nota)

escreva (“Nova Nota”)

leia (nota)

aux.Nota[qualnota]←nota

guarde(diario,aux)

fecha(diario)Fim

ArquivosArquivos Exercício:Eliminação em um arquivo de organização direta

ArquivosArquivos Acesso Direto em um arquivo sequencial

Um arquivo concebido sequencialmente foi preenchido na mesma sequencia em que as informações foram surgindo.

Ele se torna inconveniente quando cresce muito e os acessos se tornam muito frequentes. Deve-se fazer uma busca exaustiva para cada operação de inclusão, alteração ou exclusão.

Este problema pode ser contornado pelo conceito de arquivo indexado: Para isso deve-se criar um arquivo Para isso deve-se criar um arquivo auxiliar (índice) que contém as chaves e o endereço do auxiliar (índice) que contém as chaves e o endereço do registro correspondente no arquivo principal (dados).registro correspondente no arquivo principal (dados).


Exemplo: Num banco de dados, para cada arquivo de Num banco de dados, para cada arquivo de dados, podemos ter um ou mais índices, dependendo dos dados, podemos ter um ou mais índices, dependendo dos valores de chave para ser utilizados. Um arquivo de valores de chave para ser utilizados. Um arquivo de clientes poderia ser classificado por ordem alfabética ou clientes poderia ser classificado por ordem alfabética ou pelo número do CPF do cliente. Para satisfazer as duas pelo número do CPF do cliente. Para satisfazer as duas chaves, seriam criados então dois arquivos de índices: um chaves, seriam criados então dois arquivos de índices: um tendo o nome e o outro tendo o CPF como chave de tendo o nome e o outro tendo o CPF como chave de classificação.classificação.


Exemplo: Uma empresa fundada em 1985 registra seus funcionários à medida que estes são contratados, tendo, portanto, uma concepção sequencial, com o seguinte registro:

Nome: _____________________________________________Endereço: _________________________CPF:____________Telefone: __________ Bairro: ______________CEP:_______Ano de admissão:_______ Ano de demissão: _____________Estado Civil: ___________ No de dependentes: ___________Salário base: ___________ Cargo: __________ Setor: ______

ArquivosArquivosCriamos um novo arquivo que possua um campo-chave. Esse novo campo tem 7 dígitos e é estruturado: os quatro primeiros representam o ano de admissão, os dois seguintes, o setor e o último, um sequencial do setor, que não fazia parte do arquivo antigo.

Utilizaremos um arquivo de acesso direto que empregue como chave o código de funcionário subtraído de 1985000; assim, o funcionário 1985001 está armazenado na posição 1, o 1985002 na posição 2 e assim por diante. Em cada posição também será armazenada a posição do funcionário no arquivo principal.

Código Posição Nome Endereço ...

1985001 2

1985002 3

1985003 m

1985004 1

1985005 4

...

ttttt 5

XXW TRUJ

HJU DLLD

KJU LOIO

ZUH DEFS

FSW SWQA

...

KFK FJSD

1

2

1

3

4

5

2

3

4

5

m

Documents

Algoritmos e Estruturas de Dados I – Arquivos