Estructuras de Datos y Algoritmos. Curso 2004/05 …users.dsic.upv.es/~nprieto/clases/EDA0506/T4/traspas4.pdf · Estructuras de Datos y Algoritmos. Curso 2004/05 Tema 4. ... Como

Estructuras de Datos y Algoritmos. Curso 2004/05

Tema 4. Modelos y Estructuras de Datos

Mabel Galiano Natividad Prieto

Departamento de Sistemas Informaticos y ComputacionEscuela Tecnica Superior de Informatica Aplicada

Indice

1. Estructuras de Datos: Modelo o Especificacion e Implementacion 31.1. Diseno de una Estructura de Datos (EDA) en Java . . . . . . . . . . . . . . . . 41.2. Librerıas de Usuario Java para el manejo de EDAs . . . . . . . . . . . . . . . . . 61.3. Aplicacion ejemplo: Simulacion de un Banco de Modems en Java . . . . . . . . . 7

2. Modelos Lineales y sus Aplicaciones 92.1. Lista Con Punto de Interes . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 92.2. Pila . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 132.3. Cola . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 18

3. Modelos Avanzados y sus Aplicaciones 213.1. Cola de Prioridad . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 213.2. Diccionario . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 22

Objetivos y Bibliografıa

El objetivo general de este tema es presentar las Estructuras de Datos mas utilizados enComputacion, clasificandolas en base a los modelos mas o menos avanzados que definen; desdelos mas sencillos Lineales como Lista con Punto de Interes, Pila y Cola, hasta los mas sofisti-cadas Cola de Prioridad y Diccionario, que se definen para resolver problemas de Busqueda ySeleccion de forma muy eficiente. En particular, se definira una Estructura de Datos (EDA)como una organizacion concreta de una Coleccion de Datos cuyo comportamiento debe ser es-pecificado de forma independiente a la implementacion que la haga operativa en un entornoinformatico. Para ello, en su diseno en Java se especificaran y enriqueceran mediante clasesinterface, que deben ser implementadas por jerarquıas de clases. Esta forma de diseno deuna EDA permitira subrayar una vez mas las ventajas que proporciona la Programacion Orien-tada a Objetos: Reutilizacion y Portabilidad del Software via Genericidad y Ocultacion de laInformacion.

Finalmente se mostrara como usar una Especificacion de una EDA planteando aplicacionesconocidas de mediana complejidad; sera en temas sucesivo cuando se detallara sus posibles

1

INDICE

implementaciones, contiguas o enlazadas, discutiendo en base a criterios de eficiencia cual es lamas adecuada.

Como bibliografıa basica se utilizara el capıtulo 6 del libro de Weiss M.A. ”Estructurasde datos en Java”. Adisson-Wesley, 2000.

Como bibliografıa adicional se recomiendan los siguientes textos:

Wiener, R., Pinson, L.J. ”Fundamentals of OOP and Data Structures in Java”.Cambridge University Press. 2000. Capıtulos del 9 al 14.

Sahni, S. ”Data Structures, Algorithms and Aplications in Java”. McGraw-HillHigher Education, 2000. Capıtulos del 9 al 16.

2

1. Estructuras de Datos: Modelo o Especificacion e Implementacion

1. Estructuras de Datos: Modelo o Especificacion e Imple-mentacion

Cualquier aplicacion informatica exige manipular Colecciones de Datos de talla elevada;basicamente se debe poder insertar, borrar o recuperar un Dato de la Coleccion, Buscar o Se-leccionar aquel que satisfaga una propiedad relevante para la aplicacion o Recorrer la Colecciontratando todos sus Datos de una cierta manera. Para ello resulta imprescindible realizar una es-tructuracion de la Coleccion y sus Datos, que no solo posibilite su manipulacion eficaz sino quetambien, mas importante aun, permita su Reutilizacion en otras aplicaciones. Especıficamente,

se denomina Estructura de Datos (EDA) al conjunto de operaciones que definen elcomportamiento o funcionalidad de una Coleccion, esto es que se puede hacer con susDatos, y a su (-s) posible (-s) representacion (-es) en memoria, contigua o enlazada,que determinara la implementacion de las operaciones que definen su comportamiento.

En base a la definicion de EDA realizada, es comun utilizar el termino Modelo o Espe-cificacion para referirse a la descripcion, mas o menos formal, del conjunto de operacionesque definen su funcionalidad (comportamiento o semantica), independientemente de como serepresente. Asimismo, el termino Implementacion se emplea para significar conjuntamentela Representacion de una EDA y la implementacion de su Especificacion, a la que dicha Re-presentacion obliga. Como se comentara en breve, el principio de Reutilizacion del Softwareconduce a separar en tipos de clases diferentes un Modelo y sus diferentes Implementaciones, loque obliga a una programacion lo mas generica y abstracta (con Ocultacion de la Informacion)posible.

Cada aplicacion exige un Modelo determinado, cuya eficacia vendra dada por la Implementa-cion mas o menos ajustada que se pueda realizar de el; si se dispone de varias Implementacionessera la eficiencia el criterio que servira para elegir cual de ellas utilizar. Ası, si en la aplicacionse gestiona una Coleccion en base unica y exclusivamente al orden en el que se han ido incor-porando sus Datos, por ejemplo siguiendo un criterio LIFO (Last In First Out) o FIFO (FirstIn First Out) o de Acceso Secuencial, un Modelo Lineal de, respectivamente, Pila o Colao Lista Con Punto de Interes puede caracterizar perfectamente cual es el siguiente Dato atratar; notese que este tipo de gestion obliga a que la Busqueda o Seleccion de aquellos Datosque cumplan una determinada propiedad relevante para la aplicacion solo se pueda realizar, engeneral, con coste lineal con la talla de la Coleccion. Este hecho obliga a proponer modelos masavanzados que el Lineal como pueden ser Diccionario o Cola de Prioridad, cuyas Imple-mentaciones mas eficientes se realizan con Representaciones mas sofisticadas como los Arboleso las Tablas de Dispersion.

Con el ejemplo que se enuncia a continuacion se pretenden poner de manifiesto de maneraintuitiva todos los conceptos introducidos hasta el momento, reservando para secciones poste-riores los detalles de su transcripcion a Java: sea una aplicacion de gestion de una Coleccion deTrabajos -los ficheros a imprimir tras una sesion de trabajo, las tareas de un Sistema Operativo(SO), las entradas de cine a vender por taquilla, los pacientes que deben de ser visitados en unaconsulta medica, etc. Se puede definir un Gestor que la modele, esto es que decida en cada mo-mento cual es el siguiente Trabajo a tratar, lo trate y lo marque como tratado -que indique cuales el siguiente fichero a imprimir, que venda una entrada al siguiente comprador, que determineel siguiente paciente a visitar, etc.; ası hasta que no queden mas trabajos a tratar. Para ello, se

M.Galiano,N.Prieto 3


requiere no solo una Representacion adecuada de la Coleccion de Trabajos a gestionar, sino loque es mas importante aun, la funcionalidad mınima que describen las siguientes operaciones:

