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 enlazadas.
No
lineales
· Árboles.
· Grafos.
Las estructuras dinámicas de datos se
utilizan para almacenamiento de datos del mundo real, que están cambiando constantemente.
Un ejemplo típico, es la lista de pasajeros de una línea aérea. Si esta lista
se mantuviera en orden alfabético en un arreglo, sería necesario hacer espacio
para insertar un nuevo pasajero por orden alfabético. Esto requiere utilizar un
ciclo para copiar los datos del registro de cada pasajero al siguiente elemento
del arreglo. Si en su lugar se utilizará una estructura dinámica de datos, los
nuevos datos del pasajero se pueden insertar simplemente entre dos registros
existentes con un mínimo de esfuerzo.
Listas.
Una lista lineal es un conjunto de
elementos de un tipo dado que se encuentran ordenados y pueden variaren número.
Los elementos de una lista
lineal se almacenan normalmente contiguos en posiciones consecutivas de la memoria.
Las sucesivas entradas en una guía o directorio telefónico, por ejemplo, están
en líneas sucesivas, excepto en las partes superior e inferior de cada columna.
Una lista lineal se almacena en la memoria principal de una computadora en
posiciones sucesivas de memoria; cuando se almacenan en cinta magnética, los
elementos sucesivos se presentan en sucesión en la cinta. Esta sucesión se
denomina almacenamiento secuencial.
Las líneas así definidas se
denominan contiguas. Las operaciones que se pueden realizar con listas lineales
contiguas 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 sublistas.
7. Copiar una lista.
8. Borrar una lista.
Una lista lineal se almacena
en la memoria de la computadora en posiciones sucesivas o adyacentes y se procesa
como un arreglo unidimensional. En este caso, el acceso a cualquier elemento de
la lista y la adición de nuevos elementos es fácil; Sin embargo la inserción o
borrado requiere un desplazamiento de lugar de los elementos que le siguen y,
en consecuencia un diseño de algoritmo especifico.
Listas
encadenadas.
Una lista enlazada o encadenada es un
conjunto de elementos en los que cada elemento contiene la posición o dirección
del siguiente elemento de la lista. Cada elemento de la lista encadenada debe
tener al menos dos campos: Un campo que tiene el valor del elemento y un campo
(enlace o link) que contiene la posición del siguiente elemento, es decir, su
conexión, enlace o encadenamiento. Los elementos de una lista son enlazados por
medio de los campos enlaces.
Las listas encadenadas
tienen una terminología propia que se suele utilizar normalmente. Primero, los valores
se almacenan en un nodo.
Los componentes de un nodo
se llaman campos. Un nodo tiene al menos un campo de dato o valor y un enlace
(indicador o puntero) con el siguiente campo. El campo enlace apunta (proporciona
la dirección de) al siguiente nodo de la lista. El último nodo de la lista
encadenada, por convenio, se suele representar por un enlace con la palabra nil
(nulo), una barra inclinada, y en ocasiones, el símbolo eléctrico de tierra o
masa.
Una lista enlazada o
encadenada es una lista que se construye empleando apuntadores. Además, no tiene
un tamaño fijo, sino que puede crecer y decrecer durante la ejecución del
programa. Se constituyen como variables.
En las listas enlazadas no
es necesario que los elementos en la lista sean almacenados en posiciones
físicas adyacentes, ya que el apuntador indica dónde se encuentra el siguiente
elemento de la lista.
Por consiguiente, la
inserción y borrado no exigen desplazamiento como en el caso de las listas
contiguas.
Para eliminar un elemento de
una lista enlazada, solo es necesario cambiar el puntero del elemento anterior al
elemento siguiente del que deseamos eliminar. Para insertar un elemento en
determinada posición, solo necesitamos cambiar el apuntador de la posición
anterior a donde queremos insertar a nuestro nuevo elemento y este elemento
deberá direccionar el elemento al que anteriormente apuntaba el elemento que
quedo antes del nuevo elemento.
Una lista enlazada sin
ningún elemento se llama lista vacía. Su puntero inicial o de cabecera tiene el
valor nulo (nil).
Una lista enlazada se puede
definir por:
· El tipo de sus elementos:
campo de información (datos) y campo enlace (puntero).
· Un puntero de cabecera que
permite acceder al primer elemento de la lista.
· Un medio para detectar el último
elemento de la lista: puntero nulo (nil).
Las operaciones que hay que
realizar con una lista enlazada son:
1. Definir y crear los
nodos.
2. Definir la cabecera (o
inicio) de la lista.
3. Recorrer los nodos de una
lista enlazada.
4. Agregar un nodo a la
lista.
a. Al final.
b. Al Principio.
c. En el centro.
5. Eliminar un nodo de la
lista.
a. Al
final.
b. Al
Principio.
c. En el centro.
Pilas
Es una estructura de datos especial en
donde la inserción y el borrado de los nuevos elementos se realizan sólo por un
extremo que se denomina cima o tope. Esta estructura posee numerosas analogías
en la vida real, por ejemplo imagine 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.
Las operaciones que se
pueden realizar con una pila son:
ü PUSH
(pila, elemento): Introduce un elemento en la pila. También se le conoce como poner o meter.
ü POP
(pila): Elimina un elemento de la pila. También se le conoce como sacar o
quitar.
ü 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.
Un ejemplo sencillo de pilas
en PHP seria el siguiente:
<?php
/*insertar pila */
$pila=array("a","b");
echo"</br>antes
de insertar</br>";
print_r($pila);
array_push($pila,"c");
echo
"</br> </br>despues de insertar</br>";
print_r($pila);
?>
Esto mostraría lo siguiente:
Antes de insertar
Array ( [0] =>
a [1] => b )
Después de
insertar
Array ( [0] =>
a [1] => b [2] => c )
Colas
(filas)
Las colas o filas son otro tipo de
estructura lineal de datos, similares a las pilas, diferenciándose de ellas en el
modo de insertar ó eliminar elementos.
Una cola es una estructura
lineal de datos en la que las eliminaciones se realizan al principio de la
lista, y las inserciones se realizan por la fina de la misma. En las colas el
elemento que entró primero también sale primero, por ello se conocen como
estructuras FIFO. Así pues la diferencia con las pilas es solamente el modo de
entrada y salida de datos.
En la vida real se tienen
ejemplos numerosos de colas: la cola de un autobús, la cola de un cine, etc. En
todas ellas el primer elemento que llega es el primero que sale.
En informática existen
también numerosas aplicaciones de colas. Por ejemplo, en un sistema de tiempo compartido
suele haber un procesador central y una serie de periféricos compartidos:
discos, impresoras, etc. Los recursos se comparten por los diferentes usuarios
y se utiliza una cola para almacenar los programas o peticiones de los usuarios
que esperan su turno de ejecución.
Las colas se pueden
representar como estructuras dinámicas de datos o como arreglos.
Las operaciones que se
pueden realizar con una cola son:
1. Acceder al primer
elemento de la cola.
2. Añadir un elemento al
final de la cola.
3. Eliminar el primer
elemento de la cola.
4. Vaciar la cola.
5. Verificar el estado de la
cola.
Un ejemplo sencillo de cola en PHP seria el siguiente:
<?php
//array_shift
extraex al inicio
$cola=array("a","b","c","d");
echo"</br>antes
de desplazar</br>";
print_r($cola);
$atendiendo=array_shift($cola);
echo"</br></br>despues
de desplazar</br>";
print_r($cola);
echo"</br></br>atendiendo
$atendiendo</br>";
?>
Esto mostraría lo siguiente:
Antes de desplazar
Array ( [0] =>
a [1] => b [2] => c [3] => d )
despues de
desplazar
Array ( [0] =>
b [1] => c [2] => d )
Atendiendo a
