Forum Informatica Unict

LAUREA TRIENNALE (D.M. 270/04) => Programmazione 2, 9 CFU => Topic started by: Vivynz on 17-04-2009, 12:04:01



Title: Liste circolari
Post by: Vivynz on 17-04-2009, 12:04:01
Stavo provando ad implementare una lista circolare..non sapevo innanzitutto se usare una lista linkata o doppiamente linkata..ho provato con la seconda ma ho dei probl con l'inserimento ordinato e la ricerca(non ordinata...
cmq si può fare in modo diverso?o più semplice?
Code:
public class LinkedListCircolare
{
private Nodod head,tail;
public LinkedListCircolare()
{
head=tail=null;
}
public Nodod getHead()
{
return head;
}
public Nodod getTail()
{
return tail;
}
public boolean isEmpty()
{
return (head==null);
}
public void insertHead(Comparable c)
{
if(isEmpty())
head=tail=new Nodod(c);
else
{
head=new Nodod(c,head,tail);
head.getNext().setPrev(head);
}
tail.setNext(head);
head.setPrev(tail);
}
public void insertTail(Comparable c)
{
if(isEmpty())
head=tail=new Nodod(c);
else
{
tail=new Nodod(c,head,tail);
tail.getPrev().setNext(tail);
}
tail.setNext(head);
head.setPrev(tail);
}
public void insertOrdered(Comparable c)
{
if(isEmpty())
head=tail=new Nodod(c);
else
if(((Comparable)head.getInfo()).compareTo(c)>=0)
{
head=new Nodod(c,head,tail);
head.getNext().setPrev(head);
}
else
{
Nodod aux=head.getNext();
for(;aux.getNext()!=head&&((Comparable)aux.getNext().getInfo()).compareTo(c)<0;aux=aux.getNext());
if(aux.getNext()==head)
{
tail=new Nodod(c,null,tail);
tail.getPrev().setNext(tail);
}
else
{
aux.setNext(new Nodod(c,aux.getNext(),aux));
aux.getNext().getNext().setPrev(aux.getNext());
}

}
tail.setNext(head);
head.setPrev(tail);
}
public Comparable deleteHead()
{
if(isEmpty())
throw new EmptyListException();
else
{
Nodod aux=head;
if(head==tail)
head=tail=null;
else
{
head=head.getNext();
head.setPrev(tail);
tail.setNext(head);
}
return aux.getInfo();
}
}
public Comparable deleteTail()
{
if(isEmpty())
throw new EmptyListException();
else
{
Nodod aux=tail;
if(head==tail)
head=tail=null;
else
{
tail=tail.getPrev();
tail.setNext(head);
head.setPrev(tail);
}
return aux.getInfo();
}
}
public Comparable deleteKey(Comparable c)
{
if(isEmpty())
throw new EmptyListException();
else
{
if(((Comparable)head.getInfo()).compareTo(c)==0)
{
Nodod aux=head;
head=head.getNext();
tail.setNext(head);
head.setPrev(tail);
return aux.getInfo();
}
else
{
Nodod aux=head.getNext();
for(;aux!=head&&((Comparable)aux.getInfo()).compareTo(c)!=0;aux=aux.getNext());
if(aux!=head&&((Comparable)aux.getInfo()).compareTo(c)==0)
{
tail.setNext(head);
head.setPrev(tail);
return aux.getInfo();
}
tail.setNext(head);
head.setPrev(tail);
return null;
}

}
}
public Nodod search(Comparable c)
{
if(((Comparable)head.getInfo()).compareTo(c)==0)
return head;
else
{
Nodod aux=head.getNext();
for(;aux!=head&&((Comparable)aux.getInfo()).compareTo(c)!=0;aux=aux.getNext());
return aux;
}
}
public Nodod searchOrdered(Comparable c)
{
if(((Comparable)head.getInfo()).compareTo(c)==0)
return head;
else
{
Nodod aux=head.getNext();
for(;aux!=head&&((Comparable)aux.getInfo()).compareTo(c)<0;aux=aux.getNext());
if(aux!=head&&((Comparable)aux.getInfo()).compareTo(c)==0)
return aux;
return null;

}
}
}