insertar(Trabajo t), que incorpora un nuevo Trabajo a la Coleccion;

recuperar(), que obtiene el Trabajo a gestionar en cada momento;

borrar(), que elimina de la Coleccion un Trabajo ya gestionado.

Esta descripcion o Especificacion sugiere que, si todos los Trabajos tienen la misma priori-dad, la gestion de la Coleccion de los Trabajos se realiza de forma FIFO: insertar(Trabajot) en realidad es encolar(Trabajo t), recuperar() equivale a obtener el primero() de losTrabajos a gestionar y borrar() es desencolar(); en otras palabras,

¡el Gestor es una Cola!

Notese que una definicion generica del Gestor permitira su reutilizacion en tantas aplicacio-nes de gestion como tipos de Trabajo se planteen; cuando se desee gestionar la cola del cine o lade la impresora, se debera disponer de un nuevo Gestor especıfico que extendera o tendra comoatributo una Cola Generica de, respectivamente, Compradores o Ficheros a imprimir.

Un ejemplo que resulta de interes en este momento se deriva del que se acaba de presentarsimplemente dotando de una Prioridad a los Trabajos a gestionar; entonces, el siguiente Trabajoa atender siempre es el que tiene mayor Prioridad, como en las urgencias de un hospital o enun SO eficaz o en una cola de impresion en la que los trabajos que consumen menos tiempose imprimen antes para optimizar tiempos de espera. En este caso, el modelo de Cola que seha definido ya no es valido, pues no tiene en cuenta esta caracterıstica de la aplicacion, lo queobliga tratar en el mınimo tiempo posible el Trabajo mas prioritario. Por tanto,

insertar(Object t) debe incorporar un nuevo Trabajo a la Coleccion atendiendo a suPrioridad, ordenadamente;

recuperar() debe obtener como Trabajo a gestionar en cada momento el mas prioritariode los de la Coleccion; por ello, en adelante se le denominara buscarMin();

borrar() debe eliminar de la Coleccion un Trabajo ya gestionado, i.e. el que era el masprioritario; por ello, en adelante se le denominara elimarMin().

Como se detallara mas adelante, las tres operaciones descritas caracterizan al Modelo de-nominado Cola de Prioridad, que se comporta como una simple Cola cuando algunos de losTrabajos tienen la misma Prioridad.

1.1. Diseno de una Estructura de Datos (EDA) en Java

Como ya se ha indicado una EDA consta de una Especificacion y una Implementacion, laprimera independiente de la segunda. Si a la hora de disenar en Java una EDA se desea manteneresta independencia y, al mismo tiempo, favorecer la Reutilizacion de las Implementacionesrealizadas, se definiran ambas componentes en distintos tipos de clases, una interface y lajerarquıa que lo implementa.

4


Especificacion de una EDA en Java

El tipo de clase Java que permite describir en todos sus extremos el concepto de Especifi-cacion de una EDA es el interface; en efecto, como todos sus metodos son abstractos y noestan permitidos en el atributos no estaticos ni metodos constructores, asegura la independenciacompleta de la Implementacion que del interface se realice. Ademas, una ventaja adicionaldel interface es que es la herramienta para la Herencia Multiple en Java: mientras que unaclase solo puede extender a otra, puede implementar todas las interfaces que sea necesario. Porejemplo, las Especificaciones Java de las EDA Cola y Cola de Prioridad serıan las siguientesclases interface:

public interface Cola {void encolar(Object x);Object desencolar();Object primero();boolean esVacia();

}public interface ColaPrioridad {

void insertar(Object x);Object eliminarMin();Object buscarMin();boolean esVacia();

}

Cuestion: ¿Es posible que uno de los metodos de un interfaz sea toString()?. Razonese larespuesta.

Implementacion de una EDA en Java

Como ya se ha indicado la implementacion de una EDA en Java se realiza eligiendo primerola Representacion (contigua o enlazada) de la Coleccion de Datos, esto es los atributos de laClase que implementa al interface; despues, en base a estos, se implementaran los metodosque lo componen. En ocasiones, ademas de los metodos del interface, la clase (o jerarquıa) quelo implementa anade nuevos metodos, como por ejemplo toString, o metodos auxiliares quese declaran privados. Por ejemplo, la clase ArrayCola implementa el interfaz Cola utilizandoun array como soporte para los Datos de la Coleccion:

public class ArrayCola implements Cola {private Object elArray[];private int fin, primero, tallaActual;private static final int CAPACIDAD_POR_DEFECTO = ...;

public ArrayCola() { ... }public String toString() { ... }....private void duplicarVector() { ...}....public void encolar(Object x) { ... }public Object desencolar () { ... }public Object primero () { ... }public boolean esVacia () { ... }

}


1.

En general, los metodos que se definen en un interfaz representan las operaciones basicas demanejo de la Coleccion, tıpicamente insertar, borrar y recuperar. Por lo tanto, puede ocurrir quetras haber disenado el interface surja la necesidad de enriquecerlo o ampliar su funcionalidad,para lo que se puede definir una clase que lo extiende o subinterface; volviendo al ejemplo deCola, si se desea disponer de una operacion de inversion, que no es basica, se debera enriquecerel Modelo definiendo el correspondiente subinterface como sigue:

interface ColaEnriquecida extends Cola {void invertir ();

}

Notese que ColaEnriquecida por una parte hereda todos los metodos de Cola y por otrano puede implementar ninguno, pues es un interfaz. Por tanto, como ArrayCola ya implementaa Cola, la clase que implementa a ColaEnriquecida se puede definir como sigue:

public class ArrayColaEnriquecida extends ArrayCola implements ColaEnriquecida{public ArrayColaEnriquecida () { ... }public void invertir () { ... }

}

Notese que ArrayColaEnriquecida utiliza la implementacion de ArrayCola sin necesidadde volver a definirla, pues extends ArrayCola; como ademas implements ColaEnriquecida,invertir se puede definir en terminos de los metodos del interface sin acceder a su Imple-mentacion. Ası una ColaEnriquecida ES UNA Cola que ademas se puede invertir.

1.2. Librerıas de Usuario Java para el manejo de EDAs

Aunque otras organizaciones son viables, en la asignatura EDA se propone que los Mode-los y las jerarquıas de clases que los implementan se ubiquen en librerıas del nuevo proyectoestructurasDeDatos del directorio libJava. Especıficamente,

el paquete modelos contendra todas las Especificaciones de EDAs que se realicen en estetema: interface Pila, Cola, ListaConPI, ColaPrioridad y Diccionario;

el paquete lineales contendra las jerarquıas de clases que implementan los interface

Lineales mediante una Representacion enlazada o contigua;

el paquete arboles contendra aquellas clases que implementan Modelos en base a Arbo-les: Montıculos y Arboles Binarios de Busqueda (ABB); en particular, las Implemen-taciones de ColaPrioridad mediante un Montıculo y un ABB y la Implementacion deDiccionario mediante un ABB;

el paquete hashing contendra las clases que implementan Diccionario mediante dife-rentes tipos de Tablas de Dispersion;

