Foro de elhacker.net

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):

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.

Podrías explicar primero que error te da exactamente?

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:

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

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

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.

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:

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:

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!

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:

#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:

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

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