Ordenamiento de una lista simplemente enlazada

El ordenamiento de una lista simplemente enlazada es similar al ordenamiento de vectores con la gran diferencia de que en una lista simplemente enlazada no disponemos del concepto del “índice” que nos ayuda a acceder directamente a un elemento de la lista, en este caso para acceder a un elemento debemos recorrer desde el inicio hasta hallar el elemento que nos interese.

Un algoritmo sencillo es el del Intercambio, consiste en lo siguiente:

1. Situar un puntero al inicio de la lista que nos irá indicando a medida que vayamos ordenando, cuánto de la lista ya está ordenada, es la variable más importante del algoritmo porque nos servirá para saber que hemos acabado de ordenar la lista.

Elemento * elemBase = elemInicio;

while(elemBase != NULL)

{

//en este proceso vamos ordenando la lista a partir del nodo elemBase hasta el final

elemBase = elemBase->next;

}

2. En el caso que el ordenamiento sea de menor a mayor, necesitamos encontrar el menor de los elementos a partir del elemento base hasta el final de la lista.

En el caso del ordenamiento de Vectores obteníamos la posición, en este caso obtendremos un puntero al menor elemento.

Elemento* buscarMenor(Elemento* ptrInicial)

Esta función tendría que utilizarse en cada iteración

Elemento * elemBase = elemInicio;

Elemento* elemMenor; //puntero que nos sirve para apuntar al menor elemento encontrado

while(elemBase != NULL)

{

elemMenor = buscarMenor(elemBase);

elemBase = elemBase->next;

}

3. Intercambiar el elemento menor con el elemento que se encuentra apuntando el puntero base. Para hacer este intercambio es necesario que el elemento anterior al elemento base apunte al elemento menor, para eso necesitamos un puntero que apunte al anterior del elemento base.

Como es una lista simplemente enlazada, no podemos retroceder para hallar al puntero anterior al puntero base, por tanto, crearemos una función que nos sirva para ubicarnos en el elemento anterior que queramos. Esta función es necesaria para luego poder hacer el intercambio de nodos.

Elemento * getElemAnterior(Elemento* elemInicio, Elemento* elem);

Utilizaremos esta función para obtener el elemento anterior al base y al menor y de esta forma poder realizar el intercambio

Elemento * elemAnteBase = NULL;//puntero que apunta al anterior de elemento base

Elemento * elemBase = elemInicio;

Elemento* elemAnteMenor; //puntero que apunta al anterior del elemento menor

Elemento* elemMenor; //puntero que nos sirve para apuntar al menor elemento encontrado

while(elemBase != NULL)

{

elemMenor = buscarMenor(elemBase);

elemAnteBase = getElemAnterior(elemInicio, elemBase);

elemAnteMenor = getElemAnterior(elemInicio, elemMenor);

elemBase = elemBase->next;

}

Teniendo el puntero anterior al base ya podemos hacer el intercambio:

void intercambio(Elemento* elemAnteBase, Elemento* elemBase,

Elemento* elemAnteMenor, Elemento* elemMenor);

Incorporamos el intercambio en cada iteración y asignamos el nodo menor como el nuevo elemento base:

Elemento * elemAnteBase = NULL;//puntero que apunta al anterior de elemento base

Elemento * elemBase = elemInicio;

Elemento* elemAnteMenor; //puntero que apunta al anterior del elemento menor

Elemento* elemMenor; //puntero que nos sirve para apuntar al menor elemento encontrado

while(elemBase != NULL)

{

elemMenor = buscarMenor(elemBase);

elemAnteBase = getElemAnterior(elemInicio, elemBase);

elemAnteMenor = getElemAnterior(elemInicio, elemMenor);

intercambio(elemAnteBase, elemBase, elemAnteMenor, elemMenor);

elemBase = elemMenor;

elemBase = elemBase->next;

}

4. Finalmente desarrollamos las funciones:

Elemento* buscarMenor(Elemento* ptrInicial)

{

Elemento* elemMenor = ptrInicial;

Elemento* ptr = ptrInicial;//puntero que sirve para recorrer la lista

int menorValor = elemMenor.valor;//inicializamos el primer valor menor

//recorremos toda la lista y dejamos el puntero elemMenor en el de menor valor

while(ptr!=NULL)

{

if(ptr.valor < menorValor)

{

elemMenor = ptr;

menorValor = ptr.valor;

}

ptr = ptr->next;

}

return elemMenor;

}

void intercambio(Elemento* elemAnteBase, Elemento* elemBase,

Elemento* elemAnteMenor, Elemento* elemMenor)

{

Elemento* aux = elemBase->next; //nos sirve para hacer el intercambio sin perder punteros

elemBase->next = elemMenor->next;

elemMenor->next = aux;

elemAnteBase->next = elemMenor;

elemAnteMenor->next = elemBase;

}

Elemento * getElemAnterior(Elemento* elemInicio, Elemento* elem)

{

Elemento*anterior = NULL;

Elemento*ptr = elemInicio;

int finBusqueda = 0;

while(ptr!=NULL && ptr->next!=NULL && !finBusqueda)

{

if(ptr->next.valor == elem.valor)

{

finBusqueda = 1;

}

anterior = ptr;

ptr = ptr->next;

}

return anterior;

}

Push en una Pila

Cuando nos explican el concepto de Pilas lo principal es que: "el primero que entra es el primero que sale":

con esto parece que tenemos toda la teoría aprendida, el problema viene cuando intentamos implementarlo y no sabemos por dónde empezar.

Por lo general cuando se explica este tema se hace en C++ y utilizando estructuras, por tanto antes de continuar esta explicación os recomiendo leer previamente el post relacionado a estructuras

Vemos en la imagen que cada elemento de la pila está formado por un círculo con un valor y una flecha que lo une con el siguiente círculo, con estos dos elementos formaremos un elemento de la Pila, de esta forma:

struct ElemPila{
  int valor; //esto representa el valor que está dentro del círculo
  struct ElemPila * siguienteElem; //esto representa la flecha, observar que es un puntero
};

Hasta aquí tenemos definida la estructura, pero aún no la estamos utilizando, ahora veremos como desde el programa utilizamos esta esta estructura para agregar los elementos: 1, 2 y 3:

int main()
{
  / /Creamos el primer elemento, con valor 1 y la flecha que apunta al siguiente elemento apunta a NULL
   struct ElemPila* elem1 = new ElemPila; //reserva memoria para el contenido de la estructura
   elem1->valor = 1; //inicializa el valor de la estructura
   elem1->siguienteElem = NULL; //inicializa el valor hacia donde apunta el siguiente
   
   struct ElemPila* elem2 = new ElemPila;
   elem2->valor = 2;
   elem2->siguienteElem = NULL;
   
   struct ElemPila* elem3 = new ElemPila;
   elem3->valor = 3;
   elem3->siguienteElem = NULL;
      
   return 0;
}

Al ejecutar este programa lo que logramos es tener 3 elementos independientes, así:

Como paso siguiente modificaremos el programa para introducir el puntero que será cabeza de la pila e introduciremos sólo el primer elemento a la pila:

int main()
{
   struct ElemPila* elem1 = new ElemPila;
   elem1->valor = 1;
   elem1->siguienteElem = NULL;
   
   struct ElemPila* elem2 = new ElemPila;
   elem2->valor = 2;
   elem2->siguienteElem = NULL;
   
   struct ElemPila* elem3 = new ElemPila;
   elem3->valor = 3;
   elem3->siguienteElem = NULL;
   
   struct ElemPila* cabezaPila; //creamos el puntero
   cabezaPila = elem1; //hacemos que apunte al primer elemento
   
   return 0;
}

