Listas Ligadas

Una lista ligada es un artificio de programación utilizado como estructura de datos, donde cada elemento de la lista es un conjunto de datos q apunta o esta enlazado al siguiente y/o anterior elemento de la lista. Si bien en un arreglo pueden agregarse, eliminarse, ordenarse (entre otras operaciones) los elementos de una lista a través de la re asignación dinámica de memoria, estas tareas son complejas y poco prácticas, por lo tanto los arreglos son utilizados generalmente sólo como estructuras de datos estáticas. Por el contrario las listas ligadas son estructuras dinámicas donde las operaciones sobre los elementos de la lista son más faciles de llevar acabo. En el tipo más básico de listas ligadas cada elemento apunta o contiene la dirección del siguiente elemento de la lista. El siguiente diagrama muestra una conceptualización de esta estructura de datos:



Esta es una lista unidireccional donde cada elemento de la misma apunta solo al siguiente elemento, el ultimo apunta a nada, ademas de que se debe tener un apuntador al primer elemento de la lista, siendo útil contar con un apuntador para almacenar algún elemento o item de la lista como actual o activo.

En C++ la implementación de una lista podría ser de la siguiente manera:

1. Para administrar la lista, como la creación de nodos, la eliminación de nodos, el ordenamiento, la destrucción de la lista, etc. puede llavarse a cabo mediante la definición de una clase y sus métodos.

2. Como elemento de la lista se puede definir una estructura, una clase, o una clase + una estructura, en este último paradigma la clase podría servirnos para llevar a acabo operaciones sobre los datos del nodo de la lista, mientras q la estrucutura se ocuparía sólo para almacenar los datos del nodo. A continuación se muestra la creación de una lista ligada fundamental en C++ donde usaremos una clase para la administración de la lista y una estructura para los datos del nodo, posteriormente se mencionaran otro tipo de listas ligadas.

Primero definimos la clase, en este ejemplo la llamaremos CLista y definiremos los métodos para crear un nodo, eliminar un nodo, limpiar la lista, ir al primer elemento, ir al último elemento, ir al siguiente elemento e ir a un elemento deseado. No olvidemos declarar antes la estructura para almacenar los datos del nodo, la llamaremos SDatos y posteriormente definiremos sus campos pero por el momento diremos que serán necesario un campo numérico para almacenar el ID secuencial del nodo y el apuntador de tipo SDato para almacenar la dirección del elemento contiguo o siguiente de la lista.

Bien, la declaración de la clase sería:

struct SDatos;

class CLista{
public:
SDatos *Nodo;  //Contendra, digamoslo asi, el nodo actual de la lista
void CreaNodo();
void EliminaNodo();
void Siguiente();
void Anterior();
void Primero();
void Ultimo();
void DameNodo(unsigned long);
void LimpiarLista();
unsigned long TotalNodos();  //Encapsulamos el numero total de nodos de tal forma que no se pueda fuera de la clase sobreescribir este dato solamente leer
CLista();
~CLista();
private:
unsigned long TotNod;
SDatos *Lista;  //Almacena el inicio o primer nodo de la lista
void Renumera();
};

Y la definición de cada uno de sus métodos:

CLista::CLista()
{
Lista = NULL;
Nodo = NULL;
TotNod = 0;
}

CLista::~CLista()
{
LimpiarLista();
}

void CLista::CreaNodo()
{
UltimoNodo();
if(Nodo)
{
Nodo->Sig = new SDatos;
Nodo = Nodo->Sig;
}
else
{ 

//Es el primer nodo de la lista
Lista = new SDatos;
Nodo = Lista;
}
Nodo->Sig = NULL;
TotNod++;
Nodo->No = TotNod;
}

void CLista::EliminaNodo()
{
SDatos *Act = Nodo;
if(Nodo)
{
if(Nodo==Lista)
{
Lista = Nodo->Sig;
Nodo = Lista;
}
else
{
Anterior();
Nodo->Sig = Act->Sig;
}
delete Act;
TotNod--;
Renumera();
}
}

void CLista::Siguiente()
{
if(Nodo)
Nodo = Nodo->Sig;
}

void CLista::Anterior()
{
unsigned long QueNodo = 0;
if(Lista)
if(Nodo != Lista)
{
if(!Nodo)
QueNodo = TotNod;
else
QueNodo = Nodo->No-1;
DameNodo(QueNodo);
}
}

void CLista::Primero()
{
Nodo = Lista;
}

void CLista::Ultimo()
{
DameNodo(TotNod);
}

void CLista::DameNodo(unsigned long ANo)
{
if(ANo<1)
ANo = 1;
if(ANo > TotNod)
ANo = TotNod;
Primero();
while(Nodo && Nodo->No != ANo)
Siguiente();
}

