Ordenar lista simplemente enlazada en lenguaje C método burbuja ordenamiento

[Pino06-01-2016]

Hola, a todos. Les voy a pedir un poco de colaboración para aprender a ordenar una lista simplemente enlazada, lo voy a implementar utilizando el método de la burbuja pero desconozco cómo hacerlo, vi algunos Ejs. pero no me queda claro si se hace como ordenar un vector o como leí que se debe volcar los datos a un vector, ordenarlos y luego crear una lista nueva con los datos ordenados.

Les dejo el código de lo que llevo hasta el momento. -

Código: [Seleccionar]

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

 
struct _agenda{
int dato;
struct _agenda *siguiente;
};
 
struct _agenda *primero, *ultimo;
 
void mostrar_menu();
void agregar_elemento( size_t *cont );
void mostrar_lista( size_t cont);
void ordenar_lista( size_t cont);
 
int main(void){
char opcion, ch;
size_t cont = 0;
primero = (struct _agenda *) NULL;
ultimo = (struct _agenda *) NULL;

do{
mostrar_menu();
opcion = getchar();
while((ch = getchar()) != EOF && ch != '\n');
switch ( opcion ){
case '1': agregar_elemento( &cont );
break;
case '2':  printf("No disponible todavía!\n");
break;
case '3': mostrar_lista( cont );
break;
case '4': ordenar_lista( cont );
break;
case '5': exit( 1 );
default: printf( "Opción no válida\n" );
printf( "\n Pulse una tecla para continuar..." ); getchar();
break;
}
} while (opcion!='5');   
 
return 0;
}
 
 
void mostrar_menu(){
system( "clear" );
printf( "\n\n ===== Menu =====" );
printf( "\n\n 1 - Agregar elemento" );
printf( "\n 2 - Borrar elemento" );
printf( "\n 3 - Mostrar elementos" );
printf( "\n 4 - Ordenar elementos" );
printf( "\n 5 - Salir" );
 
  printf("\n\n Escoge una opcion......: ");
}
 
 
/* Con esta función añadimos un elemento al final de la lista */
void agregar_elemento( size_t *cont ){
struct _agenda *nuevo;
int ch;
 
/* reservamos memoria para el nuevo elemento */
nuevo = (struct _agenda *) malloc (sizeof(struct _agenda));
if( nuevo == NULL){
printf(" \n No hay memoria disponible");
}
printf( "\n ===== Nuevo elemento =====" );
printf( "\n Dato.....:" );
scanf( "%d", &nuevo->dato );
while ((ch = getchar()) != EOF && ch != '\n');
 
/* el campo siguiente va a ser NULL por ser el último elemento*/
nuevo->siguiente = NULL;
 
/* ahora metemos el nuevo elemento en la lista. lo situamos al final de la lista */
/* comprobamos si la lista está vacía. si primero==NULL es que no
         hay ningún elemento en la lista. también vale ultimo==NULL */
if( primero == NULL ){
printf( "\n Primer elemento" );
primero = nuevo;
ultimo  = nuevo;
}else{
/* el que hasta ahora era el último tiene que apuntar al nuevo */
ultimo->siguiente = nuevo;
/* hacemos que el nuevo sea ahora el último */
ultimo = nuevo;
}
*cont += 1;
}
 
 
void mostrar_lista( size_t cont ){
struct _agenda *auxiliar; /* lo usamos para recorrer la lista */
int i=0;
 
auxiliar = primero;
printf( "\n Mostrando la lista completa (total %lu):\n ", cont);
while( auxiliar != NULL ){
printf( "\n Dato....: %d", auxiliar->dato);
auxiliar = auxiliar->siguiente;
i++;
}
if( i==0 ){
printf( "\n La lista esta vacia!!\n" );
}
printf( "\n Pulse una tecla para continuar..." ); getchar();
}

void ordenar_lista( size_t cont){
printf( "\n No desarrollado..." ); getchar();
}

Saludos.
Daniel

[Ogramar]

Buenas, desde mi punto de vista no hace falta volcar los datos ni crear nuevos arrays o listas. El procedimiento de la burbuja se basaría en sustituir elementos por pares intercambiando su posición. Por tanto lo que sería necesario es guardar el elemento que va a ser sustituido en el intercambio como elemento temporal. Una vez almacenado el elemento que va a ser sustituido, se sustituye por el elemento que ha resultado menor. Tras esto la posición intercambiada será ocupada por el elemento temporal. Hay distintas variantes del algoritmo de la burbuja.