Para incluir el segundo elemento en la pila, lo que tenemos que hacer es que el segundo elemento apunte al primero (elem1) y la cabeza de pila apunte al segundo:

int main()

{

   struct ElemPila* elem1 = new ElemPila;

   elem1->valor = 1;

   elem1->siguienteElem = NULL;

   struct ElemPila* elem2 = new ElemPila;

   elem2->valor = 2;

   elem2->siguienteElem = NULL;

   struct ElemPila* elem3 = new ElemPila;

   elem3->valor = 3;

   elem3->siguienteElem = NULL;

   struct ElemPila* cabezaPila;

   cabezaPila = elem1;

   elem2-> siguienteElem = cabezaPila;

   cabezaPila = elem2;

   return 0;

}

Finalmente incluimos el tercer elemento, siguiendo los mismo pasos que el anterior, que es hacer que el siguiente de elemento 3 apunte al elemento 2 y la cabeza de la pila apunte a elemento 3:

int main()

{

   struct ElemPila* elem1 = new ElemPila;

   elem1->valor = 1;

   elem1->siguienteElem = NULL;

 

   struct ElemPila* elem2 = new ElemPila;

   elem2->valor = 2;

   elem2->siguienteElem = NULL;

 

   struct ElemPila* elem3 = new ElemPila;

   elem3->valor = 3;

   elem3->siguienteElem = NULL;

 

   struct ElemPila* cabezaPila;

   cabezaPila = elem1;

 

   elem2->siguienteElem = cabezaPila;

   cabezaPila = elem2;

 

   elem3->siguienteElem = cabezaPila;

   cabezaPila = elem3;

 

   return 0;

}

Si observamos atentamente el código y las imágenes veremos que las variables elem1 y elem2 se quedan apuntando a elementos de la pila que en teoría no se deberían acceder directamente (el acceso es sólo con la cabeza de pila), por tanto podríamos deducir que con una sola variable de tipo ElemenPila sería suficiente. De la misma forma podemos observar en el código que el mecanismo para agregar un elemento es el mismo, por lo tanto podríamos utilizar una función para reutilizar el código. todo esto de esta forma:

#include <iostream>

struct ElemPila{

  int valor;

  struct ElemPila * siguienteElem;

};

using namespace std;

//incluimos una función de impresión para comprobar el orden en que se han guardado

void imprimir(struct ElemPila* cabezaPila)

{

    struct ElemPila* auxiliar = cabezaPila;

    while(auxiliar != NULL)

    {

      cout << auxiliar->valor << " - ";

      auxiliar = auxiliar -> siguienteElem;

    }

    cout << "=====================\n";

}

//función que realiza el push de forma genérica para cualquier elemento

struct ElemPila* push(int pValor, struct ElemPila* elem, struct ElemPila* cabezaPila)

{

   elem = new ElemPila;    

   elem->valor = pValor;

   elem->siguienteElem = NULL;

   elem->siguienteElem = cabezaPila;

   cabezaPila = elem;

   return cabezaPila;

}

int main()

{

   struct ElemPila* cabezaPila = NULL;

   struct ElemPila* elem = NULL;

   cabezaPila = push(1, elem, cabezaPila);   

   imprimir(cabezaPila);

       

   cabezaPila = push(2, elem, cabezaPila);   

   imprimir(cabezaPila);

   

   cabezaPila = push(3, elem, cabezaPila);   

   imprimir(cabezaPila);

   

   return 0;

}

Executing the program....

1 - =====================
2 - 1 - =====================
3 - 2 - 1 - =====================

Listas dinámicas

La manera más práctica de trabajar con una lista de objetos del mismo tipo es un Vector (o Array), cuando se instancia un vector se está reservando en memoria una cantidad fija de bytes para almacenar la información, así si tenemos:

int myList[5]; //reserva espacio para 5 variables de tipo int

myList[0] = 1; //almacena el valor 1 en la primera posición del vector

