Newsgroup: it.comp.lang.c++
Titolo: Ordinamento di una lista

Ho cercato di ordinare la lista a priori, cioč, durante l'inserimento degli 
elementi... ma c'č qualcosa che non va!!!
Se inserisco 1 2 3 4 5, la lista viene "ordinata" cosě: 1 3 4 5 2 (il 
secondo elemento viene portato in unltima posizion).
Mi dite cosa ho sbagliato?
void Lista::crea_lista(int val, elem*& lista)
 {
  //Ipotesi in cui la lista sia vuota
  if (lista == NULL)
   {
    lista = new elem (val, NULL);
    return;
   }
  //Ipotesi in cui ci sia un solo elemento > di val
  if (lista->val > val)
   {
    lista = new elem(val, lista);
    return;
   };
  //Ipotesi in cui ci sia un solo elemento < di val
  if (lista->next == NULL)
   {
    lista->next = new elem(val, NULL);
    return;
   }
  //Ipotesi in cui ci sia piů di un elemento
  elem* p = lista;
  elem* q = lista->next;
  while (q->next != NULL && q->val < val)
   {
    p = p->next;
    q = q->next;
   };
   //Inserisco val tra p e q
   p->next = new elem (val, q);
 };

 void Lista::crea_lista(int val, elem*& lista)
Questa sarebbe la funzione per aggiungere un elemento in una lista? Il nome
confonde....
Inoltre in C++ dovresti fare in modo che la classe lista nasconda di piu'
l'implementazione all'utente... non e' bello passare un "int" e un "elem*&
lista".
Nella mia implementazione tutto cio che devi passare e' un "int".
Inoltre stavi facendo un pochino troppi casi.
Prova di vedere se quello che segue ti puo' aiutare a capire. L'ho scritta
in due minuti, quindi spero funzioni correttamente (sembra), ed ho cercato
di copiare un pochino la tua logica ma di metterla in modo un pochino piu'
OO.
Ovviamente non ho fatto nessun metodo per togliere elementi dalla lista o
per farci altro... non era questa la domanda ;-)
<CODE>
#include<iostream>
using namespace std;
class Lista{
public:
     Lista():m_ptr_testa(0){
          // constructor
     }
     ~Lista(){
          // cancella la lista evitando memory leaks
          Elem *tmp = m_ptr_testa;
          Elem *prev = 0;
          while(tmp){
               prev = tmp;
               tmp = tmp->m_ptr_next;
               delete prev;
          }
     }
     void Add(int val){
          // aggiunge un elemento nella lista
          if(!m_ptr_testa){
               // lista vuota
               m_ptr_testa = new Elem;
               m_ptr_testa->m_val = val;
          }else if(m_ptr_testa->m_val>=val){
               // elemento va aggiunto in testa
               Elem *tmp = m_ptr_testa;
               m_ptr_testa = new Elem;
               m_ptr_testa->m_val = val;
               m_ptr_testa->m_ptr_next = tmp;
          }else{
               // elemento va aggiunto altrove
               Elem *scan = m_ptr_testa;
               while(scan->m_ptr_next){
                    if(scan->m_ptr_next->m_val >= val){
                         break;
                    }
                    scan = scan->m_ptr_next;
               }
               Elem *tmp = scan->m_ptr_next;
               scan->m_ptr_next = new Elem;
               scan->m_ptr_next->m_val = val;
               scan->m_ptr_next->m_ptr_next = tmp;
          }
     }
     void Print(){
          // stampa la lista
          Elem *tmp = m_ptr_testa;
          std::cout << std::endl;
          while(tmp){
               std::cout << tmp->m_val << " ";
               tmp = tmp->m_ptr_next;
          }
          std::cout << std::endl;
     }
private:
     struct Elem{
          Elem():m_ptr_next(0){}
          int m_val;
          Elem *m_ptr_next;
     }*m_ptr_testa;
};
int main()
{
     Lista l; // creiamo la lista
     int n;
     for(int i=0; i<20; ++i){
          cout << "Numero da aggiungere: " << endl;
          cin >> n;
          l.Add(n);  // aggiungiamo un elemento nella lista
          l.Print(); // stampiamola per verifica
     }
     return 0;
} // + o - qui viene distrutta la lista in automatico
</CODE>
HTH,
Tommy