Listas

ESTRUCTURAS DE DATOS I

TEMA 5Estructura de datos Lista

Jos Manuel BadaGloria Martnez

Juan Murgui

Tema 5. Estructura de datos Lista E04. Estructuras de datos I

NDICE5.1. Definicin ............................................................................................................ 35.2. El TAD Lista ....................................................................................................... 35.3. Implementaciones del tipo Lista.......................................................................... 5

5.3.1. Implementacin esttica mediante un vector ........................................ 55.3.2. Implementacin dinmica de una lista con enlace simple .................... 85.3.3. Implementacin dinmica como lista doblemente enlazada ............... 17

5.4. TAD's relacionados con la Lista........................................................................ 205.4.1. TAD Lista Ordenada ........................................................................... 205.4.2. TAD Multilista .................................................................................... 23

5.5. Ejercicios ........................................................................................................... 24BIBLIOGRAFA

(Joyanes y Zahonero, 1998), Cap. 5 y 6. (Joyanes y Zahonero, 1999), Cap. 4. (Dale y Lilly, 1989), Cap. 6 y 7. (Horowitz y Sahni, 1994).

OBJETIVOS Conocer el concepto, funcionamiento y utilidad del tipo Lista.

Conocer el TAD Lista y sus operaciones asociadas.

Saber implementar una lista mediante variables estticas.

Saber implementar una lista mediante variables dinmicas. Conocer distintasimplementaciones dinmicas del tipo, utilizando simple y doble enlace.

Conocer el TAD Lista ordenada y su implementacin mediante variablesdinmicas.

Conocer el concepto y utilidad de las multilistas.


5.1. Definicin

Al igual que ocurra en el caso de la pila y la cola, estamos bastante familiarizados con elconcepto de lista. Si pensamos por ejemplo en una lista de la compra, o en una guatelefnica, estamos manejando listas. En el primero de los casos, los elementos no tienenporque estar ordenados por su valor, mientras en el segundo se ordenan segn un ndicealfabtico. No obstante, en ambos casos estamos hablando de listas de elementos.

En el caso de las estructuras de datos, definiremos una lista del siguiente modo:

Definicin

Una lista es un conjunto ordenado de elementos homogneos en la que no hayrestricciones de acceso, la introduccin y borrado de elementos puede realizarseen cualquier posicin de la misma.

Junto con la pila y la cola, la lista forma parte de lo que se denominan estructuraslineales. Intuitivamente son estructuras en los que los distintos elementos se sitan enlnea, de ah su nombre. Dicho de otro modo, cada elemento de una estructura lineal, salvoel primero y el ltimo, tan slo tiene un anterior y un siguiente. La diferencia entre estostres tipos de estructuras lineales radica en las restricciones impuestas en el acceso a loselementos.

En una pila los elementos tan slo pueden aadirse y borrarse por uno de susextremos.

En una cola, los elementos se aaden por un extremo y se borran por el otro.

En una lista, los elementos pueden aadirse y borrarse en cualquier posicin, noslo en los extremos.

De un modo ms formal, una lista es un triplete ( P,R,v ) en donde: P: es un conjunto de posiciones, en particular un conjunto de posiciones que

contienen datos en la lista.

R: es una relacin de orden sobre el conjunto P. Los elementos se sitan en lnea(orden), no se ordenan sus valores.

v: es una funcin de evaluacin, que para cada posicin P define el valor del datoalmacenada en la misma.

5.2. El TAD Lista

En este apartado vamos a ver una posible definicin del TAD Lista. En este caso estaremoshablando de una lista general en la que sus elementos no tienen porque estar ordenados porsu valor. Por otro lado, es necesario decir que existen muchas formas de definir una lista,tal y como puede verse en la literatura al respecto. Asimismo, y como veremos enapartados posteriores, existen numerosas estructuras relacionadas directamente con la listay distintas variantes de su implementacin que ofrecen diferentes propiedades de acceso.


TAD: Lista

Operaciones:CrearLista: ListaCrea una lista vaca.ListaVacia: Lista LogicoDada una lista nos dice si est vaca.Primero: Lista PosicionDevuelve la posicin del primer elemento de la lista.Ultimo: Lista PosicionDevuelve la posicin del ltimo elemento de la lista.Siguiente: Lista x Posicion PosicionDada una posicin p en la lista, devuelve la posicin del elemento situado acontinuacin.Anterior: Lista x Posicion PosicionDada una posicion p en la lista, devuelve la posicin del situado justo antes del mismo.Dato: Lista x Posicion TipobaseDada una posicin en la lista, devuelve el dato que contiene.Almacenar: Lista x Tipobase ListaDado un dato e, lo aade a la lista como ltimo elemento.InsAntes: Lista x Posicion x Tipobase ListaDado un dato e y una posicin p, aade el dato justo antes de la posicin.InsDespues: Lista x Posicion x Tipobase ListaDado un dato e y una posicin p, aade el dato justo despus de la posicin.Borrar: Lista x Posicion ListaDada una posicin, elimina de la lista el elemento que la ocupa.Buscar: Lista x Tipobase PosicionDado un dato e, lo busca en la lista y devuelve la posicin que ocupa.Modificar: Lista x Posicion x Tipobase ListaDado un dato e y una posicin p, sustituye el valor que ocupa esa posicin por e.Longitud: Lista EnteroDada una lista, devuelve su longitud.

Axiomas: L Lista, p Posicion, e, f TipoBase,1) Listavacia(CrearLista) = cierto2) Listavacia(Almacenar(L, e)) = falso3) Longitud(CrearLista) = 04) Longitud(Almacenar(L, e)) = Longitud(L) + 15) InsDespues(CrearLista, p, e) = Almacenar(CrearLista, e)6) InsDespues(Almacenar(L, e), p, f) =

