TADs Vector, Lista e Sequência
ATAI
1
TAD Vector



Uma sequencia S de n elementos
Rank (posição) do elemento e da sequencia S indica o número de elementos antes de e em S.
TAD Vector suporta os seguintes métodos principais:

elemAtRank (r): retorna o elemento da S que esta na posição r.
Erro : se r < 0 ou r > n-1, onde n é o numero actual de elementos.
Entrada: int; Saída: Objecto

replaceAtRank (r, e): Substitui o elemento na posição r com e e retorna o
objecto substituído.
Erro : se r < 0 ou r > n-1, onde n é o numero actual de elementos
Entrada: int r e Objecto e; Saída: Objecto

insertAtRank (r, e): Insere um novo elemento e na posição r.
Erro : se r < 0 ou r > n-1, onde n é o numero de elementos antes da inserção
Entrada: int r e Objecto e; Saída: Nenhuma

removeAtRank (r): Remove da sequencia S o elemento que esta na posição r.
Erro : se r < 0 ou r > n-1, onde n é o numero actual de elementos.
Entrada: int r; Saída: Objecto
2
Exemplo de execução
Operação
Output
S
insertAtRank(0,7)
-
(7)
insertAtRank(0,4)
-
(4, 7)
elemAtRank(1)
7
(4, 7)
insertAtRank(2,2)
-
(4, 7, 2)
error
(4, 7, 2)
removeAtRank(1)
7
(4, 2)
insertAtRank(1,5)
-
(4, 5, 2)
insertAtRank(1,3)
-
(4, 3, 5, 2)
insertAtRank(4,9)
-
(4, 3, 5, 2, 9)
elemAtRank(2)
5
(4, 3, 5, 2, 9)
elemAtRank(3)
3
Implementação do Deque com TAD Vector
Métodos Deque
Métodos do Vector
tamanho()
size()
estaVazia()
isEmpty()
primeiro()
elemAtRank(0)
ultimo()
elemAtRank(size()-1)
inserirPrimeiro(e)
insertAtRank(0,e)
inserirUltimo(e)
insertAtRank(size(),e)
removePrimeiro()
removeAtRank(0)
removerUltimo()
removeAtRank(size()-1)
4
Implementação estática do TAD Vector

Pseudo-Codigo:
Algoritmo insertAtRank(r,e):
for i = n - 1, n - 2, ... , r do
S[i+1]  s[i]
S[r]  e
nn+1
Algoritmo removeAtRank(r):
e  S[r]
for i = r, r + 1, ... , n - 2 do
S[i]  S[i + 1]
nn-1
return
5
Implementação do TAD Vector com classe
Vector da Java
Métodos do TAD Vector
Métodos da classe Vector
(java.util.Vector)
size()
size()
isEmpty()
isEmpty()
elemAtRank(r)
get(r)
replaceAtRank(r,e)
set(r,e)
insertAtRank(r,e)
add(r,e)
removeAtRank(r)
remove(r)
6
Implementação dinâmica do TAD Vector (lista
duplamente ligada) – inserir elemento
Lista antes da inserção:
Criar novo nó:
Lista depois da inserção:
7
Implementação dinâmica do TAD Vector (lista
duplamente ligada) – inserir elemento
public void insertAtRank (int rank, Object element)
throws BoundaryViolationException {
if (rank < 0 || rank > size())
throw new BoundaryViolationException(“invalid rank”);
DLNode next = nodeAtRank(rank); // the new node
//will be right before this
DLNode prev = next.getPrev(); // the new node
//will be right after this
DLNode node = new DLNode(element, prev, next);
// new node knows about its next & prev. Now
// we tell next & prev about the new node.
next.setPrev(node);
prev.setNext(node);
size++;
}
8
Implementação dinâmica do TAD Vector (lista
duplamente ligada) – apagar elemento
Lista antes da operação:
Apagar nó:
Lista depois da operação:
9
Implementação dinâmica do TAD Vector (lista
duplamente ligada) – apagar elemento
public Object removeAtRank (int rank) throws
BoundaryViolationException
{
if (rank < 0 || rank > size()-1)
throw new BoundaryViolationException(“Invalid rank.”);
DLNode node = nodeAtRank(rank); // node to be removed
DLNode next = node.getNext(); // node before it
DLNode prev = node.getPrev(); // node after it
prev.setNext(next);
next.setPrev(prev);
size--;
return node.getElement(); // returns the element of the
// deleted node
}
10
Implementação dinâmica do TAD Vector (lista
duplamente ligada) – procura de elemento
numa posição
private DLNode nodeAtRank (int rank) {
// auxiliary method to find the node of the
//
element with the given rank
DLNode node;
if (rank <= size()/2) { //scan forward from head
node = header.getNext();
for (int i=0; i < rank; i++)
node = node.getNext();
}else { // scan backward from the tail
node = trailer.getPrev();
for (int i=0; i < size()-rank-1 ; i++)
node = node.getPrev();
}
return node;
}
11
Passagem de nó para o elemento corrente
Noção de elemento corrente (current position)



