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.
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()<<" ";
}
Risposte
Mi sembra un po' incasinata come soluzione (e non credo funzionerà). Che algoritmo di ordinamento avevi in mente?
Più che il codice dell'ordinamento, è il codice dove vengono implementati gli iteratori ad essere importante per comprendere il tuo errore. Con ogni probabilità get() restituisce una copia del valore o un riferimento/puntatore costante e non è possibile scambiarne i valori usando swap (anche fosse possibile richiamare il metodo diversamente dal tuo caso). Non conoscendo l'API implementata dai tuoi iteratori, non abbiamo però alcuna possibilità di prevedere come dovrà apparire la tua funzione. Quello che posso però dirti è che la tua funzione non appare neanche lontanamente simile ad un ordinamento corretto. Mi sembra tu stia semplicemente scorrendo la lista e scambiando due valori consecutivi nel caso non fossero nel corretto ordine. Ma questo algoritmo non funziona. Prova ad ordinare la lista \( 5, 4, 3, 2, 1\) utilizzando il tuo algoritmo. Il risultato dovrebbe essere, se ho capito le tue intenzioni \( 4, 3, 2, 1, 5 \). La funzione potrebbe inoltre potenzialmente andare in crash nel caso in cui la lista sia vuota.
questa è la classe LISTA che sto utilizzando, è con le stringhe ma ho cambiato string in int per utilizzarla giusto per farvi capire di che si tratta
// 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;
}
vorrei capire come si effettuano scambi in una lista senza però utilizzare funzioni già implementate e contenute nella libreria
Probabilmente modificando la definizione del tuo iteratore in modo che permetta la modifica del nodo a cui "punta". Se no credo proprio che tu sia costretto a evitare l'uso degli iteratori.
l'ho rifatto perchè non mi funziona ancora?
#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;
}
Ma perché, invece di ostinarti a cercare di far scambiare due valori che giustamente non dovrebbe essere possibile scambiare, non aggiungi una funzione che permette di settare il valore del nodo a cui punta un iteratore oppure non lavori direttamente con i nodi?
potresti farmi vedere il codice
perchè se non lo vedo funzionare proprio non riesco a convincermi
ho provato in molti modi ma nessuno mi funziona correttamente
perchè se non lo vedo funzionare proprio non riesco a convincermi
ho provato in molti modi ma nessuno mi funziona correttamente
Accedi a tutti gli appunti
Tutor AI: studia meglio e in meno tempo