Listas Estáticas-1

Prévia do material em texto

Estrutura de Dados
Listas
Jorge Campos
jorge@unifacs.br
Abstração de Dados
Abstração de Dados (Data Abstraction) é um dos mais importante mecanismo de abstração. 
No processo de abstração de dados “tudo” é visto como objetos. 
Abstração de Dados permite que sejam abstraídos os detalhes de como os objetos são implementados e que toda a atenção seja dada a como os objetos se comportam e se comunicam. 
Na prática a abstração de dados é obtida através da definição de um novo tipo de dado (Tipo Abstrato de Dado).
O comportamento dos objetos é expresso em termos de um conjunto de operações com algum significado para esses objetos.
Tipo Abstrato de Dados = (objetos, operações)
Em Java, Tipos Abstrados de Dados são obtidos através de classes ou interfaces.
Forma Geral da Especificação de um TAD
Visibilidade class Nome {
// Visão Geral: uma breve descrição do comportamento do objeto
// Construtores
// Especificação dos construtores
// Requer:
// Modifica:
// Efeito:
// Métodos
// Especificação dos métodos
// Requer:
// Modifica:
// Efeito:
}
Listas
Definição
Uma lista é uma seqüência mutável de zero ou mais itens na forma A1, A2,…,An onde n é o tamanho da lista e Ai são elementos de um determinado tipo.
Propriedade Estrutural 
Para qualquer lista, à exceção da lista vazia, tem-se:
	O item Ai está na i-ésima posição da lista
	Ai precede Ai+1 (para i>1)
	Ai+1 sucede Ai (para i<n)
	O predecessor de A1 e o sucessor de An não são definidos
Tipo Abstrato de Dados = (objetos, operações)
Operações Sobre Objetos Listas 
Criar uma Lista vazia
Consultar o número de elementos na lista
Verificar se a lista está vazia 
Esvaziar a lista
Adicionar um elemento no final da lista
Remover a primeira ocorrência de um elemento na lista
Inserir um novo elemento na i-ésima posição
Remover o elemento na i-ésima posição
Buscar o i-ésimo elemento
Buscar a posição da primeira ocorrência de um elemento
Combinar duas ou mais listas em uma lista única
Dividir uma lista em duas
Fazer uma cópia da lista
Ordenar os itens da lista em ordem crescente ou decrescente
Imprimir a lista
…
*
Implementação de Listas
Posição dos elementos na mémoria
	Elementos consecutivos (lista seqüencial) 
	Elementos não consecutivos (lista encadeada)
Representações usuais
	Através de arranjos (arrays) – listas estáticas
	Através de apontadores ou ponteiros – listas dinâmicas
Restrições nas operações 
	Diferentes tipos de listas (pilhas, filas, deques, etc)
Organização dos Elementos
	Listas ordenadas ou não ordenadas
Implementação das operações
	Depende da representação e da organização dos elementos
Implementação de TADs Genéricos
A Superclasse Object em Java
A classe Object é a superclasse de todas as classes em Java.
public MinhaClasse extends Object {…}
Implícito
Alguns Métodos da Classe Object
public boolean equals(Object obj)
Indicates whether some other object is "equal to" this one.
Parameters: obj - the reference object with which to compare. 
Returns: true if this object is the same as the obj argument; false otherwise. 
The equals method implements an equivalence relation on non-null object references: 
	It is reflexive: for any non-null reference value x, x.equals(x) should return true. 
	It is symmetric: for any non-null reference values x and y, x.equals(y) should return true if and only if y.equals(x) returns true. 
	It is transitive: for any non-null reference values x, y, and z, if x.equals(y) returns true and y.equals(z) returns true, then x.equals(z) should return true. 
	It is consistent: for any non-null reference values x and y, multiple invocations of x.equals(y) consistently return true or consistently return false, provided no information used in equals comparisons on the objects is modified. 
	For any non-null reference value x, x.equals(null) should return false. 
