Pilas

ESTRUCTURA DE DATOS

INTRODUCCIÓN

Una de las aplicaciones más interesantes y potentes de la memoria dinámica y de los punteros son, sin duda, las estructuras dinámicas de datos. Las estructuras básicas disponibles en C++ (structs y arrays) tienen una importante limitación: no pueden cambiar de tamaño durante la ejecución.
Las estructuras dinámicas nos permiten crear estructuras de datosque se adapten a las necesidades reales a las que suelen enfrentarse nuestros programas. Pero no sólo eso, también nos permitirá 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ñas estructuras a las que llamaremos nodos o elementos, queagrupan los datos con los que trabajará nuestro programa y además uno o más punteros autorreferenciales, es decir, punteros a objetos del mismo tipo nodo.

Marco teórico
La base del C proviene del BCPL, escrito por Martin Richards, y del B escrito por Ken Thompson en 1970 para el primer sistema UNIX en un DEC PDP-7. Estos son lenguajes sin tipos, al contrario que el C que proporcionavarios tipos de datos. Los tipos que ofrece son caracteres, números enteros y en coma flotante, de varios tamaños. Además se pueden crear tipos derivados mediante la utilización de punteros, vectores, registros y uniones. El primer compilador de C fue escrito por Dennis Ritchie para un DEC PDP-11 y escribió el propio sistema operativo en C.
Originariamente, el manual de referencia del lenguaje para el granpúblico fue el libro de Kernighan y Ritchie, escrito en 1977. Es un libro que explica y justifica totalmente el desarrollo de aplicaciones en C, aunque en él se utilizaban construcciones, en la definición de funciones, que podían provocar confusión y errores de programación que no eran detectados por el compilador. Como los tiempos cambian y las necesidades también, en 1983 ANSI establece elcomité X3J11 para que desarrolle una definición moderna y comprensible del C. El estándar está basado en el manual de referencia original de 1972 y se desarrolla con el mismo espíritu de sus creadores originales. La primera versión de estándar se publicó en 1988 y actualmente todos los compiladores utilizan la nueva definición. Una aportación muy importante de ANSI consiste en la definición de unconjunto de librerías que acompañan al compilador y de las funciones contenidas en ellas.

Listas abiertas
Definición
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 y 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.
El nodo típico para construir listas tiene esta forma:-------------------------------------------------
struct nodo \{
-------------------------------------------------
int dato;
-------------------------------------------------
struct nodo *siguiente;
-------------------------------------------------
};
En el ejemplo, cada elemento de la lista sólo contiene un dato de tipo entero, pero en la práctica no hay límite en cuanto a la complejidad de los datos a almacenar.
Declaracionesde tipos para manejar listas en C

Normalmente se definen varios tipos que facilitan el manejo de las listas, en C, la declaración de tipos puede tener una forma parecida a esta:
-------------------------------------------------
typedefstruct _nodo \{
-------------------------------------------------
intdato;
-------------------------------------------------
struct _nodo *siguiente;...