Ordenar lista simplemente enlazada en lenguaje C.

[NOB2014]

Hola, que tengan un muy buen día. -
ivancea96, no lo intente de esa manera porque a la apurada leí que era muy costoso hacerlo directamente sobre la lista y como Alberto me sugirió hacerlo de la otra manera no lo pensé demasiado y lo intente, pero no hay caso no solo no me sale, sino que ahora también descubro que no tenía demasiado conocimiento de estructuras anidadas, en conclusión estoy en un pozo demasiado profundo y muy confundido. -
Descarte el código que deje en el primer post y lo estoy intentando con el programa que esta en el video de Alberto sin el borrado de nodo, lo que ocurre es que podría aprenderme la sintaxis de memoria y continuar pero tengo claro que esa no es la forma de estudiar en serio. -
En definitiva, voy a respirar muy profundo, pensar tranquilo e intentar interpretar lo que ahora me tiene ocupado que son las 2 estructuras, créanme que si los tuviera sentado frente a una computadora a algunos de Uds. ni siquiera así intentaría pedirles alguna ayuda dado que es algo que me da vueltas con respecto a las dos estructuras pero no logro expresar exactamente lo que no entiendo.
En conclusión, voy a seguir pensando en el tema y si me surge alguna duda concreta la voy a postear.

Código (c) [Seleccionar] Expandir

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

//LsL001

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

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

struct lista *agregar( struct lista *L, int dato );
struct nodo *crear( int dato );

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

Lista = agregar( Lista, 1 );
Lista = agregar( Lista, 2);
Lista = agregar( Lista, 3);

return 0;
}

struct lista *agregar( struct lista *L, int dato ){
if( L != NULL ){
struct nodo *e = crear( dato );
printf( "\n Creando elemento con valor %d", dato );
L->ultimo->siguiente = e;
L->ultimo = e;

return L;
}else{
struct nodo *e = crear( dato );
struct lista *l = calloc( sizeof( struct lista ), 1 );
printf( "\n Inicializando la lista con valor %d", dato );
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;
}

/*
============================== LsL001 ==============================
- Definir estructura.
- Inicializar.
- Agregar elementos.
- Ordenar elementos.
- Borrar elementos.
*/
       

Saludos.   

[AlbertoBSD]

Yo sugerí el pasarlo a un arreglo externo para que no lo vieras como una lista ligada.

El algoritmo es el mismo para la lista ligada, lo que cambia contra tu arreglo es el acceso a los elementos de la lista y las condiciones de parada...

En el ordenamiento de burbuja que tenias se compara dos valores y si uno es mayor se hace el cambio de variable, esto para ordenar la lista

Enronces lo que necesitas es guardar las direcciones de memoria en un apuntador por ejemplo (pivotey actual). Hacer la comparación

Código (c) [Seleccionar] Expandir

//While o for aquí
//guardar valores de actual y siguiente
if(pivote->dato > actual->dato){
//hacer cambio de variable aqui.
}
//fin while o for


Solo necesitas traducir el algoritmo que ya tienes de burbuja por el correspondiente a lista ligada

Te propongo que hagas el ejercicio a mano.

usando este ejemplo como datos del la Lista:

Código (c) [Seleccionar] Expandir


/*
Variable Entera
tmp

Variables Nodos:
Pivote
Actual

Lista:
[200]->[150]->[100]->[50]->[0]->[40]->NULL
Primero                         Ultimo
*/


Tu algoritmo burbuja ya lo tienes:

Código (c) [Seleccionar] Expandir

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;
}
}
}


Solo tienes que cambiar las variables temp[i,j] por los correspondientes.

Saludos

No me pude resistir 

Código (c) [Seleccionar] Expandir

void ordenar_lista(struct lista *L) {
//Elegir metodo de ordenamiento
// Burbuja
struct nodo *pivote = NULL,*actual = NULL;
int tmp;
if(L != NULL) {

pivote = L->primero; //i = 0
while(pivote != L->ultimo) { //for(i=0; i<cont-1; i++) {
actual = pivote->siguiente; //j=i+1
while(actual != NULL) { //for(j=i+1; j<cont; j++) {
if(pivote->dato > actual->dato) { //if( tmp[i] > tmp[j] ){
tmp = pivote->dato; //aux = tmp[i];
pivote->dato = actual->dato; //tmp[i] = tmp[j];
actual->dato = tmp; //tmp[j] = aux;
}
actual = actual->siguiente; //j++
}
pivote = pivote->siguiente; //i++
}
}
else {
printf("Error lista no inicializada");
}
/*
Pivote
Actual
[200]->[150]->[100]->[50]->[0]->[40]->NULL
Primero                         Ultimo

*/
}

