PC2 Aula08

Prévia do material em texto

© ELFS 123 
8. Classes de Coleções 
•  Imagine que um programa precisa manter um conjunto ordenado de 
números inteiros fornecidos pelo usuário. O que é preciso fazer? 
1) Declarar um vetor. De qual tamanho? 
2) Manter uma variável N que indica quantos elementos o conjunto contém. 
3) A cada novo número recebido, verificar se ele já existe no vetor e, caso 
não exista, incluir. 
 N = 3 Novo = 4 
 
 
 
•  E se os elementos também puderem ser removidos? 
 N = 4 Excluir = 2 
2 5 8 2 5 8 
2 4 5 8
2 4 5 8 4 5 8 
4 5 8
© ELFS 124 
8. Classes de Coleções 
public static void main(String[] args) 
{ 
 Scanner s = new Scanner(System.in); 
 int V[] = new int[30]; 
 int N = 0; 
 while (true) 
 { 
 System.out.println("(I)ncluir, (E)xcluir, (F)im? "); 
 String x = s.next(); 
 if (x.equals("F")) 
 { 
 break; 
 } 
 System.out.println("Valor:"); 
 int v = s.nextInt(); 
 if (x.equals("I")) 
 { 
 int i = 0; 
 while (i < N && V[i] < v) i++; 
 if (V[i] != v) 
 { 
 for (int j = N; j > i; j--) 
 V[j] = V[j-1]; 
 V[i] = v; 
 N++; 
 } 
 } 
if (x.equals("E")) 
 { 
 int i = 0; 
 while (i < N && V[i] < v) i++; 
 if (V[i] == v) 
 { 
 for (int j = i; j < N-1; j++) 
 V[j] = V[j+1]; 
 N--; 
 } 
 } 
 } 
 System.out.print("[ "); 
 for (int i = 0; i < N; i++) 
 System.out.print(V[i] + " "); 
 System.out.println("]"); 
 } 
O que acontece se N > 30? 
© ELFS 125 
8. Classes de Coleções 
•  Alternativa: usar coleções. 
public static void main(String[] args) 
{ 
 Scanner s = new Scanner(System.in); 
 TreeSet ts = new TreeSet(); 
 while (true) 
 { 
 System.out.println("(I)ncluir, (E)xcluir, (F)im? "); 
 String x = s.next(); 
 if (x.equals("F")) 
 { 
 break; 
 } 
 System.out.println("Valor: "); 
 int v = s.nextInt(); 
 
 if (x.equals("I")) 
 ts.add(v); 
 
 if (x.equals("E")) 
 ts.remove(v); 
 } 
 System.out.println(ts); 
} 
© ELFS 126 
8. Classes de Coleções 
•  Vetores: estruturas de tamanho fixo para armazenar dados homogêneos. 
•  Coleções: estruturas de tamanho variável (pode aumentar ou diminuir) para 
armazenar dados heterogêneos. 
•  As coleções são implementadas a partir de interfaces e classes do pacote 
java.util. 
•  A interface Collection é parte de uma hierarquia de interfaces para a 
definição de coleções dos seguintes tipos: 
•  Set (Conjunto): coleção de objetos sem possibilidade de elementos 
duplicados. 
•  List (Lista): coleção de objetos com possibilidade de elementos 
duplicados. 
•  Map (Lista Associativa): coleção de pares (chave, valor). 
3 5 8 10 3 5 10 
3 A 8 10 3 A 15 3 A 15 X 
© ELFS 127 
Navegação em Coleções 
•  Percorrer uma coleção é acessar cada um de seus itens individualmente. A 
linguagem Java dispõe de alguns mecanismos para percorrer uma coleção. O 
melhor mecanismo é o iterador (um objeto de uma classe que implementa 
a interface Iterator). 
•  A interface Collection define o método iterator(), que retorna um iterador 
para uma determinada coleção. Iteradores são melhores para o 
percorrimento de coleções, pois sendo objetos, dispõem de métodos para 
diversas operações. 
•  Métodos mais importantes: hasNext() e next(). 
 
