Problemas listas

[Cas980]

Estoy trabajando con listas dobles circulares, espero puedan ayudarme.
Lo que intento hacer es que al ir agregando se vayan ordenando los datos
Pero tengo problemas con el ultimo caso, como hago la comparacion y como voy avanzando si lo tengo que hacer de forma recursiva??

Código (c) [Seleccionar] Expandir


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

#define SALIR 0

typedef struct nodo
{
   int dato;
   struct nodo *sig;
   struct nodo *ant;
}NODO;

typedef struct punteros
{
   struct nodo *inicio;
   struct nodo *fin;
}LISTA;

int agregar_ordenado(LISTA *aux, int dato)
{
   if(aux->inicio==NULL)//LISTA VACIA
   {
       NODO *nuevo=(NODO *)malloc(sizeof(NODO));
       nuevo->dato=dato;
       nuevo->ant=nuevo;
       nuevo->sig=nuevo;
       aux->fin=nuevo;
       aux->inicio=nuevo;
       return 1;
   }
   if(dato > aux->inicio->dato)//ES MAYOR AL INICIO
   {
       NODO *nuevo=(NODO *)malloc(sizeof(NODO));
       nuevo->dato=dato;
       nuevo->sig=aux->inicio;
       aux->inicio->ant=nuevo;
       aux->inicio=nuevo;
       nuevo->ant=aux->fin;
       aux->fin->sig=aux->inicio;
       return 1;
   }
   if(dato < aux->fin->dato)//ES MENOR AL FIN
   {
       NODO *nuevo=(NODO *)malloc(sizeof(NODO));
       nuevo->dato=dato;
       nuevo->ant=aux->fin;in        aux->fin->sig=nuevo;
       nuevo->sig=aux->inicio;
       aux->inicio->ant=nuevo;
       return 1;
   }
   if()//EN MEDIO DE LA LISTA
   {

   }

   agregar_ordenado(aux->inicio->sig)

}



void imprimir(LISTA *aux)//DEL ULTIMO AREGADO AL PRIMERO
{
NODO *actual;
actual = aux->inicio;
while(actual != aux->fin)
   {
printf(" %i ",actual->dato);
actual = actual->sig;
}
printf(" %i ",actual->dato);
printf("\n");
}


int main()
{
   NODO *lista =NULL;
   LISTA *aux=(LISTA *)malloc(sizeof(LISTA));
   int op,dat,num;

   aux->inicio = NULL;
   aux->fin = NULL;
   do
   {
       printf("\n 1.Agregar elemento");
       printf("\n 2.Imprimir lista");
       printf("\n 0.salir");
       scanf(" %d",&op);
       switch(op)
       {
       case 0:
           exit(0);
       case 1:
           printf("\n Ingrese dato: ");
           scanf(" %d",&dat);
           agregar_ordenado(aux,dat);
           break;
       case 2:
           imprimir(aux);
           break;
       }


   }while(op!=SALIR);
   return 0;
}


   

[eferion]

Una lista doblemente enlazada se caracteriza porque puedes recorrerla hacia adelante o hacia atrás indiferentemente.

La norma general para añadir un elemento es, una vez localizada la posición en la que se ha de insertar, realizar las siguientes operaciones:

1. nuevo_nodo->puntero_anterior = nodo_anterior;
2. nuevo_nodo->puntero_siguiente = nodo_siguiente;
3. nodo_anterior->puntero_siguiente = nuevo_nodo;
4. nodo_siguiente->puntero_anterior = nuevo_nodo;

Esta norma general tiene 2 excepciones:

* Si el nodo va en primer lugar, se omite el paso 3 y el 1 apunta a null.
* Si el nodo va al final, se omite el paso 4 y el 2 apunta a null.

Si resulta que la lista está vacía, se dan a la vez las dos circunstancias anteriores... basta con aplicarlas.

En tu caso concreto, hablando sobre el "cuarto caso", lo que tienes que hacer es seguir los 4 puntos que te he indicado. No tiene pérdida.

Por cierto, si la lista va a ser SIEMPRE ordenada, agregar_principio y agregar_ordenado colisionan entre sí, deberías eliminar una de las dos funciones para evitar código duplicado.

Es más, si tu idea es recorrer la lista para ubicar un elemento, no puedes usar un puntero a tipo "LISTA"... tienes que usar uno a tipo "NODO", para poder recorrer de forma recursiva la lista:

Código (c) [Seleccionar] Expandir


void agregar_elemento( LISTA* lista, NODO* nodo_ant, int dato )
{
  if (lista->inicio == NULL)
  {
    // Este caso se da cuando la lista esta vacia
    NODO *nuevo=(NODO *)calloc(1, sizeof(NODO));
    nuevo->dato = dato;
    lista->inicio = nuevo;
    lista->fin = nuevo;
  }
  else if ( nodo_ant->dato < dato )
  {
    // el nuevo nodo va "antes" que nodo_ant
    NODO *nuevo=(NODO *)malloc(sizeof(NODO));
    nuevo->dato = dato;
    nuevo->ant = nodo_ant->ant;
    nuevo->sig = nodo_ant;
    nodo_ant->sig = nuevo;

    if ( nodo_ant->ant )
      nodo_ant->ant->sig = nuevo;
    else
      lista->inicio = nuevo;
  }
  else if ( nodo_ant->dato > dato )
  {
    // El nuevo nodo va despues que "nodo_ant"
    // Hay que comprobar si hemos llegado al final de la lista

    if ( nodo_ant->sig )
      agregar_elemento( nodo_ant->sig );
    else
    {
      // nodo_ant es el ultimo elemento de la lista, el nuevo tiene que ir despues
      NODO *nuevo=(NODO *)calloc(1, sizeof(NODO));
      nuevo->dato = dato;
      nuevo->ant = nodo_ant;
      nodo_ant->sig = nuevo;
      lista->fin = nuevo;
    }
  }
}

Incluso se podría optimizar más el código usando dos funciones ( una para localizar la ubicación del nuevo nodo y otra para insertarlo ), pero eso ya te lo dejo a ti.