PDF de programación - Tema 4.3. Tipos de datos lineales. Listas - Estructuras de Datos y Algoritmos

Imágen de pdf Tema 4.3. Tipos de datos lineales. Listas - Estructuras de Datos y Algoritmos

Tema 4.3. Tipos de datos lineales. Listas - Estructuras de Datos y Algoritmosgráfica de visualizaciones

Publicado el 4 de Enero del 2019
661 visualizaciones desde el 4 de Enero del 2019
290,8 KB
31 paginas
Creado hace 8a (23/04/2015)
Estructuras de Datos 

y Algoritmos

Tema 4.3. Tipos de datos lineales.

Listas

Prof. Dr. P. Javier Herrera

Contenido









Listas: Conceptos generales
Operaciones básicas
Especificación algebraica
Implementación dinámica
Extensión de operaciones
Extensión de la especificación algebraica
Extensión de la implementación dinámica

Tema 4.3. Listas

22

Listas: Conceptos generales











Vivimos rodeados de listas: la lista de la compra, la lista de regalos de boda, la lista de libros 
para el próximo curso, etc., siendo el denominador común de todas estas listas el establecer 
una ordenación entre sus elementos.

Las listas son las estructuras de datos lineales más flexibles, puesto que su única 
característica es imponer un orden entre los elementos almacenados en ellas.

Según este criterio, las pilas y las colas serían casos particulares de listas, donde se ha 
restringido la forma de acceso a la estructura.

No existe una visión unánime de las listas como TAD, con un conjunto básico de operaciones.

Se trata de un tipo de datos parametrizado, donde el comportamiento de las operaciones 
sobre los valores del tipo lista es independiente de la naturaleza de los elementos que la 
componen.

Tema 4.3. Listas

3
3

Operaciones básicas



Un posible TAD de las listas cuenta con las siguientes operaciones:

– crear la lista vacía,
– generar una lista unitaria formada por un elemento dado,
– añadir un elemento por la izquierda,
– añadir un elemento por la derecha,
– consultar el elemento más a la izquierda,
– consultar el elemento más a la derecha,
– eliminar el elemento más a la izquierda,
– eliminar el elemento más a la derecha,
– determinar si una lista es vacía,
– concatenar dos listas, y
– calcular la longitud de una lista.

Tema 4.3. Listas

4
4

Especificación algebraica

especificación LISTAS[ELEM]
usa BOOLEANOS, NATURALES
tipos lista
operaciones

[ ]
_ : _
[ _ ]
_ # _
izquierdo
elim-izq
derecho
elim-der
es-lista-vacía?
_ ++ _
longitud

:
: elemento lista
: elemento
: lista elemento
: lista
: lista
: lista
: lista
: lista
: lista lista
: lista

{ constructora }
{ constructora }

→ lista
→ lista
→ lista
→ lista
→p elemento
→p lista
→p elemento
→p lista
→ bool
→ lista
→ nat

Tema 4.3. Listas

5
5

Especificación algebraica

variables

: elemento

e, f
x, y, z : lista

ecuaciones

= e : [ ]

[e]
x # e = x ++ [e]

izquierdo([ ])
izquierdo(e : x) = e

= error

elim-izq([ ])
elim-izq(e : x)

= error
= x

= error

derecho([ ])
derecho(e : [ ]) = e
derecho(e : f : x) = derecho(f : x)

Tema 4.3. Listas

6
6

Especificación algebraica

= error

elim-der([ ])
elim-der(e : [ ]) = [ ]
elim-der(e : f : x) = e : elim-der(f : x)

es-lista-vacía?([ ]) = cierto
es-lista-vacía?(e : x) = falso

[ ] ++ y
(e : x) ++ y

= y
= e : (x ++ y)

longitud([ ])
longitud(e : x)

= 0
= 1 + longitud(x)

fespecificación



También podemos considerar como constructoras la operación que crea la lista vacía y la que 
añade un elemento por la derecha (situación simétrica a la anterior); o bien elegir la lista 
vacía, la operación de construcción de la lista unitaria y la operación de concatenación.

Tema 4.3. Listas

7
7

Implementación dinámica







Los elementos de una lista se representan mediante una sucesión de nodos doblemente 
enlazados: cada nodo, además del valor del elemento concreto almacenado, contiene 
enlaces al nodo siguiente y al anterior en la sucesión.