Si p = Ultimo(Almacenar(L, e))entonces Almacenar(Almacenar(L, e), f)sino Almacenar(InsDespues(L, p, f), e)

7) Dato(CrearLista, p) = error


8) Dato(Almacenar(L, f), p) =Si p = Ultimo(Almacenar(L, f)) entonces fsino Dato(L, p)

9) Borrar(CrearLista, p) = CrearLista10) Borrar(Almacenar(L, e), p) =

Si p = Ultimo(Almacenar(L, e)) entonces Lsino Almacenar(Borrar(L, p), e)

10) Modificar(Almacenar(L, e), p, f) =Si p = Ultimo(Almacenar(L, e)) entonces Almacenar(L, f)sino Almacenar(Modificar(L, p, f), e)

5.3. Implementaciones del tipo Lista

Dentro de este apartado vamos a ver con mayor o menor detalle tres implementaciones delTAD Lista. En primer lugar veremos como puede implementarse de forma eficientemediante una estructura esttica de tipo vector. A continuacin veremos dosimplementaciones posibles mediante variables dinmicas que difieren en la eficiencia conque se desarrollan las distintas operaciones de acceso.

5.3.1. Implementacin esttica mediante un vector

En una primera aproximacin, podramos pensar en identificar la lista con un vector deelementos del tipo base. Dado que no existe ninguna posicin especfica en la cual sealmacenen o borren los elementos, no sera necesario guardar ningn valor adicional, tal ycomo ocurre en implementacin esttica de la pila o la cola. Los elementos podranaadirse o borrarse de cualquier posicin del vector.

Sin embargo, inmediatamente podemos observar problemas con estaimplementacin. En primer lugar, para aadir un elemento en la lista, sera necesariodesplazar todos los elementos situados a continuacin del mismo en el vector. En segundolugar, conforme fusemos borrando elementos de la lista, iramos generando huecos en elvector. Si quisiramos hacer un uso ptimo del espacio disponible, sera necesariodesplazar los elementos del vector para rellenar los huecos generados. As pues, lasoperaciones de modificacin de la pila resultan muy costosas utilizando un vector de estaforma. Adems, nos encontraramos con el problema derivado de manejar una estructuradinmica, como es la lista, mediante una estructura esttica, como es el vector. Podradarse el caso de que la lista se llenara, al disponer de un espacio limitado por el tamao delvector para almacenar sus elementos.

As pues, optaremos por una solucin alternativa para implementar una lista de formams eficiente mediante un vector. Para no tener que desplazar elementos al aadir o borrar,lo que haremos es no obligar a que elementos sucesivos de la lista se almacenen enposiciones consecutivas del vector. Para ello ser necesario que cada elemento guarde,adems de la informacin contenida en la lista, informacin sobre cual es la posicin delsiguiente elemento en la misma. De este modo, cada elemento del vector tendr doscomponentes. Una posible implementacin de esta estructura en Pascal es la siguiente:


CONST

MAX = ... {Tamao del vector y mximo tamao posible de la lista}TYPE

Posicion = 0 .. MAX;Elemento = RECORD

info: ;sig: Posicion

END;

TipoLista= RECORDprimero, vacios: Posicion;mem = ARRAY [1..MAX] OF Elemento

END;

VAR

v:TipoLista;

Como vemos, cada componente de la lista es un registro con dos campos: un campoinfo que contiene el elemento de la lista y un campo sig que contiene el ndice en elvector del siguiente elemento. A su vez, la lista es un registro con tres componentes

mem: contiene los elementos de la lista

primero: contiene el ndice del primer elemento de la lista en el vector

vacios: contiene el ndice del primer elemento vaco del vector

Con esta implementacin, los enlaces entre elementos de la lista no son punteros,sino que son simulados mediante enteros en el rango 0..MAX que contienen ndices decomponentes del vector.

Veamos grficamente un ejemplo de esta implementacin:1 2 3 4 5 6 7 8 9

primero=1 A C D M3 6 40

info

sig

vacios=2

En este caso la lista contiene 4 elementos {A, C, M, D}. Dado que el campo primerovale 1, el primer elemento de la lista ser el que ocupe esta posicin en el vector: A. Dadoque el campo sig de este elemento vale 3, el segundo elemento de la lista ser el queocupe esta posicin en el vector: C. Se sigue este razonamiento hasta llegar al elemento Dcuyo campo sig vale 0. Tomaremos como criterio general el que el valor 0 en este campoindique el final de la lista. As pues, la lista implementada mediante la estructura anteriores de la siguiente forma:

A C M D=

L


Dmonos cuenta que con esta implementacin de la lista estamos "simulando" lamemoria dinmica mediante un vector. Los elementos de la lista se almacenan en unvector, y los punteros al siguiente elemento son simulados mediante enteros que indican(apuntan) cual es la posicin del mismo en el vector.

Los distintos elementos de la lista no tienen porque encontrarse consecutivos en elvector y adems, durante el manejo de la estructura, se habrn ido produciendo huecos enel mismo. A la hora de insertar nuevos elementos ser necesario conocer la posicin de losdistintos huecos. Para ello lo que haremos es enlazar las componentes del vector que nocontengan elementos de la lista para formar otra lista de elementos vacos. De este modo,el vector contendr realmente dos listas: una de elementos y otra de huecos. Vemoslogrficamente:

1 2 3 4 5 6 7 8 9lista=1 A C D M

3 6 40info

sig5 7 8 9 0

vacios=2

La lista de elementos del ejemplo empieza en la posicin 1 del vector, mientras lalista de huecos empieza en la posicin 2. La lista de elementos ser la representadaanteriormente, mientras la de huecos enlazar las siguientes componentes del vector:

=

v

2 5 7 98

Para poder manejar esta implementacin de la lista ser necesario implementar dosoperaciones adicionales a las incluidas en el TAD. Estas operaciones simularn lasfunciones New y Dispose proporcionadas por el Pascal para la gestin de punteros:

La operacin Nuevo(L) devolver, si existe, una componente del vector que estvaca para poder almacenar el siguiente elemento de la lista L. Para ello consultar la listade huecos, devolver su primera componente y la eliminar de esta lista.

FUNCTION Nuevo(VAR L: TipoLista):Posicion;BEGIN

IF L.vacios=0 THEN { no quedan componentes en el vector }{ mensaje de error de lista llena }

ELSE BEGIN

Nuevo := L.vacios;L.vacios := L.mem[L.vacios].sig

END

END;

La operacin Liberar(L, e) aadir al principio de la lista de huecos lacomponente e del vector. Se supone que esta componente acaba de ser borrada de la listade elementos.


PROCEDURE Liberar(VAR L: TipoLista; e: Posicion);BEGIN

L.mem[e].sig := L.vacios;L.vacios := e

END;

Se deja como ejercicio la implementacin de las operaciones que definen el TADLista utilizando la estructura descrita en este apartado.

5.3.2. Implementacin dinmica de una lista con enlace simple

En este aparado veremos cmo implementar una lista mediante variables dinmicas ypunteros. En una primera aproximacin consideraremos que cada nodo de la lista tiene doscomponentes: una de ellas contiene la informacin del elemento de la lista, mientras la otracontiene un puntero al siguiente elemento de la misma. Al utilizar un solo enlace por cadanodo de la lista denominaremos a esta implementacin de enlace simple.

La implementacin directa de esta idea nos lleva a la siguiente estructura de datos enPascal

TYPE

Posicion = ^Elemento;Elemento = RECORD

info: sig: Posicion

END;

TipoLista = Posicion;

En este caso el tipo TipoLista es un puntero al primer elemento de la lista. Podramosrealizar una implementacin utilizando esta estructura, pero para simplificar las distintasoperaciones del TAD, haremos que la lista sea un registro con tres componentes:

Una componente que apunte al primer elemento de la lista

Una componente que apunte al ltimo elemento de la lista

Una componente que nos d la longitud de la lista.

De este modo, la estructura de datos utilizada quedar as:

TYPE


info: sig: Posicion

END;

TipoLista = RECORDlongitud: INTEGER;primero, ultimo: Posicion

END;


Grficamente

ultimo

primero

q:TipoListaElemento

info sig

Implementacin mediante punteros

A B CA B C

primero ultimo

TAD Lista

NIL

long 3

Esta estructura es muy similar a la que hemos utilizado para implementar una colamediante memoria dinmica. Sin embargo, la diferencia estriba en las operaciones daacceso, dado que stas pueden aadir y borrar elementos en cualquier posicin de laestructura.

Veamos como se implementan las distintas operaciones que definen el TAD Lista:

PROCEDURE CrearLista (VAR L: TipoLista);BEGIN

L.longitud := 0;L.primero := NIL;L.ultimo := NIL

END;

Al crear una lista, su longitud ser 0 y no estarn definidos ni su primer ni su ltimoelemento.

FUNCTION ListaVacia(L: TipoLista):BOOLEAN;BEGIN

ListaVacia := (L.longitud=0)END;

Se considerar que la lista est vaca cuando su longitud sea 0.

FUNCTION Primero (L:TipoLista):Posicion;BEGIN

Primero := L.primeroEND;

El primer elemento de la lista es el apuntado por el campo primero.

FUNCTION Ultimo (L: TipoLista): Posicion;BEGIN

Ultimo := L.ultimoEND;


El ltimo elemento de la lista es el apuntado por el campo ultimo. Si no hubisemosincluido este campo en la estructura de datos TipoLista, sera necesario recorrer toda lalista desde su primer elemento para devolver la posicin del ltimo. En las dos funcionesanteriores no hemos considerado el caso en el que la lista estuviese vaca de un modoespecial. En este caso, por el modo en que el resto de subprogramas tratan los distintoscampos de la estructura, la posicin devuelta ser NIL.

FUNCTION Siguiente ( L: TipoLista; p: Posicion): Posicion;BEGIN

Siguiente := p^.sigEND;

En una implementacin completamente libre de errores deberamos habercontemplado el caso en el que la posicin p pasada como argumento no correspondiese aun elemento de la lista. En ese caso deberamos haber devuelto algn tipo de error. Sinembargo, para no complicar el cdigo, vamos a suponer que al usar esta funcin, siemprese pasa una posicin que apunta a uno de los elementos de la lista. Este elemento puedehaberse encontrado por ejemplo usando la funcin Buscar que veremos ms adelante.

FUNCTION Longitud ( L : TipoLista ): INTEGER;BEGIN

Longitud := L.longitudEND;

Al disponer de un campo longitud en la estructura que representa la lista, es muysencillo implementar esta operacin. Si no hubisemos incluido este campo, habra sidonecesario recorrer toda la lista y contar sus componentes.

FUNCTION Anterior (L: TipoLista; p:Posicion): Posicion;VAR

aux: Posicion;BEGIN

IF p = Primero(L) THENaux := NIL

ELSE BEGIN

aux := Primero (L);WHILE (Siguiente(L,aux) p) DO

aux := Siguiente(L,aux)END;

Anterior := auxEND;

En la funcin Anterior de nuevo hemos supuesto que la posicin pasada comoargumento corresponde con un elemento de la lista. Al implementarla hemos decontemplar dos casos:


