UNIDAD IV
Estructuras de Datos Lineales
Estáticos y Dinámicos

4.1. LISTAS ENLAZADAS

Introducción

Las estructuras dinámicas de datos son estructuras que  «crecen a medida que se ejecuta un programa». Una estructura dinámica de datos  es una colección de elementos – llamados nodos  –  que son normalmente registros. Al contrario 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.

4.1.1 Representación en memoria

Una lista es una estructura de datos secuencial. Gráficamente se suele representar así:

Como se ha dicho anteriormente, pueden cambiar de tamaño, pero su ventaja fundamental es que son flexibles a la hora de reorganizar sus elementos; a cambio se ha de pagar una mayor lentitud a la hora de acceder a cualquier elemento.

4.1.2 Listas simples

Una lista enlazada o encadenada es un conjunto de elementos en los que cada elemento contiene la posición del siguiente elemento de la lista. Cada elemento de la lista enlazada debe tener al menos dos campos: un campo que tiene el valor del elemento y un campo (enlace, 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 enlazadas tienen una terminología propia que se suele utilizar normalmente. Primero, los valores se almacenan en un nodo. Figura 2.1

Figura 2.1 Nodo con dos  campos

Una lista enlazada se muestra en la Figura 2.2

Los componentes de un  nodo se llaman campos. Un nodo tiene al menos un campo dato o valor  y un enlace(indicador o puntero) con el siguiente nodo. El campo enlace apunta (proporciona la dirección o referencia de) al siguiente nodo de la lista. El último nodo de la lista enlazada, por convenio, se suele representar por un enlace con la palabra reservada nil(nulo), una barra inclinada (/) y, en ocasiones, el símbolo eléctrico de tierra o masa.
A partir de ahora utilizaremos el término puntero (apuntador) para describir el enlace entre dos elementos o nodos de una lista enlazada.
Un puntero (apuntador) es una variable cuyo valor es la dirección o posición  de otra variable.

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 define 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).

Implementación de listas enlazadas con punteros

Como ya hemos visto la representación gráfica de un puntero consiste en una flecha que sale del puntero y llega a la variable dinámica apuntada.

Declaración de una variable de tipo puntero:

Tipo
Punt = ^ Nodo
Nodo = Registro
Campo1: Tipo1
Sig: Punt
Fin_nodo
Var
Reg: Nodo
Ini, ant, aux: Punt;

Inicialización

P ¬ nulo    A nulo para indicar que no apunta a ninguna variable.

Comparación

p = q          Con los operadores = o <>

Asignación

P ¬ q        Implica hacer que el puntero q apunte a donde apuntaba q.

Creación de variables dinámicas

Reservar (p)   Reservar espacio en memoria ocupado por la variable dinámica.

Eliminación de variables dinámicas

Liberar (p)     Liberar espacio en memoria ocupado por la variable dinámica.

Creación de la lista
La creación de la lista conlleva la inicialización a nulo del puntero (inic), que apunta al primer elemento de la lista.

Tipo
Punt = ^ Nodo
Nodo = Registro
Campo1: Tipo1
Sig: Punt
Fin_nodo
Var
Reg: Nodo
Ini, ant, aux: Punt;

      Inicio
           Inicializar(ini)
…
      Fin

      procedimiento inicializar (inic:punt)
      inicio
            ini ¬ nulo
            ant ¬ nulo
      fin_procedimiento

Inserción de un elemento
La inserción tiene dos casos particulares:

Insertar el nuevo nodo en el frente, principio de la lista.

Insertar el nuevo nodo en cualquier otro lugar de la lista.

El procedimiento insertar inserta un nuevo elemento a continuación de anterior, si anterior fuera nulo significa que ha de insertar al comienzo de la lista.

1º Situación de partida.

2º reservar (aux).
 

3º Introducir la nueva información en aux^.elemento.