el paquete grafos contendra las clases que permiten implementar y manipular los distintostipos de grafos que se estudien.

En cuanto a las Excepciones de Usuario lanzadas por los Modelos o sus Implementaciones seubicaran siempre en el paquete ya existente excepciones, del proyecto excepcionesDeUsuario

de libJava. A modo de resumen grafico, la siguiente figura muestra la propuesta realizada:

6

1.

$HOME

excepcionesDeUsuario

modelos

ListaConPI.java

Pila.java

Cola.java

ColaPrioridad.java

Diccionario.java

eda

progJava libJava

util estructurasDeDatos

PilaArray.java

ColaArray.java

LEIOrdenada.java

NodoBinario.java

Monticulo.java

lineales jerarquicos ...

LEI.java

LEIConPI.java

NodoLista.java

ArbolBinarioBusqueda.java

ABBDiccionario.java

ABBColaPrioridad.java

Finalmente se debe destacar que algunos de los Modelos que se estudiaran en este tema,ası como las clases que los implementan que se estudiaran en temas posteriores, coincidenparcialmente con los que proporciona el lenguaje Java en su librerıa java.util. No obstante,se ha preferido reproducirlas en Castellano para facilitar la comprension de las definiciones,lo que presenta el inconveniente de hacerlas sintacticamente incompatibles con (insubstituıblespor) las correspondientes de java.util.

1.3. Aplicacion ejemplo: Simulacion de un Banco de Modems en Java

En cualquier aplicacion de Simulacion se emula el funcionamiento de un cierto sistemareal con el fin de obtener una serie de estadısticas sobre el; del analisis de estas se extraeranlas condiciones y requisitos imprescindibles que el sistema real debiera satisfacer para que sufuncionamiento resulte optimo.

Si el sistema real a emular se puede describir en terminos de los distintos Eventos (o sucesos)originados por su funcionamiento, la aplicacion de Simulacion consiste, basicamente, en gestio-nar una Coleccion de Eventos de la forma mas adecuada posible; en particular, retomando elejemplo del Gestor de Trabajos ya presentado y suponiendo que,

un Trabajo es un Evento que se incorpora a la Coleccion en base al instante en el que seproduce u origina, lo que marca su Prioridad frente a otros Eventos;

el Gestor es un Simulador que procesa los Eventos conforme estos se producen, i.e. realizauna Simulacion Dirigida por Eventos en la que solo hay simulacion si hay Evento,

se puede concluir que el Gestor o Simulador debe contar entre sus atributos con una Cola dePrioridad de Eventos, i.e. TIENE UNA ColaPrioridad.

Un problema concreto de Simulacion Dirigida por Eventos es el que se enuncia a continua-cion: el Centro de Calculo de la UPV dispone de un Banco de Modems, i.e. de un numero dado


1.

de modems, a los que se accede vıa telefonica: si al realizar una peticion de conexion al sistematodos los modems del Banco estan ocupados, el telefono da la senal de ocupado; sino, si algunmodem del Banco esta disponible, se efectua la conexion demandada y se inicia una sesion detrabajo cuya conclusion, tras un cierto tiempo de conexion, permitira liberar el modem. Caraa optimizar el comportamiento de este Banco de Modems, se quiere realizar una Simulacionque obtenga una serie de estadısticas, como el porcentaje de peticiones de conexion atendidas yrechazadas en un determinado intervalo horario, la carga media del sistema, el numero mınimode modems para conseguir un servicio razonable, etc. Para ello, en primer lugar es necesarioestablecer que Eventos son los que gestiona la Cola de Prioridad del Simulador; como es facildeducir, el funcionamiento del Banco se caracteriza por dos tipos de Eventos: MARCAR, querepresenta una nueva peticion de conexion a un modem del banco y COLGAR, que representael final de la correspondiente conexion y, por tanto, la liberacion del modem que se ocupo alMARCAR y la actualizacion de los valores estadısticos que se esten calculando. Ademas de untipo, un Evento se puede caracterizar por los siguientes atributos (TIENE UN): un identifica-dor que, por ejemplo, puede representar el numero de peticion de conexion que lo ha originadoy que, por tanto, se establece en el momento que se origina el Evento (al MARCAR) y semantiene hasta que la peticion bien es rechazada o bien, tras ser atendida, finaliza (al COL-GAR); un tiempo que representa el instante en el que se origina el Evento y que, por tanto,determina su Prioridad a la hora de ser gestionado.

En base a la descripcion realizada resulta facil deducir que los atributos que caracterizanal Simulador son: el numero de modems libres en cada paso de Simulacion, que al iniciarseesta coincide con el numero de modems del Banco; las distribuciones de probabilidad quegobiernan, respectivamente, el tiempo en el que se origina un Evento de tipo MARCAR y suduracion, esto es el tiempo de conexion otorgado a una peticion cuando hay modems libres;notese que como un MARCAR se puede originar en cualquier instante de la Simulacion, ladistribucion que los gobierna puede ser sin perdida de generalidad una distribucion uniforme;sin embargo la que gobierna la duracion de una conexion sera una distribucion, por ejemploGaussiana, centrada en un cierto valor medio igual al tiempo medio de conexion. En conse-cuencia, como el tiempo de conexion a un modem no puede ser cero, el tiempo en el que seproduce un Evento COLGAR solo puede ser estrictamente mayor que el del MARCAR quelo ha originado y, sin embargo, el tiempo en el que se origina un Evento de tipo MARCARpuede ser mayor o igual que el del Evento anterior del mismo tipo.

En cuanto a la funcionalidad basica del Simulador, se distinguen dos operaciones: la que loconstruye para cada Simulacion que se quiera efectuar, esto es la que inicializa sus atributosdados un numero de modems y un tiempo medio de conexion, y la que simula el funcionamientodel Banco, esto es gestiona segun una Cola de Prioridad la Coleccion de Eventos que se vanproduciendo.

A continuacion se describe en pseudo-Java una forma de simular en la que el tiempo total deSimulacion se establece en base al numero de eventos que se deseen procesar, que representa elparametro numEventos: al inicio de la Simulacion se generan numEventos de tipo MARCAR,cada uno de los cuales se integra en el proceso de Simulacion al ser insertado en la Cola dePrioridad del Simulador; su procesado se relega al bucle de Simulacion durante el cual soloalgunos de ellos, los que representen peticiones que pueden ser atendidas, daran lugar a loscorrespondientes Eventos COLGAR.

8

2. Modelos Lineales y sus Aplicaciones

