Download Estructura de la información

Estructura de la información
TEMA 1 TIPOS ABSTRACTOS DE DATOS
Tema 1
Tipos abstractos de datos
1. Concepto TAD
2. Una jerarquía de TAD
3. Implementación de TAD
4. Eficiencia de las
implementaciones
5. Representación de
contenedores usando vectores
6. Implementación de TAD con
una memoria dinámica
1. CONCEPTO TAD
Un tipo abstracto de Datos se define como un dominio de valores sobre los
que se pueden aplicar una o más operaciones, que también forman parte del TAD.
El concepto de TAD es la evolución natural de la noción más primitiva de tipos de
datos, propia de los programas de los años sesenta, que se centraban en los
valores y obviaban las operaciones.


Un TAD consta de dos partes:
La Especificación: introduce las operaciones de TAD (nombre e interfaz) y
fijan su comportamiento.
La Implementación: Determina una representación de los valores del TAD y
la codificación de las operaciones de acuerdo con esta representación.
En Orientación a Objetos, la clase es la unidad básica de encapsulación, que
combina un conjunto de datos (representado por los atributos) y un conjunto de
operaciones (también denominados métodos). Los objetos que interaccionan en
los programas construidos con lenguajes orientados a objetos son instancias de
clases: sólo pueden tomar los valores permitidos por la clase y solo se les puede
aplicar métodos de clase. Los objetos se crean mediante los llamados métodos
constructores, y se destruyen también mediante métodos o bien de forma
implícita.
Algunas clases no permiten crear instancias, bien porque hay algún método
sin implementar (clases diferidas), bien porque la clase caracteriza ciertas
propiedades del dominio (clases abstractas). Por otro lado, existen las clases
genéricas en las que el tipo de determinantes atribuidos está aún sin concretar, su
utilidad es enorme porque permiten definir categorías similares de clases de una
sola vez.
2. UNA JERARQUÍA DE TAD
Operaciones de los
contenedores
OPERACIONES BÁSICAS
Inserción
Supresión
Consulta sobre elementos
OTRAS OPERACIONES
Creación
Destrucción
Predicados
Recorridos…
El Objetivo de este apartado es ofrecer un catálogo versátil de TAD
encapsulados en clases genéricas y organizados jerárquicamente, para poder
gestionar colecciones de elementos con distintas políticas de accesos. Empezamos
por introducir el concepto de contenedor como nexo de todos los TADs que
forman una jerarquía. Un contenedor es cualquier TAD que se caracterice por
contener un conjunto de elementos (por ejemplo un TAD para registrar los socios
de un club, las direcciones web de una hiperagenda, etc).
El concepto de contenedor es muy general, lo representamos mediante una
clase diferida parametrizada:
 Diferida porque algunos métodos no se pueden implementar.
 Parametrizada porque el comportamiento del TAD es independiente de los tipos
de elementos almacenados.



Los contenedores se caracterizan porque:
Debe ser posible crearlos y destruirlos.
Todo contenedor tendrá una ocupación determinado, por eso definimos un
atributo tamaño que registra el número de elementos en él contenidos.
Sus elementos son todos del mismo tipo.
2 · Estructura de la información
Se ofrece en la página siguiente una figura en representación UML de la clase
contenedor y de varias clases herederas que estudiaremos en este módulo.
Jerarquía de clases


Contenedores recorribles: Una de las funciones que solemos pedir a los
contenedores es la obtención de todos sus elementos, a veces siguiendo un
orden determinado, a veces aleatorio. En cualquier caso, todos los
contenedores recorribles seguirán el mismo patrón: se situarán sobre el primer
elemento, y después consultarán el elemento actual y avanzarán al siguiente
reiteradamente hasta llegar al final. Como paso previo a la definición de
contenedores recorribles, formulamos la clase iterator que ofrece las cuatro
opciones mencionadas y se definen los contenedores recorribles por herencia
múltiple de las clases cotenedor e iterator.
Contenedores acotados: Los TAD contenedores no pueden tener una
capacidad infinita dado que todo ordenador no tiene una capacidad infinita; por
eso se introduce esta clase que controla que no se produzca un
desbordamiento en esta familia de Tad. Normalmente le pasamos la dimensión
como parámetro de la operación de creación pues resulta más fácil en el
entorno Java.
Por último, establecemos una jerarquía de elementos añadiendo varias
especializaciones: ElemOrd (orden total), ElemEsp (identifica un elemento especial),
ElemClave (define los elementos en los que se puede distinguir una clave que los
identifica).
En un segundo nivel, por herencia múltiple de estas clases, encontramos:
ElemOrdClave (permite comparar las claves de los elementos de ElemClave),
ElemClaveEsp (la clave tiene un valor especial que utilizamos sobre todo como
indicador de inexistencia de un elemento en un contenedor) y ElemSum (añade una
operación de suma de los elementos, así como un segundo elemento especial, esta
clase nos permitirá asignar pesos a los elementos). Todos estos conceptos
podemos verlos agrupados en la imagen de la página siguiente
Estructura de la información · 3
Los TAD, son, por tanto, el eje vertebrador de la asignatura, y un efecto de la
variedad de los mismos es la posible combinación entre ellos, heredando atributos,
métodos y restricciones propios de su raiz correspondiente.
Jerarquía de elementos
Clasificación de los contenedores
Clases de Contenedores
SECUENCIAS
Pilas
Colas
Colas prioritarias
Listas con puntos de interés
ÁRBOLES BINARIOS
CONJUNTOS
Conjuntos como tales
Sacos
FUNCIÓN
Función Parcial
Función Total
RELACIONES
Relaciones Binarias
Grafos Dirigidos
Grafos Dirigidos Etiquetados
Grafos No Dirigidos Etiquetados
Dada su funcionalidad, distinguimos cinco clases principales de
contenedores, que describimos a continuación (cada una con sus particularidades y
a la vez, subclases):
Las Secuencias (1ª clase) representan disposiciones lineales de
elementos. Existe un primer elemento, un último y una política de acceso lineal a
todos ellos. Los elementos se añaden de uno en uno. Existen muchos TAD con este
tipo de disposición, pero vamos a destacar las pilas y colas. Las pilas se
caracterizan porque se borra y se consulta el último elemento insertado (como una
pila de platos, el último en poner es el primero que debemos coger) mientras que
en las colas se consulta y se borra el primer elemento insertado (como en la cola
del cine), a excepción de las colas prioritarias en las que la posición que ocupa
un elemento dentro de la cola viene dada por su prioridad y no por el orden de
inserción. Otro caso especial son las listas cuyo nombre auténtico es listas con
puntos de interés, en las que los elementos se pueden insertar y borrar en
cualquier secuencia. (podemos observar la jerarquía colgante en la página
siguiente).
Los árboles binarios (2º) nos sirven para introducir relaciones
jerárquicas. Cada elemento está por encima de dos más, como mucho y está por
debajo de un tercero (excepto el elemento raiz). En este tipo la clase todavía no
está definida y la política de obtención de elementos tampoco. Lo que si es
necesario es tratar un mismo árbol con diferentes recorridos: inorden, posorden…
Los conjuntos (3º) tienen una operación conmutativa para añadir
elementos, y la operación de suprimir, por su parte, no viene dada por la posición
4 · Estructura de la información
del elemento, sino por una operación que explicita exactamente el elemento a
suprimir. Distinguimos dos categorías de conjuntos: los conjuntos como tales, y los
conjuntos con repeticiones denominados sacos. En los primeros los elementos no
pueden aparecer repetidos, en los segundos sí, y por ello la supresión de un
elemento elimina solo una aparición de un elemento. Como es habitual, en la
jerarquía colgante, podemos crear las versiones recorribles.
Jerarquía colgante de Secuencia
Las funciones (4º) se caracterizan por la
existencia de un segundo dominio de elementos. El
contenedor se ocupa de asociar un valor de este
segundo dominio (alcance) a todo elemento del
primero que aparezca (dominio). Por este motivo, la
inserción implica pares de elementos. La supresión y
la consulta se llevan a cabo de acuerdo con el primer
elemento insertado. Este concepto es el de función
parcial. Pero por otro lado existen también las
funciones totales, que exigen que el alcance de la
función tenga un elemento especial, que es el
resultado que se obtiene cuando se consulta un
elemento que no forma parte del dominio de la
función. (ElemEsp).
Otra característica especial es cuando uno de
los dos dominios está contenido en el otro (por
ejemplo una función que dado el DNI de una persona
proporciona la ficha completa de ésta, incluido el
mismo DNI).
Jerarquía colgante de Conjunto
Jerarquía colgante de Función
Por último, restan las relaciones (5º y último
tipo de jerarquía de clase) que son relaciones binarias
entre pares de elementos. Al igual que sucedía con las
funciones, hay dos dominios de elementos
involucrados en el contenedor, y las operaciones de
añadir o borrar se refieren al establecimiento o
ruptura de interrelaciones entre elementos de los dos dominios. Es importante la
operación para obtener todos los elementos de un dominio relacionados con un
Estructura de la información · 5
elemento de otro. Dado que además se trata de dos recorridos posibles, conviene
heredar dos veces de los iteradotes (como vemos en la página siguiente).
También es importante la asociación de pesos
llamadas etiquetas, que deben presentar ciertas
operaciones para manipularlas cómodamente.
Clases de Relaciones
Otra especialización básica es el TAD de los
grafos, que tiene lugar cuando todos los dominios
son el mismo. Tenemos entonces los grafos dirigidos
(restricción sobre dominios), grafos dirigidos
etiquetados.
Hay dos aspectos importantes en la
traducción de estas jerarquías a Java, y son la
genericidad y la herencia múltiple.



Dado que Java no ofrece genericidad
podemos aprovechar que Java consideran que todas
sus clases heredan de una superclase llamada Object.
Así definimos los contenedores sobre valores Object y
éstos pueden tomar cualquier forma y se les puede
aplicar los métodos adecuados. Sin embargo esto
también nos puede conducir a 3 problemas
principales:
Se pueden construir contenidos heterogéneos donde se mezclen elementos de
varias clases.
La clase Object no ofrece alguna de las funciones que algunos contenedores
necesitan más adelante.
Los elementos del contenedor deben ser objetos de clase y éste no es el caso
habitual de valores de tipos predefinidos.
El otro gran problema es la simulación de la herencia múltiple que Java no
soporta, pero que podemos eludir usando las interfaces de Java para simularla
(recordemos que las interfaces son clases en las que todos los métodos son
virtuales). Las propiedades más importantes es que una interfaz puede heredar de
más de una interfaz (múltiple); una clase además puede implementar una o más
interfaces (totalmente o parcialmente).
Dos detalles más al implementar con Java: las operaciones constructoras deben
tener el mismo nombre de la clase; y no hay operaciones de destrucción dado que
Java hace gestión de la memoria dinámica que destruye automáticamente los
objetos.
3. IMPLEMENTACIÓN DE TAD


La implementación de un TAD consta de 3 partes:
Decidir la representación del TAD, es decir, la estrategia de representación
de sus valores. Decidir, por tanto, un método de almacenamiento de los
elementos del contenedor y representarlo mediante atributos privados de la
clase (Podemos decir que se trata de elegir una de los 5 contenedores antes
comentados). Los atributos que podemos elegir son los tipos voléanos,
numéricos, caracteres, etc, hasta los vectores y tuplas.
Establecer las relaciones entre los atributos mediante el invariante de la
representación, que identifica los estados admisibles de los objetos de la
clase. Consistirá en un booleano y su efecto es documental. Forma parte de la
precondición y postcondición de toda operación pública o protegida del TAD; y
la idea fundamental es que independientemente de si usamos una notación
6 · Estructura de la información
formal, semiformal o totalmente informal, una clase de implementación siempre
debe incluir este invariante.
 Escribir algoritmos que codifiquen cada una de las operaciones del TAD. Estos