4º Hacer que aux^.sig apunte a donde lo hacía anterior^.sig
5º Conseguir que anterior^.sig apunte a donde lo hace aux.

Eliminación de un elemento de una lista enlazada
Antes de proceder a la eliminación de un elemento de la lista, debemos comprobar que no está vacía. Para lo que podremos recurrir a la función Vacia.

Función vacia (inic:punt): lógico
Inicio
Devolver(inic = nulo)
Fin

Al suprimir un elemento de una lista consideraremos dos casos particulares:

• El elemento a suprimir está al principio de la lista.
• El elemento se encuentra en cualquier otro lugar de la lista.

1. Situación de partida
2. Anterior^.sig apunta a donde Posic.^.sig
3. Liberar(posic)

Recorrido de una lista enlazada
Para recorrer la lista utilizaremos una variable de tipo puntero auxiliar.

Acceso a un elemento de una lista enlazada
La búsqueda de una información en una lista simplemente enlazada sólo puede hacerse mediante un proceso secuencial o recorrido de la lista elemento a elemento, hasta encontrar la información buscada o detectar el final de la lista.

4.1.3 Listas circulares

Las listas enlazadas no permiten a partir de un elemento acceder directamente a cualquiera de los elementos que le preceden. En lugar de almacenar un puntero NULO en el campo SIG del último elemento de la lista, se hace que el último elemento apunte al primero o principio de la lista. Este tipo de estructura se llama lista enlazada circular o simplemente lista circular.

Las listas circulares presentan las siguientes ventajas respecto de las listas enlazadas simples:

• Cada nodo de una lista circular es accesible desde cualquier otro nodo de ella. Es decir, dado un nodo se puede recorrer toda la lista completa. En una lista enlazada de forma simple sólo es posible recorrerla por completo si se parte de su primer nodo.
• Las operaciones de concatenación y división de listas son más eficaces con listas circulares.

Los inconvenientes, por el contrario, son:

Se pueden producir lazos o bucles infinitos. Una forma de evitar estos bucles infinitos es disponer de un nodo especial que se encuentre permanentemente asociado a la existencia de la lista circular. Este nodo se denomina cabecera de la lista.

El nodo cabecera puede  diferenciarse de los otros nodos en una de las dos formas siguientes:

• Puede tener un valor especial en su campo INFO que no es válido como datos de otros elementos.
• Puede tener un indicador o bandera (flag) que señale cuando es nodo cabecera.

El campo de la información del nodo cabecera no se utiliza, lo que se señala con el sombreado de dicho campo.
Una lista enlazada circularmente vacía se representa como se muestra a continuación:

4.1.4 Listas dobles

En las listas lineales estudiadas anteriormente el recorrido de ellas sólo podía hacerse en un único sentido: de izquierda a derecha (principio a fin). En numerosas ocasiones se necesita recorrer las listas en ambas direcciones.

Las listas que pueden recorrerse en ambas direcciones se denominan listas doblemente enlazadas. En estas listas cada nodo consta del campo INFO de datos y dos campos de enlace o punteros: ANTERIOR (ANT) y SIGUIENTE (SIG) que apuntan hacia delante y hacia atrás.
La lista necesita dos punteros CABECERA Y FIN que apunta hacia el primero y el último nodo.
La variable CABECERA y el puntero SIG permiten recorrer la lista en el sentido normal y la variable FIN y el puntero ANT permiten recorrerla en sentido inverso.

Inserción
La inserción de un nodo a la derecha de un nodo especificado, cuya dirección está dada por la variable M, puede presentar varios casos:

1. La lista está vacía; se indica mediante M=NULO y CABECERA y FIN son también NULO.

Una inserción indica que CABECERA se debe fijar con la dirección del nuevo nodo y los campos ANT y SIG también se establecen en NULO.

1. Insertar dentro de la lista: existe un elemento anterior y otro posterior de X.
2. Insertar a la derecha del nodo de la extrema derecha de la lista. Se requiere que el apuntador FIN sea modificado.

