Estructura De Datos

REPASO DE ESTRUCTURA DE DATOS
Las estructuras dinámicas son 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ólolos tipos básicos:
Listas abiertas: cada elemento só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 pilapuede ser leído, y sólo pueden añadirse elementos encima de la 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 alprimero. De hecho, en las listas circulares no puede hablarse 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: cadaelemento dispone de dos o más punteros, pero las referencias 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 hayaseguido para ordenar el árbol, y los de la otra rama serán menores.
Arboles AVL: son también árboles de búsqueda, pero su estructura está más optimizada para reducir los tiempos de búsqueda.
Arboles B: son estructuras más complejas, aunque también se trata de árboles de búsqueda, están mucho más optimizados que los anteriores.
Tablas HASH: son estructuras auxiliares para ordenar listas.
Grafos:es el siguiente nivel de complejidad, podemos considerar estas estructuras como árboles no jerarquizados.

LISTAS
La forma más simple de estructura dinámica es la lista abierta. En esta forma los nodos se organizan de modo que cada uno apunta al siguiente, y el último no apunta a nada, es decir, el puntero del nodo siguiente vale NULL.
En las listas abiertas existe un nodo especial: elprimero. Normalmente diremos que nuestra lista es un puntero a ese primer nodo o llamaremos a ese nodo la cabeza de la lista. Eso es porque mediante ese único puntero podemos acceder a toda la lista.
Cuando el puntero que usamos para acceder a la lista vale NULL, diremos que la lista está vacía.
OPERACIONES CON LISTAS
Con las listas tendremos un pequeño repertorio de operaciones básicas que sepueden realizar:
Añadir o insertar elementos.
Buscar o localizar elementos.
Borrar elementos.
Moverse a través de una lista, anterior, siguiente, primero.

PILA
Una pila es un tipo especial de lista abierta en la que sólo se pueden insertar y eliminar nodos en uno de los extremos de la lista. Estas operaciones se conocen como “push” y “pop”, respectivamente “empujar” y “tirar”. Además,las escrituras de datos siempre son inserciones de nodos, y las lecturas siempre eliminan el nodo leído.
Estas características implican un comportamiento de lista LIFO (Last In First Out), el último en entrar es el primero en salir.
El símil del que deriva el nombre de la estructura es una pila de platos. Sólo es posible añadir platos en la parte superior de la pila, y sólo pueden tomarse del...