Insertar un elemento ordenadamente en una lista enlazada simple

[NathanD]

Hola, tengo que hacer una lista enlazada simple en la que los elementos que se insertan, sea de una forma ordenada (de menor a mayor). He hecho la función y no consigo que funcione como debe, no sé cuál es el fallo y cómo debo corregirlo...

Os dejo la función (creo que no hace falta poner todo el programa, pero si así fuera decídmelo y lo pongo (igual me he líado con el nombre de alguna variable en la traducción jeje):

Código (c) [Seleccionar] Expandir

LISTA *meterElementoOrdenado(int num, LISTA *lista)
{
LISTA *nodo_aux, *inicio;
int cont = 1;

inicio = lista;
nodo_aux = (LISTA*) malloc( sizeof(LISTA) );

if(nodo_aux == NULL)
printf("\nNo hay sitio para mas elementos...\n");

if(lista == NULL)
{
nodo_aux->numero = num;
nodo_aux->siguiente = NULL;
return nodo_aux;
}

else
{
do
{
          if(num < lista->numero)
          {
                                   nodo_aux->numero = num;
                                   nodo_aux->siguiente = lista->siguiente;
                                  lista->siguiente = nodo_aux;
                                  cont = 0;
           }
           lista = lista->siguiente;

}while( (lista != NULL) && (cont != 0) );

nodo_aux = inicio;
return nodo_aux;
}

}

Gracias de antemano y saludos.

[SARGE553413]

Podrías explicar primero que error te da exactamente?

[xiruko]

Código (c) [Seleccionar] Expandir

if(num < lista->numero) {
    nodo_aux->numero = num;
    nodo_aux->siguiente = lista->siguiente;
    lista->siguiente = nodo_aux;
    cont = 0;
}
lista = lista->siguiente;

si tienes que ordenar los numeros de menor a mayor, entonces si entras en este if tendras que poner el numero antes del nodo de la lista en el que te encuentres. esto se complica puesto que seguro mas de una vez necesitaras insertar un nodo en medio de la lista, y diria que para hacerlo necesitas una lista doblemente enlazada, con un puntero que apunte al nodo anterior y otro al siguiente:

Código (c) [Seleccionar] Expandir

struct lista {
    int num;
    struct lista *anterior;
    struct lista *siguiente;
};

de esta manera, en el if deberias hacer algo asi:

Código (c) [Seleccionar] Expandir

if(num < lista->numero) {
    nodo_aux->numero = num;
    nodo_aux->siguiente = lista; //enlazas con el nodo siguiente
    nodo_aux->anterior=lista->anterior; //enlazas con el nodo anterior

    lista->anterior->siguiente=nodo_aux; //al nodo anterior al nodo creado, actualizas su 'siguiente' al nodo nuevo creado
    lista->anterior=nodo_aux; //al nodo posterior al nodo creado, actualizas su 'anterior' al nodo nuevo creado

    cont = 0;
}
lista = lista->siguiente;

claro que si lo haces asi, entonces deberas modificar el resto de codigo que tengas teniendo en cuenta el nuevo puntero al nodo anterior. tampoco he tenido en cuenta el comprobar si colocas el numero al principio de la lista, por lo que entonces tienes que hacer que 'anterior' apunte a NULL, igual que si es al final tienes que hacerlo pero con 'siguiente', pero espero que la idea te sirva.

Código (c) [Seleccionar] Expandir

nodo_aux = inicio;
return nodo_aux;

luego esto de aqui no tiene nada que ver con el error, pero no entiendo por que no haces directamente:

Código (c) [Seleccionar] Expandir

return inicio;

saludos!

EDITO: pensandolo mejor, otra opcion seria que declararas otro puntero auxiliar que apuntara al nodo anterior en el que te encuentres. de esta manera:

Código (c) [Seleccionar] Expandir

LISTA *nodo_aux=NULL, *inicio=NULL, *anterior=NULL;
int cont = 1;

//...

if(num < lista->numero) {
    nodo_aux->numero = num;
    nodo_aux->siguiente = lista;

    anterior->siguiente = nodo_aux;

    cont = 0;
}
anterior=lista;
lista = lista->siguiente;

aunque aqui tampoco tengo en cuenta los casos especiales como insertar al principio o al final. pero bueno espero que te sirva, un saludo!

[rir3760]

tengo que hacer una lista enlazada simple en la que los elementos que se insertan, sea de una forma ordenada (de menor a mayor).

La forma mas sencilla es separando los tres casos:
A) Lista vacía.
B) Inserción como primer elemento.
C) Inserción después del primero.

Un programa de ejemplo basado en el tuyo:

Código (c) [Seleccionar] Expandir

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

struct lista {
   int numero;
   struct lista *siguiente;
};
typedef struct lista LISTA;

LISTA *meterElementoOrdenado(int num, LISTA *lista);

int main(void)
{
   LISTA *primero = NULL;
   LISTA *p;
   LISTA *siguiente;
   int i;
   
   srand((unsigned) time(NULL));
   
   for (i = 10; i > 0; i--)
      primero = meterElementoOrdenado(rand() % 10, primero);
   
   for (p = primero; p != NULL; p = p->siguiente)
      printf("%2d", p->numero);
   putchar('\n');
   
   for (p = primero; p != NULL; p = siguiente){
      siguiente = p->siguiente;
      free(p);
   }
   
   return EXIT_SUCCESS;
}

LISTA *meterElementoOrdenado(int num, LISTA *lista)
{
   LISTA *nuevo = malloc(sizeof *nuevo);
   
   if (nuevo == NULL){
      fputs("Error con malloc!", stderr);
   }else {
      nuevo->numero = num;
     
      if (lista == NULL || lista->numero > num){
         nuevo->siguiente = lista;
         lista = nuevo;
      }else {
         LISTA *p = lista;
         
         while (p->siguiente != NULL && p->siguiente->numero <= num)
            p = p->siguiente;
         
         nuevo->siguiente = p->siguiente;
         p->siguiente = nuevo;
      }
   }
   
   return lista;
}


Una forma mas corta y que evita los casos especiales pero a cambio es mas complicada e ineficiente es:

Código (c) [Seleccionar] Expandir

LISTA *meterElementoOrdenado(int num, LISTA *lista)
{
   LISTA *nuevo = malloc(sizeof *nuevo);
   
   if (nuevo == NULL){
      fputs("Error con malloc!", stderr);
   }else {
      LISTA **p = &lista;
      nuevo->numero = num;
     
      while (*p != NULL && (*p)->numero <= num)
         p = &(*p)->siguiente;
     
      nuevo->siguiente = *p;
      *p = nuevo;
   }
   
   return lista;
}

Un saludo

[NathanD]

Muchísimas gracias a todos, ya lo he conseguido con vuestra ayuda. Gracias!!