AULA_ED_02

Prévia do material em texto

ESTRUTURA DE DADOS 
ESTRUTURA DE DADOS 
ESTRUTURA DE DADOS 
O QUE SÃO ESTRUTURA DE DADOS? 
É uma disposição de dados na memória de um computador, ou em 
discos. 
 
Algumas Estruturas de Dados mais conhecidas são: 
• Vetores; 
• Listas encadeadas; 
• Pilhas; 
• Árvores Binárias; 
• Tabelas Hash. 
ESTRUTURA DE DADOS 
O QUE SÃO ALGORITMOS? 
É a descrição detalhada dos passos que deverão ser seguidos para se 
atingir um objetivo. 
 
Um exemplo do mundo real por exemplo é descrever todos os passos 
necessários para a troca de uma lâmpada queimada. 
1. Pego a escada; 
2. Posiciono a escada próxima a lâmpada queimada; 
3. Pego uma lâmpada nova; 
4. Subo na escada; 
5. Retiro a lâmpada queimada; 
6. Etc... 
ESTRUTURA DE DADOS 
ESTRUTURA DE DADOS E ALGORITMOS 
A Estrutura de Dados é uma forma de organizar e armazenar os dados na 
memória do computador ou em um disco. 
 
Os Algoritmos são a maneira de manipularmos e acessarmos estes dados. 
ESTRUTURA DE DADOS 
O QUE PODEMOS FAZER? 
Podemos categorizar os nossos problemas e após essa categorização, 
teremos uma visão geral de como aplicar os conceitos de Estrutura de 
Dados a estes problemas 
 
Inicialmente vamos categorizar os nossos problemas em 03 categorias: 
 
• Armazenamento de dados do mundo real; 
• Ferramentas do programador; 
• Modelagem 
ESTRUTURA DE DADOS 
ARMAZENAMENTO DE DADOS DO MUNDO REAL 
Nesta problemática temos que encontrar maneiras de armazenar dados 
que são comuns no mundo real. 
 
Um exemplo clássico é a organização dos nossos contatos. Normalmente 
utilizamos fichas ou uma agenda. 
ESTRUTURA DE DADOS 
ARMAZENAMENTO DE DADOS DO MUNDO REAL 
Como transportar para o mundo computacional? 
 
Para isso devemos analisar: 
 
• Como armazenaria na memória do computador;. 
• Este método funcionaria para 100, 1.000, 1.000.000 de contatos; 
• Seria permitido a inserção imediata de novos contatos?; 
• É possível uma busca rápida de um contato em específico?; 
• Como organizar em ordem alfabética? 
ESTRUTURA DE DADOS 
FERRAMENTAS DO PROGRAMADOR 
Muitas estruturas de dados são a representação dos dados dos usuários. 
No entanto algumas representam informações que serão úteis apenas 
para o sistema. 
 
Pilhas e filas são alguns exemplos destas ferramentas. 
ESTRUTURA DE DADOS 
MODELAGEM DO MUNDO REAL 
A estrutura de dados para este tipo de modelagem são os GRAFOS, e com 
eles podemos modelar e testar situações do mundo real, com o objetivo 
de simular estas situações antes de vivenciá-las. 
ESTRUTURA DE DADOS 
TIPOS DE ESTRUTURAS DE DADOS 
ESTRUTURA DE DADOS VANTAGENS DESVANTAGENS 
Vetor Inserção rápida, acesso 
rápido se o índice for 
conhecido 
Pesquisa e remoção lenta, 
e tamanho fixo 
Vetor ordenado Pesquisa mais rápida que 
o vetor não ordenado 
Inserção e remoção lenta, 
e tamanho fixo 
Pilha Fornece acesso do tipo 
último a entrar, primeiro a 
sair 
Acesso lento para outros 
itens 
Fila Fornece acesso do tipo 
primeiro a entrar, primeiro 
a sair 
Acesso lento para outros 
itens 
ESTRUTURA DE DADOS 
TIPOS DE ESTRUTURAS DE DADOS 
ESTRUTURA DE DADOS VANTAGENS DESVANTAGENS 
Lista ligada Inserção e remoção rápida Pesquisa lenta 
Árvore binária Pesquisa, inserção e 
remoção rápida, se a 
estiver balanceada 
Algoritmo de remoção é 
complexo 
Árvore vermelho – preto Pesquisa, inserção e 
remoção rápidas. Sempre 
balanceada 
Complexa 
Árvore 2-3-4 Pesquisa, inserção e 
remoção rápidas. Sempre 
balanceada. Boas para 
armazenamento em disco 
Complexa 
ESTRUTURA DE DADOS 
TIPOS DE ESTRUTURAS DE DADOS 
ESTRUTURA DE DADOS VANTAGENS DESVANTAGENS 
Tabela hash Acesso muito rápido se a 
chave for conhecida. 
Inserção rápida 
Acesso lento se a chave 
não for conhecida, uso de 
memória ineficiente 
Heap Inserção, remoção e 
acesso rápidos para maior 
item 
Acesso lento para outros 
itens 
Grafo Modela situações do 
mundo real 
Algoritmos lentos e 
complexos 
ESTRUTURA DE DADOS 
ALGUMAS DEFINIÇÕES 
Banco de Dados 
Todo e qualquer dado que será utilizado em uma situação particular. Cada 
item terá um formato singular 
 
Registro 
São as unidades nas quais uma base de dados é divida. Fornecem o 
formato para armazenar a informação 
 
Campo 
Um registro é geralmente dividido em vários campos. Ex.: nome, idade, 
sexo, cpf 
ESTRUTURA DE DADOS 
ALGUMAS DEFINIÇÕES 
Chave 
Campo que será utilizado na pesquisa dos dados. Geralmente é uma 
identificação única. 
ESTRUTURA DE DADOS 
TIPOS DE VARIÁVEIS – TIPOS PRIMITIVOS 
Tipo Bits Faixa de Valores 
boolean 1 true ou false 
byte 8 -128 a 127 
char 16 ‘\u0000’ a ‘\uFFFF’ 
short 16 -32.768 a 32.767 
int 32 -2.147.483.648 a 2.147.483.647 
long 64 -9.223.372.036.854.775.808 a 
9.223.372.036.854.775.807 
float 32 Aproximadamente 10-38 a 1038; 
7 dígitos significativos 
double 64 Aproximadamente 10-308 a 10308; 
15 dígitos significativos 
ESTRUTURA DE DADOS 
?