Ordenar lista simplemente enlazada en lenguaje C.

[NOB2014]

Hola, que tengas un muy buen día.



En primer lugar, les consulto si la imagen refleja lo que es un nodo, sin tener en cuenta las direcciones de memoria que no necesariamente son continuas como un vector. -
Y la otra duda es, como debo hacer para que la lista quede ordenada. -
Les pediría un pequeño favor mas, si es posible me ayuden con pseudocódigo quiero encarar la solución por mí mismo, luego si se me queman los papeles les pediré algo de código. -

Código (c) [Seleccionar] Expandir

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


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

struct _agenda *primero, *ultimo;

void mostrar_menu();
void agregar_elemento();
void mostrar_lista();

int main(void){
char opcion, ch;

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();
break;
case '2':  printf("No disponible todavía!\n");
break;
case '3': mostrar_lista(primero);
break;
case '4': exit( 1 );
default: printf( "Opción no válida\n" );
printf( "\n Pulse una tecla para continuar..." ); getchar();
break;
}
} while (opcion!='4');   

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 - Salir" );

printf("\n\n Escoge una opcion......: ");
}

void agregar_elemento(){
struct _agenda *nuevo;
int ch;

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');

nuevo->siguiente = NULL;

if( primero == NULL ){
printf( "\n Primer elemento" );
primero = nuevo;
ultimo  = nuevo;
}else{
ultimo->siguiente = nuevo;
ultimo = nuevo;
}
}


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

auxiliar = primero;
printf( "\n Mostrando la lista completa:\n ");
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();
}


Saludos.

[MCKSys Argentina]

Hola!

La imagen me parece bien. Quizás podrías colocar valores hexa (y más grandes, tipo 0x0001CAFE) a las direcciones donde se encuentran los nodos, pero la idea en gral. la veo bien.

Con respecto al ordenamiento, creo que lo más sencillo de aplicar es ordenación por burbuja.
Te dejo un par de links para que mires cómo es el método:

http://c.conclase.net/orden/?cap=burbuja
https://es.wikipedia.org/wiki/Ordenamiento_de_burbuja

Saludos!

[AlbertoBSD]

Si esa imagen es de nodos de lista ligada o colas.

Algoritmo.

Pasar los datos de la lista ligada simple a un arreglo lineal, Tienes que tener una funcion para obtener valores sin eliminarlos.
una vez en arreglo lineal, ordenas con cualquier método de ordenamiento.

Los vuelves a agregar a una nueva lista y eliminas toda la lista vieja.

Saludos.

[NOB2014]

Hola, MCKSys Argentina muchas gracias por tu tiempo, en realidad el método de la burbuja ya lo tenía lo que necesito es la manera para lograr ordenar una lista simplemente enlazada, dejo lo que tengo logrado, lo que ocurre es que no me doy cuenta como transformar el vector estático ordenado en una lista dinámica, les dejo lo que llevo hecho, espero que puedan guiarme con código o alguna idea. -
Alberto, ya sabrás que todo texto que valla dirigido a voz es un agradecimiento.

Código (c) [Seleccionar] Expandir

void ordenar_lista( size_t cont){
struct _agenda *auxiliar; //LsE008
int tmp[cont], aux, i=0, j;
auxiliar = primero;

if( cont>1 ){ //LsE009
printf( "\n Mostrando la lista ORDENADA (total %lu):\n ", cont);
while( auxiliar != NULL ){
tmp[i] = auxiliar->dato;
auxiliar = auxiliar->siguiente;
i++;
}

//LsE010
for(i=0; i<cont-1; i++) {
for(j=i+1; j<cont; j++) {
if( tmp[i] > tmp[j] ){
aux = tmp[i];
tmp[i] = tmp[j];
tmp[j] = aux;
}
}
}

for( i=0; i<cont; i++ ){
printf( "\n %d", tmp[i] );
}
printf( "\n\n Pulse una tecla para continuar..." ); getchar();
}else{
printf( "\n No cuenta con suficientes elementos para ordenar.\n\n"
" Pulse una tecla para continuar..."); getchar();
}
}