public void simular(int numEventos){/** inicializar this.colaPrioridad con numEventos de tipo MARCAR */tiempoPeticion = generarSegunUniforme(1);numeroPeticion = 1;tipoPeticion = Evento.MARCAR;for (int i = 1 ; i <= numEventos; i++){

Evento e = new Evento(tiempoPeticion, i, tipoPeticion) ;this.colaPrioridad.insertar(e);tiempoPeticion = generarSegunUniforme(tiempoPeticion);

}/** bucle de Simulacion: procesar siguiente Evento */while ( !this.colaPrioridad.esVacia() ) {

Evento e = (Evento) this.colaPrioridad.eliminarMin() ;/** procesar(e) */if ( e.tipoEvento() == Evento.MARCAR ){

System.out.print("Peticion de Conexion al Banco numero "....);if ( this.modemsLibres > 0 ){

modemsLibres--;int duracion = e.tiempo() + obtenerSegunGauss();Evento asociadoE = new Evento(duracion, e.identificador(), Evento.COLGAR);this.colaPrioridad.insertar(asociadoE);System.out.println("Peticion de Conexion al Banco Aceptada ... );

}else System.out.println("Rechazada. Intente la conexion mas tarde");

} else {modemsLibres++;System.out.println("Conexion finalizada. Gracias por utilizar este servicio");actualizarEstadisticas(e);

}}

}

En terminos de esta propuesta, si se desea realizar una Simulacion con un Banco de 3

Modems, con un tiempo medio de Conexion de 5 y 15 peticiones de conexion, la aplicacion deSimulacion se lanzarıa como sigue:

public class SimulacionBancoModems{public static void main(String args[]){

Simulador s = new Simulador(3, 5);s.simular(15);

}


2.1. Lista Con Punto de Interes

Como ya se ha explicado, un Modelo Lineal de Acceso Secuencial es aquel cuyas operacionespermiten el Acceso a todos los Datos de una Coleccion, uno detras de otro vıa operacion sucesor(o predecesor); por ejemplo, si se quiere buscar una cancion en una cinta, esta se debera RecorrerSecuencialmente hasta encontrarla. Ası, las cuatro operaciones basicas de este Modelo son:

inicio(), que inicializa el Acceso Secuencial a la Coleccion a partir del primer Dato;



recuperar(), que obtiene el unico Dato que es accesible en cada momento;

siguiente(), que hace accesible el siguiente Dato de la Coleccion;

esFin(), que comprueba si quedan mas Datos de la Coleccion a los que acceder.

y en terminos de las cuales un Recorrido Ascendente de una Coleccion l se podrıa codificarcomo sigue:

for ( l.inicio(); !l.esFin(); l.siguiente())visitar( l.recuperar() );

Notese que en cada paso de la anterior iteracion se recupera un unico Dato de la Coleccion,el que ocupa el PUNTO DE INTERES actual y las operaciones esFin y siguiente se aplican,tambien implıcitamente, sobre dicho punto.

A partir de la descripcion realizada, se defina la EDA Lista Con Punto de Interes comouna Coleccion homogenea de Datos que solo se puede manipular accediendo secuencialmente alDato que ocupa el Punto de Interes; cuando no hay elemento alguno bajo el Punto de Interesactual, bien porque la Coleccion esta vacıa o esFin(), no tiene sentido recuperar, borrar nipasar al siguiente.

El Modelo descrito resulta familiar, pues ha sido utilizando en PRG y EDA hasta la fechaimplıcitamente, a traves de sus Implementaciones contigua o enlazada. Ası, si una Coleccionde una cierta talla se Representa sobre un array, su Recorrido Ascendente se realizarıa comosigue:

for ( int i = 0; i < talla(); i++ )visitar(array[i]);

Si por el contrario se utiliza una Representacion de Lista Enlazada Indirecta (LEI), se tendrıa:

for ( NodoLista aux = primera; aux != null; aux = aux.siguiente )visitar( aux.dato );

Mientras que con una Representacion contigua o enlazada el PUNTO DE INTERES apareceexplıcitamente, como el ındice i de array o el Enlace aux, el Modelo Lista Con Punto de Interesoculta estos detalles, relegandolos a la que sera su Implementacion.

A continuacion se describen los tres tipos de operaciones que definen ya completamente elModelo o Especificacion de una Lista Con Punto de Interes:

las consultoras esVacia(), que comprueba si la Lista esta o no vacıa, las ya presentadasesFin() y recuperar();

las modificadoras del Punto de Interes fin(), que lo situa al final de la Lista, tras su ultimoDato, y las ya presentadas inicio() y siguiente();

las modificadoras de la propia Lista, insertar(x) que inserta un nuevo Dato a la Listay borrar() que lo elimina

10


L1L = L2 Li+1 L nLi−1 Li

Punto de Interes

Figura 1: Ejemplo de una Lista Con Punto de Interes

En la figura 1 se muestra un ejemplo de una Lista Con Punto de Interes en la que se harepresentado el PI con una especie de ventana que senala o se abre sobre el unico Dato accesiblede la Lista.

En concreto, la insercion de un elemento se realizara inmediatamente delante del que esta ac-cesible a traves del punto de interes, permaneciendo este inalterado. Ası, si se tiene la Lista A

H E F con el punto de interes sobre E y se anade el nuevo elemento B, tendremos la lista AHBEF

tal y como se indica en la figura 2. Notese que la insercion al final de la lista requiere mover elpunto de interes una vez pasado el ultimo elemento.

EAL = H F

Punto de Interes

E FAL = H B

Punto de Interes

Figura 2: Insercion en una Lista Con Punto de Interes

El borrado de un elemento en una lista con punto de interes se efectuara sobre el elementosituado sobre dicho punto; una vez eliminado, el punto de interes queda marcando al que hastaahora era el elemento siguiente al punto de interes; un ejemplo se muestra en la figura 3.

EAL = H F

Punto de Interes

FAL = H B

Punto de Interes

Figura 3: Borrado en una Lista Con Punto de Interes

Obviamente esta definicion de Lista no es unica; por ejemplo se podrıa definir la inserciondespues del punto de interes o se podrıan definir operaciones de manejo del punto de interesque permitan iterar sobre la Lista en sentido descendente.

El interfaz ListaConPI

El comportamiento de la Lista descrito anteriormente se puede especificar a traves delsiguiente interfaz que llamaremos ListaConPI.

/* Metodos:* insertar : inserta el dato como nuevo elemento anterior al punto de interes, que queda inal* borrar : elimina el elemento que ocupa el punto de interes; este queda inalterado,

apuntando al elemento que seguıa al que se ha borrado;* inicio : situa el punto de interes sobre el primer elemento de la lista* fin : situa el punto de interes al final de la lista, detras del ultimo elemento* siguiente: avanza el punto de interes* esFin : true si el punto de interes esta al final, detras del ultimo elemento



* recuperar: recupera el elemento se~nalado por el punto de interes* esVacia : devuelve true si la lista no tienen ningun elemento y false en caso contrario*/

package modelos;interface ListaConPI {

boolean esVacia();boolean esFin();/* Aplicable si !esFin() */Object recuperar ();void inicio();void fin();/* Aplicable si !esFin() */void siguiente();void insertar(Object d);/* Aplicable si !esFin() */void borrar ();

}

Las posibles situaciones de error que se producirıan cuando se intenta recuperar, borrar opasar al siguiente, se evitan con la precondicion expresada: no se pueden aplicar a una Listavacıa o en la que el punto de intees no este situado sobre algun elemento de la misma; es decircuando se cumple esFin=true. Tambien se podrıan haber tratado mediante el lanzamiento deexcepciones de usuario, tal y como se propone en el ejercicio numero 2 de esta misma seccion.

Cuestiones:

1. Escribid una secuencia de instrucciones que permita construir la Lista Con Punto deInteres con los Integer 1, 2, 3, 5, 6.

2. Dada la Lista Con Punto de Interes 1, 2, 3, 5, 6 con el punto de interes situado sobre el 6,¿es equivalente hacer insertar(new Integer(4)) y despues borrar() que hacer primeroborrar y despues insertar?.

En particular, la implementacion del metodo toString para mostrar el contenido de laLista o del metodo de busqueda de un elemento, se pueden realizar utilizando unicamente lasoperaciones del interface y por tanto, de forma independiente de la Implementacion final dela Lista. El metodo buscar busca en la lista el primer elemento igual al que se pasa comoparametro devolviendo la posicion que dicho elemento ocupa en la Lista o −1 si no encuentraningun elemento igual al que se busca. A continuacion se presenta una clase abstracta como unaforma de ubicar estos dos metodos que no pueden estar en el interfaz pero que, por tener unacodificacion independiente de futuras implementaciones de ListaConPI, no resulta convenienterepetirlas esn las clases de las implementaciones:

package lineales;public abstract class ListaConPIExt implements ListaConPI {

public String toString() {string s; this.inicio(); // punto al principiowhile ( !this.esFin() ) {

Object x = this.recuperar(); // recuperar el elemento sobre PI

12

2.

s += x.toString(); // acumular sobre el stringthis.siguiente(); // avanzar al siguiente

}

public int buscar (Object x) {this.inicio(); int pos = 0; // punto al principio y posicion a 0while ( !this.esFin() && !this.recuperar().equals(x)) {

this.siguiente(); // avanzar al siguientepos++; // incrementar pos

}// averiguar si se encuentra o no:if ( this.esFin() ) return -1;else return pos;

}}

Cuestiones:

1. Anadir a la clase ListaConPIExt un metodo, esta(x), que devuelva el valor true si xesta en la lista y false en caso contrario.

2. El interfaz ListaConPI se puede modificar para que contemple el lanzamiento de la excep-cion de usuario ElementoNoEncontrado cuando se intenten aplicar de forma incorrectalos metodos recuperar, siguiente y borrar. Defınase este nuevo interfaz y reescrıbanseen base a sus metodos buscar y toString. Discutanse las diferencias observadas entrelas dos definiciones propuestas.

2.2. Pila

Las Pilas y las Colas son quizas los modelos de datos mas utilizados en computacion. UnaPila modeliza una estrategia de acceso a la Coleccion de Datos de tipo LIFO (Last In FirstOut), en la que el unico Dato accesible en todo momento es el ultimo que se inserto. En ella lasinserciones y borrados se realizan en un mismo punto que se denomina Tope de la Pila. En lafigura 4(a) se muestra una pila con cuatro elementos; si se anade un elemento E se situara enel tope (4(b)). Si se borra un elemento de la pila actual, este sera precisamente el E; despuesde tres borrados sucesivos sobre la pila que se muestra en 4 (b) se obtiene la pila de la figura4(c).

El interfaz Pila

La Pila es un modelo muy sencillo que se puede especificar a traves del siguiente interfaz.Consta de dos metodos modificadores apilar y desapilar para insertar y borrar Datos en elTope de la Pila, y de dos metodos consultores tope y esVacia; el primero consulta el ultimoelemento insertado y el segundo comprueba si la Pila tiene o no Datos. Notese que no se hacontemplado la situacion de excepcion que puede suceder si se intenta desapilar o acceder altope de una pila vacıa por medio de una excepcion de usuario; se espera que el usuario delinterfaz exija la condicion de que la pila no este vacıa antes de llamar a los metodos desapilary tope.


2.

A

B

C

D

TOPE E

C

B

A

D

TOPE

A

B

TOPE

(a) (b) (c)

Figura 4: Ejemplo de una Pila

/* Interfaz Pila:* void apilar(x) : a~nade x en el tope de la pila* Object desapilar() : devuelve el elemento en el tope de una pila no vacıa y lo elimina;* Object tope () : devuelve el ultimo elemento insertado en una pila no vacıa, el tope* boolean esVacia() : devuelve true si la pila esta vacıa, sino false*/

package modelos;interface Pila {

void apilar (Object x);/* se debe aplicar a una pila NO vacıa, sino Error de Ejecucion */Object desapilar ();/* se debe aplicar a una pila NO vacıa, sino Error de Ejecucion */Object tope ();boolean esVacia();

}

Uso de Pilas

El comportamiento LIFO se observa en multiples situaciones de la vida real; por ejemplo lapila de bandejas disponibles en el autoservicio de comedor de la cafeterıa, el papel de la bandejade la impresora, etc.

En el tema 3 de esta asignatura se reviso el modelo de ejecucion de un metodo recursivo y seplanteo como estrategia el uso de una Pila, la Pila de la Recursion. Cada vez que se produceuna nueva llamada, el registro de activacion con la informacion asociada a dicha llamada seanade a la pila; en todo momento la informacion disponible es la que se encuentra en el topede la pila; cuando el codigo de una llamada termina, se elimina el registro asociado que es elsituado en el tope de la pila. Los registros por debajo de este corresponden a llamadas quetodavıa no han concluido.

Tambien se necesita una Pila para resolver el problema de establecer la correspondencia entrelos parentesis abiertos y cerrados de una expresion. Por ejemplo, en la cadena (a ∗ (b + c) + d),el parentesis abierto de la posicion 0 se corresponde con el cerrado de la posicion 10, y el dela posicion 3 con el de la posicion 7. Se desea escribir un metodo en Java que, tomando como

14

2.

entrada un String, muestre por pantalla los pares de parentesis que se correspondan ası comoaquellos parentesis desemparejados. Notese que si se analiza la cadena de izquierda a derecha,cada parentesis cerrado se corresponde con el ultimo abierto que se ha encontrado. Ası, laestrategia para resolver el problema consiste en analizar el String de izquierda a derecha, siel caracter analizado es un parentesis abierto, su posicion se almacena en una pila. Cuando seencuentra en la entrada un parentesis cerrado, el correspondiente abierto esta en la posicionindicada por el tope de la pila (si existe tal valor) y este valor ya se puede eliminar de la pila;si la pila estuviera vacıa, se detecta que el parentesis no se puede emparejar. Esto es lo quesucede al analizar la cadena (a + b)).

