Cátia Vaz

1

Tipos de Dados Abstratos

Algoritmos e Estruturas de Dados Verão 2012

Cátia Vaz

2

Tipos Abstratos n  Um tipo abstrato é:

n  um tipo genérico de dados, dos quais não se conhece os valores

n  uma interface que define os acessos e as operações sobre os dados

n  O conjunto das propriedades algébricas da interface, que delimitam as possíveis implementações.

n  Um programa que usa um tipo abstrato é um cliente. O cliente não tem acesso à implementação.

n  Um programa que especifique o tipo de dados é uma implementação.

Cátia Vaz

3

Pilha - Stack n  Operações abstratas:

n  inicialização; n  colocação de um elemento na pilha; n  remoção de um elemento (o último colocado); LIFO n  indicar se pilha está vazia.

n  interface para uma pilha que contenha inteiros: Usando a mesma interface,

podem ser definidas várias implementações!

Cátia Vaz

public interface intStack{ public boolean empty(); public void push(int i);

public int pop(); }

4

Pilha - Stack n  Operações abstratas:

n  inicialização; n  colocação de um elemento na pilha; n  remoção de um elemento (o último colocado); LIFO n  indicar se pilha está vazia.

n  interface para uma pilha genérica: Usando a mesma interface,


Cátia Vaz

public interface Stack< E > { public boolean isEmpty(); public E push(E i); public E pop(); public E peek(); }

5

Pilha (Stack) - inserção

6

Pilha (Stack) - remoção

7

Implementação do tipo pilha usando um array

Cátia Vaz

//Não compila!! public class StackArray<E> implements Stack<E>{ private E[] s; private int top; public StackArray(int capacity) { s=new E[capacity]; } //! a criação de um array genérico não é permitida em Java public boolean isEmpty(){ return top == 0; } public E peek() { if(isEmpty()) throw new EmptyStackException(); return s[top-1]; } public E push(E item) { if( top == s.length ) return null; s[top++] = item; return item; } public E pop() { if(isEmpty()) throw new EmptyStackException(); E e = s[--top]; s[top] = null; return e; } }

8

Implementação do tipo pilha usando um array

Cátia Vaz