/* ================ Ayuda ================

LsE001 -> Con esta función añadimos un elemento al final de la lista.
LsE002 -> reservamos memoria para el nuevo elemento.
LsE003 -> El campo siguiente va a ser NULL por ser el último elemento.
LsE004 -> 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.
LsE005 -> El que hasta ahora era el último tiene que apuntar al nuevo.
LsE006 -> Hacemos que el nuevo sea ahora el último.
LsE007 -> Lo usamos para recorrer la lista.
LsE008 -> Lo usamos para recorrer la lista
LsE009 -> Verificamos si hay más de 1 dato para ordenar. de ser asi ponemos los datos
  en un vector.
LsE010 -> Ordenamos el vector.
*/
Saludos.

[AlbertoBSD]

lo que ocurre es que no me doy cuenta como transformar el vector estático ordenado en una lista dinámica

Vas bien aun tengo mi duda con una linea de tu codigo pero eso es otro detalle.

Como comente

Los vuelves a agregar a una nueva lista y eliminas toda la lista vieja.

Creas una nueva lista, he iteras en el arreglo de principio a fin agregando los nodos a esa nueva lista.

El detalle que veo es que tu funcion para agregar un elemento a la lista solo lo tienes como para agregar datos que vienen desde el teclado. Tienes que tener una funcion a la cual le puedas pasar un argumento o dos (valor a agregar y lista a la que se lo va a agregar.

Y asi creas una nueva lista y destruyes la lista vieja algo como

Código (c) [Seleccionar] Expandir

//Destruir una lista
void destruir_lista(struct _agenda *primero){
struct _agenda *pivote,*auxiliar  =primero;
while( auxiliar != NULL ){
pivote = auxiliar->siguiente;
free(auxiliar);
auxiliar = pivote;
}


Por eso si te fijas hago como funciones genericas que puedan procesar cualquier lista.

Te comento que me intriga la siguiente  linea de tu codigo

Código (c) [Seleccionar] Expandir

int tmp[cont];

No te marca error?

Saludos

Se que ya lo viste pero lo dejo aqui para otros usuarios

[youtube=640,360]https://www.youtube.com/watch?v=FqKsZzM0uEU[/youtube]

[NOB2014]

Ahora me hiciste entrar la duda, ¿no se declara de esa manera un vector de enteros?, el programa funciona de maravillas, sin ninguna advertencia. -

[AlbertoBSD]

Si, pero solo lo habia visto con valores constantes, Y para valores variables solo lo habia visto con memoria dinámica ya sea malloc o con new.

ahora que llegue a la casa lo valido

Saludos

[geeke]

Te comento que me intriga la siguiente  linea de tu codigo

Código (c) [Seleccionar] Expandir

int tmp[cont];

No te marca error?

Es una característica que se agregó a partir de C99 pero se volvió opcional en C11, se les denomina array de longitud variable

Mas info:

https://en.m.wikipedia.org/wiki/Variable-length_array

Código (c) [Seleccionar] Expandir

#include <stdio.h>

int main()
{
    size_t n;

    printf("Ingresar longitud: ");
    scanf("%d", &n);

    int array[n];

    for(int i = 0; i < n; i++)
    {
array[i] = i + 1;
printf("%4d ", array[i]);
    }
    return 0;
}

[AlbertoBSD]

agregó a partir de C99

Gracias por la respuesta y el ejemplo De hecho lo habia buscado rapidamente y llegué al siguiente enlace en stackoverflow

http://stackoverflow.com/questions/448844/variable-sized-arrays-vs-calloc-in-c

Donde de igual manera los expertos siguen recomendando otras formas de inicializar.

Aun asi para el ejemplo mostrado y dado que ae trata de una variable temporal y auxiliar dentro de una funcion esta bien usarlo asi.

Ahora aclarado eso solo queda esperar que NOB2014 solucione el detalle de crear una nueva lista ligada con el arreglo mencionando y sustiyendo a la matriz vieja.

Saludos

[ivancea96]

lo que ocurre es que no me doy cuenta como transformar el vector estático ordenado en una lista dinámica

Si lo que quieres es ordenar la lista que ya tienes, puedes aplicar el algoritmo de burbuja directamente en la lista, sin pasar por un array intermedio. El procedimiento es el mismo, cambiando índices por iteradores (struct _agenda* en tu caso).