The equals method for class Object implements the most discriminating possible equivalence relation on objects; that is, for any non-null reference values x and y, this method returns true if and only if x and y refer to the same object (x == y has the value true). 
Alguns Métodos da Classe Object
public String toString()
Returns a string representation of the object. In general, the toString method returns a string that "textually represents" this object. The result should be a concise but informative representation that is easy for a person to read. It is recommended that all subclasses override this method. 
Returns:a string representation of the object.
The toString method for class Object returns a string consisting of the name of the class of which the object is an instance, the at-sign character `@', and the unsigned hexadecimal representation of the hash code of the object. In other words, this method returns a string equal to the value of: 
getClass().getName() + '@' + Integer.toHexString(hashCode()) 
Especificação do TAD Lista
public class Lista {
// Visão Geral: seqüência mutável de zero ou mais itens na forma A0, A1,…,An-1 onde n é o 
// tamanho da lista e Ai são elementos de um determinado tipo, estruturados da seguinte forma:
// Ai precede Ai+1 (i≥0)
// Ai+1 sucede Ai (i<n-1)
// O item Ai está na i-ésima posição da lista
// O predecessor de A0 e o sucessor de An-1 não são definidos
// Construtores
public Lista()
// Efeito: Inicializa this como uma lista vazia de Objects
// Métodos
public int size()
// Efeito: retorna o número de elementos na lista
public boolean isEmpty()
// Efeito: testa se a lista está vazia
public void addElement (Object elem)
// Modifica: this
// Efeito: adiciona elem aos elementos de this na última posição
public boolean removeElement (Object elem)
// Modifica: this
// Efeito: remove a primeira ocorrência de elem dos elementos de this
*
Especificação do TAD Lista
public void removeAllElements()
// Modifica: this
// Efeito: remove todos os elementos da lista
public void insertElementAt (Object elem, int index) throws IndexOutOfBoundsException {
// Modifica: this
// Efeito: se index <0 ou index > this.size() lança uma OutOfBoundsException, caso
 // contrário adiciona elem aos elementos de this na posição index
public void removeElementAt (int index) throws IndexOutOfBoundsException {
// Modifica: this
// Efeito: se index <0 ou index > this.size() lança uma OutOfBoundsException, caso
// contrário remove o elemento na posição index de this
public Object ElementAt (int index) throws OutOfBoundsException
 // Efeito: se index <0 ou index > this.size() lança uma OutOfBoundsException, caso
 // contrário retorna o elemento na posição index na lista
public int indexOf (Object elem )
// Efeito: retorna a posição da primeira ocorrência do elemento elem na
// lista. Utiliza o método equals para determinar se são os mesmos objetos. Retorna -1, caso
// elem não esteja na lista 
public void printList ()
// Efeito: Imprime todos os elementos da lista usando o método toString()
*
Arrays em Java
Arrays
Arrays são estruturas que representam uma coleção (uni ou multidimensional) de objetos de um mesmo tipo, armazenados contiguamente na memória (sequencial).
	Declarando um variável do tipo Array (unidimensional)
Tipo de Dados[ ] UmaArray;
	Instanciando um Array com capacidade para 100 elementos:
umaArray=new Tipo de Dados[100];
Uma vez instanciada uma Array, sua capacidade não pode ser alterada!
Seus elementos podem ser alterados como qualquer outra variável e são acessados através de índices ε [0,capacidade-1]
	O1	O2	O3	...	On	null	null	null	null	null
umaArray[0]
umaArray[1]
umaArray[n]
umaArray[capaciadade-1]
Implementação do TAD Lista com Arranjos
public class Lista{
 // Representação
 private Object[] elements;	// array de objetos
 private int size;		// número de elementos na lista
 private int capacity=5;		// capacidade inicial da lista
 // Construtores
 public Lista() {
 elements=new Object[capacity];
 size=0; 
 } 
 // Métodos
 public int size() {
 return size;
 }
 public boolean isEmpty() {
 return(size==0); 
 }
MinhaLista
Object elements 
int size =0
int capacity=5
	null	null	null	null	null
capacity
*
Implementação do TAD Lista com Arranjos
public void addElement (Object elem) {
 increaseCapacityIfNecessary();
 elements[size]=elem;
 size++;
}
private void increaseCapacityIfNecessary() {
 // se não houver mais espaço no array, cria um novo array com o dobro da 
 // capacidade e repassa os elementos atualmente na lista para o novo array
 if (size==capacity) {
 Object[] newElements=new Object[capacity*2];
 for (int i=0;i<size;i++) 
 newElements[i]=elements[i];
 elements=newElements;
 capacity*=2;
 }
}
?
*
Implementação do TAD Lista com Arranjos
public void addElement (Object elem) {
 increaseCapacityIfNecessaray();
 elements[size]=elem;
 size++;
}
MinhaLista
Object elements 
int size =0
int capacity=5
MinhaLista.addElement (O1) 
	null	null	null	null	null
capacity
*
Implementação do TAD Lista com Arranjos
public void addElement (Object elem) {
 increaseCapacityIfNecessaray();
 elements[size]=elem;
 size++;
}
MinhaLista
Object elements 
int size =1
int capacity=5
MinhaLista.addElement (O2)
MinhaLista.addElement (O3)
MinhaLista.addElement (O4)
MinhaLista.addElement (O5) 
size
capacity
	O1	null	null	null	null
*
Implementação do TAD Lista com Arranjos
public void addElement (Object elem) {
 increaseCapacityIfNecessaray();
 elements[size]=elem;
 size++;
}
MinhaLista
Object elements 
int size =5
int capacity=5
MinhaLista.addElement (O6) 
capacity
size
	O1	O2	O3	O4	O5
*
Implementação do TAD Lista com Arranjos
private void increaseCapacityIfNecessaray() {
if (size==capacity) {
 Object[] newElements=new Object[capacity*2];
 for (int i=0;i,<size;i++) 
 newElements[i]=elements[i];
 elements=newElements;
 capacity*=2;
 }
}
MinhaLista
Object elements 
int size =5
int capacity=5
	null	null	null	null	null	null	null	null	null	null
	O1	O2	O3	O4	O5
	O1	O2	O3	O4	O5	null	null	null	null	null
*
Implementação do TAD Lista com Arranjos
private void increaseCapacityIfNecessaray() {
if (size==capacity) {
 Object[] newElements=new Object[capacity*2];
 for (int i=0;i,<size;i++) 
 newElements[i]=elements[i];
 elements=newElements;
 capacity*=2;
 }
}
MinhaLista
Object elements 
int size =5
int capacity=10
	null	null	null	null	null	null	null	null	null	null
	O1	O2	O3	O4	O5
	O1	O2	O3	O4	O5	null	null	null	null	null
*
Implementação do TAD Lista com Arranjos
public void addElement (Object elem) {
 increaseCapacityIfNecessaray();
 elements[size]=elem;
 size++;
}
MinhaLista
Object elements 
int size =5
int capacity=10
MinhaLista.addElement (O6) 
	O1	O2	O3	O4	O5	null	null	null	null	null
*
Implementação do TAD Lista com Arranjos
public void addElement (Object elem) {
 increaseCapacityIfNecessaray();
 elements[size]=elem;
 size++;
}
MinhaLista
Object elements 
int size =6
int capacity=10
	O1	O2	O3	O4	O5	O6	null	null	null	null
capacity
size
*
Implementação do TAD Lista com Arranjos
public void removeElement (Object elem) {
 int index=indexOf(elem);
 if (index>=0) removeElementAt(index);
}
public int indexOf (Object elem ) {
 for (int i=0;i<size;i++)
 if (elements[i].equals(elem)) 
 return i;
 return -1;
 }
?
*
Tratamento de Exceções
Exceções são eventos anormais que podem fazer um programa falhar. 
Por exemplo, quando se espera que um usuário entre com um número e este digita uma letra.
•As exceções na linguagem Java são objetos reais, instâncias de classe que herdam da classe Throwable. Um objeto da classe Throwable é criada, quando uma exceção é gerada.
•A linguagem Java permite que se tratem exceções através do try-catch-finally.
–try : neste bloco se coloca a chamada de métodos que podem lançar exceções.
–catch : Neste bloco você trata as exceções geradas.
–finally : neste bloco (opcional) coloca-se o código a ser executado indepenede de ter ocorrido ou não alguma exceção.
•Existem vários tipos de exceções na linguagem Java. Para que você possa tratá-las adequadamente é necessário descobrir quais são as exceções que podem ser geradas (levantadas) por um determinado método.
–Algumas exceções da linguagem Java
IOException			EOFException 		
FileNotFoundException		MalformedURLException 
SocketException		ArrayIndexOutOfBoundsException
*
Implementação do TAD Lista com Arranjos
public void removeElementAt (int index) throws ArrayIndexOutOfBoundsException {
 if (index<0 || index>size-1)
 throw new ArrayIndexOutOfBoundsException ("Lista.removeElementAt");
 else {
 size--;
 for (int i=index;i<size;i++) 
 elements[i]=elements[i+1];
 }
 }
?
*
Implementação do TAD Lista com Arranjos
MinhaLista
Object elements 
int size =6
int capacity=10
MinhaLista.removeElement (O3) 
index=indexOf(O3)=2 
MinhaLista
Object elements 
int size =5
int capacity=10
MinhaLista.removeElementAt (2) 
	O1	O2	O3	O4	O5	O6	null	null	null	null
	O1	O2	O4	O5	O6	O6	null	null	null	null
size
size
*
Implementação do TAD Lista com Arranjos
public void removeAllElements() {
 size=0;
}
public void insertElementAt (Object elem, int index) throws ArrayIndexOutOfBoundsException 
 if (index<0 || index>size-1) {
 throw new ArrayIndexOutOfBoundsException ("Lista.insertElementAt");
 }
 else {
 increaseCapacityIfNecessaray();
 for (int i=size;i>index;i--) 
 elements[i]=elements[i-1];
 elements[index]=elem;
 }
 size++;
 }
*
Implementação do TAD Lista com Arranjos
MinhaLista
Object elements 
int size =6
int capacity=10
MinhaLista.insertElementAt (O7,2) 
	O1	O2	O3	O4	O5	O6	null	null	null	null
	O1	O2	O3	O4	O5	O6	null	null	null	null
	O1	O2	O3	O3	O4	O5	O6	null	null	null
	O1	O2	O7	O3	O4	O5	O6	null	null	null
MinhaLista
Object elements 
int size =7
int capacity=10
size
size
O7
*
Implementação do TAD Lista com Arranjos
public void printList() {
 for (int i=0;i<size;i++) 
 System.out.println(elements[i].toString()); // pode omitir a chamada toString
 }
}
*
Exercício
Considere o seguinte problema:
Manter uma lista composta de objetos instâncias da classe Aluno.
Public Class Aluno {
	private String nome;
	private String matricula;
 public Aluno (String n,String m) {
 		nome=n;
 matricula=m;
 }
 public String toString() {
 return nome+”-”+matricula;
 }
}
*
Exemplo
public class ExemploLista {
 public static void main( String[] args) {
 Aluno a1,a2,a3;
 OrderedList ListaAlunos;
 ListaAlunos=new OrderedList();
 a1=new Aluno("Maria","000000"); 
 a2=new Aluno("Jorge","123456");
 a3=new Aluno("Jose","999999");
 ListaAlunos.addElement(a1); 
 ListaAlunos.addElement(a2); 
 ListaAlunos.addElement(a3); 
 ListaAlunos.printList();
 System.out.println("Fim");
 }
}
Resultado
Maria-000000
Jorge-123456
Jose-999999
Fim
*