#include <stdio.h>
#include <stdlib.h>

/*
PROGRAMA:    lista_enlazada_ordenar.cpp
DESCRIPCIÓN: Implementación de una lista enlazada
AUTOR: Fco. J. H. L.
VERSIÓN:  1.0
Fecha Inicio: 26-Agosto-2014
Fecha Actualización: 09-Septiembre-2014
*/

typedef struct _nodo{
	int valor;
	struct _nodo *siguiente;
}tipoNodo;


void insertar(tipoNodo **lista,int x);
int eliminar(tipoNodo **lista);
void insertar_ultimaposicion(tipoNodo **lista,int x);
void desplegar(tipoNodo *lista);
void ordenar_burbuja(tipoNodo **lista);
int contar_nodos(tipoNodo *lista);

int main(void){
	tipoNodo *lista=NULL;//La lista está vacía

	insertar(&lista,20);
	insertar(&lista,50);
	insertar(&lista,40);
	insertar(&lista,10);
	insertar(&lista,30);

	desplegar(lista);
	//desplegar(lista);

	ordenar_burbuja(&lista);

	desplegar(lista);

	//insertar_ultimaposicion(&lista,50);


	/*printf("%d ",eliminar(&lista));
	printf("%d ",eliminar(&lista));

	printf("%d ",eliminar(&lista));
	*/

	system("pause");
	return(0);
}

void insertar(tipoNodo **lista,int x){
	//Crear memoria del nodo nuevo
	tipoNodo *nodo_nuevo;
	nodo_nuevo=(tipoNodo *)malloc(sizeof(tipoNodo));
	nodo_nuevo->valor=x;

	if (*lista==NULL){//Lista vacía
		nodo_nuevo->siguiente=NULL;
		*lista=nodo_nuevo;
	}
	else{
		//Programar cuando la lista no está vacía...
		nodo_nuevo->siguiente=*lista;
		*lista=nodo_nuevo;
	}
}


int eliminar(tipoNodo **lista){
	int x_aux;
	//1
	tipoNodo *auxiliar;
	auxiliar=*lista;

	//Validar que la lista está vacía
	if(auxiliar==NULL){
		printf("\nLa lista está vacía...");
		x_aux=-1;
	}
	else{
		//2
		*lista=(*lista)->siguiente;

		x_aux=auxiliar->valor;

		//3 Liberar la memoria
		free(auxiliar);

	}

	return(x_aux);
}

void insertar_ultimaposicion(tipoNodo **lista,int x){
	tipoNodo *ultimo;

	//Crear memoria del nodo nuevo
	tipoNodo *nodo_nuevo;
	nodo_nuevo=(tipoNodo *)malloc(sizeof(tipoNodo));
	nodo_nuevo->valor=x;

	if (*lista==NULL){//Lista vacía
		nodo_nuevo->siguiente=NULL;
		*lista=nodo_nuevo;
	}
	else{
		ultimo=*lista;
		while(ultimo->siguiente!=NULL){
			ultimo=ultimo->siguiente;
		}
		nodo_nuevo->siguiente=NULL;
		ultimo->siguiente=nodo_nuevo;
	}
}

void desplegar(tipoNodo *lista){
	printf("\nLista: ");
	while(lista!=NULL){
		printf("%d ",(lista)->valor);
		lista=(lista)->siguiente;
	}
}


void ordenar_burbuja(tipoNodo **lista){
	tipoNodo *aux_j,*aux_jmas1;
	int N=contar_nodos(*lista);

	for(int i=1;i<N;i++){
		aux_j=*lista;

		for(int j=0;j<N-i;j++){
			aux_jmas1=aux_j->siguiente;

			if(aux_j->valor > aux_jmas1->valor){
				aux_j->siguiente=aux_jmas1->siguiente;
				aux_jmas1->siguiente=aux_j;

				if(aux_j==*lista){
					*lista=aux_jmas1;
				}
			
			}
			else{
				aux_j=aux_j->siguiente;
			}
		}

	}
}

int contar_nodos(tipoNodo *lista){
	int N=0;
	while(lista!=NULL){
		N++;
		lista=lista->siguiente;
	}
	return(N);
}