Eliminación
La operación de eliminación es directa.
Si la lista tiene un simple nodo, entonces los punteros de los extremos izquierdo y derecho asociados  a la lista se deben fijar en NULO. Si el nodo del extremo derecha de la lista es el señalado para la eliminación, la variable FIN debe modificarse para señalar el predecesor del nodo que se va a borrar de la lista. Si el nodo del extremo izquierdo de la lista es el que se desea borrar, la variable CABECERA debe modificarse para señalar el elemento siguiente.

4.2. PILAS

Introducción

Una pila (snack) es un tipo especial de lista lineal en la que la inserción y borrado de nuevos elementos se realiza sólo por un extremo que se denomina cima o tope (top).

Dado que las operaciones de insertar y eliminar se realizan por un solo extremo (el superior), los elementos sólo pueden eliminarse en orden inverso al que se insertan en la pila. El último elemento que se pone en la pila es el primero que se puede sacar; por ello, a estas estructuras se les conoce por el nombre de LIFO (last-in, first-out, último en entrar, primero en salir).

4.2.1 Representación en memoria

Operaciones “Push” y “Pop”

Las operaciones más usuales asociadas a las pilas son:
“push”    Meter, poner o apilar:
operación de insertar un elemento en la pila.

“pop”     Sacar, quitar o desapilar:
operación de eliminar un elemento de la pila.

Figura 1. Representación de las pilas.

Para representar una pila St, se debe definir  un vector con un determinado tamaño (longitud máxima):

Var
          St : array [1..n] de <tipo_dato>

Se considerará un elemento entero P como el puntero de la pila (snack pointer). P es el subíndice del array correspondiente al elemento cima de la pila (el que ocupa la última posición). Si la pila está vacía, P=0.

En el principio, la pila está vacía y el puntero de la pila o CIMA está a cero. Al meter un elemento en la pila, se incrementa el puntero en una unidad. Al sacar un elemento de la pila se decrementa en una unidad el puntero.

Al manipular una pila, se deben realizar algunas comprobaciones:
En una pila vacía no se pueden sacar datos (P=0).

Si la pila se implementa con un array de tamaño fijo, no se puede llenar cuando P=n (n, longitud total de la pila) y el intento de introducir más elementos en la pila producirá un desbordamiento de la pila.

4.2.2 Implementación con arreglos

Esta implementación es estática, es decir, da un tamaño máximo fijo a la pila, y si se sobrepasa dicho límite se produce un error.

La inserción o extracción de un elemento se realizará siempre por la parte superior. Su implementación mediante arrays limita el máximo número de elementos que la pila puede contener y origina la necesidad de una función más.

Ejemplo: “push” y “pop”

4.2.3 Implementación con punteros

Para la manipulación de una pila mediante punteros deberemos diseñar los siguientes procedimientos y/o funciones: inicializar, apilar, desafilar, consultar y vacia.

Los elementos se incorporan siempre por un extremo, cima.

1. Cima apunta al último elemento de la pila

2. Reservar(aux)

3. Introducimos  la información en aux^.elemento

4. Hacemos que aux^.cima apunte a donde cima
5. Cambiamos cima para que apunte donde aux

6. La pila tiene un elemento màs.

4.3. COLAS

Introducción

Una cola es una estructura de datos de acceso restrictivo a sus elementos. Un ejemplo sencillo es la cola del cine o del autobús, el primero que llegue será el primero en entrar, y afortunadamente en un sistema informático no se cuela nadie salvo que el programador lo diga.
Las colas serán de ayuda fundamental para ciertos recorridos de árboles y grafos.

Las colas ofrecen dos operaciones fundamentales, que son encolar (al final de la cola) y desencolar (del comienzo de la cola). Al igual que con las pilas, la implementación de las colas suele encapsularse, es decir, basta con conocer las operaciones de manipulación de la cola para poder usarla, olvidando su implementación interna.