En el primer caso, cuando la lista la posicin pasada como argumento corresponde alprimer elemento de la lista, devolveremos como anterior al mismo un valor indefinido:NIL;

En el segundo caso, cuando la posicin indicada no es la primera, hemos de recorrerla lista hasta encontrar el elemento apuntado. Para ello utilizaremos una variable auxiliarque ir apuntando a los sucesivos elementos recorridos. Comenzaremos apuntando alprimer elemento de la lista y recorreremos los sucesivos elementos con ayuda de la funcinSiguiente. Cuando el siguiente elemento al apuntado por aux corresponda a la posicin p,aux ser el anterior que buscamos.

C NILprimero A B D

Siguiente(L, aux)=pAnterior(L,p)=aux

PROCEDURE Dato (L: TipoLista; p: Posicion; VAR d: TipoBase);BEGIN

d := p^.infoEND;

Para acceder al dato contenido en el nodo en la posicin p, basta con devolver elcampo info de ese nodo. Si el tipo base lo permite, la operacin anterior puedeimplementarse como una funcin del siguiente modo:

FUNCTION Dato (L: TipoLista; p: Posicion): TipoBase;BEGIN

Dato := p^.infoEND;

FUNCTION Buscar (L: TipoLista; e: TipoBase):Posicion;VAR

aux: Posicion;d:TipoBase;

BEGIN

aux := Primero(L);Dato(L, aux, d);WHILE ( d e) AND (aux NIL) DO BEGIN

aux := Siguiente (L, aux);IF (aux NIL) THEN Dato (L, aux, d)

END;

Buscar := aux

END;

La operacin Buscar devolver la posicin del dato e en la lista L si se encuentra, yNIL en caso contrario. Para buscar el dato, se recorre la lista desde su primer elementodado por Primero(L), mediante un puntero auxiliar. Por cada elemento recorrido se extraeel dato que contiene mediante la funcin Dato(L,aux,d). Si el dato coincide con el


buscado, se devuelve su posicin y si no coincide se pasa al siguiente mediante laoperacin Siguiente(L,aux). El recorrido finaliza cuando hemos encontrado el elemento(d=e) o cuando hemos recorrido todos los elementos (aux=NIL).

PROCEDURE Almacenar (VAR L: TipoLista; d: TipoBase );VAR

aux: Posicion;BEGIN

new(aux);aux^.info := d;aux^.sig := NIL;IF ListaVacia(L) THEN

L.primero := auxELSE

L.ultimo^.sig := aux;L.ultimo := aux;L.longitud := L.longitud+1

END;

Supongamos que partimos de una lista como la siguiente:

C NILL.primero A B

L.ultimoL.longitud=3

Para almacenar un elemento al final debemos recorrer los siguientes pasos:

En primer lugar creamos un nuevo nodo mediante la operacin new(aux).

A continuacin rellenamos los dos campos del nodo. El campo info con el valord pasado como parmetro. Dado que el nuevo elemento va a ser el ltimo de lalista, el campo sig se rellena con NIL.

C NILL.primero A B


d NIL

aux

Si la lista estaba vaca, el campo L.primero debe apuntar al nuevo nodo aadido,

en caso contrario, debemos enlazar el ltimo nodo de la lista con el recin creado:L.ultimo^.sig := aux

CL.primero A B


d NIL

aux

Al almacenar el elemento al final, el campo L.ultimo pasar a apuntar al nuevonodo y el campo L.longitud se incrementar en 1.


CL.primero A B


d NIL

aux

PROCEDURE InsAntes (VAR L: TipoLista; p: Posicion; d: TipoBase );VAR

aux1,aux2: Posicion;BEGIN

new(aux1);aux1^.info := d;IF ListaVacia(L) THEN BEGIN

L.primero := aux1;L.ultimo := aux1;aux1^.sig := NIL

END

ELSE

IF p = Primero(L) THEN BEGINaux1^.sig := Primero(L);L.primero := aux1

END

ELSE BEGIN { cualquier posicin }aux2 := Anterior (L, p);aux2^.sig := aux1;aux1^.sig := p

END;

L.longitud := L.longitud+1END;

A la hora de insertar un elemento antes de una posicin dada, debemos considerartres casos posibles:

1. Que la lista este vaca2. Que la insercin se realice al principio de la lista3. Que la insercin se realice en cualquier otra posicin de la lista

En los tres casos debemos comenzar por crear el nuevo nodo y almacenar en su campoinfo la informacin pertinente, y debemos finalizar incrementando la longitud de la listaen 1.

1. Insercin en una lista vaca

L.primeroL.ultimo

L.longitud=0

dNIL

aux1

NILL.primero

L.ultimo

L.longitud=1

d

aux1

NIL

Antes Despus


2. Insercin al principio de la lista

L.primero A


d

aux1

B NIL L.primero A


d

aux1

B NIL

Antes Despus

2. Insercin a partir del primer elementoEn este caso debemos insertar el nuevo nodo entre el apuntado por p y elanterior. Esto es, debemos hacer que el anterior apunte al nuevo nodo y que elnuevo nodo apunte a p. Para ello, lo primero que haremos es localizar el nodoanterior a p utilizando la operacin Anterior(L,p).

L.primero A

L.longitud=5

d

aux1

B

Antes

p

aux2=Anterior(L,p)

L.primero A

L.longitud=6

d

aux1

B

Despus

p

aux2=Anterior(L,p)

PROCEDURE InsDepues (VAR L: TipoLista; p: Posicion; d: TipoBase );VAR

aux1: Posicion;BEGIN

new(aux1);aux1^.info := d;IF ListaVacia(L) THEN BEGIN


END

ELSE

