Ordinamento lista

di Anonimizzato8504 il
15 risposte
/
Anonimizzato8504
Utente anonimizzato
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

  • /
    Anonimizzato7532
    Utente anonimizzato
    La std::list ha già la funzione sort, che stai cercando di fare?
  • /
    Anonimizzato8504
    Utente anonimizzato
    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
  • /
    Anonimizzato7532
    Utente anonimizzato
    Che cosa sono sti Iterator? e is_null(). Sono tuoi?
  • /
    Anonimizzato8504
    Utente anonimizzato
    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;
}
  • /
    Anonimizzato7532
    Utente anonimizzato
    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.
  • /
    Anonimizzato8504
    Utente anonimizzato
    Potresti farmi vedere come si fa la funzione set che non capisco bene
    grazie
  • /
    Anonimizzato7532
    Utente anonimizzato
    Iterator::set(const std::string & str)
{
   assert(position != NULL);
   position->data = str;
}
  • /
    Anonimizzato8504
    Utente anonimizzato
    Ok grazie
    ci ragiono sopra e se ho qualche problema te lo faccio sapere
  • /
    Anonimizzato8504
    Utente anonimizzato
    Come lo inserisco nel codice il set
    puoi farmi vedere la modifica, che non ci riesco a fare lo scambio
  • /
    Anonimizzato7532
    Utente anonimizzato
    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.
  • /
    Anonimizzato8504
    Utente anonimizzato
    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
  • /
    Anonimizzato8504
    Utente anonimizzato
    Ma quindi devo anche modificare 
    
int get() const
    con 
    
int& get()const
    fammi sapere
  • /
    Anonimizzato8504
    Utente anonimizzato
    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()?
  • /
    Anonimizzato8504
    Utente anonimizzato
    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