El ejemplo clásico, ordenando de menor a mayor:

Primera vuelta:
( 9 6 5 8 2 1 ) →  ( 6 9 5 8 2 1 ), el algoritmo compara los primeros dos elementos y los cambia porque 9 > 6
( 6 9 5 8 2 1 ) →  ( 6 5 9 8 2 1 )
( 6 5 9 8 2 1 ) →  ( 6 5 8 9 2 1 )
( 6 5 8 9 2 1 ) →  ( 6 5 8 2 9 1 )
( 6 5 8 2 9 1 ) →  ( 6 5 8 2 1 9 )

Segunda vuelta:
( 6 5 8 2 1 9 ) →  ( 5 6 8 2 1 9 )
( 5 6 8 2 1 9 ) →  ( 5 6 8 2 1 9 ), como estos elementos ya están en orden, el algoritmo no hace cambios.
( 5 6 8 2 1 9 ) →  ( 5 6 2 8 1 9 )
( 5 6 2 8 1 9 ) →  ( 5 6 2 1 8 9 )
( 5 6 2 1 8 9 ) →  ( 5 6 2 1 8 9 )

Tercera vuelta (aquí se sigue comparando por pares, ya no he marcado en color los pares pero se sigue igual por pares):
( 5 6 2 1 8 9 ) →  ( 5 6 2 1 8 9 )
( 5 6 2 1 8 9 ) →  ( 5 2 6 1 8 9 )
( 5 2 6 1 8 9 ) →  ( 5 2 1 6 8 9 )
( 5 2 1 6 8 9 ) →  ( 5 2 1 6 8 9 )
( 5 2 1 6 8 9 ) →  ( 5 2 1 6 8 9 )

Cuarta vuelta:
( 5 2 1 6 8 9 ) →  ( 2 5 1 6 8 9 )
( 2 5 1 6 8 9 ) →  ( 2 1 5 6 8 9 )
( 2 1 5 6 8 9 ) →  ( 2 1 5 6 8 9 )
( 2 1 5 6 8 9 ) →  ( 2 1 5 6 8 9 )
( 2 1 5 6 8 9 ) →  ( 2 1 5 6 8 9 )

Quinta vuelta:
( 2 1 5 6 8 9 ) →  ( 1 2 5 6 8 9 )
( 1 2 5 6 8 9 ) →  ( 1 2 5 6 8 9 )
( 1 2 5 6 8 9 ) →  ( 1 2 5 6 8 9 )
( 1 2 5 6 8 9 ) →  ( 1 2 5 6 8 9 )
( 1 2 5 6 8 9 ) →  ( 1 2 5 6 8 9 )

En resumen creo que la idea debería ser mantener una única lista donde vas realizando comparaciones a pares e intercambiando cuando procede. La ordenación termina cuando se cumpla algún criterio, por ejemplo haber comprobado todos los pares y no haberse producido ningún intercambio

Salu2

[Pino06-01-2016]

Hola, Ogramar.
Gracias por tu tiempo, te dejo el código para que si lo deseas me ayudes con un segmentation fault, si pongo lo mismo dentro de main funciona todo a la perfección pero si lo hago como en este caso desde una función me da el error. -

Código: [Seleccionar]

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

struct nodo{
int dato;
struct nodo *siguiente;
};

struct lista{
struct nodo *primero;
struct nodo *ultimo;
};

struct lista *ingresos( struct lista *L );
struct lista *agregar( struct lista *L, int dato );
struct nodo *crear( int dato );
void ordenar(struct lista *L);
void mostrar(struct lista *L);


int main( void ){
struct lista *Lista = NULL;

ingresos( Lista );
ordenar( Lista );
mostrar( Lista );

free(Lista);
return 0;
}

struct lista *ingresos( struct lista *L ){
int i;

for( i=0; i<7; i++ ){
printf( "\n %d", i );
L = agregar( L, i );
}

return L;
}


struct lista *agregar( struct lista *L, int dato ){
if( L != NULL ){
struct nodo *e = crear( dato );
L->ultimo->siguiente = e;
L->ultimo = e;

return L;
}else{
struct nodo *e = crear( dato );
struct lista *l = calloc( sizeof( struct lista ), 1 );
l->primero = e;
l->ultimo = e;

return l;
}
}

struct nodo *crear( int dato ){
struct nodo *e = calloc( sizeof( struct nodo), 1 );
e->dato = dato;
e->siguiente = NULL;

return e;
}

