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;

}

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)

Representación de un puntero en memoria

La representación de la memoria para una variable de tipo int se puede entender de forma muy simple, en tiempo de ejecución cuando las variable se crean se les asigna un espacio físico en memoria, así cuando vemos:

//se define la variable a de tipo int
int a;

La variable a tiene reservado un espacio para almacenar su contenido (el valor de la variable) y se sabe que ese contenido tiene que ser de tipo int porque así ha sido definida.

Sin embargo, cuando utilizamos variables de tipo punteros la comprensión de la asignación de la memoria es un poco más complicada, una variable de tipo puntero tiene en su definición "al menos un *", aquí unos ejemplos:

int * b;
int **c;

Cuando se reserva memoria para un puntero, se separa un espacio de memoria pero el contenido debe tener el formato de una dirección de memoria. si tomamos como ejemplo:

int * b;

El primer paso es identificar el nombre de la variable y el tipo de la variable:

nombre de variable: b
tipo de la variable: int *

como el tipo de la variable contiene "al menos un *" entonces el contenido (el valor) tiene el formato de una dirección, esa dirección debe apuntar al tipo de variable al cual apunta.

Para saber el tipo de variable al cual apunta, seguimos el segundo paso, que consiste en leer la misma definición de la variable pero ahora el * pasa a ser parte del nombre de la variable:

nombre de variable: *b
tipo de la variable: int

Ahora vemos que la dirección a la que apunta el contenido de b (el valor de b) apunta a una dirección de memoria cuyo nombre se puede interpretar como *b y cuyo tipo es int.

Para verlo de una forma más práctica representaremos las siguientes líneas de código:

int a = 5:

//reserva memoria para el puntero, esta asignación varía según el lenguaje de programación

int* b = new int(); 

     *b = 3;

En una tabla:

Podemos ver que para la variable b el contenido es la dirección 0003, y en la dirección 3 se encuentra la variable *b de tipo int en la que se guarda el contenido 3.

Podríamos aprovechar el espacio de memoria de a para guardar el contenido de b:

int a = 5;
int* b;
     *b = a; //*b y a son del mismo tipo por eso se puede realizar la instrucción de asignación.

La representación en la tabla de memoria sería:

Podemos ver que en este caso: a y *b están en la misma dirección de memoria.