IF p = Ultimo(L) THEN BEGINp^.sig := aux1;L.ultimo := aux1;aux1^.sig := NIL

END

ELSE BEGIN { cualquier posicin }aux1^.sig := p^.sig;p^.sig := aux1

END;



Para insertar despus de una posicin dada, de nuevo tenemos que contemplar trescasos:

1. Que la lista este vaca2. Que queramos insertar despus del ltimo3. Que queramos insertar en cualquier otra posicin

De nuevo debemos comenzar por crear el nuevo nodo y almacenar la informacin ensu campo info, y debemos finalizar incrementando en uno la longitud de la lista.

1. Si la lista est vaca se opera igual que en InsAntes.

2. Si queremos insertar despus del ltimo elemento

L.primero A

L.longitud=2

d

aux1

B

Antes

p

NIL

L.ultimo

L.primero A

L.longitud=3

d

aux1

B

Despus

p

NILL.ultimo

3. Si queremos insertar en cualquier otra posicin

L.primero A

L.longitud=5

d

aux1

B

Antes

p

L.primero A

L.longitud=6

d

aux1

B

Despus

p

PROCEDURE Modificar (VAR L: TipoLista; p: Posicion; d: TipoBase);BEGIN

p^.info := dEND;

Modificar un elemento de la lista cuya posicin pasamos como parmetro consistesimplemente en asignarle el nuevo valor a su campo info.


PROCEDURE Borrar ( VAR L: TipoLista; p: Posicion );VAR

aux: Posicion;BEGIN

IF p = Primero(L) THEN BEGINL.primero := p^.sig;IF Primero(L) = NIL THEN

L.ultimo := NILEND

ELSE BEGIN

aux := Anterior (L,p);aux^.sig := Siguiente (L,p);IF p = Ultimo(L) THEN

L.ultimo := auxEND;

dispose(p);L.longitud := L.longitud - 1

END;

A la hora de borrar un elemento de la lista debemos contemplar dos casos bsicos:que el elemento a borrar sea el primero o que no. En ambos casos debemos acabar porborrar el nodo mediante un dispose y disminuir la longitud de la lista en uno.

1. Si el elemento a borrar es el primero

L.primero A

L.longitud=5

B

Antes

p

L.primero A

L.longitud=4

B

Despus

p

Si adems el elemento borrado es el nico de la lista (Primero(L)=NIL),debemos hacer que L.ultimo apunte a NIL

2. Si el elemento a borrar no es el primero

En este caso debemos enlazar el nodo anterior a p con el siguiente a p. Para ellobuscamos el nodo anterior mediante la operacin Anterior(L,p).

L.primero A

L.longitud=5

B

Antes

p

B L.primero A

L.longitud=4

B

Despus

p

B

aux=Anterior(L,p) aux=Anterior(L,p)


Adems, si el nodo a borrar es el ltimo de la lista, debemos hacer que el campoL.ultimo apunte al anterior (aux).

5.3.3. Implementacin dinmica como lista doblemente enlazada

Uno de los problemas que plantea la implementacin dinmica mediante simple enlace esel coste de insertar y borrar nuevos elementos en la lista. En varios casos es necesariorecorrerla desde el principio para poder acceder al elemento anterior al dado comoparmetro. Adems, tan slo es posible recorrer una lista as enlazada en una soladireccin.

Para solucionar ambos problemas se puede utilizar una lista doblemente enlazada. Eneste caso, cada nodo de la lista apuntar tanto al anterior como al siguiente.

NILNIL

info

ant sig

Para implementar en Pascal este tipo de listas, utilizaremos las siguientesdefiniciones:

TYPE


info: ;ant, sig: Posicion

END;

TipoLista = RECORDlongitud: INTEGER;primero, ultimo : Posicion

END;

Con esta definicin de una lista doblemente enlazada, es necesario modificar algunasoperaciones del TAD Lista para poder adaptarlas al nuevo tipo de nodo utilizado.

En este apartado queda como ejercicio la justificacin de la implementacin de lasoperaciones mostradas.

FUNCTION Anterior (L : TipoLista; p: Posicion ):Posicion;BEGIN

Anterior := p^.antEND;


PROCEDURE InsAntes( VAR L: TipoLista; p: Posicion; d: TipoBase );VAR

aux : Posicion;BEGIN

new (aux);aux^.info := d;IF ListaVacia(L) THEN BEGIN

L.primero := aux;L.ultimo := aux;aux^.sig := NIL;aux^.ant := NIL

END

ELSE

IF p = Primero(L) THEN BEGINaux^.sig := Primero(L);L.primero^.ant := aux;aux^.ant := NIL;

L.primero := auxEND

ELSE BEGIN { cualquier posicin }aux^.ant := Anterior(L,p);aux^.sig := p;p^.ant^.sig := aux;p^.ant := aux

END;


PROCEDURE InsDespues( VAR L : TipoLista; p: Posicion; d: TipoBase );VAR

aux: Posicion;BEGIN

new(aux);aux^.info := d;IF ListaVacia(L) THEN BEGIN

aux^.sig := NIL;aux^.ant := NIL;

L.primero := aux;L.ultimo := aux

END

ELSE

IF p = Ultimo(L) THEN BEGINaux^.ant := Ultimo(L);L.ultimo^.sig := aux;


aux^.sig := NIL;L.ultimo := aux

END

ELSE BEGIN { cualquier posicin }aux^.ant := p;

aux^.sig := Siguiente (L,p);p^.sig^.ant := aux;p^.sig := aux

END;

L.longitud := L.longitud + 1END;

PROCEDURE Borrar ( VAR L: TipoLista; p: Posicion );VAR

aux1, aux2 : Posicion;BEGIN

IF p = Primero(L) THEN BEGINL.primero := Siguiente(L,p);IF Primero(L) = NIL THEN

L.ultimo := NILELSE

L.primero^.ant := NILEND

ELSE

IF p = Ultimo(L) THEN BEGINaux1 := Anterior (L,p);L.ultimo := aux1;aux1^.sig := NIL

END

ELSE BEGIN { Cualquier posicin }aux1 := Anterior (L,p);aux2 := Siguiente (L,p);aux1^.sig :=aux2;aux2^.ant :=aux1

END;

dispose(p);L.longitud := L.longitud - 1

END;

5.4. TAD's relacionados con la Lista

En funcin del problema que queramos resolver y de las caractersticas especficas quequeramos conseguir en una lista, existen toda una serie de variantes de este TAD. En esteapartado vamos a ver algunas de ellas, pero puede consultarse la literatura al respecto paraencontrar otras muchas.


5.4.1. TAD Lista Ordenada

Supongamos que queremos manejar una lista en la que sus distintos elementos estnordenados en funcin de su valor. En este caso podemos definir una variante del TADLista que denominaremos Lista Ordenada. Una definicin de este nuevo tipo de datospuede ser la siguiente:

Definicin

Una lista ordenada es una estructura lineal y homognea en la que se puedenaadir o eliminar elementos en cualquier posicin, pero de manera que loselementos siempre permanezcan ordenados segn algn criterio de ordenacin.

En el caso de las listas ordenadas el TAD asociado tendr una estructura similar a lavista en el apartado 5.1.2. Sin embargo, en este caso a la hora de insertar elementos nonecesitaremos indicar ninguna posicin, dado que sta quedar definida por su valor. Elnuevo elemento se insertar de modo que se mantenga el orden en la lista.TAD: ListaOrd

Operaciones:CreaListOrd: ListaOrdCrea una lista ordenada vaca.ListOrdVacia: ListaOrd LogicoDada una lista ordenada, nos dice si est vaca.Primero: ListaOrd PosicionDada una lista ordenada, nos devuelve la posicin de su primer elemento.Ultimo: ListaOrd PosicionDada una lista ordenada, nos devuelve la posicin de su ltimo elemento.Siguiente: ListaOrd x Posicion PosicionDada una lista ordenada y una posicin en la misma, nos devuelve la posicin delsiguiente elemento.Anterior: ListaOrd x Posicion PosicionDada una lista ordenada y una posicin en la misma, nos devuelve la posicin delelemento anterior.Almacenar: ListaOrd x Tipobase ListaOrdDada una lista ordenada y un dato del tipo base, inserta el dato en la ltima posicin dela lista.InsOrd: ListaOrd x TipoBase ListaOrdDada una lista ordenada y un elemento d, inserta el elemento en la lista en su posicincorrespondiente.Borrar: ListaOrd x Posicion ListaOrdDada una lista ordenada y una posicin p, borra de la lista el elemento indicado por laposicin.Dato: ListaOrd x Posicion TipoBaseDada una lista ordenada y una posicin en la misma, nos devuelve el valor del elementosituado en la misma.Buscar: ListaOrd x TipoBase Posicion


Dada una lista ordenada y un valor del tipo base, busca dicho valor en la lista y nosdevuelve su posicin.Longitud: ListaOrd EnteroDada una lista ordenada, nos devuelve su longitud.

Axiomas: L ListaOrd, p Posicion, e, f TipoBase,1) ListaOrdVacia(CrearListOrd) = cierto2) ListaOrdVacia(Almacenar(L,e)) = falso3) Longitud(CrearListOrd) = 04) Longitud(Almacenar(L,e)) = Longitud(L) + 15) InsOrd(CrearListOrd, e) = Almacenar(CrearListOrd, e)6) InsOrd(Almacenar(L, e), f) =

Si e


debemos actualizar el campo L.primero. La segunda situacin especial se da cuandoacabamos el recorrido de la lista sin encontrar ningn elemento mayor, es decir, cuandodebemos insertar el nuevo nodo en la ltima posicin de la lista. En este caso debemosactualizar el campo L.ultimo. El siguiente subprograma contempla todos los casoscitados.

PROCEDURE InsOrd (VAR L: TipoLista; d: TipoBase );VAR

aux1,aux2,ant : Posicion;BEGIN

new(aux1); aux1^.info := d;IF ListaOrdVacia(L) THEN BEGIN


END

ELSE

IF d = d) THEN BEGINaux1^.sig := aux2;ant^.sig := aux1

END

ELSE BEGIN { Se inserta despues del ultimo }aux1^.sig := NIL;L.ultimo^.sig := aux1;L.ultimo := aux1

END

END;

L.longitud := L.longitud + 1END;

5.4.2. TAD Multilista

En el apartado anterior hemos descrito el TAD Lista ordenada en el que los distintoselementos se ordenan en funcin del valor de los mismos. Sin embargo, supongamos quelos elementos de la lista no son simples, sino que se trata de datos compuestos tales comoregistros o vectores.


Imaginemos por ejemplo que estamos tratando con una lista de alumnos en la quedos de sus campos son los apellidos y el DNI del alumno. Puede interesarnos en ocasionesrecorrer los distintos alumnos por orden de apellidos y en otras ocasiones recorrerlos pororden de DNI. Si implementamos esta lista utilizando el TAD Lista Ordenada nos vemosforzados a elegir uno de los campos para enlazar los distintos elementos en orden. En estecaso extraer los elementos ordenados segn otro campo sera mucho ms costoso.

