Listas encadenadas

1. Estructuras de datos.

La estructura de datos a utilizar está incluida en el fichero lista.h cuyo contenido se muestra en la figura 1:

Figura 1. Estructura de datos de una lista encadenada

#include "ao.h"

#define NUM_LIST_NULL ((numList *)NULL)  // Pointer to an empty list

struct numList {
    int *table;                          // Table of integers
    int length;                          // Table size
    struct numList *next;                // Next element in the linked list
};

typedef struct numList numList;

En este fichero se define en primer lugar mediante una macro la constante NUM_LIST_NULL que representa la lista vacía. A continuación se declara la estructura de datos con nombre struct numList que contiene tres campos: table es la tabla de números enteros, length indica el número de elementos de la tabla y next es un puntero que apunta al siguiente elemento de la lista encadenada. Finalmente, se define un tipo sinónimo con nombre numList equivalente a struct numList.

Cada elemento de la lista se representa por un dato de tipo numList. Estos elementos forman una cadena, donde cada elemento apunta al siguiente de la lista por medio del campo next.

La figura 2 ilustra un ejemplo de lista definida con el tipo de datos numList.

Figura 2. Lista encadenada con la estructura numList

Obsérvese que es preciso disponer de un apuntador al comienzo de la lista. A través de él se accede a cualquier elemento de la misma por medio del campo next. En este caso, la lista vacía se representa simplemente por un puntero con el valor NUM_LIST_NULL.

2. Bucles en listas encadenadas.

Uno de los problemas más comunes de las listas encadenadas es la presencia de bucles no deseados. Es decir, que en un punto de la lista se encadene un elemento anteriormente encontrado. Generalmente, cuando se manipula una lista encadenada, las operaciones para iterar sobre su contenido asumen que la lista termina con el valor NULL en el campo next del último elemento tal y como se ilustra en la figura 2 (representado por el símbolo de toma de tierra). La porción de código que se muestra en la figura 3 es un ejemplo de esta iteración:

Figura 3. Algoritmo para iterar sobre los elementos de una lista encadenada

numList *numListPointer;
numListPointer = head;
while (numListPointer != NULL) {
      // Process element pointed by numListPointer
      numListPointer = numListPointer->next;
} // End of while numListPointer != NULL

¿Qué sucede en el código de la figura 3 si el último elemento, por error, apunta a otro elemento de la lista? La figura 4 ilustra esta situación. La presencia de este bucle hace que la iteración entre en un bucle infinito.

Figura 4. Lista con un bucle

Nótese que no siempre la presencia de bucles en una lista es sinónimo de un error en el código. Todo depende del contexto en el que se utilice la estructura de datos. Si las funciones que procesan la lista asumen que ésta termina en un puntero a NULL (como en el caso del bucle anterior), entonces la presencia de un ciclo sí es un error. Sin embargo, existen aplicaciones cuya estructura de datos es una lista circular.

3. Ejercicios.

Todo el código a implementar se debe incluir en el fichero sumList.c del que se ofrece su estructura inicial: sumList_skel.c

Utilizando la estructura de datos de la figura 1 implementar la función long sumList(numList *head). El parámetro head es un puntero a la lista que se desea procesar. La función devuelve como resultado la suma de todos los enteros de todas las tablas contenidas en la lista.
Implementar la función int hasLoop(numList *list) que devuelve cero (falso) si la lista pasada como parámetro no contiene bucles y uno (cierto) en caso contrario. Esta función debe funcionar para listas de longitud arbitraria. La solución en la que se explora un número fijo de elementos de la lista (por muy elevado que éste sea) es incorrecta.
Supongamos que las listas de los dos programas anteriores corresponden a datos obtenidos de codificación numérica de imágenes. Debido a la regularidad de algunas de ellas se detecta que en un número elevado de casos, porciones significativas de elementos consecutivos de la lista apuntan a la misma tabla de enteros. Modificar la implementación de la función sumList para incrementar su eficiencia en estos casos.

4. Pruebas de programa.

Para validar la implementación de estas funciones, se facilita el fichero de pruebas listloop.c que contiene la función main. Para obtener el ejecutable se debe compilar este fichero, el fichero sumList.c y la librería libao.a (descárga LibAO.zip) en un único comando:

gcc -I ../LibAO -Wall -o listloop listloop.c sumList.c ../LibAO/libao.a

El programa realiza múltiples llamadas a sumList y hasLoop pasando diferentes listas como argumento. Al término de cada una, se imprime un mensaje indicando si el resultado obtenido es incorrecto. Si todas las pruebas se pasan correctamente, al final se imprime el mensaje:

Execution with no errors

Una de las pruebas procesa una lista con un número elevado de elementos (no se extrañe que el programa tarde algunos minutos en ejecutar la prueba 5). El programa imprime en pantalla el tiempo empleado en las pruebas más relevantes. Se debe realizar la implementación más eficiente posible con respecto al uso de memoria y al tiempo de CPU.

Fichero sumList.c (¡no entregues ficheros ejecutables!). file 80 text/plain,text/html sumList.c

La aplicación debe desarrollarse en Linux.

El objetivo de este problema es ejercitar el manejo de punteros en C. Para ello, se debe programar una primera función en la que se recorre una lista encadenada y se realiza un procesado de sus elementos. Una de las anomalías más comunes en las lista encadenadas es la presencia de bucles, es decir, un elemento que está encadenado a otro ya procesado. Se debe implementar una segunda función capaz de detectar esta situación en una lista encadenada de longitud arbitraria.

Solo debe subirse un fichero, sumList.c Deadline: 19/10/2012 17:00 Los nombres de los autores y sus NIAS deben indicarse en el comentario que aparece en sumList.c de la siguiente forma: /* AUTHORS: NIA1;Name1;NIA2;Name2 */ Las prácticas no deben ser entregadas por las dos personas de una misma pareja de prácticas. Basta con que la entregue uno de ellos en Aula Global 2

Lab 3