[C] ordinare una lista

[VendeR]

ciao a tutti!!! come da topic ho un problema a ordinare una lista (sono 2 ore che ci provo ma niente non riesco a farlo, , una volta il dev mi stampa gli elementi alla cavolo e un'altra si pianta).. quindi ho pensato di chiedere a voi (siete la mia ultima spiaggia!).
cerco di esporvi tutto in modo chiaro: il mio programma utilizza una lista (le ho appena studiate) abbastanza spartana, io possiedo il puntatore (P_list) alla testa della lista il quale a sua volta contiene il puntatore all'elemento successivo ecc.. (all'interno di P_list non è salvata nessuna informazione, quindi quando ordino la lista lui deve restare identico). ogni elemento punta al successivo e l'ultimo elemento è NULL, quindi per cercare un elemento nella lista devo sempre partire dalla testa e scorrerla tutta..
nel programma che ho fatto cerco elementi nella lista, ne inserisco e ne cancello, e tutto funiziona perfettamente, solo che non riesco ad ordinarla ecco il codice che ho scritto:

void sort (elem* P_list, int tipo){
      
      elem *o, *p, *q; /*servono scorrere tutto gli elementi della lista da ordinare*/
      elem *r,*s; /*servono per trovare il punto in cui inserire l'elemento staccato*/
      int conf;
      
      for (o = P_list, p = o->next, q = p->next; q != NULL; o = p, p = q, q = q->next){
                                                     
          if( BASE_cmp(p->val, q->val,tipo) > 0 ){ /*se il precedente è > del successivo*/
              
              /*stacco p dalla lista blocco*/
              o->next = q;
              
              /*cerco dove inserirlo*/
              for ( r = P_list, s = r->next; s!= NULL && (BASE_cmp(s->val,p->val,tipo)) < 0; r = s, s = s->next );
                      p->next = s;
                      r->next = p;
          }
      }
      
    
return;
}

piccola spiegazione: BASE_cmp è una funzione che ho scritto io che funziona come la strcmp e la uso per confrontare gli elementi della lista (questa funzione funziona ne sono sicuro la uso già altre volte nel programma senza nessun problema). in pratica io pensavo di prendere ogni valore della lista, se è più grande del successivo lo stacco, poi con un altro ciclo cerco dove reinserirlo all'interno della lista (tutto questo viene ripetuto per ogni elemento)..
la logica dell'ordinamento è giusta?? sicuramente ci sarà qualche altro metodo più efficiente, ma a me è venuto in mente solo questo..
vi prego datemi una mano non so proprio che cos'ha di sbagliato il mio codice a me pare giusto.. sia sintatticamente che a logica.. bho...
grazie 1000 in anticipo!!

[k0nt3]

