Dev - C++ - Listas Con Nodos - Ayuda

Lo que pasa es que tengo que ordenar unos nodos en ascendente y descendente.
Con burbuja esta fácil pero no se como hacerle con nodos, quisiera ver si alguien me ayuda y se los agradezco de todos modos si no pueden, solo faltarían las funciones de ordenamiento, el termino CAJA se refiere al NODO:

#include <cstdlib>
#include <iostream>

using namespace std;

struct caja{
int a;
struct caja *post;
};
typedef caja *CAJA;

void iniciar(CAJA &N)
{
N=NULL;
}
int vacia(CAJA N)
{
if (N==NULL)
return 1;
return 0;
}

void insertar(int x, CAJA &N)
{
CAJA M;
if (vacia(N))
{
N=new caja;
N->a=x;
N->post=NULL;
}
else
{
M=new caja;
M->a=x;
M->post=N;
N=M;
}
}
void eliminar(CAJA &N)
{
CAJA M;
if (vacia(N))
cout<<"La lista se encuentra vacia"<<endl;
else {
M=N;
N=N->post;
delete M;
}
}

void mostrar(CAJA N)
{
CAJA M;
if (vacia(N))
cout<<"La lista se encuentra vacia"<<endl;
else {
M=N;
while (M!=NULL)
{
cout<<M->a<<" - > ";
M=M->post;
}
cout<<" NULL "<<endl;
}

}

void ASC(CAJA *N)
{
//Como le hago?
}

void DESC(CAJA *N)
{
//Como le hago?
}

int main(int argc, char *argv[])
{
CAJA N;
int elec,x;

iniciar(N);

do {
system("CLS");
cout<<" MENU "<<endl;
cout<<" 1. Insertar Nodo "<<endl;
cout<<" 2. Eliminar Nodo "<<endl;
cout<<" 3. Ordenar Ascendente "<<endl;
cout<<" 4. Ordenar Descendente "<<endl;
cout<<" 5. Mostrar Lista"<<endl;
cout<<" 6. Salir "<<endl;
cout<<" Elige una opcion: ";
cin>>elec;
switch(elec)
{
case 1: cout<<"Dato: " ;
cin>>x;
insertar(x,N);
break;
case 2: eliminar(N);
break;
case 3: ASC(N);
break;
case 4: DESC(N);
break;
case 5: mostrar(N);
break;
case 6: cout<<"Fin del Programa "<<endl;
break;
default: cout<<"Opcion no valida. "<<endl;
}
system("PAUSE");
}while (elec!=6);

return EXIT_SUCCESS;
}

Hola.

Tal y como has implementado la "lista" te va a resultar difícil. Ya que más que una lista se parece a una pila, cuando insertas un elemento se inserta al inicio de la secuencia y cuando eliminas también se hace al inicio de la secuencia. La estructura que aqui presentas es de carácter LIFO (el último que entra es el primero que sale), en una lista sin embargo la insercción y la extracción se puede realizar en cualquier posición.

Si lo que deseas es ordenar una lista de elementos te aconsejo que busques la definición de la estructura de datos lista, las distintas implementaciones que existen y cómo se implementan las funciones básicas de inicialización, modificación, lectura y liberación de memoria. Verás que quedándote afianzandos estos conocimientos no tendrás problemas para implementar los algoritmos de ordenación.

Si lo que deseas es ordenar la estructura de datos que presentas puede optar por varias soluciones.

La primera que se me ocurre es sin acceder a la implementación de la estructura de datos. Consiste en añadir una función a la estructura de datos que devuelva el primer elemento de la secuencia (el valor del primer nodo). La función de ordenación leería el primer elemento de la estructura, lo metería en un vector y eliminaría el primer nodo, repitiendo la misma acción meteriamos en el vector el segundo elemento de la secuencia inicial y si seguimos hasta que la lista este vacía abremos metido en el vector toda la secuencia, aplicariamos el algoritmo de la burbuja al vector y volveríamos a introducir los elementos en el orden del vector, depende del extremo del vector por el que empecemos la secuncia quederá ordenada ascendete o descendentemente.

