Questo è il terzo post sulle Strutture Dati, in particolare oggi vedremo le Interfacce e le Implementazioni di TDA di tipo sequenza come ArrayList (si accede agli elementi attraverso il loro indice) e NodeList (dove il concetto principale e la Position). Raccomando la lettura di questo post agli studenti dell'Università degli studi di Salerno che studiano Informatica o Informatica Applicata e devono sostenere l'esame di Strutture Dati (SD) o di Laboratorio di Algoritmi e Strutture Dati (LASD) con il professor Salvatore La Torre. Invito i miei colleghi studenti a desistere dalla tentazione di presentarvi all'esame con i miei esercizi, (che per quanto io possa essere sicuro che siano corretti potrebbero comunque contenere errori) ma al massimo di usarli per confrontarli con i vostri.
Esercizi aggiornati al 8/04/2011
Codice per gli ArrayList
public interface IndexList <E>
extends Iterable<E>
{
public E get(int i) throws IndexOutOfBoundsException;
public E set(int i, E e) throws IndexOutOfBoundsException;
public void add(int i, E e) throws IndexOutOfBoundsException;
public E remove(int i) throws IndexOutOfBoundsException;
public int size();
public boolean isEmpty();
}
Implementare l’interfaccia IndexList utilizzando un array (classe ArrayIndexList)
Scrivere un programma di test della classe ArrayIndexList
Implementare l’interfaccia Queue mediante i metodi di IndexList (implementato dalla classe ArrayIndexList)
//ArrayIndexList implementato con array circolare estendibile
public class ArrayIndexList<E> implements IndexList<E>
{
private static final int CAPACITY = 1024;
private int size, capacity, f;
private E array[];
public ArrayIndexList()
{
this(CAPACITY);
}
public ArrayIndexList(int cap)
{
capacity = cap;
array = (E[])new Object[capacity];
size = 0;
}
public E get(int i) throws IndexOutOfBoundsException
{
checkIndex(i,size-1);
return array[map(i)];
}
public E set(int i, E e) throws IndexOutOfBoundsException
{
checkIndex(i,size-1);
E tmp = array[map(i)];
array[map(i)] = e;
return tmp;
}
public void add(int i, E e) throws IndexOutOfBoundsException
{
checkIndex(i,size);
if (size == capacity)
{
E nuovoArray[] = (E[]) new Object[capacity*2];
for(int j=0; j<size; j++)
nuovoArray[j] = array[map(j)];
array = nuovoArray;
capacity *= 2;
f = capacity-1;
}
if(i==0)
{
array[f] = e;
f = (f-1+capacity)%capacity;
}
if(i>0)
{
for(int j=size-1; j>= i; j--)
array[map(j+1)] = array[map(j)];
array[map(i)] = e;
}
size++;
}
public E remove(int i) throws IndexOutOfBoundsException
{
checkIndex(i,size-1);
E tmp = array[map(i)];
if(i == 0)
{
f = (f+1)%capacity;
}
else
{
for(int j=i; j<size-1; j++)
array[map(j)] = array[map(j+1)];
}
size--;
if (size<capacity/3)
{
E nuovoArray[] = (E[]) new Object[capacity/2];
for(int j=0; j<size; j++)
nuovoArray[j] = array[map(j)];
array = nuovoArray;
capacity /= 2;
f = capacity-1;
}
return tmp;
}
public int size()
{
return size;
}
public boolean isEmpty()
{
return (size == 0);
}
public String toString()
{
String stringa ="[ ";
for(int i=0;i<size;i++)
{
stringa += array[map(i)] + " ";
}
stringa += "] size:"+ size + " capacity:"+capacity+" f:"+f;
return stringa;
}
public int map(int i)
{
return (f+i+1)%capacity;
}
private void checkIndex(int i,int n)
{
if (i<0 || i>n)
throw new IndexOutOfBoundsException("errore indice "+i);
}
}
public class IndexListQueue<E> implements Queue<E>
{
private ArrayIndexList<E> coda;
public IndexListQueue()
{
coda = new ArrayIndexList<E>();
}
public int size()
{
return coda.size();
}
public boolean isEmpty()
{
return coda.isEmpty();
}
public E front() throws EmptyQueueException
{
if (isEmpty())
throw new EmptyQueueException();
return coda.get(0);
}
public void enqueue(E element)
{
coda.add(size(), element);
}
public E dequeue() throws EmptyQueueException
{
if (isEmpty())
throw new EmptyQueueException();
return coda.remove(0);
}
public String toString()
{
return "Queue with "+coda.toString();
}
}
Implementare l’interfaccia Deque mediante i metodi di IndexList (implementato dalla classe ArrayIndexList)
Analizzare la complessità dei metodi di Deque con questa implementazione
Modificare la classe ArrayIndexList in modo che i metodi addFirst e removeFirst di Deque abbiano tempo di esecuzione O(1)
public class IndexListDeque<E> implements Deque<E>
{
ArrayIndexList<E> dek;
public IndexListDeque()
{
dek = new ArrayIndexList<E>();
}
public int size()
{
return dek.size();
}
public boolean isEmpty()
{
return dek.isEmpty();
}
public E getFirst() throws EmptyDequeException
{
if(isEmpty())
throw new EmptyDequeException();
return dek.get(0);
}
public E getLast() throws EmptyDequeException
{
if(isEmpty())
throw new EmptyDequeException();
return dek.get(dek.size()-1);
}
public void addFirst(E element)
{
dek.add(0, element);
}
public void addLast(E element)
{
dek.add(dek.size()-1, element);
}
public E removeFirst() throws EmptyDequeException
{
if(isEmpty())
throw new EmptyDequeException();
return dek.remove(0);
}
public E removeLast() throws EmptyDequeException
{
if(isEmpty())
throw new EmptyDequeException();
return dek.remove(dek.size()-1);
}
public String toString()
{
return "Deque with " + dek.toString();
}
}
Codice su NodeList
public interface Position <E>
{
public E element();
}
public class DNode<E> implements Position<E>, Comparable<E>
{
private E element;
private DNode<E> prev, next;
private int idLista; //id Univoco della Lista
public DNode()
{
this(null,null,null);
}
public DNode(E e, DNode<E> p, DNode<E> n)
{
element = e;
prev = p;
next = n;
idLista = 0;
}
public DNode(E e, DNode<E> p, DNode<E> n, int idlist)
{
element = e;
prev = p;
next = n;
idLista = idlist;
}
public int getIdLista()
{
return idLista;
}
public void setIdLista(int id)
{
idLista = id;
}
public DNode<E> getPrev()
{
return prev;
}
public DNode<E> getNext()
{
return next;
}
//metodi modificatori
public void setElement(E e)
{
element = e;
}
public void setPrev(DNode<E> p)
{
prev = p;
}
public void setNext(DNode<E> n)
{
next = n;
}
public E element() {
return element;
}
public String toString()
{
return element.toString();
}
public int compareTo(E arg0)
{
Comparable<E> el = (Comparable<E>) element;
return el.compareTo(arg0);
}
}
public interface PositionList<E>
extends Iterable<E>
{
public Iterable <Position <E>> positions();
public int size();
public boolean isEmpty();
public Position <E> first() throws EmptyListException;
public Position <E> last() throws EmptyListException;
public Position <E> prev(Position <E> p) throws InvalidPositionException,
BoundaryViolationException;
public Position <E> next(Position <E> p) throws InvalidPositionException,
BoundaryViolationException;
public Position<E> addBefore(Position<E> p, E e) throws InvalidPositionException;
public Position<E> addAfter(Position<E> p, E e) throws InvalidPositionException;
public void addFirst(E e);
public void addLast(E e);
public E remove(Position<E> p) throws InvalidPositionException;
public E set (Position<E> p, E e) throws InvalidPositionException;
}
public class NodePositionList<E> implements PositionList<E>
{
private static int listsCounter = 0;
private int size;
protected DNode<E> header, trailer;
public NodePositionList()
{
listsCounter++;
size = 0;
header = new DNode<E>();
trailer = new DNode<E>(null,header,null);
header.setIdLista(listsCounter);
trailer.setIdLista(listsCounter);
}
public int size() {
return size;
}
public boolean isEmpty() {
return (size == 0);
}
public Position<E> first() throws EmptyListException
{
if (isEmpty())
throw new EmptyListException();
return header.getNext();
}
public Position<E> last() throws EmptyListException
{
if (isEmpty())
throw new EmptyListException();
return trailer.getPrev();
}
public Position<E> prev(Position<E> p) throws InvalidPositionException,
BoundaryViolationException
{
DNode<E> tmp = checkPosition(p);
if (tmp.getPrev() == header)
throw new BoundaryViolationException();
return tmp.getPrev();
}
public Position<E> next(Position<E> p) throws InvalidPositionException,
BoundaryViolationException
{
DNode<E> tmp = checkPosition(p);
if (tmp.getNext() == trailer)
throw new BoundaryViolationException();
return tmp.getNext();
}
public Position<E> addBefore(Position<E> p, E e) throws InvalidPositionException
{
DNode<E> tmp = checkPosition(p);
DNode<E> nuovoNodo = new DNode<E>(e,tmp.getPrev(),tmp,header.getIdLista());
tmp.getPrev().setNext(nuovoNodo);
tmp.setPrev(nuovoNodo);
size++;
return nuovoNodo;
}
public Position<E> addAfter(Position<E> p, E e) throws InvalidPositionException
{
DNode<E> tmp = checkPosition(p);
DNode<E> nuovoNodo = new DNode<E>(e,tmp,tmp.getNext(),header.getIdLista());
tmp.getNext().setPrev(nuovoNodo);
tmp.setNext(nuovoNodo);
size++;
return nuovoNodo;
}
public void addFirst(E e)
{
if (isEmpty())
{
DNode<E> nuovoNodo = new DNode<E>(e,header,trailer,header.getIdLista());
header.setNext(nuovoNodo);
trailer.setPrev(nuovoNodo);
size++;
}
else
{
DNode<E> tmp = header.getNext();
DNode<E> nuovoNodo = new DNode<E>(e,header,tmp,header.getIdLista());
tmp.setPrev(nuovoNodo);
header.setNext(nuovoNodo);
size++;
}
}
public void addLast(E e)
{
DNode<E> tmp = trailer.getPrev();
DNode<E> nuovoNodo = new DNode<E>(e,tmp,trailer,header.getIdLista());
tmp.setNext(nuovoNodo);
trailer.setPrev(nuovoNodo);
size++;
}
public E remove(Position<E> p) throws InvalidPositionException
{
DNode<E> tmp = checkPosition(p);
tmp.getPrev().setNext(tmp.getNext());
tmp.getNext().setPrev(tmp.getPrev());
size--;
return tmp.element();
}
public E set(Position<E> p, E e) throws InvalidPositionException
{
DNode<E> tmpnode = checkPosition(p);
E tmpEl = tmpnode.element();
tmpnode.setElement(e);
return tmpEl;
}
public DNode<E> checkPosition(Position<E> p) throws InvalidPositionException
{
if (p == null) throw new InvalidPositionException("null position");
if (p == header) throw new InvalidPositionException("header");
if (p == trailer) throw new InvalidPositionException("trailer");
try
{
DNode<E> temp = (DNode<E>) p;
// casting
if ((temp.getPrev() == null) || (temp.getNext() == null))
throw new InvalidPositionException("not in a NodeList");
if (temp.getIdLista() != header.getIdLista() || temp.getIdLista()==0)
throw new InvalidPositionException("Given position does not belong to NodeList "+header.getIdLista());
return temp;
}
catch (ClassCastException e)
{
throw new InvalidPositionException("not a DNode");
}
}
public String toString()
{
String stringa = "NodePositionlist id:"+ header.getIdLista() +" [ ";
DNode<E> aNode = header.getNext();
for(int i=0; i<size; i++)
{
stringa += aNode.element() + " ";
aNode = aNode.getNext();
}
stringa += "] size:"+size;
return stringa;
}
public PositionList<E> creaCopia()
{
NodePositionList<E> copia = new NodePositionList<E>();
DNode<E> oldNode = header.getNext();
for(int i=0; i<size(); i++)
{
copia.addLast(oldNode.element());
oldNode = oldNode.getNext();
}
return copia;
}
public Iterator<E> iterator()
{
/*
E[] tmp = (E[]) new Object[size];
DNode<E> aNode = header.getNext();
for(int i=0; i<size; i++)
{
tmp[i] = aNode.element();
aNode = aNode.getNext();
}
return new LinkedIterator<E>(tmp);*/
return new ElementIterator<E>(this);
}
public Iterable<Position<E>> positions()
{
PositionList<Position<E>> tmp = new NodePositionList<Position<E>>();
DNode<E> aNode = header.getNext();
for(int i=0; i<size-1; i++)
{
tmp.addLast(aNode);
aNode = aNode.getNext();
}
tmp.addLast(aNode);
return tmp;
}
/*Scrivere la funzione ricorsiva void reverse(PositionList<E> L)
che inverte la lista L.
Definizione ricorsiva di lista inversa di L=<e1,e2,...,en >
inversa(L)=L se n≤1
Inversa(L)= <en>+ inversa(<e1,...,en-1 >) se n>1
*/
//funzione ricorsiva versione 2
public void reverse(PositionList<E> L)
{
NodePositionList<E> lista = (NodePositionList<E>) L;
if (lista.size() > 1)
{
E tmp = lista.remove(lista.last());
lista.reverse(lista);
lista.addFirst(tmp);
}
}
/*
//funzione ricorsiva versione 1
public PositionList<E> reverse(PositionList<E> L)
{
NodePositionList<E> lista = (NodePositionList<E>) L;
if (lista.size() <= 1)
{
return lista;
}
else
{
E tmp = lista.remove(lista.last());
lista.reverse(lista).addFirst(tmp);
return lista;
}
}
*/
/*
//funzione non ricorsiva
public void reverse(PositionList<E> L)
{
ArrayStack<E> stack = new ArrayStack<E>();
while(!L.isEmpty())
stack.push(L.remove(L.first()));
while(!stack.isEmpty())
L.addLast(stack.pop());
}
*/
}
Post
Nessun commento:
Posta un commento