La ventaja de tener estos dobles enlaces es que así se pueden eliminar elementos por ambos 
extremos de la lista con un coste en tiempo constante.

Una lista será un registro con un campo que guarda la longitud de la lista y enlaces a los 
nodos más a la izquierda y más a la derecha de la sucesión.

Tema 4.3. Listas

8
8

Implementación dinámica

tipos

enlace-lista
nodo-lista

= puntero a nodo-lista
= reg

valor : elemento
sig, ant : enlace-lista

lista

freg
= reg

longitud : nat
izquierdo, derecho : enlace-lista

freg

ftipos

Tema 4.3. Listas

9
9

Implementación dinámica



La lista vacía no tiene elementos, por lo que la longitud es cero, y como no hay elementos, 
los punteros izquierdo y derecho son nulos.

fun lista-vacía() dev l : lista

 1O
{ }

l.longitud := 0
l.izquierdo := nil
l.derecho := nil

ffun



Una lista es vacía cuando los punteros (uno o ambos, pues ambas condiciones son 
equivalentes) son nulos pues eso significa que no hay nodos en la estructura.

fun es-lista-vacía?(l : lista) dev r : bool

r := (l.izquierdo = nil)

 1O
{ }

ffun

Tema 4.3. Listas

10
10

Implementación dinámica



Añadir un elemento por la izquierda consiste en reservar memoria para un nuevo nodo, 
almacenar en él el nuevo elemento, y enlazarlo con la estructura, distinguiendo el caso en el 
que la lista inicial sea vacía. En cualquier caso la longitud de la lista aumenta en una unidad.

proc añadir-izq(e e : elemento, l : lista)
var p : enlace-lista

 1O
{ }

reservar(p)
p↑.valor := e ; p↑.ant := nil
si l.izquierdo = nil entonces

p↑.sig := nil ; l.derecho := p

si no

{ l es vacía }

p↑.sig := l.izquierdo ; (l.izquierdo)↑.ant := p

fsi
l.izquierdo := p
l.longitud := l.longitud + 1

fproc

Tema 4.3. Listas

11
11

Implementación dinámica



Añadir un elemento por la derecha es la operación simétrica.

proc añadir-der(l : lista, e e : elemento)
var p : enlace-lista

 1O
{ }

reservar(p)
p↑.valor := e ; p↑.sig := nil
si l.derecho = nil entonces

p↑.ant := nil ; l.izquierdo := p

si no

p↑.ant := l.derecho ; (l.derecho)↑.sig := p

fsi
l.derecho := p
l.longitud := l.longitud + 1

fproc

Tema 4.3. Listas

12
12

Implementación dinámica



Construir una lista unitaria a partir de un elemento dado consiste en crear una nueva lista 
con un único nodo que es apuntado tanto por izquierdo como por derecho. La longitud es 1.

fun unitaria(e : elemento) dev l : lista
var p : enlace-lista

 1O
{ }

reservar(p)
p↑.valor := e
p↑.ant := nil ; p↑.sig := nil
l.izquierdo := p ; l.derecho := p
l.longitud := 1

ffun

Tema 4.3. Listas

13
13

Implementación dinámica





El elemento más a la izquierda de una lista no vacía se obtiene accediendo al campo valor del 
nodo apuntado por izquierdo. Si la lista es vacía se produce un mensaje de error. 
La operación derecho es simétrica.

fun izquierdo(l : lista) dev e : elemento

 1O
{ }
si l.izquierdo = nil entonces error(Lista vacía)
si no e := (l.izquierdo)↑.valor
fsi

ffun

fun derecho(l : lista) dev e : elemento

 1O
{ }
si l.derecho = nil entonces error(Lista vacía)
si no e := (l.derecho)↑.valor
fsi

ffun

Tema 4.3. Listas

14
14

Implementación dinámica



Para eliminar el izquierdo se libera el primer nodo de la estructura, dejándola bien enlazada. 
Las operaciones derecho y elim-der son simétricas a las dos anteriores.

proc elim-izq(l : lista)
var p : enlace-lista

 1O
{ }

si l.izquierdo = nil entonces error(Lista vacía)
si no

