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

[Vincenzo1968]

C'è, nel codice precedente, un bug per quanto riguarda le liste doppiamente concatenate.
Posto il codice corretto (almeno spero: l'ho testato più volte).
Se riscontrate qualche bug, per favore, fatemelo sapere.

Dopo tanto lavoro, alla fine credo ne sia valsa la pena. Facendo una ricerca su google, non sono riuscito a trovare un
solo esempio di codice per il QuickSort applicato alla Double linked list (e figuriamoci con tutt'e due i metodi : ricorsivo e iterativo).

Double linked list

#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 *prev;
	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;

// Routines per la gestione ordinaria della lista

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->prev = NULL;
	n->next = NULL;

	nMemoriaAllocata += sizeof(Persona);

	return n;
}

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

	int more = 1;

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

	if( (*Confronta)(n, Pers) > 0 )
	{
		nuovo = NewNode(Pers);
		nuovo->next = first;
		first->prev = nuovo;
		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);
			n->next->prev = nuovo;
			nuovo->next = n->next;
			nuovo->prev = n;
			n->next = nuovo;
			return first;
		}
		n = n->next;
	}

	nuovo = NewNode(Pers);

	n->next = nuovo;

	nuovo->prev = n;

	return first;
}

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

	int more = 1;

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

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

	nuovo = NewNode(Pers);

	n->next = nuovo;

	nuovo->prev = n;

	return first;
}

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* Delete(Persona *Pers, Persona *first)
{
	Persona *n = first;

	n = Find(Pers, first);

	if( n == NULL )
		return first;

	if( n->next != NULL )
		n->next->prev = n->prev;

	if( n->prev != NULL )
		n->prev->next = n->next;

	if( n == first )
	{
		n = n->next;
		free(first);
		nMemoriaDeallocata += sizeof(struct tagPersona);
		return n;
	}

	free(n);
	nMemoriaDeallocata += sizeof(Persona);

	return first;
}

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

	Persona *z;

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

	printf("Stampa in ordine decrescente:\n");

	//x = 0;
	while ( z != NULL )
	{
		printf("%d %s %s\n", z->Anni, z->Cognome, z->Nome);
		z = z->prev;	
	}
	printf("\n\n");
}

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


// Routines per l'ordinamento

Persona *SwapNodes(Persona *node1, Persona *node2, Persona *first)
{
	if ( node1 == node2 )
		return first;

	Persona *node1prev, *node2prev, *node1next, *node2next;

	Persona * tmp;

	node1prev = node1->prev;
	node2prev = node2->prev;

	node1next = node1->next;
	node2next = node2->next;

	if (node1 != first)
	{
		node1prev->next = node2;
		node1next->prev = node2;
	}
	else
	{
		node1next->prev = node2;
		first = node2;
	}

	if ( node1->next != node2 )
	{
		node2prev->next = node1;
		if ( node2next )
			node2next->prev = node1;

		tmp = node1;
		node1 = node2;
		node2 = tmp;

		node1->prev = node1prev;
		node1->next = node1next;

		node2->prev = node2prev;
		node2->next = node2next;
	}
	else
	{
		tmp = node2->next;
		node2->next = node1;
		node1->next = tmp;

		node2->prev = node1prev;
		node1->prev = node2;

		if ( node2next )
			node2next->prev = node1->prev->next;
	}
	
	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 *first, Persona *end)
{
	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(first, end);

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

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

Persona * QuickSortNonRecursive(Persona *first, int list_start, int list_end) 
{
	Persona *pivot, *left = first, *right = first, *tmp;
	int i, j;
	int s = 0;

	int stack[64];

	if (list_end <= list_start)
		return first;

	stack[s++] = list_start;
	stack[s++] = list_end;

	while ( s > 0 )
	{
		list_end = stack[--s];
		list_start = stack[--s];

		if ( list_start >= list_end )
			continue;

		// INIZIO PARTIZIONAMENTO

		i = list_start;
		j = list_end - 1;

		right = GetNthNode(list_end, first);
		left = GetNthNode(list_start, first);
		pivot = SelectPivot(left, right);
		right = pivot->prev;

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

			for(;((*Confronta)(right, pivot)>0) && (i< j);right=right->prev,j--);

			if ( i >= j )
				break;
	
			first = SwapNodes(left, right, first);
			tmp = left;
			left = right;
			right = tmp;
		}

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

		// FINE PARTIZIONAMENTO

		if (i - list_start > list_end - i)
		{
			stack[s++] = list_start;
			stack[s++] = i - 1;
			stack[s++] = i + 1;
			stack[s++] = list_end;
		}
		else
		{
			stack[s++] = i + 1;
			stack[s++] = list_end;
			stack[s++] = list_start;
			stack[s++] = i - 1;
		}
	}

	return first;
}

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 = pivot->prev;

	tmp = NULL;

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

		for(;((*Confronta)(right,pivot) > 0) && (i < j); right=right->prev,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);

	return QuickSortNonRecursive(first, 1, n);
}

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

	int i, N;

	Persona Pers;
	Persona *pPers = NULL;

	N = 5;

	/*
	for ( i = 1000; i > 0; i-- )
	{
		Pers.Anni = i;
		strcpy(Pers.Cognome, "A");
		strcpy(Pers.Nome, "B");

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

	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\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\n");
	Print(pPers);

	Free(pPers);

	printf("\nTotale memoria allocata:   %d\n", nMemoriaAllocata);
	printf("\nTotale memoria deallocata: %d\n", nMemoriaDeallocata);

	return 0;
}