#include <stdio.h>
#include <iostream.h>
#include <conio.h>

struct NODO {
    int Dato;
    struct NODO *Sig;
    struct NODO *ant;
};

struct NODO *InicioLista=NULL, *Recorre=NULL, *Recorre2=NULL, *Aux=NULL, *finLista=NULL,*aux;

void InsertaNodo(int Elemento){
    Aux=new(struct NODO);
    Aux->Dato=Elemento;
    Aux->Sig=NULL;
    Aux->ant=NULL;

    if (InicioLista==NULL){
      InicioLista=Aux;
      finLista=Aux;
    }
    else{
          Recorre=InicioLista;
          while(Recorre->Sig!=NULL){
          Recorre=Recorre->Sig;
          }
          Recorre->Sig=Aux;
          Aux->ant=Recorre;
          finLista=Aux;
    }
}


void Ordenar_Listas(){
    Recorre=InicioLista;
    Recorre2=InicioLista;
     int conta=0;
      int conta2=0;
       int aux;

    while(Recorre!=NULL){  conta++;
        Recorre = Recorre->Sig;
    }

    Recorre = InicioLista;

    do{
        while(Recorre->Sig!=NULL){
            Recorre2=Recorre2->Sig;
            if(Recorre->Dato > Recorre2->Dato){
                aux = Recorre2->Dato;
                Recorre2->Dato = Recorre->Dato;
                Recorre->Dato = aux;
                Recorre = Recorre->Sig;
            }
            else{
                Recorre = Recorre->Sig;
            }

        }
    conta2++;
    Recorre = InicioLista;
    Recorre2 = InicioLista;
    }while(conta2!=conta);

}



void ImprimirLista(){
    Recorre=InicioLista;
    while(Recorre!=NULL){
        cout<<Recorre->Dato<<" ";
        Recorre=Recorre->Sig;
    }
    getch();
}

void busquedaElemento(int Elemento){
    Recorre=InicioLista;
    int posicion=1;
    int checa=0;

    while(Recorre!=NULL){
        if(Recorre->Dato==Elemento) checa=1;
        else{
            if(checa!=1)
                           posicion++;
        }
        Recorre=Recorre->Sig;
    }
    if(checa==1) cout<<"El elemento se encuentra  en la Posicion: "<<posicion;
    else cout<<"El Elemento no se ha  encontrado";
}

void main(){
    int opc;
    int Elemento;
    do{
         clrscr();
         cout<<"1) Insertar\n";
         cout<<"2) Imprimir Lista de nodos\n";
         cout<<"3) Buscar Elemento en la lista\n";
         cout<<"4) Salir\n";
         cout<<"Opciones: ";
         cin>>opc;
         if (opc==1){
            cout<<"Elemento: ";
            cin>>Elemento;
            InsertaNodo(Elemento);
         }
         else if (opc==2){
            cout<<"Elementos Ordenados...\n";
         Ordenar();
            ImprimirLista();
         getch();
         }
         else if (opc==3){
            cout<<"Elemento a buscar: \n";
            cin>>Elemento;
            busquedaElemento(Elemento);
            getch();
         }


    }while(opc!=4);
}