Pages: [1]   Go Down
Print
Author Topic: Inserimento ordinato in lista semplice....aiuto!  (Read 1242 times)
0 Members e 1 Utente non registrato stanno visualizzando questa discussione.
Daréios89
Forumista Eroico
*****
Offline Offline

Gender: Male
Posts: 2.679


La musica è la forma d'arte suprema.


« on: 22-08-2010, 15:22:39 »

Non capisco cperchè no mi riesce di fare l'inserimento ordinato e non capisco perchè. Il codice mi sembra lineare ma praticamente la lista rimane vuota:

Code:
public void add(Node node){

boolean added=false;
if(size==0){
head=(TripleNode)node;
return;
}
else{
Node prev=head; //conterrà il precedente

for(Node tmp=head; tmp!=null; tmp=tmp.getNext()){
if(node.compareTo(tmp)<1){

       node.setNext(tmp);
prev.setNext(node);
size++;
added=true;
return; //oppure break;
}
prev=tmp;

}
}

if(added==false)         //significa che non l'ho inserito e va messo alla fine
{
tail.setNext(node);  
node.setNext(null);
tail=(TripleNode)node;
}
}

Logged

"Utilizzare sempre de l'Hôpital.....è come andare a caccia di farfalle con un bazooka".
corel_86
Forumista
***
Offline Offline

Gender: Male
Posts: 570



« Reply #1 on: 22-08-2010, 16:50:02 »

Non capisco cperchè no mi riesce di fare l'inserimento ordinato e non capisco perchè. Il codice mi sembra lineare ma praticamente la lista rimane vuota:

Code:
public void add(Node node){

boolean added=false;
if(size==0){
head=(TripleNode)node;
return;
}
else{
Node prev=head; //conterrà il precedente

for(Node tmp=head; tmp!=null; tmp=tmp.getNext()){
if(node.compareTo(tmp)<1){

        node.setNext(tmp);
prev.setNext(node);
size++;
added=true;
return; //oppure break;
}
prev=tmp;

}
}

if(added==false)         //significa che non l'ho inserito e va messo alla fine
{
tail.setNext(node); 
node.setNext(null);
tail=(TripleNode)node;
}
}



Innanzitutto dovresti mettere le classi che compongono questo codice cosi possiamo vedere la logica che hai utilizzato.....per esempio:

  • l'operatore di casting TripleNode io non ho capito a cosa serve
  • la variabile size non è inizializzata dovresti utilizzare un metodo che ritorna la lunghezza della lista
  • node.compareTo(tmp)<1)!?!? dovresti confrontare il valore all'interno del nodo non confrontare tutto il  nodo utilizza la variabile info della classe NODO

inoltre secondo me non serve che controlli se l'elemento non è stato inserito utilizza il metodo InsertTail della lista che controlla se il nodo è arrivato alla fine e lo inserisce in coda......

Ovviamente sono soltanto consigli ma per poterti aiutare il codice deve essere il più leggibile possibile.......

saluti ciao ciao ciao ciao ciao
Logged

Se trovo qualcosa che non va lo faccio presente subito

Saluti ciaociao ciao

A.C.
Daréios89
Forumista Eroico
*****
Offline Offline

Gender: Male
Posts: 2.679


La musica è la forma d'arte suprema.


« Reply #2 on: 23-08-2010, 11:11:50 »

Si hai ragione, scusami.

L'esercizio è questo:

Code:
Si realizzino due classi che implementino le interfacce Node e LinkedList (descritte
nella pagina seguente) e che siano in grado gestire un insieme attraverso l'uso di
una lista linkata semplice.
Si scriva in seguito un programma Java che, utilizzando la nuova classe per la
gestione di un insieme, prenda in input un file contenente una sequenza di terne,
del tipo (a,b,c), e scriva in un file di output la medesima sequenza in cui le terne
sono state riordinate, in senso non decrescente, in base al valore degli elementi
contenuti nelle terne (ordinare sul primo valore; in caso di valore uguale ordinare sul
secondo valore; in caso di uguaglianza dei primi due valori ordinare sul terzo
valore).
Input
Il file di input contiene una sequenza di terne. Ogni terna è del tipo (a,b,c), dove
a,b e c sono degli interi di due cifre compresi tra 00 e 99.
La prima riga del file di input contiene il numero di terne presenti nel file.
Output
Il file di output contiene la sequenza riordinata delle terne presenti nel file di input.

