PDF de programación - Especificación algebraica de TADs Ejemplos: Pilas, Colas, Listas - Estructuras de Datos y Algoritmos

Imágen de pdf Especificación algebraica de TADs Ejemplos: Pilas, Colas, Listas - Estructuras de Datos y Algoritmos

Especificación algebraica de TADs Ejemplos: Pilas, Colas, Listas - Estructuras de Datos y Algoritmosgráfica de visualizaciones

Publicado el 15 de Enero del 2019
784 visualizaciones desde el 15 de Enero del 2019
870,8 KB
20 paginas
Creado hace 5a (11/02/2015)
Estructuras de Datos 

y Algoritmos

Especificación algebraica de TADs

Ejemplos: Pilas, Colas, Listas

Prof. Dr. P. Javier Herrera

Índice

Ejemplos de especificación algebraica de TADs.

– Pila
– Cola
– Lista

Tema 1. Tipos abstractos de datos ‐ Curso 2014/15

22

Pila (Stack)

Tema 1. Tipos abstractos de datos ‐ Curso 2014/15

3

Pila ‐ Aplicaciones

• Almacenamiento de datos locales 
y la información de llamadas para 
las llamadas a procedimientos 
anidados

Tema 1. Tipos abstractos de datos ‐ Curso 2014/15

4

Pila ‐ Aplicaciones

• Evaluación de la expresión y el análisis sintáctico. 

• Por ejemplo, el cálculo ((1 + 2) * 4) + 3, puede ser anotado como en 

notación postfija con la ventaja de no prevalecer las normas y los 
paréntesis necesario: 1 2 + 4 * 3 +

• Backtracking (Vuelta atrás): es una estrategia para encontrar soluciones a 

problemas que satisfacen restricciones

• Gestión de memoria en tiempo de ejecución

Tema 1. Tipos abstractos de datos ‐ Curso 2014/15

5

Pila ‐ Operaciones básicas



El TAD de las pilas cuenta con las siguientes operaciones:

– crear la pila vacía,
– apilar un elemento,
– desapilar el elemento en la cima,
– consultar el elemento en la cima, y
– determinar si la pila es vacía.

Tema 1. Tipos abstractos de datos ‐ Curso 2014/15

6
6

Pila ‐ Especificación algebraica

especificación PILAS[ELEM]
usa BOOLEANOS
tipos pila
operaciones

pila-vacía
apilar
desapilar
cima
es-pila-vacía?

:
: elemento pila
: pila
: pila
: pila

{ constructora }
{ constructora }

→ pila
→ pila
→p pila
→p elemento
→ bool



Como el orden de apilación es fundamental para la posterior consulta y eliminación, las 
constructoras son libres (no son necesarias ecuaciones de equivalencia).

Tema 1. Tipos abstractos de datos ‐ Curso 2014/15

7
7

Pila ‐ Especificación algebraica

variables

e : elemento
p : pila
ecuaciones

desapilar(pila-vacía)
desapilar(apilar(e, p))

cima(pila-vacía)
cima(apilar(e, p))

= error
= p

= error
= e

es-pila-vacía?(pila-vacía)
= cierto
es-pila-vacía?(apilar(e, p)) = falso

fespecificación

Tema 1. Tipos abstractos de datos ‐ Curso 2014/15

8
8

Cola (queue)

Tema 1. Tipos abstractos de datos ‐ Curso 2014/15

9

Cola ‐ Aplicaciones

• Cola de impresión

Tema 1. Tipos abstractos de datos ‐ Curso 2014/15

10

Cola ‐ Operaciones básicas



El TAD de las colas cuenta con las siguientes operaciones:

– crear la cola vacía,
– añadir un elemento al final de la cola,
– eliminar el primer elemento en la cola,
– consultar el primer elemento, y
– determinar si la cola es vacía.

Tema 1. Tipos abstractos de datos ‐ Curso 2014/15

11
11

Cola ‐ Especificación algebraica

especificación COLAS[ELEM]
usa BOOLEANOS
tipos cola
operaciones

cola-vacía
pedir-vez
avanzar
primero
es-cola-vacía?

:
: cola elemento
: cola
: cola
: cola

{ constructora }
{ constructora }

→ cola
→ cola
→p cola
→p elemento
→ bool



El orden de inserción de los elementos en la cola determina la cola, por lo que las 
constructoras son libres. No son necesarias ecuaciones de equivalencia.

Tema 1. Tipos abstractos de datos ‐ Curso 2014/15

12
12

Cola ‐ Especificación algebraica

variables

e : elemento
c : cola
ecuaciones

avanzar(cola-vacía)
avanzar(pedir-vez(c, e))
avanzar(pedir-vez(c, e))

primero(cola-vacía)
primero(pedir-vez(c, e))
primero(pedir-vez(c, e))

= error

= cola-vacía ⇐ es-cola-vacía?(c)
= pedir-vez(avanzar(c), e) ⇐ ¬es-cola-vacía?(c)
= e⇐ es-cola-vacía?(c)
= primero(c) ⇐ ¬es-cola-vacía?(c)

= error

es-cola-vacía?(cola-vacía) = cierto
es-cola-vacía?(pedir-vez(c, e)) = falso

fespecificación

Tema 1. Tipos abstractos de datos ‐ Curso 2014/15

13
13

Lista (List)

Tema 1. Tipos abstractos de datos ‐ Curso 2014/15

14

Lista ‐ Aplicaciones

• Generalización de las pilas y las colas. Puede ser usada para implementar 

otras estructuras de datos.

Tema 1. Tipos abstractos de datos ‐ Curso 2014/15

15

Lista ‐ 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 1. Tipos abstractos de datos ‐ Curso 2014/15

16
16

Lista ‐ 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 1. Tipos abstractos de datos ‐ Curso 2014/15

17
17

Lista ‐ 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 1. Tipos abstractos de datos ‐ Curso 2014/15

18
18

Lista ‐ 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 1. Tipos abstractos de datos ‐ Curso 2014/15

19
19

Bibliografía

• Martí, N., Ortega, Y., Verdejo, J.A. Estructuras de datos y métodos algorítmicos. Ejercicios 

resueltos. Pearson/Prentice Hall, 2003. Capítulos 1, 3, 4, 5



Peña, R.; Diseño de programas. Formalismo y abstracción. Tercera edición. Prentice Hall, 
2005. Capítulos 5, 6

Tema 1. Tipos abstractos de datos ‐ Curso 2014/15

20
  • Links de descarga
http://lwp-l.com/pdf14857

Comentarios de: Especificación algebraica de TADs Ejemplos: Pilas, Colas, 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