Listas Ordenadas e Listas Classificadas. 2 Sumário Fundamentos Listas Ordenadas Listas Classificadas

Embed Size (px)

Text of Listas Ordenadas e Listas Classificadas. 2 Sumário Fundamentos Listas Ordenadas Listas...

  • Slide 1
  • Listas Ordenadas e Listas Classificadas
  • Slide 2
  • 2 Sumrio Fundamentos Listas Ordenadas Listas Classificadas
  • Slide 3
  • 3 Conceito de Listas Listas so os containers mais simples que existem e tambm os mais versteis. Consideradas como tipos abstratos de dados listas so sries de itens e permitem incluso e excluso de elementos e a visitao a itens na ordem em que aparecem.
  • Slide 4
  • 4 Tipos especiais de Listas Podem ser definidos dois tipos especiais de listas: Listas ordenadas so aquelas nas quais a ordem ou posio dos itens relevante, independentemente de seu contedo e, portanto, pode ser modificada. Listas classificadas so listas ordenadas nas quais a ordem inerente ao contedo dos itens e no pode ser modificada. As abstraes destes tipos de listas so encontradas nas interfaces OrderedList e SortedList.
  • Slide 5
  • 5 Interfaces OrderedList e SortedList
  • Slide 6
  • 6 Fundamentos Considerar-se-o como fundamentos os padres de Projeto e as Hierarquias de classe, ou Framework, de Bruno Preiis. Em particular as interfaces Comparable Container SearchableContainer
  • Slide 7
  • Implementao Java
  • Slide 8
  • 8 Interface Comparable public interface Comparable { boolean isLT (Comparable object); boolean isLE (Comparable object); boolean isGT (Comparable object); boolean isGE (Comparable object); boolean isEQ (Comparable object); boolean isNE (Comparable object); int compare (Comparable object); }
  • Slide 9
  • 9 Interface Container public interface Container extends Comparable { int getCount(); boolean isEmpty(); boolean isFull(); void purge(); void accept(Visitor visitor); Enumeration getEnumeration(); }
  • Slide 10
  • 10 Classe Abstrata AbstractContainer public abstract class AbstractContainer extends AbstractObject implements Container { protected int count; public int getCount() { return count; } public boolean isEmpty() { return getCount() == 0; } public boolean isFull() { return false; } //... }
  • Slide 11
  • 11 Interface SearchableContainer public interface SearchableContainer extends Container { boolean isMember(Comparable object); void insert(Comparable object); void withdraw(Comparable obj); Comparable find(Comparable object); }
  • Slide 12
  • Listas Ordenadas
  • Slide 13
  • 13 Listas Ordenadas - Sumrio Introduo Implementao sobre Arrays Implementao sobre Listas Encadeadas
  • Slide 14
  • 14 Introduo As listas Ordenadas sero apresentadas por uma interface e duas classes correspondendo a dois tipos de implementao, sobre arrays e sobre listas encadeadas: Interface OrderedList Classe OrderedListAsArray Classe OrderedListAsLinkedList
  • Slide 15
  • 15 Interface OrderedList public interface OrderedList extends SearchableContainer { Comparable get (int i); Cursor findPosition (Comparable object); }
  • Slide 16
  • 16 Interface OrderedList Esta interface estende SearchableContainer e apresenta os mtodos get e findPosition. Por sua vez SearchableContainer dispe dos mtodos: insert withdraw find isMember
  • Slide 17
  • 17 Mtodo findPosition de OrderedList O mtodo findPosition retorna um Cursor, cuja interface ser exibida a seguir e que dispe dos mtodos: getDatum insertAfter insertBefore withdraw
  • Slide 18
  • 18 Interface Cursor public interface Cursor { Comparable getDatum(); void insertAfter(Comparable object); void insertBefore(Comparable object); void withdraw(); }
  • Slide 19
  • 19 Interface SortedList public interface SortedList extends SearchableContainer { Comparable get(int i); Cursor findPosition(Comparable object); }
  • Slide 20
  • Implementao sobre Arrays
  • Slide 21
  • 21 Classe OrderedListAsArray public class OrderedListAsArray extends AbstractSearchableContainer implements OrderedList { protected Comparable[] array; //... }
  • Slide 22
  • 22 Construtor e mtodo de insero de item no final da lista public class OrderedListAsArray extends AbstractSearchableContainer implements OrderedList { protected Comparable[] array; public OrderedListAsArray(int size) { array = new Comparable [size]; } public void insert(Comparable object) { if(count == array.length) throw new ContainerFullException (); array[count] = object; ++count; } //... }
  • Slide 23
  • 23 Mtodos isMember e find public class OrderedListAsArray extends AbstractSearchableContainer implements OrderedList { protected Comparable[] array; public boolean isMember(Comparable object) { for(int i = 0; i < count; ++i) if(array[i] == object) return true; return false; } public Comparable find(Comparable arg) { for(int i = 0; i < count; ++i) if(array[i].isEQ(arg)) return array[i]; return null; } //... }
  • Slide 24
  • 24 Mtodo withdraw (1) public class OrderedListAsArray extends AbstractSearchableContainer implements OrderedList { protected Comparable[] array; public void withdraw(Comparable object) { if(count == 0) throw new ContainerEmptyException (); int i = 0; while(i < count && array[i] != object) ++i; if(i == count) throw new IllegalArgumentException("objeto no encontrado");
  • Slide 25
  • 25 Mtodo withdraw (2) for( ; i < count - 1; ++i) array[i] = array[i + 1]; array[i] = null; --count; } //... }
  • Slide 26
  • 26 Posio de um item em uma lista por meio da Classe Interior OrderedListAsArray.MyCursor (1) public class OrderedListAsArray extends AbstractSearchableContainer implements OrderedList { protected Comparable[] array; protected class MyCursor implements Cursor { int offset; MyCursor (int offset) { this.offset = offset; }
  • Slide 27
  • 27 Posio de um item em uma lista por meio da Classe Interior OrderedListAsArray.MyCursor (2) public Comparable getDatum() { if(offset = count) throw new IndexOutOfBoundsException(); return array [offset]; } //... } //... }
  • Slide 28
  • 28 Busca de um item e acesso por posio Mtodos findPosition e get de OrderedListAsArray public class OrderedListAsArray extends AbstractSearchableContainer implements OrderedList { protected Comparable[] array; public Cursor findPosition(Comparable object) { int i = 0; while(i < count && array[i].isNE(object)) ++i; return new MyCursor(i); } public Comparable get(int offset) { if(offset = count) throw new IndexOutOfBoundsException(); return array[offset]; } //... }
  • Slide 29
  • 29 Insero de itens em posies arbitrrias Mtodos insertBefore e insertAfter de OrderedListAsArray
  • Slide 30
  • 30 Mtodo insertAfter (1) public class OrderedListAsArray extends AbstractSearchableContainer implements OrderedList { protected Comparable[] array; protected class MyCursor implements Cursor { int offset;
  • Slide 31
  • 31 Mtodo insertAfter (2) public void insertAfter (Comparable object) { if(offset = count) throw new IndexOutOfBoundsException(); if(count == array.length) throw new ContainerFullException(); int insertPosition = offset + 1; for(int i = count; i > insertPosition; --i) array[i] = array[i - 1]; array[insertPosition] = object; ++count; } //... } //... }
  • Slide 32
  • 32 Mtodo insertBefore (1) public class OrderedListAsArray extends AbstractSearchableContainer implements OrderedList { protected Comparable[] array; protected class MyCursor implements Cursor { int offset;
  • Slide 33
  • 33 Mtodo insertBefore (2) public void insertBefore(Comparable object) { if(offset = count) throw new IndexOutOfBoundsException(); if(count == array.length) throw new ContainerFullException(); int insertPosition = offset; for(int i = count; i > insertPosition; --i) array[i] = array[i - 1]; array[insertPosition] = object; ++count; } //... } //... }
  • Slide 34
  • 34 Excluso de itens em posies arbitrrias Mtodo withdraw de OrderedListAsArray
  • Slide 35
  • 35 Mtodo withdraw (1) public class OrderedListAsArray extends AbstractSearchableContainer implements OrderedList { protected Comparable[] array; protected class MyCursor implements Cursor { int offset;
  • Slide 36
  • 36 Mtodo withdraw (2) public void withdraw() { if(offset = count) throw new IndexOutOfBoundsException(); if(count == 0) throw new ContainerEmptyException(); int i = offset; while(i < count - 1) { array[i] = array[i + 1]; ++i; } array[i] = null; --count; } //... } //... }
  • Slide 37
  • Implementao sobre Listas Encadadeadas
  • Slide 38
  • 38 Mtodos da classe LinkedList getDatum getNext Construtor e purge getHead getTail isEmpty getFirst getLast prepend append assign extract insertAfter insertBefore
  • Slide 39
  • 39 Classe OrderedListAsLinkedList public class OrderedListAsLinkedList extends AbstractSearchableContainer implements OrderedList { protected LinkedList linkedList; //... }
  • Slide 40
  • 40 Construtor e mtodos de insero de objeto (1) public class OrderedListAsLinkedList extends AbstractSearchableContainer implements OrderedList { protected LinkedList linkedList; public OrderedListAsLinkedList() { linkedList = new LinkedList(); } public void insert(Comparable object) { linkedList.append(object); ++count; }
  • Slide 41