8. Classes de Coleções 
void percorrer(TreeSet ts) 
{ 
 Iterator iter = ts.iterator(); 
 while (iter.hasNext()) 
 { 
 int item = iter.next(); 
 ... 
 } 
} 
© ELFS 128 
8. Classes de Coleções 
Conjuntos 
•  A interface Set contém somente métodos herdados de Collection e inclui a 
restrição de que elementos duplicados são proibidos. Dois objetos de uma 
classe que implementa a interface Set são iguais se contêm os mesmos 
elementos. 
•  Os principais métodos da interface Set são: 
•  int size(): retorna o tamanho (número de elementos) do conjunto. 
•  boolean isEmpty(): retorna true se o conjunto é vazio. 
•  void add(Object obj): adiciona o objeto obj no conjunto. 
•  void remove (Object obj): remove o objeto obj do conjunto. 
•  Tipos principais de conjuntos: 
•  HashSet: conjunto de itens. 
•  TreeSet: conjunto ordenado de itens. 
© ELFS 129 
8. Classes de Coleções 
import java.util.*; 
 
public class ExemploHashSet { 
 public static void main (String [] args) { 
 int i = 0; 
 HashSet hs = new HashSet(); 
 
 // Inserir elementos no conjunto 
 hs.add("um"); 
 hs.add("dois"); 
 hs.add("tres"); 
 hs.add(new Float(7.0F)); 
 hs.add(7); 
 hs.add("um"); // como está duplicado não é adicionado 
 
 System.out.println(hs); 
 Iterator elemento = hs.iterator(); 
 while (elemento.hasNext()) 
 { 
 System.out.println("Elemento[" + i + "]=" + elemento.next()); 
 i++; 
 } 
 } 
} 
ExemploHashSet.java 
[tres, dois, 7, 7.0, um] 
Elemento[0]=tres 
Elemento[1]=dois 
Elemento[2]=7 
Elemento[3]=7.0 
Elemento[4]=um 
Notar que não foi especificado o tipo do 
elemento do conjunto. 
Notar que um objeto Set 
pode ser impresso. 
© ELFS 130 
8. Classes de Coleções 
import java.util.*; 
 
public class ExemploTreeSet 
{ 
 public static void main (String [] args) 
 { 
 int i = 0; 
 TreeSet t = new TreeSet(); 
 t.add(1); 
 t.add(3); 
 t.add(5); 
 t.add(4); 
 t.add(2); 
 System.out.println("TreeSet: " + t); 
 
 Iterator elem = t.iterator(); 
 while (elem.hasNext()) { 
 System.out.println("Elemento[" + i + "]=" + elem.next()); 
 i++; 
 } 
 } 
} 
ExemploTreeSet.java 
Os elementos serão mostrados 
em ordem crescente. 
TreeSet: [1, 2, 3, 4, 5] 
Elemento[0]=1 
Elemento[1]=2 
Elemento[2]=3 
Elemento[3]=4 
Elemento[4]=5 
© ELFS 131 
8. Classes de Coleções 
Listas 
•  A interface List deve ser utilizada para manter uma coleção com possibilidade 
de valores duplicados. 
•  Os principais métodos de List são: 
•  boolean add(Object o): adiciona o objeto o ao final da lista. 
•  void add(int i, Object o): insere o objeto o na posição i da lista. 
•  Object get(int i): recupera o objeto da posição i. 
•  int indexOf(Object o): retorna o índice da primeira ocorrência de o. 
•  Object set(int i, Object o): grava o objeto o na posição i apagando o 
objeto que se encontrava nesta posição. 
•  Object remove(int i): remove o objeto da posição i. 
•  void clear(): remove todos os elementos da lista. 
•  boolean isEmpty(): retorna true se a lista estiver vazia. 
•  boolean contains(Object o): retorna true se a lista contém o objeto o. 
•  Dois tipos de listas: 
•  ArrayList: Lista muito eficiente (vetor redimensionável). 
•  LinkedList: Menos eficiente, mas dispõe de métodos especiais. 
© ELFS 132 
8. Classes de Coleções 
import java.util.*; 
 
public class ExemploListas 
{ 
 public static void main (String [] args) 
 { 
 Date inicio,fim; 
 double duracao; 
 final int NVEZES = 100000; 
 
 ArrayList lista1 = new ArrayList(); 
 LinkedList lista2 = new LinkedList(); 
 
 for (int i = 0; i < 100; i++) 
 { 
 lista1.add(i); 
 lista2.add(i); 
 } 
 
 System.out.println("ArrayList: " + lista1); 
 System.out.println("LinkedList: " + lista2); 
ExemploListas.java 
As listas são construídas, 
inicialmente, com 100 
elementos: 0, 1, ..., 99. 
ArrayList: [0, 1, 2, 3, 4, 5, 6, 7, 8, 9, 10, 11, 12, 13, 14, 15, ..., 99] 
LinkedList: [0, 1, 2, 3, 4, 5, 6, 7, 8, 9, 10, 11, 12, 13, 14, 15, ..., 99] 
© ELFS 133 
8. Classes de Coleções 
 inicio = new Date(); 
 for (int i = 0; i < NVEZES; i++) { 
 int enovo = (int)(100*Math.random()); 
 int index = (int)(lista1.size()*Math.random());lista1.add(index,enovo); 
 } 
 fim = new Date(); 
 duracao = (double)(fim.getTime() - inicio.getTime()); 
 System.out.print("ArrayList: "); 
 System.out.println(NVEZES + " inserções em " + duracao/1000 + 
 " segundos - Tamanho final da lista = " + lista1.size()); 
 
 inicio = new Date(); 
 for (int i = 0; i < NVEZES; i++) { 
 int enovo = (int)(100*Math.random()); 
 int index = (int)(lista2.size()*Math.random()); 
 lista2.add(index,enovo); 
 } 
 fim = new Date(); 
 duracao = (double)(fim.getTime() - inicio.getTime()); 
 System.out.print("LinkedList: "); 
 System.out.println(NVEZES + " inserções em " + duracao/1000 + 
 " segundos - Tamanho final da lista = " + lista2.size()); 
Serão feitas 100000 
inserções no meio da 
lista (gera-se o elemento 
a ser inserido e a posição 
onde ele deve entrar na 
lista). 
Objetos da classe Date 
estão sendo usados para 
determinar o tempo gasto 
em cada trecho do 
programa. 
ArrayList: 100000 inserções em 0.545 segundos - Tamanho final da lista = 100100 
LinkedList: 100000 inserções em 15.201 segundos - Tamanho final da lista = 100100 
© ELFS 134 
8. Classes de Coleções 
 int chave = (int)(100*Math.random()); 
 System.out.println("Procurando o valor " + chave + " ..."); 
 
 // Procurar por um elemento na lista 
 Iterator elem = lista1.iterator(); 
 int i = 0; 
 while (elem.hasNext()) { 
 if ((Integer)elem.next() == chave) { 
 System.out.println("Valor " + chave + " encontrado na posicao " + 
 i + " da ArrayList"); 
 break; 
 } 
 i++; 
 } 
 
 // Maneira melhor de encontrar 
 if (lista1.contains(chave)) { 
 System.out.println("Valor " + chave + " encontrado na posicao " + 
 lista1.indexOf(chave) + " da ArrayList"); 
 } 
 else { 
 System.out.println("ArrayList não contém o elemento " + chave); 
 } 
 } 
} 
Duas maneiras de encontrar 
um valor na lista. 
Procurando o valor 44 ... 
Valor 44 encontrado na posicao 11 da ArrayList 
Valor 44 encontrado na posicao 11 da ArrayList 
© ELFS 135 
8. Classes de Coleções 
•  A ordem dos elementos em uma coleção é determinada pelo método 
compare() da interface Comparator. 
•  A ordenação natural é a ordem crescente. O método compare() permite 
alterar a ordenação natural para uma outra ordem qualquer. 
•  Para ordenar os elementos de uma lista pode-se usar o método 
sort(Comparator c). Se o parâmetro deste método for null, será aplicada a 
ordenação natural. 
public class ExemploSort 
{ 
 public static void main(String[] args) 
 { 
 ArrayList lista = new ArrayList(); 
 for (int i = 0; i < 10; i++) 
 { 
 lista.add((int)(100*Math.random())); 
 } 
 System.out.println("Lista original: " + lista); 
 lista.sort(null); 
 System.out.println("Lista ordenada: " + lista); 
 } 
} 
 
 
ExemploSort.java 
Lista original: [85, 77, 99, 64, 37, 95, 91, 6, 97, 2] 
Lista ordenada: [2, 6, 37, 64, 77, 85, 91, 95, 97, 99] 
© ELFS 136 
8. Classes de Coleções 
public class Comparador implements Comparator<Integer> 
{ 
 @Override 
 public int compare(Integer v1, Integer v2) 
 { 
 return (v1 > v2 ? -1 : (v1.equals(v2)? 0 : 1)); 
 } 
} 
 
