Capítulo 12 Estructuras Dinámicas Lineales de Datos (Joyanes)

CAPÍTULO 12 Estructuras dinámicas lineales de datos (pilas, colas y listas enlazadas) 12.1. Introducción a las estructuras de datos 12.8. Colas 12.2. Listas...

CAPÍTULO 12 Estructuras dinámicas lineales de datos (pilas, colas y listas enlazadas) 12.1. Introducción a las estructuras de datos 12.8. Colas 12.2. Listas 12.9. Doble cola 12.3. Listas enlazadas ACTIVIDADES DE PROGRAMACIÓN RESUELTAS 12.4. Procesamiento de listas enlazadas CONCEPTOS CLAVE 12.5. Listas circulares RESUMEN 12.6. Listas doblemente enlazadas EJERCICIOS 12.7. Pilas INTRODUCCIÓN Los datos estudiados hasta ahora se denominan está- un método para adquirir posiciones adicionales de ticos. Ello es debido a que las variables son direcciones memoria a medida que se necesiten durante la ejecu- simbólicas de posiciones de memoria; esta relación ción del programa y liberarlas cuando no se necesitan. entre nombres de variables y posiciones de memoria Las variables que se crean y están disponibles durante es una relación estática que se establece por la decla- la ejecución de un programa se llaman variables diná- ración de las variables de una unidad de programa y micas. Estas variables se representan con un tipo de que se establece durante la ejecución de esa unidad. datos conocido como puntero. Las variables dinámicas Aunque el contenido de una posición de memoria se utilizan para crear estructuras dinámicas de datos asociada con una variable puede cambiar durante la que se pueden ampliar y comprimir a medida que se ejecución, es decir, el valor de la variable puede cam- requieran durante la ejecución del programa. Una es- biar, las variables por sí mismas no se pueden crear ni tructura de datos dinámica es una colección de ele- destruir durante la ejecución. En consecuencia, las va- mentos denominados nodos de la estructura —nor- riables consideradas hasta este punto se denominan malmente de tipo registro— que son enlazados juntos. variables estáticas. Las estructuras dinámicas de datos se clasifican en En algunas ocasiones, sin embargo, no se conoce lineales y no lineales. El estudio de las estructuras li- por adelantado cuánta memoria se requerirá para un neales, listas, pilas y colas, es el objetivo de este capí- programa. En esos casos es conveniente disponer de tulo. 430 Fundamentos de programación 12.1. INTRODUCCIÓN A LAS ESTRUCTURAS DE DATOS En capítulos anteriores se ha introducido a las estructuras de datos, definiendo tipos y estructuras de datos primitivos, tales como enteros, real y carácter, utilizados para construir tipos más complicados como arrays y registros, deno- minados estructuras de datos compuestos. Tienen una estructura porque sus datos están relacionados entre sí. Las estructuras compuestas, tales como arrays y registros, están soportadas en la mayoría de los lenguajes de programa- ción, debido a que son necesarias en casi todas las aplicaciones. La potencia y flexibilidad de un lenguaje está directamente relacionada con las estructuras de datos que posee. La programación de algoritmos complicados puede resultar muy difícil en un lenguaje con estructuras de datos limi- tados, caso de FORTRAN y COBOL. En ese caso es conveniente pensar en la implementación con lenguajes que soporten punteros como C y C++ o bien que no soporten pero tengan recolección de basura como Java o C#, o bien recurrir, al menos en el período de formación, al clásico Pascal. Cuando una aplicación particular requiere una estructura de datos no soportada por el lenguaje, se hace necesaria una labor de programación para representarla. Se dice que necesitamos implementar la estructura de datos. Esto na- turalmente significa más trabajo para el programador. Si la programación no se hace bien, se puede malgastar tiem- po de programación y —naturalmente— de computadora. Por ejemplo, supongamos que tenemos un lenguaje como Pascal que permite arrays de una dimensión de números enteros y reales, pero no arrays multidimensionales. Para implementar una tabla con cinco filas y diez columnas podemos utilizar type array[0..10] of real: FILA; var FILA: FILA1, FILA2, FILA3, FILA4, FILA5; La llamada al elemento de la tercera fila y sexta columna se realizará con la instrucción FILA3 Un método muy eficaz es diseñar procedimientos y funciones que ejecuten las operaciones realizadas por las estructuras de datos. Sin embargo, con las estructuras vistas hasta ahora arrays y registros tienen dos inconvenientes: 1) la reorganización de una lista, si ésta implica movimiento de muchos elementos de datos, puede ser muy costosa, y 2) son estructuras de datos estáticas. Una estructura de datos se dice que es estática cuando el tamaño ocupado en memoria es fijo, es decir, siempre ocupa la misma cantidad de espacio en memoria. Por consiguiente, si se representa una lista como vector, se debe anticipar (declarar o dimensionar) la longitud de esa lista cuando se escribe un programa; es imposible ampliar el espacio de memoria disponible (algunos lenguajes permiten dimensionar dinámicamente el tamaño de un array du- rante la ejecución del programa, como es el caso de Visual BASIC). En consecuencia, puede resultar difícil repre- sentar diferentes estructuras de datos. Los arrays unidimensionales son estructuras estáticas lineales ordenadas secuencialmente. Las estructuras se con- vierten en dinámicas cuando los elementos pueden ser insertados o suprimidos directamente sin necesidad de algo- ritmos complejos. Se distinguen las estructuras dinámicas de las estáticas por los modos en que se realizan las inser- ciones y borrados de elementos. 12.1.1. Estructuras dinámicas de datos Las estructuras dinámicas de datos son estructuras que «crecen a medida que se ejecuta un programa». Una estruc- tura dinámica de datos es una colección de elementos —llamados nodos— que son normalmente registros. Al con- trario que un array, 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: pilas lineales { colas listas enlazadas  Estructuras dinámicas lineales de datos (pilas, colas y listas enlazadas) 431 árboles no lineales { grafos Las estructuras dinámicas de datos se utilizan para almacenamiento de datos del mundo real que están cam- biando constantemente. Un ejemplo típico ya lo hemos visto como estructura estática de datos: la lista de pasaje- ros de una línea aérea. Si esta lista se mantuviera en orden alfabético en un array, sería necesario hacer espacio para insertar un nuevo pasajero por orden alfabético. Esto requiere utilizar un bucle para copiar los datos del re- gistro de cada pasajero en el siguiente elemento del array. Si en su lugar se utilizara una estructura dinámica de datos, los nuevos datos del pasajero se pueden insertar simplemente entre dos registros existentes sin un mínimo esfuerzo. Las estructuras dinámicas de datos son extremadamente flexibles. Como se ha descrito anteriormente, es relati- vamente fácil añadir nueva información creando un nuevo nodo e insertándolo entre nodos existentes. Se verá que es también relativamente fácil modificar estructuras dinámicas de datos, eliminando o borrando un nodo existente. En este capítulo examinaremos las tres estructuras dinámicas lineales de datos: listas, colas y pilas, dejando para el próximo capítulo las estructuras no lineales de datos: árboles y grafos. Una estructura estática de datos es aquella cuya estructura se especifica en el momento en que se escribe el programa y no puede ser modificada por el programa. Los valores de sus diferentes elementos pueden variar, pero no su estructura, ya que ésta es fija. Una estructura dinámica de datos puede modificar su estructura mediante el programa. Puede ampliar o limitar su tamaño mientras se ejecuta el programa. 12.2. LISTAS Una lista lineal es un conjunto de elementos de un tipo dado que pueden variar en número y donde cada elemento tiene un único predecesor y un único sucesor o siguiente, excepto el primero y último de la lista. Esta es una defini- ción muy general que incluye los ficheros y vectores. Los elementos de una lista lineal se almacenan normalmente contiguos —un elemento detrás de otro— en posi- ciones 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 me- moria 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 asignación de memoria se denomina almacena- miento secuencial. Posteriormente se verá que existe otro tipo de almacenamiento denominado encadenado o enla- zado. Las líneas así definidas se denominan contiguas. Las operaciones que se pueden realizar con listas lineales con- tiguas son: 1. Insertar, eliminar o localizar un elemento. 2. Determinar el tamaño —número de elementos— de la lista. 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 la lista. 8. Borrar la lista. Una lista lineal contigua se almacena en la memoria de la computadora en posiciones sucesivas o adyacentes y se procesa como un array 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, el diseño de un algoritmo específico. Para permitir operaciones con listas como arrays se deben dimensionar éstos con tamaño suficiente para que contengan todos los posibles elementos de la lista. 432 Fundamentos de programación EJEMPLO 12.1 Se desea leer el elemento j-ésimo de una lista P. El algoritmo requiere conocer el número de elementos de la lista (su longitud, L). Los pasos a dar son: 1. conocer longitud de la lista L. 2. si L = 0 visualizar «error lista vacía». si_no comprobar si el elemento j-ésimo está dentro del rango permitido de elementos 1