/**************************/
/* Funciones de Listas simplemente enlazadas

   	struct Nodo *crea_nodo( TIPO_DATO info )
	struct Nodo *recorre_al_final( struct Nodo *lista )
	struct Nodo *Inserta_Inicio( TIPO_DATO info, struct Nodo *lista )
	void Inserta_Final( TIPO_DATO info, struct Nodo *(*lista) )
	int lista_esta_vacia(struct Nodo *NODO)
	int numero_elementos(struct Nodo *NODO)
	void muestra_lista(struct Nodo *NODO)
	
 */
#include <stdio.h>
#include <stdlib.h>
#include <string.h>
#include <conio.h>

typedef int TIPO_DATO;

struct Nodo
{
        TIPO_DATO info;  
        struct Nodo *sig;
};


struct Nodo *crea_nodo( TIPO_DATO info )
{
       struct Nodo *aux;
       
       aux = (struct Nodo *) malloc( sizeof(struct Nodo) );    
       aux->info = info;
       aux->sig = NULL; // apuntaba a NULL
       
       return aux;   
}

struct Nodo *recorre_al_final( struct Nodo *lista )
{
       if ( lista->sig == NULL)
            return lista;
       else
            return recorre_al_final( lista->sig );          
}

struct Nodo *Inserta_Inicio( TIPO_DATO info, struct Nodo *lista )
{
       struct Nodo *aux;
       
       aux = crea_nodo( info );
       aux->sig = lista;
       return aux; 
}

int lista_esta_vacia(struct Nodo *NODO)
{
    if (NODO == NULL)
       return 1; // La lista est? vac?a    
    else
       return 0; // la lista no est? vac?a
}

void Inserta_Inicio2( TIPO_DATO info, struct Nodo *(*lista) )
{
      struct Nodo *aux;
      
      aux = crea_nodo( info );
      aux->sig = (*lista);    
      (*lista) = aux;
}

void Inserta_Final( TIPO_DATO info, struct Nodo *(*lista) )
{
     struct Nodo *aux;
     struct Nodo *temp;
       
     aux = crea_nodo( info );
     if( lista_esta_vacia( *lista ) )
         Inserta_Inicio2( info, lista );
     else
     {
         temp = recorre_al_final( *lista );
         temp->sig = aux;
     }
}

void Inserta_elemento_por_posicion( TIPO_DATO info, int pos, struct Nodo *(*lista) )
{
     int i=0;
     struct Nodo *temp;
     struct Nodo *nuevo;
     
     if( pos == 1 )
         Inserta_Inicio2( info, lista );
     else
     {
         temp = *lista; // a temp, le damos la dirección inicial de la lista
         while ( (temp->sig != NULL) && i<pos-2 )
         {
               temp = temp->sig;
               i++;      
         }
         
         nuevo = crea_nodo( info ); // Creamos un nuevo nodo

         nuevo->sig = temp->sig; // hacemos que el nuevo nodo apunte a lo que actualmente apunta temp
         temp->sig = nuevo; // y temp debe apuntar ahora al nuevo Nodo. Esto hace que se inserte
                        // el nuevo dato "info" en la posición solicitada
     }
     
}

struct Nodo *devuelve_ADDR_anterior( struct Nodo *lista, TIPO_DATO info )
{
       struct Nodo *ant;
       struct Nodo *temp;     
       int i=1;
     
       temp = lista;
       ant = lista;
     
       do
       {
           if( temp-> info == info )
              return ant;
           temp = temp->sig;
           if (i>1) 
              ant = ant->sig;
           i++;
       }while( temp->sig != NULL );    
       
       return NULL; 
}

