organizacao_de_arquivos

Prévia do material em texto

Estrutura de dadosEstrutura de dados
OrganizaOrganizaçção de Arquivos ão de Arquivos 
20132013
Prof Melo
Apresentação
• Técnico em Desenvolvimento de Sistemas - Ibratec, Recife-PE
• Bacharel em Sistemas de Informação – FIR, Recife-PE
• Especialista em Docência no Ensino Superior – Faculdade 
Maurício de Nassau, Recife-PE
• Mestre em Ciência da Computação – UFPE/CIN, Recife-PE
• Currículo Lattes http://lattes.cnpq.br/0759508594425296)
• Homepage https://sites.google.com/site/hildebertomelo/
Disciplinas Lecionadas
• Desenvolvimento de Aplicações Desktop
• Programação Orientada a Objetos
• Estrutura de Dados
• Tecnologia da Informação & Sociedade
• Sistemas Operacionais
• Sistemas Distribuídos
• Introdução a Informática
• Lógica de Programação
• Informática Aplicada a Saúde
• Banco de Dados
• Projeto de Banco de Dados
• Análise de Projetos Orientado a Objetos
• Programação Cliente Servidor
• Linguagens de Programação: C, C#, Pascal, PHP, ASP, Delphi, Java, JavaScript
• Programação WEB
Conteúdo
• Definição
• Organização seqüencial
• Organização relativa
• Organização hashing
• Organização indexada
• Indexação de arquivos
–Memória principal
–Memória secundária
Organização de arquivos
• Forma ou método de 
armazenamentos dos registros em 
um arquivo
• Estrutura física de um arquivo. Forma 
como são gravados e recuperados 
registros nos mesmos
Organização seqüencial
• Organização básica de todo arquivo em 
um computador
• Consiste em gravar registros uns após os 
outros, sendo que novos registros são 
gravados no fim
Número Nome Data Nasc Salário
10130 Jose 25 07 50 1200
10850 Paulo 23 12 51 11000
12700 Pedro 10 06 53 7000
...
11600 Edison 05 03 47 9800
Organização relativa
• Organização física de um arquivo, onde os 
registros são gravados na posição relativa 
de uma chave de acesso
• Permite recuperação e gravação de 
registros com apenas uma leitura
• O valor da chave deverá ser numérico e 
não esparso
• Necessita de um campo extra para indicar 
se o registro é ou não válido
Organização relativa (cont.)
• Cada registro é colocado na posição 
relativa da chave no arquivo:
Cor Descrição Flag
1 Azul 1
2 Amarelo 1
0
4 Verde 1
5 Vermelho 1
0
0
8 Branco 1
… … …
Organização Hashing 
• Organização física de um arquivo, que 
utiliza uma função, hashing, que mapeia 
uma chave qualquer em um número 
inteiro e não espaso.
• Utiliza a organização relativa como base
• Necessita de rotina para tratamento de 
colisões
• Utiliza um campo a mais de controle para 
controlar uma lista de colisões
Organização Hashing (cont.)
• Cada registro é colocado na posição 
relativa do resultado da função 
hashing aplicada a chave:
CPF Nome Flag Prox
1111111111
1
Hildeberto 1
2222222222
2
Melo 1
0
3333333333
3
Jose 1
4444444444
4
Carlos 1
f(111111111)=0
f(222222222)=1
f(333333333)=3
f(444444444)=4
f(212121212)=6
Organização indexada 
• Organização de arquivo que utiliza uma estrutura de 
índices para agilizar o processo de pesquisa em um 
arquivo
• A estrutura de índices pode estar embutida no arquivo 
ou ser externa
• Utiliza a organização relativa como base de sua 
implementação
• Existem diversas implementação de índices, tais como, 
listar, árvores, híbrida, b-tree, etc
• As estruturas de índices armazenam a chave de 
pesquisa e a posição relativa do registro no arquivo
Indexação em memória principal
• Tipos de índices:
–Vetores
– Listar
–Árvores ou
–Híbridas
• Maior agilidade na pesquisa
• Alta volatilidade da estrutura
Indexação em memória secundária
• Tipos de índices:
–Hashing
– ISAM – Método de Acesso Sequencial Indexado
–B-Tree – Árvore B
• B-Tree (+)
• Maior custo de acesso nas pesquisa
• Alta persistência da estrutura
Perguntas...
Bibliografia
• Livro(s) Texto(s):
• PREISS, Bruno R. Estrutura de Dados e 
Algoritmos. Rio de Janeiro: Campus, 2001.
• PEREIRA, Silvio L. Estruturas de dados 
fundamentais. São Paulo: Érica, 2000.
• AZEREDO, Paulo A. Métodos de 
Classificação de Dados e Análise de suas 
Complexidades. Rio de Janeiro: Campus, 
1995.
• http://www.nuperc.unifacs.br/
Bibliografia
• Livros de referencia:
• WEISS, M. A. Data structures and algorithm 
analysis in C++. California: Benjamin/Cummings, 
1999.
• SEDGEWICK, R. Algorithms in C++: Fundamentals, 
data structures, sorting, searching. New York: 
Addison-Wesley, 2001.
• TANENBAUM, Aaron; LANGSAM, Y. & 
AUGENSTEIN, M. Estruturas de Dados usando C. 
São Paulo: Makron Books, 1995.
• LAFORE, R. Aprenda em 24 horas estrutura de 
dados e algoritmo. Rio de Janeiro: Campus, 1999.
• MORAES, Celso R. Estruturas de Dados e 
Algoritmos. São Paulo: Berkeley Brasil, 2001.