INSTITUTO FEDERAL DE EDUCAÇÃO,
EDUCAÇÃO
CIÊNCIA E TECNOLOGIA DO RIO
GRANDE DO NORTE
ESTRUTURA DE DADOS
Docente: Éberton
É
da Silva Marinho
e-mail: [email protected]
[email protected]
Curso de Tecnologia em Sistemas para Internet
26/01/2014
SUMÁRIO
|
Estruturas de dados fundamentais
Vetores
y Matrizes
M t i
y Listas encadeadas
y
ESTRUTURAS DE DADOS
FUNDAMENTAIS
VETORES (ARRAYS)
Um vetor em Java é um objeto que contém uma
coleção de objetos, todos do mesmo tipo
| Os
O elementos
l
t de
d um vetor
t são
ã acessados
d por meio
i
de índices de valor inteiro, variando de 0 a n-1
|
y
int [] a = new int[6];
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
p de acesso a um elemento do vetor é da
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:
y
|
E acessado da seguinte forma:
y
|
|
i t [][] x = new int[3][5];
int
i t[3][5]
int a = x[2][3];
Um vetor bidimensional em Java é representado
como vetores de vetores
Exercício:
y
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
•Qual
Q l o tempo
t
computacional
t i
l
deste algoritmo?
Para
A[m][n] e B[n][p],
e co
considerando
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ê um exemplo
l de
d implementação
i l
t ã e diga
di quall o
tempo computacional deste implementação.
| 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
| Maneira
M
i rápida
á id de
d criar
i uma sequência
ê i de
d
elementos do mesmo tipo na memória
| Uma vez alocado,
alocado o tamanho do vetor não pode
ser alterado
| Se não tivermos como mensurar a priori a
quantidade de elementos que vamos utilizar,
pode haver desperdício
p
p
espaço,
p ç , ou necessitamos
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
lista.
lista
| O tamanho da lista pode ser redimensionado a
qualquer instante
| Gasta espaço necessário para armazenar a lista,
sem 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
| Cada
C d elemento
l
t d
da li
lista
t aponta
t para o próximo
ó i
elemento
| O último elemento aponta para uma referência
nula
| Adicionar elementos no início da lista é fácil,
fácil
porém, para adicionar elementos no final tempos
que p
q
percorrer toda a lista
|
LISTAS SIMPLES ENCADEADAS
Nesta implementação temos uma cabeça (head)
que aponta para o primeiro elemento da lista
| Também
T bé ttemos uma cauda
d (tail)
(t il)
| Cada elemento da lista aponta para o próximo
elemento
| O último elemento aponta para uma referência
nula
| Adicionar elementos no início ou fim da lista é
fácil
|
LISTAS SIMPLES ENCADEADAS
Nesta implementação temos uma cabeça (head)
que aponta para o primeiro elemento da lista
| Cada
C d elemento
l
t d
da li
lista
t aponta
t para o próximo
ó i
elemento
| O último elemento aponta para o elemento
sentinela
| Adicionar 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
| Cada
C d elemento
l
t d
da li
lista
t aponta
t para o próximo
ó i
elemento
| O último elemento aponta para o primeiro
| Adicionar elementos no início ou fim da lista é
fácil
| Também chamada de lista circular
|
EXERCÍCIO
|
Implemente uma das listas encadeadas com o
nome LinkedList, que possua os métodos para:
Adicionar
Adi
i
elementos
l
t a li
lista
t encadeada
d d
y Retirar elementos da lista encadeada
y Imprimir os elementos da lista encadeada
y
|
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:
[email protected]
[email protected]
Endereço eletrônico da disciplina:
| http://docente.ifrn.edu.br/ebertonmarinho
|
23