Comparador.java 
Fixa a ordem decrescente 
•  A interface Comparator define o método compare() que estabelece a ordem 
dos elementos de uma coleção. 
•  O método compare() deve retornar: 
•  -1, para indicar "antes de" na ordenação; 
•  0, para indicar "não importa a ordem" na ordenação; 
•  1, para indicar "depois de" na ordenação. 
•  Exemplo: ordem decrescente 
10 8 5 2 
© ELFS 137 
8. Classes de Coleções 
Listas Associativas 
•  Coleção de pares constituídos por (chave, valor). 
Exemplo: [ (Maria, 22), (Pedro, 31), (João, 50), (Ana, 15) ] 
•  Numa lista associativa, a recuperação de um elemento da coleção é feita pelo 
valor da chave (e não por um índice numérico, como no caso das listas). 
•  Os principais métodos de Map são: 
•  void put(Object k, Object o): adiciona um par (k, o) na coleção. 
•  Object get(Object k): recupera o objeto valor associado à chave k. 
•  Set keySet(): retorna um conjunto (Set) de chaves. 
•  Collection values(): retorna uma coleção (Collection) de valores. 
•  Existem duas implementações da interface Map: 
•  TreeMap: lista de pares ordenados (pelo valor da chave). 
•  HashMap: lista associativa genérica. 
© ELFS 138 
8. Classes de Coleções 
public class ExemploMap 
{ 
 public static void main(String[] args) 
 { 
 TreeMap tm = new TreeMap(new Comparador()); 
 tm.put(1,"Luis"); 
 tm.put(3,"Thais"); 
 tm.put(2,"Gustavo"); 
 tm.put(4,"Murilo"); 
 tm.put(6,"Maria"); 
 tm.put(5,"Gabriela"); 
 tm.put(6,"Felipe"); 
 System.out.println("TreeMap: " + tm); 
 
 // Percorrendo a coleção 
 System.out.println("Usando keySet() e values() para navegacao"); 
 Iterator i = tm.keySet().iterator(); 
 Iterator j = tm.values().iterator(); 
 while (i.hasNext()) 
 { 
 System.out.println("Chave: " + i.next() + " - Valor: " + j.next()); 
 } 
 } 
} 
 
 
TreeMap: {6=Felipe, 5=Gabriela, 4=Murilo, 3=Thais, 2=Gustavo, 1=Luis} 
 
Usando keySet() e values() para navegacao 
6=Felipe 5=Gabriela 4=Murilo 3=Thais 2=Gustavo 1=Luis 
ExemploMap.java 
Os valores das chaves 
devem ser únicos. A 
inclusão de um novo par com 
uma chave igual a de outro 
par provoca a exclusão do 
par antigo.