Ordinamento lista

di
masaniello
il
15 risposte
M
masaniello
Utente Attivo
Iscritto da
mar, 2011
Messaggi:
189

Ordinamento lista

Salve a tutti ho un problema con un esercizio che dice: Scrivere una funzione sort che ordina gli elementi di una lista collegata(senza copiarli in un vettore)
vi posto il codice della mia funzione ma l'errore che mi dà il compilatore è quando effettuo lo scambio di elementi, mi dice che non supporta lo swap tra due iterator, pur avendo restituito il valore dell'iteratore. 

void List::sort(List l)
{
    Iterator i=l.begin();
    Iterator j=i.next();
    while(!j.is_null())
    {
        if(i.get()>=j.get())
        swap(i.get(),j.get());
    i=i.next();
    j=j.next();
    }
Iterator a;
for(a=l.begin();!a.is_null();a=a.next())
    cout<<a.get()<<"   ";
}

15 Risposte

  • skynet
    skynet
    Utente Famoso
    Iscritto da
    lug, 2010
    Messaggi:
    3060

    Re: Ordinamento lista

    La std::list ha già la funzione sort, che stai cercando di fare?
  • M
    masaniello
    Utente Attivo
    Iscritto da
    mar, 2011
    Messaggi:
    189

    Re: Ordinamento lista

    Ah scusami non l'ho scritto nel messaggio prima
    ma la funzione la devo implementare io
    mi puoi dire come devo trattare lo swap?
    perchè è l'unico errore che mi da il compilatore
  • skynet
    skynet
    Utente Famoso
    Iscritto da
    lug, 2010
    Messaggi:
    3060

    Re: Ordinamento lista

    Che cosa sono sti Iterator? e is_null(). Sono tuoi?
  • M
    masaniello
    Utente Attivo
    Iscritto da
    mar, 2011
    Messaggi:
    189

    Re: Ordinamento lista

    Ti posto la class List
    è per le stringhe ma per gli interi basta modificare string in int , è solo per farti vedere le funzioni che uso così gli dai un'occhiata e capisci dove sta il problema 
    
// include la definizione delle funzioni next() e previous()
// come funzioni di tipo Iterator

#include <string>
#include <cassert>

using namespace std;

class Node;
class List;

class Iterator
 {public:
   Iterator();
   string get() const;
   Iterator next()const;
   Iterator previous()const;
   bool equals(Iterator b) const;
   bool is_null() const;
  private:
   Node* position;
  friend class List;
 };

class List
{public:
   List();
   void push_back(string s);
   void insert(Iterator p, string s);
   void erase(Iterator p);
   bool empty() const;
   Iterator begin();
   Iterator end();
 private:
   Node* first;
   Node* last;
};

class Node
 {public:
   Node(string s);
  private:
   string data;
   Node* prec;
   Node* succ;
  friend class List;
  friend class Iterator;
 };

Node::Node(string s)
  {data = s;
   prec = NULL;
   succ = NULL;
  }

Iterator::Iterator()
  {position = NULL;
  }

string Iterator::get() const
  {
assert(position != NULL);
   return position->data;
  }

bool Iterator::equals(Iterator b) const
  {
   return position == b.position;
  }


Iterator Iterator::next() const

{
assert(position != NULL);
  
 Iterator t;
   
 t.position = position->succ;
   
 return t;

}




Iterator Iterator::previous() const

{
  assert(position != NULL);
    
    Iterator t;
   
    t.position = position->prec;
    
    return t;

}


bool Iterator::is_null() const
  {return position==NULL;
  }

List::List()
  {first = NULL;
   last = NULL;
  }

bool List::empty() const
  { return first==NULL; }

Iterator List::begin()
  {Iterator i;
   i.position = first;
   return i;
  }

Iterator List::end()
  {Iterator i;
   i.position = last;
   return i;
  }

void List::push_back(string s)
{Node* n = new Node(s);
   if (last == NULL)
  {first = n;
   last = n;
  }
else  {n->prec = last;
        last->succ = n;
       last= n;
      }
}

void List::insert(Iterator p, string s)
{if (empty())
    push_back(s);
 else {Node* n = new Node(s);
       Node* dopo = p.position;
       Node* prima = dopo->prec;
       n->prec = prima;
       n->succ = dopo;
       dopo->prec = n;
       if (prima==NULL)
          first = n;
       else prima->succ = n;
      }
}