Title: Re:Liste circolari
Post by: rox on 17-04-2009, 23:18:51
a prima vista(è un po' tardino quindi se posso proverò a rivederla domani) la lista sembrerebbe implementata correttamente.per quanto riguarda le semplificazioni ne ho trovate alcune.
potresti cambiare queste linee di codice
Code:
if(((Comparable)head.getInfo()).compareTo(c)>=0)
{
head=new Nodod(c,head,tail);
head.getNext().setPrev(head);
}
con
Code:
if(((Comparable)head.getInfo()).compareTo(c)>=0)
{
insertHead(c);
}
analogamente potresti agire qua
Code:
if(aux.getNext()==head)
{
tail=new Nodod(c,null,tail);
tail.getPrev().setNext(tail);
}
facendo un insertTail.
In ultima istanza volevo darti un consiglio.
quando fai l'inserimento ordinato o la cancellazione di un elemento da una lista,invece di utilizzare un solo nodo ausiliario,utilizzane 3.In questo modo ,quando uscirai dal ciclo for,avrai 3 nodi che ti rappresentano rispettivamente :il precedente del nodo che vuoi cancellare,il nodo stesso che vuoi cancellare,e il successivo del nodo che vuoi cancellare.forse non sono stato molto chiaro ma non so come dirlo a parole.se qualcosa di quello che ho detto non dovesse risultarti chiaro fammelo presente.se ti può essere d'aiuto posso postare il mio codice(anche se cmq io ho fatto una lista semplicemente linkata circolare ma cmq il principio è lo stesso).spero di esserti stato di aiuto.


Title: Re:Liste circolari
Post by: Vivynz on 18-04-2009, 07:30:57
per quanto riguarda le semplificazioni si è giusto, l'ho fatta in questo modo perchè altrimenti nel compito dovrei inserire tutti i metodi e se non servono è una perdita di tempo visto che non ne abbiamo infinito..per il resto ma cosa li uso a fare se c'è sia il getPrev che il getNext??in ogni caso quei 2metodi che ho detto prima non funzionano a dovere..


Title: Re:Liste circolari
Post by: rox on 18-04-2009, 14:47:34
i nodi servono per far diventare il codice + semplice(almeno a me mi semplifica molto).cmq a primo acchitto mi sembrava giusto il codice .magari poi lo guardo meglio.


Title: Re:Liste circolari
Post by: Eleirgab on 19-04-2009, 01:33:41
E' abbastanza tardi, ogni mio errore attribuitelo al sonno   :nono

Secondo me l'errore dell'inserimento ordinato è nella condizione di uscita dal for:
Code:
aux.getNext()!=head && [...]
Credo che il parametro non venga mai confrontato con l'ultimo elemento della lista, e quindi lo inserisce sempre in coda, anche se nn dovrebbe.
Forse risolverebbe il problema farlo così
Code:
aux!=head && [...]
e mettere nell'if
Code:
if(aux==head)
{
                                   insertTail(c);
}
il resto dovrebbe andare... Spero sia giusto .leggo

Per quanto riguarda l'ottimizzazione, direi che mantenere un'indice tail è inutile: se ne hai bisogno basta un head.getPrev()...


Title: Re:Liste circolari
Post by: Vivynz on 19-04-2009, 09:58:35
continuavo ad avere problemi sembravano aumentare anzixhè diminuire..e quindi ho ricominciato da capo utilizzando però una lista semplicemente linkata..e adesso tutto sembra funzionare a dovere...
Code:
public class LinkedListCircolare
{
private Nodo head,tail;
public LinkedListCircolare()
{
head=tail=null;
}
public boolean isEmpty()
{
return (head==null);
}
public Nodo getHead()
{
return head;
}
public Nodo getTail()
{
return tail;
}
public void insertHead(Comparable c)
{
if(isEmpty())
head=tail=new Nodo(c);
else
head=new Nodo(c,head);
tail.setNext(head);
}
public void insertTail(Comparable c)
{
if(isEmpty())
{
head=tail=new Nodo(c);
tail.setNext(head);
}
else
{
tail.setNext(new Nodo(c,head));
tail=tail.getNext();
}
}
public void insertOrdered(Comparable c)
{
if(isEmpty())
{
head=tail=new Nodo(c);
tail.setNext(head);
}
else
{
if(((Comparable)head.getInfo()).compareTo(c)>=0)
{
head=new Nodo(c,head);
tail.setNext(head);
}
else if(((Comparable)head.getNext().getInfo()).compareTo(c)>=0)
head.setNext(new Nodo(c,head.getNext()));
else
{
Nodo aux=head.getNext();
Nodo prec=head;
for(;aux!=head&&(((Comparable)aux.getNext().getInfo()).compareTo(c)<0);prec=aux,aux=aux.getNext());
if(aux==head)
{
tail.setNext(new Nodo(c,head));
tail=tail.getNext();
}
else
prec.setNext(new Nodo(c,aux));
}
}
}
public Comparable deleteHead()
{
if(isEmpty())
throw new EmptyListException();
else
{
Nodo aux=head;
if(head==tail)
head=tail=null;
else
{
head=head.getNext();
tail.setNext(head);
}
return aux.getInfo();
}
}
public Comparable deleteTail()
{
if(isEmpty())
throw new EmptyListException();
else
{
Nodo aux=head;
if(head==tail)
head=tail=null;
else
{
aux=aux.getNext();
Nodo prec=head;
for(;aux.getNext()!=head;prec=aux,aux=aux.getNext());
tail=prec;
tail.setNext(head);
}
return aux.getInfo();
}
}
public Comparable deleteKey(Comparable c)
{
if(isEmpty())
throw new EmptyListException();
else
{
Nodo aux=head;
if(((Comparable)head.getInfo()).compareTo(c)==0)
{
head=head.getNext();
tail.setNext(head);
}
else
{
aux=aux.getNext();
Nodo prec=head;
for(;aux!=head&&((Comparable)aux.getInfo()).compareTo(c)!=0;prec=aux,aux=aux.getNext());
if(aux==head)
return null;
else
if(aux==tail)
{
tail=prec;
tail.setNext(head);
}
else
{
prec.setNext(aux.getNext());
}
}
return aux.getInfo();
}
}
public Nodo search(Comparable c)
{
if(((Comparable)head.getInfo()).compareTo(c)==0)
return head;
else
{
Nodo aux=head.getNext();
for(;aux!=head&&((Comparable)aux.getInfo()).compareTo(c)!=0;aux=aux.getNext());
if(aux!=head&&((Comparable)aux.getInfo()).compareTo(c)==0)
return aux;
return null;
}
}
public Nodo searchOrdered(Comparable c)
{
if(((Comparable)head.getInfo()).compareTo(c)==0)
return head;
else
{
Nodo aux=head.getNext();
for(;aux!=head&&((Comparable)aux.getInfo()).compareTo(c)<0;aux=aux.getNext());
if(aux!=head&&((Comparable)aux.getInfo()).compareTo(c)==0)
return aux;
return null;
}
}
}