p := l.izquierdo ; l.izquierdo := p↑.sig
si l.izquierdo = nil entonces l.derecho := nil
si no (l.izquierdo)↑.ant := nil
fsi
l.longitud := l.longitud − 1
liberar(p)

fsi
fproc

Tema 4.3. Listas

15
15

Implementación dinámica



La operación elim-der es simétrica.

proc elim-der(l : lista)
var p : enlace-lista

 1O
{ }

si l.derecho = nil entonces error(Lista vacía)
si no

p := l.derecho ; l.derecho := p↑.ant
si l.derecho = nil entonces l.izquierdo := nil
si no (l.derecho)↑.sig := nil
fsi
l.longitud := l.longitud − 1
liberar(p)

fsi
fproc

Tema 4.3. Listas

16
16

Implementación dinámica



La lista resultado de concatenar las dos listas que recibe como argumento, comienza siendo 
una copia de la primera lista. A continuación se recorre la sucesión de nodos de la segunda 
lista, añadiendo cada elemento por la derecha a la lista resultado. El coste en tiempo de 
concatenar es lineal respecto a la suma de las longitudes  de las listas concatenadas.

 
y
O
{ }


longitud

 
x



longitud

fun concatenar(x, y : lista) dev z : lista
var p : enlace-lista

z := lista-vacía() ; p := x.izquierdo
mientras p ≠ nil hacer

añadir-der(z, p↑.valor) ; p := p↑.sig

fmientras
p := y.izquierdo
mientras p ≠ nil hacer

añadir-der(z, p↑.valor) ; p := p↑.sig

fmientras

ffun

Tema 4.3. Listas

17
17

Implementación dinámica





Si se implementara la operación concatenar mediante un procedimiento, se podría conseguir 
un coste constante modificando el primer argumento para que también fuera el resultado, 
para lo cual bastaría encadenar el nodo derecho de x con el izquierdo de y, y sumar las dos 
longitudes.

La longitud de una lista se obtiene consultando el campo correspondiente, con un coste en 
tiempo constante.

 1O
fun longitud(l : lista) dev n : nat { }

n := l.longitud

ffun

Tema 4.3. Listas

18
18

Extensión de operaciones



Extender la especificación para considerar las siguientes operaciones:

– determinar si un elemento aparece en una lista,
– localizar la posición de un elemento (devolviendo 0 si el elemento no está),
– calcular el número de repeticiones de un elemento,
– eliminar todas las apariciones de un elemento,
– determinar si dos listas son iguales,
– determinar si una lista es capicúa,
– consultar el elemento en una posición,
– insertar un elemento en una posición,
– eliminar el elemento en una posición, y
– modificar el elemento en una posición.

Tema 4.3. Listas

19
19

Extensión de la especificación algebraica

especificación LISTAS+[ELEM=]
usa LISTAS[ELEM=], NATURALES, BOOLEANOS
operaciones

está?
posición
repeticiones
eliminar
_ == _
es-capicúa?
_ [ _ ]
insertar
eliminar
modificar

variables

: elemento lista → bool
: elemento lista → nat
: elemento lista → nat
: elemento lista → lista
: lista lista
→ bool
→ bool
: lista
→p elemento
: lista nat
: lista nat elemento →p lista
→p
  • Links de descarga
http://lwp-l.com/pdf14758

Comentarios de: Tema 4.3. Tipos de datos lineales. Listas - Estructuras de Datos y Algoritmos (0)


No hay comentarios
 

Comentar...

Nombre
Correo (no se visualiza en la web)
Valoración
Comentarios...
CerrarCerrar
CerrarCerrar
Cerrar

Tienes que ser un usuario registrado para poder insertar imágenes, archivos y/o videos.

Puedes registrarte o validarte desde aquí.

Codigo
Negrita
Subrayado
Tachado
Cursiva
Insertar enlace
Imagen externa
Emoticon
Tabular
Centrar
Titulo
Linea
Disminuir
Aumentar
Vista preliminar
sonreir
dientes
lengua
guiño
enfadado
confundido
llorar
avergonzado
sorprendido
triste
sol
estrella
jarra
camara
taza de cafe
email
beso
bombilla
amor
mal
bien
Es necesario revisar y aceptar las políticas de privacidad