#include <stdio.h>
#include <stdlib.h>
#include <time.h>//Per la random
/* definizione della struttura del nodo */
typedef struct nodo {int valore;
struct nodo * next;
//struct nodo * prev;
} Nodo ;
//Gestione di una lista doppiamente concatenata:
void add(Nodo ** lista, Nodo ** corrente, int valore);//aggiunge un nodo subito dopo il nodo corrente
void print(Nodo * lista);//stampa la lista
//Per ordinare la lista
void sort(Nodo ** lista);//ordina la lista con merge-sort
Nodo * merge(Nodo * L1, Nodo * L2);
void split(Nodo * lista, Nodo ** pari, Nodo ** dispari);
void push(Nodo * lista, Nodo ** elemento);
void main()
{
Nodo * lista = NULL;//Definisce la lista
Nodo * corrente = NULL; //Nodo corrente acquisito
int i, a[10], n=10;
//Genera un vettore casuale numeri da 1 a 50 random
srand((unsigned int)time(0));//Genero un seed per la creazione dell'array
for (i=0;i<=n-1;i++) a[i]=rand()%51; //Creo l'array
//Genero una lista a partire dall'array
for (i=0;i<=n-1;i++) add(&lista, &corrente, a[i]);
printf("--------------------------------------------------\n");
printf(" Applicazione dell'algoritmo MERGE-SORT a una li-\n");
printf(" sta doppiamente concatenata\n");
printf("--------------------------------------------------\n");
printf(" Verra' generata una lista casuale da ordinare:\n\n");
printf(" LISTA GENERATA DISORDINATA\n\n ");
if (lista != NULL)print(lista);
else printf("vuota\n");
printf("\n--------------------------------------------------\n");
printf(" Chiamata alla function MERGESORT:\n\n");
printf(" LISTA ORDINATA CON MERGESORT:\n\n ");
//ORDINA LA LISTA
if (lista != NULL) sort(&lista);
else printf("vuota\n");
//STAMPA LA LISTA ORDINATA
if (lista != NULL)print(lista);
else printf("vuota\n");
printf("\n--------------------------------------------------\n");
system("PAUSE");
}
// Aggiunge un nuovo nodo alla lista di dato VALORE
// subito dopo il nodo CORRENTE
void add(Nodo ** lista, Nodo ** corrente, int valore)
{
//alloco memoria per il nodo da inserire
Nodo *nuovo = calloc(1,sizeof(Nodo));
//copio le informazioni nel nuovo nodo
nuovo->valore = valore;
//nel caso in cui il valore sia il primo nodo, lo faccio puntare da *lista
if (*lista == NULL) {*lista = nuovo;
*corrente = nuovo;
return;
}
//collego il nuovo nodo a quello successivo e a quello precedente
if (*corrente != NULL) {nuovo->next = (*corrente)->next; //nuovo a successivo
// nuovo->prev = *corrente; //nuovo a precedente
(*corrente)->next = nuovo; //faccio puntare nodo dal precedente
// if (nuovo->next != NULL) //se il successivo esiste
// nuovo->next->prev = nuovo; //faccio puntare nodo dal successivo
}
//visto che devo aggiungere in coda, collego il puntatore corrente all'ultimo nodo aggiunto
//in modo da averlo già in posizione
*corrente = nuovo;
}
//Stampa della lista RICORSIVA
void print(Nodo * lista)
{if (lista == NULL) return;//ISTANZA BANALE [Lista vuota]
printf("%3d ",lista->valore);//Stampa elemento
print(lista->next);//Chiamata ricorsiva passandogli il successivo
}
//funzione principale [MERGESORT] che chiamerà le funzioni [SPLIT] e [MERGE]
//le function sono tutte e tre RICORSIVE
void sort(Nodo ** lista)
{//queste sono le teste delle sottoliste da ricavare dalla lista in input
Nodo * pari = NULL;
Nodo * dispari = NULL;
//una lista di 1 solo elemento è già ordinata
// ISTANZA BANALE, 0 o 1 elementi
if (*lista == NULL) return;
if ((*lista)->next == NULL) return;
//una lista di 2 o più elementi si ordina eseguendo:
//divido la lista in due liste minori di pari dimensioni
split(*lista,&pari,&dispari);
//AUTOATTIVAZIONI
//viene chiamata di nuovo la function sort per entrambe le liste appena generate
sort(&pari);//CHIAMATA RICORSIVA 1
sort(&dispari);//CHIAMATA RICORSIVA 2
//fondo le liste a due a due a partire dall'istanza banale
*lista = merge(pari,dispari);
printf("Ok\n");
}
// merge di due liste doppiamente linkate e ordinate
Nodo * merge(Nodo * L1, Nodo * L2)
{Nodo * minore = NULL;
//SE una delle due liste è vuota (NULL)
//il risultato è l'altra lista
//ISTANZA BANALE
if (L1 == NULL) return L2;
if (L2 == NULL) return L1;
//ALTRIMENTI confronto i primi elementi L1 e L2 delle due liste
if (L1->valore < L2->valore) {minore = L1;//L1 è primo elemento della lista risultante
//AUTOATTIVAZIONE
minore->next = merge(minore->next,L2);//collego il successivo del nodo minore
//a chiamata ricorsiva con l'altra lista
}
else { minore = L2;//L2 è primo elemento della lista risultante
minore->next = merge(L1,minore->next);//idem come sopra
}
//terminate le autoattivazioni, genero il legame inverso
// if (minore->next != NULL) minore->next->prev = minore;
//restituisco la lista fusa [che ovviamente parte da minore]
printf("OK\n");
return minore;
}
// divide una lista in due (elementi in posizione pari/dispari)
void split(Nodo * lista, Nodo ** pari, Nodo ** dispari)
{
//CASO BANALE: la lista è vuota
if (lista == NULL) {*pari = NULL;
*dispari = NULL;
return;
}
//se ci sono almeno 2 elementi: CHIAMATA RICORSIVA saltando i primi due
//AUTOATTIVAZIONE
if (lista->next != NULL) split(lista->next->next,pari,dispari);
//Aggiungo in testa prima il secondo (se c'e') alla semilista dispari
if (lista->next != NULL)push(lista->next,dispari);
//poi aggiungo il primo in testa alla lista pari (deve esservi per forza un nodo)
if(lista!=NULL) push(lista,pari);
printf("OOOK\n");
}
void push(Nodo * lista, Nodo ** elemento)
{//Se l'elemento non è vuoto
if (*elemento != NULL)
//Il precendete di elemento è la lista
// (*elemento)->prev = lista;
//il prossimo di lista è l'elemento
lista->next = *elemento;
*elemento = lista; //elemento è la nuova testa
}
