View
2.942
Download
1
Embed Size (px)
Citation preview
Vetores em Java
Fundamentos da Linguagem Java
Ludimila Monjardim Casagrande 2012
Implementação de Estruturas de
Dados
Vetor
Um vetor é uma lista implementada usando um
array.
O que são listas?
Lista é uma estrutura de dados que, por
definição, permite objetos duplicados e é
ordenada.
Uma estrutura de dados deve definir:
A maneira como o dado será armazenado;
A interface ou operações disponíveis para uso.
Vetores em Java ©2012 Ludimila Monjardim Casagrande 2
Vetor
Um array é uma porção de memória fixa e
sequencial dividida em pedaços idênticos
indexados a partir de 0.
A capacidade de um array é fixa e deve ser
informada no momento da criação do array.
Vetores em Java ©2012 Ludimila Monjardim Casagrande 3
Vetor de Objetos
Em cada posição do array (ou vetor), podemos
guardar um objeto. Na verdade, cada posição
pode guardar uma referência para um objeto.
Vetores em Java ©2012 Ludimila Monjardim Casagrande 4
Exemplo:
Array, vetor
ou lista de
Alunos.
O que vamos implementar?
Vamos implementar um vetor para a listagem de
Alunos.
Para isso, precisamos primeiro implementar a
classe Aluno.
Em seguida, precisamos definir a interface da
lista, isto é, as operações públicas disponíveis
para a manipulação de dados nessa estrutura.
Vetores em Java ©2012 Ludimila Monjardim Casagrande 5
Classe Aluno
package poo.modelo;
public class Aluno {
private int matricula;
private String nome;
public Aluno(int matricula, String nome) {
this.nome = nome;
this.matricula = matricula;
}
public int getMatricula() {
return matricula;
}
public void setMatricula(int matricula) {
this.matricula = matricula;
}
public String getNome() {
return nome;
}
public void setNome(String nome) {
this.nome = nome;
}
@Override
public String toString() {
return "Aluno [matricula=" + matricula + ", nome=" + nome + "]";
}
@Override
public boolean equals(Object obj) {
if (this == obj) {
return true;
}
if (obj == null) {
return false;
}
if (!(obj instanceof Aluno)) {
return false;
}
Aluno a = (Aluno) obj;
if (matricula != a.matricula) {
return false;
}
return true;
}
}
Vetores em Java ©2012 Ludimila Monjardim Casagrande 6
Obs.: Incluir o
construtor default.
Operações da Lista
Vamos implementar as seguintes operações:
Adicionar um dado objeto no fim da lista;
Adicionar um dado objeto em uma dada posição;
Recuperar o objeto de uma dada posição;
Remover o objeto de uma dada posição;
Verificar se um dado objeto está contido na lista;
Obter a quantidade de objetos (elementos) da
lista.
Imprimir a lista (implementar o método toString()).
Vetores em Java ©2012 Ludimila Monjardim Casagrande 7
Estrutura da Classe Vetor
package poo.estruturas;
import poo.modelo.Aluno;
public class Vetor {
/** Declaração e inicialização de um array de
* objetos do tipo Aluno
* com capacidade para 100 objetos. */
private Aluno[] alunos = new Aluno[100];
/** Numero atual de elementos do array. */
private int totalDeElementos;
public void adiciona(Aluno aluno) {
// TODO implementação
}
public void adiciona(int posicao, Aluno aluno) {
// TODO implementação
}
public Aluno recupera(int posicao) {
// TODO implementação
return null;
}
public void remove(int posicao) {
// TODO implementação
}
public boolean contem(Aluno aluno) {
// TODO implementação
return false;
}
public int obtemTotalDeElementos() {
// TODO implementação
return 0;
}
}
Vetores em Java ©2012 Ludimila Monjardim Casagrande 8
Obs.: Incluir também o
método toString().
Considerações sobre o Vetor
Considere que os elementos do vetor devam estar
estão todos compactados à esquerda, isto é, não
existem posições vazias entre as posições ocupadas.
Vetores em Java ©2012 Ludimila Monjardim Casagrande 9
Classes para Teste
package poo.testes;
import poo.modelo.Aluno;
import poo.estruturas.Vetor;
public class TesteAdicionaNoFim {
public static void main(String[] args) {
Aluno a1 = new Aluno(100, "José");
Aluno a2 = new Aluno(200, "João");
Vetor lista = new Vetor();
lista.adiciona(a1);
lista.adiciona(a2);
System.out.println(lista);
}
}
Vetores em Java ©2012 Ludimila Monjardim Casagrande 10
Saída esperada:
[Aluno [matricula=100, nome=José],
Aluno [matricula=200, nome=João]]
Classes para Teste
package poo.testes;
import poo.modelo.Aluno;
import poo.estruturas.Vetor;
public class TesteAdicionaPorPosicao {
public static void main(String[] args) {
Aluno a1 = new Aluno(101, "Rafael");
Aluno a2 = new Aluno(201, "Paulo");
Aluno a3 = new Aluno(301, "Ana");
Vetor lista = new Vetor();
lista.adiciona(a1);
lista.adiciona(0, a2);
lista.adiciona(1, a3);
System.out.println(lista);
}
}
Vetores em Java ©2012 Ludimila Monjardim Casagrande 11
Saída esperada:
[Aluno [matricula=201, nome=Paulo],
Aluno [matricula=301, nome=Ana],
Aluno [matricula=101, nome=Rafael]]
Classes para Teste
Vetores em Java ©2012 Ludimila Monjardim Casagrande 12
package poo.testes;
import poo.modelo.Aluno;
import poo.estruturas.Vetor;
public class TesteRecuperaPorPosicao {
public static void main(String[] args) {
Aluno a1 = new Aluno(101, "Rafael");
Aluno a2 = new Aluno(201, "Paulo");
Vetor lista = new Vetor();
lista.adiciona(a1);
lista.adiciona(a2);
Aluno aluno1 = lista.recupera(0);
Aluno aluno2 = lista.recupera(1);
System.out.println(aluno1);
System.out.println(aluno2);
}
}
Saída esperada:
Aluno [matricula=101, nome=Rafael]
Aluno [matricula=201, nome=Paulo]
Classes para Teste
Vetores em Java ©2012 Ludimila Monjardim Casagrande 13
package poo.testes;
import poo.modelo.Aluno;
import poo.estruturas.Vetor;
public class TesteRemovePorPosicao {
public static void main(String[] args) {
Aluno a1 = new Aluno(101, "Rafael");
Aluno a2 = new Aluno(201, "Paulo");
Vetor lista = new Vetor();
lista.adiciona(a1);
lista.adiciona(a2);
lista.remove(0);
System.out.println(lista);
}
}
Saída esperada:
Aluno [matricula=201, nome=Paulo]
Classes para Teste
Vetores em Java ©2012 Ludimila Monjardim Casagrande 14
package poo.testes;
import poo.modelo.Aluno;
import poo.estruturas.Vetor;
public class TesteContemAluno {
public static void main(String[] args) {
Aluno a1 = new Aluno(101, "Rafael");
Aluno a2 = new Aluno(201, "Paulo");
Vetor lista = new Vetor();
lista.adiciona(a1);
lista.adiciona(a2);
System.out.println(lista.contem(a1));
System.out.println(lista.contem(a2));
Aluno a3 = new Aluno(301, "Ana");
System.out.println(lista.contem(a3));
}
}
Saída esperada:
true
true
false
Classes para Teste
Vetores em Java ©2012 Ludimila Monjardim Casagrande 15
package poo.testes;
import poo.modelo.Aluno;
import poo.estruturas.Vetor;
public class TesteRecuperaTamanhoDaLista {
public static void main(String[] args) {
Aluno a1 = new Aluno(101, "Rafael");
Aluno a2 = new Aluno(201, "Paulo");
Aluno a3 = new Aluno();
Vetor lista = new Vetor();
lista.adiciona(a1);
lista.adiciona(a2);
System.out.println(lista.obtemTotalDeElementos());
lista.adiciona(a3);
System.out.println(lista.obtemTotalDeElementos());
}
}
Saída esperada:
2
3
Método: adiciona(Aluno aluno)
Vetores em Java ©2012 Ludimila Monjardim Casagrande 16
Possível
implementação:
Método: adiciona(Aluno aluno)
Problema da implementação anterior:
O consumo de tempo do
método piora proporcional-
mente na medida em que
o número de elementos
que existem no vetor
aumenta, o que representa
um consumo linear de tempo.
Vetores em Java ©2012 Ludimila Monjardim Casagrande 17
Complexidade de Algoritmos
Consumo Linear x Consumo Constante:
Consumo
(ou complexidade) linear:
proporcional ao número
de elementos do vetor.
Indicado por: O(n).
Consumo (ou complexidade)
constante: não varia em
função do número de
elementos do vetor.
Indicado por: O(1).
Vetores em Java ©2012 Ludimila Monjardim Casagrande 18
Consumo Linear x Consumo Constante
Método: adiciona(Aluno aluno)
Vetores em Java ©2012 Ludimila Monjardim Casagrande 19
Quantidade de elementos = Índice da
primeira posição vazia
Implementação parcial. Ainda falta
verificar se o vetor está cheio, isto é,
se totalDeAlunos < alunos.length.
Implementação alternativa
com consumo (complexidade)
constante:
Método: adiciona(int posicao, Aluno aluno)
Verifique se o vetor está cheio.
Verifique se a posição desejada é válida. As posições válidas são
as posições ocupadas e a primeira posição desocupada
(=totalDeAlunos). Além disso, a posição desejada deve ser menor
do que o tamanho do vetor.
Se a posição desejada for a última posição válida, apenas adicione
o elemento nesta posição.
Vetores em Java ©2012 Ludimila Monjardim Casagrande 20
Método: adiciona(int posicao, Aluno aluno)
Se a posição desejada for uma posição ocupada, desloque os
elementos para a direita até desocupar a posição desejada. Por fim,
adicione o elemento nesta posição e incremente o total de alunos.
Vetores em Java ©2012 Ludimila Monjardim Casagrande 21
A dica em relação a esse método é primeiro verificar se a posição
desejada é uma posição ocupada, isto é, se a posição pertence ao
intervalo de 0 a totalDeAlunos - 1.
Se sim, basta recuperar o objeto desta posição.
Método: recupera(int posicao)
Vetores em Java ©2012 Ludimila Monjardim Casagrande 22
Verifique se a posição desejada é uma posição ocupada.
Se for, remova o objeto alterando o valor da posição para null.
Em seguida, desloque os objetos à direita do objeto removido uma
posição para a esquerda, caso eles existam.
Decremente o número total de alunos.
Método: remove(int posicao)
Vetores em Java ©2012 Ludimila Monjardim Casagrande 23
Nesta operação, precisamos comparar o aluno dado com todos os
alunos existentes no vetor.
Para isso implemente um laço e compare os objetos usando o
método equals.
Método: contem(Aluno aluno)
Vetores em Java ©2012 Ludimila Monjardim Casagrande 24
Caixas de Diálogo
Você pode exibir mensagens de erro ou
informativas para o usuário usando uma caixa
de diálogo da seguinte forma:
Vetores em Java ©2012 Ludimila Monjardim Casagrande 25
Vetores em Java ©2012 Ludimila Monjardim Casagrande 26
Referências
CS-14: Algoritmos e Estruturas de Dados em Java.
Caelum: Ensino e Inovação. http://www.caelum.com.br/curso/cs-14-algoritmos-estruturas-dados-
java/
Capítulo 4 – Arrays.
Orientação a Objetos em Java.
K19 Treinamentos. http://www.k19.com.br/downloads/apostilas-java.
Capítulo 16 – Collections framework.
Caelum: Ensino e Inovação. http://www.caelum.com.br/curso/fj-11-java-orientacao-objetos/