Es una estructura de tipo FIFO (First In First Out), es decir: primero en entrar, primero en salir. A continuación se expone la implementación de colas, con arrays y con listas enlazadas circulares. En ambos casos se cubren cuatro operaciones básicas: Inicializar, Encolar, Desencolar, y Vacía. Las claves que contendrán serán simplemente números enteros.

4.3.1 Representación en memoria

Las colas  se pueden representar por listas enlazadas o por arrays.
Se necesitan dos punteros: frente(f) y final(r), y la lista o array de n elementos (LongMax).

Si la cola está vacía   frente = nulo   o bien         f 0
Eliminar elementos    frente frente + 1   o bien     f f -1
Añadir elementos      frente final + 1   o bien      r r +1

4.3.2 Colas simples

Las operaciones que se pueden realizar  con una cola son:

• Acceder al primer elemento de la cola.
• Añadir un elemento al final de la cola.
• Eliminar el primer elemento de la cola.
• Vaciar la cola.
• Verificar el estado de la cola: vacía:llena

1. Situación de partida
2. Reservar(aux)
3. Introducir la nueva información en aux^.elemento
4. Hacer que aux^.sig apunte a nulo.
5. Conseguir que final^.sig apunte a donde lo hace aux.
6. Por último, final debe apuntar también a donde aux.

El procedimiento para la inserción de un nuevo elemento deberá verificar, en primer lugar, que la cola no está totalmente  llena y, por consiguiente, no se producirá error de desbordamiento.
La condición de desbordamiento se produce cuando final =Max

Para eliminar un elemento será preciso verificar, en primer lugar, que la cola no esté vacía.

La cola estará vacía cuando frente = 0

Esta implementación tiene el inconveniente de que  puede ocurrir que la variable final llegue al valor máximo de la tabla, con lo cual no se puedan seguir añadiendo elementos a la cola, aun cuando queden posiciones libres a la izquierda de la posición frente por haber sido eliminados algunos de sus elementos.

Existen diversas soluciones a este problema:

1. Retroceso
Consiste en mantener fijo a 1 el valor de frente, realizando un desplazamiento de una posición para todas las componentes ocupadas cada vez que se efectúa una supresión.

2. Reestructuración
Cuando al final llega al máximo de elementos se desplazan las componentes ocupadas hacia atrás las posiciones necesarias para que el principio coincida con el principio de la tabla.

3. Mediante un array circular
Un array circular es aquel en el que se considera que la componente primera sigue a la componente última. Esta implementación obliga a dejar siempre una posición libre para separar el principio y el final del array. Evidentemente,  seguirá existiendo la limitación de que pueda llenarse completamente el array, Max -1 posiciones ocupadas.

El mejor método para evitar el desaprovechamiento de espacio es el diseño de la cola mediante un array circular.

4.3.3 Colas dobles

Existe una variante de la cola simple estudiada anteriormente y que es la doble cola. La doble cola o bicola es una cola bidimensional en la que las inserciones y eliminaciones se pueden realizar en cualquiera de los dos extremos de la lista.

Existen dos variantes de la doble cola:

• Doble cola de entrada restringida: acepta inserciones sólo al final de la cola.
• Doble cola de salida restringida: acepta eliminaciones sólo al frente de la cola.

Los procedimientos de inserción y eliminación de las dobles colas son variantes de los procedimientos estudiados para las colas simples.

EJERCICIO # 5: Solución de problemas con listas enlazadas

HERRAMIENTAS, MATERIALES Y EQUIPOS:

• Hojas blancas, lápiz
• Lenguaje C#
• Pc

PROCEDIMIENTO:

• Resuelva cada uno de los ejercicios de acuerdo al procedimiento que se indica.
• Elabore el algoritmo de cada uno de los problemas planteados.
• Codifique los algoritmos en Lenguaje C#.
• Compruebe que la ejecución y sus resultados  sean correctos.

EVIDENCIAS:
            Documentos:

• Hoja de presentación
• Algoritmos de cada uno de los ejercicios.
• Diagramas de Flujo de cada método.
• Impresión del Código en el lenguaje C#.
• Impresión de la ejecución. (Pantalla con resultados)
• Conclusión.

           Programas:

• Toda la carpeta
• Todos los ejercicios serán entregados en un solo disco. (El disco debe traer su etiqueta correspondiente).

PLANTEAMIENTO DE PROBLEMAS:

• Escribir un algoritmo que realice una inserción contigua a la izquierda del n-ésimo  nodo de una lista doblemente enlazada y repetir el ejercicio para una inserción también contigua a la derecha de n-ésimo nodo.
• Realizar un algoritmo que permita insertar y eliminar un nodo, y recorrer una lista circular.
• Diseñar un algoritmo que compruebe si una frase es un palíndromo (un palíndromo es una frase que se lee igual de izquierda a derecha que de derecha a izquierda).
• Elabore un algoritmo que utilice tres pilas (LETRAS, DIGITOS, OTROS) para contener los diferentes tipos de caracteres. Introducir por teclado carácter a carácter.Comprobar el tipo de carácter y según el resultado introducirlo en su pila respectiva.
• Utilice varios nombres de personas para formar una lista doblemente enlazada; incluya los campos para el nombre y el género. Implemente el método que permita partir la lista en dos, de forma que aparezca en una lista las damas y en la otra los caballeros.
• Mediante el uso de la clase LISTA_ORDENADA se han efectuado una serie de inserciones, cada nodo está constituido por los campos clave, cantidad, enlace. Desarrolle un algoritmo que determine la suma de las cantidades positivas de los nodos e indique la dirección del nodo donde se encuentra la cantidad mayor. Desarrolle un método que elimine aquellos nodos cuya cantidad sea cero o negativo.
• El listado de mercancías de cada sucursal de una empresa es una lista enlazada e incluye clave, nombre, cantidad, ordenadas de forma ascendente, con base en la clave. Desarrolle el algoritmo, para intercalar la información de dos sucursales y producir un listado único de las mercancías existentes.

Conclusión

Una lista lineal es una lista en la que cada elemento tiene un único sucesor. Las operaciones típicas en una lista lineal son: inserción, supresión, recuperación y recorrido. Una lista enlazada es una colección ordenada de datos en los que cada elemento contiene la posición (dirección) del siguiente elemento. Es decir, cada elemento (nodo) de la lista contiene dos partes: datos y enlace (puntero).

Una lista simplemente enlazada contiene sólo un enlace a un sucesor único a menos que sea el último, en cuyo caso no se enlaza con ningún otro nodo. Cuando se desea insertar un elemento en una lista enlazada, se deben considerar dos casos: añadir al principio y añadir en el interior o añadir al final. Si se desea eliminar un nodo de una lista se deben considerar dos casos: eliminar el primer nodo y eliminar cualquier otro nodo. El recorrido de una lista enlazada implica visitar cada nodo de la lista y procesar en su caso.

Una lista doblemente enlazada es una lista en la que cada nodo tiene un puntero a su sucesor y otro a su predecesor. Una lista enlazada circularmente es una lista en la que el enlace del último nodo apunta al primero de la lista.

Una pila es una estructura de datos tipo LIFO (last-in, first-out, último en entrar, primero en salir) en la que los datos se insertan y eliminan por el mismo extremo que se denomina cima de la pila. Se definen diferentes operaciones: crear, apilar, desafilar, pilavacía, pilallena, cimapila.

Una cola es una lista en la que los datos se pueden insertar por un extremo denominado Cabeza y se elimina o borra por el otro extremo denominado cola o final. Las operaciones básicas de una cola son: poner, quitar, frentecola y colavacìa, cola llena. Las colas se pueden implementar mediante arrays y listas enlazadas.