[C] Double Linked List - Puntatori a funzione - Algoritmi di ordinamento - Quick Sort

[Vincenzo1968]

Un amico, studente universitario, mi ha chiesto un algoritmo per l'ordinamento di una double linked list.
Nella speranza che possa essere utile a qualcuno, posto il codice.

Partiamo da una lista semplice (con solo il puntatore all'elemento successivo)

Codice :

#include <stdio.h>
#include <malloc.h>
#include <string.h>


int nMemoriaAllocata = 0;
int nMemoriaDeallocata = 0;


struct tagPersona
{
	int Anni;
	char Cognome[50];
	char Nome[50];
	struct tagPersona *next;
};


typedef struct tagPersona Persona;


int ConfrontaAnni(const Persona *p1, const Persona *p2)
{
	if ( p1->Anni < p2->Anni )
		return -1;
	else if ( p1->Anni > p2->Anni )
		return 1;
	else
		return 0;
}

/*
int ConfrontaCognome(const Persona *p1, const Persona *p2)
{
	return strcmp(p1->Cognome, p2->Cognome);
}
*/

int ConfrontaCognomeNome(const Persona *p1, const Persona *p2)
{
	char szCognomeNome1[100];
	char szCognomeNome2[100];

	strcpy(szCognomeNome1, p1->Cognome);
	strcat(szCognomeNome1, p1->Nome);

	strcpy(szCognomeNome2, p2->Cognome);
	strcat(szCognomeNome2, p2->Nome);

	return strcmp(szCognomeNome1, szCognomeNome2);
}


int (*Confronta)(const Persona *, const Persona *) = NULL;



Persona* Find(Persona *Pers, Persona *first)
{
	Persona *n = first;

	while( n != NULL )
	{
		if( (*Confronta)(n, Pers) == 0 )
			return n;
		n = n->next;
	}

	return NULL;
}

Persona *FindPrev(Persona *curr, Persona *first)
{
	for(; first && first->next; first = first->next)
	{
		if( curr == first->next )
		{
			break;
		}
	}
	
	if ( first->next != curr )
	{
		return curr;
	}
	
	return first;
}

Persona* Delete(Persona *Pers, Persona *first)
{
	Persona *n = first;

	n = Find(Pers, first);

	if( n == NULL )
		return first;

	// Cancellazione primo elemento
	if( n == first )
	{
		n = n->next;
		free(first);
		nMemoriaDeallocata += sizeof(Persona);
		return n;
	}

	// Prendiamo un puntatore all'elemento precedente;
	// ci servirà per cancellare l'elemento
	Persona *prevPers = NULL;
	n = first;

	while ( (*Confronta)(n, Pers) != 0 )
	{
		prevPers = n;
		n = n->next;
	}

	// Cancellazione ultimo elemento
	if ( n->next == NULL )
	{
		free(n);
		nMemoriaDeallocata += sizeof(Persona);
		prevPers->next = NULL;
		return first;
	}

	// Cancellazione elemento
	prevPers->next = n->next;
	free(n);
	nMemoriaDeallocata += sizeof(Persona);

	return first;
}

void Print(Persona *first)
{
	Persona *n = first;

	while( n != NULL )
	{
		printf("%d %s %s \n", n->Anni, n->Cognome, n->Nome);
		n = n->next;
	}
}

void Free(Persona *first)
{
	Persona *n1 = first, *n2;
	while ( n1 != NULL )
	{
		n2 = n1->next;
		free(n1);
		nMemoriaDeallocata += sizeof(Persona);
		n1 = n2;
	}
}

Persona* NewNode(Persona *Pers)
{
	Persona *n;

	n = (Persona *)malloc(sizeof(Persona));

	if( n == NULL )
		return NULL;

	n->Anni = Pers->Anni;
	strcpy(n->Cognome, Pers->Cognome);
	strcpy(n->Nome, Pers->Nome);
	n->next = NULL;

	nMemoriaAllocata += sizeof(Persona);

	return n;
}

Persona* Insert(Persona *Pers, Persona *first)
{
	Persona *n = first, *nuovo;

	// catena vuota
	if ( first == NULL )
		return NewNode(Pers);

	if( (*Confronta)(n, Pers) > 0 )
	{
		nuovo = NewNode(Pers);
		nuovo->next = first;
		return nuovo;
	}

	while( n != NULL)
	{
		if( (*Confronta)(n, Pers) == 0 )
		{
			return first;
		}
		n = n->next;
	}

	n = first;
	while( n->next != NULL )
	{
		if( (*Confronta)(n->next, Pers) > 0 )
		{
			nuovo = NewNode(Pers);
			nuovo->next = n->next;
			n->next = nuovo;
			return first;
		}
		n = n->next;
	}

	nuovo = NewNode(Pers);

	n->next = nuovo;

	return first;
}

tagPersona* Append(Persona *Pers, Persona *first)
{
	Persona *n = first, *nuovo;

	// catena vuota
	if ( first == NULL )
		return NewNode(Pers);

	n = first;
	while( n->next != NULL )
	{
		n = n->next;
	}

	nuovo = NewNode(Pers);
	n->next = nuovo;

	return first;
}


// Routines per l'ordinamento

Persona *SwapNodes(Persona *node1, Persona *node2, Persona *first)
{
	Persona *node1prev, *node2prev, *tmp;

	node1prev = FindPrev(node1, first);
	node2prev = FindPrev(node2, first);
	
	tmp = node2->next;

	// Se l'elementop è iol primo della lista
	if (node1 != first)
	{
		node1prev->next = node2;
	}
	else
	{
		first = node2;
	}
	
	// Sono due elementi adiacenti?
	if (node1->next == node2)
	{
		node2->next = node1;
		node1->next = tmp;
	}
	else
	{
		node2->next = node1->next;
		node1->next = tmp;
		node2prev->next = node1;
	}
	
	return first;
}

Persona *GetNthNode(int n, Persona *first)
{
	int i = 1;
	for( i = 1; i < n; i++ )
	{
		first = first->next;
	}
	
	return first;
}

int NumNodes(Persona *end, Persona *first)
{
	int i;

	for( i = 1; first && (first != end); i++)
	{
		first = first->next;
	}
	
	if (first != end)
	{
		return 0;
	}

	return i;
}

int countnodes(Persona *first)
{
	int i = 0;

	for (; first; first = first->next)
		i++;

	return i;
}

Persona *SelectPivot(Persona *first, Persona *end)
{
	Persona *right, *noden;
	int n;

	n = NumNodes(end, first);

	noden = GetNthNode((int)((float)n/2+0.5), first);
	right = FindPrev(end, first);

	if (noden != right)
	{
		SwapNodes(noden, right->next, first);
		return noden;
	}
	else
	{
		return noden->next;
	}
}

Persona * quicksort(Persona *first, int list_start, int list_end) 
{
	Persona *pivot, *left = first, *right = first, *tmp;
	int i = list_start, j = list_end - 1;

	if (list_start >= list_end)
	{
		return first;
	}

	right = GetNthNode(list_end, first);
	left = GetNthNode(list_start, first);

	pivot = SelectPivot(left, right);

	right = FindPrev(pivot, left);

	for(;;)
	{
		for(; ( (*Confronta)(left, pivot) < 0 ); left=left->next, i++);

		for(; ( (*Confronta)(right, pivot) > 0 ) ; right = FindPrev(right, first), j--);

		if (i < j)
		{
			first = SwapNodes(left, right, first);
			tmp = left;
			left = right;
			right = tmp;
		}
		else
			break;
	}

	// Ripristina il pivot
	first = SwapNodes(left, pivot, first); 

	first = quicksort(first, list_start, i-1);
	first = quicksort(first, i+1, list_end);

	return first;
}

// Wrapper per la funzione 'quicksort'
Persona *QSort(Persona *first)
{
	int n;
  
	n = countnodes(first);

	// Chiama la funzione 'quicksort'
	// Numeriamo gli elementi da 1 a n
	// invece che da 0 a n-1
	return quicksort(first, 1, n);
}


int main(int argc, char* argv[])
{
	Confronta = ConfrontaCognomeNome;

	int i, N;

	Persona Pers;
	Persona *pPers = NULL;

	N = 5;

	Pers.Anni = 45;
	strcpy(Pers.Cognome, "Sciascia");
	strcpy(Pers.Nome, "Leonardo");

	//pPers = Insert(&Pers, pPers);
	pPers = Append(&Pers, pPers);

	for ( i = 2; i <= N; i++ )
	{
		if ( i == 2 )
		{
			Pers.Anni = 70;
			strcpy(Pers.Cognome, "Camilleri");
			strcpy(Pers.Nome, "Andrea");
		}
		else if ( i == 3 )
		{
			Pers.Anni = 54;
			strcpy(Pers.Cognome, "Orwell");
			strcpy(Pers.Nome, "George");
		}
		else if ( i == 4 )
		{
			Pers.Anni = 65;
			strcpy(Pers.Cognome, "Pirandello");
			strcpy(Pers.Nome, "Luigi");
		}
		else if ( i == 5 )
		{
			Pers.Anni = 68;
			strcpy(Pers.Cognome, "Simenon");
			strcpy(Pers.Nome, "Georges");
		}

		//pPers = Insert(&Pers, pPers);
		pPers = Append(&Pers, pPers);
	}

	printf("\nLista non ordinata:\n");
	Print(pPers);

	//Pers.Anni = 54;
	//strcpy(Pers.Cognome, "Orwell");
	//strcpy(Pers.Nome, "George");
	//pPers = Delete(&Pers, pPers);

	pPers = QSort(pPers);

	printf("\nLista Ordinata:\n");
	Print(pPers);

	Free(pPers);

	printf("\nTotale Memoria Allocata: %d\nTotale Memoria Deallocata: %d\n", nMemoriaAllocata, nMemoriaDeallocata);

	return 0;
}

Per l'ordinamento utilizziamo l'algoritmo chaiamato 'Quick Sort' del mitico C.A.R. Hoare, che è generalmente considerato il
migliore (ma, nel caso di una lista con pochi elementi, come nell'esempio proposto, risultati migliori, dal punto di vista
della velocità di esecuzione, si potrebbero ottenere persino con un algoritmo poco efficiente come il 'Bubble Sort').

per confrontare due elementi, utilizziamo un puntatore a una funzione definita dall'utente:

int (*Confronta)(const Persona *, const Persona *) = NULL;

La sintassi dei puntatori a funzione è leggermente complicata ma ci permette di ordinare la lista in base a diversi parametri.
Per esempio, se invece che per Cognome + Nome, vogliamo un lista ordinata per Anni, tutto quello che dobbiamo fare, nel 'main',
è cambiare il puntatore alla funzione di confronto, da

	Confronta = ConfrontaCognomeNome;

a

	Confronta = ConfrontaAnni;

C'è da dire, infine, che il metodo migliore in assoluto, per avere una lista ordinata, è quello di ordinare gli elementi mentre
li andiamo inserendo.

È quello cha fa la funzione "Insert". Per utilizzarla, sostituiamola, nel 'main' allla chiamata alla funzione 'Append'
(e togliamo anche la chiamata alla funzione 'QSort') :

int main(int argc, char* argv[])
{
	Confronta = ConfrontaCognomeNome;

	int i, N;

	Persona Pers;
	Persona *pPers = NULL;

	N = 5;

	Pers.Anni = 45;
	strcpy(Pers.Cognome, "Sciascia");
	strcpy(Pers.Nome, "Leonardo");

	pPers = Insert(&Pers, pPers);

	for ( i = 2; i <= N; i++ )
	{
		if ( i == 2 )
		{
			Pers.Anni = 70;
			strcpy(Pers.Cognome, "Camilleri");
			strcpy(Pers.Nome, "Andrea");
		}
		else if ( i == 3 )
		{
			Pers.Anni = 54;
			strcpy(Pers.Cognome, "Orwell");
			strcpy(Pers.Nome, "George");
		}
		else if ( i == 4 )
		{
			Pers.Anni = 65;
			strcpy(Pers.Cognome, "Pirandello");
			strcpy(Pers.Nome, "Luigi");
		}
		else if ( i == 5 )
		{
			Pers.Anni = 68;
			strcpy(Pers.Cognome, "Simenon");
			strcpy(Pers.Nome, "Georges");
		}

		pPers = Insert(&Pers, pPers);
	}

	printf("\nLista non ordinata:\n");
	Print(pPers);

	printf("\nLista Ordinata:\n");
	Print(pPers);

	Free(pPers);

	printf("\nTotale Memoria Allocata: %d\nTotale Memoria Deallocata: %d\n", nMemoriaAllocata, nMemoriaDeallocata);

	return 0;
}