[NOB2014]

Hola, gente. -
Les pido un esfuerzo más, alguien que tenga mucho tiempo y ganas me podría decir si lo que puse en las imágenes es medianamente correcto. -




Saludos. 

[ivancea96]

No me pareció ver nada relevante, salvo que usas siempre calloc. calloc es lo mismo que malloc, solo que inicializa la memoria a 0. Salvo que realmente lo necesites, te recomendaría usar malloc.

[NOB2014]

Hola, ivancea96. -
Yo no puse las imágenes para que lo que está escrito sea relevante, solo para que me digan si tienen algún error de concepto. - 

Alberto, No puedo creer lo que estoy viendo, posteaste el código y yo sin enterarme, no lo puedo creer

Saludos.   

[AlbertoBSD]

La imagen que pusiste esta bien.

Yo le sugerí calloc para que el nodo este limpio, y comente que igualar el dato siguiente a NULL es innecesario si se usa calloc.

• Si usas calloc, no se inicializa en NULL el elemento siguiente
• Si usas malloc, es necesario inicializar el elemento en NULL

Efectivamente puse el código por que no me pude resistir y aqui dejo el ejemplo para probarlo de forma completa:

Código (c) [Seleccionar] Expandir

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

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

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

struct lista *agregar_elemento(struct lista *L, int dato);
struct nodo *crear_elemento(int dato);
void ordenar_lista(struct lista *L);
struct lista *eliminar_indice(struct lista *L, int indice);
int obtener_indice(struct lista *L,int indice);

int main() {
struct lista *Lista = NULL;
int i = 0;
srand(time(NULL));
while(i < 30) {
Lista = agregar_elemento(Lista,rand() % 1000);
i++;
}
ordenar_lista(Lista);
i = 0;
while(i < 30) {
printf("Elemento %i: %i\n",i+1,obtener_indice(Lista,i+1));
i++;
}

/*
Lista = agregar_elemento(Lista,2);
Lista = agregar_elemento(Lista,3);
Lista = eliminar_indice(Lista,3);
Lista = eliminar_indice(Lista,2);
Lista = eliminar_indice(Lista,1);
printf("apuntador de la lista %p\n",Lista);
Lista = eliminar_indice(Lista,1);
*/
return 0;
}

struct lista *agregar_elemento(struct lista *L, int dato) {
if(L != NULL) {

struct nodo *e = crear_elemento(dato);
printf("Creando elemento con valor %i\n",dato);
L->ultimo->siguiente = e;
L->ultimo = e;
L->elementos++;
return L;
}
else {
struct nodo *e = crear_elemento(dato);
struct lista *l = calloc(sizeof(struct lista),1);
printf("Inicializando lista con valor %i\n",dato);
l->primero = e;
l->ultimo = e;
l->elementos++;
return l;
}
}

struct nodo *crear_elemento(int dato) {
struct nodo *e = calloc(sizeof(struct nodo),1);
e->dato = dato;
e->siguiente = NULL; //Fines didacticos ya que Calloc devuelve en 0
return e;
}

struct lista *eliminar_indice(struct lista *L, int indice) {
if(L != NULL) {
if(indice <= L->elementos && indice > 0) {
struct nodo *anterior = L->primero;
struct nodo *pivote = L->primero;
int i = 1;
//printf("while");
while(i < indice) {
//printf("Elemento actual %i\n",pivote->dato);
anterior = pivote;
pivote = pivote->siguiente;
i++;
}
//pivote ya tiene el elemento a eliminar
printf("Elemento a eliminar %i\n",pivote->dato);
if(pivote->siguiente != NULL) {
printf("NO el ultimo elemento\n",pivote->dato);
if(pivote != L->primero) {
printf("Y no es el primero\n");
anterior->siguiente = pivote->siguiente;
free(pivote);
}
else {
printf("Si es el primero\n");
L->primero = pivote->siguiente;
free(pivote);
}
}
else {
printf("Es el ultimo elemento\n",pivote->dato);
if(pivote != L->primero ) {
anterior->siguiente = NULL;
free(pivote);
L->ultimo = anterior;
}
else {
printf("Y tamien es el primero\n");
free(pivote);
}
}
L->elementos--;
if(L->elementos == 0) {
printf("Eliminando Lista\n");
free(L);
return NULL;
}
else {
return L;
}
}
else {
printf("El indice pedido es mayor que los elementos existentes\n");
return L;
}
}
else {
printf("No se puede procesar una lista NO inicializada\n");
return NULL;}
}

