[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]

Originariamente inviato da 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

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? 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

[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

[gsa390]

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]

Originariamente inviato da 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 ?

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]

Originariamente inviato da 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.

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

[DanieleC88]

Originariamente inviato da cionci

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]

Originariamente inviato da cionci

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

[DanieleC88]

Originariamente inviato da lupoxxx87

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);
}