[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, :muro: :muro: , 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 :muro: 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]

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]

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 :D :D

[k0nt3]

volevo capire il tuo codice ma non ne ho avuto più voglia :stordita: :D 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! :D :D
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 :D

[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 :D )

[VendeR]

eh allora mi sa che dovrò fare un bel debug del programma (so come farlo :Prrr: )... 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 :D
altrimenti duplica la lista :fagiano:

[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 :D :D
cmq grazie mille per gli aiuti!!!

[sottovento]

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 :D :D
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]

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 :D :D

Opps, mi era sfuggita questa informazione :)


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 :D
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 ;)

[sottovento]

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 :D

Mi ero spiegato male: ci deve essere anche un altro elemento, oltre alla testa, altrimenti va in crash.
Comunque il codice scritto da k0nt3 e' buono e facilmente leggibile, per cui con una semplice modifica puoi togliere questa piccola imperfezione.

High Flying
Sottovento

[VendeR]

Mi ero spiegato male: ci deve essere anche un altro elemento, oltre alla testa, altrimenti va in crash.
Comunque il codice scritto da k0nt3 e' buono e facilmente leggibile, per cui con una semplice modifica puoi togliere questa piccola imperfezione.

High Flying
Sottovento

ah non ci avevo fatto a quel caso particolare (non ci avevo pensato :doh: :D 9 ) comunque ho appena risolto mettendo un controllo in cui se ho un solo elemento nella lista (testa esclusa) non cicla :cool:



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


si ora ho capito bene... grazie mille per il codice!! la mia versione con i puntatori del bubble sort aveva un paio di difetti che però davano un pò di casini :D :D


grazie mille raga a tutti per i consigli