un piccolo consiglio... crea una funzione che scambia un elemento della lista con il successivo e poi li ordini con bubblesort (che è un algoritmo semplicissimo e un pò stupido ma che funziona e di cui trovi anche l'implementazione qui http://it.wikipedia.org/wiki/Bubble_sort)

[VendeR]

ok ci provo.. però secondo te nel mio codice dove sta il problema??
mi sa che ad implemetare il bubble sort se non avrò più problemi di menò sicuro non saranno..

[k0nt3]

Originariamente inviato da VendeR

ok ci provo.. però secondo te nel mio codice dove sta il problema??
mi sa che ad implemetare il bubble sort se non avrò più problemi di menò sicuro non saranno..

ci possono essere elementi uguali nella lista?

[VendeR]

completamente uguali no (ogni elemento della lista è una struttura contenente al suo interno nome, cognome, matricola e media di un ipotetico studente, e se due persone hanno lo stesso cognome ma nome diverso, BASE_cmp ne tiene conto, però in generale no, non possono esserci due elementi "completamente" uguali..

[k0nt3]

scusa ma non ho molto tempo.. e ti devo lasciare :F magari domani torno!

[VendeR]

Originariamente inviato da k0nt3

scusa ma non ho molto tempo.. e ti devo lasciare :F magari domani torno!

ok non ti preoccupare
magari qualcun'altro ha voglia di rispondere alla mia domanda

[k0nt3]

volevo capire il tuo codice ma non ne ho avuto più voglia quando si scrive in C il codice è molto personale.. quindi ti dico come avrei fatto io:

void sort (elem* P_list, int tipo){
  boolean done;
  elem *p_prec, *p, *p_succ;

  flag = 0;            // vale 1 se ci sono stati degli scambi in una passata della lista

  while(!flag)
  { // inizia un passata di tutta la lista
    p_prec = P_list;     // p_prec serve perchè quando si scambia p con p_succ.. p_prec deve puntare a p_succ e non più a p (spero che si capisce)
    p = P_list->next;    // p è il puntatore corrente che stiamo considerando
    p_succ = p1->next;   // p_succ è il suo successivo

    while(p_succ != NULL) // finchè non siamo alla fine della lista
    {
      flag = 1; // metto flag a 1 all'inizio così se non entra mai nell'if rimane a 1 e poi esce dal while esterno perchè non ci sono stati scambi e quindi la lista è ordinata
      if(BASE_cmp(p->val, p_succ->val,tipo) > 0) // se p > p_succ
      {
        // scambio p con p_succ (nb. il codice potrebbe contenere errori ;) )
        p_prec->next = p_succ;
        p->next = p_succ->next;
        p_succ->next = p;

        flag = 0; // c'è stato uno scambio -> flag = 0
      }
      
      // avanzo di una posizione nella lista
      p_prec = p_prec-next;
      p = p->next;
      p_succ = p_succ->next;
    }
  }
}

quasi sicuramente sarà sbagliato, ma intanto è una bozza di soluzione.. in sostanza scorre la lista e scambia due elementi se uno è maggiore del successivo. quando fa tutta una passata senza scambiare niente vuol dire che la lista è ordinata

[VendeR]

ok grazie mille per il codice!! a occhio è simile come logica al mio... dopo lo provo!
cmq ieri ho provato ad implementare il bubble sort e con qualche modifica sono riuscito a farlo funzionare..
solo una cosa: io come compilatore uso il dev c++, ma non so come mai con lo stesso identico codice, a volte il programma funziona, poi se riavvio il pc e ricompilo lo stesso identico codice, non fa quello che dovrebbe.. (questo mi è capitato proprio con questo programma sulle liste).. a te sono mai capitate cose del genere?? mi sapresti consigliare qualche altro compilatore un pò più affidabile?? thx

[k0nt3]

quando lavori con tanti puntatori è possibile che ti sfugge un piccolo errore, e in quei casi il comportamente non è ben determinato (a volte funge e altre no). la cosa migliore sarebbe fare il debug e vedere cosa e dove c'è qualcosa che non và. se non sai fare il debug riempi di printf il codice in modo da stampare tutte le volte che fai qualcosa lo stato del programma. devc++ l'ho usato poco ma credo che sia sufficientemente affidabile.. usa minigw come compilatore vero? è un port di gcc per windows, e con gcc (su linux) non ho mai avuto problemi. le uniche alternativa sono visual c++ di MS (compila anche il C se non erro e potrebbe esistere una versione gratuita anche se a volte ha comportamenti poco standard di default) o borland c++ builder (la versione personal è gratuita).. non ricordo altri compilatori (se non il mitico borland c compiler da usare su dos )

[VendeR]

eh allora mi sa che dovrò fare un bel debug del programma (so come farlo )... mi informo un pò per le versioni gratuite di visual studio e c compiler.. thx per l'aiuto!

[sottovento]

Ciao,
volevo darti anch'io un suggerimento. Secondo me la cosa migliore e' scandire la lista di partenza una sola volta, creando in successione una seconda lista, ordinata, in uscita.
Ho scritto (e provato, usando visual studio) il seguente codice. Chiedo scusa per la fretta, ma qui e' tardissimo e lavoro 7 giorni su 7:

// sort.cpp : Application for testing a sort of simple linked list
//
// Author: sottovento
//

#include "stdafx.h"

// This is my list
struct List
{
	int value;
	struct List *next;
};

// Function prototypes
struct List *buildList ();
struct List *copyNode (struct List *node);
struct List *sort (struct List *unsorted);
void printList (struct List *head);

// This is some data for filling the list
#define NUM_DATA	10
int vectData[NUM_DATA] =
{
	5, 34, 7, 2, 64, 243, 7, 87, 12, 432
};

// Build up a test list
struct List *buildList ()
{
	struct List *head = NULL;
	struct List *p  = NULL;
	struct List *pCurrent = NULL;

	for (int i = 0; i < NUM_DATA; i++)
	{
		p = (struct List *)malloc (sizeof (struct List));
		if (!p)
		{
			printf ("FATAL - allocation error in buildList ()!!!\n");
			exit (0);
		}
		// Give value to this node
		p->value = vectData[i];
		p->next = NULL;
		
		if (!pCurrent)
			head = pCurrent = p;
		else
		{
			pCurrent->next = p;
			pCurrent = pCurrent->next;
		}
	}
	return head;
}

struct List *copyNode (struct List *node)
{
	struct List *p;

	p = (struct List *)malloc (sizeof (struct List));
	if (!p)
	{
		printf ("FATAL - allocation error in copyNode()!!!\n");
		exit (0);
	}
	p->value = node->value;
	p->next = NULL;
	return p;
}

// Sort the list
// INPUT: unsorted list
// OUTPUT: sorted list
struct List *sort (struct List *unsorted)
{
	struct List *p = NULL, *q = NULL, *prev = NULL;
	struct List *sorted = NULL;
	int inserted = 0;

	// scan all nodes in unsorted
	for (p = unsorted; p; p = p->next)
	{
		// I have to insert this value in the right position 
		if (!sorted)
			sorted = copyNode (p);
		else
		{
			inserted = 0;
			for (q = sorted, prev = NULL; q; prev = q, q = q->next)
			{
				if (p->value < q->value)
				{
					// OK, I have to insert here
					if (!prev)
					{
						sorted = copyNode (p);
						sorted->next = q;
					}
					else
					{
						prev->next = copyNode (p);
						prev->next->next = q;
					}
					inserted = 1;
					break;
				}
			}
			if (!inserted)
				prev->next = copyNode (p); // Insert at the end
		}
	}
	return sorted;
}

// Print a list
void printList (struct List *head)
{
	for (struct List *p = head; p; p = p->next)
		printf ("%d ", p->value);
	printf ("\n");
}

int _tmain(int argc, _TCHAR* argv[])
{
	struct List *head = buildList ();
	struct List *sorted = sort (head);

	printf ("UNSORTED:\n");
	printList (head);

	printf ("SORTED:\n");
	printList (sorted);

	// NOTICE - here you MUST free the list memory!
	return 0;
}

Naturalmente devi poi deallocare le liste, operazione da me non fatta (errore gravissimo).

Ti ricordo, come sempre, di controllare l'esito della malloc(). Purtroppo restero' inascoltato anche stavolta.

High Flying
Sottovento

[VendeR]

guarda io ero riuscito a fare una cosa simile alla tua, cioè avevo fatto una funzione che "smontava" tutta la mia lista di partenza (e la liberava) e ne ricreava una nuova, andando ad inserire ogni blocco nel punto giusto.. solo che poi volevo trovare un altro modo per fare la stessa cosa, perchè mi pareva molto "pesante" ricreare una nuova lista (se ho 1000 elementi, sono 2000malloc ecc..) però forse in effetti rispetto al bubble sort sarebbe meno pesante (e soprattutto per me più semplice da implementare!)..
secondo voi qual'è la soluzione più leggera ed elegante??

[k0nt3]

intanto ho corretto un pò di errori nel codice che ho postato prima e l'ho provato a compilare (con gcc ovviamente):
CHANGELOG: 14/05/06 21:50 - ora funziona -

void sort(elem* P_list, int tipo)
{
  int flag;
  elem *p_prec, *p, *p_succ;

  flag = 0;
  while(flag==0)
  { 
    p_prec = P_list;
    p = P_list->next;
    p_succ = p->next;

    flag = 1;
    while(p_succ != NULL)
    {
      
      if(BASE_cmp(p->val, p_succ->val,tipo) > 0)
      {
        p_prec->next = p_succ;
        p->next = p_succ->next;
        p_succ->next = p;
        flag = 0;
      }

      p_prec = p;
      p = p_succ;
      p_succ = p_succ->next;
    }
  }
}

anche sottovento non ha tutti i torti.. tutto dipende da quanta memoria occupa la lista se devi duplicarla.
il problema di agire scambiando gli elementi invece è che per ogni scambio vanno via 4 assegnamenti con il codice che ho scritto, e per ogni confronto 3 (quelli per fa scorrere la lista) in più bisogna anche valutare quanto pesa la funzione che compara i valori visto che sono stringhe... in sostanza l'obbiettivo è minimizzare gli scambi e le comparazioni per diminuire il tempo di esecuzione!
ci sono algoritmi molto migliori di quello che ho postato, come insertion sort o selection sort (lasciamo stare quick sort, merge sort, shell sort, heap sort altrimenti non finiamo più.. c'è troppa letteratura in materia).
il selection sort ad esempio scorre tutta la lista, trova il minimo e lo mette all'inizio, poi scorre la lista dall'elemento dopo, trova ancora il minimo e lo mette dopo il primo e così via... in questo modo minimizzi gli scambi senz'altro (e diminuisci un pò le comparazioni perchè via via escludi gli elementi che hai già piazzato).
a me sembra un buon compromesso tra semplicità dell'implementazione e risultato ottenuto.. insertion sort sarebbe meglio ma non ho voglia
altrimenti duplica la lista

[VendeR]

grazie!! io ci avevo pensato al selection sort ma li per li con le liste non sapevo come implementarlo.. mi sa che mi ricreo la lista che faccio prima
cmq grazie mille per gli aiuti!!!

[sottovento]

Originariamente inviato da k0nt3

intanto ho corretto un pò di errori nel codice che ho postato prima e l'ho provato a compilare (con gcc ovviamente):
CHANGELOG: 14/05/06 21:50 - ora funziona -
... omissis ...

Ciao
secondo ma hai scritto un buon codice, ma c'e' ancora qualche piccolo aggiustamento da fare.
Per esempio, se do in ingresso la sequenza
1000 34 64 250 64 243 7 87 12 432

da ordinare in maniera crescente (mi basta definire la macro di comparazione), ottengo

1000 7 12 34 64 64 87 243 250 432

(Naturalmente il test era mirato: il primo elemento non viene mai comparato)

High Flying
Sottovento

[VendeR]

però nel mio caso va bene che il primo elemento non venga mai comparato perchè è la "testa" della mia lista, la quale anche se è devinita come elmento della lista, non contiene nient'altro a parte il puntatore al secondo elemento
ma in pratica con quel codice controllo se il valore precedente è maggiore del successivo, se si li inverto, (tenendo conto del puntatore precedente al primo valore comparato).. no??

[sottovento]

Originariamente inviato da VendeR

però nel mio caso va bene che il primo elemento non venga mai comparato perchè è la "testa" della mia lista, la quale anche se è devinita come elmento della lista, non contiene nient'altro a parte il puntatore al secondo elemento

Opps, mi era sfuggita questa informazione

Originariamente inviato da VendeR

ma in pratica con quel codice controllo se il valore precedente è maggiore del successivo, se si li inverto, (tenendo conto del puntatore precedente al primo valore comparato).. no??

Esatto.
Fai solo attenzione che il codice va in crash se non hai elementi in lista, o se hai solo la testa (quella c'e' sempre e non contiene info, giusto?)

High Flying
Sottovento

[VendeR]

si la testa c'è sempre e non contiene elementi..
cmq allora non andrà mai in crash perchè prima di chiamare la funzione di ordinamento, controllo che la testo non punti a null
solo una cosuccio.. mi potresti spiegare per bene cosa fa il programma? cioè confronta un valore con il successivo e se è maggiore li inverte, ma poi? cioè dopo confronta cosa con cosa??

[k0nt3]

si.. leggendo le specifiche che aveva dato VendeR avevo ignorato il primo elemento della lista ma vedo che è già chiaro questo.

@VendeR:
il codice fa questo:
1) scorre tutta la lista e tutte le volte che l'elemento selezionato è maggiore del successivo lo scambia
2) se ci sono stati degli scambi nel precedente passo lo ripete
3) se non ci sono stati scambi durante lo scorrimento della lista significa che la lista è ordinata

