Introducción a las estructuras de datos

Como ya hemos visto en nuestro curso de programación las estructuras de datos sirven para almacenar los datos con los que trabajarán nuestros algoritmos. Podemos decir que la combinación de nuestros algoritmos (las instrucciones) y estas estructuras son las que dan forma a nuestros programas aunque también deberíamos considerar la documentación de nuestro proyecto como parte del mismo, pero quizás en proyectos de un alcance tan limitado podríamos excluirlo.

Clasificación de las estructuras

Aunque existe infinidad de clasificaciones para nuestras estructuras vamos a basarnos en la forma que estas estructuras organizan los datos, es decir, como están realmente ordenados (podemos incluso hablar de cómo se colocan) los datos o elementos dentro de la estructura atendiendo a como accederíamos a ellos pero también como los veríamos visualmente. La clasificación que sigue es la siguiente:

Datos ordenados de forma consecutiva o de forma lineal

Destacamos sobre todo las listas enlazadas, las pilas (stack), las colas (queue), los vectores… e infinidad de nombres para los mismo; una lista de elementos ordenados de forma lineal, donde los elementos están ordenados consecutivamente. Una representación gráfica sería:

Aunque sería más correcto definirlo como:

Ya que en realidad lo que tenemos es una lista en la que los elementos se van enlazando uno con otros, esto que para acceder al 6 es necesario visitar previamente el 10 y 2. Una consideración importante que debemos tener es que cuando hablamos de pilas, colas, vectores… no estamos refiriendo a estructuras que tengan los datos ordenados de forma diferente, si por su comportamiento (definido por su métodos) es que el que define el acceso a esos datos; y cuando hablamos de acceso a los datos son las posibilidades o el comportamiento que tendrá por ejemplo el método añadir en una cola o en una pila. Este tipo de estructuras son muy triviales pero son realmente utilizadas, son muy sencillas de implementar.

Datos ordenados en red

Cuando hablamos de estructuras de datos en red estamos hablando de grafos. Los grafos son estructuras definidas por arcos y nodos siendo los nodos un contenedor para un dato y los arcos la unión entre los diferentes nodos. Por ejemplo un grafo dirigido podría ser el siguiente:

Datos ordenados de forma jerárquica

Las estructuras de datos jerárquicas son los árboles. Dentro de la familia de los árboles tenemos montículos, árboles binarios, árboles B… Lo característico de los árboles es que en realidad son grafos no dirigidos en los que se tiene una raíz la cual tiene una serie de descendientes o hijos (el número de descendientes y la forma que están ordenados son los que caracterizan cada tipo de árbol) ordenados de forma jerárquica.

Datos ordenados en diccionarios

Las estructuras de diccionarios están representadas por tablas Hash. Estas tablas se basan en disponer para cada elemento una clave haciendo que el tiempo de acceso a ese elemento sea relativamente bajo comparado con otras estructuras. Las tablas Hash pueden ser de dos tipos: abiertas o cerradas.

• Tablas hash cerradas: cada celda de la estructura tiene únicamente un dato.
• Tablas hash abiertas: cada celda de la estructura tiene una estructura (cualquiera: listas, árboles, otra tabla...) que podrá una serie de elementos.

En los siguientes artículos iremos estudiando los siguientes tipos de estructura. Lo primero que haremos será explicar como se añaden los datos, como se borran y como se buscan, las operaciones básicas que debe presentar cualquier estructura. Una vez explicados los conceptos teóricos pasaremos a implementarlos con el lenguaje C#; primero programaremos una prueba simple y luego pasaremos a implementar sus métodos básicos; realizaremos una segunda prueba y explicaremos e implementaremos otro métodos no tan triviales (como por ejemplo en los grafos en algoritmo de Prim) siguiendo el mismo esquema, prueba unitaria y luego su implementación.