[C]ordinamento lista

[gsa390]

salve, dovrei scrivere una funzione che ordini una lista, as esempio in base alla matricola. Vorrei sapere se mi conviene scambiare gli indirizzi(next succesivo) oppure tutti i restanti valori?

typedef struct studente{
int matricola;
char cognome[20];
char nome[20];
next successivo;
}studente;

[lupoxxx87]

scusa ma ho un dubbio....tu hai fatto una struttura next che è un puntatore a studente ?

[gsa390]

si esattamente ;)

ho fatto una specie di bubblesort, devo ancora scrivere la funzione swap che scambia matricola, nome, ecc.. ma quella è facile.

Secondo voi va bene questa funzione?


void bubblelist (studente *first)
{
studente *tmp, *tmp2;
tmp=tmp2=first->successivo;


while(tmp2!=NULL)
{
while(tmp!=NULL)
{
if(tmp2->matricola>tmp->matricola)
{
swap(*tmp2, *tmp);
}
tmp=tmp->successivo;
}
tmp=tmp2=tmp2->successivo;
}
}

[lupoxxx87]

ma non facevi prima con

typedef struct studente{
int matricola;
char cognome[20];
char nome[20];
studente* successivo;
}studente;

visto che hai fatto una typedef ?
comunque, in una lista, non ha senso invertire gli scambiare gli attributi interni di una struttura.

può andar bene fare scambi sui puntatori.

può andare ancora meglio se ti crei un array e ci metti dentro gli indirizzi di memoria della struttura ordinata, così puoi scandire velocemente l'array una volta che hai letto tutta la lista

[gsa390]

ma non facevi prima con

typedef struct studente{
int matricola;
char cognome[20];
char nome[20];
studente* successivo;
}studente;

visto che hai fatto una typedef ?
comunque, in una lista, non ha senso invertire gli scambiare gli attributi interni di una struttura.

può andar bene fare scambi sui puntatori.

può andare ancora meglio se ti crei un array e ci metti dentro gli indirizzi di memoria della struttura ordinata, così puoi scandire velocemente l'array una volta che hai letto tutta la lista

non ho fatto studente* successivo perchè il prof dell'uni ha detto che non va bene (o almeno con alcuni compilatori potrebbe dare errori).

cmq ho provato a scambiare i puntatori ma mi incasino, potresti darmi un aiutino?:D te ne sarei grato

[lupoxxx87]

penso che il modo migliore per ordinare una lista con singolo link sia il mergesort

[gsa390]

ci è stato esplicitamente chiesto di svilupparla simile a un bubblesort :muro:

[lupoxxx87]

scusa ma....se sai qual'è l'algoritmo, hai già la struttura, hai già la lista, e non riesci a fare lo scambio in un modo.....

fallo nell'altro e basta
:p

[gsa390]

:p voglio provare a farlo come dice il prof... è molto rompiballe e il 5 maggio ho la prova...

[DanieleC88]

Qual è il problema nello scambiare i puntatori? Non ho capito in che punto trovi difficoltà.

[lupoxxx87]

il bubblesort di per sè è ottimizzato per array...
per farlo funzionare su una lista devi avere nodi con doppio puntatore, altrimenti non penso si possa ordinare la lista stessa.

a meno che tu non abbia una seconda lista che costruisci man mano

[lock cmpxchg8b %ebx]

ma non facevi prima con

typedef struct studente{
int matricola;
char cognome[20];
char nome[20];
studente* successivo;
}studente;

visto che hai fatto una typedef ?
In C per dichiarare un tipo strutturato bisogna prefissarlo esplicitamente con la keyword struct (o assegnare un nome alternativo alla struttura con typedef).
Il problema (nel tuo esempio) è che alla linea
studente* successivo;
il typedef non è stato ancora "completato", e quindi il compilatore non riesce a identificare il tipo.
Immagino sia questo il problema a cui si riferiva il suo professore, anche se la soluzione è molto semplice:
struct studente* successivo;