Noção intuitiva de “ lugar” de um elemento
Elemento corrente é definido de um modo relativo (relação
antes/depois)
Elemento corrente é um TAD Position que só possui um método:
element(): Retorna o elemento corrente
Position é uma abstracção


Na implementação dinâmica: Position é a referência para um
nó, logo element() retorna o Objecto armazenado no nó.
Na implementação estática: Position é o indice do array, logo
element() retorna o Objecto armazenado no array no indice
indicado.
12
TAD Lista


TAD Lista - TAD sequencia baseado na noção de elemento corrente
Métodos genéricos:


size(), isEmpty()
Métodos selectores:

isFirst(p), isLast(p)


first(), last()


Entrada: Position p; Saída: Position
Métodos modificadores:

swapElements(p,q)





Entrada: Position p e Position q ; Saída: nenhuma
replaceElement(p,e)


Entrada: nenhuma; Saída: Position
before(p), after(p)


Entrada: Position p; Saída: Boolean
Entrada: Position p e Object e ; Saída: Object (que estava na posição p)
insertFirst(e), insertLast(e)
insertBefore(p,e), insertAfter(p,e)
remove(p)
Cada método é implementadoe em O(1), se utilizar uma estrutura dinâmica
representada pela lista duplamente ligada.
13
Interface List
public interface List {
public int size();
public boolean isEmpty();
public boolean isFirst (Position p) throws InvalidPositionException;
public boolean isLast (Position p) throws InvalidPositionException;
public Position first() throws EmptyContainerException;
public Position last() throws EmptyContainerException;
public Position before (Position p)
throws InvalidPositionException, BoundaryViolationException;
public Position after (Position p)
throws InvalidPositionException, BoundaryViolationException;
public Position insertBefore (Position p, Object element)
throws InvalidPositionException;
public Position insertAfter (Position p, Object element)
throws InvalidPositionException;
public Position insertFirst (Object element);
public Position insertLast (Object element);
public Object remove (Position p) throws InvalidPositionException;
public Object replaceElement (Position p, Object element)
throws InvalidPositionException;
public void swapElements (Position a, Position b)
throws InvalidPositionException;
}
14
Interface Position
Interface
Position {
public Object element() throws InvalidPositionException
}
15
Classe DNode
class DNode implements Position {
private DNode prev, next;// References to the nodes before and after
private Object element; // Element stored in this position
// Constructor
public DNode (DNode newPrev, DNode newNext, Object elem) {
prev = newPrev;
next = newNext;
element = elem;
}
// Method from interface Position
public Object element() throws InvalidPositionException {
if ((prev == null) && (next == null))
throw new InvalidPositionException("Position is not in a list!");
return element;
}
// Accessor methods
public DNode getNext() { return next; }
public DNode getPrev() { return prev; }
// Update methods
public void setNext (DNode newNext) { next = newNext; }
public void setPrev (DNode newPrev) { prev = newPrev; }
public void setElement (Object newElement) { element = newElement; }
}
16
Implementação dinâmica (lista duplamente
ligada) do TAD Lista
public class NodeList implements List {
protected int numElts;
protected DNode header, trailer;
// Number of items in the list
// Special sentinels
// Constructor; O(1) time
public NodeList() {
numElts = 0;
header = new DNode(null, null, null); // create header
trailer = new DNode(header, null, null);
// create trailer
header.setNext(trailer);
// make header and trailer point to each
other
}
// Simple accessor methods:
public int size() { return numElts; }
public boolean isEmpty() { return (numElts < 1); }
public boolean isFirst (Position p)
throws InvalidPositionException {
DNode v = checkPosition(p);
return v.getPrev() == header;
}
// O(1) time
// O(1) time
// O(1) time
17
Implementação dinâmica (lista duplamente
ligada) do TAD Lista
// Convenience function; O(1) time
protected DNode checkPosition(Position p)
throws InvalidPositionException {
if (p == null)
throw new InvalidPositionException
("Null Position passed to NodeList.");
if (p == header)
throw new InvalidPositionException
("The header node is not a valid position");
if (p == trailer)
throw new InvalidPositionException
("The trailer node is not a valid position");
try {
DNode temp = (DNode)p;
if ((temp.getPrev() == null) || (temp.getNext() == null))
throw new InvalidPositionException
("Position does not belong to a valid NodeList");
return temp;
} catch (ClassCastException e) {
throw new InvalidPositionException
("Position is of wrong type for this container.");
}
}
18
Implementação dinâmica (lista duplamente
ligada) do TAD Lista
public Position first()
// O(1) time
throws EmptyContainerException {
if (isEmpty())
throw new EmptyContainerException("List is empty");
return header.getNext();
}
public Position before (Position p)
// O(1) time
throws InvalidPositionException, BoundaryViolationException
{
DNode v = checkPosition(p);
DNode prev = v.getPrev();
if (prev == header)
throw new BoundaryViolationException
("Cannot advance past the beginning of the list");
return prev;
}
19
Implementação dinâmica (lista duplamente
ligada) do TAD Lista
public Position insertBefore (Position p, Object element)
throws InvalidPositionException {// O(1) time
DNode v = checkPosition(p);
numElts++;
DNode newNode = new DNode(v.getPrev(), v, element);
v.getPrev().setNext(newNode);
v.setPrev(newNode);
return newNode;
}
public Position insertFirst (Object element) {// O(1) time
numElts++;
DNode newNode = new DNode(header, header.getNext(), element);
header.getNext().setPrev(newNode);
header.setNext(newNode);
return newNode;
}
20
Implementação dinâmica (lista duplamente
ligada) do TAD Lista
public Object remove (Position p)
// O(1) time
throws InvalidPositionException {
DNode v = checkPosition(p);
numElts--;
DNode vPrev = v.getPrev();
DNode vNext = v.getNext();
vPrev.setNext(vNext);
vNext.setPrev(vPrev);
Object vElem = v.element();
// unlink the position from the list and make it invalid
v.setNext(null);
v.setPrev(null);
return vElem;
}
21
Implementação dinâmica (lista duplamente
ligada) do TAD Lista
public Object replaceElement (Position p, Object element)
throws InvalidPositionException { // O(1) time
DNode v = checkPosition(p);
Object oldElt = v.element();
v.setElement(element);
return oldElt;
}
public void swapElements (Position a, Position b)
throws InvalidPositionException { // O(1) time
DNode pA = checkPosition(a);
DNode pB = checkPosition(b);
Object temp = pA.element();
pA.setElement(pB.element());
pB.setElement(temp);
}
22
TAD Sequencia


Combinação do TAD Vector
e TAD Lista (herança
multipla de interfaces)
Adiciona métodos que
fazem a ponte entre
posição (int) e elemento
corrente
-atRank(r) posiciona
elemento corrente
-rankOf(p) retorna a
posição do elemento p
23
Interface Sequencia
interface Sequence extends List, Vector {
// Additional "bridging" methods:
public Position atRank (int rank) throws
BoundaryViolationException;
public int rankOf (Position position) throws
InvalidPositionException;
}
24
Comparação da implementação do TAD
Sequencia
25
Implementação dinâmica (lista duplamente
ligada) do TAD Sequencia
public class NodeSequence extends NodeList implements Sequence {
// Check that rank is in the range [0,numElts-1]; O(1) time
protected void checkRank (int rank)
throws BoundaryViolationException {
if (rank < 0 || rank >= numElts)
throw new BoundaryViolationException("Rank " + rank +
" is invalid for this sequence of " + numElts + " elements.");
}
public Position atRank (int rank) {
DNode node;
checkRank(rank);
if (rank <= size()/2) { // scan forward from the head
node = header.getNext();
for (int i=0; i < rank; i++)
node = node.getNext();
}
else { // scan backward from the tail
node = trailer.getPrev();
for (int i=1; i < size()-rank; i++)
node = node.getPrev();
}
return node;
}
26
Implementação dinâmica (lista duplamente
ligada) do TAD Sequencia
// . . . (skipping methods elemAtRank(r) and rankOf(p))
public void insertAtRank (int rank, Object element)
throws BoundaryViolationException { // O(n) time
if (rank == size()) // we shouldn't checkRank in this case
insertLast(element);
else {
checkRank(rank);
insertBefore(atRank(rank), element);
}
}
public Object removeAtRank (int rank)
// O(n) time
throws BoundaryViolationException {
checkRank(rank);
return remove(atRank(rank));
}
public Object replaceAtRank (int rank, Object element)
throws BoundaryViolationException { // O(n) time
checkRank(rank);
return replaceElement(atRank(rank),element);
}
}
27