void List::erase(Iterator p)
{assert (p.position != NULL);
 Node* rimuovi = p.position;
 Node* dopo = rimuovi->succ;
 Node* prima = rimuovi->prec;
 if (prima==NULL)
    first = dopo;
 else prima->succ = dopo;
 if (rimuovi==last)
  last = prima;
 else dopo->prec = prima;
 delete rimuovi;
}
  • skynet
    skynet
    Utente Famoso
    Iscritto da
    lug, 2010
    Messaggi:
    3060

    Re: Ordinamento lista

    Crea la funzione set per l'iterator oppure il copy-costructor. lo swap non funziona perche get() ritorna delle stringhe const da cui non scambiabili. Le stringhe tra altro vengono restituite per valore quindi anche se fai lo scambio non ottieni nulla perche stai scambiando delle copie.
  • M
    masaniello
    Utente Attivo
    Iscritto da
    mar, 2011
    Messaggi:
    189

    Re: Ordinamento lista

    Potresti farmi vedere come si fa la funzione set che non capisco bene
    grazie
  • skynet
    skynet
    Utente Famoso
    Iscritto da
    lug, 2010
    Messaggi:
    3060

    Re: Ordinamento lista

    Iterator::set(const std::string & str)
{
   assert(position != NULL);
   position->data = str;
}
  • M
    masaniello
    Utente Attivo
    Iscritto da
    mar, 2011
    Messaggi:
    189

    Re: Ordinamento lista

    Ok grazie
    ci ragiono sopra e se ho qualche problema te lo faccio sapere
  • M
    masaniello
    Utente Attivo
    Iscritto da
    mar, 2011
    Messaggi:
    189

    Re: Ordinamento lista

    Come lo inserisco nel codice il set
    puoi farmi vedere la modifica, che non ci riesco a fare lo scambio
  • skynet
    skynet
    Utente Famoso
    Iscritto da
    lug, 2010
    Messaggi:
    3060

    Re: Ordinamento lista

    Allora si capisce che il codice non l'hai scritto tu. una volta modificato che fai, lo presenti come tuo e alla prima domanda che ti fano chiedi aiuto al forum? Ti ho detto che lo swap lo si fa se passi le stringhe per riferimento nel get() e non per valore.
  • M
    masaniello
    Utente Attivo
    Iscritto da
    mar, 2011
    Messaggi:
    189

    Re: Ordinamento lista

    Il codice sort l'ho fatto io ma ho quel problema
    comunque la classe list che ti ho messo è per le stringhe ma io devo andare a scambiare due elementi di una lista che sono interi non stringhe
    nella classe lista basta che cambio string con int ed ecco la classe list per gli interi
    io te l'ho messa solo per farti capire quali erano le funzioni che usavo

    Comunque il problema è che non riesco a scrivere questa parte di codice
  • M
    masaniello
    Utente Attivo
    Iscritto da
    mar, 2011
    Messaggi:
    189

    Re: Ordinamento lista

    Ma quindi devo anche modificare 
    
int get() const
    con 
    
int& get()const
    fammi sapere
  • M
    masaniello
    Utente Attivo
    Iscritto da
    mar, 2011
    Messaggi:
    189

    Re: Ordinamento lista

    Facendo tale sostituzione il programma mi effettua lo scambio tra elementi in una lista tramite swap
    ma non c'è un altro modo senza che modifichi la funzione get()?
  • M
    masaniello
    Utente Attivo
    Iscritto da
    mar, 2011
    Messaggi:
    189

    Re: Ordinamento lista

    Però non mi funziona la funzione sort 
    
#include <string>
#include <cassert>
#include<iostream>

using namespace std;

class Node;
class List;

class Iterator
 {public:
   Iterator();
   int& get() const;
   Iterator next()const;
   Iterator previous()const;
   bool equals(Iterator b) const;
   bool is_null() const;
  private:
   Node* position;
  friend class List;
 };

class List
{public:
   List();
   void push_back(int s);
   void insert(Iterator p, int s);
   void erase(Iterator p);
   bool empty() const;
   Iterator begin();
   Iterator end();
   void sort(List l);

 private:
   Node* first;
   Node* last;
};

class Node
 {public:
   Node(int s);
  private:
   int data;
   Node* prec;
   Node* succ;
  friend class List;
  friend class Iterator;
 };

Node::Node(int s)
  {data = s;
   prec = NULL;
   succ = NULL;
  }

Iterator::Iterator()
  {position = NULL;
  }

int& Iterator::get() const
  {
assert(position != NULL);
   return position->data;
  }

bool Iterator::equals(Iterator b) const
  {
   return position == b.position;
  }


Iterator Iterator::next() const

{
assert(position != NULL);
  
 Iterator t;
   
 t.position = position->succ;
   
 return t;

}




Iterator Iterator::previous() const

{
  assert(position != NULL);
    
    Iterator t;
   
    t.position = position->prec;
    
    return t;

}


bool Iterator::is_null() const
  {return position==NULL;
  }

List::List()
  {first = NULL;
   last = NULL;
  }

bool List::empty() const
  { return first==NULL; }

Iterator List::begin()
  {Iterator i;
   i.position = first;
   return i;
  }

Iterator List::end()
  {Iterator i;
   i.position = last;
   return i;
  }

void List::push_back(int s)
{Node* n = new Node(s);
   if (last == NULL)
  {first = n;
   last = n;
  }
else  {n->prec = last;
        last->succ = n;
       last= n;
      }
}

void List::insert(Iterator p, int s)
{if (empty())
    push_back(s);
 else {Node* n = new Node(s);
       Node* dopo = p.position;
       Node* prima = dopo->prec;
       n->prec = prima;
       n->succ = dopo;
       dopo->prec = n;
       if (prima==NULL)
          first = n;
       else prima->succ = n;
      }
}

void List::erase(Iterator p)
{assert (p.position != NULL);
 Node* rimuovi = p.position;
 Node* dopo = rimuovi->succ;
 Node* prima = rimuovi->prec;
 if (prima==NULL)
    first = dopo;
 else prima->succ = dopo;
 if (rimuovi==last)
  last = prima;
 else dopo->prec = prima;
 delete rimuovi;
}

void List::sort(List l)
{
    Iterator i;
    bool swapped;
    do{
    swapped=false;
    for(i=l.begin();!i.is_null();i=i.next())
    {
        if(i.get()>=(i.next()).get())
        swap(i.get(),(i.next()).get());
        swapped=true;
    }
    }while(swapped);

Iterator a;
for(a=l.begin();!a.is_null();a=a.next())
    cout<<a.get()<<"   ";
}


int main()
{
    List L;
    L.push_back(15);
    L.push_back(2);
    L.push_back(5);
    L.push_back(18);
    L.push_back(2);
    L.push_back(3);
    L.push_back(15);

    L.sort(L);

    return 0;
}
Devi accedere o registrarti per scrivere nel forum
15 risposte