Le interfacce:

Code:
public interface Node {
public Node getNext(); // ritorna il nodo successivo
public void setNext(); // setta il valore del next
public void setFirst(int i); // setta il primo val della terna
public void setSecond(int i); // setta il secondo val della terna
public void setThird(int i); // setta il terzo val della terna
public int getFirst(int i); // ritorna il primo val della terna
public int getSecond(int i); // rit. il secondo val della terna
public int getThird(int i); // ritorna il val della terna
}


public interface LinkedList {
// ritorna true se la lista è vuota
public boolean isEmpty();
// ritorna true se node è la testa della lista
public boolean isHead(Node node);
// ritorna true se node è la coda della lista
public boolean isTail(Node node);
// aggiunge un nuovo elemento alla lista
public void add(Node node);
// ritorna l'elemento più piccolo della lista
public void getMin();
// ritorna l'elemento più grande della lista
public void getMax();
// ritorna la testa della lista
public Node getHead();
// ritorna la coda della lista
public Node getTail();
// ritorna la dimensione della lista
public long getSize();
}

E le calssi che ho fatto io sono:

Code:
public class TripleNode implements Node
{
private int first,second,third;
private TripleNode next;

public TripleNode(int first,int second,int third)
{
this.first=first;
this.second=second;
this.third=third;
}

public TripleNode getNext(){ return next;}

public void setNext(Node n){next=(TripleNode)n;}

public void setFirst(int i){first=i;}

public void setSecond(int i){second=i;}

public void setThird(int i){third=i;}

public int getFirst(){return first;}

public int getSecond(){return second;}

public int getThird(){return third;}

public int compareTo(Node node){
if(this.getFirst() != node.getFirst()){
if(this.getFirst() < node.getFirst()){
return -1;
                        }
else {
                           return 1;
                    }
}

else if(this.getSecond() != node.getSecond()){
if(this.getSecond() <node.getSecond()){
    return -1;
                        }
else{
                          return 1;
                        }
}

else if(this.getThird() !=node.getThird()){
if(this.getThird() <node.getThird()){
               return -1;
                        }
else{
                              return 1;
                        }
}
return 0;
}


}


Code:
import java.io.*;
import java.util.*;

