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

1 Fundamentos de Programaci n II. Tema 3. Estructuras lineales de datos: listas, pilas, colas Lu s Rodr guez Baena 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 y aplicarlos 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.

2 O Por ejemplo, se puede ampliar el operador de multiplicaci n para multiplicar matrices. Procedimientos y funciones encapsulan 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 la definici n del tipo y de las operaciones para su manejo.

3 Universidad Pontificia de Salamanca (Campus Madrid). 2. Luis Rodr guez Baena, Escuela Superior de Ingenier a y Arquitectura, 2012. 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 cuadrado se 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.

4 Registro=cuadrado punto:origen real: lado fin_registro Universidad Pontificia de Salamanca (Campus Madrid). 3. Luis Rodr guez Baena, Escuela Superior de Ingenier a y Arquitectura, 2012. 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( * ). fin_funci n real funci n rea(valor cuadrado: c). var real : lado inicio //lado es la distancia entre dos puntos lado raiz2(( )**2+( )**2).

5 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). 4. Luis Rodr guez Baena, Escuela Superior de Ingenier a y Arquitectura, 2012. 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.

6 Una estructura de datos l gica ser a una estructura de datos que no implementa el lenguaje y que creamos a partir 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 definidas por el lenguaje de especificaci n de algoritmos utilizado (son Estructuras de datos f sicas ).

7 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). 5. Luis Rodr guez Baena, Escuela Superior de Ingenier a y Arquitectura, 2012. Tipos abstractos de datos (V). Los lenguajes no soportan todas las Estructuras de datos posibles. En muchas ocasiones es necesario realizar la definici n de la estructura de datos y declarar las operaciones primitivas que la manejan. Haremos la definici n del Tipo Abstracto de Datos.

8 O Definir el tipo de dato que contendr n. o Establecer la organizaci n de los datos utilizando los datos primitivos. o Establecer las operaciones primitivas para manejar el tipo de dato. Las Estructuras de datos utilizadas en este tema (pilas, colas , listas enlazadas) no est n implementadas en el lenguaje de programaci n. Ser necesario definirlas con las Estructuras de datos disponibles. Ser necesario implementar las operaciones primitivas para manejarlas. Universidad Pontificia de Salamanca (Campus Madrid).

9 6. Luis Rodr guez Baena, Escuela Superior de Ingenier a y Arquitectura, 2012. Datos est ticos y din micos Dato est tico. Dato que no puede variar su ubicaci n a lo largo de la ejecuci n del programa. Se reserva espacio en tiempo de Memoria est tica Memoria est tica (Pila) (Pila). compilaci n. Cuando el programa empieza su ejecuci n es necesario saber de antemano su a a 5. tama o y ubicaci n en la memoria. Se almacena en una zona de memoria est tica: pila. El dato se identifica por una variable que no es m s que una direcci n de memoria d nde est almacenada la informaci n.

10 Cuando se asigna un valor a ese dato, se almacena directamente en esa direcci n de memoria. entero: a a 5. Cuando se accede a ese dato, por ejemplo al ejecutar la instrucci n escribir(a), se accede de forma directa al contenido de esa direcci n de memoria. Universidad Pontificia de Salamanca (Campus Madrid). 7. Luis Rodr guez Baena, Escuela Superior de Ingenier a y Arquitectura, 2012. Datos est ticos y din micos (II). Dato din mico. Realiza una asignaci n din mica de memoria. Reserva espacio para almacenar la informaci n en tiempo de ejecuci n.