elhacker.net cabecera Bienvenido(a), Visitante. Por favor Ingresar o Registrarse
¿Perdiste tu email de activación?.

 

 


Tema destacado: Rompecabezas de Bitcoin, Medio millón USD en premios


+  Foro de elhacker.net
|-+  Programación
| |-+  Programación C/C++ (Moderadores: Eternal Idol, Littlehorse, K-YreX)
| | |-+  Insertar un elemento ordenadamente en una lista enlazada simple
0 Usuarios y 1 Visitante están viendo este tema.
Páginas: [1] Ir Abajo Respuesta Imprimir
Autor Tema: Insertar un elemento ordenadamente en una lista enlazada simple  (Leído 26,583 veces)
NathanD

Desconectado Desconectado

Mensajes: 48


Ver Perfil
Insertar un elemento ordenadamente en una lista enlazada simple
« en: 26 Abril 2013, 17:11 pm »

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
  1. LISTA *meterElementoOrdenado(int num, LISTA *lista)
  2. {
  3. LISTA *nodo_aux, *inicio;
  4. int cont = 1;
  5.  
  6. inicio = lista;
  7. nodo_aux = (LISTA*) malloc( sizeof(LISTA) );
  8.  
  9. if(nodo_aux == NULL)
  10. printf("\nNo hay sitio para mas elementos...\n");
  11.  
  12. if(lista == NULL)
  13. {
  14. nodo_aux->numero = num;
  15. nodo_aux->siguiente = NULL;
  16. return nodo_aux;
  17. }
  18.  
  19. else
  20. {
  21. do
  22. {
  23.          if(num < lista->numero)
  24.          {
  25.                                   nodo_aux->numero = num;
  26.                                   nodo_aux->siguiente = lista->siguiente;
  27.                                  lista->siguiente = nodo_aux;
  28.                                  cont = 0;
  29.           }
  30.           lista = lista->siguiente;
  31.  
  32. }while( (lista != NULL) && (cont != 0) );
  33.  
  34. nodo_aux = inicio;
  35. return nodo_aux;
  36. }
  37.  
  38. }

Gracias de antemano y saludos.


En línea

SARGE553413

Desconectado Desconectado

Mensajes: 176


Ver Perfil
Re: Insertar un elemento ordenadamente en una lista enlazada simple
« Respuesta #1 en: 26 Abril 2013, 17:30 pm »

Podrías explicar primero que error te da exactamente?


En línea

xiruko


Desconectado Desconectado

Mensajes: 438


Ver Perfil
Re: Insertar un elemento ordenadamente en una lista enlazada simple
« Respuesta #2 en: 26 Abril 2013, 19:18 pm »

Código
  1. if(num < lista->numero) {
  2.     nodo_aux->numero = num;
  3.     nodo_aux->siguiente = lista->siguiente;
  4.     lista->siguiente = nodo_aux;
  5.     cont = 0;
  6. }
  7. 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
  1. struct lista {
  2.     int num;
  3.     struct lista *anterior;
  4.     struct lista *siguiente;
  5. };

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

Código
  1. if(num < lista->numero) {
  2.     nodo_aux->numero = num;
  3.     nodo_aux->siguiente = lista; //enlazas con el nodo siguiente
  4.     nodo_aux->anterior=lista->anterior; //enlazas con el nodo anterior
  5.  
  6.     lista->anterior->siguiente=nodo_aux; //al nodo anterior al nodo creado, actualizas su 'siguiente' al nodo nuevo creado
  7.     lista->anterior=nodo_aux; //al nodo posterior al nodo creado, actualizas su 'anterior' al nodo nuevo creado
  8.  
  9.     cont = 0;
  10. }
  11. 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
  1. nodo_aux = inicio;
  2. 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
  1. 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
  1. LISTA *nodo_aux=NULL, *inicio=NULL, *anterior=NULL;
  2. int cont = 1;
  3.  
  4. //...
  5.  
  6. if(num < lista->numero) {
  7.     nodo_aux->numero = num;
  8.     nodo_aux->siguiente = lista;
  9.  
  10.     anterior->siguiente = nodo_aux;
  11.  
  12.     cont = 0;
  13. }
  14. anterior=lista;
  15. 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!
« Última modificación: 26 Abril 2013, 19:30 pm por xiruko » En línea

rir3760


Desconectado Desconectado

Mensajes: 1.639


Ver Perfil
Re: Insertar un elemento ordenadamente en una lista enlazada simple
« Respuesta #3 en: 26 Abril 2013, 20:47 pm »

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
  1. #include <stdio.h>
  2. #include <stdlib.h>
  3. #include <time.h>
  4.  
  5. struct lista {
  6.   int numero;
  7.   struct lista *siguiente;
  8. };
  9. typedef struct lista LISTA;
  10.  
  11. LISTA *meterElementoOrdenado(int num, LISTA *lista);
  12.  
  13. int main(void)
  14. {
  15.   LISTA *primero = NULL;
  16.   LISTA *p;
  17.   LISTA *siguiente;
  18.   int i;
  19.  
  20.   srand((unsigned) time(NULL));
  21.  
  22.   for (i = 10; i > 0; i--)
  23.      primero = meterElementoOrdenado(rand() % 10, primero);
  24.  
  25.   for (p = primero; p != NULL; p = p->siguiente)
  26.      printf("%2d", p->numero);
  27.   putchar('\n');
  28.  
  29.   for (p = primero; p != NULL; p = siguiente){
  30.      siguiente = p->siguiente;
  31.      free(p);
  32.   }
  33.  
  34.   return EXIT_SUCCESS;
  35. }
  36.  
  37. LISTA *meterElementoOrdenado(int num, LISTA *lista)
  38. {
  39.   LISTA *nuevo = malloc(sizeof *nuevo);
  40.  
  41.   if (nuevo == NULL){
  42.      fputs("Error con malloc!", stderr);
  43.   }else {
  44.      nuevo->numero = num;
  45.  
  46.      if (lista == NULL || lista->numero > num){
  47.         nuevo->siguiente = lista;
  48.         lista = nuevo;
  49.      }else {
  50.         LISTA *p = lista;
  51.  
  52.         while (p->siguiente != NULL && p->siguiente->numero <= num)
  53.            p = p->siguiente;
  54.  
  55.         nuevo->siguiente = p->siguiente;
  56.         p->siguiente = nuevo;
  57.      }
  58.   }
  59.  
  60.   return lista;
  61. }


Una forma mas corta y que evita los casos especiales pero a cambio es mas complicada e ineficiente es:
Código
  1. LISTA *meterElementoOrdenado(int num, LISTA *lista)
  2. {
  3.   LISTA *nuevo = malloc(sizeof *nuevo);
  4.  
  5.   if (nuevo == NULL){
  6.      fputs("Error con malloc!", stderr);
  7.   }else {
  8.      LISTA **p = &lista;
  9.      nuevo->numero = num;
  10.  
  11.      while (*p != NULL && (*p)->numero <= num)
  12.         p = &(*p)->siguiente;
  13.  
  14.      nuevo->siguiente = *p;
  15.      *p = nuevo;
  16.   }
  17.  
  18.   return lista;
  19. }

Un saludo
En línea

C retains the basic philosophy that programmers know what they are doing; it only requires that they state their intentions explicitly.
--
Kernighan & Ritchie, The C programming language
NathanD

Desconectado Desconectado

Mensajes: 48


Ver Perfil
Re: Insertar un elemento ordenadamente en una lista enlazada simple
« Respuesta #4 en: 27 Abril 2013, 14:25 pm »

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

Páginas: [1] Ir Arriba Respuesta Imprimir 

Ir a:  

Mensajes similares
Asunto Iniciado por Respuestas Vistas Último mensaje
Duda lista simple enlazada C
Programación C/C++
netca 3 3,836 Último mensaje 16 Agosto 2012, 00:06 am
por twins
insertar datos nom apell rut en lista enlazada
Java
Futuro_Ingeniero 0 2,378 Último mensaje 15 Abril 2013, 23:57 pm
por Futuro_Ingeniero
No se añade elemento nuevo en una lista enlazada
Programación C/C++
NathanD 2 2,192 Último mensaje 23 Abril 2013, 10:05 am
por NathanD
problema con funcion insertar de una lista enlazada
Programación C/C++
roger13 0 1,947 Último mensaje 20 Octubre 2013, 01:44 am
por roger13
borrar elemento de la lista enlazada simple
Programación C/C++
d91 2 3,272 Último mensaje 9 Junio 2014, 13:44 pm
por d91
WAP2 - Aviso Legal - Powered by SMF 1.1.21 | SMF © 2006-2008, Simple Machines