void CLista::LimpiarLista()
{
Primero();
while(Nodo)
{
Lista = Nodo->Sig;
delete Nodo;
Nodo = Lista;
}
TotNod = 0;
}

unsigned long CLista::TotalNodos()
{
return TotNod;
}

void CLista::Renumera()
{
SDatos *Act = Nodo;
unsigned long Cont = 0;
Primero();
while(Nodo)
{
Cont++;
Nodo->No = Cont;
Siguiente();
}
TotNod = Cont;
Nodo = Act;
}

La definición de la estructura para almacenar los datos puede contener los campos que sean necesarios para la aplicación, la lista ligada funcionara igual, pero al menos debe contener un apuntador de la misma estructura y un campo entero como ID del nodo.

struct SDatos{
.
.
.
unsigned long No;
SDatos *Sig;
SDatos
{
:
:
No = 0;
Sig = NULL;
}
};

Este es el tipo de lista ligada básica, entre otros tipos de lista podemos mencionar:

1. Lista bidireccional



2. Lista circular unidireccional



3. Lista circular bidireccional



Las listas bidireccionales requeriran un apuntador extra en la estructura de datos para apuntar al elemento adyacente anterior de la lista, aunque si bien hablamos de adyacencia de elementos de la lista esta es puramente lógica ya q en memoria los nodos podrían estar dispersos en cierta región de la misma. Este es un caso contrario a los arreglos cuyos elementos ocupan regiones adyacentes de memoria.

Usando Mensajes de Windows en Builder C++ 5

Los Mensajes de Windows son un mecanismo que se utiliza en el ambiente de este Sistema Operativo (SO) para comunicar aplicaciones, ventanas o para comunicar las aplicaciones con sus controles o viceversa o para comunicarse con el sistema. En este contexto podemos considerar que cada control de un formulario es una ventana, aunque en apariencia no lo sean. Podríamos decir que cada elemento en el SO Windows es una ventana y los mensajes son el mecanismo para comunicarse entre ellas. Viéndolo así, cada ventana tiene una función para procesar los mensajes que le son enviados, a esta función se le conoce como procedimiento de ventana y ya nos imaginamos que parámetros recibe: el mensaje que le esta siendo enviado (el identificador del mensaje, p. ej. WM_PAINT, valor constante de 2 bytes o 4 dígitos hexadecimales) y una serie de parámetros para hacer "algo". Son un par de parámetros enteros y la interpretación depende del tipo de mensaje, en estos parámetros se pueden empaquetar bits, podría ser un apuntador con la dirección en memoria de alguna estructura u objeto, el handler de otra ventana, etc., etc.

De igual forma, al enviar un mensaje a una ventana, salta a la vista que lo que se necesita es, el handler de la ventana destinataria, el ID del mensaje que se le enviará y el par de parámetros a ser procesados o interpretados.

El ID del mensaje es un número que va desde el 0x0000 al 0xFFFF, pero no todo el rango puede ser utilizado para los mensajes privados, de usuario, personalizados, etc., algunos de ellos están reservados para ser utilizados solamente por el sistema.

La teoría de los Mensajes de Windows es un poco más amplia, si te interesa saber más acerca de este tema y sobre los rangos disponibles para los ID de los mensajes sería conveniente que googles Windows Messages y consultes la ayuda en el MSDN de Microsoft. El objetivo es explicarte como puedes hacerlo en el environment de Builder C++.

Para definir mensajes personalizados para un control o formulario debemos derivar la clase del control o formulario e indicar entre las macros BEGIN_MESSAGE_MAP y END_MESSAGE_MAP por medio de la macro MESSAGE_HANDLER los mensajes que podrá procesar el control. Dentro de los parámetros que recibe la macro MESSAGE_HANDLER están el ID del mensaje y la función que se ejecutará o se encargará de "hacer ese algo" al recibir el mensaje. Tanto la definición de los nuevos mensajes como la declaración de las funciones que los procesarán deben escribirse en la sección private de la definición de la clase, sin olvidar que estás últimas deben precederse de la palabra clave de Builder C++ __fastcall.

Como ejemplo escribiremos las instrucciones para enviar un mensaje a un control Edit (TEdit) al presionar un botón, al recibir el mensaje el control Edit mostrará el texto "He recibido un mensaje de un botón.". Entonces comenzamos derivando la clase TEdit:

//---------------------------------------------------------------------------
//Derivamos la clase TEdit para manejar nuestros propios mensajes
class MiEdit : public TEdit
{
public:
MiEdit(TfrmMandaMensaje *);
protected:
BEGIN_MESSAGE_MAP
MESSAGE_HANDLER(WM_MSGEDIT1, TMessage, WMMsgEdit1);
END_MESSAGE_MAP(TEdit)
void __fastcall WMMsgEdit1(TMessage &Message);
};
//---------------------------------------------------------------------------

