ides

Fundamentos de Programación II

Tema 3. Estructuras lineales de
datos: listas, pilas, colas

Luís Rodríguez Baena (luis.rodriguez@upsam.net)
Universidad Pontificia de Salamanca (campus Madrid)
Escuela Superior de Ingeniería y Arquitectura

Tipos abstractos de datos
Procedimientos y funciones generalizan el concepto de operador.
● El programador puede definir sus propios operadores yaplicarlos sobre
operandos de tipos no definidos en el lenguaje.
En un algoritmo en lugar de utilizar sólo los operadores que utiliza el lenguaje,
mediante procedimientos y funciones se pueden aplicar sus propios operandos a
tipos de datos no definidos por el lenguaje.
o Por ejemplo, se puede ampliar el operador de multiplicación para multiplicar
matrices.

● Procedimientos y funcionesencapsulan las operaciones, las aíslan del
cuerpo del algoritmo.

Tipo Abstracto de Datos (TAD).
● Amplía el concepto de procedimiento a la definición de datos.
● Modelo matemático del dato junto con las operaciones que se pueden
definir sobre él.
● Utilizan también generalización y encapsulamiento.
Son generalizaciones de los tipos de datos primitivos.
Facilitan la localización de ladefinición del tipo y de las operaciones para su
manejo.

Universidad Pontificia de Salamanca (Campus Madrid)
Luis Rodríguez Baena, Escuela Superior de Ingeniería y Arquitectura, 2012

2

Tipos abstractos de datos (II)
Por ejemplo, se puede definir el tipo de datos Cuadrado y las
operaciones Área(c) y Perímetro(c)que devolverían el
valor del área y del perímetro del cuadrado c.
El cuadradose puede implementar de distintas formas:
● Con la posición de los cuatro vértices en las coordenadas de un
plano.
registro=punto
real : x,y
fin_registro
registro=cuadrado
punto: infIzq, infDer, supIzq, supDer
fin_registro

● Con la posición de un punto y el tamaño del lado.
registro=cuadrado
punto:origen
real: lado
fin_registro

Universidad Pontificia de Salamanca (Campus Madrid)Luis Rodríguez Baena, Escuela Superior de Ingeniería y Arquitectura, 2012

3

Tipos abstractos de datos (III)
El procedimiento área podría implementarse de distintas formas
dependiendo de cómo se haya definido el cuadrado.
real función Área(valor cuadrado: c)
inicio
devolver(c.lado * c.lado)
fin_función
real función Área(valor cuadrado: c)
var
real : lado
inicio
//lado es ladistancia entre dos puntos
lado
raiz2((c.infIzq.x – infDer.x)**2+(c.infIzq.y – infDer.y)**2)
devolver(lado * lado)
fin_función

● Si en un programa utilizamos el tipo de datos Cuadrado y tenemos definidas
en ese tipo de dato la función Área, la llamada a la función será Area(c),
independientemente de la implementación que hayamos hecho.
Universidad Pontificia de Salamanca (Campus Madrid)
LuisRodríguez Baena, Escuela Superior de Ingeniería y Arquitectura, 2012

4

Tipos abstractos de datos (IV)
Estructuras de datos “físicas” y “lógicas”.
● Podemos considerar que una estructura de datos física es la que
implementa el lenguaje de programación que se está utilizando.
● Una estructura de datos lógica sería una estructura de datos que no
implementa el lenguaje y que creamos apartir de los tipos de datos
y las estructuras de datos físicas que proporciona el lenguaje.
● Este concepto puede variar de un lenguaje a otro:
Conjunto: presente en Pascal y no presente en C.
Cadena: presente en Java, pero no presente en Pascal estándar.
Archivos indexados: presente en Cobol y no presente en C.

Las estructuras de datos que se han utilizado hasta ahora ya
estaban definidaspor el lenguaje de especificación de
algoritmos utilizado (son estructuras de datos “físicas”).
● El lenguaje define el tipo array e incluye las herramientas
necesarias para declarar un array, acceder a un elemento, etc.

Universidad Pontificia de Salamanca (Campus Madrid)
Luis Rodríguez Baena, Escuela Superior de Ingeniería y Arquitectura, 2012

5

Tipos abstractos de datos (V)
Los...