In C++ invece il tuo codice è corretto, visto che non serve prefissare le dichiarazioni dei tipi strutturati (oltrettuto rendendo il typedef rindondante).

[cionci]

il bubblesort di per sè è ottimizzato per array...
per farlo funzionare su una lista devi avere nodi con doppio puntatore, altrimenti non penso si possa ordinare la lista stessa.
Perché no ? Ti puoi sempre mantenere il puntatore all'elemento precedente...

[DanieleC88]

Perché no ? Ti puoi sempre mantenere il puntatore all'elemento precedente...

Esattamente...
Se di norma il bubble sort viene una cosa così:
algoritmo BubbleSort(array A, lunghezza n)
{
per i in 1..n {
per j in 1..(i - 1) {
se (A[j] > A[i]) {
scambia A[i] ed A[j]
}
}
}
}

su liste i cui nodi hanno un solo collegamento (ai prossimi nodi e non ai precedenti) si può tener traccia del vecchio iteratore man mano che si avanza, e bisogna solo fare un po' di attenzione ai puntatori quando è necessario scambiare.

La butto là:

algoritmo BubbleSort(lista L)
{
prec_i = nullo # il nodo che precede i
i = testa(L) # iteratore i

finché (i non è nullo) {
prec_j = nullo # il nodo che precede j
j = testa(L) # iteratore j

finché (j non è nullo) e (prossimo(j) non è i) {
se (chiave(j) > chiave(i) {
#
# Aggiorna i puntatori al prossimo nodo sui nodi precedenti i e j.
#
se (prec_j non è nullo) {
prossimo(prec_j) = i
}

se (prec_i non è nullo) {
prossimo(prec_i) = j
}

#
# Aggiorna i puntatori al prossimo nodo su i e j.
#
next_j = prossimo(j)
prossimo(j) = prossimo(i)
prossimo(i) = next_j

#
# Scambia i riferimenti ai nodi i e j e aggiorna il puntatore al nodo precedente i.
#
prec_i = i
i = j
j = prec_i
}

prec_j = j
j = prossimo(j)
}

prec_i = i
i = prossimo(i)
}
}

Ovviamente è solo pseudocodice (anche se abbastanza dettagliato, direi), è chiaro che l'implementazione in C sarà compito di gsa390.

[lupoxxx87]

Perché no ? Ti puoi sempre mantenere il puntatore all'elemento precedente...

beh concettualmente è lo stesso che avere la lista con doppio puntatore...
o cambi i parametri all'interno dell'algoritmo o cambi la struttura

[gsa390]

Daniele grazie del suggerimento, stasera visto che nn esco proverò a farlo, magari poi vi dico che ne è uscito :D

[DanieleC88]

o cambi i parametri all'interno dell'algoritmo o cambi la struttura

Non proprio: una cosa è l'algoritmo, un'altra è l'implementazione. Se la logica è identica ma l'implementazione è riadattata per una diversa struttura dati, non è che cambi l'algoritmo... Sempre bubble sort rimane. :)

[gsa390]

ragazzi un pò in ritardo vi porgo la soluzione del prof :)

void ordina(studente **head)
{
while(scorri(&head));
}

int scorri(studente ***head)
{
int scambi;
studente *act, *prec;
for (scambi=0, act=prec=**head; act->successivo!=NULL;)
{
if(act->matricola>=act->successivo->matricola)
{
if(prec==act)//salva la situazione del primo record
{
**head=act->successivo;
act->successivo=act->successivo->successivo;
(**head)->successivo=act;
prec=(**head);
}
else
{
swap(&prec,&act);
prec=prec->successivo;
}
scambi++;
}
else
{
prec=act;
act=act->succesivo;
}
}
return (scambi);


void swap(studente **prec, studente **act)
{
(*prec)->successivo=(*act)->successivo;
(*act)->successivo=(*act)->successivo->successivo;
(*prec)->succesivo->successivo=(*act);
}