Informatica

REPÚBLICA BOLIVARIANA DE VENEZUELA
MINISTERIO DEL PODER POPULAR PARA LA DEFENSA
UNIVERSIDAD NACIONAL EXPERIMENTAL POLITÈCNICA DE LA FUERZA ARMADA NACIONAL
(UNEFA)
NÚCLEO - VARGAS

Profesor: Alumnos:

Ochoa Denis





Catia la Mar, Noviembre de 2012

INTRODUCCION

Una de las aplicacionesmá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 y C++ (structs y arrays) tienen una importante limitación: no pueden cambiar de tamaño durante la ejecución. Los arrays están compuestos por un determinado número de elementos, número que se decide en la fase de diseño, antes de que elprograma ejecutable sea creado.

En muchas ocasiones se necesitan estructuras que puedan cambiar de tamaño durante la ejecución del programa. Por supuesto, podemos crear arrays dinámicos, pero una vez creados, tu tamaño también será fijo, y para hacer que crezcan o disminuyan de tamaño, deberemos reconstruirlos desde el principio.
Las estructuras dinámicas nos permiten crear estructuras dedatos 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á 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 oelementos, que agrupan los datos con los que trabajará nuestro programa y además uno o más punteros auto-referenciales, es decir, punteros a objetos del mismo tipo nodo.

En la presente investigación, mostraremos algunas de las diferentes Estructuras Dinámicas de Información que existen; como lo son las Listas (abiertas, circulares y doblemente cruzadas), Pilas, Colas y Arboles.

LISTAS ABIERTASLa 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: el primero. Normalmente diremos que nuestra lista es un puntero a ese primer nodo y llamaremos a ese nodo la cabeza de lalista. 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:

OPERACIONES BÁSICAS CON LISTAS

Con las listas tendremos un pequeño repertorio de operaciones básicas que se pueden realizar:

* Añadir o insertarelementos.
* Buscar o localizar elementos.
* Borrar elementos.
* Moverse a través de una lista, anterior, siguiente, primero.

Cada una de estas operaciones tendrá varios casos especiales, por ejemplo, no será lo mismo insertar un nodo en una lista vacía, ó al principio de una lista no vacía, o la final, o en una posición intermedia.

LISTAS CIRCULARES
Una lista circular es una listalineal en la que el último nodo a punta al primero.
Las listas circulares evitan excepciones en la operaciones que se realicen sobre ellas. No existen casos especiales, cada nodo siempre tiene uno anterior y uno siguiente.
En algunas listas circulares se añade un nodo especial de cabecera, de ese modo se evita la única excepción posible, la de que la lista esté vacía.
El nodo típico es elmismo que para construir listas abiertas:

OPERACIONES BÁSICAS CON LISTAS CIRCULARES

A todos los efectos, las listas circulares son como las listas abiertas en cuanto a las operaciones que se pueden realizar sobre ellas:

* Añadir o insertar elementos.
* Buscar o localizar elementos.
* Borrar elementos.
* Moverse a través de la lista, siguiente.

Cada una de estas...