ESTRUCTURA DE DATOS

ESTRUCTURAS DINÁMICAS DE DATOS
Introducción
Una de las aplicaciones más interesantes y potentes de la memoria dinámica y los punteros son las
estructuras dinámicas de datos. Las estructuras básicas disponibles en C y C++ tienen una
importante limitación: no pueden cambiar de tamaño durante la ejecución. Los arreglos están
compuestos por un determinado número de elementos, número que sedecide en la fase de diseño,
antes de que el programa ejecutable sea creado.
En muchas ocasiones se necesitan estructuras que puedan cambiar de tamaño durante la ejecución
del programa. Por supuesto, podemos hacer 'arrays' dinámicos, pero una vez creados, tu tamaño
también será fijo, y para hacer que crezcan o diminuyan de tamaño, deberemos reconstruirlas desde
el principio.
Las estructurasdinámicas nos permiten crear estructuras de datos que se adapten a las necesidades
reales a las que suelen enfrentarse nuestros programas. Pero no sólo eso, como veremos, también
nos permitirán crear estructuras de datos muy flexibles, ya sea en cuanto al orden, la estructura
interna o las relaciones entre los elementos que las componen.
Las estructuras de datos están compuestas de otras pequeñasestructuras a las que llamaremos nodos
o elementos, que agrupan los datos con los que trabajará nuestro programa y además uno o más
punteros autoreferenciales, es decir, punteros a objetos del mismo tipo nodo.
Una estructura básica de un nodo para crear listas de datos seria:
struct nodo {
int dato;
struct nodo *otronodo;
};
El campo "otronodo" puede apuntar a un objeto del tipo nodo. Deeste modo, cada nodo puede
usarse como un ladrillo para construir listas de datos, y cada uno mantendrá ciertas relaciones con
otros nodos.
Para acceder a un nodo de la estructura sólo necesitaremos un puntero a un nodo.
Durante el presente curso usaremos gráficos para mostrar la estructura de las estructuras de datos
dinámicas. El nodo anterior se representará asi:
Las estructuras dinámicasson una implementación de TDAs o TADs (Tipos Abstractos de Datos).
En estos tipos el interés se centra más en la estructura de los datos que en el tipo concreto de
información que almacenan.
Dependiendo del número de punteros y de las relaciones entre nodos, podemos distinguir varios
tipos de estructuras dinámicas. Enumeraremos ahora sólo de los tipos básicos:
Listas abiertas: cada elementosólo dispone de un puntero, que apuntará al siguiente elemento de la
lista o valdrá NULL si es el último elemento.
Pilas: son un tipo especial de lista, conocidas como listas LIFO (Last In, First Out: el último en
entrar es el primero en salir). Los elementos se "amontonan" o apilan, de modo que sólo el elemento
que está encima de la pila puede ser leído, y sólo pueden añadirse elementos encima dela pila.
Colas: otro tipo de listas, conocidas como listas FIFO (First In, First Out: El primero en entrar es el
primero en salir). Los elementos se almacenan en fila, pero sólo pueden añadirse por un extremo y
leerse por el otro.
Listas circulares: o listas cerradas, son parecidas a las listas abiertas, pero el último elemento apunta
al primero. De hecho, en las listas circulares no puedehablarse de "primero" ni de "último".
Cualquier nodo puede ser el nodo de entrada y salida.

Listas doblemente enlazadas: cada elemento dispone de dos punteros, uno a punta al siguiente
elemento y el otro al elemento anterior. Al contrario que las listas abiertas anteriores, estas listas
pueden recorrerse en los dos sentidos.
Arboles: cada elemento dispone de dos o más punteros, pero lasreferencias nunca son a elementos
anteriores, de modo que la estructura se ramifica y crece igual que un árbol.
Arboles binarios: son árboles donde cada nodo sólo puede apuntar a dos nodos.
Arboles binarios de búsqueda (ABB): son árboles binarios ordenados. Desde cada nodo todos los
nodos de una rama serán mayores, según la norma que se haya seguido para ordenar el árbol, y los
de la otra...