public class TripleList implements LinkedList
{
protected TripleNode head,tail;

private long size;

public TripleList()
{
head=null;
size=0L;
}


public boolean isEmpty(){ return(size==0);}

public boolean isHead(Node node){return (node==head);}

public boolean isTail(Node node){return (node==tail);}

public void add(Node node){

boolean added=false;
if(size==0){
head=(TripleNode)node;
return;
}
else{
Node prev=head; //conterrà il precedente

for(Node tmp=head; tmp!=null; tmp=tmp.getNext()){
if(node.compareTo(tmp)<1){

        node.setNext(tmp);
prev.setNext(node);
size++;
added=true;
return; //oppure break;
}
prev=tmp;

}
}

if(added==false)         //significa che non l'ho inserito e va messo alla fine
{
tail.setNext(node); 
node.setNext(null);
tail=(TripleNode)node;
size++;
}
}



public Node getMin()
{
Node tmp;
Node min=head;

for(tmp=head; tmp!=null; tmp=tmp.getNext())
{
if(min.compareTo(tmp)>1)
min=tmp;
}

return min;
}



public Node getMax()
{
Node tmp;
Node max=head;

for(tmp=head; tmp!=null; tmp=tmp.getNext())
{
if(max.compareTo(tmp)<1)
max=tmp;
}

return max;
}


public Node getHead(){ return head;}

public Node getTail(){return tail;}

public long getSize(){return size;}

public String toString()
{
Node n;
String s="";
String zero="0";

for(n=head; n.getNext()!=null; n=n.getNext())
{
if(n.getFirst()<10)
{
s+="("+zero+n.getFirst()+", ";
}

else s+="("+n.getFirst()+", ";

if(n.getSecond()<10)
{
s+=zero+n.getSecond()+", ";
}
else
s+=n.getSecond()+", ";

if(n.getThird()<10)
{
s+=zero+n.getThird()+")"+'\r'+'\n';
}

s+=n.getThird()+")"+'\r'+'\n';
}

return s;

}


public static void Ordina(String input,String output)
{
StringTokenizer s=null;
FileReader reader=null;
BufferedReader buff=null;
FileWriter out=null;


try
{
reader=new FileReader(input);
buff=new BufferedReader(reader);
out=new FileWriter(output);

int terne=(Integer.parseInt(buff.readLine()));
int primo,secondo,terzo;

TripleList lista=new TripleList();
TripleNode node;

while(buff.ready())
{
s=new StringTokenizer(buff.readLine(),"(,)");
primo=(Integer.parseInt(s.nextToken()));
secondo=(Integer.parseInt(s.nextToken()));
terzo=(Integer.parseInt(s.nextToken()));

node=new TripleNode(primo,secondo,terzo);
lista.add(node);
System.out.println(lista.toString());
System.out.println("fine");


}

out.write(lista.toString());

}


catch(FileNotFoundException e1)
{
System.out.println("ERROR...FILE NOT FOUND");
}

catch(IOException e2)
{
System.out.println("input/output error...");
}

finally
{
try
{
if(buff!=null) buff.close();
if(out!=null)out.close();
}

catch(IOException e3)
{
System.out.println("ERROR..IT IS NOT POSSIBLE TO CLOSE FILES");
}
}

}


public static void main(String [] args)
{
long start=System.currentTimeMillis();
Ordina("input.txt","output.txt");
long end=System.currentTimeMillis();
System.out.println("TEMPO TRASCORSO "+(end-start)+" NANOSECONDI.");
}
}
« Last Edit: 23-08-2010, 11:16:41 by Daréios » Logged

"Utilizzare sempre de l'Hôpital.....è come andare a caccia di farfalle con un bazooka".
Daréios89
Forumista Eroico
*****
Offline Offline

Gender: Male
Posts: 2.679


La musica è la forma d'arte suprema.


« Reply #3 on: 24-08-2010, 23:16:08 »

Nessuno mi saprebbe aiutare?
Il problema credo sia nell'inserimento ordinato...
Logged

"Utilizzare sempre de l'Hôpital.....è come andare a caccia di farfalle con un bazooka".
dani89
Apprendista Forumista
**
Offline Offline

Posts: 254



« Reply #4 on: 25-08-2010, 15:38:17 »

ho trovato in vecchi appunti questo:
Code:
public void insertOrd(int val)
{
         if(isEmpty())
                head=new Nodo(val);
         else if(head.getInfo()>val)
                head=new Nodo(val,head);
         else
         {
                 Nodo aux=head;
                 for(;aux.getNext()!=null && aux.getNext().getInfo()<val;aux=aux.getNext());
                 aux.setNext(new Nodo(val,aux.getNext()));
         }
}
ovviamente adattalo ai nomi delle variabili che hai usato tu.... ciao
Logged
Daréios89
Forumista Eroico
*****
Offline Offline

Gender: Male
Posts: 2.679


La musica è la forma d'arte suprema.


« Reply #5 on: 25-08-2010, 22:14:37 »

ho trovato in vecchi appunti questo:
Code:
public void insertOrd(int val)
{
         if(isEmpty())
                head=new Nodo(val);
         else if(head.getInfo()>val)
                head=new Nodo(val,head);
         else
         {
                 Nodo aux=head;
                 for(;aux.getNext()!=null && aux.getNext().getInfo()<val;aux=aux.getNext());
                 aux.setNext(new Nodo(val,aux.getNext()));
         }
}
ovviamente adattalo ai nomi delle variabili che hai usato tu.... ciao

Ho risolto in modo simile...grazie lo stesso

 
Logged

"Utilizzare sempre de l'Hôpital.....è come andare a caccia di farfalle con un bazooka".
Pages: [1]   Go Up
Print
Jump to: