Um conjunto de numeros inteiros, que suporta operacoes para inserir, adicionar e verificar se um numero esta no conjunto.
// ----------------------------------------------------------- // Estruturas de Dados 2021/2022 (CC1007) - DCC/FCUP // http://www.dcc.fc.up.pt/~pribeiro/aulas/edados2122/ // ----------------------------------------------------------- // Interface que define o TAD conjunto de numeros inteiros // Ultima alteracao: 10/03/2018 // ----------------------------------------------------------- // Interface que define o TAD conjunto de numeros inteiros public interface IntSet { public boolean contains(int x); // Retorna true se x esta no conjunto public boolean add(int x); // Adiciona x ao conjunto public boolean remove(int x); // Remove x do conjunto public int size(); // Retorna o numero de elementos do conjunto public void clear(); // Limpa o conjunto (torna-o vazio) }
// ----------------------------------------------------------- // Estruturas de Dados 2021/2022 (CC1007) - DCC/FCUP // http://www.dcc.fc.up.pt/~pribeiro/aulas/edados2122/ // ----------------------------------------------------------- // Implementa o TAD conjunto usando um array como lista de elementos // Ultima alteracao: 10/03/2018 // ----------------------------------------------------------- public class ArrayListIntSet implements IntSet { private int size; // Numero de elementos do conjunto private int elem[]; // Array que contem os elementos em si ArrayListIntSet(int maxSize) { elem = new int[maxSize]; size = 0; } public boolean add(int x) { if (!contains(x)) { if (size == elem.length) throw new RuntimeException("Maximum size of set reached"); elem[size] = x; size++; return true; } return false; } public boolean remove(int x) { if (contains(x)) { int pos = 0; while (elem[pos] != x) pos++; size--; elem[pos] = elem[size]; // Trocar ultimo elemento return true; // com o que se removeu } return false; } public boolean contains(int x) { for (int i=0; i<size; i++) if (elem[i] == x) return true; return false; } public void clear() { size = 0; } public int size() { return size; } @Override public String toString() { String res = "{"; for (int i=0; i<size; i++) { if (i>0) res += ","; res += elem[i]; } res += "}"; return res; } }
// ----------------------------------------------------------- // Estruturas de Dados 2021/2022 (CC1007) - DCC/FCUP // http://www.dcc.fc.up.pt/~pribeiro/aulas/edados2122/ // ----------------------------------------------------------- // Exemplo de utilizacao do TAD Conjunto // Ultima alteracao: 10/03/2018 // ----------------------------------------------------------- public class TestSet { public static void main(String[] args) { IntSet s = new ArrayListIntSet(100); // Cria um conjunto com espaco para 100 inteiros System.out.println(s); System.out.println(s.add(1)); System.out.println(s.add(5)); System.out.println(s.add(7)); System.out.println(s); System.out.println(s.contains(1)); System.out.println(s.contains(2)); System.out.println(s.add(1)); System.out.println(s.size()); System.out.println(s.remove(5)); System.out.println(s.remove(5)); System.out.println(s); s.clear(); System.out.println(s); System.out.println(s.size()); } }