PDF de programación - EDA Apuntes

EDAEDA
Apuntes
Apuntes

UNED

Curso 2000 – 2001

©José Manuel Carrillo

Nota:
Nota:

Los apuntes que tienes ahora en tus manos son los que he confeccionado para el
estudio de la asignatura durante el curso 2000-2001. Son resúmenes de los temas de
las Unidades Didácticas. He omitido aquellas partes del temario que, bien por su
complejidad, bien porque no he visto que en los exámenes anteriores que he tenido en
mis manos se preguntara nada sobre los mismos, he considerado que no valía la pena
estudiar. Por supuesto esta es una valoración completamente subjetiva y en algunas
cuestiones probablemente muy equivocada. Por eso quiero advertirte de tal extremo.
Por otra parte he procurado en todo momento ser fiel en la transcripción, no obstante
en algunos temas puntuales hay razonamientos propios y ligeras modificaciones
respecto al texto base. En todos estos casos lo he mencionado convenientemente.

Espero que te sirvan de ayuda.

Un saludo, José Manuel.

1.- INTRODUCCIÓN Y CONCEPTOS FUNDAMENTALES

Introducción y conceptos fundamentales / 1

1.1.- Estructuras de datos y tipos de datos abstractos (TDA)

Un tipo de datos es una colección de valores

Un tipo de datos abstracto (TDA) es un tipo de datos definido de forma única mediante un tipo y
un conjunto dado de operaciones definidas sobre el tipo.

Una estructura de datos es la implementación física de un tipo de datos abstracto.

Debido al proceso de abstracción, el diseño deberá realizarse siguiendo
fundamentales:

1.- Análisis de datos y operaciones
2.- Elección del Tipo de Datos Abstracto
3.- Elección de la implementación

tres pasos

1.2.- Tipos de datos básicos

TDA Entero: tiene como tipo el conjunto de números enteros, y como operaciones la suma,
resta, multiplicación y división entera

TDA Real: tiene como tipo el conjunto de números reales y como operaciones la suma, resta
multiplicación y división

TDA Booleano: tiene como tipo el conjunto de valores booleanos True, False y como
operaciones las definidas en el álgebra de Boole (AND, OR, NOT)

TDA Carácter: tiene como tipo el conjunto de caracteres definido por un alfabeto dado y como
operaciones todos los operadores relacionales (<, >, =, >=, <=, <>)

Se denominan tipos de datos escalares a aquellos en los que el conjunto de valores está ordenado
y cada valor es atómico: Carácter, Entero, Real y Booleano.

Se denominan tipos de datos ordinales a aquellos en los que cada valor tiene un predecesor
(excepto el primero), y un único sucesor (excepto el último): Carácter, Entero y Booleano.
Los lenguajes de alto nivel suelen presentar tres funciones adicionales asociadas a los tipos de
datos ordinales: posición (Ord), predecesor (Pred) y sucesor (Suc) de un elemento.

Otro tipo de datos son los denominados compuestos dado que son divisibles en componentes que
pueden ser accedidas individualmente. Las operaciones asociadas a los tipos compuestos o
estructurados son las de almacenar y recuperar sus componentes individuales.

Los TDA compuestos básicos son:

TDA Conjunto: colección de elementos tratados con las operaciones unión, intersección y
diferencia de conjuntos.

TDA Arreglo: colección homogénea de longitud fija tal que cada una de sus componentes
pueden ser accedidas individualmente mediante uno o varios índices, que serán de tipo ordinal, y
que indican la posición de la componente dentro de la colección.

Introducción y conceptos fundamentales / 2

TDA Registro: tipo de datos heterogéneo compuesto por un número fijo de componentes
denominadas campos a las que se accede mediante un selector de campo.

El TDA Conjunto no es estructurado ya que no está organizado mediante el modo de acceso a
sus componentes individuales, mientras que el Arreglo y el Registro si lo son. Los registros
pueden tener como campos tipos de datos simples o arreglos o incluso otros registros.

Los TDA básicos son los utilizados con mayor frecuencia, pero además cada problema puede
requerir la definición de varios TDA propios. Por ejemplo, un TDA muy utilizado en
aplicaciones informáticas es el TDA lista definido de la siguiente forma:

TDA lista (o Secuencia): colección homogénea de datos, ordenados según su posición en ella,
tal que cada elemento tiene un predecesor (excepto el primero) y un sucesor (excepto el último)
y los operadores asociados son:

Insertar: inserta un elemento x, en una posición p de la lista
Localizar: localiza la posición p en la que se encuentra el dato x
Recuperar: encuentra el elemento x que esta en la posición p
Suprimir: elimina de la lista el elemento de la posición p
Suprimir_dato: elimina de la lista cualquier aparición del elemento x
Anula: ocasiona que la lista se vacíe
Primero (Fin): proporciona el primer (último) elemento de la lista
Imprimir: imprime todos los elementos de la lista en su orden.

