Abstracción de estructuras de datos.

El estudio de las estructuras de datos implica, en general, dos propósitos complementarios:

1. Identificar y desarrollar tanto entidades como operaciones útiles relacionadas con dichas entidades. En este rubro es preciso determinar el tipo de problemas que se solucionan utilizando tales entidades y operaciones.
2. Determinar representaciones para dichas entidades abstractas, así como implementar las operaciones abstractas en representaciones concretas.

   El primero de estos dos propósitos considera a un tipo de datos de alto nivel como un instrumento que se usa para solucionar problemas. Este propósito está también en estrecha relación con la definición de tipos de datos abstractos (ADT).

   El segundo propósito considera la implementación del tipo de dato o ADT como un problema que se va a resolver utilizando objetos o elementos existentes por medio de la herencia (relación es-un (is-a)) o la composición (relación tiene-un (has-a)).

 

    Como ya se ha mencionado, en ocasiones ninguna implementación tanto de hardware como de software puede modelar en su totalidad un concepto matemático (un tipo de dato entero o real por ejemplo), por lo que es importante conocer las limitaciones de una implementación particular, ya que una consideración fundamental de cualquier implementación es no sólo su efectividad sino también su eficiencia.

Clases autorreferidas.

   La implementación de las estructuras de datos que se desarrollarán en el blog estarán basadas en un concepto muy importante: la autorreferencia.

   En el contexto de la orientación a objetos, la autorreferencia es la capacidad que tienen los objetos de una clase de almacenar explícitamente una referencia a objetos de su misma clase, es decir, a objetos de su mismo tipo.

   Considere el Ejemplo Nodo Java (Ejemplo nodo C++), el cual muestra una clase autorreferida con dos atributos:

1. dato: el atributo que representa el elemento a almacenar en el nodo.
2. siguiente: el cual es una referencia a un objeto cuya clase es la misma que lo define (Nodo), y por lo tanto, es una autorreferencia.

   En el área de las estructuras de datos, un nodo es la unidad mínima de almacenamiento dentro de la estructura de datos, y puede ser tan simple o elaborado como se requiera.

   Para el caso del Ejemplo Nodo, el nodo únicamente almacena enteros primitivos (int), pero como se discurrirá más adelante, es posible representar y almacenar entidades más elaboradas que un número entero.

   Considere la creación de un objeto nodo instanciado de la clase Nodo (Java) y nodo (C++):

Nodo nodo = new Nodo(1974);    // Java: declaración y definición de "nodo"

Nodo nodo(1974);    // C++: declaración y definición de "nodo"

y su correspondiente representación mostrada en la siguiente figura:

Representación de un objeto de la clase Nodo (Ejemplo Nodo).

   En la figura anterior puede apreciarse que un objeto es en realidad una referencia a una instancia (entidad) con características definidas por la clase de la que deriva, que para el caso específico del Ejemplo en turno están dadas por los atributos dato y siguiente.

 

    En este punto quizá valga le pena recordar algo sutil pero sumamente importante: la diferencia entre declaración y definición. Para no extenderse innecesariamente de más, se tomará el caso de Java:

 

Nodo nodo;    // Declaración de "nodo" (cuadro izquierdo en la representación gráfica)

.

.

.

nodo = new Nodo(1974);    // Definición de "nodo" (objeto con dos campos en la representación gráfica)

 

es habitual, pero no necesario, que la declaración y la definición del objeto vayan juntas (como se hizo al mostrar el ejemplo de instanciación líneas arriba). Sin embargo, también es posible declarar las variables que harán referencia a los objetos, para posteriormente crear explícitamente los objetos (new) mismos que serán referidos por la variable a la que se asignan (como lo hacen los constructores). En Java no existe el concepto explícito de referencia (apuntador); sin embargo una variable cuyo tipo es una clase, en realidad es una referencia al inicio de la memoria de la instancia de una clase, por lo que cuando hablamos de un "objeto", nos valemos de una abstracción que se refiere a la instancia propiamente dicha y a la variable que la refiere.

   Ahora bien, observe la relación entre el Ejemplo Nodo y la figura anterior de su representación, y note cómo en el constructor el objeto es inicializado con el valor recibido como argumento, y con null (nullptr) para la referencia siguiente, lo cual ha sido representado en la figura anterior con una diagonal (\) para enfatizar que la referencia representada por el atributo siguiente no hace referencia inicialmente a ningún otro objeto. Observe también que la clase o tipo del objeto nodo es la misma que la del atributo siguiente, lo cual constituye la autorreferencia que es el concepto que se desea ilustrar. Asegúrese de comprender lo anterior antes de continuar.

Implementación.

   Con base en lo descrito en la sección anterior, es posible decir que las estructuras de datos consisten, de manera general, en un conjunto de nodos ordenados en una secuencia lógica como la que se muestra en la siguiente figura:

Secuencia de nodos formados con objetos autorreferidos.

   Las estructuras de datos estudiadas en las entradas siguientes tendrán en general la forma o estructura representada por esta figura.

 

   Por otro lado, el mecanismo utilizado para la inserción y la eliminación de nodos en la estructura de datos, estará en función directa de las reglas especificadas por la definición de la estructura de datos.

   Finalmente, la especificación de las características de la estructura de datos se implementarán a través de sus atributos, mientras que la especificación de las reglas de operación o de comportamiento serán implementadas por medio de sus métodos.