PDF de programación - Tema 1. Tipos Abstractos de Datos - Programación II

Programación II
Tema 1. Tipos Abstractos de Datos

Iván Cantador y Rosa Mª Carro
Escuela Politécnica Superior
Universidad Autónoma de Madrid

Contenidos

1

• Tipos Abstractos de Datos (TAD)
• Ejemplos de TAD

• TAD Cadena de caracteres
• TAD Número complejo
• TAD Conjunto

• Implicaciones de los TAD
• Programación Orientada a Objetos (POO)

Programación II – Tema 1: Tipos Abstractos de Datos

Escuela Politécnica Superior

Universidad Autónoma de Madrid

Contenidos

2

• Tipos Abstractos de Datos (TAD)
• Ejemplos de TAD

• TAD Cadena de caracteres
• TAD Número complejo
• TAD Conjunto

• Implicaciones de los TAD
• Programación Orientada a Objetos (POO)

Programación II – Tema 1: Tipos Abstractos de Datos

Escuela Politécnica Superior

Universidad Autónoma de Madrid

Tipos Abstractos de Datos (TAD)
• Tipo Abstracto de Datos (TAD)

3

• Conjunto de datos con entidad propia (identidad definida) y 

funciones primitivas (operaciones básicas) aplicables sobre esos 
datos
• Ejemplo de TAD: NumeroComplejo

• Datos: componente real + componente imaginaria
• Primitivas: conjugado, módulo, suma, resta, …

• Importante: funciones adicionales del TAD se construirán sólo a 

partir de sus primitivas

• Estructura de Datos (EdD)

• Tipos de datos concretos con los que representar los datos del 
TAD y a partir de los que implementar las funciones primitivas
• Ejemplos de EdD para el TAD NumeroComplejo: 

float cReal, cImaginaria;

float componentes[2];

Programación II – Tema 1: Tipos Abstractos de Datos

Escuela Politécnica Superior

Universidad Autónoma de Madrid

Tipos Abstractos de Datos (TAD)
• Tipo Abstracto de Datos (TAD)

4

• Conjunto de datos con entidad propia (identidad definida) y 

funciones primitivas (operaciones básicas) aplicables sobre esos 
datos
• Ejemplo de TAD: NumeroComplejo

• Datos: componente real + componente imaginaria
• Primitivas: conjugado, módulo, suma, resta, …

• Importante: funciones adicionales del TAD se construirán sólo a 

partir de sus primitivas

• Estructura de Datos (EdD)

• Tipos de datos concretos con los que representar los datos del 
TAD y a partir de los que implementar las funciones primitivas
• Ejemplos de EdD para el TAD NumeroComplejo: 

float cReal, cImaginaria;

float componentes[2];

Programación II – Tema 1: Tipos Abstractos de Datos

Escuela Politécnica Superior

Universidad Autónoma de Madrid

Tipos Abstractos de Datos (TAD)
• Tipo Abstracto de Datos (TAD)

5

• Conjunto de datos con entidad propia (identidad definida) y 

funciones primitivas (operaciones básicas) aplicables sobre esos 
datos
• Ejemplo de TAD: NumeroComplejo

• Datos: componente real + componente imaginaria
• Primitivas: conjugado, módulo, suma, resta, …

• Importante: funciones adicionales del TAD se construirán sólo a 

partir de sus primitivas

• Estructura de Datos (EdD)

• Tipos de datos concretos con los que representar los datos del 
TAD y a partir de los que implementar las funciones primitivas
• Ejemplos de EdD para el TAD NumeroComplejo: 

float cReal, cImaginaria;

float componentes[2];

Programación II – Tema 1: Tipos Abstractos de Datos

Escuela Politécnica Superior

Universidad Autónoma de Madrid

Tipos Abstractos de Datos (TAD)

6

• Todo TAD se definirá como un modelo abstracto de unos 

elementos (datos) y unas operaciones (primitivas) sin 
tener en cuenta sus estructura e implementación 
particulares
• TAD Número complejo: módulo, conjugado, suma, resta, 

producto, cociente, …

• TAD Conjunto : tamaño, complemento, unión, intersección, …
• TAD Lista: inserción de un elemento, búsqueda de un elemento, 

eliminación de un elemento, visualización, …

• TAD Grafo: creación de un grafo vacío, inserción de un vértice, 
inserción de una arista, eliminación de un vértice, eliminación 
de una arista, distancia entre dos vértices, …

Programación II – Tema 1: Tipos Abstractos de Datos

Escuela Politécnica Superior

Universidad Autónoma de Madrid

Tipos Abstractos de Datos (TAD)

7

• Abstracciones en un TAD
• Abstracción de los datos
• Abstracción de las funcionalidades

interfaz pública

funciones primitivas

TAD

f5

f1

datos

f4

f2

f3

Programación II – Tema 1: Tipos Abstractos de Datos

Escuela Politécnica Superior

Universidad Autónoma de Madrid

Tipos Abstractos de Datos (TAD)
• Abstracciones en un TAD
• Abstracción de los datos

8

‐ Encapsulamiento de los datos, sin permitir su acceso directo, 

que se realizará sólo mediante funcionalidades definidas al 
efecto

‐ Ej.:

Complejo c = complejo_crear(2.0, -5.0)
real r = complejo_getParteReal(c)

• Abstracción de las funcionalidades

‐ Ocultación de la implementación de las funcionalidades a 
través de funciones primitivas, constituyendo la interfaz de 
acceso y manejo de los datos internos

‐ Ej.:  real m = complejo_modulo(c)

Complejo c = complejo_sumar(c1, c2)

Programación II – Tema 1: Tipos Abstractos de Datos

Escuela Politécnica Superior

Universidad Autónoma de Madrid

Tipos Abstractos de Datos (TAD)

9

• Abstracción de los datos

• Posibilita la definición y posterior (re)utilización de nuevos tipos 
de datos, dando a conocer sus posibles valores y las operaciones 
que trabajen sobre ellos, y evitando tener que conocer/entender 
su estructura interna
‐ El acceso a los valores de dichos datos se realiza sólo 

mediante las operaciones definidas sobre dicho TAD, sin 
preocuparnos de cómo son representados y tratados 
internamente

Programación II – Tema 1: Tipos Abstractos de Datos

Escuela Politécnica Superior

Universidad Autónoma de Madrid

Tipos Abstractos de Datos (TAD)

10

• Abstracción de las funcionalidades

• Permite la realización de determinadas acciones sobre los datos 
sin tener que conocer cómo se hacen, en qué tiempo y con qué 
recursos; Dichas acciones:
‐ Representan las operaciones más significativas
‐ Tienen normalmente una relación casi directa entre las 

abstracciones funcionales obtenidas en el diseño 
descendente: subproblemas

Programación II – Tema 1: Tipos Abstractos de Datos

Escuela Politécnica Superior

Universidad Autónoma de Madrid

Tipos Abstractos de Datos (TAD)
1. Especificación del TAD

11

• ¿Qué nombre darle?
• ¿Qué datos (nombres, tipos, valores restringidos) tiene?
• ¿Cuáles (nombres,entradas,salidas) son sus funciones primitivas 

fundamentales, que acceden/modifican sus atributos?

• ¿Cuáles son funciones derivadas que se pueden implementar a 

partir de las fundamentales?

2. Definición de la EdD
3. Atendiendo a la EdD elegida, pseudocódigo e 

implementación de las primitivas fundamentales y 
derivadas

4. Documentación del código (especialmente la interfaz)

Programación II – Tema 1: Tipos Abstractos de Datos

Escuela Politécnica Superior

Universidad Autónoma de Madrid

12

Este
tema

Ejemplos de TAD
• TAD Cadena de caracteres
• Lista ordenada de caracteres

• TAD Número complejo

• Número complejo, con parte real y parte imaginaria

• TAD Conjunto

• Colección de elementos no repetidos

• Algunos otros TAD

• TAD Pila
• TAD Cola
• TAD Lista enlazada
• TAD Árbol
• TAD Grafo

Programación II

Programación II – Tema 1: Tipos Abstractos de Datos

Escuela Politécnica Superior

Universidad Autónoma de Madrid

Contenidos

13

• Tipos Abstractos de Datos (TAD)
• Ejemplos de TAD

• TAD Cadena de caracteres
• TAD Número complejo
• TAD Conjunto

• Implicaciones de los TAD
• Programación Orientada a Objetos (POO)

Programación II – Tema 1: Tipos Abstractos de Datos

Escuela Politécnica Superior

Universidad Autónoma de Madrid

TAD Cadena de caracteres
• EdD

• Colección finita de caracteres pertenecientes a un alfabeto 
s = [c1 c2 … cn] ci∈
longitud(s)  0

si S = ∅⇒ longitud(s) = 0

14

• Habrá una longitud máxima de cadena permitida CC_MAX y un 

carácter especial de fin de cadena 
p.e. con CC_MAX=8 y carácter de fin de cadena @.
La cadena “PROG2” de longitud 5 sería:

P

R

G

2 @

O
• Funciones primitivas
• cc_crear, cc_liberar
• cc_vacia, cc_llena
• cc_insertarCaracter, cc_extraerCaracter

Programación II – Tema 1: Tipos Abstractos de Datos

Escuela Politécnica Superior

Universidad Autónoma de Madrid

TAD Cadena de caracteres

15

• CCCrear

• Prototipo: CC cc_crear()
• Descripción: crea y devuelve una cadena de caracteres 
“vacía”, es  decir, sólo almacenando en ella el carácter 
especial de fin de cadena

• Entrada: ninguna
• Salida: cadena creada, vacía 

(habría que especificar qué devolver en caso de error)

• Modifica: nada

Programación II – Tema 1: Tipos Abstractos de Datos

Escuela Politécnica Superior

Universidad Autónoma de Madrid

TAD Cadena de caracteres

16

• CCLiberar

• Prototipo: void cc_liberar(CC s)
• Descripción: libera una cadena dejándola “vacía”
• Entrada: cadena s
• Salida: ninguna
• Modifica: cadena s, dejándola vacía

Programación II – Tema 1: Tipos Abstractos de Datos

Escuela Politécnica Superior

Universidad Autónoma de Madrid

TAD Cadena de caracteres

17

• CCVacia

no vacía

• Prototipo: boolean cc_vacia(CC s)
• Descripción: comprueba si una cadena de caracteres está o 

• Salida: verdadero si S = ∅, falso en caso contrario

• Entrada: cadena s

• Modifica: nada

Programación II – Tema 1: Tipos Abstractos de Datos

Escuela Politécnica Superior

Universidad Autónoma de Madrid

TAD Cadena de caracteres

18

• CCLlena

• Prototipo: boolean cc_llena(CC s)
• Descripción: comprueba si una cadena de caracteres está o 
no llena, es decir si su longitud es igual o menor a CC_MAX

• Entrada: cadena s
• Salida: verdadero si la longitud de s es CC_MAX, falso en caso 

contrario

• Modifica: nada

Programación II – Tema 1: Tipos Abstractos de Datos

Escuela Politécnica Superior

Universidad Autónoma de Madrid

TAD Cadena de caracteres

19

• CCInsertarCaracter

• Prototipo: status cc_insertar(CC s, car c, pos p)
• Descripción: inserta un carácter dado en una posición 
determinada de una cadena (que queda modificada)

• Entrada: cadena s, carácter c a insertar, posición p en la que 

insertar c

• Salida: OK si la ins