Funzione per ordinare una lista

di il
7 risposte

Funzione per ordinare una lista

Avrei bisogno di un aiuto per risolvere questo piccolo problema
come si può ordinare una lista di interi
ecco qui il mio codice, non dà errori nella compilazione ma li dà nell'esecuzione
la funzione sort che ho implementato in pratica è il bubblesort applicato alle liste

#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;
}

7 Risposte

  • Re: Funzione per ordinare una lista

    I.next()).get() va in crash se vai oltre la fine della lista.
  • Re: Funzione per ordinare una lista

    Ho provato a inserire nell'if la condizione
    
    if(i.get()>=(i.next()).get() && !(i.next()).is_null())
    
    ma niente mi dà ancora errore

    come si può fare
    e soprattutto non ci sarebbe un metodo più semplice per implementare una funzione che ordini gli elementi interi di una lista
  • Re: Funzione per ordinare una lista

    Scambia l'ordine
  • Re: Funzione per ordinare una lista

    Cioè?
    
    if((i.next()).get()<=i.get() && !(i.next()).is_null())
    
    così dicevi?
    perchè anche così non funziona lo stesso
    l'errore che dà all'esecuzione riguarda questo pezzo di codice
    
    int& Iterator::get() const
      {
    assert(position != NULL);
       return position->data;
      }
    
    infatti dice Assertion failed position!=NULL e si blocca
  • Re: Funzione per ordinare una lista

    if(!(i.next()).is_null() && (i.get()<=i.next()).get()) )
  • Re: Funzione per ordinare una lista

    Così non dà alcun errore ma la schermata rimane nera
    non stampa niente
    dove sta l'errore secondo te
    hai letto il messagio di prima
    ho scritto quello che mi riportava all'esecuzione
  • Re: Funzione per ordinare una lista

    Qualche altro aiuto? potresti provare a compilarlo?
Devi accedere o registrarti per scrivere nel forum
7 risposte