Pages: [1]   Go Down
Print
Author Topic: Liste circolari  (Read 1316 times)
0 Members e 1 Utente non registrato stanno visualizzando questa discussione.
Vivynz
Forumista Eroico
*****
Offline Offline

Gender: Female
Posts: 2.033


File reality.sys corrupted, Reboot Universe? Y/N


« 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;

}
}
}

Logged

L'odrine delle lttere dnetro una praorla non è ipmortatne, la sloa cosa ipmortatne è che la pmria e l'utlima ltteera sinao nel potso giutso. Il rseto può essree in un dsiodrine più totlae e voi ptoerte smerpe lggeree sneza porblmea.
rox
Forumista
***
Offline Offline

Posts: 633


« Reply #1 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.
Logged

Una macchina è in grado di lavorare come cinquanta uomini comuni, ma nessuna macchina può svolgere il lavoro di un uomo straordinario.
Vivynz
Forumista Eroico
*****
Offline Offline

Gender: Female
Posts: 2.033


File reality.sys corrupted, Reboot Universe? Y/N


« Reply #2 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..
Logged

L'odrine delle lttere dnetro una praorla non è ipmortatne, la sloa cosa ipmortatne è che la pmria e l'utlima ltteera sinao nel potso giutso. Il rseto può essree in un dsiodrine più totlae e voi ptoerte smerpe lggeree sneza porblmea.
rox
Forumista
***
Offline Offline

Posts: 633


« Reply #3 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.
Logged

Una macchina è in grado di lavorare come cinquanta uomini comuni, ma nessuna macchina può svolgere il lavoro di un uomo straordinario.
Eleirgab
Apprendista Forumista
**
Offline Offline

Gender: Male
Posts: 344


Apprezzatemi ora. Eviterete la fila


WWW
« Reply #4 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

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

Collettivo SDAI

-----BEGIN GEEK CODE BLOCK-----
Version: 3.1
GIT d-- s+:+ a-- C++ UL++ P L+++ E- W+++>$ N? o? K- w-- O? M V? PS++ PE- Y+ PGP- t 5? X+ R>+ tv-- b++ DI+++ D- G e h! r y+
------END GEEK CODE BLOCK-----
Vivynz
Forumista Eroico
*****
Offline Offline

Gender: Female
Posts: 2.033


File reality.sys corrupted, Reboot Universe? Y/N


« Reply #5 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;
}
}
}
Logged

L'odrine delle lttere dnetro una praorla non è ipmortatne, la sloa cosa ipmortatne è che la pmria e l'utlima ltteera sinao nel potso giutso. Il rseto può essree in un dsiodrine più totlae e voi ptoerte smerpe lggeree sneza porblmea.
Pages: [1]   Go Up
Print
Jump to: