Introdução Estrutura de Dados e
Técnicas de Programação I
Professor: Renato Silva de Melo
Para que servem estrutura de
dados
Uma estrutura de dados é uma disposição de dados na
memória do computador (ou no disco).
– Vetores, Listas encadeadas, Pilhas, Filas, Arvores,
Tabelas hash, Grafos, Entre outras.
Algoritmos manipulam os dados nessas estruturas de
varias maneiras.
– Pesquisar um item de dado;
– Ordenar uma estrutura de dados;
Algoritmos
Muitos
dos
algoritmos
que
analisaremos
aplicam-se
diretamente a estrutura de dados. Para a maioria das
estruturas de dados precisamos saber:
–
Inserir um novo item de dados;
–
pesquisar um item específico;
–
Remover um item específico.
Estruturas de dados podem resolver problemas como:
a) Armazenamentos de dados do mundo real;
b) ferramentas do programador;
c) Modelagem do mundo real.
Tipos de dados
Tipos de dados podem ser entendidos como métodos de
interpretar o conteúdo da memória.
Os dados processados por um algoritmo possuem
naturezas distintas, isto é, podem ser números, letras,
frases, etc.
Para poder distinguir dados de naturezas distintas, e
saber quais operações podem ser realizadas com ele, os
algoritmos lidam com conceitos de tipos de dados.
O que são tipos primitivos de
dados
Em computação existem 4 tipos de dados permitidos,
algumas linguagens de programação subdividem esses
tipos de acordo com a capacidade da memória
necessária para a variável.
Tipos de dados primitivos
Tipos de dados em java
Visão geral de Estrutura de Dados
Estrutura de
Dados
Vantagens
Desvantagens
Vetor
Inserção rápida, acesso muito
rápido se o índice for conhecido
Pesquisa lenta, remoção lenta,
tamanho fixo.
Vetor ordenado Pesquisa mais rápida que o
vetor ordenado
Pesquisa lenta, remoção lenta,
tamanho fixo.
Pilha
Fornece acesso do tipo ultimo a
entrar, primeiro a sair.
Acesso lento para outros itens.
Fila
Fornece acesso do tipo primeiro
a entrar ultimo a sair.
Acesso lento para outros itens.
Lista ligada
Inserção rápida, remoção rápida
Pesquisa lenta.
Árvore binária
Pesquisa, inserção e remoção
rápidas.
O algoritmo de remoção é
complexo.
Tabela hash
Inserção rápida, acesso muito
rápido se o índice for conhecido.
Remoção rápida, acesso lento se
a chave não for conhecida, uso
de memória ineficiente.
Grafo
Modela situações do mundo
real.
Alguns algoritmos são lentos e
complexos.
Referência Bibliográfica
LAFORE, Robert. Estruturas de dados & algoritmos em
Java. Rio de Janeiro: Ciência Moderna, 2004.