La segunda que se me ocurre es accediendo a la implementación interna de la estructura. Quizás esta solución se ajuste más a lo que deseas hacer. No obstante, no veo buena práctica que una función de ordenación acceda a la implementación interna de una estructura de datos. La solución conciste en crear un vector de punteros a nodos, recorrer la secuencia intruduciendo una referencia a cada nodo en el vector, reordenar el vector por el algoritmo de la burbuja según el valor del campo "a" de la estructura a la que apunta cada elemento del vector y, por último, hacer que el puntero inicial apunte al mismo elemento que el primer elemento del vector, el campo "post" de la estructura a que apunta apunte al mismo nodo que el segundo elemento del vector, este nodo apunte al mismo que el tercero del vector y así hasta completar el vector, el último nodo considerado debe apuntar a 0 ( como el lenguaje es C++, NULL se representa con el valor 0). Resumiendo, se ha referenciado cada nodo, se ha ordenado cada nodo según estas referencias y luego se ha modificado los punteros de cada nodo para que el orden sea el correcto.

Espero haberte ayudado.

Disculpeme pero se me han olvidado un último caso.

En el caso de que desee aplicar el algoritmo de la burbuja sobre los nodos de la estructura que presentas y no sobre un vector (creo que es a esto a lo que te refieres, disculpeme pero a la hora que es estoy falto de sueño). En este caso se debe acceder a la implementacion de la estructura de datos. Debe tener muy claro el fundamento del algoritmo de la burbuja. En el algoritmo de la burbuja aplicado a un vector de elementos se recorre el vector parcialmente varias veces de forma que para cada elemnto se intercambia sucesivamente con los elemento consecutivos mientra estos sean menor/mayor que él. Pues para una secuencia de nodos lo mismo, pero intercambiando nodos.

A la hora de intercambiar nodos se hace necesario acceder al nodo anterior a un nodo dado por lo que es recomendable para obtener mayor eficiencia que cada nodo además de referenciar al nodo que le sigue referencia al nodo anterior. Si no se hace esto se debera recorrer la secuencia desde el primer nodo buscando el nodo tal que el nodo siguiente sea el nodo al que se le desea obtener el anterior.

Suponga que tiene esta secuencia de nodos: A(3), B(4), C(2)

El algoritmo comenzaría declarando un par de punteros a nodos "a" y "b"

"a" inicialmente apuntaría al primer elemnto y "b" al siguiente.

a-> A(3), b -> B(4), C(2)

Como el elemento que apunta "a" es menor que el que apunta "b" se incrementa "a" haciendo que "a" apunte al mismo que "b" y se hace que "b" apunte al siguiente

A(3), a->B(4), b->C(2)

Como el elemento al que apunta "a" es mayor que el que apunta "b" se realiza un intercambio. Se debe hacer que el elemento antererior al nodo al que apunta "a", en el ejemplo A, apunte al nodo al que apunta "b", en el ejemplo C, y que el nodo al que apunta "a", es decir B, apunte al elemento al que apunte el nodo al que apunte "b", en el ejemplo NULL o 0, luego se debe hacer que el nodo al que apunte "b", en el ejemplo C, apunte al nodo al que apunta "a", es decir B. Tras el intercambio quedaría así:

A(3), b->C(2), a->B(4).

Hariamos que "b" apuntara al siguiente de "a" pero es nulo, por lo que abremos terminado una pasada de la secuencia. La siguiente pasada comenzaría de nuevo con "a" apuntando al primer elemento y "b" al segundo.

El algoritmo de la burbuja asegura que en cada pasada el vector tiene un elemento más en la posición correcta, por lo que en cada pasada no es necesario recorrer el vector entero. Para evitar recorrer el vector entero se puede utilizar un tercer puntero que inicialmente apunte a 0 o null y que en cada pasada apunte a un elemento más atrás en la secuencia empezando desde el último la pasada terminará cuando "b" sea igual a este tercer puntero.