Consultoría Informática: Programas a medida, Páginas web, Tiendas Online, Posicionamiento en Internet (SEO), Accesibilidad, Usabilidad...

Ordenar una lista enlazada

Autor: José Luis Álvarez

El siguiente programa, implementado en Pascal, ordena alfabéticamente los elementos de una lista:

TYPE
T_NODO_FRUTA   = ^NODO_FRUTA;

NODO_FRUTA   = RECORD
       nombre : string;
       sig : T_NODO_FRUTA;
   END;

   
PROCEDURE INTERCAMBIO_DE_DOS_NODOS(VAR lista, ant, aux, pos : T_NODO_FRUTA);
{Para ordenar comparamos los nodos de 2 en dos 2, si se cumple la condicion impuesta el algoritmo para intercambiar ambos nodos es siempre este}

BEGIN
   pos:=aux^.sig;
   aux^.sig:=aux^.sig^.sig;
   pos^.sig:=aux;
   IF aux = lista THEN lista:=pos
   ELSE ant^.sig:=pos;
END; { INTERCAMBIO_DE_DOS_NODOS }

PROCEDURE ORDENA_LISTA(VAR lista_a : T_NODO_FRUTA);

VAR
   aux, ant, pos : T_NODO_FRUTA;
   i, cambio, x : INTEGER;

//Variable cambio nos indicara si se han tenido que intercambiar
//los ultimos dos nodos computados. Variable x nos indicara cuantos nodos se han //tenido que intercambiar en total al recorrer la lista completa

BEGIN
   ant:=NIL; pos:=NIL; aux:=lista_a; x:=0; //inicializamos valores

   IF (aux <> NIL) AND (aux^.sig <> NIL) THEN
   //Si lista_a no tiene nodos o solo tiene
   BEGIN //uno no hay que hacer nada
      REPEAT
    aux:=lista_a; x:=0;
   //Cada vuelta del bucle REPEAT estas variables deben inicializarse

      WHILE aux^.sig <> NIL DO //Mientras que aux no llegue al ultimo nodo
      BEGIN
         cambio:=0; //No se han intercambiado nodos, por tanto, cambio = 0

         IF aux^.nombre >   aux^.sig^.nombre THEN
         BEGIN

//En cuanto el nodo superior tenga un caracter mayor que el inferior se
//intercambia los nodos, la sentencia despues del OR se implementa para
//los casos por ejemplo que titulo = a y titulo.sig = aa

         INTERCAMBIO_DE_DOS_NODOS(lista_a, ant, aux, pos);
         INC(cambio); INC(x);
//Se produjo un intercambio por tanto incrementamos
         BREAK;
         END;

         IF cambio <> 0 THEN ant:=pos
         ELSE BEGIN ant:=aux; aux:=aux^.sig; END;
         END; {WHILE}
//Continuamos hasta que lleguemos al final de lista

      UNTIL
      x = 0
//Continuamos hasta que nose haya tenido que intercambiar ningun nodo en la lista
      END; {IF 1}

   END; {FIN PROCEDURE ORDENA_LISTA}