algoritmos deben usar atributos de la clase y pueden invocar métodos de otras
clases con las que tiene establecida una relación de uso. Una parte importante
de estos algoritmos son el invariante del bucle y consiste en un predicado
booleano que se debe cumplir cuando se empieza y acaba la ejecución de un
bucle, así como justo antes de entrar y salir del mismo. Otra parte importante
de la codificación de las operaciones es el encapsulado de operaciones, que se
realizan en métodos que actúan siempre sobre objetos (eventualmente serán
funciones, si retornan algún valor).
Existen, por tanto, muchas representación de TAD posibles para implementar
en un mismo problema, pero podemos llegar a necesitar otras distintas según los
casos, por lo que es muy interesante contar con una variada librería de TADs
eficaces y comprobados.
4. EFICIENCIA DE LAS IMPLEMENTACIONES
El problema de medir una implementación para saber si es correcta (no
existe la “mejor” implementación, sino la más correcta para unos determinados
requisitos de uso) surge al elegir los criterios por el cual vamos a medirlos, estos
criterios deben cumplir:






Deben ser completamente objetivos, o sea, calculable a partir de unas reglas
deterministas.
Se tiene que basar en un análisis del código y no en pruebas de ejecución.
Tiene que ser independiente de la máquina que ejecutará el código, por lo cual
la medida en tiempo (segundos) o en espacio (bytes) no son las indicadas.
Tiene que ignorar factores constantes que los avances tecnológicos acabarán
superando.
Tiene que considerar la dimensión de los datos de entrada.
Tiene que considerar los grandes volúmenes de datos, porque es cuando las
diferencias son realmente importantes.
Por ello, para medir la eficiencia de las implementaciones tanto en tiempo como
en espacio, nos decidimos por las notaciones asintóticas, las cuales no intentan
establecer el tiempo o espacio exacto de ejecución, sino que caracterizan estas
magnitudes mediante una función sobre el volumen de los datos de entrada. Hay
varias familias de notaciones asintóticas, pero nosotros nos decidimos por la
llamada O-grande, que calcula la eficiencia en el peor de los casos.
La O grande es el conjunto de funciones para las que f es asintóticamente una
cota superior. Es decir, a partir de cierto punto No, solo hay que multiplicar f por
una constante Co para conseguir que el valor de las funciones g este siempre por
debajo del valor de f.
Esto quiere decir que dado el algoritmo o representación de tipo que
queremos evaluar, obtenemos una función g(n) donde n es la dimensión de los
datos de entrada. Esta g pertenecerá a O(f) para una f dada que caracterice la
eficiencia del algoritmo o representación. Para la mayoría de los algoritmos la
función f, estará dentro de una de las siguientes categorías:
Coste
Operaciones de los
contenedores
Representación y Características
Constante
f(n)=k
Logarítmica
f(n)=log n
Se representa mediante O(log n), y encontramos investigaciones dicotómicas
Lineal
f(n)=n
Se representa por O(n), como la búsqueda de un elemento en un vector odenado
Cuasi-lineal
f(n)=n log n
O(n log n), y el ejemplo es el método de ordenación de vectores
Cuadrática
f(n)=n2
Se representa por O(n2) y surge en algoritmos de 2 bucles anidados o vectores bidimensionales
Cúbica
f(n)=n3
Se representa por O(n3) y surge en algoritmos de 3 bucles anidados o vectores tridimensionales
n
Se representa por O(kn) y surge en algoritmos que ensayan soluciones hasta encontrar la buena
Exponencial
f(n)=k
Se representa mediante O(1), suele ser la asignación de valores de tipos simples
Estructura de la información · 7
Las categorías anteriores se encuentran ordenadas de mejor (menos
tiempo o espacio) a peor.
Eficiencia temporal
La función de eficiencia temporal T(x) denota el tiempo de ejecución del
fragmento de código x medido con la notación O. Para medir esta eficiencia
temporal tendremos siempre presentes las siguientes reglas:







El acceso a un atributo o posición de vector de tipo predefinido y las
operaciones aritméticas y booleanas tienen coste O(1).
La evalucación de una expresión tiene el coste de evaluar sus subespresiones
más el coste del operador.
El coste de una composición secuencial de instrucciones, es la suma de los
costes de las instrucciones individuales que la componen.
El coste de la asignación es el de la evaluación de las expresiones que aparecen
más el de transferencia de datos que corresponde a su dimensión.
El coste de una instrucción alternativa es la suma de los costes de evaluar la
expresión y ejecutar las dos ramas.
El coste de invocar a un método es el de la evaluación de las expresiones que
se pasan como parámetros más el coste de la función invocada.
El coste de una instrucción iterativa es el resultado de multiplicar el número de
vueltas por el coste de una vuelta.
Además, en las operaciones internas del método O grande, estableceremos las
siguientes propiedades:




O(c x f(n)) = O(f(n))
C x O(f(n)) = O (f(n))
f(n) x O(g(n)) = O (f(n) x g(n))
La suma de dos o más O es la mayor de todas ellas.
Eficiencia espacial
La función de eficiencia espacial E(x) denota el espacio ocupado por la
representación de tipo x medido con la notación O. Su determinación se basa en las
siguientes reglas:




Representación de contenedores usando vectores
Representación secuencial
Rep. secuencial “simple”
Rep- secuencial marcada
Rep. Secuencial ordenada
Representación encadenada
Rep. Encadenada “simple
Rep. Encadenada circular
Rep. Doblemente
Un atributo o posición de un vector de tipo predefinido, consume un espacio
O(1), igual que cualquier referencia a un objeto.
Un vector de n posiciones ocupa el producto de n por el espacio de cada
posición (por ejemplo si son tipos predefinidos sería entonces O(n) ).
Una tupla de n componentes ocupa la suma de los espacios de los
componentes.
El espacio de la implementación de un TAD es igual a la suma del espacio
requerido por sus atributos.
A veces se prefiere contar el espacio en términos de espacio de memoria
ocupada (bytes); esto se debe al hecho de que muy a menudo las alternativas
tendrán un comportamiento asintótico idéntico y se tendrá que llevar a cabo un
estudio más cuidadoso para compararlas.
5. REPRESENTACIÓN DE CONTENEDORES USANDO VECTORES
El punto clave de la implementación de los TAD de los contenedores es la
estrategia de almacenamiento, que veremos en este apartado pero solo en lo
8 · Estructura de la información
referente a guardarlos en un vector, dejando para el siguiente el uso de la memoria
dinámica; y nos centraremos en el estudio del saco acotado.
Representación secuencial
La forma más simple de representar un contenedor consiste en almacenar
todos sus elementos en un vector añadiendo un valor natural que delimita la parte
ocupada y la parte libre del vector. El apuntador de sitio libre (apunta a la
primera posición libre) o apuntador al último (si apunta a la ultima posición
ocupada).
La figura lateral muestra el estado de un vector con apuntador de sitio libre
que almacena n elementos desde v1 hasta vn. Este tipo de implementaciones
suelen tener características comunes:
Interfaz saco acotado
Saco acotado
Tamaño, maximo; Nat
Crea (n:Nat)
Vacio()
Lleno()
nbElems()
destruye()
añade (v:Elem)
borra (v:Elem): Bool
nAps (v: Elem): Nat
Elem
Vector secuencial





Son simples y muy fácilmente comprensibles
Espacialmente son óptimas si conocemos el número de elementos que se
tienen que almacenar, ya que solo necesita espacio para éstos y algún
apuntador adicional de conste prescindible.
La consulta tiene coste lineal a no ser que los elementos estén ordenados y
apliquemos la búsqueda dicotómica con coste logarítmico (mucho mejor).
La inserción es más o menos costosa si hay que controlar la existencia previa
del elemento
La supresión es de coste lineal a causa de la búsqueda. Una vez localizado el
elemento a eliminar se tiene que mover el último elemento ocupado a la
posición borrada.
Es útil esta primera representación cuando los requisitos de eficiencia no son
demasiado elevados o cuando el volumen de datos a manejar es reducido.
La representación por tanto quedará como sigue: disponemos los
elementos de los sacos en posiciones consecutivas de un vector (cada aparición de
un mismo elemento ocupa un espacio) empezando por la primera y siguiendo la
estrategia secuencial. Habrá un contador de elementos que en realidad es el mismo
atributo tamaño que se hereda de contenedor. Declaramos el atributo vector y
reservamos en su interior una posición adicional para usar la técnica del centinela
en las búsquedas exigidas por la supresión y consulta de exigencia. El invariante,
debe poner trabas a que se supere el tamaño máximo permitido, claro.
Cuando se suprime un elemento hay que buscar la primera aparición (dado
que todos son equivalentes) y copiaremos el último elemento de la parte ocupada
del vector en ese lugar eliminado. Para contar el número de apariciones de un
elemento se hace imprescindible recorrer todo el vector e ir contando.
Respecto a la eficiencia de esta implementación obtenemos que el coste
de crear es O(máximo x n) -recordemos que máximo es el tamaño máximo de
cada elemento que, a priori no podemos conocer- y n el número de elementos.
Comprobar si esta vacio, lleno cuesta O(1), insertar tiene coste O(n), borrar tiene
coste O(máximo x n), ver si existe un elemento determinado O(máximo x n). El
coste espacial es de O(máximo x n) como nos podíamos imaginar y en cuanto al
coste espacial real es de (máximo + 1) x tamaño de los elementos + 2 naturales.
Representación secuencial marcada
El movimiento de elementos exigido por las actualizaciones secuenciales
provoca inconvenientes cuando se trata de TADs complejos; además también da
problemas cuando se acoplan dos estructuras diferentes interrelacionadas. Lo que
haremos para evitarlo será realizar una marca: es un indicador del estado de la
posición del vector, que puede indicar libre u ocupada. En el dibujo lateral
observamos que aparecen posiciones marcadas, es decir elementos que estuvieron
dentro de la estructura en un pasado, pero que se han borrado y ya no son
relevantes. Entonces, la supresión no efectúa ningún movimiento, sino que la
Rep. Secuencial marcada
Estructura de la información · 9
marca de la posición que contiene el elemento que se debe borrar se activa; se dice
que la posición se marca y está disponible para ser “rellenada”.
Ahora bien, en la inserción de un elemento podemos hacer dos cosas:
 Cuando se agota la parte libre se reorganiza el vector para eliminar las
posiciones marcadas y volver a la situación ideal, sin marcas y vacías; pero esto
hace que movamos elementos, función que queriamos evitar con la utilización
de las marcas.
 En cada inserción hay que buscar la primera posición marcada del vector y
ocuparla con el nuevo elemento. Lo hemos reciclado.
La búsqueda es una pena pero también pasa por las posiciones marcadas a
pesar de que sabemos que no contendrán el elemento buscado.
Representación secuencial ordenada
Las estrategias secuenciales penalizan las operaciones de actualización del
contenedor como la consulta individual de los elementos. Lo primero puede resultar
aceptable, pero la consulta tiene muy mal comportamiento y a veces las
rechazamos. Para evitarlo tenemos las representaciones secuenciales ordenadas
que es una estrategia que optimiza las consultas.
Se caracteriza porque no añadimos ningún atributo nuevo, solo que el
invariante añade una restricción, es decir, cada elemento es mayor que el anterior
y menor o igual que el siguiente (para el caso de las sucesivas apariciones de un
mismo elemento). Así, la operación de consulta deja de ser lineal y pasa a ser
logarítmico, que es muy aceptable.
La única pega de esta nueva estrategia es que todo cambio en la
configuración del vector obliga a mover elementos para asegurar su continuidad y
su ordenación; pero dado que su coste (el de la inserción y supresión) ya era de
O(máximo x n) tampoco perdemos nada. Y en cambio, las operaciones consultoras
salen ganando muchísimo. En cuanto al coste espacial, el gasto es el mismo que
antes.
Representaciones encadenadas
De cualquier forma, las representaciones secuenciales suponen tanto al
añadir como al borrar elementos, todo un gran movimiento de los mismos para
asegurarnos de su secuencialidad y, en otros casos también de su orden. Las
principales pegas son:



Vectores encadenados
Como los TADs son genéricos, los elementos a los que hacemos referencia
pueden ser realmente grandes y, en este caso y al desconocer su dimensión, el
gasto en el movimiento de elementos puede ser muy grande.
Los movimientos pueden desajustar varias estructuras acopladas.
El número de movimiento según el tamaño del TAD puede resultar excesivo.
Para evitar esto tenemos las estrategias de representación
encadenadas también llamadas estrategias enlazadas. En este caso en el
vector no habrá zonas diferenciadas ocupadas o libres, sino que cualquier
posición puede estar ocupada por un elemento o libre, independientemente del
estado de las posiciones más próximas. Esto se realiza añadiendo a la marca
que ya teníamos por cada posición un nuevo campo adicional de tipo entero, de
forma que una posición ocupada lleva a otra siguiendo el valor de este campo,
o sea, apunta a la siguiente dirección ocupada. En la imagen lateral podemos
ver esta estrategia con dos vectores que contienen los mismos elementos en el
mismo orden.
10 · Estructura de la información
Ahora bien, nos queda como resolver la gestión del espacio libre del vector.
Es decir, cada vez que se inserte un elemento hay que obtener una posición del
vector donde almacenarlo y, al borrarlo, hay que recuperar esta posición para
reutilizarla. Una primera solución es marcar las posiciones del vector como
ocupadas o libres y tomar espacio al final del vector hasta que se agote y
reorganizarlas; pero claro, estaríamos en el mismo problema del apartado anterior.
Lo que se puede hacer es encadenar los sitios libres igual que los ocupados pero
con la marca de libres y así se obtiene rápido una pila de sitios libres, y además
aprovechamos el mismo campo de encadenamiento para enlazar los elementos y
no ocupamos más espacio.
Gestión de sitios libres
La figura lateral muestra el mismo vector de la página anterior pero añade
la gestión de sitios libres y el llamado elemento fantasma que se deposita
cuando se crea la estructura encadenada y que simplifica los algoritmos de
manipulación del tipo, especialmente la supresión.
Representación encadenada circular y doblemente encadenada
En diferentes contextos nos vemos en la necesidad de adaptar las
estructuras vistas anteriormente para casos especiales. Dos son las principales
estructuras encadenadas que encontramos:


Rep. Encadenadas circulares que enlazan el último elemento con el
primero, así se puede acceder desde un elemento a cualquier otro (esté
situado delante o detrás) y podemos recorrer la estructura entera.
Rep. Doblemente encadenada, cada elemento apunta, no solo al
siguiente, sino también al anterior, de forma que podemos recorrer la
estructura en dos sentidos distintos.
Rep. encadenada circular
Rep. doblemente encadenada
En resumen, tenemos a continuación una tabla comparativa de
implementación de los sacos, cuya confección es de ayuda inestimable en el
momento de decidir cuál es la mejor implementación de un TAD en un contexto
determinado.
Estrategia
T(crea) T(añade)
T(borra)
T(nAps)
E(Saco)
Mov.
Rep. Secuencial
mxn
n
mxn
mxn
(m+1)xn0+2k
Sí
Rep. secuencial marcada
mxn
mxn
mxn
mxn
(m+1)x(n0+b)+2k
No
Rep. secuencial ordenada
mxn
mxn
mxn
Rep. encadenada
mxn
n
mxn
mxn
(m+1)x(n0+k)+3k
No
mxn
mxn
mxn
mxn
(m+1)x(n0+k)+3k
No
Rep. encadenada circular
log(m) x n (m+1)x(n0+k)+3k
Sí
Siendo m: máximo, n: E(Elem), k: E(nat) y b: E(bool)
6. IMPLEMENTACIÓN DE TAD CON MEMORIA DINÁMICA
Las representaciones vistas hasta ahora se basan en el uso de vectores
que, a veces resultan inconvenientes por que:



Hay que determinar su dimensión en algún momento.
El espacio ocupado por la estructura es fijo, independientemente de que esté
lleno o vacío.
La dimensión del vector actúa como cota del número máximo de elementos
que caben en el mismo, de forma que los TAD son finitos.
Para solucionar estos problemas se presenta la noción de memoria
dinámica que es el espacio del almacenamiento de datos que se adapta a las
necesidades del programa. Es decir, el programa puede ir depositando datos en la
Estructura de la información · 11
memoria dinámica a medida que estos se crean y aumentan; cuando ya no son
necesarios, el espacio usado para almacenarlos queda libre y es reutilizable.
La memoria dinámica en Java se caracteriza porque:



Cuando ya no hay ningún apuntador que de acceso a un objeto, éste es
destruido automáticamente por el recolector de basuras; aunque se puede
invocar manualmente al recolector también.
Los datos declarados de una clase (variables, atributos) nunca contienen los
valores reales, sino apuntadores a los mismos.
La creación del objeto se relaciona con la inicialización de sus atributos
mediante los constructores. Esto favorece que el objeto no se cree hasta que
realmente se necesita.
Para duplicar un objeto en Java utilizamos la función
clone que se limita a duplicar el estado del objeto pero los
atributos del nuevo objeto en realidad apuntan a los mismos del
viejo.
Comportamiento de Clone
No obstante, el uso de memoria dinámica también tiene
sus riesgos:



La memoria dinámica tampoco es infinita, dado que la memoria del ordenador
también puede agotarse.
Los punteros con clone son referencias directas a la memoria que, en algún
punto del programa pueden causar errores algorítmicos.
Varios punteros pueden designar un mismo objeto, la modificación del objeto
desde un puntero determinado da lugar a la modificación del objeto apuntado
por el resto de los punteros.
12 · Estructura de la información
TEMA 2 SECUENCIAS Y ÁRBOLES
1. PILAS Y COLAS
Las pilas y las colas son los dos modelos básicos de secuencias a los que se
puede acceder según una estrategia restringida diferente en cada caso. Los dos
tipos de secuencias se pueden considerar como un almacén lineal de elementos,
pero mientras que en el caso de las pilas la política de acceso es que lo último que
entra es lo primero que sale (pila de platos, por ejemplo), en el caso de las colas se
sigue un principio diferente: lo primero que entra es lo primero que sale (fila en el
cine para entrar a la sesión).
Las pilas se utilizan para transformar un programa recursivo en un
programa iterativo. También aparecen en el entorno de la programación en la
gestión de las llamada a subrutinas, asegurándonos que se vuelve siempre al
mismo punto que ha llamado a la rutina.
Las colas suelen aparecer con frecuencia para asegurar un acceso justo a
varios recursos.
1.1. Modelo y especificación
En ambos TADs, pilas y colas, son necesarias las siguientes operaciones:






Crear la secuencia vacía.
Añadir un elemento por un extremo,
Eliminar el elemento de uno de los extremos: en el caso de las pilas será el
último incluido y en el de las colas será el primero.
Obtener (consulta) el elemento de uno de los extremos: igual que en el caso
anterior es aconsejable saber si es el primero o el último.
Averiguar la longitud de la secuencia
Averiguar si la secuencia está vacía o no.
Estas especificaciones son válidas para pilas y colas no acotadas. En caso
de estar acotadas habrá que variar:



Crear la secuencia vacía: añadirá un parámetro con el número máximo de
elementos.
Añadir un elemento: debe controlas que no se sobrepasa la capacidad de la
secuencia.
Lleno?: Para saber si la secuencia admite la inserción de más elementos o no.
1.2. Implementaciones secuenciales. Vectores circulares.
Las implementaciones secuenciales se basan en el hecho de que los
elementos de la estructura se disponen de forma contigua en un vector, de modo
que la adyacencia lógica se corresponde con la adyacencia física. Para ello,
haremos uso de los apuntadores que sean necesarios.
La implementación secuencial de las pilas es muy sencillo, solo
necesitamos un apuntador de sitio libre que identifique donde acaba la parte
ocupada y donde empieza la parte libre y servirá de referencia para las operaciones
de inserción, supresión y consulta. En la imagen de la página siguiente podemos
observar la estrategia de la representación secuencial de las pilas. En este caso la
representación del tipo incluyo dos atributos: la tabla y el apuntador. El
invariante de la representación establece la restricción de valores sobre el
apuntador entre cero y el máximo dado y el coste de todas las operaciones es
Tema 2
Secuencias y árboles
1. Pilas y colas
2. Listas con punto de interés
3. Árboles binarios
4. Colas prioritarias
Estructura de la información · 13
Representación secuencial de las pilas
constante, mientras que el espacio necesario será
proporcional al número máximo de elementos de la
tabla.
La implementación secuencial de las
colas tiene una diferencia importante, y es que
ninguno de los dos extremos está fijo, como
podemos observar en la imagen lateral. Este
esquema plantea un problema obvio, el apuntador
de la derecha puede llegar al extremo derecho del
vector sin que la cola esté realmente llena, porque
quede un trozo libre a la izquierda. La solución
consiste en llevar el apunto sde la derecha a la
izquierda o, dicho con otras palabras, en considerar
que después de la posición max-1 viene la posición
0, con lo cual perdemos el concepto de derecha e
izquierda, y encontramos un sistema de gestión
circular que queda claro también en la
representación inferior.
Representación secuencial de las colas
La circularidad la obtenemos de forma
natural con la operación mod que calcula el resto
de la división entera, asi la expresión (x+1)mod
max, será x+1 si x se encuentra entre 0 y max-1 y
valdrá 0 si x=max-1.
Por otro lado, si los dos apuntadores son
iguales, el motivo puede ser tanto que la cola esté
vacía como llena; necesitamos un método adicional
para este caso particular, y lo que haremos será
aprovechar el atributo tamaño usado como
contador de elementos.
Las operaciones quedan de coste constante
y el espacio quedará lineal respecto al número
máximo de elementos, igual que pasaba en las
pilas.
1.3. Implementaciones encadenadas
Representación encadenada de una cola
Las implementaciones encadenadas de
cualquier clase de secuencia, exigen la existencia
de un encadenamiento único, de forma que si el
elemento A es el predecesor de B, el apuntador de
la celda que almacena A apunta a la celda que
almacena B.
Así observamos que en las colas son necesarios los
dos apuntadores, aunque nos podemos ahorrar uno
si
establecemos
una
representación
encadenada circular, es decir, si encadenamos el
último elemento al primero. Para mayor facilidad en
las implementaciones creamos el elemento fantasma
que nunca se borra; y así el último elemento apunta
al fantasma, y éste al primero.
Toda la mecánica de inserción y supresión sobre las
colas, puede observarse en la imagen lateral adjunta.
14 · Estructura de la información
2. LISTAS CON PUNTOS DE INTERÉS
Representación encadenada de las colas
El TAD de las listas es la generalización de los
tipos abstractos pilas y colas; pues en un alista se puede
insertar un elemento en cualquier posición y borrar y
consultar cualquiera de los mismos.
En la vida cotidiana las listas con punto de
interés pueden ser el hecho de seleccionar una canción
concreta de un CD o el cursor en Word que sirve de
referencia para saber donde se van a insertar o borrar
los siguientes caracteres, no teniendo que estar
necesariamente colocado al final.
2.1. Modelo y especificación
Como su nombre indica, las listas con punto de
interés se caracterizan por la existencia de un
elemento distinguido que sirve de referencia para casi todas las operaciones del
tipo; decimos que el punto de interés apunta al elemento distinguido. El punto de
interés puede desplazarse por la lista desde el primer puesto hasta el último en el
que haya un elemento, más allá dará error para ciertas operaciones como pueden
ser consulta, borrado…
Las operaciones que definen el TAD son:










Crear una lista vacía: Retorna una lista sin ningún elemento y deja el punto
de interés en el extremo derecho.
Insertar un elemento: Inserta un elemento ante el punto de interés, que no
cambia (decisión arbitraria sobre donde insertar los nuevos elementos).
Suprimir un elemento: Borra el elemento distinguido al que apunta y el
punto de interés queda sobre el siguiente elemento (esto es una decisión
arbitraria, pero alguna decisión sobre el apuntador había que tomar).
Modificar un elemento: Modifica el valor del elemento distinguido, sin
modificar el punto de interés.
Consultar un elemento: Retorna el elemento distinguido o da error si el
punto de interés está en el extremo derecho.
Obtener la longitud: de los elementos que contiene la cadena.
Mirar si la lista está vacía.
Poner el punto de interés al principio: Lo coloca sobre el primer elemento
si lo hay o en el extremo derecho si no hay ninguno.
Avanzar el punto de interés: El elemento distinguido pasa a ser el siguiente
al actual. O da error si ya estaba situado en el extremo derecho.
Mirar si el punto de interés está en el extremo derecho: Retornando
cierto o falso según el caso.
2.2. Implementación secuencial
Encontramos dos tipos de estrategias de representación secuencial: por un
lado la estrategia de almacenamiento consecutivo de los elementos en un vector, y
por otro la estrategia de partición de la lista en dos pilas.
En el almacenamiento consecutivo de los elementos en un vector
encontramos una estrategia habitual de almacenamiento en la parte izquierda del
vector, con un apuntador ll a la primera posición libre y act como punto de interés.
Observamos en la gráfica lateral la representación de la inserción y supresión de
elementos. Denotar que además este tipo de representación tiene su mayor
Ejemplo de operaciones en
lista con punto de interés
Estructura de la información · 15
dificultad en esto precisamente: la inserción y supresión, pues exige el
desplazamiento de elementos para dejar espacio libre (inserción) o para recuperar
el sitio liberado (supresión), y quedan de coste lineal sobre el número de elementos
de la lista.
Representación secuencial consecutiva de las listas con
Punto de interés
En la estrategia de partición de la lista en
dos pilas lo que hacemos es dividir la lista en dos
partes, a la izquierda van los elementos anteriores al
punto de interés, en el centro quedan las zonas libres y
a la derecha encontramos los elementos que van
después del punto de interés. Cuando se inserten
elementos en la lista lo harán al final de la parte
izquierda y cuando se borren será al inicio de la parte
derecha. Así pues la gestión es como si se tratase de
dos pilas. En la pila de la izquierda siempre se inserta y
en la derecha se borra y además al avanzar insertamos
en la pila izquierda la pila de la cima derecha y
borramos esta última.
Estas operaciones de inserción y borrado
quedan de coste constante, ahora bien, la operación de
ir al principio es de coste lineal pues es necesario apilar
en la pila de la derecha todos los elementos de la pila
izquierda, lo que implica movimientos múltiples.
Por este motivo, elegiremos la estrategia secuencial en dos pilas cuando
haya muchas intersecciones y supresiones y pocos recorridos (en listas muy
volátiles) y la estrategia secuencial simple en caso contrario. También puede ocurrir
que cambiemos la representación durante la vida de la lista si hay varias etapas:
unas más volátiles y otras menos.
Representación secuencial de las listas con
Punto de interés en dos pilas
2.3. Implementación encadenada
Otra tercera opción es la representación
encadenada. En este caso nos es necesario un
apuntador que nos lleve al elemento distinguido, pero
si el apuntador apunta al elemento distinguido, la
inserción sería costosa de implementar pues el
elemento anterior al distinguido tendría que apuntar al
elemento insertado, y éste no es accesible
directamente. La solución, por tanto, consiste en
apuntar al anterior al distinguido, así la inserción,
supresión etc, están disponibles pues conocemos el
elemento anterior al distinguido, el distinguido y el
posterior a éste.
Ahora bien, si el elemento apuntado es el
anterior al distinguido, si éste es el primero o la lista
está vacía: ¿adonde apuntamos? Pues nos evitamos
este problema creando el elemento fantasma que nos
ayudará en este caso especial. Vemos a continuación
un esquema de la estrategia de representación
encadenada con su inserción y supresión. El coste de
las operaciones siempre es O(1), salvo la creación de la
lista que queda O(max).
16 · Estructura de la información
3. SECUENCIAS Y ÁRBOLES
Representación encadenada de las listas
con punto de interés
En los árboles binarios los elementos se
encuentran organizados en nodos, ya no hay un
elemento anterior y un elemento sucesor sino que se
forma una jerarquía y, en el caso de los árboles
binarios esta jerarquía se caracteriza porque de cada
nodo solo parten dos hijos. Las relaciones jerárquicas en
nuestra vida habitual por ejemplo se observa en los
árboles genealógicos
3.1. Modelo y especificación
Todo (sub)árbol tiene una raíz única y cero o
más subárboles y todo nodo es la raíz de algún subárbol.
Se denomina aridad de un nodo al número de
subárboles que lo tienen como raiz. Cuando un árbol está cerrado por prefijo
significa que si existe el elemento 331, también existe el 33 y el 3; esto lo podemos
observar en la figura adjunta.
Las operaciones del TAD de los árboles binarios pueden ser:




Crear el árbol vacio: retorna el árbol sin ningún elemento.
Enraizar un elemento con dos subárboles.
Obtener la raíz de un árbol: Obtiene la etiqueta del nodo raíz de un árbol no
vacío.
Obtener los subárboles izquierdo y derecho: Retorna el subárbol
correspondiente de un árbol no vacío.
3.2. Implementación encadenada
Como es habitual podemos implementar los árboles con estrategia
secuencial o encadenada. Dado que la implementación encadenada es más fácil de
implementar (al contrario de las pilas y colas) que la secuencial, empezaremos por
las primeras.
En la representación encadenada usando memoria dinámica, se
añade un apuntador de cada nodo a los dos hijos del nodo, si un hijo no está, el
encadenamiento correspondiente es nulo. Las operaciones quedan de orden
constante mientras que el espacio utilizado es lineal con respecto al número de
nodos que lo forman. El Invariante debe controlar que la forma del árbol sea la
correcta, prohibiendo que haya más de un encadenamiento apuntando al mismo
nodo
La representación encadenada con vectores, si presentamos cada
árbol en un vector, las operaciones de enraizar y obtener los subárboles izquierdo y
derecho exigen duplicar o destruir (es decir, insertar en la pila de sitios libres) todos
los nodos de un árbol, por eso resultan de orden lineal sobre este factor.
3.3. Implementación secuencial por montículo
Se basa en el almacenamiento de las etiquetas en las posiciones del vector.
Esto, en las secuencias era relativamente sencillo, pero al considerar que cada nodo
tiene dos sucesores, la implementación se nos complica. La solución consistirá en
deducir una fórmula que asigne a cada posible nodo del árbol, una posición dentro
del vector y, si hay nodos que no existen, la posición correspondiente del vector se
marcará como desocupada.
Cerrado por prefijo
Estructura de la información · 17
Así lo que hacemos es situar el nodo en la primera posición, el hijo
izquierdo de la raíz en la segunda, el hijo derecho de la raíz en la tercera, el hijo
izquierdo del hijo izquierdo de la raíz en la cuarta… y así, según vemos en el
ejemplo lateral obtenemos un árbol y su representación secuencial. Por ejemplo la
posición 212 en el árbol se calculará para el vector: 2^3 + (4+0+1) = 13.
A partir de aquí podemos derivar las
diferentes relaciones entre la posición que ocupa un
nodo y la que ocupan sus hijos, hermano y padre.
Un árbol y su representación secuencial
Esta representación secuencial exige que cada
árbol se implemente en un vector único y las
operaciones de enraizar y obtener subárboles resultan
de coste lineal sobre el número de nodos
involucrados. Su utilidad principal, por ello, reside en
árboles con operaciones individuales sobre nodos.
Hemos de darnos cuenta que si el árbol tiene pocos
nodos pero muchos niveles, el espacio ahorrado por la
ausencia de apuntadores no compensa las posiciones
del vector desocupadas. El caso ideal se produce al almacenar árboles
completos: todos sus niveles contienen todos los nodos que puede haber.
También puede ser útil en los árboles cuasicompletos, que son aquellos en los
que solo en su nivel inferior hay posiciones desaprovechadas pero aun así serán las
posiciones derechas pues mantendrá su orden de árbol que es casi completo
(observemos que el árbol completo es un caso especial de árbol cuasicompleto).
3.4. Recorridos de árboles binarios
Ejemplo de recorrido
Es habitual que los programas que trabajan con árboles necesiten aplicar una
consulta que les lleva a visitar todos los nodos. Para ellos existen 3 recorridos
diferentes que se pueden realizar:



Recorrido en preorden: si a está vacio se acaba el recorrido; si no, primero se
visita la raíz de a y a continuación, se recorren en preorden los subárboles
izquierdo y derecho. Suele utilizarse en el cálculo de atributos heredados de
una gramática, como en la construcción de compiladores. En el ejemplo lateral
el recorrido sería: A B D G J E F H I.
Recorrido en inorden: si a está vacío, se acaba el recorrido; si no, primero se
recorre el subárbol izquierdo de a en inorden, a continuación su raíz, y
finalmente el subárbol derecho de a en inorden. En este caso si todos los nodos
del subárbol de la izquierda presentan una etiqueta menor que la raíz y los de
la derecha una mayor, el árbol es un árbol de búsqueda que se caracteriza por
la ordenación de los elementos en un recorrido inorden. Recorrido del ejemplo:
D J G B A E C H F I.
Recorrido en postorden: si a esta vacío se acaba el recorrido; si no, primero
se recorren sus subárboles izquierdo y derecho y, a continuación su raiz. Es
equivalente a la evaluación de una expresión matemática, donde en las hojas
existen valores y en los nodos intermedios los símbolos de la operación. En el
ejemplo el recorrido es: J G D B E H I F C A.
4. Colas prioritarias
La cola prioritaria es una cola donde los elementos no se insertan por el
final, sino que se ordenan según una prioridad que tienen asociada. Por ejemplo
cuando la CPU ejecuta determinadas tareas no por el orden de llegada, sino por
una prioridad dada. Definimos por tanto la cola prioritaria como un caso especial de
secuencia de tal forma que si a<b, a tendrá que salir antes que b en la cola.
18 · Estructura de la información
En cuanto al modelo y especificación debemos reconocer las siguientes
operaciones:




Crear la cola vacía
Encolar un elemento según su prioridad
Eliminar el primer elemento de la cola prioritaria, donde se requiere
evidentemente que la cola no esté vacía.
Obtener el primer elemento: retorna el elemento más prioritario.
Estos requerimientos nos pueden llevar a pensar que la mejor
implementación sea una lista ordenada o desordenada, pero esto aporta varias
dificultades. En un alista desordenada, la inserción queda de coste constante, pero
la supresión y la consulta exigen una búsqueda lineal. En la liste ordenada, la
inserción requiere una búsqueda lineal a cambio de un coste constante en la
consulta, mientras que la supresión depende de la representación concreta de la
lista. En cualquier caso queremos evitar cualquier operación de coste lineal y esto
lo conseguimos con una representación de árbol parcialmente ordenado cuyo
coste logarítmico de las operaciones nos es satisfactorio.
La característica más importante de los árboles parcialmente ordenados y
además cuasicompletos es que el menor nodo del árbol reside en la raiz. En la
imagen lateral observamos un árbol ordenado y cuasicompleto. Es de especial
utilidad estudiar el proceso de inserción y supresión en el árbol

Inserción: Se inserta el elemento en la primera posición libre del árbol en
recorrido lineal, en este caso se inserta como la hoja del último árbol. Al no
cumplir la condición de ordenación, se intercambian el padre y el hijo hasta que
se cumple. En el peor de los casos el número de intercambios será igual al
número de niveles del árbol, lo que nos asegura un coste de la operación
O(log(n)).
Supresión: Dado que el elemento menor reside en la raíz, la supresión
consiste en eliminarla. Para formar un nuevo árbol cuasi completo,
simplemente movemos el último elemento del árbol hasta la raíz; sin embargo
esta raíz no será menor que sus hijos, por lo que reestructuramos el árbol pero
en sentido inverso, bajando el padre con el hijo hasta cumplir el criterio de
ordenación. El coste, igualmente nos queda logarítmico.
En la representación de la clase queda claro que se utiliza un vector
para guardar el montículo; la primera posición del vector contendrá la raíz del
árbol. El invariante de la representación asegura que la relación de orden entre los
nodos se cumple y en cuanto a las operaciones de inserción y supresión, notamos
que no se intercambian los elementos a cada paso, sino que el elemento en
proceso de ubicación se mueve hasta que no se sabe la posición que le
corresponde, lo que ahorra la mitad de los movimientos, aunque no mejore el coste
asintótico.
El algoritmo de ordenación heapsort es una aplicación de estas colas
prioritarias que consiste en ordenar una lista con el menor coste posible. En un
primer paso se construye un montículo con la lista y, a continuación, se deshace el
montículo para formar el resultado ordenado. Podríamos formar el montículo por un
lado y el vector por otro, esto nos daría un coste logarítmico pero el coste espacial
sería mayor debido al espacio adicional y esto es lo que pretende solucionar este
algoritmo.
Consideramos entonces que el vector tiene dos partes: una dedicada a
simular la cola y la otra contiene una parte de la solución. En la cola, los elementos
se ordenarán según la relación > de forma que en la raíz siempre tenemos el
mayor elemento. En primer lugar formamos los nodos, empezando por abajo y de
derecha a izquierda y subiendo por niveles formando un árbol cuasi completo y
ordenado.
Inserción
en
un
árbol
parcialmente ordenado y
cuasicompleto
Estructura de la información · 19
Ordenación mediante heapsort
En un segundo bucle construimos el vector ordenado, a cada paso se
selecciona el mayor elemento de la cola y se coloca en la posición
correspondiente del vector, de modo que todos los elementos a su
izquierda son menores (aunque no están ordenados) y los de la
derecha son mayores y además están ordenados). Se continúa así
hasta tener toda la ordenación completa.
Observamos en la imagen lateral un ejemplo de ordenación
según este método de heapsort
20 · Estructura de la información
TEMA 3 FUNCIONES Y CONJUNTOS
1. MODELO Y TAD DE LAS FUNCIONES Y LOS CONJUNTOS
Los TADs estudiados hasta ahora no son suficientes para implementar de
forma eficaz todos los casos que informáticamente puedan dársenos. En este caso
nos falta un tad importante como es el de las funciones.
Una función es una relación establecida entre dos dominios de datos A y
B, de tal forma que a cada elemento de A le corresponde como mucho un elemento
de B. Las funciones de A y B se denotan mediante A  B. El conjunto de A se llama
dominio de la función y B es el alcance. Los elementos de A se denominan claves y
los de B información. A veces también se les llama tabla (vease figura lateral),
precisamente porque la representación gráfica de una función es una tabla, pero en
nuestro caso este vocablo quedará restringido a una técnica concreta de
implementación de las funciones y los conjuntos.
1.1. Modelo para las funciones parciales
Las funciones parciales son aquellas en las que no podemos asegurar que
todos los elementos de A tengan una información asociada (en contraposición a las
totales en las que sí se asegura). Los métodos de las funciones parciales son:





Crear la función vacía: con dominio real vacío.
Añadir un nuevo par (clave, información). Si existe una asociación anterior con
esta clave, se pierde.
Borrar un par de la tabla: Elimina la clave referenciada, si es que existe.
Obtener la información asociada a una clave: Aplica la función en un punto y
obtiene la información asociada a este. La clave debe estar definida.
Averiguar si una clave está en la tabla: Devuelve un booleano con la respues a
si una clave determinado existe o no (Consulta).
1.2. Modelo para las funciones totales
En las funciones totales existe el llamado elemento indefinido denotado
por indef., que se asociará por defecto a todos los elementos de A y nos permitirá
asegurar así que las funciones son efectivamente totales: La función de creación
ahora no crea un dominio vacío, sino definido; la operación borrar cambia el
antiguo valor asociado por el indef.; la operación de consulta deja de requerir
condiciones sobre el dominio de la función.





Crear la función vacía: con el dominio ya definido.
Añadir un nuevo par (clave, información): Define la función en un punto A,
pero no permite definir como alcance el valor indefinido.
Borrar un par de la función: Cambia el antiguo valor asociado por el valor
indefinido.
Obtener la información asociada a una clave: Obtiene la información a partir de
la clave.
Comprobar si una clave tiene información asociada definida.
1.3. Variante: los conjuntos con clave
Los conjuntos con clave son aquellos en los que el identificador se
encuentra dentro del propio elemento. Por ejemplo en un conjunto para almacenar
los empleados de una empresa, una persona se caracteriza por toda una serie de
Tema 3
Funciones y Conjuntos
1. Modelo TAD de las funciones y
conjuntos
2. Implementación de las
funciones mediante dispersión
3. Implementación de las
funciones mediante árboles
binarios de búsqueda
Tablas
Función AB
A
1
2
3
B
12
24
36
Estructura de la información · 21
atributos (sueldo, DNI, nombre y apellidos, categoría laboral) y uno de ellos (por
ejemplo el DNI) sirve como medio de referencia.
Las operaciones quedan definidas como sigue:





Crear el conjunto vacío.
Añadir un nuevo elemento al conjunto: Añade un elemento que no estaba o
sustituye uno que ya estaba. No puede haber más de un elemento con la
misma clave (precondición).
Borrar un elemento del conjunto: Elimina un elemento a partir de su clave; y ya
sabemos que no puede haber más de un elemento con la misma clave.
Obtener un elemento del conjunto a partir de su clave: Obtiene la información
asociada a partir de la clave.
Comprobar si hay algún elemento en el conjunto identificado por una clave,
sabiendo además que como mucho solo habrá uno.
1.4. El TAD de los conjuntos
Se diferencia del TAD anterior en que realmente no exigimos que un
elemento tenga una parte diferenciada que lo identifique, y lo usaremos
especialmente para definir conjuntos de tipo simple como tipo numérico o cadena
de caracteres.
Las operaciones definidas en él son:




Crear el conjunto vacío
Añadir un nuevo elemento al conjunto.
Borrar un elemento del conjunto.
Comprobar si un elemento pertenece al conjunto.
Dada la similitud entre todos los TAD vistos en este primer apartado, en el
resto del tema, nos centraremos en el primer modelo: las funciones parciales.
2. IMPLEMENTACIÓN DE LAS FUNCIONES MEDIANTE DISPERSIÓN
Para implementar las funciones de las que hemos tratado en el punto
anterior, la representación más intuitiva será un simple vector, indexado por las
claves que contienen la información asociada a sus posiciones. Lo malo de esto es
que a veces el domino de las claves no resulta válido como índice de vector o que
el dominio real de la función será menor que el dominio de sus claves (por ejemplo
utilizar el DNI para identificar a los solo 200 trabajadores de una empresa).
Lo que vamos a hacer es llevar a cabo esta implementación de la que
hemos hablado a través de vectores, pero solucionando los dos problemas
anteriores:
 Llevaremos a cabo una función que asigna a las claves un entero que se puede
usar como índice del vector.
 Para no desaprovechar espacio, simplemente ajustamos el número de
posiciones a la dimensión esperada del dominio real de la tabla.
Lo que vamos a llevar a cabo se denomina tabla de dispersión. La
función que asigna enteros a las claves se llama función de dispersión y los valores
enteros asignados, valores de dispersión. Eso sí, será necesario tener una idea
aproximada del número de elementos que se guardarán en la tabla. Pero nos surge
un problema evidente; si no van a existir tantas posiciones del vector como claves
en el dominio de la función existirán claves que se tendrían que almacenar en una
misma posición, eso es lo que denominamos colisión; para evitar esto tenemos
que implementar una política de organizaciones de dispersión.
22 · Estructura de la información
El objetivo de la función de dispersión (como se ve Función de dispersión
en el ejemplo lateral) es asignar un entero llamado valor de
dispersión a cada una de las claves que forman el dominio de
la función; de tal manera que esa clave se encontrará entre 0 y
r-1 (siendo r el número de claves que se esperan dentro de la
tabla).
La función de dispersión tiene que distribuir entonces
uniformemente el dominio de las claves en el intervalo (0, r-1),
además debe ser totalmente aleatoria para evitar que haya más
colisiones de la cuenta y tiene que ser rápida de calcular para evitar que se retrase
el acceso a la tabla.
Un ejemplo bastante típico es el de las funciones de dispersión sobre
cadenas de caracteres. Lo que vamos a realizar es asignar a cada letra un valor
y sumarle ese valor según la posición en que se encuentre. Lo primero es definir
qué valores ASCI son los que tendremos en cuenta para llevar a cabo la función. Si
estamos definiendo nombres y apellidos de personas descartaremos todos los
valores tipo asterisco, barras, etc, definiremos solo letras en mayúsculas y
minúsculas, guiones y quizá el punto, poco más. Eso nos reduce los 128 caracteres
a solo 54 caracteres de código. Hecho esto llevamos a cabo la función de dispersión
como la suma ponderada según la posición, que podemos ver en el ejemplo de la
tabla lateral.
Suma ponderada
Sea a = ”HOLA” y b = 26,
entonces haremos:
H= conv(H) = 8
O= conv(O)·26 = 390
L = conv(L)·676 = 15.576
A = conv(A)·17.576 = 17.576
HOLA = 26.186
Esta conversión tiene ciertas deficiencias, en general podemos llegar
fácilmente a tener un desbordamiento de cálculo, por ejemplo en una función
como la definida en el ejemplo a partir del 8º carácter en una máquina de 32 bits
se puede ya producir desbordamientos. Tenemos dos posibles soluciones:


Ignorar los bits que se van generando fuera de la dimensión de la
palabra del computador: lo cual ignora cierta cantidad de
información y reduce la aleatoriedad de la clave, amén de que a
veces es difícil y poco eficiente detectar e ignorar este
desbordamiento.
Particionar las claves de entrada y combinar los resultados
parciales mediante sumas.
Partición claves de entrada
División de una clave de 22 caracteres de letras
mayúsculas en 6 fragmentos, los cinco primeros
de 4, y el último, de 2 caracteres.
Aparte de este tipo de funciones de dispersión sobre cadenas de caracteres
existen otras muy típicas funciones de restricción de un entero a un
intervalo. Queremos transformar enteros grandes en índices válidos dentro del
dominio (0, r-1). Una de las más utilizadas es la función módulo, es uniforme,
rápida de calcular y simple MOD(x) = x mod r. Eso sí, el valor de r es fundamental
para una buena distribución de esos índices. En general no es bueno que r sea par
ni múltiplo de 3 porque existirían muchas colisiones, lo ideal es que r no tenga
divisores menores que 20.
Ahora bien, tenemos las funciones de dispersión, pero éstas
provocan alguna que otra colisión (si hemos definido una buena
función de dispersión, serán pocas) que debemos resolver. La forma
más sencilla es organizar listas con las claves sinónimas que provocan
estas
colisiones,
se
tendrían
que
organizar
mediante
encadenamientos y dan lugar a representaciones encadenadas que se
denominan tablas de dispersión encadenadas abiertas.
Tabla de dispersión encadenada abierta
En el gráfico lateral se muestra la lista correspondiente a los s sinónimos
que hay para claves con valor de dispersión igual a 0. Si asociamos una estructura
individual a cada una de las listas, nos vemos abocados a representarlas mediante
memoria dinámica, porque de otro modo la suma del espacio desperdiciado en las
diferentes listas podría llegar a ser inaceptable.
Estructura de la información · 23
El coste asintótico queda O(r) para la creación de la tabla y de complejidad
lineal sobre la longitud de las listas para el resto. Si la longitud de las listas es
corta, este factor lineal se comporta realmente como si fuera constante. Por eso
hace falta que r sea aproximadamente igual al número esperado de claves y que la
función de dispersión realmente distribuya bien, de forma que lo más probable sea
que la mayoría de las listas quede de una longitud parecida.
Las tablas de dispersión en Java se implementan a través de la clase
Hashtable contenida en el paquete java.util. Tiene operaciones individuales como
put, get y remove y dispone de los predicados isEmpty, containKey y contains (ésta
última para saber si un valor está en la tabla).
3. IMPLEMENTACIÓN DE LAS FUNCIONES MEDIANTE ÁRBOLES BINARIOS DE
BÚSQUEDA
Pese a todas las ventajas descritas anteriormente, la dispersión presenta
algunas desventajas que también es preciso aclarar:




El buen comportamiento de la dispersión depende de una buena función de
dispersión; pero aunque hayamos definido una muy buena siempre existe un
cierto componente aleatorio en su funcionamiento.
Es necesario determinar el número aproximado de elementos que se espera
guardar en la tabla.
Hay que efectuar un análisis para decidir qué función y que organización de
dispersión son las mejores para el problema actual.
Si se quiere ampliar el concepto básico de tabla para efectuar otro tipo de
operaciones, podemos tener problemas.
La existencia de estos inconvenientes nos obliga a enriquecer el modelo de las
tablas con operaciones de recorrido ordenado, estableciendo un nuevo tipo de
modelo que son las funciones recorribles ordenadamente. Este modelo se
diferencia de las funciones habituales por el añadido de las operaciones de
recorrido propias de los iteradores con la restricción de ordenación. En el momento
de determinar el modelo y tal como sucedía en las listas con puntos de interés,
debemos registrar que claves se han examinado ya y cuales no. Elegimos el
conjunto de claves ya visitadas y según ello obtenemos los siguientes métodos:




Función
Función
Función
Función
posiciona.
avanza
consulta
fin??
Veamos estas funciones con dos tipos de búsquedas los árboles binarios de
búsqueda y los árboles binarios de búsqueda AVL. Los árboles binarios de
búsqueda son árboles binarios que cumplen una de las dos condiciones
siguientes:
 El árbol a está vacío.
 La raíz de a es mayor que todos los elementos de su árbol izquierdo (si lo
tiene) y menor que todos los elementos de su árbol derecho (si lo tiene) y a su
vez sus subárboles izquierdo y derecho son también árboles de búsqueda.
Árboles binarios de búsqueda
La propiedad que hace interesante a estos árboles es que sea cual sea su
forma el recorrido en inorden proporciona los elementos del árbol
ordenados. Las operaciones que vamos a realizar en este árbol son:

Búsqueda de un elemento: si a está vacío el elemento no está en el árbol. Si a
no está vacío y no es el elemento buscado, por su valor sabremos si debemos
seguir buscando en el árbol derecho o izquierdo del mismo.
24 · Estructura de la información


Inserción: Para que al insertar un elemento el árbol resultante siga siendo de
búsqueda, se aplica primero la búsqueda del elemento, y si no se encuentra se
inserta allá donde se haya posicionado la búsqueda anterior. En el ejemplo
lateral se observa como se insertan dos nuevos elementos como dos hojas
(como pasará siempre). Evidentemente el peor coste posible es tener que
recorrer todo el árbol, si éste es cuasicompleto el coste será logarítmico, sin
embargo si se trata de un árbol degenerado con un solo hijo por cada nodo,
nos encontraremos frente a un coste n, ya que no existe ninguna propiedad
que restringa la forma del árbol.
Supresión: Primero se aplica el algoritmo de búsqueda habitual. Si el
elemento no se encuentra, la supresión acaba; si el elemento se encuentra, se
procede a eliminar el nodo n que lo contiene, ahora bien el comportamiento
depende del número de hijos que tiene el nodo n, puede ocurrir:
o Si n es una hoja, simplemente desaparece y ya está.
o Si n tiene un único subárbol, éste se sube a la posición que ocupaba n.
o Si n tiene dos hijos, ninguno de los dos métodos anteriores asegura
que nos siga quedando un árbol binario de búsqueda. Para conservar
esta propiedad se mueve o bien el mayor elemento de los elementos
menores que v (dentro del subárbol izquierdo del árbol que tiene n
como raíz) o bien el menor elemento de los elementos mayores que v
(subárbol derecho). En cualquier caso, el nodo n´ que contiene el
elemento que responde a esta descripción es o bien una hoja o un
nodo con un único hijo, de forma que a continuación se le aplica el
tratamiento correspondiente en estos casos. En el ejemplo lateral
observamos estas supresiones con un ejemplo. La eficiencia temporal
es igual a la de la inserción.
Para obtener el mayor de los menores se hace un recorrido en
inorden del hijo derecho (eso hacen las funciones auxiliares para
obtener el máximo y el mínimo de un árbol de búsqueda que nosotros
predefinimos) cuando se podría simplemente bajar de forma repetida
por la rama derecha.
Para borrar un elemento volvemos después a buscar
recursivamente con borra.
Supresión en árbol binario de búsqueda
Un caso especial de árbol binario de búsqueda lo constituyen los árboles
binarios de búsqueda AVL que se caracterizan por ser árboles binarios de
búsqueda equilibrados, es decir, el valor absoluto de las diferencias de las alturas
de sus subárboles es menor o igual que uno y sus subárboles también están
equilibrados. Este equilibrio se mantiene a fuerza de reorganizaciones del árbol al
hacerle inserciones y supresiones; pero nos asegura un coste logarítmico a las
operaciones de acceso individual.
A continuación pasamos a estudiar el caso de inserciones y supresiones en
un árbol AVL.
Inserción en árbol binario
de búsqueda (4 y 3)
Estructura de la información · 25
Para insertar un elemento en un árbol AVL por un lado aplicaremos la
casuística de la inserción “normal” que ya hemos visto anteriormente para los
árboles de búsqueda y después nos aseguraremos que el árbol queda equilibrado.
Si el árbol no resultase equilibrado puede deberse a dos casos:

Caso DD: El subárbol derecho de s tiene una altura superior en una unidad al
subárbol izquierdo de s y el nodo correspondiente al par insertado (a,b) se
inserta en el surbarbol derecho de s y, además, provoca un incremento de su
altura en uno. En este caso lo que se hace es que la raíz B del subárbol
derecho de s pasa a ser la nueva raíz del subárbol y conserva su hijo derecho
que es el que ha provocado el desequilibrio con su incremento de altura y que
con cada movimiento queda a un nivel más cerca de la raíz del árbol, de modo
que se compensa el aumento. La antigua raíz A se s se convierte en hijo
izquierdo de B y conserva su subárbol izquierdo; finalmente el anterior subárbol
izquierdo de B se convierte en su subárbol derecho de A para conservar la
propiedad de ordenación de los árboles de búsqueda. Alguno autores llaman a
estos movimientos rotaciones.
Inserción tipo DD en un árbol AVL
 Caso DI: El nodo se
inserta en el subárbol
izquierdo del subárbol
derecho de s. Este caso
no es tan evidente como
el
anterior
porque
aplicando las mismas
rotaciones de subárboles
no se soluciona el
desequilibrio y por eso
hay que descomponer
también el subárbol de s
que
cuelga
por
la
izquierda de su subárbol
derecho;
por
ello
también hay que distinguir el caso trivial en que este subárbol esté vacío y no
se pueda descomponer. El nuevo nodo puede ir a parar indistintamente a
cualquiera de los dos subárboles que cuelgan de ese subárbol sin que esto
afecte a las rotaciones definidas. En esta página observamos el caso trivial al
que hacíamos mención anteriormente, y en la siguiente vemos un caso más
complejo.
Inserción tipo DI en un árbol AVL
26 · Estructura de la información
Inserción tipo DI en un árbol AVL
Ahora bien, la supresión presenta a su vez 3 tipos de desequilibrio que
pueden llegar a darse:

DD en la supresión: En el ejemplo siguiente observamos que al borrarse un
nodo de alfa (previamente ambos subárboles tenían la misma altura), las
alturas de los dos subárboles no son iguales, y la resolución es también como
se muestra en el ejemplo.
Supresión tipo DD en un árbol AVL

DD con cambio de altura: La altura del subárbol izquierdo es menor que la
del subárbol derecho y además se borra un nodo del subárbol menor, en este
caso alfa, lo que obliga a examinar si algún subárbol que lo engloba también se
desequilibra.
Supresión tipo DD con cambio de altura en un árbol AVL
Estructura de la información · 27

Caso DI: Es el caso más complicado y podemos observar lo que ocurre en el
ejemplo cuando eliminamos el elemento 3.
Supresión tipo DI en un árbol AVL
28 · Estructura de la información
TEMA 4 RELACIONES
1. RELACIÓN
Se definen las relaciones sobre dos dominios A y B como cualquier
correspondencia entre los elementos de estos dos dominios; estas relaciones se
caracterizan por un enunciado que determina qué elementos de A están
relacionados con determinados elementos de B y viceversa. Por ejemplo: se
establece una relación entre los alumnos de un centro académico y las asignaturas
impartidas; la relación surge por el hecho de que los primeros se matriculan en las
segundas; además la relación puede ser valuada (cuando en la relación además
existe un valor determinado) que puede ser la nota obtenida de un alumno en una
asignatura en concreto.
Tema 4
Relaciones
1. Relación
2. Grafos
3. Recorrido de grafos
4. Algoritmos de cálculo de
distancias mínimas
5. Algoritmos de cálculo de
árboles de expansión mínimos
1.1. Método y especificación
En las relaciones no valuadas existen pares de elementos que cumplen
un enunciado, este modelo de representación es el típico modelo cartesiano de una
matriz de filas y columnas o, simplemente podemos tabular los pares de la relación,
como observamos en la figura lateral. Dado el modelo que explicamos, podemos
apreciar que las relaciones combinan operaciones de acceso individual con
operaciones de obtención de grupos de elementos. Por ejemplo, puedo tomar
nota de si un alumno se matricula de una asignatura de terminada, pero también
de qué asignaturas cursa un alumno y cuantos alumnos cursan una asignatura
determinada.
Como resultado de todo ello, las operaciones son las siguientes:





Crear la relación vacía
Establecer una relación entre dos elementos.
Deshacer la relación entre dos elementos: se borra el par.
Averiguar si dos elementos están relacionados o no: retorna un booleano.
Obtener el conjunto de elementos relacionados con uno dado: Es una plantilla
de iteración o, mejor dicho, dos, dependiendo de si estamos interesados en
elementos del primer o del segundo dominio. Así el recorrido cumple las
funciones: posiciona / consulta / avanza / fin (si ha encontrado lo que busca o
si es el último elemento).
En las relaciones valuadas cada par que forma parte de una relación valuada
tiene asociada una etiqueta única. Así en la relación del alumno A con la asignatura
B, de existir estará valuada por la nota C. Las operaciones son parecidas al caso
anterior, si bien hay que añadir un parámetro más a la operación de establecer una
relación. Hay que poder obtener la etiqueta de la relación dados dos elementos
relacionados y hay que añadir la operación de consulta en los recorridos. Así, las
operaciones a realizar son:





Crear una relación valuada.
Establecer una relación valuada, que incluye la relación entre los dos elementos
y el establecimiento de la oportuna etiqueta.
Deshacer la relación valuada entre los dos elementos.
Averiguar si dos elementos están relacionados.
Encontrar la etiqueta de la relación: además suponemos que las etiquetas
presentan dos elementos distinguidos inf y sup, que son las dos cotas del
dominio; esto es fundamental para el correcto funcionamiento de algunos de
los algoritmos sobre grafos que veremos más adelante.
Relación R
Matricial y Tabulación
Estructura de la información · 29
1.2. Implementación secuencial
La representación secuencial de las relaciones no hace más que traducir la
representación gráfica vista anteriormente en estructuras de datos. Es decir,
utilizamos un vector bidimensional para almacenar todos los elementos que
pertenecen a la matriz. Así, en una relación no valuada el vector será de
voléanos y la posición (a,b) será cierta si los elementos a y b están relacionados. En
una relación valuada las posiciones del vector contendrán etiquetas: usaremos la
etiqueta sup para identificar los pares de elementos no relacionados.






Representación por vector
Con estas premisas vemos que:
El invariante de la representación establece que cualquier vector representa
una relación válida.
El coste de duplicar elementos es constante
El coste de acceso individual también es constante
La creación es O(rxs)
Los recorridos O(r) y O(s) dependiendo del dominio que recorren
La complejidad espacial es O(r x s) y es la que determina la operación crea.
Esta complejidad determina el coste temporal de los recorridos; si hay muchos
elementos relacionados esta situación puede ser satisfactoria pero no lo suele
ser en el caso general. Las matrices con pocos elementos relacionados se
denominan matrices dispersas, para las que es evidente que hay que buscar
una representación alternativa.
La solución puede consistir en almacenar solo los pares que forman parte de la
relación, usando un único vector gestionado de la forma habitual (ejemplo lateral),
pero para ello necesitamos determinar el tamaño lo que ya de entrada, no siempre
es posible. Lo que se puede hacer es organizar la parte ocupada en varias zonas,
cada una de las cuales corresponde a todos los pares que tiene uno de los dos
elementos en común (por ejemplo tomamos el primer dominio), así se puede
añadir un vector índice al primer par de cada valor de este dominio. En este caso
las consultas y uno de los recorridos (sobre el primer dominio en este caso) salen
beneficiados y quedan lineales sobre un factor menos, el coste de inserción y
supresión permanece lineal, porque aunque la localización es muy rápida, una vez
insertado/borrado el par buscado, hay que reorganizar toda la estructura.
1.3. Implementaciones encadenadas
Evidentemente la variante estudiada anteriormente es problemática, dado
que la secuencialidad obliga a mover elementos al insertar o borrar pares y además
intentar gráficamente representar dos vectores unidimensionales es complicado
Vamos a intentar mejorar la implementación anterior a través de una
implementación encadenada en la que vamos a tener dos variantes: las listas y las
multilistas.
En la primera representación asociamos una lista a cada
elemento de cada uno de los dos dominios, que contenga un nodo para
cada elemento del otro dominio con el que está relacionado. Entonces
para cada par 8ª,b) existirán dos nodos, uno que corresponde a a y otro
a b, como podemos ver en la imagen lateral. Según esta estrategia, la
complejidad de las operaciones nos queda:
Encadenamiento por lista


 La creación es O(r+s)
 Las consultas individuales serían O(mínimo(r,s)) dado que
