PDF de programación - Tema04 - Estructuras lineales de datos - Fundamentos de Programación II

Fundamentos de Programación II

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

Luis Rodríguez Baena ([email protected])

Universidad Pontificia de Salamanca
Escuela Superior de Ingeniería y Arquitectura

Tipos abstractos de datos

Procedimientos y funciones generalizanel 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.

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

Universidad Pontificia de Salamanca. Escuela Superior de Ingeniería y Arquitectura
(CC) Luis Rodríguez Baena, 2013

2

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.

registro=cuadrado

punto:origen
real: lado

fin_registro

Universidad Pontificia de Salamanca. Escuela Superior de Ingeniería y Arquitectura
(CC) Luis Rodríguez Baena, 2013

3

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(c.lado * c.lado)

fin_función

real función Área(valor cuadrado: c)
var

real : lado

inicio

//lado es la distancia entre dos puntos
lado raiz2((c.infIzq.x – infDer.x)**2+(c.infIzq.y – infDer.y)**2)
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. Escuela Superior de Ingeniería y Arquitectura
(CC) Luis Rodríguez Baena, 2013

4

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.

● 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”).
● El lenguaje define el tipo array e incluye las herramientas necesarias para

declarar un array, acceder a un elemento, etc.

Universidad Pontificia de Salamanca. Escuela Superior de Ingeniería y Arquitectura
(CC) Luis Rodríguez Baena, 2013

5

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.

○ Definir el tipo de dato que contendrán.
○ Establecer la organización de los datos utilizando los datos primitivos.
○ 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. Escuela Superior de Ingeniería y Arquitectura
(CC) Luis Rodríguez Baena, 2013

6

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 compilación.

Cuando el programa empieza su ejecución

es necesario saber de antemano su 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.

● Cuando se asigna un valor a ese dato, se

almacena directamente en esa dirección de
memoria.

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

Memoria estática

Memoria estática

(Pila)

(Pila)

a

a

5

entero: a

a 5

Universidad Pontificia de Salamanca. Escuela Superior de Ingeniería y Arquitectura
(CC) Luis Rodríguez Baena, 2013

7

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.

● Cuando el programa comienza su ejecución, sólo se reserva

espacio para almacenar una referencia a la posición donde
se almacenará el dato, no para almacenar el dato en sí.
La variable que guarda la dirección de memoria (la referencia) es

el puntero.

El puntero se almacena en la pila.

● Durante la ejecución del programa es posible reservar

memoria para el dato al que apunta el puntero.
El dato en sí se almacena en una zona de memoria dinámica: el

montículo.

● En cualquier momento se puede reservar o liberar ese

espacio.

Universidad Pontificia de Salamanca. Escuela Superior de Ingeniería y Arquitectura
(CC) Luis Rodríguez Baena, 2013

8

Datos estáticos y dinámicos (III)

Definición de un puntero.

puntero_a tipoDato : varPuntero
● tipoDato, cualquier tipo de dato
estándar o definido por el usuario.

Memoria estática

(Pila)

● Al arrancar el programa la variable de

a

5

tipo puntero no está inicializada (no tiene
ningún valor).

● Sólo es posible darle valor asignándola a

otro puntero, reservando espacio en
memoria o asignándola a puntero nulo.

ptr1

ptr2

Puntero nulo.

● Se corresponde a la constante nulo.
● Se considera un puntero inicializado

(cómo dar a una variable numérica un
valor 0).

● Apunta a una dirección de memoria nula.

puntero_a entero : ptr1
puntero_a entero : ptr2

Universidad Pontificia de Salamanca. Escuela Superior de Ingeniería y Arquitectura
(CC) Luis Rodríguez Baena, 2013

9

Datos estáticos y dinámicos (IV)

Reservar espacio en el montículo.

reservar(varPuntero)
● Busca espacio en memoria para almacenar una variable del tipo de

varPuntero.

● varPuntero se carga con la dirección de memoria que se ha encontrado.

Referencia al dato apuntado por el puntero.

● Se utiliza el operador › .
varPuntero›
● Si varPuntero hace referencia a la zona de memoria a la que apunta,
hace referencia al contenido de dicha zona de memoria.

varPuntero›

● Hay que tener en cuenta que:

varPuntero es una variable de tipo puntero, por lo que sólo es posible asignarla

otro puntero (otra variable de tipo puntero, puntero nulo o reservar espacio).

○ Los operadores de asignación o las instrucciones de lectura o escritura no funcionan de la

misma forma para variables de tipo puntero que para otro tipo de variables.

varPuntero› hace referencia al contenido de la memoria a la que apunta al

puntero, por lo que es un dato del tipo base del puntero.

○ Sobre ella se podrán hacer todas las operaciones que se puedan hacer con el tipo base del

puntero.

Universidad Pontificia de Salamanca. Escuela Superior de Ingeniería y Arquitectura
(CC) Luis Rodríguez Baena, 2013

10

Datos estáticos y dinámicos (V)

Memoria estática

Memoria dinámica

(Pila)

(montículo)

a

5

ptr1

ptr2

reservar(ptr1)
ptr1
escribir(ptr1) //Error
leer(ptr1) //Error

5 //Error

Universidad Pontificia de Salamanca. Escuela Superior de Ingeniería y Arquitectura
(CC) Luis Rodríguez Baena, 2013

11

Datos estáticos y dinámicos (VI)

Asignación de variables de tipo

puntero.
● Lo que asigna no es el

contenido, sino la dirección de
memoria, la referencia.

Comparación de variables de

tipo puntero.
● Compara si dos punteros

apuntan a la misma dirección
de memoria.

Universidad Pontificia de Salamanca. Escuela Superior de Ingeniería y Arquitectura
(CC) Luis Rodríguez Baena, 2013

12

Datos estáticos y dinámicos (VII)

Liberar espacio de

almacenamiento.
liberar(varPuntero)

● Deja libre la posición de

memoria, volviéndola a marcar
como zona libre.

● El puntero que apuntaba la

posición queda indeterminado.

● No es posible recuperar la

información a la que apuntaba
el puntero.

A no ser que exista otra referencia

que también apuntaba al mismo
dato (como ptr2).

Memoria estática

Memoria dinámica

(Pila)

(montículo)

a

5

ptr1

ptr2

ptr3

10

10

liberar(ptr3)

Universidad Pontificia de Salamanca. Escuela