PDF de programación - Tema 1 - Estructuras de datos - Tipos abstractos de datos

Cap. 1


ESTRUCTURAS DE DATOS

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

Jesús Alonso S. Dpt. OEI



p-1-

ESTRUCTURAS DE DATOS

Cap. 1


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



INDICE TEMA 1.



1. Definición y propiedades de los TADs.

Especificaciones



2. Ejemplos de Especificación de TADs



2.1 TAD Pila de enteros
2.2 TAD Cola de enteros



3. Ejemplos de Implementación de TADs



3.1 TAD Pila
3.2 TAD Cola



4. Excepciones



1. Definición y propiedades de los TADs.

Jesús Alonso S. Dpt. OEI



p-2-

Cap. 1



ESTRUCTURAS DE DATOS



Realidad



Abstracción

de la



realidad



Tipo abstracto



de
Datos

ABSTRACCIÓN DE DATOS = { datos, operaciones }

tipos de datos: Especificación del TAD

operaciones: Implementación del TAD



TAD = ED + Operaciones

Jesús Alonso S. Dpt. OEI



p-3-

Cap. 1


ESTRUCTURAS DE DATOS

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.



Jesús Alonso S. Dpt. OEI



p-4-

ESTRUCTURAS DE DATOS

Cap. 1

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.

Jesús Alonso S. Dpt. OEI



p-5-

Cap. 1


ESTRUCTURAS DE DATOS

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.

Jesús Alonso S. Dpt. OEI



p-6-

Cap. 1


ESTRUCTURAS DE DATOS

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.

Jesús Alonso S. Dpt. OEI



p-7-

Cap. 1

3. Ejemplo de Especificación de TAD: Cola de enteros.

ESTRUCTURAS DE DATOS



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)-.



Jesús Alonso S. Dpt. OEI



p-8-

Cap. 1


ESTRUCTURAS DE DATOS

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 );

Crea una cola, que inicialmente está vacía.


Especificación Semántica:


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


Jesús Alonso S. Dpt. OEI



p-9-

Cap. 1


ESTRUCTURAS DE DATOS

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.


Declaración: Procedure Desencolar (var Cola: TPila;

var Elemento: Integer );

Especificación Semántica:

Extrae de la cola un elemento. Dicho elemento es el primero que se
introdujo, entre los que se encuentran actualmente en la cola.


Jesús Alonso S. Dpt. OEI



p-10-

ESTRUCTURAS DE DATOS

Cap. 1

4. Implementación del TAD Pila.



TPila = record



Type Contenido = Array [ 1.. N ] of Integer; (* N tamaño de la pila *)



PP: Integer; (* Índice de la Pila *)
Contenido: TContenido



end;



Function PilaVacia ( Pila: Tpila ): Boolean;

PilaVacia := ( Pila.PP = 0 )

Procedure Inicializar ( var Pila: TPila );

Pila.PP := 0

Procedure Apilar ( var Pila: Tpila; Elemento: Integer );

with Pila do



if PP < N then
begin


end

PP := PP + 1;
Contenido[ PP ] := Elemento

begin

end;


begin

end;


begin



end;


begin



end;

Procedure DesApilar ( var Pila: Tpila; Elemento: Integer );

with Pila do



if PP > 0 then
begin


end

Elemento := Contenido[ PP ];
PP := PP - 1

Jesús Alonso S. Dpt. OEI



p-11-

Cap. 1