TEMA
1
ESTRUCTURAS
DE DATOS
TIPOS
ABSTRACTOS DE DATOS
Practica tu
mismo, por dios, con las cosas
pequeñas; luego sigue con las más grandes.
Epíteto, Discursos
OBJETIVOS DE ESTE CAPITULO:
· Un concepto importante en
ingeniería: el de Caja Negra
· El rol de las Estructuras
de Datos en un programa
· Diferenciar la
declaración y las operaciones en una EDs.
· Ventajas de utilizar
Estructuras de Datos
|
1. Definición y propiedades de
los TADs.
m à
Realidad
Abstracción Tipo abstracto
de la de
realidad Datos
|
ABSTRACCIÓN DE DATOS = {
datos, operaciones }
|
= tipos de datos:
Especificación del TAD
= operaciones: Implementación
del TAD
Ø Características de los TADs:
ü ENCAPSULAMIENTO: Se desconoce la implementación de la
Declaración y de las Operaciones del TAD.
ü PROTECCIÓN: Sólo es posible
acceder al TAD a través de las Operaciones del mismo.
ü Representa una ABSTRACCIÓN:
Se seleccionan ciertos datos que interesan del mundo real, ignorando el resto.
ü Deben poder COMPILARSE POR
SEPARADO.
Ø Especificación del TAD: Permite al
usuario la utilización del TAD.
Ø Implementación del TAD: Sólo la
conoce el programador del TAD, no el usuario.
Ø Especificaciones
Sintácticas: Hacen
referencia a aspectos Sintácticos:
Nombre de la operación,
Parámetros de entrada, Parámetros de salida, Tipo de dichos parámetros,
Resultado devuelto por la operación, Tipo del resultado, etc.
Semánticas: Indican el
efecto producido por la operación.
Para CADA OPERACIÓN del TAD es necesario dar sus
especificaciones Sintácticas y Semánticas.
2. Ejemplo de Especificación de
TAD: Pila de enteros.
Ø Una Pila es una ED que almacena elementos de
un tipo determinado, que sigue la política de que el primer elemento que se
extrae (se ‘desapila’) es el último que se introdujo (se ‘apiló’) -primero en
salir, ultimo en entrar (LIFO)-.
=
Todos los procesadores tienen
un mecanismo de este tipo conocido por el nombre ‘Pila del Sistema’, el cual
se utiliza para guardar los parámetros de las subrutinas, y otros valores.
ESPECIFICACIÓN
del TAD PILA
Ø Operación: Inicializar una pila.
Especificación
Sintáctica:
ΠNombre de la
operación: INIPILA.
Parámetros de
entrada, y tipos: no tiene
Ž Parámetros de
salida: una pila, de tipo TPila.
Resultado: ninguno.
Declaración: Procedure IniPila ( var Pila: TPila );
Especificación
Semántica:
Crea una pila,
que inicialmente está vacía.
Ø Operación: Apilar un elemento en la pila
Especificación
Sintáctica:
ΠNombre de la
operación: APILAR
Parámetros de
entrada, y tipos:
Pila
que recibe al elemento, de tipo TPila.
Elemento
que se introduce en la pila, de tipo Entero.
Ž Parámetros de
salida: la propia pila, de tipo TPila, con el elemento introducido.
Declaración: Procedure Apilar ( Elemento: Integer;
var Pila: TPila );
Especificación
Semántica:
Introduce en la
pila el elemento pasado como parámetro. La próxima vez que se ejecute la
operación ‘DESAPILAR’, el elemento extraido será el ahora introducido.
Ø Operación: Desapilar un elemento de la pila
Especificación
Sintáctica:
ΠNombre de la
operación: DESAPILAR
Parámetros de
entrada, y tipos:
Pila
que contiene el elemento, de tipo TPila.
Ž Parámetros de
salida: la propia pila, con el elemento introducido.
Pila
de la que se ha extraido al elemento, de tipo TPila.
Elemento
que se extrae de la pila, de tipo Entero.
Declaración: Procedure Desapilar (var Pila: TPila;
var Elemento:
Integer );
Especificación
Semántica:
Extrae de la
pila un elemento. El elemento extraido es justamente el último que se
introdujo.
Ø Operación: Determinar si la pila está vacía.
Especificación
Sintáctica:
ΠNombre de la
operación: PILAVACIA
Parámetros de
entrada, y tipos:
Pila
que se quiere comprobar, de tipo TPila.
Ž Parámetros de
salida: ninguno.
Resultado: un
valor booleano.
Declaración: Function PilaVacia ( Pila: TPila ): Boolean;
Especificación
Semántica:
Devuelve el
valor ‘cierto’ si la pila no contiene ningún elemento.
3. Ejemplo de Especificación de
TAD: Cola de enteros.
Ø Una Cola es una ED que almacena elementos de
un tipo determinado, que sigue la política de que el primer elemento que se
extrae (se ‘desencola’) es el primero que se introdujo (se ‘encoló’) -primero en salir, primero en entrar
(FIFO)-.
ESPECIFICACIÓN
del TAD COLA
Ø Operación: Inicializar una cola
Especificación
Sintáctica:
ΠNombre de la
operación: INICOLA.
Parámetros de
entrada, y tipos: no tiene
Ž Parámetros de
salida: una cola, de tipo TCola.
Declaración: Procedure IniCola ( var Cola: TCola );
Especificación
Semántica:
Crea una cola,
que inicialmente está vacía.
Ø Operación: Cola Vacía
Especificación
Sintáctica:
ΠNombre de la
operación: COLAVACIA.
Parámetros de
entrada, y tipos: una cola perteneciente al tipo TCola.
Ž Parámetros de
salida: ninguno.
Declaración: Function ColaVacia ( Cola: TCola ): boolean;
Especificación
Semántica:
Devuelve
‘verdad’ si la cola pasada como parámetro está vacía; ‘falso’ en caso
contrario.
Ø Operación: Encolar un elemento en la cola
Especificación
Sintáctica:
ΠNombre de la
operación: ENCOLAR
Parámetros de
entrada, y tipos:
Cola
que recibe al elemento, de tipo TCola.
Elemento
que se introduce en la pila, de tipo Entero.
Ž Parámetros de
salida: la propia cola, de tipo TCola, con el elemento incluido.
Declaración: Procedure Encolar ( Elemento: Integer;
var Cola: TCola );
Especificación
Semántica:
Introduce en la
cola el elemento pasado como parámetro. Este elemento será el último en salir,
de todos los elementos presentes en este momento.
Ø Operación: Desencolar un elemento de la cola.
Especificación
Sintáctica:
ΠNombre de la
operación: DESENCOLAR.
Parámetros de
entrada, y tipos:
Cola
que contiene el elemento, de tipo TCola.
Ž Parámetros de
salida: la propia cola, con el elemento incluido.
Cola
de la que se ha incluido al elemento, de tipo TCola.
Elemento
que se extrae de la cola, de tipo Entero.
Monografías