El siguiente metodo Java resuelve este problema:

public static void ajustaParentesis (String expresion) {

Pila p = new ...; // cierta clase que implemente el interfaz Pila

int long = expresion.length();for ( int i=0; i<long; i++ ) {

if ( expresion.charAt(i) == ’(’ ) p.apilar(new Integer(i));else if ( expresion.charAt(i) ==’)’ )

if ( !p.esVacia() ) System.out.println(p.desapilar() + "\t" + i);else System.out.println(i + " sin emparejar);

}while (!p.esVacia())

System.out.println(p.desapilar()+" sin emparejar);}

Si los metodos apilar y desapilar se implementan con coste constante; esto es, con costeindependiente del numero de elementos de la pila, la complejidad del metodo disenado es Θ(n),donde n es el numero de elementos de caracteres de la expresion que se analiza.

El problema del Laberinto

Un laberinto es un area rectangular con una entrada y una salida, que esta estructuradaen filas y columnas paralelas a sus lımites; cada posicion en esta area representa bien un pasolibre, bien un obstaculo. Si se supone que la entrada al laberinto esta en el extremo superiorizquierdo y la salida en el inferior derecho, se desea comprobar si existe un camino que llevedesde la entrada a la salida del laberinto, teniendo en cuenta que para avanzar en el laberintosolo hay cuatro movimientos posibles a las posiciones contiguas a la actual al norte, sur, estey oeste. En la figura 5 se muestra un ejemplo de un Laberinto sobre el que se ha marcado uncamino desde la entrada hasta la salida.

Para resolver este problema se utiliza una Pila en la que se guardan las posiciones queconforman el camino desde la entrada hasta la salida.

Representacion del Laberinto: el laberinto se puede representar como una matriz quepodemos suponer cuadrada y con valores 0 (paso libre) o 1 (obstaculo). Ası:

Laberinto[i][j] =

{0 si [i][j] es una posicion libre1 si [i][j] es un obstaculo


2.

E

S

Figura 5: Ejemplo de una Pila

Como ya se ha mencionado, desde cada casilla del laberinto (i, j) hay 4 movimientos posibles:a la derecha, abajo, a la izquierda y arriba y los ındices de las casillas o posiciones a las que seaccede son respectivamente [i][j + 1], [i + 1][j], [i][j − 1] y [i − 1][j] (figura 6).

i

j

i−1

i+1

j−1 j+1

Figura 6: Movimientos permitidos en el Laberinto

Estos cuatro posibles movimientos se analizaran de forma sistematica, primero a la derecha,despues abajo, despues a la izquierda y finalmente arriba y su codificacion se puede realizarutilizando un array, desplazamiento, con la siguiente informacion:

MOVIMIENTO CODIGO DESPLAZAMIENTO

derecha 0 (0,1)abajo 1 (1,0)izquierda 2 (0,-1)arriba 3 (-1,0)

Notese que no en todas las posiciones del laberinto existen cuatro movimientos posibles,serıan casos particulares los bordes en los que solo hay tres y las cuatro esquinas desde las quesolo hay tres. Para poder realizar un tratamiento uniforme se puede rodear el laberinto porun marco de obstaculos; esta circunstancia obliga a representar el Laberinto con 2 filas y 2columnas mas de las precisas, ası si el laberinto se define de un cierto tamano (talla), esto escon talla filas y columnas, el array bidimensional se debe de crear de dimension talla+2. Lasfilas y columnas 0 y talla+ 1 constituyen el marco de obstaculos. El laberinto se encuentra porlo tanto entre las filas y columnas 1 y talla (ambas inclusive). La posicion (1, 1) es la entrada

16

2.

y la (talla, talla) la salida. En la Figura siguiente se muestra un Laberinto 4x4, en el que laentrada y la salida se han marcado con un cırculo.

1

11

1

0 1

1

1

1111

1

1

1

1 1 1 1 1 1

0

0 0 0

0101

1 0 0 1

011

Figura 7: Laberinto 4x4 con el marco de obstaculos

La estrategia de resolucion del problema exige la exploracion de las posiciones libres co-menzando en la (1, 1) y terminando en (talla, talla) si se encuentra camino o cuando se hanexplorado todas las posibilidades y no se puede continuar hacia la salida. Como desde cadaposicion hay tantas posibilidades de continuacion como posiciones libres haya a la dercha, aba-jo, a la izquierda o arriba, se utilizara una Pila para almacenar todas aquellas posiciones conalternativas pendientes de visitar: cuando se llega a una posicion desde la que no se puede con-tinuar, se vuelve atras y se ensaya, desde el ultimo punto en el que se tomo un cierto camino,otras posibilidades pendientes. Para no volver a visitar posiciones ya exploradas, estas se pue-den marcar con 1 sobre el mismo array bidimensional que representa el laberinto. En resumen,cada vez que se visita una posicion en el laberinto se intenta avanzar con el siguiente orden: ala derecha, abajo, a la izquierda y arriba, eligiendo la primera posicion libre (sin obstaculo) ysi todavıa quedan otras posibilidades de exploracion, esta posicion se guarda en la Pila parapoder continuar avanzando desde ella con otros movimientos, si desde el que se esta explorandono se tiene exito.

La estrategia se puede describir por medio del siguiente algoritmo:

posicion = (1,1);

while (!salida) {siguiente = primer vecino de posicion que aun no haya sido visitado;if ( existe siguiente ) {

apilar posicion;posicion = siguiente;marcar siguiente como ya visitado;

else // no se puede continuar desde posicionif ( la pila no esta vacıa ) posicion = tope de la pila;

}

Observese que el bucle terminara cuando se cumpla alguna de las dos condiciones siguientes:


2.

se ha alcanzado la posicion de salida del laberinto posicion = (talla, talla);

no hay salida porque no se puede seguir avanzando desde posicion y no quedan otroscaminos por explorar (la pila esta vacıa);

Notese que la estrategia propuesta resuelve el problema planteado pero no permite encontrarel camino mas corto para salir del laberinto. En el proximo apartado se resolvera este problemautilizando con estructura de datos auxiliar una Cola.

Cuestion: Aplicar la estrategia descrita para comprobar si existe o no camino en el Labe-rinto de la figura 8. ¿Cual es el camino que se encuentra? ¿Existe un camino mas corto desdela entrada a la salida?.

0

0

0 0 0

0101

1 0 0 1

011

Figura 8: Ejemplo de Laberinto

La complejidad temporal de este metodo es proporcional al tamano del Laberinto.Ejercicios:

1. Codificar en Java las clases Posicion y Laberinto. Esta ultima debe permitir crear unlaberinto de forma aleatoria de una cierta talla, mostrar el laberinto por pantalla ybuscar si existe un camino desde la posicion (1, 1) hasta la (talla, talla).

2. En el tema anterior se estudio una solucion recursiva al problema de Las Torres de Hanoi.Supongase ahora que se desea mostrar el estado de cada una de las torres; para ello sedebera representar el estado de cada torre y modificarlo cada vez que se mueve un disco.Puesto que los discos se eliminan de cada torres de forma LIFO, cada torre se puederepresentar como una pila. Se pide escribir un metodo en Java que resuelva este nuevoplanteamiento del problema.

2.3. Cola

Una Cola es tambien un modelo de datos lineal con dos puntos de acceso fijos, uno paraanadir elementos y otro para consultar y eliminar. Una Cola modeliza una estrategia FIFO(First In First Out). Al punto en el que se anaden elementos se le denomina Final y alpunto en el que se extraen y consultan elementos se le denomina Principio. Mas adelantese estudiara otra variedad de Cola, la Cola de Prioridad, en la que los borrados se realizaransegun cierto valor asociado a los elementos que se denomina Prioridad.

En la figura 9 se muestra una Cola con tres elementos; el primer elemento que se borrara de laCola sera el A, quedando la cola como se muestra en 9(b). El nuevo elemento D, se anadira des-pues de C.

18

2.

A B C

FINALPRINCIPIO

PRINCIPIO

A B C D

FINAL

(a)

(b)

Figura 9: Ejemplo de una Cola

El interfaz Cola

La estrategia FIFO o comportamiento de la Cola, se puede describir a traves del siguienteinterfaz Java. Se definen cuatro metodos, dos consultores primero y esVacia para acceder alprimer elemento de la Cola y comprobar si esta vacıa, respectivamente; y dos metodos quemodifican la estructura de la Cola, bien por la incorporacion de un nuevo elemento al final dela misma, encolar, bien por la eliminacion del elemento que esta al principio, desencolar.

/*Interfaz Cola:* void encolar(x) : a~nade x al final de la cola* Object desencolar () : elimina el primero de la cola, no vacıa, y lo devuelve* Object primero () : devuelve el primer elemento insertado en la cola no vacıa* boolean esVacia() : devuelve true si la cola esta vacıa, sino false*/package modelos;public interface Cola {

void encolar (Object x);/* se debe aplicar a una cola NO vacıa, sino Error de Ejecucion */Object desencolar ();/* se debe aplicar a una cola NO vacıa, sino Error de Ejecucion */Object primero ();boolean esVacia();

}

El problema de encontrar el camino mas corto entre dos puntos en unLaberinto

El problema que se plantea es encontrar el camino mas corto entre dos posiciones cuales-quiera de un Laberinto de las caracterısticas descritas en el subapartado anterior. La idea clavepara resolver este problema esta en explorar en primer lugar, los caminos mas cercanos a laposicion de partida. En el problema resuelto anteriormente, una vez elegido un camino, se se-guia hasta que o bien se llegaba a la salida del laberinto o bien no tenıa continuacion: siemprese intentaba seguir desde la ultima posicion visitada y por eso se utilizaba como modelo de da-tos para estructurar las posiciones visitadas una Pila. Ahora, la estrategia sugiere no explorar


2.

desde el ultimo que se visito sino desde los que menos distancia acumulada tienen, y estos sonprecisamente los primeros alcanzados; es por esto que en este caso se utiliza como modelos paraestructuras las posiciones pendientes de visitar una Cola.

El problema se resolvera en dos pasos: primero se construye una matriz con las distancias delos caminos mas cortos desde la posicion de partida hasta cada una de las posiciones alcanzablesy despues, y comenzando en la posicion destino se obtiene el camino de menor coste.

El calculo de las distancias de los caminos mas cortos se hara de la forma siguiente: losvecinos alcanzables desde la posicion de partida tienen distancia igual a 1, los vecinos de estostienen distancia 2 y ası sucesivamente hasta que se alcance la posicion de destino o no quedenvecinos alcanzables.

sea d(i,j) es la distancia hasta la posicion (i,j):si ( Lab[i][j+1]==0 ) d(i,j+1) = d(i,j) + 1;si ( Lab[i+1][j]==0 ) d(i+1,j) = d(i,j) + 1;si ( Lab[i][j-1]==0 ) d(i,j-1) = d(i,j) + 1;si ( Lab[i-1][j]==0 ) d(i-1,j) = d(i,j) + 1;

En las figuras siguiente (10 y 11) se muestra un laberinto y la matriz de distancias calculadasobre el para los puntos de inicio y fin marcados (3, 2) y (4, 6).

E

S

1

1

1

12

2

2 2

2 3

3

2

4

5

6

6

7

7

8

8

8

Figura 10: Ejemplo de Laberinto y matriz de distancias calculada

En la posicion final en la matriz de distancias se tiene la longitud del camino mas corto desdeel punto de inicio; el siguiente paso es deshacer el camino desde el final accediendo siempre aaquel que tiene una longitud una unidad menor que la actual.

La implementacion de un metodo en Java que obtenga el camino mas corto entre dosposiciones cualesquiera de un Laberinto, utiliza muchas de las ideas que se habıan comentadoen el problema de comprobar si existe o no camino en un Laberinto. La matriz de distanciasse puede calcular directamente sobre el mismo laberinto para no tener que utilizar memoriaadicional; en este caso se debe realizar alguna codificacion que permita distinguir la situacion de”posicion ya visitada”de la de camino de distancia 1”; para ello se puede optar por la solucionque propone Shani es incrementar todas las distancias en 2. Ası:

Laberinto[i][j] =

0 si [i][j] es una posicion libre1 si [i][j] es un obstaculo¿1 si la distancia del camino mas corto hasta [i][j] es Laberinto[i][j] − 2

20

3. Modelos Avanzados y sus Aplicaciones

E

S

1

1

1

12

2

2 2

2 3

3

2

4

5

6

6

7

7

8

8

8

Figura 11: Obtencion del camino mas corto

La complejidad temporal del metodo propuesto es O(talla2), donde talla es la dimensiondel Lbaerinto; esta es la cota del coste del calculo de la matriz de distancias, ya que la obtenciondel camino mas corto tiene un coste que es lineal con la longitud de dicho camino.

Ejercicio: Escribir en Java un metodo para obtener el camino mas corto en un Laberintode las caracterısticas anteriormente mencionadas.


3.1. Cola de Prioridad

Una Cola de Prioridad es una Coleccion de Datos que tienen asociada cierta informaciono valor asociado, que se denomina Prioridad, que determina el orden en el que se accede adichos datos. Se diferencia del modelo de Cola porque en aquella el acceso se realiza por elorden en el que los elementos se han incorporado a la Cola.

La funcionalidad tıpica de una Cola de Prioridad se establece en base a las dos operacionessiguientes:

acceder al elemento menor de la coleccion: buscarMin;

acceder al elemento menor y eliminarlo: eliminarMin;

El interfaz ColaPrioridad

El comportamiento de una Cola de Prioridad se puede concretar en la siguiente definicionde interfaz:

/*Interfaz ColaPrioridad:* void insertar(x) : a~nade x a la cola* Object buscarMin() : devuelve el elemento con prioridad mas peque~na de una cola no vacıa* Object eliminarMin(): devuelve el elemento de menor prioridad de una cola no vacıa y lo e* boolean esVacia() : devuelve true si la cola esta vacıa, sino false*/



package modelos;public interface ColaPrioridad {

void insertar (Object x);/* se debe aplicar a una cola NO vacıa, sino Error de Ejecucion */Object buscarMin ();/* se debe aplicar a una cola NO vacıa, sino Error de Ejecucion */Object eliminarMin ();boolean esVacia ();

}

3.2. Diccionario

Un Diccionario es una EDA especialmente disenada para favorecer el proceso de busqueda deun Dato en una Coleccion. Ası, un Diccionario es una Coleccion de Datos homogenea y dinamicaque tiene como operaciones caracterısticas insertar un Dato que no estuviera previamente enla Coleccion, borrar un Dato de la Coleccion y buscar un Dato en la Coleccion. En general, seconsiderara que en un Diccionario no hay datos repetidos; no obstante, si en alguna aplicacion esnecesario tratar con elementos repetidos, se puede hacer o bien representar el dato una sola vezanotando su frecuencia o el numero de veces que aparece bien representando las repeticionesexplıcitamente sobre la EDA; elementos repetidos interesa manejar en aplicaciones como lageneracion de referencia cruzadas en un texto, por ejemplo.

Un Diccionario se puede implementar utilizando una representacion enlazada (LEI); enconcreto, y en el caso de que sobre el dominio de los elementos del conjunto se pueda estableceruna relacion de orden total, la implementacion como Lista Ordenada, conduce a una solucionde coste lineal con el numero de entradas del Diccionario, para cualquiera de sus operaciones.Una representacion alternativa en la que estas operaciones tienen coste medio logarıtmico seconsigue utilizando un Arbol Binario de Busqueda; la implementacion mediante Tablasde Dispersion, permite obtener costes medios independientes de la talla del problema, estoes, constantes. Estas implementaciones se estudiaran en los temas 8 y 9.

El interfaz Diccionario

El modelo de la EDA Diccionario se puede representar mediante el siguiente interfaz; en else definen dos metodos modificadores insertar y borrar, y dos metodos consultores buscar

y esVacio. En particular, se define insertar para que en el caso de que el objeto a insertar yaestuviera en el diccionario, lance la excepcion ElementoDuplicado; esta misma excepcion es laque lanza borrar cuando, por no poder encontrar el elemento, no puede borrar. Las situaci

/*Interfaz Diccionario:* void insertar(x) : a~nade x en el Diccionario; si ya esta se lanza la excepcion ElementoD* Object buscar(x) : busca x en el Diccionario; si x no esta lanza la excepcion ElementoNo

si esta devuelve la informacion asociada* Object eliminar(x): borra x del Diccionario; si x no esta lanza la excepcion ElementoNoEn* boolean esVacio() : devuelve true si el diccionario esta vacio, sino false* Excepciones:* ElementoDuplicado : cuando el objeto que se desea insertar ya esta en el Diccionario* ElementoNoEncontrado: cuando el objeto que se busca o se desea eliminar no esta enn

22


el Diccionario */package modelos;public interface Diccionario {

void insertar (Object x) throws ElementoDuplicado;void eliminar (Object x) throws ElementoNoEncontrado;Object buscar (Object x) throws ElementoNoEncontrado;boolean esVacio();

}

Representacion de un Diccionario Bilingue

Existen multiples aplicaciones que manejan diccionarios y una de ellas es la Traduccion detextos. Un ejemplo sencillo plantea el diseno e implementacion de un Traductor Palabra aPalabra de castellano a ingles; es decir, dada una frase escrita en una determinada lengua, porejemplo castellano, se desea encontrar la traduccion en una lengua diferente, por ejemplo eningles. El resultado de la traduccion palabra a palabra de la frase de entrada es la concatenacionde las traducciones de cada una de las palabras que la componen (en el mismo orden); porejemplo, la traduccion de la frase La casa es roja es The house is red. Notese que estetipo de traduccion no conduce en la mayorıa de los casos a traducciones correctas; el problemade la traduccion automatica de textos es un problema muy complejo en el que intervienen otrasfuentes de conocimiento ademas de la informacion lexica como son las sintacticas, semanticasy pragmaticas.

Para poder realziar la traduccion planteada resulta imprescindible disponer de un Diccio-nario Bilingue; esto es,de una Coleccion de palabras en la lengua de referencia (castellano) consu traduccion en la lengua objetivo (ingles); utilizaremos la simplificacion de considerar unaunica traduccion por cada palabra; por ejemplo:

CASTELLANO INGLES

aceite oilabogado lawyeralbondigas meatballsabuela grandmotheralmıbar syrupabeja beeacelga chard... ...

El aspecto mas interesante de este problema es el tratamiento del Diccionario Bilingue;notese que este constara de una cantidad considerable de entradas, informacion que estara dis-ponible en algun tipo de dispositivo de memoria y que habra que estructurar u organizar paraque la operacion que se hara con mas frecuencia, la busqueda, se realice de la forma lo maseficiente posible. Esto es, precisamente, un caso particular del modelo general del Diccionario.

La estrategia a realizar para llevar a cabo el proceso de traduccion exige, en primer lugar,cargar el Diccionario Bilingue sobre la EDA elegida; una vez realizado este proceso la traduccionconsistira en leer la frase a traducir palabra a palabra y con cada palabra (que no sea unsigno de puntuacion) consultar el Diccionario para conocer su traduccion en la lengua objetivo;finalmente se mostrara la frase traducida como concatenacion de las traducciones obtenidas.



Puede ocurrir que alguna palabra no se encuentre en el Diccionario, ante esta situacion lapalabra quedara sin traducir haciendolo notar en la frase de salida; opcionalmente se puedeofrecer al usuario la posibildiad de incorporar el nuevo termino al diccionario siempre que elusuario sea capaz de darle una traduccion.

Otros Ejercicios:

1. Disenese un interfaz para modelizar el comportamiento de una Secuencia. Una Secuenciaes un Modelo de Datos lineal en el que el acceso a los elementos se realiza a travesde la posicion o ındice que ocupa el elemento en la Secuencia. Las operaciones que lacaracterizan son las siguientes: anadir un elemento al final de la Secuencia, borrar unelemento dado, dado un ındice que representa la posicion en la secuencia, consultar el dato,dado un objeto, consultar la posicion que ocupa en la secuencia, consultar el numero deelementos de la secuencia, consultar si la secuencia esta vacıa y obtener una representacionsobre array de la Secuencia;

2. Senala las diferencias mas importantes entre las EDA Lista COn Punto de Interes ySecuencia.

3. Enriquecer la EDA Pila con la siguiente funcionalidad:

a) invertir la Pila; esto es construir una nueva Pila en la que sus elementos aparezcanen orden inverso al original. Se pide tanto el diseno recursivo como iterativo.

b) comprobar si la Pila es sombrero de otra; se dice que una pila p es sombrero de otrapila q si todos los elementos de p estan en q en el mismo orden y en posiciones masproximas a la cima. Se pide el metodo recursivo.

c) transformar la Pila en una Cola, de forma que el elemento situado en el tope de lapila quede el ultimo en la cola. Se pide el metodo recursivo.

4. Ampliar la clase abstracta ListaConPI con un metodo recursivo que concatene una listadada a continuacion de la lista actual.

5. Se desea conocer el numero de palabras distintas, junto con su frecuencia de aparicion deun texto. Disenese una aplicacion Java que permita resolver este problema.

24

Documents

Estructuras de Datos y Algoritmos. Curso 2004/05 …users.dsic.upv.es/~nprieto/clases/EDA0506/T4/traspas4.pdf · Estructuras de Datos y Algoritmos. Curso 2004/05 Tema 4. ... Como