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

[Vincenzo1968]

Questo invece è il codice per le 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("\nStampa in ordine decrescente:\n\n");

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

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)
{
	Persona *node1prev, *node2prev, *tmp, *tmp2;

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

	tmp = node2->next;

	tmp2 = node1->next;

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

	// Sono due nodi adiacenti?
	if (node1->next == node2) 
	{
		// I nodi sono adiacenti
		
		node2->next = node1;
		node1->next = tmp;

		node2->prev = node1prev;
		node1->prev = node2;
		
		if ( node1->next )
			tmp->prev = node1;
	}
	else 
	{
		// I nodi non sono adiacenti

		node2->next = node1->next;
		node1->next = tmp;
		
		node2->prev = node1prev;
		node1->prev = node2prev;
		
		node2prev->next = node1;
		node2prev->prev = tmp2;
		
		if ( node1->next )
			tmp->prev = node1;
		
		tmp2->prev = node2;
	}
	
	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 ( right == NULL )
		right = end;

	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 = pivot->prev;
	if ( right == NULL )
		right = pivot;
	
	for(;;)
	{
		for(; ( (*Confronta)(left, pivot) < 0 ); left = left->next, i++);
		
		for(; ( (*Confronta)(right, pivot) > 0 ); 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);
}



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\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\nTotale Memoria Deallocata: %d\n", nMemoriaAllocata, nMemoriaDeallocata);

	return 0;
}