void ordenar(struct lista *L){
struct nodo *pivote = NULL,*actual = NULL;
int tmp;
if(L != NULL){
pivote = L->primero;
while(pivote != L->ultimo){
actual = pivote->siguiente;
while(actual != NULL){
if(pivote->dato > actual->dato){
tmp = pivote->dato;
pivote->dato = actual->dato;
actual->dato = tmp;
}
actual = actual->siguiente;
    }
pivote = pivote->siguiente;
    }

}
    else{
    printf("Error lista no inicializada");
    }
}

void mostrar(struct lista *L){
struct nodo *auxiliar;
int i=0;
auxiliar = L->primero;

    printf("\n\n Mostrando lista ordenada:\n");

while (auxiliar!=NULL) {
printf( "\n %d", auxiliar->dato);
auxiliar = auxiliar->siguiente;
i++;
}
if (i==0) printf( "\nLa lista está vacía!!\n" );
}

saludos.

[Ogramar]

Buenas, sin entrar a analizar otras cuestiones, a mí me está saltando un error en esta línea:

auxiliar = L->primero;

No veo claro este fragmento:

struct lista{
   struct nodo *primero;
   struct nodo *ultimo;
};

Normalmente una lista se define a partir de un puntero que enlaza con otro, sin necesidad de definir una estructura lista en sí, como en el siguiente ejemplo:

Código: [Seleccionar]

#include <stdio.h>

 struct _agenda {
        char nombre[20];
        char telefono[12];
        struct _agenda *siguiente;
        };

 struct _agenda *primero, *ultimo;

 void mostrar_menu() {
      printf("\n\nMenú:\n=====\n\n");
      printf("1.- Annadir elementos\n");
      printf("2.- Borrar elementos\n");
      printf("3.- Mostrar lista\n");
      printf("4.- Salir\n\n");
      printf("Escoge una opcion: ");fflush(stdout);
 }

 /* Con esta función añadimos un elemento al final de la lista */
 void anadir_elemento() {
      struct _agenda *nuevo;

      /* reservamos memoria para el nuevo elemento */
      nuevo = (struct _agenda *) malloc (sizeof(struct _agenda));
      if (nuevo==NULL) printf( "No hay memoria disponible!\n");

      printf("\nNuevo elemento:\n");
      printf("Nombre: "); //fflush(stdout);
      gets(nuevo->nombre);
      printf("Telefono: "); fflush(stdout);
      gets(nuevo->telefono);

      /* el campo siguiente va a ser NULL por ser el último elemento
         de la lista */
      nuevo->siguiente = NULL;

      /* ahora metemos el nuevo elemento en la lista. lo situamos
         al final de la lista */
      /* comprobamos si la lista está vacía. si primero==NULL es que no
         hay ningún elemento en la lista. también vale ultimo==NULL */
      if (primero==NULL) {
         printf( "Primer elemento\n");
         primero = nuevo;
         ultimo = nuevo;
         }
      else {
           /* el que hasta ahora era el último tiene que apuntar al nuevo */
           ultimo->siguiente = nuevo;
           /* hacemos que el nuevo sea ahora el último */
           ultimo = nuevo;
      }
 }

 void mostrar_lista() {
      struct _agenda *auxiliar; /* lo usamos para recorrer la lista */
      int i;

      i=0;
      auxiliar = primero;
      printf("\nMostrando la lista completa:\n");
      while (auxiliar!=NULL) {
            printf( "Nombre: %s, Telefono: %s\n",
                    auxiliar->nombre,auxiliar->telefono);
            auxiliar = auxiliar->siguiente;
            i++;
      }
      if (i==0) printf( "\nLa lista está vacía!!\n" );
 }

 int main() {
     char opcion;

     primero = (struct _agenda *) NULL;
     ultimo = (struct _agenda *) NULL;
     do {
         mostrar_menu();
         opcion = getch();
             switch ( opcion ) {
                case '1': anadir_elemento();
                       break;
                case '2':  printf("No disponible todavia!\n");
                        break;
                case '3': mostrar_lista(primero);
                        break;
                case '4': exit( 1 );
                default: printf( "Opcion no válida\n" );
                         break;
             }
     } while (opcion!='4');
 }

En este ejemplo la lista está definida implícitamente por la existencia de los punteros *primero y *ultimo, pero no como una nueva estructura de datos, sino simplemente como elementos. Bueno, esto no es sencillo...


Salu2