esempio:
metti che ho la seguente lista: 8, 3, 10, 13, 5, 1
prendo in considerazione il primo elemento (8) che è maggiore del successivo (3) e quindi li scambio ottenendo: 3, 8, 10, 13, 5, 1
ora passo al secondo elemento e non lo scambio (8<10), e il terzo neppure.
il quarto invece lo devo scambiare e ottengo: 3, 8, 10, 5, 13, 1
il quinto pure: 3, 8, 10, 5, 1, 13
ci sono stati degli scambi in questa passata della lista, quindi è necessaria un'altra passata.. per brevità scrivo il risultato finale della seconda passata: 3, 8, 5, 1, 10, 13
ci sono stati ancora degli scambi quindi ripeto l'operazione e ottengo: 3, 5, 1, 8, 10, 13
e ancora (siamo alla quarta passata): 3, 1, 5, 8, 10, 13
c'è stato ancora uno scambio quindi: 1, 3, 5, 8, 10, 13
ora se ripeto ancora non devo fare nessuno scambio, quindi mi accorgo che la lista è ordinata e esco dal while

ps. l'esempio è volutamente sfigato, il bubble sort in alcuni casi si comporta abbastanza bene.
pps. adesso hai capito il perchè di bubble sort? il numeri vanno a galla come le bollicine