Al mismo tiempo estamos creando el control Edit en tiempo de ejecución por eso declaramos el constructor de MiEdit para recibir el apuntador del formulario y así enviarlo al constructor de la clase base TEdit. No debemos olvidar definir el ID del mensaje WM_MSGEDIT1, esto lo hacemos en la cabeza de nuestro *.h

#define WM_MSGEDIT1 (WM_APP + 1)

La constante WM_APP nos indica el inicio de los valores que podemos utilizar para los ID de nuestros mensajes personalizados (o de usuario o de aplicación). Bien, en nuestro archivo *.cpp definimos el constructor de nuestra clase hija MiEdit, así como las instrucciones de la función WMMsgEdit1 que procesará el mensaje.

//---------------------------------------------------------------------------
MiEdit::MiEdit(TfrmMandaMensaje *handler):TEdit(handler)
{
}
//---------------------------------------------------------------------------
void __fastcall MiEdit::WMMsgEdit1(TMessage &Message)
{
this->Text = "He recibido un mensaje de un botón.";
}
//---------------------------------------------------------------------------

La única función del constructor es la de enviar el apuntador del formulario TfrmMandaMensaje a la clase padre TEdit ya que en este formulario es donde colocaremos nuestro Edit. Ya sólo nos falta instanciar nuestra clase MiEdit, presentar el control en el formulario y postear o enviar el mensaje. En este ejemplo la instancia la hacemos dentro del formulario TfrmMandaMensaje declarando un apuntador a la clase MiEdit.

//---------------------------------------------------------------------------
class TfrmMandaMensaje : public TForm
{
__published: // IDE-managed Components
TButton *btnEnviaMensaje;
void __fastcall FormClose(TObject *Sender, TCloseAction &Action);
void __fastcall btnEnviaMensajeClick(TObject *Sender);
private: // User declarations
MiEdit *edtEdit;
public: // User declarations
__fastcall TfrmMandaMensaje(TComponent* Owner);
};

//---------------------------------------------------------------------------

La presentación del control edtEdit la hacemos dentro del constructor de nuestro formulario

//---------------------------------------------------------------------------
__fastcall TfrmMandaMensaje::TfrmMandaMensaje(TComponent* Owner)
: TForm(Owner)
{
unsigned offset = 20;

//Creamos el control tipo Edit
edtEdit = new MiEdit(this);
edtEdit->Parent = this;

//Cambiamos las propiedades del control tipo Edit
edtEdit->Left = btnEnviaMensaje->Left + btnEnviaMensaje->Width + offset;
edtEdit->Top = btnEnviaMensaje->Top;
edtEdit->Width = 3 * edtEdit->Width;
}
//---------------------------------------------------------------------------

y la liberación del control al cierre de nuestra aplicación.

//---------------------------------------------------------------------------
void __fastcall TfrmMandaMensaje::FormClose(TObject *Sender,
TCloseAction &Action)
{
//Liberamos la memoria ocupada por el control
if(edtEdit!=NULL)
{
delete edtEdit;
edtEdit = NULL;
}
}
//---------------------------------------------------------------------------

Finalmente en el evento click de nuestro botón btnEnviaMensaje posteamos el mensaje al control edtEdit usando la instrucción PostMessage la cual como parámetros requiere el handler del control, el ID del mensaje y dos parámetros: el primero WParam y el segundo LParam, ambos enteros.

//---------------------------------------------------------------------------
void __fastcall TfrmMandaMensaje::btnEnviaMensajeClick(TObject *Sender)
{
PostMessage(edtEdit->Handle, WM_MSGEDIT1, 25, 30);
}
//---------------------------------------------------------------------------

Listo, al presionar el botón el control edtEdit mostrará el mensaje "He recibido un mensaje de un botón.". Aunque este pudo haberse hecho fácilmente poniendo directamente el texto en la propiedad edtEdit->Text en lugar de postear el mensaje, el ejemplo sirve para ilustrar como puedes manejar tus propios mensajes en Builder. Lo mismo aplica para un formulario, en este caso al crear un formulario en tiempo de diseño ya estas derivando la clase TForm, así que sólo necesitas agregar las macros y la definición de unas cuantas funciones para definir tus propios mensajes y así comunicarte con tu aplicación desde otra aplicación si desde esa aplicación dispones de los handlers de tus formularios. Aunque aquí podrías encontrarte con problemas de memoria al tratar de compartirla entre aplicaciones si lo que envías como parámetros es el apuntador de un bloque de memoria de la aplicación remitente del mensaje.