void ordenar_lista(struct lista *L) {
//Elegir metodo de ordenamiento
// Burbuja
struct nodo *pivote = NULL,*actual = NULL;
int tmp;
if(L != NULL) {

pivote = L->primero; //i = 0
while(pivote != L->ultimo) { //for(i=0; i<cont-1; i++) {
actual = pivote->siguiente; //j=i+1
while(actual != NULL) { //for(j=i+1; j<cont; j++) {
if(pivote->dato > actual->dato) { //if( tmp[i] > tmp[j] ){
tmp = pivote->dato; //aux = tmp[i];
pivote->dato = actual->dato; //tmp[i] = tmp[j];
actual->dato = tmp; //tmp[j] = aux;
}
actual = actual->siguiente; //j++
}
pivote = pivote->siguiente; //i++
}
}
else {
printf("Error lista no inicializada");
}
/*
Pivote
Actual
[200]->[150]->[100]->[50]->[0]->[40]->NULL
Primero                         Ultimo

*/
}

int obtener_indice(struct lista *L,int indice) {
struct nodo *aux;
int i = 1;
aux = L->primero;
while(i < indice) {
aux = aux->siguiente;
i++;
}
return aux->dato;
}

Genera 30 números aleatorios y los ordena en la misma lista.

Saludos!

[NOB2014]

Que más se puede pedir, gracias por tu tiempo y ya me pongo a estudiar tú código. -
Es una buena oportunidad para decir algo que hace mucho disiento con la mayoría de los que responden en los foros, el tema de retacear código, por aquello de que no se hacen tareas y el prejuicio de que nadie aprende con copiar y pegar, digo, no les parece que es mejor(si tienen el tiempo necesario) escupir código, como leí por allí que un modelador retaba a un participante con esta frase y que los que preguntamos nos hagamos cargo de que es lo que nos conviene?.           

Saludos y un abrazo para todos.

[do-while]

¡Buenas!

Si sabes que la lista no está ordenada, lo que yo haría seria introducir los datos en un árbol binario y luego generar una nueva lista haciendo un recorrido inorden. Siempre puedes crear árboles binarios según distintos criterios de comparación. La forma más sencilla sería pasar como argumento la función de comparación a la función que inserte los nuevos nodos en el árbol:

Código (c) [Seleccionar] Expandir


int insertar_nodo_arbol(tuestruct *dato, int (*cmp)(struct1,struct2));


De esta manera puedes tener funciones que devuelvan <0, 0, >0 según se comparen los structs siguiendo distintos criterios.

Por ejemplo con un árbol de enteros podrías tener una función

Código (c) [Seleccionar] Expandir


int intcmp(int a, int b)
{
   return a-b;
}


para cadenas de caracteres podrías utilizar strcmp, o para un struct con un campo entero y otro una cadena podrías tener dos funciones para ordenarlo con distintos criterios:

Código (c) [Seleccionar] Expandir


struct Cosa
{
   int x;
   char *s;
};

int cmp_cosa_int(struct Cosa *a, struct Cosa *b)
{
   return a->x - b->x;
}

int cmp_cosa_str(struct Cosa *a, struct Cosa *b)
{
   return strcmp(a->s , b->s);
}


Así al pasar los nodos de la lista al arbol solo tendrías que pasar como segundo argumento la función de comparación que quisieses.

Código (c) [Seleccionar] Expandir


int insertar_nodo_arbol(struct Cosa **raiz, struct Cosa *dato, int (*cmp)(struct Cosa *, struct Cosa *))
{
   //...
}


¡Saludos!

[NOB2014]

Hola, buen día. -
Todavía no llegue a leer sobre arboles binarios solo sé que está dentro del capitulo que estoy estudiando, igual ya hice un enlace en mis apuntes para cuando llegue al tema tratar de interpretar tu propuesta. -
La consulta que les voy a efectuar tal vez les resulte infantil, pero créanme que hace más de un día que intento interpretar como funciona pero no hay caso. -
Les pregunto en que lugar de la función ordenar se modifica la estructura nodo, hay 2 punteros a estructura pivote y actual, pero no veo que en ningún lugar se iguale L con el puntero pivote, estoy escribiendo el hilo y regreso a la función para tratar de darme cuenta como funciona pero nada. -     

Código (c) [Seleccionar] Expandir

#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 );
struct lista *ordenar(struct lista *L);
void mostrar(struct lista *L);


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

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

free(Lista);
return 0;
}

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

for( i=8; i>0; 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;
}

struct lista *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");
    }
return L;
}

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.

[AlbertoBSD]

Vas bien, la funcion ordenar nunca modifica la estructura de la lista.

Solo mueve el valor dato de un nodo a otro, incluso todos los nodos siguen en la misma direccion de memoria. Solo se cambia el dato.

si te fijas la funcion que puse en mi codigo es Void por lo cual no regresa valor.

Saludos