Funzione sort per ordinare una lista di interi

di il
6 risposte

Funzione sort per ordinare una lista di interi

Salve ragazzi come già ho scritto in un altro post sto cercando di finire un esercizio che dice di implementare una funzione sort che ordini una lista di interi.
Io ho rifatto per l'ennesima volta il codice ma niente non mi funziona
ho usato il metodo bubblesort e per scambiare gli elementi di una lista ho usato i puntatori ai nodi.
ecco il codice

#include <iostream>

#include <cassert>

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)
{
    Node* i;
    bool swapped;
    Node* temp;
    do{
    swapped=false;
    for(i=first;i!=last;i=i->succ)
        if((i->data)>((i->succ)->data))
        {
            temp=i;
            i=i->succ;
            i->succ=temp;
            swapped=true;
        }
    }while(swapped);

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

int main()
{
    List L;

    L.push_back(10);
    L.push_back(3);
    L.push_back(5);
    L.push_back(67);
    L.push_back(89);
    L.push_back(1);
    L.push_back(100);
    L.push_back(34);
    L.push_back(3);
    L.push_back(6);
    L.push_back(21);

    L.sort(L);

return 0;
}

provate anche a compilarlo così vedrete se con qualche piccola modifica a voi funzioni o no

6 Risposte

  • Re: Funzione sort per ordinare una lista di interi

    Impara ad usare il debug.
    
        #include <iostream>
    
        #include <cassert>
    
        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)
        {
            Node* i;
            bool swapped;
    		int temp;
            do{
            swapped=false;
            for(i=first;i!=last;i=i->succ)
                if((i->data)>((i->succ)->data))
                {
                    temp=i->data;
    				i->data=i->succ->data;
    				i->succ->data=temp;
                    swapped=true;
                }
            }while(swapped);
    
        Iterator p;
        for(p=l.begin();!p.is_null();p=p.next())
            cout<<p.get()<<"   ";
        }
    
        int main()
        {
            List L;
    
            L.push_back(10);
            L.push_back(3);
            L.push_back(5);
            L.push_back(67);
            L.push_back(89);
            L.push_back(1);
            L.push_back(100);
            L.push_back(34);
            L.push_back(3);
            L.push_back(6);
            L.push_back(21);
    
            L.sort(L);
    
        return 0;
        }
    
    
  • Re: Funzione sort per ordinare una lista di interi

    Scusa ma non ce l'hanno spiegato al compito
    e poi il programma non dà errori di sintassi
    il problema è che è sbagliato qualcosa concettualmente
  • Re: Funzione sort per ordinare una lista di interi

    Hai provato ad eseguire la mia modifica?
  • Re: Funzione sort per ordinare una lista di interi

    Allora si ho capito e ti ringrazio
    avrei bisogno di due chiarimenti
    uno è riguardo al debug
    come si fa ad eseguire il debug?
    e poi quando vai a effettuare lo scambio si può scrivere tra parentesi
    
                temp=i->data;
                i->data=(i->succ)->data;
               (i->succ)->data=temp;
    
    per i puntatori le dereferenziazioni vengono eseguite linearmente cioè in maniera consecutiva, in ordine di come sono scritte?
  • Re: Funzione sort per ordinare una lista di interi

    Leggi le istruzioni del tuo compilatore.Visual Studio ha proprio il menu debug. Altri non so ma ci sarà senza'altro un menu. Un IDE senza debug è da buttare quindi al 100% il tuo compilatore (qualunque esso sia) ha un menu debug e i vari pulsanti di step-in, step-out, step-into ecc.
    Il dereferenze viene eseguito da sx a dx.

    Un esempio ---> Code::Blocks

    http://wiki.codeblocks.org/index.php?title=Debugging_with_Code::Blocks
  • Re: Funzione sort per ordinare una lista di interi

    Grazie io infatti uso codeblocks
Devi accedere o registrarti per scrivere nel forum
6 risposte