#pragma warning (disable : 4996)

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

struct Lista {
    int info;
    struct Lista * siguiente;
};

typedef struct Lista * NodoListaPtr;

void Insertar(NodoListaPtr *, int);
void Imprimir(NodoListaPtr);
void OrdenBurbuja(NodoListaPtr);

void Intercambio(NodoListaPtr, NodoListaPtr);
bool vacia(NodoListaPtr);

int main()
{
    NodoListaPtr Inicio = NULL;
    int i, val, max, op;

    printf("PROGRAMA DE ORDENAMIENTO BURBUJA CON LISTAS."
        "\nFECHA DE ENTREGA: 08.11.16."
        "\n"
        "\n%cCu%cntos elementos tendr%c la lista? ", 168, 160, 160);
    scanf("%d", &max);

    for (i = 0;i < max;i++) {
        printf("\nIngrese el valor del elemento %d: ", i);
        scanf("%d", &val);
        Insertar(&Inicio, val);
        Imprimir(Inicio);
        printf("\n%cDesea Ordenar la Lista?"
            "\n1 = S%c, 0 = NO: ", 168, 214);
        scanf("%d", &op);
        if (op == 1) {
            OrdenBurbuja(Inicio);
            Imprimir(Inicio);
        }
    }

    system("PAUSE");
}

bool vacia(NodoListaPtr Inicial)
{
    return Inicial == NULL;
}

void Insertar(NodoListaPtr * Inicial, int item)
{
    NodoListaPtr NuevoPtr;
    NodoListaPtr SiguientePtr;
    NodoListaPtr ActualPtr;

    NuevoPtr = (NodoListaPtr)malloc(sizeof(Lista));

    if (NuevoPtr != NULL) {
        NuevoPtr->info = item;
        NuevoPtr->siguiente = NULL;

        SiguientePtr = NULL;
        ActualPtr = *Inicial;

        if (vacia(*Inicial)) {
            NuevoPtr->siguiente = *Inicial;
            *Inicial = NuevoPtr;
        }
        else
        {
            SiguientePtr = *Inicial;

            while (SiguientePtr->siguiente != NULL) {
                SiguientePtr = SiguientePtr->siguiente;
            }
                SiguientePtr->siguiente = NuevoPtr;
                NuevoPtr->siguiente = NULL;
        }
    }
}

void Imprimir(NodoListaPtr Lista)
{
    if (vacia(Lista)) {
        printf("\nLa Lista est%c vac%ca.\n", 160, 161);
        system("PAUSE");
    }
    else {
        printf("\nElementos de la Lista:");

        while (Lista != NULL) {
            printf("%4d", Lista->info);
            Lista = Lista->siguiente;
        }
    }
}

void Intercambio(NodoListaPtr NodoA, NodoListaPtr NodoB)
{
    int temp = NodoA->info;
    NodoA->info = NodoB->info;
    NodoB->info = temp;
}

void OrdenBurbuja(NodoListaPtr Lista)
{
    int mezclado;

    NodoListaPtr PtrUno;
    NodoListaPtr PtrAux = NULL;

    if (vacia(Lista)) {
        printf("\nLa Lista est%c vac%ca.\n", 160, 161);
        system("PAUSE");
    }
    else {
        do
        {
            mezclado = 0;
            PtrUno = Lista;

            while (PtrUno->siguiente != PtrAux) {
                if (PtrUno->info > PtrUno->siguiente->info) {
                    Intercambio(PtrUno, PtrUno->siguiente);
                    mezclado++;
                }
                PtrUno = PtrUno->siguiente;
            }
            PtrAux = PtrUno;
        } while (mezclado);

    }
}