En general el término “lista” se utiliza cuando el TDA se implementa sobre memoria principal
mientras que “secuencia” suele reservarse para implementaciones sobre memoria secundaria.

La lista es una estructura dinámica ya que su longitud dependerá del número de elementos que
tenga, aumentará al insertar y se reducirá al suprimir. Ahora bien, la lista puede implementarse
de formas muy diferentes. Una de ellas es mediante arreglos. Así, la lista, que es dinámica
independientemente de su implementación, se realiza mediante una implementación estática.

1.3.- Punteros y Listas enlazadas:

PUNTEROS
Un puntero es un tipo de datos simple cuyo valor es la dirección de una variable de otro tipo,
denominada variable referenciada.

Los punteros permiten realizar una reserva dinámica de memoria. Las variables referenciadas
son variables dinámicas, es decir, se crean en tiempo de ejecución.

El valor de un puntero es un número entero, sin embargo, este valor no es de tipo entero sino una
dirección.

El contenido de la variable referenciada puede ser cualquier tipo de dato: registro, otro puntero,
etc.

Declaración de los tipo puntero:

TYPE

Tipo_puntero = POINTER TO Tipo_var_referenc;

Introducción y conceptos fundamentales / 3

Declaración de la variable puntero: VAR

variable_puntero : Tipo_puntero;

La memoria reservada para la variable puntero es reservada y ocupada de la misma manera que
las variables estáticas.
La variable referenciada no existe hasta que no ha sido creada (en Modula2 Allocate):

Allocate (variable_puntero, SIZE (Tipo_variable_referenciada));

Las variables referenciadas recién creadas no tienen ningún valor (están sin inicializar). Para
asignarlo se accede a la variable referenciada mediante el nombre del puntero que la apunta y el
operador de acceso “^”, realizándose la asignación mediante su operador “:=”
Una vez que la variable referenciada ya no va a ser utilizada por el programa, será destruida o
liberada (en Modula2 Deallocate):

Deallocate (variable_puntero, SIZE(Tipo_referenciada));

Las operaciones asociadas al TDA puntero son la asignación y la comparación:
La asignación de punteros consiste en la asignación de “direcciones” entre variables puntero.
La comparación de punteros consiste en comprobar si sus direcciones son iguales o no

MODULE ejemlo;
TYPE

puntero = POINTER TO integer;

VAR

p, q : puntero

p ¿?

q ¿?

------------------------------------------------------------------------------------------------------------------
BEGIN

ALLOCATE (p, SIZE(integer));

p
q ¿?

¿?

------------------------------------------------------------------------------------------------------------------

p^ := 8;

p
q ¿?

8

------------------------------------------------------------------------------------------------------------------

q := p;

p

q

8

p = q TRUE

p^ = q^ TRUE

------------------------------------------------------------------------------------------------------------------

q^ := 5;

p

q

5

------------------------------------------------------------------------------------------------------------------

DEALLOCATE (p, SIZE(integer));

p ¿?
q ¿?

------------------------------------------------------------------------------------------------------------------

ALLOCATE (p, SIZE(integer));
ALLOCATE (q, SIZE(integer));

p
q

¿?
¿?

------------------------------------------------------------------------------------------------------------------

p^ := 8;

p
q ¿?

8

------------------------------------------------------------------------------------------------------------------

q^ := p^ ;

p

q

8

8

p = q FALSE

p^ = q^ TRUE

------------------------------------------------------------------------------------------------------------------

DEALLOCATE (p, SIZE(integer));

p ¿?

------------------------------------------------------------------------------------------------------------------

q

8

DEALLOCATE (q, SIZE(integer));

p ¿?

q ¿?

------------------------------------------------------------------------------------------------------------------
END

Introducción y conceptos fundamentales / 4

Cuando un puntero no señala a ninguna variable referenciada se le asigna un valor que representa
dicha circunstancia (en Modula2 NIL)

En definitiva, el TDA puntero es un tipo de dato simple cuyos valores son direcciones de
memoria, y sus operadores asociados son la asignación de punteros y la comparación de
punteros.

Los punteros son la base de construcción de todas las denominadas estructuras dinámicas, como
los árboles, las listas enlazadas, etc.

LISTAS ENLAZADAS
La finalidad de las listas enlazadas, como en el caso de los arreglos, es almacenar
organizadamente datos del mismo tipo.

Las listas enlazadas son tipos de datos dinámicos que se construyen con nodos.

Un nodo es un registro con dos campos: dat