#include <stdio.h>
#include <stdlib.h>
//Estructura que representa los nodos de la lista enlazada
struct tipo_dato {
int num;
struct tipo_dato *sig;
};
//Declaración de funciones
struct tipo_dato *mezclar(struct tipo_dato *lista1, struct tipo_dato *lista2);
struct tipo_dato *anadir_nodo_lista(struct tipo_dato nodo, struct tipo_dato *lista);
void mostrar_lista(struct tipo_dato *lista);
int longitud_lista(struct tipo_dato *lista);
struct tipo_dato *mergeSort(struct tipo_dato *lista);
struct tipo_dato *obtener_lista2(struct tipo_dato *lista);
struct tipo_dato *anadir_nodo_fin_lista(struct tipo_dato nodo, struct tipo_dato *lista);
int main()
{
struct tipo_dato *lista=NULL, *lista2=NULL, *lista_completa=NULL, *lista_ordenada=NULL;
struct tipo_dato dato;
int i=0;
for (i=0; i<50; i+=2) {
dato.num = i%19;
lista = anadir_nodo_fin_lista(dato,lista);
}
//Mostramos la lista inicial con los valores desordenados
printf("Lista inicial: ");
mostrar_lista(lista);
for (i=0; i<40; i+=3) {
dato.num = (i+1)%17;
lista2 = anadir_nodo_fin_lista(dato,lista2);
}
lista_ordenada = mergeSort(lista);
//Mostramos la lista después de haber sido ordenada
printf("Lista ordenada: ");
mostrar_lista(lista_ordenada);
return 0;
}
//Esta función se ocupa de mezclar los valores de dos listas enlazadas ordenadas
//en una sola también ordenada. La función recibe como parámetros dos punteros
//apuntando al inicio de cada una de las listas iniciales. El dato devuelto por la
//función será un puntero al inicio de la lista resultante con los valores de las
//listas iniciales ordenados.
struct tipo_dato *mezclar(struct tipo_dato *lista1, struct tipo_dato *lista2) {
struct tipo_dato *lista_mezclada=NULL;
struct tipo_dato *ptr_aux1=NULL, *ptr_aux2=NULL;
ptr_aux1=lista1;
ptr_aux2=lista2;
//Comprobamos que las dos listas contienen elementos
while (ptr_aux1!=NULL && ptr_aux2!=NULL) {
//Si el primer elemento de una de las listas es menor que el de la otra se añade a
//lista final y se mueve el puntero de esa lista al siguiente elemento.
//Cambiando el signo < se cambia el tipo de ordenación (ascendente o descendente).
if (ptr_aux1->num < ptr_aux2->num) {
//Añadimos al final de la lista resultante el nodo correspondiente de la
//primera lista
lista_mezclada = anadir_nodo_fin_lista(*ptr_aux1, lista_mezclada);
ptr_aux1=ptr_aux1->sig;
}
else {
//Añadimos al final de la lista resultante el nodo correspondiente de la
//segunda lista
lista_mezclada = anadir_nodo_fin_lista(*ptr_aux2, lista_mezclada);
ptr_aux2=ptr_aux2->sig;
}
}
//Si lista2 se ha quedado vacía y lista1 todavía tiene elementos añadimos a
//la lista resultante todos los elementos que quedan en lista1 (ya están ordenados)
while (ptr_aux1!=NULL) {
lista_mezclada = anadir_nodo_fin_lista(*ptr_aux1, lista_mezclada);
ptr_aux1=ptr_aux1->sig;
}
//Si lista1 se ha quedado vacía y lista2 todavía tiene elementos añadimos a
//la lista resultante todos los elementos que quedan en lista2 (ya están ordenados)
while (ptr_aux2!=NULL) {
lista_mezclada = anadir_nodo_fin_lista(*ptr_aux2, lista_mezclada);
ptr_aux2=ptr_aux2->sig;
}
return lista_mezclada;
}
//Esta función recorre todos los nodos de una lista cuenta cuantos hay. La función
//recibe como parámetro un puntero al inicio de la lista enlazada y devuelve un
//entero que indica el número de nodos que contiene la lista.
int longitud_lista(struct tipo_dato *lista) {
int longitud=0;
struct tipo_dato *ptr_aux=NULL;
ptr_aux = lista;
//Recorremos todos los nodos de la lista
while (ptr_aux!=NULL) {
longitud++;
ptr_aux = ptr_aux->sig;
}
return longitud;
}
//Esta función permite añadir nodos a una lista. La función recibe como parámetros una
//estructura del tipo definido para el dato y un puntero al inicio de la lista. El dato
//que devuelve es un puntero al inicio de la lista enlazada conteniendo el nuevo nodo.
//En este caso el nuevo nodo siempre se añade al inicio de la lista.
struct tipo_dato *anadir_nodo_lista(struct tipo_dato nodo, struct tipo_dato *lista) {
struct tipo_dato *nodo_aux=NULL;
nodo_aux = (struct tipo_dato *)malloc(sizeof(struct tipo_dato));
nodo_aux->num = nodo.num;
nodo_aux->sig = lista;
return nodo_aux;
}
//Esta función permite añadir nodos a una lista. La función recibe como parámetros una
//estructura del tipo definido para el dato y un puntero al inicio de la lista. El dato
//que devuelve es un puntero al inicio de la lista enlazada conteniendo el nuevo nodo.
//En este caso el nuevo nodo siempre se añade al final de la lista.
struct tipo_dato *anadir_nodo_fin_lista(struct tipo_dato nodo, struct tipo_dato *lista) {
struct tipo_dato *ptr_aux=NULL, *ptr_ant=NULL, *nodo_aux=NULL;
nodo_aux = (struct tipo_dato *)malloc(sizeof(struct tipo_dato));
nodo_aux->num = nodo.num;
nodo_aux->sig = NULL;
ptr_ant = lista;
if (ptr_ant != NULL) {
ptr_aux = ptr_ant->sig;
while (ptr_aux != NULL) {
ptr_ant = ptr_aux;
ptr_aux = ptr_aux->sig;
}
ptr_ant->sig = nodo_aux;
}else {
lista = nodo_aux;
}
return lista;
}
//Esta función recorre la lista enlazada e imprime por pantalla información referente
//a cada uno de los nodos de la misma. Recibe como parámetro un puntero al inicio de la
//lista.
void mostrar_lista(struct tipo_dato *lista) {
struct tipo_dato *ptr_aux=NULL;
ptr_aux = lista;
while (ptr_aux != NULL) {
printf("%d ", ptr_aux->num);
ptr_aux = ptr_aux->sig;
}
printf("\n");
}
//Esta función se encarga de dividir una lista enlazada en dos mitades. En caso de que el
//número de nodos no sea par la primera mitad de la lista tendrá un elemento más que la
//segunda. Recibe como parámetro un puntero a la lista inicial sin dividir y devuelve un
//puntero a la segunda parte de la lista después de dividirla. El puntero utilizado para
//pasar como parámetro el inicio de la lista de partida no se altera por lo que apuntará
//al inicio de la primera mitad de la lista dividida.
struct tipo_dato *obtener_lista2(struct tipo_dato *lista) {
struct tipo_dato *lista_aux=NULL, *ptr_aux=NULL;
int longitud = 0, mitad=0;
lista_aux = (struct tipo_dato *)malloc(sizeof(struct tipo_dato));
longitud = longitud_lista(lista);
if (longitud%2)
mitad = (longitud/2) + 1;
else
mitad = longitud/2;
ptr_aux = lista;
//Recorremos la lista hasta el nodo anterior al que corresponde a la mitad de la lista
while (mitad-1 > 0) {
ptr_aux=ptr_aux->sig;
mitad--;
}
//Colocamos un puntero apuntando al nodo de la mitad de la lista (representa la segunda mitad de la lista)
lista_aux = ptr_aux->sig;
//Transformamos la lista original en la primera parte de la misma. La segunda mitad de la lista original queda
//sin enlazar.
ptr_aux->sig = NULL;
return lista_aux;
}
//Esta función es la que realiza el algoritmo MergeSort. Recibe como parámetro un puntero
//al inicio de la lista a ordenar. Devuelve un puntero al inicio de la lista ordenada
struct tipo_dato *mergeSort(struct tipo_dato *lista) {
struct tipo_dato *lista1=NULL, *lista2=NULL, *listaOrd1=NULL, *listaOrd2=NULL, *listaOrd=NULL;
if (longitud_lista(lista) <= 1) {
return lista;
}
else {
//Este es el puntero a la primera mitad de la lista.
lista1 = lista;
//Obtenemos la segunda parte de la lista (la segunda mitad).
lista2 = obtener_lista2(lista);
//Ordenamos recursivamente cada mitad del algoritmo
listaOrd1 = mergeSort(lista1);
listaOrd2 = mergeSort(lista2);
//Mezclamos las dos mitades ordenadas previamente
listaOrd = mezclar(listaOrd1, listaOrd2);
return listaOrd;
}
}