public class StackArray<E> implements Stack<E>{ private E[] s; private int top; public StackArray(int capacity) { s= ( E[] ) new Object[capacity]; //solução! } public boolean isEmpty(){ return top == 0; } public E peek() { if(isEmpty()) throw new EmptyStackException(); return s[top-1]; } public E push(E item) { if( top == s.length ) return null; s[top++] = item; return item; } public E pop() { if(isEmpty()) throw new EmptyStackException(); E e = s[--top]; s[top] = null; return e; } }

Vantagens: simplicidade. Desvantagens: tamanho máximo limitado à partida.

9

Lista Simplesmente Ligada n  Uma lista ligada é uma colecção de objectos, designados por

nós , em que cada um contêm dados e apenas uma referência para outro nó, de modo a formarem uma lista. O primeiro nó é designado por head node.

n  Uma lista ligada diz-se simplesmente ligada quando cada nó contém uma referência para o próximo nó.

private class Node<E>{ private E data; private Node next; ...

} Exemplo:

Cátia Vaz

:SLinkedList head

:Node item next

:Node item next

“c” “g” null

10

Implementação do tipo pilha usando um lista ligada

Cátia Vaz

public class StackList<E> implements Stack<E>{ private static class Node<E> { E item; Node<E> next; Node(E i, Node<E> n){ item=i; next = n;} } private Node<E> head; public boolean isEmpty() {return head == null; } public E peek() { if(isEmpty()) throw new EmptyStackException(); return head.item; } public E push(E item) { head = new Node<E>(item, head); return item; } public E pop() { if(isEmpty()) throw new EmptyStackException(); E item = head.item; head = head.next;

return item; } }

Vantagens: - aumenta e diminui consoante se inserem ou removem novos elementos na pilha. Desvantagens: - ocupa mais memória. - acesso mais lento.

11

Que estrutura de dados escolher?

§  Depende : n  das operações que sejam mais frequentes no algoritmo a

implementar: n  Se a escolha for entre arrays e listas, dever-se-á escolher:

n  arrays se forem predominantes as operações de acesso e modificação;

n  listas se forem predominantes as operações de inserção e remoção.

n  Usar listas simples, se estas operações ocorrem sempre no início. n  Usar listas simples com ponteiro adicional para o fim da lista,

se a inserção se fizer no fim e a remoção no início. n  da previsibilidade sobre a memória necessária:

n  o uso de arrays pressupõe que se saiba que memória é suficiente;

n  quando não é previsível é necessário gerir a memória dinamicamente.

Cátia Vaz

PriorityQueue

12

public interface PriorityQueue<E>{ public void add(E elem, P prio, KeyExtractor<E> keyExtractor); public E pick(); public E poll(); public E update(int key, P prio); public void remove(int key); }

public interface KeyExtractor<E>{ public int getKey(E e); }

13

Fila-Queue n  Operações abstratas:

n  inicialização; n  colocação de um elemento na fila; n  remoção de um elemento (FIFO); n  indicar se fila está vazia.

n  interface para uma fila : Usando a mesma interface,


Cátia Vaz

public interface Queue<E>{ public boolean isEmpty(); public boolean offer(E i); public E poll(); public E remove(); public E peek(); }

14

Fila (Queue) - inserção

15

Fila (Queue) - remoção

16

Implementação do tipo fila usando um array

public class QueueArray<E> implements Queue<E> { private E[] q; private int size, head, tail; public QueueArray(int maxN) { q=(E[])new Object[maxN]; } public boolean isEmpty() { return size == 0 ;} public boolean offer(E e){ if( size == q.length) return false; q[tail] = e; tail = (tail+1) % q.length; ++size;

return true; } public E remove() { if(isEmpty()) throw new NoSuchElementException(); E e= q[head]; q[head]= null; head= (head+1)%q.length; --size; return e; } public E poll(){ return ( size == 0 ) ? null : remove();} public E peek() {return ( size == 0 ) ? null : q[head]; } }

17

Implementação do tipo fila usando uma lista ligada

public class QueueList<E> implements Queue<E> { private static class Node<E> { E item; Node<E> next;

Node() { next=this; } Node(E i, Node<E> n) { item=i; next = n; }

} private Node<E> tail = new Node<E>(); public boolean isEmpty() { return tail == tail.next; } public boolean offer(E e){ tail.next = new Node<E>( e, tail.next ); tail = tail.next;

return true; } public E remove() {

if(isEmpty()) throw new NoSuchElementException(); Node<E> rem = tail.next.next; tail.next.next = rem.next; if ( rem == tail ) tail = tail.next; return rem.item; } public E poll() { return ( isEmpty() ) ? null : remove(); } public E peek() { return ( isEmpty()) ? null :

tail.next.next.item; } }

18

ADTs §  ADTs permitem programação modular:

§  separam o programa em módulos mais pequenos; §  clientes diferentes podem partilhar a mesma ADT.

§  ADTs permitem o encapsulamento: §  mantêm-se os módulos independentes; §  podem-se substituir as várias classes que implementam a

mesma interface, sem alterar o cliente. §  Aspectos do desenho de uma ADT:

§  especificação formal do problema; §  a implementação tem tendência a tornar-se obsoleta.

Cátia Vaz

19

Lista duplamente ligada Inserção

20

Lista duplamente ligada Pesquisa

21

Lista duplamente ligada Remoção

22

Lista Duplamente Ligada

Cátia Vaz

public interface DList<E> extends Iterable<E>{ public int size(); public boolean isEmpty(); public void add(E e); public boolean remove(E e); }

23

Iteradores

Cátia Vaz

public interface Iterable<E> { public Iterator<E> iterator(); }

public interface Iterator<E> { public boolean hasNext(); public E next(); public void remove(); }

24


Cátia Vaz

public class DLinkedList1<E> implements DList<E> { private static class DNode<T> { public DNode<T> next, prev; public T key; public DNode() { } public DNode(T e ) { key=e; } } protected int size; protected DNode<E> head; public int size() { return size;} public boolean isEmpty(){ return head == null;} public void add(E e) { // Adiciona o elemento no inicio da lista ligada DNode<E> n=new DNode<E>(e); if(head!=null){ n.next=head; head.prev=n;} head=n; } //(continua...) }

25


Cátia Vaz

public class DLinkedList1<E> implements DList<E> { //(continuação...) // Remove o primeiro elemento da lista igual a e public boolean remove (E e){ DNode aux=search(e); if(aux!=null){ if(aux.prev != null) {aux.prev.next = aux.next;} else{head = aux.next;} if(aux.next != null){ aux.next.prev = aux.prev;} return true; } else return false; } protected DNode<E> search( E e ){ DNode<E> aux = head; while( aux != null && !aux.key.equals(e)) aux=aux.next; return aux; } //(continua...) }

26


Cátia Vaz

public class DLinkedList1<E> implements DList<E> { //(continuação...) public static <E> void show(DNode<E> l){ System.out.print("< "); while(l != null){ System.out.print(l.key+" "); l = l.next;} System.out.println(">"); } public void reverse() { DNode<E> iter = head, aux; while( iter != null ) { head = iter; aux = iter.next; iter.next = iter.prev; iter.prev = aux; iter = aux; } } //(continua...) }

27

Lista Duplamente Ligada-Iteradores

Cátia Vaz

public class DLinkedList1<E> implements DList<E> { //(continuação...) private class LinkedIterator implements Iterator<E> {

// Nó dos dados retornados pelo next() seguinte. protected DNode<E> node = head; /* Nó retornado pelo next() anterior. Como inicialmente não existiu next() referecia

null. Depois de um remove() permite assinalar que não existe next() anterior.*/ protected DNode<E> prev = null; // Retorna true se existem mais elementos para iterar. public boolean hasNext() { return node != null; } // Retorna o elemento da posição corrente e avança. public E next() { if ( node == null )throw new NoSuchElementException(); prev = node; node = node.next; // Avança return prev.key; } //(continua...) }

28

Lista Duplamente Ligada-Iteradores

Cátia Vaz

public class DLinkedList1<E> implements DList<E> { //(continuação...) public void remove() { // Se a última operação não foi next() lança excepção if ( prev == null ) throw new IllegalStateException(); // Remove o nó do elemnto retornado pelo último next DLinkedList1.this.remove(prev); prev = null; // Assinala que a operação anterior não foi um next() } }//termina a classe LinkedIterator public Iterator<E> iterator() {return new LinkedIterator(); } protected void remove( DNode<E> rem ){ if ( rem.next != null) rem.next.prev=rem.prev; if ( rem.prev != null ) rem.prev.next=rem.next; else head = rem.next; --size; } //(...) }

29

Lista com sentinela Inserção

30

Lista com sentinela Remoção

31

Lista com sentinela Pesquisa

32


Cátia Vaz

public interface DCList<E>{ public int size(); public boolean isEmpty(); public void add(E e); public boolean remove(E e); }

33

Lista Duplamente Ligada com Sentinela e Circular

Cátia Vaz

public class DLinkedList3<E> implements DCList<E>{ private static class DNode<E> { public DNode<E> next, prev;

public E key; public DNode() { } public DNode(E e ) { key=e; } } private int size;

protected DNode<E> dummy; public DLinkedList3() { dummy=new DNode<E>(); dummy.next= dummy.prev = dummy;} public int size() { return size;}

public boolean isEmpty() { return dummy.next == dummy;} //(continua...) }

34


Cátia Vaz

public class DLinkedList3<E> implements DCList<E> { //(continuação...) public E getFirst() { return dummy.next.key; } public E getLast() { return dummy.prev.key; } // Adiciona o elemento no fim da lista ligada public void add(E e) { DNode<E> n=new DNode<E>(e); ++size; n.prev=dummy.prev; n.next=dummy; dummy.prev.next=n; dummy.prev=n; } public boolean remove(E e){ DNode<E> aux=search(e); if(aux!=null){ aux.next.prev=aux.prev; aux.prev.next=aux.next; return true;} return false; } //(continua..) }

35


Cátia Vaz

public class DLinkedList3<E> implements DCList<E> { //(continuação...) public DNode<E> search(E e){ DNode<E> aux=dummy.next; while(aux!=dummy){ if(aux.key.equals(e)){ return aux;} aux=aux.next; } return null; } //(continua...) }

36


Cátia Vaz

public class DLinkedList3<E> implements DCList<E> { //(...)/*Move os nós da lista 2 para a lista 1. Assume que as duas listas estão ordenadas *pela ordem dada pelo comparador. A lista 1 permanece ordenada e a lista 2 fica vazia.*/ public static < E > DNode<E> merge( DNode<E> dummy1, DNode<E> dummy2,

Comparator<E> cmp) { DNode<E> head1 = dummy1.next; DNode<E> head2 = dummy2.next; while (head1 != dummy1 && head2 != dummy2 ) { if ( cmp.compare( head1.key, head2.key) <= 0 ) head1= head1.next; else { head2.prev = head1.prev; head1.prev.next = head2; head1.prev=head2; head2 = head2.next; head1.prev.next = head1; } } if ( head2 != dummy2 ) { head1.prev.next = head2; head2.prev = head1.prev; head1.prev = dummy2.prev; dummy2.prev.next = head1; } dummy2.next = dummy2.prev = dummy2; return dummy1; }}

37


Cátia Vaz

public class DLinkedList3<E> implements DList<E>{ //(...)/*Move os nós da lista 2 para a lista 1. Assume que as duas listas estão ordenadas *pela ordem dada pelo comparador. A lista 1 permanece ordenada e a lista 2 fica vazia.*/ public static < E > DNode<E> merge( DNode<E> dummy1, DNode<E> dummy2,

Comparator<E> cmp) { DNode<E> head1 = dummy1.next; DNode<E> head2 = dummy2.next; while (head1 != dummy1 && head2 != dummy2 ) { if ( cmp.compare( head1.key, head2.key) <= 0 ) head1= head1.next; else { head2.prev = head1.prev; head1.prev.next = head2; head1.prev=head2; head2 = head2.next; head1.prev.next = head1; } } if ( head2 != dummy2 ) { head1.prev.next = head2; head2.prev = head1.prev; head1.prev = dummy2.prev; dummy2.prev.next = head1; } dummy2.next = dummy2.prev = dummy2; return dummy1; }}

38

Exercício n  Implementar o algoritmo merge sort para

duas listas duplamente ligadas.

☺

Cátia Vaz

Documents

Cátia Vaz