Para solucionar este problema se utilizan las multilistas. Se trata de una estructura enla que los distintos elementos se enlazan siguiendo el orden marcado por varioscomponentes de los datos. Estrictamente hablando una multilista no es una estructuralineal, puesto que cada elemento tiene ms de un anterior y ms de un siguiente. Podramosdecir que una multilista integra varias listas ordenadas, cada una de ellas en funcin de unacomponente o campo distinto de los datos almacenado.

Veamos un ejemplo:

Prez Vzquez,Antonio

12345678

5.5

Arrufat Smith,Juan

87654321

4.8

Einstein Lpez,Pedro

18273645

8.2

La estructura de datos que podemos utilizar en Pascal para implementar unamultilista como la anterior es la siguiente

TYPE

Alumno = RECORD

nombre, DNI: String;nota: REAL

END;

Posicion = ^ElemMultList;ElemMultList = RECORD

info: Alumno;signom, sigdni, signot: Posicion

END;

Multilista = RECORDprimernom, primerdni, primernot: Posicion

END;

Al implementar la Multilista hemos elegido una estructura dinmica de enlace simplepara representar cada una de las listas que contiene. Podramos haber elegido unaestructura esttica basada en vectores y registros o haber utilizado enlaces dobles para


alguna de las listas o para todas ellas. Tambin debemos darnos cuenta de que el tipoMultilista tan slo contiene un campo asociado a cada lista: el que apunta a su primerelemento. Otra opcin sera utilizar para cada una de ellas los tres campos que hemosutilizado con el TAD Lista.

Aunque no vamos a describir en detalle el TAD Multilista ni su posibleimplementacin, s es interesante resaltar algunos aspectos del mismo:

Las operaciones involucradas seran similares a las del TAD Lista Ordenada.

Sera necesario incluir una operacin Siguiente y una Anterior por cada uno de loscampos ordenados.

Al insertar un nuevo elemento se crear un nico nuevo nodo. El nuevo nodo seintegrar en cada una de las listas siguiendo el orden adecuado en cada caso.

Al borrar un elemento deberemos actualizar los enlaces asociados a todas laslistas, pero el nodo se eliminar una sola vez.

5.5. Ejercicios1. Se tiene implementada una lista de empleados de una empresa ordenada alfabticamente por

sus apellidos. Se desea reducir el tiempo de bsqueda de los datos de un empleado y paraello, el programador decide ampliar la estructura de datos aadiendo un vector cuyo ndiceson las iniciales de los apellidos, y cuyos elementos son los punteros al primer empleado cuyoapellido empiece por dicha inicial. Se pide:

a) La definicin de tipos necesaria.b) Determinar qu operaciones de lista se pueden modificar para mejorar su eficiencia con

esta nueva estructura y cules no.

c) Implementar las nuevas operaciones de lista (slo las mejorables).

2. Se dispone de una lista de simple enlace en la que la informacin almacenada es de tipoSTRING. La lista est ordenada por orden alfabtico.

Se pretende utilizar la lista para gestionar el orden en el que se ha de realizar una oposicin.El mecanismo habitual es seguir el orden alfabtico, pero no se comienza por la letra A, sinopor una letra extrada al azar: si, por ejemplo, sale la L, el ejercicio lo comienza el primercandidato cuyo apellido empiece por L, siguindose, a partir de ah, el orden alfabtico. Alacabar, se contina con el primero hasta que todos los candidatos se hayan examinado.

Sabiendo que nos darn como informacin de entrada la letra que salga por sorteo, se pide:

a) Implementar un algoritmo que a partir de la lista original, ordenada, y de la letra, devuelvaotra lista con la reordenacin indicada.

b) Implementar un algoritmo que a partir de la lista original, ordenada, y de la letra, devuelvala misma lista pero con la reordenacin indicada.

3. Dada una lista doblemente enlazada, que almacena informacin de tipo base TB, definir laoperacin BORRA_2, tal que dada la posicin de un elemento borre el anterior y el siguiente(si un elemento dado no tuviera anterior y/o siguiente, que borre lo que pueda).


4. Dada una lista de enlace simple, que almacena informacin de tipo base TB, definir dosimplementaciones de la operacin INVERTIR, tal que a partir de la lista original

a) se obtenga otra lista en la que los elementos de la original estn en orden inverso.b) se invierta, sobre la misma lista, el orden de los elementos.

5. Dada una lista, desordenada, que almacena informacin de tipo entero, escribir un algoritmoque obtenga dos listas ordenadas: en una aparecern los elementos pares de la lista originaly en la otra los impares.

6. Una finca tiene n pisos y en cada piso hay 5 viviendas identificadas como A, B, C, D y E. Porcada vivienda, un vecino paga una determinada cuota de gastos de escalera. El administradorde la finca sabe el nombre de cada vecino, su cuota y, adems, si est alquilado o si es elpropietario del piso; en el primer caso, debe saber, adems, el nombre del propietario del pisoy su nmero de cuenta corriente, puesto que es el propietario el que corre con los gastos deescalera. En el segundo caso, para poder realizar el cargo slo se debe saber el nmero decuenta del vecino.

a) Definicin completa de la estructura de datos que permita organizar dicha informacin.b) Realizar una operacin que permita al administrador sacar un listado en el que, para cada

una de las viviendas, se emita un recibo. Un recibo indica el piso, la puerta, el nombredel vecino, el nombre del propietario, la cuota y el nmero de cuenta donde se debenefectuar los cargos del recibo de la escalera.

c) Al cabo de 15 das desde la emisin del listado y su envo al banco con el que trabaja eladministrador, el banco devuelve una lista de recibos impagados, que el administradortransforma en una lista de morosos (teniendo en cuenta que puede haber alguien queposea ms de una vivienda en la finca).c.1) Definir las estructuras lista de recibos y lista de morosos. En la lista de morosos,debe constar el nombre, la cuenta corriente y el importe total de la deuda.

