Dado un dominio D, una lista de elementos de dicho conjunto es una sucesión finita de elementos del mismo.En lenguaje
matemático, una lista es una aplicación de un conjunto de la forma {1,2, ... ,n} en un dominio D:
Una lista se suele representar de la forma:
A n se le llama longitud de la lista.
A 1,2,...,n se les llama posiciones de la lista. El elemento a(i)=ai, se dice que ocupa la posicion i. Si la lista tiene n elementos, no existe ningún elemento que ocupe la posición n+1. Sin embargo, conviene tener en cuenta dicha posición, a la que se llama posición detras de la última, ya que esta posición indicará el final de la lista. A a1 se le llama primer elemento de la lista y a an último elemento de la lista. Si n=0 diremos que la lista está vacía y lo representaremos como <>. Los elementos de una lista estan ordenados por su posición. Así, se dice que ai precede a ai+1 y que ai sigue a ai-1. A continuación vamos a especificar un ejemplo de posibles operaciones primitivas entre listas. Al conjunto de las listas (es decir, al tipo lista) lo llamaremos tLista. Al conjunto de los elementos básicos(es decir, al tipo que se almacenará en la lista) tElemento. También vamos a considerar el tipo posición como tPosicion. Esto lo haremos así, ya que no siempre las posiciones las vamos a representar por números naturales del lenguaje que se utilice. Lo único importante de la representación que se utilice es que sea un conjunto finito y totalmente ordenado: hay un primer y un último elemento y dado un elemento se puede determinar el siguiente (si no es último) y el anterior (si no es el primero).
Hay que tener en cuenta que si una lista tiene longitud n y se elimina el elemento que ocupa una determinada posición intermedia i, entonces
la longitud pasa a ser n-1 y el elemento que estaba en la posición i+1 pasará a ocupar la posición i, el de la posición i+2 pasará a ocupar la
posición i+1 y así sucesivamente.
Dentro del tipo abstracto de listas podemos proponer las siguientes primitivas:
Respecto al conjunto de primitivas que hemos presentado, no son más que un ejemplo representativo de las primitivas más importantes que nos sirve para ilustrar la forma en que se debe construir el tipo de dato abstracto Lista. Obviamente, en una implementacion real es posible optar por un conjunto distinto de primitivas teniendo en cuenta varios puntos:
Es importante aprender a usar las listas basándonos en estas especificaciones, aunque este tipo no venga en el lenguaje en el que estemos trabajando y no conozcamos la implementación que se va a usar.
Por ejemplo, vamos a escribir un porcedimiento que escriba todos los elementos de una lista. Suponiendo que para tElemento existe un procedimiento,
,escribe(x), que escribe un elemento de dicho tipo.
void salida (tLista t)
{
tposicion p;
telemento x;
for (p = primero(l); p != fin(l); p = siguiente(p, l)){
x = elemento(p, l);
escribe(x);
}
}
Veamos otro ejemplo de copia de una lista en otra:
tLista copia (tLista l)
{
tLista l2;
tPosicion p;
anula(&l2);
for (p=primero(l);p!=fin(l);p=siguiente(p,l))
insertar(elemento(p,l),fin(l2),l2);
return l2;
}
En el siguiente ejemplo, vamos a ver un porcedimiento para eliminar todos los elementos repetidos de la lista. Suponemos que el tipo
básico es tElemento y que existe una función lógica, igual(x,y), que nos dice cuando son iguales dos elementos de este tipo.
Se podría pensar en que bastaría considerar la igualdad del C(==), pero es posible que no coincidad con la igualdad de tElemento. Por
ejemplo, consideremos los numeros racionales definidos como:
typedef struct {
int num;
int den;
}racional;
Entonces si x,y son de tipo racional, entonces pueden representar el mismo racional, ser iguales, aunque no se verifique x.num==y.num
&& x.den==y.den .La función igual sería en este caso:
int igual (int x;int y)
{
return (x.num*y.den == y.num*x.den);
}
Con estas consideraciones, el procedimiento para eliminar las repeticiones de una lista sería como sigue:
void elimina (tLista l, int (*es_igual)(tElemento, tElemento))
{
tposicion p, q;
for (p = primero(l); p != fin(l); p = siguiente(p, l)){
q = siguiente(p ,l);
while (q != fin(l))
if ((*es_igual)(elemento(p, l), elemento(q, l)))
borrar(q, l);
else
q = siguiente(q, l);
}
}
Unos comentarios respecto a esto ejemplo:
Las listas se pueden implementar usando las posiciones consecutivas de un vector.Como las listas tienen longitud variable y los vectores longitud fija, esto se resuelve considerando vectores de tamaño igual a la longitud maxima de la lista y un entero donde se indica la posición donde se encuentra el último elemento de la lista.
Así podriamos tener:
#define LMAX = 100; /* Una constante adecuada. */
typedef int tElemento; /* Por ejemplo. */
typedef struct{
tElemento elementos[LMAX];
int n;
} Lista;
typedef Lista *tLista;
typedef int tPosicion;
Dado el objeto del tipo rep r = {elementos, n}, el objeto abstracto que representa es:
<r.elementos[0], r.elementos[1], ... , r.elementos[n-1]>
VERDAD.
La implementación de la mayoria de las operaciones es prácticamente inmediata. Por ejemplo, las mas simples son:
static void error (char *mensaje)
{
fprintf(stderr, "%s\n", mensaje);
exit(-1);
}
void anula (tLista *l)
{
*l = (tLista) malloc (sizeof(Lista));
if (*l==NULL) {
error("No hay memoria.");
}
(*l)->n=-1;
}
tPosicion primero (tLista l)
{
return 0;
}
tPosicion fin (tLista l)
{
return(l->n+1);
}
tPosicion siguiente (tPosicion p, tLista l)
{
if ((p < 0) || (p > l->n))
error("Posición no válida.");
return (p + 1);
}
tPosicion anterior (tPosicion p, tLista l)
{
if ((p <= 0) || (p > l->n+1))
error("Posición no válida.");
return (p - 1);
}
tElemento elemento (tPosicion p, tLista l)
{
if ((p < 0) || (p > l->n))
error("Posición no válida.");
return (l->elementos[p]);
}
Las únicas operaciones que pueden presentar un poco de dificultad son las de insertar,borrar y posicion. La función posición
tiene que realizar una búsqueda lineal en un vector. En caso de que el elemento considerado no esté en el vector, esta función debe devolver
lo mismo que fin(l).
tPosicion posicion (tElemento x, tLista l)
{
tPosicion q;
int encontrado;
q = encontrado = 0;
while ((q <= l->n) && (!encontrado)) {
if (l->elementos[q] == x)
encontrado=1;
else q++;
};
return q;
}
Para la operación de inserción hay que hacer previamente un hueco donde realizar dicha inserción. Para el borrado, hay que "rellenar" el
hueco dejado por el elemento borrado. En la figura podemos observar en las flechas superiores los movimientos de los elementos que
se han tenido que realizar para insertar en la posición p (coinciden con los movimientos en sentido contrario que se deben realizar para borrar
el elemento que se encuentra en dicha posición).
Como consecuencia de ello, habrá que mover, en ambos casos, todos los elementos que ocupen una posición superior a la considerada para realizar
la inserción o borrado. Esto tiene como consecuencia que la eficiencia de las operaciones no es muy buena, del orden del tamaño de la lista.
void insertar (tElemento x, tPosicion p, tLista l)
{
tPosicion q;
if ((p > l->n+1) || (p < 0))
error("Error p incorrecta.");
else if (l->n >= LMAX-1)
error("Lista llena");
else{
for (q = l->n; q >= p; q--)
l->elementos[q+1] = l->elementos[q];
l->n++;
l->elementos[p] = x;
}
}
void borrar (tPosicion p,tLista l)
{
if ((p > l->n) || (p < 0))
error("p incorrecta.");
else {
l->n--;
for (; p <= l->n; p++)
l->elementos[p]=l->elementos[p+1];
}
}
Aparte de la mala eficiencia de estas dos operaciones, que veremos como se mejorará en otras implementaciones, otro inconveniente de esta implementación es que las listas tienen un tamaño máximo del que no se puede pasar. Es decir, no corresponden exactamente a las especificaciones consideradas en un principio. Por otra parte, siempre hay una porción de espacio reservada para los elementos de la lista, y que no se utiliza al ser el tamaño de la lista, en un momento dado menor que el tamaño máximo. Esto se hace más grave si las distintas listas que se representen son de un tamaño muy distinto.
Otro detalle importante de esta implementación es, cómo hemos mencionado anteriormente, la necesidad de una función de destrucción ya que
ahora mismo la memoria que se requiere cada vez que se hace una llamada a la función anula no es recuperada en ningún momento.Sería interesante
añadir una nueva función tal como la siguiente (Nótese que si la constante LMAX es grande y se hace uso de un número alto de listas esta función
no sólo se hace interesante sino que necesaria:
void destruye (tLista l)
{
free(l);
}
Teniendo en cuenta los problemas que presenta la implementación que hemos presentado mediante vectores y considerando las posibilidades
que nos brinda el lenguaje C, podemos proponer una versión mas optimizada:
typedef int tElemento /* Por ejemplo. */
typedef struct{
tElemento *elementos;
int Lmax;
int n;
}Lista;
typedef Lista *tLista;
typedef int tPosicion;
tLista crear (int tamanoMax)
{
tLista l;
l = (tLista) malloc(sizeof(Lista));
if (l == NULL)
error("Memoria Insuficiente");
l->Lmax = tamanoMax;
l->n = -1;
l->elementos = (tElemento *)malloc(tamanoMax*sizeof(tElemento));
if (l->elementos == NULL)
error("Memoria Insuficiente.");
}
void destruir (tLista l)
{
free(l->elementos);
free(l);
}
Donde las demás primitivas quedarían de la misma forma sustituyendo LMAX por l->LMAX
En esta nueva implementación conseguimos resolver con exito dos cosas:
Es importante destacar la forma en que se deben usar las funciones de un tipo de dato abstracto (normalmente en la especificación junto con algún ejemplo si es necesario). Así destacaremos que que en este nuevo conjunto de primitivas incluyendo crear y destruir el uso del TDA debe ser:
Teniendo en cuenta:
Como ejemplo mostramos una función que guarda en una lista los números enteros del 0 al 9, despues la recorre eliminando los impares y por último escribe
el resultado dos veces, desde el primer elemento al último y desde el último al primero:
void EJEMPLO ()
{
int a;
tLista l;
tPosicion p;
l = crear(10);
for (a=0; a<10; a++)
insertar(a, primero(l), l);
for (p=primero(l); p!=fin(l); ) {
a = elemento(p,l);
if (a%2)
borrar(p,l);
else
p = siguiente(p,l);
}
for (p=primero(l); p!=fin(l); p=siguiente(p,l)) {
a = elemento(p,l);
printf("Elemento: %d \n",a);
}
printf(" \n \n ");
for (p=fin(l); p!=primero(l); p=anterior(p,l)) {
a = elemento(anterior(p,l), l);
printf("Elemento: %d \n",a);
}
destruir(l);
}
Una implementación de las listas que evita los problemas anteriormente mencionados para los vectores, es la que está basada en el uso de punteros. Esta implementación se basa en representar cada elemento, ai, de una lista <a1,a2, ...,an> como una celda dividida en dos partes: un primer campo donde se almacena el elemento en cuestión; y un segundo campo donde se almacena un puntero, que nos indica donde está el siguiente elemento de la lista, tal como se muestra en la parte (a) de la figura.
La celda que contiene el último elemento de la lista tiene un puntero donde se almacena NULL. Así, la lista quedaria como se muestra en la parte (b) de la figura.
Para realizar más facilmente las operaciones es conveniente considerar una celda inicial, llamada de cabecera y donde no se almacena
ningún elemento de la lista. De esta forma la lista propiamente diche vendrá representada por un puntero que indique la dirección de la cabecera
y que permite obtener los distintos elementos de la misma como se muestra finalmente en la parte (c) de la figura.
Para estas listas es conveniente representar la posición mediante un puntero que acceda al elemento correspondiente. Sin embargo, no se va a consider un puntero con la dirección de la celda donde está el elemento considerado, sino la dirección de la celda donde está el elemento anterior. Con esto se puede acceder a dicho elemento (mediante el puntero correspondiente), y también será más útil para las operaciones de inserción y borrado. La posición del primer elemento, vendrá representada entonces por un puntero apuntando a la celda de cabecera, es decir, idéntico a la lista, l. La posición del elemento ai se representará mediante un puntero, indicando la celda del elemento ai-1. La posición detrás del último elemento será un puntero apuntando a an.
Debido a que la posición lógica de un elemento viene determinada por la posición física del anterior puede dar lugar a un error de programación si
se trabaja con varias posiciones a la vez y se realizan borrados. Por ejemplo, consideremos una lista con 3 elementos y 2 punteros indicando la posición
del segundo (puntero p) y tercer (puntero q) elemento (ver figura).
Si no atendemos a la implementación, el borrar el elemento de la posición p (elemento a2) podemos considerar dos resultados:
En general, el primer caso corresponde a la implementación realizada mediante vectores y el segundo a la realizada mediante celdas enlazadas teniendo en cuenta:
Es por ello que el uso simultáneo de varias posiciones conviene que sea manejado con cuidado. Obviamente, el que el acceso a un elemento se produzca por medio del elemento anterior conviene que sea indicado en la especificación del TDA mediante el correspondiente aviso de que el borrado de un elemento invalidad los valores de posición del inmediatamente posterior (por ejemplo, se puede indicar el comportamiento de los valores posición cuando se usan las funciones de inserción y de borrado).
En C, la definición de tipos correspondiente a la implementación por punteros sería:
typedef struct Celda{
tElemento elemento;
struct Celda *siguiente;
}celda;
typedef celda *tPosicion;
typedef celda *tLista;
Dado el objeto del tipo rep l={elemento, siguiente}, el objeto abstracto que representa es:
<l->siguiente->elemento, l->siguiente->siguiente->elemento, ...
,l->siguiente-> (n) ->siguiente->elemento>
Donde r->siguiente-> (n+1) ->siguiente == NULL.
Todas las direcciones de los campos siguiente proceden de llamadas (tposicion) malloc(sizeof(celda)) o son NULL.
Y las operaciones se pueden implementar como sigue:
tLista crear ()
{
tLista l;
l = (tLista)malloc(sizeof(celda));
if (l == NULL)
error("Memoria Insuficiente.");
l->siguiente = NULL;
return l;
}
void destruir (tLista l)
{
tPosicion p;
for (p = l; l != NULL; p = l){
l = l->siguiente;
free(p);
}
}
tPosicion fin (tLista l)
{
tPosicion p;
p=l;
While (p->siguiente != NULL) {
p = p->siguiente;
}
return p;
}
Repecto a esta función es importante senñalar , que siempre tiene que recorrer toda la lista para devolver el puntero que se muestra en
la figura. Por lo que su eficiencia es del orden de la longitud de la lista. Habría que procurar no utilizarla demasiado si se usa
esta implementación.
Por ejemplo, un ciclo while con una condición p!=fin(l) se debe sustituir por:
q=fin(l);
while (p!=q)...
void insertar (tElemento x, tPosicion p, tLista l)
{
tPosicion q;
q = (tPosicion)malloc(sizeof(celda));
if (q == NULL)
error("Memoria Insuficiente.");
q->elemento = x;
q->siguiente = p->siguiente;
p->siguiente = q;
}
La forma en la que se realiza la inserción puede observarse en la figura.
Es importante señalar varias cosas de este procedimiento:
tPosicion siguiente (tPosicion p, tLista l)
{
if (p->siguiente==NULL) {
error("No hay siguiente de fin.");
}
return p->siguiente;
}
tPosicion primero (tLista l)
{
return l;
}
tPosicion posicion (tElemento x, tLista l)
{
tPosicion p;
int encontrado;
p = primero(l);
encontrado = 0;
while ((p->siguiente != NULL) && (!encontrado)) {
if (p->siguiente->elemento == x)
encontrado=1;
else p = p->siguiente;
}
return p;
}
Notas referentes a la función posicion:
tElemento elemento (tPosicion p, tLista l)
{
if (p->siguiente == NULL) {
error("Error: posicion fin(l).");
}
return p->siguiente->elemento;
}
void borrar (tPosicion p, tLista l)
{
tPosicion q;
if (p->siguiente == NULL)
error("Error: posicion fin(l).");
q = p->siguiente;
p->siguiente = q->siguiente;
free(q);
}
Respecto a esta implementación son válidos los mismos comentarios que para la función insercion.
Resulta de interés saber si es mejor usar una implementación de listas basada celdas enlazadas o en matrices en una circunstancia dada. Frecuentemente la contestación depende de las operaciones uqe queramos llevar a cabo, o de cuales son llevadas a cabo con mayor asiduiadad. Otras veces, la decisión es en base a la longitud de la lista.
Los puntos principales a considerar son los siguentes: