2
Tipos Abstractos
de Datos
o Definiciones
o TAD String
o Concepto de contenedor
o Colecciones e Iteradores
o Relaciones entre elementos
o TAD's contenedores
Estructuras de Datos y Algoritmos, curso 2021/22
Grado en Ingeniería Informática | Grado en Estadística
Universidad de Valladolid
,Tipo de Datos
Conjunto de valores
.. que pertenecen al Tipo de Datos TAD
Enumerados o construidos sintácticamente
Representación de los datos
Forma en que se almacena en memoria un valor de ese tipo
Conjunto de operaciones (especificación)
Operaciones fundamentales que se pueden realizar sobre valores
de ese tipo, y su(s) resultados
Cada operación tiene una semántica (significado de la operación,
restricciones, etc.) asociada.
Algoritmos de las operaciones (implementación)
Manera concreta en que se llevan a cabo las operaciones, dada la
representación proporcionada
César Vaca Rodríguez, Dpto. de Informática, UVa 2
,Concepto de tipo abstracto de datos (TAD)
Tipo abstracto de datos: (TAD)
Un conjunto de valores y operaciones asociadas
especificados de manera precisa
e independiente de la implementación
Objetivo:
Separar interfaz (definición operaciones) de implementación
(representación de los datos + algoritmos de las operaciones).
Notación:
El estado de un TAD viene dado por la secuencia de operaciones
realizadas sobre él.
La definición de las operaciones suele darse mediante axiomas y
reglas lógicas.
César Vaca Rodríguez, Dpto. de Informática, UVa 3
, Ejemplo de definición de PILA
Definición axiomática (TAD) Definición por código (no TAD)
ESPECIFICACIÓN PILA type
PNodo = ^TNodo;
TAD pila[elemento] TPila = PNodo;
OPERACIONES TNodo = record
Dato : ...;
• crear : pila Sig : TPila
• esta_vacía : pila booleano end;
• cima : pila elemento function cima(P: TPila) : PNodo;
• apilar : pila, elemento pila begin
• desapilar : pila pila Result := P
PRECONDICIONES end;
• cima(p) ¬ esta_vacía(p) procedure apilar(var P: TPila;
X: PNodo);
• desapilar(p) ¬ esta_vacía(p) begin
ECUACIONES X^.Sig := P; P := X
• esta_vacía( crear ) == T end;
• esta_vacía( apilar(p, x) ) == F procedure desapilar(var P: TPila);
• cima( apilar(p, x) ) == x begin
P := P^.Sig
• desapilar( apilar(p, x) ) == p
end; 4
FIN_ESPECIFICACIÓN
Tipos Abstractos
de Datos
o Definiciones
o TAD String
o Concepto de contenedor
o Colecciones e Iteradores
o Relaciones entre elementos
o TAD's contenedores
Estructuras de Datos y Algoritmos, curso 2021/22
Grado en Ingeniería Informática | Grado en Estadística
Universidad de Valladolid
,Tipo de Datos
Conjunto de valores
.. que pertenecen al Tipo de Datos TAD
Enumerados o construidos sintácticamente
Representación de los datos
Forma en que se almacena en memoria un valor de ese tipo
Conjunto de operaciones (especificación)
Operaciones fundamentales que se pueden realizar sobre valores
de ese tipo, y su(s) resultados
Cada operación tiene una semántica (significado de la operación,
restricciones, etc.) asociada.
Algoritmos de las operaciones (implementación)
Manera concreta en que se llevan a cabo las operaciones, dada la
representación proporcionada
César Vaca Rodríguez, Dpto. de Informática, UVa 2
,Concepto de tipo abstracto de datos (TAD)
Tipo abstracto de datos: (TAD)
Un conjunto de valores y operaciones asociadas
especificados de manera precisa
e independiente de la implementación
Objetivo:
Separar interfaz (definición operaciones) de implementación
(representación de los datos + algoritmos de las operaciones).
Notación:
El estado de un TAD viene dado por la secuencia de operaciones
realizadas sobre él.
La definición de las operaciones suele darse mediante axiomas y
reglas lógicas.
César Vaca Rodríguez, Dpto. de Informática, UVa 3
, Ejemplo de definición de PILA
Definición axiomática (TAD) Definición por código (no TAD)
ESPECIFICACIÓN PILA type
PNodo = ^TNodo;
TAD pila[elemento] TPila = PNodo;
OPERACIONES TNodo = record
Dato : ...;
• crear : pila Sig : TPila
• esta_vacía : pila booleano end;
• cima : pila elemento function cima(P: TPila) : PNodo;
• apilar : pila, elemento pila begin
• desapilar : pila pila Result := P
PRECONDICIONES end;
• cima(p) ¬ esta_vacía(p) procedure apilar(var P: TPila;
X: PNodo);
• desapilar(p) ¬ esta_vacía(p) begin
ECUACIONES X^.Sig := P; P := X
• esta_vacía( crear ) == T end;
• esta_vacía( apilar(p, x) ) == F procedure desapilar(var P: TPila);
• cima( apilar(p, x) ) == x begin
P := P^.Sig
• desapilar( apilar(p, x) ) == p
end; 4
FIN_ESPECIFICACIÓN