c.2) Escribir una operacin que permita transformar la lista de recibos impagados en lalista de morosos, sin modificar la lista de recibos.

7. En un teatro se identifica cada butaca por su nmero de fila y su nmero de butaca dentro deuna fila. En total hay N filas y M butacas por fila. Se quiere hacer un programa para el procesoautomtico de reservas del teatro, de forma que por cada butaca, adems de su precio, siest reservada se pueda saber quin la ha reservado.

a) Definir la estructura de datos teatro.b) Para realizar una reserva, adems del nombre de quien la hace, hay que indicar cuntos

asientos se reservan. Las reservas se deben almacenar en una lista, implementadadinmicamente que servir, adems, para cobrar la reserva en el momento del pago.

b.1) Definir la estructura de datos reserva.b.2) Definir la operacin Reservar que, dada la informacin del nombre y nmero deasientos, actualice la ocupacin del teatro y adems aada dicha informacin a la lista dereservas, incluyendo el precio. La reserva debe asegurar que los asientos seancorrelativos. Si no es posible, debe indicarlo.


b.3) Definir la operacin Cancelar que, dada la informacin del nombre, permitecancelar una reserva, eliminndola de la lista y liberando, adems, los asientoscorrespondientes.

8. En una determinada Universidad hay n campus, cada uno de ellos con m aulas informticasy cada aula con 20 puestos de trabajo. Cada uno de estos puestos de trabajo puede estarocupado o no con una conexin a la red. Caso de estarlo, el usuario quedar identificado porla siguiente informacin: su login y la tarea que est realizando. La tarea puede ser una solade estas cuatro: leer las news, hacer un write, acceder al correo electrnico o manejo delSistema Operativo.

Se desea escribir un algoritmo que permita a los operadores del sistema saber quin estconectado a la red; para ello, se quiere

a) La definicin de la estructura de datos que soporte la informacin descrita.b) Definir la estructura de datos ms adecuada para contener la salida de datos, si lo que se

quiere es la relacin de los "logins" de usuarios conectados. Escribir el algoritmo quepermita obtener dicha relacin.

c) Definir la estructura de datos ms adecuada para contener la salida de datos, si lo que sequiere es la relacin de los "logins", tarea, ordenador, aula informtica y campus de losusuarios conectados. Escribir el algoritmo que permita obtener dicha relacin.

Nota: Un "login" es una identificacin nica. Se supone que como mucho hay un nmeromximo de L "logins", L < 256.

9. Un profesor tiene un montn de exmenes y en cada momento slo puede acceder al examensituado encima del mismo. Por cada uno de ellos guarda el nombre del alumno, su dni y lanota de cada uno de los cinco ejercicios de que consta el examen.a) Definir las estructuras de datos ms adecuadas para almacenar la informacin del

problema.

b) El profesor quiere generar el acta en la que los distintos alumnos aparecen ordenadosalfabticamente. Por cada alumno debe guardar entonces su nombre, dni y la nota totalobtenida sumando la de los 5 ejercicios.b.1) Definir las estructuras de datos ms adecuadas para guardar la informacin.b.2) Implementar un procedimiento publicar que a partir del montn de exmenesgenere el acta. Al finalizar el proceso, el montn de exmenes debe quedar igual.

c) Implementar un procedimiento denominado maxnota que, a partir del acta, escriba elnombre y la nota del alumno que haya obtenido la mxima calificacin global.

d) Suponer que el profesor quiere poder recorrer el acta, tanto por orden alfabtico como pororden de la nota global de los distintos alumnos.

d.1) Modificar la estructura de datos del apartado b) para poder realizar esta operacin.d.2) Implementar el algoritmo recorrer que, en funcin de un argumento de entrada,permita recorrer el acta por orden de nombre o de nota. Por cada alumno, el algoritmodebe escribir su nombre y la nota total.

10. En una sucursal bancaria se pueden realizar ingresos, reintegros y consultas. La sucursaldispone de dos ventanillas, una de las cuales puede atender cualquier operacin (ventanilla


general), mientras que la otra slo puede realizar ingresos (ventanilla de ingresos). Losclientes, caracterizados por su NIF y la operacin que desean realizar, se atienden segn elorden de llegada, y pueden ser atendidos indistintamente por una u otra ventanilla en funcinde que estn libres en ese momento.

Si un cliente es atendido por la ventanilla de ingresos y no desea realizar esa operacin, sepasa a una dependencia donde esperan en orden de llegada todos los clientes en la mismasituacin. Todos los clientes de esta dependencia sern atendidos por la ventanilla general.Adems, tienen preferencia sobre los clientes que an no han visitado ninguna ventanilla.

Cada operacin realizada en la sucursal se registra ordenada por NIF del cliente en unaestructura denominada Operaciones en el momento de efectuarla. Por cada operacin sealmacena el NIF del cliente y la operacin realizada.

a) Definir las estructuras de datos ms adecuadas para almacenar la informacin delproblema.

b) Implementar las operaciones de atender un cliente en la ventanilla general y atenderlo enla ventanilla de ingresos.

c) Al finalizar la jornada se reordenan las operaciones efectuadas colocando en primer lugarlos ingresos, luego los reintegros y en tercer lugar las consultas, y dentro de cadamodalidad manteniendo el orden por NIF del cliente. Se pide realizar un algoritmo que apartir de la estructura Operaciones obtenga la estructura Operaciones por modalidad.

11 Escribir un algoritmo que permita intercambiar los elementos que ocupan las posiciones m y nde una lista dinmica de elementos de tipo . Tener en cuenta que no puedemodificarse el valor contenido en los nodos de la lista y que 1

Documents

Listas