ORDINAMENTO LISTA

[nepero87]

Salve...

Ho un bel problemuccio con una lista di interi...

In un esercizio mi si chiede di ordinare questa in senso crescente, e fino a qua non dovrebbero esserci problemi, lo saprei fare a occhi chiusi... Il fatto è che la lista deve essere ordinata NON scambiando la parte numerica dei nodi, ma modificando i collegamenti fra gli elementi...

Io quindi ho pensato di spostare in testa l'elemento che a ogni iterazione trovo maggiore, ma come posso fare per rendere la soluzione generalizzabile?

[lorven]

Utilizzando una lista bidirezionale, credo sia sufficiente scambiare i 2 puntatori, al predecessore e al successore, quando, nei vari confronti presenti nel solito algoritmo di sort, si incontrano due nodi con la parte informativa che non rispetta l'ordinamento.

[nepero87]

Però nel testo dell'esercizio c'è scritto di modificare una lista FIFO lineare e monodirezionale... Un modo lo conosco, ma non è generalizzabile... Quindi non va bene...

[lorven]

Anche con una lista linkata semplice, le cose non andrebbero molto diversamente ... sarebbe sufficiente conservare, ad ogni avanzamento nella lista, in una variabile d'appoggio, il link del nodo dal quale si proviene.

[gigilatrottola2]

prova a guardare questo se puo essert iutile
http://www.fuoridalbranco.com/unife.it/ ... (algoritmo)%20mergesort%20di%20linked%20list.c

spero il collegamento vada.
E' un mergesort di una linked list unidirezionale, ordinata in base ad un valore intero. Ovviamente viene ordinata muovendo i puntatori.

[lorven]

Il Link indicato da gigilatrottola mi da "accesso negato!" (non ho sbirciato...)
Dopo aver litigato un po' coi puntatori C++ (non li usavo da un pezzo), posto un abbozzo di soluzione, pare funzionante, senz'altro migliorabile.
Il sort utilizzato è un banale sort per selezione.

#include <iostream.h>
#include <stdlib.h>
#include <time.h>
#define tappo -1
using namespace std;

// La lista semplice è composta da alcuni nodi linkati
// tra loro; ogni nodo è definito con una struttura
// che contiene un numero intero >0 e un puntatore al successivo.

struct Nodo
{
  int Info;        // per memorizzare un numero intero
  Nodo* Next;      // puntatore al nodo successivo
};

Nodo* Succ;        // puntatore al nodo successivo
Nodo* First;       // puntatore al primo elemento
Nodo* Prec;        // puntatore al nodo precedente dell'ultimo inserito

/******************************************************************************/
void scambia()     // scambia il contenuto informativo di 2 nodi
{
int x;
x = Prec -> Info;
Prec -> Info = Succ -> Info;
Succ -> Info = x;
}
/******************************************************************************/
void ordina()        // ordina la lista in base al campo Info in senso crescente
{
cout << "ordinamento ...";
Prec = First;

while (Prec -> Next -> Next != 0)
{
   Succ = Prec -> Next;
   while (Succ -> Next -> Next != 0)
      {
      if (Prec -> Info > Succ -> Info)
         scambia();
      Succ = Succ -> Next;
      }
   Prec = Prec -> Next;
}

}
/******************************************************************************/
void stampa()
{
cout << endl;
cout << "lista ordinata:" << endl;
Succ = First;

while (Succ -> Next != 0) // stampa il contenuto della lista
{
   if (Succ -> Info != tappo)
       cout << Succ -> Info << " ";
   Succ = Succ -> Next;
}
cout << endl;
}
/******************************************************************************/
void leggi()               // chiede i numeri e li pone nella lista
{
int num;
Succ = First;

do
{
   cout << "Immetti un numero: " ;
   cin >> num;
   Succ -> Info = num;    // memorizza il numero nel campo Info del nodo
   Prec = Succ;           // conserva il nodo precedente
   Succ = new Nodo;       // crea un nuovo nodo
   Succ -> Next = 0   ;   // il nuovo nodo è posto in coda alla lista
   Prec -> Next = Succ;   // il nuovo nodo è agganciato dal precedente
}
while (num != tappo);
}
/****************************** M A I N ***************************************/
void main()
{
First = new Nodo;  // crea il primo nodo
leggi();
ordina();
stampa();

system ("pause");
return 0;
}

Si può usare questo programmino come base di una gestione di lista linkata più efficiente.   

[gigilatrottola2]

Da accesso negato perke va copiato tutto...
Nel mio esempio invece de lselection si usa il mergesort

[nepero87]

"lorven":Il Link indicato da gigilatrottola mi da "accesso negato!" (non ho sbirciato...)
Dopo aver litigato un po' coi puntatori C++ (non li usavo da un pezzo), posto un abbozzo di soluzione, pare funzionante, senz'altro migliorabile.

Grazie... Ho cercato di interpretare il tuo algoritmo, pare che possa funzionare... Comunque l'esame l'ho già dato, ieri sera, parlava di stringhe e codifica di particolari parole composte da numeri e lettere.. Dovrei averlo fatto bene, stasera ho gli orali...

Speriamo bene!

[nepero87]

Fatto!! Un bel 30... Che bella la programmazione!!

[lorven]

[size=150]30![/size]