Ahora utilizaré un ejemplo de un problema tipo de examen, habla sobre el registro de reclamaciones de un comercio, cada reclamación debe contener:

• El nombre de la persona que realiza la reclamación
• La fecha de la reclamación
• La descripción de la reclamación
• El estado de la reclamación: 0 si está abierta, 1 si está resuelta.

Para representar una reclamación podemos utilizar una estructura de este tipo:

typedef struct reclamacion

{

String nombrePersona;

Date fechaReclamacion;

String descripcion;

int estado;

}Reclamacion;

Ahora creamos un Vector para almacenar la lista de reclamaciones:

Reclamacion Lista[100]; //vector de capacidad para 100 reclamaciones

Pero, y ¿Qué pasa si hay más de 100 reclamaciones?

Cuando no sabemos la dimensión que puede tomar una lista lo mejor es reservar memoria de forma dinámica, para eso podemos utilizar los punteros.

Así, sólo creamos una variable de tipo puntero que apunte a la estructura, y modificamos la estructura para que apunte al siguiente elemento de la lista, así;

typedef struct reclamacion

{

String nombrePersona;

Date fechaReclamacion;

String descripcion;

int estado;

struct reclamacion * siguiente; //este puntero apunta a la siguiente reclamación

}Reclamacion;

Reclamacion * listaReclamaciones;

listaReclamaciones = NULL; //inicializamos el puntero a NULL hasta que empiecen a llegar las reclamaciones

//creamos la primera reclamación

Reclamacion * rec1 = new Reclamacion;

rec1.nombrePersona = “Juan”;

rec1.fechaReclamacion = new Date(); //representa que toma la fecha actual (esto varía según el lenguaje de programación)

rec1.descripcion = “ejemplo de reclamacion1”;

rec1.estado = 0; //lo inicializa a 0 porque cuando se crea está abierta

rec1->siguiente = NULL; //inicializa a NULL porque es un puntero

Ahora para agregar la primera reclamación a la lista hacemos que la variable listaReclamaciones ya no apunte a NULL sino que apunte al elemento rec1:

listaReclamaciones = rec1;

Para el caso de una segunda reclamación es distinto y dependerá si se quiere agregar al principio de la lista o al final de la lista, vamos a agregarlo al final, así listaReclamaciones apuntará a rec1 y rec1->siguiente apuntará a rec2:

//creamos la segunda reclamación

Reclamacion * rec2 = new Reclamacion;

rec2.nombrePersona = “Pedro”;

rec2.fechaReclamacion = new Date(); 

rec2.descripcion = “ejemplo de reclamacion2”;

rec2.estado = 0; 

rec2->siguiente = NULL; 

Si hacemos:

listaReclamaciones->siguiente = rec2; //es lo mismo que rec1->siguiente = rec2

Tenemos el problema resuelto, rec1->siguiente ya no apunta a NULL sino que apunta a rec2 y rec2 es la última de la lista.

¿Y que pasa si no sabemos la cantidad de elementos que tiene la lista y queremos agregar un elemento al final?

La solución es tomar un puntero auxiliar y desplazamos hasta el último elemento de la lista y hacer que este último elemento apunte al elemento nuevo que queremos agregar a la lista:

//puntero auxiliar que se desplaza hasta el último elemento

Reclamacion * pAuxiliar = listaReclamaciones; //se inicializa apuntando al primero de la lista

//mientras el siguiente del auxiliar es distinto a nulo, avanza el puntero al siguiente elemento, hasta llegar al último

while(pAuxiliar->siguiente != NULL) pAuxiliar = pAuxiliar->siguiente;

//ahora agregamos el nuevo elemento al final de la lista

pAuxiliar-> siguiente = nuevaRec; //nuevaRec es el nuevo elemento de tipo reclamacion*

Existen muchas variantes:

• agregar el elemento al inicio de la lista
• agregar el elemento en medio de la lista (por ejemplo para una lista ordenada)