Estruturas de Dados Fundamentais

Prévia do material em texto

INSTITUTO FEDERAL DE EDUCAÇÃO INSTITUTO FEDERAL DE EDUCAÇÃO, 
CIÊNCIA E TECNOLOGIA DO RIO 
GRANDE DO NORTEGRANDE DO NORTE
ESTRUTURA DE DADOSESTRUTURA DE DADOS
ÉDocente: Éberton da Silva Marinho
e-mail: ebertonsm@gmail.com
eberton.marinho@ifrn.edu.br
Curso de Tecnologia em Sistemas para Internet
26/01/2014
SUMÁRIO
Estruturas de dados fundamentais
Vetores
M t iMatrizes
Listas encadeadas
ESTRUTURAS DE DADOSESTRUTURAS DE DADOS
FUNDAMENTAIS
VETORES (ARRAYS)
Um vetor em Java é um objeto que contém uma 
coleção de objetos, todos do mesmo tipo
O l t d t ã d i Os elementos de um vetor são acessados por meio 
de índices de valor inteiro, variando de 0 a n-1
int [] a = new int[6];int [] a = new int[6];
A quantidade de elementos de um vetor em Java A quantidade de elementos de um vetor em Java 
pode ser acesso pela propriedade length
Uma vez alocado, o tamanho do vetor não pode , p
ser alterado
O tempo de acesso a um elemento do vetor é da p
ordem O(1)
ESTENDENDO OS VETORES JAVA
ESTENDENDO OS VETORES JAVA
T(n) = O(n)
ESTENDENDO OS VETORES JAVA
ESTENDENDO OS VETORES JAVA
ESTENDENDO OS VETORES JAVA
T(n) = O(m)
VETORES MULTIDIMENSIONAIS
Um vetor bidimensional pode ser declarado da 
seguinte forma:
i t [][] i t[3][5]int [][] x = new int[3][5];
E acessado da seguinte forma:
int a = x[2][3];int a = x[2][3];
Um vetor bidimensional em Java é representado 
como vetores de vetorescomo vetores de vetores
Exercício:Exercício:
Modifique a classe Array e crie uma 
BidimensionalArray que armazena os inteiros em um 
vetor unidimensional
MATRIZES
MULTIPLICAÇÃO DE MATRIZES
Exemplo
MULTIPLICAÇÃO DE MATRIZES
Q l t t i l •Qual o tempo computacional 
deste algoritmo?
Para Para 
A[m][n] e B[n][p],
e considerando e co s e a o 
que as matrizes 
são quadradas,
T(n) = O(n3)
MULTIPLICAÇÃO DE MATRIZES
Há alguma implementação de um algoritmo que 
tenha um tempo computacional melhor?
Dê l d i l t ã di l Dê um exemplo de implementação e diga qual o 
tempo computacional deste implementação.
Qual o nome da técnica utilizada?Qual o nome da técnica utilizada?
PROBLEMAS DOS VETORES
Um vetor em Java é um objeto que contém uma 
coleção de objetos, todos do mesmo tipo
M i á id d i ê i d Maneira rápida de criar uma sequência de 
elementos do mesmo tipo na memória
Uma vez alocado o tamanho do vetor não pode Uma vez alocado, o tamanho do vetor não pode 
ser alterado
Se não tivermos como mensurar a priori a Se não tivermos como mensurar a priori a 
quantidade de elementos que vamos utilizar, 
pode haver desperdício espaço, ou necessitamos p p p ç ,
de espaço extra para armazenar mais elementos
LISTAS SIMPLES ENCADEADAS
Sequência de objetos alocados dinamicamente, 
cada qual fazendo referência ao seu sucessor na 
listalista.
O tamanho da lista pode ser redimensionado a 
qualquer instantequalquer instante
Gasta espaço necessário para armazenar a lista, 
sem desperdíciosem desperdício
O tempo para criar cada elemento da lista é 
oneroso
LISTAS ENCADEADAS
Há diversas implementações de listas 
encadeadas. Algumas seguem abaixo:
LISTAS SIMPLES ENCADEADAS
Nesta implementação temos uma cabeça (head) 
que aponta para o primeiro elemento da lista
C d l t d li t t ó i Cada elemento da lista aponta para o próximo 
elemento
O último elemento aponta para uma referência O último elemento aponta para uma referência 
nula
Adicionar elementos no início da lista é fácil Adicionar elementos no início da lista é fácil, 
porém, para adicionar elementos no final tempos 
que percorrer toda a listaq p
LISTAS SIMPLES ENCADEADAS
Nesta implementação temos uma cabeça (head) 
que aponta para o primeiro elemento da lista
T bé t d (t il)Também temos uma cauda (tail)
Cada elemento da lista aponta para o próximo 
elementoelemento
O último elemento aponta para uma referência 
nulanula
Adicionar elementos no início ou fim da lista é 
fácilfácil
LISTAS SIMPLES ENCADEADAS
Nesta implementação temos uma cabeça (head) 
que aponta para o primeiro elemento da lista
C d l t d li t t ó i Cada elemento da lista aponta para o próximo 
elemento
O último elemento aponta para o elemento O último elemento aponta para o elemento 
sentinela
Adicionar elementos no início da lista é fácilAdicionar elementos no início da lista é fácil
Também chamada de lista circular
LISTAS SIMPLES ENCADEADAS
Nesta implementação temos uma cauda (tail) que 
aponta para o último elemento da lista
C d l t d li t t ó i Cada elemento da lista aponta para o próximo 
elemento
O último elemento aponta para o primeiroO último elemento aponta para o primeiro
Adicionar elementos no início ou fim da lista é 
fácilfácil
Também chamada de lista circular
EXERCÍCIO
Implemente uma das listas encadeadas com o 
nome LinkedList, que possua os métodos para: 
Adi i l t li t d dAdicionar elementos a lista encadeada
Retirar elementos da lista encadeada
Imprimir os elementos da lista encadeadaImprimir os elementos da lista encadeada
Após, faça um programa que utilize esta lista e 
adicione os elementos: 3, 1, 5, 7, 10, 20, 4, 1, 5, 6, , , , , , , , , , ,
1, 50. Depois retire os elementos: 1, 20, 30, 2, 4, 9. 
Qual será o resultado impresso quando 
 chamarmos o método para imprimir os elementos 
da nossa lista encadeada?
DÚVIDAS
e-mail:
ebertonsm@gmail.com
eberton.marinho@ifrn.edu.br
Endereço eletrônico da disciplina: 
http://docente.ifrn.edu.br/ebertonmarinho
2323