Estructura De Datos

ESTRUCTURAS DE DATOS DINAMICAS

Las estructuras dinámicas de datos son estructuras que crecen a medida que ejecuta un programa. Una estructura dinámica de datos es una colección de elementos – llamadas nodos - que son normalmente registros. Al contrario de un arreglo que contiene espacio para almacenar un número fijo de elementos, una estructura dinámica de datos se amplía y contrae durante la ejecución del programa, basada en los registros de almacenamiento de datos del programa.

Las estructuras dinámicas de datos se pueden dividir en dos grandes grupos:

Lineales

• Pilas.

• Colas.

• Listas.

No lineales

• Árboles.

• Grafos.

Las estructuras dinámicas de datos se utilizan para almacenamiento de datos del mundo real, que están cambiando constantemente.

ESTRUCTURAS DINAMICAS LINEALES

• LISTAS: Una lista lineal es un conjunto de elementos de un tipo dado que se encuentran ordenados y pueden variar en número. Los elementos de una lista lineal se almacenan normalmente contiguos en posiciones consecutivas de la memoria.

Las operaciones que se pueden realizar con listas lineales son:

1. Insertar, eliminar o localizar un elemento.

2. Determinar el tamaño de la lista (número de elementos).

3. Recorrer la lista para localizar un determinado elemento.

4. Clasificar los elementos de la lista en orden ascendente o descendente.

5. Unir dos o más listas en una sola.

6. Dividir una lista en varias sub-listas.

7. Copiar una lista.

8. Borrar una lista.

LISTAS ENCADENADAS: Una lista enlazada es un conjunto de elementos llamados nodos en los que cada uno de ellos contiene un dato y también la dirección del siguiente nodo. El primer elemento de la lista es la cabecera, que sólo contiene un puntero que señala el primer elemento de la lista. El último nodo de la lista apunta a NULL (nulo) porque no hay más nodos en la lista. Se usará el término NULL para designar el final de la lista.

Las listas encadenadas se presentan como alternativas a los almacenamientos contiguos y la misma se logra utilizando punteros o enlaces para referenciar a elementos de una lista lineal, los cuales almacenan la dirección del elemento sucesor que no necesariamente debe ser adyacente o contiguo físicamente. Esta metodología recibe el nombre de almacenamiento enlazado o encadenado.

Un elemento en una lista encadenada se denomina Nodo y contiene dos partes:

Información asociada al elemento. Será de tipo de datos que quiera almacenar en la lista.

Puntero: campo de enlace que contiene la dirección del próximo elemento de lista. Se utiliza para establecer el enlace con otro nodo de la lista.

LISTAS CIRCULARES: tienen como característica que el último elemento de la misma apunta al primero.

Las listas circulares presentan ventajas con respecto a las listas encadenadas:

1. Dado un nodo cualquiera, se puede recorrer toda la lista completa, en cambio en las listas encadenadas solo se las puede recorrer por completo partiendo de su primer nodo.

2. La concatenación y/o división de listas es más eficaz en esta estructura.

3. Se puede presentar un inconveniente en las listas circulares: se pueden producir bucles infinitos.

La forma de evitar este inconveniente es colocando un nodo especial llamado cabecera de la lista. Los nodos de cabecera pueden tener un valor especial en el campo INFORMACION que no es válido como datos de otros elementos, puede tener también un indicador o bandera que indique cuando es nodo de cabecera.

• PILAS: Es una estructura de datos especial en donde la inserción y el borrado de los nuevos elementos se realiza sólo por un extremo que se denomina cima o tope. Esta estructura posee numerosas analogías en la vida real, por ejemplo imaginarse una pila de platos.

Dado que las operaciones de insertar y eliminar se realizan por un solo extremo (el superior), los elementos solo pueden eliminarse en orden inverso al que se insertan en la pila. El último elemento que se pone en la pila es el primero en sacar; dado a esto a estas estructuras se les conoce con el nombre de LIFO (Last – In, Firts – Out: último en entrar, primero en salir).

Las operaciones que se pueden realizar con una pila son:

1. PUSH (pila, elemento): Introduce un elemento en la pila. También se le conoce como poner o meter.

2. POP (pila): Elimina un elemento de la pila. También se le conoce como sacar o quitar.

3. VACIA (pila): Función booleana que indica si la pila esta vacía o no.

Las pilas se pueden implementar por arreglos o bien por punteros siempre y cuando se respete el concepto antes mencionado.

Idealmente, una pila puede contener un número ilimitado de elementos y no producir nunca desbordamiento. En la práctica, sin embargo, el espacio de almacenamiento disponible es finito. La codificación de una pila requiere un cierto equilibrio, ya que si la longitud máxima es demasiado grande, se gasta mucha memoria, mientras que un valor pequeño de longitud máxima producirá desbordamientos frecuentes.

Las pilas no son estructuras de datos fundamentales de datos, es decir, no están definidos como tales en los lenguajes de programación, como lo están, por ejemplo los arreglos. Se pueden representar mediante el uso de:

a) Arreglos.

b) Listas Encadenadas.

Se utilizan ARREGLOS, por lo que se deberá definir el tamaño máximo de la pila ya además una variable

...