buscaríamos en la lista de menor longitud si se pudiese saber, de no ser así,
sería O(máximo(r,s)).
Las operaciones de recorrido quedan lineales sobre la dimensión del dominio
donde se hace el recorrido.
El espacio utilizado es O(rxs) si la relación estuviera llena.
30 · Estructura de la información
Ahora bien, nos podemos plantear si es efectivo tener repetida cada Encadenamiento por multilista
relación en cada uno de los dos dominios, si la relación fuese valuada
necesitaríamos duplicar la etiqueta de relación en cada una de las dos listas,
pero existe una posibilidad para evitar esta duplicación que es la
estructura de multilista. En ella (figura lateral), cada par de la relación
da lugar a un único nodo, por lo que la etiqueta aparece una sola vez, el
resto, los identificadores y encadenamientos aparecen igual. En este caso
utilizamos memoria dinámica para representar los pares, el invariante
establece que todos los nodos accesibles desde un valor de uno de los
dominios identifica este valor en el campo correspondiente y también se
explicita que el valor indefinido de las etiquetas no puede aparecer. La
complejidad temporal de las operaciones no cambia respecto a la propuesta
anterior.
Existe otra variante de esta implementación que consiste en cerrar
circularmente las listas de forma que el último nodo de cada lista apunte a su
cabecera. Así cada elemento se asocia a su fila o columna, según la circularidad
que estemos recorriendo. Esta opción es más costosa en el tiempo, porque para
saber la fila o la columna a la que pertenece un elemento hay que recorrer la lista
hasta el final (por eso es especialmente útil en listas cortas), pero nos permite
ahorrarnos los identificadores de dominio que aparecen en las celdas (en el dibujo
inferior aparece este ejemplo).
Otra solución intermedia es utilizar una clase con listas con
identificadores y otra circular, lo cual resulta útil cuando uno de los dos tipos
tiene una longitud máxima pequeña, y lo podemos observar en el dibujo inferior.
Por ejemplo dado que las asignaturas para un alumno siempre serán muy
pequeñas (a lo sumo 10 ó 12) comparadas con las que imparte el centro (que
puede ser de 400) se puede implementar circularmente la lista de asignaturas
mientras que en la de alumnos parece más adecuado el uso de identificadores.
Encadenamiento por lista circular y encadenamiento por lista con identificador y lista
circular
2. GRAFOS
Los grafos son relaciones establecidas sobre elementos de un mismo dominio
V, lo que se llaman relaciones binarias. Distinguimos varios conceptos dentro del
grafo:




Vértices o nodos son los elementos del dominio de la relación; se representan
mediante círculos que contienen el identificador que los caracteriza.
Arista o arco es un par representando dos vértices relacionados, se representan
mediante líneas que unen los nodos relacionales.
Camino: Cuando dos nodos están unidos mediante una secuencia de aristas.
Círculo: Un camino que empieza y acaba en el mismo vértice.
Estructura de la información · 31



Encadenamiento por lista
Relación simétrica: Cuando la relación se puede dar en los dos sentidos, se
llaman también grafos no dirigidos.
Relación no simétrica: Cuando la relación se da en un solo sentido y es
entonces cuando las líneas que representan las aristas se convierten en flechas
que identifican su sentido.
Relación valuada: En este caso se denominan grafos etiquetados y las etiquetas
aparecen al lado de las aristas.
Los grafos nos sirven para modelar situaciones: en el mundo informático son
usuales las distribuciones geográficas como redes de ordenadores, y puede
servirnos por ejemplo para minimizar los costes de conexión, reconfigurar la red
cuando cae algún nodo, etc. En la tabla lateral observamos dos ejemplos de
modelización, uno de transportes y otro de representación de expresiones
matemáticas que nos evitan la redundancia en la información.
2.1. Modelo y especificación
Definimos los grafos dirigidos osbr eun dominio V con etiquetas de un
dominio E como las funciones parciales definidas sobre V x V que tienen como
alcance las etiquetas; así pues {g : V x V  E}. Denotamos con n el número de
vértices n = ||V|| y con a su número de aristas a = ||dom(g)||. De ahora en
adelante, eso sí debemossuponer lo siguiente:







El dominio V es finito, de lo contrario la mayoría de los algoritmos e
implementaciones no funcionaría.
No hay aristas de un vértice a sí mismo.
No puede haber más de una arista entre el mismo par de vértices si el grafo es
no dirigido.
No puede haber más de una arista en el mismo sentido entre el mismo par de
vértices si el grafo es dirigido.
En estas condiciones, el máximo número de aristas de un grafo dirigido de n
nodos en (n2-n); si el grafo es dirigido hay que dividir esta magnitud por dos.
Cuando el grafo tiene el máximo número de aristas se llama completo, si es
cercano se dice que es denso y cuando tiene del orden de n aristas o menos,
se dice que es disperso.
Los sucesores de un nodo x de un grafo dirigido son aquellos a los que llega
una arista procedente de x, mientras que los predecesores son aquellos de los
que sale (nos suelen interesar más los primeros). En el caso de los grafos no
dirigidos, desaparecen estos don conceptos, y son sustituidos por la noción más
general de adyacencia, así llamanos a dos nodos adyacentes cuando hay una
arista que los conecta.
Las operaciones que podemos definir son:





Crear un grafo vacío.
Insertar una arista en un grafo: se prohibe en la precondición que la arista sea
reflexiva y que la etiqueta tenga el valor que usamos como cota máxima.
Borrar una arista de un grafo.
Averiguar si una arista pertenece al grafo.
Obtener la etiqueta de una arista del grafo.
2.2. Implementaciones
Es una implementación muy parecida al caso de las relaciones, pero a su
vez presentamos dos versiones diferentes:
La primera representación es la conocida matriz bidimensional, que en el
caso de los grafos, toma el nombre de matriz de adyacencia. Si usamos las
32 · Estructura de la información
magnitudes n y a para medir el número de nodos y aristas respectivamente,
obtenemos lo siguiente:
 La complejidad espacial de la estructura es O(n2).
 La complejidad temporal de las operaciones es O(n2) para la creación, O(1)
para la inserción, supresión y consulta de aristas, O(n) para la obtención de
sucesores y precedesores (en el peor de los casos).
En la segunda representación, que va a ser encadenada, podríamos usar la
multilista, pero va a ser raro el caso que en un mismo programa nos interesa tratar
tanto los sucesores como los predecesores de un nodo; la mayoría de las veces nos
interesa movernos por el grafo y obtener los sucesores de los nodos, y por ello
solemos utilizar la representación por listas de adyacencia. Se dispone de un
vector indexado por los vértices en el que, para cada posición, cuelga la lista de
nodos sucesores, junto con la etiqueta que forma parte de la arista
correspondiente. El gráfico lateral muestra un grafo dirigido y su implementación
por listas de adyacencia. En esta implementación debemos anotar lo siguiente:





Se representan estas listas de adyacencia mediante un atributo de clase
ListaDeParesVerticeEtiqueta, haciéndola una codificación modular, simple y
resistente a modificaciones.
El invariante del grafo vuelve a reflejar la ausencia de aristas de un vértice a sí
mismo con una variante de la típica función cadena que se define usando
varias operaciones del TAD lista.
Se introduce la función auxiliar búsqueda, que retorna un booleano indicando si
un elemento dado está dentro de una lista o no y, en caso afirmativo, posiciona
el punto de interés, así evitamos algún recorrido redundante por la lista.
La complejidad espacial de la estructura es O(n+a). Normalmente será el
número de aristas pero si hay pocas, el espacio del vector se vuelve relevante.
La complejidad temporal de las operaciones es de O(n) para la creación, O(k)
para la inserción, supresión y consulta de aristas, O(k) también para el
recorrido de la lista de sucesores y O(n+a) para el recorrido de los
predecesores puesto que hay que recorrer todas las listas. Es decir, excepto la
creación y la obtención de sucesores, el coste temporal parece favorecer la
implementación por matriz; ahora bien, el buen comportamiento en la
obtención de los sucesores provoca que muchos de los algoritmos que veremos
funcionen mejor con una implementación por listas, al basarse en un recorrido
de todas las aristas del grafo que se pueden obtener en O(n+a) frente al coste
O(n2) con las matrices.
3. RECORRIDO DE GRAFOS
El recorrido de grafos que más nos interesa, dentro de todos los posibles
que podemos llevar a cabo, es el recorrido en ordenación topológica, aplicable
solo a grafos dirigidos (etiquetados o no) y que está regido por un principio muy
simple: un nodo del grafo se visita si, y sólo si, se han visitado todos su
predecesores. Esta regla no determina un único recorrido válido. Incluso algunas
veces tos interesa el recorrido del grafo en orden topológico inverso, y así se utiliza
como mecanismo de representación de expresiones aritméticas.
Centrándonos de nuevo en el recorrido en ordenación topológica lo que
queremos es implementar una función que nos retorne una lista con punto de
interés que contenga todos sus nodos en un orden que respete la regla que define
el recorrido. Así:


En la precondición se establece la necesidad de que el grafo sea acíclico
usando una función auxiliar que determina si existe un camino entre un par de
nodos. Si no se encuentra al mismo tiempo camino de v a w y de w a v,
tendremos un grafo acíclico.
En la poscondición se establece la condición de ordenación topológica.
Matriz de adyacencia
Estructura de la información · 33





Se eligen los vértices que no tienen predecesores, los que se pueden visitar y, a
medida que se incorporan a la solución, se dejan de considerar las aristas que
salen de éstos.
El invariante establece que, a cada paso del bucle, se dispone del recorrido
parcial de los nodos ya tratados. Esta implementación es costosa pues hay que
buscar repetidamente los vértices sin predecesores, por lo cual suele hacerse:
o Usar un vector de nodos que asocia a cada vértice el número de
predecesores que aún no están en la solución.
o Usa un conjunto ceros en el que se guardan todos los nodos que se
pueden incorporar en el siguiente paso del algoritmos
A su vez, se descubre que las dos subestructuras anteriores pueden fusionarse
en una sola, añadiendo un campo encadenamiento de forma que todos los
nodos que antes estuviesen en el conjunto ceros ahora se encadenen y se
organicen mediante una estructura lineal (la típica pila). Añadir un apuntador al
primer elemento de esta pila y un booleano que indique si está la pila vacía o
no e introducimos un contador de nodos para saber si se tienen que tratar
todos o no.
El coste temporal en la inicialización queda de O(n) en el primer bucle. El
segundo bucle exige un examen de todas las aristas del grafo, si se hace por
lista de adyacencia tendrá un coste de O(a+n), si es por matrices de
adyacencia será de O(n2). El bucle principal parece que tiene un coste de O(n2),
pues se ejecuta n veces y a cada paso de añade un nodo a la solución y en la
iteración se obtienen los sucesores del nodo elegido (O(n) en el peor de los
casos). Ahora bien, si observamos que la iteración interna exige el examen de
todas las aristas que componen el grafo con un tratamiento constante de cada
una y, esto es en realidad O(a+n) y no O(n2) cuando el grafo esté
implementado por listas de adyacencia.
Por ello, se puede concluir que la eficiencia temporal del grafo será de O(a+n)
con listas de adyacencia y O(n2) con matriz de adyacencia. Por eso la
representación por listas de adyacencia es preferible si el grafo es disperso,
mientras que si es denso la implementación no afecta a la eficiencia del
algoritmo.
4. ALGORITMOS DE CÁLCULO DE DISTANCIAS MÍNIMAS
Dado un grafo dirigido que puede ser una red de metro, nos surge la
frecuente necesidad de encontrar la distancia mínima entre dos nodos, entendiendo
por distancia la suma de las etiquetas que se encuentran en un camino de un
grafo. Existen dos algoritmos para ello, el de Dijkstra calcula la distancia mínima
de un nodo al resto de nodos del grafo y el de Floyd calcula la distancia mínima
entre todos los pares de nodos. Como en ningún caso el algoritmo de Dijkstra es
más lento que el Floyd utilizaremos el primero en esta asignatura.
Algoritmo de Djisktra
El algoritmo de Djisktra, por tanto, se ocupa de calcular el camino más
corto de un nodo al resto de nodos, y en su versión estándar más simple, retorna el
coste de este camino, no los nodos que lo integran. En el ejemplo de la tabla
lateral, el vector final es el resultado de la aplicación del algoritmo sobre el grafo
superior. En la especificación del algoritmo destacan:


El coste entre dos nodos no conectados es el valor sup de las etiquetas que
representa el mayor posible.
Para caminos de longitud 1 (es decir, un único nodo y ninguna arista) se
considera que su coste es igual a la etiqueta mínima inf. (en el ejemplo 0).
Respecto a la implementación del algoritmo cabe destacar que pertenece a
los llamados algoritmos voraces caracterizados porque la solución se va
construyendo de forma incremental. Esto significa que el bucle que forma el núcleo
del algoritmo irá calculando un camino mínimo definitivo en cada paso, de forma
que después de n-1 vueltas se tendrán calculadas todas las distancias mínimas.
34 · Estructura de la información
Para saber cuales son los nodos ya tratados, la versión preliminar introduce un
conjunto S auxiliar que los va registrando, cada vez que se añade un nuevo nodo a
este conjunto se estudia si los caminos que aún no son definitivos se pueden
acortar pasando por ese mismo nodo.
El invariante del bucle nos asegura que el vector contiene caminos mínimos
formados íntegramente por nodos de S. En la tabla lateral observamos la evolución
del algoritmo de Djisktra para el ejemplo que establecíamos en la página anterior.
Evolución del algoritmo
Para conocer el coste del algoritmo vamos a establecer 4 partes en el
mismo: inicialización, selección de mínimos, marcaje y recálculo de distancias
mínimas. Podemos estudiarlo además representado por matrices de adyacencia o
por representaciones encadenadas, como vimos en el punto anterior.




Por Matrices de adyacencia el coste del algoritmo queda:
Inicialización: O(n). El bucle de inicialización se ejecuta n veces y el coste de
sus instrucciones es constante.
Selección: O(n2): El bucle de selección se ejecuta tantas veces como elementos
quedan por tratar, la primera vez n-1, la segunda n-2 etcetera, lo que
determina el coste predicho.
Marcaje: La supresión del conjunto se ejecuta un total de n-2 veces con coste
constante cada vez, por tanto O(n).
Recálculo: Por el mismo razonamiento que en el apartado de selección, el coste
es O(n2).
En las
cuestiones:



representaciones
encadenadas
destacamos
las
siguientes
La operación consulta puede llegar a ser lineal sobre el número de nodos,
aunque existe una alternativa. En el recálculo es inútil la obtención de etiquetas
para nodos y que no sean sucesores de w, porque en este caso no hay atajo en
el camino mínimo de v hacia u que pase por w. Por ello, nos podemos ahorrar
esas consultas reformulando la parte correspondiente del algoritmo. Así el coste
del recálculo pasa a ser O(a+n), pudiendo llegar a O(n2) si el grafo es denso.
En la inicialización podemos también evitar la consulta de las etiquetas
desglosando el bucle en dos, cada uno con coste total O(n).
En la fase de selección el coste es independiente de la representación del grafo
y permanece O(n2), pero nos podemos preguntar si es posible reducirlo a
O(a+n) y eso lo vamos a llevar a cabo con la cola prioritaria en el próximo
punto.
Algoritmo de Dijkstra con cola prioritaria
Jerarquía
El paso de selección lo que hace es obtener el nodo no tratado con coste
mínimo en su camino provisional hacia v. El punto clave es la característica de ser
mínimo y recordemos que las colas prioritarias presentan entre sus operaciones
precisamente la obtención y supresión del mínimo. Eso sí, recordemos que la
actualización no es uno de los métodos de las colas prioritarias, por eso definimos
un nuevo TAD que podemos observar en la figura lateral que añade las
operaciones:



Saber si un nodo está en la cola o no (existe?).
Obtención del coste asociado a un nodo cualquiera (valor).
Modificación del coste de un nodo cualquiera (Modifica).
En la implementación del TAD lo que hacemos es añadir un vector indexado
por nodos de tal forma que cada posición apunte al nodo del montículo
correspondiente, con lo que las operaciones crea existe y valor toma el valor O(1) y
añade, borra y modifica O(log n); con lo que ninguna operación llega a ser lineal.
Estructura de la información · 35
En la versión definitiva del algoritmo constatamos:



La existencia de la cola A provoca la desaparición del conjunto T para no
mantener información redundante: un elemento w ya se ha tratado si
A.consulta(w)=sup.
Desaparece el contador porque ahora sabemos que el proceso acaba cuando la
cola está vacía.
El camino de v a sí mismo al acabar la ejecución es igual al coste del ciclo más
corto que sale y vuelve a v y, por eso se pone explícitamente en el valor
mínimo justo al final; así su valor no interfiere en el funcionamiento de la
función.
La eficiencia temporal por tanto queda:




Inicialización: O(n log n) A causa de la inserción reiterada de elementos en la
cola, estando cada inserción logarítmica sobre el número de elementos que
hay.
Selección: O(n): porque cada obtención del mínimo es constante y hay n
obtenciones.
Marcaje: O(n log n): Porque cada supresión del mínimo es logarítmica y hay n.
Recálculo: O(a log n) El bucle interno examina todas las aristas del grafo a lo
largo del logaritmo y, en el peor de los casos, efectúa una sustitución por
arista, de coste O(log n).
El coste temporal definitivo es O(a+n) log n), mejor que la versión con matrices
de adyacencia cuando el grafo es disperso. Sin embargo, si el grafo es denso, el
algoritmo original es más eficiente. Eso sí, el espacio no asintótico es mucho mayor
debido a la nueva estructura de datos.
5. ALGORITMOS DE CÁLCULO DE ÁRBOLES DE EXPANSIÓN MÍNIMOS
El algoritmo del apartado anterior nos permite encontrar la conexión de
coste mínimo entre dos vértices individuales de un grafo etiquetado. Sin embargo,
en otras ocasiones nos interesa obtener un nuevo grafo con las aristas
imprescindibles para una optimización global de las conexiones entre todos los
nodos (ver el ejemplo de la tabla lateral).
Un árbol de expansión mínimo se caracteriza por:



La conectividad asegura que hay un camino entre todo par de vértices.
La aciclicidad garantiza que no hay aristas innecesarias, de hecho si hay n
nodos, deben haber n-1 aristas. Si se introduce una arista más se introduce un
ciclo, mientras que si se borra una, no todos los vértices estarán conectados.
Cualquier par de vértices estará unido por un único camino simple.
Para encontrar este árbol de expansión mínimo en cualquier grafo, haremos
uso del Algoritmo de Prim, que es un algoritmo voraz que aplica reiteradamente
la propiedad de los árboles de expansión mínimos, de forma que va incorporando
en cada bucle una arista a la solución. Su funcionamiento se explica en dos pasos:
1. Se introduce un conjunto U de vértices tratados (la primera vez se almacena un
vértice cualquiera) y se selecciona la arista mínima que une un vértice de U y
uno de su complementario, se incorpora esta arista a la solución y se añade su
vértice no tratado dentro del conjunto de vértices tratados.
2. El invariante nos asegura que realmente el resultado parcial siempre es un
árbol de expansión mínimo. Cuando acaba el algoritmo, el subgrafo es igual al
grafo entero.
36 · Estructura de la información
Evolución del cálculo de un árbol de expansión mínimo
En el algoritmo destacamos la introducción de un vector D indexado por
nodos que, para cada nodo que aún no forma parte del grafo resultante, almacena
la etiqueta mínima de las aristas que lo unen con los nodos tratados. El cálculo de
la eficiencia temporal queda como sigue:



En la Inicialización tenemos O(n) en el caso de la matriz y O(n2) en el caso de
multilistas. Podemos, como en el algoritmo de Dijkstra evitar el uso de la
consulta de forma similar, y reducimos en el caso de la multilista a O(n) pero
no nos va a afectar al coste global del algoritmo.
En el bucle principal el añadido de una arista será constante usando una matriz
y O(n) usando listas. El bucle de selección es O(n) ya que examina todas las
posiciones del vector y como debe ejecutarse n-1 veces, su coste total será de
O(n2). El bucle de reorganización depende de la representación del grafo: el
coste de los adyacentes es O(n) y el coste total queda O(n2) con matriz de
adyacencia, mientras que con multilistas queda O(a+n).
El coste asintótico total es de O(n2) independientemente de la representación,
mientras que el coste espacial es O(n).
El Algoritmo de Prim con cola prioritaria (ver ejemplo en la figura lateral)
es una mejora que se obtiene poniendo en juego las mismas ideas que usábamos
en el algoritmo de Dijkstra y que particularmente en la organización de esta cola
debemos considerar los siguientes aspectos:



Los elementos de la cola son tuplas de 3 componentes que representan aristas:
un par de nodos y la etiqueta de conexión.
Se consulta por nodo no tratado y el resultado de la consulta es la etiqueta de
la arista. Si el nodo consultado no existe, la etiqueta devuelta es sup.
El invariante debe adaptarse para tener en cuenta la existencia de la cola.
El razonamiento sobre la eficiencia del algoritmo de Prim modificado con
cola prioritaria son idénticos a los que usábamos con el algoritmo de Dijkstra y se
obtiene O((a+n) log n) que dado que el grafo inicial es conexo y entonces a>=n-1
nos queda O(a log n). Tendremos en cuenta que:



En el caso de representación por matriz de adyacencia su creación es O(n2) y la
eficacia resultante queda O(n2 +a log n)
En la representación por listas, en el peor de los casos nos queda O(n2).
Si el contexto nos permite elegir el tipo de representación del algoritmo de Prim
modificado, nos decantaremos por listas de adyacencia.
Evolución de un árbol de
expansión mínima con cola
prioritaria
Estructura de la información · 37
TEMA 5 DISEÑO DE ESTRUCTURAS DE DATOS
Para el diseño de nuevos TAD se propone una metodología en cuatro
etapas:
1. Identificación y discusión de los puntos clave del enunciado, haciendo un
análisis que permita identificar las partes relevantes desde el punto de vista del
diseño. Nos fijaremos especialmente en la funcionalidad del TAD, los datos que
intervienen (volúmenes, valores permitidos) y en los requerimientos de
eficiencia (tiempo de las operaciones, espacio ocupado). El resultado es una
lista de los puntos clave acompañados de algunas consecuencias que se
derivan de ello.
2. Decisiones de diseño: Estas decisiones condicionan la estructura de datos
como consecuencia de los puntos clave anteriores. Es importante que se
documente qué puntos clave justifican cada decisión y que se revise si cada
decisión nueva invalida alguna previa. En esta etapa existe un peligro que hay
que evitar: una decisión de diseño puede influir en otras que se hayan tomado
previamente, y hay que asegurarse de que esta interacción no sea perjudicial e
invalide parte del diseño obtenido hasta el momento. No existe ninguna receta
mágica que nos permita agrupar u ordenar los puntos clave de forma que este
peligro desaparezca.
3. Estructura de datos resultante: Una vez que se dispone ya del diseño de la
estructura, hay que plasmarla y éste es el objetivo del tercer paso. Hará falta
decidir también como se interrelacionan las diferentes subestructuras. Mientras
sea posible, se reutilizarán TADs ya existentes. El resultado se plasmará en una
descripción gráfica, la representación del tipo y su invariante.
4. Descripción de las operaciones y cálculo de eficiencia: Se hará una
explicación en lenguaje natural de la forma como se tiene que implementar
cada operación. Si se considera más ilustrativo se puede describir alguna
implementación con pseudocódigo. En cualquier caso, de la descripción se tiene
que concluir su eficiencia. Se trata de comprobar si el diseño obtenido es
correcto, más que de dar la implementación de las operaciones.
5. Implementación completa de la estructura de datos resultante: hay que
codificar hasta el último detalle, tanto los atributos como las operaciones
usando un lenguaje de programación. Esta última etapa no tiene importancia
ninguna en el proceso de creación de la solución.
Texto elaborado a partir de:
Estructura de la información
Xavier Franch Gutiérrez, Fatos Xhafa, Xavier Burgués i Illa
Febrero 2003