void Elimina_Nodo( struct Nodo *lista, int pos, TIPO_DATO info )
{
  struct Nodo *pact;
  struct Nodo *pant;

  pact = lista->sig; 
  pant = lista;
  if( pos < 1 || pos > numero_elementos)
      printf("Fuera de rango");
  else
      if( pos==1)
      {
          pant = pact; 
          pact = pact->sig; 
      }
      else
      {
          for(int i=2; i<=pos; i++)
          {
           if( i==pos)
           {
            Nodo<T> *aux = temp1;
            temp->sgte = temp1->sgte;
            delete aux;
            num_nodos--;
      }   
          
         
  while((pact = NULL) &&  
      (pact->info != info)) 
  { 
   pant = pact; 
   pact = pact->sig; 
  }
       
       
  if(pact != NULL) 
  { 
  pant->sig = pact->sig; 
  delete(pact); 
  }
}
/////////
//eliminar por posicion del nodo

void Lista<T>::del_pos(int pos)
{
  Nodo<T> *temp = head;
  Nodo<T> *temp1 = temp->sgte;

  if(pos < 1 || pos > num_nodos){
    cout << "Fuera de rango " << endl;
  } else if(pos==1){
    head = temp->sgte;
  } else{
    for(int i=2;i<=pos;i++){
      if(i==pos){
        Nodo<T> *aux = temp1;
        temp->sgte = temp1->sgte;
        delete aux;
        num_nodos--;
      }
      temp = temp->sgte;
      temp1 = temp1->sgte;
    }
  }
}
///////
struct Nodo *buscar( struct Nodo *NODO, TIPO_DATO info )
{
       struct Nodo *aux;
       
       for( aux = NODO; aux != NULL; aux = aux->sig )
            if( aux->info == info ) 
                return aux; //Lo encontré y retorno su dirección.
       
       return NULL; // nunca lo encontré. Retorno NULL       
}

int numero_elementos(struct Nodo *NODO)
{
    if ( lista_esta_vacia (NODO) )
       return 0;
    else if ( NODO->sig == NULL)
              return 1;
         else
              return 1 + numero_elementos( NODO->sig );
}

void muestra_lista(struct Nodo *NODO)
{
     
     printf("%d",NODO->info);  
     
     if (NODO->sig == NULL)
        printf("->NULL");
     else
     {
         printf("->");
         muestra_lista( NODO->sig );
     }
}

int main()
{
    struct Nodo *lista = NULL;
    struct Nodo *ptrNodo;
    TIPO_DATO dato;
    int posi;
    printf("\n\n");


    Inserta_Final(1,&lista);
    Inserta_Final(3,&lista);
    Inserta_Final(5,&lista);
    Inserta_Final(8,&lista);
    Inserta_Final(7,&lista);
    Inserta_Final(9,&lista);
    Inserta_Final(0,&lista);
    Inserta_Final(0,&lista);
    Inserta_Final(1,&lista);
    Inserta_Final(1,&lista);
    Inserta_Final(2,&lista);
   // 13587900112 Dato inicial
    
    if( !lista_esta_vacia( lista ) )
        muestra_lista( lista );
    printf("\nLa cantidad de elementos de la lista es: %d\n",numero_elementos(lista) );
    
    //Elimina elemento por dato
    printf("Elimina un elemento por dato : "); 
    scanf("%d",&dato);//guardamos el elemento
    Elimina_Nodo( lista, dato);
    printf("\nla nueva lista es: \n");
    muestra_lista( lista );
    printf("\nLa cantidad de elementos de la lista es: %d\n",numero_elementos(lista) );
    
    //Ingresar datos por posicion
    printf("Ingresar el dato a insertar: "); scanf("%d", &dato);
    printf("Ingresar la posici%cn: ",162); scanf("%d", &posi);
    
    // validamos la inserción
    if ( posi > numero_elementos(lista) || posi < 1 )
       printf("No puedo Insertar el elemento [%d] en la posici%cn %d",dato,162,posi);
    else
    {
       Inserta_elemento_por_posicion( dato, posi, &lista );
       printf("\nla nueva lista es: \n");
       if( !lista_esta_vacia( lista ) )
           muestra_lista( lista );
       printf("\nLa cantidad de elementos de la lista es: %d\n",numero_elementos(lista) );
    }
    
   /* // Buscamos un elemento en la lista
    printf("\n\nIngresar el dato del elemento a buscar: "); scanf("%d",&dato);
    
    if( ( ptrNodo = buscar( lista, dato ) ) != NULL )
    {
        printf("Elemento encontrado...\n");
        printf("[%p]:[%d]", ptrNodo, ptrNodo->info );
    }
    else
        printf("No encontr%c el elemento...",130);
    
    printf("\nIngresar el elemento para mostrar el anterior a el: ");
    scanf("%d",&dato);
    
    ptrNodo = devuelve_ADDR_anterior( lista, dato );
    
    if ( ptrNodo == NULL )
       printf("No encontr%c el elemento...",130);
    else
       printf("Ok... El elemento anterior es: %d", ptrNodo->info);
    */
    //Elimina elemento por dato
    printf("Elimina un elemento por dato : "); 
    scanf("%d",&dato);
    Elimina_Nodo( lista, dato);
    printf("\nla nueva lista es: \n");
    if( !lista_esta_vacia( lista ) )
           muestra_lista( lista );
    printf("\nLa cantidad de elementos de la lista es: %d\n",numero_elementos(lista) );

    getch();
    return 0;    
}