lista enlazada simple en C

[vosk]

Supongo que la cosa viene del mismo sitio http://www.forosdelweb.com/f96/como-...crear-1081767/

Tienes que hacer un ciclo externo para todos los elementos, y para cada vuelta haces otro ciclo interno para colisionar todos los elementos contra un numero de elementos igual a la cantidad total menos el indice del ciclo externo, que traducido sería algo así:

Código C:

int q, w, st, sz = list_length;
 
//ciclo externo
for(q = 0; q < sz; q++) {
 
        //calculas las steps del ciclo interno
        st = sz - q - 1;
 
        //ciclo interno
        for(w = 0; w < st; w++) {
            //algoritmo de comparacion y reordenacion
        }
}
 

Ahora la comparacion, que sería como la parte artistica: comparas como quieres; si quieres de mayor a menor o si quieres de menor a mayor, el funcionamiento es el mismo; el elemento critico siempre se mueve a la siguiente posicion de forma que en el siguiente step es el primero de los dos a comparar, y al final queda ordenado y por eso en el siguiente ciclo interno se omite ok?

Una nota: al determinar las steps siempre obtienes como maximo un numero menor a la longitud de la lista, por eso es seguro acceder a las posiciones actual y siguiente; una vez tienes localizadas las posiciones que quieres ordenar solo tienes que compararlas:

Código C:

if(cabeza[w] < cabeza[w+1]) {
    //reordenacion
}
 

Ten en cuenta que el w+1 es una operacion de riesgo, en este caso funciona porque la operacion que determina las steps me limita como ultimo indice a la longitud de la lista menos 1. Si el contador de steps estuviese mal, el w+1 podria apuntar fuera de la lista a una posicion de memoria no accesible por la aplicacion (violacion de segmento).

Ahora la comparacion , en este caso el algoritmo de comparacion es muy simple porque el < te da la solucion. Si quieres ordenar al reves (de mayor a menor) solo has de cambiar el operador. Pero si por ejemplo quisieras ordenar una lista de palabras segun el numero de caracteres primero contarias los caracteres y luego los compararias con el operador, es decir que al final haces lo mismo: determinar si hay swap o no. Puedes implementar la version extendida que consiste en llamar a una funcion externa para que te haga la comparacion y retorne un indicador de si tiene que reordenar, que sería lo que hacen las funciones de 'sort': les envias una lista y un puntero a una funcion de comparacion que defines tu, luego en base al resultado de la funcion se intercambian los elementos. Un ejemplo para hacerlo con funciones:

Código C:

//declaras las funciones de comparacion
char asc(int a, int b) {
    return (a > b)? 1:0;
}
//declaro las dos para darle mas emocion
char desc(int a, int b) {
    return (a < b)? 1:0;
}
 
//declaras la funcion de ordenacion, observa el puntero a la funcion
void ordenar(punteroNodo *cabeza, int (*fptr)(int , int )) {
    //aqui van los ciclos
    //hasta que llegas a la comparacion de cada elemento, en vez de hacerlo de forma
    //directa con if(cabeza[w] < cabeza[w+1]), lo haces evaluando el retorno de la funcion
    if(fptr(cabeza[w], cabeza[w+1])) {
        //reordenacion
    }
}
 
//en la llamada a la funcion de ordenacion envias un puntero a la lista y otro 
//a la funcion que quieres usar
ordenar(&lista, desc);
ordenar(&lista, asc);
 

Esto solo es para determinar si requiere swap (intercambio); esto de las funciones auxiliares sirve para cuando tienes fechas, texto o simplemente quieres optimizar la funcion de comparacion: en vez de hacer varias funciones enteras de comparacion haces una que llame a un tipo de comparacion. Los tipos de datos de las funciones auxiliares de comparacion pueden cambiarse a punteros void* para que el tipo de dato sea cualquiera; en este caso del ejemplo se limita a enteros para que veas de que va la cosa.

Hasta aqui ok no? :)) Esto de antes de las funciones de comparacion auxiliares puedes omitirlo, pero ahora que lo conoces podras tenerlo en cuenta en otra ocasion.

Y finalmente el swap: en caso que se cumpla la condicion critica intercambias los elementos; para eso (tal como te comenté en el otro hilo) debes guardar una referencia del primer elemento que sobreescribes, asignas el segundo al primero y asignas la referencia guardada al primero:

Código C:

aux = cabeza[w];//referencia
cabeza[w] = cabeza[w+1];
cabeza[w+1] = aux;
 

Otra observacion: cuando estas trabajando con punteros sobre el original en una lista dinamica la operacion cabeza[w] = cabeza[w+1] produce una perdida de memoria (memory leak), para evitarla usas el auxiliar.

Y ya lo tienes. El lenguaje C es bonito y divertido, y si te salen las cosas aun lo es mas ;)

Saludos
vosk