Nota: Como comentario final deja explicarte lo sig., seguramente habrán notado que las funciones que procesan los mensajes reciben el parámetro por referencia Message y que este es del tipo TMessage, bueno esta clase es la estructura siguiente

struct TMessage{
     Cardinal Msg;
     union{
          struct{
               Word WParamLo;
               Word WParamHi;
               Word LParamLo;
               Word LParamHi;
               Word ResultLo;
               Word ResultHi;
          };
          struct{
               Word WParam;
               Word LParam;
               Word Result;
          };
     };
};

Así que ya sabes donde caen los parámetros que envías con la función PostMessage y como acceder a ellos en las funciones con las que procesas tus mensajes; puedes acceder tanto al ID del mensaje que estas procesando como a las partes altas y bajas de los parámetros WParam y LParam que envías.

En el siguiente tip, explicaré que son las listas ligadas y porque son muy útiles cuando desarrollas aplicaciones. Suerte y hasta la próxima.

Creación de controles en tiempo de ejecución en Builder C++

Crear un control en tiempo de ejecución en Builder C++ 5 es muy sencillo, lo que debemos hacer es lo siguiente:

1.- En la definición de la clase del formulario (que se deriva de la clase TForm y que en nuestro caso se llama TfrmCreaControl) en el apartado private (no published, el cual se deja para los controles creados en tiempo de diseño) se declara la variable objeto de la clase del control que deseamos crear (también puede ser en la sección public, todo depende del scope que queramos darle al control), en el ejemplo la variable se llama edtEdit y es una variable del tipo TEdit, esta variable debe ser un apuntador ya que la creación de los controles es de forma dinámica.

//---------------------------------------------------------------------------
class TfrmCreaControl : public TForm
{
__published: // IDE-managed Components
TButton *btnCreaEdit;
void __fastcall FormClose(TObject *Sender, TCloseAction &Action);
void __fastcall btnCreaEditClick(TObject *Sender);
private: // User declarations
TEdit *edtEdit;
public: // User declarations
__fastcall TfrmCreaControl(TComponent* Owner);
};
//---------------------------------------------------------------------------

2.- En el evento Click del boton btnCreaEdit asignamos memoria al apuntador edtEdit y en la llamada al constructor enviamos el apuntador del objeto formulario TfrmCreaControl usando la palabra clave this. Para poder visualizar el control tenemos que establecer su propiedad Parent, es decir el padre del control, en este caso el formulario TfrmCreaControl. Finalmente si lo deseamos o requerimos cambiamos las propiedades por default del control recién creado, por default el control aparece en la parte superior izquierda del formulario (propiedades edtEdit->Top = edtEdit->Left = 0).

La secuencia no importa, puedes primero cambiar las propiedades del control y después establecer la propiedad Parent o viceversa.

//---------------------------------------------------------------------------
void __fastcall TfrmCreaControl::btnCreaEditClick(TObject *Sender)
{
unsigned offset = 25;

if(edtEdit!=NULL)
{
edtEdit = new TEdit(this);
edtEdit->Parent = this;
edtEdit->Left = btnCreaEdit->Left + btnCreaEdit->Width + offset;
edtEdit->Top = btnCreaEdit->Top;
edtEdit->Text = "Hello World!";
}
}
//---------------------------------------------------------------------------

En la imagen se muestra el formulario en tiempo de diseño, el formulario en tiempo de ejecución después de haber pulsado el botón, las propiedades del botón y las propiedades del formulario.

Finalmente no debemos olvidarnos de liberar la memoria previamente asignada de forma dinámica al apuntador edtEdit, esto lo hacemos al cerrar el formulario. Tal vez no sea necesario pues se supone que al cerrar nuestra aplicación esta libera toda la memoria asignada durante su ejecución, sin embargo lo hacemos por precaución, no esta de más agregar esas líneas.

//---------------------------------------------------------------------------
void __fastcall TfrmCreaControl::FormClose(TObject *Sender,
TCloseAction &Action)
{
delete edtEdit;
}
//---------------------------------------------------------------------------

Notas: Como comentario final déjame decirte que el apuntador edtEdit lo puedes declarar en cualquier parte del código, solamente hay que tener cuidado con su scope o alcance, ya que si lo declaras, por ejemplo, en una función, solamente dentro de esa función podrás acceder y visualizar el control Edit, ya que una vez que termine la ejecución de la función el control desaparece. Te invito a experimentar con diferentes formas de crear y con diferentes controles.

En el próximo tip explicaré como mandar mensajes de Windows (los cuales sirven para comunicar aplicaciones o para comunicar aplicaciones con sus controles o el sistema con las aplicaciones en el ambiente Windows) a un control o a un formulario en el environment de Builder C++ 5.