PDF de programación - Capítulo 11. Aplicaciones de tipos abstractos de datos

Capítulo 11
Aplicaciones de tipos abstractos de
datos1

Resumen: En este tema se estudia la resolución de problemas mediante el uso de
distintos tipos de datos. Para ello se proponen varios ejercicios resueltos así como
problemas a realizar por el alumno.

1. Problemas resueltos:

1.1. Confederación hidrográfica.

(Obtenido del examen final de Junio de 2010. Titulacíon: ITIS. Asignatura: EDI. Gru-

pos A y B)

Una confederación hidrográfica gestiona el agua de ríos y pantanos de una cuenca
hidrográfica. Para ello debe conocer los ríos y pantanos de su cuenca, el agua embalsada
en la cuenca y en cada pantano. También se permite trasvasar agua entre pantanos del
mismo río o de distintos ríos dentro de su cuenca.

Se pide diseñar un TAD que permita a la confederación hidrográfica gestionar la cuenca.
En particular, el comportamiento de las operaciones que debe ofrecer debe ser el siguiente:

crea, crea una confederación hidrográfica vacía.

an_rio(r) añade el río r a la confederación hidrográfica. En una confederación no
puede haber dos ríos con el mismo nombre.

an_pantano(r, p, n1, n2) crea un pantano de capacidad n1 en el río r de la
confederación. Además lo carga con n2 Hm3 de agua (si n2 >n1 lo llena). Si ya
existe algún pantano de nombre p en el río r o no existe el río la operación se ignora.

embalsar(r, p, n) carga n Hm3 de agua en el pantano p del río r de la confe-
deración. Si no cabe todo el agua el pantano se llena. Si el río o el pantano no están
dados de alta en la confederación la operación se ignora.

embalsado_pantano(r, p) devuelve la cantidad de agua embalsada en el pan-
tano p del río r. Si el pantano no existe o no existe el rio devolverá el valor 1.

1Isabel Pita Andreu es la autora principal de este tema.

279

280

Capítulo 11. Aplicaciones de tipos abstractos de datos

reserva_cuenca(r) devuelve la cantidad de agua embalsada en la cuenca del río
r.

transvase(r1, p1, r2, p2, n) transvasa n Hm3 de agua del pantano p1 del
río r1 al pantano p2 del río r2, en la confederación. Si n es mayor que la cantidad
de agua embalsada en p1 o no cabe en p2 la operación se ignora.

Todas las operaciones son totales. Se puede suponer definidos los tipos Rio y Pantano.

Solución

Representación:
Se propone utilizar una tabla con clave la información asociada a los ríos y valor todos
los pantanos existentes en el río con su capacidad y litros embalsados. Los pantanos del
río se almacenan en otra tabla, con clave la identificación del pantano y valor su capacidad
y litros embalsados. Se utilizan tablas porque las operaciones que se van a realizar tanto
sobre ríos como sobre pantanos son consultas e inserciones.

La implementación de la clase es la siguiente. El tipo Rio representa la información de
los ríos (para este ejercicio es suficiente con que esta información sea el nombre del río) y
el tipo P antano representa la información de los pantanos (es suficiente con el nombre del
pantano).
class Conf_hidrografica {

public:

Conf_hidrografica();
~Conf_hidrografica();
void an_rio (const Rio& r);
void an_pantano (const Rio& r, const Pantano& p, int n1, int n2);
void embalsar (const Rio& r, const Pantano& p, int n);
int embalsado_pantano(const Rio& r, const Pantano& p) const;
int reserva_cuenca(const Rio& r) const;
void transvase(const Rio& r1, const Pantano& p1, const Rio& r2,

const Pantano& p2,int n);

private:

struct info_pantano {

int capacidad;
int litros_embalsados;

};
HashMap<Rio,HashMap<Pantano,info_pantano> > t_rios;

};

Implementación de las operaciones.

Operación conf-hidrografica, constructor.
El constructor implícito es suficiente para inicializar la tabla de ríos y pantanos, y tiene
coste constante, ya que las tablas que se han estudiado, se crean con un tamaño inicial
independiente del número de elementos de la tabla.

Operación an_rio.
Al añadir un río, si está en la cuenca no se debe modificar su valor, por lo tanto no se
debe llamar a la operación insert ya que esta modifica el valor. La tabla correspondiente
al valor del río se crea vacía.

Estructura de Datos y Algoritmos

1. Problemas resueltos:

281

void Conf_hidrografica::an_rio (const Rio& r){

// S i
if (!t_rios.contains(r))

r i o esta ,

e l

e l

v a l o r a s o c i a d o no debe cambiar

{t_rios[r] = HashMap<Pantano,info_pantano>();}

}

Coste de la operación implementada:

El coste de consultar una tabla es constante (operación contains).

El coste de crear una tabla vacía es constante.

El coste de insertar un elemento en la tabla es constante (operación []).

Por lo tanto, el coste de la operación es constante.

Operación an_pantano.
La operación que añade un pantano a un río, si el río está en la confederación, y si el
pantano no está en el río lo añade con la capacidad y litros embalsados que se indican.
Si los litros embalsados son mayores que la capacidad se embalsa la capacidad total del
pantano. Si el río no está en la confederación, o si el pantano ya está en el río la operación
no tiene ningún efecto.
void Conf_hidrografica::an_pantano (const Rio& r, const Pantano& p,

if (t_rios.contains(r) && !t_rios[r].contains(p)) {

int n1, int n2){

// c r e a l a i n f o r m a c i o n d e l pantano
info_pantano i;
i.capacidad = n1;
if (n2 < n1) i.litros_embalsados = n2;
else i.litros_embalsados = n1;
// añade i n f o r m a c i o n a l
t_rios[r][p]=i;

r i o

}

}

Coste de la operación implementada:

El coste de consultar una tabla es constante (operaciones contains y []).

El coste de insertar un elemento en una tabla es constante (operación []).

El resto de operaciones tiene coste constante.

Por lo tanto, el coste de la operación es constante.

Operación embalsar.
La operación de embalsar añade n Hm3 al agua embalsada en un pantano. Si se supera

la capacidad, el pantano se considera lleno.
void Conf_hidrografica::embalsar (const Rio& r, const Pantano& p,

if (t_rios.contains(r) && t_rios[r].contains(p)) {

// Añade a l pantano
t_rios[r][p].litros_embalsados += n;
if (t_rios[r][p].litros_embalsados > t_rios[r][p].capacidad)

int n){

Facultad de Informática - UCM

Capítulo 11. Aplicaciones de tipos abstractos de datos

t_rios[r][p].litros_embalsados = t_rios[r][p].capacidad;

282

}

}

Coste de la operación implementada es igual que el coste de la operación an_pantano.

Operación embalsado_pantano.
La operación consulta los Hm3 embalsados en un pantano.

int Conf_hidrografica::embalsado_pantano(const Rio& r,

const Pantano& p) const{

int n = -1;
if (t_rios.contains(r) && t_rios[r].contains(p)) {

n=t_rios[r][p].litros_embalsados;
}

return n;

}

El coste de la operación viene dado por el coste de consultar la información de un

pantano en un río y por lo tanto es constante.

Operación reserva-cuenca.
La operación reserva-cuenca obtiene la suma de los Hm3 embalsados en todos los

pantanos de la cuenca.

Para implementarla se utiliza un iterador sobre la tabla que recorre todos los pantanos

del río.
int Conf_hidrografica::reserva_cuenca(const Rio& r) const {
int n = 0;
if (t_rios.contains(r)) {
HashMap<Pantano,info_pantano>::ConstIterator it=t_rios[r].cbegin();
while (it != t_rios[r].cend()) {

info_pantano i = it.value();
n += i.litros_embalsados;
it.next();

}// w h i l e
}// i f
return n;

}

Coste de la operación implementada:

El coste de consultar una tabla es constante (operaciones contains y []).

El coste de crear un iterador es constante.

El coste del bucle es lineal respecto al número de elementos de la tabla que almacena
los pantanos de un río, ya que las operaciones que se realizan en cada vuelta del bucle
tienen coste constante y el número de veces que se ejecuta el bucle coincide con el
número de elementos de la tabla.

Por lo tanto el coste de la operación es lineal respecto al número de pantanos en un río.

Operación transvase.

Estructura de Datos y Algoritmos

1. Problemas resueltos:

283

La operación realiza el transvase de un pantano a otro de n Hm3 de agua. Si no hay
suficiente agua embalsada en el pantano de origen, o si el agua a trasvasar no cabe en el
pantano de destino la operación se ignora.
void Conf_hidrografica::

transvase(const Rio& r1, const Pantano& p1,

const Rio& r2, const Pantano& p2,int n){
if (t_rios.contains(r1) && t_rios.contains(r2) &&

t_rios[r1].contains(p1) && t_rios[r2].contains(p2) &&
t_rios[r1][p1].litros_embalsados >= n &&
t_rios[r2][p2].litros_embalsados + n <= t_rios[r2][p2].capacidad) {

t_rios[r1][p1].litros_embalsados -= n;
t_rios[r2][p2].litros_embalsados += n;

}

}

El coste de la operación es constante ya que las operaciones que se realizan son las de

consultar e insertar en una tabla (coste constante).

1.2. Motor de búsqueda.

Se desea crear un motor de búsqueda para documentos de texto, de forma que, tras
indexar muchos documentos, sea posible solicitar todos aquellos que contengan todas pa-
labras de una búsqueda (por ejemplo, “elecciones rector ucm”). Implementa las siguientes
operaciones en un TAD Buscador:

crea: crea un buscador vacío, sin documentos.

indexa(d): indexa el documento d, que contendría solamente texto, de forma que
resulte buscable si la consulta contiene palabras de ese texto; y devuelve un identifi-
cador para ese documento, que se usará en los resultados.

busca(t): devuelve una lista con todos los identificadores de documentos que contienen
los términos que aparecen en t, una frase.

consulta(i): muestra el documento al que se le ha asignado el identificador i.

Se pide:

a) Obtener una representación eficiente del tipo utilizando estructuras de datos conoci-

das.

b) Implementar todas las operaciones indicando el coste de cada una de ellas. La ope-
ración busca(), en particular, debe ser lo más eficiente posible, incluso si el número
de documentos es muy elevado.

Solución.

Representación:
Una primera aproximación podría, para cada documento, almacenar en un diccionario
las palabras que aparecen en él. De esta forma podríamos ver si contiene todas las palabras
de una consulta con t palabras en O(t) operaciones. No obstante, el coste de busc