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}

Podría interesarte...

Procedimiento para crear una lista
Procedimiento para crear una lista de nodos
Procedimiento para recorrer una lista enlazada
Procedimiento para recorrer una lista enlazada y visualizar los datos por pantalla en Pascal
Añadir un nodo al final de una lista
Procedimiento en Pascal que añade al final de una lista un nodo
Busqueda en una lista
Busqueda de un nombre en una lista de nombres