Nombre Password [ Regístrate ]

Introducción

 

* Introducción
* ¿Qué es una estructura de datos?
* Tipos Abstractos de Datos
* Cómo leer estos temas.

 

Introducción

Para procesar información en un computador es necesario hacer una abstracción de los datos que tomamos del mundo real -abstracción en el sentido de que se ignoran algunas propiedades de los objetos reales, es decir, se simplifican-. Se hace una selección de los datos más representativos de la realidad a partir de los cuales pueda trabajar el computador para obtener unos resultados.

Cualquier lenguaje suministra una serie de tipos de datos simples, como son los números enteros, caracteres, números reales. En realidad suministra un subconjunto de éstos, pues la memoria del ordenador es finita. Los punteros (si los tiene) son también un tipo de datos. El tamaño de todos los tipos de datos depende de la máquina y del compilador sobre los que se trabaja.

En principio, conocer la representación interna de estos tipos de datos no es necesaria para realizar un programa, pero sí puede afectar en algunos casos al rendimiento.

 

¿Qué es una estructura de datos?

Se trata de un conjunto de variables de un determinado tipo agrupadas y organizadas de alguna manera para representar un comportamiento. Lo que se pretende con las estructuras de datos es facilitar un esquema lógico para manipular los datos en función del problema que haya que tratar y el algoritmo para resolverlo. En algunos casos la dificultad para resolver un problema radica en escoger la estructura de datos adecuada. Y, en general, la elección del algoritmo y de las estructuras de datos que manipulará estarán muy relacionadas.

Según su comportamiento durante la ejecución del programa distinguimos estructuras de datos:

- Estáticas: su tamaño en memoria es fijo. Ejemplo: arrays.
- Dinámicas: su tamaño en memoria es variable. Ejemplo: listas enlazadas con punteros, ficheros, etc.

Las estructuras de datos que trataremos aquí son los arrays, las pilas y las colas, los árboles, y algunas variantes de estas estructuras. La tabla que se encuentra al comienzo de esta página agrupa todas las estructuras de datos que emplearán los algoritmos explicados en esta web.

 

Tipos Abstractos de Datos

Los tipos abstractos de datos (TAD) permiten describir una estructura de datos en función de las operaciones que pueden efectuar, dejando a un lado su implementación.

Los TAD mezclan estructuras de datos junto a una serie de operaciones de manipulación. Incluyen una especificación, que es lo que verá el usuario, y una implementación (algoritmos de operaciones sobre las estructuras de datos y su representación en un lenguaje de programación), que el usuario no tiene necesariamente que conocer para manipular correctamente los tipos abstractos de datos.

Se caracterizan por el encapsulamiento. Es como una caja negra que funciona simplemente conectándole unos cables. Esto permite aumentar la complejidad de los programas pero manteniendo una claridad suficiente que no desborde a los desarrolladores. Además, en caso de que algo falle será más fácil determinar si lo que falla es la caja negra o son los cables.

Por último, indicar que un TAD puede definir a otro TAD. Por ejemplo, en próximos apartados se indicará como construir pilas, colas y árboles a partir de arrays y listas enlazadas. De hecho, las listas enlazadas también pueden construirse a partir de arrays y viceversa.

 

Como leer estos temas

Se recomienda tratar en profundidad los temas de estructuras de datos antes de entrar de lleno en los algoritmos, si bien es muy recomendable al menos leer la introducción a los algoritmos y algunos de los temas que suelen ser más conocidos, tales como la ordenación y la búsqueda.

En primer lugar es fundamental el conocimiento de la recursividad, inherente a muchas estructuras de datos y algoritmos. Es este por tanto el primer tema que hay tratar. Posteriormente conviene estudiar los temas de arrays y listas enlazadas, puesto que son básicos para implementar el resto de estructuras de datos. Los temas de pilas y colas son fundamentales, y mucho más sencillas de entender y aplicar que los temas restantes. Como temas avanzados (y no por ello menos importantes, además de que requieren el conocimiento de los temas anteriores) figuran los grafos, si bien en la sección de estructuras de datos se estudiarán sólo sus implementaciones y recorridos, los árboles y los montículos, una implementación especial de árbol. De manera independiente puede leerse el tema de conjuntos.

Asimismo, suele ocurrir que unos temas entran en el terreno de otros, y por lo tanto serán habituales las referencias a otros temas, ya sean a estructuras de datos y a algoritmos.

 

Nota: Además de las estructuras de datos que se estudian aquí existe otra que es el fichero; dicha estructura no se estudiará en estas páginas. Sólo se utilizarán ficheros en algunos casos -únicamente de tipo ASCII-, y exclusivamente para facilitar la introducción de los datos que se requieren para resolver un problema y también para mostrar los datos producidos por el algoritmo que procesa esos datos.

 


© (2001-2008) ALGORITMIA.NET - Política de privacidad